[7] Classic Problems of Synchronization

[ Classic Problems of Synchronization ]

 

[ Examples of a large class of Concurrency-Control Problems : 동시성 제어 문제의 고전적인 대표 예시들 ]

1) Bounded-Buffer Problem

- The Producer-Consumer Problem

2) Readers-Writers Problem

 

3) Dining-Philosophers Problem

 

 

[ Bounded Buffer Problem ]

 

Producer-Consumer Problem을 다시 떠올려보자.

사이즈 N의 버퍼에, 각각 1개의 item을 쥐고 있다고 하자.

Producer는 conumser가 사용하도록 buffer를 꽉 채울려고 하고,

Consumer는  producer가 채우도록 buffer를 비울려고 한다.

 

Shared Data Structures

- binary semaphore : mutex

 : buffer에 접근하기 위해 mutual exclusion을 제공해야하므로 1로 초기화된다.

- two counting semaphores empty and full

empty와 full 버퍼를 각각 카운트하기 위해 사용,

empty는 n으로, full은 0으로 초기화된다. (empty는 감소하고, full은 증가한다)

 

[ Figure 7.1 ]

empty buffer가 0이 될 때 까지 대기한다.

그 다음, 대기하고 있는 Producer가 여러 개 일 수 있으므로 mutual exclusion을 위해 mutex를 기다린다.

이렇게 /* add next_produced to the buffer */에 들어오면 유일하게 진입했다는 것이 보장된다.

item을 write해준 뒤, signal(mutex)를 통해 mutex를 반납하고, buffer가 다 찼으니 signal(full)을 통해 Consumer가 받을 수 있게 한다.

 

[ Figure 7.2 ]

signal(full)을 받으면 wait(full)이 깨어나고, 다시 Consumer가 여러 개 일 수 있으므로 wait(mutex)를 통해 1개의 진입만 보장하도록 한다.

item을 remove해준 뒤, signal(mutex)를 반납하고, buffer가 다 찼으니 signal(full)을 통해 Producer가 받을 수 있게 한다.

 

→ wait와 signal의 짝이 대칭으로 맞게 해야 잘 작동한다는 의미가 된다.

이렇게 한다면 Producer와 Consumer가 각각 1:1, 1:N, N:1, N:N이면서 buffer size가 1이거나 N인 복잡한 여러 상황에서 작동하더라도, Insert와 Remove가 간혹 중복되어 실행되는 상황이 있을지라도 적어도 Shared Data의 무결성이 깨지진 않는다는 것이다. 동기화 자체는 잘 된다는 것이다.

 

[ Readers-Writers Problem ]

만약 concurrently하게 동작하는 process들이 shared data에 대해 read만 하거나, read-write 둘 다 하는 경우가 있다면?

 

만약 shared data에 대해 동시에 접근하는 reader가 2개 이상인 경우에는, 별 다른 문제가 생기지 않는다.

반면에, 동시에 접근하는 writer가 2개 이상이거나, reader 또는 writer가 동시에 접근하는 경우, shared data의 무결성이 보장되지 않을 것이다.

 

[ Some Variations of the Readers-Writers Problem ]

모든 variation들에 Priority이 포함되어 있음.

- The first readers-writers problem

기본적으로 reader들은 서로를 기다리지 않아도 된다.

반면에 writer는 기다려야 한다.

→ reader들만 계속 접근하고, writer는 기다리느라 starvation이 발생할 수 있다.

 

- The second readers-writers problem

그럼 writer가 진입하려고 대기 중일 때, 새로운 reader들은 writer 뒤에서 대기하도록 해보자.

→ wrtier가 엄청나게 대기 중이라면, 이제는 reader들의 starvation이 발생할 수 있다.

 

[ Soultion to the first readers-writers problem ]

mutex는 일반적인 mutual exclusion을 위한 것.

read_count는 현재 reader의 개수.

read_count가 0이라면, writer가 진입해도 된다는 것.

 

rw_mutex는 readers와 writers가 공용으로 사용한다.

그리고 read_count를 증가시킬려고할 때, mutex를 통해서 mutual exclusion을 보장하는데 사용한다.

 

read_count는 현재 object를 읽고 있는 process의 개수인 것 !

 

[ Figure 7.3 ]

read_count가 0이 될 때, rw_mutex를 획득하게 되고 re_mutex를 획득하게되면 write를 시작하는 것.

비교적 간단함.

 

[ Figure 7.4 ]

wait(mutex)와 signal(mutex) 사이를 critical section이라 가정하면, 위, 아래 각각 2개가 존재한다.

read_count++ 이후 1이라면 rw_mutex를 회수한다.

반면에 아래에서 read_count-- 이후 0이라면, writer가 진입할 수 있게 signal(rw_mutex)를 한다.

 

 

