DEPT.

OF COMPUTER SCIENCE

ADIKAVI NANNAYA UNIVERSITY

MSN CAMPUS – KAKINADA
DEPARTMENT OF COMPUTER SCIENCE
MASTER OF COMPUTER APPLICATIONS
SUBJECT- (19105) OPERATING SYSTEMS MATERIAL

UNIT- I
TOPICS

Introduction: Page no:

1.0 Definition of Operating System 2

1.1 Types of Operating Systems 5

1.2 Operating System Structures 8

1.3 Operating-System Services 10

1.4 System Calls 13

1.5 Virtual Machines 14

1.6 Operating System Design and 18

Implementation

Process Management: Page No

1.7 Process Concepts 22

1.8 Operations on Processes 23

1.9 Cooperating Processes 24

1.10 Threads 26

1.11 Inter Process Communication 32

1.12 Process Scheduling 35

1.13 Scheduling Algorithms 42

1.14 Multiple - Processor 48

Scheduling
1.15 Thread Scheduling 48

B.V.A.SWAMY 1|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.0

Topic: 1.0 Definition of Operating System

INTRODUCTION :
An Operating System (OS) is an interface between a computer user and computer
hardware. An operating system is a software which performs all the basic tasks like file
management, memory management, process management, handling input and output, and
controlling peripheral devices such as disk drives and printers.
Some popular Operating Systems include Linux Operating System, Windows Operating
System, VMS, OS/400, AIX, z/OS, etc.

1) Definition of Operating System and functions of operating systems?

Ans: An operating system is a program that acts as an interface between the user and the
computer hardware and controls the execution of all kinds of programs.

Operating system goals:

• Execute user programs and make solving user problems easier.
• Make the computer system convenient to use.
• Use the computer hardware in an efficient manner.

Computer System Components

1. Hardware – provides basic computing resources (CPU, memory, I/O devices).
2. Operating system – controls and coordinates the use of the hardware among the various
application
programs for the various users.
3. Applications programs – Define the ways in which the system resources are used to solve
the computing
problems of the users (compilers, database systems, video games, business programs).
4. Users (people, machines, other computers).

B.V.A.SWAMY 2|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.0

1
Following are some of important functions of an operating System.

• Memory Management
• Processor Management
• Device Management
• File Management
• Security
• Control over system performance
• Job accounting
• Error detecting aids
• Coordination between other software and users

a) Memory Management
Memory management refers to management of Primary Memory or Main Memory. Main
memory is a large array of words or bytes where each word or byte has its own address.
Main memory provides a fast storage that can be accessed directly by the CPU. For a
program to be executed, it must in the main memory. An Operating System does the following
activities for memory management −
• Keeps tracks of primary memory, i.e., what part of it are in use by whom, what part
are not in use.
• In multiprogramming, the OS decides which process will get memory when and how
much.
• Allocates the memory when a process requests it to do so.
• De-allocates the memory when a process no longer needs it or has been terminated.

b) Processor Management
In multiprogramming environment, the OS decides which process gets the processor
when and for how much time. This function is called process scheduling. An Operating
System does the following activities for processor management −
• Keeps tracks of processor and status of process. The program responsible for this
task is known as traffic controller.
• Allocates the processor (CPU) to a process.
• De-allocates processor when a process is no longer required.
c) Device Management
An Operating System manages device communication via their respective drivers. It does
the following activities for device management −
• Keeps tracks of all devices. Program responsible for this task is known as the I/O
controller.
• Decides which process gets the device when and for how much time.
• Allocates the device in the efficient way.

B.V.A.SWAMY 3|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.0

d) File Management
A file system is normally organized into directories for easy navigation and usage. These
directories may contain files and other directions.
An Operating System does the following activities for file management −
• Keeps track of information, location, uses, status etc. The collective facilities are often
known as file system.
• Decides who gets the resources.
• Allocates the resources.
• De-allocates the resources.

e) Other Important Activities

Following are some of the important activities that an Operating System performs −
• Security − By means of password and similar other techniques, it prevents
unauthorized access to programs and data.
• Control over system performance − Recording delays between request for a
service and response from the system.
• Job accounting − Keeping track of time and resources used by various jobs and
users.
• Error detecting aids − Production of dumps, traces, error messages, and other
debugging and error detecting aids.
• Coordination between other softwares and users − Coordination and assignment
of compilers, interpreters, assemblers and other software to the various users of the
computer systems.

B.V.A.SWAMY 4|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.1

Topic: 1.1 Types of Operating Systems

2) Explain types of Operating systems?
Ans: Some of the important types of operating systems which are most commonly
used.
I. Batch operating system
II. Time-sharing operating systems
III. Distributed operating system
IV. Network operating system
V. Real time operating system

a) Batch operating system

The users of a batch operating system do not interact with the computer directly. Each
user prepares his job on an off-line device like punch cards and submits it to the computer
operator. To speed up processing, jobs with similar needs are batched together and run as
a group. The programmers leave their programs with the operator and the operator then sorts
the programs with similar requirements into batches.
The problems with Batch Systems are as follows −

• Lack of interaction between the user and the job.

• CPU is often idle, because the speed of the mechanical I/O devices is slower than the
CPU.
• Difficult to provide the desired priority.

b) Time-sharing operating systems

Time-sharing is a technique which enables many people, located at various terminals, to
use a particular computer system at the same time. Time-sharing or multitasking is a logical
extension of multiprogramming. Processor's time which is shared among multiple users
simultaneously is termed as time-sharing.
The main difference between Multiprogrammed Batch Systems and Time-Sharing
Systems is that in case of Multiprogrammed batch systems, the objective is to maximize
processor use, whereas in Time-Sharing Systems, the objective is to minimize response time.
Multiple jobs are executed by the CPU by switching between them, but the switches occur
so frequently. Thus, the user can receive an immediate response. For example, in a
transaction processing, the processor executes each user program in a short burst or
quantum of computation. That is, if n users are present, then each user can get a time
quantum. When the user submits the command, the response time is in few seconds at most.
The operating system uses CPU scheduling and multiprogramming to provide each user
with a small portion of a time. Computer systems that were designed primarily as batch
systems have been modified to time-sharing systems.

Advantages of Timesharing operating systems are as follows −

B.V.A.SWAMY 5|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.1

• Provides the advantage of quick response.

• Avoids duplication of software.
• Reduces CPU idle time.
Disadvantages of Time-sharing operating systems are as follows −

• Problem of reliability.
• Question of security and integrity of user programs and data.
• Problem of data communication.

c) Distributed operating System

Distributed systems use multiple central processors to serve multiple real-time
applications and multiple users. Data processing jobs are distributed among the processors
accordingly.
The processors communicate with one another through various communication lines
(such as high-speed buses or telephone lines). These are referred as loosely coupled
systems or distributed systems. Processors in a distributed system may vary in size and
function. These processors are referred as sites, nodes, computers, and so on.
The advantages of distributed systems are as follows −

• With resource sharing facility, a user at one site may be able to use the resources
available at another.
• Speedup the exchange of data with one another via electronic mail.
• If one site fails in a distributed system, the remaining sites can potentially continue
operating.
• Better service to the customers.
• Reduction of the load on the host computer.
• Reduction of delays in data processing.

d) Network operating System

A Network Operating System runs on a server and provides the server the capability to
manage data, users, groups, security, applications, and other networking functions. The
primary purpose of the network operating system is to allow shared file and printer access
among multiple computers in a network, typically a local area network (LAN), a private
network or to other networks.
Examples of network operating systems include Microsoft Windows Server 2003,
Microsoft Windows Server 2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD.

B.V.A.SWAMY 6|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.1

The advantages of network operating systems are as follows −

• Centralized servers are highly stable.

• Security is server managed.
• Upgrades to new technologies and hardware can be easily integrated into the system.
• Remote access to servers is possible from different locations and types of systems.
The disadvantages of network operating systems are as follows −

• High cost of buying and running a server.

• Dependency on a central location for most operations.
• Regular maintenance and updates are required.

e) Real Time operating System

A real-time system is defined as a data processing system in which the time interval
required to process and respond to inputs is so small that it controls the environment. The
time taken by the system to respond to an input and display of required updated information
is termed as the response time. So in this method, the response time is very less as
compared to online processing.
Real-time systems are used when there are rigid time requirements on the operation of a
processor or the flow of data and real-time systems can be used as a control device in a
dedicated application. A real-time operating system must have well-defined, fixed time
constraints, otherwise the system will fail. For example, Scientific experiments, medical
imaging systems, industrial control systems, weapon systems, robots, air traffic control
systems, etc.
There are two types of real-time operating systems.
Hard real-time systems
Hard real-time systems guarantee that critical tasks complete on time. In hard real-time
systems, secondary storage is limited or missing and the data is stored in ROM. In these
systems, virtual memory is almost never found.
Soft real-time systems
Soft real-time systems are less restrictive. A critical real-time task gets priority over other
tasks and retains the priority until it completes. Soft real-time systems have limited utility than
hard real-time systems. For example, multimedia, virtual reality, Advanced Scientific Projects
like undersea exploration and planetary rovers, etc.

B.V.A.SWAMY 7|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.2

Topic: 1.2 Operating System Structures

3) Different approaches or Structures of operating systems?
Ans: Operating system can be implemented with the help of various structures. The
structure of the OS depends mainly on how the various common components of the
operating system are interconnected and melded into the kernel. Depending on this we have
following structures of the operating system:
Simple structure:
Such operating systems do not have well defined structure and are small, simple and
limited systems. The interfaces and levels of functionality are not well separated. MS-DOS
is an example of such operating system. In MS-DOS application programs are able to
access the basic I/O routines. These types of operating system cause the entire system to
crash if one of the user programs fails.

Diagram of the structure of MS-DOS is shown below.

Layered structure:
An OS can be broken into pieces and retain much more control on system. In this
structure the OS is broken into number of layers (levels). The bottom layer (layer 0) is the
hardware and the topmost layer (layer N) is the user interface. These layers are so
designed that each layer uses the functions of the lower level layers only. This simplifies
the debugging process as if lower level layers are debugged and an error occurs during
debugging then the error must be on that layer only as the lower level layers have already
been debugged.

The main disadvantage of this structure is that at each layer, the data needs to be
modified and passed on which adds overhead to the system. Moreover careful planning of
the layers is necessary as a layer can use only lower level layers. UNIX is an example of
this structure.

B.V.A.SWAMY 8|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.2

Micro-kernel:
This structure designs the operating system by removing all non-essential
components from the kernel and implementing them as system and user programs. This
result in a smaller kernel called the micro-kernel.
Advantages of this structure are that all new services need to be added to user space and
does not require the kernel to be modified. Thus it is more secure and reliable as if a service
fails then rest of the operating system remains untouched. Mac OS is an example of this
type of OS.

Modular structure or approach:

It is considered as the best approach for an OS. It involves designing of a modular
kernel. The kernel has only set of core components and other services are added as
dynamically loadable modules to the kernel either during run time or boot time. It
resembles layered structure due to the fact that each kernel has defined and protected
interfaces but it is more flexible than the layered structure as a module can call any other
module.
For example Solaris OS is organized as shown in the figure.

B.V.A.SWAMY 9|Page
DEPT. OF COMPUTER SCIENCE

Topic: 1.3

Topic: 1.3 Operating-System Services

4) Explain Operating system Services ?
Ans: An Operating System provides services to both the users and to the programs.

• It provides programs an environment to execute.

• It provides users the services to execute the programs in a convenient manner.
Following are a few common services provided by an operating system −

• Program execution
• I/O operations
• File System manipulation
• Communication
• Error Detection
• Resource Allocation
• Protection

a) Program execution
Operating systems handle many kinds of activities from user programs to system programs
like printer spooler, name servers, file server, etc. Each of these activities is encapsulated as
a process.
A process includes the complete execution context (code to execute, data to manipulate,
registers, OS resources in use). Following are the major activities of an operating system with
respect to program management −

• Loads a program into memory.

• Executes the program.
• Handles program's execution.
• Provides a mechanism for process synchronization.
• Provides a mechanism for process communication.
• Provides a mechanism for deadlock handling.

b) I/O Operation
An I/O subsystem comprises of I/O devices and their corresponding driver software. Drivers
hide the peculiarities of specific hardware devices from the users.
An Operating System manages the communication between user and device drivers.

• I/O operation means read or write operation with any file or any specific I/O device.
• Operating system provides the access to the required I/O device when required.

c) File system manipulation

A file represents a collection of related information. Computers can store files on the disk
(secondary storage), for long-term storage purpose. Examples of storage media include
B.V.A.SWAMY 10 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.3

magnetic tape, magnetic disk and optical disk drives like CD, DVD. Each of these media has
its own properties like speed, capacity, data transfer rate and data access methods.
A file system is normally organized into directories for easy navigation and usage. These
directories may contain files and other directions. Following are the major activities of an
operating system with respect to file management −

• Program needs to read a file or write a file.

• The operating system gives the permission to the program for operation on file.
• Permission varies from read-only, read-write, denied and so on.
• Operating System provides an interface to the user to create/delete files.
• Operating System provides an interface to the user to create/delete directories.
• Operating System provides an interface to create the backup of file system.

d) Communication
In case of distributed systems which are a collection of processors that do not share memory,
peripheral devices, or a clock, the operating system manages communications between all
the processes. Multiple processes communicate with one another through communication
lines in the network.
The OS handles routing and connection strategies, and the problems of contention and
security. Following are the major activities of an operating system with respect to
communication −

• Two processes often require data to be transferred between them

• Both the processes can be on one computer or on different computers, but are
connected through a computer network.
• Communication may be implemented by two methods, either by Shared Memory or by
Message Passing.

e) Error handling
Errors can occur anytime and anywhere. An error may occur in CPU, in I/O devices or in the
memory hardware. Following are the major activities of an operating system with respect to
error handling −

• The OS constantly checks for possible errors.

• The OS takes an appropriate action to ensure correct and consistent computing.

f) Resource Management
In case of multi-user or multi-tasking environment, resources such as main memory, CPU
cycles and files storage are to be allocated to each user or job. Following are the major
activities of an operating system with respect to resource management −

• The OS manages all kinds of resources using schedulers.

• CPU scheduling algorithms are used for better utilization of CPU.

B.V.A.SWAMY 11 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.3

g) Protection
Considering a computer system having multiple users and concurrent execution of multiple
processes, the various processes must be protected from each other's activities.
Protection refers to a mechanism or a way to control the access of programs, processes, or
users to the resources defined by a computer system. Following are the major activities of an
operating system with respect to protection −

• The OS ensures that all access to system resources is controlled.

• The OS ensures that external I/O devices are protected from invalid access attempts.
• The OS provides authentication features for each user by means of passwords.

B.V.A.SWAMY 12 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.4

Topic: 1.4 System calls

5) Explain about System calls in operating system ?

Ans: The interface between a process and an operating system is provided by system calls.
In general, system calls are available as assembly language instructions. They are also
included in the manuals used by the assembly level programmers. System calls are usually
made when a process in user mode requires access to a resource. Then it requests the kernel
to provide the resource via a system call.
A figure representing the execution of the system call is given as follows −

As can be seen from this diagram, the processes execute normally in the user mode
until a system call interrupts this. Then the system call is executed on a priority basis in the
kernel mode. After the execution of the system call, the control returns to the user mode and
execution of user processes can be resumed.
In general, system calls are required in the following situations −

• If a file system requires the creation or deletion of files. Reading and writing from files
also require a system call.
• Creation and management of new processes.
• Network connections also require system calls. This includes sending and receiving
packets.
• Access to a hardware devices such as a printer, scanner etc. requires a system call.

B.V.A.SWAMY 13 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.4

Types of System Calls

There are mainly five types of system calls. These are explained in detail as follows −
• Process Control These system calls deal with processes such as process creation,
process termination etc.
• File Management :These system calls are responsible for file manipulation such as
creating a file, reading a file, writing into a file etc.

• Device Management : These system calls are responsible for device manipulation
such as reading from device buffers, writing into device buffers etc.

• Information Maintenance : These system calls handle information and its transfer
between the operating system and the user program.

• Communication : These system calls are useful for interprocess communication.

They also deal with creating and deleting a communication connection.
Some of the examples of all the above types of system calls in Windows and Unix are
given as follows –
Types of System Calls Windows Linux

Process Control CreateProcess() fork()

ExitProcess() exit()
WaitForSingleObject() wait()

File Management CreateFile() open()

ReadFile() read()
WriteFile() write()
CloseHandle() close()

Device Management SetConsoleMode() ioctl()

ReadConsole() read()
WriteConsole() write()

Information GetCurrentProcessID() getpid()

Maintenance
SetTimer() alarm()
Sleep() sleep()

Communication CreatePipe() pipe()

CreateFileMapping() shmget()
MapViewOfFile() mmap()

B.V.A.SWAMY 14 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.4

There are many different system calls as shown above. Details of some of those system calls
are as follows −
• open() : The open() system call is used to provide access to a file in a file system. This system
call allocates resources to the file and provides a handle that the process uses to refer to the file.
A file can be opened by multiple processes at the same time or be restricted to one process. It all
depends on the file organisation and file system.

• read():The read() system call is used to access data from a file that is stored in the file system.
The file to read can be identified by its file descriptor and it should be opened using open() before
it can be read. In general, the read() system calls takes three arguments i.e. the file descriptor,
buffer which stores read data and number of bytes to be read from the file.

• write() : The write() system calls writes the data from a user buffer into a device such as a file.
This system call is one of the ways to output data from a program. In general, the write system
calls takes three arguments i.e. file descriptor, pointer to the buffer where data is stored and
number of bytes to write from the buffer.

• close() : The close() system call is used to terminate access to a file system. Using this system
call means that the file is no longer required by the program and so the buffers are flushed, the file
metadata is updated and the file resources are de-allocated.

• wait() : In some systems, a process may wait for another process to complete its execution. This
happens when a parent process creates a child process and the execution of the parent process
is suspended until the child process executes. The suspending of the parent process occurs with
a wait() system call. When the child process completes execution, the control is returned back to
the parent process.This system call runs an executable file in the context of an already running
process. It replaces the previous executable file. This is known as an overlay. The original process
identifier remains since a new process is not created but data, heap, stack etc. of the process are
replaced by the new process.

• fork() : Processes use the fork() system call to create processes that are a copy of themselves.
This is one of the major methods of process creation in operating systems. When a parent process
creates a child process and the execution of the parent process is suspended until the child
process executes. When the child process completes execution, the control is returned back to the
parent process.

• exit() : The exit() system call is used by a program to terminate its execution. In a multithreaded
environment, this means that the thread execution is complete. The operating system reclaims
resources that were used by the process after the exit() system call.

• kill() : The kill() system call is used by the operating system to send a termination signal to a
process that urges the process to exit. However, kill() system call does not necessarily mean killing
the process and can have various meanings.

B.V.A.SWAMY 15 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.5

Topic: 1.5 virtual machine

6) Explain about virtual machine and system generation?
Ans: 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.
• 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 machine operator’s console.

• System Models

Non-virtual Machine Virtual Machine

• Advantages/Disadvantages of Virtual Machines

• The virtual-machine concept provides complete protection of system resources since each
virtual.
• machine is isolated from all other virtual machines. This isolation, however, permits no direct
sharing of resources.
• A virtual-machine system is a perfect vehicle for operating-systems research and
development. System development is done on the virtual machine, instead of on a physical
machine and so does not disrupt normal system operation.
• The virtual machine concept is difficult to implement due to the effort required to provide an
exact duplicate to the underlying machine.

