Chapter 8. Deadlock

# The Deadlock Problem

- Deadlock이란 무엇인가?

 

: 프로세스가 여러개 있을 때 주로 발생하는데, 잘못된 자원 관리로 인해서 프로세스들이 서로 다른 프로세스가 소유하고 있는 자원을 얻기를 바라면서 무기한 교착 상황에 빠지는 것을 의미한다.

 

 

 

 Example로 두가지를 들 수 있다.

 

1. P1, P2 프로세스가 각자 disk drive를 소유하고 있는데, 다른 상대방의 disk를 필요로 하면서 자신의 disk를 놓지

않는다면 deadlock이 발생하게 된다.

 

2. 만약 Semaphore A와 B가 둘다 1로 초기화되어있는 상태에서,

 P0가 Wait  A를 통해서 A를 0으로 만들면서 자원 A를 갖고, P1이 Wait B를 통해서 B를 0으로 만들어 자원 B를 갖는 상태에서, P0는 wai0t B를 통해 자원 B를 요구하고, P1은 wait A를 통해 자원 A를 요구한다.

이때, 서로의 자원을 요구만 하면서 Signal 함수를 통해 놓아주지 않기 때문에 Deadlock이 발생하여 벗어날수 없다.

 

 

 

 

=> 다리를 건너는 차들로도 예시를 들수 있는데, 2차선 도로에서 차가 양쪽으로 오고 있는 상황에서 갑자기 1차선으로 길이 좁아지면, 두 차가 서로 멈춰서게 된다. 이 상황에서 차들이 양보하거나 비키지 않게 되면 그 누구도 앞으로 갈수 없게 된다. Bridge crossing sample로 deadlock을 쉽게 이해할 수 있게 된다.

 

 

 

 

 

 

=> 그렇다면, 이 문제를 어떻게 해결할 수 있을까? 

1. 아예 차를 강으로 던져버린다 (;;ㄷㄷ)

: 프로세스 자체를 kill 하여 문제가 없도록 만들 수 있다.

 

2. 차를 후진한다.

: 프로그램은 원래 Sequential하게 연속적으로 수행되어야하지만, Deadlock이 발생하지 않을 시점으로 되돌린다.

: 실제로 OS에서 사용하는 Deadlock Recovery와 비슷하다.

 

#DeadLock Avoidance

: Deadlock이 일어날 기미가 보이면 사전에 방지할 수 있다. 

 

 

=> 차가 멈춰서 막고있는 시점에서, 내가 직진하면 반드시 Deadlock이 발생될 것이 보인다.

=> 그러면 버스가 진입하지 않음으로써 Deadlock을 막을 수 있다.  

 

: OS에 이 상황을 대입해보자면, Deadlock이 발생할 거 같으면 프로그램 수행 자체를 멈추는 방법도 있다.

따라서, Deadlock이 발생하기 이전에 Safe state에서 프로그램을 잠시 멈춰줄 수도 있다.

 

 

 

 

=> 그렇지만 두 차가 모두 움직이는 예시를 봤을때, Deadlock 발생 시에 여러가지 프로세스가 걸쳐 있을 때에는 검출조차 쉽지 않다.

 

 

- 여러개 프로세스가 얽힌 복잡한 케이스에서 Deadlock detection은 쉬운일이 아니다.

=> 따라서 효과적인 Deadlock Detection Algorithm이 반드시 필요하다.

 

 

 

 

주로 네가지 방법을 통해서 Deadlock을 검출하여 예방하거나, deadlock에서 복구하거나, 아예 prevention처럼 deadlock이 검출될만한 조건을 없애버리는 경우도 있다. ( ex. F받을거같으면 포강해버림ㅋㅋㅋ)

 

---

 

#System Model

blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221197205167&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

[대딩의 운영체제, OS 15] 데드락의 개념 Deadlock 과 자원 할당 그래프 Resource Allocation Graph

 

- Deadlock 과 연결된 두가지 object인 Process와 Object를 시각적으로 그래프처럼 표현 할 수 있다.

 

1. Resource Type: R1,R2....

 1) Physical Resource

: Memory Space, I/O device 등의 실체가 있는 하드웨어 자원을 위미한다.

 

 2) Logical Device

: 파일, 세마포어 등의 프로그래밍 환경에서 쓰이는 object를의미한다.

 

=> 각 Resource type Ri에는 Wi instance가 있으며, 특정 resource의 개수를 의미한다.

