Araina’s Blog

5. 교착 상태와 기아 상태 본문

Develop Study/Operating System

5. 교착 상태와 기아 상태

Araina 2021. 10. 16. 22:24

 

 

1. 교착 상태의 개념과 발생 원인

1.1) 교착 상태(DeadLock)와 기아 상태(Starvation)의 개념

교착 상태란, 결코 일어나지 않을 사건(이벤트)에 대해서 프로세스가 기다리고 있는 것을 말한다.

기아 상태란, 무기한 연기로 인해 아무리 기다려도 자신의 차례가 돌아오지 않는 것을 말한다.

다중 프로그래밍 시스템에서 프로세스들이 한정된 시스템 자원 차지를 위해 경쟁할 때 발생할 수 있다.

교착 상태, 기아 상태는 프로세스가 작업을 수행하지 못하고 무한히 대기한다는 공통점이 있다.

하지만 서로 작업을 수행하지 못하는 원인이 다르다.

 

1.2) 교착 상태 예시

프로세스 A와 B는 스캐너, CD 레코더를 공유한다.

프로세스 A는 스캐너를 할당받고, CD 레코더를 추가로 할당받는다.

프로세스 B는 CD 레코더를 할당받고, 스캐너를 추가로 할당받는다.

이 경우, 서로가 사용 중인 자원을 요청하게 되므로, 사이클이 발생하여 교착 상태에 빠질 수 있다.

이 외에도 스풀링 시스템의 교착 상태, 네트워크에서 발생하는 교착 상태, 장치 할당 요구 시 교착 상태 등이 있다.

 

1.3) 교착 상태가 시스템에 미치는 영향

자원 요구가 뒤엉켜 교착 상태에 빠진 프로세스들은 반납되지 않을 자원을 무한정 기다리게 된다.

이 경우, 작업을 더 이상 진행할 수 없게 되므로, 운영체제가 교착 상태를 해결해주어야 한다.

만약 운영체제가 교착 상태를 해결하지 못하게 되면, 사용자가 직접 프로그램을 종료하는 방법 등으로 해결해야 한다.

 

1.4) 프로세스가 자원을 사용하는 순서

자원의 요청 및 해제는 시스템 호출로 수행한다.

  • 요청: 프로세스가 필요한 자원을 요청한다. 요청이 수락되면 자원을 할당받는다. 요청이 즉시 수락되지 않으면 다른 프로세스가 해당 자원을 사용 중이므로, 할당받을 때까지 대기한다.
  • 사용: 프로세스가 요청한 자원을 점유하여 사용한다.
  • 해제: 프로세스가 자원 사용을 마친 후에는 자원을 반납한다.

 

1.5) 스풀링 시스템의 교착 상태

출력을 시작하기 전에 출력물을 디스크 스풀링 파일에 완전히 보내야 하는 경우, 완료된 작업이 없는데 중간에 스풀링 공간이 모두 차 버리면 교착 상태에 빠지게 된다.

스풀링 시스템의 교착 상태를 해결하는 방법은 다음과 같다.

  • 필요량보다 많은 스풀링 공간을 배당하는 방법: 비용이 많이 소모된다.
  • 포화 임계치를 설정하는 방법: 시스템의 처리량이 줄어들 수 있다.

현대 시스템의 해결책은 스풀링 공간을 동적으로 할당하는 방법이다.

이는 출력물을 전부 내보내기 전에 출력을 시작하도록 하여 가득 찬 스풀링 파일을 비우는 방법이다.

 

1.6) 네트워크에서 발생하는 교착 상태

네트워크가 붐비거나 입출력 버퍼 공간이 부족한 경우, 네트워크 시스템에 메시지 흐름을 제어하는 적절한 프로토콜이 없으면 교착 상태가 발생할 수 있다.

 

1.7) 장치 할당 요구 시 교착 상태

프로세스들이 서로 할당받은 장치들을 요청할 경우, 사이클이 발생하면 교착 상태가 발생할 수 있다.

