교착 상태(Dead Lock)

교착상태(Dead Lock)란

자원을 소유한 채 상대방이 소유한 자원을 기다리면서 무한정 대기하는 상태

교착 상태, 상대방이 기다리기를 무한정 기다리는 상태

 

 

 

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

1965년 다익스트에 의해 처음으로 문제화되었으며 병렬처리에서의 동기화 이슈와 해결 방법을 설명하고자 학생들에게 낸 시험 문제

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

 

이런 상황일때 식사하는데에 어떤 문제가 있을까?

• 5명이 동시에 왼쪽 포크를 들고 이후 오른쪽 포크를 들려고 하면 모두 상대의 포크를 기다리면서 식사를 할 수 없는 교착 상태(Dead Lock) 발생

 

해결 방안

• 원형 요청의 고리를 끊기 위해, 5명 중 마지막 사람만 포크를 잡는 순서를 오른쪽, 왼쪽 순으로(반대로) 진행한다.
  - 이 원형 고리는 교착상태의 원인이며, 환형 요청 / 대기(Circular Wait)이라 부름

 

컴퓨터 시스템에서의 교착 상태와 비유

철학자 = 스레드

포크 = 자원

스파게티 = 스레드가 처리할 작업

 

 

 

 

 

 

교착상태(Dead Lock)

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

- 교착상태 문제는 다익스트라의 은행원 알고리즘 연구에서 처음 제기됨

 

교착 상태 발생 위치

• 사용자가 작성한 응용프로그램
  - 정교하지 못하게 코딩한 사용자 작성 응용프로그램에서 주로 발생함
• 커널 내에서
  - 커널 내에서도 발생할 수 있지만, 전문가들이 정교하게 작성하므로 거의 발생하지 않음
• 교착 상태를 막도록 운영하는 컴퓨터 시스템은 사실상 없음
  - 막는데 많은 시간과 공간의 비용이 발생
  - 사실상 대부분의 교착 상태는 사용자가 작성한 응용프로그램에서 발생하므로, 교착상태가 발생한 것 같다면 해당 응용프로그램을 종료시키거나 시스템 재시작을 시도

 

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

• 자원
  - 교착 상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
  - 컴퓨터 시스템에는 다양한 자원이 존재
  - 소프트웨어적 자원 : 뮤텍스, 스핀락, 세마포어, 파일, DB, 파일 락
  - 하드웨어적 자원 : 프린터, 메모리, 프로세서 등
• 자원과 스레드
  - 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인
• 자원과 운영체제
  - 운영체제가 한 번에 한 개씩의 자원만 할당하는 운영체제 정책이 요인
  - 스레드가 필요한 자원을 한 번에 모두 요청하도록 하면 교착상태가 발생하지 않음
• 자원 비선점
  - 할당된 자원을 스레드가 내놓기 전에 강제로 뺏어오지 못하는 정책이 요인
  - 스레드가 필요할 때 자원을 강제로 뺏을 수 있다면 교착상태가 발생하지 않음

 

 

 

 

교착 상태 모델링

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

• 그래프의 요소
  - 꼭지점(Vertex) : 스레드(원형), 자원(사각형)
  - 간선(edge) : 소유 / 요청 관계, 할당 간선과 요청 간선(방향이 지정되므로 Directed Graph)
  - 할당 간선 : 자원에서 스레드로 가는 간선, 스레드로의 자원 할당 표시
  - 요청 간선 : 스레드에서 자원으로 가는 간선, 스레드의 자원 요청 표시

Resource Allocation Graph 예제로 P3 스레드와는 상관 없이 나머지 자원과 스레드들에서 환형 요청의 고리가 보이므로 교착상태가 발생할 수 있는 시스템임

 

 

 

 

코프만 조건

교착 상태가 발생하기 위한 4가지 필요충분 조건으로 하위 4가지 상황이 전부 허용되는 시스템은 언제든 교착상태가 발생할 수 있음

