[운영체제] pintOS 프로젝트 - Priority Scheduling

안녕하세요 레몬입니다.

지난 번 작성한 pintOS 프로젝트 첫 번째 Alarm Clock에 이어, Priority Scheduling 구현에 대해 써보려 한다.

운영체제 과목과 관련한 잡소리는 지난 글에 충분히 써놨으니 바로 본론으로 들어가보자

pintOS 프로젝트 - Alarm Clock (Sleep-Wakeup 구현하기)

[운영체제] pintOS 프로젝트 - Alarm Clock (Sleep-Wakeup 구현하기)

---

1. 과제 개요

Pintos는 새로운 thread가 ready_list에 삽입되어도 우선순위를 고려하지 않고 리스트 마지막에 삽입한다. 이를 수정하여 각 thread의 우선순위를 고려해 우선순위가 높은 thread가 리스트 앞에 삽입되어 먼저 수행될 수 있도록 수정한다.

2. 아이디어

기존 Pintos에서는 모든 thread가 단순히 ready_list의 맨 뒤에 삽입된다. 각 thread에 0~63의 값을 가지는 PRI(우선순위) 값을 추가하여 ready_list를 우선순위에 따라 정렬한다. 또 현재 CPU를 점유하고있는 thread보다 높은 우선순위를 가진 thread가 CPU를 선점할 수 있도록 한다.

코드를 보기 전에, 구현해야할 기능과 아이디어를 간략히 살펴보자

지난 포스팅에서도 사용된 Thread의 일생을 나타낸 그림이다.

이미 알고있듯 CPU는 여러 Thread를 번갈아가며 수행한다.

그래서 모든 Thread는 Ready List에 들어가 자신의 순서가 오길 기다리는데, 기존 pintOS는 단순히 새로 들어온 Thread를 줄의 맨 뒤에 세우고, 먼저 온 순서대로 처리하는 FCFS(First Come First Served) 방식으로 줄을 세운다.

하지만 Thread들 중 실시간으로 사용자와 Input/Output을 주고받아야 하거나 중요한 처리를 해야하는 경우 등 처리의 우선순위가 높은 것들이 있기 마련이다.

이를 위해 Thread들을 Priority의 순서대로 줄을 세워 처리해줘야할 필요성이 있고, 이 기능을 구현하려면 Thread들을 Ready List에 넣기 전 Priority를 비교하여 줄을 세워 넣어주면 될 것이다.

여기에 더해, CPU가 다른 Thread를 처리하고 있는 와중에 그보다 더 높은 Priority를 가진 Thread가 Ready List에 들어오면, 지금 연산중이던 Thread를 멈추고 Priority가 높은 Thread를 먼저 처리하는 기능도 구현할 것이다.

 

3. 설계 (코드!!)

-구현할 함수 선언

현재 수행중인 thread와 ready_list 안에 있는 thread의 우선순위를 비교할 수 있도록 작성할 함수를 헤더에 선언한다.

- thread_create() 함수 수정

생성된 스레드 t의 우선순위와 현재 실행중인 스레드 thread_current()의 우선순위를 비교하여, t의 우선순위가 더 클 때 thread_yield() 함수를 실행해 CPU를 양보한다.

- thread_unblock() 함수 수정

thread가 unblock될 때 기존 ready_list의 맨 끝에 thread를 추가하는 list_push_back 코드 대신 list_insert_ordered 로 수정하여 priority에 따라 정렬되어 ready_list에 삽입되도록 하였다.

- thread_yield() 함수 수정

현재 수행중인 thread가 CPU를 양보할 때에도 마찬가지로 list_insert_ordered로 수정하여 우선순위에 따라 정렬되어 삽입되도록 하였다. 이 때 사용한 cmp_priority 함수는 ready_list의 우선순위가 높으면 1을, cur->elem의 우선순위가 높으면 0을 반환하도록 작성하였다.

- thread_set_priority() 함수 수정

기존 단순히 새로운 priority 값을 thread에 쓰는 방식을 수정하여, priority가 조정되는 mlfqs가 발생할 때 현재 priority 값을 새로 받은 new_priority로 변경하고, 이 때 만약 현재 CPU에서 수행중인 thread의 priority가 낮아졌다면 ready_list의 thread들과 우선순위를 비교할 수 있도록 test_max_priority() 함수를 호출한다.

- test_max_priority() 함수 추가

cp는 현재 cpu에서 수행중인 thread이고, first_thread는 ready_list의 맨 앞에 있는 thread로, 앞서 ready_list 삽입 방식을 priority 값에 따라 정렬하여 넣는 것으로 수정했으니 first_thread가 곧 ready_list의 모든 thread중 가장 높은 우선순위를 가진 thread이다. cp와 first_thread를 비교하여 first_thread의 우선순위가 더 높다면 CPU를 양보하는 thread_yield() 함수를 호출한다.

- cmp_priority() 함수 추가

두 thread를 받아 각각의 priority를 비교하는 cmp_priority 함수를 추가하였다. list_insert_ordered 함수에 사용된다. a의 우선순위가 높으면 1을, b의 우선순위가 높으면 0을 리턴한다.

 

4. 결과

make check 명령어를 입력해 test를 진행중인 모습이다.

세가지 테스트에서 pass한 결과를 확인하였다.

---

이걸로 우리 학교 운영체제 과목의 두 번째 핀토스 과제였던 Priority Scheduling은 끝이다.

지금 포스팅하면서 다시 보니 엄청 복잡하진 않은데 그때는 왜그렇게 어려웠는지... 사실 코드보다도 핀토스 환경 설치하고 자잘한 디버깅하는게 더 오래걸린 것 같다

앞으로 남은 과제는 Synchronization, Priority Inversion Problem 두 가지다!!