Pintos Part 1-4. Priority Scheduling w/ Priority Condition Variable

아직 한 발 남았습니다. Credit: https://www.facebook.com/photo/?fbid=692610764617030

priority-condvar 테스트가 남았다

이번 포스트에서는 Pintos의 우선순위 스케줄링 구현의 마지막 단계인 priority-condvar 및 관련 개념을 다룹니다. 

들어가기에 앞서 mutex와 semaphore, condition variable에 대한 포스트를 읽고 와주시기를 권해 드립니다.

잠깐, Priority Scheduling에서 Condition Variable은?

대략적인 구조는 위와 같으며, 아래가 바로 synch.h에 위치한 컨디션 변수입니다.

---

문제 상황

Pintos는 기본적으로 비선점형 FIFO 정책으로 스레드를 처리하도록 되어 있었고, 지금까지 저희는 이를 선점형 우선순위 스케줄링으로 고치고 있었습니다. 다만 synch.c/h의 함수들을 수정하지 않은 채 내버려두고 있었지요. synch.h의 cond_init, cond_wait, cond_signal, cond_broadcast 같은 것들은 모두 동기화가 필요할 때 사용하기 위한 API와도 같은 것들인데, 이쪽을 내버려두고 있었으니 둘이 서로 다른 정책을 가지는 것입니다. 이를 해결하지 않으면 priority-condvar 테스트는 통과가 어렵습니다.

이를 사용하는 예시는 아래와 같습니다. 이 포스트에서 소개해드린 생산자-소비자 패턴의 Pintos 버전입니다.

#include "threads/thread.h"
#include "threads/synch.h"
#include <stdio.h>

static int buffer = 0; // 공유 자원
static int data_ready = 0;

/* Pintos 동기화 툴 */
static struct lock buffer_lock;
static struct condition cond;

void producer(void *aux UNUSED) {
    timer_sleep(100);  // 생산이 늦게 일어나는 상황 시뮬레이션 (tick 단위)

    lock_acquire(&buffer_lock);

    buffer = 42;
    data_ready = 1;
    printf("Producer: 데이터 생성 완료!\n");

    cond_signal(&cond, &buffer_lock);  // 소비자 깨움
    lock_release(&buffer_lock);
}

void consumer(void *aux UNUSED) {
    lock_acquire(&buffer_lock);
    while (data_ready == 0) {
        printf("Consumer: 데이터 생성을 기다리는 중...\n");
        cond_wait(&cond, &buffer_lock);  // 조건 만족까지 대기
    }

    printf("Consumer: 데이터 획득! %d\n", buffer);
    lock_release(&buffer_lock);
}

void main(void) {
    lock_init(&buffer_lock);
    cond_init(&cond);

    thread_create("consumer", PRI_DEFAULT, consumer, NULL);
    thread_create("producer", PRI_DEFAULT, producer, NULL);
}

요컨대,

• timer.c/h, thread.c/h → 스케줄러 자체
• synch.c/h → 그 스케줄러 위에서 동기화 툴을 제공하는 API 레이어 내지는 라이브러리

...로 이해할 수 있습니다.

---

해결하기

threads/synch.c 및 .h를 확인하여 아래와 같이 반영합니다.

• 구조체 구성 확인
  • 기본으로 제공된 구조체가 아래와 같은지 확인해주세요. 위 3개는 .h에, 아래 1개는 .c에 있습니다.

/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	
	// 이 waiters에는 이 semaphore에 관련하여 잠자고 있는 스레드 (struct thread의 elem 멤버)이 저장됨.
	struct list waiters;        /* List of waiting threads. */
	
};
/* Lock. */
struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

/* Condition variable. */
// 각 공유 자원마다 하나씩 가짐. 공유 자원별로 따로따로 하나씩 갖고 있어야 함.
struct condition {
	// 이 waiters에는 조건이 충족될 때까지 기다리는 세마포어들이 저장됨.
	struct list waiters;        /* List of waiting threads. */
};

/* One semaphore in a list. */
// 현재 스레드가 사용할 "자기 전용 이진 세마포어".
struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
};

• 비교 함수 추가
  • 아래 sema_priority_cmp() 및 donation_priority_cmp()를 추가합니다.

// 두 sema의 'waiters list내 스레드 중 제일 높은 priority'를 비교
// a가 높으면 true, b가 높으면 false.
bool sema_priority_cmp(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
	struct semaphore_elem *sema_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sema_b = list_entry(b, struct semaphore_elem, elem);

	struct list *waiters_a = &(sema_a->semaphore.waiters);
	struct list *waiters_b = &(sema_b->semaphore.waiters);

	struct thread *root_a = list_entry(list_begin(waiters_a), struct thread, elem);
	struct thread *root_b = list_entry(list_begin(waiters_b), struct thread, elem);

	return root_a->priority > root_b->priority;
}

// donation_elem의 priority를 기준으로 비교
// a가 높으면 true, b가 높으면 false.
bool donation_priority_cmp(const struct list_elem *a,
						   const struct list_elem *b, void *aux UNUSED){
	struct thread *st_a = list_entry(a, struct thread, donation_elem);
	struct thread *st_b = list_entry(b, struct thread, donation_elem);
	return st_a->priority > st_b->priority;
}

• cond_wait() 수정
  • 스레드가 컨디션 변수를 기다릴 때, 우선순위로 정렬하여 삽입합니다.

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_priority_cmp, NULL); // priority condvar 구현
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

• cond_signal() 수정
  • 스레드를 깨울 때 우선순위를 고려하여 가장 높은 우선순위 스레드를 먼저 깨웁니다.

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

• lock_acquire() 수정
  • 락을 체결하는 과정에서 donation priority 순서대로 정렬 삽입하도록 구성합니다.

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


	/*-- Priority donation 과제 --*/
    struct thread *t = thread_current();
    if (lock->holder != NULL) {
        t->wait_lock = lock;
        
        /*-- Priority condvar 과제 --*/
		list_insert_ordered(&lock->holder->donations, &t->donation_elem, donation_priority_cmp, NULL);
        /*-- Priority condvar 과제 --*/
    
        donate_priority();
    }

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

	t->wait_lock = NULL;
	lock->holder = thread_current();
	/*-- Priority donation 과제 --*/
}

---

테스트 및 검증

priority-condvar까지의 모든 테스트들이 통과되는지 확인하면 성공입니다. Advanced scheduler (MLFQS)를 제외한 모든 항목들의 통과를 확인할 수 있습니다.