Operating Systems &
Computer Architecture
CT049-3-1-OS&CA
Ver: VD1
Memory Management
Learning Outcomes
At the end of this section, YOU should be able to:
• Describe Paging and Segmentation
• Perform page replacement calculations using various Page Replacement
Algorithms
CT049-3-1-OS&CA Memory Management 2 of 39
Topics we will cover
• Memory Management
• Logical and Physical Memory
• Memory Partitioning
• Virtual Memory
• Demand Paging
• Demand Segmentation
• Page fault
• Page replacement
• Page replacement algorithms
• First In First Out
• Least Recently Used
• Optimal
CT049-3-1-OS&CA Memory Management 3 of 39
Virtual Memory
• Separation of user logical memory from
physical memory.
• Allows for large virtual memory to be
provided for programmers even though
physical memory is small.
• Programmers do not have to worry about
space and writing overlay codes.
• Virtual memory implemented using
demand paging or demand segmentation.
CT049-3-1-OS&CA Memory Management 4 of 39
Paging
• Physical memory is broken into fixed-
sized blocks called frames.
• Logical memory is also broken into blocks
of the same size called pages.
• When a process is executed, its pages are
loaded into any available memory frame
from the backing store.
CT049-3-1-OS&CA Memory Management 5 of 39
Paging
page 0 0 1 0
page 1 1 4 1 page 0
page 2 2 3 2
page 3 3 7 3 page 2
logical memory page table
4 page 1
7 page 3
physical memory
CT049-3-1-OS&CA Memory Management 6 of 39
Demand Paging
• A process resides in secondary memory, usually a
disk.
• When a process needs to be executed, it is paged
to memory.
• The whole process is not paged, only pages that
are needed are brought in.
• A pager decides which pages to bring into memory.
• Advantages:-
– avoid reading pages that will not be used
– decreases paging time
– decreases physical memory needed
CT049-3-1-OS&CA Memory Management 7 of 39
Demand Paging
Memory
Secondary
Storage
Program A Swap Out
0 1 2 3
4 5 6 7
8 9 10 11
Program B
12 13 14 15
Swap In
16 17 18 19
CT049-3-1-OS&CA Memory Management 8 of 39
Demand Segmentation
• What is Segmentation?
– Segmentation is a memory-management
scheme that supports a user view of memory.
– A logical address space is a collection of
segments. Each segment has a name and a
length.
– The addresses specify both the segment
name and the offset within the segment.
CT049-3-1-OS&CA Memory Management 9 of 39
Demand Segmentation
• Most efficient virtual memory storage
method.
• Needs significant amount of hardware
requirements.
• Not all paging systems use segmentation.
• Instead of allocating pages in memory,
allocate segments.
• Segment descriptors keeps track of
segments.
CT049-3-1-OS&CA Memory Management 10 of 39
Demand Segmentation
Figure 8.24 pg 275 0000
stack
segment 3 1400
Limit Base segment 0
0 1000 1400
symbol 2400
subroutine 1 400 6300
table 3200
2 400 4300
segment 0 segment 4
3 1100 3200 segment 3
4 1000 4700 4300
main segment 2
SQRT Segment table 4700
program
segment 4
segment 1 segment 2
5700
6300
Physical memory 6700 segment 1
Logical address space
CT049-3-1-OS&CA Memory Management 11 of 39
Shared Segmentation
0
Limit Base
editor 43062
0 25286 43062
segment 0
1 4425 68348
editor
data 1 segment table process P1
segment 1 68348
data 1
72773
logical memory process P1
editor Limit Base
segment 0 90003
0 25286 43062 data 2
1 8850 90003 98553
data 2 segment table process P2
1298553
segment 1
physical memory
logical memory process P2
Sharing of segments in a segmented memory system
CT049-3-1-OS&CA Memory Management 12 of 39
Quick Review Questions
1.How does demand paging work?
2.How does demand segmentation work?
CT049-3-1-OS&CA Memory Management 13 of 39
Follow Up Assignment
1.What is the difference between demand
paging and demand segmentation?
CT049-3-1-OS&CA Memory Management 14 of 39
Page Fault
• A page fault occurs when:-
– a process tries to use a page that is not in
memory.
– an operating system interrupt occurs as a
result of trying to access a missing page.
CT049-3-1-OS&CA Memory Management 15 of 39
Steps in Handling Page Fault
operating 3 locate page on backing store
system
reference
1 2 trap
i backing
load M store
6 page table Free
restart
frame
instruction
5 4
reset bring in
page memory
table page
program physical
execution memory
CT049-3-1-OS&CA Memory Management 16 of 39
Page Fault
• Steps in handling a page fault:-
– locate the missing page
– find free memory frame
– copy into physical memory
– reset the page table
– restarts the instructions
CT049-3-1-OS&CA Memory Management 17 of 39
Page Replacement
• What if there are no free frames?
– find a frame that is not currently being used
and free it.
– use a page replacement algorithm to find a
free frame.
CT049-3-1-OS&CA Memory Management 18 of 39
Page Replacement
• How to free a frame?
– find a frame not currently used.
– copy its contents to disk.
– change the page table to indicate that the
page is no longer in memory.
– newly free frame can be used to store the
page that resulted in the page fault.
CT049-3-1-OS&CA Memory Management 19 of 39
Page Replacement
• The string of memory reference is called
a reference string.
• For a given page, we need to consider
only the page number, not the entire
address.
CT049-3-1-OS&CA Memory Management 20 of 39
Page Replacement
• For example, if we trace a particular
process, we might record the following
address sequence:-
0100, 0432, 0101, 0612, 0102, 0103, 0104
0101, 0611, 0102, 0103, 0104, 0101, 0610
0102, 0103, 0104, 0102, 0609, 0102, 0105
• which at 100 bytes per page is reduced to
the following reference string
1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1
CT049-3-1-OS&CA Memory Management 21 of 39
Page Replacement
frame valid-invalid
bit
swap
2
change to 1out
O i invalid victim
page O
F v 4
F victim
reset page
3 F
table for new
page swap
desired backing
page in store
page table
physical memory
CT049-3-1-OS&CA Memory Management 22 of 39
Page Replacement
• In the previous example page O was
previously loaded into memory.
• Page O is now no longer needed.
• Page F needs to be brought into physical
memory.
• As page O is no longer needed it becomes
the victim page and is replaced with page
F.
CT049-3-1-OS&CA Memory Management 23 of 39
Page Replacement Algorithms
• Every operating system has its own
unique page replacement algorithm.
• In selecting a particular algorithm we want
the one with the lowest page fault rate.
• Types of page replacement algorithms:-
– First In First Out
– Optimal
– Least Recently Used
CT049-3-1-OS&CA Memory Management 24 of 39
First In First Out
• Simplest page replacement algorithm.
• Easily implemented.
• Algorithm uses the age of the page as the
criteria to perform page replacement.
• The age of the page is the amount of time the
page has spent in memory.
• Oldest page is the victim.
• All other pages are lined up in the order of
highest page to be sacrificed.
CT049-3-1-OS&CA Memory Management 25 of 39
First-in-first-out (FIFO)
reference string
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
Number of Page Faults : 15
Perform an Analysis of the First-In-First-Out (FIFO) Algorithm for the following
string of memory reference addresses. Assume that there are three frames available
within the memory for holding pages.
CT049-3-1-OS&CA Memory Management 26 of 39
First-in-first-out (FIFO)
• The disadvantage of this technique is
that the oldest page could be very much
in demand.
• When the oldest page is replaced there
will be an immediate page fault.
• FIFO suffers from BELADY’S
ANOMALY.
CT049-3-1-OS&CA Memory Management 27 of 39
BELADY’S ANOMALY
• BELADY was one of the pioneers of modern operating
systems who did extensive studies on Page Replacement
schemes.
• On the basis of logical thinking, as the number of memory
frames are increased, the number of page faults
decreases.
• But BELADY, after conducting extensive experiments,
found that for certain memory reference strings, as the
number of memory frames are increased the number of
page faults increases.
• BELADY’S observations contradicted the commonly
accepted dogma, and instead of ‘burning him on the
stake’, his results were classified as BELADY’S
ANOMALY.
CT049-3-1-OS&CA Memory Management 28 of 39
First-in-first-out (FIFO)
16
14
12
number of page faults
10
8
0 1 2 3 4 5 6 7
number of frames
page-fault curve for FIFO replacement on a reference string
CT049-3-1-OS&CA Memory Management 29 of 39
Optimal
• Results from Belady’s anomaly resulted
in a search for a new algorithm.
• An algorithm that provides the lowest
page fault with a fixed number of frames.
• Does not suffer from Belady’s anomaly.
• Replaces the page that will not be used
for the longest period of time.
• Difficult to implement, requires future
knowledge of the reference string.
CT049-3-1-OS&CA Memory Management 30 of 39
Optimal Algorithm
reference string
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
Replace the page that will not be
Number of Page Faults: 9 used for the longest period of time
Perform an Analysis of the Optimal Algorithm for the following string of memory
reference addresses. Assume that there are three frames available within the
memory for holding pages.
CT049-3-1-OS&CA Memory Management 31 of 39
Least Recently Used
• Associates each page with time of when
the page was last used.
• When a page needs to be replaced, the
page that has not been used the for the
longest period will be chosen.
• Technique of looking backwards.
CT049-3-1-OS&CA Memory Management 32 of 39
Least Recently Used
reference string
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
Number of Page Faults: 12
Perform an Analysis of the Least recently used for the following string of memory
reference addresses. Assume that there are three frames available within the
memory for holding pages.
CT049-3-1-OS&CA Memory Management 33 of 39
Thrashing
• A condition where there is high page
replacement activity.
• A process spends more time replacing
pages than processing.
• Causes CPU utilisation to drop.
• System throughput reduces and page
fault rate increases.
CT049-3-1-OS&CA Memory Management 34 of 39
Thrashing
• A process is thrashing if it is spending more
time paging than executing.
CPU Utilisation
degree of multiprogramming
CT049-3-1-OS&CA Memory Management 35 of 39
Question
1. You are given the following memory
references:-
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
How many page faults would occur for
the 3 different replacement algorithms,
assuming the system has various
settings of three, four and five frames?
CT049-3-1-OS&CA Memory Management 36 of 39
Summary of Main Teaching
Points
• Virtual memory system is implemented using a technique
called demand paging or demand segmentation, this
allows for a process larger then the system physical
memory to be executed.
• Demand paging only brings in pages i that are needed
into memory.
• Demand segmentation allocated memory in segments.
• Demand paging and demand segmentation takes the
responsibility of from the programmer to code using
techniques for overlays, fixed or variable partitions.
CT049-3-1-OS&CA Memory Management 37 of 39
Summary of Main Teaching
Points
• Page faults occur when a page that is needed is found in memory.
• Page replacements are based on trying to find free frames.
• Page replacement algorithms are used when there exists no free
frames.
• The page replacement algorithms are first in first out, optimal and
least recently used.
– First in first out replaces the oldest page.
– Optimal replaces the page that is least likely to be used.
– Least recently used replaces the page that is has not been used
recently.
• Thrashing occurs when page replacement activities occurs more
then process execution.
CT049-3-1-OS&CA Memory Management 38 of 39
END
Q&A
CT049-3-1-OS&CA Memory Management 39 of 39
