스케줄링 알고리즘의 종류

선입 선처리 스케줄링

큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링이다.
가장 공정해보이지만, 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

이러한 현상을 호위 효과 라고 한다.

최단 작업 우선 스케줄링

CPU 이용시간의 길이가 가장 짧은 프로세스 부터 실행되는 스케줄링 방식을 최단 작업 우선 스케줄링이라고 부른다.

라운드 로빈 스케줄링

라운드 로빈은 선입 선처리 스케줄링에 타임슬라이스라는 개념이 더해진다.
타임슬라이스는 정해진시간만 이용할수 있는 개념으로, 타임슬라이스가 끝나면 문맥교환이 일어나고 다시 큐에 삽입된다.

타임슬라이스의 크기가 지나치게 크면 보위효과가 생길 여지가 있고, 지나치게 작으면 문맥교환의 비용이 너무 커진다.

최소 잔여 시간 우선 스케줄링

최단 작업과 라운드 로빈이 섞인 알고리즘이다.

최소 잔여시간 알고리즘은 정해진 타임슬라이스 만큼 사용하되, 다음 CPU를 사용할 프로세스는 작업시간이 가장 적은 프로세스이다.

우선순위 스케줄링

우선순위 스케줄링은 프로세스에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케ㅔ줄링 알고리즘이다.

위의 3개의 알고리즘은 우선순위의 알고리즘의 일종이라고 볼수 있다.

하지만 근본적인 기아 형상이 발생하는데, 우선순위가 낮은 프로세스는 계속해서 연기될 수 있다.

이를 막기위한 방법으로는 에이징이 있다.
시간이 지남에따라, 우선순위를 점차 증가시키는것이다.

다단계 큐 스케줄링

우선 순위 별로 준비큐를 여러개 사용하는 스케줄링 방식이다.

큐를 여러개두면, 우선순위를 구분하여 실행하는것이 편리하다. 또한 타임슬라이스를 여러개 지정할 수 있으며, 큐마다 다른 스케줄링 알고리즘 적용이 가능하다.

다단계 피드백 큐 스케쥴링

다단계 큐 스케줄링에서 발전한 상태이다.
다단계 큐 스케줄링에서는 우선순위가 낮은 프로세스들은 계속 연기될 여지가 있다(기아 현상 발생)
이를 보완한 것이 다단계 피드백 큐 스케줄링이다.

요지는 프로세스들이 큐사이를 이동한다는점이다.
그래서 타임슬라이스에 못 끝내는것이 있으면 더 낮은 큐로 이동된다.

그로인해 CPU를 많이 사용하는 CPU 집중 프로세스는 우선순위가 낮아지고, 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 된다.