[KOCW] 반효경 운영체제 강의 정리 - 6. Process Synchronization 2

Semaphores(세마포어)

• Critical Section으로 들어가기 위한 작업을 추상화 하는 것
• Semaphores S
  • 정수형 변수
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

Critical Section of n Processes

Synchronization variable
semaphore mutex; /* intially 1 : 1개가 CS에 들어갈 수 있다. */

Process pi
do {
    P(mutex);    /* 만약 가능하다면 접근하고 안된다면 기다린다 */
    critical section
    V(mutex); /* 세마포어의 값을 증가해준다.*/
    remainder section
} while(1);

• busy-wait는 효율적이지 못함(=Spin Lock)
• Block & Wakeup 방식의 구현 필요(=Sleep Lock)

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

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

• block
  • 커널은 block을 호출한 프로세스를 suspend 시킴
  • 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
• wakeup(P)
  • block된 프로세스 P를 wakeup 시킴
  • 이 프로세스의 PCB를 ready queue로 옮김

• Semaphore 연산을 다음과 같이 정의

P(S)
S.value--; /* 접근 준비 */
if(S.value < 0) {    /* 접근 실패 */
    add this process to S.L;
    block();
}

V(S)
S.value++;    /* 자원 반환 */
if(S.value <= 0) {    // 자원이 내놓았는데 0 이하면 프로세스가 잠든 것이다. 즉, 깨워야 한다.
    remove a process P from S.L;
    wakeup(P);
}

Busy-wait VS Block/WakeUp

• Block/wakeup overhead vs critical section 길이
  • critical section의 길이가 긴 경우 block/wakeup 선택
  • critical section의 길이가 매우 짧은 경우 block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있다.
  • 일반적으로는 block/wakeup 방식이 더 좋음

2가지 종류의 세마포어

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock / unlock)에 사용

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• S와 Q가 1로 초기화된 semaphore라고 하면

• Starvation
  • indefinite blocking(무기한 블록)
    • 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

출처 : http://www.kocw.net/home/cview.do?lid=02fbc3fd5cb74e97