병행 제어

데이터의 접근

→ 저장과 연산하는 곳이 다름

Race Condition

•

여러 주체가 하나의 데이터에 동시에 접근하려고 할 때

storage box 는 메모리 주소 공간, 메모리, 디스크

execution box 는 CPU 프로세스, CPU, 컴퓨터 내부

→ 멀티프로세서 or 공유 메모리 사용 등으로 인해 race condition 발생

OS 에서 race condition 이 발생하는 경우

kernel 수행 중 interrupt 발생 시

•

interrupt handler vs kernel

•

load 하고 increase 하고 store 하는 세 개의 인스트럭션이 수행되는 동안 발생

•

커널 모드 running 중 interrupt 가 발생하여 interrupt 처리 루틴 수행  → 양쪽 다 커널 코드이므로 kernel address space 공유

•

해결 방법으로는 interrupt 를 disable 시키고 나서  interrupt 실행

process 가 system call 을 하여 kernel mode 로 수행 중에 context switch 가 일어나는 경우

•

해결 방법으로는 커널 모드에서 수행 중일 때는 할당 시간이 지나도 CPU 를 preempt 하지 않고 커널 모드에서 사용자 모드로 돌아갈 때 preempt 한다.

multiprocessor 에서 shared memory 내의 kernel data

•

해결 방법으로는 커널 내부 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock, unlock 을 한다.

Process Synchronization 문제

•

공유 데이터(shared data) 에 대한 동시 접근(concurrent access) 은 데이터의 불일치 문제를 발생시킬 수 있다.

•

일관성(consistency) 유지를 위해 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요

Race Condition

•

여러 프로세스들이 동시에 공유 데이터에 접근하는 상황

•

데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

•

race condition 을 막기 위해 concurrent process 는 동기화(synchronize) 되어야 한다.

사용자 프로세스 P1 수행 중 timer interrupt 가 발생해서 context switch 가 일어나 P2 가 CPU 를 잡는다면?

The Critical-Section Problem(임계구역)

•

여러 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

•

각 프로세스의 code segment 에는 공유 데이터에 접근하는 코드인 critical section 이 존재

•

count++ 등이 critical section 의 예시

•

해결책

{
	entry section;
	critical section;
	exit section;
}
C
복사

임계 구역에 들어가기 전에 lock 등으로 다른 프로세스의 접근을 막는다.

해결법 조건

•

Mutual Exclusion(상호 배제)

◦

하나의 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 critical section 에 들어가면 안된다.

•

Progress

◦

아무도 critical section 에 있지 않은 상태에서 critical section 에 들어가고자 하는 프로세스가 있으면 critical section 에 들어갈 수 있다.

•

Bounded Waiting(유한 대기)

◦

프로세스가 critical section 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야 한다.

◦

임계 구역에 들어가고자 하는 프로세스가 3개 있고 임계 구역에 2개의 프로세스만 번갈아가면서 들어가는 경우 해당 조건을 충족하지 못함

Algorithm 1

do {
	while (turn != 0);
	critical section
	turn = 1;
} while (1);
C
복사

•

do while 과 turn 으로 구분

•

progress 조건을 만족하지 못한다.

◦

프로세스 0이 1초에 10번 critical section 에 들어가고 프로세스 1이 1초에 1번 critical section 에 들어가면 프로세스 0은 1초에 1번밖에 critical section에 들어가지 못한다. 프로세스 1이 들어가서 0으로 바꿔줘야 하기때문에

Algorithm 2

do {
	flag[i] = true;
	while (flag[j]);
	critical section
	flag[i] = false;
} while (1);
C
복사

•

flag[j] 가 true 가 아닐 때 프로세스 i 가 criticaal section 에 들어갈 수 있다.

•

progress 조건을 만족하지 못한다.

◦

i 와 j 동시에 flag를 true 로 만들면 두 프로세스 모두 while 에서 대기

