7. 스케줄링(Scheduling)

스케줄링에 대한 내용에 들어가기 앞서 필요한 내용들을 쭉 정리해보겠습니다.

 

프로세스들이 life cycle 동안 state transition을 진행하는 과정에서 발생하는 이벤트가 스케줄링입니다. 실행 중인 프로세스가 중단되고 다른 프로세스로 변경될려면 CPU를 할당받아 사용하던 프로세스는 안전한 곳으로 대피시키는 교체 작업을 했었는데 이것이 context switching 이였습니다.

 

context switching은 dispatcher라는 모듈이 진행해줍니다. OS 스케줄러는 dispatcher와 밀접한 관계를 가지며, 위에는 또다른 scheduling policy로 구성된 2-level architecture 형태를 띕니다. 스케줄러는 여러 프로세스들에게 공평하면서 효율적이게 CPU를 공유시킬 수 있습니다.

 

 

 

이렇게 스케줄링의 내용을 정리했는데 만약 스케줄링이 주는 이점보다 scheduling overhead가 크다면 사용하지 않는 편이 더 좋습니다. 때문에 dispatch latency(scheduler latency)를 최소화해야합니다. scheduler latency란 한 프로세스가 더 이상 수행을 못하게 되었을 때 새로 선택된 프로세스가 다시 수행을 재개할 때까지의 시간입니다.

 

스케줄링이 필요해지는 상황은 공유 자원이 있고 이 공유 자원을 사용하기 원하는 프로세스가 여러 개 있을 때 입니다. 이런 상황에서 자원을 공유하는데 사용하는 규칙을 scehduling policy라고 합니다. scheduling policy는 scheduling algorithm으로 굉장히 많은 종류가 존재합니다. (선착순, 우선 순위 등)

 

여기서 어떤 scheduling policy를 선택하는가가 전체 시스템의 성능에 굉장히 큰 영향을 미치기 때문에 OS 스케줄러는 자기의 상황을 정확히 인지하여 최적의 queueing policy를 스케줄링해야 합니다.

 

 

 

스케줄러를 설계할 때 부여되는 Design objective는 크게 4가지가 존재합니다.

 

1. 시스템의 utilzation을 극대화 시키는 것 (리소스가 동작한 시간 중 유요한 연산을 한 시간을 백분율로 표현합니다.)
2. 자원을 공유한다는 점에서 overhead가 발생하기 때문에 이 부분을 최소화 시키는 것이 중요합니다.
3. Context switching의 과정을 최소화 하자(context switchng을 할때마다 overhead가 발생하니)
4. 공정한 CPU 할당

이런 Design objective를 스케줄러가 만족시키는지 확인하기 위해서는 전부 수치화해서 기준을 넘었는지 확인해야합니다.

이러한 수치를 optimization metric 이라고 합니다.

 

 

 

그 외에도 위 사진과 metric을 최적화 시키게 scheduling policy를 적재적소로 활용하는 것이 OS의 중요한 임무입니다. 가장 자주 사용하는 policy에 대해서 알아보겠습니다.

 

 

 

FIFO나 아니면 optimal queueing policy라고 알려진 SJF(Shortest Job First), FIFO의 변형된 형태인 Round Robin, Multilevel Feedback Queues라는 scheduling policy가 있습니다.

 

 

FIFO policy

 

queue의 제일 앞에 온 프로세스가 제일 먼저 자원을 할당받는 방법으로 모든 실행이 종료될 때까지 지속됩니다. 일종의 non-preemptive scheduling policy입니다. 실행 시간이 긴 프로세스가 더 많은 CPU를 차지하기 때문에 비효율적일 수 있습니다. (batch OS는 전통적인 FIFO policy를 사용했습니다.)

 

batch OS에서는 한번 submit하면 끝날 때까지 Job이 진행되었지만 현재는 프로세스가 끝날 때까지 CPU를 사용하지 않습니다. 멀티 프로그래밍에서 멀티 태스킹을 하기 때문에 FIFO는 그 프로세스의 CPU Burst의 시작에서부터 CPU Burst의 끝까지만 스케줄링 합니다. (정해진 구간에서만 FIFO를 진행)

 

