CPU 스케줄링

출처: https://choi-geonu.medium.com/%EB%B0%B1%EC%97%94%EB%93%9C-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%93%A4%EC%9D%B4-%EC%95%8C%EC%95%84%EC%95%BC%ED%95%A0-%EB%8F%99%EC%8B%9C%EC%84%B1-4-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-e684331afc77

현대에 들어서 PC의 컴퓨팅 성능이 증가하고, 이에 따라 동시에 여러 프로그램을 띄워 사용하는 일이 잦다.

운영체제 입장에서는 동시다발적으로 사용되고 있는 프로세스들에 대해, 

비록 CPU 코어가 하나라서 한 번에 하나의 프로세스 만을 실행시킬 수 있는 상황일지라도,

사용자로 하여금 모든 프로세스들이 병렬적으로 실행되고 있다는 착각을 불러일으킬 수 있어야 한다.

만약 PC를 통해 음악을 들으면서 웹서핑을 하는 상황에서,

음악 애플리케이션이 실행되는 동안 검색창에 타이핑이 안된다면 이는 운영체제의 역할을 제대로 수행하고 있지 않은 것이다.

이를 위해, 운영체제는 CPU를 할당할 작업들에 대한 스케줄링을 수행한다.

단순히 스케줄링을 수행시키는 단계를 넘어, 이를 잘 수행할 수 있어야 한다.

 

 

스케줄링의 평가 항목

그렇다면 어떻게 스케줄링을 해야 이를 잘 수행했다고 할 수 있을까?

어떤 스케줄링 기법들이 존재하는지 알아보기에 앞서,

스케줄링에서 활용되는 다양한 평가 항목에 대한 이해가 필요하다. 

대표적인 스케줄링의 평가 항목에는 다음의 요소들이 존재한다.

• 반환 시간(turnaround time): 특정 작업이 작업 목록에 도착하고, 해당 작업이 완료될 때까지 소요된 시간
• 공정성(fairness): 특정 프로세스에 치우치지 않고 모든 프로세스에 공정하게 CPU가 할당되는가
• 응답 시간(response time): 특정 작업이 작업 목록에 도착하고, 해당 작업이 착수될 때까지 소요된 시간

그 외에도 CPU 이용률, 오버헤드 등이 추가로 존재하나 해당 글에서는 위 3개에 대해서만 다루고자 한다.

 

 

스케줄링 기법의 분류 기준

스케줄링 기법들은 다양한 분류 기준을 갖는다. 간단히 이를 먼저 소개한 뒤 스케줄링 기법에는 어떤 것들이 존재하는지 소개하겠다.

선점형 vs 비선점형

선점이라는 말의 의미는,

이미 CPU를 할당받아 사용하고 있는 특정 작업에 대해 운영체제가 CPU의 제어권을 가져올 수 있는지에 대해서이다.

따라서 비선점형은 반대로 한번 CPU에 작업이 할당되면 해당 작업이 끝날 때까지 CPU의 제어권을 운영체제가 돌려받을 수 없는 경우를 말한다.

정적 vs 동적

여기서 정적과 동적이라는 말의 대상은 각 프로세스의 우선순위를 의미한다.

즉 정적 방식에서는 한번 결정된 프로세스의 우선순위가 변경되지 않는 것이고,  

반대로 동적 방식에서는 한번 결정된 프로세스의 우선순위는 이후 변경될 수 있다.

단일 대기열(queue) vs 다중 대기열

이는 말 그대로 프로세스들의 대기열이 하나인지 아니면 여러 개인지에 대한 여부이다.

 

 

스케줄링 기법의 종류

스케줄링 기법에는 다음의 기법들이 존재한다.

• FCFS 스케줄링
• SJF 스케줄링
• STCF 스케줄링
• RR 스케줄링
• MLFQ 스케줄링
• CFS 스케줄링

 

FCFS 스케줄링(FIFO)

First Come First Served의 약자로, 의미 그대로 먼저 들어온 작업 순서대로 작업을 수행시키는 것을 말한다.

해당 방식은 먼저 들어온 작업이 끝날 때까지 다른 작업을 시작하지 않는 비선점형 스케줄링이고,

프로세스 간 우선순위가 변하지 않는 정적 스케줄링이며, 단일 대기열 스케줄링이다.

먼저 들어온 작업을 최우선으로 수행하는 것은 얼핏보기에는 타당해 보이고 공정성의 측면에서도 문제가 없어 보이지만,

만약 먼저 들어온 작업이 다른 작업에 비해 과도하게 덩치가 큰 경우 문제가 될 수 있다.

CPU 스케줄링의 관점에서 공정성이란 결국 모든 프로세스들이 비슷한 수준으로 CPU를 사용할 수 있는 것이기 때문에, 

먼저 들어온 작업이 다른 작업에 비해 덩치의 차이가 존재한다면 뒤에 들어온 작업은 CPU를 거의 할당받지 못할 수도 있다.

