[OS]교착상태(1)

📚교착상태의 개요

교착상태(DeadLock)는 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어서 결과적으로 어느 쪽도 영원히 진행하지 못하는 상태를 의미한다.

교착상태와 기아상태는 다른 의미를 가진다. 교착상태는 모든 프로세스가 자원획득 가능성 없이 무한히 대기상태인 것을 의미하고 기아상태는 프로세스의 일부가 자원획득 가능성이 있지만 계속 대기상태인 것을 의미한다.

📚교착상태의 특성

📄교착상태의 필요조건

• 상호배제 조건
  상호배제 조건(mutual exclusion)은 프로세스가 자원에 대한 배타적인 통제권을 요구하는 조건이다. 필요로하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야한다는 의미이다.

• 점유대기 조건
  점유대기 조건(hold and wait)은 프로세스가 이미 한 자원을 할당받아 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 또 다른 자원을 요청하여 해제되기를 기다리는 상황을 의미한다.

• 비선점 조건
  비선점 조건(no preemption)은 프로세스에 할당된 자원은 프로세스가 사용을 마치고 스스로 반환하기 전에는 해제되지 않는 것을 의미한다.

• 환형대기 조건
  환형대기 조건(circular wait)은 프로세스의 지원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기하는 상황을 의미한다.

📄자원 할당 그래프

교착상태를 표현하기 위해 자원할당 그래프를 이용할 수 있다. 자원할당 그래프는 방향 그래프이고 각 프로세스 p는 원으로 나타내고 자원 r은 사각형으로 나타낸다. 자원은 프린터나 디스크처럼 자원의 유형을 나타내고 각 자원 r마다 하나 이상의 단위자원을 가질 수 있어 사각형 위에 단위자원의 개수를 숫자로 표시한다.

프로세스 p가 r의 단위자원 하나를 요구할 때 요구간선이 하나 추가된다. 요구가 만족되면, 요구간선은 할당간선으로 바뀌고 사용이 끝나서 자원이 해제될 때 할당간선은 삭제된다.

📍자원할당 그래프로 나타낸 교착상태 필요조건

• 상호배제 조건: 한 시점에 하나의 단위자원은 하나의 프로세스에 할당되므로 하나의 할당간선으로 표현
• 점유대기 조건: 한 프로세스에 할단간선과 요구간선이 연결된 것으로 표현
• 비선점 조건: 가용한 단위자원이 없는 경우 요구간선으로 표현
• 환형대기 조건: 할당간선과 요구간선으로 만들어지는 사이클로 표현

자원할당 그래프에 사이클이 없으면 교착상태가 존재하지 않고, 사이클이 있을 경우 교착상태가 발생할 수도 있다. 교착상태의 필요조건이 모두 만족되었다고 해서 항상 교착상태가 발생하는 것은 아니다.

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

📄교착상태의 처리기법

1. 교착상태 예방(prevention)
   교착상태의 네 가지 조건이 동시에 만족되는 것을 피하게 만들어서 교착상태가 발생하지 않도록 예방하는 방법이다.

2. 교착상태 회피(avoidance)
   프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착상태가 발생하지 않도록 하는 방법이다.

3. 교착상태 탐지 및 복구(detection and recovery)
   교착상태의 발생 여부를 조사하고 교착상태가 발생하였다면 적절한 조치를 취해 정상상태로 복구하는 방법이다.

📚교착상태 예방

📄상호배제 조건 제거

공유할 수 있는 자원은 상호배제가 필요하지 않기 때문에 교착상태가 발생하지 않는다. 공유할 수 없는 자원은 반드시 상호배제를 따라야하므로 상호배제 조건을 제거할 수 없다.

📄점유대기 조건 제거

프로세스가 자원을 점유했을 때 대기하지 않도록 하거나 대기할 때 자원을 점유하고 있지 않도록 한다.

• 자원 점유 시 대기상황 제거
  프로세스가 처음에 필요한 모든 자원을 한꺼번에 요구하여 할당받으면 더 이상 자원을 요구할 일이 없으므로 점유대기 조건을 제거하게 된다. 하지만 자원을 미리 한꺼번에 점유하면 아무도 그 자원을 활용하지 못하기 때문에 자원 이용률이 떨어진다는 단점이 있다. 그리고 한꺼번에 요구한 자원 중 하나라도 할당받을 수 없다면 모든 자원을 할당받지 못하고 대기해야하기 때문에 기아상태에 빠질 수 있다.

• 대기 시 자원 점유 상황 제거
  프로세스가 새로운 자원을 요구할 때 먼저 할당받았던 자원을 모두 해제하면 점유한 자원이 없으므로 대기가 발생하더라도 점유대기 조건을 제거하게 된다. 하지만 이 방법은 프린터 같은 점유 도중 해제할 수 없는 자원에 적용할 수 없다는 문제점이 있다. 따라서 자원을 점유하는 중에 추가적인 요구가 발생하지 않도록 자원을 한꺼번에 할당받을 필요가 있다. 자원을 한꺼번에 할당받아야 한다면 이 방법 역시 기아상태와 낮은 자원이용률이라는 단점이 생긴다.

📄비선점 조건 제거

프로세스가 자원을 선점 가능하도록 해야 비선점 조건을 제거할 수 있지만 자원의 특성에 따라 선점이 불가능한 경우도 있어서 비선점 조건은 완벽하게 제거할 수 없다. 자원을 점유한 프로세스가 다른 자원을 요구할 때 대기가 발생한다면 할당받았던 자원을 모두 해제하여 다른 프로세스가 비선점 조건으로 대기할 가능성을 줄이는 방법이 있다. 프린터 같은 자원은 프로세스가 사용 중 다른 프로세스가 자원을 선점하면 문제가 발생할 수 있기 때문에 비선점 조건 제거를 적용할 수 없다.

📄환형대기 조건 제거

환형대기 조건을 제거하기 위해 일단 모든 자원에 일련번호를 지정한다. 모든 자원은 각각 서로 다른 자연수의 일련번호로 지정한다. 그 다음 두 가지 방법 중 하나를 따르도록 한다.

1. 프로세스는 자원을 요구할 때 일련번호 기준으로 항상 오름차순이 되도록 요구한다.

2. 프로세스가 자원을 요구할 때 그보다 일련번호가 큰 자원은 점유하고 있지 않도록 한다.

환형대기가 되려면 자원할당 그래프에 사이클이 존재해야 한다. 사이클이 존재하려면 어떤 프로세스는 점유 중인 자원의 일련번호가 대기 중인 자원의 일련번호보다 커야 한다. 하지만 위 방법을 따르면 점유대기 중인 프로세스는 항상 점유하고 있는 자원의 일련번호 보다 대기 중인 자원의 일련번호가 크게 되므로 사이클이 발생하지 않아 환형대기 조건을 제거하게 된다.

위 방법은 자원의 일련번호는 프로세스가 자원을 요구하는 순서에 맞게 설정되어야 하는데 프로세스마다 자원의 요구 순서가 다를 수 있어 자원의 일련번호 설정에 어려움이 있다. 그리고 프로세스의 자원 요구 순서가 일련번호의 오름차순을 지키지 못하면 일련번호가 큰 점유 중인 자원을 해제해야 하는데 해제가 불가능한 자원도 있을 수 있다.