SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Module 2: Process Management

Introduction

A process can be thought of as a program in execution. A process will need certain resources-such as
CPU time, memory, files, and I/O devices -to accomplish its task. These resources are allocated to the
process either when it is created or while it is executing.

A process is the unit of work in most systems. Systems consist of a collection of processes: Operating-
system processes execute system code, and user processes execute user code. All these processes may
execute concurrently.

Although traditionally a process contained only a single thread of control as it ran, most modem
operating systems now support processes that have multiple threads.

The operating system is responsible for the following activities in connection with process and thread
management: the creation and deletion of both user and system processes; the scheduling of processes;
and the provision of mechanisms for synchronization, communication, and deadlock handling for
processes.

The more complex the operating system is, the more it is expected to do on behalf of its users. Although
its main concern is the execution of user programs, it also needs to take care of various system tasks that
are better left outside the kernel itself. A system therefore consists of a collection of processes: operating
system processes executing system code and user processes executing user code. Potentially all these
processes can execute concurrently/ with the CPU (or CPUs) multiplexed among them. By switching the
CPU between processes, the operating system can make the computer more productive.

The Process:

The Process Informally, a process is a program in execution. A process is more than the program code,
which is sometimes known as the text section. It also includes the current activity, as represented by the
value of the program counter and the contents of the processor's registers.

A process generally also includes the process stack, which contains temporary data (such as function
parameters, return addresses, and local variables), and a data section, which contains global variables. A
process may also include a heap, which is memory that is dynamically allocated during process run time.
The structure of a process in memory is shown in Figure .

1
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

We emphasize that a program by itself is not a process; a program is a passive entity, such as a file
containing a list of instructions stored on disk (often called an executable file), whereas a process is an
active entity, with a program counter specifying the next instruction to execute and a set of associated
resources. A program becomes a process when an executable file is loaded into memory. Two common
techniques for loading executable files are double-clicking an icon representing the executable file and
entering the name of the executable file on the command line (as in prog. exe or a. out.)

Although two processes may be associated with the same program, they are nevertheless considered
two separate execution sequences. For instance, several users may be running different copies of the mail
program, or the same user may invoke many copies of the Web browser program. Each of these is a
separate process; and although the text sections are equivalent, the data, heap, and stack sections vary.
It is also common to have a process that spawns many processes as it runs.

Process State

As a process executes, it changes state. The state of a process is defined in part by the current activity of
that process.

Each process may be in one of the following states:

New. The process is being created.

Running. Instructions are being executed.

Waiting. The process is waiting for some event to occur (such as an I/0 completion or reception of a
signal).

Ready. The process is waiting to be assigned to a processor.

Terminated. The process has finished execution. T

2
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

These names are arbitrary, and they vary across operating systems. The states that they represent are
found on all systems, however. Certain operating systems also more finely delineate process states. It is
important to realize that only one process can be running on any processor at any instant. Many processes
may be ready and waiting, however. The state diagram corresponding to these states is presented in
Figure.

Process Control Block:

Each process is represented by operating system by process control block _ (PCB)-also called a task control
block. A PCB is shown in Figure . It contains many pieces of Information associated with a specific process,
including these:

Process state. The state may be new, ready running, waiting, halted, and so on.

Program counter. The counter indicates the address of the next instruction to be executed for this
process.

CPU registers. The registers vary in number and type, depending on the computer architecture. They
include accumulators, index registers, stack pointers, and general-purpose registers, plus any condition-
code information. Along with the program counter, this state information must be saved when an
interrupt occurs, to allow the process to be continued correctly afterward (Figure ).

3
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

CPU-scheduling information. This information includes a process priority, pointers to scheduling queues,
and any other scheduling parameters.

Memory-management information. This information may include such information as the value of the
base and limit registers, the page tables, or the segment tables, depending on the memory system used
by the operating system .

Accounting information. This information includes the amount of CPU and real time used, time limits,
account numbers, job or process numbers, and so on.

I/O status information. This information includes the list of I/O devices allocated to the process, a list of
open files, and so on.

Figure Diagram showing CPU switch from process to process.

So, the PCB simply serves as the repository for any information that may vary from process to process.

