교착상태
개요
다중프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 프로세스가 자원을 요청했을때, 짱원ㄴ을 사용할 수 없는 상활이 발생 할 수 있고, 그 경우 프로세슨는 대기 상태로 들어간다. 이처럼 대기 상태인 프로세스들이 결코 다시는 그 상태를 변경시킬수 없으면, 이런 상황을 교착상태(DeadLock) 라고 한다.
시스템 모델
프로세스가 OS에게 자원을 요청하면, OS는 이를 확인하고 해당 프로세스에게 자원을 할당한다.
정상적인 작동모드에서, 프로세스는 다음의 순서로만 자원을 사용할수 있다.
- 요청
- 프로세스는 자원을 요청한다. 자원이 다른프로세스에 의해 사용중인 상황과 같이 요청이 즉시 허용되지 않으면, 요창 프로세스는 자원을 얻을때까지 대기한다.
- 사용
- 프로세스는 자원에 대해 작업을 수행할 수 있다.
- 예를 들어 프린터가 자원이라면, 프로세스는 프린터로 인쇄를 할 수 있다.
- 방출
- 프로세스가 자원을 방출한다.
한 프로세스 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면, 그 프로세스 집합은 교착상태에 있다.
 |
|---|
| Mutex 락 사용시의 교착상태 |
교착상태의 특정
필요조건
교착상태는 한 시스템이 다음과 같이 네가지 쪼건이 동시에 성립될 떄 발생한다.
- 상호 배제(Mutual Exclusion)
- 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한번에 한 프로세스만이 그 자원을 사용할 수 았다.
- 점유하며 대기(Hold and Wait))
- 프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기 해야 한다.
- 비선점(No Preemption)
- 자원이 강쩨적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후, 그 프로세스에 의해 자발적으로만 방출 될 수 있다.
- 순환 대기(Circular Wait))
- 대기하고 있는 프로세스의 집합에서, 서로 다른 프로세스가 서로 필요한 자원을 점유하여 순환구조로 대기한다.
자원할당 그래프(Resource Allocation Grapth)
교착상태는 시스템 자원 할닽 그래프 라고 하는 방향그래프로 보다 정확하게 기술할 수 있다. 이 그래프는 정점 V 의 집합과 간선 E 의 집합으로 구별된다. 프로세스 P와 자원 R 일때, 방향간선 P -> R 은 요청간선(Request Ddge) 라 하며, R -> P 는 할당간선(Assignment Edge) 라 한다.
 |
|---|
| 자원 할당 그래프 |
자원 할당 그래프의 정의로부터, 우리는 만일 그래프가 사이클을 포함하지 않으면 시스템 내 어느 프로세스도 교착상태가 아님을 보일수 있다.
 |
|---|
| 교착상태를 가진 자원 할당 그래프 |
 |
