[OS] Chapter 06. 교착 상태(Deadlock)

Chapter 06. 교착 상태(Deadlock)

누워서 보는 운영체제 이야기 - 김주균 교수님

---

방학 때 병팔이와 동생은 각자 강아지를 한 마리씩 키우기로 하고 우선 강아지 집을 만들기로 하였다. 창고에 있는 여러 가지 크기의 합판과 망치, 톱을 준비하고 나서 병팔이는 적당한 합판들로 망치를 가지고 지붕부터 만들기 시작했다. 동생은 망치를 이미 형이 쓰고 있어 톱을 가지고 합판들을 적당한 크기로 자르기 시작했다. 여기서 몇 가지 가정을 해보자. 이 형제는 양보라는 미덕을 모르며 융통성 또한 아예 없어서 하기로 했던 일을 중간에 상황에 따라 변경하지도 않는다. 물론 톱과 망치는 하나씩밖에 없다. 약간의 작업 후 병팔이는 톱이 필요해졌다. 그러나 동생은 사용 중인 톱을 줄 리가 없다. 톱으로 해야 할 일만 생각하며 동생이 다 쓴 후 주기만을 기다리는 병팔이는 이번에는 동생이 망치가 필요하니 달라고 하지 않는가! 병팔이 역시 망치는 계속 써야 하므로 줄 생각이 전혀 없다. 자! 지금부터 어떻게 될까? 둘 다 가지고 있는 것은 내놓지 않고 상대방이 가진 것을 달라고 하면서 더 이상 일을 하지 못한 채 시간만 하염없이 흘러갈 것이다. 보다 못한 아버지가 등장하여 한 녀석이 가진 것을 뺏어 다른 녀석에게 주어 사태 해결을 하기 전까진...

▶ 자원이 한정적인 상황에서 두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우, 외부로부터 조치가 없는 한 이들은 아무 일도 못하고 계속 기다려야 할 것임. 이러한 상황을 컴퓨터 시스템에서는 교착 상태(Deadlock)이라고 함

• 자원: 톱과 망치
• 프로세스: 병팔이와 동생
• 외부로부터의 조치: 아버지

 

 

# 6.1 교착 상태에 대해 조금 더 !

▶ 신호등이 고장 난 교차로에서 다른 차들을 신경 쓰지 않고 서로 가겠다고 밀려든 차들을 상상해보자

• 실생활에서 경험하게 되는 교통 교착 상태
• 차: 프로세스
• 도로: 자원
• 교통경찰의 역할: 운영체제가 할 일

교통 교착 상태

▶ 교착 상태가 발생되는 근본 원인: 시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많기 때문

• 위의 병팔이의 경우에도 톱과 망치가 두 개씩 있다면 아무 문제가 없고, 교통 교착 상태의 예시에서도 한쪽을 고가도로로 만들어 놓으면 발생되지 않을 문제임을 알 수 있음
• 하지만 거의 사용되지 못할 것이 뻔한데도 필요 이상의 비용을 들여 많은 자원을 구비해 놓는 시스템이 과연 가격 대비 효과 면에서 권장할 일인가?
• 최소의 비용으로 최대의 효과를 노리는 경제적 논리는 시스템에서도 적용되기 때문에 X라고 답할 수 있음

▶ 교착 상태: 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고(Blocked) 있는 상황

▶ 교착 상태의 문제점

• 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못함
• 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못한다는 점
• 위의 두 가지를 이유로 시스템 성능 저하가 나타남

▶ 교착 상태와 무한 대기

• 운영체제가 많은 프로세스들의 다양한 요청을 처리해 주다가 보면 몇몇 프로세스가 매우 오랜 시간 동안 서비스를 받지 못하는 경우가 발생할 수 있음
• 운영 체제가 정해 놓은 규칙에 의해 오랜 기간 서비스를 받을 수 없는 프로세스들이 생길 수 있고 사용자들은 마치 자신들이 교착상태에 빠진 것과 유사한 기분을 느끼게 됨
• 이런 현상은 운영체제상의 처리 규칙이 한쪽으로 치우쳐 있기 때문에 발생
• 무한 대기가 교착 상태와 다른 점은 오랜 시간 후에라도 무한 대기로부터 벗어나 서비스를 받을 수 있음. 즉, 외부적 조치가 없더라도 언젠가 해결될 문제라는 것

 

