07. 교착상태

강의 목표

• 식사하는 철학자 문제를 통해 처음으로 제기된 교착상태 개념을 이해한다.
• 컴퓨터 시스템에서의 교착상태 정의와
  교착상태를 판단할 수 있는 자원 할당 그래프를 이해한다.
• 교착상태가 유발 가능한 코프만의 4가지 조건을 이해한다.
• 교착상태의 해결 방법을 이해한다.
  교착상태 예방, 회피, 감지 및 복구, 무시
• 현대에서 교착상태 해결 방법은 교착상태 무시 방법임을 안다.

01. 교착상태 문제 제기

1.1 무한 대기와 교착상태

교착상태(deadlock)

• 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기
  컴퓨터 시스템에서 교착상태는 다중프로그래밍 도입과 함께 발생하게 되었다.
• 스레드 동기화 문제의 연장선

1.2 식사하는 철학자 문제(Dining Philosophers Problem)

문제의 개요

1965 년 Edsger Dijkstra에 의해 처음으로 문제화
병렬처리(concurrent programming)에서의 동기화 이슈와 해결 방법을 설명하고자 낸 학생 시험 문제(네델란드의 Eindhoven University of Technology)

• 5명의 철학자가 원탁에서 식사. 식사 시간은 서로 다를 수 있음
• 자리마다 스파게티 1개와 양 옆에 포크 있음
• 각 철학자는 옆의 철학자에게 말할 수 없음
• 식사를 하기 위해서는 양 옆의 포크를 모두 확보하여야 함
• 왼쪽 포크를 먼저 들고, 다음 오른쪽 포크를 드는 순서
• 포크가 사용 중이면 대기

문제
모두 거의 동시에 왼쪽 포크를 든 후, 오른쪽 포크를 들려고 할 때,
모두 상대가 가진 포크를 기다리면서 먹을 수 없는 교착 상태 발생

해결 방법
5명 중 마지막 사람을 제외한 4명이 왼쪽 포크를 먼저 잡고,
오른쪽 포크를 잡는 순서로 진행하고,
마지막 사람은 오른쪽 포크를 잡고 왼쪽 포크를 잡도록 함

철학자가 식사하는 모든 경우 분석

철학자들의 교착상태 원인 - 환형 요청/대기(circular request/wait)

• 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리 형성
• 환형 고리는 스스로 인식하거나 해체 불가

교착상태 해결 - 환형 요청/대기가 생기지 않게 규칙 변경

• 마지막 철학자만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙 수정
  → 알고리즘으로 어떻게 표현할 것인가?

1.3 식사하는 철학자와 컴퓨터 시스템

식사하는 철학자 문제는 교착 상태 문제를 비유

교착상태는 다중프로그래밍 시스템 초기에 노출된 문제점

• 철학자: 스레드
• 포크: 자원
• 스파게티: 스레드가 처리할 작업

02. 교착상태

2.1 교착상태 정의

교착상태(deadlock)

• 자원을 소유한 2개 이상의 스레드들 사이에서,
  각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하는 현상
  1965년 Dijkstra의 banker's algorithm research에서 처음 제기
  풀지 못하는 포옹(deadly embrace)이라고도 함

교착상태 발생 위치

• 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생
  정교하지 못한 코딩에서 비롯

• 커널 내에서도 발생
  하지만 거의 발생하지 않음, 매우 정교하게 작성되었기 때문

• 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없음
  막는 데에 많은 시간과 공간 비용 때문
  교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면,
  사용자가 시스템 재시작, 또는 의심스러운 몇몇 프로그램 종료

전형적인 멀티스레드 교착상태 사례

• 2개의 스레드가 각각 락 소유하고, 상대가 가진 락을 요청하고 기다릴 때
  단일 CPU/다중 CPU 모두에서 발생
  T1과 T2가 서로 다른 CPU에서 실행될 때에도 발생

• 락과 자원에 대한 경쟁이 있는 한 교착상태는 언제든 발생 가능
  

2.2 컴퓨터 시스템에 잠재된 교착상태 유발 요인

1) 자원

• 자원은 교착 상태의 발원지
• 교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
  컴퓨터 시스템의 자원
  소프트웨어 자원: 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스 파일 락
  파일 락: 스레드가 파일의 일부나 전체를 독점 사용하기 위한 잠금
  (Unix에서 flock, POSIX의 파일락 등)
  하드웨어 자원: 프린터, 메모리, 프로세서 등

2) 자원과 스레드

• 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인
  한 개의 자원만 필요한 경우 교착상태가 발생하지 않음

3) 자원과 운영체제

• 한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인
• 스레드가 자원을 필요로 할 때, 반드시 운영체제로부터 할당받아야 함
  운영체제로부터 필요한 자원을 한 번에 모두 할당받는다면,
  교착상태가 발생하지 않을 수 있음

4) 자원 비선점

• 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책
• 대부분의 운영체제는 스레드가 할당받은 자원을 강제로 빼앗지 못한다.
  강제로 빼앗아 기다리는 스레드에게 줄 수 있다면,
  교착상태가 발생하지 않는다.
  빼앗긴 스레드에게는 문제가 발생

2.3 교착상태 모델링

자원 할당 그래프(Resource Allocation Graph, RAG)

• 컴퓨터 시스템에서 자원 할당 그래프를 이용하여 교착 상태를 표현하고
  이 그래프를 기반으로 교착상태 예방, 회피, 감지 등이 운용됨

• 컴퓨터 시스템에 존재하는 자원과 스레드들의 상태를 나타내는
  방향성 그래프(graph)이다.

부모/자식 관계가 성립하는 트리 구조로는 구현할 수 없음

그래프의 요소

• 꼭짓점(vertex)
  스레드(원), 자원(사각형)
• 간선(edge)
  할당 간선(allocation edge)과 요청 간선(request edge), 소유-요청 관계

표현되는 정보

• 컴퓨터 시스템에 실행 중인 전체 스레드와 자원
• 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
• 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
• 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

교착상태가 발생한 자원 할당 그래프 모양

• 스레드들이 교착 상태에 있게 되면,
  스레드와 자원들을 연결하는 간선들의 환형 고리가 나타남

03. 교착상태 해결

3.1 코프만 조건(coffman condition)

• 교착상태를 유발할 수 있는 4가지의 필요충분 조건

다음 4가지 조건을 모두 가진 시스템에서는 언제든 교착 상태가 발생할 수 있음

• 상호 배제(Mutual Exclusion)
  각 자원은 한 번에 한 스레드에게만 할당

• 소유하면서 대기(Hold & Wait)
  스레드가 자원을 소유하면서 다른 자원 대기

• 강제 자원 반환 불가(No Preemption)
  스레드에게 할당된 자원을 강제로 빼앗지 못함

• 환형 대기(Circular Wait)
  한 그룹의 스레드들에서 각 스레드가
  다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

→ 이 4가지 조건 중 한가지라도 성립되지 않으면 교착상태에 빠지지 않음

3.2 교착상태 해결 방법

1) 교착상태 예방(prevention)

• 코프만의 4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록
  시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것

2) 교착상태 회피(avoidance)

• 운영체제가 자원을 할당할 때
  교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당

• 시스템을 안전한 상태와 불안전한 상태로 분류하여
  안전한 상태인 경우에만 자원 할당

• 자원을 할당할 때 마다 교착상태 가능성을 검사하므로
  시스템의 성능을 많이 저하시킴

3) 교착상태 감지 및 복구(detection and recovery)

• 운영체제가 교착상태를 감지하는 별도의 프로그램을 백그라운드로 구동시켜
  교착상태에 빠진 스레드 그룹을 발견하면, 교착상태로부터 해제

• 교착상태를 감시하는 작업이 주기적으로 실행되어야 하므로
  시스템에 많은 부담

4) 교착상태 무시(ignore reboot)

• 교착상태가 발생하도록 내버려 두는 방법

• 교착상태는 웬만해서 발생하지 않으며,
  발생했을 때 사용자나 관리자가 대책을 세우면 된다고 생각함

• 교차상태가 발생한다 하더라도, 범용 시스템에서는 큰 문제가 되지 않음

• 현재 대부분의 범용 운영체제에서 사용하고 있음

• 교착상태 무시 알고리즘을 ostrich 알고리즘(타조 알고리즘)이라고 함

TIP 교착상태로 인해 시스템 전체가 중단되는가?

• 교착상태가 발생한다고 해서 시스템 전체가 멈추지 않음
• 많은 스레드들이 교착상태에 있을 때는 시스템을 재시작(reboot)

3.3 교착상태 예방

• 코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함

1. 상호배제(Mutual Exclusion) → 상호배제 없애기

• 2개 이상의 스레드가 동시에 자원을 사용할 수 있도록 허용

근본적으로 적용 불가능한 방법

2. 소유하면서 대기(Hold & Wait) → 기다리지 않게

• 1) 스레드가 필요한 자원을 처음부터 모두 가지게 함
  당장 사용하지 않는 자원을 스레드에게 묶어두기 때문에
  자원 활용률이 떨어짐

• 2) 스레드가 자원을 소유한 상태에서 새로운 자원이 필요하게 되면,
  현재 할당받은 모든 자원을 반환하고,
  필요한 모든 자원을 한꺼번에 모두 요청하는 방법

1, 2 모두 가능하지 않거나, 매우 비효율적
범용 시스템에서는 불가능, 임베디드 시스템에서는 가능

3. 강제 자원 반환 불가(No-Preemption) → 자원의 선점 허용

• 더 높은 순위의 스레드가 자원을 요청하면,
  자원을 가진 낮은 순위의 스레드에게서 강제로 자원을 빼앗음

• 하지만 자원을 강제 반환하게 된 스레드가 자원을 다시 사용하게 될 때,
  이전 상태로 되돌아갈 수 있도록 상태를 관리해야함

간단하지 않으며 오버헤드가 큼

4. 환형 대기(Circular Wait) → 환형 대기 제거

• 모든 자원에 번호를 매기고, 스레드는 반드시 번호 순으로 자원을 할당

3.4 교착상태 회피

• 자원할당 알고리즘을 이용하여 교착상태를 방지하는 기법

• 자원 할당 알고리즘
  자원 할당을 요청받았을 때,
  앞으로 환형 대기가 발생하지 않는다는 확신이 서는 경우에만 자원을 할당

banker's 알고리즘

• Edsger Dijkstra에 의해 개발된 알고리즘

• 자원 할당 전에 미래에 교착 상태가 발생하지 않을 것인지 판단하는 알고리즘

• 안전한 상태
  현재 프로세스들을 어떤 순서로 실행시켰을 때,
  모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있는 상태

• 불안전한 상태
  환형 대기에 빠질 수 있는 상태

• 알고리즘
  1) 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알림
  2) 자원을 할당할 때 마다 안전한 상태인지, 불안전한 상태인지 판단
  3) 이러한 상태는 각 스레드가 필요로 하는 자원의 개수,
  현재 실행 중인 각 스레드가 할당 받은 자원의 개수,
  시스템 내 할당할 수 있는 자원의 개수를 토대로 판단함

• 비현실적
  각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능
  프로세스의 개수도 동적으로 변하기 때문에,
  미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능

사용할 자원의 개수를 미리 알 수 있는
임베디드 시스템이나, 실시간 제어 시스템에서 사용 가능

3.5 교착상태 감지 및 복구

• 교착상태를 감지하는 백그라운드 프로그램을 상시적으로 실행시켜,
  교착상태를 감지하고 해제한다

• 자원 할당 그래프에 환형 대기 모양을 갖는 부분이 있는지 판단

자원 강제 선점(preemption)

• 교착 상태에 빠진 스레드 중 하나를 선택하고,
  스레드가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 스레드에게 할당
  이렇게 함으로써 스레드의 환형 대기 고리를 끊음

롤백(rollback)

• 교착상태가 발생할 것으로 예측되는 스레드들의 상태를 주기적으로 저장
• 교착상태가 발생하면 가장 최근에 저장해둔 상태로 복구
• 다시 시작하면 스케줄링 등 여러 요인에 의해 자원 할당 순서가 달라짐

롤백을 위한 주기적인 상태 저장으로 인해, 시스템의 시간과 저장 공간을 소모하여 시스템 성능을 저하시킴

스레드 강제 종료(kill process)

• 교착 상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법
• 사용자나 시스템 관리자가 사용하는 방법

3.6 교착상태 무시: 타조(ostrich) 알고리즘

ostrich: 현실도피주의자

교착상태를 해결할 필요가 있을까?

• 컴퓨터 시스템에서 교착상태에 대한 통계치 없음

교착상태는 반드시 발생함

• 하지만, 발생 가능성이 극히 적고, 피하기 위한 비용이 많이 들어감

최적의 알고리즘: 타조 알고리즘

• put your head in the sand 접근법
  교착상태는 발생하지 않을 것이라 생각하고 아무 대책을 취하지 않는 접근법

• Unix(리눅스)와 윈도우 등 거의 모든 운영체제에서 사용
  의심 가는 스레드를 종료시키거나 시스템 재시작(reboot)
  관련 데이터를 잃어버릴 수 있으나, 비용 면에서 더 나은 방법임

• 핵 시스템, 비행기, 미사일 등 시스템 재시작이 파국을 초래할 수 있는
  hard-real time 시스템이나, 환자 감시 시스템 등에는 적합하지 않음

"Not everything worth doing is worth doing well"