DEPARTMENT OF COMPUTER APPLICATION

STAFF NAME :
CLASS : III BCA
SUBJECT : OPERATING SYSTEMS
SUBJECT CODE :

Title of the Operating Systems

Course/ Paper
Core -6 First Year & Second Credit: 4
Semester
Objective of This course introduces the fundamental concepts of operating
the course Systems with case studied on Unix and Windows.
Course UNIT-1
outline Introduction: Views - Types of System - OS Structure – Operations -
Services – Interface- System Calls- System Structure - System Design
and Implementation. Process Management: Process - Process
Scheduling - Inter-process Communication. CPU Scheduling: CPU
Schedulers - Scheduling Criteria - Scheduling Algorithms
UNIT-2
Process Synchronization: Critical- Section Problem - Synchronization
Hardware Semaphores - Classical Problems of Synchronization -
Monitors. Deadlocks: Characterization - Methods for Handling
Deadlocks - Deadlock Prevention - Avoidance - Detection - Recovery.
UNIT-3
Memory Management: Hardware - Address Binding – Address Space -
Dynamic Loading and Linking – Swapping –Contiguous Allocation -
Segmentation - Paging – Structure of the Page Table.
UNIT-4
Virtual Memory Management: Demand Paging - Page Replacement
Algorithms - Thrashing. File System: File Concept -. Access Methods -
Directory and Disk Structure - Protection - File System Structures -
Allocation Methods - Free Space Management
UNIT-5
I/O Systems: Overview - I/O Hardware - Application I/O Interface -
Kernel I/O Subsystem - Transforming 1/0 Requests to Hardware
Operations - Performance. System Protection: Goals - Domain -
Access matrix. System Security: The Security Problem - Threats –
Encryption- User Authentication.

1
1. Recommended Texts
th
(i) A. Silberschatz P.B. Galvin, Gange, 2002, Operating System Concepts, 6
Edn., AddisonWesley Publishing Co., Boston.

OPERATING SYSTEMS
UNIT – 1

OPERATING SYSTEM

Operating system is a set of programs which is interface between User

and Computer Hardware.

User OS Hardware

It is used to manage the activities of the computer system and allocates

the resources to user.
Resources(CPU, memory and I/O devices)

User User User User

1 2 3 n

Compiler Text editor Web Browser Database

System and Application Programs

Operating System

Computer
Hardware

2
VIEWS OF AN OPERATING SYSTEMS

The Operating Systems can be viewed the following ways.

[Link] View
[Link] View

User /programmer point of view :

PC consisting of monitor, keyboard, mouse and system unit. Such a

system is designed for one user to monopolize its resources, to
maximize the work that the user is performing.
Operating system is ease of use, but doesn’t assure the performance is
always good.
Low capacity system works very slow.
User connected to mainframe or minicomputer. Other users are
accessing the same computer through terminals.
These users share resources and exchange information.
The Operating System is designed to maximize resource utilization, to
assure that all available CPU time, memory and I/O are used efficiently.
Other users sit at workstations, connected to networks of other
workstations and server.
Many varieties of computers come into fashion, used singly by
individual users.
Some are connected to networks either by wire or wireless modems.

3
System point of view :

Operating system is the program that is most intimate with the

hardware.
Resources (CPU time, memory, IO devices, etc) need to be managed.
OS as a resource allocator.
A computer system has many resources – hardware and software,
that may be required to solve a problem: CPU time, memory
space, file storage space, I/O devices and so on.
OS decides how to allocate them to specific programs.
OS is a Control Program.
A control program manages the execution of user program to
prevent errors and improper use of computers.
The storage requirements and features may vary across systems.
The storage capacity of a system is measured in gigabytes.

GOALS OF AN OPERATING SYSTEMS

There are two types of goals.

a. Primary Goals
Convenient to use
Easy to Learn
Easy to Use.
Reliable.
Safe and Fast.
b. Secondary Goals

Use the computer hardware in an efficient manner.

TYPES OF SYSTEMS
4
The OS can be classifieds into several types. They are explained below.

i. Simple Batched Systems.

● The I/P devices are Card readers and Tape drives

● The O/P devices are line printers, tape drives and card punches.
● User did not interact with computer systems.
● The Os was fairly simple.
● Its major task was transfer the control automatically from one job to
another.
● The OS was always in Physical memory.

OS

User
Program
Area

● To speedup processing, jobs with similar needs were batched

together and were run through the computer as
a group.
● It has lack of interaction between Computer and User.
● The CPU becomes idle.
● The introduction of disk technology has helped for the above
problem.
● The Simultaneously Peripheral Operation On-Line(SPOOLing) is use

5
 the disk as a huge before for reading and writing.
● Spooling is also used for processing data at remote sites (ex:
Printer)
● Spooling Overlaps the I/O of one job with computation of other jobs.
● Spooling increases performance of the system.

ii. Multiprogrammed Batched Systems.

● Spooling provides an important data structure is called JOB SPOOL.
● Multiprogramming means more than one jobs executed
simultaneously by OS.
● The Physical memory is divided into several partitions.
● Any one of the partition is taken by OS.
● The remaining partitions are hold by the Jobs.
● Any one job is taken by the CPU for processing if there is any I/O
requirement then the job is suspended and the
next is executed and vice versa.
● If several jobs are ready to be brought into memory, but there is not
enough room for all of them then the OS must
choose among them, this decision making is
called JOB SCHEDULING.
OS
Job1
Job2

.
.
.

6
 Job n

● If several jobs are ready to run at the same time, the system must
choose among them, this decision making is
called CPU SCHEDULING.
● Here throughput is increased.
● The User cannot interact while running a program.

iii. Time Sharing or Multi tasking Systems.

● Time sharing system is the logical extension of Multiprogramming
where the long turn around time is affect or
decrease the waiting time of the other jobs.
● Multiple jobs are executed by the CPU switching between them; but
the switches occurs so frequently that the user
may interact with each program while it is
running.
● An interactive or hands-on computer system provides on-line
communication between the User and the
System.
● The users are able to access both data and code conveniently.
● It allows many users to share the computer simultaneously.
● It is more complex then Multiprogramming.
● It requires some form of memory management and protection and
is achieved by Virtual memory techniques.
● It is also provide an environment for concurrent execution.

iv. Distributed or Loosely coupled Systems

● A recent trend in computer system is to distribute computation

7
 among several processors
● Each processor has its own local memory.
● These processors communicate with one another through various
communication lines, such as High-speed
buses or telephone lines.
● The processors may vary in size and function.
● This may include small microprocessor, workstation, mini
computers and large general purpose computer
systems.
● These processors are referred by different names such as sites,
nodes, and computers and so on.
● There are some reasons for building Distributed Systems. They are
given below.
Resource Sharing
Computation Speedup
Reliability
Communication

v. Real Time Systems.

● Special purpose OS.
● It is used when rigid time requirements on the operation of a
processor or the flow of data.
● It is also used to control device in a dedicated application.
● It is used in the following environments.
Scientific experiments
Medical imaging systems.
Industrial control systems.

8
 Some display systems.
Automobile-engine fuel-injection systems.
Home appliance controllers.
Weapon system.
● The real time OS has well-defined, fixed time constraints.
● Processing must be done within the defined constraints or the
system will fail.
● There are two types of real time OS.
1. Hard real time OS guaranties that the critical tasks complete on
time.
2. Soft real time OS, the critical task gets priority over other tasks, and
retains the priority until it completes.
vi. Parallel or Multiprocessor or Tightly coupled Systems.
● It has more than one processor in close communication.
● Sharing the computer bus, the clock, memory and peripheral
devices.
● We are using shared memory for all
● The Reasons for building parallel system are given below.
Speedup.
Resource sharing
Increase reliability
● It has two types.
1. Symmetric Multiprocessing
● Most commonly used Multiprocessing OS.
● Each processor runs on identical copy of the OS.
● These copies communicate with one another as needed.
2. Asymmetric Multiprocessing.
9
 ● Each processor is assigned a specific task.
● A Master processor controls the system.
● The other processor either look to the master for instruction or
have predefined tasks.
● The master processor schedules and allocates work to the
Slave processors.

OPERATING SYSTEM STRUCTURE (SYSTEM COMPONENT)

An OS is large and complex.

It is created only by partitioning it into smaller pieces.
Each piece should be well defined portion of the system with carefully
defined inputs and outputs and functions.
All system not has the same structure.
Many of the modern OS are supporting the following system
components.
1. Process Management
●A process is a program in execution.
●The OS is responsible for the following activities in connection with
process management.
Creation and deletion of user and system processes.
Suspension and resumption of processes.
A mechanism for process synchronization
A mechanism for process communication
A mechanism for deadlock handling.
2. Memory management
●A main memory is a large array of words of bytes has its own

10
 address.
●It is a repository of quickly accessible data shared by the CPU & I/O
devices.
●The OS is responsible for the following activities in connection with
memory management
Keep track of which part of memory are currently being used
and by whom.
Decide which process is loaded into memory when memory
space becomes available.
Allocate and deallocate memory space as needed.
3. File Management
●A file is a collection of related information defined by creator.
●The OS is responsible for the following activities in connection with
memory management
The creation and deletion of files.
The creation and deletion of directories.
The support of primitives for manipulating files and directories.
The mapping of files onto secondary storage.
The back up of files on stable storage media.
4. I/O Management
●The OS is to hide the peculiarities of specific hardware device from
user.
●The I/O subsystem consists of the following.
A memory management component that includes Buffering,
Caching and Spooling.
A general device driver interface
Drivers for specific H/W devices.
11
5. Secondary – Storage Management
●The secondary storage is a backup of primary memory.
●The OS is responsible for the following activities in connection with
secondary storage management
Managing the free space available on the secondary-storage
device.
Allocation of storage space when new files have to be written.
Scheduling the requests for memory access.
6. Networking
●The number of computers interconnected together is called a
network.
●The network may be fully or partially connected.
●The design must consider the message routing and connection
strategies and the problems of connections and security.
7. Protection System
●Protection is any mechanism for controlling the access of
programs, processes or users to the resources defined by a
computer system.
●Protection can improve reliability by detecting errors at the
interfaces between component systems.
8. Command-Interpreter System
●It is one of the most important program for an OS.
●It is an interface between user and OS.
●Some OS includes it in the Kernel.
●Other OS (MS-DOS), UNIX) treat it as a special program.
●It is also sometimes called as control-card interpreter or shell.

12
 OPERATING SYSTEM SERVICES
● An OS provides an environment for the execution of
programs.
● The Os provides certain services to programs and to
the users of those programs.
● These services are differing from one OS to another.
● But, there are some common services that we can
identify.
● These services are provided for the convenience of
the programmer, to make the programming task
easier.
1. Program Execution
● The OS must be able to LOAD a program into memory and run it.
● The program must be ending its execution either normally or
abnormally.
2. I/O operations.
● A running program may require I/O.
● This may involve a file or an I/O device.
● User cannot control I/O devices directly.
● The OS must provide some means of I/O.
3. File-System Manipulations.
● The files are created and deleted by OS using its names
● The file system should be read and write for programs.
4. Communication
● One process needs to exchange information with another process.
● There are two major ways for communication.

13
 Communication between processes executing on the same
computer.
Communication between processes executing on the different
computers that are tied together by a network.
● Communication may be implemented via shared memory or
message passing by OS.
5. Error detection
● The OS must be aware of possible errors.
● Errors may be occurring on CPU, memory, I/O devices or user
program.
(Ex. Memory error, power failure, connection failure on network,
lock of paper, arithmetic overflow)
● For each type of error the OS should take an appropriate action to
ensure correct.
6. Resource Allocation.
● When there are multiple users or multiple jobs running at the same
time, resources must be allocated to each of them.
● The OS is must be allocated the resources properly.
7. Accounting
● The OS is to keep track of which users use how much and what kind
of computer resources.

8. Protection
● Protection involves ensuring that all access to system resources is
controlled.
● Security means each user having to authenticate himself or herself
to the system.
14
 SYSTEM CALL

It provides the interface between a process and the operating system.

These are usually available in assembly language instructions.

[Link] CONTROL
Create, Terminate process.
Load, Execute
End, Abort
get process attributes & set process attributes.
Wait event, Signal event.
Allocate and Free memory.

[Link] MANAGEMENT
Create file, delete file.
Open, close
Read, Write operations.
get file attributes, set file attributes

[Link] MANAGEMENT
Request device, release device.
Read, write, reposition.
Logically attach.

[Link] MAINTENANCE
get time or date, set time or date.
get process file or device attributes.
get system data, set system data.

[Link]

create, delete communication connection

send, receive messages.
transfer status information.

15
 SYSTEM PROGRAMS

Interface between user and operating system.

[Link] MANAGEMENT
create, delete, copy, rename, print, list and generally manipulate files
and directories.

[Link] INFORMATION

Some program requires date time, amount of available memory, no of

users and so on.

[Link] MODIFICATION

Several text editors may be available to create and modify the content
of files stored on disk.

[Link] LANGUAGE SUPPORT

