운영체제 · Pintos · Project 1 Threads · 2편

Pintos 기본 Priority Scheduler: waiters 정렬과 priority donation 구현하기

1편에서는 alarm-priority를 통해 ready list를 priority 순서로 유지해야 한다는 점을 봤습니다. 이번 글은 그 다음 단계입니다. 깃북이 요구하는 기본 Priority Scheduling을 기준으로 semaphore, condition variable, lock donation까지 연결해서 정리합니다.

이번 글에서 다루는 것

깃북의 Priority Scheduling 요구사항을 한글로 다시 정리
깃북 문장을 테스트와 코드 수정 지점으로 바꾸는 첫삽
FIFO 대기열을 priority-aware 대기열로 바꾸는 이유
semaphore / condition variable에서 가장 높은 priority thread를 먼저 깨우는 코드
lock에서 priority inversion을 donation으로 해결하는 구조
multiple donation, nested donation, donation 회수를 위한 필드와 helper 함수
MLFQS는 왜 이번 글의 범위가 아닌지

1. 깃북 요구사항을 먼저 번역하면

앞으로 이 과제 설명 원문을 "깃북"이라고 부르겠습니다. 이번 글에서 보는 깃북의 핵심 문장은 아래처럼 정리할 수 있습니다.

깃북 요구	한글 해석	주로 연결되는 테스트
Higher priority ready thread should run first	ready list에 더 높은 priority thread가 들어오면 현재 thread는 CPU를 양보해야 한다.	`priority-preempt`, `priority-change`
Highest priority waiter should wake first	lock, semaphore, condition variable에서 기다리는 thread 중 priority가 가장 높은 thread를 먼저 깨워야 한다.	`priority-sema`, `priority-condvar`
Priority donation	높은 priority thread가 낮은 priority lock holder를 기다리면, 기다리는 동안 holder에게 priority를 빌려준다.	`priority-donate-one`, `priority-donate-lower`
Multiple and nested donation	여러 thread가 한 thread에게 donation할 수 있고, H → M → L처럼 donation이 lock chain을 따라 전파될 수 있어야 한다.	`priority-donate-multiple`, `priority-donate-nest`, `priority-donate-chain`
No donation for MLFQS	Advanced Scheduler가 켜진 경우에는 priority donation을 사용하지 않는다.	`mlfqs-*`는 다음 글 범위

2. 왜 이 요구사항을 이렇게 풀어야 하는가

깃북은 "어느 파일 몇 번째 줄을 고쳐라"라고 말하지 않습니다. 대신 스케줄러가 보장해야 하는 동작을 문장으로 줍니다. 그래서 첫삽은 코드를 바로 쓰는 것이 아니라, 요구사항을 불변 조건(invariant)과 테스트가 확인하는 장면으로 바꾸는 것입니다.

깃북 문장을 코드 문제로 바꾸면

READY 상태가 된 thread 중 priority가 가장 높은 thread가 먼저 실행되어야 한다.
따라서 ready_list에 넣는 순간부터 priority 순서를 유지해야 합니다.
semaphore와 condition variable에서 기다리는 thread도 priority 순서로 깨워야 한다.
따라서 sema->waiters, cond->waiters도 단순 FIFO로 두면 안 됩니다.
높은 priority thread가 낮은 priority lock holder를 기다리면 holder를 먼저 실행시켜야 한다.
따라서 lock을 기다리기 직전에 priority를 holder에게 donation하고, lock을 release할 때 회수해야 합니다.

이 관점으로 보면 "기본 스케줄러"는 하나의 큰 기능이 아니라 세 개의 작은 문제로 나뉩니다. 백준 문제를 풀 때 예제 입력을 보고 조건을 좁히듯이, Pintos도 테스트 하나를 한 장면으로 보고 그 장면을 만족시키는 코드 위치를 찾는 편이 좋습니다.

