Neal is an applications engineer for Intel Corp. and can be reached at 2625 Walsh Ave., SC4-40, Santa Clara, CA 95051.
Memory management is a challenge for multitasking operating systems. To combat this difficulty, the Intel 80386 architecture has a method for managing memory called "paging," which is in addition to the segmentation features of the 80286. Paging can increase efficiency of virtual memory multitasking operating systems that run 8086, 80286, and 80386 microprocessor software. This article explains how paging increases the performance for multitasking operating systems and why paging is a requirement for multitasking 8086 and 32-bit 80386 microprocessor applications. In order to make use of the information in this article, you should have basic knowledge of protected mode and segmentation on the 80286 or 80386 microprocessor.
Both the 8086 and the 80286 address memory with a linear address. For systems that use these processors, or the 386 CPU without paging, the linear address is equivalent to the physical address. Address translation on the 386 CPU is shown in Figure 1. Notice that the paging unit comes after the linear address calculation. The paging unit translates the logical address seen by the programs into the physical address that goes out on the bus, which allows paging to be performed by the operating system but does not impact applications in any manner.
A segment is used to define the task's logical address space, which consists of one or more segments. The 80286 allows segments of up to 64K, and the 386 microprocessors allow segments up to 4 gigabytes long. As any experienced programmer knows, segments are visible to the application programmer, although less so on the 386 due to its larger size.
Microsoft's OS/2 currently uses segments as the basis for its virtual memory management. The 80286's maximum segment size of 64K makes segment-based physical memory allocation possible. With the 386 microprocessor, in which segments can be up to 4 gigabytes, allocating memory on such a large basis is not practical.
Segmentation-based memory management has additional shortcomings. When variable sized segments are used for physical memory allocation, for example, memory fragmentation often occurs. Fragmentation occurs when the free memory in a system consists of discontinuous small sections. Then when the operating system needs to load a large segment, it must perform a costly rearranging of memory. To overcome fragmentation, some segmentation-based schemes allocate the maximum segment size when any size segment is loaded. Although this overcomes the fragmentation problem, it wastes memory. Clearly a new method that overcomes these inefficiencies and works with 32-bit code is needed. The new method for virtual memory management is paging.
While paging is enabled, the processor translates a linear address to a physical address with the aid of page tables. Like mainframe computers, the page tables are arranged in a two-level hierarchy, as shown in Figure 2. The page table directory base, which is the control register CR3, points to the page table directory. The directory is one page long and contains entries for 1,024 page tables. Page tables are also one page long, and the entries in a page table describe 1,024 pages; each page is 4K in size. As an option, tasks can have their own page table directory, for there is a page table directory base associated with each task.
The processor uses the upper 10 bits of the linear address as an index into the directory. Each directory entry holds 20 bits of addressing information, which contain the address of a page table. The processor uses these 20 bits and the middle 10 bits of the linear address to form the page table address. The address contents of the page table entry and the lower 12 bits of the linear address form the 32-bit physical address.
Paging information is stored in the on-chip TLB and in memory. If the processor had to access these page tables in memory each time a reference was made, performance would suffer. To save the overhead of the page table lookups, the processor automatically caches mapping information for 32 recently used pages in an on-chip translation lookaside buffer. The TLB's 32 entries cover 4K, each providing a total cover of 128K of memory addresses. The TLB is flushed by changing the value of CR3, which is commonly accomplished by a privileged MOV instruction or a task switch.
As shown in Figure 3, only when the processor does not find the mapping information for a page in the TLB does it perform a page table lookup from information stored in memory. To improve hit rates, the TLB is four-way set associative, meaning each translation can be stored in one of four locations in the TLB. The result is that for typical systems, 97-99 percent of the address references are TLB hits, requiring no memory references to translate. When a TLB miss occurs, the processor replaces an older TLB entry with the new entry that is likely to be used again. This replacement, called TLB miss processing, is performed entirely in hardware.
Virtual memory allows large or multiple programs to be executed as if the entire program were in memory, even though portions are still on disk. In the case of a large program that has 20 Mbytes of data, for example, and a computer that has only 2 Mbytes of memory, the operating system can load and run the program. An operating system that uses demand paging can multitask more applications in less physical memory than an operating system that uses segmentation for memory allocation. The information for efficiently accomplishing memory management lies within the page directory entries and page table entries. In Figure 4, in the lower 12 bits of each of these entries there are several control bits used by the operating system for keeping track of which pages are in memory, which pages are on disk, information for deciding which page should be swapped out in favor of a new page, and if the swapped page needs to be written back to disk or merely discarded.
If set to 1, the P (present) bit indicates that the entry is present in memory. If the P bit is 0, any attempt to access this page will cause a page fault (exception 14) prior to the memory access. When a page fault occurs, the processor passes control to the interrupt 14 handler, part of the operating system that must read the needed page into memory and return execution to the program. The handler reads the contents of CR2 to decide which page is required. If there is no more room in physical memory to load in another page, the handler must decide which presently loaded page should be discarded. Although the operating system cannot be sure which pages will not be needed in the future, it can make a very good guess based on the least recently used pages. The A (accessed) bit and the bits reserved for operating-system use determine which pages have not been used recently. The processor's hardware automatically sets the A bit to 1 whenever the processor accesses the page; the bit can only be cleared by software. By periodically clearing the A bits, the operating system can keep track of pages not recently used. The A bit, combined with managing the operating system reserved bits, allows an accurate "least recently used" algorithm to be implemented for page management.
Once the operating system determines the page that will be discarded from RAM, it must then decide if the page needs to be written back to disk. The D (dirty) bit indicates if the page has been written to. If the D bit is set, then the operating system knows that it must be written back to disk. If the D bit is not set, then the copy of the page that is currently on the disk is the most recent version. The U/S (user/supervisor) and R/W (read/write) bits are described in the page-based protection section later on in this article.
The method of swapping pages in and out of memory when needed is called demand paging. Unix System V for the 386 microprocessor has always offered this feature, and in September 1988, PharLap Software announced that 386/VMM, which runs on top of 386/DOS-Extender, will also support demand paging. With PharLap's development tools and a compiler, such as 80386 High C Compiler from Metaware, users can develop large applications that can take advantage of demand paging.
In addition to virtual memory management, paging has another useful feature: It can be used to do a simple remapping of memory, a feature used in some DOS control programs. Programs such as Compaq's CEMM, Quarterdeck's QEMM-386, and Qualitas's 386-to-the-MAX use remapping ability to implement various features. Application programs addresses that use the LIM (Lotus, Intel, Microsoft) specification for accessing expanded memory, for instance, are remapped in software to use fast extended memory, thus eliminating the need for special memory board's external mapping hardware. This type of program also allows extended memory to be mapped into the DOS-accessible 512K - 640K range on 386 microprocessor-based PCs that have 512K of memory on the motherboard. In addition, it allows relocation of terminate-and-stay-resident utilities outside of DOS's 640K.
The 80386 provides many protection mechanisms that operating systems can selectively employ to fit their needs. Segmentation provides the basis for much of the task-based protection and multilevel protection schemes. Level 3 of segmentation-based protection corresponds to user level for paging, and levels 0, 1, and 2 correspond to supervisor level.
Paging has a separate protection mechanism that is sufficient for most operating systems. Paging protects supervisor memory and allows for write protecting of user pages. The U/S and R/W bits are found in each page directory entry and page table entry. Their presence in both levels allows more selective control over the access to page groups and individual pages. The operating system can allow user programs to have read only, read and write, or no access to a given page or page group. If a memory access violates the page protection attributes, such as user level code writing a read only page, an exception 14 will be generated.
Exception 14 is used for reporting page access violations and page faults. To distinguish the cause of an exception 14, the operating system examines a 16-bit error code that is pushed as part of the page fault handler. From the error code and the faulting linear address, stored in CR2, the operating system can correctly handle the fault and resume execution.
For running existing code, one of the biggest advantages of the 386 microprocessor is in the support for multitasking DOS applications. Microsoft's current 80286-based OS/2 does not allow multitasking of DOS applications, but the 386 can multitask DOS applications with virtual 86 mode. IGC's VM/ 386, Microsoft's Windows/386, Quarterdeck's DESQview, and several software vendors offer multitasking of DOS applications as a major feature of their software. Other products, like MERGE and VPIX, use virtual 86 mode for running DOS applications under Unix.
The 386 can execute 8086 applications in both real mode and virtual 86 mode. Virtual 86 mode allows the execution of 8086 applications while still allowing use of paging. The main difference between real and protected mode, however, is how the segment selectors are interpreted. When the processor is executing in virtual mode, the segment registers are used as in real mode. The contents of the segment register are shifted left 4 bits and added to the offset to form the segment linear address. When running in protected mode, the processor determines which applications are protected mode and which are 8086 applications. The 8086 applications require their segments to be interpreted as in real mode.
Paging is crucial to multitasking 8086 applications. With paging, the applications can be executed anywhere in memory, not just the lower 1 Mbyte. Without this ability, only 640K of applications would be multitaskable. The paging hardware allows the 20-bit linear address produced by a virtual mode program to be divided into up to 256 pages. Each one of the pages can be relocated anywhere in physical memory. The operating system is able to treat memory for virtual 86 applications as it does memory for 32-bit applications.
Because CR3, the page directory base register, is different for each task, each task can use a different mapping scheme to map pages to different physical locations. Of course entries can appear in both tables to allow sharing of operating system code between applications.
Paging is the 80386's answer to the challenges of memory management for today's multitasking operating systems. Whether a task's logical address space consists of one segment or many, an operating system can subdivide the linear address space into pages. To an operating system, pages are more convenient units than are segments for allocation because pages are all the same size, which prevents common problems that occur while using segments for memory allocation. Additionally, page-based swapping is better tuned to disk drives than segment-based swapping.
Paging is the only mechanism for virtual memory management of 32-bit applications (in which segments can be up to 4 gigabytes in length) and for virtual 8086 applications, which all exist in the lowest Mbyte of the linear address space. The fast on-chip TLB and hardware TLB miss processing allow the 386 microprocessor to perform these advanced memory management techniques without reducing the application's processing power.
When the 80386 microprocessor is brought out of reset, it first executes in real mode. To use paging, the processor must be executing in protected mode. The steps for entering and exiting protected mode are described in the DDJ article "80386 Protected Mode Initialization" by Neal Margulis (October 1988). To enable paging, follow these steps:
Once paging is turned on, all linear addresses are paged to the correct physical address. The address translation information is then automatically cached into the TLB each time the hardware performs a page translation from the tables in memory. Should you change any of the page table information in memory, or decide to use a different set of page tables, you must perform a MOV CR3, xxxxxxxx to invalidate the current TLB entries so that the new paging information will be used.
When disabling paging you must do the following:
After paging is disabled, the linear address and physical address are the same. --N. M.
Copyright © 1989, Dr. Dobb's Journal