B.V.A.SWAMY 16 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.5

System Generation (SYSGEN)

Operating systems are designed to run on any of a class of machines at a variety of
sites with a variety of peripheral configurations. The system must then be configured or
generated for each specific computer site, a process sometimes known as system generation
(SYSGEN).

SYSGEN program obtains information concerning the specific configuration of the hardware
system.
To generate a system, we use a special program. The SYSGEN program reads from
a given file, or asks the operator of the system for information concerning the specific
configuration of the hardware system, or probes the hardware directly to determine what
components are there.

The following kinds of information must be determined.

What CPU will be used? What options (extended instruction sets, floating point arithmetic, and
so on) are installed? For multiple-CPU systems, each CPU must be described.

How much memory is available? Some systems will determine this value themselves by
referencing memory location after memory location until an "illegal address" fault is generated.
This procedure defines the final legal address and hence the amount of available memory.

What devices are available? The system will need to know how to address each device (the
device number), the device interrupt number, the device's type and model, and any special
device characteristics.

What operating-system options are desired, or what parameter values are to be used? These
options or values might include how many buffers of which sizes should be used, what type of
CPU scheduling algorithm is desired, what the maximum number of processes to be supported
is.

Booting –The procedure of starting a computer by loading the kernel is known as booting the
system. Most
computer systems have a small piece of code, stored in ROM, known as the bootstrap
program or bootstrap
loader. This code is able to locate the kernel, load it into main memory, and start its execution.
Some computer systems, such as PCs, use a two-step process in which a simple bootstrap
loader fetches a more complex boot program from disk, which in turn loads the kernel.

B.V.A.SWAMY 17 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.6

Topic: 1.6 Operating System Design and Implementation

7) Explain about Operating System Design and Implementation
An operating system is a construct that allows the user application programs to
interact with the system hardware. Operating system by itself does not provide any
function but it provides an atmosphere in which different applications and programs
can do useful work.
There are many problems that can occur while designing and implementing an
operating system. These are covered in operating system design and implementation.

Operating System Design Goals

It is quite complicated to define all the goals and specifications of the operating
system while designing it.The design changes depending on the type of the operating
system i.e if it is batch system, time shared system, single user system, multi user
system, distributed system etc.
There are basically two types of goals while designing an operating system. These are
• User Goals :The operating system should be convenient, easy to use,
reliable, safe and fast according to the users. However, these specifications
are not very useful as there is no set method to achieve these goals.

• System Goals : The operating system should be easy to design, implement

and maintain. These are specifications required by those who create, maintain
and operate the operating system. But there is not specific method to achieve
these goals as well.

B.V.A.SWAMY 18 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.6

Operating System Mechanisms and Policies

There is no specific way to design an operating system as it is a highly
creative task. However, there are general software principles that are applicable
to all operating systems.
A subtle difference between mechanism and policy is that mechanism
shows how to do something and policy shows what to do. Policies may change
over time and this would lead to changes in mechanism. So, it is better to have
a general mechanism that would require few changes even when a policy
change occurs.
For example - If the mechanism and policy are independent, then few
changes are required in mechanism if policy changes. If a policy favours I/O
intensive processes over CPU intensive processes, then a policy change to
preference of CPU intensive processes will not change the mechanism.
Operating System Implementation
The operating system needs to be implemented after it is designed.
Earlier they were written in assembly language but now higher level languages
are used. The first system not written in assembly language was the Master
Control Program (MCP) for Burroughs Computers.
Advantages of Higher Level Language
There are multiple advantages to implementing an operating system
using a higher level language such as: the code is written more fast, it is
compact and also easier to debug and understand. Also, the operating system
can be easily moved from one hardware to another if it is written in a high level
language.
Disadvantages of Higher Level Language
Using high level language for implementing an operating system leads to
a loss in speed and increase in storage requirements. However in modern
systems only a small amount of code is needed for high performance, such as
the CPU scheduler and memory manager. Also, the bottleneck routines in the
system can be replaced by assembly language equivalents if required.

B.V.A.SWAMY 19 | P a g e
DEPT. OF COMPUTER SCIENCE

8) Explain about generations of operating systems?

Ans: There are four generations of operating systems. These can be described as follows −

a) The First Generation ( 1945 - 1955 ): Vacuum Tubes and Plugboards

Digital computers were not constructed until the second world war. Calculating engines
with mechanical relays were built at that time. However, the mechanical relays were very slow
and were later replaced with vacuum tubes. These machines were enormous but were still
very slow.
These early computers were designed, built and maintained by a single group of people.
Programming languages were unknown and there were no operating systems so all the
programming was done in machine language. All the problems were simple numerical
calculations.
By the 1950’s punch cards were introduced and this improved the computer system.
Instead of using plugboards, programs were written on cards and read into the system.
b) The Second Generation ( 1955 - 1965 ): Transistors and Batch Systems
Transistors led to the development of the computer systems that could be manufactured
and sold to paying customers. These machines were known as mainframes and were locked
in air-conditioned computer rooms with staff to operate them.
The Batch System was introduced to reduce the wasted time in the computer. A tray full
of jobs was collected in the input room and read into the magnetic tape. After that, the tape
was rewound and mounted on a tape drive. Then the batch operating system was loaded in
which read the first job from the tape and ran it. The output was written on the second tape.
After the whole batch was done, the input and output tapes were removed and the output tape
was printed.
B.V.A.SWAMY 20 | P a g e
DEPT. OF COMPUTER SCIENCE

c) The Third Generation ( 1965 - 1980 ): Integrated Circuits and Multiprogramming

Until the 1960’s, there were two types of computer systems i.e the scientific and the
commercial computers. These were combined by IBM in the System/360. This used integrated
circuits and provided a major price and performance advantage over the second generation
systems.
The third generation operating systems also introduced multiprogramming. This meant
that the processor was not idle while a job was completing its I/O operation. Another job was
scheduled on the processor so that its time would not be wasted.

d) The Fourth Generation ( 1980 - Present ): Personal Computers

Personal Computers were easy to create with the development of large-scale integrated
circuits. These were chips containing thousands of transistors on a square centimeter of
silicon. Because of these, microcomputers were much cheaper than minicomputers and that
made it possible for a single individual to own one of them.
The advent of personal computers also led to the growth of networks. This created network
operating systems and distributed operating systems. The users were aware of a network
while using a network operating system and could log in to remote machines and copy files
from one machine to another.

B.V.A.SWAMY 21 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.7

Process Management
Topic:1.7 Process Concepts
1). What is process concept?
Ans:
Process Concept
• Informally, a process is a program in execution. A process is more than the program
code, which is sometimes known as the text section. It also includes the current
activity, as represented by the value of the program counter and the contents of the
processor's registers. In addition, a process generally includes the process stack,
which contains temporary data (such as method parameters, return addresses, and
local variables), and a data section, which contains global variables.
• An operating system executes a variety of programs:
✦ Batch system – jobs
✦ Time-shared systems – user programs or tasks
• Process – a program in execution; process execution must progress in sequential
fashion.

When a program is loaded into the memory and it becomes a process, it can
be divided into four sections ─ stack, heap, text and data.

The following image shows a simplified layout of a process inside main memory

B.V.A.SWAMY 22 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.8

Topic: 1.8 Operations on Process

2) Explain about operations on process?

Process State As a process executes, it changes state

New State: The process is being created.
Running State: A process is said to be running if it has the CPU, that is, process
actually using the CPU at that particular instant.
Blocked (or waiting) State: A process is said to be blocked if it is waiting for some
event to happen such that as an I/O completion before it can proceed. Note that a
process is unable to run until some external event happens.
Ready State: A process is said to be ready if it needs a CPU to execute. A ready
state process is runnable but temporarily stopped running to let another process run.
Terminated state: The process has finished execution.

What is the difference between process and program?

1) Both are same beast with different name or when this beast is sleeping (not
executing) it is called program and when it is executing becomes process.
2) Program is a static object whereas a process is a dynamic object.
3) A program resides in secondary storage whereas a process resides in main
memory.
4) The span time of a program is unlimited but the span time of a process is limited.
5) A process is an 'active' entity whereas a program is a 'passive' entity.
6) A program is an algorithm expressed in programming language whereas a process
is expressed in assembly language or machine language.

B.V.A.SWAMY 23 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.9

Topic: 1.9 Cooperating processes

3). Explain about Cooperating processes?

Ans: Cooperating processes are those that can affect or are affected by other
processes running on the system. Cooperating processes may share data with each
other.

Reasons for needing cooperating processes

There may be many reasons for the requirement of cooperating processes. Some of
these are given as follows −

• Modularity
Modularity involves dividing complicated tasks into smaller subtasks. These
subtasks can completed by different cooperating processes. This leads to faster
and more efficient completion of the required tasks.

• Information Sharing
Sharing of information between multiple processes can be accomplished using
cooperating processes. This may include access to the same files. A
mechanism is required so that the processes can access the files in parallel to
each other.

• Convenience
There are many tasks that a user needs to do such as compiling, printing,
editing etc. It is convenient if these tasks can be managed by cooperating
processes.

• Computation Speedup
Subtasks of a single task can be performed parallely using cooperating
processes. This increases the computation speedup as the task can be
executed faster. However, this is only possible if the system has multiple
processing elements.

Methods of Cooperation
Cooperating processes can coordinate with each other using shared data or
messages. Details about these are given as follows −

• Cooperation by Sharing
The cooperating processes can cooperate with each other using shared data
such as memory, variables, files, databases etc. Critical section is used to
provide data integrity and writing is mutually exclusive to prevent inconsistent
data.

B.V.A.SWAMY 24 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.9

A diagram that demonstrates cooperation by sharing is given as follows −

In the above diagram, Process P1 and P2 can cooperate with each other using
shared data such as memory, variables, files, databases etc.

• Cooperation by Communication
The cooperating processes can cooperate with each other using messages.
This may lead to deadlock if each process is waiting for a message from the
other to perform a operation. Starvation is also possible if a process never
receives a message.
A diagram that demonstrates cooperation by communication is given as follows

In the above diagram, Process P1 and P2 can cooperate with each other using
messages to communicate.

B.V.A.SWAMY 25 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.10

Topic: 1.10 Thread

4).What is Thread?
Ans:
A thread is a flow of execution through the process code, with its own program
counter that keeps track of which instruction to execute next, system registers which
hold its current working variables, and a stack which contains the execution history.
A thread shares with its peer threads few information like code segment, data
segment and open files. When one thread alters a code segment memory item, all
other threads see that.
A thread is also called a lightweight process. Threads provide a way to
improve application performance through parallelism. Threads represent a software
approach to improving performance of operating system by reducing the overhead
thread is equivalent to a classical process.
Each thread belongs to exactly one process and no thread can exist outside a
process. Each thread represents a separate flow of control. Threads have been
successfully used in implementing network servers and web server. They also
provide a suitable foundation for parallel execution of applications on shared memory
multiprocessors. The following figure shows the working of a single-threaded and a
multithreaded process.

B.V.A.SWAMY 26 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.10

Difference between Process and Thread

S.N. Process Thread

1 Process is heavy weight or Thread is light weight, taking lesser

resource intensive. resources than a process.

2 Process switching needs Thread switching does not need to

interaction with operating system. interact with operating system.

3 In multiple processing All threads can share same set of open

environments, each process files, child processes.
executes the same code but has its
own memory and file resources.

4 If one process is blocked, then no While one thread is blocked and waiting,
other process can execute until the a second thread in the same task can
first process is unblocked. run.

5 Multiple processes without using Multiple threaded processes use fewer

threads use more resources. resources.

6 In multiple processes each process One thread can read, write or change
operates independently of the another thread's data.
others.

Advantages of Thread

• Threads minimize the context switching time.

• Use of threads provides concurrency within a process.
• Efficient communication.
• It is more economical to create and context switch threads.
• Threads allow utilization of multiprocessor architectures to a greater scale and
efficiency.
Types of Thread
Threads are implemented in following two ways −
• User Level Threads − User managed threads.
• Kernel Level Threads − Operating System managed threads acting on kernel,
an operating system core.

B.V.A.SWAMY 27 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.10

User Level Threads

In this case, the thread management kernel is not aware of the existence of threads.
The thread library contains code for creating and destroying threads, for passing
message and data between threads, for scheduling thread execution and for saving
and restoring thread contexts. The application starts with a single thread.

Advantages

• Thread switching does not require Kernel mode privileges.

• User level thread can run on any operating system.
• Scheduling can be application specific in the user level thread.
• User level threads are fast to create and manage.
Disadvantages

• In a typical operating system, most system calls are blocking.

• Multithreaded application cannot take advantage of multiprocessing.

Kernel Level Threads

In this case, thread management is done by the Kernel. There is no thread
management code in the application area. Kernel threads are supported directly by
the operating system. Any application can be programmed to be multithreaded. All of
the threads within an application are supported within a single process.
The Kernel maintains context information for the process as a whole and for
individuals threads within the process. Scheduling by the Kernel is done on a thread
basis. The Kernel performs thread creation, scheduling and management in Kernel
space. Kernel threads are generally slower to create and manage than the user
threads.

B.V.A.SWAMY 28 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.10

Advantages

• Kernel can simultaneously schedule multiple threads from the same process on
multiple processes.
• If one thread in a process is blocked, the Kernel can schedule another thread of the
same process.
• Kernel routines themselves can be multithreaded.
Disadvantages

• Kernel threads are generally slower to create and manage than the user threads.
• Transfer of control from one thread to another within the same process requires a
mode switch to the Kernel.

Multithreading Models
Some operating system provide a combined user level thread and Kernel level thread
facility. Solaris is a good example of this combined approach. In a combined system,
multiple threads within the same application can run in parallel on multiple processors
and a blocking system call need not block the entire process. Multithreading models
are three types

• Many to many relationship.

• Many to one relationship.
• One to one relationship.
Many to Many Model
The many-to-many model multiplexes any number of user threads onto an equal or
smaller number of kernel threads.
The following diagram shows the many-to-many threading model where 6 user level
threads are multiplexing with 6 kernel level threads. In this model, developers can
create as many user threads as necessary and the corresponding Kernel threads can
run in parallel on a multiprocessor machine. This model provides the best accuracy
on concurrency and when a thread performs a blocking system call, the kernel can
schedule another thread for execution.

B.V.A.SWAMY 29 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.10

Many to One Model

Many-to-one model maps many user level threads to one Kernel-level thread. Thread
management is done in user space by the thread library. When thread makes a
blocking system call, the entire process will be blocked. Only one thread can access
the Kernel at a time, so multiple threads are unable to run in parallel on
multiprocessors.
If the user-level thread libraries are implemented in the operating system in such a
way that the system does not support them, then the Kernel threads use the many-
to-one relationship modes.

One to One Model

There is one-to-one relationship of user-level thread to the kernel-level thread. This
model provides more concurrency than the many-to-one model. It also allows another
thread to run when a thread makes a blocking system call. It supports multiple threads
to execute in parallel on microprocessors.
Disadvantage of this model is that creating user thread requires the corresponding
Kernel thread. OS/2, windows NT and windows 2000 use one to one relationship
model.

B.V.A.SWAMY 30 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.10

Difference between User-Level & Kernel-Level Thread

S.N. User-Level Threads Kernel-Level Thread

1 User-level threads are faster to create and Kernel-level threads are slower to
manage. create and manage.

2 Implementation is by a thread library at the Operating system supports creation

user level. of Kernel threads.

3 User-level thread is generic and can run on Kernel-level thread is specific to the
any operating system. operating system.

4 Multi-threaded applications cannot take Kernel routines themselves can be

advantage of multiprocessing. multithreaded.

B.V.A.SWAMY 31 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.11

Topic: 1.11 Inter Process communication (IPC)

Explain about Inter Process Communication(IPC)?

A process can be of two types:
• Independent process.
• Co-operating process.
An independent process is not affected by the execution of other processes while a
co-operating process can be affected by other executing processes. Though one can think
that those processes, which are running independently, will execute very efficiently, in
reality, there are many situations when co-operative nature can be utilized for increasing
computational speed, convenience, and modularity. Inter-process communication (IPC) is
a mechanism that allows processes to communicate with each other and synchronize their
actions. The communication between these processes can be seen as a method of co-
operation between them.
Processes can communicate with each other through both:
1. Shared Memory
2. Message passing
Figure 1 below shows a basic structure of communication between processes via the
shared memory method and via the message passing method.
An operating system can implement both methods of communication. First, we will discuss
the shared memory methods of communication and then message passing.
Communication between processes using shared memory requires processes to share
some variable, and it completely depends on how the programmer will implement it. One
way of communication using shared memory can be imagined like this: Suppose process1
and process2 are executing simultaneously, and they share some resources or use some
information from another process. Process1 generates information about certain
computations or resources being used and keeps it as a record in shared memory. When
process2 needs to use the shared information, it will check in the record stored in shared
memory and take note of the information generated by process1 and act accordingly.
Processes can use shared memory for extracting information as a record from another
process as well as for delivering any specific information to other processes.
Let’s discuss an example of communication between processes using the shared memory
method

B.V.A.SWAMY 32 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.11

i) Shared Memory Method

Ex: Producer-Consumer problem
There are two processes: Producer and Consumer. The producer produces some items
and the Consumer consumes that item. The two processes share a common space or
memory location known as a buffer where the item produced by the Producer is stored and
from which the Consumer consumes the item if needed. There are two versions of this
problem: the first one is known as the unbounded buffer problem in which the Producer
can keep on producing items and there is no limit on the size of the buffer, the second one
is known as the bounded buffer problem in which the Producer can produce up to a certain
number of items before it starts waiting for Consumer to consume it. We will discuss the
bounded buffer problem. First, the Producer and the Consumer will share some common
memory, then the producer will start producing items. If the total produced item is equal to
the size of the buffer, the producer will wait to get it consumed by the Consumer. Similarly,
the consumer will first check for the availability of the item. If no item is available, the
Consumer will wait for the Producer to produce it

i) Messaging Passing Method

In this method, processes communicate with each other without using any kind of shared
memory. If two processes p1 and p2 want to communicate with each other, they proceed
as follows:
• Establish a communication link (if a link already exists, no need to establish it
again.)
• Start exchanging messages using basic primitives.
We need at least two primitives:
– send(message, destination) or send(message)
– receive(message, host) or receive(message)

The message size can be of fixed size or of variable size. If it is of fixed size, it is easy for
an OS designer but complicated for a programmer and if it is of variable size then it is easy
for a programmer but complicated for the OS designer. A standard message can have two
parts: header and body.
The header part is used for storing message type, destination id, source id, message
length, and control information. The control information contains information like what to do
if runs out of buffer space, sequence number, priority. Generally, message is sent using
FIFO style.
Message Passing through Communication Link.
Direct and Indirect Communication link
Now, We will start our discussion about the methods of implementing communication links.
While implementing the link, there are some questions that need to be kept in mind like :

1. How are links established?

2. Can a link be associated with more than two processes?
3. How many links can there be between every pair of communicating processes?
B.V.A.SWAMY 33 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.11

4. What is the capacity of a link? Is the size of a message that the link can
accommodate fixed or variable?
5. Is a link unidirectional or bi-directional?
A link has some capacity that determines the number of messages that can reside in it
temporarily for which every link has a queue associated with it which can be of zero
capacity, bounded capacity, or unbounded capacity. In zero capacity, the sender waits
until the receiver informs the sender that it has received the message. In non-zero capacity
cases, a process does not know whether a message has been received or not after the
send operation. For this, the sender must communicate with the receiver explicitly.
Implementation of the link depends on the situation, it can be either a direct
communication link or an in-directed communication link.
Direct Communication links are implemented when the processes use a specific process
identifier for the communication, but it is hard to identify the sender ahead of time.
For example the print server.
In-direct Communication is done via a shared mailbox (port), which consists of a queue
of messages. The sender keeps the message in mailbox and the receiver picks them up.

