• 스터디 설명 : 에이블스쿨 교육생들과 CS 공부를 위해 자발적으로 개설 및 참여한 스터디입니다.
• 혼자 공부하는 컴퓨터 구조+운영체제를 교재로 사용하였고, 일부 내용은 별도의 자료로 공부하였습니다.

13-1 교착 상태란

• 두 개 이상의 작업이 서로의 작업이 끝나기를(자원이 반환되기를) 기다리며 진행이 멈춰 버리는 현상을 교착상태(deadlock)라고 한다.
• 교착 상태는 아주 다양한 상황에서 발생한다.
  • 예를 들어 뮤텍스 락에서 프로세스 A가 임계구역 a에 진입하여 임계구역 a를 잠그고(lock_a=True), 프로세스 B가 임계구역 b에 진입하여 임계구역 b를 잠근 상태이다.(lock_b=True)
  • 이 상황에서 프로세스 A는 lock_b=False가 될때까지 임계구역 a에서 대기하고, 반대로 프로세스 B는 lock_a=False가 될 때까지 임계구역 b에서 대기한다면, 바로 교착상태가 발생하게 된다.
  • 일반적으로 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 프로세스가 서로 경쟁할 때 주로 발생한다.
• 교착 상태를 해결하기 위해서는
  1. 교착 상태가 발생했을 때의 상황을 정확히 표현해야 함 → 자원 할당 그래프
  2. 교착 상태가 일어나는 근본적인 이유를 알아야 함

자원 할당 그래프(resource-allocation graph)

규칙

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 사각형 내에 점으로 표현
   • 하드 디스크가 세 개 있는 경우 자원의 종류는 하나이지만, 사용 가능한 자원의 개수는 세 개 (CPU, 메모리 등에도 동일하게 적용)
3. 프로세스가 어떤 자원을 할당받아 사용중이라면, 자원에서 프로세스쪽으로 화살표 표시
   • 프로세스가 자원을 반납하면 화살표를 삭제
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원쪽으로 화살표 표시
5. 만약 자원 할당 그래프가 사이클을 이루고 있다면(원의 형태를 띄고 있다면) 교착 상태가 발생할 가능성이 있다.

교착 상태 발생 조건

• 교착 상태가 발생할 조건은 크게 네 가지가 있다.
  • 상호 배제 - 한 자원을 여러 프로세스가 이용할 수 없음
  • 점유와 대기
  • 비선점 - 자원을 한번 할당 받으면 다른 프로세스가 가져갈 수 없음
  • 원형 대기 - 자원 할당 그래프에서 사이클이 이루어짐
• 이 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않으며, 네 가지 조건을 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다.

상호 배제

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

점유와 대기

• 자원을 점유한 채(할당 받은 채)로 다른 자원의 할당을 기다림

비선점

• 자원을 한번 할당 받으면 다른 프로세스가 가져갈 수 없음

원형 대기

• 자원할당 그래프를 그릴 때 사이클이 이루어지는 형태
• 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다. (다른 조건을 동시에 모두 만족해야함)

13-2 교착 상태 해결 방법

• 교착 상태를 해결하는 방법에는 크게 세 가지 관점이 있다.
  • 예방 : 교착 상태 발생 조건에 부합하지 않도록 자원을 분배하는 것
  • 회피 : 교착 상태가 발생할 가능성이 있으면 자원을 할당하지 않는 것
  • 검출 후 회복 : 제약 없이 자원을 할당하다가, 교착 상태를 발생하면 회복하는 것

교착 상태 예방

• 상호 배제, 비선점, 점유와 대기, 원형 대기 네 가지 조건 중 하나를 충족하지 못하게 하는 방법과 같다.
• 상호 배제 부정 : 현실적으로 상호 배제를 없애는 것은 어렵다.
• 점유와 대기 부정 : 점유와 대기를 없애려면 특정 프로세스는 필요한 자원을 동시에 모두 할당받다거나, 하나라도 할당받지 못하거나 둘 중 하나여야 한다.
  • 단점 : 자원의 활용율이 낮아지며, 많은 자원을 사용하는 프로세스가 실행되기 어려워진다. (특정 프로세스가 무한히 대기 상태가 될 가능성도 존재)
• 비선점 부정 : 다른 프로세스가 자원을 요청할 때 가진 자원을 반납하도록 한다.
  • 대표적으로 CPU가 있다.
  • 다만 프린터와 같은 일부 자원은 물리적인 이유로 선점을 적용할 수 없다.
  • 때문에 비선점을 없애는 것은 범용적으로 사용할 수 있는 방법이 아니다.
• 원형 대기 : 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기가 발생하지 않는다.
  - 원형대기가 완성되려면 1-2, 2-3, 3-1 형태의 대기가 있어야한다.
  - 만약 오름차순 순으로만 자원을 할당한다면 3-1의 대기는 불가능하기 때문에 원형 대기가 발생하지 않는다.
  - 다만 자원에 번호를 부여하는 것도 쉽지 않은 작업이고, 특정 번호를 가진 자원의 활용률이 감소할 수 있다.

  정리하자면 예방 방법은 효과적일 수 있으나, 대개 여러 부작용을 동반한다. 특히 자원을 효율적으로 사용하기 어렵다.

교착 상태 회피 (은행원 알고리즘)

• 교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식
  • 교착 상태의 근본 원인을 한정된 자원의 무분별한 할당으로 인해 발생한다고 간주
  • 안정 상태와 불안전 상태로 구분하여 자원 할당을 제한한다.
    • 안전 상태 : 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
    • 불안전 상태 : 교착 상태가 발생할 수도 있는 상황
    • 안전 상태의 여부는 안전 순서열(safe sequence)를 통해 판단함
• 안전 순서열은 교착 상태 없이 안전하게 프로세스를 할당할 수 있는 순서를 의미한다. 안전 순서열이 하나라도 존재할 경우 안전 상태로 판단한다.
• 운영체제는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다. 즉 항시 안전 상태를 유지함으로써 교착 상태의 발생을 회피한다.

교착 상태 검출 후 회복

• 교착 상태가 발생했을 때 이를 검출(인정)하고 회복하는 방법이다.
  • 검출을 위해 주기적으로 탐지 알고리즘이 실행되어 오버헤드가 발생한다.
• 운영체제는 프로세스의 요구에 따라 그대로 자원을 할당하며, 주기적으로 교착상태 발생 여부를 검사한다. 교착 상태가 발생했다면 여러 회복 방법을 적용한다.

선점을 통한 회복

• 교착 상태가 해결될 때까지 다른 프로세스의 자원을 회수하여 한 프로세스씩 자원을 몰아주는 방법
• 보통 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 자원을 선점시킨다.

프로세스 강제 종료를 통한 회복

• 방법 1 : 교착 상태가 발생한 모든 프로세스를 강제 종료
• 방법 2 : 교착 상태가 해결될 때까지 한 프로세스 씩 강제 종료
• 종료된 프로세스는 작업 내용을 잃게되는 위험성이 존재하며, 방법2를 사용할 경우 오버헤드를 야기

타조 알고리즘(ostrich algorithm)

• 교착 상태를 아예 무시하는 방법
• 교착 상태에 대한 아무런 대책 없이 컴퓨터 시스템을 가동하고, 교착 상태가 발생하면 시스템을 재시작하거나 특정 스레드를 강제 종료하는 방법으로 해결한다.