프로세스 1이 프로세스 2에 할당되어 있는 프린터를 요청하고, 프로세스 2가 프로세스 3에 할당되어 있는 플로터를 요청하고, 프로세스 3이 프로세스 1에 할당되어 있는 테이프 드라이브를 요청하는 형태이다.

 

1.8) 교착 상태 발생 조건

교착 상태가 발생하려면 다음과 같은 4가지 조건을 모두 만족해야 한다.

  • 상호 배제(mutual exclusion): 1번에 1개의 프로세스만 해당 자원 사용 가능.
  • 점유와 대기(hold and wait): 최소한 자원 1개를 차지하고, 다른 프로세스에 할당된 자원을 얻기 위해 대기.
  • 비선점(no-preemption): 자원이 선점될 수 없음. 자원을 점유하고 있는 프로세스가 자원 사용을 마쳐야 해제.
  • 순환 대기(circular wait): 대기 프로세스 집합이 있을 때, P0은 P1이 점유하고 있는 자원을, P1은 P2가 점유하고 있는 자원을 Pn-1은 P0이 점유하고 있는 자원을 대기한다. (점유-대기 사이클 형성)

 

1.9) 순환 대기의 예시

프로세스 집합 = {P0, P1, P2, P3}

자원 집합 = {R0, R1, R2, R3}

 

 

2. 교착 상태 표현

2.1) 자원 할당 그래프

자원 할당 - 요청 관계를 나타내는 방향 그래프 G = (V, E)를 의미한다.

  • 정점 집합 V: 프로세스와 자원
  • 간선 집합 E: <Pi, Rj>와 <Rj, Pi>

자원 할당 그래프에 사이클이 존재하는 경우, 사이클을 구성하는 프로세스와 자원이 교착 상태에 연관되어 있음을 나타낸다.

같은 유형의 자원이 여러 개인 경우에도 교착 상태가 발생할 수 있다.

사이클이 있으면서 교착 상태인 예는 다음과 같다.

사이클은 있으나, 교착 상태가 아닌 예는 다음과 같다.

같은 유형의 자원이 여려 개인 경우, 사이클이 발생한다고 해서 항상 교착 상태가 발생하는 것은 아님에 주의하자.

 

 

3. 교착 상태 해결 방법

교착 상태 예방(DeadLock Prevention)

  • 교착 상태가 절대 일어나지 않도록 방지한다.
  • 명쾌하지만, 자원 활용도가 떨어진다.

교착 상태 회피(DeadLock Avoidance)

  • 시스템 내 교착 상태 가능성은 있으나, 교착 상태를 회피한다.
  • 회피 알고리즘 실행으로 시스템 부하가 가중된다.

교착 상태 탐지와 회복(DeadLock Detection and Recovery)

  • 교착 상태 발생을 허용하되, 교착 상태를 알아내고 교착 상태로부터 벗어나 회복할 수 있게 한다.
  • 교착 상태 탐지 알고리즘 실행으로 시스템에 부하가 가중된다.
  • 교착 상태 회복 과정에서, 수행한 작업의 손실이 발생한다.

1가지 방법만으로 시스템의 모든 자원 할당 문제를 해결하는 것은 불가능하다.

예방, 회피, 탐지와 회복 3가지 방법을 결합하여 자원의 형태에 따라 최적의 접근 방법을 채택해야 한다.

교착 상태 필요조건 4가지 중, 1개만 방지해도 교착 상태를 예방할 수 있다.

 

3.1) 교착 상태 예방 (DeadLock Prevention)

하벤더가 제안한 3가지 교착 상태 예방법은 다음과 같다.

  • 점유와 대기(Hold and Wait) 조건 방지
  • 비선점(No-Preemption) 조건 방지
  • 순환 대기(Circular wait) 조건 방지

교착 상태 발생 조건 중, 상호 배제(mutual Exclusion) 조건에 대한 방지법은 제외한다.

