[Pintos] Threads: Advanced Scheduler - 큰 그림 그리기 및 공유 템플릿 만들기

Thread: Advanced Scheduler - 큰 그림 그리기 및 공유 템플릿 만들기

이번 MLFQS 구현부터는 팀원들과 함께 Pintos 학습 프로세스를 적용하여 프로젝트를 진행을 시작하게 되었습니다. 준비 세션을 가지기 전, 팀원 각자가 해당 카테고리에 대해 사전 분석을 하는 시간을 가졌는데요.

 

먼저 해당 카테고리에 들어가면서 도대체 뭐가 문제이고, 이걸 왜 해결해야 하는지에 대한 문제 정의부터 시작했습니다. 그리고 이를 해결하면서 얻을 수 있는 학습 목적은 무엇인지, 그리고 해결해야 할 문제들을 대략적으로 어떻게 해결해야 할지에 대해 알아보았습니다. 뿐만 아니라 현재 pintos는 어떤 방식으로 동작하고 있고 그 부분들이 이제는 어떤 흐름으로 바뀌어야 하는지에 대해서도 찾아보고, 테스트 파일도 각자 나눠 분석해 보며 구현 이후의 pintos가 어떻게 동작해야 하는지도 예상해 보았습니다.

 

이러한 일련의 사전 분석을 각자 마친 뒤, 함께 모여 전체적인 큰 그림을 그리는 준비 세션을 가졌습니다. 그리고 최종적으로 추가·수정되어야 할 함수나 공통 인터페이스가 모두 반영된 공유 템플릿을 만들고 각자 작업을 분담한 뒤 작업에 착수했는데요. 이러한 과정을 통해 팀원들 모두가 해당 카테고리에 대한 문제 정의 및 작업 이해도를 높일 수 있었고, 모두의 합의 끝에 만들어진 공유 템플릿을 통해 작업을 시작하게 되면서 훨씬 효율적인 업무 분담 및 작업 진행을 기대하게 되었습니다. 이번 글에서는 해당 준비 세션을 진행하면서 이번에 구현할 카테고리인 MLFQS에 대해 정리한 내용을 공유해드리고자 합니다.

 

 

문제 정의 및 전체 흐름 파악

문제 정의

현재 Pintos는 고정 우선순위 기반의 스케줄러(Round-Robin + Priority Scheduling)을 사용 중인데, 이 방식은 다음과 같은 문제를 야기합니다.

• 우선순위가 높은 스레드들이 계속해서 CPU를 점유할 수 있음
  • 우선순위가 낮은 스레드의 starvation 문제 발생
• CPU 사용 시간을 공평하게 분배하는 것은 현실적으로 공평한 분배가 아님
  • CPU-bound(CPU 작업이 많은) 스레드는 부족한 시간을 받게 되어 병목이 발생
  • 반대로 I/O-bound(입출력 대기가 많고 CPU 작업이 적은) 스레드에는 필요 이상으로 할당되어 낭비가 발생
• 사용자가 thread_set_priority()로 우선순위를 직접 일일이 조정해야 함
  • 동적 스케줄링의 부재
• 시스템 전체의 부하 상태(load)를 반영하지 않음
  • 자원 분배가 현실을 반영하지 못해 비효율적이고 불공정한 스케줄링이 발생

 

학습 목적

• 우선순위 자동 조정 시스템 구현 경험
• 기아(starvation) 문제를 방지하는 설계 학습
• 정량적 시스템 상태를 반영한 스케줄링 (load_avg, recent_cpu)
• 고정소수점 연산을 통한 실수 연산 시뮬레이션
• tick-based update 전략과 인터럽트 처리 흐름 설계

핵심 목적은 스케줄러가 '공정성'을 어떻게 실현할 수 있는가에 대한 고민을 해보는 것.

 

대략적인 해결 흐름

아래 일련의 과정은 기본적인 MLFQS에 대한 핵심 내용에 대한 학습을 끝낸 상태에서 보는 것을 전제로 합니다.

• 필드 및 초기 구조 설계
  • thread 구조체에 nice, recent_cpu 추가
  • load_avg 전역 변수 선언 및 초기화
  • fixed-point.h 활용
• tick 기반 갱신 구현
  • 매 tick마다 현재 실행 중인 스레드의 recent_cpu++
  • 매 1초마다
    • load_avg 갱신
    • 모든 스레드의 recent_cpu 갱신
  • 매 4tick마다
    • 모든 스레드의 priority 재계산
• 정렬 기반 큐 유지
  • ready_list는 priority 기준 정렬
  • 이제 thread_set_priority()는 무시됨
  • thread_create(), thread_unblock(), thread_yield() 등에서 priority 재계산 후 이를 정렬에 반영

 

현재 상태 분석

현재 Pintos의 기본 스케줄러 동작 (Priority Scheduling 구현 직후)

• Round-Robin + 정적 우선순위 기반 스케줄링
• 우선순위는 thread_set_priority()로 수동 설정
• ready_list는 우선순위 기준으로 정렬
• recent_cpu, nice, load_avg 등의 개념 없음

바뀌어야 할 부분

• thread.c에 있는 우선순위 관련 필드를 계산 기반으로 변경해야 함
  • thread_get_priority()는 계산식 기반으로 변경
• 모든 스레드의 우선순위를 주기적으로 갱신하는 로직 추가 (tick interrupt 활용)
• 기존 priority set 함수는 MLFQS 모드에서는 무시
• 고정소수점을 통해 load_avg 및 recent_cpu 관련 계산 정확도 확보

 

공유 템플릿 만들기

thread.h 파일 수정

