Operating Systems (CS3000)

Lecture – 1
(Course Overview)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Course Evaluation Components
• Mid Sem: 25 (1st week October 2024)
• End Sem : 55 (4th week November)
• Assignments : 20

2
 Course Administration (3000)
• Prior knowledge: C, Data Structures, Computer Organization and Design
• Lecture slides will be available on moodle after lecture.
• Some reading material will be provided before/after the lecture.
• Discussion Time: Anytime except when we have class or laboratory (prior email is preferable).
• Lab: Once a week (Good Learning Experience).
• Easiest way to get a good grade in CS3000 is to pay attention in the class.
• 85% attendance is mandatory.
• Total = 42 Lectures, 14 Tutorials

Time Table
CS3000 Monday –11:00 AM – 11:50 AM
Tues – 8:00 AM – 8:50 AM
L T P Credits Wed – 12:00 PM – 12:50 PM
Thurs – 09:00 AM – 09:50 AM
3 1 0 4

3
 Books & Reference Materials
1. Operating System Concepts,
8th Edition by Silberschatz
[Link].
2. Operating Systems: Internals
and Design Principles, 8th
Edition by William Stallings
3. Online Resources

4
Why Operating Systems Required?
Coordinate
Color
0
Fetch

Decode Think of our life

Execute without OS!!
Display

5
 Goal of OS
User - 1 User - 2 User - n

Compiler Game/Browser File Access

Application Program

Operating Systems Operating Systems

Computer Hardware

Goals
1 – Convenient to Use / User Friendly
2 – Efficiency

6
 Usages of Operating System

 OS Provide Abstraction  OS as a Resource Manager

 Easy to program  OS must manages CPU, memory,
 No more small details are required secondary memory(hard disk),
network, etc.
 Reusable functionality
 Different programs can use the OS
 Resource Management
functionality  Allows multiple programs to share

 Portable
resources

 OS interface are consistent. The  Protect programs from each other

program does not change when the  Improved the utilization of
hardware changes resources
 Why this Course?
• Most Essential Part of a Computer System
• A program that acts as an intermediary
• between a user of a computer and the computer hardware
• A program that is a resource manager
• Memory, CPU, I/O
• Acts like Government
• No useful function by itself
• Sets up environment for other applications to achieve their tasks
• Time/Deadline Based
• Event Driven
• Challenges in the OS design
• Tradeoffs in OS design

8
 Operating System Market Share

Source:StatCounter

9
 Types of OS (Types of Applications)
• Desktops • Mac OS, Windows, Ubuntu
• Servers • Windows Server, Redhat
• Embedded OS • Contiki OS
• Mobile OS • Android, iOS
• RTOS • RTLinux
• Secure Environment • SeLinux

10
 Course Contents
• Structure of Operating System
• Functionalities & Services of an Operating System
 Process Concept - System Calls & Management

 Process Synchronization

 Process Scheduling

 Deadlock

 Memory Management

 I/O Management

11
 Types of OS Every Job or Task has -
 CPU Time
• Batch OS  IO Time
• Transistors
• Starts another job only after the present job is completed entirely
• both CPU and IO Parts to be completed
• Poor CPU Utilization
• Low Throughput (Efficiency Aspect)
No of Jobs or Tasks completed
per unit time

12
• Stored Program Architecture
• Multiple Programs or Jobs are allowed
to be in Main Memory

13
 Types of OS
• Multi Programming OS
• Overlapped execution of CPU and IO Operations Tasks
• When CPU is idle, switch to other Job
• Better CPU Utilization – when J1 is busy on IO; J2’s CPU part is
allowed
• Betters Throughput

J1 – CPU, IO, CPU J1-CPU J2-CPU J1-CPU J2-CPU CPU

J2 – CPU, IO, CPU

• J1-IO J2-IO

14
 Types of OS
• Multi Tasking OS
• Based on the concept of Time Sharing (= 2sec)
• Time Sliced Execution of Tasks
• Illusion of Simultaneous Execution of Tasks

J1 – 4 Sec
J2 – 3 Sec J1 J2 J3 J1 J3 J2 J3
J3 – 7 Sec
0 2 4 6 8 10 11 14

15
 Types of OS
• Multi Processing OS
• More than 1 Processor
• Modern day Multicore Systems
• True Simultaneous or Parallel Processing
• High Throughput
• High Reliability – Fault Tolerant Systems
• Economical – from a user and application management view

Processor - 1 J1 J2 J3 J1 J3 J2 J3

Processor - 2 J4 J5 J6 J5 J6 J4

16
Functionalities or Services of OS
Storage Management
Process Management Operating
System File Mamagement
Process Creation, execution, Creation, deletion of files and
termination directories
Process Scheduling Manipulation of files and
Interprocess Communication directories
Thread-Scheduling Mapping files onto secondary
Synchronization of processes storage
Handling Deadlocks
Mass-Storage Management
Memory Management Free Space Management
Storage Allocation
• Keeping track of used and free
Disk Scheduling
space
• Deciding which processes and
data to move into and out of Protection and Security
memory
• Allocating and deallocating • Ensuring control access of resources
memory space
Operating Systems
(CS-3000)

Lecture-2

Dr. Jaishree Mayank

Assistant Professor
IIITDM Kancheepuram
Objective of this lecture
• Processes
• Virtual address space of a process
• Metadata about the Process
• PCB
• Kernel stack of the Process
• Page table
What is a Process?
• Program in execution is know as a process.
Virtual address space of a process
• When compiled with gcc hello.c it
creates an executable [Link].
• When [Link] is executed a process is
created. Part of this process will be in
the RAM and it is identified by a
virtual address map.
• So the virtual address map is a
sequence of contiguous addressable
memory locations starting from 0 to a
limit of MAX_SIZE.
• So, within this virtual address map we
have various aspects of the process
including the instructions, global and
static data, heap, as well as the stack
Where does the kernel reside?
• The kernel resides in the lower part of the memory starting from page
frames 1, 2, 3, and so on.

• The virtual address space or virtual address map of a process is

divided into equally sized blocks. So typically the size of each block is
4KB.
• Again there is each process would also have a process page table in
memory (Kernel space) which maps each block of the process into a
corresponding page frame.
• The RAM, as we have seen is divided into page frames of size 4 KB
similar to the block size. And these page frames contain the actual
code and data of the process which is being executed.
Kernel and multiple process
What happens when we have multiple
processes in the system?
• The kernel space is mapped identically in all virtual address spaces of every
process.
• For instance, above MAX_SIZE and below Max Limit the kernel space is present in
all processes.
• Similarly, the page table in each process also has an identical mapping between
the kernel page tables and the corresponding page frames that the kernel
occupies, as can be seen (in above mentioned slide) .
• The virtual address space of each process has different entries for the kernel.
• However all processes eventually map their kernel space into the same page
frames in the RAM. So, what this means is that, we have just a single copy of the
kernel present in the RAM.
• Thus, there can be identical entries in each processes page table corresponding
to the kernel code and data.
Metadata about the process
• Corresponds to each process, kernels keeps some metadata

• Process Control Block

• Kernel Stack for the User
Process
• Page Tables for the User Process

• Process Control Block

• Kernel Stack for the User
Process
• Page Tables for the User Process

• Process Control Block

• Kernel Stack for the User
Process
• Page Tables for the User Process
Kernel Stack for User Process
• kernel stack is used when
• the kernel executes in the context of a process.
• to store the context of a process.
• Example: when the process executes a system call (service from the OS) it
results in some kernel code executing and these kernel code would use the
kernel stack for it’s local variables as well as function calls.
• So, why do we have two separate stacks? Why do we have a user stack for
the process as well as the kernel stack?
• the kernel can execute even if the user stack is corrupted.
• For Example:- Attacks that target the stack, such as buffer overflow attack will not
affect the kernel in such a case.
Process Control Block (PCB)
• PCB is a data structure that stores information associated with each process
• Process id: (unique for each process)
• Process state :– It stores the respective state of the process.
• Process number: – Every process is assigned with a unique id known as process ID or
PID which stores the process identifier.
• Program counter; – It stores the value which contains the address of the next
instruction that is to be executed for the process.
• Register: – These are the CPU registers which includes: accumulator, base, registers
and general purpose registers.
• Memory management info:- Size of process memory ,Page Table, Memory Limit, …)
• List of opened files
• List of opened devices
• Accounting and status data – This field includes information about the amount of
CPU used, time constraints, jobs or process number, etc.
What is the use of PCB?
• Context Switching: PCBs are essential for context switching, where the
operating system saves the state of the currently running process and loads
the state of the next scheduled process. This allows multiple processes to
share the CPU effectively.
• Process Management: By maintaining all necessary information about
processes, PCBs enable efficient process creation, termination, and
scheduling to support multiprogramming.
• System Stability and Efficiency: PCBs help ensure that processes are
managed in an organized manner, contributing to the stability and
efficiency of the operating system.
Process State
• From the time process is created till it finishes, it
passes through several states.
• New
• Ready
• Running
• Wait (Block)
• Terminated (Completed)
• Suspend Ready
• Suspend Wait (Block)
 Schedule
Create Completion
New Ready Running Terminated
Priority/Time Slice

I/O Completion
I/O Request
Suspend
Resume
Block/
Wait

Suspend Suspend
Ready
Resume

Finished I/O but

still suspended Suspend
Wait/Block

14
• New: Newly Created Process (or) being-created process.
• In this step, the process is about to be created but not yet created, it is the
program which is present in secondary memory that will be picked up by OS to
create the process.
• Ready: After creation process moves to Ready state, i.e. the process is ready for
execution.
• New -> Ready to run. After the creation of a process, the process enters the
ready state i.e. the process is loaded into the main memory. The process here
is ready to run and is waiting to get the CPU time for its execution. Processes
that are ready for execution by the CPU are maintained in a queue for ready
processes called READY QUEUE.
• Running: Currently running process in CPU (only one process at a time can be
under execution in a single processor).
• The process is chosen by CPU for execution and the instructions within the
process are executed by any one of the available CPU cores.
• Wait (or Blocked): When a process requests I/O access.
• Whenever the process requests access to I/O or needs input from the user or
needs access to a critical region (the lock for which is already acquired) it
enters the blocked or wait state. The process continues to wait in the main
memory and does not require CPU. Once the I/O operation is completed the
process goes to the ready state.
• Complete (or Terminated): The process completed its execution. Process
is killed as well as PCB is deleted.
• Suspend Ready: When the ready queue becomes full(that means no
sufficient memory is available for new process), then some processes are
moved to suspend ready state to give space at RAM for new high priority
process
• Process that was initially in the ready state but were swapped out of
main memory and placed onto external storage by scheduler are said to
be in suspend ready state.
• The process will transition back to ready state whenever the process is
again brought onto the main memory.
• Suspend Block: When all processes is in waiting queue, then some of the
waiting processes are moved to suspended block to give space at RAM
for new processes or high priority process
• Similar to suspend ready but remove the process which was waiting to
perform I/O operation
• When work is finished it may go to suspend ready or blocked state
Process Scheduling Queues
• Three
• Job queue – set of all processes in the system which are ready to
come to main memory, maintain in secondary memory
• Ready queue – set of all processes residing in main memory, ready
and waiting to execute in processor, maintain in main memory
• Device queues – set of processes waiting for an I/O device, maintain
in main memory
• Suspend block and suspend ready queue is maintained in secondary
memory

Processes migrate among the various queues

Process Scheduler
• Brings a set of processes to main memory
• Handles the removal of the running process from the CPU and
the selection of another process from ready queue
CPU-Bound vs I/O-Bound Processes
• A CPU-bound process requires more CPU time
• spends more time in the running state.
• An I/O-bound process requires more I/O time and less
CPU time.
• spends more time in the wait state.
Types of Process Scheduler.
Long Term or job scheduler :
• It brings the new process to the ‘Ready State’.
• It controls Degree of Multi-programming, i.e., number of process present in ready state at
any point of time
• A careful selection of both IO and CPU bound process.
• The job scheduler increases efficiency by maintaining a balance between the two.

Short term or CPU scheduler :

• It is responsible for selecting one process from ready state for scheduling it on the running
state.
• Note: Short-term scheduler only selects the process to schedule it doesn’t load the process
on running.
• The CPU scheduler is responsible for ensuring there is no starvation owing to high burst time
processes.
Dispatcher is responsible for loading the process selected by Short-term scheduler on the CPU
(Ready to Running State)
• Context switching is done by dispatcher only.
Medium-term scheduler :
• It is responsible for suspending and resuming the process.
• It mainly does swapping (moving processes from main memory to
disk and vice versa).
• It is helpful in maintaining a perfect balance between the I/O bound
and the CPU bound.
• It reduces the degree of multiprogramming
 LTS STS
Schedule
Create Completion
New Ready Running Terminated
Priority/Time Slice

I/O Completion
I/O Request
Suspend
Resume
Block/
Wait MTS
MTS
Suspend Suspend
Ready
Resume

Finished I/O but

still suspended Suspend
Wait SM

