Hyokyun Yim bio photo

Hyokyun Yim

Koreatech Computer Science Engineering undergraduate 4 grade.

Facebook Github

Deadlock 을 예방하는 방법 or Deadlock 최소화 하는 방법에 대해 알아보자

Overview

Deadlock

  • 여러 프로세스들이 Concurrent(동시 실행) 하게 수행 할때 발생 하는것이다.
  • Deadlock(교착상태)은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다려 아무것도 완료되지 못하는 상태를 말한다.
  • 컴퓨터 과학자들이 Deadlock 문제를 해결하기위한 이론들을 많이 연구하고 개발했지만 실제로 적용하는데 많은 어려움이 있다.
  • [참고]Concurrent 는 CPU가 여러개 여서 수행되는 경우도 있지만. 싱글 프로세서에서도 발생할 수 있다.

Deadlock의 예

  • deadlock은 Resource를 공유할 경우 발생한다.
  • 위 그림은 프로세스가 어떤 자원을 할당 받았는지 표현하는 자료구조 인 Resource Allocation Graph 이다.
  • 화살표가 자원에서 프로세스쪽으로 가면 : 그 자원이 프로세스에 할당 되었음
  • 화살표가 프로세스쪽에서 자원쪽으로 가면 : 프로세스가 그 자원을 사용하기를 원함
  • Process 0는 자원0을 먼저 할당 받았고 그 다음 자원1을 요청 하고 있다.
  • 반대로 Process 1는 자원1을 할당 받았고 그 다음 자원0을 요청 하고 있다.
  • 하지만 각 프로세스가 원하는 자원을 다른 프로세스가 사용중이기 때문에 해제를 하기 전까지 사용할수가 없다.
  • 이러한 Deadlock을 해결하려면 OS가 빨리 인지를 해야하는데 Resource Allocation Graph 를 이용하면 쉽게 찾을수 있다. -> 그래프 안에 어떠한 사이클이 보이면 Deadlock이 존재 하는 것이다.
  • 정리하자면 프로세스 0 -> 자원1 -> 프로세스1 -> 자원 0 -> 프로세스 0 으로 이어지는 하나의 사이클이 존재한다. 이러한 경우 Deadlock이 존재한다고 말한다.
  • [제한조건] Resource Allocation Graph 에서 사이클이 존재할때 Deadlock을 탐지 하려면 각 자원을 Guard 하는 세마포어가 바이너리 세마포어(0과 1만을 사용)일 때만 가능하다. 만약 카운팅 세마포어일 경우 다른 프로세스에게 세마포어를 제공해줄 수 있어 조건이 성립되지 않는다.

Deadlock 을 발생시키는 조건들

  • Mutual exclusion : 어떤 한 프로세스가 한 자원을 사용 하고 있으면 다른 프로세스에게 공유가 되어서는 안된다.
  • No preemption : 내가 자원을 장악하고 있고 다른 자원을 원할때 내개 사용 하는 자원을 포기하고 줄 수 없다.
  • Hold and wait : 내가 자원을 가지고 있는데 다른 자원을 원하는 상황이 되면 내가 사용하고 있는 자원은 계속 가지고 있어야 하고 원하는 자원은 계속 원하고 있어야 한다.
  • Circular wait : 위 그래프에서 이야기 했던 사이클과 같은 흐름이 있어야한다.

Deadlock Prevention기법 - Banker’s Algorithm

  • 어떤 프로세스가 시스템에 존재하는 자원을 사용 하고 있으면 그 상태를 Safe State와 Unsate State 2가지 상태로 나누는 것이다.
  • Safe State : 시스템이 Deadlock 상태에 절대 빠지지 않는 상태
  • Unsafe State : 시스템이 Deadlock 상태에 빠질 가능성이 있는 상태, Deadlock 에 빠질 수도 있고 빠지지 않을 수도 있다.
  1. 12개의 자원이 있고 이 자원들을 3개의 프로세스가 사용한다.
  2. 각 프로세스는 12개의 자원중 최대 몇개 까지 자원을 사용할 것인지 선언을 해야한다.(max needs)
  3. 또 현재 몇개의 자원을 가져다 쓰고 있는지 선언해야한다.(Current Allocations)
  4. 그 후에 현재 사용 할 수 있는 자원이 몇개인지 체크를 한다.(P0,P1,P2 에게 모두 할당하고 남은자원 3개)
  5. 먼저 P0를 제거할 수 있는지 체크해야한다. P0를 제거시키려면 10개 즉 최대 Needs 인 10개의 자원이 필요한데 남은 자원은 3개 P0이 현재사용하고있는 자원이 5개이므로 제거 할수 없다.
  6. 그러면 P1을 체크해보자 P1을 제거하기 위해선 총 최대 4개의 자원이 필요하다. 현재 사용가능한 남은 자원은 3개이고 P1이 사용하고 있는 자원이 2개 이므로 충분히 제거 가능하다.
  7. P1을 제거 한 후 P1이 사용하던 자원을 회수 받아서 총 남은 자원이 5개가 되었고, 현재 P0, P2 가 돌아가고 있다.
  8. 이 5개의 남은 자원으로 P2는 제거 하지 못하므로 다시 P0를 제거한다. 남은 자원 5개 P0이 사용하는 자원 5개 총 10개이므로 제거가 가능하다.
  9. P0 제거 후 남은 자원은 10개가 되었고, P2가 가동중 이다.
  10. 남은 자원 10개와 P2가 현재사용중이 자원 2개로 충분히 P2 제거가 가능하다.
  11. 그래서 이 상태를 Safe state 라고 한다.

