운영체제 (Operating Systems) 교착상태 (Deadlocks) 문양세 강원대학교 IT대학 컴퓨터과학전공

강의 목표 병행 프로세스들의 집합이 작업을 완료할 수 없도록 하는 교착상태를 이해하고, 관련 기술들을 학습한다. 교착상태(Deadlocks) 병행 프로세스들의 집합이 작업을 완료할 수 없도록 하는 교착상태를 이해하고, 관련 기술들을 학습한다. 교착상태를 예방하거나 회피하는 여러 방법들을 이해한다.

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태 문제 자원을 점유한 상태에서 집합 내 다른 프로세스에 의해 점유된 자원을 얻기 위해 대기하면서 봉쇄된 프로세스 집합 교착상태(Deadlocks) 자원을 점유한 상태에서 집합 내 다른 프로세스에 의해 점유된 자원을 얻기 위해 대기하면서 봉쇄된 프로세스 집합 교착상태 예제 시스템은 2개의 하드디스크 드라이브를 가지고 있다. P1과 P2 각각의 프로세스는 하나 씩의 드라이브를 점유한 상태이고, 작업 진행을 위해 다른 하나도 필요로 한다. 다른 예제: 세미포 A와 B가 모두 1로 초기화된다. P0 P1 wait(A); wait(B) wait(B); wait(A)

다리 건너기 예제 트래픽은 오직 한 방향으로만 향한다. 다리의 각 부분은 하나의 자원으로 보일 수 있다. 교착상태(Deadlocks) 트래픽은 오직 한 방향으로만 향한다. 다리의 각 부분은 하나의 자원으로 보일 수 있다. 만약 교착상태가 발생할 때, 하나의 차가 뒤로 물러서면 (자원을 내어주 고 되돌리면) 교착상태가 해결될 수 있다. 교착상태가 발생하면, 여러 차들이 뒤로 물러나야 할 수도 있다. 기아(starvation)가 발생할 수도 있다.

시스템 모델(System Model) 자원 타입(유형) R1, R2, . . ., Rm 교착상태(Deadlocks) 자원 타입(유형) R1, R2, . . ., Rm 예제: CPU 사이클, 메모리 공간, 입출력 장비들 각 자원 타입 Ri는 인스턴스(instance) Wi를 가진다. 예제: CPU 자원 타입에 대한 인스턴스로 CPU1, CPU2 각 프로세스는 다음과 같이 자원을 사용한다. 요청(request): 만약 요청이 즉시 승인될 수 없다면, 요청하는 프로세스는 자원을 획득할 때까지 대기해야 한다. 사용(use): 프로세스는 자원을 이용한다. 방출(release): 프로세스는 자원을 놓아준다

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태의 특징 교착상태는 다음 네 가지 조건이 동시에 일어나면 발생한다. 교착상태(Deadlocks) 교착상태는 다음 네 가지 조건이 동시에 일어나면 발생한다. 상호 배제(mutual exclusion): 한 순간에 하나의 프로세스만이 자원을 사 용할 수 있다. 점유하며 대기(hold and wait): 한 개 이상의 자원을 점유한 프로세스가 다른 프로세스에 의해 점유된 자원을 추가적으로 획득하기를 기다린다. 비선점(no preemption): 자원을 점유 중인 프로세스는 작업을 마친 후에 만 자발적으로만 자원을 놓을 수 있다. 순환 대기(circular wait): 대기 중인 프로세스 집합 {P0, P1, …, Pn} 이 존 재한다. P0 는 P1에 의해 점유 중인 자원을 기다리고 있다. P1는 P2에 의해 점유 중인 자원을 기다리고 있다. . . . Pn–1은 Pn에 의해 점유 중인 자원을 기다리고 있다. Pn은 P0에 의해 점유 중인 자원을 기다리고 있다.

자원 할당 그래프 (Resource Allocation Graph) (1/2) 교착상태(Deadlocks) 교착상태는 시스템 자원 할당 그래프라고 불리는 방향 그래프(directed graph)로 더 정확히 설명될 수 있다. 그래프 G = (V, E), V = 점(vertex)들의 집합, E = 간선(edge)들의 집합 V는 다음 두 가지 유형으로 나뉜다: P = {P1, P2, …, Pn}, 시스템 내 모든 프로세스들의 집합 R = {R1, R2, …, Rm}, 시스템 내 모든 자원들의 집합 E는 다음 두 가지 유형으로 나뉜다: 요청 간선(request edge): 방향 간선 Pi  Rj (프로세스 i가 자원 j를 요청함) 할당 간선(assignment edge): 방향 간선 Rj  Pi (자원 j가 프로세스 i에 할당됨)

