1. In the discussion of base and bounds registers in Section 7.1, it was said that “without base registers, after a process is swapped out, it would have to be swapped into the same location in which it resided previously.” Explain why this is so. Then, explain how modern virtual memory systems avoid this problem.
2. Early memory-management systems included implementation of a memory fence between user and kernel space, the use of base and bounds registers on a per-process basis, and overlaying. Describe the features that each of these systems was meant to achieve. Explain how modern VM systems provide all these features.
3. In Section 7.2 we discuss three schemes for structuring virtual memory: the use of fi xedsize pages, variable-size segments, and a hybrid approach. Explain the advantages of segmented schemes and why modern systems largely do not use them.
4. Virtual memory gives each process the illusion that it has the entire address space at its disposal. How large is the address space for a 32-bit CPU? What about a dual-core 32-bit CPU? What about a 64-bit CPU?
5. a. Suppose we have a 30-bit page number and 4-byte pages. How large is the complete page table for such a virtual memory system? b. What are the tradeoffs involved in having smaller pages versus larger pages? c. Why does Linux choose to use large pages for its kernel address space, and smaller pages for the user address space?
6. Suppose we have a uniprocessor machine. Why is it important to fl ush the TLB after a context switch between processes?
7. Consider the following extreme example. We have a computer with four page frames of real memory. We wish to execute a single process which in total requires fi ve pages. The program proceeds by sequentially referencing its fi ve pages in order repeatedly. That is, fi rst page 1 is referenced, then 2, then 3, etc. Is LRU the best replacement policy for this system? Explain. If not, what is the best replacement policy? For the purpose of this example, assume that the operating system itself occupies no pages of memory.
1. When a Unix process invokes fork, why should shared mappings not be marked copy-on-write?
2. What are the benefits of inverted page tables as opposed to normal page tables? Why have they fallen out of favor?
1. Suppose the x64 architecture supported 4KB and 4MB pages. Could the two different page sizes coexist in the same address space as the 4KB and 2MB page sizes do in the actual architecture? Explain.
2. As mentioned in Section 7.2.5, the IA-64 implementations of both Linux and Windows use linear page tables. Both operating systems use a three-level forward-mapping scheme to map the pages of the page table (this is used strictly by the operating system — the IA-64 TLB relies on its own entries to fi nd page-table entries; if it can’t map a page-table entry, it traps to the operating system). Suppose a thread is accessing a region sequentially, one page at a time, and TLB entries are inserted only when required. Assume that initially no relevant translations are in the TLB (though assume that the translation for the page containing the code being executed is in the TLB) and that the page size is 8K. Linear page-table entries are eight bytes long. Assume all desired translations are in valid entries of the linear page table. a. How often will there be a TLB miss, requiring the TLB to load an entry from the linear page table? Stated another way, will there be a miss on each access to a new page, on every fourth new page, on every 64th new page, etc.? b. How often will there be a trap to the operating system? c. How many memory accesses, other than those needed to fetch instructions, are required to get translation information when a gigabyte if memory is accessed sequentially?
12. Figure 7.5 shows a forward-mapped page-translation approach known as segmented paging. This is what’s commonly used on x86 architectures, where 12 bits are used for the offset and 10 bits each for the L1 page number and the L2 page number. There’s a special hardware register, known as CR3, that is set by the operating system to point to the L1 page table, known as the page-directory table. The hardware, when doing an address translation, looks in this register to fi nd the address of the page-directory table. Any attempt to store to or load from this register directly while in user mode causes a trap to the operating system. Suppose we have a virtual-machine monitor for the x86, supporting virtual machines that are intended to behave just like real x86 machines. We’d like to run in a virtual machine an operating system Z that provides a separate virtual address space for each of its processes. Our x86 system is rather old and does not support extended page translation. Thus the VMM must support shadow page tables (Section 7.2.6). a. Suppose Z, the operating system on the virtual machine, running in virtual privileged mode, sets CR3 to point to a new page-directory table. How will the VMM be notifi ed that this action has taken place? b. What should be the VMM’s response to Z’s setting of CR3? c. What other actions might Z do that affect the translation of virtual virtual addresses to virtual real addresses? d. How might things be set up to ensure that the VMM fi nds out about these actions?
1. Consider an architecture that does address translation using a software-managed TLB, with no page tables. Explain how a VMM might virtualize address translation.
2. Suppose a large amount of thrashing is going on in a system. What would be the fi rst thing you would do to alleviate the situation?
* 15. In the Fortran programming language, arrays are stored in column-major order, meaning that adjacent entries in each column are stored in adjacent memory locations. For example (using C notation for matrices), Matrix[i][j] is stored just before Matrix[i This caused no problems until such programs were run on machines supporting virtual memory, where performance (particularly for large values of M and N) turned out to be much worse than on machines that didn’t support virtual memory. Explain why performance was worse. (Hint: consider the page-replacement policy.)
16. Explain what the problem is with the one-handed clock algorithm, and explain how the two-handed clock algorithm solves this problem. What factor in this algorithm would let it be adjusted for use in systems of arbitrary-sized memory?
17. Section 220.127.116.11 discusses virtual-memory management in Windows. It mentions a potential deadlock situation in which one of the two modifi ed-page-writer threads invokes pageable fi le-system code. a. Describe a scenario in which such a deadlock might happen. b. Explain how dividing the duties of the modified-page-writer threads — so that one handles page frames containing fi le data and the other handles page frames containing private data — avoids deadlock.
18. Many operating systems allow programs to do fi le I/O in two different ways: programs may use explicit system calls (read and write in Unix, ReadFile and WriteFile in Windows) and they may map fi les into the address space (mmap in Unix, MapViewOfFile in Windows). In the former approach incoming data is read from disk and stored in a buffer in the operating system, from where it is copied to the program. Outgoing data is copied from the program to the operating system’s buffer, then, perhaps sometime later, written to the disk from the buffer. In the latter approach, the virtual-memory system fetches data from the fi le and writes modifi ed data back to the fi le, while the program merely accesses and modifi es what’s in its address space. a. Describe the problems that might occur if one program accesses a fi le via explicit system calls, while another program accesses the same fi le by mapping it into its address space. b. Explain how to fi x things so that the problems mentioned in part a don’t occur
* 19. Many Unix operating systems provide the madvise system call with which a thread can tell the operating system how it will be referencing memory. For example, a thread can specify that its references to a particular region of memory will be random, meaning that there’s no predicting whether any particular page will be referenced or not at any given moment. It can also specify that its references to a particular region of memory will be sequential, meaning that pages are going to be accessed in sequential order. Explain how the operating system might use this information. In particular, how might it affect page-ins and page-outs?
20. Unix process X has private-mapped a fi le into its address space. Our system has one-byte pages; the fi le consists of four pages, which are mapped into locations 100 through 103. The initial values of these pages are all zeros. X stores a 1 into location 100. X forks, creating process Y. X stores a 1 into location 101. Y stores a 2 into location 102. Y forks, creating process Z. X stores 111 into location 100. Y stores 222 into location 103. Z adds the contents of locations 100, 101, and 102, and stores the result into location 103. What value did Z store into 103?
21. Section 7.3.3 discusses the use of shadow objects. a. Give an example showing how the chain of shadow objects may grow arbitrarily long. b. Describe the circumstances under which such a chain may be made shorter. *