22
Context Switching
• The process of saving the context of one process and loading the
context of another process.

• When does context switching happen?

• When process moves from Running to ready state
• Preemptive scheduling used
• When a high-priority process comes to a ready state ( higher priority than the running
process)
• When time slice expires

• When process moves from running to block state for I/O operation
• When process moves from running to terminate (no need to save state of
running process, but need to load state of new process from ready to running)
Operating Systems
(CS-3000)

Lecture-3

Dr. Jaishree Mayank

Assistant Professor
IIITDM Kancheepuram
Objective of this lecture

• Performance Metrics for CPU Scheduling

• Types of CPU Scheduling Strategies
Multi-Programming
• We have many processes ready to run.
• Degree of multiprogramming – The number of processes that can
reside in the ready state at maximum
CPU Scheduling
• Decide the order of execution of processes when multiple are competing
for system resources
• Where – In the Ready State
• Who(se) Responsibility – Short Term Scheduler
• When - Wherever there is queuing for the CPU!
• Ready to Running
• Function – allocate CPU to process
• Pre-emption – Process is forcefully removed from CPU.
• Non pre-emption – Processes are not removed until they complete the
execution.
Scheduling Criteria
• Increase CPU Utilization
• CPU should not be idle as minimum time as possible.
• Increase Throughput
• complete as many processes as possible per unit time
• Minimize Average Waiting Time
• Waiting time: The time duration taken by a process waiting in the ready queue.
• Minimize Average Turn Around Time
• Turnaround time: the time taken for a single process from start to completion.
• Minimize Average Response time
• Response time: the time taken from the point that when the process enters into the ready
queue to the point when the process goes into the running state
• Fairness
• ensure that each process is given a fair share of the CPU based on some particular policy
Types of CPU Scheduling
• Non preemptive
• FCFS
• SJF
• Priority
• HRRN

• Preemptive
• SRT
• RR
• Priority
Different Time based Parameters w.r.t.
Process
• Arrival Time (AT) - Time the Process comes to the Ready State
• Burst Time (BT) – Execution time of the process – also referred as Service Time
• Completion Time (CT) – Time at which process completes its execution.
• Turn Around Time (TAT) - Time required for an application (process) to give an
output to the end user
• TAT = CT - AT
• Waiting Time (WT) - Time Difference between turn around time and burst time.
• WT = TAT – BT
• Response Time – Time for the System to Respond to Process or User (First
Response time on System Clock)
• Time Since the Request is Submitted (AT) and the First Response Time
 FCFS
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
11
 FCFS
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
13
Advantages and Disadvantages
• Advantages
• Simple
• Fair

• Disadvantages
• Waiting time depends on arrival order
• Convoy effect
 SJF
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
16
 SJF
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
18
Advantages and Disadvantages
• Advantages
• Optimal: Min avg. waiting time and response time

• Disadvantages
• Difficult to predict burst time
• Starvation
 Priority based Non-Preemptive Scheduling
PID/P# Priority AT BT CT/FT TAT WT
1 3 0 7 4 4 0
2 2 0 4 7 6 3
3 1 0 2 8 6 5
4 4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
21
Operating System
(CS-206)

Lecture-4

Jaishree Mayank
Assistant Professor

IIITDM Kancheepuram
Preemptive Scheduling Algorithm

• SRTF
• RR
• Priority
Different Time based Parameters w.r.t.
Process
• Arrival Time (AT) - Time the Process comes to the Ready State
• Burst Time (BT) – Execution time of the process – also referred as
Service Time
• Completion Time (CT) – Time at which process completes its execution.
• Turn Around Time (TAT) - Time required for an application (process) to
give an output to the end user
• TAT = CT - AT
• Waiting Time (WT) - Time Difference between turn around time and
burst time.
• WT = TAT – BT
• Response Time – Time for the System to Respond to Process or User
(First Response time on System Clock)
• Time Since the Request is Submitted (AT) and the First Response Time
Shortest-First Job-With Preemption
SRTF-Shortest Remaining Time First
• If the new process arrives with a shorter burst than remaining of
current process then schedule a new process
• Reducing average waiting time and average response time
• Not Practical
 SRTF
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
5
 SRTF
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

7
Round-Robin Scheduling approach
• Each process gets a small unit of CPU time (time quantum), usually
10-100 milliseconds. After this time has elapsed, the process is
preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is
q, then each process gets 1/n of the CPU time in chunks of at most q
time units at once. No process waits more than (n-1)q time units.
• Preemptive approach
• Performance
• q large  FIFO
• q small  q must be large with respect to context switch, otherwise overhead
is too high
 RR
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
9
 RR
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 3 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
12
Operating System
(CS-206)

Lecture-5

Jaishree Mayank
Assistant Professor

IIITDM Kancheepuram
 FCFS
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
2
 FCFS
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

4
 RR
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
6
 RR
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

8
Operating System
(CS-206)

Lecture-5

Jaishree Mayank
Assistant Professor

IIITDM Kancheepuram
 HRRN-Non-preemptive
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 0 4 7 6 3
3 0 2 8 6 5
4 0 5 10 7 5
15 11 6
Average WT 19/5

GANTT CHART
3
 HRRN
PID/P# AT BT CT/FT TAT WT
1 0 7 4 4 0
2 2 4 7 6 3
3 4 2 8 6 5
4 7 1 10 7 5
15 11 6
Average WT 19/5

5
Operating Systems (CS3000)

Lecture – 8
(Multilevel Scheduling)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Multilevel Queue
● Ready queue is partitioned into separate queues – Priority Class
• Foreground (interactive) (Word processor, game application)
• Background(batch) (System update)

● Process permanently in a given queue

● Each queue has its own scheduling algorithm
–foreground– RR
–background – FCFS
 Scheduling must be done between Queues
• Strategy 1: Using Fixed Priority Scheduling
• serve all from foreground then from background
• Issue:- Possibility of Starvation

• Strategy 2: Using Time Slice

• each queue gets a certain amount of CPU time which it can schedule
amongst its processes;
• 80% to foreground in RR
• 20% to background in FCFS

5
 Multilevel Queue Scheduling
• Higher priority System Processes
P10 P6 P12 P1

Interactive Processes
P11 P7 P3 P2

Batch Processes
P13 P14 P15

• Lower Priority

6
 Multilevel Feedback Queue
• A process can move between the various queues processes
● Does not demand a knowledge of running time of jobs
●Balances both turnaround time (optimized by SJF/PSJF by selecting the
smallest job) and response time (optimized by RR by alternating)
• Multilevel feedback queue defined by the following parameters
• Numbers of queues
• Scheduling algorithm for each queue
• Methods used to determine when to upgrade a process
• Methods used to determine when to demote a process
• Methods used to determine which queue a process will enter when a
process needs services

7
 Multilevel Feedback Queue
● Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)
● Rule 2: If Priority(A) = Priority(B), A & B run in RR
● Rule 3: When a job enters the system, it is placed at the highest priority (the
topmost queue)
● Rule 4a: If a job uses up an entire time slice while running, its priority is reduced
(i.e., it moves down one queue)
–Intuition – CPU-bound job

● Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same
priority level
–Intuition – I/O-bound (interactive job)
 Multilevel Feedback Queue
• Example: Consider 3 queues
• Q0 - time quantum 8 milliseconds
• Q1 –time quantum 16 milliseconds
• Q2 – FCFS
• Scheduling:
• A new job enters queue Q0 which is served for 8 ms.
• When it gains CPU, job receives 8 milliseconds. If it does not finish in 8
milliseconds, job is moved to queue Q1
• At Q1 job is again served RR and receives 16 additional milliseconds. If it still
does not complete, it is preempted and moved to queue Q2.
• At Q2 it executes as FCFS

10
Multilevel Feedback Queue

Quantum=8

Quantum=16

FCFS

11
 Queues during process execution

LTS STS
Job
Ready Queue CPU EXIT
Pool/
Queue

Waiting Queue 1

MTS Waiting Queue 2

Waiting Queue n
12
 Multilevel Feedback Queue
● Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)
● Rule 2: If Priority(A) = Priority(B), A & B run in RR

● Rule 3: When a job enters the system, it is placed at the highest priority (the

topmost queue)
● Rule 4a: If a job uses up an entire time slice while running, its priority is reduced

(i.e., it moves down one queue)

● Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same

priority level
● Issues

–Starvation – too many I/O jobs

–Trick the scheduler – I/O just before the time slice is over
–A program may change its behavior over time
 Multilevel Feedback Queue
● Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)
● Rule 2: If Priority(A) = Priority(B), A & B run in RR
● Rule 3: When a job enters the system, it is placed at the highest priority (the
topmost queue)
● Rule 4: Once a job uses up its time allotment at a given level (regardless of how
many times it has given up the CPU), its priority is reduced (i.e., it moves down one
queue)
● Rule 5: After some time period S, move all the jobs in the system to the topmost
queue
 Comparison b/w different scheduling approach
Algorithm Strategy Average waiting Preemption Starvation Performance
time
FCFS Acc. To arrival Large No NO Slow
time performance/con
voy effect

SJF lowest cpu burst Smaller than FCFS No Yes Mini Avg Waiting
time time

SRTF Same as SJF but Smaller than FCFS YES Yes Min avg waiting
preemption time
allowed

RR Fixed time Large as No No Each process has

quatum(TQ) compared to SJF given a fairly fixed
and Priority time
scheduling.

Priority Acc. To priority Smaller than FCFS Yes Yes Well

Preemptive time with performance, but
16
 Comparison b/w different scheduling approach
Algorithm Strategy Complexity Average Preemption Starvation Performance
waiting time
Priority Non- Acc. To priority This type is less Smaller than No Yes Most beneficial
Preemptive time with complex than FCFS with batch
monitoring priority systems
incomimg preemptive
priority tasks
HRR Response Complex than Smaller than No No Helps for
Ratio FCFS FCFS process with
longer waiting
time
MLQ According to Complex than Smaller than Yes/No Yes Good
the process priority FCFS, performance
that resides in scheduling but contain a
the higher starvation
priority queue problem
MLFQ Longer burst Complex Smaller than all Yes/No No Good
time process scheduling performance,
moves to lower types in many no starvation
priority queue cases.
17
Other Advanced Scheduling Techniques
• Multiprocessor Scheduling
• Symmetric
• Asymmetric
• Real-Time Scheduling
• Distributed System Scheduling

18
 Multiple-Processor Systems
● Multiprocessor systems are increasingly commonplace
–In desktop machines, laptops, and even mobile devices
● Multicore processor
–Multiple CPU cores are packed onto a single chip
 Multiple-Processor Scheduling - Challenges
● The same user program would not run faster
● CPU scheduling more complex when multiple CPUs are available –
where + when
–Where to run scheduler?
–Synchronization

● Shared data
 Asymmetric Multiprocessing (Master-Slave)
● All scheduling decisions, I/O processing, and other system activities
handled by a single processor—the master
● The other processors execute the assigned program
● Only one processor accesses the system data structures, reducing the
need for data sharing
 Asymmetric Multiprocessing - Issues
●Contention
–Slave processors waiting for Master to make Scheduling decisions
 Symmetric Multiprocessing
● Each processor runs its own scheduler
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Global queue: All processes in common ready queue
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Global queue: All processes in common ready queue
–Advantages
●Good CPU utilization

●Fair to all processes

–Issues
●Scalability – contention for global queue

●Synchronization – locking needed by scheduler

–Scheduler should be as light as possible

●Processor affinity not achieved
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Partitioned queue: per-processor a private queue
● Static partitioning of processes
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Partitioned queue: per-processor a private queue
● Static partitioning of processes
–Advantages

● Easy to implement – no need of synchronization

● Scalable
● Processor affinity implicitly guaranteed
–Issues

● Load imbalance
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Partitioned queue: per-processor a private queue
●Static partitioning of processes

–Advantages
●Easy to implement – no need of synchronization

●Scalable

●Processor affinity implicitly guaranteed

–Issues
●Load imbalance

●Solution??
 Symmetric Multiprocessing
● Each processor runs its own scheduler
–Hybrid Approach: global queue + partitioned queue

–Used in Linux kernel 2.6 onward

 Real-Time Scheduling
● Real-time Systems
–Explicittimeliness requirement: deadline
–The correctness of result depends on both functional
correctness and time that the result is delivered

● Hard Real-time task

–Air traffic control, Vehicle subsystems control,
Nuclear power plant control
● Soft Real-time Task
–Multimedia transmission and reception, Networking,
telecom (cellular) networks, Web sites and services,
Computer games
 Real-Time Scheduling
● Periodic tasks
–Job

● Example: Speed sensor

Ti = (ei,pi)
ei = execution requirement and pi = period
Utilization ui=ei/pi
Necessary condition: Σui ≤ 1
 Real-Time CPU Scheduling
● Rate Monotonic (RM)
● Earliest Deadline First (EDF)
 Rate Monotonic (RM) Scheduling
● Optimal Static Priority Real-time Task Scheduling Algorithm
 Rate Monotonic (RM) Scheduling
● T1(2,6), T2(3,8)