테스트 장면	이 테스트가 묻는 질문	첫 번째로 볼 코드
`priority-preempt`	더 높은 priority thread가 READY가 되면 현재 thread가 바로 양보하는가?	`thread_unblock()`, `thread_yield()`, `thread_create()`
`priority-sema`	semaphore에서 기다리던 thread 중 priority가 가장 높은 thread가 먼저 깨어나는가?	`sema_down()`, `sema_up()`
`priority-condvar`	condition variable도 FIFO가 아니라 priority 순서로 signal되는가?	`struct semaphore_elem`, `cond_wait()`, `cond_signal()`
`priority-donate-one`	H가 L의 lock을 기다릴 때 L의 effective priority가 H만큼 올라가는가?	`lock_acquire()`, `lock_release()`, `thread_get_priority()`

깃북 문장
highest priority first

불변 조건
대기열 앞은 최고 priority

테스트 장면
priority-sema 실패 로그

첫 수정
waiters insert/sort

그래서 이 글의 코드 수정 순서는 임의가 아닙니다. 먼저 thread가 READY 상태로 들어가는 길을 잡고, 그 다음 semaphore와 condition variable의 waiters를 잡고, 마지막으로 lock holder에게 priority를 빌려주는 donation을 잡습니다. 이 순서가 깃북 요구사항을 테스트 단위로 풀어가는 가장 자연스러운 첫삽입니다.

3. 지금까지 통과한 것과 실패한 것

중간에 make check를 돌렸을 때, alarm 계열과 ready list priority 계열은 통과했고 donation, semaphore, condition 쪽이 실패했습니다. 이 로그는 방향을 꽤 정확하게 알려줍니다.

상태	테스트	해석
PASS	`alarm-*`, `priority-preempt`, `priority-change`, `priority-fifo`	Alarm Clock과 ready list priority 정렬은 어느 정도 동작한다.
FAIL	`priority-sema`, `priority-condvar`	semaphore와 condition variable의 waiters가 아직 priority 기준으로 깨지지 않는다.
FAIL	`priority-donate-*`	lock holder에게 priority donation이 들어가지 않거나, release 후 복구가 제대로 되지 않는다.
제외	`mlfqs-*`	Advanced Scheduler는 별도 단계다. 기본 priority scheduler를 먼저 끝낸 뒤 들어간다.

4. 전체 구조를 먼저 보면

이번 수정의 큰 방향은 단순합니다. 기존 FIFO 대기열을 priority를 아는 대기열로 바꾸고, lock 때문에 막힌 높은 priority thread의 priority를 lock holder에게 임시로 빌려줍니다.

ready_list
priority 정렬 + sema waiters
highest 먼저 wake + cond waiters
semaphore_elem 정렬 + lock donation
multiple / nested

여기서 중요한 경계가 있습니다. priority donation은 lock에만 구현합니다. semaphore와 condition variable에는 donation을 구현하지 않지만, 그 waiters를 priority 순서로 깨우는 priority scheduling은 해야 합니다.

5. thread.h: donation을 추적할 상태 추가

기존에는 thread에 priority 하나만 있었습니다. donation을 구현하려면 원래 priority와 donation이 반영된 priority를 분리해야 하고, 누가 어떤 lock 때문에 donation했는지도 추적해야 합니다.

4-1. 전방 선언

기존 코드 블록:

#include "threads/interrupt.h"
#ifdef VM
#include "vm/vm.h"
#endif

바꿀 최종 블록:

#include "threads/interrupt.h"
#ifdef VM
#include "vm/vm.h"
#endif

struct lock; /* struct thread 안에서 struct lock *를 쓰기 위한 전방 선언 */

블록 설명: wait_on_lock 필드가 struct lock * 타입을 쓰기 때문에, thread.h에서 lock 타입 이름을 먼저 알려줍니다.

4-2. struct thread priority 부분

기존 코드 블록:

char name[16];                      /* Name (for debugging purposes). */
int priority;                       /* Priority. */
int64_t wakeup_tick;                /* Tick when this thread should wake up.비지 웨이팅용 */
/* Shared between thread.c and synch.c. */
struct list_elem elem;              /* List element. */

바꿀 최종 블록:

char name[16];                      /* Name (for debugging purposes). */
int priority;                       /* 실제 스케줄링에 쓰는 priority. donation 반영값 */
int base_priority;                  /* 원래 priority. thread_set_priority()가 바꾸는 값 */
struct list donations;              /* 나에게 priority를 빌려준 thread들의 목록 */
struct list_elem donation_elem;     /* 내가 다른 thread의 donations 목록에 들어갈 때 쓰는 elem */
struct lock *wait_on_lock;          /* 내가 지금 기다리는 lock. nested donation 추적용 */
int64_t wakeup_tick;                /* Tick when this thread should wake up.비지 웨이팅용 */
/* Shared between thread.c and synch.c. */
struct list_elem elem;              /* List element. */

