TIL 정리_97(Deadlock)

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다

 

Deadlock 

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다

 

Resource

하드웨어, 소프트웨어 등을 포함하는 개념이다

예) I/O device, CPU cycle, memory space, semaphore 등이 있다

 

프로세스가 자원을 사용하는 절차

request, allocate, use, release

---

Deadlock의 처리 방법

*상위에 기술된 것이 강한 처리방법이다

 

 

1. Deadlock Prevention

• 자원 할당 시 deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것이다.
• Deadlock을 미연에 방지하는 방법 중 하나이다 

 

Mutual Exclusion 

공유해서 안 되는 자원의 경우 반드시 성립해야 한다

 

Hold and Wait

프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다

• 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법이다
• 방법 2 : 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다

 

No Preemption

process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다

-> 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다

state를 쉽게 저장하고 복원할 수 있는 자원에서 주로 사용한다(CPU, memory)

 

Circular Wait

모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다

예를 들어 순서가 3인 자원 Ri를 보유중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는

우선 Ri를 release 해야 한다

-> Utilization 저하, throughput 감소, starvation 문제가 있다

 

 

2. Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다.

-> 자원 요청에 대한 부자정보를 이용하여 자원 할당이 Deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당한다

• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다
• Deadlock을 미연에 방지하는 방법 중 하나이다 
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다

 

safe state

시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태를 말한다

 

- safe sequence

프로세스의 sequence<P1, P2, ..., Pn>이 안전하려면 Pi의 자원 요청이(1 <= I <= n)

“가용자원 + 모든 Pj(j < I)의 보유 자원”에 의해 충족되어야 한다

-> 조건을 만족하면 아래의 방법으로 모든 프로세스의 수행을 보장한다

• Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj가 종료될 때까지 기다린다
• Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다

시스템이 safe state에 있으면 deadlock이 발생하지 않는다

시스템이 unsafe state에 있으면 deadlock이 발생할 수 있다

 

 

 

Deadlock을 피하기 위한 2가지 경우의 avoidance 알고리즘

최악의 상황을 가정한다

자원의 인스턴스가 1개씩 존재하는 경우

-> Resource Allocation Graph 알고리즘을 사용한다

자원의 인스턴스가 여러 개 존재하는 경우

-> Banker’s 알고리즘을 사용한다

 

 

Resource Allocation Graph Algorithm

Claim edge Pi -> Rj

- 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻한다 //점선으로 표시

- 프로세스가 해당 자원 요청시 request edge로 바뀐다 //실선으로 표시

- > Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다

• request edge의 assignment edge 변경시 cycle이 생기지 않는 경우에만 요청 자원을 할당한다
• Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n^) 시간이 걸린다

 

 

Banker’s Algorithm

가정

모든 프로세스는 자원의 최대 사용량을 미리 명시한다

프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이 자원들을 다시 반납한다

 

방법

기본 개념 : 자원 요청시 safe 상태를 유지할 경우에만 할당한다

1. 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다 //없는 경우 unsafe 상태이다
2. 해당하는 프로세스가 존재하면 그 프로세스에게 자원을 할당한다
3. 할당 받은 프로세스가 종료되면 보든 자원을 반납한다

-> 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다