😰 교착상태와 기아상태

개요

시스템 측면에서 자원의 요구가 뒤엉킨 상태를 말한다.
한 프로세스 집합 내의 프로세스들에 의해 발생할 사건(event)를 프로세스들이 서로 기다리고 있는 상태를 말한다.
둘 이상의 작업이 보류 상태에 놓여 중요한 자원을 이용하기 위해 기다릴 때 발생한다.
제한된 자원 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행처리기술과 자원공유에 따른 부작용이다.

초기 일괄처리시스템

사용자들이 작업제어카드에 작업을 완료하기 위해 필요한 자원을 명시하여 교착상태가 자주 발생하지 않는다.
운영체제가 요청한 자원이 준비 큐로 이동하기 전 사용 가능 여부를 확인하여 할당한다.
자원이 확보되지 않으면 작업이 준비 큐로 이동할 수 없어 교착상태가 발생하지 않는다.

대화식시스템

동적 자원 공유로 자원의 이용도를 높이는 과정에서 교착상태가 발생한다.

DVD Drive 와 Printer 가 각각 하나씩 존재하고 다음과 같은 경우

• Process P: DVD Drive 점유 >> Printer 요청
• Process Q: Printer 점유 >> DVD Drive 요청

Tape Drive 가 3개 존재하고 다음과 같은 경우

• Process P: Tape Drive 점유
• Process Q: Tape Drive 점유
• Process R: Tape Drive 점유

프로세스 자원 이용 순서

• 요청: 프로세스가 자원을 요청한다. 요청을 즉시 받아들여지지 않으면 다른 프로세스가 사용중이므로 할당 받을때 까지 대기한다.
• 사용: 프로세스가 요청한 자원을 사용한다.
• 해제: 프로세스가 자원 사용을 마친 후 할당 받은 자원을 되돌려준다.

교착상태 발생 CASE

• 파일 요청: 파일을 이용해 작업이 실행되는 동안, 파일에 대한 다른 작업의 점유 요청이 인정되면 교착상태가 발생한다.
• 전용장치 할당: 두 사용자(P1, P2)가 각각 테이프 드라이브 1대를 사용하고 한 테이프에서다른 테이프로 복사하는 작업을 할 경우 교착상태가 발생한다.
• 스풀링 시스템: 디스크에 할당된 스풀 공간의 출력이 완료되지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 교착상태가 발생한다.
• 디스크 공유: 디스크는 대표적인 공유 자원으로, 사용에 대한 제어가 없다면 교착상태가 발생할 수 있다.
• 네트워크: 붐비거나 입출력 버퍼 공간이 부족한 네트워크 시스템이 메시지 흐름을 제어하는 적절한 프로토콜을 가지지 못한 경우 교착상태가 발생한다.

교착상태 발생 조건

• 상호배제

• 점유와 대기

• 비선점

• 순한대기

• 강건너기 교착상태

- 여러 개의 돌로 된 징검다리가 있는 강을 건너는 경우
- 강을 건너는 사람을 프로세스(P), 징검다리의 돌을 자원(Data)라 가정한다.
- 두 사람이 동시에 서로 다른 방향에서 출발, 강 중간에서 만나면 '교착상태가 발생했다.' 할 수 있다.
- 돌을 딛는 것을 자원 할당, 발을 떼는 것을 자원 해제로 볼 때 동시에 같은 돌을 딛이려 하면 교착상태가 발생한다.
- 각 사람은 돌 하나를 딛고 다음 돌을 요구한다.(점유와 대기 조건 만족)
- 사람이 딛고 있는 돌을 강제로 제거할 수 없다.(비선점 조건 만족)
- 왼쪽에서 오는 사람은 오른쪽 사람을, 오른쪽에서 오는 사람은 왼쪽 사람을 기다린다.(순환대기 조건 만족)

• 강건너기 교착상태 해결방안
  • 둘 중 한 사람이 되돌아간다.(복귀)
  • 강을 건너기 전에 상대편 강 쪽을 확인하고 출발한다.
  • 강의 한 쪽 편에 우선권을 부여한다.

교착상태 해결 기법

• 시스템이 교착상태가 되지 않도록 예방
• 가능한 교착상태를 회피
• 교착상태를 허용하되 교착상태에서 다시 회복 가능하도록(사용하기 어려움, 오버헤드 증가)