1) 자원이란?

▶ 교착 상태를 일으키는 원인이 자원(Resource)이란 면에서 또한, 운영체제의 중요한 임무 중의 하나가 자원의 관리라는 점에서, 시스템이 보유하고 있는 자원들에 대한 분류와 이해는 필요함

▶ 하드웨어와 소프트웨어 관점에서의 분류

• 하드웨어 자원: 하드디스크, 테이프 드라이브, 메모리 등 눈으로 보고 만질 수 있는 모든 자원들
• 소프트웨어 자원: 데이터, 메시지 등

▶ 선점 가능성에 따른 분류

• 선점 가능 자원(Preemptible): CPU나 메모리와 같은 자원처럼 한 프로세스에 의해 사용 도중 선점되어 다른 프로세스에게 할당해 주었다가 이후 다시 원래의 프로세스에게 돌려주어도 되는 자원
• 선점 불가능 자원(Nonpreemptible): 선점이 될 경우 자원을 뺏긴 프로세스는 정상적인 진행을 포기해야 하는 불이익을 받게 되는 경우의 자원으로 시스템은 이러한 상황을 원치 않으므로 선점 불가능 자원은 사용 도중 뺏을 수 없도록 하고 있음 ex) 프린터

▶ 자원이 사용되는 방식에 따른 분류: 한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 있는지의 여부에 따른 분류

• 공유 가능 지원(Sharable): 공유 가능한 프로그램(시스템 프로그램이나 유틸리티 프로그램 등)과 공유 데이터 등으로 교착 상태가 발생하지 않음
• 배타적 사용 자원(Exclusive Use): CPU, 메모리, 테이버, 버퍼, 키보드와 모니터 등

▶ 자원의 속성에 따른 분류

• 순차적 재사용 가능 자원(Serially Reusable): 할당된 자원이 사용 후 반납(Release)되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당이 가능한 자원으로 시스템에서 프로세스들이 아무리 사용해도 없어지지 않고 영구히 존재하는 자원. ex) CPU, 메모리, 하드디스크, 테이프, 버퍼, 프로그램 등
• 소모성 자원(Consumable): 사용 후 사라지는 자원 ex) 시그널: 일시적으로 생성되었다가 사용된 후 없어짐

▶ 배타적 사용 및 순차적 재사용 가능 자원을 대상으로 하는 교착 상태의 발생과 해결책에 대해 다룰 것

 

2) 프로세스는?

• 필요한 자원에 대한 요청과 사용이 끝난 자원을 반납할 수 있음
• 필요한 자원에 대한 요청(Request) - 요청된 자원이 사용 가능하다면 이 자원을 할당받아 사용하면 되며, 자원이 다른 프로세스에 의해 사용 중이라면 반납될 때까지 대기 상태(Blocked)로 기다려야 함
• 대기 상태의 프로세스는 자력으로 그 상태에서 벗어날 수 없으며 따라서 자원의 요청이나 반납과 같은 행동은 더 이상 할 수 없음
• 사용이 끝난 자원의 반납은 deadlock과 무관함
• 자원에 대한 요청과 반납은 실행 중인 프로세스가 시스템 서비스를 호출(System Call)함으로써 운영체제에 의해 이루어지며, 반납된 자원으로 그 자원 때문에 대기 중인 프로세스를 깨우는 것도 운영체제임

 

3) 교착 상태의 원인은?

▶ 다음과 같은 4가지 조건들이 모두 갖춰질 때 교착 상태가 발생

① 자원의 배타적인 사용

• 교착 상태의 발생이 시스템이 보유한 한정적인 자원에 대한 프로세스들의 사용 경쟁 때문이라고 했을 때, 자원이 한정적이라도 모두 공유가 가능한 자원이라면 교착 상태는 발생할 수 없음
• 시스템이 보유한 자원 중 배타적 사용이 요구되는 자원 때문에 교착 상태가 발생하는 원인이 되는 것
• 상호 배제 조건(Mutual Exclusion Condition)이라고도 함

② 자원의 부분 할당(Partial Allocation)

• 각각의 프로세스는 자신의 실행 전체 과정에서 필요한 자원을 필요할 때마다 일부분씩 확보, 실행해 나가다가 어느 시점에 할당이 불가능한 자원 때문에 이미 확보한 자원들을 소유한 채 대기 상태가 되어 버리는 과정을 겪으면서 교착 상태에 빠질 가능성을 높이는 것
• 보유와 대기 조건(Hold & Wait)이라 부르기도 함

