Subject Name: Operating System

Faculty Name: Prof. Rohit M.N

COURSE CONTENT

MODULE 1: Introduction to the operating system [ 11 HOURS]

Introduction: Computer System Organization, Architecture, Structure, Operations, Process

Management, Memory Management, Storage Management. Operating System Structures: Services,
System Calls, Types, Operating System Structure, System Boot. Processes: Process Concept,
Scheduling, Operations, Interprocess Communication. Multithreaded Programming: Multithreading
Models.

MODULE 2: Process Synchronization [12 HOURS]

Process Synchronization: The Critical-Section Problem, Peterson’s Solution, Synchronisation
Hardware, Mutex Locks, Semaphores, Classic Problems of Synchronization, Monitors,
Synchronization Examples. Process Scheduling: Criteria, Scheduling Algorithms, Multi-Processor
Scheduling, Real-time CPU Scheduling. Deadlocks: System model, Characterization, Methods for
handling deadlocks, Deadlock Prevention, Avoidance, Detection, and Recovery from deadlock.

MODULE 3: Memory Management Strategies [11 HOURS]

Memory Management Strategies: Background, Swapping, Contiguous Memory Allocation,
Segmentation, Paging, Structure of the Page Table. Virtual Memory Management: Demand Paging;
Copy-on-Write, Page Replacement; Allocation of Frames. File System: File Concept, Access Methods,
Directory and Disk Structure, Protection. File-System Implementation: Structure, File-System and
Directory Implementation, Allocation methods, Free Space Management. Mass-Storage Structure:
Overview, Disk Scheduling, Disk Management.

MODULE 4: Introduction to Linux Programming [11 HOURS]

Introduction to Linux Programming: Linux system Architecture, Linux Command format, Linux
Internal and External Commands, Directory Commands, File-related commands, Disk-related
commands, and General Utilities.
Text Book

1. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne; “Operating Systems Concepts”, 9th
Edition, 201 6 India, Wiley.
2. William Stallings, "Operating Systems and Design Principles", Pearson, thEdition,2018

Reference Books

1. D M Dhamdhere; operating systems - A concept Based Approach, 3'd Edition, Tata McGraw
- Hill.
2. Sumitabha Das: "I-INIX Concepts and Applications", 4th Edition, TataMcGraw Hill' 2006
3. MGVenkateshmurthy,"uNlXandShellProgramming", Pearson Edition Asia'2005

*****

*For Internal Circulation Only 1

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

TABLE OF CONTENT

[Link] PARTICULAR [Link]

Module 1 – Introduction
1 to Operating System 3 - 67

Module 2 - Process
2 68 - 91
Synchronization

Module 3 - Memory
3 91 - 157
Management Strategies

Module 4 - Introduction
4 158 - 165
to Linux Programming

*For Internal Circulation Only 2

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

UNIT - 1

INTRODUCTION TO OPERATING SYSTEM.

1. Introduction to Operating System.
2. Computer System Organization.
3. Process Management.
4. Memory Management.
5. Storage Management.
6. Operating System Structures: Services.
7. System Calls and its Types.
8. Operating System Structure.
9. System Boot.
10. Processes: Process Concept.
11. Scheduling and Operations.
12. Interprocess Communication.
13. Multithreading Models.

*For Internal Circulation Only 3

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

1. Introduction

An operating system (OS) is a program that interfaces the system hardware and the user.
Moreover, it handles all the interactions between the software and the hardware. A computer
system's workings depend on the OS at the base level. Further, it performs all the functions like
handling memory, processes, the interaction between hardware and software, etc. Now, let us look
at the functions of the operating system.

Operating System

Objectives of OS

The primary goals of an operating system are as follows:

1. Convenience – An operating system improves the use of a machine. Operating

systems enable users to get started on the things they wish to complete quickly
without having to cope with the stress of first configuring the system.

2. Efficiency – An operating system enables the efficient use of resources. This is due
to less time spent configuring the system.

*For Internal Circulation Only 4

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

3. Ability to evolve – An operating system should be designed in such a way that it

allows for the effective development, testing, and introduction of new features
without interfering with service.
4. Management of system resources – It guarantees that resources are shared fairly
among various processes and users.
Operating system services:

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

User interface: The operating system acts as an interface between the user and system hardware.
It makes it easy and convenient for users to access system resources with the help of different
interface mechanisms. UI, GUI, and CLI are the common ways of interacting with the system.

Program execution: Operating systems handle many kinds of activities from user programs to
system programs. The system must be able to load a program into memory and run that
program. The program must be able to end its execution, either normally or abnormally.
Provides a mechanism for process synchronization, process communication, and deadlock
handling.

1. Job Accounting – The operating system keeps track of all the functions of a computer
system. Hence, it makes a record of all the activities taking place on the system. It has
an account of all the information about the memory, resources, errors, etc. Therefore,
this information can be used as and when required.
2. I/O Operation

*For Internal Circulation Only 5

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

An I/O subsystem comprises I/O devices and their corresponding driver software. An
Operating System manages the communication between user and device drivers.
3. File system manipulation:
A file represents a collection of related information. Computers can store files on the
disk. Many operating systems provide a variety of file systems. The operating system
provides various activities for file management.
4. Communication
In the case of distributed systems which are a collection of processors that do not share
memory, peripheral devices, or a clock, the operating system manages communications
between all the processes. Multiple processes communicate with one another through
communication lines in the network.
5. Error handling
Errors can occur anytime and anywhere. An error may occur in the CPU, in I/O devices,
or in the memory hardware. OS constantly checks for possible errors and takes
appropriate action to ensure correct and consistent computing.
6. Resource Management
In the case of a multi-user or multi-tasking environment, resources such as main
memory, CPU cycles, and file storage are to be allocated to each user or job. The OS
manages all kinds of resources using schedulers.
7. Protection
It provides a mechanism or a way to control the access of programs, processes, or users
to the resources defined by a computer system. OS ensures that all access to system
resources is controlled.
Types of Operating System
1. Batch Operating System:
In this system, the OS does not forward the jobs/tasks directly to the CPU. It works by
grouping similar types of jobs under one category. Further, we name this group as a ‘batch’.
Hence, the name batch OS.

*For Internal Circulation Only 6

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages of Batch Operating System

• Simple scheduling used.
• Processors of the batch systems know how long the job would be when it is in the queue.
• Multiple users can share the batch systems.
• The idle time for the batch system is very less.
• It is easy to manage large work repeatedly in batch systems

Disadvantages of Batch Operating System

• The computer operators should be well known with batch systems.
• A job could enter infinite loop.
• Batch systems are hard to debug.
• It is sometimes costly.
• Lack of protection.
• The other jobs will have to wait for an unknown time if any job fails or slow I/O devives.

2. Multi-Programming Operating System

More than one program is present in the main memory and any one of them can be kept in
execution. This is basically used for better execution of resources. Multi programming &
multi-tasking concept used.

*For Internal Circulation Only 7

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages
• Multiple programs can be executed simultaneously.
• High and efficient CUP utilization
• Increases the Throughput of the System.
• It helps in reducing the response time.
Disadvantages
• There is not any facility for user interaction of system resources with the system.
• CPU scheduling is required.
• Many management is also required to handle many jobs.
• Synchronization and IPC mechanism is needed.

3. Time-Sharing Operating Systems:

Each task is given some time to execute so that all the tasks work smoothly. Each user gets
the time of the CPU. The time that each task gets to execute is called quantum. After this
time interval is over OS switches over to the next task.

Advantages
• Each task gets an equal opportunity.
• Provide user an interface to interact with system.

*For Internal Circulation Only 8

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• CPU idle time can be reduced.

• User get quick response.
• Resources can be shared.

Disadvantages
• More complex to implement.
• One must have to take care of the security and integrity of user programs and data.
• Reliability problem.
• Data communication problem.

4. Distributed Operating System

Various autonomous interconnected computers communicate with each other using a shared
communication network. Independent systems possess their own memory unit and CPU.
Remote access is enabled within the devices connected in that network.

Advantages
• Efficient resource sharing.
• Uses load balancing to share workload
• Reliability of the network
• Exchange of information through communication
• Maintain coordination among programs using IPC mechanism.
Disadvantages
• Complexity in implantation.
• Protection to shared resources is needed.
• Require memory and resource management.

5. Real-Time Operating System:

*For Internal Circulation Only 9

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Real-time systems are used when there are rigid time requirements needed for each
operations of a processor.
Ex: missile systems, air traffic control systems, robots, etc
• Types of Real-Time Operating Systems:
A. Hard Real-Time Systems
Hard Real-Time OSs are meant for applications where time constraints are very strict and
even the shortest possible delay is not acceptable.

B. Soft Real-Time Systems:

These OSs are for applications where time-constraint is less restrictive.
Advantages
• Maximum utilization of resources and systems.
• Memory management is less demanding.
• Improved CPU scheduling.
• Focus is on application and hence performance is high.
• Error or failure rate is very less.
Disadvantages
• Implementation cost is more
• Limited tasks will run at a time.
• Uses complex algorithms.

6. Network Operating System:

These systems run on a server and provide the capability to manage data, users, groups,
security, applications, and other networking functions. These types of operating systems
allow shared access to files, printers, security, applications, and other networking functions
over a small private network.

*For Internal Circulation Only 10

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages

• Highly stable centralized servers.

• Security concerns are handled through servers.
• New technologies and hardware up-gradation are easily integrated into the system.
• Server access is possible remotely from different locations and types of systems.
Disadvantages

• Servers are costly.

• User has to depend on a central location for most operations.
• Maintenance and updates are required regularly.

Functions of Operating System

1. Memory Management

It is the management of the main or primary memory. Whatever program is executed, it has to be
present in the main memory. Main memory is a quick storage area that may be accessed directly
by the CPU. When the program is completed, the memory region is released and can be used by
other programs. Therefore, there can be more than one program present at a time. Hence, it is
required to manage the memory.

The operating system:

• Allocates and deallocates the memory.

• Keeps a record of which part of primary memory is used by whom and how much.
• Distributes the memory while multiprocessing.

*For Internal Circulation Only 11

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• In multiprogramming, the operating system selects which processes acquire

memory when and how much memory they get.
2. Processor Management/Scheduling

Every software that runs on a computer, whether in the background or in the frontend, is a process.
Processor management is an execution unit in which a program operates. The operating system
determines the status of the processor and processes, selects a job and its processor, allocates the
processor to the process, and de-allocates the processor after the process is completed.

When more than one process runs on the system the OS decides how and when a process will use
the CPU. Hence, the name is also CPU Scheduling. The OS:

• Allocates and deallocates processor to the processes.

• Keeps record of CPU status.
Certain algorithms used for CPU scheduling are as follows:

• First Come First Serve (FCFS)

• Shortest Job First (SJF)
• Round-Robin Scheduling
• Priority-based scheduling etc.
Purpose of CPU scheduling

The purpose of CPU scheduling is as follows:

• Proper utilization of CPU. Since the proper utilization of the CPU is necessary.
Therefore, the OS makes sure that the CPU should be as busy as possible.
• Since every device should get a chance to use the processor. Hence, the OS makes
sure that the devices get fair processor time.
• Increasing the efficiency of the system.
3. Device Management

An operating system regulates device connection using drivers. The processes may require devices
for their use. This management is done by the OS. The OS:

• Allocates and deallocates devices to different processes.

• Keeps records of the devices.

*For Internal Circulation Only 12

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Decides which process can use which device for how much time.
4. File Management

The operating system manages resource allocation and de-allocation. It specifies which process
receives the file and for how long. It also keeps track of information, location, uses, status, and so
on. These groupings of resources are referred to as file systems. The files on a system are stored
in different directories. The OS:

• Keeps records of the status and locations of files.

• Allocates and deallocates resources.
• Decides who gets the resources.
5. Storage Management

• Storage management is a procedure that allows users to maximize the utilization of storage
devices while also protecting data integrity on whatever media on which it lives. Network
virtualization, replication, mirroring, security, compression,

deduplication, traffic analysis, process automation, storage provisioning, and memory

management are some of the features that may be included. The operating system is in charge of
storing and accessing files. The creation of files, the creation of directories, the reading and writing
of data from files and directories, as well as the copying of the contents of files and directories
from one location to another are all included in storage management.

The OS uses storage management for:

• Improving the performance of the data storage resources.

• It optimizes the use of various storage devices.
• Assists businesses in storing more data on existing hardware, speeding up the data
retrieval process, preventing data loss, meeting data retention regulations, and
lowering IT costs

*For Internal Circulation Only 13

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Functions of Operation System:

The various functions of the operating system are as follows:

1. Process Management:

Processor management is an execution unit in which a program operates. The operating system
determines the status of the processor and processes, selects a job and its processor, allocates
the processor to the process, and de-allocates the processor after the process is completed.

The OS is responsible for the following activities of process management.

• Creating & deleting both user & system processes.

• Suspending & resuming processes.

• Providing a mechanism for process synchronization.

• Providing a mechanism for process communication.

• Providing a mechanism for deadlock handling.

2. Main Memory Management:

It is the management of the main or primary memory. Whatever program is executed, it has to
be present in the main memory. Main memory is a quick storage area that may be accessed
directly by the CPU. There can be more than one program present at a time. Hence, it is required
to manage the memory.

The OS is responsible for the following activities in connection with memory management.

• Keeping track of which parts of memory are currently being used & by whom.

• Deciding which processes are to be loaded into memory when memory space becomes
available.

• Allocating &deallocating memory space as needed.

*For Internal Circulation Only 14

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

3. File Management:

File management is one of the most important components of an OS computer can store
information on several different types of physical media magnetic tape, magnetic disk & optical
disk are the most common media.

The OS is responsible for the following activities of file management.

• Creating & deleting files.

• Creating & deleting directories.

• Supporting primitives for manipulating files & directories.

• Mapping files into secondary storage.

• Backing up files on non-volatile media.

4. I/O System Management:

One of the purposes of an OS is to hide the peculiarities of specific hardware devices from the
user. For example, in UNIX the peculiarities of I/O devices are hidden from the bulk of the OS
itself by the I/O subsystem.

The I/O subsystem consists of:

• A memory management component that includes buffering, catching & spooling.

• A general device- driver interfaces drivers for specific hardware devices. Only the device

driver knows the peculiarities of the specific device to which it is assigned.

5. Secondary Storage Management:

The main purpose of a computer system is to execute programs. These programs with the data
they access must be in main memory during execution. The main memory is too small to
accommodate all data & programs & because the data that it holds are lost when power is lost.
The computer system must provide secondary storage to back up the main memory. Most
modern computer systems use disks as the storage medium to store data & programs.

*For Internal Circulation Only 15

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The operating system is responsible for the following activities of disk management.

• Free space management.

• Storage allocation.

• Disk scheduling

Because secondary storage is used frequently it must be used efficiently.

7. Networking:
A distributed system is a collection of processors that don’t share memory peripheral devices
or a clock. Each processor has its own local memory & clock and the processor communicate
with one another through various communication lines such as high speed buses or networks.
The processors in the system are connected through communication networks which are
configured in a number of different ways. The communication network design must consider
message routing & connection strategies are the problems of connection & security.

8. Protection or security:
If a computer system has multi users & allow the concurrent execution of multiple processes
then the various processes must be protected from one another’s activities. For that purpose,

mechanisms ensure that files, memory segments, CPU & other resources can be operated on
by only those processes that have gained proper authorization from the OS.

System Calls:
System calls provide the interface between a process & the OS. These are usually available in
the form of assembly language instruction. Some systems allow system calls to be made
directly from a high-level language program like C, BCPL PERL, etc. Systems calls occur in
different ways depending on the computer in use. System calls can be roughly grouped into 5
major categories.

*For Internal Circulation Only 16

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

1. Process Control:

• End, abort: A running program needs to be able to has its execution either normally
(end) or abnormally (abort).
• Load, execute: A process or job executing one program may want to load and executes
another program.
• Create Process, terminate process: There is a system call specifying for the purpose of
creating a new process or job (create process or submit job). We may want to terminate
a job or process that we created (terminates process, if we find that it is incorrect or no
longer needed).
• Get process attributes, set process attributes: If we create a new job or process we should
able to control its execution. This control requires the ability to determine & reset the
attributes of a job or processes (get process attributes, set process attributes).
2. File Manipulation:

• Create file, delete file: We first need to be able to create & delete files. Both the system
calls require the name of the file & some of its attributes.
• Open file, close file: Once the file is created, we need to open it & use it. We close the
file when we are no longer using it.
• Read, write, reposition file: After opening, we may also read, write or reposition the file
(rewind or skip to the end of the file).
• Get file attributes and set file attributes: We need to be able to determine the values of
various attributes for files or directories and reset them if necessary. Two system calls,
get file attributes and set file attributes, are required for this purpose.
3. Device Management:

• Request device, release device: If the system has multiple users, we first request the
device. After we finish using it, we must release it.
• Read, write, reposition: Once the device has been requested & allocated to us, we can
read, write & reposition the device.

*For Internal Circulation Only 17

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

4. Information maintenance:

• Get time or date, set time or date: Most systems have a system call to return the current
date & time or set the current date & time.
• Get system data, set system data: Other system calls may return information about the
system like number of current users, version number of OS, amount of free memory
etc.
• Get process attributes, set process attributes: The OS keeps information about all its
processes & there are system calls to access this information.
Communication:

There are two modes of communication such as:

• Message passing model: Information is exchanged through an inter-process communication

facility provided by the operating system. Each computer in a network has a name by which it
is known. Similarly, each process has a process name which is translated to an equivalent
identifier by which the OS can refer to it. The get hosted and processed systems calls to do this
translation. These identifiers are then passed to the general purpose open & close calls provided
by the file system or to specific open connection system calls. The recipient process must give
its permission for communication to take place with an accepted connection call. The source
of the communication known as the client & receiver known as the server exchange messages
by reading messages & writing message system calls. The close connection call terminates the
connection.

• Shared memory model: processes use map memory system calls to access regions of memory
owned by other processes. They exchange information by reading & writing data in the shared
areas. The processes ensure that they are not writing to the same location simultaneously.

*For Internal Circulation Only 18

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

OPERATING SYSTEM STRUCTURE:

The operating systems are large and complex. A common approach is to partition the task into
small components, or modules, rather than have one monolithic system. The structure of an
operating system can be defined the following structures.

• Simple structure

• Layered approach

• Microkernels

• Modules

• Hybrid systems

Simple structure:

The Simple structured operating systems do not have a well-defined structure. These systems
will be simple, small and limited systems.

Example: MS-DOS

o There are four layers that make up the MS-DOS operating system, and each has its own
set of features.
o These layers include ROM BIOS device drivers, MS-DOS device drivers, application
programs, and system programs.
o The MS-DOS operating system benefits from layering because each level can be
defined independently and, when necessary, can interact with one another.
o If the system is built in layers, it will be simpler to design, manage, and update. Because
of this, simple structures can be used to build constrained systems that are less complex.
o When a user program fails, the operating system as whole crashes.
o Because MS-DOS systems have a low level of abstraction, programs and I/O
procedures are visible to end users, giving them the potential for unwanted access.

*For Internal Circulation Only 19

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

MONOLITHIC STRUCTURE

The monolithic operating system controls all aspects of the operating system's operation,
including file management, memory management, device management, and operational
operations.