ex) Disk 5개가 존재한다면, Resource type disk는 5개의 instance를 갖고 있으며,

 Dual CPU는 Resource type CPU가 2개의 instance를 갖고 있는 것을 의미한다.

 

:각 프로세스들은 resource를 Request, Use, Release instruction 순서대로 이용한다.

 Request는 Wait 에, Use는 Critical section에 진입함을, Release는 Signal에 비유할 수 있다.

(Request&release는 semaphore등 다른 

 

=> 이때, Deadlock의 필요조건은 Hold&Request라고 볼수 있다.

: 특정 resource를 이미 갖고 있으면서, 다른 resource를 요청한다면 Deadlock이 반드시 발생하게 된다.

 

 

#Deadlock Necessary Condition

=> Deadlock이 발생시 다음 네가지 조건이 만족함을 확인할 수 있다.( 4개를 만족해도 발생하지 않을수 있다

 

1. Mutual Exclusion

: 한번에 오직 하나의 프로세스만 Resource를 이용할 수 있다. 동시성이 허용되면 Deadlock을 논의할 필요가 없다.

+)  Single Instance인 경우는 그렇다. Multiple Instance는 아닐수도 있음.

 

2. Hold and wait

: 프로세스가 적어도 하나의 resource를 hold하고 있는 상황에서 또다른 자원을 얻고자 하여 Request를 했는데, 그 자원은 이미 점유된 상태라면, 그 프로세스가 자원을 release할때까지 기다리게 된다.

 

3. No preemption

: 중간에 끼어들어 자원을 뺏는 식으로 선점할 수 있으면 안된다.

 

4. Circular wait

: r1->p1->r2->p2->r1 이런 식으로 기다리는 관계가 circular한 형태여야 한다. 프로세스가 어떤 자원을 요구하면서 순환 구조가 생기는 것을 의미한다.

 

 

 

 

 

#Resource Allocation Graph

 

 

=> Deadlock detection을 효과적으로 진행하기 위해서 Process와 resource를 시각적으로 모델링하였다.

: Resource가 어떻게 프로세스에게 할당되었는지 그래프 형태로 그렸다고 볼수 있다.

 

1. 각 vertice들은 Process와 Resource로 이루어져 있다.

 

2. 각 edge에는 두가지 종류가 있다. 

 1) Request edge

: Pi-> Rj 식으로 프로세스가 리소스를 요청한 상태이다. (할당되었는지는 모른다)

 

2) Assignment edge

: Rj-> Pi 식으로, 리소스가 프로세스에 request한 뒤에, 이가 accept되었다면 Request edge에서 Assignment edge로 edge의 방향이 바뀌게 된다.

 

 

 

 

1) Process는 동그라미로 표현

2)  Resource가 multiple instance를 갖고 있다면, 각 instance를 resource type안에 그려서 표현해준다.

3) Process가 Resource를 요청했다면, 어떤 instance를 할당할진 모르기 때문에 전체적인 사각형을 가리킨다.

4) 특정 instance가 할당되면, 해당 instance가 process를 가리키게 된다.

 

 

 

 

=> Request edge와 assignment edge, 프로세스와 resource가 어떻게 표현되었는지 확인 할 수 있다.

 

 

 

#Resource Allocation Graph with a deadlock

 

 

 

 

=> Resource Allocation graph를 이용하면 확실히 Deadlock 을 효과적으로 detection 할 수 있다.

: Resource Allocation graph는 Resource, process의 두가지 type의 구성요소로 존재하게 되고, 

어떤 Process가 어떤 resource를 request를 했는지, 어떤 resource가 어떤 process에게 할당되었는지도 확인 가능하며,

Deadlock이 발생하는 조건 중에 하나인 Cycle을 확인 할 수도 있다.

 

: 이때, Cycle에 초점을 맞춰야 한다. 시작점에서 화살표를 따라 다시 시작점으로 돌아오면 Deadlock이 발생할 가능성 이 있다. -> Cycle 없으면 deadlock은 절대 발생하지 않는다!

 

 

 

 

 

 

 

=> Cycle이 있다고 꼭 deadlock이 발생하는 것은 아니다. Indefinite blocking이라고 하여, 계속 block되진 않는다.

 

 

=> 원래 RAG에서는 Cycle이 발생한다. P3가 R2에서 request하지만, R2의 instance가 이미 P1에게 allocate되어있는 상태이기 때문이다. 하지만 R2의 남은 instance를 P3에게 할당해주면, 화살표의 방향이 바뀌므로 cycle이 발생하지 않는다.

 

 

