참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

CPU Scheduling

학기초에 개괄적인 내용을 다루면서 CPU Scheduling 에 대해 논의한 바가 있다. CPU의 한 코어는 한번에 하나의 process만을 가질 수 있고, 여러 프로세스들을 효과적으로 작업하기 위해서 Time-sharing 전략을 사용해왔다. 다수의 프로그램을 메모리에 적재해서 프로세스로 만들고 CPU에 이 프로세스들을 번갈아가며 빠르게 할당하는 전략이다. 그렇다면 여러 프로세스를 어떻게 관리하는 것이 가장 효과적인 방법일까?

I/O and CPU Burst

프로세스의 실행은 항상 두 단계로 이루어진다.

1. CPU burst
2. I/O burst

의 순환이다. CPU-burst 는 프로세스가 CPU에 의해 실제로 실행되는 것을 말한다. 그리고 I/O-burst 는 I/O 를 위해 대기하는 것을 말한다. 어떤 프로세스가 실행되면, 해당 프로세스는 CPU-burst 로 시작된다. 그리고 어떤 I/O burst 가 되었다가 다시 CPU-burst 가 된다. 프로세스가 종료되는 시점에서도 CPU-burst 이후에 I/O-burst가 방생하고 이 시점에서 system call이 발생하며 프로세스가 종료되게 된다. 일반적으로 CPU-bound 프로그램은 긴 CPU-burst 를 가지고, I/O-bound 프로그램은 I/O 요청이 많기 때문에 짧은 CPU-burst 를 가지게 된다.

CPU Scheduler

메모리에 적재되어 ready queue에 대기 중인 프로세스를 선택해서 CPU에 할당해주는 작업을 해주는 운영체제의 일부를 short-term schduler, 혹은 CPU scheduler 라고 한다. 여기서 다시 정리하자면, long-term scheduler, 혹은 job scheduler는 저장장치에 있는 프로세스를 메모리에 적재해주는 역할을 하고, short-term scheduler, 혹은 CPU scheduler 는 메모리에 적재되어 있는 프로세스 중 CPU에 할당할 프로세스를 고르는 역할을 한다.

메모리에 적재되엉 있는 프로세스의 PCB를 모아두는 공간을 Ready Queue 라고 하지만, 우리가 알고 있는 특성처럼 항상 FIFO 원칙으로 PCB가 관리되는 것이 아니라는 것을 기억하자.

Preemptive and Nonpreemptive Scheduling

CPU 스케줄링은 다음과 같은 상황에서 이루어진다.

1. 프로세스의 상태가 wait system call 이나 I/O 요청에 의해 running 에서 waiting 으로 변경된 경우.
2. 프로세스의 상태가 interrupt 등에 의해 running 에서 ready 로 변경된 경우.
3. 프로세스의 상태가 I/O 처리가 끝나서 waiting 에서 ready 로 변경된 경우.
4. 프로세스가 종료된 경우.

Nonpreemptive Scheduling

비선점형 스케줄링 이라고도 하는 Nonpreemptive scheduling 은 1, 4번 상황에서만 스케줄링을 하는 스케줄링 방법이다. 한번 CPU에 할당된 프로세스는 해당 프로세스가 종료되거나 waiting 상태가 되어 스스로 ready queue 로 돌아가지 않는 이상 CPU에서 계속 유지된다.

Preemptive Scheduling

선점형 스케줄링 이라고도 하는 Preemptive scheduling 은 1번부터 4번까지의 모든 상황에서 스케줄링을 진행하는 방법이다. CPU에 할당된 프로세스가 스스로 해제되지 않는다고 하더라도 스케줄러가 강제가 현재 프로세스를 CPU에서 해제하고 새로운 프로세스를 할당할 수 있다. 대부분의 운영체제들이 이 방법을 채택하여 사용하고 있다.

Dispatcher

