주의!

이 글은 pintos 프로젝트의 정답 코드 및 이론을 포함하고 있습니다.
pintos의 취지 특성 상 개인의 공부, 고민 과정이 정말 중요하다고 생각하며

프로젝트 풀이에 대한 스포일러를 받고싶지 않으신 분은 읽으시는걸 비추천 합니다.

부활했다.
그렇게 나를 괴롭히던 코드와 과제들이
C언어 숙련도 상승 + 코드이해 + 알고리즘 학습이 이뤄지니
진도가 한번에 끝나버렸다.

priority 까지 완료!
내가 비전공자이기도 했고, 3만줄 코드 처음봄 + C프로그래밍 미숙 + OS 처음봄 + 영어자료 등으로 인해서 1주일 내내 해매다가 겨우 pass를 받았다.
주변 정글러 분들의 도움도 많이 받았다.

Lock이 왜 필요한가?

위 그림을 보면 L , H는 semaphore 스레드 이다. 그래서 L이 작동할때 H가 추가되더라도 먼저 실행하고 있던 L의 진행을 '강탈'할 수 없다.

그래서 하염없이 기다리게 되는데 이때 semaphore를 공유하지 않는 다른 스레드인 M이 들어오게 되면, 같은 semaphore가 아니기 때문에 priority를 비교하게 되고, 상대적으로 우선도가 낮은 L은 M에게 순서를 빼앗기게 된다.

여기까지 보면 그런가? 할 수도 있는데, 우리가 중요하게 봐야 할 것은
우선도가 높은 H조차도 대기하고 있는 상황에, 상대적으로 우선도가 낮은 M이 먼저 처리가 된다는 것이다.

이러한 우선순위 역전(priority inversion)현상 때문에 우리는 알고리즘을 수정해야 한다.

일단 전제로 깔고 가야하는 것은 다음과 같다.

• 스레드 L이 진행 중일 때는 같은 semaphore를 쓰는 H는 순서를 빼앗을 수 없다.(대기해야됨)

• 하지만 semaphore를 공유하지 않는 다른 스레드가 추가될 시, priority에 따라 실행 중에 빼앗길 수 있다.

• 그렇기 때문에 우리는 높은 스레드를 우선적으로 처리하기 위해, priority가 낮은 스레드 L의 priority를 대기하고 있는 H스레드의 priority 만큼 증가시켜 줄 것이다.

위 방식대로 한다면, 우선순위가 상대적으로 낮은 스레드 L이 먼저 처리가 되겠지만, 이후 추가되는 스레드 M보다 priority가 높은 스레드 H가 먼저 처리 될 수 있다.

Lock을 어떻게 추가하는가?

구현은 단 하나의 방법만 정확하게 구현하면 모든 방식으로도 다 통과가 된다.

우선, Lock을 추가할때는 준비물이 3개가 있다.

• original thread -> 기준이 되는 스레드

• Lock

• New - thread -> 새로 추가하려는 스레드

우리가 추가해야 할 부분은 다음과 같다.

1. 새로운 스레드에서 Lock을 가리키는 매핑

2. Original thread에서 New thread의 element를 가리키는 매핑

3. 이때 New_thread를 가리킬때 Donations에서 insert_ordered 함수를 사용해 priority 크기 순서대로 정렬한다.

4. 정렬하는 기준은 origin_priority가 아닌, priority이다.

이러한 작업을 하면 우리는 2가지 효과를 볼 수 있다.

1. Original thread에서 자신을 바라보는 New thread들을 확인 할 수 있다.

2. New thread는 Lock에 걸려 있기 때문에 wait-list에 추가된다.

매핑이 끝난 후 , 우리는 한가지 작업을 더 해줘야 한다.

위 그림을 기준으로 설명하게 되면, thread1에 2개의 새로운 thread가 추가 되었다. 그렇기 때문에 th1의 priority가 새로 추가된 thread의 priority보다 높다고 장담 할 수 없게 된다.

그래서 새롭게 thread가 추가될때, wait on lock -> holder 순회를 돌면서 각각의 thread의 priority를 갱신해줘야한다. 그 방법은 다음과 같다.

1. new_thread->wait_on_lock->holder 순회를 통해 현재 스레드가 가리키고 있는 스레드로 이동한다.

