[운영체제] Deadlock

cs-study에서 스터디를 진행하고 있습니다.

Deadlock이란?

프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 뜻하며, 교착 상태라고 부른다. 두 개 이상의 작업이 서로 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태이며, 다중 프로그래밍 환경에서 흔히 발생한다.

 

교착 상태의 조건

 

우선 발생하는 이유를 간단히 살펴 보자면, Process 1과 Process 2 각각 Resource 1과 Resource 2가 필요한 상황이 있다고 하자.

Process 1은 Resource 1을 먼저 요청하여 얻고, Process 2는 Resource 2를 먼저 요청하여 얻은 이후 Process 1은 Resource 2를 요청하지만 Process 2가 사용하여 얻을 수 없다. 마찬가지로 Process 2도 Resource 1을 요청하지만 Process 1이 요청하여 서로 무한정 wait이 된다.

 

발생 조건

• 상호 배제
• 점유 대기
• 비선점
• 순환 대기

 

상호 배제 (Mutual Exclusion)

자원은 한 번에 한 프로세스만 사용할 수 있다. 공유 불가능한 자원의 동시 사용을 피하기 위해 특정 알고리즘을 사용한다.

 

공유 불가능한 자원이란?

동시에 실행되고 있는 프로그램 간의 통신에 사용되는 비트 단위의 깃발, 계수기, 큐 등이 있다. Stack 영역을 제외한 대부분은 스레드끼리 공유하는데, 스레드가 언제라도 정지되거나 시작될 수 있으며, 이때 의도치 않는 데이터가 있거나 변경될 수 있다.

 

상호 배제는 어디서 구현하는가?

임계 구역으로 불리는 코드 영역에서 구현한다.

 

 

화장실이라는 공유 자원을 안전하게 관리하고 싶다면, Mutex를 이용하여 화장실을 한 번에 한 명만 사용하게 만들 수 있다.

프로세스는 임계 구역에 진입하기 위해 진입 허가를 요청하는데, 이러한 요청을 구현하는 부분이 입장 구역이다. 입장 구역에서 기다리다가 진입 허가가 나면 임계 구역이 진입한 후, 빠져나올 때에는 퇴장 구역이 있다. 이를 제외한 다른 코드 부분들은 나머지 구역이라 한다.

 

do {
    wait(mutex);  // 입장 구역
    // 임계 구역
    signal(mutex);  // 퇴장 구역
    // 나머지 구역
}

 

임계 구역 문제는 임계 구역으로 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때 발생하는 문제를 말한다.

 

뮤텍스와 세마포어

뮤텍스와 세마포어 모두 상호 배제 조건을 달성하기 위해 고안된 기법이다.

 

임계 구역을 한 명 씩만 사용할 수 있는 화장실로 표현해보자. 여러 명이 화장실을 가고 싶어할 때 어떻게 처리할까?

 

• 뮤텍스
  • 화장실 예시
    • 화장실이 하나이고, 이를 이용하기 위해 열쇠가 필요한 경우
    • 화장실을 가고 싶은데 열쇠가 있으면 아무도 화장실에 없다는 뜻이므로 화장실을 사용할 수 있다.
    • 화장실을 가고 싶은데 열쇠가 없으면 누군가 화장실을 사용하고 있다는 뜻이므로 화장실을 사용할 수 없다.
    • 다른 사람들이 와도 열쇠가 없으면 줄을 서야하고, 열쇠가 생기면 차례대로 화장실을 사용한다.
    • → 스레드/프로세스에 의해 공유될 수 있는 열쇠라는 객체를 통해 상호 배제를 달성한다.
  • Lock & Unlock
    • Lock : 임계 구역에 들어갈 권한을 얻음.
    • Unlock : 임계 구역을 모두 사용했음을 알림.
• 세마포어
  • 화장실 예시
    • 화장실이 여러 개 있고, 빈 칸 개수를 확인할 수 있다.
    • 화장실을 가고 싶으면 빈 칸 개수를 확인하고 1개 이상이면 사용한다.
    • 화장실을 가고싶은데 빈 칸 개수가 0개이면 1개 이상이 될 때 까지 대기한다.
    • → 공통으로 관리하는 하나의 값(integer value)을 통해 상호 배제를 달성한다.
  • 세마포어 P, V 연산
    • S : 자원의 개수
    • P : 임계 구역에 들어가기 전에 수행하는 연산 → 프로세스의 진입 여부 결정
    • V : 임계 구역에서 나올 때 수행하는 연산 → 자원 반납 알림, 대기 중인 프로세스 신호
• 뮤텍스와 세마포어

• 이외에도 Monitor를 통해 상호 배제를 구현할 수 있다.

 

알고리즘

