Unit-1 Introduction to Operating System

Introduction
An Operating System (OS) is an interface between computer user and computer hardware. An
operating system is 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.

The Operating System is a program with the following features −

• An operating system is a program that acts as an interface between the software and the
computer hardware.
• It is an integrated set of specialized programs used to manage overall resources and operations
of the computer.
• It is specialized software that controls and monitors the execution of all other programs that
reside in the computer, including application programs and other system software.

Fig: Layers of operating system

Objectives of Operating System

There are two primary objectives of operating system:
1. Operating system as an extended machine:
The architecture (instruction set, memory organization, I/O, and bus structure) of most
computers at the machine language level is primitive and awkward to program, especially for
input/output. The program that hides the truth about the hardware from the programmer and
presents a nice, simple view of named files that can be read and written is operating system. Just
as the operating system shields the programmer from the disk hardware and presents a simple
fileoriented interface, it also conceals a lot of unpleasant business concerning interrupts, timers,
memory management, and other low-level features. In each case, the abstraction offered by the
operating system is simpler and easier to use than that offered by the underlying hardware.
In this view, the function of the operating system is to present the user with the equivalent of
an extended machine or virtual machine that is easier to program than the underlying hardware.

1
 2. The Operating System as a Resource Manager
The main important objective of an operating system is to manage the various resources of the
computer system. This involves performing such tasks as keeping track of who is using which
resources, granting resource requests, accounting for resource usage, and mediating conflicting
requests from different programs and users.
Executing a job on a computer system often requires several of its resource such as CPU time,
memory space, file storage space, I/O devices and so on. The operating system acts as the manager
of the various resources of a computer system and allocates them to specific programs and users
to execute their jobs successfully. When a computer system is used to simultaneously handle
several applications, there may be many, possibly conflicting, requests for resources. In such a
situation, the operating system must decide which requests are allocated resources to operate the
computer system efficiently and fairly (providing due attention to all users). The efficient and fair
sharing of resources among users and/or programs is a key goal of most operating system.

Fig: Operating System as a resource manager

History of Operating System

Operating systems have been evolving through the years. Since operating systems have
historically been closely tied to the architecture of the computers on which they run, we will look
at successive generations of computers to see what their operating systems were like. This mapping
of operating system generations to computer generations is crude, but it does provide some
structure where there would otherwise be none.
The first true digital computer was designed by the English mathematician Charles Babbage
(1792-1871). Although Babbage spent most of his life and fortune trying to build his “analytical
engine.” he never got it working properly because it was purely mechanical, and the technology of
his day could not produce the required wheels, gears, and cogs to the high precision that he needed.
Needless to say, the analytical engine did not have an operating system.
As an interesting historical aside, Babbage realized that he would need software for his analytical
engine, so he hired a young woman named Ada Lovelace, who was the daughter of the famed
British poet Lord Byron, as the world’s first programmer. The programming language Ada® is
named after her.

2
The First Generation (1945-55) Vacuum Tubes and Plug boards
After Babbage’s unsuccessful efforts, little progress was made in constructing digital computers
until World War II. Around the mid-1940s, Howard Aiken at Harvard, John von Neumann at the
Institute for Advanced Study in Princeton, J. Presper Eckert and William Mauchley at the
University of Pennsylvania, and Konrad Zuse in Germany, among others, all succeeded in building
calculating engines. The first ones used mechanical relays but were very slow, with cycle times
measured in seconds. Relays were later replaced by vacuum tubes. These machines were
enormous, filling up entire rooms with tens of thousands of vacuum tubes, but they were still
millions of times slower than even the cheapest personal computers available today.
In these early days, a single group of people designed, built, programmed, operated, and maintained
each machine. All programming was done in absolute machine language, often by wiring up plug
boards to control the machine’s basic functions. Programming languages were unknown (even
assembly language was unknown). Operating systems were unheard of. The usual made of
operation was for the programmer to sign up for a block of time on the signup sheet on the wall,
then come down to the machine room, insert his or her plug board into the computer, and spend
the next few hours hoping that none of the 20,000 or so vacuum tubes would burn out during the
run. Virtually all the problems were straightforward numerical calculations, such as grinding out
tables of sines, cosines, and logarithms.
By the early 1950s, the routine had improved somewhat with the introduction of punched cards. It
was now possible to write programs on cards and read them in instead of using plug boards;
otherwise, the procedure was the same.

The Second Generation (1955-65) Transistors and Batch Systems

The introduction of the transistor in the mid-1950s changed the picture radically. Computers
became reliable enough that they could be manufactured and sold to paying customers with the
expectation that they would continue to function long enough to get some useful work done. For
the first time, there was a clear separation between designers, builders, operators, programmers,
and maintenance personnel.

These machines, now called mainframes, were locked away in specially air conditioned computer
rooms, with staffs of professional operators to run them. Only big corporations or major
government agencies or universities could afford the multimillion dollar price tag. To run a job
(i.e., a program or set of programs), a programmer would first write the program on paper (in
FORTRAN or assembler), then punch it on cards. He would then bring the card deck down to the
input room and hand it to one of the operators and go drink coffee until the output was ready.
When the computer finished whatever job it was currently running, an operator would go over to
the printer and tear off the output and carry it over to the output room, so that the programmer
could collect it later. Then he would take one of the card decks that had been brought from the
input room and read it in. If the FORTRAN compiler was needed, the operator would have to get
it from a file cabinet and read it in. Much computer time was wasted while operators were walking
around the machine room.

3
 The solution generally adopted was the batch system. The idea behind it was to collect a tray
full of jobs in the input room and then read them onto a magnetic tape using a small (relatively)
inexpensive computer, such as the IBM 1401, which was very good at reading cards, copying
tapes, and printing output, but not at all good at numerical calculations. Other, much more
expensive machines, such as the IBM 7094, were used for the real computing.

Fig: An Early Batch System

(a) Programmers bring cards to 1401
(b) 1401 reads batch of jobs onto tape
(c) Operator carries input tape to 7094
(d) 7094 does computing
(e) Operator carries output tape to 1401
(f) 1401 prints output
The Third Generation (1965-1980) ICs and Multiprogramming
By the early 1960s, most computer manufacturers had two distinct, and totally incompatible,
product lines. On the one hand there were the word-oriented, large-scale scientific computers, such
as the 7094, which were used for numerical calculations in science and engineering. On the other
hand, there were the character-oriented, commercial computers, such as the 1401, which were
widely used for tape sorting and printing by banks and insurance companies.
IBM attempted to solve both of these problems at a single stroke by introducing the System/360.
The 360 was a series of software-compatible machines ranging from 1401-sized to much more
powerful than the 7094. The machines differed only in price and performance (maximum
memory, processor speed, number of I/O devices permitted, and so forth). Since all the machines
had the same architecture and instruction set, programs written for one machine could run on all
the others, at least in theory. Furthermore, the 360 was designed to handle both scientific (i.e.,
numerical) and commercial computing. Thus a single family of machines could satisfy the needs
of all customers. In subsequent years, IBM has come out with compatible successors to the 360
line, using more modern technology, known as the 370, 4300, 3080, and 3090 series.

The greatest strength of the “one family” idea was simultaneously its greatest weakness. The
intention was that all software, including the operating system, OS/360 had to work on all
models. It had to run on small systems, which often just replaced 1401s for copying cards to
tape, and on very large systems, which often replaced 7094s for doing weather forecasting and
other heavy computing. It had to be good on systems with few peripherals and on systems with
many peripherals. It had to work in commercial environments and in scientific environments.
Above all, it had to be efficient for all of these different uses.
Despite its enormous size and problems, OS/360 and the similar third-generation operating systems
produced by other computer manufacturers actually satisfied most of their customers reasonably
well. They also popularized several key techniques absent in second-
4
generation operating systems. Probably the most important of these was multiprogramming. On
the 7094, when the current job paused to wait for a tape or other I/O operation to complete, the
CPU simply sat idle until the I/O finished. With heavily CPU-bound scientific calculations, I/O is
infrequent, so this wasted time is not significant. With commercial data processing, the I/O wait
time can often be 80 or 90 percent of the total time, so something had to be done to avoid having
the (expensive) CPU be idle so much.

Fig: A multiprogramming system with three jobs in memory.

The Fourth Generation (1980-Present) Personal Computers
With the development of LSI (Large Scale Integration) circuits, chips containing thousands of
transistors on a square centimeter of silicon, the age of the personal computer dawned. In terms of
architecture, personal computers (initially called microcomputers) were not all that different from
minicomputers of the PDP-11 class, but in terms of price they certainly were different. Where the
minicomputer made it possible for a department in a company or university to have its own
computer, the microprocessor chip made it possible for a single individual to have his or her own
personal computer.
In 1974, when Intel came out with the 8080, the first general-purpose 8-bit CPU, it wanted an
operating system for the 8080, in part to be able to test it. Intel asked one of its consultants, Gary
Kildall, to write one. Kildall and a friend first built a controller for the newly-released Shugart
Associates 8-inch floppy disk and hooked the floppy disk up to the 8080, thus producing the first
microcomputer with a disk. Kildall then wrote a disk-based operating system called CP/M
(Control Program for Microcomputers) for it.
In the early 1980s, IBM designed the IBM PC and looked around for software to run on it. People
from IBM contacted Bill Gates to license his BASIC interpreter. They also asked him if he knew
of an operating system to run on the PC, Gates suggested that IBM contact Digital Research, then
the world’s dominant operating systems company. Making what was surely the worst business
decision in recorded history, Kildall refused to meet with IBM, sending a subordinate instead. To
make matters worse, his lawyer even refused to sign IBM’s nondisclosure agreement covering the
not-yetannounced PC. Consequently, IBM went back to Gates asking if he could provide them
with an operating system.
When IBM came back, Gates realized that a local computer manufacturer, Seattle
Computer Products, had a suitable operating system. DOS (Disk Operating System). He
approached them and asked to buy it (allegedly for $50,000). which they readily accepted. Gates
then offered IBM a DOS/BASIC package which IBM accepted. IBM wanted certain modifications,
so Gates hired the person who wrote DOS, Tim Paterson, as an employee of Gates’ fledgling
company, Microsoft, to make them. The revised system was renamed MS-DOS (MicroSoft Disk
Operating System) and quickly came to dominate the IBM PC market.

5
 CP/M, MS-DOS, and other operating systems for early microcomputers were all based on users
typing in commands from the keyboard. That eventually changed due to research done by Doug
Engelbart at Stanford Research Institute in the 1960s. Engelbart invented the GUI (Graphical
User Interface), pronounced “gooey,” complete with windows, icons, menus, and mouse. These
ideas were adopted by researchers at Xerox PARC and incorporated into machines they built.
One day, Steve Jobs, who co-invented the Apple computer in his garage, visited PARC, saw a
GUI, and instantly realized its potential value; something Xerox management famously did not
(Smith and Alexander, 1988). Jobs then embarked on building an Apple with a GUI. This project
led to the Lisa, which was too expensive and failed commercially. Jobs’ second attempt, the Apple
Macintosh, was a huge success, not only because it was much cheaper than the Lisa, but also
because it was user friendly, meaning that it was intended for users who not only knew nothing
about computers but furthermore had absolutely no intention whatsoever of learning.
Another Microsoft operating system is Windows NT (NT stands for New Technology), which is
compatible with Windows 95 at a certain level, but a complete rewrite from scratch internally. It
is a full 32-bit system.
An interesting development that began taking place during the mid-1980s is the growth of
networks of personal computers running network operating systems and distributed operating
systems. In a network operating system, the users are aware of the existence of multiple computers
and can log in to remote machines and copy files from one machine to another. Each machine runs
its own local operating system and has its own local user (or users).
The Fifth Generation (1990–Present): Mobile Computers
Ever since detective Dick Tracy started talking to his ‘‘two-way radio wrist watch’’ in the 1940s
comic strip, people have craved a communication device they could carry around wherever they
went. The first real mobile phone appeared in 1946 and weighed some 40 kilos. You could take it
wherever you went as long as you had a car in which to carry it.
The first true handheld phone appeared in the 1970s and, at roughly one kilogram, was positively
featherweight. It was affectionately known as ‘‘the brick.’’ Pretty soon everybody wanted one.
Today, mobile phone penetration is close to 90% of the global population. We can make calls not
just with our portable phones and wrist watches, but soon with eyeglasses and other wearable
items. Moreover, the phone part is no longer that interesting. We receive email, surf the Web, text
our friends, play games, navigate around heavy traffic—and do not even think twice about it.
While the idea of combining telephony and computing in a phone-like device has been around
since the 1970s also, the first real smartphone did not appear until the mid-1990s when Nokia
released the N9000, which literally combined two, mostly separate devices: a phone and a PDA
(Personal Digital Assistant). In 1997, Ericsson coined the term smartphone for its GS88
‘‘Penelope.’’
Now that smartphones have become ubiquitous, the competition between the various operating
systems is fierce and the outcome is even less clear than in the PC world. At the time of writing,
Google’s Android is the dominant operating system with Apple’s iOS a clear second, but this was
not always the case and all may be different again in just a few years. If anything is clear in the
world of smartphones, it is that it is not easy to stay king of the mountain for long.
After all, most smartphones in the first decade after their inception were running Symbian OS. It
was the operating system of choice for popular brands like Samsung,
6
Sony Ericsson, Motorola, and especially Nokia. However, other operating systems like RIM’s
Blackberry OS (introduced for smartphones in 2002) and Apple’s iOS (released for the first iPhone
in 2007) started eating into Symbian’s market share. Many expected that RIM would dominate the
business market, while iOS would be the king of the consumer devices. Symbian’s market share
plummeted. In 2011, Nokia ditched Symbian and announced it would focus on Windows Phone
as its primary platform.
For some time, Apple and RIM were the toast of the town (although not nearly as dominant as
Symbian had been), but it did not take very long for Android, a Linux-based operating system
released by Google in 2008, to overtake all its rivals.
For phone manufacturers, Android had the advantage that it was open source and available under
a permissive license. As a result, they could tinker with it and adapt it to their own hardware with
ease. Also, it has a huge community of developers writing apps, mostly in the familiar Java
programming language. Even so, the past years have shown that the dominance may not last, and
Android’s competitors are eager to claw back some of its market share.

Types of Operating System

1. Mainframe Operating Systems

At the high end are the operating systems for mainframes, those room-sized computers still found
in major corporate data centers. These computers differ from personal computers in terms of their
I/O capacity. A mainframe with 1000 disks and millions of gigabytes of data is not unusual; a
personal computer with these specifications would be the envy of its friends. Mainframes are also
making something of a comeback as high-end Web servers, servers for large-scale electronic
commerce sites, and servers for business-to-business transactions.
The operating systems for mainframes are heavily oriented toward processing many jobs at once,
most of which need prodigious amounts of I/O. They typically offer three kinds of services: batch,
transaction processing, and timesharing. A batch system is one that processes routine jobs without
any interactive user present. Claims processing in an insurance company or sales reporting for a
chain of stores is typically done in batch mode. Transaction-processing systems handle large
numbers of small requests, for example, check processing at a bank or airline reservations. Each
unit of work is small, but the system must handle hundreds or thousands per second. Timesharing
systems allow multiple remote users to run jobs on the computer at once, such as querying a big
database. These functions are closely related; mainframe operating systems often perform all of
them. An example mainframe operating system is OS/390, a descendant of OS/360. However,
mainframe operating systems are gradually being replaced by UNIX variants such as Linux.

2. Server Operating Systems

One level down are the server operating systems. They run on servers, which are either very large
personal computers, workstations, or even mainframes. They serve multiple users at once over a
network and allow the users to share hardware and software resources. Servers can provide print
service, file service, or Web service. Internet providers run many server machines to support their
customers and Websites use servers to store the Web pages and handle the incoming requests.
Typical server operating systems are Solaris, FreeBSD, Linux and Windows Server 201x.

7
3. Multiprocessor Operating Systems

An increasingly common way to get major-league computing power is to connect multiple CPUs
into a single system. Depending on precisely how they are connected and what is shared, these
systems are called parallel computers, multicomputers, or multiprocessors. They need special
operating systems, but often these are variations on the server operating systems, with special
features for communication, connectivity, and consistency.
With the recent advent of multicore chips for personal computers, even conventional desktop and
notebook operating systems are starting to deal with at least small-scale multiprocessors and the
number of cores is likely to grow over time. Luckily, quite a bit is known about multiprocessor
operating systems from years of previous research, so using this knowledge in multicore systems
should not be hard. The hard part will be having applications make use of all this computing power.
Many popular operating systems, including Windows and Linux, run on multiprocessors.

4. Personal Computer Operating Systems

The next category is the personal computer operating system. Modern ones all support
multiprogramming, often with dozens of programs started up at boot time. Their job is to provide
good support to a single user. They are widely used for word processing, spreadsheets, games, and
Internet access. Common examples are Linux, FreeBSD, Windows 7, Windows 8, and Apple’s OS
X. Personal computer operating systems are so widely known that probably little introduction is
needed. In fact, many people are not even aware that other kinds exist.

5. Handheld Computer Operating Systems

Continuing on down to smaller and smaller systems, we come to tablets, smartphones and other
handheld computers. A handheld computer, originally known as a PDA (Personal Digital
Assistant), is a small computer that can be held in your hand during operation. Smartphones and
tablets are the best-known examples. As we have already seen, this market is currently dominated
by Google’s Android and Apple’s iOS, but they have many competitors. Most of these devices
boast multicore CPUs, GPS, cameras and other sensors, copious amounts of memory, and
sophisticated operating systems. Moreover, all of them have more third-party applications
(‘‘apps’’) than you can shake a (USB) stick at.
6. Embedded Operating Systems

Embedded systems run on the computers that control devices that are not generally thought of as
computers and which do not accept user-installed software. Typical examples are microwave
ovens, TV sets, cars, DVD recorders, traditional phones, and MP3 players. The main property
which distinguishes embedded systems from handhelds is the certainty that no untrusted software
will ever run on it. You cannot download new applications to your microwave oven—all the
software is in ROM. This means that there is no need for protection between applications, leading
to design simplification. Systems such as Embedded Linux, QNX and VxWorks are popular in this
domain.

7. Sensor-Node Operating Systems

Networks of tiny sensor nodes are being deployed for numerous purposes. These nodes are tiny
computers that communicate with each other and with a base station
8
using wireless communication. Sensor networks are used to protect the perimeters of buildings,
guard national borders, detect fires in forests, measure temperature and precipitation for weather
forecasting, glean information about enemy movements on battlefields, and much more.
The sensors are small battery-powered computers with built-in radios. They have limited power
and must work for long periods of time unattended outdoors, frequently in environmentally harsh
conditions. The network must be robust enough to tolerate failures of individual nodes, which
happen with ever-increasing frequency as the batteries begin to run down.
Each sensor node is a real computer, with a CPU, RAM, ROM, and one or more environmental
sensors. It runs a small, but real operating system, usually one that is event driven, responding to
external events or making measurements periodically based on an internal clock. The operating
system has to be small and simple because the nodes have little RAM and battery lifetime is a
major issue. Also, as with embedded systems, all the programs are loaded in advance; users do not
suddenly start programs they downloaded from the Internet, which makes the design much simpler.
TinyOS is a well-known operating system for a sensor node.

8. Real-Time Operating Systems

Another type of operating system is the real-time system. These systems are characterized by
having time as a key parameter. For example, in industrial process-control systems, real-time
computers have to collect data about the production process and use it to control machines in the
factory. Often there are hard deadlines that must be met. For example, if a car is moving down an
assembly line, certain actions must take place at certain instants of time. If, for example, a welding
robot welds too early or too late, the car will be ruined. If the action absolutely must occur at a
certain moment (or within a certain range), we have a hard real-time system. Many of these are
found in industrial process control, avionics, military, and similar application areas. These systems
must provide absolute guarantees that a certain action will occur by a certain time.
A soft real-time system, is one where missing an occasional deadline, while not desirable, is
acceptable and does not cause any permanent damage. Digital audio or multimedia systems fall in
this category. Smartphones are also soft realtime systems.
Since meeting deadlines is crucial in (hard) real-time systems, sometimes the operating system is
simply a library linked in with the application programs, with ev erything tightly coupled and no
protection between parts of the system. An example of this type of real-time system is eCos.
The categories of handhelds, embedded systems, and real-time systems overlap considerably.
Nearly all of them have at least some soft real-time aspects. The embedded and real-time systems
run only software put in by the system designers; users cannot add their own software, which
makes protection easier. The handhelds and embedded systems are intended for consumers,
whereas realtime systems are more for industrial usage. Nevertheless, they hav e a certain amount
in common.

9. Smart Card Operating Systems

The smallest operating systems run on smart cards, which are credit-card-sized devices containing
a CPU chip. They hav e very severe processing power and memory constraints. Some are powered
by contacts in the reader into which they are inserted, but contactless smart cards are inductively
powered, which greatly limits what they can do. Some of them can
9
handle only a single function, such as electronic payments, but others can handle multiple
functions. Often these are proprietary systems.
Some smart cards are Java oriented. This means that the ROM on the smart card holds an
interpreter for the Java Virtual Machine (JVM). Java applets (small programs) are downloaded to
the card and are interpreted by the JVM interpreter. Some of these cards can handle multiple Java
applets at the same time, leading to multiprogramming and the need to schedule them. Resource
management and protection also become an issue when two or more applets are present at the same
time. These issues must be handled by the (usually extremely primitive) operating system present
on the card.
Functions of Operating System
Following are some of important functions of an operating System.

1. Memory Management
2. Processor Management
3. Device Management
4. File Management
5. Security
6. Control over system performance
7. Job accounting
8. Error detecting aids
9. Coordination between other software and users

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

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

1
0
 • Allocates the processor (CPU) to a process.
• De-allocates processor when a process is no longer required.

3. 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.
• De-allocates devices.

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

5. Security
The operating system uses password protection to protect user data and similar other techniques.
it also prevents unauthorized access to programs and user data.

6. Control over system performance

Monitors overall system health to help improve performance. records the response time between
service requests and system response to have a complete view of the system health. This can help
improve performance by providing important information needed to troubleshoot problems.

7. Job accounting
Operating system Keeps track of time and resources used by various tasks and users, this
information can be used to track resource usage for a particular user or group of user.

8. Error detecting aids

Operating system constantly monitors the system to detect errors and avoid the malfunctioning of
computer system.

9. Coordination between other software and users

1
1
Operating systems also coordinate and assign interpreters, compilers, assemblers and other
software to the various users of the computer systems.

Unit-2 Operating System Structure

Kernel
Kernel is central component of an operating system that manages operations of computer and
hardware. It basically manages operations of memory and CPU time. It is core component of an
operating system. Kernel acts as a bridge between applications and data processing performed at
hardware level using inter-process communication and system calls.
Kernel loads first into memory when an operating system is loaded and remains into memory until
operating system is shut down again. It is responsible for various tasks such as disk management,
task management, and memory management.
It decides which process should be allocated to processor to execute and which process should be
kept in main memory to execute. It basically acts as an interface between user applications and
hardware. The major aim of kernel is to manage communication between software i.e. user-level
applications and hardware i.e., CPU and disk memory.
Objectives of kernel
• To establish communication between user level application and hardware.
• To decide state of incoming processes.
• To control disk management.
• To control memory management.
• To control task management

Different types of kernel are

1. Monolithic kernel
2. Microkernel
3. Exokernel
4. Nanokernel
A system as large and complex as a modern operating system must be engineered carefully if it is
to function properly and be modified easily. A common approach is to partition the task into small
components, or modules, rather than have one monolithic system. Each of these modules should
be a well-defined portion of the system with carefully defined inputs, outputs and functions.
Monolithic kernel
In the monolithic approach the entire operating system runs as a single program in kernel mode.
The operating system is written as a collection of procedures, linked together into a single large
executable binary program. When this technique is used, each procedure in the system is free to
call any other one, if the latter provides some useful computation
1
2
that the former needs. Being able to call any procedure you want is very efficient, but having
thousands of procedures that can call each other without restriction may also lead to a system that
is unwieldy and difficult to understand. Also, a crash in any of these procedures will take down
the entire operating system.
To construct the actual object program of the operating system when this approach is used, one
first compiles all the individual procedures (or the files containing the procedures) and then binds
them all together into a single executable file using the system linker. In terms of information
hiding, there is essentially none—every procedure is visible to every other procedure (as opposed
to a structure containing modules or packages, in which much of the information is hidden away
inside modules, and only the officially designated entry points can be called from outside the
module).
Even in monolithic systems, however, it is possible to have some structure. The services (system
calls) provided by the operating system are requested by putting the parameters in a well-defined
place (e.g., on the stack) and then executing a trap instruction. This instruction switches the
machine from user mode to kernel mode and transfers control to the operating system. The
operating system then fetches the parameters and determines which system call is to be carried out.
After that, it indexes into a table that contains in slot k a pointer to the procedure that carries out
system call k.
This organization suggests a basic structure for the operating system:
1. A main program that invokes the requested service procedure.
2. A set of service procedures that carry out the system calls.
3. A set of utility procedures that help the service procedures.
In this model, for each system call there is one service procedure that takes care of it and
executes it. The utility procedures do things that are needed by several service procedures, such
as fetching data from user programs. This division of the procedures into three layers is shown in
Figure.
In addition to the core operating system that is loaded when the computer is booted, many operating
systems support loadable extensions, such as I/O device drivers and file systems. These
components are loaded on demand. In UNIX they are called shared libraries. In Windows they
are called DLLs (Dynamic-Link Libraries). They have file extension .dll and the
C:\Windows\system32 directory on Windows systems has well over 1000 of them.
Main
procedure

Service
procedures

Utility
procedures

Fig: A simple structuring model for a monolithic system.

Advantages:
1
3
 •It provides CPU scheduling, memory scheduling, file management through System calls
only.
• Execution of the process is fast because there is no separate memory space for user and kernel.
Disadvantages:

• If any service fails, then it leads to system failure.

• If new services are to be added then the entire Operating System needs to be modified.
Microkernel
Microkernel is one of the classifications of the kernel. Being a kernel, it manages all system
resources. But in a microkernel, the user services and kernel services are implemented in different
address space. The user services are kept in user address space, and kernel services are kept under
kernel address space, thus also reduces the size of kernel and size of operating system as well.

It provides minimal services of process and memory management. The communication between
client program/application and services running in user address space is established through
message passing, reducing the speed of execution microkernel. The Operating System remains
unaffected as user services and kernel services are isolated so if any user service fails it does not
affect kernel service. Thus, it adds to one of the advantages in a microkernel. It is easily extendable
i.e. if any new services are to be added they are added to user address space and hence requires no
modification in kernel space. It is also portable, secure and reliable.
Microkernel is solely responsible for the most important services of operating system they are
named as follows:
• Inter process-Communication
• Memory Management
• CPU-Scheduling Advantages:

• If new services are to be added then it can be easily added.

Disadvantages:

1
4
 •Since we are using User Space and Kernel Space separately, so the communication between
these can reduce the overall execution time. Exokernel
Rather than cloning the actual machine, as is done with virtual machines, another strategy is
partitioning it, in other words, giving each user a subset of the resources. Thus one virtual machine
might get disk blocks 0 to 1023, the next one might get blocks 1024 to 2047, and so on.
At the bottom layer, running in kernel mode, is a program called the exokernel (Engler et al., 1995).
Its job is to allocate resources to virtual machines and then check attempts to use them to make
sure no machine is trying to use somebody else’s resources. Each user-level virtual machine can
run its own operating system, as on VM/370 and the Pentium virtual 8086s, except that each one
is restricted to using only the resources it has asked for and been allocated.
The advantage of the exokernel scheme is that it saves a layer of mapping. In the other designs,
each virtual machine thinks it has its own disk, with blocks running from 0 to some maximum, so
the virtual machine monitor must maintain tables to remap disk addresses (and all other resources).
With the exokernel, this remapping is not needed. The exokernel need only keep track of which
virtual machine has been assigned which resource. This method still has the advantage of
separating the multiprogramming (in the exokernel) from the user operating system code (in user
space), but with less overhead, since all the exokernel has to do is keep the virtual machines out of
each other’s hair.

Nanokernel
In a Nanokrnel, as the name suggests, the whole code of the kernel is very small i.e. the code
executing in the privileged mode of the hardware is very small. The term nanokernel is used to
describe a kernel that supports a nanosecond clock resolution.
Advantages:

• It offers hardware abstractions without system services.

Disadvantages:

• It is quite same as Micro kernel hence it is less used.

Layered System
The system had six layers, as shown in Figure. Layer 0 dealt with allocation of the processor,
switching between processes when interrupts occurred or timers expired. Above layer 0, the system
consisted of sequential processes, each of which could be programmed without having to worry
about the fact that multiple processes were running on a single processor. In other words, layer 0
provided the basic multiprogramming of the CPU.
Layer Function

5 The operator

4 User programs

3 Input/output management

2 Operator-process communication

1
5
 1 Memory and drum management

0 Processor allocation and

multiprogramming
Fig: Structure of the Operating System
Layer 1 did the memory management. It allocated space for processes in main memory and on a
512K word drum used for holding parts of processes (pages) for which there was no room in main
memory. Above layer 1, processes did not have to worry about whether they were in memory or
on the drum; the layer 1 software took care of making sure pages were brought into memory at the
moment they were needed and removed when they were not needed.
Layer 2 handled communication between each process and the operator console (that is, the user).
On top of this layer each process effectively had its own operator console. Layer 3 took care of
managing the I/O devices and buffering the information streams to and from them. Above layer 3
each process could deal with abstract I/O devices with nice properties, instead of real devices with
many peculiarities. Layer 4 was where the user programs were found. They did not have to worry
about process, memory, console, or I/O management. The system operator process was located in
layer 5.

Client-Server Model
A slight variation of the microkernel idea is to distinguish two classes of processes, the servers,
each of which provides some service, and the clients, which use these services. This model is
known as the client-server model. Often the lowest layer is a microkernel, but that is not required.
The essence is the presence of client processes and server processes.
Communication between clients and servers is often by message passing. To obtain a service, a
client process constructs a message saying what it wants and sends it to the appropriate service.
The service then does the work and sends back the answer. If the client and server happen to run
on the same machine, certain optimizations are possible, but conceptually, we are still talking about
message passing here.
An obvious generalization of this idea is to have the clients and servers run on different computers,
connected by a local or wide-area network, as depicted in Figure. Since clients communicate with
servers by sending messages, the clients need not know whether the messages are handled locally
on their own machines, or whether they are sent across a network to servers on a remote machine.
As far as the client is concerned, the same thing happens in both cases: requests are sent and replies
come back. Thus the client-server model is an abstraction that can be used for a single machine or
for a network of machines.
Machine 1 Machine 2 Machine 3 Machine 4

