[Jungle] Week8. Pintos Project 1. Priority scheduling (3) : Priority Donation

somi·2024년 5월 20일
0

[Krafton Jungle]

목록 보기
55/68

Priority Inversion, 우선순위 역전

  • 낮은 우선순위의 쓰레드(L)가 어떤 자원(락)을 점유하고 작업 수행중
  • 높은 우선순위의 쓰레드(H)가 실행되어 같은 자원(락)을 요구하지만 L이 점유하고 있기 때문에 H는 대기 상태가 된다.
  • 높은 우선순위의 쓰레드(M)가 실행되어 CPU 시간 차지하게 됨, 그래서 이때 M은 H보다 우선순위가 낮지만 H가 L에 의해 블록되어 있기 때문에 실행될 수 있다.
  • 결과적으로 가장 높은 우선순위를 가진 H가 가장 낮은 우선순위를 가진 L 때문에 더 낮은 우선순위의 M에 의해 간접적으로 블록된다.

따라서 이를 해결하기 위해 우선순위 기부(Priority Donation)기법을 핀토스에서 사용한다.


Priority Donation

높은 우선순위의 쓰레드가 낮은 우선순위의 쓰레드에 의해 블록될 때, 낮은 우선순위의 쓰레드가 높은 우선순위의 쓰레드의 우선순위를 일시적으로 donation 받는 것!

  • 높은 우선순위의 쓰레드(H)가 어떤 자원(락)을 요청하지만 그 리소스가 낮은 우선순위의 쓰레드(L)에 의해 점유되어 있는 경우
  • H는 L이 점유한 자원/락 때문에 블록된다.
  • L이 점유한 락이 해제될 때까지 기다리는 동안, H는 자신의 우선순위를 L에게 기부한다. 이로 인해 L의 우선순위가 H의 우선순위로 상승한다.
  • L은 더 높은 우선순위로 실행되어 락을 빨리 해제할 수 있게 된다.
  • 락이 해제되면, L의 우선순위는 원래의 우선순위로 돌아간다.

주의

  • 쓰레드가 2개 이상의 lock을 보유하게 되면 각 lock에 의해 priority donation이 발생할 수 있다.
    따라서 구현할 때 우리는 쓰레드의 이전 상태의 우선순위를 기억하고 있어야 한다.

multiple priority donation

  • 쓰레드 L(priority: 31)이 Lock A, Lock B 점유
  • 쓰레드 M(priority: 32)이 Lock A 요청, priority Donation 발생 (L priority = 32)
  • 쓰레드 H(priority: 33)이 Lock B 요청, priority Donation 발생 (L priority = 33)
  • 쓰레드 L이 lock B를 해지하면, 이전 상태의 우선순위(쓰레드 M에 의해 priority donation을 받은 priority: 32)를 기억하고 있다가 쓰레드 L의 priority를 31이 아니라 32로 변경해야 한다 !


Nested Donation

우선순위 기부가 중첩된 상황
한 쓰레드가 다른 쓰레드에게 우선순위 기부 -> 기부받은 쓰레드가 다시 다른 쓰레드에게 우선순위 기부하는 상황

  • 쓰레드 H가 lock B(쓰레드 M 점유)를 얻기 위해 대기. 이때 쓰레드 M은 lock A(쓰레드 L 점유)를 얻기 위해 대기하고 있다.
  • 쓰레드 H의 우선순위는 쓰레드 L, M에게 모두 priority donation되어야 한다.

이해를 위해 적어본 nested priority donation 과정

  1. H가 lock B(쓰레드 M이 점유 하는 상황) 요청 -> 따라서 쓰레드 H는 M에게 priority donation.
    쓰레드 M의 우선순위는 H의 우선순위로 priority boost
  2. M가 lock A(쓰레드 L이 점유) 요청 -> 쓰레드 M은 lock A가 해제할 때까지 대기
  • 쓰레드 M은 H로부터 기부받은 우선순위를 L에게 기부
  • 쓰레드 L의 우선순위는 쓰레드 M, 즉 쓰레드 H의 우선순위로 boost
  1. L이 lock A 해제: 쓰레드 L의 priority boost, 쓰레드 L은 더 높은 우선순위가 되어 빠르게 lock A 해제할 수 있게 된다. => Lock A가 해제되면 쓰레드 M은 lock A 획득 가능
  2. M이 lock B 해제 : 쓰레드 M은 이제 lock A를 사용해서 작업 후 lock B 해제 => 쓰레드 H가 lock B 획득 가능
  3. 우선순위 원래대로 복구
    각 쓰레드가 자신의 작업을 마치고 락을 해제하면 우선순위는 원래대로 복구!

구현하기!

