Unit-II

Process Management

by

1 Prof. (Mrs.)S.A. Nagtilak

SKNCOE,Pune
2 Syllabus:-
 Process: Concept of a Process, Process States, Process
Description, Process Control
 Threads: Processes and Threads, Concept of Multithreading,
Types of Threads, Thread programming Using Pthreads.
 Scheduling: Types of Scheduling, Scheduling Algorithms, First
Come First Served, Shortest Job First, Priority, Round Robin
3
Requirements of an OS

 Interleave the execution of multiple processes to

maximize processor utilization while providing
reasonable response time

 Allocate resources to processes

 Support interprocess communication and user

creation of processes
4
How OS Manage Execution
of Applications
 Resources are made available to multiple applications

 The physical Processor is switched among multiple

application so all will appear to be progressing

 The processor and I/O devices can be used efficiently

5
Process
 A program in execution

 An instance of a program running on a computer

 The entity that can be assigned to and executed on a

processor

 A unit of activity characterized by the execution of a

sequence of instructions, a current state, and an
associated set of system instructions
6
Process Control Block

 Contains the process elements

 Created and managed by the operating system

 Allows support for multiple processes

 76 Process Elements

 While the program is executing, this process can be uniquely

characterized by a number of elements, including:

identifier

state priority program counter

I/O status accounting

memory pointers context data
information information
7 Identifier

Process Control Block State

Priority
Contains the process elements
Program counter
It is possible to interrupt a running
Memory pointers
process and later resume execution as if
the interruption had not occurred Context data

Created and managed by the I/O status

operating system information

Key tool that allows support for multiple Accounting

processes information

Figure 3.1 Simplified Process Control Block

 Process States
8

Trace Dispatcher
the behavior of an
individual process
by listing the
sequence of small program
instructions that that switches the
execute for that processor from
process one process to
another

the behavior of the processor

can be characterized by
showing how the traces of
the various processes are
interleaved
10
9
Address Main Memory Program Counter
0
8000
100
Dispatcher

Process 5000
Process A
Execution
8000

Process B

12000

Process C

Figure 3.2 Snapshot of Example Execution (Figure 3.4)

at Instruction Cycle 13
11
10 5000 8000 12000
5001 8001 12001
5002 8002 12002
5003 8003 12003
5004 12004
5005 12005
5006 12006
5007 12007
5008 12008
5009 12009
5010 12010
5011 12011
(a) Trace of Process A (b) Trace of Process B (c) Trace of Process C

5000 = Starting address of program of Process A

8000 = Starting address of program of Process B
12000 = Starting address of program of Process C

Figure 3.3 Traces of Processes of Figure 3.2

12
12 Two-State Process Model

Dispatch

Enter Not Exit

Running Running

Pause

(a) State transition diagram

Queue
14
Not-Running Process in a
Queue
14

Table 3.1 Reasons for Process Creation

15 Process Creation

Process Parent Child

spawning process process
• when the • is the • is the new
OS creates original, process
a process creating,
at the process
explicit
request of
another
process
16 Process Termination

 There must be a means for a process to indicate its

completion
 A batch job should include a HALT instruction or an
explicit OS service call for termination
 For an interactive application, the action of the user will
indicate when the process is completed (e.g. log off,
quitting an application)
 Process Termination
18
 Process Termination
19
20
A Five-State Model
 Running
 Ready
 Blocked/waiting
 New
 Exit
21
Five-State Process Model
22
Process States
23
Using Two Queues
24
Multiple Blocked Queues
25
Suspended Processes

 Processor is faster than I/O so all processes

could be waiting for I/O
 Swap these processes to disk to free up more
memory
 Blocked state becomes suspend state when
swapped to disk
 Two new states
 Blocked/Suspend
 Ready/Suspend
26
One Suspend State
27
Two Suspend States
28 Characteristics of a Suspended
Process
 The process is not  The process may or may
immediately available not be waiting on an
for execution event

 The process was placed  The process may not be

in a suspended state by removed from this state
an agent: either itself, a until the agent explicitly
parent process, or the orders the removal
OS, for the purpose of
preventing its execution
29 Reasons for Process Suspension
30
Processes and Resources
31
Operating System Control
Structures
 Information about the current status of each process
and resource
 The OS constructs and maintains tables of information
about each entity that it is managing.
- Memory tables
- I/O tables
- File tables
- Process tables
31
Memory Tables

 Used to keep track

