[Operating System] Chapter 6: Synchronization

Background

 

프로세스들은 기본적으로 동시에 실행될 수 있습니다. *이때 동시는 parallelization이 아닌 concurrently를 말합니다. 그러므로 각각의 프로세스들은 inturrupt를 당할 수 있고, 만약 shared data에 대해 여러 개의 프로세스들이 접근하려 한다면, data inconsistency problem이 발생할 수도 있습니다. 따라서 cooperating processes들 간의 실행 순서를 통제하는 것은 data consistency를 유지하는데 매우 중요한 요소입니다.

 

아래는 두 프로세스(Producer and Consumer)가 공유하는 자료구조와 데이터인 buffer와 counter 변수에 접근하여 값을 수정하는 경우에 대한 예시입니다:

(left) the code section of Producer (right) the code section of Consumer

 

이 경우 counter 변수에 대한 race condition이 발생할 수 있습니다:

Race Condition

 

즉 process의 실행 순서에 따라 결과가 달라지는 경우가 발생합니다. *Data inconsistency!

 

Critical Section Problem

 

critical section problem은 race condition과 같은 문제를 해결하기 위해 디자인된 protocol입니다. 예를 들어 n개의 프로세스 {p0, p1, ..., pn-1}이 있을 때 각각의 프로세스들은 critical section이라고 부르는 segment of code (code의 한 부분)을 갖습니다. 이 critical section은 오직 하나의 프로세스만이 들어갈 수 있으며, 나머지 다른 프로세스들은 실행할 수 없는 코드의 한 부분입니다.

 

즉, 각 프로세스들은 critical section에 들어오기 전에 먼저 permission을 asking하고 (entry section), critical section에서 나오는 프로세스들은 OS에게 받은 permission을 반납합니다 (exit section).

 

따라서 critical section은 다음과 같이 구성됩니다:

Critical section

 

process Pi에 대해서 critical section을 구현한다면 다음과 같습니다:

Algorithm for Process Pi

 

위 코드는 process Pi와 process Pj가 서로 공유하는 데이터에 접근하는 경우에 구현된 상황입니다. 또한 ciritical section에 접근할 수 있는 permission의 역할을 수행하는 turn변수를 서로 공유합니다. 우선 Pi는 critical section에 들어가기 전 entry section인 while (turn == j); 를 실행합니다. 이는 만약 실행의 turn이 Pj에게 있다면 busy waiting을 수행하는 것입니다. Pj에서 critical section에 대한 수행이 모두 끝나 turn을 i로 넘긴다면 critical section으로 넘어갈 수 있습니다. critical section을 모두 수행한 후 exit section인 turn = j; 를 실행합니다. permission을 반납하는 것입니다.

 

Solution to Critical-Section Problem

 

Critical-Section Problem을 해결하기 위한 요소는 다음 3가지가 존재합니다:

1. Mutual Exclusion: 만약 Pi가 critical section을 실행중이라면, 다른 나머지 프로세스들은 critical section에 접근할 수 없습니다.
2. Progress: 만약 critical section을 실행중인 프로세스가 없다면, 기다리고 있는 프로세스들 중 하나를 critical section으로 진입시켜야하며, 그 선택은 지연되서는 안됩니다.
3. Bounded Waiting: critical section에 진입을 기다리는 프로세스들이 기다리는 시간이 정해져있어야합니다. 즉, 무한히 기다리면 안됩니다. 다시 말하면, critical section을 실행하고 난 다음 다시 그 프로세스가 entry section으로 들어온 경우 해당 프로세스가 아닌 다른 프로세스가 critical section에 들어올 수 있음을 보장해야합니다.

위 요소들 중 하나라도 만족하지 못한다면 Critical-Section problem을 해결했다 볼 수 없습니다.

 

Critical-Section Handling in OS

 

kernel에서 process들을 preemptive하게 설정하냐, non-preemptive하게 설정하냐에 따라 접근방식이 다를 수 있습니다. (1) 우선 process들끼리 non-preemptive하다면 프로세스끼리 interrupt가 발생하지 않기 때문에 race condition 문제에 대해 자유롭습니다. (2) 반면 preemptive한 경우 race condition을 주의해야합니다.

 

Peterson's Solution

 

이런 문제를 해결하기 위한 좋은 해결책은 Peterson's Solution입니다. 이는 다음과 같은 상황을 가정합니다:

• Two processes
• load 와 store 기계어 명령은 atomic함을 보장합니다. 즉, interrupt당하지 않는 명령어입니다.

이 경우 두 프로세스는 int turn; 과 Boolean flag[2]; 를 공유합니다.

