6장 Synchronization

Background

공유 자원에 동시에 접근하는 것은 data inconsistency(데이터 불일치) 문제를 야기할 수 있다.

bounded buffer 문제는 n개 버퍼에 기껏해야 n-1개 아이템만 들어갈 수 있다.

counter 변수를 사용해서 n개 아이템이 들어갈 수 있도록 해보자.

그러면 counter++, counter-- 가 atomically하게 수행되어야 한다.

atomic operation은 인터럽트없이 명령이 완전히 수행되는 것을 의미한다.

counter++와 counter--는 컴퓨터에서 3개 명령으로 처리한다. (counter에서 레지스터로 값을 읽어오고, 레지스터 값을 1 증가하고, 레지스터 값을 counter변수에 넣기) 따라서 중간에 인터럽트가 되면 counter에 원하지 않는 값이 들어간다.

Race condition

여러 프로세스가 공유자원에 동시에 접근하는 상황

이러한 상황을 막기 위해 프로세스들이 synchronized 되어야 한다.

The Critical-section problem

 

공유 자원을 접근하는 코드부분.

한 프로세스가 critical section 부분을 실행중일 때 다른 프로세스가 공유자원을 접근하지 못하도록 해야 한다.

세가지 요구사항

1. mutual exclusion

한 프로세스가 critical section에서 수행중일때, 다른 프로세스들은 그들의 critical section을 수행할 수 없도록.

2. progress

critical section 밖에서 수행중인 프로세스들은 다른 프로세스가 그들의 critical section으로 들어가는 것을 방해할 수 없다.

3. bounded waiting

한 프로세스가 자신의 critical section에 접근하려고 하는데 다른 프로세스가 계속 사용중이라면 기다리는 시간이 한정되어 있다. 

첫번째 알고리즘

mutual exclusion인데, progress가 아니다. Pi가 critical section에 들어가지 않았는데도 Pj가 한번 더 들어갈 수가 없다.

공유데이터 이외에도 전체 코드를 보호할 수 있는데 이는 성능이 떨어진다.

두번째 알고리즘

mutual exclusion이지만 progress가 아님. 둘다 동시에 손들면 deadlock발생 가능성.

세번째 알고리즘

첫번째, 두번째 알고리즘을 합침. 3개 모두 만족

Bakery Algorithm

프로세스에게 번호표를 나눠준다. 가장 작은 수를 가진 프로세스가 critical section에 들어갈 수 있다.

번호는 항상 증가한다.

Synchronization Hardware

하드웨어로 critical section 문제 처리

critical section 들어갈때 인터럽트 disable, 나올때 enable.

Test and Set

특별한 하드웨어 명령어.

atomically하게 실행

Swap

위 두 알고리즘은 mutual exclusion 요구사항은 만족하지만 , bounded-waiting 요구사항은 만족하지 못한다. 운이 나쁘면 계속 못들어간다.

Semaphores and Mutexes

이전 solution들은 더 복잡한 문제에는 적합하지 않다.

세마포어는 OS에서 지원하고 하드웨어나 소프트웨어적으로 구현할 수 있다.

wait(S) 와 signal(S)함수는 atomic하게 실행된다.

while로 구현한 세마포어의 장점은

반응 속도가 빠르다는 점이고 단점은

while로 인해 cpu time을 낭비한다는 것이다. 이러한 종류의 세마포어를 spinlock이라고 부른다.

busy waiting을 피할 수 있는 세마포어

블락을 이용.

블락된 프로세스들의 리스트가 있다.

프로세스가 critical section을 벗어나면 signal을 통해 리스트에서 하나를 깨워준다.

PCB의 link field를 이용해 쉽게 구현가능.

FIFO 큐를 이용해서 bounded waiting 보장.

하지만 세마포어의 사용은 특정 큐 전략에 의존해서는 안된다.

wait와 signal 함수는 atomic하게 실행되어야 한다.