Message Passing through Exchanging the Messages.

Synchronous and Asynchronous Message Passing:
A process that is blocked is one that is waiting for some event, such as a resource
becoming available or the completion of an I/O operation. IPC is possible between the
processes on same computer as well as on the processes running on different computer
i.e. in networked/distributed system. In both cases, the process may or may not be blocked
while sending a message or attempting to receive a message so message passing may be
blocking or non-blocking. Blocking is considered synchronous and blocking send means
the sender will be blocked until the message is received by receiver. Similarly, blocking
receive has the receiver block until a message is available. Non-blocking is
considered asynchronous and Non-blocking send has the sender sends the message
and continue. Similarly, Non-blocking receive has the receiver receive a valid message or
null. After a careful analysis, we can come to a conclusion that for a sender it is more
natural to be non-blocking after message passing as there may be a need to send the
message to different processes. However, the sender expects acknowledgment from the
receiver in case the send fails. Similarly, it is more natural for a receiver to be blocking
after issuing the receive as the information from the received message may be used for
further execution. At the same time, if the message send keep on failing, the receiver will
have to wait indefinitely. That is why we also consider the other possibility of message
passing. There are basically three preferred combinations:

• Blocking send and blocking receive

• Non-blocking send and Non-blocking receive
• Non-blocking send and Blocking receive (Mostly used)
In Direct message passing, The process which wants to communicate must explicitly
name the recipient or sender of the communication.
e.g. send(p1, message) means send the message to p1.
Similarly, receive(p2, message) means to receive the message from p2.
In this method of communication, the communication link gets established automatically,
which can be either unidirectional or bidirectional, but one link can be used between one
pair of the sender and receiver and one pair of sender and receiver should not possess
more than one pair of links. Symmetry and asymmetry between sending and receiving can
also be implemented i.e. either both processes will name each other for sending and
receiving the messages or only the sender will name the receiver for sending the message
and there is no need for the receiver for naming the sender for receiving the message. The
problem with this method of communication is that if the name of one process changes,
this method will not work.
In Indirect message passing, processes use mailboxes (also referred to as ports) for
sending and receiving messages. Each mailbox has a unique id and processes can
B.V.A.SWAMY 34 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.11

communicate only if they share a mailbox. Link established only if processes share a
common mailbox and a single link can be associated with many processes. Each pair of
processes can share several communication links and these links may be unidirectional or
bi-directional. Suppose two processes want to communicate through Indirect message
passing, the required operations are: create a mailbox, use this mailbox for sending and
receiving messages, then destroy the mailbox. The standard primitives used are: send(A,
message) which means send the message to mailbox A. The primitive for the receiving
the message also works in the same way e.g. received (A, message). There is a problem
with this mailbox implementation. Suppose there are more than two processes sharing the
same mailbox and suppose the process p1 sends a message to the mailbox, which
process will be the receiver? This can be solved by either enforcing that only two
processes can share a single mailbox or enforcing that only one process is allowed to
execute the receive at a given time or select any process randomly and notify the sender
about the receiver. A mailbox can be made private to a single sender/receiver pair and can
also be shared between multiple sender/receiver pairs. Port is an implementation of such
mailbox that can have multiple senders and a single receiver. It is used in client/server
applications (in this case the server is the receiver). The port is owned by the receiving
process and created by OS on the request of the receiver process and can be destroyed
either on request of the same receiver processor when the receiver terminates itself.
Enforcing that only one process is allowed to execute the receive can be done using the
concept of mutual exclusion. Mutex mailbox is created which is shared by n process. The
sender is non-blocking and sends the message. The first process which executes the
receive will enter in the critical section and all other processes will be blocking and will
wait.
Now, let’s discuss the Producer-Consumer problem using the message passing concept.
The producer places items (inside messages) in the mailbox and the consumer can
consume an item when at least one message present in the mailbox

Topic: 1.12 Process Scheduling

5). Explain about Process Scheduling?

Ans:
Definition
The process scheduling is the activity of the process manager that handles the
removal of the running process from the CPU and the selection of another process
on the basis of a particular strategy.
Process scheduling is an essential part of a Multiprogramming operating systems.
Such operating systems allow more than one process to be loaded into the
executable memory at a time and the loaded process shares the CPU using time
multiplexing.
Process Scheduling Queues
The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a
separate queue for each of the process states and PCBs of all processes in the same
execution state are placed in the same queue. When the state of a process is
changed, its PCB is unlinked from its current queue and moved to its new state queue.
The Operating System maintains the following important process scheduling queues
B.V.A.SWAMY 35 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.12

• Job queue − This queue keeps all the processes in the system.
• Ready queue − This queue keeps a set of all processes residing in main
memory, ready and waiting to execute. A new process is always put in this
queue.
• Device queues − The processes which are blocked due to unavailability of an
I/O device constitute this queue.

The OS can use different policies to manage each queue (FIFO, Round Robin,
Priority, etc.). The OS scheduler determines how to move processes between the
ready and run queues which can only have one entry per processor core on the
system; in the above diagram, it has been merged with the CPU.
Two-State Process Model
Two-state process model refers to running and non-running states which are
described below −

S.N. State & Description

1
Running
When a new process is created, it enters into the system as in the running
state.

2
Not Running
Processes that are not running are kept in queue, waiting for their turn to
execute. Each entry in the queue is a pointer to a particular process. Queue
is implemented by using linked list. Use of dispatcher is as follows. When a
process is interrupted, that process is transferred in the waiting queue. If the
process has completed or aborted, the process is discarded. In either case,
the dispatcher then selects a process from the queue to execute.

B.V.A.SWAMY 36 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.12

Schedulers
Schedulers are special system software which handle process scheduling in various
ways. Their main task is to select the jobs to be submitted into the system and to
decide which process to run. Schedulers are of three types −

• Long-Term Scheduler
• Short-Term Scheduler
• Medium-Term Scheduler
Long Term Scheduler
It is also called a job scheduler. A long-term scheduler determines which programs
are admitted to the system for processing. It selects processes from the queue and
loads them into memory for execution. Process loads into the memory for CPU
scheduling.
The primary objective of the job scheduler is to provide a balanced mix of jobs, such
as I/O bound and processor bound. It also controls the degree of multiprogramming.
If the degree of multiprogramming is stable, then the average rate of process creation
must be equal to the average departure rate of processes leaving the system.
On some systems, the long-term scheduler may not be available or minimal. Time-
sharing operating systems have no long term scheduler. When a process changes
the state from new to ready, then there is use of long-term scheduler.
Short Term Scheduler
It is also called as CPU scheduler. Its main objective is to increase system
performance in accordance with the chosen set of criteria. It is the change of ready
state to running state of the process. CPU scheduler selects a process among the
processes that are ready to execute and allocates CPU to one of them.
Short-term schedulers, also known as dispatchers, make the decision of which
process to execute next. Short-term schedulers are faster than long-term schedulers.
Medium Term Scheduler
Medium-term scheduling is a part of swapping. It removes the processes from the
memory. It reduces the degree of multiprogramming. The medium-term scheduler is
in-charge of handling the swapped out-processes.
A running process may become suspended if it makes an I/O request. A suspended
processes cannot make any progress towards completion. In this condition, to
remove the process from memory and make space for other processes, the
suspended process is moved to the secondary storage. This process is
called swapping, and the process is said to be swapped out or rolled out. Swapping
may be necessary to improve the process mix.

B.V.A.SWAMY 37 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.12

Comparison among Scheduler

S.N. Long-Term Scheduler Short-Term Medium-Term Scheduler
Scheduler

1 It is a job scheduler It is a CPU scheduler It is a process swapping

scheduler.

2 Speed is lesser than Speed is fastest among Speed is in between both

short term scheduler other two short and long term
scheduler.

3 It controls the degree of It provides lesser It reduces the degree of

multiprogramming control over degree of multiprogramming.
multiprogramming

4 It is almost absent or It is also minimal in It is a part of Time sharing

minimal in time sharing time sharing system systems.
system

5 It selects processes from It selects those It can re-introduce the

pool and loads them into processes which are process into memory and
memory for execution ready to execute execution can be
continued.

Context Switch
A context switch is the mechanism to store and restore the state or context of
a CPU in Process Control block so that a process execution can be resumed from
the same point at a later time. Using this technique, a context switcher enables
multiple processes to share a single CPU. Context switching is an essential part of a
multitasking operating system features.
When the scheduler switches the CPU from executing one process to execute
another, the state from the current running process is stored into the process control
block. After this, the state for the process to run next is loaded from its own PCB and
used to set the PC, registers, etc. At that point, the second process can start
executing.

B.V.A.SWAMY 38 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.12

Context switches are computationally intensive since register and memory state must
be saved and restored. To avoid the amount of context switching time, some
hardware systems employ two or more sets of processor registers. When the process
is switched, the following information is stored for later use.

• Program Counter
• Scheduling information
• Base and limit register value
• Currently used register
• Changed State
• I/O State information
• Accounting information

B.V.A.SWAMY 39 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.12

6).Explain about Preemptive and Non-Preemptive Scheduling?

Ans:
1. Preemptive Scheduling:
Preemptive scheduling is used when a process switches from running state
to ready state or from waiting state to ready state. The resources (mainly CPU
cycles) are allocated to the process for the limited amount of time and then is taken
away, and the process is again placed back in the ready queue if that process still
has CPU burst time remaining. That process stays in ready queue till it gets next
chance to execute.

Algorithms based on preemptive scheduling are: Round Robin (RR),Shortest

Remaining Time First (SRTF), Priority (preemptive version), etc.

2. Non-Preemptive Scheduling:
Non-preemptive Scheduling is used when a process terminates, or a
process switches from running to waiting state. In this scheduling, once the
resources (CPU cycles) is allocated to a process, the process holds the CPU till it
gets terminated or it reaches a waiting state. In case of non-preemptive scheduling
does not interrupt a process running CPU in middle of the execution. Instead, it
waits till the process complete its CPU burst time and then it can allocate the CPU
to another process.
Algorithms based on non-preemptive scheduling are: Shortest Job First (SJF
basically non preemptive) and Priority (non preemptive version), etc.

B.V.A.SWAMY 40 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.12

7). Differences Between Preemptive and Non-Preemptive Scheduling ?

1. In preemptive scheduling the CPU is allocated to the processes for the

limited time whereas in Non-preemptive scheduling, the CPU is allocated
to the process till it terminates or switches to waiting state.

2. The executing process in preemptive scheduling is interrupted in the

middle of execution when higher priority one comes whereas, the
executing process in non-preemptive scheduling is not interrupted in the
middle of execution and wait till its execution.

3. In Preemptive Scheduling, there is the overhead of switching the process

from ready state to running state, vise-verse, and maintaining the ready
queue. Whereas in case of non-preemptive scheduling has no overhead
of switching the process from running state to ready state.

4. In preemptive scheduling, if a high priority process frequently arrives in

the ready queue then the process with low priority has to wait for a long,
and it may have to starve. On the other hands, in the non-preemptive
scheduling, if CPU is allocated to the process having larger burst time
then the processes with small burst time may have to starve.

5. Preemptive scheduling attain flexible by allowing the critical processes to

access CPU as they arrive into the ready queue, no matter what process
is executing currently. Non-preemptive scheduling is called rigid as even
if a critical process enters the ready queue the process running CPU is
not disturbed.

6. The Preemptive Scheduling has to maintain the integrity of shared data

that’s why it is cost associative as it which is not the case with Non-
preemptive Scheduling.

B.V.A.SWAMY 41 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.13

Topic: 1.13 Scheduling algorithms

8).Explain about Scheduling algorithms?
Ans:
A Process Scheduler schedules different processes to be assigned to the CPU
based on particular scheduling algorithms. There are six popular process scheduling
algorithms

• First-Come, First-Served (FCFS) Scheduling

• Shortest-Job-Next (SJN) Scheduling
• Priority Scheduling
• Shortest Remaining Time
• Round Robin(RR) Scheduling
• Multiple-Level Queues Scheduling
These algorithms are either non-preemptive or preemptive. Non-preemptive
algorithms are designed so that once a process enters the running state, it cannot be
preempted until it completes its allotted time, whereas the preemptive scheduling is
based on priority where a scheduler may preempt a low priority running process
anytime when a high priority process enters into a ready state.
First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis.

• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
• Poor in performance as average wait time is high.

B.V.A.SWAMY 42 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.13

Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time

P0 0-0=0

P1 5-1=4

P2 8-2=6

P3 16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

• This is also known as shortest job first, or SJF
• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in
advance.
• Impossible to implement in interactive systems where required CPU time is not
known.
• The processer should know in advance how much time process will take.
Given: Table of processes, and their Arrival time, Execution time

Process Arrival Execution Service

Time Time Time

P0 0 5 0

P1 1 3 5

P2 2 8 14

P3 3 6 8

B.V.A.SWAMY 43 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic:
Topic: 1.13
1.13

Waiting time of each process is as follows −

Process Waiting Time

P0 0-0=0

P1 5-1=4

P2 14 - 2 = 12

P3 8-3=5

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

• Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
• Processes with same priority are executed on first come first served basis.
• Priority can be decided based on memory requirements, time requirements or
any other resource requirement.
Given: Table of processes, and their Arrival time, Execution time, and priority. Here
we are considering 1 is the lowest priority.

Process Arrival Execution Priority Service

Time Time Time

P0 0 5 1 0

P1 1 3 2 11

P2 2 8 1 14

P3 3 6 3 5

B.V.A.SWAMY 44 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.13

Waiting time of each process is as follows −

Process Waiting Time

P0 0-0=0

P1 11 - 1 = 10

P2 14 - 2 = 12

P3 5-3=2

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

• Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
• The processor is allocated to the job closest to completion but it can be
preempted by a newer ready job with shorter time to completion.
• Impossible to implement in interactive systems where required CPU time is not
known.
• It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

• Round Robin is the preemptive process scheduling algorithm.
• Each process is provided a fix time to execute, it is called a quantum.
• Once a process is executed for a given time period, it is preempted and other
process executes for a given time period.
• Context switching is used to save states of preempted processes.

B.V.A.SWAMY 45 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.13

Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time

P0 (0 - 0) + (12 - 3) = 9

P1 (3 - 1) = 2

P2 (6 - 2) + (14 - 9) + (20 - 17) = 12

P3 (9 - 3) + (17 - 12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

Multiple-level queues are not an independent scheduling algorithm. They make use
of other existing algorithms to group and schedule jobs with common characteristics.

• Multiple queues are maintained for processes with common characteristics.

• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs
in another queue. The Process Scheduler then alternately selects jobs from each
queue and assigns them to the CPU based on the algorithm assigned to the queue.

B.V.A.SWAMY 46 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 1.14

Topic:1.14 & 1.15 thread scheduling and multiple process scheduling

9). Explain about thread scheduling and multiple process scheduling?
Ans:
Thread scheduling
Distinction between user-level and kernel-level threads
Many-to-one and many-to-many models, thread library schedules user-level threads to run on
LWP
Known as process-contention scope (PCS) since scheduling competition is within the
process
Kernel thread scheduled onto available CPU is system-contention scope (SCS) –
competition among all threads in system
Pthread Scheduling
API allows specifying either PCS or SCS during thread creation
PTHREAD SCOPE PROCESS schedules threads using PCS scheduling
PTHREAD SCOPE SYSTEM schedules threads using SCS scheduling.

Pthread Scheduling API

#include <pthread.h>
#include <stdio.h>
#define NUM THREADS 5
int main(int argc, char *argv[])
{
int i; pthread t tid[NUM THREADS];
pthread attr t attr;
/* get the default attributes */
pthread attr init(&attr);
/* set the scheduling algorithm to PROCESS or SYSTEM */
pthread attr setscope(&attr, PTHREAD SCOPE SYSTEM);
/* set the scheduling policy - FIFO, RT, or OTHER */
pthread attr setschedpolicy(&attr, SCHED OTHER);
/* create the threads */
for (i = 0; i < NUM THREADS; i++)
pthread create(&tid[i],&attr,runner,NULL);
/* now join on each thread */
for (i = 0; i < NUM THREADS; i++)
pthread join(tid[i], NULL);
}
/* Each thread will begin control in this function */
void *runner(void *param)
{
printf("I am a thread\n");
pthread exit(0);
}

B.V.A.SWAMY 47 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 1.15

Multiple process scheduling

Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are available
Homogeneous processors within a multiprocessor
Asymmetric multiprocessing – only one processor accesses the system data structures,
alleviating the need for data sharing
Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in
common ready queue, or each has its own private queue of ready processes
Processor affinity – process has affinity for processor on which it is currently running
soft affinity
hard affinity

NUMA and CPU Scheduling

Multicore Processors
Recent trend to place multiple processor cores on same physical chip
Faster and consume less power
Multiple threads per core also growing
Takes advantage of memory stall to make progress on another thread while memory retrieve
happens

Multithreaded Multicore System

B.V.A.SWAMY 48 | P a g e
DEPT. OF COMPUTER SCIENCE

ADIKAVI NANNAYA UNIVERSITY

MSN CAMPUS – KAKINADA
DEPARTMENT OF COMPUTER SCIENCE
MASTER OF COMPUTER APPLICATIONS
SUBJECT- (19105) OPERATING SYSTEMS MATERIAL

UNIT -2
TOPICS
Process Synchronization: Page No: 51

2.1 The Critical Section Problem, 56

2.2 Semaphores, And 59

2.2.1 Classical Problems of 64

Synchronization,
2.3 Critical Regions, 73

2.4 Monitors, Synchronization 75

examples
.

Deadlocks: Page No

2.5 Principles of Deadlocks, 76

2.6 System Model, 78

2.7 Deadlocks Characterization, 78

2.8 Methods for Handling 80

Deadlocks
2.8.1 Deadlock Prevention, 80
2.8.2Avoidance, 81
2.8.3 Detection 85
2.8.4Recovery from Deadlocks 86
.

B.V.A.SWAMY 49 | P a g e
DEPT. OF COMPUTER SCIENCE

UNIT-2
Process Synchronization

Process Synchronization is a technique which is used to coordinate the process that

use shared Data.
There are two types of Processes in an Operating Systems:-
1. Independent Process –
The process that does not affect or is affected by the other process while its
execution then the process is called Independent Process. Example The process that
does not share any shared variable, database, files, etc.
2. Cooperating Process –
The process that affect or is affected by the other process while execution, is called a
Cooperating Process. Example The process that share file, variable, database, etc are
the Cooperating Process.

Process Synchronization is mainly used for Cooperating Process that shares the
resources.Let us consider an example of
//racing condition image

B.V.A.SWAMY 50 | P a g e
DEPT. OF COMPUTER SCIENCE

It is the condition where several processes tries to access the resources and
modify the shared data concurrently and outcome of the process depends on the
particular order of execution that leads to data inconsistency, this condition is
called Race Condition. This condition can be avoided using the technique called
Synchronization or Process Synchronization, in which we allow only one process to
enter and manipulates the shared data in Critical Section.
//diagram of the view of CS

This setup can be defined in various regions like:

• Entry Section –
It is part of the process which decide the entry of a particular process in the Critical
Section, out of many other processes.
• Critical Section –
It is the part in which only one process is allowed to enter and modify the shared
variable.This part of the process ensures that only no other process can access the
resource of shared data.
• Exit Section –
This process allows the other process that are waiting in the Entry Section, to enter
into the Critical Sections. It checks that a process that after a process has finished
execution in Critical Section can be removed through this Exit Section.
• Remainder Section –
The other parts of the Code other than Entry Section, Critical Section and Exit Section
are known as Remainder Section.

B.V.A.SWAMY 51 | P a g e
DEPT. OF COMPUTER SCIENCE

Critical Section problems must satisfy these three requirements:

1. Mutual Exclusion –
It states that no other process is allowed to execute in the critical section if a process
is executing in critical section.
2. Progress –
When no process is in the critical section, then any process from outside that request
for execution can enter in the critical section without any delay. Only those process
can enter that have requested and have finite time to enter the process.
3. Bounded Waiting –
An upper bound must exist on the number of times a process enters so that other
processes are allowed to enter their critical sections after a process has made a
request to enter its critical section and before that request is granted.

Process Synchronization are handled by two approaches:

1. Software Approach –
In Software Approach, Some specific Algorithm approach is used to maintain
synchronization of the data. Like in Approach One or Approach Two, for a number of
two process, a temporary variable like (turn) or boolean variable (flag) value is used
to store the data. When the condition is True then the process in waiting State,
known as Busy Waiting State. This does not satisfy all the Critical Section
requirements.
Another Software approach known as Peterson’s Solution is best for
Synchronization. It uses two variables in the Entry Section so as to maintain
consistency, like Flag (boolean variable) and Turn variable(storing the process
states). It satisfy all the three Critical Section requirements.
//Image of Peterson’s Algorithm

B.V.A.SWAMY 52 | P a g e
DEPT. OF COMPUTER SCIENCE

2. Hardware Approach –
The Hardware Approach of synchronization can be done through Lock & Unlock
technique. Locking part is done in the Entry Section, so that only one process is
allowed to enter into the Critical Section, after it complete its execution, the process
is moved to the Exit Section, where Unlock Operation is done so that another process
in the Lock Section can repeat this process of Execution. This process is designed in
such a way that all the three conditions of the Critical Sections are satisfied.
//Image of Lock

Using Interrupts –
These are easy to implement.When Interrupt are disabled then no other process is
allowed to perform Context Switch operation that would allow only one process to
enter into the Critical State.
//Image of Interrupts

B.V.A.SWAMY 53 | P a g e
DEPT. OF COMPUTER SCIENCE

Test_and_Set Operation –
This allows boolean value (True/False) as a hardware Synchronization, which is atomic
in nature i.e no other interrupt is allowed to access. This is mainly used in Mutual
Exclusion Application. Similar type operation can be achieved through Compare and
Swap function. In this process, a variable is allowed to accessed in Critical Section
while its lock operation is ON. Till then, the other process is in Busy Waiting State.
Hence Critical Section Requirements are achieved.

Critical Section:
In simple terms a critical section is group of instructions/statements or region
of code that need to be executed atomically (read this post for atomicity), such as
accessing a resource (file, input or output port, global data, etc.).
In concurrent programming, if one thread tries to change the value of shared
data at the same time as another thread tries to read the value (i.e. data race across
threads), the result is unpredictable.
The access to such shared variable (shared memory, shared files, shared port,
etc…) to be synchronized. Few programming languages have built-in support for
synchronization.
It is critical to understand the importance of race condition while writing kernel
mode programming (a device driver, kernel thread, etc.). since the programmer can
directly access and modifying kernel data structures.

A simple solution to the critical section can be thought as shown below,

acquireLock();
Process Critical Section
releaseLock();

A thread must acquire a lock prior to executing a critical section. The lock can be
acquired by only one thread. There are various ways to implement locks in the
above pseudo code. Let us discuss them in future articles.

B.V.A.SWAMY 54 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.1

Topic: 2.1 Critical Section Problem

Critical Section Problem

A Critical Section is a code segment that accesses shared variables and has
to be executed as an atomic action. It means that in a group of cooperating
processes, at a given point of time, only one process must be executing its critical
section. If any other process also wants to execute its critical section, it must wait
until the first one finishes. The entry to the critical section is mainly handled
by wait() function while the exit from the critical section is controlled by
the signal() function.

Entry Section
In this section mainly the process requests for its entry in the critical section.

Exit Section
This section is followed by the critical section.

The solution to the Critical Section Problem

A solution to the critical section problem must satisfy the following three conditions:

1. Mutual Exclusion
Out of a group of cooperating processes, only one process can be in its critical
section at a given point of time.

2. Progress
If no process is in its critical section, and if one or more threads want to execute their
critical section then any one of these threads must be allowed to get into its critical
section.
B.V.A.SWAMY 55 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.1

3. Bounded Waiting
After a process makes a request for getting into its critical section, there is a limit for
how many other processes can get into their critical section, before this process's
request is granted. So after the limit is reached, the system must grant the process
permission to get into its critical section.

Solutions for the Critical Section

The critical section plays an important role in Process Synchronization so that the
problem must be solved.
Some widely used method to solve the critical section problem are as follows:

1.Peterson's Solution
This is widely used and software-based solution to critical section problems.
Peterson's solution was developed by a computer scientist Peterson that's why it is
named so.
With the help of this solution whenever a process is executing in any critical
state, then the other process only executes the rest of the code, and vice-versa can
happen. This method also helps to make sure of the thing that only a single process
can run in the critical section at a specific time.
This solution preserves all three conditions:
• Mutual Exclusion is comforted as at any time only one process can access the
critical section.
• Progress is also comforted, as a process that is outside the critical section is
unable to block other processes from entering into the critical section.
• Bounded Waiting is assured as every process gets a fair chance to enter the
Critical section.

The above shows the structure of process Pi in Peterson's solution.

• Suppose there are N processes (P1, P2, ... PN) and as at some point of time
every process requires to enter in the Critical Section

B.V.A.SWAMY 56 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.1

• A FLAG[] array of size N is maintained here which is by default false.

Whenever a process requires to enter in the critical section, it has to set its
flag as true. Example: If Pi wants to enter it will set FLAG[i]=TRUE.
• Another variable is called TURN and is used to indicate the process number
that is currently waiting to enter into the critical section.
• The process that enters into the critical section while exiting would change
the TURN to another number from the list of processes that are ready.
• Example: If the turn is 3 then P3 enters the Critical section and while exiting
turn=4 and therefore P4 breaks out of the wait loop.

Synchronization Hardware
Many systems provide hardware support for critical section code. The critical
section problem could be solved easily in a single-processor environment if we could
disallow interrupts to occur while a shared variable or resource is being modified.
In this manner, we could be sure that the current sequence of instructions
would be allowed to execute in order without pre-emption. Unfortunately, this
solution is not feasible in a multiprocessor environment.
Disabling interrupt on a multiprocessor environment can be time-consuming
as the message is passed to all the processors.
This message transmission lag delays the entry of threads into the critical
section, and the system efficiency decreases.

Mutex Locks
As the synchronization hardware solution is not easy to implement for everyone, a
strict software approach called Mutex Locks was introduced. In this approach, in the
entry section of code, a LOCK is acquired over the critical resources modified and
used inside the critical section, and in the exit section that LOCK is released.
As the resource is locked while a process executes its critical section hence no other
process can access it.

B.V.A.SWAMY 57 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2

Topic: 2.2 Semaphores in operating system

Prerequisite: process-synchronization, Mutex vs Semaphore

Introduction to Semaphores
In 1965, Dijkstra proposed a new and very significant technique for managing
concurrent processes by using the value of a simple integer variable to synchronize
the progress of interacting processes. This integer variable is called semaphore. So
it is basically a synchronizing tool and is accessed only through two low standard
atomic operations, wait and signal designated by P(S) and V(S) respectively.
In very simple words, semaphore is a variable which can hold only a non-
negative Integer value, shared between all the threads, with
operations wait and signal, which work as follow:
P(S): if S ≥ 1 then S := S - 1

else <block and enqueue the process>;

V(S): if <some process is blocked on the queue>

then <unblock a process>

else S := S + 1;

The classical definitions of wait and signal are:

• Wait: Decrements the value of its argument S, as soon as it would become non-

negative(greater than or equal to 1).

• Signal: Increments the value of its argument S, as there is no more process blocked

on the queue.

Properties of Semaphores

1. It's simple and always have a non-negative Integer value.

2. Works with many processes.

3. Can have many different critical sections with different semaphores.

4. Each critical section has unique access semaphores.

5. Can permit multiple processes into the critical section at once, if desirable.

Types of Semaphores
Semaphores are mainly of two types:
B.V.A.SWAMY 58 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2

1. Binary Semaphore:

It is a special form of semaphore used for implementing mutual exclusion,

hence it is often called a Mutex. A binary semaphore is initialized to 1 and
only takes the values 0 and 1 during execution of a program.

2. Counting Semaphores:

These are used to implement bounded concurrency.

Example of Use
Here is a simple step wise implementation involving declaration and usage of
semaphore.
Shared var mutex: semaphore = 1;

Process i

begin

P(mutex);

execute CS;

V(mutex);

End;

B.V.A.SWAMY 59 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2

Limitations of Semaphores

1. Priority Inversion is a big limitation of semaphores.

2. Their use is not enforced, but is by convention only.

3. With improper use, a process may block indefinitely. Such a situation is

called Deadlock. We will be studying deadlocks in details in coming lessons.

Semaphore is simply a variable. This variable is used to solve the critical section
problem and to achieve process synchronization in the multiprocessing environment.
The two most common kinds of semaphores are counting semaphores and binary
semaphores. Counting semaphore can take non-negative integer values and Binary
semaphore can take the value 0 & 1. only.
Now let us see how it do so.
First, look at two operations which can be used to access and change the value of the
semaphore variable.

Some point regarding P and V operation

1. P operation is also called wait, sleep or down operation and V operation is also called
signal, wake-up or up operation.
2. Both operations are atomic and semaphore(s) is always initialized to one.
3. A critical section is surrounded by both operations to implement process
synchronization.See below image.critical section of Process P is in between P and V
operation.

B.V.A.SWAMY 60 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.2

Now, let us see how it implements mutual exclusion. Let there be two processes P1
and P2 and a semaphore s is initialized as 1. Now if suppose P1 enters in its critical
section then the value of semaphore s becomes 0. Now if P2 wants to enter its critical
section then it will wait until s > 0, this can only happen when P1 finishes its critical
section and calls V operation on semaphore s. This way mutual exclusion is achieved.
Look at the below image for details.

The description above is for binary semaphore which can take only two values 0 and
1. There is one other type of semaphore called counting semaphore which can take
values greater than one.
Now suppose there is a resource whose number of instance is 4.
Now we initialize S = 4 and rest is same as for binary semaphore.
Whenever process wants that resource it calls P or wait function and when it is done it
calls V or signal function.
If the value of S becomes zero then a process has to wait until S becomes positive.
B.V.A.SWAMY 61 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2

For example, Suppose there are 4 process P1, P2, P3, P4 and they all call wait operation
on S(initialized with 4). If another process P5 wants the resource then it should wait
until one of the four processes calls signal function and value of semaphore becomes
positive.
Problem in this implementation of semaphore
Whenever any process waits then it continuously checks for semaphore value (look at
this line while (s==0); in P operation) and waste CPU cycle.
To avoid this another implementation is provided below.
P(Semaphore s)
{
s = s - 1;
if (s <= 0) {
// add process to queue
block();
}
}

V(Semaphore s)
{
s = s + 1;
if (s <= 0) {
// remove process p from queue
wakeup(p);
}
}

In this implementation whenever process waits it is added to a waiting queue of

processes associated with that semaphore. This is done through system call block() on
that process. When a process is completed it calls signal function and one process in
the queue is resumed. It uses wakeup() system call.

B.V.A.SWAMY 62 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

Topic: 2.2.1 Classical Problems of Synchronization

Semaphore can be used in other synchronization problems besides Mutual Exclusion.
Below are some of the classical problem depicting flaws of process synchronaization
in systems where cooperating processes are present.
We will discuss the following three problems:

1. Bounded Buffer (Producer-Consumer) Problem

2. Dining Philosophers Problem
3. The Readers Writers Problem

Bounded Buffer Problem

• This problem is generalised in terms of the Producer Consumer problem, where

a finite buffer pool is used to exchange messages between producer and consumer

processes.

Because the buffer pool has a maximum size, this problem is often called
the Bounded buffer problem.

• Solution to this problem is, creating two counting semaphores "full" and "empty" to

keep track of the current number of full and empty buffers respectively.

Dining Philosophers Problem

• The dining philosopher's problem involves the allocation of limited resources to a

group of processes in a deadlock-free and starvation-free manner.

• There are five philosophers sitting around a table, in which there are five

chopsticks/forks kept beside them and a bowl of rice in the centre, When a

philosopher wants to eat, he uses two chopsticks - one from their left and one from

their right. When a philosopher wants to think, he keeps down both chopsticks at

their original place.

B.V.A.SWAMY 63 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

The Readers Writers Problem

• In this problem there are some processes(called readers) that only read the shared

data, and never change it, and there are other processes(called writers) who may

change the data in addition to reading, or instead of reading it.

• There are various type of readers-writers problem, most centred on relative priorities

of readers and writers.

Bounded Buffer Problem

Bounded buffer problem, which is also called producer consumer problem, is one
of the classic problems of synchronization. Let's start by understanding the problem
here, before moving on to the solution and program code.

What is the Problem Statement?

There is a buffer of n slots and each slot is capable of storing one unit of data. There
are two processes running, namely, producer and consumer, which are operating
on the buffer.

Bounded Buffer Problem

A producer tries to insert data into an empty slot of the buffer. A consumer tries to
remove data from a filled slot in the buffer. As you might have guessed by now,
those two processes won't produce the expected output if they are being executed
concurrently.
There needs to be a way to make the producer and consumer work in an
independent manner.

Here's a Solution
One solution of this problem is to use semaphores. The semaphores which will be
used here are:

B.V.A.SWAMY 64 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

• m, a binary semaphore which is used to acquire and release the lock.

• empty, a counting semaphore whose initial value is the number of slots in the

buffer, since, initially all slots are empty.

• full, a counting semaphore whose initial value is 0.

At any instant, the current value of empty represents the number of empty slots in
the buffer and full represents the number of occupied slots in the buffer.

The Producer Operation

The pseudocode of the producer function looks like this:
do

// wait until empty > 0 and then decrement 'empty'

wait(empty);

// acquire lock

wait(mutex);

/* perform the insert operation in a slot */

// release lock

signal(mutex);

// increment 'full'

signal(full);

while(TRUE)

• Looking at the above code for a producer, we can see that a producer first waits until

there is atleast one empty slot.

• Then it decrements the empty semaphore because, there will now be one less

empty slot, since the producer is going to insert data in one of those slots.

• Then, it acquires lock on the buffer, so that the consumer cannot access the buffer

until producer completes its operation.

• After performing the insert operation, the lock is released and the value of full is

incremented because the producer has just filled a slot in the buffer.

B.V.A.SWAMY 65 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

The Consumer Operation

The pseudocode for the consumer function looks like this:
do

// wait until full > 0 and then decrement 'full'

wait(full);

// acquire the lock

wait(mutex);

/* perform the remove operation in a slot */

// release the lock

signal(mutex);

// increment 'empty'

signal(empty);

while(TRUE);

• The consumer waits until there is atleast one full slot in the buffer.

• Then it decrements the full semaphore because the number of occupied slots will be

decreased by one, after the consumer completes its operation.

• After that, the consumer acquires lock on the buffer.

• Following that, the consumer completes the removal operation so that the data from

one of the full slots is removed.

• Then, the consumer releases the lock.

• Finally, the empty semaphore is incremented by 1, because the consumer has just

removed data from an occupied slot, thus making it empty.

B.V.A.SWAMY 66 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.2.1

Dining Philosophers Problem

The dining philosophers problem is another classic synchronization problem which is
used to evaluate situations where there is a need of allocating multiple resources to
multiple processes.

What is the Problem Statement?

Consider there are five philosophers sitting around a circular dining table. The dining
table has five chopsticks and a bowl of rice in the middle as shown in the below
figure.

Dining Philosophers Problem

At any instant, a philosopher is either eating or thinking. When a philosopher wants

to eat, he uses two chopsticks - one from their left and one from their right. When a
philosopher wants to think, he keeps down both chopsticks at their original place.

Here's the Solution

From the problem statement, it is clear that a philosopher can think for an indefinite
amount of time. But when a philosopher starts eating, he has to stop at some point of
time. The philosopher is in an endless cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.

B.V.A.SWAMY 67 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

The code for each philosopher looks like:

while(TRUE)

wait(stick[i]);

/*

mod is used because if i=5, next

chopstick is 1 (dining table is circular)

*/

wait(stick[(i+1) % 5]);

/* eat */

signal(stick[i]);

signal(stick[(i+1) % 5]);

/* think */

When a philosopher wants to eat the rice, he will wait for the chopstick at his
left and picks up that chopstick. Then he waits for the right chopstick to be available,
and then picks it too. After eating, he puts both the chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them pickup one
chopstick, then a deadlock situation occurs because they will be waiting for another
chopstick forever. The possible solutions for this are:

• A philosopher must be allowed to pick up the chopsticks only if both the left and right

chopsticks are available.

• Allow only four philosophers to sit at the table. That way, if all the four philosophers

pick up four chopsticks, there will be one chopstick left on the table. So, one

philosopher can start eating and eventually, two chopsticks will be available. In this

way, deadlocks can be avoided.

B.V.A.SWAMY 68 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.2.1

What is Readers Writer Problem?

Readers writer problem is another example of a classic synchronization problem.
There are many variants of this problem, one of which is examined below.

The Problem Statement

There is a shared resource which should be accessed by multiple processes. There
are two types of processes in this context. They are reader and writer. Any number
of readers can read from the shared resource simultaneously, but only
one writer can write to the shared resource. When a writer is writing data to the
resource, no other process can access the resource. A writer cannot write to the
resource if there are non zero number of readers accessing the resource at that
time.

The Solution
From the above problem statement, it is evident that readers have higher priority
than writer. If a writer wants to write to the resource, it must wait until there are no
readers currently accessing that resource.
Here, we use one mutex m and a semaphore w. An integer variable read_count is
used to maintain the number of readers currently accessing the resource. The
variable read_count is initialized to 0. A value of 1 is given initially to m and w.
Instead of having the process to acquire lock on the shared resource, we use the
mutex m to make the process to acquire and release lock whenever it is updating
the read_count variable.
The code for the writer process looks like this:
while(TRUE)

wait(w);

/* perform the write operation */

signal(w);

B.V.A.SWAMY 69 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

And, the code for the reader process looks like this:
while(TRUE)

//acquire lock

wait(m);

read_count++;

if(read_count == 1)

wait(w);

//release lock

signal(m);

/* perform the reading operation */

// acquire lock

wait(m);

read_count--;

if(read_count == 0)

signal(w);

// release lock

signal(m);

Here is the Code uncoded(explained)

• As seen above in the code for the writer, the writer just waits on the w semaphore

until it gets a chance to write to the resource.

B.V.A.SWAMY 70 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.2.1

• After performing the write operation, it increments w so that the next writer can

access the resource.

• On the other hand, in the code for the reader, the lock is acquired whenever

the read_count is updated by a process.

• When a reader wants to access the resource, first it increments

the read_count value, then accesses the resource and then decrements

the read_count value.

• The semaphore w is used by the first reader which enters the critical section and the

last reader which exits the critical section.