● T1(2,6), T2(3,8), T3(3,12)

 Rate Monotonic (RM) Scheduling
● Sufficient condition

● For n → ∞, the right hand size evaluates to loge 2 = 0.692

 Earliest Deadline First (EDF) Scheduling
● Optimal Real-time Task Scheduling Algorithm
–Job-level fixed priority
● At any scheduling point pick the job with the smallest deadline
 Earliest Deadline First (EDF) Scheduling
● T1(2,6), T2(3,8)

● T1(2,6), T2(3,8), T3(3,12)

 Earliest Deadline First (EDF) Scheduling
● Necessary and sufficient condition
Operating Systems (CS3000)

Lecture – 8

(System Calls and OS Structure)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Events
Hardware Interrupts:
• Raised by any hardware device
• They are asynchronous and may occur any time
Traps:
• Sometimes called software interrupts
• Raised by user program, to access OS functionality
Exception:
• Generated automatically by the processor itself due to illegal instructions
• Faults and Aborts
 Process Memory Map
1 – Instructions of OS
2 – OS data
Kernel/OS

How do User Program

MAX_SIZE invoke OS?
Kernel Stack
Can
access User
Process Heap
Can
access Data
(R/W)

Code
0
Memory Map of Process

5
 Communicating with the OS (System Calls)
• System Calls are a set of special functions which the OS
supports.

• User Process can invoke any of the system calls

• Why?
• to get information
• to access hardware/ resources within the Kernel.

6
 printf( )
int x = 30;
printf(“%d”, x); write System Call 30
implementation
call Library
present in libc

write(STDOUT) TRAP
Handler
TRAP

USER SPACE KERNEL SPACE

RETURN

7
 What Happens During System Calls?
• process (user mode)  process (kernel mode)
• allow the kernel or the operating system to actually execute the task

• System Call completes: process (kernel mode)  process

(user mode)

8
 Function Call v/s System Call
• CALL instruction • TRAP instruction
• User Space • User Space  Kernel Space
• CALL jumps to a relocatable • TRAP jumps to a fixed
address address

9
 System Calls for Files
• Files: Data remains even if power is off
• Operations on Files:
• open()
• close()
• read()
• write()
• Files are stored in HDD. System call required to access
Hardware.
• Process -> System Call -> Kernel -> HDD -> Return FP to
Process

12
 Monolithic OS Structure
user processes access functionalities
within each modules

System Call Interface

1. All Components of OS/All

Memory File functionality of OS are
Scheduling present in Kernel Space
Kernel Management Management
2. Kernel is a single process
Space
where all functionalities
share the same address
Process Networking space.
IPC
Management 3. Direct Function Calls
between modules of
Kernels
Device Drivers 4. Large Size Kernel, Difficult
to maintain and manage
HARDWARE

13
 Microlithic OS Structure
user processes access functionalities
within each modules

System Call Interface

Kernel 1. Few Components of

Services OS/few functionality of OS
Run Memory Process File are present in Kernel
Networking
in User Management Management Management Space
Mode 2. Some Kernel services can
be modified by users
based on needs.
Kernel Scheduling IPC
Space
1. Direct Function Calls not
possible. IPC
Device Drivers 2. Small Size Kernel, Easy to
maintain and manage
HARDWARE

14
 What Metadata of a Process Kernel Stores?
• PCB
• Kernel Stack for User Process Kernel/OS
• During System Calls
Kernel Stack
• Page Table for that User Process
Stack

Heap

Data

Code

15
Operating Systems (CS3000)

Lecture – 11
(fork() System Call)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Examples of Windows and Unix System Calls

2
 What Metadata of a Process Kernel Stores?
• PCB
• Kernel Stack for User Process Kernel/OS
• During System Calls
Kernel Stack
• Page Table for that User Process
Stack

Heap

Data

Code

3
 Creating a Process by Cloning
• fork()
• Child Process is duplicate of parent process
• PID  Parent process is Child’s PID
• PID  Child process is 0

Parent

Process-1

Invokes a fork system

call
Child
Kernel (execute
fork) Process-2

4
 fork( )
{ { {
pid_t pid; pid_t pid; pid_t pid;
pid=fork();

if (pid<0) if (pid<0) if (pid<0)

printf("error in fork \n"); printf("error in fork \n"); printf("error in fork \n");
else if (pid==0) else if (pid==0) else if (pid==0)
{ { {
fork(); fork();
printf("child print \n"); printf("child print \n"); printf("child print \n");
} } }
else if (pid>0) else if (pid>0) else if (pid>0)
printf("Parent Print \n"); printf("Parent Print \n"); printf("Parent Print \n");
printf("Main Print \n"); printf("Main Print \n"); printf("Main Print \n");
return 0; return 0; return 0;
} } }

8
Operating Systems (CS3000)

Lecture – 12
(exec(), wait() System Call)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Creating a Process by Cloning
• fork()
• Child Process is duplicate of parent process
• PID  Parent process is Child’s PID
• PID  Child process is 0

Parent

Process-1

Invokes a fork system

call
Child
Kernel (execute
fork) Process-2

2
3
 The classic fork( ) Bomb!
• Overall 8 processes in Main Memory as indicated at the leaf level
nodes count
• In general n fork class (non conditional) will result in
________processes

int main()
{
fork();
fork();
fork();
printf(“Magic of fork()\n”);
return 0;
}

4
5
 How to create a new definition of process?
• So far fork example we did, child process carried the same image as
the parent process.
• Practicality requires child to have new definition.
• Is it possible?
• Yes

6
 exec( ) system call
• fork() system call is used to create a SEPARATE, DUPLICATE process with
non-shared pages from which process (parent) it is called.
• Using Copy-on-Write (COW)-SEPARATE, DUPLICATE process with Shared
pages
• The new child process will have different PID.

• When exec() system call is invoked from (p1), the program specified in the
parameters of exec() will replace the entire process.
• exec() takes one parameter, which is another program(p2)
• p1 will be replaced by p2.
• Replace one process with another process (PID don’t change)
• As we are not creating new process
• We are replacing an existing one
• Same PID with different content

7
8
9
 wait( ) system call
• called in parent process
• int wait(arg);
• Parent goes to block state
• Until one of it’s children terminates
• -1: if no child is executing or exists

• When the child process exits i.e exit(0), it would cause the parent process to
wake up
• the wait function returns the child process’s pid

• The parent waits for the child process using this system call.

10
Why wait( ) system call ?

11
Operating Systems (CS3000)

Lecture – 13
(exit() System Call, Zombie, Orphan, Reaper
Processes)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Zombie & Reaper Process

2
 exit( ) system call
• called in child process
• Results in process termination
• Return status is passed to the parent (Voluntary Termination)

• Forcefully termination
• kill() system call

3
 Process system calls Possible Flow
Parent Parent
wait() Continue

Parent
fork()

child child
exec() exit()

4
 Orphan Process
• When a parent process terminates before its child
• The first process will adopt the orphan child.

• First process (init) in the system never exits.

5
Operating Systems (CS3000)

Lecture – 12
(Inter Process Communication)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
2
3
 IPC
• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes
– Same computer or networked computers

5
 IPC
• Reasons for cooperating processes:
– Computation speedup
●
Multiple processing cores
●
Distributed computing
• Modularity
– Subtasks into separate processes or threads
• Client-Server Computing

• Cooperating processes need Inter-Process Communication (IPC)

• Many IPC mechanisms

6
 IPC
3 Ways
• Shared Memory
• Message Passing
• Pipes
• Signals

7
 Shared Memory RAM
• Process1
• Create SM Kernel/OS
• Attach SM to it’s address Space

• Write Data into SM Write

Process - 1

• Process 2 Read SM
• Attach SM to it’s address Space
Process - 2
• Read Data from SM written by
Writer

8
9
 Functions used in SM
• shmget()  to Create the SM
• shmat()  to attach the SM with the address space of the process
• shmdt()  to detach the SM
• shmctl()  to Destroy the SM

10
 shmget()
• int shmget(key_t key, size_t size, int shmflg);

• key-> Unique value that identifies the SM.

• size-> Size of the SM in bytes
• shmflg -> Permissions on the SM
• Retuns valid identifier of SM
• Used in shmat()
• Incase of Unsuccessful -> Returns -1

• #include<sys/ipc.h>
• #include<sys/shm.h>

11
 shmat()
• void* shmat(int shmid, const void * shmaddr, int shmflg);
• shmid -> value returned by shmget().
• shmaddr -> where to attach the SM in the address space of the
calling function
• Address not know so write NULL. If shmaddr is a NULL pointer, the segment
is attached at the first available address as selected by the system.
• OS will assign it at a suitable location.
• shmflg -> if shmaddr is NULL, shmflg is 0.
• Incase of Unsuccessful -> Returns -1
• #include<sys/types.h>
• #include<sys/shm.h>

12
 shmdt()

• int shmdt(void * shmaddr)

• shmdt detaches the shared memory segment located at the address
specified by shmaddr from the address space of the calling process

• On success, it returns 0, on error –1

• Detaching the shared memory doesn’t delete it

– it just makes that memory unavailable to the current process

13
 shmctl()
• int shmctl(int shmid, int command, struct shmid_ds *buf);
• returns information about a shared memory segment and can modify it
• shmid -> value returned by shmget().
• IPC_STAT: Retrieve the status of the shared memory segment.
• IPC_SET: Set the status of the shared memory segment.
• IPC_RMID: Remove the shared memory segment.
• This is a pointer to a struct shmid_ds structure that is used to get or set
information about the shared memory segment
• On success, it returns 0, on failure, –1

14
 Server.c
server.c

15
client.c

16
Operating Systems (CS3000)

Lecture – 16
(Inter Process Communication - 2)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Message Passing using Pipes
• Pipe is a communication between parent and child process
• Communication is achieved by one process writing into the pipe and
other reading from the pipe
• To achieve the pipe system call, create two descriptors, one to write
into the file and another to read from the file.
• Patent  Child

Write
Pipe
Read

2
 Creating Pipe between Parent and Child process
• int pipe(int pipefd[2]);
• a file descriptor is used to access the two ends of the pipe: one end
for reading and one end for writing

 pipefd[0] is the file descriptor for reading.

 pipefd[1] is the file descriptor for writing.
• Returns zero on success
• Returns -1 in case of failure

5
 Message Passing using Pipes
• ssize_t read(int fd, void *buf, size_t count)

 The file descriptor to read from.

 A pointer to a buffer where the read data will be stored.
 The maximum number of bytes to read.

• Returns the number of bytes read

• Returns -1 in case of failure

6
 Message Passing using Pipes
• ssize_t write(int fd, void *buf, size_t count)


The file descriptor to write to.

A pointer to a buffer where the write data will be stored.

The maximum number of bytes to write.
• Return the number of bytes written
• Return zero in case nothing is written
• Return -1 in case of failure

7
 Message Passing using Pipes
• _int close(int fd)


Closing the pipe end.

• Return zero on success

• Return -1 in case of failure

8
 Message Passing using Pipes
• Algorithm
• Step 1 − Create a pipe
• Step 2 − Create a child process
• Step 3 − Parent process writes to the pipe
• Step 4 − Child process retrieves the message from the pipe and
writes it to the standard output
• Step 5 − Repeat step 3 and step 4 once again

9
 Two-way Communication Using Pipes
• If both the parent and the child needs to write and read from the
pipes simultaneously
• Two pipes are required

10
 Two-way Communication Using Pipes
• Algorithm
• Step 1 − Create pipe1 for the parent process to write and the child
process to read
• Step 2 − Create pipe2 for the child process to write and the parent
process to read
• Step 3 − Close the unwanted ends of the pipe from the parent and
child side
• Step 4 − Parent process to write a message and child process to
read and display on the screen
• Step 5 − Child process to write a message and parent process to
read and display on the screen

11
Pipe1.c

12
Pipe2.c

13
Operating Systems (CS3000)

Lecture – 15
(Inter Process Communication - 2)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Problem with SM
• Synchronization needed between the processes

2
 Message Passing RAM
• SM is created in Kernel
SM
• System calls are used Kernel/OS
• send(): Write to SM send ()
• receive(): Read from SM

Process - 1 receive()

Process - 2

3
 IPC using Message Queues
• linked list of messages
• stored within the kernel
• identified by a message queue identifier.
• Functions
• msgget()  To create a message queue/Open Existing
• msgsnd()  To write message to message queue by Sender/New messages
are added to the end of the queue
• msgrcv()  To retrieve message from message queue by Receiver
• msgctl()  The control function

4
 IPC using Message Queues
• Sender
• Create the MQ
• Add data to the MQ
• Receiver
• Retrieve the data from MQ
• Delete the MQ

5
 IPC using Message Queues
• int msgget(key_t key, int msgflg);

• creates a new message queue

• On success, msgget()returns the message queue identifier (a positive

integer).
• On failure, it returns -1and sets errnoto indicate the error.

6
 IPC using Message Queues

• int msgsnd(int msqid, void *msgp, size_t msgsz, int msgflg);

