교착 상태를 위한 필요 조건
1. 상호 배제 (Mutual Exclusion)
정의: 한 번에 하나의 스레드만이 자원을 사용할 수 있습니다. 만약 다른 스레드가 이미 자원을 사용 중이라면, 새로운 요청 스레드는 해당 자원이 해제될 때까지 대기해야 합니다.
예시: 프린터나 파일과 같은 자원이 상호 배제를 필요로 합니다.
주의: 읽기 전용 파일과 같이 여러 스레드가 동시에 접근할 수 있는 자원은 이 조건에 해당하지 않아 교착 상태가 발생하지 않습니다.
2. 점유와 대기 (Hold and Wait)
정의: 자원을 하나 이상 소유하고 있는 스레드가 추가적인 자원을 요청하며, 이 자원들이 현재 다른 스레드에 의해 사용되고 있기 때문에 대기하는 상태입니다.
예시: 한 스레드가 프린터를 소유한 상태에서 스캐너를 요청했지만, 스캐너가 이미 다른 스레드에 의해 사용되고 있어 대기하는 경우입니다.
3. 비선점 (No Preemption)
정의: 스레드가 자원을 자발적으로 해제하기 전까지는, 어떤 스레드도 그 자원을 강제로 빼앗을 수 없는 상태입니다.
예시: 운영체제는 스레드로부터 CPU나 메모리를 선점할 수 있지만, 프린터와 같은 자원은 스레드가 스스로 사용을 마칠 때까지 선점할 수 없습니다.
4. 순환 대기 (Circular Wait)
정의: 점유와 대기 상태에 있는 스레드들이 자원을 요청하는 방향이 순환 형태를 이루는 것입니다.
예시: 스레드 T1이 T2가 가진 자원을 요청하고, T2는 T3가 가진 자원을 요청하며, T3는 다시 T1이 가진 자원을 요청하는 경우입니다.
그래프 표현: **자원 할당 그래프(resource-allocation graph)**로 이 순환 대기 상태를 시각적으로 나타낼 수 있습니다. 이 그래프에 사이클이 존재하면 교착 상태가 발생할 가능성이 있습니다.
자원 할당 그래프
자원 할당 그래프는 교착 상태를 시각적으로 보여주는 데 사용됩니다.
구성:
노드: 원(프로세스)과 사각형(자원 유형)으로 이루어집니다.
화살표: 요청 화살표(request edge)와 할당 화살표(assignment edge) 두 가지가 있습니다.
요청 화살표: 프로세스에서 자원 유형으로 향하며, 프로세스가 자원을 요청했음을 나타냅니다.
할당 화살표: 자원 유형에서 프로세스로 향하며, 자원이 해당 프로세스에 할당되었음을 나타냅니다.
그래프의 사이클:
자원 유형 당 인스턴스가 하나인 경우: 그래프에 사이클이 존재하면 반드시 교착 상태가 발생합니다.
자원 유형 당 인스턴스가 여러 개인 경우: 그래프에 사이클이 존재하더라도 교착 상태가 발생하지 않을 수도 있습니다. 이 경우 사이클은 **교착 상태 발생의 가능성(possibility)**을 나타냅니다.
Last updated