교착상태 회피,은행원 알고리즘

5.3.2 회피 

프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법

> 사전 정보 : 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량

 

**안전상태

교착상태를 회피하면서 각 프로세스에게 그들의 최대 요구량

까지 빠짐없이 자원을 할당할 수 있는 상태

 

 

 

안전 순서열

- 순서 있는 프로세스의 집합 <p1,p2, ..... , pn >

- 각 pi에 대해 , pi가 추가로 요구할 수 있는 자원 소요량이 현재 가용 상태이거나 혹은 현재 가용인 자원에 pk(단 j<i)에 할당된 자원까지 포함하여 할당 가능한 경우

Pa :  단위 자원 할당 받지않음 ,

       추가로 7개의 자원소요량

Pb : 1개의 단위 자원 할당 받아있는상태

       추가로 2개 더 필요

Pc : 5개의 단위 자원 할당 받아있는상태

        추가로 4개더 필요

 

가용 자원이 3으로 충족할수 있는 프로세스는

Pb 뿐이므로,  안전 순서열 첫번째로 Pb 선택

 

 

두번째 프로세스가 추구할수 있는 자원은 첫번째로 할단된 Pb + 가용자원 3 , 총 4개의 자원으로 충족할 수 있는 Pc 

안전 순서열의 세번째는

가용자원 3 + Pb 자원 1 + Pc 자원 3 으로 

Pa를 충족시키수 있다.

 

그렇게 해서 

안전 순서 <Pb ,Pc, Pa>

**

프로세스의 요구에 의해 무조건 자원 할당이 아닌 미리 안전순서열을 만들어서 안전상태 체크

 

> 교착상태는 불안전상태에서 발생

 - 불안전상태 : 할당 과정에 따라 교착상태가 될 수도 있는 상태

 

> 프로세스가 가용상태의 자원을 요구하더라고 안전상태를 유지하기 위해 프로세스는 대기상태가 될 수 있음

(1) 각 자원 유형의 단위자원이 여러 개일 경우

 - 은행원 알고리즘

 

> 각 자원 유형의 단위 자원이 하나밖에 없는 경우

 - 변형된 자원할당 그래프

 

 

1) 은행원 알고리즘

자원을 요청받으면 그 자원을 할당해 주고 난 후의 상태를

계산해서 그것이 안전상태가 보장되는 경우에만 자원을 할당

 

 

 

 

은행원 알고리즘

① REQ𝑖≤NEED𝑖가 거짓이면 오류 

② REQ𝑖≤AVAIL이 거짓이면 𝑝𝑖는 대기 

③ REQ𝑖≤AVAIL이면 

   ③-1 다음과 같이 할당 후와 같은 상태를 만듦

       AVAIL   ← AVAIL - REQ𝑖

       ALLOC𝑖 ← ALLOC𝑖 + REQ𝑖

       NEED𝑖  ← NEED𝑖 - REQ𝑖

③-2 이 상태가 안전상태인지를 조사  ( 안전 알고리즘 )

③-3 안전상태이면 REQ𝑖를 할당

③-4 그렇지 않으면 프로세스를 대기상태로, 데이터 구조는 이전 상태로 복구

 

 

1-1) 안전 알고리즘   

① 길이가 각각 𝑚, 𝑛인 WORK와 FINISH 초기화

             WORK  ← AVAIL

           FINISH(𝑖) ← false, 𝑖=1, 2, …, 𝑛

② FINISH(𝑖)=false이고 NEED𝑖≤WORK인 𝑖 찾기 그런 𝑖가 없으면 go to ④

③ WORK ← WORK + ALLOC𝑖

     FINISH(𝑖) ← true

     go to ②

④ 모든 𝑖에 대하여 FINISH(𝑖) = true이면 안전상태

 

( 시간 복잡도 : O(m(n^2))   , m : 자원 유형의 개수,  n : 프로세스의 개수)