1) Graph contains no cycle: Deadlock 발생하지 않음.

 

2) Graph contains a cycle

 -1) 만약 Resource type마다 한개의 instance만 있다면, Deadlock이 발생한다. (필요충분조건)

 -2) 하지만, Resource type 마다 에 instance가 여러개이면 동시에 여러 프로세스에게 할당이 가능하므로,

   deadlock이 발생할수도 있고, 아닐 수도 있다. (필요조건)

 

 

 

---

https://includestdio.tistory.com/12

[운영체제] 데드락, 교착상태 해결 (Dead lock)

#Methods for Handling Deadlock

=> Deadlock을 막기 위해서는 세가지 방법 이 있다.

: Deadlock avoidance, Deadlock prevention, Deadlock detection & Recovery

 

1) Deadlock prevention을 통해서 deadlock의 필요 조건 중 하나를 잘라버려서 아예 deadlock이 발생하지 않도록 하는 것이다 : 이를 Deadlock Prevention이라고 한다.

=> 하지만 Deadlock prevention은 현실적으로 불가능 하다... Mutual exclusion 같은 경우에는 sharable해야 deadlock을 막을 수 있는데, 프린터기 같은 경우의 하드웨어는 애초에 nonsharable하기 때문이다.

 

2) 따라서, Deadlock avoidance를 통해서 deadlcok 발생 안되는 safe-state일때 프로그램을 수행 시킬수도 있다.

 

3) 또는 Deadlock state에 진입하는 것을 허용한 다음에, Deadlock이 detection되면 recover하는 방법도 있다.

:이때, recover란 프로그램을 과거로 rollback해서 process를 kill 해버리는 것이다.

 

 

+) Unix와 같은 많은 operating system에서는 Deadlock을 OS가 아니라 user program에서 처리해야 할 문제라 생각해서 ignore해버리는 경우도 있다. -> 따라서,Deadlock이 절대로 발생하지 않을 거라고 가정하고 문제를 처리한다.

 

 

 

#Deadlock Prevention

: Deadlock prevention의 main idea는 네가지 condition의 발생 가능성을 없애는 것이다.

=> 하지만 부작용이 발생할 수도 있고, 거의 불가능 하다.

 

1) Mutual Exclusion 조건을 없앤다고 가정하자.

 Mutual Exclusion 같은 경우에는 주로 Sharable해야 deadlock이 걸리지 않게 되는데,

printer같은 경우에는 중간에 다른 프로세스가 끼어들수 있게 허용해버리면 아예 문제가 발생한다.

=>따라서, Mutual Exclusion property를 없애버릴 수가 없다!

 

 

2) Hold And wait 조건을 없앤다고 가정하자.

=> 따라서 자원을 소유하지 않을 때에만 process가 resource를 request가능하도록 허용해야한다. (hold or wait)

 

-Hold & Wait 조건을 avoid하기 위해서는

 1) 수행 시작 전에 자원을 다 할당해버리는 경우가 있다

: 따라서, 모든 자원을 한꺼번에 이용 가능하다. 

=> but, 모든 리소스가 사용가능할 때에만 한해서 프로세스가 수행한다면, resource utilization이 떨어지고,

starvation이 발생할 수도 있다.

 

2) 프로세스가 아무것도 소유하지 않았을 때에만 request를 허용한다

: resource utilization이 높아지려면, 모든 resource가 병렬적으로 hold 된채로 사용되어야 한다. 

 

 

3) No preemption조건을 없앤다고 가정하자.

: 그렇다면, preemption을 허용하게 되는 것인데, preemption을 허용하면 deadlock이 절대 발생하지 않는다. 이미 점유되어있는 resource를 요청했다면 잠시 preemption해서 점유할 수 있기 때문이다.

=> 하지만 이것은 일부 자원에서만 가능하다. printer와 같은 하드웨어에서는 preemption이 애초에 불가능하다.

 

4) Circular Wait 조건을 없앤다고 가정하자.

: Circular wait 조건을 avoid하기 위해서는 모든 resource type의 우선순위를 매겨서 그 순서대로만 resource 요청을 허용하는 경우가 있다.

 

ex) Tape 우선순위 =1, Disk drive 우선순위 =5, Printer의 우선순위= 12라면, 프로세스는 tape, disk drive, printer 순으로 요청을 해야 한다.

 

 

 

