Cpu 스케줄링
1. 개요
- 프로그램의 시작부터 종료까지 시간 중 프로그램이 CPU를 점유하는 기간을 CPU burst라 하고, I/O 장치와의 소통으로 blocked 상태에 있는 기간을 I/O burst라 한다. CPU를 사용하는 모든 프로세스들이 CPU burst가 더 많은지 I/O burst가 더 많은지를 그래프로 그려보면, 대다수 프로세스가 I/O burst가 압도적으로 많고(이러한 프로세스들을 I/O-bound process라 한다) 소수의 프로세스들이 CPU burst가 더 많았다(이러한 프로세스들을 CPU-bound process라 한다).
- I/O-bound process들은 사용자와 interactive한 작업을 주로 수행하므로, 이러한 프로세스들에 CPU가 할당되지 않는다면 사용자 입장에서 큰 불편을 느낄 수 있다. 따라서 프로세스 사이에 CPU 할당 문제(=CPU 스케줄링)는 중요한 문제가 된다.
- OS의 CPU 스케줄러는 ready 큐에 있는 프로세스 중에서 CPU에 할당할 프로세스를 선택하는 역할을 하며, OS의 dispatcher는 이렇게 선택된 프로세스를 CPU에 넘겨 context switch를 수행한다.
- interrupt에 의해 CPU를 점유하던 프로세스가 CPU 점유권을 빼앗기는 것은 외부적 요인에 의해 강제로 CPU 점유권을 빼앗기는 것에 해당하며(이를 preemptive하다고 한다), 프로세스가 종료되는 경우거나 I/O 장치를 사용하느라 스스로 blocked 상태로 전환되는 것 같은 경우는 반대로 스스로 CPU 점유권을 반납하는 것에 해당한다(이를 non-preemptive하다고 한다).
- CPU 스케줄링을 수행하는 여러 알고리즘이 있는데, 크게 나누면 강제로 CPU 점유권을 빼앗는(preemptive) 알고리즘과 강제로 CPU 점유권을 빼앗지 않는(non-preemptive) 알고리즘으로 나눌 수 있다.
2. CPU 스케줄링 알고리즘의 평가 척도
1) CPU의 관점에서 평가 척도
- 주어진 시간 동안 CPU가 작업을 수행한 시간의 비율(CPU utilization) 또는 CPU가 수행한 작업의 개수(throughput)가 CPU 관점에서 CPU 스케줄링 알고리즘을 평가하는 척도가 될 수 있다.
2) 프로세스의 관점에서 평가 척도
(1) turnaround time: 프로세스가 ready 큐에 들어간 시점부터 CPU burst 기간 동안의 프로세스 수행을 마치고 다시 ready 큐로 돌아갈 때까지 걸린 총 시간.
(2) waiting time: 프로세스가 ready 큐에 들어간 시점부터 CPU를 점유하는 차례가 올 때까지 대기한 총 시간. preemptive 알고리즘에서는 한 CPU burst 동안에도 여러 번 ready 큐에 들어갈 수 있는데, 이때 ready 큐에서 대기한 총 시간을 합한 시간.
(3) response time: 프로세스가 ready 큐에 들어간 시점부터 처음 CPU를 점유하기 시작해서 첫 결과값을 내기 시작하는 데까지 걸린 시간.
3. CPU 스케줄링 알고리즘
1) FCFS(first-come first-served)
- non-preemptive 알고리즘으로, 먼저 들어온 프로세스가 요청한 작업이 모두 종료되면 그때 다음으로 들어온 프로세스의 작업을 수행하는 알고리즘. 작업 종료까지 시간이 오래 걸리는 프로세스가 먼저 ready 큐에 들어온다면 그만큼 전체 프로세스들의 평균 waiting time이 매우 길어질 수 있는 알고리즘(이처럼 시간이 오래 걸리는 프로세스가 먼저 들어와 CPU를 오래 점유하여 전체 프로세스들의 평균 waiting time이 길어지는 현상을 convoy effect라 한다). 비효율적.
2) priority scheduling
- 프로세스가 갖고 있는 우선순위값을 조회하여 그 값이 가장 작은 프로세스가 먼저 CPU를 점유하게 하는 알고리즘. non-preemptive 방식과 preemptive 방식이 있다.
- 항상 우선순위값이 작은 프로세스를 우선적으로 처리하기에, 우선순위값이 큰 프로세스는 영원히 CPU를 점유하지 못하는 문제가 발생할 수 있다. (이를 starvation이라 한다.) 이 경우, ready 큐에 대기한지 오래된 프로세스는 점점 우선순위값을 작게 평가하는 식으로 문제를 해결할 수 있다. (이를 aging이라 한다.)
3) SJF(shortest-job-first)
- ready 큐에 들어온 프로세스 중 앞으로 사용할 CPU burst가 가장 짧은 프로세스가 먼저 CPU를 점유하게 하는 알고리즘으로, priority scheduling의 일종. non-preemptive SJF와 preemptive SJF가 있는데, 후자는 이론적으로 모든 CPU 스케줄링 알고리즘 중 평균 waiting time을 최소로 한다는 것이 보장돼 있다.
- SJF는 앞으로 사용할 CPU burst가 가장 짧은 프로세스를 정확히 알 방법이 없기에 이를 실제로 구현하는 데는 어려움이 있다. 단, 과거 그 프로세스가 CPU를 사용했던 시간들로부터 앞으로 그 프로세스의 CPU 사용 시간을 추측하는 계산식을 세워볼 수는 있다. (\(n\)번째 CPU burst의 실제 시간을 \(t_n\), \(n\)번째 CPU burst의 추측 시간을 \(\tau_n\)이라 하고 가중치를 \(\alpha\)라 하면, \(\tau_n+1 = \alpha t_n + (1-\alpha)\tau_n\)이라는 점화식을 세울 수 있다. 이 점화식을 일반항으로 풀어내면 계수가 \((1-\alpha)\)의 지수승이고 각 항이 \(t_i\)인 다항식이 나온다.)
4) Round Robin
- 시간을 아주 짧은 시간 단위로 나누어 단위시간(time quantum)마다 각 프로세스가 돌아가며 CPU를 점유하게 하는 알고리즘. time-share OS는 Round Robin 알고리즘으로 CPU 스케줄링을 하는 OS이다.
- Round Robin 알고리즘은 다음 장점이 있다.
(1) 각 프로세스의 앞으로의 CPU burst를 예측하는 작업을 필요로 하지 않는다.
(2) 단위시간을 q, ready 큐에 대기하는 모든 프로세스의 수를 n이라 하면, 모든 프로세스가 아무리 늦어도 최대 (n-1)q의 시간 안에 CPU를 점유할 수 있어 평균적인 response time을 매우 짧게 할 수 있다.
(3) 프로세스의 waiting time은 그 프로세스의 CPU burst에 비례한다. 즉, CPU burst가 짧은 프로세스는 waiting time도 그만큼 짧아지고 CPU burst가 긴 프로세스는 waiting time도 그만큼 길어진다. (waiting time에 있어 공정하다.)
- q가 너무 길어지면 FCFS와 유사해지고 q가 너무 짧아지면 지나치게 잦은 context switch로 인한 overhead가 지나치게 많아지므로, q를 적정한 크기로 잡는 게 중요하다. (보통 수십ms 정도가 최적임이 알려져 있다.)
- 프로세스들의 CPU burst가 모두 동일하다면, Round Robin 알고리즘으로 CPU 스케줄링을 할 경우 모든 프로세스들의 CPU burst가 동시에 끝나고 그 시점은 FCFS 알고리즘으로 CPU 스케줄링을 할 때 가장 마지막 프로세스가 CPU burst를 끝마칠 때와 같아진다. 예를 들어, 프로세스 4개의 CPU burst가 각각 10초라면 Round Robin 알고리즘은 40초가 지난 뒤에 모든 프로세스가 동시에 CPU burst가 끝난다. 그런데 FCFS 알고리즘은 10초, 20초, 30초, 40초 시점에서 각각 프로세스들의 CPU burst가 끝난다. 이 사례만 놓고 보면 RR이 FCFS보다 덜 interactive하다고 할 수 있지만, 이 사례는 극단적 사례이고 대부분의 경우 프로세스들의 CPU burst는 편차가 있으므로 평균적으로는 RR이 FCFS보다 더 interactive한 알고리즘이라 할 수 있다.
4. 여러 개의 ready 큐에서 프로세스를 선택하는 알고리즘
1) multilevel queue
- 여러 개의 ready 큐를 사용하여, 각 큐에 있는 프로세스들의 특성에 맞게 각각 다른 알고리즘으로 CPU 스케줄링을 수행하게 하는 알고리즘을 쓸 수 있다. 예를 들어, 사용자와 interaction 하는 프로세스들은 RR 알고리즘을 수행하는 큐에 두고 사용자와 interaction 하지 않는 프로세스들은 FCFS 알고리즘을 수행하는 큐에 두는 식으로 ready 큐를 여럿 둠으로써 각 알고리즘의 장단점을 서로 적절히 보완하는 새로운 알고리즘을 만들 수 있다.
- 예를 들어 사용자와 interaction 하는 프로세스들이 있는 ready 큐를 사용자와 interaction 하지 않는 프로세스들이 있는 ready 큐보다 항상 더 우선적으로 처리하면 이 경우에도 starvation 문제가 발생할 수 있다. 각 ready 큐에 시간을 할당하는 방식에 있어서도 RR 알고리즘을 적용한다면(예를 들면, 사용자와 interaction 하는 프로세스들이 있는 ready 큐와 사용자와 interaction 하지 않는 프로세스들이 있는 ready 큐 사이 시간 배분을 8대 2로 하는 경우 등) starvation 문제를 해소할 수 있다.
2) multilevel feedback queue
- RR 알고리즘의 단점으로, CPU burst가 얼마나 길어질지 모르기 때문에 잦은 context switch로 인한 overhaed가 커지더라도 그것이 전체 CPU burst 대비 얼마나 잦은 것인지 알 수 없다는 점이 있었다. RR 알고리즘을 사용한다는 점은 같지만 time quantum이 각각 다른 ready 큐를 여럿 두어, 처음에는 time quantum이 가장 작은 ready 큐에 넣지만 한번 CPU를 점유했는데도 CPU burst가 끝나지 않았다면 time quantum이 더 큰 ready 큐로 옮기는 식으로 CPU 스케줄링을 하는 알고리즘을 생각할 수 있다. 이렇게 하면 지나치게 잦은 context switch로 인해 overhead가 과하게 발생하는 문제를 해소할 수 있다.
5. 기타 CPU 스케줄링 알고리즘
1) 멀티 프로세서 환경에서 CPU 스케줄링
- 하나의 ready 큐에서 프로세서들이 각각 알아서 프로세스를 가져가 연산을 수행하게 하는 알고리즘이 있다.
- 모든 프로세스가 서로 동등해 각자 알아서 스케줄링을 하는(symmetric multiprocessing) 알고리즘이 있고, 그중 어느 한 프로세서는 다른 프로세서들과 달리 ready 큐의 프로세스들을 각 CPU에 배치하는 역할을 맡는 등 역할이 조금 다른 프로세서를 사용하는(asymmetric multiprocessing) 알고리즘이 있다.
2) 실시간 스케줄링
- 어떤 작업이 반드시 특정 시간 안에 종료돼야 하기 때문에 이를 위하여 특정 시간에 반드시 그 작업을 시작하게 하고는 정해진 시간 내에 반드시 끝낼 수 있도록 그 작업이 계속 CPU를 점유하게 하는 식으로 CPU 스케줄링을 하는 경우가 있다. (hard real-time system)
3) 스레드의 스케줄링
- 유저 레벨 스레드의 경우 커널이 스레드의 존재를 알지 못하므로, 그 프로세스가 CPU를 점유하게 되었을 때 그 프로세스가 자체적으로 각 스레드의 CPU 스케줄링을 하게 된다(local scheduling).
- 커널 레벨 스레드의 경우 커널이 스레드의 존재를 알고 있으므로, 각 스레드를 마치 다른 프로세스와 동등한 입장에서 평가하여 CPU 스케줄링을 하게 된다.
6. CPU 스케줄링 알고리즘의 평가 방법
1) queueing models
- 수학적 모델을 세우고 그 모델에 대입하는 숫자들도 확률분포적인 숫자들을 대입하여 여러 성능지수를 계산하는 방법. 이론적인 방식.
2) 직접 구현해보기
- OS의 CPU 스케줄링 알고리즘을 직접 입력하고, 실제로 프로세스를 수행해보게 한 후 그 처리 결과를 여러 성능지수로 검토하고 분석해보는 방식.
3) 시뮬레이션을 하는 프로그램을 만들어보기
- 성능평가를 하고자 하는 알고리즘을 프로그래밍 언어로 모의적으로 구현한 후, 그 프로그램이 다룰 수 있는 입력예를 대입해보고 그 출력 결과를 보고 성능을 검토해보는 방식.