교착 상태(Deadlock) 및 은행원 알고리즘(Banker’s Algorithm)

데드락(Deadlock)은 두 개 이상의 프로세스나 스레드가 서로가 점유한 자원을 기다리며 영원히 진행되지 못하는 상태를 의미

데드락 발생 조건 (Coffman Conditions)

데드락은 다음 4가지 조건이 모두 동시에 성립할 때 발생

1. 상호 배제 (Mutual Exclusion): 한 번에 하나의 프로세스만 자원을 사용할 수 있다.
   • 자원이 공유가 불가능하다면, 다른 프로세스는 그 자원이 해제될 때까지 기다려야 한다.
2. 점유 및 대기 (Hold and Wait): 자원을 점유한 상태에서 다른 자원을 요청하며 대기한다.
   • 예를 들어 Process1이 Resource 1을 점유하면서 Resource 2를 요청해서 기다리는 경우
3. 비선점 (No Preemption): 이미 할당된 자원을 강제로 빼앗을 수 없다.
   • 자원을 점유한 프로세스가 자원을 스스로 해제할 때까지 기다려야 한다.
4. 순환 대기 (Circular Wait): 프로세스들이 자원을 대기하는 형태가 원형 고리처럼 연결되어 있다.
   • 프로세스 A가 자원 R1을 점유하고 R2를 기다림
   • 프로세스 B가 자원 R2를 점유하고 R3를 기다림
   • 프로세스 C는 R3을 점유하고 R1을 기다리는 경우

 

🛠️ 해결 방법

`1. 데드락 예방(Prevention)` : 데드락 조건 4가지 중에 하나라도 발생하지 않게 하는 것(각각의 조건을 부정 및 방지)

1️⃣상호 배제 조건 제거

• 자원을 공유 가능하게 만든다.
• ex) 읽기 전용 파일은 여러 프로세스가 동시에 접근 가능하게 한다.

2️⃣점유와 대기 조건 제거

• 프로세스 대기를 없애기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다. (자원 낭비 발생)
  • 자원 낭비 발생 예시
    • 프로세스 A가 실행되기 위해 R1과 R2가 필요하다고 가정.
    • 실행 초기에 R1과 R2를 모두 할당받았지만, 실제로 R2는 나중에 실행 단계에서만 필요.
    • 프로세스 B는 R2가 필요한데, 프로세스 A가 이를 사용하지 않더라도 R2를 대기해야 함.
    • 결과적으로 R2가 비효율적으로 사용되며, 시스템의 자원이 낭비.
• 자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 한다. (기아 상태 발생)
  • 기아 상태 발생 예시
    • 프로세스 A와 B가 R1과 R2를 순차적으로 사용해야 한다고 가정.
    • 프로세스 B가 R1을 요청했으나, 프로세스 A가 R1을 놓지 않으면 B는 대기.
    • A가 R1과 R2를 모두 사용하지 않으면 요청이 거부되므로, B는 자원을 계속 얻지 못하고 실행되지 못함.

3️⃣비선점 조건 제거

• 모든 자원에 대한 선점을 허용한다.
• 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 함. (자원 낭비 발생 )
  • 자원 낭비 발생 예시
    • 프로세스 A가 R1을 점유한 상태에서 R2를 요청했는데, R2가 사용 중이어서 대기해야 하는 상황.
    • A는 R1을 해제하고 다시 대기 상태로 돌아감.
    • R1은 해제되었으나 다른 프로세스에서 필요하지 않아 유휴 상태로 남아 자원 낭비 발생.

4️⃣순환 대기 조건 제거

• 자원에 번호를 부여하고, 프로세스가 항상 번호 순서대로 일정한 한 쪽 방향으로만 자원을 요청하도록 설계(자원 낭비 발생)
• 예를 들어 R1 → R2 → R3 순으로만 자원 요청 가능

 

`2. 데드락 회피(Avoidance)`: 시스템의 상태를 계속 추적하여 데드락 발생 가능성이 있는 요청을 거절

데드락 회피법 중요 키워드 : `안전 순서(Safe Sequence)` , `안전 상태(Safe State)`

• 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서 차례로 모두에게 할당해 줄 수 있다면 안전 상태에 있다고 말한다.
  • 안전 상태 :
    • 교착 상태 일어날 가능성 X
    • 프로세스가 요구한 양만큼 자원 할당 가능
    • 안전 순서열 존재 O
  • 불안전 상태 :
    • 교착상태 일어날 가능성 O
    • 프로세스가 요구한 양만큼 자원 할당 불가능
    • 안전 순서열 존재 X
• 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서 라고 부른다.