• send a message to the message queue specified by the msqid parameter.
• It is returned by the msgget() function and used to identify the message
queue to send the message to.

• The *msgp parameter points to a user-defined buffer that must contain the
following:
• A field of type long int that specifies the type of the message.
• An array that contains the actual content of the message.

7
 IPC using Message Queues
• int msgsnd(int msqid, void *msgp, size_t msgsz, int msgflg);
• The following structure is an example of what the user-defined buffer might
look like for a message that has 5 bytes of data.
struct mymsg
{
long int mtype; /* message type */
char mtext[5]; /* message text */
}
• The value of mtype must be greater than zero. When messages are received
with msgrcv(), the message type can be used to select the messages.
• The message data can be any length up to the system limit.

8
 IPC using Message Queues
• int msgsnd(int msqid, void *msgp, size_t msgsz, int msgflg);
•
• msgsz: Length of the data part of the message to be sent.

• msgflg: If the message queue is full, the msgflg parameter specifies the
action to be taken. The actions are as follows:
• 0: Suspended
• IPC_NOWAIT: do not wait for space to become available on the message queue and
return immediately.

9
 IPC using Message Queues
• int msgrcv(int msqid, void *msgp, size_t msgsz, long int msgtyp, int
msgflg);


The msgrcv() function reads a message from the message queue
specified by the msqid parameter and places it in the user-defined
buffer pointed to by the *msgp parameter.

The *msgp parameter points to a user-defined buffer that must
contain the following:
• A field of type long int that specifies the type of the message.
• A data part that contains the data bytes of the message.

10
 IPC using Message Queues
• int msgrcv(int msqid, void *msgp, size_t msgsz, long int msgtyp, int
msgflg);
struct mymsg
{
long int mtype; /* message type */
char mtext[5]; /* message text */
}
• The value of mtype is the type of the received message, as specified
by the sender of the message.
• The msgsz parameter specifies the size in bytes of the data part of
the message.
• The received message is truncated to msgsz bytes if it is larger than msgsz.

11
 IPC using Message Queues
• int msgrcv(int msqid, void *msgp, size_t msgsz, long int msgtyp, int
msgflg);

• The msgtyp parameter specifies the type of message to receive from

the message queue as follows:
• If msgtyp = 0, read the first message in the queue.
• the messages will the retrieved in the same order in which they were written into the
message queue
• If msgtyp > 0, the first message of type “msgtyp” is only received.
• If msgtyp < 0, the first message of the lowest type that is less than or equal
to the absolute value of msgtyp is received.

12
 IPC using Message Queues
• int msgrcv(int msqid, void *msgp, size_t msgsz, long int msgtyp, int
msgflg);
• If a message of the desired type is not available on the message queue,
the msgflg parameter specifies the action to be taken. The actions are as
follows:

• If the IPC_NOWAIT flag is set in the msgflg parameter, msgrcv() returns

immediately with a return value of -1.

• If 0 : suspend the process

13
 IPC using Message Queues
• int msgctl(int msqid, int cmd, struct msqid_ds *buf);
• The msgctl() function allows the caller to control the message queue
specified by the msqid parameter.
• msqid Message queue identifier, a positive integer. It is returned by
the msgget() function and used to identify the message queue on which to
perform the control operation.
• cmd Command, the control operation to perform on the message queue.
• buf Pointer to the message queue data structure to be used to get or set
message queue information.
• msqid_ds

14
MQ_Send1.c

15
MQ_Send1.c

16
Operating Systems (CS3000)

Lecture – 17
(Inter Process Communication - 4)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Signals
• A signal is an asynchronous event which is delivered to a process.
• The event can occur at any time (may be unrelated to the execution of the
process)
• An event which is generated to notify a process that some important
situation has risen

• Signals are raised by some error conditions

• Memory segment violations
• Floating point processor errors
• Illegal instructions – e.g. user types ctrl-C

2
 Signals
• What Process will do on receipt of Signal?
• Will stop what its doing and take some action

• Signals are defined in the header file <signal.h> as a macro constant

• SIGINT
• SIGFPE
• SIGKILL
• SIGUSR1
• SIGUSR2
• SIGSTOP
• Every signal has a name and an associated number.

3
 Signals
• How to raise a signal?
• Program
• System generated
• What happens?
• Default defined action
• Doesn’t want default?
• User defined action/ handling of signal
• Ignore Signal?
• Yes
• SIGSTOP/SIGKILL

4
 Signal handling
• On Signal receipt, the process has a choice of action.
• The process can ignore the signal – Signal is discarded
• Can specify a handler function
• Accept the default action for the specific kind of signal

• The program can register a handler function using function such

as signal() or sigaction().

• If the signal has not been neither handled nor ignored, its default
action takes place.

5
 Signal handling
int signal (int signum, void (*func)(int))
#include<stdio.h>
#include<signal.h>

void sig_handler(int signum)