Client File server Process server Terminal server

Kernel Kernel Kernel Kernel

Network

Message from
client to server

Fig: Client-Server Model over a network

1
6
Increasingly many systems involve users at their home PCs as clients and large machines elsewhere
running as servers. In fact, much of the Web operates this way. A PC sends a request for a Web
page to the server and the Web page comes back. This is a typical use of the client-server model
in a network.

Virtual Machines
The initial releases of OS/360 were strictly batch systems. Nevertheless, many 360 users wanted
to be able to work interactively at a terminal, so various groups, both inside and outside IBM,
decided to write timesharing systems for it. The official IBM timesharing system, TSS/360, was
delivered late, and when it finally arrived it was so big and slow that few sites converted to it.
VM/370 was based on a smart observation: a timesharing system provides (1) multiprogramming
and (2) an extended machine with a more convenient interface than the bare hardware. The essence
of VM/370 is to completely separate these two functions.
The heart of the system, known as the virtual machine monitor, runs on the bare hardware and
does the multiprogramming, providing not one, but several virtual machines to the next layer up,
as shown in Fig. 1-28. However, unlike all other operating systems, these virtual machines are not
extended machines, with files and other nice features. Instead, they are exact copies of the bare
hardware, including kernel/user mode, I/O, interrupts, and everything else the real machine has.

Fig: The structure of VM/370 with CMS

Because each virtual machine is identical to the true hardware, each one can run any operating
system that will run directly on the bare hardware. Different virtual machines can, and frequently
do, run different operating systems. On the original IBM VM/370 system, some ran OS/360 or one
of the other large batch or transaction-processing operating systems, while others ran a single-user,
interactive system called CMS (Conversational Monitor System) for interactive timesharing
users. The latter was popular with programmers.
When a CMS program executed a system call, the call was trapped to the operating system in its
own virtual machine, not to VM/370, just as it would be were it running on a real machine instead
of a virtual one. CMS then issued the normal hardware I/O instructions for reading its virtual disk
or whatever was needed to carry out the call. These I/O instructions were trapped by VM/370,
which then performed them as part of its simulation of the real hardware. By completely separating
the functions of multiprogramming and providing an extended machine, each of the pieces could
be much simpler, more flexible, and much easier to maintain.

The Shell
The operating system is the code that carries out the system calls. Editors, compilers, assemblers,
linkers, utility programs, and command interpreters definitely are
1
7
not part of the operating system, even though they are important and useful. At the risk of confusing
things somewhat, in this section we will look briefly at the UNIX command interpreter, the shell.
Although it is not part of the operating system, it makes heavy use of many operating system
features and thus serves as a good example of how the system calls are used. It is also the main
interface between a user sitting at his terminal and the operating system, unless the user is using a
graphical user interface. Many shells exist, including sh, csh, ksh, and bash. All of them support
the functionality described below, which derives from the original shell (sh).
When any user logs in, a shell is started up. The shell has the terminal as standard input and
standard output. It starts out by typing the prompt, a character such as a dollar sign, which tells
the user that the shell is waiting to accept a command. If the user now types date for example, the
shell creates a child process and runs the date program as the child. While the child process is
running, the shell waits for it to terminate. When the child finishes, the shell types the prompt again
and tries to read the next input line.
The user can specify that standard output be redirected to a file, for example, date >file
Similarly, standard input can be redirected, as in sor t <file1 >file2 which invokes the

sort program with input taken from file1 and output sent to file2.

The output of one program can be used as the input for another program by connecting them with
a pipe. Thus cat file1 file2 file3 | sort >/dev/lp invokes the cat program to concatenate three files and
send the output to sort to arrange all the lines in alphabetical order. The output of sort is redirected
to the file /dev/lp, typically the printer.
If a user puts an ampersand after a command, the shell does not wait for it to complete. Instead it
just gives a prompt immediately. Consequently, cat file1 file2 file3 | sort >/dev/lp & starts up the sort
as a background job, allowing the user to continue working normally while the sort is going on.
The shell has a number of other interesting features, which we do not have space to discuss here.
Most books on UNIX discuss the shell at some length (e.g., Kernighan and Pike, 1984; Quigley,
2004; Robbins, 2005).
Most personal computers these days use a GUI. In fact, the GUI is just a program running on top
of the operating system, like a shell. In Linux systems, this fact is made obvious because the user
has a choice of (at least) two GUIs: Gnome and KDE or none at all (using a terminal window on
X11). In Windows, it is also possible to replace the standard GUI desktop (Windows Explorer)
with a different program by changing some values in the registry, although few people do this.

1
8
 Unit-3 Process Management
Process
A process is basically a program in execution. The execution of a process must progress in a
sequential fashion. For example, when we write a program in C or C++ and compile it, the compiler
creates binary code. The original code and binary code are both programs. When we actually run
the binary code, it becomes a process.
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.

Stack
The process Stack contains the temporary data such as method/function parameters, return address
and local variables.
Heap
This is dynamically allocated memory to a process during its run time.
Text
This includes the current activity represented by the value of Program Counter and the contents of
the processor's registers.

1
9
Data
This section contains the global and static variables.

The Process Model

In this model, all the runnable software on the computer, sometimes including the operating
system, is organized into a number of sequential processes, or just processes for short. A process
is just an executing program, including the current values of the program counter, registers, and
variables. Conceptually, each process has its own virtual CPU. In reality, of course, the real CPU
switches back and forth from process to process, but to understand the system, it is much easier to
think about a collection of processes running in (pseudo) parallel, than to try to keep track of how
the CPU switches from program to program. This rapid switching back and forth is called
multiprogramming.

Fig: (a) Multiprogramming of four programs. (b) Conceptual model of four independent, sequential
processes. (c) Only one program is active at once.

With the CPU switching back and forth among the processes, the rate at which a process performs
its computation will not be uniform and probably not even reproducible if the same processes are
run again. Thus, processes must not be programmed with built-in assumptions about timing. The
difference between a process and a program is subtle, but crucial. An analogy makes help here:

Consider a culinary-minded computer scientist who is baking a birthday cake for his daughter. He has
a birthday cake recipe and a kitchen well stocked with all the input: flour, eggs, sugar, extract of vanilla,
and so on. In this analogy, the recipe is the program (i.e., an algorithm expressed in some suitable
notation), the computer scientist is the processor (CPU), and the cake ingredients are the input data.
The process is the activity consisting of our baker reading the recipe, fetching the ingredients, and
baking the cake.

Now imagine that the computer scientist’s son comes running in crying, saying that he has been stung
by a bee. The computer scientist records where he was in the recipe (the state of the current process is
saved), gets out a first aid book, and begins following the directions in it. Here we see the processor
being switched from one process (baking) to a higher-priority process (administering medical care),
each having a different program (recipe versus first aid book). When the bee sting has been taken care
of, the computer scientist goes back to his cake, continuing at the point where he left off.

2
0
The key idea here is that a process is an activity of some kind. It has a program, input, output, and
a state. A single processor may be shared among several processes, with some scheduling
algorithm being used to determine when to stop work on one process and service a different one.

Process States and Transitions

The process, from its creation to completion, passes through various states. Although each
process is an independent entity, with its own program counter and internal state, processes often
need to interact with other processes. One process may generate some output that another process
uses as input. In the shell command cat chapter1 chapter2 chapter3 | grep tree
the first process, running cat, concatenates and outputs three files. The second process, running
grep, selects all lines containing the word ‘‘tree.’’ Depending on the relative speeds of the two
processes (which depends on both the relative complexity of the programs and how much CPU
time each one has had), it may happen that grep is ready to run, but there is no input waiting for it.
It must then block until some input is available.
When a process blocks, it does so because logically it cannot continue, typically because it is
waiting for input that is not yet available. It is also possible for a process that is conceptually ready
and able to run to be stopped because the operating system has decided to allocate the CPU to
another process for a while. These two conditions are completely different. In the first case, the
suspension is inherent in the problem (you cannot process the user’s command line until it has
been typed). In the second case, it is a technicality of the system (not enough CPUs to give each
process its own private processor).

Fig: Process states and Transitions

1. Running (actually using the CPU at that instant).

2. Ready (runnable; temporarily stopped to let another process run).
3. Blocked (unable to run until some external event happens).

Logically, the first two states are similar. In both cases the process is willing to run, only in the
second one, there is temporarily no CPU available for it. The third state is fundamentally different
from the first two in that the process cannot run, even if the CPU is idle and has nothing else to do.
Four transitions are possible among these three states, as shown. Transition 1 occurs when the
operating system discovers that a process cannot continue right now. In some systems the process
can execute a system call, such as pause, to get into blocked state. In other systems, including
UNIX, when a process reads from a pipe or special file (e.g., a terminal) and there is no input
available, the process is automatically blocked.

2
1
Transitions 2 and 3 are caused by the process scheduler, a part of the operating system, without the
process even knowing about them. Transition 2 occurs when the scheduler decides that the
running process has run long enough, and it is time to let another process have some CPU time.
Transition 3 occurs when all the other processes have had their fair share and it is time for the
first process to get the CPU to run again. The subject of scheduling, that is, deciding which process
should run when and for how long, is an important one; we will look at it later in this chapter.
Many algorithms have been devised to try to balance the competing demands of efficiency for the
system as a whole and fairness to individual processes.
Transition 4 occurs when the external event for which a process was waiting (such as the arrival
of some input) happens. If no other process is running at that instant, transition 3 will be triggered
and the process will start running. Otherwise it may have to wait in ready state for a little while
until the CPU is available and its turn comes.

Process Control Block

Process Control Block is a data structure that contains information of the process related to it. The
process control block is also known as a task control block, entry of the process table, etc.
It is very important for process management as the data structuring for processes is done in terms
of the PCB. It also defines the current state of the operating system.

Fig: Process Control Block

Process State
This specifies the process state i.e. new, ready, running, waiting or terminated.
Process Number
This shows the number of the particular process.
Program Counter

2
2
This contains the address of the next instruction that needs to be executed in the process.
Registers
This specifies the registers that are used by the process. They may include accumulators, index
registers, stack pointers, general purpose registers etc.

List of Open Files

These are the different files that are associated with the process
CPU Scheduling Information
The process priority, pointers to scheduling queues etc. is the CPU scheduling information that is
contained in the PCB. This may also include any other scheduling parameters.
Memory Management Information
The memory management information includes the page tables or the segment tables depending
on the memory system used. It also contains the value of the base registers, limit registers etc.
I/O Status Information
This information includes the list of I/O devices used by the process, the list of files etc.
Accounting information
The time limits, account numbers, amount of CPU used, process numbers etc. are all a part of the
PCB accounting information.
Location of the Process Control Block
The process control block is kept in a memory area that is protected from the normal user access.
This is done because it contains important process information. Some of the operating systems
place the PCB at the beginning of the kernel stack for the process as it is a safe location.

Operations on the Process

The execution of a process is a complex activity. It involves various operations. Following are the
operations that are performed while execution of a process:

1. Creation: This the initial step of process execution activity. Process creation means the
construction of a new process for the execution. This might be performed by system, user or
old process itself. There are several events that leads to the process creation. Some of the such
events are following:

• When we start the computer, system creates several background processes.

• A user may request to create a new process.
• A process can create a new process itself while executing. Batch system takes
initiation of a batch job.
2. Scheduling/Dispatching: The event or activity in which the state of the process is changed
from ready to running. It means the operating system puts the
2
3
 process from ready state into the running state. Dispatching is done by operating system when
the resources are free or the process has higher priority than the ongoing process. There are
various other cases in which the process in running state is preempted and process in ready
state is dispatched by the operating system.

3. Blocking: When a process invokes an input-output system call that blocks the process and
operating system put in block mode. Block mode is basically a mode where process waits for
inputoutput. Hence on the demand of process itself, operating system blocks the process and
dispatches another process to the processor. Hence, in process blocking operation, the
operating system puts the process in ‘waiting’ state.

4. Preemption: When a timeout occurs that means the process hadn’t been terminated in the
allotted time interval and next process is ready to execute, then the operating system preempts
the process. This operation is only valid where CPU scheduling supports preemption. Basically
this happens in priority scheduling where on the incoming of high priority process the ongoing
process is preempted. Hence, in process preemption operation, the operating system puts the
process in ‘ready’ state.

5. Termination: Process termination is the activity of ending the process. In other words, process
termination is the relaxation of computer resources taken by the process for the execution. Like
creation, in termination also there may be several events that may lead to the process
termination.
Some of them are:
• Process completes its execution fully and it indicates to the OS that it has finished.
• Operating system itself terminates the process due to service errors.
• There may be problem in hardware that terminates the process. One process can be
terminated by another process.

Process Hierarchies
In some systems, when a process creates another process, the parent process and child process
continue to be associated in certain ways. The child process can itself create more processes,
forming a process hierarchy. Note that unlike plants and animals that use sexual reproduction, a
process has only one parent (but zero, one, two, or more children). So a process is more like a
hydra than like, say, a cow.
In UNIX, a process and all of its children and further descendants together form a process
group. When a user sends a signal from the keyboard, the signal is delivered to all members of the
process group currently associated with the keyboard (usually all active processes that were created
in the current window). Individually, each process can catch the signal, ignore the signal, or take
the default action, which is to be killed by the signal.
As another example of where the process hierarchy plays a key role, let us look at how UNIX
initializes itself when it is started, just after the computer is booted. A special process, called init,
is present in the boot image. When it starts running, it reads a file telling how many terminals there
are. Then it divides off a new process per terminal. These processes wait for someone to log in. If
a login is successful, the login process executes a shell to accept commands. These commands may

2
4
start up more processes, and so forth. Thus, all the processes in the whole system belong to a single
tree, with init at the root.
In contrast, Windows has no concept of a process hierarchy. All processes are equal. The only
hint of a process hierarchy is that when a process is created, the parent is given a special token
(called a handle) that it can use to control the child. However, it is free to pass this token to some
other process, thus invalidating the hierarchy. Processes in UNIX cannot disinherit their children.

Implementation on Process
To implement the process model, the operating system maintains a table (an array of structures),
called the process table, with one entry per process. (Some authors call these entries process
control blocks.) This entry contains important information about the process’ state, including its
program counter, stack pointer, memory allocation, the status of its open files, its accounting and
scheduling information, and everything else about the process that must be saved when the process
is switched from running to ready or blocked state so that it can be restarted later as if it had never
been stopped.
Figure below shows some of the key fields in a typical system. The fields in the first column relate
to process management. The other two relate to memory management and file management,
respectively. It should be noted that precisely which fields the process table has is highly system
dependent, but this figure gives a general idea of the kinds of information needed.

Now that we have looked at the process table, it is possible to explain a little more about how the
illusion of multiple sequential processes is maintained on one (or each) CPU. Associated with
each I/O class is a location (typically at a fixed location near the bottom of memory) called the
interrupt vector. It contains the address of the interrupt service procedure. Suppose that user
process 3 is running when a disk interrupt happens. User process 3’s program counter, program
status word, and sometimes one or more registers are pushed onto the (current) stack by the
interrupt hardware. The computer then jumps to the address specified in the interrupt vector.
That is all the hardware does. From here on, it is up to the software, in particular, the interrupt
service procedure.
All interrupts start by saving the registers, often in the process table entry for the current process.
Then the information pushed onto the stack by the interrupt is removed and the stack pointer is set
to point to a temporary stack used by the process handler. Actions such as saving the registers and
setting the stack pointer cannot even be expressed in high-level languages such as C, so they are
performed by a small assembly-language routine, usually the same one for all interrupts since the
work of saving the registers is identical, no matter what the cause of the interrupt is.
When this routine is finished, it calls a C procedure to do the rest of the work for this specific
interrupt type. (We assume the operating system is written in C, the usual choice for all real
operating systems.) When it has done its job, possibly making some process now ready, the
scheduler is called to see who to run next. After that, control is passed back to the
assemblylanguage code to load up the registers and memory map for the now-current process and
start it running.

2
5
 Fig: Fields of Process Table Entry

Cooperating Processes
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.

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

2
6
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.

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 −

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

System Calls
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.

Fig: Execution of System call

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.

2
8
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.
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 −

2
9
Threads
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.

3
0
Difference between process and thread
Process Thread
1. Process is heavy weight or resource 1. Thread is light weight, taking lesser
intensive. resources than a process.
2. Process switching needs interaction with 2. Thread switching does not need to interact
operating system. with operating system.
3. In multiple processing environments, each 3. All threads can share same set of open files,
process executes the same code but has its child processes.
own memory and file resources.
4. If one process is blocked, then no other 4. While one thread is blocked and waiting, a
process can execute until the first process second thread in the same task can run
is unblocked.
5. Multiple processes without using threads use 5. Multiple threaded processes use fewer
more resources. resources.
6. In multiple processes each process operates 6. One thread can read, write or change another
independently of the others. thread's data.

Advantages of Thread

1. Responsiveness: If the process is divided into multiple threads, if one thread completes its
execution, then its output can be immediately returned.
2. Faster context switch: Context switch time between threads is lower compared to process
context switch. Process context switching requires more overhead from the CPU.

3
1
 3. Effective utilization of multiprocessor system: If we have multiple threads in a single
process, then we can schedule multiple threads on multiple processors. This will make
process execution faster.
4. Resource sharing: Resources like code, data, and files can be shared among all threads
within a process. Note: stack and registers can’t be shared among the threads. Each thread
has its own stack and registers.
5. Communication: Communication between multiple threads is easier, as the threads shares
common address space. while in process we have to follow some specific communication
technique for communication between two process.

Types of Thread

1. User Level Thread

The user-level threads are implemented by users and the kernel is not aware of the existence
of these threads. It handles them as if they were single-threaded processes. User-level threads
are small and much faster than kernel level threads. They are represented by a program counter
(PC), stack, registers and a small process control block. Also, there is no kernel involvement
in synchronization for user-level threads. Advantages

• User-level threads are easier and faster to create than kernel-level threads. They can also
be more easily managed.
• User-level threads can be run on any operating system.
• There are no kernel mode privileges required for thread switching in user-level threads.

Disadvantages

1. Multithreaded applications in user-level threads cannot use multiprocessing to their

advantage.
2. The entire process is blocked if one user-level thread performs blocking operation.
2. Kernel Level Thread
Kernel-level threads are handled by the operating system directly and the thread management
is done by the kernel. The context information for the process as well as the process threads is
all managed by the kernel. Because of this, kernel-level threads are slower than user-level
threads.
Advantages

1. Multiple threads of the same process can be scheduled on different processors in

kernellevel threads.
2. The kernel routines can also be multithreaded.
3. If a kernel-level thread is blocked, another thread of the same process can be scheduled by
the kernel.
Disadvantages

3
2
 • 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 leads to maximum utilization of the CPU by
multitasking. Multithreading models are three types

1. Many to Many relationship.

Many to many multithreading models in operating system maps many user

threads to a lesser or equal number of kernel threads. Number of kernel level threads
are specific to the machine; advantage of this model is if a user thread is blocked we can
schedule others user thread to other kernel thread. Thus, System doesn’t block if a
particular thread is blocked.

2. Many to One relationship.

In this model, we have multiple user threads mapped to one kernel thread. In this model
when a user thread makes a blocking system call entire process blocks. As we have only
one kernel thread and only one user thread can access kernel at a time, so multiple threads
are not able access multiprocessor at the same time.

3. One to One relationship.

3
3
 One to one multithreading model maps one user thread to one kernel thread. So, for each
user thread, there is a corresponding kernel thread present in the kernel. In this model,
thread management is done at the kernel level and the user threads are fully supported by
the kernel. Here, if one thread makes the blocking system call, the other threads still run.

Interprocess Communication and Synchronization

Interprocess communication is the mechanism provided by the operating system that allows
processes to communicate with each other. This communication could involve a process letting
another process know that some event has occurred or the transferring of data from one process to
another.

Synchronization is a necessary part of interprocess communication. It is either provided by the

interprocess control mechanism or handled by the communicating processes. Some of the methods
to provide synchronization are as follows –

• Semaphore
A semaphore is a variable that controls the access to a common resource by multiple
processes. The two types of semaphores are binary semaphores and counting semaphores.

• Mutual Exclusion
Mutual exclusion requires that only one process thread can enter the critical section at a
time. This is useful for synchronization and also prevents race conditions.

• Barrier
3
4
 A barrier does not allow individual processes to proceed until all the processes reach it.
Many parallel languages and collective routines impose barriers.

• Spinlock
This is a type of lock. The processes trying to acquire this lock wait in a loop while checking
if the lock is available or not. This is known as busy waiting because the process is not
doing any useful operation even though it is active.

Race Condition

A race condition occurs when two or more threads can access shared data and they try to change
it at the same time.
To see how interprocess communication works in practice, let us now consider a simple but
common example: a print spooler. When a process wants to print a file, it enters the file name in a
special spooler directory. Another process, the printer daemon, periodically checks to see if
there are any files to be printed, and if there are, it prints them and then removes their names from
the directory.
Imagine that our spooler directory has a very large number of slots, numbered 0 , 1, 2, ..., each one
capable of holding a file name. Also imagine that there are two shared variables, out, which points
to the next file to be printed, and in, which points to the next free slot in the directory. These two
variables might well be kept in a two-word file available to all processes. At a certain instant, slots
0 to 3 are empty (the files have already been printed) and slots 4 to 6 are full (with the names of
files queued for printing). More or less simultaneously, processes A and B decide they want to
queue a file for printing. This situation is shown in Fig.

Fig: Two processes want to access shared memory at the same time
Process A reads in and stores the value, 7, in a local variable called next free slot. Just then a clock
interrupt occurs and the CPU decides that process A has run long enough, so it switches to process
B. Process B also reads in and also gets a 7. It, too, stores it in its local variable next free slot. At
this instant both processes think that the next available slot is 7.
Process B now continues to run. It stores the name of its file in slot 7 and updates in to be an 8.
Then it goes off and does other things. Eventually, process A runs again, starting from the place it
left off. It looks at next free slot, finds a 7 there, and writes its file

3
5
name in slot 7, erasing the name that process B just put there. Then it computes next free slot + 1,
which is 8, and sets in to 8. The spooler directory is now internally consistent, so the printer daemon
will not notice anything wrong, but process B will never receive any output. Situations like this,
where two or more processes are reading or writing some shared data and the final result depends
on who runs precisely when, are called race conditions.

Critical Section
It is part of the program where shared resources are accessed by various processes. When one
process is executing in its critical section no other process is to be allowed to execute in its critical
section. Mutual exclusion is a way of making sure that if one process is using a shared modifiable
data, the other processes will be excluded from doing the same thing. If we could arrange matters
such that no two processes were ever in their critical sections simultaneously, we could avoid race
conditions.
We need four conditions to hold to have a good solution for the critical section problem (mutual
exclusion).
• No two processes may at the same moment inside their critical sections.
• No assumptions are made about relative speeds of processes or number of CPUs.
• No process should outside its critical section should block other processes.
• No process should wait arbitrary long to enter its critical section.

Fig: Mutual exclusion using critical region

Here process A enters its critical region at time T1. A little later, at time T2 process B attempts to
enter its critical region but fails because another process is already in its critical region and we
allow only one at a time. Consequently, B is temporarily suspended until time T3 when A leaves
its critical region, allowing B to enter immediately. Eventually B leaves (at T4) and we are back to
the original situation with no processes in their critical regions.
Let us understand the inconsistency in the result while accessing the shared resource
simultaneously with the help of an example.

3
6
Look at the figure above, suppose there are two processes P0 and P1. Both share a common variable
A=0. While accessing A both the processes increments the value of A by 1.

First case
The order of execution of the processes is P0, P1 respectively.

Process P0 reads the value of A=0, increments it by 1 (A=1) and writes the incremented value in
A.

Now, process P1 reads the value of A=1, increments its value by 1 (A=2) and writes the
incremented value in A.

So, after both the process P0 and P1 finishes accessing the variable A. The value of A is 2.
Second case

Consider that process P0 has read the variable A=0. Suddenly context switch happens and P1 takes
the charge, and start executing. P1 would increment the value of A (A=1). After execution P1 gives
the charge again to P0.

Now the value of A for P0 is 0 & when it starts executing it would increment the value of A, from
0 to 1.

So here, when both the processes P0 & P1 end up accessing the variable A, the value of A =1
which is different from the value of A=2 in the first case

Now, this type of condition where the sequence of execution of the processes affects the result is
called race condition

Proposals for achieving mutual exclusion

1. Interrupt disabling

On a single-processor system, the simplest solution is to have each process disable all interrupts
just after entering its critical region and re-enable them just before leaving it. With interrupts
disabled, no clock interrupts can occur. The CPU is only switched from process to process as a
result of clock or other interrupts, after all, and with interrupts turned off the CPU will not be
switched to another process. Thus, once a process has disabled interrupts, it can examine and
update the shared memory without fear that any other process will intervene.

Advantages
• Mutual exclusion can be achieved by implementing operating system primitives to disable
and enable interrupts.
3
7
Disadvantages
• It is unwise to give user process the power to turn off interrupts. Suppose that if one of
them did it and never turned on again. That could be end of the system.

• If the system is multiprocessor with two or more CPUs, disabling interrupts affects only
the CPU that executed the disable instruction.

2. Lock Variables

When a process wants to enter its critical region, it first tests the lock. If the lock is 0, the process
sets it to 1 and enters the critical region. If the lock is already 1, the process just waits until it
becomes 0. Thus, a 0 means that no process is in its critical region, and a 1 means that some
process is in its critical region.
Advantages
• Mutual exclusion can be achieved.
Disadvantages
• Suppose that one process reads the lock and sees that it is 0. Before it can set the lock to 1,
another process is scheduled, runs, and sets the lock to 1. When the first process runs again,
it will also set the lock to 1, and two processes will be in their critical regions at the same
time.

3. Strict Alternation

Process 0 Process 1
The integer variable turn, initially 0, keeps track of whose turn it is to enter the critical region and
examine or update the shared memory. Initially, process 0 inspects turn, finds it to be 0, and enters
its critical region. Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing
turn to see when it becomes 1. Continuously testing a variable until some value appears is called
busy waiting.
When process 0 leaves the critical region, it sets turn to 1, to allow process 1 to enter its critical
region. Suppose that process 1 finishes its critical region quickly, so that both processes are in their
noncritical regions, with turn set to 0. Now process 0 executes its whole loop quickly, exiting its
critical region and setting turn to 1. At this point turn is 1 and both processes are executing in their
noncritical regions.
Suddenly, process 0 finishes its noncritical region and goes back to the top of its loop.
Unfortunately, it is not permitted to enter its critical region now, because turn is 1 and process 1 is
busy with its noncritical region. It hangs in its while loop until process 1 sets turn to 0.

3
8
4. Peterson Algorithm

Before using the shared variables (i.e., before entering its critical region), each process calls
enter region with its own process number, 0 or 1, as parameter. This call will cause it to wait,
if need be, until it is safe to enter. After it has finished with the shared variables, the process
calls leave region to indicate that it is done and to allow the other process to enter, if it so
desires.

Initially neither process is in its critical region. Now process 0 calls enter region. It indicates
its interest by setting its array element and sets turn to 0. Since process 1 is not interested, enter
region returns immediately. If process 1 now makes a call to enter region, it will hang there
until interested[0] goes to FALSE, an event that happens only when process 0 calls leave region
to exit the critical region.

Advantages
• Preserves all conditions of mutual exclusion. Disadvantages

3
9
 • Difficulty to program for n process system.
5. Hardware solution TSL (Test and Set Lock)

Hardware features can make the programming tasks easier and improve system efficiency.

TSL RX,LOCK
It reads the contents of the memory word lock into register RX and then stores a nonzero value
at the memory address lock. The operations of reading the word and storing into it are
guaranteed to be indivisible—no other processor can access the memory word until the
instruction is finished. The CPU executing the TSL instruction locks the memory bus to
prohibit other CPUs from accessing memory until it is done. To use the TSL instruction, we
will use a shared variable, lock, to coordinate access to shared memory.

When lock is 0, any process may set it to 1 using the TSL instruction and then read or write
the shared memory.When it is done, the process sets lock back to 0 using an ordinary move
instruction.

Advantages
• Preserves all condition, easier programming task and improve system efficiency.
Disadvantages
Difficulty in hardware design.
6. Sleep and Wakeup

One of the alternative to the busy waiting is to use sleep and wake up pair. Sleep is a system call
that causes the caller to block, that is be suspended until another process wakes it up.

4
0
 Producer-Consumer problem with a fatal race condition

The producer produces the item and inserts it into the buffer. The value of the global variable
count got increased at each insertion. If the buffer is filled completely and no slot is available
then the producer will sleep, otherwise it keep inserting. On the consumer's end, the value of
count got decreased by 1 at each consumption. If the buffer is empty at any point of time then
the consumer will sleep otherwise, it keeps consuming the items and decreasing the value of
count by 1. The consumer will be waked up by the producer if there is at least 1 item available
in the buffer which is to be consumed. The producer will be waked up by the consumer if there
is at least one slot available in the buffer so that the producer can write that.

Types of Mutual Exclusion

Semaphore
Semaphores is integer variable that is used to solve the critical section problem by using two atomic
operations, wait and signal that are used for process synchronization.
Types of Semaphores

There are two main types of semaphores i.e. counting semaphores and binary semaphores. Details
about these are given as follows −
4
1
1. Counting Semaphores
These are integer value semaphores and have an unrestricted value domain. These semaphores
are used to coordinate the resource access, where the semaphore count is the number of
available resources. If the resources are added, semaphore count automatically incremented
and if the resources are removed, the count is decremented.
The definitions of wait and signal are as follows –
Wait
The wait operation decrements the value of its argument S. If S is negative, then put process in
suspend list.
wait(S)
{
S--; if(S<0)
put process (PCB) in suspend list, sleep()
else return;
}

