Synchronization 2

  이전 글에서는spinlock 방법을 알아봤다. 하지만 이 방법은 프로세스가 대기하고 있는 동안 다른 프로세스를 실행할 수 없다거나(busy waiting) 사이클 낭비를 초래하게 되는 단점이 있었다. 그리고 모든 프로세스가 critical section(cs로 줄임)에 들어가야 한다는 bounded wating 또한 충족할 수 없었다.

  spinlock방법은 컨텍스트 스위칭이 발생하지 않기 때문에(어쨌든 프로세스는 바뀌지 않고 lock을 얻으려고 시도하니깐) cs의 길이가 짧은 경우에는 더 유리하긴 하다. 이 글에서는 그렇지 않은 경우에 더 유리한 synchronization을 high-level 수준에서 구현한 방법들에 대해 알아볼 것이다.

Semaphores

  이전 글에서의 spinlock 방법말고 block&wait 방법이 있다고도 말했었다. 이 방법은 계속해서 lock을 얻으려고 시도하는게 아니라 lock을 얻지 못하면 잠시동안 cpu를 내려놓고 다른 작업이 cpu를 사용할 수 있게끔하는 것이다. 그렇게 된다면 busy waiting을 없애줄 수 있다. 지금부터 다뤄볼 semaphores 방식도 기본적으로 block&wait 방식이다. semaphore란 상태에 대한 정수 값이 담긴 object이고 이를 바탕으로 synchronization이 이뤄진다.

  공유되는 자원이 n개가 있다면 semaphore라는 변수의 초기값은 n이다. 만약 n=1이라면 이는 우리가 알고있는 lock이랑 똑같이 동작할 것이다. 이를 다루기 위한 두 개의 중요한 operation을 살펴보자.

• wait(): semaphore의 값을 감소시킨 뒤에 이 값이 0보다 작다면 0이상일 때까지 기다린다. 0보다 크다는 건 해당 리소스를 다른 쓰레드가 사용해도 아직 자원이 남아있기 때문에 다른 쓰레드가 들어와도 된다는 뜻이다.
• signal(): 자원을 다쓰고 나갈 때는 이를 반납했다는 표시를 해줘야하니 semaphore의 값을 증가시켜준다. 그리고 만약에 해당 자원을 쓰기위해 기다리고 있는 쓰레드가 있다면 신호를 보내 그 쓰레드를 깨운다.

  이를 통해 semaphore는 단순히 cs의 진입을 보호해주는 것 뿐만 아니라 자원이 여러개 있을 때 이것들이 동시에 잘 활용될 수 있도록 할 수 있다.

Implementing Semaphores

fig 1

  fig 1은 semaphore를 구현한 것이다. semaphore 내부를 보면 자원의 값을 담을 수 있는 value가 있고 프로세스들을 담을 수 있는 Q(queue, 여기서 대기)가 있다. 

  wait()를 살펴보자. 우선 value를 하나 감소시킨다. 만약 기존 value가 1이었다면 0으로 바뀌는 것이다. 그리고 또 다른 쓰레드가 공유 영역에 들어오면 value는 -1이 되는 것이다. 그렇다면 이 쓰레드는 지금 잡을 수 있는 자원이 없으니 semaphore의 Q에 들어간 뒤 block된다.

  영역을 나오게 되면 signal()을 호출하게 된다. 이 때는 value를 하나 증가시켜준다. 'S->value <= 0'인 경우는 이 영역을 들어오려고 시도한 다른 쓰레드가 있었다는 뜻이다. 그렇다면 대기하고 있는 쓰레드를 깨우게 된다.

Types of Semaphores

  semaphores은 mutex(mutaul exclusion)을 제공하는 binary semaphore와 Counting semaphore가 있다.

  semaphore의 초기 value를 1로 설정한다면 이는 binary semaphore가 된다. value가 0이 된다면 다른 쓰레드가 공유 영역으로 들어갈 수 없게 된다. 그렇기 때문에 mutex 기반의 접근을 제공해준다.

  semaphore의 초기 value를 1보다 큰 값으로 설정한다면 여러개의 쓰레드가 영역으로 들어갈 수 있게 된다. 이 말은 많은 unit을 가진 자원이 사용가능하다는 뜻이고 쓰레드들은 사용가능한 유닛만큼 들어올 수 있게되는 것이다.

 

