[운영체제] 뮤텍스와 세마포어

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이 때, 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

이를 위해 나온 것이 세마포어이다.

세마포어 : 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

 

임계 구역(critical section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때에는 다른 프로세스가 접근하지 못하도록 해야 한다.

 

세마포어

자바를 통해 세마포 구조(block-wakeup 방식)를 간단히 살펴보면 아래와 같다.

class Semaphore {
  int value;      // number of permits
  Semaphore(int value) {
    // ...
  }
  void acquire() {
    value--;
    if (value < 0) {
      // add this process/thread to list
      // block
    }
  }
  void release() {
    value++;
    if (value <= 0) {
      // remove a process P from list
      // wakeup P
    }
  }
}

• value는 권한의 개수 등으로 생각한다.
• 위 코드에서 acquire() 는 value값을 감소시키고 만약 value값이 0보다 작으면 이미 해당 임계구역에 어느 프로세스가 존재한다는 의미이므로 현재 프로세스는 접근하지 못하도록 막아야한다. 이를 list라는 기다리는 줄에 추가한 뒤 block을 걸어준다. (list는 일반적으로 큐로 되어있다.)
• release() 는 value값을 증가시키고, 만약 value값이 0보다 같거나 작으면 임계구역에 진입하려고 대기하는 프로세스가 list에 남아있다는 의미이므로 그 중에서 하나를 꺼내어 임계구역을 수행할 수 있도록 해주어야 한다.

 

1) Mutual exclusion (상호 배제)

• sem.value = 1 (초기값을 1로 세팅)
• 만약 A,B 두개의 스레드의 코드가 아래와 같다고 하면
  • sem.acquiere()
  • balance = balance + account
  • sem.release()
• 스레드 A가 먼저 실행이 된다고 한다면 먼저 acquire()을 실행해서 value가 0이 된다.
• 0 미만이 아니라서 acquire()내부의 if문을 만족 못하므로 block되지 않고 Critical - Section 안으로 들어와 balance를 업데이트 할 수 있다.
• 공교롭게 update 하는 도중에 context swiching이 발생했다고 하자(update 코드는 어셈블리 언어로 여러줄이라 중간에 context swiching 가능)
• 스레드 B가 돌면서 acquire()실행해서 value가 -1이 된다.
• if 문을 만족하며 B는 critical section으로 못 들어가고 세마포 큐 안에 갖힌다.
• 다시 순서가 돌아와 A가 실행되고 release()를 호출해 value가 다시 0이 된다.
• release() 내에 조건문이 있는데 만약 +1 했는데 value가 0 이하면 세마포 큐안에 뭔가가 잡혀있다는 뜻이기 때문에 B를 꺼내서 ready queue로 보내주고 다시 cpu에 의해 실행되기를 기다린다.
• cpu가 다시 B를 실행되면 critical section으로 들어간다.

세마포는 이렇게 일반적으로 Mutual exclusion을 위해 사용된다.

 

2) 순서 제어 (Ordering)

세마포는 mutual exclusion뿐 아니라 ordering을 하기 위해서도 사용한다. 즉, 프로세스의 실행 순서를 원하는 순서로 설정 할 수 있다.

예를 들어, 프로세스가 P1, P2 두 개가 있다고 가정하자. 원하는 순서는 P1, P2 순으로 실행하기를 원한다. 그러면 아래와 같이 설정해줄 수 있다.

먼저, 세마포로 감싼 구역에 들어갈 수 있는 프로세스 개수를 정하는 value값을 0으로 설정한다.(sem value = 0;)

 

1. P1이 먼저 실행된 경우

• Section 1 이전에 아무런 동작이 없으므로 바로 수행한다.
• sem.release() 를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 프로세스를 깨워주는데 현재에는 큐에 프로세스가 없으므로 아무 동작도 하지 않는다.
• P2가 실행된다.
• P2의 sem.acquire() 를 만나면 현재 value값은 1이고 이를 1 감소시키면 0이 된다. value = 0이면 block을 하지 않으므로, 무사히 Section 2가 수행된다.

 

2. P2가 먼저 실행된 경우

• Section 2 이전에 sem.acquire() 가 있으므로 이를 수행하는데, 현재 value값은 0이고 이를 1 감소 시키면 -1 이 된다. value값이 음수면 해당 프로세스를 block시킨다.(세마포 큐에 삽입한다.)
• P1이 실행되면 Section 1이 바로 수행된다.
• sem.release() 를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 P2 프로세스를 깨워준다.(현재 value = 0)
• P2의 Section 2가 수행된다.

위에서 두 가지 경우를 살펴보았듯이, P1, P2 둘 중 어느 것을 먼저 실행하여도 결과적으로 P1 -> P2 순서로 수행하는 것을 알 수 있다.

 

 

- Counting Semaphores, Binary Semaphore