데드락 회피 대표 방법 : 은행원 알고리즘(Banker`s Algorithm)

(참고) 아래 만화로 알아보는 은행원 알고리즘을 보시면 훨씬 이해하기 편합니다.

만화로 보는 은행원 알고리즘

👇이해하기 쉬운 예시

1. 은행에 돈이 1000만원이 있다고 가정
2. 사업가 A는 은행에서 500만원을 빌림
3. 사업가 B는 은행에서 400만원을 빌림. 현재 은행에는 100만원이 남아 있는 상태이다.
4. 시간이 지나 은행은 A에게 돈을 갚으라고 하는데 A는 지금 갚을 수 없고 200만원만 더 빌려주면 그것으로 돈을 벌어 갚겠다고 말함
5. 은행은 현재 100만원 밖에 없기에 B에게 빌려준 돈을 받아서 A에게 200만원을 빌려주려고 함
6. 그래서 B에게 돈을 갚으라고 하는데 B 역시 지금 못 갚고 200만원만 더 빌려주면 그걸로 돈을 벌어서 갚는다고 함
7. 결국 은행은 누구에게도 돈을 빌려주지도 못 하고 빌려준 돈을 받을 수도 없는 교착상태에 빠짐..

⇒ 은행은 이러한 상황을 피하기 위해 돈을 빌려줄 때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(=안전상태)인지 확인하고 빌려주는데 이것을 은행원 알고리즘이라고 한다.

 

OS에서 은행원 알고리즘을 구현하는 방법

1. OS는 프로세스들에게 자원을 할당하기 전에 자신이 가지고 있는 전체 자원의 수를 알고 있어야 한다.
   • 이 때 OS가 가지고 있는 전체 자원의 수 = 시스템의 총 자원
2. 프로세스들은 각자 자신에게 필요한 자원의 최대 숫자를 OS에게 알려줘야 한다.
   • 프로세스가 필요한 자원의 최대 숫자 = 최대 요구 자원 (MAX)
3. 안정상태==안전 순서열이 존재
   1. 현재 OS가 가지고 있는 전체 자원의 수(시스템의 총 자원)는 14개이다.
   2. 프로세스 P1의 최대 요구 자원은 9개이고 현재 할당된 자원은 5개이다.
   3. 프로세스 P2의 최대 요구 자원은 6개이고 현재 할당된 자원은 4개이다.
   4. 프로세스 P3의 최대 요구 자원은 4개이고 현재 할당된 자원은 3개이다.

프로세스	최대 요구 자원(MAX)	현재 할당된 자원(Allocation)	요청이 예상되는 자원
P1	9	5	4
P2	6	4	2
P3	4	3	1

• P1~P3에게 할당된 자원은 총 12개이기에 현재 사용 가능한 시스템의 총 자원의 여유의 개수는 2개(Available)이다.
• 해당 여유 자원들을 가지고 프로세스들의 요청이 예상되는 자원을 제공할 수 있다.
• (위에 표를 참고) 현재 상황에 P1~P3가 모두 추가 자원을 요청했다고 해보자
  • P1이 4개의 자원을 추가로 요청하면 현재 여유 자원은 2개이기에 P1의 요청을 거부하고 P2의 요청을 받는다.
  • P2는 2개를 요청했기 때문에 여유 자원 2개를 전부 P2에게 할당한다.
  • P2는 할당된 자원을 가지고 작업을 마친 후 6개의 자원을 반납한다.
  • P2의 반납으로 여유 자원이 6개가 되었음으로 P1과 P3가 요청한 추가 자원을 모두 할당할 수 있는 상태가 되었다.

4. 불안정 상태 == 안전 순서열이 존재하지 않는다.

프로세스	최대 요구 자원(MAX)	현재 할당된 자원(Allocation)	요청이 예상되는 자원
P1	9	7	2
P2	6	4	2
P3	4	2	2

• 동일하게 현재 OS가 가지고 있는 시스템의 총 자원의 수가 14개라 했을 때
• P1 ~ P3 에게 할당된 자원은 총 13개이기에 현재 사용 가능한 자원은 1개이다.
• 여유 자원 1개 만으로는 P1~P3의 추가 요구 자원(2개)를 모두 충족할 수 없기에 불안정 상태가 된다. = 안전 순서열이 존재하지 않음.
• 단, 불안정 상태에 있더라도 모든 프로세스가 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않지만 불안정 상태 자체에 빠지지 않도록 유지하는 것이 최선이다.

📒그래서 은행원 알고리즘이란..

교착 상태에 빠질 가능성이 있으면 자원을 빌려주지 않는 회피 방법을 사용함으로 안전 순서열을 지켜 교착상태에 걸리지 않게 해서 시스템이 안전상태를 유지할 수 있게 하는 방법을 은행원 알고리즘이라 한다.

 

은행원 알고리즘은 복잡하고 계산량이 많아 실제 시스템에서 적용하기가 어렵다는 단점이 있다. 또한 시스템의 자원 이용률을 낮추어 성능 저하를 유발할 수 있음..

`3. 데드락 탐지 및 복구(Detection and Recovery)`: 데드락 발생 후 탐지 및 자원 강제 회수

• 운영체제에서 데드락을 완전히 예방하거나 회피하는 것은 비효율적이거나 많은 비용이 들 수 있음
• 데드락 탐지 및 복구 방식은 데드락 발생을 허용하고, 이를 탐지한 후 복구하는 방식으로 설계
  • 주로 자원을 효율적으로 활용하면서 교착 상태를 해결하려는 경우에 사용
• 실제 시스템에서는 데드락 복구보다는 예이나 회피 전략이 더 자주 사용 된다고 함

👉데드락 탐지(Detection)

자원 할당 그래프(Resource Allocation Graph, RAG)

• 구조:
  • 노드(Node): 프로세스(P)와 자원(R).
  • 간선(Edge):
    • 요청 간선: 프로세스 → 자원 (P → R).
    • 할당 간선: 자원 → 프로세스 (R → P).
• 데드락 판별: 그래프에 순환(Cycle)이 존재하면 데드락이 발생.
  • 각 노드는 최대 N개의 간선을 가질 수 있으므로 최대 간선의 개수는 N*(N-1)이므로 O(N^2) 시간 복잡도 발생

탐지 알고리즘

• 자원의 현재 할당 상태와 요청 상태를 기반으로 프로세스들이 자원을 끝내 사용할 수 없는지를 판단.
• 프로세스가 할당된 자원과 필요 자원을 비교하여 데드락 여부 확인

👉데드락 복구

(1) 프로세스 종료

1. 모든 데드락 프로세스 종료:
   • 데드락 상태에 있는 모든 프로세스를 강제로 종료하여 자원을 회수.
   • 가장 간단하지만 비용이 큼.
2. 하나씩 종료:
   • 데드락 상태에 있는 프로세스를 하나씩 종료하여 데드락을 점진적으로 해결.
   • 어떤 프로세스를 종료할지 선택 기준:
     • 프로세스 우선순위
     • 처리 비용
     • 이미 사용한 자원 양

(2) 자원 선점

• 데드락을 발생시킨 프로세스로부터 자원을 강제로 회수(선점).
• 방법:
  1. 자원을 회수할 프로세스 선택.
  2. 해당 프로세스를 일시적으로 중단(재시작 가능하도록 상태 저장).
• 단점: 자원 선점으로 인해 프로세스 상태 복원 비용이 증가할 수 있음.

(3) 롤백(Rollback)

• 데드락 발생 시, 문제가 된 프로세스를 이전 안전 상태로 되돌림.
• 체크포인트를 활용하여 복구 가능.

❓데드락 탐지 및 복구의 장단점

😊장점

• 탐지: 데드락 발생 가능성을 실시간으로 분석하여 즉각 조치 가능.
• 복구: 시스템을 재부팅하지 않고도 문제를 해결 가능.

😕단점

• 탐지와 복구 과정에서 추가 오버헤드(성능 저하) 발생.
• 복구 시 프로세스 종료 또는 자원 선점으로 인한 데이터 손실 또는 작업 지연 가능.

 

`4. 데드락을 완전히 무시`하는 전략 사용

데드락 회피, 탐지, 복구 방법은 오버헤드가 커서 대부분 운영체제가 무시 기법을 사용하고 있음..

 

🤔아니 현대 OS에서는 데드락이 뜨든 말든 무시한다는데 왜 알아야하지?!

데이터베이스 트랜잭션에서 데드락 발생!!

DB에서 트랜잭션이 여러 자원을 동시에 사용하려 할 때 데드락이 발생할 수 있음. 데드락의 원리와 해결 방법을 알아야 실무에서도 원인을 분석하고 해결할 수 있다 ! 

• 트랜잭션 T1은 TableA를 업데이트하려고 잠근 뒤(LOCK TableA), 해당 작업을 진행
• 이어서 TableB의 특정 행을 읽거나 업데이트하려고 잠가야 한다.(LOCK TableB)
• 동시에 트랜잭션 T2는 TableB부터 잠그고(LOCK TableB) 작업한 뒤, 후속 작업으로 TableA를 잠그려고 시도합니다(LOCK TableA).
• 두 트랜잭션이 서로 상대방이 이미 잠근 테이블(또는 행)에 접근하려고 시도하면서 대기 상태에 빠집니다.

- 트랜잭션 T1
BEGIN;
LOCK TABLE TableA IN EXCLUSIVE MODE;
-- TableA에 대한 UPDATE/INSERT/DELETE 수행
LOCK TABLE TableB IN EXCLUSIVE MODE;
-- TableB에 대한 UPDATE/INSERT/DELETE 수행
COMMIT;

- 트랜잭션 T2
BEGIN;
LOCK TABLE TableB IN EXCLUSIVE MODE;
-- TableB에 대한 UPDATE/INSERT/DELETE 수행
LOCK TABLE TableA IN EXCLUSIVE MODE;
-- TableA에 대한 UPDATE/INSERT/DELETE 수행
COMMIT;

 

해결 방법

1. 타임아웃 설정 : 일정 시간 대기 후 데드락으로 간주하고 트랜잭션 롤백 (데드락 탐지)

2. 락 순서 강제 : 자원을 항상 일정한 순서로 요청하도록 설계. (순환 대기 조건 제거)