2025.05.17

TIL(TODAY I LEARN)

---

• 오늘한 내용 : PintOS - Project1: Threads - mlfqs 구현 완료

• WEEK 09 : 정글 끝까지(PintOS) - Threads

---

참고한 블로그

[Pintos] Project 1 : Thread(스레드) - Advanced Scheduler (mlfqs)

4.4BSD Scheduler

컴파일 옵션

../thread/build

특정 테스트만 검사
pintos -v -- -mlfqs run <테스트이름>
ex) pintos -v -- -mlfqs run mlfqs-load-1

make check TEST="mlfqs-nice-10"

전체 검사
make check

mlfq(multilevel feedback queue) scheduler

• 여러 개의 ready queue 존재, 각 큐는 서로 다른 우선순위(priority level)를 가짐.
• 높은 우선순위 큐부터 먼저 검색 → 가장 높은 priority의 큐에서 첫 번째 스레드를 실행.
• 같은 큐에 여러 스레드가 있으면, Round Robin 방식으로 돌아가며 실행.
  • round robin - 스레드 간에 우선순위를 두지 않고, 순서대로 정해진 시간단위로 CPU 를 할당하는 방식. 시간단위만큼 실행된 스레드는 리스트의 맨 뒤로 이동.

우선순위 조정(feedback)

• CPU를 많이 사용하는 스레드는 시간이 지나면 우선순위가 낮아짐.
• 대기 위주의 스레드(예: I/O bound)는 우선순위가 올라감.
• Periodic priority boost: starvation 방지를 위해 모든 스레드의 priority를 주기적으로 초기화하거나 증가시킴.

MLFQ의 목적

• 인터랙티브한 프로세스에 우선순위 제공 (사용자 입력 기다리는 등)
• CPU-bound 작업은 점점 낮은 priority로 유도하여 시스템 전체 응답성을 높임

mlfqs에서 스레드 우선순위 계산

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

• time slice(4ticks)마다 우선순위가 재계산
• PRI_MAX는 우선순위의 최대값 (예: 63)
• recent_cpu: 스레드가 최근 사용한 CPU 시간
• nice: CPU를 양보하려는 성향
• priority는 정수 → 계산시 소수점은 버림

1. Niceness

• 각 스레드는 정수 nice 값을 가지며, 이는 스레드의 우선순위에 영향을 줌.
• nice가 클수록 양보를 잘함 → 우선순위가 낮음
  • nice < 0: 양보↓ → 우선순위 ↑
  • nice = 0: priority 수치 기본값
  • nice > 0: 양보↑ → 우선순위 ↓

2. Recent_cpu

recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

• 최근 사용한 CPU시간
• 오래사용되지 않은 스레드 일수록 우선순위를 높게(recent_cpu값이 작아짐.) → 모든 스레드들이 골고루 실행될 수 있게
• recent_cpu 클수록 우선순위 감소
• 지수가중 이동평균 방식을 이용해 최근 cpu 사용량에 더 큰 가중치를 부여

지수가중 이동평균 방식

(Exponetially Weigthed Moving Average)

• x(t) : t번째 데이터의 지수 가중 이동평균, recent_cpu 값

• a : 하이퍼 파라미터, 최적의 값을 대입해 사용, 부패율

  • Pintos에서의 a = k(k+1)

• f(t) : t번재 데이터 값, t 시간에서 사용한 cpu 양

• (2 * load_avg) / (2 * load_avg + 1) 부분을 부패율 a라고 보면 지수 가중 이동평균과 같음.

load_avg 계산

load_avg = (59/60)load_avg + (1/60)*ready_threads

• load_avg
  • 최근 1분동안 수행가능한(ready to run) 스레드의 평균 개수
  • 시스템의 평균적인 부하
• ready_thread : 현재 실행 중이거나 준비 상태인 스레드의 수

3. 고정 소수점 연산 (Fixed-Point Arithmetic)

• 부호, 정수부, 소수부
• Pintos는 부동 소수점 연산을 지원하지 않으므로, 고정 소수점 방식을 사용하여 실수를 표현합니다.
• 시프트 연산(1 << 14)
  • 2.75를 표현하려면 2.75 * 2^14 = 45056으로 계산하여 사용합니다

Arithmetic	C
Convert n to fixed point	n * f
Convert x to integer (rounding toward zero)	x / f
Convert x to integer (rounding to nearest)	(x + f / 2) / f if x >= 0
	(x - f / 2) / f if x <= 0
Add x and y	x + y
Subtract y from x	x - y
Add x and n	x + n * f
Subtract n from x	x - n * f
Multiply x by y	((int64_t) x) * y / f
Multiply x by n	x * n
Divide x by y	((int64_t) x) * f / y
Divide x by n	x / n

---

구현

• niceness, priority, recent_cpu: 각 스레드별로 존재하는 고유 값
• load_avg: 시스템에 하나의 값으로 존재
• niceness, priority: 정수값
• recent_cpu, load_avg: 실수값

수정한 함수

* thread.h
struct thread - nice, recent_cpu, allelem 변수 추가
-------------------------
* thread.c
int load_avg; - 전역 변수 추가
thread 구조체에 all_list 추가
init_thread() - 새로 추가한 변수 초기화 추가
fixed_point 계산을 위한 함수들 선언 및 추가
thread_set_nice() 작성
thread_get_nice() 작성
thread_get_laad_avg() 작성
thread_get_recent_cpu() 작성
-------------------------
* timer.c
timer_interrupt() - mlfqs 옵션일 때만 동작하게 및 틱당 계산 추가
-------------------------
* synch.c
기부 사용하지 않으므로
lock_acquire(), lock_release() 수정
thread_set_priority() 비활성화

성공!