대기 그래프

컴퓨터 과학에서 대기 그래프는 운영 체제와 관계형 데이터베이스 시스템의 교착 상태 탐지에 사용되는 지시된 그래프다.

컴퓨터 과학에서, 복수의 프로세스의 동시 운용과 자원 잠금을 허용하고 교착상태를 피하거나 방지할 수 있는 메커니즘을 제공하지 않는 시스템은 교착 상태를 감지하는 메커니즘과 그것들로부터 회복하기 위한 알고리즘을 지원해야 한다.

이러한 교착 상태 탐지 알고리즘 중 하나는 대기 그래프를 사용하여 프로세스가 현재 차단 중인 다른 프로세스를 추적한다.대기 그래프에서 프로세스는 노드로 표시되며, 프로세스 $P{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$에서 $프로세스$ P ${\displaystyle i_{}}$ ${\$에 이르는 $에지$는 P ${\displaystyle j_{}}${\$displaystyle P_{j$$}}}}$이(가$)$ 필요로 하는 리소스를 보유하므로$$ ${\displaystyle {Pi}_{}}$ ${\$가 P_{i}를 기다리고 있음을$$ 의미한다$$.${\displaystyle P_{j}}$을(를) 사용하여 해당 리소스에 대한 잠금을 해제하십시오.프로세스가 단일 자원 이상을 사용할 수 있게 되기를 기다리는 경우(사소한 경우), 복수의 가장자리는 서로 다른 자원 또는 컬렉션의 특정 수의 동등한 자원의 결합(및) 또는 이절(또는) 집합을 나타낼 수 있다.교착의 가능성은 결막 케이스의 그래프 사이클과 이격 케이스의 매듭에 의해 암시된다.최종 사례에서 교착 가능성을 감지할 수 있는 간단한 알고리즘은 없다.^[1]

각 리소스 유형의 여러 인스턴스가 있는 리소스 할당 시스템에는 그래픽 대기 방식이 적용되지 않는다.

참조

이 컴퓨터 과학 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t