FCFS Scheduling
ready queue에 먼저 요청한 process부터 CPU를 할당하는 Scheduling 방식의 비선점형 Scheduling.
가장 공정해 보이지만 CPU를 너무 오래 차지하는 process가 있는 경우 다른 process들의 대기 시간이 매우 길어질 수 있다.
예를들어, A process가 15ms, B, C process가 2ms를 소비하는 경우
A를 FCFS Scheduling으로 처리한다면 B와 C process는 15 + 2 + 2 ms를 기다려야 처리할 수 있다. 이러한 경우를 convoy effect라고 한다.
SFJ Schceduling
들어오는 모든 process의 작업 시간을 알고 있는 경우, 가장 짧은 대기시간을 가지는 process를 먼저 실행하도록 하는 방식의 비선점형 Scheduling.
기본적으로는 비선점형이나 선점형으로 구현될 수 있다.
Round Robin Scheduling
FCFS Scheduling에 time slice라는 개념이 더해진 scheduling 방식.
time slice란 각 process가 CPU를 사용할 수 있는 정해진 시간을 의미한다.
queue에 삽입된 process들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼 CPU를 이용하고 정해진 시간을 모두 사용하여도 완료되지 못한 경우 다시 queue의 맨 뒤에 삽입하면서 context switching이 일어나도록 한다.
Round Robin에서는 time slice의 크기가 매우 중요한데, 크기가 지나치게 큰 경우에는 FCFS와 다를 바 없어지면서 convoy effect가 발생할 수 있고 크기가 지나치게 작은 경우 context switching에서 발생하는 비용이 커져서 CPU가 process 처리보다 process 전환에 더 많은 비용을 소모할 수 있다.
SRT Scheduling
SJF Scheduling과 Round Robin Scheduling을 합친 방식.
time slice를 통해 process들은 정해진 만큼 CPU를 사용하되, 다음 CPU를 사용하는 process는 남은 작업시간이 가장 적은 process가 선택되는 구조이다.
Priority Scheduling
process들에 priority를 부여하고 가장 높은 priority를 가지는 process부터 실행하는 방식.
앞의 FCFS, SFJ Scheduling도 priority의 일종으로 볼 수 있다.
이러한 priority는 근본적인 문제점을 하나 가지고 있는데, priority가 낮은 process는 ready queue에 먼저 삽입되어도 priority가 높은 process 들에 의해 실행이 계속 연기될 수 있고, 이를 Starvation 이라고 부른다.
이를 방지하기 위해 aging이라는 기법을 사용하는데, 이는 오랫동안 대기한 process의 priority를 점차 높이는 방식이다.
이러한 기법을 적용하면 priority가 당장은 낮아 기다리는 process도 언젠가는 priority가 오를 수 있다.
Multilevel queue Scheduling
priority scheduling에서 발전한 형태이며 priority 별로 ready queue를 여러 개 사용하는 방식이다.
priority가 가장 높은 ready queue의 process를 먼저 처리하고 ready queue가 비면 그 다음 priority가 높은 queue를 처리하는 형태.
이러한 방식으로 여러 queue를 두면 process 유형별로 priority를 구분하여 실행하는 것이 편리해진다.
예를 들면 어떤 queue에는 priority가 비교적 높아야하는 CPU 집중 process가 삽입되고 다른 queue에는 IO 집중 process가 삽입될 수 있다.
또 다른 예로 어떤 queue에는 background process 들이 삽입될 수 있고 다른 queue에는 사용자와의 상호작용이 잦은 process들을 삽입할 수 있다.
또한 queue별로 여러 time slice를 지정하거나 queue마다 다른 scheduling algorithm을 적용할 수도 있다.
Multilevel feedback queue Scheduling
Multilevel queue Scheduling와 아주 유사하지만 더 발전된 형태로, 기존의 Multilevel queue Scheduling은 priority가 낮은 queue가 통째로 starvation이 발생할 수 있다.
이를 보완하기 위해 process가 queue 사이를 이동할 수 있도록 만들었다는 점인데, 새로 ready 상태가 된 process가 있다면 우선 priority가 가장 높은 queue에 삽입되며 time slice 동안 실행된다.
만약 process가 해당 queue에서 실행이 끝나지 않는다면 다음 priority queue에 삽입되어 실행된다.
또한 마지막 해당 queue에서 실행이 끝나지 않는다면 processsms Eh ekdma priority queue에 삽입되고 결국 CPU를 오래 사용하는 process는 점자 priority가 낮아지게 된다.
즉, CPU 집중 process들은 자연스럽게 priority가 낮아지고 CPU 사용이 적은 IO 집중 process들은 자연스럽게 priority가 높아진다.
process가 queue사이를 이동 가능하기 때문에 이에 aging을 적용해 starvation을 예방할 수 있다.
