CMSI 387: Welcome to Week 07

This Week's Agenda

For this week, here's the plan, Fran…

• Announcements
• Mechanisms for Virtual Memory
• Software/Hardware Interface
• Linear Page Tables
• Multilevel Page Tables
• Hashed Page Tables
• Segmentation
• Policies for Virtual Memory
• Fetch Policy
• Placement Policy
• Replacement Policy
• Security and Virtual Memory
• In-class Exercise

Mechanisms for Virtual Memory

Address mapping needs to be flexible, yet efficient. This means that the mapping function is stored in an explicit table, but at the granularity of pages rather than individual bytes or words. Many systems today use fixed-size pages, perhaps with a few exceptions for the operating system itself or hardware access, though research suggests that more general mixing of page sizes can be beneficial. Note that Linux has moved in this direction.

Typical page sizes have grown over the decades; today, the most common is 4 KB. Each page of virtual memory and each page frame of physical memory is this size, and each starts at an address that is a multiple of the page size. For example, with 4 KB pages, the first page (or page frame) has address 0, the next has address 4096, then 8192, and so forth. By the way, this is the reason for the 4096 size in the in-class exercise from last week!

Each page of virtual memory address space maps to an underlying page frame of physical memory, or it maps to none. For example, the figure shows one possible mapping, on a system with unrealistically few pages and page frames. The numbers next to the boxes are page numbers and page frame numbers. The starting addresses are these numbers multiplied by the page size. At the top of this figure, you can see that page 0 is stored in page frame 1. If the page size is 4 KB, this means that virtual address 0 translates to physical address 4096, virtual address 100 translates to physical address 4196, and so forth. The virtual address of the last 4-byte word in page 0, 4092, translates to the physical address of the last word in page frame 1, 8188. Up until this point, all physical addresses were found by adding 4096 to the virtual address. However, the very next virtual address, 4096, translates to the physical address 0, because it starts a new page, which is mapped differently. Note also that page frame 2 is currently not holding any page, and that pages 2 through 5 and page 7 have no translation available. In Exercise 6.5, you can gain experience working with this translation of virtual addresses into physical addresses by translating the addresses for page 6.

Often there are tens or hundreds of thousands of page frames and at least hundreds of thousands of pages. As a result, operating system designers need to think carefully about the data structure used to store the table that maps virtual page numbers to physical page frame numbers. Whatever data structure the operating system uses for its page table, it will need to communicate the mapping information to the hardware's MMU, which actually performs the mapping. The nature of this software/hardware interface constrains the page table design and also provides important context for comparing the performance of alternative page table structures.

Software/Hardware Interface

Performance considerations explain why such an important data structure should be nearly useless (in the literal sense). Every single memory access performed by the processor generates a virtual address that needs translation to a physical address. Naively, this would mean that every single memory access from the processor requires a lookup operation in the page table. Performing that lookup operation would require at least one more memory access, even if the page table were represented very efficiently. Thus, the number of memory accesses would at least double: for each real access, there would be one page able access. Because memory performance is often the bottleneck in modern computer systems, this means that virtual memory might well make programs run half as fast – unless the page table lookup can be mostly avoided. Luckily, it can.

The virtual addresses accessed by realistic software are not random; instead, they exhibit both temporal locality and spatial locality. That is, addresses that are accessed once are likely to be accessed again before long [temporal], and nearby addresses [spacial] are also likely to be accessed soon. Because a nearby address is likely to be on the same page, both kinds of locality wind up creating temporal locality when considered at the level of whole pages. If a page is accessed, chances are good that the same page will be accessed again soon, whether for the same address or another.

The MMU takes advantage of this locality by keeping a quickly accessible copy of a modest number of recently used virtual-to-physical translations. That is, it stores a limited number of pairs, each with one page number and the corresponding page frame number. This collection of pairs is called the Translation Lookaside Buffer [TLB]. Most memory accesses will refer to page numbers present in the TLB, and so the MMU will be able to produce the corresponding page frame number without needing to access the page table. This happy circumstance is known as a TLB hit; the less fortunate case, in which the TLB does not contain the needed translation, is a TLB miss .

The TLB is one of the most performance-critical components of a modern microprocessor. In order for the system to have a fast clock cycle time and perform well on small benchmarks, the TLB must be very quickly accessible. Yet, in order for the system's performance not to fall off sharply on larger workloads, the TLB must be reasonably large [perhaps hundreds of entries], so that it can still prevent most page table accesses. Unfortunately, these two goals are in conflict with one another.

Hardware designers, operating system designers, and application software builders, then, must find a way to cooperate in the following ways:

• hardware designers ameliorate the problem by including two TLBs, one for instruction fetches and one for data loads and stores. That way, these two categories of memory access don't need to compete for the same TLB
• hardware designers may further ameliorate the problem by including a hierarchy of TLBs, analogous to the cache hierarchy. A small, fast level-one [L1] TLB makes most accesses fast, while a larger, slower level-two [L2] TLB ensures that the page table won't need to be accessed every time the L1 TLB misses. As an example, the AMD Opteron microprocessor contains a 40-entry L1 instruction and data TLBs, and it also contains 512-entry L2 instruction and data TLBs.
• hardware designers also give the operating system designers some tools for reducing the demand for TLB entries. For example, if different TLB entries can provide mappings for pages of varying sizes the operating system will be able to map large, contiguously allocated structures with fewer TLB entries, while still retaining flexible allocation for the rest of virtual memory.
• operating system designers need to use tools such as variable page size to reduce TLB entry consumption. At a minimum, even if all application processes use small pages (4 KB), the operating system itself can use larger pages. Similarly, a video frame buffer of many consecutive megabytes needn't be carved up into 4-KB chunks.
• More fundamentally, all operating system design decisions need to be made with an eye to how they will affect TLB pressure, because this is such a critical performance factor; an example is the size of the scheduler's time slices: switching processes frequently will increase TLB pressure and thereby hurt performance, even if the TLB doesn't need to be flushed at every process switch.
• application programmers also have a role to play. Programs that exhibit strong locality of reference will perform much better, not only because of the cache hierarchy, but also because of the TLB. The performance drop-off when your program exceeds the TLB's capacity is generally quite precipitous; we saw this with the in-class exercise last week as well.

At this point, you still need to learn how entries from the page table get loaded into the TLB. This leads to the topic of the software/hardware interface.

In general, the MMU loads page table entries into the TLB on a demand-driven basis. That is, when a memory access results in a TLB miss, the MMU loads the relevant translation into the TLB from the page table, so that future accesses to the same page can be TLB hits. The key difference between computer architectures is whether the MMU does this TLB loading autonomously, or whether it does it with lots of help from operating system software running on the processor.

In many architectures, the MMU contains hardware, known as a page table walker, that can do the page table lookup operation without software intervention. In this case, the operating system must maintain the page table in a fixed format that the hardware understands. The software/hardware interface consists largely of a single register that contains the starting address of the page table. The operating system just loads this register and lets the hardware deal with loading individual TLB entries. In other processors, the hardware has no specialized access to the page table. When the TLB misses, the hardware transfers control to the operating system using an interrupt. The operating system software looks up the missing address translation in the page table, loads the translation into the TLB using a special instruction, and resumes normal execution. Because the operating system does the page table lookup, it can use whatever data structure its designer wishes. The lookup operation is done not with a special hardware walker, but with normal instructions to load from memory. Thus, the omission of a page table walker renders the processor more flexible, as well as simpler. However, TLB misses become more expensive, as they entail a context switch to the operating system with attendant loss of cache locality.

Architectures also differ in how they handle process switches. Recall that each process may have its own private virtual memory address space. When the operating system switches from one process to another, the translation of virtual addresses to physical addresses needs to change as well. In some architectures, this necessitates flushing all entries from the TLB. [There may be an exception for global entries that are not flushed, because they are shared by all processes.] Other architectures tag the TLB entries with a process identifying number, known as an Address Space IDentifier [ASID]. A special register keeps track of the current process's ASID. For the operating system to switch processes, it simply stores a new ASID into this one register; the TLB need not be flushed. The TLB will hit only if the ASID and page number both match, effeectively ignoring entries belonging to other processes.

Linear Page Tables

A linear page table is an array with one entry per page in the virtual address space. The first entry in the table describes page 0, the next describes page 1, and so forth. To find the information about page N, one uses the same approach as for any array access: multiply n by the size of a page table entry and add that to the base address of the page table.

Recall that each page either has a corresponding page frame or has none. Therefore, each page table entry contains, at a minimum, a valid bit and a page frame number. If the valid bit is 0, the page has no corresponding frame, and the page frame number is unused. If the valid bit is 1, the page is mapped to the specified page frame. Real page tables often contain other bits which can indicate permissions [for example, whether writing is allowed], dirtiness, and so forth.

In the example of the previous page table diagram, you can see how the page numbers are NOT stored in the page table itself. Rather, they are implicit in the position of the entries. In a linear page table, as shown adjacent, the information about page N is thus stored at position number N in the table. It is easy to find which page frame is for which page, by a simple count. In this example, the first row, position 0, shows that page 0 is stored in in page frame 1. The second-to-last row, position 6, shows that page 6 is stored in page frame 3. The rows with the valid bit set to 0 indicate that no page frame holds the corresponding pages.

