데드락(2022.04.03 수정)

728x90

Deadlock

정의

일련의 스레드들이 서로가 가진 자원을 기다리며 block 된 상태
자원에는 하드웨어 자원, 소프트웨어 자원이 있다.
- 하드웨어
  - A -> B 디스크에 카피하고 싶다. 그러면 둘 다 점유해야 하지만 각각 하나씩 점유하고 있으면 어느 누구도 진행이 되지 않는 데드락 상태에 도달하게 된다.
- 소프트웨어
  - memory, 세마포어
  - 락을 거는 세마포어 두 개를 얻어서 실행시키고 싶다. 그러나 각각 하나씩만 할당받으며 서로의 자원을 원할 경우

프로세스가 자원을 사용하는 절차(4단계)

자원 요청
- 요청이 즉시 허용되지 않으면(mutex 락을 다른 스레드가 가지고 있는 경우), 요청 스레드는 자원을 얻을 때까지 "대기"
자원 획득
자원 사용
- 자원이 mutex 락이라면, 스레드는 임계구역에 접근할 수 있음
자원 반납

자원의 요청과 반납의 예

파일의 open(), close()
세마포의 wait(), signal()
mutex 락의 acquire(), release()

Livelock(mutex 락 사용)

Liveness 장애의 한 예시
교착 상태와 유사하지만 "시도 방법" 이 다름
- 일반적으로 스레드가 실패한 작업을 동시에 재시도할 때 발생!!
thread1이 mutex1을 가지고, thread2가 mutex2를 가지고 있음
thread1은 mutex2를 획득하려고 "시도" 하지만 실패
- 자신이 가지고 있던 mutex1을 반납하고 다시 mutex1을 얻고 또, mutex2를 획득하려고 시도
thread2는 mutex1을 획득하려고 "시도" 하지만 실패
- 위와 반대상황
즉, 락을 얻지 못하고, 각자의 락을 해제한 후 동일한 행동을 "무한정 반복"

	//Thread1 실행
        while (!done) {
            mutex_lock(&first_mutex);
            if(mutex_trylock(&second_mutex)){

                //work

                mutex_unlock(&second_mutex);
                mutex_unlock(&first_mutex);
                done = 1;
            }
            else{
                mutex_unlock(&first_mutex);
            }
        }
        
        //Thread2 실행
        while (!done) {
            mutex_lock(&second_mutex);
            if(mutex_trylock(&first_mutex)){
                
                //work

                mutex_unlock(&first_mutex);
                mutex_unlock(&second_mutex);
                done = 1;
            }
            else{
                mutex_unlock(&second_mutex);
            }
        }

데드락 발생의 4가지 조건(4가지 조건을 모두 만족해야 데드락이 발생)

mutual exclusion(상호 배제)

자원은 무조건 독점적으로 사용
하나의 스레드만이 자원을 사용한다
다른 스레드가 자원을 요청할 시 "요청 스레드"는 자원이 방출될 때까지 지연되야함

no preemption(비선점)

프로세스는 자원을 스스로 내놓을 뿐, 강제로 뺏기지 않는다.

hold and wait(보유 대기)

자원을 가진 스레드가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있음

circular wait(순환 대기)

자원을 기다리는 스레드 간에 사이클이 형성되야함
P0은 P1이 가진 자원 기다림, P1은 P2, Pn-1은 Pn, Pn은 P0이 가진 자원을 기다림

자원 할당 그래프

데드락이 발생했는지 알 수 있는 방법으로 "자원 할당 그래프"가 있다

사각형은 자원
- 그 안에 점들은 자원 수(인스턴스)
동그라미는 프로세스

화살표 종류 2가지

프로세스 -> 자원
- 해당 프로세스가 가리키는 자원을 요청한 상황. 즉, 아직 획득하지 못함
- 요청 간선
- 요청 간선은 자원 "박스"를 가리킴
자원 -> 프로세스
- 해당 자원이 지금 프로세스에 속해있다
- 할당 간선
- 할당 간선은 "점"에서 프로세스로 향해있음