Compilers, assemblers and interpreter for common programming

languages(such as C, C++, Java, VB)

[Link] LOADING & EXECUTION

Once a program is compiled, it must be loaded into memory to be

executed.

[Link]

They allow users to send messages to another, to browse web pages,

transfer files from one machine to another.

16
 SYSTEM STRUCTURE

A system as large and complex as modern as must be engineered

carefully. There are two types of system structure.

Simple Structure
Layered Structure

SIMPLE STRUCTURE

MS-DOS – written to provide the most functionality in the least space

Not divided into modules
Although MS-DOS has some structure, its interfaces and levels
of functionality are not well separated

MS-DOS Layer Structure

UNIX – limited by hardware functionality, the original UNIX operating

system had limited structuring. The UNIX OS consists of two separable parts
Systems programs
The kernel
● Kernel is further separated into series of interfaces and device
drivers.
● Consists of everything below the system-call interface and
above the physical hardware

17
 ● Provides the file system, CPU scheduling, memory
management, and other operating-system functions.
● More functioning combined into one level, any changes in one
section could affect other areas.

UNIX System Structure

LAYERED APPROACH :

The operating system is divided into a number of layers (levels), each

built on top of lower layers. The bottom layer (layer 0), is the hardware;
the highest (layer N) is the user interface.
With modularity, layers are selected such that each uses functions
(operations) and services of only lower-level layers
Once the first layer is debug, the second layer is worked on and so on.
Thus the design and implementation of system is broken into layers.
Each layer is implemented using only operations provided by lower layer.

Difficulty:
●Layered approach involves in definition of various layers.
●A layer use only at lower level, so careful planning is necessary.
●Requirement may not be Obvious.

LAYERED APPROACH

18
VIRTUAL MACHINES

A virtual machine takes the layered approach to its logical conclusion.

It treats hardware and the operating system kernel as though they were
all hardware
A virtual machine provides an interface identical to the underlying bare
hardware
The operating system creates the illusion of multiple processes, each
executing on its own processor with its own (virtual) memory

(a) Non-Virtual Machine (b) Virtual Machine

The resources of the physical computer are shared to create the virtual
machines

●CPU scheduling can create the appearance that users have their
own processor
●Spooling and a file system can provide virtual card readers and
virtual line printers
●A normal user time-sharing terminal serves as the virtual
●Virtual machine approach involves disk system. So it provides mini
disk in needs of several disk space.

19
IMPLEMENTATION

The Virtual Machine has 2 modes.

[Link] Mode :
The virtual machine itself can executes if only user mode.
[Link] Mode :
●Virtual machine s/w can run in monitor mode as its o/s.
●The transfer of user mode to monitor mode can be done easily by:
Running a program or virtual machine in user mode.
Cause transfer to virtual machine mode and it gains the control.

SYSTEM DESIGN AND IMPLEMENTATION

There is no complete solutions to design problems exist, but some

approaches have been successful.

(a) DESIGN GOALS :

In designing a system to define the goals and specification of the
system.
The design of the system will be affected by the following:
[Link] of the hardware.
[Link] of the system(Batch, Time-shared,etc.,)
Another one is to specify the requirements. It has two groups.
(i) User Goals:
● Convenient to use.
● Easy to learn.
● Reliable.
● Safe and Fast.

(ii) System Goals:

20
 ● There is no unique solution to the problem of defining the
requirements for an OS.
● Different requirements can result in a variety of solution for
different environments.

(b) MECHANISM AND POLICIES :

Mechanism means how to do something.

Policies means what will be done.
The separation of policy and mechanism is important for flexibility.
Policy decision is important for all resources and scheduling problems.

(c) IMPLEMENTATION:
Once an operating system is designed, it must be implemented.
Traditionally the OS have been written in assembly language.
Now days, operating system can be written by High Level
Languages.
Some of the operating system written by High Level Languages.
● Master Control Program(MCP) is written by ALGOL.
● MULTICS is written by PL/1.
● Primos is written by FORTRAN.
● UNIX,OS/2,WINDOWS/NT are written by C.
Advantages Using HLL.
●Easy to write program for OS.
●Code can be written faster, easier to understand and debug.
Disadvantages Using HLL.
●Reduced Speed and increased storage space.
●An expert assembly language programmer can produce
efficient small routines for large programs than HLL
programmers.

PROCESS MANAGEMENT

21
PROCESS CONCEPTS:

PROCESS :

A program in execution is called a process.

Execution must progress in sequential fashion.
Process may include Text section, Program counter, Stack (subroutine
parameters, return address & temporary variables), Data section &
Global variables.
Program is a passive entity, whereas Process is an active entity.
The process is the unit of work in an OS.
●System processes are created by the OS to perform tasks on the
user’s or system’s behalf.
●User processes are created by the user’s actions.

PROCESS STATES :

The current activity or stage of a process is known as Process state.

Each process may be in any one of the following states:
●NEW – The process being created.
●READY – The process is waiting to be assigned to a processor.
●RUNNING – The instructions are being executed.
●WAITING – The process is waiting for some event to occur (I/O or
Signal)
●TERMINATE – The process has finished execution.

PROCESS CONTROL BLOCK :

22
 Each Process is represented in the operating system by a Process
Control Block (PCB) –also called as task control block.
The PCB contains important information about the specific process
including.
1. Process State :

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

2. Program Counter :
The counter indicates the address of the next instruction to be executed
for this process.
3. Registers :
● The registers vary in number and type depending on the computer
architecture.
● The include accumulator, index register, stack pointers, general
purpose registers and condition code information.

Process
Pointer
State
Process number
Program counter

Registers

Memory limits
List of open files
.
.
.

23
4. CPU Scheduling Information :
This information includes a process priority, pointers to scheduling queues
and any other scheduling parameters.

5. Memory Management Information :

This includes the information as the value of Base and Limit registers,
Page table or Segment table.

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

7. I/O Status Information :

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

24
THREADS
If the process has multiple threads of control, it can do more than one task
at a time. A single thread of control allows the process to perform only one
task at one time.

The benefits of multithreaded programming can be broken into four

categories :

●Responsiveness
●Resource Sharing

25
 ●Economy
●Utilization of multiprocessor architecture

USER AND KERNEL THREADS :

User Threads:
All thread creation and scheduling are done in user space without the
need for kernel intervention.
It is fast to create and manage.

Kernel Threads:
The Kernel performs thread creation, scheduling and management in
kernel space.
It is slower to create and manage than user threads.

MULTITHREADING MODELS :
Many-to-one Model
One-to-One Model
Many-to-Many Model

Many-to-one Model :
● The many-to-one model maps many user-level threads to one kernel
thread.
● Only one thread can access the kernel at a time.

Many-to-One Model
One-to-One Model :
● The one-to-one Model maps each user thread to a kernel thread.

26
 ● A user thread requires creating the corresponding kernel thread.

One-to-one model

Many-to-Many Model:
● The many-to-many model multiplexes many user-level threads to a
smaller or equal number of kernel threads.
● Developers can create as many user threads as necessary and the
corresponding kernel threads can run in parallel on a multiprocessor.

Many-to-Many Model
PROCESS SCHEDULING :

27
 The objective of multiprogramming is to improve the CPU utilization.
(a) Scheduling Queues :
A new process enter the system, they are put into a Job queue which
consists of all processes in the system.
The processes that are residing in main memory and are ready and
waiting to execute are kept on a list called a Ready queue.
There also other queue in the system.
This queue is usually stored in linked list.
The list of processes waiting for a particular I/O device is called a
device queue.
Each device has its own device queue.

The Queuing diagram illustrates the representation of process

scheduling. The circles represent a device and the rectangle represents
28
 a queue.

(b) Schedulers :

The OS must select processes from these queues in some fashion.

This selection process is carried out by the appropriate schedulers.
There are three types of schedulers.
1. Long-term Schedulers :
●This can selects a job from the Job queue and send to ready queue.
●Controls the degree of multiprogramming and only used on batch
systems.
2. Short-term Schedulers :
●Selects any one process from ready queue and assign the CPU to
run.
●Executes frequently. e.g., every 0.1 sec
●Must be very fast to minimize system overhead.
3. Medium-term Schedulers :
●Medium-term Scheduler decides when to swap processes to disk
and back to main memory.

29
(c) Context Switch :
Switching the CPU to another process is called context switching.
It needs to save the state of the old process and loading the state
of the new process.

(d) Cooperating Process

Independent process cannot affect or be affected by the execution of

another process
Cooperating process can affect or be affected by the execution of
another process
Advantages of process cooperation
● Information sharing: providing environment to allow current access
to the resources if the user interested in the same piece of
information.
● Computation speed-up: A particular task can run faster by breaking
them into subtask executed in parallel with others.
● Modularity: We can construct the system in modular Fashion
dividing system function into separate process.
● Convenience: Individual user may do several task on at one time.

Producer – Consumer Problem

● Paradigm for cooperating processes, producer process produces
information that is consumed by a consumer process
●unbounded-buffer places no practical limit on the size of the buffer
●bounded-buffer assumes that there is a fixed buffer size

30
Code For Producer & Consumer Process

#define BUFFER_SIZE 10

typedef struct {
. . .
}item;
item buffer[BUFFER_SIZE];
int in=0;
int out=0;
Producer process:
while(1) {
/* produce an item in nextproduced */
while(((in+1)%BUFFER_SIZE)==out)
; /* do nothing */
buffer[in]=nextproduced;
in =(in+1) % BUFFER_SIZE;
}
Consumer process:

while(1) {
while(in == out)
; // do nothing
nextconsumed=buffer[out];
out=(out+1) % BUFFER_SIZE;
/* consume the item in nextconsumed */
}

31
 INTERPROCESS COMMUNICATION(IPC)

● Mechanism for processes to communicate and to synchronize their

actions.
● IPC is particularly useful in a distributed environment where the
communicating processes may reside on different computers
connected with a network.

IMPLEMENTATION QUESTIONS

How are links established?

Can a link be associated with more than two processes?
How many links can there be between every pair of communicating
processes?
What is the capacity of a link?
Is the size of a message that the link can accommodate fixed or
variable?
Is a link unidirectional or bi-directional?

1. MESSAGE PASSING SYSTEM:

● Message system – processes communicate with each other without

resorting to shared variables
● IPC facility provides two operations:
●Send(message) – message size fixed or variable
●Receive(message)
● If P and Q wish to communicate, they need to:
●Establish a communication link between them
●Exchange messages via send/receive
● Implementation of communication link
●Physical (e.g., shared memory, hardware bus)
●Logical (e.g., logical properties)
The several methods for logically implementing a link and the send/
receive operations:

● Direct or indirect communications

32
 ● Symmetric or Asymmetric communications
● Automatic or explicit buffering
● Send by copy or send by reference
● Fixed size or variable size messages.

2. NAMING
Processes that want to communicate must have a way to refer to each
other.

(i) DIRECT COMMUNICATION

Processes must name each other explicitly:
●send (P, message) – send a message to process P
●receive(Q, message) – receive a message from process Q
Properties of communication link
● Links are established automatically
● The process need to know only each other’s identity to
communicate.
● A link is associated with exactly one pair of communicating
processes
● Between each pair there exists exactly one link
● The link may be unidirectional, but is usually bi-directional

(ii) INDIRECT COMMUNICATION

Messages are directed and received from mailboxes (also referred to
as ports)
●Each mailbox has a unique id
●Processes can communicate only if they share a mailbox
Properties of communication link
●Link established only if processes share a common mailbox
●A link may be associated with many processes
●Each pair of processes may share several communication links
●Link may be unidirectional or bi-directional
Operations
●Create a new mailbox
●Send and receive messages through mailbox
●Destroy a mailbox
Primitives are defined as:
Send (A, message) – send a message to mailbox A
33
 Receive (A, message) – receive a message from mailbox A
Mailbox sharing
●P1, P2, and P3 share mailbox A
●P1, sends; P2 and P3 receive
●Who gets the message?
Solutions
●Allow a link to be associated with at most two processes
●Allow only one process at a time to execute a receive operation
●Allow the system to select arbitrarily the receiver. Sender is notified
who the receiver was.
3. SYNCHRONIZATION
Communication between processes takes place by calls to send and
receive primitives. There are different design options for implementing each
primitive. Message Passing may be either blocking or non blocking- also
known as synchronous and asynchronous.
● Blocking send: The sending process is blocked until the message is
received by the receiving process or by the mailbox.
● Non blocking send: The sending process sends the message and
resumes operation.
● Blocking receive: The receiver blocks until a message is available.
● Non blocking receive: The receiver retrieves either a valid message or a
null

Different combinations of send and receive are possible. When both the
send and receive are blocking, we have a rendezvous between the sender
and the receiver.

4. BUFFERING

Whether the communications is direct or indirect, messages exchanged

by communication processes reside in a temporary queue. Basically, such
a queue can be implemented in three ways.

● Zero Capacity: The queue has maximum length 0; thus, the link cannot
have any messages waiting in it. In this case, the sender must block
until the recipient receive the messages.
● Bound Capacity: The queue has finite length n; thus, at most n
messages can reside init. If the queue is not full when a new message is
34
 sent, the latter is placed in the queue and the sender can continue