블록 설명

base_priority는 원래 priority이고, priority는 donation까지 반영된 실제 priority입니다. donations는 multiple donation을, wait_on_lock은 nested donation과 release 시 donation 제거 기준을 처리합니다.

6. thread.c: priority 상태를 유지하는 기반 코드

5-1. helper 선언

기존 코드 블록:

static bool thread_priority_ver_alram (const struct list_elem *a,
        const struct list_elem *b, void *aux); // 알람pririty 용 함수 선언

static void do_schedule(int status);

바꿀 최종 블록:

static bool thread_priority_ver_alram (const struct list_elem *a,
        const struct list_elem *b, void *aux); /* ready_list priority 정렬 기준 */

static bool donation_priority_more (const struct list_elem *a,
        const struct list_elem *b, void *aux); /* donations 목록 정렬 기준 */

static void do_schedule(int status);

블록 설명: ready list는 elem으로 정렬하고, donations list는 donation_elem으로 정렬하므로 비교 함수를 분리합니다.

5-2. init_thread()

기존 코드 블록:

t->priority = priority;
t->magic = THREAD_MAGIC;

바꿀 최종 블록:

t->priority = priority;        /* 실제 priority 초기값 */
t->base_priority = priority;   /* 원래 priority도 같은 값으로 시작 */
list_init (&t->donations);     /* donation 목록은 빈 리스트로 시작 */
t->wait_on_lock = NULL;        /* 처음에는 기다리는 lock이 없음 */
t->magic = THREAD_MAGIC;

블록 설명: 새 필드를 초기화하지 않으면 donation 목록과 lock 포인터가 쓰레기 값을 가지게 됩니다. donation 버그는 대부분 이런 상태 추적 실패에서 시작합니다.

5-3. thread_set_priority()

기존 코드 블록:

void
thread_set_priority (int new_priority) {
    struct thread *curr = thread_current ();

    curr->priority = new_priority;

    if (!list_empty (&ready_list)) {
        struct thread *front = list_entry (list_front (&ready_list),
                struct thread, elem);

        if (front->priority > curr->priority)
            thread_yield ();
    }
}

바꿀 최종 블록:

void
thread_set_priority (int new_priority) {
    struct thread *curr = thread_current ();

    curr->base_priority = new_priority; /* 사용자가 바꾸는 값은 원래 priority에 저장 */

    if (list_empty (&curr->donations))  /* donation을 받는 중이 아니면 */
        curr->priority = new_priority; /* 실제 priority도 바로 변경 */
    else {
        list_sort (&curr->donations, donation_priority_more, NULL);
        /* donation 목록을 priority 높은 순서로 정렬 */

        struct thread *donor = list_entry (list_front (&curr->donations),
                struct thread, donation_elem);
        /* 가장 높은 priority를 빌려준 thread */

        curr->priority = donor->priority > new_priority
            ? donor->priority   /* donation priority가 더 높으면 유지 */
            : new_priority;     /* 새 base_priority가 더 높으면 그 값 사용 */
    }

    if (!list_empty (&ready_list)) {
        struct thread *front = list_entry (list_front (&ready_list),
                struct thread, elem);
        /* ready_list에서 현재 가장 높은 priority thread */

        if (front->priority > curr->priority)
            thread_yield (); /* 내가 최고 priority가 아니면 CPU 양보 */
    }
}

블록 설명

donation 중에는 사용자가 priority를 낮춰도 실제 priority가 바로 낮아지면 안 됩니다. 예를 들어 base 31, donation 41 상태에서 thread_set_priority(21)을 호출하면 base는 21이 되지만 실제 priority는 41을 유지해야 합니다.

5-4. next_thread_to_run()

기존 코드 블록:

static struct thread *
next_thread_to_run (void) {
    if (list_empty (&ready_list))
        return idle_thread;
    else
        return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

바꿀 최종 블록:

static struct thread *
next_thread_to_run (void) {
    if (list_empty (&ready_list))
        return idle_thread;
    else {
        list_sort (&ready_list, thread_priority_ver_alram, NULL);
        /* donation으로 ready_list 안 thread priority가 바뀌었을 수 있어 재정렬 */

        return list_entry (list_pop_front (&ready_list), struct thread, elem);
        /* 정렬 후 맨 앞, 즉 가장 높은 priority thread를 실행 */
    }
}

블록 설명: donation은 ready list 안에 이미 들어간 thread의 priority도 바꿀 수 있습니다. 따라서 scheduler가 실제로 고르기 직전에 한 번 정렬합니다.

7. synch.c: semaphore waiters를 priority 순서로 깨우기

semaphore는 원래도 있었습니다. 바뀐 것은 semaphore 자체가 아니라 sema->waiters를 FIFO처럼 쓰던 방식입니다. 깃북 요구에 맞추려면 waiters를 priority 기준으로 관리해야 합니다.

6-1. sema_down()

기존 코드 블록:

while (sema->value == 0) {
    list_push_back (&sema->waiters, &thread_current ()->elem);
    thread_block ();
}

바꿀 최종 블록:

while (sema->value == 0) {
    list_insert_ordered (&sema->waiters, &thread_current ()->elem,
            synch_thread_priority_more, NULL);
    /* semaphore waiters도 priority 높은 thread가 앞에 오도록 삽입 */

    thread_block (); /* semaphore 값이 생길 때까지 현재 thread BLOCKED */
}

블록 설명: 기존에는 대기열 뒤에 붙였으므로 FIFO였습니다. 이제는 priority가 높은 thread가 앞쪽에 들어가도록 삽입합니다.

6-2. sema_up()

기존 코드 블록:

void
sema_up (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters))
        thread_unblock (list_entry (list_pop_front (&sema->waiters),
                    struct thread, elem));
    sema->value++;
    intr_set_level (old_level);
}

바꿀 최종 블록:

void
sema_up (struct semaphore *sema) {
    enum intr_level old_level;
    struct thread *unblocked = NULL; /* 이번 sema_up으로 깨운 thread */

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters)) {
        list_sort (&sema->waiters, synch_thread_priority_more, NULL);
        /* waiters 안에서 priority가 바뀌었을 수 있으니 깨우기 전 재정렬 */

        unblocked = list_entry (list_pop_front (&sema->waiters),
                struct thread, elem);
        /* 가장 높은 priority waiter 선택 */

        thread_unblock (unblocked); /* BLOCKED -> READY */
    }
    sema->value++;

    if (unblocked != NULL && unblocked->priority > thread_current ()->priority) {
        if (intr_context ())
            intr_yield_on_return (); /* interrupt 중이면 interrupt 끝난 뒤 yield */
        else
            thread_yield ();         /* 일반 context면 즉시 CPU 양보 */
    }

    intr_set_level (old_level);
}

함수 흐름 그림

sema_down()은 value가 0이면 현재 thread를 waiters에 넣고 BLOCKED로 보냅니다. sema_up()은 waiters에서 priority가 가장 높은 thread를 꺼내 READY로 만들고, 그 thread가 현재 thread보다 높으면 CPU를 양보합니다.

8. lock donation: priority inversion 해결

priority inversion은 낮은 priority thread L이 lock을 들고 있고, 높은 priority thread H가 그 lock을 기다리는 상황입니다. donation은 H의 priority를 L에게 임시로 빌려줘서 L이 빨리 실행되고 lock을 놓게 만드는 장치입니다.

H
high priority waits for lock_A
holder = L donates to L
priority 상승

7-1. lock_acquire()

기존 코드 블록:

void
lock_acquire (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));

    sema_down (&lock->semaphore);
    lock->holder = thread_current ();
}

바꿀 최종 블록:

void
lock_acquire (struct lock *lock) {
    struct thread *curr = thread_current ();

    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));

    if (lock->holder != NULL) {
        curr->wait_on_lock = lock;
        /* 현재 thread가 이 lock을 기다린다는 사실 기록 */

        list_insert_ordered (&lock->holder->donations,
                &curr->donation_elem, donation_priority_more, NULL);
        /* lock holder의 donations 목록에 현재 thread를 donor로 추가 */

        donate_priority ();
        /* 현재 thread priority를 holder에게 전달하고, 필요하면 nested로 전파 */
    }

    sema_down (&lock->semaphore);
    /* lock이 비어날 때까지 BLOCKED */

    curr->wait_on_lock = NULL;
    /* lock을 얻었으므로 더 이상 기다리는 lock 없음 */

    lock->holder = curr;
    /* 현재 thread가 lock holder가 됨 */
}