{
printf(“I am in sig_handler ()\n");
}

int main()
{
signal(SIGUSR1,sig_handler);
printf(“I am in main()\n");
raise(SIGUSR1);
printf(“I am in main() again\n");
return 0;
}

6
 Signal handling
• int sigaction(int signum, const struct sigaction *act, struct sigaction
*oldact)
• To change the signal action

7
Operating Systems (CS3000)

Lecture – 16
(Inter Process Communication - 5)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 IPC using Named Pipe
• Communication between unrelated processes

Execute client program from one terminal and the server program from
another terminal.

Named Pipe supports bi-directional communication.

2
 To create a Named pipe
• int mknod(const char *pathname, mode_t mode, dev_t dev);
• create a special file or file system node such as ordinary file, device file,
or FIFO.
• The pathname either absolute path or relative path of the file.
• The mode specified is the mode of file which specifies the file type and
the file permission.
• The dev field is to specify device information such as major and minor
device numbers (Default 0).
• return zero on success and -1 in case of failure.

3
 Message Passing using Pipes
int mkfifo(const char *pathname, mode_t mode)

 a FIFO special file, which is used for named pipe.

 The file name can be either absolute path or relative path.
 The file mode information is as described as permission
 return zero on success and -1 in case of failure.

4
 Message Passing using Named Pipes (FIFO)
•Algorithm: server process.
STEP1: Creates a named pipe (using library function mkfifo()) with name
“fifofile” in directory, if not created. (Only one procees will create the pipe)
STEP2: Opens the named pipe for read purpose.
STEP3: Waits infinitely for a message from the client.
STEP4: Print message received from the client and close the file.
STEP5: Opens the named pipe for write purpose.
STEP6: Accepts string from the user.
STEP7: Sends a message to the client and close the named pipe.
STEP8: Repeats infinitely until the user enters the string “end”.

5
 Message Passing using Named Pipes
• Algorithm: Client process

• STEP1: Opens the named pipe for write purpose.

• STEP2: Accepts string from the user.
• STEP3: Sends a message to the server and close the named pipe.
• STEP4: Open the named pipe for read purpose
• STEP5: Waits for the message from the server and prints the message.
• STEP6: Close the named pipe
• STEP7: Repeats infinitely until the user enters the string “end”.

6
Pipe2.c

7
8
Operating Systems (CS3000)

(Threads-Part1)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Motivation
• If a man needs 5 days to do a job then how many days will it take for 5 men to
do the same job?
• Only 1 day

• Here comes the concept of Parallelization.

•
 Agenda
• Basic Concept of Threading
• How thread is created and destroyed.
• How thread is different from Processes.
• How different Operating System support thread in different ways.
Motivation

Process

P1 P2 P3 P4

Processors
Motivation – Speedup with Multiple Process
10000000/4=2.5 million
• Create 4 processes, each loop does 1/4th of
the work.
• Properties
Process1 Process2 Process3 Process4
• Create 4 processes using fork system call
• Each process is isolated from each other
• IPC mechanish-more system calls
• Process management system calls
• Each process has own memory map
• Instructions
• Data
• Stack
P1 P2 P3 P4 • heap
•
Processors
 Motivation
• Problems on Creating 4 Processes
• Overhead
• due to considerable amount of system call.
• due to large portion of these processes are similar

•Can we reduced this overhead?

•
 Thread
• Properties
10000000/4=2.5 million
• Create 1 process with 4 threads
• 1 fork system call, 4 threads need to be
created
Process1
• Each thread is not isolated from each other
• Management of thread with fewer or no
system calls
• Each thread has own stack and registers
• Threads share
• Instructions
• Data
• Heap
P1 P2 P3 P4
Processors
 Thread
• A thread is a basic unit of CPU utilization. One Process
• Separate streams of execution in single
process. Data Code Files

• Threads in the process are not isolated from registers registers registers
each other.
stack stack stack
• Each thread state /thread control block /thread
execution context contains
• Thread id
• Program counter
• Registers
• Stack
 Advantages of Threads over Processes
• Lightweight
• Efficient communication between entities
• Efficient context switching
 Thread vs Processes
• A thread has no data segment or • A process has code, heap, stack
heap and other segments.
• A thread cannot live its own. It • We can consider a process has
needs to be attached to a at-least one thread.
process.
• There can be more than one • Processes doesn’t share the
thread in a process. Each thread files.
has its own stack.
• If a process dies, all threads die.
• If a thread dies, its stack is
reclaimed.
 How to create and manage threads?

• Using Thread Libraries

• pthread
• Win32 thread
• Java threads
 pthread library
• Create a thread in a process
• int pthread_create (pthread_t *thread, const pthread_attr_t *attr, void
*(*start_routine) (void*), void *arg);
• It takes four argument
• 1st argument- Pointer to Thread_id
• 2nd argument- specify several properties of the thread (stack size,
scheduling information)
• 3rd argument- pointer to a function where the new thread will begin
execution
• 4th argument- arg which is a pointer to the arguments to the
start_routine function (3rd argument)
 pthread library

• Destroy a thread
• void pthread_exit (void *retval);
• pass a pointer to the return value, in order to pass the return status of the
thread
• Join:- wait for a specific thread to complete
• int pthread_join (pthread_t thread, void **retval);
• the parent thread will wait for it to complete by calling the pthread_join()
function.
 pthread library 0+1+2 + … + 99 = 4950
#include <pthread.h> int main(){
#include <stdio.h> pthread_t t1, t2, t3, t4;

int sum[4];
pthread_create(&t1, NULL, thread_fn, (void *)0);
void *thread_fn (void *arg) pthread_create(&t2, NULL, thread_fn, (void *)1);
{ pthread_create(&t3, NULL, thread_fn, (void *)2);
int id =(int) arg;
pthread_create(&t4, NULL, thread_fn, (void *)3);
int start =id*25;
int i=0;
pthread_join(t1, NULL);
while(i<25) pthread_join(t2, NULL);
{
pthread_join(t3, NULL);
sum[id]+=(i+start);
pthread_join(t4, NULL);
i++;
} printf(“%d\n”, sum[0]+sum[1]+sum[2]+sum[3]);
return NULL; return 0;
}
}
Operating Systems (CS3000)

Lecture – 34
(Threads - 2)
 Agenda
• We will understand how the thread are managed.
 Who manages Thread?
• There are two Strategies

• User Level Thread

• Threads are managed by user level thread library.
• Kernel knows nothing about the threads.

• Kernel Level Thread

• Threads directly supported by the kernel.
User Level Thread
• Advantages:
• Fast (really lightweight)
• no system call to manage threads.
• The thread library does everything.
• Can be implemented in an OS that does not
support threading.
• Switching is fast. No switch from user to
protected mode.
• Disadvantages:
• Scheduling can be an issue.
• Lack of coordination between kernel and
threads.
• Problem during blocking system calls.
• If one thread invokes a system call, all
threads need to wait
Kernel Level Thread
• Advantages
• Scheduler can decide to give more time to a
process having large number of threads than
process having small number of threads.
• Kernel level thread are especially good for
applications that frequently block.
• Disadvantages
• The kernel level threads are slow (they involve
kernel invocations)
• Overheads in the kernel.
Multithreading model - Many-to-one
• Many-to-one
• Many user level thread mapped to
one kernel level thread
• Example: Solaris Green thread, GNU
Portable thread
• Disadvantage:
• Blocking system call by one thread,
will block entire process.
Multithreading model - One-to-one
• One-to-one
• Each user level thread mapped to one
kernel level thread
• Provide concurrency
• Example: Windows XP, Linux
• Disadvantage:-
• a user thread requires to create the
corresponding kernel thread
• Limitation to create kernel thread
Multithreading model - Many-to-many
• Many-to-Many Model
• Allows many user level thread to
be mapped to many kernel level
threads
• Example:- Solaris prior to version 9
 Threading Issues
• What happens when thread invokes fork?
• Duplicate all threads?
• Not easily done, other threads may be running or blocked in a system
call or a critical section.

• Duplicate only caller thread?

• More feasible

• Should only the thread terminate or the entire process?

• All the decisions are taken care by the OS designer.

 Typical usage of Thread
• Whenever an event occurs
Event occured
Event • A thread gets created
?
• Service that event
Create
No event occured
Thread • Terminate after completion
Service
• Every time you have to create a
event thread for each event
• Creation and Termination of
Terminate
thread
thread incur overhead
Thread pools
• Create thread pool of 50-100 threads.
• All threads will reside in blocked state
• Whenever a request comes
• Wake up one of the thread from the
thread pool
• Service the request
• Thread gets returned to the thread
pool.
• Reduces overhead of creation and
termination of a thread
• Once the application will terminate, all
the threads of thread pool get
terminated.
 Benefit of Multi-threading
• Responsiveness:- It allow a program to continue running even if part of it is
blocked.
• Resource Sharing:- threads share the memory and the resources of the process
to which they belong.
• Economy:- threads share resources of the process to which they belong, it is
more economical to create and context-switch threads.
• Utilization of multiprocessor architecture:- threads may be running in parallel
on different processors. Basically increases the concurrency.
 Thread Cancellation Issues
• Terminating a thread before it has finished.
• Two approaches for the cancellation of thread
• Asynchronous cancellation:-
• One thread immediately terminates the target thread.
●
Difficulties:May not free the resources allocated to a cancelled thread.
●
Inconsistency: because cancellation occurs in middle of updating
the data, which is shared by other threads.
• Deferred cancellation:-
• allows the target thread to periodically check if it should be cancelled.
• Difficulties: Target thread wait for periodic check unnecessarily.
 Thank You
Any Questions?

28
Operating Systems (CS3000)
Lecture – 21

(Threads - Scheduling)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Motivation
• Issue: In multithreaded programs communication between the kernel and the
thread library is major concern.
• Applicable for many-to many
 Lightweight Process
• An intermediate data structure between user and kernel threads known as
lightweight process (LWP)
• To user level thread LWP appears to be virtual processor on which the
application can schedule a user thread to schedule.
• Each LWP is attached to kernel thread, the kernel thread executes on physical
processors.

• Scheduler Activation:

Scheme for communicating between the user thread-library and the kernel.
 Thread Scheduling
Process contention Scope (PCS):



Competition for the CPU takes place among threads belonging to the same
process.

The thread library schedules user-level threads to run on an available LWP.

Apply for many-to many and many-to-one model

PCS is done according to priority

User-level thread priorities are set by the programmer and are not
adjusted by the thread library, although

some thread libraries may allow the programmer to change the priority of
a thread.
 Thread Scheduling
System Contention Scope (SCS):



Deciding kernel thread to schedule onto a CPU

Apply on one to one model
 pthread Scheduling

PTHREAD_SCOPE_PROCESS: Schedules threads using PCS Scheduling
PTHREAD_SCOPE_SYSTEM: Schedules threads using SCS scheduling


pthread_attr_setscope(pthread_attr_t *attr, int scope)



First parameter:attributes set for the thread



Second parameter:



value of PTHREAD_SCOPE_PROCESS or

PTHREAD_SCOPE_PROCESS
 pthread Scheduling

pthread_attr_getscope(pthread_attr_t *attr, int *scope)



First parameter:attributes set for the thread



Second parameter: value of pointer to the int value that is set to the current


value of the contention scope.

 Thank You
Any Questions?

8
Operating Systems (CS3000)

Lecture – 20
(Process Synchronization - 1)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Why Synchronization is important?
• SM-Is it Helpful?
• Communication between the Processes
• Sharing of data with Modular Programming

• What could happen because of SM?

2
 Why Synchronization?
{ {
--- ---
--- int counter = 5 ---
counter++; counter--;
---- ----
Shared Variable
---- ----
} }

Process - 1 Process - 2
• Output?
• 5 (Expected) P1 P2

P2 P1

3
 Why Synchronization?
{ {
--- ---
--- int counter = 5 ---
counter++; counter--;
---- ----
Shared Variable
---- ----
} }

Process - 1 Process - 2
• Output?
•5

4
 Why Synchronization?
{ {
--- ---
1. R1<- counter --- int counter = 5 --- 1. R2<- counter
2. R1 = R1 + 1 counter++; counter--; 2. R2 = R2 - 1
3. counter <- R1 ---- ---- 3. counter <- R2
Shared Variable
---- ----
} }

Process - 1 Process - 2
• Output?
P1 P2 P1 (1) P2(1,2,3) P1(2,3) P2 P1

Context Switch

5
 Why Synchronization?
{ {
--- ---
1. R1<- counter --- int counter = 5 --- 1. R2<- counter
2. R1 = R1 + 1 counter++; counter--; 2. R2 = R2 - 1
3. counter <- R1 ---- ---- 3. counter <- R2
Shared Variable
---- ----
} }

Process - 1 Process - 2
• Output?
P1 P2(1) P1 (1,2,3) P2(2,3) P1 P2 P1
Context Switch

6
 Why Synchronization?
• What could happen because of SM?
• Final Value of Shared Variable depends
• On the Order of Execution of Instructions
• On which instruction the process is preempted

7
 Race Condition
• Situation when several processes access and manipulate the same
data
• Critical Section:-It is the part of the program where shared resources are
accessed.
• The outcome of a race condition: O/P depends on the order in which
the accesses to the data took place.
{
--- CS
---
counter++;
----
----
}

Process - 1

8
 How to Prevent Race Condition?
• Synchronization
• Ensure only one process manipulates the shared data at a time

9
Solution to Critical Section Problem
Mutual Exclusion:-
No more than one process in critical section at a time.

Progress:-
When no process is in the critical section, any process that requests entry to the critical section must
be permitted without any delay.

Bounded waiting (No starvation):-

There is upper bound on the number of times a process enters the critical section, while another is
waiting.

10
 Locks and Unlocks
All critical section problem use techniques known as locking and unlocking
in order to solve the critical section problem

lock(L):- Acquire lock L exclusively

Unlock(L):-Release exclusive access of lock L
{
{
* int counter=5 *
* lock_t L; *
lock(L) lock(L)
counter++; counter--;
unlock(L) unlock(L)
* *
} }

11
When to use locking mechanism?

Single instruction by themselves are atomic


Multiple instruction need to be explicitly made atomic
Need explicit locking and unlocking

12
When to use locking mechanism?
• Using Interrupts
• Software solution for critical section problem
• Simple
• When interrupts are disabled, context switches won’t happen
• Requires Privileges
• User processes generally cannot disable interrupts
• Not suited for multicore systems
Process 1 Process 2

While(1){ While(1){
Disable interrupts Disable interrupts
Critical section Critical section
Enable Interrupts Enable Interrupts
} }

13
Software Solution 1
int turn=1;
Process 1 Process 2

while(1){ while(1){
while(turn ==2); while(turn==1);

Critical section Critical section

turn =2; turn =1;
} }

14
Software Solution 2
turn2=false;
Process 1 turn1=false; Process 2
while(1){ while(1){
while(turn2==true); while(turn1==true);
turn1=true; turn2=true;
Critical section Critical section
turn1 =false; turn2 =false;
} }

15
Software Solution 3
Process 1
turn2=false; Process 2
while(1){ turn1=false;
while(1){
turn1=true;
turn2=true;
while(turn2==true);
while(turn1==true);
Critical section
Critical section
turn2 =false;
turn1 =false;
}
}

16
 flag2=false;
flag1=false; Process 2
Process 1 turn

while(1){ while(1){
flag1=true; flag2=true;
turn=2; turn =1
while(flag2==true && turn =2); while(flag1==true && turn=1);

Critical section Critical section

flag1 =false; flag2 =false;

} }

17
 Bakery Algorithm
Requesting Access:
●
When a process wants to enter the critical section, it sets its flag to true.
●
chooses a number that is greater than the current maximum label value among all process. This is
done atomically to ensure the correct ordering.

Entering the Critical Section:

●
Before entering, a process checks the flags and labels of other threads:
●
It waits for all other process with lower numbers (or the same number but higher priority) to finish.

Exiting the Critical Section:

●
The process resets its flag to false after finishing its work in the critical sec

18
 boolean flag[N] = {false};

int label[N] = {0};

lock(i){
flag[i] = true;
label[i] = max(label[0], ..., label[N-1]) + 1;
flag[i] = false;
for j = 0 to N-1{
if j != i{ unlock(i)
while (flag[j]); // Wait until j takes the value and notinterested {
label[i]=0;
while( label[j] != 0 and (label[j] < label[i] or label[j] == label[i] }
and j < i)):
}}
}

19
20
21
 Thank You

Any Questions?

22
Operating Systems (CS3000)

Lecture – 20
(Process Synchronization - 2)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Hardware Solution 1-TestandSet
int locked=0;
int TestandSet(int *locked)
Process 1 { Process 2
while(1){ int prev=*locked; while(1){
while(TestandSet(&locked))==1); *locked=1; while(TestandSet(&locked))==1);
return prev;
Critical section Critical section
locked=0; } locked=0;
} }

2
 Hardware Solution 2-Swap (Version 1)
int locked=0, val=1;
int Swap(int *locked, int val)
{

int prev=*locked;
*locked=val; Process 2
Process 1
return prev;
while(1){
while(1){ while(Swap(&locked, val))==1);
while(Swap(&locked, val))==1); }
Critical section
Critical section locked=0;
locked=0; }
}

3
 Hardware Solution 2-Swap (Version-2)
int locked=0;
int Swap(int *locked, int *val)
{

int temp=*locked;
Process 1 *locked=*val; Process 2
*val=temp;
While(1){ While(1){
Val=1; Val=1;
} while(Swap(&locked, val))==1);
while(Swap(&locked, val))==1);
Critical section
Critical section
locked=0;
locked=0;
}
}

4
 Hardware Solution -For n process)
Process { boolean waiting[n];
waiting [i] = TRUE; boolean lock=False;
key = TRUE;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting [i] = FALSE;
// critical section
j = ( i + 1) % n ;
w h i l e ( (j ! = i) && ! w a i t i n g [ j ] )
j = (j + 1) % n ;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
}
5
 High Level Techniques


Spinlocks

Mutex

Semaphore

6
 Spinlocks
int locked=0;
void acquire(int *locked)
Process 1 { Process 2
while(1)
While(1){ { While(1){
acquire(&locked) if(swap(locked, val)==0) acquire(&locked)
Break;
Critical section } Critical section
release(&locked) } release(&locked)
} }
void release (int *locked)
{
*locked=0;
}

7
 Mutex
int locked=0;
void lock(int *locked)
{
Process 1 while(1) Process 2
{
While(1){ if(swap(locked, val)==0) While(1){
lock(&locked) Break; acquire(&locked)
}
Else
Critical section Critical section
sleep();
unlock(&locked) release(&locked)
}
} }
void release (int *locked)
{
*locked=0;
wakeup();
}

8
 Thundering Herd Problem

A large number of processes wake up almost
simultaneously, when the even occurs
 Leading to more context switching
 Could lead to starvation
 Wasted cpu cycle

Solutions:

9
 Thank You

Any Questions?

10
Operating Systems (CS3000)

Lecture – 20
(Process Synchronization - 3)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Producer Consumer Problem

Also Known as Bounded Buffer Problem

Producer produces the item and stores in buffer, Consumer
consumes, but buffer is empty.

Problem

2
 Producer Consumer Problem
Producer()
Consumer()Process 2
{
{
while(true)
while(true)
While(1){
{ acquire(&locked)
{
Item =produce_item();
Critical section
lock(mutex);
release(&locked)
item=remove_item();
}
lock(mutex);
Count--;
insert_item(Item);
unlock(mutex);
Count++;
unlock(mutex);
consume_item()
}}
}}
3
 Semaphore

Proposed by Dijkstras void down(int *S)
{

up/P/signal
while(*S<=0);

down/V/wait *S--;
}

Semaphore: blocking and unblocking

Counting and Binary void up(int *S)
{

*S++;
}

4
 Semaphore
typedef struct { signal(semaphore *S) {
int value;
wait(semaphore *S) { S->value++;
struct process *
S->value--; list ; if (S->value <= 0) {
if (S->value < 0) { } semaphore; remove a process P from S->list;
add this process to S->list; wakeup(P);
block()/sleep(); }
} }
}

5
• Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only
one of the waiting processes
• Let S and Q be two semaphores initialized to 1
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
. .
. .

signal (S); signal (Q);

signal (Q); signal (S);
• Starvation – Indefinite blocking may occur if we add and remove processes from the list associated
with a semaphore in LIFO (last-in, first-out) order.
• Priority Inversion - Scheduling problem when lower-priority process holds a lock needed by higher-
priority process

6

Consider two concurrent process ‘P’ and ‘Q’ executes their response code

Process P code Process Q Code

What should be the binary operation on W, X, Y, Z and what should be the initial
value of binary semaphore ‘S’ and ‘T’ in order to get the output always as 0011
0011 0011……

(a) w=P(T), X=V(T), Y=P(S), Z=V(S), S=T=1.

(b) w=P(T), X=V(T), Y=P(S), Z=V(S), S=1, T=0.

(c) w=P(T), X=V(S), Y=P(S), Z=V(T), S=T=1.

(d) w=P(T), X=V(S), Y=P(S), Z=V(T), S=0,T=1.

7
 Thank You

Any Questions?

