Operating Systems 6. Synchronization Tools - (2)
Mutex Locks
- 운영체제에서 임계방법을 해결할 수 있는 소프트웨어 도구를 제공한 것이 Mutex lock 이다.
- Mutex lock 은 acquire() 을 통해 lock을 획득하고, release() 를 통해 lock 을 반환할 수 있다.
- 그러나 루프를 반복 실행하면서 lock 을 기다리는 busy waiting 이 발생한다. -> spin lock
Semaphore
- Semaphore 을 정수 변수 S 라고 할 때, 이 변수는 오직 wait() 와 signal() 이라는 2가지 atomic operation 에 의해서만 access 가 가능하다. semaphore 의 값은 대게 사용 가능한 특정 자원의 수를 나타낸다.
Semaphore 의 용도
- Counting semaphore : 한정된 유한 개수의 자원에 접근가능하다.
- Binary semaphore : semaphore 의 값이 0 또는 1이다. (mutex lock 과 유사)
S2를 실행하기 전에 S1이 먼저 실행되어야 함을 보장해야 한다.
이때 S1을 실행하고 signal() 을 하면, P2는 기다리고 있다가 signal 을 받고 S2를 실행할 수 있게 된다.
-> 순서가 보장된다.
Semaphore 구현
- semaphore 은 절대로 두개의 프로세스가 같은 semaphore 에 대해 동시에 wait() 와 signal() 을 실행할 수 없음을 보장해야 한다.
- 따라서 wait() 와 signal() 을 사용하는 것 자체가 임계구역의 문제가 될 수 있다.
No Busy Waiting Semaphore
- 프로세스의 block, wakeup 방법을 이용한다.
- semaphore를 획득할 수 없을 때 semaphore semaphore 대기 큐에 자기 프로세스 를 추가하고 자신을 block 시킴
- semaphore를 사용 가능하게 되면, semaphore 대기 큐에서 한 프로세스를 꺼내어 ready queue로 이동하여, 대기 중인 하나의 프로세스를 wakeup시킴
- Semaphore 의 waiting queue 를 연결리스트로 구현한다.
- 음수 값은 대기 중인 프로세스의 개수를 의미하고, 양수 값은 이용 가능한 자원의 개수를 의미한다.
- semaphore 의 값을 1 줄임으로써 임계 영역에 들어갈 준비가 되었고, 자원을 필요로 한다는 선언을 한다.
- semaphore 의 값이 음수라면 프로세스를 waiting list 에 넣고 block() 한다.
- 임계영역에서 실행을 마쳤다면 semaphore 의 값을 증가시켜준다. 즉, 작업이 끝나 자원을 반납하는 것이다.
- semaphore 의 값이 0 이하라면, waiting list 에 있는 프로세스를 깨워서 ready 상태로 변환시켜 준다.
-> 세마포의 값을 먼저 감소한다. (세마포 검사와 감소의 순서가 busy-waiting 방법과 반대이다.)
Problems with Semaphores
- Deadlock : 두 개 이상의 프로세스들이 그들 중 한 프로세스에 의해서만 발생될 수 있는 사건을 무한정 기다리고 있어서 진행이 되지 않는 상황
-> 하나씩 차지한 상태로 상대방 것을 요구한다.
- Starvation : 일부 프로세스가 무한정 대기할 수 있는 상황
-> wait() 와 signal() 의 순서를 반대로 사용한 경우, signal() 대신 wait() 를 사용한 경우, signal() 또는 wait() 를 누락한 경우와 같은 상황에서 문제가 발생한다.
Monitors
- 병행 프로그래밍을 위한 지원으로, semaphore 와 같은 기능을 직접 사용하지 않고 병행 프로그래밍을 위해 고수준의 상호배제를 지원하는 기능이 개발되었다.
- 프로세스 동기화를 위한 편리하고 효율적이고 안전한 방법을 제공하는 고수준의 동기화 추상화 데이터 형이다.
- monitor 에서 정의된 procedure 만 monitor 내의 local data를 접근가능하다.
- monitor 의 procedure 들은 한 번에 하나의 프로세스만 진입하여 실행할 수 있다. -> 상호배제 보장
조건변수(Condition Variables)
- 기본 모니터는 여러 동기화 기법 모델링을 위해서 충분히 강력하지 않다.
- 공통된 자원에 대한 경쟁을 막기 위해 mutex lock, semaphore 을 사용하는데, 이러한 semaphore 와 mutex lock 을 가지려는 대상들이 2개 이상일때 조건변수를 통해 순서를 설정한다.
- condition x, y;
- X.wait() : 이 연산을 호출한 프로세스는 보류하게 된다.
- X.signal() :
- 보류 중인 프로세스가 있다면 x.wait() 를 호출한 프로세스 중 하나가 재개된다.
- X.signal() 은 정확히 한 개의 보류 중이던 프로세스만을 재개한다.
- 보류하는 프로세스가 한 개도 없다면, 아무것도 일어나지 않는다.
- Semaphore 에서 signal() 이 항상 semaphore 상태에 영향을 주는 것과 차이가 있다.
Condition Variables Choices
- P가 x.signal() 을 주고, Q는 x.wait()에 걸려있는 상태이다.
- Signal and wait : P는 Q가 monitor 를 떠나거나 다른 조건을 기다릴때까지 기다린다. (signal 을 주는애가 기다린다)
- Signal and continue : Q 는 P가 monitor 를 떠나거나 다른 조건을 기다릴때까지 기다린다. (signal 을 주고 내가 먼저 수행)
Monitor Implementation Using Semaphores
-> signal and wait
Monitor Implementation Using condition Variables
- Monitor 로 프로세스 재개하기 : x.wait(c) // c는 우선순위
- Single Resource allocation
- A monitor to Allocate Single Resource
-> time 의 시간이 작을수록 우선순위가 높다면, time 이 짧은애가 먼저 wait 를 빠져나간다.
Deadlock and Starvation
- deadlock
- Starvation : indefinite blocking
- Priority Inversion : 낮은 우선순위의 프로세스가 lock 을 먼저 가질경우, 우선순위가 역전된다.