OS-Deadlock0509

*복습

- 스케줄러 중 가장 부작용이 적은 것은 FIFO(퍼포먼스 무시, 적은 부작용만 고려)

- CPU 자체가 리소스가 아닌 time quantum이 리소스

 

#Deadlock

- 데드락은 두 개 이상의 프로세스가 각각 다른 프로세스 세트 내에서만 생성될 수 있는 이벤트를 기다리는 상황에서 발생하는 현상. 그러나 해당 이벤트는 결코 발생하지 않을 것이기 때문에 발생한 상태를 말함

- 데드락은 운영체제 설계자들이 직면하는 어려운 문제 중 하나

    > 데드락을 해결하기 위한 다양한 접근 방법을 살펴보면, 해당 접근 방법이 문제를 얼마나 잘 해결하는지와 성능 또는 운영 체제 부담 사이에 트레이드 오프가 있음

- 운영체제는 경쟁하는 프로세스들 사이에서 시스템 자원 분배해야 함

    > CPU cycle - preemptable

    > Memory - preemptable

    > Files - non preemptable

    > I/O devices(printer) - non preemptable

★리소스가 preemptable인지 non-preemptable인지 구분 해야 함

★non-preemptable 리소스만 데드락을 유발하는 리소스들임

- 특정 유형의 자원에 대한 요청은 해당 유형의 어떤 자원이든지 충족시킬 수 있음

    > 메모리에서 100바이트 사용

    > 두 개의 동일한 프린터 중 하나 사용

- 프로세스는 자원을 요청하고 사용한 후 반환

    > 여기서 가정하는 것은 자원이 재사용 가능하며 소모되지 않는다는 것

    > 자원이 현재 사용 불가능한 경우 대기

 

#Deadlock Conditions

- 데드락 발생의 4가지 조건, 동시에 충족해야 함

1. Mutual exclusion(상호 배제): 한 프로세스가 자원 소유시, 다른 프로세스들은 자원을 기다려야 함(동시에 하나의 프로세스만 해당 자원 사용 가능)

2. Hold and Wait(보유 및 대기): 프로세스는 하나 이상의 자원을 보유한 채로 다른 프로세스가 가지고 있는 추가적인 자원을 얻기 위해 대기할 수 있음

3. No preemption(선점 불가): 자원은 자발적으로만 해제 가능, 다른 프로세스나 운영체제가 프로세스에게 자원 해제를 강제할 수 없음

4. Circular wait(순환 대기): 서로 다른 프로세스들이 서로가 가지고 있는 자원을 대기하는 순환적인 관계가 형성돼야 함. 예를 들어 P0는 P1이 가지고 있는 자원을 대기하고, P1은 P2가 가진 자원을 대기, P(n-1)은 Pn이 가진 자원을 대기, Pn은 P0가 가지고 있는 자원을 대기.

 

#Resource-Allocation Graph

- 데드락 조건은 자원 할당 그래프(Resource Allocation graph, RAG)라 불리는 유향 그래프로 모델링 가능

> 2종류의 노드:

1. box - 자원을 나타냄. 자원의 인스턴스는 상자 내에 점으로 표시

2. circle - 스레드/프로세스를 나타냄

> 2종류의 유향 간선

1. request edge - 프로세스에서 자원으로의 간선. 프로세스가 자원을 요청하고, 자원을 획득하기 위해 대기하고 있는 것을 나타냄 -> 요청이 발생하면 request edge가 추가됨.

2. assignment edge(할당 간선) - 자원 인스턴스에서 프로세스로의 간선. 프로세스가 해당 자원 인스턴스를 소유하고 있음을 나타냄 

- 요청이 충족되면 요청 간선은 할당 간선으로 변환

- 프로세스가 자원을 해제하면 할당 간선은 삭제

★resource: 추상적 개념. CPU, 메모리, 디스크 드라이브, 프린터 등

★Instance: 실제로 시스템에 존재하고 사용될 수 있는 개체. resource 내에 여러개의 instance 존재 가능. CPU 코어, 디스크 드라이브 등

 

 

#Interpreting a RAG with Single Resource Instances

- 그래프에 사이클이 없다면 -> 데드락 없음

