MLFQS 활성화 조건
•
Pintos 실행 시 -mlfqs 옵션으로 활성화됨
•
thread_mlfqs가 true일 때 MLFQS 사용
•
이때 priority donation은 사용하지 않음
•
따라서 thread_set_priority()와 thread_get_priority()는 무시되거나, 현재 계산된 우선순위를 리턴해야 함
스케줄링 기본 원리
•
우선순위 기반: 항상 가장 높은 priority의 큐에서 스레드를 실행
•
같은 priority의 스레드들은 라운드 로빈(RR)으로 실행
•
priority donation 없음
스레드가 가지는 추가 속성
•
int nice: -20 ~ 20, 기본값은 0. 부모 스레드로부터 상속.
•
fixed_point recent_cpu: 스레드가 최근에 얼마나 CPU를 사용했는지 나타내는 값.
아무래도 아래 값은 스레드 구조체에 포함되는 속성이 아니라 시스템 전체에 대해 사용하는 값이다보니 전역 변수로 두는 듯 하다.
•
fixed_point load_avg: 시스템 전체의 평균 ready thread 수
Priority 계산(
️)
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
C
복사
•
priority 범위: [PRI_MIN=0, PRI_MAX=63]
•
4 tick마다 모든 스레드에 대해 재계산.
•
priority를 업데이트한 후, 현재 실행 중인 스레드가 더 이상 최고 우선순위가 아니면 yield() 필요.
recent_cpu 계산
•
매 tick마다 실행 중인 스레드의 recent_cpu += 1
(idle thread 제외)
•
매 1초마다 모든 스레드에 대해:
recent_cpu = (2*load_avg) / (2*load_avg + 1) * recent_cpu + nice
C
복사
load_avg 계산
•
시스템 부팅 시 0으로 초기화.
•
매 1초마다:
load_avg = (59/60) * load_avg + (1/60) * ready_threads
C
복사
ready_threads: ready 상태 또는 running 상태의 스레드 개수 (idle thread 제외)
Fixed-Point 연산 (부동소수점 대신 사용)
•
17.14 고정 소수점 방식 사용 (f = 1 << 14).
•
변환 / 연산 방법 요약:
◦
정수 → 고정소수: n * f
◦
고정소수 → 정수(내림): x / f
◦
고정소수 → 정수(반올림): (x + f/2) / f
◦
덧셈/뺄셈: 그대로 사용
◦
고정 × 정수: x * n
◦
고정 ÷ 정수: x / n
◦
고정 × 고정: ((int64_t)x) * y / f
◦
고정 ÷ 고정: ((int64_t)x) * f / y
구현해야 할 함수들 :
•
int thread_get_nice (void)
→ 현재 스레드의 nice 리턴
•
void thread_set_nice (int nice)
→ nice 업데이트 + priority 재계산, 필요 시 yield
•
int thread_get_recent_cpu (void)
→ recent_cpu * 100 반올림하여 리턴
•
int thread_get_load_avg (void)
→ load_avg * 100 반올림하여 리턴
요약
1.
스레드에 nice, recent_cpu 값 유지
2.
매 tick마다 recent_cpu 증가
3.
매 1초마다 모든 스레드의 recent_cpu, load_avg 재계산
4.
매 4 tick마다 priority 재계산
5.
고정 소수점 연산을 잘 구현해서 정확한 계산하기