그 다음에는 스스로 CPU를 양보하고 Waiting queue에 들어갑니다. block이 발생하기 전까지만 FIFO를 사용한다고 생각하시면 되겠습니다. 하지만 CPU Burst가 굉장히 큰 경우 CPU를 독점하는 상황이 생기기 때문에 문제가 발생할 수 있습니다.

 

이 부분은 이전에 배웠던 CPU protection mechanism으로 해결이 가능한데 timer 값이 0이 된 순간 timer interrupt가 발생하여 강제로 CPU를 뺏어오면 됩니다. non-preemptive한 FIFO를 timer를 사용하여 preemptive FIFO로 만들게 되는데 이것을 Round Robin이라고 부릅니다.

 

여기서 Time slice라는 개념이 나오는데 이건 timer device에 부여되는 interval 값입니다. 간단하게 timer가 interrupt를 발생시킬 시간을 결정한다고 생각하시면 됩니다. 즉 time slice만큼은 non-preemptive하게 수행하다 time slice 이후에도 CPU를 가지고 있다면 뺏는 방식입니다.

 

ex)

 

다음과 같이 P1, P2, P3가 ready queue에 도착했는데 미세한 차이로 P1, P2, P3 순으로 도착했다고 하겠습니다. P1의 Burst size는 24이고 P2, P3의 Burst size는 3입니다. 이 queue에 있는 프로세스를 FIFO로 스케줄링했을 때 waiting time은 

 

• P1: 0
• P2: 24
• P3: 27

로 average waiting time은 17입니다. P2와 P3는 Burst size에 비해서 굉장히 큰 waititng time을 가지게 됩니다. FIFO는 굉장힌 긴 CPU Burst size를 가지는 프로세스가 앞에 있는 경우 굉장히 긴 waiting time을 가지게 된다는 아쉬운 단점을 가지게 됩니다. 

 

 

 

이번에는 P2, P3, P1 순으로 도착했다고 가정해보겠습니다. 이 경우 average waiting time은 많이 줄어들게 됩니다. 

• P1: 6
• P2: 0
• P3: 3

average waiting time이 3이 됩니다. 즉 FIFO가 항상 나쁜 waiting time을 가지는 것은 아닙니다. 굉장히 긴 CPU Burst를 가지는 프로세스가 있는 경우에만 waiting time이 길어지게 됩니다.

 

 

 

Shortest Job First

 

이 scheduling policy는 optimal scheduling policy로 프로세스들의 waiting time을 가장 최소화 합니다. 동작은 ready queue의 프로세스를 queueing 할 때 그 프로세스가 다음에 수행할 CPU Burst size를 보고 Burst size가 작은 것을 앞으로 두고 큰 것을 뒤에 놓습니다. 

 

작은 Job(CPU Burst size가 작은 것들)을 선호한다고 하여 Shortest Job First라고 부릅니다. 이 알고리즘은 run queue에 있는 프로세스 다음에 실행 될 프로세스의 Burst size를 알아야만 사용할 수 있다는 단점이 있습니다. 실제로 구현하여 적용할 수 없기 때문에 주어진 환경에서 optimal scheduling의 기준으로 사용하여 다른 스케줄링의 성능을 측정하거나 CPU Burst size를 예측할 수 있는 문제에서만 사용합니다.

 

 

 

SJT는 non-preemptive와 preemptive 2가지 방법이 존재합니다. non-preemptive scheduling의 경우 이전과 동일하게 프로세스가 수행을 다 마칠 때까지 CPU를 절대 놓지 않는 방법입니다. preemptive sheduling의 경우 한 프로세스가 I/O Burst size가 최소여서 CPU를 잡고 동작하고 있을 때 새 프로세스가 들어오면 실행 중인 프로세스의 남은 Burst size와 비교하여 작업 중인 Burst가 더 크다면 새로운 프로세스를 먼저 실행하는 방법입니다.

 

이걸 SRTF(Shortest Remaining Time First)나 STCF(Shortest Time to Completion First)라고 부릅니다.

 