of both main (real)
and secondary
(virtual) memory
 Processes are
maintained on
secondary memory
using some sort of
virtual memory or
simple swapping
mechanism
32
I/O Tables

 Used by the OS to
manage the I/O
devices and
channels of the
computer system
 At any given time,
an I/O device may
be available or
assigned to a
particular process
33 File Tables

These tables provide information about:

•existence of files
•location on secondary memory
•current status
•other attributes

 Information may be maintained and used by a file

management system
 in which case the OS has little or no knowledge of files

 In some operating systems, much of the detail of file management is managed

by the OS itself
34
Process Tables

 Must be maintained to manage processes

 There must be some reference to memory, I/O, and files,
directly or indirectly
 The tables themselves must be accessible by the OS and
therefore are subject to memory management
35
Process Control Structures

To • where the
manage process is
and located
control a • the attributes of
the process that
process are necessary for
the OS its management
must know:
36
Process Control Structures
Process Location Process Attributes
 A process must include a  Each process has associated
program or set of programs to with it a number of attributes
be executed that are used by the OS for
process control
 A process will consist of at
least sufficient memory to hold  The collection of program,
the programs and data of that data, stack, and attributes is
process referred to as the process
image
 The execution of a program
typically involves a stack that  Process image location will
is used to keep track of depend on the memory
procedure calls and management scheme being
parameter passing between used
procedures
 37 Table 3.4
Typical Elements of a Process Image

User Data
The modifiable part of the user space. May include program data, a user stack area, and
programs that may be modified.

User Program
The program to be executed.

Stack
Each process has one or more last-in-first-out (LIFO) stacks associated with it. A stack is
used to store parameters and calling addresses for procedure and system calls.

Process Control Block

Data needed by the OS to control the process (see Table 3.5).
39
40
UNIX Process States
41
42

Two processes are unique in UNIX

- Process 0 is a special process i.e. created
when system boots. It is the swapper process

- Process 0 spawns process 1, referred to as init

process
43
Change of Process State

 Save context of processor including program

counter and other registers
 Update the process control block of the process
that is currently in the Running state
 Move process control block to appropriate queue –
ready; blocked; ready/suspend
 Select another process for execution
43 Process Control Information

 The additional information

needed by the OS to control
and coordinate the various
active processes
 Process Process Process
Identification Identification Identification
Process
Processor State Processor State Processor State Control
Information Information Information Block
Process Control Process Control Process Control
Information Information Information

User Stack User Stack User Stack

Private User Private User Private User

Address Space Address Space Address Space
(Programs, Data) (Programs, Data) (Programs, Data)

Shared Address Shared Address Shared Address

Space Space Space

Process 1 Process 2 Process n

Figure 3.13 User Processes in Virtual Memory

 Process
46 Control Block
Running

Ready

Blocked

Figure 3.14 Process List Structures

47
Role of the Process Control Block
 The most important data structure in an OS
 contains all of the information about a process that is
needed by the OS
blocks are read and/or modified by virtually every module
in the OS
defines the state of the OS
 Difficulty is not access, but protection
a bug in a single routine could damage process control
blocks, which could destroy the system’s ability to manage
the affected processes
a design change in the structure or semantics of the
process control block could affect a number of modules in
the OS
48
Modes of Execution

User Mode System Mode

less-privileged  more-privileged
mode mode
user programs  also referred to as
typically execute control mode or
kernel mode
in this mode
 kernel of the
operating system
 49
Process Management

•Process creation and termination

Table 3.7 •Process scheduling and dispatching
•Process switching
•Process synchronization and support for interprocess communication
Typical •Management of process control blocks
Functions Memory Management
of an •Allocation of address space to processes
•Swapping
Operating •Page and segment management
System I/O Management
Kernel •Buffer management
•Allocation of I/O channels and devices to processes

Support Functions

•Interrupt handling
•Accounting
•Monitoring
50 Process Creation
Once the OS decides to create a new
process it:
assigns a unique process
identifier to the new process

allocates space for the process

initializes the process control

block

sets the appropriate linkages

creates or expands other data

structures
51

Table 3.8

Mechanisms for Interrupting the Execution of a Process

Mechanism Cause Use

Interrupt External to the execution of the Reaction to an asynchronous

current instruction external event

Trap Associated with the execution of Handling of an error or an

the current instruction exception condition

Supervisor call Explicit request Call to an operating system

function
52
System Interrupts

Interrupt Trap
 Due to some sort of  An error or exception