교착 상태 문제는 한순간에 프로세스를 하나만 사용할 수 있는 자원이기 때문이다.

이 때문에 상호 배제 조건(한 번에 한 개의 프로세스만 자원 사용 가능) 방지는 사실상 불가능하며 무의미하다.

 

3.2) 점유와 대기 (Hold and Wait) 방지 방법

점유와 대기(Hold and Wait) 방지 방법은 프로세스가 자원을 점유한 채로 다른 자원을 기다리는 일을 없애는 방법이다.

즉, 자원을 점유한 프로세스는 추가 자원을 요청할 수 없도록 한다.

각 프로세스는 필요한 모든 자원을 한 번에 요청해야 한다.

요청한 자원을 모두 할당받기 전까지는 작업 진행이 불가능하다.

많은 자원이 사용되지 않으면서 오랜 시간 할당되어 있어야 하므로, 자원 효율이 떨어진다.

기아 상태가 발생할 수 있어 대화식 시스템에서 사용이 불가능하다.

자주 이용하는 자원이 다른 프로세스에 할당된 경우, 자원을 요청한 프로세스는 모든 자원이 동시에 빌 때까지 무기한 대기해야 하는 경우가 생길 수 있다.

적은 수의 자원을 요청한 프로세스가 유리하므로, 많은 수의 자원을 요청한 프로세스의 대기 시간이 길어질 수 있다.

  • 변형된 방법: 자원을 추가 요청하기 전, 점유 중인 모든 자원을 일단 해제한다.

 

3.3) 비선점(No-Preemption) 조건 방지

비선점(No-Preemption) 조건 방지는 프로세스가 점유한 자원을 강제로 해제할 수 있도록 하는 방법이다.

어떤 자원을 점유한 프로세스가 추가 자원 요청 시 기다려야 한다면, 프로세스는 현재 점유한 자원을 모두 해제한다.

작업 상태를 쉽게 저장, 복구 가능할 때 사용할 수 있는 방법이다.

프린터, 테이프 드라이브 같은 자원에는 적용하지 않는다.

자원 해제가 필요한 상황이 빈번하게 발생하지 않을 때만 이용 가능한 방법이다.

  • 변형된 방법: 프로세스에 우선순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한 자원을 빼앗을 수 있도록 한다.

 

3.4) 순환 대기(Circular wait) 조건 방지

순환 대기(Circular wait) 조건 방지는 특정 순서대로만 자원을 요청하게 함으로써, 자원 할당 그래프에 사이클이 형성되지 않게 하는 방법이다.

모든 자원에 일련의 순서(번호)를 부여하고, 각 프로세스는 이 번호 오름차순으로만 자원을 요청할 수 있다.

자신이 가지고 있는 자원보다 높은 값의 자원은 사용할 수 없다.

만약 프린터와 CD 드라이브를 함께 사용해야 하는 프로세스이며 CD 드라이브가 프린터보다 순서가 높다면, CD 드라이브를 먼저 요구한 뒤, 프린터를 요구해 사용해야 한다.

이로 인해 주어진 순서와 다르게 자원을 필요로 하는 프로세스의 경우, 불필요한 자원을 미리 할당받게 되므로 자원의 낭비가 발생할 수 있다.

또한 우선순위에 따라 자원에 번호를 부여할 경우, 실제로 사용하는 순서를 반영해야 하는 수고가 필요하다.

  • 변형된 방법: 자원 Rj를 요청할 때, 이보다 번호가 높은 자원은 일단 해제한다.

 

3.5) 교착 상태 회피(DeadLock Avoidance)

교착 상태 예방보다 덜 엄격한 조건을 요구한다.

자원을 더 효율적으로 이용하고, 병행성을 더 허용한다.

교착 상태가 일어날 가능성을 인정하고, 교착 상태가 일어나지 않도록 회피한다.

가용 자원이 있더라도, 요청한 자원을 할당하면 교착 상태가 발생할 위험이 있는 경우 요청을 거절한다.

