OPERATING SYSTEMS

(15CS64)

Notes

Prepared By
Athmaranjan K
Associate Professor
Dept. of Information Science & Eng

Srinivas Institute of Technology

Mangaluru
 MODULE 1

Introduction to operating systems, System structures: What operating systems do; Computer System
organization; Computer System architecture; Operating System structure; Operating System operations;
Process management; Memory management; Storage management; Protection and Security; Distributed
system; Special-purpose systems; Computing environments. Operating System Services; User -
Operating System interface; System calls; Types of system calls; System programs; Operating system
design and implementation; Operating System structure; Virtual machines; Operating System generation;
System boot. Process Management: Process concept; Process scheduling; Operations on processes;
Inter process communication.

Text Book:
1. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating System Principles 7th edition, Wiley-
India, 2006.
OPERATING SYSTEMS MODULE 1

INTRODUCTION TO OPERATING SYSTEMS

What is an Operating System?
An operating system is a program that manages the computer hardware, and acts as an
intermediary between the computer user and the computer hardware. It also provides a basis for
application programs.
WHAT OPERATING SYSTEMS DO
The operating system's role in the overall computer system is studied, by considering a computer
system which can be divided roughly into four components: the hardware, the operating system,
the application programs, and the users.

 Hardware provides basic computing resources such as CPU, memory, I/O devices
 System & Application programs define the ways in which the system resources are used
to solve the computing problems of the users / systems. Word processors, compilers, web
browsers, database systems, video games.
 Operating system controls and coordinates use of hardware among various applications
and users
 Users: People, machines, other computers.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 1

OPERATING SYSTEMS MODULE 1

VIEWS OF OPERATING SYSTEMS

********Explain different views of operating systems.
There are two viewpoints of Operating system
1. User view
2. System View
User View of computer system varies according to the interface being used.
 PC: In this system the operating system is designed mostly for ease of use.
 Mainframe or Minicomputer: Operating system is designed to maximize resource
utilization.
 Workstation: Operating system is designed to compromise between individual usability and
resource utilization.
 Handheld devices: Their operating systems are designed mostly for individual usability, but
performance per amount of battery life is important as well.
 Embedded computers in home devices and automobiles: their operating systems are
designed primarily to run without user intervention.
System View: From the computer's point of view, the operating system is the program most intimately
involved with the hardware. In this context, we can view an operating system as a
i. Resource allocator:
a) Manages all resources
b) Decides between conflicting requests for efficient and fair resource use
ii. Control program:
a) Control the various I/O devices and user programs.
b) Controls execution of programs to prevent errors and improper use of the computer
DEFINING OPERATING SYSTEMS
• The common functions of controlling and allocating resources are brought together in one
piece of software called Operating System
• ―The one program running at all times on the computer‖ is the kernel. Everything else is
either a system program (ships with the operating system) or an application program.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 2

OPERATING SYSTEMS MODULE 1

COMPUTER-SYSTEM ORGANIZATION
1. Computer-system operation
a. One or more CPUs, device controllers connect through common bus providing
access to shared memory.
b. Concurrent execution of CPUs and devices competing for memory cycles.

Bootstrap program: For a computer to start running—for instance, when it is powered up or

rebooted—it needs to have an initial program to run. This initial program, or bootstrap
program, tends to be simple.
 Typically, it is stored in read-only memory (ROM) or electrically erasable programmable
read-only memory (EEPROM), known by the general term firmware, within the
computer hardware.
 It initializes all aspects of the system (CPU registers, Device Controllers, memory
contents)
 Loads operating system kernel and starts execution.
 The operating system then starts executing the first process, such as "init," and waits for
some event to occur.
 The occurrence of an event is usually signaled by an interrupt from either the hardware
or the software.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 3

OPERATING SYSTEMS MODULE 1

Interrupt
 The occurrence of event is signaled by interrupt from either hardware(signal to CPU) or
software (system call)
 Interrupt transfers control to the interrupt service routine generally, through the interrupt
vector, which contains the addresses of all the service routines.
 Interrupt architecture must save the address of the interrupted instruction.
 Incoming interrupts are disabled while another interrupt is being processed to prevent a
lost interrupt.
 A trap is a software-generated interrupt caused either by an error or a user request.
 An operating system is interrupt driven.
 After the interrupt is serviced, the saved return address is loaded into the program
counter, and the interrupted computation resumes as though the interrupt is not occurred.

2. Storage Structure:
 Main Memory:
Computer programs must be in main memory (also called random-access memory or
RAM) to be executed. Main memory is the only large storage area (millions to billions of
bytes) that the processor can access directly. It commonly is implemented in a semiconductor
technology called Dynamic Random Access Memory (DRAM). Other memory devices are
ROM, EEPROM etc. Load and store instructions are used to read and write data/instructions
between memory & processor.
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 4
OPERATING SYSTEMS MODULE 1

Secondary storage
 Extension of main memory that provides large nonvolatile storage capacity.
• Magnetic disks
 Rigid metal or glass platters covered with magnetic recording material
 Disk surface is logically divided into tracks, which are subdivided into sectors.
 The disk controller determines the logical interaction between the device and the
computer.
Other storages include cache, CD-ROM, magnetic tapes and so on. The main differences among
the storage systems lie in speed, cost, size and volatility. The storage system can be organized in
a hierarchy according to speed and cost. Higher levels are expensive but they are fast. Down in
the hierarchy cost decreases and the access time increases.
Explain storage device hierarchy, with neat diagram.

The wide variety of storage systems in a computer system can be organized in a hierarchy as
shown above, is according to speed and cost. The higher levels are expensive, but they are fast.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 5

OPERATING SYSTEMS MODULE 1

As we move down the hierarchy, the cost per bit generally decreases, whereas the access time
generally increases.
CACHING
• Information in use copied from slower to faster storage device temporarily
• Faster storage (cache) checked first to determine if information is there in main memory
– If it is, information used directly from the cache (fast)
– If not, data copied to cache and used there.
I/O STRUCTURE

Storage is only one of many types of I/O devices within a computer. A large portion of operating
system code is dedicated to managing I/O, both because of its importance to the reliability and
performance of a system and because of the varying nature of the devices. A general-purpose
computer system consists of CPUs and multiple device controllers that are connected through a
common bus. Each device controller is in charge of a specific type of device. Depending on the
controller, there may be more than one attached device. The device controller is responsible for
moving the data between the peripheral devices that it controls and its local buffer storage.
Typically, operating systems have a device driver for each device controller. This device driver
understands the device controller and presents a uniform interface to the device to the rest of the
operating system.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 6

OPERATING SYSTEMS MODULE 1

COMPUTER-SYSTEM ARCHITECTURE
A computer system may be organized in a number of different ways, which we can categorize
roughly according to the number of general-purpose processors used.
 Single processor systems
 Multiprocessor system
 Clustered system
SINGLE-PROCESSOR SYSTEM
 One main CPU capable of executing a general-purpose instruction set, including
instructions from user processes.
 All systems have special purpose processors. i.e device specific processors such as disk,
keyboard, and graphics controller
 Mainframes- general purpose processors such as I/O processors
 Run limited set of instruction does not run user processes.
 Use of special purpose processor does not turn a single processor system into
multiprocessor system
MULTI-PROCESSOR SYSTEMS
 Also known as parallel systems or tightly coupled systems
 Two or more processors in close communication sharing the computer bus and
sometimes the clock, memory and peripheral devices
***List the three main advantages of multi-processor systems
Advantages
1. Increased throughput: By increasing the number of processors, we expect to get more work
done in less time
2. Economy of scale: Multiprocessor systems can cost less than equivalent multiple single-
processor systems.
3. Increased reliability: If functions can be distributed properly among several processors, then
the failure of one processor will not halt the system, only slow it down.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 7

OPERATING SYSTEMS MODULE 1

Define the following terms

i. Graceful degradation
ii. Fault tolerant systems
Graceful degradation:
The ability of computer system to continue providing service proportional to the level of
surviving hardware is called graceful degradation.
It is the ability of a computer, to maintain limited functionality even when a large portion of its
component has been destroyed or rendered inoperative.
Fault tolerance in computer system:
Fault tolerance is the way in which an operating system (OS) responds to a hardware or
software failure. The term essentially refers to a system's ability to allow for failures or
malfunctions, and this ability may be provided by software, hardware or a combination of both.
Explain the types of multiprocessor system
Two types of Multi-processor systems
i. Asymmetric multi-processing system
ii. Symmetric multi-processing system
Asymmetric multi-processing system:
 In this system each processor is assigned a specific task.
 A master processor controls the system; and other processors either look to the master for
instruction or have predefined tasks
 It defines master-slave relationship
Symmetric multi-processing system:
 In this system each processor performs all tasks within the operating system.
 No master-slave relationship exists between processors.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 8

OPERATING SYSTEMS MODULE 1

CLUSTERED SYSTEMS
****Explain the types of clustered system
 Clustered system gather together multiple CPUs to accomplish computational work
 Clustered systems are composed of two or more individual systems or nodes joined
together.
 Clustered system share storage and are closely linked via local area network.
 Clustering provide high availability.
Types of clustering systems
i. Asymmetric clustering
ii. Symmetric clustering
iii. Parallel clustering
iv. Clustering over wide area network
Asymmetric clustering
 One machine is in hot-standby mode while other is running the applications.
 The hot standby host machine does nothing but monitor the active server.
 If server fails, the hot standby host machine becomes the active server.
Symmetric clustering
 Two or more hosts are running applications and are monitoring each other.
 This mode of system is more efficient, as it uses all of the available hardware.
Parallel clustering
 Parallel clusters allow multiple hosts to access the shared data.
Clustering over wide area network
 It is a collection of physically separate computer systems that are networked (WAN) to
provide the users with access to the various resources that the system maintains.

 Access to shared resource increases computation speed, functionality, data availability

and reliability.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 9

OPERATING SYSTEMS MODULE 1

OPERATING-SYSTEM STRUCTURE
The various types of general purpose OS is
1. Batch Systems
1. Multiprogramming
2. Time sharing or Multitasking
Define the essential features of Batch operating system (Batch file system)
BATCH SYSTEM
 The user of batch OS do not interact with the computer directly.
 Each user prepares his job on an off-line device like punch cards and submits it to the
computer operator
 At some later time (after minutes, hours or days) the output is generated.
 To speed up processing, jobs with similar needs are batched together and run as a group
 As several jobs are given to computer system and unless it completes the first job it is not
possible to process the next job. Therefore it is an in-efficient OS. Also the CPU is often
idle because the speed of the mechanical I/O devices.
Define the essential features of Multiprogramming operating system
MULTIPROGRAMMING
 Multiprogramming increases CPU utilization by organizing jobs (code and data) so that the
CPU always has one to execute.
 OS keeps several jobs in memory simultaneously.
 One job selected and run via job scheduling
 In a multi-programmed system, the operating system simply switches to, and executes,
another job. When that job needs to wait, the CPU is switched to another job, and so on.
 As long as at least one job needs to execute, the CPU is never idle.
 Multiprogramming provides an environment in which various system resources are
utilized effectively but they do not provide user interaction with the computer system.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 10

OPERATING SYSTEMS MODULE 1

TIME SHARING OR MULTITASKING

Define the essential features of Time sharing operating system
 In time-sharing systems, the CPU executes multiple jobs by switching among them, but
the switches occur so frequently that the users can interact with each program while it is
running.
 The user gives instructions to the operating system or to a program directly, using a input
device such as a keyboard or a mouse, and waits for immediate results on an output
device. Accordingly, the response time should be short—typically less than one second.
 A time-shared operating system allows many users to share the computer simultaneously.
 A time-shared operating system uses CPU scheduling.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 11

OPERATING SYSTEMS MODULE 1

****Differentiate between Multi-programming, Multi-tasking (Time sharing) and Multi-

processing system
S. No Multiprogramming Multitasking Multiprocessing
1 Multiprogramming is Multitasking is the ability of Multiprocessing is the ability
the ability of an an operating system to of an operating system to
operating system to execute more than one task execute more than one
execute more than one simultaneously on a single process simultaneously on a
program on a single processor machine based on multi processor machine by
processor machine time sharing. having more than one
based on context physical processor.
switching.
2 Multiple programs It enables execution of It utilizes multiple CPUs for
reside in the main multiple tasks and processes process allocation
memory simultaneously at the same time to increase
to improve CPU CPU performance.
utilization so that CPU
does not sit idle for a
long time.
3 The main idea is to keep The idea is to allow multiple The idea is to allow multiple
the CPU busy as long as processes to run processes to run
there are processes simultaneously via time simultaneously via multiple
ready to execute. sharing processors.
4 They do not provide It allows many users to share It provides user interaction
user interaction with the the computer simultaneously with the system
computer system

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 12

OPERATING SYSTEMS MODULE 1

OPERATING SYSTEM OPERATIONS

Modern Operating system is interrupt driven. Events are always signaled by the occurrence of an
interrupt or trap. A trap is a software generated interrupt caused either by error (Division by zero,
invalid memory access) or request from a user program that an OS service be performed. For
each type of interrupt, separate segments of code in the OS determine what action should be
taken. The Interrupt Service Routine (ISR) is provided that is responsible for dealing with
interrupt.
DUAL MODE OPERATION OF OPERATING SYSTEM
*****Explain the operation of operating system
*****With neat diagram explain the Dual mode operation of operating system
In order to differentiate between the execution of OS code and user defined code, most of the
computers provide hardware support by executing these codes in two separate modes
1. User Mode
2. Kernel or Supervisor or Privileged or System mode

A mode bit is added to the computer hardware to indicate the current mode; ie: mode bit = 0 for
kernel mode and 1 for user mode.
Working Principle:
 At system Boot time, the hardware starts in kernel mode
 The OS is then loaded and starts user application in user mode
 Whenever a trap or interrupt occurs, the hardware switches from user mode to kernel
mode

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 13

OPERATING SYSTEMS MODULE 1

 The system always switches to user mode (setting mode bit = 1), before passing control
to user program
 Dual mode operation protects OS from errant users and errant user from one another
 Privileged instruction is executed only in kernel mode
 If an attempt is made to execute privileged instruction in user mode, the hardware treats it
as illegal and traps it to the OS
 A system calls are called by user program to ask the OS to perform the tasks on behalf of
the user program.
TIMER

PROCESS MANAGEMENT
A process is a program in execution. It is a unit of work within the system. Program is a passive
entity, process is an active entity. Process needs resources to accomplish its task like CPU,
memory, I/O, files. Process termination requires reclaim of any reusable resources. Single-
threaded process has one program counter specifying location of next instruction to execute.
Process executes instructions sequentially, one at a time, until completion. Multi-threaded
process has one program counter per thread. Typically system has many processes, some user,
some operating system running concurrently on one or more CPUs. All processes can execute
concurrently by multiplexing the single CPUs.
*****What are the operating System activities connected with Process management
1. Creating and deleting both user and system processes
2. Suspending and resuming processes
3. Providing mechanisms for process synchronization
4. Providing mechanisms for process communication
5. Providing mechanisms for deadlock handling
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 14
OPERATING SYSTEMS MODULE 1

MEMORY MANAGEMENT

*****What are the operating System activities connected with Memory management
Memory management activities
1. Keeping track of which parts of memory are currently being used and by whom
2. Deciding which processes (or parts thereof) and data to move into and out of memory
3. Allocating and de-allocating memory space as needed
STORAGE MANAGEMENT
1. Storage management
2. Mass-Storage management
3. Caching
FILE MANAGEMENT

*****What are the operating System activities connected with File management
OS activities include
1. Creating and deleting files and directories
2. Supporting Primitives to manipulate files and directories

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 15

OPERATING SYSTEMS MODULE 1

3. Mapping files onto secondary storage

4. Backup files onto stable (non-volatile) storage media
MASS-STORAGE MANAGEMENT

*****What are the operating System activities connected with Mass storage management
OS activities
1. Free-space management
2. Storage allocation
3. Disk scheduling
CACHING

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 16

OPERATING SYSTEMS MODULE 1

DISTRIBUTED SYSTEM
**List the essential properties of Distributed OS

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 17

OPERATING SYSTEMS MODULE 1

SPECIAL PURPOSE OPERATING SYSTEMS

These are the systems whose functions are limited and whose objective is to deal with limited
computation.
1. Real-time Embedded System
2. Multimedia systems
3. Handheld systems
REAL-TIME EMBEDDED SYSTEM (Real Time OS)
***List the essential features of Real time OS
 RTOS tend to have specific task(monitoring and managing other devices)
 RTOS provide little or no user interface
 Real time OS has well-defined fixed time constraints. Processing must be done within the
defined constraints, or the system will fail.
 It is often used as control device in dedicated application.
Embedded systems are most prevalent form of computers
Embedded system varies as
 General purpose system running standard OS
 Hardware devices with special purpose OS
The use of embedded devices continues to expand. Embedded system always run on real-time
operating systems.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 18

OPERATING SYSTEMS MODULE 1

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 19

OPERATING SYSTEMS MODULE 1

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 20

OPERATING SYSTEMS MODULE 1

OPERATING-SYSTEM SERVICES
An operating system provides an environment for the execution of programs. It provides certain
services to programs and to the users of those programs.
*********List and explain the services provided by OS for the user and efficient operation
of system.
Services provided by the OS that are helpful to the user:
1. User Interface: Almost all operating systems have a user interface (UI), such as
Command-Line (CLI) uses text commands, Graphics User Interface (GUI) is window
system, Batch Interface uses commands and directives.
2. Program execution: The system must be able to load a program into memory and to run
that program, end execution, either normally or abnormally (indicating error)
3. I/O operations: A running program may require I/O, which may involve a file or an I/O
device.
4. File-system manipulation: The file system is of particular interest. Obviously, programs
need to read and write files and directories, create and delete them, search them, list file
Information, permission management.
5. Communications: Processes may exchange information, on the same computer or
between computers over a network. Communications may be via shared memory or
through message passing (packets moved by the OS)
6. Error detection – OS needs to be constantly aware of possible errors. Errors may occur
in CPU and memory, in I/O devices and in user program.
Services provided by the OS that are helpful to the efficient operation of system.
1. Resource allocation - When multiple users or multiple jobs running concurrently,
resources must be allocated to each of them
2. Accounting - To keep track of which users use how much and what kinds of computer
resources
3. Protection and security – When several separate processes execute concurrently, it
should not be possible for one process to interfere with the others or with the OS itself.
Protection involves ensuring that all access to system resources is controlled. Security

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 21

OPERATING SYSTEMS MODULE 1

of the system from outsiders requires user authentication, extends to defending external
I/O devices from invalid access attempts
COMMAND-LINE INTERFACE OR COMMAND INTERPRETER
CLI allows direct command entry
 Sometimes implemented in kernel, sometimes by systems program
 Sometimes multiple flavors implemented – shells
 Primarily fetches a command from user and executes it
 Sometimes commands built-in, sometimes just names of programs
GRAPHICAL USER INTERFACE
• User-friendly desktop metaphor interface
– Usually mouse, keyboard, and monitor
– Icons represent files, programs, actions, etc
– Various mouse buttons over objects in the interface cause various actions (provide
information, options, execute function, open directory (known as a folder)
• Many systems now include both CLI and GUI interfaces
– Microsoft Windows is GUI with CLI ―command‖ shell
– Solaris is CLI with optional GUI interfaces (Java Desktop, KDE)
SYSTEM CALLS

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 22

OPERATING SYSTEMS MODULE 1

*****What are System calls? Explain the types of system call.

System calls provides an interface between a process and operating system to allow user-level
processes to request services of the operating system.
There are 5 different types of system calls:
1. Process control System call
2. File management
3. Device management
4. Information maintenance
5. Communication.
Process control System calls are used:
 End , abort
 Load, Execute
 Create process, terminate process
 get process attributes, set process attributes
 Wait for time
 Wait event, signal event
 Acquire lock and release lock
Common system calls dealing with file management are
 Create file, delete file
 Open, close
 Read, write, reposition
 get file attributes(file name, file type, protection codes, accounting information), set file
attributes
 Move and copy(API, system programs)
Common system calls dealing with Device management are
 Request device, release device
 Read, write, reposition
 Get device attributes, set device attributes
 Logically attach or detach devices
Common system calls dealing with Information maintenance are
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 23
OPERATING SYSTEMS MODULE 1

 get time or date, set time or date

 get system data ,set system data
 get process, file and device attributes
 set process, file and device attributes
Common system calls dealing with Communication are
 Create, delete communication connection
 Send, receive messages
 Transfer status information
 Attach or detach remote devices
Two modes of communication: 1. Message passing model 2. Shared memory model

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 24

OPERATING SYSTEMS MODULE 1

Write the system call sequence to copy a file from source to destination

With example explain how system call handles user applications

Let us consider an example, a C program invokes the printf () statement. The C library intercepts
this call and invokes the necessary system call in the operating system, in this instance, the write
() system call. The C library takes the value returned by write () and passes it back to the user
program. This is shown in below figure.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 25

OPERATING SYSTEMS MODULE 1

SYSTEM PROGRAM
***What are the different categories of system program
Six categories of system program are:
1. File management: These programs manipulate files. Create, delete, copy, rename, print,
dump, list etc
2. Status information: Some programs ask the system for Date(time), amount of memory,
number of users etc.
3. File modification: text editors can be used to create and modify the content of files stored
on the disk.
4. Programming Language support: Compilers, assemblers and interpreters for common
programming languages are provided to the user
5. Program loading and Execution: the system may provide absolute loader, re-locatable
loaders, linkage editors, overlay loaders, Debugger etc.
6. Communications: These programs are used for creating virtual connections between
processes, users and computer systems. They allow user to browse web pages, send email
or log-in remotely
OPERATING SYSTEM DESIGN AND IMPLEMENTATION
Affected by choice of hardware, type of system-batch system, time shared system
User goals and System goals
User goals – operating system should be convenient to use, easy to learn, reliable, safe, and fast
System goals – operating system should be easy to design, implement, and maintain, as well as
flexible, reliable, error-free, and efficient. The wide variety of systems in existence shows
different requirements can result in variety of solutions for different environments.
 Specifying and designing an OS is a highly creative task.
 Software engineering provide general principles.
MECHANISM AND POILCIES
One important principle is the separation of policy and mechanism.
 Policy: What will be done?
 Mechanism: How to do it?

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 26

OPERATING SYSTEMS MODULE 1

Is separation of mechanism and policy desirable while designing an operating system?

Discuss with an example.
The separation of mechanism and policy is important for flexibility. Policies are likely to change
across places or time. A general mechanism insensitive to changes in policy would be more
desirable. A change in policy would then require redefinition of only certain parameters of the
system. Thus mechanisms determine how to do something and policies decide what will be
done.
Example: Timer construct.
Mechanism: CPU protection
Policy: How long the timer is to be set for particular user.
 Timer to prevent infinite loop / process hogging resources
 Before turning over control to the user, the operating system ensures that the timer
is set to interrupt.
 Set interrupt after specific period
 Operating system decrements counter
 When counter zero generate an interrupt
 Set up before scheduling process to regain control or terminate program
that exceeds allotted time.

IMPLEMENTATION
Once an OS is designed it must be implemented. Traditionally OS is implemented in assembly
language and now it is written in c or c++ .
Example: MS-DOS written in intel 8088 assembly language. Linux OS written in C is available
to number of CPUs

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 27

OPERATING SYSTEMS MODULE 1

OPERATING SYSTEM STRUCTURE

Modern operating system is designed so as to function properly and be modified easily. Common
approach is to partition the task into small components rather than having one monolithic system.
The various structures of operating systems are:
1. Simple structured OS
2. Layered Approach
3. Micro-kernels
4. Modules
SIMPLE STRUCTURED OS
Explain the simple structured operating system with neat diagram
 These OS are simple, small and limited systems
 MS-DOS and UNIX is the examples for simple OS
 MS-DOS which is written to provide the most functionality in the least space
Disadvantages:
 It was not divided into modules carefully
 The interfaces and levels of functionality are not well separated

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 28

OPERATING SYSTEMS MODULE 1

Explain the simple structured UNIX-operating system with neat diagram

UNIX OS has two parts:
1. Kernel and
2. System programs.
 The kernel is further separated into a series of interfaces and device drivers.
 Everything below the system-call interface and above the physical hardware is the
kernel.
 The kernel provides following functions through system calls:
→ file system
→ CPU scheduling and
→ Memory management.
Disadvantage:
 Difficult to enhance, as changes in one section badly affects other areas.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 29

OPERATING SYSTEMS MODULE 1

LAYERED APPROACH
Explain the advantages of layered approach OS with neat diagram

 The OS is divided into a number of layers.

 Each layer is built on the top of another layer.
 The bottom layer is the hardware.
o The highest is the user interface
 A layer is an implementation of an abstract-object.
o i.e. The object is made up of
 data and
 operations that can manipulate the data.
 The layer consists of a set of routines that can be invoked by higher-layers.
Higher-layer
o does not need to know how lower-layer operations are implemented
o needs to know only what lower-layer operations do.
Advantage:
1) Simplicity of construction and debugging.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 30

OPERATING SYSTEMS MODULE 1

Disadvantages:
1) Less efficient than other types.

2) Appropriately defining the various layers.

MICRO-KERNEL APPROACH
Explain the advantages of Micro-kernel approach OS with neat diagram
Main function:
 To provide a communication facility between
 client program and
 various services running in user-space.

 Communication is provided by message passing

 All non-essential components are
 removed from the kernel and
 implemented as system- & user-programs.

Advantages:
1) Ease of extending the OS. (New services are added to user space w/o modification of
kernel).
2) Easier to port from one hardware design to another.
3) Provides more security & reliability.(If a service fails, rest of the OS remains
untouched.).
4) Provides minimal process and memory management.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 31

OPERATING SYSTEMS MODULE 1

Disadvantage:
1. Performance decreases due to increased system function overhead
2. Performance overhead of user space to kernel space communication.

MODULAR-KERNEL APPROACH (MODULES)

Analyze the modular kernel approach with neat diagram.

Solaris loadable modules

The kernel has
→ set of core components and
→ dynamic links in additional services during boot time
Seven types of modules in the kernel
1. Scheduling classes
2. File systems
3. Loadable system calls
4. Executable formats
5. STREAMS modules
6. Miscellaneous
7. Device and bus drivers
The top layers include
→ application environments and
→ set of services providing a graphical interface to applications.
Kernel environment consists primarily of
→ Mach microkernel and

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 32

OPERATING SYSTEMS MODULE 1

→ BSD kernel.
Mach provides
→ memory management;
→ support for RPCs & IPC and
→ thread scheduling.
BSD component provides
→ BSD command line interface
→ support for networking and file systems and
→ implementation of POSIX APIs
The kernel environment provides an I/O kit for development of
→ device drivers and
→ dynamic loadable modules (which Mac OS X refers to as kernel extensions).

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 33

OPERATING SYSTEMS MODULE 1

VIRTUAL MACHINES

******What are Virtual Machines? With neat diagram explain the concept of
virtualization and its advantages.
A virtual machine (VM) is a software program or operating system that not only exhibits the
behavior of a, separate computer hardware, but is also capable of performing tasks such as
running applications and programs like a separate computer.
• The fundamental idea behind the virtual machine is to abstract the hardware of a single
computer (CPU, memory, disk drives, network interface cards) into several execution
environments thereby creating an illusion that each separate execution environment is
running its own private computer.
• The operating system creates the illusion of multiple processes, each executing on its own
processor with its own (virtual) memory.
• Major difficulty is disk systems.

a) Non-virtual machine b) Virtual machine

The virtual-machine provides
 an interface that is identical to the underlying hardware.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 34

OPERATING SYSTEMS MODULE 1

 a (virtual) copy of the underlying computer to each process.

Problem:
 Virtual-machine software itself will need substantial disk space to provide
virtual memory.
Solution: provide virtual disks that are identical in all respects except size.
Advantages:
1) Complete protection of the various system resources.
2) It is a perfect vehicle for OS‟s R&D.
Disadvantage:
1. Difficult to implement due to effort required to provide an exact duplicate to
underlying machine.

IMPLEMENTATION OF VIRTUAL MACHINE

Explain how virtual machines are implemented.

 Though virtual machine concept is useful it is difficult to implement

 Much work is required to provide an exact duplicate of underlying machine
 The underlying machine has two modes: user mode and kernel mode
 Virtual machine software can run in kernel mode
 Virtual machine itself can run in user mode
 We have virtual user mode and virtual kernel mode with, transfer of control from
virtual user mode to virtual kernel mode on virtual machine.
 The CPU is multi-programmed among many virtual machines.
BENEFIT OF CREATING VIRTUAL MACHINE
Explain the benefit of creating virtual machine
 All virtual machines share the same hardware yet run different execution environment
 Host system is protected from the virtual machine just as virtual machines are protected
from each other. (virus)
 There is no direct sharing of resources
 However it is made possible to share the file-system volume and thus share files

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 35

OPERATING SYSTEMS MODULE 1

 Network of virtual machines each of which can send information over the virtual
communication network
 Virtual machine is a perfect vehicle of research and development
 The current operating system must be stopped and taken out of use while changes are
made and tested. This period is called as system development time.
 Multiple operating systems can be running in developers workstation concurrently
 Data center use is system consolidation (run two or more separate system and run in
virtual machine of one system)
VMWARE
*****Explain VM-WARE architecture of virtual machine with neat diagram

Key Idea: This virtualization tool run in user mode as an application on top of the operating
system such as Windows or Linux and allows this host system to concurrently execute several
different guest operating systems as independent virtual machines.
• VM-WARE abstracts intel 8086 and compatible hardware into isolated virtual machines
• Linux OS is running as the host OS: FreeBSD, Windows NT and Windows XP are
running as guest OS

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 36

OPERATING SYSTEMS MODULE 1

• The virtualization layer is the heart of VM-WARE, as it abstracts the physical hardware
into isolated virtual machines running as guest operating systems.
• Each virtual machine has its own virtual CPU, memory, disk drives, network interface
and so forth.
• An application could be tested concurrently in one physical computer with different OS
using VMware.
• Programmer could test the application on a host operating system and on three guest
operating systems with each system running as a separate virtual machine by using
VMware
JAVA VIRTUAL MACHINE
Explain VM-WARE architecture of virtual machine with neat diagram

 Java provides the specification of java virtual machine

 Java objects are specified with class construct
 Java program consists of one or more classes
 For each java class the compiler produces a architectural neutral bytecode.
 JVM is a specification for an abstract computer
 Class loader and java interpreter
 Garbage collection
 JVM can be implemented on top of host OS, hardware

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 37

OPERATING SYSTEMS MODULE 1

 Java interpreter interprets the bytecode operations one at a time

 A faster software technique is to use just-in-time(JIT) compiler
PROCESS CONCEPT
Question that arises in discussing operating systems involves what to call all the CPU activities.
A batch system executes jobs, whereas a time-shared system has user programs, or tasks. Even
on a single-user system such as Microsoft Windows, a user may be able to run several programs
at one time: a word processor, a web browser, and an e-mail package. Even if the user can
execute only one program at a time, the operating system may need to support its own internal
programmed activities, such as memory management. In many respects, all these activities are
similar, so we call all of them processes.
***What is Process?
Process is a program in execution.
A process execution must progress in sequential fashion. It has multiple parts such as Text
section, program counter, stack, data section and heap.
PROCESS IN MEMORY
Explain the process in memory
Process includes
1. Program Counter to indicate the address of the next instruction to be executed for this
process.
2. Registers Content of the processor.
3. Process Stack contains temporary data.
4. Data Section contains global variables.
5. Heap is memory that is dynamically allocated during process runtime
A program by itself is not a process.
1) A process is an active-entity.
2) A program is a passive-entity such as an executable-file stored on disk.
A program becomes a process when an executable-file is loaded into memory. If you run many
copies of a program, each is a separate process. The text-sections are equivalent, but the data-
sections vary.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 38

OPERATING SYSTEMS MODULE 1

Process in Memory
PROCESS STATE
*****Explain the process state with suitable transition diagram
As a process executes, it changes state. Each process may be in one of the following states
 New: The process is being created.
 Running: Instructions are being executed.
 Waiting: The process is waiting for some event to occur (such as I/O completions).
 Ready: The process is waiting to be assigned to a processor.
 Terminated: The process has finished execution.
Only one process can be running on any processor at anyinstant.

Transition diagram of process state

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 39

OPERATING SYSTEMS MODULE 1

PROCESS CONTROL BLOCK

******What is process control block (PCB)? Explain with neat diagram
Information associated with each process in an operating system is represented as process control
block (PCB) or task control block.
PCB contains following information about a process
Process State: The state may be new, ready, running, waiting, halted, and so on Program
Counter
Program Counter: This indicates the address of the next instruction to be executed for the
process.
CPU Registers: These include
→ accumulators (AX)
→ index registers (SI,DI)
→ stack pointers (SP)and
→ general-purpose registers (BX, CX, DX).
CPU Scheduling Information
 This includes
→ priority of process
→ pointers to scheduling-queues and
→ scheduling-parameters.
Management Information
 This includes
→ value of base- & limit-registers and
→ value of page-tables( or segment-tables).
Accounting Information
 This includes
→ amount of CPU time
→ time-limit and
→ process-number.
I/O Status Information
 This includes. list of I/O devices and list of open files.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 40

OPERATING SYSTEMS MODULE 1

PCB structure

PROCESS SCHEDULING
The main Objective of multiprogramming is to have some process running at all times to
maximize CPU utilization.
The main objective of time-sharing is to switch the CPU between processes so frequently that
users can interact with each program while it is running.
To meet above 2 objectives: Process scheduler is used to select an available process for
program- execution on the CPU.

SCHEDULING QUEUES
There are three types of scheduling-queues:
JOBQUEUE
 This queue consists of all processes in the system.
 As processes enter the system, they are put into a job-queue.
READYQUEUE
 This queue consists of the processes that are
 Residing in main-memory and
 Ready & waiting to execute
 This queue is generally stored as a linked list.
 A ready-queue header contains pointers to the first and final PCBs in the list.
 Each PCB has a pointer to the next PCB in the ready-queue.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 41

