이전 Priority Scheduling과 이어지는 글이다.
이 글에서는 저번 글에 이어서, Priority Donation을 구현하는 것을 메인으로 다룬다.
thread.h
struct thread {
/* Owned by thread.c. */
tid_t tid ; /* Thread identifier. */
enum thread_status status ; /* Thread state. */
char name [ 16 ]; /* Name (for debugging purposes). */
int priority ; /* Priority. */
int64_t localTick ; // 로컬 틱 필드 추가
int originPriority ; // priority 복구를 위한, 원래 priority
struct lock * waitOnLock ; // 현재 기다리는 lock
struct list donation ; // priority 를 빌려준 스레드 리스트
struct list_elem donationElem ; // donation 리스트를 관리하기 위한 element
/* Shared between thread.c and synch.c. */
struct list_elem elem ; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t * pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf ; /* Information for switching */
unsigned magic ; /* Detects stack overflow. */
};
우선 thread 구조체에 Priority Donation에 필요한 몇 개의 필드를 추가한다.
int originPriority : priority를 복구할 때 사용할, 기존 priority를 저장할 필드
struct lock *waitOnLock : 이 스레드가 어떤 lock을 기다리고 있는지를 저장할 필드
struct list donation : 이 스레드, 즉 holder 에게 lock을 요청한 스레드들을 저장할 리스트. 여기서 가장 높은 priority를 donation 받는다.
struct list_elem donationElem : donation 리스트만을 관리하기 위한 list element
thread.c
static void
init_thread ( struct thread * t , const char * name , int priority ) {
ASSERT ( t != NULL );
ASSERT ( PRI_MIN <= priority && priority <= PRI_MAX );
ASSERT ( name != NULL );
memset ( t , 0 , sizeof * t );
t -> status = THREAD_BLOCKED ;
strlcpy ( t -> name , name , sizeof t -> name );
t -> tf . rsp = ( uint64_t ) t + PGSIZE - sizeof ( void * );
t -> priority = priority ;
t -> magic = THREAD_MAGIC ;
// 기존 priority 저장해두기
t -> originPriority = priority ;
// 기다리고 있는 lock은 NULL
t -> waitOnLock = NULL ;
// 스레드 내의 donation 리스트 초기화
list_init ( & t -> donation );
}
위에서 thread 구조체에 4개 필드를 추가했으니 초기화해 주어야 한다.
donationElem을 제외한 모든 필드를 사용할 수 있도록 초기화해 두자.
synch.c
void
lock_acquire ( struct lock * lock ) {
ASSERT ( lock != NULL );
ASSERT ( ! intr_context ());
ASSERT ( ! lock_held_by_current_thread ( lock ));
// 현재 스레드 가지고 오기
struct thread * cur = thread_current ();
// 다른 스레드가 lock을 이미 가지고 있다면
if ( lock -> holder ) {
// 어떤 lock을 기다리는지 필드에 추가
cur -> waitOnLock = lock ;
// holder의 donation 리스트에 현재 스레드를 우선순위 내림차순 정렬하여 추가해준다
list_insert_ordered ( & lock -> holder -> donation , & cur -> donationElem , compare_thread_donate_priority , NULL );
// 현재 스레드부터 waitOnLock을 확인하여 파고들어가 priority를 donate 한다
donate_priority ();
}
// 해당 lock의 세마포어 값을 내린다
// 자리가 없다면 스레드는 waiters 에 추가되고 block된다
sema_down ( & lock -> semaphore );
// down됐으면 lock을 획득했다는 것이니 waitOnLock을 NULL로 바꿔준다
cur -> waitOnLock = NULL ;
lock -> holder = cur ;
}
lock을 요청하는 함수이다.
원하는 lock의 holder가 존재한다면(이미 다른 스레드가 lock을 가지고 있다면), 현재 스레드의 waitOnLock을 해당 lock으로 바꾼 후, holder의 donation 리스트에 현재 스레드를 우선순위 정렬하여 추가한다. 그리고 donation list가 변경되었으니, donate_priority()를 호출하여 donation을 재정비해 준다.
그리고 sema_down을 호출하여 lock이 해제될 때 까지 기다린다. sema_down 상태에서 blocked되어 기다리다가 lock이 해제되면 아래쪽 코드를 실행한다.
lock이 해제되고 sema_down이 끝났다면 Lock을 획득했을 테니 waitOnLock을 NULL로 바꿔주고, 해당 lock의 holder를 현재 스레드로 바꿔준다.
thread.c
// list_insert_ordered를 위한 구현, donation_elem priority 기준 정렬
bool compare_thread_donate_priority ( const struct list_elem * a , const struct list_elem * b , void * aux UNUSED ){
struct thread * thread_a = list_entry ( a , struct thread, donationElem);
struct thread * thread_b = list_entry ( b , struct thread, donationElem);
if ( thread_a -> priority > thread_b -> priority ) {
return true ;
}
else return false ;
}
lock_acquire함수의 list_insert_ordered의 인자로 사용되는 함수이다.
donation list를 정렬할 때 사용되는 함수라는 것 외엔 특별할 건 없다.
이 함수를 list_insert_ordered의 인자로 넣으면 priority가 큰 스레드가 donation list의 HEAD쪽에 위치하게 된다.
thread.c
// depth : nested 최대 깊이
// waitOnLock을 NULL이 나올 때 까지 파고 들어가며 우선순위를 넘겨준다.
void donate_priority ( void ) {
int depth ;
struct thread * cur = thread_current ();
// nested 최대 깊이 : 8
for ( depth = 0 ; depth < 8 ; depth ++ ) {
// waitOnLock이 없으면. 즉, 파고 들어가 마지막에 실행되고 있는 스레드일 경우 break
if ( ! cur -> waitOnLock ) break ;
// 현재 스레드가 기다리는 lock의 holder를 가져온다
struct thread * holder = cur -> waitOnLock -> holder ;
// 현재 lock을 가진 holder에게 우선순위를 기부한다.
if ( cur -> priority > holder -> priority ) {
holder -> priority = cur -> priority ;
}
// 다음 lock을 기다리는 스레드로 파고들어 간다.
cur = holder ;
}
}
nested donation 상황을 위한 donate_priority 함수이다.
cur->waitOnLock->holder 고리를 8번까지 파고 들어가서 priority를 donate 한다.
depth가 8인 이유는 딱히 대단한 건 아니고, 8정도면 충분히 nested 상황에서 적절하게 donation을 하기에 충분하기 때문이다. 만약 while로 하거나 무조건 끝까지 파고들도록 하면 오버헤드가 클 수 있어서 적절한 depth를 설정해 주는 게 좋다.
thread.c
// donation 리스트에서 스레드들을 지우는 함수
void remove_with_lock ( struct lock * lock ) {
struct list_elem * e ;
// release 할 현재 스레드 가져오기
struct thread * cur = thread_current ();
// list_end는 TAIL이 아니라, 리스트 마지막에 있는 끝을 의미하는 가상의 요소를 가리킨다.
for ( e = list_begin ( & cur -> donation ); e != list_end ( & cur -> donation ); e = list_next ( e )) {
// donation 리스트 첫 번째 요소에 대한 thread 가져오기
struct thread * t = list_entry ( e , struct thread, donationElem);
// 해당 lock을 기다리고 있었다면 donation 리스트에서 지워주기
// (waitOnLock NULL로 안바꿔주나? -> 바꿔주면 lock을 못받은 다른애들까지 지워져서 안 될 듯?)
if ( t -> waitOnLock == lock ) {
// donationElem 지움으로써 holder 스레드의 donatiotn 리스트에서 제거된다.
list_remove ( & t -> donationElem );
}
}
}
lock을 해제하는 lock_release 함수와 함께 사용되는 함수이다.
lock을 해제하면 해당 lock을 기다리던 스레드들을 기존 holder의 donation list에서 지워줘야겠지?
donation list를 HEAD에서 TAIL방향으로 끝까지 순회하며 해제한 lock을 기다리던 스레드들을 리스트에서 전부 지워준다.
만약 기존 holder가 하나의 lock만 가지고 있었다면 donation list가 전부 지워질 테고, 여러개의 lock을 가지고 있었다면 해당 lock을 기다리던 스레드들만 지워지고 donation list는 남아있을 것이다.
thread.c
// donation 리스트가 비어 있으면 originPriority로 복구하고, 남아 있다면 가장 높은 Priority를 가져온다
void refresh_priority ( void ) {
// release 할 현재 스레드 가져오기
struct thread * cur = thread_current ();
cur -> priority = cur -> originPriority ;
if ( ! list_empty ( & cur -> donation )) {
// donation list의 첫 번째 스레드를 가져오기
struct thread * front = list_entry ( list_front ( & cur -> donation ), struct thread, donationElem);
// donation list의 첫 번째 스레드 우선순위가 현재 스레드 우선순위보다 높으면 바꿔주기
if ( front -> priority > cur -> priority ) {
cur -> priority = front -> priority ;
}
}
}
마찬가지로 lock을 해제하는 lock_release 함수와 함께 사용되는 함수이다.
donation list의 스레드 삭제가 이루어졌을 경우, holder의 priority를 재설정 해 준다.
donation list가 비어있다면 holder의 originPriority로 복구하고, 남아 있다면 남아있는 스레드 중 가장 높은 priority로 설정해 준다.
synch.c
void
lock_release ( struct lock * lock ) {
ASSERT ( lock != NULL );
ASSERT ( lock_held_by_current_thread ( lock ));
// 해제할 lock을 기다리는 스레드들을 donation 리스트에서 제거한다
remove_with_lock ( lock );
// donation 리스트가 수정되었으니, 우선순위를 재설정해 준다
refresh_priority ();
// lock의 holder를 제거한다
lock -> holder = NULL ;
// semaphore 값을 올려 1자리를 만들어준다
sema_up ( & lock -> semaphore );
}
현재 스레드의 lock을 해제하는 lock_release 함수이다.
앞서 만든 remove_with_lock 함수와 refresh_priority 함수를 추가해 주면 된다.
해제된 lock을 기다리던 스레드들을 donation list에서 지우고, 변화한 donation list에 맞게 holder의 priority를 재설정해 준다.
thread.c
void
thread_set_priority ( int new_priority ) {
struct thread * cur = thread_current ();
// 현재 실행중인 스레드 우선순위 변경
// cur->priority = new_priority;
cur -> originPriority = new_priority ;
// 우선순위를 변경했다면, donation 받지 않아도 될 수 있으니 우선순위 재점검한다
refresh_priority ();
// 필요 시 yield하기
thread_preemption ();
}
마지막으로 thread_set_priority 함수를 건드리면 된다.
현재 running중인 스레드의 priority가 변경되면 donation 받지 않아도 될 수 있기 때문에 우선순위를 재점검해야 한다.
따라서 refresh_priority()를 추가해주면 된다.
이렇게 priority scheduling과 priority donation이 끝났다.
===========================
실행 결과
priority 통과
priority와 관련된 test들은 모두 통과된 모습이다.