The fundamental problem with linear page tables is that real ones are much larger than this example. For a 32-bit address space with 4-KB pages, there are 220 pages, because 12 of the 32 bits are used to specify a location within a page of 4 KB or 212 bytes. Thus, if you again assume 4 bytes per page table entry, you now have a 4-MB page table. Storing one of those page tables for every process could use up an undesirably large fraction of a computer's memory. For example, if a computer runs 70 processes, that would be a total of 280 MB of page tables, over 1/4 GB of RAM just for page tables. Worse yet, modern processors are now using 64-bit address spaces. Even if you assume larger pages, it is hard to see how a linear page table spanning a 64-bit address space could be stored.

This problem of large page tables is not insurmountable — Intel supports them as one option for its current Itanium architecture. Because storing such a huge page table is inconceivable, the secret is to find a way to avoid storing most of the table.

Recall that virtual memory address spaces are generally quite sparse: only a small fraction of the possible page numbers actually have translations to page frames. [This is particularly true on 64-bit systems; the address space is billions of times larger than for 32-bit systems, whereas the number of pages actually used may be quite comparable.] This provides the key to not storing the whole linear page table: you need only store the parts that actually contain valid entries, and you can use virtual memory to do this:

• The pattern of address space usage, although sparse, is not completely random. Often, software will use quite a few pages in a row, leave a large gap, and then use many more consecutive pages. You can choose to store those chunks of the page table that contain any valid entries, even if there are also a few invalid entries mixed in, and not store those chunks that contain entirely invalid entries.
• In fact, you can choose your chunks of page table to be the same size as the pages themselves. For example, in a system with 4-KB pages and 4-byte page table entries, each chunk of page table would contain 1024 page table entries. Many of these chunks won't actually need storage, because there are frequently 1024 unused pages in a row. Therefore, you can view the page table as a bunch of consecutive pages, some of which need storing and some of which don't.
• Now for the trick: use virtual memory to store the page table. That way, you decouple the addresses of page table entries from where they are stored – if anywhere. The virtual addresses of the page table entries will form a nice orderly array, with the entry for page N being N entries from the beginning.
• There's still a potential problem: you are now using a virtual address to look up another virtual address, which will then look up another virtual address, and so on down the recursive rabbit hole. The solution to that is to have two DIFFERENT ways to store the virtual-to-physical mapping information. The linear page table is used for application-generated virtual addresses. The other is used for the translation of page table entry virtual addresses.

This may leave you wondering what the point of the linear page table is. If another representation is going to be needed anyway, why not use it directly as the main page table, for mapping all pages, rather than only indirectly, for mapping the page table's pages? To answer this, you need to remember that the MMU has a TLB in which it keeps track of recently used virtual-to-physical translations; repeated accesses to the same virtual page number don't require accesses to the page table. Only when a new page number is accessed is the page table [of whatever kind] accessed. This is true not only when translating the application's virtual address, but also when translating the virtual address of a page table entry.

Multilevel Page Tables

Recall that the practicality of linear page tables relies on two observations:

• Because valid page table entries tend to be clustered, if the page table is divided into page-sized chunks, there will be many chunks that don't need storage.
• The remaining chunks can be located as though they were in one big array by using virtual memory address translation to access the page table itself.

These two observations are quite different from one another. The first is an empirical fact about most present-day software. The second is a design decision. You could accept the first observation while still making a different choice for how the stored chunks are located. This is exactly what happens with multilevel page tables [also known as hierarchical page tables or forward-mapped page tables]. They too divide the page table into page-sized chunks, in the hopes that most chunks won't need storage. However, they locate the stored chunks without recursive use of virtual memory, by using a tree data structure, rather than a single array.

For simplicity, start by considering the two-level case. This suffices for 32-bit architectures and is actually used in the extremely popular IA-32 architecture, the architecture of Intel's Pentium and AMD's Athlon family microprocessors. The IA-32 architecture uses 4-KB pages and has page table entries that occupy 4 bytes. Thus, 1024 page-table entries fit within one page-sized chunk of the page table. As such, a single chunk can span 4 MB of virtual address space. The operating system on an IA-32 machine stores the physical base address of the page directory in a special register, where the hardware's page table walker can find it. Suppose that at some later point, the processor generates a 32-bit virtual address and presents it to the MMU for translation. The MMU uses the following process for address translation:

• Initially divide the 32-bit virtual address into its left-hand 20 bits [the page number] and its right-hand 12 bits [the offset within the page].
• Look up the 20-bit page number in the TLB. If a TLB hit occurs, concatenate the resulting page frame number with the 12-bit offset to form the physical address. The process is over.
• On the other hand, if a TLB miss occurred, subdivide the 20-bit page number into its left-hand 10 bits [the page directory index] and its right-hand 10 bits [the page table index].
• Load the page directory entry from memory; its address is four times the page directory index plus the page directory base address, which is taken from the special register.
• Check the page directory entry's valid bit. If it is 0, then there is no page frame holding the page in question – or any of its 1023 neighbors, for that matter. Interrupt the processor with a page fault.
• Conversely, if the valid bit is 1, the page directory entry also contains a physical base address for a chunk of page table.
• Load the page table entry from memory; its address is four times the page table index plus the page table base address, which comes from the previous step.
• Check the page table entry's valid bit. If it is 0, then there is no page frame holding the page in question. Interrupt the processor with a page fault.
• On the other hand, if the valid bit is 1, the page table entry also contains the physical page frame number. Load the TLB and complete the memory access.

The actual IA-32 design derives some additional advantages from having the page directory entries with their 4-MB spans:

• Each page directory entry can optionally point directly to a single large 4-MB page frame, rather than pointing to a chunk of page table entries leading indirectly to 4-KB page frames. This option is controlled by a page-size bit in the page directory entry. By using this feature, the operating system can more efficiently provide the mapping information for large, contiguously allocated structures.
• Each page directory entry contains permission bits, just like the page table entries do. Using this feature, the operating system can mark an entire 4-MB region of virtual address space as being read-only more quickly, because it doesn't need to set the read-only bits for each 4-KB page in the region. The translation process outlined earlier is extended to check the permission bits at each level and signal a page fault interrupt if there is a permission violation at either level.

The same principle used for two-level page tables can be expanded to any greater number of levels. If you have taken a course on data structures, you may have seen this structure called a trie [or perhaps a digital tree or radix tree]. The virtual page number is divided into groups of consecutive bits. Each group of bits forms an index for use at one level of the tree, starting with the leftmost group at the top level. The indexing at each level allows the chunk at the next level down to be located.

Achieving adequate performance with a four-level page table is challenging. Extending the architecture to full 64-bit virtual addresses requires two more levels be added to the page table. Other designers of 64-bit processors have made different choices: Intel's Itanium uses either linear page tables or hashed page tables, and the PowerPC uses hashed page tables.

Hashed Page Tables

Speaking of which…

Suppose you take a radical approach and reject the starting assumption. You will still assume that the address space is sparsely occupied; that is, many page table entries are invalid and should not be stored. [After all, no one buys 264 bytes of RAM for their 64-bit processor.] However, you will no longer make any assumption about clustering of the valid and invalid pages – they might be scattered randomly throughout the whole address space. This allows greater flexibility for the designers of runtime environments. As a consequence, you will have to store individual valid page table entries, independent of their neighbors.

Storing only individual valid page table entries without storing any of the invalid entries takes away the primary tool used by the previous approaches for locating entries. You can no longer find page N's entry by indexing N elements into an array – not even within each chunk of the address space. Therefore, you need to use an entirely different approach to locating page table entries. You can store them in a hash table, known as a hashed page table.

A hashed page table is an array of hash buckets, each of which is a fixed-sized structure that can hold some small number of page table entries. [In the Itanium architecture, each bucket holds one entry, whereas in the PowerPC, each bucket holds eight entries.] Unlike the linear page table, this array of buckets does not have a private location for each virtual page number; as such, it can be much smaller, particularly on 64-bit architectures.

The page number cannot be directly used as an index into the array. Instead, the page number is first fed through a many-to-one function, the hash function. That is, each page gets assigned a specific hash bucket by the hash function, but many different pages may get assigned the same bucket.

The performance of the table relies on the assumption that only a few of the pages assigned to a bucket will be valid and hence have page table entries stored. That is, the assumption is that only rarely will multiple valid entries be assigned to the same bucket, a situation known as a hash collision. To keep collisions rare, the page table size needs to scale with the number of valid page table entries. Luckily, systems with lots of valid page table entries normally have lots of physical memory and therefore have room for a bigger page table.

Even if collisions are rare, there must be some mechanism for handling them. One immediate consequence is that each page table entry will now need to include an indication of which virtual page number it describes. In the linear and multilevel page tables, the page number was implicit in the location of the page table entry. Now, any one of many different page table entries could be assigned to the same location, so each entry needs to include an identifying tag, much like in the TLB.

The possibility of collisions has another consequence, beyond necessitating page number tags. Even if collisions occur, each valid page table entry needs to be stored somewhere. Because the colliding entries cannot be stored in the same location, some alternative location needs to be available. One possibility is to have alternative locations within each hash bucket; this is why the PowerPC has room for eight page table entries in each bucket. Provided no collision involves more than this number of entries, they can all be stored in the same bucket. The PowerPC searches all entries in the bucket, looking for one with a matching tag.

