Pintos Project1 - Priority Scheduling (2)

Pint OS project 1 - Priority Scheduling (1)

(바로 이어지는 Priority Scheduling 포스팅)

• Priority Scheduling (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 구현 (세마포어나 조건 변수에 대한 우선순위 기부는 필요 없음)
• 모든 스케줄링에 우선순위가 반영되도록 구현 

---

구현 빌드 목표

 

(2) Semaphore 대기 리스트 정렬

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

 

(3) Condtion value 대기 리스트 정렬

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

 

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

---

📌이번 포스팅의 목표는 "구현 빌드 순서 (2) / (3)" 구현

synch.h

• 먼저 synch.h에 선언된 semaphore, lock, condition 구조체를 확인해보자.
• 아래와 같이 semaphore와 condition 구조체 내부에는 waiter라는 list가 있다.
• 이번 포스팅은 저 두개의 대기 리스트들을 우선순위에 따라 정렬하면 된다.

/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

/* Lock. */
struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

해당 구조체 그림 참고 (https://coding-camel.tistory.com/196)

• lock
  • 자원에 대한 접근 제어
  • 대기 스레드 리스트 semaphore.waiters
  • 자원 접근 가능 시 sema_up으로 대기 스레드 깨움
• condition
  • 특정 조건 충족을 기다리는 스레드 관리
  • 대기 스레드 리스트 condition.waiters
  • 조건 충족 시 cond_signal로 대기 스레드에 sema_up 호출

 

✨ Semaphore 대기 리스트 정렬

synch.c

• Semaphore 내에서 현재 스레드를 push/pop
• 때문에 전 thread.c에서 만들어준 thread_compare_priority 함수 사용 가능
  • Semaphore의 waiters push (sema_down)
    • list_insert_ordered 함수로 스레드 적절한 위치 삽입
  • Semaphore의 waiters pop (sema_up)
    • list_sort 함수로 정렬 후 우선 순위 높은 스레드 pop 

void sema_down (struct semaphore *sema) {
	. . .
	while (sema->value == 0) {
		// list_push_back (&sema->waiters, &thread_current ()->elem);
		list_insert_ordered(&sema->waiters,&thread_current()->elem,thread_compare_priority,NULL);  // 추가 내용
		thread_block ();
	}
	. . .
}

void sema_up (struct semaphore *sema) {
	 . . .
	if (!list_empty (&sema->waiters)){
		list_sort(&sema->waiters,thread_compare_priority,NULL); // 추가 내용
		thread_unblock (list_entry (list_pop_front (&sema->waiters),struct thread, elem));
	}
	. . .
}

 

✨ Condition value 대기 리스트 정렬

synch.c

• Condition value 구조체 내부의 waiter는 세마포어들의 리스트
• cond waiters 리스트를 우선순위로 정렬 
  • 세마포어 리스트를 비교해주는 함수 정의
    •  sema_compare_priority 함수 (정의 예정)
    • semaphore elem는 thread_compare_priority 함수로 비교 X
  • cond의 waiters push (cond_wait)
    • list_insert_ordered 함수로 세마포어 적절한 위치 삽입
  • cond의 waiters pop( cond_signal)
    • list_sort 함수로 정렬 후 우선 순위 높은 스레드 pop

bool sema_compare_priority (struct list_elem *a,struct list_elem  *b, void *aux UNUSED){
	struct semaphore_elem *l = list_entry(a,struct semaphore_elem, elem);
	struct semaphore_elem *s = list_entry(b,struct semaphore_elem, elem);

	struct list *list_l = &(l->semaphore.waiters);
	struct list *list_s = &(s->semaphore.waiters);

	if(list_empty(list_l) || list_empty(list_s)){
		return false; 
	}

	int l_priority = list_entry(list_front(list_l),struct thread, elem)->priority;
	int s_priority = list_entry(list_front(list_s),struct thread, elem)->priority;
	return l_priority > s_priority;	
}

• sema_compare_priority ( ) 정의
• 매개변수로 주어진게  semaphore_elem의 list_elem
• 타고 타고 올라가서 thread의 priority를 구하고 비교
• list_front를 사용 할 경우 예외 처리 (대기 리스트가 없는 경우)
  • list_beyond로 하는 경우는 예외 처리 필요 없음

 

void cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;
    . . . 
	sema_init (&waiter.semaphore, 0);
	// list_push_back (&cond->waiters, &waiter.elem);
	list_insert_ordered(&cond->waiters,&waiter.elem,sema_compare_priority,NULL); // 추가 내용
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}


void cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	. . . 
	if (!list_empty (&cond->waiters)){
		list_sort(&cond->waiters,sema_compare_priority,NULL); // 추가 내용
		sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
	}
    . . . 
}

• cond_wait의 list_push_back (FIFO) 방식을 우선순위로 정렬
  • list_insert_ordered에서 sema_compare_priority 함수 사용
• cond_signal에서는 list_sort로 정렬 후 pop

 

🔖 테스트 결과

perl -I../.. ../../tests/threads/priority-sema.ck tests/threads/priority-sema tests/threads/priority-sema.result
pass tests/threads/priority-sema

perl -I../.. ../../tests/threads/priority-condvar.ck tests/threads/priority-condvar tests/threads/priority-condvar.result
pass tests/threads/priority-condvar

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

 

---

 

지금까지 내용은 거의 다 FIFO 방식으로 되던 방식을 우선순위로 바꿔보았다.

다음 포스팅은 Priority Inversion / Donation 부분을 다룬다. 

이 부분은 지금까지 했던거 보다 훨씬 더 어렵다 ...