퇴근 후 운영체제 시리즈 - 데드락

18 Apr 2024 in Studying CS Basic

운영체제 스터디 기록

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

• 데드락 문제
  • 자원
  • 우선순위 역전
    • 우선순위 상속 프로토콜
• 데드락 발생 조건
  • Mutual exclusion (상호배제)
  • No preemption (비선점)
  • Hold and wait (보유하고 대기)
  • Circular Wait (환형 대기) ⭐️
• 자원 할당 그래프
• 데드락 처리 방법
  • 데드락 예방 (방지 효과)
  • 데드락 회피 (방지 효과)
    • Safe State
    • Safe Sequence
    • 은행원 알고리즘
    • Flow
  • 데드락 Detection & recovery (복구 효과)
    • 데드락 탐지
    • Wait-for 그래프 알고리즘
    • 데드락 복구
  • 데드락 무시
• 연습문제
  • 단일 스레드 프로세스만 관여된 교착 상태가 발생할 수 있는가?

데드락의 추상화 그림

⛸️ 서로가 서로를 막아서 진행이 불가능한 상태

• 시스템에서는 자원을 기반으로 데드락이 일어난다.

데드락 문제

자원

✔︎ 하드웨어, 소프트웨어 등을 포함하는 개념

✔︎ I/O 디바이스, CPU 사이클, 메모리 공간, 세마포어 등

✔︎ 프로세스가 자원을 사용하는 절차

• request
• allocate
• use
• release

✔︎ 데드락 예시 1

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

✔︎ 데드락 예시 2

우선순위 역전

🎣 우선순위가 낮은 프로세스가 커널 데이터를 접근 중일 때 락에 의해 보호를 받고 있음

이때 높은 프로세스가 접근해야하는데 더 높은 우선순위 프로세스에 의해 선정되는 경우 기아 현생 발생가능

ex) 우선순위가 L < M < H 로 구성된 프로세스가 있다 하자.

1. 우선순위가 L인 프로세스가 현재 세마포어 변수를 쓰고 잇다 하자 (세마포어 변수는 비선점 자원의 대표적인 예)
2. 우선순위 H 프로세스가 이를 써야된다고 가정
3. 이때 우선순위 M 프로세스가 일을 다 해서 인터럽트를 걸어 L을 선점한다.

⇒ 이 문제를 우선순위 역전이라 한다.

우선순위 상속 프로토콜

우선순위 L인 프로세스를 H로 임시 상향하게 한다. ⇒ 프로세스 M이 L을 선점하는 것을 막음

이후 방출될 때 프로세스 L은 다시 낮아지고 이후 더 높은 우선순위인 H가 실행된다.

데드락 발생 조건

🌛 꿀팁 : 이걸 OS 용어다 생각하고 외우지 말고 정말 실제 세계에서 일어나는 현상을 떠오르면서 이해하면 너무 당연한 것들임

ex) 위 도로를 표현한 그림

Mutual exclusion (상호배제)

🎆 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

No preemption (비선점)

🎬 프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏기지 않음

ex) 포크레인이 차를 치우지 않음

Hold and wait (보유하고 대기)

🏓 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 잇음

ex) 운전자가 핸들을 절대 놓지 않고 계속 나아갈려함 → 포기하지 않음

Circular Wait (환형 대기) ⭐️

🏷️ 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함

자원 할당 그래프

🛴 자원과 프로세스간의 관계를 표현하는 방법

• P → R : 프로세스가 자원을 요청 중

• R → P : 자원이 프로세스에 할당됨

• 그래프에 사이클이 없으면 deadlock 이 아님
• 그래프에 사이클이 있다면
  • 자원이 여러개에 할당될 수 있다면 데드락의 가능성이 잇음
  • 자원이 오로지 한개의 프로세스에 할당될 수 있다면 데드락

데드락 처리 방법

🗿 똑같이, 외우려 하지말고 이해하면 편하다