(1) 각각 turn은 critical section에 들어갈 차례가 누구인지를 가르키고, (2) flag array는 critical section에 들어갈 준비가 되어있음을 나타냅니다.

 

이를 고려했을 때 process Pi는 다음과 같습니다:

Algorithm for process Pi

 

entry section에서 flag[i] = true; 로 설정함으로써 critical section의 진입을 기다리고 있음을 나타내고, turn = j; 는 Pj의 상황을 고려함을 나타냅니다. 만약 해당 코드가 없었다면 Pi가 critical section에서 나와서 다시 critical section에 Pj보다 먼저 들어가는 경우를 막을 수 없게 됩니다. *Bounded-Waiting! 만약 flag[j] = true이고 turn = j 라면 Pj를 기다리고, 둘 중 하나라도 false라면 critical section으로 진입합니다.

 

exit section에서는 flag[i] = false; 를 통해 Pi가 기다리고 있지 않음을, 또는 기다리고 있는 Pj에게 critical section으로 들어가라고 신호를 보냅니다. *Progress!

 

Synchronization Hardware

 

대부분의 system들은 hardware상에서 critical section code를 지원합니다. 가장 기본적인 해결 방법은 locking입니다. lock을 통해 critical section의 진입을 통제하는 것입니다.

 

만약 Uniprocessor의 경우 interrupt를 막는 것이 가능할 수 있습니다. 이는 프로세스간의 interrupt, preemptive가 발생하지 않고 실행할 수 있기 때문입니다. 하지만 일반적인 multiprocessor system에서는 적절하지 않습니다. *효율성! 

 

따라서 현대의 machine들은 atomic hardware instruction들을 제공합니다. Atomic하다는 것은 non-interruptible함을 말합니다. lock을 설정하는 것이나 lock을 해제하는 것 모두 atomic instruction입니다.

 

아래는 Lock을 이용해서 critical-section problem을 해결한 코드입니다:

Solution to Critical-section Problem Using Locks

 

test_and_set Instruction

 

test_and_set Instruction

 

우선 test_and_set 명령어는 atomicity를 보장하는 명령어입니다. *즉 이를 실행하는 동안은 interrupt 당하지 않는다는 뜻입니다. 또한 파라미터 입력으로 들어온 값을 그대로 return하면서 target의 값을 TRUE로 바꿉니다. 이는 lock에서 사용할 수 있습니다. 만약 lock이 FALSE인 경우 return FALSE와 함께 lock은 TRUE로 바뀔 것입니다. 그리고 이는 critical-section에 process가 진입했음을 나타냅니다. 만약 lock이 TRUE인 경우에는 return TRUE와 함께 lock의 값은 변하지 않습니다. 그리고 이는 critical-section에 process가 여전히 접근할 수 없음을 알려줍니다.

 

즉, return값을 통해 critical section이 진입할 수 있는지 없는지를 확인할 수 있고(test), 들어갈 수 있는 경우 target의 값을 FALSE로 바꿔줌으로써(set) critical section에 더 이상 프로세스들이 접근하는 것을 막을 수 있습니다.

 

test_and_set()을 활용하면 다음과 같은 solution을 구현할 수 있습니다:

Solution using test_and_set() with shared Boolean variable lock, initialized to FALSE

 

compare_and_swap Instruction

 

test_and_set()과 마찬가지로 atomicity를 보장하는 instruction입니다. 이는 value 라는 이름으로 넘어온 값을 그대로 return합니다. 그리고 만약 해당 value 가 expected 와 값이 같다면(compare), value 의 값을 new_value 로 변경합니다(swap).

 

compare_and_swap()을 활용하면 다음과 같은 solution을 구현할 수 있습니다:

Solution using compare_and_swap with shared integer "lock" initialized to 0

 

하지만 test_and_set() 이나 compare_and_swap()을 통해 구현한 solution들은 bounded-waiting을 해결하지 않습니다. 즉 기다리고 있는 process들 중 critical section에 들어갈 프로세스들을 선택하는 과정에서 계속 기다리고 있었던 process들을 명시적으로 선택하는 기능이 없습니다. 따라서 이를 고려했을 때 다음과 같은 solution이 나올 수 있습니다:

Bounded-waiting Mutual Exclusion with test_and_set()

 

