Chapter 8: Deadlocks

System model

2가지 형태로 되어 있다.

1. 관계를 나타낸 것이다
2. 프로세스와 리소스 간의 관계

프로세가 리소스를 사용하는 방법

• Request
• Use
• release(해제)

Deadlock Characterization

Deadlock 걸렸을 때, 나타나는 특징

1. Mutual exclusion

상호배제(리소스에 대한 상호배제)

상호배제 현상이 발생한다.

의미 찾아보기

2. Hold and wait

프로세스가 최소 1개의 리소스를 hold하고 있고, 자기가 필요로 하는 리소스를 기다리고 있다.

3. No preemption

비선점

선점이 안된다.

선점이 된다면 deadlock이 안걸린다

4. Circular wait

돌아가는 형태(사이클 형태)로 기다리고 있다.

 

Resource-Allocation

프로세스하고 리소스 관계를 체크해서 deadlock을 예방한다.

 

request edge: 프로세스가 자기가 필요한 리소스를 요청하는 것의 방향성을 나타내는 것이다.

Pi -> Rj

assingnment edge: 리소스는 프로세스를 가지는 것이다.(할당한다)

Rj -> P

리소스는 type(개수)

 

Pi requests instance of Rj

요철 할 때는, 바깥쪽에서 요청한다.

 

Pi is holding an instance of Rj

리소스는 안에서 밖으로 간다.

Resource Allocation Graph

 

 

Resource Allocation Graph With A Deadlock

Graph With A Cycle But No Deadlock

Basic Facts

• 리소스의 개수에 따라서 deadlock이 걸릴 수 있다.
• 리소스 개수당 하나의 instance를 가지고 있다. 그래서 deadlock에 걸린다
• 리소스 개수당 여러개의 instance를 가지고 있으면, deadlock에 걸릴 가능성이 있다

Methods for Handling Deadlocks

Deadlock prevention, Deadlock avoidance, Deadlock recover

  -> 미리 deadlock을 예방한다.

많은 OS들이 예방과 회피를 하지 않는다. 하지만 Deadlock이

자주 걸리는 것이 아니기에 시간과 비용이 많이 들어서, recover하고 detection 를 한다.

 

Deadlock Prevention

Deadlock 조건을 만족시키지 않으면 된다.

1. Mutual Exclusion

상호배제를 깬다

하나의 리소스에 2개의 프로세스가 사용된다

-> 말이 안되는 말이다. ->이 조건을 만족시키는 것은 말이 안된다.

2.Hold and Wait

하나의 프로세스가 리소스를 가지고 있고, 다른 프로세스는 기다린다.

깨는 방법

-> requests a resource  따른 프로세스가 리소스를 가지고 있으면

  -> 요청을 거부한다.

->문제는 자원의 활용도가 낮아진다

-> starvation possible 발생 -> 일이 끝난 리소스가 기다리던 프로세스가 요청을 못하고 다른 프로세스가  그 리소스를 가져간다.

3. No Preemption(비선점)

Preemption으로 간다는 것이다. -> 선점이 된다

-> 나보다 우선순위가 높으면 리소스를 빼길 수 있다.

-> 하지만 뺴는 프로세스는 괜찮지만, 빼기는 프로세스는 문제가 생간다

  -> 나중에 그 리소스가 나중에 할당되면 일을 다시 시작해야한다.

  -> 우선 순위가 낮아가지고, 일을 못할 수 도 있다. (기아현상)

4. Circular Wait

1~n까지 어떤 프로세스가 리소스 요청할 때, 자기가 hold하고 있는 리소스 번호보다 크면 요청 가능

 

-> deadlock prevention은 가능하지만, 자원의 활용도가 낮고, 기아현상이 나타난다

Deadlock Avoidance

시스템의 사전 정보가 있어야 한다

Safe State

Safe sequence

<P1, P2, …, Pn> 이렇게 현제의 프로세스를 나열해서 safe sequence를 보여준다

-> 순서는 일을 마치는 순서

