우리 말로는 교착상태라고도 한다.

위의 그림을 보면 사거리에서 차들이 각자의 방향대로 진행하길 고집해 결국 모든 차가 움직이지 못하는 상태가 된 것을 알 수 있다. 특정 차들을 꺼내던지, 일련의 차들을 모두 뒤로 빼야하는데 이는 굉장이 오버헤드가 큰 작업이다. 누군가가 양보를 한다면, 쉽게 해결 할 수 있다. 그래서 컴퓨터 내에서도 희생을 하지 않고 자원을 가지고 잇으면서 내가 가지지 못한 자원은 요청하고, 또 상대방도 내가 요청한 자원을 가지고 있으면서 내가 가지고 있는 자원을 요청한다면 서로 원하는 자원을 영원히 갖지 못하는 상태에 빠지게 된다.

그래서 위의 그림에서 자신이 가진 자원과 요구하는 자원은 무엇인가? 가진 자원은 자신이 지금 가는 길목이고 요구하는 자원은 통과하길 원하는 길목일 것이다. 차가 여러대 있지만 같은 열에 있는 차들을 일련의 프로세스로 보자. 그러면 위와 같은 상황이 된다. 어느누구도 양보를 하지 않으면 더이상 진행되지 않는 상태이다.

Deadlock

일련의 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태

Resourse

여기서 자원이라 함은 하드웨어 자원일 수도, 소프트웨어 자원일 수도 있다.

예

하드웨어

시스템에 2개의 tape drive가 있고 프로세스 P1, P2가 있다고 가정하자
프로세스는 하나의 tape drive에서 자원을 읽어 다른 tape drive에 쓰는 작업을 한다. 따라서 하나의 프로세스가 두개의 tape drive를 점유해야한다.
이때 P1과 P2 각각이 하나의 tape drive를 보유한채 다른 하나를 기다리고 있다면 어느 누구도 진행이 안되는 상태에 빠진다. 이러한 경우는 하드웨어 자원의 경우이다.

소프트웨어

이전에 process synchronization에서도 언급했던, semaphore에서도 deadlock이 발생할 수 있다.
P0이 S를 획득한 다음에 CPU를 빼앗겼고, P1은 Q를 획득한 다음 S를 얻으려 하는데 이미 P0가 가지고 있으니 P0가 내려 놓을 때 까지 획득하지 못한다. P0로 다시 CPU가 돌아가도 마찬가지이다.

보통 자원을 사용하는 절차는 4가지로 나누어진다.
1. 자원을 요청하는 단계
2. 자원을 획득하는 단계
3. 자원을 사용하는 단계
4. 자원을 반납하는 단계

Deadlock 발생의 4가지 조건

dead lock이 발생하기 위해선 아래의 4가지 조건을 모두 만족해야한다.

Mutual exclusion

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

우리 말로는 상호배제라고 한다. 자원을 일단 얻었으면 독점적으로 사용한다는 것이다.
다 사용했을 경우에 반환은 할 수 있다.

No preemption

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

빼앗기지 않는다 것이다. 우리말로는 비선점이라고 한다. 자원을 가지고 있는데 가진 자원을 빼앗길 수 있다면 dead lock이 발생하지 않는다.

Hold and wait

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

내가 가진 자원은 내놓지 않으면서 추가적인 자원을 요청해 기다린다.

Circular wait

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

순환 대기라고 한다. 필요로 하는 자원들이 꼬리에 꼬리를 무는 것이다. 서로가 가진 자원을 기다리면서 사이클을 형성하는 경우이다. 위에서 보았던 사거리 그림에서도 사이클을 확인할 수 있다.

프로세스 P0,P1,...,Pn이 있을 때 P0은 P1의 자원을 기다리고, P1은 P2의 자원을, P2는 P3의 자원을 .. 결국엔 Pn이 P0의 자원을 기다리는 형태이다.