entry section에서 waiting[i] = true; 는 현재 process인 Pi가 critical section으로의 진입을 기다리고 있다는 것을 나타냅니다. 그리고 key = true;로 해놓습니다. 이때 key는 lock을 의미합니다. 만약 key가 false라면 critical section에 들어갈 수 있음을 나타냅니다. key = true;로 해놓음으로써 일단 무조건 test_and_set()을 한 번은 실행하도록 하는 것입니다. *예외가 있을 수는 있음 나중에 설명... test_and_set()을 통해 lock이 false, 즉 critical section에 들어갈 수 있음을 premission받으면 waiting[i] = false; 로 함으로써 기다리고 있지 않음을 나타내고 critical section으로 진입합니다.

 

exit section에서 우선 j를 초기화합니다. 이는 Pi말고 다른 process들을 탐색하기 위한 process index입니다. while ((j != i) && !waiting[j]) j = (j + 1) % n; 을 통해 모든 프로세스들을 한 번씩 탐색합니다. 그러는 동안 탐색중인 process Pj의 waiting[j] = true; 라면, 즉 Pj가 entry section에서 lock을 기다리고 있다면 while문을 탈출합니다. 이렇게 탈출하는 경우 j != i 이므로 waiting[j] = false;로 바꿔줌으로써 Pj를 바로 critical section으로 진입하게 합니다. 만약 j를 탐색중에 모두 탐색해도 waiting[j] = true; 인 경우가 없이 j = i 일때까지 왔다면 그냥 while문을 탈출하고, 그냥 lock = false;로 바꿔줍니다. *참고로 entry section에서 test_and_set()을 실행하지 않고 critical section으로 들어오는 경우는 while문에 들어올 때 다른 process에 의해 waiting이 false가 되는 경우입니다.

 

Mutex Locks

 

지금까지 살펴봤던 해결책들은 구현하기 복잡하다는 단점이 있습니다. 그래서 일반적으로는 Mutex Lock을 통해 구현합니다. 이는 critical section을 acquire() 와 release() 를 통해 통제합니다. 그리고 acquire() 와 release() 는 반드시 atomic 해야합니다. 하지만 이 해결책은 busy waiting 이 필요하고 그래서 이를 spinlock이라고도 부릅니다.

 

mutex lock을 통해 구현하면 다음과 같습니다:

acquire() and release()

 

*당연히 acquire()와 release()는 atomic instruction이어야합니다.

 

Semaphore

 

Semaphore는 mutex lock보다는 좀 더 정교한 방법을 제공하는 도구입니다. semaphore S는 그냥 integer value로 wait() 과 signal() 함수가 존재합니다. 구현은 다음과 같습니다:

Semaphore

 

Semaphore는 크게 두 종류로 구분할 수 있습니다. (1) Counting semaphore에서의 integer value S는 제한되지 않는 범위의 integer입니다. (2) Binary semaphore에서의 integer value S는 0과 1 값만을 가집니다. 그리고 이는 mutex lock과 똑같이 기능합니다.

 

만약 synch 값이 0으로 초기화된 경우 S1과 S2의 실행 순서를 semaphore synch를 통해 통제할 수 있습니다:

Semaphore Usage

 

Semaphore Implementation

 

semaphore를 구현할 때는 wait() 과 signal() 이 다른 프로세스들과 동시에 실행되지 않음을 보장해야합니다. 즉 이들도 atomic instruction임을 보장받아야합니다. semaphore를 구현할 때 busy waiting을 사용할 수도 있습니다. 하지만 이는 구현하는 코드가 짧을 때 아니면 critical section의 출현 빈도가 작을 때 사용하는 것이 좋습니다. *busy waiting이 그냥 기다리는게 아니라 CPU 자원을 갖고 계속 기다리는 것이기 때문에 busy waiting이 잦으면 효율성의 문제가 있을 수 있습니다. 

 

Semaphore Implementation with no Busy waiting

 

각각의 semaphore는 (1) value (of type integer)와 (2) pointer to next record in the list를 갖습니다. (2)는 semaphore에 의해 wait() 중인 프로세스들을 관리하는 linked list입니다. 이때 semaphore는 block과 wakeup 기능을 수행할 수 있습니다. block()은 해당 프로세스를 waiting queue로 보내는 기능을 수행합니다. wakeup()은 waiting queue에 있는 프로세스를 ready queue로 옮겨 실행가능한 상태로 만들어주는 기능을 수행합니다.

 

아래는 semaphore 구조체와 wait(), signal()의 구현입니다:

Semaphore implementation with no Busy waiting

 

Deadlock and Starvation

 

Deadlock은 두 개 이상의 프로세스들이 waiting process에 의해 생긴 event로 인해 계속 기다리고 있는 상황을 말합니다. 또한 semaphore의 linked list에서 대기중인 process가 signal이 호출되지 않아 계속 기다리는 상황인 Starvation문제가 발생할 수 있습니다. 

 

