지난 글에 이어 이번에도 CPU 스케쥴링에 대해 공부해 보겠습니다. 이번엔 스케쥴링의 기준과 스케쥴링 알고리즘에 대해 알아보는 시간을 갖도록 하겠습니다.
1. 스케쥴링 기준 (Scheduling Criteria)
CPU의 스케쥴링 알고리즘들은 서로 다른 특성을 가지고, 서로 다른 포인트에 집중하여 스케쥴링을 진행합니다. 그래서 특정 상황에서 스케쥴링 알고리즘을 선택하기 위해서는 각 알고리즘들의 특성들을 이해하고 있어야 합니다. 스케쥴링 알고리즘을 비교하여 선택하기 위해서는 여러 가지 기준들이 필요하며, 이 기준들에 따라 선택되는 알고리즘이 크게 바뀔 수 있기 때문에, 최선의 알고리즘을 선택하기 위해서는 명확한 기준을 세우는 것이 중요합니다. 여기서는 6가지 기준에 대해 알아보겠습니다.
1. CPU Utilization (CPU 이용률): 우리는 CPU가 가능한 모든 시간에 일을 하기를 바랍니다. 다시 말해 CPU가 작동하지 않는 시간을 최대한 줄이고자 한다는 것입니다. 개념적으로 아예 사용을 안하는 0%부터, 모든 시간에 작동을 하는 100%까지 이용률을 계산할 수 있으며, 실제 실행에서는 30~40% 정도의 이용률을 갖습니다.
2. Throughput (처리량): 처리량은 단위 시간 당 완료되는 process의 작업의 수입니다. 좋은 스케쥴링 알고리즘은 처리량을 최대화할 수 있어야 합니다.
3. Turnaround Time (총처리 시간): 이번에는 CPU가 아닌 process의 입장에서 생각해 보겠습니다. Process의 관점에서 좋은 알고리즘은 자기 자신이 가장 빠르게 처리될 수 있는 알고리즘일 것입니다. 총 처리 시간이란, process가 CPU를 할당받기 위하여 제출된 시간으로부터 작업이 완료될 때까지의 시간입니다. 여기에는 메모리에 들어가기 위해 기다리는 시간, ready queue에서의 대기 시간, CPU에서 실행되는 시간, 입출력 연산을 수행하는 시간까지 모두 포함됩니다.
4. Waiting Time (대기 시간): 사실 스케쥴링 알고리즘은 process가 CPU에서 실행되는 총 시간의 합이나, 메모리에 들어가는 시간 등에는 전혀 영향을 미치지 못합니다. 대기 시간은 스케쥴링 알고리즘이 직접적으로 영향을 미칠 수 있는 ready queue에서 대기하는 시간의 총합 만을 의미합니다.
5. Response Time (응답 시간): Interactive system(대화식 시스템)에서는 총처리 시간보다 얼마나 빠르게 응답을 받는가가 가장 좋은 기준이 될 수 있습니다. 따라서 응답 시간이란 process가 제출된 시점으로부터 첫 번째 응답이 온 시점까지의 시간을 뜻합니다.
6. Fairness (공정성): 마지막으로 공정성이란 각 process들이 얼마나 공평하게 CPU를 나누어 사용하는가를 의미합니다.
당연하지만, 좋은 알고리즘은 CPU 이용률, 처리량, 공정성을 최대화하고, 총처리 시간, 대기 시간, 응답 시간은 최소화하는 알고리즘을 뜻합니다.
2. Scheduling Algorithm
본격적으로 스케쥴링 알고리즘들에 대해 하나씩 알아보도록 하겠습니다.
1. FCFS Scheduling (First-Come, First-Served Scheduling / 선입 선처리 스케쥴링)
FCFS는 말그대로 들어온 순서대로 처리해주는, 먼저 오면 먼저 처리해주는 선착순 알고리즘입니다. 앞에서 선점(preemptive) 알고리즘과 비선점(Nonpreemptive) 알고리즘에 대해 공부한 걸 기억하실 것이라 생각합니다. FCFS 알고리즘은 대표적인 비선점 스케쥴링 알고리즘 중 하나입니다. 간단하고 구현이 쉽다는 장점이 있으며, 도착한 순서대로 ready queue에 차곡차곡 들어가게 되고, 제일 앞의 process부터 CPU를 할당받게 됩니다. 하지만 평균적인 대기 시간이 길다는 단점이 있습니다. 먼저 온 process가 먼저 실행되기 때문에 먼저 온 process가 실행 시간이 정말 긴 process라면 뒤에 도착한 process들은 정말 금방 끝나는 process들이라 하더라도 먼저 온 process가 완료될 때까지 기다려야 하기 때문입니다. 이러한 현상을 Convoy Effect (호위효과)라고 부르며, 평균 대기 시간을 늘리는 주범이 됩니다.
2. SJF Scheduling (Shortest-Job-First Schedulinig / 최단 작업 우선 스케쥴링)
이 Convoy Effect는 하나의 긴 process가 완료되는 것을 다른 모든 process들이 기다리는 현상을 말합니다. 그리고 이 convoy effect를 해결하는 가장 좋은 방법은 가장 짧은 작업, 즉, 남은 CPU burst time (CPU 작업 시간)이 가장 짧은 process를 먼저 실행하는 것입니다. SJF를 통해서 FCFS에 비해 대기 시간을 비약적으로 줄일 수 있습니다.
또한 SJF는 스케쥴링 정책에 따라 선점 알고리즘이 될 수도 있고 비선점 알고리즘이 될 수도 있습니다. Ready queue에 들어온 process의 CPU 작업 시간이 현재 CPU에서 실행 중인 process의 잔여 작업 시간보다 적을 때 선점을 하여 CPU를 빼앗게 되면 선점 알고리즘이 되는 것이고, 선점을 하지는 않고 ready queue 내에서만 우선순위에 따라 실행 순서를 정하면 비선점 알고리즘이 되는 것입니다. 이 중 선점형 SJF 알고리즘은 Shortest Remaining Time First Scheduling (최소 잔여 시간 우선 스케쥴링)이라고도 불립니다.
그렇다면 아직 실행되지도 않은 process의 CPU 작업 시간은 어떻게 아는 것일까요? Process의 CPU 작업 시간을 계산하는 것은 굉장히 어렵습니다. 그래서 이 전의 CPU 작업 시간을 이용하여 다음 작업 시간을 예측하는 방법을 사용합니다. 과거의 작업 시간도 꽤 많은 데이터가 있을 것인데, 최근의 작업 시간과 전체 과거의 작업 시간을 따로 계산하여, 두 값에 가중치를 부과하여 합하는 형식으로 작업 시간을 계산합니다.
3. Priority Scheduling (우선 순위 스케쥴링)
우선 순위우선순위 스케쥴링은 모든 process들에게 나름의 우선순위를 부여하는 스케쥴링으로, SJF 스케쥴링 알고리즘은 CPU 작업 시간을 기준으로 우선순위를 부여한 우선순위 스케쥴링의 한 종류입니다. 또한 FCFS 스케쥴링 알고리즘은 모든 process들의 우선순위가 동등한 형태의 우선순위 스케쥴링 알고리즘으로 볼 수도 있습니다. 우선순위 스케쥴링에서는 숫자가 낮을수록 높은 우선순위를 가집니다. 이러한 우선순위는 CPU 작동 시간이라던지, 시간제한, 열린 파일의 수 등 내부적인 우선순위와, program에 있어서 해당 process이 가지는 중요성, 컴퓨터 사용에 관한 우선순위 등 외부적인 우선순위로 정의될 수 있습니다. 우선순위 스케쥴링 역시 SJF에서 설명한 바와 같이 선점 스케쥴링이 될 수도 있고 비선점 스케쥴링이 될 수도 있습니다.
우선순위 스케쥴링의 가장 큰 문제점은 바로 Starvation(기아) 문제입니다. Indefinite Blocking (무한 봉쇄)라고도 불리는 이 문제는 바로 우선순위가 낮은 process들이 다른 높은 우선순위의 process들이 계속 들어오는 바람에 시간이 아무리 흘러도 실행될 기회를 잡지 못하는 상태를 말합니다. 이러한 starvation 문제를 해결하는 한 가지 해결방법은 바로 Aging(노화)입니다. Aging은 낮은 우선순위의 process들이 일정 시간동안 실행되지 못하면 우선순위를 조금 높여주는 방법입니다. 시간이 흐르게 되면 아무리 낮은 우선순위의 process더라도 결국에는 우선순위를 높여 실행될 수 있게 됩니다.
4. Round-Robin Scheduling
Round Robin (RR) 스케쥴링은 시간을 할당하여 스케쥴링을 하는 방법입니다. FCFS와 유사하지만, 선점 스케쥴링을 결합한 방식인데, 여기서는 Time Quantum(시간 할당량)이라는 시간 단위의 개념을 정의하여 이용합니다. Ready queue는 FCFS처럼 관리되기 때문에 새로운 process가 들어오면 queue의 가장 뒤에 추가됩니다. 우선 time quantum에 해당하는 시간을 정합니다. 예를 들자면 1초면 1초, 0.1초면 0.1초와 같은 형식으로 말이죠. 그리고 ready queue의 가장 앞에 있는 process가 선택되고, CPU에서 time quantum 만큼 실행됩니다. Time quantum만큼 실행된 뒤에 아직 process의 작업이 완료되지 않았다면, 작업을 멈추고 ready queue의 제일 뒤로 돌아가서 차례를 기다리게 됩니다. 그리고 ready queue의 제일 앞에 있는 process가 다시 time quantum만큼 CPU에서 수행이 됩니다. 이 time quantum을 너무 길게 잡으면 FCFS와 같은 형태가 될 수 있고, 너무 작게 잡으면, context switch가 자주 발생하게 되어 성능이 떨어지게 됩니다. 그래서 적절한 시간의 time quantum을 설정해 주어야 하며 당연히 context switch에 걸리는 시간보다는 time quantum이 훨씬 길어야 합니다.
5. Multilevel Queue Scheduling (다단계 큐 스케쥴링)
마지막으로 알아볼 내용은 다단계 피드백 큐 스케쥴링입니다. 다단계 큐 스케쥴링에서는 여러개의 queue를 계층적으로 이용하여 구현을 합니다. 각 queue들은 각각의 스케쥴링 알고리즘들을 가지는 독립적인 queue입니다. 모든 process들은 메모리 크기, process의 우선 순위, process 유형 등과 샅은 특성에 따라 한 개의 queue에 영구적으로 할당됩니다. 그래서 CPU에 할당받기 위해서는 자신이 배정된 queue에만 들어갈 수 있습니다. 다단계 큐 스케쥴링에서는 queue들 사이에도 우선순위 스케쥴링이 되어있어 상위에 있는 queue의 process들이 우선순위가 높아 먼저 CPU를 할당받으며, 반드시 자신 보다 상위에 있는 queue가 비어있을 때에만 스케쥴링을 시작합니다.
하지만 이러한 다단계 큐 스케쥴링에서 역시 starvation 문제가 일어날 가능성이 높습니다. 그래서 Multilevel Feedback Queue Scheduling (MFQS / 다단계 피드백 큐 스케쥴링)이라는 것이 존재합니다. MFQS에서는 aging을 통해 queue들 사이에서의 process의 이동을 허용해서 일정 시간동안 실행이 되지 않으면 상위 레벨의 queue로 승격시켜 언젠가는 실행이 되도록 하는 구조입니다. MFQS에서는 들어올 때는 할당된 queue가 아닌 가장 상위의 queue로 들어와서 실행 시간이 긴 process들은 아래 층으로 이동하게 됩니다. 그 외의 실행은 다단계 큐 스케쥴링과 유사합니다.
이것으로 CPU 스케쥴링에 대한 공부를 마쳤습니다. 현재도 더 좋은 스케쥴링을 위해 연구가 계속되고 있는 만큼 더 확실하게 알고 넘어가면 좋을 것 같습니다. 읽어주셔서 감사합니다.