5주차. 프로세스 동기화 (3) - 세마포어 (busy-wating, block & wakeup)

Semaphore

• Cirtical Section에 대한 문제 해결 알고리즘을 추상화 시킨것.
• Integer 변수: 정수값은 자원의 개수를 의미한다.
• 아래의 두가지 Atomic 연산으로만 접근이 가능하다.
• Semaphore 변수 "S"

P 연산

/* P 연산 */

P(S):
    if (S <= 0) then block(); /* until S > 0, S가 양수가 되면 자원을 획득 */
    else S--; /* 자원 획득 */

S가 0이하라면 해당 프로세스를 Block 시킴.

S가 1이상이라면 해당 자원을 획득하여 사용함.

→ 공유 데이터를 획득하는 과정, semaphore S의 값을 획득하는 과정

 

V 연산

/* V 연산 */

V(S):
    S++; // 자원 반납
    wake_up(); /* block 중인 프로세스 깨움 */

→ 자원을 사용하고 나서 반납하는 과정

 

S의 값이 1일 때,

P 연산 시 : 자원이 0이 되면서 이후 프로세스들은 Lock이 걸린다, 자원이 풀리면 사용한다.

V 연산 시 : 자원을 반납하면서 프로세스에 Lock이 걸려있다면 풀어준다.

1) 프로세스의 Critical Section 처리방식 - Spin lock (busy-wait)

// Synchronization variable
Semaphore mutex; /* 초기값 : 1, 1개만 Critical Section에 들어갈 수 있다 */

do {
    P(mutex); // if postive: decreasec&enter else: busy-wating
    CRITICAL_SECTION;
    V(mutex); // increase
    remainder section;
}

/*
busy-wating 방식은 비효율적이다.
따라서 Sleep lock 방식을 사용한다.
*/

P(mutex) → mutex가 1 이상이라면, mutex 1감소하고 자원을 사용해서 critical section 진행, 아니면 계속 대기

V(mutext) → 사용한 자원을 반납하면서 mutex를 1 증가

 

문제점

• Critical Section이 긴 경우 오랬동안 busy-wating 해야하므로 비효율적 → block & wakeup 을 지향함

2) 프로세스의 Critical Section 처리방식 - Sleep lock (Block & Wakeup)

Semaphore를 다음과 같이 정의

typedef struct {
    int value;          /* semaphore */
    struct process *L;  /* process wait queue */
} semaphore;

value는 기존의 semaphore의 값과 같은 역활을하고, L은 사용가능한 자원이 없을 때 (S ≤ 0) 프로세스를 순서대로 담기위한 큐이다.

Semaphore {
  Value;
  L; // L -> PCB -> PCP -> PCB ...
}

blcok

• 커널은 block을 호출한 프로세스를 Block시킨다.
• 해당 프로세스의 PCB를 semaphore의 wait queue(L)에 넣는다.

wakeup(P)

• block된 프로세스를 wakeup시킨다. 해당 프로세스의 PCB를 ready queue로 옮긴다.

P연산

S.value--;
if (S.value < 0) {
    add this process to S.L; /* wait queue에 담음 */
    block;
}

• 자원을 획득하고 value의 값을 1 줄인다.
• 자원이 음수라면 받을 자원이 없다는 것이므로 해당 프로세스를 wait queue에 넣고 block 시켜놓는다.
• 그렇지 않다면 Critical Section을 수행한다.

V연산

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

• 자원을 반납하므로 value의 값을 1 증가시킨다.
• 자원이 0이하 이면 대기 프로세스가 있었던 것이므로 wait queue에서 프로세스 P를 제거한 하고 깨운다.
• 양수인 경우 자원이 남아있는 상태.

---

Busy-Wait v.s. Block & Wakeup

block & wakeup이 일반적으로 cpu 이용시간도 좋고, 쓸데없는 연산을 반복하지 않아서 좋다.

단, block & wakeup의 경우 프로세스의 상태변화(ready ←→ suspend)의 overhead가 있다. (문맥교환 비용)

• Critical Section의 길이가 매우 짧아서 빈번하게 프로세스가 바뀌는 경우 Block & wakeup의 오버헤드가 Busy-Wait의 오버헤드보다 커질수 있다.

Semaphore 종류

Binary Semaphore (mutual Exclusion, mutex)

• 0 또는 1의 값만 가질 수 있는 Semaphore이다.
• 주로 mutual exclusion (lock / unlock) 을 위해 사용한다.

Counting Semaphore

• 0 이상인 임의의 정수값.
• 주로 여분의 자원개수를 세는 용도로 사용한다.

DeadLock

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

Binary Semaphore 구조

1. P0 : P(S)를 수행하고, P(Q)를 수행하기 전에 cpu를 반납
2. P1: P(Q)를 수행하고, P(S)를 수행 하려는데 S는 이미 0번 프로세스가 갖고있어서 반환될 때까지 대기한다.
3. P0 : 다시 0번 프로세스가 P(Q)를 수행하려해도 1번 프로세스가 Q를 갖고 있어서 대기하게 된다.

→ 결과적으로 두 프로세스 모두 세마포어를 하나씩 쥔 채로 상대방 것을 요구하면서 무한 대기상태에 빠진다. (DeadLock)

 

해결방법

• Semaphore를 얻을 때 순서를 맞춰서 얻게 하면 가능하다.
• S를 얻어야 Q를 얻을수 있도록 하면 p1에서 Q를 수행하기위해 S를 대기하다가 p0로 다시 돌아가고, p0에서 마저 처리할 수 있게 된다.

Starvation

• 대표적으로 굶주리는 철학자 문제가 있다.
• 특정 프로세스가 세마포어 큐에서 빠져나가지 못하고 계속 갇혀있는 현상이다.