Pintos Project1 - Priority Scheduling (1)

Pint OS project 1 -Alarm Clock (1)

 

---

 🅿️ Priority Scheduling

• 높은 우선순위의 스레드가 낮은 우선순위 스레드보다 먼저 실행되도록 스케줄링
• ready_list 우선순위에 따라 정렬
  • ready_list에 새로운 스레드 추가될 때마다, 위치 조정
  • 스케줄러는 가장 높은 우선순위 스레드 선택해 CPU 할당
• 우선순위에 따른 즉각적인 양보 (추가 된 스레드 높은 우선순위 가지는 경우)
  • 즉시 CPU를 양보하여 우선순위가 높은 스레드 실행
  • 이런 경우 thread_yield()를 호출하고, CPU 제어를 더 높은 우선순위 스레드로 전환
• 대기 중인 스레드 관리
  • 스레드가 락,세마포어, 또는 조건 변수 기다릴 때도 우선순위 고려
• 우선순위는 높은 숫자가 높은 우선순위를 의미함
• Priority Inversion  & Priority Donation
  • 낮은 우선순위의 스레드가 높은 우선순위의 스레드가 필요한 리소스 보유
  • 높은 우선순위의 스레드가 실행되지 못하는 상황
  • Priority Donation
    • 우선순위 역전을 해결하기 위함
    • 높은 우선순위 스레드가 낮은 우선순위 스레드에게 자신의 우선순위 임시로 기부
    • 락 해제할 때까지 기부 유지
    • 락이 해제되면 L의 우선순위는 원래 우선순위로 돌아감
  • 고려사항
    • 여러 스레드가 기부할 수 있는 상황 
    • Nested Donation (중첩 기부) 처리
    • Nested Donation 가 무한으로 반복되는 것을 방지하기위해  Donation의 깊이 제한  

 

우선순위 스케줄러 특징

• 락에 대해서만 우선순위 Donation 구현 (세마포어나 조건 변수에 대한 우선순위 기부는 필요 없음)
• 모든 스케줄링에 우선순위가 반영되도록 구현 

---

구현 빌드 순서

(1) 

make build/tests/threads/priority-fifo.result
make build/tests/threads/priority-change.result
make build/tests/threads/priority-preempt.result

 

(2)

make build/tests/threads/priority-sema.result

 

(3)

make build/tests/threads/priority-condvar.result

 

(4)

make build/tests/threads/priority-donate-one.result
make build/tests/threads/priority-donate-lower.result
make build/tests/threads/priority-donate-sema.result
make build/tests/threads/priority-donate-chain.result
make build/tests/threads/priority-donate-nest.result
make build/tests/threads/priority-donate-multiple.result
make build/tests/threads/priority-donate-multiple2.result

• 위와 같은 순서로 빌드를 하면 편하다. 

---

이번 포스팅의 목표는 "구현 빌드 순서 (1)" 구현

Preemption 

1. When inserting the new thread to the ready list, compare the priority with the running thread.
→ ready list에 새로운 스레드 삽입 시, 실행 중인 스레드 우선 순위 비교 

 2. Schedule the newly inserted thread if it has the higher priority with the currently running thread.
→ 새로운 스레드가 생성되어 바로 ready list에 들어가거나, 우선순위 조정이 된 경우 

 

• Alarm clock을 끝내고 난 상태
• FIFO (First in First Out) 방식으로 ready list 구현
• 우선 순위가 높은 스레드(보라색)이 Lock을 얻고도 바로 실행되지 않는 (현)문제 

 

 

• 위의 스레드 순서와 같이 바꿔주는게 목표
• 우선 순위가 높은 스레드(보라색)이 Lock 얻으면 바로 실행

---

thread.c

 

• ready list에 들어가기 전 스레드의 우선순위에 따라 ready list 정렬
• 우선 순위를 계산 해줄 수 있는 함수 구현

 

bool thread_compare_priority(struct list_elem *l, struct list_elem *s, void *aux UNUSED){
	struct thread *a = list_entry(l,struct thread,elem);
	struct thread *b = list_entry(s,struct thread,elem);
	return a->priority > b->priority; 
}

 

 

 

• ready_list에 바로 온 스레드의 우선순위가 현재 CPU를 점유하는 스레드보다 높은 우선순위를 가진 경우
• 만일 ready_list가 비워져 있는 경우 return
• 현재 실행 중인 스레드의 우선순위와 ready_list의 맨 앞 스레드의 우선순위 비교

void thread_test_preemption(void){

	if(list_empty(&ready_list)){
		return;
	}
	
	struct thread *curr = thread_current();
	struct thread *front_ready = list_entry (list_front (&ready_list), struct thread, elem);

	if (front_ready->priority > curr->priority){
		thread_yield();
	}
}

 

 

 

• 스레드를  ready_list에 넣어주는 경우 
  • thread_unblock( )
  • thread_yield ( )
• 단순히 list_push_back ( FIFO 방식)에서 우선순위 위주 스케줄링으로 전환

void thread_unblock (struct thread *t) {
    ...
    // list_push_back (&ready_list, &t->elem); // ready_list에 스레드 추가

	list_insert_ordered(&ready_list, &t->elem,thread_compare_priority,NULL);	// 변경 사항    
    ...
}


void thread_yield (void) {
	...
	if (curr != idle_thread){
	list_insert_ordered(&ready_list, &curr->elem,thread_compare_priority,NULL);	// 변경 사항
	}
	...
}

 

 

 

• 새로운 스레드를 ready_list에 넣거나 우선순위 조정 한 경우
  • thread_create( )
  • thread_set_priority( )

thread_create (const char *name, int priority,thread_func *function, void *aux) {
	
    ...
	thread_unblock (t); 
	thread_test_preemption(); // 변경 사항
	return tid;
}


void thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	thread_test_preemption(); // 변경 사항
}

• thread_create( )에 thread_test_preemption( ) 실행
  • 새로운 스레드가 바로 ready list에 왔는데, CPU 우선순위보다 높은 경우 현재 스래드 양보
• thread_set_priority( )에 thread_test_preemption( ) 실행
  • 우선 순위가 조정 되었을 때,  CPU 우선순위보다 높은 경우 현재 스래드 양보

 

 

🔖 테스트 결과

pass tests/threads/priority-fifo
pass tests/threads/priority-change
pass tests/threads/priority-preempt

• 해당 3개의 테스트 케이스 pass가 뜨는 것을 확인 (실제 출력 양식은 위와 다름)