Chapter-02 Process Management

Chapter- Two
PROCESS MANAGEMENT

2.1 PROCESSES

2.1.1 Process Concept

 A process is a program in execution. The execution of a process must progress in

a sequential fashion.
 A process is more than the program code. It also includes the current activity, as
represented by the value of the program counter and the contents of the
processor’s registers.
 As a process executes, it changes state.

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.

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
 Ready: The process is waiting to be assigned to a processor
 Running: Instructions are being executed.
 Waiting: The process is waiting for some event to occur( such as an I/O
completion or reception of a signal )
 Terminated: The process has finished execution.
 Chapter-02 Process Management

New Terminated
Admitted Interrupt Exit

Ready Running

Scheduler dispatch

I/O or event completion I/O or event wait

Waiting

Figure 1: Diagram of process state.

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 1.
Process Control Block: Each process is represented in the operating system by a
process control block (PCB) also called a task control block. A PCB is shown in Figure 2. It
contains many pieces of information associated with a specific process, including these:
 Process state: The state may be new, ready, running, and 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.
 CPU scheduling information: this information includes a process priority
pointer 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.
 Chapter-02 Process Management
 I/O status information: The information includes the list of I/O devices
allocated to this process, a list of open files and so on
.

Figure 2: Process Control Block.

2.1.2 PROCESS SCHEDULING

 The objective of multiprogramming is to have some process running at all

times, to maximize CPU utilization.
 The objective of time sharing is to switch the CPU among processes so
frequently that users can interact with each program while it is running.
 In both the cases we expect more than one process in the system but for a
uniprocessor system, there will never be more than one running process
the rest will have to wait until the CPU is free and can be rescheduled.

Scheduling Queues:

 As processes enter the system, they are put into a job queue. This queue consists
of all processes in the system.
 The processes that are residing in main memory and are ready and waiting to
execute are kept on a list called the ready queue. This queue is generally stored
as a linked list. A ready queue header will contain pointer to the first and last
PCBs in the list. Each PCB has a pointer field that points to the next process in the
ready queue.
 When a process is allocated the CPU, it executes for a while and eventually quits,
is interrupted, or waits for the occurrence of a particular event, such as the
 Chapter-02 Process Management
completion of an I/O request; such a request may be to a dedicated tape drive, or
to a shared device, such as a disk. The list of processes waiting for a particular
I/O device is called a device queue. Each device has its own device queue.
 A common representation for a discussion of process scheduling is a queuing
diagram.
 Each rectangular box represents a queue. Two types of queues are present: the
ready queue and a set of a device queues.
 The circles represent the resources that serve the queues and the arrows
indicate the flow of processes in the system.
 A new process is initially put in the ready queue. It waits in the ready queue until
it is selected for execution and is given the CPU. once the process is allocated the
CPU and is executing , one of several events could occur:
 The process could issue an I/O request, and then be placed in an I/O
queue.
 The process could create a new sub process and wait for its termination.
 The process could be removed forcibly from the CPU, as a result of an
interrupt and then put back in the ready queue.
 In the first two cases, the process eventually switches from the waiting state to
the ready state, and is then put back in the ready queue.

Ready queue CPU

I/O I/O queue I/O request

Time slice
expired

Child Child
Fork a child
terminates executes

Interrupt Wait for an

interrupt
occurs

Queuing diagram representation of process scheduling.

 Chapter-02 Process Management
 A process continues this cycle until it terminates, at which time it is removed
from all queues and has its PCB and resources deaallocated.
Schedulers: A process migrates between the various scheduling queues throughout its
lifetime. The operating system must select process from the queues in some fashion.
The selection process is carried out by the appropriate scheduler. There are three types
of schedulers.
 Long-term scheduler
 Short-term scheduler
 Mid-term scheduler
Long-term scheduler: In a batch system, there are often more processes submitted
than can be executed immediately. These processes are spooled to a mass-storage
device (disk), where they are kept for later execution. The long-term scheduler select
processes form this pool and load them into memory for execution.
Short-term scheduler: The short-term scheduler (or CPU scheduler) selects among the
processes that are ready to execute, and allocates the CPU to one of them.
 The primary distinction between these two schedulers is the frequency of their
execution.
 The long-term scheduler, on the other hand, executes much less frequently.
 The long-term scheduler controls the degree of multiprogramming (number of
processes in memory).
 The long-term scheduler makes a careful selection. In general most processes
