[PintOS] Project1: Part2 Priority Scheduling and Synchronization

Priority Scheduling and Synchronization

과제 목표

• 지금까지 작업한 pintos에서 thread가 semaphore를 가져가는 순서는 FIFO순으로 되어있다. 이것은 priority가 높은 순으로 semaphore를 가져갈 수 있도록 할 것이다.
• 세마포어(semaphore)는 추상화한 개념으로 추상자료형(ADT)으로, 정수 형태의 변수이며 두 가지 연산(P 연산-세마포어변수값을 흭득, V 연산-세마포어를 다 쓰고 반납)으로 접근이 가능하다. 세마포어를 쓰는 이유는 공유 자원에 lock을 걸고/풀고 하는 것을 추상화하여 쉽게 접근하기 위함이다.

• (좌) FIFO: 우선순위와 상관없이 먼저 들어온 파란 블록이 먼저 lock을 받음

• (우) Priority Scheduling: 우선순위가 가장 높은 연보라색이 가장 먼저 lock을 획득

• 공통 부분적인 부분은 가장 아래 연두색 블록이 처음 lock을 받는다. 연두색 블록이 들어오는 시점을 기준으로는 이외에 어떤 블록도 없기 때문이다. 이후에 들어온 파란색 블록이 lock을 요청한다. 이때까지만 해도 waiters에는 동일하다. 이제 그 다음 블록인 연보라 블록부터 상황이 달라지는데, 왼쪽의 FIFO에서는 우선순위를 전혀 고려하지 않으니 자연스럽게 head 블록인 파란색 다음으로 연보라가 온다. 하지만 오른쪽 이미지에서는 Priority를 고려하기 때문에 head 블록으로 연보라가 오고 파란색 블록은 tail로 밀려난다. 그 다음 역시 왼쪽은 무조건 tail에 붙고 오른쪽에서는 우선순위를 고려해 적절한 위치를 찾아간다.

@/include/threads/synch.h
 
 
/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

• struct semaphore는 semaphore를 관리하기 위한 구조체로서 semaphore의 현재 상태인 value(해당 자원의 개수를 나타냄)와 이 semaphore를 기다리는 waiters(list 구조체, 자원을 기다리는 스레드가 줄 서있음) 가 있다.

@/threads/synch.c

/* One semaphore in a list. */
struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
};

• 해당 elem은 스레드가 ready queue에 매달려 있기 위한 용도이므로, 세마포어를 위한 또다른 elem을 만든 것이다.

semaphore와 관련된 함수들

@/threads/synch.c
   
void sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL);
 
	sema->value = value;
	list_init (&sema->waiters);
}

• 세마포어를 초기화하는 함수, 주어진 value로 초기화하며 빈 waiters 리스트를 생성한 다음 곧장 해당 세마포어를 리스트의 첫째 자리에 넣는다.

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_push_back (&sema->waiters, &thread_current ()->elem); // FIFO
    thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}

• 세마포어의 P연산에 해당하는 sema_down( ), 즉 자원을 흭득하는 연산이다. 현재 자원이 없는 상태라면 while문을 돌면서 현재 스레드를 waiters 리스트의 맨 끝에 삽입한 다음 block 상태로 만들어 재운다. 자원이 생기면 value는 0이 되면서 while문을 종료하고 value 값을 1로 내린 뒤 해당 스레드가 자원을 흭득할 수 있게 해준다. 이 과정에서는 다른 인터럽트의 허용을 막는다.

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);
}

• 세마포어의 V연산에 해당하는 sema_up( ), 즉 자원을 반납하는 연산이다. 현재 waiters 리스트에서 기다리고 있는 스레드가 있다면 리스트 맨 앞에 있는 스레드를 unblock시켜서 깨운다. 그러면 기다리고 있던 스레드가 알아서 P연산으로 자원을 가져갈 것이다. 이 과정에서 인터럽트를 허용하지 않게 설정한다.

lock 관련 함수들

@/threads/synch.c

void
lock_init (struct lock *lock) {
	ASSERT (lock != NULL);
 
	lock->holder = NULL;
	sema_init (&lock->semaphore, 1);
}

• lock은 semaphore와 lock->holder를 가지고 있는 구조체이다. lock->holder 는 thread이며, semaphore는 어떤 thread가 lock을 가질 수 있는지(sema->value > 0), 가질 수 없다면 대기리스트(waiters)에 들어간다.