Signal
The signal operation increments the value of its argument S.
signal(S)
{
S++;
if(S<=0)
Select a process from suspend list, wakeup()
}

2. Binary Semaphores
The binary semaphores are like counting semaphores but their value is restricted to 0 and 1.
The wait operation only works when the semaphore is 1 and the signal operation succeeds
when semaphore is 0. It is sometimes easier to implement binary semaphores than counting
semaphores.

The definitions of wait and signal are as follows –

Wait
wait(S)
{
if(S==1)
S=0; else
Block this process and place this process in suspend list, sleep()
}
4
2
Signal
signal(S)
{
if(suspend list is empty)
S=1; else
Select a process from suspend list, wakeup()
}

4
3
Solving Producer Consumer problem using Semaphore

We have a buffer of fixed size. A producer can produce an item and can place in the buffer. A
consumer can pick items and can consume them. We need to ensure that when a producer is placing
an item in the buffer, then at the same time consumer should not consume any item. In this problem,
buffer is the critical section.
To solve this problem, we need two counting semaphores – Full and Empty. “Full” keeps track of
number of items in the buffer at any given time and “Empty” keeps track of number of unoccupied
slots.
When producer produces an item then the value of “empty” is reduced by 1 because one slot will
be filled now. The value of mutex is also reduced to prevent consumer to access the buffer. Now,
the producer has placed the item and thus the value of “full” is increased by 1. The value of mutex
is also increased by 1 because the task of producer has been completed and consumer can access
the buffer.
As the consumer is removing an item from buffer, therefore the value of “full” is reduced by 1 and
the value is mutex is also reduced so that the producer cannot access the buffer at this moment.

4
4
Now, the consumer has consumed the item, thus increasing the value of “empty” by 1. The value
of mutex is also increased so that producer can access the buffer now.

Monitors
A monitor is a collection of procedures, variables and data structures grouped together in a single
module or package. Processes can call the monitor procedures but cannot access the internal data
structures. Only one process can be active in a monitor at any instant. Monitors are a programming
language construct, so the compiler knows they are special and can handle calls to monitor
procedure, the first few instructions of the procedure will check to see if any other process is
currently active within the monitor. If so, the calling process will be suspended until the other
process has left the monitor. If no other process is using the monitor, the calling process may enter.
So, no two processes will be executing their critical regions at the same time.
Monitors are needed because if many programmers are using a semaphore and one programmer
forgets to signal after the program has left the critical section, then the entire synchronization
mechanism will end up in a deadlock.

Solving producer-consumer problem using monitors

Monitor ProducerConsumer
{ int count; condition
full,empty; void insert(int
item){ if(count==N) wait(full);
insert_item(item); count++;
if(count==1)signal(empty);
}
void remove(){
if(count==0) wait(empty);
remove_item(); count--;
if(count==N-
1)signal(full);
}
count=0;
};
void producer(){

4
5
 while(TRUE){
item=produce_item();
ProducerConsumer.insert(item);
}
}
void consumer(){
while(TRUE){
item=ProducerConsumer.remove();
consume_item();
}
}
Difference between semaphore and monitor
Semaphore Monitor
1. Semaphores is an integer variable S. 1. Monitor is an abstract data type.
2. The value of Semaphore S indicates the 2. The Monitor type contains shared variables
number of shared resources availabe in the and the set of procedures that operate on
system the shared variable.
3. When any process access the shared 3. When any process wants to access the
resources it perform wait() operation on S shared variables in the monitor, it needs to
and when it releases the shared resources it access it through the procedures.
performs signal() operation on S.
4. Semaphore does not have condition 4. Monitor has condition variables.
variables.

Mutex
Mutex (Mutual Exclusion) lock is essentially a variable that is binary nature that provides code
wise functionality for mutual exclusion. At times, there maybe multiple threads that may be trying
to access same resource like memory or I/O etc. To make sure that there is no overriding. Mutex
provides a locking mechanism.
Only one thread at a time can take the ownership of a mutex and apply the lock. Once it done
utilizing the resource and it may release the mutex lock.

4
6
Message Passing
This method of interprocess communication uses two primitives, send and receive, which, like
semaphores and unlike monitors, are system calls rather than language constructs. As such, they
can easily be put into library procedures, such as
send(destination, &message); and
receive(source, &message);
The former call sends a message to a given destination and the latter one receives a message from
a given source (or from ANY, if the receiver does not care). If no message is available, the receiver
can block until one arrives. Alternatively, it can return immediately with an error code.

Producer Consumer Problem with Message Passing

4
7
Producer-Consumer Problem (Bounded Buffer)

Bounded Buffer problem which is also called producer consumer problem is one of the classic
problems of synchronization.
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.

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.
4
8
There needs to be a way to make the producer and consumer work in an independent manner.
Solution
Producer Operation

a. Producer first waits until there is atleast one empty slot.

b. 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.
c. Then, it acquires lock on the buffer, so that the consumer cannot access the buffer until
producer completes its operation.
d. 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.

Consumer Operation

• The consumer waits until there is at least 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.

Serializability

When multiple transactions are running concurrently then there is a possibility that the database
may be left in an inconsistent state. Serializability is a concept that helps us to check which
schedules are serializable. A serializable schedule is the one that always leaves the database in
consistent state.
A serial schedule is always a serializable schedule because in serial schedule, a transaction only
starts when the other transaction finished execution. However a non-serial schedule needs to be
checked for Serializability.
A non-serial schedule of n number of transactions is said to be serializable schedule, if it is
equivalent to the serial schedule of those n transactions. A serial schedule doesn’t allow
concurrency, only one transaction executes at a time and the other starts when the already running
transaction finished.
4
9
There are two types of serializability
Conflict Serializability is one of the type of Serializability, which can be used to check whether
a non-serial schedule is conflict serializable or not. A schedule is called conflict serializable if we
can convert it into a serial schedule after swapping its non-conflicting operations.
View Serializability is a process to find out that a given schedule is view serializable or not. To
check whether a given schedule is view serializable, we need to check whether the given schedule
is View Equivalent to its serial schedule.

Serial Schedule of the above given schedule:

As we know that in Serial schedule a transaction only starts when the current running transaction
is finished. So the serial schedule of the above given schedule would look like this:

If we can prove that the given schedule is View Equivalent to its serial schedule then the given schedule
is called view Serializable.
Locking Protocols

A lock is a data variable which is associated with a data item. This lock signifies that operations
that can be performed on the data item. Locks help synchronize access to the database items by
concurrent transactions.

All lock requests are made to the concurrency-control manager. Transactions proceed only once
the lock request is granted.

Binary Locks: A Binary lock on a data item can either locked or unlocked states.

5
0
Shared/exclusive: This type of locking mechanism separates the locks based on their uses. If a
lock is acquired on a data item to perform a write operation, it is called an exclusive lock.

1. Shared Lock (S):

A shared lock is also called a Read-only lock. With the shared lock, the data item can be shared
between transactions. This is because you will never have permission to update data on the data
item.

For example, consider a case where two transactions are reading the account balance of a person.
The database will let them read by placing a shared lock. However, if another transaction wants to
update that account's balance, shared lock prevent it until the reading process is over.

2. Exclusive Lock (X):

With the Exclusive Lock, a data item can be read as well as written. This is exclusive and can't be
held concurrently on the same data item. X-lock is requested using lock-x instruction. Transactions
may unlock the data item after finishing the 'write' operation.

For example, when a transaction needs to update the account balance of a person. You can allows
this transaction by placing X lock on it. Therefore, when the second transaction wants to read or
write, exclusive lock prevent this operation.

3. Simplistic Lock Protocol

This type of lock-based protocols allows transactions to obtain a lock on every object before
beginning operation. Transactions may unlock the data item after finishing the 'write' operation.

4. Pre-claiming Locking

Pre-claiming lock protocol helps to evaluate operations and create a list of required data items
which are needed to initiate an execution process. In the situation when all locks are granted, the
transaction executes. After that, all locks release when all of its operations are over.

Two Phase Locking (2PL) Protocol

Two-Phase locking protocol which is also known as a 2PL protocol. It is also called P2L. In this
type of locking protocol, the transaction should acquire a lock after it releases one of its locks. This
locking protocol divides the execution phase of a transaction into three different parts.

• In the first phase, when the transaction begins to execute, it requires permission for the
locks it needs.
• The second part is where the transaction obtains all the locks. When a transaction releases
its first lock, the third phase starts.

5
1
 • In this third phase, the transaction cannot demand any new locks. Instead, it only releases
the acquired locks.

The Two-Phase Locking protocol allows each transaction to make a lock or unlock request in two
steps:

• Growing Phase: In this phase transaction may obtain locks but may not release any locks.
• Shrinking Phase: In this phase, a transaction may release locks but not obtain any new
lock

It is true that the 2PL protocol offers serializability. However, it does not ensure that deadlocks do
not happen.

Timestamp-based Protocols
The timestamp-based algorithm uses a timestamp to serialize the execution of concurrent
transactions. This protocol ensures that every conflicting read and write operations are executed in
timestamp order. The protocol uses the System Time or Logical Count as a Timestamp.

The older transaction is always given priority in this method. It uses system time to determine the
time stamp of the transaction. This is the most commonly used concurrency protocol.

Lock-based protocols help you to manage the order between the conflicting transactions when they
will execute. Timestamp-based protocols manage conflicts as soon as an operation is created.
Example:
Suppose there are there transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then transaction T2 and lastly Transaction T3.

5
2
Classical IPC Problem
Dining philosopher problem
Consider five philosophers who spend their lives thinking and eating. The philosophers share a
circular table surrounded by five chairs, each belonging to one philosopher. In the centre of the
table is a bowl of rice, and the table is laid with five single chopsticks. When a philosopher thinks,
she does not interact with her colleagues. From time to time, a philosopher gets hungry and tries
to pick up the two chopsticks that are closest to her (the chopsticks that are between her and her
left and right neighbours). A philosopher may pick up only one chopstick at a time. Obviously, she
cannot pick up a chopstick that is already in the hand of a neighbour. When a hungry philosopher
has both her chopsticks at the same time, she eats without releasing the chopsticks. When she is
finished eating, she puts down both chopsticks and starts thinking again.
5
3
The diningphilosophers problem is considered a classic synchronization problem neither because
of its practical importance nor because computer scientists dislike philosophers but because it is
an example of a large class of concurrency-control problems. It is a simple representation of the
need to allocate several resources among several processes in a deadlock-free and starvation-free
manner. One simple solution is to represent each chopstick with a semaphore. A philosopher tries
to grab a chopstick by executing a wait() operation on that semaphore. She releases her chopsticks
by executing the signal() operation on the appropriate semaphores.

Although this solution guarantees that no two neighbours are eating simultaneously, it nevertheless
must be rejected because it could create a deadlock. Suppose that all five philosophers become hungry
at the same time and each grabs her left chopstick. All the elements of chopstick will now be equal to
0. When each philosopher tries to grab her right chopstick, she will be delayed forever. Several possible
remedies to the deadlock problem are replaced by:

• Allow at most four philosophers to be sitting simultaneously at the table.

• Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do this,
she must pick them up in a critical section).
• Use an asymmetric solution—that is, an odd-numbered philosopher picks up first her left
chopstick and then her right chopstick, whereas an even numbered philosopher picks up her
right chopstick and then her left chopstick.

5
4
The Readers and Writers Problem

5
5
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.
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.
Code for writer process while(TRUE)
{
wait(w); /* perform the write operation */ signal(w);
}

Code for Reader process while(TRUE)

{
wait(m); //acquire lock
read_count++; if(read_count ==
1) wait(w); //release lock
signal(m); /* perform the
reading operation */ wait(m);
// acquire lock read_count--
; if(read_count == 0)
signal(w); // release lock
signal(m);
}

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

The Sleeping Barber Problem

5
6
The analogy is based upon a hypothetical barber shop with one barber. There is a barber shop
which has one barber, one barber chair, and n chairs for waiting for customers if there are any to
sit on the chair.

• If there is no customer, then the barber sleeps in his own chair.

• When a customer arrives, he has to wake up the barber.
• If there are many customers and the barber is cutting a customer’s hair, then the remaining
customers either wait if there are empty chairs in the waiting room or they leave if no chairs
are empty.

The solution to this problem includes three semaphores. First is for the customer which counts
the number of customers present in the waiting room (customer in the barber chair is not
included because he is not waiting). Second, the barber 0 or 1 is used to tell whether the barber
is idle or is working, And the third mutex is used to provide the mutual exclusion which is
required for the process to execute. In the solution, the customer has the record of the number
of customers waiting in the waiting room if the number of customers is equal to the number of
chairs in the waiting room then the upcoming customer leaves the barbershop.

When the barber shows up in the morning, he executes the procedure barber, causing him to
block on the semaphore customers because it is initially 0. Then the barber goes to sleep until
the first customer comes up.

If the chair is available then customer sits in the waiting room and increments the variable
waiting value and also increases the customer’s semaphore this wakes up the barber if he is
sleeping.
At this point, customer and barber are both awake and the barber is ready to give that person a
haircut. When the haircut is over, the customer exits the procedure and if there are no customers
in waiting room barber sleeps.

When a customer arrives, he executes customer procedure the customer acquires the mutex for
entering the critical region, if another customer enters thereafter, the second one will not be
able to anything until the first one has released the mutex. The customer then checks the chairs
in the waiting room if waiting customers are less then the number of chairs then he sits
otherwise he leaves and releases the mutex.

5
7
Algorithm for Sleeping Barber problems
Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex Seats = 1;
int FreeSeats = N;
Barber {
while(true) {
/* waits for a customer (sleeps). */
down(Customers);
/* mutex to protect the number of available seats.*/
down(Seats);
/* a chair gets free.*/
FreeSeats++;

/* bring customer for haircut.*/

up(Barber);

/* release the mutex on the chair.*/

up(Seats);
/* barber is cutting hair.*/
} }
Customer {
while(true) {
/* protects seats so only 1 customer tries to sit
in a chair if that's the case.*/ down(Seats);
//This line should not be here. if(FreeSeats >
0) {

/* sitting down.*/
FreeSeats--; /*
notify the barber. */
up(Customers);

/* release the lock */

up(Seats);

5
8
 /* wait in the waiting room if barber is busy. */
down(Barber);
// customer is having hair cut
} else {
/* release the lock */
up(Seats);
// customer leaves
}
}
}

Process Scheduling
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 −

• Job queue − This queue keeps all the processes in the system.

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

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.

6
0
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 process 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.
Dispatcher
A dispatcher is a special program which comes into play after the scheduler. When the scheduler
completes its job of selecting a process, it is the dispatcher which takes that process to the desired
state/queue. The dispatcher is the module that gives a process control over the CPU after it has
been selected by the short-term scheduler. This function involves the following:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program
Difference between the Scheduler and Dispatcher
Consider a situation, where various processes are residing in the ready queue waiting to be
executed. The CPU cannot execute all of these processes simultaneously, so the operating system
has to choose a particular process on the basis of the scheduling algorithm used. So, this procedure
of selecting a process among various processes is done by the scheduler. Once the scheduler has
selected a process from the queue, the dispatcher comes into the picture, and it is the dispatcher
who takes that process from the ready queue and moves it into the running state. Therefore, the
scheduler gives the dispatcher an ordered list of processes which the dispatcher moves to the CPU
over time. Example
There are 4 processes in the ready queue, P1, P2, P3, P4; Their arrival times are t0, t1, t2, t3
respectively. A First in First out (FIFO) scheduling algorithm is used. Because P1 arrived first, the
scheduler will decide it is the first process that should be executed, and the dispatcher will remove
P1 from the ready queue and give it to the CPU. The scheduler will then determine P2 to be the
next process that should be executed, so when the dispatcher returns to the queue for a new process,

6
1
it will take P2 and give it to the CPU. This continues in the same way for P3, and then P4.

Difference between Dispatcher and Scheduler

Dispatcher Scheduler
1. Dispatcher is a module that gives control of 1. Scheduler is something which selects a
CPU to the process selected by short term process among various processes.
scheduler.
2. There are no different types in dispatcher.It is 2. There are 3 types of scheduler i.e. Longterm,
just a code segment. Short-term, Medium-term.
3. Working of dispatcher is dependent on 3. Scheduler works independently. It works
scheduler.Means dispatcher have to wait immediately when needed.
until scheduler selects a process.
4. Dispatcher has no specific algorithm for its 4. Scheduler works on various algorithm such
implementation. as FCFS, SJF, RR etc.
5. The time taken by dispatcher is called 5. Time taken by scheduler is usually
dispatch latency. negligible. Hence we neglect it.
6. Dispatcher is also responsible for: Context 6. The only work of scheduler is selection of
Switching, Switch to user mode, Jumping processes.
to proper location when process again
restarted.

CPU-I/O Burst Cycle

The success of CPU scheduling depends on the following observed property of processes. Process
execution consists of a cycle of CPU execution and I/O wait. Processes alternate back and forth
between these two states. The execution begins with CPU burst, followed by I/O burst, then
another CPU burst and so on. The last CPU burst will end with a system request to terminate
execution rather than with another I/O burst. An I/O bound program would typically have many
short CPU bursts; a CPU bound program might have a few very long CPU bursts. The duration of
these CPU bursts are measured, which help to select an appropriate CPU scheduling algorithm.

6
2
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.
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

6
3
 • Currently used register
• Changed State
• I/O State information
• Accounting information

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

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

In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one
exists in the ready queue) must be selected for execution. There is a choice, however in
circumstances 2 and 3.
When Scheduling takes place only under circumstances 1 and 4, we say the scheduling scheme
is non-preemptive; otherwise the scheduling scheme is preemptive.
Preemptive Scheduling
In this type of Scheduling, the tasks are usually assigned with priorities. At times it is necessary to
run a certain task that has a higher priority before another task although it is running. Therefore,
the running task is interrupted for some time and resumed later when the priority task has finished
its execution.
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.
Advantages

• Preemptive scheduling method is more robust, approach so one process cannot monopolize
the CPU
• Choice of running task reconsidered after each interruption.
• Each event cause interruption of running tasks
• The OS makes sure that CPU usage is the same by all running process.
• In this, the usage of CPU is the same, i.e., all the running processes will make use of CPU
equally.
• This scheduling method also improvises the average response time.
• Preemptive Scheduling is beneficial when we use it for the multi-programming
environment.

Disadvantages

• Need limited computational resources for Scheduling

• Takes a higher time by the scheduler to suspend the running task, switch the context, and
dispatch the new incoming task.
6
5
 • The process which has low priority needs to wait for a longer time if some high priority
processes arrive continuously.

Non Preemptive Scheduling

Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps
the CPU until it releases the CPU either by terminating or by switching to the waiting state.
This scheduling method is used by the Microsoft Windows 3.1 and by the Apple Macintosh
operating systems.
It is the only method that can be used on certain hardware platforms, because It does not require
the special hardware (for example: a timer) needed for 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.
Difference between Preemptive and Non Preemptive Scheduling
Preempted Non Preemptive
1. A processor can be preempted to execute the 1. Once the processor starts its execution, it
different processes in the middle of any must finish it before executing the other. It
current process execution. can't be paused in the middle.
2. CPU utilization is more efficient compared 2. CPU utilization is less efficient compared to
to Non-Preemptive Scheduling. preemptive Scheduling.
3. Waiting and response time of preemptive 3. Waiting and response time of the
Scheduling is less. nonpreemptive Scheduling method is
higher.
4. Preemptive Scheduling is prioritized. The 4. When any process enters the state of
highest priority process is a process that is running, the state of that process is never
currently utilized. deleted from the scheduler until it finishes
its job.
5. Preemptive Scheduling is flexible. 5. Non-preemptive Scheduling is rigid.
6. Examples: - Shortest Remaining Time First, 6. Examples: First Come First Serve, Shortest
Round Robin, etc. Job First, Priority Scheduling, etc.
7. Preemptive Scheduling algorithm can be 7. In non-preemptive scheduling process
pre-empted that is the process can be cannot be Scheduled
Scheduled
8. In this process, the CPU is allocated to the 8. In this process, CPU is allocated to the
processes for a specific time period. process until it terminates or switches to
the waiting state.

6
6
 9. Preemptive algorithm has the overhead of 9. Non-preemptive Scheduling has no such
switching the process from the ready state overhead of switching the process from
to the running state and vice-versa. running into the ready state.

Scheduling Criteria
There are many different criteria to check when considering the "best" scheduling algorithm, they
are:
CPU Utilization
To make out the best use of CPU and not to waste any CPU cycle, CPU would be working most
of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from
40% (lightly loaded) to 90% (heavily loaded.)
Throughput
It is the total number of processes completed per unit time or rather say total amount of work done
in a unit of time. This may range from 10/second to 1/hour depending on the specific processes.
Turnaround Time
It is the amount of time taken to execute a particular process, i.e. The interval from time of
submission of the process to the time of completion of the process (Wall clock time).
Waiting Time
The sum of the periods spent waiting in the ready queue amount of time a process has been waiting
in the ready queue to acquire get control on the CPU.
Load Average
It is the average number of processes residing in the ready queue waiting for their turn to get into
the CPU.
Response Time
Amount of time it takes from when a request was submitted until the first response is produced.
Remember, it is the time till the first response and not the completion of process execution (final
response).
In general CPU utilization and Throughput are maximized and other factors are reduced for proper
optimization.

Scheduling Algorithm
Scheduling algorithms are mainly divided into following three categories.

1. Batch system scheduling.

6
7
 a. First Come First Served (non-preemptive, preemptive)
b. Shortest Job First (non-preemptive, preemptive)
c. Shortest Remaining Time Next (preemptive)
2. Interactive system scheduling
a. Round Robin Scheduling (preemptive)
b. Priority Scheduling (non preemptive)
c. Multilevel Queue Scheduling
d. Multilevel Feedback Queue Scheduling
3. Real time scheduling
a. Priority Fair Share Scheduling
b. Guaranteed Scheduling
c. Lottery Scheduling
d. High Response Ratio Next

1. Batch system Scheduling

Batch processing is a technique in which an Operating System collects the programs and data
together in a batch before processing starts. An operating system does the following activities
related to batch processing.
• The OS defines a job which has predefined sequence of commands, programs and data
as a single unit.
• The OS keeps a number a job in memory and executes them without any manual
information.
• Jobs are processed in the order of submission, i.e first come first served fashion.
• When a job completes its execution, its memory is released and the output for the job
gets copied into an output spool for later printing or processing.
a. First Come First Served
FCFS provides an efficient, simple and error-free process scheduling algorithm that saves
valuable CPU resources. It uses nonpreemptive scheduling in which a process is automatically
queued and processing occurs according to an incoming request or process order. FCFS derives
its concept from real-life customer service.
Let's take a look at how FCFS process scheduling works. Suppose there are three processes in
a queue: P1, P2 and P3. P1 is placed in the processing register with a waiting time of zero
seconds and 10 seconds for complete processing. The next process, P2, must wait 10 seconds
and is placed in the processing cycle until P1 is processed. Assuming that P2 will take 15
seconds to complete, the final process, P3, must wait 25 seconds to be processed. FCFS may
not be the fastest process scheduling algorithm, as it does not check for priorities associated
with processes. These priorities may depend on the processes' individual execution times.
Characteristics
• Processes are scheduled in the order they are received.
• Once the process has the CPU, it runs to completion.
• Easily implemented, by managing a simple queue or by storing time the process was
received.
• Fair to all processes.
Problems

6
8
 • No guarantee of good response time. Large average waiting time.
Example 1
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 0, and given Burst Time, let's find the average waiting time using the
FCFS scheduling algorithm.
Process Burst time
P1 21
P2 3
P3 6
P4 2

Solution
Gannt chart for the above processes
P1 P2 P3 P4
0 21 24 30 32
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 21-0 =21 ms 21-21 = 0
P2 24-0 =24 ms 24-3 = 21
P3 30-0 = 30 ms 30-6 = 24
P4 32-0 = 32 ms 32-2 = 30

Total waiting time: (0+21+24+30) = 75 ms

Average waiting time: 75/4 = 18.75 ms
Total turnaround time: (21+24+30+32) = 107 ms
Average turnaround time: 107/4 = 26.75 ms

Example 2
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 0, 2, 2 and 3 respectively and given Burst Time, let's find the average
waiting time using the FCFS scheduling algorithm.
Process Arrival time Burst time
P1 0 ms 21
P2 2 ms 3
P3 2 ms 6

6
9
 P4 3 ms 2

Solution
Gannt chart for the above processes
P1 P2 P3 P4
0 21 24 30 32
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 21-0 =21 ms 21-21 = 0
P2 24-2 =22 ms 22-3 = 19
P3 30-2 = 28 ms 28-6 = 22
P4 32-3 = 29 ms 29-2 = 27

Total waiting time: (0+19+22+27) = 68 ms

Average waiting time: 68/4 = 17 ms
Total turnaround time: (21+22+28+29) = 100 ms
Average turnaround time: 100/4 = 25 ms
Example 3
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order with Arrival Time 0, 1, 5 and 6 respectively and given Burst Time. let's find the average
waiting time using the FCFS scheduling algorithm.
Process Arrival time Burst time
P1 0 ms 2
P2 1 ms 2
P3 5 ms 3
P4 6 ms 4

Solution
Gannt chart for the above processes
P1 P2 P3 P4
0 2 4 5 8 12
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 2-0 =2 ms 2-2 = 0
P2 4-1 =3 ms 3-2 = 1
P3 8-5 = 3 ms 3-3 = 0
P4 12-6 = 6 ms 6-4 = 2

7
0
Total waiting time: (0+1+0+2) = 3 ms
Average waiting time: 3/4 = 0.75 ms
Total turnaround time: (2+3+3+6) = 14 ms
Average turnaround time: 14/4 = 3.5 ms

b. Shortest job first

In the FCFS, we saw if a process is having a very high burst time and it comes first then the other
process with a very low burst time have to wait for its turn. So, to remove this problem, we come
with a new approach i.e. Shortest Job First or SJF.
In this technique, the process having the minimum burst time at a particular instant of time will be
executed first. It is a non-preemptive approach i.e. if the process starts its execution then it will be
fully executed and then some other process will come.
Shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process
with the smallest execution time to execute next.

Characteristics
• The processing time are known in advanced.
• SJF selects the process with shortest expected processing time. In case of the tie FCFS
scheduling is used.
• The decision policies are based on the CPU burst time.

Advantages

• Reduces the average waiting time over FCFS. Favors shorts jobs at the cost of long jobs.

Problems

• It may lead to starvation if only short burst time processes are coming in the ready state.
• Estimation of run time to completion.
• Accuracy
• Not applicable in timesharing system.
Example 1
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 0, and given Burst Time, let's find the average waiting time using the SJF
scheduling algorithm.
Process Burst time
P1 21
P2 3
P3 6
P4 2

7
1
Solution
Gantt chart for the above processes
P4 P2 P3 P1
0 2 5 11 32

As in the Gantt chart, the process P4 will be picked up first as it has the shortest burst time, then
P2, followed by P3 and at last P1.
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 32-0 = 32 ms 32-21 = 11
P2 5-0 =5 ms 5-3 = 2
P3 11-0 = 11 ms 11-6 = 5
P4 2-0 =2 ms 2-2 = 0

Total waiting time: (0+2+5+11) = 18 ms

Average waiting time: 18/4 = 4.5 ms
Total turnaround time: (2+5+11+32) = 50 ms
Average turnaround time: 50/4 = 12.5 ms

Example 2
Consider the processes P1, P2, P3, P4 given in the below table with arrival time 1, 2, 1 and 4
respectively and given Burst Time, let's find the average waiting time using the SJF scheduling
algorithm.
Process Arrival Time Burst time
P1 1 3
P2 2 4
P3 1 2
P4 4 4

Solution
Gantt chart for the above processes
P3 P1 P2 P4
0 1 3 6 10 14
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P3 3-1 =2 ms 2 -2 = 0
P1 6-1 =5 ms 5-3 = 2

7
2
 P2 10-2 = 8 ms 8-4 = 4
P4 14-4 = 10 ms 10-4 = 6

Total waiting time: (0+2+4+6) = 12 ms

Average waiting time: 12/4 = 3 ms
Total turnaround time: (2+5+8+10) = 25 ms Average
turnaround time: 25/4 = 6.25 ms

c. Shortest Remaining Time Next

It is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process
with the smallest amount of time remaining until completion is selected to execute. Since the
currently executing process is the one with the shortest amount of time remaining by definition,
and since that time should only reduce as execution progresses, processes will always run until
they complete or a new process is added that requires a smaller amount of time.
Shortest remaining time is advantageous because short processes are handled very quickly. The
system also requires very little overhead since it only makes a decision when a process completes
or a new process is added, and a new process is added the algorithm only needs to compare the
currently executing process with the new process, ignoring all other processes currently waiting to
execute.
Characteristics
• Low average waiting time than shortest job first.
• Useful in timesharing
Problem
• Very high overhead than shortest job first.
• Requires additional computation.
• Favors short jobs, long jobs can be victims of starvation.
Example 1
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 0, 1, 2 and 3 respectively and given Burst Time, let's find the average
waiting time and average turnaround time using the shortest remaining time next scheduling
algorithm.
Process Arrival time Burst time
P1 0 ms 21
P2 1 ms 3
P3 2 ms 6
P4 3 ms 2

Solution
Gantt chart for the above processes
7
3
 P1 P2 P4 P3 P1
0 1 4 6 12 32
As it is seen in the Gantt chart above, as P1 arrives first, hence it’s execution starts immediately,
but just after 1 ms, process P2 arrives with a burst time of 3 ms which is less than the burst time of
P1, hence the process P1 (1 ms done, 20 ms left) is preempted and process P2 is executed.
As P2 is getting executed, after 1ms, P3 arrives, but it has a burst time greater than that of P2,
hence execution of P2 continues. But after another millisecond, P4 arrives with a burst time of
2ms, as a result P2 (2ms done, 1ms left). Since remaining time of P2 is smaller than P4, P2
continues. After the completion of P2, process P4 is picked up and finishes, then P3 will get
executed and at last P1.
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 32-0 =32 ms 32 -21 = 11
P2 4-1 =3 ms 3-3 = 0
P3 12-2 = 10 ms 10-6 = 4
P4 6-3 = 3 ms 3-2 = 1

Total waiting time: (11+0+4+1) = 16 ms

