Introduction to Operating system

Operating System a type of system software. It basically manages all the resources of the
computer. An operating system acts as an interface between the software and different
parts of the computer or the computer hardware. The operating system is designed in such
a way that it can manage the overall resources and operations of the computer.

Operating System is a fully integrated set of specialized programs that handle all the
operations of the computer. It controls and monitors the execution of all other programs
that reside in the computer, which also includes application programs and other system
software of the computer. Examples of Operating Systems are Windows, Linux, Mac OS,
etc.
An Operating System (OS) is a collection of software that manages computer hardware
resources and provides common services for computer programs.
An operating system is system software that acts as an intermediary between a user of a
computer and the computer hardware. It is software that manages the computer hardware
and allows the user to execute programs in a convenient and efficient manner.

Operating system goals:

 Make the computer system convenient to use. It hides the difficulty in managing the
hardware.
 Use the computer hardware in an efficient manner
 Provide and environment in which user can easily interface with computer.
 It is a resource allocator

What is an Operating System Used for?

The operating system helps in improving the computer software as well as hardware.
Without OS, it became very difficult for any application to be user-friendly. The Operating
System provides a user with an interface that makes any application attractive and user-
friendly. The operating System comes with a large number of device drivers that make OS
services reachable to the hardware environment. Each and every application present in
the system requires the Operating System. The operating system works as a
communication channel between system hardware and system software. The operating
system helps an application with the hardware part without knowing about the actual
hardware configuration. It is one of the most important parts of the system and hence it is
present in every device, whether large or small device.
The fundamental goal of an Operating System is to execute user programs and to make
tasks easier. Various application programs along with hardware systems are used to
perform this work. Operating System is software that manages and controls the entire set
of resources and effectively utilizes every part of a computer. The figure shows how OS
acts as a medium between hardware units and application programs.

Computer System Structure (Components of Computer System)

Computer system mainly consists of four components-

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

Operating System can be viewed from two viewpoints

 User views
 System views User Views:

The user’s view of the operating system depends on the type of user.
  If the user is using standalone system, then OS is designed for ease of use and high
performances. Here resource utilization is not given importance.
 If the users are at different terminals connected to a mainframe or minicomputers, by
sharing information and resources, then the OS is designed to maximize resource
utilization. OS is designed such that the CPU time, memory and i/o are used
efficiently and no single user takes more than the resource allotted to them.
 If the users are in workstations, connected to networks and servers, then the user
have a system unit of their own and shares resources and files with other systems.
Here the OS is designed for both ease of use and resource availability (files).
 Other systems like embedded systems used in home device (like washing m/c) &
automobiles do not have any user interaction. There are some LEDs to show the
status of its work
 Users of hand-held systems, expects the OS to be designed for ease of use and
performance per amount of battery life

System Views:Operating system can be viewed as a resource allocator and control program.
 Resource allocator – The OS acts as a manager of hardware and software
resources. CPU time, memory space, file-storage space, I/O devices, shared files
etc. are the different resources required during execution of a program. There can be
conflicting request for these resources by different programs running in same system.
The OS assigns the resources to the requesting program depending on the priority.
 Control Program – The OS is a control program and manage the execution of user
program to prevent errors and improper use of the computer.

Need for Operating System

OS as a platform for Application programs: The operating system provides a platform,
on top of which, other programs, called application programs can run. These application
programs help users to perform a specific task easily. It acts as an interface between the
computer and the user. It is designed in such a manner that it operates, controls, and
executes various applications on the computer.

Managing Input-Output unit: The operating system also allows the computer to manage
its own resources such as memory, monitor, keyboard, printer, etc. Management of these
resources is required for effective utilization. The operating system controls the various
system input-output resources and allocates them to the users or programs as per their
requirements.
Multitasking: The operating system manages memory and allows multiple programs to
run in their own space and even communicate with each other through shared memory.
Multitasking gives users a good experience as they can perform several tasks on a
computer at a time.
A platform for other software applications: Different application programs are needed
by users to carry out particular system tasks. These applications are managed and
controlled by the OS to ensure their effectiveness. It serves as an interface between the
user and the applications, in other words.
Controls memory: It helps in controlling the computer‟s main memory. Additionally, it
allows and deallocates memory to all tasks and applications.
Looks after system files: It helps with system file management. As far as we are aware,
all of the data on the system exists as files. It facilitates simple file interaction.
Provides Security: It helps to maintain the system and applications safe through the
authorization process. Thus, the OS provides security to the system.

Functions of the Operating System

 Resource Management: The operating system manages and allocates memory, CPU
time, and other hardware resources among the various programs and processes
running on the computer.
 Process Management: The operating system is responsible for starting, stopping, and
managing processes and programs. It also controls the scheduling of processes and
allocates resources to them.
 Memory Management: The operating system manages the computer‟s primary
memory and provides mechanisms for optimizing memory usage.
 Security: The operating system provides a secure environment for the user,
applications, and data by implementing security policies and mechanisms such as
access controls and encryption.
 Job Accounting: It keeps track of time and resources used by various jobs or users.
 File Management: The operating system is responsible for organizing and managing
the file system, including the creation, deletion, and manipulation of files and
directories.
 Device Management: The operating system manages input/output devices such as
printers, keyboards, mice, and displays. It provides the necessary drivers and
interfaces to enable communication between the devices and the computer.
 Networking: The operating system provides networking capabilities such as
establishing and managing network connections, handling network protocols, and
sharing resources such as printers and files over a network.
 User Interface: The operating system provides a user interface that enables users to
interact with the computer system. This can be a Graphical User Interface (GUI), a
Command-Line Interface (CLI), or a combination of both.
 Backup and Recovery: The operating system provides mechanisms for backing up
data and recovering it in case of system failures, errors, or disasters.
 Virtualization: The operating system provides virtualization capabilities that allow
multiple operating systems or applications to run on a single physical machine. This
can enable efficient use of resources and flexibility in managing workloads.
 Performance Monitoring: The operating system provides tools for monitoring and
optimizing system performance, including identifying bottlenecks, optimizing resource
usage, and analyzing system logs and metrics.
 Time-Sharing: The operating system enables multiple users to share a computer
system and its resources simultaneously by providing time-sharing mechanisms that
allocate resources fairly and efficiently.
 System Calls: The operating system provides a set of system calls that enable
applications to interact with the operating system and access its resources. System
calls provide a standardized interface between applications and the operating system,
enabling portability and compatibility across different hardware and software platforms.
 Error-detecting Aids: These contain methods that include the error messages, and
other debugging and error-detecting methods.

Objectives of Operating Systems

Some of the objectives of the operating system, which are mentioned below.
 Convenient to use: One of the objectives is to make the computer system more
convenient to use in an efficient manner.
 User Friendly: To make the computer system more interactive with a more convenient
interface for the users.
 Easy Access: To provide easy access to users for using resources by acting as an
intermediary between the hardware and its users.
 Management of Resources: For managing the resources of a computer in a better
and faster way.
 Controls and Monitoring: By keeping track of who is using which resource, granting
resource requests, and mediating conflicting requests from different programs and
users.
 Fair Sharing of Resources: Providing efficient and fair sharing of resources between
the users and programs.

Operating System Services

The main purpose of the operating system is to provide an environment for the execution
of programs. Thus, an operating system provides certain services to programs and the
users of those programs.

Program Execution:The operating system provides a convenient environment where

users can run their [Link] operating system performs memory allocation to
programs, and load them into appropriate location so that they can execute. The users do
not have to worry about all these tasks.
I/O Operations: In order to execute a program, it usually requires an I/O operation. For
example, it may need to read a file and print the output. When all these I/O operations are
performed users cannot control I/O devices. All I/O is performed under the control of the
operating system.
Communication: The various processes executing on a system may need to
communicate in order to exchange data or information. The operating system provides this
communication by using a facility for message passing. In message passing packets of
information are moved between processes by the operating system.

Types of Operating Systems

 Batch Operating System: A Batch Operating System is a type of operating system
that does not interact with the computer directly. There is an operator who takes similar
jobs having the same requirements and groups them into batches.

 Time-sharing Operating System: Time-sharing Operating System is a type of

operating system that allows many users to share computer resources (maximum
utilization of the resources).
 A time-shared operating system uses CPU scheduling and multi-programming to
provide each user with a small portion of a shared computer at once. Each user has at
least one separate program in memory. A program is loaded into memory and
executes, it performs a short period of time either before completion or to complete I/O.
 Distributed Operating System: Distributed Operating System is a type of operating system
that manages a group of different computers and makes appear to be a single computer. These
operating systems are designed to operate on a network of computers. They allow multiple
users to access shared resources and communicate with each other over the network.
 Examples include Microsoft Windows Server and various distributions of Linux designed for
servers.
 Network Operating System: Network Operating System is a type of operating system that
runs on a server and provides the capability to manage data, users, groups, security,
applications, and other networking functions.
 Real-time Operating System: Real-time Operating System is a type of operating system that
serves a real-time system and the time interval required to process and respond to inputs is
very small. These operating systems are designed to respond to events in real time. They are
used in applications that require quick and deterministic responses, such as embedded
systems, industrial control systems, and robotics.
Uses of RTOS
 Defense systems like RADAR .
 Air traffic control system.
 Networked multimedia systems.
 Medical devices like pacemakers.
 Stock trading applications.

 Multiprocessing Operating System: Multiprocessor Operating Systems are used in

operating systems to boost the performance of multiple CPUs within a single computer
system. Multiple CPUs are linked together so that a job can be divided and executed
more quickly.

 Single-User Operating Systems: Single-User Operating Systems are designed to

support a single user at a time. Examples include Microsoft Windows for personal
computers and Apple macOS.

 Multi-User Operating Systems: Multi-User Operating Systems are designed to

support multiple users simultaneously. Examples include Linux and Unix.

Multiprocessor: A Multiprocessor is a computer system with two or more central

processing units (CPUs) share full access to a common RAM. The main objective of using
a multiprocessor is to boost the system‟s execution speed, with other objectives being fault
tolerance and application matching. There are two types of multiprocessors, one is called
shared memory multiprocessor and another is distributed memory multiprocessor. In
shared memory multiprocessors, all the CPUs shares the common memory but in a
distributed memory multiprocessor, every CPU has its own private memory.
The interconnection among two or more processor and shared memory is done with three
methods
i. Time shared common bus
ii. Multiport memories
iii. Crossbar switch network

 Embedded Operating Systems: Embedded Operating Systems are designed to run

on devices with limited resources, such as smartphones, wearable devices, and
household appliances. Examples include Google‟s Android and Apple‟s iOS.
 Cluster Operating Systems: Cluster Operating Systems are designed to run on a
group of computers, or a cluster, to work together as a single system. They are used
for high-performance computing and for applications that require high availability and
reliability. Examples include Rocks Cluster Distribution and OpenMPI.

System Call
A system call is a programmatic way in which a computer program requests a service
from the kernel of the operating system it is executed on. A system call is a way for
programs to interact with the operating system. A computer program makes a system
call when it requests the operating system‟s kernel.
System call provides the services of the operating system to the user programs via the
Application Program Interface(API). It provides an interface between a process and an
operating system to allow user-level processes to request services of the operating
system. System calls are the only entry points into the kernel system. All programs
needing resources must use system calls.
What is a System Call?
A system call is a mechanism used by programs to request services from the operating
system (OS). In simpler terms, it is a way for a program to interact with the underlying
system, such as accessing hardware resources or performing privileged operations.
A user program can interact with the operating system using a system call. A number of
services are requested by the program, and the OS responds by launching a number of
systems calls to fulfill the request. A system call can be written in high-level languages like
C or Pascal or in assembly language. If a high-level language is used, the operating
system may directly invoke system calls, which are predefined functions.
A system call is initiated by the program executing a specific instruction, which triggers a
switch to kernel mode, allowing the program to request a service from the OS. The OS
then handles the request, performs the necessary operations, and returns the result back
to the program.
System calls are essential for the proper functioning of an operating system, as they
provide a standardized way for programs to access system resources. Without system
calls, each program would need to implement its methods for accessing hardware and
system services, leading to inconsistent and error-prone behavior.
Services Provided by System Calls
 Process Creation and Management
 Main Memory Management
 File Access, Directory, and File System Management
 Device Handling(I/O)
 Protection
 Networking, etc.
 Process Control: end, abort, create, terminate, allocate, and free memory.
 File Management: create, open, close, delete, read files, etc.
 Device Management
 Information Maintenance
 Communication

Features of System Calls

 Interface: System calls provide a well-defined interface between user programs and
the operating system. Programs make requests by calling specific functions, and the
operating system responds by executing the requested service and returning a result.
 Protection: System calls are used to access privileged operations that are not
available to normal user programs. The operating system uses this privilege to protect
the system from malicious or unauthorized access.
 Kernel Mode: When a system call is made, the program is temporarily switched from
user mode to kernel mode. In kernel mode, the program has access to all system
resources, including hardware, memory, and other processes.
 Context Switching: A system call requires a context switch, which involves saving the
state of the current process and switching to the kernel mode to execute the requested
service. This can introduce overhead, which can impact system performance.
 Error Handling: System calls can return error codes to indicate problems with the
requested service. Programs must check for these errors and handle them
appropriately.
 Synchronization: System calls can be used to synchronize access to shared
resources, such as files or network connections. The operating system provides
synchronization mechanisms, such as locks or semaphores, to ensure that multiple
programs can access these resources safely.

A semaphore is a variable or abstract data type that controls access to a shared

resource in an operating system (OS). It's a type of synchronization primitive that helps
manage how many processes can use a resource at once

Working of system call

Here is a detailed explanation step by step how system calls work:
 Users need special resources: Sometimes programs need to do some special things
that can‟t be done without the permission of the OS like reading from a file, writing to a
file, getting any information from the hardware, or requesting a space in memory.
 The program makes a system call request: There are special predefined instructions
to make a request to the operating system. These instructions are nothing but just a
“system call”. The program uses these system calls in its code when needed.
 Operating system sees the system call: When the OS sees the system call then it
recognizes that the program needs help at this time so it temporarily stops the program
execution and gives all the control to a special part of itself called „Kernel‟. Now „Kernel‟
solves the need of the program.
 The operating system performs the operations: Now the operating system performs
the operation that is requested by the program. Example: reading content from a file
etc.
 Operating system give control back to the program: After performing the special
operation, OS give control back to the program for further execution of program .

Examples of a System Call in Windows and Unix

System calls for Windows and Unix come in many different forms. These are listed in the
table below as follows:
Process Windows Unix
 Process Control CreateProcess() Fork()
ExitProcess() Exit()
WaitForSingleObject() Wait()
File Manupulation CreateFile() Open()
ReadFile() Read()
WriteFile() Write()
Close()
Device Management SetConsoleMode() Ioctl()
ReadConsole() Read()
WriteConsole() Write()

Information mantenance GetCurrentProcessID() Getpid()

SetTimer() Alarm()
Sleep() Sleep()

Communication CreatePipe() Pipe()

CreateFileMapping() Shmget()
MapViewOfFile() Mmap()

Protection SetFileSecurity() Chmod()

InitializeSecurityDescriptor() Umask()
SetSecurityDescriptorgroup() Chown()

Open(): Accessing a file on a file system is possible with the open() system call. It gives
the file resources it needs and a handle the process can use. A file can be opened by
multiple processes simultaneously or just one process. Everything is based on the
structure and file system.

Read(): Data from a file on the file system is retrieved using it. In general, it accepts three
arguments:
 A description of a file.
 A buffer for read data storage.
 How many bytes should be read from the file Before reading, the file to be read could
be identified by its file descriptor and opened using the open() function.

Wait(): In some systems, a process might need to hold off until another process has
finished running before continuing. When a parent process creates a child process, the
execution of the parent process is halted until the child process is complete. The parent
process is stopped using the wait() system call. The parent process regains control once
the child process has finished running.
Write(): Data from a user buffer is written using it to a device like a file. A program can
produce data in one way by using this system call. generally, there are three arguments:
 A description of a file.
 A reference to the buffer where data is stored.
 The amount of data that will be written from the buffer in bytes.

Fork(): The fork() system call is used by processes to create copies of themselves. It is
one of the methods used the most frequently in operating systems to create processes.
When a parent process creates a child process, the parent process‟s execution is
suspended until the child process is finished. The parent process regains control once the
child process has finished running.

Exit(): A system call called exit() is used to terminate a program. In environments with
multiple threads, this call indicates that the thread execution is finished. After using the
exit() system function, the operating system recovers the resources used by the process.

The kernel is a computer program that's at the core of an operating system (OS):
The kernel is responsible for managing the OS's resources, including memory, disk
storage, and networking. It also:
 Prevents and resolves conflicts between processes
 Provides an interface for the rest of the OS to read and write files and communicate
on the network
 Handles system calls from software applications
 Controls processes
 Handles interrupts
 Facilitates input/output (I/O) operations

Types of System Calls

System calls are interfaces provisioned by the operating system to allow user-level
applications to interact with low-level hardware components & make use of all the services
provided by the kernel, which is a core component and the heart of an operating system that
manages all the hardware and the services provided by the OS.
These system calls are essential for every process to interact with the kernel and properly
use the services provided by it. System calls are an interface between a process and the
operating system. And they're the only way to switch from user mode to kernel mode.
Types of System Calls
Services provided by an OS are typically related to any kind of operation that a user program
can perform like creation, termination, forking, moving, communication, etc. Similar types of
operations are grouped into one single system call category. System calls are classified into
the following categories:

1. File System Operations

These system calls are made while working with files in OS, File manipulation operations
such as creation, deletion, termination etc.
 open(): Opens a file for reading or writing. A file could be of any type like text file, audio
file etc.
 read(): Reads data from a file. Just after the file is opened through open() system call,
then if some process want to read the data from a file, then it will make a read() system
call.
 write(): Writes data to a file. Wheneve the user makes any kind of modification in a file
and saves it, that's when this is called.
 close(): Closes a previously opened file.
 seek(): Moves the file pointer within a file. This call is typically made when we the user
tries to read the data from a specific position in a file. For example, read from line - 47.
Than the file pointer will move from line 1 or wherever it was previously to line-47.
Algorithm for Reading a File
algorithm read
input: user file descriptor, address of buffer in user process, number of bytes to read
output: count of bytes copied into user space
{
get file table entry from user file descriptor;
check file accessibility;
set parameters in u area for user address, byte count, I/O to user;
get inode from file table;
lock inode;
set byte offset in u area from file table offset;
while(count not satisfied)
{
convert file offset to disk block(algorithm bmap);
calculate offset into block, number of bytes to read;
if(number of bytes to read is 0)
break;
read block (algorithm breada if with read ahead, algorithm bread otherwise);
copy data from system buffer to user address;
update u area fields for file byte offset, read count, address to write into user space;
release buffer;
}
unlock inode;
update file table offset for next read;
return(total number of bytes read);
}
2. Process Control
These types of system calls deal with process creation, process termination, process
allocation, deallocation etc. Basically manages all the process that are a part of OS.
 fork(): Creates a new process (child) by duplicating the current process (parent). This
call is made when a process makes a copy of itself and the parent process is halted
temporarily until the child process finishes its execution.
 exec(): Loads and runs a new program in the current process and replaces the current
process with a new process. All the data such as stack, register, heap memory
everything is replaced by a new process and this is known as overlay. For example,
when you execute a java byte code using command - java "filename". Then in the
background, exec() call will be made to execute the java file and JVM will also be
executed.
 wait(): The primary purpose of this call is to ensure that the parent process doesn't
proceed further with its execution until all its child processes have finished their
execution. This call is made when one or more child processes are forked.
 exit(): It simply terminates the current process.
 kill(): This call sends a signal to a specific process and has various purpose including -
requesting it to quit voluntarily, or force quit, or reload configuration.
3. Memory Management
These types of system calls deals with memory allocation, deallocation & dynamically
changing the size of a memory allocated to a process. In short, the overall management of
memory is done by making these system calls.
 brk(): Changes the data segment size for a process in HEAP Memory. It takes an
address as argument to define the end of the heap and explicitly sets the size of HEAP.
 sbrk(): This call is also for memory management in heap, it also takes an argument as
an integer (+ve or -ve) specifying whether to increase or decrease the size respectively.
 mmap(): Memory Map - It basically maps a file or device into main memory and further
into a process's address space for performing operations. And any changes made in the
content of a file will be reflected in the actual file.
 munmap(): Unmaps a memory-mapped file from a process's address space and out of
