critical section은 공유 데이터를 접근하는 코드이며, remainder section은 공유데이터를 접근하지 않는 코드이다. 프로세스는 이러한 공유 데이터를 접근하는 코드와 그렇지 않은 코드가 반복되며 구성된다. 위 그림을 보면 공유데이터를 접근하는 코드 전에 entry section을 넣어 lock을 걸어 동시에 여러 프로세스가 critical section에 들어가는 것을 막으며, critical section이 끝나면 exit section으로 unlock하여 다른 프로세스가 critical section에 들어갈 수 있도록 해준다.
이는 critical section problem을 해결하기 위한 initial attempts이며 해당 글에서 소프트웨어적으로 코드를 넣어서 critical section 문제를 해결하는 법을 알아볼 예정이다.

먼저, critical section 문제를 풀기 위해 만족해야할 조건을 알아보자.

critical section 문제의 프로그램적 해결법의 충족조건

Mutual Exclusion(상호배제)

프로세스가 critical section에 들어가 있으면 다른 프로세스들은 critical section에 들어갈 수 없어야 한다.

Progress(진행)

critical section에 아무도 들어가 있지 않은 상황에서 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다. 만약 여러 프로세스가 동시에 critical section에 들어가는 것을 막고자 하다가 코드를 잘못 짜 아무도 critical section에 못 들어가게 되는 경우 progress를 만족하지 못하는 상황이 된다.

Bounded Waiting(유한대기)

기다리는 시간이 유효해야 한다.
Progress 조건과 다르게 특정 프로세스 입장에서 critical section에 들어가지 못하여 starvation이 생기는 것을 방지하는 것이다. 예를 들어 프로세스 3개가 critical section에 들어가려는 상황에서 2개의 프로세스만 번갈아 들어가고 나머지 하나의 프로세스는 계속 기다려야 하는 경우에 Bounded Waiting을 만족하지 못하는 상황이 된다.

이런 조건들이 깨지는 경우는 단일 instruction이 아니라 수행 도중 CPU를 빼앗길 경우에 문제가 발생하며 critical section 문제가 발생하는 것이다. 따라서 이런 조건들은 만족하면서 lock을 잘 걸었다가 풀 수 있는 SW 알고리즘들을 알아보자

critical section 문제 해결 알고리즘

Algorithm 1

Synchronization variable

int turn; //turn 변수를 사용하여 critical section에 들어갈 차례를 나타내준다. 즉 몇번 프로세스가 들어갈 수 있는지 나타낸다.
initially turn = 0;

Process P0

turn 변수가 0이 아닌 동안 while문을 계속 돌면서 자기 차례를 기다린다.

do {
    while (turn != 0);
    critical section
    turn = 1;
    remainder section
} while (1);

이 방법은 turn이라는 변수를 사용하여 critical section에 들어갈 차례를 나타내는 방법이다. 자신의 차례가 아닌 경우 while문에서 계속 기다리고 있다가 상대방이 critical section에서 빠져나오면서 turn을 자신의 차례로 만들어주면 critical section에 들어가게 된다.
이 방법은 mutual exclusion은 만족하지만 progress는 만족하지 못한다. 왜냐하면 critical section을 반드시 교대로 들어가도록 되어있기 때문이다. 프로세스들이 critical section에 들어가려는 빈도가 일정하지 않아, 극단적으로 P0는 빈번히 들어가고 P1은 한번만 들어간 후 들어가지 않게 된다면 P1이 turn을 바꿔주지 않아 P0도 critical section에 들어가지 못하는 상황이 발생한다.
따라서 turn을 교대로만 바꿔주는 해당 방법은 문제를 잘 해결할 수 없다.

Algorithm 2

Synchronization variables

boolean flag[2]; // critical section에 들어가고자 하는 의사 표시
initially flag[모두] = false; //처음에는 CS에 들어가고자 하는 프로세스가 없다.

Process Pi

