[운영체제] 교착상태

운영체제 강의(이화여대,반효경 교수님)를 듣고 정리한 내용입니다.

---

The Deadlock Problem

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

Deadlock Example 1

• 시스템에 2개의 tape drive가 있다.
• 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

Deadlock Example 2

• Binary semaphores A and B
• P0 : P(A) -> P(B)
• P1 : P(B) -> P(A)
• P0은 B를 획득하기 까지 무한히 기다리고, P1은 A를 획득하기 까지 무한히 기다리는 데드락 발생

Deadlock 발생의 4가지 조건

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

Resource-Allocation Graph(자원할당그래프)

 

싸이클이 있다고 꼭 데드락은 아님
자원이 1개의 인스턴스만 있고 그게 사용중이라면 데드락.
리소스에 자원이 여러개 있다면 데드락 가능성 있음.
자원을 아예 사용할 수 없고 대기 상황이 만들어져야 데드락이 된다.

Deadlock의 처리 방법

• Deadlock Prevention (데드락 방지)
  • 자원 할당시 데드락의 4가지 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance(데드락 방지)
  • 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
  • Resource Allocation Graph algorithm
  • Example of Banker's Algorithm
• Deadlock Detection and recovery(데드락 놔둠)
  • 데드락 발생은 허용하되 그에 대한 detection 루틴을 두어서 deadlock 발견시 recover
• Deadlock Ignorance(데드락 놔둠)
  • Deadlock을 시스템이 책임지지 않음.
  • UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

데드락이 발생하는 4가지 조건을 원천적으로 차단함.

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야 함. -> 이런 상황엔 없앨 수 없음.
• Hold and Wait
  • 프로세스가 자원을 요청할 떄 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 -> 자원 비효율성
  • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • 자원을 뺏어올 수 없기 때문에 발생 -> 빼앗아 올 수 있게 하면 데드락이 안생김.
  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 적용된다.
  • State를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용 (CPU,memory)
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당
  • 예 ) 순서가 3인 자원 Ri를 보유중인 프로세스가 순서 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release 해야 한다.
    -> Utilization 저하, throughput 감소, starvation 문제 ( 생기지도 않은 데드락을 생각해서 비효율적임 )

Deadlock Avoidance

• 자원이 있지만 데드락 가능성이 전혀 없는 경우에서만 자원을 할당.
• 자원을 할당했을 때 데드락이 생길 가능성이 있다면 할당하지 않음. 항상 safe한 상태를 유지한다.
• 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당.
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence<P1,P2,...Pn>이 safe하려면 Pi의 자원 요청이 "가용 자원 + 모든 Pi의 보유 자원"에 의해 충족되어야 함.
  • 조건을 만족하면 다음 방법으로모든 프로세스의 수행을 보장 - Pi의 자원 요청이 즉시 충족될 수 없으므로 모든 Pj가 종료될 때 까지 기다린다. - Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다.
    
• avoidance 알고리즘
  • Single instance per resource types
    • Resource Allocation Graph Algorithm 사용
  • Multiple instance per resource types
    • Banker's Algorithm 사용

자원 인스턴스가 하나일 때 : 자원 할당 그래프 알고리즘

이용 가능한 자원이 있다고 다 내어주지 않음. 데드락 발생 가능성이 있다면 내어주지 않음.

자원 인스턴스가 여러개일 때 : Banker's 알고리즘

프로세스가 시작될 때 평생 사용할 자원을 미리 할당받음.
전체 인스턴스에서 할당된 자원을 빼면 이용 가능한 자원 수.
Need : 추가 요청 가능한 자원의 양
프로세스가 추가 자원을 요청할 때 가용 자원을 먼저 체크하고 가용 자원을 넘지 않는 요청이라면 자원을 줌.

• 프로세스 1이 (1,0,2)의 자원을 요청하는 상황이라면 ?
  • P1이 추가로 요청할 수 있는 최대가 (1,2,2)인데 이걸 최대로 요청해도 Available에 있는 자원으로 충족 되기 때문에 줌.
• P0이 (0,2,0)- B 2개를 요청하면?
  • Available에는 B가 3개 있긴 함.
  • 그러나 !! P0이 최대로 요청할 수 있는 자원의 양이(7,4,3)인데 Available의 양이 이것을 만족하지 못함.
  • 따라서 주지 않음.
  • 언젠가 다른 프로세스들이 자원들을 반납하고 필요한 자원의 양이 맞춰지면 그 때 자원 할당.

데드락은 안생기지만 비효율적 - 항상 최악의 경우를 가정해서 자원을 할당한다.

Deadlock Detection and recovery

자원이 1개 인스턴스일때 - 그래프로 그려서확인 가능

• Wait-for Graph 알고리즘
  • 리소스 타입장 1개의 인스턴스인 경우
  • Wait-for graph
    • 자원 할당 그래프의 변형
    • 프로세스만으로 node를 구성
    • Pj가 갖고 있는 자원을 Pk 가 기다리는 경우 Pk -> Pj
  • Algorithm
    • Wait-for graph에 사이클이 존재하는지를 주기적으로조사
    • O(N^2)

자원이 여러개의 인스턴스일 때 - 테이블 만들어서 확인

Deadlock Detection

• 리소스 타입당 1개의 인스턴스인 경우
  • 자원 할당 그래프에서 사이클이 곧 데드락을 의미
• 리소스 타입당 다중 인스턴스인 경우
  • Banker's 알고리즘과 유사한 방법 활용
  • 데드락인지 아닌지 확인?
    • 낙관적으로 데드락이 아닐 가능성들로 판단
    • 현재 자원 갖고 있는 프로세스들이 자원을 반납할것이라고 가정하고 추가 요청하는 자원들을 만족한다고 가정.
    • 요청을 완료할 수 있는 시퀀스가 있다면 데드락이 없다고 판단.
    • 가용 자원으로 가능한 프로세스들의 요청 처리.
    • 자원이 부족하다면 현재 요청하지 않는 프로세스들이 자원을 반납한다고 가정.

Deadlock Recovery

• 데드락이 발견되면 복구
• Process termination (프로세스 종료)
  • 데드락에 관련된 모든 프로세스들을 죽여버림.(abort)
  • 싸이클이 사라질 때 까지 한 타임에 프로세스를 하나씩 죽여본다.
• Resource Preemption (자원 뺏기)
  • 비용을 최소화 할 victim 선정
  • safe state로 rollback 하여 process를 restart
  • Starvation 문제
    • 동일한 프로세스가 계속해서 victim으로선정되는 경우
    • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음.

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