그림으로 설명

T1은 R2의 인스턴스 한 개 점유, R1의 인스턴스를 요청하면서 대기
T2는 R1, R2의 인스턴스 한 개 점유, R3의 인스턴스를 요청하면서 대기
T3는 R3의 인스턴스 한 개 점유

사이클의 유무에 따른 데드락 발생 여부
- 사이클이 존재하지 않는다면 교착 상태가 발생할 수 없음
- 사이클이 존재한다면 교착 상태가 발생할 수 있음
  - 사이클이 존재한다면 "무조건" 교착 상태가 있는 것이 아니다!!!
  - 만약 각 자원 유형이 하나의 인스턴스만을 가지면 하나의 사이클은 교착 상태가 발생한 것!
  - 각 자원 유형이 여러 개의 인스턴스를 가지면 사이클이 반드시 교착 상태가 발생한 것이 아님!

데드락 처리 방법

Deadlock Prevention
- 자원 할당 시 deadlock의 4가지 필요조건 중 어느 하나를 만족시키지 않게 함
Deadlock Avoidance
- 자원 요청에 대한 정보를 이용하여 deadlock 가능성이 없는 경우에만 자원 할당
Deadlock Detection and recovery
Deadlock Ignorance

1, 2번은 데드락이 생기지 않게 "미연의 방지"를 하는 것이다.

3,4번은 데드락이 생기도록 놔둔다.

3번은 시스템이 느려졌을 때 데드락을 의심하고, detection 하면서 발견되면 recovery 한다.

4번은 데드락에 대해 OS가 아무 조치도 취하지 않는다.

프로그래머가 프로세스를 죽이든지 알아서 해결하는 것이다.
데드락은 자주 발생하는 것이 아니기 때문에 미연의 방지하기 위해서 훨씬 더 많은 오버헤드를 가지는 것이 비효율적이다. 따라서 4번 방법을 주로 사용한다.

prevention 과 avoidance의 차이

prevention
- 코드레벨(컴파일 타임)에 없애는게 목표
avoidance
- 실제로 발생할 상황에서 어떻게 하면 발생을 늦출 수 있을까?
- 즉, 런타임 때 데드락을 피하는 것

Deadlock Prevention

mutual exclusion
- 막을 수 있는 조건이 아니다.
- 만약에 자원을 한 번에 여러 프로세스가 공유할 수 있었다면 애초에 deadlock이 발생하지 않았을 것
hold and wait
- 어떤 스레드가 시작될 때, 스레드가 평생에 필요로 하는 자원을 모두 할당받게 함
  - 중간에 필요한 자원이 없게 됨(wait 과정은 없고 hold 과정만 존재)
  - 그러나 스레드가 종료될 때까지 모든 자원을 보유하고 있으므로 자원에 대한 비효율성 엄청 커짐
  - hold를 막는 것
- 스레드가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있음
  - hold 한 자원이 있는데 자원을 wait 하는 상황이 오면 hold 한 자원을 다 뱉어놓고 wait 한다
  - 자진해서 반납함으로써 문제를 해결
  - 자원이 할당되었지만 장기간 사용하지 않을 수 있기 때문에 자원 이용률이 낮을 수 있음
    - 전체 실행 시간 동안 mutex 락이 할당되었지만 짧은 시간동안만 수행하지만, 스레드가 끝날 때까지 mutex 락을 가지고 있음
  - 인기 있는 자원을 여러 개 필요한 스레드는 필요한 자원 중 적어도 하나는 항상 다른 스레드에 할당되므로 무한정 대기해야할 수 있음
