동기화라는 것은 뭘까? 동기화란 사전적인 의미로는 "시스템을 동시에 작동시키기 위해 여러 사건들을 조화시키는 것" 이라는 의미이다. 이를 Computer Science 분야로 가져오면, 여러 process들이 사용하는 data를 일치시키는 것을 의미한다고 볼 수 있다. Process들의 경우 이전에 Thread에 대해 다루면서 언급을 했었지만, 각각의 thread는 전역변수와 같이 process들끼리 공유하고 있는 변수들을 함께 사용하고 있다. 그런데 만약 thread1이 $x$라는 공유변수를 1만큼 증가시키는 code를 갖고 있고, thread2가 동일한 공유변수 $x$를 1만큼 감소시키는 code를 갖고 있는데 동기화 과정을 거치지 않고 두 thread가 동시에 공유변수에 접근을 하도록 하면 어떤 결과가 일어날까? 지금부터 이 과정에 대해 알아보고자 한다.

Background

위에서도 설명했지만, shared data에 대한 concurrent access가 동기화에서 발생하는 문제의 원인이고 이를 race condition이라고 한다.

위 그림에서 process1이 x=x+1이라는 code, process2가 x=x-1이라는 code를 갖고 있다고 했을 때, x=2라는 공유 변수를 두 process가 동시에 접근하게 된다면 의도한 정답은 2에서 1만큼 증가시켰다가 다시 1만큼 감소시켰기 때문에 2일 것이다. 그러나, Load, Inc, Store instruction이 interleaved 되어 있다면 결과는 마지막 Process2의 store instruction 호출에 의해 1이 된다. (각각 2를 Load해서 연산을 진행하기 때문)
이렇게 공유 data에 대한 동시 접근을 허용하게 되면 여러가지 정답이 모두 허용되기 때문에 consistency가 깨지게 된다.

Critical-Section Problem

위의 예시에서 process1에 대응하는 x=x+1과 process2에 대응하는 x=x-1을 code라고도 부르지만 shared data가 접근하는 구역이기 때문에 Critical-Section이라고도 부른다. 동기화 문제를 해결하기 위해서는 한 번에 하나의 process만 critical section을 execute 하도록 해야 한다.

1. Mutual Exclusion

: Mutual Exclusion이란, 상호배제 즉 동시 실행을 막는 것이다. 이미 Process가 critical section을 실행중인 경우 다른 process가 critical section에 진입하게 되면 문제가 발생하기 때문에 이를 원천적으로 차단하는 방법이다.

2. Progress

: Mutual Exclusion 방법이 critical section에 동시접근하는 것을 막아주긴 하지만, 너무 과도하게 process들을 막게 되면 critical section이 비어있음에도 불구하고 process가 들어가지 않아 CPU utilization과 throughput이 떨어질 수 있다. 따라서 너무 과도하게 막아서 critical section이 비어있는 상태로 내버려 두지 않고 process가 진입을 할 수 있도록 하는 것이 progress이다.

3. Bounded Waiting

: Bounded waiting의 경우 CPU scheduling에서 priority scheduling에 대해 다룰 때, priority가 낮은 process가 계속 기다리기만 해서 발생하는 starvation 문제와 유사하다. Critical section에 동시접근을 막고자 process를 막게 되면 다른 process들은 하나의 process가 critical section에 들어가 실행을 하고 빠져나와서 다음 process가 들어가는 과정을 계속 기다리면서 자신의 차례가 될 때까지 기다려야 한다. 이를 방지하고자 기다리는 시간에도 bound를 걸어서 일정 시간 이상으로 기다리지 않도록 하는 것이 Bounded waiting이다.

Algorithm

1. Mutual Exclusion

Mutual Exclusion algorithm을 살펴보면 0으로 초기화 되어 있는 turn이라는 변수가 주어져 있고, turn 값에 따라 critical section에 진입하는 여부를 결정해준다. 위의 예시에서는 P0와 P1 2개의 process만 존재한다고 가정했기 때문에 turn=0이면 p0가 들어가서 실행한 뒤 나오면서 turn을 1로 바꿔서 P1이 들어갈 수 있도록 해주기 때문에 Mutual Exclusion을 보장해준다..
그러나 이 경우, 만약 P1이 critical section에 들어가고자 하는 의지가 없는데 P0가 critical section을 들어갔다가 나오면서 turn=1로 바꿔줘서 P1이 들어가게 된다면 들어가더라도 실행을 하지 않게 되기 때문에 turn 값이 바뀌지 않아서 while(turn!=0)에서 무한루프를 돌게 되고 결국 progress 조건을 만족시키지 못하게 된다.

