[운영체제] 교착상태와 기아상태

교착상태와 기아상태

교착상태(Deadlock)

시스템 측면에서 자원의 요구가 뒤엉킨 상태

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

초기 일괄 처리 시스템

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

대화식 시스템

• 동적 자원 공유로 자원의 이용도를 높이는 과정에서 교착상태 발생
• 예 1 : DVD 드라이브와 프린트가 각각 하나씩 존재하고 다음과 같은 경우
  • 프로세스 P : DVD 드라이브 점유 -> 프린터 요청
  • 프로세스 Q : 프린터 점유 -> DVD 드라이브 요청
• 예 2 : 테이프 드라이브가 3개 존재하고 다음과 같은 경우
  • 프로세스 P : 테이프 드라이브 점유 =>
  • 프로세스 Q : 테이프 드라이브 점유 => [또 다른 테이프 드라이브 요청]
  • 프로세스 R : 테이프 드라이브 점유 =>

프로세스는 다음 순서로 자원을 이용

• 요청
  • 프로세스가 필요한 자원을 요청함
  • 요청이 즉시 받아들여지지 않으면 다른 프로세스가 사용 중이므로 할당 받을 때까지 대기함
• 사용
  • 프로세스가 요청한 자원을 사용
• 해제
  • 프로세스가 자원 사용을 마친 후, 할당 받은 자원을 되돌려 줌
• 자원의 요청과 해제 그리고 파일이나 입출력 장치를 읽거나 쓰는 자원의 사용도 시스템 호출에의해 이루어짐
• 운영체제는 프로세스가 자원 요청 시, 할당 받을 수 있도록 항상 확인하고 기록함

교착상태 발생

파일을 요청할 때의 교착상태

• 파일을 이용해 작업이 실행되는 동안, 파일에 대한 다른 작업의 점유 요청이 인정되면 교착 상태 발생
• 파일 요청 시 발생하는 교착상태 예
  • 두 개의 프로세스(판매, 재고)와 두 개의 파일(공급자 파일, 재고 파일) 자원을 이용한 교착상태 표현
  • 할당 요구 순서는 아래와 같음
    1. 프로세스 1(판매)은 판매 계획을 위해 공급자 파일을 요청해서 얻는다 (할당)
    2. 프로세스 2(재고)는 재고 확인을 위해 재고 파일을 요청해서 얻는다 (할당)
    3. 프로세스 1은 주문 요청한 판매를 위해 재고 파일을 요청하지만 허용되지 않는다.
    4. 프로세스 2는 주문을 위해 공급자 파일을 요청하지만 허용되지 않는다.

전용장치를 할당할 때의 교착상태

• 전용장치 할당 시 발생하는 교착 상태 예
  • 두 사용자(프로세스1, 프로세스2)가 각각 테이프 드라이브 한 대를 사용하고, 한 테이프에서 다른 테이프로 복사하는 작업을 할 경우
  • 할당 요구 순서는 다음과 같이 이루어진다 가정함
    1. 프로세스 1은 테이프 드라이브 1을 요청해서 얻는다(할당).
    2. 프로세스 2는 테이프 드라이브 2를 요청해서 얻는다(할당).
    3. 프로세스 1은 테이프 드라이브 2를 요청하지만 허용되지 않는다.
    4. 프로세스 2는 테이프 드라이브 1을 요청하지만 허용되지 않는다.

다중 주변 장치를 할당할 때의 교착상태

• 다중 주변 장치 할당 요구에 의한 교착 상태 예
  • 세 개의 프로그램(프로세스1, 프로세스2, 프로세스3)과 세 개의 전용 장치(테이프 드라이브, 프린터, 플로터)를 사용하는 경우
  • 할당 요구 순서는 아래와 같다 가정함
    1. 프로세스 1은 테이프 드라이브를 요청해서 얻는다.(할당)
    2. 프로세스 2는 프린터를 요청해서 얻는다.(할당)
    3. 프로세스 3은 플로터를 요청해서 얻는다.(할당)
    4. 프로세스 1은 프린터를 요청하지만 허용되지 않는다.
    5. 프로세스 2는 플로터를 요청하지만 허용되지 않는다.
    6. 프로세스 3은 테이프 드라이브를 요청하지만 허용되지 않는다.

스풀링 시스템에서의 교착상태