Deadlock and Starvation

  더 진행하기 전의 deadlock과 starvation이라는 용어에 대해 이해하고 넘어가자. 이 둘은 synchronization 기능을 만들어 낼 때 해결해야 하는 요구조건이라고 보면 된다.

Deadlock

  deadlcok은 두 개 이상의 프로세스나 쓰레드들이 어떤 이벤트가 발생할 때까지 기다리고 있는데 그 이벤트가 발생할 수 없는 상황이다. 즉 프로그램이 더 이상 진행되지 않고 대기만 하고 있는 것이다.

fig 2

  예를 들어 S, Q라는 두개의 semaphore가 1로 초기화되어 있다고 생각해보자. fig 2의 같은 행에 있는 것은 동시에 발생하는 것이다. P0은 wait(S)를 통해 S의 value를 0으로 만들고, P1은 wait(Q)를 통해 Q의 value를 0으로 만들게 된다. 그 다음 행에서 P0은 Q의 value를 -1로 만들어서 block이 되고, P1은 S의 value를 -1로 만들어서 block이 된다. 이렇게 되면 둘다 blocking 상태가 되는데 이를 풀어주기 위해서는 signal()을 발생시켜줘야 한다. 하지만 P0입장에서는 P1이 Q를 놔줘야하는데 wait(S)에서 멈춰 있는 상태이므로 signal(Q)를 실행할 수 없다. 반대도 마찬가지다.

Starvation

  stavation은 어떤 쓰레드가 계속해서 blocking 되어있는 것이다. 다시 말하면 다른 쓰레드는 다 영역에 들어가는데 혼자만 lock을 못잡거나 semaphore가 부족해서 못들어가게 되는 것이다. 이렇게 되면 특정 프로세스들은 semaphore의 Q에서 제거되지 못하고 있게 된다. 이 같은 현상은 Q에 있는 항목들을 꺼낼 때 LIFO 방식을 사용한다면 발생할 수 있다. 

Priority Inversion

  당연히 priority가 높은 프로세스를 우선적으로 실행시켜줘야 한다. 그런데 만약 우선 순위가 낮은 프로세스가 우선 순위가 높은 프로세스가 필요로 하는 lock을 가지고 있게 된다면 우선 순위가 낮은 프로세스가 먼저 실행되어야 한다는 모순이 생겨버린다. 이러한 문제는 해당 상항에 처했을 때만 우선순위가 낮은 프로세스의 priority를 잠깐동안 높은 프로세스와 같게 해주는 priority-inheritance protocol로 해결할 수 있다.

 

Classical Problems of Synchronization

  Synchronization에서 발생할 수 있는 문제점은 일반적으로 3개가 있다. 하나씩 살펴보자

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

Bounded Buffer Problem

  버퍼는 무한하지 않고 유한하기 때문에 발생할 수 있는 문제이다. producer가 버퍼에 값을 넣고 consumer가 버퍼에서 값을 빼오는 역할을 한다고 할 수 있기 때문에 producer/consumer problem이라고도 한다. 어쨌든 producer와 consumer는 독립적이기 때문에 서로 다른 속도로 동작을 하게 된다. 밑에 있는 fig 3를 보자.

No synchronizaion

fig 3

  buffer에는 N개의 데이터가 들어갈 수 있고 count는 지금 버퍼에 몇 개의 데이터가 들어있는지를 말한다.

  Consumer의 코드를 보면 'count==0'이면 계속 while문 안에 갇혀있는 상태가 된다. 그렇지 않다면 out이 가리키는 데이터를 가져오고 다음번에 가져올 위치를 out에 지정해놓은 다음 count를 1감소시킨다.

  Producer는 'count==N'이면 계속 while문 안에 갇혀있는 상태가 된다. 그렇지 않을 때는 버퍼에 데이터를 넣은 다음에 그 다음에 들어갈 버퍼 인덱스의 위치를 얻어내고 count를 1증가시킨다.

  이러한 코드에서 발생할 수 있는 문제에는 어떤 것이 있을까? 지금 이 코드는 mutex가 보장되지 않는다. 그렇기 때문에 produce와 consume이 동시에 발생할 수도 있다는 말이다. 그리고 in, out의 값이 겹쳐버릴 수도 있을 것 이다. 이런 문제의 발생원인은 소제목에서도 알 수 있듯이 synchronization이 없기에 발생하는 문제이다. 그럼 이 코드를 semaphore를 이용하여 수정해보자.

Implementation with semaphores

