[OS] Process Synchronization

임계 구역 문제를 해결하기 위한 충족 조건

• 상호 배제 (Mutual Exclusion)
  - 어떤 프로세스가 임계 구역 부분을 수행 중이면 다른 모든 프로세스는 그의 임계 구역에 들어가면 안 된다.
• 진행 (Progress)
  - 아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있으면 임계 구역에 들어가게 해 주어야 한다.
• 유한 대기 (Bounded Waiting)
  - 프로세스가 임계 구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 한계가 있어야 한다.
  - ex) 세 개의 프로세스가 있을 때 두 개의 프로세스만 번갈아가며 임계 구역에 들어가는 것은 유한 대기 조건을 만족하지 못한 것이다.
  

임계 구역 문제 해결 알고리즘

Peterson's Algorithm

do {
    flag[i] = true; // 임계 구역에 들어가고 싶다고 알린다
    turn = j; // 자신의 다음 차례를 프로세스 j로 바꿔 준다
    while (flag[i] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while (1);

상대방이 임계 구역에 들어가 있지 않고, 들어갈 준비도 하지 않는다면 내가 들어간다.

세 조건을 모두 만족하지만, 계속 CPU와 메모리를 쓰면서 기다리기 때문에 busy waiting (spin lock)이 발생한다.

임계 구역에 들어가려면 상대방이 CPU를 잡고 flag 변수를 false로 바꿔주어야 하는데, 내가 CPU를 잡고 있는 상황에서 의미 없이 while문을 돌며 CPU 할당 시간을 낭비해야 한다.

동기화 하드웨어

변수 a를 읽은 후, 그 변수를 무조건 1로 설정하도록 명령어가 구성되어 있다.

임계 구역 문제가 발생한 근본적인 이유는 데이터를 읽고 쓰는 동작을 하나의 명령어로 수행할 수 없기 때문이다. 따라서 명령어 하나만으로 데이터를 읽는 작업과 쓰는 작업을 atomic 하게 수행하도록 지원하면 앞선 임계 구역 문제를 간단하게 해결할 수 있다.

Mutual Exclusion With Test & Set

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

Test_and_Set() 함수는 매개 변수를 읽어내고, 그 변수를 1로 바꿔 준다.

만약 처음에 lock의 값이 0이었다면, while문을 탈출하고 lock 값이 1이 된다. 반대로 lock의 값이 1이면 while문에서 갇히고 lock 값은 그대로 1이 된다

Semaphore

• 추상적
• 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구

Semaphore S

• Integer variable(= 자원의 갯수)
• 아래의 두 가지 atomic 연산에 의해서만 접근이 가능

P(S): 공유 데이터를 획득하는 과정 (lock)으로 S가 양수이어야 한다.

while (S <= 0) do no-op; //wait.
S--;

V(S): 공유 데이터를 사용하고 반납하는 과정 (unlock)

S++;

busy-wait(= spin lock): 효율적이지 못함

Block & Wake-up(= Sleep lock)

typedef struct
{
    int value; // 세마포어 변수
    struct process *L; // 프로세스 Wait Queue
} semaphore;

P(S): 세마포어 변수 S를 무조건 1 줄이고, 그 변수의 값이 음수면 해당 프로세스를 Wait Queue로 보낸 후 Block 상태로 만든다.

S.value--;
if (S.value < 0)
{
    add this process to S.L;
    block();
}

V(S): 세마포어 변수 S를 무조건 1 늘리고, 그 변수의 값이 음수이면 이미 기다리고 있는 프로세스가 있으므로 프로세스 P를 Wait Queue에서 꺼내서 Ready Queue로 보낸다.
세마포어 변수 S 값이 양수면 아무나 임계 구역에 들어 갈 수 있으므로 별다른 추가 연산을 하지 않는다.
V 연산은 특정 프로세스가 공유 데이터를 반납한 후 임계 구역에서 나가는 연산임을 기억해야 한다.

S.value++;
if (S.value <= 0)
{
    remove a process P from S.L;
    wakeup(P);
}

Busy wait vs Block Wake-up

• 임계 구역의 길이가 긴 경우 Block/Wake-up 기법이 적합함.
• 임계 구역의 길이가 매우 짧은 경우 Block/Wake-up 기법의 오버헤드가 Busy-wait 기법의 오버헤드보다 크므로 Busy Wait 기법이 적합할 수 있음.
• 일반적으로 Block Wake-up 기법이 좋음.

세마포어의 종류

계수 세마포어 (Counting Semaphore)

• 도메인이 0 이상인 임의의 정수 값
• 여러 개의 공유 자원을 상호 배제함.
• 주로 resource counting에 사용됨.

이진 세마포어 (Binary Semaphore)

• 0 또는 1 값만 가질 수 있음.
• 한 개의 공유 자원을 상호 배제함.
• mutex와 유사함. (완전히 같지는 않음.)

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

P0은 P(Q) 연산을 통해 Q 자원을 얻고 싶지만, 이미 Q 자원은 P1이 갖고 있는 상태이므로 Q 자원을 가져올 수가 없다. 마찬가지로 P1도 P(S) 연산을 통해 S 자원을 얻고 싶지만, 이미 S 자원은 P0이 갖고 있는 상태이므로 S 자원을 가져올 수 없다.
이렇게 P0와 P1은 영원히 서로의 자원을 가져올 수 없고, 이러한 상황을 Deadlock이라고 한다.

해결법

자원의 획득 순서를 정해주어야 한다. S를 획득해야만 Q를 획득할 수 있다면 해결된다.

Starvation

프로세스가 자원을 얻지 못하고 무한히 기다리는 현상이다. indefinite blocking

Deadlock vs Starvation

Deadlock: 자원을 보유하고 있지마 서로의 자원을 요구하며 무한히 기다리는 현상
Starvation: 프로세스가 자원 자체를 얻지 못하고 무한히 기다리는 현상

Bounded-Buffer-Problem (Producer-Consumer Problem)

공유 데이터

• buffer 자체 및 buffer 조작 변수 (empty / full buffer의 시작 위치)

문제점

• 공유 버퍼이기 때문에 생산자 여러 명이 동시에 한 버퍼에 데이터를 쓰거나 수정할 수 있다.
• 마찬가지로 생산자가 동시에 한 버퍼의 데이터를 읽어갈 수 있다.

동기화 변수

• 이진 세마포어 (공유 데이터의 상호 배제를 위해)
• 계수 세마포어 (남은 full/empty 버퍼의 수 표시)
  

Readers-Writers Problem (독자-저자 문제)

• 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다.
• read는 동시에 여러 명이 해도 됨.

해결법

• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근할 수 있게 해 준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져 나가야만 Reader의 접근이 허용된다.

공유 데이터

• DB 그 자체
• readCount (현재 DB에 접근 중인 Reader의 수)

동기화 변수

• mutex (공유 변수 readCount를 접근하는 코드 (임계 구역)의 상호 배제를 보장하기 위해 사용)
• db (Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할)

Dining-Philosophers Problem (식사하는 철학자 문제)

모두가 동시에 왼쪽 젓가락을 들면 아무도 오른쪽 젓가락을 잡을 수 없으므로 Deadlock이 발생한다는 문제가 있다.

해결 방안

• 4명의 철학자만 테이블에 동시에 앉을 수 있게 한다.
• 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
• 비대칭: 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 방향을 정해준다.

Monitor

세마포어의 문제점

• 코딩하기 힘들다.
• 정확성의 입증이 어렵다.
• 자발적 협력이 필요하다.
• 한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.

모니터는 프로그래밍 언어 차원에서 동기화 문제를 해결할 수 있는 고수준 동기화 도구라고 할 수 있다.

프로세스가 공유 데이터에 접근하기 위해서는 위와 같이 모니터 내부의 프로시저를 통해서만 공유 데이터를 접근할 수 있도록 설계한다.

Condition Variable

• wait
  - 자원이 없으면 프로세스가 줄을 서서 기다리게 한다.
  x.wati() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 잠들게 된다.
• signal
  - 모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 한다.
  - signal() 은 정확하게 하나의 잠이 든 프로세스를 깨운다.
  - 든 프로세스가 없으면 아무 일도 일어나지 않는다.

잠들고 있으면 깨워라!