OPERATING SYSTEMS MODULE 1

DEVICE QUEUE
 This queue consists of the processes that are waiting for an I/O device.
 Each device has its own device-queue.

The ready-queue and various I/O device-queues

REPRESENTATION OF PROCESS SCHEDULING

Briefly explain process scheduling queues with neat block diagram

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 42

OPERATING SYSTEMS MODULE 1

Each rectangular box represents a queue. Two types of queues are present: the ready queue and a
set of device queues. The circles represent the resources that serve the queues, and the arrows
indicate the flow of processes in the system.
A new process is initially put in the ready queue. It waits there until it is selected for execution,
or is dispatched. Once the process is allocated the CPU and is executing. When the process is
executing, one of following events could occur
1) The process could issue an I/O request and then be placed in an I/O queue.
2) The process could create a new sub-process and wait for the sub-process's termination.
3) The process could be interrupted and put back in the ready-queue.
In the first two cases, the process eventually switches from the waiting state to the ready state
and is then put back in the ready queue. A process continues this cycle until it terminates, at
which time it is removed from all queues and has its PCB and resources de-allocated.
SCHEDULERS
A process migrates among the various scheduling queues throughout its lifetime. The operating
system must select, for scheduling purposes, processes from these queues in some fashion. This
selection process is carried out by the appropriate scheduler.

***What are schedulers? Explain any one type of scheduler

Scheduler is the system software, which select the processes form scheduling queues in some
fashion for scheduling purposes
There are three types of schedulers:
1) Long-term scheduler

2) Short-term scheduler and Explain any one in detail

3) Medium-term schedulers
LONG-TERM SCHEDULER
 Also called job scheduler.
 Selects which processes should be brought into the ready-queue.

 Need to be invoked only when a process leaves the system and therefore executes
much less frequently.
 Controls the degree of multiprogramming.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 43

OPERATING SYSTEMS MODULE 1

What is degree of multi-programming?

The number of processes in main memory is called as degree of multi-programming.
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.
Processes can be described as either:
1) I/O-bound Process
 Spends more time doing I/O operation than doing computations, many short CPU
bursts.(CPU execution time)
2) CPU-bound Process
 Spends more time doing computations than doing I/O operation and few process’s have very
long CPU bursts.
Why long-term scheduler should select a good process mix of I/O-bound and CPU-bound
processes? OR
Why it is important for the scheduler to distinguish I/O bound programs from CPU bound
programs
The reason is:
1. If all processes are I/O bound, then
i) Ready-queue will almost always be empty, and
ii) Short-term scheduler will have little work to do.
2) If all processes are CPU bound, then
i) I/O waiting q
ii)
iii) ueue will almost always be empty (devices will go unused) and system will be
unbalanced.
SHORT-TERM SCHEDULER
 Also called CPU scheduler.
 Selects which process should be executed next and allocates CPU.

 Need to be invoked to select a new process for the CPU and therefore executes much
more frequently.
 Must be fast, a process may execute for only a few milliseconds.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 44

OPERATING SYSTEMS MODULE 1

****Differentiate between Long-term scheduler and Short-term scheduler

Long-Term Scheduler Short-Term Scheduler
Also called job scheduler. Also called CPU scheduler.
Selects which processes should be brought into Selects which process should be executed next
the ready-queue. and allocates CPU.
Need to be invoked only when a process leaves Need to be invoked to select a new process for
the system and therefore executes much less the CPU and therefore executes much more
frequently. frequently.
May be slow minutes may separate the Must be fast a process may execute for only a
creation of one new process and the next. few milliseconds.
Controls the degree of multiprogramming.

MEDIUM-TERM SCHEDULER
 Some time-sharing systems have medium-term scheduler
 The scheduler removes processes from memory and thus reduces the degree of
multiprogramming.
 Later, the process can be reintroduced into memory, and its execution can be
continued where it left off. This scheme is called swapping.
 The process is swapped out, and is later swapped in, by the scheduler.
 Swapping is necessary to improve the process mix or requiring memory to be freed up.

Medium-term scheduling in Queuing diagram

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 45

OPERATING SYSTEMS MODULE 1

CONTEXT SWITCH
***Define context switch? What is the need for context switch?
Context-switch means saving the state of the old process and switching the CPU to another
process.
In general purpose systems interrupts cause the OS to change a CPU from its current task and to
run a kernel routine. When an interrupt occurs, the system needs to save the current context of
the process currently running on the CPU so that it can restore that context when its processing is
done, essentially suspending the process and then resuming it.
The context of a process is represented in the PCB of the process; it includes
 value of CPU registers
 process-state and
 memory-management information.
Disadvantages:
 Context-switch time is pure overhead, because the system does no useful
work while switching.
 Context-switch times are highly dependent on hardware support
OPERATIONS ON PROCESSES
1) Process Creation and

2) Process Termination

Process Creation
• A process may create a new process via a create-process system-call.

• The creating process is called a [Link] new process created by the parent is called

the child-process (Sub-process).

• OS identifies processes by pid (process identifier), which is typically an integer-number.

• A process needs following resources to accomplish the task:

→ CPU time
→ memory and
→ I/O devices.
• Child-process may

→ get resources directly from the OS or

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 46
OPERATING SYSTEMS MODULE 1

→ get resources of parent-process. This prevents any process from overloading the
system.
• Two options exist when a process creates a new process:

1) The parent & the children execute concurrently.

2) The parent waits until all the children have terminated.

• Two options exist in terms of the address-space of the new process:

1) The child-process is a duplicate of the parent-process (it has the same

program and data as the parent).

2) The child-process has a new program loaded into it.

PROCESS CREATION IN UNIX

In UNIX, each process is identified by its process identifier (pid), which is a unique integer. A
new process is created by the fork() system-call. The new process consists of a copy of the
address-space of the original process.
Both the parent and the child continue execution with one difference:
1) The return value for the fork() is

zero for the new (child) process.

2) The return value for the fork() is

Non-zero pid of the child for the parent-process.

Typically, the exec() system-call is used after a fork() system-call by one of the two
processes to replace the process's memory-space with a new program. The parent can
issue wait() system-call to move itself off the ready-queue.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 47

OPERATING SYSTEMS MODULE 1

Creating a separate process using the UNIX fork() system-call

Process creation using the fork() system-call

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 48

OPERATING SYSTEMS MODULE 1

PROCESS TERMINATION
A process terminates when it executes the last statement (in the program). Then, the OS deletes
the process by using exit() system-call. Then, the OS de-allocates all the resources of the process.
The resources include memory, open files and I/O buffers.
Process termination can occur in following cases:
 A process can cause the termination of another process via TerminateProcess() system-

call.
 Users could arbitrarily kill the processes.

A parent terminates the execution of children for following reasons:

 The child has exceeded its usage of some resources.
 The task assigned to the child is no longer required.
 The parent is exiting, and the OS does not allow a child to continue.
In some systems, if a process terminates, then all its children must also be terminated.
This phenomenon is referred to as cascading termination.

INTER PROCESS COMMUNICATION (IPC)

Processes executing concurrently in the OS may be 1) Independent processes or 2) Co-operating
processes.
A process is independent if
i) The process cannot affect or be affected by the other processes.

ii) The process does not share data with other processes.

A process is co-operating if
i) The process can affect or be affected by the other processes.

ii) The process shares data with other processes.

Advantages of process co-operation (Cooperative process)

1) Information Sharing

 Since many users may be interested in same piece of information (ex: shared file).

2) Computation Speedup

 We must break the task into subtasks.

 Each subtask should be executed in parallel with the other subtasks.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 49

OPERATING SYSTEMS MODULE 1

 The speed can be improved only if computer has multiple processing elements such as

CPUs or I/O channels.

3) Modularity

 Divide the system-functions into separate processes or threads.

4) Convenience

 An individual user may work on many tasks at the same time.

 For example, a user may be editing, printing, and compiling in parallel.

What is Inter-process communication? Briefly explain its types

Inter-process communication (IPC) is a set of programming interfaces that allow a programmer
to coordinate activities among different program processes that can run concurrently in
an operating system.
Cooperating processes require an IPC mechanism that will allow them to exchange data and
information.
Two basic models of IPC:
1. Shared-memory and
2. Message passing.
SHARED MEMORY SYSTEMS

Shared memory system

 Communicating-processes must establish a region of shared-memory.
 A shared-memory resides in address-space of the process creating the shared-memory.
 Other processes must attach their address-space to the shared-memory.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 50

OPERATING SYSTEMS MODULE 1

 The processes can then exchange information by reading and writing data in the shared-
memory. The processes are also responsible for ensuring that they are not writing
to the same location simultaneously
Let us illustrate Cooperative process with
PRODUCER-CONSUMER PROBLEM
Producer-process produces information that is consumed by a consumer-process.
Example (client- server, compiler-assembler, loader)
To allow producer and consumer to run concurrently, have a buffer of items to be filled by the
producer and emptied by the consumer. The buffer resides in a memory shared by producer and
consumer. Producer and consumer must be synchronized. Two types of buffer that can be used
are:
1. Unbounded-buffer places no practical limit on the size of the buffer
2. Bounded-buffer assumes that there is a fixed buffer size. Advantages: It allows
maximum speed and convenience of communication, faster
Explain the implementation of producer-consumer processes using bounded buffer in
shared memory systems.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 51

OPERATING SYSTEMS MODULE 1

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 52

OPERATING SYSTEMS MODULE 1

MESSAGE-PASSING SYSTEMS

Discuss the methods to implement message passing IPC in detail.

Message passing systems allow processes to communicate and to synchronize their actions
without sharing the same address-space. For example, a chat program used on the WWW.
Messages can be of 2 types: 1) Fixed size or
2) Variable size.
If fixed-sized messages are used, the system-level implementation is simple. However, the
programming task becomes more difficult.
If variable-sized messages are used, the system-level implementation is complex. However, the
programming task becomes simpler.
A communication-link must exist between processes to communicate. The three methods for
implementing a link are:
1) Direct or indirect communication.

2) Synchronous or asynchronous communication. Explain any one in detail

3) Automatic or explicit buffering.

IPC in message passing system provides two operations:

1) Send (P, message): Send a message to process P.

2) Receive (Q, message): Receive a message from process Q.

Advantages:
1) Useful for exchanging smaller amounts of data.

2) Easier to implement.

3) Useful in a distributed environment.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 53

OPERATING SYSTEMS MODULE 1

1. DIRECT OR INDIRECT COMMUNICATION.

*****Explain direct and indirect communication with respect to message passing system.
Direct communication:
Each process must explicitly name the recipient/sender.

Properties of a communication link:

 A link is established automatically between every pair of processes that want to
communicate. The processes need to know only each other‟s identity to communicate.
 A link is associated with exactly two processes.
 Exactly one link exists between each pair of processes.

Symmetric addressing: Both sender and receiver processes must name the other to
communicate.
Messages are sent to/received from mailboxes (or ports).
Properties of a communication link:
 A link is established between a pair of processes only if both members have a shared

mailbox.
 A link may be associated with more than two processes.

 A number of different links may exist between each pair of communicating processes.

Mailbox owned by a process:

 The owner can only receive, and the user can only send.

 The mailbox disappears when its owner process terminates.

Mailbox owned by the OS:

 The OS allows a process to:

1. Create a new mailbox

2. Send & receive messages via it

3. Delete a mailbox.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 54

OPERATING SYSTEMS MODULE 1

Differentiate between direct and indirect inter-process communication

Direct Communication Indirect Communication
Each process must explicitly name the Messages are sent to/received
recipient/sender. from mailboxes (or ports).
Properties of a communication link: Properties of a communication link:
 A link is established automatically between  A link is established between a pair of

every pair of processes that want to processes only if both members have a
communicate. The processes need to know shared mailbox.
only each other‟s identity to communicate.  A link may be associated with more than

 A link is associated with exactly two two processes.

processes.  A number of different links may exist

 Exactly one link exists between each pair of between each pair of communicating
processes. processes.
Symmetric addressing: Mailbox owned by a process:
 Both sender and receiver processes must  The owner can only receive, and the user

name the other to communicate. can only send.

 The mailbox disappears when its owner

process terminates.
Asymmetric addressing: Mailbox owned by the OS:
 Only the sender names the recipient; the  The OS allows a process to:

recipient needn't name the sender. 1. Create a new mailbox

2. Send & receive messages via it

3. Delete a mailbox.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 55

OPERATING SYSTEMS MODULE 1

2. SYNCHRONIZATION
Communication takes place through send() and receive primitives. Message passing may
be either blocking or non-blocking (also known as synchronous and asynchronous).
Synchronous Message Passing
Blocking is considered synchronous
Blocking send:
 The sending process is blocked until the message is received by the receiving process or by
the mailbox.
Blocking receive:
 The receiver blocks until a message is available.
Asynchronous Message Passing
Non-blocking is considered asynchronous
Non-blocking send:
 The sending process sends the message and resumes operation.

Non-blocking receive:
 The receiver retrieves either a valid message or a null.

3. BUFFERING
Messages exchanged by processes reside in a temporary queue. Queue can be implemented in
one of three ways.
1) Zero Capacity

 The queue-length is zero.

 The link can't have any messages waiting in it.

 The sender must block until the recipient receives the message.

2) Bounded Capacity

 The queue-length is finite.

 If the queue is not full, the new message is placed in the queue.

 The link capacity is finite.

 If the link is full, the sender must block until space is available in the queue.

3) Unbounded Capacity

 The queue-length is potentially infinite.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 56

OPERATING SYSTEMS MODULE 1

 Any number of messages can wait in the queue.

 The sender never blocks.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 57

 MODULE 2

Multi-threaded Programming: Overview; Multithreading models; Thread Libraries, Threading issues.

Process Scheduling: Basic concepts; Scheduling Criteria; Scheduling Algorithms; Multiple-processor

scheduling; Thread scheduling. Process Synchronization: Synchronization: The critical section

problem; Peterson’s solution; Synchronization hardware; Semaphores; Classical problems of

synchronization; Monitors.
OPERATING SYSTEMS MODULE 2

MULTITHREADED PROGRAMMING

What is a thread?
A thread is a basic unit of CPU utilization. It comprises thread id, program counter, register set,
and a stack.

 Thread shares with other threads belonging to the same process its code section, data
section and other OS resources. Threads run within an application.
 Traditional process has single thread of control (heavy weight) .
 If a process has multiple threads of control, it can perform more than one task at a time.
 Multiple tasks with the application can be implemented by separate threads such as Update
display, Fetch data, Spell checking and Answer a network request
What is the difference between process and thread.
S. No. Process Thread

1 Program in execution It is the basic unit of CPU utilization. It

is part of process.
2 Processes run in separate Threads within the same process run in
memory spaces. a shared memory space.
3 Heavy weight process, since it Light weight process, it consumes few
consumes most of the resources in the system.
resources in the system
4 Creation of process requires Creation of thread requires less time
more time
5 Context switching takes more Context switching is faster (takes less
time time )
6 More time required for Less time for termination
termination
7 Less efficient as compared to Enhances efficiency in the context of
the process in the context of communication.
communication.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 1

OPERATING SYSTEMS MODULE 2

Why do we need multiple-thread programming?

Suppose a process with single thread programming is used in a Web server system. A single
application may be required to perform several similar tasks. Server runs as a single process and
accepts request. When server receives a request it creates another process to service the request.
Process creation is time consuming and resource intensive. Hence it is more efficient to use one
process that has multiple threads. Here server creates a separate thread to listen for client
requests. When request is made it creates another thread to service the request. Hence it can
simplify code, and increases efficiency.

MULTI-THREADING BENEFITS
******Discuss the benefits of multi-threaded programming.
The benefits of multi-threaded programming are:
1. Responsiveness
2. Resource Sharing
3. Economy
4. Scalability

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 2

OPERATING SYSTEMS MODULE 2

Responsiveness: may allow continued execution if part of process is blocked, especially

important for user interfaces (web browser)
Resource Sharing: threads share resources of process, easier than shared memory or message
passing.
Economy: cheaper than process creation, thread switching lower overhead than context
switching.
Scalability: In a multiprocessor architecture, threads may be running in parallel on different
processors. Thus parallelism will be increased.
SUPPORT FOR THREADS
Support for threads may be provided either at the user level, for User threads or by the kernel, for
kernel threads.
1. User-level Thread
2. Kernel-level Thread
What is the difference between user-level thread and kernel- level thread?
S. No. User-Level Thread Kernel-Level Thread
1 User threads are supported above the Kernel threads are supported directly by the
kernel and are implemented by operating system.
a thread library at the user level. The The kernel performs thread creation,
library provides support for thread scheduling, and management in kernel space.
creation scheduling, and management
with no support from the kernel.
2 User-level threads are generally fast The kernel-level threads are slow and
to create and manage inefficient. For instance, threads operations are
hundreds of times slower than that of user-level
threads.
3 User level thread is generic and can Kernel level thread is specific to the operating
run on any operating system. system.
4 When threads are managed in user No run-time system is needed in each. Also,
space, each process needs its own there is no thread table in each process. Instead,
private thread table to keep track of the kernel has a thread table that keeps track of
the threads in that process all the threads in the system.
5 Example: User-thread libraries Example: Windows NT, Windows 2000, Solaris
include POSIX Pthreads, Mach C- 2, BeOS, and Tru64 UNIX (formerly Digital
threads, and Solaris 2 UI-threads. UNIX)-support kernel threads.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 3

OPERATING SYSTEMS MODULE 2

MULTITHREADING MODELS
*********Explain multi-threading models in detail OR
******Discuss the three common ways of establishing relationship between user and kernel
threads.
Three ways of establishing relationship between user-threads & kernel-threads (Multi-threading
model):
1) Many-to-one model
2) One-to-one model and
3) Many-to-many model.
Many to One model:

 Many user-level threads are mapped to single kernel thread.

 Thread management is done by the thread library in user space, so it is efficient.
 The entire process will block if a thread makes a blocking system-call.
 Multiple threads may not run in parallel on multi-processor system because only one may
be in kernel at a time.
 Few systems currently use this model.
Examples: Solaris -Green Threads, GNU Portable Threads etc.
One-to- Many model:

 Each user thread is mapped to a kernel thread

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 4

OPERATING SYSTEMS MODULE 2

Advantages:
 It provides more concurrency by allowing another thread to run when a thread makes a
blocking system-call.
 Multiple threads can run in parallel on multiprocessors.
Disadvantage:
 Creating a user thread requires creating the corresponding kernel thread.
Example:
→ Windows NT/XP/2000, Linux

Many-to-Many model:
• Many user-level threads are multiplexed to a smaller number of kernel threads

Advantages:
1) Developers can create as many user threads as necessary

2) The kernel threads can run in parallel on a multiprocessor.

3) When a thread performs a blocking system-call, kernel can schedule another thread

for execution.

Many-to-many model
THREAD LIBRARIES
It provides the programmer with an API for the creation and management of threads.
Two ways of implementation:
1) First Approach

 Provides a library entirely in user space with no kernel support.

 All code and data structures for the library exist in the user space.

2) Second Approach

 Implements a kernel-level library supported directly by the OS.

 Code and data structures for the library exist in kernel space.
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 5
OPERATING SYSTEMS MODULE 2

Three main thread libraries: 1) POSIX Pthreads

2) Win32 and

3) Java.

Pthreads
• This is a POSIX standard API for thread creation and synchronization.

• This is a specification for thread-behavior, not an implementation.

• OS designers may implement the specification in any way they wish.

• Commonly used in: UNIX and Solaris.

Java Threads
• Threads are the basic model of program-execution in Java program and Java language.

• The API provides a rich set of features for the creation and management of threads.

• All Java programs comprise at least a single thread of control.

Two techniques for creating threads:

1) Create a new class that is derived from the Thread class and override its run() method.
2) Define a class that implements the Runnable interface. The Runnable interface
is defined as follows:

THREADING ISSUES
***Discuss any 3 threading issues that come with multi-threaded programs

1. System call fork() and exec() in multi-thread programming

2. Thread cancellation

3. Signal handling

4. Thread pools

System call fork() is used to create a separate, duplicate process. If one thread in a program calls
fork(), then some systems duplicates all threads and other systems duplicate only the thread that
invoked the fork(). If a thread invokes the exec(), the program specified in the parameter to exec()
will replace the entire process including all threads.
Thread Cancellation: This is the task of terminating a thread before it has completed. Target
thread is the thread that is to be canceled. Thread cancellation occurs in two different cases:
3) Asynchronous cancellation: One thread immediately terminates the target thread.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 6

OPERATING SYSTEMS MODULE 2

4) Deferred cancellation: The target thread periodically checks whether it should be

terminated.
Signal Handling: In UNIX, a signal is used to notify a process that a particular event has
occurred. All signals follow this pattern:
1. A signal is generated by the occurrence of a certain event.
2. A generated signal is delivered to a process.
3. Once delivered, the signal must be handled.
A signal handler is used to process signals. A signal may be received either synchronously or
asynchronously, depending on the source.
1) Synchronous signals

 Delivered to the same process that performed the operation causing the signal.

 E.g. illegal memory access and division by 0.

2) Asynchronous signals

 Generated by an event external to a running process.

 E.g. user terminating a process with specific keystrokes <ctrl><c>.

Every signal can be handled by one of two possible handlers:

1) A Default Signal Handler

 Run by the kernel when handling the signal.

2) A User-defined Signal Handler

 Overrides the default signal handler.

In single-threaded programs, delivering signals is simple.

In multithreaded programs, delivering signals is more complex. Then, the following options exist:
1) Deliver the signal to the thread to which the signal applies.

2) Deliver the signal to every thread in the process.

3) Deliver the signal to certain threads in the process.

4) Assign a specific thread to receive all signals for the process.

Thread Pools: The basic idea is to create a no. of threads at process-startup and place the threads
into a pool (where they sit and wait for work).
Procedure:
1. When a server receives a request, it awakens a thread from the pool.
2. If any thread is available, the request is passed to it for service.
Once the service is completed, the thread returns to the pool.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 7

OPERATING SYSTEMS MODULE 2

Advantages:
1) Servicing a request with an existing thread is usually faster than waiting to create a

thread.
2) The pool limits the no. of threads that exist at any one point.

No. of threads in the pool can be based on factors such as: no. of CPUs, amount of
memory and expected no. of concurrent client-requests.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 8

OPERATING SYSTEMS MODULE 2

PROCESS SCHEDULING

Basic Concepts: In a single-processor system, only one process may run at a time and other
processes must wait until the CPU is rescheduled. The main objective of multiprogramming is to
have some process running at all times, in order to maximize CPU utilization.
CPU-I/O Burst Cycle: Process execution consists of a cycle of CPU execution and an I/O wait as
shown in below figure. Process execution begins with a CPU burst, followed by an I/O burst, then
another CPU burst, etc… Finally, a CPU burst ends with a request to terminate execution. An I/O-
bound program typically has many short CPU bursts. A CPU-bound program might have a few
long CPU bursts.
CPU SCHEDULER

CPU scheduler selects a waiting-process from the ready-queue and allocates CPU to the waiting-
process. The ready-queue could be a FIFO, priority queue, tree and list. The records in the queues
are generally process control blocks (PCBs) of the processes.
CPU SCHEDULING
Four situations under which CPU scheduling decisions take place:
1. When a process switches from the running state to the waiting state. For ex; I/O request.
2. When a process switches from the running state to the ready state. For ex: when an
interrupt occurs.
3. When a process switches from the waiting state to the ready state. For ex: completion of
I/O.
4. When a process terminates.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 9

OPERATING SYSTEMS MODULE 2

Scheduling under 1 and 4 is on-preemptive. Scheduling under 2 and 3 is preemptive.

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.
Preemptive Scheduling
This is driven by the idea of prioritized computation. Processes that are runnable may be
temporarily suspended
Disadvantages:
1) Incurs a cost associated with access to shared-data.

2) Affects the design of the OS kernel.

Dispatcher
It gives control of the CPU to the process selected by the short-term scheduler. The function
involves:
1) Switching context
2) Switching to user mode &
3) Jumping to the proper location in the user program to restart that program.
It should be as fast as possible, since it is invoked during every process switch.
Dispatch latency means the time taken by the dispatcher to stop one process and to start another
process to run.
SCHEDULING CRITERIA USED IN OS

******Discuss the scheduling criteria used in operating system.

The various scheduling criteria used in OS are:

1. CPU Utilization
2. Throughput
3. Turnaround time
4. Waiting time
5. Response time
CPU Utilization: We must keep the CPU as busy as possible. In a real system, it ranges from
40% to 90%.
Throughput: The number of processes completed per time unit. For long processes, throughput
may be 1 process per hour; For short transactions, throughput might be 10 processes per second.
Turnaround Time: The interval from the time of submission of a process to the time of
completion. Turnaround time is the sum of the periods spent in waiting to get into memory,

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 10

OPERATING SYSTEMS MODULE 2

waiting in the ready-queue, executing on the CPU and doing I/O.

Waiting Time: The amount of time that a process spends waiting in the ready-queue.
Response Time: The time from the submission of a request until the first response is produced.
SCHEDULING ALGORITHMS
CPU scheduling deals with the problem of deciding which of the processes in the ready queue is
to be allocated the CPU. Following are some scheduling algorithms:
1) FCFS scheduling (First Come First Served)
2) Round Robin scheduling
3) SJF scheduling (Shortest Job First)
4) SRT scheduling(Shortest Remaining Time First)
5) Priority scheduling with and without preemption.
6) Multilevel Queue scheduling and
7) Multilevel Feedback Queue scheduling
FCFS SCHEDULING
The process that requests the CPU first is allocated the CPU first. That means process which
arrives the ready-queue first, get scheduled first if the CPU is free. This is a non-preemptive
scheduling concept. The implementation is easily done using a FIFO queue.
Procedure:
1) When a process enters the ready-queue, its PCB is linked onto the tail of the queue.
2) When the CPU is free, the CPU is allocated to the process at the queue‘s head.
3) The running process is then removed from the queue.
Advantage: Code is simple to write & understand.
Disadvantages:
1) Convoy effect: All other processes wait for one big process to get off the CPU.

2) Non-preemptive (a process keeps the CPU until it releases it).

3) Not good for time-sharing systems.

4) The average waiting time is generally not minimal.

Example: Suppose that the processes arrive in the order P1, P2, P3.

The Gantt Chart for the schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 11

OPERATING SYSTEMS MODULE 2

Waiting time for P1 = 0; P2 = 24; P3

= 27 Average waiting time: (0 +
24 + 27)/3 = 17
• Suppose that the processes arrive in the order P2, P3, P1.

The Gantt chart for the schedule is as follows:

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

Average waiting time: (6 + 0 + 3)/3 = 3

SJF SCHEDULING (Shortest Job First)

The CPU is assigned to the process that has the smallest next CPU burst. If two processes have
the same length CPU burst, FCFS scheduling is used to break the tie. For long-term scheduling in
a batch system, we can use the process time limit specified by the user, as the ‗length‘. SJF can't
be implemented at the level of short-term scheduling, because there is no way to know the length
of the next CPU burst.
Advantage: The SJF is optimal, i.e. it gives the minimum average waiting time for a given set of
processes.
Disadvantage: Determining the length of the next CPU burst.
SJF algorithm may be either 1) Non-preemptive or 2) preemptive.
Non preemptive SJF: The current process is allowed to finish its CPU burst.
Preemptive SJF: If the new process has a shorter next CPU burst time than what is left of the
executing process, that process is preempted. It is also known as SRTF scheduling (Shortest-
Remaining-Time-First).
Example (for non-preemptive SJF): Consider the following set of processes, with the
length of the CPU-burst time given in milliseconds.(Arrival of process according to their
Burst time)

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 12

OPERATING SYSTEMS MODULE 2

For non-preemptive SJF, the Gantt Chart is as follows:

Waiting time for P1 = 3; P2 = 16; P3 = 9; P4=0

Average waiting time: (3 + 16 + 9 + 0)/4 = 7ms
Example (preemptive SJF): Consider the following set of processes, with the length of the
CPU-burst time given in milliseconds.

For preemptive SJF, the Gantt Chart is as follows:

The average waiting time is ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 26/4 = 6.5ms.

PRIORITY SCHEDULING
A priority is associated with each process. The CPU is allocated to the process with the highest
priority. Equal-priority processes are scheduled in FCFS order. Priorities can be defined either
internally or externally. Internally-defined priorities use some measurable quantity to compute the
priority of a process.
For example: time limits, memory requirements, no. of open files.
Externally-defined priorities set by criteria that are external to the OS
For example: importance of the process, political factors
Priority scheduling can be either preemptive or non-preemptive.
Preemptive
 The CPU is preempted if the priority of the newly arrived process is higher

than the priority of the currently running process.

Non Preemptive
 The new process is put at the head of the ready-queue

Advantage: Higher priority processes can be executed first.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 13
OPERATING SYSTEMS MODULE 2

Disadvantage: Indefinite blocking, where low-priority processes are left waiting indefinitely for
CPU.
Solution: Aging is a technique of increasing priority of processes that wait in system for a long
time.
Example: Consider the following set of processes, assumed to have arrived at time 0, in
the order PI, P2, ..., P5, with the length of the CPU-burst time given in milliseconds.

The Gantt chart for the schedule is as follows:

The average waiting time is 8.2 milliseconds.

ROUND ROBIN SCHEDULING
It is designed especially for timesharing systems. It is similar to FCFS scheduling, but with
preemption. A small unit of time is called a time quantum (or time slice), which ranges from 10 to
100 ms.
The ready-queue is treated as a circular queue. The CPU scheduler goes around the ready-queue
and allocates the CPU to each process for a time interval of up to one time quantum. To
implement this algorithm, the ready-queue is kept as a FIFO queue of processes
CPU scheduler
1. Picks the first process from the ready-queue.
2. Sets a timer to interrupt after one time quantum and
3. Dispatches the process.
One of two things will then happen.
1. The process may have a CPU burst of less than that of time quantum. In this case, the
process itself will release the CPU voluntarily.
2. If the CPU burst of the currently running process is longer than that of time quantum, the
timer will go off and will cause an interrupt to the OS. The process will be put at the tail of
the ready-queue.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 14

OPERATING SYSTEMS MODULE 2

Advantage: Higher average turnaround than SJF.

Disadvantage: Better response time than SJF.
Example: Consider the following set of processes that arrive at time 0, with the length of
the CPU- burst time given in milliseconds.(Time quantum = 4ms)

The Gantt chart for the schedule is as follows:

The average waiting time is 17/3 = 5.66 milliseconds.

NOTE:
The RR scheduling algorithm is preemptive. No process is allocated the CPU for more than one
time quantum in a row. If a process' CPU burst exceeds the time quantum, that process is
preempted and is put back in the ready-queue..
The performance of algorithm depends heavily on the size of the time quantum
If time quantum= very large, RR policy is the same as the FCFS policy.
If time quantum = very small, RR approach appears the users as though each of n processes
If time quantum = very small, RR approach appears to the users as though each
of n processes has its own processor running at l/n the speed of the real
processor.
In software, we need to consider the effect of context switching on the performance of RR
scheduling
1) Larger the time quantum for a specific process time, less time is spend on context

switching.
2) The smaller the time quantum, more overhead is added for the purpose of context-

switching.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 15

OPERATING SYSTEMS MODULE 2

MULTILEVEL QUEUE SCHEDULING

It is useful for situations in which processes are easily classified into different groups.
For example, a common division is made between foreground (or interactive) processes and
background (or batch) processes. The ready-queue is partitioned into several separate queues. The
processes are permanently assigned to one queue based on some property like memory size,
process priority or process type. Each queue has its own scheduling algorithm.
For example, separate queues might be used for foreground and background processes.

Multilevel queue scheduling

There must be scheduling among the queues, which is commonly implemented as fixed-
priority preemptive scheduling.
For example, the foreground queue may have absolute priority over the background queue.
Time slice: each queue gets a certain amount of CPU time which it can schedule among
its processes; i.e., 80% to foreground in RR 20% to background in FCFS.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 16

OPERATING SYSTEMS MODULE 2

MULTILEVEL FEEDBACK QUEUE SCHEDULING

A process may move between queues. The basic idea is to separate processes according to the
features of their CPU bursts.
For example: If a process uses too much CPU time, it will be moved to a lower-priority queue.
This scheme leaves I/O-bound and interactive processes in the higher-priority queues. If a process
waits too long in a lower-priority queue, it may be moved to a higher- priority queue. This form
of aging prevents starvation.

Multilevel feedback queues.

In general, a multilevel feedback queue scheduler is defined by the following parameters:

1) The number of queues.

2) The scheduling algorithm for each queue.

3) The method used to determine when to upgrade a process to a higher priority queue.

4) The method used to determine when to demote a process to a lower priority queue.

5) The method used to determine which queue a process will enter when that

process needs service.

MULTIPLE PROCESSOR SCHEDULING
Write a shot note on multi-processor scheduling
If multiple CPUs are available, the scheduling problem becomes more complex. The two
approaches are:
Asymmetric Multiprocessing
The basic idea is: A master server is a single processor responsible for all scheduling decisions,
I/O processing and other system activities. The other processors execute only user code.
Advantage: This is simple because only one processor accesses the system data structures,
reducing the need for data sharing.
Symmetric Multiprocessing
The basic idea is: Each processor is self-scheduling. To do scheduling, the scheduler for each
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 17
OPERATING SYSTEMS MODULE 2

processor examines the ready-queue and selects a process to execute.

Restriction: We must ensure that two processors do not choose the same process and that
processes are not lost from the queue.
Processor Affinity: In SMP a system, Migration of processes from one processor to another are
avoided and instead processes are kept running on same processor. This is known as processor
affinity. The two forms are:
Soft Affinity: When an OS try to keep a process on one processor because of policy, but cannot
guarantee it will happen. It is possible for a process to migrate between processors.
Hard Affinity: When an OS have the ability to allow a process to specify that it is not to migrate
to other processors. Eg: Solaris OS
Load Balancing
This concept attempts to keep the workload evenly distributed across all processors in an SMP
system. The two approaches:
1) Push Migration
 A specific task periodically checks the load on each processor and if it finds an