If a collision involving more than eight entries occurs on a PowerPC, or any collision at all occurs on an Itanium processor, the collision cannot be resolved within the hash bucket. To handle such collisions, the operating system can allocate some extra memory and chain it onto the bucket in a linked list. This will be an expensive but rare occurrence.

As a result of these two factors and the addition of some extra features, the Itanium architecture uses 32-byte entries for hashed page tables versus 8-byte entries for linear page tables.

Incidentally, the fact that the Itanium architecture supports two different page table formats suggests just how hard it is to select one. Research continues into the relative merits of different formats under varying system workloads. As a result of this research, future systems may use other page table formats beyond those described here, though they are likely to be variants on one of these themes.

Some operating systems treat a hashed page table as a software TLB, a table similar to the hardware's TLB in that it holds only selected page table entries. This alternative is particularly attractive when porting an operating system [such as Linux] that was originally developed on a machine with multilevel page tables.

Segmentation

Thus far, we have talked as though virtual memory were synonymous with paging. Today, that is true. However, when virtual memory was first developed in the 1960s, there were two competing approaches: paging and segmentation. Some systems [notably Multics] also included a hybrid of the two. Thus, seen historically, segmentation was both a competitor and a collaborator of paging. Today, segmentation remains only in vestigial form. We can see signs of this in the fact that the UNIX and Linux operating systems still produce a segmentation fault. The IA-32 architecture still contains full support for segmentation, but no common operating system uses it, and the successor architectures [Itanium and AMD64] have dropped it. Therefore, we will not cover it in class. If you are interested, you can read the description in the text book beginning on page 243.

Policies for Virtual Memory

Thus far, we've defined virtual memory, explained its usefulness, and shown some of the mechanisms typically used to map pages to page frames. Mechanisms alone, however, are not enough. The operating system also needs a set of policies describing how the mechanisms are used. Those policies provide answers for the following questions:

• At what point is a page assigned a page frame? Not until the page is first accessed, or at some earlier point? This decision is particularly performance critical if the page needs to be fetched from disk at the time it is assigned a page frame. For this reason, the policy that controls the timing of page frame assignment is normally called the fetch policy
• Which page frame is assigned to each page? Each page may be assigned any available frame, but some assignments may result in improved performance of the processor's cache memory. The policy that selects a page frame for a page is known as the placement policy.
• If the operating system needs to move some inactive page to disk in order to free up a page frame, which page does it choose? This is known as the the replacement policy, because the page being moved to disk will presumably be replaced by a new page – that being the motivation for freeing a page frame.

Fetch Policy

The operating system has wide latitude regarding when each page is assigned a page frame. At one extreme, as soon as the operating system knows about a page's existence, it could assign a page frame. For example, when a process first starts running, the operating system could immediately assign page frames for all the pages holding the program and its statically allocated data. Creating all page mappings right away would conflict with many of the original goals for virtual memory, such as fast start up of programs that contain large but rarely used portions. Therefore, this extreme policy can be discarded.

The other extreme, the operating system could wait for a page fault caused by an access to a page before assigning that page a page frame. In between these extremes lies a range of realistic fetch policies that try to stay just a little ahead of the process's needs. This is a reasonable choice under some circumstances. A system is said to use demand paging if it creates the mapping for each page in response to a page fault when accessing that page. Conversely, it uses prepaging if it attempts to anticipate future page use.

Demand paging has the advantage that it will never waste time creating a page mapping that goes unused; it has the disadvantage that it incurs the full cost of a page fault for each page. On balance, demand paging is particularly appropriate under the following circumstances:

• If the process exhibits limited spatial locality, the operating system is unlikely to be able to predict what pages are going to be used soon. This makes paging in advance of demand less likely to pay off.
• If the cost of a page fault is particularly low, even moderately accurate predictions of future page uses may not pay off, because so little is gained each time a correct prediction allows a page fault to be avoided.

The Linux operating system uses demand paging in exactly the circumstances suggested by this analysis. The fetch policy makes a distinction between zero-filled pages and those that are read from a file, because the page fault costs are so different. Linux uses demand paging for zero-filled pages because of their comparatively low cost. In contrast, Linux ordinarily uses a variant of prepaging [explained next] for files mapped into virtual memory. This makes sense because reading from disk is slow. However, if the application programmer notifies the operating system that a particular memory-mapped file is going to be accessed in a random fashion, then Linux uses demand paging for that file's pages. The programmer can provide this information using the madvise() procedure. The most common form of prepaging is clustered paging, in which each page fault causes a cluster of neighboring pages to be fetched, including the one incurring the fault. Clustered paging is also called read around, because pages around the faulting page are read. [By contrast, read ahead reads the faulting page and later pages, but no earlier ones.]