조건들이 구분이 잘 되지 않을 수 있으나. 빼앗기는 것과 내어놓는 것을 구분해야한다. 빼앗는 것은 비자발적이고, 내어놓는 것은 자발적인 것이다.

Deadlock이 발생했는지를 알아보기 위해 자원할당 그래프를 그려본다.

그림의 동그라미는 프로세스를 나타내며, 사각형은 자원을 나타낸다. 화살표는 두가지 종류가 있다.

• 자원 -> 프로세스
  - 해당 자원이 지금 프로세스에 속해있음을 의미한다.

• 프로세스 -> 자원
  - 프로세스가 자원을 요청하는 것이다.
  - 요청했지만, 아직 획득하진 못한 단계이다.
  사각형안의 점들은 자원의 인스턴스(수)를 얘기하는 것이다. 따라서 사각형내에 점이 두개라면 해당 자원은 인스턴스를 두개 가진 것이다.

• P1 : R2자원 보유, R1 자원 요청

• P2 : R1,R2 자원 보유, R3 자원 요청

• P3 : R3 자원 보유

화살표를 따라가보면서 사이클이 있는지 확인하면 위의 그림에선 Deadlock이 발생하지 않는 것을 볼 수 있다.

하지만 이 그림을 살펴보자.

• T1 → R1 → T2 → R3 → T3 → R2 → T1
• T2 → R3 → T3 → R2 → T2

사이클이 두개 있는 것을 확인할 수 있다.
하지만 사이클이 있다고해서 모두 Dead lock에 걸리는 것일까? 아니다. 자원당 하나의 인스턴스를 가지고 있다면 dead lock이 맞다. 하지만 자원하나에 여러 인스턴스가 존재한다면 무조건 Dead lock은 아니다. 따라서 다른 조건도 따져봐야한다.

R2 자원의 인스턴스가 두개이지만 둘 다 이미 프로세스에 각각 할당되어 있고, 할당된 프로세스들은 다른 자원을 추가로 요청하고 있으므로 절대 내어놓지 않을 것이다. 따라서 dead lock 상황이다.

위 그림에서도 T1 → R1 → T3 → R2 → T1 로 사이클이 존재한다.
하지만 사이클과 관련된 자원 R1, R2에 인스턴스가 각각 2개이다. 각 인스턴스는 프로세스가 가지고 있지만, 가지고 있는 프로세스인 P2, P4가 다른 자원을 요청하지 않기 때문에 쓰고 나서 반납할 것이다. 따라서 반납하고 나면 자원이 여유로워지므로 다른 프로세스가 사용할 것이다. 따라서 dead lock 이 아니다.

dead lock을 처리하는 방법

Deadlock Prevention, Deadlock Avoidance는 Deadlock이 생기기 이전에 미연에 방지하는 것이다.
Deadlock Detection and recovery, Deadlock Ignorance는 Deadlock이 생기도록 놔두고
위로 갈수록 더 강한 방법이다.

Deadlock Prevention

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

네가지 조건 중 하나를 원천적으로 차단해 Deadlock에 들어가지 못하게 하는 것이다.
Deadlock을 원천적으로 막을 순 있지만, 자원에 대한 이용률이 낮아지고, 전제 시스템의 성능이 나빠지고 starvation 문제가 생길 수 있다.
생기지도 않은 Deadlock을 우려해 제약조건을 많이 걸어놓기 때문에 비효율적이다.

Mutual exclusion

공유해서는 안되는 자원의 경우 반드시 성립해야 한다.

이 조건은 막을 수 있는 조건은 아니다. 한번에 여러 프로세스를 공유할 수 있는 자원이라면 애초에 Deadlock이라는 이야기가 나오지도 않았을 것이다. 그래서 이 조건은 한번에 하나의 프로세스만 사용할 수 있는 자원이라면 우리가 배제할 수 있는 조건은 아니다.

No preemption