imbalance, it evenly distributes the load to idle processors.

2) Pull Migration
 An idle processor pulls a waiting task from a busy processor.

THREAD SCHEDULING
On OSs, it is kernel-level threads but not processes that are being scheduled by the OS. The user-
level threads are managed by a thread library, and the kernel is unaware of them. To run on a
CPU, user-level threads must be mapped to an associated kernel-level thread.
Contention Scope
Two approaches:
1) Process-Contention scope
 On systems implementing the many-to-one and many-to-many models, the

thread library schedules user-level threads to run on an available LWP.

 Competition for the CPU takes place among threads belonging to the same process.

2) System-Contention scope
 The process of deciding which kernel thread to schedule on the CPU.

 Competition for the CPU takes place among all threads in the system.

 Systems using the one-to-one model schedule threads using only SCS.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 18

OPERATING SYSTEMS MODULE 2

Pthread Scheduling
Pthread API that allows specifying either PCS or SCS during thread creation.
Pthreads identifies the following contention scope values:
1. PTHREAD_SCOPEJPROCESS schedules threads using PCS scheduling.
2. PTHREAD-SCOPE_SYSTEM schedules threads using SCS scheduling.
Pthread IPC provides following two functions for getting and setting the contention scope policy:
1) pthread_attr_setscope(pthread_attr_t *attr, int scope)

2) pthread_attr_getscope(pthread_attr_t *attr, int *scope)

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 19

OPERATING SYSTEMS MODULE 2

PROBLEMS BASED ON VARIOUS PROCESSES SCHEDULING ALGORITHM

Solution steps:
1. Draw Gantt chart for the given problem.
2. From Gantt chart find the completion time of each process
3. Determine the Turnaround time using the formula:
Turnaround time = Completion time – Arrival time
4. Determine the waiting time using the formula:
Waiting time = Turnaround time – Burst time
5. Determine the Response time using the formula:
Response time = First time process scheduled – Arrival time

1. Consider the following set of processes with CPU burst time (in ms)
Process Arrival time Burst Time
P0 0 6
P1 1 3

P2 2 1

P3 3 4

Compute the waiting time and average turnaround time for the above process using
FCFS, SRT and RR (time quantum = 2ms) scheduling algorithm.
Solution:
i.) The Gantt chart for the FCFS schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting

Time time time
P0 0 6 6 6 0
P1 1 3 9 8 5

P2 2 1 10 8 7

P3 3 4 14 11 7

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 20

OPERATING SYSTEMS MODULE 2

Average Turnaround time = Sum of turnaround time/ no. of processes

= 33/4 = 8.25ms
Average waiting time = Sum waiting time/ no. of processes
= 19/4 = 4.75ms
ii.) The Gantt chart for the SRT schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting

Time time time
P0 0 6 14 14 8
P1 1 3 5 4 1

P2 2 1 3 1 0

P3 3 4 9 6 2

Average Turnaround time = Sum of turnaround time/ no. of processes

= 25/4 = 6.25ms
Average waiting time = Sum waiting time/ no. of processes
= 11/4 = 2.75ms
iii.) The Gantt chart for the RR (TQ = 2ms) schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting

Time time time
P0 0 6 12 12 6
P1 1 3 10 9 6

P2 2 1 5 3 2

P3 3 4 14 11 7

Average Turnaround time = Sum of turnaround time/ no. of processes

= 35/4 = 8.75ms
Average waiting time = Sum waiting time/ no. of processes
= 21/4 = 5.25ms
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 21
OPERATING SYSTEMS MODULE 2

2. Consider the following set of processes given in the table

Process Arrival time Burst Time Priority
P1 0 10 4
P2 3 5 2

P3 3 6 6

P4 5 4 3

Consider the large number as highest priority. Calculate the average waiting time and
turnaround time and draw Gantt chart for preemptive priority scheduling and preemptive
SJF scheduling.
Solution:
i.) The Gantt chart for the preemptive priority schedule is as follows: (Priority high= larger
number)

Process Arrival Burst Priority Completion Turnaround Waiting

time Time Time time time
P1 0 10 4 16 16 6
P2 3 5 2 25 22 17

P3 3 6 6 9 6 0

P4 5 4 3 20 15 11

Average Turnaround time = Sum of turnaround time/ no. of processes

= 59/4 = 14.75ms
Average waiting time = Sum waiting time/ no. of processes
= 34/4 = 8.5ms
ii.) The Gantt chart for the preemptive SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 10 25 25 15

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 22

OPERATING SYSTEMS MODULE 2

P2 3 5 8 5 0

P3 3 6 18 15 9

P4 5 4 12 7 3

Average Turnaround time = Sum of turnaround time/ no. of processes

= 52/4 = 13ms
Average waiting time = Sum waiting time/ no. of processes
= 27/4 = 6.75ms

3. For the following example calculate average waiting time and average turnaround time
using FCFS, preemptive SJF and RR ( 1 time unit) CPU scheduling algorithms
Process Arrival time Burst Time
P1 0 8
P2 1 4

P3 2 9

P4 3 5

Solution:
i.) The Gantt chart for the FCFS schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 8 8 8 0
P2 1 4 12 11 7

P3 2 9 21 19 10

P4 3 5 26 23 18

Average Turnaround time = Sum of turnaround time/ no. of processes

= 61/4 = 15.25ms
Average waiting time = Sum waiting time/ no. of processes
= 35/4 = 8.75ms

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 23

OPERATING SYSTEMS MODULE 2

ii.) The Gantt chart for the preemptive SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 8 17 17 9
P2 1 4 5 4 0

P3 2 9 26 24 15

P4 3 5 10 7 2

Average Turnaround time = Sum of turnaround time/ no. of processes

= 52/4 = 13ms
Average waiting time = Sum waiting time/ no. of processes
= 26/4 = 6.5ms

iii.) The Gantt chart for the RR(1 unit time) schedule is as follows

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 8 23 23 15
P2 1 4 13 12 8

P3 2 9 26 24 15

P4 3 5 20 17 12

Average Turnaround time = Sum of turnaround time/ no. of processes

= 76/4 = 19ms
Average waiting time = Sum waiting time/ no. of processes
= 50/4 = 12.5ms
3. Given below is the snapshot of processes. Draw Gantt charts using preemptive
and non preemptive priority scheduling algorithm. (A smaller number has a
higher priority) Also, calculate the average waiting time and turnaround time for
both.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 24

OPERATING SYSTEMS MODULE 2

4.
Process Arrival time Burst Time Priority
P1 0 6 4
P2 3 5 2

P3 3 3 6

P4 5 5 3

i.) The Gantt chart for the preemptive Priority schedule is as follows

Process Arrival Burst Time Priority Completion Turnaround Waiting

time Time time time
P1 0 6 4 16 16 10
P2 3 5 2 8 5 0

P3 3 3 6 19 16 13

P4 5 5 3 13 8 3

Average Turnaround time = Sum of turnaround time/ no. of processes

= 45/4 = 11.25ms
Average waiting time = Sum waiting time/ no. of processes
= 26/4 = 6.5ms
ii.) The Gantt chart for the Non-preemptive Priority schedule is as follows

Process Arrival Burst Priority Completion Turnaround Waiting

time Time Time time time
P1 0 6 4 6 6 0
P2 3 5 2 11 8 3

P3 3 3 6 19 16 13

P4 5 5 3 16 11 6

Average Turnaround time = Sum of turnaround time/ no. of processes

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 25
OPERATING SYSTEMS MODULE 2

= 41/4 = 10.25ms
Average waiting time = Sum waiting time/ no. of processes
= 22/4 = 5.5ms

5. Consider the following set of processes

Process Arrival time Burst Time Priority
P1 0 10 2
P2 2 5 1

P3 3 2 0

P4 5 20 3

Draw Gantt charts and calculate average waiting time, average turnaround time using
following CPU scheduling algorithm
i. Preemptive shortest job
ii. Non preemptive priority (0 = high priority)
i.)The Gantt chart for the preemptive shortest job schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 10 17 17 7
P2 2 5 9 7 2

P3 3 2 5 2 0

P4 5 20 37 32 12

Average Turnaround time = Sum of turnaround time/ no. of processes

= 58/4 = 14.5ms
Average waiting time = Sum waiting time/ no. of processes
= 21/4 = 5.25ms
ii.)The Gantt chart for the Non-preemptive priority (0 = high priority) schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 26

OPERATING SYSTEMS MODULE 2

Process Arrival Burst Time Priority Completion Turnaround Waiting

time Time time time
P1 0 10 2 10 10 0
P2 2 5 1 17 15 10

P3 3 2 0 12 9 7

P4 5 20 3 37 32 12

Average Turnaround time = Sum of turnaround time/ no. of processes

= 66/4 = 16.5ms
Average waiting time = Sum waiting time/ no. of processes
= 29/4 = 7.25ms

6. Consider the following set of processes

Process Arrival time Burst Time
P1 0 6
P2 2 3

P3 4 3

P4 5 5

Draw Gantt charts and calculate average waiting time, average turnaround time using
following CPU scheduling algorithm
i. FCFS
ii. SRTF
iii. RR (quantum = 1msec)
i.) The Gantt chart for the FCFS schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 27

OPERATING SYSTEMS MODULE 2

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 6 6 6 0
P2 2 3 9 7 4

P3 4 3 12 8 5

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes

= 33/4 = 8.25ms
Average waiting time = Sum waiting time/ no. of processes
= 16/4 = 4ms

ii.) The Gantt chart for the SRTF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 6 12 12 6
P2 2 3 5 3 0

P3 4 3 8 4 1

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes

= 31/4 = 7.75ms
Average waiting time = Sum waiting time/ no. of processes
= 14/4 = 3.5ms

iii.) The Gantt chart for the RR(time quantum = 1ms) schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 28

OPERATING SYSTEMS MODULE 2

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 6 14 14 8
P2 2 3 9 7 4

P3 4 3 13 9 6

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes

= 42/4 = 10.5ms
Average waiting time = Sum waiting time/ no. of processes
= 25/4 = 6.25ms

7. Consider the following set of processes

Process Burst time Priority
P1 10 3
P2 1 1

P3 2 3

P4 1 4

P5 5 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0. Draw
Gantt charts and calculate average waiting time, average turnaround time using following
CPU scheduling algorithm
i. FCFS
ii. SJF
iii. RR (quantum = 1msec)
i) The Gantt chart for the FCFS schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 29

OPERATING SYSTEMS MODULE 2

By considering arrival time = 0 for all processes.

Process Burst Time Completion Turnaround Waiting
Time time time
P1 10 10 10 0
P2 1 11 11 10

P3 2 13 13 11

P4 1 14 14 13

P5 5 19 19 14

Average Turnaround time = Sum of turnaround time/ no. of processes

= 67/5 = 13.4ms
Average waiting time = Sum waiting time/ no. of processes = 48/5 = 9.6ms

ii.) The Gantt chart for the SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 10 19 19 9
P2 0 1 1 1 0

P3 0 2 4 4 2

P4 0 1 2 2 1

P5 0 5 9 9 4

Average Turnaround time = Sum of turnaround time/ no. of processes

= 35/5 = 7ms
Average waiting time = Sum waiting time/ no. of processes
= 16/5 = 3.2ms
The Gantt chart for the RR(time quantum = 1ms) schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 30

OPERATING SYSTEMS MODULE 2

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P1 0 10 19 19 9
P2 0 1 2 2 1

P3 0 2 7 7 5

P4 0 1 4 4 3

P5 0 5 14 14 9

Average Turnaround time = Sum of turnaround time/ no. of processes

= 46/5 = 9.2ms
Average waiting time = Sum waiting time/ no. of processes
= 27/5 = 5.4ms

8. Consider the following set of processes

Process Arrival time Burst time Priority
P1 0 10 3
P2 0 1 1

P3 3 2 3

P4 5 1 4

P5 10 5 2

Draw Gantt charts and calculate average waiting time, average turnaround time using
preemptive priority scheduling algorithm. Assume highest priority = 1 and lowest priority =
4
The Gantt chart for the preemptive priority schedule is as follows:

Process Arrival Burst Time Priority Completion Turnaround Waiting

time Time time time
P1 0 10 3 11 11 1
P2 0 1 1 1 1 0

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 31

OPERATING SYSTEMS MODULE 2

P3 3 2 3 18 15 13

P4 5 1 4 19 14 13

P5 10 5 2 16 6 1

Average Turnaround time = Sum of turnaround time/ no. of processes = 47/5 = 9.4ms
Average waiting time = Sum waiting time/ no. of processes = 28/5 = 5.6ms

9. Consider the following set of processes

Process Arrival time Burst time
P0 0 6
P1 1 3

P2 2 1

P3 3 4

Draw Gantt charts and calculate average waiting time, average turnaround time using
SRTF and non preemptive SJF
i). The Gantt chart for the SRTF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P0 0 6 14 14 8
P1 1 3 5 4 1

P2 2 1 3 1 0

P3 3 4 9 6 2

Average Turnaround time = Sum of turnaround time/ no. of processes = 25/4 = 6.25ms
Average waiting time = Sum waiting time/ no. of processes = 11/4 = 2.75ms

ii). The Gantt chart for the non preemptive SJF schedule is as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 32

OPERATING SYSTEMS MODULE 2

Process Arrival Burst Time Completion Turnaround Waiting

time Time time time
P0 0 6 6 6 0
P1 1 3 10 9 6

P2 2 1 7 5 4

P3 3 4 14 11 7

Average Turnaround time = Sum of turnaround time/ no. of processes = 31/4 = 7.75ms
Average waiting time = Sum waiting time/ no. of processes = 17/4 = 4.25ms

SYNCHRONIZATION
What is synchronization?
Synchronization is the method which ensures the orderly execution of cooperating processes that
share logical address space (ie: code and data) or share data through files or messages through
threads so that data consistency is maintained.
The concurrent-access to shared-data may result in data-inconsistency. To maintain data-
consistency: the orderly execution of co-operating processes is necessary.
Suppose that we wanted to provide a solution to producer-consumer problem that fills
all full buffers. We can do so by having a variable counter that keeps track of the no. of
full buffers
Initially, counter=0.
 counter is incremented by the producer after it produces a new item to buffer.
 counter is decremented by the consumer after it consumes an item from buffer.
Shared-data:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 33

OPERATING SYSTEMS MODULE 2

Producer Process: Consumer Process:

What is Race condition?

In multiprogramming environment, a situation where several cooperative processes access
& manipulate same data (shared data) concurrently and the outcome of the execution
depends on particular order in which the access takes place, is called a race condition.
Example: In Producer-consumer process if the count ++ and count== is executed in the following
order, resulting in race condition.
counter++ could be implemented as: counter- - may be implemented as:

Consider this execution interleaving with counter = 5 initially: The value of counter may be either
4 or 6, where the correct result should be 5. This is an example for race condition. To prevent
race conditions, concurrent-processes must be synchronized.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 34

OPERATING SYSTEMS MODULE 2

CRITICAL-SECTION PROBLEM
What is critical section? Explain the requirements to be satisfied for critical section problem
Critical-section is a segment-of-code in which a process may be changing common (shared)
variables or updating a table or writing a file. Each process has a critical-section in which the
shared-data is accessed.
General structure of a typical process has following:
1) Entry-section

 Requests permission to enter the critical-section.

2) Critical-section

 Mutually exclusive in time i.e. no other process can execute in its critical-section.

3) Exit-section

 Follows the critical-section.

4) Remainder-section

General structure of a typical process

The 3 requirements to be satisfied for critical section problem is

[Link] Exclusion: If process Pi is executing in its critical section, then no other processes can
be executing in their critical sections.
[Link]: If no process is executing in its critical section and there exist some processes that
wish to enter their critical section, then the selection of the processes that will enter the critical
section next cannot be postponed indefinitely.
3. Bounded Waiting: There must be a bound on the number of times that other processes are
allowed to enter their critical-sections after a process has made a request to enter its critical-
section and before the request is granted.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 35

OPERATING SYSTEMS MODULE 2

PETERSON’S SOLUTION FOR CRITICAL SECTION PROBLEM

Illustrate with examples the Peterson’s solution for critical section problem and prove that
mutual exclusion property is preserved.

OR

Discuss an efficient algorithm which can meet all the requirements to solve the critical
section problem.

Peterson’s Solution is a classic software-based solution to the critical-section problem. This is

limited to 2 processes. The 2 processes alternate execution between critical-sections and
remainder-sections. The two processes share 2 variables:

Where variable turn indicates whose turn is to enter its critical-section. i.e., if turn== i, then
process Pi is allowed to execute in its critical-section. The flag array is used to indicate if a
process is ready (interested) to enter its critical-section. i.e. if flag[i]=true, then Pi is ready to enter
its critical-section.
while (true)
{
flag[i] = TRUE;
turn = j;
while ( flag[j] && turn == j);
CRITICAL SECTION
flag[i] = FALSE;
REMAINDER SECTION
}

The structure of process Pi in Peterson‘s solution

To prove Mutual exclusion property, let us consider two processes Pi = P0 and Pj = P1: we note
that process Pi (P0) enters its critical section only if either flag[j] = = flag[1]= = false or turn = = i
= 0 ( P1 is not interested or next turn to enter CS is P0)
If both processes can be executing in their critical sections at the same time, then flag[0] = =
flag[1] = = true.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 36

OPERATING SYSTEMS MODULE 2

These two observations imply that P0 and P1 could not have successfully executed their while
statements at about the same time, since the value of turn can be either 0 or 1 but cannot be both.
Hence one of the process say Pi (P0) must have successfully executed the while statement and
enters into critical section. Whereas Pj (P1) has to execute at least one additional statement turn =
= i (0). However, since at that time, falg[i] = flag[0] =true, and turn = = i (0), this condition(P 1 is
in trap state) will persist as long as P0 is in critical section. Thus Mutual Exclusion is preserved.
To prove Progress and bounded wait property, let us consider two processes Pi = P0 and Pj = P1

SYNCHRONIZATION HARDWARE (Hardware based Solution for Critical-section Problem)

Explain synchronization hardware.
Software based solution to critical section problem such as Peterson’s solution is not guaranteed
to work. We can protect critical regions via locks. Race conditions are prevented by acquiring
lock. Critical section problem could be solved simply in a uni-processor environment by disabling
interrupts. Disabling interrupt on a multiprocessor system is time consuming. Many modern
computer systems therefore provide a special hardware instructions that allow test and modify the
content of a word atomically. The instructions are TestAndSet() and swap()
Describe n-process solution to critical section problem which uses test and set() hardware
instruction. Prove how this algorithm satisfies all the requirements of critical section
problem’s solution.
A lock is a simple tool used to solve the critical-section problem. Race conditions are prevented
by following restriction. A process must acquire a lock before entering a critical-section. The
process releases the lock when it exits the critical-section.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 37

OPERATING SYSTEMS MODULE 2

TestAndSet( ): instruction is used to test & modify the content of a word atomically. An atomic-
operation is an operation that completes in its entirety without interruption.
The definition of TestAndSet( ) is:
boolean TestAndSet (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}

To prove Mutual Exclusion with TestAndSet() is as follows:

Initially shared boolean variable lock is initialized to false.
while (true)

while ( TestAndSet (&lock )) ; // entry section code

Critical Section

lock = FALSE; //exit section code

// remainder section
}
Suppose P0 is the process interested to enter CS. Initially lock =false, so that while(TestAndSet
(&lock )) statement results in false. P0 enters CS. When P0 is inside CS, P1 attempts to enter CS,
but P1 is blocked in the entry section of CS itself, since the value of lock = true.
SWAP( )
Definition of Swap( ) is as follows:
void swap (boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp:
}
This instruction is executed atomically. If the machine supports the Swap(), then mutual-

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 38

OPERATING SYSTEMS MODULE 2

exclusion can be provided as follows:

1) A global boolean variable lock is declared and is initialized to false.

2) In addition, each process has a local Boolean variable key

To prove Mutual Exclusion with Swap() is as follows

Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable
key.
while (true)
{
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );
Critical Section
lock = FALSE;
Remainder section
}
SEMAPHORES
• The hardware solution to the critical section problem is complicated for application
programmers to use
• To overcome this difficulty we use synchronization tool called semaphore
• Semaphore S – integer variable apart from initialization it can be accessed and modified
only by two operations wait() and signal()
What are semaphores?List any 3 application of semaphores
Semaphore is an integer variable, which is used in mutual exclusive manner by various concurrent
cooperative processes in order to achieve synchronization.
Apart from semaphores initialization it can be accessed and modified only by two operations
wait() and signal().
Application of Semaphore
1. Semaphore is used to solve critical section problem
2. Semaphore is used to decide the order of execution among the processes.(synchronization)
3. Resource management

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 39

OPERATING SYSTEMS MODULE 2

Definition of wait() and signal()

wait (S)
{
while (S <= 0); // no-op
S--;
}
signal (S)
{
S++;
}
TYPES OF SEMAPHORES
Explain binary and counting semaphores with examples.
1. Counting semaphore
2. Binary semaphore

Explain the usage of semaphores.

Counting Semaphore
Explain how semaphore is used to handle resource management.
Handling Resource management
It is mainly used in resource management. The value of a counting semaphore can range over an
unrestricted domain. Counting semaphores can be used to control access to a given resource
consisting of finite number of instances. The semaphore is initialized to the number of resources
available. Each process that wishes to use a resource performs a wait() operation on the
semaphore (thereby decrementing the count). When a process releases a resource, it performs a
signal() operation (incrementing the count). When the count for the semaphore goes to 0, all
resources are being used. After that, processes that wish to use a resource will block until the
count becomes greater than 0.
Binary Semaphore
The value of a semaphore can range only between 0 and 1.
On some systems, binary semaphores are known as mutex locks, as they are locks that provide
mutual-exclusion

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 40

OPERATING SYSTEMS MODULE 2

Solving Critical-section Problem using Binary Semaphores

Explain how semaphore is used to solve critical section problem
Binary semaphores can be used to solve the critical-section problem for multiple processes.

Mutual-exclusion implementation with semaphores

The ‘n’ processes share semaphore Mutex which is initialized to 1
Explanation: Whichever the process interested to enter critical section, say P 1 must execute the
wait (mutex) at its entry section. Mutex is decremented by 1, if its value is > 0 and process P 1
enters into CS. Now the Mutex value = 0. When P1 is inside the CS, if P2 attempts to enter CS by
executing wait (mutex). Since the mutex value is 0, the while (mutex<=0) statement results in true
and blocks process P1 in entry section. Thus the mutual exclusion property is ensured.
Explain how semaphore is used to solve synchronization problem
Solving Synchronization Problems
Semaphores can also be used to solve synchronization problems.
For example, consider 2 concurrently running-processes: P1 with a statement S1 and P2 with a
statement S2. Suppose we require that S2 be executed only after S1 has completed. We can
implement this scheme readily by letting P1 and P2 to share a common semaphore synch
initialized to 0, and by inserting the following statements in process P 1
S1 :
signal(synch)
and the following statements in process P2
wait(synch)
S2 ;
Since synch is initialized to 0, P2 will execute S2 only after P1 has invoked signal (synch), which
is after statement S1 has been executed.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 41

OPERATING SYSTEMS MODULE 2

Advantages of semaphore
What are the advantages of semaphore?
1. Semaphores allow only one process into the critical section.
2. Semaphores follow mutual exclusion principle strictly.
3. Semaphores are much more efficient than some other methods of synchronization
SEMAPHOREIMPLEMENTATION
The main disadvantage of semaphore is Busy waiting.
What is busy waiting in critical section concept?
OR
What is spinlock?
While a process is in its critical-section, any other process that tries to enter its critical-
section must loop continuously in the entry-code, and this situation in critical section
problem is called busy waiting.
Busy waiting wastes CPU cycles that some other process might be able to useproductively.
This type of semaphore is also called a spinlock (because the process "spins" while waiting
for the lock).
IMPLEMENTATION OF SEMAPHORE
Explain implementation of semaphore
To overcome busy waiting, we can modify the definition of the wait() and signal() as follows:
When a process executes the wait() and finds that the semaphore-value is not positive, it must
wait. However, rather than engaging in busy waiting, the process can blockitself.
A process that is blocked (waiting on a semaphore S) should be restarted when someother process
executes a signal(). The process is restarted by awakeup().
We assume 2 simple operations:
1) block() suspends the process that invokes it.

2) wakeup(P) resumes the execution of a blocked process P.

We define a semaphore as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 42

OPERATING SYSTEMS MODULE 2

Implementation of wait( )
wait (S)
{
value--;
if (value <0)
{
add this process to waiting queue
block();
}
}
Implementation of signal( )
signal(S)
{
value++;
if (value <=0)
{
Remove a process P from the waiting queue
wakeup(P);
}
}

NOTE:
The (critical-section) problem can be solved in two ways:
1) In a uni-processor environment

¤ Inhibit interrupts when the wait and signal operations execute.

¤ Only current process executes, until interrupts are re-enabled & the
scheduler regains control.
2) In a multi-processor environment

¤ Inhibiting interrupts doesn't work.

¤ Use the hardware / software solutions described above.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 43

OPERATING SYSTEMS MODULE 2

DEADLOCKS & STARVATION

Deadlock occurs when 2 or more processes are waiting indefinitely for an event that can be
caused by only one of the waiting processes. The event in question is the execution of a signal()
operation.
To illustrate this, consider 2 processes, Po and P1, each accessing 2 semaphores, S and Q. Let S
and Q be initialized to1.

Suppose that Po executes wait(S) and then P1 executes wait(Q). When Po executes wait(Q), it
must wait until P1 executes signal(Q). Similarly, when P1 executes wait(S), it must wait until Po
executes signal(S). Since these signal() operations cannot be executed, Po & P1 are deadlocked.
Starvation (indefinite blocking) is another problem related to deadlocks.
Starvation is a situation in which processes wait indefinitely within the semaphore. Indefinite
blocking may occur if we remove processes from the list associated with a semaphore in LIFO
(last-in, first-out)order.

CLASSIC PROBLEMS OF SYNCHRONIZATION

Here we discuss a number of synchronization problems as examples of a large class of
concurrency control problems. These problems are used for testing nearly every newly proposed
synchronization scheme.
1. Bounded-Buffer Problem
2. Readers and Writers Problem
3. Dining-Philosophers Problem

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 44

OPERATING SYSTEMS MODULE 2

BOUNDED-BUFFER PROBLEM
Give a solution to the bounded buffer problem using semaphores. Write the structure of
producer and consumer processes
The bounded-buffer problem is related to the producer consumer problem. There is a pool of n
buffers, each capable of holding one item.
Shared data:

 The mutex semaphores provide mutual exclusion for access to the buffer pool and is
initialized to the value 1
 empty and full semaphores are used to count the number of empty and full items in buffer
respectively.
 Initially empty = n; full=0
The symmetry between the producer and the consumer is ensured by the producer producing full
items in buffers for the consumer and the consumer produces empty buffers for the producer.
The structure of the producer process
while (true)
{
// produce an item
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
}
The structure of the consumer process
while (true)
{
wait (full);
wait (mutex);
// remove an item from buffer
signal (mutex);

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 45

OPERATING SYSTEMS MODULE 2

signal (empty);
// consume the removed item
}

READERS WRITERS PROBLEM

*****Explain Readers Writers problem with solution provided by semaphore
In cooperative process a data set is shared among a number of concurrent processes. In readers
arbiters problem:
 Readers are the processes which want to only read the database (DB).
 Writers are the processes which want to update (i.e. to read & write) the DB.

The actual problem in Readers Writers problem is, if 2 readers can access the shared-DB
simultaneously without any problems. However, if a writer & other process (either a reader or a
writer) access the shared-DB simultaneously, problems may arise.
Solution: The writers must have exclusive access to the shared-DB while writing to the DB.

Shared-data

Where,
 mutex is used to ensure mutual-exclusion when the variable readcount is updated.
 wrt is common to both reader and writer processes.
 wrt is used as a mutual-exclusion semaphore for the writers. Also wrt is used by the
first/last reader that enters/exits the critical-section.
 readcount counts the number of processes currently reading the object.

Initialization
mutex = 1, wrt = 1, readcount = 0
The structure of a writer process
while (true)
{
wait (wrt) ;

// writing is performed
signal (wrt) ;
}
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 46
OPERATING SYSTEMS MODULE 2

The structure of a reader process

while (true)
{
wait (mutex) ;
readcount ++ ;
if (readcount == 1) then wait (wrt) ;
signal (mutex)
// reading is performed
wait (mutex) ;
readcount - - ;
if (readcount == 0) then signal (wrt) ;
signal (mutex) ;
}

THE DINING-PHILOSOPHERS PROBLEM

Explain Dining Philosophers problem with solution provided by semaphore.
Problem statement:
 There are 5 philosophers with 5 chopsticks (semaphores).

 A philosopher is either eating (with two chopsticks) or thinking.

 The philosophers share a circular table as shown below

 The table has a bowl of rice in the center and 5 single chopsticks.

 From time to time, a philosopher gets hungry and tries to pick up the 2

chopsticks that are closest to them.

 A philosopher may pick up only one chopstick at a time.

 Obviously, one cannot pick up a chopstick that is already in the hand of a neighbor

philosopher.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 47

OPERATING SYSTEMS MODULE 2

 When hungry philosopher has both her chopsticks at the same time, she eats

without releasing her chopsticks.

 When she is finished eating, she puts down both of her chopsticks and starts thinking

again.
Problem objective: To allocate several resources among several processes in a deadlock-free &
starvation-free manner.
Solution using semaphore:
 Represent each chopstick with a semaphore; chopstick[5]

 A philosopher tries to grab a chopstick by executing a wait( ) on the semaphore.

 The philosopher releases her chopsticks by executing the signal( ) on the semaphores.

 This solution guarantees that no two neighbors are eating simultaneously.

Shared-data:
semaphore chopstick[5];

Initialization
chopstick[5]={1,1,1,1,1}

The structure of Dining- Philosopher i with semaphore solution:

do
{
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );
// eat
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
}
while (TRUE);
Disadvantage of Dining Philosopher problem with semaphore:
Deadlock may occur if all 5 philosophers become hungry simultaneously and grab their
left chopstick. When each philosopher tries to grab her right chopstick, she will be
delayed forever.
Three possible remedies to the deadlock problem:
1) Allow at most 4 philosophers to be sitting simultaneously at the table.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 48

OPERATING SYSTEMS MODULE 2

2) Allow a philosopher to pick up her chopsticks only if both chopsticks are available.

3) Use an asymmetric solution; i.e. an odd philosopher picks up first her left

chopstick and then her right chopstick, whereas an even philosopher picks up her
right chopstick and then her left chopstick.

MONITORS
Need for Monitors
When programmers use semaphores incorrectly, following types of errors may occur:
1. Suppose that a process interchanges the order in which the wait() and signal() operations on the
semaphore mutex are executed, resulting in the following execution:

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

simultaneously, violating the mutual-exclusion requirement.
2. Suppose that a process replaces signal(mutex) with wait(mutex). That is, it executes

In this case, a deadlock will occur.

3. Suppose that a process omits the wait(mutex), or the signal(mutex), or both.
In this case, either mutual-exclusion is violated or a deadlock will occur.
Monitor is a high-level synchronization construct. It provides a convenient and effective
mechanism for process synchronization.
What are Monitors? Explain its uasage and implementation
A monitor is a module that encapsulates shared data structures, procedures that operate on shared
data, synchronization between concurrent procedure invocation and conditional variable.
Monitors Usage
Explain the syntax and schematic view of monitors
A monitor type presents a set of programmer-defined operations that are provided to
ensure mutual-exclusion within the monitor.
It also contains declaration of variables, bodies of procedures (or functions). A procedure defined
within a monitor can access only those variables declared locally within the monitor and its
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 49
OPERATING SYSTEMS MODULE 2

formal-parameters. Similarly, the local-variables of a monitor can be accessed by only the local-
procedures.

Syntax view of monitor

Only one process at a time is active within the monitor. To allow a process to wait within the
monitor, a condition variable must be declared, as

Schematic view of Monitor Monitor with condition variable

Condition variable can only be used with the following 2 operations:
[Link](): This operation resumes exactly one suspended process. If no process is
suspended, then the signal operation has no effect.
[Link](): The process invoking this operation is suspended until another process invokes
[Link]().
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 50
OPERATING SYSTEMS MODULE 2

Example:
Suppose when the [Link]() operation is invoked by a process P, there exists a suspended
process Q associated with condition x. Both processes can conceptually continue with
their execution. Two possibilities exist:
1) Signal and wait

P either waits until Q leaves the monitor or waits for other condition.
2) Signal and continue

Q either waits until P leaves the monitor or waits for other condition

DINING-PHILOSOPHERS SOLUTION USING MONITORS

Describe the monitor solution to the classical dining philosopher problem.

The restriction is a philosopher may pick up her chopsticks only if both of them are available.

A monitor solution to the dining-philosopher problem

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 51

OPERATING SYSTEMS MODULE 2

Description of the solution:

1. Philosopher may pick up her chopsticks only when both of them are available
2. Three states thinking, hungry and eating
3. Philosopher i can set the variable state[i]=EATING only when (state[i+4]%5 !=EATING)
&& (state[i+1]%5 !=EATING)
4. Condition self[5] in which philosopher can delay herself when she is hungry but is unable
to obtain chopsticks she needs
5. The distribution of the chopsticks is controlled by the monitor dp as shown above
6. Each philosopher, before starting to eat, must invoke the operation pickup().
This act may result in the suspension of the philosopher process.
7. After the successful completion of the operation, the philosopher may eat.
8. Following this, the philosopher invokes the putdown() operation.
9. Thus, philosopher i must invoke the operations pickup() and putdown() in the
sequence as given in code.
IMPLEMENTING A MONITOR USING SEMAPHORES
A process must execute wait(mutex) before entering the monitor and must execute signal(mutex)
after leaving the monitor.
Variables used:
Semaphore mutex; // (initially = 1)
Semaphore next; // (initially = 0)
int next-count =0;
where
 mutex is provided for each monitor.
 next is used a signaling process to wait until the resumed process either leaves or waits
 next-count is used to count the number of processes suspended
