MODULE 2

Process and Process

Management
Processes and Process Management
Process concept and process states,

CPU and I/O bound, operating system services for process and thread
management,

CPU scheduler- short, medium, long-term, dispatcher

Scheduling: - preemptive and non-preemptive, scheduling algorithms- FCFS, SJFS,

shortest remaining time, RR, priority scheduling, Multilevel feedback queue

 PROCESS CONCEPT
Process is the execution of a program that performs the actions specified in that program. It can be defined as an
execution unit where a program runs. The OS helps you to create, schedule, and terminates the processes which is
used by CPU

Main Secondar
memory y Storage

CPU
Process Program
PROCESS CONCEPT An operating system executes a variety of programs:
Batch system – jobs
• Process – a program in execution; Time-shared systems – user programs or tasks
Textbook uses the terms job and process almost
• It is also called as job,task,unit of interchangeably
work. Multiple parts
The program code, also called text section
• Process execution must progress Current activity including program counter,
in sequential fashion processor registers
• Stack containing temporary data
A process is an activity and it has
Function parameters, return addresses, local
program - data Resources variables
state Data section containing global variables
Heap containing memory dynamically allocated
• Logically : each process has its during run time
separate virtual CPU. Program is passive entity stored on disk (executable
Real : CPU switches from one file), process is active Program becomes process when
process to another. executable file loaded into memory
Execution of program started via GUI mouse clicks,
command line entry of its name, etc
One program can be several processes. Consider
multiple users executing the same program
ALTERNATING SEQUENCE OF CPU AND I/O BURSTS
 PROCESS IN MEMORY
When a program is loaded into the memory and it becomes a process, it can be divided into four sections ─
stack, heap, text and data. The following image shows a simplified layout of a process inside main memory

The process stack contains the temporary

data like method parameters, return
address, local variables

This is dynamically allocated memory to a process during its

run time.(sys calls : new, delete,malloc,free)

Global and static

variables
includes the current activity represented by the value of
Program Counter and the contents of the processor's
registers.
A process is basically a program in execution. The execution of a process must progress in
a sequential fashion. A process is defined as an entity which represents the basic unit of work to be
implemented in the system.
To put it in simple terms, we write our computer programs in a text file and when we
execute this program, it becomes a process which performs all the tasks mentioned in the
program.

A program is a piece of code which may be a single line or millions of lines. A computer
program is usually written by a computer programmer in a programming language.
For example, here is a simple program written in C programming language −
#include <stdio.h>
int main()
{
printf("Hello, World! \n"); return 0;
}

A computer program is a collection of instructions that performs a specific task when executed
by a computer. When we compare a program with a process, we can conclude that a process is
a dynamic instance of a computer program.
A part of a computer program that performs a well-defined task is known as an algorithm.
A collection of computer programs, libraries and related data are referred to as a software.
 PROCESS IN MEMORY/ Process Life Cycle
When a process executes, it passes through different states. These stages may differ in different operating systems, and the
names of these states are also not standardized.
In general, a process can have one of the following
five states at a time.

S.N. State & Description

Start
1
This is the initial state when a process is first started/created.
Ready
The process is waiting to be assigned to a processor. Ready processes are waiting to have the
2 processor allocated to them by the operating system so that they can run. Process may come into
this state after Start state or while running it by but interrupted by the scheduler to assign CPU to
some other process.
Running
3 Once the process has been assigned to a processor by the OS scheduler, the process state is set to
running and the processor executes its instructions.
Waiting
4 Process moves into the waiting state if it needs to wait for a resource, such as waiting for user input,
or waiting for a file to become available.
Terminated or Exit
5 Once the process finishes its execution, or it is terminated by the operating system, it is moved to the
terminated state where it waits to be removed from main memory.
 PROCESS STATE
• As a process executes, it changes …..

• new: The process is being created

• running: Instructions are being executed
• waiting: The process is waiting for some
event to occur
• ready: The process is waiting to be
assigned to a processor
• terminated: The process has finished
execution
A THREE-STATE PROCESS MODEL

Ready Running

Time-out

Event Event
Occurs Wait

