Memory Management

main memory

What is relocatable code?
What is late binding? What feature of operating systems makes late binding necessary? Describe a programming language feature that makes late binding necessary.
A variable-sized partition scheme allocates to each process a contiguous chunk of memory large enough to hold that process. The operating system must choose the partition from a list of available holes. What heuristics have been used for this problem? What are their relative merits?
What is the main problem with contiguous-allocation?
What is the difference between external and internal fragmentation?
What is paging? Explain in terms of pages, frames, and page tables.
How is a logical address converted into a physical address?
The DEC PDP-11 used a set of dedicated registers to implement page tables. It had a 16-bit address space and 8 KB page size. How many registers are needed in this case? Why is this approach to implementing page tables not feasible for 32-bit machines?
Page tables can be stored in main memory, with a page-table base register and page-table length register used to access the table for the current process. What problem does this introduce? How does a TLB solve this problem?
Consider a system with 32-bit logical address space and 4KB page size. How big is the page table? We would not want to store it contiguously in memory — name three techniques used to deal with this problem.
How does hierarchical paging work? Give a concrete example of a 2-level scheme for a 32-bit machine with 4 KB page size. Draw a picture to illustrate the idea.
Why is hierarchical paging not appropriate for 64-bit machines?
How do hashed page tables work? Draw a picture to illustrate the idea.
What is an inverted page table? What is the main advantage and disadvantage of this approach to structuring page tables? How can hashing help?
What is the difference between paging and segmentation?
For a given segment table, convert a given logical address into a physical address.

virtual memory

Describe the steps involved in handling a page fault.
What is copy-on-write?
What is locality of reference? Discuss its importance to demand paging.
Explain how a dirty bit can be used to reduce the effective access time.
Given a reference string and the number of frames allocated to a process, compute the number of page faults using FIFO, OPT, and LRU.
What is Belady's Anomaly? Write out a specific example to demonstrate Belady's Anomaly in the case of FIFO.
Explain why LRU never exhibits Belady's Anomaly.
Describe the counter implementation of LRU. Why is hardware support needed?
Describe the stack implementation of LRU.
How can a reference bit be used to roughly approximate LRU?
Describe the second-chance algorithm and the enhanced second-chance algorithm.
What problem arises from Least Frequently Used page replacement? Describe an idea for dealing with this problem.
Give an example in which LRU generates fewer page faults than Least Frequently Used for the same reference string. Give another example to show the opposite result.
Give an example to show that LRU generates fewer page faults than Most Frequently Used for the same reference string. Give another example to show the opposite result.
Give a justification for Most Frequently Used page replacement.
Discuss local replacement and global replacement. What are their relative merits?
What is thrashing? Describe a strategy for dealing with thrashing based on the locality model of process execution.
What happens if the working set parameter Δ is chosen too small? Too large?
Some systems approximate the working set by keeping track of the pages referenced within a certain number of time units. What is the potential problem with this scheme?
Why do some operating systems impose a lower limit on the page fault rate of processes?
What are memory-mapped files? What are the reasons for memory mapping?
Give two reasons why kernel memory is often allocated from a free-memory pool different from the pool used to satisfy user-mode processes?
Compare the buddy system allocator with slab allocation.
Demand paging is supposed to be transparent to programs, but a smart compiler can exploit knowledge of the pager. Explain.
You can implement a solution to a programming problem using a host of different languages. How might the choice of langauge affect the page fault rate?