Average waiting time: 16/4 = 4 ms
Total turnaround time: (32+3+10+3) = 48 ms
Average turnaround time: 48/4 = 12 ms
Example 2
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 1, 1, 2 and 3 respectively and given Burst Time, let's find the average
waiting time and average turnaround time using the shortest remaining time next scheduling
algorithm.
Process Arrival time Burst time
P1 1 ms 6
P2 1 ms 8
P3 2 ms 7
P4 3 ms 3

Solution
Gantt chart for the above processes
P1 P4 P1 P3 P2
0 1 3 6 10 17 25
In the above example, at time 1ms, there are two processes i.e. P1 and P2. Process P1 is having
burst time as 6ms and the process P2 is having 8ms. So, P1 will be executed first. Since it is a
preemptive approach, so we have to check at every time quantum. At 2ms, we have three processes
i.e. P1 (5ms remaining), P2 (8ms) and P3 (7ms). Out of these three, P1
7
4
is having the least burst time, so it will continue its execution. After 3ms, we have four processes
i.e. P1 (4ms remaining), P2 (8ms), P3 (7ms) and P4 (3ms). Out of these four, P4 is having the least
burst time, so it will be executed. The process P4 keeps on executing for the next 3ms because it
is having the shortest burst time. After 6ms we have 3 processes i.e P1 (4ms remaining), P2 (8ms),
and P3 (7ms). So P1 will be selected and executed. This process of time comparison will continue
until we have all the processes executed. So waiting and turnaround time of the processes will be:
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 10-1 =9 ms 9 -6 = 3
P2 25-1 =24 ms 24-8 = 16
P3 17-2 = 15 ms 15-7 = 8
P4 6-3 = 3 ms 3-3 = 0

Total waiting time: (3+16+8+0) = 27 ms

Average waiting time: 27/4 = 6.75 ms
Total turnaround time: (9+24+15+3) = 51 ms
Average turnaround time: 51/4 = 12.75 ms

2. Interactive System Scheduling

a. Round Robin Scheduling

In this algorithm the process is allocated the CPU for the specific time period called time slice or
quantum, which is normally of 10 to 100 milliseconds. If the process completes its execution within
this time slice, then it is removed from the queue otherwise it has to wait for another time slice.
Preempted process is placed at the back of the ready list.

In this approach of CPU scheduling, we have a fixed time quantum and the CPU will be allocated
to a process for that amount of time only at a time. For example, if we are having three process P1,
P2 and P3 and our time quantum is 2ms, then P1 will be given 2ms for its execution, then P2 will
be given 2ms, then P3 will be given 2ms. After one cycle, again P1 will be given 2ms, and then P2
will be given 2ms and so on until the processes complete its execution. Advantages

• Fair allocation of CPU across the process.

• Used in timesharing system.
• Low average waiting time when process lengths vary widely.
• Poor average waiting time when process lengths are identical.

Disadvantages

• We have to perform a lot of context switching.

• Time consuming scheduling for small quantum.

7
5
Quantum size: If the quantum is very large, each process is given as much time as needs for
completion, Round Robin degenerate to First Come First Serve policy. If quantum is very small,
system bus at just switching from one process to another process, the overhead of contextswitching
causes the system efficiency degrading.
Example 1
Consider the processes P1, P2, P3 given in the below table, arrives for execution in the same order,
with Arrival Time 0 and given Burst Time, let's find the average waiting time and average
turnaround time using the Round Robin scheduling algorithm with quantum size = 2.

Process Burst time

P1 10
P2 5
P3 8

Solution
Gantt chart for the above processes
Ready queue P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P3 P1

Running queue P1P2 P3 P1 P2 P3 P1 P2 P3 P1 P3 P1

0 2 4 6 8 10 12 14 15 17 19 21 23
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 23-0 =23 ms 23-10 = 13
P2 15-0 =15 ms 15-5 = 10
P3 21-0 = 21 ms 21-8 = 13

Total waiting time: (13+10+13) = 36 ms

Average waiting time: 36/3 = 12 ms
Total turnaround time: (23+15+21) = 59 ms
Average turnaround time: 59/3 = 19.66 ms
Example 2
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same
order, with Arrival Time 0, 1, 2, 4 respectively and given Burst Time, let's find the average waiting
time and average turnaround time using the Round Robin scheduling algorithm with quantum size
= 2. How many time context switches occurs?
Process Arrival time Burst time
P1 0 5

7
6
 P2 1 4
P3 2 2
P4 4 1

Solution
Gantt chart for the above processes
Ready Queue P1 P1P3P2 P2P4P1P3 P2P4P1 P1P2P4 P1P2 P1

Running Queue P1 P2 P3 P1 P4 P2 P1
0 2 4 6 8 9 11 12
Here context switches occur for 6 times.
Process Turnaround time = Waiting time = Response Time=
Completion Time - Turn Around Time – Burst CPU First time – Arrival
Arrival Time Time Time
P1 12-0 =12 ms 12-5 = 7 0-0=0
P2 11-1 =10 ms 10-4 = 6 2-1=1
P3 6-2 = 4 ms 4-2 = 2 4-2=2
P4 9-4 = 5 ms 5-1 = 4 8-4=4

Total waiting time: (7+6+2+4) = 19 ms

Average waiting time: 19/4 = 4.75 ms
Total turnaround time: (12+10+4+5) = 31 ms
Average turnaround time: 31/4 = 7.75 ms
Total response time: (0+1+2+4) = 7 ms Average
response time: 7/4 = 1.75 ms

b. Priority scheduling

In this scheduling algorithm the priority is assigned to all the processes and the process with highest
priority executed first. Priority assignment of process is done on the basis of internal factor such
as CPU and memory requirements or external factor such as user’s choice. It is just used to identify
which process is having a higher priority and which process is having a lower priority. For
example, we can denote 0 as the highest priority process and 100 as the lowest priority process.
Also, the reverse can be true i.e we can denote 100 as the highest priority and 0 as the lowest
priority.
7
7
Advantages

• Highest priority processes like system processes are executed first.

Disadvantages

• It can lead to starvation if only higher priority process comes into the ready state. Low
priority processes may never execute.
• If the priorities of more two processes are the same, then we have to use some other
scheduling algorithm.

Example 1

Find average waiting time and average turnaround time of following four processes with their
arrival time, burst time and priority as below.
Process Arrival time Burst time Priority
P1 0 5 1
P2 1 3 2
P3 2 8 1
P4 3 6 3
Take higher priority number as high priority.

Solution
Gantt chart for the above processes
Ready Queue P1 P1P2 P1 P2P3 P1 P2P3P4 P1 P2P3 P1P3 P3

Running Queue P1 P2 P4 P2 P1 P3

0 1 2 3 9 10 14 22
In the above example, at 0ms, we have only one process P1. So P1 will execute for 1ms. After 1ms
P2 arrives in the ready queue among P1and P2, P2 has higher priority so it preempts P1. At 2ms
P3 arrives at ready queue. Among P1, P2 and P3, P2 has higher priority so it continues, at 3ms P4
arrives at the ready queue and it preempts P2 because it has higher priority. At 9ms P4 completes
and P2 continues and at 10ms P2 completes and P1 continues. At 14ms P1 completes and P3
continues and at 22ms P3 completes. The waiting and turnaround time of processes will be:
Process Turnaround time = Waiting time =
Completion Time - Turn Around Time – Burst
Arrival Time Time
P1 14-0 =14 ms 14-5 = 9
P2 10-1 =9 ms 9-3 = 6

7
8
 P3 22-2 = 20 ms 20-8 = 12
P4 9-3 = 6 ms 6-6 = 0

Total waiting time: (9+6+12+0) = 27 ms

Average waiting time: 27/4 = 6.75 ms
Total turnaround time: (14+9+20+6) = 49 ms
Average turnaround time: 49/4 = 12.25 ms

c. Multiple queues (Multilevel Queue Scheduling)

It may happen that processes in the ready queue can be divided into different classes where
each class has its own scheduling needs. For example, a common division is a foreground
(interactive) process and background (batch) processes. These two classes have different
scheduling needs. For this kind of situation Multilevel Queue Scheduling is used. Now let us
see how it works.
Ready Queue is divided into separate queues for each class of processes. For example, let us
take three different types of process System processes, Interactive processes and Batch
Processes. All three processes have their own queue. Now, look at the below figure.

High Priority System Processes Queue 1

Queue 2 Interactive Processes

Batch Processes
Low Priority Queue 3

Fig: Multiple queue

All three different types of processes have their own queue. Each queue has its own Scheduling
algorithm. For example, Queue 1 and Queue 2 uses Round Robin while Queue 3 can use FCFS to
schedule their processes.
Example : Consider below table of four processes under multilevel queue scheduling. Queue
number denotes the queue of the process.
Process Arrival Time CPU Brust Time Queue Number
P1 0 5 1
P2 0 3 2
P3 0 8 2
P4 0 6 1

Solution:
In the above example, we have two queues, i.e Queue 1 and Queue 2. Queue 1 is having higher
priority and Queue 1 is using the FCFS approach and Queue 2 is using the round-robin approach
(time quantum =2ms). Below is the Gantt chart of the problem.

7
9
 P1 P4 P2 P3 P2 P3 P3 P3
0 5 11 13 15 16 18 20 22
Since the priority of Queue 1 is higher, so Queue 1 will be executed first. In the Queue 1, we have
two processes i.e. P1 and P4 and we are using FCFS. So, P1 will be executed followed by P4.
Now, the job of the Queue 1 is finished. After this, the execution of the processes of Queue2 will
be started by using the round-robin approach.
d. Multilevel Feedback Queue Scheduling
It allows the process to move in between queues. The idea is to separate processes according to the
characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-
priority queue. Similarly, a process that waits too long in a lower-priority queue may be moved to
a higher priority queue. This form of aging prevents starvation.
Example: Consider a system which has CPU Bound process which requires burst time of 40 times
units. Multilevel feedback queue scheduling is used. The time quantum is 2 units and it will be
incremented by 5 units in each level. How many times the process will be interrupted and in which
queue process will complete the execution?
Solution:
Queue 1, Quantum=2 First time, Interrupt,
Burst time remaining =38

Queue 2, Quantum=7
Second time, Interrupt, Burst time remaining =31

Queue 3, Quantum=12
Third time, Interrupt, Burst time remaining =19

Queue 4, Quantum=17
Fourth time, Interrupt, Burst time remaining =2

Queue 5, Quantum=22

Hence from above figure process will be interrupted in 4 times and in 5th queue the process will
complete the execution.

3. Realtime System Scheduling

A real-time scheduling system is composed of the scheduler, clock and the processing hardware
elements. In a real-time system, a process or task has schedulability; tasks are accepted by a
realtime system and completed as specified by the task deadline depending on the characteristics
of the scheduling algorithm. Modeling and evaluation of a real-time scheduling system concern is
on the analysis of the algorithm capability to meet a process deadline. A deadline is defined as the
time required for a task to be processed. For example, in a real-
8
0
time scheduling algorithm a deadline could be set to 5 nano-seconds. In a critical operation the
task must be processed in the time specified by the deadline (i.e. five nano-seconds). A task in a
real-time system must be completed neither too early nor too late. A system is said to be
unschedulable when tasks cannot meet the specified deadlines. A task can be classified as either a
periodic or a periodic process.

The criteria of a real-time can be classified as hard, firm or soft. The scheduler set the algorithms
for executing tasks according to a specified order. There are multiple mathematical models to
represent a scheduling System; most implementations of real-time scheduling algorithm are
modeled for the implementation of uniprocessors or multiprocessors configurations. In the
algorithms for a real-time scheduling system, each task is assigned a description, deadline and an
identifier (indicating priority). The selected scheduling algorithm determines how priorities are
assigned to a particular task. A real-time scheduling algorithm can be classified as static or
dynamic. For a static scheduler, task priorities are determined before the system runs. A dynamic
scheduler determines task priorities as it runs. Tasks are accepted by the hardware elements in a
real-time scheduling system from the computing environment and processed in real-time. An
output signal indicates the processing status. A task deadline indicates the time set to complete for
each task.
a. Priority Fair share scheduling

Fair share scheduling is a scheduling algorithm for computer operating systems in which the
CPU usage is equally distributed among system users or groups as opposed to equal distribution
among processes.

One common method of logically implementing the fair-share scheduling strategy is to recursively
apply for the round-robin scheduling strategy at each level of abstraction (processes, users, groups,
etc). The time quantum required by round-robin is arbitrary, as any equal division of time will
produce the same results.

Example

If four users (A, B, C, D) are concurrently executing one process each, the scheduler will logically
divide the available CPU cycles such that each user gets 25% of the whole (100% /4 =25%). If
user B starts a second process, each user will still receive 25% of the total cycles, but each of user
B’s processes will now be attributed 12.5% of the total CPU cycles each, totaling user B’s fair
share of 25%. On the other hand, if a new user starts a process on the system, the scheduler will
reapportion the available CPU cycles such that each user gets 20% of the whole (100% /5=20%).

Another layer of abstraction allows us to partition users into groups, and apply the fair share
algorithm to the groups as well. In this case, the available CPU cycles are divided first among the
groups, then among the users within the groups, and then among the processes for that user. For
example, if there are three groups (1,2,3) containing three, two and four users respectively, the
available CPU cycles will be distributed as follows:

100% /3 groups = 33.3% per group

Group 1: (33.3% /3 users) =11.1% per user

8
1
Group 2: (33.3% /2 users) = 16.7% per user Group

3: (33.3% /4 users) = 8.3% per user

b. Guaranteed Scheduling

A scheduling algorithm used in multitasking operating systems that guarantees fairness by

monitoring the amount of CPU time spent by each user and allocating resources accordingly.

It makes real promises to the users about performance. If there are n users logged in while you are
working, you will receive about 1/n of the CPU power. Similarly, on a single-user system with n
processes running, all things being equal, each one should get 1 /n of the CPU cycles. To make
good on this promise, the system must keep track of how much CPU each process has had since
its creation. CPU time consumed to the CPU time entitled. A ratio of 0.5 means that a process has
only had half of what it should have had, and a ration of 2.0 means that a process has had twice as
much as it was entitled to. The algorithm is then to run the process with the lowest ratio until its
ratio has moved above its closest competitor.

c. Lottery Scheduling

Lottery Scheduling is type of process scheduling, somewhat different from other scheduling.
Processes are scheduled in a random manner. Lottery scheduling can be preemptive or
nonpreemptive. It also solves the problem of starvation. Giving each process at least one lottery
ticket guarantees that it has non-zero probability of being selected at each scheduling operation.

In this scheduling every process has some tickets and scheduler picks a random ticket and process
having that ticket is the winner and it is executed for a time slice and then another ticket is picked
by the scheduler. These tickets represent the share of processes. A process having a higher number
of tickets give it more chance to get chosen for execution.

Example

If we have two processes A and B having 60 and 40 tickets respectively out of total 100 tickets.
CPU share of A is 60% and that of B is 40%. These shares are calculated probabilistically and not
deterministically.

Explanation:

1. We have two processes A and B. A has 60 tickets (ticket number 1 to 60) and B have
40 tickets (ticket no 61 to 100).
2. Scheduler picks a random number from 1 to 100. If the picked no. is from 1 to 60 then
A is executed otherwise B is executed.
3. An example of 10 tickets picked by Scheduler may look like this-
Ticket number: {73 82 23 45 32 87 49 39 12 09}
Resulting schedule: {B B A A A B A A A A}
4. A is executed 7 times and B is executed 3 times. As you can see that A takes 70% of
CPU and B takes 30% of CPU which is not the same as what we need as we need A to
have 60% of CPU and B should have 40% of CPU. This
8
2
 happens because shares are calculated probabilistically but in a long run (i.e. when no.
of tickets picked is more than 100 or 1000) we can achieve a share percentage of
approx.. 60 and 40 for A and B respectively.
d. Highest Response Ratio Next (HRN)
HRN is non-preemptive scheduling algorithm. In Shortest Job First scheduling, priority is
given to shortest job, which may sometimes indefinite blocking of longer job. HRN Scheduling
is used to correct this disadvantage of SJF. For determining priority, not only the job’s service
time but the waiting time is also considered. In this algorithm, dynamic priorities are used
instead of fixed priorities. Dynamic priorities in HRN are calculated as, Priority
= (waiting time + service time) /service time.
So, shortest job get preference over longer processes because service time appears in the
denominator. Longer jobs that have been waiting for long period are also give favorable
treatment because waiting time is considered in numerator.
Steps of HRN implementation
1. Input the number of processes, their arrival time and burst times.
2. Sort them according to their arrival time.
3. At any given time calculate the response ratios and select the appropriate process to be
scheduled.
4. Calculate the turnaround time as
Turnaround = completion time – arrival time.
5. Calculate the waiting time as
Waiting time = turnaround time – burst time
6. Turnaround time divided by the burst time gives the normalized turnaround time.
7. Sum up the waiting and turnaround times of all processes and divide by the number of
processes to get the average waiting and turnaround time.

Example:

Process Arrival time Burst time

P1 0 ms 4 ms

P2 2 ms 5 ms

P3 4 ms 3 ms

P4 6 ms 6 ms

P5 8 ms 3 ms

Solution

P1 P2 P3 P5 P4
0 4 9 12 15 21

Explanation
8
3
At time t=0, only the process P1 is available in the ready queue. So, process P1 executes
till its completion. At time t=4, only the process P2 and P3 are available in the ready queue.
So, we have to calculate the response ratio. The process which has the highest response
ratio will be executed next.

Response Ratio is,

Response Ratio of P2 = [(4-2)+5]/5 = 1.40

Response Ratio of P3 = [(4-4)+3]/3 = 1

Process P2 has highest response ratio so it will be selected for execution. After the
completion of execution process P2, there are three processes P3, P4 and P5 are in the
ready queue.

So, the Response Ratio for processes P3, P4 and P5 are,

Response Ratio of P3 = [(9-4)+3]/3 = 2.66

Response Ratio of P4 = [(9-6)+6]/6 = 1.50

Response Ratio of P5 = [(9-8)+3]/3 = 1.33

Process P3 has highest response ratio so it will be selected for execution. After the
completion of execution of process P3, there are three processes P4 and P5 are in the ready
queue. So, the Response Ratio for processes P4 and P5 are,

Response Ratio of P4 = [(12-6)+6]/6 = 2

Response Ratio of P5 = [(12-8)+3]/3 = 2.33

Process P5 has highest response ratio so it will be executed next. After the completion of
the execution of process P5, there are only process P4 in the ready queue. So, it will be
executed next.

Advantages

• Its performance is better than SJF scheduling.

• It limits the waiting time of longer jobs and also supports shorter jobs.

Disadvantages

• It can’t be implemented practically.

• This is because the burst time of all the processes cannot be known in

advance. Exercise 1

8
4
For the process listed in following table, draw Gantt chart illustrating their execution and calculate
average waiting time and turnaround time using:

a. First Come First Served

b. Shortest Job First
c. Priority
d. Round Robin (2ms Quantum)
Process Burst Priority
P1 8 4
P2 6 1
P3 1 2
P4 9 2
P5 3 3
Solution:

Gantt chart for First Come First Serve Scheduling

P1 P2 P3 P4 P5
0 8 14 15 24 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 8-0 = 8 8-8 = 0
P2 14-0 = 14 14-6 = 8
P3 15-0 = 15 15-1 = 14
P4 24-0 = 24 24-9 = 15
P5 27-0 = 27 27-3 = 24

Total waiting time: (0+8+14+15+24) = 61 ms

Average waiting time: 61/5 = 12.2 ms
Total turnaround time: (8+14+15+24+27) = 88 ms
Average turnaround time: 88/5 = 17.6 ms

Gantt chart for Shortest Job First Scheduling

P3 P5 P2 P1 P4
0 1 4 10 18 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 18-0 = 18 18-8 = 10
P2 10-0 = 10 10-6 = 4
P3 1-0 = 1 1-1 = 0
P4 27-0 = 27 27-9 = 18
P5 4-0 = 4 4-3 = 1

8
5
Total waiting time: (10+4+0+18+1) = 33 ms
Average waiting time: 33/5 = 6.6 ms
Total turnaround time: (18+10+1+27+4) = 60 ms
Average turnaround time: 60/5 = 12 ms
Gantt chart for Priority Scheduling
P2 P3 P4 P5 P1
0 6 7 16 19 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 27-0 = 27 27-8 = 19
P2 6-0 = 6 6-6 = 0
P3 7-0 = 7 7-1 = 6
P4 16-0 = 16 16-9 = 7
P5 19-0 = 19 19-3 = 16

Total waiting time: (19+0+6+7+16) = 48 ms

Average waiting time: 48/5 = 9.6 ms
Total turnaround time: (27+6+7+16+19) = 75 ms
Average turnaround time: 75/5 = 15 ms
Gantt chart for Round Robin Scheduling (2ms Quantum)
P1 P2 P3 P4 P5 P1 P2 P4 P5 P1 P2 P4 P1 P4
0 2 4 5 7 9 11 13 15 16 18 20 22 24 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 24-0 = 24 24-8 = 16
P2 20-0 = 20 20-6 = 14
P3 5-0 = 5 5-1 = 4
P4 27-0 = 27 27-9 = 18
P5 16-0 = 16 16-3 = 13

Total waiting time: (16+14+4+18+13) = 65 ms

Average waiting time: 65/5 = 13 ms
Total turnaround time: (24+20+5+27+16) = 92 ms
Average turnaround time: 92/5 = 18.4 ms

Exercise 2
8
6
For the process listed in following table, draw Gantt chart illustrating their execution and calculate
average waiting time and turnaround time using:

a. First Come First Served

b. Shortest Job First
c. Priority
d. Round Robin (2ms Quantum)
Process Burst Priority Arrival Time
P1 8 4 0
P2 6 1 2
P3 1 2 2
P4 9 2 1
P5 3 3 3
Solution:

Gantt chart for First Come First Served Scheduling

Ready Queue P1 P5P3P2P4

0 8

Running Queue P1 P4 P2 P3 P5
0 8 17 23 24 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 8-0 = 8 8-8 = 0
P2 23-2 = 21 21-6 = 15
P3 24-2 = 22 22-1 = 21
P4 17-1 = 16 16-9 = 7
P5 27-3 = 24 24-3 = 21

Total waiting time: (0+15+21+7+21) = 64 ms

Average waiting time: 64/5 = 12.8 ms
Total turnaround time: (8+21+22+16+24) = 91 ms
Average turnaround time: 91/5 = 18.2 ms
Gantt chart for Shortest Job First
P1 P3 P5 P2 P1 P4
0 2 3 6 12 18 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 18-0 = 18 18-8 = 10
P2 12-2 = 10 10-6 = 4

8
7
 P3 3-2 = 1 1-1 = 0
P4 27-1 = 26 26-9 = 17
P5 6-3 = 3 3-3 = 0

Total waiting time: (10+4+0+17+0) = 31 ms

Average waiting time: 31/5 = 6.2 ms
Total turnaround time: (18+10+1+26+3) =58 ms
Average turnaround time: 58/5 = 11.6 ms

Gantt chart for Priority Scheduling

P1 P4 P2 P3 P4 P5 P1
0 1 2 8 9 17 20 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 27-0 = 27 27-8 = 19
P2 8-2 = 6 6-6 = 0
P3 9-2 = 7 7-1 = 6
P4 17-1 = 16 16-9 = 7
P5 20-3 = 17 17-3 = 14

Total waiting time: (19+0+6+7+14) = 46 ms

Average waiting time: 46/5 = 9.2 ms
Total turnaround time: (27+6+7+16+17) =73 ms
Average turnaround time: 73/5 = 14.6 ms

Gantt chart for Round Robin (2ms Quantam)

P1 P4 P2 P3 P1 P5 P4 P2 P1 P5 P4 P2 P1 P4
0 2 4 6 7 9 11 13 15 17 18 20 22 24 27
Process Turnaround time = Waiting time =
Completion Time- Arrival Time Turn Around Time – Burst Time
P1 24-0 = 24 24-8 = 16
P2 22-2 = 20 20-6 = 14
P3 7-2 = 5 5-1 = 4
P4 27-1 = 26 26-9 = 17
P5 18-3 = 15 15-3 = 12

Total waiting time: (16+14+4+17+12) = 63 ms

Average waiting time: 63/5 = 12.6 ms
8
8
Total turnaround time: (24+20+5+26+15) =90 ms
Average turnaround time: 90/5 = 18 ms

Unit-4
Deadlocks
Introduction
Deadlock is a situation where a set of processes are blocked because each process is holding a
resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on same track and there is
only one track, none of the trains can move once they are in front of each other. Similar situation
occurs in operating systems when there are two or more processes hold some resources and wait
for resources held by other(s). 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.

System Model

A system model or structure consists of a fixed number of resources to be circulated among some
opposing processes. The resources are then partitioned into numerous types, each consisting of
some specific quantity of identical instances. Memory space, CPU
8
9
 cycles, directories and files, I/O devices like keyboards, printers and CD-DVD drives are prime
examples of resource types. When a system has 2 CPUs, then the resource type CPU got two
instances.
Under the standard mode of operation, any process may use a resource in only the belowmentioned
sequence:

1. Request: When the request can't be approved immediately (where the case may be when another
process is utilizing the resource), then the requesting job must remain waited until it can obtain
the resource.
2. Use: The process can run on the resource (like when the resource is a printer, its job/process is
to print on the printer).
3. Release: The process releases the resource (like, terminating or exiting any specific process).
System Resources: Preemptable and Nonpreemptable Resources

A preemptable resource is one that can be taken away from the process with no ill effects. Memory
is an example of a preemptable resource. On the other hand, a nonpreemptable resource is one that
cannot be taken away from process (without causing ill effect). For example, CD resources are not
preemptable at an arbitrary moment.Reallocating resources can resolve deadlocks that involve
preemptable resources. Deadlocks that involve nonpreemptable resources are difficult to deal with.

Conditions for Resource Deadlocks

A deadlock state can occur when the following four circumstances hold simultaneously within a
system:
1. Mutual exclusion: At least there should be one resource that has to be held in a non-sharable
manner; i.e., only a single process at a time can utilize the resource. If other process demands
that resource, the requesting process must be postponed until the resource gets released. Printer
is an example of a resource that can be used by only one process at a time.
2. Hold and wait: There must exist a process which holds some resource and waits for another
resource held by some other process.
3. No preemption: Once the resource has been allocated to the process, it can not be preempted.
It means resource can not be snatched forcefully from one process and given to the other process.
4. Circular wait: All the processes must wait for the resource in a cyclic manner where the last
process waits for the resource held by the first process.

9
0
Deadlock Modeling
Holt (1972) showed how these four conditions can be modeled using directed graphs. The graphs
have two kinds of nodes: processes, shown as circles, and resources, shown as squares. A directed
arc from a resource node (square) to a process node (circle) means that the resource has previously
been requested by, granted to, and is currently held by that process. In Fig (a), resource R is
currently assigned to process A.
A directed arc from a process to a resource means that the process is currently blocked waiting for
that resource. In Fig.(b), process B is waiting for resource S. In Fig.(c) we see a deadlock: process
C is waiting for resource T, which is currently held by process D. Process D is not about to release
resource T because it is waiting for resource U, held by C. Both processes will wait forever. A
cycle in the graph means that there is a deadlock involving the processes and resources in the cycle
(assuming that there is one resource of each kind). In this example, the cycle is C T D U
C.

Resource allocation graphs. (a) Holding a resource. (b) Requesting a resource. (c) Deadlock.

The operating system is free to run any unblocked process at any instant, so it could decide to run
A until A finished all its work, then run B to completion, and finally run C.
This ordering does not lead to any deadlocks (because there is no competition for resources) but it
also has no parallelism at all. In addition to requesting and releasing resources, processes compute
and do I/O. When the processes are run sequentially, there is no possibility that while one process
is waiting for I/O, another can use the CPU. Thus, running the processes strictly sequentially may
not be optimal. On the other hand, if none of the processes does any I/O at all, shortest job first is
better than round robin, so under some circumstances running all processes sequentially may be
the best way.

9
1
The resource requests might occur in the order of Fig.(d). If these six requests are carried out in
that order, the six resulting resource graphs are as shown in Fig.(e)–(j). After request 4 has been
made, A blocks waiting for S, as shown in Fig.(h). In the next two steps B and C also block,
ultimately leading to a cycle and the deadlock of Fig.(j).

The operating system is not required to run the processes in any special order. In particular, if
granting a particular request might lead to deadlock, the operating system can simply suspend the
process without granting the request (i.e., just not schedule the process) until it is safe. In above
Fig. if the operating system knew about the impending deadlock, it could suspend B instead of
granting it S. By running only A and C, we would get the requests and
9
2
releases of Fig.(k) instead of Fig.(d). This sequence leads to the resource graphs of Fig.(l)–(q),
which do not lead to deadlock. After step (q), process B can be granted S because A is finished and
C has everything it needs. Even if B blocks when requesting T, no deadlock can occur. B will just
wait until C is finished.

Deadlock ignorance (Ostrich Algorithm)

When storm approaches, an ostrich puts his head in the sand (ground) and pretend (imagine) that
there is no problem at all. If deadlocks occur on the average once every five years, but system
crashes due to hardware failures and operating system bugs occur once a week, most engineers
would not be willing to pay a large penalty in performance or convenience to eliminate deadlocks.
In these types of systems, the user has to simply restart the computer in the case of deadlock.
Windows and Linux are mainly using this approach.

Method of Handling Deadlocks

There are mainly four methods for handling deadlock.

1. Deadlock prevention
2. Deadlock avoidance
• Banker’s algorithm
3. Deadlock detection
• Resource allocation graph
4. Recovery from deadlock
1. Deadlock prevention
Deadlock has following characteristics
1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait
We can prevent Deadlock by eliminating any of the above four conditions.

Eliminate Mutual Exclusion Condition

Mutual section from the resource point of view is the fact that a resource can never be used by
more than one process simultaneously which is fair enough but that is the main reason behind the
deadlock. If a resource could have been used by more than one process at the same time then the
process would have never been waiting for any resource.

Eliminate Hold and Wait Condition

Hold and wait condition lies when a process holds a resource and waiting for some other resource
to complete its task. Deadlock occurs because there can be more than one process which are
holding one resource and waiting for other in the cyclic order.
However, we have to find out some mechanism by which a process either doesn't hold any resource
or doesn't wait. That means, a process must be assigned all the necessary resources before the
execution starts. A process must not wait for any resource once the execution has been started.

