20. October 18, 2020

 

 

 

Deadlock 이란?

다중처리 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리는 상태

 

예를 들어,

화장실 수리공 김씨와 최씨가 있다.

김씨는 뚫어뻥을 가지고 일을 하고 있지만 이제 최씨가 가지고 있는 스패너가 필요하고,

최씨는 스패너를 가지고 일을 하고 있지만 이제 김씨가 가지고 있는 뚫어뻥이 필요한 상황.

 

서로 상대방이 가지고 있는 공구가 자기한테 할당되기를 무한정 기다리고 있는 상태를 교착상태. Deadlock이라고 한다.

 

Deadlock 발생 조건

교착상태는 아래 네 가지 조건을 모두 동시에 충족할 때 발생

1. 상호배제 (Mutual Exclusion) : 한 자원에 대한 여러 프로세스의 동시 접근 불가

2. 점유와 대기 (Hold and Wait) : 자원을 가지고 있는 상태에서 다른 프로세스가 사용하고 있는 자원의 반납을 기다리는 상태

3. 비선점(Non Preemptive) : 다른 프로세스의 자원을 강제로 가져오기 불가

4. 환형대기(Circle Wait) : 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 소유

 

 

해결방법?

1. 예방(Prevention)

Deadlock의 발생 가능성을 사전에 모두 제거하도록 시스템을 조절. 상호배제의 부정, 점유와 대기 부선정, 비선점의 부정, 환형대기의 부정

장점: 가장 명료하고 널리 사용됨

단점: 자원낭비가 심함

 

2. 회피(Avoidance)

Deadlock의 발생 가능성을 미리 알고, 판단하여 프로세스를 제어.

*은행가 알고리즘 : 프로세스가 실행 할 자원을 미리 OS에 요청하면 OS는 판단 후 실행 허용여부를 전달하는 알고리즘 (자원이 2개 이상일 때 / 단점: 사용자 프로세스가 일정해야 하고, 사용자가 최대 필요량을 미리 알아야 함)

*자원할당 그래프 알고리즘: 자원 할당 그래프에 요청 간선과 할당 간선에 추가하여, 예약 간선이라는 새로운 유형의 간선을 도입하는 알고리즘

 

3. 회복(Recovery)

Deadlock이 발생하는 것을 완전히 차단하지 않고, 만약 교착상태가 발생하면 발생 이후에 문제를 해결 

*프로세스 종료: 교착상태에 속한 프로세스를 모두 중지 (abort) ‒ 프로세스 재실행 비용이 크다. 

교착상태가 제거될 때까지 한 프로세스 씩 중지 (abort) ‒ 교착상태 탐지 알고리즘 수행 오버헤드가 크고 중지할 프로세스 선택 문제가 복잡하다.

*자원 선점: 교착상태가 제거될 때까지 자원을 선점하여 다른 프로세스에게 할당 해주는 방식.

희생자 선택 (selection of victim),  롤백 (rollback), 기아 (starvation)을 모두 고려하여야 한다.

 

4. 무시(Ignore)

Deadlock을 해결할 때에도 문맥교환에 의한 오버헤드로 성능 저하가 발생. 교착상태태에 의한 성능 저하보다 이를 해결할 때의 성능저하가 큰 경우 그냥 무시