fig 4

  여기서는 3개의 semaphore를 사용하고 있다. mutex는 말 그대로 상호배제를 위해 사용된다. producer와 consumer는 지금 buffer라는 공유자원을 사용하고 있기 때문에 in, out이 같을 때 동시에 접근되면 안된다. 이에 대한 상호배제를 제공해주기 위해 사용된다. 이는 cs를 보호하기 위한 lock/unlock 개념처럼 사용되었다.

  프로듀스의 입장에서는 지금 버퍼에 넣어줄 공간이 있는지 확인해줘야 한다. empty의 값이 0보다 크다면 버퍼에 데이터를 넣을 공간이 있다는 뜻이므로 wait(&empty)를 넘어서 wait(&mutex)에 도달할 수 있게되고 그렇지 않다면 block이 될 것이다.

  consumer의 입장에서는 buffer에서 소비할 것이 있는지 full을 통해 확인한다. full이 0보다 크다는 것은 지금 버퍼에 소비할 데이터가 있다는 뜻이므로 wait(&full)을 넘어서 wait(&mutex)에 도달할 수 있게되고 그렇지 않다면 block이 될 것이다.

  지금 바로 다루지는 않겠지만 이러한 방법이 producer와 consumer가 여러개일 때도 잘 동작할지에 대해서는 뒤에서 다뤄볼 예정이다.

Readers-Writers Problem

  문제가 발생하는 상황은 공유 자원을 여러개의 reader와 writer가 공유할 때이다. reader 쓰레드는 데이터를 읽을 수만 있고 writer 쓰레드는 데이터를 쓸 수만 있다. 이 때 다수의 reader가 한 번에 데이터를 읽을 수 있지만 wirter는 한번에 하나의 writer만 데이터를 쓸 수 있어야한다. 왜냐하면 데이터를 읽는 것은 데이터의 변화가 없어서 상관없지만 쓰는 것은 데이터가 바뀔 수 있기 때문이다.

  이 같은 상황 또한 3가지의 semaphore를 이용하여 구현해볼 수 있다. 그 종류에는 데이터를 읽을 수 있는 쓰레드의 수에 대한 readcount, 그리고 readcount를 컨트롤하는 mutex, writer나 reading이 독점적(exclusive)으로 이루어지게 하는 rw가 있다.

fig 5

  우선 Writer의 경우에는 rw가 0이냐 1이냐에 따라서 데이터를 쓸 수 있는지 없는지 기다린다. 1이라면 rw를 0으로 바꾼 뒤 다음으로 넘어가서 write작업을 수행하고 signal(&rw)를 통해 rw를 다시 1로 바꾼다. 이렇게 되면 semaphore를 기다리고 있는 reader나 또 다른 writer 중 하나를 깨워서 들어갈 수 있게 한다.

  reader는 readcount를 증가시킬 수 있기 때문에 mutex를 걸고 들어간다. 이후' readcount==1'인지 검사하는데 그 이유는 readcount가 1이라는 것은 이전까지 아무도 read하고 있지 않았기 때문에 writer 쓰레드가 지금 쓰고 있는지 여부를 알아내는 것이다. 이후에는 readcount에 대한 수정이 끝났으니 signal(&mutex)로 lock을 풀어준 뒤에 read 작업을 수행한다.

  만약 read 작업 중 또 다른 reader가 데이터를 읽고자 한다면 readcount가 1보다 크게 된다. 이 말은 다른 reader가 지금 읽고 있다는 뜻이므로 wait(&rw)를 할 필요가 없다는 뜻이다. 어찌됐든 reader 쓰레드가 read 작업을 끝내면 다시 mutex를 잠그고 readcount를 1감소시킨다. 그때 만약 'readcount==0'이라면 wirter 중에 기다리고 있는 쓰레드가 있는지 확인하고 있었다면 그것을 실행시킨다.

  지금 이 구조를 봤을 때 reader가 훨씬 많이 동작할 수 있다는 것을 알 수 있다. reader는 다른 reader가 read하고 있는 와중에 계속해서 들어올 수 있지만 writer는 마지막 reader의 read가 끝나야 다시 write할 수 있기 때문이다.

Dining-Philosophers Problem

fig 6

  Dining-Philosophers Problem은 알고리즘에서도 자주 본 Dijkstra(다익스트라)에 의해 모델링 된 문제이다. Deadlock, Starvation에 대한 문제를 확인해 볼 수 있을 것이다.  fig 6 처럼 둥근 식탁에 5명의 철학자들이 앉아 있는 상황인데 각각의 철학자들은 다음과 같은 과정을 반복하려고 한다.

