[Pintos 개발일지] [pass] priority-donate-nest

priority-donate-nest 테스트 케이스를 통과했다.

나머지도... 테스트 케이스 분석하면서 다 패스해보자.

Nested priority donation 문제를 최종적으로 다음과 같이 해결했다.

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

    struct thread* pCurThread = thread_current ();

    priority_donation (lock);

    pCurThread->hurdle = lock;
    sema_down (&lock->semaphore);
    pCurThread->hurdle = NULL;

    lock->holder = pCurThread;
    list_insert_ordered (&pCurThread->lock_list, &lock->elem, custom_less, NULL);

    // lock is will have one
    // list_push_back (&pCurThread->lock_list, &lock->elem);
}

우선 기본적인 것들을 설명하겠다.

- Thread의 hurdle을 설명하자면, 락을 선점하려 하는 상태인데 이미 락의 주인이 있는 경우, 그 스레드는 중단되므로 허들에 걸렸다 해서 허들로 지었다. 그래서 어떤 스레드가 hurdle이 NULL이 아니라면 그 스레드는 현재 그 락에 의해(주인이 이미 있어서) 중단된 상태를 의미한다.

- holder는 락의 주인을 뜻한다. 락을 거는 데에 성공하면 그 락의 holder에 주인이 누구인지에 대한 정보가 들어간다.

- 세마포어에는 waiters라는 게 있는데, 락의 주인이 이미 있을 경우 이 waiters라는 양방향 링크드 리스트에 우선 순위별로 저장되고 block된다.

- Thread의 lock_list는, 현재 스레드가 선점한 락의 목록인데, 현재 스레드가 락을 선점하면 우선 순위별로 락들을 저장한다. 우선 순위가 높을수록 가장 최근에 선점한 락이다.

static void 
priority_donation (struct lock* lock)
{
    struct thread* pCurThread = thread_current ();
    struct thread* pHostThread = lock->holder;
    
    if (lock == NULL)
	return;
    if (pHostThread == NULL)
	return;
    if (pCurThread->priority <= pHostThread->priority)
	return;

    pHostThread->priority = pCurThread->priority;
    if (pHostThread->hurdle != NULL) 
    {
	priority_donation (pHostThread->hurdle);
    }
}

Priority Donation을 수행하는 함수이다. 당연히 현재 스레드가 우선 순위가 더 크지 않다면 donation을 할 필요가 없다. 그게 아니라면 바로 락의 주인스레드의 우선순위 바꾸고, 걔가 또 락에 걸려서 진행이 안되고 있으면 그 락의 주인도 찾아가서 우선 순위를 바꿔야 하므로 재귀함수로 이렇게 구현했다.

static void
lock_reset_donation (struct lock* lock)
{
    struct thread* pCurThread = thread_current ();

    if (list_empty (&lock->semaphore.waiters))
    {
	return;
    }

    struct thread* pHighThread = list_entry (list_front (&lock->semaphore.waiters), struct thread, elem);
    if (pCurThread->priority != pHighThread->priority)
	return;

    if (list_empty (&pCurThread->lock_list))
    {
	// pCurThread->priority = pCurThread->priority_origin;
	return;
    }
    
    struct lock* lock_high = list_entry (list_front (&pCurThread->lock_list), struct lock, elem);
    if (lock_high != NULL)
    {
	if (list_empty (&lock_high->semaphore.waiters))
	{
	    pCurThread->priority = pCurThread->priority_origin;
	}
	else
	{
	    struct thread* pThread_wait_highest = list_entry (list_front (&lock_high->semaphore.waiters), struct thread, elem);
	    if (pThread_wait_highest->priority > pCurThread->priority_origin)
	    {
		pCurThread->priority = pThread_wait_highest->priority;
	    }
	}
    }
}

- 이 락을 선점하기 위해 대기하고 있는 스레드들 중 Priority가 가장 높은 것과 현재 스레드의 Priority가 다르다면, 이는 그 스레드에서 Donation되지 않은 것이므로 바로 종료한다.

- lock list가 비었으면 선점한 락이 없는데 release를 하려는 것이므로 종료한다.

- lock list에서 가장 앞에 있는(우선 순위가 높은->가장 최근에 선점한) 락을 뽑아서 lock_high에 저장한다. 그리고 만약 이 락을 선점하기 원하는 스레드들 중 가장 우선 순위가 높은 놈의 우선 순위와 현재 스레드의 원래 우선 순위를 비교해서 현재 스레드의 우선 순위가 더 작다면 현재 스레드의 우선 순위를 그 스레드의 우선 순위로 변경한다. 그래야 이번 락 이전의 Priority가 어땠는지 알 수 있고 그것으로 되돌릴 수 있기 때문이다.

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

    list_remove (&lock->elem);
    lock_reset_donation (lock);

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