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에 대해서는 저희 조의 다른 팀원들이 구현을 맡았는데, 마찬가지로 각자 정리한 내용들을 공유해 보려고 합니다.
'크래프톤 정글 > 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 |