CPU 스케줄링 — 누구에게 먼저, 얼마 동안 프로세서를 주나

1. 누구를 맨 앞에 세우나

앞 글 끝에서 물었습니다. 준비 큐에 여러 프로세스와 스레드가 기다리고 있을 때, 누구에게 먼저, 얼마 동안 프로세서를 줄 것인가. 이 결정을 CPU 스케줄링이라고 합니다. 준비 큐 맨 앞에서 꺼낸다고만 했는데, 사실 누구를 맨 앞에 세울지가 바로 스케줄링입니다. 같은 프로세스들을 어떤 순서로 돌리느냐에 따라 사용자가 기다리는 시간이 몇 배씩 달라집니다. 이 글은 그 순서를 정하는 방법들을 숫자로 직접 비교해 봅니다.

2. 프로세스는 계산과 기다림을 번갈아 합니다

프로세스를 들여다보면 프로세서로 계산하는 구간과 입출력을 기다리는 구간이 번갈아 나옵니다. 계산 구간을 CPU 버스트, 기다리는 구간을 입출력 버스트라고 부릅니다. 버스트는 한 번에 몰아서 하는 구간이라는 뜻입니다. 처음과 끝은 늘 CPU 버스트입니다.

프로세스는 성격에 따라 둘로 나뉩니다. 짧은 CPU 버스트가 잦고 입출력을 자주 기다리는 입출력 위주 프로세스, 그리고 긴 CPU 버스트가 드물게 나오는 CPU 위주 프로세스입니다. 실제로 재 보면 짧은 버스트가 아주 많고 긴 버스트는 드뭅니다.

3. 언제 고르나 — 선점과 비선점

준비 큐에서 다음 프로세스를 골라 코어 하나를 내주는 것이 CPU 스케줄러입니다. 고를 기회는 네 번 생깁니다.

1. 실행 중이던 프로세스가 입출력을 기다리러 대기로 갈 때
2. 인터럽트로 실행에서 준비로 밀려날 때
3. 입출력이 끝나 대기에서 준비로 돌아올 때
4. 프로세스가 끝날 때

첫째와 넷째는 선택의 여지가 없습니다. 프로세서가 비었으니 누군가를 반드시 골라야 합니다. 둘째와 셋째는 지금 도는 프로세스를 그대로 둘지 바꿀지 고를 수 있습니다.

이 차이로 스케줄링이 두 갈래로 나뉩니다. 비선점 스케줄링은 첫째와 넷째 경우에만 고릅니다. 한 번 프로세서를 받은 프로세스는 스스로 놓을 때까지 뺏기지 않습니다. 선점 스케줄링은 네 경우 모두 고릅니다. 더 급한 프로세스가 오거나 정해진 시간이 다 되면, 돌고 있는 프로세스에서 프로세서를 빼앗을 수 있습니다. 멀티태스킹이 이 방식입니다. 선점에는 대가가 있습니다. 공유 데이터를 고치던 도중에 프로세서를 뺏기면 데이터가 어긋날 수 있습니다. 이 문제는 다음 글에서 따로 봅니다.

고른 다음에 넘겨주는 일

스케줄러가 고르면 실제로 프로세서를 넘겨주는 모듈이 따로 있습니다. 디스패처라고 합니다. 디스패처는 문맥 교환을 하고, 사용자 모드로 바꾸고, 새 프로세스가 멈췄던 자리로 건너뜁니다. 한 프로세스를 멈추고 다른 프로세스를 시작하기까지 걸리는 이 시간을 디스패치 지연이라고 합니다. 스케줄링이 자주 일어날수록 이 지연이 쌓입니다.

4. 무엇으로 평가하나

어떤 방식이 좋은지 재는 기준은 다섯입니다. 높여야 하는 것이 둘입니다.

• 프로세서 이용률 — 프로세서가 일한 시간의 비율
• 처리량 — 단위 시간에 끝나는 프로세스 수

