What limits the size of virtual storage?
The addressing scheme of the computer system and the amount of secondary memory available — not the actual number of main storage locations.
Virtual address space vs real address.
Virtual address space: the virtual storage assigned to a process. Real address: the address of a storage location in main memory.
The two key points that make virtual memory possible.
1. Memory references are logical addresses dynamically translated into physical addresses at run time. 2. A process may be broken into pieces that need not be contiguous in main memory.
What is the resident set?
The portion of a process that is in main memory.
What happens when a needed address is not in main memory?
An interrupt is generated and the process is blocked; the OS issues a disk read, dispatches another process meanwhile, and when the I/O completes puts the process back in the Ready state.
Two implications of executing processes partly in memory.
More processes may be maintained in main memory; a process may be larger than all of main memory.
Define thrashing.
A state in which the system spends most of its time swapping pieces rather than executing instructions.
State the principle of locality and why it matters.
Program and data references within a process tend to cluster, so only a few pieces are needed over a short period; intelligent guesses are possible, so virtual memory may work efficiently.
Which two extra bits does a page table entry need?
One for whether the page is in main memory or not; one for whether its contents have been altered since it was last loaded.
Where are page tables stored?
Also in virtual memory; when a process is running, part of its page table is in main memory.
What is the drawback of ordinary page tables that inverted page tables address?
Their size is proportional to that of the virtual address space.
Fields of an inverted page table entry.
Page number; process identifier (owner); control bits (valid, referenced, locking); chain pointer (index of the next entry in the chain).
What does the TLB contain?
The page table entries that have been most recently used (a high-speed cache for page table entries).
TLB hit vs TLB miss.
Hit: the frame number is retrieved and the real address is formed. Miss: the page number is used to index the process page table.
Why must each TLB entry include the page number?
Because the TLB contains only some of the page table entries, so it cannot be indexed by page number; the processor queries many entries simultaneously (associative mapping).
Effects of a smaller page size.
Less internal fragmentation, but more pages per process, larger page tables, and a large portion of page tables in virtual memory.
Why is a large page size better for secondary memory?
Secondary memory is designed to efficiently transfer large blocks of data.
Combined paging and segmentation: which is visible to the programmer?
Segmentation is visible; paging is transparent; each segment is broken into fixed-size pages.
Demand paging vs prepaging.
Demand paging brings a page in only when a reference is made to it (many faults at start). Prepaging brings in more pages than needed (efficient for pages contiguous on disk).
When is the placement policy important?
In a segmentation system; with paging (or combined paging and segmentation) hardware performs address translation.
What may not be replaced, and what kinds of frames are locked?
A locked frame may not be replaced: the kernel of the OS, key control structures, I/O buffers; a lock bit is associated with each frame.
Optimal replacement: which page, and what is its problem?
The page for which the time to the next reference is the longest; it is impossible to have perfect knowledge of future events.
Why is LRU difficult to implement?
One approach is to tag each page with the time of last reference, which requires a great deal of overhead.
How does FIFO treat the page frames of a process?
As a circular buffer: pages are removed in round-robin style, replacing the page that has been in memory the longest.
Page stream 2 3 2 1 5 2 4 5 3 2 5 2 with 3 frames: faults after the frames fill for optimal, LRU and FIFO?
Optimal 3, LRU 4, FIFO 6.