7-1~2. Deadlocks 1,2

7-1 Deadlocks 1

교착상태(deadlock), The Deadlock Problem, Deadlock 발생의 4가지 조건, Resource-Allocation Graph(자원할당그래프), Deadlock Prevention, Deadlock의 처리 방법, Deadlock Avoidance, Resource Allocation Graph algorithm, Banker's Algorithm, Example of Banker's Algorithm

7-2 Deadlocks 2

Deadlock의 처리 방법, Deadlock Avoidance, Example of Banker's Algorithm, p1 request(1, 0, 2), Deadlock Detection and Recovery, Deadlock Ignorance

 

Deadlock

• deadlock
  • 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • 예) I/O device, CPU cycle, memory space, semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request, Allocate, Use, Release

Deadlock 발생 조건 4가지

• Mutual exclusion (상호배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음 (독점적으로 사용)
• No preemption (비선점형)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait (보유대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait (순환대기)
  • 자원을 기다리는 프로세스간 사이클이 형성되어야함
  • 프로세스 P0, P1, ~~~, Pn이 있을 때,
  • P0는 P1이 가진 자원을 기다림
  • P1은 P2가 가진 자원을 기다림
  • Pn-1은 Pn이 가진 자원을 기다림
  • Pn은 P0이 가진 자원을 기다림

왼쪽은 데드락상태이고,

오른쪽은 데드락은 아님 : 자원이 2개가 있는데 하나는 3번한테 가있고, 3번은 2번한테 요청했는데 하나는 1번한테 가있고, 4번한테 가있음 만약 자원이 한개뿐이였으면 데드락이 만들어 졌을 것, 여분의 자원이 더 있고 그 여분의 자원은 2번프로세스와 4번 프로세스가 가지고 있는데 이건 데드락에 연류된 프로세스는 아닌것, 4번프로세스가 자원을 가지고 있지만!, 쓰고나서 반납을 하면 자원이 available 해지고 그때 자원을 3번 프로세스한테 줄 수 있으니!

 

Deadlock 처리 방법

Deadlock Prevention

• 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• 가장 강력한 방법
  • Mutual exclusion (상호배제)
    • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
    → 공유해서는 안되는 자원 = 두 프로세스가 각자 다른 자원에 접근 해야함
  • No preemption (비선점형)
    • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
    • state를 쉽게 save하고, restore할 수 있는 자원에서 주로 사용 (CPU, memory)
    → no preemption이면 먼저 할당된 프로세스가 끝날 때까지 다른 애들은 못 쓰니까 deadlock이 예방
  • Hold and wait (보유대기)
    • 프로세스가 자원을 요청할 때 다른 어떠한 자원도 가지고 있지 않아야함
    • 방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    • 방법2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
  • Circular wait (순환대기)
    • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
    • 예를들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야한다.
  → Utilization 저하, Throughput 감소, starvation 문제

Deadlock Avoidance

• 프로세스가 시작될 때 이 프로세스가 평생에 쓸 자원의 최대량을 미리 알고있다고 가정
• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
  • 자원 요청에 대한 부가적인 정보를 이용해서 자원할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
  • safe state
    • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
  • safe sequence
    • 프로세스의 sequence<P1,P2,- - -, Pn>이 safe 하려면 Pi(1≤i≤n)의 자원 요청이 “가용자원 + 모든 Pj(J<i)의 보유자원”에 의해 충족되어야 함
    • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
      • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(J<i)가 종료될 때 까지 기다린다.
      • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

자원에 대한 인스턴스가 하나밖에 없는 상황

- 데드락의 위험성이 있다면, 애초부터 자원을 주지 않는 방식으로 avoidance함!

 

자원에 대한 인스턴스가 여러개 있는 상황

banker’s 알고리즘은 보수적이여서, 항상 최대 자원을 요청할 것이라 가정을하고 최대요청이 현재 가용자원을 가지고 충족이 되는가를 봄 충족이 되면, (예를들어, P1이 A 1개 C 2개를 요청했다치면, A가 3개 C가 2개 남아있기에  줄수있고, Need 부분을 봐서 P1이 추가 요청할 수 있는 양을 충족할 수 있는지를 확인해야함 추가로 요청해봐야 1 2 2 이니까 가용자원만으로도 Max 처리되니까 데드락으로부터 안전)그친구의 요청은 어떤 요청이든 받아들이고, need가 available로 처리가 안될경우(예를들어 P0이 B를 2개 요청했다치자, available은 B 여유있음. 하지만 2개 줘봤자 Need충족이 안되지 ) 그 요청은 받아들이지 않는 것임

데드락이 발생되지는 않겠으나, 너무나 비효율적인 방법. 혹시나 생길 데드락에 자원이 남아돌아도 주지않음!!

Deadlock Detecion and recovery

Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

P2는 현재 요청된게 000인데 여기서 다 반납할거라고 낙관적으로 가정을 할것임. 즉 그럼 available이 3 0 3이 생기겠지 이런식으로 아무것도 요청하지 않은 자원이 반납할 것을 가정해서 쌓고 쌓아서!! 요청된것들을 다 허용을 하고 요청된것들도 반납한다는 생각으로 이 시퀀스가 존재를 하면 데드락이없다!

데드락이 있는 지 판단 :

가용자원이 몇개 있는지를 보고, 가용자원으로 처리가능한게 있는지를 보고 요청하지 않은 프로세스들은 가용자원으로 합쳐놓고 (P0, P2), 이걸 가지고 처리가능한게 있는지 보고 할당 가능하면 할당해놓고, 끝까지 갈 수 있는지를 체크해보면됨.

데드락 발견되면 ? → recovery하면됨

 

• Process termination
  • abort all deadlocked process 데드락에 연류된 것들을 죽이는것!
  • aobrt one process at a time until the deadlock cycle is eliminated 데드락에 연류된 프로세스를 하나씩 죽여보는것 그랬음에도 또 데드락이면 또다른 하나를 죽여보고
• Resource Preemption
  • 비용을 최소화 할 victim의 선정
  • safe state로 rollback하여 process를 restart
  • Starvation문제
    • 동일한 프로세스가 계속 victim으로 선정되는 경우
    • cost factor에 rollback 횟수도 같이 고려!

Deadlock Ignorance

• Deadlock을 시스템이 책임지지 않음
  • 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있음
  • 만약 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처
• UNIX를 포함한 대부분의 OS가 채택

위의 2개는 데드락 생기지 않게 미연에 방지 밑에 두개는 데드락이 생기도록 놔두고, 세번째 방법은 시스템이 느려졌거나 그럴 때 혹시 데드락이 있는게 아닌가 그런상황에서 detection을 한 다음에 recover, 네번째는 아무것도 하지 않는 것

데드락은 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해서 훨씬 더 많은 오버헤드를 들이는 것이 현대적 시스템에서는 비효율적이기 때문에, 데드락이 생기든말든 놔두는 방법 사용함.