9
3
Eliminate No-Preemption Condition

One protocol is “if a process that is holding some resources requests another resource and that
resource cannot be allocated to it, then it must release all resources that are currently allocated to
it”.

Another protocol is “when a process requests some resources, if they are available, allocate them.
If a resource it requested is not available, then we check whether it is being used or it is allocated
to some other process waiting for other resources. If that resource is not being used, then the OS
preempts it from the waiting process and allocate it to the requesting process. If that resource is
used, the requesting process must wait”. This protocol can be applied to resources whose states
can easily be saved and restored. It cannot be applied to resources like printers.

Eliminate Circular Wait Condition

Each resource will be assigned with a numerical number. A process can request the resources
increasing/decreasing. order of numbering. For Example, if P1 process is allocated R5 resources,
now next tim’e if P1 ask for R4, R3 lesser than R5 such request will not be granted, only request
for resources more than R5 will be granted.

2. 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. This method differs from deadlock prevention, which guarantees that deadlock cannot
occur by denying one of the necessary conditions of deadlock.

If the necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being
careful when resources are allocated. So named because the process is analogous to that used by a
banker in deciding if a loan can be safely made.

A deadlock avoidance algorithm dynamically examines the resources allocation state to ensure that
a circular wait condition case never exists. Where, the resources allocation state is defined by
available and allocated resources and the maximum demand of the process. There are 3 states of
the system:

• Safe state
• Unsafe state
• Deadlock state

A state is safe if the system can allocate resources to each process (up to its maximum) in some
order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe
sequence. A sequence of processes <P1, P2, ..., Pn> is a safe sequence for the current allocation
state if, for each Pi, the resource requests that Pi can still make can be satisfied by the currently
available resources plus the resources held by all Pj, with j <i.

If a safe sequence does not exist, then the system is in an unsafe state, which may lead to deadlock.
All safe states are deadlock free, but not all unsafe states lead to deadlocks.

9
4
 Fig: Demonstration that the state in (a) is safe.
In Fig.(a) we have a state in which A has three instances of the resource but may need as many as
nine eventually. B currently has two and may need four altogether, later. Similarly, C also has two
but may need an additional five. A total of 10 instances of the resource exist, so with seven
resources already allocated, three there are still free.
The state of Fig. (a) is safe because there exists a sequence of allocations that allows all processes
to complete. Namely, the scheduler can simply run B exclusively, until it asks for and gets two
more instances of the resource, leading to the state of Fig.(b). When B completes, we get the state
of Fig.(c). Then the scheduler can run C, leading eventually to Fig.(d). When C completes, we get
Fig.(e). Now A can get the six instances of the resource it needs and also complete. Thus, the state
of Fig.(a) is safe because the system, by carefully scheduling, can avoid deadlock.

Fig: Demonstration that the state in (b) is not safe.

Now suppose we have the initial state shown in Fig.(a), but this time A requests and gets another
resource, giving Fig.(b). Can we find a sequence that is guaranteed to work? Let us try. The
scheduler could run B until it asked for all its resources, as shown in Fig.(c). Eventually, B
completes and we get the state of Fig.(d). At this point we are stuck. We only have four instances
of the resource free, and each of the active processes needs five. There is no sequence that
guarantees completion. Thus, the allocation decision that moved the system from Fig. (a) to Fig.
(b) went from a safe to an unsafe state.

Method for deadlock avoidance

Banker’s Safety Algorithm

Step1. If need <=Available then

Execute process

9
5
 Calculate new available as,

Available = Available + Allocation

Step2. Otherwise

Do not execute and go forward

Resource Request Algorithm

Step1. If Request <= Need, goto Step2 otherwise error

Step2. If Request <= Available goto Step3 otherwise wait

Step3. Available = Available – Request

Allocation = Allocation + Request

Need = Need – Request

Step4. Check new state is safe or not

Example 1

Assume that there are 5 processes, P0 through P4, and 4 types of resources. At T0 we have the
following system state:

9
6
1. What is the content of the matrix need?
2. Is the system in the safe state?

Solution
Need matrix (Max-Allocation)

Use the safety algorithm to test if the system is in a safe state.

If Needi <= work then work = work + allocation

P0 0,1,0,0 <= 1,5,2,0 true, now work = work + allocation
= 1,5,2,0 + 0,1,1,0
= 1,6,3,0
P1 0,4,2,1 <= 1,6,3,0 false
P2 1,0,0,1 <= 1,6,3,0 false
P3 0,0,2,0 <= 1,6,3,0 true, now work = work + allocation
= 1,6,3,0 + 0,6,3,2
= 1,12,6,2
P4 0,6,4,2 <= 1,12,6,2 true, now work = work + allocation
= 1,12,6,2 + 0,0,1,4
= 1,12,7,6

P1 0,4,2,1 <= 1,12,7,6 true, now work = work + allocation

9
7
 = 1,12,7,6 + 1,2,3,1
= 2,14,10,7

P2 1,0,0,1 <= 2,14,10,7 true, now work = work + allocation

= 2,14,10,7 + 0,0,1,4
= 2,14,11,11

Thus we found the system is safe.

Here we get safe sequence as P0, P3, P4, P1, P2

Example 2
Assume that there are three resources, A, B, and C. There are 4 processes P0 to P3. At T0
we have the following snapshot of the system:

1. Create the need matrix.

2. Is the system in the safe state?

Solution

9
8
 If Needi <= work then work = work + allocation

P0 1,1,0 <= 2,1,1 true, now work = work + allocation

= 2,1,1 + 1,0,1
= 3,1,2
P1 3,3,2 <= 3,1,2 false
P2 0,1,1 <= 3,1,2 true, now work = work + allocation
= 3,1,2 + 3,0,0
= 6,1,2
P3 0,1,0 <= 6,1,2 true, now work = work + allocation
= 6,1,2 + 1,0,1
= 7,1,3
P1 3,3,2 <= 7,1,3 false

Here we get the system in unsafe state.

Example 3

Assume that there are 5 processes, P0 through P4, and 4 types of resources. At T0 we have the
following system state:

Allocation Max Available

A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 5 2 0

P1 1 0 0 0 1 7 5 0

P2 1 3 5 4 2 3 5 6

P3 0 6 3 2 0 6 5 2

P4 0 0 1 4 0 6 5 6
1. What is the content of the matrix need?
2. Is the system in a safe state?
3. If a request from process p1 arrives for (0 4 2 0) can the request be granted immediately?

Solution

9
9
 Need Matrix

A B C D

P0 0 0 0 0

P1 0 7 5 0

P2 1 0 0 2

P3 0 0 2 0

P4 0 6 4 2
If Needi <= work then work = work + allocation

P0 0,0,0,0 <= 1,5,2,0 true, now work = work + allocation

= 1,5,2,0 + 0,0,1,2
= 1,5,3,2
P1 0,7,5,0 <= 1,5,3,2 false
P2 1,0,0,2 <= 1,5,3,2 true, now work = work + allocation
= 1,5,3,2 + 1,3,5,4
= 2,8,8,6
P3 0,0,2,0 <= 2,8,8,6 true, now work = work + allocation
= 2,8,8,6 + 0,6,3,2
= 2,14,11,8
P4 0,6,4,2 <= 2,14,11,8 true, now work = work + allocation
= 2,14,11,8 + 0,0,1,4
= 2,14,12,12
P1 0,7,5,0 <= 2,14,12,12 true, now work = work + allocation
= 2,14,12,12 + 1,0,0,0
= 3,14,12,12

System is in the safe state and safe sequence is P0,P2,P3,P4,P1

If a request from process P1 arrives for (0 4 2 0)

Need of P1= max of P1-allocation of P1
= 1,7,5,0 – 1,0,0,0
= 0,7,5,0

Here request (0,4,2,0) <= need (0,7,5,0)

Here request (0,4,2,0) <= available (1,5,2,0)

available = available – request

= 1,5,2,0 – 0,4,2,0
1
0
 = 1,1,0,0

allocation = allocation + request

= 1,0,0,0 + 0,4,2,0

= 1,4,2,0

need = need – request

= 0,7,5,0 – 0,4,2,0

= 0,3,3,0

Now we are going to check whether new state is safe or not.

Allocation Max Available

A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 1 0 0

P1 1 4 2 0 1 7 5 0

P2 1 3 5 4 2 3 5 6

P3 0 6 3 2 0 6 5 2

P4 0 0 1 4 0 6 5 6

Need Matrix

A B C D

P0 0 0 0 0

P1 0 3 3 0

P2 1 0 0 2

P3 0 0 2 0

P4 0 6 4 2
If Needi <= work then work = work + allocation

P0 0,0,0,0 <= 1,1,0,0 true, now work = work + allocation

= 1,1,0,0 + 0,0,1,2
= 1,1,1,2
P1 0,3,3,0 <= 1,1,1,2 false

1
0
 P2 1,0,0,2 <= 1,1,1,2 true, now work = work + allocation
= 1,1,1,2 + 1,3,5,4
= 2,4,6,6
P3 0,0,2,0 <= 2,4,6,6 true, now work = work + allocation
= 2,4,6,6 + 0,6,3,2
= 2,10,9,8
P4 0,6,4,2 <= 2,10,9,8 true, now work = work + allocation
= 2,10,9,8 + 0,6,4,2
= 2,16,13,10
P1 0,3,3,0 <= 2,16,13,10 true, now work = work + allocation
= 2,16,13,10 + 0,3,3,0
= 2,19,16,10

System is in the safe state and safe sequence is P0,P2,P3,P4,P1

Problem with Banker’s Algorithm

1. An algorithm requires fixed number of resources, some processes dynamically change

the number of resources.
2. An algorithm requires the number of resources in advance, it is very difficult to predict
the resources in advanced.
3. Algorithms predict all process returns within finite time, but the system does not
guarantee it.

3. Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and identifying the
processes and resources involved in the deadlock. The basic idea is to check allocation against
resource availability for all possible allocation sequences to determine if the system is in
deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once
a deadlock is detected, there needs to be a way to recover several alternatives exists:

• Temporarily prevent resources from deadlocked processes.

• Back off a process to some check point allowing preemption of a needed resource and
restarting the process at the checkpoint later.
• Successively kill processes until the system is deadlock free.
These methods are expensive in the sense that each iteration calls the detection algorithm until the
system proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number
of proceeds. Another potential problem is starvation; same process killed repeatedly.

Resource allocation graph (RAG)

1
0
We use the resource allocation graph for the pictographic representation of the state of a system.
The resource allocation graph contains all the information related to the processes that are holding
some resources and also waiting for some more resources.
Resource allocation graph consists of all the information which is related to all the instances of the
resources means the information about available resources and the resources which the process is
being using.
In the Resource Allocation Graph, we use a circle to represent the process and rectangle to
represent the resource. There are two components of the resource allocation graph vertices and
edges.
In RAG vertices are two type –
1. Process vertex – Every process will be represented as a process vertex. Generally, the
process will be represented with a circle.
2. Resource vertex – Every resource will be represented as a resource vertex. It is also two
type.
• Single instance type resource – It represents as a box, inside the box, there will be one
dot. So the number of dots indicate how many instances are present of each resource
type.
• Multi-resource instance type resource – It also represents as a box, inside the box,
there will be many dots present.

There are two types of edges in RAG-

1. Assign Edge – If you already assign a resource to a process then it is called Assign edge. 2.
Request Edge – It means in future the process might want some resource to complete the
execution, that is called request edge.

1
0
So, if a process is using a resource, an arrow is drawn from the resource node to the process node.
If a process is requesting a resource, an arrow is drawn from the process node to the resource node.
Example 1 (Single instances RAG)

If there is a cycle in the Resource Allocation Graph and each resource in the cycle provides only
one instance, then the processes will be in deadlock. For example, if process P1 holds resource R1,
process P2 holds resource R2 and process P1 is waiting for R2 and process P2 is waiting for R1,
then process P1 and process P2 will be in deadlock.

1
0
Here’s another example, that shows Processes P1 and P2 acquiring resources R1 and R2 while
process P3 is waiting to acquire both resources. In this example, there is no deadlock because there
is no circular dependency.So cycle in single-instance resource type is the sufficient condition for
deadlock.

Example 2 (Multi-instances RAG) –

From the above example, it is not possible to say the RAG is in a safe state or in an unsafe state.
So to see the state of this RAG, let’s construct the allocation matrix and request matrix.

1
0
 • The total number of processes are three; P1, P2 & P3 and the total number of resources are
two; R1 & R2.
Allocation matrix –
• For constructing the allocation matrix, just go to the resources and see to which process it is
allocated.
• R1 is allocated to P1, therefore write 1 in allocation matrix and similarly, R2 is allocated to
P2 as well as P3 and for the remaining element just write 0.
Request matrix –
• In order to find out the request matrix, you have to go to the process and see the outgoing
edges.
• P1 is requesting resource R2, so write 1 in the matrix and similarly, P2 requesting R1 and for
the remaining element write 0. So now available resource is = (0, 0).

Checking deadlock (safe or not) –

So, there is no deadlock in this RAG. Even though there is a cycle, still there is no deadlock.
Therefore, in multi-instance resource cycle is not sufficient condition for deadlock.

1
0
Above example is the same as the previous example except that, the process P3 requesting for
resource R1. So the table becomes as shown in below.

So, the Available resource is = (0, 0), but requirement are (0, 1), (1, 0) and (1, 0).So you can’t
fulfill any one requirement. Therefore, it is in deadlock.
Therefore, every cycle in a multi-instance resource type graph is not a deadlock, if there has to be
a deadlock, there has to be a cycle. So, in case of RAG with multi-instance resource type, the cycle
is a necessary condition for deadlock, but not sufficient.

1
0
Fig: Resource allocation graph with a deadlock Fig: Resource allocation graph with a
cycle but no deadlock

4. Deadlock Recovery
1. Process Termination:

To eliminate the deadlock, we can simply kill one or more processes. For this, we use two
methods:
a. Abort all the Deadlocked Processes:
Aborting all the processes will certainly break the deadlock, but with a great
expenses. The deadlocked processes may have computed for a long time and the
result of those partial computations must be discarded and there is a probability to
recalculate them later.
b. Abort one process at a time until deadlock is eliminated:
Abort one deadlocked process at a time, untill deadlock cycle is eliminated from the
system. Due to this method, there may be considerable overhead, because after
aborting each process, we have to run deadlock detection algorithm to check
whether any processes are still deadlocked.
2. Resource Preemption:

To eliminate deadlocks using resource preemption, we preempt some resources from processes
and give those resources to other processes. This method will raise three issues – a. Selecting a
victim:
We must determine which resources and which processes are to be preempted and also the
order to minimize the cost.
b. Rollback:
We must determine what should be done with the process from which resources are
preempted. One simple idea is total rollback. That means abort the process and restart it.

1
0
 Unit-5 Memory
Management
Introduction
1
0
Memory Management is the process of controlling and coordinating computer memory, assigning
portions known as blocks to various running programs to optimize the overall performance of the
system.

Memory management is the functionality of an operating system which handles or manages

primary memory and moves processes back and forth between main memory and disk during
execution. Memory management keeps track of each and every memory location, regardless of
either it is allocated to some process or it is free. It checks how much memory is to be allocated to
processes. It decides which process will get memory at what time. It tracks whenever some
memory gets freed or unallocated and correspondingly it updates the status.

Memory Hierarchy
The memory in a computer can be divided into five hierarchies based on the speed as well as use.
The processor can move from one level to another based on its requirements. The five hierarchies
in the memory are registers, cache, main memory, magnetic discs, and magnetic tapes. The first
three hierarchies are volatile memories which mean when there is no power, and then automatically
they lose their stored data. Whereas the last two hierarchies are not volatile which means they store
the data permanently. A memory element is the set of storage devices which stores the binary data
in the type of bits. In general, the storage of memory can be classified into two categories such as
volatile as well as non- volatile.
The memory hierarchy design in a computer system mainly includes different storage devices.
Most of the computers were inbuilt with extra storage to run more powerfully beyond the main
memory capacity. The following memory hierarchy diagram is a hierarchical pyramid for
computer memory. The designing of the memory hierarchy is divided into two types such as
primary (Internal) memory and secondary (External) memory.

Fig: Memory Hierarchy

Registers

1
1
Usually, the register is a static RAM or SRAM in the processor of the computer which is used for
holding the data word which is typically 64 or 128 bits. The program counter register is the most
important as well as found in all the processors. Most of the processors use a status word register
as well as an accumulator. A status word register is used for decision making, and the
accumulator is used to store the data like mathematical operation. Usually, computers like
complex instruction set computers have so many registers for accepting main memory, and
RISC- reduced instruction set computers have more registers.

Cache Memory
Cache memory can also be found in the processor, however rarely it may be another IC (integrated
circuit) which is separated into levels. The cache holds the chunk of data which are frequently used
from main memory. When the processor has a single core then it will have two (or) more cache
levels rarely. Present multi-core processors will be having three, 2-levels for each one core, and
one level is shared.
Main Memory
The main memory in the computer is nothing but, the memory unit in the CPU that communicates
directly. It is the main storage unit of the computer. This memory is fast as well as large memory
used for storing the data throughout the operations of the computer. This memory is made up of
RAM as well as ROM.

Magnetic Disks
The magnetic disks in the computer are circular plates fabricated of plastic otherwise metal by
magnetized material. Frequently, two faces of the disk are utilized as well as many disks may be
stacked on one spindle by read or write heads obtainable on every plane. All the disks in computer
turn jointly at high speed. The tracks in the computer are nothing but bits which are stored within
the magnetized plane in spots next to concentric circles. These are usually separated into sections
which are named as sectors.

Magnetic Tape
This tape is a normal magnetic recording which is designed with a slender magnetizable covering
on an extended, plastic film of the thin strip. This is mainly used to back up huge data. Whenever
the computer requires to access a strip, first it will mount to access the data. Once the data is
allowed, then it will be unmounted. The access time of memory will be slower within magnetic
strip as well as it will take a few minutes for accessing a strip.

Advantages of Memory Hierarchy

The need for a memory hierarchy includes the following.

• Memory distributing is simple and economical.

• Removes external destruction.
• Data can be spread all over.
• Permits demand paging & pre-paging. Swapping will be more proficient.

Logical versus and Physical Address Space

1
1
Logical address is generated by CPU while a program is running. The logical address is virtual
address as it does not exist physically, therefore, it is also known as Virtual Address. This address
is used as a reference to access the physical memory location by CPU. The term Logical Address
Space is used for the set of all logical addresses generated by a program’s perspective.
The hardware device called Memory-Management Unit is used for mapping logical address to its
corresponding physical address.
Physical Address identifies a physical location of required data in a memory. The user never
directly deals with the physical address but can access by its corresponding logical address. The
user program generates the logical address and thinks that the program is running in this logical
address but the program needs physical memory for its execution, therefore, the logical address
must be mapped to the physical address by MMU before they are used. The term Physical Address
Space is used for all physical addresses corresponding to the logical addresses in a Logical address
space.

Fig: Mapping virtual address to physical address

Logical Address Physical Address
1. It is the virtual address generated by CPU. 1. The physical address is a location in a
memory unit.
2. Set of all logical addresses generated by 2. Set of all physical addresses mapped to the
CPU in reference to a program is referred corresponding logical addresses is referred
as Logical Address Space. as Physical Address.
3. The user can view the logical address of a 3. The user can never view physical address of
program. program
4. The user uses the logical address to access 4. The user can not directly access physical
the physical address. address.

1
1
 5. The Logical Address is generated by the 5. Physical Address is Computed by MMU.
CPU

Memory Management with Swapping

Swapping is a memory management scheme in which any process can be temporarily swapped
from main memory to secondary memory so that the main memory can be made available for other
processes. It is used to improve main memory utilization. In secondary memory, the place where
the swapped-out process is stored is called swap space. The purpose of the swapping in operating
system is to access the data present in the hard disk and bring it to RAM so that the application
programs can use it. The thing to remember is that swapping is used only when data is not present
in RAM. Although the process of swapping affects the performance of the system, it helps to run
larger and more than one process. This is the reason why swapping is also referred to as memory
compaction.
The concept of swapping has divided into two more concepts: Swap-in and Swap-out.
Swap-out is a method of removing a process from RAM and adding it to the hard disk.

Swap-in is a method of removing a program from a hard disk and putting it back into the main
memory or RAM.

Fig: Swapping of two processes using a disk as a backing store

Memory Management with Bitmaps
The bitmap approach divides the memory space into small fixed sized allocation units. These units
might be a few bytes/words in size or perhaps several kilobytes. The bitmap contains a single bit
for each allocation unit which indicates the status of that unit, 1 for used, 0 for unused. The greater
the number of allocation units, the larger the bit map. The size of memory and the size of allocation
units determine the size of the bitmap. The size of the allocation
1
1
unit can be an important design consideration. If the allocation unit is too large, the bit map will
be smaller, but we will only be able to allocate memory space in multiples of large allocation units,
so it is likely that some of the space within an allocated unit might not be required by a process.

The diagram shows five processes in memory with three (shaded) free holes corresponding to 0
values in the bitmap. Initially, the memory is empty and the bitmap contains all 0 entries. To
allocate a region of memory, the memory manager needs to search the bitmap for a string of 0’s
which represents a region large enough to accommodate the request. If the memory is large and
the allocation units are relatively small, then searching the bitmap string maybe time consuming.
To deallocate a region, the memory manager simply sets the appropriate bits in the bitmap back to
0.

Disadvantages of using Bitmap

• The OS has to assign some memory for bitmap as well since it stores the details about
allocation units. That much amount of memory cannot be used to load any process therefore
that decreases the degree of multiprogramming as well as throughput.
• To identify any hole in the memory, the OS need to search the string of 0s in the bitmap.
This searching takes a huge amount of time which makes the system inefficient to some
extent.

Memory Management with Linked Lists

Another way of keeping track of memory is to maintain a linked list of allocated and free memory
segments, where a segment is either a process or a hole between two processes. Each entry in the
list specifies a hole (H) or process (P), the address at which it starts, the length, and a pointer to
the next entry. In this example, the segment list is kept sorted by address. Sorting this way has the
advantage that when a process terminates or is swapped out, updating the list is straightforward. A
terminating process normally has two neighbors (except when it is at the very top or very bottom
of memory). These may be either processes or holes, leading to the four combinations shown in
fig above.

1
1
When the processes and holes are kept on a list sorted by address, several algorithms can be used
to allocate memory for a newly created process (or an existing process being swapped in from
disk). We assume that the memory manager knows how much memory to allocate.

Memory Management without Swapping

Memory management is the process of controlling and coordinating computer memory, assigning
portions known as blocks to various running program to optimize the overall performance of the
system. Here entire process remains in memory from start to finish and does not move. The sum
of the memory requirements of all jobs in the system cannot exceed the size of physical memory.

Contiguous Memory Allocation

Contiguous memory allocation is basically a method in which a single contiguous section/part of
memory is allocated to a process or file needing it. In the image shown below, there are three files
in the directory. The starting block and the length of each file are mentioned in the table. We can
check in the table that the contiguous blocks are assigned to each file as per its need.

Fig: Contiguous Allocation

Advantages

1. It is simple to implement.
2. We will get Excellent read performance.
3. Supports Random Access into files.

Disadvantages

1. The disk will become fragmented.

2. It may be difficult to have a file grow.
Relocation
The available memory is generally shared among a number of processes in a multiprogramming
system, so it is not possible to know in advance which other programs will be resident in main
memory at the time of execution of his program. Swapping the active processes in and out of the

1
1
main memory enables the operating system to have a larger pool of ready-to-execute process.
When a program gets swapped out to a disk memory, then it is not always possible that when it is
swapped back into main memory then it occupies the previous memory location, since the location
may still be occupied by another process. We may need to relocate the process to a different area
of memory. Thus there is a possibility that program may be moved in main memory due to
swapping.

The figure depicts a process image. The process image is occupying a continuous region of main
memory. The operating system will need to know many things including the location of process
control information, the execution stack, and the code entry. Within a program, there are memory
references in various instructions and these are called logical addresses.
After loading of the program into main memory, the processor and the operating system must be
able to translate logical addresses into physical addresses. Branch instructions contain the address
of the next instruction to be executed. Data reference instructions contain the address of byte or
word of data referenced.

Memory Protection
Memory protection is a way to control memory access rights on a computer, and is a part of most
modern instruction set architectures and operating systems. The main purpose of memory
protection is to prevent a process from accessing memory that has not been allocated to it. This
prevents a bug or malware within a process from affecting other processes, or the operating system
itself. Protection may encompass all accesses to a specified area of memory, write accesses, or
attempts to execute the contents of the area. An attempt to access unowned memory results in a
hardware fault, called a segmentation fault or storage violation exception, generally causing
abnormal termination of the offending process. Memory protection for computer security includes
additional techniques such as address space layout randomization and executable space protection.

1
1
 Fig: Memory protection
Memory Allocation
Memory allocation is an action of assigning the physical or the virtual memory address space to a
process (its instructions and data). The two fundamental methods of memory allocation are static
and dynamic memory allocation.
Static memory allocation method assigns the memory to a process, before its execution. On the
other hand, the dynamic memory allocation method assigns the memory to a process, during its
execution.
To get a process executed it must be first placed in the memory. Assigning space to a process in
memory is called memory allocation. Memory allocation is a general aspect of the term binding.
Let us understand binding with the help of an example. Suppose, there is an entity in a program,
with the set of attributes. Now, a variable of this entity will have values for these set of attributes.
For storing these values, we must have memory allotted to these attributes.
So, the act of assigning the memory address to the attribute of the variable is called memory
allocation. And the act of specifying/binding the values to the attributes of the variable is called
binding. This action of binding must be performed before the variable is used during the execution
of the program.
Different allocation algorithms are:

a. First fit
b. Next fit
c. Best fit
d. Worst fit
e. Quick fit
a. First fit

1
1
 In the first fit, the partition is allocated which is the first sufficient block from the top of Main
Memory. It scans memory from the beginning and chooses the first available block that is large
enough. Thus it allocates the first hole that is large enough.

Advantage

Fastest algorithm because it searches as little as possible.

Disadvantage

The remaining unused memory areas left after allocation become waste if it is too smaller. Thus
request for larger memory requirement cannot be accomplished.
b. Next fit

Next fit is a modified version of first fit. It begins as first fit to find a free partition. When called
next time it starts searching from where it left off, not from the beginning.

c. Best fit

Allocate the process to the partition which is the first smallest sufficient partition among the free
available partition. It searches the entire list of holes to find the smallest hole whose size is greater
than or equal to the size of the process.

1
1
Advantage

Memory utilization is much better than first fit as it searches the smallest free partition first
available.
Disadvantage

It is slower and may even tend to fill up memory with tiny useless holes. d.
Worst fit

Allocate the process to the partition which is the largest sufficient among the freely available
partitions available in the main memory. It is opposite to the best-fit algorithm. It searches the
entire list of holes to find the largest hole and allocate it to process.

Advantage

Reduces the rate of production of small gaps.

1
1
Disadvantage

If a process requiring larger memory arrives at a later stage then it cannot be accommodated as the
largest hole is already split and occupied.
e. Quick fit

The quick fit algorithm suggests maintaining the different lists of frequently used sizes. Although,
it is not practically suggestible because the procedure takes so much time to create the different
lists and then expending the holes to load a process.

Exercise
Given memory partitions of 100k, 500k, 200k, 300k and 600k (in order), how would each of the
First-fit, Best-fit and Worst-fit algorithms place processes of 212k, 417k, 112k and 426k (in order)?
Which algorithm makes the most efficient use of memory?

Solution
First-fit

Primary
100K 500K 200K 300K 600K
memory

1. 212K is put in 500k partition

100K 212k 200K 300K 600K

2. 417 is put in 600k partition

100K 212k 200K 300K 417k

3. 112k is put in 288k partition (new partition 500k – 212k = 288k)

100K 212k 112k 200K 300K 417k

4. 426k must wait

Best-fit

Primary
100K 500K 200K 300K 600K
memory

1. 212K is put in 300k partition

100K 500k 200K 212K 600K

2. 417 is put in 500k partition

1
2
 100K 417k 200K 212K 600K

3. 112k is put in 200k partition

100K 417k 112K 212K 600K

4. 426k is put in 600k partition

100K 417k 112K 212K 426K

Worst-fit

Primary
100K 500K 200K 300K 600K
memory

1. 212K is put in 600k partition

100K 500k 200K 300K 212K

2. 417 is put in 500k partition

100K 417k 200K 300K 212K

3. 112k is put in 388k partition (new partition 600k – 212k = 388k)

100K 417k 200K 300K 212K 112k

4. 426k
must wait

In this example, Best-fit turns out to be the best.

Fragmentation
Fragmentation is an unwanted problem where the memory blocks cannot be allocated to the
processes due to their small size and the blocks remain unused. It can also be understood as when
the processes are loaded and removed from the memory they create free space or hole in the
memory and these small blocks cannot be allocated to new upcoming processes and results in
inefficient use of memory. Basically, there are two types of fragmentation:

• Internal Fragmentation
• External Fragmentation
Internal fragmentation
In this fragmentation, the process is allocated a memory block of size more than the size of that
process. Due to this some part of the memory is left unused and this cause internal fragmentation.

1
2
Example: Suppose there is fixed partitioning (i.e. the memory blocks are of fixed sizes) is used
for memory allocation in RAM. These sizes are 2MB, 4MB, 4MB, 8MB. Some part of this RAM
is occupied by the Operating System (OS).

Now, suppose a process P1 of size 3MB comes and it gets memory block of size 4MB. So, the
1MB that is free in this block is wasted and this space can’t be utilized for allocating memory to
some other process. This is called internal fragmentation.

How can we remove internal fragmentation?

This problem is occurring because we have fixed the sizes of the memory blocks. This problem
can be removed if we use dynamic partitioning for allocating space to the process. In dynamic
partitioning, the process is allocated only that much amount of space which is required by the
process. So, there is no internal fragmentation.

External fragmentation
In this fragmentation, although we have total space available that is needed by a process still we
are not able to put that process in the memory because that space is not contiguous. This is called
external fragmentation.

