qa.pdf

5.7 Virtual Memory 427 Because the VMM must ensure that the guest system only interacts with virtual resources, a conventional guest OS runs as a user mode program on top of the VMM. ! en, if a guest OS attempts to access or modify information related to hardware resources v...

5.7 Virtual Memory 427 Because the VMM must ensure that the guest system only interacts with virtual resources, a conventional guest OS runs as a user mode program on top of the VMM. ! en, if a guest OS attempts to access or modify information related to hardware resources via a privileged instruction—for example, reading or writing a status bit that enables interrupts—it will trap to the VMM. ! e VMM can then e" ect the appropriate changes to corresponding real resources. Hence, if any instruction that tries to read or write such sensitive information traps when executed in user mode, the VMM can intercept it and support a virtual version of the sensitive information, as the guest OS expects. In the absence of such support, other measures must be taken. A VMM must take special precautions to locate all problematic instructions and ensure that they behave correctly when executed by a guest OS, thereby increasing the complexity of the VMM and reducing the performance of running the VM. Protection and Instruction Set Architecture Protection is a joint e" ort of architecture and operating systems, but architects had to modify some awkward details of existing instruction set architectures when virtual memory became popular. For example, the x86 instruction POPF loads the # ag registers from the top of the stack in memory. One of the # ags is the Interrupt Enable (IE) # ag. If you run the POPF instruction in user mode, rather than trap it, it simply changes all the # ags except IE. In system mode, it does change the IE. Since a guest OS runs in user mode inside a VM, this is a problem, as it expects to see a changed IE. Historically, IBM mainframe hardware and VMM took three steps to improve performance of virtual machines: 1. Reduce the cost of processor virtualization. 2. Reduce interrupt overhead cost due to the virtualization. 3. Reduce interrupt cost by steering interrupts to the proper VM without invoking VMM. AMD and Intel tried to address the $ rst point in 2006 by reducing the cost of processor virtualization. It will be interesting to see how many generations of architecture and VMM modi$ cations it will take to address all three points, and how long before virtual machines of the 21st century will be as e% cient as the IBM mainframes and VMMs of the 1970s. 5.7 Virtual Memory In earlier sections, we saw how caches provided fast access to recently used portions of a program’s code and data. Similarly, the main memory can act as a “cache” for … a system has been devised to make the core drum combination appear to the programmer as a single level store, the requisite transfers taking place automatically. Kilburn et al., One-level storage system, 1962 428 Chapter 5 Large and Fast: Exploiting Memory Hierarchy the secondary storage, usually im plemented with magnetic disks. ! is technique is called virtual memory . Historically, there were two major motivations for virtual memo ry: to allow e% cient and safe sharing of memory among multiple programs, such as for the memory needed by multiple virtual machines for cloud computing, and to remove the programming burdens of a small, limited amount of main memory. Five decades a& er its invention, it’s the former reason that reigns today. Of course, to allow multiple virtual machines to share the same memory, we must be able to protect the virtual machines from each other, ensuring that a program can only read and write the portions of main memory that have been assigned to it. Main memory need contain only the active portions of the many virtual machines, just as a cache contains only the active portion of one program. ! us, the principle of locality enables virtual memory as well as caches, and virtual memory allows us to e% ciently share the processor as well as the main memory. We cannot know which virtual machines will share the memory with other virtual machines when we compile them. In fact, the virtual machines sharing the memory change dynamically while the virtual machines are running. Because of this dynamic interaction, we would like to compile each program into its own address space —a separate range of memory locations accessible only to this program. Virtual memory implements the translation of a program’s address space to physical addresses . ! is translation process enforces protection of a program’s addr ess space from other virtual machines. ! e second motivation for virtual memory is to allow a single user program to exceed the size of primary memory. Formerly, if a program became too large for memory, it was up to the programmer to make it $ t. Programmers divided programs into pieces and then identi$ ed the pieces that were mutually exclusive. ! ese overlays were loaded or unloaded under user program control during execution, with the programmer ensuring that the program never tried to access an overlay that was not loaded and that the overlays loaded never exceeded the total size of the memory. Overlays were traditionally organized as modules, each containing both code and data. Calls between procedures in di" erent modules would lead to overlaying of one module with another. As you can well imagine, this responsibility was a substantial burden on programmers. Virtual memory, which was invented to relieve programmers of this di% culty, automatically manages the two levels of the memory hierarchy represented by main memory (sometimes called physical memory to distinguish it from virtual memory) and secondary storage. Although the concepts at work in virtual memory and in caches are the same, their di" ering historical roots have led to the use of di" erent terminology. A virtual memory block is called a page , and a virtual memory miss is called a page fault . With virtual memory, the processor produces a virtual address , which is translated by a combination of hardware and so& ware to a physical address , which in turn can be used to access main memory. Figure 5.25 shows the virtually addressed memor y with pages mapped to main memory. ! is process is called address mapping or virtual memory A technique that uses main memory as a “cache” for secondary storage. physical address An address in main memory. protection A set of mechanisms for ensuring that multiple processes sharing the processor, memory, or I/O devices cannot interfere, intentionally or unintentionally, with one another by reading or writing each other’s data. ! ese mechanisms also isolate the operating system from a user process. page fault An event that occurs when an accessed page is not present in main memory. virtual address An address that corresponds to a location in virtual space and is translated by address mapping to a physical address when memory is accessed. 5.7 Virtual Memory 429 address translation . Today, the two memory hierarchy levels controlled by virtual memo ry are usually DRAMs and # ash memory in personal mobile devices and DRAMs and magnetic disks in servers (see Section 5.2). If we return to our library analogy, we can think of a virtual address as the title of a book and a physical address as the location of that book in the library, such as might be given by the Library of Congress call number. Vir tual memor y als o simpli$ es loading the program for execution by providing relocation . Relocation maps the virtual addresses used by a program to di" erent physical addresses before the addresses are used to access memory. ! is relocation allows us to load the program anywhere in main memory. Furthermore, all virtual memory systems in use today relocate the program as a set of $ xed-size blocks (pages), thereby eliminating the need to $ nd a contiguous block of memory to allocate to a program; instead, the operating system need only $ nd a su% cient number of pages in main memory. In virtual memory, the address is broken into a virtual page number and a page o! set . Figure 5.26 shows the translation of the virtual page number to a physical page number . ! e physical page number constitutes the upper portion of the physical address, while the page o" set, which is not changed, constitutes the lower portion. ! e number of bits in the page o" set $ eld determines the page size. ! e number of pages addressable with the virtual address need not match the number of pages addressable with the physical address. Having a larger number of virtual pages than physical pages is the basis for the illusion of an essentially unbounded amount of virtual memory. address translation Also called address ma pping . ! e process by which a virtual address is mapped to an address used to access memory. Virtual addresses Physical addresses Address translation Disk addresses FIGURE 5.25 In virtual memory, blocks of memory (called pages ) are mapped from one set of addresses (called virtual addresses ) to another set (called physical addresses ). ! e processor generates virtual addresses while the memory is accessed using physical addresses. Both the virtual memory and the physical memory are broken into pages, so that a virtual page is mapped to a physical page. Of course, it is also possible for a virtual page to be absent from main memory and not be mapped to a physical address; in that case, the page resides on disk. Physical pages can be shared by having two virtual addresses point to the same physical address. ! is capability is used to allow two di" erent programs to share data or code. 430 Chapter 5 Large and Fast: Exploiting Memory Hierarchy Many design choices in virtual memory systems are motivated by the high cost of a page fault. A page fault to disk will take millions of clock cycles to process. (! e table on page 378 shows that main memory latency is about 100,000 times quicker than disk.) ! is enormous miss penalty, dominated by the time to get the $ rst word for typical page sizes, leads to several key decisions in designing virtual memory systems: ! Pages should be large enough to try to amortize the high access time. Sizes from 4 KiB to 16 KiB are typical today. New desktop and server systems are being developed to support 32 KiB and 64 KiB pages, but new embedded systems are going in the other direction, to 1 KiB pages. ! Organizations that reduce the page fault rate are attractive. ! e primary technique used here is to allow fully associative placement of pages in memory. ! Page faults can be handled in so& ware because the overhead will be small compared to the disk access time. In addition, so& ware can a" ord to use clever algorithms for choosing how to place pages because even small reductions in the miss rate will pay for the cost of such algorithms. ! Write-through will not work for virtual memory, since writes take too long. Instead, virtual memory systems use write-back. Virtual page number Page offset 31 30 29 28 27 3 2 1 0 15 14 13 12 11 10 9 8 Physical page number Page offset 29 28 27 3 2 1 0 15 14 13 12 11 10 9 8 Virtual address Physical address Translation FIGURE 5.26 Mapping from a virtual to a physical address. ! e page size is 2 12 ! 4 KiB. ! e number of physical pages allowed in memory is 2 18, since the physical page number has 18 bits in it. ! us, main memory can have at most 1 GiB, while the virtual address space is 4 GiB. 5.7 Virtual Memory 431 ! e next few subsections address these factors in virtual memory design. Elaboration: We present the motivation for virtual memory as many virtual machines sharing the same memory, but virtual memory was originally invented so that many programs could share a computer as part of a timesharing system. Since many readers today have no experience with time-sharing systems, we use virtual machines to motivate this section. Elaboration: For ser vers and even PCs, 32-bit address processors are problematic. Although we normally think of virtual addresses as much larger than physical addresses, the opposite can occur when the processor address size is small relative to the state of the memor y technology. No single program or vir tual machine can bene! t, but a collection of programs or vir tual machines running at the same time can bene! t from not having to be swapped to memor y or by running on parallel processors. Elaboration: The discussion of virtual memory in this book focuses on paging, which uses ! xed-size blocks. There is also a variable-size block scheme called segmentation . In segmentation, an address consists of two par ts: a segment number and a segment offset. The segment number is mapped to a ph ysical address, and the offset is added to ! nd the actual physical address. Because the segment can var y in size, a bounds check is also needed to make sure that the offset is within the segment. The major use of segmentation is to suppor t more powerful methods of protection and sharing in an address space. Most operating system textbooks contain extensive discussions of segmentation compared to paging and of the use of segmentation to logically share the address space. The major disadvantage of segmentation is that it splits the address space into logically separate pieces that must be manipulated as a two-par t address: the segment number and the offset. Paging, in contrast, makes the boundar y between page number and offset invisible to programmers and compilers. Segments have also been used as a method to extend the address space without changing the word size of the computer. Such attempts have been unsuccessful because of the awkwardness and performance penalties inherent in a two-part address, of which programmers and compilers must be aware. Many architectures divide the address space into large ! xed-size blocks that simplify protection between the operating system and user programs and increase the ef! ciency of implementing paging. Although these divisions are often called “segments,” this mechanism is much simpler than variable block size segmentation and is not visible to user programs; we discuss it in more detail shortly. Placing a Page and Finding It Again Because of the incredibly high penalty fo r a page fault, designers reduce page fault frequency by optimizing page placement. If we allow a virtual page to be mapped to any physical page, the operating system can then choose to replace any page it wants when a page fault occurs. For example, the operating system can use a segmentation A variable-size address mapping scheme in which an address consists of two parts: a segment number, which is mapped to a physical address, and a segment o" set. 432 Chapter 5 Large and Fast: Exploiting Memory Hierarchy sophisticated algorithm and complex data structures that track page usage to try to choose a page that will not be needed for a long time. ! e ability to use a clever and # exible replacement scheme reduces the page fault rate and simpli$ es the use of fully associative placement of pages. As mentioned in Section 5.4, the di% culty in using fully associative placement is in locating an entry, since it can be anywhere in the upper level of the hierarchy. A full search is impractical. In virtual memory systems, we locate pages by using a table that indexes the memory; this structure is called a page table , and it resides in memo ry. A page table is indexed with the page number from the virtual address to discover the corresponding physical page number. Each program has its own page table, which maps the virtual address space of that program to main memory. In our library analogy, the page table corresponds to a mapping between book titles and library locations. Just as the card catalog may contain entries for books in another library on campus rather than the local branch library, we will see that the page table may contain entries for pages not present in memory. To indicate the location of the page table in memory, the hardware includes a register that points to the start of the page table; we call this the page table register . Assume for now that the page table is in a $ xed and contiguous area of memory. ! e page table, together with the program counter and the registers, speci$ es the state of a virtual machine. If we want to allow another virtual machine to use the processor, we must save this state. Later, a& er restoring this state, the virtual machine can continue execution. We o& en refer to this state as a process . ! e process is considered active when it is in possession of the processor; otherwise, it is considered inactive . ! e operating system can make a process active by loading the process’s state, including the program counter, which will initiate execution at the value of the saved program counter. ! e process’s address space, and hence all the data it can access in memory, is de$ ned by its page table, which resides in memory. Rather than save the entire page table, the operating system simply loads the page table register to point to the page table of the process it wants to make active. Each process has its own page table, since di" erent processes use the same virtual addresses. ! e operating system is responsible for allocating the physical memory and updating the page tables, so that the virtual address spaces of di" erent processes do not collide. As we will see shortly, the use of separate page tables also provides protection of one process from another. page table ! e table containing the virtual to physical address translations in a virtual memory system. ! e table, which is stored in memory, is typically indexed by the virtual page number; each entry in the table contains the physical page number for that virtual page if the page is currently in memory. Hardware/ Software Interface 5.7 Virtual Memory 433 Figure 5.27 uses the page table register, the virtual address, and the indicated page table to show how the hardware can form a physical address. A valid bit is used in each page table entry, just as we did in a cache. If the bit is o" , the page is not present in main memory and a page fault occurs. If the bit is on, the page is in memory and the entry contains the physical page number. Because the page table contains a mapping for every possible virtual page, no tags are required. In cache terminology, the index that is used to access the page table consists of the full block address, which is the virtual page number. Virtual page number Page offset 31 30 29 28 27 3 2 1 0 15 14 13 12 11 10 9 8 Physical page number Page offset 29 28 27 3 2 1 0 15 14 13 12 11 10 9 8 Virtual address Physical address Page table register Physical page number Valid Page table If 0 then page is notpresent in memory 20 12 18 FIGURE 5.27 The page table is indexed with the virtual page number to obtain the corresponding portion of the physical address. We assume a 32-bit address. ! e page table pointer gives the starting address of the page table. In this $ gure, the page size is 2 12 bytes, or 4 KiB. ! e virtual address space is 2 32 bytes, or 4 GiB, and the physical address space is 2 30 bytes, which allows main memory of up to 1 GiB. ! e number of entries in the page table is 2 20, or 1 million entries. ! e valid bit for each entry indicates whether the mapping is legal. If it is o" , then the page is not present in memory. Although the page table entry shown here need only be 19 bits wide, it would typically be rounded up to 32 bits for ease of indexing. ! e extra bits would be used to store additional information that needs to be kept on a per-page basis, such as protection. 434 Chapter 5 Large and Fast: Exploiting Memory Hierarchy Page Faults If the valid bit for a virtual page is o" , a page fault occurs. ! e operating system must be given control. ! is transfer is done with the exception mechanism, which we saw in Chapter 4 and will discuss again later in this section. Once the operating system gets control, it must $ nd the page in the next level of the hierarchy (usually # ash memory or magnetic disk) and de cide where to place the requested page in main memory. ! e virtual address alone does not immediately tell us where the page is on disk. Returning to our library analogy, we cannot $ nd the location of a library book on the shelves just by knowing its title. Instead, we go to the catalog and look up the book, obtaining an address for the location on the shelves, such as the Library of Congress call number. Likewise, in a virtual memory system, we must keep track of the location on disk of each page in virtual address space. Because we do not know ahead of time when a page in memory will be replaced, the operating system usually creates the space on # ash memory or disk for all the pages of a process when it creates the process. ! is space is called the swap space . At that time, it also creates a data structure to record where each virtual page is stored on disk. ! is data structure may be part of the page table or may be an auxiliary data structure indexed in the same way as the page table. Figure 5.28 shows the organization when a single table holds either the physical page number or the disk address. ! e operating system also creates a data structure that tracks which processes and which virtual addresses use each physical page. When a page fault occurs, if all the pages in main memory are in use, the operating system must choose a page to replace. Because we want to minimize the number of page faults, most operating systems try to choose a page that they hypothesize will not be needed in the near future. Using the past to predict the future, operating systems follow the least recently used (LRU) replacement scheme, which we mentioned in Section 5.4. ! e operating system searches for the le ast recently used page, assuming that a page that has not been used in a long time is less likely to be needed than a more recently accessed page. ! e replaced pages are written to swap space on the disk. In case you are wondering, the operating system is just another process, and these tables controlling memory are in memory; the details of this seeming contradiction will be explained shortly. swap space ! e space on the disk reserved for the full virtual memory space of a process. 5.7 Virtual Memory 435 Implementing a completely accurate LRU scheme is too expensive, since it requires updating a data structure on every memory reference. In stead, most operating systems approximate LRU by keeping track of which pages have and which pages have not been recently used. To help the operating system estimate the LRU pages, some computers provide a reference bit or use bit , which is set whenever a page is access ed. ! e operating system periodically clears the reference bits and later records them so it can determine which pages were touched during a particular time period. With this usage information, the operating system can select a page that is among the least recently referenced (detected by having its reference bit o" ). If this bit is not provided by the hardware, the operating system must $ nd another way to estimate which pages have been accessed. Hardware/ Software Interface reference bit Also called use bit . A $ eld that is set whenever a page is accessed and that is used to implement LRU or other replacement schemes. Page tablePhysical page ordisk address Physical memory Virtual pagenumber Disk storage 1111011 11 1 0 0 Valid FIGURE 5.28 The page table maps each page in virtual memory to either a page in main memory or a page stored on disk, which is the next level in the hierarchy. ! e virtual page number is used to index the page table. If the valid bit is on, the page table supplies the physical page number (i.e., the starting address of the page in memory) corr esponding to the virtual page. If the valid bit is o" , the page currently resides only on disk, at a speci$ ed disk address. In many syste ms, the table of physical page addresses and disk page addresses, while logically one tabl e, is stored in two separate data structures. Dual tables are justi$ ed in part because we must keep the disk addresses of all the pages, even if they are currently in main memory. Remember that the pages in main memory and the pages on disk are the same size. 436 Chapter 5 Large and Fast: Exploiting Memory Hierarchy Elaboration: With a 32-bit virtual address, 4 KiB pages, and 4 bytes per page table entry, we can compute the total page table size: Number of page table entries 2 2 32 20 !! 212 Size of page table 2 page table entries 2 bytes page tabl 20 2 ee entry 4 MiB That is, we would need to use 4 MiB of memory for each program in execution at any time. This amount is not so bad for a single process. What if there are hundreds of processes running, each with their own page table? And how should we handle 64-bit addresses, which by this calculation would need 2 52 words? A range of techniques is used to reduce the amount of storage required for the page table. The ! ve techniques below aim at reducing the total maximum storage required as well as minimizing the main memory dedicated to page tables: 1. The simplest technique is to keep a limit register that restricts the size of the page table for a given process. If the virtual page number becomes larger than the contents of the limit register, entries must be added to the page table. This technique allows the page table to grow as a process consumes more space. Thus, the page table will only be large if the process is using many pages of virtual address space. This technique requires that the address space expand in only one direction. 2. Allowing growth in only one direction is not suf! cient, since most languages require two areas whose size is expandable: one area holds the stack and the other area holds the heap. Because of this duality, it is convenient to divide the page table and let it grow from the highest address down, as well as from the lowest address up. This means that there will be two separate page tables and two separate limits. The use of two page tables breaks the address space into two segments. The high-order bit of an address usually determines which segment and thus which page table to use for that address. Since the high-order address bit speci! es the segment, each segment can be as large as one-half of the address space. A limit register for each segment speci! es the cur rent size of the segment, which grows in units of pages. This type of segmentation is used by many architectures, including MIPS. Unlike the type of segmentation discussed in the third elaboration on page 431, this form of segmentation is invisible to the application program, although not to the operating system. The major disadvantage of this scheme is that it does not work well when the address space is used in a sparse fashion rather than as a contiguous set of virtual addresses. 3. Another approach to reducing the page table size is to apply a hashing function to the virtual address so that the page table need be only the size of the number of physical pages in main memory. Such a structure is called an inverted page table . Of course, the lookup process is slightly more complex with an inverted page table, because we can no longer just index the page table. 4. Multiple levels of page tables can also be used to reduce the total amount of page table storage. The ! rst level maps large ! xed-size blocks of virtual address space, perhaps 64 to 256 pages in total. These large blocks are sometimes called segments, and this ! rst-level mapping table is sometimes called a 5.7 Virtual Memory 437 segment table, though the segments are again invisible to the user. Each entry in the segment table indicates whether any pages in that segment are allocated and, if so, points to a page table for that segment. Address translation happens by ! rst looking in the segment table, using the highest-order bits of the address. If the segment address is valid, the next set of high-order bits is used to index the page table indicated by the segment table entry. This scheme allows the address space to be used in a sparse fashion (multiple noncontiguous segments can be active) without having to allocate the entire page table. Such schemes are particularly useful with very large address spaces and in software systems that require noncontiguous allocation. The primary disadvantage of this two-level mapping is the more complex process for address translation. 5. To reduce the actual main memory tied up in page tables, most modern systems also allow the page tables to be paged. Although this sounds tricky, it works by using the same basic ideas of virtual memory and simply allowing the page tables to reside in the virtual address space. In addition, there are some small but critical problems, such as a never-ending series of page faults, which must be avoided. How these problems are overcome is both very detailed and typically highly processor speci! c. In brief, these problems are avoided by placing all the page tables in the address space of the operating system and placing at least some of the page tables for the operating system in a portion of main memory that is physically addressed and is always present and thus never on disk. What about Writes? ! e di" erence between the access time to the cache and main memory is tens to hundreds of cycles, and write-through schemes can be used, although we need a write bu" er to hide the latency of the write from the processor. In a virtual memory system, writes to the next level of the hierarchy (disk) can t a ke millions of pro cess or clock cycles; therefore, building a write bu" er to allow the system to write-through to disk would be completely impractical. Instead, virtual memory systems must use write-back, performing the individual writes into the page in memory, and copying the page back to disk when it is replaced in the memory. A write-back scheme has another major advantage in a virtual memory system. Because the disk transfer time is small compared with its access time, copying back an entire page is much more e% cient than writing individual words back to the disk. A write-back operation, although more e% cient than transferring individual words, is still costly. ! us, we would like to know whether a page needs to be copied back when we choose to replace it. To track whether a page has been written since it was read into the memory, a dirty bit is added to the page table. ! e dirty bit is set when any word in a page is written. If the operating system chooses to replace the page, the dirty bit indicates whether the page needs to be written out before its location in memory can be given to another page. Hence, a modi$ ed page is o& en called a dirty page. Hardware/ Software Interface 438 Chapter 5 Large and Fast: Exploiting Memory Hierarchy Making Address Translation Fast: the TLB Since the page tables are stored in main memory, every memory access by a program can take at least twice as long: one memory access to obtain the physical address and a second access to get the data. ! e key to improving access performance is to rely on locality of reference to the page table. When a translation for a virtual page number is used, it will probably be needed again in the near future, because the references to the words on that page have both temporal and spatial locality. Accordingly, modern processors include a special cache that keeps track of recently used translations. ! is special address translation cache is traditionally referred to as a translation-lookaside bu! er (TLB) , although it would be more accurate to call it a tra nslation cache. ! e TLB corresponds to that little piece of paper we typically use to record the location of a set of books we look up in the card catalog; rather than continually searching the entire catalog, we record the location of several books and use the scrap of paper as a cache of Library of Congress call numbers. Figure 5.29 shows that each tag entry in the TLB holds a portion of the virtual page number, and each data entry of the TLB holds a physical page number. translation-lookaside bu! er (TLB) A cache that keeps track of recently used address mappings to try to avoid an access to the page table. 1111011 11 1 0 0 0000000 11 1 0 0 1001011 11 1 0 0 Physical pageor disk address Valid Dirty Ref Page table Physical memory Virtual pagenumber Disk storage 111101 011000 111101 Physical page address Valid Dirty Ref TLB Tag FIGURE 5.29 The TLB acts as a cache of the page table for the entries that map to physical pages only. ! e TLB contains a subset of the virtual-to-physical page mappings that are in the page table. ! e TLB mappings are shown in color. Because the TLB is a cache, it must have a tag $ eld. If there is no matching entry in the TLB for a page, the page table must be examined. ! e page table either supplies a physical page number for the page (which can then be us ed to build a TLB entry) or indicates that the page resides on disk, in which case a page fault occurs. Since th e page table has an entry for every virtual page, no tag $ eld is needed; in other words, unlike a TLB, a page table is not a cache.