do {
    flag[i] = true; //자신의 flag를 true로 만들어 CS에 들어가고자 함을 표시
    while (flag[j]); //상대가 들어가고자 하는지 체크하며 기다림
    critical section //상대의 flag가 true가 아니면 CS에 들어감
    flag[i] = false; //CS 나오면서 자신의 flag flase로 만듦
    remainder section
} while (1);

이 방법은 flag란 배열을 사용해서 본인이 critical section에 들어가고자 함을 표시한다.
이 알고리즘은 mutual exclusion은 만족하지만 progress를 만족하지 못한다. 프로세스 i가 flag를 true로 가지고 있는 상태에서 CPU를 빼앗기고 CPU가 프로세스 j에게 넘어간 상황을 생각해보자. 이때 j 역시 flag를 true로 바꾼다면, flag[i]가 true라 critical section에 들어가지 못하고 기다린다. i가 다시 CPU를 잡게 된다면 flag[j]가 true라 마찬가지로 critical section에 들어가지 못하고 기다린다.
이렇게 아무도 critical section에 들어가지 못하는 상황이 생길 수 있다.
따라서 이 방법 역시 문제를 해결하지 못한다.

Algorithm 3 (Peterson's Algorithm)

Combined Synchronization Variables of Algorithms 1 & 2

Process Pi

do {
    flag[i] = true; // 먼저 내가 임계 구역에 들어가고 싶다고 알림
    turn = j; // turn을 상대방으로 바꾼다
    while (flag[J] && turn == j); //상대방의 flag가 true이고 상대방 trun인 경우에만 기다린다. 상대방의 의사가 없거나 상대방의 차례가 아닌 경우에 내가 CS에 들어갈 수 있다.
    critical section
    flag[i] = false;
    remainder section
} while (1);

flag와 turn을 모두 사용한다. 두 프로세스 모두가 들어가고자 하는 상황에서는 turn을 따지고, 그렇지 않은 경우에는 turn에 관계 없이 들어가는 것이다.
이 알고리즘은 mutual exclusion, progress, bounded waiting을 모두 만족한다.
하지만 이 코드는 busy waiting(=spin lock)이라는 문제가 있어 비효율적이다. 이는 CPU 할당 시간에 while문을 계속 돌면서 waiting하게 되어 계속 CPU와 memory를 쓰면서 wait하기 때문이다.

하드웨어적으로 하나의 instruction만 주어진다면 이런 ciritical 문제는 쉽게 해결된다. 지금부터 하드웨어적으로 critical section문제를 해결하는 법을 알아보자.

Synchronization Hardware

instrcution 하나만으로 데이터를 읽고 쓴느 작업을 동시에 실행할 수 있ㄷ록 한다. 보통 그 instruction으로 Test_and_Set을 사용한다. 이는 하드웨어적으로 Test&Modify를 atomic하게 수행할 수 있도록 지원한다.
이렇게 되면 SW적으로 복잡한 코드를 짤 필요없이 간결하게 바뀐다.

위 그림은 a변수를 읽은 후, 그 변수를 무조건 1로 설정하도록 명령어가 구성되어 있다. 이 과정이 Test_and_Set을 통해 atomic하게 동작한다.

Synchronization variable

boolean lock = false;

Process Pi

do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    remainder section;
} while (1);

lock이 걸려있지 않다면 (read했는데 a==0인 경우 아무도 critical section에 들어가 있지 않음을 의미한다) lock을 내가 걸고(a=1) critical section에 들어가는 작업을 atomic하게 실행하는 것이다.
만약 lock이 이미 걸려있다면 1이 읽히고(후에 1로 세팅도 하지만 원래 값이 1이라 무시된다) while문에서 기다린다.

프로그래머의 일을 간소화하기 위해 앞의 방식들을 추상화시킨 semaphores를 정의해서 사용하는 것이 일반적이다.

Semaphore

