Semaphore란?

Semaphore란?

Semaphore는 간단하게 말하면 정수 하나라고 생각할 수 있다.

여기에 wait와 post 함수를 통해서 이 정수 값을 바꿈으로써 thread를 통제한다.

어떻게 정수값을 통해 thread를 관리하는지 알아보자.

 

Semaphore 사용법

Semaphore를 사용하기 위해서는 먼저 Semaphore 객체를 만들어주어야 한다.

객체를 만들어 준 뒤에는 init 함수를 통해 Semaphore 값을 초기화시킨다.

 

이 때, 첫번째 파라미터는 Semaphore 객체,

두번째 파라미터는 Semaphore를 사용할 범위 (0: 같은 process / 1: 다른 process),

세번째 파라미터는 Semaphore 값을 초기화 할 값이다.

 

객체를 초기화 했다면 이제 wait()와 post() 함수를 이용하여 Semaphore를 컨트롤하게 된다.

 

wait() 함수는 Semaphore 값을 1 감소시키고, Semaphore 값이 음수라면 대기한다.

post() 함수는 Semaphore 값을 1 증가시키고, 대기중인 thread가 있다면 깨운다.

 

그렇다면 wait()와 post() 함수를 어떻게 이용하는지 알아보자.

 

Binary Semaphore

Binary Semaphore란 1로 초기화한 Semaphore를 말하며, lock과 같은 역할을 할 수 있다.

Binary Semaphore의 wait()는 lock() 함수, post()는 unlock() 함수처럼 사용할 수 있다.

 

초기값이 1이므로,

wait()를 첫번째로 호출한 thread는 Semaphore 값을 0으로 바꾼 뒤 값이 음수가 아니므로 critical section에 진입한다.

뒤이어 다른 thread가 wait()를 호출하면 Semaphore 값이 0이 되므로 대기하게 된다.

그리고 첫번째로 진입한 thread가 post()를 호출하여 Semaphore 값을 증가시키고 대기중인 thread를 깨운다.

깨워진 thread는 Semaphore 값을 확인하여 음수가 아니라면 critical section에 진입한다.

 

그렇다면 초기값을 1보다 큰 수로 설정하면 어떻게 될까?

wait()를 호출한 순서대로 초기화한 값 만큼의 thread가 critical section에 진입하게 될 것이다.

이로써 우리는 초기화한 값을 통해 원하는 만큼의 thread를 특정 구역에 진입시킬 수 있게 할 수 있다.

 

Condition Variable using Semaphore

Semaphore는 lock 뿐만 아니라 condition variable로도 사용할 수 있다.

위의 예시는 Semaphore를 condition variable처럼 사용하여 thread_join()을 구현한 것이다.

이 코드가 정확하게 동작하려면 Semaphore 값을 몇으로 초기화해야 할까?

 

정답은 0이다.

0으로 초기화하게 되면 wait()를 호출한 parent thread는 Semaphore 값이 -1이 되어 대기하게 된다.

그리고 child thread에서 post()를 호출하면 Semaphore 값이 0이 되고 parent thread는 깨어나 코드를 진행하게 된다.

 

이제 이를 활용하여 대표적인 문제들을 몇 개 풀어보자.

 

The Producer/Consumer Problem

앞서 condition variable을 이용하여 풀었던 생산자/소비자 문제이다.

이를 Semaphore를 이용하여 해결해보자.

 

하나의 condition variable을 사용하면 문제가 발생하기 때문에

2개의 condition variable, 즉 2개의 Semaphore를 만들어 주었다.

 

그렇다면 각각의 Semaphore는 얼마로 초기화해야 할까?

 

생산자는 상품이 가득 차 있다면 생산할 수 없다.

소비자는 상품이 하나도 없다면 소비할 수 없다.

 

처음 시작할 때에는 상품이 없으므로 생산자는 생산을 시작해야 하고, 소비자는 소비할 수 없다는 점을 생각하면,

empty Semaphore는 상품을 생산할 수 있는 최대 갯수(MAX)로 초기화하고,

full Semaphore는 0으로 초기화해야 된다는 것을 알 수 있다.

 

그리고 이렇게 구현하게 되면 한가지 문제점이 있다.

생산과 소비 부분의 mutual exclusion이 보장되지 않는다는 점이다.

따라서 wait()과 post()의 바깥에 mutex라는 Binary Semaphore를 만들어 lock이 작동하도록 해주어야 한다.

 

Reader-Writer Locks

Reader-Writer Lock은 파일의 읽기 쓰기를 어떻게 통제해야 할 지에 관한 문제이다.

파일 읽기는 인원수에 상관없이 동시에 읽기가 가능하다.

하지만 쓰기는 읽는 사람이 없어야 하며, 오직 한명만 쓸 수 있다.

이를 Semaphore를 이용하여 구현해보자.

 

먼저 readers 변수를 통해 몇 명이 파일을 읽고 있는지 저장한다.

그리고 첫번째로 readlock 획득 요청이 들어오면(readers=1) writelock을 획득하여 아무도 쓸 수 없도록 한다.

이 후 모든 readlock이 반환되면(readers=0) writelock을 반환하여 쓰기가 가능하도록 하면 된다.

 

The Dining Philosophers

이 문제는 철학자들이 원형 식탁에 둘러앉아 식사를 할 때, 공평하게 음식을 먹기 위한 방법을 묻는 문제이다.

각각의 철학자들의 양 옆에는 포크가 하나씩 놓여져 있으며, 양 옆 2개의 포크를 모두 들어야 음식을 먹을 수 있다.

따라서 한 철학자가 음식을 먹기 위해 양 옆의 포크를 들면, 양 옆의 철학자는 음식을 먹을 수 없다.

 

이는 포크 2개를 집는 것을 lock, 음식을 먹는 것을 critical section으로 생각하면 효율적인 lock 분배에 대한 방법을 묻는 문제로 볼 수 있다.

 

그렇다면 이 문제를 풀기 위한 방법을 생각해보자.

 

단순하게 생각해서 철학자가

1. 왼쪽에 포크가 있다면 포크를 든다.

2. 오른쪽에 포크가 있다면 포크를 든다.

와 같이 행동하도록 해보자.

 

얼핏 보면 문제가 없을 것 같지만 모든 철학자가 동시에 행동을 시작한다면,

모두 왼쪽 포크를 들고, 오른쪽 포크가 내려놓길 기다리게 된다.

하지만 아무도 식사를 할 수 없기에 내려놓아지는 포크는 없고, 모두가 식사를 할 수 없다.

 

그렇다면 어떻게 해야 할까?

 

정답은 간단하다. 철학자 한명은 오른쪽 포크를 먼저 들게 하면 된다.

 

모든 철학자들이 왼쪽 포크를 먼저 들지만, P4는 오른쪽을 먼저 든다고 생각해보자.

P0 철학자부터 P4 철학자까지 모두 포크를 들었을 때,

P0가 자신의 왼쪽 포크(f0)를 들었으므로 P4는 오른쪽 포크(f0)가 없으니 기다리게 된다.

그러면 자연스럽게 P3는 자신의 오른쪽 포크를 들 수 있고, 음식을 먹을 수 있게 된다.

P3는 양쪽 포크를 내려놓을 것이고 이제 P2가 음식을 먹을 수 있게 된다.

이어서 P2, P1, P0까지 음식을 먹고 마지막으로 P4까지 모든 철학자가 음식을 먹을 수 있다.