chapter

1
Introduction

An operating system (0S) is different things to different users. Each user's view is
called an abstract view because it emphasizes features that are important from the
viewer's perspective, ignoring all other features. An operating system implements
an abstract view by acting as an intermediary between the user and the computer
system. This arrangement not only permits an operating system to provide several
functionalities at the same time, but also to change and evolve with time. We discuss
how abstract views are also useful while designing an operating system, and during
itsoperation.
An operating system has twOgoalsefficient use of a computer system and user
convenience. Unfortunately, user convenience often conflicts with efficient use of a
computer system. Consequently, an operating system cannot provide both. It typi
cally strikes a balance between the two that is most effective in the environment in
which a computer system is used efficient use is important when a computer system
is shared by several users while user convenience is important in personal comput
ers. We use the term effective utilization for the balance between efficiency and user
convenience that best suits an environment. We discuss facets of efficient use and
user convenience in this chapter.
The primary concern of an OS is to support execution of user programs to ensure
user convenience and efficient use of resources. In this chapter, we describe the
functions performed by it to address these concerns.

1.1 ABSTRACT VIEWS OF AN OPERATING SYSTEM

A question like What is an OS?" is likely to evoke different answers. For example,
" For a young schoolor college student, an OS is the software that permits access
to the wealth of knowledge available on the Internet.
For aprogrammer, an OS is the software that permits the use of a computer
system for program development.
2 Operating Systen1s

" For a person using an application package, an OS is simply the software that
makes it possible for him to use the package.
For atechnician in a computerizedchemical plant, the OSis the invisible com
ponent of a computer system that controls the plant.

The answers differ because a user's perception about an OS depends on three factors:
the purpOse for which a conputer is being used, the computing environment, i.e., the
environment in which the computer system is used, and the degree of identity of the
computer system with the purpose being served.
For the student, the sole purpose of the computer system might be to use an
Internet browser. The OS helps in achieving this, so it is identified with use of the
computer system for Internet browsing. A programmer wishes to use a computer
system for general purpose program development, so theability touse a compiler for
a specifhc language is of paramount importance. For a person using an application
package, the OS is simply ameans to the use of the package. Such a user is oblivious
to other capabilities of an OS. Atechnician in a computerizedchemical plant simi
larly views the OS as everything in the control system of the plant. An OS
will doubtless have a different perception of what is an OS. designer
A common thread in all these perceptions is the
utilization of a
for a specific purpose or a set of purposes. The purposes in the computer system
above
different, so perceptions of the operating system's role are also different.examples are
From these examples it is clear that a user perceives an OS as
the software that
helps him in achieving an intended use of a conputer
of the computer system and its environment do not seemsystem-other capabilities
to matter. Thus, the OS
is simply a means of achieving an intended
purpose. A user
permits him to achieve hispurpose in the simplest and fastest will prefer an OS that
a user's perspective is always one of possiblemanner. Thus,
None of the four views of an OS convenience
and speed in computer utilization.
described at the start of this Section (and illus
trated in Figure 1.1)is complete, but each view is
a user to understand how to use an correct and useful because it helps
OS. Such views are called abstract
abstract view focuses on essential views. An
characteristics of an entity from the
of a viewer. Consequently, an
abstract view contains some elements ofperspective
reality but
ignores other elements.
1.1.1 Uses of Abstract Views

A user's abstract view contains

tive. It helps an OS designer toimportant features of a system from auser's perspec
in planning the features of an understand the requirements of a user, which helps
OS. Abstract views are useful for
other
marized in Table 1.1. The key advantage of using an abstract view inpurposes sum
it helps to control complexity of the design is that
design
narts of a system. Abstract views are also by separating the concerns of different
useful for understanding the design and
implementation of a system.
 Introduction 3

INTERNEP

STOCKINVEST

Fig. 1.1 Abstract views of an OS by a student,

programmer, user and technician

Table 1.1 Uses of abstract views

Use Description
Gathering system A user's abstract view indicates important services which a
requirements system should provide. Acollection of abstract views can be
used to compose a specification of system requirements.
Design of a Use of abstract views permits a designer to focus on a specific
system part of a system. Details of other parts are 'hidden'; these
parts can be assumed to be available. This approach helps to
controlcomplexity of the design process.
Implementation A part whose details were hidden in a design view becomes
of a system amodule, which can be called from other modules. This fact
leads to a modular implementation.

Figure 1.2 contains an abstract view of the structure of an OS, which shows three
main parts of an OS. Each part consists of a number of programs. The kernel is the
core of the OS. It controls operation of the computer and provides a set of functions
and services to use the CPU and resources of the computer. Non-kernel programs
implement user commands. These programs do not interact with the hardware, they
use facilities provided by kernel programs. Programs in the user interface part either
provide a command line interface or a graphical user interface (GUI) to the user.
These programs use facilities provided by non-kernel programs. A user interacts with
 4 Operating Systems

programs in the user interface-typically with the coMmand interpreter-torequest

use of resources and services provided by the system.

User interface

Non-kernel programs
Kernel

Computer hardware
Fig. 1.2 A designer's abstract view of an OS

The abstract view of Figure 1.2 has interesting properties. It contains ahierar
chical arrangement of program layers in which programs in a higher layer use the
facilities provided by programs in the layer below it. In fact, each layer takes an
abstract view of the layer below it. In this view the lower layer appears as a
that is capable of executing certain commands. It could even be a system
machine that is
capable of performing certain operations. The fact that the lower layer consists of
aset of programs rather than a computer system makes no
layer. Each layer extends capabilities of the machine provideddifference to the higher
by the lower layer.
The machine provided by the user interface layer
understands the commands in the
command language of the OS. This abstract view helps to understand the
an OS. design of

Logical and physicalorganization programmer's view of an entity is typically

A
an abstract view. It contains features and useful
grammer's perspective. Three important entitiesproperties
of an entity from a pro
and an VO device. The abstract view of an of this kind are a program, a file
entity is called the logical view and the
arrangement and relationship between components of the entity is called the
organization. The real view of an entity, which often coincides with the logical
system's view of the entity, is called the physical view and the operating
in it is called the physical organization. arangement depicted
Consider the execution of a program P in a computer
of the program P is shown in Pigure 1.3(a). It shows thesystem. The logical view
code of P written in a
higher level language, and the data that it reads
view of P'sexecution is shown in Figure during its execution. The physical
the machine language of the 1.3(b). Program P has been compiled into
computer system. In this form, the
of instructions that the
computer can understand and execute, andprogram data
consists
held in the
computer's memory. The rectangle represents the memory of the
The code of P occupies only one part of
the computer's memory. computer system.
programs also exist in the computer's memory. The Several other
P info This file is stored data of P is recorded in a fle
on a disk. During its
execution, P reads some data
 Introduction 5

from info, manipulates it, and

prints its
which info is recorded and the printer onresults. This view includes tne dis
which P's results are to be printed, tne
memory of the computer system and the CPUto
execute P's instructions.
Memory
OS
info
Program P Instructions
+ data space
of P Printer
Data Results CPU
Other
programs

(a) (b)
Big. 1.3 Logical and physical views of execution of a program

InSection 1.3.2.1,we discuss the logical and physical views of IO devices. We

willdiscuss logical and physical organizations of fles in Chapter 7.
1.2 GOALS OF AN OS

An operating system must not only ensure efficient use of a computer system, but
also provide user convenience. However, these considerations often conflict. For
of
example, providing Tast service to one user's request could mean that other users
remain
the system have to be neglected. It could also mean that resources should
allocated to auser's program even when the program is not using them, which would
lead to under-utilization of resources. In such cases, the OS designer must make a
with
conscious decision to trade off a part of convenience and speed for one user
Accordingly, the
that of other users or with efficient use of the computer system.
combination of efficient use and user
key goal of an operating system is to provide a which it is used. This is the notion of
convenience that best suits the environment in
effective utilization of a computer system.
in use because each one of them
We find alarge number of operating systems
At one extreme we have OSs that
provides adifferent flavor of effective utilization.
provide fast service required by command and control applications, while at the other
computer resources to provide low-cost com
we have OSs that make efficient use of
the middle, we have OSs that provide different combinations fast service
puting. In use and
we discuss several aspects of efficient
and efficient use. In the following, effective utilization.
understand the notion of
user convenience to
utilization
and effective utilization of computer systems The notion of effective
OS user-centric
considerations. At one end of the spectrum are
spansa broad spectrum of and fast service to user requests. They
are
such as user convenience
considerations,
support interactive computing or time critical
important in operating systems that
4 Operating Systems
programs in the user interface--lypically with the command interpreter-to request
use of resources and services provided by the system.

User interlace

Non-kernel programs

Kernel

Computer hardware
Fig. 1.2 A designer's abstract view of an OS

The abstract view of Figure 1.2 has interesting properties. It contains ahierar
Chical arrangement of program layers in which programs in a higher layer use the
facilities provided by programs in the layer below it. In fact, each layer takes an
abstract view of the layer below it. In this view the lower layer appearS as a system
that is capable of executing certain commands. It could even be a machine that is
capable of performing certain operations. The fact that the lower layer consists of
a set of programs rather than a computer system makes no difference to the higher
layer. Each layer extends capabilities of the machine provided by the lower layer.
The machine provided by the user interface layer understands the
commands in the
command language of the OS. This abstract view helps to understand the design of
an OS.

Logical and physical organization A

an abstract view. It contains features andprogrammer's view of an entity is typically
useful properties of an
grammer's perspective. Three important entities of this kind areentity from a pro
a program., a file
and an /O device. The abstract view of an entity is
called the
arrangement and relationship between components of the entity logical view and the
is called the logical
organization. The real view of an entity, which often coincides with the
System's view of the entity, is called the physicalview and operating
the arrangement depicted
in it iscalled the physical organization.
Consider the execution of a program P in a computer system. The
of the program P is shown in Figure 1.3(a). It shows the code of P logical view
written in a
higher level language, and the data that it reads during its execution. The
view of P'sexecution is shown in Figure 1.3(b). Program P has physical
the machine language of the computer system. In this form,
been compiled into
of
the program consists
instructions that the computer can understand and execute, and data held in the
computer's memory. The rectangle represents the memory of the computer system.
The code of P occupies only one part of the computer's memory.
Several other
programs also exist in the computer's memory. The data of P is recorded in a fle
named info. This file is stored on a disk. During its execution, P reads some data
 Introduction 5

from info, manipulates it, and prints its results. This view includes the disk on
which info is recorded and the printer on which P's results are to be printed, the
memory of the computer system and the CPU to execute P's instructions.
Memory

ProgramP O)
info
OS

Instructions
+ data space
of P Printer
Data Results
CPU
Other
programs

(a) (b)

Fig. 1.3 Logical and physical views of executionof a program

In Section 1.3.2.1, we discuss the logical and physical views of I/Odevices. We

will discuss logical and physical organizations of files in Chapter 7.
1.2 GOALS OF AN OS
system, but
An operating system must not only ensure efficient use of a computerconflict. For
also provide user convenience. However, these considerations often
other users of
example, providing tast service to one user's request could mean that
resources should remain
the system have to be neglected. It could also mean that
which would
allocated to a user's program even when the program is notusing them,
make a
lead to under-utilization of resources. In such cases, the OS designer must
user with
conscious decision to trade off apart of convenience and speed for one
Accordingly, the
that of other users or with efficient use of the computer system.
of efficient use and user
key goal of an operating system is to provide a combination
it is used. This is the notion of
convenience that best suits the environment in which
effective utilization of a computer system. each one of them
We find a large number of operating systems in use because
have OSs that
provides adifferent flavor of effective utilization. At one extreme we other
while at the
provide fast service required by command and control applications,
low-cost com
we have OSs that make efficient use of computer resources to provide
combinations fast service
puting. In the middle, we have OSs that provide different
aspects of efficient use and
and efficient use. In the following, we discuss severalutilization.
effective
user convenience to understand the notion of
OS and effective utilization of computer systems The notionof
effective utilization
are user-centric
spans a broad spectrum of considerations. At one end of the spectrum
considerations, such as user convenience and fast service to user requests. They are
critical
important in operating systems that support interactive computing or time
6Operating Systems