main memory
 mlock() and unlock(): memory lock defines a mechanism through which certain pages
stay in memory and are not swapped out to the swap space in the disk. This could be
done to avoid page faults. Memory unlock is the opposite of lock, it releases the lock
previously acquired on pages.
4. Interprocess Communication (IPC)
When two or more process are required to communicate, then various IPC mechanism are
used by the OS which involves making numerous system calls. Some of them are :
 pipe(): Creates a unidirectional communication channel between processes. For
example, a parent process may communicate to its child process through a pipe making
a parent process as input source of its child process.
 socket(): Creates a network socket for communication. Processes in same or other
networks can communicate through this socket, provided that they have necessary
network permissions granted.
 shmget(): It is short for - 'shared-memory-get'. It allows one or more processes to share
a portion of memory and achieve interprocess communication.
 semget(): It is short for - 'semaphore-get'. This call typically manages the coordination of
multiple processes while accessing a shared resource that is, the critical section.
 msgget(): It is short for - 'message-get'. IPC mechanism has one of the fundamental
concept called - 'message queue' which is a queue data structure inside memory through
which various processes communicate with each other. This message queue is allocated
through this call allowing other processes a structured way of communication for data
exchange purpose.
5. Device Management
The device management system calls are used to interact with various peripherial devices
attached to the PC or even the management of the current device.
 SetConsoleMode(): This call is made to set the mode of console (input or output). It
allows a process to control various console modes. In windows, it is used to control the
behaviour of command line.
 WriteConsole(): It allows us to write data on console screen.
 ReadConsole(): It allows us to read data from console screen (if any arguments are
provided).
 open(): This call is made whenever a device or a file is opened. A unique file descriptor
is created to maintain the control access to the opened file or device.
 close(): This call is made when the system or the user closes the file or device.

Importance of System Calls

 Efficient Resource Management: System Calls help your computer manage its
resources efficiently. They allocate and manage memory so programs run smoothly
without using up too many resources. This is important for multitasking and overall
performance.
 Security and Isolation: System Calls ensure that one program cannot interfere with or
access the memory of another program. This enhances the security and stability of your
device.
 Multitasking Capabilities: System Calls support multitasking, allowing multiple
programs to run simultaneously. This improves productivity and makes it easy to switch
between applications.
 Enhanced Control: System Calls provide a high level of control over your device‟s
operations. They allow you to start and stop processes, manage files, and perform
various system-related tasks.
 Input/Output (I/O) Operations: System Calls enable communication with input and
output devices, such as your keyboard, mouse, and screen. They ensure that these
devices work effectively.
 Networking and Communication: System Calls facilitate networking and
communication between different applications. They make it easy to transfer data over
networks, browse the web, send emails, and connect online.

The Purpose of System Calls in OS

System Calls act as a bridge between an operating system (OS) and a running program.
They are usually written as assembly language instructions and are detailed in manuals for
programmers working with assembly language.
When a program running in user mode needs to access a resource, it makes a System Call.
This request is sent to the OS kernel to obtain the needed resource.
System Calls are used for various tasks, such as:
 Creating or executing files in the file system.
 Reading from and writing to files.
 Developing and managing new procedures in programs.
 Making network connections, including sending and receiving data packets.
 Accessing hardware devices like printers and scanners.

Operating System Services

An operating system is software that acts as an intermediary between the user and
computer hardware. It is a program with the help of which we are able to run various
applications. It is the one program that is running all the time. Every computer must have
an operating system to smoothly execute other programs.
The OS coordinates the use of the hardware and application programs for various users. It
provides a platform for other application programs to work. The operating system is a set
of special programs that run on a computer system that allows it to work properly. It
controls input-output devices, execution of programs, managing files, etc.

Services of Operating System

 Program execution
 Input Output Operations
 Communication between Process
 File Management
 Memory Management
 Process Management
 Security and Privacy
 Resource Management
 User Interface
 Networking
 Error handling
 Time Management
Program Execution: It is the Operating System that manages how a program is going to
be executed. It loads the program into the memory after which it is executed. The order in
which they are executed depends on the CPU Scheduling Algorithms. A few
are FCFS, SJF, etc. When the program is in execution, the Operating System also handles
deadlock i.e. no two processes come for execution at the same time. The Operating
System is responsible for the smooth execution of both user and system programs. The
Operating System utilizes various resources available for the efficient running of all types
of functionalities.
Input Output Operations: Operating System manages the input-output operations and
establishes communication between the user and device drivers. Device drivers are
software that is associated with hardware that is being managed by the OS so that the
sync between the devices works properly. It also provides access to input-output devices
to a program when needed.
Communication between Processes: The Operating system manages the
communication between processes. Communication between processes includes data
transfer among them. If the processes are not on the same computer but connected
through a computer network, then also their communication is managed by the Operating
System itself.
File Management :The operating system helps in managing files also. If a program needs
access to a file, it is the operating system that grants access. These permissions include
read-only, read-write, etc. It also provides a platform for the user to create, and delete files.
The Operating System is responsible for making decisions regarding the storage of all
types of data or files, i.e, floppy disk/hard disk/pen drive, etc. The Operating System
decides how the data should be manipulated and stored.
Memory Management :Let‟s understand memory management by OS in simple way.
Imagine a cricket team with limited number of player . The team manager (OS) decide
whether the upcoming player will be in playing 11 ,playing 15 or will not be included in
team , based on his performance . In the same way, OS first check whether the upcoming
program fulfil all requirement to get memory space or not ,if all things good, it checks how
much memory space will be sufficient for program and then load the program into memory
at certain location. And thus , it prevents program from using unnecessary memory.
Process Management : Understand the process management in unique way. Imagine,
our kitchen stove as the (CPU) where all cooking(execution) is really happen and chef as
the (OS) who uses kitchen-stove(CPU) to cook different dishes(program). The chef(OS)
has to cook different dishes(programs) so he ensure that any particular dish(program)
does not take long time(unnecessary time) and all dishes(programs) gets a chance to
cooked(execution) .The chef(OS) basically scheduled time for all dishes(programs) to run
kitchen(all the system) smoothly and thus cooked(execute) all the different
dishes(programs) efficiently.
Security and Privacy
 Security: OS keep our computer safe from an unauthorized user by adding security
layer to it. Basically, Security is nothing but just a layer of protection which protect
computer from bad guys like viruses and hackers. OS provide us defenses
 like firewalls and anti-virus software and ensure good safety of computer and personal
information.
 Privacy: OS give us facility to keep our essential information hidden like having a lock
on our door, where only you can enter and other are not allowed . Basically , it respect
our secrets and provide us facility to keep it safe.
Resource Management : System resources are shared between various processes. It is
the Operating system that manages resource sharing. It also manages the CPU time
among processes using CPU Scheduling Algorithms. It also helps in the memory
management of the system. It also controls input-output devices. The OS also ensures the
proper use of all the resources available by deciding which resource to be used by whom.
User Interface :User interface is essential and all operating systems provide it. Users
either interacts with the operating system through the command-line interface or graphical
user interface or GUI. The command interpreter executes the next user-specified
command.
A GUI offers the user a mouse-based window and menu system as an interface.
Networking: This service enables communication between devices on a network, such as
connecting to the internet, sending and receiving data packets, and managing network
connections.
Error Handling :The Operating System also handles the error occurring in the CPU, in
Input-Output devices, etc. It also ensures that an error does not occur frequently and fixes
the errors. It also prevents the process from coming to a deadlock. It also looks for any
type of error or bugs that can occur while any task. The well-secured OS sometimes also
acts as a countermeasure for preventing any sort of breach of the Computer System from
any external source and probably handling them.
Time Management :Imagine traffic light as (OS), which indicates all the cars(programs)
whether it should be stop(red)=>(simple queue), start(yellow)=>(ready
queue),move(green)=>(under execution) and this light (control) changes after a certain
interval of time at each side of the road(computer system) so that the cars(program) from
all side of road move smoothly without traffic.

Components of Operating system

An Operating system is an interface between users and the hardware of a computer
system. It is a system software that is viewed as an organized collection of software
consisting of procedures and functions, providing an environment for the execution of
programs. The operating system manages system software and computer hardware
resources. It allows computing resources to be used in an efficient way. Programs interact
with computer hardware with the help of operating system. A user can interact with the
operating system by making system calls or using OS commands.
Important Components of the Operating System
 Process Management
 File Management
 Command Interpreter
 System Calls
 Signals
 Network Management
 Security Management
 I/O Device Management
 Secondary Storage Management
 Main Memory Management
Process Management
A process is a program in execution. It consists of the followings:
 Executable program
 Program data
 Stack and stack pointer
 Program counter and other CPU registers
 Details of opened files
A process can be suspended temporarily and the execution of another process can be
taken up. A suspended process can be restarted later. Before suspending a process, its
details are saved in a table called the process table so that it can be executed later on. An
operating system supports two system calls to manage processes Create and Kill –
 Create a system call used to create a new process.
 Kill system call used to delete an existing process.

Fig: Five State Process Model

A process can create a number of child processes. Processes can communicate among
themselves either using shared memory or by message-passing techniques. Two
processes running on two different computers can communicate by sending messages
over a network.
Files Management
Files are used for long-term storage. Files are used for both input and output. Every
operating system provides a file management service. This file management service can
also be treated as an abstraction as it hides the information about the disks from the user.
The operating system also provides a system call for file management. The system call for
file management includes:
 File creation
 File deletion
 Read and Write operations
Files are stored in a directory. System calls provide to put a file in a directory or to remove
a file from a directory. Files in the system are protected to maintain the privacy of the user.
Below shows the Hierarchical File Structure directory.

Figure: File Structure Directory

Command Interpreter
There are several ways for users to interface with the operating system. One of the
approaches to user interaction with the operating system is through commands. Command
interpreter provides a command-line interface. It allows the user to enter a command on
the command line prompt (cmd). The command interpreter accepts and executes the
commands entered by a user. For example, a shell is a command interpreter under UNIX.
The commands to be executed are implemented in two ways:
 The command interpreter itself contains code to be executed.
 The command is implemented through a system file. The necessary system file is
loaded into memory and executed.
System Calls
System calls provide an interface to the services made by an operating system. The user
interacts with the operating system programs through System calls. These calls are
normally made available as library functions in high-level languages such as C, Java,
Python etc. It provides a level of abstraction as the user is not aware of the implementation
or execution of the call made. Details of the operating system is hidden from the user.
Different hardware and software services can be availed through system calls.
System calls are available for the following operations:
 Process Management
 Memory Management
 File Operations
 Input / Output Operations
Signals
Signals are used in the operating systems to notify a process that a particular event has
occurred. Signals are the software or hardware interrupts that suspend the current
execution of the task. Signals are also used for inter-process communication. A signal
follows the following pattern :
 A signal is generated by the occurrence of a particular event it can be the clicking
of the mouse, the execution of the program successfully or an error notifying, etc.
 A generated signal is delivered to a process for further execution.
 Once delivered, the signal must be handled.
 A signal can be synchronous and asynchronous which is handled by a default
handler or by the user-defined handler.
The signal causes temporarily suspends the current task it was processing, saves its
registers on the stack, and starts running a special signal handling procedure, where the
signal is assigned to it.
Note: An interrupt is a signal that tells the operating system (OS) to stop the current process
or service and do something else. Interrupts can be caused by a device or a program, and
they can be planned or unplanned

Network Management
The complexity of networks and services has created modern challenges for IT
professionals and users. Network management is a set of processes and procedures that
help organizations to optimize their computer networks. Mainly, it ensures that users have
the best possible experience while using network applications and services.
Network management is a fundamental concept of computer networks. Network
Management Systems is a software application that provides network administrators with
information on components in their networks. It ensures the quality of service and
availability of network resources. It also examines the operations of a network,
reconstructs its network configuration, modifies it for improving performance of tasks.
Security Management
The security mechanisms in an operating system ensure that authorized programs have
access to resources, and unauthorized programs have no access to restricted resources.
Security management refers to the various processes where the user changes the file,
memory, CPU, and other hardware resources that should have authorization from the
operating system.
I/O Device Management
The I/O device management component is an I/O manager that hides the details of
hardware devices and manages the main memory for devices using cache and spooling.
This component provides a buffer cache and general device driver code that allows the
system to manage the main memory and the hardware devices connected to it. It also
provides and manages custom drivers for particular hardware devices.
The purpose of the I/O system is to hide the details of hardware devices from the
application programmer. An I/O device management component allows highly efficient
resource utilization while minimizing errors and making programming easy on the entire
range of devices available in their systems.
Secondary Storage Management
Broadly, the secondary storage area is any space, where data is stored permanently and
the user can retrieve it easily. Your computer‟s hard drive is the primary location for your
files and programs. Other spaces, such as CD-ROM/DVD drives, flash memory cards, and
networked devices, also provide secondary storage for data on the computer. The
computer‟s main memory (RAM) is a volatile storage device in which all programs reside, it
provides only temporary storage space for performing tasks. Secondary storage refers to
the media devices other than RAM (e.g. CDs, DVDs, or hard disks) that provide additional
space for permanent storing of data and software programs which is also called non-
volatile storage.
Main Memory Management
Main memory is a flexible and volatile type of storage device. It is a large sequence of
bytes and addresses used to store volatile data. Main memory is also called Random
Access Memory (RAM), which is the fastest computer storage available on PCs. It is costly
and low in terms of storage as compared to secondary storage devices. Whenever
computer programs are executed, it is temporarily stored in the main memory for
execution. Later, the user can permanently store the data or program in the secondary
storage device.
System Programs
In the context of an operating system, system programs are nothing but special software
which gives us facility to manage and control the computer's hardware and resources. Also
provide a convenient environment for program development and execution.
According to computer hierarchy, one which comes at last is hardware. Then it is Operating
System, System Programs and finally Application Programs. Some of the System Programs
are simple user interfaces while others are complex. It traditionally lies between the user
interface and system calls so users can only view up-to-the System Programs and can‟t
see System Calls.

System Programs can be divided into following categories:

1. File Management: A file is a collection of specific information stored in the memory of
a computer system. File management is defined as the process of manipulating files in
the computer system, its management includes the process of creating, modifying and
deleting files.

2. Command Line Interface (CLI’s) : CLIs is the essential tool for user . It provides user
facility to write commands directly to the system for performing any operation. It is a
 text-based way to interact with operating system. CLIs can perform many tasks like file
manipulation, system configuration and etc.
3. Device drivers: Device drivers work as a simple translator for OS and devices.
Basically it act as an intermediatory between the OS and devices and provide facility to
both OS and devices to understand each other‟s language so that they can work
together efficiently without interrupt.
4. Status Information: Information like date, time amount of available memory, or disk
space is asked by some users. Others provide detailed performance, logging, and
debugging information which is more complex. All this information is formatted and
displayed on output devices or printed. Terminal or other output devices or files or a
window of GUI is used for showing the output of programs.

5. File Modification: This is used for modifying the content of files. Files stored on disks
or other storage devices, we use different types of editors. For searching contents of
files or perform transformations of files we use special commands.

6. Programming-Language support: For common programming languages, we use

Compilers, Assemblers, Debuggers, and interpreters which are already provided to
users. It provides all support to users. We can run any programming language. All
important languages are provided.

7. Program Loading and Execution: When the program is ready after Assembling and
compilation, it must be loaded into memory for execution. A loader is part of an
operating system that is responsible for loading programs and libraries. It is one of the
essential stages for starting a program. Loaders, linkage editors, and Overlay loaders
are provided by the system.
8. Communications: Connections among processes, users, and computer systems are
provided by programs. Users can send messages to another user on their screen, User
can send e-mail, browsing on web pages, remote login, the transformation of files from
one user to another.

Process Management
Earlier there used to be only single-task performing systems. In this way, there used to be
only one process running at a time. And it had the freedom to utilise all the resources in the
system. But today, we have multitasking and multiprocessing operating systems, where
more than one process runs at a time.
This creates problems such as deadlock and multiple processes requesting for the same
resource, processor, or RAM space allocation to execute.
All these problems require a proper solution, and this instigates the operating system to
carry out processor management.

Process is important part of the operating system. It allows you to control the way your
computer runs by managing the currently active processes. This includes ending processes
that are no longer needed, setting process priorities, and more. You can do it on your
computer also.
There are a few ways to manage your processes. The first is through the use of Task
Manager. This allows you to see all of the processes currently running on your computer and
their current status and CPU/memory usage. You can end any process that you no longer
need, set a process priority, or start or stop a service.
The Role of the Operating System
The operating system is the backbone of a computer. It‟s responsible for managing all of
computer‟s processes and making it possible to interact with your device.
When you boot up your computer, the operating system is the first thing that starts running. It
loads into memory and starts managing all of the other programs and processes running on
your computer. It also controls files and devices, allocates system resources, and handles
communications between applications and users.
In short, the operating system is responsible for making sure that everything runs smoothly
on your computer.
What is a process?
A process is an active execution unit of a program that performs some action. An operating
system has the right to create, schedule, and terminate a process. There are four sections in
a process:
 Text: holds the current activities represented by the value of Program Counter
 Stack: holds temporary data such as local variables, functional parameters,
return addresses, etc.
 Data: holds the global variables
 Heap: dynamically allocated memory to process during runtime.

The operating system controls a process by a block called Process Control Block (PCB). It
is a type of Data Structure that is maintained by the OS for storing the context of each
process.

What is Process Management?

Now that we know about a process and its various states and parts. Process management
involves tasks related to processing like creation, scheduling, termination, deadlock, etc. The
operating systems allocate resources that allow the process to exchange information. It
synchronizes among processes and safeguards the resources of other processes.
The operating system manages the running processes in the system and performs tasks like
scheduling and resource allocation.

Process Attributes

 Process Id: a unique identifier assigned by the operating system to each process.
 Process State: there are a few possible states a process goes through during
execution.
 CPU registers: stores the details of the process when it is swapped in and out of
the CPU, just like the program counter. Like the Program Counter (CPU registers
must be saved and restored when a process is swapped in and out of the CPU)
 I/O status information: shows information like the device to which a process is
allotted and details of open files. For example, devices allocated to the process,
open files, etc
 CPU scheduling information: processes are scheduled and executed based on
priority. For example, Priority (Different processes may have different priorities, for
example, a shorter process assigned high priority in the shortest job first
scheduling)
 Accounting & Business information: information about the amount of CPU used
and time utilities like a job or process number, real-time utilised, etc.
 Memory management information: information about the value of base registers
and limit registers, segment tables, and pages.
*********************************************************************************************************
In an operating system (OS), the base register is a key component of memory management
that holds the starting address of a process's memory segment. The base register is used to
protect memory space and control access in a system
 In an operating system (OS), the limit register contains the maximum offset from zero that a
process can access. It's used in conjunction with the base register to check addresses
generated in user mode

In an operating system (OS), an offset is a value or position that can be adjusted to access
data or perform calculations in a specific location.

A segment table in an operating system (OS) is a data structure that tracks the different
memory segments used by a program:

Purpose: The segment table maps logical addresses generated by the CPU to physical
addresses in memory. It also helps the OS keep track of which parts of memory are being
used by each process and prevents conflicts between processes.

How it works: Each entry in the segment table corresponds to a program segment and

containsdetails about the segment's size and beginning address. When a program reads
memory, the CPU uses the segment entry value to find the relevant record in the segment
table.

Components:A segment table includes a segment base and a segment limit. The segment
base indicates the starting address of the segment in physical memory, while the segment limit
determines the size of the segment.

Storage:The segment table is stored in the main memory. However, in Linux, the segment
table is stored in a file on disk to save memory space and make it easier to move processes
between computers.

Memory segmentation is a memory management technique that divides a computer's

primary memory into segments, each with its own purpose and access permissions.

A logical address is a virtual address that a CPU generates while a program is running to
reference a memory location. It's also known as a virtual address because it doesn't
physically exist
********************************************************************************************************
Process priority is a numeric value that determines the order in which processes are
scheduled and executed by an operating system (OS). It's based on the importance or
urgency of each process.
Here are some things to know about process priority:
Priority value: The priority value ranges from 0 to 99, with 0 being the lowest priority and 99
being the highest.
Priority assignment: The priority is assigned when the Process Control Block (PCB) is
created. It can depend on factors like the process's age and the resources it consumes.
Scheduling: The kernel uses the priority to schedule processes, giving more CPU time to
higher-priority tasks.
Monitoring: You can check a process's priority using the automatic display mode (ADM)
screen or Operations Centre. You can also use the MX (Mix Entries) command to display
processes and their priorities.
Changing priority: You can change a process's priority using the PR (Priority) system
command.

