구현 성공한 것

Alarm Clock

• timer_sleep 함수: ticks만큼 실행을 멈추는 함수
• Sleep Queue를 구현할 때 유념했던 점 2가지 정도

(1) 함수 정의 및 static 전역변수에 대한 이해

• static 전역변수로 선언한 경우, 해당 파일에서만 변수를 사용할 수 있음
• 하지만 해당 변수에 접근하는 함수를 만들고, 그걸 다른 파일에서 사용하는 건 자유
• thread.c에서 static으로 선언된 sleep_list, ready_list는 thread.c에서만 접근 가능
• 다른 파일에서 직접 접근 불가능

// thread.c
/* Alarm clock timer_sleep 구현을 위함. */

// 모든 쓰레드의 `wakeup_ticks` 중 최솟값
static int64_t min_wakeup_ticks = INT64_MAX;

 // 스케줄러 - 다음 쓰레드 스케줄링을 위한 연결리스트
static struct list ready_list;

// `timer_sleep`으로 블로킹한 쓰레드를 관리
static struct list sleep_list;

• 하지만 ready_list, sleep_list, min_wakeup_ticks에 접근하는 함수 thread_sleep, wake_up, save_min_ticks, get_min_ticks를 thread.c에서 정의하면, 해당 함수들은 다른 파일에서도 사용 가능
  • 참고로 thread_sleep: 현재 쓰레드를 재우고, sleep_list로 보냄, block 상태로 바꾸고, 다른 쓰레드를 스케줄링. 현재 실행 중이므로 ready_list에 없으니, 거기서 빼진 않아도 됨.
  • wake_up: sleep_list에서 깨워야 할 모든 쓰레드를, ready_list로 보내고, ready 상태로 바꿈
  • save_min_ticks로 min_wakeup_ticks 값 바꾸고, get_min_ticks로 해당 값을 반환.

• thread_sleep, wake_up 실행 중에는 인터럽트를 차단해서, 큐 갱신 과정에서 발생할 수 있는 동시성 문제를 해결
  • 특히 다른 타이머 인터럽트를 차단한다는 점에서 중요.

// thread.c 파일
// Saves the minimum value of ticks that threads have
void save_min_ticks(int64_t new_value){
	min_wakeup_ticks = new_value;
}

// Returns the minimum value of ticks
int64_t get_min_ticks(void){
	return min_wakeup_ticks;
}

// 현재 쓰레드를 sleep하고, ticks 시점에 깨움
void thread_sleep (int64_t ticks){
	// 함수를 호출한 쓰레드 자기 자신
	struct thread *curr = thread_current();

	// interrupt 차단하기
	enum intr_level old_level;
	old_level = intr_disable();

	if (curr != idle_thread){

		// 현재 쓰레드의 local wakeup_tick 저장.
		curr -> wakeup_tick = ticks;

		// 전역 min_wakeup_ticks 변수를 수정
		if (get_min_ticks() > ticks){
			save_min_ticks(ticks);
		}

		// 슬립 큐에 넣기 (슬립큐는 깨울 틱 수의 오름차순)
		list_insert_ordered(&sleep_list, &curr->elem, asc_ticks, NULL);

		// 지금 쓰레드는 BLOCKED로 전환 -> 스케줄링.
		do_schedule(THREAD_BLOCKED);

	}
	intr_set_level(old_level);
};

// sleep_list를 순회하면서 깨울 쓰레드를 찾음
void wake_up(int64_t ticks){
	// interrupt 차단하기
	enum intr_level old_level;
	old_level = intr_disable();

	// 깨울 쓰레드가 있는지 확인하기
	if (ticks >= min_wakeup_ticks){

		struct list_elem *node;
		struct thread *curr_thread;

		// sleep 리스트의 머리를 확인. ticks가 작은 순서부터. 깨울 thread가 있으면 찾음.
		while (!list_empty(&sleep_list)){
			node = list_front(&sleep_list);
			curr_thread = list_entry(node, struct thread, elem);

			// 더이상 깨울 쓰레드가 없음
			if ((curr_thread -> wakeup_tick) > ticks){

				break;
			}
			// 레디 큐에 넣기 (레디 큐는 priority의 내림차순)
			curr_thread -> status = THREAD_READY;
			list_insert_ordered(&ready_list, list_pop_front(&sleep_list), dsc_priority, NULL);
		}

		// global tick을 update
		if (list_empty(&sleep_list)){
			save_min_ticks(INT64_MAX);
		} else {
			save_min_ticks(curr_thread -> wakeup_tick);
		}
	}
	intr_set_level(old_level);
}

