Synchronization with OS Support : Semaphore

Semaphore

Semaphore는 synchronization primitive이다.

일반적인 동기화 문제를 해결하는데 primitive 한 수단이다.

 

Bakery 알고리즘이나 peterson의 알고리즘은 synchronization 문제를 해결할 수는 있으나 알고리즘이 복잡하기 때문에 흔히 사용되지는 않는다.

일반적인 synchronization 문제의 경우 semaphore을 이용해서 해결한다.

 

APIs

Semaphore는 정수형 변수로, 운영체제가 특별하게 보호하는 변수이다.

때문에 임의로 접근하지 못하고 운영체제가 제공하는 api를 이용해서 접근해야 한다.

이런 api는 atomic하게 동작하며, 작동 중에는 다른 함수가 개입하지 못한다.

• wait(S)
  • semaphore가 양수이면 1 감소한다.
  • semaphore가 양수가 아니면 기다린다.
• signal(S)
  • semaphore를 1 증가시킨다.

 

사용

Shared datasms <pre>semaphore S</pre>이고, 초기값은 1이다.

 

Semaphore의 이용은 아래와 같이 하면 된다.

Mutual exclusion, process, bounded waiting을 모두 충족할 수 있다.

do {
	// entry section
	wait(S);
    
    // critical section
    ...
    
    // exit section
    signal(S);
    ...
	
} while(1);

 

Atomicity and Bounded Waiting

OS는 semaphore S에 대한 접근을 atomic 하도록 보장한다.

또한 운영체제는 프로세스가 wait() 함수로부터 return 하는 순서를 조절함으로써 bounded waiting을 보장해준다.

 

따라서 프로그래머는 그냥 사용하면 된다.

 

Semaphore as a General Synchronization Tool

Semaphore는 critical section 문제를 넘어서서 일반적인 synchronization 문제를 해결할 수 있다.

 

프로세스의 실행 순서를 강제할 수 있다.

A를 실행한 후 B를 실행하도록 강제하는 것은 다음과 같다.

semaphore flag의 초기값을 0으로 설정하면 A를 실행 한 후 1이 되어야만 B를 실행할 수 있게 된다.

 

Issue

Semaphroe를 사용할 때 deadlock과 starvation의 문제를 조심해야 한다.

 

Deadlock은 어떤 프로세스도 progresss를 만들지 못하는 현상이다.

2개 이상의 semaphore를 사용할 때 발생한다.

 

Deadlock에 빠졌을 때 프로세스는 계속해서 실행되지 못하는 starvation 된다.

 

---

Semaphore의 구현

운영체제가 내부적으로 semaphore를 구현하는 방식에는 두 가지가 있다.

• busy waiting semaphore
• blocking semaphore

 

Busy Waiting Semaphore

Spin lock 이라고도 한다.

특정 프로세스가 critical section에 들어갈 수 없는 상황이면 loop에 빠뜨린다.

 

그런데 이는 해당 시간 동안 CPU가 다른 작업을 하지 못하게 하므로 상대적으로 CPU 시간이 낭비된다.

짧은 시간 안에 일이 일어날 경우 유용한 방법이다.

 

Semaphore의 값이 0과 1 사이에서 변화한다.

(blocking semaphore는 음수가 될 수 있다.)

 

Blocking Semaphore

CPU 시간의 낭비를 해결하는 방법이다.

 

프로세스를 block/wake up 함으로써 busy waiting에서의 loop를 대신한다.

• block : 프로세스의 상태를 running → waiting 으로 만듦
• wake up : 프로세스의 상태를 waiting → running 으로 만듦

 

현재 critical section에 들어가고 싶어하는 프로세스들을 기억해야 한다.

이를 위해서 linked list의 형태로 프로세스들을 유지한다.

typedef struct {
	int value;
    struct process *L; // critical section에 들어가고자 하는 프로세스들을 기억
} semaphore;

 

구현

Blocking semaphore는 다음과 같이 구현할 수 있다.

loop를 없앰으로써 CPU 시간 낭비를 방지한다.

 

이미 critical section에 들어간 프로세스가 존재한다면, 이후의 프로세스들은 semaphore를 감소시키고 linked list에 추가된다.

critical section에 들어갔던 프로세스가 나왔는데, 누군가 critical section에 들어가기위해서 대기하고 있으면 linked list에서 꺼낸다.

 

Semaphore의 값이 음수 값이 될 수 있다.

(busy waiting semaphroe는 0과 1 사이에서 움직인다.)

음수값의 크기는 현재 critical section에 들어가기 위해서 대기하는 프로세스의 수를 의미한다.

 

waiting process의 list(linked list)는 FIFO queue를 이용하기 때문에 bounded waiting을 보장해준다.

나보다 앞선 프로세스들을 수행하면 되기 때문에 upper bound는 n-1이 된다.

 

---

Sempahore의 사용

Semaphore의 사용 측면에서 2가지로 구분할 수 있다.

• Binary semaphore
  • semaphore의 값이 1을 넘지 않는다.
  • 초기값은 주로 1로 설정한다.
  • semaphore의 값이 0과 1 사이에서 움직인다.
  • 음수는 그저 critical section 대기하는 프로세스의 수로 취급한다.
• Counting semaphore
  • semaphore의 값이 1을 넘을 수 있다.
  • semaphore의 초기값은 동시에 critical section에 들어갈 수 있는 프로세스의 수를 의미한다.
  • 동일한 유형의 resource의 instance가 여러 개가 있는 경우 사용한다.
    • 예 : 프린터가 3개인 경우 3개의 application이 동시에 접근이 가능하다.
  • 여러 개의 binary semaphore를 이용해서 구현이 가능하다.