Waiting
PROCESS TRANSITIONS (1)
• Ready –> Running
• When it is time, the dispatcher selects a new
process to run.
• Running –> Ready
• the running process has expired his time slot.
• the running process gets interrupted because
a higher priority process is in the ready state.
PROCESS TRANSITIONS (2)
• Running –> Waiting
• When a process requests something for which it must wait:
• a service that the OS is not ready to perform.
• an access to a resource not yet available.
• initiates I/O and must wait for the result.
• waiting for a process to provide input.
• Waiting –> Ready
• When the event for which it was waiting occurs.
FIVE-STATE PROCESS MODEL
 PROCESS ATTRIBUTES
• Process ID
• Parent process ID
• User ID
• Process state/priority
• Program counter
• CPU registers
• Memory management information
• I/O status information
• Access Control
• Accounting information
PROCESS CONTROL BLOCK (PCB)
Information associated with each process
Information associated with each
process (also called task control block)
 Process state – running, waiting, etc
• Process state
 Program counter – location of instruction to next
• Process Privileges
execute
• Process Id  CPU registers – contents of all process-centric
• Pointer
registers
 CPU scheduling information- priorities, scheduling
• Program counter
queue pointers
• CPU registers  Memory-management information – memory allocated
• CPU scheduling information
to the process
 Accounting information – CPU used, clock time
• Memory-management information
elapsed since start, time limits
• Accounting information  I/O status information – I/O devices allocated to
• I/O status information
process, list of open files
PROCESS CONTROL BLOCK (PCB)
 PROCESSES IN MEMORY (2)
A. Frank - P. Weisberg
 TYPICAL PROCESS TABLE ENTRY
A. Frank - P. Weisberg
COMPONENTS OF PROCESS CONTROL BLOCK (PCB)

• Process Control Block (PCB) – IBM name for information

associated with each process – its context!
• PCB (execution context) is the data needed (process

attributes) by OS to control process :

1. Process location information
2. Process identification information
3. Processor state information
4. Process control information
PROCESS LOCATION INFORMATION
• Each process image in memory:
• may not occupy a contiguous range of addresses (depends on
memory management scheme used).
• both a private and shared memory address space can be used.

• The location if each process image is pointed to by an entry

in the process table.
• For the OS to manage the process, at least part of its image
must be brought into main memory.
PROCESS IMAGES IN MEMORY
PROCESS IDENTIFICATION INFORMATION
• A few numeric identifiers may be used:
• Unique process identifier (PID) –
• indexes (directly or indirectly) into the process table.
• User identifier (UID) –
• the user who is responsible for the job.
• Identifier of the process that created this process (PPID).
• Maybe symbolic names that are related to numeric identifiers.
PROCESSOR STATE INFORMATION
• Contents of processor registers:
• User-visible registers
• Control and status registers
• Stack pointers

• Program Status Word (PSW)

• contains status information
• Example: the EFLAGS register on Pentium machines.
PROCESS CONTROL INFORMATION

• scheduling and state information:

• Process state (i.e., running, ready, blocked...)
• Priority of the process
• Event for which the process is waiting (if blocked).

• data structuring information

• may hold pointers to other PCBs for process queues, parent-child
relationships and other structures.
PROCESS CONTROL INFORMATION
• Inter-process communication –
• may hold flags and signals for IPC.

• Resource ownership and utilization –

• resource in use: open files, I/O devices...
• history of usage (of CPU time, I/O...).

• Process privileges (Access control) –

• access to certain memory locations, to resources, etc…

• Memory management –
• pointers to segment/page tables assigned to this process.
OPERATIONS ON PROCESS: PROCESS CREATION AND TERMINATION

• New state –
• OS has performed the necessary actions to
create the process:
• has created a process identifier.
• has created tables needed to manage the
process.
• but has not yet committed to execute the
process (not yet admitted):
• because resources are limited.
• Terminated state –
• Program termination moves the process to this state.
• It is no longer eligible for execution.
• Tables and other info are temporarily preserved for
auxiliary program –
• Example: accounting program that cumulates
resource usage for billing the users.
• The process (and its tables) gets deleted when the data is
no more needed.
 REASONS FOR PROCESS CREATION

• System initialization.
• Submission of a batch job.
• User logs on.
• Created by OS to provide a service to a user (e.g., printing a
file).
• A user request to create a new process.
• Spawned by an existing process
• a program can dictate the creation of a number of processes.
PROCESS CREATION (1)
• Parent process create children processes, which, in turn create other
processes, forming a tree of processes.
• Possible resource sharing:
• Parent and children share all resources.
• Children share subset of parent’s resources.
• Parent and child share no resources.
• Possible execution:
• Parent and children execute concurrently.
• Parent waits until children terminate.
PROCESS CREATION (2)
• Assign a unique process identifier (PID).
• Allocate space for the process image.
• Initialize process control block
• many default values (e.g., state is New, no I/O devices or files...).