• 상호 배제(Mutual Exclusion)
  - 각 자원은 한 번에 하나의 스레드에게만 할당
• 소유하면서 대기(Hold & Wait)
  - 스레드가 한 자원을 소유하면서 다른 자원을 기다리기
• 강제 자원 반환 불가(No Preemption)
  - 스레드에게 할당된 자원을 강제로 빼앗지 못함
• 환형 대기 (Circular Wait)
  - 한 그룹의 스레드들에 대해, 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

-> 이중 하나라도 성립되지 않으면, 교착상태는 발생하지 않음

 

 

 

 

교착상태 해결 방법

• 교착상태 예방(prevention)
  - 교착상태 발생 여지를 미리 차단하여 예방
  - 교착상태에 빠지는 4가지 코프만 조건 중 하나 이상이 성립되지 못하도록 시스템 구성
• 교착상태 회피(avoidance)
  - 미래에 교착상태로 가지 않도록 미리 회피
  - 자원 할당 시 마다 미래의 교착상태 가능성을 검사하여 교착상태가 발생하지 않을 것이라 확신가능할 경우에만 자원을 할당하는 방식
  - 안전상태, 불안전상태로 시스템을 분류하고 안전상태일 경우에만 자원 할당
  - 대표적으로 Banker's Algorithm이 있으며, 자원 할당 시 마다 교착 상태 가능성을 검사하므로 시스템 성능이 저하됨
• 교착상태 감지 및 복구(Detection and Recovery)
  - 교착 상태를 감지하는 프로그램을 백그라운드에서 구동, 감지하면 교착상태를 해제
  - 늘 백그라운드에 실행되어야하므로 시스템에 부담
• 교착상태 무시
  - 교착 상태는 없다고 단정, 아무런 대비책을 두지 않음
  - 사용자, 관리자가 이상을 느끼면 알아서 재실행, 재부팅을 할 것이라고 믿는 방법
  - 현재 리눅스, 윈도우 등 대부분 운영체제에서 사용하는 일반적인 방법
  - 대표적으로 Ostrich 알고리즘
  - 교착상태 예방, 감지, 회피 등에는 많은 시간과 공간이 필요하여 시스템 성능을 저하시키기 때문

 

 

교착상태 예방(prevention)

• 상호 배제(Mutual Exclusion)조건 없애기
  - 동시에 2개 이상의 스레드가 자원을 활용할 수 있게 됨
  -> 자원충돌이 발생하므로 컴퓨터 시스템에서 근본적으로 적용이 불가능
• 소유하면서 대기(Hold & Wait)조건 없애기(기다리지 않게)
  - 방법 1 : 스레드 실행 전 필요한 자원을 파악하고 실행 시 한번에 할당
  -> 당장 사용하지 않는 자원도 묶이므로 자원 활용률이 저하되며 다른 스레드들이 자원을 할당받지 못함
  - 방법 2 : 스레드가 새로운 자원을 요청할 때 현재 할당받은 자원을 전부 반환하고 한꺼번에 요청하여 할당받게 하기
  -> 방법 1, 2 모두 가능하지 않거나 매우 비효율적
• 강제 자원 반환 불가(no preemption) 조건 없애기(선점 허용)
  - 강제로 반환한 스레드가 다시 해당 자원을 사용하게 될 때, 반환 직전의 상태로 되돌아갈 수 있도록 자원 상태 관리가 필요함
  -> 간단하지 않으며, 오버헤드가 매우 커서 사실상 불가능함
• 환형 대기(Circular wait)조건 없애기(환형 대기 제거)
  - 모든 자원에 번호를 매기고 번호순으로 자원 할당

 

환형 대기(Circular Wait) 제거

• 스레드가 번호 순으로 자원을 할당 받음
  - 환형 대기가 발생하는 해당 상황에서,
  T1 -> 자원 1, 2 요청
  T2 -> 자원 2, 3 요청
  T3 -> 자원 3, 4 요청
  T4 -> 자원 4, 1 요청
  -> 자원의 순서대로 할당을 받는다면, T4는 자원 번호 순서대로 할당되므로 이미 T1에 할당된 자원 1을 먼저 요청하므로 자원4를 요청하지 못해 환형 대기가 끊어짐

 

 

 

 