Example: Suppose in the above example, if three new processes P2, P3, and P4 come of sizes
1MB, 3MB, and 6MB respectively. Now, these processes get memory blocks of size 2MB, 4MB
and 8MB respectively allocated.

So, now if we closely analyze this situation then process P3 (unused 1MB) and P4 (unused

1
2
2MB) are again causing internal fragmentation. So, a total of 4MB (1MB (due to process P1) +
1MB (due to process P3) + 2MB (due to process P4)) is unused due to internal fragmentation.

Now, suppose a new process of 4MB comes. Though we have a total space of 4MB still we can’t
allocate this memory to the process. This is called external fragmentation.

How can we remove external fragmentation?

This problem is occurring because we are allocating memory continuously to the processes. So,
if we remove this condition external fragmentation can be reduced. This is what done in paging &
segmentation(non-contiguous memory allocation techniques) where memory is allocated non-
contiguously to the processes. We will learn about paging and segmentation in the next blog.
Another way to remove external fragmentation is compaction. When dynamic partitioning is used
for memory allocation then external fragmentation can be reduced by merging all the free
memory together in one large block. This technique is also called defragmentation. This larger
block of memory is then used for allocating space according to the needs of the new processes.

1
2
Difference between Internal fragmentation and External fragmentation
Internal fragmentation External fragmentation

1. In internal fragmentation fixed-sized 1. In external fragmentation, variable-sized

memory, blocks square measure appointed memory blocks square measure appointed
to process. to method.

2. Internal fragmentation happens when the 2. External fragmentation happens when the
method or process is larger than the method or process is removed.
memory.

3. The solution of internal fragmentation is 3. Solution of external fragmentation is

best-fit block. compaction, paging and segmentation

4. Internal fragmentation occurs when memory 4. External fragmentation occurs when

is divided into fixed sized partitions. memory is divided into variable size
partitions based on the size of processes.

5. The difference between memory allocated 5. The unused spaces formed between
and required space or memory is called noncontiguous memory fragments are too
Internal fragmentation. small to serve a new process, is called
External fragmentation .

Fixed (static) partitioning

This is the oldest and simplest technique used to put more than one processes in the main memory.
In this partitioning, number of partitions (non-overlapping) in RAM are fixed but size of each
partition may or may not be same. As it is contiguous allocation, hence no spanning is allowed.
Here partition are made before execution or during system configure.

1
2
As illustrated in above figure, first process is only consuming 1MB out of 4MB in the main
memory. Hence, Internal Fragmentation in first block is (4-1)=3MB. Sum of Internal
Fragmentation in every block = (4-1)+(8-7)+(8-7)+(16-14)= 3+1+1+2 = 7MB.
Suppose process P5 of size 7MB comes. But this process cannot be accommodated inspite of
available free space because of contiguous allocation (as spanning is not allowed). Hence, 7MB
becomes part of External Fragmentation.
There are some advantages and disadvantages of fixed partitioning.
Advantages of Fixed Partitioning – 1.
Easy to implement:
Algorithms needed to implement Fixed Partitioning are easy to implement. It simply requires
putting a process into certain partition without focussing on the emergence of Internal and
External Fragmentation.
2. Little OS overhead:
Processing of Fixed Partitioning require lesser excess and indirect computational power.
Disadvantages of Fixed Partitioning – 1. Internal Fragmentation:
Main memory use is inefficient. Any program, no matter how small, occupies an entire
partition. This can cause internal fragmentation.
2. External Fragmentation:
The total unused space (as stated above) of various partitions cannot be used to load the
processes even though there is space available but not in the contiguous form (as spanning is
not allowed).
3. Limit process size:
Process of size greater than size of partition in Main Memory cannot be accommodated.
Partition size cannot be varied according to the size of incoming process’s size. Hence, process
size of 32MB in above stated example is invalid.
4. Limitation on Degree of Multiprogramming:
Partition in Main Memory are made before execution or during system configure. Main
Memory is divided into fixed number of partition. Suppose if there
1
2
 are n1 partitions in RAM and n2 are the number of processes, then n2<=n1 condition must be
fulfilled. Number of processes greater than number of partitions in RAM is invalid in Fixed
Partitioning.

Variable (Dynamic) partitioning

It is a part of Contiguous allocation technique. It is used to alleviate the problem faced by Fixed
Partitioning. In contrast with fixed partitioning, partitions are not made before the execution or
during system configure. Various features associated with variable Partitioning-
1. Initially RAM is empty and partitions are made during the run-time according to process’s
need instead of partitioning during system configure.
2. The size of partition will be equal to incoming process.
3. The partition size varies according to the need of the process so that the internal fragmentation
can be avoided to ensure efficient utilisation of RAM.
4. Number of partitions in RAM is not fixed and depends on the number of incoming process and
Main Memory’s size.

Advantages of Variable Partitioning – 1.

No Internal Fragmentation:
In variable Partitioning, space in main memory is allocated strictly according to the need of
process, hence there is no case of internal fragmentation. There will be no unused space left
in the partition.
2. No restriction on Degree of Multiprogramming:
1
2
 More number of processes can be accommodated due to absence of internal fragmentation. A
process can be loaded until the memory is empty.
3. No Limitation on the size of the process:
In Fixed partitioning, the process with the size greater than the size of the largest partition
could not be loaded and process can not be divided as it is invalid in contiguous allocation
technique. Here, In variable partitioning, the process size can’t be restricted since the partition
size is decided according to the process size.

Disadvantages of Variable Partitioning – 1.

Difficult Implementation:
Implementing variable Partitioning is difficult as compared to Fixed Partitioning as it involves
allocation of memory during run-time rather than during system configure.
2. External Fragmentation:
There will be external fragmentation inspite of absence of internal fragmentation. For example,
suppose in above example- process P1(2MB) and process P3(1MB) completed their execution.
Hence two spaces are left i.e. 2MB and 1MB. Let’s suppose process P5 of size 3MB comes.
The empty space in memory cannot be allocated as no spanning is allowed in contiguous
allocation. The rule says that process must be contiguously present in main memory to get
executed. Hence it results in External Fragmentation.

Non-contiguous memory allocation

The Non-contiguous memory allocation allows a process to acquire the several memory blocks at
the different location in the memory according to its requirement. The non-contiguous memory
allocation also reduces the memory wastage caused due to internal and external fragmentation. As
it utilizes the memory holes, created during internal and external fragmentation.

Fig: Non-contiguous memory allocation

Non-contiguous memory allocation is of different types,

1. Paging
2. Segmentation
3. Segmentation with paging
1
2
i) Paging

A non-contiguous policy with a fixed size partition is called paging. A computer can address more
memory than the amount of physically installed on the system. This extra memory is actually called
virtual memory. Paging technique is very important in implementing virtual memory. Secondary
memory is divided into equal size partition (fixed) called pages. Every process will have a separate
page table. The entries in the page table are the number of pages a process. At each entry either we
have an invalid pointer which means the page is not in main memory or we will get the
corresponding frame number. When the frame number is combined with instruction of set D than
we will get the corresponding physical address. Size of a page table is generally very large so
cannot be accommodated inside the PCB, therefore, PCB contains a register value PTBR( page
table base register) which leads to the page table.

Advantages: It is independent of external fragmentation.

Disadvantages:

1. It makes the translation very slow as main memory access two times.
2. A page table is a burden over the system which occupies considerable space.

ii) Segmentation

Segmentation is a programmer view of the memory where instead of dividing a process into equal
size partition we divided according to program into partition called segments. The translation is
the same as paging but paging segmentation is independent of internal fragmentation but suffers
from external fragmentation. Reason of external fragmentation is program can be divided into
segments but segment must be contiguous in nature.

iii) Segmentation with paging

In segmentation with paging, we take advantages of both segmentation as well as paging. It is a

kind of multilevel paging but in multilevel paging, we divide a page table into equal size partition
but here in segmentation with paging, we divide it according to segments. All the properties are
the same as that of paging because segments are divided into pages

1
2
Difference between contiguous and non-contiguous memory allocation
Contiguous memory allocation Non-contiguous memory allocation
1. Contiguous memory allocation allocates 1. Non-Contiguous memory allocation
consecutive blocks of memory to a allocates separate blocks of memory to a
file/process. file/process.
2. Faster in Execution 2. Slower in Execution
3. It is easier for the OS to control. 3. It is difficult for the OS to control.
4. Overhead is minimum as not much address
4. More Overheads are there as there are more
translations are there while executing a
address translations.
process.
5. Internal fragmentation occurs in 5. External fragmentation occurs in
Contiguous memory allocation method. NonContiguous memory allocation
method.
6. It includes single partition allocation and
6. It includes paging and segmentation.
multi-partition allocation.
7. Wastage of memory is there. 7. No memory wastage is there
8. In contiguous memory allocation, swapped- 8. In non-contiguous memory allocation,
in processes are arranged in the originally swapped-in processes can be arranged in
allocated space any place in the memory.

Coalescing and Compaction

1
2
The process of merging two adjacent holes to form a single larger hole is called coalescing.

Figure: coalescing

Even when holes are coalesced, no individual hole may be large enough to hold the job, although
the sum of holes is larger than the storage required for a process. It is possible to combine all the
holes into one big one by moving all the processes downward as far as possible; this technique is
called memory compaction. The efficiency of the system is decreased in the case of compaction
due to the fact that all the free spaces will be transferred from several places to a single place. Huge
amount of time is invested for this procedure and the CPU will remain idle for all this time. Despite
of the fact that the compaction avoids external fragmentation, it makes system inefficient.

Fig: Compaction

Virtual Memory

Virtual Memory is a space where large programs can store themselves in form of pages while their
execution and only the required pages or portions of processes are loaded into the main memory.
This technique is useful as large virtual memory is provided for user programs when a very small
physical memory is there. whenever some pages needs to be loaded in the main memory for the
execution and the memory is not available for those many pages, then in that case, instead of
stopping the pages from entering in the main memory, the OS search for the RAM area that are
least used in the recent times or that are not referenced and copy that into the secondary memory
to make the space for the new pages in the main memory.

1
3
Benefits of having Virtual Memory

1. Large programs can be written, as virtual space available is huge compared to physical
memory.
2. Less I/O required, leads to faster and easy swapping of processes.
3. More physical memory available, as programs are stored on virtual memory, so they
occupy very less space on actual physical memory.

Paging

A computer can address more memory than the amount physically installed on the system. This
extra memory is actually called virtual memory and it is a section of a hard that's set up to emulate
the computer's RAM. Paging technique plays an important role in implementing virtual memory.
Paging is a memory management technique in which process address space is broken into blocks
of the same size called pages (size is power of 2, between 512 bytes and 8192 bytes). The size of
the process is measured in the number of pages.
Similarly, main memory is divided into small fixed-sized blocks of (physical) memory called
frames and the size of a frame is kept the same as that of a page to have optimum utilization of
the main memory and to avoid external fragmentation.

1
3
Page address is called logical address and represented by page number and the offset.
Logical Address = Page number + page offset
Frame address is called physical address and represented by a frame number and the offset.
Physical Address = Frame number + page offset
A data structure called page map table is used to keep track of the relation between a page of a
process to a frame in physical memory.

1
3
When the system allocates a frame to any page, it translates this logical address into a physical
address and create entry into the page table to be used throughout execution of the program.
When a process is to be executed, its corresponding pages are loaded into any available memory
frames. Suppose you have a program of 8Kb but your memory can accommodate only 5Kb at a
given point in time, then the paging concept will come into picture. When a computer runs out of
RAM, the operating system (OS) will move idle or unwanted pages of memory to secondary
memory to free up RAM for other processes and brings them back when needed by the program.
This process continues during the whole execution of the program where the OS keeps removing
idle pages from the main memory and write them onto the secondary memory and bring them back
when required by the program.

Advantages of paging

• It allows to store parts of a single process in a non-contiguous fashion.

• It solves the problem of external fragmentation

Disadvantages of paging

• It suffers from internal fragmentation.

• There is an overhead of maintaining a page table for each process.
• The time taken to fetch the instruction increases since now two memory accesses are required

Structure of page table

There are several types of page tables, which are optimized for different requirements. Some of
major page tables are listed below:

a. Hierarchical page table

b. Hashed page table
1
3
 c. Inverted page table
d. Shared page table
a. Hierarchical page table
It is also called multilevel page table. The multilevel page table method is to avoid keeping all
the pages tables in memory all the time. The top level page table with 1024 entries
corresponding to the 10 bits PTL (Page Table Length Filed). When a virtual address is
presented to the memory management unit (MMU). it first extracts the PTL. (Page Table
Length Filed), and uses this value as an index into the top level page table.

Fig: Two level page table

1
3
 b.

Hashed page table

In hashed page tables, the virtual page number in the virtual address is hashed into the hash
table. They are used to handle address spaces higher than 32 bits. Each entry in the hash table
has a linked list of elements hashed to the same location (to avoid collisions – as we can get
the same value of a hash function for different page numbers). The hash value is the virtual
page number. The Virtual Page Number is all the bits that are not a part of the page offset.

For each element in the hash table, there are three fields –
1. Virtual Page Number (which is the hash value).
2. Value of the mapped page frame.
3. A pointer to the next element in the linked list.

c. Inverted page table

1
3
Inverted page table is the global page table which is maintained by the operating system for all
the processes. In inverted page table, the number of entries is equal to the number of frames in
the main memory. It can be used to overcome the drawbacks of page table. There is always a
space reserved for the page regardless of the fact what whether it is present in the main memory
or not. However, this is simply the wastage of the memory if the page is not present. We can
save this wastage by just inverting the page table. We can save the details only for the pages
which are present in the main memory. Frames are the indices and the information saved inside
the block will be Process ID and page number.

It has only one-page table for all processes. This table has an entry for each real page (block of
physical memory). Each element contains the virtual address of the page stored in that physical
location, with information about the process that owns that page.

frame Process Page no id no

0
P1 p0
1
P2 p1
2 P1 p2
3
P3 p1
4
P2 p3
5
Inverted page table P3 p2

1
3
d. Shared page table
The primary purpose of sharing page tables is improved performance for large applications
that share big memory areas between multiple processes. It eliminates the redundant page
tables and significantly reduces the number of minor page faults. Here pages may be shared
by multiple processes.

1
3
 Fig: Shared page table

Mapping
The transformation of data from main memory to cache memory is referred to as a mapping. There
are three types of mapping
1. Associative mapping: The fastest and most flexible cache organization uses an associative
memory. The associative memory stores both the address and content (data) of the memory
word. This permits any location in cache to store any word from main memory. A CPU address
is placed in the argument register and the associative memory is searched for a matching
address. If the address is found, the corresponding data is read and sent to the CPU. If no match
occurs, the main memory is accessed for the word. The address- data pair is then transferred to
the associative cache memory.

1
3
2. Direct mapping: Associative memory is expensive compared to random-access memories
because of the added logic associated with each cell. The CPU address is divided into two fields
index and tag field. Least significant bits constitute the index field and the remaining form the
tag field. The main memory needs an address that includes both the tag and the index bits. Each
word in cache consists of the data word and its associated tag. When a new word is first brought
into the cache, the tag bits are stored alongside the data bits. When the CPU generates a memory
request, the index field is used for the address to access the cache. The tag field of the CPU
address is compared with the tag in the word read from the cache. If the two tags match, there
is a hit and the desired data word is in cache. If there is no match, there is a miss and the required
word is read from main memory. The disadvantage of direct mapping is that the hit ratio can
drop considerably if two or more words whose address have the same index but different tags
are accessed repeatedly.

3. Set Associative mapping: Disadvantage of direct mapping is that two words with the same index
in their address but with different tag values cannot reside in cache memory at the same time.
In set associative mapping each word of cache can store two or more words of memory under
the same index address. Each data word is stored together with its tag
1
3
 and the number of tag- data items in one word of cache is said to form a set. When the CPU
generates a memory request, the index value of the address is used to access the cache. The tag
field of the CPU address is then compared with both tags in the cache to determine if a match
occurs. The hit ratio will improve as the set size increases because more words with the same
index but different tags can reside in cache. However, an increase in the set size increases the
number of bits in words of cache and requires more complex comparison logic.

Demand paging

A demand paging system is quite similar to a paging system with swapping where processes reside
in secondary memory and pages are loaded only on demand, not in advance. When a context switch
occurs, the operating system does not copy any of the old program’s pages out to the disk or any
of the new program’s pages into the main memory Instead, it just begins executing the new
program after loading the first page and fetches that program’s pages as they are referenced.
While executing a program, if the program references a page which is not available in the main
memory because it was swapped out a little ago, the processor treats this invalid memory reference
as a page fault and transfers control from the program to the operating system to demand the page
back into the memory

1
4
Advantages

Following are the advantages of Demand Paging −

• Large virtual memory.

• More efficient use of memory.
• There is no limit on degree of multiprogramming.
Disadvantages

Number of tables and the amount of processor overhead for handling page interrupts are
greater than in the case of the simple paged management techniques

Page fault

1
4
A page fault occurs when a program attempts to access a block of memory that is not stored in the
physical memory, or RAM. The fault notifies the operating system that it must locate the data in
virtual memory, then transfer it from the storage device, such as an HDD or SSD, to the system
RAM. So when page fault occurs then following sequence of events happens:

• The computer hardware traps to the kernel and program counter (PC) is saved on the stack.
Current instruction state information is saved in CPU registers.
• An assembly program is started to save the general registers and other volatile information to
keep the OS from destroying it.
• Operating system finds that a page fault has occurred and tries to find out which virtual page
is needed. Sometimes hardware register contains this required information. If not, the operating
system must retrieve PC, fetch instruction and find out what it was doing when the fault
occurred.
• Once virtual address caused page fault is known, system checks to see if address is valid and
checks if there is no protection access problem.
• If the virtual address is valid, the system checks to see if a page frame is free. If no frames are
free, the page replacement algorithm is run to remove a page.
• If frame selected is dirty, page is scheduled for transfer to disk, context switch takes place,
fault process is suspended and another process is made to run until disk transfer is completed.
• As soon as page frame is clean, operating system looks up disk address where needed page is,
schedules disk operation to bring it in.
1
4
• When disk interrupt indicates page has arrived, page tables are updated to reflect its position,
and frame marked as being in normal state.
• Faulting instruction is backed up to state it had when it began and PC is reset. Faulting is
scheduled, operating system returns to routine that called it.
• Assembly Routine reloads register and other state information, returns to user space to continue
execution.

Page Replacement Algorithm

Page Replacement Algorithm decides which page to remove, also called swap out when a new
page needs to be loaded into the main memory. Page Replacement happens when a requested page
is not present in the main memory and the available space is not sufficient for allocation to the
requested page.
A page replacement algorithm tries to select which pages should be replaced so as to minimize the
total number of page misses. There are many different page replacement algorithms. These
algorithms are evaluated by running them on a particular string of memory reference and
computing the number of page faults. The fewer is the page faults the better is the algorithm for
that situation. Some Page Replacement Algorithms :

• First In First Out (FIFO)

• Least Recently Used (LRU)
• Optimal Page Replacement (OPR)

First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm, the OS maintains a queue that
keeps track of all the pages in memory, with the oldest page at the front and the most recent page
at the back. When there is a need for page replacement, the FIFO algorithm, swaps out the page at
the front of the queue, that is the page which has been in the memory for the longest time.

For Example:
Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3 page frames. Find number of page faults

1
4
 .

Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page
Faults. When 3 comes, it is already in memory so —> 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —>1 Page
Fault. 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 —>1
Page Fault. Finally when 3 come it is not avilable so it replaces 0 1 page fault

Advantages

• Simple and easy to implement.

• Low overhead.
Disadvantages

• Poor performance.
• Doesn’t consider the frequency of use or last used time, simply replaces the oldest page.
• Suffers from Belady’s Anomaly (i.e. more page faults when we increase the number of
page frames).

Least Recently Used (LRU)

Least Recently Used page replacement algorithm keeps track of page usage over a short period
of time. It works on the idea that the pages that have been most heavily used in the past are most
likely to be used heavily in the future too.

In LRU, whenever page replacement happens, the page which has not been used for the longest
amount of time is replaced.
For Example:
Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frames. Find
number of page faults.

1
4
Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults 0 is
already their so —> 0 Page fault. When 3 came it will take the place of 7 because it is least recently
used —>1 Page fault 0 is already in memory so —> 0 Page fault. 4 will takes place of 1 —> 1
Page Fault Now for the further page reference string —> 0 Page fault because they are already
available in the memory. Advantages

• Efficient.
• Doesn't suffer from Belady’s Anomaly.
Disadvantages

• Complex Implementation.
• Expensive.
• Requires hardware support.

Optimal Page Replacement

Optimal Page Replacement algorithm is the best page replacement algorithm as it gives the least
number of page faults. It is also known as OPT, clairvoyant replacement algorithm, or Belady’s
optimal page replacement policy.

In this algorithm, pages are replaced which would not be used for the longest duration of time in
the future, i.e., the pages in the memory which are going to be referred farthest in the future are
replaced.
This algorithm was introduced long back and is difficult to implement because it requires future
knowledge of the program behaviour. However, it is possible to implement optimal page
replacement on the second run by using the page reference information collected on the first run.

For Example
Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frame. Find number
of page fault.

1
4
Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults 0 is
already there so —> 0 Page fault. When 3 came it will take the place of 7 because it is not used
for the longest duration of time in the future.—>1 Page fault. 0 is already there so —> 0 Page
fault. 4 will takes place of 1 —> 1 Page Fault. Now for the further page reference string —> 0
Page fault because they are already available in the memory. Advantages

• Easy to Implement.
• Simple data structures are used.
• Highly efficient.
Disadvantages

• Requires future knowledge of the program.

• Time-consuming.

Consider a reference string: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2. the number of frames in the memory is 3.

Find out the number of page faults respective to:

1. Optimal Page Replacement Algorithm

2. FIFO Page Replacement Algorithm
3. LRU Page Replacement Algorithm

Optimal Page Replacement Algorithm

1
4
Number of Page Faults in Optimal Page Replacement Algorithm = 5

LRU Page Replacement Algorithm

Number of Page Faults in LRU = 6

FIFO Page Replacement Algorithm

Number of Page Faults in FIFO = 6

1
4
Thrashing

Thrashing in computing is an issue caused when virtual memory is in use. It occurs when the virtual
memory of a computer is rapidly exchanging data for data on hard disk, to the exclusion of most
application-level processing. As the main memory gets filled, additional pages need to be swapped
in and out of virtual memory. The swapping causes a very high rate of hard disk access. Thrashing
can continue for a long duration until the underlying issue is addressed. Thrashing can potentially
result in total collapse of the hard drive of the computer. Thrashing is also known as disk thrashing.

Fig: Thrashing

Techniques to Handle Thrashing

We already seen Local replacement is better than Global replacement to avoid thrashing. But it
also has disadvantages and not suggestable. Some more techniques are

Working Set Model

This model is based on locality. What locality is saying, the page used recently can be used again
and also the pages which are nearby this page will also be used. Working set means set of pages
in the most recent D time. The page which completed its D amount of time in working set
automatically dropped from it. So accuracy of working set depends on D we have chosen. This
working set model avoid thrashing while keeping the degree of multiprogramming as high as
possible.

Page Fault Frequency

1
4
It is some direct approach than working set model. When thrashing occurring we know that it has
few number of frames. And if it is not thrashing that means it has too many frames. Based on this
property we assign an upper and lower bound for the desired page fault rate. According to page
fault rate we allocate or remove pages. If the page fault rate become less than the lower limit,
frames can be removed from the process. Similarly, if the page fault rate become more than the
upper limit, more number of frames can be allocated to the process. And if no frames available
due to high page fault rate, we will just suspend the processes and will restart them again when
frames available.
Segmentation

Segmentation is a technique of memory management. It is just like the Paging technique except
the fact that in segmentation, the segments are of variable length but, in Paging, the pages are of
fixed size. In segmentation, the memory is split into variable-length parts. Each part is known as
segments. The information which is related to the segment is stored in a table which is called a
segment table.

There are types of segmentation:

1. Virtual memory segmentation –
Each process is divided into a number of segments, not all of which are resident at any one
point in time.
2. Simple segmentation –
Each process is divided into a number of segments, all of which are loaded into memory at run
time, though not necessarily contiguously.

There is no simple relationship between logical addresses and physical addresses in segmentation.
A table stores the information about all such segments and is called Segment Table.

1
4
Segment Table – It maps two-dimensional Logical address into one-dimensional Physical address.
It’s each table entry has:
• Base Address: It contains the starting physical address where the segments reside in memory.
• Limit: It specifies the length of the segment.

Advantages of Segmentation

1. No internal fragmentation.
2. Average Segment Size is larger than the actual page size.
3. Less overhead.
4. It is easier to relocate segments than entire address space.
5. The segment table is of lesser size as compare to the page table in paging.

Disadvantages of Segmentation

1. It can have external fragmentation.

2. It is difficult to allocate contiguous memory to variable sized partition.
3. Costly memory management algorithms.

1
5
 Fig: Logical view of segmentation

Difference between Paging and Segmentation

Paging Segmentation

1. In paging, program is divided into fixed or 1. In segmentation, program is divided into

mounted size pages variable size sections.
2. For paging operating system is 2. For segmentation compiler is accountable.
accountable.
3. Page size is determined by hardware. 3. Here, the section size is given by the user.

4. It is faster in the comparison of 4. Segmentation is slow.

segmentation
.
5. Paging could result in internal 5. Segmentation could result in external
fragmentation fragmentation.
.
6. In paging, logical address is split into page

1
5
 number and page offset. 6. Here, logical address is split into section
number and section offset.
7. Paging comprises a page table which 7. While segmentation also comprises the encloses the
base address of every page. segment table which encloses segment number and segment
offset.
8. Paging is invisible to the user. 8. Segmentation is visible to the user.

Segmentation with paging (MULTICS)

Instead of an actual memory location the segment information includes the address of a page table
for the segment. When a program references a memory location the offset is translated to a memory
address using page table. A segment can be extended simply by allocating another memory page
and adding it to the segment’s page table.

An implementation of virtual memory on a system using segmentation with paging usually only
moves individual pages back and forth between main memory and secondary storage, similar to a
paged non-segmented system. Pages of the segment can be located anywhere in main memory and
need not be contiguous. This usually results in a reduced amount of input/output between primary
and secondary storage and reduced memory fragmentation.

The MULTICS (Multiplexed Information and Computing Service) operating system was one of
the most influential operating systems ever, having had a major influence on topics as disparate as
UNIX, the x86 memory architecture, TLBs, and cloud computing. It was started as research project
at MIT and went live in 1969. The MULTICS system solved problems of external fragmentation
and lengthy search times by paging the segments.

1
5
 Unit-6
Input/Output Device Management
Principles of I/O Hardware
Different people look at I/O hardware in different ways. Electrical engineers look at it in terms of
chips, wires, power supplies, motors, and all the other physical components that make up the
hardware. Programmers look at the interface presented to the software the commands the hardware
accepts, the functions it carries out, and the errors that can be reported back. Nevertheless, the
programming of many I/O devices is often intimately connected with their internal operation.

I/O devices
I/O devices can be roughly divided into two categories: block devices and character devices. A
block device is one that stores information in fixed-size blocks, each one with its own address.
Common block sizes range from 512 bytes to 32,768 bytes. The essential property of a block device
is that it is possible to read or write each block independently of all the other ones. Disks are the
most common block devices.
If you look closely, the boundary between devices that are block addressable and those that are not
is not well defined. Everyone agrees that a disk is a block addressable device because no matter
where the arm currently is, it is always possible to seek to another cylinder and then wait for the
required block to rotate under the head. Now consider a tape drive used for making disk backups.
Tapes contain a sequence of blocks. If the tape drive is given a command to read block N, it can
always rewind the tape and go forward until it comes to block N. This operation is analogous to a
disk doing a seek, except that it takes much longer. Also, it may or may not be possible to rewrite
one block in the middle of a tape. Even if it were possible to use tapes as random access block
devices, that is stretching the point somewhat: they are not normally used that way.
The other type of I/O device is the character device. A character device delivers or accepts a stream
of characters, without regard to any block structure. It is not addressable and does not have any
seek operation. Printers, network interfaces, mice (for pointing), rats (for psychology lab
experiments), and most other devices that are not disk-like can be seen as character devices.
This classification scheme is not perfect. Some devices just do not fit in. Clocks, for example, are
not block addressable. Nor do they generate or accept character streams. All they do is cause
interrupts at well-defined intervals. Still, the model of block and character devices is general
enough that it can be used as a basis for making some of the operating system software dealing
with I/O device independent. The file system, for example, deals only with abstract block devices
and leaves the device-dependent part to lower-level software called device drivers.

Device controllers
Device drivers are software modules that can be plugged into an OS to handle a particular device.
Operating System takes help from device drivers to handle all I/O devices.
The Device Controller works like an interface between a device and a device driver. I/O units
(Keyboard, mouse, printer, etc.) typically consist of a mechanical component and an electronic
component where electronic component is called the device controller.

1
5
There is always a device controller and a device driver for each device to communicate with the
Operating Systems. A device controller may be able to handle multiple devices. As an interface its
main task is to convert serial bit stream to block of bytes, perform error correction as necessary.
Any device connected to the computer is connected by a plug and socket, and the socket is
connected to a device controller. Following is a model for connecting the CPU, memory,
controllers, and I/O devices where CPU and device controllers all use a common bus for
communication.

Interrupts

Interrupts are signals sent to the CPU by external devices, normally I/O devices. They tell the CPU
to stop its current activities and execute the appropriate part of the operating system.

There are three types of interrupts:

1. Hardware Interrupts are generated by hardware devices to signal that they need
some attention from the OS. They may have just received some data (e.g.,
keystrokes on the keyboard or an data on the ethernet card); or they have just
completed a task which the operating system previous requested, such as
transferring data between the hard drive and memory.
2. Software Interrupts are generated by programs when they want to request a
system call to be performed by the operating system.
3. Traps are generated by the CPU itself to indicate that some error or condition
occurred for which assistance from the operating system is needed.
Interrupts are important because they give the user better control over the computer. Without
interrupts, a user may have to wait for a given application to have a higher priority over the CPU
to be ran. This ensures that the CPU will deal with the process immediately.

Working mechanism of Interrupts

