[운영체제] 07 Deadlock

gramm·2021년 1월 30일

운영체제

목록 보기

7/14

내용 출처

KOCW 반효경 교수님 <운영체제> 강의

반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,

이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.

Deadlock (교착상태)

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

Resource (자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- ex. I/O device, CPU cycle, Memory space, Semaphore 등
- 프로세스가 자원을 사용하는 절차
  - Request, Allocate, Use, Release
Deadlock 예시
- 시스템에 2개의 tape drive가 있다.
- 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

Deadlock 발생의 4가지 조건

Mutual exclusion (상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
No premmption (비선점)
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
Hold and wait (보유 대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 내놓지 않고 계속 가지고 있는다.
Circular wait (순환 대기)
자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
(ex. Philosopher's Dining Problem)

자원 할당 그래프

Deadlock이 발생했는지 여부를 확인하기 위한 그래프

Assignment Edge (R -> P) : 자원이 프로세스에 할당되어 있다.
Request Edge (P -> R) : 프로세스가 자원을 요청했지만 아직 할당받지는 못한 상태다.

그래프에 cycle이 없으면 deadlock이 아니다.
그래프에 cycle이 있으면
- 자원 당 인스턴스가 하나밖에 없다면 deadlock이다.
- 자원 당 인스턴스가 여러 개라면 deadlock일 수도, 아닐 수도 있다.

첫 번째 그림 : cycle이 없으므로 deadlock이 아니다.

두 번째 그림 : cycle이 있고, 자원에 인스턴스가 2개씩 있는데, 관련된 프로세스가 모두 cycle 내에 있으므로 deadlock이다.

세 번째 그림 : cycle이 있고, 자원에 인스턴스가 2개씩 있는데, 자원에 연결된 프로세스 중 P2와 P4는 사이클 내에 있지 않으므로 deadlock이 아니다. R1이 P2에, 혹은 R2가 P4에 자원을 내어줄 경우 cycle이 사라질 것이기 때문이다.

Deadlock의 처리 방법

Deadlock Prevetion
자원 할당시 deadlock의 4가지 조건 중 하나가 만족되지 않도록 한다.
Deadlock Avoidance
자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.
Deadlock Detection and Recovery
deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover한다.
Deadlock Ignorance
deadlock을 시스템이 책임지지 않는다.
UNIX를 포함한 대부분의 OS가 채택하고 있는 방식이다.

위로 갈수록 강한 방식이다.

1번, 2번 - deadlock이 생기지 않게 미연에 방지하는 방식
3번, 4번 - deadlock이 생기도록 놔두는 방식

현재의 운영체제가 대부분 deadlock ignorance를 채택하는 이유 : deadlock은 빈번하게 발생하지 않으므로, 이를 미연에 방지하기 위해 많은 오버헤드를 들이는 것이 현재의 시스템에서는 비효율적이다.

Deadlock Prevention

Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 한다.
Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 한다.
  (단, 이 방법은 비효율적이다.)
- 방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하게 한다.
No Preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용된다.
  (CPU, Memory 등)
Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
- 예를 들어, 순서가 3인 자원 $R_i$ 를 보유 중인 프로세스가 순서가 1인 자원 $R_j$ 을 할당받기 위해서는 우선 $R_i$ 를 release해야 한다.

[문제점]

자주 발생하지도 않을 deadlock 때문에 많은 제약조건을 달아서 비효율적이다.

Deadlock Avoidance

자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당한다.

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

safe state
- deadlock이 일어나지 않는 상태
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
- 시스템이 safe state에 있으면 -> no deadlock
- 시스템이 unsafe state에 있으면 -> possibility of deadlock
  (unsafe state에 있다고 해서 반드시 deadlock이 발생하는 것은 아니다.)
safe sequence
- 프로세스의 sequence < $P1, P2, …, Pn$ >이 safe하려면 $P_i$ 의 자원 요청이 "가용 자원 + 모든 $P_j (j<i)$ 의 보유 자원"에 의해 충족되어야 한다. (아래 Banker's Algorithm으로 이해하기)
- 조건을 만족하면 다음의 방법으로 모든 프로세스의 수행을 보장한다.
  - $P_i$ 의 자원 요청이 즉시 충족될 수 없으면 모든 $P_j$ 가 종료될 때가지 기다린다.
  - $P_{i-1}$ 이 종료되면 $P_i$ 의 자원요청을 만족시켜 수행한다.

2가지의 avoidance 알고리즘

1) 자원의 인스턴스가 하나인 경우 : Resource Allocation Graph Algorithm

Claim Edge (Pi -> Rj) (점선)
- 프로세스 Pi가 자원 Rj를 적어도 한번은 요청할 수 있다.
Request Edge (Pi -> Rj) (실선)
- 프로세스가 해당 자원 요청시 claim edge가 request edge로 바뀐다.
Assignment Edge (Rj -> Pi) (실선)
- 자원 Rj를 프로세스 Pi에 실제로 할당한다.
- request edge가 assignment edge로 변경될 때, (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
- Rj가 release되면 assignment edge는 다시 claim edge로 바꾼다.

세 번째 그림이 deadlock은 아니다. 점선은 평생에 한번 자원을 요청할 수 있는 것을 의미하지, 현재 자원을 요청한 것을 의미하지는 않기 때문이다. 하지만 deadlock avoidance는 deadlock의 가능성이 아예 없는 경우에만, 다시 말해서 점선을 포함해도 cycle이 생기지 않는 경우에만 자원을 할당한다. 그래서 P2가 R2를 요청했을 때, R2를 아무도 가지고 있지 않음에도 P2에 할당하지 않는다.

2) 자원의 인스턴스가 여러 개인 경우 : Banker's Algorithm

프로세스 : P0 ~ P4 / 자원 : A(10), B(5), C(7)

Allocation : 현재 프로세스별 할당된 자원 현황
Max : 프로세스가 평생 사용하게 될 최대 자원의 수
Available : 현재 사용 가능한 자원의 수 (총 자원 - 할당된 총 자원)
Need : 추가 요청 가능한 자원의 수 (Max - Allocation)

Banker's Algorithm은 프로세스가 최대 요청을 할 것이라고 가정하고, 그것이 현재 가용 가능한 (Available한) 자원으로 충족되는 경우에만 자원을 프로세스에 할당한다. 즉, 해당 프로세스의 Need <= Available인 경우에만 그 프로세스에 자원을 할당한다.

ex1. P0이 (1, 0, 0)을 요청한 경우
P0의 Need는 (7, 4, 3)이고, Available은 (3, 3, 2)이므로 받아들이지 않는다.
ex2. P1이 (1, 0, 2)를 요청한 경우
P1의 Need는 (1, 2, 2)고, Available은 (3, 3, 2)이므로 받아들인다.

sequence <P1, P3, P4, P2, P0>가 deadlock이 생기지 않는 safe sequence이므로, 이 시스템은 safe state하다.

Deadlock Detection and Recovery

1. Deadlock Detection

1) 자원 당 인스턴스가 하나인 경우 : 자원 할당 그래프

자원 할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
(단, 자원 당 인스턴스가 하나인 경우에도 Banker’s Algorithm을 쓸 수 있다. 이것이 더 간단한 방법이기도 하다.)

자원의 최대 사용량을 미리 알릴 필요가 없으므로 그래프에 점선이 없다.

자원 당 인스턴스가 하나밖에 없는 상황에서 자원 할당 그래프에서 자원을 빼고, 거기에 대응하는 wait-for graph로 바꿔줄 수 있다. 이때 자원 할당 그래프의 cycle과 wait-for 그래프의 cycle은 같은 의미를 지닌다.

wait-for graph는 프로세스만으로 node가 구성된다. Pk에서 Pj로 향하는 실선은 Pj가 가지고 있는 자원을 Pk가 기다리고 있음을 의미한다.

wait-for graph에서 cycle를 찾는 시간 복잡도 : O(n^2)

cycle를 찾으려면 모든 화살표를 찾아보아야 한다.
프로세스가 n개일 때, 화살표의 개수는 최대 $n(n + 1) / 2$ 개다.

2) 자원 당 인스턴스가 여러 개인 경우 : Banker’s Algorithm과 유사한 방법 활용

자원 : A(7), B(2), C(6)
Request : 추가 요청 가능량이 아니라, 현재 실제로 요청한 자원량

결과 : No deadlock (sequence <P0, P2, P3, P1, P4> will work!)

cf) 위 그림에서 P2가 자원 C를 하나 더 요청한 경우

결과 : 요청한 자원이 없는 프로세스가 P0밖에 없다. P0이 자원 B 하나를 반납하더라도, 다른 어떤 프로세스의 요청도 들어줄 수가 없다. 따라서 이 경우에는 deadlock이 발생한다.

2. Deadlock Revovery

Process termination (프로세스 종료시키기)
- 방법 1. deadlock에 연루된 프로세스를 모두 죽인다.
- 방법 2. deadlock cycle이 없어질 때까지 deadlock에 연루된 프로세스를 하나씩 죽인다.
Resource Preemption (자원 빼앗기)
- 비용을 최소화할 victim을 선정한다.
- safe state로 rollback하여 프로세스를 restart한다.
- starvation 문제
  - 동일한 프로세스가 계속해서 victim으로 선정되는 경우
  - cost factor에 rollback 횟수도 같이 고려한다.

Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 하지 않는다.

deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 오버헤드일 수 있다.
만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다.
UNIX, Windows 등 대부분의 범용 OS가 채택하고 있다.

gramm

I thought I introduced

이전 포스트

[운영체제] 06 Process Synchronization

다음 포스트