데드락

식사하는 철학자 문제

식사하는 철학자 문제 (Dining philosophers problem)

• 5명의 철학자(philosopher)가 둥근 탁자에 둘러앉아 있고 탁자 중앙에는 밥 한 공기가 있다.
• 총 5개의 젓가락이 철학자 사이마다 있다.
• 철학자는 식사를 하거나 생각한다.
• 생각할 때는 젓가락이 필요 없다.
• 식사를 하려면 자신의 왼쪽, 오른쪽에 있는 젓가락을 들어야 한다.
• 철학자 : 협력적 스레드(혹은 프로세스)
• 중앙 밥공기 : 각 스레드가 처리하고자 하는 자신의 작업
• 젓가락 : 공유 자원(혹은 공유 데이터)
• 젓가락에 대한 상호 배제 보장 필요

철학자 스레드를 위한 루틴 순서

• 일단 생각을 하다가
• 배가 고파서 밥을 먹기로 한다.
• 밥을 먹기 위해 자기 위치의 좌우 젓가락을 집는다.
• 밥을 먹는다.
• 배가 부르니 젓가락을 다시 제자리에 놓는다.

while(true){
	think();
	get_chopstick();
	eat();
	put_chopstick();
}

컨디션 변수 및 뮤텍스 락 기반 해결

• 각 젓가락을 락으로 정의
  • 락 배열 변수 chopstick[5] 정의
  • chopstick[i]에 대한 락을 획득하여 젓가락을 집음(get_chopstick)
  • chopstick[i]에 대한 젓가락을 놓고(put_chopstick) 락을 해제

  void get_chopstick(i){
  	wait(chopstick[i]);
  	wait(chopstick[(i+1)%5]);
  }
  

  void put_chopstick(i){
  	signal(chopstick[i]);
  	signal(chopstick[(i+1)%5]);
  }
  

데드락(Deadlock)

데드락(Deadlock), 교착

• 뮤텍스 락(혹은 세마포어)에 의해 두 이웃(neighboring)하는 철학자가 동시에 밥을 먹지 못하도록 보장 (상호배제 보장)
• 만약 5명의 철학자가 동시에 배가 고파서 자신의 왼쪽 젓가락을 집어든다면?
• 락 배열 변수 chopstick[5]의 모든 요소에 락이 걸림
• 각 철학자는 오른쪽 젓가락을 집어 들기 위해 무한한(forever) 시간 동안 대기

철학자 문제에서 데드락 문제를 해결하려면

• 첫 번째 방법 : 젓가락 숫자를 늘리기
• 두 번째 방법 : 좌우 젓가락이 탁자에 있을 때만 젓가락을 집기
• 세 번째 방법 : 젓가락 잡는 순서를 다르게 하기

데드락이란

• 협력적 스레드들이 자원을 요청 후 wait 상태 유지
• 요청한 자원을 점유하고 있는 스레드들도 wait상태 유지
• wait상태가 계속 유지되면 자원 점유가 계속 풀리지 않는다면 ⇒ 데드락

데드락 예제 1 : 멀티 스레드 응용

데드락 예제 2 : 라이브락

• 두 개 이상의 스레드가 작업을 진행하는 것을 서로 막는 것

데드락 조건(Deadlock Conditions)

하나라도 만족되지 않으면 데드락이 걸리지 않음

Mutual exclusion

• 최소 하나의 자원(resource)은 상호 배제를 요구해야 함

Hold and wait

• 하나의 스레드는 자원 하나는 점유한 상태에서 다른 스레드가 이미 점유한 자원 사용을 위해 대기해야 한다.
• 스레드가 최소 2개의 자원을 요구해야 함

No preemption(비선점)

• 자원은 선점될 수 없다.

Circular wait(순환대기)

• 스레드들이 자원에 대해 대기할 때 순환 구조를 이루어야 한다.

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

그래프 구조

• V : 버텍스(vertex) 집합(노드)
• E : 엣지(edge) 집합(링크, 노드 사이 연결)
• T = {T1, T2,..., Tn} : 모든 활성화(active) 스레드를 포함하는 집합
• R = {R1, R2,..., Rn} : 모든 리소스 타입을 포함하는 집합

Request edge

• 스레드가 특정 리소스 타입에 대한 인스턴스를 요청
• 스레드는 리소스를 할당받기 위해 대기
• Ti → Rj

Assignment edge