이러한 상황을 Convoy Effect라고 하는데

해당 상황에서는 반환 시간과 응답 시간의 측면에서도 성능을 보장하기가 어렵다.

따라서 해당 방식은 단순하고 구현하기 쉽다는 장점이 있음에도 잘 사용되지 않는 방식이다.

 

SJF 스케줄링

Shortest Job First의 약자로, 말 그대로 가장 짧은 작업을 먼저 수행하는 것을 의미한다.

해당 방식은 단일 대기열로 구현된다.

또한 해당 방식은 일반적으로 비선점형으로 구현되며,

프로세스의 우선순위가 각 프로세스의 CPU 사용 시간(CPU burst time)에 대한 예측치로 결정되는 동적 스케줄링 기법이다.

SJF 스케줄링은 모든 작업이 동시에 대기열에 들어오는 상황에서는 응답 시간, 공정성의 평가 기준 상 최적의 기법이지만,

현실의 상황은 그렇지 않다. 

따라서 먼저 덩치가 큰 작업이 들어온 뒤에, 순차적으로 짧은 작업이 들어온다면

FCFS 스케줄링에서 발생했던 Convoy Effect가 동일하게 발생한다.

또한 각 작업의 CPU burst time을 정확하게 예측할 수 없다는 문제점도 존재한다.

 

STCF 스케줄링

Shortest Time-to-Completion First의 약자로,

현재 대기열에 존재하는 작업들 중 완료까지 잔여 시간이 가장 짧은 작업을 우선으로 수행시킨다.

해당 방식을 위해서는 특정 프로세스가 실행되는 와중에도 언제든지 잔여 시간이 가장 짧은 작업으로 대체될 수 있어야 하기 때문에

선점 방식의 스케줄링으로 구현해야 한다.

또한 작업의 우선순위가 실시간으로 변경될 수 있는 동적 스케줄링이면서 단일 대기열을 갖는 스케줄링이다.

해당 방식은 SJF 스케줄링과 달리, 모든 작업이 동시에 대기열에 포함되지 않더라도,

반환 시간과 공정성 만을 고려했을 때는 정말 훌륭한 방식이다.

하지만 응답 시간을 고려했을 때는 이야기가 달라진다.

잔여 시간이 상대적으로 긴 작업들은 CPU를 점유하기 위해서는 오랜 대기 시간을 가져야 하고,

이는 이미 위에서 언급한 모든 스케줄링 방식에서도 동일하게 발생하는 문제이다.

따라서 응답 시간 관점에서는 이미 소개된 스케줄링 방식들은 모두 좋은 방식은 아니다.

 

RR 스케줄링

Round-Robin의 약자로,

해당 방식은 사전에 타임 퀀텀 값이라고 불리는 시간 값을 설정한 후 모든 대기열 내 프로세스들에 대해 

타임 퀀텀만큼씩만 CPU를 점유하게 하는 방식을 사용한다.

대기열 내 존재하는 모든 작업들이 타임 권텀 값만큼 한 번씩 수행되고 나면,

위에서 언급한 과정을 계속해서 수행한다.

위와 같이 동작하는 해당 방식의 특성상 선점형이며 정적이고, 단일 대기열 스케줄링이다.

해당 방식은 공정성의 측면에서 보았을 때 정말 훌륭한 방식이다.

또한 응답 시간의 측면에서도, 위에서 이미 언급한 스케줄링 방식들에 비해 훨씬 나은 방식이다.

다만, 반환 시간의 측면에서 보았을 때는 거의 최악이다.

일반적으로 공정성을 우선시하는 방식에서는 반환 시간과 같은 평가 척도는 나쁘게 나올 수밖에 없기 때문에 발생하는 당연한 결과이다.

해당 방식은 또한 타임 퀀텀 값을 어떻게 설정하느냐에 따라서 성능이 달라진다.

만약 타임 퀀텀 값을 상대적으로 작게 가져간다면, 평균 응답 시간은 더욱 좋아질 것이다.

다만 타임 퀀텀 값이 너무 작아지게 되면, 콘텍스트 스위칭이 너무 자주 발생하여 성능 상 좋지 못한 결과를 얻을 수 있다. 

따라서 라운드로빈 방식에서는 해당 trade-off를 고려하여 적절한 타임 퀀텀 값을 설정하는 것이 중요하다.

해당 방식은 앞서 언급했듯이 반환 시간의 측면에서 그리 좋지 못한 스케줄링 방식이지만, 실제로는 많이 쓰이는 방식이다. 

그 이유로는, 

현대의 컴퓨터에서 응답 시간은 가장 체감이 잘되는 성능 지표 중 하나라는 점과

말 그대로 상대적으로 반환 시간이 안 좋은 것이지 컴퓨팅 기술의 발전으로 절대적으로는 그 차이가 미미하다는 점이 있다. 

 

MLFQ 스케줄링

