[Part2-공룡책] 6. 교착상태(1/2) - Operating System(OS)

Operating System(OS)에 이어서 Part2에는  다음과 같은 순서*로 알아보겠습니다.
*공룡책을 기반

[프로세스 관리]
1. 프로세스
2. 스레드와 병행성
3. CPU 스케줄링
[프로세스 동기화]
4. 프로세스동기화
5. 동기화 예제
6. 교착상태
[메모리 관리]
7. 메인 메모리
8. 가상 메모리
[저장장치 관리]
9. 대용량 저장장치 구조
10. 입출력 시스템
[파일시스템]
11. 파일시스템 
12. 파일시스템 구현

 

LG 울트라PC 15U560 6세대 i5 지포스940M 15.6인치 윈도우10

* 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받을 수 있습니다.

 

Operating System(OS) Part2 - 6. 교착상태(1/2)

1. 시스템 모델 (System Model)
운영체제에서 교착 상태(Deadlock)는 여러 프로세스가 서로 다른 자원을 대기하면서 무한히 기다리게 되는 상태를 의미합니다. 이를 이해하기 위해 시스템 모델을 정의할 필요가 있습니다. 시스템 모델은 프로세스와 자원의 관계를 나타내며, 이를 통해 교착 상태의 발생 여부를 분석할 수 있습니다.

• 프로세스 (Process): 실행 중인 프로그램의 인스턴스.
• 자원 (Resource): 프로세스가 작업을 수행하기 위해 필요한 요소들로, CPU 사이클, 메모리, 파일, I/O 장치 등이 있습니다.
• 자원 유형 (Resource Type): 자원은 특정 유형에 따라 분류되며, 각 유형에는 여러 인스턴스가 있을 수 있습니다. 예를 들어, 프린터는 하나의 자원 유형이고, 두 대의 프린터는 두 개의 인스턴스입니다.
• 자원 요청 및 할당: 프로세스는 자원을 요청하고, 운영체제는 이를 할당합니다. 프로세스는 자원을 해제할 수도 있습니다.

 

2. 교착상태 특징 (Deadlock Characterization)
교착 상태는 네 가지 조건이 모두 성립할 때 발생합니다. 이를 교착 상태의 필요 조건이라고 합니다.

2.1 Deadlock 발생 조건
1) 상호 배제 (Mutual Exclusion): 자원의 한 인스턴스는 한 번에 하나의 프로세스만 사용할 수 있습니다.
2) 점유와 대기 (Hold and Wait): 최소한 하나의 자원을 점유하면서 다른 자원을 추가로 요청하여 대기 중인 프로세스가 있어야 합니다.
3) 비선점 (No Preemption): 자원을 강제로 빼앗을 수 없고, 자원을 점유한 프로세스가 자원을 자발적으로 해제할 때까지 기다려야 합니다.
4) 순환 대기 (Circular Wait): 자원 요청 프로세스들이 원형 형태로 서로의 자원을 기다리는 상태가 되어야 합니다.

 

3. 자원 할당 그래프 (Resource Allocation Graph)
자원 할당 그래프는 교착 상태를 시각적으로 분석하는 도구입니다. 이 그래프는 다음과 같이 구성됩니다.

• 노드 (Node): 두 종류의 노드가 있습니다. 프로세스 노드 𝑃𝑖Pi​와 자원 유형 노드 𝑅𝑗Rj​.
• 에지 (Edge):
  • 요청 에지 (Request Edge): 프로세스에서 자원으로 향하는 화살표로, 프로세스가 자원을 요청하고 있음을 나타냅니다.
  • 할당 에지 (Assignment Edge): 자원에서 프로세스로 향하는 화살표로, 자원이 프로세스에 할당되었음을 나타냅니다.

                                                                                     P는 프로세스, R은 리소스.

즉, P -> R은 요청 간선(Request Edge)이고, R -> P는 할당 간선(Assignment Edge).

자원 할당 그래프에서 사이클이 없다면 어느 프로세스도 교착상태(Deadlock)가 생기지 않습니다.

반면 사이클이 있다면 교착상태가 발생할 수 있지만 100%는 아닙니다. 각 resource type이 여러개의 instance를 가지면 사이클이라고 해서 반드시 교착상태가 발생했을음 의미하지는 않습니다. 

교착 상태가 발생하는지 확인하기 위해 이 그래프를 분석합니다. 순환 대기 조건을 그래프에서 확인할 수 있다면 교착 상태가 존재합니다.