2. 만약 Donations가 empty 하지 않다면, 제일 앞 D_elem 스레드의 priority와 현재 스레드의 origin_priority를 비교해 더 큰값으로 갱신한다.

3. 1에서 했던것처럼 wait_on_lock이 NULL이 될때까지 반복 순회한다.

이렇게 하면 새로운 thread가 추가되었을때 자신이 가리키고 있는 스레드, 그 스레드가 가리키고 있는 스레드..... 들의 값이 모두 갱신되게 된다.

lock_acquire

void lock_acquire (struct lock *lock) {
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(!lock_held_by_current_thread(lock));

	struct thread *thread_now = thread_current();
	
	if (lock->holder != NULL){
      thread_now->wait_on_lock = lock;
      if(thread_get_priority() > lock->holder->priority){
         list_insert_ordered(&thread_now->wait_on_lock->holder->donations , &thread_now->d_elem , (list_less_func *)&larger , NULL);

            while(thread_now -> wait_on_lock!= NULL){
                  if(thread_now->priority > thread_now->wait_on_lock->holder->priority){
                     thread_now->wait_on_lock->holder->priority = thread_now->priority;
                     thread_now = thread_now ->wait_on_lock->holder;	
                  }
               else break;
            }
      }
	}
	sema_down(&lock->semaphore);
	thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current();
}

위의 과정을 충실하게 따른 코드이다.

lock->holder != NULL일때

• 생성하는 스레드(지금 running 스레드)의 W를 lock으로 매핑
• 스레드의 priority가 holder의 priority보다 크다면
• holder에 insert_ordered로 d_elem을 추가
• 위의 방식을 W가 NULL이 될때까지 반복(갱신된 priority와 기존 priority만을 비교)

만약 lock->holder가 NULL이라면

• sema_down을 한 후
• thread의 W을 NULL로 만들고, holder를 thread_curr로 바꿈.

Lock을 어떻게 해제하는가?

구현하는 코드는 짧지만 정확하게 구현해야 한다.

우선 Lock 해제를 알기 전에 한가지를 먼저 이해해야 한다.
그것은 Lock을 해제할때 어떤 상황이 발생하는가 이다.
그 과정은 다음과 같다.

1. Lock 하나가 해제가 된다.

2. th1의 donations의 d_elem 중 하나가 삭제가 된다.

3. donations의 원소가 변했음으로 priority 갱신이 필요하다.

4. donations의 제일 왼쪽 원소(donations의 원소 중 priority가 가장 큰 thread)의 priority와 th1의 origin_priority를 비교한다.

5. 그중 가장 큰 값으로 갱신하고, th1의 값이 갱신되었음으로 wait_on_lock -> holder 스레드(th1이 가리키는 스레드)의 값도 갱신해준다.

6. 하지만 priority의 값이 변하지 않거나, wait_on_lock이 NULL이면 갱신을 하지 않는다.

이 과정을 정확하게 lock_release에 적용시키면 multi , nest 구조를 작성한 것이기 때문에 모두 통과하게 된다.

lock_release

void lock_release(struct lock *lock) {
    ASSERT(lock != NULL);
    ASSERT(lock_held_by_current_thread(lock));
    struct thread *cur = lock->holder;

    if (!list_empty(&cur->donations)) {
        struct list_elem *e = list_begin(&cur->donations);
        while (e != list_end(&cur->donations)) {
            struct thread *t = list_entry(e, struct thread, d_elem);
            if (t->wait_on_lock == lock) {
                list_remove(e);
                t->wait_on_lock = NULL;
            }
            e = e->next;
        }
    }

    if (!list_empty(&cur->donations)) {
        struct thread *t = list_entry(list_front(&cur->donations), struct thread, d_elem);
        cur->priority = t->priority;
    } else {
        cur->priority = cur->origin_priority;
    }

    lock->holder = NULL;
    sema_up(&lock->semaphore);
}

만약 cur->donations에 d_elem이 있다면(!empty)

• list_begin부터 순회를 돌며 lock에 연결된 스레드를 모두 해제한다.

• cur->priority에 donations의 첫번째 thread의 priority를 대입한다.(donation을 한 thread는 전부 origin_priority보다 큰 값)

• 이후 lock->holder를 NULL로 만들고, sema_up을 한다.