[OS]교착상태에 대한 모든 것-개념, 조건, 해결 방법

안녕하세요. 진또배기입니다. 오늘은 저번 포스팅에 이어서 교착상태에 대해 알아보도록 하겠습니다. 저번 포스팅에 교착상태에 대한 재미있는 이야기를 담았으니 궁금한 분은 방문해주세요!

0. 교착상태에 대한 재미있는 이야기 링크: 410leehs.tistory.com/11

교착상태에 대한 재미있는 이야기(Feat. 마지노선)

---

1. 교착상태란?

IT세계에서의 교착상태란 다중프로그래밍 구조에서 두 개 이상의 프로세스(일을 수행하는 동작 단위)가 하나의 자원을 차지하기 위해 무한정 대기하는 상태입니다. 따라서 이를 "교착상태에 빠진다"라는 표현을 씁니다.

---

2. 교착상태 예시

위의 설명한 개념만으로는 쉽게 이해하기에는 어렵다고 생각되어 예시를 하나 들어보겠습니다. 교착상태는 여러 부문에서 일어날 수 있지만, 상호 거래 패턴에서 가장 많이 일어나니 결제 거래를 예로 들어보겠습니다. 아래의의 표에 보이는 트랜잭션 1은 A가 B에게 포인트를 주는 로직이고 트랜잭션 2는 B가 A에게 포인트를 주는 로직입니다. 그리고 Member라는 테이블에 사람 A,B,C와 포인트가 있습니다.

교착상태 예시

표의 로직을 살펴보면 슈도코드는 다음과 같습니다.

1. 상대방에게 포인트를 주기 위해 먼저 자신의 포인트를 차감한다.
    1) 트랜잭션 1은 Member 테이블의 첫번 째 행에 접근하고 락을 걸고 점유한다. (표의 빨간색 로직)
    2) 트랜잭션 2는 Member 테이블의 두번 째 행에 접근하고 락을 걸고 점유한다. (표의 파란색 로직)
2. 차감한 포인트를 상대방에게 준다.

하지만 극악의 확률로 이 트랜잭션이 동시에 일어나게 된다면 다음 로직(초록색, 보라색 로직)을 수행하지 못하게 됩니다. 왜냐하면 트랜잭션1에서의 초록색 로직은 Member의 두 번째 행인 B에 접근해야 하는데 이것은 이미 트랜잭션 2가 점유하고 있기 때문입니다. 마찬가지로 트랜잭션2에서의 보라색 로직은 Member의 첫 번째행에 접근해야 하는데 이것은 이미 트랜잭션 1이 점유하고 있기 때문입니다. 이러한 상황이 일어났을 때, 교착상태에 빠졌다. 교착상태가 발생했다고 표현합니다.

---

3. 교착상태 발생의 필요충분조건

교착상태가 발생하기 위해서는 다음의 네가지 조건이 충족되어야 하는데, 이 네가지 조건중 하나라도 충족되지 않으면 교착상태가 발생하지 않습니다.

1) 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
즉, 공유하지 않고 오로지 나만 쓰는 상황이라고 할 수 있습니다.

2) 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
즉, 내가 어떤 공유된 자원을 가진 상태에서 또 다른 것을 요구할 때 발생합니다.

3) 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 빼앗을 수 없다.
즉, 내가 가진 공유 자원을 양보하지 않아서 더이상 진행되지 않을 때 발생합니다.

4) 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
즉, 실제로 교착상태(DeadLock)는 일직선일 때 발생하지 않습니다. 이말은 일직선이라면 우선순위가 있다는 것인데 우선순위가 정해지면 그것이 교착상태를 해결하는 방법이기때문에 일직선일 때 발생하지 않습니다.

---

4. 교착상태 해결방법

이를 해결할 수 있는 방법에는 4가지가 있습니다.

1) 교착상태 예방(Prevention) : 교착상태의 필요조건을 부정함으로써 교착상태가 발생하지 않도록 미리 예방하는 방법이다. (예시-순환대기, 비선점, 점유와 대기, 상호배제 4가지 필요조건 한 가지라도 부정)

2) 교착상태 회피(Avoidance) : 교착상태 가능성을 배제하지 않고 적절하게 피해나가는 방법이다.

(예시-은행원 알고리즘)
1. 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법입니다. (다익스트라 알고리즘은 나중에 포스팅하겠습니다!)
2. 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 합니다.
3. 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 합니다.
4. 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장합니다.

3) 교착상태 탐지(Detection) : 교착상태 발생을 허용하고, 발생 시 원인을 규명하여 해결하는 방법입니다.

(예시-자원할당 그래프)

4) 교착상태 회복(Recovery) : 교착상태 발견 후, 선형대기를 배제시키거나 자원을 중단하는 메모리 할당 기법입니다.

(예시-선점(희생자 선택, 롤백, 기아 상태 사항 고려), 프로세스 중지(회생자 선택))

---

오늘은 교착상태에 대한 모든 것을 알아보았습니다.

진또배기 올림