Algorithm 3 (Peterson’s Algorithm)

do {
	flag[i] = true;
	turn = j;
	while (flag[j] && turn ==j);
	critical section
	flag[i] = false;
} while (1);
C
복사

•

Algorithm 1, 2 를 결합한 것

•

조건을 모두 만족함

•

busy waiting(spin lock) 문제

◦

계속 CPU 와 memory 를 쓰면서 wait

Synchronization Hardware

•

하드웨어로 test & modify 를 atomic 하게 수행할 수 있도록 지원하는 경우 문제가 쉽게 해결 가능

◦

공유 데이터의 읽는 작업과 쓰는 작업을 한번에 수행하면 해결 가능

◦

test_and_set(a) 라는 인스트럭션

Semaphores

•

Semaphore S:

◦

integer(자원의 갯수)

◦

P, V 연산에 의해서만 접근 가능

◦

atomic 연산

•

P(S): 

◦

while (S≤0) wait;

◦

S—;

◦

세마포어 변수 값을 획득하는 연산

◦

S 값이 양수가 될 때까지 busy-wait

•

V(S):

◦

S++;

◦

반납하는 연산

do {
	P(mutex); /* mutext 는 mutual exclusion */
	critical section
	V(mutex);
} while (1);
C
복사

•

busy wait 방식(spin lock)

•

block & wakeup 방식(sleep lock) 으로 해결 가능

Block & Wakeup 방식

•

Semaphore 를 integer 변수 값(value)과 queue 변수 값(L)으로 정의

•

value 값이 단순히 공유 가능 자원 개수가 아니라, 공유 가능한지 상황을 나타낸다. 음수면 공유 불가, 양수면 공유 가능

•

P(S):

S.value--;
if (S.value < 0 ) {
	add this process to S.L;
	block();
}
C
복사

◦

value 가 부족하면 block 됨

•

V(S):

S.value++;
if (S.value <= 0) {
	remove a process P from S.L;
	wakeup(P);
}
C
복사

◦

단순히 자원을 반납하고 끝나는게 아니라 혹시 잠들어 있는 프로세스가 있다면 깨움

busy-wait vs block & wakeup

•

critical section 의 길이가 짧으면 busy-wait 방식도 좋음

•

일반적으로는 block & wakeup

binary semaphore(mutex)

•

자원의 값이 하나인 경우(값이 0, 1)

•

주로 lock/unlock 에 사용

counting semaphore

•

자원의 개수가 여러개 있을 때

•

resource counting 에 사용

Deadlock and Starvation

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event 를 무한히 기다리는 현상

•

세마포어 S, Q 두 개가 있을 때 어떤 일을 하기 위해 두 개 모두 획득해야 일을 할 수 있는 경우 데드락 발생

•

P0 이 P(S) 를 얻고 CPU 를 P1 이 가져감.

•

P1 이 P(Q) 를 얻고 P(S) 를 얻으려고 할 때 무한정 대기

•

해결방법: S, Q 를 얻는 순서를 하나로 정해주면 된다.

Starvation

특정한 프로세스가 영원히 자원을 얻지 못하고 기다리는 현상

•

특히 일부 프로세스만 자원을 가지고 특정 프로세스만 못가지는 현상. 데드락은 관련된 모든 프로세스가 모두 못가짐.

Classical Problems of Synchronization

Bounded-Buffer Problem(Producer-Consumer Problem)

Producer 와 Consumer 가 여러 개

생산자나 소비자 2개가 한번에 왔을 때

•

데이터를 동시에 넣으려고 함

•

데이터를 동시에 꺼내려고 함

•

공간(buffer)에 락을 걸어서 진행

buffer가 가득 찼을 때

데이터를 집어 넣을 buffer 가 없다

그래서 생산자는 대기

•

동기화 변수로는 1. binary semaphore 와 2. integer semaphore

변수는 full = 0, empty = n, mutex = 1; 로 시작