또한 Scheduling과 연관되어서, lock을 가지고 있어서 다른 프로세스들의 execution을 막는 프로세스가 scheduling상 낮은 priority를 갖는 경우 CPU 자원이 해당 프로세스에게 안 와서 더 이상 진행이 안돼 lock이 풀리지 않는 경우가 발생할 수 있습니다. 그리고 이를 Priority Inversion이라고 부릅니다. 이는 priority-inheritance protocol을 통해서 해결할 수 있습니다. 이는 lock을 가지고 있는 프로세스의 우선순위를 높여 이런 문제를 방지하는 프로토콜을 말합니다.

 

Classical Problems of Synchronization

 

고전적인 동기화 문제들은 다음과 같습니다:

• Bounded-Buffer Problem
• Readers and Writets Problem
• Dining-Philosophers Problem

 

Bounded-Buffer Problem

 

상황은 다음과 같습니다:

(1) n개의 buffer가 있으며 각각의 buffer는 하나의 item을 갖습니다.

(2) Semaphoer mutex 는 1로 초기화 되어있습니다; mutual exclusion용으로 사용하는 semaphore

(3) Semaphoer full 은 0으로 초기화 되어있습니다; buffer가 가득찼을때 Producer가 데이터를 buffer에 못 넣게 하는 용으로 사용하는 semaphore, 0으로 초기화하는 것은 처음 시작할때 buffer에 데이터가 0개로 시작한다는 의미입니다.

(4) Semaphoer empty 는 n으로 초기화 되어있습니다; buffer가 비었을때 Consumer가 데이터를 buffer에서 못 읽게 하는 용으로 사용하는 semaphore, n으로 초기화하는 것은 처음 시작할때 buffer에 데이터가 n만큼 비어있다는 의미입니다.

 

(left) the structure of the producer process, (right) the structure of the consumer process

 

Readers-Writers Problem

 

상황은 다음과 같습니다:

(1) 여러 개의 process들이 공유하는 데이터 셋에 접근하려는 상황입니다.

(2) Reader는 오직 데이터 셋을 읽기만 가능하며, 업데이트하는 것은 가정하지 않습니다. Writer는 읽고 쓸 수 있습니다.

(3) 이때, 오직 하나의 프로세스만 데이터 셋에 접근을 허용하는 것이 아닌, 읽을 때는 여러 프로세스들이 접근할 수 있게 하려고 합니다. 

(4) Semaphore rw_mutex는 1로 초기화 되어있습니다; 이는 Data와 관련된 Writer와 Reader 모두에게 적용되는 mutex입니다. Semaphore mutex는 1로 초기화 되어있습니다; 이는 Reader들과 관련된 mutex입니다. Integer read_count는 0으로 초기화 되어있습니다; 이는 현재 데이터 셋을 읽고있는 reader들의 수를 나타냅니다.

 

*이 해결책은 Writer와 Reader사이의 우선순위와 관련하여 많은 variations들이 존재하며, 해당 교재에서는 Reader에게 우선순위를 주는 버전입니다.

 

 

(left) the structure of a writer process, (right) the structure of a reader process

 

Reader-Writers Problem Variations

 

• First variation - reader는 기다리지 않습니다. *교재에 나온 버전
• Second variation - 한 번 writer가 준비되면, 최대한 빨리 write operation을 실행합니다.

이 두 variation모두 starvation문제를 갖고 있습니다. *First의 경우 Writer의 starvation, Second의 경우 Reader의 starvation. 또한 kernel level Reader-Writer lock을 통해 이 문제를 해결할 수도 있습니다. 자세히 어떻게인지는 잘...

 

Dining-Philosophers Problem

 

Dining-Philosophers Problem

 

상황은 다음과 같습니다:

(1) 철학자는 생각하거나(Thinking), 먹으며(eating) 살아갑니다.

(2) 밥을 먹을 때는 양쪽에 존재하는 젓가락을 하나씩 사용하여 밥을 먹을 수 있습니다.

(3) 만약 다른 철학자가 젓가락을 사용중이라면 주변의 철학자들은 밥을 먹을 수 없습니다.

(4) 공유되는 데이터인 rice가 있고, Semaphore에 해당하는 chopstick[5] 가 각각 1로 초기화 됩니다.

 

The structure of Philosopher i

 

하지만 이렇게 구성하면 문제가 발생할 수 있습니다. 만약 프로세스의 순서가 모든 P가 동시에 왼쪽 chopstick을 wait()하면, 모든 P들은 오른족 chopstick의 signal을 계속 무한히 기다려야합니다(Deadlock).

 