8
Operating Systems (CS3000)

Lecture – 20
(Process Synchronization - 4)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Classical Problems of Synchronization

Producer Consumer Problem (Bounded-Buffer Problem)

Readers and Writers Problem

Dining-Philosophers Problem

2
Producer Consumer Problem

N buffers, each can hold one item

Semaphore mutex initialized to the value 1

Semaphore full initialized to the value 0

Semaphore empty initialized to the value N.


Full =4

Empty=2

N=6

3
 Producer Consumer Problem
Producer() Consumer()
{ {
while(true) while(true)
{ {
Item =produce_item();

item=remove_item();
Count--;
insert_item(Item);

consume_item()
}}
}}
4
 Producer Consumer Problem
Producer()
Consumer()Process 2
{
{
while(true)
while(true)
While(1){
{ acquire(&locked)
{
Item =produce_item();
Critical section
release(&locked)
item=remove_item();
}
insert_item(Item);

consume_item()
}}
}}
5
 Producer Consumer Problem
Producer() Consumer()
{ { Process 2
while(true) while(true)
While(1){
{ { acquire(&locked)
Item =produce_item();
wait (full);
Critical section
wait (empty); wait (mutex);
release(&locked)
wait (mutex); }
item=remove_item();
// insert_item(Item);
signal (mutex);
signal (mutex); signal (empty);
signal (full); consume_item(item);
}} }}
6
Reader Writer Problem

A data set is shared among a number of concurrent processes

Readers – only read the data set; they do not perform any updates

Writers – can both read and write


Problem – allow multiple readers to read at the same time. Only one single
writer can access the shared data at the same time


Shared Data

Data set

Semaphore mutex initialized to 1

Semaphore wrt initialized to 1

Integer readcount initialized to 0

7
 Reader Writer Problem
do {
do { wait(mutex);
readcount + + ;
wait (wrt) ;
if (readcount == 1)
wait(wrt);
// writing is performed signal(mutex);
// reading is performed
wait (mutex) ,
signal (wrt) ; readcount--;
} while (TRUE); if (readcount == 0)
signal(wrt);
signal(mutex);
} while(TRUE);
8
9
Dining Philosophers Problem

Philosophers either think or
eat

To eat, a philosopher needs
to hold both forks (the one
on his left and the one on
his right)

If the philosopher is not
eating , he is thinking

Problem Statement:
Develop an algorithm where
no philosopher starves

10
Solution 1
#define N 5
Void philosopher(int i){
While(TRUE){
think(); //for some_time
Take_fork(R);
Take_fork(L);
eat();
put_fork(L);
put_fork(R);
}
}

11
12
 Thank You

Any Questions?

13
Operating Systems (CS3000)

Lecture – 20
(Process Synchronization - 5)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Dining Philosophers Problem

Philosophers either think or
eat

To eat, a philosopher needs
to hold both forks (the one
on his left and the one on
his right)

If the philosopher is not
eating , he is thinking

Problem Statement:
Develop an algorithm where
no philosopher starves

2
Solution 1
#define N 5
Void philosopher(int i){
While(TRUE){
think(); //for some_time
Take_fork(R_i);
Take_fork(L_i);
eat();
put_fork(L_i);
put_fork(R_i);
}
}

3
 #define N 5

Solution 2 Void philosopher(int i){

While(TRUE){
think(); //for some_time
Take_fork(R_i);
if(available(L_i)){
Take_fork(L_i);
eat();
put_fork(L_i);
put_fork(R_i);
}
Else
{
put_fork(R_i);
Sleep(T);
}
}}

4
 #define N 5
Solution 3 Void philosopher(int i){
While(TRUE){
think(); //for some_time
lock(mutex);
Take_fork(R_i);
Take_fork(L_i);
eat();
put_fork(L_i);
put_fork(R_i);
unlock(mutex);
}
}

5
 #define N 5
Solution 4 semaphore chopstick[5];
Void philosopher(int i){
While(TRUE){
wait (chopstick [i] );
wait(chopstick [ (i + 1) % 5] ) ;
// eat
signal(chopstick [i]);
signal(chopstick [(i + 1) % 5]);
}
}

6
 Solution 5 Void take_fork(int i){
Void take_fork(int i){
#define N 5 lock(mutex);
semaphore S[5]; state[i]=hungry; lock(mutex);
states[i]={thinking, test(i) state[i]=thinking;
hungry, eating} unlock(mutex); test(left);
Void philosopher(int i) down(S[i]); text(right);
{ unlock(mutex);
}
While(TRUE){ }
Think();
take_fork(i); Void test(int i){
// eat if(state[i]=hungry && state[Left]!=eating && state[right]!=eating)
put_fork(i) {
}
state[i]=eating;
}
up[i];
}
}
7
8
 Thank You

Any Questions?

9
Deadlocks
Dr. Jaishree Mayank
 Deadlock
• In a multiprogramming environment, several processes may compete
for a finite number of resources.
• A process requests resources; and if the resources are not available at
that time, the process enters a waiting state.
• Sometimes, a waiting process is never again able to change state,
because the resources it has requested are held by other processes.
• This situation is called a deadlock.
 System Model
• A system consists of a finite number of resources to be
distributed among a number of competing processes.
• The resources are partitioned into several types, each consisting
of some number of identical instances.
• Example of Resource Types

CPU Cycles Memory Space

I/O Devices Files

• Under the normal mode of operation, a process may
utilize a resource in only the following sequences:
[Link]:-
• If the request is available, assigned the resource to the
process.
• If the request cannot be granted immediately , then the
requesting process must wait until it can acquire the
resource.
2. Use:- The process can operate on the resource.
3. Release:- The process releases the resource.
Deadlock Characterization
• In a deadlock, processes never finish executing, and system
resources are tied up, preventing other jobs from starting.

• Features that characteristics deadlocks-Necessary condition

1. Mutual Exclusion:-
• There exists at least one non-sharable resource.
• At a time only one process can use the resource.

2. Hold and wait:-

A process must be holding at least one resource and wait for
other resource that are currently being held by other process.
3. No Preemption:
Resources cannot be pre-empted; that is, a resource
can be released only when the process holding it finishes
the task.

[Link] 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 a resource
held by P2, … , Pn-1 is waiting for a resource held by Pn.

• All four conditions must hold for a deadlock to occur.

• The four conditions are not independent of each other.
Resource-Allocation Graph
• A directed graph is called a System Resource Allocation Graph.
• The graph consists of a set of vertices V and a set of edges E.
• Set of Vertices:-
• P={P1, P2, …, Pn}:- Set of active Processes
• R={R1, R2, .., Rm}:- Set of Resources

• Set of Edges:-
• Request Edge:-
• A directed edge from process type Pi to resource type Rj (Pi -> Rj)

• Assignment Edge:-
• A directed edge from resource type Rj to process type Pi (Pi -> Rj)
• Processes • P= {P1, P2, P3}
• R= {R1, R2, R3, R4}
• Resource
…. • Request Edge= {P1->R1, P2->P3}
• Assignment Edge= {R1->P2, R3->P3,
R2->P2}
R1 R3

. . • Resource Instances
• One instance of R1
• One instance of R3
P3
• Two instance of R2
P1 P2 • Tree instance of R4

• Observation:
..
R2
…
• No Cycle:- No deadlock
• Cycle:- Deadlock may exist
R4
Example1 R1 Example 2
. R3
. .. P2

P1 P2 P3 R1
P1
P3

…
.
R2
R4 .. P4

R2
Example of Deadlock
P1 P2 P3 Process1 Process2

CD CD CD
Drive Drive Drive
CD
Printer1 Drive

P1 P2 P3

CD CD CD
Drive Drive Drive
Methods for Handling Deadlock
Three ways to deal with deadlock problems:
Prevention : Ensure that the system will never enter a
deadlock state

Avoidance: Ensure that the system will never enter an

unsafe state

Detection :Allow the system to enter a deadlock state and

then recover
 2. Hold and Wait
• Whenever a process requests a resource, it does not hold any
other resources.
• Protocol 1:- For each process, all its resources are allocated
before it begins execution.
• Protocol 2:- It allows a process to request resources only when
it has none.

Disadvantages
[Link] utilization may be low
2. Starvation is possible
3. No Preemption
• Preemption must hold.

• Protocol 1:-If a process is holding some resources and requests another resource
that cannot be immediately allocated to it(that is, the process must wait), then
all resources currently being held are pre-empted.
• Protocol 2:-
If a process requests some resources, we first check whether they are available.
If they are available, we allocate them.
If not, check are they allocated to some other resource which is also waiting for
additional resource. If so, we pre-empt the desired resources from the waiting
process and allocate to the requesting process.

Applicable for CPU registers and memory space but it cannot be applied to
resources as printers and tape drives.
4. Circular wait
• To impose a total ordering of all the resource types and
to require that each process requests in increasing order
of enumeration.
Deadlocks
Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection and Recover
Deadlock Prevention
• At least one of these conditions cannot hold, we can prevent the
occurrence of a deadlock

• Mutual Exclusion – not required for sharable resources; must hold for non-sharable resources

• Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold
any other resources
• Require process to request and be allocated all its resources before it begins execution,
• allow process to request resources only when the process has none
• Low resource utilization;
• starvation possible
Deadlock Prevention (Cont.)
• No Preemption –
• If a process that is holding some resources requests another resource that
cannot be immediately allocated to it, then all resources currently being held
are released
• Preempted resources are added to the list of resources for which the process
is waiting
• Process will be restarted only when it can regain its old resources, as well as
the new ones that it is requesting

• Circular Wait – impose a total ordering of all resource types, and require that
each process requests resources in an increasing order of enumeration
Deadlock Avoidance
• Requires that the system has some additional a priori
information available.
• Simplest and most useful model requires that each process declare the
maximum number of resources of each type that it may need

• The deadlock-avoidance algorithm dynamically examines the resource-

allocation state to ensure that there can never be a circular-wait
condition

• Resource-allocation state is defined by the number of available and

allocated resources, and the maximum demands of the processes
Safe State
• When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe state.
• System is in safe state if there exists a sequence <P1, P2, …, Pn> of all the processes is the systems
such that for each Pi, the resources that Pi can still request can be satisfied by
currently available resources + resources held by all the Pj, with j < i

• If Pi resource needs are not immediately available, then Pi can wait until all
Pj have finished
• When Pj is finished, Pi can obtain needed resources, execute, return
allocated resources, and terminate
• When Pi terminates, Pi +1 can obtain its needed resources, and so on
Safe, Unsafe , Deadlock State
Deadlock avoidance algorithm
• Single instance of a resource type
• Use a resource-allocation graph

• Multiple instances of a resource type

• Use the banker’s algorithm
Resource Allocation Graph
• Claim edge Pi - -> Rj process Pj may
request resource Rj; represented by a
dashed line

• Claim edge converts to request edge when

a process requests a resource

• Request edge converted to an assignment

edge when the resource is allocated to the
process

• When a resource is released by a process,

assignment edge reconverts to a claim
edge

• Resources must be claimed a priori in the

system
RAG Algorithm
• Suppose that process Pi requests a resource Rj

• The request can be granted only if converting the request

edge to an assignment edge does not result in the
formation of a cycle in the resource allocation graph
Banker’s Algorithm
• Multiple instances

• Each process must a priori claim maximum use

• When a process requests a resource it may have to wait

• When a process gets all its resources it must return them in a finite
amount of time
Data Structures for the Banker’s
Algorithm
• Let n = number of processes, and m = number of resources types.

• Available: Vector of length m. If available [j] = k, there are k instances of

resource type Rj available
• Max: n x m matrix. If Max [i, j] = k, then process Pi may request at most k
instances of resource type Rj
• Allocation: n x m matrix. If Allocation[i, j] = k then Pi is currently allocated k
instances of Rj
• Need: n x m matrix. If Need[i, j] = k, then Pi may need k more instances of Rj
to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

Resource-Request Algorithm for
Process Pi
Request = request vector for process Pi. If Requesti [j] = k then process Pi wants k
instances of resource type Rj
1. If Requesti <= Needi go to step 2. Otherwise, raise error condition, since
process has exceeded its maximum claim
2. If Requesti <=Available, go to step 3. Otherwise Pi must wait, since
resources are not available
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
 If safe - the resources are allocated to Pi
 If unsafe -Pi must wait, and the old resource-allocation state is restored
Safety Algorithm
1. Let Finish be vector of length n. Initialize:
work= available
Finish [i] = false for i = 0, 1, …, n- 1
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi <=work
If no such i exists, go to step 4
3. work= work + Allocationi
Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state.
Example of Banker’s Algorithm
• 5 processes P0 through P4;
3 resource types:
A (10 instances), B (5instances), and C (7 instances)
Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433
Deadlocks
Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection and Recover
Deadlock Prevention
• At least one of these conditions cannot hold, we can prevent the
occurrence of a deadlock

• Mutual Exclusion – not required for sharable resources; must hold for non-sharable resources

• Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold
any other resources
• Require process to request and be allocated all its resources before it begins execution,
• allow process to request resources only when the process has none
• Low resource utilization;
• starvation possible
Deadlock Prevention (Cont.)
• No Preemption –
• If a process that is holding some resources requests another resource that
cannot be immediately allocated to it, then all resources currently being held
are released
• Preempted resources are added to the list of resources for which the process
is waiting
• Process will be restarted only when it can regain its old resources, as well as
the new ones that it is requesting

• Circular Wait – impose a total ordering of all resource types, and require that
each process requests resources in an increasing order of enumeration
Deadlock Avoidance
• Requires that the system has some additional a priori
information available.
• Simplest and most useful model requires that each process declare the
maximum number of resources of each type that it may need

• The deadlock-avoidance algorithm dynamically examines the resource-

allocation state to ensure that there can never be a circular-wait
condition

• Resource-allocation state is defined by the number of available and

allocated resources, and the maximum demands of the processes
Safe State
• When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe state.
• System is in safe state if there exists a sequence <P1, P2, …, Pn> of all the processes is the systems
• such that for each Pi, the resources that Pi can still request can be satisfied by
currently available resources + resources held by all the Pj, with j < i

• If Pi resource needs are not immediately available, then Pi can wait until all
Pj have finished
• When Pj is finished, Pi can obtain needed resources, execute, return
allocated resources, and terminate
• When Pi terminates, Pi +1 can obtain its needed resources, and so on
Safe, Unsafe , Deadlock State
Deadlock avoidance algorithm
• Single instance of a resource type
• Use a resource-allocation graph

• Multiple instances of a resource type

• Use the banker’s algorithm
Resource Allocation Graph
• Claim edge Pi - -> Rj process Pj may
request resource Rj; represented by a
dashed line

• Claim edge converts to request edge when

a process requests a resource

• Request edge converted to an assignment

edge when the resource is allocated to the
process

• When a resource is released by a process,

assignment edge reconverts to a claim
edge

• Resources must be claimed a priori in the

system
RAG Algorithm
• Suppose that process Pi requests a resource Rj

• The request can be granted only if converting the request

edge to an assignment edge does not result in the
formation of a cycle in the resource allocation graph
Banker’s Algorithm
• Multiple instances

• Each process must a priori claim maximum use

• When a process requests a resource it may have to wait

• When a process gets all its resources it must return them in a finite
amount of time
Data Structures for the Banker’s
Algorithm
• Let n = number of processes, and m = number of resources types.

• Available: Vector of length m. If available [j] = k, there are k instances of

resource type Rj available
• Max: n x m matrix. If Max [i, j] = k, then process Pi may request at most k
instances of resource type Rj
• Allocation: n x m matrix. If Allocation[i, j] = k then Pi is currently allocated k
instances of Rj
• Need: n x m matrix. If Need[i, j] = k, then Pi may need k more instances of Rj
to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

Resource-Request Algorithm for
Process Pi
Request = request vector for process Pi. If Requesti [j] = k then process Pi wants k
instances of resource type Rj
1. If Requesti <= Needi go to step 2. Otherwise, raise error condition, since
process has exceeded its maximum claim
2. If Requesti <=Available, go to step 3. Otherwise Pi must wait, since
resources are not available
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
 If safe - the resources are allocated to Pi
 If unsafe -Pi must wait, and the old resource-allocation state is restored
Safety Algorithm
1. Let Finish be vector of length n. Initialize:
work= available
Finish [i] = false for i = 0, 1, …, n- 1
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi <=work
If no such i exists, go to step 4
3. work= work + Allocationi
Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state.
Example of Banker’s Algorithm
• 5 processes P0 through P4;
3 resource types:
A (10 instances), B (5instances), and C (7 instances)
Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433
Example of Banker’s Algorithm
• 5 processes P0 through P4;
3 resource types:
A (10 instances), B (5instances), and C (7 instances)
Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
P0 010 753 230
P1 302 322
P2 302 902
P3 211 222
P4 002 433
Example of Banker’s Algorithm
• 5 processes P0 through P4;
3 resource types:
A (10 instances), B (5instances), and C (7 instances)
Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
P0 030 753 210
P1 302 322
P2 302 902
P3 211 222
P4 002 433
Operating Systems (CS3000)

Lecture – 20
(Memory Management – 1)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 What is Memory?
2<M
• Physical device which stores Memory Hierarchy
Size
information temporarily or Speed

permanently.
• Primary memory – only large Register
storage media that the CPU
can access directly. Cache

Main Memory
• Secondary storage – extension
of main memory that provides Secondary Memory
large nonvolatile storage
capacity
 Execution of Program (Process)

• #include<stdio.h> • Process
int main(){ • A program in execution
char str[]=“Hello World\n”; • Present in the RAM
print(str); • Comprises of
} • Executable Instructions
• Stack
• Heap
Compile (gcc hello.c) • State in the OS (in the kernel)

Executable file Process

3
 Contiguous Memory Allocation

0xFFF.. • How we can execute

multiple programs?
• Using Swapping
Swap In • One process occupies RAM
User Program at a time
DISK • When one process
Swap Out completes, another
OS
process is allocated RAM
0

5
 Multiprogramming

Process 1 Process2 Process 3 Process 4

Multiprogramming

RAM

6
 Memory Management Scheme
• Multiple processes can occupy the RAM simultaneously
• Using Memory Management Scheme
• Contiguous
• Fixed
• Variable or Dynamic
• Non-Contiguous (Modern Scheme)

• OS maintains Partition Table in RAM.

• Allocated partition
• Free partition(hole)

7
 Fixed Scheme
• User memory size=25KB, no. of partition=5
• P0=4KB, P1=3KB, P2=6KB, P3=4KB, P4=5KB, P5=5KB
P5 5KB P3 5KB

P4 5KB P2 8KB
Internal
5KB fragmentation
P3 P1 4KB

5KB 2KB
P1

P0 5KB P0 6KB

OS OS

8
 Fixed Scheme
• The memory is divided into • Issues
a fixed number of partitions • Internal Fragmentation
• Limit in process size
• The number of partitions is
• Degree of multiprogramming
fixed. is limited
• Partition size can be equal
or unequal
• Degree of
multiprogramming depends
on the no. of partitions.

9
 Variable Scheme
• User memory size=25KB
• P1=10KB, P2=8KB, P3=6KB
• P2 completed, P4 arrives=9KB 1KB free
7KB free P3 6KB P3
15KB free

8KB
P2 P2

10KB P1 P1
P1 P1
OS OS OS OS

10
 Variable Scheme
• Initially, the memory will be • Advantages:
full contiguous free block. • No internal
• Whenever a request by a fragmentation
process comes, accordingly • No limitation on the
the partition will be made. number of processes
• Size of the process is
limited by the available
RAM size
• Issues
• External Fragmentation
• Solution:

11
 Memory Management Unit

• Logical Address: generated by the CPU; also referred to as

virtual address
• Physical Address: address seen by the memory unit

Memory-Management Unit (MMU)

• Hardware device that maps virtual to physical address

• In MMU scheme, adds the relocation register value to every address generated
by a user process

• The user program deals with logical addresses; it never sees the real physical addresses

12
 Memory Management Unit
Assume logical address is 20
Base address=10
Limit address= 40
Relocation address=12000

13
 Thank You
Any Questions?

14
Operating Systems (CS3000)

Lecture – 20
(Memory Management – 2)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Memory-Allocation Scheme
• First-Fit
• Allocate the first hole that is big enough
• Next-Fit
• Allocate the next hole that is big enough from the previous allocation
• Worst-Fit
• Allocate the largest hole; must also search the entire list
• Best-Fit
• Allocate the smallest hole that is big enough; must search entire list, unless
ordered by size
 Memory-Allocation Scheme
Ex: 200KB, 400KB, 150KB, 400KB

100 500 200 300 600

 Limitations of Contiguous Memory Management
• Entire process needs to be in RAM
• Allocation needs to be in contiguous memory
• Fragmentation
• Limit the size of the process by RAM-size
• Management of Partitions
 Modern Memory Management Schemes
Virtual Memory – Technique that allows only part of the program needs to be in
memory for execution
• Paging
• Segmentation
 Paging
• Paging is a memory-management scheme
allows the physical address space of a
process to be non-contiguous.

• Divide physical memory into fixed-sized

blocks called frames

• Divide logical memory into blocks of same

size called pages

• Keep track of all free frames

• To run a program of size n pages, need to

find n free frames and load program

• Set up a page table to translate logical to

physical addresses
 Address Translation Scheme
Address generated by CPU is divided into:

Page number (p) – used as an index into a page table which contains base address of each
page in physical memory

Page offset (d) – combined with base address to define the physical memory address that is
sent to the memory unit (no. Of bits required to represent the page size or word no of page)

frame number (f) – used to represent frame number which is a base address base address of
each page in physical memory

Page offset (d) – same as previously defined

 Address Translation Scheme
1. LA=29 bits
2. LAS=256 KW
3. PA=33 bits
4. PAS=64MW

5. LA 13 bits, PA=12 bits, Page size 1KW

Address Translation Scheme
Example: Address Translation Scheme
 Problems
1. Consider the virtual address space is 44KB. Physical address space is 24KB.
Page size=4KB. Find the (p, d) in logical and (f, d) in physical address.

2. Consider the physical memory space is 64MB and 32-bit virtual address space. Page size is 4KB,
what is the approximate size of page table?
(a) 2 MB (b) 3MB (c ) 4 MB (d) 6 MB
 Problems
3. Consider the virtual address space is 32 bit.
Page size=4KB. Page table entries of 4 byte. What is the approximate size of page table size?
(a)2MB (b) 3MB (c) 4 MB (d) 8MB

4. Consider the computer system implements 40 bit virtual address and Page size is 16KB, what is
the approximate size of page table, if each page table entry is 48 bits.
(a)398MB (b) 48 MB(c) 192 MB(d) 96MB
 Hardware Implementation of Page-table
Case1: Implement the page table as a set of dedicated registers

Problem: This can be used only when page table is small.

Case2:-Keep the page table in main memory and a page table base register (PTBR)
Problem:- 2 memory accesses (one for page table and one for actual byte)

Solution of Case 2
 TLB is high-speed cache memory.
 It consists of two parts : key and value
 Search is fast
 Few of the page-table entries
 When logical addresses is generated by the CPU, its page number is presented to the TLB.
 If page number is found, its frame number is easily available and used to access the memory.
 If not found in the TLB, a memory reference to the page table is made.
 After accessing, we add the page number and frame number to the TLB.
Paging With TLB
 Effective Access Time
• Associative Lookup = e time unit
• Assume memory cycle time is 1 microsecond
• Hit ratio (a) – percentage of times that a page number is found in TLB;

• Effective Access Time (EAT)

EAT = a(e+m) + (e+2m)(1 – a)
 Problem 1
Consider that 80-percent hit ratio means that we find the desired page number in the
TLB 80 percent of the time.
Assume it takes 20 nanoseconds to search the TLB and 100 nanoseconds to access
memory.
Find the effective memory-access time.

Sol:-
 Problem 1 Solution
Consider that 80-percent hit ratio means that we find the desired page number in the
TLB 80 percent of the time.
Assume it takes 20 nanoseconds to search the TLB and 100 nanoseconds to access
memory.
Find the effective memory-access time.

Sol:-EAT= TLB hit (TLB access time+Memeory acc time)+(1-TLB hit) (TLB AT+2MAT)
=0.8(20+100)+0.2(20+200)
=96+44
= 140ns
 Problem 2
If effective memory access time is given as 160ns. We assume 90-percent hit ratio
means that we find the desired page number in the TLB 90 percent of the time.
100 nanoseconds to access memory.
Find the TLB access time.

Sol:-
 Problem 2
If effective memory access time is given as 160ns. We assume 90-percent hit ratio
means that we find the desired page number in the TLB 90 percent of the time.
100 nanoseconds to access memory.
Find the TLB access time.

Sol:-EAT= TLB hit (TLB access time+Memeory acc time)+(1-TLB hit) (TLB AT+2MAT)
160=0.9(T+100)+0.1(T+200)
160=1T+90+20
T= 50ns(TLB access time)
 Memory Protection Using bit
Valid-invalid bit attached to each entry in the page table:
• “valid” indicates that the associated page is in the process logical address space, and is
thus a legal page
• “invalid” indicates that the page is not in the process logical address space
 Shared Pages Concept
 An advantages of paging is the possibility of sharing common code.
 This is particularly important in time-sharing environment.

Shared code
• One copy of read-only (reentrant) code shared among processes (i.e., text
editors, compilers, window systems).
• Shared code must appear in same location in the logical address space of
all processes

Private code and data

• Each process keeps a separate copy of the code and data
• The pages for the private code and data can appear anywhere in the logical
address space
Example
 Shared Pages Concept
• Assume 40 users using text editors
• Text editor size= 150 KB
• Data size=20 KB

• Non-Shared Memory
Total Size=6800KB

• Shared Memory
Total Size=950KB
 Thank You
Any Questions?
Operating Systems (CS3000)

Lecture – 20
(Memory Management – 3)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Demand Paging
• Bring a page into memory only when it is needed