- 수정
- 질문 : 결국 두 방법의 차이는 리소스를 부분적으로 사용할 수 없고, 있고의 차이인가?
- 둘다 궁극적인 목표는 부분적으로 이용하고 부분적으로 반납하는 것을 없애려고하는 것이다,,
- 둘다 궁극적인 목표는 hold하면서 wait를 하는 것을 막는 것이다.
no preemption
- 자원을 뺏을 수 있게 하면 데드락이 생기지 않게 된다.
- 현재 스레드가 즉시 할당받을 수 없는 자원을 요청하면 현 스레드가 가지고 있는 자원은 "선점"될 수 있음
- CPU나 메모리는 자원의 사용형태를 save 하고 restore 할 수 있기 때문에 아무 때나 뺏을 수 있음
- 하지만 어떤 자원은 중간에 뺏어오면 하던 일이 다 엉망이 돼서 문제가 생길 수 있음(선점을 하면 안 되는 자원이 존재)
  - 예로 mutex 락과 세마포 같은 자원에는 적용될 수 없음
circular wait
- 자원의 순서를 정해놓는다. 즉, 자원마다 번호를 매긴다.
- 예를 들어 내가 1, 3, 5번 자원이 필요하다면 낮은 번호의 자원을 획득해야만 그다음 자원을 얻을 수 있다.
문제점
- 데드락을 원천적으로 막을 수 있지만 자원 이용률이나 전체 시스템 성능(총처리율) 및 starvation 문제가 발생
- 생기지도 않을 데드락을 미리 생각해서 제약조건을 달아 놓기 때문에 비효율적

Deadlock avoidance

프로세스가 시작될 때, 해당 프로세스가 사용할 자원의 최대량을 알고 있다고 가정하여 데드락을 회피
프로세스가 자원 요청했을 때, "데드락 발생 가능성"이 있다면 자원의 여분이 있음에도 불구하고 할당하지 않음
자원 당 인스턴스의 개수에 따른 해결 방법
- 인스턴스가 하나만 존재한다면 자원 할당 그래프를 이용해서 피할 수 있음
- 여러 개라면 "뱅커스 알고리즘"을 통해 피할 수 있음

안전 상태(Safe State)

스레드들이 요청하는 모든 자원을 어떤 순서로든 할당해줘도 데드락이 발생하지 않는 상태를 안전 상태라 함
- 시스템이 "안전 순서"를 찾을 수 있다면 안전 상태라 함
안전 상태이면 데드락이 발생하지 않음
불안전 상태이면 데드락이 발생할 수 있음!
- 이 말은, 발생할 수도, 발생하지 않을 수도 있다는 말임

자원 할당 그래프 알고리즘

자원 유형마다 단 한개의 인스턴스만을 가질 경우 자원 할당 그래프 알고리즘을 통해 데드락을 파악할 수 있음
앞서 배운 자원 할당 그래프에서 "예약 간선(claim edge)"을 추가함
- 예약 간선은 미래에 스레드가 자원을 요청할 것이라는 의미임
- 여기서 자원을 "요청"하면 그대로 요청 간선으로 변환됨 ( T1 -> R1 )
- 자원을 반납할 시 "할당 간선"은 다시 "예약 간선"으로 변환 (R1 -> T1) -> (T1 -> R1)

첫 번째 그림

R1은 T1에 할당, T2는 R1을 요청
T1은 R2를 예약, T2는 R2를 예약

두 번째 그림

T2에 R2를 할당한 상황

결론

교착 상태를 회피하기 위해선느 T2에 R2를 할당할 수 없음
왜냐?
사이클이 생기기 때문, 그래서 불안정 상태를 만들기 때문에 T2에 R2를 할당할 수 없다
- T1이 R2를 요청하고, T2가 R1을 요청하면 데드락이 발생!!

Deadlock detection

각 자원 유형의 인스턴스가 한 개만 있을 경우
- 대기 그래프(wait-for graph)을 사용
- 자원 할당 그래프로부터 자원 유형 노드를 삭제
- T1 -> T2의 간선은 T1 -> R1, R1 -> T2를 의미
  - 즉, T1이 보유하고 있는 자원 R1을 T2가 할당받기를 원함
- 사이클이 발생할 경우 데드락이 발생할 수 있음!
자원유형의 인스턴스가 여러 개일 경우
- 대기 그래프 사용할 수 없음
- 뱅커스 알고리즘과 비슷하게 수행됨

