Ch.7 교착상태 (Dead Lock)

7.1 시스템 모델

• 작업 순서
• 요청 - 사용 - 해제
• 교착 상태
• 결코 만족될 수 없는 자원 요청을 함으로써 process가 중지되어 기다리는 상태

 자원의 개념

1) Serially Reusable Resource (SR)
ex) Tap, CPU
특징)

• Number of units is constant
• Each unit is either available or allocated for exclusive use.
• A process may release a unit only after it has previously acquired that unit.

2) Consumable Resource (CR)
ex) message, signal
특징)

• Number of units vary
• Producer process increase number of units.
• Consumer process decrease number of units.

3) SR과 CR에 대한 dead lock 대처 방법 상이

 → CR일 경우 time limited RECEIVE or WAIT으로 해결

 

7.2 Dead Lock의 특징

 

7.2.1 dead lock의 4가지 필요 조건

(1) 상호 배제 (Mutual Exclusion)

• 한번에 하나의 프로세스만이 그 자원을 사용 가능

(2) 점유와 대기 (Hold & Wait)

• 자원을 점유하면서 다른 자원을 대기

(3) 비 선점 조건 (Non-preemption)

• 자원을 강제로 빼앗을 수 없고, 해제될 때까지 대기

(4) 순환 대기(Circular Wait)

• 자원할당 그래프에서 cycle을 형성

 

7.2.2 자원 할당 그래프

• 모든 프로세스에 대해 가능한 모든 할당 순서를 찾음
• 자원 할당 그래프에 cycle이 존재
  : 교착상태일 수도 있고, (자원이 하나씩만 있는 경우) 아닐 수도 있다.
•  자원 할당 그래프에 no-cycle -> no dead lock

 자원 할당 그래프의 소거

• 프로세스의 자원요구가 만족될 수 있으면 그 프로세스는 소거 가능하다.
• 모든 프로세스를 소거할 수 없으면 교착 상태이다.

7.3 Dead Lock 처리 방법

(1) 예방(Prevention)

• Dead lock의 필요조건 네가지 중 하나를 부정

(2) 회피(Avoidance)

• 은행원 알고리즘(Banker's Algorithm)

(3) 발견과 복구 (Detection & Recovery)
(4) 무시 (Ignore)

 

7.4 Dead Lock 예방

• Dead Lock 필요조건 네가지 중 하나를 부정

7.4.1 '상호배제' 조건의 방지

• 일반적으로 부정할 수 없음

7.4.2 '점유와 대기' 조건의 방지

가)   수행 전에 필요한 모든 자원을 요구하여 할당 받는 방법

나)   각 프로세스는 점유하고 있는 자원이 없을 때만 요구하여 할당 받는 방법

단점) 자원의 비효율성, 기아상태 발생 가능

 

7.4.3 '비선점'조건의 방지

• 자원을 점유하고 있으면서 더 이상 요구가 받아들여지지 않으면 점유하고 있던 자원을 해제하고 대기
• register나 memory 공간에 이용 가능
• 기아상태 발생 가능

7.4.4 '순환대기' 조건의 방지

• 각 자원에 고유 번호를 붙여 자원의 번호가 커지는 순서대로만 요청할 수 있게 함
• 자원 낭비

7.5 Dead Lock의 회피

7.5.2 자원할당 그래프 알고리즘

• 각 자원이 종류마다 한개씩만 있을 경우에 사용 (cycle을 형성하며 무조건 D/L)

7.5.3 Dijkstra의 Banker's algorism

• 안전상태 (safe state)

• 불안전 상태 (unsafe state)

• 안전 상태만 갖도록 자원을 할당하는 방법

• 표기법t: 자원의 총 개수avail :    사용 가능한 자원의 총 갯수alloc(i): 프로세스 i에게 할당된 자원의 갯수 max(i): 프로세스 i가 최대로 필요로 하는 자원의 갯수need(i): 프로세스 i가 추가로 필요로 하는 자원의 갯수프로세스 - 고객자원 - 돈반남할지 안할지 모르면 빌려주지 않음자원을 반드시 회수할 수 있을 때 빌려줌

가) 안전 상태의 예

 총 12개의 Tape

proc    alloc(i)     max(i)    need(i)   avail

p1        1             4          3          6          

p2        4             6          2          2

p3        5             8          3          6

안전 순서: p2 → p3 → p1

or p2 → p1 → p3

=>안전상태

 

나) 불안전 상태의 예

총 12개의 Tape

proc    alloc(i)     max(i)    need(i)   avail

p1        8            10          2         1(누가한테 주더라도 끝나지 않아 자원 회수 불가 )          

p2        2             4          2          

p3        1             3          2          

- 불안전한 상태가 D/L을 의미하지 않음(발생 가능성 있음)

- 시스템이 항상 안전 상태를 유지하도록 자원을 할당한다.

 

7.5.3.1 안정성 알고리즘

1. work와 Finish를 각각 m과 n인 벡터라 하자.

      work := Available

      Finish[i] := false, i = 1,2,3,...,n

2. 다음을 만족하는 i를 찾는다.