=> 만약 이렇게 R1이 R2보다 우선순위가 높을 경우에, P1은 R1->R2순서대로 리소스를 요청하게 된다.

이때, P2가 R2를 먼저 request했다면, 그 다음에 R1을 request할수 없다. 우선순위 순서대로 request해야 하기 때문이다.

: 하지만, 이렇게 되면 동시에 resource를 활용할 확률이 적어지므로 역시 resource의  utilization이 떨어진다.

 

 

Mutual Exclusion	거의 불가능 하다고 봐야 한다.
Hold & Wait	: 역시 리소스를 동시에 사용할 가능성이 줄어드므로 resource utilization이 떨어질 수 있다.
No-preemption	:CPU같은 건 당연히 허용하지만, 프린터와 같은 리소스는 불가능하다.
Circular wait	: 따라서, Resource utilization이 낮아질수 밖에 없다.

 

 

---

#Deadlock Avoidance

: Deadlock이 발생할 것 같으면 Deadlock이 발생하지 않은 State( Safe state)에 도달할 때 까지 실행을 멈춘다.

 

1) Single instance of a resource type이라면 -> Resource Allocation Graph를 사용한다.

2) Multiple instance of a resource type이라면 -> Banker's Algorithm을 사용한다.

 

 

 

=> Single instance example에서는 Resource allocation graph를 그려보면 쉽게 deadlock이 발생할 state를 detection할 수 있다. 

=> 먼저, request할 미래의 edge를 점선으로 그려야 한다. 이 점선인 request edge가 assignment edge로 바뀔때

Cycle이 발생하지 않는지 확인하면 된다.

 

위 그림 예시에서 만약 P1이 R1을 사용중인데, P2가 R1을 요청하고, R2를 P1과 P2가 동시에 요청했을 때, R2가 P2에 할당되어 Cycle이 발생할 여지가 생긴다면, P1이 R2에게 요청한 것을 허용하지 않게 된다.

 

=> 따라서, Cycle이 발생할 거 같으면, request를 허용하지 않는 것으로 생각할 수 있다.

:프로그램을 멈추고, P2가 R2를 release하여 safe state에 도달할 때까지 기다리게 된다.

 

#Multiple Instance 일 때는?

: 우선 역시 Deadlock Avoidance의 기본 목적은 시스템이 unsafe 한 state에 아예 진입하지 않도록 보장하는 것이다.

: 애초에 이미 할당된 resource+ 요구하는 resource 개수보다  available한 resource의 개수가 많으면 deadlock이 절대 발생하지 않는다.

=> 자원이 모자라면 Deadlock이 발생할 수 있다. 같은 자원을 계속 돌려 써야 하기 때문이다.

 

 

 

=> 교차로를 예시로 들었을때, 이미 차가 길을 가고 있는데 중간에 끼어들려고 하면 어떤 차도 움직일 수 없게 된다.

: 따라서, 차들을 교통정리 해줄 신호등이 반드시 필요하다. 

신호등을 통해서 교차로에 진입하는 차들의 순서를 정하는 것과 같은 원리라고 할 수 있겠다.

=> 따라서, 각 resource의 순서를 정해서 safe한 sequence를 정해야 할 것이다.

 

<각 Resource를 안전한 순서대로 실행하는 예시>

 

 

 

: 만약 resoure sequence를 P1-> P0 -> P2 순서대로 시행할 때 안전하다고 예상해보자.

: 현재 이미 각 프로세스들에게 allocated된 resource + 추가로 demand하는 resource <= available resource 개수이면 절대 deadlock이 발생하지 않는다.

 

T0에서 사용되고 있는 resource는 9개이다. 그리고 currently available한 resource한 개수는 3개가 된다.

 

1) 먼저 P1을 실행시킬때, 현재 필요한 tape의 개수는

(이미 P0,P1,P2에 할당되어 사용되고 있는 리소스)( 5+2+2= 9개) 와

(P1이 이미 갖고 있는 resource를 제외하고 추가로 요구하는 resource) (4-2= 2개)를 더해

11 개이다. 이는 12개 보다 작으므로 가능하다.

 

2) 그 다음 P1이 종료되면, 갖고 있던 4개의 tape을 반환한다. 그러면 currently available한 tape은 5개가 된다.

3) 그 다음 P0을 실행시키면, 그 시점에서 필요한 tape의 개수는 5+ 2+ 5= 12개이다. 이는 12와 같으므로 실행가능하다.

