1 00:00:00,870 --> 00:00:03,980 Here's how our virtual memory system will work. 2 00:00:03,980 --> 00:00:08,680 The memory addresses generated by the CPU are called virtual addresses to distinguish 3 00:00:08,680 --> 00:00:12,300 them from the physical addresses used by main memory. 4 00:00:12,300 --> 00:00:16,490 In between the CPU and main memory there's a new piece of hardware called the memory 5 00:00:16,490 --> 00:00:20,060 management unit (MMU). 6 00:00:20,060 --> 00:00:24,980 The MMU's job is to translate virtual addresses to physical addresses. 7 00:00:24,980 --> 00:00:26,980 "But wait!" you say. 8 00:00:26,980 --> 00:00:31,070 "Doesn't the cache go between the CPU and main memory?" 9 00:00:31,070 --> 00:00:35,821 You're right and at the end of this lecture we'll talk about how to use both an MMU and 10 00:00:35,821 --> 00:00:36,980 a cache. 11 00:00:36,980 --> 00:00:42,359 But for now, let's assume there's only an MMU and no cache. 12 00:00:42,359 --> 00:00:47,600 The MMU hardware translates virtual addresses to physical addresses using a simple table 13 00:00:47,600 --> 00:00:48,890 lookup. 14 00:00:48,890 --> 00:00:51,989 This table is called the page map or page table. 15 00:00:51,989 --> 00:00:57,480 Conceptually, the MMU uses the virtual address as index to select an entry in the table, 16 00:00:57,480 --> 00:01:01,239 which tells us the corresponding physical address. 17 00:01:01,239 --> 00:01:06,690 The table allows a particular virtual address to be found anywhere in main memory. 18 00:01:06,690 --> 00:01:10,940 In normal operation we'd want to ensure that two virtual addresses don't map to the same 19 00:01:10,940 --> 00:01:13,539 physical address. 20 00:01:13,539 --> 00:01:17,920 But it would be okay if some of the virtual addresses did not have a translation to a 21 00:01:17,920 --> 00:01:19,810 physical address. 22 00:01:19,810 --> 00:01:23,789 This would indicate that the contents of the requested virtual address haven't yet been 23 00:01:23,789 --> 00:01:29,020 loaded into main memory, so the MMU would signal a memory-management exception to the 24 00:01:29,020 --> 00:01:32,020 CPU, which could assign a location in physical 25 00:01:32,020 --> 00:01:37,520 memory and perform the required I/O operation to initialize that location from secondary 26 00:01:37,520 --> 00:01:40,140 storage. 27 00:01:40,140 --> 00:01:45,410 The MMU table gives the system a lot of control over how physical memory is accessed by the 28 00:01:45,410 --> 00:01:47,789 program running on the CPU. 29 00:01:47,789 --> 00:01:53,090 For example, we could arrange to run multiple programs in quick succession (a technique 30 00:01:53,090 --> 00:01:59,190 called time sharing) by changing the page map when we change programs. 31 00:01:59,190 --> 00:02:04,020 Main memory locations accessible to one program could be made inaccessible to another program 32 00:02:04,020 --> 00:02:07,260 by proper management of their respective page maps. 33 00:02:07,260 --> 00:02:12,200 And we could use memory-management exceptions to load program contents into main memory 34 00:02:12,200 --> 00:02:17,769 on demand instead of having to load the entire program before execution starts. 35 00:02:17,769 --> 00:02:23,499 In fact, we only need to ensure the current working set of a program is actually resident 36 00:02:23,499 --> 00:02:25,480 in main memory. 37 00:02:25,480 --> 00:02:30,260 Locations not currently being used could live in secondary storage until needed. 38 00:02:30,260 --> 00:02:35,379 In this lecture and next, we'll see how the MMU plays a central role in the design of 39 00:02:35,379 --> 00:02:39,549 a modern timesharing computer system. 40 00:02:39,549 --> 00:02:44,720 Of course, we'd need an impossibly large table to separately map each virtual address to 41 00:02:44,720 --> 00:02:46,450 a physical address. 42 00:02:46,450 --> 00:02:51,690 So instead we divide both the virtual and physical address spaces into fixed-sized blocks, 43 00:02:51,690 --> 00:02:53,840 called pages. 44 00:02:53,840 --> 00:03:00,180 Page sizes are always a power-of-2 bytes, say 2^p bytes, so p is the number address 45 00:03:00,180 --> 00:03:03,519 bits needed to select a particular location on the page. 46 00:03:03,519 --> 00:03:09,680 We'll the use low-order p bits of the virtual or physical address as the page offset. 47 00:03:09,680 --> 00:03:14,310 The remaining address bits tell us which page is being accessed and are called the page 48 00:03:14,310 --> 00:03:15,310 number. 49 00:03:15,310 --> 00:03:25,159 A typical page size is 4KB to 16KB, which correspond to p=12 and p=14 respectively. 50 00:03:25,159 --> 00:03:26,700 Suppose p=12. 51 00:03:26,700 --> 00:03:33,280 If the CPU produces a 32-bit virtual address, the low-order 12 bits of the virtual address 52 00:03:33,280 --> 00:03:38,840 are the page offset and the high-order 20 bits are the virtual page number. 53 00:03:38,840 --> 00:03:44,739 Similarly, the low-order p bits of the physical address are the page offset and the remaining 54 00:03:44,739 --> 00:03:48,189 physical address bits are the physical page number. 55 00:03:48,189 --> 00:03:54,090 The key idea is that the MMU will manage pages, not individual locations. 56 00:03:54,090 --> 00:03:58,168 We'll move entire pages from secondary storage into main memory. 57 00:03:58,168 --> 00:04:04,450 By the principal of locality, if a program access one location on a page, we expect it 58 00:04:04,450 --> 00:04:08,379 will soon access other nearby locations. 59 00:04:08,379 --> 00:04:13,799 By choosing the page offset from the low-order address bits, we'll ensure that nearby locations 60 00:04:13,799 --> 00:04:19,190 live on the same page (unless of course we're near one end of the page or the other). 61 00:04:19,190 --> 00:04:22,900 So pages naturally capture the notion of locality. 62 00:04:22,900 --> 00:04:27,770 And since pages are large, by dealing with pages when accessing secondary storage, 63 00:04:27,770 --> 00:04:32,780 we'll take advantage that reading or writing many locations is only slightly more time 64 00:04:32,780 --> 00:04:36,759 consuming than accessing the first location. 65 00:04:36,759 --> 00:04:41,360 The MMU will map virtual page numbers to physical page numbers. 66 00:04:41,360 --> 00:04:47,919 It does this by using the virtual page number (VPN) as an index into the page table. 67 00:04:47,919 --> 00:04:52,561 Each entry in the page table indicates if the page is resident in main memory and, if 68 00:04:52,561 --> 00:04:56,919 it is, provides the appropriate physical page number (PPN). 69 00:04:56,919 --> 00:05:03,970 The PPN is combined with the page offset to form the physical address for main memory. 70 00:05:03,970 --> 00:05:10,550 If the requested virtual page is NOT resident in main memory, the MMU signals a memory-management 71 00:05:10,550 --> 00:05:15,949 exception, called a page fault, to the CPU so it can load the appropriate page from secondary 72 00:05:15,949 --> 00:05:20,699 storage and set up the appropriate mapping in the MMU. 73 00:05:20,699 --> 00:05:26,349 Our plan to use main memory as page cache is called "paging" or sometimes "demand paging" 74 00:05:26,349 --> 00:05:31,580 since movements of pages to and from secondary storage is determined by the demands of the 75 00:05:31,580 --> 00:05:33,030 program. 76 00:05:33,030 --> 00:05:35,190 So here's the plan. 77 00:05:35,190 --> 00:05:40,819 Initially all the virtual pages for a program reside in secondary storage and the MMU is 78 00:05:40,819 --> 00:05:45,360 empty, i.e., there are no pages resident in physical memory. 79 00:05:45,360 --> 00:05:49,860 The CPU starts running the program and each virtual address it generates, either for an 80 00:05:49,860 --> 00:05:55,319 instruction fetch or data access, is passed to the MMU to be mapped to a physical address 81 00:05:55,319 --> 00:05:57,400 in main memory. 82 00:05:57,400 --> 00:06:01,919 If the virtual address is resident in physical memory, the main memory hardware can complete 83 00:06:01,919 --> 00:06:04,310 the access. 84 00:06:04,310 --> 00:06:09,990 If the virtual address in NOT resident in physical memory, the MMU signals a page fault 85 00:06:09,990 --> 00:06:16,479 exception, forcing the CPU to switch execution to special code called the page fault handler. 86 00:06:16,479 --> 00:06:22,129 The handler allocates a physical page to hold the requested virtual page and loads the virtual 87 00:06:22,129 --> 00:06:26,630 page from secondary storage into main memory. 88 00:06:26,630 --> 00:06:30,930 It then adjusts the page map entry for the requested virtual page to show that it is 89 00:06:30,930 --> 00:06:36,789 now resident and to indicate the physical page number for the newly allocated and initialized 90 00:06:36,789 --> 00:06:39,540 physical page. 91 00:06:39,540 --> 00:06:44,080 When trying to allocate a physical page, the handler may discover that all physical pages 92 00:06:44,080 --> 00:06:45,800 are currently in use. 93 00:06:45,800 --> 00:06:52,340 In this case it chooses an existing page to replace, e.g., a resident virtual page that 94 00:06:52,340 --> 00:06:55,130 hasn't been recently accessed. 95 00:06:55,130 --> 00:07:00,409 It swaps the contents of the chosen virtual page out to secondary storage and updates 96 00:07:00,409 --> 00:07:05,690 the page map entry for the replaced virtual page to indicate it is no longer resident. 97 00:07:05,690 --> 00:07:10,419 Now there's a free physical page to re-use to hold the contents of the virtual page that 98 00:07:10,419 --> 00:07:13,229 was missing. 99 00:07:13,229 --> 00:07:18,500 The working set of the program, i.e., the set of pages the program is currently accessing, 100 00:07:18,500 --> 00:07:23,370 is loaded into main memory through a series of page faults. 101 00:07:23,370 --> 00:07:29,050 After a flurry of page faults when the program starts running, the working set changes slowly, 102 00:07:29,050 --> 00:07:34,909 so the frequency of page faults drops dramatically, perhaps close to zero if the program is small 103 00:07:34,909 --> 00:07:37,280 and well-behaved. 104 00:07:37,280 --> 00:07:42,099 It is possible to write programs that consistently generate page faults, a phenomenon called 105 00:07:42,099 --> 00:07:43,919 thrashing. 106 00:07:43,919 --> 00:07:50,170 Given the long access times of secondary storage, a program that's thrashing runs *very* slowly, 107 00:07:50,170 --> 00:07:57,449 usually so slowly that users give up and rewrite the program to behave more sensibly. 108 00:07:57,449 --> 00:08:00,330 The design of the page map is straightforward. 109 00:08:00,330 --> 00:08:03,879 There's one entry in the page map for each virtual page. 110 00:08:03,879 --> 00:08:09,620 For example, if the CPU generates a 32-bit virtual address and the page size is 2^12 111 00:08:09,620 --> 00:08:19,349 bytes, the virtual page number has 32-12 = 20 bits and the page table will have 2^20 entries. 112 00:08:19,349 --> 00:08:25,210 Each entry in the page table contains a "resident bit" (R) which is set to 1 when the virtual 113 00:08:25,210 --> 00:08:27,689 page is resident in physical memory. 114 00:08:27,689 --> 00:08:33,750 If R is 0, an access to that virtual page will cause a page fault. 115 00:08:33,750 --> 00:08:40,029 If R is 1, the entry also contains the PPN, indicating where to find the virtual page 116 00:08:40,029 --> 00:08:43,360 in main memory. 117 00:08:43,360 --> 00:08:47,320 There's one additional state bit called the "dirty bit" (D). 118 00:08:47,320 --> 00:08:53,300 When a page has just been loaded from secondary storage, it's "clean", i.e, the contents of 119 00:08:53,300 --> 00:08:58,279 physical memory match the contents of the page in secondary storage. 120 00:08:58,279 --> 00:09:01,089 So the D bit is set to 0. 121 00:09:01,089 --> 00:09:06,660 If subsequently the CPU stores into a location on the page, the D bit for the page is set 122 00:09:06,660 --> 00:09:12,880 to 1, indicating the page is "dirty", i.e., the contents of memory now differ from the 123 00:09:12,880 --> 00:09:15,810 contents of secondary storage. 124 00:09:15,810 --> 00:09:20,820 If a dirty page is ever chosen for replacement, its contents must be written to secondary 125 00:09:20,820 --> 00:09:26,720 storage in order to save the changes before the page gets reused. 126 00:09:26,720 --> 00:09:30,389 Some MMUs have additional state bits in each page table entry. 127 00:09:30,389 --> 00:09:35,350 For example, there could be a "read-only" bit which, when set, would generate an exception 128 00:09:35,350 --> 00:09:38,100 if the program attempts to store into the page. 129 00:09:38,100 --> 00:09:43,310 This would be useful for protecting code pages from accidentally being corrupted by errant 130 00:09:43,310 --> 00:09:47,779 data accesses, a very handy debugging feature. 131 00:09:47,779 --> 00:09:50,220 Here's an example of the MMU in action. 132 00:09:50,220 --> 00:09:56,230 To make things simple, assume that the virtual address is 12 bits, consisting of an 8-bit 133 00:09:56,230 --> 00:09:59,680 page offset and a 4-bit virtual page number. 134 00:09:59,680 --> 00:10:03,840 So there are 2^4 = 16 virtual pages. 135 00:10:03,840 --> 00:10:10,420 The physical address is 11 bits, divided into the same 8-bit page offset and a 3-bit physical 136 00:10:10,420 --> 00:10:11,740 page number. 137 00:10:11,740 --> 00:10:16,190 So there are 2^3 = 8 physical pages. 138 00:10:16,190 --> 00:10:21,649 On the left we see a diagram showing the contents of the 16-entry page map, i.e., an entry for 139 00:10:21,649 --> 00:10:24,200 each virtual page. 140 00:10:24,200 --> 00:10:30,300 Each page table entry includes a dirty bit (D), a resident bit (R) and a 3-bit physical 141 00:10:30,300 --> 00:10:33,760 page number, for a total of 5 bits. 142 00:10:33,760 --> 00:10:41,340 So the page map has 16 entries, each with 5-bits, for a total of 16*5 = 80 bits. 143 00:10:41,340 --> 00:10:45,941 The first entry in the table is for virtual page 0, the second entry for virtual page 144 00:10:45,941 --> 00:10:49,320 1, and so on. 145 00:10:49,320 --> 00:10:53,670 In the middle of the slide there's a diagram of physical memory showing the 8 physical 146 00:10:53,670 --> 00:10:54,980 pages. 147 00:10:54,980 --> 00:11:01,010 The annotation for each physical page shows the virtual page number of its contents. 148 00:11:01,010 --> 00:11:05,129 Note that there's no particular order to how virtual pages are stored in physical memory 149 00:11:05,129 --> 00:11:08,300 - which page holds what is determined by which 150 00:11:08,300 --> 00:11:11,630 pages are free at the time of a page fault. 151 00:11:11,630 --> 00:11:16,540 In general, after the program has run for a while, we'd expected to find the sort of 152 00:11:16,540 --> 00:11:20,060 jumbled ordering we see here. 153 00:11:20,060 --> 00:11:26,050 Let's follow along as the MMU handles the request for virtual address 0x2C8, generated 154 00:11:26,050 --> 00:11:30,260 by the execution of the LD instruction shown here. 155 00:11:30,260 --> 00:11:36,850 Splitting the virtual address into page number and offset, we see that the VPN is 2 and the 156 00:11:36,850 --> 00:11:40,090 offset is 0xC8. 157 00:11:40,090 --> 00:11:46,170 Looking at the page map entry with index 2, we see that the R bit is 1, indicating that 158 00:11:46,170 --> 00:11:50,290 virtual page 2 is resident in physical memory. 159 00:11:50,290 --> 00:11:58,149 The PPN field of entry tells us that virtual page 2 can be found in physical page 4. 160 00:11:58,149 --> 00:12:04,270 Combining the PPN with the 8-bit offset, we find that the contents of virtual address 161 00:12:04,270 --> 00:12:09,920 0x2C8 can be found in main memory location 0x4C8. 162 00:12:09,920 --> 00:12:13,380 Note that the offset is unchanged by the translation process - 163 00:12:13,380 --> 00:12:18,620 the offset into the physical page is always the same as the offset into the virtual page.