[운영체제] #7 Deadlocks

개념

Deadlock (교착상태)

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태.
• 프로세스가 필요한 자원 중 일부 자원을 가지고 해당 자원을 내놓지 않으면서 서로 상대방이 가지고 있는 자원을 요구하는 상태.

Resource

• HW (I/O Device, CPU cycle, Memory Space ...) / SW (Semaphore ...) 모두 포함
  • ex) 프로세스가 세마포어 2개를 얻으려고 했는데 다른 프로세스가 하나를 가지고 있다면 Deadlock
• 자원을 사용하기 위해서 프로세스는
  • Request -> Allocate -> Use -> Release 단계를 거친다.

발생 조건 4가지

Mutual Exclusion

상호 배제 : 매 순간 하나의 프로세스만이 자원을 독점적으로 사용한다.

No Preemption

비선점 : 프로세스가 스스로 자원을 내놓기 전엔 빼앗기지 않음.

Hold and Wait

보유 대기 : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음.

Circular Wait

순환 대기 : 자원을 기다리는 프로세스 간에 사이클이 형성됨.

자원할당그래프

그래프 사이클 존재	Deadlock
X	X
O	자원 인스턴스가 하나이면 deadlock 여러개이면 데드락의 가능성이 있음.

처리 방법

Deadlock Prevention

• Deadlock이 생기지 않도록 위의 4가지 조건 중 어느 하나라도 만족되지 않게 예방한다.
  가장 강력함.

Mutual Exclusion

• 공유해서는 안되는 자원의 경우 반드시 한번에 하나만 접근할 수 있음. -> 성립.

Hold and Wait

• 프로세스가 자원을 요청할 때, 다른 자원을 가지고 있지 않아야 함.
  • 방법1. 프로세스 시작 시 필요한 자원을 모두 할당 받음. -> 비효율적
  • 방법2. 자원이 필요하면 보유 자원을 모두 놓고 요청 -> 효율적

No Preemption

• 프로세스가 어떤 자원을 기다릴 때, 이미 보유한 자원을 선점 (빼앗음)
• 모든 필요한 자원을 얻을 수 있을 때 해당 프로세스는 다시 시작된다.
• 프로세스의 상태를 쉽게 save & restore 할 수 있는 자원에서 주로 사용 (CPU, MEmory)
  • 빼앗았을 때 상태를 저장하기 어렵다거나 해서 문제가 생기면 이 방법은 비추.

Circular Wait

• 사이클 안생기게
• 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당한다.

하지만 이 모든걸 만족하려면 Utilization(사용성)? 내려갑니다~, throughput(처리율) 내려갑니다~, Starvation? 생깁니다~ 다다 비효율적입니다~ 라서 많이 사용하진 않는다.

Deadlock Avoidance

• 자원 요청에 대한 부가 정보를 이용해서 Deadlock 가능성이 없는 경우에 자원 할당.
  • 부가 정보 : 해당 프로세스가 최대로 요청할 자원을 보고 안전(safe)한지를 조사해서 자원을 줄지 말지 판단.
• 시스템 상태가 원래 상태로 돌아올 수 있는 경우에만 자원을 할당한다.

ex) 각 프로세스가 필요로 하는 각 자원별 최대 사용량을 미리 선언하는 방법.

• 프로세스 시작 시 프로세스가 평생 쓸 자원을 알고 있어서 데드락 가능성이 있으면(unsafe) 자원을 할당하지 않는다.
  • Safe State : 시스템 내의 프로세스에 대한 Safe Sequence 가 존재.
  • Safe Sequence
    • 프로세스 sequence <P1, P2, ... Pn> 이 safe 하다.
    • == Pi 의 자원 요청 <= 가용자원 + 모든 Pj (j < i) 의 보유 자원 이어야 한다.
    • Pi-1 이 종료되면 Pi 의 자원 요청을 만족시켜서 수행한다.

자원이 하나 -> 자원 할당 그래프 알고리즘

• 위의 자원 할당 그래프에서 Claim Edge 라는 개념 추가.
  • 프로세스가 자원을 미래에 요청할 수 있음을 뜻한다.
  • 자원을 요청하면 Request Edge 로 바뀌고
  • 자원을 놓으면 다시 Claim Edge 로 바뀐다.