- 그래프가 사이클이 있다면, 데드락 존재

* 단일 자원 인스턴스의 경우, 사이클은 데드락의 필요 조건이자 충분 조건

 

#Dealing with Deadlock

- Ostrich Approah(타조 접근법): 문제를 무시하고 머리를 모래 속에 숨기는 접근법

- Deadlock prevention: 4가지 데드락 조건 중 하나를 제거하여 데드락이 발생 하지 않도록 예방

- Deadlock detection algorithms - 데드락 발생 시 감지하는 알고리즘

- Deadlock recovery algorithms - 데드락 해제 알고리즘

- Deadlock avoidance algorithms - 현재 사용 가능한 자원, 각 스레드에 할당된 자원, 가능한 미래의 요청을 고려항여 데드락을 발생시키지 않는 요청만 충족시키는 알고리즘

 

#Deadlock Prevention

- 기본 아이디어: 데드락의 4가지 조건중 하나가 성립하지 않도록 보장

 

1. Mutual exclusion: 동시에 한 번에 하나의 프로세스만 해당 자원을 사용 가능

    > 공유할 수 없는 자원에 대해서는 상호 배제 피하기 어려움

        > 프린터 및 다른 I/O 장치

        > 파일

    > 그러나 많은 자원은 공유할 수 있으므로, 해당 자원에 대해서는 데드락을 피할 수 있음

        > 읽기 전용 파일

    > 프린터의 경우, 스풀링을 사용해 상호 배제 피할 수 있음

        > 이렇게 하면 프로세스가 물리적인 프린터를 기다릴 필요가 없음

 

2. Circular wait

    > 데드락을 피하기 위해, 모든 자원에 대해 전체적인 순서를 부여하고, 프로세스가 그 순서대로 자원을 요청하도록 요구

        > 예를 들어, 디스크 드라이브 -> 프린터 -> CD-ROM 순서로 설정

        > P1은 디스크 드라이브를 요청한 후에 프린터 요청

        > P2는 디스크 드라이브를 요청한 후에 프린터 요청

        > P2는 프린터를 요청한 후에 디스크 드라이브를 요청하지 않도록 해야 데드락 피할 수 있음

    > 순서는 일반적으로 자원을 획득하는 논리적인 순서에 맞춰 설정돼야 함

        > 프로세스가 모든 자원을 해제하고 요청 순서를 처음부터 다시 시작하도록 허용할 수 있음

        > 또는 프로세스가 각 자원의 총 개수를 한 번의 요청으로 요청하도록 강제할 수 있음

 

3. No preemption

- Avoid를 위해 preemption 허용

    > 만약 프로세스 A가 사용할 수 없는 자원을 요청하면, 누가 해당 자원을 소유했는지 검사

        > 만약 B가 소유중이고, 추가적인 자원을 기다리고 있다면, A가 선점

        > 그렇지 않으면 A는 대기해야 함

            > 대기하는 동안 A가 현재 가지고 있는 일부 자원이 선점될 수 있음

            > 새로운 자원과 선점된 자원을 함께 획득할 때만 A가 깨어날 수 있음

        > 만약 프로세스가 할당할 수 없는 자원을 요청하면, 해당 프로세스가 가지고 있는 모든 자원이 선점됨

            > 요청한 모든 자원을 획득할 수 있을 떄까지만 프로세스가 깨어날 수 있음

        > 이 방법은 상태를 저장하고 복원할 수 있는 자원에만 적용될 수 있음(ex: 메모리, 프린터는 불가능)

 

4. Hold and wait

- Avoid위해, 프로세스가 언제 자원을 요청하더라고, 다른 자원을 hold하지 않는다고 보장

    > 프로세스 실행 시작 시 모든 자원을 한번에 요청

        > 무한루프 프로세스는?

    > 어떤 지점에서든 모든 자원을 한 번에 요청

    >  새로운 자원을 얻기 위해 현재의 모든 자원을 해제하고, 새로운 자원과 이전 자원을 한 번에 획득하려고 시도

- 미리 어떤 자원을 요청해야 할 지 알기 어려움

- 낭비적(Wasteful), 자원을 소모하고 자원 활용율을 줄임

