Skip to content

deadlock.md

Latest commit

 

History

History
85 lines (65 loc) · 7.38 KB

deadlock.md

File metadata and controls

85 lines (65 loc) · 7.38 KB

참고. 상호배제(Mutual Exclusion)란?

다중 프로그래밍 시스템에서 여러 프로세스들이 동시에 독립적으로 진행됨으로 인하여 발생하는 문제점을 해결하는 기법 중 하나. 상호배제란 둘 이상의 프로세스가 임계 영역에 동시에 접근하는 것을 금지시키는 방법이다.

교착상태(Deadlock)란?

  • 교착상태란 상호배제에 의해 다중 프로그래밍 시스템에서 여러 프로세스들이 공유하고 있는 일부 자원들을 점유하고 놓지 않으면서 다른 프로세스가 갖고 있는 자원들을 요구하여 무한정으로 기다리고 있는 상태를 말한다.

deadlock 0. Process1,2와 공유자원 Resource1,2가 있다고 하자.

  1. Process1이 Resource1에 을 사용하며 Lock 동시에 Resource2를 요청하며 대기 Wait 한다.
  2. 하지만 Process2가 이미 Resource2에 대한 선점을 진행하고 있는 상태이며, Process2 또한 Resource1의 사용을 요청한다.
  3. 결과적으로 어떤 프로세스가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생하게 되고 대기상태로 들어간 프로세스들이 실행상태로 변경될 수 없게되며 ::교착상태::가 발생하게 된다.

교착상태 필요조건 4가지

  • 교착상태가 발생하기 위해서는 필요 조건이 4가지가 존재한다.

1.상호배제(Mutual Exclusion)

  • 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 자원이어야 한다. 이러한 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
  • 위 그림처럼 한 자원에 대해 한 Process가 임계구역을 설정(Lock)하고 있기 때문에 다른 프로세스가 동시에 사용할 수 없는 교착 상태가 발생한다.

2. 비선점(non-preemption)

  • 한 프로세스가 사용중인 자원은 다른 프로세스가 뺏을 수 없는 비선점 자원이어야 한다.
  • 위 그림처럼 한 프로세스가 사용중인 자원은 프로세스가 끝나기 전까지 Lock을 풀지 않으며 다른 프로세스가 계속해서 Wait하고 있다.

3. 점유와 대기(Hold and Wait)

  • 프로세스가 자원을 가지고 있는 상태 와 동시에 다른 프로세스가 갖고 있는 자원의 반납을 기다리고 있는 상태 이다.

4. 환형대기(Circular wait)

  • 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 갖고있는 상태다.
  • 그림에서는 2개의 프로세스와 2개의 자원만이 예시로 나왔지만, 선형이 아닌 원형을 이루게 되어 프로세스의 자원 할당에서 첫 번째 프로세스 와 마지막 프로세스의 자원할당이 겹치게 되어 원형에 있는 모든 프로세스가 자원 할당을 받고자 기다리는 형태를 생각해보자(꼬리물기)

교착상태 해결 방법

  • 교착상태를 해결하는 방법에는 예방, 회피, 회복, 무시 4가지 방법이 있다.

1. 예방(Prevention)

  • 교착상태 발생 조건은 4가지 조건을 모두 만족시켜야 하므로 교착상태 조건 중 하나만 해결하면 교착상태는 해결된다.
  1. 상호배제 예방 : 시스템 내에 있는 독점적으로 샤용할 수 있는 자원을 없애는 방법이다. 모든 자원을 공유하도록 하는것인데, 시스템 내에는 공유할 수 없는 자원이 있기 때문에 사실적으로는 상호배제 예방은 어렵다.
  2. 비선점 예방 : 모든 자원을 뺏을 수 있게 만드는 방법. 그러나 임계구역 보호를 위해 잠금을 사용한다면 자원을 뺏을 수 없을 뿐더러 자원을 뺏어도 어떤 조건으로 뺏을 지 결정이 어렵다.
  3. 점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서는 다른 자원을 기다리지 못하게 예방한다. 하지만 다음과 같은 단점이 존재한다. -프로세스가 자신이 사용하는 자원을 알기 어렵다. -자원의 활용이 떨어진다.(당장 사용도 안하면서 선점하는 현상) -많은 자원을 사용하는 프로세스는 동시에 모든 자원을 확보하기 어렵기 때문에 아사현상(Starvation)이 발생할 수 있다.
아사현상(Starvation)이란?
- 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태, 기아상태라고도 한다.
  1. 원형 대기 예방 : 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방한다. 즉, 모든 자원에 숫자를 부여해 숫자가 큰 방향으로만 자원을 할당하는 것이다. (작은 수가 부여된 자원을 잡은 상태에서 -> 큰 상태의 자원을 잡는것은 가능 하지만 그 반대는 불가능) -이 또한 프로세스 작업 진행에 유연성이 하락하고, -자원의 번호를 부여하는 방법을 어떻게 할지 문제가 발생

2. 회피(Avoidance)

  • 교착상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상 자원을 나누어주면 교착상태가 발생하는지 ::파악::하여 ::그 수준 이하::로 자원을 나눠주는 방법이다.
  • 대표적인 알고리즘으로 ::은행원 알고리즘::이 있다.
은행원 알고리즘이란?
간단하게 교착상태를 예측하여, 교착상태가 가능한 상태는 자원을 할당하지 않는 알고리즘.
검사를 진행하여 ‘안정상태’에 있으면 자원을 할당, ‘불안정상태’라면 다른 프로세스들이 자원을 해제할 때까지 기다린다.

3. 회복(Recovery)

  • 교착상태가 발생하는 것을 아예 막지 않고, 만약 교착상태가 발생하면 발생 이후에 문제를 해결하는 방법
  • 회복 이전에 교착상태를 검출하여 검출된 교착상태를 푸는 회복작업을 진행한다.
교착상태의 검출
1. 타임아웃을 이용한 교착 상태 검출
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법. 특별한 알고리즘 없이 쉽게 구현할 수 있다.

2. 자원 할당 그래프를 이용하여 교착 상태 검출
자원 할당 그래프를 통해 시스템 내의 프로세스가 어떤 자원을 사용하는 지, 혹은 기다리는지 알 수 있다. 교착 상태가 없는 할당 그래프는 싸이클이 없고, 교착상태가 존재하는 경우 싸이클이 존재한다.
  • 자원할당 그래프는 사진과 같다

자원할당 그래프

  • 검출이 완료된 교착상태의 후속작업으로 회복을 진행한다.
  1. 교착 상태를 일으킨 모든 프로세스를 종료 : 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착상태를 일으킬 수 있다. 따라서 종료 후 순차적으로 실행한다.
  2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 : 우선순위가 낮은 프로세스 먼저 종료, 우선순위가 같은 경우 작업시간이 짧은 프로세스 먼저 종료. 두 조건이 모두 같은 경우 자원을 많이 사용하는 프로세스 먼저 종료

4. 무시(Ignore)

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