• 스레드가 특정 리소스 타입에 대한 인스턴스를 요청
• 특정 리소스 타입에 대한 인스턴스가 스레드에 할당
• Rj → Ti

자원 할당 그래프 예제

데드락이 발생하는 자원 할당 그래프 예제

사이클이 존재하는 자원 할당 그래프 예제

데드락 솔루션

데드락 무시(Deadlock ignorance)

• 데드락 발생에 대해서 신경 쓰지 않음
• 데드락을 잡는 것이 오버헤드

데드락 예방(Deadlock prevention)

• 데드락이 발생하기 전에 조치를 취함
• 데드락이 걸리는 조건 중 하나 이상이 발생하지 못하도록 해서 데드락이 발생하지 않는 것을 보장

데드락 회피(Deadlock avoidance)

• 스레드가 운영체제에게 자원을 요청할 때 자원 사용에 대한 세부정보를 운영체제가 미리 알고 있어 스레드에게 자원을 바로 할당할 것인지 대기를 좀 더 타게 할 것인지 결정을 할 수 있도록 하는 방식

데드락 탐지 및 복구(Deadlock detection/recovery)

• 데드락이 발생한 후 조치를 취하는 것

데드락 예방(Deadlock Prevention)

Mutual exclusion

• 상호 배제 자체를 없앰 (공유 데이터에 대해 쓰기 작업-읽기 작업을 동시에 대기시키지 않음)
• 실용적이지 못함

Hold and wait

• 스레드가 리소스를 소유하고 있는 동안 대기를 허용하지 않음
• 모든 리소스를 한 번에 할당받게 함
• Low resource utilization 및 starvation문제 발생

No preemption

• 스레드 간 리소스 선점을 허용
• 리소스의 상태 정보를 쉽게 저장하고 읽어 들일 수 있을 때 사용
• 뮤텍스 락이나 세마포어에서는 사용하기 어려움

Circular wait

• 스레드 간 리소스 요청 순서를 별도록 정함

순환 대기(Circular wait)

Circular wait

• 각 리소스 타입에 유일한 정수(우선순위)를 부여
• 미리 정해진 우선순위순서대로 리소스를 할당

F(first_mutex) = 1

F(second_mutex) = 5

데드락 회피(Deadlock Avoidance)

데드락 회피

• 스레드가 어떤 리소스를 어떻게 요청하고 할당받을 것인지 그 정보를 사전에 파악
• 스레드 간 리소스 할당 상태를 체크 및 circular wait 조건 만족 여부를 확인

안전 상태(Safe State)

안전 상태

• Safe sequence : 데드락을 발생시키지 않는 리소스 할당 순서
• 스레드의 리소스 요청에 대해 safe sequence를 찾을 수 있다면 시스템의 상태는 safe 하다고 정의
• 시스템이 safe state 라면 → 데드락 발생하지 않음
• 시스템이 unsafe state라면 → 데드락 발생할 가능성이 있음

  

은행원 알고리즘(Banker's Algorithm)

• 데드락 회피를 위해 사용
• 다중 인스턴스를 가지는 리소스 타입에 적용 가능
• 각 스레드는 미리 자신이 사용할 자원 최대치를 통지
• 시스템은 안전 상태(safe state)를 유지하면서 각 스레드에게 자원을 할당
• 안전상태가 유지되지 않는 겨우 각 스레드는 대기를 수행
• 안전 상태를 찾기 위한 Safety algorithm과 자원 할당을 위한 Resource-request algorithm으로 구성됨

은행원 알고리즘을 위한 자료 구조

Available

• Vector(길이 = m)
• Available[j] = k 라면 리소스 타입 Rj에 대해 k개의 인스턴스가 가용함

Max

• Matrix(크기 = n x m)
• Max[i, j] = k라면 스레드 Ti는 리소스 타입 Rj에 대해 최대 k개의 인스턴스를 요청

Allocation

• Matrix(크기 = n x m)
• Allocation[i,j] = k라면 스레드 Ti는 리소스 타입 Rj에 대해 현재 k개의 인스턴스를 할당받음

Need

• Matrix(크기 = n x m)
• Need[i,j] = k라면 스레드 Ti는 리소스 타입 Rj에 대해 k개의 인스턴스를 더 할당받아야 작업을 종료할 수 있음

Max[i,j] = Allocation[i,j] + Need[i,j]

은행원 알고리즘 : Safety Algorithm

은행원 알고리즘 : Resource-request Algorithm

은행원 알고리즘 예제

은행원 알고리즘 예제 변경