Deadlock: 교착 상태 (1/2)

* Deadlock

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

 

* Resource (자원)

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

 - 예) I/O serivice, CPU cycle, memory space, semaphore 등

 - 프로세스가 자원을 사용하는 절차 (Request, Allocate, Usem Release)

 

Deadlock Example 1

 - 시스템에 2개의 tape drive가 있다. (하나 복사 - 다른 하나 paste)

 - 프로세스 p1과 p2 각각 하나의 tape drive를 보유한 채 다른 하나를 기다림

Deadlock Example 2

 - Binary semaphores A and B

Process0          P(A)          P(B)

Process1          P(B)          P(A)

 

1. 데드 락 발생의 4가지 조건

- Mutual exclusion (상호 배제)

매 순간 하나의 프로세스만이 자원을 사용할 수 있음 -> 독점적 사용

- No preemption (비선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음 -> 빼앗기면 데드락 발생하지 않을텐데 

- Hold and wait (보유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

- Circular wait (순환 대기) 

자원을 기다리는 프로세스간에 사이클이 형성되어야 함

프로세스 P0,P1,,,,Pn이 있을 때

P0은 P1이 가진 자원을 기다림

P1은 P2가 가진 자원을 기다림

Pn-1은 Pn가 가진 자원을 기다림

Pn은 P0가 가진 자원을 기다림

 

<Resoure-Allocation Graph: 자원 할당 그래프>

* Vertex

 - process P = {P1, P2, ,,, Pn}

 - Resource R = {R1, R2, ,,, Rn}

* Edge

 - request edge Pi -> Rj

 - assignment edge Rj -> Pi

 

! 그래프 안에 사이클 없으면 데드락 아님

! 사이클이 있다면

 1) 자원 인스턴스가 1개뿐이라면 데드락임

데드락

 2) 자원 타입당 여러개의 자원 인스터가 있다면 데드락일수도 아닐수도~~~~  

얘는 데드락 아님

2. 데드 락의 처리 방법

1. Deadlock Prevention (데드락 생기지 않게 미연에 방지)

자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

2. Deadlock Avoidance (얘도 미연에 방지)

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

시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당 

3. Deadlock Detection and Recovery

Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover -> 컴 느려지면 그 때 detection 돌려서 해결함(recover)

4. Deadlock Ignorance

deadlock 발생을 시스템이 책임지지 않는다. 사실 deadlock은 usual하지 않기 때문에 오히려 대응하는게 overhead가 크다. 사용자가 알아서 프로그램 종료해라

unix를 포함한 대부분의 os가 채택하는 방식임

 

1에서 4로 갈수록 느슨한 정책임

 

<Deadlock Prevention>

* Mutual Exclusion

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

 

* Hold and wait

 - 프로세스가 자원을 요청할 떄 다른 어떤 자원도 가지고 있으면 안되다.

 - 방법 1: 프로세스 시작 시 한번에 모든 필요한 자원을 할당받게 하는 방법(비효율적임)

 - 방법 2: 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다. 

 

* No preemption (일단 자원을 빼앗아올 수 있으면 데드락은 안생기니까,,)

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

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

  - state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용한다. (CPU, 메모리)

 

* Circular Wait

  - 모든 자원 유형에 할당 순서를 정하여 정해진 순서로만 자원 할당

  - 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Ri를 할당받기 위해서는 우선 Ri를 realease 해야함 => utilization 저하, throughput 감소, starvation 문제

 

<Deadlock Avoidance>

 - 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당한다. 

 - 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원 별 최대 사용량을 미리 선언하도록 하는 방법

 

* safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

 * safe sequence

 - 프로세스의 sequence <P1,P2 ,,, Pn>이 safe하려면 Pi( 1 <= i <=n)의 자원 요청이 "가용 자원 + 모든 Pi (j < i)의 보유 자원"에 의해 충족되어야 함

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

  ` Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j < i)가 종료될 때까지 기다린다.

  ` Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다. 

 

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

* 시스템이 unsafe state에 있으면 데드락의 발생 가능성이 있다.

* deadlock avoidance 

 - 시스템이 unsafe state에 들어가지 않도록 보장한다.

2가지 경우의 avoidance 알고리즘

1) Single instance per resource type -> Resource Allocation Graph Algorithm 사용

2) Multiple instacne per resource type -> Banker's Algorithm 사용

 

<Resource Allocation Graph Algorithm>

자원당 인스턴스 1개 뿐일때

3번째는 사이클이 생성되었음= unsafe / 그래프 점선까지 합쳐서 cycle이 생기면 요청을 받아들이지 않음 -> safe 상태 유지

 점선 화살표: 프로세스로부터 자원한테 가는 화살표 이 프로세스가 평생에 적어도 한번은 이 자원을 사용할 일이 있음을 의미한다. 

* claim edge Pi -> Rj

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

 - 프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)

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

 

* Request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.

* cycle 생성 여부 조사시 프로세스가 n개 있으면 O(n^2) 시간이 걸린다. 데드락 생성 가능성이 있으면 자원 안줌(위험성 있으면 x)

 

<Banker's Algorithm>

자원 여러 개 있을 때

* 가정

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

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

 

* 방법

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

 - 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다. (그런 프로세스가 없으면 unsafe 상태임)

 - 할당 받은 프로세스가 종료되면 모든 자원을 반납한다.

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

 

Example of Banker's Algorithm

 * 5개의 프로세스들 (P0, P1, P2, P3, P4)

 * 3 자원 타입 /  A - 10개, B - 5개,  C - 7개씩 자원 있음

Sequence는 <P1, P3, P4, P2, P0>가 존재하므로 System은 safe state. P0은 가용 자원이 Available보다 훨씬 많으므로 주지 않고 기다리게 한다. Available로 need를 충족 가능한가? -> 요청 받아주기 / 충족 불가능? -> 요청 받아주지 않고 기다림