1 교착상태 문제 제기
1.1 무한 대기와 교착상태
서로 무한정 대기하는 상태를 교착상태(deadlock)라고 부른다.
1.2 식사하는 철학자 문제(Dining Philosophers Problem)
문제의 개요
- 5명의 철학자가 원탁에서 식사. 식사 시간은 서로 다를 수 있음
- 자리마다 스파게티 그릇이 하나 있고 5개의 포크가 그릇 사이에 있음
- 철학자는 다른 철학자와 대화할 수 없음
- 식사를 위해서는 양 옆의 포크를 함께 들어야 함
- 왼쪽 포크를 먼저 든 다음 오른쪽 포크를 드는 순서이며 포크가 사용 중이면 대기해야함, 왼쪽 포크를 옆 철학자가 사용하고 있다면 오른쪽 포크도 잡을 수 없음
철학자가 식사하는 모든 경우 분석
- 철학자들의 교착상태 원인 - 환형 요청/대기(circular request/wait)
- 철학자들의 교착상태 해결 - 환형 요청/대기가 생기지 않게 규칙 변경
1.3 식사하는 철학자와 컴퓨터 시스템
‘식사하는 철학자 문제’는 컴퓨터 시스템에서 발생하는 교착상태의 발생 요인을 설명하기 위해 다음과 같이 비유적으로 만든 사례이다.
- 철학자 - 프로세스
- 포크 - 자원
- 스파게티 - 프로세스가 처리할 작업
2 교착상태
오늘날 실행 단위는 스레드이기 때문에 스레드를 대상으로 설명한다.
2.1 교착상태 정의
스레드 사이에서 발생하는 공유 자원에 대한 동기화 문제 중의 하나 교착상태는 자원을 소유한 스레드들 사이에서 각 스레드는 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상이다.
전형적인 멀티스레드 교착상태 사례
교착상태는 단인 CPU든 다중 CPU든 가리지 않고, 락이나 자원에 대한 멀티스레드의 경쟁이 있는 한 발생할 수 있다.
커널 코드 내에서는 거의 발생하지 않고, 사용자 응용프로그램 내에서 주로 발생한다.
2.2 컴퓨터 시스템에 잠재된 교착상태 유발 요인
컴퓨터 시스템이 실행되는 방식에 교착상태를 유발시킬 수 있는 여러 요인들이 근본적으로 잠재되어 있다.
- 자원 - 자원은 교착상태의 발생지이다.
- 소프트웨어/데이터 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일락 등
- 하드웨어 자원 - 프린터, 메모리, 프로세서 등
- 자원과 스레드 - 한 스레드가 동시에 여러 개의 자원을 필요로 하는 경우가 있다.
- 자원과 운영체제 - 운영체제는 한 번에 하나씩 자원을 할당한다.
- 자원 비선점 - 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺐지 못한다.
2.3 교착상태 모델링
자원 할당 그래프
컴퓨터 시스템에서 자원 할당 그래프(RAG, resource allocation graph)를 이용하여 교착상태를 표현하고 이 그래프를 기반으로 교착상태 예방, 회피, 감지 등이 운용된다. RAG는 자원과 스레드들의 상태를 나타내는 방향성 그래프(graph)이다. 구성요소
- 꼭짓점 - 스레드는 원으로, 자원은 사각형으로 나타낸다.
- 간선 - 간선은 할당 간선(allocation edge)과 요청 간선(request edge)의 두 종류로 나뉜다. 할당 간선은 자원에서 스레드로 향하는 화살표로서 스레드가 자원을 소유하고 있음을 나타내며, 요청 간선은 스레드에서 자원으로 향하는 화살표로서 스레드가 자원을 기다리고 있음을 나타낸다. 자원 할당 그래프를 통해 표현되는 정보는 다음과 같다.
- 컴퓨터 시스템에 실행 중인 전체 스레드와 자원
- 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
- 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
- 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수
교착상태가 발생한 자원 할당 그래프 모양
간선들의 환형 고리가 나타남
2.4 교착상태에 빠진 응용프로그램 사례
3 교착상태 해결
3.1 코프만 조건(Coffman condition)
- 상호배재(Mutual Exclusion) - 자원을 한 번에 한 스레드에게만 할당
- 소유하면서 대기(Hold & Wait) - 스레드가 자원을 소유하면서 다른 자원대기
- 강제 자원 반환 불가(No Preemption) - 스레드에게 할당된 자원을 강제로 빼앗지 못함
- 환형 대기(Circular Wait) - 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유한 자원을 요청하여 환형 고리 생성 코프만은 컴퓨터 시스템에서 교착상태를 유발할 수 있는 4가지의 필요충분조건을 찾아내어 증명하였다. 위 4가지 조건을 모두 가진 컴퓨터 시스템에서는 언제든 교착상태가 발생할 수 있다는 것이다.
3.2 교착상태 해결 방법
교착상태 예방(prevention)
코프만의 4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것이다.
교착상태 회피(avoidance)
운영체제가 자원을 할당할 때마다 교착상태 가능성을 검사하여 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당하는 방법이다. (시스템의 성능을 많이 저하시킴)
교착상태 감지 및 복구(detection and recovery)
운영체제가 교착상태를 감지하는 별도의 프로그램을 백그라운드로 구동시켜 교착상태에 빠진 스레드 그룹을 발견하면 교착상태로부터 해체하는 방법이다. (교착상태를 감지하는 작업이 주기적으로 실행되므로 시스템에 많은 부담)
교착상태 무시(ignore and reboot)
아무런 대비책 없이 교착상태가 발생하도록 내버려 두는 방법이다
교착상태로 인해 시스템 전체가 중단되는가? 교착상태가 발생한다고 컴퓨터 시스템 전체가 멈추는 것이 아니라 몇몇 스레드들 사이에서 발생하므로 문제가 되는 스레드만 제거하면 교착상태는 사라진다.
3.3 교착상태 예방
- 상호배제(Mutual Exclusion) → 상호배제 없애기
- 소유하면서 대기(Hold & Wait) → 기다리지 않게
- 운영체제는 스레드 실행 전에 스레드가 필요한 자원을 모두 알고, 스레드 실행 시작과 함께 모든 자원을 할당해주어 실행 중에 자원을 요청하여 대기하는 일이 없도록 하는 것
- 스레드가 자원을 소유한 상태에서 새로운 자원이 필요하게 되면, 현재 할당받은 모든 자원을 반환하고 필요한 모든 자원을 한꺼번에 요청하는 방법 모 아니면 도 전략(all or nothing)
- 자원 강제 반환 불가(No Preemption) → 자원의 선점 허용
- 환형 대기(Circular Wait) → 환형 대기 제거
모든 자원에 번호를 매기고, 스레드에게 반드시 번호 순으로 자원을 할당받게 하는 방법
3.4 교착상태 회피
자원할당 알고리즘을 이용하여 교착상태를 방지하는 방법 대표적인 알고리즘으로 banker’s 알고리즘(은행원 알고리즘)이 있다.
3.5 교착상태 감지 및 복구
교착상태를 감지하는 백그라운드 프로그램을 상시적으로 실행시켜 교착상태를 감지하고 교착상태를 해제하는 방법 교착상태의 감지는 RAG에 환형 대기 모양을 가지는 부분이 있는지 판단 교착상태 해제 방법에는 다음과 같은 것들이 있다.
- 자원 강제 선점(preemption) 교착상태에 빠진 스레드 중 하나를 선택하고 이 스레드가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 다른 스레드에게 할당하는 방법
- 롤백(rollback) 교착상태가 발생할 것으로 예측되는 스레드들에 대해 그들의 상태를 주기적으로 저장해두었다가, 교착상태가 발생하면 가장 최근에 저장해둔 상태로 복구시켜 가장 최근에 실행하던 상태로 돌아가게 한다. 롤백 이후 스레드들이 다시 시작하면, 스케줄링 등 여러 요인에 의해 자원이 할당되는 순서가 다르게 되어 교착상태가 발생되지 않게된다.
- 스레드 강제 종료(kill process) 교착상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법
3.6 교착상태 무시: 타조(ostrich) 알고리즘
교착상태를 해결할 필요가 있을까?
교착상태가 발생할 가능성이 극히 적은 반면 교착상태를 피하기 위한 비용이 많이 들어간다면, 굳이 많은 시간과 비용을 소모하면서까지 교착상태를 해결할 필요가 있을까? 현재 유닉스, 리눅스, Windows 등 대부분의 운영체제에서는 교착상태에 대해 아무 대책을 세우지 않는 교착상태 무시 전략 이른바 타조 알고리즘을 사용한다.
최고의 알고리즘: 타조 알고리즘
교착상태에 대한 아무런 대책 없이 컴퓨터 시스템을 가동시키고, 교착상태가 발생하면 시스템을 재시작 하거나 특정 스레드를 강제 종료하는 쉬운 방법으로, 교착상태를 해결한다. 이 과정에서 데이터 손실이 발생할 수 있지만, 비용 면에서 더 나은 방법이다. 실시간 시스템에는 부적절하다. 보통 교착상태는 커널 코드보다는 멀티스레드 응용프로그램 내에서 스레드들 사이에서 주로 발생
+ Alpha
- 교착 상태는 왜 발생하는가?
- 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문이다.
- 캡슐화(encapsulation)의 성질 때문이다.
- 코딩을 개판으로 했기 때문이다
- 구글의 맵리듀스(MapReduce)
- 자원할당그래프는 어떤방식으로 가지고 있을까?
- 저장을 한다면 어디에 하는지?
- 분산처리 시스템에서 교착상태 처리는 어케함
Ref.
황기태, “명품 운영체제”, (주)생튼출판사(2021)