[Pintos - threads] - donation 개념 정리

 

CPU는 동시에 여러 스레드가 존재할 때, 어떤 스레드를 먼저 실행할지 결정하는 기준으로 ‘우선순위(priority)를 사용한다.
즉, 우선순위가 높은 스레드일수록 더 빨리 CPU를 점유해 실행된다.

스레드	우선순위(Priority)	순서
Thread1	20	thread2 실행이 끝나고 실행
Thread2	40	먼저 실행

 

 

하지만 여러 스레드가 동시에 같은 자원(파일, 메모리 등)에 접근하려 하면 데이터의 일관성이 깨질 수 있다. 이를 방지하기 위해 사용하는 것이 락(lock)이다. 락은 하나의 자원에는 한 번에 하나의 스레드만 접근할 수 있도록 제어하는 역할을 한다.

 

정상 결과값

int result = 0;

thread1:               thread2:
result += 5;           result += 6;

//정상 결과값
result = 0 + 5 + 6 = 11

 

문제 상황

단계	Thread1	Thread2	result값
1	result 읽음		0
2		result 읽음	0
3	reuslt = 0 + 5		0
4		result = 0 + 6	덮어쓰!!!!

 

 

Priority Donation(우선순위 도네이션)

이때, 우선순위 스케줄링과 락 메커니즘이 동시에 작동하면 ‘우선순위 역전(priority inversion)’이라는 문제가 발생할 수 있다. 낮은 우선순위의 스레드가 락을 점유한 상태에서 높은 우선순위의 스레드가 그 락을 기다리면,
높은 우선순위 스레드가 오히려 실행되지 못하고 멈추는 현상이다. 이 문제를 해결하기 위해 등장한 개념이 바로 우선순위 도네이션(Priority Donation)이다.

즉, 높은 우선순위 스레드가 낮은 우선순위 스레드에게 자신의 우선순위를 ‘잠시 기부(donate)’함으로써 락이 빨리 해제되도록 유도하는 것이다.

 

도네이션이 왜 필요할까?

"솔직히 그냥 lock이 걸린 스레드만 먼저 처리해 주면 되는거 아닌가?"라고 생각했다. 근데 만약 lock 걸린 스레드가 우선순위가 낮을 경우에 CPU에서 "너 우선순위 낮잖아! 저리가" 하면서 실행을 중단 시키도 우선순위가 높은 스레드는 lock이 걸린 스레드가 처리되지 않아서 작업을 할 수 없는 상황이 일어난다. 

 

이러한 문제를 해결하기 위해서 lock이 걸린 스레드에게 우선순위가 높은 스레드가 priority를 양보해서 CPU가 작업을 진행할 수 있게 만들어준다.

 

우선순위 역전 상황 (Priority Inversion)

[CPU 실행 순서 결정 기준: 우선순위(priority)]

 ┌───────────────────────────────┐
 │ Thread A  | priority 20 | lock 보유 중
 │ Thread B  | priority 50 | lock 필요 (대기)
 │ Thread C  | priority 40 | lock 필요 없음
 └───────────────────────────────┘

현재 상태:
- B(50)가 A(20)의 lock을 기다림
- 하지만 스케줄러는 "C(40)"이 실행 가능하다고 판단
- CPU는 A를 무시하고 C를 실행함 ⚠

 

A는 lock을 해제하지 못하고,
B는 계속 기다림 → 결국 B(50)가 A(20) 때문에 멈춰버림

 

 

도네이션 발생 (Priority Donation)

Thread B (50) ───▶ Thread A (20)
        "내 우선순위를 잠시 너에게 줄게!"

┌───────────────────────────────┐
│ Thread A  | priority 50 | lock 보유 중 (도네이션 받음)
│ Thread B  | priority 50 | lock 대기 (도네이션 함)
│ Thread C  | priority 40 | lock 필요 없음
└───────────────────────────────┘

→ CPU는 이제 A(50)를 먼저 실행시킴
→ A가 lock을 해제
→ B가 깨어나서 lock을 획득 후 실행됨

 

 

도네이션 이후 (복원 과정)

A: lock 해제 완료 → 원래 priority(20) 복귀
B: lock 획득 후 실행
C: 이후 차례대로 실행