교착상태 회피(avoidance)

자원 할당 시, 미래에 교착 상태가 발생할 것으로 판단되면 자원을 할당하지 않는 방법

• 은행원 알고리즘(Banker's Algorithm)
  - 다익스트라에 의해 개발된 알고리즘으로 자원 할당 전에 교착상태가 미래에 발생하지 않을 것인지 미리 판단하는 알고리즘
  - 어떤 프로세스를 실행했을 때, 다른 모든 프로세스가 해당 프로세스와 자원 요청에 충돌이 발생하지 않고 실행할 수 있다면 이 프로세스는 안전한 상태
  - 이와 달리 환형 대기에 빠질 수 있다면 불안전한 상태
• 알고리즘 로직
  - 각 프로세스가 실행 전 필요한 전체 자원 수를 운영체제에 알림
  - 자원 할당 시 마다 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전할때만 할당
  - 각종 자원들의 정보들을 바탕으로 현재 자원을 할당해도 안전한지 판단
• 비현실적
  - 각 프로세스가 실행전에 필요한 자원의 개수를 아는것은 불가능함
  - 프로세스 개수도 동적으로 변하므로, 모든 프로세스들에 대하여 자원 충돌 여부를 검사하는 것은 무의미함

 

 

 

 

교착상태 감지 및 복구(Detection and Recovery)

교착 상태를 감지하는 프로그램을 상주시켜 교착 상태를 감지하고, 해제한다

 

교착상태 감지 시 복구 방법

• 자원 강제 선점(preemption)
  - 교착 상태에 빠진 스레드의 자원중 하나를 강제로 빼앗아 다른 스레드에 할당
  -> 강제로 자원을 뺏긴 스레드의 상태를 보증할 수 없으므로 사실상 불가능
• 롤백(Rollback)
  - 교착상태가 발생할 것으로 예측되는 스레드들의 상태를 주기적으로 저장
  - 교착상태가 발생하면 마지막 저장 상태로 돌아가도록하고, 해당 스레드를 재시작하면 스케줄링 등 여러 요인에 의해 자원 할당 순서가 달라지게 함
  -> 메모리 공간에 대한 오버헤드가 크기때문에 사실상 잘 사용하지 않음
• 스레드 강제 종료(Kill Process)
  - 교착 상태에 빠진 스레드 중 하나를 선택하여 강제 종료
  -> 가장 간단하면서도 효과적이나, 종료된 스레드를 보증할 수 없으므로 사실상 무의미

 

 

 

 

 

교착상태 무시

• 교착상태는 반드시발생하나, 발생 가능성이 극히적어 통계치가 없을 정도이며 이를 회피하기위해 많은 비용까지 소요되므로 굳이 교착상태를 해결할 필요성이 사실상 없음
• 타조(Ostrich) 알고리즘
  - Put your head in the sand 접근법을 사용
  - 타조가 머리를 모래 속에 박고 자신이 보이지 않은 체 아웅하는 것
  - 이와 같이 '교착 상태는 발생하지 않을 것이야' 라고 아무 대책도 취하지 않고 방치하는 접근법
  - 현재 대부분의 운영체제에서 사용되며 사용자가 직접 의심가는 스레드를 종료시키거나 재부팅을 하는 방법으로 해결하게 함(이는 운영체제 기준에서는 큰 손실이 아님)
  - 거의 발생하지 않는 상황이지만 해결하기 위한 비용이 높으므로 이 방식을 채택
• 주의사항
  - 핵 관리 시스템, 비행기, 탄도 미사일 등 시스템 재시작이 파국을 초래할 Hard RT 시스템이나 실수가 용납되지 않는 환자 감시 시스템 등에서는 적합하지 않음