4
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Switching the CPU to another process requires performing a state save of the current process and a state
restore of a different process. This task is known as ‘Context Switch’. When a context switch occurs, the
kernel saves the context of the old process in its PCB and loads the saved context of the new process
scheduled to run. Context-switch time is pure overhead, because the system does no useful work while
switching. Its speed varies from machine to machine, depending on the memory speed, the number of
registers that must be copied, and the existence of special instructions (such as a single instruction to load
or store all registers). Typical speeds are a few milliseconds.

#Operations on Process:
The processes in most systems can execute concurrently, and they may be created and deleted
dynamically. Thus, these systems must provide a mechanism for process creation and termination.

1 Process Creation:

A process may create several new processes, via a create-process system call, during the course of
execution. The creating process is called a parent process, and the new processes are called the children
of that process. Each of these new processes may in turn create other processes, forming a tree of
processes.

Fig. Processes Tree on a Solaris System

5
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

When a process creates a new process, two possibilities exist in terms of execution:

1. The parent continues to execute concurrently with its children.

2. 2. The parent waits until some or all of its children have terminated.

There are also two possibilities in terms of the address space of the new process:

[Link] child process is a duplicate of the parent process (it has the same program and data as the
parent).

[Link] child process has a new program loaded into it.

Typically, the exec() system call is used after a fork() system call by one of the two processes to replace
the process's memory space with a new program. The exec() system call loads a binary file into memory
(destroying the memory image of the program containing the exec() system call) and starts its
execution.

2 Process Termination:

A process terminates when it finishes executing its final statement and asks the operating system to
delete it by using the exit () system calL At that point, the process may return a status value
(typically an integer) to its parent process (via the wait() system call). All the resources of the
process-including physical and virtual memory, open files, and I/0 buffers-are deallocated by the
operating system.

A parent may terminate the execution of one of its children for a variety of reasons, such as these:

[Link] child has exceeded its usage of some of the resources that it has been allocated. (To
determine whether this has occurred, the parent must have a mechanism to inspect the state of its
children.)

[Link] task assigned to the child is no longer required.

[Link] parent is exiting, and the operating system does not allow a child to continue if its parent
terminates.

Some systems, including VMS, do not allow a child to exist if its parent has terminated. In such
systems, if a process terminates (either normally or abnormally), then all its children must also be
terminated. This phenomenon, referred to as cascading termination, is normally initiated by the
operating system.

Questions:
What is threading and Multithreading? Explain importance of Multithreading.
What is thread? How multithreading is beneficial? Compare and contrast different
multithreading models?
Differentiate between Process and thread.

6
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

No Process Thread

1. When a program is under execution, A segment of a process is known as

then it is known as a process. thread.

2. It consumes maximum time to stop. It consumes minimum time to stop.

3. It needs more time for work and It needs less time for work and
conception. conception.

4. Context switching takes maximum time Here, context switching takes minimum
here. time.

5. It is not that effective in terms of It is effective in terms of communication.

communication.

6. It takes more resources. It takes less resources.

7. It is a heavy weight process. It is a light weight process.

8. If one process is obstructed then it will If one thread is obstructed then it will
not affect the operation of another affect the execution of another process.
process.

7
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Thread:
A thread is a sequence of code that runs within a process and keeps track of its location in memory
so it can resume where it left off when it next gets called. It is a lightweight process doing the same
task as a process.
One process can have multiple threads.
Threads are a way that the operating system handles the multiple tasks that you might ask it to do
at the same time. In an ideal world, the operating system would be able to do all of these tasks
simultaneously, but that isn’t always possible. The running programs are all linked together,
meaning they’re all running in parallel. This makes it possible for the programs to work together
as a team, rather than working against each other.
What is Multi-Threading?
Multithreading is the process of executing multiple tasks simultaneously. In computer science,
multithreading refers to a program running in parallel with another program. This means that the
two programs are executing at the same time, on separate threads of execution. Multiple tasks can
be executed simultaneously on separate cores of a processor or separate processors.

Example of Multi-Threading in real-life scenarios-

If you’re trying to open a file in your program, you might want to be able to do it without
waiting for the program that you’re running in the back.
If you are processing data in a database, you can use a thread to process the data cooperatively.
In this scenario, the data is written to the database in parallel, and then the threads read the
data back.
Downloading the file and viewing it simultaneously.
Video games are based on multithreading where graphics run in the background.

