DeadLock

Dead Lock

교착상태가 없는 프로그램을 설계하는 것은 프로그래머의 책임이다.

System model
프로세스의 자원 사용 순서: 요청(후 대기), 사용, 방출

다중 응용 스레드에서 교착상태
Live lock: 라이브니스 장애, 스레드가 실패한 행동을 계속 시도할 때 발생. 실패한 작업을 동시에 재시도. 실패한 행동을 재시도하는 시간을 무작위로 정해 회피

길에서 앞에 사람이왔을 때 왼 오왼오 왼오 왼오

Deadlock characterization

Necessary conditions
1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait

Resource allocation graph
T -> R (request edge)
R -> T (assignment edge)
사이클이 포함되면 교착상태가 존재할 수 있다.

Deadlock prevention

4가지 필요조건 중 하나가 성립되지 않도록 보장함으로써 예방

Mutual exclusion

• 읽기 전용 파일의 경우 누구나 동시에 접근할 수 있다.
• 불가능한 방법. 어떤 자원들은 근본적으로 공유가 불가능하다.

Hold and wait

• 스레드 실행 전 모든 자원 요청(비실용적)
• 자원을 갖지 않을 때 자원 요청
• 자원 이용률이 낮을 수 있다. 기아가 발생할 수 있다.
  

No preemption

• 스레드가 즉시 할당할 수 없는 자원을 요청하면 현재 점유한 모든자원 선점, 즉 스레드가 대기해야하면 묵시적으로 방출
• 자원을 요청하면 사용가능한지 검사한다. 불가능하면 대기중인 스레드가 점유중인지 본다. 점유하고 있다면 선점. 아니면 대기
• CPU레지스터나 데이터 베이스 트랜잭션에 종종 적용.(상태가 쉽게 저장되고 복원될 수 있는 자원) 교착상태가 흔하게 발생하는 자원유형에는 적용할 수 없다.(Mutex, semaphore)

Circular Wait

• 자원 유형에 순서를 부여하여 순서대로자원을 요청하게 한다.

Dead Lock avoidance

자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구
각 요청에 대해 교착 상태를 회피하고자 스레드가 대기해야 하는지 여부를 알 수 있다.

Safe state

• 시스템이 어떤 순서로든 스레드들이 요청하는 모든자원을 교착상태를 야기하지 않고 차례로 모두 할당할 수 있는 상태
• Safe sequence를 찾을 수 있으면 시스템은 안전하다고 하다. 찾을 수 없으면 시스템은 불안전 하다.
• 불안전과 안전 상태는 상호 배제이며, 불안전 상태는 교착상태가 될 수도 있지만 안될 수도 있다.

Resource-Allocation graph algorithm
예약간선(claim edge) 도입 T-> R 미래에 T가 R을 요청할 것이라는 뜻.

Banker’s algorithm
스레드가 시작될 때 스레드가 가지고 있어야할 최대의 자원 개수를 종류마다 신고해야한다. 이 숫자가 최대 자원수를 넘어서면 안 된다. 스레드가 자원을 요청하면 시스템은 그것을 들어줬을 때 안전상태에 머무는지 판단해야 한다. 안전하다면 요청을 들어주고 아니면 스레드는 대기한다.

N: 스레드의 수 M: 자원의 종류 수
Available: 각 종류별로 가용한 자원의 개수를 나타내는 벡터, 크기 M
MAX: 각 스레드가 최대로 필요로 하는 자원의 개수 . 크기 N*M
Allocation: 각 스레드에게 현재 할당된 자원의 개수 크기 N*M
Need: 각 스레드가 향 후 요청할 수 있는 자원의 크기를 나타내는 행렬, 크기N*M

Safety algorithm: 시스템이 안전한지 알아낼 수 있는 알고리즘은 아래와 같다.
1. Work와 Finish는 크기가 m과 n인 벡터
2. Finish[i]==false, Need[i]<=Work를 만족하는 i를 찾는다. 찾을 수 없다면 4로 간다.
3. Work=Work+Allocation, Finish[i]=true
4. 모든I 값에 대해 Finish[i]==true이면 아전상태
이 알고리즘으로 안전 여부를 알아내는 대에는 $m*n^2$개의 연산이 필요하다.

Resource-Request Algorithm: 자원 요청을 안전하게 들어줄 수 있는지 검사하는 알고리즘
Request[i][j]==k, T[i]가 R[j]를 k개 까지 요청 하고 있다./ T[i]가 자원을 요청하면 아래와 같이 조치
1. Request[i]<=Need[i]이면 2번. 아니면 시스템에 있는 개수보다 많은 수를 요청했음으로 오류
2. Request[i]<=Available[i] 이면 3번. 아니면 요청한 자원이 당장 없으므로 T[i]는 대기
3. 시스템이 T[i]에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꿔 본다.
4. Available=Available-Request[i]
Allocation[i]+=Request[i]
Need[i]=Need[i]-Requesst[i]
만약 이렇게 바뀐 상태가 안전하면 T[i]에 여기에 반영된 정보대로 자원을 준다.
불안전하면 자원할당 상태를 원상태로 복원하고 T[i]는 Request[I]가 만족되기를 기다려야 한다.

Deadlock Detection

Single instance of each resource: wait for graph 사용.
T1-> R1, R1 ->T2 , T1 -> T2
주기적으로 사이클 탐지 알고리즘 호출 $O(n^2)$ n은 정점의 수

Several Instance of a resource Type: Available, Allocation, Request 사용

1. Work = Available 크기:M
   Allocation !=0이면 Finish[i]=false 아니면 true
2. Finish[i] ==false, Request[i]<=Work 인 i값을 찾는다.
3. Work=Work + allocation[i], Finish[i]=true, 2번으로
4. I에 대해(i=0~n) Finish[i]==false 인값이 있으면 교착상태. T[i] 교착 상태
   $m * n^2$번의 연산 필요

Detection- algorithm usage: 위의 알고리즘들은 언제 사용할까?
1. 교착 상태가 얼마나 자주 일어나는지
2. 교착 상태가 일어날 때 몇 개의 스레드가 연루되어 있는지.
CPU 이용률 40% 이하 && 한 시간에 한번

Recovery from Dead Lock: 스레드를 중지하거나 자원을 선점하거나
Process and Thread Termination: 교착상태 프로세스 모두중지, 하나씩 중지
Resource preemption: selection of a victim, roll back, starvation