스케줄링(scheduling)

0. 스케줄링의 정의

일반적으로 프로세스/스레드에 대해서 CPU배정 순서를 정하는 과정

1. 스케줄링 알고리즘의 평가항목

1-1 일반적인 평가항목(엄밀하게 측정하기 어려움)

workload(작업량) -얼마나 많은 일을 하는가 (보통 특정시간동안) 높을수록 좋음

overhead(추가 일) - 이 스케줄링때문에 얼마나 많은 일이 추가되는가 -낮을수록 좋음

Fairness(공정성) - 얼마나 공정한가 (같은 우선순위일때 공정성이나, 우선순위가 높을수록 빨리하는등) -높을수록 좋음

Predictability(예측 가능성) - 예측이 가능한가 -높을수록 좋음

 

1-2 측정 가능한 평가항목(정확하게 측정가능, 입력값에 따라 달라짐)

Throughput(작업량) - 작업한 프로세스(스레드) 개수/시간

Average wait time(평균 대기시간) - ready, wait 상태에 있었던 평균 시간

Turn around time(끝날때 까지 기다리는 시간) - (특정 프로그램이 끝난시간 - 그 프로그램이 도착한 시간)

response time(반응시간) - 처음 프로세스가 running이 되기까지 걸린 시간

 

2. 스케줄러가 작동하는 지점

프로세스의 생애주기에서 ready(준비)-> running(실행)으로 갈때 스케줄러가 작동(ready에 있는 것들 중에서 선택)

 

3. 스케줄러의 주요 분기점

3-1 preemptive(선점형)

preemptive이면 다른 프로세스가 돌아가던도중 끼어들수 있고(context switch),

비선점형이면 그 프로세스가 내주기 전까지는 끼어들 수 없음. 

 

주로 CPU-bound 작업(CPU만 집중적으로 돌아가는 계산, 인공지능 계열)을 주로 하면 non-preemptive(비선점)

I/O-bound 작업(입출력을 위주로 하는계산, 카톡등 일반적인 프로그램)을 주로 하면 preemptive(선점)

 

3-2 work-conserving(항상 일하는가)

예약된 작업이 있을경우 항상 돌리는 것을 work conserving

예약된 작업이 있어도 유휴가 가능한 것이 non-work conserving

거의 대부분 work conserving을 쓰지만, predictability(예측 가능성)이 중요할경우 non-work conserving을 쓰기도함.

4. 주요 스케줄링 알고리즘 - Uniprocessor(싱글 코어)

4-1 FIFO(first in first out)

처음 들어온 것이 처음 나가는 방식

문제점 - 오래걸리는 작업이 앞에있으면, 뒤에 있는 짧은 작업들이 그걸 기다려야함. (response time이 bad)

 

4-2 SJF(shortest job first)

짧은 걸 먼저하는 방식

문제점 - 정확한 시간을 알기 힘듬, 기아 상태 발생(기아 상태= 너무 오랫동안 작업을 받지못하는 경우)

 

4-3 Round-robin

계속 과정들을 특정 시간만(time slice) 하면서 돌아가는 방식

문제점: 과도한 context switch(프로세스를 바꾸는 context switch도 시간소모), Turn-around time이 좋지 못함. 

 

4-4 priority scheduling

각 작업에 우선순위를 주고 우선순위 대로 진행하는 방식

문제점: 기아 상태 발생(SJF와 같은 원리)

 

4-5 MLFQ

배정받은 시간을 I/O로 인해 양보할경우 높은 우선순위 큐, 양보하지 않을경우 낮은 우선순위 큐를 매기는 방식

처음에는 높은 큐에 두지만, 잘 양보하지 않는 cpu-bound 작업위주는 낮은 큐로 내려간다. 

같은 큐 내부에서는 주로 RR을 쓰고, 높은 우선순위 일수록 짧은 time slice를 가진다

 

특정시간이 지나면 다시 모든 작업을 높은 큐로 배치해 기아 상태 문제를 해결한다.

대부분의 CPU-bound 작업들이 우선순위가 낮아도 되며, 오래걸린다는 것을 이용한 방식.

 

5. 주요 스케줄링 알고리즘 - Multiprocessor(멀티코어) 

5-1 Affinity scheduling

같은 프로세스 thread 끼리 같은 코어에서 작업하게 만드는 방식(공간 통일)

(context switch가 빠름)

 

5-2 Gang scheduling

단일 프로세스 thread끼리 동시에 작업하게 만드는 방식(시간 통일)

(context switch 횟수가 감소)