All of the above attributes of a process are also known as the context of the process.
Every process has its own process control block(PCB), i.e. each process will have a
unique PCB. All of the above attributes are part of the PCB.

Process Operations
Process operations in an operating system refer to the various activities the OS performs
to manage processes. These operations include process creation, process scheduling,
execution and killing the process. Here are the key process operations:

Process Creation: Process creation in an operating system (OS) is the act of

generating a new process. This new process is an instance of a program that can
execute independently.
Scheduling: Once a process is ready to run, it enters the “ready queue.” The scheduler‟s
job is to pick a process from this queue and start its execution.
Execution: Execution means the CPU starts working on the process. During this time, the
process might:
 Move to a waiting queue if it needs to perform an I/O operation.
 Get blocked if a higher-priority process needs the CPU.
Killing the Process: After the process finishes its tasks, the operating system ends it and
removes its Process Control Block (PCB).

Process Control Block (PCB)

While creating a process, the operating system performs several operations. To identify
the processes, it assigns a process identification number (PID) to each process. As the
operating system supports multi-programming, it needs to keep track of all the processes.
For this task, the process control block (PCB) is used to track the process‟s execution
status. Each block of memory contains information about the process state, program
counter, stack pointer, status of opened files, scheduling algorithms, etc.
All this information is required and must be saved when the process is switched from one
state to another. When the process makes a transition from one state to another, the
operating system must update information in the process‟s PCB. A Process Control
Block (PCB) contains information about the process, i.e. registers, quantum, priority, etc.
The Process Table is an array of PCBs, which logically contains a PCB for all of the
current processes in the system.
Structure of the Process Control Block
A Process Control Block (PCB) is a data structure used by the operating system to
manage information about a process. The process control keeps track of many important
pieces of information needed to manage processes efficiently. The diagram helps explain
some of these key data items.

Fig: Process control block(PCB)

 Pointer: It is a stack pointer that is required to be saved when the process is switched
from one state to another to retain the current position of the process.
 Process state: It stores the respective state of the process.
 Process number: Every process is assigned a unique id known as process ID or PID
which stores the process identifier.
 Program Counter (PC):Program Counter stores the counter, which contains the
address of the next instruction that is to be executed for the process.
A program counter (PC) is a register in a computer's central processing unit (CPU) that keeps track of
the memory address of the next instruction to be executed:
What it does: Tracks the memory address of the next instruction to be executed
How it works: The CPU reads the address from the PC and executes the instruction in sequence
What happens when it increments: The address specified by the PC is incremented by +n, where
+1 is for a 1-word instruction and +2 is for a 2-word instruction
What happens when it encounters a jump or branch instruction: The PC is loaded with a new
address, altering the sequence of execution
What happens if it points to an invalid address: The program may crash or an error may occur
The PC is also known as the instruction pointer.

 Register: Registers in the PCB, it is a data structure. When a processes is running and
it‟s time slice expires, the current value of process specific registers would be stored in
the PCB and the process would be swapped out. When the process is scheduled to be
run, the register values is read from the PCB and written to the CPU registers. This is
the main purpose of the registers in the PCB.
 Memory limits: This field contains the information about memory management
system used by the operating system. This may include page tables, segment tables,
etc.
 List of Open files: This information includes the list of files opened for a process.

PCBs store essential process information for execution.

Process States
As a process executes, it changes state. The state of a process is defined in part by the
current activity of that process. Each process may be one of the following states:
New: This state represents a newly created process that hasn‟t started running yet. It has
not been loaded into the main memory, but its process control block (PCB) has been
created, which holds important information about the process.

Ready: A process in this state is ready to run as soon as the CPU becomes available. It is
waiting for the operating system to give it a chance to execute.

Running: This state means the process is currently being executed by the CPU. Since
we‟re assuming there is only one CPU, at any time, only one process can be in this state.

Blocked/Waiting: This state means the process cannot continue executing right now. It is
waiting for some event to happen, like the completion of an input/output operation (for
example, reading data from a disk).

Exit/Terminate: A process in this state has finished its execution or has been stopped by
the user for some reason. At this point, it is released by the operating system and removed
from memory.

Fig: Process State

New State: When a program in secondary memory is started for execution, the process is
said to be in a new state.
Ready State: After being loaded into the main memory and ready for execution, a process
transitions from a new to a ready state. The process will now be in the ready state, waiting
for the processor to execute it. Many processes may be in the ready stage in a
multiprogramming environment.
Run State: After being allotted the CPU for execution, a process passes from the ready
state to the run state.
Terminate State: When a process‟s execution is finished, it goes from the run state to the
terminate state. The operating system deletes the Process Control Box (or PCB) after it
enters the terminate state.
Block or Wait State: If a process requires an Input/output operation or a blocked resource
during execution, it changes from run to block or the wait state. The process advances to the
ready state after the I/O operation is completed or the resource becomes available.

Process Scheduling
The process scheduling is the activity of the process manager that handles the removal of
the running process from the CPU and the selection of another process on the basis of a
particular strategy.
Process scheduling is essential part of a Multiprogramming operating systems. Such
operating systems allow more than one process to be loaded into the executable memory at
a time and the loaded process shares the CPU using time multiplexing.

Categories of Scheduling
There are two categories of scheduling:
 Non-preemptive: Here the resource can‟t be taken from a process until the process
completes execution. The switching of resources occurs when the running process
terminates and moves to a waiting state.
 Preemptive: Here the OS allocates the resources to a process for a fixed amount of
time. During resource allocation, the process switches from running state to ready
state or from waiting state to ready state. This switching occurs as the CPU may give
priority to other processes and replace the process with higher priority with the
running process.

Process Scheduling Queues

The OS maintains all Process Control Blocks (PCBs) in Process Scheduling Queues. The
OS maintains a separate queue for each of the process states and PCBs of all processes in
the same execution state are placed in the same queue. When the state of a process is
changed, its PCB is unlinked from its current queue and moved to its new state queue. The
Operating System maintains the following important process scheduling queues
 Job queue: This queue keeps all the processes in the system.
 Ready queue: This queue keeps a set of all processes residing in main memory,
ready and waiting to execute. A new process is always put in this queue.
 Device queues: The processes which are blocked due to unavailability of an I/O
device constitute this queue.

The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.).
The OS scheduler determines how to move processes between the ready and run queues
which can only have one entry per processor core on the system; in the above diagram, it
has been merged with the CPU.
Schedulers: Schedulers are special system software which handle process scheduling in
various ways. Their main task is to select the jobs to be submitted into the system and to
decide which process to run. Schedulers are of three types.
 Long-Term Scheduler
 Short-Term Scheduler
 Medium-Term Scheduler

Long-term schedulers are in charge of determining the order in which processes are
executed and managing the execution of processes that may take a long time to complete,
such as batch jobs or background tasks.
A long-term scheduler‟s primary function is to minimize processing time by taking the
mixtures of CPU-bound jobs and I/O-bound jobs.

[Link]
Short Term Scheduler: It is also called as CPU scheduler. Its main objective is to increase
system performance in accordance with the chosen set of criteria. It is the change of ready
state to running state of the process. CPU scheduler selects a process among the processes
that are ready to execute and allocates CPU to one of them.
Short-term schedulers, also known as dispatchers, make the decision of which process to
execute next. Short-term schedulers are faster than long-term schedulers.

The medium-term scheduler is also known as the switching scheduler

The medium-term scheduler is part of the swapping function in an operating system. It's
responsible for temporarily removing processes from the main memory and placing them in
secondary storage, like a disk drive. This process is called swapping out or swapping in

The degree of multiprogramming is the maximum number of processes that a single-

processor system can run efficiently. The main factor that affects the degree of
multiprogramming is the amount of memory available for the processes.

Basis Short-Term Scheduler Medium-term Scheduler Long-Term Scheduler

It is also called a CPU It is also called a process It is also called a job
Alternate Name
scheduler. swapping scheduler. scheduler.
It provides lesser control It reduces the control over
Degree in It controls the degree of
over the degree of the degree
programming multiprogramming.
multiprogramming. of multiprogramming.
The speed of the short- Speed of medium The speed of a long-
term scheduler is very scheduler between the term term scheduler is
Speed
fast. short-term and long-term more than medium-
scheduler term scheduler.
Usage in time- It is almost absent or
It is minimal in the time- It is a part of the time-
sharing system minimal in a sharing
sharing system. sharing system.
sharing system system.
It can reintroduce the from
among the process into It selects processes
It selects the processes
memory that executes and from the pool and loads
Purpose from among the process
its execution can be them into memory for
that is ready to execute.
continued. execution.

Process state is ready to Process state is not Process state is new to

Process state
running present ready.
Select that process, which
Select a good process ,
Selection of Select a new process for is currently not need to
mix of I/O bound and
process a CPU quite frequently. load fully on RAM, so it
CPU bound.
swap it into swap partition.

Inter-Process Communication (IPC)

The way in which processes communicate with each other is called IPC. We know that
different processes running in a system and these processes may need to communicate
each other. Interprocess communication (IPC) is a process that allows different processes of
a computer system to share information.

Necessary of Inter process Communication

IPC lets different programs run in parallel, share data, and communicate with each other. It‟s
important for two reasons:
 It speeds up the execution of tasks.
 It ensures that the tasks run correctly and in the order that they were executed.
 IPC is essential for the efficient operation of an operating system.
 Operating systems use IPC to exchange data with tools and components that the
system uses to interact with the user, such as the keyboard, the mouse, and the
graphical user interface (GUI).
 IPC also lets the system run multiple programs at the same time. For example, the
system might use IPC to provide information to the windowing system about the
status of a window on the screen.

Comparison with a real-life example

When you are using a team-based system, it is necessary to communicate with all the teams
in the company. Some of them are the Business Objects and product sales teams, and
others are the technical teams. Communication between them will speed up the work and
overall efficiency will also increase. So, in the same way, an operating system allows a
particular program to handle several user requests simultaneously. And overall efficiency will
increase.
Processes executing concurrently in the operating system may be either independent or
cooperting processes. These processes may be independent or cooperting processes

 Independent process: A process that cannot be affected by other processes, and does
not affect them either. Independent processes do not share data with other processes
or systems. Independent Processes are those processes whose task is not dependent
on any other processes. An independent process is not affected by the execution of
other processes
 Cooperating process: A process that can affect or be affected by other
processes. Cooperating processes share data with other processes and systems.
 Cooperating Processes are those processes that depend on other processes or
processes. They work together to achieve a common task in an operating system.
These processes interact with each other by sharing the resources such as CPU,
memory, and I/O devices to complete the task. Co-operating process can be affected by
other executing processes. in reality, there are many situations when cooperative nature
can be utilized for increasing computational speed, convenience, and modularity.
Inter process communication needed in Cooperating Processes.

There are several reasons for providing an environment that allows process cooperation
Information sharing: Several users may be interested in a single piece of information.
Example: Shared file
Information can be shared concurrently.
Computational Speed up: In order to achieve Computational Speed if we having a task,
divide the task into several subtasks and all these subtasks to make run concurrently in that
way we can speed up the system, instead of taking one task waiting for it complete from
beginning to till end. We can break the task into several subtasks and all the subtasks will
be made to run concurrently and hence can achieve more speed in our system. When we
do that when tasks are broken down into several different tasks they are assigned to several
different processes. Since all these processes are belong to one single task or one main
task those processes need to communicate each other.
Modularity: We want to design the system by dividing into seperate modules. Later these
modules put together to achieve a single goal.
Convenience: If we allow the processes to cooperate with other that become very
convenient for user.
User may be use different tasks at the same time. Different processes are running at the
same time.
Cooperting processes require an IPC mechanism that will allow them to exchange data and
information. There are two fundamental models of interprocess communication.
 Shared memory model
 Message passing model
In shared memory model, a region of memory that is shared by cooperting processes is
established. Portion of memory shared by all the processes cooperting each other.
Processes can then exchange information by reading and writing data to the shared region.
Whenever one process wants communicate with another it will do is write the information or
the thing that want to share or communicate to the other processes into that shared memory
region and the other processes can read that data that was written by first process from the
shared memory region and then it will understand what it actually try to communicate.
Suppose process A wants to communicate with process B and needs to attach it is address space to
this shared memory segment. Process A will write a message to the shared memory, and Process B
will read that message from the shared memory. So, processes are responsible for ensuring
synchronization so that both processes do not write to the same location at the same time.

Message Passing: Another important way inter-process communication occurs with other
processes is via message passing. When two or more processes participate in inter-process
communication, each process sends messages to the others via Kernel. Here is an example
of sending messages between two processes: – Here, the process sends a message like
“M” to the OS kernel. This message is then read by Process B. A communication link is
required between the two processes for successful message exchange. There are several
ways to create these links.

Message passing: in the message passing model communication takes place by means of
messages exchanged between the cooperting processes.
The processes communicate with each other by exchanging messages. For this purpose,
a Communication Link must exist between the processes and it must facilitate at least two
operations send (message) and receive (message). The size of messages may be variable
or fixed.

Advantages of Interprocess Communication

 Interprocess communication allows one application to manage another and enables
glitch-free data sharing.
 Interprocess communication helps send messages efficiently between processes.
 The program is easy to maintain and debug because it is divided into different
sections of code that work separately.
 Programmers can perform a variety of other tasks at the same time, including
Editing, listening to music, compiling, etc.
 Data can be shared between different programs at the same time.
 Tasks can be subdivided and run on special types of processors. You can then
exchange data via IPC.

Disadvantages of Interprocess Communication

 The program cannot write to similar locations.
 Processes or programs that use the shared memory model must make sure that they
are not writing to similar memory locations.
 The shared storage model can cause problems such as storage synchronization and
protection that need to be addressed.
 It‟s slower than a direct function call.
Critical Section Problem

The critical section is a code segment where the shared variables can be accessed. An
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.

A diagram that demonstrates the critical section is as follows

In the above diagram, the entry section handles the entry into the critical section. It acquires
the resources needed for 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.

Solution to the Critical Section Problem

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.
Semaphores are a tool used in computer science to help manage how different processes
(or programs) share resources, like memory or data, without causing conflicts. These are
used to implement critical sections, which are regions of code that must be executed by
only one process at a time. By using semaphores, processes can coordinate access to
shared resources, such as shared memory or I/O devices.
Semaphores are just normal variables used to coordinate the activities of multiple
processes in a computer system. They are used to enforce mutual exclusion, avoid race
conditions, and implement synchronization between processes.
A race condition in an operating system (OS) is a situation where multiple processes or
threads are executing simultaneously, and the outcome depends on the order in which
they are executed. This can lead to unexpected or incorrect results, such as system
crashes, incorrect outputs, or security breaches.
The process of using Semaphores provides two operations: wait and signal
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. When the value of the semaphore is zero, any
process that performs a wait operation will be blocked until another process performs a
signal operation.
When a process performs a wait operation on a semaphore, the operation checks whether
the value of the semaphore is >0. If so, it decrements the value of the semaphore and lets
the process continue its execution; otherwise, it blocks the process on the semaphore.
wait(S)
{
while (S<=0);

S--;
}

Signal: The signal operation increments the value of its argument S. A signal operation on a
semaphore activates a process blocked on the semaphore if any, or increments the value
of the semaphore by 1. Due to these semantics, semaphores are also called counting
semaphores. The initial value of a semaphore determines how many processes can get
past the wait operation.
signal(S)
{
S++;
}
Types of Semaphores
There are two main types of semaphores i.e. counting semaphores and binary semaphores.
  Counting Semaphores: These are integer value semaphores and have an
unrestricted value domain. These semaphores are used to coordinate the resource
access, where the semaphore count is the number of available resources. If the
resources are added, semaphore count automatically incremented and if the
resources are removed, the count is decremented.
 Binary Semaphores: The binary semaphores are like counting semaphores but their
value is restricted to 0 and 1. The wait operation only works when the semaphore is 1
and the signal operation succeeds when semaphore is 0. It is sometimes easier to
implement binary semaphores than counting semaphores.
Difference between Counting and Binary Semaphores
Criteria Binary Semaphore Counting Semaphore
A counting semaphore is a
A Binary Semaphore is a
semaphore that has multiple values of
semaphore whose integer
the counter. The value can range over
value range over 0 and 1.
an unrestricted domain.
typedef struct {
int semaphore_variable;
typedef struct {
Structure Queue
Implementation
int semaphore_variable;
list; //A
}binary_semaphore;
queue to store the list of task
}counting_semaphore;
0 means that a process or a
thread is accessing the
The value can range from 0 to N,
critical section, other
where N is the number of process or
Representation process should wait for it to
thread that has to enter the critical
exit the critical section. 1
section.
represents the critical
section is free.
Yes, it guarantees mutual No, it doesn‟t guarantees mutual
exclusion, since just one exclusion, since more than one
Mutual Exclusion
process or thread can enter process or thread can enter the critical
the critical section at a time. section at a time.
No, it doesn‟t guarantees
bounded wait, as only one Yes, it guarantees bounded wait,
process can enter the critical since it maintains a list of all the
section, and there is no limit process or threads, using a queue,
Bounded wait
on how long the process can and each process or thread get a
exist in the critical section, chance to enter the critical section
making another process to once. So no question of starvation.
starve.
No waiting queue is present
then FCFS (first come first Waiting queue is present then FCFS
Starvation serve) is not followed (first come first serve) is followed
so,starvation is possible and so,no starvation hence no busy wait.
busy wait present
Used only for a single
Used for any number of instance of
Number of instance of resource type
instance
resource of type [Link] can be used for
[Link] can be usedonly for 2
any number of processes.
processes.
 Operating System Handout

Unit IV – CPU Scheduling and Algorithm

Section 4.1 Scheduling types
Scheduling Objectives
 Be Fair while allocating resources to the processes
 Maximize throughput of the system
 Maximize number of users receiving acceptable response times.
 Be predictable
 Balance resource use
 Avoid indefinite postponement
 Enforce Priorities
 Give preference to processes holding key resources
 Give better service to processes that have desirable behaviour patterns

CPU and I/O Burst Cycle:

 Process execution consists of a cycle of CPU execution and I/O wait.
 Processes alternate between these two states.
 Process execution begins with a CPU burst, followed by an I/O burst, then another CPU
burst ... etc
 The last CPU burst will end with a system request to terminate execution rather than
with another I/O burst.
 The duration of these CPU burst have been measured.
 An I/O-bound program would typically have many short CPU bursts, A CPU-bound
program might have a few very long CPU bursts.
 This can help to select an appropriate CPU-scheduling algorithm.

Mr. [Link] Page 1 of 18

 Operating System Handout

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

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

Basis for
Preemptive Scheduling Non Preemptive Scheduling
Comparison
Once resources are allocated to a
The resources are allocated to a process, the process holds it till it
Basic
process for a limited time. completes its burst time or switches to
waiting state.
Process can be interrupted in Process can not be interrupted till it
Interrupt
between. terminates or switches to waiting state.
If a high priority process
If a process with long burst time is
frequently arrives in the ready
Starvation running CPU, then another process with
queue, low priority process may
less CPU burst time may starve.
starve.
Preemptive scheduling has
Non-preemptive scheduling does not
Overhead overheads of scheduling the
have overheads.
processes.
Flexibility Preemptive scheduling is flexible. Non-preemptive scheduling is rigid.
Preemptive scheduling is cost Non-preemptive scheduling is not cost
Cost
associated. associative.

Scheduling Criteria

 There are several different criteria to consider when trying to select the "best"
scheduling algorithm for a particular situation and environment, including:
o CPU utilization - Ideally the CPU would be busy 100% of the time, so
as to waste 0 CPU cycles. On a real system CPU usage should range from
40% ( lightly loaded ) to 90% ( heavily loaded. )
o Throughput - Number of processes completed per unit time. May range
from 10 / second to 1 / hour depending on the specific processes.

Mr. [Link] Page 2 of 18

 Operating System Handout

o Turnaround time - Time required for a particular process to complete,

from submission time to completion.
o Waiting time - How much time processes spend in the ready queue
waiting their turn to get on the CPU.
o Response time - The time taken in an interactive program from the
issuance of a command to the commence of a response to that command.

In brief:
Arrival Time: Time at which the process arrives in the ready queue.
Completion Time: Time at which process completes its execution.
Burst Time: Time required by a process for CPU execution.
Turn Around Time: Time Difference between completion time and arrival time.
Turn Around Time = Completion Time – Arrival Time
Waiting Time(W.T): Time Difference between turnaround time and burst time.
Waiting Time = Turn Around Time – Burst Time

