CPU Scheduler & Dispatcher
실행중인 프로그램은 CPU를 사용하는 작업과,
I/O처리를 위해 CPU를 내려놓고 기다리는 과정의 반복이다.
운영체제는 이러한 프로세스들이 원활하게 돌아가도록 스케줄링할 책임이 있다.
CPU를 기다리는 프로세스 중에서, 어떤 프로세스를 고를지 담당하는 부분을
운영체제의 CPU Scheduler라고 한다.
그리고 선택된 프로세스가 작업할 수 있게 context switching을 하는 부분을
운영체제의 Dispatcher라고 한다.
성능 측정 기준
CPU utilization
CPU를 얼마나 활용하는지 측정하는 기준이다.
총 시간동안 쉬지않고 CPU가 돌아간 시간을 비교한다.
Throughput
단위 시간 동안 얼마나 많은 수의 프로세스를 처리했는지 측정하는 기준이다.
Turnaround time
하나의 프로세스가 들어와서 완전히 나갈때까지 걸린 시간이다.
Waiting time
하나의 프로세스가 들어와서 완전히 나갈때까지 총 기다린 시간이다.
Response time
하나의 프로세스가 처음 CPU를 사용하기까지 걸린 시간이다.
선점형 or 비선점형
운영체제의 스케줄러가 프로세스로부터 강제로 CPU를 가져올 수 있는 경우
선점형(preemptive) 스케줄러라 한다.
반대로 CPU를 강제로 가져오지 못하는 경우를
비선점형(Non-preemptive) 스케줄러라라 한다.
스케줄러가 선점형인지 비선점형인지에 따라 같은 스케줄링 방법을 사용하여도
차이가 발생한다.
스케줄링 방법
지금부터 여러 스케줄링 방법을 알아보고,
각각 어떠한 특성이 있는지 알아보자.
FCFS
First Come First Served의 약어로, 먼저 온 프로세스를
먼저 처리하는 방식이다. 비선점(Non-preemptive)방식이다.
만약 CPU 사용 시간이 긴 프로세스가 앞에 온다면 뒤에 프로세스들이
오래 기달려야 하는 단점이 존재한다.
SJF (Non-preemptive)
Shortest Job First의 약어로, 대기하고 있는 프로세스중
가장 CPU 사용시간이 짧은 것을 선택하는 방식이다.
이 방식은 프로세스들의 평균 Waiting time이 짧다는 장점이 있다.
SJF (preemptive)
선점형 SJF방식이다.
프로세스가 CPU를 사용하고 있다 하더라도 더 짧은 작업이 들어오면,
프로세스를 교체한다.
이 방식은 가장 짧은 평균 Waiting time을 보장한다.
그러나 SJF방식은 기아(Starvation)현상이 발생할 수 있다는 단점이 존재한다.
10초짜리 프로세스가 도착했어도 계속해서 그보다 짧은 프로세스들이 도착하면
10초짜리 프로세스는 CPU를 할당받지 못한다.
또한 모든 프로세스의 CPU 사용 시간을 알아야 한다는 단점도 있다.
이는 미래를 예측해야 하는 불가능한 일이기 때문에, SJF는 이론적으로만 존재하는
스케줄링 방식이다. 물론 과거의 데이터로부터 예측하여 SJF방식을 어느정도
구현할 수 있다.
Priority
프로세스에 우선순위를 부여하여 우선순위가 높은 프로세스부터 처리하는 방식이다.
SJF는 우선순위를 CPU 사용시간에 두었다고 볼 수 있다.
중간에 CPU를 가져오면 선점형이 되고, 가져오지 않으면 비선점형이다.
우선순위 스케줄링 기법은 SJF의 단점인 기아(Starvation)현상이 발생할 수 있다.
우선순위가 낮은 프로세스는 계속 밀릴 수 있기 때문이다.
이를 해결하기 위해 한번씩 밀릴 때마다 우선순위를 높여주는 aging기법을
사용할 수 있다.
Round Robin
모든 프로세스가 CPU를 특정 시간만 사용하고 교체되는 기법이다.
특정 시간 이후에 CPU를 가져오는 선점형 방식이다.
가장 많이 쓰이는 스케줄링 방식 중 하나다.
이 방식의 장점은 Response time이 빠르다는 것이다.
큐에 n개의 프로세스가 존재하고, q초단위로 교체될 때
어느 프로세스도 (n-1) * q 시간을 넘게 기다리지 않는다.
RR 스케줄링 기법을 사용할 때, q를 어떻게 정하느냐는 중요한 문제다.
q가 너무 길면 이 방식은 FCFS와 같고, q가 너무 짧으면 context switching에 의한
overhead가 커져서 성능이 떨어진다.
Multilevel Queue
지금까지는 대기큐를 1개 사용하는 스케줄링 기법이었다.
지금부터는 여러개의 큐를 사용하는 스케줄링 기법을 얘기한다.
Round Robin방식은 Response time이 빠르다는 장점이 있었다.
그러나 프로세스 사이에서 우선순위를 부여하지 못한다.
만약 프로세스에 우선순위를 부여할 수 있다면,
사용자와 상호작용하는 프로세스들을 먼저 처리해주는 것이 가능해지고,
이는 Response time을 더 빠르게 할 수 있다.
예를 들어 첫번째 큐에는 사용자와 상호작용하는 프로세스들을 넣고
두번째 큐에는 CPU사용이 긴 프로세스를 넣는다.
첫번째 큐에는 80% CPU시간을 할당하고 두번째 큐에는 20%시간을 할당한다.
첫번째 큐에는 Round Robin방식을 적용하고 두번째 큐에는 FCFS방식을 적용한다.
이렇게 하게되면 빠른 응답을 필요로 하는 프로세스를 먼저 처리해줄 수 있게 된다.
Multilevel Feedback Queue
Multilevel Feedback Queue는 여러개의 큐를 연결하는 방식이다.
첫번째 큐를 통과한 프로세스는 두번째 큐에 들어가고,
두번째 큐를 통과한 프로세스는 세번째 큐에 들어간다.
각 큐마다 다른 스케줄링 기법을 적용할 수 있다.
예를 들어 첫번째 큐에는 4초씩 사용하는 RR방식,
두번째 큐에는 8초씩 사용하는 RR방식,
세번째 큐에는 FCFS방식을 적용한다.
모든 프로세스는 처음에 4초씩 CPU를 사용할 수 있고,
완료되지 않은 프로세스는 두번째 큐로 넘어간다.
첫번째 큐가 비었다면, 두번째 큐를 처리한다.
이러한 과정을 반복하면 짧은 CPU시간을 가지는 프로세스에 우선순위를
줄 수 있고, SJF와 같이 평균 waiting time도 줄이고,
RR의 빠른 response time도 가져갈 수 있다.