먼저 thread 구조체에
Donation 받기 전의 원래의 priority를 저장할 init_priority 필드, 현재 쓰레드가 기다리고 있는 Lock을 저장할 wait_on_lock 필드, donation 기부받은 list를 관리할 donations 필드, donations 리스트의 각각의 엘리먼트를 관리할 d_elem 필드를 추가해준다.
=> 각 쓰레드가 priority donation을 어떻게 받는 상황인지, 어떤 Lock을 기다리고 있는 상황인지, priority donations 리스트를 어떻게 관리하고 있는지를 알 수 있게 된다.


donations: 각 쓰레드가 받은 우선순위 기부를 추적하기 위한 필드 -> 해당 쓰레드에게 우선순위를 기부한 쓰레드의 list


wait_on_lock: 각 쓰레드가 기다리고 있는 lock을 추적하기 위한 필드.
현재 쓰레드가 어떤 lock을 기다리고 있는지 알 수 있게 된다.


init_thread()

새로 추가된 필드도 초기화해주는 코드를 입력해준다.

lock_acquire()

쓰레드가 lock을 획득할 때 priority donation을 처리해주는 코드를 추가해준다.

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL); 
	ASSERT (!intr_context ()); 
	//Lock을 획득하는 동작은 인터럽트 컨텍스트에서 수행되면 안됨. 일반적으로 사용자 레벨의 코드에서만 수행되어야 한다.
	ASSERT (!lock_held_by_current_thread (lock)); //현재 쓰레드가 이미 해당 락을 보유하고 있지 않는지 확인
	//락을 이미 보유한 쓰레드가 다시 시도할 경우 데드락 발생시킬 수 있음. 

	//해당 Lock의 holder가 이미 존재한다면(다른 쓰레드가 Lock을 보유하고 있다면)
	if (lock->holder != NULL) {
		thread_current()->wait_on_lock = lock; 

		// list_push_back(&lock->holder->donations, &thread_current()->d_elem);
		//현재 쓰레드를 락을 보유한 쓰레드의 donations 리스트에 우선순위에 따라 삽입 
		list_insert_ordered(&lock->holder->donations, &(thread_current()->d_elem),compare_donation_priority, NULL);

		donate_priority(); // priority donation: lock을 보유한 쓰레드의 우선순위를 현재 쓰레드의 우선순위로 설정
	}
	sema_down (&lock->semaphore); 
	//lock에 연결된 세마포어의 값이 0보다 크면 1감소, 그렇지 않으면 대기 상태로 전환
	//lock을 획득하기 위해 대기하거나 즉시 획득하는 역할 -> Lock 획득시 -1(공유 자원에 대한 접근 권한 획득했음을 의미) 

	//현재 쓰레드가 lock을 획득하게 되면, 
	thread_current()->wait_on_lock = NULL; //현재 쓰레드가 더 이상 이 lock을 기다리고 있지 않음 표시
	lock->holder = thread_current(); //lock의 소유자는 현재 쓰레드로 설정

}

if (lock->holder== NULL)
만약 해당 락의 Holder 가 없다면, sema_down(세마포어 값이 0보다 크면 1 감소, 그렇지 않으면 대기 상태)
=> 이후 lock을 획득하게 되면 wait_on_lock = NULL로 해주어서 현재 쓰레드가 더 이상 이 lock을 기다리고 있지 않다고 저장하고 lock의 Holder를 thread_current()로 설정한다.

if (lock->holder != NULL)
반면에 이미 해당 Lock의 Holder가 있다면, priority donation이 일어난다.

Priority Donation을 수행하는 함수
-> 현재 쓰레드가 기다리고 있는 Lock과 연결된 모든 쓰레드들을 순회하면서
현재 쓰레드의 우선순위를 lock을 보유하고 있는 쓰레드에게 기부한다.

void donate_priority(void) {

	struct thread *cur = thread_current();
	int cnt = 0;

	for (cnt; cnt < 9; cnt++){
		
		//현재 쓰레드를 기다리고 있는 lock이 없으면 반복문 종료
		if (cur->wait_on_lock == NULL) {
			break;
		}
		else 
		{	
			//holder = 현재 lock을 보유하고 있는 쓰레드
			struct thread *holder = cur->wait_on_lock->holder; 	
			//lock을 보유하고 있는 쓰레드의 우선순위를 현재 쓰레드의 우선순위로 설정(priority donation)
			holder->priority = cur->priority;
			cur= holder;
		}
	
	}		
}	

현재 쓰레드가 기다리고 있는 lock의 holder에게 현재 쓰레드의 우선순위를 기부한다.
nested Priority donation의 limit도 설정해주었다. 우선순위 기부가 너무 많이 발생하게 되면 너무 많은 자원을 우선순위 기부관련 작업을 하는데 사용해야 할 수도 있기 때문이다.

현재 실행 중인 쓰레드는 lock->holder의 우선순위보다 높아서, 우선순위비교 없이 바로 우선순위 기부를 해줄 수 있다.

