[CS] 운영체제 - Deadlock

데드락이란 교착상태를 말한다. 일련의 프로세스들이 서로가 가진 자원을 기다리며 blcok된 상태를 말한다.

 

Resource(자원)

자원은 하드웨어, 소프트웨어 등을 포함하는 개념이다.

예를 들어 I/O 장치, CPU cycle, memory space, semaphore 등이 있다.

프로세스가 자원을 사용하는 절차는 크게 4 단계를 거친다.

1. request: 자원 요청
2. allocate: 자원을 획득
3. use: 자원을 사용
4. release: 자원을 반납

Deadlock 발생의 4가지 조건

데드락이 발생하려면 아래 4가지 조건을 모두 만족해야한다.

1. Mutual exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
2. No preemotion(비선점): 프로세스는 자원을 스스로 내어놓을 뿐이고 강제로 뺏기지 않는 상황
3. Hold and wait(보유 대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
4. Circular wait(순환 대기): 자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.

Deadlock의 처리 방법

사전에 미리 방지하는 방법

Deadlock prevention: 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 방법이다. 이러한 방식은 자원의 이용률의 저하, 시스템 성능 감소, starvation 문제등이 생길 수 있다. (생길지도 모르는 deadlock을 방지하기 때문이다.)

• Mutual exclusion(상호 배제): 공유해서는 안되는 자원의 경우 반드시 성립해야 한다.
• Hold and wait: 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법
• No preemotion(비선점)
  • process가 어떠한 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
  • State를 쉽게 save하고 복구할 수 있는 자원에서 주로 사용한다.
  • 자원을 빼앗아 올 수 있게 하면 된다.
• Circular wait(순환 대기)
  • 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원 할당을 한다.

Deadlock Avoidance: 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다. 가장 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하게 하는 방법이다.

• safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태이다.

Deadlock이 생겼을때 처리하는 방법

Deadlock Detection and recovery: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 둬서 deadlock 발견시 회복하는 방법이다.

• resource 타입당 싱글 인스턴스인 경우 자원할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
• resource 타입당 멀티 인스턴스인 경우 Banker's algorithm과 유사한 방법을 사용한다.
• Recovery
  • Process termination: 데드락에 연루된 프로세스를 한번에 kill한다.
  • Resource Preemption:: 데드락이 없어질때까지 프로세스를 하나하나 죽여본다.

Deadlock에 관여하지 않는 방법

Deadlock Ignorance: Deadlock을 시스템이 책임지지 않는다. UNIX를 포함한 대부분의 OS가 채택하는 방식이다.

• Deadlock이 일어나지 않는다고 생각하고, 아무런 조치도 취하지 않는다. 
• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 오버헤드가 될 수 있다.
• 만약 시스템에 deadlock이 발생한 경우 사람이 느낀 후, 직접 process를 죽이는 방법 등으로 대처한다.