예방 기법

• 상호배제 문제 고려
• 하벤더, 1986년 상호배제를 제외한 3가지 기본 방법 제안
  • 각 프로세스는 한번에 필요한 모든 자원을 요구해야하며, 요청한 자원을 모두 제공 받기 전까지는 작업을 진행할 수 없다.
  • 어떤 자원을 점유하고 있는 프로세스의 요구가 더 이상 허용되지 않으면 점유한 자원을 모두 반납하고 필요할 때 다시 자원을 요구해야 한다.
  • 모든 프로세스에 자원을 순서대로 할당해야 한다. 모든 프로세스에 각 자원을 유형별로 할당 순서를 부여한 후, 순서에 따라 자원을 요구한다.

상호배제 조건 방지

• 상호배제 조건은 자원의 비공유를 전제로 한다.
• 일반적으로 상호배제 조건을 거부하면 교착상태를 예방하는 것이 불가능하다.
• 파일 쓰기는 배차적인 접근만이 허용되어야 한다.

점유와 대기 조건 방지

• 최대 자원 할당
  • 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 획득 해야한다.
  • 보류 상태에서는 프로세스가 자원을 점유할 수 없으므로 대기 조건이 성립하지 않는다.

비선점 조건 방지

• 할당 자원 선점권 제외
  • 어떤 자원을 가진 프로세스가 자원 요청 시 기다려야 한다면, 프로세스는 현재 가진 자원을 모두 해제한다.
  • 프로세스가 작업을 시작하려면 요청한 새로운 자원과 해제한 자원을 확보해야한다.
  • 작업 상태를 쉽게 저장 및 복구 가능할 때 또는 빈번하게 발생하지 않을 때만 좋은 수단으로 이용 가능하다.

비선점 조건 방지 - 대안

• 프로세스 자원 요청 시 사용 가능여부 검사
  • 사용 가능하다면 자원 할당, 사용 불가능한 경우 대기 프로세스가 요청한 자원을 점유하고 있는지 검사한다.
  • 요청한 자원을 대기 프로세스가 선점하고 있다면, 자원을 해제하고 요청 프로세스에 할당한다.
  • 요청한 자원을 사용할 수 없거나, 실행 중인 프로세스가 점유하고 있다면 요청 프로세스는 대기한다.

순환 대기 조건 방지

• 계층적 요구 기법
  • 모든 자원에 일련의 순서를 부여, 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 한다.
  • 순환대기의 가능성을 제거하여 교착상태를 예방한다.
  • 예상된 순서와 다르게 자원을 요구하는 작업은 자원 낭비를 초래한다.
  • R={R1, R2… Rn} 을 자원 형태 집합이라 가정하고, 각 자원 형태에 고유 숫자를 부여한다.

교착상태 회피 기법

• 프로세스의 시작 거부

  • 프로세스의 요구가 교착상태를 일으킬 수 있다면 프로세스 시작을 중지한다.
  • 현재 수행중인 모든 프로세스의 최대 자원 요구량과 새로운 프로세스의 최대 요구량을 합한 자원요구량을 수용할 수 있으면 새로운 프로세스를 수용한다.

• 자원 할당의 거부

  • 프로세스가 요청한 자원을 할당했을 때, 교착상태가 발생할 수 있다면 요청한 자원을 할당하지 않는다.
  • 일반적으로 은행가 알고리즘이라 부른다.

• 교착상태 회피를 위한 자원 요구 시점 추가 정보 필요성

  • 각 프로세스마다 요청과 해제에 대한 정확한 순서를 파악하고 있다면 요청에 따른 프로세스 대기여부를 결정 가능하다.

• 각 프로세스에 대한 요구, 해제 사전 인지

  • 필요한 정보의 양과 종류에 따라 다양한 교착상태 회피 알고리즘을 적용할 수 있다.
  • 프로세스가 요청할 자원마다 최대치 정보를 미리 파악할 수 있다면 시스템이 교착상태가 되지 않을 확실한 알고리즘을 만들 수 있다.

• 안정 상태와 불안정 상태

  • 교착상태 회피 알고리즘은 시스템이 순환-대기 조건이 발생하지 않도록 자원 할당 상태를 검사한다.
  • 자원 할당 상태는 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의해 정의된다.