추상 자료형이란, object와 operation으로 구성된 것이다. 정수 추상 자료형이란 정수 숫자가 있고 그 숫자에 대해 정의된 연산이 있는 것을 말한다. 즉 추상 자료형은 논리적으로 정의하는 것이다. Semaphore도 일종의 추상 자료형에 해당하며, 앞의 방식들을 추상화시킨 것이다.
Semaphore는 integer variable을 가지고 P연산과 V연산 두가지를 정의한다.
세마포어를 사용하는 이유는 무엇일까? 앞서 나온 Lock을 걸었다 풀었다 하는 것을 프로그래머에게 제공하기 위해 사용된다. 또한 어느 공유 자원을 획득하고 반납하는 것을 세마포어가 처리해줄 수 있다.
먼저 P연산은 세마포어 변수 값을 획득하는 과정, 즉 공유데이터를 획득하는 과정이고 Lock에 해당한다.
V연산은 다 사용하고 반납하는 과정이며, Unlock에 해당한다.
세마포어 변수가 정수 값을 가질 수 있는데, 이는 자원의 개수를 나타낸다. 예를 들어 S가 5면 자원이 5개 있는 것이고 이 상태에서 P연산을 한번 하면 자원을 하나 가져가 S가 4가 된다. V를 하면 자원을 다 사용하고 내어주기 때문에 이 상황에서 V연산을 하면 S가 다시 4가 된다.
변수 S에 P연산을 했을 때 자원을 다 가져가고 없는 상태면 while문을 돌고, 누군가가 자원을 내어줘서 S가 양수가 되면 S를 하나 빼고 자원을 획득한다. 사용이 다 끝나면 V연산을 통해 S를 증가시키고 자원을 반납한다.

P와 V는 atomic하게 연산된다고 가정한다. 추상적인 정의이기 때문에 어떻게 atomic하게 구현되는지까진 따지지 않는다.
Semaphore에서도 busy-wait(=spin lock)문제가 생긴다. 자원이 없을 때 P연산을 하게 되면 계속 while문에서 기다리다가 CPU 시간을 다 사용하게 된다.

Critical Section 문제 해결을 위한 Semaphore

critical section 문제에서 세마포어를 사용하게 되면 세마포어 변수 mutex를 처음 1로 놓고 critical section에 들어갈 때 P연산, 빠져나올 때 V연산을 취해 critical section 문제를 해결한다. 세마포어가 지원되는 경우 프로그래머는 critical section 문제를 P와 V연산을 통해 해결할 수 있고, P와 V를 어떻게 구현할지는 그때그때 구현하는 시스템의 몫이다. 즉, 사용자가 일일이 코딩해야하는 것이 아니라 추상 자료형을 제공해주면 프로그래머는 이를 간단하게 사용하기만 하면 된다.

Block & wake up(=sleep lock)

이 방법으로 세마포어를 구현하여 크리티컬 섹션문제를 해결하면 busy wait를 해결할 수 있다.
프로세스가 Lock을 얻지 못하면 blocked 상태가 되어 잠든다. 누군가가 공유데이터를 쓰고 있으면 그 프로세스가 내어주기 전까지는 차례가 오지 않기 때문에 while문에서 기다리며 busy wait하는 게 아니라 blocked된 상태로 잠들어 있다가 프로세스가 공유데이터를 내어주면 그때 깨어나서 ready queue에 들어간다. 후에 CPU를 얻으면 비로소 공유데이터를 얻을 수 있다.
세마포어를 획득할 수 없어 프로세스를 block시키는 것은 struct process *L로 정의된 wait queue에 연결리스트로 PCB를 넣는 것이다.

구체적인 구현

P연산

자원을 획득하는 과정이다. 자원에 여분이 있으면 자원을 획득하여 세마포어 변수값 S.value를 하나 빼준다. 자원에 여분이 없으면 block상태로 들어가 잠에 들어 S.L에 프로세스가 연결된다.

V연산