Safe 상태에 있다고해서 항상 Safe 할까?.. 아래 예외적인 상황을 보자

  • 만약 P2의 Current Allocations 을 +1 한다면 Deadlock 가능성 있는 상태로 가게 된다.
  • P1을 제거 한후 총 사용 가능한 자원의 수는 4개가 된다. 그러나 P0이나 P2를 제거 하려면 자원이 부족하여 Deadlock 에 빠지게 된다.

Banker’s Algorithm 정리

  • 어떤 프로세스가 새로 들어오면 그 프로세스는 항상 최대 자원을 선언해야 한다.
  • 어떤 프로세스가 자원 요청을 하면 그 요청을 수락했을때 발생하는 상태가 안전한지 체크 한다.
  • 만약 안전하면 그 요청을 들어주고
  • 아니라면 그 요청을 Waiting 상태에 넣는다.

Banker’s Algorithm 에 필요한 Array

m: 시스템에 존재하는 자원 개수 n: 시스템에 존재하는 프로세스의 개수

  1. Available[1:m] : 사용 가능한 자원의 수를 표현 -> 여러개의 인스턴스 표현 가능
  2. Max[1:n, 1:m] : 프로세스 별 최대 요구 자원(2차 배열) -> 프로세스 i가 j타입의 자원을 최대 몇개까지 요구하는지
  3. allocation[1:n, 1:m] : 현재 각 프로세스에 할당되어 있는 자원 수 -> 프로세스 i가 j타입의 자원을 몇개 받아 쓰고 있는
  4. Need[1:n, 1:m] : 각 프로세스 별 남아 있는 자원의 수 (Max[i,j] - Allocation[i,j])

Banker’s Algorithm 동작 구현 - Safety check

  1. Woark[1:m] 와 Finish[1:n] 라는 두 배열을 둔다. -> Finish 배열은 어떤 프로세스가 제거 되었는지를 알려주는 Boolean 배열이다. , Work 배열은 어떤 자원의 중간 계산 결과를 저장하고 있는 배열이다.
  2. Work에 현재 사용가능한 자원을 할당 한다. 그리고 종료된 프로세스가 아직 없으므로 Finish[i] = False로 만든다.
  3. 현재 수행을 끝내지 않았고 , 최대로 필요로 하는 자원을 다 만족 시킬 수 있는 프로세스를 찾는다.(현재 사용가능한 자원으로 종료시킬 수 있는 프로세스를 찾는다)
  4. 그 프로세스를 찾으면 Work = Work + Allocation[i] , Finish[i] = True 종료 시키고 , 자원을 반환 받고 다시 위 과정을 반복하여 더 이상 남은 프로세스가 없으면 다음 단계로 간다.
  5. 우리가 원하는 상황은 모든 프로세스가 Finish[i] = True 가 되는것인데 몇몇 프로세스가 False 라면 Safe 하지 않은 상태가 된다.

Banker’s Algorithm 동작 구현 - 자원 할당 승인

Safety check 알고리즘을 사용하여 다음 단계를 진행한다.

  1. Request[1:m, 1:m] 에 자원을 요구하는 각 프로세스들의 요청을 기록한다.
  2. 그런 후 어떤 프로세스가 최대값이라고 정의 했던값보다 더 높게 요구하면 에러를 상태를 띄운다.
  3. 아니면 승인을 하고 다음 단계로 간다
  4. Safety check 알고리즘을 돌려서 조건에 맞으면 요청을 수행하고 아니면 요청을 거부한다.

