[Operating System] Process Synchronization (프로세스 동기화)

Race condition

  공유된 데이터에 대한 경쟁적인 접근은 데이터의 불일치를 초래할 수 있다. 여러 개의 프로세스들이 동일한 데이터에 접근해서 데이터를 변경하려는 상황을 Race condition이라고 한다. Race condition으로 인해 최종적으로 데이터의 값은 잘못된 값이 될 가능성이 있다. 이러한 Race condition을 방지하기 위해 경쟁하는 프로세스들은 동기화 되어야 한다.

  이러한 상황에는 P1이 연산을 먼저 수행하고, P2가 그 다음 연산을 수행한다면 X가 처음과 동일하게 2로 유지될 것이라고 생각할 수 있지만, instruction이 interleaving된다면 P1의 연산 도중 P2가 연산을 동시에 수행하여 결과를 P1보다 늦게 X에 저장한다면 X의 최종 값은 1이 될 것이다. 이는 일반적으로 기대한 결과가 아닐 것이다.

  이 때, X=X+1이나 X=X-1과 같이 X의 값에 직접적으로 영향을 끼치는 코드의 부분을 Crirical-Section이라고 한다.

 

Requirements for the Solution

프로세스가 동기화 되려면 다음과 같은 요구사항을 충족시켜야한다.

Mutual Exclusion : CS는 동시에 한 프로세스만 수행해야한다. 한 프로세스가 CS를 수행하고 있다면, 그 프로세스를 제외한 나머지 프로세스들은 CS를 수행해서는 안된다.

Progress : CS는 계속해서 수행되어야 한다. CS를 수행하고 있는 프로세스가 없다면, CS를 수행하고자 하는 프로세스가 존재해야 하며, 어떤 프로세스가 CS를 수행할 지에대한 선택은 지연되어서는 안된다.

Bounded Waiting : 무한히 CS 수행을 대기하는 프로세스는 없어야한다.

 

Peterson's Algorithm

  소프트웨어적으로 프로세스를 동기화할 수 있는 알고리즘이다.

flag[i] = true // CS를 수행하고자 하는 의사를 나타낸다.

turn = j // j 프로세스에게 순서를 양보한다.

while(flag[j] && turn == j) // 순서를 양보받은 프로세스가 CS를 수행하고자하는 의사가 있어 CS를 수행중이라면 Busy Waiting한다.

flag[i] = false // CS 수행을 끝냈음을 나타낸다.

 

하지만 이 알고리즘은 Busy Waiting하며 CPU를 쉬지않고 사용하기 때문에 비효율적일 수 있다.

 

 

Synchronization Hardware

  싱글 사이클에 기능을 다 끝마치는 것을 보장해주는 하드웨어를 Atomic Hardware라고 한다. Atomic Hardware의 도움을 받는 함수들은 싱클 사이클에 수행이 된다. 이를 활용한 동기화는 대표적으로 Test-And-Set과 Swap을 이용한 동기화가 있다.

 

- Test-And-Set

이 함수는 매개변수로 받은 target를 true로 바꾸지만, target의 원본값을 반환한다.

lock이 true일 때는 어떤 프로세스가 CS를 수행하고 있을 때이다. 이 때 TAS의 반환값은 항상 true이다.

CS수행을 마친 프로세스가 lock을 false로 바꾸면 while을 돌고 있던 프로세스중 하나가 lock을 true로 바꾸고 false를 반환하는 TAS를 실행할 것이다. 그 프로세스가 CS를 수행한다. 

 

- Swap

이 함수는 a와 b가 가진 값을 바꾸는 Atomic function이다.

key : 열쇠 (true : 열쇠 사용 가능, false : 열쇠 사용 불가)

CS : 방

lock : 자물쇠 (true : 열림, false : 잠김)

swap : 열쇠로 자물쇠를 따려는 시도

라고 생각하자.

key가 true이고 lock이 false일 때, swap하면 key가 false, lock이 true가 된다. 이 때 프로세스는 CS를 수행하고, lock을 false로, 즉 방문을 잠그고 나온다. 그러면 그 다음 프로세스가 마찬가지로 swap으로 방문을 열고 들어가 CS를 수행한다.

 

Semaphore (Busy Waiting)

세마포어는 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법이다. 세마포어에는 P연산과 V연산이 있다.

P 연산 : CS에 진입하기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V 연산 :  CS에서 나올 때 수행 (자원 반납 알림, 대기중인 프로세스를 깨우는 신호)

S가 0일 때 프로세스들은 Busy Waiting에 묶여있고, CS에서 나오는 프로세스가 S를 1로 만들 때는 한 프로세스가 S를 0으로 만들고 CS에 진입한다. 이와 같은 세마포어 S 를 binary semaphore라고 한다.

 

 