• Set up appropriate linkages

• Ex: add new process to linked list used for the scheduling queue.
 PROCESS CREATION (3)

• Address space
• Child duplicate of parent.
• Child has a program loaded into it.
• UNIX examples
• fork system call creates new process.
• exec system call used after a fork to replace
process memory space with a new program.
PROCESS CREATION (3)
WHEN DOES A PROCESS GET TERMINATED?

• Batch job issues Halt instruction.

• User logs off.
• Process executes a service
request to terminate.
• Parent kills child process.
• Error and fault conditions.
REASONS FOR PROCESS TERMINATION (1)
• Normal/Error/Fatal exit.
• Time limit exceeded
• Memory unavailable
• Memory bounds violation
• Protection error
• example: write to read-only file

• Arithmetic error
• Time overrun
• process waited longer than a specified maximum for an event.
 REASONS FOR PROCESS TERMINATION (2)

• I/O failure
• Invalid instruction
• happens when trying to execute data.

• Privileged instruction
• Operating system intervention
• such as when deadlock occurs.

• Parent request to terminate one child.

• Parent terminates so child processes terminate.
PROCESS TERMINATION
• Process executes last statement and asks the
operating system to terminate it (exit):
• Output data from child to parent (via wait).
• Process’ resources are deallocated by operating
system.
• Parent may terminate execution of child processes
(abort):
• Child has exceeded allocated resources.
• Mission assigned to child is no longer required.
• If Parent is exiting:
• Some OSs do not allow child to continue if its
parent terminates.
• Cascading termination – all children terminated.
SCHEDULERS
PROCESS SCHEDULING QUEUES

Maximize CPU use, quickly switch processes onto CPU for

time sharing
Process scheduler selects among available processes for
next execution on CPU
Maintains scheduling queues of processes
Job queue – set of all processes in the system
Ready queue – set of all processes residing in main
memory, ready and waiting to execute
Device queues – set of processes waiting for an I/O
device
Processes migrate among the various queues
SCHEDULING CRITERIA
• CPU utilization – keep the CPU as busy as possible
• Typically between 40% to 90%
• Throughput – # of processes that complete their execution per
time unit
• Depends on the length of process
• Turnaround time – amount of time to execute a particular process
• Sum of wait for memory, ready queue, execution, and I/O.
• Waiting time – amount of time a process has been waiting in the
ready queue
• Sum of wait in ready queue
• Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output
• for time-sharing environment
SCHEDULING ALGORITHM OPTIMIZATION CRITERIA

• Max CPU utilization

• Max throughput
• Min turnaround time
• Min waiting time
• Min response time
CPU SCHEDULER
• The CPU scheduler selects from among the processes in memory that are ready to
execute and allocates the CPU to one of them
• CPU scheduling is affected by the following set of circumstances:
1.(N) A process switches from running to waiting state
2.(P) A process switches from running to ready state
3.(P) A process switches from waiting to ready state
4.(N) A processes switches from running to terminated state
• Circumstances 1 and 4 are non-preemptive; they offer no schedule choice
• Circumstances 2 and 3 are pre-emptive; they can be scheduled
 TYPES OF CPU SCHEDULING

• Pre-Emptive Scheduling
• if a new process arrives with a CPU burst length less than the
remaining time of the current executing process, then it will pre-empt
the currently executing process.

• Non-Pre-Emptive Scheduling
• once the CPU is given to the process, it cannot be preempted until it
completes its CPU burst or till it switches to the waiting state.
 Three-level Scheduling

• Long-term scheduler
(or job scheduler) –
SHORT-TERM
selects which processes
should be brought into
the ready queue
• Short-term scheduler
(or CPU scheduler) –
selects which process
should be executed
next and allocates CPU
LONG-TERM MID-TERM
SINGLE PROCESSOR SCHEDULING
ALGORITHMS
 SINGLE PROCESSOR SCHEDULING ALGORITHMS

 First Come, First Served (FCFS)

 Shortest Job First (SJF)
 Shortest Remaining Time Next (SRTN)
 Priority
 Round Robin (RR)
 Multiple Level Queues Scheduling
