deadlock – 교착상태

교착상태는 동일한 자원을 공유하고 있는 두 개의 컴퓨터 프로그램들이, 상대방이 자원에 접근하는 것을 사실상 서로 방해함으로써, 두 프로그램 모두 기능이 중지되는 결과를 낳는 상황을 말한다. 초창기의 컴퓨터 운영체계들은 한번에 오직 한 개의 프로그램만을 실행시킬 수 있었다. 시스템의 모든 자원들은 하나의 프로그램만이 사용할 수 있었다. 후에, 운영체계의 발전으로 한번에 여러 개의 프로그램들을 실행할 수 있게 되었다. 프로그램들은 동시에 실행되고 있는 다른 프로그램과 충돌이 일어나지 않도록, 사전에 자신이 필요로 하는 자원을 명시해야 했다. 결국, 일부 운영체계들은 자원의 동적 할당 기능을 제공하였다. 프로그램들은 실행이 시작된 후, 그 이상의 자원 할당을 요구할 수 있었는데, 결국 이것이 교착상태의 문제를 만들었다. 아래에 간단한 예제가 있다. 프로그램 1이 자원 A를 요청하여, 그것을 할당받았다. 프로그램 2가 자원 B를 요청하여, 그것을 할당받았다. 프로그램 1이 자원 B를 추가로 요청하였으나, 자원 B가 다른 프로그램에 의해 사용 중이므로, 사용 가능한 상태가 될 때까지 대기 열에서 기다리고 있다. 프로그램 2가 자원 A를 추가로 요청하였으나, 자원 A가 다른 프로그램에 의해 사용 중이므로, 사용 가능한 상태가 될 때까지 대기 열에서 기다리고 있다.