4.2 Types of Scheduling Algorithm

(a) First Come First Serve (FCFS)

In FCFS Scheduling
 The process which arrives first in the ready queue is firstly assigned the CPU.
 In case of a tie, process with smaller process id is executed first.
 It is always non-preemptive in nature.
 Jobs are executed on first come, first serve basis.
 It is a non-preemptive, pre-emptive scheduling algorithm.
 Easy to understand and implement.
 Its implementation is based on FIFO queue.
 Poor in performance as average wait time is high.

Advantages-
 It is simple and easy to understand.
 It can be easily implemented using queue data structure.
 It does not lead to starvation.
Disadvantages-
 It does not consider the priority or burst time of the processes.
 It suffers from convoy effect i.e. processes with higher burst time arrived before
the processes with smaller burst time.

Mr. [Link] Page 3 of 18

 Operating System Handout

Example 1:

Example 2:
Consider the processes P1, P2, P3 given in the below table, arrives for execution in
the same order, with Arrival Time 0, and given Burst Time,
PROCESS ARRIVAL TIME BURST TIME
P1 0 24
P2 0 3
P3 0 3
Gantt chart

P1 P2 P3
0 24 27 30

Mr. [Link] Page 4 of 18

 Operating System Handout

PROCESS WAIT TIME TURN AROUND TIME

P1 0 24
P2 24 27
P3 27 30

Total Wait Time = 0 + 24 + 27 = 51 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes) = 51/3 = 17 ms

Total Turn Around Time: 24 + 27 + 30 = 81 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
= 81 / 3 = 27 ms
Throughput = 3 jobs/30 sec = 0.1 jobs/sec
Example 3:
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution
in the same order, with given Arrival Time and Burst Time.
PROCESS ARRIVAL TIME BURST TIME
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Gantt chart
P1 P2 P3 P4
0 8 12 21 26

PROCESS WAIT TIME TURN AROUND TIME

P1 0 8–0=8
P2 8–1=7 12 – 1 = 11
P3 12 – 2 = 10 21 – 2 = 19
P4 21 – 3 = 18 26 – 3 = 23

Total Wait Time:= 0 + 7 + 10 + 18 = 35 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)= 35/4 = 8.75 ms

Total Turn Around Time: 8 + 11 + 19 + 23 = 61 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
61/4 = 15.25 ms

Throughput: 4 jobs/26 sec = 0.15385 jobs/sec

Mr. [Link] Page 5 of 18

 Operating System Handout

(b) Shortest Job First (SJF)

 Process which have the shortest burst time are scheduled first.
 If two processes have the same bust time, then FCFS is used to break the tie.
 This is a non-pre-emptive, 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.
 Pre-emptive mode of Shortest Job First is called as Shortest Remaining Time
First (SRTF).

Advantages-
 SRTF is optimal and guarantees the minimum average waiting time.
 It provides a standard for other algorithms since no other algorithm performs
better than it.

Disadvantages-
 It can not be implemented practically since burst time of the processes can not
be known in advance.
 It leads to starvation for processes with larger burst time.
 Priorities can not be set for the processes.
 Processes with larger burst time have poor response time.

Example-01:
Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time
P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3
Solution-
If the CPU scheduling policy is SJF non-preemptive, calculate the average waiting
time and average turnaround time.
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Mr. [Link] Page 6 of 18

 Operating System Handout

Process Id Exit time Turn Around time Waiting time

P1 7 7–3=4 4–1=3
P2 16 16 – 1 = 15 15 – 4 = 11
P3 9 9–4=5 5–2=3
P4 6 6–0=6 6–6=0
P5 12 12 – 2 = 10 10 – 3 = 7
Now,
 Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
 Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

Example-02:
Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time
P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3
If the CPU scheduling policy is SJF pre-emptive, calculate the average waiting time and
average turnaround time.
Solution-
Gantt Chart-

Process Id Exit time Turn Around time Waiting time

P1 4 4–3=1 1–1=0
P2 6 6–1=5 5–4=1
P3 8 8–4=4 4–2=2
P4 16 16 – 0 = 16 16 – 6 = 10
P5 11 11 – 2 = 9 9–3=6

Now,

 Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit

 Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

Mr. [Link] Page 7 of 18

 Operating System Handout

Example-03:

Consider the set of 6 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 7
P2 1 5
P3 2 3
P4 3 1
P5 4 2
P6 5 1

If the CPU scheduling policy is shortest remaining time first, calculate the average
waiting time and average turnaround time.
Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 19 19 – 0 = 19 19 – 7 = 12
P2 13 13 – 1 = 12 12 – 5 = 7
P3 6 6–2=4 4–3=1
P4 4 4–3=1 1–1=0
P5 9 9–4=5 5–2=3
P6 7 7–5=2 2–1=1

Now,
 Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit
 Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

Mr. [Link] Page 8 of 18

 Operating System Handout

Example -04:

Consider the set of 3 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 9
P2 1 4
P3 2 9

If the CPU scheduling policy is SRTF, calculate the average waiting time and average
turn around time.

Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 13 13 – 0 = 13 13 – 9 = 4
P2 5 5–1=4 4–4=0
P3 22 22- 2 = 20 20 – 9 = 11

Now,
 Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
 Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

Example-05:

Consider the set of 4 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 20
P2 15 25
P3 30 10
P4 45 15

Mr. [Link] Page 9 of 18

 Operating System Handout

If the CPU scheduling policy is SRTF, calculate the waiting time of process P2.

Solution-

Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Thus,
 Turn Around Time of process P2 = 55 – 15 = 40 unit
 Waiting time of process P2 = 40 – 25 = 15 unit

(c) Round Robin Scheduling

 CPU is assigned to the process on the basis of FCFS for a fixed amount of time.
 This fixed amount of time is called as time quantum or time slice.
 After the time quantum expires, the running process is preempted and sent to the
ready queue.
 Then, the processor is assigned to the next arrived process.
 It is always preemptive in nature.

Mr. [Link] Page 10 of 18

 Operating System Handout

Advantages-

 It gives the best performance in terms of average response time.

 It is best suited for time sharing system, client server architecture and
interactive system.

Disadvantages-

 It leads to starvation for processes with larger burst time as they have to repeat
the cycle many times.
 Its performance heavily depends on time quantum.
 Priorities can not be set for the processes.

With decreasing value of time quantum,

 Number of context switch increases
 Response time decreases
 Chances of starvation decreases

Thus, smaller value of time quantum is better in terms of response time.

With increasing value of time quantum,

 Number of context switch decreases
 Response time increases
 Chances of starvation increases

Thus, higher value of time quantum is better in terms of number of context switch.

 With increasing value of time quantum, Round Robin Scheduling tends to

become FCFS Scheduling.
 When time quantum tends to infinity, Round Robin Scheduling becomes FCFS
Scheduling.
 The performance of Round Robin scheduling heavily depends on the value of
time quantum.
 The value of time quantum should be such that it is neither too big nor too
small.

Example-01:
Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

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

Mr. [Link] Page 11 of 18

 Operating System Handout

If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate
the average waiting time and average turnaround time.
Solution-
Ready Queue- P5, P1, P2, P5, P4, P1, P3, P2, P1
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time
P1 13 13 – 0 = 13 13 – 5 = 8
P2 12 12 – 1 = 11 11 – 3 = 8
P3 5 5–2=3 3–1=2
P4 9 9–3=6 6–2=4
P5 14 14 – 4 = 10 10 – 3 = 7
Now,
 Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit
 Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit
Problem-02:
Consider the set of 6 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time

P1 0 4

P2 1 5

P3 2 2

P4 3 1

P5 4 6

P6 6 3
If the CPU scheduling policy is Round Robin with time quantum = 2, calculate the average
waiting time and average turnaround time.
Solution-
Ready Queue- P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1
Gantt chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Mr. [Link] Page 12 of 18

 Operating System Handout

Process Id Exit time Turn Around time Waiting time

P1 8 8–0=8 8–4=4
P2 18 18 – 1 = 17 17 – 5 = 12
P3 6 6–2=4 4–2=2
P4 9 9–3=6 6–1=5
P5 21 21 – 4 = 17 17 – 6 = 11
P6 19 19 – 6 = 13 13 – 3 = 10
Now,
 Average Turn Around time = (8 + 17 + 4 + 6 + 17 + 13) / 6 = 65 / 6 = 10.84 unit
 Average waiting time = (4 + 12 + 2 + 5 + 11 + 10) / 6 = 44 / 6 = 7.33 unit
Problem-03: Consider the set of 6 processes whose arrival time and burst time are
given below-
Process Id Arrival time Burst time
P1 5 5
P2 4 6
P3 3 7
P4 1 9
P5 2 2
P6 6 3
If the CPU scheduling policy is Round Robin with time quantum = 3, calculate the
average waiting time and average turnaround time.
Solution-
Ready Queue- P3, P1, P4, P2, P3, P6, P1, P4, P2, P3, P5, P4
Gantt chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time
P1 32 32 – 5 = 27 27 – 5 = 22
P2 27 27 – 4 = 23 23 – 6 = 17
P3 33 33 – 3 = 30 30 – 7 = 23
P4 30 30 – 1 = 29 29 – 9 = 20
P5 6 6–2=4 4–2=2
P6 21 21 – 6 = 15 15 – 3 = 12

Mr. [Link] Page 13 of 18

 Operating System Handout

Now,

 Average Turn Around time = (27 + 23 + 30 + 29 + 4 + 15) / 6 = 128 / 6 = 21.33 unit

 Average waiting time = (22 + 17 + 23 + 20 + 2 + 12) / 6 = 96 / 6 = 16 unit

(d) Priority Scheduling

 Out of all the available processes, CPU is assigned to the process having the
highest priority.
 In case of a tie, it is broken by FCFS Scheduling.
 Priority Scheduling can be used in both preemptive and non-preemptive mode.

 The waiting time for the process having the highest priority will always be zero in
preemptive mode.
 The waiting time for the process having the highest priority may not be zero in non-
preemptive mode.
Priority scheduling in preemptive and non-preemptive mode behaves exactly same under
following conditions-
 The arrival time of all the processes is same
 All the processes become available
Advantages-
 It considers the priority of the processes and allows the important processes to
run first.
 Priority scheduling in pre-emptive mode is best suited for real time operating
system.
Disadvantages-
 Processes with lesser priority may starve for CPU.
 There is no idea of response time and waiting time.

Problem-01:
Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time Priority

P1 0 4 2

P2 1 3 3

P3 2 1 4

P4 3 5 5

P5 4 2 5

If the CPU scheduling policy is priority non-preemptive, calculate the average waiting time
and average turnaround time. (Higher number represents higher priority)

Mr. [Link] Page 14 of 18

 Operating System Handout

Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time
P1 4 4–0=4 4–4=0
P2 15 15 – 1 = 14 14 – 3 = 11
P3 12 12 – 2 = 10 10 – 1 = 9
P4 9 9–3=6 6–5=1
P5 11 11 – 4 = 7 7–2=5
Now,
 Average Turn Around time = (4 + 14 + 10 + 6 + 7) / 5 = 41 / 5 = 8.2 unit
 Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit

Problem-02: Consider the set of 5 processes whose arrival time and burst time are
given below-
Process Id Arrival time Burst time Priority
P1 0 4 2
P2 1 3 3
P3 2 1 4
P4 3 5 5
P5 4 2 5
If the CPU scheduling policy is priority preemptive, calculate the average waiting
time and average turn around time. (Higher number represents higher priority).
Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time
P1 15 15 – 0 = 15 15 – 4 = 11
P2 12 12 – 1 = 11 11 – 3 = 8
P3 3 3–2=1 1–1=0
P4 8 8–3=5 5–5=0
P5 10 10 – 4 = 6 6–2=4

Mr. [Link] Page 15 of 18

 Operating System Handout

Now,
 Average Turn Around time = (15 + 11 + 1 + 5 + 6) / 5 = 38 / 5 = 7.6 unit
 Average waiting time = (11 + 8 + 0 + 0 + 4) / 5 = 23 / 5 = 4.6 unit

(d) Multilevel Queue Scheduling

A multi-level queue scheduling algorithm partitions the ready queue into several separate
queues. The processes are permanently assigned to one queue, generally based on some
property of the process, such as memory size, process priority, or process type. Each queue has
its own scheduling algorithm.
Let us consider an example of a multilevel queue-scheduling algorithm with five queues:
1. System Processes
2. Interactive Processes
3. Interactive Editing Processes
4. Batch Processes
5. Student Processes
Each queue has absolute priority over lower-priority queues. No process in the batch queue,
for example, could run unless the queues for system processes, interactive processes, and
interactive editing processes were all empty. If an interactive editing process entered the ready
queue while a batch process was running, the batch process will be pre-empted.

4.3 Deadlock
 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.
 For example, in the below diagram, Process 1 is holding Resource 1 and waiting for
resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.

Mr. [Link] Page 16 of 18

 Operating System Handout

Deadlock can arise if following four necessary conditions hold simultaneously.

1. Mutual Exclusion: One or more than one resource are non-sharable means Only one
process can use at a time.
2. Hold and Wait: A process is holding at least one resource and waiting for another
resources.
3. No Pre-emption: A resource cannot be taken from a process unless the process releases
the resource means the process which once scheduled will be executed till the
completion and no other process can be scheduled by the scheduler meanwhile.
4. Circular Wait: A set of processes are waiting for each other in circular form means
All the processes must be waiting for the resources in a cyclic manner so that the last
process is waiting for the resource which is being held by the first process.
Difference between Starvation and Deadlock
Sr. Deadlock Starvation

Starvation is a situation where the low

Deadlock is a situation where no process got
1 priority process got blocked and the high
blocked and no process proceeds
priority processes proceed.

2 Deadlock is an infinite waiting. Starvation is a long waiting but not infinite.

3 Every Deadlock is always a starvation. Every starvation need not be deadlock.

The requested resource is blocked by the other The requested resource is continuously be
4
process. used by the higher priority processes.

Deadlock happens when Mutual exclusion, hold

It occurs due to the uncontrolled priority and
5 and wait, No preemption and circular wait
resource management.
occurs simultaneously.

Deadlock Handling
The various strategies for handling deadlock are-
1. Deadlock Prevention
2. Deadlock Avoidance
3. Deadlock Detection and Recovery
4. Deadlock Ignorance
1. Deadlock Prevention
 Deadlocks can be prevented by preventing at least one of the four required
conditions:
Mutual Exclusion
 Shared resources such as read-only files do not lead to deadlocks.
 Unfortunately, some resources, such as printers and tape drives, require exclusive
access by a single process.
Hold and Wait
 To prevent this condition processes must be prevented from holding one or more
resources while simultaneously waiting for one or more others.

Mr. [Link] Page 17 of 18

 Operating System Handout

No Preemption
 Preemption of process resource allocations can prevent this condition of deadlocks,
when it is possible.
Circular Wait
 One way to avoid circular wait is to number all resources, and to require that processes
request resources only in strictly increasing ( or decreasing ) order.
2. Deadlock Avoidance
 In deadlock avoidance, the operating system checks whether the system is in safe state
or in unsafe state at every step which the operating system performs.
 The process continues until the system is in safe state.
 Once the system moves to unsafe state, the OS has to backtrack one step.
 In simple words, The OS reviews each allocation so that the allocation doesn't cause
the deadlock in the system.

3. Deadlock detection and recovery

 This strategy involves waiting until a deadlock occurs.
 After deadlock occurs, the system state is recovered.
 The main challenge with this approach is detecting the deadlock.

4. Deadlock Ignorance
 This strategy involves ignoring the concept of deadlock and assuming as if it does not
exist.
 This strategy helps to avoid the extra overhead of handling deadlock.
 Windows and Linux use this strategy and it is the most widely used method.

Mr. [Link] Page 18 of 18

 Introduction of Deadlock in Operating System
DEFINATION: 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.
Under the normal mode of operation, a process may utilize a resource in
only the following sequence:
1. Request: If the request cannot be granted immediately (for example,
the resource is being used by another process), then the requesting
process must wait until it can acquire the resource.

2. Use: The process can operate on the resource (for example, if the
resource is a printer, the process can print on the printer).

3. Release: The process releases the resource.

Consider an example when two trains are coming toward each other
on the same track and there is only one track, none of the trains can
move once they are in front of each other. A similar situation occurs in
operating systems when there are two or more processes that hold
some resources and wait for resources held by other(s). For example,
in the below diagram, Process 1 is holding Resource 1 and waiting for
resource 2 which is acquired by process 2, and process 2 is waiting for
resource 1.
Deadlock System Model − The Deadlock System model is a way to
describe and analyze systems that may be prone to deadlocks, which
occur when two or more processes are unable to proceed because they
are each waiting for the other to release a resource. Below are the
components of this model −
 Resources − The system has a set of resources that are shared
among processes. These resources can be hardware or software
components, such as memory, files, printers, or network
connections. Each resource is identified by a unique name or
identifier.
 Processes − The system has a set of processes that request and
release resources. Processes are units of execution that can be
started, suspended, resumed, and terminated. Each process is
identified by a unique process ID.
 Resource Allocation − Each resource can be in one of two states ,
allocated or available. A resource that is allocated to a process
cannot be used by any other process until it is released.
 Request and Release − A process can request a resource by
sending a request to the system. If the resource is available, it will
be allocated to the process. When a process is finished using a
resource, it must release it so that it can be used by other processes.
 Resource Dependency − Some processes may require multiple
resources to complete their tasks. A resource dependency graph
can be used to represent the relationships between processes and
resources and to detect potential deadlocks.
 Deadlock Detection − A deadlock can occur when two or more
processes are waiting for resources that are being held by other
processes, creating a circular dependency. Deadlock
detection algorithms can be used to detect when a deadlock has
occurred, so that corrective action can be taken.
 Deadlock Resolution − Once a deadlock has been detected, it can
be resolved by breaking the circular dependency between the
processes. This can be done by releasing one or more resources that
are being held by a process, or by preempting one or more
 processes that are holding resources. The Working of some of the
techniques are given below –
o Resource preemption is a technique used to break the
circular wait condition of a deadlock. The operating system
can preempt resources from one or more processes involved
in the deadlock and allocate them to the processes that need
them. Preemption can be done either selectively or globally.
In selective preemption, only the resources that are required
to resolve the deadlock are preempted, while in global
preemption, all the resources held by the deadlocked
processes are preempted.
o When a process is terminated, all the resources held by
the process are released, and other processes can proceed.
However, this approach can lead to data loss and
inconsistency if the terminated process was in the middle of a
critical task.
 Deadlock Avoidance − Deadlock avoidance is a technique used
to prevent the occurrence of deadlocks in a computer system. The
goal of deadlock avoidance is to ensure that all resources required
by a process are available before the process starts execution,
thereby avoiding the possibility of deadlock.
Difference between Starvation and Deadlock
Sr. Deadlock Starvation

1 Deadlock is a situation where no process got Starvation is a situation where the low
blocked and no process proceeds priority process got blocked and the high
priority processes proceed.

2 Deadlock is an infinite waiting. Starvation is a long waiting but not

infinite.

3 Every Deadlock is always a starvation. Every starvation need not be deadlock.

4 The requested resource is blocked by the The requested resource is continuously be
other process. used by the higher priority processes.

5 Deadlock happens when Mutual exclusion, It occurs due to the uncontrolled priority
hold and wait, No preemption and circular and resource management.
wait occurs simultaneously.

Deadlocks characterization:
Necessary conditions for Deadlocks:
Deadlock can arise if the following four conditions hold
simultaneously (Necessary Conditions)

1. Mutual Exclusion
A resource can only be shared in mutually exclusive manner. It
implies, if two processes cannot use the same resource at the same
time.
2. Hold and Wait
A process waits for some resources while holding another resource
at the same time.

3. No preemption
The process which once scheduled will be executed till the
completion. No other process can be scheduled by the scheduler
meanwhile.
4. Circular Wait
All the processes must be waiting for the resources in a cyclic
manner so that the last process is waiting for the resource which is
being held by the first process.
methods for handling Deadlock
1. Deadlock prevention:
Deadlock happens only when Mutual Exclusion, hold and wait, No
preemption and circular wait holds simultaneously. If it is possible to
violate one of the four conditions at any time then the deadlock can
never occur in the system.
The idea behind the approach is very simple that we have to fail one of
the four conditions but there can be a big argument on its physical
implementation in the system.
2. Deadlock avoidance:
In deadlock avoidance, the operating system checks whether the
system is in safe state or in unsafe state at every step which the operating
system performs. The process continues until the system is in safe state.
Once the system moves to unsafe state, the OS has to backtrack one step.
In simple words, The OS reviews each allocation so that the allocation
doesn't cause the deadlock in the system.
3. Deadlock detection and recovery:
This approach let the processes fall in deadlock and then periodically
check whether deadlock occur in the system or not. If it occurs then it
applies some of the recovery methods to the system to get rid of
deadlock.

