Advanced Scheduler - gon2gon2/pintos-kaist GitHub Wiki

4.4BSD scheduler와 비슷한 MLFQS를 구현하라.

MLFQS

• CPU burst가 짧은 프로세스에게 높은 우선순위를 주는 방식
• 우선순위가 높을수록 time quantum이 작다.
• 짧은 time quantum안에 프로세스가 종료된다. -> CPU burst가 작다.
• time quantum안에 못 끝냈다. -> CPU burst가 커서 짧은 애들 먼저 처리하고 나중에 처리한다.
• MLFQ는 최초에 배정된 큐에서 이동할 수 없지만, MLFQS는 aging이나 CPU burst에 따라 다른 큐로 이동할 수 있다.
• 처음 생성된 프로세스는 가장 높은 우선순위의 큐에 배정되고,
• 다음과 같은 파라미터들이 필요하다.
  • 큐의 수
  • 각 큐마다의 스케줄링 알고리즘(높은 우선순위는 짧은 time quantum의 RR,가장 낮은 우선순위는 FCFS)
  • 어떤 프로세스를 상향/하향 시켜줄 것인가.
  • 프로세스가 service가 필요할 때 어떤 큐에 넣어줄지에 대한 방법
• 가장 일반적인 CPU 스케줄러이지만, 설정할 파라미터가 많아 가장 복잡하다.

4.4BSD scheduler

• scheduling metrics 중 average response time 를 줄이기 위한 스케줄러, MLFQS를 사용한다.
• 우선순위별로 레디 큐가 있다.

Nice

• 다른 스레드들에게 얼마나 nice한지.(사려깊은, 이타적인, ...)
• 높을수록 nice해서 다른 스레드에게 양보해주고 낮을수록 다른 스레드로부터 뺏어오려고 한다.
• priority = PRI_MAX - (recent_cpu / 4) - (nice * 2).

Priority

• 0~63, 클수록 우선순위가 높다. nice하지 않을수록, 최근에 CPU를 사용하지 않을수록 높아진다.
• 각 coefficient(4,2)는 큰 의미는 없고 잘 작동하더라.

Recent CPU

• 중첩된 곱의 연산으로(곱을 덮어씌우는 연산) 구한다.
• exponential weighted moving average를 사용해서 계산한다
• 계수를 먼저 구하고 recent cpu를 곱해야 한다.
• recent_cpu = (2load_avg)/(2load_avg + 1) * recent_cpu + nice.

Load AVG

• 1분동안 수행 가능한 스레드의평균 개수
• 시스템이 모두 하나의 값을 가짐(전역적임)
• load_avg = (59/60)*load_avg + (1/60)*ready_threads.

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

• 부호비트, 정수부, 소수부로 나눠진다.
• 정수부와 소수부의 비트 수는 시스템마다 달라진다.
• 핀토스에서는 1/17/14로 나눠서 쓴다.
• 정수와 실수의 표현방법이 달라 비트연산을 이용해 스케일을 맞춰줘야 한다.(보통 정수에 2^14를 곱하는 연산을 해준다)