• 이제 timer.c에서 이 함수들을 호출할 수 있음. 이렇게 thread.c에 있는 static 전역변수를 간접적으로 접근할 수 있는 것

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);

	// 깨울 때까지 시간이 남은 경우, thread_sleep 호출
	if (timer_elapsed(start) < ticks){
		thread_sleep(start + ticks);
	}
}

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	// 깨울 쓰레드 찾고, 실제로 깨우기
	wake_up(ticks);
}

• 위처럼 변수는 다른 파일에서 접근하지 못하게 하되, 함수로 관리하는 것은 유지보수와 디버깅에 큰 도움이 됨
  • 오류가 발생했을 때 해당 파일의 함수만 확인하면 되기 때문

(2) 깨울 노드 찾기

• wake_up 함수는, 현재 슬립 큐에 있는 쓰레드 중 깨워야 하는 노드를 있는 대로 모두 깨움
  • 즉 현재 시각 ticks보다 깨우기로 한 시각 struct_thread -> wakeup_tick이 작거나 같은 경우, 깨워야 함
  • 단 깨우는 과정에서는, 연결 리스트(슬립 큐)에서 해당 노드를 빼야 함
  • 하지만 연결 리스트를 순회하는 도중에 노드를 빼면 제대로 순회가 이루어지지 않을 수 있음
• (1) 깨우기로 한 시각 (curr_thread -> wakeup_tick)의 오름차순으로 연결 리스트의 노드를 관리
  • 새로운 노드를 sleep 큐에 삽입할 때, 무조건 깨워야 할 시간의 오름차순으로 리스트가 정렬되게끔 알맞은 위치에 삽입해야 함
  • 이후에는 머리 노드만 반복적으로 확인하며, 현재 시각 >= 깨우기로 한 시각인 경우 노드를 빼는 방식으로 구현 가능.
  • 현재 시각 < 깨우기로 한 시각이 되면 반복문을 멈춤.
• (2) 이를 위해선 리스트에 노드를 삽입할 때 /pintos/lib/kernel/list.c의 list_insert_ordered 함수를 사용해야 함

void
list_insert_ordered (struct list *list, struct list_elem *elem,
		list_less_func *less, void *aux) {
	struct list_elem *e;

	ASSERT (list != NULL);
	ASSERT (elem != NULL);
	ASSERT (less != NULL);

	for (e = list_begin (list); e != list_end (list); e = list_next (e))
		if (less (elem, e, aux))
			break;
	return list_insert (e, elem);
}

• 특이하게 함수 포인터 list_less_func *less를 받는다는 점이 중요.

typedef bool list_less_func (const struct list_elem *a,
                             const struct list_elem *b,
                             void *aux);

• 쉽게 말하자면, less에는 함수명을 넣어야 함
  • 해당 함수는 매개변수로 struct list_elem*형 포인터 a/b, 그리고 부가 매개변수인 aux를 받음

for (e = list_begin (list); e != list_end (list); e = list_next (e))
		if (less (elem, e, aux))
			break;

• 위 반복문에서는, 리스트에 삽입할 노드인 elem과, 현재 리스트의 원소인 e가 list_less_func의 a, b에 대입됨
• 만약 list_less_func의 반환값이 참(1)인 경우, 반복문을 종료
• 여기서 우리는, 각 쓰레드의 wakeup_tick의 오름차순으로 정렬하고 싶음

/* 리스트 정렬 용도. 두 노드 -> 쓰레드의 priority를 비교. */
// 오름차순 정렬시
bool asc_ticks (const struct list_elem *x, const struct list_elem *y, const void *aux){
	struct thread *tx = list_entry(x, struct thread, elem);
	struct thread *ty = list_entry(y, struct thread, elem);
	return (tx -> wakeup_tick) < (ty -> wakeup_tick);
}

• 이렇게 asc_ticks 함수를 정의하면, 삽입할 노드 elem의 wakeup_tick이 현재 리스트의 원소 e의 wakeup_tick보다 작을 때 반복문이 멈추고, 삽입이 이루어짐
  • 즉 오름차순 삽입이 이루어진다는 뜻.

priority scheduling

thread.*

• ★★[구현 2-1]★★ ready_list의 각 쓰레드는 priority 내림차순으로 정렬되어 있어야 함. 즉 삽입될 때 순서에 맞게 넣기.
  • 요주의 함수: thread_unblock, thread_yield
  • ready_list에 새로운 쓰레드를 넣을 때마다, list_insert_ordered 사용할 것.

list_insert_ordered(&ready_list, &curr->elem, dsc_priority, NULL)

static bool dsc_priority (const struct list_elem *x, const struct list_elem *y, const void *aux){
	struct thread *tx = list_entry(x, struct thread, elem);
	struct thread *ty = list_entry(y, struct thread, elem);
	return (tx -> priority) > (ty -> priority);
}

