교착상태(deadlock)
두 개 이상의 작업이 서로의 작업이 끝나기만을 기다리는 결과적으로 아무것도 못하는 상태
The Deadlock Problem
Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- 세마포어와 같은 CPU자원이나 tape drive같은 하드웨어가 될 수도 있다.
Deadlock의 발생 조건 (4가지)
-
Mutual exclusion(상호 배제) : 매 순간 하나의 자원을 하나의 프로세스만이 사용할 수 있는 경우
-
No preemption(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
-
Hold and wait(보유 대기) : 자원을 가진 프로세스가 자신이 가진 자원은 놓지 않고 다른 자원을 기다리는 경우
- 위 조건이 모두 만족되어도 교착상태가 발생하지 않을 수 있음. 4번 조건이 발생할 경우 데드락이 발생함.
- Circular wait(환형 대기) : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
Resource-Allocation Graphs(자원 할당 그래프)
-
그래프를 통해 deadlock이 발생하는지 확인
-
cycle이 발생한 경우(어떤 프로세스에서 출발하여 다시 그 프로세스로 돌아올 경우) ->
1. 자원이 여러개일 경우? : 데드락이 아닐수도 있음(사이클의 개수에 따라 다름) 2. 자원이 하나인 경우 : 무조건 데드락
- 운영체제 상식 시험에도 자주 나온다고 한다.
Deadlock의 처리(방지) 방법
❗ 위 두가지 방법은 데드락 방지, 아래 두가지 방법은 데드락 처리
-
Deadlock Prevention
-
Deadlock Avoidance
-
Deadlock Detection and recovery
-
Deadlock Ignoracne
Deadlock Prevention
-
Mutual Exclusion : 공유해서는 안되는 자원(CPU 등)의 경우 반드시 성립해야함. 자원 자체의 성격이기 때문에 방지하기는 어려움.
-
Hold and wait
- 프로세스가 자원을 요청할 때 다른 어던 자원도 가지고 있지 않아야 한다. 방법 1. 자원이 필요한 경우 모든 보유자원을 놓고 다시 요청 방법 2. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- No Preemption
-
Cpu, Memory는 빼앗을 수 있는 자원,
-
process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
-
모든 필요한 자원을 얻을 수 있을 때 그 프로세스 는 다시 시작된다.
- Circular Wait
- 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
Deadlock Avoidance
프로세스가 생성될 때 어느 정도의 자원을 사용할지에 대한 정보가 주어짐
-
Claim edge P1 -> R1
-
프로세스 P1이 자원 R1을 미래에 요청할 수 있음을 뜻함(점선으로 표시)
-
프로세스가 해당 자원 요청시 request edge로 바뀜
-
현재 요청받은 자원이 가용 자원이어도 미래에 데드락의 위험이 있을 경우 자원을 할당하지 않는 보수적인 방법
-
2 가지 경우의 avoidance 알고리즘
- single instance per resource types (자원당 종류 1개)ㅑ
-> Resource Allocation Graph algorithm 사용
- 2번 프로세스는 두 자원을 모두 미래에 받아야하는 실선이기 때문에 두 자원을 할당 받기 전에 1번 프로세스에게 첫번째 자원을 할당하고 그 다음에 2번 프로세스에게 자원을 할당한다(데드락 위험성 제거)
- Multiple instances per resource types
-> Banker's Algorithm 사용
-
위 그림은 각 프로세스에 할당되어있는 자원을 보여주는 그림이다.
-
현재 할당되어있는 자원을 제외한 자원을 가용자원으로 두고, 현재 가용자원 기준으로 처리할 수 있는 요청만 받아들이는 방식
Deadlock Detectiion and recovery
Deadlock 발생을 허용하되 발생할 경우 복구하는 방법
single instance
-
그래프를 그려서 데드락 확인
-
인스턴스가 하나인 경우 자원에서 프로세스, 프로세스에서 자원으로 가는 그래프가 아니라 프로세스에서 프로세스로 가는 그래프를 그려서 데드락을 찾아내면 된다.
multiple instance
-
Banker's Algorithm 사용
-
Avoidence와 다르게 요청한만큼 자원을 할당
-
Detection : 현재 요청한 자원량이 가용량보다 많을 경우 현재 요청이 없는 프로세스에서 자원을 가져와서 사용 -> 이러한 방식으로 현재 요청이 처리가 된다면 데드락 상태가 아니라고 판단
-
물론 위 방식은 매우 낙관적인 방법으로 당장 데드락인지 아닌지에 대한 판단을 하는 방법임
-
만약 요청한 자원을 가용자원 + 현재 요청이 없는 프로세스가 보유한 자원으로 해결할 수 없는 경우 -> 데드락으로 판단
Deadlock을 Detection 한 경우?
Recovery
-
Process termination
(1) : 데드락에 연루된 모든 프로세스를 운영체제가 강제종료시키는 방법
(2) : 데드락에 연루된 프로세스중 한 가지를 종료시키고 상태를 보는 방법 -
Resource Preemption
-
비용을 최소할 victim의 선정
-
safe state로 rollback하여 프로세스를 restart
-
이 경우 한 프로세스가 계속해서 victim할 가능성 고려
-> cost factor에 rollback횟수도 같이 고려
-
Deadlock Ignorance
Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방법
-
데드락 자체가 드물게 발생하는 문제이기 때문에 이에 대한 조치를 하는 것 자체가 큰 overhead라고 판단하여 아무런 조치도 취하지 않는 방법
-
이 경우 사용자가 직접 프로세스를 종료시키는 등의 방법이 있음
