📌 교착상태 제거기법
✔️ 프로세스 중지 (Process Termination)
어쩔 수 없이 복구를 위해서, 프로세스가 강제로 비정상 종료함으로써 교착상태가 풀리도록 한다.
✔️ 리소스 제공 (Resource Preemption)
교착 상태에 있는 프로세스에게 자원을 강제로 제공함으로써 교착상태가 풀리도록 한다. (대부분 다른 프로세스에게서 빼앗아서 주는데, 이 경우 다른 프로세스가 잘못 종료될 수도 있다)
1. 프로세스 중지 기법
☑️ 어떤 프로세스를 종료시킬까?!
Termination Cost 모델
각 프로세스를 종료시킬 경우의 손해 비용을 계산한다.
프로세스의 우선순위, 프로세스 타입(Interactive, Batch, Real Time등), 총 실행 시간과 잔여시간, 프로세스들이 지금까지 사용한 자원 등 여러 파라미터를 고려한다.
1) Lowest-Termination-Cost-Process First 기법
Termination Cost를 계산하고, 가장 비용이 작은 process부터 종료시킨다.
P3 종료 -> detection 알고리즘, 아직 교착상태 -> P6 종료 -> detection 알고리즘, 아직 교착상태 -> p1 종료 -> detection 알고리즘, 교착풀림.p1, p3, p6은 종료되고 다시 처음부터 시작하고, 나머지 p2, p4, p5는 자원을 할당 받게 된다.
✔️ 단순하고 오버헤드도 적지만 항상 최적의 기법은 아니다.
알고 보니 p1, p6만 종료되어도 교착상태가 풀릴 수 있기 때문이다. 이 경우 p3의 경우 cost가 낮다는 이유만으로 종료당한 것일 수도 있다.
2) Minimum Cost Recovery 기법
종료되기에 최적의 프로세스 집합을 찾아 낸다.
총 6개의 프로세스가 교착상태에 있는데, 그 중 subset을 전부 다 검사하여 (2의 6승 갯수의 subset) 최적의 cost를 계산해본다.
그리고 가장 적은 비용의 subset을 계산하고 종료시킨다.
✔️이 경우 시간복잡도가 굉장히 크고 오버헤드가 크다. 따라서 현실적으로 사용하기 어렵다.
2. Resource Preemption 기법
교착상태에 걸린 프로세스에게 자원을 나누어주고, 빼앗긴 프로세스는 강제종료될 수 있는 기법이다.
☑️ Victim을 어떻게 선정할 것인가?!
➡️똑같이 Termination Cost Model을 이용하여 강제종료될 프로세스를 고른다.
📌 Rollback
1) Total Rollback
Termination 당한 프로세스들이 처음부터 돌아가서 새로 시작하는 것
2) Partial Rollback (=Checkpoint restart)
처음으로 돌아가는 것이 아니라 약간 뒤로 돌아가는 것. 부분 roll back이 가능하다면, 조금만 뒤로 돌아가는 것이 좋을 수 있다. 단 그 때의 지점에서 Context Saving이 되어 있어야 하기 때문에 중간 중간 저장을 해 두어야 한다!
