운영체제 13. CPU 스케쥴링을 어떻게 구현할까

CPU 스케줄링은 실질적으로 어떻게 구현되는가?

스케줄링 알고리즘이 많다. 어떤 스케쥴링이 좋을까? 자원을 가장 효율적으로 활용하는 스케쥴링 방법이 가장 좋을 것이다. 스케쥴링 알고리즘의 성능 평가 기준을 알아보자.

1. CPU utilization (CPU 사용율): CPU를 100%중 얼마나 사용하고 있는가?
2. Throughtput (처리율): 단위 시간당 완료되는 프로세스의 수로 정의한다. 처리율은 높을 수록 좋다.
3. Turnaround time (반환 시간): 프로세스가 생성에서 종료될 때까지의 시간. 모든 프로세스의 평균을 냈을 때 짧을 수록 좋다.
4. Waiting time (대기 시간): 프로세스가 생성부터 종료될 때까지 대기한 총 시간이다. 모든 프로세스의 평균 대기시간을 재봤을 때 짧을 수록 좋다.
5. Response time (반응 시간): 입력했을떄 반응이 시작하기 전까지 걸리는 시간

가장 정석 방법은 비선점 스케줄링 3개 선점 스케줄링 3개 있다. 선점한다는 것이 무엇인가? 기존의 실행되던 프로세스가 우선순위가 더 높은 프로세스에 의해 선점될 수 있는 것이 선점 스케쥴링이다. 즉 선점이란 Context Switch와 같다. 비선점 스케쥴링은, 남이 뺏을 수 없다. 본인이 반환할 때 까지 이론상 무한히 CPU를 사용할 수 있다.

비선점 스케쥴링에는 다음 알고리즘이 존재한다.

1. FCFS(First-Come-First-Served)
2. 최단 작업 우선(Shorest Job First; SJF)
3. 우선 순위 스케쥴링(Priority Scheduling)

선점 스케쥴링에는 다음 알고리즘이 존재한다.

1. 라운드 로빈 스케쥴링
2. 다단계 큐 스케쥴링
3. 다단계 피드백 큐 스케쥴링

[!tip] CPU Burst Time이 무엇인가?{title} CPU 할당 후 입출력 요구시까지의 시간, 즉 CPU의 실 사용 시간이다.

FCFS 스케쥴링 방법은 무엇인가?

First-Come-First-Served. 선착순 방법이다. 가장 먼저 CPU에게 요청한 프로세스에게 CPU 자원을 제공한다. 문제가 많다. 만약 가장 오래걸리는 작업이 먼저 도착하면, 뒤에 짧은 Burst Time을 가진 작업들이 오래 대기하고 있다. 이러면 대기 시간이 늘어난다. 이를 호위 효과(Convoy Effect)라고 함. FCFS가 장점이 있을까? 구현이 간단하고, 뭐 계산할게 없으니까 스케쥴링 오버헤드가 적다.

[!example] 도착 순서에 따른 평균 반환시간과 평균 대기시간{title}

각각 평균 대기시간과, 평균 반환시간을 계산해보자. 시작 지점에서 1, 2, 3 순서대로 도착했다고 가정한다. 평균 대기시간 = (0+24+27)/3 = 51/3 = 17 평균 반환시간 = (24 +27+30)/3 = (8+9+10) = 27

평균 대기시간 = (0+3+6)/3 = 3 평균 반환시간 = (3+6+30)/3 = 13

도착 순서에 따라 평균 대기시간과 평균 반환시간이 드라마틱하게 차이난다! 그렇다면, CPU Burst Time이 작은 작업부터 먼저 할당해주면 평균 대기, 반환 시간이 더 개선되지 않을까????

최단 작업 우선 방법

위에서 착안한 아이디어가 바로 최단 작업 우선 방법이다. CPU 실 사용 시간, 즉 CPU Burst Time이 가장 짧은 프로세스에게 먼저 CPU를 할당해준다. 그럼 같은 시간 내에 많은 작업을 끝낼 수 있다는 장점이 있다. 따라서 평균 대기 시간에 한에선 최적 알고리즘이다.