applications. System-centric considerations cxist at the other end of the spcctrum.

Elticient use of the system is the paramount concern in a system-centric computing
Cnvironment such ias non-interactive dataprocessing. It is achieved through use of
good resource allocation policics.
Elticiency of use has two aspects. An OS consumes some resources of a com
puter systemduring its own operation, for example, it occupies memnory and uses
the CPU. This cOnsumption of resources constitutes an overhead that reduces the
resources available to user programs.
The other aspeCt of efficient use concerns use of resources by user
Poor cfficicncy can result from two causes-if an OS over-allocates
programs.
resourCes to
prograns, or if it is unable to allocate free resources to programs that necd them.
The former leads to wastage of resources, while the latter leads to idling of
resources
and affects progress of programs. To achieve good efficiency, an OS must
both these effects and alsO minimize its counter
overhead.
Efficient use Efficient use of resources can be obtained by monitoring the use
of resources and performing corrective actions when
necessary. However, a com
puter system contains several resources like memory, I/Odevices and
the CPU, SO a
comprehensive method of monitoring efficiency may lead to high overhead. Con
sequently, operating systems employ simple and casy to apply but known-to-be
suboptimal strategies for ensuring good efficiency, e.g., they either focus on effi
ciency of a few important resources like the CPUand
memory, or handle user pro
grams in a manner that guarantees high efficiency. The latter
putation of efficiency, which isa recurrent overhead. Batch alternative avoids com
gramming, two early OSs using efficiency of use as a designprocessing and multipro
aim, used this approach
(see Chapter 2).
User convenience User convenience has several
facets as summarized in Table 1.2.
In the earlydays of computing,
tems emphasized efficient use.
computer systems were expensive, so operating sys
with bare necessity-the mere abilityConsequently, user convenience was synonymous
to execute a program written in a higher
language was considered adequate. Experience with level
better service, where the notion of serVice was early OSs led to demands for
limited to fast response to a user
request.
Other facets of user convenience can be linked
with the use of
computerizcd applications in new fields. Early operating systems hadcomputers and
complex user
interfaces, whose use required substantial user training. This was
most users were scientists and engineers. Easy-to-use acceptable because
to facilitate computer usage by new classes of users. interfaces had to be developed
User friendly operating systems
achieved this effect. In many ways, this move can be compared to
driving skills in the first half of the twentieth century. Over a periodthe spread of car
of time, driving
became less of an expertise and more of a skill that could be acquired with limited
training and experience.
 Introduction 7

Table 1.2 Facetsof User Convenicnce

Facet Examples
Necessity Ability to exccute programs, use the file system
GoodService Speedy response to computational requests
User friendly OS Easy-to-use commands, Graphical user interface (GUI)
New programming model Concurrent programming
Features for experts Means to set up complex computational structures
Web-oriented features Means to set up Web-enabled servers
Evolution Ability to add new features, use new computers

Computer users attacked new problems as computing power increased. New

models were proposed for developing cost-effective solutions to new types of
problems. Some of these models could be supported bythe compiler technology and
required little specific support from the OS. Modular and object oriented program
design are two such models. Other models like the concurrent programming model
required specific support features in the OS. User friendly user interfaces were
considered boring by professional programmers, hence specialized interfaces were
developed for expert users.
Yet another class of OS features was motivated by the advent of the Internet.
Effective use of the web requires the ability to set-up servers that are usable over the
web. This feature requires extensive networking support and an ability to scale up
at it.
the performance of a server or shut it down depending on the load directed
Finally, users expect their operating system t0 evolve with time to support new
features as newapplication areas and new computer technologies develop.

1.3 OPERATION OF AN OS
of its users with the
An operating system implements computational requirementsdescribed in Table l.3.
help of resources of the computer system. Its key concerns are
Table 1.3 Key concerns of an operating system

Concern OS responsibility
Programs Initiation and termination of programs. Providing convenient
methods so that several programs canwork towards acommongoal.
Resources Ensuring availability of resources in the system and allocating them
to programs.
Scheduling Deciding when, and for how long, to devote the CPUto a program.
Protection Protect data and programs against interference from other users and
their programs.
To realize execution of a program, an operating system must ensure that resources
 8 Operating Systems

Iike memoryand I/Odevices are available to it. It must also provide sufficient CPU
attention to a program's execution. This function is calledscheduling. A user may
employ severalprograms to fulfill a computational requirement, so an OS must pro
Vide means to ensure harmonious working of such programs. To win the trust of
Users, an OS must provide a guarantee that their data would not be illegally used
or lost, and that execution of their programs would not face interference from other
programs in the system.
An operating system performs several housckeeping tasks to support the func
tions of creation and termination of programs, resource allocation, scheduling and
protection. An operating system also performs other tasks to implement its notion of
effective utilization. Table 14describes commonly performed OS tasks.
Table 1.4 Common tasks performed by operating systems

Task When/who performs

1. Maintain a list of
2.
authorized users System administrator
Construct a list of
all resources in the system When OS is started
3. Initiate execution of programs At user commands
4. Maintain resource usage information by programs Continuously during OS
and current status of all programs operation
5. Maintain current status of all resources and allocate At resource request or
resources to programs when requested release
6. Perform scheduling
7. Maintain information for protection During OS operation
8. Handle requests made by users and During OS operation
their programs At user requestsS
The list of persons who are authorized to use the
by the system administrator of the OS. The computer system is maintained
this list in accordance with the computer usage administrator adds and deletes names to
is switched on, it invokes a procedure called policy. When the computer system
booting, which performs a number of
preparatory actions and starts operation of an OS. One of these actions is to make
a list of all resources in the system.
The OS initiates a new program when a user
issues a command to execute it. The OS keeps track of
resource usage by programs
as this information might be needed to implement its notion of effective utilization,
e.g., to ensure fairness in the use of resources. The OS also
about current status of resources and programs for use while
maintains information
performing resource
allocation and scheduling. The following sections discuss preliminaries of how an
OS manages programs, resources and scheduling.

1.3.1 Programs
Acomputational structure is a configuration of one or more programs that work
towards acommon goal. It is created by issuing one or more commands specify
relationships betweenprograms and to initiate their execution. Some typical compu
 Introduction 9
tational structures are:
" A single
" A program
sequence of single programs
Co-executing programs.
These computational structures wil be defined and
their salient features are described here to described in later chapters; only
them. Table 1.5 summarizes OS illustrate user convenience provided by
responsibilities for these computational structures.
Table 1.5 Computational structures and OS responsibilities

Computational structure OS responsibilities

Single program Perform program initiation/termination, resource
management
Sequence of single programs Implement program dependence--terminate the
sequence if aprogram faces abnormal termination
Co-executing programs Provide appropriate interfaces between programs,
perform termination of the co-executing programs

Singleprogram Asingle program computation consists of the execution of a pro

gram on agiven setof data. The program can be either sequential or concurrent. A
single program is the simplest computational structure; it matches with the conven
tional notion of a program. In a concurrent program, different parts of the program
can execute concurrently. The OS needs to know the identities of these parts toorga
nize their concurrent execution. This function isnot served by the user interface of
the OS; Chapter 9 describes how it is implemented. In this section each program is
assumed to be sequential in nature.

Sequence of single programs Each single program in the sequence is initiated by

the user through a separate command. However, a sequence of single programs has
its own semanticsa program should be executed only if the previous programs in
the sequence executed successfully. To achieve a common goal, the programs must
explicitly interface their inputs and outputs with other programs in the sequence.
Example 1.1 discusses the notion of asequence of single programs in MS DOS.
Example 1.1 An MS DOS .bat fle can be used to form a sequence of single pro
grams. The file contains a sequence of commands, each command indicating exe
cution of aprogram. Let a .bat hle contain commands to initiate a sequence of
programs to compile, link and execute a C program: The C compiler compiles a C
program existing in file alpha. c, linker links the output of the compiler to generate
an executable program named demo, and program demo executes on the data contained
infle sample. The command interpreter loads the C compiler into the memory for ex
ecution. When the compiler completes its operation, the command interpreter initiates
execution of the linker. Eventually, it initiates execution of demo.
10 Operating Systems

C
linker demo
compiler

Fig. 1.4 Steps in exccution of' a sequcnce of program