Dispatcher 는 CPU 스케줄러에 의해 선택된 프로세스에게 CPU의 제어를 전해주는 기능을 하는 모듈이이다. 디스패처를 통해 context switching, user mode로의 전환, PCB로부터 이전에 중단한 위치를 복구하는 것이 관리된다. 디스패처는 context switching 이 발생할 때 항상 호출된다. 이미 우리가 알고있는 것처럼 context switching 은 교환될 두 PCB에 데이터를 저장하고 불러오는 pure overhead 를 가지고 있다. 따라서 디스패처는 가능한 최고 속도로 수행될 필요가 있다. 이때 디스패처가 시작되고 끝나는데까지 발생하는 시간을 dispath latency 라고 한다.

Scheduling Criteria

여러 CPU Scheduling 알고리즘을 비교하기 위해서 필요한 기준들이 있다.

1. CPU Utilization (CPU 이용률): CPU를 사용하는 정도를 말한다. CPU 스케줄링의 목적은 결국 CPU를 최대한으로 사용할 수 있도록 프로세스를 분배하는 것이다.
2. Throughput (처리량): 단위 시간 당 CPU가 완료하는 프로세스의 수를 말한다.
3. Turnaround Time (총처리 시간): 특정한 프로세스가 실행하고 종료되는데까지 소요되는 시간을 말한다. 총 처리시간은 프로세스가 제출되고 완료되기까지의 시간을 말하기 때문에, ready queue 에서 머무른 시간, 실제로 실행된 시간, I/O 를 위해 대기한 시간까지 모두 포함한다.
4. Waiting Time (대기 시간): 대기 시간은 프로세스가 종료되기까지 ready queue 에서 대기한 시간의 총합을 말한다.
5. Response Time (응답 시간): 응답시간은 프로세스에게 어떤 결과를 요청하고 응답을 받기까지 걸리는 시간을 말한다. 유의할 점은 응답시간은 요청 이후에 응답을 시작하기 까지 걸리는 시간을 말하기 때문에 화면에 출력하는데 걸리는 시간은 포함하지 않는다.

Scheduling Algorithm

First-Come, First Served (FCFS)

이 알고리즘은 단순하게 가장 먼저 ready queue 에 도착한 프로세스가 가장 먼저 CPU에 할당되도록 하는 알고리즘이다. 큐를 통해 구현되고 ready queue 에 새로운 프로세스의 PCB가 들어올 때마다 PCB를 앞에 있는 PCB를 가르키도록 링크 해준다.

이 알고리즘은 구현하기가 쉽고 내부 동작을 이해하기 쉽지만, 프로세스들의 평균 waiting time 이 길어질 수 있다는 단점이 된다. 만약 burst 시간이 긴 프로세스가 먼저 ready queue에 들어오고 상대적으로 시간이 짧은 프로세스가 다음에 들어온다면, 뒤에 들어온 프로세스는 빨리 끝날 수 있는 작업임에도 불구하고 먼저 들어온 프로세스가 모두 종료되기 까지 기다려야 하게 된다. 이렇게 모든 프로세스가 현재 실행중인 프로세스가 끝날때까지 기다리고 있는 현상을 convoy effect 라고 한다.

FCFS 스케줄링은 nonpreemptive 스케줄링이다. 따라서 한번 CPU에 할당된 프로세스는 스스로 해제되기전까지 계속 CPU를 차지하고 있게 된다. 따라서 Interactive system 에서는 불리하게 작용할 것이다.

Shortest-Job First (SJF)

SFJ 알고리즘을 통한 스케줄링은 주어진 프로세스들 중에서 burst 시간이 가장 짧은 프로세스를 우선적으로 선택하는 알고리즘이다. FCFS에서 발생했던 문제가 상대적으로 burst 시간이 긴 프로세스가 실행중일 때, 다른 프로세스들의 waiting time이 비효율적으로 증가하는 문제가 있었는데, 가장 빨리 끝나는 프로세스를 맨 앞에 넣으면 그런 문제가 사라진다. 따라서 평균 waiting time이 크게 줄어들게 된다.

