교착 상태 (deadlock)

(참고자료: 최린교수님 운영체제 강의)

 

교착상태(deadlock, 데드락)는 둘 이상의 프로세스가 자원을 할당받지 못해 무한히 대기하는 상태를 말합니다.

멀티프로세싱, 병렬 컴퓨팅, 분산 시스템 등에서 중요한 과제입니다.

 

현실에서 쉽게 예시를 들 수 있는게 교차로입니다. 교차로 꼬리물기를 하면 현실에서 교착상태가 발생합니다. 그래서 꼬리물기 하지 말라고 단속하는거죠.

 

 

교착상태의 필요조건

• 상호 배제 (Mutual Exclusion)
  • 여러 프로세스가 한 자원을 동시에 사용할 수 없음
• 보유 및 대기 (Hold and Wait)
  • 자원을 할당받고 다른 자원을 기다림
• 비선점 (No preemption)
  • 다른 프로세스의 자원을 뺏어올 수 없음
• 환형 대기 (Circular wait)
  • 대기상태가 사이클이 되어 자기 자신으로 돌아옴

위 네가지 조건이 전부 만족되면 교착상태가 일어납니다.

 

 

교착상태 처리 방법

• 무시한다 (Ignoring)
  • 아래 방법들은 다 오버헤드가 있기 때문에 교착상태 발생 확률이 매우 낮으면 무시하는 방법도 있음
    --> 나중에 재부팅 등을 해야 함
  • = Ostrich algorithm
• 예방 (Prevention)
  • 구조적으로 교착상태가 일어나지 않도록 강제
  • 보수적(Conservative)인 방법
• 회피 (Avoidance)
  • allocation을 요청했을 때, deadlock이 발생할 수 있는 경우 거부
  • 미래 request 정보들까지 알고 있어야 함
  • 두 가지 접근 방법이 있다
    • 프로세스 시작 거부 (Process Initial Denial)
    • 리소스 할당 거부 (Resource allocation Denial, =banker's algorithm)
• 탐지, 복구 (Detection & Recovery)
  • 교착상태를 따로 막지 않고, 대신 주기적으로 교착상태 발생 여부를 체크함
  • 교착상태 발생 시 rollback, preemption을 해야 함

 

 

교착상태 예방 (prevention)

교착상태 발생을 예방하려면 교착상태의 필요조건 중 하나가 일어나지 않도록 강제하면 됩니다

• 상호배제를 없애기
  • 이건 불가능하다고 봐야 한다
• 보유 및 대기를 없애기
  • ex. Request all at once: 자원을 전부 한번에 받도록 만듦
• 비선점 조건을 없애기
  • 구현방식은 두가지
  • 1. resource allocation에 실패하면 해당 프로세스가 보유중인 resource를 전부 release
  • 2. 다른 프로세스가 들고 있는 resource에 allocation을 요청하면 뺏어서 준다
• 환형 대기를 없애기
  • ex) Resource Ordering: 자원의 순서를 정의

각 방법들은 저마다 장단점이 있고 오버헤드가 있습니다.

 

 

교착상태 회피 (Avoidance)

작성예정 (공부중)

 

 

예시) Dining Philosophers Problem

Illustration from Wikipedia

식사하는 철학자 문제는 유명한 교착상태 예제인데요, E. W. 다익스트라가 1965년 학생들 시험에 냈던 예제라고 합니다.

5명의 철학자가 원탁에 앉아있고, 각자의 앞에는 스파게티가 놓여 있습니다. 스파게티 양쪽에는 포크(또는 젓가락 한짝)가 놓여져 있습니다.

철학자는 생각하거나, 먹거나 둘 중 하나의 행동만 합니다. 스파게티를 먹을 때는 양쪽에 놓인 포크 두개를 사용해야만 먹을 수 있습니다. 즉 포크를 옆사람과 공유하게 됩니다 (좀 드럽습니다)

 

이때 교착상태가 언제 생기냐면 모든 철학자가 스파게티를 먹으려고 왼쪽 포크를 집은 다음, 오른쪽 포크를 집으려고 보면 모든 포크가 사용중이니 대기하게 됩니다. 스파게티를 먹을 수 있는 철학자가 없으니 교착상태가 무한히 지속됩니다.

위에서 설명한 교착상태 처리 방법을 이 예시에 적용해보겠습니다

• 교착상태 예방 (prevention)
  • 보유 및 대기를 없애기
    • 양쪽 포크를 한번에 잡을 수 있을 때만 잡게 만듦 (request all at once)
  • 비 선점을 없애기
    • 1. 포크 한 쪽을 집은 뒤 다른 한 쪽을 잡는데 실패하면 집었던 포크를 내려놓는다
    • 2. 포크를 집을 때 옆 사람이 포크를 쓰고 있든 말든 그냥 뺏어온다
  • 환형 대기를 없애기
    • 포크에 번호를 1, 2, 3, 4, 5 이런식으로 붙이고 작은 포크 먼저 집고 큰 포크를 그 다음에 집도록 만들면 자연히 환형 대기가 없어짐
• 교착상태 회피 (avoidance)
  • (작성예정)
• 교착상태 탐지 (detection)
  • 웨이터를 한명 배치해서 5초에 한번씩 교착상태가 발생했는지 체크하게 한다. 교착상태가 생겼으면 교착상태 생긴 포크를 양쪽 사람 중 한 명에게 적당히 배분하게 한다.

 

 

라이브락(Livelock)

A situation where two or more processes continuously change their states without making progress.

뭔가 state가 바뀌고 진행은 되는 것 같은데 궁극적으로 진행이 되지 않는 상태를 말합니다.

최린 교수님 曰 "연구실에 학생한테 뭘 시켰는데 뭔가 열심힌 하긴 하는데 progress는 없는 때를 livelock이라고 한다" (링크)

이 사진으로도 설명 가능할 듯 하네요 ㅋㅋ