Figure 1.4 illustrates the three computations. Note that each program in the sequence
must make its own arrangements to communicate its results toother programs. This
Is (ypically achieved by using some file naming conventions, e.g., the output of the
Ccompiler may be put into a file named alpha .obj so that linker can pick it up
from there. The command interpreter is unaware of these arrangements; it Simply
implements the commands issued to it.
Semantics of a sequence of programs dictate that linker would be executed only if
the compilation of the C program was successful, and that demo would be executed
only if linking was successful. This would not have been the case if the same three
programs were initiated as three single programs.
Co-executing programs Auser initiates co-executing programs by indicatingtheir
names in a single command. Co-execution semantics require that the
should execute at the same time, rather than one after another as in a programs
sequence of
programs, and interact with one another during their execution. The nature of inter
action is specific to a co-execution command. The OS provides
faces between the co-executing programs. Example 1.2 discussesappropriate inter
programs in Unix. co-execution of
Example 1.2 The Unix command
cat names sort |unigwc -1

initiates execution of four co-executing programs to count the

in file names. These programs are-cat, sort, number of unique names
uniq and wc. |' is the symbol for a
Unix pipe, which sends the output of one program as input to another
the output of cat is given to sort as its input, the program. Thus,
and the output of uniq is given to wc. cat reads output of sort is given to uniq
contents
each name it finds there into its standard output file. The
of file names and writes
output of cat is the input to
sort, so sort reads these names, sorts them in alphabetical order,
into its output file. uniq removes duplicate names appearing in its and writes them
the unique names. wc counts and reports the number of names in input and outputs
its input. (-1 is
an option to the wc command asking it to count the number of lines in
its input since
uniq putseach name in a line by itself.)
Note that the four programs do not form a sequence of programs. The
programs
co-exist in the memory and co-operate with one another during their execution (see
Figure 1.5). Unlike in a sequence of programs, passing of one program's results to
the next program is the responsibility of the OS. The command processor also has
to provide appropriate synchronization between the programs to ensure that a pro
gramconsumes some data only after it has been produced. Allco-executing programs
terminate together. Control then returns to the command processor.
 Introduction 11

Cat Sort uniq WC

Fig. 1.5 Co-executing programs

L.3.2 Resource Allocation and Scheduling

The resource allocation function performs binding of one or more resources with a
requesting program-that is, it associates resources with a program. Italso deallo
cates reSources from a program and allocates them to other programs. Allocation
and deallocation of resources in this manner helps to implement resource shar1ng by
users. Resources can be divided into system resources and user-created resources.
The resource protection function prevents mutual interference between users
sharing a set of resources. Protection is implemented by performing an allocation
only if a request satisfies a set of constraints. Some of these constraints relate to the
several
nature of a resource, e.g., whether a resource can be used concurrently by
constraints
users. Other constraints are specified by the owner of a resource. These
typically embody the notion of access privileges and specify whether a specific user
should or should not be allowed to access a resource.
Two popular strategies for resource allocation are:
Partitioning of resources
" Allocation from a pool.
decides a priori what resources shbould
Inthe resource partitioning approach, the OS
approach is called static allocation because
be allocated to a user program. This
aprogram begins. Static resource
the allocation is made before the execution of problems
flexibility that leads to
allocation is simple to implement. However, it lacksprogram but remain unused, and
allocated to a
like wastage of resources that are to a program during its execution.
inability of the OS to grant additional resources basis of perceived needs of
made on the
These difficulties arise because allocation is
than its actual needs.
aprogram, rather maintains acommon pool of resources and
In the pool-based approach the OS requests a resource. This approach is
pool whenever a program
allocates from this a pro
dynamic alocation because allocation takes place during exccution of
called resources, hence it can provide better
resource
gram. It avoids wastage of allocated
utilization. central data
simple resource allocation scheme uses a resource table as the
A and address of a
inthe table contains the name
structure (see Table 1.6). Eachentry it is free or allocated to some
pr0
present status, 1.e., whether
resource unit and its of I/O devices
procedure by sensing the presence
gram. This table is built by the boot
resource allocation approach, the OS considers the
In the partitioned
in the system.
 12 Operating Systems

Table 1.6 Resource

allocation table

Resource name Class Address Allocation status

printerl Printer 101 Allocated to Pl
printer2 Printer 102 Free
printer3 Printer 103 Free
disk l Disk 201 Allocated to Pl
disk2 Disk 202 Allocated to P2
cdwl CD writer 301 Free

number of resources and programs in the system and decides hoW many
each kind would be allocated to a program. For resources of
example, an OS may decide that a
program can be allocated 1MB of memory. 2000 disk blocks and a
collection of monitor. Such a
resources called apartition.
is
In thepool-based allocation approach. OS consults the resource table
program makes a request for a resource, and allocates when a
of aresource class exist in the accordingly. When many units
system, a resource request only
class and the OS checks if any unit of that class is available indicates
for
the resource
based allocation incurs overhead of allocation. Pool
ally; however, it avoids both allocating and deallocating resources individu
by adapting the allocation to problems faced by the resource partitioning approach
resource requirements of programs.

IMB |IMB IMB

|IMB I MB | IMB

Resource
pool

Partition 1 Partition n
P1 P2
(a)
Fig. 1.6 Resource (b)
partitioning and pool based allocation
Figure 1.6(a) shows a set of partitions that are
resource table contains entries for resource defined during boot time. The
resources. A free partition is allocated to eachpartitions rather than for individual
program before its execution is ini
tjated. Figure I.6(b) illustrates pool based
a monitor, a disk area of 2000 blocks allocation. Program Pl has been allocated
andTMB of memory. Program P2 has been
allocated a monitor and 2 MB of memory: disk area is not
not request it. Thus pool based allocation avoids allocated because P2 did
allocation of resources that are not
 Introduction 13

needed by a program. Programs with large or unusual resource requirements can be

handled by the OS so long as the required resources exist in the system.
Sharing of resources Programs can share a resource in twO ways:
Sequential sharing
" Concurrent sharing.

In sequential sharing, a resource is allocated for exclusive use by a program. When

the resOurce is deallocated, it is marked free in the resource table. Now it can be
allocated to another program. Inconcurrent sharing, two or more programs can con
currently use the same resource. Examples of concurrent sharing are data files like
bus time tables. Most other resources cannot be shared concurrently. Unless other
Wise mentioned, all through this text resources are assumed to be only sequentially
shareable.
The OS deallocates a resource when the program towhich it isallocated either
terminates or makes an explicit request for deallocation. Sonmetimes it deallocates a
resource by force toensure fairness in its utilization by programs, or to realize certain
system-level goals. This action is called resource preemption. We use the shorter
term preemption for the forced deallocation of the CPU. A program that loses the
CPUin this manner is called apreempted program.
CPUsharing The CPUcan be shared only in a sequential manner, so it can be
assigned to onlyone program at a time. Oher programs in the system have to wait
their tun on the CPU. The OS must share the CPUamongprograms in a fair manner.
Therefore,after a program has executed for a reasonable amount of time, it preempts
the program and gives the CPUto another program. The function of deciding which
program should be given the CPU, and for how long, is called scheduling,

Preempted progranm

New Scheduler CPU

Completed
program program
Programs waiting Selected
for the CPU
program

Fig. 1.7 A schematic of scheduling

Figure l.7 shows a schematic for CPUscheduling. Several programs await allo
cation of the CPU. The scheduler selects one of these programs for execution on the
CPU. A preempted program is added to the set of programs waiting for the CPU.
Memory sharing Parts of memory can be treated as independent resources. Both
partitioning and pool-based allocation can be used to manage memory. Partitioning
 14 Operating Systems

IS simple to implement. It also simplifies protection ot memory areas allocated to

different programs. However, pool-based allocation achieves better use of memory.
Memory canbe preempted from inactive programs and used lo accommodate active
programs. The spccial term swapping is used for memory preemption; the term
memory precmption' is rarely used in OS literature.

Partition

A A
B

3 B
Pool of
Unused
memory
4

(a) (b)
Fig. 1.8 Memory allocation schematics: (a)
partitioned allocation, (b) pool-based allocation
Figure 1.8 illustrates the approaches to memory
titioned approach the memory is divided a priori intoallocation.
many
In the fixed par
allocated to aprogram at its initiation. Figure 1.8(a) illustratesareas.
the
A partition is
memory has been divided into equal sized partitions and two of situation when
cated to programs A and B. Two partitions are them have been allo
is smaller than the size of the currently free. Note that the size of B
partition, so some memory allocated to it remains un
used. Figure 1.8(b) illustrates the pool based
allocated memory from the pool. Each program approach. Newly initiated programs are
is allocated only as much
as requested by it, so allocated memory is not wasted. memory
Disk sharing Different parts of a disk
can be treated as
Both partitioning and pool based
approaches are
independent resources.
show a preference for the pool based feasible; however, modern OSs
by an operating system; approach. Disk preemption is not
individual users can preempt their disk areas bypracticed
their files onto tape cartridges. copying
1.3.2.1 Virtual Resources
A virtual resource is a fictitious
through use of areal resource. Anresourceit is an illusion
OS may use the same realsupported by an Os
several virtual resources. This way, it can resource to suppo
number resources than it actually does.
of give the impression of having a largei
the use of an appropriate real resource. In Each use of a virtual resource
that sense, a results l
view ofa resource taken by a virtual resource is an abstract
Jseof virtual resources computation.
Started with the use of virtual devices. To
interference between programs, it was a good idea to allocate a deviceprevent mutua
exclusively
 Introduction 15

TOr use by one program. However, a computer system did not poSsess many real
devices, SO virtual devices were used. An OS would create a virtual device when a
user needed an I/O device. Thus, the disk areas called disk 1l and disk2 in Table 1.6
could be viewed as small virtual disks based on the real disk. Virtual devices are used
incontemporary operating systems as well. Aprint server is a common example of
a virtual device. When a program wishes to print a file, the print server simply
copies the file into the print queue. The program requesting the print goes on with
its operation as if the printing had been performed. The print server continuously
examines the print queue and prints any file it finds in the queue.
Mostoperating systems provide a virtual resource called virtual memory, which
is an illusion of a memory that is larger in size than the real memory of a computer.
Its use enables a programmer to execute a program whose size may exceed the size
of real memory.
Some operating systems create virtual machines (VMs) sothat each machine can
be allocated to a user. The virtual machines are created by partitioning the memory
and I/O devices of a real machine. The advantage of this approach is twofold. AI
location of avirtual machine to each user eliminates mutual interference between
users. lt also permits each user to select an OS of his choice to execute on his virtual
machine. Ineffect, this arrangement permits users to use differentoperating systems
on the same computer system simultaneously (see Section 14.5).

1.3.3 Security and Protection

An unauthorized person may try to use or modify a file. He may also try to interfere
with use of the file by authorized users and their programs. An operating system
must thwart such attempts. Protection and security are two aspects of this issue.
The protection function counters threats of unauthorized use or interference that are
posed by users of a computer system, whereas the security function counters similar
threats that are posed by persons outside the control of an operating system.
When a computer system functions in complete isolation, the protection and
security issues can be separated easily. The operating system verifies the identity
of a person through a password check when the person logs in. This procedure is
called authentication. Therefore, security threats do not arise in the system if the
authentication procedure is foolproof. A file open statement executed by a program
poses a protection threat if the user who initiated the program is not authorized to
access the file. The file system counters this threat by aborting such a program. Fig
ure 1.9 illustrates this arrangement.
When a computer system is connected to the Internet, and a user downloads
a program from the Internet, there is a danger that the downloaded program may
interfere with other programs or with resources in the system. This is a security
threat because the interference is caused by some person outside the system, called an
intruder, who either wrote the downloaded program, or modified it, so as to interfere
with other programs. Such security threats are posed either through a Trojan horse,
 16 Operating Systems
Computer system

Security Resourcs
Intruder threats

Protection
threats

Internet

Programs
Authentication A Users

Fig. 1.9 Overview of protection and security concerns

which is a program with aknown legitimate function, anda well-disguised malicious

function; or through a virus, which is a piece of code with a malicious function that
attaches itself to other programs and spreads to other systems when such programs
are copied. Another class of security threats is posed by worms, which are programs
that replicate by themselves through holes in the security set-ups of operating sys
tems.

Operating systems address security threats by ensuring that a program cannot be

modified while it is being copied over the Internet, and by plugging security holes
when they are discovered. Users are expected to contribute to
caution while downloading programs from the Internet. security by exercising

1.4 PREVIEW OF THE BOOK

Abstract views help us to limit the scope of study so that we may

feature, and to present generic concepts or ideas. We will focus on a selected
use abstract views to
present the design and implementation of features of an
this book. operating system all through
In Part I of the book, we focus on
system organizes its own functioning, fundamental concepts, i.e., how an operating
and manages user programs, and the
mental resources in the system, namely, the CPU, funda
book is devoted to advanced topics in the memory and files. Part II of ne
sources, and the design techniques used tomanagement
ensure that
of user programs and mboxre
evolution in computer technology and expectations ofoperating systems can adap
primarily discuss operating systems for conventional computer users. Parts Iand l
acterized by use ofa single computer system having acomputing environments cha
discusses operating systems for the single CPU; only Chapter D
of the book is devoted to a study of multiprocessor
computing environment. Part IIl
distributed operating systems, which gained "
importance in the 1990's due to advances in networking and
availability cheap
of
46 Operating Systems
Ma dataregister. Theinterruptroutinetakesthe necessary actions for this purpOse and
passes controlto the scheduler. The scheduler selects a user prOgram and switches the
exccution.
to its systemdoes not provide an operand in the SI instruction,, aprogram
IlaCPU
computer
pushes a code corresponding tothe system call being made on the stack before exe-
cuting the SIinstruction. The kernel analyzes the code and performs the neceSsary
action. In Example 2.4. the program pushes 10 on the stack before executing the SI

instruction.
Table 2.4 indicates some generic types of system calls and lists a few examples

Resource related calls provide resource allocation and dealocation

cach type.
ofvices. ser
f the requested resource is available, the resource allocation request is hon-
ored straightaway; otherwise, the requesting program's execution is delayed until the
program may wish to check for atvte
resource becomes available. Therefore, a
related calls provide servicer .
ityof a resource before making a request. Program certain period of
start or terminate execution of other programs, and to wait Tor a
in the
time. Communication related calls set up communication with other programs
each O8
system and realize exchange of messages. Apart trom these generic types,
provides a host of specialized system calls.
Table 2.4 System calls

Type Examples
Resource Allocateldeallocate resource, check resource availability
Program Setvawait timer interrupt,execute/terminate program
File Open/close a file, read/writea file
Information Get time and date, get OS information, get resource information
Communication Send/receive message, setup/terminate connection

2.2 EFFICIENCY, SYSTEM PERFORMANCE AND USER CONVENIENCE

In Chapter I we discussed aspects of efficient use of a computer System and user
convenience providedby an operating system. We also introducedthree fundamental
co-
computational structures-asingle program, a sequence of single programns andthis
In
executing programs-to illustrate how an OS can provide user convenience. System
Section, we discuss the
and describe some metricsnature of computations
that are performed
used to measure efficiency, an operat1ng
in system performance
and user convenience. The Concepts and terms introduced here Will be usefulinlater
sections of this chapter, and in the following
chapters.
2.2.1 Nature of Computations in an OS
In a non-interactive theOS
ilto
environment, acomputation is
and obtaining its results at the realized by submitting classical
for processing end of its Inthe
processing-
 Overview of Operating Systems 47
non-nteractive environment, computations were classified into programs and jobs.
A program is a set of functions or modules, including some
obtaincd from libraries.
A job iS a sequence of single programs (see Section L.3.l and
COnsists of asecquence of job steps, where cach job step
Example 1.). It
constitutes cxccution of one
program. Thus, a job for compiling and executing a C++ program consists of three
job steps to compile, link and execute the program. It is not
job step unless each of the previous job steps has executed meaningtul e.g.,execute a
to
successfully,
is not meaningful unless compilation was successful. The notion of a Iinking
job is of less
relevance in interactive computing environments because a user typically submits
one command at a time to the command prOcessor.
A process represents an execution of a program. We illustrate some advantages
of processes when we discuss real time systems in Section 2.7. In the interest of
simplicity, we defer discussion of other features of processes until Chapter 3.
In an interactive environment, a user interacts with his program. One interaction
consists of presentation of a computational requirement by the user to a program
we call this a subrequest-and the computation of a response by the program.
Depending on the nature of a subrequest, the response may be in the form of a result
or it may be an action performed by the program, e.g., a data-base update.
Table 2.5 Computations in an OS

Computation Description
Program Aprogram is a set of functions or modules, including some func
tions or modules obtained from libraries.
Job Ajob is a sequence of job steps, where each job step is comprised
of the execution of one program. It is not meaningful to execute
the program in ajob step unless programs in the previous job steps
were successfully executed (see Section 1.3.1).
Process A process is an execution ofa program.
Subrequest A subrequest is the presentation of a computational require
ment by a user to a process. Each subrequest produces a single
response, which iseither a set of results or a set of actions.

Table 2.5 describes the job, program, process and subrequest computations.
Notions of system performance and user convenience in an operating system depend
on the nature of computations. We discuss this issue in the next section.
2.2.2 Measuring Efficiency, System Performance and User Convenience
Measurement provides a quantitative basis for comparing alternative techniques used
in the design and implementation of an OS. However, several practical difficulties
arise in making quantitative comparisons. Some atuributes of an OS may be intan
gible hence numerical comparisons may not be possible, or techniques may possess
different attributes hence comparisons may not be meaningful.
48 Operating Systems
We encounter both difficulties when we consider
venience in different classes of operating systems.
intertaces provide intangible conveniences, and
efficifeatures
Some ency of likeuse annd user
different computing User con
use ditterent notions of cficiency and user convenience. Howeverthe
marized in Table 2.6 are useful to understand the impact of a tcchniquemeasures sum frie
environmentndiy
aspccific class. We use these measures in the
Svstems of'
Table .6 Measures of eticieney and user convenience following sectioonns.operating
Attribute Concept
Efficiency of use CPUefficiency Description
Percent utilization of the CPU.
System performance Throughput Amount of 'work' done per unit time.
User service Turn around time Time to complete a job or
Response time Time to process.
between aimplement
oneinteraction
user and his/her process.

Efficiency and system performance Although go0d efficiency of use is important

it is rarely a design goal of an
operating system. Go0d performance in its comput.
ing environment is an important design goal.
this end, for example, efficiency of Efficiency of use may be a means to
resources like the CPUand disks are important
parameters for fine-tuning the performance of a system. In Chapters 6 and 4. we
instances of such usage in the context of virtual memories see
and scheduling.
System performance is typically measured as throughput.

Definition 2.2 (Throughput) The throughput of a system is the number of

programs, processes or subrequests completed by it per unit time. jobs,

The unit of work used in computing throughput

depends on the nature ot ne
computing environment. n a non-interactive environment,
measured interms of number of jobs, programs or processes throughput of an OS 3
In an interactive environment, throughput may be completed per u
measuredcomputing
of subrequests completed per unit time. In a specialized in terms ofenvironment,
the nu
performance may be measured in terms meaningful to the application beingserviced.
e.g., the number of transactions in a banking environment. Throughput can also be
used as a measure of performance for VO devices. For example, the throughputt ofa
disk can be measured as the number of /O operations completed per unit time orthe
number of bytes transferred
per unit time.
User service User service is a measurable aspect of user convenience. It indicates
how a user's computation has been treated by the OS. We define two measuresof
user service-turn-around time and response time. These are used in non-interactive
and interactive computing environments, respectively.
 Overview of Operating Systems 49
Definition 2.3 (Turn-around time) The turn-around time of a job, program or process
is the time since itssubmission for processing to the time its results beconme available
to the user:

Definition 2.4 (Response time) The response time provided to a subrequest is the time
between the subnission of the subrequest by a user and the formulation of the pro
cess's response to it.
2.3 CLASSES OF OPERATING SYSTEMS
2.3.1 Key Features of Different Classes of Operating Systems
Table 2.7 summarizes key features of five fundamental classes of operating systems.
Table 2.7 Key features of classes of operating systems

OS class Period Prime concern Key concepts

Batch Processing 1960s CPUidle time Spooling, command processor
Multiprogramming 1970s Resource utilization Program priorities, preemption
Time sharing 1970s Good response time Time slice, round-robin scheduling
Real time 1980s Meet the deadline Real timne scheduling
Distributed 1990s Resource sharing Transparency, distributed control

The periodcolumn shows the period when operating systems of that class first
came into widespread use. Interestingly, key features of the early OS classes can
be found in today's operating systems as well! In fact, that is why we study them
today. The prime concern column of Table 2.7 shows the fundamental effectiveness
criterion that motivated development of that OS class. The key concepts column
indicates concepts that were evolved to help in implementing the prime concerns of
an OS.

Batch processing and multiprogramming systems Acursory look at the prime con
cerns in different classesof operating systems reveals an interesting trend. The first
twoOS classes,viz. batch processing and multiprogramming, were concerned with
efficient use of a computer system. In batch processing, the concern was limited to
CPUefficiency, so avoiding wastage of CPU time was the prime concern. In multi
programming, the concernwas broadened to include other resources, mainly memory
and the /O subsystem, so a balanced utilization of all resources in the system was
those
the prime concern. These concerns arose from the high cost of hardware in
days, and satisfying these concerns did not provide any direct benefits to users.

Time sharing and real timne systems In mid-seventies, the focus shifted from effi
was
cient use of a computer system to productivity of computer users. This shift
necessitated by the clamor for efficient service by users, and it became practical due
to reducing costs of hardware. Time sharing systems focused on providing a quick
50 Operaling Systems

Tesponse to a subrequest. This focus provided angible benefits to computer users.

About the same time, applications of computers in time-critical environments led to
the development of real timeOSs that focused on completing a computationaltask
belore the deadlinc specilied by an application. Due to the need to meet deadlines,a
real time system is often dedicated to a single time-critical application.

Distributed systenms In the 1990s, declining hardware costs led to the develop
ment of disributed systems that consisted of several computer systems with varying
nunber and sophistication of resources. Adistributed system permits resource shar
ing across the boundariesof individual computer systems. Thus, a user of a low cost
computer system can use expensive resources existing in other computer systems.
Somefeatures of resource sharing resemble efficient use of resources. However, it
possesses other important features like fault tolerance that have much to do with user
Convenience.

Multi
\programming
Time Distributed
sharing OS
Efficicnc y

Real
time OS
Batch
processing

Necessity Good service Resource sharing

User convenience
Fig. 2.11 Efficienc y and user convenience in different oS classes

2.3.2 Efficient Use and User Convenience

As discussed in the
Introduction, efficient use and user convenience often exert con
trary pressures on the design of an OS. However, the trend in OS design has been
towards increasing user convenience. Figure 2.11 shows the balance between effi
ciency and user convenience achieved by different OS classes. Note that neither axis
in this plot is homogeneous. The notion of user convenience
changes from one OS
class to another. Resources whose efficiency has been plotted also
change acrOSs
 E

45656 Overview of Operating Systems 51

OS classCs. As discu[sed in Section L2, nccessity is at the lowest end of user con
venicnce. Batch processing and multiprogramming operating systems provide this
levelof user convenicnce. Batch processing provides low cfficicncy hecause it pro
cessesone user program at a ime. Multiprogramming provides higher cfliciency by
proccssng many user programs in an intcrlcaved manner Over the same duration of
time.
Atime sharing system provides good service, which is is ratcd higher on the scale
of'user convenience. A time sharing system processes many programs over the same
period of time, hence it can provide better efficiency than pure batch processing.
However, efficiency may be lower than that of multiprogramming systems due to
higher overhead of OS operation. Areal time system may provide lower efficiency
than a time sharing system bccause it may be dedicated to a single application.
A distributed OS provides resource sharing across the boundaries of computer
systems, so efficiency provided by it covers a wider range than any other operating
system. At the lower end, lowcost computing may rescmble batch processing in
many ways. The resources available in a computer system may be adequate only for
a small number of programs. Advantages of multiprogramming become available if
a computer system under the control of a distributed OS has reasonable computing
resources. Further, resource sharing across boundaries of individual computer sys
tems may enhance resource utilization. Therefore, a distributed OS has the potential
toprovide higher efficiency than a multiprogramming system.
2.3.3 Execution of User Computations in Different OS Classes
Table 2.8 summarizes the manner in which execution of user computations is orga
nized in operating systems of different classes. A batch processing system operates
in astrict one-job-at-a-time manner. Within a job, it executes thc programs oneatter
another. Thus only one program is under execution at any time. CPUefficiency is
enhanced by efficiently initiating the next job when one job ends.
In a multiprogramming system, several programs are in a state of partial com
pletion at any time. Resources allocated to a program are utilized when the program
is executed. The OS switches the CPU between execution of different programs to
ensure a balanced utilization of resources. It uses the notion of priority to decide
which program should be executed on the CPUat any time.
Atime sharing system also interleaves execution of processes. However, the
purpose of interleaving is to provide goodresponse times to allprocesses. Hence
a time sharing OS does not assign priorities to processes; it provides fair cxccution
opportunity toeach process.
A real time system permits a user to create several processes witlhin an app!i
cation program and assign them execution priorities. It interlcaves the execution of
processes to meet the deadline of the application.
Adistributed OS provides sharing and efficient use of resources located in all
computers in the system. One way to achieve this is to let a process access resources
52 Operating Systems
systems
Execution of user computations in different operating
Table 2.8

OS class Computations Key execution concept

Jobs One job is executed at a time.
Batch processing
Multiprogramming Programs
ajob are executed sequentially.
OS interleaves execution
of
Programs in
grams to improve resource several pro-
Processes
system performance.
OS interlrleaves execution of
utilization and
Time sharing
processes to
provide goodresponse toall processes,
Processes OS interleaves execution of
Real time processes in an
applicationprogram to meet its deadline
Distributed Processes Access to remote resources using network.
ing. Execution of processes of an applica
tion in different computers to achieve shar.
ing and efficient use of resources.

located in a remote computer using the networking component. However, useof

networking causes delays, so the OS may execute processes of a program in different
computers to achieve good utilization of resources.
Thus, the five fundamental OS classes cater for different notions of effectivenes,
and use different concepts and techniques to meet their design goals. In Sections 2.4+
2.8,we discuss features of the fundämental OS classes. New concepts and techniques
used in their implementation are defined and illustrated with the help of examples.
2.4 BATCH PROCESSINGSYSTEMS

Computer systems of the 1960's used punched cards as the primary input mediun.
A program and its data consisted of a deck of cards. A programmer would submit a
program at a counter in the computer center. The computer center staff would handle
the card decks and eventually the onthe
execution of a program would be set up
and
computer by a computer operator. The operator too had to handle the card decksSome
perform physical actions like loading them into the card reader and pressing
switches on the console toinitiate processing of a program. The CPUofthe compuler
system was idle while the CPUtime was
operator
performed these actions. Alot of
wasted in this manner. Batch processing was introduced to avoid this wastage.
batch
Abatch is a sequence of user jobs formed for the bya
purpose of processing
structure of a
processing operating system. Note that abatch is not a computational ypically
user. Each job in the batch is of other jobs in the batch; jobs setof
independent
belong different users. A computer
to organizing a and
operator forms a batch by Start
user jobs in a sequence and inserting special indicate the thebatch
end of the batch. The marker cards to by
operator submits a batch as a unit of processing
 Overview of Operating Systems 53
processing operating system. The primary function of the batch processing system
is to service the jobs in abatch one after another without requiring the operator's
intervention. This is achieved by automating the transition from execution of one job
to that of the next job in the batch.

Batch processing is implemented by the kernel (also called the batch monitor),
which resides in one part of the computer's memory. The remaining memory is used
for servicing a user jobthe current job in the batch. When the operator gives a
command to initiate the processing of abatch, the batch monitor sets up the process
ing of the first job of the batch. At the end of the job, it performs job termination
processing and initiates execution of the next job. At the end of the batch, it performs
batch termination processing and awaits initiation of the next batch by the operator.
Thus the operator needs to intervene only at the start and end of a batch.
System Batch
area Monitor
1 job job; jobn ‘
User Current 'Start of batch' End of batch
area
Job of card card
the batch

Fig. 2.12 Schematic of a batch processing system

Figure 2.12 shows a schematic of a batch processing system. The batch consists
of n jobs, jobj, job. job,,, one of which is currently in execution. The figure
depicts a memory map showing the arrangement of the batch monitor and the current
job of the batch in the computer's memory. The part of memory occupied by the
batch monitor is called the system area, and the part occupied by the user job is
called the user area.

Batch processing systems used the notion of virtual devices described in Sec
tion 1.3.2.1 to conserve the CPUtime of a powerful computer system as follows:
The computer system used virtual devices for input and outputtypically tapes or
disks instead of punched cards and printers. To make this feasible, a program first
recorded a batch of jobs on a magnetic tape. The batch processing system processed
these jobs and wrote theirresults on another magnetic tape. The contents of this mag
netic tape were then printed by another program. The two spooling operations, called
inspooling and outspooling, respectively, were typically performed on asmaller com
puter system having a slow CPU. The main computer used the faster magnetic tape
mediahence it suffered smaller CPU idle imes. Results of ajob were not released to
auser immediately afer the job was processed: they were released only after printing
wascompleted.
$4 Operating Systenms
2.4.1 User Service

The notion of turn-around time is used to quantify user service in a bateh processing
system. Duc to spooling, the turn-around time of ajobjob; processed in a batch
processing system includes the following time intervals:
1. Time until a batch is formed (i.e., time until the jobs jobi+|, . job, are sub
mitted)
2. Time spent in executing alljobs of the batch
5. Time spent in printing and sorting the results belonging to different jobs.
Thus, the turn-around time for job; is a function of many factors, its own execution
time being only one of them. It is clear that use of batch processing does not guaran
tee improvements in the turn-around times of jobs. In fact, the service to individual
users would probably deteriorate due to the three factors mentioned above. This is
not surprising because batch processing does not aim at improving user service-it
aims at improving CPU utilization.
Example 2.5 Figure 2.13 illustrates different components in the turn-around times
of a job. The user submits the job at time tÍ. However, the batch is not formed
immediately. The operations staff of the computer center form a batch only after a
sufficient number of jobs have been submitted. Consequently, the batch actually gets
formed at time f. Itsprocessing starts at time and ends at t,. Printing of the results
is commenced at time l4 and completes at t_. The results are returned tothe user only
at time to. Thus the turn-around time of the job is (t6 to). It has no direct relation to
its own execution time.

Batch Result
execution printing
t2 t6

Job is Batch is Results are

submitted formed returned to user
turn-around time

Fiy. 2.13 Turn around time in a batch processing system

2.4.2 Batch Monitor Functions

To exercise effecive control over the batch processing environment, the batch mon
itor performs three functions-scheduling, memory management, and sharing a
protection. The first two functions are trivial. Scheduling is implicit in formation o!
a batch, while memory allocation is performed at system boot time by allocating all
memory not used by the OS to the processing of user jobs. The memory is shared
sequentially by user jobs.
 Overvicw of Operating Systems 55
The protection function is more complex. User jobs cannot interfere with each
other's execution directly because they never coexist in acomputer's memory. How
ever. contrary to one's intuition, even sequential sharing of resources can lead to loss
of protection. This problem is discussed in the following.
Protection problems in card based systems As mentioned at the start of this Sec
tion, early batch processing systems were card-based systems of the 1960's. These
systems possessed few secondary memory units like tapes and disks, so commands,
user programs, and data were all derived from a single input source-the card reader.
This feature could lead to interference between consecutive jobs in a batch. Exam
ple 2.6 illustrates how this can happen.

Example 2.6 A and B are consecutive jobs in a batch. Each job consists of a program
and its data. The program of job A requires ten data cards whereas the user who
submitted job A has included only five data cards in it. When job A executes, it reads
its five data cards and the first five cards of job B as its own data. When job B is
processed, the compiler finds many errors since the first five cards of B are missing.
Thus job A has interfered with the execution of job B.

Control statements and the command processor A batch processing system

requires a user to insert a set of control statements in a job. The control statements
are used for two purposesto implement a job as a 'sequence of programs' (see
Section 1.3.1), and to avoid mutual interference between jobs. Figure 2.14 shows
the control statements used to compile and execute a Pascal program. For simplicity
statements concerning data-setdefinitions or device assignments that were necessary
in most batch processing systems are omitted.
The // JOB statement indicates the start of a job. It contains accounting infor
mation for the user like his name, user category, and resource limits. An// EXEC
<program name> statement, where <program name> is the name of a program to
be executed, constitutes ajob step. Cards containing the data for<program name>
follow this statement. The statement 7*' marks the end of data. Thus, the state
ment// EXEC PASCAL in Figure 2.14 indicates that the Pascal compiler is to be
executed to compile a Pascal program. The Pascal program to be compiled is placed
between this statement and the first /** statement. The // EXEC statement without
should be
a program name in Figure 2.14 indicates that the just-compiled program
executed. The second /*' statement indicates the end of data for the program, and
the /&' statement indicates the end of the job.
A control statement is processed by the command processor component of the
analyses
batch processing kernel. The command processor reads a control statement,
that might lead to
it and carries out the required action. It also checks for situations user's
interference between jobs. At a// JOB statement, it verifies the validity of the
accounting information and initializes its own data bases to note that the processing
loading and execution
of anew job has started. At an // EXEC statement it organizes
of the appropriate program.
 56 Operating Systenms
// JOB
// EXEC PASCAL

Pawal
proyran

"Ld f data statICnt

Data for
Pascal
progran
, 'Endof data' staterneit
'End of job' statement
Fig. 2.14 Control statements in lM
360/370 sysem%

If a '/*' or '/2'statement is encountered during the cxeculion of a

thecommand prOcessor rcalizes that the program has reached the end of program,
its data. If
the program tries to read more data cards, it is terminated by
statemcnt.
skipping the '/u
to
Thecommand processor must proccss cach control
statement to implement these
functionalities. Toensure that the Commandproccssor sces cach control
user program is not permitcdto rcad cards directly. It must makea statement,a
nel to read acard. (This is done through a system request to the ker
call--sce Section
now reaches the command processor, which rcads the card and 2.1.2.2.) Control
card checks whether the
contains a Control statement. If so, thc command proceSsor
terminationof the job; otherwise, ít hands over the card to the userinitiates
program.
abnormal
2.5 MULTIPROGRAMMING SYSTEMS

Concurrency of operation between the CPUand the I/O subsystem (see Section 2.Il)
can be cxploitedto get more work donein the system. The OS can put
programs in thememory, and let the CPU execute instructions of one many user
the I/)subsystem is busy with an l/O operation for program while
iscalled multiprogramming. another program. This technique
Figure 2. 15 illustrates operation of a
tains three programs. An I/O operation is inmultiprogramming OS. The memory con
CXCCuling progran,. The CPUis switched toprogress for program1. while the CPUIs
program when program; initiates an
1/0operalion, and it is switched to program when
pletes. The multiprogramming kernel performs program 's I/O operation com
and I/0management. It uses a simple scheduling. memory management
scheduling
Section 2.5,3,1, and performs simple partitioned orpolicy, which we will discuss in
ory and I/0 devices. pool-based allocation of mem
(Scheduling, memory management and I/O management are
discussedin detail in Chapters 4, 5-6, and 7-12,
ure 2.12, cach program in the respectively.) As shown in Fig
memory could be a program in the current job of a
 Overview of Operating Systems 57

Multiprogramming
Kenel
Multiprogramming
Kernel
Multiprogramming
Kernel
|/O
Program| program CPU progran|

CPU program) /O program2 J/O programn2

progrann3 CPU ) progrann3 progran3

(a) (b) (c)

Fig. 2.15 Operation of a

multiprogramming system.
batch of jobs. Thus one could have both batch processing and multiprogramming at
the same time.
In principle the CPUand the I/O subsystem could operate on the same program.
However, in this case the program must explicitly synchronize activities of the CPU
and the I/O subsystem to ensure that the program executes corectly. Example 2.7
illustrates the need for synchronization.
Example 2.7 Consider the following program segment
Stmt no. Statement
1 read a;

5 b := a+5;

After initiating an VO operation to implement the read statement, the CPUcould

continue with execution of the program. However, the value of a should not be used
in the fifth statement before its reading is completed by the first statement! The CPU
and /O activities in the program are synchronized to ensure that this does not happen.
The multiprogramming arrangement ensures synchronization of the CPU and
JO activities in a simple manner--it allocates the CPU to a program only when the
program is not performing an VOoperation.

2.5.1 Architectural Support for Multiprogramming

A computer must possess the features summarized in Table 2.9 to support multi
programming (see Section 2.1.1). The DMA makes multiprogramming feasible by
permitting concurrent operation of the CPU and /O devices. Memory protection
prevents mutual interference between programs. The privileged mode of the CPU
provides a foolproof method of implementing memory protection and other mea
sures that avoid interference between programs. For example, instructions to load
addresses into the lower bound register (LBR) and upper bound register (UBR) of
the CPUare privileged instructions. If a program tries to change contents of the LBR
S8 Operating Systems

and UBR by using these instructions, a program interrupt would be raised becausa
the CPUis in the user mode while exceuting user programs; the kernel would abor
the program while servicing this interrup1.
Table 2.9 Architeural support for multiprogranning

Feature Description
DMA The CPUinitiates an I/O operation when an l/Oinstruc
tion is executed. The DMA implements the data transfer
involved in the l/O operation without involving the CPU,
and raises an l/O interrupt when the data transfer completes.
Memory protection Ensures that a program does not access or destroy contents
of memory areas occupied by other programs or the OS.
Privileged mode Certain instructions, called privileged instructions, can be
of CPU performed only when the CPUisin the privileged mode. A
program interrupt is raised if a program tries to execute a
privileged instruction when the CPU is in the user mode.
Since several programs are in memory at the same time, the instructions, data,
and VO operations of one program should be protected against interference by other
programs. It is achieved simply by putting the CPUin the user mode while executing
user programs.
2.5.2 User Service

In a multiprogramming system, the turn-around time of a job is affected by the

amount of CPU attention devoted to other jobs executing concurrently with it, so the
turn-around time of a job depends on the number of jobs in the system, and relative
priorities assigned to different jobs by the scheduler. As in a batch processing system,
the turn-around time of a job is not directly related to its own execution
The influence of priorities on user service is discussed in Section 2.5.3.1.
requirements.

2.5.3 Functions of the Multiprogramming Kernel

Important functions of the multiprogramming kernel are:
1. Scheduling
2. Memory management
3. /O management.

Scheduling is performed after servicing every interrupt (see Figure 2.8). Mul
liprogramming systems use a simple priority based scheduling scheme described in
the next Section. Functions 2 and 3 involve allocation of memory and I/O devices.
Simple partitioned or pool-based allocation can be used for this purpose. Resource
sharing necessitates protection against mutual interference--the instructions, datla,
and 1/Ooperations of one program should be protected against interference by other
59 hardware
pro programs.processing
memory to
throughput,over programs
CPU, andin anddiffer
based.
interrupt. than de following. be
Systems other taken activities
concepts eXe
in
programs
programs throughput
the computation lot
larger of priority in
memory pro in
CPU
tinme computa al it. preempted prog
bursts.
userits Interrupt
protection time on
several number VO-bound a use
always
Operating to outside an is be their the
involving
long
to and
allocated instructions the the small
executingcaused OS totalprocessesn may actual using
in a little wishesCPU. prog1
uses keeps usesfor isCPU is
multiprogramming in muchoverlapsufficient
techniques in CPU
situated the This and program CPU veryCPU the of
of Memory interrupt.
that activities It that
However,systemexecution OS The theuse mix Let
Overview memory and CPU-boundI/O.
while program that-to). executehow can the
Description
the involves
operation.the program
on to
locations processed a littleuses priority. m=2.
a that uses wishes proper
executing
this. mode an OS n/(tf because i.e.,kernel keeps and
multiprogramming is
very
with to mayoperations. their programs program it program
It priority
processed, concepts I/O
achieve the
leads multiprogramming
is system of andis, I/O, aassigned program a with
non-privileged
memory mix where
interfering
terminate a programs tr system program the overlaps an
bursts-that program keep
of computation of
CPU-bound starting
I/0-bound highest system
now at well user a lot
performance ends VO The these memory,
keeps prioritymust
to a isprogram
Every
used instruction,
access System processingbeing how and of before and thepriority OS multiprogram
from simply of and simultaneouslyoneperform a 2.10. discuss The
number
multiprogramming time.
any
at The
kernel long
andthroughput,
programs memory An tion to higher
numberatto in A of
are theto Multiprogramming a grams located
low an
program Table "
in program
provisions interrupts of of starts programs perform,
We a why
put privileged Throughputbatch A if
measure
the in in scheduling. see
is that of programs
thedescribed Concept/Technique
a CPU user of a nature
they in
multiprogramming To
prevent these ratio time of other optimize techniques preemptive
and
Priority-based a
Two mix consider
thea a appropriate throughput place I/O Program
mix
by use a the of
them. the of preemptive ofDegree scheduling Program
for of some much techniques
to andetfort
programs. to period
is process take on To kinds and
Performance
usedgrams,or routines which pends cution,
Anyarea, An maywhile howtime. ent Concepts
is thethe
2.10
2.5.3.1
Table
60 Operating Systems
programs are heavily
the two programs under processing. Let us assume that both
CPU-bound and prog1 is currently executing. Being CPU-bound. prog1 performs
along burst of CPUactivity before performing an /O operation. CPUis
given to
of
prog: when prog1 initiates an I/O operation. prog2 also perlorms a long burst
CPU activity before perfornming an l/Ooperation. prog1 would have finished its J/O
operation by this time, so it can use the CPU for another burst of compuation. In
this manner the CPU is kept busy most of the time. I remains idle only when both
programs simultancously perform I/O. The /O subsystem is underloaded. In fact.
it is idle most of the time because programs contain long CPUbursts, so periods of
concurrent CPUand /O activities are rare. Consequently, the throughput is low.
To analyze the throughput of this multiprogramming system, we will compare
it with a batch processing system processing the same two programs. The batch
processing system would service the programs one after another, i.e., either in the
sequence prog1. prog2 or in the sequence prog:. prog1. The throughput would be
identical in both cases. For comparing the throughput of the batch processing and
multiprogramming systems, we introduce the notion of progress of a program. A
program 'makes progress when either the CPU is executing its instructions or its
VOoperation is inprogress. Throughput would be higher if several programs make
progress concurrently.
In our example. progi and prog2 make progress concurrently only when one of
them performs I/O and the other executes on the CPU, ie., only when the CPUand
the VO subsystem execute concurrently. Such periods are rare, so periods when both
programs make progress are also rare. Consequently. throughput of the multipro
gramming system is likely to be much the same as the batch processing system.
A practical way to improve the throughput is to select amix of programs that
contains some CPU-bound programs and some I/O-bound programs. For example,
let a multiprogramming system with n=2contain the following programs:

progch CPU-bound program

progiob JO-bound program
progch Can keep the CPU occupied while progjob keeps the l/O subsystem busy. Thus,
both programs would make good progress, and the throughput would be
in a batch processing higher than
system.
Program priority We assume a simple implementation scheme in which each
program has a numeric priority where a larger value implies higher
priority.
Definition 2.5 (Priority) Priority is a tie-breaking notion used ina scheduler to
which request should be scheduled on the sever when many decide
requests await service.
When many programs are ready to use the CPU, the
gives the CPUto the program with the highest priority. Thismultiprogramming kernel
rule leads to preemption
 Overview of Operating Systems 61
of alow priority program when ahigh priority program
CPU. becomes ready to use the

Definition 2.6(Preemption) Preemption is the forced deallocation of the

programn. CPUfrom a
Example 2.8 illustrates how preemption takes place in a
muliprogramming system.
Example 2.8 In amultiprogramming system a high priority program is
pertorming an /O operation and a low priority engaged in
program
is in
in Example 2.3 and illustrated in Figure 2.9. when an execution. As discussed
interrupt occurs the CPU Is
SWitched to execution of the /O interrupt processing routine that has the start
bbb. After the interrupt processing actions, control is transferred to the address
scheduler,
which selects the high priority program for execution. Effectively, the low priority
program that was executing on the CPUhas been preempted.
Contrast Example 2.8 with Example 2.3 in the context of a
multiprogramming
system. In Example 2.3, itwas assumed that the program that was executing when an
interrupt occurred is scheduled again for execution. This assumption implies that the
VO operation whose completion was signaled by the interrupt must have belonged
to some lower priority program. The interrupted program still remains the highest
priority program that can use the CPU, so it is selected forexecution by the scheduler.
Assignment of program priorities The kernel of the multiprogramming system
has to assign priorities to programs. The program mixconsists of some CPU-bound
programs and some I/O-bound programs, so the kernel has to decide whether CPU
bound programs should have higher priority or whether /O-bound programs should
have higher priority. This is a crucial decision because it can influence system
throughput. The priority assignment rule in multiprogramming systems is as fol
lows:

" In multiprogramming systems I/O-bound programs should have higher priority

than CPU-bound programs.
To illustrate this rule, and its influence on system throughput, we considera multipro
gramming system containing progch and progiob. The CPU and /O activities of these
programs are plotted in the form of a timing chart in which the x-axis shows time
and the y-axis shows CPUand I/Oactivities of the two programs (see Figure 2.1l6).
We compare timing charts for different priority assignments toprosch and progiob:
To emphasize why /O-bound programs should have higher priority, we tirst discuss
how a system would perform poorly when a CPU-bound program is given a higher
priority.
Higher priority to CPU-bound programs Example 2.9 discusses features of sys
tem operation when CPU-bound programs have higher priority than 1/0-bound pro
grams.
62 Operating Systems

Example 2.9 The timing chart of Figure 2.16 depicts operation of the system when
prog¢b, the CPU bound program, has higher priority. Note that the chart is not to
scale. The CPU activity of progiob and the I/O activitiesof both programs have been
exaggerated for clarity.

CPUidle
CPU progiob
activity
proßcb

progiob
activity
progcb
|WOidle
0 I|| 12 t|3l14
time
Fig. 2.16 Timing chart when CPU-bound program has higher priority

progcb is the higher priority program, so it starts executing at time = 0. After a

long burst of CPU activity, it initiates an I/O operation (time instant ). The CPU is
now switched to progiob, the /O-bound program. Processing of progiob by the CPU
is thus concurrent with the I/O operation of progcb. progiob initiates an /O operation
soon, i.e., at i12. Two IO operations are now in progress, and the CPU will be idle
until one of them completes. Assuming proge's VO to finish earlier, it would start
executing on the CPU at t13. Completion of progiob's VO at I4 makes no difference
to the progress of progcb, which continues its executionsince it is the higher priority
program. Its CPU burst ends at time instant /1s when it initiates an /O operation. The
cycle of events of time interval j - s can now repeat. Note that the CPU is idle over
the intervals t12-13 and l6-17. Similarly the VO subsystem is idle over the intervals
I14-I15 and ij7-ti8.
From Example 2.9 one can make the following observations concerning system
operation when CPU-bound programs have higher priorities than VO-bound pro
grams:
1. CPUutilization is reasonable.
2. VO utilization is poor because the CPU-bound program monopolizes the CPU
and the IVO-bound program does not get an opportunity to execute.
3. Periods of concurrent CPUand /O activities are rare.

From observation 3 it is clear that most of the time only one of the two pro
grams is able to make progress, so the throughput is not much better than in a batch
processing system. Attempts to improve the throughput by increasing the degree of
multiprogramming meet with litle success. For example, let us increase the degree
 Overview of Operating Systems 63
of multiprogramming (n) to 3 and introduce a
ority between those of progch and progiab. ThisCPU-bound programprog3 with a pri
action improves the CPU utilization
since the new program can keep the CPU busy over
been idle if m was 2 (see interval t1p-a). However., itintervals where it would have
of the I/Outilization because prog,ob leads to further deterioration
receives
of an /0-bound program (say, proga) instead lesser opportunity to execute. Adoluon
of proga makes little difference to the
CPUand I/O utilization because progA Would have the lowest
get much opportunity to execute. priority, so it does not

CPUidle
CPU
progiob
activity |
progeb.

progiob
activity
progcb

VO idle
I22 I23
time

Fig. 2.17 Timing chart when O-bound program has higher priority

Higher priority to VO-bound programs Example 2.10 discusses features of system

operation when /O-bound programs have higher priority than CPU-bound programs.
Example 2.10 Figure 2.17 depicts the operation of the system when the VO-bound
program has higher priority. prog iob is the higher priority program, hence it is given the
CPUwhenever it needs, i.e., whenever it is not performing l/O. When progiob initiates
an /O operation, progcb gets the CPU. Being a CPU-bound program, progch keeps
the CPUbusy until progioh's IOcompletes. progch is preempted when progiob CoM
pletes its I/O since progiob has a higher priority than progcb. This explains the system
behavior in the period 0-t26. Deviations from this behavior occur when progch initi
ates an VOoperation. Now both programs are engaged in I/O and the CPU remains
idle until one of them completes its I/O. This explains the CPU-idle periods (z6-t7
and t28-tg. VO-idle periods occur whenever prog iob executes on the CPU and progcb
is not performing /O (see intervals l22-)3 and t24-l2s).
From Example 2. 10,one can make the following observations concerning system
operation when /O-bound programs have higher priorities:
1. CPUutilization is reasonable.
2. VOutilization is reasonable (however, VO idling would exist if system contains
many devices capable of operating in the DMA mode),
64 Operating Systems

3. Periods of concurrent CPU and I/O activities are frequent.

progioh Makes good progress since it is the highest priority program. It makes
light use of the CPU, so progb also makes good progress. The throughput is thus
substantially higher than in the batch processing system. Another important featurc
of this priority assignment is that system throughput can be improved by adding more
programs. Table 2.11shows how this can be achieved. Hence onecan conclude that
assignment of higher priorities to l/0-bound programs leads to good throughput. It
also enables the OS to combat poor throughput in the system by increasing the degree
of multiprogramming.
Table 2.11 Improving throughput in a multiprogramming system

Add a A CPU-bound program (say, prog:) can be introduced to utilize

CPU-bound some CPUtime that is wasted in Example 2.10 (e.g. the intervals
program I26027 and I28-29). prog: would have the lowest priority. Hence its
presence would not affect the progress made by progh and pro8iob
Add an An /O-bound program (say, prog4) can be introduced. Its priority
VO-bound would be between the priorities of progiob and progecb. Presence of
program prog4 would improve I/O utilization. It would also not affect the
progressof progcb very much since prog4 does not use a significant
amount of CPU time,

Degree of multiprogramming When a proper program mix is maintained, an

increase in the degree of multiprogramming, m, would result in an increase in
throughput. Memory capacity and the average memory requirements of user pro
grams determine practical values of m. Figure 2.18 shows how the throughput of a
system varies with the degree of multiprogramming.

Throvghput

1 3

Degree of multiprogramming
Fig. 2.18 Variation of throughput with degree of
multiprogramming
When m= 1,the throughput is dictated by the elapsed time of the lone program
 Overview of Operating Systems 65

in he system. At higher values of n, lower priority programs also contribute to

throughput. However their contribution is limited by their opportunity to use the
CPU. Throughput stagnates with increasing values of m if low priority programs do
not get any opportunity to execute.
26 TIME SHARING SYSTEMS

In a non-interactive computing environment, a user has no contact with his program

during its execution. In such an environment it is natural to use the batch process
ing or multiprogramming paradigm. Both these systems provide poor user service.
However, this is inevitable due to the nature of I/Odevices in use.
In an interactive computing environment, a user can provide inputs to a program
from the keyboard and examine its output on the monitor screen. A different OS
paradigm is used in such environments to provide quick service to user requests; it
creates an illusion that each user has a computer system at his sole disposal. This
paradigm is called time sharing.
2.6.1 User Service

User service is characterized in terms of the time taken to service a subrequest, 1.e.,
the response time (rt). Benefits of good response times are best seen during program
development. Auser engaged in program development compiles and tests a program
repeatedly. Atypical request issued by the user concerns compilation of a statement
or an execution of a program on given data. The response consists of a message from
the compiler or results computed by a program. Auser issues the next request after
receiving the response to the previous request. Good response times would lead to an
improvement in the productivity of the user. Any application in which a user has to
interact with a computation would derive similar benefits from good response times.
Emphasis on good response times, rather than on efficient use or throughput,
requires use of new design principles and techniques. The notion of a job is no
longer relevant, an interactive user interface has to be designed, and new scheduling
and memory management techniques are needed to provide good response times to
a large number of users. These changes are discussed in the following Sections.

2.6.2 Scheduling
User service in a time sharing system is characterized by response times to user
requests, so the time sharing kernel must provide good response times to all users. To
realize this goal all users must get an equal opportunity to present their computational
requests and have them serviced. Each user must also receive reasonable service.
Two provisions are made to ensure this.
1. Programs are not assigned priorities because assignment of priorities may deny
oS attention to low priority programs. Instead, programs are executed by turn.
 66 Operating Systems
amounts of CPUtime
2. Aprogram is preventcd from consuming unreasonable will
when scheduled to exccute. This provision ensures that every request
receive OS attention without unreasonable delays.
These provisions are implemented using the techniques of round-rob1n scheduling
and time slicing, respectively.
Round-robin scheduling When a user makes a computational request to his pro
gram, the program is added to the end of a scheduling list. The scheduler always
removes the first program from the scheduling list and gives the CPU to it. When
aprogram hnishes computing its response to a request, it is removed from the CPU
and the first program in the new list is selected for execution. When the user makes
another request, the program is once again added to the end of the scheduling list.

Time slicing The notion of a time slice is used to prevent monopolization of the
CPUby a program.
Definition 2.7 (Tme slice) The time slice is the largest amount of CPUtime any
program can consume when scheduled to execute on the CPU.
Time slicing is an implementation of the notion of a time slice. Every program is
subjected to the time limit specified by the time slice. A program exceeding this limit
is preempted. Figure 2.19 illustrates a schematic of round-robin scheduling with time
slicing. Apreempted program is added to the end of the scheduling list. A program
may be scheduled and preempted a few times before it produces a response.
Preempted program
time slice
Over

Scheduler CPU

Scheduling Selected Computation

Over
list program
Fig, 2.19 Aschematicof round-robin
scheduling with time slicing
The time sharing kernel uses the interval timer of the
computer to implement time
slicing. The interval timer consists of a register called timer
an integer number representing a time interval in register that can store
hours, minutes and seconds. The
Contents of the register are decremented with an
few times every second. A timer interrupt is appropriate periodicity, typically a
raised when the contents of the timner
register become zero, that is, when the time interval
Atime sharing OS uses round-robin elapses.
shows actions of the time sharing kernel.scheduling withtime slicing. Algorithm 2.I
 Overview of Operating Systems 67
Algorithm 2.1 (Time slicing)
1. Select the first progranm in the scheduling list for
execution. Let the selected
program be P. Remove P from the scheduling list.
2. Load the value of the time slice (6)
into the interval timer.
3. Start execution of program P on the
CPU.
4. If P initiates an I/O operation, goto step 1 to
execution.
schedule another program Tor
J. When a timer interrupt occurs. preempt P and add it at the end of the schedul
ing list. Go to step 1.

In Step Sthe preempted program is put at the end of the scheduling list. If a
program does not consume ðseconds of CPUtime, e.g., if it starts an VOoperation,
the kernel simply schedules the next program. When an I/O completion interrupt is
raised the kernel identifies the program whose VO operation has completed and adds
the program at the end of the scheduling list.

Example 2.11 Figure 2.20 illustrates operation of Algorithm 2.1 in a time sharing
system using time slice . It is assumed that scheduling overhead of the OS is o
seconds. Figure 2.20(a) depicts the situation when the time slice elapses during exe
cution of a program. The kernel preempts this program and schedules another pro
gram for execution. The new program therefore starts executing o seconds after the
time slice elapses. In Figure 2.20(b), the program executing on the CPU makes an
VO request. After starting the VO operation, the kernel schedules another program
for execution. If we ignore the 0S overhead in initiating an I/O operation, the newly
scheduled program starts executing Gseconds after the VO request was made.
Program is Program is Program is Program is
scheduled scheduled scheduled scheduled

Time slice /O operation

elapses is started

(a) (b)

Fig. 2.20 Operation of atime slicing scheduler

for
When round-robin scheduling with time slicing is used, the response timeusers
manner: Let the number of
each user request can be estimated in the following
require exactly § CPU
using the system at any time be n. Let each user request in switch
seconds for completion. As in Example 2.11, leto be the CPUtime spent an WO
If we assume that
ing from execution of one program to the next program. immediately
request
operation completes instantaneously and a user submits the next
68 Operating Systems

after recciving response to theprevious request, the response time fr ) and the CPU
efticiency () are given by
n.(8+o) (2.2)

(2.3)
The actual response time may be different from the value ofr predicted by Eg.
(2.2). There are several reasons for this. First, the value of rt may bc smaller than
that predicted by Eq. (2.2) because all users may not have made requests to their
programs. Hence rt would not be influenced by n, the total number of users in the
system; it would be influenced by the number of active users (a), ng K n. Second,
user requests do not require exactlyÓ CPæ seconds to produce a response, so the
relationship of rt and n with Õ
is more complex than shown in Eqs. (2.2) and (2.3).
Table 2.12 summarizes the effect of small or large values ofð. Fromn this one can
conclude that rt may not be small for small ð and n may not be large for large ò,
which makes the choice of Ó a sensitive design decision.
Table 2.12 Influence ofð on response time

Value of S Influence on response time

Ò
very small Value ofÓ may become smaller than the CPUtime needed to satisfy
a computational request. Such a program would have to be sched
uled a few times before it can produce a response. Hence
response
time would be larger than n X (ð+¡) seconds. Also, magnitudes
of ð and o may be comparable, which leads to low values of n from
Eq. (2.3). Cache memory performance may also be poorer (see
Section 2.1.1).
S large Most user requests may be processed in less than ¿ CPUseconds.
Thus most programs release the CPU before Óseconds (see Step 4
of Algorithm 2.1). Hence rt< ng x (Ò+o) andn is worse than the
value predicted by Eq. (2.3).

Example 2.12 Figure 2.21 shows operation of a time sharing

grams P and P2 in it. Parts (a) and (b) show execution of the system all by
with two pro
programs
selves. Both programs have acyclic behavior, each cycle containing a burst ofthem
CPU
activity followed by a burst of I/O activity. The CPUbursts of programs P and P2 are
15and 30 msec, respectively, while the /O bursts are 100 and 60 msec,
When eXecuted by themselves, the programs have response times of115 respectively.
msec and
90 msec, respectively, since a programmer sees the results of a computation on the
monitor at the end of an /O operation.
Part (c) shows execution of the programs in a time sharing system using a time sl1ce or
10msec. Programs P and P> nowget CPUbursts limited to 10 msec. Both programs
have to be scheduled a few times before they can complete the CPU bursts of their
execution cycle and start LVO. Thus P starts an /O operation at 25 msec from start
 Overview of Operating Systems 69

CPU
(a)
/O

50 100 150 200

(b)
CPU P)
I/O

50 100 150 200

CPU P
P2
(c) VO P
P2
50 100 150 200
time
Fig. 2.21 Execution of programs P and P by themselves, and together

Table 2.13 Time sharing scheduling

Time Scheduling Scheduled Remarks

list program

{Pi,P2} P; P is preempted at 10 msec

10 {P2.P1} Pa P2 is preempted at 20 msec
20 {Pi,P2} P P1 starts I/O at 25 msec
25 {P2} P2 P> is preempted at 35 msec
35 {P2} P2 PT starts I/O at 45 msec
45 CPUis idle
105 {P2} P2 P2 is preempted at 115 msec
115 {P2} P2 P2 is preempted at 125 msec
125 {P,.P2} Pi P is preempted at 135 msec

of operation of the system. Now P2 gets two consecutive time slices (separated, of
course, by OS overhead for actions that first preempt program P and then schedule
it again because no other program in the system needs the CPU). P's VO operation
completes at 125 msec. P2 starts an I/Ooperation at 45 msec, which completes at 105
msec. Thus, the response times are 125 msec and 105 msec, respectively. Table 2.13
shows the scheduling list and scheduling decisions of the kernel between 0 and 105
msec assuming scheduling overhead to be negligible.
 70 Operating Systems
2.6.3 Memory Management
In Example 2.12, the CPU was idle between 45 msec and 105 msec, so the sveters
can service a few more user programs. However:, the computer system
must poSseSs a
large memory to accommodate all these programs, which is an expensive proposition
The technique of swapping provides an alternative whereby acomputer system can
Supporta large number of users without having topossess a large memory.
Definition 2.8 (Swapping) Swapping is the technique of temporarily emoving
inactive programs from the memory of a computer system.
An inactive program is one which is neither executing on the CPU, nor perform
ing an I/Ooperation. Figure 2.22 illustrates swapping as used in a practical situation.
The programs existing in the memory are classified into three categories:
1. Active programs-one active program executes on the CPU while others
perform VO.
2. Programs being swapped out of the memory.
3. Programs being swapped into the memory.
Kernel
Programs being
swapped out
Program in Swapped out
execution
programs
Programs being
swapped in

Fig, 2.22 A schematic of swapping

Whenever an active program becomes inactive, the OS swaps it out by

instructions and data onto a disk. A new program is loaded in its place.copying itS
The new
program is added at the end of the scheduling list; it receives CPU
COurse. attention in due
Use of swapping is feasible in time sharing
systems because the time sharing
kernel can estimate when a program is likely to be
scheduled next. It can use this
estimate to ensure that the program is swapped in before its turn on the CPU. Note
that swapping increases the OS overhead due to the disk I/O
involved.
2.7 REAL TIME OPERATING SYSTEMS
In aclass of applications called real time
applications, users need computer to
perform some actions in atimely manner to control the activities in the
an external sys
tem, or to participate in them. The timeliness of actions is
determined by the time
 Overview of Operating Systems 71

constraints of the external system. Accordingly, we detine a rcal time application as

follows:

Definition 2.9 (Real time application) Areal time application is a program that
responds to activities in an external system within amnaxinum time determined by
the external system.
If the application takes too long to respond to an activity, a failure can occur in
the externalsystem. We use the termresponse requirement of a system to indicate the
largest value of response time for which the system can function perfectly; a timely
response isone whose response time is smaller than the response requirement of the
system.
Consider a system that logs data received from asatellite remote sensor. The
satellite sends digitized samples to the earth station at the rate of 10000 samples
per second. The application process is required to simply store these samples in a
file. Since anew sample arrives every 100 microseconds, the computer must respond
of a
to every "store the sample" request in less than 100 microseconds, or arrival
new sample would wipe out the previous sample in the computer's memory. This
less than 100
system 1S areal time application because asample must be stored in
microseconds to prevent a failure. Its response requirement is 99,9 microseconds.
the action
The deadline of an action in a real time application is the time by which
should be performed. In the above example, if a new samplemicroseconds.is received from the
satellite at time t, the deadline for storing it on disk ist +99.9
command
Examples of real time applications can be found in missile guidance, sampling
traffic control, data
and control applications like process control and air
in automobiles, multimedia sys
and data acquisition systems like display systems systems that are based on use
banking
tems, and applications like reservations and
requirements of these systems vary from a few
of real time data bases. The response systems to a few seconds for
microseconds or milliseconds for guidance and control
reservations and banking systems.
2.7.1 Hard and Soft Real Time Systems
maximum
advantage of the features of real time systems while achieving
To take have evolved. Ahard real time
cost-effectiveness, two kinds of real time systems provably meets
processing real time applications, and
system is typically dedicated to application under all conditions. Asoftreal time sys
an
the response requirement of meet time application
theresponserequirement of a real
tem makes the best effort to able to meet it under all conditions. Typically, it
will be
but cannot guarantee that it some probabilistic manner, say, 98 percent
of the
requirements in time
meets the response
control applications fail if they cannot meet the response
time. Guidance and Appli
they are typically serviced using hard real time systems.
applications
requirement,hence quality of service, e.g., multimedia failure. so
cations that aim at providing good
have a notion of
applications like reservations and banking, do not
and
72 Operating Systems

they may be serviced using soft real time systems-the picture quality provided bw
a video on demand system may deteriorate occasionally, but one can still watch tha
video!

2.7.2 Features of a Real Time Operating System

Areal time OS provides the special fcatures summarized in Table 2.14, Areal
time application can be coded such that thc 0S can execute its parts concurrently
When priority-based scheduling is used, we have a situation analogous to multi
programming within the application--if one part of the application initiates an /O
operation, the OS would schedule another part of the application. Thus, CPUand
I/O activities of the application can be overlapped with one another, which helps to
reduce the worst-case response time to the application. Deadline scheduling is a spe
cial scheduling technique that helps an application meet its deadline. Some aspects
of deadline scheduling are described later in Section 4.2.
Table 2.14 Features of a real time operating system
(RTOS)

1. Permits creation of multiple processes within an

2. Permits priorities to be assigned to application
processes
3. Permits a programner to define interrupts and interrupt
4. Uses priority driven or deadline oriented scheduling processing routines
5. Provides fault tolerance and graceful degradation
capabilities.
Specification of domain specific interrupts and interrupt servicing actions for
them enables a real time application to respond to special conditions and events in the
external system in a timely manner. Predictabilityof policies and overhead of the OS
enables an application developer to calculate the worst-case response time that
OScan provide and determine whether it can meet the the
response requirements of the
application. When resources are overloaded, OS overhead can become unbounded.
i.e., arbitrarily large. For example, if memory utilization is very
allocator may take long to find a free memory area to meet amemory
high the memory
hard real time OS must avoid such situations. Hard real time request. A
tion their resources (see Section 1.3.2) and allocate them
systems therefore parti
permanently to
processes in the application. This approach reduces the allocation overheadcompeting
and guar
antees thatthe kernel response for a resource request made by one process
would be
independent of resource utilization byother processes in the system. Hard real time
systems also avoid use of features whose performance cannot be predicted precisely,
e.g. virtual memory (see Chapter 6).
A real time OS employs two techniques to ensure continuity of operation when
faults occurfault tolerance, and graceful degradation. Afault tolerant computer
system uses redundancy of resources to ensure that the system will keep functioning
even if a fault occurs, e.g., it may have two disks even though the application actually
 Overview of Operating Systems 73
nceds only one disk. Graceful degradation is the ability of a system to all
back O d
reduced level of service when a fault occurs and to revert to normal operations
the lault is rectified. The programmer can assign high priorities to crucial Wnen
so that they would be performed in atimely manner even functions
when the system operates
in a degraded mode.

28 DISTRIBUTEDOPERATING SYSTEMS
A distributed computer system consists of several individual computer systems Con
nected through anetwork. Thus, many resources of a kind, e.g.., many memories,
CPUs and I/Odevices, exist in the distributed system. Adistributed operating sys
tem explots the multiplicity of resources and the presence of a network to provide
the advantages of resource sharing across computers, reliability of operation, speed
up of applications, and communication between users. However, the possibility of
network failures or failures of individual computer systems complicates functioning
of the operating system and necessitates use of special techniques in its design. Users
also need to use special techniques to access resources over the network. We discuss
these aspects in Section 2.8.1.
Table 2.15 Features of distributed operating systems

Feature Description/Implication
Resource sharing Improves resource utilization across boundaries of
individual computer systems.
Reliability Availability of resources and services despite failures.
Computation speed-up Parts of a computation can be executed in different
computer systems to speed-up the computation.
Communication Provides means of communication between remote
entities.
Incremental growth Capabilities of a system (e.g., its processing power)
can be enhanced at a price proportional to the nature
and size of the enhancement.

systems. Resource
Table 2.15 summarizes advantages of distributed operating
operating systems. The
sharing has been the traditional motivation for distributed operating system,
earliest form of a distributed operating system was a network
resources by geograph
which enabled the use of specialized hardware and softwareimportant aspect of dis
to be an
ically distant users. Resource sharing continues
of disribution and sharing of
tributed operating systems today, although the nature technology. Sharing of
networking
resources has changed due to advances in the
equally meaningful in a local area network (LAN), Thus. low-cost
resources is now
laboratory can share some expensive
computers and workstations in an office or a
resources like laser printers.
aspect of reliability is availab1lity of a resource despite failures in a sys
One
 74 Operating Systems

tem. Adistributed environment can offer enhanced availability of resources throueh

redundancy of resources and communication paths. For example, availability of a
disk resource can be increased by having two or moredisks located at different sites
in the system. Ifone disk is unavailable duc to a failure, a process can use some
other disk. Availability of adata resource, c.g., a file, can be similarly enhanced by
keeping copies of the tile in various parts of he systen.
Computation speed-up implies oblaining better response times or turnaround
times for an application. This is achieved by dispersing processes of an applica
tion to different computers in the distributed system, so that they can execute at the
same time. This arrangement is qualitatively different from the overlapped operation
of processes of an application in aconventional operating system (see Section 2.7).
Users of a dis1ributed operating system have user ids andpasswords that are valid
throughout the system. This feature greatly facilitates communication between users
in two ways. First, communication through user ids automatically invokes the secu
rity mechanisms of the OS and thus ensures authenticity of communication. Second,
users can be mobile within the distributed system and still be able to communicate
with other users of the system conveniently.
2.8.1 Special Techniques of Distributed Operating Systems
A distributed system is more than a mere collection of computers
connected to a
networkfunctioning of individual computers must be integrated to achieve effec
tive utilization of the services and resources in the system in the manner
summarized
in Table 2.15. This is achieved through
participation of all computers in the control
functions of the operating system. Accordingly, we define a distributed system as
follows:

Definition 2.10 (Distributed System) A distributed system is a system consisting of

two or more nodes, where each node is a computer systen wvith its
Own menory,
some networking hardware, and acapability ofperforming some of the control func
tions of an OS.
The control functions performed by individual computer systems
contribute to
effective utilization of the distributed system. Table 2.16 summarizes three key con
cepts and techniques used in adistributed OS.Distributed control is the opposite of
centralized controlit implies that the control functions of the distributed system are
performed by several computers in the system in the manner of Def. 2.10, instead of
being performed by a single computer. Distributed control is essential for ensuring
that failure of a single computer, or a group of computers, does not halt
the entire system. Transparency of a resource or service implies that a operation
ol
user should
be able to access it without having to know which node in the distributed system
contains it. This feature enables the OS to change the position of asofware resOuree
or service to optimize its use by computations. For example, in a system
providing
 Overview of Operating Systems 75

bahle 2.16 KeyOnCepts lmd techhiques ned in a disttibuted OS

'Technique Description
Disributed control A conrolfunction is performed through participation of sev
eralnodes, possibly all nodes, in a distributed system.
Transparency A resource or service can be accessed without having to
know its location in the distributed system.
Remote procedure Aprocess calls aprocedure that is located in a different com
call (RPC) puter system. The procedure call is analogous to a procedure
or function callin a programming language, except that It is
the OS that passes parameters to the remote procedure and
relurns its results. Operation of the process making the call
is resumed when results are returned to it.

ransparency, a distributed file system may move a file to the node that contains a
computation using the file, so that the delays involved in accessing the file over the
network would be eliminated. The remote procedure call (RPC) is used by an The
ap
plication to execute a procedure in another computer in the distributed system.
remote procedure may perform a part of the computation in the application, or it may
use a resource located in that computer.

2.9 MODERN OPERATING SYSTEMS

environment. Hence a
Users engage in diverse activities in amodern computing
for all processes; it must use
modern operating system cannot use a unitorm strategy
process.. For example, a user may
astrategy that is appropriate for each individual programs, and watch a video at
some
open a mail handler, edit afew fhles, execute be interactive, and may involve an
program may
the samne time. Here, execution of a
system, and watching of a video
activity in another node of a distributed computer round-robin scheduling for program
time activity, so the OS must use
is a soft real processes of the video application, and
executions, use priority-based scheduling for
node. Thus,
remote procedure calls (RPC) to support activities in another connection
implement discussed in
uses most concepts and techniques that we
time sharing, real time and distributed
a modern OS
processing, multiprogramming,
with the batch and techniques.
systems. Table 2.17 contains a summary of such concepts
operating mod
different strategies for different kinds of processes, so a
AnOS cannot use strategy that adapts its working to suit each
single complex
ern OS actually uses a the scheduling strategy may be priority-based, how
individual process. For example, sys
assigning a fixed priority to a process as in a multiprogramming decide
ever insteadof process to
scheduling strategy might consider the recent behavior ofa priority, all inter
lem, the
priority. This way, a real time process would get a high processes would
its current amoderate priority, and
non-interactive
active processes would get