[OS] CPU scheduling

CPU scheduling은 ready queue에 있는 프로세스 중 실행할 프로세스를 선택하는 방식을 의미한다. 각 알고리즘에 따라서 프로세스를 선택하여 ready 상태에 있는 프로세스를 running 상태로 변경한다.

 

1. Preemptive vs Non-preemptive (선점식 vs 비선점식)

 

- Preemptive: 선점식 스케줄링은 CPU가 이미 어떤 프로세스를 실행하고 있는 중에 이를 중단시키고 새로운 프로세스를 할당하는 방식이다.

 

- Non-preemptive: 비선점식 스케줄링은 CPU가 이미 프로세스를 수행 중인 경우, 프로세스가 끝나거나 IO를 만나게 될 때까지 프로세스 변경을 수행하지 못한다.

 

 

2. Scheduling Algorithms

 

- FCFS (First Come First Served)

 

프로세스가 먼저 온 순서대로 처리하는 방식이다. 가장 단순하고 공정하지만 최적화가 되지 않기 때문에 성능면에서는 좋지 않을 수 있다.

 

비선점형 스케줄링으로 하나의 프로세스가 CPU를 점유하면 해당 프로세스의 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환되면 스케줄링이 이루어진다.

 

※ convoy effect: 소요시간이 긴 프로세스가 먼저 도착하게 되는 경우, 해당 프로세스 종료까지 나머지 프로세스들이 모두 대기하여 효율성이 낮아지는 현상이 발생한다.

 

- SJF (Shortest Job First)

 

수행 시간이 짧은 프로세스를 먼저 실행시킨다. FCFS와 달리 늦게 도착한 프로세스여도 CPU burst time이 짧으면 먼저 할당된다. FCFS와 동일하게 비선점형 스케줄링으로 프로세스들의 대기 시간을 줄이는 관점에서는 가장 좋다.

 

문제점으로는 먼저 도착하였지만 수행시간 이 긴 프로세스의 경우 계속해서 대기하면서 수행이 지나치게 미뤄질 수 있다는 것이다. 프로세스가 수행되지 않고 계속 CPU 할당이 미뤄지는 것을 starvation이라고 한다.

 

수행시간을 예측하여서 스케줄링을 수행하는데, 이는 사실상 비현실적이라고 할 수 있다.

 

- SRTF (Shortest Remaining Time First)

 

최소잔여시간 우선 방식으로 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어지는 선점형 스케줄링이다. 새로운 프로세스가 도착한 경우 프로세스들의 최소 잔여시간을 비교하는데, 이때 현재 수행중인 프로세스의 남은 burst time 보다 새로운 프로세스가 더 짧은 CPU burst time 을 가지는 경우 새로운 프로세스가 CPU를 뺏어간다.

 

새로운 프로세스가 도달할 때마다 스케줄링을 다시 하게 되는데, 이때마다 CPU burst time을 측정할 수 없는 문제가 있고, SJF와 동일하게 starvation 이 발생할 수 있다.

 

- Priority Scheduling

 

우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선 순위는 일반적으로 정수로 표현되며, 작은 숫자일수록 우선 순위가 높다.

 

선점형 방식으로 현재 실행중인 프로세스보다 더 높은 우선순위의 프로세스가 도착하면 ready queue의 head에 넣는다.

 

한번 우선순위가 밀리고 계속해서 높은 우선순위의 프로세스들이 들어오는 경우 계속해서 CPU를 할당받지 못하게 되는 infinite blocking, starvation 상태가 된다. 이러한 문제를 해결하기 위해 aging 이라는 방법을 사용한다. 이 방법은 우선순위가 낮더라도 오랜 시간 기다린 프로세스의 우선순위를 높여주어 대기 시간을 줄이도록 하는 방법이다.

 

- Round Robin 

 

각 프로세스들이 돌아가면서 CPU를 점유하는 방식이다. 시간을 쪼개서 각각의 프로세스에게 할당 시간으로 주게 된다. 각 프로세스는 할당 시간동안 CPU를 점유하고, 할당 시간이 지나면 CPU는 다음 프로세스에게 선점당하고 실행중이던 프로세스는 ready queue의 제일 뒤로 이동하여 다음 차례까지 대기한다.

 

이 방식은 CPU 사용시간이 랜덤한 프로세스들이 섞여있는 경우 효율적으로 사용할 수 있다.

 

Round Robin 방식의 효율성은 할당되는 시간인 time quantum에 따라 달라진다. 각 할당시간이 끝날때 마다 다른 프로세스로 변경되는 context switching이 발생하게 되는데, time quantum이 너무 짧은 경우 context switching이 빈번하게 일어나 성능이 떨어질 수 있다. 반대로 time quantum이 너무 커지면 FCFS와 같아지게 된다. 그렇기 때문에 time quantum을 적절하게 설정하는 것이 중요하다.

 

- Multilevel Queue Scheduling

 

이전까지는 하나의 ready queue를 사용하는 알고리즘이었다면 이 알고리즘은 다수의 ready queue를 사용하는 알고리즘이다.

 

여러개의 queue들은 각각의 용도를 가지고 있고, 이에 맞는 프로세스들을 입력받게 된다. 각각의 queue 들은 서로 다른 스케줄링 알고리즘을 가지고 작업을 수행한다.

 

queue 간에 우선순위가 다를 수 있는데, 이러한 우선순위 특징 때문에 특정 queue만 수행되고 나머지는 대기하는 starvation이 발생할 수 있다. 그래서 각 queue 마다 CPU 사용시간을 달리 적용하는 time slice 방법을 사용하여 특정 queue가 CPU를 독점하는 문제를 방지한다.

 

- Multilevel Feedback Queue Scheduling

 

multilevel queue scheduling 과 다르게 각 프로세스들이 큐를 옮겨다닐 수 있다.

모든 프로세스는 하나의 입구로 queue에 진입하게 된다. 너무 많은 CPU time을 사용하거나 starcation이 우려되는 경우, 우선 순위를 고려하여 해당 프로세스는 다른 queue로 이동하게 된다.