Linux reads a cluster of sixteen pages aligned to start with a multiple of 16. Microsoft Windows uses a smaller cluster size, which depends in part on the kind of page incurring the fault: instructions or data. Because instruction accesses generally exhibit more spatial locality than data accesses, Windows uses a larger cluster size for instruction pages than for data pages.

Linux's read around is actually a slight variant on the prepaging theme. When a page fault occurs, the fault handler fetches a whole cluster of pages into RAM but only updates the faulting page table entry. The other pages are in RAM but not mapped into any virtual address space; this status is known as the page cache. Subsequent page faults can quickly find pages in the page cache. Thus, read around doesn't decrease the total number of page faults, but converts many from major page faults [reading disk] to minor page faults [simply updating the page table]. Because reading from disk takes about 10 milliseconds and because reading sixteen pages takes only slightly longer than reading one, the success rate of prepaging doesn't need to be especially high for it to pay off.

Placement Policy

Just as the operating system needs to determine when to make a page resident [on demand or in advance], it needs to decide where the page should reside by selecting one of the unused page frames. This choice influences the physical memory addresses that will be referenced and can thereby influence the miss rate of the cache memory hardware.

Although cache performance is the main issue in desktop systems, there are at least two other reasons why the placement policy may matter. In large-scale multiprocessor systems, main memory is distributed among the processing nodes. As such, any given processor will have some page frames it can more rapidly access.

To explain why the placement policy in uences cache miss rate, we need to review cache memory organization. An idealized cache would hold the N most recently accessed blocks of memory, where N is the cache's size. However, this would require each cache access to examine all N blocks, looking to see if any of them contains the location being accessed. This approach, known as full associativity, is not feasible for realistically large caches. Therefore, real caches restrict any given memory location to only a small set of positions within the cache; that way, only those positions need to be searched. This sort of cache is known as set-associative.

The lower the cache's associativity, the more likely conflict misses are to be a problem. Thus, careful page placement was more important in the days when caches were external to the main microprocessor chips, as external caches are often of low associativity. Improved semiconductor technology has now allowed large caches to be integrated into microprocessors, making higher associativity economical and rendering placement policy less important.

Suppose, though, that an operating system does wish to allocate page frames to reduce cache conflicts. How should it know which pages are important to keep from conflicting? One common approach is to assume that pages that would not conflict without virtual memory address translation should not conflict even with address translation; this is known as page coloring. The main argument in favor of page coloring is that it leaves intact any careful allocation done at the level of virtual addresses. Some compiler authors and application programmers are aware of the importance of avoiding cache conflicts, particularly in high-performance scientific applications, such as weather forecasting.

Another common approach is to assume that pages which are mapped into page frames soon after one another are likely to also be accessed in temporal proximity; therefore, they should be given nonconflicting frames. This is known as bin hopping. The main argument in favor of bin hopping is that experimental evidence suggests it performs better than page coloring does, absent cache-conscious data allocation. This may be because page coloring is less flexible than bin hopping, providing only a way of deciding on the most preferred locations in the cache for any given page, as opposed to ranking all possible locations from most preferred to least.

Replacement Policy

Conceptually, a replacement policy chooses a page to evict every time a page is fetched with all page frames in use. However, operating systems typically try do some eviction in advance of actual demand, keeping an inventory of free page frames. When the inventory drops below a low-water mark, the replacement policy starts freeing up page frames, continuing until the inventory surpasses a high-water mark. Freeing page frames in advance of demand has three advantages:

• Last-minute freeing in response to a page fault will further delay the process that incurred the page fault. In contrast, the operating system may schedule proactive work to maintain an inventory of free pages when the hardware is otherwise idle, improving response time and throughput.
• Evicting dirty pages requires writing them out to disk first. If the operating system does this proactively, it may be able to write back several pages in a single disk operation, making more efficient use of the disk hardware.
• In the time between being freed and being reused, a page frame can retain a copy of the page it most recently held. This allows the operating system to inexpensively recover from poor replacement decisions by retrieving the page with only a minor page fault instead of a major one.

In a real operating system, a page frame may go through several temporary states between when it is chosen for replacement and when it is reused. For example, Microsoft Windows may move a replaced page frame through the following four inventories of page frames, as illustrated in the Figure:

When the replacement policy first chooses a dirty page frame, the operating system moves the frame from a process's page table to the modified page list. The modified page list retains information on the previous page mapping so that a minor page fault can retrieve the page. [Microsoft calls this a soft page fault.] If a page frame remains in the modified page list long enough, a system thread known as the modified page writer will write the contents out to disk and move the frame to the standby page list. A page frame can also move directly from a process's page table to the standby page list if the replacement policy chooses to evict a clean page. The standby page list again retains the previous mapping information so that a soft page fault can inexpensively recover a prematurely evicted page. If a page frame remains on standby for long enough without being faulted back into use, the operating system moves it to the free page list. This list provides page frames for the system's zero page thread to proactively fill with zeros, so that zero-filled pages will be available to quickly respond to page faults, as discussed earlier. The operating system also prefers to use a page frame from the free list when reading a page in from disk. Once the zero page thread has filled a free page frame with zeros, it moves the page frame to the zero page list, where it will remain until mapped back into a process's page table in response to a page fault.