SINGLE PROCESSOR SCHEDULING ALGORITHMS

A Gantt chart is a project management tool assisting in the planning and

scheduling of projects of all sizes; they are particularly useful for
visualising projects. A Gantt chart is defined as a graphical representation
of activity against time; it helps project professionals monitor progress.
Gantt charts are essentially task scheduling tools: project management
timelines and tasks are converted into horizontal bars (also called Gantt
bars) to form a bar chart. These Gantt bars show start and end dates, as
well as dependencies, scheduling and deadlines, including how much of
the task is completed per stage and who is the task owner. Gantt charts
show planned activity against time; they are frequently used throughout
projects, programmes and portfolios after tasks have been identified using
a work breakdown structure.
FIRST-COME, FIRST-SERVED (FCFS)
SCHEDULING
FCFS is non-preemptive algorithm. The process which requests the CPU first is allocated to
the CPU first.
Process CPU Burst Time
P1 24

P2 3
P3 3
• Case #1: Suppose that the processes arrive in the order: P1 , P2 , P3
P1 P2 P3

The Gantt Chart for the schedule is:

0 24 27 30

Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17

• Average turn-around time: (24 + 27 + 30)/3 = 27
FCFS SCHEDULING (CONT.)
• Case #2: Suppose that the processes arrive in the order: P2 , P3 , P1
P2 P3 P1
• The Gantt chart for the schedule is:
0 3 6 30
• Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3 (Much better than Case #1)

• Average turn-around time: (3 + 6 + 30)/3 = 13
• Case #1 is an example of the convoy effect; all the other processes wait for one long-
running process to finish using the CPU. This problem results in lower CPU and device
utilization;
•Case #2 shows that higher utilization might be possible if the short processes were
allowed to run first
• The FCFS scheduling algorithm is non-preemptive
• Once the CPU has been allocated to a process, that process keeps the CPU until it releases it
either by terminating or by requesting I/O
• It is a troublesome algorithm for time-sharing systems
EXAMPLE: 1
S. NO PROCESS ID PROCESS NAME ARRIVAL TIME BURST TIME
___ ______ _______ _______ _______
1 P1 A 0 9
2 P2 B 1 3
3 P3 C 1 2
4 P4 D 1 4
5 P5 E 2 3
6 P6 F 3 2
S. No Process ID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
1 A 0 9 9 9 0
2 B 1 3 12 11 8
3 C 1 2 14 13 11
4 D 1 4 18 17 13
5 E 2 3 21 19 16
6 F 3 2 23 20 18

The Average Completion Time is:

Average CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Average CT = 97 / 6 = 16.16667
The Average Waiting Time is:
Average WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Average WT = 66 / 6 = 11
The Average Turn Around Time is:
Average TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
Average TAT = 89 / 6 = 14.83334
This is how the FCFS is solved in Non Pre Emptive Approach.
AVERAGE WAITING TIME = (0 + 3 + 5 + 5+ 6 )/ 5 = 19 / 5
= 3.8
AVERAGE TURNAROUND TIME =???
Process Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Average Waiting Time

= 40/5= 8
Processes Arrival Time Burst Time

P1 0 4

P2 1 3

P3 2 1

P4 3 2

P5 4 5
•The overall execution of the processes will be as shown below:

Remaining
Time Execution Initial Burst
Process Arrival Time Waiting Table Burst Time
Instance Time Time

0-1ms P1 0ms 1ms 4ms 3ms

P1 0ms 1ms 3ms 2ms
1-2ms
P2 1ms P2 0ms 3ms 3ms
P1 0ms 1ms 2ms 1ms
2-3ms P2 1ms P2 0ms 3ms 3ms
P3 2ms P2, P3 0ms 1ms 1ms
P1 0ms 1ms 1ms 0ms
P2 1ms P2 0ms 3ms 3ms
3-4ms
P3 2ms P2, P3 0ms 1ms 1ms
P4 3ms P2, P3, P4 0ms 2ms 2ms
P2 1ms 1ms 3ms 2ms
P3 2ms P3 0ms 1ms 1ms
4-5ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms
P2 1ms 2ms 2ms 0ms
P3 2ms P3 0ms 1ms 1ms
5-7ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms
SHORTEST JOB FIRST (SJF)
SCHEDULING
SHORTEST-JOB-FIRST (SJF) SCHEDULING
• The SJF algorithm associates with each process the length of its next CPU burst
• Whenever CPU becomes available, it is assigned to the process that has the smallest
next CPU burst
• If two processes have the same next CPU Burst time then FCFS scheduling algorithm
is used to select the next process
• Two schemes:
• Non-pre-emptive – once the CPU is given to the process, it cannot be
preempted until it completes its CPU burst
• Pre-emptive – if a new process arrives with a CPU burst length less than the
remaining time of the current executing process, then it will pre-empt the
currently executing process. This scheme is know as the Shortest-Remaining-
Time-First (SRTF) scheduling
EXAMPLE #1: NON-PRE-EMPTIVE SJF (SIMULTANEOUS ARRIVAL)
Process Arrival Time Burst Time
P1 0.0 6

P2 0.0 4
P3 P2 P4 P1
P3 0.0 1
0 1 5 10 16
P4 0.0 5
•SJF (non-preemptive, simultaneous arrival)
•Average waiting time = (0 + 1 + 5 + 10)/4 = 4
•Average turn-around time = (1 + 5 + 10 + 16)/4 = 8
EXAMPLE #2: NON-PRE-EMPTIVE SJF(VARIED ARRIVAL TIMES)
Process Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1
P1 P3 P2 P4
P4 5.0 4
0 3 7 8 12 16
• SJF (non-preemptive, varied arrival times)

• Average waiting time

= ( (0 – 0) + (8 – 2) + (7 – 4) + (12 – 5) )/4
= (0 + 6 + 3 + 7)/4 = 4
• Average turn-around time:
= ( (7 – 0) + (12 – 2) + (8 - 4) + (16 – 5))/4
= ( 7 + 10 + 4 + 11)/4 = 8
EXAMPLE #3: PRE-EMPTIVE SJF (SHORTEST-REMAINING-TIME-FIRST)
Process Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4 P1 P2 P3 P2 P4 P1

• SJF (pre-emptive, varied arrival times)

0 2 4 5 7 11 16

• Average waiting time

= ( [(0 – 0) + (11 - 2)] + [(2 – 2) + (5 – 4)] + (4 - 4) + (7 – 5) )/4
= 9 + 1 + 0 + 2)/4
=3
• Average turn-around time = ((16-0) +(7-2) + (5-4) + (11-5))/4 = 7
EXAMPLE #3: PRE-EMPTIVE SJF (SHORTEST-REMAINING-TIME-FIRST)
Process Arrival Time Burst Time