ex)

 

CPU Burst size를 알고있어야 SJF를 구현할 수 있으니 알고있다고 가정하겠습니다.각각 도달한 시간이 다른 것을 알 수 있습니다. 위의 예시는 non-preemptive SJF로 P1의 남은 Burst size보다 작은 P2가 들어왔지만 P1의 실행이 끝날 때까지 CPU를 잡고있는 것을 알 수 있습니다. 그래서 average waiting time이 크게 나온 것을 확인할 수 있습니다. (처음 실행되는 프로세스의 CPU Burst size가 클수록 성능이 낮아짐)

 

 

 

preemptive SJF의 경우 P1이 실행되던 도중에 P1의 남은 Burst size보다 더 작은 Burst size 프로세스가 run queue에 들어오게 되면 바로 교체가 일어나게 됩니다. (P1의 remaining size = 5, P2 Burst size = 4) 이렇게 비교하여 교체하는 과정이 계속 반복됩니다. non-preemptive SJF의 average waiting time 보다 더 작은 것을 확인할 수 있습니다. 

 

 

 

SJF는 가장 optimal한 선택지 이지만 아직 수행도 하지 않은 프로세스의 Burst size를 알 방법이 없기 때문에 예측해서 사용해야 합니다. 그중 널리 사용되는 것이 Exponential average라는 것입니다. weighted sum으로 값을 예측하는 방법인데 예측은 일정한 인터벌 단위로 일어나게 됩니다. 

 

$V_{n+1} = \alpha V_n + (1 - \alpha) \theta$로 예측값 n+1은 이전의 Expoential average값에 어떤 가중치 $\alpha$를 곱하고 지금 Burst size에 $1 - \alpha$를 곱하면 됩니다. $\theta$가 현재 Burst size입니다. (지수가중평균을 사용하여 진행)

 

이런 Exponential average를 사용하는 예측을 Exponential smoothing이라고 부릅니다. 가중치 $\alpha$ 값에 따라 현재값이 예측값에 영향을 미치는지 아니면 이전 예측값이 현재 예측값에 영향을 더 미치는지를 결정합니다. 이 알파값이 하이퍼 파라미터로 우리가 결정해야 하는데 잘 결정하기 힘들기에 좋은 예측이 일어나기가 어렵습니다. (프로세스마다 다 다른값)

 

위에서 말한 것 처럼 SJF는 optimal한 알고리즘이지만 실제 컴퓨터 환경에서는 적용하기 어렵다는 문제가 존재합니다. 그럼 구현이 가능하면서 waiting time을 최소화 시키는 방법을 찾아야 하는데 그 대안이 Preemptive한 FIFO scheduling policy인 Round Robin입니다.

 

 

 

Round Robin

 

FIFO와 마찬가지로 선착순으로 진행되며 CPU Burst를 다 소진하거나 time slice를 다 소진한 경우 CPU를 뺏기고 run queue 가장 뒷 부분으로 이동합니다. Round Robin은 우선순위도 부여할 수 있어 FIFO보다 더 유연하게 스케줄링이 가능합니다. 

 

 

 

Round Robin을 사용하기 위해서는 time slice를 정해야 합니다. time silice가 너무 긴 경우 FIFO 알고리즘 처럼 동작 할 수 있습니다. 그렇다고 너무 짧게 설정한다면 스케줄링이 너무 빈번하게 발생하여 context switching overhead가 커지게 됩니다. 즉 overhead를 줄이기 위해서는 time slice를 길게 잡아야 하지만 사용자에게 빠른 응답을 하기 위해서 짧게 설정해야 하는 trade off가 발생합니다.

 

최근에 사용되는 OS에서는 time slice를 약 1~10ms로, 실시간으로 동작해야 하는 시스템에서는 약 500ms로 설정합니다. 초기 unix의 경우 CPU 성능이 좋지 않아 time slice를 1로 설정한 것과 비교하면 굉장히 작아진 것을 알 수 있습니다. (프로세스가 마무리 되어도 time slice가 남아있다면 그 시간동안 CPU를 놔주지 않음)

 

ex)

 

