This post introduces virtual memory.

Background

When a program runs, not all of its code and data need to be used at the same time, i.e. not everything needs to be loaded into physical memory.

Virtual memory: separation of user logical memory from physical memory

• Logical memory can be much larger than physical memory
• Multiple processes can share it

Demand Paging

Pages are loaded into memory when they are needed

Valid-Invalid Bit: valid means the page is in memory, invalid means it is not in memory

When a program references a page that is not in memory, a page fault occurs, and the operating system steps in to handle it: first, the operating system checks the page table to determine whether the reference is an invalid reference; if so, the program is terminated. If the page is simply not in memory, the following steps are performed. Next, the operating system looks for a free frame to hold the page that needs to be brought in. Then, a disk operation is scheduled to swap the target page from disk into the free frame that was found. After that, the page table and frame table are updated, and the valid-invalid bit of the page that was brought in is set to valid (v), indicating that the page is now in memory. Finally, the instruction that caused the page fault is restarted so the program can continue executing.

Free-Frame List: the list of free frames, zero-fill-on-demand

Copy-on-Write

• Principle: allows the parent and child processes to initially share the same pages in memory. Only when one of the processes attempts to modify a shared page does the system create a copy of that page. This avoids unnecessary copying of large numbers of shared pages at process creation time.
• Advantages: improves the efficiency of process creation. Since only the modified pages are copied, memory copy operations and time overhead are reduced, thereby speeding up process creation.
• Memory allocation: the free pages involved are allocated from a pool of zero-filled-on-demand pages, to guarantee that demand paging can be carried out quickly. The page pool must always have free frames, to avoid extra handling caused by a lack of free frames when a page fault occurs.
• System call application: vfork() is a variant of the fork() system call. It uses copy-on-write, suspending the parent process while the child uses the parent’s copy-on-write address space. This design allows the child to call exec() efficiently, and is often used to implement UNIX command-line shell interfaces.

Page Replacement

find some page in memory, but not in use, page it out

Performance – want an algorithm with minimum # page faults

Pages in memory may be modified; the modify (dirty) bit is used to mark whether a page has been changed. During page replacement, only pages whose bit is set to 1, i.e. modified pages, are written back to disk; unmodified pages, whose contents are consistent with what is stored on disk, do not need to be written back, thus reducing unnecessary disk I/O operations and lowering the page transfer overhead, i.e. only modified pages are written back to disk.

Page Replacement Algorithms

First-In-First-Out (FIFO) Page Replacement

• Principle: select the page that entered memory earliest for replacement, i.e. select the page that entered the queue earliest for replacement.

Optimal Page Replacement

• Principle: select the page that will not be accessed for the longest time in the future for replacement, i.e. select the page in the queue that will not be accessed for the longest time in the future for replacement.
  But the future cannot be predicted, so it is hard to implement

Least Recently Used (LRU) Page Replacement

• Principle: select the page that has not been used for the longest time for replacement, i.e. select the page in the queue that has not been accessed for the longest time for replacement.

LRU Approximation Page Replacement

• Principle: approximates the LRU algorithm by using data structures such as stacks or counters to approximately implement LRU.
• Second-Chance Algorithm: pages are placed in a circular queue; when a page is accessed, it is moved to the tail of the queue, otherwise it is removed from the queue.

Counting Page Replacement

• Principle: a counter records the number of accesses to each page, and the page with the fewest accesses is selected for replacement.

Global vs. Local Replacement

• Global replacement: process selects a replacement frame from the set of all frames; one process can take a frame from another
• Local replacement: each process selects from only its own set of allocated frames

Allocation of Frames

Each process needs minimum number of frames

• Fixed Allocation
  • Equal allocation
  • Proportional allocation: Allocate according to the size of process
• Priority allocation

Summary

• Virtual memory abstracts physical memory into an extremely large uniform array of storage
• Benefits of virtual memory:
  • (1) a program can be larger than physical
    memory,
  • (2) a program does not need to be entirely in memory,
  • (3)processes can share memory
  • (4) processes can be created more efficiently.
• Demand paging loads pages only when they are demanded during program execution
• A page fault occurs when a page currently not in memory is accessed
• Copy-on-write allows the child process to share its parent’s address, and only make a copy when one of them modifies a page
• Page replacement algorithms: FIFO, optimal, LRU, LRU-approximations.
• Discussed frame allocation among processes

Translated from the Chinese original.