|---|
| 사이클이 있으면서 교착상태가 아닌 자원 할당 그래프 |
위의 예에서, 프로세스 P2,P4가 끝나고 자원이 반납되면 남은 프로세스가 자원을 할당받게 되고, 고착상태 상황이 풀린다.
- Only one instance type -> deadlock
- multi instance type -> deadlock or not
교착상태 처리 방법
원칙적으로 교착상태 문제를 해결하기위해 세가지 다른방법이 있다.
- 시스템이 결코 교착상태가 되지 않도록 보장하기 위해 교착상태를 예방 하거나 회피 하는 프로토콜을 쩍용시킨다.
- 시스템이 교착상태가 되도록 허용한다면, 이를 회복 시킨다.
- 문제를 무시 하고, 교착상태가 시스템에서 결코 방생하지 않는 척 한다.
세번째 해결안이 Linux와 Winodws를 포함해 대부분의 OS가 사용하는 방법이다. 쯕, 교착상태를 해결하는것은 프로그램을 작성하는 개발자의 몫이다.
교착상태 예방
교착상태 예방(Deadlock Prevention) 이란, 교착상태가 발생하기 위한 필요조컨들 중 적어도 하나가 성립되지 않도록 보장하는 방법이다.
상호 배제(Mutual Exclusion)
공유 가능한 자원들을 배타적인 접근을 요구하지 않도록하여 교착상태에 관련될 수 없도록 한다.
점유하며 대기(Hold and Wait)
프로세스가 자원을 요청할 때는, 다른 자원들을 점유하지 않을 것을 반드시 보짱한다.
프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당받을것을 요구하거나, 프로세스가 자원을 전혀 가지고 있지 않을때만 자원을 요청할수 있도록 허용하는 방안이 있다.
이러한 방법에는 두가지 단점이 있다.
- 많은 자원들이 할당된 후, 오랜동안 사용되지 않기 때문에 자원의 이용도가 낮다.
- 기아상태를 유발시킬수 있다.
비선점(No Preemption)
만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원들이 선점된다. 즉 이들 자원들은 묵시적으로 방출된다.
대안으로, 한 프로세스가 어떤 자원들을 요청하면, 우리는 이들이 사용 가능한지를 검사한다. 사용가능하다면 할당하고, 사용이 불가능 하다면, 그 자원들이 추가의 자원을 위해 대기하고 있는 어떤 다른 프로세스에 할당되어 있는지를 검사한다.
순환 대기(Circular Wait)
순환대기 조건이 성립되지 않도록하는 한가지 방법은 모든 자원 타입들에게 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것이다.
교착상태 회피
교착상태 회피(Deadlock Avoidence) 이란, 프로세스가 일생동안 요구하고 사용할 자원에 대한 부갖적인 정보를 미리 제공할 것을 요구한다.
교착상태 예방을 통해 해결할떄, 가능한 부수적인 문제는 장치의 이용률이 저하되고, 시스템 처리율(Throughput)이 감소된다는 것이다.
교착상태 회피에 대한 가장 단순한 모델은, 각 프로세스가 자신이 필요로하는 각 타입의 자원마다 최대 수를 선언하도록 요구하는 것이다. 각 프로세스가 요청할 각 타입의 자원의 최대 수 정보를 미리 알 수 있다면, 시스템이 교착상태에 들어가지 않을것을 보장하는 알고리즘을 만들 수 있다.
안전 상태(Safe Sate)
시스템 상태가 안전 하단는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 교착상태를 발생시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다.
시스템의 상태가 안전하다면 교착상태가 아니다. 반면에 교착상태에 있는 시스템은 불안전한 상태에 있다. 하지만 불한전한 상태의 시스템이 반드시 교착상태를 발생시키지는 않는다.
 |
|---|
| 안전, 불안전, 그리고 교착상태 공간 |
자원할당 그래프 알고리즘(Resource Allocation Grapth Algorithm)
자원 할당 그래프의 변형을 사용하여 교착상태를 회피한다. 예약 간선(Claim Edge) 라는 새로운 간선을 추가한다. 예약 간선 P -> R는 P가 미래에 짜원 R을 요청할 것이라는 의미이다.
 |
|---|
| 교착상태 회피를 위한 자원 할당 그래프 |
 |
|---|
| 불안전 상태의 자원 할당 그래프 |
은행원 알고리즘(Banker’s Algorithm)
자원 할당 그래프 알고리즘은 종류마다 짜원이 여러개씩 있게되면 사용할 수 없다.
은행원 알고리즘을 도입한 시스템에서는 프로세스가 시작할 때 프로세스가 가지고 있어야할 자원의 최대 갯수를 자원 종류마다 미리 신고해야 한다.
은행원 알고리즘을 구현하기 위해 몇가지 자료구조가 필요하다. n이 프로세스의 수이고, m은 자원의 종류수 라고 하자.
- Available[ m ] indicates how many resources are currently available of each type.
- Max[ n ][ m ] indicates the maximum demand of each process of each resource.
- Allocation[ n ][ m ] indicates the number of each resource category allocated to each process.
- Need[ n ][ m ] indicates the remaining resources needed of each type for each process. ( Note that Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ] for all i, j. )
안정성 알고리즘(Safery Algorithm)
시스템이 안전한지 아닌지 알아내는 알고리즘은 다음과 같다.
- Let Work and Finish be vectors of length m and n respectively. 1.1. Work is a working copy of the available resources, which will be modified during the analysis. 1.2. Finish is a vector of booleans indicating whether a particular process can finish. ( or has finished so far in the analysis. ) 1.3. Initialize Work to Available, and Finish to false for all elements.
- Find an i such that both (A) Finish[ i ] == false, and (B) Need[ i ] < Work. This process has not finished, but could with the given available working set. If no such i exists, go to step 4.
- Set Work = Work + Allocation[ i ], and set Finish[ i ] to true. This corresponds to process i finishing up and releasing its resources back into the work pool. Then loop back to step 2.
- If finish[ i ] == true for all i, then the state is a safe state, because a safe sequence has been found.
자원요청 알고리즘(Resource Request Algorithm)
자원 요청이 안전하게 들엊줄 수 있는지를 검사하는 알고리즘이다.
- Let Request[ n ][ m ] indicate the number of resources of each type currently requested by processes. If Request[ i ] > Need[ i ] for any process i, raise an error condition.
- If Request[ i ] > Available for any process i, then that process must wait for resources to become available. Otherwise the process can continue to step 3.
- Check to see if the request can be granted safely, by pretending it has been granted and then seeing if the resulting state is safe. If so, grant the request, and if not, then the process must wait until its request can be granted safely.The procedure for granting a request ( or pretending to for testing purposes ) is:
- Available = Available - Request
- Allocation = Allocation + Request
- Need = Need - Reques
교착상태 탐지
만일 시스템이 교착상태 예방이나 교착상태 방지 알고리즘을 사용하지 않는다면 교착상태가 발생 할 수 있다. 이러한 시스템은 다음과 같은 알고리즘을 반드시 지원해야 한다.
- 교착상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
- 교착상태로부터 회복하는 알고리즘
각 자원타입이 한개씩 있는 경우(Single Instance of Each Resource Type)
모든 자원들이 한개의 인스턴스만 있다면, 대기 그래프(Wait for graph) 라고 한는, 자원 할당 그래프의 변형을 사용하여 교착상태 탐지 알고리즘을 정의할 수 있다.
 |