event that is external to condition generated
and independent of the within the currently
currently running process running process
 clock interrupt  OS determines if the
 I/O interrupt condition is fatal
 memory fault  moved to the Exit state
 Time slice and a process switch
 the maximum amount
occurs
of time that a process  action will depend on
can execute before the nature of the error
being interrupted
52
Mode Switching

If no interrupts are If an interrupt is

pending the processor: pending the processor:

proceeds to the fetch stage and fetches

sets the program counter to the starting
the next instruction of the current
address of an interrupt handler program
program in the current process

switches from user mode to kernel mode

so that the interrupt processing code
may include privileged instructions
 54

 The steps in update the move the

a full save the context
process control process control
process block of the block of this
of the processor process
switch are: currently in the
process to the
appropriate
Running state queue

If the currently running process is to be moved to

another state (Ready, Blocked, etc.), then the select another
OS must make substantial changes in its process for
execution
environment
restore the
context of the
processor to that
which existed at update the
the time the update memory process control
selected process management block of the
was last switched data structures process
out selected
55
Change of Process State

 Update the process control block of the process

selected
 Update memory-management data structures
 Restore context of the selected process
56
CPU Scheduling
 Basic Concepts
 Scheduling Criteria
 Scheduling Algorithms
 Multiple-Processor Scheduling
 Real-Time Scheduling
57
Basic Concepts

 The objective of multiprogramming is to have

maximum CPU utilization.

 CPU–I/O Burst Cycle – Process execution consists of a

cycle of CPU execution and I/O wait.
 Alternating Sequence of CPU and I/O Bursts
58
59
CPU Scheduler
 Selects one of the process from ready queue which is ready to
execute, and allocates the CPU to one of them.

 CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state.
2. Switches from running to ready state.
3. Switches from waiting to ready.
4. Terminates.

 Scheduling under 1 and 4 , there is no choice in terms of

scheduling i.e. nonpreemptive or cooperative.

 All other scheduling is preemptive.

60 Non preemptive:- Once the CPU has
been allocated to a process, it keeps
the CPU until process terminates or by
switching to the wait state.
Eg. MS Windows 3.x

Preemptive:- The process can be

preempted when a higher priority
process is ready for the execution.
Eg. Windows NT, Mac OS, Android,
Linux, ios
61
Dispatcher
 Dispatcher module gives control of the CPU to the
process selected by the short-term scheduler; this
involves:
 switching context
 switching to user mode
 jumping to the proper location in the user program
to restart that program
 Dispatch latency – The time it takes for the
dispatcher to stop one process and start another
running.
62
Types of Scheduling
63
64
 Difference among Long term, short term and medium term
9

Sr. Long term Short term Medium term

No.
1 It is job scheduler It’s CPU scheduler It is swapping

2 Speed is less than short term Speed is very fast Speed is in between both
scheduler
3 It controls the degree of Less control over the degree Reduce the degree of
multiprogramming of multiprogramming multiprogramming

4 Absent or minimal in the minimal in the time sharing Time sharing system
time sharing system system use medium term scheduler

5. It selects process from pool It selects from among Processes can be

and load them into memory processes that are ready to reintroduced into memory
for execution execute and it’s execution can be
continued
6 Process state is (New to Process state is (ready to Process state is (ready-
ready) running) suspend to ready)

7 Select good process, mix of Select new process for CPU

I/O bound and CPU bound quite frequently
 Scheduling Criteria
66

 CPU utilization – keep the CPU as busy as possible

 Throughput – No. of processes that complete their execution per

time unit

 Turnaround time – The interval from the time of submission of a

process to the time of completion.

 Waiting time – amount of time a process has been waiting in the

ready queue

 Response time –This is the time from submission of a request until

the response begins to be received (for time-sharing
environment)
67
Optimization Criteria
 Max CPU utilization
 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
First-Come, First-Served (FCFS) Scheduling
68

Process Burst Time

P1 24
P2 3
P3 3
 Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3

0 24 27 30

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

 Average waiting time: (0 + 24 + 27)/3 = 17
69
(Cont.)

Suppose that the processes arrive in the order

P2 , P3 , P1 .
 The Gantt chart for the schedule is:
P2 P3 P1

0 3 6 30

 Waiting time for P1 = 6; P2 = 0; P3 = 3

 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case.
 Convoy effect short process behind long process
