[운영체제] Deadlocks

서지혜·2023년 8월 3일

TIL

목록 보기

19/22

🧭 CS Study - 운영체제

🚩 주제 : Deadlocks

🎥 강의 : KOCW 운영체제 강의 - 이화여자대학교 반효경 교수님

Deadlock

			https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

Deadlock은 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태를 말한다. 위 그림에서와 같이 두 프로세스 모두 필요한 자원을 각자 점유하고 있어서 그 누구도 실행되지 못한다. 여기서 자원은 하드웨어 혹은 소프트웨어 자원이다.

프로세스가 자원을 요청하는 단계는 1) 자원 요청, 2) 자원 획득, 3) 자원 사용, 4) 자원 반납이다.

Deadlock이 발생하는 4가지 조건

아래 네 가지 조건 중 하나라도 만족하지 못하면 Deadlock이 발생하지 않는다.

1. Mutual exclusion(상호 배제)
자원을 얻으면 독점적으로 사용한다. 매 순간 하나의 프로세스만 자원을 사용한다.

2. No preemption(비선점)
프로세스가 사용하는 자원을 빼앗지 않는다.

3. Hold and wait(보유 대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 자신이 가진 자원을 보유하고 기다린다.

4. Circular wait(순환 대기)
자원을 기다리는 프로세스간에 사이클이 형성된다.

Resource-Allocation Graph

			https://www.geeksforgeeks.org/resource-allocation-graph-rag-in-operating-system/

위 그림은 프로세스의 자원 할당 구조를 표현한 자원할당 그래프이다. 원은 프로세스를 의미하고 사각형은 자원을 의미한다. 자원 할당 그래프에 Cycle이 존재하는지에 따라서 Deadlock이 발생했는지 알 수 있다.

자원 할당 그래프에 사이클이 없다면 deadlock 상황이 아니다. 그러나 자원할당 그래프에 사이클이 생겼다면 그것은 deadlock 가능성이 있다.

만약 자원의 인스턴스가 1개인데 자원 할당 그래프에 사이클이 생긴다면 그것은 deadlock 상황이다. 그러나 자원의 인스턴스가 2개 이상인데 사이클이 생긴다면 그것은 deadlock 상황일 수도 있고 아닐 수도 있다. 자원의 인스턴스가 모두 점유된 상태에서 사이클이 생기면 deadlock이 발생하는 것이다. 그래서 인스턴스 2개가 모두 점유되었다면 deadlock 상황이고 인스턴스 1개만 점유되었다면 deadlock 상황이 아니다.

Deadlock의 처리 방법

1. Deadlock Prevention
자원 할당 시 Deadlock의 4가지 조건 중 하나라도 만족되지 않도록 막는것이다.

2. Deadlock Avoidance
deadlock의 가능성이 없는 경우에만 자원을 할당한다.

3. Deadlock Detection and recovery
deadlock 발생은 허용하되 그에 대한 detetion 루틴을 만들어서 deadlock이 발생하면 복구한다.

4. Deadlock Ignorance
deadlock을 시스템이 책임지지 않는다. 현대의 OS들은 이 방법을 선택한다. deadlock을 방지하기 위해 제약 조건을 많이 걸어두는 것은 성능저하를 유발할 수 있기 때문이다. 그래서 프로그램이 안돌아가는 상황이 생기면 사용자가 알아서 눈치채고 프로세스를 죽이도록 방치한다.

1. Deadlock Prevention

Deadlock의 네 가지 조건 중 한 가지라도 발생하지 않도록 막는 것이다.

Mutual Exclusion
발생을 막을 수 있는 조건이 아니다. 한 번에 하나의 프로세스만 사용할 수 있는 자원이라면 막을 수 없다.
Hold and Wait
프로세스가 자원을 보유하고 있을 때는 자원을 요청하지 못하게 막는다. 아래의 2가지 방법이 있다.

방법1. 프로세스가 시작할 때 필요한 모든 자원을 할당하는 방법
방법2. 자원이 필요할 때 보유 자원을 다 반납하고 요청하는 방법
No Preemption
자원을 Preemption 할 수 있게 만들면 발생하지 않는다.
Circular Wait
자원에 순서를 정해서 순서대로만 자원을 할당한다.

발생하지 않은 Deadlock을 미리 대비하기 위해 제약을 많이 걸기 때문에 성능 하락 가능성이 있다.
==> Utilization 저하, throughput 감소, starvation 문제 발생

2. Deadlock Avoidance

자원요청에 대한 부가 정보를 이용해서 Deadlock 가능성이 없는 요청만 자원을 할당한다. 프로세스를 시작할 때, 프로세스가 종료될 때까지 사용할 자원을 정의하고 가능성을 측정한다.

자원의 인스턴스가 1개일 경우 (Resource Allocation Graph algorithm)

						https://zitoc.com/deadlock-avoidance-algorithms/

상황
프로세스가 2개, 자원 2개가 있다. 자원으로부터 프로세스에게 가는 화살표는 자원이 프로세스에게 할당되었음을 의미한다. 점선으로 표시된 것은 미래에 자원을 요청할 수 있음을 의미한다.

두번째 그림에서 R2가 아무에게도 할당되지 않았기 때문에 p2에게 자원을 할당하면 점선을 포함해서 Cycle이 생길 위험이 있다. Deadlock Avoidance는 Deadlock의 가능성이 있는 p2에게 R2를 할당하지 않는다. 만약 p1이 R2를 요청한다면 Cycle이 발생하지 않기 때문에 자원할당이 가능하다.

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

			https://www.geeksforgeeks.org/bankers-algorithm-in-operating-system-2/

상황
프로세스 5개, 자원 3종류(A(10개), B(5개), C(7개))가 존재한다. 이때 각각의 프로세스가 아래와 같이 자원을 최대로 요청해야 할 경우, 적절한 자원 할당이 필요하다.

			https://www.geeksforgeeks.org/bankers-algorithm-in-operating-system-2/

만약 P1이 자원A 1개, 자원C 2개를 요청했다면 가용 자원을 초과하지 않으므로 자원 할당이 가능해야한다. 그러나 Banker's Algorithm은 프로세스의 자원 요청이 최대 요청이 아니더라도 항상 최대 요청이라고 가정하고 현재 가용자원이 최대요청에 충족하는지를 확인한다. 충족되면 요청을 받아드리고 충족되지 않으면 가용자원 범위 내의 요청이더라도 자원을 할당하지 않는다.

프로세스가 자신의 일을 마치고 자원을 반환하면 가용자원이 늘어난다. 그 이후에는 자원이 필요한 다른 프로세스에게 자원을 할당한다.

위 그림의 예제에서는 < p1, p3, p4, p2, p0> 의 sequence로 자원을 할당하고, 시스템은 safe state가 된다.

safe sequence
프로세스 sequence가 safe하려면 각 프로세스 자원요청이 '가용자원 + 이전까지 끝난 프로세스의 보유자원'에 의해 충족되어야 한다.

safe state
현재 남은 자원만으로도 프로세스들을 끝낼 수 있는 상태 / 프로세스들에 대한 safe sequence가 존재하는 상태이다.

Deadlock Avoidance 알고리즘은 프로세스 sequence가 safe한 상태에 머무르는 것을 보장한다.

3. Deadlock Detection and recovery

Deadlock이 발생할 수 있지만 자원 요청을 받고, Deadlock이 발생할 상황이 감지되면 recovery한다.

자원의 인스턴스가 1개인 경우

자원 할당 그래프에서 Cycle이 생기면 deadlock detection을 한다. (그래프 알고리즘(DFS, BFS)를 사용하면 Cycle이 생기는지 탐색할 수 있다.)

자원이 다수인 경우

Banker's algorithm과 유사하게 동작한다.

Recovery 방법

Process termination : 프로세스를 종료시키는 방법
방법1. deadlock에 관여되는 모든 프로세스를 abort(비정상 종료)한다.
방법2. deadlock에 관여되는 프로세스를 deadlock이 없어질 때까지 1개씩 abort한다.
Resource Preemption : 프로세스로부터 자원을 빼앗는 방법
비용을 최소화할 victim 프로세스를 선정한 뒤(deadlock 없애기) safe state로 rollback해서 프로세스를 재시작한다.

이 방법은 Starvation 문제가 발생할 가능성이 있다.
동일한 프로세스가 계속해서 희생자가 될 경우 starvation 문제가 발생한다. 그래서 deadlock이 발생했을 때 희생자를 선정하는 패턴(비용 최소화 및 프로세스가 희생자로 선정된 횟수 등)을 바꿔서 이러한 문제를 방지한다.