줄여야 하는 것은 셋입니다.

• 반환 시간 — 프로세스가 들어와서 끝날 때까지 걸린 전체 시간
• 대기 시간 — 준비 큐에서 기다린 시간의 합
• 응답 시간 — 요청하고 나서 첫 반응이 나오기까지 걸린 시간

이 글에서는 주로 평균 대기 시간으로 비교합니다. 시간 단위는 밀리초, 곧 천분의 일 초입니다.

5. 먼저 온 순서대로

가장 단순한 방식은 먼저 온 프로세스에게 먼저 주는 것입니다. 선착순 스케줄링이라고 하고, 비선점입니다. 0초에 세 프로세스가 P1, P2, P3 순서로 들어오고, CPU 버스트는 P1이 24, P2가 3, P3가 3이라고 합니다. P1이 0부터 24까지 돌고, P2가 24부터 27까지, P3가 27부터 30까지 돕니다. 기다린 시간은 P1 0, P2 24, P3 27입니다. 평균은 17입니다.

그런데 순서만 P2, P3, P1으로 바꾸면 기다린 시간은 0, 3, 6이 되고 평균은 3입니다. 같은 일을 순서만 바꿨는데 여섯 배 가까이 차이가 납니다. 긴 프로세스 하나가 앞에 서면 짧은 것들이 모두 뒤에서 오래 기다립니다.

6. 짧은 것부터

그렇다면 짧은 것을 먼저 돌리면 됩니다. 다음 CPU 버스트가 가장 짧은 프로세스에게 먼저 주는 방식을 최단 작업 우선이라고 합니다. 0초에 네 프로세스가 들어오고 버스트가 P1 6, P2 8, P3 7, P4 3이라고 합니다. 짧은 순서대로 P4, P1, P3, P2가 돕니다. 기다린 시간은 P4 0, P1 3, P3 9, P2 16이고 평균은 7입니다.

이 방식은 평균 대기 시간을 가장 짧게 만든다는 것이 증명되어 있습니다. 문제는 다음 버스트가 얼마나 길지 미리 알 수 없다는 것입니다. 그래서 지난 버스트 길이들을 바탕으로 예측합니다. 최근 값에 무게를 더 두고 오래된 값일수록 무게를 줄여 가며 평균을 내는 방식입니다.

프로세스들이 서로 다른 시각에 도착하면 규칙이 하나 붙습니다. 프로세서가 빌 때마다, 그 순간까지 와 있는 프로세스 중에서만 가장 짧은 것을 고릅니다. 그리고 비선점이라 한 번 시작한 프로세스는 더 짧은 것이 와도 끝까지 돕니다.

문제 1

P1은 0초에 와서 8이 필요하고, P2는 1초에 와서 4, P3는 2초에 와서 9, P4는 3초에 와서 5가 필요합니다. 비선점 최단 작업 우선으로 스케줄링하면 도는 순서는 어떻게 되고, 평균 대기 시간은 얼마일까요. 기다린 시간은 도착한 때부터 셉니다.

0초에는 P1밖에 없어서 P1이 먼저 돌고, 비선점이라 8초까지 쭉 돕니다. 8초가 되면 P2, P3, P4가 모두 와 있고, 이 중 가장 짧은 것은 4인 P2입니다. 남은 P3 9와 P4 5 중에서는 P4가 짧습니다. 기다린 시간은 시작 시각에서 도착 시각을 뺀 값입니다.

모두 더하면 31이고 넷으로 나누면 7.75입니다.

7. 짧은 것이 오면 바로 바꾸기

방금 문제에서 P2는 1초에 도착했는데 8초까지 기다렸습니다. P1이 비선점이라 뺏을 수 없었기 때문입니다. 선점을 허용하면 어떨까요. 새 프로세스가 올 때마다, 지금 도는 프로세스의 남은 시간과 비교해 더 짧으면 바로 바꿉니다. 이것을 최단 잔여 시간 우선이라고 합니다.