•

P(empty) 에서 empty 가 0이 아니라면 버퍼 프로세스 획득 후 mutex 를 0으로 바꿈(락)

•

V(mutex) 로 반납 후 V(full) 로 full 변수에 1을 증가시킴

Readers and Writers Problem

•

DB 에서 발생

•

한 프로세스가 db 에 write 중일 때 다른 process 가 접근하면 안됨

•

read 는 동시에 여럿이서 해도 됨

•

해결책:

◦

writer 가 db 에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader 들을 다 db 에 접근하게 해준다.

◦

writer 는 대기중인 reader 가 하나도 없을 때 db 접근이 허용됨

◦

일단 writer 가 db 에 접근 중이면 reader 들은 접근이 금지됨

◦

writer 가 db 에서 빠져나가야만 reader 의 접근이 허용

•

공유 데이터

◦

db 자체

◦

read count

•

mutex 는 readcount 에 대한 배타락을 얻기 위한 세마포어 변수 

•

starvation 이 발생할 수 있음. 예시(신호등 존재 이유)

Dining Philosophers Problem

•

semaphore chopstick[5];

•

처음에 모든 values 는 1

•

생각하는 업무와 밥먹는 업무 2개 있음

•

문제점:

◦

데드락 발생 가능성

▪

다 각각 왼쪽 젓가락 잡았을 때

•

해결책

◦

4명의 철학자만 테이블에 앉을 수 있도록

◦

젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게

◦

짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락 부터 집도록 비대칭 전략

◦

•

self[5] 는 집을 수 있는 권한, 초기화 값은 0

•

이 부분이 일반적인 세마포어의 철학과는 다름

◦

자원의 개수를 초기값으로 하고 그 자원의 개수가 1이거나 1이상일 때를 권한으로 봄

◦

권한을 주는게 V(self[i]) → 0이었던 값을 1로 바꿈

Monitor

•

Semaphore 의 문제점

◦

코딩하기 힘듦

◦

정확성의 입증이 어려움

◦

자발적 협력이 필요

◦

한번의 실수가 모든 시스템에 치명적인 영향

•

언어 차원에서 동기화 문제 해결

•

동시 수행중인 프로세스 사이 abstract data type 의 안전한 공유를 보장하기 위한 high-level 동기화 construct

monitor monitor_name {
	procedure body P1 (...) {
		...
	}
	procedure body P2 (...) {
		...
	}
	procedure body Pn (...) {
		...
	}
	{
		initialization code
	}
}
Java
복사

•

객체지향 언어들은 객체를 중심으로 operation 들이 정의된다.

•

공유 데이터에 접근하기 위해서는 내부에 procedure 를 통해서만 공유 데이터에 접근할 수 있다.

•

프로그래머가 데이터에 락을 걸 필요가 없다.

•

모니터가 원천적으로 프로시저가 동시에 실행할 수 없도록 한다.

•

여러 프로세스가 동시에 접근해도 모니터가 알아서 queue 에 줄 세우고 프로시저를 순차적으로 실행시켜준다.

•

모니터 내에서는 한번에 하나의 프로세스만 활동 가능

•

프로그래머가 동기화 제약 조건(lock)을 명시적으로 코딩할 필요가 없다.

•

프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable(x, y) 을 사용

•

condition variable 은 wait 와 signal 연산에 의해서만 접근이 가능하다.

•

wait()

◦

x.wait() 을 invoke 한 프로세스는 다른 프로세스가 x.signal() 을 invoke 하기 전까지 suspend 됨

•

signal()

◦

x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다.

◦

suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.

•

생산자 소비자 모니터 코드

◦

P(mutex), V(mutex) 처럼 락을 걸고 해제하는 코드가 사라졌다.

•

식사하는 철학자

test 메서드 안의 self[i].signal() 은 인접 철학자가 putdown 시 깨워주기 위한 용도