Semaphore

Semaphore 초기화

Semaphore는 라이브러리로 제공이 되며 초기화가 굉장히 중요하다.

초기값은 sem_init 의 세 번째 parameter가 된다. (예시에서는 1)

 

Semaphore의 2가지 Method

sem_wait는 P 연산(네덜란드어로 검사하다)이라고도 하며 positive number 일 때는 value를 감소를 시키고 negative number 일 때는 더 이상 감소 시킬 수 없기 때문에 sem_wait를 호출한 시점에서 sleep 상태로 진입하게 된다.

 

sem_post는 V 연산(네덜란드어로 증가하다)이라고도 하며 value를 돌려놓는 일 즉, semaphore value를 증가시킨다.

또한 누군가 wait 하고 있다면 하나를 깨운다.

 

wait 하고 있는 대상을 깨운다는 것을 좀 더 자세히 알아보면

Semaphore의 구조

Semaphore 내부에는 wait queue 가 존재하는데 이 큐 안에 만약 wait 하고 있는 대상이 존재한다면, 그 대상을 Queue에서 제거하고 Ready Queue로 옮겨준다. 이 과정을 '깨운다' 라고 한다. 그러면 나중에 Scheduler가 Ready Queue에서 대기하고 있는 Thread 중에 하나를 선택해서 스케쥴링을 하게 되는 것이다.

 

정리하면 sem_post는 value를 증가 시키고, 누군가 기다리고 있다면 wake one을 한다.

Semaphore의 용도

Semaphore를 이용한 Lock

Semaphore를 이용해서 Lock을 만들 수 있다.

이 때는 초기값을 1로 해야한다.

Semaphore value가 0 또는 1로 지정될 수 있기 때문에 Binary Semaphore 라고 한다.

 

Lock을 얻는 것은 sem_wait(&m) 가 되며 value를 감소시키는 P 연산을 말하고 감소 시킬 value가 없다면 wait 한다.

초기값을 앞에서 1로 셋팅 했기 때문에 P 연산을 여러 Thread에서 했다면 1개만 Lock을 얻고 나머지는 negative number로 표현이 될 것이다.

 

Unlock을 하는 것은 sem_post(&m) 가 된다. 즉 value를 다시 증가시켜서 원래대로 되돌려놓는 것을 말한다.

 

Single Thread 동작 예시

1로 초기화 -> sem_wait()를 통해 lock을 얻고 value가 0으로 감소 -> critical section -> unlock을 위해 sem_post 호출 -> value가 다시 1로 증가, 깨울 대상이 없음 (Single Thread 에서의 동작)

 

Mutil-Thread 동작 예시

초기값 1 -> sem_wait() 를 통해 lock을 얻고 value가 0으로 감소 -> critical section 진입 -> 일을 다 끝내지 못하고 Interrupt 가 걸림, Thread 1으로 Context Switching (Run->Ready) -> Thread 1 실행 -> sem_wait()을 통해 lock을 얻으려고 했지만 감소를 했더니 negative number가 됐다. (0 -> -1) -> 따라서 Semaphore Waiting Queue에 Thread1을 등록시키고 Thread 1은 sleep 하게 된다. (Run->Sleep) 다시 T0로 Context Switching -> critical section 이어서 진행, 이 과정은 mutual exclusive 하게 진행 됐다. (Thread 1에서 critical section 에 진입을 하지 못했기 때문, 즉 sleep 했다) -> sem_post()를 통해 unlock을 해서 value를 증가시키고 기다리고 있는 T1 Thread를 깨운다. (Waiting Queue에서 제거하고 Ready Queue로 옮긴다, 따라서 Thread1은 Sleep->Ready) -> Interrupt 발생, T1으로 Switching -> wait() return 하는데 이 때 semaphore value를 얻었고 critical section으로 진입한다. -> sem_post()를 통해 unlock, value 증가 -> 끝.

 

과정이 길고 복잡해보이지만 천천히 한 번 따라가보자.

 

위 예시가 갖는 의미는 Interrupt 발생으로 인해 critical section에서 처리하고 있던 일이 중간에 끊겨도 mutual exclusive 하게 동작한다는 것이다. 다시 말해 Binary Semaphore를 이용해서 Lock으로 사용 할 수 있다는 것을 알 수 있다.

Semaphores For Ordering

Thread가 여러 개 있을 때 이들은 서로 임의의 순서로, 비결정적으로 실행이 되는데, 필요에 따라 이들은 순서에 맞춰서 결정적으로 실행될 필요가 있다. 이 때 Semaphore를 활용하는 방법이 존재한다.

 

이 경우 semaphore의 초기값은 0

main 함수에서 Thread를 하나 생성을 했고 (병행적으로) 이 Thread는 child를 실행하도록 했다.

위 코드의 의도를 보면 child가 먼저 실행되기를 원한다고 볼 수 있다.

main 함수에서 생성한 Thread는 child를 실행하도록 했고 이후 main은 child가 끝날 때까지 기다리도록 했기 때문.

child에서는 child에서의 일 (예시에서는 출력)이 끝난 다음 sem_post를 통해 알려주면 main thread에서 이후의 작업을 이어서 한다.

정리하면 기다리는 쪽: main, sem_wait(), P 연산 이고 신호를 보내서 깨우는 쪽: child, sem_post(), V 연산 이다.

 

우리가 원하는 순서는 parent가 시작, child 가 일을 하고 parent가 일을 끝내는 것.

순서에 집중하면서 아래 2개의 케이스를 살펴보자.

 

첫 번째 케이스

이 Method와 함께 보면 이해하는데 도움이 된다.

첫 번째 케이스를 보면 Parent에서 Child Thread를 생성하고 sem_wait()를 호출, value를 감소시켜서 초기값 0 인 상태에서 value는 -1이 되었고 sem<0 이기 때문에 sleep 상태로 들어가게 된다. 이 때 Parent는 Semaphore의 Waiting Queue에 들어간다. 이후 Context Switching을 통해 Child Thread로 가게 되고 child는 자기 할 일(print)을 하고 sem_post()를 호출, semaphore value를 증가시키고(-1 -> 0) waiting queue에 있는 Parent를 깨운다. (Ready Queue로 옮김) -> 이후 Interrupt가 걸렸다고 가정 -> Parent로 다시 넘어와서 sem_wait()를 return 하고 이후 Parent의 할 일(print)을 하게 된다.

 

두 번째 케이스

두 번째 케이스는 Parent에서 Child Thread를 create를 통해 생성하자마자 Interrupt가 걸려서 Child로 넘어가게 됐다. Child는 자기 할 일을 하고 끝났음을 알려주기 위해 sem_post() 를 호출해서 value를 increment 한다. (0 -> 1) 이어서 깨울 대상을 확인했지만 아무도 없어서 그냥 넘어간다. semaphore value만 증가시키고 끝. 이후 Interrupt가 발생해서 다시 Context Switching이 되면, Parent가 Run 하는데 우선 sem_wait()를 호출, semaphore value를 감소 시킨다. (1 -> 0) 하지만 방금 전 Child가 value를 증가 시켜 놓았기 때문에 감소를 해도 negative number로 떨어지지 않는다. 따라서 Sleep 상태로 들어가지 않는다. 그래서 Parent가 쭉 진행되면서 sem_wait()를 return 하고 Parent의 할 일을 한다.

 

이 두 가지 케이스가 Semaphore를 이용해서 Ordering을 하는 방법에 대한 예시이다.