The core of an operating system for computers is called the kernel (OS). All other System
components are provided with fundamental services by the kernel. The operating system and
the hardware use it as their main interface. When an operating system is built into a single piece
of hardware, such as a keyboard or mouse, the kernel can directly access all of its resources.

The monolithic operating system is often referred to as the monolithic kernel. Multiple
programming techniques such as batch processing and time-sharing increase a processor's
usability. Working on top of the operating system and under the complete command of all
hardware, the monolithic kernel performs the role of a virtual computer. This is an old operating
system that was used in banks to carry out simple tasks like batch processing and time-sharing,
which allows numerous users at different terminals to access the Operating System.

*For Internal Circulation Only 20

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages of Monolithic Structure:

o Because layering is unnecessary and the kernel alone is responsible for managing all
operations, it is easy to design and execute.
o Because functions like memory management, file management, process scheduling,
etc., are implemented in the same address area, the monolithic kernel runs rather quickly
when compared to other systems. Utilizing the same address speeds up and reduces the
time required for address allocation for new processes.

Disadvantages of Monolithic Structure:

o The monolithic kernel's services are interconnected in address space and have an impact
on one another, so if any of them malfunctions, the entire system does as well.
o It is not adaptable. Therefore, launching a new service is difficult.

LAYERED STRUCTURE

The OS is separated into layers or levels in this kind of arrangement. Layer 0 (the lowest layer)
contains the hardware, and layer 1 (the highest layer) contains the user interface (layer N).
These layers are organized hierarchically, with the top-level layers making use of the
capabilities of the lower-level ones.

*For Internal Circulation Only 21

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The functionalities of each layer are separated in this method, and abstraction is also an option.
Because layered structures are hierarchical, debugging is simpler, therefore all lower-level
layers are debugged before the upper layer is examined. As a result, the present layer alone has
to be reviewed since all the lower layers have already been examined.

Advantages of Layered Structure:

o Work duties are separated since each layer has its functionality, and there is some
amount of abstraction.
o Debugging is simpler because the lower layers are examined first, followed by the top
layers.

Disadvantages of Layered Structure:

o Performance is compromised in layered structures due to layering.

o Construction of the layers requires careful design because the upper layers only make
use of the lower layers' capabilities.

*For Internal Circulation Only 22

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

MICRO-KERNEL STRUCTURE

The operating system is created using a micro-kernel framework that strips the kernel of any
unnecessary parts. Systems and user applications are used to implement these optional kernel
components. So, Micro-Kernels is the name given to these systems that have been developed.

Each Micro-Kernel is created separately and is kept apart from the others. As a result, the
system is now more trustworthy and secure. If one Micro-Kernel malfunctions, the remaining
operating system is unaffected and continues to function normally.

. Advantages of Micro-Kernel Structure:

o It enables portability of the operating system across platforms.

o Due to the isolation of each Micro-Kernel, it is reliable and secure.
o The reduced size of Micro-Kernels allows for successful testing.
o The remaining operating system remains unaffected and keeps running properly even
if a component or Micro-Kernel fails.

Disadvantages of Micro-Kernel Structure:

o The performance of the system is decreased by increased inter-module communication.

o The construction of a system is complicated.

*For Internal Circulation Only 23

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Process Concept
A process is a program in execution. The execution of a process must progress sequentially.

When a program is loaded into the memory and becomes a process, it can be divided into
four sections ─ stack, heap, text, and data. The following image shows a simplified layout
of a process inside the main memory.

S.N. Component & Description

1 Stack
The process Stack contains the temporary data such as method/function parameters, return
address and local variables.

2 Heap
This is dynamically allocated memory to a process during its run time.

3 Text
This includes the current activity represented by the value of the Program Counter and the
contents of the processor's registers.

4 Data

*For Internal Circulation Only 24

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

This section contains the global and static variables.

Process State:

• Processes may be in one of 5 states.

o New - The process is in the stage of being created.
o Ready - The process has all the resources available that it needs to run, but the
CPU is not currently working on this process's instructions.
o Running - The CPU is working on this process's instructions.
o Waiting - The process cannot run at the moment, because it is waiting for some
resource to become available or for some event to occur. For example the
process may be waiting for keyboard input, disk access request, inter-process
messages, a timer to go off, or a child process to finish.
o Terminated - The process has completed.

Process Control Block

For each process, there is a Process Control Block, PCB, which stores the following ( types of
) process-specific information, as illustrated in Figure 3.1. ( Specific details may vary from
system to system. )

*For Internal Circulation Only 25

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Process State - Running, waiting, etc., as discussed above.

• Process ID, and parent process ID.
• CPU registers and Program Counter - These need to be saved and restored when
swapping processes in and out of the CPU.
• CPU-Scheduling information - Such as priority information and pointers to scheduling
queues.
• Management information - E.g. page tables or segment tables.
• Accounting information - user and kernel CPU time consumed, account numbers,
limits, etc.
• I/O Status information - Devices allocated, open file tables, etc.

Context switch
• Context switching is a technique or method used by the operating system to switch a
process from one state to another to execute its function using CPUs in the system.
• It is a method to store/restore the state of a CPU in a PCB. So that process execution
can be resumed from the same point at a later time. The context-switching method is
important for multitasking OS.

*For Internal Circulation Only 26

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Process scheduling:
• It allows the OS to allocate a time interval of CPU execution for each process. Another
important reason for using a process scheduling system is that it keeps the CPU busy
all the time.
• This allows you to get the minimum response time for programs.
• Thread is a lightweight process that holds less number of resources. In multithreaded
OS a process can have single or many no. of threads.
• The objective of multiprogramming is to have some process running at all times, to
maximize CPU utilization.
• The objective of time sharing is to switch the CPU among processes so frequently that
users can interact with each program while it is running.

*For Internal Circulation Only 27

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Process Scheduling Queues:

• Process scheduler manages the scheduling of execution of all the processes with the
help of queues.
• Process Scheduling Queues help you to maintain a distinct queue for each and every
process state and PCB.
Three types of operating system queues are:

1. Job queue – It helps you to store all the processes in the system.
2. Ready queue – This type of queue helps you to set every process residing in the main
memory, which is ready and waiting to execute.
3. Device queues – It is a process that is blocked because of the absence of an I/O device.

Categories of Scheduling:

➢ Non-Preemptive Scheduling:
• In this scheduling, once the resources (CPU cycles) are allocated to a process, the
process holds the CPU till it gets terminated or reaches a waiting state. In the case of
non-preemptive scheduling does not interrupt a process running CPU in the middle
of the execution. Instead, the Process scheduler manages the scheduling of execution
of all the processes with the help of queues.

*For Internal Circulation Only 28

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Process Scheduling Queues help you to maintain a distinct queue for each and every
process state and PCBs.
Three types of operating system queues are:

4. Job queue – It helps you to store all the processes in the system.
5. Ready queue – This type of queue helps you to set every process residing in the main
memory, which is ready and waiting to execute.
6. Device queues – It is a process that is blocked because of the absence of an I/O device.

Categories of Scheduling:

➢ Non-Preemptive Scheduling:
• In this scheduling, once the resources (CPU cycles) are allocated to a process, the
process holds the CPU till it gets terminated or reaches a waiting state. In the case of
non-preemptive scheduling does not interrupt a process running CPU in the middle
of the execution. Instead, the Process scheduler manages the scheduling of execution
of all the processes with the help of queues.
• Process Scheduling Queues help you maintain a distinct queue for every process state
and PCB.
Three types of operating system queues are:

7. Job queue – It helps you to store all the processes in the system.

*For Internal Circulation Only 29

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

8. Ready queue – This type of queue helps you to set every process residing in the main
memory, which is ready and waiting to execute.
9. Device queues – It is a process that is blocked because of the absence of an I/O device.

Categories of Scheduling:

➢ Non-Preemptive Scheduling:
In this scheduling, once the resources (CPU cycles) are allocated to a process, the
process holds the CPU till it gets terminated or reaches a waiting state. In the case of
non-preemptive scheduling does not interrupt a process running CPU in the middle
of the execution. Instead, Implementation is difficult and high cost.

❑ Process Schedulers:
A scheduler is a type of system software that allows the OS to handle and monitor process
scheduling.
There are mainly three types of Process Schedulers:
✓ Long Term Scheduler
✓ Short Term Scheduler
✓ Medium Term Scheduler

*For Internal Circulation Only 30

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

1. Long-term scheduler (Job scheduler)

• It selects which processes should be brought into the ready queue.
• Long-term scheduler is invoked infrequently (seconds, minutes)  (may be slow)
• The long-term scheduler controls the degree of multiprogramming.
• Long-term scheduler should select a good process mix to improve performance
2. Short-term scheduler (or CPU scheduler) –
▪ It selects which process should be executed next and allocates CPU.
▪ Sometimes the only scheduler in a system.
▪ Short-term scheduler is invoked frequently (milliseconds)  (must be fast)
Processes can be described as either:

I/O-bound process – spends more time doing I/O than computations, many short CPU bursts

CPU-bound process – spends more time doing computations; few very long CPU bursts

3. Medium-term scheduler
• It can be added if degree of multiple programming needs to decrease
• Remove process from memory, store on disk, bring back in from disk to continue
execution: swapping

Process Scheduling

Definition

Process scheduling is the activity of the process manager that handles the removal of the
running process from the CPU and the selection of another process on the basis of a particular
strategy.

*For Internal Circulation Only 31

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Process scheduling is an essential part of a multiprogramming operating system.

• In multiprogramming operating systems allow more than one process to be loaded into
the executable memory at a time and the loaded process shares the CPU using time
multiplexing.
Scheduling Queues

As processes enter the system, they are put into a job queue, which consists of all processes in
the system.

• The processes that are residing in main memory and are ready and waiting to execute
are kept on a list called the ready queue.
• 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 includes a pointer field that points to the
next PCB in the ready queue.
• The system also includes other queues. When a process is allocated the CPU, it executes
for a while and eventually quits, is interrupted, or waits for the occurrence of a particular
event, such as the completion of an I/O request.
• Suppose the process makes an I/O request to a shared device, such as a disk. Since there
are many processes in the system, the disk may be busy with the I/O request of some other
process. The process therefore may have to wait for the disk.
• The list of processes waiting for a particular I/O device is called a device queue. Each
device has its own device queue as shown in the below figure.

Note:

• UNIX OS a new process is created by the fork() system call.

• The exec() system call loads a binary file into memory.

• The wait() system call to move itself off the ready queue until the termination of the
child.
• The parent process resumes fromthe call to wait(), where it completes using the exit()
system call.

*For Internal Circulation Only 32

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Below figure shows process creation using above mentioned system calls.

Process Termination

• A process terminates when it finishes executing its final statement and asks the
operating system to delete it by using the exit() system call.

• At that point, the process may return a status value (typically an integer) to its parent
process (via the wait() system call).
• All the resources of the process—including physical and virtual memory, open files,
and I/O buffers—are deallocated by the operating system.
Termination can occur in other circumstances as well. A process can cause the termination of
another process via an appropriate system call.

• Usually, such a system call can be invoked only by the parent of the process that is to
be terminated. Otherwise, users could arbitrarily kill each other’s jobs. Note that a parent
needs to know the identities of its children if it is to terminate them.
• Thus, when one process creates a new process, the identity of the newly created process
is passed to the parent.
• A parent may terminate the execution of one of its children for a variety of reasons,
such as these

*For Internal Circulation Only 33

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The child has exceeded its usage of some of the resources that it has been allocated. (To
determine whether this has occurred, the parent must have a mechanism to inspect the state
of its children.)
• The task assigned to the child is no longer required.
• The parent is exiting, and the operating system does not allow a child to continue if its
parent terminates.
Cascading termination

Some systems do not allow a child to exist if its parent has terminated. In such systems, if a
process terminates (either normally or abnormally), then all its children must also be terminated
and this phenomenon, referred to as cascading termination, is normally initiated by the
operating system.

Zombie process

A process that has terminated, but whose parent has not yet called wait(), is known as a zombie
process. When the child process becomes orphans then OS addresses the issue by assigning the
in it process as the new parent to orphan processes.

Interprocess Communication

• Processes executing concurrently in the operating system may be either

independent processes or cooperating processes.

A process is independent if it cannot affect or be affected by the other processes

executing in the system.
Any process that does not share data with any other process is independent.
A process is cooperating if it can affect or be affected by the other processes executing
in the system. Clearly, any process that shares data with other processes is a cooperating
process.
There are several reasons for providing an environment that allows process cooperation

• Information sharing.

*For Internal Circulation Only 34

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Since several users may be interested in the same piece of information (for
instance, a shared file), we must provide an environment to allow concurrent access to
such information.
• Computation speedup.
• If we want a particular task to run faster, we must break it into subtasks, each of
which will be executing in parallel with the others. Notice that such a speedup can be
achieved only if the computer has multiple processing cores.
• Modularity.
• We may want to construct the system in a modular fashion, dividing the system
functions into separate processes or threads.
• Convenience.
• Even an individual user may work on many tasks at the same time. For instance,
a user may be editing, listening to music, and compiling in parallel.

• There are two fundamental models of interprocess communication: shared

memory and message passing.
• In the shared-memory model, a region of memory that is shared by cooperating
processes is established. Processes can then exchange information by reading and
writing data to the shared region.
• In the message-passing model, communication takes place by means of
messages exchanged between the cooperating processes.
• The two communications models are contrasted in below figures, figure a
illustrate Message passing and figure b Shared memory.

*For Internal Circulation Only 35

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Shared-Memory Systems

• Interprocess communication using shared memory requires communicating processes

to establish a region of shared memory.

• Typically, a shared-memory region resides in the address space of the process creating
the shared-memory segment.
• Other processes that wish to communicate using this shared-memory segment must
attach it to their address space.
• Normally, the operating system tries to prevent one process from accessing another
process’s memory.
• Shared memory requires that two or more processes agree to remove this restriction.
• They can then exchange information by reading and writing data in the shared areas.
The form of the data and the location are determined by these processes and are not under
the operating system’s control.
• The processes are also responsible for ensuring that they are not writing to the same
location simultaneously.

*For Internal Circulation Only 36

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• To illustrate the concept of cooperating processes, let’s consider the producer–consumer

problem, which is a common paradigm for cooperating processes.
• A producer process produces information that is consumed by a consumer process.
Sometimes producer consumer problem results in issues like try to consume the usage of not
produced items.

• One solution to the producer–consumer problem uses shared memory.

• To allow producer and consumer processes to run concurrently, we must have available
a buffer of items that can be filled by the producer and emptied by the consumer. This buffer
will reside in a region of memory that is shared by the producer and consumer processes.
A producer can produce one item while the consumer is consuming another item. The
producer and consumer must be synchronized, so that the consumer does not try to consume
an item that has not yet been produced.
• Two types of buffers can be used. The unbounded buffer places no practical limit on
the size of the buffer. The consumer may have to wait for new items, but the producer can
always produce new items. The bounded buffer assumes a fixed buffer size. In this case,
the consumer must wait if the buffer is empty,and the producer must wait if the buffer is
full.
Message-Passing Systems

• Message passing provides a mechanism to allow processes to communicate and to

synchronize their actions without sharing the same address space.
• It is particularly useful in a distributed environment, where the communicating
processes may reside on different computers connected by a network.
• A message-passing facility provides at least two operations:
• send(message)
• receive(message)
• If processes P and Q want to communicate, they must send messages to and receive
messages from each other: a communication link must exist between them.

• This link can be implemented in a variety of ways.

• Direct or indirect communication

*For Internal Circulation Only 37

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Synchronous or asynchronous communication

• Automatic or explicit buffering
Naming

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

• They can use either direct or indirect communication.

• Under direct communication, each process that wants to communicate must explicitly
name the recipient or sender of the communication.
• In this scheme, the send() and receive() primitives are defined as below • send(P,
message)—Send a message to process P.
• receive(Q, message)—Receive a message from process Q.
• In indirect communication, the messages are sent to and received from mailboxes, or
ports.

Synchronization

• Communication between processes takes place through calls to send() and receive()
primitives.
• There are different design options for implementing each primitive. Message passing
may be either blocking or non-blocking also known as synchronous and asynchronous.
• Blocking send. The sending process is blocked until the message is received by the
receiving process or by the mailbox.
• Non-blocking send. The sending process sends the message and resumes operation.
• Blocking receive. The receiver blocks until a message is available.
• Non-blocking receive. The receiver retrieves either a valid message or a null.
Buffering

• Whether communication is direct or indirect, messages exchanged by communicating

processes reside in a temporary queue.
• Basically, such queues can be implemented in three ways
• Zero capacity.

*For Internal Circulation Only 38

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The queue has a maximum length of zero; thus, the link cannot have any messages waiting
in it. In this case, the sender must block until the recipient receives the message.

• Bounded capacity.

The queue has a finite length of n; thus, at most n messages can reside in it. If the queue is not
full when a new message is sent, the message is placed in the queue (either the message is
copied or a pointer to the message is kept), and the sender can continue execution without
waiting. The link’s capacity is finite, however. If the link is full, the sender must block until
space is available in the queue.

• Unbounded capacity. The queue’s length is potentially infinite; thus, any number of
messages can wait in it and the sender never blocks. The process could be removed forcibly
from the CPU, as a result of an interrupt, and be 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 deallocated.
Schedulers

Schedulers are special system software that handles process scheduling in various ways. Their
main task is to select the jobs to be submitted into the system and to decide which process to
run.

• 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. The selection process is carried out by the appropriate scheduler.
Schedulers are of three types as below

• Long-Term Scheduler

• Short-Term Scheduler
• Medium-Term Scheduler

*For Internal Circulation Only 39

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Degree of multiprogramming

The degree of multiprogramming describes the maximum number of processes that a single
processor system can accommodate efficiently. The primary factor affecting the degree of
multiprogramming is the amount of memory available to be allocated to executing processes.

• In general, most processes can be described as either I/O bound or CPU bound.
• An I/O-bound process spends more of its time doing I/O than it spends doing
computations.
• A CPU-bound process, in contrast, generates I/O requests infrequently, using more of
its time doing computations.
Comparison among Scheduler

Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler

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

scheduler.

Speed is lesser than short- Speed is the fastest Speed is in between both
term scheduler among the other two short and long-term
schedulers.

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

multiprogramming over the degree of multiprogramming.
multiprogramming

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

minimal in the sharing sharing system systems.
system

It selects processes from the It can re-introduce the

It selects those processes
pool and loads them into process into memory and
that are ready to execute
memory for execution execution can be continued.

*For Internal Circulation Only 40

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

This medium-term scheduler is diagrammed in below figure.

• The key idea behind a medium-term scheduler is that sometimes it can be advantageous
to remove a process from memory (and from active contention for the CPU) and thus reduce
the degree of multiprogramming. Later, the process can be reintroduced into memory, and
its execution can be continued where it left off and this scheme is called swapping.

Context switching

• Context switching is the procedure of storing the state of an active process for the CPU
when it has to start executing a new one.

• Context switches are resource-intensive and most operating system designers try to
reduce the need for a context switch. They can be software or hardware governed depending
upon the CPU architecture.
• Context switches can relate to either a process switch, a thread switch within a process,
or a register switch. The major need for a context switch arises when CPU has to switch
between user mode and kernel mode but some OS designs may obviate it.
Ex: Process A with its address space and stack is currently being executed by the CPU and
there is a system call to jump to a higher priority process B; the CPU needs to remember the
current state of process A so that it can suspend its operation, begin executing the new process
B and when done, return to its previously executing process A.

