데드락

•

일부 자원을 가지고 있으면서 내가 못가진 자원을 요구하는 것

Deadlock

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

4가지 조건

•

mutual exclusion(상호 배제)

◦

매 순간 하나의 프로세스만 독점적으로 자원을 사용

•

no preemption(비선점)

◦

프로세스는 자원을 스스로 내어놓고, 강제로 빼앗기지는 않음

•

hold and wait(보유 대기)

◦

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

•

circular wait(순환 대기)

◦

자원을 기다리는 프로세스간에 사이클이 형성됨

Resources

•

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

◦

IO device, CPU cycle, memory space, semaphore 등

•

프로세스가 자원을 사용하는 절차

◦

request, allocate, use, release

Resource Allocation Graph

•

Vertex

◦

Process P

◦

resource R

•

Edge

◦

request edge P → R

◦

assignment edge R → P

•

그래프에 cycle 이 없으면 deadlockdl 아니다.

•

그래프에 cycle 이 있으면

◦

자원당 인스턴스가 하나밖에 없으면 deadlock

◦

자원당 여러 인스턴스가 있으면 deadlock 가능성

•

왼쪽 그림에서는 2개의 사이클

◦

R2 → P1 → R1 → P2 → R3 → P3 → R2

◦

R2 → P2 → R3 → P3 → R2

◦

R2 가 2개의 인스턴스가 있더라도 R2 의 인스턴스 모두 사이클에 물려있기때문에 데드락 상태

•

오른쪽 그림은 1개의 사이클

◦

R1, R2 인스턴스가 각각 2개이고 그 중 하나의 자원은 열려있기때문에 데드락 X

Deadlock 처리 방법

•

deadlock prevention

◦

미연에 방지

◦

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

◦

hold and wait

▪

방법1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법

▪

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

◦

no preemption

▪

프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨

▪

CPU, memory 등 state 를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용

◦

circular wait

▪

자원의 할당 순서를 정함

◦

utilization 저하, throughput 감소, starvation 문제

•

deadlock avoidance

◦

미연에 방지

◦

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

◦

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

◦

프로세스가 쓸 자원의 양을 알고 있다고 가정하고 분석하여 데드락 회피

◦

resource allocation graph algorithm

◦

banker’s algorithm

•

deadlock detection and recovery

◦

deadlock 발생은 허용하되 그에 대한 detection 루틴을 둬 deadlock 발견시 recover

◦

자원을 빼고 더 간단하게 그린다.

◦

N^2 의 시간복잡도 → dfs 라서

◦

recovery

▪

모든 데드락된 프로세스를 abort

▪

데드락에 연루된 프로세스를 하나씩 abort

▪

자원을 빼앗고 process restart

•

deadlock ignorance

◦

책임 X

◦

대부분의 OS 가 채택

→ deadlock 은 드물게 발생한다고 보고 이에 대한 대비를 하는 것은 오버헤드를 높이기때문에 ignorance