Os All Merged

INTRODUCTION
INTRODUCTION
TO TO
O P E R ATOI PNEGR AS TYISNTGE SMY SS T E M S
MODULE - I
Dr. A.Padmavathi
Assistant Professor(SG)
MODULE - I
Department of Computer Science and Engineering
Amrita School of Engineering, Chennai
LECTURE - 1
Introduction to Operating Systems
Introduction to Operating Systems 2

WHAT IS AN OPERATING SYSTEM
(OS)?
q A program that acts as an intermediary between a user of a computer and
the computer hardware.
q In simple words, OS is an interface between user and hardware (CPU, I/O,
RAM).
q OS is a program (software) that manages the computer hardware.
q It includes all programs that are associated with the operation of the system
(computer).
q OS resides in hard disc, but on system booting, it is copied to RAM.

COMPUTER SYSTEM COMPONENTS
1. Hardware – basic computing resources (CPU, memory, I/O devices).
2. Operating system – controls and coordinates the use of the hardware among various
application programs for different users.
3. Applications programs – define the ways in which system resources are used to solve
the computing problems of the users
4. Users (people, machines, other computers).
U1, U2….Un are users
Introduction to Operating Systems

Abstract view of the components of a computer system 5
VARIOUS OPERATING SYSTEMS
and many more……..

QUICK QUESTION
q Why there is a need of an operating system?
ØIf there is no operating system, then the user need to write separate
program to access each of the hardware.
ØEg. In order to print a document, the user need to write a program to

invoke the printer and do the printing.

OPERATING SYSTEM GOALS
q Make the computer system convenient to use.

qCONVINIENCE (Windows OS acquired 95% market)
q Execute user programs and make solving user problems easier.

– EFFICIENCY/THROUGHPUT (Linux)
– Throughput is number of tasks executed per unit time

PARTS OF OPERATING SYSTEM
q Kernel (heart of OS)

q Device drivers (to communicate with system hardware)
q User interface (allows a user to enter and receive information)
q System libraries (An organized collection of computer programs that is
maintained on-line with a computer system by being held on a secondary
storage device)
q System utilities ( manage, maintain and control computer resources)

QUICK QUESTIONS
q Are application programs eg. Excel, chrome etc. are part of OS?
qNo
qOS (Kernel) is helping in running these processes
qIf any process wants to communicate with any hardware devices, it uses system calls.
q Why do we need an interface (OS)? Why not the user directly

communicate with the hardware?
qMany problems such as memory access, resource conflict etc. will happen

KERNEL
q Kernel is the heart of OS

q Portion of the OS code that is always resident in the main memory (RAM)
q Functions of Kernel
– Process management
– Memory management
– File system management
– Protection & security
– Device management
– Inter process communication etc.

OS & KERNEL
q Windows OS – Windows NT is the Kernel (more than 75% market share)
q Mac OS – XNU is the Kernel (around 19% market share)
q Ubuntu OS – Red hat is the Kernel (Linux 1.6% market share for desktop
computers)
– In server class machines, Linux is used and more than 70% market share is acquired by
Linux
– In smart watches, smart phones, cars, smart TV etc. Linux Kernel is used.

QUICK QUESTION
q Can we have an OS without Kernel?

– No
q Can we have Kernel without an OS?

– Yes

FUNCTIONS OF OPERATING
SYSTEMS
– Resource management
– Process management
– Storage management
– Memory management
– File system management
– Protection & security
– Inter process communication etc.
q In other words, functions of Kernel + CLI(command line interface) and GUI (graphical user
interface) for user interaction with the system
q OS provides system utilities and system libraries

LECTURE - 2
Types of Operating Systems

TYPES OF OPERATING SYSTEMS
Batch Multiprocessor Desktop Distributed Clustered Real-time Handheld

systems systems systems systems systems systems systems

1. BATCH SYSTEMS
• There is no direct interaction between user and the computer.
• User submits his jobs to the computer operator
• The operator submits a batch of jobs to an input device of the computer
• Based on the requirements and the language, jobs are batched
• The special program called monitor manages all the jobs in a batch
• Eg. of batch based OS– Payroll systems, Bank statements etc.

2. MULTI PROGRAMMING SYSTEMS
Ø OS picks up and begins to execute one of the jobs
from memory.
Ø Once this job needs an I/O operation, operating system
switches to another job.
Ø If several jobs are ready to run at the same time, CPU
scheduling is to be done.
• In non-multiprogrammed systems, there are moments
when CPU is idle.
• In multiprogramming system, CPU will never be idle
and keeps on processing.
Ø Primarily to optimize utilization of hardware.
Ø Reduce setup time by batching similar jobs. Simple batch Multi programmed
system batch system
Ø Automatic job sequencing.
Ø Resident monitor.
3. MULTIPROCESSOR SYSTEMS
• Consists of several processors that share a common physical memory.

• Provides higher computing power and speed.
• In multiprocessor system all processors operate under single operating
system.
• I/O routine supplied by the system
• Memory management
• CPU scheduling
• Allocation of devices
• Eg. Windows NT, 2000, XP, and Unix,OpenBSD

4. DESKTOP SYSTEMS
• Personal computers – computer system dedicated to a single user.

• PC operating systems therefore were neither multiuser nor multitasking.
• Instead of maximizing CPU and peripheral utilization, maximizing user
convenience and responsiveness is opted
• These systems are called desktop systems. Eg. PCs running with Windows and
Apple Macintosh.
• Eg. Windows, Apple's mac OS, Chrome OS, BlackBerry Tablet OS,

5. DISTRIBUTED OPERATING
SYSTEMS
• Distribute the computation among several physical processors.
• Advantages of distributed systems
– Resources Sharing
– Powerful and inexpensive microprocessors
– Computation speed up – load sharing
– Reliability
– Advanced Communications
Eg. LOCUS, MICROS, IRIX etc.

TYPES OF DISTRIBUTED
OPERATING SYSTEMS
1. Client-server systems 2. Peer-to-peer systems
Centralized systems today act as server In contrast to tightly coupled systems,
systems to satisfy requests of client systems. it uses a set of processors that do not
share a memory or clock.
Each process has its own local memory
They are loosely coupled systems

6. CLUSTERED SYSTEMS
• Like parallel systems, clustered systems gather together multiple CPUs to

accomplish computational work.
• Clustering allows two or more systems to share storage.
• Provides high reliability and availability.
• Asymmetric clustering: all nodes runs the application while other one node is
in standby.
• Symmetric clustering: all N hosts are running the application.
• Eg. Solaris MC, UnixWare, MOSIX and GLUnix

7. REAL-TIME SYSTEMS
• It is an OS that give maximum time for each of the critical operations that it
performs, like OS calls and interrupt handling.
• Often used as a control device in a dedicated application.
• Well-defined fixed-time constraints.
• Real-Time systems may be either hard or soft real-time.
– Hard real time systems: The RTOS which guarantees the maximum time for critical
operations and complete them on time
– Soft real time systems: RTOS that guarantees maximum of the time, to critical task by
assigning priority over other tasks, but no assurity of completing it in a defined time.
Eg. FreeRTOS, VxWOrks, QNX etc.

7. HANDHELD SYSTEMS
• Personal Digital Assistants (PDAs)

• Cellular telephones
• Issues:
– Limited memory
– Slow processors
– Small display screens
Eg. Palm OS, Pocket PC, Symbian OS, Android, Linux etc.

Lecture – 3
Understand the Operations of

Computer System
Introduction – Basics of Computer System
Ø Knowledge of computer system operation is required to understand how OS works.
Ø For a computer to start operating:
Ø The initial program that runs when a computer is powered up or rebooted - bootstrap program (BP)
Ø It initializes all aspects of the system and is stored in ROM
Ø BP loads the OS and prepares how to start executing that system. An ISR is a software
Ø BP locate the operating-system kernel and load it into memory. process invoked by an
Ø Once kernel is loaded & executing, it provides services to system & its users. interrupt request from a
Ø Some services are provided outside of the kernel during boot time – system processes, or system daemons. hardware device.
Ø Once this phase is complete, the system is fully booted, and the system waits for some event to occur.
Ø The occurrence of an event is signaled by an interrupt from either the hardware or the software
Ø Hardware trigger an interrupt at any time by sending a signal to the CPU, through system bus.
Ø Software trigger an interrupt by executing a special operation called a system call
Ø When CPU is interrupted, it stops what it is doing and immediately transfers execution to a fixed location.
Ø The interrupt service routine (ISR) executes; on completion, the CPU resumes the interrupted computation.
ISR
OPERATIONS OF OPERATING SYSTEMS 3

Introduction – Basics of Computer System
ØA modern general-purpose computer system consists of one or more CPUs and a number of device
controllers connected through a common bus that provides access to shared memory
ØCPU – brain of the computer system. It is the processing unit, doing all
computations.
Ø Controllers - are responsible for how the connected devices work.

Ø Bus – The CPU and the controllers are connected to the memory using a
common bus.
Ø CPU and controllers can execute concurrently and compete for memory
Ø A memory controller synchronize access to the memory. (memory is finite)
Ø All the connected devices to execute need to be loaded to the main

memory
Source: OS concepts by A Silberschatz

Introduction – Computer System Architecture
Ø A computer can be organized in different ways, based on the number of processors used.
Single processor system Multiprocessor system
The system contains only one processor The system contains two or more processors
Single processor uses multiple controllers (co-processors) to In multiprocessors two approaches are used:
handle special tasks & can execute limited instruction sets a. Symmetric multiprocessing (SMP)
b. Asymmetric multiprocessing (AMP)
Cost is more because each processor requires separate Cost is less because they uses same resources on sharing
resources. i.e. Mass Storage, Peripherals, Power Supplies basis.
etc.
Less reliable because failure in one processor will result in More reliable
failure of entire system. A computer’s capability to
process more than one
Throughput is low (each and every task is performed by the Throughput is high. ( For N Processors - throughput will be task simultaneously is
same processor) slightly less than N because synchronization must be
maintained between two processors and they also share
called multiprocessing
resources which add certain overhead)
Easy to design Complex design
Eg. Most of modern PCs Eg. Blade servers

Multiprocessor system Multicore systems

A system with two or more CPUs that allow simultaneous A single CPU(processor) with two or more
processing of programs. independent processing units are called core. Cores
execute instructions.
Multiple chips with single core Multiple computing cores on a single chip.
This is called Simultaneous Multiprocessing (SMP). This is called Chip-level Multiprocessing (CMP).
Expensive They are cheaper as only single CPU
More traffic On chip communication is faster
Fast running of multiple programs Fast running of single program
More reliable as failure in one CPU will not affect the other Not as reliable
Multicore systems

Lecture – 3
Understand the Operations of

Operating Systems
Ø In multiprocessors two approaches are used:
Asymmetric multiprocessing Symmetric multiprocessing
Use of two or more processors handled by one Use of two or more processors sharing a common
master processor. memory space.
There is one master processor that controls the Processors shares the same memory
data structure of the system.
Only the master processor run task in OS. All the processor in the system run tasks in OS
Processors need not communicate as they are All processors communicate with another processor
controlled by the master processor. via a shared memory.
Simple as master processor access the data Complex as all the processors need to be
structure. synchronized to maintain the load balance.
Master-slave approach Peer-to-peer approach

ØIn multiprocessing systems, memory access model can be two ways:
Uniform memory access (UMA) Non Uniform memory access (NUMA)
UMA has single memory controller. NUMA has multiple memory controllers.
UMA memory access is slow. NUMA memory access is faster than
UMA memory.
UMA has equal memory access time. NUMA has varying memory access time.
UMA has limited bandwidth. NUMA has more bandwidth than UMA.
UMA is used in general purpose and NUMA is used in real time and time
time sharing applications. critical applications.

Operating System Operations
Ø Modern OS are interrupt driven
Ø Events are signaled by occurrence of an interrupt or trap
Ø A trap is a software generated interrupt

Ø A trap is generated when there is an error or a request from user program to run an OS service.
Ø To ensure the proper execution of OS, need to distinguish between the execution of OS code & user
defined code.
Ø The approach taken - provide hardware support to differentiate among various modes of execution.
Ø Two separate modes (Dual mode) of operation
Ø User mode
Ø Kernel mode (supervisor/system/privileged mode)

Dual Mode Operation –
User mode and Kernel mode
Ø We are users of computer and we use one or the other
applications of the computer (through API). Then, we are in USER
mode.
Ø But, all the OS core functionalities and drivers function only in
KERNEL mode.
Ø And the processor switches between USER and KERNEL mode.
Ø At system boot time, the hardware starts in kernel mode.
Ø User cannot access the hardware directly. Does it through
system calls.
Ø System call – it is a way in which a computer program requests a
service from the Kernel of an OS.
Ø When get system call is activated – read() system call is invoked
(mode bit=1) and the system moves to KERNEL mode (mode
bit=0). This happens via interrupt (trap).
ØReal world eg. Bank transaction

Multimode Operation
Ø The concept of modes of operation in OS can be extended beyond the dual mode. This is known
as multimode system.
Ø Here, more than one bit is used by the CPU to set and handle the mode.
Ø Eg. of multimode systems can be understood from systems that support virtualization.
These, CPUs have a separate mode that specifies when the virtual machine manager (VMM) and
the virtualization management software—is in control of the system.
Ø In this mode, the VMM has more privileges than user processes but fewer than the kernel.

Privileged Instructions
Ø What are privileged instructions?
Ø The instructions that can run only in KERNEL mode are called privileged instructions.
Ø Characteristics:
Ø If any attempt is made to execute a privileged instruction in USER mode, it will not be executed. The
hardware traps it to the OS.
Ø Before transferring the control to any user program, it is the responsibility of the OS to ensure that the
TIMER is set to interrupt.
ØThus, if the timer interrupts, then the OS regains the control.
What is non-
Ø So, any instruction that can modify the contents of the TIMER is a privileged instruction.
privileged
Ø Privilege instructions are used by OS in order to achieve correct operation. instruction?
Ø Eg. of privileged instructions: IO instructions, context switching, disabling the interrupt, set the time of
clock

Lecture - 5
System Call
System Call
Ø System call – it is a way in which a computer program requests a service from the Kernel of an OS.
Ø System call provide an interface to the services made available to an OS.
Ø In order to understand more about the system calls, we need to understand the
Two modes of operation in which a program can operate:
Ø User mode
Ø Kernel mode
Modes of Operation of a Program
Ø User mode and Kernel mode are the two modes in which a program can execute
Ø If a program is running in user mode, the program do not have direct access to memory, hardware and such
resources.
Ø But, if a program is running in Kernel mode it has access to hardware, memory etc.
Ø So, if a program is running in a Kernel mode, we say that it is in privileged mode
Ø But, is a program is running in Kernel mode and the program gets crashed, then the entire system will
crash, or the system would halt, that is a problem of a Kernel mode.
User Mode
Ø If the program is running in user mode and if it crashes, then the entire system would not crash
Kernel
Ø User mode – SAFER MODE of operation, though Kernel mode – PRVILEGED MODE of operation
Model
System call
Ø when a program, is executing in system mode, it may need access to some of the resources like:
memory, hardware etc, then:
Ø The program makes a call to the OS informing that it need some resources
Ø When the call is made, the program switches from user mode to kernel mode so that it can use those
resources
Ø So, when a program switched from user mode to kernel mode and vice versa it is called as context
switching
Ø So the call which was made to the kernel to access the system resources is known as system call
System call is the programmatic way in which a computer program requests a service from the kernel of the
OS. These calls are available as routines written in C or C++
System call
ØUser operates in USER mode and if user wants any functionality of the OS, it needs to be in KERNEL mode.
Ø To switch from USER mode to KERNEL mode to access the functionalities of OS, system call is used.
Ø Eg, a C program to add two numbers (USER mode) and print the result in monitor (KERNEL mode).
Ø printf is a function, which uses the system call write() to print the value
Ø Wondows 7 has around 700 system calls and some other OS have 300 etc.
An Example to Understand…
Ø Example of a SYSTEM CALL sequence for writing a simple program to read data from one file and copy them to another file.
Ø The required set of system calls for read data from the file:
Ø Acquire input file name – we need a system call to acquire the file name
Ø Write to screen – a system call to display in the screen (for using the output device)
Ø Accept input – a system call to use keyboard or mouse (for using input devices)
Ø The required set of system call for write data to the file:
Ø Acquire output file name
Ø Write to screen - a system call to display in the screen (for using the output device)
Ø Accept input - a system call to use keyboard or mouse (for using input devices)
Ø Open input file
Ø If file doesn’t exist – ABORT
Ø Create file name
Ø If file doesn’t exist – ABORT
Ø Read from input file
Ø Write to output file ( it a loop until read fails)
Ø Close output file
Ø Write completion message on the screen
Ø Terminate normally
Types of System Calls
Ø System calls are grouped into 6 major categorize.
1. Process Control
2. File manipulation
3. Device manipulation
4. Information maintenance
5. Communications
6. Protection
1. Process Control
Ø The system calls that are used to control the processes.
Ø There are various processes running in a system and that needs to be controlled. Some of
the examples are:
Ø end, abort ( a process when is running, on completion needs to end normally or abnormally)
Ø load, execute
Ø create, terminate
Ø get process attributes, set process attributes
Ø wait for time
Ø wait event, signal event
Ø allocate and free memory
2. File Manipulation
Ø These are the system calls that are used to manipulate or manage files.
Ø create file, delete file
Ø open, close file
Ø get file attributes, set file attributes
Ø read, write, reposition

3. Device Manipulation
Ø For managing and manipulation the devices: input, output devices etc.
Ø request device, release device
Ø read, write, reposition
Ø get and set device attributes
Ø logically attach or detaching devices

