0.도입
OS의 scheduling policy들을 소개하며 특성과 한계, 워크로드에 대한 가정의 완화를 통해 BSD unix의 기본 scheduler인 MLFQ와 그 도입배경까지 확장해보자.
**워크로드:
시스템에서 처리해야 하는 작업의 전체적인 양과 특성.
주어진 작업의 종류, 수행 시간, 리소스 요구사항 등을 포함한다.
0.1.일반적인 스케쥴러에 존재하는 큐
-
대기 큐 (ready Queue, input queue):
실행 가능한 프로세스들이 CPU를 할당받기 위해 대기하는 큐. -
실행 큐 (running Queue):
현재 CPU를 소유한 프로세스들로 구성된 큐.
MLFQ라면 running queue는 서로 다른 레벨을 가진 여러 개의 queue로 구성된다.
멀티프로세서 시스템인 경우, 각 프로세서에 해당하는 running queue가 존재한다. -
차단 큐 (blocked queue, i/o queue, waiting queue, sleeping queue, device queue):
I/O 작업 등의 외부 이벤트가 발생하여 프로세스가 실행을 멈추고 기다려야 할 때, 해당 프로세스가 대기하는 큐.
I/O작업이 완료되면 해당 프로세스는 ready queue로 이동한다. -
종료 큐 (terminated queue, exit queue):
실행이 완료된 프로세스가 이동하는 큐.
종료된 프로세스들은 이 큐에서 제거되거나 기록되는 것을 기다린다.
0.2.CPU scheduling criteria
0.2.1. Criteria to Maximize(최대화)
- CPU 이용률(utilization)
utilization = running time / (running time + idle time)
실제 시스템에서는 CPU 이용률 40%에서 90%까지의 범위를 가진다. - 처리량(throughput)
처리량 : 단위 시간당 완료된 프로세스의 개수
0.2.2. Criteria to Minimize(최소화)
-
반환시간, 총 처리 시간(turnaround time)
프로세스를 실행하는 데 소요된 시간.
turnaround time(반환시간) = completion time - arrival time
performance(성능) 측면의 평가기준이다. -
대기 시간(waiting time)
Ready Queue에서 대기하면서 보낸 시간의 합. -
응답 시간(response time)
요청이 제출된 후 첫 번째 응답이 나올 때까지의 시간.
response time(응답시간) = firstrun time - arrival time
fairness(공정성), responsivity(반응성) 측면의 평가기준이다.
** turnaround time = waiting time + 프로세스 running time(스케쥴링을 통해 변경불가),
따라서 스케쥴링을 통해 turnaround time을 최소화하는 것이 곧 waiting time 을 최소화하는 것이다.
1.FIFO(선입선출)
초기가정:
1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다. (running queue로)
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다 (즉, 입출력을 수행하지 않는다).
5. 각 작업의 실행 시간은 사전에 알려져 있다.
먼저 도착한 작업을 먼저 실행하는 scheduling 정책이다.
장점: 없다.
단점: cpu를 점유하고 있는 작업이 지연되면, 그 뒤에 있는 작업이 모두 지연되는 convoy effect(호위효과)를 발생시킬 수 있다.
2.SJF(shortest job first. 최단작업우선)
가장 짧은 실행시간을 가진 작업을 먼저 실행하는 scheduling 정책이다.
장점: 초기가정 하에서 turnaround time에 대해 최적의 정책이다. 이 아이디어를 통해 다음 아이디어로 확장할 수 있다.
단점: 가정2를 제거하고 모든 작업은 임의의 시간에 도착할 수 있다고 가정하면, 다시 convoy effect가 발생할 수 있다.
단점: response time이 최악이다.
3.STCF(shortest time-to-compeletion first. 최소잔여시간우선), PSJF(preemptive SJF. 선점형 최단작업시간우선)
언제든 새로운 작업이 도착하면, 현재 작업과 새로운 작업의 잔여실행시간(completion time - current time)을 비교하여 더 적은 잔여실행시간을 가진 작업이 실행되도록 scheduling한다.
장점: 가정5 덕분에 turnaround time에 대해 최적의 정책이다. 이 아이디어를 통해 다음 아이디어로 확장할 수 있다.
단점: response time이 최악이다.
4.Round-Robin(라운드로빈, time slicing)
time sharing system을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, running queue에 위치한 순서대로 시간단위(Time Quantum)만큼 CPU를 할당하는 방식의 scheduling 정책이다.
time quantum이 작아질수록 평균응답시간이 작아지지만, 전체시간당 context switching 비용의 비율이 증가한다.
그래서 time quantum은 context switching 비용을 상쇄시킬정도로 길어야하면서도 평균응답시간을 고려해서 너무 길어지면 안된다.
장점: response time이 최적이다.
단점: turnaround time이 최악이다.
**time slice, time quantum
현재 실행 중인 작업이 다른 작업으로 전환되기전에 CPU를 사용할 수 있는 시간의 양.
time slice의 길이는 타이머 인터럽트 주기의 배수여야 한다.
**context switching 비용상쇄
일반적인 상쇄(amortization) 기술은 어떤 연산에 고정 비용이 존재하는 시스템에서 흔히 사용된다.
context switching time / time slice의 비율이 시스템의 전체시간동안 프로세스가 실행되는 시간에 직접적인 영향을 미치므로
이 비율을 낮추는 것이 비용을 상쇄(amortization)하는 것이다.
5.I/O연산을 고려
I/O위주의 대화형 작업 a는, 전체 프로세스 시간에서 cpu burst time의 비율이 적고 I/O burst time의 비율이 크다.
I/O burst time동안 프로세스는 block되는데, 이 때 cpu연산과 i/o연산을 중첩시키려면 다른 프로세스 b를 실행할 수 있게하고,
i/o연산이 끝나면 b를 선점하고 a가 실행되게 하면된다.
이렇게 연산을 중첩하여 I/O burst time동안 다른 cpu burst작업이 실행되게 하면 CPU utilization이 높아진다.
https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/korean
https://www.krivalar.com/OS-ready-queue-in-os