블록 설명: 기존에는 lock을 얻지 못하면 그냥 잠들었습니다. 이제는 잠들기 전에 holder의 donations 목록에 현재 thread를 넣고, priority를 holder에게 전파합니다.

7-2. lock_release()

기존 코드 블록:

void
lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    lock->holder = NULL;
    sema_up (&lock->semaphore);
}

바꿀 최종 블록:

void
lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    remove_donations_for_lock (lock);
    /* 이 lock 때문에 나에게 들어온 donation만 제거 */

    refresh_priority ();
    /* 남은 donation과 base_priority 기준으로 내 priority 재계산 */

    lock->holder = NULL;
    /* lock 소유자 비움 */

    sema_up (&lock->semaphore);
    /* 이 lock을 기다리던 thread 중 highest priority thread를 깨움 */
}

블록 설명: lock을 놓을 때 모든 donation을 지우면 안 됩니다. 지금 release하는 lock 때문에 들어온 donation만 제거하고, 남은 donation 중 최고 priority를 다시 반영해야 합니다.

9. condition variable: semaphore_elem priority 저장

condition variable의 waiters는 thread를 직접 담지 않고 struct semaphore_elem으로 감쌉니다. 그래서 condition waiters를 priority 순서로 깨우려면 semaphore_elem 안에 priority를 저장해야 합니다.

8-1. struct semaphore_elem

기존 코드 블록:

struct semaphore_elem {
    struct list_elem elem;              /* List element. */
    struct semaphore semaphore;         /* This semaphore. */
};

바꿀 최종 블록:

struct semaphore_elem {
    struct list_elem elem;              /* List element. */
    struct semaphore semaphore;         /* This semaphore. */
    int priority;                       /* condition waiter의 priority 저장 */
};

8-2. cond_wait()

기존 코드 블록:

sema_init (&waiter.semaphore, 0);
list_push_back (&cond->waiters, &waiter.elem);
lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);

바꿀 최종 블록:

sema_init (&waiter.semaphore, 0);
waiter.priority = thread_get_priority ();
/* 현재 thread의 priority를 condition waiter에 저장 */

list_insert_ordered (&cond->waiters, &waiter.elem,
        semaphore_elem_priority_more, NULL);
/* condition waiters도 priority 높은 순서로 삽입 */

lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);

8-3. cond_signal()

기존 코드 블록:

if (!list_empty (&cond->waiters))
    sema_up (&list_entry (list_pop_front (&cond->waiters),
                struct semaphore_elem, elem)->semaphore);

바꿀 최종 블록:

if (!list_empty (&cond->waiters)) {
    list_sort (&cond->waiters, semaphore_elem_priority_more, NULL);
    /* signal 직전에 condition waiters를 priority 순서로 재정렬 */

    sema_up (&list_entry (list_pop_front (&cond->waiters),
                struct semaphore_elem, elem)->semaphore);
    /* 가장 높은 priority waiter의 semaphore를 up해서 깨움 */
}

블록 설명: 기존에는 condition waiters도 FIFO였습니다. 이제는 condition waiter가 저장한 priority를 기준으로 가장 높은 waiter를 먼저 깨웁니다.

10. synch.c helper 함수들

마지막으로 waiters 정렬과 donation 전파, donation 제거, priority 재계산을 담당하는 helper 함수가 필요합니다. 아래 함수들은 cond_broadcast() 아래쪽에 두는 보조 함수들입니다.

static bool
synch_thread_priority_more (const struct list_elem *a,
        const struct list_elem *b,
        void *aux UNUSED) {
    const struct thread *ta = list_entry (a, struct thread, elem);
    const struct thread *tb = list_entry (b, struct thread, elem);

    return ta->priority > tb->priority;
    /* semaphore waiters에서 priority 높은 thread가 앞 */
}

