😽 교착 상태 문제 (Deadlock Problem)

프로세스가 한 자원을 점유하고 봉쇄되고(blocking), 다른 프로세스가 이 자원을 획득하기 위해 요청 후 기다리는 상태

• 예
  • 하나의 프린터와 하나의 DVD 드라이브가 있는 시스템
  • 프로세스 P1는 DVD 드라이브를 점유하고, 프로세스 P2는 프린터를 점유한다고 가정
  • P1가 프린터를 요청하고, P2가 DVD 드라이브를 요청한다면 교착 상태가 발생
  • 각각은 프린터와 DVD를 방출하는 사건을 기다리는데, 이 사건은 서로 대기 중인 프로세스들 중의 어느 하나에 의해서만 발생이 가능

🤺 시스템 모델 (System Model)

• 시스템의 자원(resource)은 다수의 유형으로 분할
• 각 자원의 유형은 동등한 다수의 인스턴스(instance)들로 구성
  • 한 시스템의 두 개의 SPU를 가진다면, 자원 유형 CPU는 두 개의 인스턴스를 가짐
• 프로세스는 다음 순서로만 자원을 사용
  • 요청(request) : 요청이 즉시 허용되 않으면 요청 프로세스는 자원을 얻을 때까지 대기
  • 사용(use) : 프로세스는 자원에 대해 작업을 수행
  • 방출(release) : 프로세스가 자원을 방출

🦛 교착 상태의 특징

교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생

• 상호 배제(mutual exclusion) : 한 번에 오직 한 프로세스만이 한 자원을 사용
• 점유하면 대기(hold and wait) : 최소한 하나의 자원을 점유한 프로세스가 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기해야 함
• 비선점(no preemption) : 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로 방출
• 순환 대기(circular wait) : 대기하고 있는 프로세스의 집합에서는 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고, 그 뒤를 계속 대기하여 Pn이 P0 자원을 대기

다중 스레드 응용에서의 교착 상태

• 교착 상태는 시스템 콜(자원 요청, 해제), 도익화를 위한 락킹 등에 의해서 발생
• 다중 스레드 응용에서 뮤텍스락, 세마포 등을 사용한 동기화 시에는 응용 개발자는 교착 상태의 가능성을 고려해야 함

☘ 자원 할당 그래프 (Resource-Allocation Graph)

정점(vertext) V의 집합과 간선(edge) E의 집합으로 구성된 그래프

• V는 두 가지 유형으로 구별
  • P = {P1, P2, P3, P4 … Pn} 시스템 내의 모든 활성 프로세스의 집합
  • R = {R1, R2, R3, R4 … Rm} 시스템 내의 모든 자원 유형의 집합
• 방향 간선(directed edge)은 Pi → Rj : 프로세스가 Pi가 자원 유형 Rj의 인스턴스를 하나 요청
• 방향 간선은 Ri → Pk : 자원 유형 Rj의 한 인스턴스가 프로세스 Pk에 할당

• 자원 할당 그래프에 사이클이 없다면, 시스템은 교착 상태가 아님
• 사이클이 있는 경우
  • 자원 유형 당 하나의 인스턴스만 있다면 교착 상태
  • 자원 유형 당 여러 개의 인스턴스가 있다면 교착 상태의 가능성

🚀 교착 상태 처리

교착 상태 처리

원칙적으로 교착 상태 문제를 처리하는 세 가지 방법

• 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 사용
• 시스템이 교착 상태가 되도록 허용한 다음에 회복시키는 방법
• 문제를 무시하고, 교착 상태가 시스템에서 결코 발생하지 않는 척 함
  • UNIX와 Windows를 포함해 대부분의 운영체제가 사용하는 방법

교착 상태 예방

교착 상태를 발생시키는 네 가지 조건 중에서 최소한 하나가 성립하지 않도록 보장

• 상호배제 (Mutual Exclusion) : 공유 가능한 자원들은 배타적인 접근을 요구하지 않아서 교착상태 발생x
  • 읽기 전용 파일 등
• 점유하며 대기 (Hold and Wait) : 프로세스가 자원을 요청할 때는, 다른 자원들을 점유하지 않을 것을 반드시 보장해야 함
  • 각 프로세스가 실행되기 전에 사용되는 모든 자원을 요청하고 모두 할당 받을 것을 요구
  • 다른 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용
  • 단점
    • 많은 자원들이 할당된 후 오랜 동안 사용되지 않기 때문에 자원의 이용도가 낮음
    • 기아 상태 유발 가능성
• 비선점 (No Preemption) : 이미 할당된 자원이 선점되지 않아야 한다는 조건이 성립되지 않도록 보장하는 프로토콜을 사용
  • 만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 점유하고 있는 모든 자원들이 선점 → 즉, 현재 점유 자원들을 방출(release)
  • 선점된 자원들은 기다리고 있는 프로세스 자원들의 리스트에 추가
  • 자원이 선점된 프로세스는 자신이 요청하고 있는 새로운 자원과 점유했던 예 자원들을 다시 획득할 수 있을 때에만 다시 시작
• 순환 대기 (Circular Wait) : 순환 대기 조건이 성립되 않도록 모든 자원 유형들에게 전체적인 순서를 부여
  • 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구
• 교착 상태 예방 알고리즘은 요청 방법을 제약하여 교착 상태를 예방
  • 이 제약은 교착 상태를 위해 필요한 조건 중 최소한 하나가 발생하지 않도록 보장
  • 이런 방식으로 교착 상태를 예방할 때 가능한 부수적인 문제는 장치의 이용률이 저하되고 시스템 처리율( throughput)이 감소

🦴참고

Operating System Concepts, 10th Ed.