|---|
| (a) 자원 할당 그래프, (b) 대응되는 대기 그래프 |
각 자원타입을 여러개 가진 경우(Several Instance of a Resource Type)
대기 그래프의 경우, 각 쫑류마다 자원이 여러개씩 존재하는 상황일때는 사용항 수 없다.
은행원 알고리즘과 마찬가지로 시시각각 내용이 달라지는 자료구조를 사용하며, 알고리즘은 아래와 같다.
- In step 1, the Banker’s Algorithm sets Finish[ i ] to false for all i. The algorithm presented here sets Finish[ i ] to false only if Allocation[ i ] is not zero. If the currently allocated resources for this process are zero, the algorithm sets Finish[ i ] to true. This is essentially assuming that IF all of the other processes can finish, then this process can finish also. Furthermore, this algorithm is specifically looking for which processes are involved in a deadlock situation, and a process that does not have any resources allocated cannot be involved in a deadlock, and so can be removed from any further consideration.
- Steps 2 and 3 are unchanged
- In step 4, the basic Banker’s Algorithm says that if Finish[ i ] == true for all i, that there is no deadlock. This algorithm is more specific, by stating that if Finish[ i ] == false for any process Pi, then that process is specifically involved in the deadlock which has been detected.
교착상태로부터 회복
프로세스 종료(Process Termination)
프로세스를 중지시킴으로써 교착상태를 제거하기 위해 두 방법중 하나를 사용할 수 있다.
- 교착상태 프로세스를 모두 중지
- 이 방식의 경우 확실하게 교착상태의 사이클을 깰수 있지만, 비용이 크다.
- 교착상태가 쩨거될 때까지 한 프로세스씩 중지
- 각 프로세스가 중지될때 마다 교착생태 탐지 알고리즘을 호출하여 프로세스들이 아직도 교착상태에 있는지 확인하기 때문에 상당한 오버헤드가 유발한다.
만일 부분 종료방식을 사용한다면 교착상태인 프로세스들의 집합 중에서 교착상태를 깨트리기 위해 어느 프로세스를 중지해야 하는지 반드시 결졍 해야한다.
어느 프로세스를 중지시킬 것인지 결정하는데 다음과 같은 요인이 있다.
- 프로세스의 우선순위가 무엇인지
- 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는데 까지 더 필요한 시간
- 프로세스가 사용한 자원 타입과 수
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
- 프로세스가 대화형인지 일괄처리형 인지 여부
자원 선점(Resource Preemption)
자원 선점을 이용해 교착상태를 제거하기 위해선, 교착상테기 께어질 때까지 프로세스로부터 자원을 계속 선점해 이들을 다른 프로세스에게 준다.
교착상태를 제거하기 위해 선점이 필요하다면 다음의 세가지 사항들을 고려해야 한다.
- 희생자 선탱(Selection of Victim)
- 어느 자원과 어느 프로세스들이 선점될 것인지
- 후퇴(Rollback)
- 프로세스로 부터 자원을 선점할떄, 해당 프로세슨는 어떻게 해야하는지(중지, 안전한 상태로 후퇴)
- 기아 상태(Starvation))
- 자원들이 동일한 프로세스로부터 항상 선점되지 않도록 어떻게 보장할 것인지