③ 자원의 선점 불가능성

• 선점이 불가능한 자원을 억지로 선점이 되도록 하면 어떨까? 선점의 권한이 주어진 프로세스들은 자원 때문에 대기할 필요가 없으므로 교착 상태라는 것은 없앨 수 있음. 하지만 자신의 자원을 선점당한 프로세스들은 정상적인 실행을 포기해야 함
• 선점을 당한다는 것은 그 자원을 가지고 해왔던 지금까지의 일을 잃게 된다는 뜻
• 자원의 선점 불가능성을 고수할 경우 교착 상태의 원인이 되는 것을 알 수 있음
• 비선점(No Preemption) 조건이라고도 함

④ 자원에 대한 환형 대기(Circular-Wait)

• 프로세스들이 자신의 자원은 보유한 채로 서로 상대방의 자원을 요청하고 결과적으로 대기 상태가 되어버리는 일련의 과정에서 교착 상태가 발생 가능하다고 함
• 아래 그림이 두 프로세스 사이에 발생한 교착 상태의 예

두 프로세스의 교착 상태

 

 

# 6.2 교착 상태의 해결

1) 예방 기법

• 교착 상태가 발생되는 4가지 원인 중 하나를 제거함으로써 교착 상태의 발생 자체를 막도록 한 방법
• 즉, 교착 상태가 발생할 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않음
• 첫 번째 방법을 제외한 나머지 방법들은 자원의 심각한 낭비와 특정 프로세스의 무한 대기 가능성을 피할 수 없음

① 자원의 배타적 사용 조건을 배제

• 모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단하겠다는 의도
• but, 시스템이 보유한 자원 중에는 배타적으로 사용할 수밖에 없는 자원들도 있음
• 프린터나 테이프 장치 등은 프로세스들이 차례로 사용해야 하는 자원으로 공유가 가능한 자원이 될 수 없음
• 결론적으로, 이 조건을 배제하여 교착 상태를 예방하기는 불가능함

② 자원의 부분 할당을 배제

• all at once (all or none): 한 번에 받을 수 있으면 다 받자
• 프로세스들은 각자 자신이 필요한 모든 자원을 미리 할당받아 실행을 시작하도록 하는 방법
• 심각한 자원의 낭비가 초래됨: 일부 자원만 확보되면 시작할 수 있음에도 불구하고 모든 것을 할당받을 때까지 기다려야 하고, 할당 가능했던 일부 자원들은 사용되지 못해 낭비되는 현상이 발생하게 되는 것
• 무한 대기(기아/Starvation)를 겪게 될 프로세스가 발생할 수 있음 - 필요한 자원이 번갈아가며 다른 프로세스에게 지속적으로 할당될 경우 계속 대기를 해야 할 수 있음

③ 자원의 선점 불가능성을 배제

• 모든 자원이 선점 가능하도록 할 경우 교착 상태는 발생하지 않을 것이라는 점을 고려한 해결책
• 일부 자원을 가지고 실행하던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우 자신이 보유하고 있던 자원을 내놓게 함으로써 비선점 조건을 없앴다는 것
• 실행 도중 보유한 자원을 내어놓게 되는 프로세스는 비정상적인 종료와 함께 심할 경우 처음부터 다시 시작해야 하는 불이익을 받게 되는 것이며, 반납된 자원들을 사용하여 지금까지 해왔던 일들이 모두 무효가 됨으로써 결과적으로 그동안 가동되었던 모든 자원들은 사실상 낭비된 결과가 되는 것
• 계속해서 "처음부터 다시"해야 하는 무한 대기도 겪게 될 가능성이 매우 높음

④ 자원의 환형 대기 상황을 배제

• linear ordering: 요청하는 자원에 대해 numbering 하는 방식으로 이 순서는 사용할 자원의 순서와 무관하게 시스템에서 지정함
• 예) 톱과 망치가 있는 병팔이와 동생의 경우 톱에 1번 망치에 2번으로 순서를 할당할 경우 두 사람 모두 어떤 자원이 먼저 필요한지와는 관계없이 1번, 2번 순서대로 자원을 요청하는 것
• 자원들의 순서를 정하고 프로세스들은 이 순서를 지켜 요청함으로써 사이클이 발생될 소지를 없애 교착 상태를 없앤 방법
• 자원의 낭비와 프로세스의 무한 대기를 피해 갈 수 없음

 

