🌸🌸🌸블로그 글은 복습 겸 gitbook의 순서에 따라 번역 및 관련 내용에 JK피셜을 달아 정리할 예정이다. 말그대로 JK피셜인 칸큼 100%맞는 말은 아닐 수 있다는 거 참고해주길 바란다.
📖 Gitbook 내용 📖
Priority Scheduling
Pintos에서 우선순위 스케줄링과 우선순위 기부(priority donation)를 구현해야 합니다.
만약 현재 실행중인 스레드보다 우선순위가 높은 스레드가 준비 리스트에 추가되면, 현재 스레드는 바로 CPU를 양보해야 합니다. 마찬가지로, 락, 세마포어, 조건 변수를 기다리는 스레드들이 있을 때는 가장 높은 우선순위를 가진 대기 중인 스레드가 먼저 깨어나야 합니다. 스레드는 언제든지 자신의 우선순위를 변경할 수 있지만, 자신보다 우선순위가 높지 않은 상태로 우선순위를 낮추면 즉시 CPU를 양보해야 합니다.
스레드 우선순위는 PRIMIN (0)부터 PRI_MAX (63)까지의 범위를 가집니다. 낮은 숫자는 낮은 우선순위를 나타내며, 우선순위 0은 가장 낮은 우선순위이고 우선순위 63은 가장 높은 우선순위입니다. 초기 스레드 우선순위는 thread_create()에 인자로 전달됩니다. 다른 우선순위를 선택할 이유가 없다면 PRI_DEFAULT (31)을 사용하면 됩니다. PRI 매크로는 threads/thread.h에 정의되어 있으며, 이 값을 변경해서는 안 됩니다.
우선순위 스케줄링의 한 문제는 "우선순위 역전"입니다. 고우선순위(High), 중간우선순위(Medium), 저우선순위(Low) 스레드 H, M, L을 고려해봅시다. 만약 H가 L(예를 들어, L이 소유한 락을 기다리는 경우)를 기다려야 한다면, 그리고 준비 목록에 M이 있다면, 낮은 우선순위 스레드가 CPU 시간을 받지 않기 때문에 H는 CPU를 절대로 얻지 못할 것입니다. 이 문제를 해결하기 위한 부분적인 방법은 H가 L이 락을 소유하는 동안에만 우선순위를 L에게 "기부"하는 것이며, L이 락을 해제하면 (따라서 H가 락을 얻게 되면) 기부를 취소하는 것입니다.
우선순위 기부를 구현하세요. 우선순위 기부가 필요한 모든 다양한 상황을 고려해야 합니다. 하나의 스레드에 여러 개의 우선순위가 기부되는 경우를 처리할 수 있어야 합니다. 또한 중첩된 기부를 처리해야 합니다: 만약 H가 M이 소유한 락을 기다리고, M이 L이 소유한 락을 기다리는 경우, M과 L 모두 H의 우선순위로 상승되어야 합니다. 필요한 경우, 중첩된 우선순위 기부의 깊이를 합리적인 제한(예: 8단계)으로 설정할 수 있습니다.
락에 대한 우선순위 기부를 구현해야 합니다. 다른 Pintos 동기화 구조물에 대한 우선순위 기부는 구현할 필요가 없습니다. 그러나 모든 경우에 대해 우선순위 스케줄링을 구현해야 합니다.
마지막으로, 스레드가 자체 우선순위를 확인하고 수정할 수 있는 다음 함수들을 구현해야 합니다. 이러한 함수에 대한 구조체는 threads/thread.c에서 제공됩니다.
void thread_set_priority (int new_priority);현재 스레드의 우선순위를 새로운 우선순위로 설정합니다. 만약 현재 스레드가 더 이상 최고 우선순위를 가지지 않는다면, 양보합니다.
int thread_get_priority (void);현재 스레드의 우선순위를 반환합니다. 우선순위 기부가 있는 경우, 더 높은 (기부된) 우선순위를 반환합니다.
다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다.
우선순위 스케줄러는 이후 프로젝트에서는 사용되지 않습니다.
💯 이론 공부 💯
Round Robin Scheduling, RR
default PintOS의 thread 스케줄러는 '라운드 로빈'으로 구현되어 있다.
라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.
보통 시간 단위는 10 ms ~ 100 ms 정도이다. 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.
정적 스케줄링과 동적 스케줄링
- 정적 스케줄링(Static Scheduling) : 프로세스에 부여된 우선순위가 바뀌지 않는다. 고정우선순위 스케줄링이라고도 한다.
- 동적 스케줄링(Dynamic Scheduling): 스케줄링 과정에서 프로세스의 우선순위를 변동시킨다. 유동우선순위 스케줄링이라고도 한다.
비선점형과 선점형
스케줄링 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있다. 비선점형은 위의 결정 시점 중 '수행 → 대기'와 '수행 → 종료'의 상황에서만 수행되며, 선점형은 '수행 → 대기', '수행 → 준비', '대기 → 준비', '수행 → 종료'의 모든 상황에서 수행된다.
비선점형 스케줄링(Non-preemptive Scheduling) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다.[1]
선점형 스케줄링(Preemptive Scheduling) : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다. '운영 체제가 프로세서 자원을 선점'하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.[1]
- 비선점 프로세스 스케줄링
- SJF 스케줄링(Shortest Job First Scheduling)
- HRRN 스케줄링(Highest Response Ratio Next Scheduling)
- FCFS 스케줄링(First Come First Served Scheduling)
- 선점 프로세스 스케줄링
- RR 스케줄링(Round Robin Scheduling)
- SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
- 다단계 큐 스케줄링(Multilevel Queue Scheduling)
- 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
- RM 스케줄링(Rate Monotonic Scheduling)
- EDF 스케줄링(Earliest Deadline First Scheduling)
⌨️ 코드 구현 ⌨️
test_max_priority()
priority 함수의 identity와 같은 함수다. 근데 왜 test_max_priority()로 이름지었는지 모르겠다.(직감적이지 않아..kaist, 한양대 교수님들 왜 그러신거죠?)
아무튼 test_max_priority()함수는 현재 실행 중인 스레드의 우선순위보다 높은 우선순위를 가진 스레드가 준비 리스트에 있는 경우에만 현재 스레드를 양보하는 함수다.
우리팀 초안코드 🧐
//include/threads/thread.h
void test_max_priority(void);
//threads/thread.c
void test_max_priority(void){
if (list_empty(&ready_list))
return;
struct thread* max_priority = list_entry(list_front(&ready_list), struct thread, elem);
if (max_priority->priority > thread_current()->priority){
thread_yield();
}
}우리팀은 thread_get_priority()함수를 사용하지 않았다. 로직에는 차이가 없지만, 구현되어 있는 함수들을 좀 더 활용하도록 코드 보는 시야를 넓힐 필요성이 있었다.
또한 예외처리문을 전혀 고려하지 못했는데, ready list가 비어있거나 현재 컨텍스트가 인터럽트 컨텍스트인지 확인하는 절차(intr_context())가 있도록 수정했다.
우리팀 수정 코드 🤓
//include/threads/thread.h
void test_max_priority(void);
//threads/thread.c
void test_max_priority(void)
{
if (list_empty(&ready_list) || intr_context())
{
return;
}
int run_priority = thread_current()->priority;
struct list_elem *e = list_begin(&ready_list);
struct thread *t = list_entry(e, struct thread, elem);
if (t->priority > thread_get_priority())
{
thread_yield();
}
}수정한 코드는 준비 리스트가 비어 있거나 현재 컨텍스트가 인터럽트 컨텍스트인 경우, 함수 실행을 중단하고 반환한다. 이는 스케줄링이 필요하지 않은 상황을 나타낸다.
현재 실행 중인 스레드의 우선순위를 run_priority 변수에 저장한다.
준비 리스트의 첫 번째 요소(list_begin(&ready_list))를 가져와서 해당 스레드를 가리키는 포인터 t를 얻는다. 이때 list_entry 매크로를 사용하여 요소에서 스레드 구조체를 추출한다.
t의 우선순위가 현재 스레드의 우선순위(thread_get_priority())보다 높은지 비교한다.
만약 t의 우선순위가 더 높다면, 현재 스레드는 CPU를 양보하기 위해 thread_yield() 함수를 호출한다. 이를 통해 우선순위가 더 높은 스레드가 실행되도록 스케줄링이 이루어진다.
test_max_priority()에서 쓰이는 thread_yield()함수를 수정해 보자
기존의 thread_yield()함수는 다음과 같다.
//threads/thread.c
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)
list_push_back (&ready_list, &curr->elem);
do_schedule (THREAD_READY);
intr_set_level (old_level);
}기존 코드를 보면 현재 thread를 ready_list의 맨 뒤에 넣어놓고 cpu 점유를 양보한다. 이를 priority에 따라 양보하기 위해서 다음과 같은 함수들은 구현해서 proiority에 따라 양보할 수 있도록 수정하자.
우리팀 코드 🤓
//threads/thread.c
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)
{
list_insert_ordered(&ready_list, &curr->elem, priority_less, NULL);
}
do_schedule(THREAD_READY);
intr_set_level(old_level);
}
thread_yield()에서 쓰이는 priority_less()함수를 구현해 보자.
우리팀 코드 🤓
//include/threads/thread.h
bool priority_less(const struct list_elem *a, const struct list_elem *b,
void *aux UNUSED);
//threads/thread.c
bool priority_less(const struct list_elem *a, const struct list_elem *b,
void *aux UNUSED)
{
struct thread *t_a = list_entry(a, struct thread, elem);
struct thread *t_b = list_entry(b, struct thread, elem);
return (t_a->priority) > (t_b->priority);
}priority_less()함수는 두 개의 리스트 요소(a와 b)와 aux 매개변수를 비교하여 우선순위가 낮은지 판단하는 함수다.
pintOS에는 이중연결리스트 관리에 대한 함수구현이 매우 잘되어있다. include/lib/kernel/list.h 및 lib/kernel/list.c 의 함수들을 잘 쇼핑해서 골라 쓰자!
특히 list_entry()함수는 앞으로도 계속 나오는 유용한 함수인데, list_elem이 포함된 객체의 구조체로 타고 올라갈 수 있는 함수다.
보통 list_elem이 포함되어있는 구조체에 비교대상이 있으므로 거의 외우다시피 쓰게 될 것이다.
해당 함수를 통해 ready_list를 priority에 따라 큰 순으로 정렬하면서 우선순위에 따른 스케줄링을 실현할 수 있도록 해준다.
thread_create() 수정해보자.
thread를 생성하고 ready_list삽입 시, 현재 실행 중인thread와 우선순위를 비교하여 새로생성된 thread의 우선순위가 높다면 thread_yield()를 통해 CPU를 양보할 수 있도록 수정한다.
이 때 앞서 구현한 test_max_priority(void)을 사용하면 된다.
thread_create()의 기존 코드는 다음과 같다.
//threads/thread.c
tid_t thread_create(const char *name, int priority,
thread_func *function, void *aux)
{
struct thread *t;
tid_t tid;
ASSERT(function != NULL);
/* Allocate thread. */
t = palloc_get_page(PAL_ZERO);
if (t == NULL)
return TID_ERROR;
/* Initialize thread. */
init_thread(t, name, priority);
tid = t->tid = allocate_tid();
/* Call the kernel_thread if it scheduled.
* Note) rdi is 1st argument, and rsi is 2nd argument. */
t->tf.rip = (uintptr_t)kernel_thread;
t->tf.R.rdi = (uint64_t)function;
t->tf.R.rsi = (uint64_t)aux;
t->tf.ds = SEL_KDSEG;
t->tf.es = SEL_KDSEG;
t->tf.ss = SEL_KDSEG;
t->tf.cs = SEL_KCSEG;
t->tf.eflags = FLAG_IF;
/* Add to run queue. */
thread_unblock(t);
return tid;
}여기에 test_max_priority()함수를 추가해서 새로 생성된 thread가 priority 정렬에 맞춰 스케줄에 들어 가도록 하고, priority에 따라 스레드가 실행되도록 하자.
우리팀 코드 🤓
//threads/thread.c
tid_t thread_create(const char *name, int priority,
thread_func *function, void *aux)
{
.
.
.
t->tf.ss = SEL_KDSEG;
t->tf.cs = SEL_KCSEG;
t->tf.eflags = FLAG_IF;
/* Add to run queue. */
thread_unblock(t);
/*----------------[project2]-------------------*/
test_max_priority();
/*----------------[project2]-------------------*/
return tid;
}thread_unblock()을 수정해보자.
thread_unblock()는 블록된 스레드 t를 다시 준비 상태로 전환하는 역할을 한다. 스레드가 블록 상태에서 준비 상태로 전환되면, 스케줄러는 해당 스레드를 곧바로 실행할 수 있도록 준비 리스트에 추가한다.
thread_unblock()의 기존함수는 다음과 같다.
//threads/thred.c
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
list_push_back (&ready_list, &t->elem);
t->status = THREAD_READY;
intr_set_level (old_level);
}여기서 스레드가 unblock 될때 우선순위순으로 정렬되어 ready_list에 삽입 되도록 수정한다.
우리팀 코드 🤓
void thread_unblock(struct thread *t)
{
enum intr_level old_level;
ASSERT(is_thread(t));
old_level = intr_disable();
ASSERT(t->status == THREAD_BLOCKED);
/*-------------------------[project 1]-------------------------*/
list_insert_ordered(&ready_list, &t->elem, &priority_less, NULL);
/*-------------------------[project 1]-------------------------*/
t->status = THREAD_READY;
intr_set_level(old_level);
}thread_set_priority()을 수정해보자.
thread_set_priority()는 스레드의 우선순위가 변경되었을 때 우선순위에 따라 선점이 발생하도록 한다.
기존 코드는 다음과 같다.
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
thread_current ()->priority = new_priority;
}우리팀 초안코드 🧐
void thread_set_priority(int new_priority)
{
enum intr_level old_level;
struct thread *cur_t = thread_current();
cur_t->priority = new_priority;
old_level = intr_disable();
if (!is_cur_high())
{
thread_yield();
}
intr_set_level(old_level);
}우리팀은 앞서 정의할 때 많은 예외처리를 놓쳤다는 것이 꽂혀서 인지 이번에는 thread_yield()안에 있는 intr_disable()을 넣어줬는데, thread_yield()가 intr를 하는 함수인데 감싸버렸더니 작동을 안했다ㅎ 생각을 깊게 하자는 교훈을 얻고 다음과 같이 수정했다.
우리팀 수정 코드 🤓
/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
thread_current()->priority = new_priority;
test_max_priority();
}지금 블로그를 쓰면서 복기를 해보니 참, ppt따라가는 것에 급급해서 내가 구현한 함수에 대한 abstaract를 정확히 파악하지 못한 것이 관련한 다음 코드를 구현할 때도 오류를 만드는 원인인 것 같다.
권영진 교수님 특강처럼 문제를 잘 쪼개서 layer를 나누고 abstract를 통해 구조화하는 것이 부족했다. 문제인식을 했으니 성장하자!
