CPU 스케줄링 : CPU 스케줄러와 CPU 스케줄링 알고리즘들

CPU 스케줄링

CPU 스케줄링이란 어떤 프로세스에게 CPU를 할당을 해줄 것인지 정하는 것이다. CPU와 I/O 장치 등의 시스템 자원을 골고루 효율적으로 사용하기 위해서 CPU 스케줄링이 필요하다. 

 

CPU Scheduler가 Ready 상태에 프로세스 중에서 이번에 CPU를 줄 프로세스를 선택하면, Dispatcher가 그 프로세스에게 CPU 제어권을 넘기며 이 과정을 문맥 교환, context switch라고 한다.

 

 

 

 

 

스케줄링을 위한 큐와 스케줄러

프로세스를 스케줄링하기 위한 큐에는 세 가지가 있다. 프로세스들은 각 큐들을 오가며 수행된다. 

 

1. Job queue : 현재 시스템 내에 있는 모든 프로세스의 집합

 

2. Ready queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리고 있는, Ready 상태의 프로세스의 집합

 

3. Device queue : I/O device의 처리를 기다리는 프로세스의 집합

 

 

 

스케줄러 또한 세 종류가 있다.

 

1. Long-term scheduler (Job scheduler) : 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정한다. 프로세스에 메모리를 주는 문제와 관련되어 있으며 time sharing system에는 보통 이 장기 스케줄러를 두지 않고 새로 생성되는 프로세스를 무조건 ready queue에 넣는다.

 

2. Short-term scheduler (CPU scheduler) : CPU 스케줄링 알고리즘에 따라 어떤 프로세스를 다음에 실행시킬지 결정한다. 프로세스에 CPU를 할당하는 문제와 연관되어 있으며 충분히 빠르게 동작해야 한다.

 

3. Medium-term scheduler (Swapper) : 여유 공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다. 프로세스에게서 메모리를 빼앗는 것과 관련되어 있다.

 

 

 

 

 

CPU 스케줄링의 분류

1. 비선점 스케줄링

프로세스가 자발적으로 CPU를 반납하는 것을 비선점이라고 부른다. 프로세스가 종료(terminate)하거나 I/O 요청하는 시스템 콜을 보내 프로세스가 대기 상태(blocked)로 전환하는 경우가 이에 해당된다.

 

 

2. 선점 스케줄링

선점은 OS가 CPU 사용권을 강제로 회수하여 우선 순위가 높은 프로세스에게 넘기는 것이다. 우선 순위가 높은 프로세스를 빠르게 처리해야 할 경우 유용하며, 높은 우선 순위를 가진 프로세스들만 들어오는 경우에는 오버헤드가 발생한다. I/O 작업 완료 후에 인터럽트가 발생하거나 할당시간이 만료되어 timer interrupt가 발생하는 등의 경우에 선점 스케줄링이 일어날 수 있다. 

 

 

 

 

 

CPU 스케줄링 성능 척도

1. CPU utilization : CPU 이용률에 해당하며 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율을 의미한다. 즉, CPU를 얼마나 잘 활용하는지를 나타낸다.

 

2. Throughput : 특정 시간동안 실행이 완료된 프로세스의 개수를 말한다. 

 

3. Turnaround time : 총처리 시간으로 특정 프로세스가 시작해서 끝날 때까지 걸리는 시간이다. Ready queue에서 대기한 시간과 CPU에서 실행하는 시간, I/O 시간 등을 모두 합한 시간이다.

 

4. Waiting time : 프로세스가 waiting queue에서 대기하는 시간이다.

 

5. Response time : 한 요구가 submit된 후에 첫 번째 응답이 나올 때까지의 시간이다. 즉, 응답이 시작되는 데까지 시간이 얼마나 걸리는지를 나타내는 척도다.

 

 

 

 

 

CPU 스케줄링 알고리즘

FCFS(First-Come First-Service)

먼저 도착한 프로세스에게 우선순위를 부여한다. 도착한 프로세스의 CPU 이용 시간에 따라 Waiting time과 Average waiting time에 편차가 크다. 이를 convoy effect라고도 하는데, convoy effect는 CPU 소요시간이 긴 프로세스가 먼저 도달하여 short process가 오래 기다려야 하는 것을 뜻한다.

 

 

 

SJF(Shortest-Job-First)

다음 *CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄링한다.

 

선점 스케줄링에서는 현재 수행 중인 프로세스의 남은 시간보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 기존에 CPU를 사용하던 프로세스는 CPU를 빼앗긴다. 이를 Shortest-Remaining-Time-First(SRTF)라고도 부른다.

비선점 스케줄링에서는 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 프로세스는 CPU를 선점당하지 않는다.

 

SJF의 문제점은 "다음번 CPU burst time"을 프로세스를 직접 실행해보기 전까지는 정확히 알 수 없다는 것에 있다. 다만 우리는 과거의 CPU burst time을 이용해서 exponential averaging 등의 방법으로 다음번 CPU burst time을 추정할 수는 있다. exponential averaging에서 사용하는 식은 다음과 같다.

 

 