can be described as either I/O bound or CPU bound.
 An I/O-bound process is one that spends more of its time doing I/O than it
spends doing computations.
 A CPU-bound process is one that generates I/O requests very infrequently, using
more of its time doing computation than an I/O-bound process uses.
 It is important that the long-term scheduler select a good process mix of I/O-
bound and CPU-bound processes.
 If all processes are I/O-bound processes, the ready queue will almost always be
empty, and the short-term scheduler will have little to do.
 If all processes are CPU-bound processes, the waiting queue will almost always
be empty, devices will go unused, and again the system will be unbalanced.
 The short term scheduler must select a new process for the CPU quite
frequently. A process may execute for only a few milliseconds before waiting for
an I/O request. Often, the short-term scheduler executes at least once every 100
milliseconds.
 Because of the short duration of time between executions, the short-term
scheduler must be very fast.
Mid-term scheduler: The mid-term scheduler is diagrammed below. The key idea in
this scheduling is that somet imes it can be advantageous to remove processes from
 Chapter-02 Process Management
Memory (and from active contention for the CPU), and thus to reduce the degree of
programming. At some later time, the process can be reintroduced into memory and its
execution can be continued where it left off. This scheme is called swapping. The
process is swapped out and swapped in later by the medium-term scheduler.

 Swapping may be necessary to improve the process mix, or because a change in

memory requirements has overcommitted available memory, requiring memory
to be freed up.

Swap in swap
Partially executed swapped out processes out

Ready queue C P U
e n
d

I/O waiting queues

I/O

Long-term scheduling: The decision to add to the pool of processes to be executed.

Medium-term scheduling: The decision to add to the number of processes that are
partially or fully in main memory
Short-term scheduling: The decision as to which available process will be executed by
the processor.

New
LTS
STS
Ready Running

MTS
Waiting
 Chapter-02 Process Management
Context switch
Switching the CPU to another process requires saving the state of the old process and
loading the saved state for the new process. This task is known as a context switch.
 Context-switch time is pure overhead, because the system does no useful work
while switching.
 Context-switch times are highly dependent on hardware support.
 A context-switch simply includes changing the pointer to the current register set.
Of course, if there are more active processes than there are register sets, the
system resorts to copying register data to and from memory, as before.

2.2.3 OPERATION ON PROCESSES

The processes in the system can execute concurrently, and must be created and
deleted dynamically. Thus, the operating system must provide a mechanism for
Process creation and termination.
Process Creation:
 A process may create several new processes during the course of execution.
 The creating process is called a parent process whereas the new processes are
called the children of that process. Each of these processes may in turn create
other process, forming a tree of processes.
 When a process creates a new process, two possibilities exist in terms of
execution:
 The parent process continues to execute concurrently with its children.
 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:
 The child process is a duplicate of the parent process.
 The child process has a program loaded into it.
Process Termination:
 A process terminates when it finishes executing its last statement and asks the
operating system to delete it by using the exit system call. At that point, the
process may return data (output) to its parent process (via the wait system call).
 All of the resources of the process, including physical and virtual memory, open
files, and I/O buffers, are de allocated by the operating system.
 A parent may terminate the execution of one of its children for a variety of
reasons, such as:
 The child has exceeded it usage of some of the resources it has been
allocated.
 The task assigned to the child is no longer required.
 The parent is exiting, and the operating system does not allow a child to
continue if its parent terminates.
 Chapter-02 Process Management
In UNIX, a process may terminate by using the exit system call, and its parent process
may wait for that event by using the wait system call.

2.2.4 CO-OPERATING PROCESSES

The concurrent processes executing in the operating system may be either independent
or cooperating processes.
Independent processes: A process is independent if it cannot affect or be affected by
the processes executing in the system. i.e., any process that does not share any data
with any other process is independent.
Cooperating processes: A processes is cooperating if it can affect or be affected by the
other processes executing in the system. i.e., any process that shares data with other
processes is a cooperating process.
There are several reasons for providing an environment that allows process
cooperation:
 Information sharing
 Computation speedup
 Modularity
 Convenience
2.3 THREADS

A thread is a base unit of CPU utilization, consists of a program counter, register set, and
a stack space. It shares with peer threads its code section, data section, and operating
system. A thread is also called a light weight process (LWP).

