Discussion 21
Virtual Memory
Many people think of virtual memory as a way of making a disk appear to be an extension of main memory. While this is a major benefit of virtual memory, it is not a definition. Virtual memory can be defined as
A mapping from a virtual address space to a physical address space.
OR
A mapping from a name space to an address space.
In either case, the key term is mapping. The processor generates an address that is sent through a mapping function to produce the actual bit pattern presented to the address lines of the memory. The insertion of the mapping function between the processor and the memory adds flexibility, because it allows us to store data in different places in the memory yet have it appear in a different logical arrangement from the perspective of the program.
One of the advantages of this flexibility is that programs can be compiled for a standard address space, and can then be loaded into the available memory and run without modification. For example, in a multitasking environment one program can be arranged to fit into memory along with an arbitrary combination of other programs.
Another advantage is that the mapping function can signal (through an exception) when locations are mapped to locations outside of main memory, such as on disk storage. If such an exception occurs, commonly called a page fault, then the operating system can load the data in from disk and adjust the mapping function so that accesses to the data refer to wherever it wound up in main memory.
In this latter sense, virtual memory provides a way to make main memory appear larger than it is. It saves the programmer from having to explicitly move portions of the program or data in and out from disk. It is thus most useful for running large programs on small machines.
Unfortunately, the performance of virtual memory is best when a small application runs on a large machine. The reason is that heavy reliance on the disk drive (which is 5 orders of magnitude slower than main memory) increases the miss rate at the main memory level of the hierarchy. It was noted earlier that programming models deal with this wide performance gap by making access to the secondary memory level explicit. However, virtual memory is a mechanism that attempts to hide the difference between these layers through an abstraction. The unknowledgeable programmer can be easily lead by this abstraction to write programs that give extremely poor performance. Experienced programmers try to arrange their code and data to avoid excessive reliance on virtual memory.
Fortunately, in a multitasking situation, the time required to access the disk can often be hidden by switching to another task. Because main memories are now quite large, it is less frequent for a single program to need virtual memory (large data sets being an exception). However, with a multitasking OS, multiple programs can use up the memory and also keep the processor busy.
There are basically three approaches to implementing virtual memory: Paging, segmentation, and a combination of the two called paged segmentation. We'll look at each of these approaches in turn.
Paging
Memory is divided into fixed-size blocks called pages. Main memory contains some number of pages (memory size / page size), which is smaller than the number of pages in the virtual address space (virtual address range / page size).
For example, if the page size is 4K and the physical memory is 256M (64K pages) and the virtual memory is 4G (1 M pages) then there is a factor of 16 to 1 mapping.
In order to perform the mapping function, a table lookup is employed. A page table is kept with one entry per virtual page. (In reality, a 1M entry table would not be used -- parts of it would also be mapped in virtual memory, and in may cases those pages would never be stored anywhere because they would never be accessed.)
A page table entry might have the following form:
The Presence Bit indicates whether the physical page is in main memory or must be fetched from secondary storage (a page fault). The secondary storage address is used to locate the data on disk. Physical page address is substituted for the virtual page address as a result of the lookup.
A virtual address takes the following form for a page of 4K words:
The page offset (low order 12 bits) is the location of the desired word within a page. The Presence Bit indicates whether the physical page is in main memory or must be fetched from secondary storage (a page fault).
Thus, the virtual address translation hardware appears as follows:
The virtual address from the CPU is split into the offset and page number. The page number becomes the index into the table (requiring a shift and an add of the base address of the table to get a proper address).The table entry is fetched, starting with the presence bit and the physical page. When the presence bit indicates that the page is in main memory, it simply substitutes the physical page from the table for the virtual page portion of the address. When the presence bit indicates that the page is not in main memory, it triggers a page fault exception, and the OS must initiate the disk transfer that brings the page into memory.
While a disk transfer is in progress, the OS my cause another task to execute or it may simply stall the current task and sit idle. In either case, once the transfer is complete, the OS stores the new physical page number into the page table and jumps back to the instruction causing the page fault so that the access can be reissued.
Thus, any virtual page may be stored at any physical page location and the addressing hardware performs the translation automatically.
A page table can also contain privilege information consisting of an owner process ID and level of access. On any access, the current process ID in the program status word is checked against the owner process ID portion of the page table entry and if there is a match and the type of access (read vs. write) is allowed, then the access proceeds. Otherwise an access privilege violation exception is signaled.
Pages are usually loaded in this manner, which is called "on demand". However, schemes have also been devised in which the historical behavior of a task is recorded, and when the task is suspended, its working set of pages is reloaded before it restarts.
Once main memory pages are all allocated to virtual pages, then any accesses to additional virtual pages force pages to be replaced (or "swapped"). It should be obvious that, just as with a cache, replacement necessitates a replacement policy. Typical policies for page replacement are the same as for a cache: LRU, FIFO and random. However, because page replacement is a costly operation, it is more often the case that the more costly LRU policy is employed.
Just as in the cache, the page table entry can contain a dirty bit that indicates whether the contents of a page have been changed. If no change has occurred, then we can skip the writing back of the page before we replace it. In fact, because of the savings of not writing a page back, the LRU policy is sometimes altered to select a page that is unchanged and not quite the least recently used over an altered page that was least recently used.
As we noted before, LRU has a degenerate pattern of accesses that can cause pages to be thrown out just before they are needed again. When pages are repeatedly replaced due to such a pattern, or simply because the program's working set is so large that it forces continual replacement with few accesses to each page, then it is said to be thrashing. Given the difference in access speed between disk and RAM, a thrashing program can exhibit a factor of 100,000 loss in performance. To put this in perspective, a program that takes 6 seconds to execute in RAM would take almost a week to execute if it thrashes in virtual memory.
One inefficiency of paging is that the fixed size of a page means that some space is wasted in partially filled pages. Although not as much of a concern today, this "internal fragmentation" was considered to be a serious problem when machines had smaller main memories (e.g., 32K = 8 pages). Another problem with paged virtual memory is that it is a "flat" virtual address (or name) space. There is just one virtual space shared by all processes, and the processes have to be statically relocated when loaded.
Segmentation
The operating system can create multiple virtual address spaces, each starting at an arbitrary location and with arbitrary length. The start of a segment is virtual address 0. Each process can be assigned a different segment, and so it is completely unaware that other processes are sharing the memory with it. Relocation is effectively done dynamically at run time by the virtual memory mapping mechanism.
Segmentation is implemented in a manner much like paging, through a lookup table. The difference is that each segment descriptor in the table contains the base address of the segment and a length.
Usually, segments are limited to starting on some power-of-two boundary that makes the mapping simpler to implement. A system may impose a limit on the number of active segments, and their minimum size may be limited to (virtual address range/maximum number of segments). The maximum number of segments is typically small compared to the virtual address range (for example 256), in order to keep the size of the segment tables small. Even so, under many circumstances, individual processes could be allocated multiple segments (e.g., for code, data, stack, heap, I/O).
A segment descriptor also typically carries some protection information, such as the read/write permission of the segment and the process ID. It will also have some housekeeping information such as a presence bit and dirty bit.
A virtual address in the segmentation scheme consists of a segment number and a segment offset (if a process has multiple segments, it has access to some of the bits of the segment number -- otherwise the segment number is just an ID assigned by the OS). In a pure segmentation scheme the segment offset field grows and shrinks (logically) depending on the length of the segment. In a typical implementation, this simply means that some of the high order bits of the offset are ignored.
Segmentation also suffers from internal fragmentation (some of a segment may be allocated but goes unused). In addition the variable size of the segments can lead to external fragmentation in which the allocation and deallocation of space for processes with segments of different sizes leaves a collection of holes that are too small for a new process to be fit into, yet there may be more than enough empty memory if all of the holes were collected into one space (or if the process could be split up). This situation is also known as checkerboarding.
External fragmentation is addressed through a process known as compaction in which all active processes are temporarily suspended and then relocated in order to gather together all of the memory holes. Compaction is a costly process, especially in machines that have large amounts of physical memory. Because the main memory is being completely rearranged, many memory access operations are required, and few of them can take any advantage of the cache.
Segmentation also suffers from the large unbroken nature of a segment. It is very costly to swap processes because an entire segment must be written out (except when the entering segment is smaller, in which case an amount equivalent to the entering segment must be saved to disk).
Paged Segmentation
The solution to the problems of external fragmentation in segmentation and the flat name space of paging is to combine the two into a paged segmentation scheme where segments contain pages and can be split up on page boundaries. Thus, paging occurs within the distinct name space of each segment, and segments can be distributed like pages on fixed boundaries that avoid checkerboarding. They can also be loaded and swapped on a page-by-page basis, making context switches less costly.
A virtual address in a paged segmented scheme is divided into three parts: a segment number, a page number, and an offset. The segment number points to an entry in a segment table. The segment descriptor then points to the page table for the segment and the page number is used to index into the page table. The page table contains the physical page number that is concatenated with the offset to generate the physical address. Thus, instead of having just a single page table, there is a separate page table for each segment. Because the segments can be limited in size, their page tables are sometimes small enough to be kept in memory.
Note that, as with segmentation, the logical size of the page number portion of the address grows and shrinks according to the size of the segment.
Acceleration of Virtual Address Translation
Each access in a paged-segmented virtual memory system generates two additional memory accesses (one to the segment table, and the other to the page table). Even if these tables are cached, the required accesses triple the time to transfer data between the memory and the CPU. If the tables are not cached, then the access can be far slower.
In order to avoid these delays, a specialized cache called a translation lookaside buffer (TLB), is used. Whenever a translation takes place, the segment and page number are stored together with the upper portion of the resulting physical address. The next time an access to the same virtual page is made, the cache fetches the translation and inserts it directly into the physical address, avoiding the extra memory references. Of course, when there is a miss in the TLB we must detect the miss and then the normal table lookup proceeds to generate the address which is stored as a new TLB entry.
A TLB is typically fully associative and fairly small in size (tens to a few thousand entries). Each entry serves for a large number of locations (e.g., 4K) and so normal exploitation of memory locality ensures that entries in the TLB change much less frequently than cache entries. Typical hit rates in a TLB are in the 99% to 99.9% range. Still, when a miss occurs it will typically cost 10 to 300 clock cycles. So if 1 in 100 accesses miss in the TLB and the average penalty is 30, then the processor slows down by nearly a third.
Virtual Memory and Caching
One question that a designer must face is whether to place the cache in front of the virtual memory translation or after it. The latter situation means that the cache is accessed with a physical address. The former means that the cache sees a virtual address.
A physically addressed cache has advantages of simplicity. It is possible for two processes to use the same virtual addresses, but the mapping function ensures that the physical addresses are distinct. Thus, there is no chance that aliasing could occur in the cache. In addition, recall that when DMA I/O occurs, the addresses must be compared to the contents of the cache so that cache lines are either written back or invalidated. This comparison is much easier when the cache is physically addressed. In a virtually addressed cache, a reverse translation has to take place (from physical to virtual address) in order to carry out the comparison.
On the other hand, a physically addressed cache only sees its address after it has gone through the mapping process. Even with a TLB, this typically introduces a one-cycle delay. Memory accesses can be pipelined so that the rate of data transfer is maintained, but when loads or stores occur in isolation and there are no independent operations to fill the resulting delay, then the CPU sees a memory wait state and is effectively slowed down by the mapping.
Most systems use a virtual level 1 cache followed by a physical level 2 cache. The level 1 cache sees no delay due to mapping, while the level 2 cache's physical mapping is compatible with comparisons to I/O operation accesses. If the level 2 cache keeps track of which of its lines are currently in the level 1 cache, then if it sees an I/O operation accessing one of those lines it can signal the level 1 cache to take action. Otherwise it can simply handle the I/O without affecting the level 1 cache.
© Copyright 1995, 1996, 2001 Charles C. Weems Jr. All
rights reserved.
Back to Chip Weems' home page.
Back to Computer Science Department home page.