[KAIST PintOS Project 1] 2. priority scheduling

priority scheduling

 

지난 단계에서는 CPU를 정말로 쓸 스레드만 ready_list에 삽입하는 sleep & awake의 구현으로 불필요한 토스를 줄여 기능을 개선했다. 이번 단계의 목표는 수많은 ready 상태의 대기중인 스레드 중 우선도가 높은 순서대로 사용하도록 하는 기능의 구현이다.

간단히 말해 ready_list를 queue에서 priority에 따르는 heap으로 바꾸는 것이 목적이다.

 

 

순서 1 ~ 2

 

스레드간의 우선도를 따지기 위해 각 스레드마다 priority라는 값을 가진다. 기존에 선착순으로 ready_list에 진입하던 구조를 개선하여 이 priority에 따라 ready_list가 정렬되도록 한다면, 항상 ready_list의 first만 취하는 현재의 알고리즘대로 작동하더라도 priority가 높은 스레드가 우선되는 구조를 만들 수 있을 것이다.

라이브러리에는 이를 구현하기 위한 함수 list_insert_ordered(list, e, func)가 구현되어있는데, 이 함수는 삽입하려는 원소 e를 일단 list의 끝에 삽입한다. 이후 e와 e 직전의 원소에 대해 TF함수 func를 실행하여 이의 결과값에 따라 e의 위치를 연쇄적으로 교환하는데, 이는 결과적으로 func를 기준으로 정렬된 인덱스에 e를 위치하게 한다.

따라서 바닥부터 구현할 필요 없이, 두 스레드의 priority를 비교하는 TF함수만 구현하면 될 것이다.

 

이때 함수의 입력은 thread가 아니라 list_elem이므로, 두 list_elem으로부터 각각 thread 구조체를 추출해 둘의 priority를 비교하여 TF를 리턴하는 함수 CMP_priority(a, b)를 구현했고, ready_list에 elem을 삽입하는 모든 함수에서 항상 list_insert_ordered()를 사용하도록 수정함으로써 priority 순으로 정렬된 ready_list를 구현했다.

 

 

순서 3 ~ 5

 

위와 같은 구조를 구현시 새 스레드를 create하거나 thread_current()의 priority 값을 변경(set)시 우선순위에 변동이 있을 것이다. 그리고 그 경우 현재 실행중인 thread_current()는 자기보다 priority가 높은 스레드가 존재한다면 yeild해야 한다. 따라서 thread_create()와 thread_set_priority()에서 이를 확인하는 과정을 추가한다.

 

마지막으로 새로 추가된 함수들을 헤더에 등록함으로써 priority scheduling를 구현했다.

 

 

 

내일 랜덤런치인데 시간이 늦어서 synchronization, donation은 내일 정리해야겠다.