교착 상태를 회피하기 위해서는 자원 요구에 대한 추가 정보가 필요하다.

자원 할당 상태는 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의해 정의된다.

필요한 정보의 양과 종류에 따라 다음과 같은 다양한 교착 상태 회피 알고리즘을 적용할 수 있다.

  • 자원 할당 그래프 알고리즘
  • 은행가 알고리즘

교착 상태 회피 방법을 사용할 경우, 시스템은 아래의 2가지 상태 중 1개를 가질 수 있다.

  • 안정 상태(stable state): 각 프로세스에 자원을 최대 요구 수까지 할당할 수 있어 교착 상태를 피할 수 있다.
  • 불안정 상태(unstable state): 프로세스의 안정 순서가 존재하지 않는 상태이다.

어떤 시점에 시스템이 안정 상태임을 보이려면 안정 순서가 존재함을 보이면 된다.

안정 순서란, 그 시점부터 시작해 최악의 경우에도 모든 프로세스가 작업을 완료할 수 있는 프로세스 순서를 말한다.

프로세스 순서 <P1, P2, P3, ~, Pn>이 안정 순서라는 뜻은 Pi의 최대 자원 요청이 다음 2가지를 합해 충족될 수 있음을 의미한다.

  • 현재 사용 가능한 자원
  • i보다 앞선(j < i) 모든 Pj가 점유하고 있는 자원들

프로세스 Pi가 필요한 자원을 즉시 사용할 수 없다면 Pi는 모든 Pj가 끝날 때까지 기다렸다가 자원을 확보하며 필요한 모든 자원 확보 시 작업을 완료하고 자원을 반납한다.

 

3.6) 자원 할당 그래프 알고리즘

자원 할당 그래프 알고리즘은 프로세스들이 미리 필요한 자원의 요구를 알리는 알고리즘이다.

프로세스들의 자원 요구 사항을 허가했을 때, 사이클이 생성될 수 있는지를 판단한다.

사이클이 생성된다면, 교착 상태가 발생할 가능성이 있으므로, 요구를 거부한다.

교착 상태는 불안정 상태일 때 발생하지만, 불안정 상태라고 해서 무조건 교착 상태인 것은 아니다.

시스템이 안정 상태를 유지하도록 자원 할당 요청을 처리하여 교착 상태를 피해가야 한다.

이를 집합 관계로 표현하면 다음과 같다.

안정 상태 예시는 다음과 같다.

프로세스가 현재 사용량에서 최대 사용량까지 추가 요구량에 맞춰 자원을 요구하여도, 여분 자원 수에서 자원을 할당해줄 수 있다.

불안정 상태 예시는 다음과 같다.

안정 순서가 존재하지 않으므로, 교착 상태 발생 위험이 있다.

물론, 여기서도 교착 상태가 발생하지 않을 수도 있다.

  • P2가 자원 2개를 할당받아 실행 완료
  • P3이 자원 1개 반납
  • P0이 자원 5개 할당받아 실행 완료
  • P1 실행 완료
  • P3 실행 완료

 

3.7) 은행가 알고리즘

은행가 알고리즘은 은행에서 모든 고객이 만족하도록 현금을 할당하는 과정과 유사하여 붙은 이름의 알고리즘이다.

각 프로세스가 자원 종류별 최대 요청 수를 파악, 자원 요청이 있을 때마다 다음과 같이 결정한다.

  • 요청을 수락해도 안정 상태를 유지할 수 있다면, 요청을 수락한다.
  • 요청을 수락하면 불안정 상태로 변한다면, 요청을 거절한다.

은행가 알고리즘은 프로세스 수, 자원 수가 일정해야 사용 가능하다.

각 프로세스가 요청할 자원 유형별 최대치 정보를 미리 파악해야 한다.

프로세스가 자원을 요청할 때마다 교착 상태 회피 알고리즘을 수행해야 하므로 시스템 부하가 증가한다.