데드락 예방 (방지 효과)

🪀 자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

ex) 그래서 신호등이 있다

Mutual Exclusion

• 이걸 방지하지 않을 수 없음 → 애초에 공유 데이터가 아니라면 데드락이 없음

Hold and wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 비효율적임. 자원을 모두 할당을 필요가 없음
• 방법 2. 자원이 필요한 경우 보유 자원을 모두 놓고 요청해야됨

비선점

• 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작
• 상태를 쉽게 저장하고 복원할 수 있는 자원에서 주로 사용 (CPU, Memory, 데이터베이스 트랜잭션)
  • 얘네는 저장 복구가 쉬우니까 데드락이 걸릴 수 없는 자원임
  • 문제는 세마포어 변수 같은 거는 애초에 선점이 불가함

환형 고리

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 순서가 3인 자원 $R_i$ 를 보유 중인 프로세스가 순서 1인 자원 R_j 를 할당받기 위해서는 우선 $R_j$를 놓아줘야됨

⇒ 이용률 저하, 기아 발생 등 비효율적인 방법

데드락 회피 (방지 효과)

📈 ✔︎ 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당

✔︎ 시스템 상태가 원래 상태로 돌아올 수 있는 경우에만 자원 할당

• 부가 정보를 이용해서 자원 할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델을 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

Safe State

시스템 내의 프로세스들에 대한 safe sequence 가 존재하는 상태

Safe Sequence

✔︎ 프로세스의 시퀀스 \(<P_1,\ P_2, \ P_3, \ P_4 ... >\) 가 safe 하려면 $P_i$ 의 자원 요청이 가용 자원 + 모든 \(P_j \ (j<i)\) 의 보유 자원 에 의해 충족되어야 됨

✔︎ 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장

• \(P_i\) 의 자원 요청이 즉시 충족될 수 없으면 모든 \(P_j\) 가 종료될 때까지 기다린다.
• \(P_{i-1}\) 이 종료되면 P_i 의 자원요청을 만족시켜 수행

• P ⇢ R : 해당 프로세스가 자원을 미래에 요청할 수 있음
• 자원 요청 시 실선으로 바뀜
• 점선을 포함해서 사이클이 생긴다 하더라도 데드락은 아니나 데드락이 생길 수 있음 ⇒ 점선까지 고려해서 사이클 여부를 체크하겠다! 가 핵심
• 사이클 생성 여부를 조사할 때 시간 복잡도가 너무 크다.
  • 한 노드에 대해 DFS

• 자원당 하나의 프로세스만 할당 가능하다면 ⇒ 자원할당 그래프 알고리즘 사용(사이클 체크)

은행원 알고리즘

Allocation

• 현재 프로세들에게 할당된 자원들의 수

Max

• 우리는 각 프로세스가 얼마나 쓸지 부가정보를 알고 있기에 활용할 수 있는 정보
• 각 프로세스가 평생의 최대로 써야할 자원의 개수

Available

• 가능한 자원 할당 수

Need (Max - Allocation)

---

Flow

🪓 가용 자원의 수만을 고려하지 않고 Need도 같이 고려한다!

⇒ 가용 자원의 수를 요청하더라도 자신이 필요한(Need) 를 충족하지 못하면 자원을 주지 않는다.

1. \(P_0\) 의 요청은 듣지 않는다. 가용 자원으로 Need를 만족할 수 없기 때문
2. \(P_1\) 의 요청을 받아 들인다. 가용자원을 주어서 Need를 만족하면 이를 상환할 수 있기 때문에.
3. …

⇒ 만족할 수 있는 프로세스들이 있기에 지금 시스템은 safe state 다! ⇒ 반납될 수 있기에 안전한 자원에 먼저 주면 그에 따라 가용 자원이 늘어나서 하나씩 처리가 될 수 있다.

데드락 Detection & recovery (복구 효과)

