[Pintos] Threads: Priority Scheduling - 동기화 Primitive 단계별로 수정하기

2025. 5. 11. 22:57·크래프톤 정글/Code 정글(C언어)

Thread: Priority Scheduling - 동기화 Primitive 단계별로 수정하기

이번 구현의 핵심 목표는 기존 PintOS의 FIFO 기반 스케줄링 방식을 스레드 우선순위 기반 스케줄링으로 전환하는 것입니다. 이러한 변화는 단순히 ready list만 수정하는 데 그치지 않고, 동기화 관련 primitive(단순 메커니즘)인 세마포어, 락, 조건 변수에도 동일하게 반영되어야 의미가 있는데요. 이번 글에서는 동기화 객체에 우선순위 기반 스케줄링을 적용하는 과정을 단계별로 정리해봅니다.

 

주요 목표

  • 기본 FIFO 스케줄링을 우선순위 기반 방식으로 개선
  • 특히, sema_down, sema_up, cond_wait, cond_signal 등 동기화 primitive 함수들에 우선순위 반영
  • priority donation 등 고급 개념을 이해하고 이를 위한 구조체 설계를 선행

 

학습 키워드

  • ready_list 정렬: FIFO → priority 기반
  • 선점 시점: thread unblock 시에만 선점 여부 판단
  • waiters 정렬: 모든 동기화 객체의 waiters 리스트를 우선순위 정렬로 유지
  • priority inversion 해결: priority donation 설계 및 구현 준비
  • thread 구조체 확장: wait_on_lock, donations 리스트 등

 

(참고) 수정 파일

  • threads/synch.c
  • threads/synch.h

 

동기화 Primitive 단계별로 수정하기

1단계: 문제 정의하기

  • 기존 구조는 list_push_back()과 list_pop_front()를 사용해 FIFO 방식으로 자원 대기 스레드를 관리
  • 이로 인해 우선순위가 높은 스레드가 오히려 자원을 기다리는 상황(Priority Inversion) 발생
  • 해결 방안: 모든 waiters 리스트를 priority 기준으로 정렬된 상태로 유지
대상 함수 수정 요약
sema_down() waiters에 list_insert_ordered() + cmp_priority()
sema_up() list_sort() 후 list_pop_front() → thread_unblock()
cond_wait() 내부 semaphore_elem을 cmp_sema_priority 기준 삽입
cond_signal() 우선순위 가장 높은 semaphore_elem을 깨우도록 pop

 

 

2단계: 구조 설계 및 흐름 정리

기존 waiters 리스트 구조

  • 삽입: list_push_back()
  • 제거: list_pop_front()
    → 둘 모두 FIFO 구조로, 우선순위를 전혀 고려하지 않음

 

목표 구조

  • 삽입: list_insert_ordered()
  • 비교자: cmp_priority() 또는 cmp_sema_priority()
  • 제거: list_pop_front()
    → 항상 우선순위가 가장 높은 스레드가 먼저 깨어나게 됨

 

3단계: 함수 단위 설계 및 구현하기

(1) cmp_sema_priority() 함수 추가

semaphore_elem 구조체의 우선순위를 비교하여 정렬 시 높은 우선순위가 먼저 오도록 하기 위한 비교 함수입니다.

  • cond->waiters를 정렬하기 위해 사용
  • semaphore_elem에 priority 필드 추가 필요
  • cond_wait 내부에서 thread_get_priority()를 이 필드에 저장
/* 
 * cmp_sema_priority:
 * 두 개의 리스트 요소 a, b를 받아 각각을 semaphore_elem 구조체로 변환한 뒤,
 * 그 안의 priority 값을 비교하여 a가 b보다 우선순위가 높으면 true를 반환합니다.
 * 이 함수는 리스트를 우선순위 기준으로 내림차순(높은 우선순위 먼저) 정렬할 때 사용됩니다.
 */
bool cmp_sema_priority(const struct list_elem *a,
                       const struct list_elem *b, void *aux UNUSED)
{
    // 리스트 요소 a, b를 semaphore_elem 구조체로 캐스팅
    struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

    // priority 값을 비교하여 a가 더 크면 true (내림차순 정렬)
    return sa->priority > sb->priority;
}

 

(2) sema_down() 함수 수정

세마포어 값을 검사하여 0이면 현재 스레드를 대기열에 우선순위 정렬로 삽입하고 차단(block)하며, 세마포어가 사용 가능할 때 자원을 획득하도록 하는 함수입니다.

  • waiters에 삽입 시 priority 기준 정렬 유지
/*
 * sema_down:
 * 세마포어의 값을 감소시키며 자원을 획득합니다.
 * 만약 세마포어 값이 0이라면, 자원이 사용 중이므로
 * 현재 스레드를 대기열(sema->waiters)에 우선순위 기준으로 정렬하여 삽입하고
 * 해당 스레드를 block 상태로 만듭니다.
 * 자원이 사용 가능해지면(sema->value > 0) 스레드는 깨어나고, 세마포어 값을 1 감소시켜 자원을 차지합니다.
 */
