Process Synchronization 3.

게시: February 04, 2022

본 포스팅에서는 앞선 포스팅에서 다룬 Process synchronization 문제를 해결하기 위한 방법들을 추상화한 방법으로 중요한 개념인 세마포어(Semaphore)에 대하여 다룬다.

Semaphore란 무엇인가?

사전적 의미로 수기 신호라는 뜻으로 세마포어(Semaphore)는 컴퓨터 자원의 신호등의 역할을 한다. 세마포어는 보다 구체적으로 두 가지 역할을 하는데 Mutex(Mutual Exclusion) 문제를 해결하고 어떠한 공유 자원을 획득하고 반납하는 작업을 처리해준다.

이해에 주의해야할 점은 Process synchronization을 해결하는 소프트웨어적인 방법처럼 어떠한 알고리즘의 구현(Implementation)을 말하는 것이 아니라 추상적인 개념을 의미한다는 점이다.

세마포어는 변수 S(Semaphore)와 자원을 획득하는 P(), 자원을 반납하는 V() 연산으로 구성된다.

P(S) 하면 S가 0 이하인 동안에는 아무 것도 하지 않고 대기(Wait)하고, S가 1 증가하면 S를 1 감소(S--)시키고 자원을 획득한다. 자원 사용이 끝나면 V(S)하여 S를 1 증가(S++)시키고 자원을 반납한다.

세마포어는 커널에서 지원해야 하는 추상적 의미이기 때문에 세마포어가 지원되면 프로그래머 입장에서는 P(), V() 연산만 구현해주면 되고, 해당 연산을 어떻게 구현할지는 시스템에서 고민할 몫이다.

Semaphore의 구성

변수 S(Semaphore)와 P(), V() 연산으로 구성되며 두 연산은 Atomic하게 수행된다고 가정한다.

1. Synchronization Variable S

Integer 타입의 변수로 자원의 갯수를 의미한다. 예를 들어 S = 5 이면 자원을 5개의 프로세스가 동시에 자원을 가져갈 수 있고, S = 10이면 10개의 프로세스가 동시에 자원을 가져갈 수 있다.

2. P()

공유 자원을 획득하는 과정이다. 예를 들어 S = 5인 상황에서 P(S)하면 S = 4가 되고 한 번 더 P(S)하면 S = 3이 된다. 이를 Pseudocode로 나타내면 아래와 같다.

while (S ≤ 0) do no-operation;  /* i.e. wait */
S--;

S가 Positive인 경우에만 Decrement(S--) 및 Enter하고 그렇지 않으면 S가 Positive 될 때 까지 기다린다. 만약 자원을 내놓는 프로세스가 없어서 S = 0가 유지된다고 해도 계속 기다린다.

3. V()

공유 자원을 반납하는 과정이다. 예를 들어 S = 4인 상황에서 V(S)하면 S = 5가 된다.

S++;

Critical Section 문제에 적용하면

S가 1인 경우 Lock/Unlock 하는 것이라고 볼 수 있다.

semaphore mutex = 1;  /* 하나의 Process만 Critical section에 들어갈 수 있게 1로 초기화. */

do {
    P(mutex);         /* If positive, then decrement & enter section, otherwise wait. */
    critical section
    V(mutex);         /* Increment semaphore */
    remainder section
} while (1);

먼저 한 번에 하나의 프로세스만 Critical section에 진입할 수 있도록 semaphore형 mutex 변수를 mutex = 1로 초기화한다. 이후 P(mutex)하여 mutex가 양의 정수가 아니면(mutex ≤ 0) 대기하고 그렇지 않으면 S를 1만큼 감소(S--)시키고 Critical section에 진입한다.

Critical section에서 빠져나오면 V(mutex)하여 S를 1만큼 증가(S++)시켜 자원을 반납한다.

Busy waiting 방식의 한계

세마포어를 적용하더라도 Busy waiting(Spin lock) 문제는 해결되지 않는다. 자원이 없을 때 P(S) 해봤자 자원이 없기 때문에 while 안에서 CPU 할당시간을 다 쓰고 CPU를 반납해야 하기 때문이다.

Block & Wake-up Implementation (Sleep Lock)

세마포어를 Busy-waiting 방식으로 구현하지 않고 Block & Wake-up 방식으로도 구현할 수 있다. Block & Wake-up 방식으로 세마포어를 다음과 같이 정의할 수 있다.

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

여기서 value는 Integer 타입의 세마포어 변수를 의미한다. *L은 Block(Sleep)된 세마포어 연결을 위한 Queue이다. Block & Wake-up 방식은 S를 획득할 수 없는 상황이면 프로세스를 Block시키고 누군가 S를 반납하면 Blocked 프로세스를 Wake-up 시킨다.

Resource waiting queue-1 — 자원을 쓸 수 없으면 while문 안에서 CPU쓰지 않고 Blocked 되어 Resource queue에서 기다린다.
마치 CPU를 쓰기 위해 프로세스 상태가 Blocked 되어 Ready queue에 들어가는 것과 같다.

Block

Block을 호출한 프로세스를 커널이 Suspend 시킨다.
이 프로세스의 PCB를 S에 대한 Waiting Queue(*L)에 넣는(매달아 둔)다.

