pintos project 1 threads

 Project 1: Threads - Pintos 스레드 구조부터 우선순위 스케줄링까지

Pintos Project 1에서는 스레드 관리와 스케줄링 정책을 구현하게 됩니다.
Alarm Clock을 통한 busy waiting 제거, 우선순위 기반 스케줄링 및 Nested Priority Donation 구현이 주요 목표입니다.

---

 1-1. Pintos 스레드 구조 이해

Pintos는 각 스레드를 struct thread로 표현합니다. 스레드의 메타 정보와 커널 스택이 1페이지에 함께 존재하며, 아래와 같은 필드들이 핵심입니다:

struct thread {
  tid_t tid;                         // 스레드 ID
  enum thread_status status;        // 상태 (RUNNING, READY 등)
  uint8_t *kernel_stack;            // 스택 포인터
  int priority;                     // 스레드 우선순위
  ...
};

스레드 메모리 구조는 다음과 같습니다:

4KB ----------------------------------
     |       kernel stack           |
     |-----------------------------|
     |       struct thread         |
0KB ----------------------------------

커널 스택은 위에서 아래로 성장하므로, stack overflow가 발생하면 struct thread를 덮어쓸 수 있습니다. 이를 방지하기 위해 ASSERT(is_thread(t)) 같은 검사가 들어갑니다.

---

 1-2. Alarm Clock 구현

timer_sleep()은 busy waiting을 제거하고, 스레드를 슬립 리스트에 넣어 대기하게 만드는 기능입니다.

• wakeup_tick: 깨어나야 할 tick 값을 각 스레드에 저장
• sleep_list: sleep 중인 스레드들을 저장하는 리스트
• timer_interrupt(): 매 tick 마다 리스트를 확인하고 깨어나야 할 스레드 깨움

void timer_sleep(int64_t ticks) {
  int64_t start = timer_ticks();
  thread_sleep_until(start + ticks);
}

핵심은 sleep list를 정렬하여 매 tick마다 전체 순회하지 않도록 최적화하는 것입니다.

---

 1-3. Priority Scheduling

Pintos 기본 스케줄러는 Round-Robin 방식이기 때문에, 이를 priority 기반 스케줄링으로 바꾸는 작업이 필요합니다. 이를 위해 다음과 같은 핵심 수정이 이루어집니다:

• 스레드가 priority 값을 가지도록 하고
• ready_list를 priority 기준으로 정렬
• 더 높은 priority를 가진 스레드가 생기면 즉시 선점 (preemption)

---

1. ready_list 정렬 기준 함수

bool priority_more(const struct list_elem *a, const struct list_elem *b, void *aux) {
  return thread_get_priority(list_entry(a, struct thread, elem)) >
         thread_get_priority(list_entry(b, struct thread, elem));
}

이 비교 함수는 ready_list, lock->waiters 등 스레드를 우선순위 기준으로 정렬할 때 사용됩니다.

---

2. thread_yield()에서 ready_list 정렬 삽입

void thread_yield(void) {
  struct thread *curr = thread_current();
  enum intr_level old_level;

  ASSERT(!intr_context());
  old_level = intr_disable();

  if (curr != idle_thread)
    list_insert_ordered(&ready_list, &curr->elem, priority_more, NULL);

  do_schedule(THREAD_READY);
  intr_set_level(old_level);
}

스레드가 CPU를 양보할 때, 단순히 list_push_back()으로 넣는 대신 우선순위 기준으로 삽입해야 합니다. 이 로직이 없다면 스레드의 priority를 구현해도 실행 순서가 보장되지 않아 테스트가 실패합니다.

---

3. thread_create()에서 우선순위 선점 (Preemption)

새로운 스레드를 생성한 직후, 해당 스레드의 우선순위가 현재 실행 중인 스레드보다 높다면 즉시 CPU를 양보해야 합니다. 이를 구현한 코드가 아래와 같습니다:

if (t->priority > curr->priority)
{
  thread_yield();
}

