[운영체제/OS] Deadlocks 데드락

요청(request): 만약 요청이 즉시 승인되기 힘드면, 요청 프로세스는 자원 획득까지 대기해야한다.

사용(use): 프로세스는 자원을 이용한다.

방출(release): 프로세스는 자원을 놓아준다.

 

Deadlock Characterization 데드락 발생 (가능한) 조건 _ 반드시 4가지 모두! 발생한 경우

-Mutual exclusion: 동시에 하나의 프로세스만 독점적으로 자원을 사용할 수 있다.

-Hold and wait: 한 프로세스가 하나의 자원을 갖고있으면서 다른 프로세스의 자원을 또 요청하려고 기다림.

-No preemption(선점 허용x): 점유하던 프로세스가 자발적으로 release해야지만 자원이 release된다. (프로세스가 본인작업 완료 후)

-Circular wait: 위 세 가지가 {P0, P1, ....Pn} 프로세스들로 사이클을 이룸.

 

하나라도 만족하지 않으면 데드락은 발생하지 않는다. 반드시 4가지 모두 만족해야 함.

 

Resource-Allocation Graph

그래프가 사이클이 없다면 => 데드락 없음.

그래프가 사이클이 있다면 => 

   모든 리소스가 싱글 인스턴스라면: 데드락 100%

   several(multiple) 인스턴스 타입이라면: 데드락의 가능성만 있다.

차이점 중요!

 

Deadlock Prevention

Mutual Extension: 공유 가능한 자원들의 배타적인 접근 요구하지 않음.

 

Hold and Wait: 프로세스가 자원을 요청할 때마다 다른 자원을 점유하지 않았음을 보장해야 함.

  방법1) 프로세스가 실행 시작 전 모든 자원을 요청 ->낮은 자원 이용률 야기

  방법2) 프로세스가 아무 자원도 점유 않을 때만 자원 요청하도록 -> 순차적 자원 할당. Starvation 위험

 

No Preemption: 이미 공유 자원 점유한 프로세스가 추가로 요청하면 현재 잡고 있는 모든 자원을 내려놓도록 함.

 

Circular Wait: 모든 자원 타입들에 대해 전체적으로 순서 부여. 각 프로세스는 오름차순이나 내림차순으로만 자원을 요청할 수 있음.(한 방향) ->사이클은 안 일어나지만 성능이 떨어지는 큰 제약 조건이 됨.

 

 

Deadlock Avoidance

미리 프로세스들의 가능하고 할당된 자원들의 개수, 요청 최대 개수 정보를 정해두라! 그 정보만 트래킹하면 편하다.

safe state에 시스템이 있다면 데드락은 발생할 일 없다.

unsafe state에 있다면 데드락의 발생 가능성이 있다.

Avoidance=> safe에서 safe 구간으로만 이동을 허용한다. 

 

 

Avoidance Algorithms (할당할지 말지 결정..)

Single instance의 자원 타입-> resource-allocation graph 이용해서 cycle 존재유무 확인

multiple instance의 자원 타입-> banker's algorithm

 

Resouce-Allocation Graph

Claim edge : 요청해도 돼? 물어보기 => (O) Cycle 없네 :) => request

                                               => (X) deadlock 생길 거 같아. Cycle이 있어. :( =>deadlock avoidance (request안함)

 

deadlock avoidance: Claim을 미리 보고 assignment(할당) 발생시 cycle 생기면 요청하지 않는 것이다.

 

Banker's Algorithm

한 종류 리소스가 두 개 이상의 인스턴스 가질 때 

(<->Resource-allocation graph는 여러개의 한 종류의 자원 인스턴스에는 적용 안됨)

 

n : 프로세스의 개수

m  : 자원(리소스)의 개수

available[j] : 자원의 개수만 갖는 배열

max[i][j] =k: i번째 프로세스는 j타입의 자원을 최대 k개 요구할 것이다.

allocation[i][j]=k : Pi는 현재 자원타입 Rj의 인스턴스를 k개 할당되었다.

need[i][j]=k  필요한 자원의 개수. need[i,j] = max[i,j] - allocation[i,j]

 

 

Safety Algorithm

safe한지 아닌지 판단하는 알고리즘

1. Work = Available

  Finish[i] = false for i=0,1,....n-1

2. (a) Finish[i] = false

   (b) Need[i] <= work  //자기가 필요한 프로세스는 모두 만족한단 뜻.

i가 없다면 4단계로 바로 이동

3. Work = Work + Allocation[i]

  Finish[i] = true

2단계로 이동. 프로세스 i는 종료됨

4. Finish[i] == true 라면 모두 safe state

 

 

Resource-Request Algorithm

1. Request[i] <= Need[i] 이면 2단계로 이동. 아니면 에러 리턴(잘못된 코드임)

2. Request[i] <= Available이면 3단계로 이동. 아니면 Pi는 wait(가능한 자원이 없다는 뜻)

3. Available = Available - Request[i];

   Allocation[i] = Allocation[i] + Request[i];

   Need[i] = Need[i] - Request[i];

safe하다면 자원을 Pi에 할당

unsafe하다면 Pi는 wait해야한다. deadlock 발생가능 상황이라 요청을 안 들어준다.(원래값으로 돌려줌)