5 Deadlock

Deadlock 이란

• 불가능한 상황을 기다리는 것 → 무한 대기 상태가 됨
• 확률은 희박하지만 이런 상황이 발생하기도 함

Deadlock 발생 조건

모두 만족해야 함

• exclusive resource: 자원을 동시에 나눠 쓸 수는 없음
• non-preemptive: 부족한 자원을 뺏어올 수 없음
• hold and wait(partial allocation): 일단 확보 가능한 것은 확보하고 대기
• circular waiting: 프로세스 자원 대기에 circle이 있어야 함

Deadlock방침

Deadlock Prevention

• 위의 deadlock 발생 조건 중 하나라도 발생하지 않도록 막는다.
• exclusive resource: 충분한 양의 resource를 확보한다 → 사용하지 않을 때는 낭비됨
• preemptive: process 죽이고 다시 시작함 → 낭비 증가, 실제로 사용 불가능함
• hold and wait: 모든 자원이 확보되기 전까지 대기 → 차후에 쓰일 resource가 없어도 대기하기 때문에 낭비 증가
• circular waiting: total allocation과 비슷하게 동작하게 됨

Deadlock Avoidance

• safe state에 있을 때만 할당한다.
• maximum require를 알아야만 한다 → 현실적으로 불가능 하기 때문에 예측함 → overhead 발생
• process 개수가 고정되어 있어야 한다.
• Dijkstra, Habermanm 방식이 있다.
• 최악의 경우를 대비하는 방식이다.

Deadlock detection & solving

• graph를 그려서 unblocked면 실행하고 blocked이면 현재 deadlock state에 있다고 판단한다.
• 만약 deadlock state이면 종료시킬 process를 선택한다.
  • cost가 가장 적은 것부터 종료시킴
  • cost는 지금까지 run time, resource 사용 등을 고려하여 정한다.
• kernel이 개입하여 어떤 걸 종료시킬 지 계산하기 때문에 overhead 발생한다. 따라서 실제로는 그냥 reboot 한다.
• graph를 그리는데 overhead 발생한다.
• 할당 가능한 자원은 바로 할당한다.
• 최상의 경우를 대비하는 방식이다.

이 글은 배운 내용을 정리한 것으로 오류가 있을 수 있습니다. 오류를 발견하셨다면 댓글로 알려주세요!