4. Information Maintenance
Ø All the information about the system must be maintained and updated.
Ø Eg. date and time

Ø get time or date, set time or date
Ø get system data, set system data
Ø get process, file, or device attributes
Ø set process, file or device attributes

5. Communication
Ø The system calls that are used for communication between processes and devices.
Ø create, delete communication connection
Ø send, receive messages
Ø transfer status information
Ø attach or detach remote devices

6. Protection
Ø Protection provides a mechanism for controlling access to the resources provided by a
computer system.
Ø Protection is a concern with of all computer systems from servers to mobile handheld
devices
Ø set permission, get permission
Ø allow user, deny user

Lecture – 5
Operating Systems Structure
OPERATING SYSTEM STRUCTURE 2

DIFFERENT STRUCTURES OF OPERATING SYSTEMS –
I. SIMPLE STRUCTURE
¡ The large and complex modern operating system must be engineered carefully to function properly and
be modified easily.
¡ A common approach is to partition the task into small modules.
¡ Each of these modules should be a well-defined portion of the system, with carefully defined inputs, outputs, and
functions.
Simple Structure
q The structure followed in designing olden OS - MS-DOS operating systems
q They do not have a very well defined structure
q ROM BIOS (Basic Input/Output System)device drivers – to perform hardware initialization during the booting process
q Device drivers, System program and Application program can also access system hardware
q Thus, in this structure interfaces and levels of functionalities are not well separated
q Even though it looks like a layered structure it is not actually a layered structure
q Such freedom makes MS-DOS vulnerable to errors or malicious programs, causing the entire system to crash when the user program fails.
q So, it is not well protected, well structed and not well defined. MS-DOS layer structure
q Eg. MS DOS,
II. UNIX STRUCTURE (MONOLITHIC STRUCTURE)
¡ It was a limited structure, limited by the hardware functionality

¡ It consist of two separate parts: the kernel and system programs
¡ Everything below the system-call interface and above the physical hardware is the kernel.
¡ The kernel provides file system, CPU scheduling, memory management, & other OS functions through system
calls
¡ Resulting an enormous amount of functionality to be combined into one level
¡ Monolithic structure was difficult to implement and maintain.
¡ Eg. UNIX, Linux, and Windows operating systems.

III. LAYERED STRUCTURE
¡ Here, the operating system is divided into a number of layers

¡ At the lower most layer or at Layer 0 we have the hardware, then we have layer 1, 2…n (user interface)
¡ Here, we have broken down the functionalities into different layers and are separated
¡ The main advantage is it is easy to implement and debug, because every layer has different functionalities
¡ If one layer have a problem, then we need to debug only that layer instead of debugging the entire system
¡ Hardware is protected from the layers above
¡ But there are some disadvantages also:
¡ We need to be specific in deciding the layers which are above and below a specific layer.
¡ Because a layer can use the functionalities of layers which are only below it
¡ This structure is not very efficient when compared to other structures: response is late
¡ Eg. Microsoft Windows NT
OPERATING SYSTEM STRUCTURE
5
IV. MICRO KERNELS
¡ In the mid-1980s, researchers at Carnegie Mellon University developed an OS called Mach that modularized the kernel using the
microkernel approach.
¡ Removed all nonessential components from the kernel and implemented them as system and user-level programs. The result is a
smaller kernel.
¡ Microkernels provide minimal process and memory management, in addition to a communication facility
¡ The main function is to provide communication between the client program and the various services running in user space.
Communication is provided through message passing,
¡ Advantages
¡ All new services are added to the user space (user mode), so modification of kernel is not required
¡ Operating system is easier to port from one hardware design to another
¡ Microkernel also provides more security and reliability, since most services are running as user programs.
¡ Disadvantages
¡ Micro kernels can suffer from performance decrease due to increased system function overhead (due to message passing)
¡ Eg. Tru64 UNIX is implemented with a Mach kernel. The Mac OS X kernel (Darwin) is also partly based on the Mach micro kernel.
¡ Eg. QNX, a RTOS has QNX Neutrino microkernel
V. MODULES
¡ Follow a modular approach in structuring the OS
¡ Best current methodology for OS design which involves OOP techniques to create a modular kernel
¡ It has a core kernel, which has only the core functionalities of a kernel and other functionalities are available as modules
which will be loaded to the kernel either during booting time or run time
¡ It ensures that other functionalities will be loaded to the kernel dynamically as and when required.
¡ It looks something like a layered approach and micro kernel approach
¡ Resemblance to layered structure – each kernel section has defined protected interfaces ensuring the non availability to all
not wanted interfaces accessing it. But, more flexible than a layered system that any module can call any other module
¡ Resemblance to micro kernel approach – micro kernel has only main functionalities and all other functionalities are
provided as system programs. But, advantage is in micro kernel we need to have message passing to communicate
between the modules, but here they are loaded dynamically into the core kernel as when needed. No need of message
passing.
¡ Eg. Solaris, Linux, and Mac OS X, as well as Windows

VI. HYBRID STRUCTURE
¡ In practice, very few OS adopt a single, strictly defined structure.
¡ Instead, they combine different structures, resulting in hybrid systems that address performance, security,
and usability issues.
¡ Eg. both Linux and Solaris are monolithic, however, they are also modular, so that new functionality can be
dynamically added to the kernel
¡ Windows is largely monolithic, but it retains some behavior typical of microkernel systems
¡ The Apple Mac OS X uses a hybrid structure. It is a layered system and below these layers is the kernel
environment, consists primarily of the Mach microkernel and the BSD UNIX kernel.
¡ iOS is a mobile operating system designed by Apple. OS is structured on the Mac OS X, with added
functionality pertinent to mobile devices, but does not directly run Mac OS X applications.
¡ iOS is designed to run on Apple mobile devices and is close-sourced, Android runs on a variety of mobile
platforms and is open-sourced,
¡ Android has layered stack of software and at the bottom Linux kernel. 8
OPERATING SYSTEM STRUCTURE
Lecture – 7
Overview of Protection and

Security of Operating System
3
Introduction
Ø Interferences in resource utilization is a very serious threat in an OS

Ø If a computer system has multiple users and allows the concurrent execution of
multiple processes, then access to data must be regulated.
Ø OS uses two sets of techniques to address threats:
Ø Protection
Ø Security
Protection and security of Operating Systems

4
Protection
Ø Any mechanism for controlling the access of processes or users to the

resources defined by a computer system is called as Protection.
Ø Protection - ensure that only processes that have gained proper authorization
from the OS can operate on memory segments, the CPU, and other resources.
Ø It involves guarding a user’s data and program against interference by other
authorized users of the system.
Ø Furthermore, an unprotected resource cannot defend against use (or misuse)
by an unauthorized user.
Ø A protection-oriented system provides a means to distinguish between
authorized and unauthorized usage.
5
Security
Ø A system can have adequate protection but still be prone to failure and allow
inappropriate access.
Ø It is the job of security to defend a system from external and internal attacks.
Ø Security ensures the authentication of system users to protect the integrity of the
information stored in the system as well as the physical resources of the computer system.
Ø It involves guarding of user’s data and programs against interferences by external entities
(unauthorized persons)
Ø The security system prevents unauthorized access, malicious destruction or alteration of
data, and accidental introduction of inconsistency.

7
Goal of Protection
Ø Modern protection concepts have evolved to increase the reliability of any complex system that
makes use of shared resources.
Ø Protection is provided for various reasons:
Ø To prevent the mischievous, intentional violation of an access restriction by a user
Ø To ensure each program components to use system resources only in ways consistent with stated
policies.
Ø Protection can improve reliability by detecting latent errors
Ø An unprotected resource cannot defend against use (or misuse) by an unauthorized or incompetent
user.
Ø A protection-oriented system provides means to distinguish between authorized and unauthorized
usage

8
Principles of Protection
Ø PRINCIPLE OF LEAST PRIVILEGE

Ø It dictates that programs, users, and even systems be given just enough privileges to perform
their tasks.
Ø An OS following the principle of least privilege implements its features, programs, system calls,
and data structures so that failure or compromise of a component does the minimum damage.
Ø Computers implemented in a computing facility under the principle of least privilege can be
limited to running specific services, accessing specific remote hosts via specific services, and
doing so during specific times.
Ø The principle of least privilege can help produce a more secure computing environment.
Ø Solaris, a UNIX based OS is relatively more secure than Windows 2000

9
Domain of Protection
Ø A computer system is a collection of processes and objects.

Ø Objects - both hardware objects and software objects.
Ø Each object has a unique name that differentiates it from all other objects in the system, and
each can be accessed only through well-defined and meaningful operations.
Ø Objects are essentially abstract data types.
Ø The operations that are possible may depend on the object.
Ø For example, on a CPU, we can only execute, memory segments can be read and written,
whereas a CD-ROM/DVD-ROM can only be read.

10
Domain of Protection contd….
Ø A process should be allowed to access only those resources for which it has authorization.
Ø Furthermore, at any time, a process should be able to access only those resources that it
currently requires to complete its task - referred to as the need-to-know principle, is useful
in limiting the amount of damage a faulty process can cause in the system.
Ø A process operates with in a protection domain - the resources that the process may access
Ø The ability to execute an operation on an object is an access right. A domain is a collection of
access right.
Ø The association between a process and a domain may be either static, if the set of resources
available to the process is fixed throughout the process’s lifetime, or dynamic.
Ø If the association is dynamic, a mechanism is available to allow domain switching, enabling the
process to switch from one domain to another.
11
Aspect of protection of information
Ø There are two aspects of protection of information:

Ø Secrecy – Only authorized users should be able to access information
Ø Privacy – information should be used only for the purposes for which it is intended and shared.
Ø OS focuses on guaranteeing secrecy of information and leaves the issue of privacy to users and
their processes.
Security Policy Specify whether a person can become a user of the system. Performed by
system admin.
Mechanism • Add or delete user
• Verify whether a person is an authorized user
Protection Policy Specify whether a user can access a specific file. Performed by owner of the
file.
Mechanism • Set or change protection information of a file
• Check whether a file can be access by a user.
12
Protection - Summary
Computer systems contain many objects, and they need to be protected from
misuse. Objects may be hardware or software. An access right is permission to
perform an operation on an object. A domain is a set of access rights. Processes
execute in domains and may use any of the access rights in the domain to access
and manipulate objects. During its lifetime, a process may be either bound to a
protection domain or allowed to switch from one domain to another.

14
Security
Ø A system is secure if its resources are used and accessed as intended under all
circumstances.
Ø Unfortunately, total security cannot be achieved.
Ø Security violations (or misuse) of the system can be categorized as intentional
(malicious) or accidental.
Ø It is easier to protect against accidental misuse than against malicious misuse.
Ø Intruder and cracker for those attempting to breach security.
Ø A threat is the potential for a security violation, such as the discovery of a
vulnerability, whereas an attack is the attempt to break security.
15
Security Breaches
Ø Breach of confidentiality – This type of violation involves unauthorized reading of data (or theft of
information).
Ø Eg. credit-card information or identity information for identity theft, can result directly in money for the intruder.
Ø Breach of integrity – This violation involves unauthorized modification of data.

Ø Result in passing of liability to an innocent party or modification of the source code of an important commercial
application.
Ø Breach of availability – This violation involves unauthorized destruction of data.
Ø Website defacement is a common example of this type of security breach.
Ø Theft of service – This violation involves unauthorized use of resources.

Ø An intruder (or intrusion program) may install a daemon on a system that acts as a file server.
Ø Denial of service (DOS) – This violation involves preventing legitimate use of the system. DOS attacks are
sometimes accidental.
Ø For example, a website click could download a Java applet that proceeds to use all available CPU time or to pop up
windows infinitely. The second category involves disrupting the network.
16
Reasons for taking security measures
Ø To prevent loss of data

Ø To prevent corruption of data
Ø To prevent compromise of data
Ø To prevent theft of data
Ø To prevent sabotage

17
Methods adopted to breach security
Ø Masquerading – One participant in a communication pretends to

be someone else. By masquerading, attackers breach authentication,
the correctness of identification; they can then gain access that they
would not normally be allowed or escalate their privileges.
Ø Replay attack - Consists of the malicious or fraudulent repeat of a
valid data transmission. Eg. in a repeat of a request to transfer money.
Ø Man-in-the-middle attack - An attacker sits in the data flow of a
communication, masquerading as the sender to the receiver, and vice
versa. In a network communication, a man-in-the-middle attack may
be preceded by a session hijacking, in which an active
communication session is intercepted.
Absolute protection of the system from malicious abuse is not possible

18
Security Measures
To protect a system, we must take security measures at four levels:

1. Physical
Ø The sites containing the computer systems must be physically secured against armed or surreptitious entry by intruders.
The machine rooms and workstations that have access to the machines must be secured.
2. Human
Ø Authorization must be done carefully to assure that only appropriate users have access to the system. Eg. Phishing,
dumpster diving
3. Operating System
Ø The system must protect itself from accidental or purposeful security breaches. A runaway process could constitute an
accidental DOS attack. A query to a service could reveal passwords. A stack overflow could initiate an unauthorized process.
The list of possible breaches is almost endless.
4. Network
Ø Much computer data in modern systems travels over private leased lines, shared lines like the Internet, wireless
connections, or dial-up lines. Intercepting these data could be just as harmful as breaking into a computer, and interruption
of communications could constitute a remote DOS attack, etc.
19
Security - Summary
Protection is an internal problem. Security, in contrast, must consider both

the computer system and the environment—people, buildings, businesses,
valuable objects, and threats—within which the system is used. Methods of
preventing or detecting security incidents include intrusion detection
systems, antivirus software, auditing and logging of system events,
monitoring of system software changes, system-call monitoring, and firewalls.

20
Comparison between Protection & Security
Parameters Protection Security
Basic Control the access to the system Provides the system access to legitimate
resources users only
Handles Simple queries More complex concerns
Policy Specifies what file can be access by Describes which person is allowed to use
a particular user the system
Type of threat Internal External
Mechanism Set or alter the authorization Authentication and encryption are

information performed
Lecture – 8
Operating System Services
Operating System Services 2

1. User Interface
◦ An operating system provides an environment for the execution of programs.
◦ It provides certain services to programs and to the users of those programs.
1. User Interface
◦ User interface allows a user to interact with the OS or interact with the computer.
◦ All OSs have a user interface and this can take several forms; such as CLI and GUI
◦ Eg. of CLI: the command prompt we have in Windows or terminal in Uduntu systems.
◦ CLI – we can provide text-based command through keyboard in order to perform certain tasks.
◦ Most commonly used user interface is GUI: it is an interface where we have a Windows system with pointing
device like mouse and there are menus through which you can provide input and also using keyboard.
◦ Most user friendly interface is GUI
◦ Thus, user interface is one of the most important services provided by an operating system.
3
2. Program Execution
◦ OS must provide environment for execution of the programs.
◦ A user must be able to run the programs or softwares that you have.
◦ For this, the system must load the program inti the memory and it should be able to run
that program.
◦ The program must be able to end its execution, either normally or abnormally (indicating
error).
Source Comp Object Execu

code iler code tor
Output
3. Input / Output Operations
◦ A running program may require I/O, which may involve a file or an I/O device.
◦ For efficiency and protection, users usually cannot control I/O devices directly.
◦ For eg. When you use keyboard or mouse, you may feel that you are using it directly, but it
is not so; there is the OS which is between you and the computer which actually controls
the usage of the IO devices.
◦ Therefore, the operating system must provide a means to do I/O.

4. File System Manipulation
◦ The file system management involves files.

◦ There are many files and directories in your system that are to be used.
◦ The programs need to read and write files and directories, create and delete them search
for a given file, and list file information etc..
◦ OS must control how these files are to be managed.
◦ OS must include permissions to allow or deny access to files or directories based on file
ownership.

5. Communication
◦ Communication between processes.
◦ There are many circumstances in which one process needs to exchange information with
another process.
◦ Such communication may occur between processes that are executing on the same
computer or between processes that are executing on different computer systems tied
together by a computer network.
◦ Communications may be implemented via shared memory, in which two or more processors
read or write to a shared section of memory, or message passing, in which packets of
information in predefined formats are moved between processes by the operating system.

6. Error detection
◦ Errors can always occur during the course of computing.
◦ The OS needs to be detecting and correcting errors constantly.
◦ Errors may occur in the CPU and memory hardware, I/O devices, a connection failure on a
network, or lack of paper in the printer and in the user program (such as an arithmetic
overflow etc. )
◦ For each type of error, the OS should take appropriate action to ensure correct and consistent
computing.
◦ Sometimes, it has no choice but to halt the system. At other times, it might terminate an error-
causing process or return an error code.
◦ When error occurs, the entire system should not break down or seize the computing
completely; instead the OS should manage these errors so that the computations are consistent
and is still carried out.

Another set of operating system functions exists not for
helping the user but rather for ensuring the efficient
operation of the system itself.

7. Resource Allocation
◦ Allocating resources to different processes or different users.

◦ Resources can be of different types: the CPU, files, I/O devices etc. and there are different
processes running in the system.
◦ All these processes require some of these resources at some point in time.
◦ OS must help in resource allocation by allocating different resources to different
processes which are requesting for it.
◦ OS should do this in an efficient way such that all the processes gets all the resources
which they need and no process should be waiting for a resource, which it never gets it.
◦ we should not end in a process is waiting for a resource indefinitely and a process is
holding a resource, which it never release it.

8. Accounting
◦ We want to keep track of which users use how much and what kinds of computer
resources.
◦ This record keeping may be used for accounting (so that users can be billed) or
simply for accumulating usage statistics.
◦ Usage statistics may be a valuable tool for researchers who wish to reconfigure
the system to improve computing services.