*For Internal Circulation Only 41

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Operations on Processes

The processes in most systems can execute concurrently, and they may be created and deleted
dynamically.

Process Creation

• During the course of execution, a process may create several new processes. As
mentioned earlier, the creating process is called a parent process, and the new processes
are called the children of that process.

• Each of these new processes may in turn create other processes, forming a tree of
processes.
• Most operating systems (including UNIX, Linux, and Windows) identify processes
according to a unique process identifier (or pid), which is typically an integer number.
• The pid provides a unique value for each process in the system, and it can be used as
an index to access various attributes of a process within the kernel.
• Below figure illustrates a typical process tree for the Linux operating system, showing
the name of each process and its pid.

In general, when a process creates a child process, that child process will need certain resources
(CPU time, memory, files, I/O devices) to accomplish its task.

*For Internal Circulation Only 42

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• When a process creates a new process, two possibilities for execution exist
• The parent continues to execute concurrently with its children.
• The parent waits until some or all of its children have terminated.
• There are also two address-space possibilities for the new process
• The child process is a duplicate of the parent process (it has the same program and data
as the parent).
• The child process has a new program loaded into it.
Thread

• A thread is a lightweight process.

• Threads provide a way to improve application performance through parallelism.

• Threads represent a software approach to improving performance of operating system
by reducing the overhead thread is equivalent to a classical process.
• A thread is a basic unit of CPU utilization; it comprises a thread ID, a program • counter,
a register set, and a stack.
• It shares with other threads belonging to the same process its code section, data section,
and other operating-system resources, such as open files and signals. A traditional (or
heavyweight) process has a single thread of control.
• If a process has multiple threads of control, it can perform more than one task at a time.
Below figure illustrates the difference between a traditional single-threaded process and a
multithreaded process.

*For Internal Circulation Only 43

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Benefits of multithreaded programming

The benefits of multithreaded programming can be broken down into four major categories

• Responsiveness
• Multithreading an interactive application may allow a program to continue
running even if part of it is blocked or is performing a lengthy operation, thereby
increasing responsiveness to the user.
• This quality is especially useful in designing user interfaces.
• Resource sharing
• Processes can only share resources through techniques such as shared memory
and message passing.
• Such techniques must be explicitly arranged by the programmer. However,
threads share the memory and the resources of the process to which they belong by
default.
• The benefit of sharing code and data is that it allows an application to
• have several different threads of activity within the same address space.
• Economy

• Threads share the resources of the process to which they belong, it is more
economical to create and context-switch threads.

*For Internal Circulation Only 44

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Empirically gauging the difference in overhead can be difficult, but in general

it is significantly more time-consuming to create and manage processes than threads.
• Scalability

• The benefits of multithreading can be even greater in a multiprocessor

architecture, where threads may be running in parallel on different processing cores.
• A single-threaded process can run on only one processor, regardless how many
are available.
Multicore programming

Multicore programming helps to create concurrent systems for deployment on multicore

processors and multiprocessor systems.

• A multicore processor system is basically a single processor with multiple execution

cores in one chip.
• It has multiple processors on the motherboard or chip.
• A Field-Programmable Gate Array (FPGA) is might be included in a multiprocessor
system. A FPGA is an integrated circuit containing an array of programmable logic blocks
and a hierarchy of reconfigurable interconnects.
• Multicore and FPGA processing helps to increase the performance of an embedded
system.
• Also helps to achieve scalability, so the system can take advantage of increasing
numbers of cores and FPGA processing power over time.
Note:

• Concurrent systems that we create using multicore programming have multiple tasks
executing in parallel.
• This is known as concurrent execution. When multiple parallel tasks are executed by a
processor, it is known as multitasking.
• A CPU scheduler, handles the tasks that execute in parallel. The CPU implements tasks
using operating system threads. So that tasks can execute independently but have some data
transfer between them, such as data transfer between a data acquisition module and
controller for the system. Data transfer occurs when there is a data dependency.

*For Internal Circulation Only 45

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Multicore Programming Challenges

In general, five areas present challenges in programming for multicore systems

• Identifying tasks.

This involves examining applications to find areas

that can be divided into separate, concurrent tasks. Ideally, tasks are independent of one another
and thus can run in parallel on individual cores.

• Balance.
While identifying tasks that can run in parallel, programmers must also ensure that the tasks
perform equal work of equal value. In some instances, a certain task may not contribute as
much value to the overall process as other tasks. Using a separate execution core to run that
task may not be worth the cost.

• Data splitting.
Just as applications are divided into separate tasks, the

data accessed and manipulated by the tasks must be divided to run on separate cores.

• Data dependency.
The data accessed by the tasks must be examined for

dependencies between two or more tasks. When one task depends on data from another,
programmers must ensure that the execution of the tasks is synchronized to accommodate the
data dependency.

• Testing and debugging.

When a program is running in parallel on multiple cores, many different execution paths are
possible. Testing and debugging such concurrent programs is inherently more difficult than
testing and debugging single-threaded applications.

*For Internal Circulation Only 46

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Parallelism

Parallelism is when tasks literally run at the same time, eg. on a multicore processor. The term
Parallelism refers to techniques to make programs faster by performing several computations
in parallel. This requires hardware with multiple processing units.

Types of Parallelism

In general, there are two types of parallelism Data parallelism

Task parallelism.

Data parallelism

• Data parallelism focuses on distributing subsets of the same data across multiple
computing cores and performing the same operation on each core.

• Consider, for example, summing the contents of an array of size N.

• On a single-core system, one thread would simply sum the elements [0] . . . [N − 1].
• On a dual-core system, however, thread A, running on core 0, could sum the elements
[0] . . . [N/2 − 1] while thread B, running on core 1, could sum the elements

[N/2] . . . [N − 1]. The two threads would be running in parallel on separate computing cores.

Task parallelism

• Task parallelism involves distributing not data but tasks (threads) across multiple
computing cores. Each thread performs a unique operation.

• Different threads may be operating on the same data, or they may be operating on
different data. Consider again our example above.
• In contrast to that situation, an example of task parallelism might involve two threads,
each performing a unique statistical operation on the array of elements.
• The threads again are operating in parallel on separate computing cores, but each is
performing a unique operation.
•

*For Internal Circulation Only 47

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Note: Data parallelism involves the distribution of data across multiple cores and task
parallelism on the distribution of tasks across multiple cores.

Multithreading Models

Support for threads may be provided either at the user level, for user threads, or by the kernel,
for kernel threads.

• User threads are supported above the kernel and are managed without kernel support.
• Kernel threads are supported and managed directly by the operating system.
• Virtually all contemporary operating systems—including Windows, Linux, Mac OS X,
and Solaris— support kernel threads.
• Ultimately, a relationship must exist between user threads and kernel threads. In this
section, we look at three common ways of establishing such a relationship
• The many-to-one model
• The one-to-one model
• The many-to-many model
Many-to-One Model

• The many-to-one model maps many user-level threads to one kernel thread.

• Thread management is done by the thread library in user space, so it is efficient.

• However, the entire process will be blocked if a thread makes a blocking system call.
Also, because only one thread can access the kernel at a time, multiple threads are unable
to run in parallel on multicore systems.
• Green threads—a thread library available for Solaris systems and adopted in early
versions of Java—used the many-to-one model.
• However, very few systems continue to use the model because of its inability to take
advantage of multiple processing cores.

*For Internal Circulation Only 48

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

One-to-One Model

• The one-to-one model maps each user thread to a kernel thread.

• It provides more concurrency than the many-to-one model by allowing another thread
to run when a thread makes a blocking system call.
• It also allows multiple threads to run in parallel on multiprocessors.
• The only drawback to this model is that creating a user thread requires creating the
corresponding kernel thread.
• Because the overhead of creating kernel threads can burden the performance of an
application, most implementations of this model restrict the number of threads supported
by the system.
• Linux, along with the family of Windows operating systems, implements the one-to-
one model.

*For Internal Circulation Only 49

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Many-to-Many Model

• Many-to-Many Model The many-to-many model multiplexes many user-level threads

to a smaller or equal number of kernel threads.

• The number of kernel threads may be specific to either a particular application or a

particular machine.
• The many-to-many model suffers from neither of these shortcomings: developers can
create as many user threads as necessary, and the corresponding kernel threads can run in
parallel on a multiprocessor.
• Also, when a thread performs a blocking system call, the kernel can schedule another
thread for execution.
• One variation on the many-to-many model still multiplexes many user-level threads to
a smaller or equal number of kernel threads but also allows a user-level thread to be bound
to a kernel thread.
• This variation is sometimes referred to as the two-level model.
• The Solaris operating system supported the two-level model in versions older than
Solaris 9.

*For Internal Circulation Only 50

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Many-to-Many Model

Two-level model

CPU Scheduler

• Whenever the CPU becomes idle, the operating system must select one of the processes
in the ready queue to be executed. The selection process is carried out by the short-term
scheduler, or CPU scheduler.

• The scheduler selects a process from the processes in memory that are ready to execute
and allocates the CPU to that process.
• Note that the ready queue is not necessarily a first-in, first-out (FIFO) queue.
• As we shall see when we consider the various scheduling algorithms, a ready queue can
be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked
list. Conceptually, however, all the processes in the ready queue are lined up waiting for a
chance to run on the CPU.
• The records in the queues are generally process control blocks (PCBs) of the processes.

*For Internal Circulation Only 51

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Pre-emptive Scheduling

• CPU-scheduling decisions may take place under the following four circumstances
• When a process switches from the running state to the waiting state (for example, as
the result of an I/O request or an invocation of wait() for the termination of a child process)
• When a process switches from the running state to the ready state (for example, when
an interrupt occurs)
• When a process switches from the waiting state to the ready state (for example, at
completion of I/O)
• When a process terminates
• Scheduling schemes are classified as follows
• Non-pre-emptive or cooperative.
• Pre-emptive.
• Under non-pre-emptive 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.
• Pre-emptive scheduling can result in race conditions when data are shared among
several processes. Consider the case of two processes that share data. While one process is
updating the data, it is pre-empted so that the second process can run. The second process
then tries to read the data, which are in an inconsistent state.

Dispatcher

• Another component involved in the CPU-scheduling function is the dispatcher.

• The dispatcher is the module that gives control of the CPU to the process selected by
the short-term scheduler. This function involves the following
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program
• The dispatcher should be as fast as possible since it is invoked during every process
switch.

*For Internal Circulation Only 52

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The time it takes for the dispatcher to stop one process and start another running is
known as the dispatch latency.
Scheduling Criteria

• Different CPU-scheduling algorithms have different properties, and the choice of an

algorithm may favor one class of processes over another.

• In choosing which algorithm to use in a situation, we must consider the properties of

the various algorithms.
• Many criteria have been suggested for comparing CPU-scheduling algorithms.
• Which characteristics are used for comparison can make a substantial difference in
which algorithm is judged to be best?
The criteria include the following

1. CPU utilization

We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from
0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system)
to 90 percent (for a heavily loaded system).

2. Throughput.

If the CPU is busy executing processes, then work is being

done. One measure of work is the number of processes that are completed per time unit, called
throughput. For long processes, this rate may be one process per hour; for short transactions, it
may be ten processes per second.

3. Turnaround time.

From the point of view of a particular process, the

important criterion is how long it takes to execute that process. The interval from the time of
submission of a process to the time of completion is the turnaround time. Turnaround time is
the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing
on the CPU, and doing I/O.

*For Internal Circulation Only 53

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

4. Waiting time.

The CPU-scheduling algorithm does not affect the amount of time during which a process
executes or does I/O. It affects only the amount of time that a process spends waiting in the
ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.

*For Internal Circulation Only 54

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

5. Response time.

In an interactive system, turnaround time may not be

the best criterion. Often, a process can produce some output fairly early and can continue
computing new results while previous results are being output to the user. Thus, another
measure is the time from the submission of a request until the first response is produced. This
measure, called response time, is the time it takes to start responding, not the time it takes to
output the response. The turnaround time is generally limited by the speed of the output device.

Scheduling Algorithms

• A Process Scheduler schedules different processes to be assigned to the CPU

based on scheduling algorithms.
• There are six popular process scheduling algorithms which are as follows
• First-come, First-Served (FCFS) Scheduling
• Shortest-Job-Next (SJN) Scheduling
• Priority Scheduling
• Shortest Remaining Time
• Round Robin(RR) Scheduling
• Multiple-Level Queues Scheduling
• Above algorithms are either non-pre-emptive or pre-emptive.
• Non-pre-emptive algorithms are designed so that once a process enters the
running state, it cannot be pre-empted until it completes its allotted time.
• Pre-emptive scheduling is based on priority where a scheduler may pre-empt a
low-priority running process anytime when a high-priority process enters a ready state.

First Come First Serve (FCFS)

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

• It is a non-pre-emptive, pre-emptive scheduling algorithm.

• Easy to understand and implement.
• Its implementation is based on FIFO queue.

*For Internal Circulation Only 55

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Poor in performance as average wait time is high.

Wait time of each process is as follows

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

Shortest-Job-First Scheduling

• This is also known as shortest job first, or SJF

• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in advance.
• Impossible to implement in interactive systems where required CPU time is not known.
• The processer should know in advance how much time process will take.
As an example of SJF scheduling, consider the following set of processes, with the length of
the CPU burst given in milliseconds

*For Internal Circulation Only 56

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Using SJF scheduling, we would schedule these processes according to the following Gantt
chart

• The waiting time is 3 milliseconds for process P1, 16 milliseconds for process • P2,
9 milliseconds for process P3, and 0 milliseconds for process P4.
• Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.
• By comparison, if we were using the FCFS scheduling scheme, the average waiting
time would be 10.25 milliseconds.

Priority Scheduling

• Priority scheduling is a non-preemptive algorithm and one of the most common

scheduling algorithms in batch systems.

• Each process is assigned a priority. The process with the highest priority is to be
executed first and so on.
• Processes with the same priority are executed on a first-come first-served basis.
• Priority can be decided based on memory requirements, time requirements, or any other
resource requirement.

Note that we discuss scheduling in terms of high priority and low priority. Priorities are
generally indicated by some fixed range of numbers, such as 0 to 7 or 0 to 4,095.

*For Internal Circulation Only 57

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Consider the following set of processes, assumed to have arrived at time 0 in the order
P1, P2, ···, P5, with the length of the CPU burst given in milliseconds

• Using priority scheduling, we would schedule these processes according to the

following
Gantt chart

• The average waiting time is 8.2 milliseconds.

Round Robin Scheduling

• Round Robin is the pre-emptive process scheduling algorithm.

• Each process is provided a fixed time to execute, it is called a quantum.

• Once a process is executed for a given period, it is pre-empted, and another process
executes for a given period.
• Context switching is used to save states of pre-empted processes.

*For Internal Circulation Only 58

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The wait time of each process is as follows

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

*For Internal Circulation Only 59

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Multiple-level Queue Scheduling.

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

• Multiple queues are maintained for processes with common characteristics.

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

Multilevel Feedback Queue Scheduling

• The multilevel feedback queue scheduling algorithm, in contrast, allows a process to

move between queues.

• The idea is to separate processes according to the characteristics of their CPU bursts.
• If a process uses too much CPU time, it will be moved to a lower-priority queue.
• This scheme leaves I/O-bound and interactive processes in the higher-priority queues.
• In addition, a process that waits too long in a lower-priority queue may be moved to a
higher-priority queue. This form of aging prevents starvation.

Thread Scheduling

Thread scheduling is done by thread library, which consists of below contention scope.

PCS (Process Contention Scope)

• In PCS scheduling is done by the thread’s library.

• The library chooses which unbound thread will be put on which LWP.
• The scheduling of the LWP is (of course) still global and independent of the local
scheduling. While this does mean that unbound threads are subject to a sort of funny, two-

*For Internal Circulation Only 60

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

tiered scheduling architecture, in practice, you can ignore the scheduling of the LWP and
deal solely with the local scheduling algorithm.
SCS (System Contention Scope)

• The System Contention Scope is one of two thread-scheduling schemes used in

operating systems.

• This scheme is used by the kernel to decide which kernel-level thread to schedule onto
a CPU, wherein all threads (as opposed to only user-level threads, as in the Process
Contention Scope scheme) in the system compete for the CPU.
• Operating systems that use only the one-to-one model, such as Windows, Linux, and
Solaris, schedule threads using only System Contention Scope

Multiple-Processor Scheduling
In multiple-processor scheduling multiple CPUs are available and hence Load Sharing
becomes possible.

• However multiple processor scheduling is more complex as compared to single

processor scheduling.
• In multiple processor scheduling there are cases when the processors are identical i.e.
HOMOGENEOUS, in terms of their functionality, we can use any processor available to
run any process in the queue.

Approaches to Multiple-Processor Scheduling

Asymmetric Multiprocessing

One approach is when all the scheduling decisions and I/O processing are handled by a single
processor which is called the Master Server and the other processors executes only the user
code. This is simple and reduces the need of data sharing.

*For Internal Circulation Only 61

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Symmetric Multiprocessing

A second approach uses Symmetric Multiprocessing where each processor is self scheduling.
All processes may be in a common ready queue or each processor may have its own private
queue for ready processes. The scheduling proceeds further by having the scheduler for each
processor examine the ready queue and select a process to execute.

Processor Affinity

• Processor Affinity means a process has an affinity for the processor on which it is
currently running.

• When a process runs on a specific processor there are certain effects on the cache
memory. The data most recently accessed by the process populate the cache for the
processor and as a result successive memory access by the process are often satisfied in the
cache memory. Now if the process migrates to another processor, the contents of the cache
memory must be invalidated for the first processor and the cache for the second processor
must be repopulated. Because of the high cost of invalidating and repopulating caches, most
of the SMP(symmetric multiprocessing) systems try to avoid migration of processes from
one processor to another and try to keep a process running on the same processor. This is
known as PROCESSOR AFFINITY.
There are two types of processor affinity

• Soft Affinity

When an operating system has a policy of attempting to keep a process running on the same
processor but not guaranteeing it will do so, this situation is called soft affinity.

• Hard Affinity
Hard Affinity allows a process to specify a subset of processors on which it may run. Some
systems such as Linux implements soft affinity but also provide some system calls like
sched_setaffinity() that supports hard affinity.

*For Internal Circulation Only 62

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Load Balancing

Load Balancing is the phenomenon that keeps the workload evenly distributed across all
processors in an SMP system.

• Load balancing is necessary only on systems where each processor has its own private
queue of processes that are eligible to execute. Load balancing is unnecessary because once
a processor becomes idle it immediately extracts a runnable process from the common run
queue.
• On SMP(symmetric multiprocessing), it is important to keep the workload balanced
among all processors to fully utilize the benefits of having more than one processor else
one or more processors will sit idle while other processors have high workloads along with
lists of processors awaiting the CPU.
There are two general approaches to load balancing:

• Push Migration

In push migration a task routinely checks the load on each processor and if it finds an imbalance
then it evenly distributes the load on each processor by moving the processes from overloaded
to idle or less busy processors.

• Pull Migration

