13.1 교착 상태란

13.1.1 식사하는 철학자 문제

• 식사하는 철학자 문제; dining philosophers problem 는 교착 상태(dead lock) 상황을 설명하기 위한 고전적인 문제 상황
  • 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생
  • 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들 수 없기 때문
  • 다시 말해 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다림
  • 포크-임계 구역 or 자원
  • 철학자-프로세스 or 스레드
  • 생각하는 행위-자원을 기다리는 것
• 교착 상태; deadlock: 영원히 일어나지 않을 사건을 기다리며, 진행이 멈춰 버리는 현상

• 프로세스A는 임계 구역 진입 전 lock1을 잠그고 (lock1 = true), 프로세스B는 임계 구역 진입 전 lock2를 잠갔다고 (lock2 = true) 가정
• 만일 프로세스 A는 lock2가 false가 되길 기다리고, 프로세스 B는 lock1이 false가 되길 기다린다면 교착 상태가 발생

13.1.2 자원 할당 그래프

• 교착 상태는 자원 할당 그래프 resource-allocation graph 를 통해 단순하게 표현 가능

• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띈다

13.1.3 교착 상태 발생 조건

• 아래 조건 중 하나라도 만족하지 않는다면 교착 상태 발생 X

• 아래 조건이 모두 만족될 때 교착 상태 발생 O

13.1.3.1 상호 배제, mutual exclusion

• 식사하는 철학자 문제에서 하나의 포크를 여러 명이 동시에 사용할 수 있었다면 교착 상태는 발생하지 않음
• 프로세스도 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때,
• 즉, 상호 배제 mutual exclusion 상황에서 교착 상태가 발생 가능

13.1.3.2 점유와 대기, hold and wait

• 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다.
• 이렇게 ‘자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태‘를 점유와 대기라 한다.

13.1.3.3 비선점, nonpreemptive

• 만일 철학자들 중 누군가가 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착 상태는 발생하지 않음

• 프로세스가 자원을 비선점 nonpreemptive 하고 있었기 때문.

• 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다.

• 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생

13.1.3.4 원형 대기, circular wait

• 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문입니다.
• 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기 circular wait 라고 합니다.

• 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 ‘수’ 있다고 표현한 이유가 있다.
  • 자원 할당 그래프가 원의 형태를 띄지 않는다면 교착 상태는 발생하지 않으나,
  • 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아닙니다.

13.2 교착 상태 해결 방법

• 운영체제는 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방 가능

• 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피 가능

• 자원을 제약 없이 할당하다가 교착 상태가 검출되면 교착 상태를 회복 가능

13.2.1 교착 상태 예방

• 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당

• 상호 배제 없애기

  • 모든 자원을 공유 가능하게 만든다는 말
  • 교착 상태는 없앨 수 있지만, 모든 자원의 상호 배제를 없애기는 현실적으로 어려움

• 점유와 대기 없애기

  • 철학자들로 하여금 한 손에 포크를 들고 다른 포크를 기다리지 못하게 금지하는 것과 같다.
    • 포크를 두 개 동시에 들게 하거나, 아니면 아예 들지 못하게 하는 것
  • 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지않는 방식으로 배분
  • 이론적으로는 교착 상태를 해결할 수 있지만, 단점도 존재
    • 자원의 활용률이 낮아질 우려 존재
      • 점유와 대기를 금지하면 한 프로세스에 필요한 자원들을 몰아주고, 그 다음에 다른 프로세스에 필요한 자원들을 몰아줘야 함
      • 이는 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아짐
    • 많은 자원을 사용하는 프로세스가 불리
      • 자원을 많이 사용하는 프로세스는 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기 어렵기 때문
      • 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려

