교착상태(Deadlock)

교착상태(Deadlock)

: 멀티프로세싱 환경에서 여러 프로세스가 간섭하여 생기는 문제

-> 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태

Deadlock의 조건

1. Mutual exclusion

: 한번에 오직 하나의 프로세스만 자원을 사용가능

2. Hold-and-wait

: 프로세스가 할당된 자원을 점유하고 다른 프로세스가 반납하는걸 기다리는 상태

3. No preemption

:  프로세스의 할당된 자원은 강제로 빼앗을수 없다.

4. Circular wait

: 프로세스 자원요구가 순환적

Deadlock Prevention(데드락 예방)

: deadlock이 발생할 4가지 조건중 하나라도 제거하자

1. Mutual Exclusion - 사용하지 않음/동시접근 허락되지 않음

2. Hold and Wait - 프로세스가 필요로하는 자원을 일시에 요구/할당

3. No preemption - 자원임시 할당해제 및 원상복구

4. Circular Wait - 자원의 고유번호 지정

=>자원의 비효율적 사용

Deadlock Avoidance(데드락 회피)

: resource에 대한 요청이 있을 때마다 deadlock이 발생할 수 있는지 아닌지를 추정한 후에 안전하다고 판단되면 요청을 허가.

- 안전 상태(safe state) : 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄수 있는 상태

- 불안전 상태(unsafe state) : 교착상태 발생 가능성이 있다.

Deadlock Avoidance 방법인 banker's alogrithm

자원할당요청->안전한지 판단->안전하면 자원할당 그렇지 않으면 할당 거부

: 시스템이 자원을 할당한 후에도 안정상태로 남아있는지 검사하여

 안전 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기한다.

Avaliable vector : 사용 가능한 자원의 수

Claim matrix : 각 프로세스의 최대 자원 요구의 수

Allocation matrix : 각 프로세스에 할당외어 있는 자원의수

C-A : 각 프로세스에 남아있는 필요한 자원의 수

■ safe state

■ unsafe state

P1 requests resource (1, 0, 1)를 허가했다고 가정하면… 

unsafe->p1요구를 허가할수 없다./데드락가능성이 있다.

Deadlock Detection(데드락 감지)

: 교착상태가 발생한 프로세스들을 알아내는 알고리즘을 통해

교착상태를 탐지하여 해결해주는 방식