2020-11-8 운영체제 기초(7) 세마포어

Semaphores(세마포어)

  • 세마포어를 통해 lock을 걸고 푸는걸 간단하게 할 수 있다

  • 공유자원을 획득하고 반납하는 과정을 세마포어가 처리할 수 있다.

  • 이전에 critical section 해결하는 알고리즘을 추상화를 했다.

  • 세마포어에는 P연산, V연산이 있다. P연산은 공유데이터를 획득하는 과정, V연산은 공유데이터를 반환하는 과정

  • Semaphore 변수 S가 있다. 변수값의 자원의 갯수를 의미.

    • integer형 변수

    • 만약에 Semaphore변수 S=5이면 공유자원이 5개가 존재. 이때 P연산을 하면 공유자원을 가져가므로 S=4가 된다. V연산을 하면 다시 S=5가 된다.

    • P연산을 하면 lock을 걸고, V연산을 하면 lock을 푼다.

    • 아래 2가지 atomic 연산에 의해서만 접근 가능

    • P(s)
while (S <= 0) do no-op
s--

    • V(s)
  s++

  • 세마포어를 n개의 프로세스에 적용하기

    • semaphore mutex; // 초기값 1

// Process PI  
do {
  P(mutex); // if mutex > 0, semaphore decrement
  critical section
  V(mutex); // semaphore increment
} while (1);
    • busy-wait방식(=spin lock) => 비효율

Block/ Wakeup 방식

  • 세마포어를 아래와 같이 정의

    • typedef struct {
  int value; // 세마포어
  struct process *L // process wait queue, 프로세스를 연결하는 리스트
} semaphore

// P연산 P(s)
S.value--;
if (S.value < 0) { // 공유자원이 없다.
  add this process to S.L; // 구조체 변수 L에다가 이 프로세스를 연결하고 blocked한다.
  block();
}

// V(S)
S.value++
  if (S.value <= 0) { // 잠들어 있는 프로세스가 있으면 깨워라
    // remove a process P from S.L;
    wakeup(P);
}

  • block과 wakeup을 다음과 같이 가정

    • block : 커널은 block을 호출한 프로세스를 suspend 시킨다. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
    • wakeup(P) : block된 프로세스 P를 wakeup시킨다. 이 프로세스의 PCB를 ready queue로 옮긴다.
    • v(s)에서 세마포어 변수가 음수이면 잠들어 있는 프로세스가 있는거다.

Busy-wait vs Block-wakeup

  • 보통은 Block-wakeup이 더 효율적이다.
  • Block-wakeup overhead vs Critical Section의 길이
  • critical section의 길이가 긴 경우 blcok-wakeup이 적당
  • critical section이 매우 짧으면 block-wakeup이 오버헤드가 busy-wait 오버헤드보다 클 수 있다.

세마포어의 2가지 타입

  • counting semaphore : 도메인이 0이상인 임의의 정수값, 주로 자원 카운팅에서 사용
  • Binary semaphore(=mutex) : 0, 1만 가질 수 있다. 주로 mutual exclusion(lock/unlock)에 사용

Deadlock and Starvation

  • 데드락 : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상

  • S, Q가 1로 초기화된 세마포어라 하자.

  • //P0
P(S);
P(Q);
...
V(S);
V(Q);

//P1
P(Q);
P(S);
...
V(Q);
V(S);
    • 프로세스 P0과 P1가 각각 S,Q를 접근하고, Q,S를 획득 요청을 하면 Starvation이 발생한다.
  • Starvation : indefinite blocking, 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나올 수 없는 현상

Reference

  • https://1.bp.blogspot.com/-8CZTgMmmpuo/Xox1HhX4a8I/AAAAAAAAAsY/IA9LNC-r-QM-Z_aJmaINK9RqJc66zYoQwCLcBGAsYHQ/s640/highest-priority.webp => Multilevel Queue
  • https://jhi93.github.io/category/os/2019-12-14-operatingsystem-06-1/ => execution-box
  • http://denninginstitute.com/modules/ipc/pink/semaph2.gif => block and wake up
Written on November 8, 2020