static bool
donation_priority_more (const struct list_elem *a,
        const struct list_elem *b,
        void *aux UNUSED) {
    const struct thread *ta = list_entry (a, struct thread, donation_elem);
    const struct thread *tb = list_entry (b, struct thread, donation_elem);

    return ta->priority > tb->priority;
    /* donations 목록에서 priority 높은 donor가 앞 */
}

static bool
semaphore_elem_priority_more (const struct list_elem *a,
        const struct list_elem *b,
        void *aux UNUSED) {
    const struct semaphore_elem *sa = list_entry (a, struct semaphore_elem, elem);
    const struct semaphore_elem *sb = list_entry (b, struct semaphore_elem, elem);

    return sa->priority > sb->priority;
    /* condition waiters에서 priority 높은 waiter가 앞 */
}

donation 전파와 회수:

static void
donate_priority (void) {
    struct thread *curr = thread_current ();
    int depth = 0;

    while (curr->wait_on_lock != NULL && depth < DONATION_DEPTH_LIMIT) {
        struct lock *lock = curr->wait_on_lock;
        struct thread *holder = lock->holder;

        if (holder == NULL)
            break;

        if (holder->priority < curr->priority)
            holder->priority = curr->priority;
        /* curr의 priority를 lock holder에게 donation */

        curr = holder;
        /* holder가 또 다른 lock을 기다리면 다음 루프에서 그 holder에게도 전파 */

        depth++;
    }
}

static void
remove_donations_for_lock (struct lock *lock) {
    struct thread *curr = thread_current ();
    struct list_elem *e = list_begin (&curr->donations);

    while (e != list_end (&curr->donations)) {
        struct thread *donor = list_entry (e, struct thread, donation_elem);
        struct list_elem *next = list_next (e);

        if (donor->wait_on_lock == lock)
            list_remove (e);
        /* 지금 release하는 lock 때문에 들어온 donation만 제거 */

        e = next;
    }
}

static void
refresh_priority (void) {
    struct thread *curr = thread_current ();

    curr->priority = curr->base_priority;
    /* 일단 원래 priority로 복구 */

    if (!list_empty (&curr->donations)) {
        list_sort (&curr->donations, donation_priority_more, NULL);
        /* 남은 donation 중 가장 높은 donor를 찾기 위해 정렬 */

        struct thread *donor = list_entry (list_front (&curr->donations),
                struct thread, donation_elem);

        if (donor->priority > curr->priority)
            curr->priority = donor->priority;
        /* base_priority보다 높은 donation이 남아 있으면 그 값을 유지 */
    }
}

블록 설명

donate_priority()는 H → M → L 같은 nested donation을 최대 8단계까지 전파합니다. remove_donations_for_lock()은 release하는 lock 때문에 생긴 donation만 제거하고, refresh_priority()는 남은 donation과 base priority 중 가장 큰 값을 실제 priority로 다시 잡습니다.

11. semaphore 작동 흐름을 그림으로 다시 보기

이번 수정에서 헷갈리기 쉬운 부분은 semaphore입니다. semaphore 자체가 새로 생긴 것이 아니라, waiters를 깨우는 순서가 priority 기준으로 바뀐 것입니다.

sema_down
value 확인 0이면 waiters 삽입
priority 순서 → BLOCKED
대기 → sema_up
highest wake

기존 FIFO에서는 먼저 기다린 thread가 먼저 깨어났습니다. 수정 후에는 waiters 중 priority가 가장 높은 thread가 먼저 깨어납니다.

12. 확인할 테스트

이 글의 목표는 MLFQS가 아니라 기본 Priority Scheduling입니다. 따라서 먼저 아래 테스트 묶음을 확인합니다.

cd ~/pintos/threads/build
source ../../activate

for t in priority-change priority-donate-one priority-donate-multiple \
priority-donate-multiple2 priority-donate-nest priority-donate-sema \
priority-donate-lower priority-fifo priority-preempt priority-sema \
priority-condvar priority-donate-chain alarm-priority; do
  make tests/threads/$t.result
  cat tests/threads/$t.result
done

MLFQS는 여기서 제외

mlfqs-* 테스트는 Advanced Scheduler 구현이 필요합니다. 기본 Priority Scheduling과 Donation을 완성해도 자동으로 통과되는 영역이 아닙니다.