4) 그 다음 P0를 종료시키면, 10개의 tape을 반환하게 된다. 따라서 이제 10개의 tape이 available하게 된다.

 

5) 마지막으로 P2를 실행시킬때, 현재 필요한 tape의 개수는 2+ ( 9-2) = 9개이다.

 

=> 따라서 P1-> P0 -> P2 순서대로 process를 실행시키는 것은 safe sequence이다.

- 프로세스가 수행되면 수행될 수록 available한 자원의 개수는 증가하게 된다.

 

 

 

 

=> 그렇지만, 우선 P0->P1-> P2 순서대로 sequence를 실행하게된다면,

 P0는 5+2+2 이미 할당된 resource를 제외하고 5개를 더 요구한다, 이 때 필요한 테이프가 14개이므로 available한 resource의 개수를 넘게 된다. 이는 unsafe한 sequence라고 볼 수 있겠다.

 

 

 

 

 

 

https://baked-corn.tistory.com/13

[10] 운영체제 - Deadlock-2

 

 

< Safe sequence를 설정하기 위한 가정>

=> sequence를 실행할 때, 미리 알아야 하는 정보는 각 프로세스가 자원을 어떻게 요청하고 release할지에 대한 것이다.

 : 이를 위해서 각 프로세스는 타입별로 resource 요구량의 최대 개수를 명시한다. ( 이 정보가 없으면 deadlock avoidance에 대한 적용은 불가능하다)

 

즉, safe한 sequence인지를 예측할 수 있는 식은

 allocated resource + demanding resource <= 전체 resource이면 해당 seqeunce는 안전한다.

따라서 다시 얘기하면 이미 할당된 양은 제외하고, 새로 요구하는 양이 available한 resource의 양보다 적거나 같아야 한다는 것이다. 즉,  demanding resource <= available resource이면 해당 sequence는 안전하다는 것.

: 프로세스가 수행되면 수행될 수록 available한 resource의 개수는 늘어난다.

: 프로세스가 terminate되면 자원을 release하기 때문이다.

 

 

- Safe state

: Safe state의 핵심은 안전한 프로세스 수행 순서을 찾아야 한다는 것이다.

=> 프로세스가 수행되면 될수록 available한 resource개수는 증가한다. 기존에 수행되었던 task가 terminate되면서 자신이 갖고 있던 자원을 release하기 때문이다. ( 따라서 safe sequence를 잘 찾기만 하면 점점 available 한 resource가 많아지므로 deadlock이 발생할 가능성은 점점 낮아진다.)

 

=> Safe한 sequence의 작동 방식은 

 1) 이미 한 프로세스가 실행되고 있으면, 뒤의 task들은 앞서 수행되는 task가 끝나길 기다린다.

 2) 한 프로세스가 수행이 끝나면, resource를 반납한다

 3) 따라서, available한 resource의 개수가 늘게 되고, 결국 deadlock이 발생할 여지가 줄어들게 되는 것이다.

 

 

 

 

# Banker's Algorithm

: 각 resource들이 multiple instance를 갖고 있을 때 deadlock이 발생할지를 검사하여 만약 deadlock이 발생할 여지가 있으면 자원을 할당하지 않고, deadlock이 발생하지 않는다면 자원을 할당해주는 알고리즘이다.

demanding resource <= available resource 기억할 것!!

 

1) Banker's Algorithm에서 필요한 자료구조

: n: 프로세스의 개수, m : 자원 타입의 개수

1. Available 

: m 길이의 vector로, available[j] = k라면, 지금 해당 resource안에 k개의 instance가 avilable한 것이다.

2. Max

: N X M 형태의 matrix로, Max[i,j]=k라면,  Pi 프로세스는 Resource type Rj에 대해서 최대 k개의 리소스 타입을 요청할 수 있다,

3. Allocation

: N X M 형태의 matrix로, 만약 Allocation[i,j]=k라면 Pi는 현재 Rj의 k instance를 할당받고 있다.

4. Need

 

 

=> 즉,  Max[ i, j] - Allocation [i, j] = Need[ i, j] 라고 할 수 있다.

 

EX)

 

 

=> Need 한 resource와 available한 resource를 계속 비교해가면서  Safe 한 sequence를 만들어낼 수 있다.

P2-> P3 ->P4-> P1 순으로 실행된다.

 

 

# Summary

- Resource Allocation graph를  이용해서 Cycle이 발생할 것 같으면 수행을 멈춘다.