9. Protection & Security
◦ Our data should be secured and everything that we do must be protected.

◦ When many processes are executing at the same time, one process should not interfere with the
execution of another process or even with the OS execution.
◦ Protection means access to different computer resources must be controlled.

◦ Security is talked about wrto. to outside access.
◦ We should ensure that the system is not accessible from outsiders who are not authorized to use the
computer.
◦ In order to protect the computer it should be protected from all the angles possible.
◦ As the saying goes: a chain is as strong as its weakest link.


Lecture – 9
Introduction to Processes
Introduction to Processes 2
Introduction
• A process is a program in execution.
• A process will need certain resources: CPU time, memory, files, and I/O devices to accomplish its
task.
• These resources are allocated to the process either when it is created or while it is executing.
• Systems consist of a collection of processes: operating-system processes execute system code, and user
processes execute user code. All these processes may execute concurrently.
• Traditionally a process contained only a single thread but, most modern OS support processes that have
multiple threads.
• The OS is responsible for several important aspects of process and thread management:
• creation and deletion of both user and system processes
• scheduling of processes
• provision of mechanisms for synchronization, communication, and deadlock handling for processes.
How a program is developed
• Write the program using a high level language: C, C++, Java etc.
• But, computer does not understand high level language, it understand only binary 1/0
• So the program needs to be converted to binary.
• Using a compiler, the program is compiled which helps to convert the program into a machine
understandable language.
• Now the program is converted to a machine understandable language and is ready for execution.
• The program need to be loaded into the memory and it needs some resources of the computer.
• The OS provide these resources for the execution of the program.
• So, the OS loads the executable program into the memory, allocate the resources and then the
program will begin its execution.
• Until the executable code of the program is generated, it is a passive entity; it doesn’t do anything.
• But the moment it begins execution, the program is called as a process.
A PROCESS CAN BE THOUGHT OF AS A PROGRAM IN EXECUTION 4

Introduction to Processes
Processes
• Earlier computer supports one program/process execution at a time; but today’s
computer supports multiple program/process execution.
• One single program can have multiple processes associated with it.
• When a program begins its execution is called as a process.
Threads:
• Thread is a basic unit of process in execution.
• A process can have one thread to many threads.
• If you want to see which are the processes in execution in your computer, you can see it
using task manager.
• In order to see the threads that are running, you need to download a program called as
process explorer.
Task Manager - Processes
Process Explorer - Threads
Processes (contd…)
• A process includes the current activity, as represented by the value of the program
counter and the contents of the processor’s registers.
• A process generally also includes the process stack, which contains temporary data and
a data section, which contains global variables.
• A process may also include a heap, which is memory that is dynamically allocated
during process run time.
• The structure of a process in memory is as shown in Figure.

• A program by itself is not a process.
• A program is a passive entity, in contrast, a process is an active entity, with a
program counter specifying the next instruction to execute and a set of associated
resources.
• A program becomes a process when an executable file is loaded into memory. Two
common techniques for loading executable files
Process States
• As a process execute, it changes state.
• The state of a process is defined in part by the current activity of that process.
• A process may be in one of the following states:
New The process is being created
Running Instructions are being executed
Waiting The process is waiting for some event to occur
Ready The process is waiting to be assigned to a processor
Terminated The process has finished execution
Diagram of Process States
Lecture – 9
Process Scheduling
Process Scheduling-Basics
The objective of multiprogramming is to have some process running all times, to maximize the CPU
utilization.
Time sharing is to switch the CPU between the processes so frequently that users can interact with
each program while it is running.
To meet these objectives, the process scheduler selects an available process from a set of available
processes, for program execution on the CPU.
◦ For a single processor system, there will never be more than one running process
◦ Of there are more processes, the rest will have to wait until the CPU is free and can be
rescheduled.
Scheduling Queues:
In order to help the process scheduling we have scheduling queues.
There are two types of queues:
◦ Job queue
◦ Ready queue
PROCESS SCHEDULING 3
Scheduling Queues
Ø Job Queue – As the process enters the system, they are put into a job queue, which consist of
all processes of the system.
Ø The processes may not be executing at this time, but these are the list of all processes we have
in the system.
Ø Ready Queue – The processes that are residing in the main memory and are ready and waiting
to execute are kept on a list called the ready queue.
CPU
Processes
Ready Queue – processes that are ready and waiting to execute Job Queue – all processes in the system
Queueing-diagram representation of
process scheduling
job queue assigned to CPU end/terminated
Ø Each rectangular box represents a queue.

Ø Two types of queues are present: the ready queue and a set of device queues.
Ø The circles represent the resources that serve the queues, and the arrows indicate the flow of processes
in the system
Queueing-diagram contd…
Ø A new process is initially put in the ready queue.
Ø It waits there until it is selected for execution, or dispatched.
Ø Once the process is allocated to the CPU and is executing, one of several events could
occur:
Ø The process could issue an I/O request and then be placed in an I/O queue.
Ø The process could create a new child process and wait for the child’s termination.
Ø The process could be removed forcibly from the CPU, as a result of an interrupt, and be
put back in the ready queue.
Ø In the first two cases, the process eventually switches from the waiting state to the ready
state and is then put back in the ready queue.
Ø A process continues this cycle until it terminates, at which time it is removed from all
queues and has its PCB and resources deallocated.
Schedulers
Ø A process migrates among the various scheduling queues throughout its lifetime.
Ø The OS must select processes from these queues for scheduling and the selection process is carried out by a scheduler.
Ø In a batch system, more processes are admitted than can be executed immediately. These processes are send to a mass-
storage device (like disk), where they are kept for later execution.
Ø The job scheduler (long-term scheduler) – selects processes from this pool and loads them into memory for execution.
Ø The CPU scheduler (short-term scheduler) - selects from among the processes that are ready to execute and allocates the
CPU to one of them.
Ø The primary distinction between these two schedulers lies in frequency of execution.
Ø The short-term scheduler must select a new process for the CPU frequency. Often, the short-term scheduler executes at
least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast.
Ø The long-term scheduler executes much less frequently; minutes may separate the creation of one new process and the
next. The long-term scheduler controls the degree of multiprogramming .
Addition of medium-term scheduling to
queueing diagram
Ø Processes can be described as either I/O bound or CPU bound.
Ø An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations.
Ø A CPU-bound process in contrast, generates I/O requests infrequently, using more of its time doing
computations.
Ø It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-bound
processes.
Ø Some operating systems, such as time-sharing systems, introduce an intermediate level of scheduling -
medium-term scheduler.
Context Switch
What is a context switch?
When does a context switch occur?
What does a context switch do in an operating system?
Ø Interrupts cause the operating system to change a CPU from its current task and to run a
kernel routine.
Ø Such operations happen frequently on general purpose systems.
Ø When an interrupt occurs, the system needs to save the current context of the process
currently running on the CPU so that it can restore that context when its processing is done,
essentially suspending the process and then resuming it.
Ø The context is saved in the PCB of the process.
Context Switch contd….
Ø Switching the CPU to another process requires performing a state save of the current process
and a state restore of a different process.
Context Switch
State save State restore
Ø Context switch time (milli sec) is an overhead, as the system does no useful work during
switching.

Lecture – 11
Operations on Processes
Process Creation
■ The processes in most systems can execute concurrently, and they may
be created and deleted dynamically.
■ Thus, these systems must provide a mechanism for process creation
and termination.
Process Creation
■ A process may create several new processes, via a create-process
system call, during the course of execution.
■ The creating process is called a parent process and the new processes
are called the children of that process.
■ Each of these new processes may in turn create other processes,
forming a tree of processes.
Process Creation contd…
■ When a process creates a new process, two possibilities exist in terms of execution:
– The parent continues to execute concurrently with its children
– The parent waits until some or all of its children have terminated
■ With respect to the resource requirements:
– The children may have all of the resources of the parent process or
– A subset or a part of the resources of the parent.
■ There are also two possibilities in terms of the address space of the new processes:
– The child process is a duplicate of the parent process (same program and data as
the parent)
– The child process has a new program loaded into it
Process Termination
■ A process terminates when it finishes executing its final instruction and ask the OS to
delete it by using the exit() system call.
■ At that point, the process may return a status value to its parent process (via wait()
system call)
■ All the resources of the process - including physical and virtual memory, open files and
I/O buffers - are deallocated by the OS
Termination can occur in other circumstances as well:
■ A process can cause the termination of another process via an appropriate system call
■ Usually, such a system call can be invoked only by the parent of the process that is to be
terminated.
■ Otherwise, users could arbitrarily kill each other’s job
Process Termination contd…
■ A parent may terminate the execution of one of its children for a variety of reasons:
– The child had exceeded the usage of some of the resources that it has been
allotted
– The task assigned to the child is no longer required
– The parent is exiting, and the OS does not allow a child to continue if its parent
terminates
Lecture – 13
Threads
THREADS 2
INTRODUCTION
¡ A program under execution is a process

¡ Thread is a basic unit of execution
¡ Each program may have a number of processes associated with it and each processes can have a number of
threads executing in it
¡ Thread is a basic unit of execution or basic unit of CPU utilization
¡ A thread comprises of – thread ID – PC – register set – stack.
¡ It shares with other threads belonging to the same process its code section, data section, and other OS
resources such as open files and signals.
¡ A traditional or heavy weight process has a single thread of control. If a process has multiple threads of
control, it can perform more than one task at a time.
THREADS 3
SINGLE-THREADED & MULTI-THREADED PROCESSES
¡ Single-threaded process can execute only one task at a time.
Single process
¡ In multi-threaded process, there are multiple threads in a
single process and each of the thread has its own stack and
registers
¡ At the same time, the code section, data section and files of the
Single-threaded process
process are shared among various threads of the process.
¡ Multiple tasks can be executed by multi-threaded process
Single process
¡ Multi-threaded processes are more efficient than single-
threaded processes
¡ It will make the computations more faster and efficient.
4
THREADS Multi-threaded process

PROCESS THREADS VIEW
¡ Process threads view software – allows us to see the different processes and threads that running in
our system.
Different processes running on the system Different threads running on the system
Different threads perform different tasks and multiple tasks can be performed at the same time in a
THREADS
multi-threaded process Improving the speed and efficiency of computation. 5
BENEFITS OF MULTI-THREADED PROGRAMMING
Utilization of
Responsiveness Resource sharing Economy multiprocessor
architecture
Multi threading an interactive Threads share memory and the Allocating memory and Benefit of multithreading can be
application may allow a resources of the process to resources for process creation is greatly increased in a
program to continue running which they belong. The benefit costly. Because threads share multiprocessor architecture,
even if part of it is blocked or is of sharing code and data is that the resources of the process to where threads may be running
performing a lengthy operation, it allows an application to have which they belong, it is more in parallel on different
thereby improving several different threads of economical to create and processors. A single threaded
responsiveness to the users. activity within the same address context switch threads process thread can run only on a
space. single CPU, whereas multi
threading on a multi-CPU
machine increases the
concurrency.
THREADS
6
MULTI-THREADING MODELS
¡ Types of threads:
¡ User threads – supported above the kernel and are managed with out the kernel support
¡ Kernel threads – supported and managed directly by the operating system
¡ There must exist a relationship between the user threads and kernel threads
How can we establish a relationship between the user threads and kernel threads?
Ans: through multi threaded models
¡ Multi threading models are the types of relationships that can be there between the user threads and
kernel threads.
¡ There are three ways to establishing the relationship
¡ Many-to-One Model
¡ One-to-One Model
¡ Many-to-Many Model
THREADS 7
many to one
MANY-TO-ONE MODEL
¡ There is a many-to-one relationship established between the user threads and kernel threads
¡ Here, many user threads are accessing one kernel thread
¡ Maps many user-level threads to one kernel thread
¡ Advantages:
¡ Thread management is done by the thread library in user space, so it is efficient.
¡ Here, we are able to manage the threads in the user space
¡ Disadvantages:
¡ The entire process will block if a thread makes a blocking system call
¡ Because only one thread can access the kernel at a time, multiple threads are unable to run in parallel on
multiprocessors.
THREADS 8
one to one
ONE-TO-ONE MODEL
¡ Here, one user thread is mapped to exactly one kernel thread

¡ Advantages:
¡ Maps each user thread to a kernel thread
¡ Provides more concurrency than the many-to-one model by allowing another thread to run when a
thread makes a blocking system call
¡ Allows multiple threads to run in parallel on multiprocessors
¡ Disadvantages:
¡ Creating a user thread requires creating the corresponding kernel thread
¡ Because the overhead of creating the kernel threads, can burden the performance of an application, the
number of threads supported by the system is limited.
THREADS 9
MANY-TO-MANY MODEL many to many
¡ Many user threads are mapped to many kernel threads

¡ Advantages:
¡ Multiplexes many user-level threads to a smaller or equal number of kernel threads
¡ The number of kernel threads may be specific to either a particular application or a particular machine
¡ Developers can create as many user threads as necessary, and the corresponding kernel threads can run in parallel on
a multiprocessor
¡ When a thread performs a blocking system call, the kernel can schedule another thread for execution
¡ So, many-to-many model is advantageous than one-to-one model and many-to-one model
¡ It is the model that is implemented in most of the systems
¡ This is the best model we can have in a multi threading system to establish a relationship between the user
threads and kernel threads.
THREADS 10
THREADING ISSUES
¡ What are the issues that we face in threading and how do address them?
¡ Fork() exec() system calls
¡ These system calls are used for specific purposes such as:
¡ Fork() is used to duplicate a process or for creating a child process from a parent
process with a different ID
¡ Exec() system call is used for replacing the contents of a process with another process,
but retaining the same process ID.
¡ The semantics of the fork() and exec() system calls change in a multi threaded
programming
¡ Because a process can consist of multiple threads and one thread in the system
requested for a fork() system call
¡ When a fork() system call is made, it is to create a duplicate process.
THREADS 11
THREADING ISSUES – FORK() SYSTEM CALL
¡ Issue:
¡ If one thread in a program calls a fork() call, does the new process duplicate all threads, or is the new
process single threaded?
¡ Solution:
¡ Some UNIX system have chosen to have two versions of fork() – one that duplicates all threads and
another that duplicates only the thread that invoked the fork()system call
¡ Which of the fork() to be used and when?

¡ When do we duplicate all the threads? and
¡ When do we duplicate the single thread that called the fork() system call?
THREADS 12
THREADING ISSUES – EXEC() SYSTEM CALL
¡ What will happen when an exec() system call is invoked?

¡ If a thread invokes the exec() system call, the program specified in the parameter to exec() will
replace the entire process - including all the threads
¡ Function of a exec() system call – it is to replace the contents of a process with another process
that is passed as a parameter in the exec() system call
¡ So when an exec() system call is invoked, the entire process will be replaced including all the
threads by the new process that is mentioned in the parameter of the system call.
THREADS 13
WHICH VERSION OF FORK() TO USE AND WHEN?
¡ If a thread invokes an exec() system call, the program specified in the parameter to exec() will
replace the entire process – including all threads
¡ Which of the two versions of fork() to use depends on the application.
If exec() is called immediately after forking If the separate process does not call exec()
Then duplicating all threads in unnecessary, as the after forking
program specified in the parameters to exec() will
replace the process.
In this instance, duplicating only the calling thread is Then the separate process should duplicate all the
appropriate threads.
THREADS 14
THREADING ISSUES – THREAD CANCELLATION
¡ Thread cancellation is the task of terminating a thread before it has completed

When does thread cancellation occur?
What are the issues that we can face when thread cancellation occur?
¡ If multiple threads are concurrently searching through a database, and one threads
returns the result, the remaining threads might be cancelled.
¡ When a user presses a button on the web browser that stops a web page from loading
any further, all threads loading the page are cancelled.
¡ A thread that is to be cancelled is often referred to as the target thread.
THREADS 15
¡ Cancellation of a target thread may occur in two different scenarios:
1. Asynchronous cancellation 2. Deferred cancellation

One thread immediately terminates the target thread The target thread periodically checks whether it should terminate,
allowing it an opportunity to terminate itself in an orderly fashion.
Where the difficulty with cancellation lies?

¡ In situations where:
¡ Resources have been allocated to a cancelled thread
¡ A thread is cancelled in the midst of uploading data it is sharing with other threads.
¡ Often the OS will reclaim system resources from a cancelled thread, but will not reclaim all the
resources.
¡ Therefore, cancelling a thread asynchronously may not free a necessary system-wide resources.
THREADS 16
With deferred cancellation:
¡ One thread indicates that a target thread is to be cancelled

¡ But, cancellation occurs only after the target thread has checked a flag to determine if it should be
cancelled or not.
¡ This allows a thread to check whether it should be cancelled at a point when it can be cancelled
safely.
THREADS 17
Lecture - 14
Basics of CPU Scheduling
INTRODUCTION TO CPU SCHEDULING
Ø CPU scheduling is an important topic in operating systems

Ø CPU scheduling is the basis of multiprogrammed operating systems
Ø By switching the CPU among processes, the OS can make the computer more
productive
Ø Lets try understanding by switching the CPU among processes how the
productivity of the computer gets improved?
Ø Introduction to CPU scheduling
Ø Various CPU scheduling algorithms
Basics of CPU Scheduling 3

SINGLE PROCESSOR AND MULTIPROCESSOR SYSTEMS
• In a single processor system, only one process can run at a time

