교착 상태와 기아 상태

Sawol·2021년 5월 19일

운영체제 뽀개기

목록 보기

4/7

교착 상태(Deadlock)

교착 상태

결코 일어나지 않을 사건을 기다리는 상태. 컴퓨터에서는 둘 이상의 프로세스가 서로의 자원을 기다릴 때를 의미한다.

교착 상태가 일어나는 이유

제한된 자원의 사용률과 효율성을 높이기위해 병행 처리 기술과 자원 공유에 따른 부작용이다.

예시

스풀링 시스템
스풀 공간의 출력을 완료하지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지할 때 발생. 스풀링 공간의 포화 임계치를 설정하면 예방 가능하다.
디스크를 공유할 때
프로세스가 실린더 55 위치를 읽으라고 명령하면, 그 위치로 이동하는 동안 다른 프로세스에게 제어권이 넘어간다. 다음 프로세스가 실린더 245 위치를 읽으라고 명령하면 또 위치로 이동하는 동안 다른 프로세스에게 제어권이 넘어간다. 이런 현상이 반복되어, 어느 프로세스의 요구도 만족하지 못하므로 프로세스들이 모두 대기 상태가 되어 교착 상태가 일어난다.
네트워크

교착 상태 발생 조건

자원의 특성

상호배제
한 번에 프로세스 하나만 자원을 사용할 수 있어야 한다.
비선점
자원을 강제로 빼앗을 수 없어야한다.

프로세스의 특성

점유와 대기
자원을 최소 하나는 보유하고 다른 프로세스에 할당된 자원을 얻으려고 기다려야한다.
순환(환형)대기
순환된 형태로 자원을 요구하고 대기하는 상태여야한다.

4 가지 발생조건 중 하나만 성립되지 않아도 교착 상태는 발생하지 않는다.

교착 상태 해결 방법

예방 방법

상호배제 조건 방지
모든 자원을 공유하면 상호배제 조건을 막을 수 있음.
하지만 현실적으로 불가능.
비선점 조건 방지
모든 자원에 대한 선점 허용하면 비선점 조건을 막을 수 있음.
하지만 현실적으로 불가능.
- 유사한 방법
  요청하는 자원이 다른 프로세스가 점유하고 있어 요청이 거절당하면 점유한 자원을 모두 반납하고 작업 취소.
  이후 프로세스는 다시 처음부터 시작해야 하므로 심각한 자원 낭비가 발생하므로 비현실적.
점유와 대기 조건 방지
필요 자원을 한번에 모두 할당하면 점유와 대기 조건을 막을 수 있음.
프로세스가 아직 필요하지 않는 자원까지 모두 할당받고 있어 다른 프로세스가 사용을 못해서 자원 낭비가 발생.
무한 대기 현상 발생 가능.
순환(환형)대기 조건 방지
모든 자원에 순서를 부여하여 프로세스가 순서대로 요청을 할 수 있게 하면 순환 대기 조건을 막을 수 있음.
프로세스는 순서가 증가하는 방향으로만 자원을 요청할 수 있기때문에 첫번째 순서의 자원을 다른 프로세스가 점유하여 할당 받지 못하면 다음 자원을 할당 받아 일을 하면 되는데 그렇게 하지 못하니 대기해야함. => 자원 낭비가 발행함.

예방 방법으로 교착상태 발생을 막을 순 있지만 심각한 자원 낭비가 발생함.

회피 방법

예방 방법은 시스템의 효율성과 처리량을 떨어뜨린다. 그래서 회피 방법은 예방 방법보다 덜 엄격한 조건으로 자원을 좀 더 효율적으로 사용하는 것이 목적이다.
시스템 상태를 계속 감시(오버헤드 증가)하며 교착상태가 일어날 가능성이 있다면 자원할당 요청을 보류함.(자원 효율성 하락: 일어나지 않을 수도 있는데 자원할당을 하지 못하게해 함)
그러기위해 시스템을 항상 safe state 상태로 유지함.
예방방법은 신호등이였다면, 회피방법은 경찰이 직접 교통통제를 하는 것.
회피 방법의 가정은 프로세스 수, 자원 수가 고정 되어있고 필요한 최대 자원수를 알고있어야한다 인데 현실적으로는 프로세스 수와 자원 수가 고정될 수 없고 필요한 자원수도 알수 없음.

Safe state
모든 프로세스가 정상적으로 종료 가능한 상태
교착상태가 되지 않을 수 있음을 보장하는 safe sequence가 존재
Unsafe state
교착상태가 발생될 가능성이 있음. => 반드시 발생하다는 건 아님.

프로세스 시작 중단
프로세스의 요구가 교착 상태를 발생시킬 수 있다면 시작을 중단한다.
각 프로세스마다 요청과 해제 순서를 파악하여 대기여부를 결정해야한다.
자원 할당 거부
요청 자원을 할당 했을 때 교착 상태가 발생할 수 있다면 요청 자원을 할당하지 않는다. 이를 보통 은행가 알고리즘 이라고 한다.
- 은행가 알고리즘(banker's algorithm)
  가정 : 한 종류의 자원이 여러 개 있다
  시스템을 항상 safe state로 유지시키는 알고리즘.
  프로세스가 자원을 요청하면 일단 자원을 줬다고 가정하고 safe sequence가 하나라도 존재하는 지 확인해봄. 존재하지 않으면 자원 요청을 거절.
- Habermann's algorithm
  은행가 알고리즘의 확장 버전
  한 종류의 자원으로 가정했던 은행가 알고리즘과 다르게 여러 종류의 자원 고려.
  시스템을 항상 safe state로 유지시키는 알고리즘.

탐지하여 회복하는 방법

주기적으로 교착상태가 발생하는지 확인(오버헤드 발생)

교착 상태 탐지 알고리즘 : Graph reduction 알고리즘
- 주어진 그래프에서 엣지(자원을 할당/요청하는 간선)를 하나씩 지워가는 방법
- unblocked process에 연결된 엣지를 제거하는 방식으로 진행
- unblocked process
  필요한 자원을 모두 할당 받을 수 있는 프로세스
- 모든 엣지가 제거되면 교착상태에 빠진 프로세스 없음
- 지울 수 있는 엣지가 존재하면 교착상태에 빠진 프로세스가 존재
교착 상태 회복 알고리즘 :
- Process termination 알고리즘
  교착상태인 프로세스 중 일부를 종료하면서 교착상태를 회복.
  이때 종료시킬 프로세스를 선택하는 여러 모델(Termination cost model)들을 만들어 가장 비용이 적은 모델 선택.
  여러 모델을 만들어가는 과정에서 오버헤드가 발생.
- Resource preemption 알고리즘
  선점할 자원을 선택 및 선점하여 그 자원을 가지고 있던 프로세스를 종료시킴.
  선점할 자원을 선택하는 것에 필요한 모델(Preemption cost model)을 만들어야함

기아 상태(Starvation)

기아 상태

결코 사용할 수 없는 자원을 무한정 기다리는 상태를 말한다.

식사하는 철학자 문제

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게되는 것을 교착 상태라고 한다. 동시에 양쪽 포크를 집을 수 없어 식사를 하지 못하는 기아 상태가 발생할 수도 있다.
양쪽 포그를 모두 사용할 수 있을 때 포크를 집도록 하면 이 문제를 해결 할 수 있다.

기아 상태 해결 방법

각 작업이 가다린 시간을 조사 및 추적해서 오래 기다린 프로세스의 우선 순위를 높여줘야함.
요청 순서대로 처리하는 요청큐 사용.