A traditional or heavy weight process is equal to a task with one thread.

A process (task) does nothing if no threads are in it, and a thread must be in exactly one
task.

2.4 INTER PROCESS COMMUNICATION (IPC)

Inter process communication (IPC) provides a mechanism to allow processes to

communicate and to synchronize their actions. Interposes communication is best
provided by a message system.
 An IPC facility provides at least the two operations: send (message) and receive
(message).
 If processes P and Q want to communicate,, they must send messages to and
receive messages from each other; a communication link must exist between
them.
 Chapter-02 Process Management
 There are several methods for logically implementing a link and send/receive
operations.

2.5 CPU SCHEDULING

2.5.1 BASIC CONCEPTS

Scheduling 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.

CPU-I/O Burst Cycle:

The success of CPU scheduling depends on the following observed property of

processes: Process execution consists of a cycle of CPU execution and I/O wait.
Processes alternate back and forth between these two states. Process execution begins
with a CPU burst. That is followed by an I/O burst, which is followed by another CPU
burst, then another I/O burst, and so on. Eventually, the last CPU burst will end with a
system request to terminate execution, rather than with another I/O burst.

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 processes is carried out by the short-
term scheduler (CPU scheduler).

CPU scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state.
(For example, I/O request, or invocation of wait for the termination of one of the
child processes)
2. when a process switched from the running state to the ready state (for example,
when an interrupt occurs)
3. When a process switches from the waiting state to the ready state.(for example
completion of I/O )
4. When a process terminates.

In case of 1 and 4 there is no choice in terms of scheduling, but there is a choice for 2
and 3.
 Chapter-02 Process Management
When scheduling takes place only under circumstances 1 and 4, we say the scheduling
scheme is non preemptive; otherwise, the scheduling scheme is preemptive.

Under non preemptive scheduling, once the CPU has been allocated to a process, the
process keeps CPU until it releases the CPU either by terminating or by switching to the
waiting state.

Dispatcher:

 Dispatcher is the module that gives control of the CPU to the process selected by
the short-term scheduler.
 This function involves:
 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, given that it is invoked during every
process switch.
 The time it takes for the dispatcher stop one process and start another running
is known as the dispatch latency

2.5.2 SCHEDULING CRITERIA

Different CPU scheduling algorithms have different properties and 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. Different criteria have been
suggested, given below, for comparing CPU scheduling algorithms.

 CPU utilization. We want to keep the CPU as busy as possible.

 Throughput. Number of processes that are completed per time unit is called
throughput. For long processes, this rate may be one process per hour; for short
transactions, throughput might be 10 processes per second.
 Turnaround time. 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/O.
 Chapter-02 Process Management
 Waiting time. Waiting time is the sum of the periods spent waiting in the ready
queue.
 Arrival Time: Time at which the process arrives in the ready queue.
 Completion Time: Time at which process completes its execution.
 Burst Time: Time required by a process for CPU execution.
 Turn Around Time: Time Difference between completion time and arrival time.
 Turn Around Time = Completion Time – Arrival Time
 Waiting Time (W.T): Time Difference between turnaround time and burst time
 Waiting Time = Turn Around Time – Burst Time
 Response Time: Time at which the process received its first response.

It is desirable to maximize CPU utilization and throughput, and to minimize turnaround

time, waiting time and response time.

2.5.3 SCHEDULING ALGORITHMS

1. First-Come, First-Served Scheduling (FCFS)

 This is the simplest scheduling algorithm. In this scheme, the process that
requests the CPU first is allocated the CPU first.
 This FCFS algorithm is implemented using 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 code for the FCFS scheduling is simple to write and understand.
 The average waiting time under the FCFS policy is often quite long.
 FCFS is a non-preemptive. Once the CPU has been allocated to a process, that
process keeps the CPU until it releases the CPU, either by terminating or by
requesting I/O.
 FCFS algorithm is particularly troublesome for time-sharing systems, where it is
important that each user get a share of the CPU at regular intervals.

Example1:
1. Consider the following set of processes that arrive at time 0, with the length of the
CPU-burst time given in milliseconds.

Process : P1 P2 P3

Burst time : 24 3 3
 Chapter-02 Process Management