2. Progress

2번째 알고리즘의 경우 첫 번째 알고리즘에서 생기는 문제를 해결하기 위해 turn 대신에 flag[]를 사용한 점이 첫 번째 알고리즘과의 차이점이다. flag[i]=1 (자신의 flag=1)인 경우 critical section에 들어가고자 하는 의지가 있는 process이기 때문에 들어가도 된다. 그 전에 while문에서 flag[j]를 검사해서 이미 critical section에 process가 존재하는지를 확인하고 없다면 진입을 하고 있다면 while문에서 대기를 한다. 그 뒤 실행한 process가 빠져나오면서 자기 자신의 flag를 false로 바꾸는 과정으로 진행된다.
그러나 이 알고리즘 역시 문제점이 존재한다. 만약, 여러 process들의 flag 값이 true인 경우 이미 critical section에 들어있던 process가 빠져 나온 뒤 다음으로 들어갈 process를 결정할 때 문제가 생긴다. 그러므로 이 문제를 해결하기 위해서는 flag=true인 process들 중 어떤 process가 더 먼저 들어가야 하는지 교통정리를 해주는 변수가 필요할 것이다.

3. Peterson's Algorithm

첫 번째 알고리즘에서의 turn의 경우 실행 의지가 없는 process에게 turn이 주어져서 문제였고 두번째 알고리즘에서의 flag의 경우 실행 의지가 있는 process들 중 누가 critical section에 들어가야 하는지를 정하지 못하기 때문에 문제가 발생한다. 두 알고리즘의 문제점의 경우 상호보완적으로 해결이 가능하다. 따라서 이 두 알고리즘의 특성을 합친 알고리즘이 Peterson's Algorithm이다.

간단히 설명을 하면 들어갈 의지가 있고 (flag[i]==true), 자신의 차례 (turn=i)가 되었을 때 critical section에 진입을 하는 알고리즘이다. 이 알고리즘의 경우 1번과 2번의 장점을 합친 알고리즘이기 때문에 완벽한 것 처럼 보인다. 하지만, 이 역시 문제점이 존재한다. 가장 먼저 critical section 이전 부분인 entry section이 너무 길다는 점이다. Entry section이 너무 길 때의 문제점은 각각의 process마다 coding을 해주어야 하기 때문에 번거롭다는 점이다. 두 번째로는 process가 critical section에 진입하기 위한 권한을 얻기 위해 busy waiting을 하게 된다는 점이다. Busy waiting을 하게 되면 쓸 데 없이 CPU 자원을 낭비하면서 대기를 하게 되기 때문에 효율 및 성능이 떨어지게 된다.

이를 해결하기 위한 방법이 critical section을 자물쇠로 잠궈버리는 방법이다.

Lock

말 그대로 lock을 걸어서 이 lock을 해제할 수 있는 key를 갖고 있는 process만 진입을 허용하는 방법이다. 그러나 이마저도 한번에 1개의 process만이 lock을 해제할 key를 갖고 있다는 것을 보장할 방법을 필요로 한다.
이를 Atomic 하다 라고 하며, Atomic의 의미는 non-interruptable로 한 번에 하나만 실행한다는 의미로 이어진다.

Semaphore

Semaphore 역시 여러 process가 동시에 접근하는 것을 막기 위해 고안된 방법으로 atomic해야 하며, P(S)와 V(S)로 접근을 차단한다. P,V 내부를 보면 Semaphore 변수 S의 값에 따라 달라지는데, P는 S가 0보다 작거나 같을 때 즉 P에는 여러 process들이 들어갈 수 있기 때문에 process의 개수 만큼 S 값이 작아지게 되고 1으로 초기화 되어 있던 값이 0 이하가 된다면 이 때는 critical section에 process가 존재한다고 생각하고 while loop를 돌게 되다가 process가 빠져나오면서 V를 거쳐서 S를 1만큼 늘려주었을 때 0보다 커지게 되었을 때 진입을 한다.

Semamphore 변수를 사용할 때 중요한 점은 같은 semaphore 변수를 사용하고 있는 2개 이상의 process가 동시에 wait(), signal()에 접근하면 안된다는 점이다. 이 또한 synchronization 문제가 되기 때문에 peterson algorithm을 사용하여 P(), V()에 대한 접근을 동기화할 수 있다.

Block / WakeUp