-> 나열되면 현제 safe sequenc가 존재하는 지를 보여준다.

 

-> deadlock은 일을 진행을 멈추는 것이다.

-> safe sequence가 존재하지 않으면 deadlock이 존재하는 것이다

 

If a system is in safe state -> no deadlocks

If a system is in unsafe state -> possibility of deadlock

-> 가능성이 있다

 

Avoidance(회피)

-> 현제 상태가 unsafe로 들어가지 않게 회피해주는 것이다.

-> 항상 safe상태를 유지 시켜준다.

Safe, Unsafe, Deadlock State

현제 상태를 체크하는 것

Safe은 상태면 -> deadlock이 아니라는 형태이다

Unsage-> deadlock일 수도 있다.

 

Avoidance Algorithms

 

각 리소스 타입마다, 개수가 1개 밖에 없다.

-> resource-allocation graph 사용한다

 

Claim edge

-> 점선 표시이다.

-> 앞으로 필요하다고 claim을 보내는 것이다.

Resource-Allocation Graph

Unsafe State In Resource-Allocation Graph

Data Structures for the Banker’s Algorithm

• Available-> 할당 되진 않은 각 리소스의 숫자
• Max -> 2차 배열 각 프로세스가 자기가 일을 끝내기 위한 리소스의 개수
• Allocation -> 현제 그 프로세스의 할당된 리소스의 개수
• Need -> 일을 끝내기 위해서 필요한 리소스의 숫자

Example of Banker’s Algorithm

• Allocation(all) + Available = 어떤 리소스의 총 인스턴스의 개수
• Need = Max – allocation

Available 3 3 2

P1 한테 남은 리소스를 줄 수 있다.

남은 리소스: p1은 리소스를 받고 일을 끝내서 리소스를 돌려준다,

그래서 5 3 2가 된다

P3

-> 남은 것은 7 4 3

 

Example:  P1 Request (1,0,2)

Available 5 3 2 -> 7 4 3

Available 2 1 0 -> No

요청을 받을 것인가. -> safe라는 것

아니면 회피 할 것 인가 -> unsafe라는 것

Can request for (3,3,0) by P4 be granted?

-> 가능하다

Can request for (0,2,0) by P0 be granted?

-> deadlock

 

wait-for graph

• 프로세스만 가지고 만든 그래프
• 리소스마다 프로세스가 1개 밖에 없을 때, 가능하다

 

Example of Detection Algorithm

Example

P2이 request가 0 0 1이면,

-> deadlock이 생긴다

 

Detection-Algorithm Usage

호출 시기와 빈도는 다음에 따라 달라진다.

deadlock 얼마나 자주 일어나는가?

얼마나 많은 프로세스를 Rollback해야 하는가

Recovery from Deadlock:Process Termination

프로세스를 끄기

1.Deadlock에 걸린 프로세스를 전부 끈다 -> 다시 처음부터 시작해야 해서 비용이 증가

2.Deadlock에 걸린 프로세스를 순차적으로 멈춘다(다시 확인)-> deadlock이 푸는 데 오래 걸림, 하지만 비용은 낮다 그래서 사간이나 비용이 적을 수 도 있다

  -> 프로세스의 우선순위 낮은 것부터 확인

  -> 프로세스가 일을 적게 한 것부터 멈춘다

  -> 리소스를 많이 가진 프로세스를 멈춘다

  -> 프로세스가 일을 끝내기위해 필요한 리소스의 많은가

  -> 프로세스가 종료되기 위해 얼마나 많은 리소스가 필요한가

  -> 프로세스가 batch인가 interactive한가

Recovery from Deadlock:  Resource Preemption

Resource Preemption -> 자원을 선점하게 한다

-> 자원을 빼서 다른 프로세스에게 줄 수 도 있다

 

minimize cost: 비용을 최소화 한다.

 

빼긴 프로세스는 safe가 된다. 다시 Rollback을 해줘야 한다.

-> 하지만 기아 현상이 발생할 수 있다.