Each external procedure F is replaced by

Mutual-exclusion within a monitor is ensured.

How condition variables are implemented?

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 52

OPERATING SYSTEMS MODULE 2

Definition of [Link]() Definition of [Link]()

Resuming Processes within a Monitor

• If several processes queued on condition x, and [Link]() executed, which should be
resumed?
• FCFS frequently not adequate
• conditional-wait construct of the form [Link](c)
– Where c is priority number
– Process with lowest number (highest priority) is scheduled next

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 53

 MODULE 3

Deadlocks: Deadlocks; System model; deadlock characterization; methods for handling deadlocks;

Deadlock prevention; Deadlock avoidance; Deadlock detection and recovery from deadlock.

Memory management: Memory Management strategies: background; Swapping; Contiguous memory

allocation; Paging; Structure of page table; Segmentation

OPERATING SYSTEMS MODULE 3

DEADLOCKS
DEADLOCK
Define deadlock.
Deadlock is a situation where a set of processes are blocked because each process is holding a
resource and waiting for another resource held by some other process.

Real life example:

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

SYSTEM MODEL
A system consists of finite number of resources. (For ex: memory, printers, CPUs). These
resources are distributed among number of processes. A process must request a resource before
using it and release the resource after using it. The process can request any number of resources to
carry out a given task. The total number of resource requested must not exceed the total number of
resources available.
In normal operation, a process must perform following tasks in sequence:
1. Request
If the request cannot be granted immediately (for ex: the resource is being used by
another process), then the requesting-process must wait for acquiring the resource.
For example: open( ), malloc( ), new( ), and request( )
2. Use
The process uses the resource. For example: prints to the printer or reads from the file.
3. Release
The process releases the resource. So that, the resource becomes available for other processes.
For example: close( ), free( ), delete( ), and release( ).
A set of processes is deadlocked when every process in the set is waiting for a resource
that is currently allocated to another process in the set. Deadlock may involve different
types of resources.
As shown in below figure , Both processes P1 & P2 need resources to continue execution.
P1 requires additional resource R1and is in possession of resource R2. P2 requires
additional resource R2 and is in possession of R1. Thus, neither process can continue.
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 1
OPERATING SYSTEMS MODULE 3

Multithread programs are good candidates for deadlock because they compete for shared
resources.

DEADLOCK CHARACTERIZATION
In a deadlock, processes never finish executing, and system resources are tied up, preventing other
jobs from starting.

NECESSARY CONDITIONS

**********What are the necessary conditions for deadlock? OR

***********What are the characteristics of deadlock?
There are four conditions that are necessary to achieve deadlock:
1. Mutual Exclusion
 Only one process at a time can use a resource.
 At least one resource must be held in a non-sharable mode.
 If any other process requests this resource, then the requesting-process must
wait for the resource to be released.
2. Hold and Wait
A process must be simultaneously holding at least one resource and waiting to acquire additional
resources held by the other process.
3. No Preemption
Once a process is holding a resource ( i.e. once its request has been granted ), then that
resource cannot be taken away from that process until the process voluntarily releases it.
4. Circular Wait
A set of processes {P0, P1, P2, . . ., PN } must exist such that P0 is waiting for a resource that is held
by P1. P1 is waiting for a resource that is held by P 2. Pn–1 is waiting for a resource that is held by
Pn, and Pn is waiting for a resource that is held by P0.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 2

OPERATING SYSTEMS MODULE 3

RESOURCE-ALLOCATION-GRAPH (RAG)

The resource-allocation-graph (RAG) is a directed graph that can be used to describe the
deadlock situation.
RAG consists of a
i. Set of vertices (V) and
ii. Set of edges (E).
V is divided into two types of nodes
1) Process vertex or node; P={P1,P2……..Pn} i.e., set consisting of all active processes
in the system.
2) Resource vertex or node; R={R1,R2……….Rn} i.e., set consisting of all resource
types in the system.
E is divided into two types of edges:
1) Request Edge

 A directed-edge Pi → Rj is called a request edge.

 Pi → Rj indicates that process Pi has requested a resource Rj.

2) Assignment Edge

 A directed-edge Rj → Pi is called an assignment edge.

 Rj → Pi indicates that a resource Rj has been allocated to process Pi.

NOTE:
Suppose that process Pi requests resource Rj.; Here, the request for Rj from Pi can be granted only
if the converting request-edge to assignment-edge do not form a cycle in the resource-allocation
graph.
Pictorially, we represent each process Pi as a circle. We represent each resource-type Rj as a
rectangle.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 3

OPERATING SYSTEMS MODULE 3

As shown in below figures, the RAG illustrates the following 3 situation

Describe RAG i) With deadlock ii) With a cycle but no deadlock
1) RAG with a deadlock

2) RAG with a cycle and deadlock

3) RAG with a cycle but no deadlock

1.) RAG with a deadlock 2). With a cycle and deadlock 3). With cycle but no deadlock

CONCLUSION:
1) If a graph contains no cycles, then the system is not deadlocked.

2) If the graph contains a cycle and if only one instance per resource type is used, then

deadlock will occur.

3) If the graph contains a cycle and if several instances per resource type is used, then

there is a possibility of deadlock but not necessarily present

METHODS FOR HANDLING DEADLOCKS

***Briefly explain the methods for handling deadlock
There are three ways of handling deadlocks:
1. Deadlock prevention or Avoidance: Do not allow the system to get into a deadlocked state. In
order to prevent deadlocks, use set of methods for ensuring that at least one of the necessary
conditions for deadlock cannot hold. In order to avoid deadlocks, the system must have additional
information about all processes, such that which resources a process will request and use during
its lifetime. With this additional knowledge, it can decide for each request whether or not the
process should wait.
2. Deadlock detection and recovery: Abort a process or preempt some resources when
deadlocks are detected. Deadlock detection is fairly straightforward, but deadlock
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 4
OPERATING SYSTEMS MODULE 3

recovery requires either aborting processes or preempting resources.

3. Ignore the problem all together and pretend that deadlocks never occur in the system:
This solution is used by most operating system

DEADLOCK-PREVENTION

How can deadlock be prevented? Describe any three of them.

Deadlocks can be eliminated by preventing (making False) at least one of the four required
conditions:
1) Mutual exclusion

2) Hold-and-wait

3) No preemption

4) Circular-wait.
Mutual Exclusion

 This condition must hold for non-sharable resources. For example: A printer cannot be
simultaneously shared by several processes.
 On the other hand, shared resources do not lead to deadlocks. For example: Simultaneous
access can be granted for read-only file.
 A process never waits for accessing a sharable resource.
 In general, we cannot prevent deadlocks by denying the mutual-exclusion
condition because some resources are non-sharable by default.
Hold and Wait:
To prevent this condition it must be ensure that, whenever a process requests a resource, it does
not hold any other resources.
There are several solutions to this problem.
 Each process must be allocated with all of its resources before it begins execution
 A process must request a resource only when the process has none allocated to it. A
process may request some resources and use them. Before it can request any additional
resources, however, it must release all the resources that it is currently allocated
No Preemption
To prevent this condition the resources must be preempted.
There are several solutions to this problem.
 If a process is holding some resources and requests another resource that cannot be
immediately allocated to it, then all resources currently being held are preempted.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 5

OPERATING SYSTEMS MODULE 3

 The preempted resources are added to the list of resources for which the process is
waiting.
 The process will be restarted only when it regains the old resources and the new
resources that it is requesting.
 When a process request resources, we check whether they are available or not. If they are
available allocate them, if they are not check whether they are available with process
waiting for additional resource if so preempt desired resources from the waiting process.
Circular-Wait
 To ensure that this condition never holds is to impose a total ordering of all resource types
by assigning numbers to all resources, and require that each process requests resources in
an increasing/decreasing order of enumeration.
 Require that whenever a process requests a resource, it has released resources
with a lower number.
 One big challenge in this scheme is determining the relative ordering of the different
resources.

DEADLOCK AVOIDANCE
The general idea behind deadlock avoidance is to prevent deadlocks from ever happening.
Deadlocks are requiring additional information about how resources are to be requested.
Deadlock-avoidance algorithm
 Requires more information about each process, and
 Tends to lead to low device utilization.
For example:
1) In simple algorithms, the scheduler only needs to know the maximum number

of each resource that a process might potentially use.

2) In complex algorithms, the scheduler can also take advantage of the schedule

of exactly what resources may be needed in what order.

A deadlock-avoidance algorithm dynamically examines the resources allocation state to
ensure that a circular-wait condition never exists. The resource-allocation state is defined
by the number of available and allocated resources and the maximum demand of each
process.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 6

OPERATING SYSTEMS MODULE 3

SAFE STATE

A state is safe if the system can allocate all resources requested by all processes without entering
a deadlock state.
A state is safe if there exists a safe sequence of processes {P0, P1, P2, ..., PN} such that the requests
of each process(Pi) can be satisfied by the currently available resources.
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.

Safe, Unsafe and Deadlock state spaces

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 7

OPERATING SYSTEMS MODULE 3

DEADLOCK AVOIDANCE USING RESOURCE ALLOCATION GRAPH ALGORITHM

If resource categories have only single instances of their resources, then deadlock states can be
detected by cycles in the resource-allocation graphs.
In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation
graph with claim edges (denoted by a dashed line).
Claim edge Pi → Rj indicated that process Pi may request resource Rj at some time in future.
The important steps are as below:
1. When a process Pi requests a resource Rj, the claim edge P i → Rj is converted to a request
edge.
2. Similarly, when a resource Rj is released by the process Pi, the assignment edge Rj → Pi is
reconverted as claim edge Pi → Rj.
3. The request for Rj from Pi can be granted only if the converting request edge to assignment
edge do not form a cycle in the resource allocation graph.
To apply this algorithm, each process Pi must know all its claims before it starts executing.
Conclusion:
 If no cycle exists, then the allocation of the resource will leave the system in a safe state.
 If cycle is found, system is put into unsafe state and may cause a deadlock.
For example: Consider a resource allocation graph shown in Figure below

Suppose P2 requests R2. Though R2 is currently free, we cannot allocate it to P 2 as this action will
create a cycle in the graph as shown in below Figure. This cycle will indicate that the system is in
unsafe state: because, if P1 requests R2 and P2 requests R1 later, a deadlock will occur.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 8

OPERATING SYSTEMS MODULE 3

Unsafe State In Resource-Allocation Graph

Problem:
The resource-allocation graph algorithm is not applicable when there are multiple instances for
each resource.
Solution: Use banker's algorithm.
BANKERS ALGORITHM
This algorithm is applicable to the system with multiple instances of each resource types.
However, this algorithm is less efficient then the resource-allocation-graph algorithm. When a
process starts up, it must declare the maximum number of resources that it may need. This number
may not exceed the total number of resources in the system. When a request is made, the system
determines whether granting the request would leave the system in a safe state.
If the system in a safe state, then the resources are allocated;
else the process must wait until some other process releases enough resources.
Assumptions: Let n = number of processes in the system Let m = number of resources types.
Following data structures are used to implement the banker’s algorithm.
Explain the data structures used in Bankers algorithm.
Available [m]
 This vector indicates the no. of available resources of each type.

 If Available[j]=k, then k instances of resource type Rj is available.

Max [n][m]
 This matrix indicates the maximum demand of each process of each resource.

 If Max[i,j]=k, then process Pi may request at most k instances of resource type Rj.

Allocation [n][m]
 This matrix indicates no. of resources currently allocated to each process.

 If Allocation[i,j]=k, then Pi is currently allocated k instances of Rj.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 9

OPERATING SYSTEMS MODULE 3

Need [n][m]
 This matrix indicates the remaining resources need of each process.

 If Need[i,j]=k, then Pi may need k more instances of resource Rj to complete its task.

 So, Need[i,j] = Max[i,j] - Allocation[i]

Write and explain Bankers algorithm. (explain both safety and Resource request algorithm)
This algorithm is applicable to the system with multiple instances of each resource types.
When a process starts up, it must declare the maximum number of resources that it may need. This
number may not exceed the total number of resources in the system. When a request is made, the
system determines whether granting the request would leave the system in a safe state.
If the system in a safe state, then the resources are allocated;
else the process must wait until some other process releases enough resources.
Assumptions: Let n = number of processes in the system Let m = number of resources types.
Following data structures are used to implement the banker’s algorithm
Available [m], Max [n][m], Allocation [n][m], Need [n][m]
The Banker’s algorithm has two parts: 1) Safety Algorithm
2) Resource – Request Algorithm
Safety Algorithm
Step 1:
Let Work and Finish be two vectors of length m and n respectively.
Initialize:
Work = Available
Finish[i] = false for i=1,2,3,…….n
Step 2:
Find an index(i) such that both
a) Finish[i] = false

b) Need i <= Work.

If no such i exist, then go to step 4

Step 3:
Set:
Work = Work + Allocation(i)
Finish[i] = true
Go to step 2
Step 4:
If Finish[i] = true for all i, then the system is in safe state.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 10

OPERATING SYSTEMS MODULE 3

Resource-Request Algorithm

****Explain Resource Request Algorithm

This algorithm determines if a new request is safe, and grants it only if it is safe to do so. When a
request is made ( that does not exceed currently available resources ), pretend it has been granted,
and then see if the resulting state is a safe one. If so, grant the request, and if not, deny the request.
Let Requesti be the request vector of process Pi.
If Requesti [j]=k, then process Pi wants k instances of the resource type Rj.
Step 1:
If Requesti <= Needi then go to step 2
else
Raise an error condition, since the process has exceeded its maximum claim.
Step 2:
If Requesti <= Available then go to step 3
else
Pi must wait, since the resources are not available.
Step 3:
If the system wants to allocate the requested resources to process Pi then modify
the state as follows:
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi – Requesti
Step 4:
If the resulting resource-allocation state is safe, then
i) transaction is complete and
ii) Pi is allocated its resources.
Step 5:
If the new state is unsafe,then
i) Pi must wait for Request i and
ii) Old resource-allocation state is restored.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 11

OPERATING SYSTEMS MODULE 3

An Illustrative Example

1. Consider the following snapshot of a system:

Allocation Max Available

A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 3 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

Answer the following questions using Banker's algorithm.

i) What is the content of the matrix need?

ii) Is the system in a safe state?

iii) If a request from process P1 arrives for (1, 0, 2) can the request be granted

immediately?
Solution:
The content of the matrix Need is given by Need = Max - Allocation
So, the content of Need Matrix is:
Need
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1

Applying the Safety algorithm on the given system:

Step 1: Initialization
Work = Available ie: Work = 3 3 2

Process P0 P1 P2 P3 P4

Finish False False False False False

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 12

OPERATING SYSTEMS MODULE 3

Step 2: For i= 0
Finish [P0] = false and Need [P0] <= Work i.e. (7 4 3) <= (3 3 2) ie: false So P0 must wait.
Step 2: For i=1
Finish [P1] = false and Need [P1] <= Work i.e. (1 2 2) <= (3 3 2) ie: True, So P1 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P1] = (3 3 2) + (2 0 0) = (5 3 2)

Process P0 P1 P2 P3 P4

Finish False True False False False

Step 2: For i=2

Finish[P2] = false and Need[P2] <= Work i.e. (6 0 0) <= (5 3 2) ie: false, So P2 must wait.
Step 2: For i=3
Finish[P3] = false and Need[P3] <= Work i.e. (0 1 1) <= (5 3 2) ie: True, So P3 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P3] = (5 3 2) + (2 1 1) = (7 4 3)

Process P0 P1 P2 P3 P4

Finish False True False True False

Step 2: For i=4

Finish[P4] = false and Need[P4] <= Work i.e. (4 3 1) <= (7 4 3) ie: True, So P4 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P4] = (7 4 3) + (0 0 2) = (7 4 5)

Process P0 P1 P2 P3 P4

Finish False True False True True

Step 2: For i=0

Finish[P0] = false and Need[P0] <= Work i.e. (7 4 3) <= (7 4 5) ie: True, So P0 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P0] = (7 4 5) + (0 1 0) = (7 5 5)

Process P0 P1 P2 P3 P4

Finish True True False True True

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 13

OPERATING SYSTEMS MODULE 3

Step 2: For i=2

Finish[P2] = false and Need[P2] <= Work i.e. (6 0 0) <= (7 5 5) ie: True, So P2 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P2] = (7 5 5) + (3 0 2) = (10, 5 7)

Process P0 P1 P2 P3 P4

Finish True True True True True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P1, P3, P4, P0, P2>.
ii) Conclusion: Yes, the system is currently in a safe state.

Solution (iii): P1 requests (1 0 2) i.e. Request [P1] = (1 0 2)

To decide whether the request is granted, we use Resource Request algorithm.
Step 1: Request[P1] <= Need[P1] i.e. (1 0 2) <= (1 2 2) ie: true.
Step 2: Request[P1] <=Available (at time t0, when system snapshot is taken)
i.e. (1 0 2) <= (3 3 2) ie: true.
Step 3: Available = Available – Request [P1] = (3 3 2) - (1 0 2) = (2 3 0)
Allocation[P1] = Allocation[P1] + Request[P1] = (2 0 0) + (1 0 2)= (3 0 2)
Need[P1] = Need[P1] – Request[P1] = (1 2 2) - (1 0 2)= (0 2 0)

We arrive at the following new system state:

Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 2 3 0
P1 3 0 2 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

The content of the matrix Need is given by Need = Max - Allocation

So, the content of Need Matrix is:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 14

OPERATING SYSTEMS MODULE 3

Need
A B C
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
To determine whether this new system state is safe, we again execute Safety algorithm.
Step 1: Initialization
Work = Available ie: Work = 2 3 0

Process P0 P1 P2 P3 P4

Finish False False False False False

Step 2: For i= 0
Finish [P0] = false and Need [P0] <= Work i.e. (7 4 3) <= (2 3 0) ie: false So P0 must wait.
Step 2: For i=1
Finish [P1] = false and Need [P1] <= Work i.e. (0 2 0) <= (2 3 0) ie: True, So P1 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P1] = (2 3 0) + (3 0 2) = (5 3 2)

Process P0 P1 P2 P3 P4

Finish False True False False False

Step 2: For i= 2
Finish [P2] = false and Need [P2] <= Work i.e. (6 0 0) <= (5 3 2) ie: false So P2 must wait.
Step 2: For i=3
Finish [P3] = false and Need [P3] <= Work i.e. (0 1 1) <= (5 3 2) ie: True, So P3 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P3] = (5 3 2) + (2 1 1) = (7 4 3)

Process P0 P1 P2 P3 P4

Finish False True False True False

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 15

OPERATING SYSTEMS MODULE 3

Step 2: For i=4

Finish [P4] = false and Need [P4] <= Work i.e. (4 3 1) <= (7 4 3) ie: True, So P4 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P4] = (7 4 3) + (0 0 2) = (7 4 5)

Process P0 P1 P2 P3 P4

Finish False True False True True

Step 2: For i =0
Finish [P0] = false and Need [P0] <= Work i.e. (7 4 3) <= (7 4 5) ie: True, So P0 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P0] = (7 4 5) + (0 1 0) = (7 5 5)

Process P0 P1 P2 P3 P4

Finish True True False True True

Step 2: For i =2
Finish [P2] = false and Need [P2] <= Work i.e. (6 0 0) <= (7 5 5) ie: True, So P2 must be kept in
safe sequence.
Step 3: Work = Work + Allocation [P2] = (7 5 5) + (3 0 2) = (10, 5, 7)

Process P0 P1 P2 P3 P4

Finish True True True True True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P1, P3, P4, P0, P2>.
Conclusion: Since the system is in safe sate, the request can be granted.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 16

OPERATING SYSTEMS MODULE 3

[Link] the following snapshot of a system:

Allocation Max Available
A B C A B C A B C
P0 0 0 2 0 0 4 1 0 2
P1 1 0 0 2 0 1
P2 1 3 5 1 3 7
P3 6 3 2 8 4 2
P4 1 4 3 1 5 7
Answer the following questions using Banker's algorithm.
i) What is the content of the matrix need?

ii) Is the system in a safe state?

iii) If a request from process P2 arrives for (0, 0, 2) can the request be granted

immediately?
Solution:
i) The content of the matrix Need is given by Need = Max - Allocation
So, the content of Need Matrix is:
Need
A B C
P0 0 0 2
P1 1 0 1
P2 0 0 2
P3 2 1 0
P4 0 1 4

ii) Applying the Safety algorithm on the given system:

Step 1: Initialization
Work = Available ie: Work = (1 0 2)

Process P0 P1 P2 P3 P4

Finish False False False False False

Step 2: For i=0

Need[P0] <= work ie: (0 0 2) <= (1 0 2) ie: True, So P0 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P0] = (1 0 2) + (0 0 2) = (1 0 4)

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 17

OPERATING SYSTEMS MODULE 3

Set Finish[P0] = True

Step 2: For i=1

Need[P1] <= work ie: (1 0 1) <= (1 0 4) ie: True, So P1 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P1] = (1 0 4) + (1 0 0) = (2 0 4)

Set Finish[P1] = True

Step 2: For i=2

Need[P2] <= work ie: (0 0 2) <= (2 0 4) ie: True, So P2 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P2] = (2 0 4) + (1 3 5) = (3 3 9)

Set Finish[P2] = True

Step 2: For i=3

Need[P3] <= work ie: (2 1 0) <= (3 3 9) ie: True, So P3 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P3] = (3 3 9) + (6 3 2) = (9, 6, 11)

Set Finish[P3] = True

Step 2: For i=4

Need[P4] <= work ie: (0 1 4) <= (9, 6, 11) ie: True, So P4 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P4] = (9, 6, 11) + (1 4 3) = (10, 10, 14)

Set Finish[P4] = True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P0, P1, P2, P3, P4>.

Solution (iii): P2 requests (0 0 2) i.e. Request [P2] = (0 0 2)

To decide whether the request is granted, we use Resource Request algorithm.
Step 1: Request[P2] <= Need[P2] i.e. (0 0 2) <= (0 0 2) ie: true.
Step 2: Request[P2] <=Available (at time t0, when system snapshot is taken)
i.e. (0 0 2) <= (1 0 2) ie: true.
Step 3: Available = Available – Request [P2] = (1 0 2) - (0 0 2) = (1 0 0)
Allocation[P2] = Allocation[P2] + Request[P2] = (1 3 5) + (0 0 2)= (1 3 7)
Need[P2] = Need[P2] – Request[P2] = (0 0 2) - (0 0 2) = (0 0 0)

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 18

OPERATING SYSTEMS MODULE 3

We arrive at the following new system state:

Allocation Max Available
A B C A B C A B C
P0 0 0 2 0 0 4 1 0 0
P1 1 0 0 2 0 1
P2 1 3 7 1 3 7
P3 6 3 2 8 4 2
P4 1 4 3 1 5 7

The content of the matrix Need is given by Need = Max - Allocation

So, the content of Need Matrix is:
Need
A B C
P0 0 0 2
P1 1 0 1
P2 0 0 0
P3 2 1 0
P4 0 1 4
To determine whether this new system state is safe, we again execute Safety algorithm.
Step 1: Initialization
Work = Available ie: Work = (1 0 0)

Process P0 P1 P2 P3 P4

Finish False False False False False

Step 2: For i=0

Need[P0] <= work ie: (0 0 2) <= (1 0 0) ie: False, So P0 must wait.

Step 2: For i=1

Need[P1] <= work ie: (1 0 1) <= (1 0 0) ie: False So P1 must wait.

Step 2: For i=2

Need[P2] <= work ie: (0 0 0) <= (1 0 0) ie: True, So P2 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P2] = (1 0 0) + (1 3 7) = (2 3 7)

Set Finish[P2] = True

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 19

OPERATING SYSTEMS MODULE 3

Step 2: For i=3

Need[P3] <= work ie: (2 1 0) <= (2 3 7) ie: True, So P3 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P3] = (2 3 7) + (6 3 2) = (8, 6, 9)

Set Finish[P3] = True

Step 2: For i=4

Need[P4] <= work ie: (0 1 4) <= (8, 6, 9) ie: True, So P4 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P4] = (8, 6, 9) + (1 4 3) = (9, 10, 12)

Set Finish[P4] = True

Step 2: For i=0

Need[P0] <= work ie: (0 0 2) <= (9, 10, 12) ie: True, So P0 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P0] = (9, 10, 12) + (0 0 2) = (9, 10, 14)

Set Finish[P0] = True

Step 2: For i=1

Need[P1] <= work ie: (1 0 1) <= (9, 10, 14) ie: True, So P1 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P1] = (9, 10, 14) + (1 0 0) = (10, 10, 14)

Set Finish[P1] = True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P2, P3, P4, P0, P2>.
Conclusion: Since the system is in safe sate, the request can be granted.

[Link] the following snapshot of a system:

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
Answer the following questions using Banker's algorithm.
i) What is the content of the matrix need?

ii) Is the system in a safe state?

iii) If a request from process P1 arrives for (0, 4, 2, 0) can the request be granted?

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 20

OPERATING SYSTEMS MODULE 3

The content of the matrix Need is given by Need = Max - Allocation

So, the content of Need Matrix is:
Need
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
Step 1: Initialization
Work = Available ie: Work = (1 5 2 0)

Process P0 P1 P2 P3 P4

Finish False False False False False

Step 2: For i=0

Need[P0] <= work ie: (0 0 0 0) <= (1 5 2 0) ie: True, So P0 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P0] = (1 5 2 0) + (0 0 1 2) = (1 5 3 2)
Set Finish[P0] = True
Step 2: For i=1
Need[P1] <= work ie: (0 7 5 0) <= (1 5 3 2) ie: False, So P1 must wait
Step 2: For i=2
Need[P2] <= work ie: (1 0 0 2) <= (1 5 3 2) ie: True, So P2 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P2] = (1 5 3 2) + (1 3 5 4) = (2 8 8 6)
Set Finish[P2] = True

Step 2: For i=3

Need[P3] <= work ie: (0 0 2 0) <= (2, 8, 8, 6) ie: True, So P3 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P3] = (2, 8, 8, 6) + (0 6 3 2) = (2, 14, 11, 8)
Set Finish[P3] = True
Step 2: For i=4
Need[P4] <= work ie: (0 6 4 2) <= (2, 14, 11, 8) ie: True, So P4 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P4] = (2, 14, 11, 8) + (0 0 1 4) = (2, 14, 12, 12)
Set Finish[P4] = True

Step 2: For i=1

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 21

OPERATING SYSTEMS MODULE 3

Need[P1] <= work ie: (0 7 5 0) <= (2, 14, 12, 12)ie: True, So P1 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P1] = (2, 14, 12, 12) + (1 0 0 0) = (3, 14, 12, 12)
Set Finish[P1] = True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P0, P2, P3, P4, P0>.
Solution (iii): P1 requests (0, 4, 2, 0) i.e. Request [P1] = (0, 4, 2, 0)
To decide whether the request is granted, we use Resource Request algorithm.
Step 1: Request[P1] <= Need[P1] i.e. (0, 4, 2, 0) <= (0, 7, 5, 0) ie: true.
Step 2: Request[P1] <=Available (at time t0, when system snapshot is taken)
i.e. (0, 4, 2, 0) <= (1, 5, 2, 0) ie: true.
Step 3: Available = Available – Request [P1] = (1, 5, 2, 0) - (0, 4, 2, 0) = (1, 1, 0, 0)
Allocation[P1] = Allocation[P1] + Request[P1] = (1 0 0 0) + (0, 4, 2, 0) = (1, 4, 2, 0)
Need[P1] = Need[P1] – Request[P1] = (0, 7, 5, 0) - (0, 4, 2, 0) = (0, 3, 3, 0)

We arrive at the following new 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 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

The content of the matrix Need is given by Need = Max - Allocation

So, the content of Need Matrix is:
Need
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

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 22

OPERATING SYSTEMS MODULE 3

To determine whether this new system state is safe, we again execute Safety algorithm.
Step 1: Initialization
Work = Available ie: Work = (1, 1, 0, 0)

Process P0 P1 P2 P3 P4

Finish False False False False False

Step 2: For i=0

Need[P0] <= work ie: (0 0 0 0) <= (1 1 0 0) ie: True, So P0 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P0] = (1 1 0 0) + (0 0 1 2) = (1 1 1 2)
Set Finish[P0] = True
Step 2: For i=1
Need[P1] <= work ie: (0 3 3 0) <= (1 1 1 2) ie: False, So P1 must wait
Step 2: For i=2
Need[P2] <= work ie: (1 0 0 2) <= (1 1 1 2) ie: True, So P2 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P2] = (1 1 1 2) + (1 3 5 4) = (2 4 6 6)
Set Finish[P2] = True

Step 2: For i = 3
Need[P3] <= work ie: (0 0 2 0) <= (2 4 6 6) ie: True, So P3 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P3] = (2 4 6 6) + (0 6 3 2) = (2, 10, 9, 8)
Set Finish[P3] = True
Step 2: For i=4
Need[P4] <= work ie: (0 6 4 2) <= (2, 10, 9, 8) ie: True, So P4 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P4] = (2, 10, 9, 8) + (0 0 1 4) = (2, 10, 10, 12)
Set Finish[P4] = True

Step 2: For i=1

Need[P1] <= work ie: (0 3 3 0) <= (2, 10, 10, 12) ie: True, So P1 must be kept in safe sequence.
Step3: Therefore work = work + Allocation [P1] = (2, 10, 10, 12) + (1 4 2 0) = (3, 14, 12, 12)
Set Finish[P1] = True

Step 4: Finish[Pi] = True for 0 <= i<= 4

Hence, the system is currently in a safe state. The safe sequence is <P0, P2, P3, P4, P1>.
Conclusion: Since the system is in safe sate, the request can be granted.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 23

OPERATING SYSTEMS MODULE 3

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 24

OPERATING SYSTEMS MODULE 3

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 25

OPERATING SYSTEMS MODULE 3

DEADLOCK DETECTION
If a system does not use either of deadlock-prevention or deadlock-avoidance algorithm then a
deadlock may occur. In this environment, the system must provide:
1. An algorithm to examine the system-state to determine whether a deadlock has occurred.
2. An algorithm to recover from the deadlock.
SINGLE INSTANCE OF EACH RESOURCE TYPE
If all the resources have only a single instance, then deadlock detection-algorithm can be defined
using a wait-for-graph. The wait-for-graph is applicable to only a single instance of a resource
type.
A wait-for-graph (WAG) is a variation of the resource-allocation-graph. The wait-for-graph can
be obtained from the resource-allocation-graph by removing the resource nodes and collapsing
the appropriate edges.
An edge from Pi to Pj implies that process Pi is waiting for process Pj to release a resource that Pi
needs. An edge Pi → Pj exists if and only if the corresponding graph contains two edges Pi → Rq
and Rq → Pj.
For example:
For the following resource Allocation Graph, write the wait-for –graph.
Consider resource-allocation-graph shown in below Figure

The corresponding wait-for-graph is shown in below Figure:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 26

OPERATING SYSTEMS MODULE 3

A deadlock exists in the system if and only if the wait-for-graph contains a cycle. To detect
deadlocks, the system needs to 1) Maintain the wait-for-graph and 2) Periodically execute an
algorithm that searches for a cycle in the graph.
SEVERAL INSTANCES OF A RESOURCE TYPE
The wait-for-graph is applicable to only a single instance of a resource type. However, the wait-
for-graph is not applicable to a multiple instance of a resource type. The following detection-
algorithm can be used for a multiple instance of a resource type.
Assumptions:
Let ‘n’ be the number of processes in the system Let ‘m’ be the number of resources types.
Following data structures are used to implement this algorithm.
Available [m]
This vector indicates the no. of available resources of each type.
If Available[j]=k, then k instances of resource type Rj is available.
Allocation [n][m]
This matrix indicates no. of resources currently allocated to each process.
If Allocation[i,j]=k, then Pi is currently allocated k instances of Rj.
Request [n][m]
This matrix indicates the current request of each process.
If Request [i, j] = k, then process Pi is requesting k more instances of resource type Rj.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 27

OPERATING SYSTEMS MODULE 3

DETECTION-ALGORITHM USAGE
The detection-algorithm must be executed based on following factors:
1. The frequency of occurrence of a deadlock.
2. The no. of processes affected by the deadlock.
If deadlocks occur frequently, then the detection-algorithm should be executed frequently.
Resources allocated to deadlocked-processes will be idle until the deadlock is broken.
Problem:
Deadlock occurs only when some processes make a request that cannot be granted immediately.
Solution 1:
The deadlock-algorithm must be executed whenever a request for allocation cannot be granted
immediately. In this case, we can identify set of deadlocked-processes and specific process
causing the deadlock.
Solution 2:
The deadlock-algorithm must be executed in periodic intervals. For example: once in an hour,
that is whenever CPU utilization drops below certain threshold
RECOVERY FROM DEADLOCK
********Explain different methods to recover from deadlock

The 3 different deadlock recovery methods are:

1. Inform the system-operator for manual intervention of deadlocked process.
2. Process Termination
3. Resource Preemption
Process Termination
Two methods to remove deadlocks:
i. Terminate all deadlocked-processes. This method will definitely break the deadlock-cycle.
However, this method incurs great expense. This is because a) Deadlocked-processes
might have computed for a long time. b) Results of these partial computations must be
discarded. c) Probably, the results must be re-computed later.
ii. Terminate one process at a time until the deadlock-cycle is eliminated: This method incurs
large overhead. This is because after each process is aborted, deadlock-algorithm must be
executed to determine if any other process is still deadlocked.
For process termination, following factors need to be considered:
1. Priority of the process
2. How long process has computed, and how much longer to completion

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 28

OPERATING SYSTEMS MODULE 3

3. Resources the process has used