• Other processes must wait until the CPU is free and can be rescheduled
• In a multiprocessor system, there were many processes which can run concurrently on many
processors, and was found better
• The objective of multiprogramming is to have some process running all the time, to maximize
CPU utilization
• A process is executed until it must wait, typically for the completion of some I/O request.
• In a computer system, the CPU just sits idle.
• The waiting time is wasted and no useful work is accomplished – THE BASIC NEED OF CPU
SCHEDULING IS TO AVOID THIS WAITING TIME OR AVOID THE CPU IDLING TIME!!

NEED OF CPU SCHEDULING
• If there are processes available, then we want the CPU to be utilized as much as possible. We do
not want the CPU to idle.
• In order to accomplish this, we want to introduce CPU scheduling
• With multiprogramming, we try to use the CPU idling time productively.
• Several processes are kept in memory at one time.
• When one process has to wait, the OS takes the CPU away from that process and give the CPU to
another process and this pattern continues, making the computation more efficient.
• By doing this, the CPU will not be idle, it will be used by one or the other process for execution.

WHAT DOES CPU SCHEDULING DO?
• How do we determine
• Which process should get the CPU?
• Which process should wait?
• After how long a process should be given the CPU? CPU scheduling
• What do you mean by scheduling?
• We are trying to assign a particular time for doing a task
• The operating system will prepare a schedule of which process should get the CPU at what time
or how long should a process wait and things like that….
• What is the rule that CPU scheduling follows in order to accomplish this task?
• Many rules are followed (different scheduling algorithms)
Scheduling is a fundamental operating-system function. Almost all computer resources are scheduled
before use. The CPU is, of course, one of the primary computer resources. Thus, CPU scheduling is
central to operating-system design.
6
CPU AND I/O BURST CYCLES
• The success of CPU scheduling depends on how to manage the process execution
between CPU execution and I/O wait.
• Processes alternate between these two states.
CPU Burst is
• CPU execution – when a process has begun its execution, it is under the CPU execution when the
state. It is using CPU for its execution. process is
being executed
• I/O wait state - the process may require an input/output operation in order to in the CPU
complete its execution.
• CPU burst – is the time when the process is in CPU execution.
I/O Burst is
• I/O burst – when a process is waiting for an I/O, it is called as I/O burst. when is
• Process execution begins with a CPU burst, followed by an I/O burs, CPU burst, I/O waiting for
burst and so on. I/O for further
execution
• The final CPU burst ends with a system request to terminate execution.
CPU SCHEDULER
• Whenever the CPU becomes idle, the OS must select one of the processes in the ready queue
to be executed. The selection process is carried out by the short-term scheduler, or CPU
scheduler.
• The scheduler selects a process from the processes in memory that are ready to execute and
allocates the CPU to that process.
• Ready queue is not necessarily a first-in, first-out (FIFO) queue.
• A ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an
unordered linked list.
• All the processes in the ready queue are lined up waiting for a chance to run on the CPU.
• The information contained in the queues are generally process control blocks (PCB) of the
processes.
DISPATCHER
• Another component involved in the CPU-scheduling function is the dispatcher.

• The dispatcher is the module that gives control of the CPU to the process selected by the
short-term scheduler. This function involves the following:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program
• The dispatcher should be as fast as possible, the time it takes for the dispatcher to stop one
process and start another running is known as the dispatch latency.

9
PREEMPTIVE & NON-PREEMPTIVE SCHEDULING
• They are the two different ways in which scheduling can happen.
• Preemptive and non-preemptive scheduling are not CPU scheduling algorithms, but they are two ways
in which CPU scheduling can take place.
• CPU scheduling decisions may take place under the following four circumstances:
1) When a process switches from the running state to the waiting state
2) When a process switches from the running state to the ready state (eg. When an interrupt occurs)
3) When a process switches from the waiting state to the ready state (at completion of I/O)
4) When a process terminates
• For cases 1 & 4, there is no choice in terms of scheduling. A new process must be selected for
execution. But, there is a choice for case 2 & 3.
• When scheduling takes place only under circumstances 1 & 4, we say that the scheduling
scheme is non-preemptive or cooperative. Otherwise, it is preemptive.

SCHEDULING CRITERIA
• To understand different scheduling algorithms we need to know different scheduling

criteria based on which we can compare different scheduling algorithms.
• When we have many scheduling algorithms, on what basis we are going to compare them or
on what basis are we deciding the efficiency or performance of a particular algorithm. For
this, we need some criteria to decide this.
• The different scheduling criteria are:
• CPU utilization
• Throughput
• Turnaround time
• Waiting time
• Response time
SCHEDULING CRITERIA
§ Keep the CPU as bust as possible
CPU UTILIZATION § CPU utilization can vary from 0 to 100%
§ In real system, vary from 40% (lightly loaded)to 90% (heavily loaded)
• If CPU is busy executing processes, then work is being done

THROUGHPUT • One measure of work done is the number of processes that are completed per unit time, called
throughput
For a process, an important criteria is how long it takes to execute that process.
• The interval from the time of submission of a process to the time of completion is turnaround time.
TURNAROUND • Turnaround time the sum of time periods spent to get into memory, waiting in the ready queue, executing
TIME on CPU and doing I/O.
§ Another measure is the time from the submission of a request until the first response is produced.
RESPONSE TIME § This measure is the response time, and is the time it takes to start responding, not the time it takes
to output the response
§ The CPU scheduling does not affect the amount of time during which a process executes or does I/O.
§ It affects only the amount of time that a process spends waiting in the ready queue.
WAITING TIME
§ Waiting time is the some of the periods spent waiting in the ready queue.
12
Lecture - 15
Scheduling Algorithms
I. FIRST COME, FIRST SERVED SCHEDULING
(FCFS)
q The simplest CPU scheduling algorithm
q The process that requests the CPU first is allocated the CPU first
q The implementation of FCFS is easily managed with a First-in First-out (FIFO) queue.
q When a process enters the ready queue, its PCB is linked onto the tail of the queue.
q When the CPU is free, it is allocated to the process at the head of the queue.
q The running process is then removed from the queue.
WHETHER FCFS IS AN EFFICIENT SCHEDULING ALGORITHM?
q The average waiting time under the FCFS policy is long.

q Consider the following set of processes that arrive at time 0
q Burst time is the time that a process will take to complete its execution.
q If the processes arrive in the order P1, P2 and P3 and are served in FCFS order,
we get the following result:
q Waiting time for P1 = 0

q Waiting time for P2 =24ms
q Waiting time for P3 = 27ms
q Average waiting time = (0+24+27)/3 = 17ms
WHETHER FCFS IS AN EFFICIENT SCHEDULING ALGORITHM?
q If the processes arrive in the order P2, P3, P1 (with the same burst time)
q Waiting time for P2 =0ms
q Average waiting time = (6+0+3)/3 = 3ms
q This reduction is substantial. Thus, the average waiting time under an FCFS policy is generally not minimal
and may vary substantially if the process’s burst times vary greatly.
The FCFS scheduling algorithm is non-preemptive
! K.)% #$% G0L $+* 8%%. +DD()+#%/ #( + &'()%**2 #$+# &'()%** M%%&* #$% G0L 9.#,D ,# '%D%+*%* #$% G0L2 %,#$%' 8I
#%'7,.+#,.< (' 8I '%N9%*#,.< !BKE
! FGFH +D<(',#$7 ,* #'(98D%*(7% "(' #,7%O*$+',.< *I*#%7*2 6$%'% ,# ,* ,7&('#+.# #$+# %+)$ 9*%' <%#* + *$+'% ("
#$% G0L +# '%<9D+' ,.#%'-+D*E
! !# 6(9D/ 8% /,*+*#'(9* #( +DD(6 (.% &'()%** #( M%%& #$% G0L "(' +. %P#%./%/ &%',(/E
! !"# $% $& '"% (' )**$+$)'% (,-".$%/01
II. SHORTEST JOB FIRST SCHEDULING (SJF)
q SJF - The process that requires shortest time run on CPU will be the first process to get the
CPU.
q This algorithm associates with each process the length of the process’s next CPU burst.
q When the CPU is available, it is assigned to the process that has the smallest next CPU burst.
q If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.
The SJF algorithm can be either preemptive or non-preemptive
! E 2*)' .(()*()1.-' -')2 :*) -&1, ,+&'B0813; 2'-&*B 7*08B 9' -&' ,89:;<=;>-<?;>4&5>@A:=;
sncba
%BC9:D;8E#
! F'+.0,' ,+&'B0813; B'('3B, *3 -&' 8'3;-& *: -&' 3'>- 456 90),- *: . ()*+',,A ).-&') -&.3 1-,
-*-.8 8'3;-&<
EXAMPLE OF SJF SCHEDULING (NON-PREEMPTIVE)
q Consider the following set of processes, with the length of the CPU burst given in
millisecond:
q Average waiting time = (3+16+9+0)/4 = 7ms
q If we were using the FCFS algorithm, the average waiting time would be 10.25 ms
q From this, we can see that SJF algorithm is better than FCFS algorithm.
EXAMPLE OF SJF SCHEDULING (PREEMPTIVE)
q Consider the following set of processes, with the length of the CPU burst given in millisecond:
Waiting time = Total waiting time - No. of milliseconds process executed – Arrival time
! ?.1-13; -12' :*) 5I J KIL$I$LM J N2,

! ?.1-13; -12' :*) 5O J KI$L$IM J L2,
! ?.1-13; -12' :*) 5P J KIQ$L$OM J IR2,
! ?.1-13; -12' :*) 5S J KR$L$PM J O2,
! %F<:GC< HGD;DIC ;DE< J 1KLMLNOLP3QR J S#OE=
Preemptive SJF scheduling is sometimes called Shortest Remaining Time First Scheduling
PROBLEMS WITH SJF SCHEDULING
q The problem with SJF is knowing the length of the next CPU request.
q Although the SJF algorithm is optimal, it cannot be implemented at the level of short-term
CPU scheduling.
q There is no way to know the length of the next CPU burst.
One approach is:
! !3 )49 )3 2''43H%&2)# 8G7 $-"#./(%01
! A# &29 03) D03: )"# (#01)" 36 )"# 0#H) *+, F/4$)B F/) :# &29 F# 2F(# )3 '4#.%-) %)$
E2(/#@
! A# #H'#-) )"2) )"# 0#H) *+, F/4$) :%(( F# $%&%(24 %0 (#01)" )3 )"# '4#E%3/$ 30#$@
! !"/$B F9 -3&'/)%01 20 2''43H%&2)%30 36 )"# (#01)" 36 )"# 0#H) *+, F/4$)B :# -20 '%-D )"#
'43-#$$ :%)" )"# $"34)#$) '4#.%-)#. *+, F/4$)@
III. PRIORITY SCHEDULING
q A priority is associated with each process, and the CPU is allocated to the process with
the highest priority.
q Equal priority processes are scheduled in FCFS order.
q An SJF algorithm is a priority algorithm, where priority is the inverse of next CPU burst.
q The larger the CPU burst, the lower the priority, and vice versa.
2/) PS (,-".$%/0 +(' <) )$%/). 9.))09%$:) ". '"'89.))09%$:)
! I '4##&')%E# '4%34%)9 $-"#./(%01 2(134%)"& :%(( '4##&') )"# *+, %6 )"# '4%34%)9 36 )"#
0#:(9 244%E#. '43-#$$ %$ "%1"#4 )"20 )"# '4%34%)9 36 )"# -/44#0)(9 4/00%01 '43-#$$#$@
! I 030;'4##&')%E# '4%34%)9 $-"#./(%01 2(134%)"& :%(( $%&'(9 '/) )"# 0#: '43-#$$ 2) )"#
"#2. 36 )"# 4#2.9 5/#/#@
EXAMPLE OF PRIORITY SCHEDULING
q Consider the following set of processes, assumed to have arrive time 0, in the order P1,
P2, P3, P4 and P5:

q Average waiting time = (6+0+16+18+1)/5 = 41/5 = 8.2ms
PROBLEM WITH PRIORITY SCHEDULING
Problem with priority scheduling
q The problems with priority scheduling is indefinite blocking or starvation.
q A process that is ready to run, but waiting for the CPU can be considered blocked.
! ! "#$%#$&' ()*+,-.$/0 1.0%#$&*2 )1/ .+13+ (%2+ .%4 "#$%#$&' "#%)+((+( 41$&$/0 $/,+5$/$&+.'6
!"#$%&"' %" %() *+",#)-
! 7/,+5$/$&+ 8.%)910+ %5 &*+ .%4:"#$%#$&' "#%)+(( $( 10$/0
! !0$/0 $( 1 &+)*/$;-+ %5 0#1,-1..' $/)#+1($/0 &*+ "#$%#$&' %5 &*+ "#%)+((+( &*1& 41$& $/ &*+
,T,-'2 :*) . 8*3; -12'<
0?GEUB<
! C: ()1*)1-1', ).3;', :)*2 IOQ -* LA 7' +*08B 13+)'.,' -&' ()1*)1-T *: . 7.1-13; ()*+',, 9T I
'@')T IR213,<
! U@'3-0.88TA . ()*+',, 71-& . ()1*)1-T *: IOQA 7*08B &.@' -&' &1;&',- ()1*)1-T 13 -&' ,T,-'2 .3B
7*08B 9' '>'+0-'B<
IV. ROUND ROBIN (RR) ALGORITHM SCHEDULING
q The RR scheduling algorithm is designed especially for timesharing systems.
q It is similar to FCFS scheduling, but preemption is added to switch between the processes.
q A small unit of time, called time quantum or time slice is defined (10 to 100ms)
q Each process is assigned this time quantum for its execution on CPU, irrespective of its CPU
burst.
! = 2/.&#%% <*)) ;# -)).<#' 0. /(+ .+)3 4./ 0"-0 0*1# >(-+0(1 -1.(+0 *+ 0"# 4*/%0 /.(+': -+'
-40#/ 0"-0 0"# +#D0 2/.&#%% <*)) ;# -%%*,+#' 0. 0"# 8EF -+' %. .+5
! !"# /#-'3 >(#(# *% 0/#-0#' -% - &*/&()-/ >(#(#5
! !"# 8EF %&"#'()#/ ,.#% -/.(+' 0"# /#-'3 >(#(#: -)).&-0*+, 0"# 8EF 0. #-&"
! 2/.&#%% 4./ - 0*1# *+0#/G-) .4 (2 0. @ 0*1# >(-+0(1
IMPLEMENTATION OF RR SCHEDULING
q Ready queue is a FIFO queue of processes

