운영체제의 핵심은 하드웨어 자원을 응용프로그램으로부터 보호하는 것도 있지만 여러 프로그램들이 공정하게 하드웨어 자원(CPU, 메모리)등을 균등하게 사용할 수 있게 도와주는 역할을 합니다. 우리의 컴퓨터를 보면 여러가지가 프로그램이 프로세스의 형태로 메모리에 적재되어 있는 것을 확인할 수 있습니다. 그리고 하나의 코어를 가진 CPU는 프로세스를 한번에 하나씩만 처리를 할 수 있습니다. 그러면 운영체제는 어떻게 프로세스들에게 순서를 정해주는지 알아보겠습니다.
CPU 스케줄링이란?
우리는 앞선 프로세스는 무엇이고 어떻게 관리될까 포스트를 통해서 프로세스는 여러 상태를 가진다는 것을 배웠습니다. 그 중에서 운영체제는 Ready 상태에 있는 프로세스들 중에서 가장 우선순위가 높은 프로세스에게 CPU를 부여합니다. 이 과정에서 Dispatcher 를 통해 프로세스가 실행가능한 상태로 변경됩니다.(프로세스 상태를 Ready에서 Run으로 변경 및 기존에 실행되던 프로세스와 컨텍스트 스위칭 발생)
CPU 스케쥴링의 종류
cpu 스케줄링은 선점형 스케줄링 과 비선점형 스케줄링 으로 구분됩니다. 선점이라는 말은 “남보다 앞서서 차지하는 것”의미하며 해당 용어를 운영체제 관점에서 바라보면 현재 실행 중인 프로세스나 태스크를 강제로 중단시키고 다른 프로세스나 태스크를 실행하는 것을 나타냅니다. 비선점 스케줄링은 기존의 작업이 마무리되고 난후에 다른 프로세스가 수행되는 스케줄링 기법입니다. 이 둘을 비교하는 표를 보면 이해가 조금더 쉬울 것 같습니다.
| 선점형 스케줄링 | 비선점형 스케줄링 | |
|---|---|---|
| 개념 | 실행 중인 프로세스를 중단하고 우선순위가 높은 프로세스를 실행함 | 실행 중인 프로세스가 끝날 때까지 다른 프로세스로 변경하지 않음 |
| 프로세스 변경 시점 | 우선순위가 높은 프로세스가 도착하거나, 특정 조건(시간 초과 등)이 발생할 때 | 현재 실행 중인 프로세스가 작업을 완료한 후 |
| 응답 시간 | 짧음: 우선순위가 높은 프로세스를 빠르게 처리 가능 | 길어질 수 있음: 우선순위가 낮은 프로세스가 실행 중일 경우 대기 시간이 증가 |
| 복잡도 | 상대적으로 높음: 문맥 교환(Context Switching)이 빈번히 발생함 | 상대적으로 낮음: 문맥 교환이 적음 |
| CPU 이용률 | 더 높을 수 있음: 짧은 작업들을 빠르게 처리하여 CPU를 효율적으로 사용 | 낮을 수 있음: 긴 작업이 끝날 때까지 다른 프로세스들이 대기 상태에 머무를 수 있음 |
| 예시 알고리즘 | Round Robin, SRTF(Shortest Remaining Time First), Priority Scheduling | FCFS(First-Come, First-Served), SJF(Shortest Job First) |
| 장점 | 우선순위 높은 작업을 신속히 처리 가능, 긴급 작업에 유리 | 문맥 교환 오버헤드가 적고, 알고리즘이 단순하여 구현과 관리가 쉬움 |
| 단점 | 문맥 교환 오버헤드로 인해 시스템 성능 저하 가능 | 우선순위가 낮은 작업은 기아(Starvation) 상태에 빠질 수 있음 |
💡 CPU 스케줄링은 어떻게 성능을 평가할까?
CPU 스케줄링은 시스템 관점에서와 사용자 관점에서 성능 평가요소가 있습니다. 시스템 관점에서는 CPU가 프로세스를 얼만큼 잘 처리했는지를 파악하는 것이 핵심이고 사용자 관점에서는 실행한 프로세스가 원할하게 CPU를 얻고 사용했는지 파악하는 것이 핵심입니다.시스템 관점 성능평가 요소
- CPU 이용률 : 전체 시간 중에서 CPU가 일을 한 시간의 비율을 의미
- 프로세스 처리량 : 단위 시간 동안 ready 상태인 프로세스들을 얼만큼 처리했는지
사용자 관점 성능평가 요소
- 소요시간(Turnaround Time) : 프로세스가 ready 상태로 기다린 시간 + cpu를 사용한 시간
- 대기시간(Waiting Time) : CPU 버스트 기간 중 프로세스가 ready 상태로 기다린 시간
- 응답시간(Response Time) : CPU를 처음 얻기까지 걸린 시간
FCFS(First-Come First-Service)
편의점에 음료가 소비되는 것처럼 Ready 큐에 도착한 순서대로 작업을 먼저 처리하는 스케줄링 알고리즘입니다. 저희가 주로 사용하는 자료구조인 Queue를 생각하면 이해하기 쉬울 것 같습니다. FCFS는 비선점형 스케줄링으로 겉으로 보기에는 공정하다고 느껴질 수 있습니다.
하지만 빠르게 처리할 수 있는 프로세스가 작업시간이 긴 프로세스 뒤에 오게 되면 해당 작업이 모두 마무리 된 후에 작업을 수행할 수 있습니다. 또한 해당 알고리즘은 요청이 작업이 들어온 순서에 따라서 프로세스의 대기시간이 천차만별로 달라질 수 있다는 특징이 있습니다.
SJF(Shortest Job First)
SJF는 FCFS의 단점인 작업시간이 적은 프로세스의 작업이 긴대기시간을 가질 수 있다는 점을 개선하기 위해 등장한 CPU 스케줄링 알고리즘입니다. SJF는 선점형 방식과 비선점형 방식으로 구현이 될 수 있으며 해당 알고리즘에서는 작업 처리 시간이 작은 작업을 우선을 처리합니다.
이상적으로 보았을 때 작업량이 적은 일부터 빠르게 처리해나가면 프로세스마다 평균 대기시간도 줄어들어 효율적인 스케줄링 기법으로 볼 수 있습니다. 하지만 지속적으로 작업시간이 적은 프로세스가 ready 큐에 들어오게 된다면 긴 작업 시간을 가진 프로세스는 CPU를 할당받지 못하는 현상이 발생할 것 입니다. 이를 기아 현상(starvation)이라고 합니다.
💡 운영체제는 프로세스의 작업량(작업시간)을 어떻게 알 수 있을까?
운영체제는 프로세스의 작업처리 시간을 미리 알 수 없습니다. 그래서 이전 작업 정보를 통해서 예측하는 방안으로 프로세스의 작업시간을 파악합니다.
Priority Scheduling
우선순위 스케줄링은 프로세스의 우선순위를 정해 작업을 처리하는 기법입니다. 우선순위는 정수의 값으로 관리하며 운영체제는 해당 우선순위 값을 기준으로 프로세스의 순서를 결정합니다. 우선순위 스케줄링 역시 선점형 방식과 비선점형 방식으로 구현이 가능합니다.
우선순위 스케줄링 기법의 경우도 SJF 알고리즘과 마찬가지로 기아 현상이 발생합니다. 예를 들면 사용자 프로세스 보다는 커널에 처리하는 프로세스가 보편적으로 우선순위가 높은데 지속적으로 커널 프로세스의 작업 요청이 발생하면 사용자 프로세스는 후순위로 밀리게 됩니다. 우선순위 스케줄링을 이와 같은 문제를 해결하기 위해서 Aging 기법을 도입해 기아현상을 발생하지 않도록 도와줍니다. Aging 기법은 프로세스가 대기 큐 속에서 우선순위가 계속 유지되는 것이 아닌 점진적으로 증가시키는 방법입니다.
RR(Round Robin)
라운드 로빈 스케줄링은 프로세스에 동일한 크기의 CPU 사용시간을 할당해 주는 방식입니다. 해당 방식은 Time quantum이 설정해 해당 시간이 넘어가기 되면 다른 프로세스로 전환하는 스케줄링 기법입니다. 그렇기에 Time quantum을 잘 설정하는 것이 중요합니다.
Time quantum을 프로세스 처리 시간이 비해 길게 설정한다면 결국 FCFS와 같은 방식으로 동작을 하게 될 것이고 반대로 Time quantum을 너무 짧게 설정한다면 해당 잦은 컨텍스트 스위칭에 대한 오버해드가 발생합니다. 그렇기에 프로세스를 처리하기 시작해 I/O로 전환되는 시점까지를 예측해 설정하는 것이 가장 최선의 방법일 것있습니다.
Multi-level Queue
앞선 스케줄링 알고리즘들은 하나의 대기 큐를 활용했다면 Multi-level Queue는 이름과 같이 여러 개의 대기 큐를 이용한 방식입니다. 여러 대기 큐들은 서로 다른 우선순위를 가지고 있습니다. 그래서 높은 우선순위를 가지는 작업들은 높은 우선순위의 대기 큐에 들어가고 낮은 우선순위를 가지는 프로세스들은 낮은 우선순위의 대기 큐에서 관리됩니다.
각 대기 큐 내부에서는 주로 각각의 다른 스케줄링 알고리즘을 활용합니다. 높은 우선수위를 가지는 대기 큐에서는 빠르게 작업들을 전환하기 위해서 라운드 로빈(RR) 스케줄링을 활용하고 Batch 프로세스와 같이 CPU 연산 비율이 높은 프로세스를 관리하는 낮은 우선순위의 대기 큐에서는 주로 FCFS 방식을 통해 불필요한 컨텍스트 스위칭의 오버해드를 줄입니다.
한정된 CPU에서 여러 큐의 작업들을 번갈아가면서 작업하기 위해서는 큐들을 대상으로도 스케줄링이 필요합니다. 큐들간의 스케줄링 기법에는 고정 우선순위 방식 과 타임 슬라이스 방식 이 있습니다. 고정 우선순위 방식은 큐별로 우선순위를 정해놓고 처리하는 방안이고 타임 슬라이스 방식의 경우는 큐에 대한 기아현상을 방지하는 방안으로 각 큐에 CPU 활용 시간을 비율로 나누어서 활용하는 방안입니다.
Multi-level Feedback Queue
다단계 피드백 큐 스케줄링 방식과 다단계 큐 스케줄링 방식은 비슷하면서도 차이가 있습니다. 다단계 큐 스케줄링 방식은 여러 큐 들의 프로세스가 CPU를 할당 받는 비율을 다르게 해서 처리하는 방식이라면 다단계 피드백 큐 스케줄링 방식은 프로세스가 하나의 큐에만 있는 것이 아닌 다른 큐로도 이동이 가능한 스케줄링 기법입니다. 각 큐들간에 이동은 설계하기 나름이 될 것입니다. (상위 큐에서 하위 큐로 이동이 가능하고 하위 큐에서 상위 큐로 이동이 가능할 것입니다.)
상위 큐에서 하위 큐로 이동하는 예를 들어 보겠습니다. 큐1과 큐2는 라운드 로빈 기법을 활용하고 큐3는 FCFS 기법을 활용한다고 하겠습니다. 프로세스가 처음으로 대기 큐에 진입하면 가장 우선순위가 높은 큐에서 대기를 하면 CPU를 할당받습니다. 해당 프로세스가 CPU를 할당 받고도 작업이 완료되지 않는다면 큐2로 이동해 대기합니다. 이후에 CPU를 더 할당 받고도 해당 프로세스가 완료되지 않는다면 cpu 작업이 많은 프로세스라고 판단해 큐3로 보내져 문맥교환이 발생하지 않는 방식으로 프로세스를 처리해 나갑니다.
반대로 하위 큐에서 상위 큐로 이동을 하는 예시로는 각 프로세스 마다 Aging 기법을 통해 age가 높은 프로세스들을 상위 큐로 이동시키는 방법이 있습니다.
정리
- 운영체제는 여러 프로세스가 CPU를 공정하게 사용할 수 있게 CPU 스케줄링을 처리합니다.
- CPU 스케줄링 기법에는 선점형 방식과 비선점형 방식으로 구분되며 선점형 방식은 기존의 프로세스를 멈추고 우선순위가 높은 프로세스가 실행되는 방식이며 비선점형 방식은 실행되는 프로세스가 종료된 후 다음 프로세스를 처리하는 방식입니다.
- FCFS 스케줄링은 프로세스가 대기 큐에 들어온 순서대로 작업을 처리하는 방식입니다.
- SJF 스케줄링은 프로세스 처리 시간이 짧은 작업부터 수행하는 방식입니다.
- priority 스케줄링은 각 프로세스 마다 우선순위를 통해 작업을 수행하며 Aging 기법을 통해 기아현상을 방지합니다.
- Round Robin 스케줄링은 time quantum을 두어 프로세스가 주어진 시간동안에만 CPU를 할당 받는 방식입니다.
- Multi-level queue 스케줄링 기법은 여러 대기 큐를 통해서 프로세스를 관리하는 스케줄링으로 대기 큐간의 우선순위를 관리합니다.
- Multi-level feedback queue 스케줄링 기법은 프로세스가 하나의 큐에만 속하는 것이 아닌 다른 큐로 이동이 가능한 기법입니다.
참고자료
- https://www.geeksforgeeks.org/first-come-first-serve-cpu-scheduling-non-preemptive/
- https://www.geeksforgeeks.org/program-for-shortest-job-first-or-sjf-cpu-scheduling-set-1-non-preemptive/
- https://www.geeksforgeeks.org/program-for-round-robin-scheduling-for-the-same-arrival-time/
- https://www.geeksforgeeks.org/multilevel-queue-mlq-cpu-scheduling/
- https://www.geeksforgeeks.org/multilevel-feedback-queue-scheduling-mlfq-cpu-scheduling/
