데드락이란?

할당받을 수 없는 자원을 요청해 더이상 실행할 수 없는 상태

프로세스 A,B는 리스소 X,Y를 가지고있어야 진행이 가능합니다. 하지만 A,B가 각각 Y,X를 점유하고 X,Y를 요청한다면, 영원히 X,Y를 동시에 획득하지 못하는 상황이 발생합니다.

운영체제에는 다양한 자원을 복잡한 방법으로 할당받아 사용하기에, 위와 같은 경우라고 해서 무조건 데드락이 발생하지는 않고, E.G 코프만 교수가 아래 4가지 조건이 모두 충족되어야만 데드락이 발생함을 보였습니다.

1. 상호배제. Mutual Exclusion: 두 개의 프로세스가 필요로 하는 자원을 배타적으로 점유해야 한다.
2. 비선점. Non Preemption: 프로세스의 실행중, 다른 프로세스가 자원의 점유를 빼앗을 수 없다.
3. 점유 대기. Hold and Wait: 할당된 자원을 가진 상태로 다른 자원을 기다린다.
4. 환형 대기. Circular Wait: 여러 프로세스가 순환적으로 자원 할당을 기다린다.

데드락 예방 방법

그러므로, 데드락을 예방하는 방법은 위 네 가지중 한가지를 부정해주면 됩니다.

1. 상호배제조건 제거: 자원을 배타적으로 점유하는 조건을 제거, 자원 공유
   1. 락을 사용하지 않았을 때의 문제점이 그대로 발생한다.
2. 비선점 조건 제거: 자원의 할당을 선점해올 수 있도록 방법 제공
   1. 구현이 매우 복잡해지며, 성능 오버헤드가 발생한다.
3. 점유대기 제거: 프로세스의 시작시점에 필요한 모든 자원을 요청한다
   1. 사용하지 않는 자원을 점유하고있는 비용과, 기아상태로 인한 무한대기가 발생한다.
4. 환형대기 제거: 자원을 선형으로 분류해 순서를 매기고, 증가하는 순서로만 자원을 요청. (TODO Check 필요)
   1. 가장 현실적인 방법. 이것마저도 꽤 큰 성능 오버헤드 발생

데드락 회피 방법

또, 데드락은 회피방법이 존재합니다. 예방방법과 달리, 운영체제가 실행중에 동작하는 방법이기에 회피방법이라 부릅니다.

교착상태가 발생할 수 있는 자원 할당을 피하고, 안전한 상태에서만 자원 할당을 하는 방법입니다.

앞선 예방방법에서도 비용 및 성능 오버헤드로 인한 한계점을 보았듯, 회복 방법 역시 태생적 한계점이 존재합니다.

1. 운영체제가 프로세스의 최대 자원 할당 수를 알고있어야 하고,
2. 프로세스의 수가 고정되어야 합니다 ( Process Create X )
3. 자원의 종류와 숫자가 고정되어야 합니다.

Banker’s Algorithm

TODO안전하지 않은 순서에 대한 예제 체크, 예시 고치기

다익스트라가 제안한것으로 유명한 은행원 알고리즘은, 대표적인 데드락 회피 방법입니다.

프로세스와 프로세스의 최대 할당 자원, 현재 할당 자원을 알고있을 때, 최대 할당자원을 넘어가지 않는 안전순서열을 만들어 자원을 할당하는 방법입니다.

운영체제는 총 14개의 자원을 갖고있다고 가정하겠습니다.

Process	최대 할당 자원 수	현재 할당 자원 수	필요한 자원 수
A	12	5	7
B	5	1	4
C	5	4	1

1. 현재 할당된 자원 수는 12개입니다. 가용 자원 수는 4개입니다.
2. C에 1개의 자원을 할당해 실핼시키고, C가 종료되어 5의 자원을 반환받습니다.
3. 현재 가용 자원 수는 8개입니다. (4 -1 + 5)
4. B에 자원 4개를 할당해 실행시키고, B가 종료되어 5의 자원을 반환받습니다.
5. 현재 가용 자원 수는 9개입니다 ( 8 - 4 + 5)
6. A에 7개의 자원을 할당하고, 모든 프로그램을 종료합니다.

자원을 안전하게 분배할 수 있는 순서는 C → B → A가 유일합니다. (Safe Sequence)

안전순서열로 보장된 실행순서로 프로세스를 실행하면 데드락을 회피할 수 있으며, 안전하지 않은 상태에서의 실행은 데드락이 발생할 수 있는 확률이 있음을 의미합니다.

은행원 알고리즘은 하나의 종류의 자원이 여러개 필요하다고 가정하고 시작한다는 한계가 있습니다. 사용된다고 하더라도, 프로세스 스케줄링 루틴은 자주 일어나는 작업인데, 낮은 빈도로 발생하는 데드락을 위해 스케줄링 과정에 프로세스를 감시해야 하므로 높은 오버헤드가 존재합니다.

데드락 탐지 및 복구방법

데드락 탐지 및 복구방법은 운영체제가 실행중에 동작하는 방법인것은 회피방법과 같지만, 이 방법은 데드락이 발생 후 처리하는 방식이라는 차이점이 있습니다.

먼저, 어떤 프로세스가 데드락 상태인지 판별하기 위해 Resourse Allocation Graph를 탐색해 데드락 상태인 프로세스를 탐지합니다. 이는 RAG의 자원 대기를 나타내는 그래프의 사이클을 판별하면 됩니다.

이미지 출처: https://velog.io/@jerry92/OS-교착상태deadlock의-조건과-해결-방법

사이클 내에 존재하는 프로세스는 아래 두 가지 방법중 하나로 데드락에서 탈출해야 합니다.

1. 프로세스 중단: 사이클에 속하는 하나 이상 또는 전체 프로세스를 중단합니다. 전체 프로세스를 중단하는것은 대규모 작업이 될 수도 있고, 연관된 다른 프로세스까지 종료하게 된다면, 작업 손실이 발생할 수도 있습니다.

   이에 프로세스 age나 우선순위 등을 고려해 한개씩 삭제하는게 좋습니다.

2. 자원 선점: 교착상테에 놓인 자원을 선점할 때까지 프로세스의 자원을 다른 프로세스가 선점하도록 하므로써 데드락을 탈출합니다.

Reference

OSTEP: Operating Systems: Three Easy Pieces

[HPC Lab. KOREATECH, OS Lecture](https://www.youtube.com/watch?v=es3WGii_7mc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN)

Wikipedia, Deadlock

Eng Wikipedia, Deadlock