[PintOS] Priority Scheduling 추상화 과정

후노바스·2024년 3월 10일

왜 Priority Donation이 필요한가?

PintOS 프로젝트로 미니 OS를 priority까지 구현하던 중, Priority Donation을 구현하라는 과제를 받았다. 하지만 과제를 설명한 Gitbook에는 어째서 Donation를 구현하는지에 대한 명확한 설명은 생략되어 있어 이번 포스트에서 조사한 자료를 토대로 정리하고자 한다.

다음의 main 스레드와 main으로부터 생성된 스레드 A, B가 있는 상황에서의 우선순위 스케줄링을 유저 레벨에서 생각해보자.

테스트 코드:
(상황을 가정하기 위해 예시로 작성한 코드이며 실제로 돌아가는 코드가 아닙니다.)

int g_pushup = 0;
struct semaphore lock_a;

void do_pushup(void* arg);
void print_pushup(void* arg);

int main() {
	ASSERT (thread_get_priority () == 31);

    sema_init(&lock_a, 1);
    sema_down(&lock_a);

    thread_create ("thread B", 63, do_pushup, NULL);
    thread_create ("thread A", 32, print_pushup, NULL);

	sema_up (&lock_a);

    return 0;
}

void do_pushup(void* arg UNUSED)  {

	sema_down (&lock_a);
    for (int i = 0; i < 50; i++)
        g_pushup++;
	sema_up (&lock_a);

}

void print_pushup(void* arg UNUSED) {

	printf("%d번 팔굽혀펴기 중 ^^7", g_pushup);
	
}

main 스레드에서는 그저 lock a를 걸어준 뒤 스레드 B와 A를 생성하고 있다. 스레드 B에서는 푸시업 횟수 g_pushup을 더해주고 있고, 스레드 A에서는 푸시업 횟수 g_pushup를 출력만 한 줄 해주고 있다. 즉, 팔굽혀펴기를 실제로 하는 스레드가 따로 있고 최종적으로 팔굽혀펴기를 몇 번 했는지 출력하는 스레드가 따로 있다.

당연히 유저 입장에서는 스레드 A보다 스레드 B의 우선순위를 더 높게 책정할 것이다.

위 상황에서 Donation이 없는 우선순위 정책을 가진 스케줄러는 메인 함수부터 작동을 시작해서 스레드들의 작업을 어떻게 분배시키는지 차근차근 생각해보자.

기본 우선순위를 가진 main에서는 lock a를 걸어놓은 상태로 우선순위 63의 스레드 B를 만든다.
thread_create ("thread B") 단계에서 B의 우선순위가 더 크기 때문에 스케줄러는 B로 콘텍스트 스위칭을 해준다.
main은 ready list에 실리고 스레드 B가 실행되기 시작한다.
B에서 sema_down(&lock_a)를 만나면 스케줄러는 B를 BLOCK 상태로 만들고 ready list에 실렸던 main으로 다시 콘텍스트 스위칭을 해준다.
thread_create ("thread A") 단계에서 A의 우선순위가 더 크기 때문에 스케줄러는 A로 콘텍스트 스위칭을 해준다.
main은 ready list에 실리고 스레드 A가 실행되기 시작한다.
A에서 프롬프트에 다음을 출력한다.

0번 팔굽혀펴기 중 ^^7
스레드 A가 종료되고 ready list에 실렸던 main으로 다시 콘텍스트 스위칭을 해준다.
main에서 lock a를 해제하면서 BLOCK 상태의 B가 다시 ready list에 실리고, 우선순위가 더 높으므로 스케줄러는 B로 콘텍스트 스위칭을 해준다.
main은 ready list에 실리고 스레드 B가 실행되기 시작한다.
B에서 lock a를 걸어놓은 상태로 팔굽혀펴기를 수행한다.
B에서 lock a를 해제하면서 종료되고 ready list에 실렸던 main으로 다시 콘텍스트 스위칭을 해준다.

스레드 B가 팔굽혀펴기를 하기 전에 스레드 A에서 먼저 출력을 해버리는 바람에 0이라는 숫자가 출력이 되었다.

"아니, 스레드 B에서 lock a에 대해 대기 요청을 했으니 당연히 B가 A보다 늦게 실행되어야 하는 것 아니야?"

라고 할 수도 있지만,
공유 변수를 사용한다면 스레드 간에 lock을 거는 상황이 상당히 빈번하게 발생할 수 있고 위처럼 간단하고 무식한 코드가 아니라 정교하게 짜여진 코드에서는 유저가 미처 생각하지 못한 빈틈에서 스레드 간 우선순위만 고려하다가 위와 같은 문제가 발생할 수 있다.

유저가 B가 실행되어야 한다고 생각했던 위치:

> Donation을 하게 된다면?

Donation 기능을 구현한다면 스레드 main은 스레드 B가 lock a에 접근하는 순간 스레드 B로부터 우선순위 Donation을 받게 되고, 스레드 A가 만들어지는 순간 A에게 스케줄 점유를 빼앗기지 않게 된다. 따라서 코드의 로직이 유저의 의도대로 아래와 같이 흘러갈 수 있다.

