교착상태(Deadlock)

교착상태의 정의
교착 상태(膠着狀態, 영어: deadlock)란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 교착상태는 멀티프로세싱에서 많은 작업들이 상호 배반적(mutually exclusive)으로 이루어지기 때문에 발생한다. 컴퓨터는 time-sharing이나 이나 real-time의 경우, 하나의 작업이 하드웨어를 독점적으로 사용하기 위해 하드웨어 록(hardware lock)을 설정하기 때문이다. 전산학에서 교착 상태란 멀티프로세싱 환경에서 흔히 발생할 수 있는 문제이다. 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.

교착상태는 자와 연필로 그림을 그리는 상황에 비유될 수 있다. 만일 한 사람이 연필을 가지고 있고, 또 다른사람이 자를 가지고 있다면, 교착상태는 연필을 가지고 있는 사람이 자를 필요로 하고, 자를 가지고 있는 사람이 연필을 필요로 할때 발생하게 된다. 자를 가지고 있는 사람이 연필을 포기하거나, 연필을 가지고있는 사람이 자를 포기하기 전까지 두 사람 모두 만족할 수 없는 상태에 빠지게 된다. 이를 교착상태라고 한다.

또 다른 예를 들어보자. 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 된다.

교착상태를 설명하기 위한 시스템 개념(모델)
- 시스템은 제한된 개수의 자원으로 구성
- 프로세스는 자원을 경쟁적으로 사용

정상상태에서의 프로세스 자원 사용 순서
(1) 요구
(2) 사용
(3) 해제(반납)

교착상태가 존재하기 위한 4가지 조건
(1971년  E. G. Coffman의 논문에 최초 언급되어서 Coffman조건이라고도 알려져 있음)
(1) 상호배제조건(Mutual exclusion): 한 프로세스가 자원을 사용하고 있을 때, 다른 프로세스는 기다려야 함
(2) 점유대기(Hold and wait): 프로세스가 다른 자원을 기다리면서, 이미 자신에게 할당된 자원은 해제하지 않고 점유하고 있음
(3) 비중단조건(no preemption): 자원 사용이 끝나기 전에 중도에 비자발적으로 해제될 수 없음
(4) 순환대기 (circular wait): 프로세스간 환형 사슬이 존재하여 각 프로세스는 다음 프로세스가 요구하는 자원을 가지고 있음

Example of deadlock conditions
An example of a deadlock which may occur in database products is the following. Client applications using the database may require exclusive access to a table, and in order to gain exclusive access they ask for a lock. If one client application holds a lock on a table and attempts to obtain the lock on a second table that is already held by a second client application, this may lead to deadlock if the second application then attempts to obtain the lock that is held by the first application. (But this particular type of deadlock is easily prevented, e.g., by using an all-or-none resource allocation algorithm.)

Another example might be a text formatting program that accepts text sent to it to be processed and then returns the results, but does so only after receiving "enough" text to work on (e.g. 1KB). A text editor program is written that sends the formatter with some text and then waits for the results. In this case a deadlock may occur on the last block of text. Since the formatter may not have sufficient text for processing, it will suspend itself while waiting for the additional text, which will never arrive since the text editor has sent it all of the text it has. Meanwhile, the text editor is itself suspended waiting for the last output from the formatter. This type of deadlock is sometimes referred to as a deadly embrace (properly used only when only two applications are involved) or starvation. However, this situation, too, is easily prevented by having the text editor send a forcing message (eg. EOF) with its last (partial) block of text, which message will force the formatter to return the last (partial) block after formatting, and not wait for additional text.

Nevertheless, since there is no general solution for deadlock prevention, each type of deadlock must be anticipated and specially prevented. But general algorithms can be implemented within the operating system so that if one or more applications becomes blocked, it will usually be terminated after a time (and, in the meantime, is allowed no other resources and may need to surrender those it already has, rolled back to a state prior to being obtained by the application).