(1) 필드 추가 (구현 필요)

int nice;                // 기본값 0, 사용자 설정 가능
fixed_t recent_cpu;      // 고정소수점으로 표현된 최근 CPU 사용량

(2) 기존 함수 시그니처 유지 (구현 필요)

// 현재 실행 중인 스레드의 nice 값을 설정 (우선순위에 영향)
void thread_set_nice (int nice);

// 현재 실행 중인 스레드의 nice 값을 반환
int thread_get_nice (void);

// 현재 실행 중인 스레드의 recent_cpu 값을 반환 (고정소수점으로 계산됨)
int thread_get_recent_cpu (void);

// 현재 시스템의 load_avg 값을 반환 (고정소수점으로 계산됨)
int thread_get_load_avg (void);

이미 파일에 thread_mlfqs 플래그가 있으므로, 이를 기반으로 분기 처리 필요 (thread_set_priority 무시 등)

 

thread.c 파일 수정

(1) 전역 변수 추가

static fixed_t load_avg;	// 부하 평균

(2) 추가 구현이 필요한 함수

• thread_set_nice(), thread_get_nice()
• thread_get_recent_cpu(), thread_get_load_avg()
• init_thread()에 nice, recent_cpu 초기화 추가 필요
• thread_tick() → mlfqs_on_tick() 호출 추가 고려
• thread_create()에서 초기 recent_cpu, nice 설정 필요 (부모로부터 상속)

(3) 추가해야 할 함수

// 시스템 평균 부하(load_avg)를 매 1초마다 갱신
static void update_load_avg(void);

// 해당 스레드의 recent_cpu 값을 갱신
static void update_recent_cpu(struct thread *t);

// 모든 스레드의 recent_cpu 값을 갱신 (1초마다 호출)
static void update_all_recent_cpu(void);

// 해당 스레드의 priority 값을 recent_cpu 및 nice 값 기반으로 갱신
static void update_priority(struct thread *t);

// 모든 스레드의 priority 값을 갱신 (4tick마다 호출)
static void update_all_priority(void);

// timer tick마다 호출되어 MLFQS 관련 주기적 업데이트 수행
void mlfqs_on_tick(void);

thread_yield()나 thread_unblock() 등의 동작 흐름에 priority 변화가 반영되도록 정렬 유지 로직 추가 필요

 

fixed-point.h 파일 추가

17.14 고정소수점 연산 함수 구현 필요

// fixed-point.h
#ifndef THREADS_FIXED_POINT_H
#define THREADS_FIXED_POINT_H

typedef int fixed_t;

#define F (1 << 14)

// 변환 함수
fixed_t int_to_fixed(int n);
int fixed_to_int(fixed_t x);
int fixed_to_int_round(fixed_t x);

// 연산 함수
fixed_t add_fixed(fixed_t x, fixed_t y);
fixed_t sub_fixed(fixed_t x, fixed_t y);
fixed_t mul_fixed(fixed_t x, fixed_t y);
fixed_t div_fixed(fixed_t x, fixed_t y);

fixed_t fixed_mul_int(fixed_t x, int n);
fixed_t fixed_div_int(fixed_t x, int n);

#endif

 

timer.c 파일 수정

timer_interrupt() 내부에 다음을 추가

if (thread_mlfqs)
    mlfqs_on_tick();	// mlfqs 중앙 제어 함수 (thread.c)

 

synch.c 파일 수정

MLFQS 활성화 시 donation이 동작하면 안 됨

• lock_acquire()나 lock_release() 등에서 if (thread_mlfqs)로 donation 관련 코드 비활성화 필요

 

전체 작업 요약 

작업 내용	위치
nice, recent_cpu 필드 추가	thread.h
fixed-point 연산 구현	fixed-point.h
mlfqs_on_tick 및 관련 계산 함수	thread.c
thread_set_nice, thread_get_recent_cpu, 등 구현	thread.c
thread_set_priority() 무효화	thread.c
init_thread() 초기화 추가	thread.c
thread_create()에 필드 상속 추가	thread.c
timer_interrupt()에서 호출 연결	timer.c
donation 관련 코드 비활성화	synch.c

 

역할 분담

팀원1 (초기화 / 스레드 구조 / 전반 흐름)

• nice, recent_cpu 필드 추가
• init_thread()에서 초기화
• thread_create()에서 상속
• mlfqs_on_tick()을 thread_tick()에 연결
• thread_set_priority() 등에서 분기 무효화

구조체 및 초기 상태, 흐름 연결을 담당

 

팀원2 (계산 및 tick 흐름)

• update_load_avg()
• update_recent_cpu(), update_all_recent_cpu()
• update_priority(), update_all_priority()
• mlfqs_on_tick() 전체 통합 흐름

계산식 및 주기적 업데이트 등 핵심 로직 담당

 

팀원3 (인터페이스 / 외부연결 / donation 제거)

• thread_set_nice(), thread_get_nice()
• thread_get_load_avg(), thread_get_recent_cpu()
• synch.c에서 thread_mlfqs 분기 및 donation 코드 비활성화

사용자 함수 및 외부 접근, 동기화와의 연결 담당

 

 

마치면서

이번에 처음 준비 세션을 진행해보면서, 잘된 점도 있었고 아쉬운 점도 있었는데요. 이를 바탕으로 프로세스를 점차 발전시켜 나가보려 합니다. 저는 이번에 팀원2에 배정되어 계산식 및 주기적 업데이트를 해주는 핵심 로직을 담당하게 되었기에, 구현을 마친 뒤에 정리하는 글로 다시 한 번 찾아뵙겠습니다. 감사합니다.