[OS] 운영체제(6장) 교착상태 - 1

1. 시스템 모델

• 시스템 모델
  • 자원(resource) - 유한한 개수의 자원
  • 프로세스(process) - 자원 사용을 경쟁하는 프로세스들
• 자원
  • 시스템의 자원은 여러 유형(type)으로 구분됨
  • 물리적 자원: CPU 사이클, 메모리 공간, I/O 장치
  • 논리적 자원: 파일, 세마포, 뮤텍스 락
  • 각 유형의 자원(Ri)은 여러 개(Wi)의 인스턴스(instance)를 가질 수 있음
• 프로세스의 자원 이용 과정
  1. 요청(request) – 요청 자원을 즉시 사용할 수 없으면, 자원을 획득할 때까지 대기해야 함
  2. 사용(use)
  3. 방출/해제(release)
     • 이와 관련된 시스템 호출 : open() – close(), request() – release(), allocate() – free(), wait() – signal()

교착상태 문제

교착상태

프로세스 집합에 있는 모든 프로세스가 한 자원을 점유하고, 같은 집합의 다른 프로세스가 점유한 자원의 획득을 기다리는 상태 → 모든 프로세스가 진행되지 못함

2. 교착상태의 특징

교착상태가 발생하는 필요조건

1. 상호배제(Mutual exclusion)
   • 한 번에 한 프로세스만 사용할 수 있는 자원(비공유 모드로 점유되는 자원)이 적어도 하나 존재
2. 점유하며 대기(Hold and wait)
   • 프로세스가 최소 하나의 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기
3. 비선점(No preemption)
   • 자원이 강제로 방출될 수 없고, 자발적으로만 방출될 수 있음
4. 순환대기(Circular wait)
   • (예) 식사하는 철학자 문제

3. 교착상태 처리 방법

교착상태 예방(prevention) 또는 회피(avoidance)

• 시스템이 deadlock 상태가 되지 않도록 보장하는 방법
• deadlock prevention :
  • 4가지 필요조건 중 하나 이상을 만족하지 않게 함
• deadlock avoidance :
  • 부가적인 정보를 사용하여 자원 요청을 위해 프로세스가 대기할 지 여부를 결정

교착상태 탐지(detection) 후 복구(recovery)

• deadlock 상태가 되는 것을 허용
• deadlock detection 알고리즘과 deadlock recovery 알고리즘으로 구성

교착상태 무시

• deadlock이 자주 발생하지 않기 때문에 예방/회피나 탐지를 하지 않음
• 수작업으로 복구
• 대부분의 운영체제(Linux, Windows)에서 사용
  • 응용프로그램의 deadlock 방지는 응용 프로그래머 책임

교착상태 예방

4가지 필요조건들 중 적어도 한 개를 만족하지 않게 함

1. 상호배제 조건 거부

• 동시 공유 가능 자원은 상호배제 하지 않음 (예) 읽기 전용 파일
• 동시 공유 불가능 자원은 상호배제를 해야 함

2. 점유 대기 조건 거부

• 자원을 요청할 때에 다른 자원을 점유하지 않은 상태에서 자원을 요청
• 두 가지 방법
  1. 실행하기 전에 모든 자원을 요청하여 할당 받도록 함
  2. 점유 자원을 반납한 후에 이 자원과 추가 자원을 요청함
• 단점
  • 자원 이용률이 낮음 - 자원들이 할당된 후 일부 자원이 오랫동안 사용되지 않을 수 있음
  • 기아 가능성

3. 비선점 조건 거부

• 어떤 자원을 점유한 프로세스가 다른 자원 요청하여 즉시 할당 받을 수 없으면,
• 방법 1: 현재 점유한 모든 자원을 반납하고 대기 상태가 된다. 프로세스는 반납한 자원과 추가 요청 자원들의 대기 리스트에 추가
  • 반납한 자원과 요청한 자원을 할당 받을 수 있을 때에 재개됨
• 방법 2: 요청한 자원을 이용할 수 없거나 다른 대기 프로세스가 점유하지 않았다면 대기 상태가 됨
  • 점유한 자원은 다른 프로세스가 요청하는 경우에만 선점되어 반납
  • 선점된 자원과 요청한 자원을 할당 받을 수 있을 때에 재개됨
• 단점:
  • CPU 레지스터나 메모리 공간처럼 저장과 복원이 용이한 자원에만 선점 적용가능

4. 순환 대기 조건 거부

• 모든 자원들에 전체적인 순서(total ordering) 부여
  • One-to-one mapping function: F(r) = n (r: resource, n: integer)
• 여러 개의 자원이 필요한 경우에 오름차순으로 자원들을 요청함
  • Ri을 점유한 프로세스는 F(Rj) > F(Ri) 일 때만 Rj 를 요청할 수 있음
  • F(Rj) <= F(Ri) 인 자원 Ri 은 반납해야 함
• 위의 두 가지 프로토콜을 사용하면 순환 대기가 발생하지 않음

교착상태 회피

교착상태 예방의 단점

• 장치 이용률(utilization) 저하
• 시스템 처리율(throughput) 감소

교착상태 회피(avoidance) 방법

• 자원이 어떻게 요청되는 지에 대한 추가 정보를 필요로 함
  • 필요로 하는 각 유형별 자원에 대한 최대 수 등.
• 자원 할당 상태를 조사하여 순환 대기 조건이 발생하지 않도록 자원 요청을 제어함