The CPU switches among different process to make the computer more productive. A single processor system can execute only one process can run, and any other processes have to wait till the process finishes.
Multiple processes are kept in memory simultaneously. When some process that is currently running has to wait (from some I/O request to complete, for example), the OS takes the CPU away from the waiting process and gives it to another process and this sequence of steps go on. This is called multiprogramming.
A process that is being executed can be in either of two states - CPU execution or I/O wait. The time spent in either of these states is called burst (CPU burst or I/O burst).
The 4 circumstances during which CPU scheduling takes place are -
The ready state is not the same as a waiting state. The ready state is when the process wants control of the CPU as soon as it is available
In the first and last situations, whatever process is in the ready queue is just allocated CPU time, theres not really a choice. And the scheduling scheme is said to be nonpreemptive or cooperative.
Otherwise it is preemptive.
FCFS is pretty self explanatory. The process that requests the CPU first is allocated the CPU first. A FIFO queue is used for the implementation. The PCB is attached to the tail when a process enters the queue.
It has the disadvantage that the average waiting time is unpredictable, since it depends on the order in which the processes enter the ready queue. This is undesirable for time sharing systems especially.
It is a non preemptive technique.
SJF assigns the CPU to the process with the shortest NEXT CPU burst time. If two processes have the same next CPU burst, then FCFS is followed. Basically, run a process till another process with a lower burst shows up. When it does, assign CPU to it and continue. Don't forget to run the previous processes.
It is difficult however to know the next CPU burst time of a process. It is an optimal algorithm but is difficult for short term scheduling algorithms.
It can be either premptive or non preemptive.
A process with higher priority runs first. Equal ones are scheduled in FCFS order. SJF can be thought of as a priority scheduling algorithm where the priority is inverse of next CPU burst time.
It has the disadvantage of causing indefinite blocking or starvation. A steady stream of high priority processes will make sure that a lower priority process will never get the CPU. To solve this, we use aging. We basically increase the priority of a process if it is waiting.
It can be either premptive or non preemptive. The preemptive one will make the current process wait if higher priority process arrives. The non preemptive one will simply put the new process in queue regardless of priority.
RR is pretty similar to FCFS, but it has preemption added in. The CPU scheduler goes around the ready queue as if it was circular, and lets each process run for a fixed interval of time (called a quantum). If the process finished execution before the quantum is complete, it releases the CPU voluntarily and the next process is dispatched to.
It is a non preemptive technique.