6.6 Semaphore

뮤텍스 락은 동기화 도구중에 가장 간단하다. 여기서는 뮤텍스 락과 유사하지만 프로세스가 활동을 동기화하는 더 복잡하지만 세밀한 방법을 제공한다. S는 두 원자적 연산인 wait() 와 signal()을 통해서 접근되는 integer 변수다(wait를 P 연산이라고도 하며, signal을 V 연산이라고도 한다).

wait(S) {
  while (S <= 0)
    ; // 바쁜 대기
  S--;
}

signal(S)
{
  S++;
}

 위 wait()와 signal() 연산에서 semaphore의 integer 값에 대한 모든 수정은 atomic하게 실행되어야 한다. 즉, 한 프로세스가 세마포어 값을 수정할 때, 다른 프로세스가 동시에 그 같은 세마포어 값을 수정할 수 없다. 또한 wait(S)의 경우, Semaphore의 S의 정수값(S ≤ 0)의 테스트 및 가능한 수정 (S--)이 중단 없이 실행되어야 한다.

 

6.6.1 Semaphore Usage

 OS에서는 보통 counting semaphore 와 binary semaphore 로 두가지 유형이 있다. counting semaphore 의 값은 무제한 도메인에 걸쳐 범위를 가질 수 있고, binary semaphore 의 값은 0부터 1까지만 범위를 가질 수 있다. 따라서 binary semaphore 는 Mutex Lock과 유사하게 동작한다. 실제로, 뮤텍스 락을 제공하지 않는 시스템에서는 이진 세마포어를 사용하여 상호 배제를 제공할 수 있다.

 counting semaphore 는 유한한 수로 구성된 자원에 대한 액세스를 관리할 때 사용할 수 있고, 사용 가능한 리소스의 수로 초기화된다. 리소스를 사용하려는 각 프로세스는 semaphore 에게 wait() 연산을 수행시켜서 (이로써 카운트를 감소시킴) 리소스에 액세스한다. 프로세스가 리소스를 해제하고 싶을때 각 프로세스는 semaphore에게 signal() 연산을 수행시켜서 (카운트를 증가시킴) 해제하게 된다. 세마포어의 카운트가 0이 되면, 모든 리소스가 사용 중이며, 이후에 리소스를 사용하려는 프로세스는 카운트가 0보다 커질 때까지 블록된다.

 또한 세마포어를 사용하여 다양한 동기화 문제를 해결할 수 있다. 예를 들어, 두 개의 동시에 실행되는 프로세스를 고려해보자. 이러한 방식을 구현하려면 처음에 P1과 P2가 공통의 세마포어 synch를 공유하도록 하고, 이를 0으로 초기화해야 한다. 프로세스 P1에서는 다음과 같은 코드를 넣는다.

/* codes */
signal(synch);

 

그 다음에 P2는 다음 명령을 수행한다.

wait(synch);
/* codes */

synch는 0으로 초기화되므로 P2는 P1이 signal(synch)를 호출한 후에만 /* codes */ 를 실행할 수 있다.

 

6.6.2 Semaphore Implementation

 뮤텍스 락 구현은 busy waiting의 문제가 있다고 했다. wait(), signal() semaphore 연산의 정의도 동일한 문제가 있다. 프로세스가 wait 연산을 수행하고 값이 양수가 아닌 것을 발견하면 busy waiting 대신 프로세스를 ready 상태로 전환하고 세마포어와 관련된 ready queue에 자신을 넣는다. 그 후 제어가 CPU 스케줄러로 전달되어 다른 프로세스를 실행하도록 선택한다.

 세마포어 S 에서 대기 중인 프로세스는 다른 프로세스가 signal() 연산을 실행할 때 다시 실행되어야 하며 프로세스는 wakeup 연산을 통해서 wait 상태에서 ready 상태로 변경된다. 그 다음 ready 큐에 배치된다. 정의에 따라 세마포어를 구현하기 위해 세마포어를 다음과 같이 정의한다.

 

