[운영체제] Deadlock - 1
The Deadlock Problem
Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
Resource(자원) : HW/SW 포함 개념, 프로세스가 자원을 사용하는 절차(4가지가 있음 : Request, Allocate, Use, Release)
- 발생 조건 (4가지 모두 만족해야 함.)
1. Mutual Exclusion(상호 배제) : 하나의 프로세스만 자원을 사용할 수 있음. (독점적으로 자원을 사용)
2. No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음.
3. Hold and Wait (보유) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음.
4. Circular wait (순환대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함.
데드락 발생 확인 위한 자원 할당 그래프 (Resource-Allocation Graph)
사각형 : 자원
원 : 프로세스
화살표 :
1. 자원 -> 프로세스 : 프로세스가 자원을 갖고 있음.
2. 프로세스 -> 자원 : 프로세스가 자원을 요청.
DeadLock 유무?
-> 그래프에 cycle이 없으면 데드락 아님.
-> 있다면 ? 자원 당 인스턴스 하나면 : deadlock 발생, 그렇지 않다면 deadlock 발생 가능성 있음.
- 처리 방법
1. Deadlock Prevention (미연 방지) : Deadlock을 막을 수는 있지만 자원 이용율 저하. 전체 시스템이 나빠지는(starvation) 발생 가능성 높임. => 비효율적
4가지 필요 조건 중 어느 하나가 만족되지 않도록 함.
- Mutual Exclusion(상호 배제) : 하나의 프로세스만 자원을 사용할 수 있음.
- No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음.
=> 가져올 수 있는 자원을 가져올 수 없기에 생김. 자원을 preemption 할 수 있도록 설정.
- Hold and Wait (보유) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음. => 프로세스 시작 시 모든 필요한 자원을 할당 혹은 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법
2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
- Circular wait (순환대기) : 모든 자원 유형에 할당 순서를 정해 정해진 순서대로만 자원 할당.
필요한 자원들이 cycle이 만들어진 경우
[해결] 자원에 순서를 정함.
2. Deadlock Avoidance
자원 요청에 대한 부가적인 정보를 이용해 데드락의 가능성 없는 경우에만 자원 할당.
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.
: deadlock 가능성 전혀 없을 때만 자원 할당
프로세스가 시작할 때, 사용 최대 알고 있다 가정 -> deadlock 미리 피함.
deadlock 가능성이 있다면 자원을 아예 주지 않음.
- 자원의 instance 하나 : Resource allocation algorithm 사용
자원을 요청하게 되면 requst edge 로 (점선 -> 실선) : cycle이 생기지 않은 경우에만 요청 자원 할당.
- 자원의 instance 여러개 : banker's algorithm 사용
최대 가능요청 - 현재 가능 자원 = need
자원이 있지만 주지 않음.
ex P4가 요청을 한다면 가용 자원으로는 충족이 안되기에 기다리게 함.
3. Deadlock Detection and recovery
4. Deadlock Ignorance (아무 일도 하지 않음.)