• 스풀링 시스템에서 디스크에 할당된 스풀 공간의 출력이 완료되지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 교착상태가 발생
• 스풀링 처리부(Input Spooler)에 필요량보다 많은 공간을 배당하여 교착상태 발생률을 줄일 수 있으나 비용이 많이 듬
• 스풀링 파일의 ‘일정 포화 임계치(Saturation Threshold)’를 설정하여 교착 상태 예방 가능하나 시스템의 처리량이 줄어들 수 있음
  • 예 : 약 75% 정도에 이르면 새로운 작업을 읽어 들이지 못하도록 하여 교착상태를 예방

디스크를 공유할 때의 교착상태

• 디스크는 대표적인 공유 자원으로, 사용에 대한 제어가 없다면 교착상태가 발생할 수 있음
• 디스크 공유 시 발생하는 교착상태 예
  • 프로세스 P1이 실린더 55의 내용을 읽도록 명령함
  • 디스크 헤드는 실린더 55로 이동, P1은 중지상태가 되고 입출력 채널은 다음 입출력을 요구함
  • 프로세스 P2가 입출력 채널 제어권을 넘겨받아 실린더 245에 위치한 레코드에 쓰기를 명령함
  • 디스크 헤드는 실린더 245로 이동, P2는 중지상태
  • 입출력 채널 제어권은 다시 P1로 이동, P1은 실린더 55의 코드 읽기를 명령함
  • 디스크 헤드는 실린더 55로 이동, P2는 입출력 채널 제어권을 넘겨받아 다시 명령함

네트워크에서의 교착상태

• 네트워크가 붐비거나 입출력(I/O) 버퍼 공간이 부족한 네트워크 시스템이 메시지 흐름을 제어하는 적절한 프로토콜을 가지지 못한 경우 교착상태 발생
• 네트워크에서 발생하는 교착상태 예
  • 화살표는 메시지 흐름을 나타냄
  • 노드 N6, N7에서 출발하여 목적지가 N2인 메시지는 N1의 출력 큐에 임시 저장됨
  • N3, N4에서 출발하여 N1이 목적지인 메시지는 N2의 출력 큐에 임시 저장됨
  • N1의 버퍼 공간이 부족할 때 N1은 N2로부터 메시지를 수신할 수 없음
  • N2의 버퍼 공간이 부족할 때 N1이나 다른 노드로부터 메시지를 수신할 수 없다면, N1과 N2 사 이의 통신 선로는 교착상태에 빠짐
  • N1은 N6, N7로부터 메시지를 전송 받을 수 있으나, N2로 전송이 불가능하므로 교착상태에 빠 짐

교착상태 발생 조건

다음 네 가지 조건이 동시에 발생할 때, 즉 필요충분조건이 성립될 때 발생

상호배제

• 자원이 최소 하나 이상 비공유, 즉 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 함
• 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기해야 함

점유와 대기

• 최소한 자원 하나를 보유하고 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 함

비선점

• 자원은 선점될 수 없음, 즉 자원을 강제로 뺏을 수 없으며 자원을 점유하고 있는 프로세스가 끝나야 해제됨

위의 세 가지 조건으로 발생할 수 있으나, 발생하지 않을 수도 있으며, 교착 상태 발생에는 반드시 아래의 조건이 요구됨

순환대기

• 대기 프로세스 집합 {P0, P1, …, Pn}이 있을 때, P0은 P1이 보유하고 있는 자원을, P1은 P2, P2는 P3, Pn-1은 Pn, Pn은 P0이 보유하고 있는 자원을 각각 얻기 위해 대기하는 경우

교착상태 해결 기법 - 예방

교착상태 해결 기법

교착상태를 해결하는 기법은 크게 3가지로 나뉨

• 시스템이 교착상태가 되지 않도록 예방(방지)하는 것
• 가능한 교착상태를 회피하는 것
• 교착상태를 허용하되 교착상태에서 다시 회복할 수 있게 하는 것

교착상태 예방 기법

4가지의 교착상태 조건 중 하나라도 발생하지 않도록 함

• 상호배제 문제는 고려해야 함
  • 전용자원에서는 교착상태가 발생하지 않으므로 프로세스가 원하는 자원을 배타적으로 사용하려는 것은 제외시켜야 함