70
FCFS Scheduling (Cont.)

 FCFS scheduling algorithm is nonpreemptive.

 It is particularly troublesome for time sharing systems,
where each user needs to get share of the CPU at
regular intervals.
 The average waiting time under the FCFS policy is
often quite long.
71
Shortest-Job-First (SJF)
Scheduling
 Associates with each process the length of its next
CPU burst. Use these lengths to schedule the process
with the shortest time.
 Two schemes:
 Nonpreemptive – once CPU given to the process it
cannot be preempted until completes its CPU burst.
 preemptive – if a new process arrives with CPU burst
length less than remaining time of current executing
process then preempt. This scheme is known as the
Shortest-Remaining-Time-First (SRTF).
 SJF is optimal – gives minimum average waiting time
for a given set of processes.
72
Example of Non-Preemptive
SJF
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 SJF (non-preemptive)

P1 P3 P2 P4

0 7 8 12 16
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
73
Example of Preemptive SJF

Process Arrival Time Burst Time

P1 0 7
P2 2 4
P3 4 1
P4 5 4
 SJF (preemptive)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16
 Average waiting time = (9 + 1 + 0 +2)/4 =3
74
Priority Scheduling
 A priority number (integer) is associated with
each process
 The CPU is allocated to the process with the
highest priority (smallest integer = highest
priority).
Preemptive
Non preemptive
 Problem = Starvation – low priority processes
may never execute.
 Solution = Aging – as time progresses increase
the priority of the process.
75
Context switch
 A context switch is the computing process of
storing and restoring the state (context) of a
CPU so that execution can be resumed from
the same point at a later time. This enables
multiple processes to share a single CPU.

 When an interrupt occurs, the system needs to

save the current context of the process
currently running on the CPU

 The context is represented in the PCB of the

process
Contd..
76

 A context switch can mean a register

context switch, a task context switch, a
thread context switch, or a process context
switch

 Switching from one process to another

requires a certain amount of time for doing
the administration .

 Context switch time is pure overhead,

because the system does no useful work
while switching
77
78
Round Robin (RR)
 Each process gets a small unit of CPU time (time
quantum), usually 10-100 milliseconds. After this
time has elapsed, the process is preempted and
added to the end 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.
 Performance depends on size of the time quantum
 q large  FCFS
 q small  q must be large with respect to
context switch, otherwise overhead is too high.
 Example of RR with Time Quantum = 20
79

Process Burst Time

P1 53
P2 17
P3 68
P4 24

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

 The Gantt chart is:

 Typically, higher average turnaround than SJF, but better
response.
 Time Quantum and Context Switch Time
80
81

 priority
 P1 2
 P2 1
 P3 3
 P4 2
 P5 5
82
Round Robin Example
Pro AT BT CT TAT WT
cess
P1 0 7 15 15 8
P2 1 1 2 1 0
P3 2 3 10 8 5
P4 3 4 13 10 6

 TQ =1 ms
 Ready Queue
 P1 P2 P1 P3 P4 P1 P3 P4 P1 P3 P4 P1 P4 P1 P1
P1 P2 P1 P3 P4 P1 P3 P4 P1 P3 P4 P1 P4 P1 P1
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
83
Windows 2000 Priorities
 Thread
84

 A thread is single sequence stream within a process. Because threads

have some properties of processes, they are sometimes called
lightweight processes

 A thread is basic unit of CPU utilization, it comprises a thread id, a

program counter, a register set

 Has an execution stack

85
Contd…

 per-thread static storage for local variables

 Access to the memory and resources of its process
 all threads of a process share the memory
 Multithreading
86

 Operating system supports multiple threads of execution within a

single process

 MS-DOS supports a single thread

 UNIX supports multiple user processes but only supports one thread
per process

 Windows, Solaris, Linux, Mach, and OS/2 support multiple threads

87
88
 In multithreaded environment, a process is defined as the unit
of resource allocation and a unit of protection.

 Have a virtual address space which holds the process image

 Protected access to processors, other processes, files, and I/O

resources
89
90
Benefits of Threads
 Takes less time to create a new thread than a
process
 Less time to terminate a thread than a process
 Less time to switch between two threads within
the same process
 Since threads within the same process share
memory and files, they can communicate with
each other without invoking the kernel
 Threads
91

 Suspending a process involves suspending all threads of the process

since all threads share the same address space

 Termination of a process, terminates all threads within the process

92
Thread States

 Like process, threads also have execution states

 Spawn
 Spawn another thread

 Block
 Unblock
 Finish
 Deallocate register context and stacks