• The reason for this is, when the first readers enters the critical section, the writer is

blocked from the resource. Only new readers can access the resource now.

• Similarly, when the last reader exits the critical section, it signals the writer using

the w semaphore because there are zero readers now and a writer can have the

chance to access the resource.

B.V.A.SWAMY 71 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.3

Topic: 2.3 Critical Region

Critical Region

According to the critical section problem using semaphore all processes must share a

semaphore variablemutex which is initialized to one. Each process must execute wait

(mutex) before entering the critical section and execute the signal (mutex) after completing

the execution but there are various difficulties may arise with this approach like:

Case 1:

Suppose that a process interchanges the order in which the wait and signal operations on

the semaphore mutex are executed, resulting in the following execution:

Signal (mutex);

..........

Critical Section

...........

Wait (mutex);

In this situation several processes may be executing in their critical sections simultaneously,

which is violating mutual exclusion requirement.

Case 2:

Suppose that a process replaces the signal (mutex) with wait (mutex). The execution is as

follows:

Wait (mutex);

...........

Critical Section

...........

Wait (mutex);

In this situation a deadlock will occur

B.V.A.SWAMY 72 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.3

Case 3:Suppose that a process omits the wait (mutex) and the signal (mutex). In this case

the mutual exclusion is violated or a deadlock will occur. To illustrate the various types or

error generated by using semaphore there are some high level language constructs have

been introduced such as critical region and monitor. Critical region is also known as

conditional critical regions. It constructs guards against certain simple errors associated with

semaphore. This high level language synchronization construct requires a variable V of type

T which is to be shared among many processes. It is declared as V: shared T;

The variable V can be accessed only inside a region statement as like below
Wait (mutex);
While (! B) {
First_count++;
if (second_count> 0)
Signal (second_delay);
Else
Signal (mutex);
Wait (first_delay);
First_count--;
Second_count++;
if (first_count> 0)
Signal (first_delay);
Else
Signal (second_delay);
Wait (second_delay);
Second_count --;
}
S;
if (first_count> 0)
Signal (first_delay);
Else if (second_count> 0)
Signal (second_delay);
Else
Signal (mutex);
B.V.A.SWAMY 73 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.4

Topic: 2.4 Monitors

Monitors
Monitor is one of the ways to achieve Process synchronization. Monitor is supported
by programming languages to achieve mutual exclusion between processes. For
example Java Synchronized methods. Java provides wait() and notify() constructs.
1. It is the collection of condition variables and procedures combined together in a
special kind of module or a package.
2. The processes running outside the monitor can’t access the internal variable of
monitor but can call procedures of the monitor.
3. Only one process at a time can execute code inside monitors.

Condition Variables
Two different operations are performed on the condition variables of the monitor.
Wait.
signal.

let say we have 2 condition variables

condition x, y; //Declaring variable

Wait operation
x.wait() : Process performing wait operation on any condition variable are suspended.
The suspended processes are placed in block queue of that condition variable.
Note: Each condition variable has its unique block queue.

Signal operation
x.signal(): When a process performs signal operation on condition variable, one of
the blocked processes is given chance.
If (x block queue empty)
// Ignore signal
else
// Resume a process from block queue.

B.V.A.SWAMY 74 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.5

Topic:2.5 Deadlocks
Principles of Deadlocks

Process Deadlocks in Operating System

A deadlock happens in operating system when two or more processes need some resource to complete
their execution that is held by the other process.

In the above diagram, the process 1 has resource 1 and needs to acquire resource 2. Similarly process
2 has resource 2 and needs to acquire resource 1. Process 1 and process 2 are in deadlock as each
of them needs the other’s resource to complete their execution but neither of them is willing to relinquish
their resources.
Coffman Conditions
A deadlock occurs if the four Coffman conditions hold true. But these conditions are not mutually
exclusive.

The Coffman conditions are given as follows −

• Mutual Exclusion
There should be a resource that can only be held by one process at a time. In the diagram
below, there is a single instance of Resource 1 and it is held by Process 1 only.

• Hold and Wait

A process can hold multiple resources and still request more resources from other processes
which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource
3 and is requesting the Resource 1 which is held by Process 1.

B.V.A.SWAMY 75 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.6

• No Preemption
A resource cannot be preempted from a process by force. A process can only release a
resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process
1. It will only be released when Process 1 relinquishes it voluntarily after its execution is
complete.

• Circular Wait
A process is waiting for the resource held by the second process, which is waiting for the
resource held by the third process and so on, till the last process is waiting for a resource held
by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2
and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting
Resource 2. This forms a circular wait loop.

Deadlock Detection
A deadlock can be detected by a resource scheduler as it keeps track of all the resources that are
allocated to different processes. After a deadlock is detected, it can be resolved using the following
methods −

• All the processes that are involved in the deadlock are terminated. This is not a good
approach as all the progress made by the processes is destroyed.
• Resources can be preempted from some processes and given to others till the deadlock is
resolved.
Deadlock Prevention
It is very important to prevent a deadlock before it can occur. So, the system checks each transaction
before it is executed to make sure it does not lead to deadlock. If there is even a slight chance that a
transaction may lead to deadlock in the future, it is never allowed to execute.

Deadlock Avoidance
It is better to avoid a deadlock rather than take measures after the deadlock has occurred. The wait for
graph can be used for deadlock avoidance. This is however only useful for smaller databases as it can
get quite complex in larger databases.

B.V.A.SWAMY 76 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.4

Topic: 2.6 System Model

System Model
● For the purposes of deadlock discussion, a system can be modeled as a collection of limited
resources, which can be partitioned into different categories, to be allocated to a number of
processes, each having different needs.

● Resource categories may include memory, printers, CPUs, open files, tape drives, CD-ROMS, etc.

● By definition, all the resources within a category are equivalent, and a request of this category can
be equally satisfied by any one of the resources in that category. If this is not the case ( i.e. if there is
some difference between the resources within a category ), then that category needs to be further
divided into separate categories. For example, "printers" may need to be separated into "laser
printers" and "color inkjet printers".

● Some categories may have a single resource.

● In normal operation a process must request a resource before using it, and release it when it is
done, in the following sequence:
1. Request - If the request cannot be immediately granted, then the process must wait until the
resource(s) it needs become available.
Example: system calls open( ), malloc( ), new( ), and request( ).
2. Use - The process uses the resource.
Example: prints to the printer or reads from the file.
3. Release - The process relinquishes the resource. so that it becomes available for other processes.
close( ), free( ), delete( ), and release( ).
● For all kernel-managed resources, the kernel keeps track of what resources are free and which are
allocated, to which process they are allocated, and a queue of processes waiting for this resource to
become available. Application-managed resources can be controlled using mutexes or wait( ) and
signal( ) calls, ( i.e. binary or counting semaphores. )

● A set of processes is deadlocked when every process in the set is waiting for a resource that is
currently allocated to another process in the set ( and which can only be released when that other
waiting process makes progress).

Topic:2.7 Deadlock Characterization

Deadlock Characterization
Necessary Conditions:
There are four conditions that are necessary to achieve deadlock: 91
Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process
requests this resource, then that process must wait for the resource to be released.

Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at
least one resource that is currently being held by some other process.

No preemption - Once a process is holding a resource ( i.e. once its request has been granted ),
then that resource cannot be taken away from that process until the process voluntarily releases it.

Circular Wait - A set of processes { P0, P1, P2, . . ., PN } must exist such that every P[ i ] is waiting
for P[ ( i + 1 ) % ( N + 1 ) ]. ( Note that this condition implies the hold-and-wait condition, but it is
easier to deal with the conditions if the four are considered separately. )

B.V.A.SWAMY 77 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.7

Resource-Allocation Graph
In some cases deadlocks can be understood more clearly through the use of Resource-Allocation
Graphs, having the following properties:
*A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as square nodes on the graph.
Dots inside the resource nodes indicate specific instances of the resource. ( E.g. two dots might
represent two laser printers. )
*A set of processes, { P1, P2, P3, . . ., PN }

*Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi has requested Rj,
and is currently waiting for that resource to become available.

*Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource Rj has been
allocated to process Pi, and that Pi is currently holding resource Rj.

Note that a request edge can be converted into an assignment edge by reversing the direction of the
arc when the request is granted. ( However note also that request edges point to the category box,
whereas assignment edges emanate from a particular instance dot within the box. )
For example:

92
*If a resource-allocation graph contains no cycles, then the system is not deadlocked. ( When looking
for cycles, remember that these are directed graphs. ) See the example in Figure 7.2 above.

*If a resource-allocation graph does contain cycles AND each resource category contains only a
single instance, then a deadlock exists.

*If a resource category contains more than one instance, then the presence of a cycle in the
resourceallocation graph indicates the possibility of a deadlock, but does not guarantee one.
Consider, for
example, Figures 7.3 and 7.4 below:

Fig: Resource Allocation Graph with cycle

B.V.A.SWAMY 78 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.8

Topic: 2.8 Methods of Handling Deadlock

METHODS OF HANDLING DEADLOCK
In general, there are four strategies of dealing with deadlock problem:
1. Deadlock Prevention: Prevent deadlock by resource scheduling so as to negate at least one of
the four
conditions.
2. Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
3. Deadlock Detection and Recovery: Detect deadlock and when it occurs, take steps to recover.
4. The Ostrich Approach: Just ignore the deadlock problem altogether.
Topic: 2.8.1

Topic:2.8.1 Deadlock Prevention

DEADLOCK PREVENTION
A deadlock may be prevented by denying any one of the conditions.
• Elimination of “Mutual Exclusion” Condition: The mutual exclusion condition must hold for
nonsharable resources. That is, several processes cannot simultaneously share a single resource.
This condition is difficult to eliminate because some resources, such as the Hard disc drive and
printer, are inherently non-shareable. Note that shareable resources like read-only-file do not require
mutually exclusive access and thus cannot be involved in deadlock.

• Elimination of “Hold and Wait” Condition: There are two possibilities for elimination of the
second condition. The first alternative is that a process request be granted all of the resources it
needs at once, prior to execution. The second alternative is to disallow a process from requesting
resources whenever it has previously allocated resources. This strategy requires that all of the
resources a process will need must be requested at once. The system must grant resources on “all or
none” basis. If the complete set of resources needed by a process is not currently available, then the
process must wait until the complete set is available. While the process waits, however, it may not
hold any resources. Thus the “wait for” condition is denied and deadlocks cannot occur. This strategy
can lead to serious waste of resources.

• Elimination of “No-preemption” Condition: The non-preemption condition can be alleviated by

forcing a process waiting for a resource that cannot immediately be allocated to relinquish all of its
currently held resources, so that other processes may use them to finish. This strategy requires that
when a process that is holding some resources is denied a request for additional resources. The
process must release its held resources and, if necessary, request them again together with
additional resources. Implementation of this strategy denies the “no-preemptive” condition effectively.

• Elimination of “Circular Wait” Condition: The last condition, the circular wait, can be denied by
imposing a total ordering on all of the resource types and then forcing, all processes to request the
resources in order (increasing or decreasing). This strategy impose a total ordering of all resources
types, and to require that each process requests resources in a numerical order (increasing or
decreasing) of enumeration. With this rule, the resource allocation graph can never have a cycle.

For example, provide a global numbering of all the resources, as shown

1 ≡ Card reader
2 ≡ Printer
3 ≡ Optical driver
4 ≡ HDD
5 ≡ Card punch

Now the rule is this: processes can request resources whenever they want to, but all requests must
be made in numerical order. A process may request first printer and then a HDD(order: 2, 4), but it
may not request first a optical driver and then a printer (order: 3, 2). The problem with this strategy is
that it may be impossible to find an ordering that satisfies everyone.

B.V.A.SWAMY 79 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.8.2

Topic: 2.8.2 Deadlock Avoidance

DEADLOCK AVOIDANCE

This approach to the deadlock problem anticipates deadlock before it actually occurs. This approach
employs an algorithm to access the possibility that deadlock could occur and acting accordingly. If the
necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being careful
when resources are allocated. It employs the most famous deadlock avoidance algorithm that is the
Banker’s algorithm.

A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a

circular wait condition can never exist. The resource-allocation state is defined by the number of
available and allocated resources, and the maximum demands of the processes.

Safe and Unsafe States

A system is said to be in a Safe State, if there is a safe execution sequence. An execution sequence
is an ordering for process execution such that each process runs until it terminates or blocked and all
request for resources are immediately granted if the resource is available.

A system is said to be in an Unsafe State, if there is no safe execution sequence. An unsafe state
may not be deadlocked, but there is at least one sequence of requests from processes that would
make the system deadlocked.

(Relation between Safe, Unsafe and Deadlocked States)

Resource-Allocation Graph Algorithm

The deadlock avoidance algorithm uses a variant of the resource-allocation graph to avoid
deadlocked state. It introduces a new type of edge, called a claim edge. A claim edge Pi Rj
indicates that process Pi may request resource Rj at some time in the future.
This edge resembles a request edge in direction, but is represented by a dashed line. When process
Pi requests resource Rj, the claim edge Pi Rj is converted to a request edge. Similarly, when a
resource Rj is released by Pi, the assignment edge Rj Pi is reconverted to a claim edge Pi
Rj.

Suppose that process Pi requests resource Rj. The request can be granted only if converting the
request edge Pi Rj to an assignment edge Rj Pi that does not result in the formation of a
cycle in the resource-allocation graph. An algorithm for detecting a cycle in this graph is called cycle
detection algorithm.

If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is
found, then the allocation will put the system in an unsafe state. Therefore, process Pi will have to
wait for its requests to be satisfied.

B.V.A.SWAMY 80 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.8.2

Banker's algorithm

The Banker's algorithm is a resource allocation & deadlock avoidance algorithm developed by
Edsger Dijkstra that test for safety by simulating the allocation of pre-determined maximum possible
amounts of all resources. Then it makes a "safe-state" check to test for possible deadlock conditions
for all other pending activities, before deciding whether allocation should be allowed to continue.

The Banker's algorithm is run by the operating system whenever a process requests resources. The
algorithm prevents deadlock by denying or postponing the request if it determines that accepting the
request could put the system in an unsafe state (one where deadlock could occur).

For the Banker's algorithm to work, it needs to know three things:

• How much of each resource could possibly request by each process.
• How much of each resource is currently holding by each process.
• How much of each resource the system currently has available.

Resources may be allocated to a process only if it satisfies the following conditions:

1. request ≤ max, else set error as process has crossed maximum claim made by it.
2. request ≤ available, else process waits until resources are available.

Several data structures must be maintained to implement the banker's algorithm. These data
structures encode the state of the resource-allocation system. Let n be the number of processes in
the system and m be the number of resource types.

We need the following data structures:

Available: A vector of length m indicates the number of available resources of each type. If
Available[j] = k, there are k instances of resource type Rj available.

Max: An n x m matrix defines the maximum demand of each process. If Max[i,j] = k, then process Pi
may request at most k instances of resource type Rj.

Allocation: An n x m matrix defines the number of resources of each type currently allocated to each
process. If
Allocation[i,j] = k, then process Pi is currently allocated k instances of resource type Rj.

Need: An n x m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then
process Pi may need k more instances of resource type Ri to complete its task. Note that Need[i,j] =
Max[i,j] - Allocafion[i,j].

These data structures vary over time in both size and value. The vector Allocationi specifies the
resources currently allocated to process Pi; the vector Needi specifies the additional resources that
process Pi may still request to complete its task.

B.V.A.SWAMY 81 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.8.2

Safety Algorithm
The algorithm for finding out whether or not a system is in a safe state can be described as follows:

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

Work := Available and Finisk[i] :=false for i = 1,2, ..., n.

2. Find an i such that both a. Finisk[i] =false

b. Needi < Work.
If no such i exists, go to step 4.

3. Work := Work + Allocationi

Finisk[i] := true
go to step 2.

4. If Finish[i] = true for all i, then the system is in a safe state.

This algorithm may require an order of m x n2 operations to decide whether a state is safe.

Resource-Request Algorithm
Let Requesti be the request vector for process Pi. If Requesti[j] = k, then process Pi wants k instances
of resource type Rj. When a request for resources is made by process Pi, the following actions are
taken:
1. If Requesti < Needi, go to step 2. Otherwise, raise an error condition, since the process has
exceeded its maximum claim.

2. If Requesti < Available, go to step 3. Otherwise, Pi must wait, since the resources are not
available.

3. Have the system pretend to have allocated the requested resources to process Pi by
modifying the state as follows:

Available : = Available - Requesti;

Allocationi : = Allocationi + Requesti;
Needi : = Needi - Requesti;

If the resulting resource-allocation state is safe, the transaction is completed and process Pi is
allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti and the old
resource-allocation state is restored.

Consider a system with five processes P0 through P4 and three resource types A,B,C. Resource type
A has 10 instances, resource type B has 5 instances, and resource type C has 7 instances. Suppose
that, at time T0, the following snapshot of the system has been taken:

B.V.A.SWAMY 82 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.8.2

that the sequence <PI, P3, P4, P0, P2> satisfies our safety requirement. Hence, we can immediately

grant the request of process PI.

However, that when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since

the resources are not available. A request for (0,2,0) by Po cannot be granted, even though the

resources are available, since the resulting state is unsafe.

B.V.A.SWAMY 83 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 2.8.3

Topic: 2.8.3 Deadlock Detection

DEADLOCK DETECTION
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a
deadlock situation may occur. In this environment, the system must provide:
• An algorithm that examines the state of the system to determine whether a deadlock has occurred.
• An algorithm to recover from the deadlock.
According to number of instances in each resource type, the Deadlock Detection algorithm can be
classified into two categories as follows:

1. Single Instance of Each Resource Type: If all resources have only a single
instance, then it can define a deadlock detection algorithm that uses a variant of the
resource-allocation graph (is called a wait-for graph).

A wait–for graph can be draw by removing the nodes of type resource and collapsing the appropriate
edges from the resource-allocation graph.

An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a
resource that Pi needs. An edge Pi Pj exists in a wait-for graph if and only if the corresponding
resource allocation graph contains two edges Pi Rq and Rq Pj for some resource Rq. For
Example:

((a) Resource-allocation graph. (b) Corresponding wait-for graph)

A deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks,
the system needs to maintain the wait-for graph and periodically to invoke an algorithm that searches
for a cycle in the graph. An algorithm to detect a cycle in a graph requires an order of n2 operations,
where n is the number of vertices in the graph.

Several Instances of a Resource Type: The following deadlock-detection algorithm is applicable to

several instance of a resource type .

The algorithm employs several time-varying data structures:

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[i,j] = k, then
process Pi I requesting k more instances of resource type Rj.

B.V.A.SWAMY 84 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 2.8.4

The detection algorithm is described as follows:

1. Let Work and Finish be vectors of length m and n, respectively.
Initialize, Work := Available. 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.
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 a deadlock state.
if Finish[i] =false, then process Pi is deadlocked.
This algorithm requires an order of m x n2 operations to detect whether the system is in a deadlocked
state.

Topic: 2.8.4 Recovery From Deadlock

RECOVERY FROM DEADLOCK

When a detection algorithm determines that a deadlock exists, then the system or operator is
responsible for handling deadlock problem. There are two options for breaking a deadlock.
1. Process Termination
2. Resource preemption

Process Termination
There are two method to eliminate deadlocks by terminating a process as follows:

1.Abort all deadlocked processes: This method will break the deadlock cycle clearly by terminating
all process. This method is cost effective. And it removes the partial computations completed by the
processes.

