교착상태란 무엇이며, 교착상태에 대처하는 방법

동시 프로그래밍에서 교착 상태는 매우 일반적인 논리 오류입니다. 올바른 프로그래밍 방법을 채택하면 교착 상태를 방지하는 것이 어렵지 않습니다.

교착상태의 4가지 필요조건

컴퓨터공학 학부 교과서에는 일반적으로 교착상태의 4가지 필요조건이 소개되어 있습니다. 이 네 가지 조건은 반드시 필요하며, 이 중 어느 하나라도 위반하면 교착상태가 발생할 수 없습니다. 검토해 보면 이 네 가지 조건은 다음과 같습니다.

?상호 배제: 특정 시간에 하나의 실행 스레드(스레드라고도 함)에만 할당할 수 있는 리소스가 있습니다. Hold(Hold 및 대기): 요청된 리소스가 점유되고 실행 스레드가 차단되면 리소스 점유자는 리소스를 해제할 필요가 없을 뿐만 아니라 계속해서 더 많은 리소스를 요청할 수도 있습니다. 선점 없음(No preemption): 상호 배타적인 리소스입니다. 실행 스레드에 의해 획득된 자원은 강제로 박탈될 수 없습니다. 즉, 자원 점유자만이 자원을 해제할 수 있습니다. 순환 대기: 여러 실행 스레드가 서로 다른 순서로 상호 배타적인 자원을 획득하여 순환 체인을 형성하는 상황을 상상해 보십시오. 여러 스레드로 구성된 각 스레드는 다음 스레드가 보유하고 있는 리소스를 해제할 때까지 기다리고 있습니다.

교착상태 해제의 필요조건

교착상태의 4가지 필요조건 중 두 번째, 세 번째, 네 번째 조건은 상대적으로 제거하기 쉽다는 것을 어렵지 않게 볼 수 있습니다. 트랜잭션 메커니즘을 도입하면 모든 잠금 작업을 트랜잭션으로 처리하여 두 번째 및 세 번째 조건을 제거할 수 있습니다. 잠금이 시작되면 모든 작업이 롤백되고 잠금 관리자를 통해 교착 상태가 감지됩니다. 리소스 박탈(트랜잭션 롤백) 이 접근 방식은 때때로 더 큰 오버헤드를 초래하고 잠금 모델에 더 많은 변경이 필요합니다.

네 번째 조건을 제거하는 것이 더 쉽고 비용도 저렴합니다. 특히 이 방법은 잠금 순서가 일관되어야 한다는 점에 동의합니다. 구체적으로 우리는 "수위"와 유사한 자물쇠에 방향 속성을 인위적으로 할당합니다. 이미 보유하고 있는 잠금에 관계없이 이 스레드의 모든 잠금 작업은 낮은 순서에서 높은 순서(또는 높은 순서에서 낮은 순서)로 수행되어야 하며 시스템에서는 한 가지 순서만 허용됩니다.

잠금이 해제되는 순서는 교착상태를 일으키지 않는다는 점에 유의하세요. 즉, A 잠금, B 잠금, A 잠금, B 잠금 순으로 잠금 작업을 수행하는 것이 이상하게 보일 수 있지만, 모두 A, B 순으로 잠금을 수행하는 한 교착 상태는 발생하지 않습니다.

예

세 개의 개체 A, B, C가 있다고 가정합니다. 잠금 순서는 A, B, C 순으로 인위적으로 동의합니다.

예를 들어, 다음 잠금 시퀀스는 적법합니다:

? Lock C, put C. Lock B, put B. Lock B, lock C, put B, put C. Lock B, lock C, put C , B 잠금 A 넣기, A 넣기 잠금 A, C 잠금, A 넣기, C 넣기 A 잠금, C 잠그기, C 넣기, A 넣기 A 잠금, B 잠그기, A 넣기, B 넣기 A 넣기, B 잠그기, B 넣기, put A Lock A, lock B, lock C, put A, put B, put C Lock A, lock B, lock C, put C, put B, put A

위에 정의된 시스템에서는 교착 상태를 일으키는 일반적인 잠금 순서는 다음과 같습니다:

? Lock B, lock A, lock C, put C, put A, put B

(B가 먼저이고 그 다음이 A이기 때문입니다) 잠금 순서가 잠금 순서 계약을 위반하는 경우 다른 실행 스레드가 A와 B의 순서로 동시에 잠금을 수행하면 실행 스레드 A가 B를 획득하고 실행 스레드 B가 A를 획득하여 두 당사자 모두 기다리게 되기 때문일 수 있습니다. 상대방이 동시에 잠금을 해제합니다. 잠금이 발생하여 교착 상태가 발생합니다. 해결 방법은 작업 순서에 적절한 잠금 작업을 추가하는 것입니다. 즉, 잠금 B, 잠금 A, 잠금으로 변경합니다. B, C 잠금, C 해제, A 해제, B 해제)

즉, 잠금 해제 시 역순이 없는 한(예를 들어 C를 누른 상태에서 B 또는 A를 잡으려고 하는 경우) 또는 B)를 누른 상태에서 A를 잡으려고 시도하고 잠재적인 역순이 발생할 때 먼저 놓아야 합니다. "작은" 잠금이 더 큰 잠금을 포착하면 확실히 교착 상태가 발생하지 않습니다.