Chapter 9: Virtual Memory
Operating System Concepts Essentials – 9th Edition Silberschatz, Galvin and Gagne ©2013
Background
Code needs to be in memory to execute, but entire program rarely used.
Entire program code not needed at same time.
Consider ability to execute partially-loaded program:
User written error handling routines are used only when an error occurred in the
data or computation.
Certain options and features of a program may be used rarely.
Many tables are assigned a fixed amount of address space even though only a
small amount of the table is actually used.
The ability to execute a program that is only partially in memory would counter
many benefits.
Less number of I/O would be needed to load or swap each user program into
memory.
A program would no longer be constrained by the amount of physical memory
that is available.
Each user program could take less physical memory, more programs could be
run the same time, with a corresponding increase in CPU utilization and
throughput.
Operating System Concepts Essentials – 9th Edition 9.2 Silberschatz, Galvin and Gagne ©2013
Virtual Memory
Virtual Memory is a storage scheme that provides user an illusion of having a very big
main memory. This is done by treating a part of secondary memory as the main
memory.
In this scheme, User can load the bigger size processes than the available main
memory by having the illusion that the memory is available to load the process.
Instead of loading one big process in the main memory, the Operating System loads
the different parts of more than one process in the main memory.
By doing this, the degree of multiprogramming will be increased and therefore, the
CPU utilization will also be increased.
Virtual address space – logical view of how process is stored in memory.
Usually start at address 0, contiguous addresses until end of space.
Meanwhile, physical memory organized in page frames.
MMU must map logical to physical address.
Operating System Concepts Essentials – 9th Edition 9.3 Silberschatz, Galvin and Gagne ©2013
How Virtual Memory Works?
In modern word, virtual memory has become quite common these days.
In this scheme, whenever some pages needs to be loaded in the main memory for the
execution and the memory is not available for those many pages, then in that case,
instead of stopping the pages from entering in the main memory, the OS search for
the RAM area that are least used in the recent times or that are not referenced and
copy that into the secondary memory to make the space for the new pages in the
main memory.
Since all this procedure happens
automatically, therefore it makes the
computer feel like it is having the unlimited
RAM.
Virtual memory can be implemented via:
Demand paging
Demand segmentation
Operating System Concepts Essentials – 9th Edition 9.4 Silberschatz, Galvin and Gagne ©2013
Virtual Memory is Larger Than Physical Memory
Operating System Concepts Essentials – 9th Edition 9.5 Silberschatz, Galvin and Gagne ©2013
Demand Paging
A demand paging system is quite similar to a
paging system with swapping where
processes reside in secondary memory and
pages are loaded only on demand, not in
advance.
When a context switch occurs, the operating
system does not copy any of the old
program’s pages out to the disk or any of the
new program’s pages into the main memory
Instead, it just begins executing the new
program after loading the first page and
fetches that program’s pages as they are
referenced.
While executing a program, if the program
references a page which is not available in
the main memory because it was swapped
out a little ago, the processor treats this
invalid memory reference as a page
fault and transfers control from the program
to the operating system to demand the page
back into the memory.
Operating System Concepts Essentials – 9th Edition 9.6 Silberschatz, Galvin and Gagne ©2013
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated
(v in-memory – memory resident, i not-in-memory)
Initially valid–invalid bit is set to i on all entries
Example of a page table snapshot:
Frame # valid-invalid bit
v
v
v
v
i
….
i
i
page table
During MMU address translation, if valid–invalid bit in page table entry
is i page fault
Operating System Concepts Essentials – 9th Edition 9.7 Silberschatz, Galvin and Gagne ©2013
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts Essentials – 9th Edition 9.8 Silberschatz, Galvin and Gagne ©2013
Page Fault
If there is a reference to a page, first reference to that page will trap
to operating system: page fault.
1. Operating system looks at another table to decide:
Invalid reference abort
Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault
Operating System Concepts Essentials – 9th Edition 9.9 Silberschatz, Galvin and Gagne ©2013
Steps in Handling a Page Fault
Operating System Concepts Essentials – 9th Edition 9.10 Silberschatz, Galvin and Gagne ©2013
What Happens if There is no Free Frame?
Page replacement – find some page in memory, but not really in
use, page it out.
Algorithm –replace the page.
Performance – want an algorithm which will result in minimum
number of page faults.
Same page may be brought into memory several times.
Operating System Concepts Essentials – 9th Edition 9.11 Silberschatz, Galvin and Gagne ©2013
Basic Page Replacement
1. Find the location of the desired page on 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.
- Write victim frame to disk if dirty.
3. Bring the desired page into the (newly) free frame; update the page and frame tables.
4. Continue the process by restarting the instruction that caused the trap.
Operating System Concepts Essentials – 9th Edition 9.12 Silberschatz, Galvin and Gagne ©2013
Page Replacement
Operating System Concepts Essentials – 9th Edition 9.13 Silberschatz, Galvin and Gagne ©2013
Page Replacement Algorithms
Page-replacement algorithm
Want lowest page-fault rate on both first access and re-access.
Evaluate algorithm by running it on a particular string of memory references
(reference string) and computing the number of page faults on that string.
String is just page numbers, not full addresses.
Repeated access to the same page does not cause a page fault.
Results depend on number of frames available.
In all our examples, the reference string of referenced page numbers is:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Operating System Concepts Essentials – 9th Edition 9.14 Silberschatz, Galvin and Gagne ©2013
First-In-First-Out (FIFO) Algorithm
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1.
3 frames (3 pages can be in memory at a time per process).
15 page faults
Operating System Concepts Essentials – 9th Edition 9.15 Silberschatz, Galvin and Gagne ©2013
Page Faults vs. Number of Frames
Operating System Concepts Essentials – 9th Edition 9.16 Silberschatz, Galvin and Gagne ©2013
FIFO Illustrating Belady’s Anomaly
Belady’s Anomaly: Adding more frames sometimes can cause more page faults!
Consider: 1,2,3,4,1,2,5,1,2,3,4,5
Operating System Concepts Essentials – 9th Edition 9.17 Silberschatz, Galvin and Gagne ©2013
Optimal Algorithm
Replace page that will not be used for longest period of time.
How do you know this?
Not easy to read the future.
Operating System Concepts Essentials – 9th Edition 9.18 Silberschatz, Galvin and Gagne ©2013
Least Recently Used (LRU) Algorithm
Use past knowledge rather than future.
Replace page that has not been used in the most amount of time.
Operating System Concepts Essentials – 9th Edition 9.19 Silberschatz, Galvin and Gagne ©2013
Thrashing
At any given time, only a few pages of any process are in the main memory and
therefore more processes can be maintained in memory.
Furthermore, time is saved because unused pages are not swapped in and out of
memory.
However, the OS must be clever about how it manages this scheme. In the steady-
state practically, all of the main memory will be occupied with process pages, so that
the processor and OS have direct access to as many processes as possible.
Thus when the OS brings one page in, it must throw another out. If it throws out a
page just before it is used, then it will just have to get that page again almost
immediately.
Too much of this leads to a condition called Thrashing.
The system spends most of its time swapping pages rather than executing
instructions. So a good page replacement algorithm is required.
Operating System Concepts Essentials – 9th Edition 9.20 Silberschatz, Galvin and Gagne ©2013
Continue…
In the given diagram, the initial degree of multiprogramming up to some extent of
point(lambda), the CPU utilization is very high and the system resources are utilized
100%. But if we further increase the degree of multiprogramming the CPU utilization
will drastically fall down and the system will spend more time only on the page
replacement and the time is taken to complete the execution of the process will
increase. This situation in the system is called thrashing.
Operating System Concepts Essentials – 9th Edition 9.21 Silberschatz, Galvin and Gagne ©2013
Continue…
Causes of Thrashing :
High degree of multiprogramming : If the number of processes keeps on
increasing in the memory then the number of frames allocated to each process will be
decreased. So, fewer frames will be available for each process. Due to this, a page
fault will occur more frequently and more CPU time will be wasted in just swapping in
and out of pages and the utilization will keep on decreasing. For example:
Let free frames = 400.
Case 1: Number of process = 100.
Then, each process will get 4 frames.
Case 2: Number of processes = 400 .
Each process will get 1 frame.
Case 2 is a condition of thrashing, as the number of processes is increased, frames per process
are decreased. Hence CPU time will be consumed in just swapping pages.
Lacks of Frames: If a process has fewer frames then fewer pages of that process
will be able to reside in memory and hence more frequent swapping in and out will be
required. This may lead to thrashing. Hence sufficient amount of frames must be
allocated to each process in order to prevent thrashing.
Operating System Concepts Essentials – 9th Edition 9.22 Silberschatz, Galvin and Gagne ©2013
Continue…
Recovery of Thrashing :
Do not allow the system to go into thrashing by instructing the long-term scheduler
not to bring the processes into memory after the threshold.
If the system is already thrashing then instruct the mid-term scheduler to suspend
some of the processes so that we can recover the system from thrashing.
Operating System Concepts Essentials – 9th Edition 9.23 Silberschatz, Galvin and Gagne ©2013
Paging vs. Segmentation
Paging Segmentation
Paging divides program into fixed size pages. Segmentation divides program into
variable size segments.
OS is responsible Compiler is responsible.
Paging is faster than segmentation Segmentation is slower than paging
Paging is closer to Operating System Segmentation is closer to User
It suffers from internal fragmentation It suffers from external fragmentation
Logical address is divided into page number Logical address is divided into segment
and page offset number and segment offset
Page table is used to maintain the page Segment Table maintains the segment
information. information
Operating System Concepts Essentials – 9th Edition 9.24 Silberschatz, Galvin and Gagne ©2013
Segmented Paging
Pure segmentation is not very popular and not being used in many of the operating
systems.
However, Segmentation can be combined with Paging to get the best features out of
both the techniques.
In Segmented Paging, the main memory is divided into variable size segments which
are further divided into fixed size pages.
Pages are smaller than segments.
Each Segment has a page table which means every program has multiple page
tables.
The logical address is represented as Segment Number (base address), Page
number and page offset.
Segment Number → It points to the appropriate Segment Number.
Page Number → It Points to the exact page within the segment.
Page Offset → Used as an offset within the page frame.
Operating System Concepts Essentials – 9th Edition 9.25 Silberschatz, Galvin and Gagne ©2013
Continue…
Each Page table contains the various information about every page of the segment.
The Segment Table contains the information about every segment. Each segment
table entry points to a page table entry and every page table entry is mapped to one
of the page within a segment.
Operating System Concepts Essentials – 9th Edition 9.26 Silberschatz, Galvin and Gagne ©2013
Continue…
Translation of logical address to physical address
The CPU generates a logical address which is divided into two parts: Segment
Number and Segment Offset.
The Segment Offset must be less than the segment limit. Offset is further divided into
Page number and Page Offset.
To map the exact page number in the page table, the page number is added into the
page table base.
The actual frame number with the page offset is mapped to the main memory to get
the desired word in the page of the certain segment of the process.
Operating System Concepts Essentials – 9th Edition 9.27 Silberschatz, Galvin and Gagne ©2013
Continue…
Operating System Concepts Essentials – 9th Edition 9.28 Silberschatz, Galvin and Gagne ©2013
0
Continue… 1
P0
Segment Table 2
Segment Limit Page Table P1
3
Base Page Size=2
0 4
S0 10 1000 P2
5
S1 50 1200
6
S2 20 1400 P3
0 P3 F0 7
1 S0
10 2
4 P2 F1
yes 3
CPU S d d<limit d
4 4
0 5 P1 F2
0,4 no 2
6
Logical Address Error 7
p o P0 F3
F o
1,0
.
P0 1000 F3
.
#of page=d/page size=4/2=2 P1 1001 F2
O=d % page size=4%2=0 .
Physical address=(frame no*page size)+o P2 1002 F1
=1*2+0=2
P3 1003 F0 Fn
Page Table
Operating System Concepts Essentials – 9th Edition 9.29 Silberschatz, Galvin and Gagne ©2013
Continue…
Advantages of Segmented Paging
It reduces memory usage.
Page table size is limited by the segment size.
Segment table has only one entry corresponding to one actual segment.
External Fragmentation is not there.
It simplifies memory allocation.
Disadvantages of Segmented Paging
Internal Fragmentation will be there.
The complexity level will be much higher as compare to paging.
Page Tables need to be contiguously stored in the memory.
Operating System Concepts Essentials – 9th Edition 9.30 Silberschatz, Galvin and Gagne ©2013
Practice
Considering the following segment table and page table, translate the following
logical address to physical address: (2, 6), where page size=2.
Segment Table Page Table
Segment Limit Page Table Base P0 1000 F3
P1 1001 F2
S0 10 1000 P2 1002 F1
S1 14 1200 P3 1003 F0
S2 12 1400
Operating System Concepts Essentials – 9th Edition 9.31 Silberschatz, Galvin and Gagne ©2013
THANK YOU!
Operating System Concepts Essentials – 9th Edition 9.32 Silberschatz, Galvin and Gagne ©2013