같은 자료로 해 봅니다. 1초에 P2가 오면 P1은 7이 남았고 P2는 4이니 P2로 바꿉니다. 2초에 오는 P3는 9, 3초에 오는 P4는 5라서 그때 P2에게 남은 3과 2보다 길어 바꾸지 않습니다. P2가 5초에 끝나면 남은 것 중 P4 5가 가장 짧아 10초까지 돕니다. 그다음 P1이 남은 7을 17초까지, P3가 26초까지 돕니다. 평균 대기 시간은 6.5입니다. 같은 자료에서 7.75가 6.5로 줄었습니다.

8. 돌아가며 조금씩 — 라운드 로빈

사람이 화면 앞에서 입력하고 결과를 바로 기다리는 대화형 시스템에서는 평균보다 반응이 중요합니다. 라운드 로빈은 선착순과 비슷하지만 선점입니다. 프로세서 시간을 타임 퀀텀이라는 작은 조각으로 자르고, 준비 큐를 둥글게 돌며 한 조각씩 줍니다. 조각을 다 쓰면 큐 맨 뒤로 갑니다. 퀀텀은 보통 10에서 100밀리초입니다.

앞의 선착순 예, P1 24, P2 3, P3 3을 퀀텀 4로 돌려 봅니다. P1이 4까지 돌고 뒤로 갑니다. P2가 7까지, P3가 10까지 돌고 둘 다 끝납니다. 그 뒤로는 P1 혼자 30까지 돕니다. 기다린 시간은 P1 6, P2 4, P3 7이고 평균은 약 5.67입니다. 선착순의 17보다 훨씬 짧습니다.

퀀텀은 얼마가 좋은가

라운드 로빈의 성능은 퀀텀을 얼마로 잡느냐에 달려 있습니다. 퀀텀이 아주 작으면 모두가 프로세서를 조금씩 나눠 쓰는 것처럼 보이지만, 갈아탈 때마다 문맥 교환 비용이 드니 그 비용이 일을 잡아먹습니다. 퀀텀이 아주 크면 대부분 한 조각 안에 끝나 버려 선착순과 다를 바가 없어집니다. 흔히 쓰는 기준은 CPU 버스트의 80% 정도가 한 퀀텀 안에 끝나도록 잡는 것입니다.

문제 2

0초에 세 프로세스가 P1, P2, P3 순서로 들어옵니다. 버스트는 P1이 5, P2가 3, P3가 1입니다. 퀀텀 2인 라운드 로빈으로 돌리면 각각 언제 끝나고, 평균 대기 시간은 얼마일까요. 기다린 시간은 끝난 시각에서 버스트를 빼면 됩니다.

끝난 시각은 P1 9, P2 8, P3 5입니다. 버스트를 빼면 기다린 시간은 P1 4, P2 5, P3 4입니다. 더하면 13, 셋으로 나누면 약 4.33입니다. 가장 짧은 P3가 5초에 끝나 금방 반응을 받았다는 점을 눈여겨봅니다.

9. 급한 것부터 — 우선순위

프로세스마다 우선순위를 매겨 높은 것부터 주는 방식도 있습니다. 여기서는 숫자가 작을수록 우선순위가 높다고 합니다. 0초에 다섯 프로세스가 옵니다. P1은 버스트 10에 우선순위 3, P2는 1에 1, P3는 2에 4, P4는 1에 5, P5는 5에 2입니다. 우선순위 순서로 P2, P5, P1, P3, P4가 돕니다. 기다린 시간은 P2 0, P5 1, P1 6, P3 16, P4 18이고 평균은 8.2입니다.

이 방식에는 위험이 있습니다. 높은 우선순위가 계속 들어오면 낮은 것은 영영 차례가 오지 않습니다. 이것을 기아라고 합니다. 해결책은 오래 기다린 프로세스의 우선순위를 조금씩 올려 주는 것입니다. 이것을 에이징이라고 합니다.