4. Resources process needs to complete
5. How many processes will need to be terminated
6. Is process interactive or batch?
Resource Preemption
Some resources are taken from one or more deadlocked-processes. These resources are given to
other processes until the deadlock-cycle is broken. Three issues need to be considered:
1. Selecting a victim: Which resources/processes are to be pre-empted (or blocked)? The
order of pre-emption must be determined to minimize cost. a) The cost factors includes the
time taken by deadlocked-process for computation. b) The number of resources used by
the deadlocked-processes.
2. Rollback: If a resource is taken from a process, the process cannot continue its normal
execution. In this case, the process must be rolled-back to break the deadlock. This method
requires the system to keep more information about the state of all running processes
3. Starvation: In a system where victim-selection is based on cost-factors, the same process
may be always picked as a victim. As a result, this process never completes its designated
task. To ensure a process is picked as a victim only a (small) finite number of times.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 29

OPERATING SYSTEMS MODULE 3

MEMORY MANAGEMENT
Main Memory
Basic Hardware structure of Main memory: Program must be brought (from disk) into main
memory and placed within a process for it to be run. Main-memory and registers are the only
storage that a CPU can access directly.
 Register access in one CPU clock.

 Main-memory can take many cycles.

 Cache sits between main-memory and CPU registers.

 Protection of memory required to ensure correct operation.

 A pair of base- and limit-registers used to define the logical (virtual) address as shown in

below figures.

A base and a limit-register define a logical-address space Hardware address protection with base and limit-registers

ADDRESS BINDING
Explain the multi-step processing of a user program with a neat block diagram.

Address binding of instructions to memory-addresses can happen at 3 different stages as shown

in below figure.
Compile Time: If memory-location is known in advance then absolute code can be generated. If
starting location changes, then we must recompile code

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 30

OPERATING SYSTEMS MODULE 3

Load Time: Must generate re-locatable code if memory-location is not known at compile time.
Execution Time: Binding delayed until run-time if the process can be moved during its execution
from one memory-segment to another. So it needs hardware support for address maps (e.g. base
and limit-registers).

Multistep processing of a user-program

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 31

OPERATING SYSTEMS MODULE 3

LOGICAL VERSUS PHYSICAL ADDRESS SPACE

Logical-address is generated by the CPU (also referred to as virtual-address). Physical-address is
the address seen by the memory-unit. The compile-time and load-time address-binding methods
generate identical logical and physical addresses. The execution-time address binding scheme
results in differing logical and physical addresses.
Differentiate between Logical address and Physical address
S. No. Logical address Physical address

1 An address generated by the CPU An address seen by the memory unit

2 The set of all logical addresses Set of all physical addresses mapped to the
generated by CPU for a program is corresponding logical addresses is referred as
called logical address space. Physical Address space

3 Logical address is generated by the Physical address is computed by Memory

CPU. Management Unit..
4 The user can view the logical The user can never view physical address of
address of a program. program

MMU (Memory-Management Unit)

Hardware device that maps virtual-address to physical-address is MMU. The value in the
relocation-register is added to every address generated by a user-process at the time it is sent to
memory. The user-program deals with logical-addresses; it never sees the real physical-addresses.

Dynamic relocation using a relocation-register

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 32

OPERATING SYSTEMS MODULE 3

DYNAMIC LOADING & LINKING

***Write a short note on dynamic loading and Linking
Dynamic loading can be used to obtain better memory-space utilization. A routine is not loaded
until it is called. This works as follows:
1. Initially, all routines are kept on disk in a re-locatable-load format.
2. Firstly, the main-program is loaded into memory and is executed.
3. When a main-program calls the routine, the main-program first checks to see whether the
routine has been loaded.
4. If routine has been not yet loaded, the loader is called to load desired routine into memory.
5. Finally, control is passed to the newly loaded-routine.
Advantages:
1. An unused routine is never loaded.
2. Useful when large amounts of code are needed to handle infrequently occurring cases.
3. Although the total program-size may be large, the portion that is used (and hence loaded)
may be much smaller.
4. Does not require special support from the OS.
Dynamic Linking: Linking is postponed until execution-time. This feature is usually used with
system libraries, such as language subroutine libraries. A stub is included in the image for each
library-routine reference. The stub is a small piece of code used to locate the appropriate memory-
resident library-routine. When the stub is executed, it checks to see whether the needed routine is
already in memory. If not, the program loads the routine into memory. Stub replaces itself with
the address of the routine, and executes the routine. Thus, the next time that particular code-
segment is reached, the library-routine is executed directly, incurring no cost for dynamic-linking.
All processes that use a language library execute only one copy of the library code.
SHARED LIBRARIES
A library may be replaced by a new version, and all programs that reference the library
will automatically use the new one version info. is included in both program & library so
that programs won't accidentally execute incompatible versions.
SWAPPING
A process must be in memory to be executed. A process can be swapped temporarily out-of-
memory to a backing-store (secondary device) and then brought into memory for continued
execution.
Backing-store is a fast disk which is large enough to accommodate copies of all memory-
images for all users. Roll out/Roll in is a swapping variant used for priority-based
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 33
OPERATING SYSTEMS MODULE 3

scheduling algorithms.
 Lower-priority process is swapped out so that higher-priority process can be

loaded and executed.

 Once the higher-priority process finishes, the lower-priority process can be

swapped in and continued

Swapping depends upon address-binding:
1) If binding is done at load-time, then process cannot be easily moved to a different

location.
2) If binding is done at execution-time, then a process can be swapped into a

different memory- space, because the physical-addresses are computed during

execution-time.

Swapping of two processes using a disk as a backing-store

Major part of swap-time is transfer-time; i.e. total transfer-time is directly proportional to the
amount of memory swapped.
Disadvantages: Context-switch time is fairly high. If we want to swap a process, we must be sure
that it is completely idle. Two solutions: Never swap a process with pending I/O operation.
Execute I/O operations only into OS buffers.
CONTIGUOUS MEMORY ALLOCATION
Memory is usually divided into 2 partitions:
1. One for the resident OS.
2. One for the user-processes.
Each process is contained in a single contiguous section of memory.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 34

OPERATING SYSTEMS MODULE 3

Memory Mapping & Protection

Memory-protection means protecting OS from user-process and protecting user-processes from
one another. Memory-protection is done using
 Relocation-register: contains the value of the smallest physical-address.
 Limit-register: contains the range of logical-addresses.
Each logical-address must be less than the limit-register. The MMU maps the logical-address
dynamically by adding the value in the relocation-register. This mapped-address is sent to
memory as shown in below figure. When the CPU scheduler selects a process for execution,
the dispatcher loads the relocation and limit-registers with the correct values. Because every
address generated by the CPU is checked against these registers, we can protect the OS from the
running-process. The relocation-register scheme provides an effective way to allow the OS size to
change dynamically.
Transient OS code: Code that comes & goes as needed to save memory-space and overhead for
unnecessary swapping.

Hardware support for relocation and limit-registers

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 35

OPERATING SYSTEMS MODULE 3

MEMORY ALLOCATION
Two types of memory partitioning are:
1) Fixed-sized partitioning and
2) Variable-sized partitioning
Fixed-sized Partitioning (Static partition) The memory is divided into fixed-sized partitions
before the process enters main memory. The size of each partition may or may not be same. Each
partition may contain exactly one process. The degree of multiprogramming is bound by the
number of partitions (Limitation on number of processes). When a partition is free, a process is
selected from the input queue and loaded into the free partition. When the process terminates, the
partition becomes available for another process.
Variable-sized Partitioning ( Dynamic partition): Partitions are made as the process enters into
main memory. The OS keeps a table indicating which parts of memory are available and which
parts are occupied. A hole is a block of available memory. Normally, memory contains a set of
holes of various sizes. Initially, all memory is available for user-processes and considered one
large hole. When a process arrives, the process is allocated memory from a large hole. If we find
the hole, we allocate only as much memory as is needed and keep the remaining memory
available to satisfy future requests.
Three strategies used to select a free hole from the set of available holes.

1. First Fit
2. Best Fit
3. Worst Fit
Difference between First fit and Best fit algorithms

S. No. First Fit Algorithm Best Fit Algorithm

1 Allocate the first hole in main memory that is Allocate the smallest hole in main
big enough to fit the requested page memory that is big enough to fit the
requested page
2 Searching time for free holes in main Searching time for free holes in main
memory is less memory is more
3 It is faster in operation It is slower in operation
4 Internal fragmentation is more. Internal fragmentation is less

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 36

OPERATING SYSTEMS MODULE 3

First Fit
 Allocate the first hole that is big enough to fit the requested page.
 Searching can start either at the beginning of the set of holes or at the location where the
previous first-fit search ended.
Best Fit
 Allocate the smallest hole that is big enough to fit the requested page
 We must search the entire list, unless the list is ordered by size.
 This strategy produces the smallest leftover hole. Internal fragmentation is less.
Worst Fit
 Allocate the largest hole and fit the requested page.
 Again, we must search the entire list, unless it is sorted by size.
 This strategy produces the largest leftover hole. Internal fragmentation is more.
First-fit and best fit are better than worst fit in terms of decreasing time and storage utilization.
FRAGMAENTATION
What is fragmentation?
As processes are loaded and removed from main memory the free memory space is broken into
little pieces. After some time that processes cannot be allocated to memory because of smaller
size and memory block or partition remains unused. This problem is called fragmentation.
Two types of memory fragmentation:
1) Internal fragmentation and
2) External fragmentation
Internal Fragmentation
The general approach is to break the physical-memory into fixed-sized blocks and allocate
memory in units based on block size or process size as shown below:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 37

OPERATING SYSTEMS MODULE 3

The allocated(partitioned) memory to a process may be slightly larger than the requested-memory.
The difference between requested-memory and allocated-memory is called internal fragmentation
i.e. Unused memory that is internal to a partition.
External Fragmentation
External fragmentation occurs when there is enough total memory-space to satisfy a request but
the available-spaces are not in contiguous. (i.e. storage is fragmented into a large number of small
holes). For example in below figure we have 3 free holes of size say 9K, 5K and 6K. Let us
consider the next arriving process whose size = 20K. Memory partition cannot be allocated for
this process, even though the total available size of memory is more than the size of process.
Since the available-spaces are not in contiguous.

Both the first-fit and best-fit strategies for memory-allocation suffer from external fragmentation.
Statistical analysis of first-fit reveals that given N allocated blocks, another 0.5 N blocks will be
lost to fragmentation. This property is known as the 50-percent rule.
Given the memory partitions of 200K, 700K, 500K, 300K, 100K, 400K. Apply first fit and
best fit to place 315K, 427K, 250K, 550K processes.
Solution: First Fit

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 38

OPERATING SYSTEMS MODULE 3

Best Fit:

Worst Fit

Total internal fragmentation = 385K + 73K +150K = 568K

Available total free memory holes = 200K +300K + 100K =600K. It is not possible to allocate
memory for process whose size = 550K (No available memory partition whose size >= 550K)
External fragmentation due to non-availability of contiguous memory = 550K ie: the size of
process P4 = 550K.
Therefore the Best fit algorithm makes an efficient use of memory for the given processes.

2. Given the 5 memory partitions 100KB, 500KB, 200KB, 300KB and 600KB, how each of the
First fit, best fit and worst fit algorithms place processes of 212KB, 417KB, 112KB and 426KB
size. Which algorithm makes an efficient use of the memory?

Internal fragmentation = 288K + 88K + 183K = 559K

There is no external fragmentation, because the total available memory (400K) is < P4 process
size (426K).

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 39

OPERATING SYSTEMS MODULE 3

Internal fragmentation = 83K + 88K + 88K + 174K = 433K

There is no external fragmentation

Internal fragmentation = 83K + 188K + 388K = 659K

There is no external fragmentation, because the total available memory (300K) is < P4 process
size (426K). That means, there is no free memory hole which can big enough to fit the P 4 process.
Therefore the Best fit algorithm makes an efficient use of memory for the given processes

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 40

OPERATING SYSTEMS MODULE 3

PAGING
What is paging?
Paging is a memory management scheme that permits the physical address space of a process to
be noncontiguous.
It avoids external fragmentation. It also solves the considerable problem of fitting memory chunks
of varying sizes onto the backing store.
Paging Hardware
Explain the concept of simple paging hardware.
Divide physical (Main) memory into fixed-sized blocks called frames and logical (secondary)
memory is broken into fixed size blocks called pages.
• When a process is to be executed, its pages are loaded into any available main memory-
frames from the backing-store. The backing-store is divided into fixed-sized blocks that
are of the same size as the memory-frames.
• Still have Internal fragmentation

The page-table contains the base-address (frame number on which page is loaded) of each page in
physical-memory. Address generated by CPU is the logical address divided into 2 parts:
1. Page-number(p) is used as an index to the page-table and
2. Offset(d) is combined with the base-address (frame number) to define the physical-
address. This physical-address is sent to the memory-unit to fetch the required
data/instruction.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 41

OPERATING SYSTEMS MODULE 3

Paging model of logical and physical-memory

With supporting paging hardware, explain in detail concept of paging with an example for
32-byte memory with 4 byte pages with a process being 16 bytes. How many bits are
reserved for page number and page offset in the logical address. Suppose the logical address
is 5, calculate the corresponding physical address, after populating memory and page table.
For explanation refer above paging hardware topic
Example:
Given that page size = 4 byte. Therefore frame size = 4 byte.
Process size = 16 byte
Number of pages = 16/4 = 4 Pages
Main memory size = 32 byte
Number of frames in main memory = 32/4 =8
When CPU generates logical address it contains two parts:
Page Number and Offset field.
Number of pages = 4, so we need 2 bits to represent 4 different pages; 0,1,2, 3
Here the number of bits required for Offset field = number of bits required for page size = 2 bits
So the number of bits reserved for page no. = 2 bits and number of bits for offset = 2 bits.
Therefore CPU generates logical address of size 4 bits.
Suppose CPU generates a logical address = 5
Logical address (0101)
Page number (2) Offset (2)
01 01

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 42

OPERATING SYSTEMS MODULE 3

The physical address corresponding to this logical address (5) is obtained by referring the
following memory and page table information.
In the above logical address page no = 01 = Page 1
Now the MMU refers the Page Table and finds the frame number corresponding to page 1. ie:
frame 6.
Since main memory contains 8 frames, we need 3 bits to represent 8 different frames, f0, f1….f7,
in physical address. Offset field = 2 bits
Physical address
Frame number (3) Offset (2)
110 01
That is the logical address 5 (page 1, offset 1) maps to physical address = (6 x 4) +1 = 25
Therefore the physical address corresponding to the logical address 5 = 11001 = 25

PROBLEMS WITH SIMPLE PAGING SCHEME

Mention the problems with simple paging

1. Problem with simple paging is that extra memory references to access the page table is
required to get the frame number corresponding to the page number.
2. Thus two memory accesses are needed to access a byte in main memory, one for the page
table entry and one for the byte.
3. In simple paging scheme memory access is slowed by a factor of 2.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 43

OPERATING SYSTEMS MODULE 3

TRANSLATION LOOKASIDE BUFFER

The problems with simple paging scheme can be solved using translation look-aside buffer (TLB)
paging scheme.
What is TLB? With neat diagram explain the concept of TLB.
A translation-Look-aside buffer (TLB) is an associative high speed memory cache that is used to
reduce the time taken to access a user memory location. It is a part of MMU. The TLB contains
only a few of the page-table entries.
Working:

A TLB consists of two parts: a) Page number) b) Frame number. TLB contains only a few of the
page-table entries. When a logical-address is generated by the CPU, its page-number is presented
(entered) to the TLB.
 If the page-number is found(TLB hit), its frame-number is immediately available and used
to access memory.
 If page-number is not found in TLB (TLB miss), a memory-reference to page table must
be made. The obtained frame-number can be used to access memory. In addition, we add
this page-number and frame-number to the TLB, so that they will be found quickly on the
next reference.
If the TLB is already full of entries, the OS must select one for replacement. Percentage of times
that a particular page-number is found in the TLB is called hit ratio.
Advantage: Search operation is fast.
Disadvantage: Hardware is expensive.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 44

OPERATING SYSTEMS MODULE 3

In the paging scheme with TLB, it takes 20ns to search the TLB and 100ns to access
memory. Find the effective access time and percentage slowdown in memory access time if
i. Hit ratio is 80%

ii. Hit ratio is 98%

Solution:
In the paging scheme with TLB, if we find the page in TLB, it takes 20ns to search the TLB and
100ns to access memory, and then a mapped memory access takes 120ns when the page number is
in the TLB.
If we fail to find the page number in TLB(20ns), then we must first access memory for the page
table to get the page number and corresponding frame number(100ns). Then access memory for
the desired byte in memory (100ns).
Thus total 220ns time required to access the byte if the page number is not in TLB. (TLB search
time in main memory page table access + In main memory desired byte access)
i) Effective memory Access time = 0.80 x 120 + 0.20 x 220 = 140ns
Percentage slow down in memory access time = (140-100) = 40%

ii) Effective memory Access time = 0.98 x 120 + 0.02 x 220 =122ns
Percentage slow down in memory access time = (122-100) = 22%

MEMORY PROTECTION
Memory-protection is achieved by protection-bits for each frame. The protection-bits are kept in
the page-table. One protection-bit can define a page to be read-write or read-only. Every reference
to memory goes through the page-table to find the correct frame-number. Firstly, the physical-
address is computed. At the same time, the protection-bit is checked to verify that no writes are
being made to a read-only page. An attempt to write to a read-only page causes a hardware-trap to
the OS (or memory-protection violation).

Valid Invalid Bit

This bit is attached to each entry in the page-table as shown below. Valid bit: The page is in the
process’ logical-address space. Invalid bit: The page is not in the process’ logical-address space.
Illegal addresses are trapped by use of valid-invalid bit. The OS sets this bit for each page to allow
or disallow access to the page

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 45

OPERATING SYSTEMS MODULE 3

Valid(V) or Invalid (I) bit in page table

SHARED PAGES
Advantage of paging: Possible to share common code. Re-entrant code is non-self-modifying
code, it never changes during execution. Two or more processes can execute the same code at the
same time. Each process has its own copy of registers and data-storage to hold the data for the
process's execution. The data for 2 different processes will be different. Only one copy of the
editor need be kept in physical-memory as shown in below figure. Each user's page-table maps
onto the same physical copy of the editor, but data pages are mapped onto different frames.
Disadvantage: 1) Systems that use inverted page-tables have difficulty implementing shared-
memory

Sharing of code in paging environment

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 46

OPERATING SYSTEMS MODULE 3

STRUCTURE OF THE PAGE TABLE

The 3 types of page table structures are:
1. Hierarchical Paging
2. Hashed Page-tables
3. Inverted Page-tables
HIERARCHICAL PAGING
***Explain Hierarchical Paging structure with example
Most computers support a large logical-address space (232 to 264). In these systems, the page-table
itself becomes excessively large. So divide the page-table into smaller pieces.
Two Level Paging Algorithm: The page-table itself is also paged as shown below:

Two level page table scheme

This is also known as forward-mapped page-table because address translation works from the
outer page-table inwards.

Address translation for a two-level 32-bit paging architecture

Consider the system with a 32-bit logical-address space and a page-size of 4 KB. A logical-
address is divided into 20-bit page-number and 12-bit page-offset. Since the page-table is paged,

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 47

OPERATING SYSTEMS MODULE 3

the page-number is further divided into 10-bit page-number and 10-bit [Link], a logical-
address is as follows:

HASHED PAGE TABLES

This approach is used for handling address spaces larger than 32 bits. The hash-value is the virtual
page-number. Each entry in the hash-table contains a linked-list of elements that hash to the same
location (to handle collisions). Each element consists of 3 fields: Virtual page-number, Value of
the mapped page-frame and Pointer to the next element in the linked-list.
The algorithm works as follows

Hashed page-table

The virtual page-number is hashed into the hash-table. The virtual page-number is compared with
the first element in the linked-list. If there is a match, the corresponding page-frame (field 2) is
used to form the desired physical-address. If there is no match, subsequent entries in the linked-
list are searched for a matching virtual page-number.
INVERTED PAGE TABLES
It has one entry for each real page of memory. Each entry consists of virtual-address of the page
stored in that real memory-location and information about the process that owns the page.
Each virtual-address consists of a triplet:
<process-id, page-number, offset>.
Each inverted page-table entry is a pair <process-id, page-number>
The algorithm works as follows:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 48

OPERATING SYSTEMS MODULE 3

Inverted page table

1. When a memory-reference occurs, part of the virtual-address, consisting of <process-id,

page-number>, is presented to the memory subsystem.
2. The inverted page-table is then searched for a match.
3. If a match is found, at entry i-then the physical-address < i, offset> is generated.
4. If no match is found, then an illegal address access has been attempted.
Advantage:
1) Decreases memory needed to store each page-table
Disadvantages:
1. Increases amount of time needed to search table when a page reference occurs.
2. Difficulty implementing shared-memory.

SEGMENTATION
Explain segmentation with an example.
Segmentation is a memory-management scheme that supports user-view of memory. A logical-
address space is a collection of segments. Each segments of various size, which has a name and a
length. The addresses specify both segment-name and offset within the segment.
Normally, the user-program is compiled, and the compiler automatically constructs segments
reflecting the input program.
For example: The code, Global variables, The heap, from which memory is allocated. The stacks
used by each thread.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 49

OPERATING SYSTEMS MODULE 3

Programmers view of a program

Hardware Support
Segment-table maps 2 dimensional user-defined addresses into one-dimensional physical-
addresses. In the segment-table, each entry has following 2 fields:
Segment-base contains starting physical-address where the segment resides in memory.
Segment-limit specifies the length of the segment

Segmentation hardware
A logical-address consists of 2 parts:
Segment-number(s) is used as an index to the segment-table. Offset(d) must be between 0 and the
segment-limit.
If offset is not between 0 & segment-limit, then we trap to the OS (logical-addressing attempt
beyond end of segment).
If offset is legal, then it is added to the segment-base to produce the physical-memory address

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 50

OPERATING SYSTEMS MODULE 3

Consider the following segment table:

Segment Base Length(Limit)
0 219 600
1 2300 14
2 1327 580
3 1952 96

What are the physical addresses for the following logical addresses:
i. (0, 430) ii. (1, 10) iii. (2, 500) iv) 3, 400

Solution
i. (0, 430)
Segment = 0 and limit = 430
Therefore physical address = 219 + 430 = 649
ii. (1, 10)
Segment = 1 and limit = 10
Therefore physical address = 2300 + 10 = 2310
iii. (2, 500)
Segment = 2 and limit = 500
Therefore physical address = 1327 + 500 = 1827
iv. (3, 400)
Segment = 3 and limit value = 400 which is > limit value 96. So a reference to byte
400 of segment 3 would result in a trap to the OS, as this segment is only 96 bytes
long, thereby generating segment Fault error.
Consider the following segment table:

Segment Base Length(Limit)

0 330 124
1 876 211
2 111 99
3 498 302

What are the physical addresses for the following logical addresses:
i. (0, 9, 9) ii. (2, 78) iii. (1, 265) iv) (3, 222) v) (0, 111)

Solution
i. (0, 9, 9): Logical address is incorrect; since it contains only two parts as segment and
limit.
ii. (2, 78)
Segment = 2 and limit = 78
Therefore physical address = 111 + 78 = 189
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 51
OPERATING SYSTEMS MODULE 3

iii. (1, 265)

Segment = 1 and limit = 265
Llimit value = 265 which is > limit value 211. So a reference to byte 265 of segment 1
would result in a trap to the OS, as the segment1 is only 211 bytes long, thereby
generating segment Fault error.
iv. (3, 222)
Segment = 3 and limit = 222
Therefore physical address = 498 + 222 = 720
v. (0, 111)
Segment = 0 and limit = 111
Therefore physical address = 330 + 111 = 441

Differentiate between segmentation and Paging

S. No. Paging Segementation
1 A page is of fixed block size. A segment is of variable size
2 Paging may lead to internal Segmentation may lead to external fragmentation
fragmentation
3 The user specified address is The user specifies each address by two quantities
divided by CPU into a page number a segment number and the offset (Segment limit)
and offset.
4 The hardware decides the page size The segment size is specified by the user
5 Paging involves a page table that Segmentation involves the segment table that
contains base address of each page contains segment number and offset (segment
length).

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 52

 MODULE 4

Virtual memory Management: Background, Demand Paging, Copy on Write; Page Replacement;

Allocation of Frames; Thrashing;

File System, Implementation of File system; File system; File concept, Access Methods; Directory

structure; File system mounting; File sharing; Protection; Implementing File system; File system

structure; File system implementation; Directory implementation; Allocation Methods; Free space

Management.
OPERATING SYSTEMS MODULE 4

VIRTUAL MEMORY MANAGEMENT

Virtual Memory
What is virtual memory? How it can be implemented? What are its benefits?
Virtual Memory is a technique that allows the execution of processes that are not completely in
[Link] involves the separation of logical-memory as perceived by users from physical-
memory. This separation allows an extremely large VM to be provided for programmers when
only a smaller physical memory is available. VM makes the task of programming much easier.
Benefits of Virtual Memory:
1. More programs could be run at the same time.
2. Programmers could write for a large virtual-address space and need no longer use
overlays.
3. Less I/O would be needed to load/swap programs into memory, so each user program
would run faster.
Virtual-memory can be implemented by:
i. Demand paging and
ii. Demand segmentation.
The virtual (or logical) address-space of a process refers to the logical (or virtual) view of how a
process is stored in memory. Physical-memory may be organized in page-frames and that the
physical page-frames assigned to a process may not be contiguous. It is up to the MMU to map
logical-pages to physical page-frames in memory.

Diagram showing virtual memory that is larger than physical-memory

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 1

OPERATING SYSTEMS MODULE 4

DEMAND PAGING
********What is on demand paging?Explain demand paging in detail.
The process of loading the page into main memory on demand (whenever page fault occurs) is
known as demand paging.
 A demand-paging system is similar to a paging-system with swapping Processes reside in
secondary-memory (usually a disk).
 It is a method of virtual memory management, where it follows that a process begins
execution with none of its pages in main memory, and many page faults will occur until
most of a process's working set of pages are located in main memory.
 When we want to execute a process, we swap it into memory. Instead of swapping in a
whole process, lazy swapper brings only those necessary pages into main memory

The valid-invalid bit scheme can be used to distinguish between pages that are in memory and
pages that are on the disk.
 If the bit is set to valid, the associated page is both legal and in memory.
 If the bit is set to invalid, the page either is not valid (i.e. not in the logical-address space
of the process) or is valid but is currently on the disk
The hardware to support demand paging is i) Page table and ii) Secondary memory.
Page table mark an entry invalid through a valid-invalid bit. Secondary memory holds the pages
that are not in main memory.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 2

OPERATING SYSTEMS MODULE 4

Page-table when some pages are not in main-memory

Advantages:
i. Avoids reading into memory-pages that will not be used,
ii. Decreases the swap-time and
iii. Decreases the amount of physical-memory needed.
PAGE FAULT
******What is a page fault? With a supporting diagram explain the steps involved in
handling page fault.
A page fault is a type of exception raised by computer hardware when a running program
(process) tries to access a page that was not brought into main memory.
Procedure for handling the page-fault:

Steps in handling a page-fault

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 3

OPERATING SYSTEMS MODULE 4

1. Check an internal-table to determine whether the reference was a valid or an invalid

memory access.
2. If the reference is invalid, we terminate the process. If reference is valid, but we have not
yet brought in that page, we now page it in.
3. Find a free-frame (by taking one from the free-frame list, for example).
4. Read the desired page into the newly allocated frame.
5. Modify the internal-table and the page-table to indicate that the page is now in memory.
6. Restart the instruction that was interrupted by the trap.
PURE DEMAND PAGING
What is pure demand paging?
It is technique in which, never bring pages into main memory until it is required.
• In the extreme case, we can start executing a process with no pages in memory.
• When the operating system sets the instruction pointer to the first instruction of the
process, which is on a non-memory-resident page, the process immediately faults for the
page.
• After this page is brought into memory, the process continues to execute, faulting as
necessary until every page that it needs is in memory. At that point it can execute with no
more faults.
• This scheme is pure demand paging such that never bring a page into memory until it is
required.
Some programs may access several new pages of memory with each instruction, causing multiple
page-faults and poor performance.
Programs tend to have locality of reference, so this results in reasonable performance from
demand paging.

PERFORMANCE OF DEMAND PAGING

*****Discuss on the performance of demand paging
Demand paging can significantly affect the performance of a computer-system.
Let p be the probability of a page-fault (0≤p ≤1). if p = 0, no page-faults and if p = 1, every
reference is a fault.
The effective access time (EAT) = [(1 - p) * memory access] + [p * page-fault time]
A page-fault causes the following events to occur:
1. Trap to the OS.
2. Save the user-registers and process-state.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 4

OPERATING SYSTEMS MODULE 4

3. Determine that the interrupt was a page-fault.

4. Check that the page-reference was legal and determine the location of the page on the disk.
5. Issue a read from the disk to a free frame:
a). Wait in a queue for this device until the read request is serviced.
b). Wait for the device seek time.
c). Begin the transfer of the page to a free frame.
6. While waiting, allocate the CPU to some other user.
7. Receive an interrupt from the disk I/O subsystem (I/O completed).
8. Save the registers and process-state for the other user (if step 6 is executed).
9. Determine that the interrupt was from the disk.
10. Correct the page-table and other tables to show that the desired page is now in memory.
11. Wait for the CPU to be allocated to this process again.
12. Restore the user-registers, process-state, and new page-table, and then resume the
interrupted instruction.
COPY-ON-WRITE
***Explain copy-on write process in virtual memory.
Copy On Write technique allows the parent and child processes initially to share the same pages in
memory. If either process writes to a shared-page, a copy of the shared-page is created. Copy on
write allows more efficient process creation as only modified pages are copied.
For example:
Assume that the child process attempts to modify a page containing portions of the stack, with the
pages set to be copy-on-write. OS will then create a copy of this page, mapping it to the address
space of the child process. Child process will then modify its copied page & not the page
belonging to the parent process.

Before Process 1 modifies page C.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 5
OPERATING SYSTEMS MODULE 4

After Process 1 modifies page C

PAGE REPLACEMENT
Why do we need for Page Replacement in OS?
If we increase our degree of multiprogramming, we are over-allocating memory. While a user-
process is executing, a page-fault occurs. Then the OS determines where the desired page is
residing on the disk but then finds that there are no free frames on the free-frame list.
Then the operating System could:
 Terminate the user-process (Not a good idea).
 Swap out a process, freeing all its frames, and reducing the level of multiprogramming.
 Perform page replacement.

Need for page replacement

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 6

OPERATING SYSTEMS MODULE 4

Basic Concepts of Page Replacement

If no frame is free, we find one that is not currently being used and free it
Page replacement takes the following steps:
1. Find the location of the desired page on the disk.
2. Find a free frame:
a) If there is a free frame, use it.
b) If there is no free frame, use a page-replacement algorithm to select a victim-frame.
c) Write the victim-frame to the disk; change the page and frame-tables accordingly.
3. Read the desired page into the newly freed frame; change the page and frame-tables.
4. Restart the user-process.

Page replacement

What are the problems that occur in page replacement concept? How it can be overcome.
Problem: If no frames are free, 2 page transfers (1 out & 1 in) are required. This situation
doubles the page-fault service-time and increases the EAT accordingly.
Solution: Use a modify-bit (or dirty bit).
Each page or frame has a modify-bit associated with the hardware. The modify-bit for a page is
set by the hardware whenever any word is written into the page (indicating that the page has been
modified).
Working: When we select a page for replacement, we examine it‟s modify-bit.
If the modify-bit =1, the page has been modified. So, we must write the page to the disk.
If the modify bit = 0; the page has not been modified. So we need not write the page to the disk, it
is already there.
Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 7
OPERATING SYSTEMS MODULE 4

Advantage: Can reduce the time required to service a page-fault.

We must solve 2 major problems to implement demand paging:
Develop a Frame-allocation algorithm: If we have multiple processes in memory, we must decide
how many frames to allocate to each process.
Develop a Page-replacement algorithm: We must select the frames that are to be replaced.

PAGE REPLACEMENT ALGORITHMS

1) FIFO page replacement
2) Optimal page replacement
3) LRU page replacement (Least Recently Used)
To determine the number of page faults for a particular reference string and page-replacement
algorithm, we also need to know the number of page frames available.
As the number of frames available increases, the number of page faults decreases
FIFO Page Replacement
Each page is associated with the time when that page was brought into memory. When a page
must be replaced, the oldest page is chosen. We use a FIFO queue to hold all pages in memory.
When a page must be replaced, we replace the page at the head of the queue. When a page is
brought into memory, we insert it at the tail of the queue.
Example: Consider the following references string with frames initially empty;

 The first three references (7, 0, 1) cause page-faults and are brought into these empty
frames.
 The next reference (2) replaces page 7, because page 7 was brought in first.
 Since 0 is the next reference and 0 is already in memory, we have no fault for this
reference.
 The first reference to 3 results in replacement of page 0, since it is now first in line.
 This process continues till the end of string.
 There are fifteen page faults altogether.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 8

OPERATING SYSTEMS MODULE 4

Advantage: Easy to understand & program.