• Page is needed -> reference to it

• invalid reference -> abort
• Not-in-memory ->bring to memory

2
Page Table When Some Pages Are Not in Main
Memory

3
 Page Fault
If there is a reference to a page, first reference to that page will trap to operating system: page fault

1. OS looks at Page table to decide:

Invalid reference -> abort
Just not in memory
2. Get empty frame (Swap Out some frames from main memory)
3. Swap In page into frame
4. Reset tables
5. Set validation bit = v
6. Restart the instruction that caused the page fault

4
Steps in Handling a Page Fault

5
 Page Fault
Page Fault Rate 0 <=p <=1.0
if p = 0 no page faults
if p = 1, every reference is a fault

Effective Access Time (EAT)

EAT = (1 – p) x memory access + p (page fault overhead
+ swap page out
+ swap page in
+ restart overhead)

6
 Page Fault
Memory access time = 200 nanoseconds = 0.2 microsecond

Average page-fault service time = 8 milliseconds

EAT = (1 – p) x 0.2 + p (8 milliseconds)

= (1 – p) x 0.2 + p x 8,000
= 0.2 + p x 8000

If one access out of 1,000 causes a page fault, then

EAT = 8.2 microseconds.

7
 Problem 1
Consider a system which has page fault service time =100ns.
Page fault rate is 65%.
Main memory access time is 1ns.
What is effective memory access time?

Sol: EAT=

8
 Problem 2
Let the page fault service time be 10ms in a computer with average memory access
time being 20ns.
If one page fault is generated for every 10^6 memory accesses,
what is the effective access time (approx.) for the memory?

Solution:
EAT=

9
 Page Replacement
• Page replacement – find some page in memory, but not really in use, swap it out
• algorithm
• performance – want an algorithm that will result in a minimum number of page faults
• The same page may be brought into memory several times

• Algorithm Structure
1. Find the location of the desired page on the disk

2. Find a free frame:

- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to select a victim frame

3. Bring the desired page into the (newly) free frame; update the page and frame tables

4. Restart the process

10
Page Replacement

11
 Frame Allocation Schemes
• Each process needs minimum number of pages

• Two major allocation schemes

• Equal allocation – For example, if there are 100 frames and 5 processes, give each
process 20 frames.
• Proportional allocation – Allocate according to the size of process

si size of process pi
m 64
S  si
si 10
m total number of frames s2 127
s 10
ai allocation for pi  i m a1 
137
64 5
S
127
a2  64 59
137

12
 Allocation Schemes
• Priority allocation
• Use a proportional allocation scheme using priorities rather than size
• If process P generates a page fault,
i
• select for replacement one of its frames
• select for replacement a frame from a process with lower priority number

Replacement Schemes
• Global replacement – process selects a replacement frame from the set of all frames; one process
can take a frame from another
• Local replacement – each process selects from only its own set of allocated frames

13
 FIFO-Page Replacement
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• 3 frames (3 pages can be in memory at a time per process)

Number of fault=

• 4 frames

Number of fault=

Belady’s Anomaly: more frames  more page faults

14
Normal vs Belady’s Anamoly Graph

15
FIFO-Page Replacement

16
 Problem
1. A system uses FIFO policy for page replacement. It has 4 page frames with no
pages loaded to begin with.
The system first accesses 100 distinct pages in some order and then accesses the
same 100 pages but now in the reverse order.
How many page faults will occur?

Solution :

17
 Optimal Page Replacement
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• Replace page that will not be used for longest period of time
• 3 frames

Number of page fault=7

• 4 frames

Number of page fault=6

How do you know this?

Used for measuring how well your algorithm performs

18
Optimal Page Replacement

19
 LRU Page Replacement
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3 frames

4 frames

20
LRU Page Replacement

21
 Thrashing
If a process does not have “enough” pages, the page-fault rate is very high. This leads to:
• low CPU utilization
• OS thinks that it needs to increase the degree of multiprogramming another process added to the
system

Thrashing = a process is busy swapping pages in and out

22
 Thank You
Any Questions?

23
Operating Systems (CS3000)

Lecture – 20
(Memory Management – 4)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
 Structure of the Page Table
• Many modern computer systems support a large logical address space,
in such an environment, the page table itself becomes excessively large

Types of Page table

• Hierarchical Paging

• Hashed Page Tables

• Inverted Page Tables

 2-Level Page Table
• Break up the logical address space
into multiple page tables
• 2-level paging, in which page table
itself is also paged.
• A logical address (on 32-bit machine
with 1K page size) is divided into:
• a page number consisting of 22
bits
• a page offset consisting of 10 bits
• Since the page table is paged, the
page number is further divided into:
• a 12-bit page number
• a 10-bit page offset
2-Level Page Table
3-Level Page Table
 Problems 1
Consider a three level paging scheme with a TLB. Assume no page fault occurs. It
takes 20 ns to search the TLB and 100 ns to access the physical memory. If TLB hit
ratio is 80%, the effective memory access time is _______ ns.

Solution:
EAT=
 Problems 1
Consider a three level paging scheme with a TLB. Assume no page fault occurs. It
takes 20 ns to search the TLB and 100 ns to access the physical memory. If TLB hit
ratio is 80%, the effective memory access time is _______ ns.

Solution:
EAT= TLB hit(TLB acc. Time +Memory acc. time) +TLB miss(TLB acc. Time+ (L+1)
Memory access time)

= 0.8(120)+0.2(420)
=96+84
=180 ns
 Hashed Page Table
Used for handling address spaces larger than 32 bits (or large address
space)

• Hash value is the virtual page number.

• This page table contains a chain of elements hashing to the same
location
• Steps for hashed paging
• The virtual page number in the virtual address is hashed into the hash table.
• The virtual page number is compared with field 1 in the first element in the linked list.
• If match, corresponding page frame is used to form the physical address.
• If no match, subsequent entries in the linked list and searched for a matching virtual page
number.
Hashed page table
 Inverted Page Table
• One entry for each real page of memory
• Entry consists of the virtual address of the page stored in that real
memory location, with information about the process that owns that page
• Decreases memory needed to store each page table, but increases time
needed to search the table when a page reference occurs
• Use hash table to limit the search to one — or at most a few — page-
table entries
Inverted page table
 Problem 1

In a 64-bit machine, with 2 GB RAM, and 8 KB page size, how many

entries will be there in the page table if it is inverted?.

Sol:- PAS =2GB= 2^31

Page size= 8KB= 2^13

Number of entries in page table= 2^31/2^13= 2^28.

 Problem 2
Consider a system with logical address of 34 bits and physical address of 39 bits.
Page size is 16KB. The memory is byte addressable. Page-table entry size is 8 bytes.
Calculate the page table size in conventional paging and inverted paging.

Solution:
 Problem 2
Consider a system with logical address of 34 bits and physical address of 39 bits.
Page size is 16KB. The memory is byte addressable. Page-table entry size is 8 bytes.
Calculate the page table size in conventional paging and inverted paging.

Solution: LAS= 2^34

PAS= 2^39
Page size= 2^14
Number of pages= (2^34)/(2^14)= 2^20
Number of frames= (2^39)/(2^14)=2^25
Conventional page table size= no of pages x entry size= 2^20 x 8= 8MB
Inverted page table size= no of frames x entry size= 2^25 x 8= 256MB
 Thank You
Any Questions?
Operating Systems (CS3000)

Lecture – 20
(Memory Management – 5)

Dr. Sanjeet Nayak

Assistant Professor
Department of Computer Sc. and Engg.
 Segmentation
• Non-contiguous memory allocation techniques like paging.
• Unlike paging in segmentation, the processes are not divided into fixed-
size pages.
• Processes are divided into several modules called segments which
improve the visualization for the users.
User Views of a program
 Segmentation Architecture
• Logical address consists of a two tuple:
<segment-number, offset>

• Segment table – maps two-dimensional physical addresses; each table entry has:
base – contains the starting physical address where the segments reside in memory
limit – specifies the length of the segment

• Segment-table base register (STBR) points to the segment table’s location in memory

• Segment-table length register (STLR) indicates number of segments used by a program;

segment number s is legal if s < STLR
Segmentation Hardware
Example of Segmentation
 Thank You
Any Questions?
Operating Systems (CS3000)

Lecture – 20
(Disk Management – 1)

Dr. Jaishree Mayank

Assistant Professor
Department of Computer Sc. and Engg.
Disk Structure

• Each Disk has platter

• Each platter has two
surfaces.
• Each surface is divided
into tracks.
• Each track is divided
into sector.
• Sector store the data
 Problems 1

Consider a Disk that has 16 platters. Each platter is divided into two surfaces.
Every surface is divided into 1K tracks. Every track is divided into 512 sectors.

Each sector can store 2KB of data.

(a)What is the capacity of the disk?

(b) How many bits are required to identify the sector?

Consider a Disk that has 16 platters. Each platter is divided into two surfaces.
Every surface is divided into 1K tracks. Every track is divided into 512 sectors.

Each sector can store 2KB of data.

(a)What is the capacity of the disk?

(2^4) x 2 x (2^10) x (2^9) x (2^11)=(2^35)=32GB

(b) How many bits are required to identify the sector?

4+1+10+9=24 bits
 Disk Operations
The read-write header can be on any particular track.

•First the header is moved from current track to desired track.

•Then the header will wait for the desired sector as the disk is moving in clockwise or
anticlockwise:

•Seek Time:-The amount of time taken to move the r/w head from its current position to
the desired track.

•Rotational Latency:-The amount of time taken to rotate the track when the read/write
header comes to exact position (sector)

Rotational latency=1/2 rotation time(avg)

• Transfer Time:-The amount of time is taken to transfer the
required data is called Transfer time.

• Transfer time depends on the rotational rate of the disk and the
total size of the track.

• Transfer Rate:-The number of bytes transferred per unit time.

• Total Access Time= Seek Time+ Rotational Latency+Tranfser time

 Problem 1

Consider a disk that has average seek time of 30 s.

• The rotational rate of 360 rpm.
• Each track has 512 sectors and each size is 512 KB.
What is the time required to read four successive sectors?
Av. Seek Time= 30ns
Av. Rotational latency= (60/360)x(1/2)
Transfer Time
In one Rotation we transfer= 512 sectors x 512 Kbytes= 2^28=256MB
Required data is from 4 sectors= 4 x 512KB= 2MB
256MB in 60/360 s
2MB=(60/360)*(2/256) sec
Total Access Time= seek Time+ Rotational latency+ Transfer Time
 Disk Scheduling
For efficient use of disk drives, the disk must have
•fast access time
•large disk bandwidth: the total number of bytes transferred/the total time between the first request for service and the
completion of the last transfer.

Access time has two major components

• Seek time is the time for the disk to move the heads to the cylinder containing the desired
sector
• Minimize seek time
• Seek time =seek distance

• Rotational latency is the additional time waiting for the disk to rotate the desired
sector to the disk head
FCFS Disk Scheduling
 SSTF Disk Scheduling

SSTF:-It chooses the pending request closest to the current head position.

•It perform well compared to FCFC

•It may cause starvation of some requests.

SSTF Disk Scheduling
 SCAN and C-SCAN Disk Scheduling
SCAN:-
• The disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the
other end of the disk, where the head movement is reversed and servicing continues.

• SCAN algorithm Sometimes called the elevator algorithm

C-SCAN (Circular SCAN)

• Provides a more uniform wait time than SCAN

• The head moves from one end of the disk to the other, servicing requests as it goes
• When it reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any
requests on the return trip
• Treats the cylinders as a circular list that wraps around from the last cylinder to the first one
SCAN Disk Scheduling
C-SCAN Disk Scheduling
 LOOK and C-LOOK Disk Scheduling
LOOK:-

• Arm only goes as far as the last request in each direction, then, where the head movement is reversed and
servicing continues

C-LOOK (Circular SCAN)

• Arm only goes as far as the last request in each direction, then reverses direction immediately, without first
going all the way to the end of the disk
LOOK Disk Scheduling
C-LOOK Disk Scheduling
 Problem
A disk has 200 tracks (numbered 0 through 199).

At a given time, it was servicing the request of reading data from track 120, and at the previous request,
service was for track 90.

The pending requests (in order of their arrival) are for track numbers. 30 70 115 130 110 80 20 25.

How many times will the head change its direction for the disk scheduling policies SSTF(Shortest Seek
Time First), FCFS(First Come Fist Serve), SCAN and C-SCAN

Solution: SSTF
FCFS
SCAN
C-SCAN
Problem
 Problem
A disk has 200 tracks (numbered 0 through 199).

At a given time, it was servicing the request of reading data from track 120, and at the previous request,
service was for track 90.

The pending requests (in order of their arrival) are for track numbers. 30 70 115 130 110 80 20 25.

How many times will the head change its direction for the disk scheduling policies SSTF(Shortest Seek
Time First), FCFS(First Come Fist Serve), SCAN and C-SCAN

Solution: SSTF=3
FCFS=4
SCAN=1
C-SCAN=2
 Thank You
Any Questions?