*CPU burst time : 프로세스가 수행될 때 CPU를 연속적으로 사용하는 구간을 CPU burst라고 하고 I/O 요청을 보내서 대기 상태로 전환된 구간은 I/O burst라고 한다. CPU burst에 CPU 작업이 집중적으로 일어나며, CPU burst time은 프로세스의 종류에 따라 다르게 분포한다. 

 

 

 

Priority Scheduling

각자 프로세스는 우선순위를 가지며 더 높은 우선순위를 가진 프로세스에게 CPU를 할당한다. 선점, 비선점 스케줄링이 모두 가능하다. SJF는 우선순위가 다음 CPU burst time 예측값인 일종의 priority scheduling이다.

 

priority scheduling의 문제점은 낮은 우선순위를 가진 프로세스들은 기약없이 대기만 하는 기아현상, Starvation이 일어날 수 있다는 것이며 이를 해결하기 위해서 시간이 지남에 따라 프로세스의 우선순위를 높여주는 Aging 방법을 쓸 수 있다.

 

 

 

Round Robin(RR)

각 프로세스는 동일한 크기의 할당시간, time quantum을 가져서 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. n개의 프로세스가 ready queue에 있고 할당시간이 q time unit인 경우 어떤 프로세스도 최대 (n-1) x q time unit 이상 대기하지 않는다는 장점이 있다.

 

하지만 time quantum을 잘 조절해야 best performance를 낼 수 있는데, q를 너무 크게 설정하면 모든 프로세스가 그 time unit 안에 다 처리되어 FCFS와 다를 바가 없어지고, q를 지나치게 작게 설정하면 context switch가 자주 발생하여 오버헤드가 커진다.

 

RR는 일반적으로 SJF보다 평균 turnaround time이 더 길지만, 번갈아가며 모든 프로세스에 대해 응답을 우선 하기 때문에 response time은 더 짧다. 

 

 

 

Multilevel Queue

Multilevel queue는 Ready queue를 여러 개로 분할하는 방법이다. interactive한 프로세스는 foreground로, human interaction 없이 여러 가지 일을 연달아 하는 작업들은 background에 넣으며 각 큐는 RR, FCFS로 독립적인 스케줄링 알고리즘을 가지도록 한다.

 

이때 큐 간의 스케줄링도 필요한데, foreground를 모두 serve한 후에 background를 실행하는 식으로 큐 사이에 고정된 우선순위를 부여할 수도 있으나 아주 드문 확률로 기아현상이 발생할 우려가 있다. 각 큐에 CPU time을 적당한 비율로 할당하는 time slice 방법을 이용할 수도 있다. 예를 들어 80%는 RR을 쓰는 foreground에, 20%는 FCFS를 쓰는 background에 할당하는 것이다.

 

multilevel queue를 다음 그림과 같이 더 세분화 할 수도 있다.

 

 

 

 

 

Multilevel Feedback Queue

multilevel queue 방식에서 프로세스가 다른 큐로 이동할 수 있도록 한 알고리즘이다. aging을 구현하여 기아현상을 방지할 수도 있고 작업이 끝날 기미가 안 보인다면 priority가 더 낮은 다른 큐로 보내버릴 수 있다. 전체 큐의 수와 각 큐의 스케줄링 알고리즘, 프로세스를 상위-하위 큐로 보내는 기준과 프로세스가 들어갈 큐를 결정하는 기준 등을 정의해야 한다. 

 

 

Multiple-Processor scheduling

Multiple Processor는 CPU를 여러 개 사용하는 것으로, 같은 종류의 프로세서인 경우에는 단순하게 프로세스를 queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 하면 되지만, 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해진다.

 

일부 프로세서에 job이 몰리지 않도록 부하를 적절히 나누는 load sharing 메커니즘이 필요하며 시스템 데이터의 접근과 공유를 각 프로세서가 각자할 것인지(Symmetric Multiprocessing, SMP) 하나의 프로세서가 도맡아 처리하고 나머지는 거기에 따를 것인지(Asymmetric multiprocessing)도 결정해야 한다.

 

 

 

 

 

Thread Scheduling

- Local Scheduling : 유저 레벨 스레드는 사용자 수준의 thread library에 의해 어떤 스레드를 스케줄할지 결정한다.

 

- Global Scheduling : 커널 레벨 스레드는 일반 프로세스와 마찬가지로 커널의 단기 스케줄러(CPU 스케줄러)가 어떤 스레드를 스케줄할지 결정한다.

 

 

 

 

 

Algorithm Evaluation

알고리즘을 평가하는 방법에는 다음과 같은 방법들이 있다.

 

1. Queueing models : 확률 분포로 주어지는 queue에 process가 arrive하는 arrival rate과 server를 통해 나가는 server rate을 통해 각종 performance index 값을 직접 계산해 평가의 척도로 이용할 수 있다.

 

2. Implementation & Measurement : 실제 시스템에 알고리즘을 직접 구현하여 실제 작업에 대해 성능을 측정하고 비교할 수 있다.

 

3. Simulation : 알고리즘을 모의 프로그램으로 작성한 후에 trace를 입력으로 하여 결과를 비교해볼 수 있다.