void sema_down(struct semaphore *sema)
{
    enum intr_level old_level;

    ASSERT(sema != NULL);

    // 인터럽트를 비활성화하여 동시 접근으로 인한 문제를 방지
    old_level = intr_disable();

    // 세마포어 값이 0이면 자원이 사용 중이므로 대기
    while (sema->value == 0)
    {
        /* 현재 스레드를 세마포어 대기 리스트에 삽입
           우선순위가 높은 스레드가 앞에 오도록 cmp_priority 사용 */
        list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL);

        // 현재 스레드를 block 상태로 전환하여 CPU에서 제외
        thread_block();
    }

    // 자원이 확보되었으므로 세마포어 값을 1 감소시킴
    sema->value--;

    // 인터럽트를 이전 상태로 복원
    intr_set_level(old_level);
}

 

(3) sema_up() 함수 수정

세마포어 값을 증가시키고, 대기 중인 스레드가 있다면 우선순위가 가장 높은 스레드를 깨워 실행 가능 상태로 만듭니다.

/*
 * sema_up:
 * 세마포어 값을 증가시켜 자원을 반환합니다.
 * 만약 대기 중인 스레드가 있다면, 우선순위가 가장 높은 스레드를 선택하여
 * 실행 가능 상태로 만듭니다 (unblock).
 * 이후 우선순위 선점을 고려해 현재 스레드가 CPU를 양보할지 판단합니다.
 */
void sema_up(struct semaphore *sema)
{
    enum intr_level old_level;

    ASSERT(sema != NULL);

    // 인터럽트를 비활성화하여 동시성 문제 방지
    old_level = intr_disable();

    // 대기 중인 스레드가 있다면
    if (!list_empty(&sema->waiters))
    {
        // waiters 리스트를 우선순위 기준으로 정렬
        list_sort(&sema->waiters, cmp_priority, NULL);

        // 가장 우선순위가 높은 스레드를 꺼냄
        struct thread *t = list_entry(list_pop_front(&sema->waiters),
                                      struct thread, elem);

        // 해당 스레드를 실행 가능 상태로 전환
        thread_unblock(t);
    }

    // 세마포어 값을 증가시켜 자원 반환
    sema->value++;

    // 인터럽트 상태 복원
    intr_set_level(old_level);

    // 더 높은 우선순위의 스레드가 있다면 현재 스레드를 선점할 수 있도록 확인
    preempt_priority();  // interrupt off 상태에서 호출 후 선점 가능
}

 

(4) cond_wait() 함수 수정

조건 변수 대기열에 현재 스레드를 우선순위 기준으로 추가하고, 락을 잠시 해제한 뒤 조건이 만족될 때까지 대기하며, 신호를 받으면 락을 다시 획득합니다.

  • semaphore_elem 구조체에 priority 저장 → cmp_sema_priority()로 정렬
/*
 * cond_wait:
 * 조건 변수를 이용해 현재 스레드를 대기(wait) 상태로 전환합니다.
 * 먼저 semaphore_elem 구조체를 생성하여 현재 스레드의 우선순위를 저장하고,
 * 조건 변수의 대기 리스트(cond->waiters)에 우선순위 기준으로 삽입합니다.
 * 그 다음 락을 잠시 해제하고(sema_down에서 block 대기할 것이기 때문),
 * 세마포어를 통해 신호를 받을 때까지 대기합니다.
 * 신호를 받아 깨어나면 다시 락을 획득하고 임계구역 진입을 시도합니다.
 */
void cond_wait(struct condition *cond, struct lock *lock)
{
    struct semaphore_elem waiter;

    // 현재 스레드의 우선순위를 저장 (우선순위 기반 정렬을 위해)
    waiter.priority = thread_get_priority();

    // 해당 세마포어를 0으로 초기화하여 sema_down() 시 block 되도록 함
    sema_init(&waiter.semaphore, 0);

    // 조건 변수 대기 리스트에 우선순위 기준으로 삽입
    list_insert_ordered(&cond->waiters, &waiter.elem, cmp_sema_priority, NULL);

    // 락을 해제하여 다른 스레드가 자원을 사용할 수 있도록 함
    lock_release(lock);

    // 세마포어가 올라갈(sema_up) 때까지 대기
    sema_down(&waiter.semaphore);

    // 깨어난 후 락을 다시 획득
    lock_acquire(lock);
}

 

(5) cond_signal() 함수 수정

조건 변수 대기열 중 가장 높은 우선순위의 스레드 하나를 선택해 세마포어를 통해 깨워줍니다.

  • 조건 만족 시, waiters 리스트에서 우선순위 가장 높은 스레드를 깨움
