교착상태

교착상태(Deadlock)

교착상태(Deadlock)

• 여러 프로세스 들이 각자 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 요청하면서 무한하게 대기하는 상태

<프로세스의 자원>

• 시스템 자원 : CPU, 기억장치, I/O장치 ,파일, 세마포어 등
• 프로세스가 자원을 사용하려면 다음 순서로 수행한다
  1. 요청(request) : 요청이 즉시 허용되지 않는 경우, 자원을 얻을때까지 대기한다
  2. 사용(use)
  3. 해제(release) or 반환

---

교착상태 조건

1. 상호배제(Mutual exclusion)
   • 한 번에 오직 한 프로세스만이 자원을 사용할 수 있다
2. 점유와 대기(Hold and wait)
   • 프로세스가 적어도 하나의 자원을 점유하면서 다른 프로세스가 점유하고 있는 자원을 추가로 얻기 위해 대기한다
3. 비선점(No preemption)
   • 점유된 자원은 강제로 반환될 수 없고, 점유하고 있는 프로세스가 작업을 마치고 자원을 자발적으로 반환한다.
4. 순환대기(Circular wait)
   • 대기하고 있는 프로세스 집합{P0,P1...Pn}에서 P0->P1, P1->P2.. Pn-1->Pn, Pn->P0식으로 자원을 요청한다.

4가지 조건이 동시에 만족될 때 교착상태가 발생한다

---

교착상태 처리 방법

• 교착상태가 발생하지 않도록 예방(prevention)
• 교착상태를 가능한 회피(avoidance)
• 교착상태를 허용하고, 발생을 탐지한 후, 복구(dectection & recovery)

<교착상태에 관해>

대부분의 운영체제는 문제를 무시하고 교착상태가 발생하지 않는다고 가정한다. 교착상태가 잘 발생하지 않을 뿐더러, 교착상태 예방, 회피, 탐지 및 복구 방법을 사용하는 것은 비용이 많이 들기 때문이다

---

교착상태 예방(prevention)

교착상태 발생 4가지 조건 중에서 하나라도 성립되지 않으면 된다.

1. 상호배제 예방 방법

   • 공유가 가능한 자원들은 동시접근을 허용한다

2. 점유와 대기 예방 방법

   • 프로세스가 실행되기 전에 사용할 모든 자원을 함께 요청
   • 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청
   • 단점
     • 자원의 낮은 사용률 : 자원을 실제로 사용하지 않는 동안에도 자원을 점유하고 있어야 함
     • 기아 상태 가능성 : 프로세스가 필요한 자원들을 영원히 할당받지 못해서 계속 기다리고 있는 상태

3. 비선점 예방 방법

   • 어떤 자원을 가진 프로세스가 추가 자원을 요청하여 대기하게 되면, 가지고 있던 자원을 반환하고 대기함
   • 이후, 대기 중인 프로세스는 이전의 자원들과 새 자원을 모두 갖게 되면 다시 작업을 시작함

4. 순환대기 예방 방법

   • 모든 자원 유형에 일련 번호를 부여하고, 프로세스는 오름차순으로 자원을 요청

교착상태 예방법들은 자원의 사용률을 저하시키는 문제점이 있다

---

교착상태 회피(avoidance)

• 각 프로세스는 자원 유형마다 필요한 최대 개수를 선언하고, 운영체제는 이 정보를 이용해서 다음과 같이 교착상태가 되지 않도록 한다
• 어떤 프로세스가 자원을 요청하면, 이 자원을 할당한 후의 사애가 안정 상태인지 검사한다
  • 안정 상태이면 자원을 할당
  • 불안정 상태이면 자원을 할당하지 않는다 -> 교착상태 회피

<안정 상태(Safe State)>

<안정 상태와 교착상태의 상관관계>

• 시스템이 안정상태라면 교착상태가 없다
• 시스템이 불안정 상태라면 교착상태 가능성이 있다
• 교착상태는 불안정 상태이지만, 불안정 상태라고 모두 교착상태는 아니다
• 교착상태 회피는 시스템이 불안정 상태에 들어가지 않도록 하는 것이다

<교착상태 회피 알고리즘 : 은행가 알고리즘(Banker's Algorithm)>

은행가 알고리즘(Banker's) Alogrithm

은행가 알고리즘 단점

• 할당할 수 있는 자원의 수가 일정해야 한다
• 사용자 수가 일정해야 한다
• 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮다
• 최대 자원 요구량을 미리 알아야 한다
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다

서술된 단점들에 의해 운영체제의 오버헤드가 너무 커서 현재 채택되고 있는 방식은 아니다

---

교착상태 탐지(detection)

• 교착상태가 일어나도록 허용함
• 교착상태가 발생했는 지를 탐지하는 알고리즘 수행
• 교착상태로부터 회복하는 알고리즘 수행

유형1 - 각 자원 유형이 하나의 자원을 가진 경우

• 탐지 알고리즘은 주기적으로 수행하면서 대기 그래프에 주기가 생기는지 검사
  • 그래프의 정점이 n개이면, n^2의 연산이 필요함
• 대기그래프는 자원 할당 그래프를 변형해서 그린다. 자원형태의 정점을 제거하고, 정점을 프로세스로 표현한다.

유형2 - 각 자원 유형이 여러 자원을 가진 경우

• 교착상태 회피 알고리즘은 은행가 알고리즘과 비슷한 방법을 사용
• 차이점
  • 프로세스가 사용할 자원의 최대 개수를 미리 알지 않는다
  • 자원을 할당한 후의 상태를 검사하는 것이 아니라 현재 상태를 검사하여 교착상태를 탐지
  • 주기적으로 탐지 알고리즘을 수행해야 한다

    <교착상태 탐지 알고리즘>

    은행가 알고리즘과 매우 유사하다.

1. 사용 가능한 자원을 할당 했을때 해당 프로세스가 완료되면 자원을 돌려받는다
2. 돌려받은 자원으로 다른 프로세스에게 1번을 수행한다
3. 모든 프로세스에 대하여 1~2번의 작업이 가능한 순서가 존재한다면 교착상태가 아니다. 순서가 존재하지 않으면 교착상태 이다

---

교착상태 회복(recovery)

• 프로세스 종료
  • 교착상태에 있는 모든 프로세스를 종료시킨다
  • 교착상태가 해결될 때까지 프로세스를 하나씩 종료한다
• 자원 선점
  • 프로세스로부터 자원을 빼앗아서 이들을 교착상태가 해결될 때까지 다른 프로세스에게 준다

---

참고

• 교착상태 회피 - 은행원 알고리즘
• [System Software & Security Lab @ Myongji Univ. - Operating System ppt]