P():  S.value--;
      if (S.value < 0)
      {  add this process to S.L;  /* Prepare to enter */
         block;                    /* Oops! negative. I can't enter => block */
      }

Resource waiting queue-2 — 자원을 쓸 수 없는 상황이면 while문 안에서 기다리지 않고 queue에 들어간다.

Wake-up

누군가 S를 반납해서 차례가 오면 Block된 프로세스 P를 Wake-up시킨다.
해당 프로세스의 PCB를 Ready queue로 옮긴다.

S():  S.value++;
      if (S.value ≤ 0)
      { remove a process P from S.L;
        wakeup(P);
      }

여기서 주의할 점은 Wake-up할 때는 S.value가 0 이상인 경우가 아니라 0 이하인 경우라는 점이다.

누군가를 깨워야 하는 상황은 누군가가 잠들어 있는 상태에서만 필요한 동작이다. 만약 S가 양의 정수라면 잉여 자원이 있다는 뜻이므로 굳이 Wake-up문으로 들어갈 필요없이 바로 자원을 가져다 쓰면 되기 때문이다.

또한 누군가 Block될 때는 반드시 S를 1만큼 감소(S--)시키고 잠들기 때문에 누군가를 깨워야 하는 상황은 항상 S가 0 이하여야만 한다. 따라서 Wake-up 조건이 만족되는 상황은 항상 S가 0 이상이 아닌 0 ㄹ이하인 상황이다.

이와 같이 Block & Wake-up 방식에서 변수 S는 Busy waiting 방식처럼 같이 자원의 수를 나타내는 변수가 아니라 누군가를 Wake-up 해야 하는지 상태인지 아닌지 확인하는 변수이기 때문에 조건식에서 S를 체크하는 비교식에 주의할 필요가 있다.

Which Is Better?

보통 자원을 얻을 수 없는 상황이면 굳이 while문 안에서 대기하면서 CPU 타임을 쓰지 않고 CPU를 반납하고 Resource queue에 들어가는 Block & Wake-up이 더 효율적이다. Critical section이 어느 정도 이상이 되면 필수적으로 사용한다.

다만 Block & Wake-up 방식은 Busy waiting보다 O/H가 크기 때문에 Critical section이 매우 짧은 경우에는 Busy waiting 방식이 더 효율적일 수 있다.

Two Types Semaphores

Binary Semaphore (mutex)

0 또는 1 값만 가질 수 있는 세마포어이다.
주로 Mutual exclusion(Lock/Unlock)에 사용한다.

Counting Semaphore

자원이 여러 개 있어서 여분의 자원이 있는 경우 가져다 쓸 수 있는 것을 말한다.
도메인이 0 이상인 임의의 값이다.
주로 Resource counting에 사용한다.

Semaphore 사용시 주의사항

교착 상태(Deadlock)와 기아 현상(Starvation)에 주의해야 한다.

Deadlock

2개 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상이다.

예를 들어 HDD S에 있는 데이터를 HDD Q에 복사해야 한다고 가정하자. 이러면 HDD S, Q 모두 획득하는 조건을 충족해야 해당 작업을 수해하고 자원(HDD S, Q)를 반납할 것이다.

이러한 작업을 P₀ 도 하고 P₁ 도 수행한다고 하고 세마포어 변수는 프로세스 하나만 동시에 사용할 수 있는 mutex한 변수라고 가정하자.

P₀ 가 먼저 CPU를 얻고 P(S)로 S를 얻고 CPU를 빼앗기면 P₁ 은 S를 얻을 수 없기 때문에 Q 획득 후 S를 기다리고, 이후 P₀ 도 Q를 기다리게 되면서 영원히 조건이 충족되지 않는 상태에 빠지게 된다.^[1] 이를 교착 상태(Deadlock)라고 한다.

Deadlock case — 서로 상대의 자원을 얻기 위하여 무한히 대기하게 된다.

이를 해결하려면 자원을 획득하는 순서가 항상 같도록 프로그래밍해야 한다.

아래 그림과 같이 항상 S를 먼저 얻고 Q를 획득하게 하면 P₁ 는 자기 차례에서 S를 얻을 수 없기 때문에 B도 획득하지 않고 CPU를 P₀ 에게 넘겨주게 된다. 이후 P₀ 는 Q를 얻고 작업을 처리할 수 있게 되어 교착상태에 빠지지 않게 된다.

Deadlock solution — 나중에 시작한 프로세스는 이미 선행 자원을 선점당했기 때문에 더 이상 진행되지 않는다.

Starvation

Infinite blocking 되는 현상을 말한다. 특정 프로세스들만 자기들끼리 자원을 공유하면서 다른 특정 프로세스에게는 영원히 자원이 가지 못하는 상황을 의미한다. 이는 CPU 스케줄링의 우선순위 큐처럼 시간이 지남에 따라 우선순위를 높여주는 방법으로 해결할 수 있다.

각주

1 : 일종의 Starvation으로 볼 수도 있다.

Reference

반효경, “반효경 [운영체제] 13. Process Synchronization 2” KOCW. 2014년 4월 4일. video, http://www.kocw.net/home/cview.do?lid=02fbc3fd5cb74e97

OS 시리즈 모두보기 (펼치기)

Twitter Facebook LinkedIn

Seungho Jeong