[운영체제] Chapter 7. Deadlocks 1, 2

조희연·2022년 1월 7일

Study

목록 보기

8/15

Chapter 7. Deadlocks 1, 2

위 그림처럼 일련의 프로세스들이 서로가 가진 자원을 기다리며 block되어 더 이상 진행이 될 수 없는 상태
이때 자원이란 HW, SW 등을 포함하는 개념
- 예) I/O device, CPU cycle, memory space, semaphore 등
프로세스가 자원을 사용하는 절차 : Request -> Allocate -> Use -> Release
- Request : 자원 요청
- Allocate : 자원 할당
- Use : 자원 사용
- Release : 자원 반납
Deadlock은 모든 프로세스가 Request 상태인 상황

Deadlock Example)

예를 들어, 세마포어 변수 A와 B가 있고 프로세스 P0이 P(A), P(B)를 순서대로 호출하고 P1이 P(B), P(A)를 호출한다고 가정하면 P0과 P1은 서로 각각 B와 A를 영원히 기다리는 상태가 되어버린다.

1. Mutual exclusion(상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2. No preemption(비선점)
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3. Hold and wait(보유대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

4. Circular wait(순환대기)
자원을 기다리는 프로세스간에 사이클이 형성되어야 함
ex) 프로세스 P0, P1, ... Pn이 있을 때 P0은 P1이 가진 자원을 기다림, P1은 P2이 가진 자원을 기다림, ... Pn은 P0이 가진 자원을 기다림

프로세스 간의 관계를 그래프로 도식화하면(자원 할당 그래프) 데드락이 발생할지 예상할 수 있다.

R : 자원 / P : 프로세스 / 자원 내의 동그라미 : 인스턴스의 개수
그래프에 cycle이 없으면(위의 그림에 해당) deadlock이 아니다.
그래프에 cycle이 있으면
- if only one instance per resource type(자원 당 하나의 인스턴스), then deadlock
- if several instances per resource type, posibility of deadlock

Prevention(미리 예방하는 방법)과 Avoidance(피하는 방법), Detection and Recovery(발생 시 처리하는 방법), Ignorance(무시하는 방법)으로 나뉜다.

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

Mutual Exclusion
- Critical Section Problem을 해결하기 위해서 이 조건은 반드시 만족해야 하므로 공유자원이 존재한다면, 이 조건은 만족시킬 수 밖에 없다.
Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록
- 프로세스를 시작할 때 모든 필요 자원을 할당받게 하거나, 자원이 필요한 경우 보유하던 자원을 모두 반납하고 다시 요청하도록
No preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우 보유하던 자원이 선점될 수 있도록
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스가 다시 시작된다.
Circular wait
- 자원의 타입에 따라 프로세스마다 할당 순서를 정해 정해진 순서대로만 자원이 할당되도록

-> 효율성과 처리량 감소, Starvation 발생 가능성 존재

자원 요청에 대한 부가정보를 이용해 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해 안전한 경우에만 할당
Safe Sequence : 프로세스의 sequence(P1, P2, ... Pn)가 있을 때, Pi의 자원 요청이 가용 자원 + 모든 Pj의 보유 자원에 의해 충족되는 경우 sequence를 safe하다고 말한다.
Safe state : 시스템 내의 프로세스들에 대한 Safe Sequence가 존재하는 상태(시스템이 Safe state에 있으면 deadlock은 발생하지 않음)

-> Deadlock Avoidance는 시스템이 Unsafe state에 들어가지 않는 것을 보장하는 것이다.

2.1 자원당 인스턴스가 하나밖에 없는 경우

점선으로 표시된 간선(Claim edge)은 프로세스가 자원을 미래에 요청할 수 있음을 의미한다.
자원을 요청할 경우, 실선(Request edge)으로 바뀌고 자원을 할당받으면 방향이 반대인 간선(Assignment edge)이 된다. 이후 자원을 모두 쓰고 반납하게 되면 다시 Claim edge로 바뀐다.
Deadlock을 피하는 방법은, Request edge가 Assignment edge로 변경될 때 점선을 포함해 사이클이 생기지 않는 경우에만 요청된 자원을 할당해주는 것이다.
두번째 그림의 경우, 데드락의 가능성이 있으므로 P2가 요청한 자원 R2를 주지 않음으로 데드락 발생을 방지한다.

2.2 자원당 인스턴스가 여러개 있는 경우 : Banker's Algorithm
-> 이는 프로세스가 자원을 요청할 때마다 수행된다.

가정)