P()에는 여러 process들이 한 번에 하나의 process만 진입하여 Semaphore 값을 감소시키기 때문에 S의 값이 0보다 커질 때까지 P에 진입했던 process들은 busy waiting을 해야 한다. 이는 CPU 효율을 떨어뜨리기 때문에 busy waiting을 방지하기 위한 방법으로 block / wakeup 방식이 제안되었다. 이 방법은 말 그대로 대기를 하면서 의미없이 CPU를 사용하지 않도록 process를 재웠다가 순서가 되었을 때 깨우는 방식이다.

code를 보면 기존의 P, V와 거의 유사하지만 구조체를 사용하였기 때문에 구조체 형식으로 사용한 점과 Linkedlist로 대기 중인 process를 연결해서 block을 호출해 L에 있는 process들을 재웠다가 V에서 하나씩 dequeue하면서 깨우는 과정으로 진행된다.

Test-And-Set

TestAndSet의 경우 약간 특이한 점이 있다. Entry section에 쓰일 때 while문의 조건으로 lock을 인자로 받는데 boolean type 함수를 보면 왜 특이하다고 하는지 이해가 될 것이다.

boolean TestAndSet(boolean &target){
	boolean rv = target;
    target = true;
    return rv;
}

target을 lock으로 보면, 인자로 받은 뒤 boolean 변수 rv에 복사를 한 뒤, 원래의 값을 true로 바꾸는데 return하는 값은 true로 바꾼 값이 아닌 원래의 target 값을 return한다.
해석을 하면 다음과 같다.

• lock = False : TestAndSet(lock) -> lock = True, rv = False
• lock = True : TestAndSet(lock) -> lock = True, rv = True

첫번째 case는 rv가 false이기 때문에 while을 탈출해서 Critical section으로 진입할 수 있다. 그러나 두 번째 case는 rv가 True이기 때문에 진입을 하지 못한다. Critical section을 빠져 나오면서 lock=false로 바꾸게 되면 다시 while문을 진입했을 때 rv=false, lock=true가 되어 그 다음 process가 진입할 수 있게 된다. 그러나 여러 process가 대기 중인 경우 rv와 lock 둘 다 true이기 때문에 대기를 하게 된다.

Swap

이 과정을 Swap 함수로도 할 수 있다.

void Swap(boolean &a, boolean &b){
	boolean temp = a;
    a = b;
    b = temp;
}

code의 과정을 보면 key=true로 설정한 뒤, while문을 거쳐서 key==true인 경우 lock과 key의 값을 swap하라고 되어 있다.

• Key = True
  • lock = False <-> Key = False, lock = True
  • lock = True <-> Key = True, lock = True

첫 번째 경우는 key=False이기 때문에 while문을 탈출해서 Critical section에 진입할 수 있다. 그러나 두 번째 경우는 여전히 while문을 탈출하지 못하게 된다. 그러므로 먼저 들어간 process가 critical section을 빠져나와 lock=False로 바꿔야만 다음 process가 critical section을 진입할 수 있게 된다.

이렇게 기본적인 Synchronization에 대한 내용에 대해 알아보았다. 지금부터는 여러가지 synchronization 문제에 대해 알아볼 것이다.

Classical problems of Synchronization

Bounded-Buffer

Producer-Consumer problem이라고도 불리는 Bounded-Buffer problem은 생산만하는 producer와 소비만 하는 consumer가 공유자원을 두고 발생하는 synchronization problem이다.

• Producer의 경우 empty buffer가 존재하는지 (가득 찬 경우 write 작업을 할 수 없기 때문)를 확인하고 존재하면 critical section에 들어가 write 작업을 수행한다.
• Consumer의 경우 full buffer가 존재하는지 (full buffer가 비어있을 경우 소비를 할 수 없기 때문)를 확인하고 존재하면 critical section에 들어가 read 작업을 한다.

이 둘의 경우 서로에게 영향을 주기 때문에 P, V를 호출하는 부분이 서로 다른 곳에 위치한다고 해석을 했다. binary semaphore S_mutex로 각각의 critical section을 보호하는 것은 동일하지만, producer는 empty buffer에 대한 P를 호출하고 full buffer에 대한 V를 호출하고 consumer는 그 반대로 호출을 한다.

Producer가 write할 때, Consumer가 read 작업을 할 때 마다 buffer의 개수가 변하는데 이 방법을 통해 race condition을 방지할 수 있다.

Readers-Writers Problem

