Paged Virtual Memory Management (vmm) (11/05/2003)

Paged Virtual Memory Management (VMM) (11/05/2003)

With the advent of 64-bit address architectures, the ancient principle of paged Virtual Memory Management (VMM) experiences a revival in the early 2000s. Originally, the driving principle for developing VMM systems (paged or segmented or both) was the hunger for more addressable program memory than was available in physical memory. Scarceness was caused by the high cost of memory. The early technology of core memories carried a high price tag due to the tedious manual labor involved. Now the days of high cost per byte of memory are gone. But the days of having insufficient physical memory have returned, with 64 bit addresses. What applications are sufficiently served with just a few Gigabytes of physical memory? Only trivial ones

Synopsis

1. 
   Steps of Paged Virtual Memory Management
   
2. 
   The Mapping Steps (Two-Level Mapping)
   
3. 
   Definitions
   
4. 
   History of Paging
   
5. 
   Goals and Methods of Paging
   
6. 
   An Unrealistic Paging Scheme
   
7. 
   A Realistic Paging Scheme for 32-bit Architecture
   
8. 
   Typical PD and PT Entries
   

Steps of Paged Virtual Memory Management

9. 
   Instruction references a logical address
   
10. 
    VMM determines, whether logical address maps onto a resident page
    
11. 
    If yes, the memory access completes. In a system with L1 cache, such an access is fast
    
12. 
    If such access is a store operation, (aka write) that fact is recorded
    
13. 
    If not on a resident page, the corresponding swapped-out page is found on disk and made available in memory, or else it is created the first time ever
    
14. 
    Making a new page available requires finding memory space (page frame)
    
15. 
    If such space can be allocated from unused memory (usually during initial program execution), it is now reserved
    
16. 
    If no page frame is available, a currently resident page is swapped out and the freed space is reused for the new page
    
17. 
    Should the page to be swapped out have be dirty, it must be written to disk
    
18. 
    Otherwise a copy exists on disk already and the swap-out operation is empty
    

The Mapping Steps (Two-Level Mapping)

19. 
    Instruction references a logical address (la)
    
20. 
    Processor finds start address of Page Directory (PD)
    
21. 
    Logical address is partitioned into three bit fields, Page Directory Index, Page Table (PT) Index, and Page Offset
    
22. 
    Entry in PD is found by adding PD Index left-shifted by 2 to the start address of PD; this yields a PT address
    
23. 
    Add PT Index left-shifted by 2 to previously found PT address; this yields Page Address
    
24. 
    Add Page Offset to previously found Page Address; this yields byte address
    
25. 
    Along the way there may have been 3 page faults
    

Definitions

Demand Paging:

Dirty Bit:

Global Page:

Logical Address:

Page:

Page Frame:

Page Directory:

A list of addresses for Page Tables. Typically this directory consumes an integral number of pages as well. In addition to page table addresses, each entry also contains information about presence, access rights, written to or not, global, etc. similar to Page Table entries.

Page Directory Base Register (pdbr):

Page Table Base Register (ptbr):

Page Fault:

Page Frame:

Page Table:

Physical Memory:

Present Bit:

Resident:

Swap-in:

Swap-out:

Thrashing:

Translation Look-Aside Buffer:

Virtual Contiguity:

Virtual Memory:

Working Set:

History of Paging

26. 
    Invented about 1960 at University of Manchester for Atlas Computer
    
27. 
    Used commercially in KDF-9 computer of English Electric Co.
    
28. 
    Ever since claimed to have been invented by most computer manufacturers
    
29. 
    In fact, KDF-9 was one of the major architectural milestones in computer history aside from von Neumann’s and Atanasoff’s machines; incorporated first cache and VMM, had hardware display for stack frame addresses, etc.
    
30. 
    In the late 1960s to early 1980s, memory was expensive, processors were expensive and getting fast, and programs grew large. Insufficient memories were common and were one aspect of the growing Software Crisis of the late 1970s
    
31. 
    16-bit minicomputers and 32-bit mainframes became common; also 18-bit address architectures (CDC and Cyber) of 60-bit words were common
    
32. 
    Paging grew increasingly popular: fast execution was gladly traded against large address range at cost of slower performance
    
33. 
    By mid 1980s, memories became cheaper, faster, large ones prevailed
    
34. 
    By the late 1980s, memories had become cheaper yet, the address range remained 32-bit, and large physical memories became possible and available
    
35. 
    Several supercomputers were designed with operating systems that provided no memory virtualization at all, no memory mapping. For example, Cray systems were built without VMM. The Intel Hypercube NX ® operating system had no virtual memory management
    
36. 
    Just when VMM was falling into disfavor, the addressing limitation of 32 bits started constraining programs. In the early 1990, 64-bit architectures started becoming common-place, rather than an exception
    
37. 
    Intermediate steps between architectural jumps: The Harris 3-byte system with 24-bit addresses, not making the jump to 32 bit quite. The Pentium Pro ® with 36 bits in extended addressing mode, not quite yet making the jump to 64 bit addresses. Even the early Itanium ® family processors had only 44 physical address bits, not quite making the jump to the physical 64 bit address space
    
38. 
    By end of 1990s, 64-bit addresses were common, 64-bit integer arithmetic will be performed in hardware, not longer via slow library extensions
    