P1 0.0 9

P2 2.0 2

P3 4.0 5
ADVANTAGES AND DISADVANTAGES OF SJF SCHEDULING ALGORITHM

•Advantages:
 Overall performance is slightly improved in terms of response time
 It’s having the least average waiting time, average turn around time and average
response time

•Disadvantages:
 There is a risk of starvation of longer processes
 It is difficult to know the length of the next CPU burst time
 SHORTEST REMAINING TIME NEXT (SRTN)

• Its Pre-emptive version of SJF scheduling

• At the arrival of every process, the short term scheduler schedules the
process with the least remaining burst time among the list of available
processes and the running process.
• Once all the processes are available in the ready queue, No pre-emption is
done and the algorithm will work as SJF scheduling.
• For SJF scheduling, OS should know the CPU brust time of next process.
• The Prediction of CPU burst is given by
• Tn+1=alpha Tn+(1-alpha) Tn
• Tn+1= cpu brust of n+1 process
• Tn= cpu brust of nth process
• Alpha= 0<= alpha<=1
PRIORITY SCHEDULING
 PRIORITY SCHEDULING
• The SJF algorithm is a special case of the general priority scheduling algorithm
• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority (smallest integer = highest priority)
• Priority scheduling can be either preemptive or non-preemptive
• A preemptive approach will preempt the CPU if the priority of the newly-arrived process is
higher than the priority of the currently running process
• A non-preemptive approach will simply put the new process (with the highest priority) at the
head of the ready queue
• SJF is a priority scheduling algorithm where priority is the predicted next CPU burst time
• The main problem with priority scheduling is starvation, that is, low priority processes may never
execute
• A solution is aging; as time progresses, the priority of a process in the ready queue is increased
Gantt chart n WT are
wrong
TWO WAYS OF PRIORITY

• Internal Priority: This priority depends on execution time, memory