• >= 말고 >를 사용해야, 우선순위가 동일한 쓰레드가 존재하는 경우 맨 뒤에 삽입됨.

  • 이렇게 해야 동일 우선순위일 때 round robin 식으로 동일하게 순서가 돌아감. 이거 확인하는 테스트 케이스 있다 (priority-fifo)

• [구현 2-2] preemption(선점) 구현

  • 요주의 함수: thread_create 내 thread_unblock 호출 이후!
  • 쓰레드를 ready_list에 넣었을 때, 현재 실행 중인 쓰레드보다 우선순위가 높은 경우, 새로운 쓰레드로 문맥을 전환
    • 우선순위 역순으로 정렬되어 있으니, list_front로 맨 앞 노드만 확인하면 될 것.
  • 그러니까 그걸 비교해야겠지. thread_get_priority 사용할 것.
    • 비교 시점은 ready_list에 삽입된 이후여야 함. 비교 후 조건이 참이면 thread_yield를 호출하자.

• [구현 2-3] priority 재설정

  • 요주의 함수: thread_set_priority

• 현재 쓰레드의 우선순위를 낮추는 경우, ready_list에 있는 다른 쓰레드의 우선순위가 높아질 수 있음.

  • 이 경우 해당 쓰레드에게 yield해줘야 하는데, list_front로 연결리스트 맨 앞 노드 priority 확인하고 비교하면 됨. 구현 2-2에서 했던 거랑 비슷.
  • 단 연결 리스트가 비어 있는 경우엔 list_front 사용하면 안 됨. list_empty로 예외 처리하던가 하자.

synch.h

• [구현 2-4] struct semaphore의 멤버 struct waiters의 각 쓰레드는 priority 내림차순으로 정렬되어 있어야 함.

  • 요주의 함수: sema_down
  • waiters에 새로운 쓰레드를 넣을 때마다, list_insert_ordered 사용할 것.

• [구현 2-5] 락이 풀릴 때 현재 쓰레드보다 더 높은 priority의 쓰레드를 깨우는 경우 yield할 것.

  • 요주의 함수: sema_up
  • 현재 쓰레드의 priority보다, thread_unblock으로 추가된 쓰레드의 priority가 큰 경우 thread_yield를 호출하자.
  • 원래 쓰레드의 sema -> value--;는 아직 실행되지 않았음.
    • 따라서 sema -> value++;로 높인 다음에, thread_yield를 시도해야 했음.

• ★★[구현 2-6]★★ struct condition의 멤버 struct waiters의 각 쓰레드는 priority 내림차순으로 정렬되어 있어야 함.

  • 요주의 함수: cond_wait
  • 문제는... 여기의 waiters 연결 리스트는 struct thread의 elem 멤버를 원소로 받지 않음.
  • 대신 struct semaphore_elem의 elem 멤버만 넣을 수 있음. 그런데 이 구조체엔 priority가 기본적으로 없음.
  • struct semaphore_elem에 별도로 priority를 멤버로 추가해고, 거기에다 현재 쓰레드의 priority를 저장한 뒤, 이걸 기준으로 정렬해야 함.
  • 일단 cond_signal은 수정해줄 필요가 없었음. sema_up을 호출하는 건데 그건 이미 [구현 2-4]에서 처리했으니?

// synch.c
void
cond_wait (struct condition *cond, struct lock *lock) {
	// [구현 2-6] Priority 내림차순으로, 올바른 위치에 삽입

    // 여기에 priority를 추가해야 하더라.
    struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
	int priority;						// 정렬 용도 priority.
    };


	// cond_signal이 해당 condition으로 시그널을 보낼 때까지 대기해야 한다.
	// waiters 리스트에 대기할 waiter는 struct semaphore_elem 형으로 정의
	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);
	waiter.priority = thread_get_priority();

    // cond의 waiters 리스트(&cond -> waiters)에 지금 쓰레드 (&waiter.elem)를 넣는다. priority의 역순으로 넣는다.
	list_insert_ordered (&cond->waiters, &waiter.elem, dsc_sema_priority, NULL);
	lock_release (lock);  // 기존 모니터 락이 임시 해제
	sema_down (&waiter.semaphore);  // signal 올때까지 wait
	lock_acquire (lock);  // wait이 풀림
}

/* priority의 내림차순으로 정렬할 시 사용되는 함수. */
bool dsc_sema_priority (const struct list_elem *x, const struct list_elem *y, const void *aux){
	struct semaphore_elem *tx = list_entry(x, struct semaphore_elem, elem);
	struct semaphore_elem *ty = list_entry(y, struct semaphore_elem, elem);
	return (tx -> priority) > (ty -> priority);
}