하벤더(Havender, 1986년)가 상호배제를 제외한 세 가지 기본방법 제안

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

상호배제 조건 방지

• 상호배제 조건은 자원의 비공유를 전제로 함
  • 공유 가능한 자원들은 배타적인 접근을 요구하지 않으므로 교착상태가 발생하지 않음
• 일반적으로 상호배제 조건을 거부하면 교착상태를 예방하는 것이 불가능함
  • 어떤 자원은 공유 자체가 불가능한 것도 있음
• 파일 쓰기는 배타적인 접근만이 허용되어야 함
  • 하나 이상의 프로세스가 쓰기 권한을 가지면 교착상태가 발생할 가능성이 있음

점유와 대기 조건 방지

• 최대 자원 할당
  • 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 획득해야 함
  • 보류 상태에서는 프로세스가 자원을 점유할 수 없으므로 대기 조건이 성립하지 않음
• 점유와 대기 조건 방지를 위한 두 가지 방법
  • 모든 프로세스는 자원을 요청하고 사용할 수 있음
  • 프로세스가 자원을 더 요청하려면, 먼저 자신에게 할당된 자원을 해제해야 함
    1. 자원 할당 시 시스템 호출된 프로세스 하나의 실행에 필요한 모든 자원을 먼저 할당하여 실행시킨 후 다른 시스템 호출에 자원을 할당함
    2. 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용함
• 단점
  1. 자원의 효율성이 낮음
     • 많은 자원이 사용되지 않으면서 오랜 시간 할당되기 때문
  2. 기아상태 발생이 가능함
     • 자주 쓰는(이용하는) 자원이 다른 프로세스에 할당된 경우, 자원을 요청한 프로세스는 무한히 기다려야 하는 경우가 발생
     • 적은 수의 자원을 요청한 프로세스의 우선순위가 높으므로, 많은 수의 자원을 요청한 프로세스의 대기 시간이 기어질 수 있음

비선점 조건 방지

• 이미 할당 된 자원에 대한 선점권이 없어야 한다는 전제 조건을 가짐
  • 어떤 자원을 가진 프로세스가 자원 요청 시 기다려야 한다면, 프로세스는 현재 가진 자원을 모두 해제함
  • 프로세스가 작업을 시작하려면 요청한 새로운 자원과 해제한 자원을 확보해야 함
  • 작업 상태를 쉽게 저장 및 복구 가능할 때 또는 빈번하게 발생하지 않을 때만 좋은 수단으로 이용 가능
• 두 가지 대안 제시됨
  1. 프로세스가 어떤 자원을 요청 할 때, 요청한 자원이 사용가능한지 검사
  • 사용 가능하다면 자원 할당, 사용 불가능한 경우 대기 프로세스가 요청 한 자원을 점유하고 있는지 검사
  • 요청한 자원을 대기 프로세스가 선점하고 있다면, 자원을 해제하고 요청 프로세스에 할당
  • 요청한 자원을 사용할 수 없거나, 실행 중인 프로세스가 점유하고 있으면 요청 프로세스는 대기
    1. 두 프로세스에 우선순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한 자원을 선점하여 해갈
  • 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후 복원이 쉬운 자원에 이용

순환대기 조건 방지

• 계층적 요구 기법
  • 모든 자원에 일련의 순서를 부여, 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 함
  • 순환대기의 가능성을 제거하여 교착상태를 예방
  • 예상된 순서와 다르게 자원을 요구하는 작업은 자원 낭비를 초래함
• R = {R1,R2, …, Rn}을 자원 형태 집함이라 가정하고, 각 자원 형태에 고유 숫자를 부여
• 1:1 함수인 ‘F:R -> N’으로 정의 가능하며, N은 자연수 집합을 의미함
  1. 프로세스는 임의의 자원 Ri를 요청할 수 있지만 그 다음부터는 ‘F(Rj) > F(Ri)’인 경우에만 자원 형태 Rj를 요청 할 수 있음
     • 각 프로세스는 오름차순으로만 자원들을 요청할 수 있으며, 데이터 형태 자원이 여러 개 필요한 경우 우선 요청할 형태 자원 하나를 정해야 함
  2. 프로세스가 자원 형태 Rj을 요청할 때마다 ‘F(Ri) >= F(Rj)’가 되도록 Rj의 모든 자원을 해제