Transcript PPT Chapter 12

Chapter 12
Virtual Memory
Copyright © 2008
Introduction
•
•
•
•
•
•
•
•
•
Virtual Memory Basics
Demand Paging
The Virtual Memory Manager
Page Replacement Policies
Controlling Memory Allocation to a Process
Shared Pages
Memory-Mapped Files
Case Studies of Virtual Memory Using Paging
Virtual Memory Using Segmentation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.2
2
Virtual Memory Basics
• MMU translates logical address into physical one
• Virtual memory manager is a software component
– Uses demand loading
– Exploits locality of reference to improve performance
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.3
3
Virtual Memory Basics (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.4
4
Virtual Memory Using Paging
• MMU performs address translation using page table
Effective memory address of logical address (pi, bi)
= start address of the page frame containing page pi + bi
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.5
5
Demand Paging Preliminaries
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.6
6
Demand Paging Preliminaries
(continued)
• Memory Management Unit (MMU) raises a page fault
interrupt if page containing logical address not in
memory
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.7
7
Demand Paging Preliminaries
(continued)
A page fault interrupt
is raised because
Valid bit of page 3 is 0
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.8
8
Demand Paging Preliminaries
(continued)
• At a page fault, the required page is loaded in a free
page frame
• If no page frame is free, virtual memory manager
performs a page replacement operation
– Page replacement algorithm
– Page-out initiated if page is dirty (modified bit is set)
• Page-in and page-out: page I/O or page traffic
• Effective memory access time in demand paging:
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.9
9
Page Replacement
• (Empirical) law of locality of reference: logical
addresses used by process in a short interval tend to
be grouped in certain portions of its logical address
space
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.10
10
Memory Allocation to a Process
• How much memory to allocate to a process
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.11
11
Optimal Page Size
• Size of a page is defined by computer hardware
• Page size determines:
–
–
–
–
No of bits required to represent byte number in a page
Memory wastage due to internal fragmentation
Size of the page table for a process
Page fault rates when a fixed amount of memory is
allocated to a process
• Use of larger page sizes than optimal value implies
somewhat higher page fault rates for a process
– Tradeoff between HW cost and efficient operation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.12
12
Paging Hardware
• Page-table-address-register (PTAR) points to the start
of a page table
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.13
13
Paging Hardware (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.14
14
Memory Protection
• Memory protection violation raised if:
– Process tries to access a nonexistent page
– Process exceeds its (page) access privileges
• It is implemented through:
– Page table size register (PTSR) of MMU
• Kernel records number of pages contained in a process in
its PCB
– Loads number from PCB in PTSR when process is scheduled
– Prot info field of the page’s entry in the page table
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.15
15
Address Translation and Page Fault
Generation
• Translation look-aside buffer (TLB): small and fast
associative memory used to speed up address
translation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.16
16
Address Translation and Page Fault
Generation (continued)
• TLBs can be HW or SW managed
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.17
17
Address Translation and Page Fault
Generation (continued)
TLB hit ratio
• Some mechanisms used to improve performance:
– Wired TLB entries for kernel pages: never replaced
– Superpages
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.18
18
Superpages
• TLB reach is stagnant even though memory sizes
increase rapidly as technology advances
– TLB reach = page size x no of entries in TLB
– It affects performance of virtual memory
• Superpages are used to increase the TLB reach
– A superpage is a power of 2 multiple of page size
– Its start address (both logical and physical) is aligned on
a multiple of its own size
– Max TLB reach = max superpage size x no of entries in
TLB
– Size of a superpage is adapted to execution behavior of a
process through promotions and demotions
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.19
19
Support for Page Replacement
• Virtual memory manager needs following information
for minimizing page faults and number of page-in and
page-out operations:
– The time when a page was last used
• Expensive to provide enough bits for this purpose
• Solution: use a single reference bit
– Whether a page is dirty
• A page is clean if it is not dirty
• Solution: modified bit in page table entry
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.20
20
Practical Page Table Organizations
• A process with a large address space requires a large
page table, which occupies too much memory
• Solutions:
– Inverted page table
• Describes contents of each page frame
– Size governed by size of memory
– Independent of number and sizes of processes
– Contains pairs of the form (program id, page #)
• Con: information about a page must be searched
– Multilevel page table
• Page table of process is paged
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.21
21
Inverted Page Tables
Use of hash table
Speeds up search
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.22
22
Multilevel Page Tables
• If size of a table entry is 2e
bytes, number of page
table entries in one PT
page is 2nb/2e
• Logical address (pi , bi) is
regrouped into three fields:
– PT page with the number
pi1 contains entry for pi
– pi2 is entry number for pi
in PT page
– bi
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.23
23
I/O Operations in a Paged
Environment
• Process makes system call for I/O operations
– Parameters include: number of bytes to transfer, logical
address of the data area
• Call activates I/O handler in kernel
– I/O subsystem does not contain an MMU, so I/O handler
replaces logical address of data area with physical
address, using information from process page table
– I/O fix (bit in misc info field) ensures pages of data area
are not paged out
– Scatter/gather feature can deposit parts of I/O operation’s
data in noncontiguous memory areas
– Alternatively, data area pages put in contiguous areas
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.24
24
Example: I/O Operations in Virtual
Memory
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.25
25
The Virtual Memory Manager
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.26
26
Example: Page Replacement
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.27
27
Overview of Operation of the Virtual
Memory Manager
• Virtual memory manager makes two important
decisions during its operation:
– Upon a page fault, decides which page to replace
– Periodically decides how many page frames should be
allocated to a process
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.28
28
Page Replacement Policies
• A page replacement policy should replace a page not
likely to be referenced in the immediate future
• Examples:
– Optimal page replacement policy
• Minimizes total number of page faults; infeasible in practice
– First-in first-out (FIFO) page replacement policy
– Least recently used (LRU) page replacement policy
• Basis: locality of reference
• Page reference strings
– Trace of pages accessed by a process during its
operation
– We associate a reference time string with each
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.29
29
Example: Page Reference String
• A computer supports instructions that are 4 bytes in
length
– Uses a page size of 1KB
– Symbols A and B are in pages 2 and 5
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.30
30
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.31
31
Page Replacement Policies
(continued)
• To achieve desirable page fault characteristics, faults
shouldn’t increase when memory allocation is increased
– Policy must have stack (or inclusion) property
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.32
32
FIFO page replacement policy does not exhibit stack property.
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.33
33
Page Replacement Policies
(continued)
• Virtual memory manager cannot use FIFO policy
– Increasing allocation to a process may increase page
fault frequency of process
• Would make it impossible to control thrashing
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.34
34
Practical Page Replacement Policies
• Virtual memory manager has two threads
– Free frames manager implements page replacement
policy
– Page I/O manager performs page-in/out operations
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.35
35
Practical Page Replacement Policies
(continued)
• LRU replacement is not feasible
– Computers do not provide sufficient bits in the ref info
field to store the time of last reference
• Most computers provide a single reference bit
– Not recently used (NRU) policies use this bit
• Simplest NRU policy: Replace an unreferenced page and
reset all reference bits if all pages have been referenced
• Clock algorithms provide better discrimination between
pages by resetting reference bits periodically
– One-handed clock algorithm
– Two-handed clock algorithm
» Resetting pointer (RP) and examining pointer (EP)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.36
36
Example: Two-Handed Clock
Algorithm
• Both pointers are advanced simultaneously
• Algorithm properties defined by pointer distance:
– If pointers are close together, only recently used pages
will survive in memory
– If pointers are far apart, only pages that have not been
used in a long time would be removed
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.37
37
Controlling Memory Allocation to a
Process
• Process Pi is allocated alloci number of page frames
• Fixed memory allocation
– Fixes alloc statically; uses local page replacement
• Variable memory allocation
– Uses local and/or global page replacement
– If local replacement is used, handler periodically
determines correct alloc value for a process
• May use working set model
• Sets alloc to size of the working set
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.38
38
Implementation of a Working Set
Memory Allocator
• Swap out a process if alloc page frames cannot be
allocated
• Expensive to determine WSi(t,∆) and alloci at every time
instant t
– Solution: Determine working sets periodically
• Sets determined at end of an interval are used to decide
values of alloc for use during the next interval
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.39
39
Shared Pages
• Static sharing results from static binding performed by a
linker/loader before execution of program
• Dynamic binding conserves memory by binding same
copy of a program/data to several processes
– Program or data shared retains its identity
– Two conditions should be satisfied:
• Shared program should be coded as reentrant
– Can be invoked by many processes at the same time
• Program should be bound to identical logical addresses in
every process that shared it
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.40
40
Shared pages
should have same
page numbers in
all processes
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.41
41
Copy-on-Write
• Feature used to conserve memory when data in shared
pages could be modified
– Copy-on-write flag in page table entries Memory
allocation decisions are performed statically
A private copy of
page k is made
when A modifies it
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.42
42
Memory-Mapped Files
• Memory mapping of a file by a process binds file to a
part of the logical address space of the process
– Binding is performed when process makes a memory
map system call
– Analogous to dynamic binding of programs and data
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.43
43
Memory-Mapped Files (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.44
44
Case Studies of Virtual Memory Using
Paging
•
•
•
•
Unix Virtual Memory
Linux Virtual Memory
Virtual Memory in Solaris
Virtual Memory in Windows
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.45
45
Unix Virtual Memory
•
•
•
•
•
Paging hardware differs in architectures
Pages can be: resident, unaccessed, swapped-out
Allocation of as little swap space as possible
Copy-on-write for fork
Lack reference bit in some HW architectures;
compensated using valid bit in interesting manner
• Process can fix some pages in memory
• Pageout daemon uses a clock algorithm
– Swaps out a process if all required pages cannot be in
memory
– A swap-in priority is used to avoid starvation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.46
46
Linux Virtual Memory
• Page size of 4 KB
• On 64-bit architectures, uses three-level page table
• States for page frames: free, active, inactive dirty,
inactive laundered, inactive clean
• Page replacement based on a clock algorithm
– Uses two lists called active list and inactive list
• Buddy system allocator for allocating page frames
• Several virtual memory regions for a process:
– Zero-filled, file-backed, private memory
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.47
47
Virtual Memory in Solaris
• Supports normal pages and superpages
– Superpages:
• Automatically for processes with large address spaces
• Can be requested using memcntl system call
• Not used for memory-mapped files
• Solaris 6 introduced priority paging to avoid interference
between file processing and virtual memory
• Page scanner tries to keep a sufficient number of page
frames on cyclic page cache (since Solaris 8)
– lotsfree parameter indicates how many page frames
should be free
– Uses two-handed clock algorithm on a global basis
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.48
48
Virtual Memory in Windows
•
•
•
•
Supports both 32-bit and 64-bit logical addresses
Page size is 4 KB
Process address space is either 2 GB or 3 GB
Two-, three- or four-level page tables and various page
table entry formats
– On the X-86 architecture:
• Page frame can be in one of eight states, including:
valid, free, zeroed, standby, modified, and bad
• A process must first reserve virtual address space and
then commit it for specific entities
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.49
49
Virtual Memory in Windows
(continued)
• A section object represents a section of memory that
can be shared
– A process maps a view to access part of a section
– Copy-on-write feature used for sharing pages
– Prototype PTE is set-up for shared pages
• TLBs are managed by HW (32-bit) or SW (64-bit)
• Exploits reference locality: loads a few pages before
and after a page-faulted page into memory
• Uses notion of working sets (for memory allocation)
– Clock algorithm
• Page lists: free, zero-initiated, modified, standby
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.50
50
Virtual Memory Using Segmentation
• A segment is a logical entity in a program, such as a
function, a data structure, or an object
– Or, a module that consists of some or all of these
– Convenient unit for sharing and protection
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.51
51
Example: Effective Address
Calculation in Segmentation
• Logical address (si, bi) can be specified as ids
– (alpha, beta)
• alpha: name of a segment
• beta: id associated with a byte contained in alpha
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.52
52
Management of Memory
• Similarities to paging:
– Segment fault indicates segment is not in memory
– Segment-in operation is performed to load segment
• Segment-out operations may be needed first
– Can use working set of segment for allocation
• Segments can be replaced on NRU basis
• Differences to paging:
– Can lead to external fragmentation
• Tackled through compaction or through memory reuse
techniques (first fit, best fit, etc.)
– Segments can dynamically grow or shrink in size
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.53
53
Sharing and Protection
• Two important issues in protection and sharing of
segments are:
– Static and dynamic sharing of segments
– Detecting use of invalid addresses
• Protection exception if bi exceeds size of si
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.54
54
Segmentation with Paging
• External fragmentation exists in a virtual memory using
segmentation
– Solution: segmentation with paging
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.55
55
Summary
• Basic actions in virtual memory using paging: address
translation and demand loading of pages
– Implemented jointly by
• Memory Management Unit (MMU): Hardware
• Virtual memory manager: Software
• Memory is divided into page frames
• Virtual memory manager maintains a page table
– Inverted and multilevel page tables use less memory but
are less efficient
– A fast TLB is used to speed up address translation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.56
56
Summary (continued)
• Which page should VM manager remove from memory
to make space for a new page?
– Page replacement algorithms exploit locality of reference
• LRU has stack property, but is expensive
• NRU algorithms are used in practice
– E.g., clock algorithms
• How much memory should manager allocate?
– Use working set model to avoid thrashing
• Copy-on-write can be used for shared pages
• Memory mapping of files speeds up access to data
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
12.57
57