Dispatcher

The function that gives control of the CPU to the process selected by the short-term or CPU scheduler is called Dispatcher.

Dispatcher function involves

i) Context switching

ii) Switching to user mode

iii) Jumping to the location in the user program to restart that program.

It will be better than a dispatcher should be as fast possible.

Scheduling Algorithms

Criteria for comparing CPU-scheduling Algorithms include the following:

1. CPU Utilization: To keep the CPU as busy as possible we would like the CPU to be utilized as much as we can.

2. Throughput: The number of processes completed per time unit is called throughput.

3. Turnaround Time: It is the sum of the period spent waiting to get into memory, waiting in the Ready Queue, executing on the CPU and doing I/O etc. So, turnaround time of a process is the period from the time of submission to the time of completion.

4. Waiting Time: another criterion is the amount of time that a process spends waiting in the ready queue.

5. Response Time: It is an important criterion in interactive systems. Response time is the calculation of time for a process request from its submission to the first response produced.

First Come, First Served Scheduling

The simplest algorithm is the First Come, First Served (FCFS) scheduling algorithm. In this scheduling scheme, the process that requests the CPU first is allocated the CPU first. The average waiting time under FCFS algorithm is long.

A set of processes arrives at time 0. The length of CPU Burst for process P1 is 24 ms, 3 ms for P2 and 3 ms for p3.

0 24 27 30

If these processes are executed using FCFS algorithm then the waiting time for process P1 is 0 ms, 24 ms for P2 and 27 ms for P3. So, the average waiting time is (0+24+27) / 3 = 17 ms. If the process arrives in the order P2, P3 and P1 then the average waiting time is (6+0+3) / 3 = 3 ms.

0 3 6 30

So the average waiting time in FCFS Scheduling Algorithm depends upon the CPU burst times of processes.

Shortest Job First

In the Shortest Job First (SJF) Scheduling, the process having the shortest CPU burst time is executed first. Although it is difficult to measure the length of CPU burst among processes we can predict the values. We expect that the next CPU burst time will be similar in length to the previous ones. So by computing the approximate length of next CPU burst, we pick a process with a shortest predicted CPU burst.

A set of processes have the following CPU burst time in milliseconds P1 = 6, P2 = 8, P3 = 7 and P4 = 3 ms.

0 3 9 16 24

Waiting time for P1 is 3 ms, 16 ms for P2 and 9 ms for P3 and 0 ms for P4. So, the average waiting time is (3+16+9+0) / 4 = 7ms. The average waiting time for this Situation is FCFS scheduling is 10.25 ms.

Priority Scheduling

A priority is associated with each process and the CPU is allocated to the process with the highest priority. Processes having equal priority are scheduled in FCFS order. So, the Shortest Job First algorithm is also a priority algorithm because processes having smallest CPU burst are executed first.

A set of processes arrive at time 0 have following CPU burst time and priority.

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

The processes will be scheduled in the following order using priority scheduling and the average waiting time calculated is 8.2 ms.

0 1 6 16 18 19

Internal or External priorities can be defined in Priority Scheduling. Internally defined priorities use measurable quantities i.e. time limits or memory requirements etc. Externally defined priorities are set by criteria that are external to the Operating System

i.e. amount of funds paid, department sponsoring the work etc.

Priority scheduling can be preemptive or non-preemptive. Preemptive priority assigns the CPU to the newly arrived process if its priority is higher than the currently running process. In non-preemptive priority the newly arrived process will be at the head of the ready queue and CPU will be assigned to this process when the currently running process will finish.

Starvation the problem in Priority scheduling is that it will leave low priority processes waiting for CPU for a long time and this problem is called Starvation.

Aging the solution to starvation is aging. In this technique, a waiting process priority is increased after a fixed time. So, even a process of low priority will execute, as its priority will be increased within few hours or days.

Round Robin Scheduling

The scheduling algorithm used in time-sharing systems is Round Robin Scheduling. In Round Robin (RR) Algorithm the ready queue is treated as a circular queue. The short-term or CPU scheduler allocates CPU to each process for a small unit of time called time quantum or time slice, and one quantum may be from 10 ms to 100 ms.

The RR scheduling algorithm is preemptive and the average waiting time in round-robin algorithm is long.

A set of processes arrive at time 0. The length of CPU burst time for process P1 is 24 ms, 3 ms for P2, and 3 ms for P3.

