Deadlock

Deadlock이란?

두 개 이상의 프로세스가 더 이상 진행할 수 없는 상황

 

a,b,c,d는 resource, 자동차는 process라고 하자.

모든 자동차가 서로 지나가려고 하다가 꽉~막혀버렸다.

이런 상황을 deadlock이라고 표현할 수 있다.

 

resource는

• 한 번에 하나의 프로세스에 의해 사용될 수 있다.
• 하드웨어와 소프트웨어 모두 될 수 있다.
• 즉, OS가 개입할 여지가 있다는 말이다!

잘 활용하면.. deadlock막을 수 있겠는데..?

 

 

일반적으로 데드락은 Non preemption resources를 가정한다.

 

Resource Allocation Graphs

데드락을 미연에 방지할 수 있다!

먼저 vertices부터 살펴보자

동그라미로 표시되는 Px는 프로세스를 의미하고,

네모로 표시되는 Rx는 자원을 의미한다.

작은 검정점은 resource타입의 instance이다.

 

edge를 살펴보자

• Request Edge : P->R로 가는 유향 에지
  - 말그대로 프로세스가 자원을 요청한다.
• Assignment edge : R->P로 가는 유향 에지
  - 자원이 프로세스에 점유되었다 = held by

왼쪽 그림은 전형적인 deadlock을 보여준다.

2개의 자원이 두개의 프로세스에 의해 점유되었고 각각의 프로세스가 서로의 자원을 요청하고 있는 상황이다.

 

오른쪽 그림은 deadlock이 아니다.

왼쪽과 비슷한 그림이지만 자원 instance 개수가 더 많기 때문에 프로세스는 요청하고있는 자원을 점유할 수 있다.

 

위 그림을 보고 알 수 있는 사실

1. 그래프가 cycle을 포함하지 않으면 deadlock은 발생하지 않는다.

2. 그래프가 cycle을 포함한다면
  - 자원 당 하나의 instance가 있다면 데드락은 발생한다.

  - 자원 당 여러 개의 instance가 있다면 데드락이 발생할 가능성이 있다.

 

아까 본 자동차 deadlock그림을 그래프로 표현하면 오른쪽 그림이 된다.

 

Deadlock은

발생하기 전에 방지,

발생 후에 수정

하는 방법을 통해 해결한다.

 

 

Dining Philosophers Problem

5명의 철학자는 5개의 포크가 있는데, 식사를 위해 개인당 2개의 포크를 이용한다.

하지만 두 명 이상의 철학자는 동시에 같은 포크를 사용할 수 없다 즉 상호배제가 이루어져야한다.

그릇은 process, 포크는 resource

 

아래는 식사하는 철학자 문제를 보여주는 code이다.

세마포어를 5개 만든다.

wait을 하고 포크하나를 잡는다. -> p operation

wait을 하고 포크하나를 더 잡는다. -> v operation

eat : 먹는다.

signal : 포크하나를 다 썼다고 시그널을 보낸다.

signal : 나머지 포크도 다 썼다고 시그널을 보낸다.

 

실제 자바로 구현된 코드를 보며 이해해보자.

 

잘가다가 마지막에 deadlock발생!

 

Deadlock Characterization

deadlock은 아래 조건을 만족했을 때 발생한다.

• Mutual exclusion : 하나의 자원은 여러개의 프로세스에 의해 동시에 사용될 수 없다.
• No preemption : 자원은 중간에 빼앗길 수 없다.
• Hold and wait : 최소 하나의 자원을 점유하고 있는 프로세스는 다른 프로세스에 의해 점유되고 있는 다른 자원을 기다리고 있다.
• Circular wait : 점유하고 대기하는 것들이 cycle을 이룬다.

 

Deadlock Handling

1. Deadlock prevention : 데드락 조건 4가지중 한가지라도 만족하지 않도록
2. Deadlock avoidance : 데드락이 발생하지 않도록 승인을 하지 않음
3. Deadlock detection and recovery : 주기적으로 데드락 체크, 일정 시간동안 뭐가 없으면 deadlock이라고 예상하고 해당 프로세스 죽임 
4. Just ignore the problem : 수동적인 방법. 위 내용들은 비용이 들기에 비용절감 하기 위해 그냥 무시

1,2는 데드락발생 전/ 3,4는 데드락 발생 후 handling

 

1. Deadlock Prevention

• Hold and Wait 제거 
  프로세스는 필요한 자원을 한 번에 요청한다. 그리고 모든 요청을 동시에 승인 할 수있을 때까지 프로세스를 차단한다. 이 방식은 자원을 과다 사용하기에 비효율적이고, concurrency를 낮게 한다는 단점이 있다.
• Circular Wait 제거
  Resource Ordering. 자원에 순서를 매겨 순서대로 자원을 요청하도록 한다.
  불편하고 복잡하다. incremental적 제한이 있다.

room = {4}이다 즉 counting semaphore를 4로 제한한다.

CS에 진입할 수 있는 process는 최대 4개가 된다.

따라서 deadlock은 발생할 수 없다.

 

아래는 hold and wait조건을 제거한 방식이다.

 

아래는 resource reordering하는 방식이다.

1. Deadlock Avoidance

safe state(deadlock이 발생할 수 없는 상태)만들고 유지할 수 있도록 관리하는 방법

이 방식은 prevention하는 방식보다 concurrency를 보장할 수 있다.

banker's algorithm으로 나타낼 수 있다.

safe state : deadlock을 야기하지 않는 resource의 sequence가 적어도 하나 있는 상태이다.

unsate state : safe state가 아닌 상태

특정 시간에 snapshot을 찍었다고 하자.

P1은 최대 10개의 자원을, P2는 4개, P3는 9개를 가질 수 있다.

P1,P2,P3는 12개의 resource를 할당받을 수 있다.

현재 5,2,2개씩 할당받았기 때문에 3개의 자원이 남아있는 상태이다.