• Claim Edge 를 포함해서 사이클이 생기지 않는 경우에만 요청 자원을 할당한다.
• 프로세스 수 n 일 때, Cycle 생성 여부 조사 O(n^2)

자원이 여러개 -> Banker's Algorithm

가정

• 모든 프로세스는 자원의 최대 사용량을 미리 명시
• 프로세스가 요청 자원을 모두 할당받으면 유한 시간 안에 해당 자원을 반납.

방법

• 자원 요청 시 safe 상태를 유지하는 경우에만 자원을 할당.
• safe : (앞으로 요청할 총 자원 수 <= 가용 자원) 이면 자원 할당.
  • 최악의 상황을 가정하고 바라보는 것.
• 아니라면 자원을 주지 않는다.

예시

• 5개의 프로세스 : P0~P4
• 3개의 자원 : A 10개, B 5개, C 7개

• Allocation : 현재 각 프로세스에 할당된 자원
• Max : 각 프로세스가 평생 사용할 자원
• Available : 현재 남아있는 자원
• Need : 각 프로세스가 앞으로 사용할 자원
• Need <= Available 이면 자원 할당.
  • ex1) P1 이 1 0 2 를 요청하면 P1 의 Need 인 1 2 2 은 3 3 2 로 처리가 가능하기 때문에 자원을 준다.
  • ex2) P0 이 0 2 0 을 요청하면 가용 자원 3 3 2만 봤을 땐 줄 수 있어 보이지만, P0 의 Need 7 4 3 을 3 3 2 로 충족할 수 없기 때문에 자원을 주지 않는다.

• safe sequence P1 P3 P2 P4 P0 이 존재하므로 시스템은 safe state 이다.
• 절대 데드락이 생길 수가 없음. 그치만 자원이 남는데도 최악의 상황을 가정하고 자원 할당을 안하는 것은 비효율적이다.

Deadlock Detection and Recovery

• Deadlock 발생은 허용하나 Deadlock Detiction Routine 을 두어서 Deadlock 발견 시 Recover

자원이 하나씩 -> 그래프

• 자원을 빼고 wait-for graph 로 그려서 사이클 여부를 체크한다.
  • 자원할당 그래프를 변형해서 자원 대신 프로세스만으로 node 를 구성한다.
  • Pj 가 가진 자원을 Pk 가 기다리고 있다면 Pk -> Pj
  • 사이클이 있는지 주기적으로 조사한다. O(n^2)

자원이 여러개 -> table (~= banker)

• 은행원 알고리즘과 비슷하나 여기는 최선의 상황 가정.
  • 자원을 현재 요청하고 있지 않은 프로세스는 할당된 자원을 반납할 것이라고 본다.
  • Request <= (Available + Request 0 0 0) 이면 자원 할당.

• 그치만 자원을 반납한다고 해도 Request 보다 적게 반납할 수 있으므로 Deadlock 의 가능성은 있음.

Recovery

• Process termination (종료)
  • 데드락에 연관된 모든 프로세스를 다 죽이거나
  • 데드락 사이클에 있는 프로세스를 하나씩 죽여본다.
• Resource Preemption (데드락에 걸린 프로세스의 자원을 뺏음.)
  • 비용을 최소화할 수 있는 프로세스를 하나 선정해서 자원을 뺏는다.
  • Safe State 로 롤백해서 프로세스를 다시 시작.
  • Starvation
    • 항상 같은 것만 죽이면 그 프로세스는 계속해서 진행하지 못할 수 있음.
    • 비용의 고려 요소에 롤백 횟수 (몇 번 자원 뺏겼는지) 도 고려해서 자원 빼앗을 프로세스정해야 함.

Deadlock Ignorance

• Deadlock 을 시스템이 책임지지 않음
• UNIX 외 대부분의 현재 OS 가 채택
• 데드락이 매우 드물게 발생하기 때문에, 데드락에 대한 조치가 더 큰 오버헤드 일 수 있음. -> 데드락 발생 시 사용자가 알아서 관리해라!

출처 / 참고

반효경 교수님의 2014 운영체제 7. Deadlocks, 2 강의를 듣고 포스팅하고,
공룡책을 읽고 추가 정리합니다.

사진 출처는 강의 자료.