requirement, and no of files
• External Priority: This priority depends on external parameters like
importance of the process.
ROUND ROBIN (RR) SCHEDULING
 ROUND ROBIN (RR) SCHEDULING

• In Round Robin concept, the algorithm uses time-sharing. The algorithm is

same as FCFS, but it is preemted. Each process gets CPU time called a
quantum time to limit the processing time, typically 1-100 milliseconds.
After time runs out, the process is delayed and added to the ready queue. If
a process has a CPU burst smaller than the time quantum, then the process
will release the CPU if it has finished its work so that the CPU can be
immediately used by the next process.

• Conversely, if a process has a CPU burst greater than the time quantum,
the process will be suspended if it reaches a quantum of time, and then
queuing back to the position of the tail of the ready queue and then
execute the next process.
• If there are n processes in the ready queue and the time quantum q, then
each process gets 1/n of the CPU time at most q time units at once CPU
scheduling. No process waits for more than (n-1) q time units.
EXAMPLE OF RR WITH TIME QUANTUM = 20

Proces Brust
s Time
P1 53
P2 17
P3 68
P4 24
 EXAMPLE OF RR WITH TIME QUANTUM = 20

Process Burst Time

P1 53 33 13

P2 17 _

P3 68 48 28 8

P4 24 4 _
• The Gantt chart is:

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162

• Typically, higher average turnaround than SJF, but better response time
• Average waiting time
= ( [(0 – 0) + (77 - 20) + (121 – 97)] + (20 – 0) + [(37 – 0) + (97 - 57) + (134 – 117)] + [(57 – 0) + (117
– 77)] ) / 4
•
= (0 + 57 + 24) + 20 + (37 + 40 + 17) + (57 + 40) ) / 4
•
= (81 + 20 + 94 + 97)/4
•
= 292 / 4 = 73
• There are six processes named as P1, P2, P3, P4, P5 and P6. Their arrival time
and burst time are given below in the table. The time quantum of the system
is 4 units. Find out the average waiting time using RR scheduling algorithm
• Advantages of Round-robin Scheduling

• It doesn’t face the issues of starvation or convoy effect.

• All the jobs get a fair allocation of CPU.

• If you know the total number of processes on the run queue, then you can also assume the worst-
case response time for the same process.

• This scheduling method does not depend upon burst time. That’s why it is easily implementable
on the system.

• It gives the best performance in terms of average response time.

• Disadvantages of Round-robin Scheduling

• If slicing time of OS is low, the processor output will be reduced.

• This method spends more time on context switching

• Its performance heavily depends on time quantum.

• Round-robin scheduling doesn’t give special priority to more important tasks.

MULTI-LEVEL QUEUE SCHEDULING
 MULTI-LEVEL QUEUE SCHEDULING
 Multiple-level queues are not an independent scheduling algorithm. They make use of
other existing algorithms to group and schedule jobs with common characteristics. Multi-
level queue scheduling is used when processes can be classified.
 Multiple queues are maintained for processes with common characteristics.
 Each queue can have its own scheduling algorithms.
 Priorities are assigned to each queue.
 For example, foreground (interactive) processes and background (batch) processes
• The two types of processes have different response-time requirements and so may
have different scheduling needs
• Also, foreground processes may have priority (externally defined) over background
processes
• A multi-level queue scheduling algorithm partitions the ready queue into several separate
queues
• 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
• The foreground queue might be scheduled using an RR algorithm
• The background queue might be scheduled using an FCFS algorithm
• In addition, there needs to be scheduling among the queues, which is commonly
implemented as fixed-priority pre-emptive scheduling
• The foreground queue may have absolute priority over the background queue
MULTI-LEVEL QUEUE SCHEDULING
• One example of a multi-level queue are the five queues shown below
• Each queue has absolute priority over lower priority queues
• For example, no process in the batch queue can run unless the queues
above it are empty
• However, this can result in starvation for the processes in the lower
priority queues
 MULTILEVEL QUEUE SCHEDULING
• Another possibility is to time slice among the queues
• Each queue gets a certain portion of the CPU time, which it can
then schedule among its various processes
• The foreground queue can be given 80% of the CPU time for
RR scheduling
• The background queue can be given 20% of the CPU time
for FCFS scheduling
Example Problem
Let us consider the following four processes.

Let's assume that the priority order of the queues is as follows:

Queue1 > Queue2 > Queue3
The Gantt chart will look as follows:

