-
Project1 : Thread - Priority Scheduling (1)OS/Pintos 2021. 12. 30. 11:07
개념
Priority Scheduling (우선순위 스케쥴링) : 우선순위가 제일 높은 CPU에게 주겠다
✅ 스레드가 현재 실행 중인 쓰레드보다 우선순위가 높은 준비 목록에 추가되면 현재 스레드는 즉시 프로세서를 새 스레드에 넘겨야 한다.
✅ 마찬가지로 스레드가 lock, semaphore 또는 condition 변수를 기다릴 때 가장 높은 우선순위를 가진 기다리던 스레드가 먼저 활성화되어야 한다.
스레드는 언제든지 자신의 우선순위를 올리거나 낮출 수 있지만, 더 이상 높은 우선순위를 갖지 않도록 우선 순위를 낮추면 CPU를 즉시 양보한다.
스레드의 우선순위 범위는 PRI_MIN(0)부터 PRI_MAX(63)까지이다.
낮은 숫자는 낮은 우선순위! 숫자가 높을수록 우선순위가 높은것!
초기 스레드의 우선순위는 thread_create()의 인수로 전달된다.
우선순위의 변동이 필요없는 스레드라면 PRI_DEFAULT(31)을 사용하면 된다.
과제 목표
Implement priority scheduling and priority donation in Pintos.
현재 핀토스에서 스레드를 우선순위에 상관없이 실행하고 있다. (라운드로빈으로 구현되어 있음)
이 과제의 목표는 우선순위 순서대로 스레드가 실행되도록 하는 것이다.
🚨 고려사항
- 우선순위 반전 문제 고려A라는 자원 존재 가정해결방법즉, 필요한 자원이 lock되어 있다면, H가 자신의 우선순위를 L에게 기부하여 L이 모두 돌게하여, A라는 자원을 반납 후에 H의 우선순위를 다시 회복한다면 우선순위 반전이 발생하지 않을것이다.
- 하지만, Priority Donation과 동시에 Multiple Donations와 Nested Donation 또한 함께 고려하여야 한다. (Priority Scheduling (3)에서 다룰 예정)
- Priority Donation으로 해결할 수 있다.
- L이 현재 A라는 자원을 사용하여 Running 중 → H들어옴 → L이 H에게 CPU양보함 (⭐️ A자원은 L이 그대로 가지고 있음) → 현재 ready_queue에는 M이 있음 → H에게 CPU가 가도 자원이 없으니 H는 절대로 CPU를 얻을 수 없다. 즉, 우선순위가 낮은 M이 돌것(우선순위 반전 발생!!!)
- 우선순위 반전 : H, M, L 각 우선순위를 가진 스레드가 있다고 가정,(우선순위 H > M > L)
- 우선순위 매크로는 thread/thread.h에 정의되어 있으나 그 값을 변경하면 안 된다.
Solution(1)
아이디어
💡 스레드가 자신의 우선순위를 점검 수정하는 함수를 보자!
void thread_set_priority (int new_priority); //Sets the current thread's priority to new priority. //현재 스레드의 우선순위를 새 우선순위로 설정한다. int thread_get_priority (void); 현재 스레드의 우선순위를 반환한다. Returns the current thread's priority.💡 현재 Pintos 스케쥴러가 어떻게 구현되어있지?
- Pintos는 리스트를 이용하여 스레드를 관리 함
- 새로운 스레드를 ready_list에 어떤 방식으로 집어넣지?
✅ thread_unblock(), thread_yield()함수 확인해봐야겠다! → 특별히 우선순위를 고려하지 않고 ready_list 맨 마지막에 스레드를 삽입하는 것을 알 수 있다.
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ 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); } 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); }ready_list에서 스레드를 꺼내는 과정을 확인! (현재 CPU를 점유하고 있는 스레드가 CPU를 양보했다는 의미!)
thread_exit(), thread_yield(), thread_block()함수를 통해 이루어짐. → 모두 schedule()함수 호출함!!
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ void thread_exit (void) { ASSERT (!intr_context ()); #ifdef USERPROG process_exit (); #endif /* Just set our status to dying and schedule another process. We will be destroyed during the call to schedule_tail(). */ intr_disable (); do_schedule (THREAD_DYING); // <- 결국 schedule( ) 함수 호출 NOT_REACHED (); } 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); // <- 결국 schedule( ) 함수 호출 intr_set_level (old_level); } static void do_schedule(int status) { ASSERT (intr_get_level () == INTR_OFF); ASSERT (thread_current()->status == THREAD_RUNNING); while (!list_empty (&destruction_req)) { struct thread *victim = list_entry (list_pop_front (&destruction_req), struct thread, elem); palloc_free_page(victim); } thread_current ()->status = status; schedule (); } void thread_block (void) { ASSERT (!intr_context ()); ASSERT (intr_get_level () == INTR_OFF); thread_current ()->status = THREAD_BLOCKED; schedule (); }schedule()함수 주요 목적 : 현재 CPU를 점유중인 스레드와 다음에 실행될 스레드의 상태를 바꾸는 것.
다음 실행될 스레드는 next_thread_to_run()함수에 의해 결정되며, 이 스레드는 ready_list 안의 첫번째 스레드이다.
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ static struct thread * next_thread_to_run (void) { if (list_empty (&ready_list)) return idle_thread; else return list_entry (list_pop_front (&ready_list), struct thread, elem); // <- ready_list 맨 앞의 스레드 반환 } static void schedule (void) { struct thread *curr = running_thread (); struct thread *next = next_thread_to_run (); ASSERT (intr_get_level () == INTR_OFF); ASSERT (curr->status != THREAD_RUNNING); ASSERT (is_thread (next)); /* Mark us as running. */ next->status = THREAD_RUNNING; // <- 상태 변경 /* Start new time slice. */ thread_ticks = 0; #ifdef USERPROG /* Activate the new address space. */ process_activate (next); #endif if (curr != next) { /* If the thread we switched from is dying, destroy its struct thread. This must happen late so that thread_exit() doesn't pull out the rug under itself. We just queuing the page free reqeust here because the page is currently used bye the stack. The real destruction logic will be called at the beginning of the schedule(). */ if (curr && curr->status == THREAD_DYING && curr != initial_thread) { ASSERT (curr != next); list_push_back (&destruction_req, &curr->elem); } /* Before switching the thread, we first save the information * of current running. */ thread_launch (next); } }구현
STEP1 : ready_list에 스레드를 삽입할 때 우선순위가 정렬되도록 삽입 하도록 수정해서 해결가능함.
- 우선순위 정렬 방법에는 두가지가 있다 : Ready list에 push할 때 or push를 다 넣어놓고 뽑을 때 우선순위
- thread_yeild / thread_unblock
STEP2 : 선점의 우선순위 문제 고려
- Ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인 thread의 우선순위보다 높으면, 기존 thread를 밀어내고 CPU를 점유하도록 한다.
- running을 하고 있는 trhead의 우선순위를 비교하는 순간
- running을 하고 있는 thread를 제외한 ready_list 중 우선순위 높은 thread들어오면 선점 (ready_list는 정렬되어있다는 가정과 지금 running에 돌고 있는 현재는 최우선순이다 라는 가정하에!)
- 새로운 thread의 우선순위가 현재 실행중인 thread의 우선순위보다 높으면, 새로운 thread가 실행중인 thread를 선점 : thread_create
- 특정 스레드들의 priority를 다시 set해주는 함수 : thread_set_priority
세부 구현
STEP1
list_insert_ordered() 함수 이용 (구현되어있는 함수 수정)
/* list.c */ 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)) //emlm(새로운 요소element) < e(기존요소)이면 True, elem >= e면 False break; return list_insert (e, elem); //e의 앞에 elem이 사입된다. } //정렬하여 리스트에 insert하는 함수 void list_insert (struct list_elem *before, struct list_elem *elem) { ASSERT (is_interior (before) || is_tail (before)); ASSERT (elem != NULL); elem->prev = before->prev; elem->next = before; before->prev->next = elem; before->prev = elem; }list_insert_ordered( ) 함수의 인자 : 스레드를 넣을 리스트 / 넣고자 하는 스레드 /삽입시 기준이 될 함수
해당 함수의 내부를 살펴보면 list_insert( ) 함수를 호출하는 것을 알 수 있다.
그리고 list_insert( ) 함수의 결과, 두 번째 인자에 해당하는 스레드가첫 번째 인자에 해당하는 스레드 앞에 위치하게 된다.
그런데 앞서 ready_list는 우선순위가 높은 순으로 정렬되어 있어야 한다고 하였다.
list_insert_ordered( ) 함수 내부의 less( ) 함수는 아래와 같이 elem > e 일 때 true를 반환하는 함수여야 한다.
따라서, 우선순위를 비교해줄 함수 (thread_compare_priority) 생성 필요!
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) { return list_entry (l, struct thread, elem)->priority > list_entry (s, struct thread, elem)->priority; }이제! 이 내용을 바탕으로, ready_list에 스레드를 삽입하는 과정을 수정하고자 한다.
아래 thread_yield( ) 함수와, thread_unblock( ) 함수 코드에서 list_push_back( ) 함수를 주석 처리하였다.
그리고 새롭게 list_insert_orered( ) 함수를 넣어주었다.
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ 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); list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0); do_schedule (THREAD_READY); intr_set_level (old_level); } 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); list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0); t->status = THREAD_READY; intr_set_level (old_level); }STEP2
새롭게 ready_list에 삽입된 스레드의 우선순위가 현재 CPU를 점유하고 있는 스레드의 우선순위보다 높다면 CPU 점유를 넘겨야 한다.
이를 위해 ready_list의 맨 앞 스레드의 우선순위와 현재 CPU를 점유하고 있는 스레드의 우선순위를 비교하는 함수를 만들었다.
그리고 이를 thread_create( )와 thread_set_priority( ) 함수에 추가해주었다.
/* threads/thread.c */ /* PROJECT1: THREADS - Priority Scheduling */ void thread_test_preemption (void){ if (!list_empty (&ready_list) && thread_current ()->priority < list_entry (list_front (&ready_list), struct thread, elem)->priority) thread_yield (); } 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); thread_test_preemption(); return tid; } void thread_set_priority (int new_priority) { thread_current ()->priority = new_priority; thread_test_preemption(); }마지막으로!
thread.h에 새롭게 생성된 함수 추가
지금까지의 과정을 통해 우선순위가 가장 높은 스레드가 CPU를 점유할 수 있게 되었다.
터미널의 다음과 같이 입력하면 결과를 확인할 수 있다.
~/pintos-kaist-team06$ source ./activate
~/pintos-kaist-team06$ cd threads
~/pintos-kaist-team06$ make check
참고
'OS > Pintos' 카테고리의 다른 글
Project2: User Programs(introduction) (0) 2022.01.10 Project1 : Thread - Priority Scheduling(3) (0) 2021.12.30 Project1 : Thread - Priority Scheduling(2) (0) 2021.12.30 Project1 : Thread - introduction (0) 2021.12.30 Project1. Alarm clock (0) 2021.12.28