🏮 데드락 발생은 허용하되 그에 대한 detection 루틴을 두고 발견 시 복구

데드락 탐지

• 리소스 타입 당 single instance 인 경우
  • Wait-for 그래프에서의 사이클이 곧 데드락
• Multiple instance 인 경우
  • 은행원 알고리즘과 비슷한 알고리즘을 활요

Wait-for 그래프 알고리즘

• 리소스 타입 당 single instance 인 경우
  • Wait-for 그래프 활용
    • 자원할당 그래프의 변형
    • 프로세스만으로 Node 구성
    • \(P_i\)가 가지고 잇는 자원을 \(P_k\) 가 기다리는 경우 \(P_k → P_i\)
  • 알고리즘
    • Wait-for 그래프에 사이클이 존재하는지 주기적 검사
    • O(n^2)

• 여기서는 부가 정보가 필요 없음

• 여유 자원이 있다면 무조건 준다.

• 0번이나 2번이 요청을 따로 안하기 때문에 자신의 자원을 줄 수 있음 → 가용 자원 UP
• 하나씩 풀리면 가능하나 계속 못한다면 데드락 처리

탐지 알고리즘은 언제 돌리는가?

• 교착 상태가 얼마나 자주 일어나는가?
• 일어나면 통상 몇개의 스레드가 거기에 연루되는가

데드락 복구

✔︎ 프로세스 끝내기

• 데드락과 관련된 프로세스 모두 끝내기
• 하나하나씩 끝내가면서 데드락 풀리면 stop

✔︎ 자원 선점

• 비용을 최소화 할 victim 프로세스 선정
• safe state로 롤백하여 프로세스를 다시 시작
• 기아 문제
  • 동일한 프로세스가 계속 선정되는 경우
  • cost factor에 롤백 횟수도 같이 고려 (일종의 aging 효과)

데드락 무시

🪓 (이 내용은 차량 그림에 적용 불가)

데드락을 시스템이 책임지지 않음

대부분의 OS가 이 방법을 채택

그냥 유저한테 떠맡김 → 프로그램이 작동하지 않습니다~

이걸 해결하고 처리하는 방법이 더 오버헤드로 작용할 수 잇음

---

연습문제

단일 스레드 프로세스만 관여된 교착 상태가 발생할 수 있는가?

단일 스레드 프로세스에서 교착 상태 발생 가능성

일반적으로 단일 스레드 프로세스에서는 교착 상태가 발생하지 않습니다.

교착 상태는 두 개 이상의 프로세스가 서로 자원을 기다리면서 서로 진행될 수 없는 상태를 의미합니다. 단일 스레드 프로세스는 자원을 스스로 점유하고 사용하기 때문에 다른 프로세스와 자원 경쟁이 발생하지 않아 교착 상태가 발생할 가능성이 낮습니다.

하지만 특정 조건에서는 단일 스레드 프로세스에서도 교착 상태가 발생할 수 있습니다. 예를 들어, 다음과 같은 경우가 있습니다.

재귀 호출: 스레드가 자기 자신을 재귀적으로 호출하면 무한 재귀에 빠질 수 있습니다. 이 경우 스레드는 스스로 점유하고 있는 자원을 계속 사용하게 되고, 다른 작업을 수행할 수 없게 됩니다.

시스템 호출 블록: 스레드가 시스템 호출을 수행하는 동안 블록되고, 해당 시스템 호출을 처리하는 코드에서 다른 스레드가 블록되는 경우 교착 상태가 발생할 수 있습니다.

데드락 예방 메커니즘 오류: 운영 체제의 데드락 예방 메커니즘이 오류를 일으키면 잘못된 방식으로 스레드를 블록시켜 교착 상태를 발생시킬 수 있습니다.

따라서 단일 스레드 프로세스에서 교착 상태가 발생하는 가능성은 매우 낮지만, 절대 불가능하지는 않습니다.