execution without waiting.
● Un bounded Capacity: The queue has potentially infinite length ; thus,
any number of messages can wait in it. The sender never blocks.

CPU SCHEDULING
CPU SCHEDULER :

The Scheduler selects from among the processes in memory that are
ready to execute, and allocates the CPU to one of them.
CPU scheduling decisions may take place when a process:
[Link] from running to waiting state.
[Link] from running to ready state.
[Link] from waiting to ready.
[Link].
Scheduling under 1 and 4 is non preemptive.
All other scheduling is preemptive.

SCHEDULING CRITERIA :

1. CPU Utilization :
We can keep the CPU as busy as possible.
CPU Utilization may range from 0 to 100%.
2. Throughput :
The number of processes that are completed per time unit is
called throughput.
3. Turnaround time :
The time interval from the time job submission and time of job
completion is called turnaround time.
It includes sum of waiting to get memory, waiting in ready
35
 queue, executing on the CPU and doing I/O.

4. Waiting Time :

The amount of time that a process spends waiting in the ready

queue is called waiting time.

5. Response Time :
The time from the submission of a request until the first
response is produced is called response time.(ex. Interactive
systems)

SCHEDULING ALGORITHMS :

CPU Scheduling deals with the problem of deciding which

process is in ready queue is to be allocated the CPU.
There are several CPU Scheduling algorithms

1. FIRST-COME, FIRST-SERVED (FCFS) SCHEDULING

The process that requests the CPU first is allocated

Easily managed by FIFO queue
Process enters the ready queue, its PCB is linked to the tail of queue
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

36
 Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17 milliseconds

FCFS Scheduling (Cont.)

Suppose that the processes arrive in the order

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

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

Average waiting time: (6 + 0 + 3)/3 = 3 milliseconds
FCFS is non preemptive.
Once the CPU allocated to a process, that process keeps the CPU until
it release the CPU, either by terminating or by requesting I/O
It is troublesome for time sharing system, where each user needs to
get a share of CPU at regular intervals.

2. SHORTEST-JOB-FIRST (SJF) SCHEDULING

Associate with each process the length of its next CPU burst. Use
these lengths to schedule the process with the shortest time

Two schemes:
●non preemptive – once CPU given to the process it cannot be
preempted until completes its CPU burst

●preemptive – if a new process arrives with CPU burst length less

than remaining time of current executing process, preempt. This
scheme is know as the

37
 Shortest-Remaining-Time-First (SRTF)

SJF is optimal – gives minimum average waiting time for a given set of
processes
If two processes have same length FCFS scheduling is used.

Example:
Consider the following set of process with the length of CPU burst time

PROCESS BURST TIME

P1 6
P2 8
P3 7
P4 3
Gantt chart

P4 P1 P3 P2

0 3 9 16 24

Average waiting time =0+3+9+16/4

=7 millisecond

3. PRIORITY SCHEDULING

A priority number (integer) is associated with each process.

The CPU is allocated to the process with the highest priority.
●Preemptive :
It will preempt the CPU if the priority of the newly arrived
process is higher than the priority of the currently running process.
●Non preemptive:
It will simply put the new process at the head of the ready
queue.
SJF is a priority scheduling where priority is the predicted next CPU
burst time.

38
 Starvation – low priority processes may never execute.
Aging –It increasing the priority of the processes that wait in the
system for long time.

Example :

Consider the following process with CPU burst time as follows:

PROCESS BURST TIME PRIORITY

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

Gantt chart

P2 P5 P1 P3 P4

0 1 6 16 18 19

Average waiting time = 0+1+6+16+18/5

= 8.2 milliseconds

TWO Types of priority

[Link] Priority:
It uses measurable quantity. Ex: time limit, memory requirement, CPU
burst etc.
[Link] Priority:
It sets by criteria that are external from operating system. Ex: Important for
process, amount of fund required etc.

[Link] ROBIN SCHEDULING

39
 Each process gets a small unit of CPU time (time quantum), usually
10-100 milliseconds. After this time has elapsed, the process is
preempted and added to the end of the ready queue.
If there are n processes in the ready queue and the time quantum is q,
then each process gets 1/n of the CPU time in chunks of at most q time
units at once. No process waits more than (n-1)q time units.
Performance
●q large FIFO
●q small q must be large with respect to context switch, otherwise
overhead is too high

Example of RR with Time Quantum = 4

PROCESS BURST TIME

P1 24
P2 3
P3 3

The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

P1=0; P2=4; P3=7; P1=10; P1=10-4=6;

The average waiting time =4+7+6/3=17/3
=5.666 milliseconds
Typically, higher average turnaround than SJF, but better response

5. MULTILEVEL QUEUE

Ready queue is partitioned into separate queues:

foreground (interactive)

background (batch)

40
 Each queue has its own scheduling algorithm
●foreground – RR
●background – FCFS
Scheduling must be done between the queues
●Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.
●Time slice – each queue gets a certain amount of CPU time which
it can schedule amongst its processes; i.e., 80% to foreground in
RR
●20% to background in FCFS

MULTILEVEL QUEUE SCHEDULING

6. MULTILEVEL FEEDBACK QUEUE SCHEDULING

A process can move between the various queues; aging can be

implemented this way
Multilevel-feedback-queue scheduler defined by the following
parameters:
●Number of queues
●Scheduling algorithms for each queue
●Method used to determine when to upgrade a process
●Method used to determine when to demote a process
●Method used to determine which queue a process will enter when
that process needs service

41
 MULTILEVEL FEEDBACK QUEUES

UNIT – II
PROCESS SYNCHRONIZATION

THE CRITICAL-SECTION PROBLEM

Definition:

● A System consisting of ‘n’ processes {P0, P1, P2…… Pn-1} to be considered.

● A segment of code, in which processes may be updating a table etc.,
● Contains the following:
a) Entry Section

42
 b) Exit Section
c) Remainder Section

Each process must request permission to enter its critical section. The
section of the code implementing this request is the entry section.
The Critical section may be followed by an exit section.
The remaining code is the remainder section.

General structure of a typical process Pi

do {
entry sections
Critical section
exit section
remainder section
}while(1);

Solution to the Critical Section Problem

1. Mutual exclusion: If process Pi is executing in its critical section, then

no other processes can be executing in their critical sections.

2. Progress: If no process is executing in its critical section and some

processes wish to enter their critical sections, then only those processes
that are not executing in their remainder section can participate in the

43
 decision on which will enter its critical section next, and this selection
cannot be postponed indefinitely.

3. Bounded Waiting: There exists a bound on the number of times that

other processes are allowed to enter their critical sections after a
processes has made a request to enter its critical section and before
that request is granted.

do {
flag[i]=true;
turn=j;
while(flag[j]&&turn==j);
Critical section
flag[i]=false;
Remainder section
} while(1)

We need to show that:

(i). Mututal Exclusion is preserved
(ii). The progress requirement is satisfied.
(iii). The bounded waiting requirement is achieved.
● To prove property (i), each Pi enters its critical section only if
flag[J]= false or turn=i.
● To prove property (ii) and (iii), Pi can be prevented from entering the
Critical section only if it is stuck in the while loop with the condition
flag [j] = true and turn=j.
● If Pj resets flag[j], the turn has to be set to i.
● Pi will come into the critical section (progress) after maximum of
one entry by Pj (Bounded Waiting).
SYNCHRONIZATION HARDWARE
Definition:

44
 ● Synchronization Hardware deals with simple hardware instruction.
● Available on so many systems to solve the critical section problem.
Need for Synchronization Hardware

The critical section problem could be solved simply in a uniprocessor

environment if we could forbid interrupts to occur while a shared variable is
being modified.
● Currently running code would execute without preemption
This solution is not feasible in multiprocessor environment. It disable
interrupt in time consuming.
● System efficiency decreases.
Modern machines provide special atomic hardware instructions
● Atomic = non-interruptable
● Either test memory word and set value
● Or swap contents of two memory words

Mutual Exclusion with Test and Set

The TestAndSet instruction can be defined as:

while(true)
{
while(TestAndSet(lock));
critical section
lock=false;
remainder section
}

● The lock state is implemented by a memory location. The location is 0,

if the lock is unlocked and 1, if the lock is locked.
● The lock operation is implemented as follows:

45
 while(TestAndSet(l)==1);
● The unlock operation is implemented as i=0.

Definition of Swap Instruction

The swap instruction operates on the contents of two words, like the test-
and- set instructions, it is executed atomically.

void swap(boolean &a,boolean &b)

{
boolean temp=a;
a=b;
b=temp;
}
● The swap instruction defined operates on the contents of two words.
● Similar to the TestAndSet instruction, it is executed automatically.

A global Boolean variable lock is declared and is initialized to false. Each

process has a local boolean variable key.

boolean waiting[n];
boolean lock;

do {
key=true;
while(key==true)
swap(lock,key);
critical section
lock=false;
remainder section
}while(1);

46
 SEMAPHORES
Synchronization tool that does not require busy waiting.
A Semaphore S is an integer variable
Two standard operations modify S: acquire() and release()
●Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic) operations

acquire( ) {
while S<=0
; //no-op
S--;
}

release( ) {
S++;
}

SEMAPHORE IMPLEMENTATION :

Must guarantee that no two processes can execute acquire() and

release () on the same semaphore at the same time
Thus, implementation becomes the critical section problem where the
wait and signal code are placed in the critical section.
● Could now have busy waiting in critical section implementation
● But implementation code is short
● Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections and
therefore this is not a good solution.

Semaphore Implementation with no Busy waiting

With each semaphore there is an associated waiting queue. Each entry

in a waiting queue has two data items:
●value (of type integer)
●pointer to next record in the list
Two operations:
47
 ●block – place the process invoking the operation on the appropriate
waiting queue.
●wakeup – remove one of processes in the waiting queue and place
it in the ready queue.

Implementation of acquire() :

acquire( ) {
value--;
if(value<0) {
add this process to list
block ;
}
}

Implementation of release():

release( ) {
value++;
if(value<=0) {
remove a process P from list
wakeup(P);
}
}

DEADLOCK AND STARVATION :

Deadlock – two or more processes are waiting indefinitely for an event

that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1

P0 P1
[Link](); [Link]();
[Link](); [Link]();
. .
. .
. .
[Link](); [Link]();
48
 [Link](); [Link]();

Starvation – indefinite blocking. A process may never be removed

from the semaphore queue in which it is suspended.

BINARY SEMAPHORES :

Counting semaphore – integer value can range over an unrestricted

domain
Binary semaphore – integer value can range only between 0

and 1; can be simpler to implement

●Also known as mutex(mutual exclusion) locks

Semaphore sem = new Semaphore(1);

[Link]();
// critical section
[Link]();
// remainder section

CLASSICAL PROBLEMS OF SYNCHRONIZATION

These problems are used for testing nearly every newly proposed
synchronization scheme.

The bounded buffer problem:

The mutex semaphores provides mutual exclusion for accesses to the
buffer pool and is initialized to the value 1.
The empty and full semaphores count the number empty and full
buffers, respectively.

The semaphores empty is initialized to the value n; the semaphore full

is initialized to the value 0.