교착 상태 회피 방법은 교착 상태 해결 방법 중에서 시스템 부하 문제가 가장 심하다.

불안정 상태를 방지해야 하므로 자원 이용도가 낮다.

요청하는 자원이 충분해도, 불안정 상태를 막기 위해 요청을 거부할 수 있기 때문이다.

은행가 알고리즘 작동 예시는 다음과 같다.

프로세스: 5개

자원 종류: 3종류 (A: 10개, B: 5개, C: 7개)

현재 할당 상태: A = 7개, B = 2개, C = 5개

  • Available: 332로 할당 가능한 Need: P1, P3
  • P1 할당 후 작업 종료 시, 반환: 332 + 200 = 532
  • Available: 532로 할당 가능한 Need: P3, P4
  • P3 할당 후 작업 종료 시, 반환: 532 + 211 = 743
  • Available: 743로 할당 가능한 Need: P0, P2, P4
  • P0 할당 후 작업 종료 시, 반환: 743 + 010 = 753
  • Available: 753로 할당 가능한 Need: P2, P4
  • P2 할당 후 작업 종료 시, 반환: 753 + 302 = 1055
  • Available: 1052로 할당 가능한 Need: P4
  • P4 할당 후 작업 종료 시, 반환: 1055 + 002 = 1057

프로세스: 5개

자원 종류: 3종류 (A: 10개, B: 4개, C: 7개)

현재 할당 상태: A = 8개, B = 4개, C = 7개

  1. Available: 210로 할당 가능한 Need: 없음
  2. Available로 프로세스들의 자원 요구를 만족시킬 수 없으므로, 교착 상태가 발생할 수 있는 불안정 상태.

 

3.8) 교착 상태 탐지(DeadLock Detection)

교착 상태 존재 여부를 알아내고, 연관된 프로세스 및 자원을 알아내는 방법.

순환 대기(Circular wait) 존재 여부에 초점을 맞춘다.

교착 상태 탐지 알고리즘 2가지는 다음과 같다.

  1. 자원 할당 그래프 소거(Reduction of Resource Allocation Graph) 알고리즘
  2. 쇼사니와 코프만의 교착 상태 탐지 알고리즘

탐지 알고리즘 호출 문제는 교착 상태 발생 빈도 수와 교착 상태 발생 시 영향을 받는 프로세스의 수에 따라 결정된다.

교착 상태가 발생하면 해결될 때까지 프로세스에 할당된 자원들은 유휴 상태가 되고, 교착 상태에 연관된 프로세스 수가 점점 늘어난다.

프로세스가 유휴 상태가 되면 CPU가 작업을 진행할 수 없게 되므로 CPU 이용률이 하락한다.

교착 상태 탐지 알고리즘을 자주 호출하면 연관 프로세스 수 증가 문제를 해결할 수 있으나, 시스템 부하 또한 증가한다.

지나친 시스템 부하를 막기 위한 경제적인 방법은 교착 상태 탐지 알고리즘 호출 빈도를 줄이는 것이다.

 

3.9) 자원 할당 그래프 소거 알고리즘

자원 할당 그래프 소거 알고리즘은 어떤 프로세스의 자원 요청을 수락할 수 있으면, 그 프로세스에 의해 그래프가 소거될 수 있도록 하는 알고리즘이다.

해당 프로세스는 실행을 마치고 자원을 반납할 수 있는 프로세스이다.

그래프 소거란, 프로세스에서 자원으로 향한 화살표와 자원에서 프로세스로 향한 화살표를 모두 제거하는 것을 말한다.

모든 프로세스에 의해 그래프가 소거될 수 있으면, 교착 상태는 일어나지 않는다.

자원 할당 그래프 소거 알고리즘의 예시는 다음과 같다.

P1은 R1의 자원을 요청하였고, 할당받을 수 있으므로 소거된다.

P2는 R2의 자원을 사용하였고, 다른 프로세스의 요청이 없으므로 소거된다.