• 안정 상태

  • 각 프로세스에 자원을 할당할 수 있고(최대치까지), 교착상태를 방지할 수 있다.

• 불안정 상태

  • 안정 상태처럼 프로세스의 자원 할당 및 해제의 순서가 명확히 존재하지 않는 경우
  • 교착상태는 불안정 상태이나, 모든 불안정 상태가 교착상태인 것은 아니다.

교착상태 탐지

쇼사니와 포크만이 제안, 다음과 같은 자료구조들을 사용한다.

• Available: 자원 형태마다 사용 가능한 자원 수를 표시하는 길이가 M인 Vector
• Allocation: 각 프로세스에 현재 할당된 각 형태의 자원 수를 표시하는 n * m 행렬
• Request: 각 프로세스의 현재 요청을 표시하는 n * m 행렬
• Request(i,j): 프로세스 pi 가 필요한 자원 수가 k 개라면 프로세스 pi 는 자원 형태 rj 의 자원을 k 개 더 요청한다.

교착상태 회복 기법

• 순환대기 탈피
  • 프로세스를 한 개 이상 중지 시키는 방법
  • 교착상태의 프로세스들로부터 자원을 선정하는 방법
• 프로세스 중지
  • 두 가지 방법이 있으며, 모두 시스템이 정지된 프로세스에 할당된 모든 자원의 해제를 요구한다.
  • 교착상태 프로세스를 모두 중지
  • 한 프로세스 씩 중지
• 부분 종료 방식
  • 어느 프로세스를 중지 시킬지 결정해야 하며, 이는 프로세서 스케줄링과 유사한 정책 결정 문제이다.
  • 경제적인 문제로, 프로세서들을 중지 시키는데 최소 비용으로 중지시키는 방법을 찾아야한다.
• 자원 선점
  • 프로세스의 자원을 선점하여 교착상태가 해결될 때 까지 선점한 자원을 다른 프로세스에 할당하여 이용한다.
  • 선점 자원 선택
  • 복귀
  • 기아

기아상태

프로세스가 자신의 작업을 완료하지 못하는 상태, 교착상태를 예방하기 위해 자원을 할당할 때 발생되는 결과이다.

• 다익스트라, 식사하는 철학자 문제

  • 철학자 5명은 대부분의 시간을 생각하고 먹는데 소비하며, 철학자들은 의자 5개로 둘러 쌓인 원형 테이블을 공유한다.
  • 테이블 중앙에 음식이 있으며 포크가 5개 놓여있다.
  • 지역 풍습에 따라 철학자들은 포크 2개로 식사하며, 5명의 철학자가 동시에 식사할 수 없고 2명만 동시에 식사 가능하다.
  • 철학자가 생각 중 일 때 다른 철학자가 간섭하지 않는다.
  • 배고픈 철학자가 식사를 위해 왼쪽과 오른쪽의 포크를 2개를 든 다 가정할 때,
  • 철학자는 한 번에 포크 하나만 들 수 있으며, 왼쪽 포크를 먼저 집은 후 오른쪽 포크를 집는다.
  • 이웃 철학자가 이미 들고 있는 포크는 잡을 수 없다.
  • 배고픈 철학자는 두 포크를 동시에 갖게 되면 식사를 시작한다.
  • 식사를 마치면 포크 2개를 내려놓고 계속 생각한다.
  • 모든 철학자가 동시에 식사를 한다면 교착상태에 빠진다.

• 포크를 세마포어로 표시하여 교착상태 해결

  • 철학자는 포크에 해당하는 세마포어에 대한 연산 p 를 수행하고 나서 포크를 집는다.
  • 포크는 해당 세마포어에 대한 연산 v 을 수행함으로써 내려 놓는다.

• 교착상태 발생 해결 방안

  • 철학자 4명만 테이블에 동시에 앉도록 한다.
  • 철학자가 양쪽 포크 모드를 사용 가능할 때 포크를 집을 수 있도록 허용한다.(임계영역 내)
  • 비대칭 해결법을 사용하며, 홀수번째 철학자는 왼쪽 포크를 집은 후 오른쪽 포크를 짝수번째 철학자는 오른쪽 포크 다음에 왼쪽 포크를 집도록 한다.