q Processes are added to the tail of the ready queue.
q The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt
after 1 time quantum, and dispatches the process
V. MULTILEVEL QUEUE SCHEDULING
q A class of scheduling algorithms has been created for situations in which processes are easily
classified into different groups.
q If we are able to classify our processes into different groups, for this kind of processes there are a
class of scheduling algorithms that has been created. Multilevel queue is one of them.
q Example:
! F('%<'(9./ &'()%**%* 7+I $+-% &',(',#I %P#%'.+DDI /%",.%/ (-%' 8+)M<'(9./ &'()%**%*E
! @ 79D#,D%-%D N9%9% *)$%/9D,.< +D<(',#$7 &+'#,#,(.* #$% '%+/I N9%9% ,.#( *%-%'+D *%&+'+#% N9%9%*E
! C$% &'()%**%* +'% &%'7+.%.#DI +**,<.%/ #( (.% N9%9%2 <%.%'+DDI 8+*%/ (. *(7% &'(&%'#I (" #$%
&'()%**%*2 *9)$ +* 7%7('I *,T%2 &'()%** &',(',#I2 (' &'()%** *,T%E
! R+)$ (.% $+* ,#* (6. *)$%/9D,.< +D<(',#$7E
MULTILEVEL QUEUE SCHEDULING CONTD….
Example:
q Separate queues might be used for foreground and background processes.
q Foreground processes may be scheduled by RR algorithm, while the background processes queue is
scheduled by an FCFS algorithm.
q Foreground processes being interactive processes, cannot wait for long time, need to be quick.
q In order for them to be quick, there need to be a proper time sharing between them.
! ;$,)$ ,* #$% 8%*# *)$%/9D,.< +D<(',#$7 #$+# 6% )+. 9*%V K9# (" #$% /,*)9**%/ +D<(',#$72 #$+# 8%*#
*9,#* #,7% *$+',.< *I*#%7* +'% UU *)$%/9D,.<E
! W+)M<'(9./ &'()%**%* 8%,.< .(# ,.#%'+)#,-%2 )+. 6+,# "(' *(7% #,7% ,. #$% N9%9%E H(2 6% )+. 9*%
FGFH +D<(',#$7E
! !. +//,#,(.2 #$%'% 79*# 8% + *)$%/9D,.< +7(.< #$% N9%9%*2 6$,)$ ,* ",P%/ &',(',#I &'%%7&#,-%
*)$%/9D,.<E
! R<2E F('%<'(9./ N9%9% 7+I $+-% &',(',#I (-%' 8+)M<'(9./ N9%9%E
AN EXAMPLE – MULTILEVEL QUEUE SCHEDULING
q There are five queues and within queues, we have processes.
q Consider the low priority queue: student queue - it can execute only when all the above
queues are empty.
q Similarly, batch processes can execute only when the processes in the above queues are
empty.
DRAWBACK – Processes belonging to one queue cannot move from that queue to another, until its execution completion.
VI. MULTILEVEL FEEDBACK SCHEDULING
q In a multilevel scheduling, processes belong to one queue cannot move to another queue,
until its execution is complete.
q A multilevel feedback scheduling allows a process to move between queues.
q This is the main difference between multilevel scheduling and multilevel feedback
scheduling.
q The idea here is to separate processes according to the characteristics of their CPU
bursts.
! =6 2 '43-#$$ /$#$ )33 &/-" *+, )%&#B %) :%(( F# &3E#. )3 2 (3:#4 '4%34%)9 5/#/#@
! !"%$ $-"#&# (#2E#$ =W> F3/0. 20. %0)#42-)%E# '43-#$$#$ %0 )"# "%1"#4 '4%34%)9 5/#/#$@
! =0 2..%)%30B 2 '43-#$$ )"2) :2%)$ )33 (301 %0 2 (3: '4%34%)9 5/#/# &29 F# &3E#. )3 2 "%1"
'4%34%)9 5/#/#@
! !"%$ 634& 36 21%01 '4#E#0)$ $)24E2)%30@
EXAMPLE – MULTILEVEL FEEDBACK SCHEDULING
q Processes belonging to queues of lower priority can execute only when
queues of higher priorities are empty.
q Different queues will follow different scheduling algorithms.
q Also, processes in different queues are allowed to execute with different
quantum of time.
q Eg. QUEUE 0 is the highest priority queue and each process in QUEUE 0 will
run for a time quantum of 8ms.
q Then, next higher priority queue is QUEUE 1, where each process will run for
time quantum of 16ms.
! A5% (#0%" 1"+#"+,2 -.%.% +& =><>< D; +) 05+$5 1"#$%&&%& ".) '3&%9 #) EFEG7
! H%"%; +/ 1"#$%&&%& +) =><>< ? $#61(%,%& +,& %4%$.,+#) 0+,5+) @6&; +, +& /+)%I
#,5%"0+&% ,5#&% 1"#$%&&%& 0+(( '% 6#J%9 /"#6 =><>< ? ,# A:KL #/ =><>< B7
! G+6+(3"(2; 1"#$%&&%& +) =><>< B +& 3((#0%9 ,# %4%$.,% /#" BC6&7 M,5%
1"#$%&&%& +) =><>< B 0+(( ".) #)(2 3/,%" 1"#$%&&%& +) =><>< ? $#61(%,%&N;
3)9 +/ $3))#, $#61(%,%; 0+(( '% 6#J%9 /"#6 =><>< B ,# A:KL #/ =><>< D7
! :)9 +, $#),+).%&7
PARAMETERS DEFINING MULTILEVEL FEEDBACK
QUEUE SCHEDULING
Following are the parameters:

q The number of queues
q The scheduling algorithm for each queue
q The method used to determine when to upgrade a process to a higher priority queue.
q The method used to determine when to demote a process to a lower priority queue.
q The method used to determine which queue a process will enter when that process
needs service.
PROCESS
SYNCHRONIZATION
z
UNIT – 2
2
Lecture - 16
Introduction to
Process Synchronization
3
z
§ By process synchronization we mean some kind of synchronization between the processes.
§ Why do we need that? – need to find out
§ A cooperating process is one that can affect or be affected by other processes

executing in the system.
Cooperating
processes
Problem: Concurrent
Directly share a logical Or be allowed to share access to shared data
address space (both only data through files or may result in data
code and data) messages
inconsistency
4
z
§ Cooperating process will be sharing a region of data.
§ So they will be able to access the shared region and will be able to manipulate that shared
data.
§ if multiple processes are concurrently trying to manipulate data, then that will lead to data
inconsistency.
§ That is the problem we have and that is why we need process synchronization.
We will discuss:
Various mechanisms to ensure the orderly execution of cooperative processes
that share a logical address space.
So that data consistency is maintained.

5
z
An Example to understand why Process
Synchronization is important
§ We have learnt about shared memory systems - and understood a problem called as
Producer-Consumer Problem.
§ A producer process produces information that is consumed by a consumer process.
§ One solution to Producer-Consumer Problem uses shared memory.
§ To allow producer and consumer process to run concurrently, we must have available a
buffer of items that can be filled by producer and emptied by the consumer.
§ This buffer will reside in a region of memory that is shared by the producer and consumer
processes.
§ A producer can produce one item while the consumer is consuming another item.
§ The producer and consumer must be synchronized, so that the consumer does not try to
consume an item that has not yet been produced.
6
z
Example contd….
§ Two kind of buffers: unbounded buffer (no practical limit on the size of the buffer) and
bounded buffer (fixed buffer size).
§ lets try to use the bounded buffer and try to modify it.
§ In a bounded buffer we need to keep track of the items that are present in the buffer,
because we need to know when the buffer is full and empty.
§ So lets use a variable: counter to count the no. of items present in a buffer
§ Counter will be incremented by 1 - a process is added to the buffer by the producer
will be decremented by 1 - a process is consumed by the consumer process.
§ Initially counter variable = 0

7
z
Example contd…
§ Counter is incremented every time we add a new item to the buffer: counter++
§ Counter is decremented every time we remove one item to the buffer: counter—
§ Example:
§ Suppose that the value of the variable counter is currently 10
§ The producer and consumer processes execute the statements counter++ and
counter– concurrently.
§ Following the execution of these two statements, the value of the variable counter may
be 9, 10 or 11!
§ The only correct result, though is counter==10, which is generated correctly of the
producer and consumer execute separately.
8
z
Implementation of Counter
§ ‘Counter++’ may be implemented in machine language as:

§ Register1 = counter; value of counter is stored in Register1(10)
§ Register1 = Register1 + 1; register1 value is incremented by 1 (11)
§ Counter = Register1; value of register1 is stored to counter (counter=11)
§ ‘Counter--’ may be implemented in machine language as:

§ Register2 = counter; value of counter is stored in Register2 (10)
§ Register2 = Register2 - 1; register2 value is decremented by 1 (9)
§ Counter = Register2; value of register2 is stored to counter (counter=9)

9
z
Race condition
T0 producer execute Register1 = counter {Register1 = 10}
T1 producer execute Register1 = Register1 + 1 {Register1 = 11}
T2 consumer execute Register2 = counter {Register2 = 10}
T3 consumer execute Register2 = Register2 – 1 {Register2 = 9}
T4 producer execute Counter = Register1 {counter = 11}
T5 consumer execute Counter = Register2 {counter = 9}
We arrived at this incorrect state, because we allowed both processes to manipulate

the variable counter concurrently.
A situation like this, where several processes access and manipulate the same data concurrently
and the outcome of the execution depends on the particular order in which
the access takes place, is called a race condition.
In the example, if producer gets hold of the counter, the value of counter=11 and if consumer
was the first one to get counter; then counter=9.
So, there is a race between producer and consumer.
Who ever first gets hold of the variable, will modify the counter variable first.
Here, we arrived at wrong answer because we allowed two processes to modify the same variable concurrently.
We want the resulting changes not to interfere with one another. Hence, we need process synchronization.
PROCESS
SYNCHRONIZATION
UNIT – 2
Lecture - 18
Critical Section Problem
&
Peterson’s Solution
CRITICAL SECTION
• Consider a system consisting of n processes {P0, P1,P2,…..Pn}
• Each process has a segment of code, called a critical section in which the process may be changing
common variables, updating a table, writing a file and so on.
• Critical section is a segment of code in a process where, the process will be changing common
variables, updating a table, writing a file and so on.
• Whenever the process is accessing and doing some manipulations in the shared memory, then the
code that is responsible for doing that particular operation is known as a critical section.
• When one process is executing in its critical section, no other process is to be allowed to execute in
its critical section.
• That is no two processes are executing in their critical sections at the same time.
3
CRITICAL SECTION
• In process synchronization, when two different processes are simultaneously trying to manipulate a shared
variable, then data inconsistency may occur. So in order to avoid that we are using the critical section.
• Different processes have different critical sections.
• So when one process is executing its critical section, it implies that it is making some change to the shared data.
During that time we should not allow other processes to execute in their critical section.
• That is when one process is accessing and manipulating the shared data no other process will be allowed to
access and manipulate the shared data.
• If this can be accomplished, then we can guarantee that multiple processes will not concurrently try to manipulate
the shared data.
• The critical section problem is to design a protocol that the processes can use to cooperate.
4
RU L E S TO B E F O L LOW E D BY P RO C E S S E S
WHILE USING CRITICAL SECTIONS
1) Each process must request permission to enter its critical section

2) The section of code implementing this request is the entry section
3) The critical section may be followed by an exit section
4) The remaining code is the remainder section.
General structure of a typical process
5
R E Q U I R E M E N T S T O B E S AT I S F I E D
• A solution to the critical section problem must satisfy the following three requirements:
a) Mutual exclusion:
• If process Pi is executing in its critical section, then no other processes can be executing in their critical
sections
b) Progress:
• If no process is executing in its critical section and some processes wish to enter their critical section,
then only these processes that are not executing in their reminder sections can participate in the
decision on which will enter its critical section next, and this selection cannot be postponed
indefinitely.
c) Bounded waiting
• There exists a bound, or limit, on the number of times that other processes are allowed to enter their
critical sections after a process has made a request to enter its critical section and before that request
is granted.
6
PETERSON’S SOLUTION
• A classic software-based solution to the critical section problem
• May not work correctly on modern computer architectures
• However, it provides a good algorithmic description of saving the critical section problem and illustrates some of the
complexities involved in designing software that addresses the requirements of mutual exclusion, progress and bounded
waiting requirements.
• Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder
sections. Let’s call the processes Pi and Pj.
• Peterson’s solution requires two data items to be shared between the two processes:
int turn boolean flag[2]
If turn= I, then process Pi is ready to enter If flag(i) = process Pi is ready to enter
its critical section and Indicate whose turn it is to Used to indicate if a process is ready
its critical section and
If turn=2, process Pj is ready to enter enter its critical section If falg(j) = process Pj is ready to enter
its critical section to enter its critical section its critical section
7
HOW PETERSON’S SOLUTION WORKS
• In Peterson’s solution, when a process (Pi) wants to enter into critical section, it will set its
flag=true, indicating that the process (Pi) is ready to enter the critical section.
• If a process (Pi) wants to enter into its critical section, it will set turn=other process (Pj)
• It is a humble algorithm because, when one process wants to enter into its critical section,
instead of entering the critical section, it is giving the turn to another process.
8
HOW PETERSON’S SOLUTION WORKS
int turn boolean flag[2]
Indicate whose turn it is to Used to indicate if a process is ready

enter its critical section to enter its critical section
Structure of process Pi in Peterson’s solution Structure of process Pj in Peterson’s solution

9
EXAMPLE
• Lets consider both Pi and Pj wants to enter into the critical section at the same time.
• Should that be allowed? NO
• Pi and Pj tries to enter into critical section, and what will happen?
• Pi will execute its first instruction: flag[i] = true, telling Pi wants to enter into its critical section
• Pj also sets flag[j] = true, telling Pj also wants to enter into its critical section
• In Peterson’s solution, Pi is going to be humble and sets turn=j, allowing Pj to run its critical section
• Pj also does the same thing.
• Turn is a shared variable, so it will have only one value, which is the last set value will be the final value of turn. [turn = i, finally]
• Which if the while conditions are going to work?

• While condition of Pi: flag[j] is true && turn==[j] is false – the while condition is false, so it will break from the while and come to critical section
part of Pi.
• At the same time: While condition of Pj: flag[i] is true && turn==[i] is true – the while condition is true, it will loop in while and will not enter
critical section of Pj.
• After Pi completes its critical section, flag[i]=false and while of Pj becomes false and it will execute its critical section.
10
W H E T H E R R E Q U I R E M E N T S A R E M E T O R N OT ?
• Mutual exclusion – yes it is preserved

• Progress – fulfilled. Both Pi and Pj was allowed to take a decision on who should enter the
critical section. Final value was dependent on the final value of turn. So, progress was also
fulfilled. The decision on who should enter the critical section was not postponed indefinitely. A
decision was taken, Pi executed first and then Pj.
• Bounded waiting – fulfilled. Because if a process wanted to enter the critical section, it was
allowed to enter the critical section and was not kept waiting indefinitely. Pi and Pj wanted to
enter into critical section, both set the turn to other process and finally, Pi got chance to
execute first and then Pj. So there was no indefinite waiting.
11
PROCESS
SYNCHRONIZATION
UNIT – 2
Lecture 19
Hardware & Software based Solutions
for Process Synchronization
Hardware Instructions for Critical Section Problems
q Software-based solutions such as Peterson’s are not guaranteed to work on modern

computer architectures.
q Hardware instructions that are available on many systems and showing how they can be used
effectively in solving the critical-section problem.
q Hardware features can make any programming task easier and improve system efficiency
q Solution 1:
• The critical-section problem could be solved in a single-processor environment if we
could prevent interrupts from occurring while a shared variable was being modified.
• In this way, we could be sure that the current sequence of instructions would be allowed
to execute in order without preemption.
• This is often the approach taken by non-preemptive kernels.
• Not feasible in a multiprocessor environment.
Hardware Instructions for Critical Section Problems
Solution 2:
q Many modern computer systems provide special hardware instructions that allow us either to
test and modify the content of a word or to swap the contents of two words atomically as one
uninterruptible unit.
q We can use these special instructions to solve the critical-section problem.
q Two instructions:
• Test_and_set()
• Compare_and_swap()
Test and Set Lock
q A hardware solution to the synchronization problem.

q There is a shared lock variable which can take either of the two values: 0 or 1
q Value –0: unlocked, value -1: locked
q Before entering into the critical section (CS), a process inquires about the lock
q If it is locked, it keeps on waiting till it becomes free (some other process is waiting its CS)
q If it is not locked, it takes the lock and executes the CS.
q Test_and_Set instruction returns a boolen result and
takes a Boolean type variable (target) as an argument
q Target = lock value
q rv = Target value
Atoand
Definition of Test mic Set() instruction
q reset target as TRUE at the end Operation
q Atomic operation – in test and set lock instruction, what ever is happening in a process will
happen as a single operation and will not be interrupted by any other processes.
Test and Set ()
q When the process P1 wants to run its CS, it will come to do-while loop
q In while loop, we have test_and_set function
q We are passing as argument – lock (address of lock, bz lock is a
shared variable and we need the current value of lock )
q Lock = 0 initially
Mutual exclusion implementation for P1 with test and set
q So we have test_and_set(0=target, rv=target=0, return 0)
q While(0) – while condition is FALSE, it will break out of while loop and run CS.
q While, P1 is executing CS, the target value is set to 1, no other process can enter CS
q After P1 executes, CS lock value is set to FALSE and P1 runs the reminder section.
q Now, if any other process want to execute CS, can run
Test and Set ()
q While P1 is executing its CS, if another process P2

wants to execute its CS, what will happen?
q P2 will also execute its do-while loop
q It has test_and_set instruction with argument lock
q Lock = 1. that is test_and _set(1), target=1, rv=target=1, it return1
P1
P2
q Then it is while(1), TRUE, it will keep looping while and will not come out of loop, do nothing.
q When P1 is executes its CS, even though P2 wants to execute its CS, cannot execute it
q After P1 completes its CS, lock is set to 0, and if P2 is still trying to execute its CS, lock=0 and
P2 can execute its CS.
Advantages:
q It satisfies mutual exclusion
q Does not satisfy bounded waiting – multiple preemptions of a low priority tasks
Compare_and_swap()
q In contrast to the test_and_set() instruction, compare_and_swap() operates on three

