CPU Scheduling Algorithms
The CPU, like every part of the computer has a task to perform, as well as a set of instructions on how to perform such tasks. Since a numerous amount of programs can be in memory at the same time, the CPU needs a sequence of functionality; that’s where the process manager comes in. The Process manager handles the removal of the running process from the CPU and the selection of another process.
The OS maintains all Process in scheduling Queues. It maintains a separate queue for each of the process states and when the state of a process is changed, it is unlinked from its current queue and moved to its new state queue.
- Job queue − This queue keeps all the processes in the system.
- Ready queue − This queue keeps a set of all processes that are in memory, and are waiting to be executed
- Device queues − The processes which are blocked due to unavailability of an I/O device constitute this queue.
The OS can use different scheduling algorithms to manage each queue. The process manager determines how to move processes between the ready and run queues which can only have one entry per processor core on the system.
There are six popular methods of scheduling processes to the CPU, which are:
- First Come, First Serve
- Shortest Job First
- Priority Scheduling
- Shortest Remaining Time
- Round Robin(RR)
- Multiple-Level Queues
These algorithms can be either non-preemptive or preemptive. Non-preemptive algorithms are made so that once a process has a the resource, it does not have to let go of the resource until its given time if over. In the other hand, the preemptive scheduling functions with priority, which means the schedule can stop the process from using the resource to give it to another process with a higher priority.
First In, First Out:
First come first serve, is just as it sounds like. The task that comes first, gets executed first. It is also a non-preemptive algorithm. While this method ensures that each process has a fair amount of time to be executed, it usually has poor performance due to high average waiting time.
Shortest Job First:
Shortest Job First is a preemptive algorithm that executes the shortest job first. This algorithm has one of the best approach to minimize the waiting time, when the processor knows in advance how much time it will take to execute each process. In an interactive OS this algorithms fails, since small process will get to cut the line each time they arrive which could lead to starvation of the longer tasks.
Priority Scheduling
Priority Scheduling is a non-preemptive algorithm that assigns each task a priority number to be executed by. If two task arrive at the same time, they would be dealt in a first come first serve manner. Priority can be decided on a number of factors such as memory requirements, time requirements or any other resource requirement.
Shortest Remaining Time:
Shortest Remaining Time is very similar to Short Job First. Unlike SJF, this algorithm looks at how much time is left in the execution time of the task in order to give it CPU time. This algorithm is also preemptive.
Round Robin
Round Robin is a preemptive algorithm, which works by using a quantum time. Each task is only allowed to run for this quantum time, The task manager then preempts the resource and gives it to the next task. It repeats this process until all task are finish.
Multiple-Level Queues
Multiple-level queues are used when tasks can places into groups depending on their characteristics, such as CPU time or Memory size. Each queue is assign a priority to be executed, and are allowed to have its own scheduling algorithm.
(example provided by www.tutorialspoint.com)
For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue.