If the process arrive in the order P1, P2, P3 and are served in FCFS order then waiting
time, turnaround time, and Response times are given below.

Gantt chart is P1 P2 P3
0 24 27 30

Process Arrival Burst Response Waiting Turnaround

time Time time time time
P1 0 24 0 0 24
P2 0 3 24 24 27
P3 0 3 27 27 30
51

The average waiting time of a process = 51/3 = 17 milliseconds.

If the process arrive in the order P2, P3, P1 and are served in FCFS order then waiting
time, turnaround time, and Response times are given below.

Gantt chart is

P2 P3 P1
0 3 6 30

Process Arrival Burst Response Waiting Turnaround

time Time time time time
P2 0 3 0 0 3
P3 0 3 3 3 6
P1 0 24 6 6 30
9

The average waiting time of a process = 9/3 = 3 milliseconds.

 The average time under FCFS policy in general is not minimal, and may vary
substantially if the process CPU-burst times vary greatly.
 Chapter-02 Process Management

Example 2. For the following data perform the same as in previous problem.

Process : P1 P2 P3 P4 P5

Arrival time : 0 2 4 6 8

Burst time : 3 6 4 5 2

Gantt chart:
P1 P2 P3 P4 P5

0 3 9 13 18 20

Process Arrival Burst Response Waiting Turnaround

time Time time time time
P1 0 3 3 3 3
P2 2 6 1 1 7
P3 4 4 5 5 9
P4 6 5 7 7 12
P5 8 2 10 10 12
26

The average waiting time of a process = 26/5 = 5.2 milliseconds.

 Chapter-02 Process Management

2. Shortest-Job-First Scheduling (SJF)

 This algorithm associates with each process the length of the latter’s next CPU
burst. When the CPU is available, it is assigned to the process that has the
smallest next CPU burst. If two processes have the same length next CPU burst,
FCFS scheduling is used to break the tie.

Example1: consider the following set of processes, with the length of the CPU burst
time given in milliseconds.
Process : P1 P2 P3 P4

Arrival time : 0 0 0 0

Burst time : 6 8 7 3
 Chapter-02 Process Management
Find the average waiting time, response time and show the schedule using Gantt chart.

Gantt chart:
P4 P1 P3 P2

0 3 9 16 24

Process Arrival Burst Response Waiting Turnaround

time Time Time time time
P1 0 6 3 3 9
P2 0 8 16 16 24
P3 0 7 9 9 16
P4 0 3 0 0 3
28

The average waiting time of a process = 28/4 = 7 milliseconds.

 if we were using he FCFS scheduling scheme, then the average waiting
time would be 10.25 milliseconds.

Example2: consider the following set of processes, with the length of the CPU burst
time given in milliseconds.

Process : P1 P2 P3 P4

Arrival time : 0 1 2 3

Burst time : 8 4 9 5

Find the average waiting time and response times using Gantt charts.
 Chapter-02 Process Management
Gantt chart:

P1 P2 P4 P1 P3

0 1 5 10 17 26
Process Arrival Burst Response Waiting Turnaround
time Time time time time
P1 0 8 0 9
P2 1 4 0 0
P3 2 9 15 15
P4 3 5 2 2
26

Average waiting time of a process = 26/4 = 6.5 milliseconds.

 In this example, P1 is preempted because the next arrived process

P2 has 4 milliseconds of burst time, which is less than the
remaining time for process P1.
 A non-preemptive SJF scheduling would result in an average time
of 7.75 milliseconds.

 The SJF scheduling algorithm is provably Optimal, in that it gives the minimum
average waiting time for a given set of processes.
 Although the SJF algorithm is optimal, it cannot be implemented at the level of
shortest-term CPU scheduling. There is no way to know the length of the next
CPU burst.
 One approach is to try to approximate SJF scheduling. We may not know the
length of the next CPU burst; we may able to predict its value. Thus, by
computing an approximation of the length of the next CPU burst, we can pick the
process with the shortest predicted CPU burst.
 The SJF algorithm is either preemptive or non-preemptive. Preemptive SJF
Scheduling is called shortest-remaining-time-first scheduling.

3. Priority Scheduling

 In 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.
 Priorities are generally some fixed range of numbers, such as 0to7, or 0 to 1023.
However there is no general agreement on whether 0 is the highest or lowest
 Chapter-02 Process Management
