[swjungle] WEEK08 WIL - pintOS

1. Alarm Clock (04/25 목 ~ 04/27 토)

• 1.1 Initial Implementation

  • 초기 timer_sleep() 구현에서 CPU 자원 낭비 문제를 식별하고, 바쁜 대기(Busy-waiting)의 문제점을 파악함.
  • 타이머 인터럽트를 활용하여 슬립 함수를 개선하는 방식으로 구현함.
    tick을 기준으로 슬립 함수를 구현하고, 이를 통해 CPU 자원을 효율적으로 사용할 수 있도록 함. sleep_wakeup() 함수를 통해 스레드를 대기시키고, 타이머 인터럽트를 통해 스레드를 깨우는 방식으로 구현함.

• 1.2 Timer Interrupt

  • 타이머 인터럽트를 사용하여 스레드를 효율적으로 대기시키고 깨우는 메커니즘을 배우고, sleep_wakeup() 함수를 통해 구현함.

---

2. Priority Scheduling (04/27 토 ~ 04/29 월)

semaphore, lock, condition variable을 이용하여 스레드가 락(lock), 세마포어(semaphore), 조건 변수(condition variable)를 기다릴 때, 우선순위가 가장 높은 스레드가 CPU를 점유할 수 있게끔 구현함.

• 조건 변수 관련한 의문: Pintos에서의 조건 변수 구현을 살펴보며, 일반적으로 조건 변수는 명시된 "조건"에 따라 스레드의 대기 및 깨우기를 관리한다고 알고 있었는데, Pintos의 예제 코드(priority_condvar.c)에서는 이러한 "조건"이 명확하게 정의되어 있지 않아서 모호하다고 느꼈고, 테스트 케이스를 좀 더 분석해보면서 의문점을 해결하고자 했습니다.

---

3. Priority Inversion Problem (04/29 월 ~ 05/01 수)

• 우선순위 역전 : 우선순위가 높은 스레드가 낮은 우선순위의 스레드를 기다리는 현상을 다룸.

  • 3.1 Priority Donation

    • 우선순위 기부 메커니즘을 구현하여, 높은 우선순위 스레드가 낮은 우선순위 스레드에 의해 블록되는 것을 방지함.

  • 3.2 Multiple Priority Donation

    • 스레드가 여러 개의 락을 보유할 경우, 각 락에 의해 우선순위 도네이션이 발생할 수 있으며, 스레드는 이전 우선순위 상태를 기억해야 함.

  • 3.3 Nested Priority Donation

    • 중첩된 우선순위 기부 상황을 처리하여 다중 락 상황에서도 우선순위 역전 문제를 해결함.

질문 요약

Pintos의 priority-condvar.c 테스트 코드에서 조건 변수가 어떻게 사용되는지, 그리고 테스트 코드에서 정의된 "조건"의 역할에 대한 질문입니다. 코드에서 cond_wait()와 cond_signal() 함수가 중심적으로 사용되고 있으나, 이들이 어떠한 조건을 기반으로 스레드를 대기시키고 깨우는지에 대한 명확한 구현이 보이지 않습니다.

조교님의 답변

priority-condvar.c는 일반적인 조건 변수 사용과는 다르게, 특정 "조건" 없이 우선순위에 따라 cond_wait() 중인 스레드를 깨우는 것을 테스트하는 코드입니다. 조건 변수는 특정 "조건"이 만족될 때까지 스레드를 대기하게 할 필요가 있을 때 사용되지만, 실제로 "조건"은 조건 변수 외부에서 정의되며, 조건 변수 자체는 스레드를 대기 상태로 만드는 역할만 합니다.

코드 예시

void waiting_thread() {
    lock.acquire(); // 조건 변수 사용 전에 lock 획득

    while (유저가 설정한 조건 == false) {
        cond_var.wait(&lock); // 조건이 참이 될 때까지 대기
    }

    lock.release(); // lock 해제
}

조건 변수 관련한 의문에 대하여

Pintos에서의 조건 변수 구현을 살펴보며, 일반적으로 조건 변수는 명시된 "조건"에 따라 스레드의 대기 및 깨우기를 관리한다고 알고 있었는데, Pintos의 예제 코드(priority_condvar.c)에서는 이러한 "조건"이 명확하게 정의되어 있지 않아서 모호하다고 느꼈고, 테스트 케이스를 좀 더 분석해보면서 의문점을 해결하고자 했습니다.