SFJ 알고리즘은 스케줄링을 위한 최적의 알고리즘처럼 보인다. 알고리즘 내에서 다음에 올 프로세스의 burst 시간을 알 수 있는 방법이 없기 때문에 구현이 불가능하다. 따라서 이 알고리즘을 구현하기 위해서 다음에 올 CPU burst 가 바로 이전의 CPU burst 와 소요시간이 비슷할 것이라고 가정하고 다음 CPU burst 예측한다.

Burst Time Prediction

$T_{n+1}=\alpha t_n + (1- \alpha)T_n$

위 수식을 통해 다음번에 올 burst 시간을 예측한다. t_n 은 째 burst 의 길이이고, T_n+1 은 다음에 올 burst 의 예측 값이다. 알파 값은 최근 값과 이전 값의 가중치를 의미한다. 따라서 만약 알파가 0이라면, T_n+1 = T_n 의 식이 만들어지기 때문에 최근 값들을 사용하지 않는 다는 것을 의미한다. 만약 알파가 1이라면, T_n+1 = t_n 의 식이 만들어지기 때문에 가장 최근의 burst 정보만 예측에 사용하겠다는 것을 의미한다. 일반적으로는 알파값을 1/2 로 둔다.

Shortest Remaining Time First

SFJ에서 조금 변형된 형태읭 스케줄링 알고리즘이다. 이 알고리즘에서는 각 프로세스들의 burst 의 남은 시간을 계산하게 된다. 따라서 어떤 프로세스가 실행되는 중에 남은 burst 시간보다 짧은 시간을 가진 프로세스가 등장하면 해당 프로세스를 CPU에 할당해주게 된다.

Round-Robin Scheduling (RR)

라운드 로빈 스케줄링 알고리즘은 time quantum 이라는 타임스탬프를 사용하는 알고리즘이다. time quantum 이 정해지면 모든 프로세스는 ready queue에 준비된 순서대로 CPU에 할당되면서 정확히 time quantum 만큼만 burst 하고 다음 프로세스와 교체된다. 할당된 프로세스의 burst 시간이 time quantum 보다 작다면, 프로세스를 종료하고 곧바로 다음 프로세스를 동일한 time quantum을 가지고 실행하게 된다.

프로세스가 정확히 time quantum 만큼만 수행되고 강제적으로 교체되기 때문에 preemptive scheduling 이라고 할 수 있다. 라운드 로빈 알고리즘의 평균 대기시간이 다른 알고리즘보다 길 때도 있지만, 라운드 로빈은 준비된 모든 프로세스를 빠르게 돌아가면서 스케줄링하게 되기 때문에 interactive 한 시스템에서는 효과적이다.

하지만 라운드 로빈 스케줄링은 time quantum 에 큰 영향을 받는다. 프로세스의 burst time에 비해 time quantum이 터무니 없이 크다면, 라운드 로빈은 FCFS 알고리즘과 다를 것이 없어진다. 모든 프로세스가 time quantum 안으로 끝나기 때문이다. 또, time quantum이 너무 짧게 되면 그만큼 context switching 의 횟수가 증가하기 때문에 overhead 가 늘어나게 된다.

Priority Scheduling

Priority scheduling 은 프로세스마다 우선순위를 두고 우선순위가 높은 프로세스를 우선적으로 할당하는 방법이다. 만약 우선순위가 같은 프로세스가 여럿 있다면 FCFS 방식을 적용하게 된다. 여기서 우선순위는 사용하는 리소스나 그 양 혹은 사용자에 요청 등 다양한 요소에 의해 정의될 수 있다.

이 방법을 구현할 때, preemptive 하게, nonpreemptvie 하게 모두 구현될 수 있다. 만약 preemptive 스케줄링으로 구현되었다면, 새로운 프로세스가 queue 에 들어왔을 때, 그 우선순위가 현재 실행중인 프로세스의 우선순위보다 높다면 곧바로 CPU로 디스패치될 것이다. Nonpreeptive 스케줄링에서는 새로운 프로세스가 queue 에 들어왔을 때 해당 프로세스의 우선순위가 현재 실행중인 프로세스의 우선순위보다 높다면, ready queue 에 가장 앞 자리로 위치하게 될 것이다.