49
The structure of the producer process:
Repeat
do
{
………………
Produce an item in next p
………………
wait (empty);
wait (mutex);
………………
add next p to buffer
………………..
signal (mutex);
signal (full);
until false;

The structure of the consumer process:

repeat
wait (full);
wait (mutex);
………………….
remove an item from buffer to next c
…………………….
signal (mutex);
signal (empty);
………………….
consume the item in next c
………………
until false;

The readers and writers problem:

A data object (such as a file or record) is to be shared among several
concurrent processes. Some of these processes may want only to read

50
 the content of the shared object whereas others may want to update (ie: to
read and write) the shared object.
If two readers access the shared data object simultaneously no
adverse effects, will result.
If a writer and some other access the shared object simultaneously,
chaos may ensue.
The readers-writers problem has several variations, all involving
priorities.
●The first readers-writers problem, requires that no reader will be
kept waiting unless a writer has already obtained permission to
use the shared object.
●The second readers-writers problem require that once a writer is
ready, that access the object no new readers may start read.
The structure of a writer process:

wait (wrt);
……
writing is performed
……
signal (wrt);

The structure of the reader process:

wait (mutex);
readcount++;
if (readcount==1)
wait (wrt);
signal (mutex);
…
reading is performed
…
wait (mutex);
readcount--;
if (readcount ==0)
signal (wrt);
signal (mutex);

The Dining philosophers problem:

51
 Consider five philosophers who spend their lives thinking and eating. The
philosophers share a common circular table surrounded by five chairs, each
belonging to one philosopher. In the center of the table where is a bowl of rice
and the table is laid with five single chopsticks. when a philosopher thinks, she
does not interact with her colleagues.

The situation of the dining philosophers:

One simple solution is to represent each chopstick by a semaphore. A

philosopher tries to grab the chopstick by executing a wait operation on that
semaphore; one releases her chopsticks by executing the signal operation on
the appropriate semaphores.
The structure of philosopher
repeat
wait (chopstick[i]);
wait (chopstick[(i+1)%5]);
…
eat
…
signal (chopstick [i]);
signal (chopstick [(i+1)%5];
…
think

52
 …
until false;

We present a solution to the dining philosopher problem that ensure

freedom from deadlocks.
Allow at most four philosopher to be sitting simultaneously as the table.
Allow a philosopher to pick up her chopsticks only if both chopsticks are
available.
Use an asymmetric solution; that is an odd philosopher picks up first
her left chopstick and then her right chopstick, whereas an even
philosopher picks up her right chopstick and then her left chopstick.

CRITICAL REGIONS

MOTIVATION :

The time dependent errors can be easily generated when semaphores

are used to solve.
The critical section problem. To overcome this difficulty a new
language construct, the critical region was introduced.

DEFINITION AND NOTATION :

A variable v of type T, which is to be shared among many processes can be

declared:

Var V: shared T;

The variable V can be accessed only inside a region statement of the

following form:

region V when B do S;

This construct means that while statement S is being executed, no other

53
process can access the variable V. The expression B is a Boolean expression.
If the expression is true, statement S is executed. If the two statements,

region V when (true) S1;

region V when (true) S2;

are executed concurrently in distinct sequential processes, the result will be

equivalent to the sequential execution “S1 followed by S2” or “S2 followed by
S1”.
To illustrate this construct, consider the frames CLASS defined in abstract
data type. Since mutual exclusion is required when accessing the array free,
we need to declare it as a shared array.

Var free : Shared Array[1…n] of Boolean;

The acquire procedure must be rewritten as follows,

PROCEDURE ENTRY acquire(Var index : integer)

Begin
region free do
for index:=1 to n do
if free[index] then
Begin
free[index]:=false;
End;
End;

The critical region construct guards against some simple errors associated
with the semaphore solution to the critical section problem which may be
made by a programmer.

Implementation of the Critical Region Construct :

For each declaration

Var V : Shared T;
The compiler generates a semaphore v-mutex initialized to 1. For each
statement,

54
 region V do S;
the compiler generates the following code:

P(v-mutex);
S;
V(v-mutex);

Critical region may also be nested. In this case, however deadlocks may result.

VAR X,Y : SHARED T;

PARBEGIN
Q : REGION X do REGION Y do S1;
R : REGION Y do REGION X do S2;
PAREND;

MONITORS

A high-level abstraction that provides a convenient and effective

mechanism for process synchronization
Only one process may be active within the monitor at a time

Syntax of a Monitor

55
 Fig: Schematic view of a Monitor

56
Condition Variables :

Condition x, y;

Two operations on a condition variable:

● [Link] () – a process that invokes the operation is
suspended
● [Link] () – resumes one of processes (if any) that
invoked [Link] ()

57
 Fig: Monitor with Condition Variables

DEADLOCK

Ex: Let us consider a system with 2 processes with 2 resources

58
 • Here Process P1 consisting of Resource1 information along with that P1
is waiting to acquire Resource2 information. Here P1 requires additional
resource R2.
• As the same thing P2 process consists of Resource2 Information along
with P2 is waiting to acquire Resource1 (R1) information. Here P2
requires additional resource Resource1.
Hence no one process can continue its processing.

In a multiprogramming environment , several processes may compete

for a finite number of resources. A process request resources; if the resources
are not available at the time, the process enters a wait state. This situation is
called as DEADLOCK.

SYSTEM MODEL :

Resource types R1,R2,…Rm

CPU cycles, memory space, I/O devices.
Each resource type Ri has Wi instances.
Each process utilizes a resource as follows:
●request : if the request cannot be granted immediately then the
requesting process must wait until it can acquire the resource.
●use : The process can operate on the resource .
●release : The process releases the resource.

DEADLOCK CHARACTERIZATION

Deadlock can arise if four conditions hold simultaneously.

Mutual exclusion: only one process at a time can use a resource.
Hold and wait: a process holding at least one resource is waiting to
acquire additional resources held by other processes.
No preemption: a resource can be released only voluntarily by the
process holding it, after that process has completed its task.
Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such
that P0 is waiting for a resource that is held by P1, P1 is waiting for a
resource that is held by
59
 P2, …, Pn–1 is waiting for a resource that is held by

Pn, and P0 is waiting for a resource that is held by P0.

METHODS FOR HANDLING DEADLOCKS

Ensure that the system will never enter a deadlock state.

Allow the system to enter a deadlock state and then recover.
Ignore the problem and pretend that deadlocks never occur in the
system; used by most operating systems, including UNIX.

DEADLOCK PREVENTION

Restrain the ways request can be made.

Mutual Exclusion – not required for sharable resources; must hold for
non sharable resources.
Hold and Wait – must guarantee that whenever a process requests a
resource, it does not hold any other resources.
●Require process to request and be allocated all its resources before
it begins execution, or allow process to request resources only
when the process has none.
●Low resource utilization; starvation possible.
No Preemption
●If a process that is holding some resources requests another
resource that cannot be immediately allocated to it, then all
resources currently being held are released.
●Preempted resources are added to the list of resources for which
the process is waiting.
●Process will be restarted only when it can regain its old resources,
as well as the new ones that it is requesting.
Circular Wait
● Impose a total ordering of all resource types, and require that
each process requests resources in an increasing order of
enumeration.

60
 DEADLOCK AVOIDANCE

Requires that the system has some additional a priori information

available.

● Simplest and most useful model requires that each process declare the
maximum number of resources of each type that it may need.
● The deadlock-avoidance algorithm dynamically examines the resource-
allocation state to ensure that there can never be a circular-wait
condition.
● Resource-allocation state is defined by the number of available and
allocated resources, and the maximum demands of the processes.

Safe-State :

When a process requests an available resource, system must decide if

immediate allocation leaves the system in a safe state.
System is in safe state if there exists a sequence <P1, P2, …, Pn> of ALL
the processes is the systems such that for each Pi, the resources that
Pi can still request can be satisfied by currently available resources +
resources held by all the Pj, with j < i.
That is:
●If Pi resource needs are not immediately available, then Pi can wait
until all Pj have finished.
●When Pj is finished, Pi can obtain needed resources, execute, return
allocated resources, and terminate.
●When Pi terminates, Pi +1 can obtain its needed resources, and so on.

BASIC FACTS :

If a system is in safe state no deadlocks.

If a system is in unsafe state possibility of deadlock.
Avoidance ensure that a system will never enter an unsafe state.

61
 Fig: Safe, Unsafe, Deadlock State

AVOIDANCE ALGORITHMS:
Single instance of a resource type. Use a resource-allocation graph
Multiple instances of a resource type. Use the banker’s algorithm

Resource Allocation Graph Scheme :

Claim edge Pi Rj indicated that process Pj may request resource Rj;
represented by a dashed line.

Claim edge converts to request edge when a process requests a

resource.

Request edge converted to an assignment edge when the resource is

allocated to the process.
When a resource is released by a process, assignment edge reconverts
to a claim edge.

Resources must be claimed a priori in the system.

Resource-Allocation Graph

62
 Unsafe State In Resource-Allocation Graph

RESOURCE ALLOCATION GRAPH ALGORITHM :

Suppose that process Pi requests a resource Rj

The request can be granted only if converting the request edge to an
assignment edge does not result in the formation of a cycle in the
resource allocation graph.

BANKER’S ALGORITHM:

Multiple instances.
Each process must a priori claim maximum use.
When a process requests a resource it may have to wait.
When a process gets all its resources it must return them in a finite
amount of time.

DATA STRUCTURES FOR THE BANKER’S ALGORITHM :

Let n = number of processes and m = number of resources types.

63
 Available: A Vector length m indicates the no. of available resources of
each type.
Vector of length m. If available [j] = k, there
are k instances of resource type Rj available.
Max: Defines the maximum demand of each process.
n x m matrix. If Max [i,j] = k, then process Pi may
request at most k instances of resource type Rj.
Allocation: Defines the no. of resources of each type.
n x m matrix. If Allocation[i,j] = k then Pi is
currently allocated k instances of Rj.
Need: Remaining resources needed for each process.
n x m matrix. If Need[i,j] = k, then Pi may need k
more instances of Rj to complete its task.

Need [i,j] = Max[i,j] – Allocation [i,j].

SAFETY ALGORITHM:

[Link] Work and Finish be vectors of length m and n, respectively. Initialize:

Work = Available
Finish [i] = false for i = 0, 1, …, n- 1.
[Link] and i such that both:
(a) Finish [i] = false
(b) Needi Work
If no such i exists, go to step 4.
[Link] = Work + Allocationi

Finish[i] = true

go to step 2.
[Link] Finish [i] == true for all i, then the system is in a safe state.

RESOURCE-REQUEST ALGORITHM FOR PROCESS Pi :

64
 Request = request vector for process Pi. If Requesti [j] = k then process Pi
wants k instances of resource type Rj.
1. If Requesti Needi go to step 2. Otherwise, raise error condition, since
process has exceeded its maximum claim.
2. If Requesti Available, go to step 3. Otherwise Pi must wait, since
resources are not available.

3. Pretend to allocate requested resources to Pi by modifying the state

as follows:

Available = Available – Request;

Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
● If safe the resources are allocated to Pi.
● If unsafe Pi must wait, and the old resource-allocation state
is restored

DEADLOCK DETECTION

Allow system to enter deadlock state

Detection algorithm

Recovery scheme

SEVERAL INSTANCE OF EACH RESOURCE TYPE :

Maintain wait-for graph

●Nodes are processes.
●Pi Pj if Pi is waiting for Pj.
Periodically invoke an algorithm that searches for a cycle in the graph.
If there is a cycle, there exists a deadlock.

65
 2
An algorithm to detect a cycle in a graph requires an order of n
operations, where n is the number of vertices in the graph.

Resource-Allocation Graph And Wait-For Graph

Resource-Allocation Graph Corresponding wait-for graph

SEVERAL INSTANCES OF A RESOURCE TYPE :

Available: A vector of length m indicates the number of available

resources of each type.
Allocation: An n x m matrix defines the number of resources of each
type currently allocated to each process.
Request: An n x m matrix indicates the current request of each
process. If Request [ij] = k, then process Pi is requesting k more
instances of resource type. Rj.

66
DETECTION ALGORITHM :

1. Let Work and Finish be vectors of length m and n, respectively Initialize:

(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi 0, then

Finish[i] = false;otherwise, Finish[i] = true.

2. Find an index i such that both:
(a) Finish[i] == false
(b) Requesti Work

If no such i exists, go to step 4.

3. Work = Work + Allocationi

Finish[i] = true

go to step 2.

4. If Finish[i] == false, for some i, 1 i n, then the system is in deadlock state.

Moreover, if Finish[i] == false, then Pi is deadlocked.
2)
Algorithm requires an order of O(m x n operations to detect whether the
system is in deadlocked state.

RECOVERY FROM DEADLOCK

There are two options for breaking deadlock

[Link] termination.
[Link] preemption.

67
PROCESS TERMINATION:

Eliminating deadlock by aborting a process involves 2 methods.

Abort all deadlocked processes.
●clearly break the deadlock
●but great expense
Abort one process at a time until the deadlock cycle is eliminated.
In which order should we choose to abort?
●Priority of the process.
●How long process has computed, and how much longer to
completion.
●Resources the process has used.
●Resources process needs to complete.
●How many processes will need to be terminated.
●Is process interactive or batch?

RESOURCE PREEMPTION :

Selecting a victim – minimize cost.

Rollback – return to some safe state, restart process for that state.

Starvation – same process may always be picked as victim, include

number of rollback in cost factor.

BINDING OF INSTRUCTIONS AND DATA TO MEMORY :

Address binding of instructions and data to memory addresses can

happen at three different stages
●Compile time: If memory location known a priori, absolute code can
be generated; must recompile code if starting location changes.

68
 ●Load time: Must generate relocatable code if memory location is
not known at compile time.
●Execution time: Binding delayed until run time if the process can be
moved during its execution from one memory segment to
another. Need hardware support for address maps (e.g., base
and limit registers).

UNIT – III
MEMORY MANAGEMENT

Memory Definition:

Memory consist of a large array of words or bytes each with its own
address. The CPU fetches instruction from memory using program counter.

ADDRESS BINIDING :
INPUT QUEUE :

The collection of processes on the disk that are waiting to be brought in

to the memory for execution forms is called as input queue.
The normal procedure is to select one of the processes in the input

69
 queue and to load that process into memory. As the process is executed, it
access instruction and data from memory. Eventually when it terminate,
it’s memory space is declared as available.
The above process is done using address binding . A compiler bind the
symbolic address to relocatable address. A Linkage editor (or) Loader
will bind this relocatable address to absolute address.

Binding Of Instructions And Data To Memory :

Address binding of instructions and data to memory addresses

can happen at three different stages
Compile time: If memory location known a priori, absolute code
can be generated; must recompile code if starting location
changes
Load time: Must generate relocatable code if memory location
is not known at compile time
Execution time: Binding delayed until run time if the process can
be moved during its execution from one memory segment to
another. Need hardware support for address maps (e.g., base
and limit registers)

MULTISTEP PROCESSING OF A USER PROGRAM

70
 DYNAMIC LOADING AND LINKING

● Routine is not loaded until it is called

● Better memory-space utilization; unused routine is never loaded
● Useful when large amounts of code are needed to handle infrequently
occurring cases
● No special support from the operating system is required implemented
through program design

Two Types of Linking:

[Link] LINKING:
The system language libraries are treated as other object module and
combined by loader into memory binary program image.
2. DYNAMIC LINKING:
Linking postponed until execution time.
Small piece of code, stub, used to locate the appropriate memory-
resident library routine.
Stub replaces itself with the address of the routine, and executes the
routine.
Operating system needed to check if routine is in processes memory
address.
Dynamic linking is particularly useful for libraries.

71
 System also known as shared libraries.

OVERLAYS
● The size of the process is limited to the size of physical memory , so
that a process can be larger than the amount of memory allocated to it
then overlays technique is used.
● The ideas of overlays is to keep in memory only those instructions and
data that are needed at any given time. And the other instructions
needed are loaded into space that was occupied by previous
instructions no larger needed.
Ex:
Consider two process assembles the size of the components are as
follows;
Process-1 70kb
Process-2 80kb
Symbol table 20kb
Common routine 30kb
To load everything we need 200kb of memory. If only 150kb is available,
we can’t run our process. As process-1 and process-2 needn’t be at the same
thing in memory .
Thus two overlays are defined:

● Overlay A-symbol table,common routines & process-1.

● Overlay B-symbol table,common routines & process-2.
● And a overlay driver is included

Starting with overlay A in memory when process-1 is finished, we jump

to overlay driver which reads .
Overlay B into memory over writing on A & then control transferred to
process-2.
Overlays two process assembler.

Symbol
table
Common
routines

72
 Overlays
drivers

LOGICAL AND PHYSICAL ADDRESS SPACE

The concept of a logical address space that is bound to a separate
physical address space is central to proper memory management
●Logical address – generated by the CPU; also referred to as virtual
address.
●Physical address – address seen by the memory unit.
Logical and physical addresses are the same in compile-time and load-
time address-binding schemes; logical (virtual) and physical addresses differ
in execution-time address-binding scheme.

RUNTIME MAPPING :

The runtime mapping from virtual to physical address is done by (MMU)

Memory Management Unit as follows which is a hardware device,

73
 SWAPPING

A process can be swapped temporarily out of memory to a backing store,

and then brought back into memory for continued execution.

Backing store – fast disk large enough to accommodate copies of all

memory images for all users; must provide direct access to these memory
images.

Roll out, roll in – swapping variant used for priority-based scheduling

algorithms; lower-priority process is swapped out so higher-priority process
can be loaded and executed.

Major part of swap time is transfer time; total transfer time is directly
proportional to the amount of memory swapped.

Modified versions of swapping are found on many systems (i.e., UNIX,

Linux, and Windows)

System maintains a ready queue of ready-to-run processes which have

memory images on disk.

SCHEMATIC VIEW OF SWAPPING

74
 CONTIGUOUS ALLOCATION

Main memory usually into two partitions:

Resident operating system, usually held in low memory with interrupt
vector
User processes then held in high memory.
There are two types of allocations are as follows:
1. Single partition allocation:
● Relocation registers used to protect user processes from each other,
and from changing operating-system code and data.
● Base register contains value of smallest physical address.
● Limit register contains range of logical addresses – each logical
address must be less than the limit register.
● MMU maps logical address dynamically by adding the value in the
relocation register.

[Link]-partition allocation:

75
 ● Hole – block of available memory; holes of various size are scattered
throughout memory
● When a process arrives, it is allocated memory from a hole large
enough to accommodate it
● Operating system maintains information about:

a) allocated partitions b) free partitions (hole)

Hardware Support for relocation and limit Registers

DYNAMIC STORAGE-ALLOCATION PROBLEM :

How to satisfy a request of size n from a list of free holes

First-fit: Allocate the first hole that is big enough
Best-fit: Allocate the smallest hole that is big enough; must search
entire list, unless ordered by size
●Produces the smallest leftover hole
Worst-fit: Allocate the largest hole; must also search entire list
●Produces the largest leftover hole
● First-fit and best-fit better than worst-fit in terms of speed and
76
 storage utilization
FRAGMENTATION

External Fragmentation – total memory space exists to satisfy a

request, but it is not contiguous.
Internal Fragmentation – allocated memory may be slightly larger than
requested memory; this size difference is memory internal to a partition,
but not being used.
Reduce external fragmentation by compaction.
●Shuffle memory contents to place all free memory together in one
large block.
●Compaction is possible only if relocation is dynamic, and is done at
execution time.
●Compaction is not possible , if relocation is static, and is done at
load time.
●I/O problem
* Latch job in memory while it is involved in I/O.
* Do I/O only into OS buffers.

NON-CONTIGUOUS ALLOCATION

The memory is allocated to a process in non-contiguously. There are

two methods :
1. Segmentation.
2. Paging.

SEGMENTATION:
Memory-management scheme that supports user view of memory
A program is a collection of segments. A segment is a logical unit such
as:
* main program,
* procedure,
* function,
* method,

77
 * object,
* local variables, global variables,
* common block,
* stack,
* symbol table, arrays
The logical address space is the collection of segments. Each segment
has a name and length. The logical address consists of two types.

<segment number, offset>

User’s View of a Program

Hardware:
In segmentation the mapping is effected by segment table. Each entry of
segment has segment base and segment limit.
Segment base:
Starting physical address where the segment reside in memory.
Segment limit:
Length of the segment.
The segment number is used as index into segment table. The off set d
of logical address must be between o and the segment limit if it is not,
we trap the OS, if it is legal then it is added to produce the address in
physical memory of desired byte.
Segmentation Hardware

78
Example:
The segment 0 to 4 is stored as follows in memory. For example segment
2 is 400 bytes long and begins at 4300 then the physical memory address is
the reference byte 53 of segment 2 is mapped as
4300+53=4353.

Example of Segmentation

PROTECTION AND SHARING :

particular advantage of segmentation is protection the memory mapping

hardware will check the protection bit associated with each segment table
entry to prevent illegal access to memory such as to attempts to write in to a
read only segment or to use an execute only segment.
Another advantage of segmentation involves the sharing of code or
data. Each process has a segment table associates with it. Segments are
79
shared when entries in segment tables of the two different process points to
same physical location.

editor
Segment 0

limit Base Data 1

Segment 1
25286 43062
4425 68348

0
1

Segment table process P1

Logical memory process p1

Physical memory
editor
Segment 0

limit Base
25286 43062
8850 Segment
90003 1

Data 1
0
1

Segment table process P2

Logical memory process p2

80
PAGING :

Logical address space of a process can be noncontiguous; process is

allocated physical memory whenever the latter is available.
Divide physical memory into fixed-sized blocks called frames (size is
power of 2, between 512 bytes and 8,192 bytes).
Divide logical memory into blocks of same size called pages.
Keep track of all free frames.
To run a program of size n pages, need to find n free frames and load
program.
Set up a page table to translate logical to physical addresses.
Internal fragmentation.

Paging Hardware

ADDRESS TRANSLATION SCHEME :

Address generated by CPU is divided into:

Page number (p) – used as an index into a page table which
contains base address of each page in physical memory
Page offset (d) – combined with base address to define the
physical memory address that is sent to the memory unit
81
 Paging model of logical and Physical memory

Page number page offset

p d
m-n n
m n
For given logical address space 2 and page size2

82
Paging example for a 32-byte memory with 4-byte pages
Using a page size of a 4 bytes and physical memory of 32 bytes (8
bytes) we shown an example of how the user view of memory can be mapped
into physical memory. Logical address 0 is page 0 offset 0. Indexing into the
page table, we find a page 0 is in frame 5.

Thus logical address 3(page 0,offset 3) maps to physical address

[23=(5*4)+3]. Logical address 4 is page 1 offset 0 according to the page table
page 1 is mapped to frame 6.

When a process arrives in the system to be executed , its size,

expressed in pages. It examined each page of the process needs one frame.
Thus if the process required n pages there must be at least 0 frames available
in memory if there are 0 frames there are allocated to the arriving process.

The first page of the process is loaded into one of the allocated
process frames and the frame no; is put in to the page table for these process.
The next page is loaded into the another frames and its frame no; is put in to
the page table and so on.

83
FREE FRAMES :

BEFORE ALLOCATION AFTER ALLOCATION

HARDWARE SUPPORT :
The hardware implementation of the page table can be done in a no.
of different ways.
The problem with this approach is the time required to access a user
memory location. If we want to access location I, we first index into the page
table , using the value in the PTBR offset by the page no. for i. this task
required a memory address access. It provides us with the frame no., which is
combined with the page offset to produce the actual address we can then
access the desired place in memory, with this scheme two memory access
are needed to access a byte(one for the page table, one for the byte).

IMPLEMENTATION OF PAGE TABLE :

● Page table is kept in main memory

● Page-table base register (PTBR) points to the page table
● Page-table length register (PRLR) indicates size of the page table
● In this scheme every data/instruction access requires two memory
accesses. One for the page table and one for the data/instruction.
84
 ● The two memory access problem can be solved by the use of a
special fast-lookup hardware cache called associative memory or
translation look-aside buffers (TLBs)
● Some TLBs store address-space identifiers (ASIDs) in each TLB
entry – uniquely identifies each process to provide address-space
protection for that process

ASSOCIATIVE MEMORY :

Associative memory – parallel search

Address translation (p, d)

page# frame#

●If p is in associative register, get frame # out

●Otherwise get frame # from page table in memory

Associative register are used with pages tables in the following way.
The associative registers contain only a few of the page-table entries. When a
logical address is generated by the CPU its page number is presented to a set
of associative registers that contain page no and their corresponding frame
number. If the page no is found in the associative register its frame number is
immediately available and is used to access memory.

PAGING HARDWARE WITH TLB

85
PROTECTION :

Memory protection in a paged environment is accomplished by protection

bits that are associated with each frame. Normally these bits are kept in the
page table. One bit can define a page to be read and write or read only. Every
reference to memory goes through the page table to find the correct frame
number.

At the same time that the physical address is being computed the
protection bits can be checked to verify that no writes are being made to a
read-only page. An attempt to write to a read-only page causes a hardware
trap to the operating system (memory protection violation)

86
 One more bit is generally attached to each entry in the page table; a valid-
invalid bit. When this bit is set to “valid” this value indicates that the associated
page is in the logical address space and it thus the page is not in the
processes logical address space.

Valid(v) or Invalid(i) Bit in a Page Table

STRUCTURE OF THE PAGE TABLE :

Hierarchical Paging
Hashed Page Tables
Inverted Page Tables

HIERARCHICAL PAGE TABLES :

87
 Break up the logical address space into multiple page tables
A simple technique is a two-level page table

Two-Level Page-Table Scheme

A logical address (on 32-bit machine with 1K page size) is divided into:
● a page number consisting of 22 bits
● a page offset consisting of 10 bits
Since the page table is paged, the page number is further divided into:
● a 12-bit page number
● a 10-bit page offset
Thus, a logical address is as follows:

88
 page number page offset
P1 P2 d

where pi is an index into the outer page table, and p2 is the displacement
within the page of the outer page table

Address-Translation Scheme

Three-level Paging Scheme

89
HASHED PAGE TABLES :

Common in address spaces > 32 bits

The virtual page number is hashed into a page table
●This page table contains a chain of elements hashing to the same
location
Virtual page numbers are compared in this chain searching for a match
●If a match is found, the corresponding physical frame is extracted

Hashed Page Table

INVERTED PAGE TABLE :

Each page table memory consists of millions of entries these tables

memory consumes large amount of physical memory which is required just to
keep track of how the other physical memory is being used.
To solve this problem we can use an inverted table. An inverted table has
90
one entry for real page(frame) of memory. Each entry consists of the virtual
address of the page started in that real memory location with important
information about the process that owns that page.
Each virtual address in the system consists of a triple.

<process-id,page-number,offset>

Each inverted page-table entry is a pair <process-id,page-number> when

a memory reference occurs, part of the virtual address consisting of <process-
id,page-number> is represented of the memory subsystem.

Inverted Page Table Architecture

This page table scheme decreases the amount of memory needed to

share each page table it increase the amount of time needed to search the
table when a page.

SHARED PAGES :

91
 Shared code
●One copy of read-only (reentrant) code shared among processes
(i.e., text editors, compilers, window systems).
●Shared code must appear in same location in the logical address
space of all processes.
Private code and data
●Each process keeps a separate copy of the code and data.
●The pages for the private code and data can appear anywhere in
the logical address space.

Shared Pages Example :

Re-entrant code (also called pure code) is non self-modifying code. If the
code is re-entrant, then is never changes during execution. Thus two or more
processes can execute the same code at the same time. Each process has its
own copy of register and data storage to hold the data for the process
execution.

UNIT – IV
VIRTUAL MEMORY

92
 Virtual memory is a technique that allows the execution of processes
that may not be completely in memory. The main visible advantage of this
scheme is that programs can be larger than physical memory.
Virtual memory is the separation of user logical memory from physical
memory. This separation allows an extremely large virtual memory is
available.

Virtual memory is commonly implemented by Demand paging. Demand

segmentation can also be used to provide virtual memory.

DEMAND PAGING :

A demand paging system is similar to a paging system with swapping

processes reside on secondary memory. When we want to execute a process,
we swap it into the memory. Rather than swapping the entire process into
memory. How ever we use a lazy swapper. A lazy swapper never swaps a
page in to memory unless that page will be needed.

Demand Paging

A swapping manipulates entire processes. Where ever a page is

concerned with the individual pages of a process. We shall use the term pager.

93
 With this scheme we need some form of hardware support to
distinguish between those pages table, that are in memory and those pages
that are in the disk.
The valid – invalid bit scheme can be used for this purpose. This time,
how ever, when this bit is set to “valid”, this valid indicate that the associated
page is both legal and in memory. If the bit is set to “invalid” this valued
indicates that the page either is not valid or is valid but is currently on the disk.

PAGE TABLE :
This page table has the ability to make an entry invalid through a valid –
invalid bit or special value of protection bits.

Page Table

94
[Link] check an internal table (usually kept with the process control block) for
this, process to determine whether the reference was a valid or invalid
memory access.
2. If the reference was invalid, we terminate the process. If it was valid, but we
have not get brought in that page, we know page in the letter.
3. We find a free frame (by taking one from the free frame list).
4. We schedule a disk operation to read the decide operation page in to the
newly allocated frame.
5. When the disk read is complete, we modified the internal table kept with in
the process and the page table to indicate the page is now in memory.
[Link] restart the instruction that was interrupted by the illegal address track.
The process can now access the page as through it had always been in
memory.

Secondary memory:

This memory holds those pages that are not present in main memory.
The secondary memory is usually a high speed disk. It is known as the swap
device, and the section of disk used for this purpose is known as swap space
or backing store.
Page Fault

95
PAGE REPLACEMENT :

Prevent over-allocation of memory by modifying page-fault service

routine to include page replacement
Use modify (dirty) bit to reduce overhead of page transfers – only
modified pages are written to disk
Page replacement completes separation between logical memory and
physical memory – large virtual memory can be provided on a smaller
physical memory

Need For Page Replacement

96
BASIC SCHEME :

If no frame is free we find one that is no currently being used and free it.
We can free a frame by writing its content to swap space and changing the
page table to indicate that the page is no longer in memory. The free frame
can now be used to hold the page for which the process faulted.
The page replacement involves the following steps:

1.find the location of the desire page on the disk

2. find a free space
● If there is a free-frame use it.
● Otherwise use a page replacement algorithm to select a victim
frame.
● Write a victim page to the disk, change the page and frame tables
accordingly.

97
 3. Read the desired page into the free frame change the page and
frame table.
4. restart the user process
Page Replacement

PAGE REPLACEMENT ALGORITHMS:

There are many different page replacement algorithms.

1. FIFO Algorithm:
It is simplest replacement algorithms
A FIFO algorithm associate with each page time when that page was
brought into memory.
A pages replaced by choosing a old page

98
 FIFO queue is created to hold all pages
FIFO Page Replacement

Optimal algorithm:
An optimal page replacement algorithm has the lowest page fault. Rate of
all algorithms. Use of this page replacement algorithm it the lowest possible
page fault rate for a fixed no of frames.

Here the page 7 is replaced because it is used only after the reference
18, whereas page 0 is used at 5 and page 1 is used at 14.

LRU ALGORITHM:

Least recently used algorithm, here we replace the page that has not been
used for the long period of time. It associates with each page of that pages
last use.

99
 LRU Page Replacement

LRU APPROXIMATION ALGORITHM:

In this algorithm a reference bit is used to denote the reference of the

pages. Here the reference bit is said to one if it is referred and said to zero if it
is not referred.

1. ADDITIONAL REFERENCE BIT ALGORITHM:

We gain additional ordering information by recording the reference bit at

regular intervals.
we keep eight bit for each page in a table in the memory.
0000 0000 The page has not been used for 8 period of times.
1111 1111 The page is used at least once in each period of time.
1100 0100 The page is used more recently than 0111 0111.
The OS shifts there reference bit for each page into higher-order bit of its
bit, shifting the other bits right, bit discarding the low-order bit.
2. SECOND CHANCE ALGORITHM:

In the algorithm if the reference bit is 0 then we proceed to replace the

page. If the reference bit is 1 the page is given second chance and moved to
next FIFO page and the reference bit of the second chance given page is
cleared.

Second-Chance (clock) Page-Replacement Algorithm

100
ENHANCED ALGORITHM:

The second chance algorithm can be enhanced by considering both the

reference bit and modified bit.
POSSIBLE FOUR CLASSES:

1. (0, 0) – Neither recently used nor modified-best page to replace.

2. (0, 1) – Not recently used but modified-not quite good because the page will
need to be written out before replacement.
3. (1, 0) – Recently used but clean-probably will be used again & so on.
4. (1, 1) – Recently used & modified probably will be used again & written out
will be needed before replacing it.

101
COUNTING ALGORITHM:

[Link] algorithm:
Least frequently used page replacement algorithm.
The page with smallest count will be replaced.
Used page have larger count and the page no. larger used has small
count.
[Link] algorithm:
Most frequently used page replacement algorithm.
Based on the pages with smallest count was probably just brought in &
has get to be used.
PAGE BUFFERING ALGORITHM:

System keeps a pool of free frames.

When page fault occurs a victim page is chosen.
The particular victim frame is removed from free frame.
When the victim is later written out it is added to the free frame
pool.

THRASHING:

If the process does not have the number of frame it needs to support
pages in active use, it will quickly page fault.
At this point, it must replace some pages. However since all its pages are

102
in active use, it must replace a page that will be needed again. It quickly fault
again & again replacing pages.
This high paging activity is called thrashing. Thrashing results in severe
performance problem. Operating system monitors CPU utilization. If CPU
utilization is low, we increase the degree of multiprogramming by introducing a
new process to the system.
A global page replacement algorithm is used, to replace pages without
regard to the process, to which they begin.
Now suppose that a process enters a new face in its execution and
needs more frames it started fault takes the frames away from other
processes.
This process needs those pages, so they also fault. These faulting
processes must be use paging device to swap pages in and out.
Cpu scheduler monitors the decreasing cpu utilization and increasing
degree of multi-programming as a result.

FILE SYSTEM

File system consists of two distinct points

Collection Of Files:
103
 Each storing related data.
Directory Structure:
This organized and provides information about all the files in the
system.

FILE CONCEPT

A File is named collection of related information (i.e) recorded in

secondary storage.
A file as a creation defined structure according to its type.

Text File:
Is a sequence of characters organized into lines.

Source File:
Sequence of subroutines and functions.

Executable File:
Is a series of code section that the loader can bring the into memory and
execute.

File Types:
If an operating system recognizes the type of a file it can operate on the
file in reasonable ways.
A common technique for implementing file types is to include as part of
the file name.
The name is split into two parts.

104
 1. Name
2. Extension

Name:
Specifies the name of the file.

Extension:

Usually separated by period.

Used to identify the type of the file.
Common File
Types

105
File Structure:
File types may also be used to indicate the internal structure of the file.

Internal Structure Of The File:

The disk system typically has well defined block size, determined by the
size of a sector. All disk I/O is preformed in units of one block and all blocks are
the same size.

ACCESS METHODS

File store information when I t is used, this information must be access and

106
read into computer memory. There are several ways to access the
information.

Sequential Access:
Simplest access method. Information processed in order, one record
after the other. The operation on the file are read and write. It is based on tape
model of a file.

Sequential – access file

Direct Access Method:

It is otherwise known as relative access.
File is made up of fixed length logical record.
Based on disk model of a file.
Disk allows random access to any file block.
It is used to access large amount of information immediately.
The operation must include block number as a Para to access a
block.

Simulation of sequential access on a direct-access file

107
Other Access Method:
This is additional method, generally involve the construction of index
for the file.
The index like an index in the back of book contains pointers to the
carious blocks.
To find an entry in the file
1. First search the index.
2. Use ptr to access the file directly.
3. Find the desired entry.

Example of index and relative files

DIRECTORY STRUCTURE

108
 Directory structure provides the information about file system and
organizes and manages the system. The organization is done in two parts.

1. The file system is broken into partitions.

2. Each partition contains information about files. This information is kept in
“device directory” or “volume table of content”.

A typical file-system organization

Operation On Directory:

Search for a file- searching particular entry of a file in directory

structure.
Create a file- new file created and added directory.
Delete a file- when a file not needed remove it from directory.
List a directory- listing all files in the directory.
Rename a file- name represent the content of a file, so when content
changes its name is changed.
Traverse the file- easy to access a directory or a file this provides a

109
 backup copy in case of system failure. There are various types of directory
structures.
1. Single level directory:
Simplest directory structure.
All files are contained in same directory.
It has significant limitations.
The files must have unique names.
As the number of file increases, if is difficult to remember the
names of all files.
Single - level Directory

2. Two level directory:

Each user has their own user file directory.
It solves the name collision problem.
A file is named by giving both user name and file name.
The root is the master file directory.
Its direct descendants are UFD’s.
The files are the leaves of the tree.
Specifying a user name and file name defined path in the tree
from the root to leaf.

Two-level directory structure

110
3. Tree structured directories:
Tree is a most common directory. The tree has a two root
directory.
Each file in the system has unique path name.
A path name is the path from the root through all the
subdirectories.
Path name can be of two types:
1. Absolute path name.
2. Relative path name.

Absolute path name- begins at the root and follows a path down to the
specified files, giving the directory name on the path. Ex: root/spoll/mail/prt/
first.
Relative path name- it is defined as the path name from the current
directory.

Tree-structured directory structure

111
4. Acyclic graph structure:
It allows directories to have shared sub direct files.
It is flexible then simple tree.
Also it is complex because is has mare absolute path.
No cycles are ensured.
The deletion is done using reference list where list is empty the
file is deleted.

A cyclic-graph directory structure

112
[Link] graph directory:
Cycles are allowed in the directory structures.
When new links are added to tree structure the tree structure is
destroyed resulting in a simple graph structure. While searching a
file second search can be avoided.

General graph directory

PROTECTION

Protection can be provided in many ways.

Type Of Access:

Protection mechanism provides controlled access by limiting the types of

file access that can be made in several different types of operations can be
controlled.

113
 Read – read from the file.
Write – write or rewrite the file.
Execute – load the file into memory or execution.
Append – write new information at the
Delete – delete the file and free its space possible revise.
List – list the name and attributes of the files.
Other operations such as renaming copying, editing can also are controlled.
Access List And Groups:
The most common approach to the protection problem is to make
access dependent on the identity if the user. The most general scheme to
implement identify dependent access is to associate with each file and
directory.

Access List:
Specifies user name and type of access allowed for each user.
The main problem is due to length of access list.
These problems can be resolved by use of condensed version of
access list/
Length of access list can be condensed by the classification of user as
given below:
●Owner – the user who create the file.
●Group – a set of user who sharing the file and need similar access
in a group.
●Universe – all the users in the system belongs to universe.
Other Protection Approaches:

The other approach to the protection problem is associated a

password with each file.

114
 Access to computer system controlled by password.
Access to each file controlled by a password

CONSISTENCY SEMANTICS

This is an important criteria for evolution of any file that supports sharing
of files. It is always enclosed between open and close operations.

UNIX Semantics:
Unix file system uses the following:
Rights to open a file by a user or visible immediately to others.
There is mode of sharing.
SESSION Semantics:

Rights to open a file by a user non-visible immediately to others.

Once a file is closed the changes made to it or visible in sessions
starting later does not reflect in already opened sessions.
IMMUTABLE-Shared-Files-Semantics:

Once a file is declared as shared by its creator it can’t be modified.

It has two important properties
Its name must not be reused
Content may not be modified.

FILE SYSTEM STRUCTURE

File system structure disk provides the bulk of secondary storage on which
a file system is maintained.

115
 Disks are performed in a unit of blocks.
Each block is divided into one or more sectors.
Disks have two important characteristics
1. They can be re-written.
2. It can be accessed sequentially or randomly.

File System Organization:

File system generally composed of different levels. Each level in the design
uses the features of lower to create new feature for use by higher level.

Layered File System

I/O Control:

116
 The lowest level.
Its consist of device drivers and interrupt handlers to transfer
information between the memory and the disk system.
Basic File System:

It is needed only to issue generic commands to appropriate device

driver to read and write physical blocks on the disk.
Each disk is identified by desk address.
File Organization Module:

If is used to know about the files and their logical blocks.

It also includes the free space manager which tracks the unlocated
blocks and provides the blocks to the file organization module when
required.
Logical File System:

It is used to directory structure to provide the file organization module.

Also responsible for protection and security.

ALLOCATION METHOD

The major methods of allocating disk space are

Contiguous Allocation:

This method requires contiguous blocks on the disk. Contiguous

allocation of a file defined by the disk address and length.
If the file is n block and starts at the location b then it occupy b, b+1,
b+2…..b+n-1.
The directory entry for each file indicates the address of the starting
block and length of the space allocated for this file.
File can be accessed sequentially.

117
 Contiguous allocation of disk space

Linked Allocation:

Solves the problem of contiguous allocation

Each file is linked list of disk blocks and may scattered any where on
the disk.
The directory contains a pointer to the and last blocks.
Each block contains pointer to the next block.
Advantage: No external fragmentation.
Disadvantage: Used only for sequential access.

Space is required for pointer in the block.

Linked allocation of disk space

118
Indexed Allocation:

The pointers are brought together into a block called index block.
Each file has own index block.
Supports direct access.
It does not suffer from external fragmentation but suffer from wasted
space to store index block.

Indexed allocation of disk space

119
 FREE SPACE MANAGEMENT

Free Space List:

Keeps track of free disk space, the system maintain a free space list.
It records all disk blocks that are not allocated.

Creating A File Involves The Following Steps:

Search for free space list for the required amount of space.
And allocated the space to the new file.
The disk space is then removed from free space list.
When the file is deleted, then it is added to free space list.
[Link] Vector:

120
 The free space list is implemented as a bit vector or bit map.
Bit free block is represented by bit one.
Allocated block is a reference by bit zero.

Ex:
consider the following disk blocks,2,3,4,5,8,9,10,11,12,13,17,18,25,26&27
are free and the rest of the block are allocated. Then the bit vector would be
00001100011111111111000000000111………
Advantage:
It is effective to find free space list.

[Link] List:

Another approach is to link together all the free disk blocks, keeping a
pointer to the first free block is special location in the disk & catching it in
memory. The first block contains a pointer to the next free disk block &
so on.

[Link]:

Stores the address of n free blocks in first free block.

The first block contains n-1 free blocks.
The last block contains the address of another n free blocks and so on.

121
[Link]:

Rather than keeping a list of n free disk address.

Can keep the address of first free block and number of n free continue
blocks, which allow the first block.
Each entry in free space list consists of disk address and count.

UNIT - 5
I/O SYSTEMS

The two main jobs of a computer are I/O and processing. The main job is I/
O and the processing is merely incidental. We browse a web page or edit a file,
our immediate interest is to read or enter some information, not to compute
an answer.

The role of the operating system in computer I/O is to manage and control
I/O operations and I/O devices.

I/O devices vary so widely in their function and speed (mouse, hard disk
and CD-ROM), a variety of methods are needed to control them.

I/O HARDWARE

Computers operate a great many kinds of devices. Most fit into the

general categories of storage devices(disks, tapes) transmission
devices(network cards, modem)and human interface devices(screen,
keyboard, mouse)

122
 A device communicates with a computer system by sending signals
over a cable or even through the air. The device communicates with the
machine via a connection point(or port).

A Typical PC Bus Structure

If one or more devices use a common set of wires, the connection is

called a bus. A bus is set of wires and a rigidly defined protocol that
specifies a set of messages that can be sent on the wires.
A PCI bus that connects the processor-memory subsystem to the fast
devices and an expansion bus that connects relatively slow devices
such as the keyboard and serial and parallel ports.
For disks are connected together on a SCSI bus plugged into a SCSI
controller.
A controller is a collection of electronics that can operate a port, a bus,
or a device.
A SCSI bus controller is not simple because the SCSI protocol is
complex, the SCSI bus controller is implemented in a separate circuit
board (host adapter) that plugs into a computer.
An I/O port typically consists of four registers, called the status, control,
data-in and data-out registers.

Device I/O Port Locations on PCs (partial)

123
Polling
Determines state of device
ocommand-ready
obusy
oError
Busy-wait cycle to wait for I/O from device

Interrupts
CPU Interrupt-request line triggered by I/O device
Interrupt handler receives interrupts
Maskable to ignore or delay some interrupts
Interrupt vector to dispatch interrupt to correct handler
oBased on priority
oSome nonmaskable
Interrupt mechanism also used for exceptions

Interrupt-Driven I/O Cycle

124
 Intel Pentium Processor Event-Vector Table

125
Direct Memory Access

Used to avoid programmed I/O for large data movement

Requires DMA controller
Bypasses CPU to transfer data directly between I/O device and
memory

Six Step Process to Perform DMA Transfer

126
 APPLICATION I/O INTERFACE

Application can open a file on a disk without knowing what kind of disk
it is, and how new disks and other devices can be added to a computer
without the operating system being disrupted.
Making the I/O subsystem independent of the hardware simplifies the
job of the operating system developer.

127
 A kernel I/O structure

Devices vary in many dimensions, as illustrated

●Character-stream or block : A character-stream device transfers
bytes one by one, whereas a block device transfers a block of
bytes as a unit.
●Sequential or random-access : A sequential device transfers data in
a fixed order determined by the device, whereas the user of a
random-access device can instruct the device to seek to any of
the available data storage locations.
●Synchronous or Asynchronous : A synchronous device is one that
performs data transfers with predictable response times. An
asynchronous device exhibits irregular or unpredictable response
time.
●Sharable or dedicated : A sharable device can be used concurrently
by several processes or threads, a dedicated device cannot.
●Speed of operation : Device speeds range from a few bytes per
second to a few gigabytes per second.

128
 ●Read-write, read only, or write only : Some devices perform both
input and output, but others support only one data direction.

Characteristics of I/O Devices

BLOCK AND CHARACTER DEVICES :

The block-device interface captures all the aspects necessary for

accessing disk drives and other block-oriented devices.
The expectation is that the device understands commands such as
read( ) and write( ) and if it is a random access device seek( ) command
to specify which block to transfer next.
In a character-stream interface, enable an application to get( ) or put( )
one character.
This style of access is convenient for input devices such as keyboards,
mice, and modem.

NETWORK DEVICES :
The performance and addressing characteristics of network I/O differ
significantly from those of disk I/O, most operating system provide a
network I/O interface that is different from the read( ),write( ) and seek( )
interface used for disks.
129
 To support the implementation of servers, the sockets interface also
provides a function called select( ) that manages a set of sockets.

CLOCKS AND TIMERS :

Most computers have hardware clocks and timers that provide three basic
functions :
● Give the current time.
● Give the elapsed time.
● Set a timer to trigger operation X at time T.
These functions are used heavily by the operating system and also by
time- sensitive applications.
The hardware to measure elapsed time and to trigger operations is called
a programmable interval timer.

BLOCKING AND NONBLOCKING I/O :

Another aspect of the system-call interface relates to the choice between
blocking I/O and non blocking(or asynchronous) I/O.
When an application issues a blocking system call, the execution of the
application is suspended. The application is moved from the operating
system’s run queue to a wait queue.
Some user-level processes need non blocking I/O. User interface that
receives keyboard and mouse input while processing and displaying data
on the screen.

Two I/O Methods

KERNEL I/O SUBSYSTEM

130
 I/O Scheduling
●Some I/O request ordering via per-device queue
●Some OS try fairness

Buffering - store data in memory while transferring between devices

●To cope with device speed mismatch
●To cope with device transfer size mismatch
● To maintain “copy semantics”

Sun Enterprise 6000 Device-Transfer Rates

Caching - fast memory holding copy of data

131
 ●Always just a copy
●Key to performance

Spooling - hold output for a device

●If device can serve only one request at a time
●i.e., Printing

Device reservation - provides exclusive access to a device

●System calls for allocation and de allocation
●Watch out for deadlock

Error Handling
OS can recover from disk read, device unavailable, transient write
failures
Most return an error number or code when I/O request fails
System error logs hold problem reports.

I/O Protection

User process may accidentally or purposefully attempt to disrupt

normal operation via illegal I/O instructions
o All I/O instructions defined to be privileged
o I/O must be performed via system calls
●Memory-mapped and I/O port memory locations must
be protected too

Kernel Data Structures

Kernel keeps state info for I/O components, including open file
tables, network connections, character device state
Many, many complex data structures to track buffers, memory
allocation, “dirty” blocks
Some use object-oriented methods and message passing to
implement I/O

132
 UNIX I/O Kernel Structure

TRANSFORMING I/O TO HARDWARE OPERATIONS

A process issues a blocking read( ) system call to a file descriptor of a

file that has been opened previously.
The system call cede in the kernel checks the parameters for
correctness. In the case of input, if the data are already available in the
buffer cache, the data are returned to the process and the I/O request is
completed.
Otherwise, a physical I/O needs to be performed, so the process is
removed from the run queue and is placed on the wait queue for the
device and the I/O request is scheduled. Eventually, the I/O subsystem
sends the request to the device driver. Depending on the OS, the request
is sent via a subroutine call or via an in-kernel message.
The device driver allocates kernel buffer space to receive the data and
schedules the I/O. Eventually the driver sends commands to the device

133
 controller by writing into the device control registers.
The device controller operates the device hardware to perform the data
transfer.
The driver may poll fro status and data or it may have set up a DMA
transfer into kernel memory. The transfer is managed by a DMA
controller, which generates an interrupt when the transfer completes.
The correct interrupt handler receives the interrupt via the interrupt-
vector table, stores any necessary data, signals the device driver and
returns from the interrupt.

Life Cycle of an I/O Request

134
 The device driver receives the signal, determines which I/O request
completed, determines the request’s status and signals the kernel I/O
subsystem that the request has been completed.
The kernel transfers data or return codes to the address space of the
requesting process and moves the process from the wait queue back to
the ready queue.
Moving the process to the ready queue unblocks the process. When
the scheduler assigns the process to the CPU, the process resumes
execution at the completion of the system call.

135
 PERFORMANCE

I/O a major factor in system performance:

oDemands CPU to execute device driver, kernel I/O code
oContext switches due to interrupts
oData copying
oNetwork traffic especially stressful

Intercomputer Communications

Improving Performance
Reduce number of context switches
Reduce data copying
Reduce interrupts by using large transfers, smart controllers, polling
Use DMA
Balance CPU, memory, bus, and I/O performance for highest
throughput

136
 Device-Functionality Progression

SECONDARY STORAGE STRUCTURE

Disks provide the bulk of secondary storage for modern computer

systems. Magnetic tape was used as an early secondary-storage medium, but
the access time is much slower than for disks.

PROTECTION

Protection refers to a mechanism for controlling the access of programs,

processes of users to the resources defined by a computer system. This
mechanism must provide a means for specification of the control to be
imposed, together with some means of enforcement.

137
GOALS OF PROTECTION

Protection was originally conceived as an adjunct to multiprogramming

operating systems, so that untrustworthy users might safely share a
common logical name space, such as directory of files or share a
common physical name space, such as memory.

To increase the reliability of any complex system that makes use of

shared resources.

The need to prevent mischievous, intentional violation of an access

restriction by a user.

Protection can improve reliability by detecting latent errors at the

interfaces between component subsystems.

An unprotected resource cannot defend against use (or misuse) by an

unauthorized or incompetent user.

Policy is distinct from mechanism. Mechanisms determine how

something will be done, Policies decide what will be done.

The separation of policy and mechanism is important for flexibility.

Policies are likely to change from place to place or time to time.

DOMAIN OF PROTECTION

A computer system is a collection of processes and objects. By object

means both hardware and software objects.

Each object has a unique name that differentiates it from all other
objects in the system, and each can be accessed only through well-
defined and meaningful operation.

The operations that are possible may depend on the object.

CPU – Execute.
Memory segments - Read and write.
CD-ROM - Read.
Tape drives - read, written, and rewound.
Data files - created, opened, read, written, closed and deleted.

138
 program files - read, written, executed and deleted.

A process should be allowed to access only those resources for which

it has authorization.

DOMAIN STRUCTURE :

Each domain defines a set of objects and the types of operations that
may be invoked on each object.

The ability to execute an operation on an object is an access rights.

A Domain is a collection of access rights, each of which is an ordered

pair <object-name,rights-set> where rights-set is a subset of all valid
operations that can be performed on the object.

A domain can be realized in a variety of ways:

Each user may be a domain. Domain switching occurs when the user is
changed generally when one user logs out and another user logs in.

Each process may be a domain. Domain switching corresponds to one

process sending a message to another process and the waiting for a
response.

Each procedure may be a domain. The set of objects that can be

accessed corresponds to the local variables defined within the
procedure. Domain switching occurs when a procedure call is made.

Domain Implementation (UNIX)

Switching the domain corresponds to changing the user identification

139
 temporarily.

An owner identification and a domain bit(setuid bit) are associated with

each file.

When a user (with user-id=A) starts executing a file owned by B, whose

associated domain bit is off, the user-id of the process is set to A.

When the setuid bit is on, the user-id is set to that of the owner of the
file B. When the process exits, this temporary user-id change ends.

Domain Implementation (MULTICS)

● The protection domains are organized hierarchically into a ring

structure.

● Let Di and Dj be any two domain rings.

● If j < i then Di is a subset of Dj.

● A process executing in domain Dj has more privileges than does a

process executing in domain Di.

ACCESS MATRIX

140
 Our model of protection can be viewed abstractly as a matrix called an
access matrix.
The rows of the access matrix represent domains and the column
represent objects.
The entry access(i,j) defines the set of operations that a process,
executing in domain Di, can invoke on object Oj.
There are four domains and four objects, three files(F1,F2,F3) and one laser
printer.
When a process executes in domain D1 it can read files F1 and F3. A process
executing in domain D4 has the same privileges as it does in domain D1
but in addition, it can also write onto files F1 and F3.
The laser printer can be accessed only by a process executing in domain
D2.

Access Matrix

Process switch from one domain to another. Domain switching from

domain Di to domain Dj is allowed to occur if and only if the access right
switch to access(i,j).

A process executing in domain D2 can switch to domain D3 or to domain

D4.

A process in domain D4 can switch to D1 and one in domain D1 can

switch to domain D2.

141
 Access matrix with domain as objects

Allowing controlled change to the contents of the access-matrix entries

requires three additional operations :

● Copy

● Owner

● Control

The ability to copy an access right from one domain (row) of the access
matrix to another is denoted by an asterisk(*) appended to the access right.

This scheme has two variants:

1. A right is copied from access(i,j) to access(k,j); it is then removed from

access(i,j); this action is a transfer of a right, rather than a copy.

2. Propagation of the copy right may be limited. When the right R* is

copied from access(i,j) to access(k,j) only the right R(not R*) is created.
A process executing in domain Dk cannot further copy the right R.

142
 Access matrix with copy rights

To allow addition of new rights and removal of some rights.

The owner right controls these operations. If access(i,j) includes the owner
right, then a process executing in domain Di can add and remove any right
in any entry in column j.

Domain D2 is the owner of F2 and F3, and thus can add and remove any
valid right within these two columns.

143
 Access Matrix With Owner Rights

The control rights is applicable only to domain objects.

If access(i,j) includes the control right, then a process executing in domain
Di can remove any access right from row j.

Modified Access Matrix

144
 THE SECURITY PROBLEM

The operating system can provide (with appropriate aid from the
hardware) that allow user to protect their resources(usually program &
data).
Security violations (or misuse) of the system can be categorized as
intentional (malicious) or accidental. It is easier to protect against
accidental misuse than against malicious misuse.
Malicious access are the following:
● Unauthorized reading of data (or theft of information).
● Unauthorized modification of data.
● Unauthorized destruction of data.
● Preventing legitimate use of the system (or denial of service).

Standard Security Attacks

145
 To protect the system, we must take security measures at four levels:
1. Physical: The site or sites containing the computer systems must be
physically secured against armed or surreptitious entry by intruders.
2. Human: Users must be screened carefully to reduce the chance of
authorizing a user who then gives access to an intruder (in exchange for
a bribe, for example).
3. Network: Much computer data in modern systems travels over private
leased lines, shared lines like the internet, of dial-up lines. The
interception of this data could be just as harmful as the break-in of a
computer. The interruption of these communications could be a remote
denial-of-service attack and diminish user’s use of and trust of the
system.
4. Operating system: The system must protect itself from accidental or
purposeful security breaches.

AUTHENTICATION

Authentication is a process of verifying whether a person is a legitimate

user or not. We have two types of authentication process.
1. Centralized environment.
2. Distributed environment.

Centralized Environment :

Authentication in this environment can be achieved in the following three

ways :

● A secret, known only to that user (eg, password)

● Something possessed only by that user (eg, magnetic badge)
● Some human characteristics of the user (eg, handwritten signature,
finger prints, retina images)

Distributed Environment :

146
 A message passing through the network can be tapped at multiple
locations in distributed systems.

● Location of encryption devices.

● Key distribution.
● Traffic padding.
● Message Authentication.

USER AUTHENTICATION

A major security problem for operating systems is authentication. The

protection system depends on an ability to identify the programs and
processes currently executing.
Authentication is based on one or more of three items: user possession
(a key or card), user knowledge(a user identifier and password) and / or a user
attribute(fingerprint, retina pattern or signature).

PASSWORD :

To authenticating a user identity is the use of passwords. When the

user identifies herself by user ID or account name and password.
Whenever a request is made to use the resource, the password must
be given. If the password is correct, access is granted.
Different passwords may be used for each of the following file
operations: reading, appending and updating.

PASSWORD VULNERABILITIES :

Passwords are extremely common because they are easy to

understand and use. Unfortunately, passwords can often be guessed.
There are two common ways to guess a password.
1. The intruder to know the user or to have information about the user.
2. All possible combinations of letters, numbers and punctuation, until
the password is found.
An intruder can look over the shoulder of a user (shoulder surfing)
when the user is logging in and can learn the password easily by
watching the keyboard.

147
 Some systems force the user to select hard-to-remember or long
passwords.
Less security than systems that allow easy passwords.
Some systems also age passwords, forcing users to change their
passwords at regular intervals(every 3 months).

ENCRYPTED PASSWORDS :

The UNIX system uses encryption to avoid the necessity of keeping its
password list secret.
Given a function value f(x), however it is impossible to compute x. This
function is used to encode all passwords. Only encoded passwords are
stored.
When a user presents a password, it is encoded and compared against
the stored encoded password.
For eg, The phrase “My mother’s name is katherine”, the password is
“Mmnisk”.

ONE TIME PASSWORDS :

To avoid the problems of password sniffing and shoulder surfing, a

system could use a set of paired passwords.
When a session begins, the system randomly selects and presents one
part of a password pair; the user must supply the other part. The user is
challenged and must respond with the correct answer to that challenge.
The password is different in each instance. Any one capturing the
password from one session and trying to reuse it in another session will
fail.
One-time passwords are among the only ways to prevent improper
authentication due to password exposure.

BIOMETRICS :

Palm or hand-readers are common to secure physical access.

These readers match stored parameters against what is being read
from their hand-reader pad.
The parameters can include a temperature map, as well as finger
length, finger width and line patterns.
Finger print readers have become accurate and cost-effective and
148
 should become more common in the future. These devices read your
finger’s ridge patterns and convert then into a sequence of
numbers.

ADDITIONAL PASSWORDS :

Some OS ask for multiple passwords at different levels. This makes

penetration more difficult.
This provides more security.

CONTINUOS CHALLENGE :

An OS, at random intervals may ask predetermined questions to the

user challenging him to prove his identity.
Ex:
1. Where you born?
2. What is your exact height in inches?

PROGRAM THREATS

When a program written by one user may be used by another user, misuse
and unexpected behavior may ensue.

Trojan Horse :

Many System have mechanisms for allowing programs written by

users to be executed by other users.
If these programs are executed in a domain that provides the access
rights of the executing user, the other users may misuse these rights.
A Code segment that misuses its environment.
A variation of the Trojan horse is a program that emulates a login
program.
An unsuspecting user starts to log in at a terminal and mistyped the
password. He tries again and is successful.
The authentication and password have been stolen by the login
emulator that was left running on the terminal by the thief.

149
Trap Door :

The code might check for a specific user ID or password and it might
circumvent normal security procedures.
A clever trap door could be included in a compiler.
The compiler could generate standard object code as well as a trap
door, regardless of the source code being compiled.
Trap door pose a difficult problem because to detect them, we have to
analyze all the source code for all components of a system.

Stack and Buffer Overflow :

The Stack or buffer-overflow attack is the most common way for an

attacker outside of the system, on a network or dial-up connection, to
gain unauthorized access to the target system.
The attack exploits a bug in a program.
The attacker determines the vulnerability and writes a program to do
the following:
● Overflow an input field.
● Overwrite the current return address on the stack with the
address of the exploit code.
● Write a simple set of code for the next space in the stack that
includes the commands that the attacker wishes to execute.
If a web page form expects a user name to be entered into a field, the
attacker could send the user name, plus extra characters to overflow the
buffer and reach the stack, plus a new return address to load onto the
stack, plus the code the attacker wants to run.

SYSTEM AND NETWORK THREATS

It is possible to create a situation where operating system resources and

user files are misused.

WORMS :

A worm is a program spreads to other computer or nodes over a

150
 network and bring the entire network to halt.
It does not harm any other program or data. It is usually operates on a
network.
Each node maintains a list of all other nodes on the network and also a
mailing list which contains the name and address of the reachable
machine on the network.
It gets the mailing list and sending a copy to all nodes. As a result of
this continuous transfer over the network a major portion of the network
resources such as disk capacity, transmission capacity, network buffer
thus denial service to the legitimate user.

Internet Worms :

In November 2, 1988 Robert tappn morris, cornell graduate student

introduces a worm into internet.
Internet is a network connecting thousands of computers , hundreds of
corporation, Universities, laboratories and government organizations in
the world.
The worm brought down the entire network.
Morris wrote a self duplicating program named worm. This program to
fool the users and down the entire network.
A friend of morris let-out this secret to a ‘Newyork times reporter’.This
story is published in the front page of the newspaper.
Finally Morris was punished three years custody and fine of Ten
thousand US dollars.
The worm was made up of two programs, a grappling hook(also called
as bootstrap or vector) program and the main program. daemon

The Morris Internet Worm

151
Cryptography as a Security Tool
Cryptography enables a recipient of a message to verify that the
message was created by some computer possessing a certain key –
the key is the source of the message.
A sender can encode its message so that only a computer with a
certain key can decode the message so that the key becomes the
destination.

VIRUSES :

viruses are designed to spread into other programs and can wreak
havoc in a system, including modifying of destroying files and causing
system crashes and program malfunctions.

A virus is a fragment of code embedded in legitimate program .

Viruses are usually spread by users downloading viral programs from

public bulletin boards or exchanging disks containing an infection.

In Feb 1992, two Cornell University students developed three

Macintosh game programs with an embedded virus and distributed
them to worldwide software archives via the Internet.

In recent years, a common form of virus transmission has been via the
exchange of Microsoft Office files, such as Microsoft Word documents.

152
 Purchasing unopened software from vendors and avoiding free or
pirated copies from public sources or disk exchange is the safest route
to preventing infection.
Even new copies of legitimate software applications are not immune to
virus infection.
To avoid opening any email attachments from unknown users.

Denial of Service :

Denial of service does not involve gaining information or stealing

resources, but rather disabling legitimate use of a system or facility.
An intruder could delete all the files on a system.
These attacks are generally network based. They fall in two categories,
1. An attack that uses so many facility resources that no useful work
can be done.
2. Disrupting the network of the facility.

ENCRYPTION

Encryption algorithm consists of

● Set of K keys
● Set of M Messages
● Set of C cipher texts (encrypted messages)
● A function E : K (M C). That is, for each k K, E(k) is a
function for generating cipher texts from messages
● Both E and E(k) for any k should be efficiently computable
functions
● A function D : K (C M). That is, for each k K, D(k) is a
function for generating messages from cipher texts
● Both D and D(k) for any k should be efficiently computable
functions
An encryption algorithm must provide this essential property: Given
a cipher text c C, a computer can compute m such that E(k)(m) = c
only if it possesses D(k).
● Thus, a computer holding D(k) can decrypt cipher texts to the
153
 plaintexts used to produce them, but a computer not holding D(k)
cannot decrypt cipher texts
● Since cipher texts are generally exposed (for example, sent on
the network), it is important that it be infeasible to derive D(k)
from the cipher texts

SYMMETRIC ENCRYPTION :

Same key used to encrypt and decrypt

● E(k) can be derived from D(k), and vice versa
DES is most commonly used symmetric block-encryption algorithm
(created by US Govt)
● Encrypts a block of data at a time
Triple-DES considered more secure
Advanced Encryption Standard (AES), two fish up and coming
RC4 is most common symmetric stream cipher, but known to have
vulnerabilities
● Encrypts/decrypts a stream of bytes (i.e wireless transmission)
● Key is a input to pseudo-random-bit generator
● Generates an infinite key stream
ASYMMETRIC ENCRYPTION :

Public-key encryption based on each user having two keys:

● public key – published key used to encrypt data.
● private key – key known only to individual user used to decrypt
data.
Must be an encryption scheme that can be made public without
making it easy to figure out the decryption scheme.
● Most common is RSA block cipher.
● Efficient algorithm for testing whether or not a number is prime
● No efficient algorithm is known for finding the prime factors of a
number.

Formally, it is computationally infeasible to derive D(kd , N) from

E(ke , N), and so E(ke , N) need not be kept secret and can be widely
disseminated
●E(ke , N) (or just ke) is the public key
●D(kd , N) (or just kd) is the private key
●N is the product of two large, randomly chosen prime numbers p
154
 and q (for example, p and q are 512 bits each)
●Encryption algorithm is E(ke , N)(m) = mke mod N, where ke
satisfies kekd mod (p−1)(q −1) = 1
● The decryption algorithm is then D(kd , N)(c) = ckd mod N

Secure Communication over Insecure Medium

155