operands
q Mutual exclusion can be provided as follows: a global variable (lock) is declared and is
initialized to 0. The first process that invokes compare_and_swap() will set lock to 1. It will
then enter its critical section, because the original value of lock was equal to the expected
value of 0. Subsequent calls to compare and swap() will not succeed, because lock now is
not equal to the expected value of 0. When a process exits its critical section, it sets lock
back to 0, which allows another process to enter its critical section.
Software based Solution to Synchronization Problem
Semaphores
q Semaphores proposed by E. Dijkstra is a technique to manage concurrent
processes by using a simple integer value, which is known as semaphores
q Semaphore is simply a variable which is non-negative and shared between threads.
This variable is used to solve the CS problem and to achieve process
synchronization in the multiprocessing environment.
q A semaphore S is an integer variable that, apart from initialization is accessed only
3&('78& 3<' )3$5*$(* $3'#04 '(0"53$30'5 <$03CE $5* )085$9CE.
q Wait() à P {from the Dutch word proberen, which means “to test”}
q Signal() àV { from the Dutch word verhogen, which means “to increment”}
Wait()
Definition of wait()
q P is used to denote wait operation and S is semaphore
q When one process wants to access a resource or run its CS, at that time the variable S that is shared
between the processes,
Will take care of who should access the resource or who should enter the CS
q The process will check whether the variable S is <=0, some process is already using the resource or
running CS
q S is shared variable and if S is TRUE, it will be stuck in the while loop, doing no operation
q But, if S not <=0, (FALSE), then S is decremented by 1 and enters the CS and start executing it.
q The process decrements S, because it wants other processes to know that the value of S is decremented,
so that if any other process wants to enter the CS, can check the condition and enter the CS
q Wait operation is used to test whether any process is using the resource or is there any processes
running the CS and if it is not there, will decrement S and start using it or if any process is already running
its CS then, the while condition will be TRUE, and the requesting process will be stuck in the while loop.
q Wait is used for TESTING
Signal ()
! !085$9 '%"($30'5 0) 4$99"* <&"5 3&" %('4")) 3&$3 <$) #$2058 7)" 'B 3&" )"#$%&'("
3' "53"( 053' 3&" ?! '( <$) 7)058 $ (")'7(4"; 4'#%9"3") 03) '%"($30'5 $5* 0) '73 'B 03.
! M5 )085$9 '%"($30'5 03 054("#"53) 3&" :$97" 'B !; #"530'5058 3&$3 03 &$) 4'#%9"3"*
7)058 3&" )"#$%&'(" $5* '3&"( %('4"))") 4$5 7)" 03.
! !085$9 0) 7)"* +, $ %('4")) 3' !MNOAP '3&"( %('4"))") 3&$3 03 &$) 4'#%9"3"* 7)058
3&" (")'7(4"; $5* 0B $5, '3&"( %('4")) <$53) 3' 7)" 03 4$5 $44")) 03.
! O'3"Q A99 3&" #'*0B04$30'5) 3' 3&" 053"8"( :$97" 'B 3&" )"#$%&'(" 05 3&" <$03CE $5*
)085$9CE '%"($30'5) #7)3 +" "R"473"* 05*0:0)0+9,.
! >&$3 0); <&"5 '5" %('4")) #'*0B0") 3&" )"#$%&'(" :$97"; 5' '3&"( %('4")) 4$5
)0#793$5"'7)9, #'*0B, 3&$3 )$#" )"#$%&'(" :$97".
Types of Semaphores
q There are two types of semaphores:
1. Binary Semaphore: The value of a binary semaphore can range only between 0 and 1. On
some systems binary semaphores are known as mutex locks, or they are locks that provide
mutual exclusion.
q Find out how SIGNAL instruction is operated with binary semaphore:
q If S=0, some other process is executing its CS
q Assume that process P1 wants to run CS and checks for the value of S.
q S is free (S=1 initially), in signal instruction it checks whether S<=0, FALSE does not enter while loop, do
S– - (S=0)
q If another process P2 wants to execute CS, it checks the value of S. S is now 0. That process will be stuck
in the while loop, and will not enter the CS
q Now P1, after competing execution of its CS, it is exiting from CS, then P1 will call the SIGNAL operation.
q P1 will increment S (S=0+1=1), that means P1 is signaling other process that it has completed using CS,
and is now free to use by others.
Types of Semaphores
q The second type is:
2. Counting semaphore – Its value can range over an unrestricted domain (1,2,3…). It is used to
control access to a resource that has multiple instances.
q There are processes P1, P2 and P3 sharing the same resource which has two instances R1 and R2.
q In this case P1 can use R1 and P2 can use R2. But, it is limited.
q Here, S=2. initial value of S=2.
q P1 want resource. It checks the wait() operation. P1 checks whether S<=0? (2<=0) FALSE.
Decrement S (S=1) and use the resource R1.
q If P2 wants to use the same resource, it will execute wait() operation. S<=0? (1<=0) FALSE.
Decrement S (S=0) and use the resource R2.
q If P3 wants to use the same resource, it will execute wait() operation. S<=0? (0<=0) TRUE. P3 will
get stuck in the loop doing no operation and cannot use the resource. If P1 or P2 completes using
the resource, will call the signal() operation.
q It will increment S (S=1), resource is free and other process can use it. Now, P3 can make use of the
resource.
Disadvantages of Semaphores
q The main disadvantage of the semaphore is it requires busy waiting.

q While a process is in its critical section, any other process that tries to enter the CS must loop
continuously in the entry code.
q Busy waiting is a problem because it wastes CPU cycles that some other process might be able to use
productively.
q This type of semaphore is also called a spinlock because the process “spins” while waiting for the lock.
q To overcome the need for busy waiting, we can modify the definition of the wait() and signal() semaphore
operations.
q When a process executes the wait() operation and finds the semaphore value is not positive, it must wait.
q However, rather than engaging in busy waiting, the process can block itself.
q The block operation places a process into a waiting queue associated with the semaphore, and the state
of the process is switched to the waiting state.
q The control is transferred to the CPU scheduler which selects another process to execute.
q Whether all the problems are solved??
Deadlocks and Starvation
q The implementation of a semaphore with a waiting queue may result in a situation where two
or more processes are waiting indefinitely for an event that can be caused only by one of the
waiting processes. – DEADLOCK!!
q The event here is execution of a signal() operation. When such a state is reached, these
processes are said to be deadlocked.
q Two process P0 and P1 and two semaphores S and Q
q P0 executes wait on S and P1 execute wait on Q – both is OK
q Next, P0 try to execute wait on Q and it is not possible as P1 is using it
q P1 want execute wait on S and it is not possible as P0 is held by P0.
q Both of them are not able to proceed
q Process P0 and P1 are DEADLOCKED!!

Classical Problems of Synchronization
( The Bounded-Buffer Problem)
q Bounded-buffer problem is also known as Producer-Consumer problem is one of the classic

problems of synchronization
q There is a buffer of n slots and each is capable of storing one unit of data.
q There are two processes running, namely, Producer and Consumer, which are operating on the
buffer.
Producer
Buffer of n slots
q The producer tries to insert a data into an empty clot of a buffer. Consumer
q The consumer tries to remove data from a filled slot in the buffer.
q The producer must not insert data when the buffer is full.
q The consumer must not remove data when the buffer is empty.
q The producer and consumer should not insert and remove data simultaneously.
Solution to Bounded Buffer Problem using Semaphores
q Three semaphores are used.

1. m (mutex), a binary semaphore which is used to acquire and release the lock
2. empty, a counting semaphore whose initial value is the number of slots in the
buffer, since initially all slots are empty. (no. of empty slots in the buffer)
3. full, a counting semaphore whose initial value is 0. (initially buffer=EMPTY)
q do-while loop
q Inside the do: wait operation on empty semaphore – wait until empty > 0 and then
decrement empty.
Structure of a producer process

PROCESS
SYNCHRONIZATION
UNIT – 2
Lecture – 20
Classical Problems of Synchronization

I. The Bounded-Buffer problem
q Bounded-buffer problem is also known as producer-consumer problem is one of the classic problems of
synchronization
q There is a buffer of n slots and each is capable of storing one unit of data.
q There are two processes running, namely, producer and consumer, which are operating on the buffer.
Producer
! 85& +*"%#3&* 4*.&/ 4" .$/&*4 0 %040 .$4" 0$ &-+46 /,"4 ") 0 (#))&*: Buffer of n slots
Consumer
q The consumer tries to remove data from a filled slot in the buffer.
q The producer must not insert data when the buffer is full.
q The consumer must not remove data when the buffer is empty.
q The producer and consumer should not insert and remove data simultaneously.
Solution To Bounded Buffer Problem Using
Semaphores
q Three semaphores are used.
1. M (mutex), a binary semaphore which is used to acquire and release the lock
2. Empty, a counting semaphore whose initial value is the number of slots in the
buffer, since initially all slots are empty. (No. Of empty slots in the buffer)
1. Full, a counting semaphore whose initial value is 0. (Initially buffer=empty)
Producer process:
q There is a do-while loop. Inside the do: wait operation on empty semaphore – wait until empty > 0 and
then decrement empty.
q When a producer wants to produce something it has to check whether there are any empty slots, if there
are empty slots it can insert data to the buffer.
q After writing data, it will decrement empty by one, to notify that one of the empty slot is filled.
q Wait (empty) operation will decrement semaphore and signal will increment semaphore.
Solution to bounded buffer problem using
semaphores
q Wait (mutex) – mutex is a binary semaphore and is for acquiring the lock
q Mutex semaphore is shared between producer and consumer.

q If producer acquire the lock, then consumer may not be able to make any changes to the buffer, unless the
producer releases the lock. Then actual addition of data to the buffer happens.
q After it is done, it will signal (mutex). That means it will release the lock. Now, the producer signals the
consumer that the mutex is free and if consumer want, it can acquire the buffer and make changes to it.
q It will then signal (full) – it will increment the full semaphore. Signal will have increment operation.
q It is incrementing full, because the producer has now added one data into the buffer and the full variable
has to be increased.
Solution to bounded buffer problem using
semaphores
Consumer process:
q There is a do-while loop and if a consumer process wants to read or consume any data from the buffer; it will
perform the wait operation on the full semaphore.
q It means wait until full>0; means if there are at least one data in the buffer then only consumer can read or
consume the data and then decrement full.
q After the consumer consumes one data, the full semaphore has to be decremented by one.
q Next is wait operation on mutex, which is a binary semaphore. The consumer will be acquire the lock and the
producer won’t be able to disturb the buffer at that time, until consumer frees the mutex lock. Because mutex is
shared between producer and consumer.
q After acquiring the lock, the consumer removes the data from the buffer.
q After data is removed, it will signal (mutex) – it will release the lock.
q Signal (empty) - it will increment empty slots
Structure of a consumer process

readers writers
II. The Readers –Writers Problem

q A database is to be shared among several concurrent processes
q Some of the processes may want to only to read the database (readers), whereas others may want to
update (read and write) the database (writers).
W-R
R-W
W-W
R-R
q Obviously, if two readers access the shared data simultaneously, no adverse affects will result.
q However, of a writer and some other processes access the database simultaneously chaos may result.
q To ensure that these difficulties do not arise, we require that the writers have exclusive access to the
shared database.
q This synchronization problem is referred to as the readers-writers problem.
Solution to the readers-writers problem using
semaphores
Mutex=1, initially. If writer want to write something and reader

wants to read some data, only one application will get the lock and
will run its critical section.
Multiple reader scenario
Mutex =1, initially. When reader1 calls the wait(mutex), mutex value will be decrement to 0.
When reader 2 or 3 tries to call wait(mutex), mutex will become negative. And they need to
wait. So, this solution is not allowing multiple reader to reader simultaneously.
Solution to the readers-writers problem using
semaphores
qThe readers–writers problem is generalized to provide reader–writer locks on some systems.
q Acquiring a reader–writer lock requires specifying the mode of the lock: either read or write
access.
qWhen a process wishes only to read shared data, it requests the reader–writer lock in read mode.
q A process wishing to modify the shared data must request the lock in write mode.
q Multiple processes are permitted to concurrently acquire a reader-writer lock in read mode, but
only one process may acquire the lock.
qFor writing, an exclusive access is required for writers.
III. The Dining Philosophers Problem P0
F1 F0
• One of the classical problems of synchronization P1
• There few philosophers (in this case 5) sitting around a round table.
rice P4
F2 F4
• The philosopher can be in any of the two states:
• Thinking state F3 P3
P2
• Eating state
• When philosophers are thinking they don’t interact with their colleagues. They mind their own business and
do not interact with others.
• When they are hungry they eat the rice that is available in the plate.
• When they want to eat the food, they have to use the forks/chopsticks that are placed adjacent to them.
• When a philosopher wants to eat he needs two forks, not just one.
• When he is eating no one can disturb him or take away the fork from him.
• Once he finishes eating, he will keep the forks back at respective places.
The Dining Philosophers Problem
Philosopher
Thinks Eats
What is the problem??

When a philosopher gets hungry, he
When a philosopher thinks, he
tries to pick uo two forks that are closest qThe forks are limited.
does not interact with his
to him (left & right). A philosopher may
colleagues There are 5 philosophers
pick up only one fork at a time.
and 5 forks.
One cannot pick up a fork that is already qSo we need to ensure
im the hand of a neighbour. that no to philosophers
who are adjacent to each
When the hungry philosopher has both
his forks at the same time, he eats other should not eat at
without releasing his forks. When he has the same time.
finished eating, he puts down both of his
forks and starts thinking again
Significance of Problem
Ø WHY ARE WE DISCUSSING THIS PROBLEM AND TRYING TO SOLVE IT?

Ø This is a problem in operating system with deals with resource allocation
Ø The philosophers represents processes and forks represents the resources that are
to be shared among processes.
Ø Since there are limited resources and that has to be shared with all the processes
in a synchronized manner, without violating the rules.
Ø So there may be resources, that can be used only by one process at a time,
meanwhile the other processes need to wait, otherwise it may lead to problems in
operating systems.
Solution to Dining Philosophers Problem using
Semaphores
Ø One simple solution is to represent each fork with semaphore
Ø A philosopher tries to grab a fork by executing a wait() operation on that semaphore.
Ø He releases his fork by executing the signal() operation on the appropriate semaphores.
Ø Thus, the shared data are: semaphore fork[5], where all the elements of forks are initialized to
1.
Ø Semaphore is a binary semaphore, each of the semaphore can have a value either 1/0
Ø In binary semaphore, when its value is initialized to 1, it means it is FREE and 0, means it is
currently being held by some other process and NOT FREE.
Structure Of Philosopher
Ø When a philosopher wants to eat his food, he need to get hold of the two
forks/chopsticks which are adjacent to him.
Structure of philosopher i
Ø How he will do that?
Ø We assume that these chopsticks are semaphores. So, he will have to run a wait on two chopsticks
which are adjacent to him.
Ø So, for philosopher 0, he need to run wait(chopstick 0) and wait(chopstick 1 % 5) and so on.
Ø But for philosopher 5 (P4), it will be chopstick 4 & 5, but there is no chopstick 5.
Ø So, after 4, it should be 1 again. That’s why we are using mod 5 here. When i=4 (F4), i+1=5, (5mod5)
=0 (F0).
Ø So, philosopher needs to run wait operation on two adjacent chopsticks that are placed near him.
Ø Once, he get hold of two of chopsticks, he can start eating.
Structure Of Philosopher
Ø After eating he has to place the chopstick back where they were, so that other philosophers can
make use of it.
Ø He has to use the signal operations on those two chopsticks and free them
Ø Then start thinking
Ø Although this solution guarantee that no two neighbors are eating simultaneously, it could still
create a deadlock.
Ø Suppose that all 5 philosophers become hungry simultaneously and each grabs their left fork. All
the elements of fork will now be equal to 0. (all elements of fork are initialized to 1)
Ø When each philosopher tries to grab his right fork, he will be delayed forever – DEADLOCK!!
Remedies to Avoid Deadlocks
1. Allow at most 4 philosophers to be sitting simultaneously at the table

2. Allow a philosopher to pick up his forks only if both forks are available (to
do this he must pick them up in a critical section)
3. Use an asymmetric solution, that is an odd philosopher picks up first his
left fork and then his right fork, where as an even philosopher picks up his
right fork and his left fork.
Monitors
• There are some limitations of semaphores such as: timing errors and deadlock.
• Another method to solve process synchronization problem is called as monitors.
• It is a high level abstraction that provides a convenient and effective mechanism for process
synchronization.
• A monitor type presents a set of programmer-defined operations that provide mutual
exclusion within the monitor.
• The monitor type also contains the declaration of variables whose values define the state of
an instance of that type, along with the bodies of procedures or functions that operate on
those variables.
Syntax of Monitor
• The data type is monitor, because it is an abstract type
• Functions P1, P2…Pn are operations that can be performed upon these shared variables.
• Finally, there is an initialization code, where we initialize the variables.
• In monitors, the shared variables itself are declared inside the monitor and functions will be making
changes to the share variables as and when required.
• A procedure (function) defined within a monitor can access only those variables declared locally
within the monitor and its formal parameters.
• Similarly, the local variables of a monitor can be accesses by only the local procedures.
• The monitor construct ensure that only one process at a time can be active within the monitor.
Monitors
• The extra thing that we need to define in monitors is:
• Condition construct: condition x,y;
• The only operations that can be invoked on a condition variable are wait() and signal()
• The operation x.wait(): means that the process invoking this operation is suspended until another
process invokes x.signal();
• Let’s assume there is a shared variable x, and one of the process wants to use x. That process will put
x.wait() and if there is some other process that is making use of the x variable, then this process will
have to wait. And it will be keep on waiting until and unless another process invokes the x.signal()
operation. x.signal() is used for releasing the shared resource.
• The x.signal() operation resumes exactly one waiting process.

Monitors monitor
• Shared data are defined which will be shared between different processes.
• Operations are the functions(procedures) Schematic diagram of a monitor
• Procedures are the functions that will take of the operations that will be performed over the shared data.
• Then there is initialization code, that will initialize the variables that we will use.
• There is an entry queue, where processes are waiting to make use of the monitors in order to use the shared
data.
• Within the monitors itself, there are queues associated with x and y conditions.
• In the case of semaphore, we had only a semaphore variable, which was modified by different processes.
Each of the process has to be defined in such a way that it will correctly execute in the way it is expected. If
there were some problems in these definition, it would lead to deadlock and other errors.
• In case of monitors, since all the functions and operations are done within the monitor itself, the process
doesn’t have to worry about that too much as in the case of semaphores.
PROCESS SYNCHRONIZATION
UNIT – 2
Lecture 21
DEADLOCKS
Deadlocks
q In a multiprogramming environment, several process may compete for a finite number of
resources.
q A process requests resources, and if the resources are not available at that time, the process
enters a waiting state.
! Sometimes, the waiting process is never again able to change state, because the resources
has requested are held by other waiting processes.
q This situation is called a deadlock.
System Model
q A system consists of a finite number of resources to be distributed among a
number of competing processes.
q The resources are partitioned into several types, each consisting of some
number of identical instances.
Memory space CPU cycles Files I/O devices
Example of resource type Printers DVD drivers

Sequence of Utilizing the Resource
q 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 (if 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 ( eg. If the resource is a
printer, the process can print on the printer)
3. Release The process releases the resource.
An Example-Deadlock
Process P1 Process P2 Process P3 Process P1 Process P2 Process P3
Deadlock
Process P1 Process P2 Process P1 Process P2
Deadlock
Deadlock Characterization
q Features that characterize deadlocks and the conditions must hold for a deadlock to occur.
q In a deadlock, processes never finish executing and system resources are tied up, preventing
other jobs from starting.
q Features that characterize deadlocks – Necessary conditions
q A deadlock situation can arise if the following four condition hold simultaneously in a
system.
1. Mutual Exclusion
§ At least one resource must be held in a non-sharable mode, that is only one process at a time can use
the resource.
§ If another process requests that resource, the requesting process must be delayed until the resource has
been released.
Deadlock Characterization
2. Hold and wait
§ A process must be holding at least one resource and waiting to acquire additional resources that are
currently being held by other processes.
3. No preemption
§ Resources cannot be preempted, that is, a resource can be released only voluntarily by the process
holding it, after that process has completed its task.
4. Circular wait
§ A set {P0, P1, P2…Pn} of waiting processes must exist such that P0 is waiting for a resource held by
P1, P1 is waiting for P2 and so on.
We emphasis that all four conditions must hold for a deadlock to occur.
The circular wait condition implies the hold and wait condition. All the 4 conditions are
not completely independent.
Methods for Handling Deadlocks
q We can deal with the deadlock problem in one of three ways:

1. We can use a protocol to prevent or avoid deadlocks, ensuring that the
system will never enter a deadlock state
2. We can allow the system to enter a deadlock state, detect it and recover.
3. We can ignore the problem all together and pretend that deadlocks
never occur in the system.
q To ensure that deadlocks never occur, the system can use either
a deadlock prevention or a deadlock avoidance scheme
Provides a set of methods for ensuring that at least Requires that the OS be given in advance
one of the necessary conditions cannot hold: additional information concerning which resources
1. Mutual exclusion 2. Hold and wait a process will request and use during its lifetime.
3. No preemption 4. Circular wait
With the additional knowledge, it can decide for
each request whether or not the process should
wait.
q If a system does not employ either a deadlock-prevention or deadlock avoidance algorithm, then
a deadlock situation may arise.
q In this environment, the system can provide an algorithm that examines the state of the system
to determine whether a deadlock has occurred and an algorithm to recover from the deadlock (if
a deadlock has indeed occurred)
! If the system either ensure that a deadlock will never occur nor provides a mechanism for
deadlock detection and recovery, then we may arrive at a situation where the system is in a
deadlocked state yet has no way of recognizing what has happened.
In this case, the undetected deadlock will result in deterioration of the system’s performance,
because resources are being held by processes that cannot run and because more and more
processes as they make requests for resources, will enter a deadlock state.
q Eventually, the system will stop functioning and will need to be restarted manually.
PROCESS SYNCHRONIZATION
UNIT – 2
Lecture 22
DEADLOCK – AVOIDANCE, DETECTION,
PREVENTION AND RECOVERY
Resource Allocation Graph
vResource-allocation-graph is a pictorial representation of processes and resources and

how processes are holding resources and how resources are allocated to processes.
vUsing this graph we can identify whether there is a deadlock in the system.
vDeadlocks can be described more precisely in terms of a directed graph called system
resource-allocation graph.
vHow to form a resource allocation graph and how to read it and identify whether there
is a deadlock in the system?
vThis graph consists of a set of vertices V and a set of edges E.
The set of vertices V is partitioned into two different types of nodes:
vP = {P1, P2…..Pn}, the set consisting if all the active processes in the system
vR = {R1, R2…..Rn}, the set consisting of all resource types in the system.
Resource Allocation Graph
v There are two types of edges:

Request Edge
vA directed edge from processes Pi to resource type, Rj, PiàRj signifies that process Pi
has requested an instance of resource type Rj, and is currently waiting for that
resource.
Assignment Edge
vA directed edge from resource type Rj, to process Pi, Rjà Pi signifies that an instance
of resource type Rj, has been allocated to process Pi.
v How to draw a RAL
- processes are represented using circle
- resources are denoted using rectangles. Since a resource type Rj, may have more than
one instance, we represent each such instance as a dot within the rectangle.
Resource Allocation Graph – Example-1
v The sets of P, R and £:
v P = {P1, P2, P3}
v R = {R1, R2, R3, R4}
v £ = {P1àR1, P2àR3, R1àP2, R2à P2, R2àP1, R3àP3}
v Resource instances:
v One instance of R1
v Two instances of R2
v One instance of R3
v Three instances of R4
v If the graph contains no cycle, then no process in the system is deadlocked.
Fig. 1 Fig. 2
v If the graph does contain a cycle, then a deadlock may exist.
v In Fig. 2, two minimal cycles exist in the system:
v P1àR1àP2àR3àP3àR2àP1
v P2àR3àP3àR2àP2
v Processes P1, P2 and P3 are deadlocked.
Resource Allocation Graph – Example-2
v P1àR1àP3àR2àP1
v We have a cycle here.
v However there is no deadlock
v Observe that P4 may release its instance of R2. That resource can then be
allocated to P3, breaking the cycle.
v Cycle is a necessary condition for deadlock, not sufficient condition. Because if
there is a cycle in the system it does mean that there will be a deadlock for
sure. Because, resources may have multiple instances and the cycle could be
broken.
v If there is only single instances of resources, and there exist a cycle in the
system, it will result in deadlock.
v If a RAG does not have a cycle, then the system is not in a deadlock state.
Deadlock Avoidance
rag
Resource-Allocation-Graph Algorithm
v How this algorithm can be used to avoid deadlocks?

v In RAG algorithm, in addition to the request and assignment edges,
we introduce a new type of edge, called a claim edge.
v A claim edge PiàRj indicates that process Pi, may request resource
Rj, at some time in the future.
v It resembles a request edge in direction but is represented in the
graph by a dashed line.
v When process Pi requests resource Rj, the claim edge PiàRj is
converted to a request edge.
v Similarly, when a resource Rj is released by Pi, the assignment edge
RjàPi is reconverted to a claim edge PiàRj.
Deadlock Avoidance
! >0" &"#$%&'"# 9%#+ ;" '*),9"3 /&,$& ,- +0" #7#+"95 >0)+ ,#G ;"2$&" /&$'"## C,
#+)&+# "K"'%+,-.G )** ,+# '*),9 "3."# 9%#+ )*&")37 )//")& ,- +0" !LM5
v Suppose that process Pi requests resource Rj. The request can be granted only if
converting the request edge PiàRj to an assignment edge RjàPi does not result
in the formation of a cycle in the RAG.
v Note that we check for safety by using a cycle-detection algorithm.
v If no cycle exists, then the allocation of the resources will leave the system in a
safe state.
v If a cycle is found, then the allocation will put the system in an unsafe state.
Deadlock Avoidance
Unsafe State
By using a RAG algorithm, we should not allow the assignment of R2 to P2. Thus, we can make sure that the
Deadlock is avoided. Because, by the RAG algorithm, the process could claim, and if we allow one of the
claim edges to converted to a request edge, there is a possibility of deadlock to occur, the request by the
process will not be granted. So, if we know what are the claims from each processes, then see that which of
the requests could be granted and then which should not be granted and when should a process wait even if
the request is made then, we can avoid the deadlock. So by checking the claims, we check whether there
is a cycle to occur and can be avoided.
Important- RAG algorithm can be used only in systems where, there is a single instance of a resource.
Deadlock Avoidance – Banker’s Algorithm
v An algorithm that can be used for deadlock avoidance in resource allocation

systems with multiple instanced of each resource type.
v It is given the name Banker’s algorithm because the algorithm could be used in a
banking system to ensure that the bank never allocated its available cash in such a
way that it could no longer satisfy the needs of all its customers.
v This algorithm can be used in banking systems.
v The same is applied in OS, where; the resources could not be allocated in such a
way that the needs of the processes cannot be met.
v So we need to allocate the resources in such a way that the needs of the processes
can always be met and will never lead to a deadlock.
Banker’s Algorithm
v Some data structures that are used to implement the banker's algorithm are:
vAvailable
vMax Allocation Max Available
vAllocation
vNeed
v Consider the system with 5 processes: P0, P1, P2, P3, P4 and A B C A B C A B C
3 resources: A, B, C. P0 0 1 0 7 5 3 3 3 2
vThe following snapshot of the system is given. P1 2 0 0 3 2 2
vFind the needy matrix.
P2 3 0 2 9 0 2
vIs the system in a safe state?
P3 2 1 1 2 2 2
vIf yes, find the safe sequence.
P4 0 0 2 4 3 3
Need Matrix
v Need matrix = Max – Allocation NEED MATRIX
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Safety Algorithm
vIf need <= available

vThen Execute process
vNew available = Available + Allocation
vElse do not execute, GO FORWARD
vFor P0:
vneed = <7, 4,3> and available = <3, 3,2>
vHence, need NOT<= available,
vDO NOT EXECUTE P0, go forward with P1
vFor P1:
!4%%"Q R?1@1AT 64" 6>6#86;8% Q R@1 @1 AT
!C%4&%1 4%%" RQ 6>6#86;8%1 WXWHYGW .?
!U%9 6>6#86;8% Q 6>6#86;8% Z 688*&6'#*4 Q R@ZAQ[1 @ZOQ@1 AZOQAT
Safety Algorithm
vFor P2:
vneed = <6,0,0> and available = <5,3,2>
vHence, need > available,
vDO NOT EXECUTE P2, go forward with P3
vFor P3:
vneed= <0,1,1> and available = <5, 3, 2>
vHence, need <= available, EXECUTE P3
vNew available = available + allocation = <5+2=7, 3+1=4, 2+1=3>
vFor P4:
vneed= <4,3,1> and available = <7,4,3>
Safety Algorithm
vNow, check for all NOT EXECUTED processes

vFor P0:
vFor P2:
Safe Sequence
v <P1, P3, P4, P0, P2>

Deadlock Detection
Wait-For-Graph (Single Instance Resources)
vSingle instance of each resource type
vIn systems where each resources have only a single instance, we can use Wait-
For-Graph which is an algorithm for deadlock detection and is a variant of the
RAG.
vP3 is waiting for R1, whereas R1 is allocated to P1.
vP2 is waiting for R2, whereas R2 is allocated to P1.
vThus, P3 is waiting for P1 and P2 is also waiting for P1.
vThus, if all the resources have single instances and cycle is being formed, then the
system is in DEADLOCK.
vIf cycle is there, but resources have more than one instance, then the deadlock may
or may not be present.
Deadlock Detection
Wait-For-Graph (Single Instance Resources)
DEAD LOCK!!
Recovery from Deadlock – Process Termination
vWhat to do when a deadlock detection algorithm determines that a

deadlock exist?
vPossibility-1: Inform the operator that a deadlock has occurred and let the
operator deal with the deadlock manually.
vPossibility- 2: Let the system recover from the deadlock automatically. What
are the methods that the system can follow once a deadlock is detected.
vHow to break from the deadlock?
vOption-1: Abort one or more processes to break the circular wait.
vOption-2:Preempt some resources from one or more of the deadlocked
processes.
Process Termination
vTo eliminate deadlocks by aborting a process, we use one of two methods:

vAbort all deadlocked processes
vAbort one process at a time until the deadlock cycle is eliminated
vAborting a process may not be easy – We should abort those processes whose
termination will incur the minimum cost.
vFactors that affect which process are chosen to be aborted:
!!"#$ $"% &'()'($* )+ $"% &'),%--
!.)/ 0)12 $"% &'),%-- "#- ,)3&4$%5 #15 ")/ 34," 0)12%' $"% &'),%-- /(00 ,)3&4$% 6%+)'%
,)3&0%$(12 ($- 5%-(21#$%5 $#-78
vHow many and what type of resources the process has used
vHow many more resources the process needs in order to complete
vHow many processes will need to be terminated
vWhether the process is interactive or batch
Recovery from Deadlock – Resource Preemption
v Here we successively preempt some resources from processes and give these
resources to other processes until the deadlock cycle is broken.
v If preemption is required to deal with deadlocks, then three issues need to be
addressed:
v Selecting a victim
v which resources and which processes are to be preempted?
v minimize cost
v Rollback
v what should be done with a process if we preempt its resources?
v we must roll back the process to some safe state and restart it from that state
v Starvation
v how do we ensure that starvation will not occur?
v how can we guarantee that resources will not always be preempted from the same process?
Deadlock Prevention
• Linear ordering *'& +,%,"- &$+'.&-$+

• /$+'.&-$+ ,' 0$ %--$++$( %&$ 1#'2# "# %(3%#-$
• 4&($&"#) %--$++$+ 05 ,"6$+,%67+
Lecture 23
INTRODUCTION TO
MEMORY MANAGEMENT
2
Memory Management in OS
◦ It is a kind of method or it is a kind of functionality to manage the various kinds of
memories.
◦ Eg. If we take our laptops, there are different kinds of memories such as: RAM, disk,
registers etc. So, memory management deals with how can we manage the different
memory units in a more efficient manner. This is the functionality of the OS.
◦ So, it is a method of managing the primary memory.
◦ Out of the majority of memory units, the majority isRAM.
Registers RAM
CPU (Primary Secondary
Cache memory) memory
2
Main Memory
◦ CPU will execute each instruction one by one and CPU is connected with registers, cache and
RAM. There is a direct connection.
◦ But the secondary memory is not directly connected with the CPU. The reason is SPEED.
◦ Secondary memory is very slow and CPU is very fast. So, we can’t connect them directly.
◦ So, we connect fast memories like register, cache and RAM.
◦ There is a limited size of registers, cache and RAM.
◦ If we increase the size of RAM, or registers or cache, then it will directly increase the cost of the system.
◦ So, all the programs are stored in secondary memory, which need to be executed.
◦ How CPU will execute all these programs lying in the secondary memory?
◦ So, all the user written programs are sitting idle in the secondary memory.
◦ For running programs in CPU, the program needs to be brought into RAM, the main memory, so
that CPU can directly interact with the processes and it can be executed.
◦ Registers and cache are very fast but they are very small in size.
3
P0
Main Memory CPU

RAM
(Primary
memory)
P1
Secondary
memory P2
P3
P4
qLets consider that the CPU communicate with the primary memory directly
and the programs/processes in the secondary memory needs to be swapped
or brought into the primary memory for executing in the CPU.
qThis is referred as degree of multiprogramming. Because, when we push the
programs from the secondary memory to the primary memory (RAM), we
need to bring as many programs as possible so that CPU can execute all of
them resulting in increased CPU utilization.
4
Memory Organization
◦ Memory is central to the operation of a modern computer system
◦ Memory consists of a large array of bytes, each with its own address.
◦ The CPU fetches instructions from memory according to the value of the program
counter.
◦ A typical instruction-execution cycle, for example, first fetches an instruction from
memory.
◦ The instruction is then decoded and may cause operands to be fetched from memory.
◦ After the instruction has been executed on the operands, results may be stored back in
memory.
◦ The memory unit sees only a stream of memory addresses; it does not know how they are
generated or what they are for.
◦ To have fast memory between the CPU and main memory, cachememoryis added.
5
Swapping
◦ A process can be swapped temporarily out of memory to a backing store, and then brought back
into memory for continued execution.
◦ Swapping makes it possible for the total physical address space of all processes to exceed the real
physical memory of the system, thus increasing the degree of multiprogramming in a system.
◦ Swapping requires a backing store
◦ Backing store
◦ It is a fast disk
◦ Should be large enough to accommodate copies of all memory images for all users
◦ Must provide direct access to these memory images
◦ Roll-in, Roll-out
◦ When a higher priority process arrives, a lower priority process is swapped out, and then
swapped back in, when the higher priority process finishes
◦ Major part of swap time if transfer time
◦ Totaltransfer time is directly proportional to the amount of memory swapped. 6
Swapping
◦ The system has a ready queue with all processes whose memory images are on the
backing store or in memory and ready to run
◦ The CPU scheduler calls the dispatcher before running a
process
◦ The dispatcher checks if the next process in queue is in primary
memory
◦ If not, and if there is no free region, the dispatcher swaps out a
process currently in primary memory and
swaps in the desired one from backing store.
◦ It then reloads registers and transfers control to the process
◦ The context switch time in such a swapping system is fairly high
◦ If we want to swap a process, it must be completely idle
Schematic view of swapping 8
Memory Management Techniques
◦ Operating system uses various memory management methods to manage the primary
memory (RAM).
◦ Memory is a large area of bytes and every byte is having an address.
◦ We are trying to divide the memory or partition the memory and to keep maximum
number of processes in RAM.
◦ Also, more number of processes should be in ready state, so that these processes can be
changed to execute state by assigning it to the CPU, and also have plenty of ready
processes if a process does an I/O operation (file operations, using hardware devices,
display etc.), not idling the CPU.
◦ The main memory must accommodate both the operating system and the various user
processes.
◦ We therefore need to allocate main memory in the most efficient way possible.
8
Memory Management Techniques - Types
Fixed Partitioning
(static)
Contiguous
Variable Partitioning
Memory (dynamic)
management
techniques
Non-contiguous Paging
Multilevel Paging
Inverted Paging
Segmentation
Segmented Paging
9
OS OS
Memory Management Types P1
P2
P1
P3 P4
P4 P2
P5 P3
◦ Basically there are two types: contiguous and non-contiguous.
Contiguous Non-contiguous
◦ Contiguous memory allocation is further divided into static and dynamic allocation.
◦ Basically, the memory is divided into two partitions: one for the resident OS and one for the user
processes.
◦ We want several user processes to be present in the main memory
◦ In contiguous memory allocation, each process is allocated to the memory addresses continuously.
◦ Fixed portioning is used long back, in main frame systems.
◦ In non-contiguous memory allocation, the processes are not allocated in continuous addresses,
rather they are in different addresses.
10
Fixed Partioning (Static)
OS OS
◦ In fixed portioning, the number of partions are fixed
P1 4MB P1 8MB
◦ When ever a system is started, the OS is mounted in the
P2 8MB P2 8MB
RAM
P3 8MB P3 8MB
P4 16MB P4 8MB
◦ In memory allocation, we want to allocate more user processes in RAM, before that the number of partitions are fixed in the memory.
◦ The time when the system is configured, that time itself, the number of partions are fixed.
◦ Size of each partition may be same or different.
◦ In contiguous allocation, sparing is not allowed.
◦ Sparing means, when a process needs to be allocated to the memory, it will be assigned to a particular partition. In case, it is not possible to be
allocated within a partition, then it cannot be allocated to any other partition.
◦ Disadvantages:
◦ Eg. In case there is a 2MB process; then the process will be assigned to the 4MB partition in Fig.1 and the rest 2MB memory will be wasted.
This is called as internal fragmentation.
◦ In case a process of size 32MB is there, then it cannot be allocated to any partition – there is a limit in the process size.
◦ Here the no. of partitions are fixed (4) , if we have 5 or more than 4 processes, we can’t bring that to main memory – limitation on degree of
multi programming
◦ Externalfragmentation
11
OS
2MB P1
Variable Partitioning 4MB

8MB
◦ In variable partitioning, whenever the processes are admitted to the RAM, only then we are allocating the sp ace
P2
P3
the processes. to P4
4MB
◦ RAM is kept free initially, when processes are executed, at run-time based on the capacity of each processes,
memory is allocated dynamically.
◦ If P1 size is 2MB, so we allocate 2MB of RAM to P1. If P2 = 4MB, again 4MB of RAM is allocated to P2 and OS
so on. So, there is no wastage of memory and thus, no internal fragmentation.
P1
◦ Advantages:
◦ No internal fragmentation.
◦ No limitation on the number of processes and thus, no limit on degree of multiprogramming
P3
◦ No limitation on the process size
◦ External fragmentation
◦ If processes P2 and P4 completes executes and terminates, then the allocated memory will be made free and a hole
will be created. Now, if a new process P5 enters, the system whose size is 8MB, which cannot be allocated now, then
the process will wait. This is called as external fragmentation. (although we have required memory size
available, it cannot be allocated to a process, because it is not contiguous)
◦ Solution is – compaction. Separate the used and unused memory spaces are separated (copy-paste) – undesirable
◦ - Allocation / deallocation – is complex as compared to fixed partitioning
13
Allocation Methods in Contiguous Memory
Management P10
◦ There are 4 algorithms used to how memory is allocated to different processes. 25K P1
◦ There are already processes in the memory and there are holes available. Now we have to identify how processes P11
can be allocated to the available holes. P3
40K
◦ First-fit allocation (simple & fast, most convenient) P12
◦ Allocate the first hole, that is BIG enough (P1=15K, check the first location which is big enough to hold 15K). It is easy
and not time consuming as it is allocating processes in the first search itself 20K
◦ Next-fit allocation (faster)
◦ Same as first-fit; start search always from last allocated hole. (P2=18K, start searching from P1 location and find the
next suitable hole.
◦ Best-fit allocation (less internal fragmentation, but slow)

◦ Search the entire list and it will try to search that hole, which will lead to minimum internal fragmentation.
(P1=15K, by best-fit it will not be allocated to 25K or 40K, instead the entire list will be search and the best-fit is 20K,
because the left over space is only 5K)
◦ Worst-fit allocation (further more processes can be added to the left over space, but slow)
◦ Allocate to the largest hole. (P1 will be allocated to 40K, where the left over space is max.) 14
Fragmentation Memory fragmentation can be internal or external
15
Segmentation – Non contiguous Memory
d
•MMU will help to convert logical BA Size
Logical
address to physical address. 0 add. d 0 OS For segment S5-
3300 200 BA
•This conversion is done with compared 1500 1500 is base
the help of segmenttable. 1 1800 400 with size S5 address
d≤size Yes 1800
•Segment table will help to fetch a 2 2700 600 ≤ + 2200
S1 And size of
S5=300
data from the phy. memory S4
3 2300 400
2300
Segment Segment 2200 100 S3
no. (S) size (d) 4 No 2700
Logical address. 1500 300 S2
5 3300
00001(S1) 10000 Trap S0
Segment Table 3500
CPU generates LA
Main memory
16
OS
Non – Contiguous Memory Allocation 2KB P1

1KB
2KB P1
◦ In con-contiguous memory allocation different processes are allocated to the main memory in 1KB
non-consecutive manner. 2KB P1
◦ In contiguous memory allocation, a process cannot spare between different memory locations. Main memory
◦ In non-contiguous memory allocation, sparing is supported. Ie, one process can be divided and
allocated to different memory locations. P1
◦ If we have a process P1 of 6KB size, cannot be put into main memory with the available free space
by contiguous memory allocation.
◦ But, in non-contiguous allocation, the process P1 can be divided into 3 partitions of 2KB each and
can be allocated to main memory. Thus, removing external fragmentation. Here, partitions are 6KB
made based on the available hole sizes.
◦ But, portioning is a costly method. Because holes are created dynamically and it changes at run-
time.
17
Segmentation Vs Paging
◦ Now, if a new process P2 arrives of size 2KB. This process want to occupy the main memory, then it will check the
holes in the memory and its sizes. It will find that there are 2 holes of 1KB each. Then, the process will be divided
into 2 partitions of 1KB size each.
◦ But, there are difficulties as holes are created dynamically and its number and size keep changing at run-time. Every
time, when a process tries to occupy the space in memory, it has to analyze the holes and size and location. Bases on
this, the process needs to be partitioned and thus, it is a time consuming job.
◦ So, the alternate to this is, before we bring a process into the main memory, we divide the process into partitions and
each partition is called a PAGE. This partitioning is done in the secondary memory itself.
◦ At the same time, we divide the main memory also into partitions. These partitions in the main memory is called as Main memory
FRAMES. OS
◦ In this case, the size of the page will always be equal to the size of the frame. Frame 0
◦
Page Size = Frame Size Page 0
Frame 1
◦ Here, external fragmentation is completely avoided. Page 1
Page 2
Frame 2
P1
18
Need of Paging
◦ Eg. RAM of 8KB, frame size is 1KB.
◦ Then., there will be 8 frames.
Frame OS
◦ Let the process P1 be of size 2KB. Process need to be divided into pages of size=frame size=1KB P1
0
◦ Similarly, if there processes P2 (2KB), P3(2KB), P4(2KB) are available, then each process pages P1
1
can be allocated to frames in main memory. 2 P2
◦ Later, of P2 and P4 finished its execution and completes. Then, 4 holes of 1KB size will be created 3 P2
4 P3
◦ If now, a process P5 of size 4KB arrives, we divide it into pages of size 1KB, so totally 4 pages.
5 P3
◦ In non-contiguous allocation we can allocate these 4 pages into frames 2, 3, 6 and 7.
6 P4
◦ Thus, in conclusion in paging, we divide each process before allocating to the main memory into pages. P4
7
The size of the page is decided by the size of the frames in main memory. Here, pages of process will
exactly fit in frames of main memory, thus removing external fragmentation completely. This is the
reason of using paging.
19
Paging
Frame No. Bytes
0 0 1
1 2 3
◦ In paging, the process is divided into equal size pages and stored in the main memory frames. 2 40 15 P0
◦ Lets assume we have a process P1 of size 4 Byte and page size if 2 Byte.
3 6 7
◦ Therefore, the number of pages = 4/2 = 2 pages
◦ Size of main memory = 16 Bytes 4 828 939 P1
◦ Frame size = 2 Byte Bytes 5 10 11
◦ Note: frame size and page size should always be the same.
Page No. 0 00 11
6 12 13
◦ Because, when we divide the process to save in the pages, these pages should be saved into main 1
22 33
7 14 15
Memory frames. So to fit it correctly, the page size and main memory frame size should be same.
Page table Main memory
◦ Number of frames = 16/2 = 8 frames
◦ Main memory is byte addressable.
◦ Now, when CPU is executing process P1, CPU is not aware of the frames, it only asks for a byte of data from main memory to execute P1. For eg. When CPU asks
for byte no. 3, it is mapped to the respective byte in the page but is actually available in frames of the main memory.
◦ For eg. If frames 0,1,3 and 5 are filled already, then page 0, will be stored in frame 2 and page 1 will be stored in frame 4. now, if CPU asks for byte no. 3, then byte
3 can be present in any of the frames (here, in frame 4).
◦ So, we need mapping here. The CPU when generating addresses, are not absolute addresses. So, there should be a mechanism to convert this 3 to 9 in the main
memory and fetch the data from there. The mapping is done by memory management unit. Ie, the MMU, is responsible for conversion of the address generated
by CPU, to absolute address MMU takes the help of page table. It contains frame numbers where that page is actually present in the main memory.
20
Paging Page No. 0 0 1
Bytes
1 2 3
◦ Every process has its own page tables.
◦ For P1 process, how many entries will be there in the page table? How many pages that process
has, those many entries will be there.
Page no.
◦ How is this process happening? 0 F2
◦ CPU will generate logical addresses. Logical address is generated with two things: page number 1 F4
and page offset (size of the page). Page table of
Process 1
◦ To represent page no., in this case 2, we need one bit (page0, page1)
Page no. Page offset
◦ To represent page size, in this case 2, we need one bit 1 bit 1 bit
◦ Now, CPU has generated an address: 3 (11-binary) ie. Page no-1 and page offset-1 1 1
◦ In page no-1, there are 2 bytes (0th byte and 1st byte). Logical address
21
Paging
◦ Now, the CPU generated address 3, we need to convert to 9
◦ The logical address generated by CPU need to be converted to physical address
◦ We understood what is logical address is.
◦ Now, physical address (PA) (it says where actually the byte is lying) is directed connected with the
main memory
◦ PA is related to the size of the main memory (16 bytes in this case)
◦ To represent 16 in binary, we need 4 bits. Frame no. Frame offset
3 bits 1 bit
◦ We understood that we need to go to frame no.4 from page 1, using logical address. 1001 =9
100 (4) 1
◦ Next is frame offset is 2bytes, which is same as page offset, because the 2nd position in page
Physical address
should be same as second position in frame as well.
◦ In conclusion, CPU will say the byte address, which need to be converted to logical
address and later to physical address and then read the byte from the main memory.
22
Paging – Another example
◦ CPU is asking for byte no.1
◦ 1 is represented as 01 – that means in 0th page, the 1st byte.
◦ Next we will take the page table, in page table page 0 – refers to frame no. 2. In frame 2, we need
to take the 1st byte: 5
◦ In physical address: frame no 2 is represented as 010 using 3 bits. Next is frame offset: 1. thus,
physical address is now: 0101 = 5
◦ This is how we map, logical address to physical address. For this mapping, we need page table. In
page table we have frame number. From frame number, we take the byte and give it to CPU
23
LECTURE - 24
VIRTUAL M E M O RY
2
Virtual Memory
v Virtual memory provides an illusion to the programmer that the process whose size is larger than
the size of main memory can also b e executed.
v How is it that possible?
v The size of the main memory is finite. But, there is no limitation to the size of the processes.
v In case, if the size of a process is larger than the main memory size, how can we generate the
pages and provide data to the C PU? How C P U can execute the process?
v We know that to improve the degree of multiprogramming, we need to bring more and more
processes to the main memory. But, its size, being limited, how can we bring more processes for
executing in the C PU?
v In logical address space (ie, hard disk) there are multiple processes and are divided into pages.
v In case, where a full process cannot b e brought into the main memory, we can bring the required
pages of the process for execution.
v Which pages are required at a particular time, only those pages of the process will b e brought into
the main memory – this uses the P R I N C I P L E O F L O C A L I T Y O F R E F E R E N C E
v When a particular p a ge is brought into the main memory, not only that pages, but all the related
pages of that process are also brought into the main memory.
Virtual Memory
v So, main memory will contain some p a ge s of process P1, some p a ge s of P2, etc. so, the advantage is that
the user will find multiple process for execution even though the entire process are not present in the
main memory.
v This is done with the help of swap-in and swap-out operation/roll-in or roll-out.
v Swap-in means we bring the required p ages of a process to the main memory for execution and keep it
there until the execution is complete, and then swap-out to secondary storage. Then we, will bring the
relevant p a g e s of another process to the main memory. This is called as PA G E R E P L A C E M E N T
P3
P1 P0
OS
P0 P1 P0
Page 0 of P1 Swap-in/ Roll-in
P1 P2 P1
Page table of P2
P2 P3 P2
Page 2 of P2
P3 P4 P3
Page 2 of P1 Swap-out/ Roll-out
P4 P5 P4
Page table of P1
P5 P2 P5
Page 0of P2
Logical Address S p ace
M a in M e m o r y
Virtual Memory
v Advantag es of V irtual memory:
v no limitation on the number of processes that can b e in the main memory
v no limitation to the size of the process
v Disadvantages
v Let say, C PU is executing process P1, it will demand for some data (eg. Page 1 of process P1).
Where is this p a ge lying in the main memory? With the help of p a g e table, MMU will identify
the data. But, there could b e instances, where pages are not present in the frames. This is
identified by the entry in the p a ge table called as valid/invalid bits. This bit, tells, whether that
p a g e is actually present or absent in the main memory
v So, when a p a g e that is required by the C PU for execution is not present in the main memory, it
will generate a PAGE FAULT. And TRAP will b e generated and the control will change from
Valid/invalid bit
user to O S and context switch will happen.
v W hen O S gets activated, it will check the user who dem and that p a g e F1
CPU
whether he an authenticated user or not. If the user, is an authenticated - 0
user, then O S will provide that p a g e from the hard disc. F2
- 0
Page table of P1
Demand Paging
v Demand paging is the method by which virtual memory is implemented in any O S
v In this technique, a p a g e is brought into the memory for its execution only when it is
demanded.
v It is a combination of paging and swapping.
v The demand paging requires the complete process should b e in the secondary storage area in
the form of pages.
v It is called lazy swapper method, because it swaps the p a g e only when it is n e e de d
v Advantages
v Reduces the memory requirement
v Swap time is reduced
v It increases the d e g r e e of multi programing Frames
of A
v Disadvantages
v The occurrence of p a g e fault
Frames
of B
M ain m em ory Disk

Thrashing
v Thrashing is linked with the degree of multi programming.
v In multiprogramming, as much of processes should b e brought into the main memory so that
the C P U utilization is increased.
v When the process executing in the CPU, want to do some I/O operation, then the C PU will
becom e idle and thereby reducing the throughput of the system.
v So, we need to keep the C P U busy, but there are limitations on the size of the main memory.
v This is addressed with the help of PAGING
v The degree of multiprogramming can b e increased, if only 1/2 pages of every process is
brought into the main memory. Thus, every process will feel that it is present in the main
memory, but the entire process in not present in the main memory.
v But, in worst case, if one p a ge of all processes are brough into the main memory and if C P U is
demanding for p a ge 0 of P1, in that case it is available and in case if C PU asks for p a ge 1 of P1,
PAGE FAULT will happen and there is time is required to bring the p a ge 1 of P1 from hard disk
to main memory.
v Like this, if pa ge fault happens for all the pages of various processes, then if p a g e fault
increases in the system, then THRASHING will happen.
Thrashing
v Thrashing is linked with the degree of multi programming.
v Solution to thrashing:
v Increase the size of main memory
v Using Long time scheduler – its responsibility is to keep as many processes in READY state.

Os All Merged

Uploaded by

Copyright:

Available Formats

Os All Merged

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Os All Merged

Uploaded by

Copyright:

Available Formats

INTRODUCTION

Introduction to Operating Systems

Introduction to Operating Systems 2

Introduction to Operating Systems 4

U1, U2….Un are users

Introduction to Operating Systems

and many more……..

Introduction to Operating Systems 6

q Why there is a need of an operating system?

ØEg. In order to print a document, the user need to write a program to

Introduction to Operating Systems 7

q Make the computer system convenient to use.

q Execute user programs and make solving user problems easier.

Introduction to Operating Systems 8

q Kernel (heart of OS)

Introduction to Operating Systems 9

q Why do we need an interface (OS)? Why not the user directly

Introduction to Operating Systems 10

q Kernel is the heart of OS

Introduction to Operating Systems 11

q Windows OS – Windows NT is the Kernel (more than 75% market share)

q Mac OS – XNU is the Kernel (around 19% market share)

Introduction to Operating Systems 12

q Can we have an OS without Kernel?

q Can we have Kernel without an OS?

Introduction to Operating Systems 13

Introduction to Operating Systems 14

Types of Operating Systems

Introduction to Operating Systems 2

Batch Multiprocessor Desktop Distributed Clustered Real-time Handheld

Introduction to Operating Systems 3

• There is no direct interaction between user and the computer.

• User submits his jobs to the computer operator

• The operator submits a batch of jobs to an input device of the computer

• Based on the requirements and the language, jobs are batched

• Eg. of batch based OS– Payroll systems, Bank statements etc.

Introduction to Operating Systems 4

• Consists of several processors that share a common physical memory.

Introduction to Operating Systems 6

• Personal computers – computer system dedicated to a single user.

Introduction to Operating Systems 7

Introduction to Operating Systems 8

Introduction to Operating Systems 9

• Like parallel systems, clustered systems gather together multiple CPUs to

Introduction to Operating Systems 10

Introduction to Operating Systems 11

• Personal Digital Assistants (PDAs)

Introduction to Operating Systems 12

Understand the Operations of

OPERATIONS OF OPERATING SYSTEMS 3

Ø Controllers - are responsible for how the connected devices work.

Ø A memory controller synchronize access to the memory. (memory is finite)

Ø All the connected devices to execute need to be loaded to the main

OPERATIONS OF OPERATING SYSTEMS 4

Eg. Most of modern PCs Eg. Blade servers

OPERATIONS OF OPERATING SYSTEMS 5

Multiprocessor system Multicore systems

OPERATIONS OF OPERATING SYSTEMS 6

Understand the Operations of

Asymmetric multiprocessing Symmetric multiprocessing