typedef struct {
  int value;
  struct process *list;
} semaphore;

 각 세마포어는 value 값과 프로세스 list를 가진다.

 

wait (semaphore *S)
{
  S->value--;
  if (S->value < 0)
  {
    add this process to S->list;
    sleep();
  }
}

프로세스가 세마포어에서 wait 되어야 할 경우에 그 프로세스는 프로세스 리스트에 추가된다.

 

signal (semaphore *S)
{
  S->value;
  if (S->value <= 0)
  {
    remvoe a process P from S->list;
    wakeup(P);
  }
}

signal 연산은 대기 중인 프로세스 리스트에 하나의 프로세스를 제거하고 그 프로세스를 wakeup 한다.

 sleep() 연산은 이를 호출한 프로세스를 중지시키고, wakeup(P) 연산은 중지된 프로세스 P(sleep 된 것) 을 다시 재개한다. 이 두 연산은 운영 체제에서 기본 시스템 호출로 제공된다. 이 구현에서는 세마포어 값이 음수가 될 수 있는데, 세마포어 값이 음수인 경우에는 그 절댓값은 해당 세마포어에서 기다리고 있는 프로세스의 수를 의미하고, 0일 때 기다리는 프로세스가 없다는 뜻이 된다.

 

 프로세스 대기 목록은 위의 semaphore 자료구조에서 봤듯이 PCB가 list 형으로 되어 있는 것을 봤다. 따라서 semaphore에는 value와 process(PCB라고 하는게 더 정확함) list가 있고, bounded waiting을 보장하기 위해 목록에서 process를 추가하고 제거할 때, head pointer와 tail pointer가 모두 포함된 FIFO 대기열 또한 사용할 수 있을 것이다(어떤 자료구조를 사용하던 제대로 동작하기만 하면 상관 무).

 

 또 semaphore 연산을 atomic하게 실행하는 것이 중요할 것이다(당연 data integrity를 위해). 두 프로세스가 동시에 동일한 세마포어에서 wait(), signal() 작업을 실행할 수 없도록 보장해야하며, 이는 critical section 문제에서, 단얼 프로세서 환경의 wait(), signal()이 실행되는 동안 인터럽트를 금지(다른 프로세스가 preemptive 할 수 없도록)하도록 이 문제를 해결할 수 있다.

 

 근데 이런 인터럽트를 금지하기 전에 다른 프로세서의 명령 때문에 interleave(교차)가 될 수도 있을 것이다. 이 때문에 multicore 아키텍처에서 모든 처리 코어의 인터럽트를 비활성화해야 하는데,,, 모든 코어에서 인터럽트를 비활성화하는 것은 복잡하고 성능이 떨어질 수 있기 때문에 SMP 시스템은 기본적으로 원자적인 compare_and_swap(), spinlock(wait(), signal()) 을 구현해놓았다.

 

• 모든 생성되는 thread는 기본적으로 ready state 가 됨
• scheduler에 의해 선택(ready queue에서 선택)되면 running state 가 됨
• ready state 의 프로세스에 대한 ready counting semaphore 존재 가능 (구현 맘대로)
• block state 의 프로세스에 대한 block counting semaphore 존재 가능 (구현 맘대로)
• sleep() 을 통해 점유하고 있던 CPU를 내어주고 block 상태로 들어가게 됨 → block counting semaphore
• yield() 을 통해 점유하고 있던 CPU를 내어주고 ready 상태로 들어가게 됨 → ready counting semaphore
• wakeup(P) 을 통해 해당 프로세스를 ready 상태로 돌릴 수 있음 → ready counting semaphore
• running에 대한 것은 binary semaphore(mutex로 해도 됨)를 사용해서 차지하고 있는지 or 아닌지를 구분
• 모든 semaphore는 PCB의 list와 atomic variable의 integer value를 가지게 됨