Semaphore (Block / Wakeup)

CPU를 사용하는 Busy waiting 방식의 Semaphore를 개선하기 위해 Block/Wakeup 방식의 Semaphore를 사용할 수 있다.

이 때 Semaphore는 세마포어의 값과, CS 진입을 대기하는 프로세스의 큐로 구성된 구조체로 표현될 수 있다.

Block/Wakeup을 이용한 P와 V는 다음과 같다.

  block은 커널이 프로세스를 일시중지 시키는 것이고, Wakeup은 block된 프로세스를 깨우는 것이다.

  CS에 진입하고자 하는 프로세스는 P 호출하여 세마포어 값을 감소시키고, 그 때의 세마포어 값이 음수가 된다면 프로세스 큐에 들어가 block된다.

  CS에서 나온 프로세스는 V를 호출하여 세마포어 값을 증가시키고, 그 때의 세마포어 값이 0보다 작거나 같다면 큐에서 프로세스를 하나 꺼내서 깨운다.

  세마포어의 값의 절댓값은 대기중인 프로세스들이 들어있는 큐의 길이라고 생각할 수 있다. 이 때 이러한 세마포어를 integer semaphore라고 한다. 

 

Bounded-Buffer Problem

  Producer가 데이터를 Buffer에 쓰면 Consumer가 읽는다. 

- # of full buf > 0 라면 consumer가 읽는다.

- # of empty buf > 0 라면 Producer가 쓴다.

자원의 수를 세는 이 변수들도 Producer와 Consumer 사이에서 공유될 변수이므로 Integer semaphore가 필요하고. buf에 쓰거나 읽는 것도 CS이기 때문에 binary semaphore로 보호해야한다.

 

Readers-Writers Problem

  DB에 다수의 유저가 접근할 수 있다. 다만 reader와 writer가 동시에 데이터에 접근하면 안된다. 모든 reader들이 데이터 접근을 끝냈을 때 writer가 데이터에 접근할 수 있도록 하자.

  만약 한 reader가 reading을 하고 있다면, 다른 reader들도 reading을 시작할 수 있다. 마지막 reader가 reading을 끝냈을 때 writer가 writing을 시작할 수 있도록 한다.

readcount는 reader들 간에 공유되는 변수이므로 mutex로 보호하고, readcount를 1로 만드는 reader는 P(db)를 호출하고, readcount를 0으로 만드는 reader는 V(db)를 호출한다.

 

Dining-Philosophers Problem

  철학자가 젓가락 두개를 집어야 음식을 먹을 수 있는(CS에 진입) 문제이다. 철학자와 인접한 젓가락은 인접한 철학자와 공유하는 공유변수이다.

  하지만 모든 철학자가 같은 방향의 젓가락을 집는다면, 모든 철학자는 반대쪽 젓가락을 집기 위해 무기한 대기, 즉 deadlock에 걸릴 것이다. 이를 해결하기 위해 다음과 같은 방법들이 사용될 수 있다.

 

1. 양쪽 젓가락 동시에 들기

2. 홀수 번째 철학자 -> 왼쪽 젓가락 우선 들기, 짝수 번째 철학자 -> 오른쪽 젓가락 우선 들기

3. 철학자 한 자리 비우기

4. 모니터

 

- 모니터

  모니터란 모니터 내부 프로시저를 통해서만 공유 변수에 접근할 수 있게 하는 메커니즘이다.

 

  모니터에서는 한 프로세스만 active하다. 모니터의 프로시저를 호출하는 프로세스는 단 하나로 유일하다. 프로시저 호출을 대기하는 프로세스들인 엔트리 큐에서 대기한다.

 

  프로세스가 모니터 내부에서 대기하게 하기 위해서는 condition 변수가 선언되어야 한다.

  condition x와 연관된 프로세스들은 x.wait()가 호출되면 큐에 추가되고, x.signal()을 호출하면 x와 관련된 큐에 있는 프로세스 하나가 실행을 재개한다. 이 때, x.signal()을 호출한 프로세스는 대기상태에 들어가게 된다.

 

  Dining-Philosopher Problem에 모니터를 적용한 의사코드이다.

  여기서 test는 이중적인 역할을 한다.

- pickup에서 호출되는 test

  양쪽 젓가락이 모두 사용 가능하다면 state[i]를 eating으로 바꾼다.

- putdown에서 호출되는 test

  putdown을 호출한 철학자가 젓가락을 내려 놓았을 때, 왼/오른쪽 철학자가 양쪽 젓가락을 모두 사용 가능하다면 state[(i+4)%5] 또는 state[(i+1)%5]를 eating으로 바꾸고 self[(i+4)%5].signal() 또는 self[(i+1)%5].signal()을 호출하여 실행을 재개하도록 한다.