Deadlock 해결 방법 - Detection

  • Deadlock을 회피할 수 없을때 사용
  • Banker’s Algorithm 의 safety check 를 사용하여 마지막에 Finish[i] = False 인 프로세스들을 Detect 한다.
  • Detect 한 프로세스를 죽여서 해결가능하면 죽이고, 아니라면 CPR 기법 추가적으로 사용해 해결한다.

CheckPoint and Resume (CPR)

응용 프로그램이 동작 중에 일정 시간 간격으로 응용 프로그램의 모든 상태를 디스크에 저장하고, 문제가 발생했을 때 저장된 응용 프로그램의 상태를 사용해 응용 프로그램의 수행을 재개하는 기법

[참고]Livelock

  • Deadlock은 프로세스가 수행은 못하지만 자원을 낭비하지 않는다.(단지 프로세스 waiting 상태)
  • 이 Livelock(무한반복)은 CPU 자원을 계속 허용하면서 아무일도 하지 않는 것을 말한다

  • 어느 한 회사가 DB 서버를 만들고 여러 사원들이 이용할 수 있게 구축을 하였다.
  • 그러나 이 회사의 네트워크 Bandwidth가 낮아서 서버 검색시간이 너무 오래 걸렸다.
  • 그래서 속도가 더 좋은 스위치와 랜으로 교체 했지만 더 성능이 나빠졌다.
  • 이 문제가 바로 Livelock 문제이다.
  • 사원들이 DB 서버에 접근하기 위해 Request를 보내면 DB 서버 하단에 있는 NIC(Network Interface Card)가 인터럽트를 걸게된다.
  • 인터럽트를 걸어서 인터럽트 서비스 루틴이 들어오는 패킷들을 패킷큐에 적재 시킨다.
  • 이 패킷 큐가 궁극적으로 IP 프로토콜을 처리하는 큐가 된다.
  • 그런데 Bandwidth가 너무커서 패킷이 너무많이 도착하게 된다. 즉 인터럽트가 너무많이 걸리게 된다.
  • IP프로토콜이 패킷큐에 적재된 패킷을 읽어가기전에 이 큐가 가득 차버리는 문제가 발생한다.
  • 결국 여태 까지 저장해놓았던 패킷을 버리는 방법을 선택한다.
  • 그런데 또 채우자마자 인터럽트가 들어온다.
  • 인터럽트 프로세싱은 유저 프로세싱보다 우선순위가 높기때문에 인터럽트 핸들러가 도냐고 유저 프로세스가 돌 시간이 없다. 결국 인터럽트 프로세스만 돌아서 패킷만 채우고 버리고 채우고 버리고 하는 현상만 반복된다. -> “Receive Livelock” 문제 라고도 한다.
  • 라우터 같은 장치에서 이런 문제가 많이 발생한다.

[참고]Livelock 해결법 - Interrupt Coalescing

  • Livelock 문제의 근원은 인터럽트가 너무 발생하는 것이다.
  • 인터럽트 발생 빈도를 줄이기 위해서, 여러 번의 입력을 모아서 한번에 인터럽트를 발생시키거나 일정 시간마다 한번씩 인터럽트를 발생시켜서 해결한다.
  • 즉 패킷이 50개 또는 100개 쌓일때 까지 인터럽트를 걸지 않다가 조건에 만족 할 경우 인터럽트를 한번 거는 것이다. 다시 말해 인터럽트 서비스 루틴의 수행 빈도를 낮추는 것이다. 그러면 그사이에 유저프로세스가 돌아서 수행을 한다.

[참고]Indefinite postponement

  • Deadlock은 2개이상의 프로세스가 존재할때 발생하지만 Indefinite postponement(무기한 연기)는 혼자서 발생한다.
  • 절대 일어날수 없는 이벤트를 기다리는 것이다.
  • 자신이 어떤 프로세스로부터 메세지를 기다리는데 그 메세지를 보내주려던 프로세스에 문제가 생겨서 제거가 되버렸다. 그러면 Indefinite postponement에 빠지게 된다.

추가적으로 ..

  • Deadlock 은 비행기나, 전투기 같은 Realtime OS와 같은데서 잘 다뤄야 할 중요한 문제이다.
  • 또는 기업에서 출시한 핸드폰의 Deadlock 을 해결하는데 개발자들이 많은 시간을 투자하기도 한다.