일단 현재 요청한 프로세스 목록 중에 CPU Burst TIme이 가장 짧은 애를 골라 스케쥴링해준다. 그런데, CPU Burst Time은 결국 프로세스가 직접 실행되어야 알 수 있는거 아닌가? 어떻게 미리 알 수 있을까? 절대 알 수 없다. 알 수 있으면 Halting Problem이 풀림 따라서 기존의 Burst Time 데이터를 기록하고, 그 데이터를 통해 예측할 수 밖에 없다. 그 데이터는 PCB 내에 저장된다.

즉 최단 작업 우선 방법(SJF)는 CPU Burst Time 기록을 통해 ‘다음번에 가장 짧을 것으로 예측되는 작업’을 가장 먼저 실행해주는 방법이다. 예측은 지수평균을 낸다.

\[\tau_{n+1} = \alpha t_{n} + (1-\alpha)\tau_{n} ~~~(0 \leq \alpha \leq 1)\] \[= \alpha t_{n} + (1-\alpha) t_{n-1} + (1-\alpha)^2t_{n-2} + \dots + (1-\alpha)^{n+1} t_{0}\]

\(\tau\)는 예측값, \(t\)는 실측값. \(\alpha\)는 가중치. 왜 지수평균을 사용하는가? 실측한 데이터는 항상 정확한게 아니다. 노이즈 가능성이 존재한다. 따라서 딱 직전의 값만 사용하기 보단, 기존의 데이터를 모두 활용하는게 더 안정적이다. 다만 최신 데이터 일수록 더 많은 가중치를 부여해주는 것 뿐이다. 충분히 납득 가능하다.

만약 새로 생성된 프로세스라면 우선순위를 어떻게 결정해주는가? 부모 PCB가 갖던 Burst Time 데이터 값을 그대로 물려받는다.

SJF는 선점 스케쥴링에도 적용 가능하다. Time Slice가 도입된다. 현재 실행중인 프로세스보다 CPU Burst Time이 더 작은 프로세스가 요청하면, 요청한 프로세스가 CPU를 선점한다. 선점 스케쥴링에서 SJF를 사용하는게 비선점 스케쥴링에서 사용하는 것보다 평균 대기시간이 더 짧다. 이는 당연하다. 더 빨리 끝날 수 있는 프로세스를 바로바로 실행시켜 주기 때문이다.

[!example] 평균 반환 시간과 평균 대기 시간{title}

평균 대기 시간 = (0+3+9+16)/4 = 7 평균 반환 시간 = (3+9+16+24)/4 = 13

[!example] 도착 시간을 고려한 비선점 SJF의 평균 대기시간과 평균 반환 시간{title}

평균 대기 시간 = (0+(8-2)+(7-4)+(12-5))/4 = (6+3+7)/4 = 4 평균 반환 시간 = (7+(8-4)+(12-2)+(16-5))/4 = (7+4+10+11)/4 = 8

[!example] 도착 시간을 고려한 선점 SJF의 평균 대기시간과 평균 반환 시간{title}

평균 대기 시간 = ((11-2)+1+(7-5))/4 = (9+1+2)/4 = 3 평균 반환 시간 = (16+(7-2)+1+(11-5))/4 = (16+5+1+6)/4 = 7

비선점 SJF보다 더 짧다.

그럼 이 방법이 최선인가?

우선 순위 스케쥴링(priority scheduling)

우선순위라는 것은 CPU Burst Time 말고 다른 중요한 요소들이 많을 것이다. 이를 일반화하여, 우선순위가 높은 프로세스부터 스케쥴링하자는 방법이다. SJF는 우선 순위 스케쥴링의 특수 케이스와 같다. 우선순위 p가 CBT 예측치의 역수 1/tau.

우선순위는 여러 요인들에 의해서 고려되어야 한다. 내부적으로는 제한 시간, 메모리 요구량, 사용하는 파일 수, CPU Burst Time, I/O Burst Time 등이 존재한다. 외부 요소로는 높은 사용료를 내는 유저에게 높은 우선순위를 부여하는 등의 조작도 가능해야 한다. 이런 모든 정보는 PCB에 저장되어 우선순위 연산에서 사용한다.