출처: https://www.geeksforgeeks.org/difference-between-multilevel-queue-mlq-and-multi-level-feedback-queue-mlfq-cpu-scheduling-algorithms/

Multi-level Feedback Queue의 약자로,

해당 방식은 각 작업의 CPU burst time을 예측하기 어렵다는 한계 속에서 응답 시간과 반환 시간을 최적화하기 위해 등장한 방식이다.

이름에서 알 수 있듯이, 다중 대기열을 사용하는 방식인데 이때 각 대기열은 하나의 우선 순위를 의미한다.

즉, 우선 순위 별로 대기열이 존재하는 것이다.

이 때 우선순위는 정적으로 정해져 있는 것이 아닌,

처음 작업이 들어왔을 때는 높은 우선순위를 갖고 있다가 실행이 됨에 따라 점차 우선순위가 낮아지는 방식을 채택한다.

해당 방식은 다음의 규칙에 따라 스케줄링을 수행한다.

1. 우선순위가 가장 높은 큐에 존재하는 작업부터 실행
2. 특정 큐에 여러 개의 작업이 존재한다면, 이는 RR 방식으로 스케줄링
3. 새로운 작업이 들어오면 이를 우선순위가 가장 높은 큐에 배치
4. 특정 작업이 타임 퀀텀을 모두 소진하지 못한 채 CPU를 반환할 경우엔 기존 큐에 그대로 두고, 타임 퀀텀을 모두 소진한 경우에는 한단계 낮은 큐로 이동
5. 사전에 설정해둔 기간이 지날 경우 모든 큐의 작업을 최상위 큐로 이동(Aging)

이를 통해 MLFQ는 우선순위를 고려하면서도 작업들의 응답, 반환 시간을 최적화한다. 

또한 낮은 우선순위의 작업들이 기아 상태에 빠지는 것을 고려하여 Aging 기법을 추가적으로 적용하여 이를 해결했다.

해당 방식은 선점형, 동적, 다중 대기열 스케줄링으로 볼 수 있다.

해당 방식은 구현에 난이도가 있는 방식이지만

실시간으로 응답을 수행해야하는 대화형 작업(ex. 키보드 입력)에 대해 나쁘지 않은 성능을 보이고,

덩치가 큰 작업들이 지속적으로 CPU를 할당받을 수 있게 한다는 점에서 

많은 운영체제에서 채택하는 방식이다. 특히, Windows 운영체제에서 이를 기본 스케줄러로 사용한다.

 

CFS 스케줄링

출처: https://www.linuxjournal.com/node/10267

Completely Fair Scheduler의 약자로, 이름에서 알 수 있듯이 해당 스케줄링 방식은 공정성을 최우선 목표로 잡는다.

이를 위해 해당 방식에서는 sched_latency와 min_granularity라는 두 변수를 먼저 설정한다.

일반적으로 두 값은 각각 48ms와 6ms를 갖기 때문에 이를 기준으로 설명하겠다.

여기에서 sched_latency는 현재 대기열에 존재하는 모든 작업들이 공유하는 하나의 사이클 주기이다.

만약 대기열 내 프로세스가 4개 존재한다면, 48ms를 4로 나눠 각각 12ms씩 할당받는다.

이제 각 작업은 12ms씩 수행하게 되고, 각 작업이 갖는 vruntime이라는 변수에 실행 시간을 쌓는 식으로 작동한다.

이 때 다음 수행할 작업은 vruntime이 가장 작은 작업을 선택하게 된다.

만약 대기열 내 프로세스가 굉장히 많은 상황에서는, 각 작업이 할당 받는 시간이 굉장히 짧을 것이다. 또한 컨텍스트 스위칭이 더 자주 발생하여 성능 상 문제가 발생할 수 있다.

이를 위해 존재하는 것이 min_granularity 값인데, 각 작업에 할당되는 시간이 해당 값보다 작아지더라도 스케줄러는 무조건 min_granularity 값 만큼은 작업을 수행시킨다. 

CFS가 공정성을 최우선 목표로 잡기는 하나, 그렇다고 성능이 그렇게 나쁘지만은 않다.

CFS 방식에서는 성능을 위해 작업들을 Red-Black 트리를 통해 관리하는데, 이를 통해 연결 리스트로 작업들을 관리하는 다른 방식과 비교하여 해당 분야에서 더 나은 성능을 얻을 수 있었다. 특히 연결 리스트 방식에 비해, 확장성이 더 뛰어나다.

CFS는 위와 같은 특징들을 통해 확장성과 성능을 어느정도 보장할 수 있었고, 이에 리눅스에서 기본 설정으로 쓰이는 스케줄러이다. 

(nice 조정을 통한 프로세스 간 할당 시간 가중치 조정은 글이 너무 길어진 탓에 다루지 않겠다.)

 

 

 

참조

OSTEP(Operating System Three Easy Pieces), 2015 - Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau