[Pintos 1주차] Day 4-6

Day 4-5

PT면접 준비에 집중했다.

---

Priority Scheduling

현재 실행 중인 thread보다 우선순위가 높은 thread가 ready list에 추가되면, 현재 thread는 즉시 새 thread에게 프로세서를 양보해야 한다. 마찬가지로, thread가 락, 세마포어 또는 조건 변수를 대기하는 경우, 우선순위가 가장 높은 대기 thread가 먼저 깨어나야 한다. thread는 언제든지 자신의 우선순위를 높이거나 낮출 수 있지만, 우선순위를 낮춰 더 이상 가장 높은 우선순위를 갖지 않게 되면 즉시 CPU를 양보해야 한다.

 

Thread의 우선순위 범위는 PRI_MIN(0)부터 PRI_MAX(63)까지이다. 63이 가장 높은 우선순위, 0이 가장 낮은 우선순위를 가진다. 초기 thread 우선순위는 thread_create()에서 (특별한 이유가 없다면) PRI_DEFAULT(31)로 설정된다.

 

우선순위 스케줄링의 한 가지 이슈는 우선순위 역전이다. H가 L을 기다려야 하고(L에 락이 걸려있다면), M이 ready list에 있다면, 낮은 우선순위 thread가 어떤 CPU 시간도 얻지 못할 것이기 때문에 H는 CPU를 얻지 못할 것이다. 이러한 문제에 대해, H를 위한 부분적인 해결책은 L이 락을 가지고 있을 때 L에게 우선순위를 기부하고, L이 락을 release하면 (그리고 H가 acquire하면) 기부를 회수한다.

---

🔹 Main goal: 현재의 pintos를 FIFO 스케줄링을 사용하고 있고, 이것을 우선순위 스케줄링으로 수정해야 한다.

• ready list를 thread 우선순위를 기준으로 정렬
• 동기화 프리미티브(세마포어, 조건변수)를 위해 wait list를 정렬
• 선점 구현
• 선점 포인트: thread가 ready list에 넣어졌을 때 (timer 인터럽트가 호출될 때마다는 아님)

🔹 고려 사항

• Ready list에서 실행할 thread를 선택할 때, 가장 높은 우선 순위를 가진 것을 선택해야 한다.
• 선점Preemption
  • ready list에 새로운 thread를 삽입할 때, 실행 중인 thread와 우선순위를 비교한다.
  • 새로 삽입된 thread가 현재 실행중인 thread보다 우선순위가 더 높을 때, 그 새로운 thread를 스케줄한다.
• 락: 세마포어, 조건 변수
  • lock을 기다리는 threads의 집합에서 하나의 thread를 선택할 때, 가장 높은 우선순위를 가진 것을 선택한다.

🔹 Pintos에서의 우선순위

• 범위 : PRI_MIN(=0) ~ PRI_MAX(=63)
  • 숫자가 높을수록 더 높은 우선순위를 가짐
  • 기본값은 PRI_DEFAULT(=31)
• PintOS는 thread_create()에 의해 스레드가 생성될 때 초기 우선순위를 설정한다.
• 관련 함수

void thread_set_priority(int new_prioirty) // Change priority of the current thread to new_priority
int thread_get_priority(void) // Return priority of current thread

 

🔹 우선순위 스케줄링 구현

tid_t thread_create(const char *name, int priority, thread_func *function, void *aux)

• 우선순위의 순서에 따라 ready_list에 thread를 삽입하기
• thread가 ready_list에 추가될 때 새로운 thread와 현재 thread의 우선순위 비교하기
• 새로운 thread의 우선순위가 더 높으면 schedule() 호출 → 현재 thread가 CPU를 양보한다.

🔹 thread_create()

• ready_list에 새로운 thread를 넣을 때, 현재 실행 중인 thread와 우선순위를 비교한다.
• 새로 도착한 thread가 더 높은 우선순위를 가지면, 현재 실행중인 thread를 선점하고 새로운 것을 실행한다.

🔹 다른 수정할 사항들

void thread_unblock(struct thread *t) // When the thread is unblocked, it is inserted to ready_list in the priority order.
void thread_yield(void) // The current thread yields CPU and it is inserted to ready_list in priority order.
void thread_set_priority(int new_priority) // Set priority of the current thread. Reorder the ready_list

• thread_unblock() / thread_yield()

/* 수정 전 */
list_push_back (&ready_list, &curr->elem);

/* 수정 후 */
list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);

bool cmp_priority(struct list_elem *a, struct list_elem *b, void *aux UNUSED) {
	struct thread *t1 = list_entry(a, struct thread, elem);
    struct thread *t2 = list_entry(b, struct thread, elem);
    return t1->priority > t2->priority;
}

• thread_set_priority()

/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority) {
	// Set priority of the current thread
	thread_current ()->priority = new_priority;
	// Reorder of the ready_list
	list_sort(&ready_list, cmp_priority, NULL);
}

구현 진행 상황