기본 우선순위를 가진 main에서는 lock a를 걸어놓은 상태로 우선순위 63의 스레드 B를 만든다.
thread_create ("thread B") 단계에서 B의 우선순위가 더 크기 때문에 스케줄러는 B로 콘텍스트 스위칭을 해준다.
main은 ready list에 실리고 스레드 B가 실행되기 시작한다.
B에서 sema_down(&lock_a)를 만나면 스케줄러는 B를 BLOCK 상태로 만들고 ready list에 실렸던 main에게 자신의 우선순위를 기부한 뒤, main으로 다시 콘텍스트 스위칭을 해준다.
thread_create ("thread A") 단계에서 main의 우선순위가 더 크기 때문에 스케줄러는 main으로 콘텍스트를 유지한다.
A는 ready list에 실리고 main이 실행되기 시작한다.
main에서 lock a를 해제하면서 기부받았던 우선순위에서 원래 자신의 우선순위로 돌아오고, BLOCK 상태의 B가 다시 ready list에 실리고, 우선순위가 더 높으므로 스케줄러는 B로 콘텍스트 스위칭을 해준다.
main은 ready list에 실리고 스레드 B가 실행되기 시작한다.
B에서 lock a를 걸어놓은 상태로 팔굽혀펴기를 수행한다.
B에서 lock a를 해제하면서 종료되고 ready list에 실렸던 스레드 중 가장 큰 A로 다시 콘텍스트 스위칭을 해준다.
A에서 프롬프트에 다음을 출력한다.

50번 팔굽혀펴기 중 ^^7
스레드 A가 종료되고 ready list에 실렸던 main으로 다시 콘텍스트 스위칭을 해준다.

Nested Donation

스레드의 락은 위 그림과 같이 연쇄되어 걸릴 수 있다. 그림에서 스레드 C는 B가 가진 lock b에 의해 BLOCK 상태가 되면서 자신의 우선순위를 기부했고, 스레드 B는 A가 가진 lock a에 의해 BLOCK 상태가 되면서 자신의 우선순위를 기부했다. 여기서 스레드 C는 B뿐만 아니라 A에게도 기부를 했다는 점이다. 왜냐하면 지금 상태에서 RUNNING 상태를 가질 수 있는 스레드는 A 뿐이기 때문이다.

이렇게 Nested Donation을 구현한 상태에서 63의 우선순위를 가진 lock d를 가진 스레드 D가 lock c에 접근하게 되면 어떻게 될까?

스레드 D는 C뿐만 아니라 C가 기다리고 있는 lock에 대한 주인(스레드 B)에게도, 그 주인이 기다리고 있는 lock에 대한 주인(스레드 A)에게도 기부를 해주어야만 하는데, 이는 반복문이나 재귀함수로 구현할 수 있을 것이다.

이 상태에서 2가지를 묻겠다.

A가 lock a를 해제한다면 그림은 어떻게 되어야 하는가?

A가 lock d에 접근한다면 그림은 어떻게 되어야 하는가?

1번에 대한 그림은 아래와 같다.

A는 lock a을 통해 받고 있던 Donation의 연결이 끊겼으므로 원래 자신이 가지고 있던 우선순위로 돌아와야만 한다.

2번에 대한 그림은 아래와 같다.

특히 2번에 대한 그림은 데드락(Deadlock)이라고 하는 상황을 나타낸 것인데, 어떤 스레드도 RUNNING 상태를 가질 수 없어 프로그램이 작동을 멈춘 상황을 표현한 말이다.
이 문제에 대한 해결책은 다음에 다루기로 하고, 일단 Donation에서 발생하는 문제점이 있는데, 위 그림에 나온 스레드가 아닌 다른 기부를 하려는 스레드에서 lock a, lock b, lock c, lock d 중 어느 하나에 접근하기만 하면 스레드 A, B, C, D를 돌면서 기부를 해야 하는데, 자칫 잘못하면 무한루프에 빠질 수도 있다. 이는 아래 2가지 방법으로 해결할 수 있다.

반복시키기 전에 if (수혜자의 우선순위 < 기부자의 우선순위) 조건문을 단다.
재귀 깊이를 제한하거나, 반복문에 깊이 조건에 대한 break를 추가한다.

Multiple Donation

한 스레드가 여러 개의 락을 가질 수도~~(||잠글 수도||획득할 수도||걸 수도)~~ 있다. 위 그림과 같은 상태에서 (우선순위가 22인) 기부를 받는 스레드는 자신이 가진 여러 개의 락에 연결된 기부자들의 우선순위 중 가장 높은 우선순위를 가져야 한다.

여기서 2가지를 묻겠다.

A가 lock b를 해제한다면 그림은 어떻게 되어야 하는가?

D가 lock c에 접근한다면 그림은 어떻게 되어야 하는가?

1번에 대한 그림은 아래와 같다.

A는 lock b을 통해 받고 있던 Donation의 연결이 끊겼으므로 60에 대한 우선순위 정보를 지우고, 자신이 가진 lock에 대한 정보 중 가장 큰 우선순위로 갱신해줘야만 한다.

