교착상태(Deadlock)

Previous운영체제 Next프로세스와 스레드

Last updated 5 years ago

Was this helpful?

교착상태(Deadlock)

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, 교착상태라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

데드락의 발생조건

교착상태는 한 시스템 내에서 다음의 네가지 조건이 동시에 성립 할 때 발생한다. 따라서 아래의 4가지 조건중 하나라도 성립하지 않도록 만든다면 교착상태를 해결할 수 있다.

상호배제(Mutual exclusion) : 최소한 하나의 자원은 비공유방식(nonsharable mode)으로 점유되어야한다.
- 비공유 방식 점유 : 한번에 하나의 프로세스만 자원을 사용할 수 있음을 의미.
- 예방법 ) 상호배제 부정 :여러개의 프로세스가 공유자원을 사용할 수 있도록 한다.
점유 대기(Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다. 예방법 ) 점유대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
비선점(No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다. 예방법) 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
순환 대기(Circular wait) : 프로세스의 집합 {P0,P1,...,Pn에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2...Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다. 예방법 ) 순환대기 부정 : 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

자원 할당 그래프

프로세스와 자원간의 관계를 나타내는 그래프.

방향이 있는그래프
정점(vertex)들과 정점을 연결하는 간선(edge)들로 이루어짐
간선의 두 형태
- 요청선(request edge) : 프로세스 정점에서 자원 정점으로 연결된선 :
- 할당선(assignment edge) : 자원 정점에서 프로세스 정점으로 연결 된 선.

Cycle 과 Deadlock

사이클이 있으면 데드락은 존재할수도고 안할수도 있다.

자원 유형당 하나의 인스턴스 : 데드락
인스턴스가 여러개면 ? : 무조건 deadlock인건 아님. 아닐수도 있다.

아래의 경우는 사이클은 존재하지만 데드락은 존재하지 않는다.

데드락 처리방법

교착상태 예방 및 회피 : 교착상태가 되지 않도록 보장하기 위하여 교착상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
- 데드락 예방(Deadlock prevention)
- 데드락 회피(Deadlock avoidance) : 추가적인 정보(시간, 최대치 개수)를 받아서 deadlock 생길지 안생길지 확인해서 deadlock 안생기게 지연or 할당.
교착상태 탐지 및 회복 :교착상태가 되도록 허용한 다음에 회복시키는 방법(교착상태로부터 회복이란 교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 거을 의미한다.)
- 프로세스 종료(Process termination) 방법.
  - 교착상태에 속한 프로세스를 모두 중지 : 프로세스 재실행 비용이 크다.
  - 교착상태가 제거될 때까지 한 프로세스 씩 중지 - 교착상태 탐지 알고리즘 수행 오버헤드가 크고 중지할 프로세스 선택 문제가 복잡하다.
- 자원 선점 (Resource preemption) 방법.
  - 교착상탤가 제거될 때까지 자원을 선점하여 다른 프로세스에게 할당 해주는 방식.
  - 희생자 선택(selection of victim), 롤백(rollback), 기아(starvation)를 모두 고려하여야 한다.
교착 상태 무시 : 대부분의 시스템은 교착상태가 잘 발생하지 않으며, 교착상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

데드락 예방(prevention)

교착상태 발생 조건중 하나를 제거함으로써 해결하는 방법.
자원의 낭비가 심하다.

1. Mutual Exclusion

여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

2. Hold and wait

프로세스가 실행되기 전 필요한 모든 자원을 할당한다.

3. No Preemption

자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게한다.

4. Circular wait

자원에 고유한 번호를 할당하고, 번호순서대로 자원을 요구하도록 한다.

Previous운영체제 Next프로세스와 스레드

Last updated 5 years ago

Was this helpful?

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, 교착상태라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

데드락의 발생조건

상호배제(Mutual exclusion) : 최소한 하나의 자원은 비공유방식(nonsharable mode)으로 점유되어야한다.
- 비공유 방식 점유 : 한번에 하나의 프로세스만 자원을 사용할 수 있음을 의미.
- 예방법 ) 상호배제 부정 :여러개의 프로세스가 공유자원을 사용할 수 있도록 한다.
점유 대기(Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다. 예방법 ) 점유대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
비선점(No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다. 예방법) 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
순환 대기(Circular wait) : 프로세스의 집합 {P0,P1,...,Pn에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2...Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다. 예방법 ) 순환대기 부정 : 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

자원 할당 그래프

프로세스와 자원간의 관계를 나타내는 그래프.

방향이 있는그래프
정점(vertex)들과 정점을 연결하는 간선(edge)들로 이루어짐
간선의 두 형태
- 요청선(request edge) : 프로세스 정점에서 자원 정점으로 연결된선 :
- 할당선(assignment edge) : 자원 정점에서 프로세스 정점으로 연결 된 선.

Cycle 과 Deadlock

사이클이 있으면 데드락은 존재할수도고 안할수도 있다.

자원 유형당 하나의 인스턴스 : 데드락
인스턴스가 여러개면 ? : 무조건 deadlock인건 아님. 아닐수도 있다.

아래의 경우는 사이클은 존재하지만 데드락은 존재하지 않는다.

데드락 처리방법

교착상태 예방 및 회피 : 교착상태가 되지 않도록 보장하기 위하여 교착상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
- 데드락 예방(Deadlock prevention)
- 데드락 회피(Deadlock avoidance) : 추가적인 정보(시간, 최대치 개수)를 받아서 deadlock 생길지 안생길지 확인해서 deadlock 안생기게 지연or 할당.
교착상태 탐지 및 회복 :교착상태가 되도록 허용한 다음에 회복시키는 방법(교착상태로부터 회복이란 교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 거을 의미한다.)
- 프로세스 종료(Process termination) 방법.
  - 교착상태에 속한 프로세스를 모두 중지 : 프로세스 재실행 비용이 크다.
  - 교착상태가 제거될 때까지 한 프로세스 씩 중지 - 교착상태 탐지 알고리즘 수행 오버헤드가 크고 중지할 프로세스 선택 문제가 복잡하다.
- 자원 선점 (Resource preemption) 방법.
  - 교착상탤가 제거될 때까지 자원을 선점하여 다른 프로세스에게 할당 해주는 방식.
  - 희생자 선택(selection of victim), 롤백(rollback), 기아(starvation)를 모두 고려하여야 한다.
교착 상태 무시 : 대부분의 시스템은 교착상태가 잘 발생하지 않으며, 교착상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

데드락 예방(prevention)

교착상태 발생 조건중 하나를 제거함으로써 해결하는 방법.
자원의 낭비가 심하다.

1. Mutual Exclusion

여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

2. Hold and wait

프로세스가 실행되기 전 필요한 모든 자원을 할당한다.

3. No Preemption

자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게한다.

4. Circular wait

자원에 고유한 번호를 할당하고, 번호순서대로 자원을 요구하도록 한다.