- Multiple Instance => 이 조건에 맞지 않는다면 다른 프로세스를 try해가면서 safe sequence를 찾을 수 있게 된다. 

---

 

#Deadlock Detection

: Deadlock detection은 deadlock이 발생한 이후에 Deadlock을 감지하여 그 이후에 Deadlock에 빠진 상태에서 복구하는 방법이다. 

: 위의 Deadlock avoidance 와 deadlock을 검출하는 방법은 비슷하다.

 

1) Single Instance인 경우

 

 

 

-1번 RAG 그래프는 Resource와 process를 모두 표현해 놓고 있다. 해당 그래프에서 사이클이 발생하는지 관찰한다.

-2번 Corresponding wait-for graph 처럼 프로세스만 표현해 놓고 있어도 Cycle이 발생했는지 확인하는데는 전혀 

지장이 없다. 위 그래프를 살펴보면 Cycle이 여러개 발생하고 있는 것을 확인 할 수 있다.

 

=> Single Instance에서의 Deadlock은 Cycle이다.

 

 

 

 

2) Multiple Instance의 경우

 

: Banker's algorithm과 매우 유사하게 확인 할 수 있다.

 

- Deadlock avoidance : Need한 resource= Max- Allocation 

- Deadlock detection : Need 값 대신에 실제로 Request하는 개수로 바뀌게 된다.

 

 

 

: Need값은 현재 상태에서 요청하지 않아도 궁극적으로 작업을 끝내기 위해 필요한 양이다.

: Request는 당장 현재 상태에서 특정 자원을 요청한 상황을 말한다3

 

 

---

 

#Recovery

: Deadlock이 발생한 것이 확인되면 어떻게 한다? 

: 만약 Deadlock detection algorithm이 Deadlock이 발생한다는 것을 확인되면,

1)  OS에게 알려서 매뉴얼적으로 deadlock을 처리하도록 한다.

2) System이 자동으로 deadlock을 해결하도록 한다.

 

 

또, 두가지 방법론 측면에서 컴퓨터를 Deadlock으로부터 복구하는 방법이 존재한다.

1) Kill the process (가장 효과적이다)

2 ) Roll back 방식 (기존에 Deadlock이 발생하지 않는 상태로 프로그램을 되돌리는 것이다)

 

1. Process Termination

: Deadlock을 유발시킨 프로세스를 Terminate한다.

 => 이 때 모든 프로세스를 terminate해버릴 수도 있고,

 => Deadlock cycle이 없어질때까지 프로세스를 한번에 하나씩 종료시킨다

 

 : 만약 두번째 방법이라면, 어떤 프로세스를 먼저 terminate시켜야 하는가?

1) Process의 priority가 높은가?

2) 얼마나 더 많은 resource를 필요로 하는가?

=> 두 가지를 고려해서 어떤 프로세스를 Terminate할지 정한다.

 

 

2. Checkpoint & Rollback

 : Deadlock이 발생하지 않은 State로 프로그램을 되돌리는 것이다. 

=> Safe state까지 돌아가서 프로그램을 재수행 하게 된다.

: 이때, rollback하는 프로세스도 정해져 있어야 한다. (minimize cost라던가 policy가 필요하다)

 

 Q) 프로그램을 Roll back 하더라도 재수행이 가능할까?

 A) 프로그램을 rollback 했을 때 그때의 context값이 저장되어있지 않으면 재수행이 불가능하다

: 마치 티스토리 게시물을 쓰다 날렸는데 임시저장을 안해놨으면 아예 다시 써야하는 것처럼 ㅎㅎ

 

=> 이 Context값은 Checkpoint라는 부분에 저장되는데, Check point에서는 해당 부분에 context를 저장하고,

해당 checkpoint에서만 재수행이 가능하도록 한다.

 

 

 

 

1) 프로그램의 Context값은 오직 Checkpoint에만 저장되어있고, roll back을 하더라도 그 부분으로만 돌아갈수 있다.

 

2) 만약 프로그램을 수행하다가 Deadlock 이 detection 되었다면, 이전 Checkpoint 까지만 돌아간다.

: 왜냐하면 Checkpoint에만 이전 Context들이 저장되어있기 때문이다.

: 해당 정보들이 저장되어있어야만 그 부분에서 재수행이 가능하다.

 

3) 따라서, Deadlock이 detect되었다면 program counter는 checkpoint로 돌아가서 그 부분부터 실행을 다시하게 된다.