2.Abort one process at a time until the deadlock cycle is eliminated: This method terminates one
process at a time, and invokes a deadlock-detection algorithm to determine whether any processes
are still deadlocked.

Resource Preemption
In resource preemption, the operator or system preempts some resources from processes and give
these resources to other processes until the deadlock cycle is broken.

If preemption is required to deal with deadlocks, then three issues need to be addressed:
1. Selecting a victim: The system or operator selects which resources and which processes are to
be preempted based on cost factor.
2. Rollback: The system or operator must roll back the process to some safe state and restart it from
that state.

3. Starvation: The system or operator should ensure that resources will not always be preempted
from the same process?

B.V.A.SWAMY 85 | P a g e
DEPT. OF COMPUTER SCIENCE

Difference between Deadlock and Starvation in OS

Deadlock:
Deadlock occurs when each process holds a resource and wait for other resource
held by any other process. Necessary conditions for deadlock to occur are Mutual
Exclusion, Hold and Wait, No Preemption and Circular Wait. In this no process
holding one resource and waiting for another get executed. For example, in the
below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which
is acquired by process 2, and process 2 is waiting for resource 1. Hence both
process 1 and process 2 are in deadlock.

Starvation:
Starvation is the problem that occurs when high priority processes keep
executing and low priority processes get blocked for indefinite time. In heavily
loaded computer system, a steady stream of higher-priority processes can
prevent a low-priority process from ever getting the CPU. In starvation resources
are continuously utilized by high priority processes. Problem of starvation can be
resolved using Aging. In Aging priority of long waiting processes is gradually
increased.

B.V.A.SWAMY 86 | P a g e
DEPT. OF COMPUTER SCIENCE

Difference between Deadlock and Starvation:

S.NO Deadlock Starvation

High priority processes keep

All processes keep waiting for each executing and low priority processes
1. other to complete and none get executed are blocked

Resources are continuously utilized by

2. Resources are blocked by the processes high priority processes

Necessary conditions Mutual Exclusion,

Hold and Wait, No preemption, Circular Priorities are assigned to the
3. Wait processes

4. Also known as Circular wait Also know as lived lock

It can be prevented by avoiding the

5. necessary conditions for deadlock It can be prevented by Aging

B.V.A.SWAMY 87 | P a g e
DEPT. OF COMPUTER SCIENCE

ADIKAVI NANNAYA UNIVERSITY

MSN CAMPUS – KAKINADA
DEPARTMENT OF COMPUTER SCIENCE
MASTER OF COMPUTER APPLICATIONS
SUBJECT- (19105) OPERATING SYSTEMS MATERIAL

UNIT – III
TOPICS

Memory Management: Page No

3.1 Logical Versus Physical Address, 89

3.2 Swapping, 91

3.3 Contiguous Memory Allocation, 92

3.4 Paging, 94

3.5 Structure of the Page Table, 99

3.6 Segmentation, 102

3.7 Virtual Memory, 105

3.8 Demand Paging, 106

3.9 Page Replacement Algorithms, 108

3.10 Thrashing 111

File System Implementation: Page No

3.11 Concept of a file and File System 113

Structure
3.12 Access Methods, 116

3.13 Directory Structure and Directory 117

Management
3.14 Allocation Methods, 120

3.15 Free Space Management, 122

3.16 Device Drivers.

B.V.A.SWAMY 88 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.1

UNIT – III
Topic: 3.1 Logical Versus Physical Address
Logical Versus Physical Address Space
• The concept of a logical address space that is bound to a separate physicaladdress space
is central to proper memory management.
o Logical address – address generated by the CPU; also referred to as virtual
address.
o Physical address – address seen by the memory unit.
• The set of all logical addresses generated by a program is a logical address space; the set
of all physical addresses corresponding to these logical addresses are a physical address
space.

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

• The run-time mapping from virtual to physical addresses is done by a hardware device called the
memory management unit (MMU).

• This method requires hardware support slightly different from the hardware configuration. The
base register is now called a relocation register. The value in the relocation register is added to
every address generated by a user process at the time it is sent to memory.

• The user program never sees the real physical addresses. The program can create a pointer to
location 346, store it in memory, manipulate it and compare it to other addresses. The user
program deals with logical addresses. The memory mapping hardware converts logical addresses
into physical addresses. The final location of a referenced memory address is not determined
until the reference is made.

B.V.A.SWAMY 89 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.1

Dynamic Loading

• Routine is not loaded until it is called.

• All routines are kept on disk in a relocatable load format.

• The main program is loaded into memory and is executed. When a routine needs to call another
routine, the calling routine first checks to see whether the other the desired routine into memory
and to update the program’s address tables to reflect this change. Then control is passed to the
newly loaded routine.

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

Dynamic Linking

• Linking is postponed until execution time.

• Small piece of code, stub, is used to locate the appropriate memory-resident library routine, or to
load the library if the routine is not already present.

• When this stub is executed, it checks to see whether the needed routine is already in memory. If
not, the program loads the routine into memory.

• Stub replaces itself with the address of the routine, and executes the routine.

• Thus the next time that code segment is reached, the library routine is executed directly,
incurring no cost for dynamic linking.

• Operating system is needed to check if routine is in processes’ memory address.

Dynamic linking is particularly useful for libraries.

B.V.A.SWAMY 90 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.2

Topic: 3.2 Swapping

Swapping
• A process can be swapped temporarily out of memory to a backing store, and then brought back
into memory for continued execution. For example, assume a multiprogramming environment with
a round robin CPU scheduling algorithm. When a quantum expires, the memory manager will start
to swap out the process that just finished, and to swap in another process to the memory space that
has been freed. In the mean time, the CPU scheduler will allocate a time slice to some other process
in memory. When each process finished its quantum, it will be swapped with another process.
Ideally, the memory manager can swap processes fast enough that some processes will be in
memory, ready to execute, when the CPU scheduler wants to reschedule the CPU. The quantum
must also be sufficiently large that reasonable amounts of computing are done between swaps.
Roll out, roll in – swapping variant used for priority-based scheduling algorithms. If a higher
priority process arrives and wants service, the memory manager can swap out the lower priority
process so that it can load and execute lower priority process can be swapped back in and
continued. This variant is some times called roll out, roll in. Normally a process that is swapped
out will be swapped back into the same memory space that it occupied previously. This
restriction is dictated by the process cannot be moved to different locations. If execution time
binding is being used, then a process can be swapped into a different memory space, because the
physical addresses are computed during execution time.

• Backing store – fast disk large enough to accommodate copies of all memory images for all
users; must provide direct access to these memory images. It must be large enough to accommodate
copies of all memory images for all users, and it must provide direct access to these memory images.
The system maintains a ready queue consisting of all processes whose memory images are scheduler
decides to execute a process it calls the dispatcher. The dispatcher checks to see whether the next
process in the queue is in memory. If not, and there is no free memory region, the dispatcher swaps
out a process currently in memory and swaps in the desired process. It then reloads registers as
normal and transfers control to the selected process.
• 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).

B.V.A.SWAMY 91 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.3

Topic: 3.3 Contiguous Memory Allocation

Contiguous Memory Allocation
• Main memory is usually divided into two partitions:

o Resident operating system, usually held in low memory with interrupt vector.

o User processes, held in high memory.

• In contiguous memory allocation, each process is contained in a single contiguous section of
memory.
• Single-partition allocation
o Relocation-register scheme used to protect user processes from each other, and from
changing operating-system code and data. Relocation register contains value of
smallest physical address; limit register contains range of logical addresses – each
logical address must be less than the limit register.

• Multiple-partition allocation

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

a) allocated partitions b) free partitions (hole)

o A set of holes of various sizes, is scattered throughout memory at any given time.
When a process arrives and needs memory, the system searches this set for a hole that is
large enough for this process. If the hole is too large, it is split into two: one part is
allocated to the arriving process; the other is returned to the set of holes. When a process
terminates, it releases its block of memory, which is then placed back in the set of holes.
If the new hold is adjacent to other holes, these adjacent holes are merged to form one
larger hole.

B.V.A.SWAMY 92 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.3

• This procedure is a particular instance of the general dynamic storage allocation problem,
which is how to satisfy a request of size n from a list of free holes. There are many solutions
to this problem. The set of holes is searched to determine which hole is best to allocate. The
first-fit, best-fit and worst-fit strategies are the most common ones used to select a free hole
from the set of available holes.

o First-fit: Allocate the first hole that is big enough.

o Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless
ordered by size.

o Worst-fit: Allocate the largest hole; must also search entire list.

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

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

B.V.A.SWAMY 93 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.4

Topic: 3.4 Paging

Paging
• Paging is a memory management scheme that permits the physical address space of a process to
be non contiguous.

• Divide physical memory into fixed-sized blocks called frames (size is power of 2, for example
512 bytes).

• Divide logical memory into blocks of same size called pages. When a process is to be executed,
its pages are loaded into any available memory frames from the backing store. The backing store
is divided into fixed sized blocks that are of the same size as the memory frames.

• The hardware support for paging is illustrated in below figure.

• Every address generated by the CPU is divided into two parts: a page number (p) and a page
offset (d). The page number is used as an index into a page table. The page table contains the
base address of each page in physical memory. This base address is combined with the page
offset to define the physical memory address that is sent to the memory unit.

• The paging model of memory is shown in below figure. The page size is defined by the
hardware. The size of a page is typically of a power of 2, varying between 512 bytes and 16 MB
per page, depending on the computer architecture. The selection of a power of 2 as a page size
makes the translation of a logical address into a page number and page offset particularly easy. If
the size of logical address is 2m, and a page size is 2n addressing units, then the high order m-n
bits of a logical address designate the page number, and the n low order bits designate the page
offset.

B.V.A.SWAMY 94 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.4

• 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 may occur. Let us take an example. Suppose a program needs 32 KB
memory for allocation. The whole program is divided into smaller units assuming 4 KB and is
assigned some address. The address consists of two parts such as:

• A large number in higher order positions and

• Displacement or offset in the lower order bits.

The numbers allocated to pages are typically in power of 2 to simplify extraction of page numbers
and offsets. To access a piece of data at a given address, the system first extracts the page number
and the offset. Then it translates the page number to physical page frame and access data at offset in
physical page frame. At this moment, the translation of the address by the OS is done using a page
table. Page table is a linear array indexed by virtual page number which provides the physical page
frame that contains the particular page. It employs a lookup process that extracts the page number
and the offset. The system in addition checks that the page number is within the address space of
process and retrieves the page number in the page table. Physical address will calculated by using the
formula.

Physical address = page size of logical memory X frame number + offset

B.V.A.SWAMY 95 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 3.4

When a process arrives in the system to be executed, its size expressed in pages is examined. Each
page of the process needs one frame. Thus if the process requires n pages, at least n frames must be
available in memory. If n frames are available, they are allocated to this arriving process. The first
page of the process is loaded into one of the allocated frames, and the frame number is put in the
page table for this process. The next page is loaded into another frame, and its frame number is put
into the page table and so on as in below figure. An important aspect of paging is the clear
separation between the user’s view of memory and the actual physical memory. The user program
views that memory as one single contiguous space, containing only this one program. In fact, the
user program is scattered throughout physical memory, which also holds other programs. The
difference between the user’s view of memory and the actual physical memory is reconciled by the
address-translation hardware. The logical addresses are translated into physical addresses. This
mapping is hidden from the user and is controlled by the operating system.

B.V.A.SWAMY 96 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.4

Implementation of Page Table

• Page table is kept in main memory.
• Page-tablebase register (PTBR) points to the page table.
• In this scheme every data/instruction-byte access requires two memory accesses. One for the
page-table entry and one for the byte.
• The two memory access problem can be solved by the use of a special fast-lookup hardware
cache called associative registers or associative memory or translation look-aside buffers(TLBs).
• Typically, the number of entries in a TLB is between 32 and 1024.

• The TLB contains only a few of the page table entries. When a logical address is generated by
the CPU, its page number is presented to the TLB. If the page number is found, its frame
number is immediately available and is used to access memory. The whole task may take less
than 10 percent longer than it would if an unmapped memory reference were used.

• If the page number is not in the TLB (known as a TLB miss), a memory reference to the
page table must be made. When the frame number is obtained, we can use it to access
memory.

Hit Ratio
• Hit Ratio: the percentage of times that a page number is found in the associative registers.

• For example, if it takes 20 nanoseconds to search the associative memory and 100 nanoseconds
to access memory; for a 98-percent hit ratio, we have

Effective memory-access time = 0.98 x 120 + 0.02 x 220

= 122 nanoseconds.

• The Intel 80486 CPU has 32 associative registers, and claims a 98-percent hit ratio.
B.V.A.SWAMY 97 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.4

Valid or invalid bit in a page table

• Memory protection implemented by associating protection bit with each frame.
• Valid-invalid bit attached to each entry in the page table:

o “Valid” indicates that the associated page is in the process’ logical address space, and is
thus a legal page.
o “Invalid” indicates that the page is not in the process’ logical address space.
• Pay attention to the following figure. The program extends to only address 10,468, any
reference beyond that address is illegal. However, references to page 5 are classified as valid,
so accesses to addresses up to 12,287 are valid. This reflects the internal fragmentation of
paging.

B.V.A.SWAMY 98 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic:3.5

Topic: 3.5 Structure of the Page table

Structure of the Page Table
Hierarchical Paging:
• A logical address (on 32-bit machine with 4K page size) is divided into:
o A page number consisting of 20 bits.
o A page offset consisting of 12 bits.
• Since the page table is paged, the page number is further divided into:
o A 10-bit page number.
o A 10-bit page offset.

• Thus, a logical address is as follows:

Where p1 is an index into the outer page table, and p2 is the displacement within the page of the
outer page table. The below figure shows a two level page table scheme.

Address-translation scheme for a two-level 32-bit paging architecture is shown in below figure

B.V.A.SWAMY 99 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.5

Hashed Page Table:

A common approach for handling address spaces larger than 32 bits is to use a hashed page table,
with the hash value being the virtual page number. Each entry in the hash table contains a linked list
of elements that has to the same location. Each element consists of three fields: (a) the virtual page
number, (b) the value of the mapped page frame, and (c) a pointer to the next element in the linked
list. The algorithm works as follows: The virtual page number in the virtual address is hashed into the
hash table. The virtual page number is compared to field (a) in the first element in the linked list. If
there is a match, the corresponding page frame (field (b)) is used to form the desired physical
address. If there is no match, subsequent entries in the linked list are searched for a matching virtual
page number. The scheme is shown in below figure.

Inverted Page Table:

• One entry for each real page (frame) of memory.
• Entry consists of the virtual address of the page stored in that real memory location, with
information about the process that owns that page.
• There is only one page table in the system. Not per process.
• Decreases memory needed to store each page table, but increases time needed to search the table
when a page reference occurs.
Use hash table to limit the search to one — or at most a few — page-table entries

B.V.A.SWAMY 100 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.5

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> where the process-id assumes the role
of the address space identifier. When a memory reference occurs, part of the virtual address,
consisting of <process-id, page-number>, is presented to the memory subsystem. The inverted page
table is then searched for a match. If a match is found say at entry i, then the physical address <i,
offset> is generated. If no match is found, then an illegal address access has been attempted.

Shared Page:
• Shared code
o One copy of read-only (reentrant) code shared among processes (i.e., text editors,
compilers, window systems).

o Shared code must appear in same location in the logical address space of all processes.

• Private code and data

o Each process keeps a separate copy of the code and data.

o The pages for the private code and data can appear anywhere in the logical address
space.

Reentrant code or pure code is non self modifying code. If the code is reentrant, then it 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 registers and data storage to hold the data for the process’
execution. The data for two different processes will of course vary for each process.

B.V.A.SWAMY 101 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.6

Topic: 3.6 Segmentation

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,
Object,

Local variables, global

variables, Common block,
Stack,
Symbol table, arrays

• Segmentation is a memory management scheme that supports this user view of memory.

• A logical address space is a collection of segments. Each segment has a name and a length.

• The addresses specify both the segment name and the offset within the segment.

• The user therefore specifies each address by two quantities such as segment name and an offset.
For simplicity of implementation, segments are numbered and are referred to by a segment
number, rather than by a segment name.

• Logical address consists of a two tuples:

<segment-number, offset>

B.V.A.SWAMY 102 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.6

• Segment table – maps two-dimensional physical addresses; each table entry has:

o Base – contains the starting physical address where the segments reside in memory.

o Limit – specifies the length of the segment.

• Segment-table base register (STBR) points to the segment table’s location in memory.

• Segment-table length register (STLR) indicates number of segments used by a program;

Segment number s is legal if s< STLR.

• When the user program is compiled by the compiler it constructs the segments.
• The loader takes all the segments and assigned the segment numbers.
• The mapping between the logical and physical address using the segmentation technique is
shown in above figure.
• Each entry in the segment table as limit and base address.
• The base address contains the starting physical address of a segment where the limit address
specifies the length of the segment.
• The logical address consists of 2 parts such as segment number and offset.
• The segment number is used as an index into the segment table. Consider the below
example is given below.

B.V.A.SWAMY 103 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.6

Segmentation with Paging

• Both paging and segmentation have advantages and disadvantages, that’s why we can combine
these two methods to improve this technique for memory allocation.

• These combinations are best illustrated by architecture of Intel-386.

• The IBM OS/2 is an operating system of the Intel-386 architecture. In this technique both
segment table and page table is required.

• The program consists of various segments given by the segment table where the segment table
contains different entries one for each segment.
Then each segment is divided into a number of pages of equal size whose information is maintained
in a separate page table.

• If a process has four segments that is 0 to 3 then there will be 4 page tables for that process, one
for each segment.

• The size fixed in segmentation table (SMT) gives the total number of pages and therefore
maximum page number in that segment with starting from 0.

• If the page table or page map table for a segment has entries for page 0 to 5.

• The address of the entry in the PMT for the desired page p in a given segment s can be obtained
by B + P where B can be obtained from the entry in the segmentation table.
Using the address (B +P) as an index in page map table (page table), the page frame (f) can be
obtained and physical address can be obtained by adding offset to page frame.

B.V.A.SWAMY 104 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.7

Topic: 3.7 Virtual Memory

Virtual Memory
• It is a technique which allows execution of process that may not be compiled within the primary
memory.

• It separates the user logical memory from the physical memory. This separation allows an
extremely large memory to be provided for program when only a small physical memory is
available.

• Virtual memory makes the task of programming much easier because the programmer no longer
needs to working about the amount of the physical memory is available or not.

• The virtual memory allows files and memory to be shared by different processes by page
sharing.

It is most commonly implemented by demand paging

B.V.A.SWAMY 105 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.8

Topic: 3.8 Demand Paging

Demand Paging
A demand paging system is similar to the paging system with swapping feature. When we want to
execute a process we swap it into the memory. A swapper manipulates entire process where as a
pager is concerned with the individual pages of a process. The demand paging concept is using pager
rather than swapper. When a process is to be swapped in, the pager guesses which pages will be used
before the process is swapped out again. Instead of swapping in a whole process, the pager brings
only those necessary pages into memory. The transfer of a paged memory to contiguous disk space is
shown in below figure.

Thus it avoids reading into memory pages that will not used any way decreasing the swap time and
the amount of physical memory needed. In this technique we need some hardware support to
distinct between the pages that are in memory and those that are on the disk. A valid and invalid bit
is used for this purpose. When this bit is set to valid it indicates that the associate page is in memory.
If the bit is set to invalid it indicates that the page is either not valid or is valid but currently not in
the disk.

B.V.A.SWAMY 106 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.8