How Multi-Threading works in the operating system-

8
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Multithreading in operating systems is implemented through the use of threading

libraries. These libraries provide the programmer with APIs that make it easy to
create multithreaded programs. The threading library takes care of all the low-level
coordination required to keep the threads running in a synchronized fashion. This
synchronization is necessary
Advantages of Multi-Threading-
Multithreading allows the CPU to execute multiple tasks simultaneously, which can
boost performance.
Multithreading reduces the amount of time that is spent waiting for a task to finish.
Multithreading can help to improve the scalability of a program.
Interactive applications may allow a program to continue running even if part of it
is blocked or is performing a lengthy operation, thereby increasing responsiveness.
Disadvantages of Multi-Threading -
Multithreading can be complex and challenging to implement.
Multithreading can increase the complexity of a program.
Multithreading can be error-prone.
Programmers must carefully design their code to utilize multithreading capabilities
without introducing unwanted delays or fragmentation into their programs’
execution

#User thread and karnel thread:

What is User Level Thread?

The User-level threads are small and faster as compared to kernel-level threads, and the OS
directly supports user-level threads. Users implement the user-level threads, and the kernel is
unaware of their existence and handles them as though they are single-threaded processes.
These threads are represented by registers, the program counter (PC), stack, and some small
process control. Furthermore, there is no kernel interaction in user-level thread
synchronization.
It is also known as the many-to-one mapping thread, as the OS assigns every thread in a
multithreaded program to an execution context. Every multithreaded process is treated as a
single execution unit by the OS.

Advantages and Disadvantages of User Level Threads

There are various advantages and disadvantages of User-level Threads. Some of the
advantages and disadvantages of User-level Threads are as follows:
Advantages
User level threads are simpler and faster to generate. They are also easier to manage.
Thread switching in user-level threads doesn't need kernel mode privileges.
These are more portable.
These threads may be run on any OS.
Disadvantages
The complete process is blocked if a user-level thread runs a blocking operation.
User-level threads don't support system-wide scheduling priorities.

9
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

It is not appropriate for a multiprocessor system.

What are Kernel Level Threads?

In Kernel Level Thread, the kernel handles all thread management. Every process doesn't
have a thread table, but the kernel has one that maintains track of all of the threads in the
system. If a thread wishes to make a new thread or stop an existing one, it initiates a kernel
call that performs the work.
The kernel-level threads table contains each thread's registers, status, and other information.
The data is identical to that of user-level threads, except it is now in kernel space rather than
user space.

Advantages and Disadvantages of Kernel Level Threads-

There are various advantages and disadvantages of kernel-level Threads. Some of
the advantages and disadvantages of Kernel-level Threads are as follows:
Advantages
If a thread in the kernel is blocked, it does not block all other threads in the same
process.
Several threads of the same process might be scheduled on different CPUs in kernel-
level threading.
Kernel routines can be multithreaded as well.
Disadvantages
Compared to user-level threads, kernel-level threads take longer to create and
maintain.
A mode switch to kernel mode is important to transfer control from one thread in a
process to another.

#Multi-Threading Models
Multithreading allows the execution of multiple parts of a program at the same time. These
parts are known as threads and are lightweight processes available within the process.
Therefore, multithreading leads to maximum utilization of the CPU by multitasking.
The main models for multithreading are one to one model, many to one model and many to
many model. Details about these are given as follows −
One to One Model
The one to one model maps each of the user threads to a kernel thread. This means that many
threads can run in parallel on multiprocessors and other threads can run when one thread
makes a blocking system call.
A disadvantage of the one to one model is that the creation of a user thread requires a
corresponding kernel thread. Since a lot of kernel threads burden the system, there is
restriction on the number of threads in the system.
A diagram that demonstrates the one to one model is given as follows −

10
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Many to One Model

The many to one model maps many of the user threads to a single kernel thread. This model
is quite efficient as the user space manages the thread management.
A disadvantage of the many to one model is that a thread blocking system call blocks the
entire process. Also, multiple threads cannot run in parallel as only one thread can access the
kernel at a time.
A diagram that demonstrates the many to one model is given as follows −

