Concurrency: Deadlock and Starvation Lecture #6 Concurrency: Deadlock and Starvation

자원(Resources) (1) 컴퓨터 자원의 예 Printers, tape drives, Tables, etc. 동일한 종류의 자원이 여러 개 존재 가능 프로세스는 운영체제에게 필요한 자원을 적절한 방법으로 요구하여 할당 받은 후에 그 자원을 사용할 수 있다 하나의 자원은 한 순간에 한 프로세스만 사용할 수 있다 프로세스의 경쟁적 자원 요청이 교착 상태를 유발 한 프로세스가 자원 A을 할당 받은 상태에서 자원 B를 요청 동시에 다른 프로세스가 자원 B를 할당 받은 상태에서 자원 A를 요청 두 개의 프로세스는 모두 블록된 상태를 유지(교착 상태) Operating System

자원(Resources) (2) 선점형 자원(Preemptable resources) can be taken away from a process with no ill effects 예: CPU, HDD, etc. 비선점형 자원(Nonpreemptable resources) will cause the process to fail if taken away 예: tape driver, printer, etc. Operating System

자원(Resources) (3) Sequence of events required to use a resource 자원 할당 요구(request the resource) 자원 사용(use the resource) 자원 해제(release the resource) 자원 할당 요구가 만족하지 못하면 프로세스는 자원을 사용할 수 있을 때까지 자원 요청, 휴면, 재요청 과정을 반복한다 requesting process may be blocked may fail with error code Operating System

교착 상태(Deadlocks) 시스템 자원에 대해 경쟁하거나 상호 통신하는 프로세스 집합의 영구적인 대기 상태 두개 이상의 프로세스가 시스템 자원을 경쟁적으로 요구하는 상황에서 발생한다 일반적으로 최적의 해결책은 없다 Operating System

교착 상태 발생 예제 Operating System

교착 상태가 발생하지 않는 예 Operating System

Reusable Resources Used by only one process at a time and not depleted by that use Processes obtain resources that they later release for reuse by other processes Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores Deadlock occurs if each process holds one resource and requests the other Operating System

Example of Deadlock Operating System

Another Example of Deadlock Space is available for allocation of 200Kbytes, and the following sequence of events occur Deadlock occurs if both processes progress to their second request P1 P2 . . . . . . Request 80 Kbytes; Request 70 Kbytes; . . . . . . Request 60 Kbytes; Request 80 Kbytes; Operating System

Consumable Resources Created (produced) and destroyed (consumed) Interrupts, signals, messages, and information in I/O buffers Deadlock may occur if a Receive message is blocking May take a rare combination of events to cause deadlock Operating System

Example of Deadlock Deadlock occurs if receive is blocking P1 P2 . . . Receive(P2); Receive(P1); . . . . . . Send(P2, M1); Send(P1, M2); Operating System

Resource Allocation Graphs Directed graph that depicts a state of the system of resources and processes Operating System

Resource Allocation Graphs Operating System

교착 상태 발생 조건 (1) 다음 3 가지 조건이 성립하면 교착 상태가 발생할 수 있다: 1: 상호 배제(Mutual exclusion) 단지 한번에 하나의 프로세스 만이 자원을 사용할 수 있다 2: 점유와 대기(Hold-and-wait) 하나의 프로세스가 다른 프로세스가 요구하는 자원을 할당 받은 상태에서 다른 자원의 할당을 요구한다 3: 비선점(No preemption) 자원을 강제적으로 선점할 수 없고 소유 프로세스가 작업을 종료한 후에 해제할 수 있다 Operating System

교착 상태 발생 조건 (2) 다음 조건이 존재하면 교착 상태가 발생한다: 4: 순환 대기(Circular wait) 하나의 프로세스가 다음 프로세스가 요구하는 자원을 가지는 경우가 반복되어 닫힌 체인(chain)을 구성하는 경우 Operating System

Operating System

교착 상태 발생 조건 (3) 순환 대기 조건이 해결되지 않으면 교착 상태가 발생한다 앞의 3 가지 조건이 존재하면 순환 대기 조건을 해결되지 않는다 위의 4 가지 조건은 교착 상태에 대한 필요 충분 조건이 된다 Operating System

교착 상태 처리 방법 교착 상태 무시(Deadlock ignoring) 교착 상태 예방(Deadlock prevention) 가능성이 희박한 사건으로 간주하여 무시하는 방법 교착 상태 예방(Deadlock prevention) 교착 상태 발생의 4 가지 조건 중에 하나를 허용하지 않는 방법 교착 상태 회피(Deadlock avoidance) 자원 할당이 교착 상태를 발생시키는 자원에 대한 요청을 인정하지 않는 방법 교착 상태 탐지(Deadlock detection) 항상 가능하면 자원 요청을 인정한다 주기적으로 교착 상태 발생을 탐지하고 발생한 경우 회복하도록 한다 Operating System