이미 스케줄링할때 ready_list에서 가장 우선순위가 높은 순으로 스케줄하도록 구현했기 때문에


lock_release()

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock)); //lock을 해제하기 전에 현재 쓰레드가 Lock의 소유자인지 확인
	lock->holder = NULL; //lock의 소유자를 NULL로
	
    remove_with_lock(lock);
	revoke_priority();
	
    sema_up (&lock->semaphore); /*세마포어의 값 1증가. -> 
	만약 세마포어의 값이 0이하였다면, 하나 이상의 쓰레드가 lock을 얻기 위해 대기 중이었음.
	-> 하나의 쓰레드가 깨어나서 lock을 얻을 수 있게 됨 */	
}

remove_with_lock(lock)

: 현재 쓰레드가 특정 lock을 기다리며 기부받은 priority를 관리하는 함수
-> 현재 쓰레드의 donations 리스트를 순회하면서, 기부해준 쓰레드가 wait_on_lock이 release된 Lock을 기다렸던 경우, 해당 쓰레드를 donations 리스트에서 지워준다.
해당 Lock을 기다렸기 때문에 우선순위를 기부를 했는데 이제 Release됐으니까 기부받은 쓰레드는 원래의 우선순위로 돌아가야 한다.
또한 우선순위 기부는 높은 우선순위의 쓰레드가 낮은 우선순위의 쓰레드가 보유한 자원을 기다릴 때 우선순위 역전을 방지하기 위해 존재한다. lock이 해제되면 더 이상 자원을 기다릴 필요가 없으니 기부된 우선순위도 의미 없어진다.

void remove_with_lock(struct lock *lock){
	struct thread *cur = thread_current();
	struct list_elem *elem = list_begin(&cur->donations);


	//lock이 여러개일 때 -> 순회가 필요
	//현재 쓰레드의 Donations(다른 쓰레드로 부터 기부받은 우선순위 리스트 순회)
	for (elem; elem!= list_end(&cur -> donations);){
		struct thread *t = list_entry(elem, struct thread, d_elem);

		//쓰레드가 lock을 기다리고 있다면 donation list에서 제거
		if (t->wait_on_lock == lock){
			elem = list_remove(&t->d_elem);
		}
		else {
			elem = list_next(elem);
		}
	}
}

revoke_priority()

현재 쓰레드의 우선순위를 원래대로(처음의 init_priority로 되돌리거나, 기부를 받은 우선순위가 있다면 기부 받은 우선순위 중 가장 높은 우선순위와 현재 쓰레드의 우선순위를 비교해서 우선순위를 업데이트 한다.

void revoke_priority(void){
	struct thread *cur = thread_current();

	//현재 쓰레드의 우선순위를 원래 초기 우선순위 값으로 되돌림!
	cur->priority = cur->init_priority;

	//기부 받은 우선순위가 있다면 
	if (!list_empty(&cur->donations)){
		//donations list에서 가장 큰 우선순위 값
		struct thread *donation_max_priority = list_entry(list_begin(&cur->donations), struct thread, d_elem);

		//기부 받은 우선순위와 현재 쓰레드의 우선순위를 비교해서, 
		//기부 받은 우선순위 값이 더 크다면 우선순위 업데이트
		if (donation_max_priority->priority > cur->priority){
			cur->priority = donation_max_priority->priority;
		}
	}
}

참고)

여기서 if (donation_max_priority->priority > cur->priority) 조건문은 주석처리 해주어도 테스트 통과된다.

왜냐하면 lock_acquire할 때 이미 donations 리스트에 정렬되어 insert되기 때문에 donations리스트의 첫 번째 요소는 항상 가장 높은 우선순위를 가진 쓰레드다.

또한 빈리스트가 아닐 때라는 조건을 이미 걸어주었으니 list_front를 사용해도 테스트는 Pass될 것이다!

따라서 lock_release()를 해줄 때 현재 쓰레드의 Donation list를 순회하면서 해당 Lock을 기다리는 도네이션 항목을 제거해주고, 쓰레드의 우선순위도 재조정해주어야 한다.


Project1에서 가장 어려웠던 Priority scheduling.

특히 donation의 개념이 너무 어려웠고 이를 어떻게 구현해야 할지 너무 막막했다. 정답을 참고하면서 구현했는데도 개념이랑 구현 코드 둘 다 잘 이해가 안가 시간이 더 오래 걸렸다.

wait_on_lock, Donations 리스트로 donation을 관리하는 것을 직접 구현하면서 우선순위 스케줄링에서 우리가 우선순위 역전 문제를 해결해주기 위해서 고려해줘야 하는 것이 얼마나 많은지 깨달았다.

profile
📝 It's been waiting for you

0개의 댓글