교착 방지 알고리즘

컴퓨터 과학에서 교착 방지 알고리즘은 여러 프로세스가 둘 이상의 공유 자원을 획득해야 할 때 동시 프로그래밍에 사용된다. 두 개 이상의 동시 프로세스가 여러 자원을 무차별적으로 획득하는 경우, 각 프로세스가 다른 프로세스에 필요한 자원을 보유하는 상황이 발생할 수 있다. 그 결과, 어느 프로세스도 필요한 모든 자원을 확보할 수 없으므로, 모든 프로세스는 추가 실행이 차단된다. 이런 상황을 교착상태라고 한다. 교착 방지 알고리즘은 적어도 하나의 프로세스가 항상 필요한 모든 리소스를 얻을 수 있도록 각 프로세스별로 리소스 사용을 체계화한다. 그러한 교착 알고리즘의 예로는 뱅커의 알고리즘이 있다.

개요

교착 방지 기술 및 알고리즘

이름	커피맨 조건	설명
뱅커 알고리즘	상호배제	뱅커의 알고리즘은 Edsger Dijkstra에 의해 개발된 자원 할당 및 교착 회피 알고리즘이다.
재귀 잠금 방지	상호배제	이것은 하나의 나사산이 동일한 잠금 장치에 두 번 이상 들어가는 것을 방지한다.

분산 교착 상태

분산형 교착상태는 분산형 트랜잭션이나 동시성 통제를 사용할 때 분산형 시스템에서 발생할 수 있다. 분산 교착상태는 교착상태 검출기의 로컬 대기 그래프에서 전역 대기 그래프를 구성하거나 에지 추적과 같은 분산 알고리즘을 사용하여 탐지할 수 있다.

팬텀 교착상태는 시스템 내부 지연으로 인해 분산 시스템에서 감지되지만 탐지 시점에 실제로 존재하지 않는 교착상태다.

교착 방지

반복 잠금 장치가 그렇지 않으면 교착 상태를 야기할 수 있는 병렬 처리를 증가시키는 많은 다양한 방법이 있다. 하지만 대가가 있다. 그리고 그 가격은 성능/과잉이거나, 데이터 손상을 허용하거나, 둘 다 입니다.

일부 예:^[1] 잠금 계층, 잠금 참조 카운팅 및 선점(버전화를 사용하거나 선점 시 데이터 손상을 허용) Wait-For-Graph (WFG)[1] 알고리즘은 교착상태(임시적 교착상태 포함)를 유발하는 모든 사이클을 추적하고, 교착상태의 100%에서 병렬상태를 증가시킬 필요는 없지만, 대신 성능/오버헤드 대 병렬이 허용되는 충분한 장소에서 이를 해결함으로써 타협한다.

"교차로에서 두 열차가 서로 접근하는 경우"를 생각해 보십시오. 정시방지는 다른 대기열차 위와 위를 달리는 '슈퍼 트랙'에 한 열차만 올려주는 스위치로 건널목(건널목 보호대)에 사람이 서 있는 것과 같은 효과를 낸다.

• 비재발 잠금장치의 경우 잠금장치를 한 번만 입력할 수 있다(잠금 해제 없이 두 번 입력하는 나사산이 교착상태를 유발하거나, 원형 대기방지를 시행하기 위한 예외를 발생시키는 경우).
• 재귀 잠금 장치의 경우 하나의 나사산만 잠금 장치를 통과할 수 있다. 다른 스레드가 잠금 장치에 들어갈 경우, 이 스레드는 처음 스레드가 입력된 횟수 n번을 완료할 때까지 기다려야 한다.

그래서 첫 번째의 문제는 그것이 전혀 교착상태를 예방하지 않는다는 것이다. 두 번째는 분산된 교착상태 예방을 하지 않는다. 그러나 두 번째 것은 첫 번째가 다루지 않는 교착 상황을 막기 위해 재정의된다.

반복적으로, 하나의 나사산만 자물쇠를 통과할 수 있다. 다른 스레드가 잠금 장치에 들어갈 경우, 통과된 초기 스레드가 n번 완료될 때까지 기다려야 한다. 그러나 잠금을 입력하는 스레드 수가 잠긴 수와 같을 경우 하나의 스레드를 슈퍼 스레드로 할당하고 완료될 때까지 스레드를 실행(잠금을 입력/종료하는 횟수 추적)만 허용하십시오.