FIFO의 경우 preemtive한 스케줄링이 non-preetive한 스케줄링보다 waiting time이 작았지만 Round Robin에서는 다릅니다.

 

 

 

 

P1, P2 순으로 도착했고 time slice는 1로 설정했을 때 RR은 P1, P2가 서로 반복적으로 1 time unit마다 동작하게 됩니다. P2는 1번의 time slice로 끝나고 P1은 10번의 time slice로 종료되니 총 11 time slice 후 두 프로세스가 종료됩니다. P1의 waiting time은 1 time slice가 됩니다. average time은 1이 됩니다. (처음 P2가 대기한 시간과 P2가 실행될 때 P1이 대기한 시간)

 

 

 

하지만 RR이 항상 FIFO보다 빠른 것은 아닙니다. 두 프로세스의 Burst time이 동일한 경우 FIFO에서는 P2만 대기하니 average waiting time은 2.5이지만 RR에서는 1번 실행될 때마다 1 time slice가 줄어들어 매번 변경이 일어나서 더 느려집니다. 

 

정리하면 workload가 다 균일하다면 Round Robin을 사용하면 느리므로 CPU Burst size가 크게 차이가 나는 경우나 아니면 CPU Burst size가 작아 빠르게 마무리 시킬 수 있을 때 효과적입니다. FIFO는 이와 달리 균일한 CPU Burst size에 빠르고 차이가 난다면 느려집니다. 그렇기에 이 두 스케줄링을 적절히 섞어 더 좋은 퍼포먼스를 뽑아내는 것이 중요합니다.

 

- I/O process인 경우 CPU를 많이 사용하지 않기 때문에 빠르게 마무리를 짓는 Round Robin이 효과적입니다.

- CPU process의 경우 긴 Burst size를 가지는데 FIFO가 긴 Burst size를 대기 시키는 시간이 짧아 효과적입니다.

- 즉 어떤 프로세스인지 구별하는 것이 중요!

 

 

 

FIFO와 RR은 time slice의 차이로 만들어집니다. workload에 따라 적절하게 time slice를 조절한다면 이상적인 average waiting time을 얻을 수 있겠지만 이 방법은 굉장히 어려운 문제에 속합니다. adaptive하게 time slice를 설정해주는 RR 알고리즘을 Multi-level Feedback Queue(MLFQ)라고 부릅니다.

 

 

 

Multi-level Feedback Queue(MLFQ)

 

 

Feedback Queue는 Round Robin queue라는 것을 의미하고 Multi-level은 이 RR queue가 여러 겹으로 되어 있다는 것을 의미합니다. MLFQ는 STCF 알고리즘의 CPU Burst size의 핵심 아이디어를 사용합니다. 과거에 짧은 Burst size 패턴을 보였다면 그 이후에도 짧을 확률이 높기 때문에 우선 순위를 높게 설정하는 방법을 적용하여 구현해야 합니다.

 

 

 

이 스케줄링의 핵심은 I/O process인지 CPU process인지 구분을 할 수 있어야 하며, I/O process는 Burst size가 작으니 우선순위를 높게 주고 CPU process는 Burst size가 크니까 낮은 우선순위를 주는 것 입니다. 여기서 CPU process는 timer interrupt를 자주 발생할 경우 성능이 좋지 않기 때문에 긴 time slice를 주는 방향으로 설계를 해야합니다. (이것이 MLFQ의 기본적인 아이디어 입니다.)

 

 

 

MLFQ는 처음 생성되는 프로세스는 I/O process라고 가정하여 짧은 time slice와 높은 우선순위를 부여합니다. 그 다음 각 프로세스를 실행하다 한 프로세스가 CPU intensive process라고 생각이 된다면 우선순위를 한 단계 낮추고 time slice의 값을 2배로 늘립니다. 이렇게 2배씩 time slice를 늘리는 방식으로 인해 MLFQ를 Exponential queues 기법이라고도 부릅니다. (time slice가 2의 n승으로 굉장히 빠르게 증가하기 때문)

 

 

 

