[OS] Deadlocks, Monitors

 

 

 

하나의 프로세서는 프로세스 실행을 위해 여러 하드웨어 자원을 필요로 하고 os는 이 자원들을 잘 분배해야 한다.

배분이 잘 안된다면 데드락에 빠지게 된다.

어떤 자원은 가지고 있으나 다른 프로세서가 사용중이라 다른 자원을 갖지 못할 때에는 대기해야 한다.

데드락은 어떤 자원을 가지고 있으면서 다른 자원을 가지려 대기할 때 발생한다.

 

 

 

 

교착상태 (Deadlocks) 필요조건

 

1. Mutual exclusion (상호배타) → 한 프로세서가 특정 하드웨어를 사용하면 다른 프로세스는 사용하지 못함.

2. Hold and wait (보유 및 대기) → 어떤 자원을 보유하고 있으면서 다른 자원을 기다리는 것. 

3. No Preemption (비선점) → 어떤 자원을 보유하고 있으면서 다른 자원을 강제로 뺏어오는 것.

4. Circular wait (환형대기) → 5명의 철학자 모두 왼쪽 젓가락을 듦 → starvation현상

 

필요조건이기 때문에 이 4가지 조건이 모두 만족된다 해도 데드락이 일어나지 않을 수 있다.

데드락이 일어나지 않게 하려면 4가지 조건 중 하나라도 만족하지 않으면 된다.

 

 

자원(Resource)

 

동일한 타입의 자원이 여러 개 있을 때 각각을 instance라 한다.

 

자원의 사용

request → use → release

 

자원할당도(Resource Allocation Graph)

자원이 어느 프로세서에 어떻게 할당되었는지를 그래프로 나타낸 것이다. 이를 보고 교착상태가 일어날 지 안일어날 지 예측 가능하다.

R1자원은 한개인데 P1이 사용중이다. P2이 P1의 사용이 끝나면 R1을 사용하려 요청중에 있다.

 

P1은 R2의 한 인스턴스를 사용중이고 R1의 자원을 사용하기 위해 요청중이다.

P2는 R1,R2의 자원을 사용중이고 R3의 자원을 사용하기 위해 요청중이다.

P3는 R3의 자원을 사용중이다.

R4에 있는 인스턴스들은 아무 프로세서에도 사용되지 않은 상황이다.

 

 

 

교착상태 처리

 

데드락이 일어나면 시스템은 더 이상 동작하지 않는다.

 

1. 교착상태 방지 (Deadlock Prevention) → 4조건 중 하나를 깨는 것.

   Mutual exclusion (상호배타) → 자원공유를 가능하게 함

   Hold and wait (보유 및 대기) → 자원을 가지고 있으면서 다른 자원을 기다리지 않게 함

   No Preemption (비선점) →  자원을 선점가능하게 함

   Circular wait (환형대기) →  자원에 번호를 붙여 오름차순으로 자원을 요청

 

 

2. 교착상태 회피 (Deadlock Avoidance) →  Banker's algorithm사용

magnetic tape 12개일 때

process	max needs	current needs
P0	10	5
P1	4	2
P2	9	2

p0,p1,p2에 각각 5,2,2를 나눠줌 → 3개 남음. 안전한 할당(p0,p1,p2 각각 5, 2, 7 남음)

p1에 2개 할당 →  p1종료되어 4개 반환됨 →  5개 남음(1+4)

p0에 5개 할당 →   p0종료되어 10개 반환됨 →  10개 남음

p2에 7개 할당 →  p2종료되어 9개 반환됨 →  12개 남음 

파산이 일어나지 않음

 

magnetic tape 12개일 때

process	max needs	current needs
P0	10	5
P1	4	2
P2	9	3

p0,p1,p2에 각각 5,2,3를 나눠줌 → 2개 남음. 안전한 할당(p0,p1,p2 각각 5, 2, 6 남음)

p1에 2개 할당 →  p1종료되어 4개 반환됨 →  4개 남음

남은 자원이 부족해 p0, p2에 자원을 할당할 수 없음

파산이 일어남

 

 

 

3. 교착상태 검출 및 복구 (Deadlock Detection & Recovery) → 데드락이 일어나는 건 허용하되, 이를 복구하도록 함

Deadlock detection

os의 process management에서 지속적으로 데드락이 발생했는지 주기적으로 검사해주어야 한다.

→  detection을 하기 위한 오버헤드가 크고 데드락 이전의 상태를 기억해주어야 한다.

 

복구를 하려면 프로세스를 강제로 종료하거나 자원을 선점해 일부 프로세스에게 할당하는 방법이다.

 

4. 교착상태 무시 (Don't care) → 잘 안일어남

데드락은 실제로 잘 발생하지 않는다. 따라서 만야에 데드락이 발생한다면 그냥 무시해버리는 방법이다.

 

 

 

 

 

 

모니터(Monitors)

 

모니터는 세마포 이후에 나온 프로세스 동기화 도구이다. 

모니터는 공유자원과 공유자원 접근함수 그리고 2개의 큐로 구성된다.

공유자원 접근함수에는 최대 1개의 스레드만 접근할 수 있고(상호배타), 접근 스레드가 wait()로 블록되면 원래 접근하던 스레드는 conditional synchronization 큐로 들어가고 새로운 스레드가 접근할 수 있다.

새로운 스레드는 notify()를 통해 conditional synchronization 큐에 블락되었던 스레드를 깨울 수있다. 깨워진 스레드는 현재 스레드가 나가면 다시 접근할 수 있다.

wait() : conditional synchronization 큐에 스레드 가둠

notify() : conditional synchronization 큐에 갇힌 스레드 깨움

notifyAll() : conditional synchronization 큐에 갇힌 스레드 여러개면 모두 깨움

 

 

모니터의 일반적 사용

1.상호배타

synchronized{

critical section

}

상호배타를 구현하기 위한 세마포의 경우, sem.value = 1을 주어 임계구역에 들어가기 전 acquire()함수를 호출하고 들어가고 난 후에는 release()함수를 호출하는 등 과정이 복잡했는데, 모니터의 경우 synchronized만 붙여주면 되기 때문에 간단하다.

 

 

2.ordering

 

Bank Account problem

• Parent 먼저 (PPPPPCCCCC)

parent	child
	wait()
deposit	withdraw
notify()

• Child 먼저 (CCCCCCCPPPPPPP)

parent	child
wait()
deposit	withdraw
	notify()

• Parent Child 교대로(PCPCPCPCPCPC)

parent	child
	withdraw
	while (p turn)
notify()	wait()
p turn = false
wait()	notify()
	p turn = true
	wait()