[OS] Deadlocks

밈무·2023년 2월 9일

목록 보기

9/15

Deadlock(교착상태)

데드락 이란?
각자 일부 자원을 가지고 놓지 않으면서 상대방이 가진 자원을 요구하는 상황에서 발생한다.
위 그림에서 같은 길에 있는 차들을 일련의 프로세스라고 보고, 지나고 있는 도로를 프로세스가 가지고 있는 자원이라고 보자. 위 그림에선 4가지 종류의 차들이 길을 점유하고 있으면서 상대방이 지나고 있는 길을 내어놓으라고 하고 있는 상황으로, 컴퓨터 관점에서 보았을 때 프로세스들이 자원을 점유하고 있으면서 다른 프로세스가 가지고 있는 자원을 요구하는 상황이다.
즉, Deadlock이란 일련의 프로세스들이 서로가 가진 자원을 기다리며 blocked된 상태이다. 이때 자원은 하드웨어와 소프트웨어 자원 등을 포함한다.

예시

하드웨어 자원에서의 Deadlock

시스템에 2개의 tape drive가 있다고 가정해보자.
프로세스 P1, P2가 각각 하나의 tape drive를 가지고 있는 채 다른 하나의 자원을 기다리고 있으면 어느 누구도 더 이상 진행되지 않는 deadlock 상태에 빠지게 된다.

소프트웨어 자원에서의 Deadlock

두 프로세스가 lock을 거는 세마포어 두개를 획득하여 일을 하고 싶어하는 상황이다. 위의 상황에서는 CPU가 누구한테 가더라도 자원 획득이 불가능하여 데드락에 빠지게된다.

Resource

하드웨어와 소프트웨어 등을 포함하는 개념으로 I/O device, CPU cycle, memory space, semaphore 등이 이에 해당한다.

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

Request : 자원을 요청한다.
Allocate : 자원을 획득한다.
Use : 자원을 사용한다.
Release : 사용이 끝나면 자원을 반납한다.

프로세스가 자원을 사용하는 절차를 위 단계별로 구분하여 어떻게 하면 데드락을 막을 수 있을지 앞으로 설명할 예정이며, 이를 위해 먼저 데드락 발생 조건과 데드락이 발생 여부를 어떻게 알 수 있는지를 알아보자.

Deadlock 발생의 4가지 조건

Mutual Exclustion(상호배제)

프로세스가 자원을 가지고 있는 동안에는 그 하나의 프로세스만이 자원을 독점적으로 사용한다.

No Preemption(비선점)

비선점은 프로세스가 자원을 스스로 내어놓기만 하고 강제로 빼앗기는 경우는 없는 것을 말한다. (자원을 빼앗을 수 있으면 필요한 경우 빼앗으면 되기 때문에 데드락이 발생하지 않는다.)

Hold and Wait(보유대기)

자원을 가진 프로세스가 다른 자원을 얻지 못한 상태에서 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는 것이다.
내가 가지고 있는 자원은 내어놓지 않으면서 추가적인 자원을 요청할 시 데드락이 발생한다.

Circular Wait(순환대기)

데드락이 발생하려면 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
초반의 그림에서 도로를 점유하고 있는 차들의 모습으로 이해할 수 있다.

프로세스 P0, P1, ..., Pn이 있을 때
P0은 P1이 가진 자원을 기다림
P1은 P2가 가진 자원을 기다림
P(n-1)은 Pn이 가진 자원을 기다림
Pn은 P0이 가진 자원을 기다림

데드락이 발생했는지 알아보는 방법

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

데드락이 발생했는지 알아보기 위해 graph그려 확인해보는 방법이다.

그래프 안에 cycle이 없으면 데드락이 아니다.
cycle이 있는 경우에는 데드락일 수도 있고 아닐 수도 있다.

위의 그림의 경우 cycle이 존재하지 않기 때문에 데드락이 발생하지 않는다는 것을 알 수 있다.

만약 자원(사각형)의 인스턴스(사각형 내부의 점)이 하나밖에 없는 경우에는 cycle이 있으면 데드락이다.
하지만 자원의 인스턴스가 여러 개 있는 경우에는 cycle이 있어도 데드락일 수도 있고 아닐 수도 있다.

왼쪽 그림의 경우 cycle이 2개가 있다. 이 상황에는 R2의 인스턴스가 2개가 있지만 데드락이 발생한다. 왜냐하면 R2의 인스턴스가 모두 P1과 P2에게 이미 할당되어 있고, P1과 P2 모두 또다른 자원을 요청하지만 다른 프로세스가 해당 자원들을 잡고 있기 대문이다.

오른쪽 그림의 경우 cycle이 1개가 있다. 이 cycle과 관련된 자원들의 인스턴스가 모두 여러개가 있다. 이 자원들은 모두 다른 프로세스가 가지고 있지만 P2, P4는 데드락에 연루되어 있지 않기 때문에 이 프로세스들이 자원을 내어놓는다면 cycle이 사라지기 때문이다.

Deadlock 해결 방법

deadlock prevention
deadlock avoidance
deadlock detection and recovery
deadlock ignorance

위로 갈수록 더 강한 처리 방법이다.

1, 2번째 방법은 데드락을 미리 예방하는 것이다.
3번째 방법의 경우 시스템이 느려지면 deadlock detection을 한 후 발견 시 recover한다.
4번째 방법은 deadlock이 있어도 아무것도 하지 않는 방식이다.
현대 OS는 대부분 4번째 방법을 채택한다. 데드락이 발생하면 사람이 알아서 프로세스를 죽이는 방식으로 해결해야 한다. 이를 채택하는 이유는 데드락이 빈번하게 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 드는 오버헤드로 인해 비효율이 발생하기 때문이다.

deadlock prevention

자원을 할당할 때 deadlock의 4가지 필요 조건 중 어느 하나를 원천적으로 데드락의 조건이 만족되지 않도록 하는 방법이다.

mutual exclusion
한번에 하나의 프로세스만 사용할 수 있는 자원(인스턴스가 하나라면?)이라면 배제할 수 있는 조건이 아니다.
hold and wait
- 이를 없애기 위해서는 자원을 기다리는 상황에서는 자원을 보유하고 있지 않도록 한다.
- 방법 1
  어떤 프로세스가 시작할 때 그 프로세스가 필요한 모든 자원을 할당받게 한다. 중간에 추가로 필요한 자원이 없다. 모든 것을 다 hold하고 시작하여 wait 할 일이 없다.
  -> 이 방법은 매 시점마다 필요한 자원이 다른데 그것을 처음 시작부터 보유하고 있기 때문에 비효율적이다.
- 방법 2
  자원이 필요할 경우 그때그때 보유 자원을 모두 놓고 다시 요청하는 방법이다. 이미 hold한 자원을 다 뱉어낸 다음에 wait를 한다.
  -> 자진해서 반납하여 문제를 해결한 것!
No Preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 빼앗겨 선점된다. (Preemption)
- 모든 필요한 자원을 얻을 수 있을 때 프로세스가 다시 시작된다.
- CPU와 memory처럼 state를 쉽게 save하고 restore할 수 있는 자원에서 자주 사용된다.
Circular Wait
- 자원마다 번호를 매겨서 할당 순서를 정하고 정해진 순서대로만 자원을 할당한다. 이 방식으로 하면 cycle이 발생하지 않는다.
  예) 순서가 3인 자원을 보유 중인 프로세스가 순서가 1인 자원을 할당받기 위해서 우선 3번 자원을 먼저 release해야 한다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용하여 deadlock의 가능성이 없는 경우에만 자원을 할당하는 방법이다. 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.
이 역시 미연에 데드락을 방지하는 방법이다.
deadlock avoidance는 프로세스가 시작될 때 프로세스가 평생 쓸 자원의 최대량을 미리 알고 있다고 가정하고 이런 자원 요청에 대한 부가정보를 이용해서 자원할당이 deadlock으로부터 안전한지 동적으로 조사하여(=어떤 프로세스가 자원 요청을 했을 때 데드락이 생길 가능성이 있는지 파악한다.) 안전한 경우에만 할당한다.

Single Instance per Resource Types

자원의 인스턴스가 하나밖에 없는 경우에는 resource allocation graph algorithm을 사용한다.

1. 점선 화살표는 프로세스로부터 자원으로 가는 화살표로, 이 프로세스가 평생동안 적어도 한번은 이 자원을 사용할 일이 있음을 의미한다.
2. 두번째 그림에서처럼 P2가 R2를 실제로 요청하면 실선 화살표로 바뀐다.
3. 이때 R2는 아무도 가지고 있지 않기 때문에 가장 오른쪽 그림처럼 P2에게 R2를 할당해준다.

현재 경우에는 데드락이 아니다. 왜냐하면 P1이 R2를 요청할 가능성이 있는 것이지, 당장 요청한 것은 아니기 때문이다.

하지만 만약 이 시점에 P1이 R2를 요청하게 되면 cycle이 생기고 데드락이 발생한다.
만약 이 시점에 P1이 R2를 요청하지 않고 P2가 먼저 자원을 다 쓰고 반납하게 된다면 데드락이 발생하지 않고 아무 문제 없이 진행된다.

하지만 deadlock avoidance 방식은 최악의 상황을 가정하기 때문에 점선을 포함하여 cycle을 판단한다.

Multiple Instances per Resource Types

자원의 인스턴스가 여러 개인 경우에는 Banker's Algorithm을 사용한다.

available에 남아있는 여분의 자원 양으로 최대 요청인 need가 만족되면 할당한다.

deadlock avoidance는 항상 safe state를 보장하는 방식이다.
safe state는 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태를 의미한다. safe sequence는 Pi(1≤i≤n)의 자원요청이 “가용자원 + 모든 Pj(j<i)의 보유자원”에 의해 충족되어야 한다. 즉 Pj가 다 사용하고 뱉어낸 자원과 가용자원이 합쳐져 Pi가 사용할 수 있는 상황을 말한다. 이 조건을 만족하면 Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj가 종료될 때까지 기다리는 식으로 모든 프로세스의 수행을 보장한다.

Deadlock Detection and Recovery

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

자원 당 인스턴스가 하나인 경우
- 자원할당 그래프 사용해서 cycle이 발생하면 deadlock으로 판단
- 자원할당 그래프에서 자원을 빼고 프로세스끼리 화살표로 연결하여 wait-for graph라는 더 간결한 그래프를 만든다.
- deadlock detection을 위해 wait-for graph를 그리고 cycle이 발생하는지 확인한다.
  - 여기서 cycle을 찾는 overhead는 O(n^2)의 시간이 걸린다. 프로세스가 n개가 있고 각 프로세스에 대해 화살표는 최대 (n-1)개가 존재할 수 있다. 따라서 모든 화살표를 따라가면 O(n^2)의 시간이 걸린다.
자원 당 인스턴스가 여러 개인 경우
- 테이블 사용(Banker’s algorithm과 유사한 방식을 활용한다)
- Allocation : 현재 할당된 자원
- Request : 현재 들어와 있는 요청
- Available : 가용 자원
- 낙관적인 접근. 현재 요청된 것이 없는 프로세스들이 사용하고 있는 자원들은 반납될 것이라고 가정하기 때문에 request들을 받아들인다.
- 데드락이 발견되면 recovery를 해야한다.
  - 방법 1) Process termination 데드락에 연루된 프로세스들을 한번에 모두 죽인다.
  - 방법 2) Resource Preemption 비용을 최소화할 victim을 선정하여 하나씩 자원을 빼앗아본다. 이는 데드락에 연루된 프로세스들로부터 자원을 빼앗는 방법이다. safe state로 rollback한 후 process를 restart하여 데드락을 없앤다. 자원을 빼앗아 데드락을 없앴는데 똑같은 패턴이 반복되어 데드락이 계속 발생할 수 있다. 동일한 프로세스가 계속해서 victim으로 선정되는 경우 starvation문제가 발생할 수 있기 때문에 cost factor에 rollback 횟수도 같이 고려한다.