교착 상태 무시 타조 알고리즘 다음과 같은 조건에서는 적절한 접근법 일반적으로 UNIX와 Windows에서 채용 머리를 땅 속에 파묻고 아무런 문제가 없는 것처럼 대처 가장 단순한 접근법 다음과 같은 조건에서는 적절한 접근법 교착 상태가 아주 드물게 발생하는 경우 교착 상태 예방 비용이 매우 클 경우 일반적으로 UNIX와 Windows에서 채용 다음과 같은 측면에서의 trade-off가 존재 편리함(Convenience) 정확성(Correctness) Operating System

교착 상태 예방(Deadlock Prevention) 운영체제가 교착 상태 발생 가능성을 사전에 배제하도록 한다 간접적인 방법 상호배제, 점유와 대기, 비선점 조건 중에 하나를 허용하지 않는 방법 직접적인 방법 순환 대기 발생을 막는 방법 Operating System

간접 교착 상태 예방(1) 상호 배제(Mutual Exclusion) 점유와 대기(Hold-and-Wait) 이 조건의 해제를 허용할 수 없다 예: 한번에 단지 하나의 프로세스 만이 파일에 기록할 수 있다 점유와 대기(Hold-and-Wait) 프로세스가 한번에 필요한 모든 자원을 요청하도록 한다 모든 자원이 사용할 수 있을 때까지 프로세스는 대기 상태로 기다려야 한다 프로세스는 상당히 오랜 기간 동안 기다릴 수 있다 자원의 효율성이 떨어진다 Operating System

간접 교착 상태 예방(2) 비선점(No preemption) 자원의 상태를 쉽게 저장하고 복구할 수 있는 경우에 적절하게 지원할 수 있는 방법 예: CPU(processor) 등 Operating System

직접 교착 상태 예방(1) 순환 대기를 예방하는 프로토콜을 사용: 자원 타입별로 순서를 정의한다 예: R1: tape drives: O(R1) = 2 R2: disk drives: O(R2) = 4 R3: printers: O(R3) = 7 프로세스가 자원별 순서를 고려하여 자원을 요청하도록 한다 이전에 자원 R1을 요구하였으면 다음에는 R1 보다 순서가 높은 자원만을 요청하도록 한다 Operating System

직접 교착 상태 예방(2) 자원 순서 프로토콜에서는 순환 대기가 발생하지 않는다 Processes {P0, P1,…,Pn} are involved in circular wait iff Pi is waiting for Ri which is held by Pi+1 and Pn is waiting for Rn held which is held by P0 (circular waiting) under this protocol, this means: O(R0) < O(R1) < .. < O(Rn) < O(R0) impossible! 이 방법은 교착 상태를 예방할 수 있지만 자원을 비효율적으로 사용하게 된다 Operating System

교착 상태 회피(Deadlock Avoidance) 운영체제가 교착 상태가 발생하지 않는다고 판단될 때에 3 가지 발생 조건을 허용하도록 한다 예방 방법보다는 더 많은 병행성을 허용할 수 있다 두 가지 접근법: 자원 요청이 교착 상태를 유도하는 프로세스는 실행하지 않는 방법 자원 할당이 교착 상태를 유도하는 경우 추가적인 자원 요청을 인정하지 않는 방법 위의 접근법의 경우: 각 자원에 대한 최대 요청이 미리 정의되어야 한다 Operating System

자원 타입(Resource Types) 시스템 내의 자원을 자원 타입(resources types) 별로 구분하여 관리한다 각 타입별 자원은 일정한 양의 자원이 시스템에 존재한다 R(i) : 자원 타입 i 의 전체 자원 양 R(main memory) = 128 MB R(disk drives) = 8 R(printers) = 5 Operating System

Process initiation denial C(k,i) : 프로세스 k의 자원 타입 i에 대한 요청 자원 수 프로세스 k는 실행을 인정 받기 위해 모든 자원 타입 i 에 대한 C(k,i)을 사전에 정의하여야 한다 V(i) : 할당되지 않은 자원 타입 i의 총 자원 수 V(i) = R(i) - S_k C(k,i) 새로운 프로세스 n은 다음조건을 만족할 때에 인정된다: C(n,i) <= V(i) for all resource type i 프로세스의 모든 자원 요청이 만족될 때에 프로세스 실행이 인정되므로 항상 교착 상태를 피할 수 있다 Operating System