@/threads/synch.c

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 ();
}

• running중인 thread가 어떤 임계 영역을 써야될 때, 해당 임계영역을 사용가능한가 (semaphore->value > 0) 를 확인한다. 이 thread가 lock을 얻는다면 lock->holer 를 thread_current()로 지정한다.

@/threads/synch.c

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));
 
	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

• lock의 semaphore를 다 사용하고 나면 lock을 반납한다.

condition variable 관련 함수들

@/threads/synch.c

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

• conditional variable로 관리한다. 여기서는 signal로 관리하기때문에 대기 리스트(waiters)만 필요로 한다.

@/threads/synch.c
 
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_push_back (&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}
 
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))
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}
 
void
cond_broadcast (struct condition *cond, struct lock *lock) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
 
	while (!list_empty (&cond->waiters))
		cond_signal (cond, lock);
}

• 위의 cond관련 함수들은 위의 Monitor관련 참조글에 설명되어있다.
• condition variable 참고글

구현

• 전 과제에서 만든 cmp_priority( )함수를 이용하여, priority 순대로 삽입될 수 있도록 한다.

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)
	{
		/* waiters 리스트 삽입 시, 우선순위대로 삽입 */
		list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL);
		thread_block();
	}
	sema->value--;
	intr_set_level(old_level);
}

• 기존에 FIFO로 삽입하는 list_push_back()을 제거하고 list_inser_ordered()로 수정했다. 이때, 우선순위를 비교하는 함수인 cmp_priority()을 사용한다.

• 우선순위로 정렬하는 것은 사실 이 챕터에선 필요없다. 왜냐하면 우선순위가 변경되는 것은 running_thread의외는 없기 때문이다. waiter_list에 있는 thread의 priority가 변경되는 일은 차후 단계의 donation에서 일어난다.

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

	ASSERT(sema != NULL);

	old_level = intr_disable();

	if (!list_empty(&sema->waiters))
	{
		/* 스레드가 waiters list에 있는 동안 우선순위가 변경 되었을 경우를
        고려하여 waiters list를 우선순위로 정렬 한다. */
		list_sort(&sema->waiters, cmp_priority, NULL);
		thread_unblock(list_entry(list_pop_front(&sema->waiters),
								  struct thread, elem));
	}
	sema->value++;
    
	/* priority preemption 코드 추가 */
	test_max_priority();
    
	intr_set_level(old_level);
}

• thread_unblock으로 ready_list에 들어간 thread가 running중인 thread보다 더 우선순위가 높을 수 있으므로 priority preemption()을 실행해준다.

• 우선 semaphore_elem을 받아와서 해당 semphore의 주인 thread의 priority를 비교할 수 있는 함수를 만든다. 이는 cmp_priority와 거의 유사하다.

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

	struct list_elem *ta = list_begin(&sa->semaphore.waiters);
	struct list_elem *tb = list_begin(&sb->semaphore.waiters);
	return cmp_priority(ta, tb, NULL);
}

• condition variable 내 waiters list에 스레드를 대기시키는 함수. 어떤 스레드 하나가 critical section에 들어가 있다면 lock에서는 하나의 스레드 이외의 나머지는 CS에 들어갈 수 없으며 바깥에서 줄서서 대기하고 있어야 한다.

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);
	/* condition variable의 waiters list에 우선순위 순서로 삽입 */
	list_insert_ordered(&cond->waiters, &waiter.elem, cmp_sem_priority, NULL);
	lock_release(lock);
	sema_down(&waiter.semaphore);
	lock_acquire(lock);
}

• 여기서는 중간에 우선순위가 바뀌었을 수 있으니 waiters list 내 우선순위를 점검하고(list_sort), 그 다음 리스트 맨 앞에 있는 우선순위가 가장 높은 스레드에 대해 sema_up을 실행한다.

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))
	{
		/* condition variable의 waiters list를 우선순위로 재정렬 */
		list_sort(&cond->waiters, cmp_sem_priority, NULL);
		sema_up(&list_entry(list_pop_front(&cond->waiters),
							struct semaphore_elem, elem)
					 ->semaphore);
	}
}

결과

요약

• 추가 함수

• 수정 함수

PintOS Project1 GIthub 주소 PintOS