[TIL/크래프톤 정글9기] 65일차 (Pintos 우선순위 기부 수도 코드)

우선 순위 기부 - 쓰레드 구조체에서 도네이션 리스트 구성 및 도네이션 리스트에서 같은 락 걸린 제일 빠른 같은 락 도네이션 elem 찾기?

Thread.h

thread.h에 thread 구조체가 있기 때문, 이미 구조체가 있기 때문에 thread 구조체에 선언만 하면 됨

struct thread

• 추가
  • struct lock* wait_on_lock
    • “내가 지금 어떤 락을 기다리고 있는지”를 저장하는 포인터
    • 락을 기다릴 때만 값이 들어가고, 락을 얻거나 기다림이 끝나면 NULL
    • 락 대기 상태 관리에만 사용
  • struct list donor_list
    • “나에게 우선순위를 기부한 쓰레드들”을 저장하는 용도
    • 여러 쓰레드가 동시에 나에게 기부할 수 있으니, 리스트로 관리
    • 리스트 안에는 “기부자 쓰레드”의 정보(보통 thread 구조체의 포인터 등) 들어감
    • 항상 우선순위 오름차순 정렬로 관리하면, 가장 높은 우선순위 기부자를 쉽게 찾을 수 있음
  • struct list_elem donor_elem
    • “내가 다른 쓰레드의 donor_list에 들어갈 때” 리스트 요소 사용
    • 즉, 내가 누군가에게 우선순위를 기부할 때, 그 상대방의 donor_list에 내 정보를 넣기 위해 필요
  • int donated_priority
    • 스레드가 다른 스레드에게 우선순위를 기부받으면, 임시로 더 높은 우선순위를 가지게 됨
    • 이때 원래의 우선순위(priority) 값을 덮어써버리면, 기부가 끝났을 때 원래 우선순위를 복원할 수 없게 되므로 문제 발생
    • 따라서 기부로 인해 변경된 우선순위와 원래 우선순위를 분리하여 관리

Thread.c

함수 :

int get_effective_priority(struct thread *)

• 입력한 받은 thread의 도우너 리스트가 있으면 donor_list에서 가장 큰 priority return
  • 수도코드

    int get_effective_priority(struct thread * t) {
    	/* 도우너 스레드 = list_entry(가장 뒤에 있는 donor_list_elem, thread, donor_elem)
    	return donor_list->priority; <- 왜냐 나를 락거는 애들은 나보다 우선순위가 크기 때문*/
    }

int thread_get_priority(void)

• 현재 스레드의 get_effective_priority()를 가져오면 스레드의 현재 가지고 있는 우선 순위를 가져올 수 있음
• 수도코드

  int
  thread_get_priority (void) {
  	/*
  	현재 스레드의 get_effective_priority()를 가져오면 
  	스레드의 현재 가지고 있는 우선 순위를 가져올 수 있음
  	return get_effective_priority(thread_current ());
  	*/
  }

void set_priority(int)

• current thread의 원본 priority를 변경
  • 수도코드

    void set_priority(int new_priority) {
    	/*
    	현재 스레드의 우선순위 = 입력 받은 우선 순위
    	cur_priority = new_priority
    	
    	while로 donor_list를 순회하면서,
    	각 donor 스레드의 실질적인 우선순위(get_effective_priority)를 얻어옴
    	이 우선순위를 기준으로 기부를 유지할지 회수할지 판단하기 위해 사용
    
    	donor의 우선순위가 새 priority보다 작거나 같으면
    	  donor_list에서 해당 donor 이후 전체 리스트를 잘라냄(extract)
    	  
    	마지막 yield*/ 
    }

List.c

함수 추가 :

int list_extend(strcut list *dest, struct list *src)

• src list를 dest의 끝에 이어붙이는 함수
• 수도코드

  int list_extend(struct list *dest, struct list *src)
  {
  	/*
  	dest나 src가 null이면 에러
  	만약 src의 사이즈가 0이면 return 0
  
  	dest의 tail전 원소 d_end를 찾음
  	src의 head 다음 원소 s_start를 찾음
  	d_end , s_start 연결
  
  	dest의 tail 전 원소 s_end를 찾음
  	s_end, src.tail 연결
  	return 0
  	*/
  }
  

struct list * list_extract(struct list *list)

• list를 분리해내는 함수
• 수도코드

  struct list *list_extract(struct list *list)
  {
  	// list보다 앞에 다른 원소가 있는지 확인
  		// (head -> next) -> prev != head
  	// list보다 뒤에 다른 원소가 있는지 확인
  		// (tail -> prev) -> next != tail
  	//	앞뒤에 원소가 둘 다 있으면 둘이 연결
  	
  	//	list 첫 원소가 head를 다시 가리키도록 연결
  	//	list의 끝 원소가 tail을 다시 가리키도록 연결
  	//	return list
  }
  

Sync.c

find_same_priority_in_donor_list()

쉣 세임 낫 세임

lock_acquire(struct lock *lock)

• 현재 스레드가 lock을 획득하는 함수
• 필요 변경 사항
  • sema_down을 sema_try_down으로 변경해서 실패시 처리 추가 (인터럽트 끄고 할 것)
  • 쓰레드의 wait_on_lock에 lock 추가
  • 우선순위 기부 로직 추가
    • 수도코드

      void
      lock_acquire (struct lock *lock) {
      	ASSERT (lock != NULL);
      	ASSERT (!intr_context ());
      	ASSERT (!lock_held_by_current_thread (lock));
      
      	enum intr_level old_level;
      	old_level = intr_disable ();
      	if(! sema_try_down(&lock->semaphore)) {
      		struct thread *donor = thread_current(), *holder = lock->holder;
      		donor->wait_on_lock = lock;
      		/*
      		TODO : 우선순위 기부 로직
      		donor의 donor_list를 순회하며 이 lock을 쓰고있는 쓰레드 donor elem을 찾으면 list_extract
      		holder 의 donor list 제일 뒤에 donor의 donor list를 추가
      		*/
      		intr_set_level(old_level);
      		sema_down (&lock->semaphore);
      	} else{
      		intr_set_level(old_level);
      	}
      
      	lock->holder = thread_current ();
      }

lock_release(struct lock *lock)

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));
	/*
		TODO : 우선순위 가져오는 로직 구현
		인터럽트 걸고
		semaphore의 wait_list의 front를 holder의 donor_list에서 extract
		lock->holder = NULL;
		sema_up (&lock->semaphore);
		인터럽트 풀기
	*/
	
}