PintOS Priority
PintOS에서의 우선순위는 쓰레드 스케줄링과 관련이 있습니다. 각 쓰레드는 특정 우선순위를 가지며, 높은 우선순위를 가진 쓰레드가 CPU를 더 많이 할당받게 됩니다. 이를 통해 우선순위가 높은 작업이 먼저 실행되고, 시스템의 응답성과 성능을 향상시킬 수 있습니다.
PintOS에서는 0부터 63까지의 우선순위 범위를 사용합니다. 낮은 숫자일수록 높은 우선순위를 의미합니다. 우선순위가 0인 Idle 쓰레드는 가장 낮은 우선순위를 가지며, 실행 가능한 쓰레드가 없을 때 CPU를 점유하게 됩니다.
PintOS의 우선순위는 기본적으로 선점형 스케줄러인 MLFQS(Multi-Level Feedback Queue Scheduler)에서 사용됩니다. 이 스케줄러는 각 쓰레드에 대한 우선순위를 동적으로 조정하며, CPU 사용 시간과 대기 시간 등을 고려하여 우선순위를 결정합니다. 쓰레드의 우선순위가 변경될 때마다 스케줄러는 이를 적용하여 적절한 쓰레드를 선택하여 CPU를 할당합니다.
PintOS에서 우선순위를 설정하려면 thread_set_priority() 함수를 사용할 수 있습니다. 이 함수를 통해 특정 쓰레드의 우선순위를 변경할 수 있습니다. 쓰레드의 우선순위를 변경하면 MLFQS 스케줄러가 이를 감지하여 스케줄링 결정에 반영합니다.
초심자가 PintOS의 우선순위를 이해하기 위해서는 스케줄링 알고리즘과 쓰레드 동작의 상호작용을 이해하는 것이 중요합니다. 우선순위가 어떻게 적용되고, 쓰레드가 어떻게 스케줄링되는지에 대한 개념을 학습하면 PintOS에서의 우선순위 개념을 이해하는 데 도움이 될 것입니다
구현
전체 코드는 올리지 못해서 이번에 공부하면서 중요하다고 생각되는 부분을 가져왔습니다.
void lock_acquire
void lock_acquire(struct lock *lock)
{
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(!lock_held_by_current_thread(lock));
struct thread *curr = thread_current();
if (lock->holder != NULL) // if the lock is available
{
struct thread *th = thread_current();
curr->wait_on_lock = lock;
if (curr->priority > lock->holder->origin_priority)
{
if (list_empty(&lock->semaphore.waiters)) // waiters의 값이 처음 입력되는경우
{
list_push_back(&lock->holder->donations, &curr->donation_elem); // add current thread into donation list.
}
else if (list_entry(list_front(&lock->semaphore.waiters), struct thread, elem)->priority < curr->priority) // 만약 새로 들어온 쓰레드값이 waiters의 가장 큰 값이면 도네이션도 업데이트
{
struct list_elem *e;
for (e = list_begin(&lock->holder->donations); e != list_end(&lock->holder->donations); e = list_next(e))
{
struct thread *t = list_entry(e, struct thread, donation_elem);
if (lock == t->wait_on_lock) // 받아온 락이 wait_on_lock일경우
{
list_remove(&t->donation_elem);
list_insert_ordered(&t->donations, &curr->donation_elem, donation_sort, NULL); // insert current thread in the donation list before the thread with lower priority
break;
}
}
}
donate_priority();
}
}
sema_down(&lock->semaphore);
lock->holder = curr;
curr->wait_on_lock = NULL;
}위의 코드는 lock_acquire 함수로, 락을 획득하기 위한 동작을 수행하는 함수입니다. 해당 함수는 다음과 같은 동작을 수행합니다:
-
먼저, 함수의 매개변수로 전달된 lock이 유효한지(NULL이 아닌지) 검사합니다. 그리고 인터럽트 컨텍스트에서 호출되지 않았는지, 현재 쓰레드가 해당 락을 이미 소유하고 있는지 확인하는 ASSERT 문들을 사용하여 검사합니다.
-
lock의 홀더(holder)가 NULL이 아닌 경우, 즉 락이 이미 소유되어 있는 경우입니다. 이 경우 현재 쓰레드는 해당 락을 기다리기 위해 wait_on_lock 변수를 설정합니다. 또한, 현재 쓰레드의 우선순위가 락을 소유한 쓰레드의 기본 우선순위보다 높은 경우, 우선순위 기부(Donation)가 발생합니다.
-
우선순위 기부가 필요한 경우를 처리하기 위해 다양한 조건을 확인합니다. 먼저, lock의 대기자(waiters) 리스트가 비어있는 경우는 처음 대기자가 등록된 경우입니다. 이 경우, 현재 쓰레드를 lock의 홀더의 기부(donations) 리스트에 추가합니다.
-
대기자 리스트에 이미 쓰레드가 존재하고, 현재 쓰레드의 우선순위가 대기자 리스트의 가장 높은 우선순위보다 높은 경우입니다. 이 경우, lock의 홀더의 기부(donations) 리스트를 순회하면서 wait_on_lock이 현재 lock인 쓰레드를 찾고, 해당 쓰레드의 기부(donation)를 제거한 뒤, 현재 쓰레드를 우선순위에 맞게 기부 리스트에 삽입합니다.
-
우선순위 기부가 발생한 후, donate_priority 함수를 호출하여 현재 쓰레드의 우선순위를 업데이트합니다.
-
마지막으로, sema_down 함수를 호출하여 lock의 세마포어를 획득합니다. 세마포어를 획득한 후, 현재 쓰레드를 lock의 홀더로 설정하고, wait_on_lock을 NULL로 초기화합니다.
이렇게 lock_acquire 함수는 락을 획득하기 위한 동작을 수행하며, 우선순위 기부 등의 로직을 사용하여 쓰레드의 우선순위를 조정합니다. 이를 통해 락의 확보 및 쓰레드 스케줄링에 우선순위 개념이 적용됩니다
PintOS Priority를 공부하면서 어려웠던 점은 elem에 대한 이해와 관련하여 생겼습니다. elem은 연결 리스트에서 노드를 구성하는 요소 중 하나로, 다른 노드와의 연결을 가능하게 해줍니다. 하지만 초기에는 elem이 어떤 역할을 하는지 이해하기 어려웠고, 노드와 elem 사이의 관계를 파악하는 데 시간이 걸렸습니다.
또한, PintOS Priority에서 우선순위 개념을 이해하고 그것을 적용하는 것도 어려웠습니다. 우선순위에 따라 쓰레드 스케줄링이 이루어지고, 락을 획득하는 동안 우선순위 기부가 발생하는 등 여러 개념과 로직이 함께 작용하다보니 한번에 이해하기 어려웠습니다.
이러한 어려움을 해결하기 위해 여러 번의 학습과 실험을 통해 개념을 천천히 익히고, 코드를 따라가며 디버깅해보는 등의 노력을 했습니다. 결국에는 elem의 역할과 우선순위 개념을 확실히 이해하고 코드를 이해할 수 있었습니다. 이러한 어려움을 겪으며 중요한 점은 한 번에 모든 것을 이해하려는 것보다 단계적으로 학습하고 실험하는 것이 좋다는 것을 깨달았습니다
