Operating Systems
“Virtual Memory”
Roadmap
• Hardware and Control Structures
• Operating System Software
Terminology
Real and Virtual Memory
• Real memory
• Main memory, the actual RAM
• Virtual memory
• Memory on disk
• Allows for effective multiprogramming and relieves the user of tight
constraints of main memory
Key points in Memory Management
1) Memory references are logical addresses dynamically translated into
physical addresses at run time
• A process may be swapped in and out of main memory occupying different
regions at different times during execution
2) A process may be broken up into pieces that do not need to be
located contiguously in main memory
Breakthrough in Memory Management
• If both of those two characteristics are present,
• then it is not necessary that all of the pages or all of the segments of a
process be in main memory during execution.
• If the next instruction, and the next data location are in memory then
execution can proceed
• at least for a time
Execution of a Process
• Operating system brings into main memory a few pieces of the
program
• Resident set - portion of process that is in main memory
• An interrupt is generated when an address is needed that is not in
main memory
• Operating system places the process in a blocking state
Execution of a Process
• Piece of process that contains the logical address is brought into main
memory
• Operating system issues a disk I/O Read request
• Another process is dispatched to run while the disk I/O takes place
• An interrupt is issued when disk I/O complete which causes the operating
system to place the affected process in the Ready state
Implications of this new strategy
• More processes may be maintained in main memory
• Only load in some of the pieces of each process
• With so many processes in main memory, it is very likely a process will be in
the Ready state at any particular time
• A process may be larger than all of main memory
• The operating system automatically loads pieces of a process into main
memory as required.
Characteristics of Paging and Segmentation
Thrashing
• A state in which the system spends most of its time
swapping pieces rather than executing instructions.
• To avoid this, the operating system tries to guess which
pieces are least likely to be used in the near future.
• The guess is based on recent history
Principle of Locality
• Program and data references within a process tend to cluster
• Only a few pieces of a process will be needed over a short period of
time
• Therefore, it is possible to make intelligent guesses about which
pieces will be needed in the future
• This suggests that virtual memory may work efficiently
The locality map
• Note that during the
lifetime of the process,
references are
confined to a subset of
pages.
Paging
• Each process has its own page table
• Each page table entry contains the frame number of the
corresponding page in main memory
• Two extra bits are needed to indicate:
• whether the page is in main memory or not
• Whether the contents of the page has been altered since it was last loaded
Processes and Frames
A.0
A.1
A.2
A.3
D.0
B.0
D.1
B.1
D.2
B.2
C.0
C.1
C.2
C.3
D.3
D.4
Page Table
Address Translation
Two-Level Hierarchical Page Table
• 232 / 212 = 220 pages
• Each page is mapped by a 4-byte page
table entry (PTE) / 1 word
• Results in a user page table composed of
220 PTEs requiring 4 Mbyte (222 ) bytes
Address Translation for Hierarchical page
table
Page Size
• Smaller page size, less amount of internal fragmentation
• But Smaller page size, more pages required per process
• More pages per process means larger page tables
• Larger page tables means large portion of page tables in virtual
memory
Further complications to Page Size
• Small page size, large number of pages will be found in main memory
• As time goes on during execution, the pages in memory will all
contain portions of the process near recent references. Page faults
low.
• Increased page size causes pages to contain locations further from
any recent reference. Page faults rise.
Page Size
Segmentation
• A program can be subdivided into segments
• Segments may vary in length
• There is a maximum segment length
• Addressing consist of two parts
• a segment number and
• an offset
• Segmentation is similar to dynamic partitioning
Segment Organization
• Starting address corresponding segment in main memory
• Each entry contains the length of the segment
• A bit is needed to determine if segment is already in main memory
• Another bit is needed to determine if the segment has been modified
since it was loaded in main memory
• Same as in the page organization
Segment Table Entries
Address Translation in Segmentation
Combined Paging and Segmentation
• Paging is transparent to the programmer
• Segmentation is visible to the programmer
• Each segment is broken into fixed-size pages
Combined Paging and Segmentation
Address Translation
Roadmap
• Hardware and Control Structures
• Operating System Software
Memory Management Decisions
• Three fundamental areas of choice:
• Whether or not to use virtual memory techniques
• The use of paging or segmentation or both
• The algorithms employed for various aspects of memory management
Key Design Elements
• Key aim: Minimise page faults
• No definitive best policy
Fetch Policy
• Determines when a page should be brought into memory
• Two main types:
• Demand Paging
• Prepaging
Demand Paging and Prepaging
• Demand paging
• only brings pages into main memory when a reference is made to a location
on the page
• Many page faults when process first started
• Prepaging
• brings in more pages than needed
• More efficient to bring in pages that reside contiguously on the disk
• Don’t confuse with “swapping”
Placement Policy
• Determines where in real memory a process piece is to reside, e.g.
best-fit, first-fit, next-fit
• Important in a segmentation system
• Paging or combined paging with segmentation hardware performs
address translation
Replacement Policy
• When all of the frames in main memory are occupied and it is
necessary to bring in a new page
• the replacement policy determines which page currently in memory is
to be replaced.
• Page removed should be the page least likely to be referenced in the
near future
• How is that determined?
• Principal of locality again
• Most policies predict the future behavior on the basis of past
behavior
Basic Replacement Algorithms
• There are certain basic algorithms that are used for the selection of a
page to replace, they include
• Optimal
• Least recently used (LRU)
• First-in-first-out (FIFO)
• Clock
• Examples
Examples
• An example of the implementation of these policies will use a page
address stream formed by executing the program is
• 232152453252
• Which means that the first page referenced is 2,
• the second page referenced is 3,
• And so on.
Optimal policy
• Selects for replacement that page for which the time to the next
reference is the longest
• But Impossible to have perfect knowledge of future events
Optimal Policy Example
• The optimal policy produces three page faults after
the frame allocation has been filled.
Least Recently Used (LRU)
• Replaces the page that has not been referenced for the longest time
• By the principle of locality, this should be the page least likely to be
referenced in the near future
• Difficult to implement
• One approach is to tag each page with the time of last reference.
• This requires a great deal of overhead.
LRU Example
• The LRU policy does nearly as well as the optimal
policy.
• In this example, there are four page faults
First-in, first-out (FIFO)
• Treats page frames allocated to a process as a circular buffer
• Pages are removed in round-robin style
• Simplest replacement policy to implement
• Page that has been in memory the longest is replaced
• But, these pages may be needed again very soon if it hasn’t truly fallen out of
use
FIFO Example
• The FIFO policy results in six page faults.
• Note that LRU recognizes that pages 2 and 5 are referenced
more frequently than other pages, whereas FIFO does not.
Clock Policy
• Uses and additional bit called a “use bit”
• When a page is first loaded in memory or referenced, the use bit is
set to 1
• When it is time to replace a page, the OS scans the set flipping all 1’s
to 0
• The first frame encountered with the use bit already set to 0 is
replaced.
Clock Policy Example
• Note that the clock policy is adept at protecting frames 2 and 5
from replacement.
Combined Examples
Comparison
Resident Set Management
• The OS must decide how many pages to bring into main memory
• The smaller the amount of memory allocated to each process, the more
processes that can reside in memory.
• Small number of pages loaded increases page faults.
• Beyond a certain size, further allocations of pages will not affect the page
fault rate.
Resident Set Size
• Fixed-allocation
• Gives a process a fixed number of pages within which to execute
• When a page fault occurs, one of the pages of that process must be replaced
• Variable-allocation
• Number of pages allocated to a process varies over the lifetime of the process
Replacement Scope
• The scope of a replacement strategy can be categorized as global or
local.
• Both types are activated by a page fault when there are no free page frames.
• A local replacement policy chooses only among the resident pages of the
process that generated the page fault
• A global replacement policy considers all unlocked pages in main memory
Fixed Allocation, Local Scope
• Decide ahead of time the amount of memory allocation to be given to
a process
• If allocation is too small, there will be a high page fault rate
• If allocation is too large there will be too few programs in main
memory
• Increased processor idle time or
• Increased swapping.
Variable Allocation, Local Scope
• When new process added, allocate number of page frames based on
application type, program request, or other criteria
• When page fault occurs, select page from among the resident set of
the process that suffers the fault
• Reevaluate allocation from time to time
Variable Allocation, Global Scope
• Easiest to implement
• Adopted by many operating systems
• Operating system keeps list of free frames
• Free frame is added to resident set of process when a page fault
occurs
• If no free frame, replaces one from another process
• The challenge is, which frame of process to replace.
Resident Set Management Summary
Cleaning Policy
• A cleaning policy is concerned with determining when a modified
page should be written out to secondary memory.
• Demand cleaning
• A page is written out only when it has been selected for replacement
• Precleaning
• Pages are written out in batches
Cleaning Policy
• Best approach uses page buffering
• Replaced pages are placed in two lists
• Modified and unmodified
• Pages in the modified list are periodically written out in batches
• Pages in the unmodified list are either reclaimed if referenced again
or lost when its frame is assigned to another page
Load Control
• Determines the number of processes that will be resident in main
memory
• especially in multiprogramming environment
• Two things to consider:
• Too few processes, many occasions when all processes will be blocked, and
much time will be spent in swapping
• Too many processes will lead to thrashing
Multiprogramming
Too few processes
leads to swapping
Too many processes leads to trashing
Process Suspension
• If the degree of multiprogramming is to be reduced, one or more of the
currently resident processes must be suspended (swapped out).
• Six categories of suspension:
• Lowest priority process
• Faulting process
• This process does not have its working set in main memory so it will be blocked anyway
• Last process activated
• This process is least likely to have its working set resident
• Process with smallest resident set
• This process requires the least future effort to reload
• Largest process
• Obtains the most free frames
• Process with the largest remaining execution window
Thank You