혼자 공부하는 컴퓨터 구조 + 운영체제 Chapter 13

안녕하세요! 제이덥입니다~ 저는 학부 때 공부했던 CS 기초 내용을 Wrap-Up 하기 위해 혼공학습단 11기 활동을 진행하고 있는데요. 5주째가 되니 어느정도 개념을 다시 정리한 느낌이 듭니다.
이번 포스팅에서는 Chapter 13 교착 상태에 대해 다룹니다. 교착 상태가 무엇이고 어떻게 해결 할 수 있는지에 대해 정리했습니다. 동기화와 더불어 CS 면접에 자주 나오니 이 글을 보시는 분들도 세세하게 살펴보시는걸 추천드립니다.
해당 도서는 제가 직접 구매하여 글을 작성한 것이며, 혼공단 11기 활동의 일환으로 학습 내용에 대한 공유 글을 작성하게되었음을 알려드립니다. 도서에 대한 자세한 내용과 활동에 대한 내용을 알고 싶은 분들은 아래 Reference에서 확인해주세요~

Chapter 13. 교착 상태

1️⃣ 교착상태란

• 식사하는 철학자 문제(dining philosophers problem)
  • 교착 상태를 설명하는 고전적인 예시이자 시나리오
  • 상황 가정:
    
    • 동그란 원탁에 5명의 철학자가 앉아 있음
    • 철학자 앞에는 음식이 있고, 식사에 필요한 2개의 포크가 있고, 이 포크를 통해서만 식사가 가능함
    • 식사 순서
      1. 계속 생각을 하다가 왼쪽 포크가 사요가능하면 집어듬
      2. 계속 생각을 하다가 오른쪽 포크가 사용가능하면 집어듬
      3. 왼쪽과 오른쪽 포크 모두 집어들면 정해진 시간 동안 식사
      4. 식사 시간이 끝나면 오른쪽 포크를 내려놓음
      5. 오른쪽 포크를 내렿놓은 뒤, 왼쪽 포크를 내려높음
      6. 다시 1번 부터 반복
  • 1,2명이 식사하는데 문제가 없으나 모든 철학자가 동시에 왼쪽 포크를 들게되면 식사를 시작하지 못함
  • ⇒ 실행 순서 때문에 식사를 하지 못하고 무한히 기다리게 됨
  • 이와 같이 교착상태(deadlock)는 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 말함
    • ex) 프로세스 A가 프로세스 B의 자원C를 기다리고, 반대로 프로세스 B가 프로세스 A의 자원 D를 기다리며 대기 ⇒ 계속 대기함
• 자원 할당 그래프(resource-allocation graph)
  • 교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있음
    
  • 표현 방식
    1. 프로세스는 원으로 자원의 종류는 사각형으로 표현
    2. 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현
    3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
    4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
  • 교착 상태가 발생하는 그래프는 원으로 순환하는 형태를 띄게됨
• 교착 상태의 4가지 발생 조건
  • 교착 상태를 발생할 조건은 상호 배제, 점유와 대기, 비선점, 원형 대기 총 4가지 조건이 존재함. 다만, 이 조건 중 하나라도 만족하지 않는 다면 교착 상대(Deadlock)은 발생하지 않음.
  • 상호배제(mutual exclusion)
    • 철학자 문제에서 하나의 포크를 여러명이 사용할 수 있다면 문제는 발생하지 않음.
    • ⇒ 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 교착 상태가 발생할 수 있음
  • 점유와 대기(hold and wait)
    • 철학자 문제에서 왼쪽 포크를 들고 오른쪽 포크를 기다렸기 때문에 해당 문제가 발생함
    • ⇒ 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다렸기 때문에 발생함
  • 비선점(nonpreemptive)
    • 철학자 문제에서 강제로 포크를 빼앗을 수 있었다면 교착 상태는 발생하지 않음
    • ⇒ 비선점 자원은 프로세스가 끝날 때까지 기다려야만 이용이 가능함으로, 어떤 프로세스도 자원을 뺏지 못했기 때문에 문제가 발생
  • 원형 대기(circular wait)
    • 프로세스들과 프로세스가 요청 및 할당 받은 자원이 원의 형태를 이루었기 때문

2️⃣ 교착 상태 해결 방법

예방, 회피, 검출& 회복

• 교착 상태 예방
  • 교착 상태의 4가지 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 충족하지 못하게 하여 예방함
  • 상호 배제를 없애기
    • 상호 배제를 없앤다 ⇒ 모든 자원을 공유 한다
    • 이론적으로 교착 상태를 없앨 수 있지만, 모든 상호 배제를 없애기는 어렵기 때문에(race condition 발생 가능) 이는 불가능한 방법
  • 점유와 대기를 없애기
    • 특정 프로세스에 모든 자원을 할당하거나, 할당하지 않는 방법
    • 단점 존재 :
      • 특정 프로세스에 자원을 몰아줘서 다른 프로세스에서 자원이 필요해도 기다릴 수 밖에 없기 때문에 자원 활용률이 낮아짐 ⇒ 기아 현상 야기
  • 비선점 조건을 없애기
    • CPU와 같은 일부 자원에는 효과적
    • 하지만 프린터와 같이 비선점에 부적합한 자원이 존재 ⇒ 범용성이 떨어지는 방법
  • 원형 대기 조건 없애기
    • 번호를 통해 제거 ⇒ 현실적이고 실용적
    • 단점 존재 :
      • 프로세스 내에 수많은 자원에 번호를 붙이는 일은 간단한 작업 X
      • 각 자원에 어떤 번호를 붙이느냐에 따라 자원의 활용률 감소
  • 예방 방식은 각각의 방식에서 여러 부작용이 존재
• 교착 상태 회피
  • 교착 상태 회피 : 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주 ⇒ 교착 상태가 발생하지 않을 정도만 자원을 할당
  • 구현 방식 : 안전 순서열 활용
    • 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미함.
    • 안전 상태(safe state) : 정상적으로 자원을 할당 받아 종료될 수 있는 상태 ⇒ 안전 순서열 존재
    • 불안전 상태(unsafe state) : 교착상태가 발생할 수 있는 상태 ⇒ 안전 순서열 존재X
• 교착 상태 검출 후 회복
  • 교착 상태가 발생했음을 인지하고 해결하는 방식
  • 선점을 통한 회복
    • 교착 상태가 해결 될 때까지 다른 프로세스로부터 자원을 강제로 빼앗아 몰아주는 방식
  • 프로세스 강제 종료를 통한 회복
    • 교착 상태에 놓여있는 프로세스 모두를 강제 종료 ⇒ 가장 확실한 방법, 프로세스들이 작업 내역을 잃게 될 가능성이 큼
    • 교착 상태가 없어질 때까지 한 프로세스씩 종료 ⇒ 작업 내역을 잃는 프로세스를 줄일 수 있지만, 교착 상태를 지속적으로 확인하는 오버헤드 발생
  • 교착 상태를 무시하는 방법 : 타조 알고리즘(ostrich algorithm)
    • 문제 발생 빈도나 심각성에 따라 무시하여 엔지니어 관점에서 개발의 효율성을 추구

Reference :

혼자 공부하는 컴퓨터구조 + 운영체제

혼공학습단 11기 활동