Resource allocation denial: the banker’s algorithm 프로세스에 대한 자원 할당은 은행에서의 대출 작업과 유사하다 은행에서는 모든 고객의 요구가 만족되지 않으면 대출할 수 없다 프로세스의 자원 요청에 대한 자원 할당이 교착 상태를 유발하는지를 검사하여 자원을 할당하도록 한다 Operating System

The banker’s algorithm(1) Banker 알고리즘은 프로세스의 자원 할당 요청에 대하여 요청 자원에 대한 할당이 안정 상태(Safe State)을 유도하는지를 검사한다: 안정 상태가 보장되면 자원을 할당한다 안정 상태가 보장되지 않으면 자원 요청을 거부한다 안정 상태(Safe State) 모든 프로세스가 교착상태에 발생시키지 않고 종료할 수 있도록 하는 자원 할당 순서가 존재하는 경우 Operating System

The banker’s algorithm(2) 시스템 상태: R(i) : 자원 타입 i의 총 자원 양 C(k,i) : 프로세스 k가 요청하는 자원 타입 i의 자원 양 A(k,i) : 프로세스 k가 할당된 자원 타입 i의 자원 양 V(i) : 현재 사용 가능한 자원 타입 i의 자원 양 i.e. V(i) = R(i) - S_k A(k,i) N(k,i) : 프로세스 k가 작업을 완료하기 위해 필요로 하는 자원 타입 i의 자원 양 i.e. N(k,i) = C(k,i) - A(k,i) Operating System

The banker’s algorithm(3) Q(k,i) : 프로세스 k가 자원 타입 i에 대해 요구하는 자원 양 banker’s algorithm 다음 과정을 통해 자원 요청에 대해 자원을 할당한 것인지를 결정한다 모든 자원 타입 i에 대해 Q(j,i) <= N(j,i) 을 만족하는 지를 검사한다. 만족하지 않으면 자원 할당 요청을 거부한다 모든 자원 타입 i에 대해 Q(j,i) <= V(i) 을 만족하는지를 검사한다. 현재 자원이 사용할 수 있는 상태가 아니므로 자원 할당 요청을 거부한다 Operating System

The banker’s algorithm(4) banker’s algorithm cont’n 현재 자원 할당 요청에 대해 자원 할당을 가정하고 다음과 같이 새로운 자원 할당 상태를 계산한다 V(i) = V(i) - Q(j,i) for all i A(j,i) = A(j,i) + Q(j,i) for all i N(j,i) = N(j,i) - Q(j,i) for all i 새로운 자원 할당 상태가 안정 상태인지를 검사한다 안정 알고리즘(Safety Algorithm) 안정 상태가 되면 자원을 할당한다 그렇지 않으면 프로세스는 자원 할당이 가능할 때까지 기다려야 한다 Operating System

Banker’s algorithm 예제 (1) 다음과 같은 시스템 상태를 가정한다 : 3가지의 자원 타입 : R(1) = 9, R(2) = 3, R(3) = 6 아래의 초기 상태를 가지는 4개의 프로세스 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 1 0 0 5 1 1 2 1 1 0 0 2 1 1 2 P1 P2 P3 P4 R1 R2 R3 프로세스 P2가 Q = (1,0,1) 자원 할당을 요청할 때에 자원을 할당할 것인가? Operating System

Banker’s algorithm 예제 (2) 새로운 상태가 안정상태가 되는지를 검사한다 안정 알고리즘 P2  P1  P3  P4 자원 할당 요청에 대하여 자원을 할당한다 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 1 0 0 6 1 2 2 1 1 0 0 2 0 1 1 P1 P2 P3 P4 R1 R2 R3 현재 사용 가능한 자원이 있으므로 자원 할당을 가정하면 다음과 같은 새로운 자원 할당 상태가 된다 Operating System

Banker’s algorithm 예제 (3) Claimed Allocated Available P1 P2 P3 P4 3 2 2 0 0 0 3 1 4 4 2 2 R1 R2 R3 1 0 0 2 1 1 0 0 2 6 2 3 프로세스 P2 실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 3 1 4 4 2 2 R1 R2 R3 2 1 1 0 0 2 7 2 3 프로세스 P1실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 4 2 2 R1 R2 R3 0 0 2 9 3 4 프로세스 P3 실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 R1 R2 R3 9 3 6 프로세스 P4실행 : Operating System

Banker’s algorithm 예제 (4) 만약 초기 상태에서 프로세스 P1가 Q = (1,0,1) 자원할당을 요청하면 자원 할당을 가정하는 경우 다음과 같은 새로운 상태가 된다 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 2 0 1 5 1 1 2 1 1 0 0 2 0 1 1 P1 P2 P3 P4 R1 R2 R3 새로운 상태는 안정 상태가 되지 않는다 따라서 프로세스 P1의 자원 할당 요청을 거부한다 Operating System