Resource-Allocation Graph
The resource allocation graph is the pictorial representation of the state
of a system. As its name suggests, the resource allocation graph is the
complete information about all the processes which are holding some
resources or waiting for some resources.
It also contains the information about all the instances of all the
resources whether they are available or being used by the processes.
In Resource allocation graph, the process is represented by a Circle
while the Resource is represented by a rectangle.
Example:
Let's consider 3 processes P1, P2 and P3, and two types of resources R1
and R2. The resources are having 1 instance each.

According to the graph, R1 is being used by P1, P2 is holding R2 and

waiting for R1, P3 is waiting for R1 as well as R2.

The graph is deadlock free since no cycle is being formed in the graph

Deadlock Detection using RAG

If a cycle is being formed in a Resource allocation graph where all the
resources have the single instance then the system is deadlocked.

In Case of Resource allocation graph with multi-instanced resource

types, Cycle is a necessary condition of deadlock but not the sufficient
condition.
The following example contains three processes P1, P2, P3 and three
resources R2, R2, R3. All the resources are having single instances each.

If we analyze the graph then we can find out that there is a cycle formed
in the graph since the system is satisfying all the four conditions of
deadlock.
Deadlock Prevention
Deadlock prevention is a technique used in operating systems to ensure
that deadlocks, which are situations where two or more processes are
unable to proceed because each is waiting for the other to release a
resource, do not occur. It involves designing the system in such a way
that at least one of the necessary conditions for deadlock cannot hold.
This typically requires careful resource allocation and tracking, as well
as enforcing certain rules and protocols to prevent deadlock formation.
Deadlock Characteristics
The deadlock has the following characteristics:
1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait
We can prevent a Deadlock by eliminating any of the above four
conditions.
Eliminate Mutual Exclusion: It is not possible to dis-satisfy
the mutual exclusion because some resources, such as the tape drive
and printer, are inherently non-shareable.
Eliminate Hold and wait: Allocate all required resources to the
process before the start of its execution, this way hold and wait
condition is eliminated but it will lead to low device utilization. for
example, if a process requires a printer at a later time and we have
allocated a printer before the start of its execution printer will remain
blocked till it has completed its execution. The process will make a new
request for resources after releasing the current set of resources. This
solution may lead to starvation.

Eliminate No Preemption : Preempt resources from the process when

resources are required by other high-priority processes.
Eliminate Circular Wait : Each resource will be assigned a numerical
number. A process can request the resources to increase/decrease. order
of numbering. For Example, if the P1 process is allocated R5 resources,
now next time if P1 asks for R4, R3 lesser than R5 such a request will
not be granted, only a request for resources more than R5 will be
granted.
Deadlock Avoidance:
Deadlock avoidance is another technique used in operating
systems to deal with deadlocks. Unlike deadlock prevention, which
aims to eliminate the possibility of deadlocks, deadlock avoidance
focuses on dynamically detecting and avoiding situations that could
lead to deadlocks. It involves analyzing the resource allocation state
and resource requests made by processes to determine if granting a
request would potentially result in a deadlock. If a potential deadlock is
detected, the system can make decisions to avoid it by selectively
granting or denying resource requests.
Resource Allocation Graph:
Resource Allocation Graph (RAG) is a popular technique used for
deadlock avoidance. It is a directed graph that represents the processes
in the system, the resources available, and the relationships between
them. A process node in the RAG has two types of edges, request edges,
and assignment edges.

In order to avoid deadlocks, the process must tell OS, the maximum
number of resources a process can request to complete its execution.

The simplest and most useful approach states that the process should
declare the maximum number of resources of each type it may ever
need. The Deadlock avoidance algorithm examines the resource
allocations so that there can never be a circular wait condition.

Safe and Unsafe States:

The resource allocation state of a system can be defined by the instances

of available and allocated resources, and the maximum instance of the
resources demanded by the processes. A state of a system recorded at
some random time is shown below.
 Resources Assigned

Process Type 1 Type 2 Type 3 Type 4

A 3 0 2 2

B 0 0 1 1

C 1 1 1 0

D 2 1 4 0

Resources still needed

Process Type 1 Type 2 Type 3 Type 4

A 1 1 0 0

B 0 1 1 2

C 1 2 1 0

D 2 1 1 2

1. E = (7 6 8 4)
2. P = (6 2 8 3)
3. A = (1 4 0 1)
Above tables and vector E, P and A describes the resource allocation
state of a system. There are 4 processes and 4 types of the resources in a
system. Table 1 shows the instances of each resource assigned to each
process.

Table 2 shows the instances of the resources, each process still needs.
Vector E is the representation of total instances of each resource in the
system.

Vector P represents the instances of resources that have been assigned to

processes. Vector A represents the number of resources that are not in
use.

A state of the system is called safe if the system can allocate all the
resources requested by all the processes without entering into deadlock.

If the system cannot fulfill the request of all processes then the state of
the system is called unsafe.

The key of Deadlock avoidance approach is when the request is made

for resources then the request must only be approved in the case if the
resulting state is also a safe state.

Deadlock Detection
Deadlock Detection in OS, with this type of deadlock, multiple
processes try to acquire resources simultaneously but fail due to
insufficient resources at any given time. To avoid such problems, an OS
must periodically check the acquisition of resources by processes and
release any locked resources if necessary.

Purpose of deadlock detection algorithm:

 The purpose of a deadlock detection algorithm is to identify and
resolve deadlocks in a computer system.
 It does so by identifying the occurrence of a deadlock, determining
the processes and resources involved, taking corrective action to
break the deadlock, and restoring normal system operations.
  The algorithm plays a crucial role in ensuring the stability and
reliability of the system by preventing deadlocks from causing the
system to freeze or crash.

.The deadlock Detection Algorithm is of two types:

 Wait-for-Graph Algorithm (Single Instance)
 Banker’s Algorithm (Multiple Instance)

Wait-for-Graph Algorithm: It is a variant of the Resource Allocation

graph. In this algorithm, we only have processes as vertices in the
graph. If the Wait-for-Graph contains a cycle then we can say the
system is in a Deadlock state. Now we will discuss how the Resource
Allocation graph will be converted into Wait-for-Graph in an
Algorithmic Approach. We need to remove resources while converting
from Resource Allocation Graph to Wait-for-Graph.

Algorithm:
Step 1: Take the first process (Pi) from the resource allocation graph
and check the path in which it is acquiring resource (Ri), and start a
wait-for-graph with that particular process.
Step 2: Make a path for the Wait-for-Graph in which there will be no
Resource included from the current process (P i) to next process (Pj),
from that next process (Pj) find a resource (Rj) that will be acquired by
next Process (Pk) which is released from Process (Pj).
Step 3: Repeat Step 2 for all the processes.
Step 4: After completion of all processes, if we find a closed-loop
cycle then the system is in a deadlock state, and deadlock is detected.
Now we will see the working of this Algorithm with an Example.
Consider a Resource Allocation Graph with 4 Processes P1, P2, P3, P4,
and 4 Resources R1, R2, R3, R4.
Find if there is a deadlock in the Graph using the Wait for Graph-based
deadlock detection algorithm.
Step 1: First take Process P1 which is waiting for Resource R1,
resource R1 is acquired by Process P2, Start a Wait-for-Graph for the
above Resource Allocation Graph.

Step 2: Now we can observe that there is a path from P1 to P2 as P1 is

waiting for R1 which is been acquired by P2. Now the Graph would be
after removing resource R1 looks like.
Step 3: From P2 we can observe a path from P2 to P3 as P2 is waiting
for R4 which is acquired by P3. So make a path from P2 to P3 after
removing resource R4 looks like.

Step 4: From P3 we find a path to P4 as it is waiting for P3 which is

acquired by P4. After removing R3 the graph looks like this.

Step 5: Here we can find Process P4 is waiting for R2 which is

acquired by P1. So finally the Wait-for-Graph is as follows :

Step 6: Finally In this Graph, we found a cycle as the Process P4 again

came back to the Process P1 which is the starting point (i.e., it’s a
closed-loop). So, According to the Algorithm if we found a closed
loop, then the system is in deadlock state. So here we can say the
system is in a deadlock state.

Banker's Algorithm:
It is a banker algorithm used to avoid deadlock and allocate
resources safely to each process in the computer system. The 'S-
State' examines all possible tests or activities before deciding whether
the allocation should be allowed to each process. It also helps the
operating system to successfully share the resources between all the
processes. The banker's algorithm is named because it checks whether a
person should be sanctioned a loan amount or not to help the bank
system safely simulate allocation resources. In this section, we will learn
the Banker's Algorithm in detail. Also, we will solve problems based
on the Banker's Algorithm.

When a new process is created in a computer system, the process must

provide all types of information to the operating system like upcoming
processes, requests for their resources, counting them, and delays. Based
on these criteria, the operating system decides which process sequence
should be executed or waited so that no deadlock occurs in a system.
Therefore, it is also known as deadlock avoidance algorithm or deadlock
detection in the operating system.

When working with a banker's algorithm, it requests to know about three

things:

1. How much each process can request for each resource in the
system. It is denoted by the [MAX] request.
2. How much each process is currently holding each resource in a
system. It is denoted by the [ALLOCATED] resource.
3. It represents the number of each resource currently available in the
system. It is denoted by the [AVAILABLE] resource.
Following are the important data structures terms applied in the banker's
algorithm as follows:

Suppose n is the number of processes, and m is the number of each type

of resource used in a computer system.

1. Available: It is an array of length 'm' that defines each type of

resource available in the system. When Available[j] = K, means
that 'K' instances of Resources type R[j] are available in the
system.
2. Max: It is a [n x m] matrix that indicates each process P[i] can
store the maximum number of resources R[j] (each type) in a
system.
3. Allocation: It is a matrix of m x n orders that indicates the type of
resources currently allocated to each process in the system. When
Allocation [i, j] = K, it means that process P[i] is currently
allocated K instances of Resources type R[j] in the system.
4. Need: It is an M x N matrix sequence representing the number of
remaining resources for each process. When the Need[i] [j] = k,
then process P[i] may require K more instances of resources type
Rj to complete the assigned work.

Need[i][j]=max[i][j]-Allocation[i][j].

5. Finish: It is the vector of the order m. It includes a Boolean value

(true/false) indicating whether the process has been allocated to the
requested resources, and all resources have been released after
finishing its task.

The Banker's Algorithm is the combination of the safety algorithm and

the resource request algorithm to control the processes and avoid
deadlock in a system:
 Safety Algorithm
It is a safety algorithm used to check whether or not a system is in a safe
state or follows the safe sequence in a banker's algorithm:

1. There are two vectors Wok and Finish of length m and n in a safety
algorithm.

Initialize: Work = Available

Finish[i] = false; for I = 0, 1, 2, 3, 4… n - 1.

2. Check the availability status for each type of resources [i], such as:

Need[i]<=Work
Finish[i]==false
If the i does not exist, go to step 4.

3. Work = Work +Allocation (i) // to get new resource allocation

Finish[i] = true

Go to step 2 to check the status of resource availability for the next

process.

4. If Finish[i] == true; it means that the system is safe for all processes.
Resource Request Algorithm

A resource request algorithm checks how a system will behave when a

process makes each type of resource request in a system as a request
matrix.

Let create a resource request array R[i] for each process P[i]. If the
Resource Request [j] equal to 'K', which means the process P[i] requires
'k' instances of Resources type R[j] in the system.
1. When the number of requested resources of each type is less than
the Need resources, go to step 2 and if the condition fails, which means
that the process P[i] exceeds its maximum claim for the resource. As the
expression suggests:

IfRequest(i)<=Need
Go to step 2;

2. And when the number of requested resources of each type is less than
the available resource for each process, go to step (3). As the expression
suggests:

IfRequest(i)<=Available
Else Process P[i] must wait for the resource since it is not available for
use.

3. When the requested resource is allocated to the process by changing

state:

Available=Available-Request
Allocation(i)=Allocation(i)+Request(i)
Needi = Needi - Requesti

When the resource allocation state is safe, its resources are allocated to
the process P(i). And if the new state is unsafe, the Process P (i) has to
wait for each type of Request R(i) and restore the old resource-allocation
state.

Example: Consider a system that contains five processes P1, P2, P3, P4,
P5 and the three resource types A, B and C. Following are the resources
types: A has 10, B has 5 and the resource type C has 7 instances.

Process Allocation Max Available

A B C A B C A B C

P1 0 1 0 7 5 3 3 3 2
P2 2 0 0 3 2 2
P3 3 0 2 9 0 2
P4 2 1 1 2 2 2
P5 0 0 2 4 3 3

Answer the following questions using the banker's algorithm:

1. What is the reference of the need matrix?

2. Determine if the system is safe or not.
3. What will happen if the resource request (1, 0, 0) for process P1
can the system accept this request immediately?

Ans. 2: Context of the need matrix is as follows:

Need[i]=Max[i]-Allocation[i]
Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

Process Need
A B C

P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1
Hence, we created the context of need matrix.

Ans. 2: Apply the Banker's Algorithm:

Available Resources of A, B and C are 3, 3, and 2.

Now we check if each type of resource request is available for each

process.

Step 1: For Process P1:

Need <= Available

7, 4, 3 <= 3, 3, 2 condition is false.

So, we examine another process, P2.

Step 2: For Process P2:

Need <= Available

1, 2, 2 <= 3, 3, 2 condition true

New available = available + Allocation

(3, 3, 2) + (2, 0, 0) => 5, 3, 2

Similarly, we examine another process P3.

Step 3: For Process P3:

P3 Need <= Available

6, 0, 0 < = 5, 3, 2 condition is false.

Similarly, we examine another process, P4.

Step 4: For Process P4:
P4 Need <= Available

0, 1, 1 <= 5, 3, 2 condition is true

New Available resource = Available + Allocation

5, 3, 2 + 2, 1, 1 => 7, 4, 3

Similarly, we examine another process P5.

Step 5: For Process P5:

P5 Need <= Available

4, 3, 1 <= 7, 4, 3 condition is true

New available resource = Available + Allocation

7, 4, 3 + 0, 0, 2 => 7, 4, 5

Now, we again examine each type of resource request for processes P1

and P3.

Step 6: For Process P1:

P1 Need <= Available

7, 4, 3 <= 7, 4, 5 condition is true

New Available Resource = Available + Allocation

7, 4, 5 + 0, 1, 0 => 7, 5, 5

So, we examine another process P2.

Step 7: For Process P3:

P3 Need <= Available

6, 0, 0 <= 7, 5, 5 condition is true

New Available Resource = Available + Allocation

7, 5, 5 + 3, 0, 2 => 10, 5, 7

Hence, we execute the banker's algorithm to find the safe state and
the safe sequence like P2, P4, P5, P1 and P3.
Ans. 3: For granting the Request (1, 0, 2), first we have to check
that Request <= Available, that is (1, 0, 2) <= (3, 3, 2), since the
condition is true. So the process P1 gets the request immediately.

Deadlock Recovery :
A traditional operating system such as Windows doesn’t deal with
deadlock recovery as it is a time and space-consuming process. Real-
time operating systems use Deadlock recovery.
Process Termination
To eliminate the deadlock, we can simply kill one or more processes.
For this, we use two methods:
1. Abort all the Deadlocked Processes: Aborting all the processes
will certainly break the deadlock but at a great expense. The
deadlocked processes may have been computed for a long time and
the result of those partial computations must be discarded and there
is a probability to recalculate them later.

2. Abort one process at a time until the deadlock is eliminated:

Abort one deadlocked process at a time, until the deadlock cycle is
eliminated from the system. Due to this method, there may be
considerable overhead, because after aborting each process, we have
to run a deadlock detection algorithm to check whether any
processes are still deadlocked.
Advantages of Process Termination
 It is a simple method for breaking a deadlock.
 It ensures that the deadlock will be resolved quickly, as all processes
involved in the deadlock are terminated simultaneously.
 It frees up resources that were being used by the deadlocked
processes, making those resources available for other processes.
Disadvantages of Process Termination
 It can result in the loss of data and other resources that were being
used by the terminated processes.
 It may cause further problems in the system if the terminated
processes were critical to the system’s operation.
 It may result in a waste of resources, as the terminated processes
may have already completed a significant amount of work before
being terminated.

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

3. Starvation: In a system, it may happen that the same process is

always picked as a victim. As a result, that process will never
complete its designated task. This situation is called Starvation and
must be avoided. One solution is that a process must be picked as a
victim only a finite number of times.

Advantages of Resource Preemption

1. It can help in breaking a deadlock without terminating any
processes, thus preserving data and resources.
2. It is more efficient than process termination as it targets only the
resources that are causing the deadlock.
3. It can potentially avoid the need for restarting the system.
Disadvantages of Resource Preemption
1. It may lead to increased overhead due to the need for determining
which resources and processes should be preempted.
2. It may cause further problems if the preempted resources were
critical to the system’s operation.
3. It may cause delays in the completion of processes if resources are
frequently preempted.
Unil
MemoxyTManagconur.
:
Definition
KeMemonymanoqenent isthe prDcess
of Contholioq orordinaliogu
Computesmtmory
koowsas
portiongi
assigoing blockstovaou
to optimiseheloueral|o
uOninqproqramgi
q the [Link]
performanc 900r

functions
MemoTmanaqements the funclional:
a antoswhab handles07managcs
primar bomemnctsorplog

ocation i°isallo
etheo caledto
Some prbes

Itchechs how much2 meroon ig to be *

catudto Ss.0ronTO
alio prDCe

1t decidesubichprocesswiltqt nemory
at whatatime
33001
BasicHadwaTe into
Rotothe
ibutlts
Maiosmemovy the eqista
&

itsf
processo are thedeuice
only storage
that can acgs directly
Thattake
There are machbiocinstructions
mtmory adde SSeg as anqumertsbutthy
( StcondaU
will not takr disk addresScs
memory Throre anyiostructons %
Euccatiorn
&

must be
tngtueb'on
Tfthedalais not o
imatn
anudata beinguscd
of the
he maio memor
memoTythy
 the CPO Cao oper
must be movecd there btfore
onthem to protect
hasi
hotCortoperation
Ensure
he os om àccessinq b ustI
o proccSS &

hddtion
otePo usY prucess
to protecttht frorm

must beprouid
Ont a00ther Thiçihoprolection
by theHtardwaTe.
> has
Cacb process a memoTyspaa
Sepavat
to determin
t

dothisweDeed the abilitu th

addessthat
nangeioteqal theproce$s
thattheproces
mauiacccsStonEnsuTe
Can acCessonl thereleqaladdresses
XrUei we canprovide
1htsprotetiogby usiag
bq
aNdtosrqistets lmitneislz
lonamel baselte
xx BaseQrqisterr Specifte& leqal
theasmallest
physicalmemoT oddessiC on
Stantnqdocati
Lureco
Limt Req'ster ogiu
- Speciesithe
3 q gang
CSi2e O process).
3ri Bast and in
limitReqisles memory
opaeingeesio
UrobB00040a228bbo
Ur Base

iprocesti
Procass
lo24400
 Pag epacemo
AApoi lsase linit
spacl
th logico oddess
6
& lspecifi
ioragislers