In order to keep the size of this inventory relatively stable over the long term, the operating system balances the rate of page replacements with the rate of page fetches. It can do this in either of two different ways, which lead to the two major categories of replacement policies, local replacement and global replacement.

Local replacement keeps the rate of page evictions and page fetches balanced individually for each process. If a process incurs many page faults, it will have to relinquish many of its own page frames, rather than pushing other processes' pages out of their frames. Microsoft Windows uses local replacement.

Global replacement keeps the rate of page evictions and page fetches balanced only on a system-wide basis. If a process incurs many page faults, other process's pages may be evicted from their frames. The replacement policy chooses which page frames to free from all the page frames, regardless which processes they are used by. all the members of the UNIX family, including Linux and Mac OS X, use global replacement.

Both local and global replacement policies may be confronted with a situation where the total size of the processes' working sets exceeds the number of page frames available. In the case of local replacement, this manifests itself when the allocation policy cannot allocate a reasonable number of page frames to each process. In the case of global replacement, an excessive demand for memory is manifested as thrashing, that is, by the system spending essentially all its time in paging and process switching, producing extremely low throughput.

The traditional solution to excess memory demand is swapping. The operating system picks some processes to evict entirely from memory, writing all their data to disk. Moreover, it removes those processes' threads from the scheduler's set of runnable threads, so that they will not compete for memory space. After running the remaining processes for a while, the operating system swaps some of them out and some of the earlier victims back in. Swapping adds to system complexity and makes scheduling much choppier; therefore, some global replacement systems such as Linux omit it and rely on users to steer clear of thrashing. Local replacement systems such as Microsoft Windows, on the other hand, have little choice but to include swapping.

Some people incorrectly call paging swapping; for example, you may hear of Linux swapping, when it really is paging. That is, Linux is moving individual pages of a process's address space to disk and back, rather than moving the entire address space.

Specific Replacement Policies

Now we have some context, so here are three specific replacement policies to ponder.

If the operating system knew in advance the full sequence of virtual memory accesses, it could select for replacement the page that has its next use furthest in the future. This turns out to be more than just intuitively appealing: one can mathematically prove that it optimizes the number of demand fetches. Therefore, this replacement policy is known as optimal replacement [OPT].

Real operating systems don't know future page accesses in advance. However, they may have some data that allows the probability of different page accesses to be estimated. Thus, a replacement policy could choose to evict the page estimated to have the longest time until it is next used. As such, it makes sense to replace the page that has gone the longest without being accessed. This replacement policy is known as Least Recently Used [LRU]. LRU replacement is more realistic than OPT, because it uses only information about the past, rather than about the future. However, LRU is not a gold standard in the same way that OPT is; while OPT is optimal among all policies, LRU may not even be optimal among policies relying only on past activity. Real processes do not access pages randomly with slowly shifting probability distributions. Nonetheless, LRU tends to perform reasonably well in many realistic settings; therefore, many other replacement policies try to approximate it.

A simple policy is known as First in, First out replacement [FIFO]. The name tells the whole story: the operating system chooses for replacement whichever page frame has been holding its current page the longest. Note the difference between FIFO and LRU; FIFO chooses the page that was fetched the longest ago, even if it continues to be in frequent use, whereas LRU chooses the page that has gone the longest without access. FIFO is not a very smart policy; in fact, early simulations showed that it performs comparably to random replacement. Beyond this mediocre performance, one sign that FIFO isn't very smart is that it suffers from Belady's anomaly: increasing the number of page frames available may increase the number of page faults, rather than decreasing it as one would expect.

Both OPT and LRU are immune from Belady's anomaly, as are all other members of the class of stack algorithms. A stack algorithm is a replacement policy with the property that if you run the same sequence of page references on two systems using that replacement policy, one with N page frames and the other with n + 1, then at each point in the reference sequence the N pages that occupy page frames on the first system will also be resident in page frames on the second system.

Remember that page frames chosen for replacement are not immediately reused, but rather enter an inventory of free page frames. The operating system can recover a page from this inventory without reading from disk, if the page is accessed again before the containing page frame is reused. This refinement turns out to dramatically improve the performance of FIFO. Thus, the pages that wind up actually replaced are those that were not accessed recently, approximating LRU. This approximation to LRU, based on FIFO, is known as Segmented FIFO [SFIFO].

