Deadlock

이 글은 KOCW 강좌 중 경성대학교 양희재 교수님의 '운영체제' 강의를 정리한 글입니다.

 

Deadlock

Deadlock

2개 이상의 Process가 서로 자원을 기다리다가 Process 모두 완료되지 못하는 상태를 Deadlock이라고 한다.

Process는 실행을 위해 CPU, Memory, file, printer 등 다양한 자원을 필요로 한다.

예를 들어, Process가 A,B 자원이 필요한데 A 자원만 있고 B 자원을 대기해야 한다.

다른 Process 역시 B 자원을 가지려고 기다리면 Deadlock, 교착상태가 될 가능성이 있다.

Deadlock 필요 조건

Deadlock이 일어나려면 4가지 필요 조건이 있다.

4가지 필요 조건이 다 충족해도 무조건 발생하는 것이 아니라 Deadlock일 가능성이 생기는 것이다.

• Mutual exculsion(상호 배타)
  • 1개 Process가 자원을 사용할 시, 다른 Process 자원 진입을 막는 것.
• Hold and wait(보유 및 대기)
  • Process가 자원을 소유하면서 대기 중인 상태
• No Preemption(비선점)
  • Process 수행 중에 다른 Process가 끼워들 수 없다.
• Circular wait(환형대기)
  • Process가 요구하는 자원의 방향이 원형을 이룬다.

위의 필요조건이 모두 충족해도 Deadlock이 무조건 일어나는 것은 아니다.

대신 Deadlock이 일어나면 Process는 자원을 가진 상태에서 아무것도 하지 않아 치명적인 상태이다.

Resources

Resouces는 동일한 형식의 자원이 존재할 수 있다.

Process는 운영체제에 Resource 사용을 요청한다.

Process는 Resource 사용 후 운영체제에 Resouce를 반납한다.

Resource Allocation Graph

자원할당도

어떤 Resource가 어떤 Process에 할당는지 그림으로 나타낸 것이다.

• Resource -> 사각형
• Instance -> 점
• Process -> 원
• 할당 -> 화살표

Deadlock 처리

Deadlock Prevention

Deadlock 방지는 Deadlock 필요조건 4가지를 만족시키지 않도록 하는 것이다.

• Mutual exculsion(상호 배타)
  • Resource를 공유 가능해야 하지만 현실적으로 불가능
• Hold and wait(보유 및 대기)
  • Resource를 가진 상태에서 대기하지 않도록 함(일부만 가지고 있을 경우 모두 반납 등...)
  • 자원 활용률을 저하시키고 starvation 발생
• No Preemption(비선점)
  • 현실적으로 불가능(Printer 수행 중간에 다른 Process 선점 불가능)
• Circular wait(환형대기)
  • 대표적으로 방지할 수 있는 방법은 Resource에 번호를 부여, 오름차순으로 Resource 요청
  • 자원 활용률 저하

Deadlock Avoidance

Deadlock 회피는 Resource 잘못 할당되지 않도록 하는 것이다.

안전한 할당(Safe Allocation)과 불안전한 할당(Unsafe Allocation)이 있다.

불안정한 할당이 되면 Deadlock이 일어날 수 있다.

운영체제는 불안전한 할당이 되지 않도록 해야한다.

Deadlock 회피는 대출전문 은행과 유사하게 동작해, 해결방법을 Banker's Algorithm이라고 한다.

Deadlock Detection & Recovery

위에 방법들은 사전에 Deadlock이 일어나지 않도록 하는 것이다.

Deadlock 검출 및 복구는 Deadlock 일어나는 것을 허용한다.

대신 주기적으로 Deadlock 일어나는지 검사해야 한다.

주기적으로 검사를 하게 되면 검사에 필요한 계산을 위해 Resource를 사용하게 된다.

그리고 복구를 위해 주기적으로 상태를 저장해야 한다.

아니면 일부 Process를 강제 종료 후 Resource를 다른 Process에 할당한다.

Deadlock 무시

Deadlock은 필요조건 4가지를 충족해도 반드시 일어나지 않는다.

그러다보니 Deadlock은 매우 드문 현상이다.

Deadlock를 주기적으로 검사하며 Resource를 쓰는 것이 오히려 비효율적인 환경도 있다.(예. PC ...)

Deadlock에 대해서 아무런 조치를 하지 않는 방법도 있다.