[PintOS 1주차] Bonus: Advanced Scheduler

커리큘럼에서 Advanced Scheduler는 필수구현이라고 적혀있지만, 원래는 Optional이었다고 한다. GPT의 등장으로 카이스트에서 '한 번 GPT를 사용해서 구현해봐라'는 의미로 필수로 올렸다고 한다. 1주차 프로젝트를 마무리하는 의미에서 GPT의 도움 없이 최대한 Advanced scheduler 구현을 시도해보자.

 

🔹 Main Goal

• 4.4 BSD 스케줄러와 유사한 다중레벨 피드백 큐(MLFQ) 스케줄러 구현하기
  • interactive하게 프로세스에 우선순위를 부여 (수식 이용)
  • 우선순위 기반 스케줄러

---

4.4BSD 스케줄러 #

• 이 스케줄러는 실행 가능한 스레드로 구성된 여러 큐를 유지하며, 각 큐에는 서로 다른 우선순위를 가진 스레드가 저장된다. 스케줄러는 언제든지 우선순위가 가장 높고 비어 있지 않은 큐에서 스레드를 선택한다. 우선순위가 가장 높은 큐에 여러 스레드가 포함된 경우, 스레드는 round-robin 순서로 실행된다.
• 이 스케줄러의 다양한 측면에서 특정 횟수의 타이머 틱 후에 데이터가 업데이트되도록 요구된다. 어떤 경우든 이러한 업데이트는 일반 커널 스레드가 실행되기 전에 이루어져야 한다. 그래서 커널 스레드가 새로 증가된 값 timer_ticks()과 이전 스케줄러 데이터 값을 동시에 볼 가능성이 없다.
• 4.4BSD 스케줄러에는 Priority donation 기능이 포함되어 있지 않다.

Niceness

int thread_get_nice (void);
// Returns the current thread's nice value.

int thread_set_nice (int nice);
// Sets the current thread's nice value to new nice and recalculates the thread's priority based on the new value

• Nice value: 스레드의 'niceness'를 나타내며, 스레드가 nice해지면, CPU 시간 중 일부를 기꺼이 포기할 것이다.
• Value (-20 ~ 20): 음수값에 가까워질수록 우선순위가 증가한다.

🔹 우선순위 계산하기

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

• 스레드가 nice해지면 우선순위를 낮춘다.
• 스레드가 최근에 많은 CPU를 사용했다면 우선순위를 낮춘다.
• 모든 스레드들에 대해서, 우선순위는 매 4클럭 틱마다 재계산된다.
• 결과값은 가장 가까운 정수값으로 내림된다.

🔹 recent_cpu 계산하기

recent_cpu = decay * recent_cpu + nice

• 매 타이머 인터럽트(매 클럭 틱)마다 현재 실행중인 프로세스의 recent_cpu를 1만큼 증가시킨다.
• 매 초마다 모든 스레드의 recent_cpu를 업데이트한다.

decay = (2*load_avg)/ (2*load_avg + 1)

• heavy load에서 decay는 거의 1, light load에서는 0이다.

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

• 부팅할 때, load_avg는 초기에 0으로 설정된다.
• ready_threads: ready_list에 있는 스레드와 업데이트하는 시간에 실행되는 스레드의 수 (idle 제외)

🔹 고정소수점 계산 구현하기

• 커널 내부에서는 정수형 계산만 가능하다: 커널은 컨텍스트 스위칭할 때 부동소수점 레지스터를 저장하지 않는다.
• 정수형 산술 연산을 사용해서 고정소수점 산술 연산을 구현해야 한다.
  • priority, nice, ready_threads 값은 정수형이고, recent_cpu, load_avg 값은 실수형이다.
  • 17.14 고정소수점 수 표현을 사용해 고정소수점 산술연산을 구현한다.

n: 정수 / x, y: 고정소수점 숫자 / f: 17.14 포맷의 1

• (Ex.) n을 고정 소수점으로 변환: n을 14 left shift
• (Ex.) x를 정수형으로 변환: x를 14 right shift