Deadlock

모든 Proceess가 다른 process에 의해 야기될수 있는 event를 기다리고 있을때 발생

발생조건 :

1) Mutual Exclusion : 최소 하나의 자원이 비공유 모드로 지원되어야 함

2) hold and wait : process는 최소하나의 자원을 점유한 상태로, 다른 process에 의해 점유된 자원을 얻기 위해 대기해야함

3) No preemption : 자원들은 선점이 될 수 없고, 자발적으로만 방출될수 있다.

4) circular wait : waiting process들이 순환적 대기를 해야한다.

Solution

1) deadlock prevention, deadlock avoidance : system이 deadlock state에 들어가지 않도록 하는 protocol이 사용

2) deadlock detection : system이 deadlock에 들어가도록 허용하되, detect해서 recover하도록 하는 방법

3) 어차피 자주 발생하지 않으므로 무시하는 방법(most popular)

deadlock prevention,avoidance 방법은 비용이 너무 크므로 발생하면 재부팅하는 경우도 있다.

Deadlock Prevention

deeadlock 발생 4가지 조건중 하나라도 안되도록 하는 방법

• mutual exclusion : resource를 sharable하게 만듬

  • 문제점
    • 어떤 자원은 근본적으로 공유가 불가능함

• hold and wait : 실행전에 필요한 resource들을 모두 요청하게 한다.

  • 문제점

    • 많은 자원이 할당된후 오랬동안 사용이 되지 않기 때문에 자원의 이용률이 낮아질수있다.

    • 기아상태가 발생할수 있다. 자신이 필요로 하는 자원 중에서 최소한 하나가 항상 다른 프로세스에게 할당되어 있으면 무한정 대기할수도 있다.

• No preemption : process가 자원들을 점유하다가 즉시 할당할수 없는 자원을 요청하면 현재 점유되고 있는 자원들이 released

  • 문제점
    • 프린터나 테이프 드라이브 같은 자원에는 사용할수 없다.

• circular wait : 모든 자원 타입들에 전체적인 순서를 부여하여 각 process가 열거된 순서대로 자원을 요청하도록 요구.

Deadlock Avoidance

자원이 어떻게 요청될지에 대한 추가 정보를 요구, 프로세스의 요청과 방출에 대한 완전한 순서를 파악함으로써 교착상태를 피하기 위해서 process의 대기여부 결정

• safe state : 시스팀이 어떤 순서로든지 요청하는 자원을 교착상태 없이 모두 할당해줄수 있는 상태(safe sequence를 찾을 수 있는 상태)

• unsafe state : deadlock state가 발생가능 (항상 발생하는것은 아님)

자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

• 자원타입마다 하나의 인스턴스만을 갖고있다면 사용가능

• 요청간선을 실제로 할당간선으로 변환할때,자원할당 그래프에 사이클이 생기지 않을때만 요청을 허용

• 사이클 탐지 알고리즘의 시간복잡도는 O(N^2)이 된다.

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

• 자원타입마다 여러개의 인스턴스가 있을때 사용

• Safety Algorithm의 시간복잡도는 O(M*N^2)이다.

Deadlock Detection

1. 각 자원 타입이 한 개씩 있는 경우

• 대기 그래프(wait-for-graph)라고 하는 자원 할당 그래프의 변형을 사용해 교착상태 탐지 알고리즘을 정의

• 시간복잡도는 O(n^2)

2. 각 타입의 자원을 여러개 가진경우

• 은행원 알고리즘과 같이 시시각각 그내용이 달라지는 자료구조 사용

• 시간복잡도는 O(m*n^2)

주의할점

• 자원을 요청할때마다 탐지 알고리즘을 호출하면 오버헤드가 너무 크게 된다.

• 오버헤드를 줄이는 방법

  • 지정된 시간 간격마다 실행 (한시간에 한번)

  • CPU 이용률이 40% 이하로 떨어질때 실행

Deadlock Recovery

1. 프로세스 종료(Process Termination)

• 교착상태 프로세스를 모두 중지

  • 확실하게 교착상태의 사이클을 깨뜨리지만, 그 비용이 크다. 왜냐하면 이미 연산했던 계산 결과들을 폐기해야하기 때문이다.

• 교착상태가 제거될 때까지 한 프로세스 씩 중지

  • 각 프로세스가 중지될때마다 교착상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착상태에 있는지 확인

  • 상당한 오버헤드가 유발됨.

2. 자원 선점(Resource Preemption)

교착상태가 깨질때까지 프로세스로부터 자원을 선점해 다른 프로세스에게 주는 방법

다음 세가지를 고려해야한다.

• 희생자 선택(selection of a victim)

  • 교착상태 프로세스가 점유하고 있는 자원의수, 교착상태가 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수들을 고려하여 선점 프로세스를 선택

• Rollback

  • 프로세스를 중지시키고 재시작

  • 프로세스를 단지 교착상태를 깨뜨릴 수 있을 정도로 롤백시킬 수 있다면효과적

  • 모든 프로세스들의 상태에 대한 보다 많은 정보를 필요

• Starvation

  • 주로 비용을 고려하여 victim을 선정할때, 동일한 프로세스가 항상 희생자로 선택되는 경우 발생 가능

  • 일반적으로 비용요소에 롤백의 횟수를 포함시키는방법으로 해결한다.