RIo th aboue{iTthes
holds B0904
base reqisles
is1204
limiteqsates
9 0o
theoproqromconq all acassl
addesse
om 420
300040 to 40
Ondy theOS
only 0s Can loadthebascEnlinit
aotgistea
* Logical memoT address - u

d oATô by CPUswhilea proqio

Qodratedd
isTunninqhd logicala addnessis Virtdl
addressas it does noto&ristaphsicall
thureloeisalsoknouonas vittual adds
This addss t usedoias toba
a tftrena
access the physicolDemoru location
by CPU
Th Tenglogical oddessspaces used or
th set qa loqicaladdress qnuYas loy
a proqamspespecivas
Thu hodware deoic callec memorymana
Qumutunid isused
isgcd fon mappi nglogica
aldarss o its Caricspondingphusaladehe
Physicalsoddrss
H Tdtifes
ina
în
Tequireddata a
physicalocati
ac
memor the ser uuer
o

diretldaals withThe phsicaladdress but

canacassby
ttscorItuending addre
togltal
 qnerolesHhe
ustrproqrom Logical
The
addrss thinksthallh proqrams Tun
nddessbut theproqrac
but
to thislogicaliaddaess h
ts
nudsphusícalmemoTLyor Ts facantor
addrssmust
logical
sthregoret be mappd
tothphusic oddaess
by MMU before
aruscd.
x bitweeological
Diffre0a & Addess
Phystcal
Spaa
poinlor oddaess
logical
onparision spac spaca.
220rbboworolopip
J Bosta isqLatralad
CPU
uuhileo
by His(ompatid
proqram
by
MMUoConemoTU
s unning
)AddressSet
o all Logica
a isetngtall
phsica
LspaceaddsSesqeneratedby addrrsss
rmappdto
CPU fer a protpamGoTits
pondingog
Mbap eavbhooipdaddesses.
D Loqical
Existancc addss
Exist The plysical
addyes
ooteolvintualq
thad claesnat In an accessil
locatton physical
haueispaifra tocatic
in fishog wttßiot
t Eaist physically
huncah
memory unit,
knownas
ftisralso
3 virtuoaddressonf

the lheuSed Ca0 nwe

useTCanvieu
4)visibiltu|he
loqical % u'eo
addvess the physica
a program. q progro
address
 useruses
6)AcceSSlhe the uusesicannot
ta diretlyaccess
address
logical
the
phisiadphsICala
ooottssthe
addeSS

JRebost Systemeboots,TfaSqglerorebo
theLogicaladdss
Shtbe phystcal
istE.
lmunoy
bevanishedoaddsses
will
001

Memo ManaqenentUnttaLMMUJ. ROy

300 from Logtcal
Thácamiicomappingi
calad
to physi dmssisdoneby hadware
doices CalledmemoryD hanaqementuni
To ilushatethe mapping oithMMUS use
the qentialisatioo base meaistm)i
he base igisleaig no0sCalledas
oegislersbodo2doadl
elocation is
•The valueoin tt locati803isled
re
by a
addedt61éueTy addessgntTatd
LSeT pro $sot lhe ime
Ce
i4 ise
Sertto
noiominoTY onibatdile
o2
Logicoiha9iToPhqsical SyachsMain
ccaddes
|o5
amie

agistes
on uingclacalon
Dynamienelacali
G
E Tf the base i5t lo5,hereaouStx
attioplsa poceSSThen addtSSlocato
sacoes
tcnamtcallq.
to loois
Locaticon
to ocalion
located o5
mapped to 9og
CPO will qeoerale logca address
uoniog
ohilenunninglh mh
proqro MMUwil!
naddthe alu q melocalion ( 1os
register
So th phustcal
is
mmonaddresGorProai
YAddreSS Bioding-
H ispr ss q mappinqfrom one
*Adrss
binding
Can occus at 3 differer
[Link]
i5CompiletirneIfyoukoouw ad compile
timecubere esYdesi in main mernoy
thenabsolute Coderalcanbe cqnrated
} Lo adlime - 1 itiskáoona conpil
me wheretbe processiutwill stde'
thecompi len mustqentrale omelocatab
code & finalbindinq is delayedtil
Loadtime.
he
iisCzecutiontime I{ The procesScanbe
duringts ecution
movec duriog from one
memeTy Stomunto anotherthenbindig
rus
must Be dzayed
untiluntime
Swappiog
I is a Simple meno or protS
managimnt melhod used'
byThe opeyal?ng
 JH isiprodeG9 O aprocs5
Swappinq

8to
dbnimain
backinqu
me
)e
stor Csecondar
disk the broughtback
botchavd
mory
main
o
mumo TJ
to
the ezeulo
contiouc
menbTUSnot Enough
olwhence@u
to tmporanily
Stord ulHplepoqrarns
ODheowTTakeg fro9RAM
SomedProqrorm
uQlsbrethemtolhehand bysa
diskb
igpoMachanisCalleoo Swop outSimilony
Caiiwhên broyBoough
RAM isiofrecio to Store
Swap io
Tlhunh
prograims- in thouprograms
Krom hard dsk to RAM.

Swap 0t The proqra

Deansltake
um stcondaTù memoT
Themiog
mary nenLoTotanStoeo
ttr d digk)Soapoa
on
cutaloleimage
procesSplacesthefze
laatdrdice
iht Sttondaryiastoragi
• Swap fo meanstakeThe prbqran
from
horddsk& storethem inRAMaSuap tn prbccs
itnaga
backco Ezccaltable
takeslhtocopiss
suappedoutiprousshronnSttand
dhepreviouslap
hainimnmory
bintoc loeoition. oia

salgoitbm
Ez?-Tn RoundTobiodscheduling
when atimenuantum [Link] memoT
manags oillsartto Swap outthe proes
inan
6 toSw appedo
thot hs nqustofinished
hea intommorg
procc6S2 spacethahasbecn
deallo
cgted
 Can be usedforprio
voriantSwappinqIf a hiqherprforitu
A
ithmTf
thm
alqori 6m
cation
Scheduling for
allo
mcmoTy
processTeguest beo occupied
isahad ful or ithas pre -

dowprioity proCeSGesorOCcapid b
b Somc Theo memoT manag1
ty
high priori prDceSSts
a low piorit9
Can ditrrmie to Swapout
proctssesSo That higherpriorit pocess°c
Gzecutedt5zecutioo thelower
beloaded
processcan now be Swappedinagain
prioity Thisi
tts fxccution
lcontioue UcriatSwapping
Doo Jooor
turodas Roll-orta
policqis
x Advantaqes
The process
processes
This me
belpstheoPU
titoiotheSa
to' nana
rme nmain
thodhelpsto cCreat &u
€ruse
mg
gu nulip

nemoT
imethod
This ?s econ
omifcal.
Bett

ad vontaqts
Dis
Jn the
-osolb
prformance
o

i
CPO.

ase o heauySwappioq
aclivity
power theuser
the ComputessyctrsIoses
if

might losealltheinformationmelatedto the

proqraD.
TH numbii pag faults e
increaSesonithe
decreastSTheOvttall prformanemio oe
Jo cffiitntly ma amives
iis
otoreSOurceSD9r afvaiable
fvataalei
.
inCast uhere
iusedby
is Co nnmonly
otheproiastesuhichaTecusing tochin
anSwapping
bslppolos
 Memory Allocalion-so
(6AD09Po
ás a prpiesSby
onte Memory allocolion
cohichi aare as3iqned to
compatesproqtams mernor

Space dlloca
alhe art
oT
memoTallocotion
nemoTy altodation
c bl3)Non Contiqeous
9lbou3
altocctio
Cootiqeou'sMemory
9
in onthaooDdoCE6Contieous memoryiallo
all, spact memaing Togeth
theaucilaole memnory
gh
fn ont place TH mansfreclyavailabl
blocksae not Scattred hee& there acros
theswholenemori ispaceo3ci2bidoioy
The main memomis dividedintostwo
oncLportiontsforHos other
partiionsie &

Fishfor Tht useT [Link]

To cootiquousmtrhoTy Qwheothe
ermo7y allocation
fosthe modyllQueie
3dlprocessolamives
toithe
The Contiquous
main memoTyfo fzcculion
blocksarea l1ocatedtoThe procLsS
mernoy
accordíngto itsrequiremenl.
oooila

DYD0of2

troario
haaraai
 memoryallocalion
) ontiqeous
b)Loben afile C trininates
thuftles
mleasesMhe no
mmerty creat'ng holem
D Fized Siacdpartiion
or StatieConttoa
Memory allocattonom3o2bos0ihooD G
o Here mermoTyisondividedattofi
Cblocks)&
Size partition Each blockconl
ont prodesSButdsastä
ezactly ed part:
Twtllintthe- degre)
qâamutiproqramm
bpo asthe numby o blockotuill
the numbry elth
decid
or (ao
odbrthoo2 eoold
siedpatitioo
a) Variable dynamicCoti
ocation307niso
quou nonyivaume

otteretheacóso
onalysis
thumcmoT
Gtha
Tequirement theoprDcesS
wihasa
memoT blocko
theurcquiredi
athto
sttu tothe
tfiatncntnoyyblock
allocateg
procesS)T

¥ Creotioo
of i
Holes8 aliot potbrn0
Tniötially
the
uhole memoT spaa is
the user procesSesas a larae
Qw oilable
for
blockor bole wheneveTtheprocess large
isani ve
Ro the memoTy the proCESS qats
Executed
Jerminated! memory here theprous
CreatestheSt o holesof uan'able sizesp
x If tbe memor hole istoolarqe forlhe pioa
Ih
into
itgcissplit Two paTTs ontpart
themenmoTyhole isallocatedto the arived
process& theotherpartis etuvned tothe
 Set oabolesyuheo a prodcsstrrmin
E thelomtm
Teleases it,
oru allocatedto
he Ts teplad
mleascdimengoYu back
20D thostonholes that
Thetuo holes:

rmrgedttoforr
folesor oneLarghole
Now atthisBoiotos checksohth,this
lavqeholeisableto
X

newlyformedfree
satishy otherad qúcued
processewaiinq
th proLSSalQoesS oniiookdrg
Thre ar 3 ahgorith
Startangies
to Selectthe free hole fomset o holes
D Grst 1) best ft
2r0DociotocnportIomr
D Frst ft stuitsscan
This alqozithmo
fom the beginning
tions serialq
the parti
uohenanEmptol thotis biq ênodqht
iporfion
a Stortthe procšSisfound then thatholeis
toilallocaledtotheiproas$20rsrouCanSay
thifrsthole
altocátes thotiselbi enoughi.
The Si2e o hole hastobe qreatesthano7
3sotleastequaloito theLprocs siaes
2U009
eslo
o War

lo
+ Pie
(12

Fqti bq P
Memorg blocksthotaTe occupied
hgii Empty holes.s
P,PPsa
P
booRef abouefiqore ss Phroso
itproce
I5ktwonts to lallocate memoT thott chooses
Becausciol frst fit itsearohesfor
an
thalisEnoagh
Enyptihole to Storeisthe
spac
r
processC 35 k D
lsk so 5 k ts ocdupied
alaloDiolodoprol ocuotulos
.
* Advanlags Grstft negtitse
Tt is aste
sti searchias
i1f1Seavches
ondythe
HstEmpty blockfs Enoughto
eslo
ocateE n 3n
Easy to all
* Disadvantagestood
Ezlernal
haqmotation
ocurs
oobJastoqe o spacclo17
poinaipsdsf
GtC
fnoughtoStvse prbCess
Shov

B Besttt
allthe
alqoithn
bparions
Ernpty
o

firstS
Thiso
blocks
tfun p7
Cans
itoll
o catesuthc osi
oSmollestzéd tho block
isÉnouo sto stoethatipiocasst
eslooola
ttu Fiqi
Rafert1 1foproces$PiofSi2e
1S k wnts spaaio memoTyThen 20 k block
is allocatd.
because asitscansalltheEmph
mernoTyholesthuoit choosesThe Somallest
thotsenoughto sort-tlatprouss. ho
•Advantaaes
Less wastaqespaaas compared
memoTye efiient asthe
to frst
0S the
allocateg
t
jobot in
process minimumpossibl
spaa
 Drsadvantagts
-
oCuTs
Fagmntation
Exfernal
THs theime Consuminq proces S

ernptyholes
Slow,checkscoh all for
o
job makesthe workingq the0s
eachjab
slow
3orst
Gmply
t
memoTQ
IH allth
alsoScasfor
largsst thupro
siztp0titionto ess
the iq11,f proceSS P, wants
rrfr
Exrefr
Spac inmemoT biy using worS fit
it
kSi2ed memoT block
calesthedtoo
Urcalo
9xiH atoibobio2i
hdvantaggs-t3Upr22 ta new
Bdvantags space
23v9TheotDnaining callocated

°Snternal
hagmentaior gsoinaft
occurS
ss can bepla
ccd
cOveYSpa ce thA oTherproct

Disadvontagunind
IH iShtioe processaci2
consumingproeesshsol
Tt fs alsosoulprocss289er

Hagmentotion are loaded

As proceSSes E movedfom
memor Thefe memor Spaceisbrokenito
ittlepicces. Can'1be allocated
The proccoes
to

Thost 0; tememoYy blocks. this

considening
s ame remains
SmollerSize& memoig block Unuse
s
Tbisproblem known as fragmntation.
 space(Redarea)
astage
a
CUnused)

spacefoqontel
Alscald
Bastcalltherrare two typcs
to fragatrit
Tatinalhaqmntationrrnsryplgn

D Ioternal
fragmentation
3-Ewoglingoxagspat
IHoccunts
occuhenThe menoTy
isdivided
ioto ixed Sized blocks whie
processmeguest for [Link]
fd siaxdblockgRs aliocated tos theproS
To case The memoTY assiqnedto fhuprocs
proco
isisomerusht arq 1hantheimehor
iTeauetted theocthe bts assigthe
differeiceo
erequested memoTy
emary
isthcîternalfaamta
* This"leftourr spaceinside theofized
SiRedblock can
notio
processasitaDoQld
toang
be'sallocated
onotossufeiiet to
satisfyThe Tequesto m moTybby the procas
spaL Used
sUsedsp
Used
aotwohdos
Spaco astedaso spaca
4 7515MB T

30 M8attL
spaGcrfor
Ossiarud
Assighudispadfoy
2id
1,5b0M8
Procss proass 500 M6
 Joterna wiloccuvsbecau
fragmrstolion
we haueixed sicsi0)the rnernoT blockS
lhisOroblermCan beomemovedif wa uSe
dynamicor variablesi2ed bastiion, &Pac
The processisallocatedonty thatmuch
amountospaceo ashichiismequiTedab fha
proces9 So there is nointenal
fraqrmentati
Woldelioumarcoihosa
)Ezternalfraqmentation d bofipse 0
It o ccuTSwhoTher isai
amount or
Sufficiert
sSatisfu
dhamemoTiquest moTyeoiSavai
butfhe cmemoTyauatlablets to nonhcor
qeousmonne heneprocesssrmemorya
Mequest
caonoto
[Link].0ubsAMOO Dp
XCtther,jouuiappl rsto
or best d memo
allocatioo
stattrquwillCausesEternol
wiT1 a
qmetationor 9
ProceSs1
osAvat
lalbleoenssn
o ProaesS3 oo io
inoanCorligd

clwt
lóan2nnovesithe
EztemalFracamenta
by usinqCompachíon,
bq
inqall he femamoT
meansmTq
Compaction
tocethin ongLarge blsck
Thistechnigur
ts
epAAtai
 alsocalledas de kagmentatioo
Thislarge.
block o memoTYishinused foY allocahi
to1he needgq teibs
Spaceaccovdinq thene
proCesSes.d

i)Non1Contiqtous
anosoe
memor allocation
Jo1heino
ContiqtousmemoT
Qllocation
1heavailable
free memor Spau a
andatheeall
scattcred
here fee o tinoT spau
isnot at oneplaceacubsa
ot doliLo the nonrconti
guousmimoTal0c
tion
a processoillacquire
thememory spaa
but itisi not atoncplaceoits attfie
drfe
to the processrequiremeot
Aocations Thistecb
-que o NCMA Tducesthof aslaqocnarno
w Non Contiqous memyallocaionhauing
techniques uo)WiuswputoteOoitooollo
1 Paaing ) Seqmentat
Paging
Paqing thephysical
permits address spa
o a fo be Ttisa fzd
non-contiqous.
proceSs
size
partitioning Tothepaqinqtich
schemt.
the sccondaru
memory & maio memor ar dividu
ióto
equal d-size
partitions.
• Ihe poaqcso proccssar Storediothefame
naio nemorydeprndinq
upon
Theiy
Quaila
o1alhen
paceSiae hamesi2CShould
away!
loeSame
ur onstder
a processSi2¢ is 4 bqlespags
is1bye so we Candiuideioa Process
i6to4 pagcsPo,P, P. and P.
Thatisnurmber Pages size
= process Ipage
4/1 = 4
 Translating addrss
the logical intoPhysica
addess:
CPU address.
alwoysqtneratesa loqical
A phuSical addessrsnecded to acces
Deededto sThe
main mernory
followinq art
sleps iowed
fol toraosl
loqtcaladdr
Ss intophustcaladdress.
Step: CPU logtca address
qunerates ddreSS Consi
slingo two paits.
Paqcnumbe ItspecifitstheSpeciftcpaqy

theproCeSS orn ohch cpo wantsto read dat

TIUspecifes
3) Paqe bifseta thespecific tword
Wion hpag tht(wantstotad
paqg
Sttprefon inurobexdqeotyat
theicpaqt bu

[Link] pagtable provides ina

the CorYrEspond fom
numbe oherethat paqe isl
Stored io
mainmemo
Step 3 : physical
tequired addre
with tân
The frame numberCornbined
paqo offsetafuon SS.

Framernumb specfics fame

The specáfice
owherethenequired page isistored.
29190 0

OfsetSpecifes the speoßcwo1dthathas

afrortdhat [Link]
to be read bo o 2h
8Aduataqes
e ioacnonContiqúousfashion
•It thsi
solues problermo fraqmta
lernal
balleoaoldst
Disadvantaqes io8biaodoc)
aoleoif
JoItasuffers romalernolfaqmentation
There isan ouhtad9mainlatoinquaPaqt
talolefo Each Process.
The, to
taken
time fththeinstruction
ipaeases
quted.
Sioce w memoTy CcesSes
 Frameofßet (19)
CPU Pagt
number
offsct number

Logical addres
Phstcali
addrss
CPU

Pogcno 90
Po
Po
023kboPa of62tbbo
bPal
PagtTableo Pa

xTranslatioo
tookaside Bufei
ICTLBbinPaginge
iforeach processpaqe
In paging tablewil
be rratedwhichuiM containPagetnlormatton
ikefane numberSome othe useulbitseThispaa
rushere n The maio
tabletalls memoythe actuad tal
A Bqhusingi
acessime
accesse
ricoun
pagtisTesfdinq: 0or
pagtTablet incrtases
due to ioreased
[Link] uses8megoT
eficRencuPres
numbT memo
accesses
Loto qt the fame numb frompagatalble
Gne
anothes
I
is to getpage lot Frorm thu page d
&

TU
x If the process isbtq,thcopage tabks
šiRe
olsobeCorne bq. If we Sore ThigopgtTtabtes
oioTeqistess,tht qislerSmay nst holdalthe
pag talalesbecauseq theii e

Toouy
Siae.
gmallero
-torothis
ComeThisprobleo u sea Small,
special fast oti ke
Lookup blw issetupfor page tables
Called
TranslationLookasideBaferCTLBD.«piCi E
TLBnas high spead logemoTnyedto keepitack
Teanlq yed transcalion
gCcMostaiedpaa tallatht
parisdots
C Paqe unbeyand
frarmenumber.r
23223030
19 with TLB
tardawae
Poging
addres
Logical
CPU
P NooframNo
iTLBbit
hiPhusteal
addess022o
331 bd o

Eidscdu
o0ipo 2
TLB 3004
TLB toiss
22xrbb0 eoip

Paqesid lilsoal
The TLBContainsonlya a fewo fhepage

tableentitsoheneuer theLoqical addTessiš

i ts umoer is
qenesatedb y the CPU
tofheTLB.
theo page pag
Prrseted theo itsfanm
th page umber is found
& is usedto
• f
numbris oomediatal auatloble
Qrder to access the memoY Thisiskooun as

TUB hit.
Tocase ifthc page numbe isnotfn the TL8

Cwhichis koownasTLB miss, thenamemo

e to thupagetablimustbe used mad..
eferen to
TLB fshigh speed' memonylGcache
ikeephiackiqurTecerttysaisedlhasaotionsn
whenthu fame toumbes [Link] inadt canibe
CLsed to access Thu cnemouo
coDdoduo
Tn caseif thenTLEisaltadqhullo Eniiesthu
th0S USes pageineplamert toTepla
alqorithm
thepaqes.
 *Tagg &
FagingProtection
pagingprocessshouldbe
The proleo
byusingthe Conapto însertion q an additi
bit callednalid Tovalid [Link]
d with
asSsoctate Each pagtalole
Eotry Speifu E
protectionon1he Corrspondinq page.
is Set to validThe
* wbeo bitts &ssttatA
isiothe process'Sloqical addressSpaae thus
poqt is Leqal or Nalid.o
Nalid.
when tbe bit igSetto ipvalid the paqeis
ootfo the proccess'sogicaladdressspace thus
Ilegal addressts
a
rapped by
fiq:valid Invalid
bit o
Pagetale