슈퍼 스레드가 완료된 후 상태는 재귀 잠금 및 종료된 슈퍼 스레드의 로직을 사용하는 것으로 다시 변경된다.

1. 초호화하지 않는 것으로 설정하다.
2. 보관함에 다른 잠긴 대기 스레드가 이 상태를 다시 확인해야 함을 알린다.

교착 상황 시나리오가 존재하는 경우, 새로운 수퍼 스레드를 설정하고 그 논리를 따르십시오. 그렇지 않으면 정기 잠금을 다시 시작하십시오.

위에서 다루지 않은 문제

많은 혼란은 중단 문제를 중심으로 돌아간다. 그러나 이 논리는 잠금이 발생하는 조건을 알고 있기 때문에 정지 문제를 해결하지 못하는데, 이는 (정지 문제가 요구하는 다른 일반적인 해결책 대신에) 특정한 해결책을 제시하기 때문이다. 그래도 이 사물함은 이 논리를 이용한 잠금장치만 고려해도 모든 교착상태를 방지한다. 그러나 다른 잠금 메커니즘과 함께 사용할 경우, 절대 잠금 해제되지 않는 잠금(잠금 해제 없이 튀어나오거나 잠금 해제 해제 내에서 무한히 루핑하거나 잠금 해제를 호출하는 것을 잊어버린 코딩 오류)을 사용할 경우 교착 상태가 매우 가능하다. 이것들을 포함하기 위해 조건을 증가시키려면 중단 문제를 해결해야 할 것인데, 그 이유는 사람은 아무것도 모르고 바꿀 수 없는 조건들을 다루게 될 것이기 때문이다.

또 다른 이슈는 두 개 이상의 스레드가 서로 잠기는 동안 또 다른 관련 없는 스레드가 가동되는 일시적인 교착 상태 문제(실제로 교착 상태가 아닌 성능 파괴자)를 해결하지 못한다는 점이다. 이러한 일시적인 교착상태는 그 안에서만 실이 가동되어 평행성이 높아질 수 있다. 그러나 분산된 교착 상태 감지가 하위 집합이 아닌 모든 잠금 장치에 대해 작동하는 방식 때문에, 임시 교착 상태를 제거하기 위해 수퍼 스레드 논리를 수행하기 전에 관련 없는 실행 스레드가 완료되어야 한다.

위 내용에서 일시적인 라이브락 시나리오를 볼 수 있다. 관련 없는 다른 실행 스레드가 첫 번째 관련 없는 스레드가 종료되기 전에 시작되면 또 다른 일시적인 교착 상태가 발생할 것이다. 이러한 상황이 계속 발생할 경우(극히 드문 경우) 관련되지 않은 다른 스레드가 항상 완료되도록 보장되는 경우(한 스레드가 항상 완료되도록 보장되기 때문에) 프로그램이 종료되기 직전까지 임시 교착 상태를 연장할 수 있다.

추가 확장

이는 더 나아가 일시적인 교착 상태가 발생할 수 있는 평행도를 증가시키기 위한 추가적인 논리를 포함하도록 확장될 수 있다. 그러나 논리를 추가하는 각 단계마다 우리는 더 많은 오버헤드를 추가한다.

기존 잠금 장치의 각 서브셋을 고려하도록 분산된 슈퍼 스레드 잠금 메커니즘 확장, 교착(임시적 교착 상태 포함)을 유발하는 모든 사이클을 추적하는 WFG(Wait-For-Graph) [2] 알고리즘, 임시 장애 발생 장소의 100%에서 반드시 평행도를 증가시키지 않는 휴리스틱스 알고리즘 등이 몇 가지 예다.애드록은 가능하지만, 대신 성능/성능 대 병렬이 허용되는 충분한 장소에서 해결함으로써 타협한다(예: 사용 가능한 각 프로세서의 경우 프로세서 수 + 1 깊이보다 적은 교착 상태 사이클을 찾기 위해 노력한다).

참조