cpu는 한정되어있는 자원이기에, 프로세스를 배정해줄 때, 어떤 순서로 배정할지, 어떤 순서로 사용할 지가 현재 컴퓨터에 돌아가는 프로세스들의 평균 응답시간을 결정한다. 따라서 현재 돌아가는 컴퓨터의 성능에 cpu 스케줄링은 매우 중요한 역할을 한다.

출처: https://huisam.tistory.com/entry/cpu-Scheduling

선점 vs 비선점

cpu 스케줄링에는 크게 한 프로세스가 사용중에 다른 프로세스가 cpu를 선점하는 선점 방식,
다른 프로세스가 cpu를 사용중에는 끝날 때까지는 선점하지 못하는 비선점 방식으로 나뉜다.

선점 방식

선점 방식은 한 프로세스가 사용중에 다른 프로세스가 cpu를 선점가능하므로,앞에 짧은 실행시간을 가지는 프로세스를 배치할 수 있다. 뒤에 짧은 실행시간을 가지는 프로세스가 배치된다면 오랜 시간을 기다려야 하므로, 평균 응답시간은 길어질 수 밖에 없다.
이를 통해서 각 프로세스 별 평균 응답시간이 낮아진다.

그러나 타임 슬라이스를 매우 작게 가져간다면 잦은 컨텍스트 스위칭이 일어나서, 오버헤드가 일어난다.
또한 타임 슬라이스가 크다면, FCFS와 다른 점이 없다.
따라서 선점 방식에서는 cpu를 한번에 얼마나 사용할 지에 대한 타임슬라이스를 잘 설정해야한다.

비선점 방식

비선점 방식은 한 프로세스가 사용중에 다른 프로세스가 cpu를 선정할 수 없다. 이 방식을 이용하면, 짧은 실행시간을 가지는 프로세스가 뒤에 배치될 수도 있으므로, 평균 응답시간이 길어지는 경향이 있다.
하지만 컨텐스트 스위칭이 덜 일어나므로, 오버헤드는 덜 발생한다.

cpu 스케줄링 알고리즘

FCFS

First Come First Served Schedule의 줄임말로 먼저 들어온 프로세스를 먼저 실행하는 스케줄링이다.
이 알고리즘은 비선점형으로, 계속 하나의 프로세스가 실행이 끝날 때까지 대기 해야한다.

단순하게 먼저 들어온 것을 먼저 처리 하기 때문에, 실행시간은 고려하지 않는다.
이 때문에 위에서 말한 짧은 실행시간을 가지는 프로세스들이 뒤 배치 되어서 오래 기다리는 문제인 convoy effect가 발생할 수 있다.

SJF

Shortest Job first의 줄임말로 큐에서 실행시간이 짧은 프로세스가 먼저 실행되는 비선점형 스케줄링이다.
큐에서 실행시간이 짧은 프로세스가 먼저 실행되므로, 언뜻 보면 매우 효율적으로보이지만, 큐에 계속 짧은 프로세스만 들어온다면, 긴 실행시간을 가지는 프로세스는 계속 대기를 할 수 밖에 없다.
이를 기아 현상이라고 한다.

Round Robin Scheduling

Round Robin은 FCFS에 선점형 스케줄링을 부여한 방식으로 프로세스가 먼저 들어온 순서대로 타임슬라이스로 쪼개서, cpu를 사용하는
방식이다.
기존의 비선점형보다는 기아현상이 발생할 가능성이 적지만, 위에서 말한 타임 슬라이스의 크기에 따라서 성능이 달라진다.

SRJF

Shortest Remain Job First의 줄임말로, 현재 남은 시간 중 최소 시간을 가지는 프로세스가 먼저 실행한다.
여전히 긴 실행시간을 가지는 프로세스는 오래 기다려야되거나, 아예 실행이 안 될 수도 있다.

Multilevel Queue

위에서 말한 기아현상을 해결하기 위해서, 각 우선순위를 부여한 큐를 만들고, 우선순위에 해당하는 큐에 프로세스를 넣어두는 것이다.
우선순위가 높은 큐에 있는 것을 먼저 처리하고, 우선순위가 낮은 것을 그 다음에 처리한다.
이 방식을 활용해서 우선순위를 변경시켜서, 기아현상을 더욱 해결할 수 있는데 이방식이 Multilevel Feedback Queue Scheduling이다.
제일 먼저 프로세스가 들어오면 가장 높은 우선순위의 큐에 넣고, 타임 슬라이스 만큼 사용후 낮은 순위 큐
에 넣는다. 또한 너무 오랜 시간을 기다리는 프로세스의 경우 에이징을 이용해서 우선순위를 올릴 수도 있다.
이 방식을 이용하면, 짧은 실행시간을 가지는 프로세스가 먼저 실행되므로, 호위효과를 막을 수 있고, 에이징을 이용해서 기아현상 또한 막을 수 있다.