Marking a page invalid will have no effect if the process never attempts to access that page. So while
a process executes and access pages that are memory resident, execution proceeds normally. Access
to a page marked invalid causes a page fault trap. It is the result of the OS’s failure to bring the
desired page into memory.

Procedure to handle page fault

If a process refers to a page that is not in physical memory then

• We check an internal table (page table) for this process to determine whether the reference was
valid or invalid.

• If the reference was invalid, we terminate the process, if it was valid but not yet brought in, we
have to bring that from main memory.

• Now we find a free frame in memory.

• Then we read the desired page into the newly allocated frame.

• When the disk read is complete, we modify the internal table to indicate that the page is now in
memory.

We restart the instruction that was interrupted by the illegal address trap. Now the process can access
the page as if it had always been in memory

B.V.A.SWAMY 107 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.9

Topic: 3.9 Page Replacement algorithm

Page Replacement
• Each process is allocated frames (memory) which hold the process’s pages (data)

• Frames are filled with pages as needed – this is called demand paging
•
Over-allocation of memory is prevented by modifying the page-fault service routine to replace
pages

• The job of the page replacement algorithm is to decide which page gets victimized to make room
for a new page

• Page replacement completes separation of logical and physical memory

Page Replacement Algorithm

Optimal algorithm
• Ideally we want to select an algorithm with the lowest page-fault rate

• Such an algorithm exists, and is called (unsurprisingly) the optimal algorithm:

• Procedure: replace the page that will not be used for the longest time (or at all) – i.e. replace the
page with the greatest forward distance in the reference string

• Example using 4 frames:

Reference # 1 2 3 4 5 6 7 8 9 10 11 12
Page referenced 1 2 3 4 1 2 5 1 2 3 4 5
Frames 1 1 1 1 1 1 1 1 1 1 4 4
_ = faulting page 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3
4 4 4 5 5 5 5 5 5

• Analysis: 12 page references, 6 page faults, 2 page replacements. Page faults per number of
frames = 6/4 = 1.5

• Unfortunately, the optimal algorithm requires special hardware (crystal ball, magic mirror, etc.)
not typically found on today’s computers

• Optimal algorithm is still used as a metric for judging other page replacement algorithms

B.V.A.SWAMY 108 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.9

FIFO algorithm (First In First Out)

• Replaces pages based on their order of arrival: oldest page is replaced

Example using 4 frames

Reference # 1 2 3 4 5 6 7 8 9 10 11 12
Page referenced 1 2 3 4 1 2 5 1 2 3 4 5
Frames 1 1 1 1 1 1 5 5 5 5 4 4
_ = faulting page 2 2 2 2 2 2 1 1 1 1 5
3 3 3 3 3 3 2 2 2 2
4 4 4 4 4 4 3 3 3

• Analysis: 12 page references, 10 page faults, 6 page replacements. Page faults per number of
frames = 10/4 = 2.5

LFU algorithm (page-based) .

• procedure: replace the page which has been referenced least often
• For each page in the reference string, we need to keep a reference count. All reference counts
start at 0 and are incremented every time a page is referenced.
• example using 4 frames:
Reference # 1 2 3 4 5 6 7 8 9 10 11 12
Page referenced 1 2 3 4 1 2 5 1 2 3 4 5
Frames 11 11 11 11 21 21 21 31 31 31 31 31

_ = faulting page 12 12 12 12 22 22 22 32 32 32 32

n = reference count 13 13 13 13 15 15 15 23 23 25

14 14 14 14 14 14 14 24 24

• At the 7th page in the reference string, we need to select a page to be victimized. Either 3 or 4
will do since they have the same reference count (1). Let’s pick 3.

• Likewise at the 10th page reference; pages 4 and 5 have been referenced once each. Let’s pick
page 4 to victimize. Page 3 is brought in, and its reference count (which was 1 before we paged it
out a while ago) is updated to 2.

• Analysis: 12 page references, 7 page faults, 3 page replacements. Page faults per number of
frames = 7/4 = 1.75

LFU algorithm (frame-based)

• Procedure: replace the page in the frame which has been referenced least often

B.V.A.SWAMY 109 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.9

• Need to keep a reference count for each frame which is initialized to 1 when the page is paged in,
incremented every time the page in the frame is referenced, and reset every time the page in the
frame is replaced

• Example using 4 frames:

Reference # 1 2 3 4 5 6 7 8 9 10 11 12
Page referenced 1 2 3 4 1 2 5 1 2 3 4 5
Frames 11 11 11 11 21 21 21 31 31 31 31 31

_ = faulting page 12 12 12 12 22 22 22 32 32 32 32

n = reference count 13 13 13 13 15 15 15 13 13 15

14 14 14 14 14 14 14 24 24

• At the 7th reference, we victimize the page in the frame which has been referenced least often --
in this case, pages 3 and 4 (contained within frames 3 and 4) are candidates, each with a reference
count of 1. Let’s pick the page in frame 3. Page 5 is paged in and frame 3’s reference count is reset
to 1.