When I/O device has finished the work given to it, it causes an interrupt. It does this by asserting
a signal on a bus, that it has been assigned. The signal detected by the interrupt controller then
decides what to do? If no other interrupts are pending, the interrupt controller processes the

1
5
interrupts immediately, if another is in progress, then it is ignored for a moment.
To handle the interrupt, the controller puts a number of address line specifying which device wants
attention and asserts a signal that interrupt the CPU. The number of address lines is used as index
to a table called interrupt vector to fetch a new program counter, this program counter points to the
start of corresponding service procedure.

Memory Mapped I/O

When using memory-mapped I/O, the same address space is shared by memory and I/O devices.
The device is connected directly to certain main memory locations so that I/O device can transfer
block of data to/from memory without going through CPU.
While using memory mapped IO, OS allocates buffer in memory and informs I/O device to use
that buffer to send data to the CPU. I/O device operates asynchronously with CPU, interrupts CPU
when finished.
The advantage to this method is that every instruction which can access memory can be used to
manipulate an I/O device. Memory mapped IO is used for most high-speed I/O devices like disks,
communication interfaces.

Goals of IO Software
There are many goals of I/O software. Some of major principles of I/O software are listed below:

a. Device independence

A key concept in the design of I/O software is known as device independence. It means
that I/O devices should be accessible to programs without specifying the device in advance.
For example, a program that reads a file as input should be able to read a file on a floppy
disk, on a hard disk, or on a CD-ROM, without having to modify the program for each
different device.
1
5
 b. Uniform naming
Uniform Naming, simply be a string or an integer and not depend on the device in any way.
In UNIX, all disks can be integrated in the file-system hierarchy in arbitrary ways so the
user need not be aware of which name corresponds to which device. Here the name of file
or device should be some specific string or number. It must not depend upon device in any
way. All files and devices are addressed the same way: by a path name.
c. Error handling
Generally, errors should be handled as close as possible to the computer hardware. It should
try to correct the error itself if it can in case if the controller discovers a read error. And in
case if it can’t then the device driver should handle it. If the controller discovers a read
error, it should try to correct the error itself if it can. If it cannot, then the device driver
should handle it, perhaps by just trying to read the block again. In many cases, error
recovery can be done transparently at a low level without the upper levels even knowing
about the error.

d. Synchronous vs. Asynchronous transfers

Most physical input/output is asynchronous however some very high performance
applications need to control all the details of the I/O, so some operating systems make
asynchronous I/O available to them. The central processing unit starts the transfer and goes off
to do something other until the interrupt arrives. In case if input/output operations are blocking
the user programs are much easier to write. After a read system call the program is
automatically suspended until the data are available in buffer. Basically, it is up to the OS to
make the operation that are really asynchronous look blocking to the user programs. e.
Buffering Sometime data that come off a device can’t be stored directly in its final destination.
Buffering sometime has a major impact on the systems input/output performance because it
involves considerable copying.
Data comes in main memory cannot be stored directly. For example, data packets come
from the network cannot be directly stored in physical memory. Packet to be put into output
buffer for examining them. Some devices have several real-time constraints, so data must
be put into output buffer in advance to decouple the rate at which buffer is filled and the
rate at which it is emptied, in order to avoid buffer under runs.
f. Sharable and Dedicated devices
Some I/O devices, such as disks, can be used by many users at the same time. No problems
are caused by multiple users having open files on the same disk at the same time. Other
devices, such as printers, have to be dedicated to a single user until that user is finished.
Then another user can have the printer. Introducing dedicated (unshared) devices also
introduces a variety of problems, such as deadlocks. Again, the operating system must be
able to handle both shared and dedicated devices in a way that avoids problems.

Programmed IO
Programmable I/O is one of the I/O technique other than the interrupt-driven I/O and direct
memory access (DMA). The programmed I/O was the simplest type of I/O technique for the
exchanges of data or any types of communication between the
1
5
processor and the external devices. With programmed I/O, data are exchanged between the
processor and the I/O module. The processor executes a program that gives it direct control of the
I/O operation, including sensing device status, sending a read or write command, and transferring
the data. When the processor issues a command to the I/O module, it must wait until the I/O
operation is complete. If the processor is faster than the I/O module, this is wasteful of processor
time. The overall operation of the programmed I/O can be summaries as follow:

1. The processor is executing a program and encounters an instruction relating to I/O

operation.
2. The processor then executes that instruction by issuing a command to the appropriate I/O
module.
3. The I/O module will perform the requested action based on the I/O command issued by the
processor (READ/WRITE) and set the appropriate bits in the I/O status register.
4. The processor will periodically check the status of the I/O module until it find that the
operation is complete.

Advantages
• Simple to implement
• Very little hardware support

Disadvantages
• Busy waiting
• Ties up CPU for long period with no useful work

Interrupt driven IO
This mode uses an interrupt facility and special commands to inform the interface to issue the
interrupt command when data becomes available and interface is ready for the data transfer. In the
meantime, CPU keeps on executing other tasks and need not check for the flag. When the flag is
set, the interface is informed and an interrupt is initiated. This interrupt causes the CPU to deviate
from what it is doing to respond to the I/O transfer. The CPU responds to the signal by storing the
return address from the program counter (PC) into the memory stack and then branches to service
that processes the I/O request. After the transfer is complete, CPU returns to the previous task it
was executing. The branch address of the service can be chosen in two ways known as vectored
and non-vectored interrupt. In vectored interrupt, the source that interrupts, supplies the branch
information to the CPU while in case of non-vectored interrupt the branch address is assigned to a
fixed location in memory.

Difference between Programmed IO and Interrupt driven IO

Programmed IO Interrupt driven IO

1
5
 1. Data transfer is initiated by the means of 1. The I/O transfer is initiated by the interrupt
instructions stored in the computer command issued to the CPU.
program. Whenever there is a request for
I/O transfer the instructions are executed
from the program.
2. The CPU stays in the loop to know if the 2. There is no need for the CPU to stay in the
device is ready for transfer and has to loop as the interrupt command interrupts
continuously monitor the peripheral the CPU when the device is ready for data
device. transfer.
3. This leads to the wastage of CPU cycles as 3. The CPU cycles are not wasted as CPU and
CPU remains busy needlessly and thus the hence this method is more efficient.
efficiency of system gets reduced.
4. CPU cannot do any work until the transfer 4. CPU can do any other work until it is
is complete as it has to stay in the loop to interrupted by the command indicating the
continuously monitor the peripheral readiness of device for data transfer.
device.
5. Its module is treated as a slow module. 5. Its module is faster than programmed I/O
module.
6. It is quite easy to program and understand. 6. It can be tricky and complicated to
understand if one uses low level language.

DMA (Direct Memory Access)

DMA is a mechanism that provides a device controller the ability to transfer data directly to or
from the memory without involving the processor. When large volumes of data are to be moved,
a more efficient technique is required: direct memory access (DMA).

DMA can save processing time and is a more efficient way to move data from the computer’s
memory to other devices. In order for devices to use direct memory access, they must be assigned
to a DMA channel. Each type of port on a computer has a set of DMA channels that can be assigned
to each connected device. For example, a PCI controller and a hard drive controller each have their
own set of DMA channels.

1
5
 Fig: Block diagram of DMA
Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write to
memory without involvement. DMA module itself controls exchange of data between main
memory and the I/O device. CPU is only involved at the beginning and end of the transfer and
interrupted only after entire block has been transferred. Direct Memory Access needs a special
hardware called DMA controller (DMAC) that manages the data transfers and arbitrates access to
the system bus. The controllers are programmed with source and destination pointers (where to
read/write the data), counters to track the number of transferred bytes, and settings, which includes
I/O and memory types, interrupts and states for the CPU cycles.

Working procedure of DMA

• The CPU programs the DMA controller by its registers so it knows what to transfer where.
It also issues a command to disk controller telling it to read data from disk to its internal
buffer and verify the checksum. When valid data are in disk’s controller buffer, DMA can
begin.
• The DMA controller initiates the transfer by issuing a read request over the bus to disk
controller.
• Data transferred from disk controller to memory.
• When transferred completed, the disk controller sends an acknowledgement signal to DMA
controller. The DMA controller then increments the memory address to use and decrement
the byte count. This continues until the byte count greater than 0.
• When transfer completed the DMA controller interrupt the CPU.

I/O software layers

Basically, input/output software organized in the following four layers:

• Interrupt handlers

1
5
 • Device drivers
• Device-independent input/output software
• User-space input/output software

In every input/output software, each of the above given four layer has a well-defined function to
perform and a well-defined interface to the adjacent layers. The figure given below shows all the
layers along with hardware of the input/output software system.

Here is another figure shows all the layers of the input/output software system along with their
principal functions.

Interrupt Handlers

Whenever the interrupt occurs, then the interrupt procedure does whatever it has to in order to
handle the interrupt.

Device Drivers

1
6
Basically, device driver is a device-specific code just for controlling the input/output device that
are attached to the computer system.

Device-Independent Input/Output Software

In some of the input/output software is device specific, and other parts of that input/output software
are device-independent.

The exact boundary between the device-independent software and drivers is device dependent, just
because of that some functions that could be done in a device-independent way sometime be done
in the drivers, for efficiency or any other reasons.

Here are the list of some functions that are done in the device-independent software:
• Uniform interfacing for device drivers
• Buffering
• Error reporting
• Allocating and releasing dedicated devices
• Providing a device-independent block size

User-Space Input/Output Software

Generally most of the input/output software is within the operating system (OS), and some small
part of that input/output software consists of libraries that are linked with the user programs and
even whole programs running outside the kernel.

Disk structure

In modern computers, most of the secondary storage is in the form of magnetic disks. Hence,
knowing the structure of a magnetic disk is necessary to understand how the data in the disk is
accessed by the computer.

A magnetic disk contains several platters. Each platter is divided into circular shaped tracks. The
length of the tracks near the centre is less than the length of the tracks farther from the centre. Each
track is further divided into sectors, as shown in the figure.
Tracks of the same distance from centre form a cylinder. A read-write head is used to read data
from a sector of the magnetic disk.
The speed of the disk is measured as two parts:

• Transfer rate: This is the rate at which the data moves from disk to the computer.
• Random access time: It is the sum of the seek time and rotational latency.

1
6
Seek time is the time taken by the arm to move to the required track. Rotational latency is defined
as the time taken by the arm to reach the required sector in the track.
Even though the disk is arranged as sectors and tracks physically, the data is logically arranged and
addressed as an array of blocks of fixed size. The size of a block can be 512 or 1024 bytes. Each
logical block is mapped with a sector on the disk, sequentially. In this way, each sector in the disk
will have a logical address.

Fig: structure of a magnetic disk

Disk structure key terms

• Seek Time: Seek time is the time taken to locate the disk arm to a specified track where the
data is to be read or write. So the disk scheduling algorithm that gives minimum average seek
time is better.
• Rotational Latency: Rotational Latency is the time taken by the desired sector of disk to
rotate into a position so that it can access the read/write heads. So the disk scheduling
algorithm that gives minimum rotational latency is better.
• Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed
of the disk and number of bytes to be transferred.
• Disk Access Time: Disk Access Time is:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
• Disk Response Time: Response Time is the average of time spent by a request waiting to
perform its I/O operation. Average Response time is the response time of the all requests.
Variance Response Time is measure of how individual request are serviced with respect to

1
6
 average response time. So the disk scheduling algorithm that gives minimum variance response
time is better.
• Transmission Time: To access a particular record, first the arm assembly must be moved to
the appropriate cylinder, and then rotate the disk until it is immediately under the read write
head. The time taken to access the whole record is called transmission time.

Disk Scheduling
Various disk scheduling algorithms are:
1. First Come-First Serve (FCFS)

2. Shortest Seek Time First (SSTF)

3. Elevator (SCAN)

4. Circular SCAN (C-SCAN)

5. LOOK

6. C-LOOK

1. First Come-First Serve (FCFS)

FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed
in the order they arrive in the disk queue. Let us understand this with the help of an example.
Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50

1
6
Advantages:
• Every request gets a fair chance No indefinite postponement Disadvantages:
• Does not try to optimize seek time
• May not provide the best possible service

2. Shortest Seek Time First (SSTF)

In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the
seek time of every request is calculated in advance in the queue and then they are scheduled
according to their calculated seek time. As a result, the request near the disk arm will get executed
first. SSTF is certainly an improvement over FCFS as it decreases the average response time and
increases the throughput of system. Let us understand this with the help of an example.

Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50

1
6
Advantages:
• Average Response Time decreases Throughput increases Disadvantages:
• Overhead to calculate seek time in advance
• Can cause Starvation for a request if it has higher seek time as compared to incoming requests
• High variance of response time as SSTF favours only some requests

3. Elevator (SCAN)

In SCAN algorithm the disk arm moves into a particular direction and services the requests coming
in its path and after reaching the end of disk, it reverses its direction and again services the request
arriving in its path. So, this algorithm works as an elevator and hence also known as elevator
algorithm. As a result, the requests at the midrange are serviced more and those arriving behind
the disk arm will have to wait.
Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at
50, and it is also given that the disk arm should move “towards the larger value”.

1
6
Therefore, the seek time is calculated as:
=(199-50)+(199-16) =332
Advantages:
• High throughput
• Low variance of response time Average response time Disadvantages:
• Long waiting time for requests for locations just visited by disk arm

4. Circular SCAN (C-SCAN)

In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its
direction. So, it may be possible that too many requests are waiting at the other end or there may
be zero or few requests pending at the scanned area.
These situations are avoided in CSCAN algorithm in which the disk arm instead of reversing its
direction goes to the other end of the disk and starts servicing the requests from there. So, the disk
arm moves in a circular fashion and this algorithm is also similar to SCAN algorithm and hence it
is known as C-SCAN (Circular SCAN).
Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at
50, and it is also given that the disk arm should move “towards the larger value”.

1
6
Advantages:
Provides more uniform wait time compared to SCAN

5. LOOK

It is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in
spite of going to the end of the disk goes only to the last request to be serviced in front of the head
and then reverses its direction from there only. Thus it prevents the extra delay which occurred
due to unnecessary traversal to the end of the disk.

Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at
50, and it is also given that the disk arm should move “towards the larger value”.

1
6
6. C-LOOK

As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk
scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes only to the last
request to be serviced in front of the head and then from there goes to the other end’s last request.
Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the
disk.
Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at
50, and it is also given that the disk arm should move “towards the larger value”

1
6
So, the seek time is calculated as:
=(190-50)+(190-16)+(43-16)
=341

1
6
 Unit-7
File System Interface Management
File concept
A file is a collection of correlated information which is recorded on secondary or non-volatile
storage like magnetic disks, optical disks, and tapes. It is a method of data collection that is used
as a medium for giving input and receiving output from that program.

In general, a file is a sequence of bits, bytes, or records whose meaning is defined by the file creator
and user. Every File has a logical location where they are located for storage and retrieval.

Objective of file management

• It provides I/O support for a variety of storage device types.
• Minimizes the chances of lost or destroyed data
• Helps OS to standardized I/O interface routines for user processes.
• It provides I/O support for multiple users in a multiuser systems environment

File structure
A File Structure needs to be predefined format in such a way that an operating system understands.
It has an exclusively defined structure, which is based on its type.

Three types of files structure in OS:

• A text file: It is a series of characters that is organized in lines.

• An object file: It is a series of bytes that is organized into blocks. A
source file: It is a series of functions and processes.

File type
It refers to the ability of the operating system to differentiate various types of files like text files,
binary, and source files.

The system uses the extension to indicate the type of the file and the type of operations that can be
done on that file. Only a file with a .com, .exe, or .sh extension can be executed, for instance. The
.com and .exe files are two forms of binary executable files, whereas the .sh file is a shell script
containing, in ASCII format, commands to the operating system. Application programs also use
extensions to indicate file types in which they are interested. For example, Java compilers expect
source files to have a .java extension, and the Microsoft Word processor expects its files to end
with a .doc or .docx extension. These extensions are not always required, so a user may specify a
file without the extension (to save typing), and the application will look for a file with the given
name and the extension it expects. Because these extensions are not supported by the operating
system, they can be considered “hints” to the applications that operate on them.

1
7
 Fig: Common file types

File access methods

The information stored in a file must be accessed and read into memory. Though there are many
ways to access a file, some system provides only one method, other systems provide many
methods, out of which you must choose the right one for the application.

1. Sequential Access Method

In this method, the information in the file is processed in order, one record after another. For
example, compiler and various editors access files in this manner.

The read-next – reads the next portion of a file and updates the file pointer which tracks the I/O
location. Similarly, the write-next will write at the end of a file and advances the pointer to the new
end of the file.

1
7
 2. Direct Access Method

The other method for file access is direct access or relative access. For direct access, the file is
viewed as a numbered sequence of blocks or records. This method is based on the disk model of
file. Since disks allow random access to file block.

You can read block 34, then read 45, and write in block 78, there is no restriction on the order of
access to the file. The direct access method is used in database management. A query is satisfied
immediately by accessing large amount of information stored in database files directly. The
database maintains an index of blocks which contains the block number. This block can be
accessed directly and information is retrieved.
3. Indexed sequential access method

1
7
It is the other method of accessing a file which is built on the top of the sequential access method.
These methods construct an index for the file. The index, like an index in the back of a book,
contains the pointer to the various blocks. To find a record in the file, we first search the index and
then by the help of pointer we access the file directly.

File allocation methods

The allocation methods define how the files are stored in the disk blocks. There are three main disk
space or file allocation methods.

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation
The main idea behind these methods is to provide:
• Efficient disk space utilization. Fast access to the file blocks.

1. Contiguous Allocation
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file
requires n blocks and is given a block b as the starting location, then the blocks assigned to the file
will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the length
of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
Address of starting block Length of the allocated
portion.
The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore,
it occupies 19, 20, 21, 22, 23, 24 blocks.

Advantages:
1
7
• Both the Sequential and Direct Accesses are supported by this. For direct access, the address
of the kth block of the file which starts at block b can easily be obtained as (b+k).
• This is extremely fast since the number of seeks are minimal because of contiguous allocation
of file blocks.
Disadvantages:
• This method suffers from both internal and external fragmentation. This makes it inefficient in
terms of memory utilization.
• Increasing file size is difficult because it depends on the availability of contiguous memory at
a particular instance.

2. Linked List Allocation

In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk
blocks can be scattered anywhere on the disk. The directory entry contains a pointer to the starting
and the ending file block. Each block contains a pointer to the next block occupied by the file. The
file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25)
contains -1 indicating a null pointer and does not point to any other block.

Advantages:
• This is very flexible in terms of file size. File size can be increased easily since the system does
not have to look for a contiguous chunk of memory.
• This method does not suffer from external fragmentation. This makes it relatively better in
terms of memory utilization.
Disadvantages:
• Because the file blocks are distributed randomly on the disk, a large number of seeks are needed
to access every block individually. This makes linked allocation slower.
• It does not support random or direct access. We can not directly access the blocks of a file. A
block k of a file can be accessed by traversing k blocks sequentially (sequential access ) from
the starting block of the file via block pointers.
1
7
• Pointers required in the linked allocation incur some extra overhead.

3. Indexed Allocation
In this scheme, a special block known as the Index block contains the pointers to all the blocks
occupied by a file. Each file has its own index block. The ith entry in the index block contains the
disk address of the ith file block. The directory entry contains the address of the index block as
shown in the image:

Advantages:
• This supports direct access to the blocks occupied by the file and therefore provides fast access
to the file blocks.
• It overcomes the problem of external fragmentation.
Disadvantages:
• The pointer overhead for indexed allocation is greater than linked allocation.
• For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep
one entire block (index block) for the pointers which is inefficient in terms of memory
utilization. However, in linked allocation we lose the space of only 1 pointer per block.

File attributes

A file is named, for the convenience of its human users, and is referred to by its name. A name is
usually a string of characters, such as example.c. Some systems differentiate between uppercase
and lowercase characters in names, whereas other systems do not. When a file is named, it becomes
independent of the process, the user, and even the system that created it. For instance, one user
might create the file example.c, and another user might edit that file by specifying its name. The
file’s owner might write the file to a USB disk, send it as an e-mail attachment, or copy it across a
network, and it could still be called example.c on the destination system. A file’s attributes vary
from one operating system to another but typically consist of these:

1
7
 • Name:The symbolic file name is the only information kept in human readable form.
• Identifier: This unique tag, usually a number, identifies the file within the file system; it is
the non-human-readable name for the file.
• Type: This information is needed for systems that support different types of files.
• Location: This information is a pointer to a device and to the location of the file on that
device.
• Size: The current size of the file (in bytes, words, or blocks) and possibly the maximum
allowed size are included in this attribute.
• Protection: Access-control information determines who can do reading, writing, executing,
and so on.
• Time, date, and user identification: This information may be kept for creation, last
modification, and last use. These data can be useful for protection, security, and usage
monitoring.

File operations
A file is an abstract data type. To define a file properly, we need to consider the operations that
can be performed on files. The operating system can provide system calls to create, write, read,
reposition, delete, and truncate files. Let’s examine what the operating system must do to perform
each of these six basic file operations. It should then be easy to see how other similar operations,
such as renaming a file, can be implemented.

• Creating a file: Two steps are necessary to create a file. First, space in the file system must
be found for the file. Second, an entry for the new file must be made in the directory.
• Writing a file: To write a file, we make a system call specifying both the name of the file
and the information to be written to the file. Given the name of the file, the system searches
the directory to find the file’s location. The system must keep a write pointer to the location
in the file where the next write is to take place. The write pointer must be updated whenever
a write occurs.
• Reading a file: To read from a file, we use a system call that specifies the name of the file
and where (in memory) the next block of the file should be put. Again, the directory is
searched for the associated entry, and the system needs to keep a read pointer to the location
in the file where the next read is to take place. Once the read has taken place, the read
pointer is updated. Because a process is usually either reading from or writing to a file, the
current operation location can be kept as a per-process current file-position pointer. Both
the read and write operations use this same pointer, saving space and reducing system
complexity.
• Repositioning within a file: The directory is searched for the appropriate entry, and the
current-file-position pointer is repositioned to a given value. Repositioning within a file
need not involve any actual I/O. This file operation is also known as a file seek.
• Deleting a file: To delete a file, we search the directory for the named file. Having found
the associated directory entry, we release all file space, so that it can be reused by other
files, and erase the directory entry
• Truncating a file: The user may want to erase the contents of a file but keep its attributes.
Rather than forcing the user to delete the file and then recreate it, this function allows all
attributes to remain unchanged—except for file length—but lets the file be reset to length
zero and its file space released.

1
7
Directories
A Directory is the collection of the correlated files on the disk. In simple words, a directory is like
a container which contains file and folder. In a directory, we can store the complete file attributes
or some attributes of the file. A directory can be comprised of various files. With the help of the
directory, we can maintain the information related to the files.

There are several logical structures of directory, these are given as below:

1. Single-level directory

The single-level directory is the simplest directory structure. In it, all files are contained in the
same directory which makes it easy to support and understand.
A single level directory has a significant limitation, however, when the number of files increases
or when the system has more than one user. Since all the files are in the same directory, they must
have a unique name. if two users call their dataset test, then the unique name rule violated.

Advantages

• Since it is a single directory, so its implementation is very easy.

• If the files are smaller in size, searching will become faster.
• The operations like file creation, searching, deletion, updating are very easy in such a directory
structure.

Disadvantages:

• There may chance of name collision because two files can not have the same name.
• Searching will become time taking if the directory is large. This cannot group the
same type of files together.

2. Two-level directory
In the two-level directory structure, each user has their own user files directory (UFD). The
UFDs have similar structures, but each lists only the files of a single user. system’s master file
directory (MFD) is searches whenever a new user id=s logged in. The MFD is indexed by
username or account number, and each entry points to the UFD for that user.

1
7
Advantages:
• We can give full path like /User-name/directory-name/.
• Different users can have the same directory as well as the file name.
• Searching of files becomes easier due to pathname and user-grouping.
Disadvantages:
• A user is not allowed to share files with other users.
• Still, it not very scalable, two files of the same type cannot be grouped together in the same
user.

3. Hierarchical directory

In Hierarchical directory structure, the users can create directories under the root directory and can
also create sub-directories under this structure. As the user is free to create many subdirectories, it
can create different sub-directories for different file types.

4. Tree structure directory

1
7
Once we have seen a two-level directory as a tree of height 2, the natural generalization is to extend
the directory structure to a tree of arbitrary height. This generalization allows the user to create
their own subdirectories and to organize their files accordingly.

A tree structure is the most common directory structure. The tree has a root directory, and every
file in the system has a unique path.

Advantages:
• Very general, since full pathname can be given.
• Very scalable, the probability of name collision is less.
• Searching becomes very easy, we can use both absolute paths as well as relative.

Disadvantages:

• Every file does not fit into the hierarchical model; files may be saved into multiple directories.
• We cannot share files.
• It is inefficient, because accessing a file may go under multiple directories.

5. Acyclic graph directory

An acyclic graph is a graph with no cycle and allows us to share subdirectories and files. The same
file or subdirectories may be in two different directories. It is a natural generalization of the tree-
structured directory.

1
7
It is used in the situation like when two programmers are working on a joint project and they need
to access files. The associated files are stored in a subdirectory, separating them from other projects
and files of other programmers since they are working on a joint project so they want the
subdirectories to be into their own directories. The common subdirectories should be shared. So
here we use Acyclic directories.
It is the point to note that the shared file is not the same as the copy file. If any programmer makes
some changes in the subdirectory it will reflect in both subdirectories.

Advantages:
• We can share files.
• Searching is easy due to different-different paths.
Disadvantages:
• We share the files via linking, in case deleting it may create the problem,
• If the link is a soft link then after deleting the file we left with a dangling pointer.
• In the case of a hard link, to delete a file we have to delete all the references associated with it.

Path names
1. Absolute Path name – In this method, each file is given an absolute path name consisting
of the path from the root directory to the file. As an example, the
path /usr/ast/mailbox means that the root directory contains a subdirectory usr, which in
turn contains a subdirectory ast, which contains the file mailbox.

1
8
 Absolute path names always start at the root directory and are unique.
In UNIX the components of the path are separated by ‘/’. In Windows, the separator is ‘’.
Windows usrastmailbox
UNIX /usr/ast/mailbox
2. Relative Path name – This is used in conjunction with the concept of the working
directory (also called the current directory). A user can designate one directory as the
current working directory, in which case all path names not beginning at the root directory
are taken relative to the working directory.
For example, if the current working directory is /usr/ast, then the file whose absolute path
is /usr/ast/mailbox can be referenced simply as mailbox.
In other words, the UNIX command :cp/usr/ast/mailbox/usr/ast/mailbox.bak
and the command : cp mailbox mailbox.bak do exactly the same thing if the
working directory is /usr/ast.

Operations on directory
1. Searching

A directory can be searched for a particular file or for another directory. It can also be searched
to list all the files with the same name.

2. Creating

A new file can be created and inserted to the directory or new directory can be created keeping in
mind that its name must be unique under that particular directory.

3. Deleting

If a file is no longer needed by the user, it can be deleted from the directory. The entire directory
can also be deleted if it is not needed. An empty directory can also be deleted. When a directory
is empty it is resembled by dot and dotdot.

4. List a directory

List of all the files in the directory can be retrieved and also the contents of the directory entry, for
each file in a list. To read the list of all the files in the directory, it must be opened and after
reading the directory must be closed to free up the internal tablespace.

5. Renaming

The name of the file or a directory represents the content it holds and its use. The file or directory
can be renamed in case, the content inside or the use of file get changed. Renaming the file or
directory also changes its position inside the directory.

6. Link

1
8
The file can be allowed to appear in more than one directory. Here, the system call creates a link
between the file and the name specified by the path where the file is to appear.

7. Unlink

If the file is unlinked and is only present in one directory its directory entry is removed. If the file
appears in multiple directories, only the link is removed.

Protection
When information is stored in a computer system, we want to keep it safe from physical damage
(the issue of reliability) and improper access (the issue of protection). Reliability is generally
provided by duplicate copies of files. Many computers have systems programs that automatically
(or through computer-operator intervention) copy disk files to tape at regular intervals (once per
day or week or month) to maintain a copy should a file system be accidentally destroyed. File
systems can be damaged by hardware problems (such as errors in reading or writing), power surges
or failures, head crashes, dirt, temperature extremes, and vandalism. Files may be deleted
accidentally.
Protection can be provided in many ways. For a single-user laptop system, we might provide
protection by locking the computer in a desk drawer or file cabinet. In a larger multiuser system,
however, other mechanisms are needed.

Types of Access
The need to protect files is a direct result of the ability to access files. Systems that do not permit
access to the files of other users do not need protection. Thus, we could provide complete
protection by prohibiting access. Alternatively, we could provide free access with no protection.
Both approaches are too extreme for general use. What is needed is controlled access. Protection
mechanisms provide controlled access by limiting the types of file access that can be made. Access
is permitted or denied depending on several factors, one of which is the type of access requested.
Several different types of operations may be controlled:
• Read. Read from the file.
• Write. Write or rewrite the file.
• Execute. Load the file into memory and execute it.
• Append. Write new information at the end of the file.
• Delete. Delete the file and free its space for possible reuse. List. List the name and
attributes of the file.
Other operations, such as renaming, copying, and editing the file, may also be controlled. For many
systems, however, these higher-level functions may be implemented by a system program that
makes lower-level system calls. Protection is provided at only the lower level. For instance,
copying a file may be implemented simply by a sequence of read requests. In this case, a user with
read access can also cause the file to be copied, printed, and so on.

Access control

The most common approach to the protection problem is to make access dependent on the identity
of the user. Different users may need different types of access to a file or
1
8
directory. The most general scheme to implement identity dependent access is to associate with
each file and directory an access-control list (ACL) specifying user names and the types of access
allowed for each user. When a user requests access to a particular file, the operating system checks
the access list associated with that file. If that user is listed for the requested access, the access is
allowed. Otherwise, a protection violation occurs, and the user job is denied access to the file.

This approach has the advantage of enabling complex access methodologies. The main problem
with access lists is their length. If we want to allow everyone to read a file, we must list all users
with read access. This technique has two undesirable consequences:

• Constructing such a list may be a tedious and unrewarding task, especially if we do not
know in advance the list of users in the system.
• The directory entry, previously of fixed size, now must be of variable size, resulting in
more complicated space management.