94
Multithreading
95
User-Level Threads

All thread management is done by

the application and loaded
entirely in user space.
Each thread needs it’s own private
thread table and it is managed by
run time system.
The kernel is not aware of the
existence of threads
Examples
96
User-Level Threads
 Advantages of User level thread
97

 User level threads allows each process to have

it’s own scheduling algorithm.(Application
specific)

 The entire process loaded in user space, so the

process does not switch to the kernel mode to
do the thread management.

 User level threads can run on any OS.

 ULTs are fast to create and manage

98 Disadvantages of User level thread

 When user level thread executes a system

call, all of the threads within the process are
blocked.

 Multithreaded application can not use

multiprocessing since at actual, only one
process is assigned to the processor at one
time.

 Jacketing : to solve the problem of thread

blocking.
 Kernel-Level Threads
99

 Windows is an example of this approach

 The kernel maintains thread table that keeps track of the
process and all the threads in the system
 If existing thread wants to create or destroy the thread then it
makes the system call
 Scheduling is done on a thread basis
 Examples
- Windows 95/98/NT/2000
- Solaris
- Tru64 UNIX
- BeOS
- Linux
100
Kernel-Level Threads
 Advantages of Kernel level thread
101

 It supports multiprocessing, a thread in a process is blocked, the

kernel can schedule another thread of the same process
 Kernel level threads are especially good for applications that
frequently block.

Disadvantages of Kernel level thread

 More cost for creating and destroying threads in the kernel

 To manage and schedule threads kernel require a full TCB for
each thread to maintain information about threads. So overhead
and increased in kernel complexity.
 Transfer of control from one thread to another within the same
process requires a mode switch to the kernel
102
Benefits of multithreading

 Responsiveness
 Resource sharing
 Economy
 Scalability
103
Multithreading Models

 Many-to-One

 One-to-One

 Many-to-Many
 104
Many-to-One
 Many user-level threads mapped to single kernel thread
 Thread management is done by the thread library in user space
 Entire process will block if a thread makes a blocking system call
 Eg. Linux, Windows NT, Green threads – a thread library available for
Solaris
105
Many-to-One
 106
One-to-One
 Each user-level thread maps to kernel thread.
 It provides more concurrency than the many to one
model by allowing another thread to run when a
thread makes a blocking system call
 Drawback: Creating a user thread requires creating
the corresponding kernel thread and it is overhead to
the application
 Eg. - Windows 95/98/NT/2000/XP
- OS/2
107
One-to-one Model
108
Many-to-Many Model

Allows many user level threads to be

mapped to many kernel threads.

Allows the operating system to create a

sufficient number of kernel threads.
Eg. IRIX, HP-UX, Tru64 UNIX
109
Many-to-Many Model
110
Relationship Between
Threads and Processes
111
Windows Processes

 Implemented as objects
 An executable process may contain one or more
threads
 Both processes and thread objects have built-in
synchronization capabilities
112
113
Windows Process Object
114
Windows Thread Object
115
Windows 2000
Thread States
 Ready
 Standby
 Running
 Waiting
 Transition
 Terminated
116
117
Solaris

 Process includes the user’s address space, stack, and

process control block
 User-level threads
 Lightweight processes (LWP)
 Kernel threads
118
119
120 Solaris Lightweight Data Structure
Identifier
Priority
Signal mask
Saved values of user-level registers
Kernel stack
Resource usage and profiling data
Pointer to the corresponding kernel
thread
Pointer to the process structure
121
122
Linux Task Data Structure

State
Scheduling information
Identifiers
Interprocess communication
Links
Times and timers
File system
Address space
Processor-specific context
123
Linux States of a Process

 Running
 Interruptable
 Uninterruptable
 Stopped
 Zombie
124
• Running: This state value corresponds to two states. A Running
process is either executing or it is ready to execute.
125
• Interruptible: This is a blocked state, in which the process is waiting
for an event, such as the end of an I/O operation, the availability of
a resource, or a signal from another process.
• Uninterruptible: This is another blocked state. The difference
between this and the Interruptible state is that in an uninterruptible
state, a process is waiting directly on hardware conditions and
therefore will not handle any signals.
• Stopped: The process has been halted and can only resume by
positive action from another process. For example, a process that is
being debugged can be put into the Stopped state.
• Zombie: The process has been terminated but, for some reason,
still must have its task structure in the process table.