• At the 10th reference, we again have a page fault. Pages 5 and 4 (contained within frames 3 and
4are candidates, each with a count of 1. Let’s pick page 4. Page 3 is paged into frame 3, and frame 3’s
reference count is reset to 1.
• Analysis: 12 page references, 7 page faults, 3 page replacements. Page faults per number of
frames = 7/4 = 1.75

LRU algorithm
• Replaces pages based on their most recent reference – replace the page with the greatest
backward distance in the reference string

• Example using 4 frames:

Reference # 1 2 3 4 5 6 7 8 9 10 11 12
Page referenced 1 2 3 4 1 2 5 1 2 3 4 5
Frames 1 1 1 1 1 1 1 1 1 1 1 5
_ = faulting page 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 4 4
4 4 4 4 4 4 3 3 3

• Analysis: 12 page references, 8 page faults, 4 page replacements. Page faults per number of
frames = 8/4 = 2
• One possible implementation (not necessarily the best):
o Every frame has a time field; every time a page is referenced, copy the current time into
its frame’s time field.
o When a page needs to be replaced, look at the time stamps to find the oldest
B.V.A.SWAMY 110 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.10

Topic: 3.10 Thrashing

Thrashing
• If a process does not have “enough” pages, the page-fault rate is very high

– low CPU utilization

– OS thinks it needs increased multiprogramming
– adds another process to system
• Thrashing is when a process is busy swapping pages in and out

• Thrashing results in severe performance problems. Consider the following scenario, which is
based on the actual behaviour of early paging systems. The operating system monitors CPU
utilization. If CPU utilization is too low, we increase the degree of multiprogramming by
introducing a new process to the system. A global page replacement algorithm is used; it
replaces pages with no regard to the process to which they belong. Now suppose that a
process enters a new phase in its execution and needs more frames.

B.V.A.SWAMY 111 | P a g e
DEPT. OF COMPUTER SCIENCE

UNIT - III
File System Implementation
File System Implementation: Page No

3.11 Concept of a file and File System 113

Structure
3.12 Access Methods, 116

3.13 Directory Structure and Directory 117

Management
3.14 Allocation Methods, 120

3.15 Free Space Management, 122

3.16 Device Drivers.

B.V.A.SWAMY 112 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.11

Topic: 3.11 Concept of a file and File System Structure

File System

File concept and File System Structures

A file is a collection of related information that is stored on secondary storage. Information stored in
files must be persistent i.e. not affected by power failures & system reboots. Files may be of free
from such as text files or may be formatted rigidly. Files represent both programs as well as data. Part
of the OS dealing with the files is known as file system. The important file concepts include:

1. File attributes: A file has certain attributes which vary from one operating system to another.

• Name: Every file has a name by which it is referred.

• Identifier: It is unique number that identifies the file within the file system.

• Type: This information is needed for those systems that support different types of files.

• Location: It is a pointer to a device & to the location of the file on that device

• Size: It is the current size of a file in bytes, words or blocks.

• Protection: It is the access control information that determines who can read, write &
execute a file.

• Time, date & user identification: It gives information about time of creation or last
modification & last use.

2. File operations: The operating system can provide system calls to create, read, write, reposition,
delete and truncate files.

• Creating files: Two steps are necessary to create a file. First, space must be found for the
file in the file system. Secondly, an entry must be made in the directory for the new file.

Reading a file: Data & read from the file at the current position. The system must keep a read
pointer to know the location in the file from where the next read is to take place. Once the read has
been taken place, the read pointer is updated.

• Writing a file: Data are written to the file at the current position. The system must keep a
write pointer to know the location in the file where the next write is to take place. The write
pointer must be updated whenever a write occurs.

• Repositioning within a file (seek): The directory is searched for the appropriate entry &
the current file position is set to a given value. After repositioning data can be read from or
written into that position.
B.V.A.SWAMY 113 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.11

• Deleting a file: To delete a file, we search the directory for the required file. After deletion,
the space is releasedso that it can be reused by other files.

• Truncating a file: The user may erase the contents of a file but allows all attributes to
remain unchanged expect the file length which is rest to ‘O’ & the space is released.

3. File types: The file name is spilt into 2 parts, Name & extension. Usually these two parts are
separated by a period. The user & the OS can know the type of the file from the extension itself.
Listed below are some file types along with their extension:

File Type Extension

Executable File exe, bin, com

Object File obj, o (compiled)

Source Code file C, C++, Java, pas

Batch File bat, sh (commands to command the interpreter)

Text File txt, doc (textual data documents)

Archieve File arc, zip, tar (related files grouped together into file compressed for
storage)
Multimedia File mpeg (Binary file containing audio or A/V information)

File System structure:

Files can be structured in several ways. Three common possible are:

• Byte sequence:The figure shows an unstructured sequence of bytes. The OS doesn’t care
about the content of file. It only sees the bytes. This structure provides maximum flexibility.
Users can write anything into their files & name them according to their convenience. Both
UNIX & windows use this approach.

byte

· Record sequence: In this structure, a file is a sequence of fixed length records. Here the
read operation returns one records & the write operation overwrites or append or record.

B.V.A.SWAMY 114 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.11

Record

• Tree:In this organization, a file consists of a tree of records of varying lengths. Each record
consists of a key field. The tree is stored on the key field to allow first searching for a
particular key.

• Sequential access: It is the simplest access method. Information in the file is processed in
order i.e. one record after another. A process can read all the data in a file in order starting
from beginning but can’t skip & read arbitrarily from any location. Sequential files can be
rewound. It is convenient when storage medium was magnetic tape rather than disk.

Direct access: A file is made up of fixed length-logical records that allow programs to read
& write records rapidly in no particular O order. This method can be used when disk are
used for storing files. This method is used in many applications e.g. database systems. If an
airline customer wants to reserve a seat on a particular flight, the reservation program must
be able to access the record for that flight directly without reading the records before it. In a
direct access file, there is no restriction in the order of reading or writing. For example, we
can read block 14, then read block 50 & then write block 7 etc. Direct access files are very
useful for immediate access to large amount of information.

B.V.A.SWAMY 115 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.12

Topic:3.12 Access Methods

Protection
When information is kept in a computer system, a major concern is its protection from physical
damage (reliability) as well as improper access.

Types of access: In case of systems that don’t permit access to the files of other users. Protection
is not needed. So, one extreme is to provide protection by prohibiting access. The other extreme is
to provide free access with no protection. Both these approaches are too extreme for general use.

So, we need controlled access. It is provided by limiting the types of file access. Access is permitted
depending on several factors. One major factor is type of access requested. The different type of
operations that can be controlled are:

• Read
• Write
• Execute
• Append
• Delete
• List
Access lists and groups:
Various users may need different types of access to a file or directory. So, we can associate an
access lists with each file and directory to implement identity dependent access. When a user access
requests access to a particular file, the OS checks the access list associated with that file. If that user
is granted the requested access, then the access is allowed. Otherwise, a protection violation occurs
& the user is denied access to the file. But the main problem with access lists is their length. It is
very tedious to construct such a list. So, we use a condensed version of the access list by classifying
the users into 3 categories:

• Owners: The user who created the file.

• Group: A set of users who are sharing the files.
• Others: All other users in the system.

Here only 3 fields are required to define protection. Each field is a collection of bits each of which
either allows or prevents the access. E.g. The UNIX file system defines 3 fields of 3 bits each: rwx

• r( read access)
• w(write access)
• x(execute access)

Separate fields are kept for file owners, group & other users. So, a bit is needed to record protection
information for each file.

B.V.A.SWAMY 116 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.13

Topic:3.13 Directory Structure and Directory Management

Directory structure: The file system of computers can be extensive. Some systems store thousands
of file on disk. To manage all these data, we need to organize them. The organization is done in 2
steps. The file system is broken into partitions. Each partition contains information about file within
it.

Operation on a directory:

• Search for a file: We need to be able to search a directory for a particular file.

• Create a file: New files are created & added to the directory.

• Delete a file: When a file is no longer needed, we may remove it from the directory.

• List a directory: We should be able to list the files of the directory.

• Rename a file: The name of a file is changed when the contents of the file changes.

• Traverse the file system: It is useful to be able to access every directory & every file
within a directory.

Structure of a directory: The most common schemes for defining the structure of the directory
are:

1. Single level directory: It is the simplest directory structure. All files are present in the same
directory. So it is easy to manage & understand.

Limitation: A single level directory is difficult to manage when the no. of files increases or
when there is more than one user. Since all files are in same directory, they must have unique
names. So, there is confusion of file names between different users.

2. Two level directories: The solution to the name collision problem in single level directory is to
create a separate directory for each user. In a two level directory structure, each user has its own
user file directory. When a user logs in, then master file directory is searched. It is indexed by
user name & each entry points to the UFD of that user.

Limitation: It solves name collision problem. But it isolates one user from another. It is an
advantage when users are completely independent. But it is a disadvantage when the users need
to access each other’s files & co-operate among themselves on a particular task.

B.V.A.SWAMY 117 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.13

Tree structured directories: It is the most common directory structure. A two level directory
is a two level tree. So, the generalization is to extend the directory structure to a tree of arbitrary
height. It allows users to create their own subdirectories & organize their files. Every file in the
system has a unique path name. It is the path from the root through all the sub-directories to a
specified file. A directory is simply another file but it is treated in a special way. One bit in each
directory entry defines the entry as a file (O) or as sub- directories. Each user has a current
directory. It contains most of the files that are of current interest to the user. Path names can be
of two types: An absolute path name begins from the root directory & follows the path down to
the specified files. A relative path name defines the path from the current directory. E.g. If the
current directory is root/spell/mail, then the relative path name is prt/first & the absolute path
name is root/ spell/ mail/ prt/ first. Here users can access the files of other users also by
specifying their path names.

4. A cyclic graph directory:It is a generalization of tree structured directory scheme. An a cyclic

graph allows directories to have shared sub-directories & files. A shared directory or file is not
the same as two copies of a file. Here a programmer can view the copy but the changes made in
the file by one programmer are not reflected in the other’s copy. But in a shared file, there is
only one actual file. So many changes made by a person would be immediately visible to others.
This scheme is useful in a situation where several people are working as a team. So, here all the
files that are to be shared are put together in one directory. Shared files and sub-directories can
be implemented in several ways. A common way used in UNIX systems is to create a new
directory entry called link. It is a pointer to another file or sub-directory. The other approach is
to duplicate all information in both sharing directories. A cyclic graph structure is more flexible
then a tree structure but it is also more complex.

Limitation: Now a file may have multiple absolute path names. So, distinct file names may refer
to the same file. Another problem occurs during deletion of a shared file. When a file is removed
by any one user. It may leave dangling pointer to the non existing file. One serious problem in a
cyclic graph structure is ensuring that there are no cycles. To avoid these problems, some
systems do not allow shared directories or files. E.g. MS-DOS uses a tree structure rather than a
cyclic to avoid the problems associated with deletion. One approach for deletion is to preserve
the file until all references to it are deleted. To implement this approach, we must have some
mechanism for determining the last reference to the file. For this we have to keep a list of
reference to a file. But due to the large size of the no. of references. When the count is zero, the
file can be deleted.

B.V.A.SWAMY 118 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.13

5. General graph directory: When links are added to an existing tree structured
directory, the tree structure is destroyed, resulting in a simple graph structure. Linking is a
technique that allows a file to appear in more than one directory. The advantage is the
simplicity of algorithm to transverse the graph & determines when there are no more
references to a file. But a similar problem exists when we are trying to determine when a file
can be deleted. Here also a value zero in the reference count means that there are no more
references to the file or directory & the file can be deleted. But when cycle exists, the
reference count may be non-zero even when there are no references to the directory or file.
This occurs due to the possibility of self referencing (cycle) in the structure. So, here we have
to use garbage collection scheme to determine when the last references to a file has been
deleted & the space can be reallocated. It involves two steps:

• Transverse the entire file system & mark everything that can be accessed.

• Everything that isn’t marked is added to the list of free space.

6. But this process is extremely time consuming. It is only necessary due to presence of cycles in the
graph. So, a cyclic graph structure is easier to work than this.

B.V.A.SWAMY 119 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.14

Topic:3.14 Allocation Methods

Allocation methods
There are 3 methods of allocating disk space widely used.

1. Contiguous allocation:

a. It requires each file to occupy a set of contiguous blocks on the disk.

b. Number of disk seeks required for accessing contiguously allocated file is minimum.

c. The IBM VM/CMS OS uses contiguous allocation. Contiguous allocation of a file is defined
by the disk address and length (in terms of block units).

d. If the file is ‘n’ blocks long and starts all location ‘b’, then it occupies blocks b, b+1, b+2,----

-------- - -b+ n-1.

e. The directory for each file indicates the address of the starting block and the length of the
area allocated for each file.

f. Contiguous allocation supports both sequential and direct access. For sequential access, the
file system remembers the disk address of the last block referenced and reads the next block
when necessary.

g. For direct access to block i of a file that starts at block b we can immediately access block b
+ i.

Problems: One difficulty with contiguous allocation is finding space for a new file. It also
suffers from the problem of external fragmentation. As files are deleted and allocated, the
free disk space is broken into small pieces. A major problem in contiguous allocation is how
much space is needed for a file. When a file is created, the total amount of space it will need
must be found and allocated. Even if the total amount of space needed for a file is known in
advances, pre-allocation is inefficient. Because a file that grows very slowly must be allocated
enough space for its final size even though most of that space is left unused for a long period
time. Therefore, the file has a large amount of internal fragmentation.

2. Linked Allocation:

a. Linked allocation solves all problems of contiguous allocation.

b. In linked allocation, each file is linked list of disk blocks, which are scattered throughout the
disk.
B.V.A.SWAMY 120 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.14

c. The directory contains a pointer to the first and last blocks of the file.

d. Each block contains a pointer to the next block.

e. These pointers are not accessible to the user. To create a new file, we simply create a new
entry in the directory.

f. For writing to the file, a free block is found by the free space management system and this
new block is written to & linked to the end of the file.

g. To read a file, we read blocks by following the pointers from block to block.

h. There is no external fragmentation with linked allocation & any free block can be used to
satisfy a request.

i. Also there is no need to declare the size of a file when that file is created. A file can continue
to grow as long as there are free blocks.

j. Limitations: It can be used effectively only for sequential access files. To find the ‘ i ' th
block of the file, we must start at the beginning of that file and follow the pointers until we
get the ith block. So it is inefficient to support direct access files. Due to the presence of
pointers each file requires slightly more space than before. Another problem is reliability.
Since the files are linked together by pointers scattered throughout the disk. What would
happen if a pointer were lost or damaged.

3. Indexed Allocation:

a. Indexed allocation solves the problem of linked allocation by bringing all the
pointers together to one location known as the index block.

b. Each file has its own index block which is an array of disk block addresses. The ith
entry in the index block points to the ith block of the file.
b. The directory contains the address of the index block. The read the ith block, we use the
pointer in the ith index block entry and read the desired block.

c. To write into the ith block, a free block is obtained from the free space manager and its
address is put in the ith index block entry.

d. Indexed allocation supports direct access without suffering external fragmentation.

e. Limitations: The pointer overhead of index block is greater than the pointer overhead of
linked allocation. So here more space is wasted than linked allocation. In indexed allocation,
an entire index block must be allocated, even if most of the pointers are nil.

B.V.A.SWAMY 121 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.15

Topic:3.15 Free Space Management

Free Space Management

Since there is only a limited amount of disk space, it is necessary to reuse the space from the deleted
files. To keep track of free disk space, the system maintains a free space list. It records all the disk
blocks that are free i.e. not allocated to some file or dictionary. To create a file, we search the free
space list for the required amount of space and allocate it to the new file. This space is then removed
from the free space list. When a file is deleted, its disk space is added to the free space list.

Implementation:

There are 4 ways to implement the free space list such as:

• Bit Vector: The free space list is implemented as a bit map or bit vector. Each block is
represented as 1 bit. If the block is free, the bit is 1 and if it is allocated then the bit is 0. For
example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 & 27 are free
and rest of the blocks are allocated. The free space bit map would be
0011110011111100011000000111……………………..

The main advantage of this approach is that it is simple and efficient to find the first free block
or n consecutive free blocks on the disk. But bit vectors are inefficient unless the entire vector is
kept in main memory. It is possible for smaller disks but not for larger ones.

Linked List: Another approach is to link together all the free disk blocks and keep a pointer to the
first free block. The first free block contains a pointer to the next free block and so on. For example,
we keep a pointer to block 2 as the free block. Block 2 contains a pointer to block which points to
block 4 which then points to block 5 and so on. But this scheme is not efficient. To traverse the list,
we must read each block which require a lot of I/O time

• Grouping: In this approach, we store the address of n free blocks in the first free block. The
first n-1 of these blocks is actually free. The last block contains the address of another n free
blocks and so on. Here the addresses of a large number of free blocks can be found out quickly.

Counting: Rather than keeping a list of n free disk block addresses, we can keep the address of the
first free block and the number of free contiguous blocks. So here each entry in the free space list
consists of a disk address and a count.

B.V.A.SWAMY 122 | P a g e
DEPT. OF COMPUTER SCIENCE

UNIT -III
Mass Storage Structure
Topics Page NO

3.16 MASS STORAGE 124

STRUCTURES
3.17 DISK STRUCTURE 125

3.18 DISK SCHEDULING 126

3.19 DISK ATTACHMENT 129

3.20 DISK MANAGEMENT 129

3.21 SWAP SPACE MANAGEMENT 130

B.V.A.SWAMY 123 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.16

Topic: 3.16 MASS STORAGE STRUCTURES

x Disks provide a bilk of secondary storage. Disks come in various sizes, speed and
information can be stored optically or magnetically.

x Magnetic tapes were used early as secondary storage but the access time is less than disk.

x Modern disks are organized as single one-dimensional array of logical blocks. x The
actual details of disk i/o open depends on the computer system, OS, nature of i/o channels
and disk controller hardware.

x The basic unit of information storage is a sector. The sectors are stored on flat,
circular, media disk. This disk media spins against one or more read-write heads. The head
can move from
the inner portion of the disk to the outer portion.
x When the disk drive is operating the disks is rotating at a constant speed. x To read or
write the head must be positioned at the desired track and at the beginning if the desired
sector on that track. x Track selection involves moving the head in a movable head system
or electronically selecting one head on a fixed head system. x These characteristics are
common to floppy disks, hard disks, CD-ROM and DVD.

B.V.A.SWAMY 124 | P a g e
DEPT. OF COMPUTER SCIENCE
Topic: 3.17

Topic: 3.17 DISK STRUCTURE

1. Seek Time:-Seek time is the time required to move the disk arm to the required track.

Seektimecanbegivenby Ts=m*n+s. Where Ts = seek time

n = number of track traversed. m = constant that depends on the disk drive s = startup
time.

2. Rotational Latency :- Rotational latency is the additional addition time for

waiting for the disk to rotate to the desired sector to the disk head.

3. Rotational Delay :- Disks other than the floppy disk rotate at 3600 rpm which is one
revolution per 16.7ms.

4. Disk Bandwidth:-Disk bandwidth is the total number of bytes transferred divided by

total time between the first request for service and the completion of last transfer.

Transfer time = T =b / rN Where b = number of bytes transferred.

T = transfer time. r = rotational speed in RpS. N = number of bytes on the track.

Average access time = Ta = Ts + 1/ 2r + b/ rN Where Ts = seek time.

5.Total capacity of the disk:-It is calculated by using following formula. Number of

cylinders * number of heads * number of sector/track * number of bytes/sector.
DISK ATTACHMENT

The amount of head movement needed to satisfy a series of i/o request can affect
the performance. If the desired drive and the controller are available the request can be serviced
immediately. If the device or controller is busy any new requests for service will be placed on the
queue of pending requests for that drive when one request is complete the OS chooses which
pending request to service next.

B.V.A.SWAMY 125 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.18

Topic:3.18 DISK SCHEDULING

Different types of scheduling algorithms are as follows:

1. FCFS scheduling algorithm:This is the simplest form of disk scheduling
algorithm. This services the request in the order they are received. This
algorithm is fair but do not provide fastest service. It takes no special time

to minimize the overall seek time.

2. Eg:-consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,
124, 65, 67
If the disk head is initially at 53, it will first move from 53 to 98 then to 183 and then to 37, 122, 14,
124, 65, 67 for a total head movement of 640 cylinders. The wild swing from 122 to 14 and then
back to 124 illustrates the problem with this schedule. If the requests for cylinders 37 and 14 could
be serviced together before or after 122 and 124 the total head movement could be decreased
substantially and performance could be improved.

3. SSTF ( Shortest seek time first) algorithm:This selects the request with minimum seek
time from the current head position. Since seek time increases with the number of
cylinders traversed by head, SSTF chooses the pending request closest to the current
head position. Eg:-
:-consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14, 124,
65, 67

B.V.A.SWAMY 126 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.18

If the disk head is initially at 53, the closest is at cylinder 65, then 67, then 37 is closer
then 98 to 67. So it services 37, continuing we service 14, 98, 122, 124 and finally 183.
The total head movement is only 236 cylinders. SSTF is essentially a form of SJF and it
may cause starvation of some requests. SSTF is asubstantial improvement over FCFS, it
is not optimal.
1. SCAN algorithm:In this the disk arm starts at one end of the disk and moves towards the
other end, servicing the request as it reaches each cylinder until it gets to the other end of
the disk. At the other end, the direction of the head movement is reversed and servicing
continues. Eg:-:-consider a disk queue with request for i/o to blocks on cylinders. 98, 183,

37, 122, 14, 124, 65, 67

If the disk head is initially at 53 and if the head is moving towards 0, it services 37 and then 14. At
cylinder 0 the arm will reverse and will move towards the other end of the disk servicing 65, 67, 98,
122, 124 and 183. If a request arrives just in from of head, it will be serviced immediately and the
request just behind the head will have to wait until the arms reach other end and reverses direction.
The SCAN is also called as elevator algorithm.

2. C-SCAN (Circular scan) algorithm:

C-SCAN is a variant of SCAN designed to provide a more uniform wait time. Like SCAN, C-
SCAN moves the head from end of the disk to the other servicing the request along the way. When
the head reaches the other end, it immediately returns to the beginning of the disk, without
servicing any request on the return. The C-SCAN treats the cylinders as circular list that wraps

B.V.A.SWAMY 127 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.18

around from the inal cylinder to the first one.

Eg:-

3. Look Scheduling algorithm:

Both SCAN and C-SCAN move the disk arm across the full width of the disk. In practice neither of
the algorithms is implemented in this way. The arm goes only as far as the final request in each

direction. Then it reverses, without going all the way to the end of the disk. These versions of
SCANand CSCAN are called Look and C-Look scheduling because they look for a request before
continuing to move in a given direction. Eg:

Selection of Disk Scheduling Algorithm:

1. SSTF is common and it increases performance over FCFS.

2. SCAN and C-SCAN algorithm is better for a heavy load on disk.
3. SCAN and C-SCAN have less starvation problem.
4. SSTF or Look is a reasonable choice for a default algorithm.

B.V.A.SWAMY 128 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.19

Topic:3.19 Disk Attachment

• Host-attached storage accessed through I/O ports talking to I/O
busses
• SCSI itself is a bus, up to 16 devices on one cable, SCSI initiator
requests operation and requests operation and SCSI targets SCSI
targets perform tasks perform tasks
• Each target can have up to 8 logical units (disks attached to device
controller)  FC is high-speed serial architecture
• Can be switched fabric with 24-bit address space – the basis of storage
area networks (SANs) in which many hosts attach to many storage
units
• I/O directed to bus ID device ID logical unit (LUN) Topic: 3.20

Topic: 3.20 DISK MANAGEMENT

• Low-level formatting, or physical formatting — Dividing a disk into sectors that the
disk controller can read and write.
•  To use a disk to hold files, the operating system still needs to record its
own data structures on the disk.
• Partition the disk into one or more groups of cylinders.
• Logical formatting or “making a file system”.
•  Boot block initializes system.
• The bootstrap is stored in ROM.
• Bootstrap loader program.
Methods such as sector sparing used to handle bad blocks

B.V.A.SWAMY 129 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 3.21

Topic: 3.21 SWAP SPACE MANAGEMENT

• Swap-space — Virtual memory uses disk space as an extension of main

memory.
• Swap-space can be carved out of the normal file system,or, more
commonly, it can be in a separate disk partition.
• 4.3BSD allocates swap space when process starts; holds text segment (the
program) and data segment.
• Kernel uses swap maps to track swap-space use.Solaris 2 allocates swap
space only when a page is forced out of physical memory, not when the virtual
memory page is first created.

RAID Structure

 Disk striping uses a group of disks as one storage unit schemes improve performance and
improve the reliability of the storage system by storing redundant data
• Mirroring or shadowing (RAID 1) keeps duplicate of each disk
• Striped mirrors (RAID 1+0) or mirrored stripes (RAID 0+1) provides high performance
and high reliability
• Block interleaved parity (RAID 4, 5, 6) uses much less redundancy
RAID within a storage array can still fail if the array fails, so automatic replication of the data
between arrays is common.Frequently, a small number of hot-spare disks are left unallocated,
automatically replacing a failed disk and having data rebuilt onto them.
• RAID – multiple disk drives provides reliability via redundancy. It is arranged into six
different levels.Several improvements in disk-use techniques involve the use of multiple
disks working cooperatively.Disk striping uses a group of disks as one storage unit.
•  RAID schemes improve performance and improve the reliability of the
storage system by storing redundant data.
• Mirroring or shadowing keeps duplicate of each disk.
• Block interleaved parity uses much less redundancy.
• RAID alone does not prevent or detect data corruption or other errors, just disk
failures .Solaris ZFS adds checksums of all data and metadata Checksums kept with pointer
to object, to detect if object is the right one and whether it changed can detect and correct
data and metadata corruptionZFS also removes volumes, partititions .Disks allocated in
pools
Filesystems with a pool share that pool, use and release space like “malloc” and “free” memory allocate
/ release calls.
B.V.A.SWAMY 130 | P a g e
DEPT. OF COMPUTER SCIENCE

UNIT- 4
TOPICS
PROTECTION Page No

4.1 Goal and Principle of 132

Protection
4.2 Access matrix 133
implementation
4.3 Access control 135

4.4 Revocation of access rights 137

B.V.A.SWAMY 131 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 4.1

Topic: 4.1 PROTECTION: GOALS OF PROTECTION

• Discuss the goals and principles of protection in a modern computer system

• Explain how protection domains combined with an access matrix are used to
specify the resources a process may access.Examine capability and language-
based protection systems
• Operating system consists of a collection of objects, hardware or software
Each object has a unique name and can be accessed through a well-defined set of
operations
• Protection problem -ensure that each object is accessed correctly and only by
those processes that are allowed to do so

PRINCIPLES OF PROTECTION

• Guiding principle principle of least privilege

– Programs, users and systems should be given just enough privileges
to perform their tasks Disk Attachment : Stable-Storage
Implementation

• Write-ahead log scheme requires stable storage

• • To implement stable storage:
• Replicate information on more than one nonvolatile storage media with
independent failure modes
• Update information in a controlled manner to ensure that we can recover
the stable data after any failure during data transfer or recovery

DOMAIN OF PROTECTION

Domain Structure

Access-right=<object-name,rights-set> where rights-set is a subset of all valid

operations that can be performed on the object.

Domain Implementation (UNIX)

• System consists of 2 domains:

• User
• Supervisor
• UNIX
• Domain = user-id
• Domain switch accomplished via file system
• Each file has associated with it a domain bit (setuid bit)

B.V.A.SWAMY 132 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 4.1

• When file is executed and setuid = on, then user-id is set to owner of the file
being executed. When execution completes user-id is reset.

Topic: 4.2 ACCESS MATRIX

• View protection as a matrix (access matrix)

• Rows represent domains
• Columns represent objects
• Access(i, j) is the set of operations that a process executing in Domaini can
invoke on Objectj

Use of Access Matrix

• If a process in Domain Di tries to do “op” on object Oj, then “op” must be in the
access matrix
• • Can be expanded to dynamic protection
• – Operations to add, delete access rights
• – Special access rights: • owner of Oi
• copy op from Oi to Oj
• control – Di can modify Dj access rights
• transfer – switch from domain Di to Dj
• • Access matrix design separates mechanism from policy
• – Mechanism
• Operating system provides access-matrix + rules
• If ensures that the matrix is only manipulated by authorized agents and that
rules are strictly enforced
• – Policy
• User dictates policy
• Who can access what object and in what mod

B.V.A.SWAMY 133 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 4.2

IMPLEMENTATION OF ACCESS MATRIX

• Each column = Access-control list for one object Defines who can

perform what operation. Domain 1 = Read, Write Domain 2 Read

Domain 3 Read

• Each Row = Capability List (like a key)

Fore each domain, what operations allowed on what objects. Object 1 – Read Object 4
– Read, Write, Execute
Object 5 – Read, Write, Delete, Copy

ACCESS MATRIX OF FIGURE A WITH DOMAINS

AS OBJECTS

ACCESS MATRIX WITH COPY RIGHTS

B.V.A.SWAMY 134 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 4.3

MODIFIED ACCESS MATRIX OF FIGURE B

Topic: 4.3 ACCESS CONTROL

Protection can be applied to non-file resources. Solaris 10 provides role-based

access control (RBAC) to implement least privilege.Privilege is right to execute system
call or use an option within a system call Can be assigned to processes. Users assigned
roles granting access to privileges and Programs. Revocation of Access Rights

• Access List – Delete access rights from access list

• Simple
• Immediate
• • Capability List – Scheme required to locate capability in the system before
capability can be revoked
• Reacquisition
• Back-pointers
• Indirection
• Keys

• Low cost is the defining characteristic of tertiary storage.

• Generally, tertiary storage is built using removable media.
• Common examples of removable media are floppy disks and CD-ROMs; other
types are available.

B.V.A.SWAMY 135 | P a g e
DEPT. OF COMPUTER SCIENCE

Removable Disks
• Floppy disk — thin flexible disk coated with magnetic material, enclosed in a protective
plastic case
• Most floppies hold about 1 MB; similar technology is used for removable disks
that hold more than 1 GB
• Removable magnetic disks can be nearly as fast as hard disks, but they are at
a greater risk of damage from exposure
• • A magneto-optic disk records data on a rigid platter coated with magnetic
material
• Laser heat is used to amplify a large, weak magnetic field to record a bit
• Laser light is also used to read data (Kerr effect)
• The magneto-optic head flies much farther from the disk surface than a
magnetic disk head, and the magnetic material is covered with a protective layer
of plastic or glass; resistant to head crashes
• Optical disks do not use magnetism; they employ special materials that are
altered by laser light
The data on read-write disks can be modified over and over
• WORM (“Write Once, Read Many Times”) disks can be written only once
• Thin aluminum film sandwiched between two glass or plastic platters
• To write a bit, the drive uses a laser light to burn a small hole through the
aluminum; information can be destroyed by not altered
• Very durable and reliable..
• Read-only disks, such ad CD-ROM and DVD, com from the factory with the data
pre-recorded Tapes
• Compared to a disk, a tape is less expensive and holds more data, but random
access is much slower.
• Tape is an economical medium for purposes that do not require fast
random access, e.g., backup copies of disk data, holding huge volumes of data
• Large tape installations typically use robotic tape changers that move tapes between
tape drives and storage slots in a tape library
• stacker – library that holds a few tapes
• silo – library that holds thousands of tapes
A disk-resident file can be archived to tape for low cost storage; the computer can stage
it back into disk storage for active use.

B.V.A.SWAMY 136 | P a g e
DEPT. OF COMPUTER SCIENCE

Topic: 4.4

Application Interface
• Most OSs handle removable disks almost exactly like fixed disks — a new
cartridge is formatted and an empty file system is generated on the disk.
• Tapes are presented as a raw storage medium, i.e., and application does not
not open a file on the tape, it opens the whole tape drive as a raw device.
• Usually the tape drive is reserved for the exclusive use of that application.
• Since the OS does not provide file system services, the application must
decide how to use the array of blocks.
• Since every application makes up its own rules for how to organize a
tape, a tape full of data can generally only be used by the program that created it.

Topic:4.4 Revocation of Access

Rights Revocation of Access Rights
„ In dynamic protection system, we may need to revoke access rights to objects shared by
different users.
„ Various questions about revocation may arise:
Immediate versus Delayed: Does revocation occur immediately, or is it delayed?
Selective versus General: When an access right to an object is revoked, does it affect all
users who have an access to that object, or can we specify a select group of users whose
access rights should be revoked?
Partial versus Total: Can a subset of rights associated with an object be revoked, or must
we revoke all access rights for this object?
Temporary versus Permanent: Can access be revoked permanently (that is, the revoked
access right will never again be available), or can access be revoked and later be obtained
again?.

B.V.A.SWAMY 137 | P a g e
DEPT. OF COMPUTER SCIENCE

7.8 CAPABILITY-BASED SYSTEM

• Hydra
• Fixed set of access rights known to and interpreted by the system
• Interpretation of user-defined rights performed solely by user's program;
system provides access protection for use of these rights
• • Cambridge CAP System
• Data capability -provides standard read, write, execute of individual storage
segments associated with object
• Software capability -interpretation left to the subsystem, through its protected
procedures
• Specification of protection in a programming language allows the high-level
description of policies for the allocation and use of resources
• Language implementation can provide software for protection enforcement
when automatic hardware- supported checking is unavailable
• Protection in Java 2
• Protection is handled by the Java Virtual Machine (JVM)
• A class is assigned a protection domain when it is loaded by the JVM
• The protection domain indicates what operations the class can (and cannot)
perform
• If a library method is invoked that performs a privileged operation, the stack is
inspected to ensure the operation can be performed by the library
• Interpret protection specifications to generate calls on whatever protection
system is provided by the hardware and the operating system.

B.V.A.SWAMY 138 | P a g e
DEPT. OF COMPUTER SCIENCE

UNIT – 4
TOPICS
Case Study Page No

Linux

Windows Operating System

B.V.A.SWAMY 139 | P a g e