운영체제(7) - Deadlocks(1)

‘운영체제’를 공부하여 정리한 내용입니다.

1. System Model

시스템의 구성

• 시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다.

  • 자원은 다수의 타입으로 분할되면, 각각은 동등한 다수의 instance들로 구성된다.
    • 자원 타입의 예) 메모리 공간, CPU 주기, 파일, I/O 장치 등
    • 만약에 한 시스템이 두 개의 CPU를 가진다면, CPU타입의 instance가 두 개 있는 것이다.

• 프로세스는 동작하면서 특정 자원 타입의 인스턴스를 요청하게 되고, OS는 이를 할당하게 된다.

  • 프로세스는 자원을 사용하기 전에 반드시 요청해야 하고, 사용 후에는 반드시 반납해야 한다.
  • 자원 사용을 위해 다음의 순서를 따른다.
    1. 요청
    2. 사용
    3. 방출
  • 자원이 할당될 때는 어디에 할당되었는지 기록된다.
  • 만약 어떤 프로세스가 동일한 자원을 요청하면, 그 자원을 기다리는 Process queue에 입력될 수 있다.

• 여기에서 한 프로세스 집단을 생각해보자.

  • 이 안에 있는 모든 프로세스가 같은 집합 내의 다른 프로세스에 의해서만 발생할 수 있는 사건을 서로 기다리고 있다면
  • 지금 이 프로세스 집합은 교착 상태에 있는 것이다.
  • 그리고 주로 이 사건은 자원의 획득과 방출을 의미한다.

• Multi Thread Application을 개발하는 프로그래머는 반드시 이 문제에 특별히 신경을 써야 한다.

  • Thread의 경우는 특히 자원을 두고 경쟁하는 경우의 수가 많이 발생한다.

2. Deadlock Characterization

필요 조건들 (꼭 외워두기!)

1. Mutual Exclusion

   • 어떤 자원이 비공유 모드로 점유되어야 한다는 의미다. 만약 공유모드로 점유된다면 다른 프로세스가 이 프로세스가 이 자원을 반납하길 기다릴 필요가 없다.
2. Hold-and-wait
   • 프로세스는 최소한 하나의 자원을 점유한 채, 다른 프로세스가 점유하고 있는 자원을 얻기위해 대기하고 있어야 한다.
3. No Preemption
   • 특정 프로세스에서 다른 프로세스가 점유한 자원을 함부로 빼앗을 수 없어야 한다는 의미다. 이는 모두가 자원 점유에 있어서는 동등한 위치에 있기에 스스로 자원을 반납하지 않는 이상은 자원이 반납될 가능성이 없어야 한다는 의미이다.
4. Circular wait
   • 2번에 따라 프로세스는 자원을 점유하고 다른 프로세스의 자원을 기다린다. 이 때, 존재하는 프로세스가 {p0, p1, … , pN}일 때, p0는 p1의 자원을 기다리고, 같은 방식으로 따라 갔을 때, PN은 P0의 자원을 기다리는 형태가 된다는 의미이다.

자원 할당 그래프

• 그리는 방법은 생략하겠다.
• 중요한 것은 다음과 같은 내용이다.
  • 자원 할당 그래프에 사이클이 없다면, 시스템은 교착상태가 아니다.
  • 반면에, 사이클이 있다면 시스템은 교착상태일 수도 있고, 아닐 수도 있다.

3. Methods for Handling Deadlocks

접근법

• 교착상태를 예방하거나, 회피한다.
• 교착상태가 되도록 허용하고, 다음에 회복시킨다.
• 문제를 무시한다. 시스템에서 결코 발생하지 않는 척 한다.
  • 현대의 많은 OS는 이 방법을 사용한다.
  • 이전에 Job Scheduler 관련에서도 아예 구현을 안 하는 것도 그렇고, 생각보다 어떤 부분은 과감하게 포기하는 것이 나은 경우도 있는 것 같다.

4. Deadlock Prevention

고려

• 위에서 얘기했던 Deadlock의 4가지 요건을 차례로 고려하면서 생각해보는 과정을 거친다.
  • 원인을 분석하고 나누어서 필요한 일을 찾는 것이다.
  • (추후 업데이트)

5. Deadlock Avoidance

안전 상태(Safe State)

• 시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 교착상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 의미한다.
  • 만약에 시스템이 위와 같은 Safe sequence를 찾을 수 있다면 시스템은 Safe하다.
  • 반대로, 찾지 못한다면 unsafe하다.
    • Deadlock이 발생할 가능성이 있다는 의미이다.
    • 운이 좋다면, 안 일어날 수도 있다.

Resource-Allocation Graph Algorithm

• 예약 간선(clain edge) 등을 사용해서 Deadlock에 영향을 주는 Cycle이 생기는지를 계속 확인할 수 있다.

Banker’s Algorithm

• (추후 업데이트)

6. Deadlock Detection, 7. Recovery from Deadlock

• (추후 업데이트)