Deadlock: 교착상태
- Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Deadlock 발생의 4가지 조건
- Mutual exclusion(상호배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
- No preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗지 않는다.
- Hold and wait(보유 대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있는다.
- Circular wait(환형 대기): 자원을 기다리는 프로세스들 간에 사이클이 형성된다.
Resource-Allocation Graph(자원할당그래프)
- R1 --> P1: P1이 R1을 점유하고 있다.
- P1 --> R1: P1이 R1을 기다리고 있다.
- 그래프에 cycle이 없으면 deadlock이 아니다.
- 그래프에 cycle이 있으면 자원 하나 당 사이클 하나가 있을 때 deadlock이다.
Deadlock의 처리 방법
- Deadlock Prevention: Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
- Deadlock Avoidance: 자원 요청에 대한 부가적인 정보를 이용해서, deadlock의 발생 가능성이 아예 없는 경우에만 자원을 할당하는 것
- Deadlock Detection and Recovery: Deadlock 발생은 허용하되, 그에 대한 deadlock 루틴을 두어, deadlock 발생 시 recovery하는 것
- Deadlock Ignorance: Deadlock을 시스템이 책임지지 않는다.
Deadlock Prevention
- Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
▶ Mutual Exclusion: 공유해서는 안되는 자원의 경우, 반드시 성립해야 한다. (무산 불가능)
▶ No Preemption --> Preemption(CPU, memory)
▶ Hold and Wait --> 프로세스가 자원을 요청할 때, 다른 어떤 자원도 가지고 있지 않도록 한다.
- 방법1) 프로세스 시작 시, 모든 필요한 자원을 할당받게 하는 방법(낭비)
- 방법2) 자원이 필요한 경우, 보유 자원을 모두 내놓고 다시 요청하도록 하는 방법
▶ Circular Wait --> 모든 자원 유형에 대해 할당 순서를 정하여, 정해진 순서대로만 자원을 할당하도록 한다.
--> Utilization 저하, Throughput 감소, Starvation 문제
Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서, deadlock의 발생 가능성이 아예 없는 경우에만 자원을 할당하는 것
▷ 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 한다.
- R1 --> P1: P1이 R1을 점유하고 있다.
- P1 --> R1(점선): P1이 R1을 미래에 요청할 수 있다.
- P1 --> R1(실선): P1이 R1을 요청한다.
▷ 점선을 포함하여, cycle이 생기지 않는 경우에만 요청 자원을 할당한다. (점선 --> 실선으로 바뀌면 deadlock이 발생할 수 있기 때문)
'운영체제' 카테고리의 다른 글
[운영체제] KOCW 8 - Ch8: Memory Management (0) | 2023.06.09 |
---|---|
[운영체제] KOCW 7 - Ch7: Deadlock (0) | 2023.06.09 |
[운영체제] KOCW 6.2 - Ch6: Process Synchronization (0) | 2023.06.09 |
[운영체제] KOCW 6.1 - Ch6: Process Synchronization (0) | 2023.06.09 |
[운영체제] KOCW 5.3 - Ch6: Process Synchronization (0) | 2023.06.09 |