MLFQ의 run queue의 struture입니다. single queue로 구성되어 있으며 제일 앞 부분에서 CPU로 dispatch가 일어나고 새로 들어온 프로세스는 제일 뒤로 들어가는 구조입니다. MLFQ는 이런 single queue가 여러 개 존재하는데 위 사진처럼 n개의 레벨이 존재할 수 있습니다.

 

이 n개의 queue들은 각각의 우선순위를 가지게 되는데 제일 위에 있는 queue가 가장 높은 우선순위의 queue가 됩니다. 어떤 프로세스가 queue에서 dispatching 되려면 윗 레벨 queue들이 전부 비워져 있어야 됩니다. 이렇게 Round Robin과 Preemtive가 적용된 형태로 동작합니다.

 

각 레벨의 queue들은 time slice 값이 다릅니다. 우선순위가 높을수록 I/O process에 가까우니 time slice를 짧게 그 반대의 경우에는 길게 time slice를 설정합니다. (2의 n승, n = priority),

 

 

그러면 어떤 방식으로 I/O intensive한 프로세스인지 알 수 있을까요?

 

대부분의 I/O process는 time slice가 다 사용되기 전에 I/O operation을 initiate하고 Block 당합니다. 이를 통해서 time slice가 끝나기 전에 CPU를 내놓으면 I/O process로 생각합니다. 반대로 어떤 프로세스가 time slice를 다 소모하고도 더 많은 CPU를 사용하고자 한다면 CPU process로 간주합니다.

 

• 프로세스가 생성될 때마다 우선순위가 0인 프로세스에 넣고 위에 방법을 통해서 CPU intensive하면 점점 아래로 내리고 I/O intensive하면 그대로 두는 방식으로 동작합니다.

 

 

 

Fair Share Scheduling

 

 

 

OS는 멀티미디어를 지원합니다. 이런 continuous media 같은 경우 프로세스들에게 웨이트에 따라 일정한 CPU bandwidth를 제공해줘야 합니다. 비디오 디코더가 원활하게 동작할려면 CPU time의 20%는 할당받아야 하고 다른 프로그램들은 그보다 덜 받아도 원활하게 동작할 수 있다면 이게 fair한 스케줄링이 됩니다. (프로세스의 웨이트에 따라 CPU를 할당)

 

 

 

fair share sheduling을 수학적으로 formulation하면 사진과 같이 나옵니다. $t_1$에서 $t_2$까지의 time interval이 존재할 때 ready queue에 있는 모든 프로세스의 웨이트 합분의 나의 웨이트만큼의 시간을 하면됩니다. 하지만 $t_1$에서 $t_2$의 interval이 굉장히 작거나 클 수 있습니다.

 

작을 때 이런 비율을 계속 제공해 준다면 실현이 불가능합니다. 왜냐하면 계속 CPU를 context switching해야 되기 때문입니다. scheduling overhaed가 발생하여 아주 작은 time interval 동안에 fairness를 보장해주기는 어려운 문제가 있습니다.

 

이런 overhead가 없다고 가정한 상황이 있는데 이것을 generalized process sharing으로 가장 이상적인 fair share schreduling이라고 합니다. 이런 기법은 실제적으로 구현한 fair share scheduling의 성능과 비교할 때 사용됩니다. 가장 이상적인 성능에 얼마나 가까운지 평가하기 위해서 입니다.

 

 

 

generelized process sharing은 2가지 방법으로 구현이 됩니다. 첫 번째는 Round Robin을 통해서 두 번째는 virtual run time을 통해서 구현이 됩니다. Weightd Round Robin(WRR)의 경우 각 프로세스들에게 time slice을 각 프로세스의 웨이트에 비례하게 설정합니다.

 

Weighted Fair Queuing(WFQ)은 프로세스들이 웨이트가 달라도 같은 시간동안 CPU를 사용하는 것을 의미합니다. 다른 점은 CPU를 뺏기고 다시 run queue로 이동할 때 웨이트가 큰 프로세스는 중간에 끼어드는 방식으로 WRR과 비슷한 CPU time을 얻어가게 됩니다.

 

- CPU Burst는 CPU execution에 해당하는 사이클