교착상태와 교착상태 해결방법

김멉덥·2022년 11월 21일
2

기술면접 공부

목록 보기
7/8
post-thumbnail

교착상태와 교착상태 해결방법에 대해서 설명해주세요.

CS 및 기술 면접 준비 스터디

답변

  • 교착상태란 두 개 이상의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 서로에게 요구하고 있어서 그 프로세스들이 무한정으로 기다리고 있는 상태입니다.
  • 이에 대한 해결방법은 예방, 회피, 탐지회복이 있습니다.

교착상태란 ?

  • Deadlock
  • 두 개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘 다 영원히 끝나지 않는 상황


교착상태의 4가지 필요 조건

아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
→ 하나라도 만족하지 않으면 발생하지 X

  1. 상호 배제 (Mutual exclusion)
    • 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.
    • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
  2. 점유와 대기(Hold and wait)
    • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
  3. 비선점 (No preemption)
    • 이미 할당된 자원을 강제로 빼앗을 수 없다.
    • 프로세스가 task를 마친 후 리소스를 자발적으로 반환할 때까지 기다려야 한다.
  4. 환형 대기 (Circular wait)
    - 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
    - Hold and wait 관계의 프로세스들이 서로를 기다림

교착상태 해결방법

크게 3가지의 해결법이 존재한다.

  • 데드락이 발생하지 않도록 예방(prevention) 하기
  • 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
  • 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복(Recovery)하기

1️⃣ 예방 (Prevention)

  • 교착상태가 발생할 수 있는 요구조건을 만족시키지 않게 함으로써 교착상태를 방지한다.
  • 위에 있는 교착상태 발생의 네가지 조건 중에서 어느 하나를 제거함으로써 수행된다.
  • 자원 낭비가 가장 심한 기법이다.

2️⃣ 회피 (Avoidance)

  • 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법이다.
  • 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다.
  • 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.

은행원 알고리즘

  • 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
  • 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태는 안전상태, 교착상태가 발생할 수 있는 상태는 불안전 상태 라고 한다.
  • 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
  • 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.

3️⃣ 탐지 및 회복 (Detection and Recovery)

  • 교착상태가 발생 할 수 있도록 놔 두고 교착상태가 발생 할 경우 찾아내어 고친다.

탐지

  • 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
  • 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용한다.

    자원 할당 그래프의 단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생한다.

회복

  • 교착상태를 발견했다면 회복기법을 진행한다.
  • 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.

    1. 프로세스 종료 방법

    • 교착 상태의 프로세스 모두 중지
    • 교착 상태가 제거될 때까지 한 프로세스씩 중지

    2. 자원 선점 방법

    • 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
    • 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴

참고 자료

profile
데굴데굴 뚝딱뚝딱 개발기록

0개의 댓글