싱글 프로세서의 경우에는 그 프로세서가 인터럽트 못걸게 막으면 된다.

하지만 멀티 프로세서는 모든 프로세스를 막아야 하니 어렵고 성능이 떨어진다.

while로 구현한 세마포어를 사용할 경우 atomic하게 실행된다.

대개 프로그램을 잘짜면 long waiting이 드물다. 

Deadlocks and Starvation

두개 이상의 프로세스가 이벤트를 무한히 기다릴때, 그 이벤트는 기다리고 있는 프로세스 중의 하나가 생성할 수 있는 것일때. 이러한 상황을 Deadlock.

Starvation

무한 블락킹에 빠질경우. 프로세스가 세마포어에서 무한정 기다리게 된다. 예) 리스트가 LIFO일 때, Starvation의 가능성 있다.

두종류의 세마포어

Counting semaphore

세마포어 값(S)이 1보다 큰 값을 가질 수 있다.

critical section에서 여러개의 프로세스가 동시에 실행가능

Binary semaphore

세마포어 값이 0,1만 가진다.

구현이 쉽고

counting semaphore를 구현할 수 있다.??

Mutex

세마포어의 일종

binary 세마포어

소유권의 개념을 가지고 있음.(lock을 건 task만 unlock을 할 수 있다.)

주로 thread간 동기화에 쓰인다. 

Classical Problems of Synchronization

1. Bounded-Buffer using semaphores.

생산자는 empty 감소, full 증가.

소비자는 empty 증가, full 감소.

2. Readers-Writers Problem

버퍼는 하나이고 리더와 라이터는 여러명 일때 버퍼에 어떻게 access하나?

reader를 존중했을 때

writer가 버퍼 사용을 허락받았으면 readers는 기다림.

다른 리더가 버퍼 사용하고 있어도 리더들은 안기다려도됨.

writer가 unbounded waiting에 빠질 수 있음.

writer를 존중했을 때

writer가 빨리 수행될 수 있도록.

writer가 기다리고 있을 때는 어떤 새로운 reader도 buffer에 접근할 수 없다.

reader가 unbounded waiting에 빠질 수 있음.

둘 다 starvation 문제가 있다.

Dining-Philosophers Problem

하는 일이라곤 생각하고 먹을 줄만 아는 5명의 철학자.

둥그런 탁자에 젓가락이 5개밖에 놓여져 있지 않고

배고프면 양옆에 있는 젓가락 2개를 집어야 먹을 수 있다.

하지만 하나 밖에 못집는 상황이 발생.

deadlock과 starvation이 발생할 가능성이 있다.

젓가락 갯수만큼 세마포어가 있을 경우

5명 동시에 젓가락을 하나 집었을 경우 데드락발생

해결방법

철학자 4명만 테이블에 앉게 하기

양쪽 젓가락이 모두 이용가능할때만 집기

홀수 철학자는 왼쪽 젓가락을 먼저 집고 그다음 오른쪽 젓가락을 집는다. 짝수 철학자는 왼쪽 젓가락을 집고 그다음 오른쪽 젓가락을 집는다.

Condition Variable

 어떤 공유 데이터가 특정 상태에 이를 때까지 자신의 실행을 block하게 해준다.

mutex와 함께 사용된다.

mutex는 공유 데이터의 접근을 제어하고

condition variable은 쓰레드가 어떤 공유데이터가 특정한 상태에 이를때까지 wait하게 한다.

condition variable에 의해 wait된 쓰레드는 다른 쓰레드가 공유 데이터에 접근할 수 있도록 자동으로 mutex를 언락한다.

다른 쓰레드에 의해 호출된 signal에 의해 wait하고 있던 그 쓰레드는 다시 꺠어나 mutex를 lock한다.

Conditional variable을 사용하지 않으면 공유 데이터가 특정한 상태에 이르렀는지 계속 조사해야 하므로 쓰레드낭비다.

참고사이트: http://4ellene.net/tt/961