2) 회피 기법

• 예방 기법에서는 교착 상태의 발생 조건을 배제하는 방식을 사용하였고 회피 기법에서는 다른 알고리즘을 선보임
• 자원의 낭비는 예방 기법보다는 덜하나 여기서도 꽤 발생함
• 회피 기법의 대표적인 알고리즘은 Dijkstra의 은행가 알고리즘(Banker's Algorithm) 임

① 안전 상태(Safe State)

• 시스템에 있는 모든 프로세스가 유한(Finite) 시간 내에 정상적으로 종료될 수 있는 상태를 말함
• 그렇지 못한 경우는 불안전(Unsafe) 상태라고 함
• 안전 상태란 교착 상태가 발생할 수 없는 상태를 말하며, 불안전 상태라고 해서 그것이 곧 교착 상태임을 의미하는 것은 아니지만 불안전 상태는 교착 상태로 갈 가능성이 있으며 그럴 경우의 방지책이 없음을 뜻함
• 이것은 각 프로세스의 자원에 대한 요청을 해당 자원이 사용 가능하다고 해서 할당되는 것이 아니라 할당의 결과 시스템이 계속 안전 상태가 되느냐에 의해 결정함을 뜻함

안전, 불안전, 교착 상태의 관계

• 은행가 알고리즘이 제대로 작동하기 위해서는 시스템에 대한 몇 가지 가정이 요구되는데 다음과 같음

1. 시스템 내의 프로세스 수가 고정되어 있어야 한다
2. 자원의 수 역시 고정되어 있어야 한다
3. 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다
4. 각 프로세스는 할당받은 자원을 사용 후 반드시 반납하여야 한다

• 위의 가정 중 1번은 실제 프로그램 작동에서 프로세스 수가 고정되기 힘들다는 점이 있고 3번은 미래를 알아야 한다는 점(실제 실행을 해보아야 프로세스 수를 알 수 있음)에서 지켜지기 힘들다는 것을 알 수 있음
• 이러한 이유로 은행가 알고리즘은 교착 상태를 말할 때 이론적인 접근의 방편으로 언급됨

② Dijkstra의 은행가 알고리즘

• system의 state를 safe 상태만 유지하도록 하는 알고리즘
• 프로세스가 자원을 요청했을 때, 지원을 할당한 상태가 안전한 상태가 되면 할당해 주고 불안전한 상태가 되면 할당하지 않음
• 현재 시스템의 상태: 아래와 같이 프로세스가 3개로 고정되어 있고 이들의 현재 보유랑, 최대 요구량과 함께 현재 시스템이 할당해 줄 수 있는 여유량이 나타나 있음

safe state

시스템이 보유한 전체 자원의 수는 각 프로세스의 현재 보유량과 여유량을 합친 것

P2가 더 요구할 최대량이 2개이며 이것은 시스템이 현재 가지고 있는 여유량을 넘지 않음

따라서 P2의 요청에 여유량을 할당해 주어 P2의 성공적인 종료를 유도하고,

결과적으로 반납되는 6개의 자원을 여유량으로 확보하면 P1과 P3의 어떤 요청에도 할당 가능함

즉, 안전 상태의 판단은 "현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있는가"에 달려 있음

 

unsafe state

현재의 여유량이 1개인 자원으로는 어떤 프로세스도 향후 자신의 최대 요구량에 이르지 못하는 상태가 되어 불안전 상태가 됨

 

3) 탐지 기법

• 예방, 회피 기법은 교착 상태의 발생이 허용되지 않음
• 교착 상태의 발생을 막기 위한 사전 조치를 취하지 않는 경우 언젠가는 발생할 터이고 이것을 어떤 방법으로든 찾아내어 적절한 대응을 하겠다는 것이 탐지 기법
• 교착 상태가 탐지 프로그램이 알 수 있는 적당한 형태로 시스템 내에 표현되어야 하며 최소한 "어떤 프로세스가 어떤 자원을 가지고 있는가?", "어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?"에 대한 정보는 있어야 함
• 즉, 교착 상태의 발생이 허용되어 있는 시스템에서 교착 상태가 발생하였는지 발생하였다면 어떤 프로세스들과 자원들이 관여되었는지를 탐지함
• 교착 상태의 탐지를 위해 현 시스템의 상황을 그래프로 많이 표현하는데, 이것을 자원 할당 그래프(Resource Allocation Grahp, RAG)라 부름