일반적으로 CPU-Bound 작업 보다 I/O-Bound 작업의 우선순위를 높혀줘서 대화성을 높히는 것이 중요하다. 대화성은 곧 사용자 입장에서 운영체제의 성능과 같기 때문이다.

우선순위 스케쥴링의 가장 큰 문제점은, 우선 순위가 높은 작업이 계속 들어오면 우선순위가 낮은 프로세스는 평생 실행이 안될 수도 있다. 이걸 기아 상태(Starvation) 를 유발한다고 한다. 해결 방법은 위에서 봤듯이 우선순위를 조금씩 높혀주는 에이징(Aging) 방법으로 해결한다.

[!example] 평균 대기시간과 평균 반환시간{title}

이때 우선순위는 값이 아니라 우선순위를 고려한 실행 순서로 정의한다. 평균 대기시간 = (0+1+6+16+18)/5 = 8.2 평균 반환시간 = (1+7+16+18+19)/5 = 12.2

여러 복합적인 요소를 고려하기 때문에, SJF보다 평균 대기시간과 반환시간은 느릴 수 있다.

라운드 로빈(Round Robin) 스케줄링이 무엇인가?

Ready Queue를 원형 큐로 간주하고, 타임 퀀텀 시간만큼 CPU를 돌아가면서 할당해준다. 타임 퀀텀 = 타임 슬라이스 우선순위 없이 공산주의 체제와 같다. 만약 새로운 프로세스가 대기큐에 들어오면, 큐의 맨 뒤에 추가된다.

장점이 무엇인가? CPU가 공정하게 돌아가므로 기아 상태는 발생하지 않는다. 단점이 무엇인가? 먼저 Context Switch가 잦아져 오버헤드가 크다. 또, 타임 퀀텀을 어떻게 잡느냐에 따라 성능이 크게 의존한다.

[!example] 타임 퀀텀이 20일 때 평균 대기시간{title}

P1의 대기시간 = 0+(77-20)+(121-97)=81 P2의 대기시간 = 20 P3의 대기시간 = 37+(97-57)+(134-117)=94 P4의 대기시간 = 57+(117-77)=97 평균 대기시간 = 73

만약 SJF였으면, 평균 대기시간이 38이다.

타임 퀀텀은 어떻게 설정하는게 좋은가? 너무 짧으면 Context Switch의 오버헤드가 크다. 너무 크면 FCFS와 다를게 없다. 따라서 적당한 Time 퀀텀을 잡아야 한다. 타임 퀀텀을 증가시키는게 좋을까? 증가시키면 반환시간이 짧아지긴 한다. 그렇다고 일정 크기 이상을 넘어가면 오히려 더 늘어날 수도 있다 타임 퀀텀을 짧게하면 좋을까? 타임 퀀텀을 적당히 잡으면 한번에 끝날 자잘한 작업들이 오히려 분할되어 실행되서 평균 대기시간이 더 늘어나 버릴 수도 있다.

따라서 타임 퀀텀에 정답은 없다. 상황에 따라 잘 튜닝해야 하는데, 실험했을 때 타임 퀀텀이 80%의 프로세스의 Burst Time보다 길도록 설정하면 좋다고 한다.

다단계 큐 스케줄링이 무엇인가?

다단계 큐 스케쥴링 방법이 무엇인가? Ready Queue를 여러개 만든다. Queue에 우선순위를 부여한다. 중요한 Queue에 있는 작업부터 순서대로 처리한다.

큐를 어떻게 만드는가? 운영체제 구현하는 사람 마음이다. 각 큐는 각각 다른 스케쥴링 방법을 따로따로 적용할 수 있다. 예를들어, 맨 위의 큐에는 FCFS, 두번째 큐는 라운드 로빈 알고리즘을 사용하는 방식도 가능하다.

하나의 큐만 사용하지 않고, 여러개의 큐를 만드는 이유는 무엇인가? 그냥 우선순위 스케쥴링을 쓰면 되는 것 아닌가? 여러개의 큐를 만드는 이유는, 비슷한 프로세스끼리 그룹별로 묶어서 그룹에 적합한 스케쥴링 방법을 따로따로 적용할 수 있기 때문이다.