In this example, the processes P1, P2, and P3 arrive at t=0, but still, P1 runs first as it
belongs to queue number 1, which has a higher priority. After the P1 process is over, the
P2 process in queue 2 runs before the process P3 which is present in queue 3 because
queue 2 has a higher priority than queue 3, and then P3 runs. While the P3 process is
running, the process P4 belonging to queue 1 arrives. Since queue 1 has higher priority
than queue 3, process P3 is stopped (paused), and P4 starts executing. After the
execution of P4 is completed, the execution of P3 is resumed.
MULTI-LEVEL FEEDBACK QUEUE SCHEDULING
 MULTILEVEL FEEDBACK QUEUE SCHEDULING
• In multi-level feedback queue scheduling, a process
In Multilevel
can moveFeedback Queue, Process
between can move
the various between
queues; the queues.
aging can be It uses many ready queue and
associate a different priority
implemented thiswith
wayeach queue. Multilevel Queue scheduling doesn’t allow us to do this.
So, this was the disadvantages of Multilevel Queue scheduling.
Consider Processes with different CPU burst characteristic. If a process uses too much of the CPU, it will be
moved to a lower priority queue. In same way, a process that waits too much in a lower priority queue may be
moved to a higher priority queue.
While implementing a Multilevel Feedback queue, there are various parameters that define the schedulers –
•The number of queues
•The scheduling algorithm for each queue
•The method used to demote processes to lower priority queues
•The method used to promote processes to higher priority queues
•The method used to determine which queue a process will enter
Let us take an example to understand:
Let’s consider there are three queues Q1, Q2 and Q3.
– Q1 Time quantum 9 milliseconds
– Q2 Time quantum 18 milliseconds
– Q3 FCFS
 MULTILEVEL FEEDBACK QUEUE SCHEDULING
Criteria of Multilevel Feedback Queue –
•The scheduler first executes all processes in Q1.
•Only when Q1 is empty will it executes processes in Q2.
•Similarly, processes in Q3 will be executed only if Q1 and Q2 are
empty.
•A process that arrives for Q2 will preempt a process in Q3.
•A process that arrives for Q3 will, in turn, preempt a process in
Q3.

MultiLevel FeedBack Queue Scheduling Example

Explanation
Any process entering the ready queue is put in Q1. Then, A
process in Q1 is given a time quantum of 9 milliseconds. If it does
not finish within time, it is moved to the tail of Q2.
If Q1 is empty, the process at the head of Q2 is given a quantum
of 18 milliseconds. or, If it does not complete, it is preempted and
is put into Q3.
Processes in Q3 are run on an FCFS basis, only when Q1 and Q2
are empty.
 EXAMPLE OF MULTILEVEL FEEDBACK
• Scheduling
QUEUE
• A new job enters queue Q0 (RR) and is placed at the end. When it gains the CPU, the job
receives 8 milliseconds. If it does not finish in 8 milliseconds, the job is moved to the end of
queue Q1.

• A Q1 (RR) job receives 16 milliseconds. If it still does not complete, it is preempted and moved
to queue Q2 (FCFS).

Q0

Q1

Q2
DEADLOCKS
• In a multiprogramming environment, several processes may compete for a finite number of
resources. A process requests resources; if the resources are not available at that time, the
process enters a waiting state. Sometimes, a waiting process is never again able to change
state, because the resources it has requested are held by other waiting processes. This
situation is called a deadlock.

• This results from sharing resources such as memory, devices, files, links.

• Operating systems typically do not provide deadlock-prevention facilities, and it remains the
responsibility of programmers to ensure that they design deadlock-free programs.

93
DEADLOCKS Bridge Crossing
Example

• Traffic only in one direction.

• Each section of a bridge can be viewed as a resource.
• If a deadlock occurs, it can be resolved if one car backs up
(preempt resources and rollback).
• Several cars may have to be backed up if a deadlock occurs.
• Starvation is possible.
94
 Deadlock Principles
 A deadlock is a permanent blocking of a set of processes
 a deadlock can happen while threads/processes are competing for system resources or
communicating with each other
 SYSTEM MODEL
• A system consists of a finite number of resources (physical or logical) to be distributed among a number of competing processes. The resources are partitioned into
several types, each consisting of some number of identical instances. Memory space, CPU cycles, files, semaphores and I/0 devices (such as printers and DVD
drives) are examples of resource types. If a system has two CPUs, then the resource type CPU has as two instances. Similarly, the resource type printer may have
five instances.