Asboo
3

2 C 2
5

Leaical
eumol4 tasle
Paat 9
Stconco
Cmimoye muhort

Seqmentation
Deqo is a memory manaqiment
Searnentation
iowhich
tacbnigue the roemorpisdivfde tito
sGtheNá[Link] a
whichCan be allocatedto
b
La [Link]
i Cach Scrntnthas a namiand itslenath
Consi dér0 is
Proqpan lkhgth
s
into Seqnunts
idiytdedos
21)
slack
Subbol
Subouti 4oble
Seg 4eD)
omain 2Dpr
eieSq 62
vt Scqmird 22scbbod
Stal1
As
program a
isa
Stgnment loqical susasi
it nay any
function,
be
untt nais
datastruc
-üTNS like stack queue,araqs, trees elc
for ur s tmplermen
lation Scameols aTe
Easy
numbrde mefereocedby seqmntnunbes
catherthanStqment name
fach Seqmertare stored
Tbe detailsabort
io Tablecalledsegmesttable.
a
Seqmeottablestoresa ioform
Tbe ateon :
:
* Base Ttis stantingaddress q Seqmar
Linit
3 Itislengthq the Seqment
PIostqmentatio thelogical address
Consis
poits
Seamerit numbes:SpecißiestheSpecif'c
Seqmend g th processfrom which cPO
wonttoadthu datao2 O000
bs Scamieadoffsct the specific
Specificieg
sCwoxd iothe Seametthat0026
CPU wantsto eod

00
for thenqintrated SequrtinumbeyConspon
ingeAtrys locald intheoSeqrmend
talle
scarurt atfsctisComparedwiththusiz
baoel
Climit the Segmurtoabreno
Two Cagey ar posible,do
(2)
Lcase >= ligit
Seqment offset
if
if Segntoffsc
fssound thoe
tobeqreales
i.
equaltolimit a tropis genratd
Case Stamentoffse irnit
thenTeqursts troledas a Nalid eguest
isad ded to the
tnt offset
Theo Seqn

Fig Stqmnta w
s
baseaddtss the seqmetto phqsical
lian
Limt4 base

Segment
GRU &otolaoni w

table

yes

lel 2ii
Pianobtrapi erro inoPhysscal
addmssing

Segmesdtalle
iBase
Lint
1000

alBooG StamuntOo 3ro0

bosbo0ooAO0 32000
SeqmantSrd4000o
3500

300o o0
bsbnSeqmuntrdl
4940
Stamuad
rScanent O900
Consideran Qccessing
to ngtruclauetfonj loca
atan fßetCll4)*%buk 876nooL0D
ot
 The CPU wants to efey4hi
pyte in seqme
bybmappinqaong
uo-nt3then
314<2bolan
limittue,ttheolimit
o Seo

igLoddedto base O r35004L43GT4)

Seq 2 orC8so0H|14
b922inbmoinmemo onlocafonbho39eMUO

Advantages
Tt allous odivrdeproqvomintomoduleSo
battruser uiguali
Seqmeoswhich prouides
Hsolues leminternalfragmeo
itfheprolb
Jeqnenttale lessSpavag
foConsanes Cornpaved
2223etupagitalsleoraat2
ot rORo

%10bbtesatbhacgr
*Disaduantogu M

ternalfoqmeno
headsutoi
Th Segtntotion
bastosuitedfox
Seqmant o unequansi2eAre

batwuo pagioq
&o Seqmentatio
DifferencLs

Itma Paging
hadordrns
ooSeamentat
ad togr
fagmertot
omnttation ezternal
iottrnalra
theblw
s si2evi
Thecseqmet
do poqing userL
decides si2tl Specifiedivbu
thekpage
A processaddrSSpaaf oo
AupTOCESS addess
sd Spaceisbroken to
indif
isbrokeoiito hzed
s whichistalled nisizedbloct
are
block
Pages. bbpbioocaltedseo E

i
Toe pagtngtichniqut
faslexfu oneonoYUaess
is.
Seamurlahon slowe
Than paqingmdhed
talllsorsthe
Paqt
slor
Sernentatiortab
opag databo tuStgnentaon
data.
 VirtualMemT addresSmoTe
Smnem
ComDudes Can
Aameunt
e
Computes
phsicallq ostalledon t.
thaothe
SuttemThis Eza menoryis ig CalledbiTtual
m.

o NM Stcondar ilmemory Can beaaddesse

as though were pat q main memoTU
H

Tn Vm The useTCao stoTeProe

CanStoe Ssesott
a lbiaqry Si2e hanTheQuoilalole moin emoy

menoTislTequimd
ohyvitual ba
oINQuheneven
nConpuoes nothavespauBo fhe
mmory to stoTeprocesses
(phystcal theoprocess
ae
aTE stovedin Secondam mermory agtr gettog
Spagio SMfhe Stordprocešsint
ointo
thc PM SovitualoemorUtUsesthe
[Link]
COnce ha2
x IovM the omplateproqram oeed tobe
plaaa
ini memorycutngEzecution. fore instta
there g
Tuoningong onq proCeSS in enath memoTy
tmoTy.
the
Os doadsNariouspartsCpaqts) notc than on

processio tbemain memou.

X MM cappeais
bich ert bu not ogtaal
to be preis
presertdyMisiost geal,itiisspustt
a imagin
Ttts justollusion inagin
ton0SeT.bho22sxo
okJotking o ViTual Menorydtdes
•To Vmthe proqram qoerad addreSSeg eshal
ant
CfomedasviTtual addsses&s Setravint
headdtSseis are emn a UiTtua addrss
spad
jng rangmand Sg dqhamically
2Sqskrn bindsEnch
nlvi
stual adolresstophysicaladdrosinmai
memory hen thu Processisat uni'me
 ssSpace
Uistua!addr
is
of a process bokeo
calledpoqes The phys
Toupinto parts 9rblocks
to pagts
to
cal nemoI bloksthcdCoTCSpond
alio
o main memprqlat dhromesiomust
calle
paqcs&dmeoTyi
Tberefore
fromes
inl
pog carn be plugqcd
be Same Si2eihe an
ahy frome in physicatmainoncmoTUq
0SUrOoo
fq vitudlmtmomy.
[Link]

coPag obolddooea
sforr23o
ot
Pagt
Main m emory
20 Swap

Page
viclua)trmat paa
tole
pagts poipo
Brote eas90Sttsndaty memory
uillmaps
oiAs oaboUefiquwiTtualomemo
caloddres
s)toaphsi
addwYeSS Cpaqe
theilogicalo
[Link] paqe is prsen
that
by usinqiopag lod
in maio omoytoT hatddiskora
aitsdatattoa
be paqcsore napped6Sends
or otohard diskaoub
phusicaliroomoT
I heimain mtrmoru docsnot Contoio
thepag
gt
whichhas mapped b paqetable,theo
back from tHD by usingSwap'io
sthat page
30proceSSno)pipog onpmsbbbar
Tf thephysicalimmory
thl
isofullgthe pag
ISwappedbut
Teplaad toHD:
 Aduantaqes
The
- load&
aoiity to Gzecutoa process
Tthot
otarqT
rquirs Gmaunt q memorythaowht
a Tarqeramount
is alesb loadinqthu
ougilable by procesS inpas
uE tho fzecute
[Link]
Pun laratrproqraomsl Pm Lphast
wtlhless
advantaqes
Dis
Cons
umeS the StoraqeSpa« a harddisk
TttokesmoTt imeto s oitchblw applicati
proqrammesCan un
slouly
x mtmoT isimplemrtd
Vitual by usingdemand
paging
Dermand Paging
A demngnd paginqmechani
sm isveT.
to a paqing Systemwitk
much similag
Suappingwher processesstored theio
onl on demandnot
poges orehoaded io
adugnccAccoTding to theCornCapto VM inotda
ttozecule iaoilprocess
itis not nescesSarThat
the whole processshould
prsent in mainmmor
at the qivtohimcBu bow Can wedeciden
aduancewhichpage should inmain
beapresent
oo mernoTat otime
donpavticulax &which should
Got lhereono0a
b
aosab ToiSolwe 1hisdemandpaqingqi
Cónipt
Totoduad
demond paqinqconapt
E
Says cde
Shouldoottood an paqe intothe mainmDO
cai quired o
we shoadkoep all
thepaqesfo
Secondarymemory untldmanded by CPO.
 Hence it s called aslaz Suappesbeca ge
se

qpags
thosaapping itsdonenonlyuwh equi
byCPOigRgDenand
Paginq
Pr

A
B

P E

Mato memor Seconday

memoTY

The main tmoT fomesare Gmpl. So

întially
processCCPO) is demanding
whenevexThe fo pro ces
to main memoTyby usin
P, tht datais stored
SuapoutCioSwapping).
Supposeif ueoantto paqes
Store heag
of procesSPa in maio memTmemor is
aTeswappe
fu theounusedpages oandprocessPa
Store back t in
Out maiomenor
from the pagc
SeCondar memoTLNowNow we cao loadw

Pa procesS in main menoY.

o

Ifohe demandedipaqt ionaino

islnotipreSent
wbeoapagesf
M
K

theo Ue Calltaspaqefault,
ouTsotheqrequird paaehasto fotchedfror be

mainmino•
Secondaymemor to maio
 io)f9n
Can beuilisedith
b
beterefetc
siMemory
Memorg
to
Ifang
Tf islavqca
proqram To physicamemn
thenithlpstoTun his proatom.
No fxtrnalfagmentation
Eosyto Swap oll pages.
Disaduaataqesi
•Toternol
e
nay OccUrS.
Rogmntation
MemoT ocous Tocislonget.
acceSs longer.

Page faut handliag os in

poqe faut ocCuTS io0s tbenthat
whenpage
in
itmust be handled a SeTieS StepsRepex

L
Po

62 ulomà Pageto SM

eferena Pi
aPOdo bring
bact
pdae Pt
Pdaitoblnd
isked
fn
Mainmemoi
Stept
Check 1hea gcthc
location irefrenadi
poging
pagetalle
iofiq Tthc
wansto accesspagl
GRO
Poofpoes5oftrstitiwtlthScatchitfe
pag in th
le.
Pag tal
 not contain
3, IfThe paqe tobledoes) the pag
mol ht paqefaultoccuxsSo in
[Link] equesTedpoq
cby cpu iso
not present inpaqe tableso now"i
will be o page fault.
s soonas thopaqe
fault
OccurS the tontrolaqocs
to osulqp
n34The O wilputthe procssinwaiting
state
blockedstate now 0S wil| Search that paqeio
stoneeriseCodaryponenoryo
backing,
4sTheOS witothen tadthei
pag frómthe
loadoittoThepmain cnoTy
backingstoru& me

S* Ned tht0s cwilMiapdatetbe paqtalale

eatr
accondinglu
Gfinall
yotBe2 istaken
control, obacko
from the Qsi
theGrecutioo processsisimestarted
0

* Paredenandpagin puTedemandpaqin
paqeisnot
euen a Stogle loaded
iTo
toto memor
if Causes a paqe faultIo
ioitiallyhence suc
Case the 0s setstheinstruction theprcess pf
wbich is on a 00 emoty tesidlent
a [Link]
processimmediately fos page,
faults fte the

paqtisbrouqhtitoimemor.
0oítenslax

x Pagefaul
PaqeReplacementAlqoithmil?sta
e iscdoneben be
Paqe meplacement
page?s not found in the mainmenmor
nequested
Cpagefaulthe
te aeuavious
plaaneplacimee
ffeot
method
1Eacho
alaorithot of whbichohasladi
Du wbichthe paqe Can be eplacedg o

are3Typeslo
XMaiolynThare PRA.mo0k
iy FIÉoroEint
Ast out]as0ole 02
First
pageireplacnentalqori
Eoptinmal i
Last ecertlyus
 isnot
notaleady
aleady
paugeis
FauHst-The
fage [Link] memo
Hit-The|ggeio aleady lein meo
Civatlab
Out)g acE Ee
TOyeTEO
tFIFO Cist ToGrst
Tbiss thesimplest
tht pag plaumertolaoitt
Jo 2
Tn 0S
thistht keaps hck
hck ioallpagsi n indth
4

In
Husthetmai
eplates
H paqc that hasbeer F3
the oldest
thoimoioc
Sert in
prt nenbruHorthelonqtsttime
F,
Beladys Anomalhis phenonena O CCuss

inFTO,Thtrri ioBelady'smanomal pmoTR

wheomoTeOrnES
number g paqeafaultocourS
Qr to aprocesS.
allocated 20 o hcs
2} Consi
Ex ifConsideroa
paqe M3.0,3.S
ferenestring
ne 25G
G3hwith pagt hames 3 indthe nümbr page
paqe taults.

3b3 al 9Gob iNofaults

+G

Explantion xIoitatly
for Eztr atloslols

tmpyslstswith3
, are

paátfaulTsndgyp
toth
So cohen 3,0 Come thy aTe allocated iitL
xohto3camesitis alodio nernoyS0
ocoritnisipage
hitatbanattona0ng bas
kheo aComesaitis in menory
not auailable
bo Sonithepla
cesthe oldestpage slot
EE1 witt
Onne

*GComes. itsis
iS0
At tast
alSonot

in3(ones
pag
thememoTtx
sOvailalbleio
the oldestt
Tploces
itSnotayailasle
So itTe
3
n
sloti
o) to t
placesf sot(at uthpag
Pag fault.
3
 Dh Consides stríngA.0.1.2,0,3,
à paqeimeftrence
do,4 2, Bo,33.2o with 3 paqe fames,
Findthe numbe ) paqefauttsand hits.
3o 423
4 o 3 2o

F, K k
3 3
B 3
9

4
2k
4d
332 1

|O
oH H
IONu H

Number q paqe faulls

s 2.0 a9lqy

3 ConsidTa page frnaistringt2,3)2.45,2.4 G

21155339,2.48with paqeframes31find
oclpaqe raneso
Ebts-singnfÍFO otom
recoson

92|r B222 3
F3al
L9
33b33 33
a22d 1SSSs 8| 83
1X55 44
H H % H

Hits= Gsmlar o

ik LRulteast
yneCeotlq
used)
paqeeplaca
nent
[Link]
Sugqesls
onThe principle
woTkS
alquit
irthis
easteCertly
used
thepage hati
Tt replaces vhagenotbeeo)
Atiurefe
ired b the CPU fosThe lonqcsttime
(fas
EosConsiderpaqerefernu
sting 234.5.J,
3,1G,3.5, with4 4 paqefanes,Findthe
B
I,
number frames & hitsusing LRO.
 Hme

4
4S,4C
4
3 3
4
fa 3 3 3 33
1 55
5
H H H H
onumbespaqeHits
faultsA
numbrr
lo4
O8

:Hhut
Explanation rogoodau
ToitiallyallthcHslotsare fmply so when
.2.34 are allocated to the Ernplyslots fouY,
4 paqt fautt$

*NowSConnes
poccaTS)t 30DQ bieno) e oo
&iipaqe5 islnotprsert
i
maio memor h enapagu
in
fault0cCuTS SoITepla
8 it i0 fe slo bcz that s least
mecentls
used past i
*CPUTequtst page
paqt1aqaio paq 1 isnot
presttt htocepaq
faultoccurs. t io
Eslotat thtisloaste Centlueplak
cised
ow cpuTequest 3
io main memoul paqesobch
X
are alrrady
presert itisapaqc hit. So
DL
no Teplaameit.
Now CPU TequeSt pagL pagGit
isnot present,
fthepoq faultoccuts&lgeplacetit hante
tn F4 lst
ikethtsfollouw fOY2 used'in past
Detandn8
Ob Consid
er pageTereng
Cooa
pages.
latogua
slring0,
2o, 3,

rameSize
4 fnd thenumber fautts
hits
 o 4 2-3
2 22 22
aooo3 3
b4 4

2
Oo
H H H H
* X H H H H

0G0ADumbirq paq [Link]

faults
Hits lol2elone
pagt CoPRD
eplacernert erssen
iReplate he paqc wbichisonot usedio
in
longestdirecion dimensioó
* OPR t sbestiþaqg
qrtime fatuTe io
ment alqorithm
meplaci as it
qives tht eastnumbe q pagu fautts.
T45sLalsokoonas olaiyuogantoTG r
diBeladu'
s [Link]

Exib Considea paqe neffrence 2,3+

string1.
P G323wttth
S.13,P, 4
fame si2e nd
pagt faaltand
3 4
tt using OPR
5 23
3 3 F37

H H H. H H H
00l' Jumberopagpfaultso=
o Goibor

hitsFo
l0G
if
:
Ezplanation
allslots
Joitialty are Soiwhec)
1.
2,3.44 Cam Jhy geallocatdo
theEmpty
o
slotsinorder their,
anivalThis
isfaultsas
 ,
|O 2,1when
4 35 Qre s90t
S
auaiablei
main nemo
in
itisnot auatlable
Comes,
mtmor pagfault Teplac
wbichis
4 qorngtobe used to
fusthey
future among B4E
H
oheoacomes
thyane Ovaila
inthe eapagehit so
memorqiei Só no pa42
tot.
Tplacem
wbeoGComes,t is not auailabl in
So paq faultooccus
mmoTyohen1323 f itrplace 1
comeS,RtislCavat\a
ninthimemoTQ ineepagehit
bitgbs6 rao
rio
pag
iplacemest [Link]
Err 2t
3.0. 2, 3,o
2.3,o
4
fnna
Consider
82.I,2004 o,6A
Ting
paq mftrnastingA,D,1,2
witt
4 fame5 find
the number
paqL faults ond
hits.i sbieo
03O 42 3 o 3

2 222
fe
fa
1 X4414 4 4 4

Fi 7||73233333333|3
HH * 333
H H H H H H H H H
H

Nurnbtyo) faults
H H
clno. hils
Hit gotio Tot X lO0
Tota no. Teferenas
oibspla
Faultsaiolotal
ümbrofaaltsx lod = XI00
eeencasop)
 to ohroaproqrom 0ed spaa
process
sthanRAMorit cedospace whenRAM
largtr
isfault 0s wil|Tr to allocalespacofrom
SecondaymemoTyand behaUes ikc4 has
thatmuch amountq mern0TQ by Seruingto
that proqram
or proccssCuintualrnenor
wekno w that Euery proqram process
is
iotoSomt paqesawbeoo ptoqrom
divided neds
apagewhich is not ioRAMpCmaiymunoTu,
ipaqefault
tha isLCalled
faultoccursoS oil
s whentUTa pagpag
htryitofetchsthatpag
fromiSecondarymenoqa to suwap it
oswithon e thepogeinRemlesaapping
?nt miitboo
Defn-Thrashing
eDY Tfthepage faultandn
anda
Swapping
happrning veTyhequntl thenoS has to

Spend more time to Swapr thesepagts.

This
stateis calledas Thrashingi " this
Because
isgotngito
CPU atil:2gtion be redu
ced

2233019

31233orgooo
sldolio0D

