**Related Content:** CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems

- Scheduling algorithms
- UNIX System V scheduling algorithm
- Optimal scheduling
- Algorithm evaluation

**Multilevel feedback queue scheduling** allows a process to move between queues. The
idea is to separate processes with different CPU burst characteristics. If a process uses too
much CPU time, it will be moved to a lower-priority queue. This scheme leaves I/O
bound and interactive processes in the higher-priority queues. Similarly a process that
waits too long in a lower-priority queue may be moved o a higher priority queue. This
form of aging prevents starvation.

In general, a multi-level feedback queue scheduler is defined by the following
parameters:

- Number of queues
- Scheduling algorithm for each queue
- Method used to determine when to upgrade a process to higher priority queue
- Method used to determine when to demote a process
- Method used to determine which queue a process enters when it needs service

Figure 17.1 shows an example multilevel feedback queue scheduling system with the
ready queue partitioned into three queues. In this system, processes with next CPU bursts
less than or equal to 8 time units are processed with the shortest possible wait times,
followed by processes with CPU bursts greater than 8 but no greater than 16 time units.

Processes with CPU greater than 16 time units wait for the longest time.

\

Figure 17.1 Multilevel Feedback Queues Scheduling

UNIX System V scheduling algorithm is essentially a multilevel feedback priority queues algorithm with round robin within each queue, the quantum being equal to1 second. The priorities are divided into two groups/bands:

- Kernel Group
- User Group

Priorities in the Kernel Group are assigned in a manner to minimize bottlenecks, i.e, processes waiting in a lower-level routine get higher priorities than those waiting at relatively higher-level routines. We discuss this issue in detail in the lecture with an example. In decreasing order of priority, the kernel bands are:

- Swapper
- Block I/O device control processes
- File manipulation
- Character I/O device control processes
- User processes

The priorities of processes in the Kernel Group remain fixed whereas the priorities of processes in the User Group are recalculated every second. Inside the User Group, the CPU-bound processes are penalized at the expense of I/O-bound processes. Figure 17.2 shows the priority bands for the various kernel and user processes.

Figure 17.2. UNIX System V Scheduling Algorithm

Every second, the priority number of all those processes that are in the main memory and ready to run is updated by using the following formula:

**Priority # = (Recent CPU Usage)/2 + Threshold Priority + nice**

The ‘threshold priority’ and ‘nice’ values are always positive to prevent a user from
migrating out of its assigned group and into a kernel group. You can change the nice
value of your process with the nice command.

In Figure 17.3, we illustrate the working of the algorithm with an example. Note that
recent CPU usage of the current process is updated every clock tick; we assume that
clock interrupt occurs every sixtieth of a second. The priority number of every process in
the ready queue is updated every second and the decay function is applied before
recalculating the priority numbers of processes.

Figure 17.3 Illustration of the UNIX System V Scheduling Algorithm

Figure 17.4 shows that in case of a tie, processes are scheduled on First-Come-First- Serve basis.

Figure 17.4 FCFS Algorithm is Used in Case of a Tie

To select an algorithm, we must take into account certain factors, defining their relative importance, such as:

- Maximum CPU utilization under the constraint that maximum response time is 1 second.
- Maximize throughput such that turnaround time is (on average) linearly proportional to total execution time.

Scheduling algorithms can be evaluated by using the following techniques:

A scheduling algorithm and some system workload are used to produce a formula or number, which gives the performance of the algorithm for that workload. Analytic evaluation falls under two categories:

**Deterministic modeling** is a type of analytic evaluation. This method takes a particular
predetermined workload and defines the performance of each algorithm for workload in
terms of numbers for parameters such as average wait time, average turnaround time, and
average response time. Gantt charts are used to show executions of processes. We have
been using this technique to explain the working of an algorithm as well as to evaluate
the performance of an algorithm with a given workload.

Deterministic modeling is simple and fast. It gives exact numbers, allowing the
algorithms to be compared. However it requires exact numbers for input and its answers
apply to only those cases.

The computer system can be defined as a network of servers. Each server has a queue of
waiting processes. The CPU is a server with its ready queue, as are I/O systems with their
device queues. Knowing the arrival and service rates of processes for various servers, we
can compute utilization, average queue length, average wait time, and so on. This kind of
study is called **queuing-network analysis.** If n is the average queue length, W is the average waiting time in the queue, and let λ is the average arrival rate for new processes
in the queue, then

**n = λ * W**

This formula is called the** Little’s formula,** which is the basis of **queuing theory**, a
branch of mathematics used to analyze systems involving queues and servers.

At the moment, the classes of algorithms and distributions that can be handled by
queuing analysis are fairly limited. The mathematics involved is complicated and
distributions can be difficult to work with. It is also generally necessary to make a
number of independent assumptions that may not be accurate. Thus so that they will be
able to compute an answer, queuing models are often an approximation of real systems.

As a result, the accuracy of the computed results may be questionable.

The table in Figure 17.5 shows the average waiting times and average queue lengths
for the various scheduling algorithms for a pre-determined system workload, computed
by using Little’s formula. The average job arrival rate is 0.5 jobs per unit time.

Figure 17.5 Average Wait Time and Average Queue Length Computed With Little’s Equation

Simulations involve programming a model of the computer system, in order to get a more
accurate evaluation of the scheduling algorithms. Software date structures represent the
major components of the system. The simulator has a variable representing a clock; as
this variable’s value is increased, the simulator modifies the system state to reflect the
activities of the devices, the processes and the scheduler. As the simulation executes,
statistics that indicate algorithm performance are gathered and printed. Figure 17.6 shows
the schematic for a simulation system used to evaluate the various scheduling algorithms.

Some of the major issues with simulation are:

- Expensive: hours of programming and execution time are required
- Simulations may be erroneous because of the assumptions about distributions used for arrival and service rates may not reflect a real environment

Figure 17.6 Simulation of Scheduling Algorithms

Even a simulation is of limited accuracy. The only completely accurate way to evaluate a
scheduling algorithm is to code it, put it in the operating system and see how it works.

This approach puts the actual algorithm in the real system for evaluation under real
operating conditions. The Open Source software licensing has made it possible for us to
test various algorithms by implementing them in the Linux kernel and measuring their
true performance.

The major difficulty is the cost of this approach. The expense is incurred in coding
the algorithm and modifying the operating system to support it, as well as its required
data structures. The other difficulty with any algorithm evaluation is that the environment
in which the algorithm works will change.