- Starvation 발생 가능

 

* knot : 사이클 개수만큼 인스턴스를 가지면서, 그 사이클에 모두 관여하는 리소스

#Interpreting a RAG with multiple resource instances

- 그래프에 사이클이 없으면, 데드락 없음

- 그래프에 사이클이 있으면 데드락 있을 수도 있음

- multiple resource instances에서는 사이클이 데드락의 필요조건이지만 충분조건은 아님

 

- knot(cycle 포함)이 존재하면, 데드락 존재

이 그림에서 knot은 r3, 그래프에 사이클 2개, r3의 인스턴스 2개. r3는 두 사이클 모두에게 관여함

- knot이 없으면, 데드락 없음

사이클이 1개뿐. knot이 없음

* knot : 사이클 개수만큼 인스턴스를 가지면서, 그 사이클에 모두 관여하는 리소스

* 예를 들어, 프로세스 P1과 P2가 자원 R1의 인스턴스를 요청하는데, 이미 다른 프로세스 P3에게 할당되어 있을 때, 노트가 형성됩니다. 이 경우, P1 및 P2에서 R1에 대한 요청 엣지가 노트로 향하게 됩니다. 이는 자원 인스턴스가 현재 다른 프로세스에 할당되어 있으므로, P1 및 P2는 R1의 인스턴스를 기다려야 함을 나타냅니다.

 

#Deadlock Detection(multiple resources of each type)

- Coffman 알고리즘

- n 프로세스, m 리소스 타입

    > Exsisting Resources 벡터는, 존재하는 타입의 자원

    > Available Resources 벡터는, 사용 가능한 타입의 자원

    > i-th 연속적인 최근 할당된 matrix는 process i 에게 할당된 타입의 자원

- 각 행이 1개의 프로세스, 열은 리소스의 종류

- 누구의 프로세스가 충족되었나?

1. P1: no - CD ROM 

2. p2: no - no printer

3. P3: yes -> A=(2 2 2 0) 확보, 수행 후 반환 -> (0 1 2 0)이 최근 할당됐고, (2 1 0 0)요청하고 확보했으므로 (2 2 2 0)

-> P3 종료 후 에도 cd롬은 0이므로 p1은 불가, p2는 가능 , 반납된 ( 2 2 2 0) + p2할당 (2 0 0 1) -> p2 A=(4 2 2 1)

-> p2종료 후 p1 수행 -> (0 0 1 0)(p1할당) + (4 2 2 1)(반납된 리소스) = A = (4 2 3 1) == 최초 exsisting resources

 

#After Deadlock Detection: Deadlock Recovery:

- 얼마나 자주 deadlock detection 해야 하는가?

    > 모든 리소스 요청 이후?

    > 그거보다 덜: 매 시간마다 또는 자원 이용률 낮아질 때

- 데드락을 감지하면?

    > 프로세스 종료 

        > 모든 데드락된 프로세스

        > 데드락 해결 될 때까지 한번에 한 프로세스

            > 어떤 프로세스 종료하나

            > 가장 많은 자원을 보유한 프로세스

            > 더 적은 비용이 드는 프로세스: (사용된 CPU time, 필요한 CPU time), 사용된 자원, 필요한 자원

        > 스케줄링과 비슷한 선택 -> 프로세스 종료가 가능한가?

            > 많은 계산이 수행됐을수도 -> 이상적이지 않음. 하지만 종료시키기는 가능

            > 파일 업데이트, I/O 작업 수행했을 수도 -> 종료 불가

- 덜 극적인 방법은?

    > preempt resources

        > 코스트에 따라서 CPU 스케줄링과 비슷하게 한번에 하나씩 종료시킨다

    > rollback 가능한가?

        > preempt resources: take them away

        > rollback: 안전한 상태로 돌리고, 거기부터 재시작

            > OS가 체크포인트 자주 저장해야함, write its state to a file

        > 시작점으로 롤백 가능하지만, 데드락을 해제하는 것도 방법

            > 바로 직전으로 돌아가서 리소스 대기

    > Avoid starvation

        > 자주 희생되는 프로세스에게 발생 가능

        > 같은 프로세스를 계속 죽이지 말아야 함