자원 할당 그래프 (Resource Allocation Graph) (2/2) 교착상태(Deadlocks) 프로세스 4개의 인스턴스를 가진 자원 타입 Pi가 Rj의 한 개 인스턴스를 요청한다. Pi가 Rj의 한 개 인스턴스를 점유하고 있다. 그래프에서 사이클이 발생하면 교착상태일 가능성이 있다. Pi Rj Pi Rj

자원 할당 그래프 예제 교착상태가 발생하는가? 발생하지 않는가? 교착상태가 아니다! 상호 배제: R1, R2, R3, R4 교착상태(Deadlocks) 교착상태가 발생하는가? 발생하지 않는가? 상호 배제: R1, R2, R3, R4 점유하며 대기: P1, P2 비선점: YES 순환 대기: NO  사이클이 발생하지 않음 교착상태가 아니다!

교착상태를 가진 자원 할당 그래프 교착상태가 발생하는가? 발생하지 않는가? 교착상태이다! 교착상태(Deadlocks) 교착상태가 발생하는가? 발생하지 않는가? 상호 배제: R1, R2, R3, R4 점유하며 대기: P1, P2, P3 비선점: YES 순환 대기: YES  사이클이 발생함 교착상태이다!

사이클이 있으나 교착상태가 아닌 경우 교착상태가 발생하는가? 발생하지 않는가? 교착상태(Deadlocks) 교착상태가 발생하는가? 발생하지 않는가? 상호 배제: R1, R2 점유하며 대기: P1, P3 비선점: YES 순환 대기: YES  사이클이 발생함 교착상태가 아니다! (P4가 R2를 방출하면 해결)

자원 할당 그래프와 교착상태 그래프에 사이클이 존재하지 않는다면  교착상태 없음! 그래프가 사이클이 존재한다면  교착상태(Deadlocks) 그래프에 사이클이 존재하지 않는다면  교착상태 없음! 그래프가 사이클이 존재한다면  자원 타입당 하나의 인스턴스만 존재한다면, 교착상태가 발생한다. 자원 타입당 여러 인스턴스가 존재한다면, 교착상태가 발생할 가능성이 있다.  교착상태가 발생하지 않을 수도 있다.

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태 처리 방법 1. 시스템이 교착상태로 들어가지 않는 것을 보장한다. 교착상태(Deadlocks) 1. 시스템이 교착상태로 들어가지 않는 것을 보장한다. 교착상태를 예방(prevention)하거나 회피(avoidance)하는 프로토콜을 사용한다. 교착상태 예방: 교착상태 발생의 네 가지 조건 중 적어도 하나가 성립하지 않도록 한다. 교착상태 회피: 프로세스가 요구할 자원들을 미리 파악하여 대기 여부를 결정한다. 2. 시스템이 교착상태에 들어가는 것을 허락하고 그 후에 회복한다. 교착상태 탐지, 교착상태 회복 3. 문제를 무시하고 시스템에서 교착상태가 결코 일어나지 않는 척한다. 유닉스와 윈도우를 포함한 대부분의 운영체제에서 사용된다. 교착상태를 처리하는 것은 응용 프로그램 개발자에게 달려 있다.

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태 예방 (Deadlock Prevention) (1/3) 교착상태(Deadlocks) 교착상태를 발생하게 하는 네 가지 조건 중에 적어도 하나가 일어나지 않게 보장함으로써 교착상태를 예방할 수 있다. 상호 배제(Mutual Exclusion) 공유 가능한 자원들은 배타적인 접근을 요구하지 않는다. 예를 들어, 읽기 전용 파일(read-only file)에 대해서는 배타적 접근이 필요하지 않다. 반면에, 프린터 등의 비공유 자원의 경우는 배타적 접근이 보장되어야 한다. 점유하며 대기(Hold and Wait) 프로세스가 자원을 요청할 때마다 다른 자원을 점유하지 않았음을 보장해야 한다. 방법 1) 프로세스가 실행을 시작 전에 필요한 모든 자원을 요청하여 모두 할당 받는다.  낮은 자원 이용률을 야기한다. 방법 2) 프로세스가 아무 자원도 점유하고 있지 않을 때만 자원을 요청하도록 한다.  순차적 자원 할당이 이뤄진다. 기아가 발생할 수도 있다.