P3는 P4가 사용 중인 R3를 요청하였으므로, P4의 작업이 종료될 때까지 대기 후에 할당받는다. 이때 사이클이 발생하지 않았으므로 P3와 P4 모두 소거된다.

P7, P9, P8은 서로 사이클을 형성하고 있으나, 모두 R6와 R7에서 자원을 할당받아 작업을 종료할 수 있으므로 소거된다.

P5, P6는 서로 R5와 R4를 사이클을 형성해 요청하고 있으며, R4와 R5가 각각 할당할 수 있는 자원의 수가 1개뿐이므로 순환 대기 상태(교착 상태)에 빠지게 되어 소거될 수 없다.

 

3.10) 쇼사니와 코프만의 교착 상태 탐지 알고리즘

쇼사니와 코프만의 교착 상태 탐지 알고리즘은 현재 자원의 할당 상태에 관한 정보를 관리하고, 이 상태 정보에 의해 교착 상태 여부를 판단할 수 있는 알고리즘을 말한다.

쇼사니와 코프만의 교착 상태 탐지 알고리즘 작동 예시는 다음과 같다.

프로세스 처리 순서: P0, P2, P3, P1, P4

Available 자원으로 모든 프로세스의 자원 요구를 해결할 수 있으므로, 교착 상태가 발생하지 않는다.

P0이 작업을 완료하고 점유 자원을 반납하더라도, P1, P2, P3, P4의 자원 요구를 해결할 수 없다.

이로 인해 P1, P2, P3, P4가 연관된 교착 상태가 발생한다.

 

3.11) 교착 상태 회복(DeadLock Recovery)

교착 상태에서 회복한다는 것은 순환 대기 상태에서 벗어난다는 것을 의미한다.

교착 상태 회복은 특정 프로세스를 강제로 제거하거나, 자원 반납을 요구하므로, 보통 수행한 작업을 잃는다.

교착 상태 회복 기법으로는 다음과 같이 2가지가 있다.

  • 프로세스 중지: 교착 상태인 프로세스들 중 1개 이상을 중지하는 방법.
  • 자원 선점: 교착 상태인 프로세스들로부터 자원을 빼앗는 방법.

 

3.12) 프로세스 중지

프로세스 중지에는 2가지 방법이 있으며, 모두 시스템이 중지된 프로세스에 할당된 모든 자원의 해제를 요구한다.

  • 교착 상태 프로세스 모두 중지: 교착 상태의 순환 대기를 확실하게 해결할 수 있다. 자원 사용과 시간 면에서 비용이 크게 든다.
  • 한 프로세스씩 중지 (부분 종료 방식): 프로세스 1개가 중지될 때마다 교착 상태 탐지 알고리즘을 호출하여 프로세스의 교착 상태 여부를 확인한다. 교착 상태 탐지 알고리즘 호출 부담이 크다. 어느 프로세스를 중지할지 결정해야 한다.

한 프로세스씩 중지하는 방법의 경우, 일반적으로 다음과 같이 중지할 프로세스들을 선정하는 기준이 존재한다.

  • 프로세스 우선순위가 낮은 것부터 중지
  • 프로세스가 수행된 시간, 앞으로 종료하는 데 필요한 시간이 낮은 것부터 중지
  • 프로세스가 사용한 자원의 형태와 수: 중단 가능한 자원을 차지하고 있는 프로세스부터 중지
  • 프로세스 종료에 필요한 자원 수: 자원 수가 적은 프로세스부터 중지
  • 중지해야 할 프로세스 수가 적은 것부터 중지
  • 프로세스가 대화식인지, 일괄식인지 여부: 일괄식부터 중지

 

3.13) 자원 선점

자원 선점이란, 교착 상태가 해결될 때까지 프로세스의 자원을 빼앗아 다른 프로세스에 할당해주는 방법을 말한다.