1. 생각하기
2. 두 개의 포크를 집기
3. 먹기
4. 두 개의 포크를 내려놓기

  ※ 한번에 하나의 포크만 집을 수 있다.

A simple solution

 

fig 7

  포크가 5개이니, N=5라고 하고 각각이 1로 초기화 되어있다. L(i), R(i)는 각각의 포크 위치를  나타낸 것이다. philosopher()는 좀 전에 말한 1~4를 반복하는 것이고 pickup(), pickdown()은 각각 왼쪽->오른쪽 순서로 포크를 집고 내려놓는 함수이다. 이 코드에서는 문제가 발생할까?

  4명까지는 동시에 포크를 집어도 괜찮아 보인다. 4번째로 왼쪽 포크를 집은 철학자는 오른쪽 포크도 집을 수 있게되어 4번째->3번째->...->1번째 순서로 양손에 포크를 집을 수 있게 되니 말이다. 하지만 만약 5명의 철학자가 동시에 왼쪽 포크를 집었다고 생각해보자. 그럼 5명 모두 누군가 포크를 내려놓기만을 기다리게 된다(deadlcok). 이를 해결하기 위해서는 어떻게 해야할까?

A deadlock-free solution

fig 8

  이전 솔루션과의 차이점은 1~4번 철학자는 오른쪽->왼쪽 순서로 포크를 들게하고 마지막 5번 철학자만 왼쪽->오른쪽 순서로 포크를 든다. 이렇게 되면  1~4번이 오른쪽 포크를 들고 이후에 다시 왼쪽 포크를 들게되면 5번도 왼쪽 포크를 들 수 있게 되는 모양새가 되니 모든 철학자가 식사를 할 수는 있게된다. 하지만 5번 철학자는 다른 철학자들에 비해 포크를 자주 들지 못하는 문제점(starvation)이 발생한다.

  이러한 방법외에도 홀수번은 왼쪽, 짝수번은 오른쪽 포크를 집게 한다던가, 타임아웃을 두고 시간 내에 양쪽에 포크를 집지 못하면 다시 내려놓게 하는 등의 방법이 있다.

Problems with Semaphores

  synchronization을 구현하는데 semaphore를 많이 사용하였다. signal()-wait()를 한다거나, wait()-wait(), 또는 두개 중 하나를 빠드리게 된다든가 하면 언제든지 deadlock이나 starvation이 발생할 수 있기 때문에 semaphore를 사용하여 synchronization을 구현하는게 어려울 수 있다.

 

Coarse-Grain Locks & Fine-Grain Locks

  멀티 쓰레딩 환경 등 cs가 존재하는 환경에서 race condition을 방지하기 위해 lock을 사용할 수 있었다. lock을 사용하는 방식은 cs의 선정 범위에 따라 즉, Lock을 얼바나 세분화하여 설정하느냐에 따라 Coarse-grain Locks와 Fine-grain Locks 두가지로 나눌 수 있다. 이처럼 race conditon이 발생하지 않더라도 lock을 사용하는 방법에 따라 성능에 변화가 있을 수 있다.

Coarse-Grain Locks

 

fig 9

  Coarse-grain locks는 큰 임계영역을 취하는 lock이다. 즉 여러개의 cs를 묶어서 lock을 거는 것이다. fig 9을 보자. 한 쓰레드가 accts[]의 한 원소에 접근하고 있을 때 다른 accts[]의 원소에 들어가려는 쓰레드도 cs에 들어갈 수 없게 된다. 이 방법의 장점은 한 쓰레드가 cs에 들어가 있는 동안 다른 쓰레드는 들어올 수 없으니 예상치 못한 간섭이 발생할 수 없는 것이다. 단점은 두개의 cs가 병렬적으로 동작할 수 없어서 성능이 저하되는 것이 있다.

Fine-grain Locks

fig 10

  Fine-grain locks는 cs마다 lock을 거는 것이다. fig 10에서는 accts[]의 각 원소마다 lock을 걸어놓았다. 때문에 만약 accts[1]에 어떤 쓰레드가 접근하고 있어도 다른 쓰레드가 accts[2]에 접근할 수 있는 것이다. 그렇기 때문에 이 방법의 장단점은 coarse-grain lock의 반대이다. 장점은 cs들이 병렬적으로 실행될 수 있는 것이고, 단점은 실수가 발생할 수 있는 것이다. fig 10은 매우 간단한 예시였지만 만약 cs에 들어가려고 할 때 2개 이상의 lock이 필요한 경우를 생각해보자.

 

