13-1 교착 상태란

식사하는 철학자 문제

1. 생각하다가 왼쪽 포크를 사용할 수 있으면 집는다.
2. 생각하다가 오른쪽 포크를 사용할 수 있으면 집는다.
3. 왼쪽, 오른쪽 포크를 모두 들었으면 일정 시간동안 식사한다.
4. 식사 시간이 끝나면 오른쪽 포크 놓는다.
5. 오른쪽 포크 놓은 후, 왼쪽 포크 놓는다.
6. 위의 과정을 반복한다.

• 모든 철학자가 동시에 왼쪽 포크를 집어들면, 식사를 영원히 할 수 없다.
• 교착 상태 발생
  • 프로세스 A 동작 중, 프로세스 B가 사용 중인 자원을 기다리고 있고, 프로세스 B 동작 중, 프로세스 A가 사용 중인 자원을 기다림.
  • 서로 기다리느라 어느 프로세스도 동작하지 않음.

자원 할당 그래프

• 프로세스가 어떤 자원을 사용하고 있고, 기다리고 있는지 표현하는 그래프

규칙

• 프로세스는 원으로, 자원 종류는 사각형으로 표현
• 사용 가능한 자원의 수는 자원 사각형 내에 점으로 표시
  • ex. 하드디스크가 3개 있으면, 하드디스크 사각형 내에 점 3개
• 프로세스가 자원 사용 중이면, 자원(점)에서 프로세스를 향해 화살표
• 프로세스가 자원을 기다리고 있으면, 프로세스에서 자원(사각형)을 향해 화살표

교착 상태 발생 조건

상호 배제

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없음

점유와 대기

• 자원을 할당 받은 상태에서 다른 자원 할당 받기를 기다리는 상태

비선점

• 다른 프로세스가 자원을 점유하록 있을 때, 강제로 자원을 빼앗지 못함

원형 대기

• 순환 형태로 프로세스가 자원을 점유하고, 대기하는 모습이면 교착 발생 가능
  • 항상 발생은 아님.

13-2 교착 상태 해결 방법

교착 상태 예방

상호 배제 없애기 - 불가능

• 모든 자원을 모든 프로세스끼리 공유 가능하도록 하면, 동기화 문제 발생

점유와 대기 없애기 - 불가능

• 프로세스가 모든 자원을 할당 받도록 하거나, 아니면 아예 할당 못 받게 하기
• 자원 활용률이 낮아짐.
  • 당장 자원이 필요해도 기다려야 하는 프로세스, 당장 사용 안하면서 오랫동안 할당된 상태로 있는 자원이 발생
  • 프로세스는 동시에 자원을 사용할 타이밍 찾기가 힘듦.
  • 많은 자원 필요한 프로세스가 기아 상황이 될 수 있음.

비선점 없애기 - 일부 자원 (CPU) 에서 효과적

• 다른 프로세스가 사용하는 자원 뺏어오기
• 일부 자원에 대해 효과적
  • CPU - 선점 가능.
    • 한 프로세스가 CPU 사용하다가 사용 시간 다 되면, 다른 프로세스가 CPU 할당 받음.
• 한 번에 하나의 프로세스만 이용 가능한 자원은 빼앗으면 안됨.
  • 범용성 떨어짐

원형 대기 없애기 - 단점 존재

• 모든 자원에 번호를 붙이고 오름차순으로 자원 할당
• 수많은 자원에 번호 붙이는 작업은 복잡함. 자원의 번호에 따라 특정 자원의 활용률 떨어질 수 있음.

결론

• 교착 상태 발생 조건을 원천적으로 제거하는 방식은 부작용이 있음.

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로 자원 할당
  • 교착 상태는 자원을 무분별하게 할당해서 발생하는 것.
• 안전 상태 : 교착 상태 없이 모든 프로세스가 정상적으로 자원 할당 받고 종료할 수 있는 상태. 안전 순서열대로 프로세스들에게 자원 배분
• 불안전 상태 : 교착 상태가 발생할 수 있는 상황. 안전 순서열이 없음
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스에게 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

• 교착 상태를 인정하고, 사후에 조치
• 운영체제는 프로세스가 자원 요구할 때마다 자원 할당, 교착 상태 여부 주기적 검사, 다음의 방식으로 조치

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아 줌 - 다른 프로세스로부터 자원을 뺏어서

프로세스 강제 종료를 통한 회복 - 단순&확실

• 교착 상태의 프로세스를 모두 강제 종료 - 작업 내용 잃을 수 있음
• 교착 상태가 없어질 때까지 하나씩 프로세스 강제 종료 - 교착 상태 없어졌는지 확인하는 과정에서 오버헤드 발생
• 타조 알고리즘 : 교착 상태를 아예 무시하기