가지고 있는 자원을 뺏어올 수 없기 때문에 Deadlock이 생긴다. 따라서 자원을 빼앗을 수 있게 하면 된다.
CPU는 preemptive 스케줄을 사용했다. CPU를 받고 나면 영원히 반납하지 않을 수 있기 때문에 timer를 둬 특정 프로세스가 CPU를 독점하지 못하도록 했다. 그래서 CPU는 항상 빼앗아올 수 있었다. 이러한 자원은 Deadlock이 걸리지 않는다.

자원을 아무렇게나 빼앗아 오면 문제가 생길 수 있다. 하지만 CPU나 memory는 어떻게 쉽게 빼앗아 오는 것일까? 자원의 현재 사용상태를 save하고 restore할 수 있기 때문이다. 어떤 자원은 중간에 빼앗아오면 하던일에 문제가 생길 수 있다. 그래서 이러한 자원들은 preemption을 사용하기 어렵다.

Hold and wait

프로세스가 자원을 요청할 때 다른 어던 자원도 가지고 있지 않아야 한다.

내가 가진 자원은 내놓지 않으면서 추가적인 자원을 요청해 기다리기 때문에 Deadlock생긴다.
자원을 기다려야하는 상황에서는 자원을 보유하고 있지 않으면 되는 것이다.
그래서 이를 해결하는 방법은 두가지가 있다.

• 프로세스가 시작될 때 프로세스가 평생에 필요로 하는 자원을 모두 할당받게 한다.
  • 종료 될 때 모든 자원을 반납하고, 중간에 추가적인 자원을 필요로 하지 않으므로 Deadlock이 생기지 않음
  • 하지만 매 시점마다 필요로 하는 자원이 다르기 때문에 특정 자원이 필요하지 않은 상황에서도 해당 자원을 가지고 있게 되면 비효율적인 자원 소모가 이루어진다.
• 필요할 때 자원을 그때그때 할당받는다. 하지만 자원을 요청할 때 가지고 있는 자원을 모두 내려놓고 대기한다.
  • 자진해서 반납
  • 그러면 대기하고 있던 누군가가 자원을 사용할 수 있다.

Circular wait

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

필요한 자원들이 꼬리에 꼬리를 물고 있으면서 사이클이 형성된 경우이다.
이걸 막기 위해선 자원마다 순서를 매기는 것이다.
내가 1,3,5번 자원이 필요할 때 숫자가 낮은 것 부터 획득할 수 있게 한다. 그러면 1번 자원을 획득해야 3번 자원을 획득할 수 있게 하면 Deadlock이 생기지 않는다.
왜냐하면 누군가는 1번 자원을 가지고 있으면서 3번 자원을 기다리고 누군가는 3번 자원을 가지고 있으면서 1번 자원을 기다려야 Deadlock인데, 1번과 3번 모두가 필요하면 모두가 1번 부터 획득해야하기 때문이다.
따라서 사이클이 생길 우려가 없다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해 Deadlock의 가능성이 없는 경우에만 자원을 할당
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

prevention과 마찬가지로 미연에 Deadlock을 방지하는 방법이다.
자원을 요청하는 것에 대해 부가적인 정보를 이용해 자원이 있지만 Deadlock일 가능성이 전혀 없는 경우에만 자원을 할당
보통은 어떻게 동작하냐 ?
프로세스가 시작해서 종료될 때 까지 사용하려는 자원의 수나, 종류가 다 다르다. 그렇기 때문에 Deadlock avoidance는 프로세스가 시작될 때 프로세스가 평생 쓸 자원의 최대량을 알고 있다고 가정하고 Deadlock을 피해간다. 평생 쓸 자원을 알고 있기 때문에 자원을 할당해줬을 때 Deadlock이 생길 수 있다고 판단되면 자원을 할당해주지 않는 것이다.

두가지로 나눠서 생각할 수 있다. 자원의 인스턴스가 하나씩밖에 없을 때는 그래프를 통해 Avoidance를 할 수 있다. 자원의 인스턴스가 자원당 여러개가 있다면 Banker's Algorithm을 사용할 수 있다.

