저번엔 Low-level, 즉 OS단계에서 사용하는 synchronization 방식을 알아봤으니 이번엔 Application단계의 synchronization 방식인 Semaphore, Mutex lock, Monitor방식을 알아볼 것이다.
참고로 Application단에서의 synchronization 구현도 결국 OS가 제공한다.
OS단에서도 critical section문제가 발생할 것이므로,
spin lock 또는 disabling Interrupt 또한 함께 사용될 것이다.
1. Semaphore
semaphore방식에는 counter라는 변수가 존재한다. shared resource의 갯수를 알려주는 변수이다. (1이면 shared resource가 1개, 2면 2개, ...)
그리고 semaphore에 가능한 operation은 딱 두개다. 더하기(P)와 빼기(V).
개념 자체는 lock과 비슷하다. 프로세스가 진입할때, semaphore의 값을 먼저 읽는것이다. 두가지 경우가 있는데,
-
semaphore의 값이 양수일 경우
: shared resource가 남는다는 뜻이므로, 진입 후 1을 빼고 resource를 사용.
빠져 나올 때 +1. -
semaphore의 값이 0일 경우
: wating.
그림을 보니 shared resource가 1개, wait()은 -1 , signal()은 +1역할인듯 하다.
※ semaphore의 값이 0 또는 1밖에 없는경우를 binary semaphore,
아닌 경우를 counting semaphore라고 한다.
이제 wait()과 signal()을 뜯어보자.
value : counter역할
process L : 해당 critical section을 기다리는 process들의 list.
wait은 value를 1 빼주고, signal은 value를 1 더해주는 모습이다.
그리고 value값에 따라 process들을 waiting list에 넣거나,
wating 상태였던 process를 빼서 실행시키는 것을 볼 수 있다.
※ 여기서 lock은 OS의 lock이다.
2. Mutex Locks
운영체제가 사용하는 spin lock과 달리, application process나 thread가 blocking되는 lock이다.
개념 자체는 똑같다. critical section에 들어가기전에 lock, 나올 때 unlock을 해준다.
어떻게 하나 결과는 같다. 사실 Binary semaphore=Mutext Lock이라고 봐도된다.
하지만, OS의 spin lock과는 다른 개념이다!
3. Monitor
그런데 semaphore의 변수 자체가 전역변수이기도 하고, 디버깅이 안되므로 프로그래머가 직접사용하기엔 issue가 발생하기 쉽다.
타이밍 문제로 deadlock이 발생한다던지... (mutex lock도 비슷)
그래서 프로그래밍 언어 자체에 critical section보호 기능을 넣은 것이 monitor다.
이론적 기반은 semaphore이니, 원리만 살펴보자.
참고로 Java에서만 지원한다. 자바에서 쓰던 synchronized 그거 맞다.
monitor라는 구간 안에 shared data를 선언했다. 이때 P1~Pn이 shared data를 사용한다고 하면 각각의 body들은 모두 critical section이 될것이다.
그리고 P1~Pn은 모니터링되며 한번에 하나씩만 실행될 수 있다.
monitor라는 class안에 멤버 변수와 함수가 있는 구조라고 보면된다.
Java에서 synchronized를 사용할 땐 컴파일러가 procedure의 시작과 끝에 각각 lock과 unlock을 걸어준다고 생각해도 된다.
condition variables
그림 처럼 한번에 하나의 process만 monitor안으로 들어가서 수행될 수 있다.
여기서 condition variable(조건 변수)라는 개념을 알아야 한다.
마지막으로 두가지 용어를 살펴보자.
Deadlock?
lock이 안풀려서 대기중인 프로세스들이 영원히 기다림.
S, Q 두개의 binary semaphore가 있는데, 위와 같이 interrupt가 걸렸다고 하자.
- P1은 wait(S)에서 waiting상태가 된다.(P0이 S 세마포를 0으로 만들었으므로)
- 다시 P0이 스케줄링 된다.
- P0는 wait(Q)에서 waiting상태가 된다.(P1이 Q 세마포를 0으로 만들었으므로)
두 프로세스 모두 waiting 상태가 되어 깨어날 수가 없고, 이것이 deadlock이다.
Starvation?
나보다 우선순위가 높은 프로세스들이 계속 생겨, 영원히 기다려야하는 상황