Pull Migration occurs when an idle processor pulls a waiting task from a busy processor for its
execution.

Multicore Processors

• In multicore processors multiple processor cores are placed on the same physical chip.
Each core has a register set to maintain its architectural state and thus appears to the
operating system as a separate physical processor.

• SMP systems that use multicore processors are faster and consume less power than
systems in which each processor has its own physical chip.
• However multicore processors may complicate the scheduling problems. When a
processor accesses memory then it spends a significant amount of time waiting for the data

*For Internal Circulation Only 63

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

to become available. This situation is called MEMORY STALL. It occurs for various
reasons such as cache miss, which is accessing the data that is not in the cache memory. In
such cases, the processor can spend up to fifty percent of its time waiting for data to become
available from the memory.
• To solve this problem recent hardware designs have implemented multithreaded
processor cores in which two or more hardware threads are assigned to each core. Therefore
if one thread stalls while waiting for the memory, core can switch to another thread.
There are two ways to multithread a processor:

Coarse-Grained Multithreading

In coarse-grained multithreading a thread executes on a processor until a long latency event

such as a memory stall occurs, because of the delay caused by the long latency event, the
processor must switch to another thread to begin execution. The cost of switching between
threads is high as the instruction pipeline must be terminated before the other thread can begin
execution on the processor core. Once this new thread begins execution it begins filling the
pipeline with its instructions.

Fine Grained Multithreading: This multithreading switches between threads at a much finer
level mainly at the boundary of an instruction cycle. The architectural design of fine-grained
systems includes logic for thread switching and as a result, the cost of switching between
threads is small.

Solaris Scheduling

• Solaris uses priority-based thread scheduling.

• Each thread belongs to one of six classes

• Time sharing (TS)
• Interactive (IA)
• Real-time (RT)
• System (SYS)
• Fair share (FSS)
• Fixed priority (FP)

*For Internal Circulation Only 64

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Threads in the real-time class are given the highest priority. A real-time process
will run before a process in any other class.
• Solaris uses the system class to run kernel threads, such as the scheduler and
paging daemon.
• Below figure illustrates how the six scheduling classes relate to one another and
how they map to global priorities.

Algorithm Evaluation

Algorithm Evaluation is about selecting a CPU-scheduling algorithm for a system.

The first problem is defining the criteria to be used in selecting an algorithm and criteria are
often defined in terms of CPU utilization,

• response time, or throughput.

*For Internal Circulation Only 65

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• To select an algorithm, we must first define the relative importance of these elements.
• Our criteria may include several measures, such as these:
• Maximizing CPU utilization under the constraint that the maximum response time is 1
second.
• Maximizing throughput such that turnaround time is (on average) linearly proportional
to total execution time.
• Once the selection criteria have been defined, we want to evaluate the algorithms under
consideration.
• We have below evaluation methods.

Deterministic Modeling

• One major class of evaluation methods is analytic evaluation. Analytic evaluation uses
the given algorithm and the system workload to produce a formula or number to evaluate
the performance of the algorithm for that workload.

• Deterministic modeling is one type of analytic evaluation. This method takes a

predetermined workload and defines the performance of each algorithm for that workload.

Queueing Models

• The computer system is described as a network of servers.

• Each server has a queue of waiting processes. The CPU is a server with its ready queue,
as is the I/O system with its device queues. Knowing arrival rates and service rates, we can
compute utilization, average queue length, average wait time, and so on.
• This area of study is called queueing-network analysis.

• The above equation, known as Little’s formula, is particularly useful because it is valid
for any scheduling algorithm and arrival distribution.

*For Internal Circulation Only 66

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Where n be the average queue length (excluding the process being serviced) W be the average
waiting time in the queue,

be the average arrival rate for new processes in the queue.

Simulations

• To get a more accurate evaluation of scheduling algorithms, we can use simulations.

• Running simulations involves programming a model of the computer system.

• Software data structures represent the major components of the system.
• The simulator has a variable representing a clock. As this variable’s value is increased,
the simulator modifies the system state to reflect the activities of the devices, the processes,
and the scheduler.
• As the simulation executes, statistics that indicate algorithm performance are gathered
and printed.
Implementation

• Even a simulation is of limited accuracy.

The only completely accurate way to evaluate a scheduling algorithm is to code it up, put it in
the operating system, and see how it works.

• This approach puts the actual algorithm in the real system for evaluation under real
operating conditions.

*For Internal Circulation Only 67

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

UNIT – 2
PROCESS SYNCHRONIZATION.

1. The Critical-Section Problem.

2. Peterson’s Solution.
3. Synchronisation Hardware.
4. Mutex Locks.
5. Semaphores.
6. Classic Problems of Synchronization.
7. Monitors, Synchronization Examples.
8. Process Scheduling: Criteria.
9. Scheduling Algorithms.
10. Multi-Processor Scheduling.
11. Real-time CPU Scheduling.
12. Deadlocks: System model and Characterization.
13. Methods for handling deadlocks.
14. Deadlock Prevention.
15. Avoidance.
16. Detection.
17. Recovery from deadlock.

*For Internal Circulation Only 68

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Process Synchronization

• Process Synchronization means sharing system resources by processes in such a way

that, Concurrent access to shared data is handled thereby minimizing the chance of
inconsistent data. Maintaining data consistency demands mechanisms to ensure
synchronized execution of cooperating processes.

• Process Synchronization was introduced to handle problems that arose during multiple
process executions. Some of the problems are discussed below.

Race Condition

• A race condition is a situation that may occur inside a critical section. This happens
when the result of multiple thread execution in a critical section differs according to the
order in which the threads execute.

• Race conditions in critical sections can be avoided if the critical section is treated as an
atomic instruction. Also, proper thread synchronization using locks or atomic variables can
prevent race conditions.
Critical Section

• The critical section in a code segment where the shared variables can be accessed.

• Atomic action is required in a critical section i.e. only one process can execute in its
critical section at a time.
• All the other processes have to wait to execute in their critical sections.

The critical section is given as follows:

do

Entry Section

Critical Section

*For Internal Circulation Only 69

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Exit Section

Remainder Section

} while (TRUE);

• In the above diagram, the entry sections handle the entry into the critical section. It
acquires the resources needed for the execution by the process. The exit section handles
the exit from the critical section. It releases the resources and also informs the other
processes that the critical section is free.

• The critical section problem needs a solution to synchronize the different processes.
The solution to the critical section problem must satisfy the following conditions.

Mutual Exclusion

• Mutual exclusion implies that only one process can be inside the critical section at any time.
If any other processes require the critical section, they must wait until it is free.

Progress

• Progress means that if a process is not using the critical section, then it should not stop
any other process from accessing it.

• In other words, any process can enter a critical section if it is free.

Bounded Waiting

Bounded waiting means that each process must have a limited waiting time. It should not wait
endlessly to access the critical section.

Peterson’s Solution

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

• In Peterson’s solution, we have two shared variables:

• boolean flag[i] : Initialized to FALSE, initially no one is interested in entering the
critical section
• int turn: The process whose turn is to enter the critical section.

*For Internal Circulation Only 70

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

