s--
P : s<0 -> block(); 어차피 아무것도 못하니 block
V : s<=0 -> wakeup(p);
s++
Producer-Consumer Problem
여러 Process가 동시에 같은 빈 버퍼에 데이터 접근하여 넣음
해결 ➡️ 접근시 Lock 걸기
Shared data : buffer, buffer 조작 변수 (empty, full buffer 시작 위치)
Synchronization variables: resource count(empty, full buffer), mutual exclusion(binary semaphore)
P(empty)
P(mutex)
V(mutex)
V(full): 소비자 입장에서 자원 반납
P(full)
P(mutex)
V(mutex)
V(empty) 빈 것 반납 생산자 입장에서 자원 반납
write은 오직 한 process만, read는 동시에 여럿이 해도 됨 ➡️ 둘 다 lock을 해도 되지만 비효율적이다.
해결
➡️ 대기 중인 reader가 없을 때 writer 접근 허용
➡️ 접근 중일 때만 DB lock
➡️ reader 포함 모든 process 접근 금지
Shared data : DB, readcount(현재 접근 중인 Reader의 수)
Synchronization variables: db(binary semaphore), mutex(readcount를 접근하는 코드) ➡️ lock 걸기 위함
P(db)
V(db)
P(mutex)
readcount++
if readcount==1: P(db)
: 도중에 writer가 값을 바꾸면 안되니깐 최초 reader일 때 db에 락을 걺.V(mutex)
P(mutex)
readcount--
if readcount==0: V(db)
: writer은 대기 중인 reader가 없을 때 db 접근이 가능하므로 이 사실을 writer에게 알리기 위함V(mutex)
철학자가 하는 일은 생각하기와 밥먹기인데, 밥먹을 때 문제 발생
젓가락 좌우를 모두 잡아야 식사가 가능한데, 모두 동시에 왼쪽만 집은 경우 등 Deadlock의 가능성이 있다.
해결
1. 4명의 철학자만이 동시에 앉도록
2. 두개를 모두 집을 수 있는 경우에만 먹을 권한 주기 ➡️ 밥을 먹을 때만(먹을 수 있을 때만 권한 가능성을 줌)
3. 비대칭 : 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 먼저 집도록 한다.
variables
enum {thinking, hungry, eating} state[5];
semaphore self[5]=0; : binary(0,1) : 권한을 줄지 말지에 대한 변수
semaphore mutex=1 : lock을 위한 변수
putdown(i)
: thinking state로 바꾸고, 좌우에게 권한을 줄지 말지를 정하기 위해 양 옆을 직접 test 진행
pickup(i)
: hungry state로 바꾸고, 본인이 잡을 수 있는지 check 후 P(self[i])
를 통해 1이면 양옆이 알아서 줌
test(i)
: 양 옆이 eating state가 아니어야 하고, 본인은 hungry 상태여야 함. 조건 충족 한다면 eating state로 바꾸고, 권한을 준다.
➡️ 해당 방식은 monitor 방식과 더 유사하다.
공유 데이터에 대해 알아서 자동으로 처리
➡️ Monitor 등장!
High-level synchronization construct
lock을 걸 필요가 없음
active process 하나만 모니터 접근 가능하도록 함. 아니면 다 queue에서 기다려야 함
monitor name
{
shared variable declarations
procedure body P1(...){...}
procedure body P2(...){...}
procedure body P3(...){...}
{initialization code}
}
monitor bounded_buffer
{ int buffer[N];
condition full, empty; // 값을 가지지 않고 자신의 큐에 프로세스를 달아 sleep시키거나 깨우는 역할만 함
void produce(int x)
{ if there is no empty buffer : empty.wait();
add x to an empty buffer
full.signal() // full을 기다리는 소비자 하나 깨우기
}
void consume(int *x)
{ if there is no full buffer: full.wait()
remove an item from buffer and store it to *x
empty.signal()
}
}
example
Deadlock 확인 방법
O: 프로세스 / ㅁ: 자원 (single or multi instance)
O->ㅁ: 프로세스가 자원 요청 / O<-ㅁ: 자원이 프로세스에 속함
분류
위로 갈 수록 강한 방법
Deadlock 발생 조건 중 하나가 만족되지 않도록 하는 것. 미리 방지하는 방식
➡️ 미리 방지하는 방법. 하지만 비효율적
자원 이용률(utilization) 낮아지고, startvation, 시스템 성능(throughput) 저하 등 발생
생기지도 않을 deadlock이니 이렇게 미리 방지하는 것은 오버해드
자원 요청시 부가 정보를 통해 deadlock의 가능성이 없는 경우에만 자원 할당. 미리 방지하는 방식
해당 요청 수행시 deadlock으로부터 안전한지 동적으로 조사 후 안전한 경우만 할당
자원별 최대 사용량을 미리 선언해두도록 함
Safe sequence : 최대 자원 요청이 가용 자원 + 보유자원
안에 들어가도록 일련의 프로세스인 sequence를 구성해야함. 앞 프로세스가 모든 자원을 반납하여 다음 프로세스의 자원 요청을 만족시킨다.
Safe state 를 유지해야함. by Safe sequence
➡️ no deadlock 상태
반대로 unsafe state은 possibilty of deadlock 상태
➡️ deadlock일 수도, 아닐수도 있다.
Resource Allocaion Graph Algorithm (ver. Single instance)
그래프 이용하기. O(n^2) 시간 소요.
➡️ 점선으로 표현된 특정 요청이 들어오면 곧장 deadlock으로 빠지는 최악의 상황만 가정하여, 해당 요청이 들어오면 그 자원이 available해도 주지 않음.
이러한 가정은 미리 최대 자원 요청 정보를 알고 있기에 가능하다.
Bancker's Algorithm (ver. Multi instance)
대단히 보수적이고, 항상 안전한 방식
가정 : 최대 사용량 미리 명시 && 요청 자원을 할당 받은 뒤 유한 시간 안에 자원 다시 반납
Allocation: 현재 할당된 것
Max: 최대 사용량
Available: Allocation을 제외하고 남은 가용 자원
Need(Max-Allocaion, 앞으로 해당 프로세스가 필요한 자원들
특정 프로세스가 자원 요청시, 최대 요청 상황으로 가정하고 Need가 Available을 충족하는지 확인
가능하면 어느 요청이든 ok, 하지만 불가능하면 절대 내주지 않음
해당 방법으로 sequence 구성해야함
➡️ 대단히 비효율적인 방법. 자원이 놀고 있게 되는 비효율
루틴을 두어 이상을 detect 후 deadlock 발견시 recover함. 발생 후 해결하는 방법
single instance 경우 : cycle 발생이 곧 deadlock
Wait-for graph 알고리즘 이용 : 자원을 제외하고 프로세스끼리 종료를 기다리는 화살표로 표현해 간결
➡️ cycle이 있는지 주기적으로 조사. O(n^2) 시간 소요. 최대 사용량을 미리 알릴 필요는 없음.
multi instacne 경우 : Banker's algorithm 응용
낙관적으로 보아 반납할 것이라고 가정.
앞 프로세스가 보유 자원 모두 반납할 시 가동 가능한 프로세스를 찾는다. 그러고 safe sequence를 구성해둠.
Recovery
데드락이 일어나지 않는다고 가정 후 아무 조치도 안취함. 발생 후 해..결하는 방법
overhead일수도 있음 : 데드락이 매우 드물게 발생하므로 미리 조치나 해결을 하는 것은 오버
➡️ 만약 시스템에 발생시 시스템은 책임을 지지 않고 비정상적 작동을 사람이 느낀 후 알아서 kill 등 대처하도록 함. 대부분의 범용 os가 채택함