Disadvantages: Performance is not always good. A bad replacement choice increases the page-
fault rate (Belady's anomaly).
BELADY'S ANOMALY
For example consider the following reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
For this example, the number of page faults for four frames is ten which is greater than the
number of page faults for three frames is nine. This is the most unexpected result which is known
as Belady’s anamoly.

Page-fault curve for FIFO replacement on a reference string

****What is Belady's anomaly? Explain with an example.

For some page replacement algorithms, on increasing the number of page frames, the number of
page fault do not necessarily decrease, they may also increase. This is the most unexpected result
which is known as Belady’s anamoly in operating system.
Example: Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with the number of frame
used is 3 and 4.
FIFO with 3 frames:
Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 4 4 4 5 5 5 5 5 5
2 2 2 2 1 1 1 1 1 3 3 3
3 3 3 3 2 2 2 2 2 4 4
No. of Page faults √ √ √ √ √ √ √ √ √

No. of page faults = 9

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 9

OPERATING SYSTEMS MODULE 4

FIFO with 4 frames:

Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 1 1 1 5 5 5 5 4 4
2 2 2 2 2 2 2 1 1 1 1 5
3 3 3 3 3 3 3 2 2 2 2
4 4 4 4 4 4 4 3 3 3
No. of Page faults √ √ √ √ √ √ √ √ √ √

No. of page faults = 10

Conclusion: With 3 frames, No. of page faults = 9. With 4 frames, No. of page faults = 10.
Thus, Belady's anomaly has occurred, when number of frames is increased from 3 to 4.

OPTIMAL PAGE REPLACEMENT

Working principle:
Replace the page that will not be used for the longest period of time. That means we have to see
the page which is demanded as the last page in future demand. This is used mainly to solve the
problem of Belady‟s Anamoly. This has the lowest page-fault rate of all algorithms.
Consider the following reference string:

Optimal page-replacement algorithm

 The first three references cause faults that fill the three empty frames.
 The reference to page 2 replaces page 7, because page 7 will not be used until reference is
18.
 The page 0 will be used at 5, and page 1 at 14.
 With only nine page-faults, optimal replacement is much better than a FIFO algorithm,
which results in fifteen faults.
Advantage: Guarantees the lowest possible page-fault rate for a fixed number of frames.
Disadvantage: 1) Difficult to implement, because it requires future knowledge of the reference
string.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 10

OPERATING SYSTEMS MODULE 4

The key difference between FIFO and OPT:

FIFO uses the time when a page was brought into memory. OPT uses the time when a page is to
be used.
LRU PAGE REPLACEMENT (Least Recently Used)
Working principle:
Replace the page that has not been used for the longest period of time.
Each page is associated with the time of that page's last use
Example: Consider the following reference string:

LRU page-replacement algorithm

 The first five faults are the same as those for optimal replacement.
 When the reference to page 4 occurs, LRU sees that of the three frames, page 2 was used
least recently. Thus, the LRU replaces page 2.
 The LRU algorithm produces twelve page faults.
Two methods of implementing LRU:
[Link]
 Each page-table entry is associated with a time-of-use field.
 A counter(or logical clock) is added to the CPU.
 The clock is incremented for every memory-reference.
 Whenever a reference to a page is made, the contents of the clock register are copied to the
time-of-use field in the page-table entry for that page.
 We replace the page with the smallest time value.
Stack
 Keep a stack of page-numbers as shown in below figure.
 Whenever a page is referenced, the page is removed from the stack and put on the top.
 The most recently used page is always at the top of the stack. The least recently used page
is always at the bottom.
 Stack is best implement by a doubly linked-list.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 11

OPERATING SYSTEMS MODULE 4

Advantage:
1) Does not suffer from Belady's anomaly.
Disadvantage:
1) Few computer systems provide sufficient hardware support for true LRU page replacement.
Both LRU & OPT are called stack algorithms.

Use of a stack to record the most recent page references

LRU-Approximation Page Replacement
Some systems provide a reference bit for each page. Initially, all bits are cleared (to 0) by the OS.
As a user-process executes, the bit associated with each page referenced is set (to 1) by the
hardware. By examining the reference bits, we can determine which pages have been used and
which have not been used. This information is the basis for many page-replacement algorithms
that approximate LRU replacement.
Additional-Reference-Bits Algorithm
We can gain additional ordering information by recording the reference bits at regular intervals.
A 8-bit byte is used for each page in a table in memory. At regular intervals, a timer-interrupt
transfers control to the OS. The OS shifts the reference bit for each page into the high-order bit of
its 8-bit byte. These 8-bit shift registers contain the history of page use, for the last eight time
periods.
Examples:
00000000 - This page has not been used in the last 8 time units (800 ms). 11111111 - Page has
been used every time unit in the past 8 time units.
11000100- has been used more recently than 01110111. The page with the lowest number is the
LRU page, and it can be replaced. If numbers are equal, FCFS is used.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 12

OPERATING SYSTEMS MODULE 4

SECOND-CHANCE ALGORITHM
The number of bits of history included in the shift register can be varied to make the updating as
fast as possible. In the extreme case, the number can be reduced to zero, leaving only the
reference bit itself. This algorithm is called the second-chance algorithm. This is the variant of
basic FIFO replacement algorithm.
Procedure:
 Initially all reference bits are set to 0 and any page hit results in corresponding reference
bit to set to 1
 When a page has been selected for replacement, we inspect its reference bit
 If reference bit = 0, we proceed to replace this page.
 If reference bit = 1, we give the page a second chance & move on to select next FIFO
page.
 When a page gets a second chance, its reference bit is cleared, and its arrival time is reset.

A circular queue can be used to implement the second-chance algorithm as shown in above figure.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 13

OPERATING SYSTEMS MODULE 4

 A pointer (that is, a hand on the clock) indicates which page is to be replaced next.
 When a frame is needed, the pointer advances until it finds a page with a 0 reference bit.
 As it advances, it clears the reference bits.
 Once a victim page is found, the page is replaced, and the new page is inserted in the
circular queue in that position.
Enhanced Second-Chance Algorithm
We can enhance the second-chance algorithm by considering Reference bit and modify-bit.
We have following 4 possible classes:
1) (0, 0) neither recently used nor modified -best page to replace.
2) (0, 1) not recently used hut modified-not quite as good, because the page will need to be
written out before replacement.
3) (1, 0) recently used but clean-probably will be used again soon.
4) (1, 1) recently used and modified -probably will be used again soon, and the page will be
need to be written out to disk before it can be replaced.
Each page is in one of these four classes. When page replacement is called for, we examine the
class to which that page belongs. We replace the first page encountered in the lowest nonempty
class.
Counting-Based Page Replacement
[Link] page-replacement algorithm
Working principle: The page with the smallest count will be replaced. The reason for this
selection is that an actively used page should have a large reference count.
Problem:
When a page is used heavily during initial phase of a process but then is never used again. Since it
was used heavily, it has a large count and remains in memory even though it is no longer needed.
Solution:
Shift the counts right by 1 bit at regular intervals, forming an exponentially decaying average
usage count.
MFU (Most Frequently Used) page-replacement algorithm
Working principle: The page with the smallest count was probably just brought in and has yet to
be used.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 14

OPERATING SYSTEMS MODULE 4

EXERCISE PROBLEMS

1) Consider the page reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, for a memory

with 3 frames, how many page faults would occur for i) LRU algorithm ii) FIFO algorithm
and iii) Optimal page replacement algorithm? Which is the most efficient among them?
Solution:
LRU with 3 frames:
Frames 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
2 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
3 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
No. of Page faults √ √ √ √ √ √ √ √ √ √ √ √

No of page faults = 12
FIFO with 3 frames:
Frames 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
3 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
No. of Page faults √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

No of page faults = 15
Optimal with 3 frames:
Frames 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
2 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
3 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
No. of Page faults √ √ √ √ √ √ √ √ √

No of page faults = 9
Conclusion: The optimal page replacement algorithm is most efficient among three algorithms, as
it has lowest page faults i.e. 9.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 15

OPERATING SYSTEMS MODULE 4

2) Consider the page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

How many page fault, would occur for the following page replacement algorithms assuming
3 and 5 frames. i) LRU ii) Optimal
Solution:

LRU with 3 frames:

Frames 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2
2 2 2 2 2 2 2 6 6 6 6 3 3 3 3 3 3 3 3 3
3 3 3 3 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6
No. of Page faults √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

No of page faults = 15
LRU with 5 frames:
Frames 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6
4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 7 7 7 7 7 7 7 7
No. of Page faults √ √ √ √ √ √ √ √

No of page faults = 8
Optimal with 3 frames:
Frames 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 6
2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2
3 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 1
No. of Page faults √ √ √ √ √ √ √ √ √ √ √

No of page faults = 11

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 16

OPERATING SYSTEMS MODULE 4

Optimal with 5 frames:

Frames 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6
5 5 5 5 5 5 5 7 7 7 7 7 7 7 7
No. of Page faults √ √ √ √ √ √ √

No of page faults = 7

3) For the page reference, 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5. calculate the page faults that occur
using FIFO and LRU for 3 and 4 page frames respectively.
Solution:
LRU with 3 frames:
Frames 5 4 3 2 1 4 3 5 4 3 2 1 5
1 5 5 5 2 2 2 3 3 3 3 3 3 5
2 4 4 4 1 1 1 5 5 5 2 2 2
3 3 3 3 4 4 4 4 4 4 1 1
No. of Page faults √ √ √ √ √ √ √ √ √ √ √

No of page faults = 11

LRU with 4 frames:

Frames 5 4 3 2 1 4 3 5 4 3 2 1 5
1 5 5 5 5 1 1 1 1 1 1 2 2 2
2 4 4 4 4 4 4 4 4 4 4 4 5
3 3 3 3 3 3 3 3 3 3 3 3
4 2 2 2 2 5 5 5 5 1 1
No. of Page faults √ √ √ √ √ √ √ √ √

No of page faults = 9

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 17

OPERATING SYSTEMS MODULE 4

FIFO with 3 frames:

Frames 5 4 3 2 1 4 3 5 4 3 2 1 5
1 5 5 5 2 2 2 3 3 3 3 3 1 1
2 4 4 4 1 1 1 5 5 5 5 5 5
3 3 3 3 4 4 4 4 4 2 2 2
No. of Page faults √ √ √ √ √ √ √ √ √ √

No of page faults = 10

FIFO with 4 frames:

Frames 5 4 3 2 1 4 3 5 4 3 2 1 5
1 5
2
3
4
No. of Page faults √ √ √ √ √ √ √ √ √ √ √

No of page faults = 11

4) Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Calculate the page faults using

FIFO and LRU for memory with 3 and 4 frames.
Solution:
FIFO with 3 frames:
Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 4 4 4 5 5 5 5 5 5
2 2 2 2 1 1 1 1 1 3 3 3
3 3 3 3 2 2 2 2 2 4 4
No. of Page faults √ √ √ √ √ √ √ √ √

No. of page faults = 9

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 18

OPERATING SYSTEMS MODULE 4

FIFO with 4 frames:

Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 1 1 1 5 5 5 5 4 4
2 2 2 2 2 2 2 1 1 1 1 5
3 3 3 3 3 3 3 2 2 2 2
4 4 4 4 4 4 4 3 3 3
No. of Page faults √ √ √ √ √ √ √ √ √ √

No. of page faults = 10

LRU with 3 frames:
Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 4 4 4 5 5 5 3 3 3
2 2 2 2 1 1 1 1 1 1 4 4
3 3 3 3 2 2 2 2 2 2 5
No. of Page faults √ √ √ √ √ √ √ √ √

No. of page faults = 10

LRU with 4 frames:
Frames 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 1 1 1 1 1 1 1 1 5
2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 5 5 5 5 4 4
4 4 4 4 4 4 4 3 3 3
No. of Page faults √ √ √ √ √ √ √ √

No. of page faults = 8

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 19

OPERATING SYSTEMS MODULE 4

ALLOCATION OF FRAMES
We must also allocate at least a minimum number of frames to processes. One reason for this is
performance. As the number of frames allocated to each process decreases, the page-fault rate
increases, slowing process execution. In addition, when a page-fault occurs before an executing
instruction is complete, the instruction must be restarted. The minimum number of frames is
defined by the computer architecture.
Explain any one frame allocation algorithms with example
ALLOCATION ALGORITHMS
1. Equal Allocation
2. Proportional Allocation
Equal Allocation:
We split m frames among n processes is to give everyone an equal share, m/n frames.
For example: if there are 93 frames and five processes, each process will get 18 frames. The three
leftover frames can be used as a free-frame buffer pool.
Proportional Allocation
We can allocate available memory to each process according to its size.
In both 1 & 2, the allocation may vary according to the multiprogramming level. If the
multiprogramming level is increased, each process will lose some frames to provide the memory
needed for the new process. Conversely, if the multiprogramming level decreases, the frames that
were allocated to the departed process can be spread over the remaining processes.
GLOBAL VERSUS LOCAL ALLOCATION
Global Replacement Local Replacement
Allows a process to a replacement frame from Each process selects from only its own set of
the set of all frames. allocated frames.
A process may happen to select only frames Number of frames allocated to a process does not
allocated to other processes, thus increasing the change.
number of frames allocated to it.
Disadvantage: Disadvantage:
A process cannot control its own page-fault rate. Might prevent a process by not making available
to it other less used pages of memory.
Advantage:
Results in greater system throughput.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 20

OPERATING SYSTEMS MODULE 4

THRASHING
What is thrashing? Explain thrashing concept in operating system
As we increase the degree of multiprogramming CPU utilization increases up to a certain level,
after that it drastically decreases, that is called as thrashing.
A process is thrashing if it is spending more time paging than executing.
Cause of Thrashing
• Thrashing results in severe performance problems
• The OS monitors CPU utilization. If it is low increase the degree of multiprogramming by
introducing new process to the system.
• If global replacement algorithm is used it replaces pages without regard to the process to
which they belong
• As the processes wait for the paging device, CPU utilization decreases
The thrashing phenomenon:
As processes keep faulting, they queue up for the paging device, so CPU utilization decreases
The CPU scheduler sees the decreasing CPU utilization and increases the degree of
multiprogramming as a result. The new process causes even more page-faults and a longer queue!

Thrashing

How to detect thrashing in operating system

[Link] one process starts thrashing, it cannot steal frames from another process and cause the latter
to thrash as well.
[Link] must provide a process with as many frames as it needs. This approach defines the
locality model of process execution. Locality Model states that As a process executes, it moves
from locality to locality. A locality is a set of pages that are actively used together.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 21

OPERATING SYSTEMS MODULE 4

A program may consist of several different localities, which may overlap.

Determination of number of frames allocated to a process
To know how many frame a process needs there are several techniques. The most popular
technique called Working set strategy starts by looking at how many frames the process is
actually using. This approach is the locality model of process execution
Working set model
The model uses the parameter ∆ , to define working-set window. The set of pages in the most
recent ∆ page references is the working set. If the page is in active-use, it will be in working-set
If it is no longer been used, it will drop from the working set ∆ time units after its last reference.
Let us consider ∆ = 10 and at time t1 WS(t1) = {1, 2, 5, 6,7} and WS(t2) = { 3, 4}

  working-set window  a fixed number of page references

Example: 10,000 instruction
WSSi (working set of Process Pi) = total number of pages referenced in the most recent  (varies
in time)
If  is too small will not encompass entire locality. If  is too large will encompass several
localities.
if  =   will encompass entire program.
D =  WSSi  total demand frames
if D > m  Thrashing ( if page demand is more than the available total frames)
Policy if D > m, then suspend one of the processes

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 22

OPERATING SYSTEMS MODULE 4

Page Fault – Frequency

Thrashing has high page-fault rate, thus we want to control the rate. When it is too high, the
process needs more frames. If the page fault rate is too low, then the process may have too many
frames. We can establish upper and lower bounds on the page fault-rate. If the actual page-fault
rate exceeds the upper limit, we allocate the process another frame and if the page-fault rate falls
below the lower limit remove a frame from the process. Thus the page-fault rate is controlled and
thrashing is prevented.
Page-Fault Frequency Scheme
Establish “acceptable” page-fault rate. If actual rate is too low, process loses frame. If actual rate
is too high, process gains frame.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 23

OPERATING SYSTEMS MODULE 4

FILE SYSTEM
File system provides a mechanism for on-line storage of and access to both data and programs of
OS and all users of the computer system. The file system consists of two distinct parts:
 Collection of files, each storing related data
 Directory structure which organizes and provides information about all files in the system.
What is a file? What are the different types of file?
A file is a named collection of related information on secondary-storage.
Commonly, file represents program and data. Data in file may be in numeric, alphabetic or binary
form. Four types of files are:
1) Text file: sequence of characters organized into lines.

2) Source file: sequence of subroutines & functions.

3) Object file: sequence of bytes organized into blocks.

4) Executable file: series of code sections.

Mention any 5 file attributes.

1. Name: The only information kept in human-readable form.
2. Identifier: It is a unique number which identifies the file within file-system and it is in
non-human-readable form.
3. Type: It is used to identify different types of files.
4. Location: It is a pointer to device and location of file.
5. Size: Current-size of file in terms of bytes, words, or blocks. It also includes maximum
allowed size.
6. Protection: Access-control information determines who can do reading, writing and
executing.
7. Time, date, & user identification: These information can be kept for creation, last
Modification and last use. These data can be useful for protection, security and
Usage, monitoring.
Mention any 5 file operations.
1. Creating a file: The two steps in creation of files are: i.) Find the space in the file-system for
the file. ii) An entry for the new file is made in the directory.
[Link] a file: Make a system call specifying both file name and information to be written to
the file. The system searches the directory to find the file’s location.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 24

OPERATING SYSTEMS MODULE 4

The write-pointer must be updated whenever a write-operation occurs.

[Link] a file: Make a system-call specifying both file-name and location of the next block of
the file in the memory. The system searches the directory to find the file's location. The read-
pointer must be updated whenever a read-operation occurs. Same pointer (rp & wp) is used for
both read- & write-operations. This results in → saving space and reducing system-complexity.
4. Repositioning within a file: Two steps are: Search the directory for the appropriate entry.
Set the current-file-position to a given value. This file-operation is also known as file seek.
[Link] a file: Two steps are: Search the directory for the named-file. Release all file-space
and erase the directory-entry.
[Link] a file: The contents of a file are erased but its attributes remain unchanged.
Only file-length attribute is set to zero.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 25

OPERATING SYSTEMS MODULE 4

Differentiate between i.) shared lock and exclusive lock ii) Mandatory and advisory lock

Explain different common file types

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 26

OPERATING SYSTEMS MODULE 4

Explain different file accessing methods.

1. Sequential access 2. Direct access 3. Indexed access.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 27

OPERATING SYSTEMS MODULE 4

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 28

OPERATING SYSTEMS MODULE 4

DIRECTORY AND DISK STRUCTURE

Storage Structure
A storage-device can be used in its entirety for a file-system.
The storage-device can be split into 1 or more partitions (known as slices or minidisk). Any entity
containing a file-system is known as a volume. The volume may be a subset of a device or a
whole device. Each volume must also contain information about the files in the system. This
information is kept in entries in a device directory (or volume table of contents).
Device directory (or directory) records following information for all files on that volume as
shown in figure below:
 name
 location
 size and
 type.

Directory Overview
The various operations performed on a directory: 1) Search for a File : We need to be able to
search a directory-structure to find the entry for a particular file.
2) Create a File: We need to be able to create and add new files to the directory.
3) Delete a File: When a file is no longer needed, we want to be able to remove it from the
directory.
4) List a Directory: We need to be able to list the files in a directory and list the contents of the
directory-entry for each file.
5) Rename a File: Because the name of a file represents its contents to its users, we must be able
to change the name when the contents or use of the file changes.
6) Traverse the File-system: We may wish to access every directory and every file within a
directory-structure.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 29

OPERATING SYSTEMS MODULE 4

For reliability, it is a good idea to save the contents and structure of the entire file-system at
regular intervals.
Describe the methods used for implementing directories.
OR
******Explain various directory structures.
The various directory structures are:
1) Single level directory

2) Two level directory

3) Tree structured directories

4) Acyclic-graph directories

5) General graph directory

1. Single Level Directory

All files are contained in the same directory as shown in below figure.
Disadvantages: i) Naming problem: All files must have unique names.
ii) Grouping problem: Difficult to remember names of all files, as number of files increases.

Single-level directory
2. Two Level Directory
A separate directory for each user is maintained. Each user has his own UFD (user file directory).
The UFDs have similar structures. Each UFD lists only the files of a single user. When a user job
starts, the system's MFD is searched (MFD = master file directory). The MFD is indexed by user-
name. Each entry in MFD points to the UFD for that user as shown in below figure.

Two-level directory-structure

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 30

OPERATING SYSTEMS MODULE 4

To create a file for a user, the OS searches only that user's UFD to determine whether another file
of that name exists. To delete a file, the OS limits its search to the local UFD
Advantages: No filename-collision among different users and efficient searching.
Disadvantage: Users are isolated from one another and can‟t cooperate on the same task.
3. Tree Structured Directories
Users can create their own subdirectories and organize files as shown in below figure. A tree is
the most common directory-structure. The tree has a root directory. Every file in the system has a
unique path-name.

Tree-structured directory-structure

A directory contains a set of files (or subdirectories). A directory is simply another file, but it is
treated in a special way. In each directory-entry, one bit defines as file (0) or subdirectory (1).
Path-names can be of 2 types: Absolute path-name begins at the root. Relative path-name defines
a path from the current directory.
Advantage: Users can be allowed to access the files of other users.
Disadvantages: A path to a file can be longer than a path in a two-level directory. It prohibits the
sharing of files (or directories).

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 31

OPERATING SYSTEMS MODULE 4

4. Acyclic Graph Directories

The directories can share subdirectories and files as shown in below figure. (An acyclic graph
means a graph with no cycles). The same file (or subdirectory) may be in 2 different directories.
Only one shared-file exists, so any changes made by one person are immediately visible to the
other.

Acyclic-graph directory-structure

Two methods to implement shared-files (or subdirectories): [Link] a new directory-entry called
a link. A link is a pointer to another file (or subdirectory). 2. Duplicate all information’s about
shared-files in both sharing directories.
Two problems: A file may have multiple absolute path-names. Deletion may leave dangling-
pointers to the non-existent file. Solution to deletion problem: Use back pointers: Preserve the file
until all references to it are deleted.
With symbolic links, remove only the link, not the file. If the file itself is deleted, the link can be
removed.
5. General Graph Directory
If there are cycles in Acyclic directory then we want to avoid searching components twice as
shown in below figure. The solution is to limit the number of directories accessed in a search.
Also the problem with cycles, the reference-count may be non-zero even when it is no longer
possible to refer to a directory (or file). (A value of 0 in the reference count means that there are
no more references to the file or directory, and the file can be deleted). The solution to this
problem is Garbage-collection scheme can be used to determine when the last reference has been
deleted. Garbage collection involves: First pass: traverses the entire file-system and marks
everything that can be accessed.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 32

OPERATING SYSTEMS MODULE 4

A second pass collects everything that is not marked onto a list of free-space.

General graph directory

FILE MOUNTING
Briefly explain file mounting concept in operating system

A file-system must be mounted before it can be available to processes on the system. This is as
shown in below figure. Mount-point is the location in the file-structure where the file-system is to
be attached.

File system. (a) Existing system. (b) Unmounted volume

The file mounting procedure is as follows:

1) OS is given name of the device and mount-point as shown in below figure.
2) OS verifies that the device contains a valid file-system.
3) OS notes in its directory-structure that a file-system is mounted at specified mount-point.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 33

OPERATING SYSTEMS MODULE 4

Mount point

FILE SHARING
Sharing of files on multi-user systems is desirable. Sharing may be done through a protection
scheme. On distributed systems, files may be shared across a network. Network File-system
(NFS) is a common distributed file-sharing method.
Multiple Users:
File-sharing can be done in 2 ways: The system can allow a user to access the files of other users
by default or The system may require that a user specifically grant access.
To implement file-sharing, the system must maintain more file- & directory-attributes than on a
single-user system. Most systems use concepts of file owner and group.
Owner: The user who may change attributes & grant access and has the most control over the file
(or directory). Most systems implement owner attributes by managing a list of user-names and
user IDs
Group: The group attribute defines a subset of users who can share access to the file. Group
functionality can be implemented as a system-wide list of group-names and group IDs. Exactly
which operations can be executed by group-members and other users is definable by the file's
owner. The owner and group IDs of a file are stored with the other file-attributes and can be used
to allow/deny requested operations.
Remote File Systems:
It allows a computer to mount 1 or more file-systems from 1 or more remote-machines.
Three methods:
1. Manually via: programs like FTP.
2. Automatically DFS (Distributed file-system): remote directories are visible from a local
machine.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 34

OPERATING SYSTEMS MODULE 4

3. Semi-automatically via www (World Wide Web): A browser is needed to gain access to
the remote files, and separate operations (a wrapper for ftp) are used to transfer [Link]
is used for both anonymous and authenticated access. Anonymous access allows a user to
transfer files without having an account on the remote system.
Client Server Model
It allows clients to mount remote file-systems from servers. The machine containing the files is
called the server. The machine seeking access to the files is called the client. A server can serve
multiple clients, and A client can use multiple servers. The server specifies which resources (files)
are available to which clients. A client can be specified by a network-name such as an IP address.
Disadvantage: 1) Client identification is more difficult. In UNIX and its NFS (network file-
system), authentication takes place via the client networking information by default. Once the
remote file-system is mounted, file-operation requests are sent to the server via the DFS protocol.
Distributed Information Systems
It provides unified access to the information needed for remote computing. The DNS (domain
name system) provides hostname-to-network address translations. Other distributed information
systems provide username/password space for a distributed facility.
Failure Modes
Local file-systems can fail for a variety of reasons such as failure of disk (containing the file-
system) corruption of directory-structure & cable failure.
Remote file-systems have more failure modes because of the complexity of network-systems.
The network can be interrupted between 2 hosts. Such interruptions can result from hardware
failure poor hardware configuration or networking implementation issues.
DFS protocols allow delaying of file-system operations to remote-hosts, with the hope that the
remote-host will become available again. To implement failure-recovery, some kind of state
information may be maintained on both the client and the server.
Consistency Semantics
These represent an important criterion of evaluating file-systems that supports file-sharing. These
specify how multiple users of a system are to access a shared-file simultaneously. In particular,
they specify when modifications of data by one user will be observed by other users. These
semantics are typically implemented as code with the file-system.
These are directly related to the process-synchronization algorithms. A successful implementation
of complex sharing semantics can be found in the Andrew file-system (AFS).

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 35

OPERATING SYSTEMS MODULE 4

FILE PROTECTION
When information is stored in a computer system, we want to keep it safe from physical damage
(reliability) and improper access (protection). Reliability is generally provided by duplicate copies
of files.
Explain the various file protection methods

1. For a small single-user system, we might provide protection by physically removing the
floppy disks and locking them in a desk drawer. File owner/creator should be able to
control: what can be done by whom.
2. Protection mechanisms provide controlled access by limiting the types of file access that
can be made Read, write, execute, append, delete, list (name and attribute) Other
operations like renaming, copying and editing the file.

3. Associate password with each file. This scheme may be effective in limiting access to file.
Some systems associate password with subdirectory.

IMPLEMENTING FILE SYSTEM

Explain file implementation methods in operating system

On-disk & in-memory structures are used to implement a file-system in operating system.
On-disk structures shown in below figure include:
i. Boot Control Block: Contains information needed to boot an OS from the partition. It is
typically the first block of a volume. In UFS, it is called the boot block. In NTFS, it is
the partition boot sector.
ii. Partition Control Block: Contains partition-details like number of blocks, size of blocks
and free-block count. In UFS, this is called a superblock. In NTFS, it is stored in the
master file table.
iii. Directory-structure: Used to organize the files. In UFS, this includes file-names and
associated inode-numbers. In NTFS, it is stored in the master file table.
iv. FCB (file control block): Contains file-details including file-permissions, ownership, file-
size and location of data-blocks.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 36

OPERATING SYSTEMS MODULE 4

A typical file-control block

Explain the structure File control block (FCB)

Directory structure is used to organize the files. Per-file FCB contains many details about the file.

• To create a new file, application program calls the logical file system
• It allocates FCB
• The system then reads the appropriate directory structure to memory and updates it with
new file name and FCB, and writes it back to the disk
• When the process closes the file, per-process table entry is removed, and system-wide
entry’s open count is decremented.
In-Memory File System Structures may include:
i. In-memory Mount Table: Contains information about each mounted partition.
ii. An in-memory Directory-structure: Holds directory information of recently accessed
directories.
iii. System-wide Open-file Table: Contains a copy of the FCB of each open file
iv. Per-process Open-file Table: Contains a pointer to the appropriate entry in the system-
wide open-file table.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 37

OPERATING SYSTEMS MODULE 4

Buffers hold file-system blocks when they are being read from disk or written to disk. To create a
new file, a program calls the LFS (logical file-system). The „LFS‟ knows the format of the
directory-structures. To create a new file, the LFS
1) Allocates a new FCB.

2) Reads the appropriate directory into memory.

3) Updates LFS with the new file-name and FCB.

4) Writes LFS back to the disk

After a file has been created, it can be used for I/O.

1) First the file must be opened.
2) FCB is copied to a system-wide open-file table in memory.
3) An entry is made in the per-process open-file table, with a pointer to the entry in the
system-wide open-file table.
4) The open call returns a pointer to the appropriate entry in the per-process file-system table.
5) All file operations are then performed via this pointer.
6) When a process closes the file: The per-process table entry is [Link] system-wide
entry‟s open count is decremented.

In-memory file-system structures. (a) File open. (b) File read

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 38

OPERATING SYSTEMS MODULE 4

PARTITIONS & MOUNTING

Disk layouts can be: A disk can be divided into multiple partitions or A partition can span
multiple disks (RAID). Each partition can either be: Raw i.e. containing no file-system or
Cooked i.e: containing a file-system.
Boot information is a sequential series of blocks, loaded as an image into memory. Execution of
the image starts at a predefined location, such as the first byte. The boot information has its own
format, because at boot time the system does not have device-drivers loaded and the system
cannot interpret the file-system format.
Steps for mounting: The root partition containing the kernel is mounted at boot time. Then, the OS
verifies that the device contains a valid file-system. Finally, the OS notes in its in-memory mount
table structure that A file-system is mounted and Type of the file-system.
VIRTUAL FILE SYSTEMS
The OS allows multiple types of file-systems to be integrated into a directory-structure.
Three layersare:
1) File-system Interface: This is based on the open(), read(), writeO and closeO calls on file
descriptors.
2) File-system (VFS) Interface: This serves 2 functions: Separates file-system basic
operations from their implementation by defining a clean VFS [Link] VFS is based
on a file-representation structure called a vnode. vnode contains a numerical designator for
a network-wide unique file.
3) Local File-system:Local files are distinguished according to their file-system types.

Schematic view of a virtual file system

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 39

OPERATING SYSTEMS MODULE 4

DIRECTORY IMPLEMENTATION
1. Linear-list 2. Hash-table
Linear List
A linear-list of file-names has pointers to the data-blocks.
To create a new file: First search the directory to be sure that no existing file has the same name.
Then, add a new entry at the end of the directory.
To delete a file: Search the directory for the named-file and Then release the space allocated to the
file.
To reuse the directory-entry, there are 3 solutions: Mark the entry as unused (by assigning it a
special name). Attach the entry to a list of free directory entries. Copy the last entry in the
directory into the freed location & to decrease length of directory.
Problem: Finding a file requires a linear-search which is slow to execute.
Solutions: A cache can be used to store the most recently used directory information. A sorted list
allows a binary search and decreases search time.
Advantage: 1) Simple to program.
Disadvantage: 1) Time-consuming to execute.
Hash Table
A linear-list stores the directory-entries. In addition, a hash data-structure is also used.
The hash-table takes a value computed from the file name and returns a pointer to the file name
in the linear-list.
Advantages: Decrease the directory search-time. Insertion & deletion are easy.
Disadvantages: Some provision must be made for collisions i.e. a situation in which 2 file-names
hash to the same location. Fixed size of hash-table and the dependence of the hash function on
FILE ALLOCATION METHODS
The direct-access nature of disks allows us flexibility in the implementation of files. In almost
every case, many files are stored on the same disk.
Main problem: How to allocate space to the files so that disk-space is utilized effectively and files
can be accessed quickly. Three methods of allocating disk-space:
1. Contiguous
2. Linked
3. Indexed
Each method has advantages and disadvantages. Some systems support all three

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 40

OPERATING SYSTEMS MODULE 4

******Explain the various storage mechanisms available to store files, with neat diagram.

OR

*******Explain different file allocation methods

There are three file allocation methods for allocating disk-space:

1. Contiguous
2. Linked
3. Indexed
1. Contiguous Allocation
Each file occupies a set of contiguous-blocks on the disk as shown in below figure. Disk
addresses define a linear ordering on the disk. The number of disk seeks required for accessing
contiguously allocated files is minimal. Both sequential and direct access can be supported.
Problems: Finding space for a new file. External fragmentation can occur. Determining how
much space is needed for a file. If you allocate too little space, it can't be extended.
Two solutions:
The user-program can be terminated with an appropriate error-message. The user must then
allocate more space and run the program again.
Find a larger hole, copy the contents of the file to the new space and release the previous space.
To minimize these drawbacks: A contiguous chunk of space can be allocated initially and
Then when that amount is not large enough, another chunk of contiguous space is added.

Contiguous allocation of disk-space

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 41
OPERATING SYSTEMS MODULE 4

2. Linked Allocation
Each file is a linked-list of disk-blocks. The disk-blocks may be scattered anywhere on the disk.
The directory contains a pointer to the first and last blocks of the file as shown in below figure.
To create a new file, just create a new entry in the directory (each directory-entry has a pointer to
the disk-block of the file). A write to the file causes a free block to be found. This new block is
then written to and linked to the end of file (eof). A read to the file causes moving the pointers
from block to block.
Advantages: No external fragmentation, and any free block on the free-space list can be used to
satisfy a request. The size of the file doesn't need to be declared on creation. Not necessary to
compact disk-space.
Disadvantages: Can be used effectively only for sequential-access files. Space required for the
pointers.
Solution: Collect blocks into multiples (called „clusters‟) & allocate clusters rather than blocks.
Reliability: Problem occurs if a pointer is lost ( or damaged). Partial solutions: i) Use doubly
linked-lists. ii) Store file name and relative block-number in each block.

Linked allocation of disk-space File-allocation table

FAT is a variation on linked allocation (FAT=File Allocation Table). A section of disk at the
beginning of each partition is set aside to contain the table as shown in above figure. The table has
one entry for each disk-block and is indexed by block-number.
The directory-entry contains the block-number of the first block in the file. The table entry
indexed by that block-number then contains the block-number of the next block in the file.
This chain continues until the last block, which has a special end of file has the table entry.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 42