do {

flag[i] = true;

turn = j;

while (flag[j] && turn == j); /* critical section */

flag[i] = false; /* remainder section */

while (true);

Peterson’s Solution preserves below three conditions

• Mutual Exclusion is assured as only one process can access the critical section at any
time.

• Progress is also assured, as a process outside the critical section does not block other
processes from entering the critical section.
• Bounded Waiting is preserved as every process gets a fair chance.

Synchronization Hardware

• TestAndSet is a hardware solution to the synchronization problem.

• In TestAndSet, we have a shared lock variable that can take either of the two values, 0
or 1.
• We follow below conventions
0 Unlock 1 Lock

• Before entering into the critical section, a process inquires about the lock. If it is locked,
it keeps on waiting till it becomes free and if it is not locked, it takes the lock and executes
the critical section.
• In TestAndSet, Mutual exclusion and progress are preserved but bounded waiting
cannot be preserved.

*For Internal Circulation Only 71

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Semaphores

• Semaphores are integer variables that are used to solve the critical section problem by
using two atomic operations, wait and signal that are used for process synchronization.

• The definitions of wait and signal are as follows

• Wait

• The wait operation decrements the value of its argument S, if it is positive. If S is

negative or zero, then no operation is performed. wait(S)
{

while (S<=0);

S--;

• Signal
• The signal operation increments the value of its argument S.
signal(S)

S++;

Types of Semaphores

There are two main types of semaphores i.e. counting semaphores and binary semaphores.
Details about these are given as follows

Counting Semaphores

• These are integer value semaphores and have an unrestricted value domain. These
semaphores are used to coordinate resource access, where the semaphore count is the
number of available resources.

*For Internal Circulation Only 72

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• If the resources are added, the semaphore count is automatically incremented and if the
resources are removed, the count is decremented.
Binary Semaphores

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

• Semaphores allow only one process into the critical section.

• They follow the mutual exclusion principle strictly and are much more efficient than
some other methods of synchronization.
• There is no resource wastage because of busy waiting in semaphores as processor time
is not wasted unnecessarily to check if a condition is fulfilled to allow a process to access
the critical section.
• Semaphores are implemented in the machine-independent code of the microkernel. So
they are machine-independent.
Disadvantages of Semaphores

• Semaphores are complicated so the wait and signal operations must be implemented in
the correct order to prevent deadlocks.
Semaphores are impractical for last-scale use as their use leads to loss of modularity. This
happens because the wait and signal operations prevent the creation of a structured layout for
the system.

• Semaphores may lead to a priority inversion where low-priority processes may access
the critical section first and high-priority processes later.
Classic Problems of Synchronization

Classical problems depict flaws of process synchronization in systems and it is addressed by

using the below approaches.

• Bounded Buffer (Producer-Consumer) Problem

*For Internal Circulation Only 73

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The Readers Writers Problem

• Dining Philosophers Problem

The Bounded-Buffer Problem

• This problem is generalized in terms of the Producer-Consumer problem, where a finite

buffer pool is used to exchange messages between producer and consumer processes.

• Because the buffer pool has a maximum size, this problem is often called the Bounded
buffer problem.
• The solution to this problem is, creating two counting semaphores full and empty to
keep track of the current number of full and empty buffers, respectively.
• Need to follow the below conventions.
• a buffer that can store n items.
• a producer process that creates the items (1 at a time).
• a consumer process that processes them (1 at a time).

Note:

• A producer cannot produce unless there is an empty buffer slot to fill.

• A consumer cannot consume unless there is at least one produced item.

The Readers Writer's Problem

• In this problem there are some processes(called readers) that only read the shared data,
and never change it, and there are other processes(called writers) who may change the data
in addition to reading.
• There are various types of readers-writer problems, most centered on the relative
priorities of readers and writers.
• A data item such as a file is shared among several processes. Each process is classified
as either a reader or a writer. Multiple readers may access the file simultaneously.

*For Internal Circulation Only 74

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• A writer must have exclusive access (i.e., cannot share with either a reader or another
writer).
• Solution gives priority to either readers or writers.
• Reader’s priority: no reader is kept waiting unless a writer has already obtained
permission to access the database.
• Writer’s priority: if a writer is waiting to access the database, no new readers can start
reading.
• Solution to either version may cause starvation
• In the reader's priority version, writers may starve
• In the writer’s priority version, readers may starve

Dining Philosophers Problem

The dining philosopher’s problem states that 5 philosophers are sharing a circular table and
they eat and think alternatively.

• There is a bowl of rice for each of the philosophers and 5 chopsticks. A philosopher
needs both their right and left chopsticks to eat.
• A hungry philosopher may only eat if there are both chopsticks available. Otherwise, a
philosopher puts down their chopstick and begin thinking again.
• The dining philosopher is a classic synchronization problem as it demonstrates a large
class of concurrency control problems.
Solution of Dining Philosophers' Problem

• A solution of the Dining Philosophers Problem is to use a semaphore to represent a

chopstick.
• A chopstick can be picked up by executing a wait operation on the semaphore and
released by executing a signal semaphore.
The structure and diagram of the chopstick is shown below

*For Internal Circulation Only 75

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

semaphore chopstick [5];

• Initially the elements of the chopstick are initialized to 1 as the chopsticks are on the
table and not picked up by a philosopher.

• The structure of a random philosopher i is given as follows

do {

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

EATING THE RICE.

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

THINKING.

} while(1);

• In the above structure, the first wait operation is performed on chopstick[i] and
chopstick[ (i+1) % 5].
• This means that the philosopher has picked up the chopsticks on his sides. Then the
eating function is performed.
After that, signal operation is performed on chopstick[i] and chopstick[ (i+1) % 5].

• This means that the philosopher has eaten and put down the chopsticks on his sides.
Then the philosopher goes back to thinking.
Difficulty with the solution

The above solution makes sure that no two neighboring philosophers can eat at the same time.
But this solution can lead to a deadlock.

• This may happen if all the philosophers pick their left chopsticks simultaneously. Then
none of them can eat and deadlock occurs.

*For Internal Circulation Only 76

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Some of the ways to avoid deadlock are as follows • There should be at most
four philosophers on the table.
• An even philosopher should pick the right chopstick and then the left chopstick while
an odd philosopher should pick the left chopstick and then the right chopstick.
• A philosopher should only be allowed to pick their chopstick if both are available at the
same time.
Monitors in Process Synchronization

• The monitor is one of the ways to achieve Process synchronization. The monitor is
supported by programming languages to achieve mutual exclusion between processes.
For example Java Synchronized methods. Java provides wait() and notify() constructs.

• It is the collection of condition variables and procedures combined together in a special

kind of module or a package.
• The processes running outside the monitor can’t access the internal variable of the
monitor but can call procedures of the monitor.
• Only one process at a time can execute code inside monitors.

monitorDemo //Name of Monitor

variables;

condition variables;

Procedure p1{…}

Procedure p2{…}

• Condition Variables

*For Internal Circulation Only 77

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Two different operations are performed on the condition variables of the monitor.
• Wait.
• signal.
• let say we have 2 condition variables
• condition x, y; // Declaring variable

• Wait operation

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

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

Advantages of Monitor

• Monitors have the advantage of making parallel programming easier and less error-
prone than using techniques such as semaphore.

Disadvantages of Monitor

• Monitors have to be implemented as part of the programming language. The compiler

must generate code for them.

• This gives the compiler the additional burden of having to know what operating system
facilities are available to control access to critical sections in concurrent processes.
• Some languages that do support monitors are Java, C#, Visual Basic, Ada, and
concurrent Euclid.

*For Internal Circulation Only 78

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

DEADLOCK

Definition

A deadlock is a situation where a set of processes are blocked because each process is holding
a resource and waiting for another resource acquired by some other process.

The below diagram shows the scenario of deadlocks.

• In the above diagram, process 1 has resource 1 and needs to acquire resource 2.
• Similarly process 2 has resource 2 and needs to acquire resource 1.
• Process 1 and process 2 are in a deadlock as each of them needs the other’s resources
to complete their execution but neither of them is willing to relinquish their resources.
Deadlock Characterization

A deadlock occurs if the four Coffman conditions hold. But these conditions are not mutually
exclusive.

Mutual Exclusion

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

*For Internal Circulation Only 79

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Hold and Wait

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

No Pre-emption

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

Circular Wait

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

*For Internal Circulation Only 80

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Resource-Allocation Graph

Deadlock can be described more precisely in terms of a directed graph called a system
Resource allocation graph.

• This graph consists of a set of verities V and a set into two different types of nodes P=
{P 1, P 2 ,…P n }, the set consisting of all the active processes in the system.
• R= {R 1, R 2 ,… R n }, the set consisting of all the resource types in the system.
• A directed edge from process Pi to resources type R j is denoted by P I → R j. It signifies
that process Pi to resource type R j and is currently waiting for that resource.
• A directed edge Pi → R j is called request edge.
• A directed edge from resource type R j to process Pi is denoted by R j →Pi. It signifies
that an instance of resource type has been allocated to process Pi. A directed edge R j →
Pi is called an assignment edge.
• Pictorially, we represent each process a circle, and each resource type Rj as a square
since resource type Rj may have more than one instance, we represent each such instance
as a dot within the square.
Note: A request edge points to only the square Rj. Whereas an assignment edge must also
designate one of the dots in the square.

*For Internal Circulation Only 81

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The resource-allocation graph shown in figure depicts the following situation

The sets P, R and E: P= {P1, P2, P3} R= {R1, R2, R3, R4}

E= {P1 →R1, P2 →R3, R1→P2, R2 →P2, R2 →P1, R3 →P3}

• Resource Instance
• One instance of resource type R1.
• Two instances of resource type R2.
• One instance of resource type R3.
• Three instances of resource type R4.
Note:

When process Pi requests an instance of resource type R j a request edge is inserted in the
resource allocation graph. When this request can be fulfilled, the request edge is transferred to
an assignment edge is doted.

• Process states

• Process P1 is holding an instance of resource type R2 and is waiting for

• an instance of resource type R1.
• Process P2 is holding an instance of R1 and an instance of R2 and is
• waiting for an instance of R3.
• Process P3 is holding an instance of R3.

*For Internal Circulation Only 82

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Defined a resource-allocation graph, it can be shown that, if a graph contains no cycle

then there is no deadlock.

• If the cycle invokes only a set of resource types each of which has only a single instance,
then deadlock has occurred. Each process involved in the cycle is deadlock.
• If a resource type has several instances, then a cycle doesn’t necessarily imply that a
deadlock has occurred.
• In this case the cycle in the graph is necessary but not sufficient for the deadlock.
Deadlock Prevention

• A deadlock may occur when Mutual exclusion, hold and wait. No pre-emption, circular
wait occurs simultaneously. A system can be prevented from deadlock if these conditions
are not allowed to occur.

Mutual Exclusion

• The mutual-exclusion condition must hold for non-sharable resources so it can be

avoided by making the resource shareable like a printer which cannot be accessed by more
than one at a time.

• Shareable resources like read-only files can be shared among processes. Thus, a process
never needs to wait for a sharable resource.
Hold and Wait

• To ensure that the hold and wait condition never occurs in the system, we must
guarantee that whenever process requests a resource, it does not hold any other resources.
• First product that can be used requires each process to request and be allocated all its
resources before it begins execution.
• An alternative protocol allows a process to request resources only when the process has
none.
• A process may request some resources and use them. Before it can request any
additional resources. It must release all the resources that is currently allocated.

*For Internal Circulation Only 83

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

No pre-emption

• To ensure that this condition does not hold, we can use the following protocol.

• If a process is holding some resources and requests another resource that cannot be
immediately allocated to it (i.e. the process must wait), then all resources currently being
held are pre-empted.
• The pre-empted resources are added to the list of resources for which the process is
waiting the process will be re-started only when it can re-gain its old resources, as well as
the new ones that it is requesting.
• Alternatively, if the process requests some resources, we first check whether they are
available.
• If they are, we allocate them. If they aren’t available, we check whether they are
allocated to another process that is waiting for additional resources.
Circular Wait

• One way to ensure that this condition never holds is to impose a total that each process
requests resources in increasing order of enumeration.

Let R= {R1, R2 …Rn} be the set of resource printers if the enumeration

F (pen drive) =1

F (disk drive) =5

F (printer) = 12

Where F is a function.

• Allocation of resources can be made in any of the orders. Tape drive, disk drive for all
F (tape drive) < F (disk drive)
• Tape drive, printer for all F (tape drive) <F (printer) Disk drive, printer for all F (disk
drive) < F (printer)

Being in the increasing order of the enumeration and thus deadlock can be prevented.

*For Internal Circulation Only 84

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Deadlock Avoidance

• In the approach of dead-lock avoidance, each process declares a maximum number of

resources of each type that is may need. Once this priori information of each process is
obtained, it is easy to construct an algorithm that ensures that the system will never enter a
deadlock state.

• This algorithm defines the dead-lock avoidance approach. A dead-lock avoidance

algorithm dynamically examines the resources and the maximum demands of the process.
Safe State

• A state is safe if the system can allocate resources to each process in some order and
still avoid a deadlock. More precisely a system is in a safe state only if there exists a safe
sequence.

• A sequence of processes <P1, P2 , P3 …Pn >is in a safe state only if for each Pi the
resources that Pi can still request can be satisfied by the currently available resources plus
the resources held by all the P j, with j < i.

*For Internal Circulation Only 85

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Resource-Allocation-Graph Algorithm

• Along with the request and assignment edges, we introduce a new type of edge, called
claim edge.

• A claim edge Pi → Rj indicates that process Pi may request resources R j at some time
in the future. They are represented in a dashed line.
• If no cycle exists, then the allocation of the resource will put the system in a safe state.
On the other hand, if the cycle is found, the allocation will put the system in an unsafe state.
• The Below graph represents the resource allocation graph for deadlock avoidance.
• Consider the resource allocation graph, suppose that P2 requests r2 although R2 is
currently free, we cannot allocate it to P2, since this action will create a cycle in the graph.
• A cycle indicates that the system is in an unsafe state. If P1 requests R2, and P2 requests
R1, then a deadlock will occur.

Banker’s Algorithm

The resource allocation graph algorithm does not apply to a resource • allocation system
with multiple instances of each resource type.

• For that we use Banker’s algorithm.

• It is named so because, in a banking system, the bank never allocates its available cash
such that it can no longer satisfy the needs of all its customers.
• The Below graph shows the unsafe state in a resource allocation graph.

*For Internal Circulation Only 86

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The data structure used in the banker’s algorithm are

Available

A vector (array) of length m indicates the number of available resources of each type.
Available[j]=K, indicates that there are K instances to resource type R j is available.

MAX

An n*m matrix defines the maximum demand to each process. If Max{i,j}=K, then Pi may
request the most K instances of resource type Rj.

Allocation

An n*m matrix defines the number of resources of each type currently allocated to each
process. If allocation[i,j]=K, then process Pi currently allocated K instances of resource type
Rj.

Need

An n*m matrix indicates the renaming resource need of each process. If need[i,j]=K then Pi
may need K more instances of resource type Rj, to complete its task and Need [ i , j] = Max[ I
, j]

Allocation [ i , j]

*For Internal Circulation Only 87

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Before going further, let us define the following notation

X and Y be the vectors of length n, X≤Y.

If X[i]≤Y[i], for all i=1,2…n Ex:

X= (1,7,3,2) and Y= (0,3,2,1) Then Y≤X, Y<X only if Y≤X and Y≠X.

Safety Algorithm

Safety algorithm for finding out whether a system is in a safe state. This algorithm can be
described as follows.

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

Initialize Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.

• Find an index i such that both Finish[i] == false

Needi ≤ Work

If no such i exists, go to step 4.

• Work = Work + Allocationi Finish[i] = true Go to step 2.

• If Finish[i] == true for all i, then the system is in a safe state.
This algorithm may require an order of m × n2 operations to determine whether a state is safe.

Resource-Request Algorithm

• Next, we describe the algorithm for determining whether requests can be safely
granted.

• Let Requesti be the request vector for process Pi . If Requesti [j] == k, then
process Pi wants k instances of resource type Rj . When a request for resources is
made by a process
Pi , the following actions are taken

• If Requesti ≤ Needi, go to step 2. Otherwise, raise an error condition, since the

process has exceeded its maximum claim.
• If Requesti ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources
are not available.

*For Internal Circulation Only 88

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Have the system pretend to have allocated the requested resources to process Pi
by modifying the state as follows:
• Available = Available–Requesti ; Allocationi = Allocationi + Requesti ;
Needi = Needi –Requesti ;

• If the resulting resource-allocation state is safe, the transaction is completed,

and process Pi is allocated its resources.
• However, if the new state is unsafe, then Pi must wait for Requesti , and the old
resource-allocation state is restored.
Deadlock Detection

• In a system that does not implement dead-lock prevention or deadlock avoidance

algorithm, then a dead-lock may occur.
• In such a system it is required an algorithm.
• That examines the state of the system to determine whether a deadlock has occurred.
To recover from the deadlock.
Single Instance of Each Resource Type

• This dead-lock detection algorithm uses a different type of resource allocation graph
called the wait-for graph. It consists of the edge.

• Pi → Pj indicates that process Pi is waiting for process Pj to release a resource that Pi

needs.
• For a given resource allocation graph in figure the corresponding allocation graph is
shown in figure b.
• If there exists a cycle in the graph, then the process is in a dead-lock condition. The
algorithm detects a cycle in a graph and requires an order of n2 operations.
• Figure b corresponding wait-for graph.

*For Internal Circulation Only 89

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Several Instances of Resource Type

This algorithm consists of the following data structures

• Available

A vector (Array) of length m indicates the number of available resources of each type.

• Allocation
An n*m matrix defines the number of resources of each type currently allocated to each
process.

• Request
An n*m matrix indicates the current request of each process and the algorithm is like a banker’s
algorithm with slight variation

• Let Work and Finish be vectors of length m and n, respectively. Initialize Work =
Available. For i = 0, 1, ..., n–1, if Allocationi != 0, then Finish[i] = false. Otherwise,
Finish[i] = true.
• Find an index i such that both

Finish[i] == false

*For Internal Circulation Only 90

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Requesti ≤ Work

If no such i exists, go to step 4.

• Work = Work + Allocationi Finish[i] = true Go to step 2.

• If Finish[i] == false for some i, 0 ≤ i < n, then the system is in a deadlocked state.
Moreover, if Finish[i] == false, then process Pi is deadlocked.

The above algorithm requires an order of m × n2 operations to detect whether the system is in
a deadlocked state.

*For Internal Circulation Only 91

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

UNIT – 3

MEMORY MANAGEMENT SYSTEM.

1. Memory Management Strategies: Background.

2. Swapping.
3. Contiguous Memory Allocation.
4. Segmentation.
5. Paging.
6. Structure of the Page Table.
7. Virtual Memory Management: Demand Paging.
8. Copy-on-Write, Page Replacement.
9. Allocation of Frames. File System.
10. File Concept, Access Methods.
11. Directory and Disk Structure.
12. Protection.
13. File-System Implementation: Structure.
14. File-System and Directory Implementation.
15. Allocation methods.
16. Free Space Management.
17. Mass-Storage Structure: Overview.
18. Disk Scheduling.
19. Disk Management.

*For Internal Circulation Only 92

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Memory Management

• Memory is central to the operation of a modern computer system.

• Memory consists of many bytes, each with its address.
• The CPU fetches instructions from memory according to the value of the program
counter. These instructions may cause additional loading from and storing to specific
memory addresses.

• A typical instruction-execution cycle is as follows

• First fetches an instruction from memory.
• The instruction is then decoded and may cause operands to be fetched from memory.
After the instruction has been executed on the operands, results may be stored back in
memory. The memory unit sees only a stream of memory addresses; it does not know
how they are generated (by the instruction counter, indexing, indirection, literal
addresses, and so on) or

• what they are for (instructions or data).

• Accordingly, we can ignore how a program generates a memory address. We are
interested only in the sequence of memory addresses generated by the running program.

Basic Hardware
• It should be noted that from the memory chips point of view, all memory accesses
are equivalent. The memory hardware doesn't know what a particular part of memory is
being used for, nor does it care. This is almost true of the OS as well, although not entirely.

• The CPU can only access its registers and main memory. It cannot, for example,
direct access to the hard drive, so any data stored there must first be transferred into the
main memory chips before the CPU can work.(Device drivers communicate with their
hardware via interrupts and "memory" accesses, sending short instructions for example to
transfer data from the hard drive to a specified location in main memory. The disk
controller monitors the bus for such instructions, transfers the data, and then notifies the

*For Internal Circulation Only 93

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

CPU that the data is there with another interrupt, but the CPU never gets direct access to
the disk.)

• Memory accesses to registers are very fast, generally one clock tick, and a CPU
may be able to execute more than one machine instruction per clock tick

• Memory accesses to main memory are comparatively slow and may take several
clock ticks to complete. This would require intolerable waiting by the CPU if it were not
for an intermediary fast memory cache built into most modern CPUs. The basic idea of the
cache is to transfer chunks of memory at a time from the main memory to the cache, and
then to access individual memory locations one at a time from the cache.

• User processes must be restricted so that they only access memory locations that
"belong" to that particular process. This is usually implemented using a base register and
a limit register for each process, as shown in below figures a and b. Every memory access
made by a user process is checked against these two registers, and if a memory access is
attempted outside the valid range, then a fatal error is generated. The OS has access to all
existing memory locations, as this is necessary to swap users' code and data in and out of
memory. It should also be obvious that changing the contents of the base and limit registers
is a privileged activity, allowed only to the OS kernel.
Figure a: A base and a limit register define a logical address space

*For Internal Circulation Only 94

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Figure b: Hardware address protection with base and limit registers

Address Binding
• User programs typically refer to memory addresses with symbolic names such as
"i", "count", and "average Temperature". These symbolic names must be mapped or bound
to physical memory addresses, which typically occur in several stages.

*For Internal Circulation Only 95

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Compile Time - If it is known at compile time where a program will reside in

physical memory, then absolute code can be generated by the compiler, containing actual
physical addresses. However, if the load address changes at some later time, then the
program will have to be recompiled. [Link] programs use compile time binding.

• Load Time - If the location at which a program will be loaded is not known at
compile time, then the compiler must generate relocatable code, which references
addresses relative to the start of the program. If that starting address changes, then the
program must be reloaded but not recompiled.

• Execution Time - If a program can be moved around in memory during its

execution, then binding must be delayed until execution time. This requires special
hardware and is the method implemented by most modern operating systems.
The below figure shows the various stages of the binding processes and the units involved in
each stage.

Logical Versus Physical Address Space

• The address generated by the CPU is a logical address, whereas the address seen
by the memory hardware is a physical address.

• Addresses bound at compile time or load time have identical logical and physical
addresses.

*For Internal Circulation Only 96

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Addresses created at execution time, however, have different logical and physical
addresses.
In this case, the logical address is also known as a virtual address, and the two terms are
used interchangeably in our text.

• The set of all logical addresses used by a program composes the logical address
space, and the set of all corresponding physical addresses composes the physical address
space.

• The run-time mapping of logical to physical addresses is handled by the memory

management unit, MMU.

• The MMU can take on many forms. One of the simplest is a modification of the
base register scheme described earlier.

• The base register is now termed a relocation register, whose value is added to every
memory request at the hardware level.

• Note that user programs never see physical addresses. User programs work entirely
in logical address space, and any memory references or manipulations are done using
purely logical addresses. Only when the address gets sent to the physical memory chips is
the physical memory address generated.
The below figure shows dynamic relocation using a relocation register

•
•

*For Internal Circulation Only 97

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Dynamic Loading

• Rather than loading an entire program into memory at once, dynamic loading loads up
each routine as it is called. The advantage is that unused routines need never be loaded,
reducing total memory usage and generating faster program startup times. The downside
is the added complexity and overhead of checking to see if a routine is loaded every time
it is called and then loading it up if it is not already loaded.
Dynamic Linking and Shared Libraries

• With static linking library modules get fully included in executable modules,
wasting both disk space and main memory usage, because every program that included a
certain routine from the library would have to have its copy of that routine linked into their
executable code.
• With dynamic linking, however, only a stub is linked into the executable module,
containing references to the actual library module linked in at run time.
• This method saves disk space because the library routines do not need to be fully
included in the executable modules, only the stubs.
• We will also learn that if the code section of the library routines is re-entrant(
meaning it does not modify the code while it runs, making it safe to re-enter it ), then the
main memory can be saved by loading only one copy of dynamically linked routines into
memory and sharing the code amongst all processes that are concurrently using it. (Each
process would have its copy of the data section of the routines, but that may be small
relative to the code segments.) The OS must manage shared routines in memory.
• An added benefit of dynamically linked libraries (DLLs, also known as shared
libraries or shared objects on UNIX systems) involves easy upgrades and updates.
When a program uses a routine from a standard library and the routine changes, then the
program must be rebuilt (re-linked) to incorporate the changes. However, if DLLs are used,
then as long as the stub does not change, the program can be updated merely by loading
new versions. a program can specify a version of the DLL if necessary.

• In practice, the first time a program calls a DLL routine, the stub will recognize the
fact and will replace itself with the actual routine from the DLL library. Further calls to the

*For Internal Circulation Only 98

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

same routine will access the routine directly and not incur the overhead of the stub access.
of the DLLs onto the system. Version information is maintained in both the program and
the

Swapping

• A process must be loaded into memory to execute.

• If there is not enough memory available to keep all running processes in memory at the
same time, then some processes that are not currently using the CPU may have their
memory swapped out to a fast local disk called the backing store.
Standard Swapping

• If compile-time or load-time address binding is used, then processes must be swapped

back into the same memory location from which they were swapped out. If execution
time binding is used, then the processes can be swapped back into any available location.
• Swapping is a very slow process compared to other operations. For example, if a user
process occupied 10 MB and the transfer rate for the backing store were 40 MB per
second, then it would take 1/4 second ( 250 milliseconds ) just to do the data transfer.
Adding in a latency lag of 8 milliseconds ignoring head seek time for the moment, and
further recognizing that swapping involves moving old data out as well as new data in,
the overall transfer time required for this swap is 512 milliseconds, or over half a second.
For efficient processor scheduling the CPU time slice should be significantly longer than
this lost transfer time.
To reduce swapping transfer overhead, it is desired to transfer as little information as possible,
which requires that the system know how much memory a process is using, as opposed to how

• much it might use. Programmers can help with this by freeing up dynamic memory that
they are no longer using.

• It is important to swap processes out of memory only when they are idle, or more to the
point, only when there are no pending I/O operations. ( Otherwise, the pending I/O
operation could be written into the wrong process's memory space. ) The solution is to

*For Internal Circulation Only 99

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

either swap only idle processes or do I/O operations only into and out of OS buffers,
which are then transferred to or from the process's main memory as a second step.

• Most modern OSes no longer use swapping, because it is too slow and there are faster
alternatives available. ( e.g. Paging. ) However, some UNIX systems will still invoke
swapping if the system gets extremely full, and then discontinue swapping when the load
reduces again.
Windows 3.1 would use a modified version of swapping that was somewhat controlled by
the user, swapping processes out if necessary and then only swapping them back in when
the user focused on that particular window.

• Below figure shows the swapping of two processes using a disk as a backing store.

Memory Allocation
• One method of allocating contiguous memory is to divide all available memory
into equal-sized partitions and to assign each process to its partition. This restricts both the
number of simultaneous processes and the maximum size of each process and is no longer
used.

• An alternate approach is to keep a list of unused ( free ) memory blocks ( holes ),

and to find a hole of a suitable size whenever a process needs to be loaded into memory.

*For Internal Circulation Only 100

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

There are many different strategies for finding the "best" allocation of memory to
processes, including the three most commonly discussed

• First fit - Search the list of holes until one is found that is big enough to satisfy the
request and assign a portion of that hole to that process. Whatever fraction of the hole not
needed by the request is left on the free list as a smaller hole. Subsequent requests may
start looking either from the beginning of the list or from the point at which this search
ended.

• Best fit—Allocate the smallest hole big enough to satisfy the request. This saves
large holes for other process requests that may need them later, but the resulting unused
portions of holes may be too small to be of any use and will, therefore, be wasted. Keeping
the free list sorted can speed up finding the right hole.

• Worst fit - Allocate the largest hole available, thereby increasing the likelihood that
the remaining portion will be usable for satisfying future requests.

• Simulations show that either the first or best fit is better than the worst fit regarding
both time and storage utilization. The first and best fits are about equal in terms of storage
utilization, but the first fit is faster.

Fragmentation
• All the memory allocation strategies suffer from external fragmentation, though
the first and best fits experience the problems more so than the worst fit. External
fragmentation means that the available memory is broken up into lots of little pieces, none
of which is big enough to satisfy the next memory requirement, although the sum total
could.

• The amount of memory lost to fragmentation may vary with algorithm, usage
patterns, and some design decisions such as which end of a hole to allocate and which end
to save on the free list.

• Statistical analysis of the first fit, for example, shows that for N blocks of allocated
memory, another 0.5 N will be lost to fragmentation.

*For Internal Circulation Only 101

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Internal fragmentation also occurs, with all memory allocation strategies. This is
caused by the fact that memory is allocated in blocks of a fixed size, whereas the actual
memory needed will rarely be that exact size.

For a random distribution of memory requests, on average 1/2 block will be wasted per
memory request, because on average the last allocated block will be only half full.

• Note that the same effect happens with hard drives and that modern hardware gives
us increasingly larger drives and memory at the expense of ever larger block sizes, which
translates to more memory lost to internal fragmentation.
• Some systems use variable-size blocks to minimize losses due to internal
fragmentation.
• If the programs in memory are relocatable, ( using execution-time address binding
), then the external fragmentation problem can be reduced via compaction, i.e. moving all
processes down to one end of physical memory. This only involves updating the relocation
register for each process, as all internal work is done using logical addresses.
• Another solution as we will see in upcoming sections is to allow processes to use
non-contiguous blocks of physical memory, with a separate relocation register for each
block.

Segmentation
• Segmentation is a memory management technique in which each job is divided into
several segments of different sizes, one for each module that contains pieces that perform
related functions.
• Each segment is a different logical address space of the program.

• When a process is to be executed, its corresponding segmentation is loaded into non-

contiguous memory though every segment is loaded into a contiguous block of available
memory.
• Segmentation memory management works very similar to paging but here segments are
of variable length whereas in paging pages are of fixed size.

*For Internal Circulation Only 102

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Basic Method
• Most users ( programmers ) do not think of their programs as existing in one
continuous linear address space.
• Rather they tend to think of their memory in multiple segments, each dedicated to
a particular use, such as code, data, the stack, the heap, etc.
• Memory segmentation supports this view by providing addresses with a segment
number ( mapped to a segment base address ) and an offset from the beginning of that
segment.

• For example, a C compiler might generate 5 segments for the user code, library
code, global ( static ) variables, the stack, and the heap, as shown in the below figure.

Segmentation Hardware
A segment table maps segment-offset addresses to physical addresses, and simultaneously
checks for invalid addresses, using a system like the page tables and relocation base
registers discussed previously. (Note that at this point in the discussion of segmentation,
each segment is kept in contiguous memory and may be of different sizes, but that
segmentation can also be combined with paging as we shall see shortly.)

*For Internal Circulation Only 103

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Paging
• A computer can address more memory than the amount physically installed on the
system. This extra memory is actually called virtual memory and it is a section of a hard
that's set up to emulate the computer's RAM. The paging technique plays an important role
in implementing virtual memory.
• Paging is a memory management technique in which process address space is
broken into blocks of the same size called pages (size is power of 2, between 512 bytes
and 8192 bytes). The size of the process is measured in the number of pages.

*For Internal Circulation Only 104

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Similarly, main memory is divided into small fixed-sized blocks of (physical)

memory called frames and the size of a frame is kept the same as that of a page to have
optimum utilization of the main memory and to avoid external fragmentation.

Advantages and Disadvantages of Paging

• Paging reduces external fragmentation but still suffers from internal fragmentation.

• Paging is simple to implement and assumed as an efficient memory management

technique.

• Due to the equal size of the pages and frames, swapping becomes very easy. • Page
table requires extra memory space, so may not be good for a system having small RAM.
Virtual memory
• Virtual memory involves the separation of logical memory as perceived by users from
physical memory.

• This separation allows an extremely large virtual memory to be provided for

programmers when only smaller physical memory is available.

• Diagram showing virtual memory that is larger than physical memory.

*For Internal Circulation Only 105

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Virtual memory is a memory management capability of an operating system that uses

hardware and software to allow a computer to compensate for physical memory
shortages by temporarily transferring data from RAM to disk storage. • The virtual
address space of a process refers to the logical view of how a process is stored in memory.

• Code needs to be in memory to execute, but the entire program is rarely used.
• Error code, unusual routines, large data structures
• Entire program code is not needed at the same time.
• Consider the ability to execute partially-loaded
• Program no longer constrained by limits of physical memory
• Each program takes less memory while running -> more programs run at the same time
or turnaround time

• Less I/O needed to load or swap programs into memory ->each user program runs faster
• Separation of user logical memory from physical memory
• Only part of the program needs to be in memory for execution
• Logical address space can therefore be much larger than physical address space
• Allows address spaces to be shared by several processes

*For Internal Circulation Only 106

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Allows for more efficient process creation

• More programs running concurrently
• Less I/O needed to load or swap processes
Demand paging
• A demand paging system is quite similar to a paging system with swapping where
processes reside in secondary memory and pages are loaded only on demand, not in
advance.

• When a context switch occurs, the operating system does not copy any of the old
program’s pages out to the disk or any of the new program’s pages into the main memory
Instead, it just begins executing the new program after loading the first page and fetches
that program’s pages as they are referenced.

• While executing a program, if the program references a page which is not available
in the main memory because it was swapped out a little ago, the processor treats this invalid

*For Internal Circulation Only 107

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

memory reference as a page fault and transfers control from the program to the operating
system to demand the page back into the memory.

Advantages

• Large virtual memory.

• More efficient use of memory.
• There is no limit on the degree of multiprogramming.
Disadvantages
• The number of tables and the amount of processor overhead for handling page interrupts
are greater than in the case of the simple paged management techniques.

Page fault
• A page fault occurs when a program attempts to access a block of memory that is not
stored in the physical memory, or RAM.

• The fault notifies the operating system that it must locate the data in virtual memory, and
then transfer it from the storage device, such as an HDD or SSD, to the system RAM.

• Page fault can be handled as follows

• Find a free frame
• Swap page into the frame via scheduled disk operation
• Reset tables to indicate page fault
• Restart the instruction that caused the page fault
Page Replacement Algorithm
• Page replacement algorithms are the techniques using which an Operating System
decides which memory pages to swap out, and write to disk when a page of memory needs
to be allocated.

• Paging happens whenever a page fault occurs and a free page cannot be used for
allocation purposes accounting to the reason that pages are not available or the number of
free pages is lower than the required pages.

*For Internal Circulation Only 108

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• When the page that was selected for replacement and was paged out, is referenced
again, it has to read in from disk, and this requires I/O completion. This process determines
the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the
better is the algorithm.

• A page replacement algorithm looks at the limited information about accessing the
pages provided by hardware, and tries to select which pages should be replaced to
minimize the total number of page misses while balancing it with the costs of primary
storage and processor time of the algorithm itself.

• There are many different page replacement algorithms. We evaluate an algorithm

by running it on a particular string of memory references and computing the number of
page faults.

Copy-on-write
• Copy on write sometimes referred to as implicit sharing or shadowing, is a resource
management technique used in computer programming to efficiently implement a
"duplicate" or "copy" operation on modifiable resources.

• If a resource is duplicated but not modified, it is not necessary to create a new

resource; the resource can be shared between the copy and the original.

• Modifications must still create a copy, hence the technique: the copy operation is
deferred to the first write.

• By sharing resources in this way, it is possible to significantly reduce the resource

consumption of unmodified copies, while adding a small overhead to resourcemodifying
operations.

Allocation of Frames
• An important aspect of operating systems, virtual memory is implemented using demand
paging. Demand paging necessitates the development of a pagereplacement algorithm
and a frame allocation algorithm.

• Frame allocation algorithms are used if you have multiple processes; it help decide how
many frames to allocate to each process.

*For Internal Circulation Only 109

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• There are various constraints to the strategies for the allocation of frames.
• You cannot allocate more than the total number of available frames.
• At least a minimum number of frames should be allocated to each process. This
constraint is supported by two reasons. The first reason is, as less number of frames are
allocated, there is an increase in the page fault ratio, decreasing the performance of the
execution of the process. Secondly, there should be enough frames to hold all the
different pages that any single instruction can reference.

• Allocation of frames is achieved by using algorithms like Equal allocation and

Proportional allocation

Thrashing
• Thrashing is a condition or a situation when the system is spending a major portion
of its time servicing the page faults, but the actual processing done is very negligible.

• The basic concept involved is that if a process is allocated too few frames, then
there will be too many and too frequent page faults. As a result, no useful work would be
done by the CPU and the CPU utilization would fall drastically.

• The long-term scheduler would then try to improve the CPU utilization by loading
some more processes into the memory thereby increasing the degree of multiprogramming.
This would result in a further decrease in the CPU utilization triggering a chained reaction
of higher page faults followed by an increase in the degree of multiprogramming, called
Thrashing.
File Management System File
• File system is the most visible aspect of an operating system. It provides the mechanism
for online.

• storage and access to both data and programs of the operating system and all the users of
the operating system.

• The file system consists of two distinct parts

• A collection of files storing related data

*For Internal Circulation Only 110

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• A directory structure- which organizes and provides information about all the files in the
system.

File concept
• A file is a named collection of related information that is recorded on the secondary
• storage
. • A file directory is a group of files organized together an entry within a directory refers
to

• the directory or another file. Hence, a tree structure or hierarchy can be formed. • The
directories are used to group files belonging to different applications or users

• The Directory enables files to be separated based on user and user application. Thus
simplifying system management issues like backup recovery, security, integrity, name
collision problems (file name clashes), housekeeping of files, etc.

File Attributes
• A file’s attributes vary from one operating system to another but typically consist of the
following

• Name: the symbolic file name is the only information kept in human-readable form.
• Identifier: this unique tag, usually a number, identifies the file within the file system. It
is the non-human-readable form.

• Type: this information is needed for systems that supports different types of files.
• Location: This information is a pointer to a device and to the location of the file on that
device.

• Size: the current size of the file (in bytes, words, or blocks) and possibly the maximum
allowed size is included in this attribute.

• Protection: Access control information determines who can do reading, writing

executing, and so on.

• Time, Date, and user identification: this information may be kept for creation,
last

*For Internal Circulation Only 111

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• modification, and last use. These data can be useful for protection, security, and usage
monitoring.

File Operations
To define a file properly, we need to consider the following operations that can be
performed on files.
• Creating a file

• Two steps are necessary to create a file. First, space in the file system
• must be found for the file. Second, an entry for a new file must be made in the directory.
• Writing a file:
To write a file, we make a system call specifying both the name of the file

• and the information to be written to the file.

• Given the name of the file, the system searches the directory to find the file’s location.
• The system must keep the write pointer to the location in the file where the next write is
• to take place. The write pointer must updated whenever the write occurs.
• Reading a file:
• To read from a file, we use a system call that specifies the name of the file and where
(memory) the next block of the file should be put. Again, the directory is searched for
the associated entry, and the system needs to keep a read pointer to the location in the
file where the next read is to take place.

• Repositioning within a file

• The directory is searched for the appropriate entry, and the current-file-position pointer
is repositioned to a given value.

• Repositioning within a file need not involve any actual I/O. This file operation is also
called a file seek.

• Deleting a file

• To delete a file, we search the directory for the named file.

• Having found the associated directory entry, we release all file space. So, that it can be
reused by other files and erase the directory entry.

*For Internal Circulation Only 112

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Truncating a file
• The user may want to erase the contents of the file but keep its attributes.
• Rather than forcing the user to delete the file and then recreate it, this function allows all
attributes to remain unchanged except for file length.
File Types
• A common technique for implementing file types is to include the type as part of the file
• name.
• The name is split into two parts: a name and an extension, usually separated by a period
character.

• In this way, the user and the operating system can tell from the name alone what type of
the file is.

• Some of the file types are as below.

*For Internal Circulation Only 113

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• File name examples include [Link], [Link], and Reader thread.c. The system
uses the extension to indicate the type of operations that can be done on that file.

• Only a file with .com, .exe, or .bat extension can be executed, for instance. The .com and
.exe files are two forms of binary executable files, whereas a .bat file is a batch file
containing, in ASCII format, commands to the operating system

File Access Methods

• Sequential Access Method

• The file contains the information but when it is required to used this information can be
accessed by the access methods and read into the computer memory. • Some system
provides only one access method and some provide more than one access method to
access the file.

• A sequential access is that in which the records are accessed in some sequence, i.e., the
information in the file is processed in order, one record after the other.
This access method is the most primitive one.
• The idea of Sequential access is based on the tape model which is a sequential access
device. We consider the Sequential access method to be best because most of the records
in a file are to be processed. For example, transaction files.

• Example: Compilers usually access files in this fashion.

Direct or Random Access Methods

• Sometimes it is not necessary to process every record in a file. It is not necessary
to process all the records in the order in which they are present in the memory. In all such
cases, direct access is used.

• The disk is a direct access device which gives us the reliability to random access
of any file block. In the file, there is a collection of physical blocks and the records of those
blocks.

*For Internal Circulation Only 114

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Ex: Databases are often of this type since they allow query processing that involves
immediate access to large amounts of information. All reservation systems fall into this
category.

• Not all operating systems support direct access files. The sequential and direct
access of the file is defined at the time of creation and accessed accordingly later. Direct
access to a sequential file is not possible but Sequential access to a direct access file is
possible

Index Access Method

• An indexed file is a computer file with an index that allows easy random access to
any record given its file key.

• The key is an attribute that uniquely identifies a record. We can say that If more
than one index is present the other ones are alternate indexes. The creation of the indexes
is done with the file but maintained by the system.

Index Sequential Access Method

• The index sequential access method is a modification of the direct access method.
It is a kind of combination of both sequential access as well as direct access.

• The main idea of this method is to first access the file directly and then it accesses
sequentially. In this access method, it is necessary to maintain an index. The index is
nothing but a pointer to a block. The direct access of the index is made to access a record
in a file.

• The information which is obtained from this access is used to access the file.
Sometimes the indexes are very big. So to maintain all these hierarchies of indexes are
built in which one direct access of an index leads to information of another index access.

• The main advantage in this type of access is that both direct and sequential access
of files is possible with the help of this method.

Directory overview
• A file directory is a group of files organized together on entry within a directory or
another file. Hence, a tree structure or hierarchy can be formed.

*For Internal Circulation Only 115

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The directories are used to group files belonging to different applications or users.
• Directories enable files to be separated based on user and user applications. Thus,
simplifying system management issues like backup recovery, security, integrity, name
collision problems (file name clashes), etc • The device directory records information
like name, location, size, and type for all the files on the partition. A root refers to the
part of the disk from where the root directory begins, which points to the user directories,
the root directory is distinct from sub-directories in that it is in a fixed position and of
fixed size.

• Following are the operations that can be performed on a directory or file system. • Search
for file: we need to be able to search a directory structure to find the entry for a particular
file. Since files have symbolic names and similar names may indicate a relationship
between files, we may want to be able to find all files whose names match a particular
pattern.

• Create a file: new files need to be created and added to the directory.
• Delete a file: when a file is no longer needed, we want to be able to remove it from the
directory.

• List a directory: we need to be able to list the files in a directory and the contents of the
directory entry for each file in the list.

• Rename a file: because the name of the file represents its contents to its users, we must
be able to change the name when the contents or use of the file changes. • Renaming a
file: This may also allow its position within the directory structure to be changed.

• Traverse the file system: we may wish to access every directory and every file within a
directory structure. Often, we do this by copying all files to magnetic tape. This technique
provides a backup copy in case of system failure.

*For Internal Circulation Only 116

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Logical directory structure

The most common schemes for defining logical directory structure are as follows.

Single-level directory

• In this a single directory is maintained for all the users.

• Naming problem: Users cannot have the same name for two files.
• Grouping problem: Users cannot group files according to their needs.

Two-level directory

• In this separate directories for each user are maintained.

• Path name: Due to two levels there is a path name for every file to locate that file.
• Now, we can have the same file name for different users.
• Searching is efficient in this method.

*For Internal Circulation Only 117

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Tree-structured directory

• Directory is maintained in the form of a tree.

• Searching is efficient and also there is grouping capability. We have an absolute or
relative path name for a file.

File System Mounting

• Mounting is a process by which the operating system makes files and directories
on a storage device (such as a hard drive, CD-ROM, or network share) available for users
to access via the computer's file system.

• In general, the process of mounting comprises the operating system acquiring

access to the storage medium; recognizing, reading, and processing file system structure
and metadata on it before registering them to the virtual file system (VFS) component.

• The location in VFS where the newly mounted medium was registered is called the
mount point; when the mounting process is completed, the user can access files and
directories on the medium from there.

• An opposite process of mounting is called unmounting, in which the operating

system cuts off all user access to files and directories on the mount point, writes the
remaining queue of user data to the storage device, refreshes file system metadata, then
relinquishes access to the device, making the storage device safe for removal.

*For Internal Circulation Only 118

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Normally, when the computer is shutting down, every mounted storage will
undergo an unmounting process to ensure that all queued data got written, and to preserve
integrity of file system structure on the media.
File sharing is the public or private sharing of computer data or space in a network with
various levels of access privilege.

• While files can easily be shared outside a network (for example, simply by handing
or mailing someone your file on a diskette), the term file sharing almost always means
sharing files in a network, even if in a small local area network.

• File sharing allows a number of people to use the same file or file by some
combination of being able to read or view it, write to or modify it, copy it, or print it.

• Typically, a file sharing system has one or more administrators. Users may all have
the same or may have different levels of access privilege. File sharing can also mean
having an allocated amount of personal file storage in a common file system.
• FTP can be used to access (read and possibly write to) files shared among a
particular set of users with a password to gain access to files shared from an FTP server
site.

• Most Web site developers use FTP to upload new or revised Web files to a Web
server, and indeed the World Wide Web itself can be thought of as large-scale file sharing
in which requested pages or files are constantly being downloaded or copied down to the
Web user.

• File sharing implies a system in which users write to as well as read files or in
which users are allotted some amount of space for personal files on a common server,
giving access to other users as they see fit.

• Any multi-user operating system will provide some form of file sharing. Among
the best known network file systems is (not surprisingly) the Network File System (NFS).

• Originally developed by Sun Microsystems for its UNIX-based systems, it lets you
read and, assuming you have permission, write to sharable files as though they were on
your own personal computer.

*For Internal Circulation Only 119

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Files can also be shared in file systems distributed over different points in a
network. File sharing is involved in groupware and several other types of applications.

Protection
• When information is stored in a computer system, we want to keep it safe from physical
damage (the issue of reliability) and improper access (the issue of protection).

• Reliability is generally provided by duplicate copies of files.

• Many computers have systems programs that automatically (or through computer
operator intervention) copy disk files to tape at regular intervals (once per day or week
or month) to maintain a copy should a file system be accidentally destroyed.

• File systems can be damaged by hardware problems (such as errors in reading or

writing), power surges or failures, head crashes, dirt, temperature extremes, and
vandalism. Files may be deleted accidentally.

• Bugs in the file-system software can also cause file contents to be lost.
• Protection can be provided in many ways. For a single-user laptop system, we might
protect by locking the computer in a desk drawer or file cabinet.
In a larger multiuser system, however, other mechanisms are needed.

• Several different types of file operations may be controlled as below.

• Read. Read from the file.
• Write. Write or rewrite the file.
• Execute. Load the file into memory and execute it.
• Append. Write new information at the end of the file.

• Delete. Delete the file and free its space for possible reuse.

• List. List the name and attributes of the file.

File Allocation Methods

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

*For Internal Circulation Only 120

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Contiguous Allocation

• Linked Allocation

• Indexed Allocation

The main idea behind these methods is to provide:

• Efficient disk space utilization.

• Fast access to the file blocks.

All three methods have their advantages and disadvantages as discussed below:

1. Contiguous Allocation
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a
file requires n blocks and is given a block b as the starting location, then the blocks
assigned to the file will be b, b+1, b+2,……b+n-1. This means that given the starting block
address and the length of the file (in terms of blocks required), we can determine the blocks
occupied by the file.

The directory entry for a file with contiguous allocation contains

• Address of starting block

• Length of the allocated portion.

The file ‘mail’ in the following figure starts from block 19 with length = 6 blocks.

Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks

*For Internal Circulation Only 121

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages:
• Both the Sequential and Direct Accesses are supported by this. For direct access,
the address of the kth block of the file which starts at block b can easily be obtained
as (b+k).
• This is extremely fast since the number of seeks are minimal because of contiguous
allocation of file blocks.
Disadvantages:
• This method suffers from both internal and external fragmentation. This makes it
inefficient in terms of memory utilization.
• Increasing file size is difficult because it depends on the availability of contiguous
memory at a particular instance.
2. Linked List Allocation
• In this scheme, each file is a linked list of disk blocks that need not be contiguous.
The disk blocks can be scattered anywhere on the disk. The directory entry contains
a pointer to the starting and ending file blocks. Each block contains a pointer to the
next block occupied by the file.

*For Internal Circulation Only 122

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The file ‘jeep’ in the following image shows how the blocks are randomly
distributed. The last block (25) contains -1 indicating a null pointer and does not
point to any other block.

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

*For Internal Circulation Only 123

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

3. Indexed Allocation

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

Advantages:
• This supports direct access to the blocks occupied by the file and therefore provides
fast access to the file blocks.
• It overcomes the problem of external fragmentation.

Disadvantages:
• The pointer overhead for indexed allocation is greater than linked allocation.
• For very small files, say files that expand only 2-3 blocks, the indexed allocation
would keep one entire block (index block) for the pointers which
• is inefficient in terms of memory utilization. However, in linked allocation, we lose
the space of only 1 pointer per block.

*For Internal Circulation Only 124

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Free Space Management in Operating System

Free space management is a critical aspect of operating systems as it involves managing

the available storage space on the hard disk or other secondary storage devices. The
operating system uses various techniques to manage free space and optimize the use of
storage devices. Here are some of the commonly used free space management techniques:

1. Bitmap or Bit vector

A Bitmap or Bit Vector is a series or collection of bits where each bit corresponds to a disk
block. The bit can take two values: 0 and 1: 0 indicates that the block is free and 1 indicates
an allocated block. The given instance of disk blocks on the disk in Figure 1 (where green
blocks are allocated) can be represented by a bitmap of 16 bits as 1111000111111001.

2. Linked List

In this approach, the free disk blocks are linked together i.e. a free block contains a pointer
to the next free block. The block number of the very first disk block is stored at a separate
location on the disk and is also cached in memory.

*For Internal Circulation Only 125

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

In Figure-2, the free space list head points to Block 5 which points to Block 6, the next
free block and so on. The last free block would contain a null pointer indicating the end of
free list. A drawback of this method is the I/O required for free space list traversal.
Advantages:

• The total available space is used efficiently using this method.

• Dynamic allocation in Linked List is easy, thus can add the space as per the
requirement dynamically.
Disadvantages:

• When the size of the Linked List increases, the headache of miniating pointers also
increases.
• This method is not efficient during iteration of each block of memory.

Grouping
This approach stores the address of the free blocks in the first free block. The first free
block stores the address of some, say n free blocks. Out of these n blocks, the first n-1
blocks are free and the last block contains the address of the next free n blocks. An

*For Internal Circulation Only 126

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

advantage of this approach is that the addresses of a group of free disk blocks can be
found easily.

Advantage:

• Finding free blocks in massive amounts can be done easily using this method.
Disadvantage:

• The only disadvantage is, that we need to alter the entire list if any of the blocks of
the list is occupied.
Counting
This approach stores the address of the first free disk block and a number n of free
contiguous disk blocks that follow the first block. Every entry in the list would contain:

• Address of first free disk block.

• A number n.

Advantages:

• Using this method, a group of entire free blocks can take place easily and Fastly.
• The list formed in this method is especially smaller in size.

Disadvantage:

• The first free block in this method, keeps account of other free blocks. Thus, due
to that one block the space requirement is more.
Recovery

File System Consistency Checker:

FSCK is one approach still used by older Linux-based systems to find and repair
inconsistencies. It is not a complete solution and may still have inodes pointing to garbage
data. The major focus is to make the metadata internally consistent.

*For Internal Circulation Only 127

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The following are the checks that FSCK performs to achieve consistency:

• SuperblockChecks:
FSCK performs a sanity check to see if the file size is greater than the number of
blocks allocated. In this case, it tries to find the suspect superblock and use an
alternate copy instead.
• FreeBlockChecks:
FSCK also scans inodes to ensure that blocks in inodes are marked allocated.
• InodeStateChecks:

FSCK checks inodes for corruption. Corrupted inodes are simply cleared.

• InodeLinkChecks:
FSCK counts the number of links to an inode and modifies the inode count. If an
allocated inode has no directory or file referring to it, FSCK moves it to the lost
and found directory.
• DuplicatePointers:
FSCK checks duplicate pointers. For example, if two inodes have pointers to the
same data block, one of the inodes can be deleted.
• BadBlocks:
A bad pointer is simply one that points to a memory address that is out of range. In
this case, FSCK deletes the pointer.
• DirectoryChecks:
FSCK makes sure the directory format is correct, e.g. they should start with “.” and
“..”.
Advantages of FSCK:

• It requires little overhead space.

Disadvantages of FSCK:
• Scanning the disk, again and again, is slow and infeasible for large disk sizes.
• It requires a heavy understanding and prior knowledge of the file system. As file
systems continue to evolve, it is difficult to keep track of every nuance.

Backup and Recovery

Data backup is the process of storing additional copies of your data in physical or virtual
locations distinct from your data files in storage. Typically, backup data includes all the

*For Internal Circulation Only 128

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

data – documents, media files, configuration and registry files, machine images, etc.
required to perform the workload on your server. In essence, any data that you desire to
keep can be saved as backup data.

The main goal of backup is to generate a copy of the data that can be recovered if the
primary data fails. Failure can be – hardware or software failures, data corruption, or a
human-initiated event such as an attack (virus or malware) or data deletion by an accident.

The act of backing up your data in the case of a loss and putting up secure mechanisms
that allow you to recover your data, as a result, this process is known as data backup and
recovery. It copies and preserves data in order to keep it available in the event of data loss
or damage. Suppose you have backed up your data, so you can only recover data from a
previous point in time. Data backup is a type of disaster recovery that should be included
in every plan for disaster recovery.

Backup copies should be made on a constant, regular basis for optimal outcomes since this
will reduce the amount of data lost between backups. When recovering from a backup, the
longer the gap between backup copies, the greater the risk of data loss.
Recovery

Data recovery, often known as a restore, is required when data of any sort is no longer
readable or has been corrupted by a malicious alteration. The act, process, or occurrence
of recovering data following inadvertent loss or corruption is known as recovery. The cost
of recovering data is high.

*For Internal Circulation Only 129

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Causes Of Data Recovery:

In this hierarchy, all the storage devices are arranged according to speed and cost. The
higher levels are expensive, but they are fast. As we move down the hierarchy, the cost per
bit generally decreases, whereas the access time generally increases. The storage systems
above the Electronic disk are Volatile, whereas those below are Non-Volatile.

An Electronic disk can be designed to be either Volatile or Non-Volatile. During normal

operation, the electronic disk stores data in a large DRAM array, which is Volatile.
However many electronic disk devices contain a hidden magnetic hard disk and a battery
for backup power. If external power is interrupted, the electronic disk controller copies the
data from RAM to the magnetic disk. When external power is restored, the controller
copies the data back into the RAM. The design of a complete memory system must balance
all the factors. It must use only as much expensive memory as necessary while providing
as much inexpensive, Non-Volatile memory as possible. Caches can be installed to
improve performance where a large access time or transfer-rate disparity exists between
two components.

*For Internal Circulation Only 130

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Magnetic Disk

A magnetic Disk is a type of secondary memory that is a flat disc covered with a magnetic
coating to hold information. It is used to store various programs and files. The polarized
information in one direction is represented by 1, and vice versa. The direction is indicated
by 0.

Magnetic disks are less expensive than RAM and can store large amounts of data, but the
data access rate is slower than main memory because of secondary memory. Data can be
modified or can be deleted easily in the magnetic disk memory. It also allows random
access to data.
Floppy Disks

A floppy disk is a detachable, flexible magnetic storage device that may hold computer
files or other electronic data. It is composed of a flexible and thin magnetic storage disk
that is enclosed inside a rectangular plastic carrier that has a fabric lining for increased
sturdiness. Data can be read and written because the disk is magnetic. Writes and reads
floppy disks with a floppy disk drive.

Floppy disks also known as floppy diskettes, floppy disks or floppy disks, are a type of
storage medium that can read data storage information and are used to store electronic
data. Unlike CD-ROM, it was 8 inches in diameter when it was initially created, and users
could not write data to it.

Although later versions of this disk could hold up to 800KB of data, it could only hold
80KB at a time. These days, network file transfers and USB devices have taken the position
of floppy disks, however they are no longer in use.

Types of Floppy Disk

Here are the four types of Floppy Disk.

• 8-inch Drive: The First ever floppy design to be adopted as a read-only format
before being able to read and write which was introduced in the early 1970s was

*For Internal Circulation Only 131

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

the 8-inch Drive. The physical characteristic that permitted the floppy drive series
its name was floppy.
• Zip Drive: The Zip drive was introduced by Iomega Corporation. Since zip drives
were peripheral, they were primarily able to enhance an alreadyexisting system.
Due to its high cost, this drive was not widely utilized and never really took off as
a storage device.
• 3.5" Drive: 3.5" Drive is another kind of floppy disk. Conversely, a 3.5′′ drive is
typically found in desktop computers and servers and has a bigger diameter of 3.5
inches.
• 5.25" Drive: A 5.25" is a floppy disk drive that was a common computer accessory.
During the early nineties, computers with capacities ranging from 360 kilobytes to
1.2 gigabytes were also armed with floppy disk drives.

Advantages of Floppy Disk

Below are some advantages of Floppy Disk.

• Flexibility and comparability: Floppy drives have several benefits, one of which
is their flexibility and comparably small size. 3.5" Drive floppy disks are smaller
in size than Compact Disks.
• Cost: Less costly than other storage devices portable and non-volatile which means
that data stored on them won't be lost when the system is powered down and
compatible with the majority of computers.
• Compose Protection: Floppy disks also include a little score that provides a
feature called Write Protection, even with plastic wrapping.
• Boot Disk: Floppy disk drives are often situated above the primary hard drives in
the boot order sequence.

*For Internal Circulation Only 132

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Disadvantages of Floppy Disk

Below are some disadvantages of Floppy Disk.

• Capacity: The main disadvantage of these disks is their smaller capacity for
storing data when compared to more modern technologies like CDs, which have
an average capacity of 650–700 MB per disk.
• Dependability: A floppy disk drive and a variable capacity source were absent
from a vast majority of PCs.
• Easily Broke: The floppy disk, which is extremely flexible and fragile, was made
using a plastic shell. If someone handles it carelessly, it might break easily.
• Data Deletion: If the disk comes into touch with a magnetic field side, then data
may be deleted.
• Magnetic drums, magnetic tape, and magnetic disks are types of magnetic memory.
These memories use the property of magnetic memory. Here, we have explained
about magnetic tape in brief.

Magnetic Tape memory:

In magnetic tape, only one side of the ribbon is used for storing data. It is a sequential
memory that contains a thin plastic ribbon to store data and is coated by magnetic
oxide. Data read/write speed is slower because of sequential access. It is highly reliable
and requires a magnetic tape drive to write and read data.
Advantages:

1. These are inexpensive, i.e., low-cost memories.

2. It provides backup or archival storage.
3. It can be used for large files.
4. It can be used for copying from disk files.
5. It is a reusable memory.
6. It is compact and easy to store on racks.

*For Internal Circulation Only 133

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Disadvantages:

1. Sequential access is the disadvantage, means it does not allow access randomly or
directly.
2. It requires caring to store, i.e., vulnerable humidity, dust-free, and suitable
environment.
3. It stored data cannot be easily updated or modified, i.e., difficult to make updates
on data.

Disk Scheduling Algorithms

There are several Disk Several Algorithms. We will discuss in detail each one of them.

• FCFS (First Come First Serve)

• SSTF (Shortest Seek Time First)

• SCAN

• C-SCAN

• LOOK

• C-LOOK

1. FCFS (First Come First Serve)

FCFS is the simplest of all Disk Scheduling Algorithms. In FCFS, the requests are
addressed in the order they arrive in the disk queue. Let us understand this with the help
of an example.

*For Internal Circulation Only 134

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Example: Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is: 50

So, total overhead movement (total distance covered by the disk arm) =
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

Advantages of FCFS Here are some of the advantages of First Come First Serve.

• Every request gets a fair chance

• No indefinite postponement

Disadvantages of FCFS

Here are some of the disadvantages of First Come First Serve.

• Does not try to optimize seek time

• May not provide the best possible service

2. SSTF (Shortest Seek Time First)

In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed
first. So, the seek time of every request is calculated in advance in the queue and then they

*For Internal Circulation Only 135

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

are scheduled according to their calculated seek time. As a result, the request near the disk
arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases
the average response time and increases the throughput of the system. Let us understand
this with the help of an example.

Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is: 50

total overhead movement (total distance covered by the disk arm) = (50-43)+(43-
24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

Advantages of Shortest Seek Time First

Here are some of the advantages of Shortest Seek Time First.

• The average Response Time decreases

• Throughput increases

Disadvantages of Shortest Seek Time First

Here are some of the disadvantages of Shortest Seek Time First.

• Overhead to calculate seek time in advance

*For Internal Circulation Only 136

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Can cause Starvation for a request if it has a higher seek time as compared to
incoming requests

• The high variance of response time as SSTF favors only some requests

3. SCAN

In the SCAN algorithm the disk arm moves in a particular direction and services the
requests coming in its path and after reaching the end of the disk, it reverses its
direction and again services the request arriving in its path. So, this algorithm works
as an elevator and is hence also known as an elevator algorithm. As a result, the
requests at the midrange are serviced more and those arriving behind the disk arm will
have to wait.

Example:

SCAN Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the

Read/Write arm is at 50, and it is also given that the disk arm should move “towards
the larger value”.

Therefore, the total overhead movement (total distance covered by the disk arm) is
calculated as

= (199-50) + (199-16) = 332

*For Internal Circulation Only 137

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Advantages of SCAN Algorithm

Here are some of the advantages of the SCAN Algorithm.

• High throughput

• Low variance of response time • Average response time

Disadvantages of SCAN Algorithm

Here are some of the disadvantages of the SCAN Algorithm.

• Long waiting time for requests for locations just visited by disk arm

4. C-SCAN

In the SCAN algorithm, the disk arm again scans the path that has been scanned, after
reversing its direction. So, it may be possible that too many requests are waiting at the
other end or there may be zero or few requests pending at the scanned area.

These situations are avoided in the CSCAN algorithm in which the disk arm instead of
reversing its direction goes to the other end of the disk and starts servicing the requests
from there. So, the disk arm moves in a circular fashion and this algorithm is also similar
to the SCAN algorithm hence it is known as C-SCAN (Circular SCAN).

Example:

*For Internal Circulation Only 138

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Circular SCAN

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the

Read/Write arm is at 50, and it is also given that the disk arm should move “towards
the larger value”.

So, the total overhead movement (total distance covered by the disk arm) is calculated
as: =(199-50) + (199-0) + (43-0) = 391
Advantages of C-SCAN Algorithm

Here are some of the advantages of C-SCAN.

• Provides more uniform wait time compared to SCAN.

5. LOOK

LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the
difference that the disk arm in spite of going to the end of the disk goes only to the last
request to be serviced in front of the head and then reverses its direction from there

*For Internal Circulation Only 139

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

only. Thus it prevents the extra delay which occurred due to unnecessary traversal to
the end of the disk.

Example:

LOOK Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the

Read/Write arm is at 50, and it is also given that the disk arm should move “towards
the larger value”.

So, the total overhead movement (total distance covered by the disk arm) is calculated
as:

= (190-50) + (190-16) = 314

*For Internal Circulation Only 140

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

6. C-LOOK

As LOOK is similar to the SCAN algorithm, in a similar way, C-LOOK is similar to

the CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to
the end goes only to the last request to be serviced in front of the head and then from
there goes to the other end’s last request. Thus, it also prevents the extra delay which
occurred due to unnecessary traversal to the end of the disk.

Example:

1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the

Read/Write arm is at 50, and it is also given that the disk arm should move
“towards the larger value”

6. C-LOOK
So, the total overhead movement (total distance covered by the disk arm) is calculated
as
= (190-50) + (190-16) + (43-16) = 341

Disk Management in Operating System

*For Internal Circulation Only 141

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Disk management is one of the critical operations carried out by the operating system.
It deals with organizing the data stored on the secondary storage devices which
includes the hard disk drives and the solid-state drives. It also carries out the function
of optimizing the data and making sure that the data is safe by implementing various
risk management techniques. We will learn more about disk management and its
related techniques found in operating systems.

system is responsible for configuring the file system, ensuring the safety and reliability
of reading and write operations to secondary storage, and maintains access times (the
time required to write data to or read data from secondary storage).

Disk Management of the Operating System Includes:

• Disk Format

• Booting from disk

• Bad block recovery

The low-level format or physical format:

Divides the disk into sectors before storing data so that the disk controller can read
and write Each sector can be:

The header retains information, data, and error correction code (ECC) sectors of data,
typically 512 bytes of data, but optional disks use the operating system’s own data
structures to preserve files using disks.

It is conducted in two stages:

1. Divide the disc into multiple cylinder groups. Each is treated as a logical disk.

*For Internal Circulation Only 142

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

2. Logical format or “Create File System”. The OS stores the data structure of the
first file system on the disk. Contains free space and allocated space.

For efficiency, most file systems group blocks into clusters. Disk I / O runs in blocks.
File I / O runs in a cluster.

For example, the sizes can be 256,512, and 1,024 bytes. If the disk is formatted with a
larger sector size, fewer sectors can fit on each track.

As a result, fewer headers and trailers are written on each track and more space is
obtainable for user data. – Some operating systems can handle a sector size of 512
bytes.

The operating system keeps its data structures on disk before it uses the disk to store
the files. It performs this with the following two steps:

1. It partitions the disk into one or more groups of cylinders. Each partition is treated
by the OS as a separate disk.

2. Logical formatting: This means the creation of a file system.

In order to increase efficiency, the file system groups blocks in chunks called as
clusters.

Some operating systems give special programs the ability to use a disk partition as a
large sequential array of logical blocks, without any file-system data structures. This
array is sometimes called the raw disk, and I/O to this array is called as raw I/O.

*For Internal Circulation Only 143

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Boot block:

• When the computer is turned on or restarted, the program stored in the initial
bootstrap ROM finds the location of the OS kernel from the disk, loads the kernel
into memory, and runs the OS. start.

• To change the bootstrap code, you need to change the ROM and hardware chip.
Only a small bootstrap loader program is stored in ROM instead.

• The full bootstrap code is stored in the “boot block” of the disk.

• A disk with a boot partition is called a boot disk or system disk.

• The bootstrap program is required for a computer to initiate the booting after it is
powered up or rebooted.

• It initializes all components of the system, from CPU registers to device

controllers and the contents of main memory, and then starts the operating system.

• The bootstrap program then locates the OS kernel on disk, loads that kernel into
memory, and jumps to an initial address to start the operatingsystem execution.

• The Read Only Memory (ROM) does not require initialization and is at a fixed
location that the processor can begin executing when powered up or reset.
Therefore bootstrap is stored in ROM.

• Because of read only feature of ROM; it cannot be infected by a computer virus.

The difficulty is that modification of this bootstrap code requires changing the
ROM hardware chips.

• Therefore, most systems store a small bootstrap loader program in the boot ROM
which invokes and bring full bootstrap program from disk into main memory.

*For Internal Circulation Only 144

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• The modified version of full bootstrap program can be simply written onto the
disk.

• The fixed storage location of full bootstrap program is in the “boot blocks”.

• A disk that has a boot partition is called a boot disk or system disk.

Bad Blocks:

• Disks are error-prone because moving parts have small tolerances.

• Most disks are even stuffed from the factory with bad blocks and are handled in a
variety of ways.

• The controller maintains a list of bad blocks.

• The controller can instruct each bad sector to be logically replaced with one of the
spare sectors. This scheme is known as sector sparing or transfer.

• A soft error triggers the data recovery process.

• However, unrecoverable hard errors may result in data loss and require manual
intervention.

• Failure of the disk can be:

1. Complete, means there is no way other than replacing the disk. Back up of content
must be taken on new disk.

2. One or more sectors become faulty.

3. After manufacturing, the bad blocks exist. Depending on the disk and controller in
use, these blocks are handled in a different ways.

*For Internal Circulation Only 145

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Disk management in operating systems involves organizing and maintaining the data
on a storage device, such as a hard disk drive or solid-state drive. The main goal of
disk management is to efficiently utilize the available storage space and ensure data
integrity and security.

Some common disk management techniques used in operating systems include:

1. Partitioning: This involves dividing a single physical disk into multiple logical
partitions. Each partition can be treated as a separate storage device, allowing for
better organization and management of data.

2. Formatting: This involves preparing a disk for use by creating a file system on it.
This process typically erases all existing data on the disk.

3. File system management: This involves managing the file systems used by the
operating system to store and access data on the disk. Different file systems have
different features and performance characteristics.

4. Disk space allocation: This involves allocating space on the disk for storing files
and directories. Some common methods of allocation include contiguous
allocation, linked allocation, and indexed allocation.

5. Disk defragmentation: Over time, as files are created and deleted, the data on a disk
can become fragmented, meaning that it is scattered across the disk. Disk
defragmentation involves rearranging the data on the disk to improve performance.

Advantages of disk management include:

1. Improved organization and management of data.

2. Efficient use of available storage space.

3. Improved data integrity and security.

*For Internal Circulation Only 146

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

4. Improved performance through techniques such as defragmentation.

Disadvantages of disk management include:

1. Increased system overhead due to disk management tasks.

2. Increased complexity in managing multiple partitions and file systems.

3. Increased risk of data loss due to errors during disk management tasks.

4. Overall, disk management is an essential aspect of operating system management

and can greatly improve system performance and data integrity when implemented
properly.

Swap-Space Management in Operating system

Swapping is a memory management technique used in multi-programming to increase the

number of processes sharing the CPU. It is a technique of removing a process from the
main memory and storing it into secondary memory, and then bringing it back into the
main memory for continued execution. This action of moving a process out from main
memory to secondary memory is called Swap Out and the action of moving a process out
from secondary memory to main memory is called Swap In.

Swap-space management is a technique used by operating systems to optimize memory

usage and improve system performance. Here are some advantages and disadvantages of
swap-space management:

Advantages:

1. Increased memory capacity: Swap-space management allows the operating system

to use hard disk space as virtual memory, effectively increasing the available
memory capacity.

*For Internal Circulation Only 147

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

2. Improved system performance: By using virtual memory, the operating system can
swap out less frequently used data from physical memory to disk, freeing up space
for more frequently used data and improving system performance.
3. Flexibility: Swap-space management allows the operating system to dynamically
allocate and deallocate memory as needed, depending on the demands of running
applications.

Disadvantages:

Slower access times: Accessing data from disk is slower than accessing data from physical
memory, which can result in slower system performance if too much swapping is required.
Increased disk usage: Swap-space management requires disk space to be reserved for use
as virtual memory, which can reduce the amount of available space for other data storage
purposes.
Risk of data loss: In some cases, if there is a problem with the swap file, such as a disk
error or corruption, data may be lost or corrupted.
Overall, swap-space management is a useful technique for optimizing memory usage and
improving system performance. However, it is important to carefully manage swap space
allocation and monitor system performance to ensure that excessive swapping does not
negatively impact system performance.

Swap-Space :
The area on the disk where the swapped-out processes are stored is called swap space.

Swap-space management :
Swap-Space management is another low-level task of the operating system. Disk space is
used as an extension of main memory by the virtual memory. As we know the fact that
disk access is much slower than memory access, In the swap space management we are
using disk space, so it will significantly decrease system performance. Basically, in all our
systems we require the best throughput, so the goal of this swap-space implementation is
to provide the virtual memory the best throughput. In this article, we are going to discuss

*For Internal Circulation Only 148

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

how swap space is used, where swap space is located on disk, and how swap space is
managed.

Swap-Space Use :
Swap space is used by the different operating systems in various ways. The systems which
are implementing swapping may use swap space to hold the entire process which may
include image, code, and data segments. Paging systems may simply store pages that have
been pushed out of the main memory. The need to swap space on a system can vary from
megabytes to gigabytes but it also depends on the amount of physical memory, the virtual
memory it is backing, and how it is using the virtual memory.

It is safer to overestimate than to underestimate the amount of swap space required because
if a system runs out of swap space it may be forced to abort the processes or may crash
entirely. Overestimation wastes disk space that could otherwise be used for files, but it
does not harm other.

The following table shows a different system using an amount of swap space:

*For Internal Circulation Only 149

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Figure – Different systems using the amount of swap space.

• Explanation:
• Solaris, setting swap space equal to the amount by which virtual memory
exceeds pageable physical memory. In the past, Linux has suggested setting swap
space to double the amount of physical memory. Today, this limitation is gone,
and most Linux systems use considerably less swap space.
• Including Linux, some operating systems; allow the use of multiple swap
spaces, including both files and dedicated swap partitions. The swap spaces are
placed on the disk so the load which is on the I/O by the paging and swapping will
spread over the system’s bandwidth.
• Swap-Space Location :

• Figure – Location of swap-space

• A swap space can reside in one of the two places

• Normal file system

• Separate disk partition

Let, if the swap space is simply a large file within the file system. To create it, name it, and
allocate its space normal file-system routines can be used. This approach, though easy to
implement, is inefficient. Navigating the directory structures and the disk-allocation data

*For Internal Circulation Only 150

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

structures takes time and extra disk access. During reading or writing of a process image,
external fragmentation can greatly increase swapping times by forcing multiple seeks.

There is also an alternate to create the swap space which is in a separate raw partition.
There is no presence of any file system in this place. Rather, a swap space storage manager
is used to allocate and de-allocate the blocks. from the raw partition. It uses the algorithms
for speed rather than storage efficiency because we know the access time of swap space is
shorter than the file system. By this Internal fragmentation increases, but it is acceptable
because the life span of the swap space is shorter than the files in the file system. The raw
partition approach creates a fixed amount of swap space in case of disk partitioning.

Some operating systems are flexible and can swap both in raw partitions and in the file
system space, for example, Linux.

Swap-Space Management: An

Example –
The traditional UNIX kernel started with an implementation of swapping that copied the
entire process between contiguous disk regions and memory. UNIX later evolved to a
combination of swapping and paging as paging hardware became available. In Solaris, the
designers changed standard UNIX methods to improve efficiency. More changes were
made in later versions of Solaris, to improve the efficiency.

Linux is almost similar to the Solaris system. In both systems the swap space is used only
for anonymous memory, it is that kind of memory that is not backed by any file. In the
Linux system, one or more swap areas are allowed to be established. A swap area may be
in either in a swap file on a regular file system or a dedicated file partition.

*For Internal Circulation Only 151

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Figure – A data structure for swapping on Linux system

Each swap area consists of 4 KB page slots, which are used to hold the swapped pages.
Associated with each swap area is a swap-map- an array of integers counters, each
corresponding to a page slot in the swap area. If the value of the counter is 0 it means the
page slot is occupied by a swapped page. The value of the counter indicates the number of
mappings to the swapped page. For example, a value 3 indicates that the swapped page is
mapped to the 3 different processes.

1. Protection and Security

• Protection: Refers to mechanisms that control access to resources in a computing

system. It ensures that programs, processes, and users of the system are only
allowed to access resources they are authorized to use.
• Security: Encompasses policies and mechanisms that protect a system’s data and
resources against unauthorized access, alteration, or destruction. Security goes
beyond protection by also addressing confidentiality, integrity, and availability.

*For Internal Circulation Only 152

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

2. Goals of Protection

• Confidentiality: Ensures that information is accessible only to those authorized to

have access.
• Integrity: Protects information from being modified by unauthorized users or by
malicious software.
• Availability: Ensures that authorized users have access to information and
resources when needed.
• Accountability: Tracks actions of users to detect and trace unauthorized or
inappropriate access and usage.
• Least Privilege: Ensures users have only the minimum access necessary to
perform their duties.

3. Domain Protection

• Definition: A domain defines a boundary within which a process or user has

authority to access certain resources. Domain protection is the practice of
restricting access to resources based on these domains.
• Implementation: Systems are divided into domains (e.g., user domain, system
domain), and each domain has specific permissions. For example, a user domain
may have access to user files but not system files.
• Domain Switching: Allows processes to switch from one domain to another to
gain different permissions as required, often controlled by system calls or specific
commands.

4. Access Matrix

• Concept: An access matrix is a theoretical model that defines the rights of each
subject (user, process) to each object (file, directory) in the system.
• Structure:
o Rows represent subjects. o Columns represent objects. o Each cell in the
matrix specifies the types of access allowed (e.g., read, write, execute).

*For Internal Circulation Only 153

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Example: If a file A is in the column, and user U1 is in the row, the intersection
cell might contain "read" and "write" permissions, indicating that U1 can read and
write to A.
• Access Control Mechanisms:

o Access Control Lists (ACL): Lists the users and their permitted access
rights for each object.
o Capabilities: Tokens or keys associated with a subject, listing objects and
access rights for each.

5. Authentication

• Purpose: Verifying the identity of a user or system.

• Types of Authentication:
o Password-based: The most common method, requiring a secret password
known only to the user.
o Biometric: Uses physical characteristics like fingerprints, iris scans, or
voice recognition.
o Multi-factor Authentication (MFA): Combines two or more independent
credentials (e.g., password + OTP).
o Token-based: Involves generating a unique token that can be used to verify
identity, often via a mobile app.
• Common Authentication Protocols:
o Kerberos: A network authentication protocol using secret-key
cryptography to provide strong authentication.
o OAuth: An open standard for access delegation, commonly used as a way
to grant websites or applications limited access.

6. One-Time Password (OTP)

*For Internal Circulation Only 154

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Definition: A password that is valid for only a single transaction or login session,
offering enhanced security.
• Generation Methods:
o Time-based: Generated based on the current time and valid for a short
duration (e.g., 30 seconds).
o Event-based: Generated upon request and expires after a single use.
• Benefits: Reduces the risk of password interception and reuse.
• Examples: Google Authenticator, SMS-based OTP, email-based OTPs.

7. Program Threats

• Definition: Security risks that arise due to malicious programs that exploit software
vulnerabilities.
• Types of Program Threats:
o Virus: A self-replicating program that attaches itself to files and infects a
system when executed.
o Worm: A standalone program that replicates itself across networks, causing
system slowdowns.
o Trojan Horse: A program disguised as a legitimate application but
performs malicious actions in the background.
o Spyware: Software that secretly monitors user activity and collects
personal information.
o Ransomware: Malware that locks users out of their systems or files and
demands payment to unlock access.

• Mitigation: Regular software updates, using antivirus software, and practicing safe
browsing habits.

8. System Threats

*For Internal Circulation Only 155

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Definition: Larger threats that impact the entire system or network, often aiming
to disrupt or control the system.
• Types of System Threats:
• Denial of Service (DoS): Overloads the system resources, making it
unavailable to legitimate users.
• Distributed Denial of Service (DDoS): A coordinated DoS attack
using multiple systems to target a single system or network.
• Rootkits: Programs that modify the OS to hide malicious activity or
unauthorized access.
• Backdoors: Unauthorized access points created by attackers to bypass
normal authentication.
• Mitigation: Use of firewalls, intrusion detection systems, regular system
monitoring, and enforcing network security policies.

9. Case Study of Windows and Linux Operating Systems

• Windows Security:
• User Account Control (UAC): Limits program access to system
resources based on the user's privileges.
• NTFS Permissions: File system permissions for fine-grained access
control.
• Windows Defender: Built-in antivirus and anti-malware software.

• Active Directory: Centralized directory for managing permissions and

policies across networked Windows systems.
• Linux Security:
o Permissions and Ownership: Each file and directory has permissions for
the owner, group, and others.
o SELinux/AppArmor: Security modules that provide mandatory access
control.
o iptables and firewall: Firewall utilities for network security.

*For Internal Circulation Only 156

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

o Pluggable Authentication Modules (PAM): A framework for integrating

multiple authentication methods.
• Comparison:
o Windows is user-friendly but often targeted due to its widespread use. It
uses proprietary security tools.
o Linux is open-source, customizable, and generally seen as secure due to
permissions and user roles, but requires technical knowledge to configure
effectively.

10. Security Problem

• Definition: Broad challenges or vulnerabilities that threaten system security.

• Key Security Problems:
o Software Vulnerabilities: Flaws in software code that can be exploited by
attackers (e.g., buffer overflows).
o Insider Threats: Threats from within the organization, such as employees
misusing access privileges.

o Phishing and Social Engineering: Attacks that trick users into revealing
sensitive information.
o Zero-day Exploits: Vulnerabilities unknown to the software developer,
exploited before they can be patched.
• Solutions:
o Regular security audits and vulnerability assessments. o Educating
employees on security best practices. o Implementing robust access control
and monitoring policies. o Using encryption for data protection.

*For Internal Circulation Only 157

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

UNIT – IV
INTRODUCTION TO LINUX PROGRAM.
1. Linux System Architecture.
2. Linux Command format.
3. Linux Internal and External Commands.
4. Directory Commands.
5. File-related commands.
6. Disk-related commands and General Utilities.

*For Internal Circulation Only 158

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

The Linux System Architecture consists of several layers that work together to provide a
functioning operating system. Here's an overview:

1. Hardware Layer
• This is the physical hardware of the computer, including:
o CPU (Central Processing Unit)
o Memory (RAM)
o Input/Output Devices (e.g., keyboard, mouse, display, storage)

2. Kernel Layer
• The core of the Linux operating system that directly interacts with the hardware.
• Responsible for:
o Process Management: Scheduling and managing processes.
o Memory Management: Allocating and deallocating memory for processes.
o Device Drivers: Interface between the hardware and the OS.
o System Calls: Providing an interface for user-level processes to interact with
the kernel.
The kernel can be further divided into:
• Monolithic Kernel: Linux uses this, meaning most functions are handled in a single,
large kernel space.
• Modules: Dynamically loadable modules allow the kernel to extend its functionality
without rebooting.

3. System Libraries
• Libraries provide standard functions that developers and applications can use without
directly accessing kernel-level system calls.
• Example: glibc (GNU C Library) for basic system functions like I/O, memory
allocation, and string operations.
4. Shell
• Acts as an intermediary between the user and the operating system.
• Allows users to execute commands, scripts, and manage files.

*For Internal Circulation Only 159

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Types of shells:
o Bash (Bourne Again Shell): Most common.
o Other examples: Zsh, Ksh, Csh.
5. User Space
• Applications and Utilities: Programs that run in the user space, such as text editors
(e.g., Vim, Nano), browsers, and other tools.
• User Processes: Programs initiated by the user or scripts executed by the shell.
6. File System
• Linux organizes and stores data using a hierarchical file system.
• Common file systems: ext4, XFS, Btrfs, etc.
• Virtual file systems like /proc and /sys allow interaction with kernel data structures.
7. User Interface (Optional)
• Command-Line Interface (CLI): Primary interface through the shell.
• Graphical User Interface (GUI): Optional layer, including desktop environments like
GNOME, KDE, or XFCE.

*For Internal Circulation Only 160

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Process Management
• Definition: A process is an instance of a running program.
• States of a Process:
1. New: Created but not yet ready.
2. Ready: Waiting for CPU allocation.
3. Running: Executing on the CPU.
4. Waiting: Waiting for resources or I/O.
5. Terminated: Finished execution.

Commands:
• ps: List active processes.
• top: Monitor running processes in real time.
• kill: Terminate a process.
4. Synchronization
• Purpose: Manage access to shared resources in a multi-process environment.
• Mechanisms:
o Mutex Locks: A synchronization primitive used to ensure mutual exclusion,
allowing only one thread or process to access a critical section at a time.

*For Internal Circulation Only 161

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

o Semaphores: A signaling mechanism used to control access to a finite number of

resources, which can be either binary (like mutexes) or counting semaphores.
o Spinlocks: A lock mechanism where a process continuously checks for lock
availability (busy-waiting), commonly used in scenarios with short wait times to
avoid overhead from sleep/wake operations.

Example Problem: Dining Philosophers Problem.

Diagram: Synchronization Problem (Critical Section)

5. File Systems
• Structure: Hierarchical directory structure starting from root (/).
• Key Components:

*For Internal Circulation Only 162

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

o Directories: Contain files or other directories.

o File Permissions: Define read, write, and execute rights for users, groups, and
others.
Diagram: Linux File System Structure
Commands:
• ls: List directory contents.
• chmod: Change file permissions.
• df: Show disk space usage.
• mount: Attach a file system to the directory tree.

Deadlocks

• Deadlock occurs when processes are stuck waiting for each other’s resources.
• Deadlock Prevention: Avoid one of the four necessary conditions (Mutual
Exclusion, Hold and Wait, No Preemption, Circular Wait).

• Mutual Exclusion: A condition where resources are non-shareable, meaning only

one process can use a resource at any given time.
• Hold and Wait: A condition where a process holding at least one resource is
waiting to acquire additional resources held by other processes.
• No Preemption: A condition where resources cannot be forcibly taken from a
process holding them; they must be released voluntarily.
• Circular Wait: A condition where a circular chain of processes exists, with each
process waiting for a resource held by the next process in the chain.

7. Case Study: Process Scheduling in Linux

• Scenario: A university’s course registration system experiences high demand during
peak times.
o Problem: Slow response times and crashes due to resource contention.
o Solution:
▪ Apply round-robin scheduling to fairly allocate CPU time.

*For Internal Circulation Only 163

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

• Use Mutex locks to prevent race conditions during database updates. Implement
dynamic priority adjustment to prioritize critical tasks.
Internal Commands:
These commands are built into the shell (like Bash) and do not require any external executable
files. They are processed directly by the shell itself.
Examples of Internal Commands:
• cd: Changes the current directory.
• echo: Displays a line of text or variable values.
• pwd: Prints the current working directory.
• exit: Exits the current shell.
• history: Displays the history of commands used.
• set: Sets shell options and environment variables.
• unset: Removes environment variables or functions.
Characteristics of Internal Commands:
• Execute faster as they are directly built into the shell.
• Do not require an external file or path.
2. External Commands:
These commands are not built into the shell and exist as standalone executable files in the
system. They are typically found in directories like /bin, /usr/bin, /sbin, and /usr/sbin.
Examples of External Commands:
• ls: Lists directory contents.
• cp: Copies files or directories.
• mv: Moves or renames files or directories.
• rm: Removes files or directories.
• find: Searches for files and directories.
• grep: Searches for patterns in files.
• man: Displays the manual pages of commands.
Characteristics of External Commands:
• They are stored as executable files.
• They often reside in system directories like /bin, /usr/bin, or /sbin.
• They may require more resources as they involve reading an external file to execute.

*For Internal Circulation Only 164

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

Directory Commands in Linux.

In Linux, directory commands are used to navigate and manipulate directories. These
commands allow you to list, create, delete, and change directories, among other operations.
Below is a list of common directory commands and their functions.
1. pwd (Print Working Directory)
• Purpose: Displays the current directory path.
2. cd (Change Directory)
• Purpose: Change the current directory to the specified directory.
• cd [directory] -
• cd /home/user/Downloads - To change to the /home/user/Downloads directory
• cd ~ - To go back to the home directory.
• cd .. - To go up one directory level.
[Link] (List Directory Contents)

• Purpose: Lists the files and directories in the current or specified directory.
• Usage: ls [directory]
• To show detailed information, including file permissions, sizes, and modification dates
- ls -l
• To show hidden files (those starting with a dot) –
4. mkdir (Make Directory)

• Purpose: Create a new directory.

• Usage: mkdir [directory_name]

5. rmdir (Remove Directory)

• Purpose: Deletes an empty directory.

*For Internal Circulation Only 165

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

*For Internal Circulation Only 166

Subject Name: Operating System
Faculty Name: Prof. Rohit M.N

*For Internal Circulation Only 75