We assume that the time quantum is 4 ms. Process P1 executes for first 4 ms and it requires 20 ms more, but due to 4 ms of time quantum, it will be preempted as CPU will be given the process P2. P2 quits before its time quantum expires and same it happens to P3. Now the CPU is returned to P1 for the additional time quantum and the average waiting time like this for RR scheduling in this situation is 17/3 = 5.66 ms.

The performance of RR Scheduling depends on the size of time quantum. Very large time quantum acts like an FCFS policy and very short time quantum e.g. 1 ms is called processor sharing.

Multilevel Queue Scheduling

Multilevel queue scheduling is designed for situations where processes are classified into different groups. Ready queue is partitioned into separate queues and processes stored in any queue depend upon their memory size or process type etc. Each queue then again can have its own scheduling algorithm.

We have a ready queue partitioned into 5 different queues. System processes queue has the highest priority whereas student processes queue has the lowest priority. A process in a batch queue cannot run unless all its upper queues are empty.

Another technique is if we time to slice all the queues, i.e. each queue gets a portion of the time which it can then schedule among the various processes in its queue.

Multilevel Feedback Queue Scheduling

In Multilevel Feedback Queue Scheduling, a process can be moved between queues. Generally, processes that are moved between queues depend upon their CPU burst characteristics. If a process uses too much time it is moved to a low priority queue. Similarly, a process waiting for a long time in lower priority queue will be moved to the higher priority queue.

A multilevel feedback queue scheduler has three queues 0-2. The scheduler will first execute processes of queue 0, queue 1 and then queue 2. Processes in queue 0 will be given a time quantum of 8 ms and if a process does not finish in 8 ms, then it will be moved to the tail of queue 1. Processes in queue 1 have time quantum of 16 ms and if a process does not finish within that time, it is moved to queue2 that executes processes on the FCFS basis.

Generally, a multilevel feedback queue scheduler is defined on following considerations.

1. The number of queues

2. The scheduling algorithm for each queue.

3. Decide when to promote a process to a high-priority queue.

4. Decide when to demote a process to a lower-priority queue.

5. Decide which queue, a process should be placed.

Multilevel Feedback queue is a very general scheduling scheme but is also the most complex.

Multiprocessor Scheduling

Multiprocessor Scheduling is used on systems having multiple processors. Scheduling on systems having multiple processors is more complex. Multiprocessor scheduling depends upon the type of processors present in a system.

In Heterogeneous System (a system having different processors) each processor has its own queue and its own scheduling algorithm. A program written on one processor will not run on other processors.

In Homogeneous systems (a system having identical processors), there is one common ready queue. All processes go into one queue and are scheduled on to any available processor. So this scheme ensures that all processes work almost equally instead of one overloaded with processes and the other sitting idle.

Algorithm Evaluation

In algorithm evaluation, we evaluate different scheduling algorithm and try to find the efficiency of scheduling algorithms depending upon certain conditions. There are many evaluation methods that can be used for this purpose.

Analytic Evaluation

Is an important class of evaluation in which different techniques can be used for finding the efficiency of algorithms.

Deterministic Modeling

In this method, we check the performance of different algorithms for a defined workload i.e.

Process	Burst Time
P1	10
P2	29
P3	3
P4	7
P5	12

The average waiting time for this situation in FCFS algorithm is 28 ms, 13 ms in SJF and 23 ms in Round Robin Algorithm.

P1 = 0

P2 = 10+3+7+10+2 = 32

P3 = 20

P4 = 23

P5 = 30+10 = 40

0 + 32 + 20 + 23 + 40 = 115/5 = 23ms

So, Deterministic modeling is a simple way through which the efficiency of different algorithms can be evaluated accurately and quickly.

Queuing Models

Can also be used for comparing scheduling algorithms. The number of processes leaving the queue should be equal to the number of processes entering the queue in the steady System State.

An equation

n = l x w

known as Little’s formula and can be used for determining the efficiency of the scheduling algorithm.

n is the queue length, l is the average arrival rate for new processes in the queue and w is the waiting time.

If 7 processes arrived every second and queue length is 14 then average waiting time per process can be calculated i.e. 2 seconds

n = l x w w = n / l

w = 14 / 7 = 2 Seconds.

Simulations

Can be used for accurate evaluation of scheduling algorithms. In simulations, we monitor the real system and record the sequence of actual events and then we use this sequence in our simulation i.e. a model of the computer system, Programmed.

Scheduling Algorithms in operating system