[OS] 8-1. 뮤텍스와 세마포어

뮤텍스 (Mutex)

Critical Section Problem을 해결하기 위한 소프트웨어 도구 중 가장 단순한 방법으로 뮤텍스가 있습니다. 뮤텍스는 lock이 하나만 존재할 수 있습니다. 이미 하나의 프로세스가 Critical Section에 진입했다면 다른 프로세스들은 Critical Section에 진입할 수 없습니다.

lock을 걸고 푸는 동작은 하드웨어 방식처럼 Atomic하게 수행됩니다.

acquire()
{
	while (!available);
    available = true;
}

release()
{
	available = true;
}

do
{
	acquire();
    // critical section
    release();
} while(true);

이 방식은 Mutual Exclusion, Progress, Bounded Waiting 모두 만족합니다. 하지만 프로세스들이 Critical Section 진입을 대기하면서 계속 자원을 사용하는 문제가 있습니다.

---

세마포어 (Semaphores)

여러 프로세스나 스레드가 Critical Section에 진입할 수 있는 방식입니다.

세마포어는 카운터를 이용하여 동시에 자원에 접근할 수 있는 프로세스를 제한합니다. 주로 S라는 정수형 변수로 나타내며 사용 가능한 자원 개수를 의미합니다.

이 변수는 오직 두 개의 Atomic한 연산을 통해서 접근할 수 있습니다. 한 프로세스가 이 변수를 수정할 때 다른 프로세스가 동시에 같은 변수를 수정할 수 없습니다.

세마포어 변수를 0 또는 1만 사용하면 이진 세마포어라고 하며 뮤텍스와 동일한 역할을 합니다.

wait(S) // P(S)
{
	while (S <= 0);
    S--;
}

signal(S) // V(S)
{
	S++;
}

do
{
	P(mutex);
    // critical section
    V(mutex);
    // remainder section
} while(true);

이 방식도 결국 Busy Waiting 문제가 발생합니다. 세마포어는 이를 해결하기 위해 Block & Wakeup 방식을 사용합니다.

이 방식은 Critical Section 진입에 실패한 프로세스를 기다리게 하지 않고 Block시킨 뒤 Critical Section에 자리가 나면 다시 Wakeup시켜줌으로써 Busy Waiting 문제를 해결합니다.

일반적으로 Busy Waiting이 비효율적이지만 Critical Section이 매우 짧은 경우 Block & Wakeup 방식이 비효율적일수도 있습니다.

Block & Wakeup 방식은 다음과 같이 구현합니다.

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

void wait(semaphore S)
{
	S.value--;
    if (S.value < 0)
    {
    	// add this process to S.L;
        block();
    }
}

void signal(semaphore S)
{
	S.value++;
    if (S.value <= 0)
    {
    	// remove a process P from S.L;
        wakeup(P);
    }
}

value는 세마포어 변수, L은 block된 프로세스들이 기다리는 Queue입니다.

• Block
  wait에서 value를 감소시키고 만약 value가 0보다 작으면 이미 Critical Section에 어느 프로세스가 존재한다는 의미이므로 현재 프로세스는 Critical Section에 진입하지 못하게 해야 합니다. 현재 프로세스를 L에 추가해줍니다.
• Wakeup
  signal에서 value를 증가시키고 만약 value가 0 이하면 Critical Section에 진입하려고 대기하는 프로세스가 L에 남아있다는 의미이므로 L에서 프로세스를 하나 꺼내 Critical Section에 진입할 수 있게 합니다.