임계 구역에서 상호 배제를 보장하는 알고리즘은 여러 가지 있다.

 

• 데커의 알고리즘
  • flag와 turn 변수를 통해 프로세스 중, 누가 임계 영역에 진입할 것인지와 다음 차례가 누구인지 나타낸다.
• 피터슨의 알고리즘
  • 데커의 알고리즘과 유사하나, 다른 프로세스/스레드에게 진입 기회를 양보한다.
• 다익스트라의 알고리즘
• 램퍼드의 베이커리 알고리즘
  • 여러 개의 프로세스/스레드에 대한 처리가 가능하며, 가장 작은 수의 번호표(프로세스에 부여된 고유한 번호이자 우선순위)를 가지고 있는 프로세스가 임계 영역에 진입한다.

 

이러한 소프트웨어적 솔루션의 경우 여러 가지 단점이 존재한다.

 

• 속도가 느리다.
• 구현이 복잡하다.
• Busy waiting이 발생하여 비효율적이다. 계속 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는다.
• 프로세스 실행 중 선점될 경우 오버헤드가 발생한다.

 

점유 대기 (Hold and Wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.

나 하나 있는데, 너 꺼 갖고 싶어

 

비선점 (No Preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다. Nonpreemptive 스케줄링을 통해 구현하는데, 이때 프로세스는 자원을 스스로 반납할 때까지 계속 자원을 사용할 수 있다.

 

순환 대기 (Circular Wait)

프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

 

 

 

 

사실 점유 대기 조건과 비선점 조건을 만족하면 순환 대기 조건이 따라온다.

 

교착 상태의 관리

예방 (Prevention)

교착 상태 발생 조건 중 하나를 제거하여 발생하기 전에 예방한다.

 

• 상호 배제 부정
  • 여러 프로세스가 공유 자원을 사용하도록 한다.
• 점유 대기 부정
  • 한 프로세스가 수행되기 전에 모든 자원을 할당하고, 자원이 점유되지 않을 때에만 다른 프로세스에서 요구할 수 있도록 한다.
    • 자원 과다 사용으로 인한 효율성 문제
    • 프로세스가 요구하는 자원을 파악하는 데에 대한 비용
    • 자원에 대한 내용을 저장 및 복원하기 위한 비용
    • 기아 상태
    • 무한 대기 문제
• 비선점 부정
  • 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납하도록 한다.
• 순환 대기 부정
  • 자원에 고유 번호를 할당하여 순서대로 자원을 요구하도록 한다.

 

단점

• 자원 낭비가 심하다.
• 비용이 많이 든다.

 

회피 (Avoidance)

교착 상태가 발생하면 탐지 후 회피해서 해결한다. 자원이 어떻게 요청될 지에 대한 추가 정보를 제공하도록 요구하여 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

 

안전 상태와 불안전 상태

운영 체제는 교착 상태에 빠질 수 있는 가능성이 있는 불안전 상태와 그렇지 않은 안전 상태를 나눈다. 프로세스가 자원을 요청할 때 안전 상태를 유지할 수 있는 요청만 수락하고, 불안전 상태를 초래하는 요청은 거절한다.

 

 

• 안전 상태
  • 시스템이 교착 상태를 일으키지 않으면서 각 프로세스가 요구한 최대량만큼 필요한 자원을 할당해 줄 수 있는 상태로, 안전 순서열이 존재
  • 안전 순서열이란, 현재 상태에서 모든 프로세스에게 결국에는 자원을 할당할 수 있게 해 주는 프로세스 실행 순서
• 불안전 상태
  • 안전 순서열이 존재하지 않는 상태로, 교착 상태이기 위한 필요 조건
  • 교착 상태 → 불안전 상태 (역은 성립 x)

 

 

회피 알고리즘

자원 할당 그래프 알고리즘

각 자원 유형의 단위 자원이 하나 밖에 없는 경우 사용한다. 이 알고리즘은 자원 할당 그래프를 통해 교착 상태를 탐지하고 회피하고자 한다.

 

 

• 요청 간선
  • 프로세스 노드 → 자원 노드 실선
• 할당 간선
  • 자원 노드 → 프로세스 노드 실선
• 요청 가능 간선
  • 프로세스 노드 → 자원 노드 점선
  • 향후에 프로세스가 자원을 요청할 수 있음

 

교착 상태 예측 방법

• 그래프에 사이클이 존재하는지 확인
• 사이클이 존재할 경우, 자원 유형에 몇 개의 사례가 있는지 확인
• 하나의 사례만 있으면 교착 상태, 여러 사례가 있으면 교착 상태 가능성이 있다고 판별

 

사이클이 있지만 교착 상태가 아닌 예시

 

프로세스 P1이 작업을 완료하고 R3의 자원을 반환하면 P3은 P1이 반환한 자원을 할당 받으면 된다.

 

알고리즘의 구현

• 프로세스가 자원 요청
• 요청 간선 추가
• 요청 간선을 할당 간선으로 변환
• 교착 상태 예측 후 불안전 상태일 경우 대기. 안전 상태일 경우 요청 승인

 

자원 할당 그래프 알고리즘의 단점

자원 요청 시, 탐지 알고리즘을 실행하기 때문에 그에 따른 오버헤드가 발생하여 성능에 큰 영향을 끼칠 수 있다.

 

은행원 알고리즘 (Banker's Algorithm)

각 자원 유형의 단위 자원이 여러 개일 경우 사용한다. 운영 체제가 최소 하나의 프로세스에게는 자원을 줄 수 있는 상태를 항상 유지하는 것이 핵심이다.

은행이 최소한 한 명에게 대출해줄 수 있는 금액을 항상 보유하고 있어야 한다는 개념에서 나왔다

 

사용 자료구조

• [Available] 시스템은 현재 얼만큼의 자원을 보유하고 있는가 길이가 m인 벡터로 표현하며, Available[j] = k 일 경우 자원 j를 k개 사용할 수 있다.
• [MAX] 각 프로세스는 최대 얼만큼의 자원을 요청할 수 있는가 n * m 행렬로 표현하며, Max[i, j] = k 일 경우 프로세스 i는 자원 j를 최대 k개까지 요청할 수 있다.
• [Allocation] 각 프로세스는 현재 얼만큼의 자원을 보유하고 있는가 n * m 행렬로 표현하며, Allocation[i, j] = k 일 경우 프로세스 i는 자원 j를 k개 할당 받았음을 의미한다.
• [Need] 각 프로세스에 남아 있는 자원 요구량이 얼마인가 n * m 행렬로 표현하며, Need[i, j] = k 일 경우 프로세스 i는 작업을 완료하기 위해 자원 j가 k개 더 필요하다 Need의 경우, Max - Allocation을 통해 계산할 수 있다.

 

교착 상태 예측 방법

안전 상태인지 조사, 즉 안전 순서열 탐지는 다음과 같은 작업을 통해 이루어진다.

 

# 안전 알고리즘 (Safety Algorithm)
Work = Available
Finish = False * i

find i where Finish[i] == False and Need[i] <= Work[i]
if i exists:  # 자원을 할당받을 수 있는 프로세스를 찾음
    Work[i] = Work[i] + Allocation[i]
    Finish[i] = True
    find next i
else:
    if all(Finish) == True:  # 모든 프로세스가 자원을 할당받을 수 있음
        safe_state
    else:
        unsafe_state

 

알고리즘의 구현

프로세스가 자원을 요청할 경우 다음과 같은 작업이 이루어진다.

 

# 자원 요청 알고리즘 (Resource Request Algorithm)
if Request[i][j] < Need[i][j]:
    if Request[i][j] <= Available[j]:
        # 요청된 자원 할당
        Avaiable[j] = Available[j] - Request[j]
        Allocation[i][j] = Allocation[i][j] + Request[i][j]
        Need[i][j] = Need[i][j] - Request[i][j]

        if safe_state:  # 안전 상태인지 조사
            # 할당 완료
        else:
            rollback  # 데이터 구조는 이전 상태로 복구
            wait  # 대기
    else:
        wait  # 현재 자원이 부족하기 때문에 대기한다
else:
    error  # 프로세스가 최대 요청치 초과

 

은행원 알고리즘의 단점

• 할당할 수 있는 자원의 수가 일정해야 한다.
• 사용자 수가 일정해야 한다.
• 항상 불안전 상태를 방지해야 하기 때문에 자원 이용도가 낮다.
• 최대 자원 요구량(Max)를 미리 알아야 한다.
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

 

탐지 (Detection)

교착 상태가 발생한 후, 회복을 하기 위해서는 우선 탐지를 해야 한다. 탐지 알고리즘 → 회복 알고리즘

 

대기 그래프 (Wait-for Graph)

각 자원 유형의 단위 자원이 하나일 경우 사용한다. 자원 할당 그래프의 변형으로, 자원 할당 그래프에서 자원 노드를 제거하고 프로세스 간의 간선으로 나타낸 그래프이다.

 

 

(a) 자원 할당 그래프에 대응하는 (b) 대기 그래프다.

• Pi → Rq, Rq → Pj 간선 2개 : Pi → Pj 간선
• → 프로세스 j가 보유 중인 자원을 프로세스 i가 기다린다는 의미이다.

 

Shoshani & Coffman 알고리즘

각 자원 유형의 단위 자원이 여러 개일 경우 사용한다. 은행원 알고리즘에서 사용하는 자료 구조인 Available, Allocation, Request를 사용한다.

 

# 탐지 알고리즘 (Detection Algorithm)
Work = Available
**if Allocation[i] != 0:
    Finish[i] = False
else:
    Finish[i] = True**

find i where Finish[i] == False and **Request[i]** <= Work[i]
if i exists:
    Work[i] = Work[i] + Allocation[i]
    Finish[i] = True
    find next i
else:
    if all(Finish) == True:
        **not Deadlock**
    else:
        **Deadlock**

 

회복 (Recovery)

교착 상태가 발생한 후, 교착 상태를 일으킨 프로세스를 탐지하여 종료하거나 할당된 자원을 해제하여 회복한다.

 

프로세스 종료 방법

교착 상태의 프로세스를 종료하여 자원을 회수한다.

 

• 전체 종료 : 교착 상태의 프로세스를 모두 중지
• 부분 종료 : 교착 상태가 제거될 때까지 하나씩 프로세스 중지

 

자원 선점 방법

교착 상태 사이클이 없어질 때까지 자원을 빼앗아 다른 프로세스에게 제공

 

무시

위 기법들을 사용할 경우 성능에 큰 영향을 미칠 수 있기 때문에 교착 상태 발생 확률이 낮은 경우에는 별다른 조치를 취하지 않는다. 교착 상태는 자주 발생하지 않으므로 이 방법이 가장 비용이 적게 들며, 대부분의 운영체제에서 채택된 방식이다.

 

출처

• Deadlock
• 위키백과 교착 상태
• 뮤텍스(Mutex)와 세마포어(Semaphore)의 차이
• 상호배제 방법 - 뮤텍스, 세마포어, 모니터
• 세마포어(Semaphore) & 뮤텍스(Mutex)
• [OS] 은행원 알고리즘 (예시문제 까지)
• 교착상태 회피, 은행원 알고리즘
• 은행원 알고리즘?
• [운영체제]교착상태 회피-은행원 알고리즘(Banker's Algorithm) 쉬운 예시, 안전상태, 불안전상태
• [운영체제]데드락을 회피할 수 있는 자원할당 그래프, 은행원 알고리즘
• [운영체제] 7장 교착상태 (Deadlocks)

 

예상 면접 질문 및 답변

데드락이란 무엇인가?

데드락은 교착 상태라고도 불리며, 프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 뜻한다. 흔히 다중 프로그래밍에서 발생하는 문제로, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태가 된다.

 

데드락이 발생하는 조건은 무엇인가?

데드락이 발생하기 위해서는 조건 상호 배제, 점유 대기, 비선점, 그리고 순환 대기. 총 4가지 조건이 만족되어야 하며, 하나라도 만족되지 못하면 교착 상태가 발생하지 않는다.

상호 배제는 자원은 한번에 한 프로세스만 사용할 수 있다는 조건, 점유 대기는 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다리고 있다는 조건, 비선점은 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다는 조건, 순환 대기는 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다는 조건이다.

 

데드락을 해결할 수 있는 방법에는 어떤 것이 있는가

• 예방
  • 교착 상태의 4가지 조건 부정
• 회피
  • 자원 할당 그래프 알고리즘
  • 은행원 알고리즘
• 탐지
  • 대기 그래프
  • Shoshani & Coffman 알고리즘
• 회복
  • 프로세스 종료법
  • 자원 선점법

 

은행원 알고리즘을 설명해보아라

은행원 알고리즘이란 다중 프로그래밍 환경에서 교착 상태가 발생했을 때 해결하는 회피 알고리즘 중 하나이다. 은행원 알고리즘은 프로세스가 자원을 요청했을 때, 자원을 주게 된다면 교착 상태가 발생할 수 있는 상태가 되는지 예측한 후, 그렇지 않은 경우에만 요청에 응하는 방식으로 교착 상태를 회피한다.

따라서 프로세스가 자원을 요청하는 자원 요청 알고리즘과 해당 요청을 응했을 때 교착 상태가 발생할 수 있는 상태가 되는지, 즉, 안전 상태가 유지되는지 판별하는 안전 알고리즘을 이용하여 은행원 알고리즘을 구현할 수 있다.

 

은행원 알고리즘의 문제(단점)는 무엇인가

• 할당할 수 있는 자원의 수가 일정해야 한다.
• 사용자 수가 일정해야 한다.
• 항상 불안전 상태를 방지해야 하기 때문에 자원 이용도가 낮다.
• 최대 자원 요구량(Max)를 미리 알아야 한다.
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

 

결국 은행원 알고리즘은 구현이 복잡하고, 프로세스의 최대 자원 요구량을 미리 알아야 한다는 점에서 실질적으로 사용하기에는 어렵다.