자원을 반납하는 과정이다. 자원을 단순 반납만 하는 것이 아니라 해당 자원을 기다리며 잠들어 있는 프로세스가 있다면 이를 깨워주는 작업이 함께 필요하다.
이때 P연산에서 S.value를 먼저 감소시킨 후 이것이 0미만이면 blocked상태에 들어가기 때문에 자원을 반납한 후 S.value가 늘어난 것이 0 이하이면 기다리는 프로세스가 있음을 의미한다. 만약 이것이 양수값이면 자원에 여분이 있어 기다리는 프로세스가 없음을 나타낸다.
busy wait방식에서는 S변수가 정확한 자원의 개수를 세는 변수였지만 여기서는 자원을 기다리고 있는지 아닌지에 대한 상황을 나타내는, 깨워야 할 누군가가 있는지 없는지 확인하기 위한 변수이다.

Busy-wait vs Block/wakeup

일반적으로 block/wakeup을 쓰는 것이 더 효율적이다. CPU를 계속 쓰면서 기다리지 않아 CPU를 낭비하지 않기 때문이다.
그런데 굳이 나누어 보자면, block/wakeup도 오버헤드를 가진다. . 프로세스의 상태를 ready ↔ block 상태로 바꿔줄 때 오버헤드가 발생한다. 그래서 critical seciton의 길이가 매우 짧은 경우에는 busy wait의 오버헤드가 block/wakeup 오버헤드보다 더 짧아지는 상황이 생길 수도 있다(busy wait를 써도 크게 문제는 되지 않는 정도의 의미).

하지만 critical section 의 길이가 긴 경우에는 busy wait를 사용하면 한번 lock을 걸고 굉장히 오랫동안 unlock하지 않음에도 다른 프로세스가 CPU를 얻을 때 unlock되기를 기다리고만 있기 때문에 이런 경우에는 block/wakeup이 필수적이다.

세마포어 종류

counting semaphore

자원의 개수가 여러 개 있어서 여분이 있으면 가져다 쓸 수 있는 경우이다. 주로 resource counting, 여분의 자원의 수를 세는 용도로 쓰인다.

binary semaphore(=mutex)

자원의 개수가 하나인 경우, 0또는 1 값만 가질 수 있는 세마포어로 주로 mutual exclusion(lock/unlock)에 사용한다.

세마포어 사용 시 주의점

Deadlock and Starvation

• Deadlock
  S와 Q가 binary semaphore인 경우 문제가 생길 수 있다.
  예를 들어 P0가 먼저 CPU를 얻어서 S를 차지한 다음, CPU를 빼앗기고 P1이 CPU를 얻어 Q를 획득한다. 그 후 S를 획득하려 봤더니 이미 P0이 차지하고 있다. 이런 경우에 위의 상황에서 영원히 서로 쥐고 놓지 않고 기다리고 있다.
  Deadlock은 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다. 상대방이 가진 것을 기다리면서 자기가 가진 것은 놓지 않고 영원히 기다리는 것을 deadlock이라 한다.
  자원을 획득하는 순서를 똑같이 맞춰주면 이런 데드락 문제를 해결할 수 있다. 위의 상황의 경우, 두 프로세스 모두 S→Q 순으로 획득하도록 한다면 해결할 수 있다.
• Starvation
  특정한 프로세스가 자원을 얻지 못하고 영원히 기다리는 현상을 starvation이라고 한다. 위의 deadlock 역시 starvation 측면에서 해석할 수 있다. 그런데 여기서 특별히 얘기하는 starvation은 특정 프로세스들끼리만 자원을 공유하여 다른 프로세스의 차례는 돌아오지 않는 현상을 의미한다.
• Dining-Philosophers Problem
  - deadlock 문제 : 5명의 철학자가 동시에 배가 고파져서 왼쪽 젓가락을 다 잡으면 deadlock이 발생(오른쪽 젓가락을 상대방이 쥐고 있음)한다.
  - starvation 문제 : 한 철학자를 가운데 두고 양쪽 철학자가 연이어 밥을 먹으면 가운데에 있는 철학자는 starvation에 빠진다.