boo
Degteeq alipugrioing
(36

22c
q multiprogromminq
•the maimum
Degree
numbeY
iTtdesei
sststhat
proCt
Singleprocesso7
Sysleom can accomalate
oriotuL
efficiertu.
The abilit9 an 0s to Ezeca
mort thanoneproqramon a Singleprotssoy
[Link]

bo ma Intheqiutndiaqramioiial
dqree o

mttiproqrammingaptosomc fzlent
o time
the CPO tili2tioois VeThiqb 6 thususti
De eSouYcesaTeo tilisedoo Ba ifwe furth
incrase thedeqre9s multi proqrarnming
t6e
CPU. tili2attonwtlfall down thesuste
E
willspent moYe limeonl inThe pagL Tepla
-mnt and th tirneta ken to Comple the
aExccutiooo thecproceSS oilt
increases.
970
Causesg Thrashing
s High deqreq muttiproqo mming o
T the numbero processes
increasinginthe memorythan keeps
number o
fomes tocatedto each process willbe
decreased.
So,lessnumbezo hamescuillbe
[Link] tothis aa page
page
faultswillocçurMore
CPO time wil be
frequentlyand moTe
bc wasted in
in out o paqesand the just
& Swapping
wl
tili2ation
keep on decreasing
 Locksofames ootlroas
&
bep3d
Ifn pocess lnurnbeto
hasnlessi
famesthan lesspage o thatprocessuill be

iable inmimor
to neside henceimoTe
&

in out will be TequiT

Treguernt swapping €,

ithismay deads tolhrahingttenca sufleie

rdiamount toeach
offra oes must be allocated
processiinoderiton thrashing.
preventl
ueilcan
Dpog bvrl2ah
byrtexb lioit thecefet ThTashi
g

by appluingglobalpaqe meat
neplact
locallpage ment
meplace 16olio30
ea1to paqei
Global -7he paqing
Teplacement
iapplicdotoall
3Yalqoithm 1hepagso The
owhichprocess
memoT neqadless
Owns
bothemApaqe faultinoneprocess mau

Local paqtTeplacemert i
where a process
ioitsown
Can ool be allocatedpages
Teqiono memoT or itSele cts The pagcs
tothatpOCCSS. S
which onl belongs
tbee achanceto
1s_ meduce the thrashi

thrashingbased
to handle
Techoiques
:
model-Thismodelis
Wosking set pagc used necent
f
on localt.
Jocalfy isthe
Locality
and alsothe
usedagaioand agaio
Can be
also
whichare nearby thispage wll
pags.
 be thesct
[Link] Setomeans o

paqcs iothelmost reCerittimnt.

lhe paae
amoutt Timein
itsp
wbich Completed
dropped
Cuorkinqsetautomatically frorn it

Paqe
} faultfrequency uhenthroshi
ithas a few ngmbe
Th
OccuTSawe knowthdt
aofameS, Basedoo this, we assiqn
id2appr oaerboind
& foTthe destd
fautti
gatts ofccordinq
toapagefauttsate
Cwe allocate or Temovepaqs. T the page
faultratebecomes less page
tha lowerJimt
hames canbetremo VedromtheolproCeSS
SimilarluifthepagefauttTaleisornor
o than upper boundo thenhmoTe number o
Framescan benallocaedto
tbe prOCeSSiand
fno framesaTeauailabledue
To bighpaqe
fault ate,Suspendtheprocesses
&mresta
itagaiowheo frames become auailabl

6oopdoo2iisr

92
 Operating System Handout

Unit VI – File management

6.1 Files
Concepts:
• A file is a named collection of related information that is recorded on secondary
storage such as magnetic disks, magnetic tapes and optical disks.
• In general, a file is a sequence of bits, bytes, lines or records whose meaning is
defined by the files creator and user.
Attributes of a File
Following are some of the attributes of a file:
• Name . It is the only information which is in human-readable form.
• Identifier. The file is identified by a unique tag(number) within file system.
• Type. It is needed for systems that support different types of files.
• Location. Pointer to file location on device.
• Size. The current size of the file.
• Protection. This controls and assigns the power of reading, writing, executing.
• Time, date, and user identification. This is the data for protection, security,
and usage monitoring.
File Operations
The operating system must do to perform basic file operations given below.
• Creating a file: Two steps are necessary to create a file. First, space in the file
system must be found for the file. Second, an entry for the new file must be made
in the directory.
• Writing a file: To write a file, we make a system call specifying both the name
of the file and the information to be written to the file. Given the name of the
file, the system searches the directory to find the file's location. The system must
keep a write pointer to the location in the file where the next write is to take
place. The write pointer must be updated whenever a write occurs.
• Reading a file: To read from a file, we use a system call that specifies the name
of the file and where (in memory) the next block of the file should be put. Again,
the directory is searched for the associated entry, and the system needs to keep a
read pointer to the location in the file where the next read is to take place. Once
the read has taken place, the read pointer is updated.
• Repositioning within a file: The directory is searched for the appropriate entry,
and the current-file-position pointer is repositioned to a given value.
Repositioning within a file need not involve any actual I/O. This file operation
is also known as a file seek.
• Deleting a file. To delete a file, we search the directory for the named file.
Having found the associated directory entry, we release all file space, so that it
can be reused bv other files, and erase the directory entry.

Mr. [Link] Page 1 of 17

 Operating System Handout

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

executing, and so on.
• Truncating a file: The user may want to erase the contents of a file but keep its
attributes. Rather than forcing the user to delete the file and then recreate it, this
function allows all attributes to remain unchanged—except for file length—but
lets the tile be reset to length zero and its file space released.
In brief

File Types

Mr. [Link] Page 2 of 17

 Operating System Handout

File System Structure

A File Structure should be according to a required format that the operating system can
understand.
• A file has a certain defined structure according to its type.
• A text file is a sequence of characters organized into lines.
• A source file is a sequence of procedures and functions.
• An object file is a sequence of bytes organized into blocks that are
understandable by the machine.
• When operating system defines different file structures, it also contains the code
to support these file structure. Unix, MS-DOS support minimum number of file
structure.
Files can be structured in several ways in which three common structures are given in
this tutorial with their short description one by one.
File Structure 1
• Here, as you can see from the figure 1, the file is an unstructured sequence of
bytes.
• Therefore, the OS doesn't care about what is in the file, as all it sees are bytes.
File Structure 2
• Now, as you can see from the figure 2 that shows the second structure of a file,
where a file is a sequence of fixed-length records where each with some internal
structure.
• Central to the idea about a file being a sequence of records is the idea that read
operation returns a record and write operation just appends a record.
File Structure 3
• Now in the last structure of a file that you can see in the figure 3, a file basically
consists of a tree of records, not necessarily all the same length, each containing
a key field in a fixed position in the record. The tree is stored on the field, just to
allow the rapid searching for a specific key.

Fig.1 Fig.2 Fig.3

Mr. [Link] Page 3 of 17

 Operating System Handout

6.2 File Access method

File access mechanism refers to the manner in which the records of a file may be
accessed. There are several ways to access files −
• Sequential access
• Direct/Random access
• Indexed sequential access
1. Sequential Access
• 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.
• The Sequential access method is 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.
In Brief:
• Data is accessed one record right after another is an order.
• Read command cause a pointer to be moved ahead by one.
• Write command allocate space for the record and move the pointer to the new
End of File.
• Such a method is reasonable for tape.
Advantages of sequential access
• It is simple to program and easy to design.
• Sequential file is best use if storage space.
Disadvantages of sequential access
• Sequential file is time consuming process.
• It has high data redundancy.
• Random searching is not possible.

2. Direct Access
• 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 that blocks.
• Example: 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.
In brief:
• This method is useful for disks.
• The file is viewed as a numbered sequence of blocks or records.

Mr. [Link] Page 4 of 17

 Operating System Handout

• There are no restrictions on which blocks are read/written, it can be dobe in any
order.
• User now says "read n" rather than "read next".
• "n" is a number relative to the beginning of file, not relative to an absolute
physical disk location.
Advantages:
• Direct access file helps in online transaction processing system (OLTP) like
online railway reservation system.
• In direct access file, sorting of the records are not required.
• It accesses the desired records immediately.
• It updates several files quickly.
• It has better control over record allocation.
Disadvantages:
• Direct access file does not provide backup facility.
• It is expensive.
• It has less storage space as compared to sequential file.

3. Indexed Sequential Access

• The index sequential access method is a modification of the direct access
method.
• Basically, it is kind of combination of both the 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 for maintaining 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.
• It is built on top of Sequential access.
• It uses an Index to control the pointer while accessing files.
Advantages:
• In indexed sequential access file, sequential file and random file access is
possible.
• It accesses the records very fast if the index table is properly organized.
• The records can be inserted in the middle of the file.
• It provides quick access for sequential and direct processing.
• It reduces the degree of the sequential search.
Disadvantages:
• Indexed sequential access file requires unique keys and periodic reorganization.
• Indexed sequential access file takes longer time to search the index for the data
access or retrieval.

Mr. [Link] Page 5 of 17

 Operating System Handout

• It requires more storage space.

• It is expensive because it requires special software.
• It is less efficient in the use of storage space as compared to other file
organizations.

Swapping:
• Swapping is a mechanism in which a process can be swapped temporarily out of
main memory (or move) to secondary storage (disk) and make that memory
available to other processes.
• At some later time, the system swaps back the process from the secondary
storage to main memory.
• Though performance is usually affected by swapping process but it helps in
running multiple and big processes in parallel and that's the reason
• Swapping is also known as a technique for memory compaction.
• Swap space is a space on hard disk which is a substitute of physical memory.
• It is used as virtual memory which contains process memory image.
• Whenever our computer run short of physical memory it uses its virtual memory
and stores information in memory on disk.

File Space Allocation:

Files are allocated disk spaces by operating system. Operating systems deploy following
three main ways to allocate disk space to files.
• Contiguous Allocation
• Linked Allocation
• Indexed Allocation
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.

Mr. [Link] Page 6 of 17

 Operating System Handout

• 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
1. Address of starting block
2. Length of the allocated portion.
• The file ‘mail’ in the following figure starts from the block 19 with length = 6
blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.

• Each file occupies a contiguous address space on disk.

• Assigned disk address is in linear order.
• Easy to implement.
• External fragmentation is a major issue with this type of allocation technique.
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 Allocation
• In this scheme, each file is a linked list of disk blocks which need not be
contiguous.
• The disk blocks can be scattered anywhere on the disk.
• The directory entry contains a pointer to the starting and the ending file block.
• Each block contains a pointer to the next block occupied by the file.
• The file ‘jeep’ in following image shows how the blocks are randomly
distributed. The last block (25) contains -1 indicating a null pointer and does not
point to any other block.

Mr. [Link] Page 7 of 17

 Operating System Handout

• Each file carries a list of links to disk blocks.

• Directory contains link / pointer to first block of a file.
• No external fragmentation
• Effectively used in sequential access file.
• Inefficient in case of direct access file.
Advantages:
1. File size does not have to be specified.
2. No external fragmentation.
Disadvantages:
1. It does sequential access efficiently and is not for direct access
2. Each block contains a pointer, wasting space
3. Blocks scatter everywhere and a large number of disk seeks may be necessary
4. Reliability: what if a pointer is lost or damaged?
3. Indexed Allocation
• In this scheme, a special block known as the Index block contains the pointers
to all the blocks occupied by a file. Each file has its own index block.
• The ith entry in the index block contains the disk address of the ith file block.
• The directory entry contains the address of the index block as shown in the
image:

• Provides solutions to problems of contiguous and linked allocation.

• A index block is created having all pointers to files.

Mr. [Link] Page 8 of 17

 Operating System Handout

• Each file has its own index block which stores the addresses of disk space
occupied by the file.
• Directory contains the addresses of index blocks of files.
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.

6.3 Directory Structure

• A directory is a container that is used to contain folders and file.
• It organizes files and folders into a hierarchical manner.

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

Advantages:
• Since it is a single directory, so its implementation is very easy.
• If files are smaller in size, searching will faster.

Mr. [Link] Page 9 of 17

 Operating System Handout

• The operations like file creation, searching, deletion, updating are very easy in
such a directory structure.
Disadvantages:
• There may chance of name collision because two files cannot have the same
name.
• Searching will become time taking if directory will large.
• In this cannot group the same type of files together.

2. Two-level directory –
• As, a single level directory often leads to confusion of files names among
different users hence the solution to this problem is to create a separate directory
for each user.
• In the two-level directory structure, each user has their own user files directory
(UFD).
• The UFDs has similar structures, but each lists only the files of a single user.
system’s master file directory (MFD) is searches whenever a new user id=s
logged in.
• The MFD is indexed by username or account number, and each entry points to
the UFD for that user.

Advantages:
• We can give full path like /User-name/directory-name/.
• Different users can have same directory as well as file name.
• Searching of files become more easy due to path name and user-grouping.
Disadvantages:
• A user is not allowed to share files with other users.
• Still it not very scalable, two files of the same type cannot be grouped together
in the same user.
3. Tree-structured directory –
• Once we have seen a two-level directory as a tree of height 2, the natural
generalization is to extend the directory structure to a tree of arbitrary height.

• This generalization allows the user to create their own subdirectories and to
organize on their files accordingly.
• A tree structure is the most common directory structure. The tree has a root
directory, and every file in the system have a unique path.

Mr. [Link] Page 10 of 17

 Operating System Handout

Advantages:
• Very generalize, since full path name can be given.
• Very scalable, the probability of name collision is less.
• Searching becomes very easy, we can use both absolute path as well as relative.
Disadvantages:
• Every file does not fit into the hierarchical model; files may be saved into
multiple directories.
• We cannot share files.
• It is inefficient, because accessing a file may go under multiple directories.

Disk Organization:
A physical structure of disk is a memory storage device which looks like this:

• Hard disk consists of a number of platters

• The platters rotate at a very high speed (5400 RPM to 10,000 RPM)
• Disk (read/write) heads move over the platter surface to read and write
(magnetize) data bits

Mr. [Link] Page 11 of 17

 Operating System Handout

• The disk head can read or write data only when the desired disk surface area is
under the disk head.
• Read-Write(R-W) head moves over the rotating hard disk.
• It is this Read-Write head that performs all the read and write operations on the
disk and hence, position of the R-W head is a major concern.
• To perform a read or write operation on a memory location, we need to place the
R-W head over that position. Some important terms must be noted here:
1. Seek time – The time taken by the R-W head to reach the desired track from
it’s current position.
2. Rotational latency – Time taken by the sector to come under the R-W head.
3. Data transfer time – Time taken to transfer the required amount of data. It
depends upon the rotational speed.
4. Controller time – The processing time taken by the controller.
5. Average Access time – seek time + Average Rotational latency + data
transfer time + controller time.

Logical Disk Structure:

• The disk is divided into tracks.
• Each track is further divided into sectors.
• The point to be noted here is that outer tracks are bigger in size than the inner
tracks but they contain the same number of sectors and have equal storage
capacity.
• This is because the storage density is high in sectors of the inner tracks whereas
the bits are sparsely arranged in sectors of the outer tracks.
• Some space of every sector is used for formatting.
• So, the actual capacity of a sector is less than the given capacity.

Mr. [Link] Page 12 of 17

 Operating System Handout

Basically, hard disk can be divided in the logical structure in the following five logical
terms:
• MBR (Master Boot Record)
• DBR (DOS Boot Record)
• FAT (File Allocation Tables)
• Root Directory
• Data Area
1. The Master Boot Record (or MBR)
• At the beginning of the hard drive is the MBR. When your computer starts using
your hard drive, this is where it looks first.
• The MBR itself has a specific organization. The size of the MBR is 512 bytes.
• The boot loader is the first 446 bytes of the MBR. This section contains
executable code, where programs are housed.
• The partition tables are 4 slots of 16 bytes each, containing the description of a
partition (primary or extended) on the disk.
Here is how to describe a partition:
• State of the partition (inactive partition bootable) - (1 byte)
• Custom heads at the beginning of the partition - (1 byte)
• Cylinder sector and the beginning of the partition - (2 bytes)
• Type of partition (file system, eg, 32 fat, ext2 etc ...) - (1 bytes)
• Head of the end of the partition (1 byte)
• Cylinder sector and the end of the score - (2 bytes)
• Number of sectors between the MBR and the first sector of the partition - (4
bytes)
• Number of sector of the partition - (4 bytes)
• The Magic Number is two bytes used to determine if the hard disk has a
bootloader or not. If it does, the magic number should be equal in value to
hexadecimal 55AA.

2. DOS Boot Record (DBR) / DOS Boot Sector

• After the partition table, the DOS Boot Record (DBR) or sometimes called DOS
Boot Sector is the second most important information on your hard drive.
• The DOS Boot Record (DBR) for the first partition on a hard disk is usually
found at Absolute Sector 63 (the 64th sector on the disk drive) or in CHS form
we can say C–H–S = 0–1–1 for most drives.
• The sector on which DBR resides becomes logical sector 1 of that particular
partition for the DOS. The sector number used by DOS starts from the physical
sector on which DBR is located.
• First logical sector of each DOS partition will contain a DOS Boot Record (DBR)
or DOS Boot Sector. The job of the DBR is to load the operating system from

Mr. [Link] Page 13 of 17

 Operating System Handout

the hard disk drive into the main memory of computer and give the systems
control to the loaded program.

3. FAT (File Allocation Tables)

• Following DBR are the File Allocation Tables.
• The FAT has been modified several times to accommodate expanding needs.
• FAT keeps a map of the complete surface of the disk drive such that, which area
is free, which area is bad, which area is taken up by which file etc.
• When some data stored on the disk surface is to be accessed, the DOS consults
the FAT to find out the areas of the hard disk surface that contains the data.
• The FAT does not keep track of each and every sector on the disk surface instead
it manages the disk area in a group of sectors called “cluster” or “allocation unit”
(See the Cluster Discussed before, in the same chapter).
• A cluster is the smallest unit of hard disk drive space that DOS allocates to a file,
it consists of one or more sectors depending on the drive size.
• The cluster size is decided and fixed by the DOS FORMAT program during the
high level formatting of the hard disk drive. (See the “size of clusters” discussion,
given before)
• Actually, the FAT is an index of the clusters of the entire volume.
• The FAT has one entry for each cluster. The first two entries in a FAT contain
information about the FAT.
• The third and subsequent entries in the FAT are assigned to clusters of disk
space, starting with the first cluster available for use by files

4. Root Directory or Directory table

• Following the last FAT is the Root Directory.
• The root directory is like a table of contents for the information stored on the
hard disk drive.
• The location of the Root Directory can easily be established by adding up the
values from boot record, as it is positioned following the FATs.
• The directory area keeps the information about the file name, date and time of
the file creation, file attribute, file size and starting cluster of the particular file.
• Each directory entry describing this information about a file is a 32 byte
information.
• The root directory contains information about the files and directories branching
from the root directory.
• All further directories are themselves stored as files, in the same format as the
root directory.

Mr. [Link] Page 14 of 17

 Operating System Handout

• Previously the root directory used to be fixed in size and located at a fixed
position on disk but now it is free to grow as necessary as it is now treated as a
file.

5. Data Area (or Files Area)

• Following the Root Directory, the Data Area (or Files Area) starts. Rather we
can say that the remainder of the volume after Root Directory is the Data Area.
• The data area contains the actual data stored on the disk surface.
• DOS uses cluster number 2 for the first sector of the data area therefore we
should keep it in mind while performing various calculations that the cluster
number should start from 2.

Raid Structure of Disk:

• RAID, or “Redundant Arrays of Independent Disks” is a technique which makes
use of a combination of multiple disks instead of using a single disk for increased
performance, data redundancy or both.
Why data redundancy?
• Data redundancy, although taking up extra space, adds to disk reliability.
• This means, in case of disk failure, if the same data is also backed up onto another
disk, we can retrieve the data and go on with the operation.
• On the other hand, if the data is spread across just multiple disks without the
RAID technique, the loss of a single disk can affect the entire data.

Standard RAID levels

RAID 0: This configuration has striping, but no redundancy of data. It offers the best
performance, but no fault tolerance.

RAID 1: Also known as disk mirroring, this configuration consists of at least two drives
that duplicate the storage of data. There is no striping. Read performance is improved
since either disk can be read at the same time. Write performance is the same as for
single disk storage.

Mr. [Link] Page 15 of 17

 Operating System Handout

RAID 2: This configuration uses striping across disks, with some disks storing error
checking and correcting (ECC) information. It has no advantage over RAID 3 and is no
longer used.

RAID 3: This technique uses striping and dedicates one drive to storing parity
information. The embedded ECC information is used to detect errors. Data recovery is
accomplished by calculating the exclusive OR (XOR) of the information recorded on
the other drives. Since an I/O operation addresses all the drives at the same time, RAID
3 cannot overlap I/O. For this reason, RAID 3 is best for single-user systems with long
record applications.

RAID 4: This level uses large stripes, which means you can read records from any
single drive. This allows you to use overlapped I/O for read operations. Since all write
operations have to update the parity drive, no I/O overlapping is possible. RAID 4 offers
no advantage over RAID 5.
Mr. [Link] Page 16 of 17
 Operating System Handout

RAID 5: This level is based on block-level striping with parity. The parity information
is striped across each drive, allowing the array to function even if one drive were to fail.
The array's architecture allows read and write operations to span multiple drives. This
results in performance that is usually better than that of a single drive, but not as high
as that of a RAID 0 array. RAID 5 requires at least three disks, but it is often
recommended to use at least five disks for performance reasons.

RAID 6: This technique is similar to RAID 5, but includes a second parity scheme that
is distributed across the drives in the array. The use of additional parity allows the array
to continue to function even if two disks fail simultaneously. However, this extra
protection comes at a cost. RAID 6 arrays have a higher cost per gigabyte (GB) and
often have slower write performance than RAID 5 arrays.

Mr. [Link] Page 17 of 17