1. Scheduling Algorithms
CPU를 공평하게 나누어 주는 것도 좋지만 사용자와 상호작용하는 작업에 CPU를 우선적으로 주는 방향으로 이루어져야 하는 것이 중요한데요 이를 위해서 CPU 스케줄링은 두 가지 정도를 고려해볼 수 있습니다.
우선 CPU burst에 들어온 프로그램들이 여럿 있는데 어떤 프로그램에게 CPU를 줄 것인가를 결정하는 문제가 있을 것입니다.
그리고 또 다른 하나는 프로그램에게 CPU를 주었을 때, 이 프로그램 작업 동안 CPU를 계속 줄지, 아니면 중간에 CPU를 뺏어서 다른 프로세스에게 CPU를 넘겨줄지에 대한 문제입니다.
만약 CPU를 한 프로그램에게 주었다면 그 프로그램이 CPU를 다 쓰고 I/O 작업을 하러 나갈 때까지 CPU를 다른 프로그램에서 사용하지 못하게 됩니다. 그래서 CPU brust가 굉장히 긴 프로그램에 한번 CPU가 넘어가게 되면, 뒤에 I/O burst job들은 CPU를 금방 쓰고 나갈 프로그램들인데도 불구하고 오래 기다려야하는 문제가 생기는 것입니다.
위와 같은 이유로 CPU 스케줄링 알고리즘의 방식은 크게는 비선점형(nonpreemptive)와 선점형(preemptive) 두 가지로도 나누어 볼 수 있습니다.
비선점형(nonpreemptive) 스케줄링은 프로그램에 CPU를 주었다면 뺏지 않는 방법입니다.
반면, 선점형(preemptive) 스케줄링은 프로그램에 CPU를 주었다해도 언제든지 뺏어올 수 있는 방법입니다. 현대적인 CPU 스케줄링은 거의 대부분 선점형 스케줄링을 사용하고 있습니다.
그래서 어떻게 하는 것이 더 효율적인 스케줄링인지를 결정하는 여러 가지 CPU 스케줄링 알고리즘에 대해 설명하겠습니다.
(1) FCFS(First-Come-First-Served)
먼저 온 순서대로 먼저 처리하는 알고리즘입니다. 만약 CPU를 굉장히 오래쓰는 프로세스가 먼저 도착해 CPU 제어권을 잡게 되면 CPU를 짧게 쓰는 프로그램(Interactive job)들이 들어와도 오래 기다려야하는 문제가 생기기 때문에 효율적이지는 않습니다.
예를 들어, 위 그림과 같이 프로세스가 P1, P2, P3가 간발의 차이로 도착한다고 가정을 하면 P3는 27초를 기다린 후에야 CPU를 얻을 수 있는 것입니다.
만약 P2, P3, P1 순으로 도착하면 각각의 대기 시간은 P1은 6초, P2는 0초, P3는 3초로 평균 3초의 대기시간을 가지며 도착 순서에 따라 평균 대기 시간이 많이 차이나는 것을 확인할 수 있습니다.
정리하자면 FCFS는 비선점형 스케줄링으로 CPU를 얻으면 작업이 완료되기 전까지 뺏기지 않습니다. 이렇게 먼저 도착한 긴 프로세스 때문에 나중에 도착한 다른 프로세스가 오래 기다려야하는 상황을 Convoy Effect라 합니다.
(2) SJF(Shortest Job First or Shortest Remaining Time First)
CPU를 사용하고자 하는 시간이 가장 짧은 프로세스에게 CPU 제어권을 넘겨주는 알고리즘입니다. Burst time이 짧은 프로세스가 앞에 위치하기 때문에 Queue가 전체적으로 짧아지고 평균 대기 시간이 가장 적습니다.
SJF는 비선점형과 선점형 방식으로 나누어 볼 수 있습니다.
(1) 비선점형 SJF
SJF의 비선점형 방식은 현재 기다리는 프로세스 중에서 가장 짧게 실행되는 프로세스에게 CPU를 넘겨주었을 때, 더 짧은 프로세스가 도착하더라도 CPU를 내놓지 않는 것입니다.
프로세스의 도착 시간이 같다면, Burst time 이 짧은 순으로 실행되는 것을 알 수 있습니다.
(2) 선점형 SJF
선점형 스케줄링은 다른 프로세스에게 CPU를 넘겨주어도 더 짧은 프로세스가 오면 CPU 제어권을 빼앗을 수 있습니다. 그래서 비선점형 방식보다 대기 시간이 더 짧습니다.
0초에 도착해있는 프로세스는 P1밖에 없어서 1번을 실행합니다. 실행 중에 P2가 도착했는데 P2의 남은 실행 시간이 더 짧아 P2에게 CPU가 넘어갑니다. P2 실행중 P4, P3가 도착했지만 남은 실행 시간이 더 길기에 P2 다음으로 실행되게 됩니다. 이후 같은 과정으로 프로세스가 실행되게 됩니다.
SJF 스케줄링의 문제점
1. Starvation(기아 현상)
SJF는 CPU 사용시간이 짧은 프로세스에게 먼저 CPU 제어권을 넘겨주기 때문에, 사용 시간이 긴 프로세스는 무한하게 기다리는 상태가 될 수도 있습니다.
2. CPU 사용 시간을 미리 알 수 없다.
프로그램이 실행이 되다 보면, 위와 같이 계속해서 사용 시간이 짧은 프로세스가 들어온다고 하면 미리 사용 시간과 종료시간을 계산하기가 매우 힘듭니다. 과거의 CPU 사용을 이용해 예측하는 방법인 Exponential averaging을 통해 대략적으로 추정할 수는 있습니다.
Exponential averaging 더보기
(3) Priority Scheduling
우선 순위가 높은 프로세스에게 CPU를 넘겨줍니다. Priority Scheduling도 선점형과 비선점형으로 나뉘는데, SJF와 비슷하게 중간에 CPU를 뺏으면 선점형, 빼앗지 못하면 비선점형 스케줄링으로 나뉩니다.
SJF와 비슷하게 우선 순위가 낮은 프로세스는 영원히 실행이 되지 못하는 Starvation 문제가 발생할 수 있습니다. 이 문제를 해결하기 위해 aging을 해줍니다. 단어 그대로 나이를 부여하는 것인데, 우선 순위가 낮더라도 오래 기다리게 되면 aging 기법을 통해 우선 순위를 높여 언젠가는 CPU를 얻게 됩니다.
(4) Round Robin(RR)
현대적인 컴퓨터 시스템에서 사용하는 스케줄링은 Round Robin에 기반하고 있습니다.
CPU를 넘겨주기 전에 CPU 할당 시간을 정하고, 그 시간이 끝나면 Timer Interrupt에 의해 CPU 제어권을 넘겨주고 Ready Queue에 다시 줄을 서게 되고, 그럼 그 다음 프로세스가 위 과정을 반복하는 방식입니다.
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지기 때문에 가장 큰 장점은 응답 시간(CPU를 최초로 얻기까지의 시간)이 빠르다는 것입니다. 조금씩 CPU를 주었다가 뺏었다를 반복하기 때문에 어떤 프로세스던지 짧은 시간만 기다리면 적어도 한 번은 CPU 제어권을 얻게 됩니다.
또 다른 특징은 CPU의 사용 시간과 CPU를 기다리는 시간이 비례한다는 것입니다. CPU를 짧게 쓰는 프로세스는 짧게 쓰고 빠지기 때문에 기다리는 시간도 짧지만, CPU를 길게 써야하는 프로세스는 짧은 프로세스들이 끝나는 것도 대기해야하기 때문에 대기 시간이 길어지게 됩니다.
단점으로는 할당 시간(time quantum)을 매우 크게 잡으면 FCFS와 같은 스케줄링 알고리즘이 되어버리는 것입니다. 그렇다고 지나치게 할당 시간을 작게 잡으면 계속 CPU 제어권이 이동하게 되고, 그렇게 되면 context switching이 자주 발생해 overhead가 커집니다. 따라서 적당한 규모의 할당 시간을 주는 것이 좋습니다. (일반적으로 10 -100 milliseconds)
위 그림은 할당 시간이 4ms라고 했을때의 Round Robin 을 가정한 것입니다. 4ms안에 끝나는 P2, P3는 빨리 빠져나가는 것을 볼 수 있습니다.
즉 Round Robin은 SJF 스케줄링보다 Turn around나 waiting time은 길 수도 있지만, Response Time은 짧습니다.
Round Robin은 CPU 사용 시간이 짧은 프로세스와 긴 프로세스가 마구잡이로 섞여있을 때 효율적인 스케줄러입니다. 만약 모든 프로세스의 CPU 사용 시간이 같다면, 한 시점에 모든 프로세스가 몰려서 끝나는 문제가 생길 수 있기 때문입니다.
(5) Multilevel Queue Scheduling
위에서의 스케줄링 알고리즘은 Ready Queue에 한 줄로 세웠지만, 지금의 Multilevel Queue나 아래의 Multilevel feedback Queue에서는 여러 줄로 프로세스를 관리합니다.
Ready queue를 여러 줄로 분할하여 foreground에는 interactive job을 넣고 background에는 batch(no human interaction) job을 넣습니다.
그림에서 위에 위치할수록 우선 순위가 높고 아래에 있을수록 우선 순위가 낮습니다. 그리고 각 Queue는 독립적인 스케줄링 알고리즘을 가집니다. foreground에는 응답 시간을 짧게 하는 것이 중요하기 때문에, Round Robin 스케줄링을 가지고, background에는 사용자와의 상호 작용보단, CPU를 오래 사용하는 프로세스가 들어있기에 FCFS 스케줄링을 합니다.
이렇게 Queue 별로 알고리즘을 배치하면 각 Queue에 대한 스케줄링이 필요합니다. 우선 순위로 각 Queue를 배치하면, SJF 스케줄링과 Priority 스케줄링과 비슷하게 Starvation 문제가 생길 수 있습니다. 이를 방지하기 위해 두 가지 정도의 방법이 있습니다.
1. Fixed Priority Scheduling
첫째는 foreground의 우선 순위를 극단적으로 높이는 것입니다. foreground의 우선 순위를 크게 높이면, foreground queue가 비는 것이 더 원활해지고 그때 background에 있는 queue가 돌아가게 하는 것입니다.
2. Time Slice
다른 방법은 시간 단위로 분배하는 것입니다. CPU time을 적절한 비율로 각 Queue에 할당하는 것인데, 보통 foreground에 80%, background에 20%정도로 foreground에 많은 시간을 투자합니다.
(6) Multilevel feedback Queue Scheduling
우선 순위가 가장 높은 queue는 Round Robin으로 할당 시간(Time Quantum)을 굉장히 짧게 주고, 밑으로 갈수록 할당 시간을 점점 길게 주며 제일 아래 queue는 FCFS 방식을 사용하는 스케줄링입니다.
CPU 사용 시간이 짧은 프로세스에게 우선 순위를 높게 주는 방식으로, CPU 사용 시간이 긴 프로세스는 점점 밑으로 쫓겨나게 됩니다. 아래에 있는 Queue로 갈 수록 할당 시간이 더 길게 부여되지만 Queue간의 우선 순위에서는 위의 Queue가 먼저 끝나야 아래의 Queue가 실행될 수 있습니다.
2. Multiple-Processor Scheduling
지금까지 살펴본 알고리즘은 CPU가 하나일 때의 스케줄링 기법이었다면, 이제 다중 프로세서 시스템에서의 스케줄링 기법을 알아보겠습니다. 다중 프로세서 시스템에서는 여러 개의 CPU가 동시에 동작하며 프로세스를 처리합니다. 이를 효율적으로 관리하기 위한 여러가지 스케줄링 기법에 대해 설명드리겠습니다.
(1) Homogeneous Process
Queue에 한 줄로 세워서 각 프로세스가 알아서 꺼내가게 하는 방법입니다. 그러나 특정 CPU에서만 실행되어야하는 프로세스가 있다면 문제가 복잡해집니다.
(2) Load Sharing(Load balancing)
특정 CPU에 일이 몰리지 않게 각 CPU에게 골고루 일을 하도록 하는 것입니다. 몇 개의 CPU가 과부하되어 작업이 몰리지 않도록 하는 것이 목적입니다.
(3) Symmertic Multiprocessing(SMP, 대칭 다중 처리)
모든 CPU가 대등하게 일을 처리하며, 각 CPU는 자체 스케줄링을 수행하는 방식입니다. 각 CPU가 독립적으로 작업을 처리하므로 병렬처리가 가능하고 대규모 계산이나 병렬 처리가 필요한 작업에 적합합니다.
(4) Asymmetric Multiprocessing(ASMP, 비대칭 다중 처리)
여러 CPU가 있는데 하나의 CPU가 전체적인 컨트롤(데이터의 접근, 공유)를 담당하고 나머지 CPU는 그에 맞게 수동적으로 스케줄링을 따릅니다.
3. Real-Time Scheduling
실시간 스케줄링은 프로세스들이 특정 시간(데드라인) 내에 실행되어야하는 환경에서 사용됩니다. 주로 시간에 민감한 응용 프로그램을 다루는 데에 적합합니다.
(1) Hard real-time systems
데드라인이 있어서 정해진 시간 안에 반드시 끝내도록 스케줄링해야하는 시스템입니다. 시간을 준수하지 않으면 큰 문제가 생길 수 있어서 엄격한 제한이 있는 환경에서 사용합니다.(ex. 실시간 제어 시스템, 항공 우주 시스템, 의료 장비 등)
(2) Soft real-time computing
반드시 정해진 시간 내에 끝내야하는 것은 아니지만, 높은 우선 순위를 갖게하는 시스템입니다. 즉 시간에 민감한 작업이긴 하지만, 가끔씩 데드라인을 초과할 수 있는 유연성이 있는 환경에서 사용합니다. 그래서 Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖습니다.(ex. 멀티미디어 프로그램, 실시간 게임)
4. Thread Scheduling
(1) Local Scheduling
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정하는 방식입니다. 스레드 관리가 커널이 아닌 사용자 수준에서 이루어지기 때문에, 빠른 스레드 전환이 가능합니다. 하지만 사용자 수준 라이브러이에서 스케줄링이 이루어지기 때문에 운영체제가 스레드에 대한 정보를 인식하지 못하여 시간이 오래 걸리는 I/O연산 등에서 작업이 멈추면, 전체 프로세스가 멈추는 단점이 있습니다.
(2) Global Scheduling
Kernel level thread은 커널 수준의 스레드로 운영체제 커널이 스레드를 직접 관리하는 방식입니다. 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정합니다. 각 스레드에 대한 정보를 운영체제가 갖고 있기 때문에 운영체제가 스레드를 관리하고 인식할 수 있습니다.
참고자료
[KOCW 이화여대 반효경 교수님 - CPU Scheduling 2]
https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f
반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1
설명이 없습니다.
core.ewha.ac.kr
[ Chapter5 Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