Many to Many Model

The many to many model maps many of the user threads to a equal number or lesser kernel
threads. The number of kernel threads depends on the application or machine.

11
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

The many to many does not have the disadvantages of the one to one model or the many to
one model. There can be as many user threads as required and their corresponding kernel
threads can run in parallel on a multiprocessor.
A diagram that demonstrates the many to many model is given as follows −

# Process Scheduling:
CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among
processes, the operating system can make the computer more productive.

In a single-processor system, only one process can run at a time; any others must wait until the CPU
is free and can be rescheduled. The objective of multiprogramming is to have some process running
at all times, to maximize CPU utilization. The idea is relatively simple. A process is executed until it
must wait, typically for the completion of some I/O request. In a simple computer system, the CPU
then just sits idle. All this waiting time is wasted; no useful work is accomplished. With
multiprogramming, we try to use this time productively. Several processes are kept in memory at one
time. When one process has to wait, the operating system takes the CPU away from that process and
gives the CPU to another process. This pattern continues. Every time one process has to wait, another
process can take over use of the CPU. Scheduling of this kind is a fundamental operating-system
function. Almost all computer resources are scheduled before use. The CPU is, of course, one of the
primary computer resources. Thus, its scheduling is central to operating-system design.

1 CPU-i/O Burst Cycle:

The success of CPU scheduling depends on an observed property of processes: process execution
consists of a cycle of CPU execution and I/0 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

12
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

another CPU burst, then another I/0 burst, and so on. Eventually, the final CPU burst ends with a
system request to terminate execution.

Figure : Alternating sequence of CPU and I/O bursts.

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. Note that the ready queue is not necessarily
a first-in, first-out (FIFO) queue. As we shall see when we consider the various scheduling algorithms,
a ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered
linked list.

When to Schedule?

Process scheduling decisions may take place under the following circumstances:

• When a process switches from the new state to the ready state.

• When a process switches from the running state to the waiting state (I/O or event wait).

• When a process switches from the running state to the ready state (interrupt).

• When a process switches from the waiting state to the ready

state (I/O or event completion).

• When a process terminates.

13
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

Dispatcher: Another component involved in the CPU-scheduling function is the 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 The dispatcher should be as fast as
possible, since it is invoked during every process switch. The time it takes for the dispatcher to stop
one process and start another running is known as the dispatch latency.

#Non-preemptive vs. Preemptive Scheduling

• Under non-preemptive (or cooperative) scheduling, each running process keeps the CPU
until it completes or it switches to the waiting (blocked) state (points 2 and 5 from
previous slides).

• Under preemptive scheduling, a running process may be also forced to release the CPU
even though it is neither completed nor blocked.

• In time-sharing systems, when the running process reaches the end of its time quantum
(slice)

• In general, whenever there is a change in the ready queue.

# Scheduling Criteria

Different CPU-scheduling algorithms have different properties, and the choice of a particular
algorithm may favor one class of processes over another. In choosing which algorithm to use in a
particular situation, we must consider the properties of the various algorithms. Many criteria have
been suggested for comparing CPU-scheduling algorithms. Which characteristics are used for
comparison can make a substantial difference in which algorithm is judged to be best. The criteria
include the following:

CPU utilization.: We want to keep the CPU as busy as possible. Conceptually, CPU utilization can
range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded
system) to 90 percent (for a heavily used system).

Throughput. If the CPU is busy executing processes, then work is being done. One measure of
work is the number of processes that are completed per time unit, called throughput. For long
processes, this rate may be one process per hour; for short transactions, it may be ten processes
per second.

Turnaround time. From the point of view of a particular process, the important criterion is how
long it takes to execute that process. The interval from the time of submission of a process to the
time of completion is the turnaround time. Turnaround time is the sum of the periods spent
waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/0.
Waiting time. The CPU-scheduling algorithm does not affect the amount of time during which a
process executes or does I/0; it affects only the [Link] of time that a process spends waiting in
the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.
Response time. In an interactive system, turnaround time may not be the best criterion. Often, a

14
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