Deadlock avoidance
Deadlock can be avoided if certain information about processes is available in advance of resource allocation. For every resource request, the system sees if granting the request will mean that the system will enter an unsafe state, meaning a state that could result in deadlock. The system then only grants request that will lead to safe states. In order for the system to be able to figure out whether the next state will be safe or unsafe, it must know in advance at any time the number and type of all resources in existence, available, and requested. One known algorithm that is used for deadlock avoidance is the Banker's algorithm, which requires resource usage limit to be known in advance. However, for many systems it is impossible to know in advance what every process will request. This means that deadlock avoidance is often impossible.

Two other algorithms are Wait/Die and Wound/Wait. In both these algorithms there exists an older process (O) and a younger process (Y). Process age can be determined by a time stamp at process creation time. Smaller time stamps are older processes, while larger timestamps represent younger processes.

Wait/Die	Wound/Wait
O is waiting for a resource that is being held by Y	O waits	Y dies
Y is waiting for a resource that is being held by O	Y dies	Y waits

Deadlock prevention
Deadlocks can be prevented by ensuring that at least one of the following four conditions occur:

(1) Removing the mutual exclusion condition means that no process may have exclusive access to a resource. This proves impossible for resources that cannot be spooled, and even with spooled resources deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.
(2)The "hold and wait" conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations); this advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to release all their resources before requesting all the resources they will need. This too is often impractical. (Such algorithms, such as serializing tokens, are known as the all-or-none algorithms.)
(3)A "no preemption" (lockout) condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, inability to enforce preemption may interfere with a priority algorithm. (Note: Preemption of a "locked out" resource generally implies a rollback, and is to be avoided, since it is very costly in overhead.) Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic concurrency control.
(4)The circular wait condition: Algorithms that avoid circular waits include "disable interrupts during critical sections" , and "use a hierarchy to determine a partial ordering of resources" (where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering) and Dijkstra's solution.

Deadlock detection
Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.

Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock.

Distributed deadlocks
Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing.

Phantom deadlocks are deadlocks that are detected in a distributed system but don't actually exist - they have either been already resolved or no longer exist due to transactions aborting.

Livelock
A livelock is similar to a deadlock, except that the state of the processes involved in the livelock constantly changes with regards to each other, none progressing. [1] Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing. [2]

As a real-world example, livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always both move the same way at the same time.

Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can repeatedly trigger. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action. [3]

See also

Banker's algorithm

Computer bought the farm

Deadlock provision

Dining philosophers problem

Gridlock (in vehicular traffic)

Hang

Infinite loop

Mamihlapinatapai

Race condition

Sleeping barber problem

Stalemate

Synchronization

the SPIN model checker can be used to formally verify that a system will never enter a deadlock.

교착상태 기술(Description)
시스템자원할당그래프(방향성 그래프)를 사용하여 기술함
G=(V, E)
V:꼭지점의 집합은 아래의 두 집합으로 구성됨
  - 프로세스의 집합 P={p1, p2, p3,,,pn}  (원으로 나타냄)
  - 자원의 집합 R={r1, r2, r3,,,rm} (사각형 내의 점으로 나타냄)
E:간선의 집합은 아래와 같은 두 가지의 순서쌍이 가능함
  - (pi, rj) : pi로부터 rj로 방향간선(directed edge)이 존재. pi가 rj를 요청하여 대기중인 상태.
                  요구간선(request edge)이라고 함.
  - (rj, pi) : rj로부터 pi로 방향간선(directed edge)이 존재. rj가 pi에 할당된 상태.
                  할당간선(assignment edge)이라고 함.
자원할당그래프에서 사이클이 존재하는 것이 교착상태의 충분조건은 아님.
사이클이 존재하지 않으면 교착상태는 존재하지 않음.
(각 유형의 자원이 여러 단위자원을 가지면 교착상태가 발생하지 않음)

교착상태에 관한 연구대상
Coffman조건 4가지를 모두 만족해야만 교착상태이므로, 위의 4가지 조건 중 어느 한가지가 성립하지 않는 상황을 만들거나, 그런 상황이 되도록 조정함으로써 교착상태를 방지할 수 있게 된다.

(1) 교착상태 방지
교착상태의 발생조건 네 가지 중 어느 한 가지를 발생하지 않도록 통제하면 교착상태를 방지할 수 있다.