Indefinite Blocking (Starvation)

Priority Scheduling 에서 발생하는 문제가 있다. 우선순위에 의해 프로세스들이 할당되기 때문에 어떤 프로세스의 우선순위가 너무 낮은 경우에는 해당 프로세스가 ready queue 에서 절대 빠져나오지 못하고 계속 다른 프로세스에 순서를 뻬았기는 현상이 발생한다. 이런 문제를 indefinite blocking, 혹은 starvation 이라고 한다.

aging

Indefinite blocking 문제를 해결하기 위한 방법으로 각 프로세스마다 aging 이라는 개념을 도입할 수 있다. 각 프로세스는 ready queue 에 들어온 이후에 주기적으로 우선순위가 조금씩 증가된다. 이렇게 하면 낮은 우선순위를 가진 프로세스도 시간이 지남에 따라 높은 우선순위를 가지게 되어 CPU에 할당될 수 있게 된다.

Mix with RR

또 다른 해결 방법으로는 Round Robind 스케줄링을 함께 적용하는 것이다. 라운드 로빈 스케줄링을 적용하게 되면 같은 우선 순위를 가진 프로세스들이 라운드 로빈에 의해 빠르게 진행되면서 우선순위가 낮은 프로세스까지 실행시킬 수 있게 된다.

Multilevel Queue Scheduling

지금까지 정리한 방법들은 모두 프로세스를 단일한 ready queue 에서 관리한다. Multilevel queue scheduling 은 우선순위마다 각각의 ready queue 를 만들어서 스케줄링을 하는 방법이다.

우선 순위가 낮은 큐에 있는 프로세스들은 상위 우선순위의 큐가 비워질 때까지는 실행되지 않는다. 일반적으로 각 큐는 RR에 의해 스케줄링된다.

어떤 경우에서는 프로세스에 유형에 따라 Multilevel을 만들어서 스케줄링을 관리하기도 한다. 응답시간이 얼마나 요구되냐에 따라서 foreground process 와 background process 로 나누어서 큐를 구성하기도 한다.

각 우선순위가 가지는 queue 의 스케줄링도 적절히 관리되어야 하는데, 위에서 설명한 것처럼 우선순위가 더 높은 단계의 큐가 완전히 비워질 때까지 우선순위가 낮은 큐는 스케줄링을 진행하지 않게 할 수도 있고, CPU의 시간을 나누어서 각 레벨이 각각 비율에 맞게 스케줄 되도록 할 수도 있다.

Multilevel Feedback Queue Scheduling

Multilevel feedback queue scheduling 은 multilevel queue scheduling 을 조금 더 강화한 형태이다. 다른 스케줄링 알고리즘은 프로세스들이 각 단계별 큐에 진입했을 때, 큐와 큐 사이의 이동을 허용하지 않지만, 다단계 피드백 큐 스케줄링에서는 프로세스를 한 큐에서 다른 큐로 이동시킬 수 있다. 낮은 우선순위의 큐에서 프로세스가 너무 오랫동안 대기하고 있는 상태라면 윗 우선순위 큐로 올릴 수도 있다.

만약 각 단계의 큐마다 time quantum 을 두고 프로세스를 넣을 때, 이 프로세스가 최상층 큐의 time quantum 안으로 끝나지 않는다면 다음 큐로 이동시키는 방식으로 진행된다.

다단계 피드백 큐 스케줄링은 효과적이지만 그만큼 고려해야할 요소들이 많다. 일반적으로 이 스케줄링은 다음과 같은 매개변수들에 의해 결정된다.

1. 큐의 개수
2. 큐들 사이에 적용할 스케줄링 알고리즘
3. 프로세스의 우선순위를 올려주는 기준
4. 프로세스의 우선순위를 낮추는 기준
5. 새로운 프로세스가 들어갈 큐를 결정할 기준