Multiple Locks

fig 11

  다음은 cs에 들어가기 위해 2개의 lock을 얻어야하는 은행계좌 예시이다. 예를 들어 1번 계좌가 2번 계좌로 이체(transfer)하기 위해서는 accts[1].lock(accts[id_from].lock)과 accts[2].lock(accts[id_to].lock)을 동시에 얻어야 한다. 이 코드에서는 어떤 문제가 발생할 수 있을까? 만약 Thread 0이 241->37로 이체하려고 하고 Thread 1이 37->241로 이체하려는 상황이 동시에 이뤄진다고 해보자. 그렇다면 fig 11과 같은 결과가 발생할 수 있다.

fig 12

  Thread 0, 1이 각각 241, 37의 lock을 얻었다. 그 다음 Thread 0은 241의 lock을, Thread 1은 37의 lock을 얻어야 한다. 하지만 두 쓰레드가 필요한 lock을 상대 쓰레드가 갖고 있는 상황이 지속되면서 하염없이 기다리기만 하는 일이 발생한다. 바로 deadlock이 발생하는 것이다. 즉 deadlock은 공유 자원을 서로 필요로 하게되면(circular wait) 발생하게 된다. 이에 대한 해결방볍이 있을까?

Correct Multiple Lock Program

  해결방법으로는 circular wait가 발생하지 않도록 항상 각 쓰레드가 multiple locks을 같은 순서로 얻으면 된다.

fig 13

fig 14

 fig 13은 fig 11의 코드를 수정한 것이다. min()과 max()를 통해 first, second를 정해주면 동일한 상황에서 두 쓰레드 모두 37->241의 순서로 lock을 얻고자 할 것이다. 즉 circular wait가 발생하지 않으므로 deadlock도 발생하지 않는다.

 

More Lock Madness

  문제가 거의 해결된 것 같지만 아직도 고려해야할 사항들은 많다. 만약 일부작업은 1개 또는 2개의 lock을 필요로 하거나 모든 lock을 필요로 할 때는 cs를 병렬로 실행할 수 있을까? 또는 전역 변수에 lock이 있을 때 operation은 언제 이 lock을 잡아야 할까? 이처럼 lock기반 프로그래밍은 고려할게 많아 매우 어렵다.

    게다가 lock을 얻는 것은 cost가 매우 큰 작업이다. 왜냐하면 lock에 대한 쓰기 권한 획득 등 lock의 정의에 의해 느린 atomic instructions을 필요로 하고 ordering constraint로 인해 속도가 훨씬 느려진다. 그리고 99%의 시간은 굳이 필요하지 않는 것에 소요된다. 왜냐하면 대부분의 동시 작업은 실제로 데이터를 공유하지 않지만 lock관련 작업은 계속 발생하므로 이유없이 lock을 획득하는데 시간을 지불하기 때문이다.

 

Condition Variables

  lock을 이용하여 상호 배제를 구현하였었다. 여기에 condition variable(cv, 상태 변수)를 추가하여 쓰레드간 실행 순서를 고려하는 방법에 대해서 살짝 살펴보자. 상태 변수는 쓰레드가 특정 조건을 만족하지 않았을 때 queue내에서 대기하게 만들어 준다. A쓰레드를 B쓰레드 실행완료 후에 실행하고 싶을 때, cv를 사용하여 A는 B 완료시까지 sleep상태로 기다리게 할 수 있는 것이다. 이러한 작업을 위해 다음과 같은 operation을 사용한다.

fig 15

• wait(cond_t *cv, mutex_t *mutex): wait()가 호출될 때 mutex가 유지되고 있다고 가정한다. 호출자를 절전 모드로 전환하고 mutex를 atomically하게 해제한다. 그리고 깨워지게 되면 return 전에 mutex를 다시 획득한다.
• signal(cond_t *cv): cv를 가진 쓰레드에게 signal을 보내서 깨운다.
• broadcast(cond_t *cv): 대기 중인 쓰레드를 모두 깨우고 대기 중인 쓰레드가 없다면 아무 작업도 하지 않고 반환한다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org