자원 선점을 위해서는 다음과 같은 3가지 사항들을 해결해야 한다.

  • 선점 자원 선택: 비용을 최소화하기 위해 적절한 선점 순서를 결정해야 한다.
  • 복귀: 자원을 빼앗긴 프로세스는 정상 실행이 불가능하므로, 프로세스를 안전한 상태로 복귀 후 다시 시작해야 한다. 시스템이 실행하는 모든 프로세스의 상태 정보를 유지해야 하는 부담이 존재한다.
  • 기아: 비용에 근거한 시스템에서는 동일한 프로세스가 반복하여 희생자로 선택되기 쉽다. 프로세스가 짧은 시간 동안 희생자로 선택됨을 보장해야 한다. 일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함하는 것이다.

 

 

4. 기아 상태

기아 상태란, 프로세스가 작업을 수행하지 못하고 무한히 기다리는 상태를 말한다.

교착 상태와 다르다는 것에 주의하자.

현실적으로 수행할 수 있는 작업이지만, 무기한 연기로 인해 수행할 수 없는 상태에 빠지는 것.

프로세스의 우선순위에 따라 자원을 할당할 경우, 우선순위가 낮은 프로세스들은 기아 상태에 빠질 수 있다.

기아 상태를 해결하기 위한 방안으로는 에이징(aging)이 있다.

에이징이란, 어떤 자원을 오래 대기할수록 해당 프로세스의 우선순위를 높여주는 방법이다.

 

4.1) 식사하는 철학자 문제

병행 프로세스와 교착 상태, 기아 상태를 설명하는 프로세스 동기화 문제.

문제는 다음과 같다.

  • 5명의 철학자는 생각과 식사를 반복한다.
  • 테이블 중앙에는 음식이 있다.
  • 철학자들 사이에는 포크 5개가 1개씩 놓여 있다.
  • 철학자들은 좌우의 포크를 공유한다.
  • 모든 철학자들은 1개의 포크를 2명이서 동시에 사용할 수 없다.
  • 식사할 때는 각자의 좌우 포크 2개를 사용한다.
  • 식사를 마치면 포크를 내려놓고 생각을 시작한다.

식사하는 철학자 문제의 교착상태 해결책은 기아 상태를 방지해야 한다.

교착 상태를 방지하는 과정에서 철학자 중 1명이라도 굶어 죽는 일(기아 상태)이 없어야 한다.

교착 상태 해결책은 기아 상태 가능성을 제거할 수 없다.

기아 상태를 해결하기 위해서는 먼저 기다리는 작업을 발견하고, 각 작업이 기다린 시간을 추적 조사해야 한다.

시스템이 기아 상태를 발견하면 즉시 새로운 작업의 시작을 대기하도록 조치해야 한다.

이 경우, 빈번한 시스템 대기로 처리량 감소 가능성이 있다.

여기서는 세마포어를 이용하여 식사하는 철학자 문제를 해결해본다.

포크를 세마포어로 표시하여 상호 배제(한 번에 한 개의 포크만 사용 가능)를 구현한다.

포크를 양쪽 철학자 2명이 동시에 사용할 수 없으므로, 각 포크에 대한 상호 배제가 필요하다.

// 5개의 세마포어로 이루어진 배열 선언
semaphore fork[5] = {1};

각 세마포어(포크)는 1로 초기화한다.

철학자가 포크를 집으려면, 세마포어에 대한 P연산을 수행한다.

철학자가 포크를 내려놓으려면, 세마포어에 대한 V 연산을 수행한다.

  • 철학자 2가 최초로 fork[2]와 fork[3]을 집어서 식사를 시작한다.
  • 철학자 3이 식사를 시작하려면, fork[3]과 fork[4]를 집어야 한다.
  • 철학자 3은 철학자 2가 이미 P연산을 통해 fork[3]을 집었으므로, 식사를 시작할 수 없다.
  • 철학자 2가 V연산을 통해 fork[2]와 fork[3]을 내려놓으면, 철학자 3이 식사를 시작할 수 있다.
