교착상태

🔎 교착상태
복수의 트랜잭션을 사용하다 보면 교착상태가 일어날 수 있다. 
교착상태란 두 개 이상의 트랜잭션이 특정 자원(테이블 또는 행)의 잠금을 획득한 채 다른 트랜잭션이 소유하고 있는 잠금을 요구하면 아무리 기다려도 상황이 바뀌지 않는 상태가 되는데, 이를 교착상태라고 한다.

 

출처 : https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/Database#%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C

 

트랜잭션 1이 테이블 B의 첫번째 행의 잠금을 얻고 트랜잭션 2도 테이블 A의 첫번째 행의 잠금을 얻었다고 했을 때,
트랜잭션을 COMMIT하지 않은채 서로의 첫번째 행에 대한 잠금을 요청하면 Deadlock이 발생한다.

 

교착 상태의 빈도를 낮추는 방법

1. 트랜잭션을 자주 커밋한다.
2. 정해진 순서로 테이블에 접근한다.
   위에서는 트랜잭션 1이 테이블 B → A의 순으로 접근했고, 트랜잭션 2는 테이블 A → B 순으로 접근했다. 
   트랜잭션들이 동일한 테이블 순으로 접근하게 한다.
3. 읽기 잠금 획득 (SELECT ~ FRO UPDATE)의 사용을 피한다.
4. 한 테이블의 복수 행을 복수의 연결에서 순서 없이 갱신하면 교착상태가 발생하기 쉽다. 이 경우에는 테이블 단위의 잠금을 획득해 갱신을 직렬화하면 동시성은 떨어지지만 교착상태를 회피할 수 있다.

 

교착 상태 탐지 알고리즘

은행원 알고리즘

각 자원 유형마다 인스턴스가 여러 개 있는 경우 은행원 알고리즘(Banker's Algorithm)을 사용하여 교착 상태를 탐지한다.

 

• 각 프로세스의 자원 요청(Request) 개수를 사용한다.
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 현재 상태가 안정 상태인지 확인한다.
• 불안정 상태라면 교착 상태라고 판단한다.

✅ 안정 상태면 자원 할당, 아니면 다른 프로세스들의 자원 해지까지 대기

 

자원 할당 그래프 알고리즘

자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착 상태를 회피하는 알고리즘

 

• 프로세스가 자원을 요구할 때 요청 간선을 할당 간선으로 변경하면 사이클이 생성되는지 확인

📢 사이클이 생선된다고 무조건 교착 상태인 것은 아니다!

1. 자원에 하나의 인스턴스만 존재하면 교착 상태로 판별
2. 자원에 여러 인스턴스가 존재하면 교착 상태 가능성으로 판별

탐지 알고리즘 호출 주기

탐지 알고리즘은 오버헤드가 있기 때문에 얼마나 자주 교착 상태가 발생하는지 얼마나 많은 프로세스가 교착 상태에 연루되어 있는지에 따라 호출 빈도를 조절해야 한다.

1.  자원을 요청했는데 즉시 할당되지 못하는 시점에 호출
2. 주기적으로 일정 시간마다 호출
3. cpu 이용률이 특정 값 이하로 떨어지는 시점에 호출

 

[참고]

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/Database#%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C

Interview_Question_for_Beginner/Database at main · JaeYeopHan/Interview_Question_for_Beginner

 

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md

tech-interview-for-developer/Computer Science/Operating System/DeadLock.md at master · gyoogle/tech-interview-for-developer

 

https://yoongrammer.tistory.com/67

교착상태(Dead Lock) 해결 방법