이 게시글은 operating system concepts 책을 기반으로 들은 강의 내용을 정리한 것입니다.
CPU scheduling 이란?
기본적으로 cpu는 한 번에 한가지의 일 밖에 하지 못한다. (싱글코어 가정)
하지만 우리가 실제로 컴퓨터를 사용할 때는 음악을 틀어 놓고 코딩을하면서 프로그램을 실행시켜 마치 여러가지일을 동시에 처리하는 것처럼 보인다.
이는 cpu 가 매우 빠르게 짧은 시간동안 여러가지 일을 돌아가면서 처리하여 마치 우리가 보기에는 동시에 처리하는 것처럼 보이게 한다.
이를 concurrent 하게 처리한다고 한다. (concurrent vs parallel 차이 찾아보기)
기본적으로 process (program이 실행되는 기본적인 단위)가 실행될 때에는 running, waiting, ready 상태를 번갈아 가며 실행하게 된다.
running이 실제로 cpu에서 실행되고 있는 프로세스의 상태이고 waiting은 다른 I/O 장치를 기다리는 상태, ready는 당장 실행될 수 있는 상태이다.
running인 프로세스는 단 하나뿐이고 ready인 상태인 프로세스는 여러 개이다.
여기서 ready 상태인 프로세스 중 어떤 것을 dispatch하여 running 상태로 cpu를 실행시켜야 할까?
이 문제가 운영체제에서 해야하는 CPU scheduling 이다.
context switching
Scheduling algorithm
기본적으로 스케쥴링 알고리즘을 선택할 때 고려해야할 사항이 여러가지 있다.
최대한 cpu를 많이 사용해야하고, 특정 프로세스가 독점하지 않고 골고루 cpu를 사용해야하며 빠르고 효율적으로 처리해야한다.
시스템마다 목표로 하는 바가 조금씩 다르기 때문에 자세한 것은 추가로 찾으면 좋을 것 같다.
스케쥴링 알고리즘은 크게 두가지로 나눌 수 있는데 preemptive 방식과 non-preemptive 방식이다.
preemptive 방식은 기존에 실행되던 프로세스를 내리고 우선 순위가 있는 프로세스를 실행시키는 방법이고
non-preemptive는 이미 실행된 프로세스는 끝까지 실행되어야 되는 방법이다.
자 그러면 이제 하나씩 자세히 설명하겠다.
FCFS
First Come First Served 를 줄인 말로 FIFO와 유사하다. Ready queue에서 먼저 들어온 순서대로 cpu에 dispatch 되어 실행되는 것이다. 일상 생활에서 많이 사용되는 알고리즘으로 가장 공정한 방법으로 먼저 떠올릴 수 있다. non-preemptive한 방식이며 starvation(계속 실행되지 못하고 기다리는 상황)이 발생하지 않는다.
하지만 프로세스의 동작 시간을 고려하지 않은 방식으로 waiting time이 매우 길어져서 Convoy effect(짧은 프로세스가 긴 프로세스 뒤에서 줄줄이 기다리는 상황)이 발생할 수 있다.
SJF
Shortest Job First의 줄인 말로 CPU 사용시간이 가장 짧은 프로세스 먼저 처리하는 방식이다.
non-preemtive 방식이며 한 프로세스가 끝나면 가장 짧은 프로세스를 선정한다. 이론상으론 가장 optimal한 알고리즘이다. waiting time이 최소가 된다. 하지만 짧은 프로세스가 계속 들어오면 긴 프로세스는 starvation이 발생할 수 있고, 실제로 처리시간이 얼마나 걸릴지는 예측이 어려워 구현이 불가하다.
SRTF
Shortest Remaining Time First 를 줄인 것으로 SJF 방식에서 preemtive 방식만 추가한 것이다. 매 time마다 남아 있는 처리 시간을 기준으로 context switching한다. 마찬가지로 사용하지 않는다.
Priority
말 그대로 우선 순위를 부여하여 우선순위가 높은 프로세스 먼저 처리하는 방식이다.
우선 순위가 높은 프로세스만 계속 기다리게 되면 낮은 프로세스는 실행되지 못하므로 starvation이 발생할 수 있으며 해결 방법으로 Aging을 사용하여 기다린 시간에 비례하여 우선 순위를 높이는 방법이 있다. 시스템에 따라서 우선 순위를 무엇으로 결정할지 고려해야 한다. 이것도 preemtive한 방식으로 구현한다.
Round Robin
robin이라는 새가 새끼한테 모이를 줄 때 계속 돌아가면서 일정량을 주는 것에서 유래되었다. 일정한 quantum마다 계속 돌아가면서 switching하는 방법으로 preemptive한 방식이다. time quantum이 클수록 FCFS의 양상을 띄어서 비효율적이고 너무 작으면 switching하는 시간에 대한 overhead가 너무 커서 비효율적이여서 적절한 시간으로 고려해야 한다. 일반적으로 10ms~100ms.
Multi-Level Queue
여러 알고리즘을 조합하여 만든 방식으로 각 우선 순위에 따라 각각의 큐를 만들어서 실행하는 방식이다. 높은 우선 순위 큐가 먼저 실행되며 각 큐 안에서 여러 프로세스 사이에서는 적절한 알고리즘을 통해 실행 순서를 결정한다.(대부분 RR을 사용) 하지만 이것도 마찬가지로 해당 프로세스를 어떤 큐에 넣어야 할지 미리 결정을 할 수가 없다.
Multi-Level Feedback Queue
Mulit-Level Queue를 보완한 것으로 프로세스를 우선 실행시키고 짧은 quantum을 준다. 만약 그 시간을 다 소모했으면 다음에는 더 많은 시간을 주면서 이 프로세스의 우선 순위를 파악하여 큐에 넣은다. 일반적으로 실행시간이 긴 프로세스가 낮은 우선 순위를 갖고 짧은 프로세스는 높은 우선 순위를 갖는다. waiting time을 줄이기 위함이다.
추가적으로 Multi-Processor 일 때 스케쥴링 방법과 Real-Time system에서의 스케쥴링 방법 등 다양한 알고리즘이 있다. 그리고 현재 실제로 쓰고 있는 윈도우나 리눅스나 솔라리스와 같은 운영체제들은 더 복잡하고 구체적이고 융합되어 있는 알고리즘을 사용하여 효율성을 높였다. ex) CFS 등
