세마포어

세마포어 (Semaphore) 란?

 

한 프로그램안에 다수의 프로세스가 동작할때 공유 (데이타)메모리를 사용하게된다.

그럴때 크리티컬섹션(임계영역)에 서로 경쟁하다가 동시에 충돌나거나 순서가 뒤바뀌는경우가있따.

이러한 문제를 해결하기위해........ 태어난 세마포어

그 이름은 바로..!  세마포어.

이녀석의 역활은 한번에 하나의 프로세스만 접근을 가능하게 만들어주는것이다. (이한줄로 개념)

 

 

일단 가장 기본적인 기법으로 Dijkstra 알고리즘 기법이 있다.

이것은 두개이상 프로세스들은 간단한 형태의 시그널을 이용하여 협동 할수있다.

즉 한 프로세스가 특정 시그널을 수신할때가지 정해진 위치에서 강제로 중지하는것이다,

좀더 복잡한 프로세스들 간의 상호작용에대한 요구 조건도 적절한 구조의 시그널을 이용하면 만족 할수있다.

 

 

세마포어에도 종류가있다!

 

 - 범용 세마포어(General Semaphore or Counting Semaphore)

 - 이진 세마포어(Binary Semaphore or  mutex)

 

우선 일반 세마포어부터 소개하겠다 (범용)

 

struct semaphore {
       int count;
       queueType queue;
}
void wait(semaphore s)
{
       s.count--;
       if (s.count < 0)
       {
           요청한 프로세스를 s.queue에 연결
           요청한 프로세스를 블록상태로 전이시킴
       }
}
void signal(semaphore s)
{
       s.count++;
       if (s.count <= 0)
       {
          s.queue에 연결되어 이는 프로세스를 큐에서 제거

          프로세스의 상태를 실행 가능으로 전이시키고, 레디큐에 연결
       }
}

위의 소스코드는 슈도코드이며.... 일반제너럴 세마포어임을 보여준다.

 

Singal과 Wait는 원자적으로 수행되며  각 프리미티브가 수행되면 완료될때까지 다른프로세스가 끼질못한다.

접근불가! (보호받는의미)

 

다음은 일반세마포어의 구조를 나타낸다.

 

1. 세마포어 초기화 : 세마포어는 음이 아닌 값으로 초기화한다.

 

2. semWait  : 

                   - 세마포어 값을 감소한다.

                   - 만약 값이 음수가되면 semWait호출한 프로세스는 블럭(대기)한다.

                   - 음수가 아니면 프로세스는 계속 수행될 수 있다.

 

3. semSignal :

                     - 세마포어 값을 증가시킨다.

                     - 만약 값이 양수가 아니면 semWait 연산에 의해 블록된 프로세스를 깨운다. (READY로)

 

---

이진 세마포어

 

struct binary_semaphore {
       enum (zero, one) value;
       queueType queue;
};
void waitB(binary_semaphore s)
{
       if (s.value == 1)
            s.value = 0;
       else
       {
            요청한 프로세스를 s.queue에 연결;
            요청한 프로세스를 블록상태로 전이시킴;
       }
}
void signalB(semaphore s)
{
       if (s.queue.is_empty( ))
            s.value = 1;
       else
       {
            s.queue에 연결된 프로세스를 큐에서 제거;
            프로세스의 상태를 실행가능으로 전이시키고 레디큐에 연결;
       }
}

1. 세마포어 초기화 : 이진 세마포어는 0이나 1로 초기화된다.

 

2. SemWaitB :

                    - 세마포어 값을 확인한다.

                    - 만약 값이 1이면, 값을 0으로 변경하고 프로세스는 계속 수행

 

3. SemSignalB :

                       - 블록되어있는 프로세스가 존재하는지 확인한다.

                       - 만일 블록되어 있는 프로세스가 존재하면 그 프로세스를 깨운다.

                       - 반면 블록되어 있는 프로세스가 존재하지 않으면 세마포어 값을 1로 설정한다.

 

 

이진세마포어는 일밤범용 세마포어보다 구현하기가 쉽다.

 

이녀석이고 저녁석이고 블록된 프로세스를 관리해야되므로 큐를 사용하는거다 FIFO

 

---

 

상호배제 세마포어

/* program mutualexclusion */

const int n = /* number of processes */;

semaphore s = 1;

void P(int i)

{

       while (true)

       {

            wait(s);

            /* critical section */;

            signal(s);

            /* remainder */;

       }

}

void main()

{

       parbegin (P(1), P(2), . . ., P(n));

}

 

각 프로세스에서는 임계영역에 들어가기 직전에 semWait(s)를 호출한다.

만일 세마포어 s의 값이 음수라면 프로세스는 불록된다.

만약 s의 값이 1이라면 1만큼 감소시키고 임계영역 안으로 들어간다.

 

세마포어를 이용한 상호배제

 

위 그림은 세마포어로 상호배제를 수행하는 과정 그림이다.

 

A, B, C는 각각의 프로세스이다.

 

얘들이 진입하면 s의값은 감소한다.

임계영역에 들어갔던 프로세스가 빠져나오면 s의값은 1이 증가한다.

블록큐에서 프로세스가 빠져나와 레디큐로 들어간다.

이 예제에선 ABC라는 세게의 프로세스는 lock이란 이름의 세마포어 변수에 의해 보호되는 공유자원에 접근한다

 

출처: Cheol's Blog