detection은 언제 할까?

그렇다면 우리는 detection 알고리즘을 언제 사용할까?

교착 상태가 자주 발생하는 경우
- 당연히 자주 돌려야함
- 교착 상태가 발생하면 자원을 회수하기까지 해당 자원은 아무도 사용하지 못함
- 시간이 더 지날수록 데드락에 연루된 스레드들이 늘어날 수 있음
교착 상태가 일어날 시 몇 개의 스레드가 연루되어있는가?
- 교착 상태가 일어나는 시점은 스레드가 자원을 요청했는데 즉시 만족되지 못하는 시점
  - 만약에 스레드의 요청이 즉시 만족되지 않을 때마다 detection 알고리즘을 실행한다면??
  - 데드락에 연루된 스레드 뿐만 아니라 데드락을 야기한 스레드도 알 수 있음
- 하지만 자주 detection 알고리즘을 실행한다면 오버헤드가 매우 커짐
  - 해결방법
  - 지정된 시간마다 알고리즘을 수행해보자!! 또는 CPU 이용률이 기준 미만일 때 수행하자!!
  - 하지만 임의의 시간에 호출하면 여러 사이클을 포함할 수 있고, 데드락을 발생시킨 스레드를 알아낼 수 없게 됨

recovery

교착 상태가 발생한 것을 operator에게 통지해, 운영자가 직접 처리하거나

시스템이 자동으로 교착 상태로부터 회복하게 하는 방법이 있음

한 개 이상의 스레드를 중지시키거나 데드락인 스레드로부터 자원을 선점함

Process termination

데드락에 연관된 프로세스들을 한꺼번에 중지
- 확실하게 데드락을 깨뜨리지만 비용이 큼
- 중지된 프로세스나 스레드가 오랫동안 연산한 결과를 폐기하고, 다시 진행해야함
데드락에 연관된 프로세스들을 하나씩 죽이면서 데드락인지 확인한다
- 각 프로세스나 스레드가 중지될 때마다 detect 알고리즘을 호출해 데드락인지 확인해야하므로 오버헤드가 상당함
- 그렇다면 어떤 프로세스를 중지시킬까(기준 제시)?
  - 프로세스의 우선순위
  - 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는데 더 필요한 시간
  - 프로세스가 사용한 자원 유형과 수(자원들을 선점하기가 단순한지 여부)
  - 프로세스가 종료하기 위해 더 필요한 자원의 수
  - 얼마나 많은 수의 프로세스가 종료되어야 하는지

Resource Preemption

데드락이 연루된 프로세스로부터 자원을 뺏는다.
비용을 "최소화"할 희생양을 찾고, 희생양으로부터 자원을 뺏어서 데드락을 없앤다.
safe state한 상태로 roll back하여 프로세스를 restart 한다
- 문제점
  - 희생양으로부터 자원을 뺏었는데 다른 프로세스가 갖기 전에 해당 프로세스가 또 자원을 요청하여 다시 가져가 버릴 수도 있음. 데드락을 없애놨더니 똑같은 패턴이 일어날 수도 있다.
    - 자원을 뺏는 패턴을 똑같은 방식으로만 하는 것이 아니라 조금씩 바꿔서 시행
- starvation이 발생할 수 있음
  - 항상 비용을 최소화해야 한다고 해서 특정 프로세스만 선정이 되고 그 프로세스만 자원을 뺏기게 되면 비용을 최소화하는 데 성공했지만, 그 프로세스 입장에서는 계속 앞부분으로 롤백해야 하기 때문에 희생이 크다.

Deadlock Ignorance

운영체제나 시스템은 데드락이 생기면 책임지지 않고 그대로 놔둔다.
데드락이 발생하면 사용자가 문제가 생겼다는 것을 알고 프로세스를 죽이든지 사용자가 알아서 처리하도록 한다.

REFERENCES

Operating System Concepts(10th EDITION)

- ABRAHAM SILBERSCHATZ

https://core.ewha.ac.kr/publicview/C0101020140411151510275738?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f