우선순위가 높은 큐에 작업이 계속 들어오면 우선순위가 낮은 큐의 작업은 평생 처리되지 못하는 것 아닌가? 따라서, 낮은 우선순위의 프로세스는 에이징을 해서 언젠가 실행될 수 있도록 만들어야 한다. 그렇기 위해선, 프로세스의 우선순위가 조절될 수 있어야 한다. 이를 다단계 피드백 큐 스케쥴링 이라고 부른다. 프로세스는 우선순위가 조절되면 다른 큐로 이동될 수 있다.

우선순위가 조절되야 하는 이유가 더 있다. 만약 타임 슬라이스를 주면 항상 풀로 다 써버리는 괘씸한 프로세스(무한루프를 돌고 있음, CPU Bound)는 우선순위를 낮춰야 대화성이 증진된다.

다단계 피드백 큐 스케쥴링이 가장 좋은거냐? 그런건 아니다. 다단계 피드백 큐는 구현이 골치 아프다. 큐는 몇개를 사용하는가? 각 큐에 대한 스케쥴링 정책을 어떻게 설정하는가? 언제 우선순위를 조절하고, 어떤 우선순위일 때 어떤 큐에 넣는가? 와 관한 것을 전부 고려해야 한다. 그러나, 다단계 피드백 큐는 이 모든 것을 고려하면 가장 일반적인 방법이 된다.

타임 슬라이스는 바뀔 수 있다?

프로세스마다 각기 다른 타임 슬라이스를 부여할 수 있다. 그리고 부여된 타임 슬라이스는 동적으로 변경될 수 있다. 왜 타임 슬라이스를 바꿀 수 있어야 할까? CPU-Bound 프로세스는 대부분 타임 슬라이스를 모두 소진하기 때문에, 타임 슬라이스를 많이 부여하면 대화성이 떨어진다. 반대로 IO-Bound 프로세스는 타임 슬라이스를 넉넉하게 줘도, 금방 반환하기 때문에 문제 없다. 보통 우선순위가 높을 수록, 대화성이 높은 프로세스와 같다. 예를들어, 리눅스 Ver 2.4의 경우 다음과 같다.

Nice값은 우선순위다. 실제 우선순위는 0부터 139까지 있고, 0부터 99까지는 Real time에서 사용한다. 기본은 100에서 139까지 사용하고, Nice값으로 -20~19로 맵핑된다. Nice 값이 낮을 수록, 우선 순위가 높다. Real time이 우선순위가 더 높아야 하기 때문에, 더 작은 값을 할당받았다고 생각

그러나 우선순위 예측에 실패하면, CPU-Bound 작업에 Time slice를 높게 줘서 버벅이는 현상이 발생했다. 따라서, 리눅스 Ver 2.6.23 이후부턴 CPU 사용 시간을 공평하게 주는 CFS(Completely Fair Scheduling) 로 변경한다.

CFS는 가상 런타임(vruntime) 개념을 도입한다. CFS는 단순하게 vruntime 값이 가장 작은 프로세스에게 CPU를 할당하는 방법이다. vruntime 정의는 다음과 같다.

\[\text{vruntime = actual runtime / weight}\]

actual runtime은 실제 CPU를 할당받은 시간, weight는 nice 값에 대응하는 가중치와 같다. nice 값을 weight 값으로 변환해주는 table이 constast로 define되어있다. nice 값이 클 수록 우선순위는 작고, weight 값도 작다.

vruntime이 가장 낮은 프로세스에게 CPU를 할당해준다. 실제 runtime이 길 수록 vruntime이 크므로, 다른 프로세스가 할당될 확률이 높다. 실제 runtime이 짧을 수록 vruntime이 작으므로, CPU 할당될 확률이 높다. 또, 우선순위가 클 수록 nice 값이 작으므로 weight 값은 크므로 vruntime 값이 작아지므로 CPU가 할당될 확률이 높아진다.

멀티코어 시스템은 싱글코어 시스템과 어떤 차이점이 있을까?