2번에 대한 그림은 아래와 같다.

A는 lock a로부터 B에게 32의 우선순위를 기부받고 있고, lock b로부터 C에게 60의 우선순위를 기부받고 있고, lock c로부터 D에게 63의 우선순위를 기부받고 있다. 이 때 중요한 점은 A의 우선순위를 60에서 63으로 교체해주는 것 뿐만 아니라, lock b를 계속 가진 채로 다시 lock c를 해제할 경우를 대비해 60에 대한 우선순위 정보를 저장해야만 한다는 것이다. lock a, b, c가 모두 A로부터 해제된 다음에야 A는 원래 자신의 우선순위인 22로 돌아올 것이다.

Problem Abstraction

위 그림들은 단순한 경우에 대해 설명한 것이다. 한 락에 여러 스레드가 대기할 수도 있고, Nested Donation과 Multiple Donation이 섞인 문제가 나올 수도 있다. 이를 좀 더 간단하게 분석하기 위해, 우리는 Priority Donation이 스레드의 우선순위에 발생시키는 현상을 명료하게 도표화할 것이다.

~~좀 허접하지만 excalidraw에서 표를 지원안해준다. 참고보자~~
스레드 A, B, C, D, E, F와 lock a, b, c, d, e, f가 있고 이 사이 관계와 그에 따른 우선순위에 대해 표로 나타낼 것이다. 여기서 스레드가 어떤 락을 가진 상태를 ○로, 락에 대기하고 있는 상태를 ◇로, 락을 해제한 상태를 빈 칸으로 둘 것이다.

여기서 중요한 점은,

각 락 당 표시할 수 있는 획득 표시 ○는 1개 뿐이다. 스레드가 하나의 락을 가지게 되면, 다른 스레드는 그 락을 가지기 전까지 대기해야 하기 때문이다.
각 스레드 당 표시할 수 있는 대기 표시 ◇는 1개 뿐이다. 스레드가 한 번 대기하기 시작하면 작동 정지가 되었다는 뜻이기 때문이다.

○는 가로줄에 한 개 씩만 있어야 한다.
◇는 세로줄에 한 개 씩만 있어야 한다.

위를 유념하고,
아래 첫 번째 예시를 보자.

이 상태에서 스레드 A는 우선순위로써 어떤 상태를 가져야 할까?

/
원래 자신의 우선순위를 저장해야 할까? (O/X)
/
a. 대기 중인 우선 순위 중 가장 높은 42만 우선순위로 바꾸면 될까?
b. 대기 중인 우선순위 중 자기보다 높은 우선순위만 저장한 채 우선순위를 42로 바꾸면 될까?
c. 모든 대기 중인 우선순위를 저장한 채 우선순위를 42로 바꾸면 될까?

정답은 1. O, 2. a이다.
2번이 왜 a냐면 스레드 A가 오직 1개의 락만 가지고 있기 때문에, 그 락에 대한 최고의 우선순위를 가진 스레드만 저장하면 된다. 즉, 스레드 B, C, D, E 순으로 lock a에 접근해서 기부를 하게 되었다면, A의 우선순위는 다음과 같았을 것이다.

스레드 B 기부 X -> 22
스레드 C 기부 O -> (22) / 31
스레드 D 기부 O -> (22) / 42
스레드 E 기부 X -> (22) / 42

스레드 D가 기부했을 때 C의 우선순위를 저장하지 않고 덮어씌웠다는 점을 유념해라.

아래는 두 번째 예시이다.

/
스레드 A에서의 우선순위 저장상태는 위 도표의 스레드들이 어떤 순서로 대기 요청을 했는지에 영향을 미치는가? (O/X)
만약 F->D->C->E->B 순으로 대기 요청을 했다고 한다면, 스레드 A는
a. F에 대한 우선순위만 저장하면 된다.
b. 모든 스레드에 대한 우선순위를 저장해야 한다.
c. C, D, F에 대한 우선순위를 저장해야 한다.

정답은 1. X, 2. c이다. 1번에 대한 내용은 다음 예시에서 설명하겠다. 2번은 기부자의 우선순위는 스레드 A의 현재 우선순위가 아닌 스레드 A의 원래 우선순위와 비교해야 하므로 a가 틀렸고, 스레드 A는 lock의 수만큼 우선순위를 저장하되, 같은 lock에 대한 우선순위 기부가 들어오고 그 값이 더 크다면 그 lock에 대한 우선순위를 덮어씌우면 되므로 C, D, F의 우선순위만 저장한다.

다음 세 번째 예시이다.

이 상태에서 A의 우선순위 저장상태가 어떻게 되는가?

-

-

-

-

-

답은 모른다 이다. 이번 예시는 스레드들이 어떤 순서로 대기 요청을 했는지에 따라 A의 우선순위 저장상태가 달라진다. 위 그림의 순서로 대기 요청을 하게 되는 것과, 아래 그림의 순서로 대기 요청을 하게 되는 것이 A의 우선순위 저장상태가 어떻게 달라지는지 직접 계산해보라.

--첫 번째--

--두 번째--