▶ RAG를 설명하기 위한 그래프 이론

1. RAG는 방향성 이분 그래프이며 노드와 에지들로 이루어져 있음. 노드들은 프로세스와 자원들을 표현하며 에지들은 프로세스와 자원들 간의 할당과 대기 상황을 나타냄. 프로세스로부터 자원으로 향하는 에지는 보통 두 개의 의미를 가지는데 하나는 요청 중이라는 것과 또 하나는 대기 상태가 되었다는 것
2. RAG에서 자원 노드는 그 자원의 형(Type)을 나타내고 그 안의 작은 동그라미가 자원의 개수를 나타냄. 즉, 한 자원 형에 여러 개의 자원이 있을 수 있음을 나타냄
3. 한 자원 형에는 자원의 개수를 나타내는 정수(ti)가 있으며, 임의의 노드 a로부터 다른 노드 b로 향하는 에지의 개수는 |(a,b)|로 표현

 

▶ RAG에 대한 그래프 제거(Gragh Reduction) 법으로 교착 상태를 탐지하게 되는 것

• priod detection: 시스템 전체에서 여러 서브 그래프가 그려질 수 있음
• 자원으로 향하는 에지가 없는 프로세스: 대기 상태가 아닌 즉, 활동이 가능한 프로세스이며 이를 unblocked process 또는 싱크(sink)라고 함
• 대기 상황을 나타내는 에지로부터 방향을 따라 경로를 탐색하고, 탐색 도중 싱크가 발견되면 교착 상태는 없다고 판단함

• 그래프의 제거 순서는 상관 없음 → 제거될 거면 다 제거되고 아니면 안 지워지기 때문임
• 그림 6.5의 (a)는 억지로 만들어낸 상황임. 실제 시스템에서 blocked edge는 하나만 생겨야 함
• 즉, complete reduce는 deadlock이 없었다고 판단되는 기준이며 edge 제거가 되지 않을 경우가 발생하면 deadlock이 존재한다는 뜻임
• 자원 형에 다수 개의 자원이 있을 경우에는 노트(Knot)라는 자료구조의 발견이 곧 교착 상태의 발견이 됨
• 프로세스가 경로를 따라 만날 수 있는 노드가 모두 같을 때가 knot구조를 형성

Knot: 모든 노드가 "자신이 만나는 노드 + 자기 자신"의 결과가 같은 경우를 표현하는 구조로 이때 cycle을 포함함

* 자원의 unit이 하나씩만 있을 때 cycle이 형성되면 무조건 교착임. 즉, 자원의 unit이 하나씩만 있는 것은 교착 상태의 필요충분조건임.

* 자원이 하나 이상일 경우에 cycle을 형성하면 교착 가능성이 높아질 뿐 교착인 것은 아님. 즉, 자원이 하나 이상일 경우의 교착 상태의 필요충분조건은 cycle을 포함하여 knot이 발견되어야 함

 

▶ RAG에 대한 그래프 탐색(Graph Search)

• blocked 될 때마다 모든 path를 방문해서 싱크가 있으면 교착상태가 아니고 싱크가 없으면 교착 상태로 판단하는 기법

▶ Graph Reduction 과 Graph Search의 비교

	Gragh Reduction	Gragh Search
정의	시스템 전체를 스캔해서 싱크를 찾아 그 싱크로부터 엣지들을 하나씩 없애가는 방식	프로세스들이 blocked될 때마다 따라가 보는 것 (path를 찾는 것)
빈도	주기적으로 발생	blocked될 때 마다 발생(continuous detection)
시간	오래걸림(시스템 전체를 스캔하기 때문에)	reduction에 비해서는 짧게 걸림 (blocked된 프로세스가 속한 cycle 내에서만 찾음)
특징	reduction 이후 발생한 교착 상태는 다음 reduction 이전까지 발견되지 못함	교착상태를 즉시 발견할 수 있음

 

4) 복구 기법