• 비선점 조건 없애기

  • 비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있음
  • 이 방식은 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적
    • 가령 CPU는 프로세스들이 선점할 수 있는 대표적인 자원
    • 한 프로세스가 CPU를 이용하다가 일정 시간이 지나면 아직 작업이 모두 끝나지 않았다고 할지라도 다른 프로세스가 CPU를 할당받아 사용할 수 있기 때문
  • 하지만 모든 자원이 이렇게 선점 가능한 것은 아님
    • 한 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야 하는 자원도 얼마든지 존재
      • 예를 들어 한 번에 하나의 프로세스만 이용 가능한 프린터 자원
      • 한 프로세스가 이 프린터를 이용하는 도중에, 다른 프로세스가 프린터 자원을 빼앗아 사용하기 어려움
      • 그렇기에 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하는 것은 다소 범용성이 떨어지는 방안

• 원형 대기 조건 없애기

  • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않음
    • 예를 들어, 식사하는 철학자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고,
    • 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어들게 한다면 원형 대기는 발생하지 않음
    • 5번 포크를 집어들고 1번 포크를 집어들 수 없기 때문
  • 원형 대기를 없앰으로써 교착 상태를 예방하는 방식은 비교적 현실적이고 실용적인 방식이지만, 역시 단점 존재
    • 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 간단한 작업이 아니거니와
    • 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있음

  

• 이렇듯 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 존재

13.2.2 교착 상태 회피

• 교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식

  • 항시 ‘안전 상태’를 유지하도록 자원을 할당하는 방식

• 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주

  • 포크가 100개, 1,000개 있는 상태에서 철학자들이 한두 개 의 포크를 요구하면 교착 상태는 발생 X
  • 반면 포크의 양이 충분하지 않은 상태에서 모두 자신이 요구할 수 있는 최대의 포크 (두 개)를 요구하면 교착 상태가 발생

• 안전 상태; safe state: 교착 상태가 발생하지 않고, 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태

  • 안전 순서열이 있어서 교착 상태가 발생하지 않는 상태를 안전 상태 라 한다.

• 불안전 상태; unsafe state: 교착 상태가 발생할 수도 있는 상황

  • 안전 순서열이 없는 상태, 교착 상태가 발생할 위험이 있음

• 안전 순서열; safe sequence: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

  • 예를 들어 웹 브라우저, 메모장, 게임 프로세스가 동시에 운영체제에 자원을 요청한 상황에서
  • 웹 브라우저-메모장-게임 프로세스 순서대로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정
  • 이 경우 웹 브라우저 -> 메모장 > 게임이 안전 순서열이 됩니다.

프로세스와 스레드는 자원을 사용하기 위해

1. 우선 자원을 운영체제에게 요청
2. 운영체제로부터 자원을 할당받아 사용
3. 자원의 사용이 끝났다면 자원을 반환

• 안전 상태 예시

​

​

• 불안전 상태 예시

  

​

13.2.3 교착 상태 검출 후 회복

• 교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력이었다면,
• 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식
  • 검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당
  • 교착 상태 발생 여부를 주기적으로 검사하고, 검출되면 그때 회복

13.2.3.1 선점(독점 불가)을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식

13.2.3.2 프로세스 강제 종료를 통한 회복

• 프로세스 강제 종료를 통한 회복은 가장 단순하면서 확실한 방식

• 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고,

  • 가장 확실한 방식이지만 그만큼 많은 프로세스들이 작업 내역을 잃게 될 가능성이 존재

• 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있다.

  • 작업 내역을 잃는 프로세스는 최대한 줄일수 있지만 교착 상태가 없어졌는지 여부를 확인 오버헤드를 야기

• 실은 교착 상태를 아예 무시하는 방법도 존재

  • 타조(ostrich) 알고리즘: 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식
  • 완벽을 추구하는 과학자나 수학자 입장에서는 납득할 수 없는 방식일지 모르나
  • 문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 때때로 이 방식이 적합할 때도 있다.

Reference

• 혼자 공부하는 컴퓨터구조+운영체제 (강민철, 한빛미디어) https://product.kyobobook.co.kr/detail/S000061584886