상대방이 깃발을 들고 있고(상대방 flag == true) && 상대방 차례(turn == 상대)
이면 계속 while을 돌음while(S<=0)
으로 돌다가 S가 양수가 되면 자원을 가져감(S--
)S++
semaphore mutex;
do {
P(mutex)
critical section
V(mutex)
} while(1);
S-- // 자원 획득
if (S < 0) { // 획득할 수 없으면 block으로 변경
block()
}
S++ // 자원 반납
if (S <= 0) { // 누군가에게 줄 수 있으면 wakeup해서 깨워줌
wakeup()
}
S <= 0
= 누군가 -1하고 잠들어 있다일반적으로 Block & Wakeup이 Busy-Wait보다 효율적
- 프로세스를 block <-> wakeup하는 오버헤드는 존재
- critical section이 매우 짧은 경우 오버헤드가 커질 수 있음
➡️ 공유 버퍼에 들어갈 때 lock을 걸고 풀어야 함
➡️ 공유 버퍼에 들어가기 전 버퍼가 비었는지(찼는지) 확인하고 들어가야 함
자원의 개수를 셀 때(resource count), 자원에 접근할 때(mutext exclusion) 세마포어 변수가 필요
readCount++
하고 나갈 때 readCount--
readCount
역시 공유 변수이므로 변경할 때 lock을 걸어야 함readCount
가 1이 아니면 이미 누가 읽고 있던 것으로 lock을 안걸어도 됨readCount == 0
이면 아무도 읽고 있지 않으므로 lock을 해제readCount
와 db 접근 모두 binary 세마포어➡️ 이런 문제를 보완
동시 수행 중인 프로세스 사이에서 안전한 데이터 공유를 위한 high-level 동기화 구조
conditinal variable
사용교착 상태
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
자원 할당 시 발생 조건 4가지 중 하나 이상이 만족되지 않도록 하기
자원 요청의 부가 정보를 이용해 deadlock의 가능성이 없는 경우에만 자원을 할당하기
데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 발견시 recover
데드락을 시스템이 책임지지 않음 -> UNIX를 포함한 대부분의 OS가 채택
자주 발생하는 문제가 아니라 방지하는게 오버헤드일 수 있음
사용자가 처리하도록 미루기
➡️ 생길지 모르는 데드락을 방지하기 위해 위와 같은 처리를 하는게 비효율적일 수 있음
Banker's 알고리즘
- 자원 별 개수
- 프로세스 별 평생 필요한 자원별 최대 개수(Max)
- 현재 할당 가능한 자원의 개수(Available)
- 최대 요청 가능량(Max) - 현재 할당량(Allocation) = 할당을 요구할 수 있는 최대량(Need)
- 현재 가능한 자원량(Available)에서 지금 요청한 자원량을 줘도 Need를 만족시킬 수 있는지 판단해서 자원을 할당
➡️ 자원이 남아도는데도 안주니까 비효율적, 최대량을 줄 수 없는 상황이라도 반드시 데드락이 발생하는게 아님
방법 1) 사이클을 찾기(자원이 하나씩일 때)
방법 2) 다른 프로세스가 자원을 반납할 거라고 낙관적으로 생각하며 자원을 할당 - 정말 데드락인 경우만 찾기
방법 1) 데드락과 관련된 모든 프로세스 죽이기
방법 2) 데드락과 관련된 프로세스 중 하나씩 자원을 빼앗으면서 해결되는지 확인