• 질문

Pintos의 priority-condvar.c 테스트 코드에서 조건 변수가 어떻게 사용되는지, 그리고 테스트 코드에서 정의된 "조건"의 역할에 대한 질문입니다. 코드에서 cond_wait()와 cond_signal() 함수가 중심적으로 사용되고 있으나, 이들이 어떠한 조건을 기반으로 스레드를 대기시키고 깨우는지에 대한 명확한 구현이 보이지 않습니다.

조교님 답변

priority-condvar.c는 일반적인 조건 변수 사용과는 다르게, 특정 "조건" 없이 우선순위에 따라 cond_wait() 중인 스레드를 깨우는 것을 테스트하는 코드.

조건 변수는 특정 "조건"이 만족될 때까지 스레드를 대기하게 할 필요가 있을 때 사용되지만, 실제로 "조건"은 조건 변수 외부에서 정의되며, 조건 변수 자체는 스레드를 대기 상태로 만드는 역할만 합니다.

---

• priority_condvar.c 테스트코드

/* Tests that cond_signal() wakes up the highest-priority thread
    waiting in cond_wait(). */

static thread_func priority_condvar_thread;
static struct lock lock;
static struct condition condition;

void
test_priority_condvar (void)
{
    int i;

    /* This test does not work with the MLFQS. */
    ASSERT (!thread_mlfqs);

    lock_init (&lock);
    cond_init (&condition);

    thread_set_priority (PRI_MIN);
    ***for (i = 0; i < 10; i++)
    {
        int priority = PRI_DEFAULT - (i + 7) % 10 - 1;
        char name[16];
        snprintf (name, sizeof name, "priority %d", priority);
        thread_create (name, priority, priority_condvar_thread, NULL);
    }

    for (i = 0; i < 10; i++)
    {
        lock_acquire (&lock);
        msg ("Signaling...");
        cond_signal (&condition, &lock);
        lock_release (&lock);
    }***
}

static void
priority_condvar_thread (void *aux UNUSED)
***{
    msg ("Thread %s starting.", thread_name ());
    lock_acquire (&lock);
    cond_wait (&condition, &lock);
    msg ("Thread %s woke up.", thread_name ());
    lock_release (&lock);
}***

• cond_wait

void cond_wait(struct condition *cond, struct lock *lock) {
    struct semaphore_elem waiter;

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

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

• cond_signal

void cond_signal(struct condition *cond, struct lock *lock UNUSED) {
    ASSERT(cond != NULL);
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(lock_held_by_current_thread(lock));
    if (!list_empty(&cond->waiters)) {
        list_sort(&cond->waiters, sema_compare_priority, NULL);
        sema_up(&list_entry(list_pop_front(&cond->waiters), struct semaphore_elem, elem)->semaphore);
    }
}

• sema_up

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

    ASSERT(sema != NULL);

    old_level = intr_disable();
    list_sort(&sema->waiters, compare_priority, NULL);
    if (!list_empty(&sema->waiters))                               // 대기중인 스레드가 있을 때
        thread_unblock(list_entry(list_pop_front(&sema->waiters),  // 대기중인 스레드를 깨움 맨 앞에 있는 놈으로 하는 중
                                    struct thread, elem));
    priority_preemtion();
    sema->value++;  //  깨웠으니까  락을 하나 늘림
    intr_set_level(old_level);
}

• sema_down

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

    ASSERT(sema != NULL);
    ASSERT(!intr_context());

    old_level = intr_disable();
    
    while (sema->value == 0) {
        list_insert_ordered(&sema->waiters, &thread_current()->elem, compare_priority, NULL);
        thread_block();
    }
    sema->value--;
    intr_set_level(old_level);
}

---

pintos- project1 회고

Pintos 프로젝트를 받고 문서도 다 영어였어서 이해하기가 어려웠는데,
코드를 타고 타고 들어가면서 디버깅으로 한줄씩 넘기면서 이해하니까 대략적인 갈피는 잡을 수 있었던 것 같다.
project1은 걸음마 정도인것으로 들었는데, project2,3은 훨씬 어렵다고 들었기 때문에 이번에는 좀 시간날때마다 코드를 보면서 전체 프로젝트의 그림을 그릴 수 있게끔 노력해야겠다고 생각했다.