39. 
    Pentium Pro has 4kB pages by default, 4MB pages if page size extension (pse) bit is set in normal addressing mode
    
40. 
    However, if the physical address extension (pae) bit and pse bit are set, the default page size changes from 4kB to 2 MB
    

Goals and Methods of Paging (VMM)

41. 
    Make full logical (virtual) address space available, even if smaller physical memory installed
    
42. 
    Perform mapping transparently. Thus, if at a later time the target receives a larger physical memory, the same program will run unchanged except faster
    
43. 
    Map logical onto physical address, even if this costs some performance
    
44. 
    Implement the mapping in a way that the overhead is small in relation to the total program execution
    
45. 
    A necessary requirement is a sufficiently large working set, but also:
    
46. 
    This is accomplished by caching page directory- and page table entries
    
47. 
    Or by placing complete page directory into a special cache
    

An Unrealistic Paging Scheme

48. 
    Assume 32-bit architecture, byte-addressable, 4-byte words, 4kB page size
    
49. 
    Single-level paging mechanism --later we’ll cover multi-level mapping
    
50. 
    With 4kB page size, rightmost 12 bits of each page address are all 0, or implied
    
51. 
    Page Table thus has (32-12 = 20) 2²⁰ entries, each entry typically 4 bytes
    
52. 
    Page offset of 12 bits identifies each byte on a 4kB page
    

53. 
    With each Page Table entry consuming 4 bytes, results in page table of 4 MB
    
54. 
    This is not a good paging scheme, since the scarce resource, physical memory, consumes already a 4MB overhead. Note that Page Tables should be resident, as long as some entries point to resident user pages
    
55. 
    Thus the overhead may exceed the total available resource - memory
    
56. 
    Moreover, almost all entries are empty; their associated pages do not exist yet, pointers are null
    

57. 
    Problem: The one data structure that should be resident is too large, consuming all/most of the physical memory that is so scarce
    
58. 
    So: break it into smaller units!
    
59. 
    Disadvantage of additional mapping: more memory accesses
    
60. 
    Advantage: Avoiding large 4MB Page Table
    

A Realistic Paging Scheme for 32-bit Architecture

61. 
    Again: 32-bit architecture, byte-addressable, 4-byte words, 4kB page size
    
62. 
    Two-level paging mechanism, consisting of Page Directory and Page Tables in addition to user pages
    
63. 
    With 4kB page size, again rightmost 12 bits of any page address 0 implied
    

64. 
    Have HW register point to Page Directory
    
65. 
    Or else implement Page Directory as a special-purpose cache
    
66. 
    Or place PD into a-priori known memory location
    
67. 
    But there must be a way to locate the PD, best without extra memory access
    
68. 
    Design principle: have user pages, pages of Page Tables, and pages of Page Directory look the same: all consume a page frame each
    

69. 
    Every logical address is broken into three parts: two indices + one offset
    
70. 
    Note that Page Directory Index is indeed an index; to find the entry in PD, first << 2 (multiply by 4), add this to the start address of PD, then PD entry found
    
71. 
    Similarly, Page Table Index is an index; to find the entry: << 2 and add result to the start address of PT found in previous step, thus entry in PT found
    
72. 
    The PT entry holds the address of the user page, rightmost 12 bit implied all 0
    
73. 
    The rightmost 12 bits of a logical address define the page offset within the found user page
    
74. 
    Since pages are 4 kB in size, 12 bits suffice to identify any byte in a page
    
75. 
    Given that the address of a user page is found, add the offset to its address, and the final byte address is identified
    

76. 
    Disadvantage: Multiple memory accesses, total of 3
    
77. 
    In fact, any of these total 3 accesses could cause page faults, resulting in 3 swap-ins
    
78. 
    Performance loss could be tremendous; i.e. several decimal orders of magnitude slower than a single memory access
    
79. 
    Thus some of these data structures must be cached
    
80. 
    In Intel Pentium Pro ® the Translation Look-Aside Buffer (TLB) is a special purpose cache of PD or PT entries
    
81. 
    Also possible to cache the complete PD, since contained in size O( 4 kB )
    

Typical PD and PT Entries

82. 
    Entries in PD and PT need 20 bits for address; lower 12 bits implied
    
83. 
    Other 12 bits can be used for additional information
    
84. 
    P-Bit: Is referenced page present? (aka resident)
    
85. 
    R/W/E bit: Can referenced page be read, written, executed, all?
    
86. 
    User/Supervisor bit: OS dependent, is page reserved for privileged code?
    
87. 
    Typically the P-Bit is positioned for quick, easy access: rightmost bit in 4-byte word
    

88. 
    Some information is unique to PD or PT
    
89. 
    For example, P-Bit not needed in PD entries, if Page Tables must be present
    
90. 
    On systems with varying page sizes, page size information must be recorded
    
91. 
    See examples below:
    

If the Operating System exercises a policy to not ever swap-out Page Tables, then the respective PT entries in the PD do not need to track the fact that a PT was modified (i.e. the Dirty bit). Hence there may be reasons that PT and PD entries have minor differences. But in general, the format and structure of PTs and PDs are identical, and the size of user pages, PTs and PDs are identical.