• 교착 상태로부터 벗어나기 위한 방법
• 교착 상태에 포함되어 있는 한 개 이상의 프로세스를 강제로 종료시켜 이들로부터 반납되는 자원들을 나머지 프로세스들에게 줌으로써 해결
• 교착 상태를 벗어나기 위해 필요한 추가의 자원을 어디서든 갖고 와 할당해 줌으로써 해결
• 프로세스의 종료 방식과 자원의 선점에 의한 방식으로 나뉨

▶ 프로세스의 종료(Process Termination) 방식

• deadlock chain에서 포함되는 자원을 뺏어서 할당해 줌
• 교착 상태를 형성한 프로세스들 중 몇 개를 강제로 종료시켜 이들로부터 반납된 자원으로 복구
• 문제점: 어떤 프로세스들을 종료시킬 것인가?
• 강제로 종료된 프로세스들은 지금까지 해왔던 일을 포기하게 되고 기회가 왔을 때 다시 자원들을 할당받아 일을 새로 시작해야 하는 희생이 요구되므로 이러한 희생을 최소화할 수 있는 종료 비용(Termination Cost)이라는 것을 따져 교착 상태로부터 복구될 때까지 종료 비용이 최소인 프로세스부터 종료시켜 나감 → 비교적 간단하나 프로세스 하나를 종료시킬 때마다 교착 상태가 제거되었는지 알아보아야 함
• 교착 상태에 있는 프로세스들의 집합에서 가능한 모든 부분집합을 만들어 이 집합들에 속하는 프로세스들을 종료시켰을 경우의 비용을 따져 역시 최소의 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료시키는 방식을 취하기도 함 → 최소 비용의 프로세스들을 고를 수는 있으나 모든 부분 집합에 대해 비용을 계산하기가 복잡하고 힘듦

▶ 종료 비용의 산정 방법

• 프로세스의 우선순위(Priority)나 종류, 실행된 시간의 크기, 남은 시간 등
• 우선순위가 낮은 것, 실시간이 아닌 것, 실행된 시간이 적은 것, 남은 시간이 큰 것에 해당될수록 종료 비용이 싸다고 보는 것

▶ 자원의 선점에 의한 방식

• deadlock chain에서 그와 유사한, 비슷한 자원이 다른 곳에 또 있다면 거기서 가져옴
• 필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어 교착 상태에 있는 프로세스들에게 줌으로써 해결하는 것
• 자원을 선점당하는 프로세스는 교착 상태와는 전혀 상관이 없지만 단지 해당 자원을 가지고 있다는 이유 때문에 선택될 수 있음
• 선점 시의 최소 비용은 따져야 함
• 프로레스의 강제 종료는 그동안의 일을 없던 것으로 하고 처음부터 다시 해야 하기 때문에 복구 비용을 키우는 주요인이 되며 시스템의 입장에서는 큰 낭비 요인임

▶ 강제 종료 시의 낭비를 줄이기 위한 방법

• 검사점 지정(Checkpointing)과 재시작(Restart)
• 프로세스들은 실행의 중간중간에 그 시점까지의 실행 결과를 보존하고 표시를 해두는데 이를 검사점이라 함
• 강제로 종료될 때는 아예 처음으로 돌아가는 것이 아니라 가장 최근의 검사점부터 차례로 하나씩 되돌리는 것
• 이 과정에서 교착 상태를 벗어날 수 있다면 종료된 프로세스는 처음부터가 아니라 최종적으로 되돌려졌던 검사점에서 보존된 내용으로 재시작을 할 수 있어 잃게 되는 일의 양을 최소화할 수 있음
• cold restart: check pointing을 사용했음에도 처음으로 돌아간 것. 즉, 거슬러가는데도 내놓는 자원이 부족하여 계속 내놓다 보니 처음으로 돌아간 상태
• 예시) 100원짜리 동전을 10개씩 쌓아 총금액을 계산한다 생각할 때 1000원씩 쌓아 놓은 탑들이 검사점이 되며, 탑 9개 이후 동전을 세다가 중간에 까먹고 9100원부터 다시 세는 행동을 재시작이라고 할 수 있음. 이때 9개 이후 쌓았던 10개 미만으로 구성된 탑은 재시작으로 잃게 되는 시간과 노력 즉, 종료 비용이 됨
• Heuristic: 운영체제의 여러 기법들이 일상생활에서 흔히 경험하는 일과 그 해결책들을 응용하는 것