교착상태 예방 (Deadlock Prevention) (2/3) 교착상태(Deadlocks) 비선점(No Preemption) 한 개 이상의 자원을 점유한 프로세스가 즉시 할당 받을 수 없는 추가의 자원을 요청한 다면, 현재 잡고 있는 모든 자원을 내려 놓도록 한다. 선점된 자원은 기다리고 있는 프로세스를 위한 자원 목록에 추가된다. 프로세스는 요청했던 새로운 자원 뿐 아니라 이전에 소유했던 자원까지 모두 다시 얻었 을 때, 다시 시작 될 수 있다. CPU 레지스터, 메모리 등 그 상태가 쉽게 저장/복원 가능한 경우에 사용되나, 프린터, 테이프 드라이브 등에는 적용이 어렵다. 순환 대기(Circular Wait) 모든 자원 타입들에 대해 전체적으로 순서(order)를 부여한다. 각 프로세스는 오름차순으로만 자원을 요청할 수 있다. 사이클이 발생하지 않으므로 교착상태가 발생하지 않으나, 오름차순 요청은 자원을 활용하는데 큰 제약 조건이다.

교착상태 예방 (Deadlock Prevention) (3/3) 교착상태(Deadlocks) 교착상태 예방 알고리즘 요청이 생성되는 방법에 제약을 가하여 교착상태를 예방한다. 이 제약에 의해, 적어도 교착상태 발생의 필요 조건 중 하나가 일어나지 않게 함으로써 교착상태가 발생하지 않게 한다. 교착상태 예방에서 가능한 사이드 부작용(side effect) 낮은 장치 사용률 감소된 시스템 처리량 대체 방법?  교착상태 회피

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태 회피 (Deadlock Avoidance) 교착상태(Deadlocks) 시스템은 프로세스가 자원을 어떻게 요청할지에 대한 추가적인 정보를 제공하도록 요구한다. 교착상태 회피를 위한 가장 간단하고 유용한 모델은 각 프로세스는 자신이 필요로 하는 각 타입에 대한 자원의 최대 개수를 선언하도록 요구한다. 교착상태 회피 알고리즘은 순환(사이클) 대기 상황이 발생하지 않도록 동적으로 자원 할당 상태를 검사한다. 자원 할당 상태는 가용 자원 수, 할당된 자원 수, 프로세스들의 최대 요구 개수에 의해 정의된다.

안전 상태 (Safe State) 교착상태(Deadlocks) 프로세스가 가용한 자원을 요청했을 때, 시스템은 즉시 자원을 할당하더 라고 시스템이 안전 상태에 있는지를 결정해야 한다. 시스템이 안전 상태에 있다는 말은? 시스템이 프로세스들의 안전 순서(safe sequence)를 찾을 수 있음을 의미한다. 프로세스 순서 <P1, P2, …, Pn>이 안전하다는 말은 모든 Pi에 대해 Pi가 요청하는 자원이 현재 시스템에 가용하거나 혹은 앞에서 실행을 마칠 프로세스 Pj들(j < i)이 반납하는 자 원들로 만족시켜줄 수 있음을 의미한다. 다시 말해서, 만약 Pi의 자원 요구가 즉시 가용하지 않다면, Pi는 모든 Pj가 끝날 때까지 기다려야 한다. Pj가 끝나면, Pi는 필요한 모든 자원을 획득하여 실행하고, 할당된 자원을 반납하고 종료 될 수 있다. Pi가 종료되면, Pi+1는 필요한 자원을 획득할 수 있다.

안전 상태에 대한 기본 사실 만약 시스템이 안전 상태에 있다면  교착상태가 발생하지 않는다. 교착상태(Deadlocks) 만약 시스템이 안전 상태에 있다면  교착상태가 발생하지 않는다. 시스템이 불안전 상태에 있다면  교착상태가 발생할 수도 있다. 교착상태 회피  시스템이 불안전 상태로 들어가지 않도록 보장한다.

자원 할당 그래프 알고리즘 자원 할당 그래프(Resource Allocation Graph)의 변형을 이용한다. 교착상태(Deadlocks) 자원 할당 그래프(Resource Allocation Graph)의 변형을 이용한다. 예약 간선(claim edge) Pi  Rj:프로세스 Pi 가 미래에 자원 Rj를 요청할 수 있음을 나타내며, 요청 간선(request edge)과 구분하기 위해 점선으로 표시한다. 예약 간선은 프로세스가 실제로 자원을 요청하면 요청 간선으로 변경되고, 프로세스에 할당되었던 자원을 방출하면, 할당 간선(assignment edge)은 다시 예약 간 선으로 변경된다. 시스템에서 자원이 반드시 미리 예약되어야 한다. 각 프로세스는 실행되기 전에 자신의 모든 예약 간선들이 자원 할당 그래프에 표시되어 야 한다. Pi Rj