세마포어는 크게 Counting Semaphores, Binary Semaphore 2종류가 있다. 카운팅 세마포어는 세마포어의 카운트가 양의 정수값을 가지며, 설정한 값만큼 쓰레드를 허용하고 그 이상의 쓰레드가 자원에 접근하면 락이 실행된다. 바이너리 세마포어는 세마포어의 카운트가 1이며 Mutex처럼 사용될 수 있다.(뮤텍스는 절대로 세마포어처럼 사용될 수 없다.)

 

- (보충) 세마포 구현방식 busy-waiting, block-wakeup 방식

acquire(S) { 
	while S <=0; // 아무것도 하지 않음 (반복문) 
    S--; 
} 

release(S) { 
	S++; 
}

최초 제시된 세마포 구현은 바쁜 대기(busy waiting)를 이용한 방법이다.

이 방법은 임계 구역에 들어갈 수 있을 때까지 빈 반복문을 수행하기 때문에, 단일 처리기 다중 프로세스 환경에서 처리기 효율이 떨어진다. 또한 대기 중인 프로세스들 중 어느 것을 먼저 임계 구역에 진입시킬지를 결정할 수 없다.

 

최초 방법의 단점을 보완한 방법으로서 재움 큐를 활용하여 프로세스를 재우는 위에서 소개한 block-wakeup 방식이다.

acquire(S) { 
	S--; 
    if S < 0 
    	// 이 프로세스를 재움 큐에 추가 (잠 듦) 
        block() 
} 
    
release(S) { 
	S++; 
    if S <= 0 
    // 재움 큐로부터 프로세스를 제거 (깨어남) 
    	wakeup(P) 
}

block과 wakeup은 다음과 같이 동작한다.

• block() : 커널은 block을 호출한 프로세스를 중지 시키고 이 프로세스 PCB를 semaphore에 대한 wait queue에 넣는다.
• wakeup(P) : block된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮긴다.

 

뮤텍스 (Mutex)

뮤텍스는 세마포어와 마찬가지로 병행 처리를 위한 동기화 기법 중 하나이다. 바이너리 세마포어와 같이 초기값을 1과 0으로 가진다. 임계영역에 들어갈 때 락(lock)을 걸어 다른 프로세스(혹은 쓰레드)가 접근하지 못하도록 하고, 임계영역에서 나와 해당 락을 해제(unlock) 한다.

간단히 코드로 보자면 다음과 같다.

mutex = 1;

void lock () {
	while (mutex != 1) {
    	/* mutex 값이 1이 될 때까지 기다립니다.*/
    }
    /* 이 구역에 도착했다는 것은 mutex 값이 1이라는 것입니다.
       따라서 이제 뮤텍스 값을 0으로 만들어 다른 프로세스(혹은 쓰레드)가 접근하지 못하도록 막아야 합니다.
    */
    mutex = 0;
}

void unlock() {
	/* 임계 구역에서 나온 프로세스는 다른 프로세스가 접근할 수 있도록 락을 해제합니다.*/
	mutex = 1;
}

 

뮤텍스는 오직 하나의 쓰레드만이 동일한 시점에 뮤텍스를 얻어 임계 영역(Critical Section)에 들어올 수 있다. 그리고 오직 이 쓰레드만이 임계 영역에서 나갈 때 뮤텍스를 해제할 수 있다.

이러한 이유는 뮤텍스가 1개의 락만을 갖는 메커니즘이기 때문이다.

뮤텍스 메커니즘의 특징을 정리했다.

• Atomicity - mutex 잠금(lock)은 최소단위 연적(atomic operation) 으로 작동한다. 이 말의 뜻은 하나의 쓰레드가 mutex 를 이용해서 잠금을 시도하는 도중에 다른 쓰레드가 mutex 잠금을 할수없도록 해준다는 뜻이다. 한번에 하나의 mutex 잠금을 하도록 보증해준다.
• Singularity - 만약 스레드가 mutex 잠금을 했다면, 잠금을 한 쓰레드가 mutex 잠금을 해제 하기 전까지 다른 어떠한 쓰레드도 mutex 잠금을 할수 없도록 보증해준다.
• Non-Busy Wait - 바쁜 대기 상태에 놓이지 않는다는 뜻으로, 하나의 쓰레드가 mutex 잠금을 시도하는데 이미 다른 쓰레드가 mutex 잠금을 사용하고 있다면 이 쓰레드는 다른 쓰레드가 락을 해제하기 전까지 해당 지점에 머물러 있으며 이 동안은 어떠한 CPU 자원도 소비하지 않는다 (이를테면 sleep).

 

뮤텍스와 세마포어 차이

• 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스(또는 쓰레드)가 접근할 수 있다. 반면에 뮤텍스는 오직 1개만의 프로세스(또는 쓰레드)만 접근할 수 있다.
• 현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있다. 하지만 뮤텍스는 락(lock)을 획득한 프로세스가 락을 해제해야 한다.