OPERATING SYSTEMS MODULE 4

Advantages:
i. Cache can be used to reduce the no. of disk head seeks.
ii. Improved access time, since the disk head can find the location of any block by reading
the information in the FAT.
3. Indexed Allocation
It solves the problems of linked allocation (without a FAT) by bringing all the pointers together
into an index block. Each file has its own index block, which is an array of disk-block addresses.
The ith entry in the index block points to the ith file block. The directory contains the address of the
index block.

Indexed allocation of disk space

When the file is created, all pointers in the index-block are set to nil. When writing the ith block, a
block is obtained from the free-space manager, and its address put in the ith index-block entry,
Problem: If the index block is too small, it will not be able to hold enough pointers for a large file,
Solution: Three mechanisms to deal with this problem:
Linked Scheme: To allow for large files, link several index blocks,
Multilevel Index: A first-level index block points to second-level ones, which in turn point to the
file blocks,
Combined Scheme: The first few pointers point to direct blocks (i.e. they contain addresses of
blocks that contain data of the file). The next few pointers point to indirect blocks.
Advantage:
1) Supports direct access, without external fragmentation,
Disadvantages: Suffer from wasted space, The pointer overhead of the index block is generally
greater than the pointer overhead of linked allocation. Suffer from performance problems.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 43

OPERATING SYSTEMS MODULE 4

Performance of file allocation methods

Contiguous Allocation
It requires only one access to get a disk-block. We can calculate immediately the disk address of
the next block and read it directly. It is good for direct access
Linked Allocation
It is good for sequential access. But it is not to be used for an application requiring direct access
Indexed Allocation
If the index block is already in memory, then the access can be made directly but keeping the
index block in memory requires considerable space.

FREE SPACE MANAGEMENT

**********What do you mean by free space list? With suitable example, explain any two
methods of implementation of free space list. OR
Explain how free space is managed?
A free-space list keeps track of all free disk-space. Free space list records all free disk blocks-
those not allocated to some file or directory.
To create a file, we search the free-space list for the required amount of space. Allocate that space
to the new file. This space is then removed from the free-space list. To delete a file, its disk-space
is added to the free-space list.
The various methods used in implementation of free space list:
1. Bit-vector
2. Linked list
3. Grouping
4. Counting
1. Bit Vector
The free-space list is implemented as a bit map /bit vector. Each block is represented by a bit.
If the block is free, the bit is [Link] the block is allocated, the bit is 0.
For example, consider a disk where blocks 2, 3, 4, 5 and 7 are free and the rest of the blocks
are allocated. The free-space bit map will be 00111101
Advantage: 1) Relative simplicity & efficiency in finding the first free block, or „n‟ consecutive
free blocks.
Disadvantages: Inefficient unless the entire vector is kept in main memory. The entire vector is
written to disc occasionally for recovery.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 44

OPERATING SYSTEMS MODULE 4

2. Linked List
The basic idea is Link together all the free disk-blocks as shown in below figure. Keep a pointer
to the first free block in a special location on the disk. Cache the block in memory. The first block
contains a pointer to the next free one, etc.
Disadvantage: 1) Not efficient, because to traverse the list, each block is read. Usually the OS
simply needs a free block, and uses the first one.

Linked free-space list on disk

3. Grouping
The addresses of n free blocks are stored in the 1st free block. The first n-1 of these blocks are
actually free. The last block contains addresses of another n free blocks, etc.
Advantage: Addresses of a large no of free blocks can be found quickly.
4. Counting
Takes advantage of the fact that, generally, several contiguous blocks may be allocated /freed
simultaneously. To Keep the address of the first free block and the number n of free contiguous
blocks that follow the first block. Each entry in the free-space list then consists of a disk address
and a count.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 45

 MODULE 5

Secondary storage structures, Protections: Mass storage structures; Disk structures;

Disk attachment; Disk scheduling; Disk management; Swap space management; Protection:

Principle of protection, Domain of protection, Access matrix, Implementation of access matrix,

Access control, Revocation of access rights, Capability based systems,

Case Study: The Linux operating system: Linux history; Design principles; Kernel modules;

Process management; Scheduling; memory management; File systems, Input and output; Inter-

process communication
OPERATING SYSTEMS MODULE 5

MASS-STORAGE STRUCTURE
Hard-Disks
With neat diagram briefly explain the structure of moving disk.
Hard-disks provide the bulk of secondary-storage for modern computer-systems as shown in figure.
Each disk-platter has a flat circular-shape, like a CD. The 2 surfaces of a platter are covered with a
magnetic material. Information is stored on the platters by recording magnetically.

Moving-head disk mechanism

A read/write head flies just above the surface of the platter. The heads are attached to a disk-arm that
moves all the heads as a unit. The surface of a platter is logically divided into circular tracks, which
are subdivided into sectors. The set of tracks that are at one arm position makes up a cylinder. There
may be thousands of concentric-cylinders in a disk-drive, and each track may contain hundreds of
sectors.
Disk-speed has 2 parts:
 The transfer-rate is the rate at which data flow between the drive and the computer.
 The positioning-time (or random-access time) consists of 2 parts:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 1

OPERATING SYSTEMS MODULE 5

a) Seek-time refers to the time necessary to move the disk-arm to the desired
cylinder.
b) Rotational-latency refers to the time necessary for the desired sector to rotate to
the disk-head.
A disk can be removable which allows different disks to be mounted as needed. A disk-drive is
attached to a computer by an I/O bus.
Different kinds of buses: Advanced technology attachment (ATA), Serial ATA (SATA), eSATA,
Universal serial bus (USB) and Fiber channel (FC).
SOLID-STATE DISKS
An SSD is non-volatile memory that is used like a hard-drive.
For example: DRAM with a battery to maintain its state in a power-failure through flash-memory
technologies.
Advantages compared to Hard-disks: More reliable: SSDs have no moving parts and are faster
because they have no seek-time or latency and Less power consumption.
Disadvantages: More expensive and Less capacity and so shorter life spans, so their uses are
somewhat limited.
Applications: One use for SSDs is in storage-arrays, where they hold file-system metadata that
require high performance. SSDs are also used in laptops to make them smaller, faster, and more
energy-efficient.
MAGNETIC TAPES
Magnetic tape was used as an early secondary-storage medium.
Advantages: It is relatively permanent and can hold large quantities of data.
Disadvantages: Its access time is slow compared with that of main memory and Hard-disk.
In addition, random access to magnetic tape is about a thousand times slower than random access to
Hard-disk, so tapes are not very useful for secondary-storage.
Applications: Tapes are used mainly for backup, for storage of infrequently used information.
Tapes are used as a medium for transferring information from one system to another.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 2

OPERATING SYSTEMS MODULE 5

DISK STRUCTURE
Modern Hard-disk-drives are addressed as large one-dimensional arrays of logical blocks. The
logical block is the smallest unit of transfer.
How one-dimensional array of logical blocks is mapped onto the sectors of the disk sequentially?
Sector 0 is the first sector of the first track on the outermost cylinder. The mapping proceeds in order
through that track, then through the rest of the tracks in that cylinder, and then through the rest of the
cylinders from outermost to innermost.
In practice, it is difficult to perform this mapping, for two reasons.
 Most disks have some defective sectors, but the mapping hides this by substituting spare
sectors from elsewhere on the disk.
 The number of sectors per track is not a constant on some drives.
DISK ATTACHMENT
Computers access disk storage in two ways.
 via I/O ports (or host-attached storage); this is common on small systems.
 via a remote host in a distributed file system; this is referred to as network-attached storage.
Host-Attached Storage
Host-attached storage is storage accessed through local I/O ports. These ports use several
technologies.
 The desktop PC uses an I/O bus architecture called IDE or [Link] architecture supports a
maximum of 2 drives per I/O bus.
 High-end workstations( and servers) use fibre channel (FC), a high-speed serial architecture
that can operate over optical fiber.
It has two variants:
 One is a large switched fabric having a 24-bit address space. This variant is the basis of
storage-area networks (SANs).
 The other FC variant is an arbitrated loop (FC-AL) that can address 126 devices.
A wide variety of storage devices are suitable for use as host-attached storage. For ex: Hard-disk-
drives, RAID arrays, and CD, DVD, and tape drives.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 3

OPERATING SYSTEMS MODULE 5

Network-Attached Storage

Network-attached storage
A network-attached storage (NAS) device is a special-purpose storage system that is accessed
remotely over a data network as shown in figure. Clients access NAS via a remote-procedure-call
interface such as NFS for UNIX systems and CIFS for Windows machines.
The remote procedure calls (RPCs) are carried via TCP or UDP over a local area network (LAN).
Usually, the same local area network (LAN) carries all data traffic to the clients. The NAS device is
usually implemented as a RAID array with software that implements the RPC interface.
Advantage: All computers on a LAN can share a pool of storage with the same ease of naming and
access local host-attached storage.
Disadvantages: NAS is less efficient and have lower performance than some direct-attached storage
options. The storage I/O operations consume bandwidth on the data network, thereby increasing the
latency of network communication.
iSCSI is the latest network-attached storage protocol. iSCSI uses the IP network protocol to carry
the SCSI protocol. Thus, networks rather than SCSI cables can be used as the interconnects between
hosts and their storage.
Storage-Area Network
A storage-area network (SAN) is a private network connecting servers and storage units as shown in
figure. The power of a SAN lies in its flexibility.
1. Multiple hosts and multiple storage-arrays can attach to the same SAN.
2. Storage can be dynamically allocated to hosts.
3. A SAN switch allows or prohibits access between the hosts and the storage.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 4

OPERATING SYSTEMS MODULE 5

4. SANs make it possible for clusters of servers to share the same storage and for storage arrays
to include multiple direct host connections.
5. SANs typically have more ports than storage-arrays.
FC is the most common SAN interconnect.
Another SAN interconnect is InfiniBand- a special-purpose bus architecture that provides hardware
and software support for high-speed interconnection networks for servers and storage units.

Storage-area network

DISK SCHEDULING
Explain in brief the selection of disk scheduling algorithm.

The selection of disk scheduling algorithm depends on

1. Access time = Seek-time + Rotational-latency
Seek-time: The seek-time is the time for the disk-arm to move the heads to the cylinder containing
the desired sector.
Rotational-latency: The Rotational-latency is the additional time for the disk to rotate the desired
sector to the disk-head.
2. The disk bandwidth is the total number of bytes transferred, divided by the total time
between the first request for service and the completion of the last transfer.
We can improve both the access time and the band width by managing the order in which the disk
I/O requests are serviced by selecting appropriate disk scheduling algorithms.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 5

OPERATING SYSTEMS MODULE 5

Whenever a process needs I/O to or from the disk, it issues a system call to the operating system.
The request specifies several pieces of information:
 Whether this operation is input or output
 What the disk address for the transfer is
 What the memory address for the transfer is
 What the number of sectors to be transferred is
If the desired disk-drive and controller are available, the request can be serviced immediately.
If the drive or controller is busy, any new requests for service will be placed in the queue of
pending requests for that drive.
For a multiprogramming system with many processes, the disk queue may often have several
pending requests. Thus, when one request is completed, the operating system chooses which
pending request to service next. Any one of several disk-scheduling algorithms can be used.
DISK SCHEDULING ALGORIHMS
*******What is disk scheduling? Explain different disk scheduling algorithms. (Any two)

In a multiprogramming system with many processes, the disk queue may often have several pending
disk requests. Thus, when one request is completed, the operating system chooses which
pending request to service next. This mechanism is called as disk scheduling.
The various disk scheduling methods are: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK
FCFS DISK SCHEDULING ALGORITHM: stands for First Come First [Link]
requests are serviced in the same order, as they are received. For example:

FCFS Disk Scheduling

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 6
OPERATING SYSTEMS MODULE 5

Starting with cylinder 53, the disk-head will first move from 53 to 98, then to 183, 37, 122, 14, 124,
65, and finally to 67 as shown in above figure.
Head movement from 53 to 98 = 45
Head movement from 98 to 183 = 85
Head movement from 183 to 37 = 146
Head movement from 37 to 122 =85
Head movement from 122 to 14 =108
Head movement from 14 to 124 =110
Head movement from 124 to 65 =59
Head movement from 65 to 67 = 2 Total head movement = 640
Advantage: This algorithm is simple & fair and no starvation of process requests.
Disadvantage: Generally, this algorithm does not provide the fastest service.
SSTF SCHEDULING
SSTF stands for Shortest Seek-time First. This selects the request with minimum seek-time from the
current head-position. Since seek-time increases with the number of cylinders traversed by head,
SSTF chooses the pending request closest to the current head-position.
Problem: Seek-time increases with the number of cylinders traversed by head.
Solution: To overcome this problem, SSTF chooses the pending request closest to the current head-
position. For example:

SSTF disk scheduling

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 7

OPERATING SYSTEMS MODULE 5

The closest request to the initial head position 53 is at cylinder 65. Once we are at cylinder 65, the
next closest request is at cylinder [Link] there, the request at cylinder 37 is closer than 98, so 37 is
served next. Continuing, we service the request at cylinder 14, then 98, 122, 124, and finally 183. It
is shown in above Figure.
Head movement from 53 to 65 = 12
Head movement from 65 to 67 = 2
Head movement from 67 to 37 = 30
Head movement from 37 to 14 =23
Head movement from 14 to 98 =84
Head movement from 98 to 122 =24
Head movement from 122 to 124 =2
Head movement from 124 to 183 = 59 Total head movement = 236
Advantage: SSTF is a substantial improvement over FCFS, it is not optimal.
Disadvantage: Essentially, SSTF is a form of SJF and it may cause starvation of some requests.
SCAN SCHEDULING
The SCAN algorithm is sometimes called the elevator algorithm, since the disk-arm behaves just
like an elevator in a building.
Here is how it works:
The disk-arm starts at one end of the disk. Then, the disk-arm moves towards the other end,
servicing the request as it reaches each cylinder. At the other end, the direction of the head
movement is reversed and servicing continues. The head continuously scans back and forth across
the disk. For example:

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 8

OPERATING SYSTEMS MODULE 5

Before applying SCAN algorithm, we need to know the current direction of head movement.
Assume that disk-arm is moving toward 0, the head will service 37 and then 14. At cylinder 0, the
arm will reverse and will move toward the other end of the disk, servicing the requests at 65,67,98,
122, 124, and 183. It is shown in above figure.
Head movement from 53 to 37 = 16
Head movement from 37 to 14 = 23
Head movement from 14 to 0 = 14
Head movement from 0 to 65 =65
Head movement from 65 to 67 =2
Head movement from 67 to 98 =31
Head movement from 98 to 122 =24
Head movement from 122 to 124 = 2
Head movement from 124 to 183 = 59
Total head movement = 236
Disadvantage: If a request arrives just in from of head, it will be serviced immediately.
On the other hand, if a request arrives just behind the head, it will have to wait until the arms reach
other end and reverses direction.
C-SCAN SCHEDULING
Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide a more uniform
wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing
requests along the way. When the head reaches the other end, however, it immediately returns to the
beginning of the disk, without servicing any requests on the return trip as shown in below figure.
The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps
around from the final cylinder to the first one.
Before applying C - SCAN algorithm, we need to know the current direction of head movement.
Assume that disk-arm is moving toward cylinder number 199, the head will service 65, 67, 98, 122,
124, 183. Then it will move to 199 and the arm will reverse and move towards 0.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 9

OPERATING SYSTEMS MODULE 5

While moving towards 0, it will not serve. But, after reaching 0, it will reverse again and then serve
14 and 37. It is as shown in below figure.

C-SCAN disk scheduling

Head movement from 53 to 65 = 12

Head movement from 65 to 67 = 2
Head movement from 67 to 98 = 31
Head movement from 98 to 122 =24
Head movement from 122 to 124 =2
Head movement from 124 to 183 =59
Head movement from 183 to 199 =16
Head movement from 199 to 0 = 199
Head movement from 0 to 14 = 14
Head movement from 14 to 37 = 23
Total head movement = 382

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 10

OPERATING SYSTEMS MODULE 5

LOOK SCHEDULING
SCAN algorithm, move the disk-arm across the full width of the disk. In practice, the SCAN
algorithm is not implemented in this way.
The arm goes only as far as the final request in each direction. Then, the arm reverses, without going
all the way to the end of the disk. This version of SCAN is called Look scheduling because they
look for a request before continuing to move in a given direction.
Example:

Look scheduling

Total head movement = (53 – 14) + (183 – 14) = 39 + 169 = 208

C-LOOK SCHEDULING
Circular LOOK (C-LOOK) scheduling is a variant of LOOK designed to provide a more uniform
wait time. Like LOOK, C-LOOK the head goes only as far as the final request in each direction.
Then, the arm reverses, without going all the way to the end of the disk. Now it moves the head
from one end of the disk to the other, without servicing any requests on the return trip. At the other
end, the direction of the head movement is reversed and servicing continues.
Assume that disk-arm is moving toward 199, the head will service 65, 67, 98, 122, 124, 183. Then
the arm will reverse and move towards 14. Then it will serve 37. It is as shown in below Figure

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 11

OPERATING SYSTEMS MODULE 5

C-LOOK disk scheduling

Head movement from 53 to 65 = 12

Head movement from 65 to 67 = 2
Head movement from 67 to 98 = 31
Head movement from 98 to 122 =24
Head movement from 122 to 124 =2
Head movement from 124 to 183 =59
Head movement from 183 to 14 = 169
Head movement from 14 to 37 = 23
Total head movement = 322

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 12

OPERATING SYSTEMS MODULE 5

EXERCISE PROBLEMS

Suppose that the disk-drive has 5000 cylinders numbered from 0 to 4999. The drive is
currently serving a request at cylinder 143, and the previous request was at cylinder 125. The
queue of pending requests in FIFO order is 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.
Starting from the current (location) head position, what is the total distance (in cylinders) that
the disk-arm moves to satisfy all the pending requests, for each of the following disk-
scheduling algorithms?
i. FCFS
ii. SSTF
iii. SCAN
iv. LOOK
v. C-SCAN
vi. C-LOOK

Solution:

i. FCFS

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 13

OPERATING SYSTEMS MODULE 5

For FCFS schedule, the total seek distance is 7081.

ii. SSTF

For SSTF schedule, the total seek distance is = (143-130) + (130-86) + (1774-86) = 1745.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 14

OPERATING SYSTEMS MODULE 5

iii, SCAN

For SCAN schedule, the total seek distance is = (4999- 143) + (4999 -86) = 9769

iv. C-SCAN

For C-SCAN schedule, the total seek distance is = (4999 – 143) + (4999 – 0)+(130-0) = 9985

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 15

OPERATING SYSTEMS MODULE 5

v. LOOK

For LOOK schedule, the total seek distance is = (1774 – 143) + (1774 – 86) = 3319.

vi. C-LOOK

For C- LOOK schedule, the total seek distance is = (1774 – 143) +(1774 -86) + (130-86) = 3363

1) Suppose that a disk has 50 cylinder named 0 to 49. The R/W head is currently serving at cylinder

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 16

OPERATING SYSTEMS MODULE 5

Suppose that a disk has 50 cylinders named 0 to 49. The R/W head is currently serving at
cylinder 15. The queue of pending request are in order: 4, 40, 11, 35, 7, 14 starting from the
current head position, what is the total distance traveled (in cylinders) by the disk-arm to
satisfy the request using algorithms
i. FCFS
ii. SSTF and
iii. LOOK.
Illustrate with figure in each case.

FCFS

Queue: 4, 40, 11, 35, 7, 14

Head starts at 15

For FCFS schedule, the total seek distance is 135

SSTF

Queue: 4, 40, 11, 35, 7, 14

Head starts at 15

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 17

OPERATING SYSTEMS MODULE 5

For SSTF schedule, the total seek distance is 47

LOOK
Queue: 4, 40, 11, 35, 7, 14
Head starts at 15

For LOOK schedule, the total seek distance is 47

Given the following queue 95, 180, 34, 119, 11, 123, 62, 64 with head initially at track 50 and
ending at track 199. Calculate the number moves using:
i. FCFS
ii. SSTF
iii. Elevator and
iv. C-look.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 18

OPERATING SYSTEMS MODULE 5

FCFS

For FCFS schedule, the total seek distance is 640

SSTF

For SSTF schedule, the total seek distance is 236

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 19

OPERATING SYSTEMS MODULE 5

Elevator (SCAN)

For Elevator (Scan) schedule, the total seek distance is 230

C-LOOK

For C-LOOK schedule, the total seek distance is = (50 – 11) + (180 – 11) + (180 -62) = 326

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 20

OPERATING SYSTEMS MODULE 5

DISK MANAGEMENT
The operating system is responsible for several other aspects of disk management. For example:
Disk initialization, Booting from disk and Bad-block recovery.
Disk Formatting: Usually, a new Hard-disk is in a blank slate: it is just a platter of a magnetic
recording material. Before a disk can store data, it must be divided into sectors that the disk
controller can read and write. This process is called low-level formatting, or physical formatting.
Low-level formatting fills the disk with a special data structure for each sector. The data structure
for a sector typically consists of a header, a data area (usually 512 bytes in size), and a trailer. The
header and trailer contain information used by the disk controller, such as sector number and error-
correcting code (ECC). Before a disk can store data, the operating system still needs to record its
own data structures on the disk. It does so in two steps.
 Partition the disk into one or more groups of cylinders.
 The operating system can treat each partition as a separate disk.
For example: one partition can hold a copy of the operating system’s executable code, another
partition can hold user files.
Logical formatting or creation of a file system: The operating system stores the initial file-system
data structures onto the disk. These data structures may include maps of free and allocated space and
an initial empty directory. To increase efficiency, most file systems group blocks together into larger
chunks, frequently called clusters. Disk I/O is done via blocks, File system I/O is done via clusters.
BOOT BLOCK
What are boot blocks? Explain.
For a computer to start running, it must have a bootstrap program to run. The Bootstrap program
initializes CPU registers, device controllers and the contents of main memory and then starts the
operating system. For most computers, the bootstrap is stored in read-only memory (ROM). To
change the bootstrap code, the ROM hardware chips has to be changed. To solve this problem, most
systems store a tiny bootstrap loader program in the boot-ROM. This loader program in ROM will
bring bootstrap program from disk. The full bootstrap program is stored in the form of boot blocks at
a fixed location on the disk. A disk that has a boot partition is called a boot disk or system disk.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 21

OPERATING SYSTEMS MODULE 5

In the boot-ROM, the code instructs the disk-controller to read the boot blocks into memory and
then starts executing that code.
BAD BLOCKS
What are bad blocks? Explain
Because disks have moving parts and small tolerances, they are prone to failure. Sometimes, the disk
needs to be replaced. The disk-contents need to be restored from backup media to the new disk. One
or more sectors may become defective. From the manufacturer, most disks have bad-blocks.
How to handle bad-blocks?
On simple disks, bad-blocks are handled manually.
One strategy is to scan the disk to find bad-blocks while the disk is being formatted. Any bad-blocks
that are discovered are flagged as unusable. Thus, the file system does not allocate them.
If blocks go bad during normal operation, a special program (such as Linux bad-blocks command)
must be run manually to search for the bad-blocks and to lock the bad-blocks. Usually, data that
resided on the bad-blocks are lost.
Bad blocks are recovered by using:
1. Sector sparing method 2. Sector slipping
The controller can be told to replace each bad sector logically with one of the spare sectors. This
scheme is known as sector sparing or forwarding
As an alternative to sector sparing some controllers can be instructed to replace a bad block by
sector slipping
Example: A typical bad-sector transaction might be as follows:
The operating system tries to read logical block 87. The controller calculates the ECC and finds that
the sector is bad. It reports this finding to the operating system. The next time the system is
rebooted, a special command is run to tell the controller to replace the bad sector with a spare. After
that, whenever the system requests logical block 87, the request is translated into the replacement
sector’s address by the controller.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 22

OPERATING SYSTEMS MODULE 5

SWAP SPACE MANAGEMENT

Swap-space management is a low-level task of the operating system. Virtual memory uses disk
space as an extension of main memory.
What is swap space management in OS? Explain

The main goal of swap space: to provide the best throughput for the virtual memory system.
Here, we discuss about 1) Swap space use 2) Swap space location.
Swap-Space Use: Swap space can be used in 2 ways.
 Swapping-Systems may use swap space to hold an entire process image, including the code
and data segments.
 Paging-systems may simply store pages that have been pushed out of main memory.
The amount of swap space needed on a system can therefore vary from a few megabytes of disk
space to gigabytes, depending on amount of physical memory, amount of virtual memory it is
backing, and way in which the virtual memory is used.
Swap-Space Location: A swap space can reside in one of two places:
1, The swap space can be a large file within the file system: Here, normal file-system routines can be
used to create it, name it, and allocate its space.
Advantage: This approach easy to implement,
Disadvantage: This approach is inefficient. This is because navigating the directory structure and the
disk structures takes time and extra disk accesses. External fragmentation can greatly increase
swapping times by forcing multiple seeks during reading or writing of a process image.
[Link] swap space can be in a separate raw (disk) partition: No file system or directory structure is
placed in the swap space. Rather, a separate swap-space storage manager is used to allocate and de-
allocate the blocks from the raw partition. This manager uses algorithms optimized for speed rather
than for storage efficiency, because swap space is accessed much more frequently than file system.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 23

OPERATING SYSTEMS MODULE 5

PROTECTION
Protection vs. Security Protection
 Protection controls access to the system-resources by Programs, Processes or Users.
 Protection ensures that only processes that have gained proper authorization from the OS can
operate on memory-segments, CPU and other resources.
 Protection must provide means for specifying the controls to be imposed, means of enforcing
the controls.
 Protection is an internal problem. Security, in contrast, must consider both the computer-
system and the environment within which the system is used.
Security
 Security ensures the authentication of system-users to protect integrity of the information
stored in the system (both data and code) physical resources of the computer-system.
 The security-system prevents unauthorized access malicious destruction alteration of data or
accidental introduction of inconsistency.
Goals of Protection
Explain the goals of protection
Operating system consists of a collection of objects, hardware or software. Each object has a unique
name and can be accessed through a well-defined set of operations.
Protection problem: ensure that each object is accessed correctly & only by those processes that are
allowed to do so.
Reasons for providing protection: To prevent mischievous violation of an access restriction. To
ensure that each program component active in a system uses system resources only in ways
consistent with policies.
Mechanisms are distinct from policies:
Mechanisms determine how something will be done. Policies decide what will be done. This
principle provides flexibility.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 24

OPERATING SYSTEMS MODULE 5

Principles of Protection
Explain the principles of protection
A key principle for protection is the principle of least privilege. Principle of Least Privilege:
Programs, users, and even systems are given just enough privileges to perform their tasks. The
principle of least privilege can help produce a more secure computing environment. An operating
system which follows the principle of least privilege implements its features, programs, system-
calls, and data structures. Thus, failure of a component results in minimum damage. An operating
system also provides system-calls and services that allow applications to be written with fine-
grained access controls.
Access Control provides mechanisms to enable privileges when they are needed, to disable
privileges when they are not needed. Audit-trails for all privileged function-access can be created.
Audit-trail can be used to trace all protection/security activities on the system.
The audit-trail can be used by Programmer, System administrator or Law-enforcement officer.
Managing users with the principle of least privilege requires creating a separate account for each
user, with just the privileges that the user needs. Computers implemented in a computing facility
under the principle of least privilege can be limited to running specific services, accessing specific
remote hosts via specific services accessing during specific times. Typically, these restrictions are
implemented through enabling or disabling each service and through using Access Control Lists.
DOMAIN OF PROTECTION
A process operates within a protection domain. Protection domain specifies the resources that the
process may access. Each domain defines set of objects and types of operations that may be invoked
on each object. The ability to execute an operation on an object is an access-right.
A domain is a collection of access-rights. The access-rights are an ordered pair <object-name, rights-
set>.
For example:
If domain D has the access-right <file F, {read, write}>; Then a process executing in domain D can
both read and write on file F. As shown in below Figure, domains may share access-rights. The
access-right <O4, {print}> is shared by D2 and D3.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 25

OPERATING SYSTEMS MODULE 5

System with three protection domains

The association between a process and a domain may be either static or dynamic.
If the association between processes and domains is static, then a mechanism must be available to
change the content of a domain. Static means the set of resources available to the process is fixed
throughout the process’s lifetime.
If the association between processes and domains is dynamic, then a mechanism is available to
allow domain switching. Domain switching allows the process to switch from one domain to
another. A domain can be realized in a variety of ways:
Each user may be a domain.
Each process may be a domain.
Each procedure may be a domain.
Domain Structure
A protection domain specifies the resources a process may access. A domain is a collection of
access rights, each of which is an ordered pair <object-name, rights-set>
Access right = the ability to execute an operation on an object. Access-right = <object-name, rights-
set> where rights-set is a subset of all valid operations that can be performed on the object.
Domains also define the types of operations that can be invoked.
The association between a process and a domain may be:
Static (if the process’ life-time resources are fixed): Violates the need-to-know principle
Dynamic: A process can switch from one domain to another.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 26

OPERATING SYSTEMS MODULE 5

A domain can be realized in several ways:

 Each user may be a domain
 Domain switching occurs when a user logs out.
 Each process may be a domain
 Domain switching occurs when a process sends a message to another process and waits for a
response
 Each procedure may be a domain
 Domain switching occurs when a procedure call is made
ACCESS MATRIX
Explain Access Matrix with an example.
Access-matrix provides mechanism for specifying a variety of policies. The access matrix is used to
implement policy decisions concerning protection. In the matrix, 1) Rows represent domains.2)
Columns represent objects. Each entry consists of a set of access-rights (such as read, write or
execute). In general, Access(i, j) is the set of operations that a process executing in Domaini can
invoke on Objectj
Example: Consider the access matrix shown in below [Link] are Four domains: D1, D2, D3,
and D4 and three objects: F1, F2 and F3
A process executing in domain D1 can read files F1 and F3.

Access matrix
i. OR

Explain access matrix with domain as an object.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 27

OPERATING SYSTEMS MODULE 5

Domain switching allows the process to switch from one domain to another. When we switch a
process from one domain to another, we are executing an operation (switch) on an object (the
domain).We can include domains in the matrix to control domain switching. Consider the access
matrix shown in Figure below: A process executing in domain D2 can switch to domain D3 or to
domain D4.

Access matrix with domains as objects

Explain the operation in access matrix with example for each: i. Copy ii. Transfer iii.
Limited copy
Allowing controlled change in the contents of the access-matrix entries requires 3 additional
operations as shown in below figure:
 Copy(*) denotes ability for one domain to copy the access right to another domain.
 Owner denotes the process executing in that domain can add/delete rights in that
column.
 Control in access (D2, D4) means: A process executing in domain D2 can modify row
D4.

Access matrix with Copy rights, Owner rights & Control rights

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 28

OPERATING SYSTEMS MODULE 5

IMPLEMENTATION OF ACCESS MATRIX

**********What is an access matrix? Explain the different methods of implementing access

matrix.

Access-matrix provides mechanism for specifying a variety of policies. The access matrix is used to
implement policy decisions concerning protection in an operating system. In the matrix, 1) Rows
represent domains.2) Columns represent objects. Each entry consists of a set of access-rights (such
as read, write or execute).
In general, Access(i, j) is the set of operations that a process executing in Domaini can invoke on
Objectj
The different methods of implementing access matrix are:
1. By using Global table
2. Access lists for objects
3. Capability lists for domains
4. A Lock-Key mechanism
Global Table
A global table consists of a set of ordered triples <domain, object, rights-set>. Whenever an
operation M is executed on an object Oj within domain Di, the global table is searched for a triple <
Di , Oj , Rk >, with M Є Rk. If this triple is found, Then, we allow the access operation;Otherwise,
access is denied, and an exception condition occurs.
Disadvantages: The table is usually large and can't be kept in main memory.
It is difficult to take advantage of groupings, e.g. if all may read an object, there must be an entry in
each domain.
Access Lists for Objects
In the access-matrix, each column can be implemented as an access-list for one object. Obviously,
the empty entries can be discarded. For each object, the access-list consists of ordered pairs
<domain, rights-set>.
Working : Whenever an operation M is executed on an object Oj within domain Di, the access list
is searched for a triple < Di , Rk >, with M Є Rk.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 29

OPERATING SYSTEMS MODULE 5

If this entry is found, Then, we allow the access operation; Otherwise, we check the default-set. If M
is in the default-set, we allow the access operation; Otherwise, access is denied, and an exception
condition occurs.
Advantages:
The strength is the control that comes from storing the access privileges along with each [Link]
allows the object to revoke or expand the access privileges in a localized manner.
Disadvantages:
The weakness is the overhead of checking whether the requesting domain appears on the access list.
This check would be expensive and needs to be performed every time the object is accessed.
Usually, the table is large & thus cannot be kept in main memory, so additional I/O is needed. It is
difficult to take advantage of special groupings of objects or domains.
Capability Lists for Domains
For a domain, a capability list is a list of objects & operations allowed on the objects. Often, an
object is represented by its physical name or address, called a capability. To execute operation M on
object Oj, the process executes the operation M, specifying the capability (or pointer) for object O j
as a parameter. The capability list is associated with a domain. But capability list is never directly
accessible by a process. Rather, the capability list is maintained by the OS & accessed by the user
only indirectly. Capabilities are distinguished from other data in two ways:
 Each object has a tag to denote whether it is a capability or accessible data.
 Program address space can be split into 2 parts. One part contains normal data, accessible to
the program. Another part contains the capability list, accessible only to the OS.
A Lock–Key Mechanism
The lock–key scheme is a compromise between 1) Access-lists and 2) Capability lists.
Each object has a list of unique bit patterns, called locks. Similarly, each domain has a list of unique
bit patterns, called keys. A process executing in a domain can access an object only if that domain
has a key that matches one of the locks of the object.

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 30