교착상태 회피를 위한 자원 할당 그래프 모든 자원이 한 개의 인스턴스만 가지는 경우를 고려한다. 교착상태(Deadlocks) 모든 자원이 한 개의 인스턴스만 가지는 경우를 고려한다. R2는 현재 자유 상태이나 이를 P2에 할당할 수 없다. 할당할 경우 사이클이 생긴다! 안전한 프로세스 시퀀스는? P1, P2  YES P2, P1  NO

자원 할당 그래프의 불안정 상태(Unsafe State) 교착상태(Deadlocks) R2가 P2에 할당되었다 하자. 안전한 프로세스 시퀀스는? P1, P2  NO P2, P1  NO 결국, 교착상태가 발생할 가 능성이 높아진다!

자원 할당 그래프를 이용한 교착상태 회피 교착상태(Deadlocks) 프로세스 Pi가 자원 Rj를 요청한다 가정할 때, 요청 간선 Pi  Rj를 할당 간선 Rj  Pi로 변환해도 사이클을 형성하지 않을 때만 요청을 허용한다. 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 된다. 사이클이 발견되면, 프로세스 Pi는 조건(사이클 없음)이 충족될 때까지 대기해야 한다. 사이클 탐지(cycle detection) 알고리즘을 사용해 안전성을 검사하며, 이 알고리즘은 n2의 연산이 필요하다. (n = 프로세스 개수) 자원 할당 그래프는 하나의 타입에 자원 인스턴스가 여러 개 있을 경우 에는 적용되지 못한다.  은행원 알고리즘(banker’s algorithm)으로 해결 프로세스는 자신이 필요로 하는 자원의 최대 개수를 미리 신고함 시스템은 자원의 최대 개수를 허용했을 경우에도 안전 상태에 있도록 판단함 자세한 알고리즘은 생략  교재 참조

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태 탐지(Deadlock Detection) 교착상태(Deadlocks) (시스템의 성능 저하 방지를 위해) 교착상태 예방(prevention)이나 회피(avoidance)를 하지 않는다면? 시스템은 교착상태에 들어갈 수 있으며, 이 환경에서 시스템은 다음 알고리즘을 반드시 지원해야 한다. 교착상태를 탐지하는 알고리즘 교착상태로부터 회복하는 알고리즘

각 자원 타입이 한 개 인스턴스만 갖는 경우 대기 그래프(wait-for graph)를 유지한다. 교착상태(Deadlocks) 대기 그래프(wait-for graph)를 유지한다. 자원 할당 그래프의 변형으로, 자원 할당 그래프에서 자원 타입의 노드를 제거하고, 프로세스들 간의 대기 상태를 그래프로 나타낸다. 좀 더 정확히 말하면, 요청 간선 Pi  Rq이 있고, 할당 간선 Rq  Pj이 있다면, 대기 그래프에는 Pi  Pj의 간선을 추가한다. 주기적으로 대기 그래프에서 사이클을 찾는 알고리즘을 수행한다. 그래프에서 사이클을 탐지하는 알고리즘은 n2의 복잡도를 요구한다. n은 그래프의 노드 개수(여기서는 프로세스 개수)이다.

자원 할당 그래프 vs 대기 그래프 자원 할당 그래프 (resource-allocation graph) 대응하는 대기 그래프 교착상태(Deadlocks) 자원 할당 그래프 (resource-allocation graph) 대응하는 대기 그래프 (corresponding wait-for graph)

각 자원 타입이 여러 인스턴스를 갖는 경우 대기 그래프를 사용하여 탐지할 수 없다. 교착상태(Deadlocks) 대기 그래프를 사용하여 탐지할 수 없다. 은행원 알고리즘의 자료구조를 사용하여 탐지한다.  교재 참조

탐지 알고리즘의 사용 언제, 얼마나 자주 탐지 알고리즘을 호출할 것이냐는 다음에 의존한다. 교착상태(Deadlocks) 언제, 얼마나 자주 탐지 알고리즘을 호출할 것이냐는 다음에 의존한다. 교착상태가 얼마나 자주 일어날 것 같은가? 교착상태가 발생하면 통상 몇 개의 프로세스가 연루되는가? 탐지 알고리즘이 제멋대로 호출된다면? 자원 그래프에 많은 사이클이 존재할 수 있다. 교착상태인 프로세스가 많아지면, 어떤 프로세스가 교착상태를 유발했는지 알 수 없다. 탐지 알고리즘 호출하는 바람직한 시점은? 자원을 요청할 때마다 탐지 알고리즘을 호출할 수도 있음  오버헤드가 매우 크다. 어떤 프로세스가 자원을 요청했는데 그것이 즉시 만족되지 못하는 시점  교착상태 연루 프로세스들을 알 수 있고, 누가 교착상태를 유발했는지 알 수 있다. 지정된 시간 간격으로 호출함  예로, 한 시간에 한 번 CPU 이용률이 40% 이하로 떨어질 때

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

