Basic Concepts

CPU-I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution.

CPU Scheduler

Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler, or CPU scheduler. The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.

Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
Switching context
Switching to user mode
Jumping to the proper location in the user program to restart that program

Scheduling Algorithms

First Come First Serve

The simplest of all scheduling algorithms. The process that requested the CPU first is allocated the CPU first.

Demerits

1.Average waiting time under FCFS policy is quite long.
2.A smaller process has to wait for a large amount of time before a bigger process that has been allocated CPU finishes its execution.
3.Not suitable for time sharing systems where each user gets a share of CPU at regular intervals.

Shortest Job Scheduling

The scheduling criteria under this policy depends on which process has the shortest-next-CPU-burst. It is an optimal way of
CPU scheduling, i.e it gives the minimum average waiting time for a set of processes. If two process have the same burst time
left, FCFS is used to resolve the tie.

Demerits

1.It often cannot be implemented at the level of short-term CPU scheduling as there is no way to know the length of the next CPU burst.
2.The next CPU burst length is thereby approximated using statistical techniques like exponential average

Shortest Remaining Time First

This is the preemptive version of Shortest Job First scheduling. A newly arrived process in the ready queue
may have a burst time lesser than that of the current process getting executed. In such a case, the current process is preempted
and the newly arrived process is scheduled to execute. Similar to SJF, FCFS is used to resolve the tie here.

Largest Job First Scheduling

This is the opposite of Shortest Job First scheduling. It selects for execution the process with the largest execution time. It can be preemptive or non preemptive.

Demerits

1.The disadvantage with this algorithm is the total execution time of the process must be known before the execution.
There is a chance for starvation of processes which have lesser execution time when the longer processes are continually added.

Largest Remaining Time First Algorithm

It is the preemptive version of the Largest job first scheduling.

Non-preemptive priority scheduling

A more general case of the SJF scheduling where the priority was based on burst time. Each process is associated with a priority and CPU is allocated to the process with highest priority. Equal priority processes are scheduled in FCFS order. A newly arrived process is simply put in the ready queue based on its priority and does not interrupt the currently executing process.

Preemptive priority scheduling

It is a preemptive version of the priority scheduling algorithm. The priority of newly arrived processes are compared
with the currently executing process. If the priority is higher, then the currently executing process is preempted and the
newly arrived process executes

Round-Robin scheduling

The ready queue is treated as a circular queue. The CPU scheduler goes around the queue, allocating the CPU to each of the processes a
time period of 1 quantum. If the burst time left for a process is less than the time quantum, then the process will itself
release the CPU voluntarily. If the burst time left is more than 1 time quantum, the timer for that process will go off and a context switch is forced. This algorithm is preemptive by its nature.

Performance

1.Performance depends heavily on the time quantum. A very large time quantum will it make it effectively an FCFS algorithms and a very short time quantum will force a very large number of context switches.
2.A rule of thumb is that 80% of the CPU bursts must be shorter than the time quantum.

Highest Response Ratio Next

1.The response ratio of all the processes are calculated and the scheduler selects the process with the highest response ratio.
2.A process once selected will run till its completion.
3.Response ratio = (Waiting time so far + Burst Time)/Burst time.
4.Shortest processes are favoured. As the waiting time increases, the response ratio increases and the longer jobs can get past short jobs.

Comparator