Readers-Writers problem의 경우 Producer-Consumer problem과 굉장히 유사하다. 그러나 다른 점은, Consumer의 경우 full buffer는 1만큼 줄이고 empty buffer는 1만큼 늘렸는데 이 경우는 read 작업이 공유 변수의 값을 변화시키지 않기 때문에 writer가 critical section에 있을 때를 제외하면 여러 reader들이 접근해도 된다는 점이다.
이 경우 2가지로 나뉘게 된다.

1. 모든 reader들이 다 읽은 뒤 writer가 작업 (writer의 우선순위 = 후순위)
2. ex) 2명의 reader가 작업 중이고 writer와 또다른 reader들이 대기 중이라면 2명의 reader의 작업이 끝난 뒤 writer 작업 후 이어서 reader들이 작업

여기서는 semaphore 변수로 mutex와 db를, 공유 변수로 현재 read 작업을 하고 있는 reader들의 인원수 readcount를 설정하였다.

공유 변수 readcount에 대한 보호를 mutex로 하여 readcount 값을 바꿔주고 readcount==1일 때 db로 critical section을 보호한 뒤 한 번에 한명의 reader가 진입하도록 되어 있다. 이 때 readcount 값이 1 일 때와 0일 때, 즉 제일 처음 진입한 reader와 마지막으로 빠져나오는 reader만 값을 바꿔주는 이유는 reader가 들어갈 때마다 readcount 값을 증감시키게 된다면 reader들 끼리의 병렬성이 보장되지 않기 때문이다. 그 말인즉슨 read의 경우 전에 말했듯이 값을 바꾸지 않기 때문에 여러 reader들이 동시에 작업을 해도 synchronization problem이 발생하지 않는다. 그러나 readcount=1에서 P(db)를 호출하는 것이 아니라 reader들이 들어올 때마다 P(db)를 호출하게 되면 말 그대로 한 번에 한 명의 reader만 critical section에 진입할 수 있게 되기 때문에 Producer-Consumer problem와의 차별성이 없어지게 된다.

따라서 제일 첫번째 reader가 들어갈 때와 마지막 reader가 나올 때만 readcount 값을 바꿔주는 것이다.

참고

• 만약 P, V 둘 중에 하나라도 atomic 하지 않은 경우
  : P, V 함수는 semaphore S의 값을 1 만큼 증감시키게 되는데 둘 중 하나라도 atomic 하지 않게 되면 여러 process들이 동시에 S 값을 바꿀 수 있게 되기 때문에 starvation이나 deadlock 문제가 발생할 수 있다.

Dining-Philosophers Problem

마지막으로 Dinint-Philosopher problem에 대해 보게 되면, 5명의 철학자들(process)이 5개의 젓가락(공유변수)를 두고 생기는 문제이다. 젓가락은 2개가 한 쌍이기 때문에 5명에게 5개의 젓가락을 준다는 것은 최소 1명 이상은 밥을 먹지 못한다는 의미이다. 그런데 만약, 모든 사람들이 본인 기준 오른쪽 / 왼쪽 젓가락 1개만 집게 된다면 아무도 2개를 잡은 사람이 없기 때문에 5명 중 그 누구도 식사를 할 수 없는 deadlock 상태에 이르게 된다.

Deadlock vs Starvation

• Deadlock
  : Deadlock은 2개 이상의 process들이 무기한으로 기다리고 있는 상태이다. 이 경우는 절대 해결이 불가능하다.
  
• Starvation
  : Starvation은 "indefinite blocking"을 의미한다. Priority Scheduling에서 priority가 낮은 process가 waiting queue에서 계속 후순위로 밀려나면서 계속 대기만 하는 경우가 대표적인 예시이다. Starvation의 경우 Deadlock과는 달리 언젠가는 해결이 된다.

그렇다면 Dining-Philosopher problem은 어떻게 해결해야할까? 가장 대표적인 3가지 방법이 있다.

• 무조건 1사람은 2개를 집는다
• 홀수번에 앉은 사람은 왼쪽 젓가락, 짝수번에 앉은 사람은 오른쪽 젓가락을 집는다.
• 젓가락이 5개면 4명을 앉힌다.

Monitor

Monitor란 OOP와 비슷한 개념이다. Monitor 내부에 선언된 공유변수의 경우 monitor에 선언한 public method로만 접근이 가능하다는 개념이다.

여기서, process가 monitor에 대기하기 위해서는 조건 변수가 반드시 선언되어 있어야 한다. 이 조건 변수의 경우 block/wakeup과 마찬가지로 wait(), signal()로 process를 이동시킨다.
위의 그림에서 condition variables를 추가하면 아래와 같다.

Dining-Philosopher problem