교착상태로부터의 회복 교착상태(Deadlocks) 탐지 알고리즘이 교착상태가 존재한다는 것을 파악했다면, 이 상태로부 터 회복하기 위해 여러 대안이 가능하다. 운영자에 의한 해결: 교착상태 발생을 운영자에게 알리고, 운영자가 교착상태를 수작업으로 처리하도록 한다.  오늘날 컴퓨터 시스템에서는 비현실적 방법임 프로세스 종료(process termination): 순환 대기를 깨뜨리기 위해 하나 이상의 프로세스를 종료시킨다. 자원 선점(resource preemption): 교착상태로 인해 멈춘 하나 이상의 프로세스들로부터 자원을 내놓게 한다.

프로세스 종료(Process Termination) 교착상태(Deadlocks) 1. 교착상태 프로세스를 모두 중지 확실하게 교착상태의 사이클을 제거하나, 비용이 많이 든다. 2. 교착상태가 제거될 때까지 하나씩 중지 중지되는 프로세스 수는 줄일 수 있으나, 중지 후 문제가 해결되었는지 확인을 위해 교착상태 탐지 알고리즘을 호출해야 하는 오버헤드가 있다. 종료해야 하는 프로세스는 다음 사항을 고려하여 선택한다. 프로세스의 우선순위 프로세스가 얼만큼 계산되었고, 종료될 때까지 얼마나 남았는가? 프로세스가 사용한 자원 프로세스가 완료되기 위해 필요한 자원 얼마나 많은 프로세스들이 종료될 필요가 있는가? 프로세스가 대화형인가, 일괄(batch)처리형인가?

자원 선점(Process Preemption) 교착상태(Deadlocks) 교착상태가 깨질 때까지 프로세스로부터 자원을 선점해(빼앗아) 다른 프 로세스에게 주어야 한다. 자원 선점의 세 가지 요소 희생자 선택(selection of a victim): 비용 최소화를 고려해야 한다. 프로세스가 점유한 자원의 수, 지금까지 소요한 시간 등을 고려하여 선택한다. 롤백(rollback): 프로세스를 안전한 상태까지 되돌리고 그 상태에서부터 재시작한다. 교착상태를 해결할 수 있는 수준까지 롤백시키는 것이 가장 바람직하다. 그러나, 안전한 상태를 파악하기 어려우므로, 가장 단순한 것은 프로세스를 중지(abort) 시키고 재시작하는 것이다. 기아(starvation): 같은 프로세스가 항상 희생자로 선택될 수도 있다. 해결책으로는 희생자를 선택할 때, 롤백된 횟수를 고려한다.

강의 목차 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 요약

요약 (1/2) 교착상태가 일어날 수 있다. 교착상태 처리를 위한 세 가지 방법 교착상태(Deadlocks) 교착상태가 일어날 수 있다. 두 개 이상의 프로세스들이 서로 상대의 자원을 요청하면서 무한정 기다리는 상태 교착상태 처리를 위한 세 가지 방법 교착상태 예방(deadlock prevention) 교착상태 회피(deadlock avoidance) 교착상태 무시 후, 탐지-회복 기법 교착상태는 네 가지 조건이 동시에 발생하면 일어난다. 상호 배제(mutual exclusion) 점유하며 대기(hold and wait) 비선점(no preemption) 순환 대기(circular wait)

요약 (2/2) 교착상태 예방은 교착상태 발생에 필요한 조건 중 적어도 하나는 발생하 지 않도록 보장하는 것이다. 교착상태(Deadlocks) 교착상태 예방은 교착상태 발생에 필요한 조건 중 적어도 하나는 발생하 지 않도록 보장하는 것이다. 교착상태 회피는 프로세스가 필요로 하는 자원 정보를 미리 파악하여 교 착상태가 발생하지 않도록 한다. 교착상태가 탐지되면, 시스템은 몇몇 프로세스들을 종료하거나 몇몇 프 로세스들의 자원을 선점(preemption)함으로써 회복해야 한다.