• If a process requests an instance of a resource type, the allocation of any instance of the type will satisfy the request. If it will not, then the instances are not
identical, and the resource type classes have not been defined properly..

• Each process utilizes a resource as follows:

• request
• use
• Release
o The request and release of resources are system calls. Request and release of resources that are not managed by the operating
system can be accomplished through the wait() and signal() operations on semaphores or through acquisition and release of a
mutex lock. For each use of a kernel managed resource by a process or thread, the operating system checks to make sure that the
process has requested and has been allocated the resource
o To illustrate a deadlocked state, consider a system with one printer and one DVD drive. Suppose that process P; is holding the
DVD and process Pi is holding the printer. If P; requests the printer and P1 requests the DVD drive, a deadlock occurs. This
example illustrates a deadlock involving the different resource type.
o A programmer who is developing multithreaded applications must pay particular attention to this problem. Multithreaded
programs are good candidates for deadlock because multiple threads can compete for shared resources
NECESSARY CONDITIONS
ALL of these four must happen simultaneously for a deadlock to occur: DEADLOCKS
Mutual exclusion
At least one resource must be held in a non-sharable mode; that is, only one process at a time can
use the resource. If another process requests that resource, the requesting process must be delayed
until the resource has been released.

Hold and Wait

A process holds a resource while waiting to acquire another resource held by other processes.

No Preemption
There is only voluntary release of a resource - nobody else can make a process give up a resource.

Circular Wait
A set { P0 , Pl, ... , P11 } of waiting processes must exist such that P0 is waiting for a resource held
by P1, P1 is waiting for a resource held by P2, ... , Pn-1 is waiting for a resource held by Pn and Pn is
waiting for a resource held by P0.
METHODS FOR HANDLING DEADLOCKS
 Prevention
 Ensure that the system will never enter a deadlock state. Prevent any one of the 4 conditions
from happening

 Avoidance
 Ensure that the system will never enter an unsafe state. Allow all deadlock conditions, but
calculate cycles about to happen and stop dangerous operations.
 Detection
 Allow the system to enter a deadlock state and then recover

 Do Nothing
 Ignore the problem and let the user or system administrator respond to the problem; used by
most operating systems, including Windows and UNIX
To ensure that deadlocks never occur, the system can either use a deadlock-prevention or a
deadlock-avoidance scheme
DEADLOCKS Deadlock Prevention
99
Do not allow one of the four conditions
to occur.

Mutual exclusion:

Must holds for printers and other non-

sharable resources.

Shared entities (read only files) don't

need mutual exclusion (and aren’t
susceptible to deadlock.).

A process never needs to wait

for a sharable resource.
In general, however, we cannot prevent
deadlocks by denying the mutual-
exclusion condition, because some
resources are intrinsically non-
sharable.
 DEADLOCKS Deadlock Prevention
No preemption:
If a process that is holding
some resources requests
another resource that cannot
be immediately allocated to
it, then all resources currently
being held by the process are
released
• Preempted resources are
added to the list of
resources for which the
process is waiting
• A process will be restarted
only when it can regain its
old resources, as well as
the new ones that it is
requesting .
Hold and101
wait:
We must guarantee that whenever a process requests a resource,
it does not hold any other resources

One protocol that can be used requires each process to request

and be allocated all its resources before it begins execution. We
can implement this provision by requiring that system calls
requesting resources for a process precede all other system calls.

An alternative protocol allows a process to request resources only

when it has none. A process may request some resources and
use them. Before it can request any additional resources,
however, it must release all the resources that it is currently
allocated.
Require a process to request and be allocated all its resources
before it begins execution, or allow a process to request
resources only when the process has none
Result: Low resource utilization; starvation possible
 102

CIRCULAR WAIT

TO MAKE SURE THAT THIS

CONDITION NEVER HOLDS,
IMPOSE A TOTAL ORDERING OF
ALL RESOURCE TYPES, AND
REQUIRE THAT EACH PROCESS
REQUESTS RESOURCES IN AN
INCREASING ORDER OF
ENUMERATION.

For Example, if the P1 process is allocated R5 resources, now next time if P1

asks for R4, R3 lesser than R5 such a request will not be granted, only a
request for resources more than R5 will be granted.