자원의 인스턴스가 하나만 있는 경우

자원이 두개 있다. 점선 화살표는 프로세스 -> 자원, 이 프로세스가 평생에 적어도 한번은 이 자원을 한번은 사용할 일이 있음을 의미한다. Deadlock Avoidance는 프로세스가 시작될 때 프로세스가 평생에 사용할 자원들을 미리 다 declare를 하고 그걸 이용해 Deadlock을 피해갈 수 있는 방법을 사용한다고 했었다. 그래서 점선 화살표를 이용해 지금은 사용하지 않지만 미래에 사용할 자원을 표시해놓는 것이다.

첫번째 상황에서 P2가 R2를 요청하면 두번째 그림과 같이 된다. 이때 R2는 아무도 가지고 있지 않기 때문에 P2가 가지고 있게 된다. 따라서 마지막 그림과 같은 상황이 된다. 최종적으로 마지막 상황은 Deadlock이 아니다. 왜냐하면 P1이 R2를 미래에 요청할 수 있지만, 지금은 요청하지 않은 상태이기 때문에 사이클이 형성되지 않는다. 실제 요청을 하는 시점에 점선이 실선으로 바뀌며 Deadlock에 걸린다.

마지막 그림은 Deadlock이 아니지만 (P1이 R1을 사용하고 반납하면 P2가 R1을 사용하면 되기 때문이다.) Deadlock Avoidance는 최악의 상황을 생각한다. 그래서 두번째 그림의 상황에서 R2를 P2에게 할당하게 되면 세번째 그림이 된다. 따라서 Deadlock의 가능성이 있는 상황이 되므로 R2를 할당하지 않는 것이다. 그래서 R2를 아무도 가지고 있지 않은데도 아무도 가지지 못하는 상황이 생긴다. 이후에 P1이 R2를 요청하면, 사이클이 생길 가능성이 전혀 없기 때문에 R2를 할당해준다. P1이 R2를 다 사용하고 반납하면 그 이후에는 P2가 R2를 할당받아도 사이클이 생기지 않기 때문에 P2가 R2를 할당 받는다.