Security and Virtual Memory

Virtual memory plays a central role in security because it provides the mechanism for equipping each process with its own protected memory. There is one classic virtual memory security issue that can best be discussed here, which is particularly relevant to application programmers.

Recall that the most traditional use of virtual memory is to simulate having lots of RAM by moving inactive pages to disk. This can create a security problem if a program processes condential data that should not be permanently stored. For high-security applications, you may NOT want to rely on the operating system to guard the data that is on disk. Instead, you may want to ensure the sensitive information is never written to disk. That way, even if an adversary later obtains physical possession of the disk drive and can directly read all its contents, the sensitive information will not be available.

As a familiar example, most systems do not store login passwords on disk. Instead, they store the results of feeding the passwords through a one-way function. That suces for checking entered passwords without making the passwords themselves vulnerable to exposure.

Application programmers may think their programs keep sensitive data only temporarily in volatile main memory and never store it out to disk. The programmers may even take care to overwrite the memory afterward with something safe, such as zeros. Even so, a lasting record of the condential data may be on the disk if the virtual memory system wrote out the page in question during the vulnerable period.

To protect your programs against this vulnerability, you need to forbid the operating system from writing a sensitive region of memory out to disk. In eect, you want to create an exception to the normal replacement policy, in which certain pages are never chosen for replacement.

In-class Work For This Week

Since we didn't get to the exercise last week because of spending more time with Linux, this week you have the option of doing last week's exercise OR this week's exercise, OR BOTH if you so desire. These exercises are given below.

In-class Assignment #6

For this in-class assignment, you will investigate some virtual memory accessing. Write a program that loops many times, each time using an inner loop to access every 4096th element of a large array of bytes. Time how long your program takes per array access. Do this with varying array sizes. Are there any array sizes when the average time suddenly changes? Write a report in which you explain what you did, and the hardware and software system context in which you did it, carefully enough that someone could replicate your results.

The specifications are as follows:

1. Write a program vmArrayTimer.c which takes an array size as a command line argument
2. The program should create an array that is the size of that command line argument. You will need to use the malloc() function call for this operation. Don't forget to free the memory at the end of your program with a free() function call.
3. Next, fill the array with integers which are random values between one and one hundred, inclusive
4. Make sure your program includes an output statement to inform the user that the array has been filled, then another output statement to let the user know that an access has happened, including the value retrieved from the array
5. Compile and run your program to make sure it works properly; you can start small; instead of the 4096th element, declare the array on the command line to be 100 elements, and then access element number 57 [for example] to prove correct operation
6. Modify your program [if necessary] to handle a very large array and every 4096th element as the problem statement above requires
7. Time the operation of your program; you can look up the command for accessing system time for your O/S on the Internet and use it to determine program duration. The time method does NOT have to be built into your program unless you want to do so.
8. Manually track the elapsed time duration to determine the average time; does it change in any significant way with a VERY large array of numbers?

In-class Assignment #7

The exercise this week is to create a simulation which will model the operation of page access using Virtual Memory. The idea of the exercise is to model several page frames of instructions using arrays, then model a fixed-size page array, that will contain pointers to the page frames. This will model the situation of the figure near the top of this page. You will then create a set of threads that will all access the page frames, via the page array, in random order and for a short time so that no thread will run to completion during any one turn. This will simulate loading pages from Virtual Memory into Physical Memory.

You will do the following tasks:

1. Create the file VMSimulator.c
2. Create a table that contains 4096 integer entries; this simulates a page in virtual memory for one program
3. Fill the table with random values in the range of 1 - 65536 inclusive; this simulates the program code and data of one program
4. Repeat steps 2 and 3 for five more arrays
5. Create a table of int values that contains the pointers to the six pages
6. Create a thread function that will simulate a running program by reading and displaying the values from the pages in virtual memory; note that the thread function will read several lines from its own block, then will pause and let another thread run
7. Write a main method that will spawn six threads; make each thread run for a small amount of time, during which it outputs the numbers in its own virtual memory page – the page should be loaded from the POINTERS which are in the second table of the simulation, NOT from the VM tables directly, and the threads should NOT execute all the way to the end before they stop to let another thread run unless they run out of memory space before the end of their time is up
8. When the simulation reaches the end of the code for each thread, that one should stop executing because it is finished
9. Run the simulation until all threads have completed; see if you can make the simulation run them in random order, and try to make them complete at different times

Homework Assignment #2

I know this isn't due for a while, but i wanted to give you a heads-up on the homework assignments that you will be doing this semester. They are all available from the syllabus page, but just to make sure …

Week Seven Wrap-up

That's probably enough for the this week. Be sure to check out the links to the related materials that are listed on the class links page.