이를 해결하기 위해서는 다음과 같은 방법들이 존재합니다:

• P의 수를 줄이거나 C의 수를 늘립니다; Allow at most 4 philosophers to be sitting simultameously at the table
• P들은 오직 양쪽의 C가 모두 사용가능할 때만, C를 wait합니다.
• 비대칭 해결책; 짝수번째 P들은 왼쪽 C를 먼저, 홀수번째 P들은 오른쪽 C를 먼저 wait합니다.

 

이 외에도 semaphore를 사용하면서 다양한 문제(Deadlock or Starvation)가 있을 수 있습니다:

• signal -> wait: signal후에 wait을 하는 경우 wait이 걸리지 않을 수 있습니다.
• wait -> wait: signal이 없다면 계속 wait할 수 있습니다.
• wait이나 signal을 아에 빼먹는 경우 문제가 발생합니다.

 

Monitor

 

Monitor는 high-level abstraction으로 동기화 문제를 효율적이고 편하게 제공하기 위해 만들어졌습니다. Monitor는 일종의 code영역으로 monitor에서는 오직 하나의 process만 실행가능합니다. 즉, monitor자체적으로 mutual exclusion을 지킵니다.

Monitor with Condition variables

 

Monitor에는 condition variable이 존재하며, 이는 monitor내에서 추가적인 기능을 제공합니다. 각각의 condition variable들은 wait()과 signal() operation을 갖습니다. 이는 semaphore의 wait()과 signal() operation과 유사하며, 차이점은 semaphore의 경우 integer의 값을 -1하거나 +1하는 기능이 존재하지만, condition variable의 wait()과 signal()은 integer를 조작하지 않고 바로 해당 process를 suspending(condition variable에 존재하는 queue에 넣음으로써) 하거나, resuming합니다. *참고로 만약 queue에 아무 프로세스도 없는 상황에서 signal을 호출하면 아무런 효과가 없습니다.

 

Condition Variable Choices

 

condition variable x가 존재하고 x의 queue에는 process P1이 있다고 가정합니다. 이때 monitor에는 process P2가 들어왔고, x.signal()을 호출합니다. 이때 monitor는 어떤 process를 실행시키고 어떤 process를 susupending시켜야할까요? *monitor의 mutual exclusion 정책에 의해 P1과 P2모두 동시에 실행시킬 수는 없습니다. 이에 두 가지 옵션이 존재합니다:

• Signal and wait - P2는 signal된 process인 P1이 monitor를 나가거나 다른 condition에 의해 wait이 될때까지 기다립니다.
• Signal and continue - P1은 signal을 호출한 process인 P2가 monitor를 나가거나 다른 condition에 의해 wait이 될때까지 기다립니다.

각각의 옵션들 모두 장단점이 존재하며, 언어들마다 구현이 다를 수 있습니다.

 

Solution to Dining Philosophers

 

Monitor를 이용해서 Dining Philosophers Problem을 해결하면 다음과 같습니다:

Monitor

 

해당 해결방법은 deadlock은 없지만 starvation은 여전히 존재할 수 있습니다.

 

Monitor Implementation Using Semaphores

 

Monitor를 구현할 때 사용할 semaphore들과 initial variable은 다음과 같습니다:

• semaphore mutex; // initially = 1
• semaphore next; // initially = 0
• int next_count = 0 // monitor안에서 wait중인 proc.의 개수

Monitor Implementation Using Semaphore

 

*만약 next_count가 0보다 커서 monitor내에 기다리고 있는 proc.이 있다면 monitor에 대한 signal이 아닌 monitor안에 있는 proc.에 대해 signal을 호출합니다.

 

Monitor Implementation - Condition Variables

 

condition variable을 구현하는데 사용한 semaphore는 다음과 같습니다:

• semaphore x_sem; // initially = 0
• int x_count = 0; // condition variable x가 가지고 있는 proc.의 개수

(left) x.wait(), (right) x.signal()

 

Resuming Processes within a Monitor

 

여러 개의 process들이 condition x에 의해 wait중이며, signal이 호출되었을때 어떤 proc.이 resume되야하는지에 대해 결정해야합니다. 이때 FCFS는 좋은 방법이 아닐 수 있습니다. 그래서 conditional-wait을 사용합니다. 이는 x.wait()의 파라미터로 c를 넣어줍니다. c는 priority number를 의미하며, c가 작으면 높은 우선순위로 resuming됨을 보장합니다.

A monitor to allocate single resource