/*
 * cond_signal:
 * 조건 변수(cond)의 대기 리스트에서 가장 우선순위가 높은 스레드 하나를 깨웁니다.
 * 이를 위해 먼저 대기 리스트를 우선순위 기준으로 정렬한 후,
 * 가장 앞에 있는 세마포어를 찾아 sema_up()을 호출하여 대기 중인 스레드를 unblock 상태로 만듭니다.
 * 이 함수는 반드시 락을 소유한 상태에서 호출되어야 하며, 대기 중인 스레드가 없다면 아무 작업도 하지 않습니다.
 */
void cond_signal(struct condition *cond, struct lock *lock UNUSED)
{
    // 조건 변수와 락이 유효한 상태인지 확인
    ASSERT(cond != NULL);
    ASSERT(!intr_context());                    // 인터럽트 컨텍스트에서는 호출 불가
    ASSERT(lock_held_by_current_thread(lock));  // 현재 스레드가 락을 가지고 있어야 함

    // 대기 중인 스레드가 있다면
    if (!list_empty(&cond->waiters))
    {
        // 우선순위 기준으로 조건 변수 대기 리스트를 정렬
        list_sort(&cond->waiters, cmp_sema_priority, NULL);

        // 가장 높은 우선순위의 세마포어를 꺼내고 해당 스레드를 깨움
        sema_up(&list_entry(list_pop_front(&cond->waiters),
                            struct semaphore_elem, elem)->semaphore);
    }
}

 

디버깅 포인트

처음엔 list_max()로 가장 높은 우선순위의 스레드를 가져오려 했지만 테스트 실패가 반복됐었는데요. 이 현상이 왜 발생했는지, 그리고 어떻게 해결했는지를 정리해보았습니다.

  • 원인
    • list_max()는 내부적으로 less(a, b), 즉 a < b 형식의 비교자를 기대 → a > b 비교자인 cmp_priority() 사용 시 최솟값이 선택되는 구조적 오류 발생.
  • 해결
    • list_sort() 후 list_pop_front() 방식으로 변경 → 정확한 우선순위 선별 가능 → 모든 테스트 통과

 

마치면서

이번 구현을 통해 스레드 우선순위 기반 스케줄링을 동기화 객체 수준까지 확장할 수 있었는데요. 이는 향후에 다른 팀원이 맡은  Priority Donation 및 Nested Donation 구현의 기초가 되며, 전체 스케줄링 흐름의 일관성을 보장하게 만들어줍니다. 테스트의 경우 동기화 primitive 수정까지 완료되었다면, priority-sema와 priority-condvar 테스트를 추가적으로 통과할 수 있습니다.

 

참고로 현재 보고 있는 글은 'Priority Scheduling Part 2 - 동기화 프리미티브 수정 (Semaphore, Lock, Condition Variable)'에 관한 내용입니다. 나머지 Part에 대해서는 저희 조의 다른 팀원들이 구현을 맡았는데, 마찬가지로 각자 정리한 내용들을 공유해 보려고 합니다.

  • (박은범 학우) Priority Scheduling Part 1: 기본 스케줄링 로직 (Ready List 처리 및 Preemption) 구현
  • (임준혁 학우) Priority Scheduling Part3: Priority Donation (Nested 포함) 구현
저작자표시 비영리 변경금지 (새창열림)

'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글

[Pintos] 단일 테스트 실행하기  (0) 2025.05.13
[Pintos] Threads: Advanced Scheduler - 큰 그림 그리기 및 공유 템플릿 만들기  (1) 2025.05.12
[Pintos] Pintos 학습 프로세스 ver1.0  (0) 2025.05.10
[Pintos] Threads: Alarm Clock 단계별 구현 및 테스트하기  (0) 2025.05.09
[Pintos] Pintos를 시작하면서 - 협업에 대한 고민, AI의 활용 범위  (0) 2025.05.09
'크래프톤 정글/Code 정글(C언어)' 카테고리의 다른 글
  • [Pintos] 단일 테스트 실행하기
  • [Pintos] Threads: Advanced Scheduler - 큰 그림 그리기 및 공유 템플릿 만들기
  • [Pintos] Pintos 학습 프로세스 ver1.0
  • [Pintos] Threads: Alarm Clock 단계별 구현 및 테스트하기
그냥사람_
그냥사람_
IT 관련 포스팅을 합니다. 크래프톤 정글 8기 정경호
  • 그냥사람_
    그냥코딩
    그냥사람_
  • 전체
    오늘
    어제
    • 글 전체보기 N
      • 크래프톤 정글 N
        • 로드 투 정글(입학시험)
        • CS기초(키워드, 개념정리)
        • 컴퓨터구조(CSAPP)
        • Code 정글(C언어)
        • Equipped in 정글(나만무) N
        • 마이 정글(WIL, 에세이)
      • 자료구조&알고리즘
        • 자료구조
        • 알고리즘
      • 일상
  • 블로그 메뉴

    • 홈
  • 링크

    • Github
  • hELLO· Designed By정상우.v4.10.3
그냥사람_
[Pintos] Threads: Priority Scheduling - 동기화 Primitive 단계별로 수정하기
상단으로

티스토리툴바