상호배제조건 방지
 상호배제조건은 서로 공유될 수 없는 자원에 대해서는 반드시 따르는 조건이다. 공유할 수 있는 자원에 대해서도 특수한 경우에만 상호배제조건을 배제할 수 있다.(예:읽기 전용 자원 등)

대기조건 방지
대기조건이 발생하지 않도록 하려면, 프로세스가 자원을 요청할 때 그 프로세스는 어떤 자원도 할당되어 있지 않은 상태라야 한다. 대기조건 방지전략을 적용하면 자원이용률이 낮아지고, 기아상태(starvation)가 발생할 수 있다는 단점이 있음
방안1> 프로세스 수행 사전에 필요 예상 자원을 모두 할당받는 전략
방안2> 필요한 자원만 할당받되, 자원을 요청할 때에는 이전에 갖고 있던 자원을 반드시 해제하도록 하는 전략

비중단조건 방지
비중단조건 방지방법은 CPU나 레지스터,기억장치 등에 적용하기 좋으나, 프린터, 테이프드라이브 등에 적용 불가

환형 대기조건 방지
모든 자원의 유형에 대해서 일련번호를 지정하고, 교착상태 방지를 위해 프로세스는 항상 자원을 일련번호 순서(예:오름차순)으로 요청하도록 함.

(2) 교착상태 회피
교착상태 방지 기법은, 교착상태 조건 중 한 가지를 일어나지 않도록 하는 것인데, 이렇게 하면 장치 이용률(device utilization)이 크게 낮아지고 시스템의 성능이 저하됨

각 프로세스가 자신이 사용할 자원의 최대 요구량을 제시하도록 하는 방법이 사용될 수 있음

안전상태(safe state)
시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태. 안전순서열이 존재하는 상태를 말함.

불안전상태(unsafe state)
안전순서열이 존재하지 않는 상태를 말함. 불안전상태는 교착상태이기 위한 필요조건이다. 교착상태는 불안전상태에서만 발생한다. 안전상태 개념을 이용하여, 교착상태 회피 알고리즘 구성이 가능하며, 현재 가용자원을 프로세스 요청시 바로 할당해 줄 것인지, 기다리게 할 것인지를 결정하는 문제라고 볼 수 있다.

단일유형의 여러 자원이 존재하는 경우
가용자금을 할당하는 은행 시스템과 비슷해서 붙여진 이름. 시스템이 자원요청을 받으면, 할당해 주고 난 후의 상태를 가정하고, 그 상태가 안전상태인지를 확인한 후, 안전상태가 보장되는 경우에만 할당하는 것. 다음 네 가지에 대한 데이터 구조가 필요함
   1. 가용자원
   2. 최대요구
   3. 할당자원
   4. 추가요구
- 은행원 알고리즘(banker's algorithm)
- 안전 알고리즘 : 안전상태 여부 확인에 m X n^2 의 연산이 필요함

각 유형의 자원이 한 개 뿐일 경우

(3) 교착상태 발견
(4) 교착상태 회복




External links

Deadlock Detection Agents

Paper "Deadlock Detection in Distributed Object Systems" by Nima Kaveh and Wolfgang Emmerich

Article "Distributed Deadlock Detection" by JoAnne L. Holliday and Amr El Abbadi

Article "Deadlock detection in distributed databases" by Edgar Knapp

Article "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong

Paper "Confirmation of Deadlock Potentials Detected by Runtime Analysis" by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier

Citations by CiteSeer

Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971).

Paper Eliminating Receive Livelock in an Interrupt-driven Kernel by Jeffrey C. Mogul, K. K. Ramakrishnan

DeadLock at the Portland Pattern Repository

Etymology of "Deadlock"

참고문헌
1. http://leadbiz.tistory.com/145
2. 위키백과사전(교착상태)
3. http://en.wikipedia.org/wiki/Deadlock

관련자료

invalid-file

교착상태 프리젠테이션 파일(출처:http://syso.mju.ac.kr/0402/os/os.files/notes/os-ch7.ppt)