priority. Some systems use low numbers to represent low priority; others use
low numbers for high priority.
 In this algorithm we assume that low numbers represent high priority.

Example1: consider the following set of processes, assumed to have arrived at time 0, in
the order P1, P2, P3, P4, P5, with the length of the CPU-burst time given in milliseconds. Find
the average waiting time and turnaround time using Gantt charts.

Process : P1 P2 P3 P4 P5

Burst time : 10 1 2 1 5

Priority : 3 1 3 4 2

Sol:
Gantt chart: P2 P5 P1 P3 P4

0 1 6 16 18 19

Process Arrival Burst Priority Response Waiting Turnaround

time Time time time time
P1 0 10 3 6 6 16
P2 0 1 1 0 0 1
P3 0 2 3 16 16 18
P4 0 1 4 18 18 19
P5 0 5 2 1 1 6
41

Average waiting time = 41/5 = 8.2 milliseconds.

Example2: consider the following set of processes, in the order P1, P2, P3, P4, with the
length of the CPU-burst time given in milliseconds and Priorities. Find the average
waiting time and turn around time using Gantt charts.
 Chapter-02 Process Management

Process : P1 P2 P3 P4

Arrival time : 0 2 4 6

Burst time : 8 4 9 5

Priority : 3 1 4 2

Gantt chart:

P1 P2 P4 P1 P3

0 2 6 11 17 26

Process Arrival Burst Priority Response Waiting Turnaround

time Time time time time
P1 0 8 3 0 9 17
P2 2 4 1 0 0 4
P3 4 9 4 13 13 22
P4 6 5 2 0 0 5
22

Average waiting time of a process is = 22/4 = 5.5 milliseconds.

 Priorities can be defined either internally or externally.

 Priorities scheduling can be either preemptive or nonpreemptive;
 A major problem with priority scheduling is indefinite blocking or starvation. A
process that is ready to run but lacking the CPU can be considered blocked,
waiting for the CPU. In a heavily loaded computer system, a steady stream of
high-priority processes can prevent a low-priority process from ever getting
CPU.
 A solution to the indefinite blockage of low-priority processes is aging.
 Aging is a technique or gradually increasing the priority of processes that wait in
the system for a long time.
18 | P a g e
 Chapter-02 Process Management

4. Round-Robin Scheduling

The round-robin (RR) scheduling algorithm is designed especially for time- sharing
systems.
 A small unit of time, called a time quantum, or time slice, is defined. 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 the RR scheduling, we keep the ready queue as FIFO queue of
processes. New processes are added to the tail of the ready queue. The CPU
scheduler picks the first processes from the ready queue, sets a timer to
interrupt after 1 time quantum, and dispatches the process.
 The average waiting time under the RR policy, however, is often quite long.

Example 1: consider the following set of processes, assumed to have arrived at time 0,
in the order P1, P2, P3, P4, P5, with the length of the CPU-burst time given in
milliseconds. Find the average waiting time and turnaround time using Gantt charts for
RR scheduling. (Time quantum is 3 milliseconds).

Process : P1 P2 P3 P4 P5

Burst time : 10 1 2 1 5

Gantt chart:

P1 P2 P3 P4 P5 P1 P5 P1 P1

0 3 4 6 7 10 13 15 18 19

Process Arrival Burst Response Waiting Turnaround

time Time Time time Time
P1 0 10 0 9 19
P2 0 1 3 3 4
P3 0 2 4 4 6
P4 0 1 6 6 7
P5 0 5 10 10 15
32

19 | P a g e
 Chapter-02 Process Management
Average waiting time of a process is = 32/5 = 6.2 milliseconds.

 RR scheduling is a preemptive scheduling.

 The performance of RR scheduling is heavily depends on time quantum.
 If time quantum is very large then RR policy is the same as FCFS.
2.5.4 ALGORITHM EVALUATION
 How do we select for a CPU scheduling for a particular system?
 To select an algorithm, we must first define the relative importance of different measures
as mentioned below.
 Maximize CPCU utilization under the constraint that the maximum response time is 1
second.
 Maximize throughput such that turnaround time is linearly proportional to total
execution time.

One the selection criteria have been defined, we want to evaluate the various algorithms under
consideration.
 Deterministic modeling
 Queueing models.
 Simulations.
 Implementations.

20 | P a g e