OPERATING SYSTEMS MODULE 5

ACCESS CONTROL
Protection can be applied to non-file resources as shown in below figure:
Solaris 10 provides role-based access control (RBAC) to implement least privilege. Privilege is right
to execute system call or use an option within a system call. Privilege can be assigned to processes.
Users assigned roles granting access to privileges and programs

Role-based access control in Solaris 10.

REVOCATION OF ACCESS RIGHTS

In a dynamic protection system, we may sometimes need to revoke access rights to objects shared
by different users.

*****Explain the various questioning that arise in revocation of access rights

Following questions about revocation may arise:
1. Immediate versus Delayed
Does revocation occur immediately, or is it delayed? If revocation is delayed, can we find out when
it will take place?

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 31

OPERATING SYSTEMS MODULE 5

2. Selective versus General

When an access right to an object is revoked, does it affect all the users who have an access right to
that object, or can we specify a select group of users whose access rights should be revoked?
3. Partial versus Total
Can a subset of the rights associated with an object be revoked, or must we revoke all access rights
for this object?
4. Temporary versus Permanent
Can access be revoked permanently (that is, the revoked access right will never again be available),
or can access be revoked and later be obtained again? Schemes that implement revocation for
capabilities include the following:
i. Reacquisition
 Periodically, capabilities are deleted from each domain.
 The process may then try to reacquire the capability.
ii. Back-Pointers
 A list of pointers is maintained with each object, pointing to all capabilities
associated with that object.
 When revocation is required, we can follow these pointers, changing the
capabilities as necessary
iii. Indirection
 Each capability points to a unique entry in a global table, which in turn points
to the object.
 We implement revocation by searching the global table for the desired entry
and deleting it.
iv. Keys
 A key is associated with each capability and can't be modified / inspected by
the process owning the capability
 Master key is associated with each object; can be defined or replaced with the
set-key operation

Athmaranjan K Dept. of ISE, Srinivas Institute of Technology Mangaluru Page 32

 MODULE 5 (CONT.): THE LINUX SYSTEM

5.13 Linux History

• Linux is a free OS-based on UNIX standards. (Linus + Unix= Linux)
• Linux is an open source software i.e. source-code is made available free on the Internet.
• Linux was first developed as a small self-contained kernel in 1991 by Linus Torvalds.
• Major design-goal of Linux project: UNIX-compatibility.
• In early days, Linux-development revolved largely around the central OS kernel.
• Kernel
→ manages all system-resources and
→ interacts directly with the computer-hardware.
• Linux-Kernel vs Linux-System:
1) Linux-Kernel is an original piece of software developed from scratch by Linux community
2) Linux-System includes a large no. of components, where
→ some components are written from scratch and
→ some components are borrowed from other development-projects and
• A Linux-Distribution includes
→ all the standard components of the Linux-System
→ set of administrative-tools to install/remove other packages on the system.

5.15.1 Linux Kernel

• Linux version 0.01 was released on
1991. Main features:
→ ran only on 80386-compatible Intel processors and PC hardware.
→ support for extremely limited device-driver.
→ support for only the Minix file-system.
• Linux 1.0 was released on
1994. Main features:
→ support for UNIX’s standard TCP/IP networking-protocols.
→ support for device-driver to run IP over an Ethernet.
→ support for a range of SCSI controllers for high-performance disk-access
• Linux 1.2 was released on
1995. Main features:
→ first PC-only Linux-Kernel
→ support for a new PCI hardware bus architecture.
 → support for dynamically loadable and unloadable kernel modules.
• Linux 2.0 was released on
1996. Main features:
→ support for multiple architectures.
→ support for symmetric multiprocessing (SMP).
→ support for the automatic loading of modules on-demand.
• Linux 2.2 was released on in
1999. Main features:
→ Networking was enhanced with i) firewall, ii) improved routing/traffic management
• Improvements continued with the release of Linux 2.4 and
2.6. Main features:
→ added journaling file-system.
→ support for pre-emptive kernel, 64-bit memory.
• Linux 3.0 was released in
2011. Main features:
→ support for improved virtualization.
→ facility for new page write-back
→ improvement to the memory-management system
5.15.2 Linux-System
• Linux uses many tools developed as part of
→ Berkeley’s BSD OS
→ MIT’s X Window-System and
→ Free Software Foundation’s GNU project.
• Main system-libraries are created by GNU project.
• Linux networking-administration tools are derived from 4.3BSD code.
• Linux-System is maintained by a many developers collaborating over the Internet.
• A small groups or individuals are responsible for maintaining the integrity of specific components.
• Linux community is responsible for maintaining the File-system Hierarchy Standard.
• This standard ensures compatibility across the various system-components.

5.15.3 Linux-Distributions
• Linux-Distributions include
→ system-installation and management utilities
→ ready-to-install packages of common UNIX tools (ex: text-processing, web browser).
• The first distributions managed these packages by simply providing a means of unpacking all the
files into the appropriate places.
• Early distributions included SLS and Slackware.
• RedHat and Debian are popular distributions from commercial and non-commercial sources,
respectively.
• RPM Package file format permits compatibility among the various Linux-Distributions.

5.15.4 Linux Licensing

• The Linux-Kernel is distributed under the GNU General Public License (GPL).
• Linux is not public-domain software.
• Public domain implies that the authors have waived copyright rights in the software.
• Linux is free software i.e. the people can copy it, modify it, use it.
• Anyone creating their own derivative of Linux, may not make the derived product proprietary.
• Software released under the GPL may not be redistributed as a binary-only product.
5.16 Design Principles
• Linux is a multiuser multitasking-system with a full set of UNIX-compatible tools.
• Linux’s file-system follows traditional UNIX semantics.
• The standard UNIX networking model is fully implemented.
• Main design-goals are speed, efficiency, and standardization
• Linux is designed to be compliant with the relevant POSIX documents; at least two Linux-
Distributions have achieved official POSIX certification.

Figure 5.14 Components of the Linux-System

5.16.1 Components of a Linux-System

• The Linux-System is composed of 3 main bodies of code (Figure 5.14):
1) Kernel
 The kernel is responsible for maintaining all the important abstractions of the OS.
 The abstractions include i) virtual-memory and ii) processes.
2) System-Libraries
 The system-libraries define a standard set of functions through which applications can
interact with the kernel.
 These functions implement much of the operating-system functionality that does not need
the full privileges of kernel-code.
 The most important system-library is the C library, known as libc.
 libc implements
→ user-mode side of the Linux-System-call interface, and
→ other critical system-level interfaces.
3) System Utilities
 The system utilities perform individual, specialized management tasks.
 Some system utilities are invoked just once to initialize and configure some aspect of the
 system.
 Other daemons run permanently, handling such tasks as
→ responding to incoming network connections
→ accepting logon requests from terminals, and
→ updating log files.
• The system can operate in 2 modes: 1) Kernel mode 2) User-mode.
Sr. No. Kernel Mode User-Mode
1 All the kernel-code executes in the Any operating-system-support code
processor’s privileged mode with full access that does not need to run in kernel
to all the physical resources of the mode is placed into the system-
computer. This privileged mode called as libraries and runs in user-mode.
kernel mode
2 No user code is built into the kernel. User-mode has access only to a
controlled
subset of the system’s resources.
5.17 Kernel Modules
• A kernel module can implement a device-driver, a file-system, or a networking protocol.
• The kernel’s module interface allows third parties to write and distribute, on their own terms,
device- drivers or file-systems that could not be distributed under the GPL.
• Kernel modules allow a Linux-System to be set up with a standard minimal kernel, without any
extra device-drivers built in.
• The module support has 3 components:
1) Module Management
2) Driver Registration
3) Conflict Resolution

5.17.1 Module Management

• Allows modules to be loaded into memory.
• Allows modules to communicate with the rest of the kernel.
• Module loading is split into 2 separate sections:
1) The management of sections of module code in kernel-memory.
2) The handling of symbols that modules are allowed to reference.
• Linux maintains an internal symbol table in the kernel.
• This symbol table
→ does not contain the full set of symbols defined in the kernel.
→ contains a set of symbol that must be explicitly exported.
• The set of exported symbols constitutes a well-defined interface by which a module can interact
with the kernel.
• The loading of the module is performed in two stages.
1) Module Loader Utility asks the kernel to reserve a continuous area of virtual kernel
memory for the module.
 The kernel returns the address of the memory allocated.
 The loader utility can use this address to relocate the module’s machine code to the correct
loading address.
2) Module Requestor manages loading requested, but currently unloaded, modules.
 It also regularly queries the kernel to see whether a dynamically loaded module is still in use.
 It will unload the module when it is no longer actively needed.

5.17.2 Driver Registration

• Allows modules to tell the rest of the kernel that a new driver has become available.
• The kernel
→ maintains dynamic tables of all known drivers and
→ provides a set of routines to allow drivers to be added to or removed from these tables
at any time.
• The kernel calls a module’s startup routine when that module is loaded.
The kernel calls the module’s cleanup routine before that module is unloaded.
• Registration tables include the following items:
1) Device-Drivers
 These drivers include character devices (such as printers, terminals, and mice), block
devices (including all disk drives), and network interface devices.
2) File-systems
 The file-system implements Linux’s virtual file-system-calling routines.
3) Network Protocols
 A module may implement an entire networking protocol, such as TCP or simply a new set
of packet-filtering rules for a network firewall.
4) Binary Format
 This format specifies a way of recognizing, loading, and executing a new type of
executable file.
5.17.3 Conflict Resolution
• Allows different device-drivers to
→ reserve hardware resources and
→ protect the resources from accidental use by another driver.
• Its aims are as follows:
1) To prevent modules from clashing over access to hardware resources.
2) To prevent autoprobes from interfering with existing device-drivers.
3) To resolve conflicts among multiple drivers trying to access the same hardware.

5.18 Process management

5.18.1 The fork() and exec() Process Model
• UNIX process management separates the creation of processes and the running of a new program
into two distinct operations.
• A new process is created by the fork() system-call. A new program is run after a call to exec().
• Process properties fall into 3 groups: 1) Process identity 2) Environment and 3) Context.

[Link] Process Identity

• A process identity consists mainly of the following items:
1) Process ID (PID)
• Each process has a unique identifier.
• The PID is used to specify the process to the OS when an application makes a system-call to signal,
modify, or wait for the process.
2) Credentials
• Each process must have an associated user ID and one or more group IDs that determine the rights
of a process to access system-resources and files.
3) Personality
• Each process has an associated personality identifier that can slightly modify the semantics of certain
system-calls.
• Personalities are primarily used by emulation libraries to request that system-calls be compatible
with certain varieties of UNIX.
4) Namespace
• Each process is associated with a specific view of the file-system hierarchy, called its namespace.
• Most processes share a common namespace & thus operate on a shared file-system hierarchy.
• However, processes and their children can have different namespaces.

[Link] Process Environment

• Process’s environment is inherited from its parent & is composed of 2 null-terminated vectors:
1) Argument vector simply lists the command-line arguments used to invoke the running program.
2) Environment vector is a list of ―NAME=VALUE‖ pairs that associates named environment
variables with arbitrary textual values.

[Link] Process Context

• Process context is the state of the running program at any one time; it changes constantly.
• Process context includes the following parts:
1) Scheduling Context
• Scheduling context refers to the info. scheduler needs to suspend & restart the process.
• This information includes saved copies of all the process’s registers.
• The scheduling context also includes information about
→ scheduling priority and
→ any outstanding signals waiting to be delivered to the process.
2) Accounting
• The kernel maintains accounting information about
→ resources currently being consumed by each process and
→ total resources consumed by the process in its entire lifetime.
3) File Table
• The file table is an array of pointers to kernel file structures representing open files.
• When making file-I/O system-calls, processes refer to files by a file descriptor(fd) that the kernel
uses to index into this table.
4) File-System Context
• File-system context includes the process’s root directory, current working directory, and namespace.
5) Signal-Handler Table
• The signal-handler table defines the action to take in response to a specific signal.
• Valid actions include ignoring the signal, terminating the process, and invoking a routine in the
process’s address-space.
6) Virtual-Memory Context
• Virtual-memory context describes the full contents of a process’s private address-space.
5.18.2 Processes and Threads
• Linux provides the ability to create threads via the clone() system-call.
• The clone() system-call behaves identically to fork(), except that it accepts as arguments a set of
flags.
• The flags dictate what resources are shared between the parent and child.

• The flags include:

• If clone() is passed the above flags, the parent and child tasks will share
→ same file-system information (such as the current working directory)
→ same memory space
→ same signal handlers and
→ same set of open files.
However, if none of these flags is set when clone() is invoked, the associated resources are not
shared
• A separate data-structures is used to hold information of process. Information includes:
→ file-system context
→ file-descriptor table
→ signal-handler table and
→ virtual-memory context
• The process data-structure contains pointers to these other structures.
• So any number of processes can easily share a sub-context by
→ pointing to the same sub-context and
→ incrementing a reference count.
• The arguments to the clone() system-call tell it
→ which sub-contexts to copy and
→ which sub-contexts to share.
• The new process is always given a new identity and a new scheduling context
5.19 Scheduling
• Scheduling is a process of allocating CPU-time to different tasks within an OS.
• Like all UNIX systems, Linux supports preemptive multitasking.
• In such a system, the process-scheduler decides which process runs and when.

5.19.1 Process Scheduling

• Linux uses 2 scheduling-algorithms:
1) A time-sharing algorithm for fair preemptive-scheduling between multiple processes.
2) A real-time algorithm where absolute priorities are more important than fairness.
• A scheduling-class defines which algorithm to apply
• The scheduler is a preemptive, priority-based algorithm with 2 separate priority ranges:
1) Real-time range from 0 to 99 and
2) Nice-value ranging from −20 to 19.
• Smaller nice-values indicate higher priorities.
• Thus, by increasing the nice-value, the priority is decreased and being ―nice‖ to the rest of the
system.
• Linux implements fair scheduling.
• All processes are allotted a proportion of the processor’s time.

5.19.2 Real-Time Scheduling

• Linux implements the two real-time scheduling-classes:
1) FCFS (First-Come, First Served) and
2) Round-robin.
• In both cases, each process has a priority in addition to its scheduling-class.
• The scheduler always runs the process with the highest priority.
• Among processes of equal priority, the scheduler runs the process that has longest waiting-time.
• Difference between FCFS and round-robin scheduling:
1) In FCFS, processes continue to run until they either exit or block.
2) In round-robin, process will be preempted after a while and moved to the end of the
scheduling-queue. Thus, processes of equal priority will automatically time-share among
themselves.
Kernel Synchronization
• Two ways of requesting for kernel-mode execution:
3) A running program may request an OS service, either
→ explicitly via a system-call or
→ implicitly when a page-fault occurs
4) A device-driver may deliver a hardware-interrupt.
The interrupt causes the CPU to start executing a kernel-defined handler.
• Two methods to protect critical-sections: 1) spinlocks and 2) semaphores.
1) Spinlocks are used in the kernel only when the lock is held for short-durations.
i) On SMP machines, spinlocks are the main locking mechanism used.
ii) On single-processor machines, spinlocks are not used, instead kernel pre-emption are

enabled and disabled.

2) Semaphores are used in the kernel only when a lock must be held for longer periods.
 The second protection technique applies to critical-sections that occur in ISR (interrupt
service routine).
 The basic tool is the processor’s interrupt-control hardware.
 By disabling interrupts during a critical-section, the kernel guarantees that it can proceed
without the risk of concurrent-access to shared data-structures.
• Kernel uses a synchronization architecture that allows long critical-sections to run for their entire
duration without interruption.
• ISRs are separated into a top half and a bottom half (Figure 5.15):
1) The top half is a normal ISR, and runs with recursive interrupts disabled.
2) The bottom half is run, with all interrupts enabled, by a miniature-scheduler that ensures
that bottom halves never interrupt themselves.
• This architecture is completed by a mechanism for disabling selected bottom halves while executing
normal, foreground kernel-code.
• Each level may be interrupted by code running at a higher level, but will never be interrupted by
code running at the same or a lower level.
• User-processes can always be preempted by another process when a time-sharing scheduling
interrupt occurs.
 Figure 5.15 Interrupt protection levels

5.19.3 Symmetric Multiprocessing (SMP)

• Linux 2.0 kernel was the first stable Linux-Kernel to support SMP hardware,
• Separate processes can execute in parallel on separate processors.
• In Linux 2.2, a single kernel spinlock (called BKL for ―big kernel lock‖) was created to allow
multiple processes to be active in the kernel concurrently.
• However, the BKL provided a very coarse level of locking granularity. This resulted in poor scalability.
• Linux 3.0 provided additional SMP enhancements such as
→ ever-finer locking
→ processor affinity and
→ load-balancing.
 Memory-Management
• Memory-management has 2 components:
1) The first component is used for allocating and freeing physical-memory such as
→ groups of pages and
→ small blocks of RAM.
2) The second component is used for handling virtual-memory.
A virtual-memory is a memory-mapped into the address-space of running processes.

5.20.1 Management of Physical-Memory

• The memory is divided into 3 different zones (Figure 5.16):
1) ZONE DMA
2) ZONE NORMAL
3) ZONE HIGHMEM

Figure 5.16 Relationship of zones and physical addresses in Intel x86-32.

• Page-allocator is used to
→ allocate and free all physical-pages.
→ allocate a ranges of physically-contiguous pages on-demand.
• Page-allocator uses a buddy-heap algorithm to keep track of available physical-pages (Figure 5.17).
• Each allocatable memory-region is paired with an adjacent partner (hence, the name buddy-heap).
1) When 2 allocated partners regions are freed up, they are combined to form a larger region
(called as a buddy heap).
2) Conversely, if a small memory-request cannot be satisfied by allocation of an existing small
free region, then a larger free region will be subdivided into two partners to satisfy the request.
• Memory allocations occur either
→ statically (drivers reserve a contiguous area of memory during system boot time) or
→ dynamically (via the page-allocator).
 Figure 5.17 Splitting of memory in the buddy system.

• Slab-allocator is another strategy for allocating kernel-memory.

• A slab is made up of one or more physically contiguous pages.
• A cache consists of one or more slabs.
• In Linux, a slab will be in one of 3 possible states:
1) Full: All objects in the slab are marked as used.
2) Empty: All objects in the slab are marked as free.
3) Partial: The slab consists of both used and free objects.
• The slab-allocator first attempts to satisfy the request with a free object in a partial slab(Figure 5.18)
1) If none exists, a free object is assigned from an empty slab.
2) If no empty slabs are available, a new slab is allocated from contiguous physical-pages and
assigned to a cache; memory for the object is allocated from this slab.

Figure 5.18 Slab-allocator in Linux.

Virtual-memory
• VM system
→ maintains the address-space visible to each process.
→ creates pages of virtual-memory on-demand and
→ loads those pages from disk & swaps them back out to disk as required.
• The VM manager maintains 2 separate views of a process’s address-space:
4) Logical-view and 2) Physical-view
1) Logical-Vew
• Logical-view of a address-space refers to a set of separate regions.
• The address-space consists of a set of non-overlapping regions.
• Each region represents a continuous, page-aligned subset of the address-space.
• The regions are linked into a balanced binary-tree to allow fast lookup of the region.
2) Physical-View
• Physical-view of a address-space refers to a set of pages.
• This view is stored in the hardware page-tables for the process.
• The page-table entries identify the exact current location of each page of virtual-memory.
• Each page of virtual-memory may be on disk or in physical-memory.
• A set of routines manages the Physical-view.
• The routines are invoked whenever a process tries to access a page that is not currently present in the
page-tables.

[Link] Virtual-Memory-Regions
• Virtual-memory-regions can be classified by backing-store.
• Backing-store defines from where the pages for the region come.
• Most memory-regions are backed either 1) by a file or 2) by nothing.
1) By Nothing
 Here, a region is backed by nothing.
 The region represents demand-zero memory.
 When a process reads a page in the memory, the process is returned a page-of-memory filled
with zeros.
2) By File
 A region backed by a file acts as a viewport onto a section of that file.
 When the process tries to access a page within that region, the page-table is filled with the
address of a page within the kernel’s page-cache.
 The same page of physical-memory is used by both the page-cache and the process’s page
 tables.
• A virtual-memory-region can also be classified by its reaction to writes. 1) Private or 2) Shared.
1) If a process writes to a private-region, then the pager detects that a copy-on-write is necessary
to keep the changes local to the process.
2) If a process writes to a shared-region, the object mapped is updated into that region.
 Thus, the change will be visible immediately to any other process that is mapping that object.

[Link] Lifetime of a Virtual Address-Space

• Under following 2 situations, the kernel creates a new virtual address-space:
1) When a process runs a new program with the exec() system-call.
 When a new program is executed, the process is given a new, completely empty virtual
address-space.
 It is up to the routines to populate the address-space with virtual-memory-regions.
2) When a new process is created by the fork() system-call.
 Here, a complete copy of the existing process’s virtual address-space is created.
 The parent’s page-tables are copied directly into the child’s page-tables.
 Thus, after the fork, the parent and child share the same physical-pages of memory in their
address-spaces.

.
[Link] Swapping and Paging
• A VM system relocates pages of memory from physical-memory out to disk when that memory is
needed.
• Paging refers to movement of individual pages of virtual-memory between physical-memory & disk.
• Paging-system is divided into 2 sections:
1) Policy algorithm decides
→ which pages to write out to disk and
→ when to write those pages.
2) Paging mechanism
→ carries out the transfer and
→ pages data back into physical-memory when they are needed again.
• Linux’s pageout policy uses a modified version of the standard clock algorithm.
• A multiple pass clock is used, and every page has an age that is adjusted on each pass of the clock.
• The age is a measure of the page’s youthfulness, or how much activity the page has seen recently.
• Frequently accessed pages will attain a higher age value, but the age of infrequently accessed pages
will drop toward zero with each pass. (LFU → least frequently used)
• This age valuing allows the pager to select pages to page out based on a LFU policy.
• The paging mechanism supports paging both to
1) dedicated swap devices and partitions and
2) normal files
• Blocks are allocated from the swap devices according to a bitmap of used blocks, which is
maintained in physical-memory at all times.
• The allocator uses a next-fit algorithm to try to write out pages to continuous runs of disk blocks for
improved performance.

[Link] Kernel Virtual-Memory

• Linux reserves a constant, architecture-dependent region of the virtual address-space of every
process for its own internal use.
• The page-table entries that map to these kernel pages are marked as protected.
• Thus, the pages are not visible or modifiable when the processor is running in user-mode.
• The kernel virtual-memory area contains two regions.
1) A static area contains page-table references to every available physical-page of memory in
the system.
 Thus, a simple translation from physical to virtual addresses occurs when kernel-code is run.
 The core of the kernel, along with all pages allocated by the normal page-allocator, resides
 in this region.
2) The remainder of the reserved section of address-space is not reserved for any specific
purpose.
 Page-table entries in this address range can be modified by the kernel to point to any other
areas of memory.

5.20.3 Execution and Loading of User Programs

• Linux
→ maintains a table of possible loader-functions
→ gives loader-function the opportunity to try loading the given file when an exec() system-
call is made.
• The registration of multiple loader routines allows Linux to support both the ELF and [Link] binary
formats.
• ELF has a number of advantages over [Link]:
1) Flexibility and extendability.
2) New sections can be added to ELF w/o causing the loader routines to become confused.
[Link] Mapping of Programs into Memory
• Initially, the pages of the binary-file are mapped into regions of virtual-memory.
• Only when a program tries to access a given page, a page-fault occurs.
• Page-fault results in loading the requested-page into physical-memory.
• An ELF-format binary-file consists of a header followed by several page-aligned sections.
• The ELF loader
→ reads the header and
→ maps the sections of the file into separate regions of virtual-memory.
• As shown in Figure 5.19
 Kernel VM is not accessible to normal user-mode programs.
 Job of loader: To set up the initial memory mapping to begin the execution of the program.
 The regions to be initialized include 1) stack and 2) program’s text/data regions.
 The stack is created at the top of the user-mode virtual-memory.
 The stack includes copies of the arguments given to the program.
 In the binary-file,
¤ Firstly, program-text or read-only data are mapped into a write-protected region.
¤ Then, writable initialized data are mapped.
¤ Then, any uninitialized data are mapped in as a private demand-zero region.
¤ Finally, we have a variable-sized region that programs can expand as needed to hold data
allocated at run time.

 Each process has a pointer brk that points to the current extent of this data region,
Figure 5.19 Memory layout for ELF programs

[Link] Static and Dynamic Linking

• A program is statically linked to its libraries if the necessary library-functions are embedded directly
in the program’s executable binary-file.
• Disadvantage of Static Linking:
Every program generated must contain copies of exactly the same common system-library functions.
• Advantage of Dynamic Linking:
Dynamic linking is more efficient in terms of both physical-memory and disk-space usage. This
is because the system-libraries are loaded into memory only once.
• Linux implements dynamic linking in user-mode through a special linker library.
• Every dynamically linked program contains a small, statically linked function that is called when the
program starts.
• This static function
→ maps the link library into memory and
→ runs the code that the function contains.
• The link library determines the dynamic libraries required by the program
5.21 File-Systems
5.21.1 Virtual File-System
• The Linux VFS is designed around object-oriented principles.
• It has two components:
1) A set of definitions that specify the file-system objects.
2) A layer of software to manipulate the objects.
• The VFS defines 4 main object types:
1) An inode object represents an individual file.
2) A file-object represents an open file.
3) A superblock object represents an entire file-system.
4) A dentry object represents an individual directory entry.
• For each object type, the VFS defines a set of operations.
• Each object contains a pointer to a function-table.
• The function-table lists the addresses of the actual functions that implement the defined operations for that
object.
• Example of file-object’s operations includes:
int open(. . .) — Open a file.
ssize t read(. . .) — Read from a file.
ssize t write(. . .) — Write to a file. int
mmap(. . .) — Memory-map a file.
• The complete definition of the file-object is located in the file /usr/include/linux/fs.h.
• An implementation of the file-object is required to implement each function specified in the definition of
the file-object.
• The VFS software layer can perform an operation on the file-objects by calling the appropriate
function from the object’s function-table.
• The VFS does not know whether an inode represents
→ networked file
→ disk file
→ network socket, or
→ directory file.
• The inode and file-objects are the mechanisms used to access files.
• An inode object is a data-structure containing pointers to the disk blocks that contain the actual file
contents.
• The inode also maintains standard information about each file, such as
→ owner
 → size and
→ time most recently modified.
• A file-object represents a point of access to the data in an open file.
• A process cannot access an inode’s contents without first obtaining a file-object pointing to the inode.
• The file-object keeps track of where in the file the process is currently reading/writing.
• File-objects typically belong to a single process, but inode objects do not.
• There is one file-object for every instance of an open file, but always only a single inode object.
• Directory files are dealt with slightly differently from other files.
• The UNIX programming interface defines a number of operations on directories, such as
→ creating file
→ deleting file and
→ renaming file.
5.21.2 Linux ext3 File-system
• Similar to BSD FFS, ext3 File-system locates the data blocks belonging to a specific file.
• The main differences between ext3 and FFS lie in their disk-allocation policies.
1) In FFS, the disk is allocated to files in blocks of 8 KB. (FFS → Fast File-system)
 The 8KB-blocks are further subdivided into fragments of 1 KB for storage of small files.
2) In ext3, fragments are not used.
 Allocations are performed in smaller units.
 Supported block sizes are 1, 2, 4, and 8 KB.
• ext3 uses allocation policies designed to place logically adjacent blocks of a file into physically
adjacent blocks on disk.
• Thus, ext3 can submit an I/O request for several disk blocks as a single operation.
• The allocation-policy works as follows (Figure 5.20):
 An ext3 file-system is divided into multiple segments. These are called block-groups.
 When allocating a file, ext3 first selects the block-group for that file.
 Within a block-group, ext3 keeps the allocations physically contiguous to reduce
fragmentation.
 ext3 maintains a bitmap of all free blocks in a block-group.
i) When allocating the first blocks for a new file, ext3 starts searching for a free block
from the beginning of the block-group.
ii) When extending a file, ext3 continues the search from the block most recently
allocated to the file. The search is performed in 2 stages:
1) First, ext3 searches for an entire free byte in the bitmap; if it fails to
find one, it looks for any free bit.
¤ The search for free bytes aims to allocate disk-space in chunks of at
least 8 blocks.
2) After a free block is found, the search is extended backward until an allocated
block is encountered.
¤ The backward extension prevents ext3 from leaving a hole.
 The preallocated blocks are returned to the free-space bitmap when the file is closed.
Figure 5.20 ext3 block-allocation policies.
5.21.3 Journaling
• ext3 file-system supports a popular feature called journaling.
• Here, modifications to the file-system are written sequentially to a journal.
• A set of operations that performs a specific task is a transaction.
• Once a transaction is written to the journal, it is considered to be committed.
• The journal entries relating to the transaction are replayed across the actual file-system structures.
• When an entire committed transaction is completed, it is removed from the journal.
• If the system crashes, some transactions may remain in the journal.
• If those transactions were never completed, then they must be completed once the system recovers.
• The only problem occurs when a transaction has been aborted i.e. it was not committed before the
system crashed.
• Any changes from those transactions that were applied to the file-system must be undone, again
preserving the consistency of the file-system.

5.21.4 Linux Process File-system (proc File-system)

• The proc file-system does not store data, rather, its contents are computed on demand according to
user file I/O requests.
• The /proc file-system must implement two things: a directory structure and the file contents within.
• proc must define a unique and persistent inode number for each directory and the associated files.
• proc uses this inode number to identify what operation is required when a user tries to
→ read from a particular file inode or
→ perform a lookup in a particular directory inode
• When data are read from these files, proc will collect the appropriate information, format it into
textual form, and place it into the requesting process’s read buffer.
• The kernel can allocate new /proc inode mappings dynamically, maintaining a bitmap of allocated
inode numbers.
• The kernel also maintains a tree data-structure of registered global /proc file-system entries.
• Each entry contains
→ file’s inode number
→ file name and
→ access permissions
→ special functions used to generate the file’s contents.
• Drivers can register and deregister entries in this tree at any time, and a special section of the tree is
reserved for kernel variables.
5.22 Input and Output
• Three types of devices (Figure 5.21): 1) Block device
2) Character device and
3) Network device.
1) Block Devices
• Block devices allow random access to completely independent, fixed-sized blocks of data.
• For example: hard disks and floppy disks, CD-ROMs and Blu-ray discs, and flash memory.
• Block devices are typically used to store file-systems.
2) Character Devices
• A character-device-driver does not offer random access to fixed blocks of data.
• For example: mice and keyboards.
• Character devices include mice and keyboards.
3) Network Devices
• Users cannot directly transfer data to network devices.
• Instead, they must communicate indirectly by opening a connection to the kernel’s
networking

subsystem.
Figure 5.21 Device-driver block structure.
5.22.1 Block Devices
• Block devices allow random access to completely independent, fixed-sized blocks of data.
• For example: hard disks and floppy disks, CD-ROMs and Blu-ray discs, and flash memory.
• Block devices are typically used to store file-systems.
• Block devices provide the main interface to all disk devices in a system.
• A block represents the unit with which the kernel performs I/O.
• When a block is read into memory, it is stored in a buffer.
• The request manager is the layer of software that manages the reading and writing of buffer
contents to and from a block-device-driver.
• A separate list of requests is kept for each block-device-driver.
• These requests are scheduled according to a C-SCAN algorithm.
• C-SCAN algorithm exploits the order in which requests are inserted in and removed from the lists.
• The request lists are maintained in sorted order of increasing starting-sector number.

5.22.2 Character Devices

• A character-device-driver does not offer random access to fixed blocks of data.
• For example: mice and keyboards.
• Difference between block and character devices:
i) block devices are accessed randomly, ii) character devices are accessed serially.
• A character device-driver must register a set of functions which implement the driver’s various
file
I/O operations
• The kernel performs almost no preprocessing of a file read or write request to a character device.
• The kernel simply passes the request to the device.
• The main exception to this rule is the special subset of character device-drivers which
implement terminal devices.
• The kernel maintains a standard interface to these drivers.
• A line discipline is an interpreter for the information from the terminal device.
• The most common line discipline is the tty discipline, which glues the terminal’s data stream
onto the standard input and output streams of a user’s running processes.
• This allows the processes to communicate directly with the user’s terminal.
5.23 Inter-Process Communication
• In some situations, one process needs to communicate with another process.
• Three methods for IPC:
1) Synchronization and Signals
2) Message Passing Data between Processes
3) Shared Memory Object

5.23.1 Synchronization and Signals

• Linux informs processes that an event has occurred via signals.
• Signals can be sent from any process to any other process.
• There are a limited number of signals, and they cannot carry information.
• Only the fact that a signal has occurred is available to a process.
• The kernel also generates signals internally.
• The Linux-Kernel does not use signals to communicate with processes running in
kernel mode. Rather, communication within the kernel is accomplished via
scheduling states and wait_queue structures.
• Whenever a process wants to wait for some event to complete, the process
→ places itself on a wait queue associated with that event and
→ tells the scheduler that it is no longer eligible for execution.
• Once the event has completed, every process on the wait queue will be awoken.
• This procedure allows multiple processes to wait for a single event.

5.23.2 Passing of Data among Processes

• The standard UNIX pipe mechanism allows a child process to inherit a
communication channel from its parent.
• Data written to one end of the pipe can be read at the other.
• Shared memory offers an extremely fast way to communicate large or small amounts of
data.
• Any data written by one process to a shared memory-region can be read
immediately by any other process.
• Main disadvantage of shared memory:
1) It offers no synchronization.
2) A process cannot
→ ask the OS whether a piece of shared memory has been written or
 → suspend execution until the data is written.
5.23.3 Shared Memory Object
• The shared-memory object acts as a backing-store for shared-memory-regions, just
as a file can act as a backing-store for a memory-mapped memory-region.
• Shared-memory mappings direct page-faults to map in pages from a persistent
shared memory object.
• Also, shared memory objects remember their contents even if no processes are
currently mapping
them into virtual-memory.