오늘 하루 요약

지금 내 상태...

✏️ 오늘의 한 일

• PintOS Lab : Priority Scheduling -> Ready list 우선순위에 따른 정렬

🌈오늘의 성장!

Priority Scheduling

일단 Ready List를 우선순위에 따라서 정렬하는 것 부터 하기로 했다.
따라서 Ready Status와 관련 있는 저 3개의 함수를 수정해야했다.(노랑 형광펜 친 함수들)

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))// -> cmp_priority
			break;
	return list_insert(e, elem);
}

cmp_priority

• list_less_func 프로토타입

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

리스트의 a 요소와 b 요소를 비교하는 기능을 수행
우리는 Prority가 더 큰 값이 리스트의 head 에 오기를 바란다.
따라서 새롭게 넣고자 하는 스레드의 우선순위(elem) 이 기존 리스트에 있던 요소 스레드의 우선순위(e)보다 크다면, 그 앞에 집어넣으면 정렬이 된다.

// l -> elem, s -> e
bool cmp_priority(struct list_elem *l, struct list_elem *s, void *aux UNUSED)
{
	struct thread * elem = list_entry(l, struct thread, elem);
	struct thread * e = list_entry(s, struct thread, elem);

	return elem->priority > e->priority;
}

thread_create()

새로 만드는 스레드의 우선순위와, 현재 실행중(CPU를 가진) 스레드의 우선순위를 비교
만약 새로 만드는 스레드의 우선순위가 더 크다면, CPU를 양보하도록 한다.

tid_t thread_create(const char *name, int priority,
										thread_func *function, void *aux)
{
	struct thread *t; // 새로운 스레드
	tid_t tid;				// 스레드 ID
    
    ...

	int curr_priority = thread_get_priority(); // 현재 running 중인 스레드의 우선순위

	thread_unblock(t);

	if (!list_empty(&ready_list) && t->priority > curr_priority)
	{
		thread_yield(); // 현재 CPU 점유중이던 스레드, CPU 자원 양보
	}

	return tid;
}

thread_yield

만약 위 상황처럼 현재 CPU를 점유중이던 스레드가 나가리가 되면,
다시 Ready Queue로 돌아가야한다.
이때 역시 우선순위 순서대로 들어가야 하기 때문에
앞에서 구현했던 list_insert_ordered를 활용해서넣어준다.

void thread_yield(void)
{
	struct thread *curr = thread_current();
	enum intr_level old_level;

	ASSERT(!intr_context());

	old_level = intr_disable();
	if (curr != idle_thread)
		// ready list에 정렬된 상태로 push
		list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);
	do_schedule(THREAD_READY);
	intr_set_level(old_level);
}

thread_unblock

BLOCK => READY 로 상태가 바뀌면 역시나 Ready Queue로 들어가야한다.
그말은 즉 우선순위 대로 정렬해서 들어가야한다~

void thread_unblock(struct thread *t) // wakeup 역할?
{
	enum intr_level old_level;

	ASSERT(is_thread(t));

	old_level = intr_disable();
	ASSERT(t->status == THREAD_BLOCKED); // Block이 아니면 ASSERT
	// list_push_back(&ready_list, &t->elem); // Ready list tail로 인자로 받은 thread push
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
	t->status = THREAD_READY;	 // BLOCK -> READY
	intr_set_level(old_level); // disabled 되었던 인터럽트 다시 abled
}

🚨 Trouble Shooting

끝난줄 알았다...
근데... priority-change를 테스트를 돌려보니 이따구로 에러를 뱉더라...

backtrace 0x800421347d 0x80042089f4 0x8004208da6 0x8004213c90 0x8004213d38 0x8004209b2c 
0x8004209fed 0x8004218eff 0x8004207417.
0x000000800421347d: debug_panic (lib/kernel/debug.c:32)
0x00000080042089f4: intr_handler (threads/interrupt.c:365)
0x0000008004208da6: intr_entry (threads/intr-stubs.o:?)
0x0000008004213c90: list_remove (lib/kernel/list.c:254)
0x0000008004213d38: list_pop_front (lib/kernel/list.c:267)
0x0000008004209b2c: sema_up (threads/synch.c:113)
0x0000008004209fed: lock_release (threads/synch.c:227)
0x0000008004218eff: simple_thread_func (tests/threads/priority-fifo.c:97 (discriminator 3))
Traceback (most recent call last):
  File "/workspaces/pintos_lab_docker/pintos-kaist/utils/backtrace", line 42, in <module>
    main(sys.argv)
  File "/workspaces/pintos_lab_docker/pintos-kaist/utils/backtrace", line 37, in main
    resolve_loc(argv[1:])
  File "/workspaces/pintos_lab_docker/pintos-kaist/utils/backtrace", line 31, in resolve_loc
    int(addrs[int(idx/2)], 16), fname, path))
ValueError: invalid literal for int() with base 16: '0x8004207417.'

이게 TDD...?

• TEST CASE : priority-change.c
  여기서 건드는 함수는 딱 두개다 thread_create 와 thread_set_priority

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

  msg ("Creating a high-priority thread 2.");
  thread_create ("thread 2", PRI_DEFAULT + 1, changing_thread, NULL);
  msg ("Thread 2 should have just lowered its priority.");
  thread_set_priority (PRI_DEFAULT - 2);
  msg ("Thread 2 should have just exited.");
}

static void
changing_thread (void *aux UNUSED) 
{
  msg ("Thread 2 now lowering priority.");
  thread_set_priority (PRI_DEFAULT - 1);
  msg ("Thread 2 exiting.");
}

근데 thread_create 이걸 봤는데 아무리 생각해도 내가 생각한 로직이 맞았다.
슬라이드와 깃북에서 이야기하는 요구사항들을 다 이행했음에도 에러가 난게 이해가 안갔다.

그때 테스트 코드를 다시 보니 thread_set_priority 얘가 있네?

• 기존 코드

void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	// list_sort...?
	list_sort(&ready_list, cmp_priority, NULL);
	
}

처음엔 우선순위를 새로 받았으니까 역시나 Ready 큐를 정렬하면 되겠구나 생각했다.
그리고 리스트 정렬 메서드를 줘서 개꿀~ 하면서 정렬만 해놨다.

원인

자 여기서 우린 빼먹은게 있다.
현재 실행중인 스레드가 새로운 우선순위를 받아서 준비 큐를 정렬했다.

그렇다면 정렬 전 준비 큐에서 가장 우선순위가 높아서 CPU를 점유했는데
그 준비 큐가 정렬되어서 순서가 바뀌었다면?

그럼 head에 현재 CPU 점유중인 스레드보다 더 우선순위가 높은 스레드가 위치할 수도 있다.
이 경우, 비교를 해서 현재 Running 중인 스레드가 CPU를 양보해 주어야 한다.

해결

void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	// list_sort...?
	list_sort(&ready_list, cmp_priority, NULL);
	if (!list_empty(&ready_list) && list_entry(list_begin(&ready_list), struct thread, elem)->priority > new_priority)
	{
		thread_yield(); // 현재 CPU 점유중이던 스레드, CPU 자원 양보
	}
}

끝.

priority에서 3개가 추가로 PASS... 이제 LOCK 걸러 가자

⛏ 오늘의 삽질

오늘 매순간이 삽질...
gdb 도 찍고 backtrace 도 하고~