Banker’s algorithm: 요약 안정 상태는 교착 상태가 되지 않는다 불안정 상태가 반드시 교착 상태가 되는 것은 아니다 예: 앞의 예제에서 프로세스 P1가 자원 타입 1과 3 의 자원을 잠시 해제하게 되면 안정 상태로 돌아간다 몇몇 프로세스가 불필요하게 기다리게 된다 최적으로 자원을 활용할 수 없다 교착 상태 회피 알고리즘은 프로세스들이 독립적이라고 가정한다 Operating System

교착 상태 탐지(Deadlock Detection) 자원 할당 요청에 대해 가능하면 자원을 할당한다 운영체제는 다음과 같은 작업을 수행한다 교착 상태가 발생하는지 검사한다 교착 상태가 발생하면 회복 작업을 수행한다 자원 할당 요청이 발생할 때마다 교착 상태 발생 여부를 검사한다 빈번한 교착 상태 검사는 CPU 시간을 낭비하게 된다 Operating System

교착 상태 탐지 알고리즘 은행가 알고리즘(Banker’s Algorithm)과 유사 각 프로세스가 교착 상태가 아니라고 가정하고 모든 프로세스을 실행 가능 여부를 표시하지 않는다 다음 과정을 수행한다 Mark each process j s.t A(j,i) = 0 for all resource type i. (since these are not deadlocked) Initialize work vector : W(i) = V(i) for all i REPEAT: Find a unmarked process j such that Q(j,i) <= W(i) for all i. Stop if such j does not exists If such j exists: mark process j and set W(i) = W(i) + A(j,i) for all i. Goto REPEAT At the end: each unmarked process is deadlocked Operating System

Request Allocated Available 교착 상태 탐지 예제 Mark P4 since it has no allocated resources Set W = (0,0,0,0,1) P3’s request <= W. So mark P3 and set W = W + (0,0,0,1,0) = (0,0,0,1,1) Algorithm terminates. P1 and P2 are deadlocked 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 R1 R2 R3 R4 R5 P1 P2 P3 P4 Request Allocated Available 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 Operating System

교착 상태 회복(Deadlock Recovery)(1) 교착 상태가 발생하였을 때 다음과 같은 회복 방법을 사용할 수 있다 교착 상태가 된 모든 프로세스 중지한다 운영체제에서 적용하는 일반적인 방법 교착 상태가 된 프로세스의 를 이전의 검사 시점으로 되돌리고 다시 실행한다 원래의 교착 상태가 발생할 가능성 있다 교착 상태가 존재하지 않을 때까지 교착 상태가 된 프로세스를 계속적으로 중지시켜 나간다 매번 교착 상태 탐지 알고리즘을 실행하여야 한다 교착 상태가 존재하지 않을 때까지 하나의 프로세스에서 자원을 선점하여 다른 프로세스에게 할당한다 자원을 선점 당하는 프로세스는 자원 할당 이전의 상태로 되돌려 놓아야 한다 Operating System

교착 상태 회복(Deadlock Recovery)(2) 교착 상태 회복 기법에서 희생 프로세스를 선택하는 방법: 현재까지 CPU 시간을 적게 사용한 프로세스 현재까지 할당된 자원의 양이 적은 프로세스 현재까지 수행한 작업이 적은 프로세스 등 Operating System

통합 교착 상태 전략 일반적으로 여러 가지 접근법을 통합하여 교착 상태를 관리한다 자원을 종류별로 그룹을 구성하고 순서를 할당한다. 예를 들면, Swappable space (secondary memory) Process resources (I/O devices, files...) Main memory... 자원 그룹 간에 교착 상태를 방지하기 위하여 순환 대기 예방 접근법을 사용한다 자원 그룹 내의 교착 상태는 각 그룹 별로 가장 적절한 접근법을 사용한다 Operating System

Strengths and Weaknesses of the Strategies Operating System

UNIX Concurrency Mechanisms Pipes Messages Shared memory Semaphores Signals Operating System

Operating System

Linux Kernel Concurrency Mechanisms Includes all the mechanisms found in UNIX Atomic operations execute without interruption and without interference Operating System

Linux Atomic Operations Operating System

Linux Atomic Operations Operating System

Linux Kernel Concurrency Mechanisms Spinlocks Used for protecting a critical section Operating System

Operating System

Linux Kernel Concurrency Mechanisms Operating System

Solaris Thread Synchronization Primitives Mutual exclusion (mutex) locks Semaphores Multiple readers, single writer (readers/writer) locks Condition variables Operating System

Operating System

Windows Synchronization Objects Operating System