최고의 멀티코어 시스템은 현재진행형으로 연구 중이다. 프로세스를 어떤 CPU에 할당해야 할지 고려해야 하는 사항이 많다. 예를들어, 어떤 프로세스에서 특정 디바이스와 입출력하는데, 그 입출력 디바이스가 특정 CPU 버스에만 연결되어 있을 수도 있다. 그러면, 그 프로세스에서 디바이스를 사용할 때 디바이스와 연결된 CPU에 할당해줘야 한다. 그냥 할당하고, 할당된 CPU가 디바이스와 연결이 안되어있다면 바로 반납해주는 식으로 구현하면 되지 않을까? 그럼 계속 할당하고 할당해제되고 반복해도 vruntime은 크게 차이나지 않을 거고, 언젠가는 디바이스와 연결된 CPU에 할당받겠지 ㅇㅇ

크게 두가지 멀티코어 시스템이 존재한다.

1. 비대칭 다중 처리 (Asymmetric Multiprocessing)
2. 대칭 다중 처리 (Symmetric Multiprocessing, SMP)

비대칭 다중 처리는 무엇인가? 여러 CPU 중 하나를 스케쥴링 담당으로 임명한다. 임명된 CPU를 master server라고 하며, 모든 스케쥴링 결정, 입출력 처리, 시스템 활동 등을 담당한다. 나머지 CPU는 사용자 프로세스 코드만을 수행한다. 이 구조는 한 CPU에게 부하가 몰릴 수 있고, 그 CPU의 부하처리 능력에 의존하기 때문에 지금은 대칭 다중 처리를 대부분 사용한다.

대칭 다중 처리는 무엇인가? 각 CPU마다 각각의 준비 큐를 가지고 있고, 그 준비 큐에 대한 스케쥴링을 따로 수행한다. 그렇다면, 어떤 프로세스를 어떤 CPU의 준비 큐에 넣느냐? 이 문제점이 발생한다. 이때 두가지 이슈가 존재한다.

1. Processor Affinity
2. Load Balancing

Processor Affinity가 무엇인가?

프로세스를 처리하는 CPU를 다른 프로세스로 옮기면 그만큼 오버헤드가 발생한다. 왜? CPU, TLB 캐시 메모리의 이점을 못받으니까. 어떤 프로세스를 처리하던 CPU는 계속 해당 CPU가 담당하도록 하는게 좋다. 이 성질이 Processor Affinity이다.

OS는 기본적으로 Soft Affinity를 보장해주지만, System Call (sched_setaffinity())을 사용하여 Hard Affinity를 보장해줄 수 있다.

[!example] 시스템의 메인 메모리 구조가 Process Affinity에 영향을 끼칠 수 있다.{title} 예를 들어 Non-Uniform Memory Access, NUMA가 있다. 이는 코어 수가 많아질 수록, 공용 메모리에 접근하는데 병목 현상을 완화하고자 만든 아키텍처다. 대규모 서버에서 사용한다. 이런 아키텍처의 경우 프로세스가 올라가있는 메모리의 CPU에서 처리하는게 더 효율적이다. 이렇게 메모리 아키텍처에 따라 Process Affinitiy가 영향을 받을 수 있다.

Load Balancing이 뭔데?

여러 CPU가 있으면, 일을 골고루 처리하게 하는게 좋다. 이를 Load Balancing이라고 한다.

CPU는 서로 비슷한 양의 작업을 균등하게 처리하는게 좋다. 만약 한쪽이 작업을 몰빵당하고 있다면, 조절할 필요가 있다. 단순하게, 큐에 있는 작업이 한곳에 많이 몰려있으면 다른 애들한테 골고루 뿌려주면 끝이다.

누가 Load Balancing 해주는가? 커널의 스케쥴러가 담당한다.

만약 CPU가 본인만의 큐를 갖고있으면, 그냥 큐에 있는 작업이 한곳에 많이 몰려있으면 다른 애들한테 골고루 뿌려주면 그만이다.

Processor Affinitiy와 Load Balancing은 서로 상충되는 개념이기 때문에, OS 설계자는 무엇을 무엇이 더 가치있는지 잘 판단하여 정책을 만들어야 한다.