자원당 인스턴스가 여러개 있는 경우 (Banker's Algorithm)

5개 프로세스 -> P0,P1,P2,P3,P4
3개 자원 -> A,B,C 는 각각 10,5,7개의 인스턴스를 가지고 있다.

Deadlock Avoidance는 평생 사용할 자원의 최대량을 알고 있다고 가정한다고 했다. 이때 이 최대량이 Max이다.
Allocation : 할당 받은 자원
Max에서 Allocation을 빼면 Need가 되는 것이다.
Available : 추가로 할당할 수 있는 양(남은 가용 자원)
자원을 줄 수 있지만 문제가 생길 가능성이 있으면 주지 않는 방법이다.

원래 (10,5,7)의 인스턴스가 있지만 이미 할당된것 (0+2+3+2+0, 1+0+0+1+0, 0+0+2+1+2)를 빼면 가용자원은 (3,3,2)가 남는다. 이때 각 프로세스에 자원을 할당할 수 있는지 확인해보자.

P0
P0이 필요한 데이터는 Max(7,5,3)에서 Allocation(0,1,0)을 뺀 Need(7,4,3)이다.
하지만 현재 가용 자원은 (3,3,2)이므로 (7,4,3)을 할당할 수 없다. 따라서 P0에는 자원을 할당해주지 않고 넘어간다. (요청을 받아들이지 않는다.)
Max를 지금 당장 요청하지 않고 조금만 요청해 가용자원인 (3,3,2)를 줄 수도 있지만, P0가 Max를 모두 요청해서 이를 받아들이게 되면 문제가 생길 수 있다. 당장은 deadlock이 생기지 않는다. 왜냐하면 P0가 데이터를 대기하는 동안 다른 프로세스가 사용하던 자원을 반납할 수 있기 때문이다. 하지만 Banker's Algorithm은 굉장히 보수적이다. 따라서 본인의 최대 요청을 할 것이라고 가정을 한다.
가용자원으로 처리 가능 -> 요청 받아들임
가용자원으로 처리 불가능 -> 요청 무시
P0가 지금 당장은 Max가 아닌 A를 하나만 달라고 할수도 있지만, Max를 달라고 할 위험성이 있기 때문에 Max를 모두 처리하지 못한다면 요청을 받아들이지 않는다.

P1
P1의 need가 (1,2,2)이므로 available인 (3,3,2)가 모두 커버 가능하다. 필요한 만큼 할당이 되었다면, 다시 반납할 것이므로 이제 available은 Allocation(2,0,0)을 더한 것이 된다. 즉, available = (5,3,2)이다.
왜 요청을 받아들이는가? 최대 요청보다 더 요청할 일은 없는데, 최대 요청을 모두 커버할 수 있기 때문이다. 따라서 언젠가는 반환할 일만 남았다.

P2
P2의 Need가 (6,0,0)이므로 가용자원인 (5,3,2)이 커버하지 못한다. 그러므로 요청을 받아들이지 않는다.

P3
Need가 (0,1,1)이므로 가용자원 (5,3,2)으로 커버할 수 있다. 따라서 이제 가용자원은 (7,4,3)이 된다.

P4
Need가 (4,3,1)이므로 가용자원 (7,4,3)으로 커버할 수 있다. 따라서 이제 가용자원은 (7,4,5)이다.

P0
Need가 (7,4,3)이므로 가용자원 (11,7,4)로 커버할 수 있다. 따라서 이제 가용자원은 (7,5,5)이다.

P2
Need가 (6,0,0)이므로 가용자원 (7,5,5)로 커버할 수 있다. 따라서 이제 가용자원은 원래 인스턴스인 (10,5,7)이다.

따라서 sequence<P1,P3,P4,P2,P0>가 존재한다.

이러면 deadlock은 생기지 않으나, 굉장히 비효율적이다. 왜냐면 요청을 안할지도 모르는데 혹시나 최대 요청을 할 것을 대비해 자원이 있는데도 요청을 받아들이지 않기 때문이다. 특정 프로세스의 요청을 가용자원으로 충족하지 못한다고 하더라도 다른 프로세스들이 반납할 수도 있으므로 알 수 없는 것인데 이 알고리즘에서는 항상 최악의 경우를 생각한다.

항상 safe한 상태만 생각한다.
가용자원이 max 자원을 만족시켰기 때문에 해당 프로세스는 언젠가 종료될 것이다. 종료되면 가진 자원을 다 내려놓는다. 그렇게 되면 가졌던 자원도 모두 가용자원이 된다. 그래서 이 가용자원을 가지고 최대 요청을 충족할 수 있는 프로세스에게 주는 것이다. 따라서 프로세스 n개를 현재의 가용자원만으로 처리될 수 있고, 그 뒤의 프로세스는 뱉어낸 자원과 가용 자원으로 처리될 수 있다. 이런식으로 끝까지 sequence가 한가지 존재한다면 안전한 상태인 것이다. 이러한 상태를 safe 상태라고 한다. 그래서 모든 프로세스가 끝까지 수행되는 것을 보장하는 상태이다.

P0가 A를 하나 요청하면 A가 남아있으니까 줄 수 있다. 문제가 되느냐 ? 문제가 되는 건 없다. safe한 상태에서 가용자원만으로 충족되지 않는 프로세스에게 자원을 준다고 해서 deadlock인 것은 아니다. 자신이 가지고 있는 것을 내려 놓지 않고 요청하고 대기만 하면 deadlock이다.
그래서 굉장히 안전하게 가자는 알고리즘이다.

결론적으로 미리 deadlock을 막는 방법이다.

Deadlock Detection and recovery

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

시스템이 느려지거나 할 때 혹시나 Deadlock이 생긴 것은 아닌가 detection을 하고 있으면 recovery하는 것이다.

Deadlock Detection

자원당 인스턴스가 하나뿐인 경우에는 자원할당 그래프를 이용해 detection 한다.
자원 할당 그래프를 오른쪽 그래프와 같이 자원은 빼버리고 프로세스끼리만 연결해 간단하게 그릴 수 있다. 왜냐하면 사이클이 나오는 상황은 둘 다 똑같기 때문이다.
그렇다면 오른쪽 그래프에서 사이클을 찾는 오버헤드?
프로세스가 n개가 있다면 O(n^2)시간이 걸린다. 왜냐하면 프로세스가 n개 있기때문에 다 화살표를 따라가보면 된다. 프로세스가 n개이면 화살표는 최대 n(n-1)개가 있다. 모든 점을 다 탐색해보는 것이기 때문에 DFS,BFS와 같다고 할 수 있다.

자원당 인스턴스가 여러개일 경우에는 아래와 같이 sequence를 확인해 detection할 수 있다.

여기선 Max에 대해 고려하지 않고 현재의 요청인 Request에 대해서만 고려한다.
위의 sequence를 확인해보면 <P0,P2,P3,P1,P4>가 존재한다.

만약 P2가 자원 C를 하나 더 요청하면 어떻게 될까?
dead lock이 걸린다 ! 왜냐하면 P0를 커버하고 나서 모든 프로세스에 대해 커버하지 못하기 때문이다.

그래프를 이용하는 것이 위의 sequence를 확인하는 것의 subset이다. 그래서 인스턴스가 하나여도 sequence를 찾는게 더 간단하다.

Deadlock Recovery

• Process termination

  • Deadlock에 연루된 프로세스들을 사살 -> 한꺼번에 죽인다.
  • Deadlock에 연루된 프로세스들을 하나씩 죽여보는 것이다. -> 하나씩 죽여보고 Deadlock인지 확인하고 Deadlock이 아직도 걸려있다면 또 죽인다.

• Resource Preemption

  • 비용을 최소화할 희생양을 하나 찾아 자원을 뺏는다.
  • safe state로 rollback해 프로세스를 restart하면 Deadlock이 없어진다.
  • 문제는 Deadlock을 없애놨더니 똑같은 패턴이 또 나타날 수 있는 것이다. 즉, 계속 동일한 프로세스가 희생양으로 선정되어 starvation 문제가 생길 수 있다. 그래서 Deadlock이 발생했을 때 수행하는 패턴을 계속 조금씩 바꿔야한다. 따라서 자원을 몇번 뺏겼는지 rollback 횟수도 cost factor에 고려해 자원을 뺏는 방법에 대해 고민해야 한다.

Deadlock Ignorance

Deadlock 을 시스템이 책임지지 않음

Deadlock에 대해 아무것도 하지 않는다. 현대의 운영체제들은 이 방법을 채택하고 있다. 그럼 어떻게 해결하는가? 운영체제가 관여하지 않으면, 사람이 프로세스를 돌리다가 돌아가지 않으면 사람이 해결한다.

Deadlock은 빈번히 발생하는 이벤트가 아니기 때문에, 이를 미연에 방지하기 위해 훨씬 많은 오버헤드를 들이는 것이 현대적인 시스템에서는 비효율적이기 때문에 이를 처리하지 않는다.

Deadlock을 방지, detection을 하는 것이 시스템의 오버헤드를 발생시키기 때문에 Deadlock이 생겨도 그냥 두는 것이다. 따라서 Deadlock이 생기면 시스템이 느려지거나 멈출 것이다. 이땐 사용자가 이를 감지하고 프로세스를 멈추던지 해결을 해야한다. 현대의 운영체제들이 이방법을 채택하고 있다.

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수