process can produce some output fairly early and can continue computing new results while
previous results are being output to the user. Thus, another measure is the time from the
submission of a request until the first response is produced. This measure, called response time,
is the time it takes to start responding, not the time it takes to output the response. The
turnaround time is generally limited by the speed of the output device.

# Scheduling Algorithm

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is
to be allocated the CPU. There are many different CPU-scheduling algorithms.

1 First-Come, First-Served Scheduling By far the simplest CPU-scheduling algorithm is the first-
come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the
CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with
a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue.
When the CPU is free, it is allocated to the process at the head of the queue. The running process
is then removed from the queue. The code for FCFS scheduling is simple to write and understand.

2 Shortest-Job-First Scheduling A different approach to CPU scheduling is the shortest-job-first

(SJF) scheduling algorithm. This algorithm associates with each process the length of the process's
next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next
CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break
the tie. Note that a more appropriate term for this scheduling method would be the shortest-
next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a
process, rather than its total length.

A preemptive SJF algorithm will preempt the currently executing process, whereas a
nonpreemptive SJF algorithm will allow the currently running process to finish its CPU burst.
Preemptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling.

3 Priority Scheduling:The SJF algorithm is a special case of the general priority scheduling
algorithm. A priority is associated with each process, and the CPU is allocated to the process with
the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is
simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst.
The larger the CPU burst, the lower the priority, and vice versa.

Note that we discuss scheduling in terms of high priority and low priority. Priorities are generally
indicated by some fixed range of numbers, such as 0 to 7 or 0 to 4,095. However, there is no
general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers
to represent low priority; others use low numbers for high priority.

Priority scheduling can be either preemptive or nonpreemptive. When a process arrives at the
ready queue, its priority is compared with the priority of the currently running process. A
preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived

15
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

process is higher than the priority of the currently running process. A nonpreemptive priority
scheduling algorithm will simply put the new process at the head of the ready queue.

A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A

process that is ready to run but waiting for the CPU can be considered blocked. A priority
scheduling algorithm can leave some low priority processes waiting indefinitely.

A solution to the problem of indefinite blockage of low-priority processes is aging. Aging is a

technique of gradually increasing the priority of processes that wait in the system for a long time.
For example, if priorities range from 127 (low) to 0 (high), we could increase the priority of a
waiting process by 1 every 15 minutes.

4 Round-Robin Scheduling: The round-robin (RR) scheduling algorithm is designed especially for
timesharing systems. It is similar to FCFS scheduling, but preemption is added to enable the
system to switch between processes. A small unit of time, called a time quantum or time slice, is
defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is
treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU
to each process for a time interval of up to 1 time quantum.

To implement RR scheduling, we keep the ready queue as a FIFO queue o£ processes. New
processes are added to the tail of the ready queue. The CPU scheduler picks the first process from
the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. One
of two things will then happen. The process may have a CPU burst of less than 1 time quantum.
In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to
the next process in the ready queue. Otherwise, if the CPU burst of the currently running process
is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating
system. A context switch will be executed, and the process will be put at the tail o£ the ready
queue. The CPU scheduler will then select the next process in the ready queue. The average
waiting time under the RR policy is often long.

In the RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in
a row (unless it is the only runnable process). If a process's CPU burst exceeds 1 time quantum,
that process is preempted and is put back in the ready queue. The RR scheduling algorithm is thus
preemptive.

If there are n. processes in the ready queue and the time quantum is q, then each process gets

1 /n of the CPU time in chunks of at most q time units. Each process must wait no longer than (n
- 1) x q time units until its next time quantum. For example, with five processes and a time
quantum of 20 milliseconds, each process will get up to 20 milliseconds every 100 milliseconds.

The performance of the RR algorithm depends heavily on the size of the time quantum. At one
extreme, if the time quantum is extremely large, the RR policy is the same as the FCFS policy. In
contrast, if the time quantum is extremely small (say, 1 millisecond), the RR approach is called
processor sharing and (in theory) creates the appearance that each of 11 processes has its own
processor running at 1 /n the speed of the real processor.

16
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