These problems can be resolved by use of a condensed version of the access list. To condense the
length of the access-control list, many systems recognize three classifications of users in
connection with each file:

• Owner. The user who created the file is the owner.

• Group. A set of users who are sharing the file and need similar access is a group, or work
group.
• Universe. All other users in the system constitute the universe.
Access control matrix
An access control matrix is a table that defines access permissions between specific subjects and
objects. A matrix is a data structure that acts as a table lookup for the operating system. It is a
matrix that has specific access permissions defined by user and detailing what actions they can
perform.

Unit-8 Security
Management
Introduction
Security refers to providing a protection system to computer system resources such as CPU,
memory, disk, software programs and most importantly
1
8
data/information stored in the computer system. If a computer program is run by an unauthorized
user, then he/she may cause severe damage to computer or data stored in it. So a computer system
must be protected against unauthorized access, malicious access to system memory, viruses,
worms etc.
OS security encompasses many different techniques and methods which ensure safety from threats
and attacks. OS security allows different applications and programs to perform required tasks and
stop unauthorized interference.

OS security may be approached in many ways, including adherence to the following:

• Performing regular OS patch updates

• Installing updated antivirus engines and software
• Scrutinizing all incoming and outgoing network traffic through a firewall
• Creating secure accounts with required privileges only (i.e., user management)

Security problems
Security must consider external environment of the system and protect the system resources.
Crackers attempt to break security. Threat is potential security violation. Attack can be accidental
or malicious. Easier to protect against accidental than malicious misuse. There are various security
problems in operating system out of them major security problems are listed below:
• User authentication
• Program threats
• System threats

User authentication
Authentication refers to identifying each user of the system and associating the executing programs
with those users. It is the responsibility of the Operating System to create a protection system
which ensures that a user who is running a particular program is authentic. a. Passwords
The most common approach to authenticating a user identity is the use of passwords. When the
user identifies herself by user ID or account name, she is asked for a password. If the user-supplied
password matches the password stored in the system, the system assumes that the account is being
accessed by the owner of that account. Passwords are often used to protect objects in the computer
system, in the absence of more complete protection schemes.

They can be considered a special case of either keys or capabilities. For instance, a password could
be associated with each resource (such as a file). Whenever a request is made to use the resource,
the password must be given. If the password is correct, access is granted. Different passwords may
be associated with different access rights.

For example, different passwords may be used for reading files, appending files, and updating
files. In practice, most systems require only one password for a user to gain full rights. Although
more passwords theoretically would be more secure, such systems tend not to be implemented due
to the classic trade-off between security and convenience. If security makes something

1
8
inconvenient, then the security is frequently bypassed or otherwise circumvented. b. Password
Vulnerabilites
Vulnerability is a cyber-security term that refers to a defect in a system that can leave it open to
attack. Vulnerability may also refer to any type of weakness in a computer system itself, in a set
of procedures, or in anything that leaves information security exposed to a threat.

Strong protection starts with strong passwords. Use a variety of lowercase and uppercase letters,
numbers, characters and symbols; the more jumbled the better. And, be sure to change them every
few months. Never use combinations that include personal information or are easy to guess, like
the website name, your name, birthday, or social security number. Don’t use the same password
for more than one account. It seems like the easy choice, but it comes with risks. If a hacker does
get into one of your accounts, then they will be able to access all the other ones with the same
login.
c. Encrypted Password
Encryption is the process of encoding a message or information in such a way that only authorized
parties can access it and those who are not authorized cannot.
Using one-way encryption formats, user passwords may be encrypted and stored the directory,
which prevents clear passwords from being accessed by any users including the system
administrators. Using two-way encryption formats, passwords are encrypted while stored in the
database, and decrypted when returned to an authorized client. Use of two-way encryption protects
the password stored in the database.

d. One Time Password and Biometrics Password

One-time passwords provide additional security along with normal authentication. In One-Time
Password system, a unique password is required every time user tries to login into the system.
Once a one-time password is used, then it cannot be used again. One-time password are
implemented in various ways.
• Random numbers − Users are provided cards having numbers printed along with
corresponding alphabets. System asks for numbers corresponding to few alphabets
randomly chosen.
• Secret key − User are provided a hardware device which can create a secret id mapped
with user id. System asks for such secret id which is to be generated every time prior to
login.
• Network password − Some commercial applications send one-time passwords to user on
registered mobile/ email which is required to be entered prior to login.
e. User Authorizations

Authorization is a security mechanism used to determine user/client privileges or access levels

related to system resources, including computer programs, files, services, data and application
features. Authorization is normally preceded by authentication for user identity verification.
System administrators (SA) are typically assigned permission levels covering all system and user
resources.

1
8
During authorization, a system verifies an authenticated user's access rules and either grants or
refuses resource access.

Program Threats

Operating system's processes and kernel do the designated task as instructed. If a user program
made these process do malicious tasks, then it is known as Program Threats. One of the common
example of program threat is a program installed in a computer which can store and send user
credentials via network to some hacker. Following is the list of some well-known program threats.
a. Trojan Horse
Trojan horse is a program downloaded and installed on a computer that appears harmless, but is,
in fact, malicious. Unexpected changes to computer settings and unusual activity, even when the
computer should be idle, are strong indications that a Trojan is residing on a computer.

Typically, the Trojan horse is hidden in an innocent-looking email attachment or free download.
When the user clicks on the email attachment or downloads the free program, the malware that is
hidden inside is transferred to the user's computing device. Once inside, the malicious code can
execute whatever task the attacker designed it to carry out.

The easiest way to protect a system from a Trojan horse is by never opening or downloading emails
or attachments from unknown sources. Deleting these messages before opening will delete the
Trojan horse threat

b. Trap Door
Trapdoor- is a method of gaining access to some part of a system other than by the normal
procedure (e.g. gaining access without having to supply a password). Hackers who successfully
penetrate a system may insert trapdoors to allow them entry at a later date, even if the vulnerability
that they originally exploited is closed. There have also been instances of system developers
leaving debug trapdoors in software, which are then discovered and exploited by hackers.

c. Stack and buffer overflow

A buffer is a temporary area for data storage. When more data (than was originally allocated to be
stored) gets placed by a program or system process, the extra data overflows. It causes some of
that data to leak out into other buffers, which can corrupt or overwrite whatever data they were
holding.

In a buffer-overflow attack, the extra data sometimes holds specific instructions for actions
intended by a hacker or malicious user; for example, the data could trigger a response that damages

1
8
files, changes data or unveils private information. Attacker would use a buffer-overflow exploit to
take advantage of a program that is waiting on a user’s input. There are two types of buffer
overflows: stack based and heap-based. Heap-based, which are difficult to execute and the least
common of the two, attack an application by flooding the memory space reserved for a program.
Stack-based buffer overflows, which are more common among attackers, exploit applications and
programs by using what is known as a stack: memory space used to store user input. d. Logic
Bomb

A logic bomb is a piece of code inserted into an operating system or software application that
implements a malicious function after a certain amount of time, or specific conditions are met. For
example, a programmer may hide a piece of code that starts deleting files, should they ever be
terminated from the company. Logic bombs are often used with viruses, worms, and trojan horses
to time them to do maximum damage before being noticed.

System Threats

System threats refers to misuse of system services and network connections to put user in trouble.
System threats can be used to launch program threats on a complete network called as program
attack. System threats creates such an environment that operating system resources/ user files are
misused. Following is the list of some well-known system threats.

a. Worms

A worm is a malicious, self-replicating program that can spread throughout a network without
human assistance. Worms cause damage similar to viruses, exploiting holes in security software
and potentially stealing sensitive information, corrupting files and installing a back door for remote
access to the system, among other issues. Worms often utilize large amounts of memory and
bandwidth, so affected servers, networks and individual systems are often overloaded and stop
responding. But worms are not viruses. Viruses need a host computer or operating system. The
worm program operates alone. The worm is often transmitted via file-sharing networks,
information-transport features, email attachments or by clicking links to malicious websites. Once
downloaded, the worm takes advantage of a weakness in its target system or tricks a user into
executing it. Some worms have a phishing component that entices users to run the malicious code.
b. Viruses

A computer virus, much like a flu virus, is designed to spread from host to host and has the
ability to replicate itself. Similarly, in the same way that flu viruses cannot reproduce without a
host cell, computer viruses cannot reproduce and spread without programming such as a file or
document.
In more technical terms, a computer virus is a type of malicious code or program written to alter
the way a computer operates and is designed to spread from one computer to another. A virus
operates by inserting or attaching itself to a legitimate program or document that supports macros
in order to execute its code. In the process, a virus has the potential to cause unexpected or
damaging effects, such as harming the system software by corrupting or destroying data.

1
8
Once a virus has successfully attached to a program, file, or document, the virus will lie dormant
until circumstances cause the computer or device to execute its code. In order for a virus to infect
your computer, you have to run the infected program, which in turn causes the virus code to be
executed.
This means that a virus can remain dormant on your computer, without showing major signs or
symptoms. However, once the virus infects your computer, the virus can infect other computers
on the same network. Stealing passwords or data, logging keystrokes, corrupting files, spamming
your email contacts, and even taking over your machine are just some of the devastating and
irritating things a virus can do.
Different types of viruses are:

1. Boot sector virus

This type of virus can take control when you start — or boot — your computer. One way it can
spread is by plugging an infected USB drive into your computer.

2. Web scripting virus

This type of virus exploits the code of web browsers and web pages. If you access such a web page,
the virus can infect your computer.

3. Browser hijacker
This type of virus “hijacks” certain web browser functions, and you may be automatically directed
to an unintended website.
4. Resident virus
This is a general term for any virus that inserts itself in a computer system’s memory. A resident
virus can execute anytime when an operating system loads.

5. Direct action virus

This type of virus comes into action when you execute a file containing a virus. Otherwise, it
remains dormant.

6. Polymorphic virus
A polymorphic virus changes its code each time an infected file is executed. It does this to evade
antivirus programs.

7. File infector virus

This common virus inserts malicious code into executable files — files used to perform certain
functions or operations on a system.

8. Multipartite virus
This kind of virus infects and spreads in multiple ways. It can infect both program files and system
sectors.

1
8
9. Macro virus
Macro viruses are written in the same macro language used for software applications. Such viruses
spread when you open an infected document, often through email attachments.

A computer virus attack can produce a variety of symptoms. Here are some of them:

• Frequent pop-up windows. Pop-ups might encourage you to visit unusual sites. Or they
might prod you to download antivirus or other software programs.
• Changes to your homepage. Your usual homepage may change to another website, for
instance. Plus, you may be unable to reset it.
• Mass emails being sent from your email account. A criminal may take control of your
account or send emails in your name from another infected computer.
• Frequent crashes. A virus can inflict major damage on your hard drive. This may cause
your device to freeze or crash. It may also prevent your device from coming back on.
• Unusually slow computer performance. A sudden change of processing speed could
signal that your computer has a virus.
• Unknown programs that start up when you turn on your computer. You may become
aware of the unfamiliar program when you start your computer. Or you might notice it by
checking your computer’s list of active applications.
• Unusual activities like password changes. This could prevent you from logging into your
computer.
How to protect against computer viruses?

• Use a trusted antivirus product.

• Avoid clicking on any pop-up advertisements.
• Always scan your email attachments before opening them.
• Always scan the files that you download using file sharing programs.
• Update your operating system regularly.
• Increase your browser security settings.
• Don’t open messages from unknown senders.

e. Denial of Services

A denial-of-service (DoS) attack is a type of cyber attack in which a malicious actor aims to render
a computer or other device unavailable to its intended users by interrupting the device's normal
functioning. DoS attacks typically function by overwhelming or flooding a targeted machine with
requests until normal traffic is unable to be processed, resulting in denial-of-service to addition
users. A DoS attack is characterized by using a single computer to launch the attack.

A denial-of-service (DoS) attack occurs when legitimate users are unable to access information
systems, devices, or other network resources due to the actions of a malicious cyber threat actor.
Services affected may include email, websites, online accounts (e.g., banking), or other services
that rely on the affected computer or network. A denial-of-service condition is accomplished by
flooding the targeted host or network with traffic until the target cannot respond or simply crashes,

1
8
preventing access for legitimate users. DoS attacks can cost an organization both time and money
while their resources and services are inaccessible.

Unit-9
Distributed Operating System
Introduction
A distributed operating system is an operating system that runs on several machines whose purpose
is to provide a useful set of services, generally to make the collection of machines behave more
like a single machine. The distributed operating system plays the same role in making the collective
resources of the machines more usable that a typical single-machine operating system plays in
making that machine’s resources more usable. Usually, the machines controlled by a distributed
operating system are connected by a relatively high-quality network, such as a high-speed local
area network. Most commonly, the participating nodes of the system are in a relatively small
geographical areas, something between an office and a campus.
The Distributed Os involves a collection of autonomous computer systems, capable of
communicating and cooperating with each other through a LAN / WAN. A Distributed Os provides
a virtual machine abstraction to its users and wide sharing of resources like as computational
capacity, I/O and files etc. A distributed operating system (DOS), are systems which model where
distributed applications are running on multiple computers, linked by communications.

1
9
 Fig: Distributed system
Applications of Distributed Operating Systems:
• Telecommunication Networks
• Network Applications
• Real Time Process Control
• Parallel Computation

Advantages of Distributed System

1. Scalability:
As computing occurs on each node independently, it is simple and inexpensive to add more
nodes and functionality as required.
2. Reliability:
Most distributed systems are made from many nodes that work together which ultimately
make them fault tolerant. The system doesn’t experience any disruptions if a single
machine fails.
3. Performance:
These systems are regarded to be very efficient as the work load can be broken up and sent
to multiple machines, therefore reducing data processing.
4. Data sharing:
Nodes can easily share data with other nodes as they are connected with each other.
5. No domino effect in case of a node failure:
The failure of one node in a DOS does not have a domino effect and enables all other nodes
fail. Other nodes can still communicate with each other despite the failure.
6. Shareable:
Resources, for instance like printers, can be shared with multiple nodes rather than just
being constrained to just one node.

Disadvantages of Distributed Operating System

1. Scheduling:

1
9
 The system has to decide which jobs need to be executed, when they should be executed,
and where they should be executed. A scheduler will have limitations, this may lead to
under-utilised hardware and unpredictable runtimes.
2. Latency:
The more widely distributed a system is the more latency can be experienced with
communications. This therefore results in teams/developers to make tradeoffs between
availability, consistency and latency.
3. Observability:
It can be a real challenge to gather, process, present, and monitor hardware usage metrics
for large clusters.
4. Security:
It is difficult to place adequate security in DOS, as the nodes and the connections need to
be secured.
5. Data loss:
Some data/messages may be lost in the network while moving from one node to another.
6. Complicated database:
In comparison to a single user system, the database connected to a DOS is relatively
complicated and difficult to handle.
7. Overloading:
If multiple nodes in DOS send data all at once, then the system network may become
overloaded. 8. Expensive:
These systems are not readily available, as they are regarded to be very expensive.
9. Complex software:
Underlying software is highly complex and is not understood very well compared to other
systems.
Network Operating System

A network operating system (NOS) is a computer operating system (OS) that is designed primarily
to support workstations, personal computers and, in some instances, older terminals that are
connected on a local area network (LAN).
Network Operating System runs on a server and gives the server the capability to manage data,
users, groups, security, applications, and other networking functions. The basic 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.
Some examples of network operating systems include Microsoft Windows Server 2003, Microsoft
Windows Server 2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD. Advantages

1. Centralized servers are highly stable.

2. Security is server managed.
3. Upgradation of new technologies and hardware can be easily integrated into the system.
4. It is possible to remote access to servers from different locations and types of systems.
Disadvantages

1. High cost of buying and running a server.

1
9
 2. Dependency on a central location for most operations.
3. Regular maintenance and updates are required.

Difference between network operating system and distributed operating system

The main difference between these two operating systems is that in network operating system each
node or system can have its own operating system on the other hand in distribute operating each
node or system have same operating system which is opposite to the network operating system.

Network Operating System Distributed Operating System

1. Network Operating System’s main objective 1. Distributed Operating System’s main

is to provide the local services to remote objective is to manage the hardware
client. resources.

2. In Network Operating System, 2. In Distributed Operating System,

Communication takes place on the basis of Communication takes place on the basis of
files. messages and shared memory.

3. Distributed Operating System is less scalable

3. Network Operating System is more scalable than Network Operating System.
than Distributed Operating System.

4. In Network Operating System, fault 4. While in Distributed Operating System, fault

tolerance is less. tolerance is high.

5. Rate of autonomy in Network Operating 5. While The rate of autonomy in Distributed

System is high. Operating System is less.

6. Ease of implementation in Network 6. While in Distributed Operating System Ease

Operating System is also high. of implementation is less.

7. In Network Operating System, All nodes can 7. While in Distributed Operating System, All
have different operating system. nodes have same operating system.
Hardware and Software Concepts

All distributed systems consist of multiple CPUs. There are several different ways the hardware
can be arranged. The important thing related to hardware is that how they are interconnected and
how they communicate with each other. It is important to take a deep look at distributed system
hardware, in particular, how the machines are connected together and how they interact.
Many classification schemes for multiple CPU computer systems have been proposed over the
years, but none of them have really implemented. Still, the most commonly used taxonomy is
Flynn's (1972), but it was in basic stage. In this scheme, Flynn took only two things to consider

1
9
i.e. the number of instruction streams and the number of data streams.
1. Single Instruction, Single Data Stream (SISD)
A computer with a single instruction stream and a single data stream is called SISD. All traditional
uni-processor computers (i.e., those having only one CPU) fall under this category, from personal
computers to large mainframes. SISD flow concept is given in the figure below.

Fig :SISD Flow structure

2. Single Instruction, Multiple Data Stream (SIMD)
It uses an array of processors with only one instruction unit that fetches an instruction, and
multiple data units which work in parallel. These machines are used where there need to apply
the same instruction for multiple data example, adding up all the elements of 64 independent
vectors. Some supercomputers are SIMD. Figure below shows the SIMD flow structure.

Fig: SIMD Flow structure

3. Multiple Instructions, Single Data Stream (MISD)
This structure was worked when there are multiple different instructions to operate on the same
type of data. In general MISD architecture is not use more in practical.

1
9
 Fig: MISD Flow structure
4. Multiple Instruction, Multiple Data Stream (MISD)
The next category is MIMD, which has multiple instructions performances on multiple data
units. This means a group of independent computers; each has its own program counter,
program, and data. All distributed systems are MIMD, so this classification system is not more
useful for simple purposes.

Fig: MIMD Flow structure

Software Concept
Although the hardware is important, the software is even more important. The image that a
system presents to its users and how they think about the system is largely determined by the
operating system software, not the hardware.
There are basic two types of operating system namely tightly coupled operating system and
loosely couple operating system, for multiprocessor and multicomputer. Loosely coupled
software allows machines and users of a distributed system to be fundamentally independent
of one another. Consider a group of personal computers, each of which has its own CPU, its
own memory, its own hard disk, and its own operating system, but which share some resources,
such as laser printers and databases over a LAN. This system
1
9
is loosely coupled, since the individual machines are clearly distinguishable, each with its own
job to do. If the network should go down for some reason, the individual machines can still
continue to run to a considerable degree, although some functionality may be lost.
For tightly coupled system consider a multiprocessor dedicated to running a single chess
program in parallel. Each CPU is assigned a board to evaluate and it spends its time examining
that board and all the boards that can be generated from it. When the evaluation is finished, the
CPU reports back the results and is given a new board to work on.

Communication in Distributed Systems

1. Shared memory
Distributed shared memory (DSM) is a form of memory architecture where physically
separated memories can be addressed as one logically shared address space. Here, the term
"shared" does not mean that there is a single centralized memory, but that the address space is
"shared" (same physical address on two processors refers to the same location in memory). A
distributed-memory system, often called a multicomputer, consists of multiple independent
processing nodes with local memory modules which is connected by a general interconnection
network. Software DSM systems can be implemented in an operating system, or as a
programming library and can be thought of as extensions of the underlying virtual memory
architecture. When implemented in the operating system, such systems are transparent to the
developer; which means that the underlying distributed memory is completely hidden from the
users. In contrast, software DSM systems implemented at the library or language level are not
transparent and developers usually have to program them differently. However, these systems
offer a more portable approach to DSM system implementations. A distributed shared memory
system implements the shared-memory model on a physically distributed memory system.
The syntax used for DSM is the same as that of normal centralized memory multiprocessor
systems. read(shared_variable) write(data, shared_variable)
The read() primitive requires the name of the variable to be read as its argument and the write()
primitive requires the data and the name of the variable to which the data is to be written. The
operating system locates the variable through its virtual address and, if necessary, moves the
portion of memory containing the variable to the machine requiring it.

1
9
 Fig: Distributed shared memory

Advantages

• Scales well with a large number of nodes

• Message passing is hidden
• Can handle complex and large databases without replication or sending the data to
processes
• Generally cheaper than using a multiprocessor system
• Provides large virtual memory space
• Programs are more portable due to common programming interfaces
• Shield programmers from sending or receiving primitives

Disadvantages

• Generally slower to access than non-distributed shared memory

• Must provide additional protection against simultaneous accesses to shared data
• May incur a performance penalty
• Little programmer control over actual messages being generated
• Programmers need to understand consistency models, to write correct programs
• DSM implementations use asynchronous message-passing, and hence cannot be more
efficient than message-passing implementations

2. Message Passing

Message passing model allows multiple processes to read and write data to the message queue
without being connected to each other. Messages are stored on the queue until their recipient
retrieves them. Message queues are quite useful for interprocess communication and are used by
most operating systems.
1
9
Message passing is the basis of most interprocess communication in distributed systems. It is at
the lowest level of abstraction and requires the application programmer to be able to identify the
destination process, the message, the source process and the data types expected from these
processes.

Communication in the message passing paradigm, in its simplest form, is performed using the
send() and receive() primitives. The syntax is generally of the form:

send(receiver, message)

receive(sender, message)

The send() primitive requires the name of the destination process and the message data as
parameters. The addition of the name of the sender as a parameter for the send() primitive would
enable the receiver to acknowledge the message. The receive() primitive requires the name of the
anticipated sender and should provide a storage buffer for the message.
Machine A Machine B

Task 0 Task 1

Data Data

send () recv()

Task 2 Task 3

Data Data

recv() send ()

Fig: Message Passing

3. Remote Procedure Call

Message passing leaves the programmer with the burden of the explicit control of the movement
of data. Remote procedure calls (RPC) relieve this burden by increasing the level of abstraction
and providing semantics similar to a local procedure call.

Remote Procedure Call (RPC) is a powerful technique for constructing distributed,

clientserver-based applications. It is based on extending the conventional local procedure calling
so that the called procedure need not exist in the same address space as the calling procedure.
The two processes may be on the same system, or they may be on different systems with a network
connecting them.

1
9
The syntax of a remote procedure call is generally of the form: call

procedure_name(value_arguments; result_arguments)

The client process blocks at the call() until the reply is received. The remote procedure is the server
processes which has already begun executing on a remote machine. It blocks at the receive() until
it receives a message and parameters from the sender. The server then sends a reply() when it has
finished its task. The syntax is as follows:

receive procedure_name(in value_parameters; out result_parameters)

reply(caller, result_parameters)

Clock Synchronization

Distributed System is a collection of computers connected via the high speed communication
network. In the distributed system, the hardware and software components communicate and
coordinate their actions by message passing. Each node in distributed systems can share their
resources with other nodes. So, there is need of proper allocation of resources to preserve the state
of resources and help coordinate between the several processes. To resolve such conflicts,
synchronization is used. Synchronization in distributed systems is achieved via clocks.

The clock synchronization can be achieved by 2 ways:

1
9
External and Internal Clock Synchronization.
1. External clock synchronization is the one in which an external reference clock is
present. It is used as a reference and the nodes in the system can set and adjust their
time accordingly.
2. Internal clock synchronization is the one in which each node shares its time with
other nodes and all the nodes set and adjust their times accordingly.

There are 2 types of clock synchronization algorithms: Centralized and Distributed.

1. Centralized is the one in which a time server is used as a reference. The single time
server propagates its time to the nodes and all the nodes adjust the time accordingly. It
is dependent on single time server so if that node fails, the whole system will lose
synchronization. Examples of centralized are- Berkeley Algorithm, Passive Time
Server, Active Time Server etc.
2. Distributed is the one in which there is no centralized time server present. Instead, the
nodes adjust their time by using their local time and then, taking the average of the
differences of time with other nodes. Distributed algorithms overcome the issue of
centralized algorithms like the scalability and single point failure. Examples of
Distributed algorithms are – Global Averaging Algorithm, Localized Averaging
Algorithm, NTP (Network time protocol) etc.

Physical clock synchronization

In distributed systems, this is not the case. Unfortunately, each system has its own timer that drives
its clock. These timers are based either on the oscillation of a quartz crytal, or equivalent IC.
Although they are reasonably precise, stable, and accurate, they are not perfect. This means that
the clocks will drift away from the true time. Each timer has different characteristics --
characteristics that might change with time, temperature, &c. This implies that each systems time
will drift away from the true time at a different rate -- and perhaps in a different direction (slow or
fast).

Berkeley algorithm

• The server polls each machine periodically, asking it for the time.
• Based on the answer it computes for the average time and tells all the other machine to
advance their clocks to the new time or slow their clocks down until some specific
reduction has been achieved.
• The time daemon’s time must be set manually by operator periodically.

2
0
Logical Clock

Logical Clocks refer to implementing a protocol on all machines within your distributed
system, so that the machines are able to maintain consistent ordering of events within some
virtual timespan. A logical clock is a mechanism for capturing chronological and causal
relationships in a distributed system. Distributed systems may have no physically synchronous
global clock, so a logical clock allows global ordering on events from different processes in
such systems.

Lamport’s algorithm

• Each message carries a timestamp of the sender’s clock When a message

arrives :
- If the receiver’s clock < message timestamp
set system clock to (message timestamp + 1)
else do nothing
• Clock must be advanced between any two events in the same process.

The algorithm for sending is:

# event is known
time = time + 1; #
event happens
send(message, time);

The algorithm for receiving a message is:

(message, time_stamp) = receive();

time = max(time_stamp, time) + 1;

2
0
Correcting the clock

2
0
2
0
 Tribhuvan University
Faculty of Humanities and Social Sciences
OFFICE OF THE DEAN
2019

Bachelor in Computer Applications Full marks: 60

Course Title: Operating System Pass Marks: 24
Code No: CACS 251 Time: 3 hours
Semester: IV

Centre: Symbol No:

Candidates are required to answer the questions in their own words as far as possible.

Group A
Attempt all the questions.
[10×1=10]

1. Circle ( ) the correct answer in the following questions.

i. In UNIX, which system call creates the new process?

a) fork b) create c) new d) None of the
mentioned ii.
Which of the following does not contain process control block (PCB)?
a) Code b) Bootstrap program c) Stack d) Data iii. The Test and Set
instruction is executed:
a) after a particular process b) automatically
c) periodically d) None of these iv. How circular wait condition can be
prevented?
a) By defining linear ordering of resource type
b) By resource grant on all or none basis
c) By using pipes
d) By using threads
v. Which process can be affected by other processing executing in the system?
a) Cooperation process b) Init c) Parent process d) Child process
process
2
0
vi. External fragmentation will not occur when?
a) First fit is used
b) Worst fit is used
c) Best fit is used
d) No matter which algorithm is used, it will always occur
vii. What is compaction?
a) A technique for overcoming internal fragmentation
b) A technique for overcoming external fragmentation
c) A paging technique
d) A technique for overcoming fatal error
viii. Why is one-time password safe?
a) It is easy to generated b) It is different for every access
c) It cannot be shared d) It is complex encrypted password ix. In distributed system, each
processor has its own:
a) Local memory c) Both local memory and clock
b) Clock d) None of these
x. How process on the remote system are identified:
a) Host ID b) Host name and identifier
c) Identifier d) Process ID

2
0
 Tribhuvan University
Faculty of Humanities and Social Sciences
OFFICE OF THE DEAN
2019

Bachelor in Computer Applications Full Marks: 60

Course Title: Operating System Pass Marks: 24
Code No: CACS 251 Time : 3 hours
Semester: IV
Candidates are required to answer the questions in their own words as far as possible.
Group B
Attempt any SIX questions. [6×5=30]
2. What is an Operating System? Explain the function of operating system. [1+4]
3. Define the term semaphore. How does semaphore help in dining philosopher [1+4] problem.
4. A system has two process and three resources. Each process needs a maximum [5] of two
resources is deadlock possible? Explain with answer.
5. Suppose a new process in a system arrives at an average of six process per minute [5] and each
such process requires an average of 8 seconds of service time. Estimate the fraction of time the
CPU is busy in a system with a single processor.
6. Given references to the following pages by a program: [2.5+2.5]
0, 9, 0, 18, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3
How many page faults will occur if the program has three page frames for each of
the following algorithms?
a) FIFO
b) LRU
7. What is file? Explain how access control matrix provides resource protection that [1+4] may
access process.
8. What do you mean by one-time password in authentication? How worms are [2+3] differing from
virus.

Group C
Attempt any TWO questions. [2×10= 20]

9. What is CPU scheduling criterias? For the process listed in following table, draw [1+9] Gantt
chart illustrating their execution and calculate average waiting time and turnaround time using:
a) First Come First Serve
b) Shortest Remaining Time Next
c) Priority
d) Round Robin (quantum = 1)
2
0
 Process Arrival Time Burst Time (Sec) Priority
P0 0.00 7 3
P1 2.01 7 1
P2 3.01 2 4
P3 3.02 2 2

10. Define the term seek time and rotational delay in disk scheduling. Suppose that a [2+8] disk has
100 cylinders, numbered 0 to 99. The drive is currently serving a request at cylinder 43 and
previous request was at cylinder 25. The queue of pending request, in FIFO order is: 86, 70, 13,
74, 48, 9, 22, 50, 30
Starting from the current head position, what is total distance (in cylinders) that
the disk arm moves at satisfy all pending request for each of following disk
scheduling algorithms?
a) FCFS b) SSTF c) SCAN d) LOOK

11. What is clock synchronization? Explain how physical clock synchronize by [1+9] Berkeley
algorithm and logical clock synchronize by Lamport’s algorithm with suitable example.

2
0
208