该文介绍虚拟内存。

Background

程序运行时并非所有代码和数据都需要同时使用，即不需要全部加载入物理内存。

虚拟内存：separation of user logical memory from physical memory

• 逻辑内存可比物理内存大很多
• 多进程可共享

Demand Paging

需要时将页面加载入内存

Valid-Invalid Bit：valid表示页面在内存中，invalid表示不在内存中

Page Fault: 访问不在内存中的页面

11

Free-Frame List: 空闲帧列表,zero-fill-on-demand(按需清零)

Copy-on-Write

• 原理：允许父进程和子进程在初始阶段共享内存中的相同页面。只有当其中一个进程尝试修改共享页面时，系统才会为该页面创建一个副本，这种方式避免了在进程创建时对大量共享页面的不必要复制。
• 优势：提高了进程创建的效率。由于只有被修改的页面才会被复制，减少了内存复制操作和时间开销，从而加快了进程创建速度。
• 内存分配：涉及的空闲页面从按需清零的页面池中分配，以保证快速执行需求分页操作。页面池需始终有空闲帧，避免在缺页时因无空闲帧而进行额外处理。
• 系统调用应用：vfork()是fork()系统调用的变体，它利用写时复制技术，让父进程暂停执行，子进程使用父进程的写时复制地址空间。这一设计使得子进程能够高效地调用exec()，常被用于实现UNIX命令行外壳接口。

Page Replacement

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

Performance – want an algorithm with minimum # page faults

内存中的页面可能被修改，modify (dirty) bit用于标记页面是否被改动过。在页面置换时，只将其置为 1，即被修改过的页面写回磁盘；未修改的页面，由于内容与磁盘存储一致，无需写回，从而减少了不必要的磁盘 I/O 操作，降低了页面传输开销，即仅将修改的页面写回磁盘。

Page Replacement Algorithms

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

• 原理：选择最早进入内存的页面进行替换，即选择队列中最早进入的页面进行替换。

Optimal Page Replacement

• 原理：选择未来最长时间不被访问的页面进行替换，即选择队列中未来最长时间不被访问的页面进行替换。
  但无法预知未来，故很难实现

Least Recently Used (LRU) Page Replacement

• 原理：选择最近最久未使用的页面进行替换，即选择队列中最近最久未被访问的页面进行替换。

LRU Approximation Page Replacement

• 原理：近似 LRU 算法，通过使用栈或计数器等数据结构来近似实现 LRU 算法。
• Second-Chance Algorithm：将页面置于环形队列中，当页面被访问时，将其移至队尾，否则将其移出队列。

Counting Page 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