we want the time quantum to be large with respect to the context switch time. If the context-
switch time is approximately 10 percent of the time quantum, then about 10 percent of the CPU
time will be spent in context switching. In practice, most modern systems have time quanta
ranging from 10 to 100 milliseconds. The time required for a context switch is typically less than
10 microseconds; thus, the context-switch time is a small fraction of the time quantum.

Turnaround time also depends on the size of the time quantum.

The time quantum should be large compared with the context switch time, it should not be too
large. If the time quantum is too large, RR scheduling degenerates to an FCFS policy. A rule of
thumb is that 80 percent of the CPU bursts should be shorter than the time quantum.

5 Multilevel Queue Scheduling:

Another class of scheduling algorithms has been created for situations in which processes are
easily classified into different groups. For example, a common division is made between
foreground (interactive) processes and background (batch) processes. These two types of
processes have different response-time requirements and so may have different scheduling
needs. In addition, foreground processes may have priority (externally defined) over background
processes. A multilevel queue scheduling algorithm partitions the ready queue into several
separate queues (Figure ). The processes are permanently assigned to one queue, generally based
on some property of the process, such as memory size, process priority, or process type. Each
queue has its own scheduling algorithm. For example, separate queues might be used for
foreground and background processes. The foreground queue might be scheduled by an RR
algorithm, while the background queue is scheduled by an FCFS algorithm. In addition, there must
be scheduling among the queues, which is commonly implemented as fixed-priority preemptive

17
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

scheduling. For example, the foreground queue may have absolute priority over the background
queue.

Figure Multilevel queue scheduling

Each queue has absolute priority over lower-priority queues. No process in the batch queue, for
example, could run unless the queues for system processes, interactive processes, and interactive
editing processes were all empty. If an interactive editing process entered the ready queue while
a batch process was running, the batch process would be preempted.

6 Multilevel Feedback Queue Scheduling:

Normally, when the multilevel queue scheduling algorithm is used, processes are permanently
assigned to a queue when they enter the system. If there are separate queues for foreground and
background processes, for example, processes do not move from one queue to the other, since
processes do not change their foreground or background nature. This setup has the advantage of
low scheduling overhead, but it is inflexible. The multilevel feedback queue scheduling algorithm,
in contrast, allows a process to move between queues. The idea is to separate processes according
to the characteristics of their CPU bursts. 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. In addition, a process that waits too long in a lower-priority queue may be moved
to a higher-priority queue. This form of aging prevents starvation.

For example, consider a multilevel feedback queue scheduler with three queues, numbered from
0 to 2 (Figure ). The scheduler first executes all processes in queue 0. Only when queue 0 is empty
will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues
0 and 1 are empty. A process that arrives for queue 1 will preempt a process in queue 2. A process
in queue 1 will in turn be preempted by a process arriving for queue 0. A process entering the
ready queue is put in queue 0. A process in queue 0 is given a time quantum of 8 milliseconds. If
it does not filcish within this time, it is moved to the tail of queue 1. If queue 0 is empty, the
process at the head of queue 1 is given a quantum of 16 milliseconds. If it does not complete, it is
preempted and is put into queue 2. Processes in queue 2 are run on an FCFS basis but are run only
when queues 0 and 1 are empty. This scheduling algorithm gives highest priority to any process

18
 SFIT, Borivali

Class-SE (A&B) Subject:Operating System Subject Teacher: [Link] Rane

*************************************************************************************

with a CPU burst of 8 milliseconds or less. Such a process will quickly get the CPU, finish its CPU
burst, and go off to its next I/0 burst. Processes that need more than 8 but less than 24
milliseconds are also served quickly, although with lower priority than shorter processes. Long
processes automatically sink to queue 2 and are served in FCFS order with any CPU cycles left over
from queues 0 and 1.

In general, a multilevel feedback queue scheduler is defined by the following parameters:

[Link] number of queues

[Link] scheduling algorithm for each queue

[Link] method used to determine when to upgrade a process to a higher priority queue

[Link] method used to determine when to demote a process to a lower priority queue

5. The method used to determine which queue a process will enter when that process needs
service

The definition of a multilevel feedback queue scheduler makes it the most general CPU-scheduling
algorithm. It can be configured to match a specific system under design. Unfortunately, it is also
the most complex algorithm, since defining the best scheduler requires some means by which to
select values for all the parameters.

19