// 세마포어 포크 배열을 1로 초기화
semaphore fork[5] = {1};

while (true) {
    // P 연산 //
    wait(fork[i]);       // 왼쪽 포크를 집음
    wait(fork[i+1]%5]);  // 오른쪽 포크를 집음
    
    /* 식사 한다 */
    
    // V 연산 //
    signal(fork[i]);      // 완쪽 포크를 내려둠
    signal(fork[i+1]%5);  // 오른쪽 포크를 내려둠
    
    /* 생각 한다 */
}

세마포어를 이용한 식사하는 철학자 문제 해결법은 아래와 같이 교착 상태가 발생할 수 있다.

5명의 철학자들이 동시에 모두 왼쪽 포크를 먼저 집어 들고, 오른쪽 포크를 집으려고 하는 경우 교착 상태가 발생한다.

교착 상태 예방을 위한 몇 가지 해결책은 다음과 같다.

  • 철학자 4명만 테이블에 동시에 앉도록 하는 방법: 프로세스 1개를 강제로 줄임으로써, 사이클 형성 원인을 원천 차단한다.
  • 철학자가 양쪽 모든 포크를 집을 수 있을 때만 포크를 집도록 허용하는 방법: 양쪽 포크는 1번 잡을 때 무조건 동시에 잡을 수 있도록 제한하여 포크 1개만 집는 경우를 예방한다. 양쪽 포크를 동시에 잡는 작업은 임계 영역 내에서 이루어져야 한다.
  • 비대칭 해결법: 홀수 번째 철학자는 왼쪽 포크를 집은 후에 오른쪽 포크를 집을 수 있다. 짝수 번째 철학자는 오른쪽 포크를 집은 후에 왼쪽 포크를 집을 수 있다.

철학자 4명만 테이블에 동시에 앉도록 하는 방법을 코드로 구현하면 아래와 같다.

// 세마포어 room: 좌석 4개 제한
semaphore room = 4;
semaphore fork[5] = {1};

while (true) {
    wait(room);        // 좌석 P 연산
    wait(fork[i]);     // 왼쪽 포크
    wait(fork[i+1]%5); // 오른쪽 포크
    
    /* 식사 한다. */
    
    signal(fork[i+1]%5);
    signal(fork[i]);
    signal(room);   
}

철학자가 양쪽 포크 모두 사용 가능할 때 포크를 집도록 허용하는 방법은 아래와 같다.

  • P0가 f1과 f0를 동시에 할당받는다.
  • P3가 f3와 f4를 동시에 할당받는다.
  • P1은 f1이 이미 P0에게 할당되어 있으므로, 식사를 할 수 없다.
  • P2는 f3가 이미 P3에게 할당되어 있으므로, 식사를 할 수 없다.
  • P4는 f4와 f0이 이미 P3, P0에게 할당되어 있으므로, 식사를 할 수 없다.

비대칭 해결법을 사용하는 방법은 아래와 같다.

  • P0은 오른쪽 포크, f1 할당을 요청한다.
  • P1은 왼쪽 포크, f1 할당을 요청한다.
  • P2는 오른쪽 포크, f3 할당을 요청한다.
  • P3는 왼쪽 포크, f3 할당을 요청한다.
  • P4는 오른쪽 포크, f0 할당을 요청한다.
  • f1과 f3는 할당 기준에 따라 두 철학자 중 1명에게만 돌아간다.

 

 

수고하셨습니다!

 

저작자표시 비영리 변경금지

'Develop Study > Operating System' 카테고리의 다른 글

7. 메모리 관리  (0) 2021.11.12
6. 프로세스 스케줄링  (0) 2021.11.04
4. 병행 프로세스와 상호 배제  (0) 2021.10.12
3. 프로세스와 스레드  (0) 2021.10.12
2. 운영체제  (0) 2021.10.12
'Develop Study/Operating System' Related Articles more
Comments