[ Solution to the Readers-Writers Problem ]

 

위 7.3, 7.4에서 문제는, read_count가 0이 되었을 때, signal(re_mutex)를 받은 writer뿐만 아니라 reader도 접근이 가능하다는 것이다. (waiting readers or a single waiting writer)

이걸 선택하는 것은 scheduler에 의해 결정된다.

reader와 writer에게 공평하게 접근할 수 있게 한다면 first problem의 해법이 되고,  writer에게 우선권을 준다면 second problem의 해법이 된다.

 

[ The Reader-Writer Locks ]

위 문제와 해법은 고전적인 이론이고, 현대에서 일반화된 해법으로는 reader-writer locks이 존재한다.

 

reader-writer lock을 획득할 때, mode 중 read or write를 지정하고, read mode라면 multiple processes가 lock을 획득할 수 있게 하고, write mode라면 1개의 process만 lock을 획득할 수 있게 한다.

 

 

[ The Dining-Philosophers Problem ]

생각하고, 먹는데에 삶을 보내는 5명의 철학자가 있다고 가정해보자.

이들은 5개만 존재하는 젓가락을 공유하고 있다.

때때로, 철학자들은 배고파져서, 가장 가까이있는 2개의 젓가락을 집으려고 시도한다.

 

만약, 배고픈 철학자가 젓가락을 서로 동시에 집으려고 한다면 어떻게 될까?

 

이는 Race Condition이 발생할 때, 젓가락을 순서대로 집게 하기 위해 젓가락을 집는 행위에 대한 mutual exclusion이 필요하다는 뜻이 된다.

 

여태 mutual exclusion을 통해 race condition은 해결해왔으나, 이 예시에선 철학자들이 원형으로 앉아 젓가락을 서로 공유한다는 것인데, 이젠 여러 프로세스들에게 여러 리소스들을 "deadlock과 starvation없이" 할당해야 한다는 것이다. 

 

[ The problem of deadlock and starvation ]

Figure 7.6을 보면, semaphore를 이용한 간단한 solution은 mutual exclusion을 보장해준다.

하지만, 이런 상황은 deadlock과 starvation이 자주 발생하게 된다.

 

5명의 철학자들이 전부 동시에 배고파진다고 가정해보자.

이제 각자 자신의 좌측 젓가락을 집고, 그 다음 오른쪽의 젓가락을 집으려고 시도한다.

→ deadlock이 발생하게 된다.

 

[ Possible remedies to the deadlock problem ]

1) 철학자들을 최대 많아봐야 4명으로 제한한다.

→ 제한할 수 있을 때만 가능

2) 철학자들이 양측 젓가락을 전부 집을 수 있을 때만 집게 한다.

 

3) Asymmetric solution

홀수 번호를 받은 철학자들은 (left→right) 순서대로 젓가락을 집게한다.

반면에, 짝수 번호를 받은 철학자들은 (right→left) 순서대로 젓가락을 집게한다.

 

위 방법들은 dead-free solution은 맞으나, starvation의 가능성을 반드시 없앨 수는 없다.

 

[ Monitor Solution ]

2) 철학자들이 양측 젓가락을 전부 집을 수 있을 때만 집게 한다.

 

철학자들은 3개의 state로 구분시킨다.

thinking, hungry, eating

 

좌우 2명의 철학자의 state가 eating이 아닐 때만 철학자를 eating state로 넘어갈 수 있게 한다.

또한 철학자가 배가 고프지만 필요한 젓가락을 집을 수 없을 때 딜레이 시킬 수 있는 Condition varibale도 필요해진다.

 

[ Solution to the Dining-Philosophers Problem ]monitor인 DiningPhilosopher에 의해 젓가락을 분배하게 해보자.

pickup(), putdown()으로 구분시켜 주고 pickup()을 성공 해야 식사를 시작하고, 실패하면 중단된다.

식사가 끝나면 putdown()을 통해 끝났음을 알린다.

 

그러나 이 방식은 mutual exclusion과 deadlock-free는 보장되나, starvation은 여전히 존재할 수 있다.

 

 

[ Thread-Safe Concurrent Applications ]

멀티코어 시스템에서 mutex lock, semaphore, monitor 등을 사용하는 Concurrent applications은 좋은 성능을 내나, race condition, 그리고 deadlock같은 liveness hazard의 리스크를 지닌다.

 

그래서 thread-safe한 concurrent application의 디자인을 위한 alternative approach가 존재한다.

→ 특정 api의 document를 보면 간혹 "이 함수는 thread-safe 합니다"라는 안내가 있다.

 

1) Transactional Memory

Atomic operation → CAS

2) OpenMP

3) Functional Programming Language