10. 줄을 여러 개 두기

프로세스의 성격이 다르면 줄을 나누는 것이 낫습니다. 다단계 큐는 준비 큐를 여러 개로 나누고 줄마다 다른 방식을 씁니다. 예를 들어 사용자와 대화하는 프로세스는 앞 줄에서 라운드 로빈으로, 사람이 기다리지 않고 뒤에서 한꺼번에 처리하는 일괄 작업은 뒷 줄에서 선착순으로 돌립니다. 줄 사이에도 규칙이 있어서, 앞 줄이 빌 때만 뒷 줄을 돌리거나, 프로세서 시간을 80대 20처럼 나눠 줍니다.

여기서 한 걸음 더 나아간 것이 다단계 피드백 큐입니다. 프로세스가 줄 사이를 옮겨 다닐 수 있습니다. 새 프로세스는 맨 위 줄에서 짧은 퀀텀을 받습니다. 그 안에 못 끝내면 아래 줄로 내려가 더 긴 퀀텀을 받습니다. 그러면 입출력 위주 프로세스는 위에 남고 CPU 위주 프로세스는 아래로 내려갑니다.

11. 정해진 시간 안에 끝내야 할 때

자동차의 브레이크 제어처럼 몇 밀리초 안에 반드시 반응해야 하는 시스템도 있습니다. 이런 실시간 시스템은 둘로 나뉩니다. 연성 실시간은 중요한 프로세스를 먼저 돌려 준다는 것만 약속합니다. 경성 실시간은 마감 시각 안에 반드시 끝내야 하고, 마감을 넘기면 아예 안 한 것과 같습니다.

실시간 시스템에는 센서 읽기처럼 일정한 간격마다 되풀이되는 작업이 많습니다. 이 간격을 주기라고 합니다. 주기가 짧을수록 우선순위를 높게 고정하는 방식을 비율 단조 스케줄링이라고 합니다. 반대로 마감이 가장 가까운 작업에 먼저 주는 방식을 마감 우선 스케줄링이라고 합니다. 마감 우선 방식은 이론상 프로세서를 100% 쓰면서도 마감을 모두 지킬 수 있습니다.

12. 리눅스는 어떻게 하나

리눅스의 기본 스케줄러는 완전 공정 스케줄러라는 이름을 씁니다. 각 작업이 지금까지 프로세서를 얼마나 썼는지를 가상 실행 시간이라는 값으로 적어 두고, 매번 이 값이 가장 작은 작업을 고릅니다. 가장 덜 쓴 쪽에 먼저 주는 것입니다.

우선순위는 나이스 값으로 정합니다. 마이너스 20부터 플러스 19까지이고 기본은 0입니다. 값이 클수록 남에게 양보한다는 뜻으로 우선순위가 낮습니다. 우선순위가 낮은 작업은 같은 시간을 써도 가상 실행 시간이 더 빨리 늘어납니다. 입출력 위주 작업은 조금 쓰고 곧 기다리니 이 값이 작게 유지되고, 자연스럽게 먼저 뽑힙니다.

정리

스케줄러는 준비 큐에서 다음 프로세스를 고르고, 디스패처가 넘겨줍니다. 비선점은 스스로 놓을 때만, 선점은 도중에도 바꿉니다. 선착순은 단순하지만 긴 것이 앞에 서면 모두가 기다립니다. 최단 작업 우선은 평균 대기를 가장 줄이지만 길이를 예측해야 하고, 선점하면 더 줄어듭니다. 라운드 로빈은 퀀텀씩 돌려 반응을 빠르게 하고, 우선순위 방식은 기아를 에이징으로 막습니다. 그런데 선점을 설명하면서 미뤄 둔 것이 있습니다. 공유 데이터를 고치던 도중에 프로세서를 뺏기면 데이터가 어긋난다는 문제입니다. 다음 글에서는 그 문제, 동기화를 봅니다.