교착상태 (명품_운영체제 Ch 07)

교착상태(Deadlock)

자원을 소유한 스레드들 사이에서 각 스레드가 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상

교착상태는 대체로 사용자 프로그램 내에서 발생한다

• 대부분 잘못된 멀티스레드 코딩에서 발생함
• 커널은 교착상태를 교려하여 매우 정교하게 작성되어 있어 거의 발생하지 않는다
• 교착상태를 막기 위해선 많은 시간과 공간 비용이 발생하기 때문에 교착상태를 막도록 운영되는 컴퓨터 시스템은 거의 없다

교착상태 유발 요인

• 스레드가 동시에 여러개의 자원을 필요로 하는 경우
  • 스레드 실행동안 한 개의 자원만 필요한 경우 교착상태가 발생하지 않음
• 운영체제는 한 번에 하나씩 자원을 할당한다
  • 한 번에 여러개의 자원을 할당할 수 있다면 교착상태가 발생하지 않을수도 있음
• 할당 자원을 강제로 빼앗지 못한다
  • 대부분은 스레드가 할당 받은 자원을 운영체제가 강제로 빼앗지 못함
  • 빼앗아서 기다리는 스레드에게 줄 수 있다면 교착상태는 발생하지 않음

식사하는 철학자

교착상태를 설명하는 대표적인 문제이다 아래 사진의 조건

• 5개의 자리, 5명의 철학자와 5개의 스파게티, 5개의 포크가 있다
• 스파게티는 무한으로 보충되며, 철학자는 가끔씩 식사를 하러 자리에 앉는다
• 식사를 하기 위해선 반드시 자신의 왼쪽 포크를 집어 스파게티 안에 넣은 후, 오른쪽 포크를 사용하여 먹어야 한다
• 포크는 한 개에 한 명만 사용할 수 있으며, 다른 철학자가 사용중이라면 사용이 끝날 때까지 기다려야 한다
• 만약 왼쪽 포크를 들었는데 오른쪽 포크가 없다면 왼쪽 포크를 든 상태로 기다려야 한다
• 다른 철학자가 들고 있는 포크를 빼앗을 수 없다

위 사진의 조건에 나와 있는 단어들을 컴퓨터 시스템 입장에서 해석해보자

• 철학자 - 프로세스(스레드)
• 포크 - 자원
• 스파게티 - 프로세스가 처리할 작업
• 식사 - 프로세스 실행
• 한 개에 한 명 - 상호배제
• 빼앗을 수 없음 - 비선점
• 왼쪽 포크를 든 상태로 기다림 - 점유 및 대기
• 사용이 끝날 때까지 기다림 - 환형대기

해당 문제에서는 한 명 이상의 철학자가 포크를 드는 순서를 바꾸면 환형대기가 깨지면서 교착상태에 빠지지 않는다

교착상태 모델링

자원 할당 그래프

• 컴퓨터 시스템에서 교착상태를 표현하고 이 그래프를 기반으로 예방, 회피 감지 등이 운용된다
• 자원과 스레드들의 상태를 나타내는 방향성 그래프이다
• 구성요소
• 꼭짓점(vertex)
  • 스레드는 원으로, 자원은 사각형으로 나타낸다
• 간선(edge)
  • 할당 간선(allocation edge)
    • 자원에서 스레드로 향하는 화살표, 스레드가 자원을 소유하고 있음을 나타냄
  • 요청 간선(request edge)
    • 스레드에서 자원으로 향하는 화살표, 스레드가 자원을 요청하고 있음을 나타냄
• 표현 정보
  • 컴퓨터 시스템에 실행중인 전체 스레드와 자원
  • 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
  • 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
  • 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

(d) 모양이 교착상태 모양임

스레드들이 교착상태에 빠지면 해당 그래프의 모양에서 간선들의 환형 고리가 나타난다

자원을 소유하는 스레드가 다른 스레드가 소유하는 자원을 요청하였는데 그 스레드 마저도 다른 스레드의 자원을 요청하고 대기하는 상태가 환형모양으로 연결되어야 교착상태에 빠졌다고 한다

• 그러므로 (b) 그래프의 T4, T5는 교착상태에 걸리지 않았다

교착상태 해결

코프만 조건(Coffman condition)

• 교착상태를 유발하는 4가지의 필요충분조건으로 하나라도 만족하지 않으면 교착상태가 발생하지 않는다
• 상호배제(Mutual Exclusion)
  • 자원을 한 번에 한 스레드에게만 할당
• 소유하면서 대기(Hold & Wait)
  • 스레드가 자원을 소유하면서 다른 자원 대기
• 강제 자원 반환 불가-비선점(No Preemption)
  • 스레드에게 할당된 자원을 강제로 빼앗지 못함
• 환형 대기(Circular Wait)
  • 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 사유한 자원을 요청하는 환형 고리 형성

현재까지 제안된 교착상태 해결 방법

• 교착상태 예방(prevention)
  • 코프만 조건 중 하나 이상이 아예 성립되지 못하도록 시스템을 설계하는 방법
• 교착상태 회피(avoidance)
  • 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당시키는 방법
  • 자원 할당마다 교착상태 가능성 검사가 필요하므로 성능이 저하된다
• 교착상태 감지 및 복구(detection and recovery)
  • 운영체제가 교착상태를 감지하도록 별도의 백그라운드 프로그램을 통해 교착상태에 빠진 스레드 그룹을 탐색하고 해제하는 방법
  • 교착상태 감지 작업이 주기적으로 실행되어야 하므로 시스템에 부담이 됨
• 교착상태 무시(ignore and reboot)
  • 교착상태가 발생하도록 내버려 두는 방법
  • 교착상태는 웬만해선 발생하지 않으며, 만약 이상이 발생하면 의심되는 스레드를 종료하든 부팅하든 그 때 대책을 세우면 된다는 방식

교착상태 예방

코프만의 4가지 조건 중 한 가지 이상을 성립하지 못하게 한다

1. 상호배제 -> 상호배제 없애기
   • 2개 이상의 스레드가 동시에 자원을 사용할 수 있도록 허용한다
   • 이로 인해 발생하는 공유자원 훼손의 문제가 심각하기 때문에 불가능한 방법이다
2. 소유하면서 대기 -> 기다리지 않게 하기
   • 처음부터 스레드가 필요한 자원을 모두 가지게 하는 것으로 두 가지 방법이 있다
     1. 스레드의 실행 시작과 함께 필요한 모든 자원을 할당한다
     • 그렇게 할 수 없다면 실행 자체를 대기시킨다 2. 자원을 소유한 상태로 새로운 자원을 요청하게 되면, 현재 소유한 자원을 모두 반환하고 반환한 자원을 포함한 모든 필요 자원을 한 번에 요청한다
     • 자원을 소유하면서 대기하는 것이 아니기 때문에 교착상태에 빠지지 않는다
     • 하이 리스크 하이 리턴
3. 자원 강제 반환 불가(비선점) -> 자원의 선점 허용
   • 더 높은 스레드가 자원을 요청하면 낮은 스레드에게서 강제로 자원을 빼앗는다
   • 자원을 빼앗긴 스레드를 다시 실행할 때, 이전의 자원 소유 상태로 돌아가기 위한 상태 관리가 필요하여 어려운 방법이다
4. 환형 대기 -> 환형 대기 제거
   • 모든 자원에 번호를 매기고, 스레드에게 반드시 번호 순으로 자원을 할당받게 한다

ex) T1~T4는 각각 (R1, R2), (R2, R3), (R3, R4), (R4, R1)의 자원을 필요로 한다

(a)는 자원의 순서가 없어 할당 가능한 것부터 받게되고 나머지는 요청 & 대기하게 되어 교착상태에 빠진다 (b)는 자원에 번호를 매겨(R1~R4가 1~4의 순서를 가짐) 스레드가 반드시 자원의 번호 순대로 할당받도록 한다 T4는 (R4, R1)이 필요하고 반드시 R1부터 할당받아야 하지만 T1이 소유하고 있으므로 요청 & 대기 상태가 되고 R4 자원은 T3가 할당받으며 교착상태가 아니게 된다

교착상태 회피

교착 상태가 발생하지 않을 것이란 확신이 있을 때만 자원을 할당시켜주는 방법

대표적인 알고리즘으로 banker’s 알고리즘(은행원 알고리즘)이 있다

은행원 알고리즘

• 1965년 Edsgar dijstra에 의해 개발
• 시스템을 안전한 상태와 불안전한 상태로 나누고, 자원을 할당하였을 때 안전한 상태로 갈 때만 자원을 할당한다
• 여러 정보들을 통해 현재 요청된 자원을 할당해도 안전한지 미리 판단한다
  • 각 스레드가 필요로 하는 자원의 개수, 현재 실행중인 각 스레드가 할당 받은 자원의 개수, 시스템 내 할당 가능한 자원의 개수 등
• 스레드 실행 전에 필요 자원 정보를 아는 것은 사실상 불가능하여 비현실적인 알고리즘이다

교착상태 감지 및 복구

교착상태를 감지하는 백그라운드 프로그램을 상시 실행하여 감지 및 복구하는 방법

자원 할당 그래프에서 환형 대기 모양을 가지는 부분을 교착상태로 감지한다

복구(해제) 방법

• 자원 강제 선점(preemption)
  • 교착상태에 빠진 스레드 중 하나가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 스레드에게 할당하여 환형 대기 고리를 끊는다
• 롤백(rollback)
  • 교착상태가 예상되는 스레드들에 대해 주기적으로 상태를 저장해두었다가, 교착상태 발생 시 최근에 저장해둔 상태로 복구킨다
  • 스케줄링 등 여러 요인에 의해 자원 할당 순서가 변경되어 교착상태가 발생하지 않는다
  • 주기적인 상태 저장으로 인한 시간, 공간 비용으로 시스템 성능이 저하된다
• 스레드 강제 종료(kill process)
  • 교착상태에 빠진 스레드 중 하나를 강제 종료시킨다

감지와 복구 모두 시스템에 부담을 주는 방법들이다

교착상태 무시

대책을 세우지 않고 즉각 대응하는 방법

대부분의 교착상태는 멀티스레드 응용프로그램 내에서 발생하므로, 사용자나 개발자가 이상을 발견하기 쉽기 때문에 많은 비용을 들여 미리 대비할 필요가 없다

타조 알고리즘(ostrich algorithm)

• 교착상태에 대한 대책 없이 시스템을 가동시키고, 교착상태가 발생하면 시스템을 재시작(reboot)하거나 특정 스레드를 강제 종료하여 해결한다
• 데이터 손실이 발생할 수 있지만 미리 대비하는 비용에 비해서는 더 나은 방법이다
• 스레드 강제 종료나 시스템 재시작으로 큰 문제가 생길 수 있는 시스템에는 부적절하다(병원, 비행기, 미사일 등등)
• 대부분의 운영체제에서 사용한다(Unix, Linux, Windows)