이번 글에서 기억할 것

기본 Priority Scheduler는 ready list만 정렬한다고 끝나지 않는다.
깃북 요구사항은 먼저 불변 조건과 테스트 장면으로 바꿔야 코드 수정 지점이 보인다.
semaphore와 condition variable waiters도 priority가 높은 thread를 먼저 깨워야 한다.
lock에서 생기는 priority inversion은 donation으로 해결한다.
multiple donation과 nested donation을 처리하려면 donations list와 wait_on_lock이 필요하다.
MLFQS는 donation을 쓰지 않는 별도 스케줄러이므로 다음 단계로 분리한다.

다음 글 예고

다음 글에서는 MLFQS / Advanced Scheduler로 넘어갑니다. MLFQS는 사용자가 준 priority와 donation이 아니라 nice, recent_cpu, load_avg 공식으로 priority를 자동 계산하는 스케줄러입니다. 같은 priority 안에서는 Round Robin처럼 돌아가며 실행된다는 점도 같이 정리할 수 있습니다.

Pintos · Project 2 User Programs · 1편 (1)	2026.05.02
운영체제 · Pintos · Project 1 Threads · 3편 (1)	2026.04.29
운영체제 · Pintos · Project 1 Threads · 1편 (0)	2026.04.29
크래프트 정글 × 바이브 프로젝트 미니 DBMS - API 서버 (0)	2026.04.23
크래프트 정글 × 바이브 프로젝트Mini SQL을 두 번 만들고 나서야보인 것들 (1)	2026.04.16

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

cedis 님의 블로그

운영체제 · Pintos · Project 1 Threads · 2편

Pintos 기본 Priority Scheduler: waiters 정렬과 priority donation 구현하기

이번 글에서 다루는 것

1. 깃북 요구사항을 먼저 번역하면

2. 왜 이 요구사항을 이렇게 풀어야 하는가

3. 지금까지 통과한 것과 실패한 것

4. 전체 구조를 먼저 보면

5. thread.h: donation을 추적할 상태 추가

4-1. 전방 선언

4-2. struct thread priority 부분

6. thread.c: priority 상태를 유지하는 기반 코드

5-1. helper 선언

5-2. init_thread()

5-3. thread_set_priority()

5-4. next_thread_to_run()

7. synch.c: semaphore waiters를 priority 순서로 깨우기

6-1. sema_down()

6-2. sema_up()

8. lock donation: priority inversion 해결

7-1. lock_acquire()

7-2. lock_release()

9. condition variable: semaphore_elem priority 저장

8-1. struct semaphore_elem

8-2. cond_wait()

8-3. cond_signal()

10. synch.c helper 함수들

11. semaphore 작동 흐름을 그림으로 다시 보기

12. 확인할 테스트

이번 글에서 기억할 것

다음 글 예고

'개발 > 프로젝트' 카테고리의 다른 글

'개발/프로젝트'의 다른글

티스토리툴바

운영체제 · Pintos · Project 1 Threads · 2편

이번 글에서 다루는 것

1. 깃북 요구사항을 먼저 번역하면

2. 왜 이 요구사항을 이렇게 풀어야 하는가

3. 지금까지 통과한 것과 실패한 것

4. 전체 구조를 먼저 보면

5. thread.h: donation을 추적할 상태 추가

4-1. 전방 선언

4-2. struct thread priority 부분

6. thread.c: priority 상태를 유지하는 기반 코드

5-1. helper 선언

5-2. init_thread()

5-3. thread_set_priority()

5-4. next_thread_to_run()

7. synch.c: semaphore waiters를 priority 순서로 깨우기

6-1. sema_down()

6-2. sema_up()

8. lock donation: priority inversion 해결

7-1. lock_acquire()

7-2. lock_release()

9. condition variable: semaphore_elem priority 저장

8-1. struct semaphore_elem

8-2. cond_wait()

8-3. cond_signal()

10. synch.c helper 함수들

11. semaphore 작동 흐름을 그림으로 다시 보기

12. 확인할 테스트

이번 글에서 기억할 것

다음 글 예고

'개발 > 프로젝트' 카테고리의 다른 글

'개발/프로젝트'의 다른글

관련글

티스토리툴바