thread_create()의 마지막 부분에 추가되며, 현재 스레드가 CPU를 점유하고 있지만, 더 높은 우선순위의 스레드가 ready_list에 생겼다면 스스로 양보하도록 합니다.

이 선점 로직이 없으면 priority-preempt 테스트에서 실패하게 됩니다. 예를 들어 낮은 priority의 스레드가 thread_create()로 높은 priority 스레드를 만들고도 계속 실행되는 현상이 발생합니다.

---

 관련 테스트

• priority-preempt: 더 높은 우선순위 스레드가 생기면 즉시 CPU를 양보하는가?
• priority-change: 실행 중에 priority가 변경될 경우에도 정렬이 유지되는가?
• donate-multiple: 여러 스레드가 동시에 donation할 때, 올바른 priority 순서를 유지하는가?

위 테스트들은 모두 ready_list 정렬, thread_yield() 수정, thread_create() 선점 로직이 올바르게 작동해야 통과됩니다.

 요약

Priority Scheduling은 단순히 숫자 필드를 추가하는 것이 아니라, 스레드를 리스트에 넣고 꺼낼 때 모두 우선순위를 기준으로 정렬해야 작동합니다. 또한, 새로운 스레드가 만들어졌을 때 선점할 수 있도록 thread_create()에 선점 조건을 추가해야 진짜 우선순위 스케줄러가 됩니다.

 1-4. Priority Donation (Nested)

그림 설명

• 높은 우선순위 스레드(H)가 락을 요청할 때, 락을 보유한 낮은 우선순위 스레드(L)에게 자신의 우선순위를 일시적으로 "기부"함
• L의 우선순위가 일시적으로 H의 수준으로 상승
• 중간 우선순위 스레드(M)가 더 이상 L을 선점할 수 없게 됨
• L이 빠르게 작업을 마치고 락을 반환하면, 원래의 우선순위로 복귀
• H가 락을 획득하고 실행을 계속함

 

Priority Inversion 문제를 해결하기 위해, 낮은 우선순위 스레드가 lock을 보유했을 때, 높은 우선순위 스레드의 priority를 기부(donation)해야 합니다.

• lock->holder의 priority를 donate_priority()로 상향
• lock->waiters 정렬 유지
• Nested Donation: 최대 깊이 제한 (예: 8단계)
• lock release 시 priority 회수

void donate_priority(struct thread *t) {
  for (int depth = 0; depth < MAX_DEPTH; depth++) {
    if (t->wait_on_lock == NULL) break;
    ...
    t->wait_on_lock->holder->priority = max(t->priority, holder->priority);
    t = t->wait_on_lock->holder;
  }
}

기부를 받은 스레드는 lock을 release할 때 priority를 복구해야 하며, 이를 위해 original_priority 필드가 필요합니다.

---

 1-5. 테스트 전략 및 디버깅 예시

다음 테스트들은 이 기능들이 올바르게 동작하는지를 확인합니다:

• priority-donate-one: 단일 기부가 제대로 작동하는가?
• priority-donate-nest: nested donation 2단계 이상 처리 가능한가?
• priority-donate-multiple: 여러 스레드가 하나의 스레드에 동시에 기부할 때

🔍 디버깅 팁

• printf("donating from %d to %d\n", a->priority, b->priority);로 donation 로그 출력
• ASSERT(is_thread(t)) 실패 시 스택 오염 의심
• bt 명령어로 GDB에서 backtrace 확인

---

 마무리

Project 1은 스레드의 생성, 정렬, 상태 전이, lock을 통한 동기화까지 운영체제 스케줄링의 기본을 모두 담고 있습니다. 각 단계마다 디버깅을 철저히 하며, 스레드의 상태 변화, ready_list의 정렬 상태, lock 보유 여부를 주의 깊게 관찰해야 합니다.

다음 편에서는 Project 2: System Call과 사용자 프로세스를 정리할 예정입니다.