## Background ### Multiprogramming Problem: if a program needs to be run, but there is no enough free memory? One solution：**swap out (换出) a process and swap in (换入)** the target process ### Swapper - Function: A completeprocess can be swappedtemporarily out of memory to a backing store, and then brought back into memory for continued execution - **Swapper (一定要跟后面的 Pager 区分）： A swappermanipulates entireprocess swapping** | Advantanges | Disadvantages | | ------------------------- | ------------------------------------------------------------ | | Increase multiprogramming | Context switch time can then be very high; Total context switch timeincludes swapping time for the whole process | #### Improvement: Swapping with Paging - When memory is low, unused pages are swapped to disk (instead of whole processes) - Pager is then designed to solve following problems: - How to determine which pages are unused? - What happens when a process suddenly tries to access a page that was swapped out? ### Introduction to virtual memory - Program can be partially loaded into memory - Program length is no longer constrained by limits of physical memory - Each program takes less memory → more programs run at the same time - Less I/O needed to load programs into memory → each user program runs faster - Virtual memory –separation of user logical memory from physical memory - Logical address space can therefore be much larger than physical address space - Only needed pages are loaded into memory ## Demand Paging ### Definition Paging can bring pages into memory which are needed. - Advantages - Less I/O needed, no unnecessary I/O - Less memory needed - Faster response - More users/processes - Page is needed (called a **reference** to the page) - Invalid reference might be caused by - Wrong adress $\to$ process abort - Not-in-memory $\to$ bring to memory - Apagercan swap in and out one page at a time (not a whole process like swapper does) - **MMU determines the set of pages that are needed in the memory** Valid-Invalid bit is to check if a reference is valid or not, associate each page table entry with a valid-invalid bit. - **v**: the page is in memory - **i**: the page is: - either not-in-memory - or wrong logical address - Initially valid-invalid bit is set to **i** on all entries ### Page Fault Definition: - Caused when a process makes **a reference to a page which is not in RAM** - **MMU** detects that the page is marked as invalidin the process’s page table Two posibilities: - the process is trying to access a page that does not exist at all - Solution: Process aborts - The page is not in memory but is somewhere on the hard disk - Solution: Load the page from hard disk to RAM （注意这里后面可能要引入 Page Replacement 算法） #### Steps in Handling a Page Fault  1.CPU makes a reference to a page which is marked*i*in the page table 2.MMU traps to kernel - if the reference page does not exist at all, stop the process; - otherwise, go to 3 3.Find the page in the hard backing store 4.Find a free frame in the memory and load the page into that frame 5.Reset the page table such that the valid bit is *v* 6.Restart the process by re-executing the instruction which caused the page fault. #### An extreme analysis of demand paging  #### Improvement: Locality Reference - Content: The tendency of processes to reference memory in patterns rather than randomly, resulting in reasonable performance from demand paging. - Working-set model: The set of pages in the most recent page references - Locality model: A model for page replacement based on the working-set strategy - At any point in time, a process usually uses only a small part of all its pages. Here is an example of keeping track of the working set: 由于精确追踪的困难，操作系统通常采用**近似**方法来跟踪工作集。一个常见的近似方法是结合使用**固定间隔的定时器中断（fixed-interval timer interrupt）和 引用位（reference bit）**。 以下是这种近似方法的工作原理： 1. **设置定时器和引用位：** - 选择一个工作集窗口 Δ 的值（例如，10,000 次引用）。 - 配置硬件或操作系统，使其能够为每个页面维护一个**引用位**。当硬件（MMU）访问一个页面时，它会自动设置该页面的引用位为 1。 - 设置一个定时器，使其以固定的间隔（例如，每 5,000 次引用）触发中断。这个间隔通常小于 Δ。 - 为每个页面在内存中额外维护一些**历史位（history bits）**，用于记录引用位的历史状态（例如，2 位历史位，或者一个 8 位字节）。最初，这些位通常被清零。 2. **定时器中断时的处理：** - 当定时器中断发生时，操作系统会遍历每个进程的页面。 - 对于每个页面，操作系统将该页面的**引用位**的值转移到历史位中，例如，将其移入历史位的最高位。如果使用多位历史位，则将现有的历史位向右移动一位。 - 操作系统随后将该页面的硬件**引用位重置为 0**。 3. **确定近似工作集：** - 当操作系统需要知道一个页面是否是工作集的一部分（例如，在发生页错误时或需要进行页替换时），它会检查该页面的当前**引用位和历史位**。 - **如果这些位中的任何一个为 1**，则表明该页面在最近的一段时间内（由定时器间隔和历史位的数量决定）被引用过。因此，这个页面被认为是近似工作集的一部分。 **准确性与开销的权衡** 这种近似方法并非完全准确。操作系统不知道在最近的定时器间隔内，引用位是在何时被设置的。它只知道该页面在某个时间点（由历史位覆盖的时间段）内被引用过。 [](https://imgse.com/i/pVSfnmR) ### Demand Paging Optimizations - Set a swap space on hard disk (not supported in mobile systems) - I/O faster than file system I/O - Less management is needed than file system - Copy entire process image to swap space at process load time, then page in and out of swap space (e.g., in older BSD Unix) - Discard the pages if they are not modified in the memory - When a page is needed to page out to free a frame, if its content is not changed, no need to transfer out ### Copy-on-Write 感觉是一个很孤立的知识点 **Definition: COW allows both parent and child processes to initially share the same pages in memory** When a child process is initially created: - only copy the page table of its parent - share parents' pages - the shared pages are write-protected (using protection bits of page tables) - If either process modifies a shared page, then copy that page. [](https://imgse.com/i/pVSfQk6) ## Page Replacement ### Background 当出现一个 Page Fault 的时候，新的 page 应该要被加载进来。但是如果此时已经没有 frame 可以用了，就需要 swap 一些 pages 出 memory #### Question 1: from which process a page is replaced - Global replacement - Process selects a replacement frame from the set of all frames - One process can take a frame from another process. - The # of frames allocated to each process will change. - Local replacement - Each process selects from only its own set of allocated frames. - The # of frames allocated to each process does not change Comparison: - Global replacement - Process execution time can vary greatly - But greater throughput (吞吐量), so it is more commonly used - Local replacement - More consistent per-process performance - But possibly under-utilized memory #### Question 2: Which pages to replace (be removed from RAM)? - Two good candidates: - Pages which are not used by a process right now - Pages that are not modified (called dirty) recently - An **algorithm** is needed to find the right frame to free - **Victim page**: the page that will be replaced ### Page and Frame Replacement algorithms - Frame-allocation algorithms - Determine how many frames to give each processes - Page-replacement algorithms - Which frame to be replaced - Want lowest page-fault rate on both first access and re-access - Algorithm evaluation - Run it on a particular string of memory references (reference string) and compute the number of page faultson that string - String is just page numbers, not full addresses - Results depend on number of frames available #### FIFO - Rule: Replace the oldest one - Implementation: - 维护一个循环队列 (circular queue) - 队头 (head): oldest one - 队尾 (tail): Recent arrival - 当出现一个 Page Fault 的时候：`++ head, q[++ tail] = new page` #### Optimal - Rule: Replace the page that will not be used for longest period of - This method can only be used to measure how other algorithms are close to the optimal - 实际上不可以被实现，因为永远无法预测未来哪些 Frame 最久不会出现 #### LRU (Least Recently Used) Algorithm - Rule: Replace page that has not been used in the most amount of time - Better than FIFO(15) but worse than OPT(9) - LRU is a good algorithm and frequently used - LRU and OPT don’t have Belady’sAnomaly ##### Implementation 1: Counter 一句话：对于队列中的 Frame 维护一个 Page Counter，每次入队的时候赋值为 global counter （相当于一个时间戳），每次发生 Page Fault 的时候，遍历队列找到最小的 Page Counter，把那个 Page 移除。 ##### Implementation 2: Stack 一句话：其实根本不是 Stack。分两种情况讨论： 1. 如果要加入的 page 已经在 stack 中，则找到那个 page，从提到栈顶（代表最近访问的 page） 2. 如果发生了 page fault，那么栈底（一定是最久没有被用的 page）被删除，把新的 page 加入栈顶 ##### Approximation algorithms 见附文 ### Page Buffering More strategies (algorithms) in improving the efficiency of page replacement [](https://imgse.com/i/pVSOG3n) ## Allocation of Frames - For the performance reason, each process needs minimum number of frames - This number is defined by the computer architecture - Maximum frame number is defined by the amount of total frames in the system. ### Allocation schemes #### Fixed allocation - Equal allocation - Each process is allocated same number of frames - Disadvantage: Space waste for small process - Propositional allocation - Allocate frames according to the size of a process - Disadvantage: Process size might be changed during the execetion #### Priority allocation - The ratio of frames depends on the combination of size and priority of a process - Replace the pages of process with lower priority **Page Replacement 触发：before the number of frames falls below a certain threshold** ## Thrashing ### Definition - Background: If a process does not have enough frames in memory, the page-fault rate will be very high - Replace page frequently - The replaced page might be used again - That will result in - Low CPU ultilization - OS keeps adding new process, trying to increase CPU utilization - 陷入恶性循环 - Definition: A process is busy swapping pages in and out, instead of doing useful work 导致 Thrashing 的原因：  **Thrashing 的原因和恶性循环**： - Thrashing 通常伴随着严重的性能下降。 - 一个主要的表现是 CPU 利用率大幅下降。 - 在早期的分页系统中，操作系统可能会监控低 CPU 利用率，并错误地认为系统有空闲资源，于是增加多道程序设计度（degree of multiprogramming），引入更多进程来运行。 - 新引入的进程也需要帧，它们会进一步从已有的进程那里“窃取”帧。 - 这导致更多进程的帧数量不足，缺页率进一步升高。 - 所有这些频繁缺页的进程都会排队等待分页设备（用于页面调入调出），导致分页设备的平均服务时间增加。 - 由于进程都在等待分页设备，就绪队列变空，CPU 利用率进一步下降。 - 操作系统看到持续下降的 CPU 利用率，可能会继续增加多道程序设计度，从而形成一个恶性循环，使 Thrashing 加剧，系统吞吐量急剧下降。 - 图 10.20 展示了这种现象，随着多道程序设计度增加，CPU 利用率先上升，达到峰值后，如果继续增加多道程序设计度，Thrashing 发生，CPU 利用率急剧下降。 ### Solutions - Decrease the degree of multiprogramming - Establish “acceptable” page-fault frequency (PFF) rate and use local replacement policy - Install enough physical memory (hardware) - Install faster hard disk ### Page-Fault Frequency  ## Allocating Kernel Memory 好的，根据您提供的资料和我们的对话历史，我们可以来讲解一下“Allocating Kernel Memory”（分配内核内存）这个概念。 **什么是分配内核内存？** 分配内核内存是指操作系统内核为自身运行和管理系统资源而进行的内存分配过程。这与为用户应用程序分配内存是不同的。 **为什么内核内存分配与用户内存分配不同？** 有几个主要原因导致内核内存的分配策略需要特殊考虑： 1. **数据结构大小多样且通常较小**：内核需要内存来存放各种不同大小的数据结构，例如进程控制块 (PCB)、文件描述符结构体 等。这些结构体的大小通常小于一个页帧的大小。因此，内核必须谨慎使用内存，并尽量减少因**内部碎片**（即分配的内存块大于实际需求而造成的浪费）引起的浪费。需要为每种结构体管理多个实例。 2. **内核代码/数据通常不参与分页**：许多操作系统不将内核代码或数据放入分页系统。这意味着分配给内核的物理内存通常是常驻内存的，不会被交换到二级存储。这种设计会影响内核的总体设计。优点包括避免内核缺页带来的性能问题和复杂性；缺点可能包括消耗更多物理内存，以及在内存紧张时无法将内核部分内容换出。 3. **某些硬件需要连续的物理内存**：某些硬件设备（如直接与物理内存交互而无需虚拟内存接口的设备）可能需要驻留在物理上连续的页帧中的内存。 4. **性能要求高**：内核操作对性能非常敏感，内存分配和释放需要快速高效。 **内核内存分配方法** 由于上述特殊需求，内核通常使用专门的内存分配机制。资料中提到了两种主要的内核内存分配策略： 1. **伙伴系统 (Buddy System)** - **工作原理**：伙伴系统从一个固定大小的、由物理上连续的页组成的内存段中分配内存。它使用一种“幂等分配器”（power-of-2 allocator），以 2 的幂次方（如 4KB, 8KB, 16KB 等）为单位满足请求。如果请求的大小不是 2 的幂，系统会将其向上取整到下一个最大的 2 的幂。例如，请求 21KB 的内存会被分配一个 32KB 的段。初始时，一个大段会被递归地分成两个等大的“伙伴”子段，直到找到一个大小合适（向上取整后）的子段来满足请求。 - **优点**：相邻的空闲伙伴可以快速合并（称为 **coalescing**）成更大的段，这有助于减少外部碎片。 - **缺点**：向上取整到下一个 2 的幂可能会导致分配的段内部出现**内部碎片**，因为分配的块可能会显著大于实际请求的大小。例如，一个 33KB 的请求只能用 64KB 的段来满足。资料提到不能保证小于 50% 的已分配单元不会因内部碎片而浪费。 - **Linux 中的应用**：Linux 使用伙伴系统来管理物理页帧的分配，特别是按区域（zone）划分的物理内存。 2. **Slab 分配器 (Slab Allocator)** - **工作原理**：Slab 分配器使用**缓存 (cache)** 来存储唯一的内核数据结构。每种内核数据结构（例如，进程描述符、文件对象、信号量等）都有一个对应的缓存。一个缓存由一个或多个 **Slab** 组成。一个 Slab 则由一个或多个物理上连续的页组成。每个 Slab 被划分为多个**对象 (object)**，这些对象是该数据结构的实例。每个对象有两种状态：空闲 (free) 和已用 (used)。当内核需要某个数据结构的实例时，分配器会从该数据结构对应的缓存中分配一个空闲对象来满足请求。分配的对象会被标记为已用。当内核使用完一个对象并释放它时，它会被标记为空闲并返回到其缓存中，从而可用于后续请求。 - 优点 ： - **无碎片**：由于每个缓存是为特定大小的内核数据结构设计的，分配器会返回表示该对象所需的**精确数量的内存**。因此，不会因碎片而浪费内存。 - **分配速度快**：对象在创建缓存时就已预先分配好。当内核需要时，可以直接从缓存中获取一个空闲对象，这比动态分配内存要快得多。当对象被释放时，它被返回到缓存，立即可用。这对于频繁分配和释放对象的场景非常有效。 - **历史与 Linux 中的应用**：Slab 分配器最初出现在 Solaris 2.4 内核中。Linux 从版本 2.2 开始采用了 Slab 分配器，称为 SLAB。后续版本引入了 SLUB（自 2.6.24 起成为默认）和 SLOB（适用于内存有限的嵌入式系统）等改进型分配器。 - **示例**：在 Linux 中，进程描述符 `struct task_struct` 需要大约 1.7KB 内存。当 Linux 内核创建一个新任务时，它会从 `struct task_struct` 对应的缓存中请求所需的内存，缓存会分配一个已在 Slab 中分配且标记为空闲的对象来满足请求。 除了这两种主要方法，资料中关于 Linux 内核内存管理的部分还提到： - **`kmalloc()`**：用于处理任意大小的请求（大小不预先知道，可能只有几个字节）。它会按需分配完整的物理页，然后将它们分成更小的块。分配的内存必须通过 `kfree()` 显式释放。 - **`vmalloc()`**：用于将物理上不连续的物理页分配到一个虚拟上连续的内核内存区域。 - **`vremap()`**：用于将一系列虚拟地址映射到设备驱动程序用于内存映射 I/O 的内存区域。 **内核虚拟内存** 值得注意的是，内核的虚拟内存也需要管理。Linux 为每个进程保留了一个固定的、依赖于体系结构的虚拟地址空间区域用于自身内部使用。这些区域中的页表项被标记为受保护，因此当处理器运行在用户模式时，这些页面不可见或不可修改。这块内核虚拟内存包含一个静态区域，其中包含对系统中每个可用物理内存页的引用，使得在内核代码运行时可以进行简单的物理地址到虚拟地址的转换。内核的核心以及通过普通页分配器分配的所有页面都驻留在这个区域。这种设计（将内核代码映射到每个进程的地址空间中）有助于实现用户模式和内核模式之间更快的切换，因为不需要保存和恢复内存管理寄存器，并且缓存也不会失效。 总之，分配内核内存是一个专门化的过程，旨在高效、安全地为操作系统内核本身管理内存资源，以满足其特殊的需求，如处理各种大小的数据结构、支持不参与分页的常驻内存以及满足对物理连续性的要求。主要方法包括伙伴系统和 Slab 分配器，它们各自针对不同的分配场景提供了优化。 ## Other considerations 好的，您提供的这段文字出自关于**虚拟内存 (Virtual Memory)** 的章节，具体是探讨在实现虚拟内存和需求分页 (Demand Paging) 时的一些“其他考虑因素”。这些因素都是为了**减少缺页中断 (Page Faults)** 和**提高系统性能**。 这段内容主要说明了可以通过以下几个方面来优化分页系统的性能： 1. **预分页 (Prepaging)**: - 这是一种尝试减少进程启动时大量缺页中断的策略。 - 其思想是，在进程真正需要这些页面之前，就将它可能需要的部分或全部页面一次性加载到内存中。例如，在使用工作集模型 (working-set model) 的系统中，当一个进程被唤醒时，系统可能会尝试将其整个工作集（即最近经常使用的页面集合）预先加载到内存。 - **需要权衡 (Need to balance)**：预分页的成本是加载了可能不会立即使用（或根本不使用）的页面，这会浪费 I/O 和内存资源。其效益在于避免了后续对这些页面的单独缺页中断服务时间。是否使用预分页，以及预分页多少，取决于预分页页面中实际被使用的比例。 - 来源还提到了 Linux 的 `readahead()` 系统调用，用于预取文件内容到内存。 2. **页大小选择 (Page size selection)**: - 系统设计者在设计新机器时需要决定最佳的页大小。对于现有机器，页大小通常是固定的。 - 页大小的选择涉及多种权衡： - **页表大小 (Page table size)**：对于给定的虚拟内存空间，减小页大小会增加页数，从而增加页表的大小。较大的页大小有利于减小页表大小。 - **内存碎片 (Fragmentation)**：使用较小的页大小可以更好地利用内存，因为它能减少内部碎片（即分配的最后一个页帧未被完全使用造成的浪费）。平均而言，内部碎片约为半页大小。 - **I/O 时间和局部性 (I/O time and locality)**：较大的页大小意味着每次缺页中断时需要传输更多数据，但这通常减少了总体的缺页中断次数，因为局部性原理使得相邻数据也可能被需要。较小的页大小更准确地匹配程序局部性，但可能导致更多的缺页中断和 I/O 操作。 - 历史趋势是页大小逐渐变大。现代系统通常使用 4KB 或 8KB 的页，一些系统支持更大的页（如 x86-64 上的 2MB 或 1GB “大页/巨页”）。 - **需要权衡 (Need to balance)**：需要在页表大小、内部碎片、I/O 时间和局部性等因素之间找到平衡。 3. **TLB 覆盖范围 (TLB reach)**: - **TLB 覆盖范围**是指 TLB (Translation Look-aside Buffer) 所能直接访问的内存量，计算方式是 TLB 条目数乘以页大小。 - TLB 是页表的硬件缓存，用于加速地址翻译。TLB 命中率高意味着地址翻译快，性能好。 - 理想情况下，一个进程的工作集应该存储在 TLB 中。 - 增加 TLB 覆盖范围可以提高 TLB 命中率，从而减少通过页表查找物理地址的需要（这通常需要额外的内存访问）。 - 可以通过增加 TLB 的条目数（硬件成本高且耗电）或增加页大小来增加 TLB 覆盖范围。有些系统支持多种页大小来实现这一点。 - **需要权衡 (Need to balance)**：增加 TLB 条目数成本高，增加页大小又面临碎片等问题。因此也需要在 TLB 大小、页大小和性能/成本之间进行权衡。 4. **程序结构 (Program structure)**: - “程序员能做什么？” 这里探讨的是程序编写方式对分页性能的影响。 - 尽管需求分页对用户程序是透明的，但程序的结构（如何访问数据、数据结构的组织方式）会影响**局部性 (locality)**，进而影响缺页中断率和工作集的大小。 - 通过仔细选择数据结构和编程结构，程序员可以提高程序的局部性，从而降低缺页中断率。 - 来源提供了一个例子：初始化一个二维数组时，按行访问比按列访问可以显著减少缺页中断次数，前提是每行的数据能很好地适应页的大小。 总而言之，这段“其他考虑因素”内容是在讨论除了基本的页面置换算法和帧分配策略之外，系统设计者和（在某种程度上）程序员还可以采取哪些措施来优化基于需求分页的虚拟内存系统，核心目标都是为了减少代价高昂的缺页中断，从而提高系统整体性能。 Loading... ## Background ### Multiprogramming Problem: if a program needs to be run, but there is no enough free memory? One solution：**swap out (换出) a process and swap in (换入)** the target process ### Swapper - Function: A completeprocess can be swappedtemporarily out of memory to a backing store, and then brought back into memory for continued execution - **Swapper (一定要跟后面的 Pager 区分）： A swappermanipulates entireprocess swapping** | Advantanges | Disadvantages | | ------------------------- | ------------------------------------------------------------ | | Increase multiprogramming | Context switch time can then be very high; Total context switch timeincludes swapping time for the whole process | #### Improvement: Swapping with Paging - When memory is low, unused pages are swapped to disk (instead of whole processes) - Pager is then designed to solve following problems: - How to determine which pages are unused? - What happens when a process suddenly tries to access a page that was swapped out? ### Introduction to virtual memory - Program can be partially loaded into memory - Program length is no longer constrained by limits of physical memory - Each program takes less memory → more programs run at the same time - Less I/O needed to load programs into memory → each user program runs faster - Virtual memory –separation of user logical memory from physical memory - Logical address space can therefore be much larger than physical address space - Only needed pages are loaded into memory ## Demand Paging ### Definition Paging can bring pages into memory which are needed. - Advantages - Less I/O needed, no unnecessary I/O - Less memory needed - Faster response - More users/processes - Page is needed (called a **reference** to the page) - Invalid reference might be caused by - Wrong adress $\to$ process abort - Not-in-memory $\to$ bring to memory - Apagercan swap in and out one page at a time (not a whole process like swapper does) - **MMU determines the set of pages that are needed in the memory** Valid-Invalid bit is to check if a reference is valid or not, associate each page table entry with a valid-invalid bit. - **v**: the page is in memory - **i**: the page is: - either not-in-memory - or wrong logical address - Initially valid-invalid bit is set to **i** on all entries ### Page Fault Definition: - Caused when a process makes **a reference to a page which is not in RAM** - **MMU** detects that the page is marked as invalidin the process’s page table Two posibilities: - the process is trying to access a page that does not exist at all - Solution: Process aborts - The page is not in memory but is somewhere on the hard disk - Solution: Load the page from hard disk to RAM （注意这里后面可能要引入 Page Replacement 算法） #### Steps in Handling a Page Fault  1.CPU makes a reference to a page which is marked*i*in the page table 2.MMU traps to kernel - if the reference page does not exist at all, stop the process; - otherwise, go to 3 3.Find the page in the hard backing store 4.Find a free frame in the memory and load the page into that frame 5.Reset the page table such that the valid bit is *v* 6.Restart the process by re-executing the instruction which caused the page fault. #### An extreme analysis of demand paging  #### Improvement: Locality Reference - Content: The tendency of processes to reference memory in patterns rather than randomly, resulting in reasonable performance from demand paging. - Working-set model: The set of pages in the most recent page references - Locality model: A model for page replacement based on the working-set strategy - At any point in time, a process usually uses only a small part of all its pages. Here is an example of keeping track of the working set: 由于精确追踪的困难，操作系统通常采用**近似**方法来跟踪工作集。一个常见的近似方法是结合使用**固定间隔的定时器中断（fixed-interval timer interrupt）和 引用位（reference bit）**。 以下是这种近似方法的工作原理： 1. **设置定时器和引用位：** - 选择一个工作集窗口 Δ 的值（例如，10,000 次引用）。 - 配置硬件或操作系统，使其能够为每个页面维护一个**引用位**。当硬件（MMU）访问一个页面时，它会自动设置该页面的引用位为 1。 - 设置一个定时器，使其以固定的间隔（例如，每 5,000 次引用）触发中断。这个间隔通常小于 Δ。 - 为每个页面在内存中额外维护一些**历史位（history bits）**，用于记录引用位的历史状态（例如，2 位历史位，或者一个 8 位字节）。最初，这些位通常被清零。 2. **定时器中断时的处理：** - 当定时器中断发生时，操作系统会遍历每个进程的页面。 - 对于每个页面，操作系统将该页面的**引用位**的值转移到历史位中，例如，将其移入历史位的最高位。如果使用多位历史位，则将现有的历史位向右移动一位。 - 操作系统随后将该页面的硬件**引用位重置为 0**。 3. **确定近似工作集：** - 当操作系统需要知道一个页面是否是工作集的一部分（例如，在发生页错误时或需要进行页替换时），它会检查该页面的当前**引用位和历史位**。 - **如果这些位中的任何一个为 1**，则表明该页面在最近的一段时间内（由定时器间隔和历史位的数量决定）被引用过。因此，这个页面被认为是近似工作集的一部分。 **准确性与开销的权衡** 这种近似方法并非完全准确。操作系统不知道在最近的定时器间隔内，引用位是在何时被设置的。它只知道该页面在某个时间点（由历史位覆盖的时间段）内被引用过。 [](https://imgse.com/i/pVSfnmR) ### Demand Paging Optimizations - Set a swap space on hard disk (not supported in mobile systems) - I/O faster than file system I/O - Less management is needed than file system - Copy entire process image to swap space at process load time, then page in and out of swap space (e.g., in older BSD Unix) - Discard the pages if they are not modified in the memory - When a page is needed to page out to free a frame, if its content is not changed, no need to transfer out ### Copy-on-Write 感觉是一个很孤立的知识点 **Definition: COW allows both parent and child processes to initially share the same pages in memory** When a child process is initially created: - only copy the page table of its parent - share parents' pages - the shared pages are write-protected (using protection bits of page tables) - If either process modifies a shared page, then copy that page. [](https://imgse.com/i/pVSfQk6) ## Page Replacement ### Background 当出现一个 Page Fault 的时候，新的 page 应该要被加载进来。但是如果此时已经没有 frame 可以用了，就需要 swap 一些 pages 出 memory #### Question 1: from which process a page is replaced - Global replacement - Process selects a replacement frame from the set of all frames - One process can take a frame from another process. - The # of frames allocated to each process will change. - Local replacement - Each process selects from only its own set of allocated frames. - The # of frames allocated to each process does not change Comparison: - Global replacement - Process execution time can vary greatly - But greater throughput (吞吐量), so it is more commonly used - Local replacement - More consistent per-process performance - But possibly under-utilized memory #### Question 2: Which pages to replace (be removed from RAM)? - Two good candidates: - Pages which are not used by a process right now - Pages that are not modified (called dirty) recently - An **algorithm** is needed to find the right frame to free - **Victim page**: the page that will be replaced ### Page and Frame Replacement algorithms - Frame-allocation algorithms - Determine how many frames to give each processes - Page-replacement algorithms - Which frame to be replaced - Want lowest page-fault rate on both first access and re-access - Algorithm evaluation - Run it on a particular string of memory references (reference string) and compute the number of page faultson that string - String is just page numbers, not full addresses - Results depend on number of frames available #### FIFO - Rule: Replace the oldest one - Implementation: - 维护一个循环队列 (circular queue) - 队头 (head): oldest one - 队尾 (tail): Recent arrival - 当出现一个 Page Fault 的时候：`++ head, q[++ tail] = new page` #### Optimal - Rule: Replace the page that will not be used for longest period of - This method can only be used to measure how other algorithms are close to the optimal - 实际上不可以被实现，因为永远无法预测未来哪些 Frame 最久不会出现 #### LRU (Least Recently Used) Algorithm - Rule: Replace page that has not been used in the most amount of time - Better than FIFO(15) but worse than OPT(9) - LRU is a good algorithm and frequently used - LRU and OPT don’t have Belady’sAnomaly ##### Implementation 1: Counter 一句话：对于队列中的 Frame 维护一个 Page Counter，每次入队的时候赋值为 global counter （相当于一个时间戳），每次发生 Page Fault 的时候，遍历队列找到最小的 Page Counter，把那个 Page 移除。 ##### Implementation 2: Stack 一句话：其实根本不是 Stack。分两种情况讨论： 1. 如果要加入的 page 已经在 stack 中，则找到那个 page，从提到栈顶（代表最近访问的 page） 2. 如果发生了 page fault，那么栈底（一定是最久没有被用的 page）被删除，把新的 page 加入栈顶 ##### Approximation algorithms 见附文 ### Page Buffering More strategies (algorithms) in improving the efficiency of page replacement [](https://imgse.com/i/pVSOG3n) ## Allocation of Frames - For the performance reason, each process needs minimum number of frames - This number is defined by the computer architecture - Maximum frame number is defined by the amount of total frames in the system. ### Allocation schemes #### Fixed allocation - Equal allocation - Each process is allocated same number of frames - Disadvantage: Space waste for small process - Propositional allocation - Allocate frames according to the size of a process - Disadvantage: Process size might be changed during the execetion #### Priority allocation - The ratio of frames depends on the combination of size and priority of a process - Replace the pages of process with lower priority **Page Replacement 触发：before the number of frames falls below a certain threshold** ## Thrashing ### Definition - Background: If a process does not have enough frames in memory, the page-fault rate will be very high - Replace page frequently - The replaced page might be used again - That will result in - Low CPU ultilization - OS keeps adding new process, trying to increase CPU utilization - 陷入恶性循环 - Definition: A process is busy swapping pages in and out, instead of doing useful work 导致 Thrashing 的原因：  **Thrashing 的原因和恶性循环**： - Thrashing 通常伴随着严重的性能下降。 - 一个主要的表现是 CPU 利用率大幅下降。 - 在早期的分页系统中，操作系统可能会监控低 CPU 利用率，并错误地认为系统有空闲资源，于是增加多道程序设计度（degree of multiprogramming），引入更多进程来运行。 - 新引入的进程也需要帧，它们会进一步从已有的进程那里“窃取”帧。 - 这导致更多进程的帧数量不足，缺页率进一步升高。 - 所有这些频繁缺页的进程都会排队等待分页设备（用于页面调入调出），导致分页设备的平均服务时间增加。 - 由于进程都在等待分页设备，就绪队列变空，CPU 利用率进一步下降。 - 操作系统看到持续下降的 CPU 利用率，可能会继续增加多道程序设计度，从而形成一个恶性循环，使 Thrashing 加剧，系统吞吐量急剧下降。 - 图 10.20 展示了这种现象，随着多道程序设计度增加，CPU 利用率先上升，达到峰值后，如果继续增加多道程序设计度，Thrashing 发生，CPU 利用率急剧下降。 ### Solutions - Decrease the degree of multiprogramming - Establish “acceptable” page-fault frequency (PFF) rate and use local replacement policy - Install enough physical memory (hardware) - Install faster hard disk ### Page-Fault Frequency  ## Allocating Kernel Memory 好的，根据您提供的资料和我们的对话历史，我们可以来讲解一下“Allocating Kernel Memory”（分配内核内存）这个概念。 **什么是分配内核内存？** 分配内核内存是指操作系统内核为自身运行和管理系统资源而进行的内存分配过程。这与为用户应用程序分配内存是不同的。 **为什么内核内存分配与用户内存分配不同？** 有几个主要原因导致内核内存的分配策略需要特殊考虑： 1. **数据结构大小多样且通常较小**：内核需要内存来存放各种不同大小的数据结构，例如进程控制块 (PCB)、文件描述符结构体 等。这些结构体的大小通常小于一个页帧的大小。因此，内核必须谨慎使用内存，并尽量减少因**内部碎片**（即分配的内存块大于实际需求而造成的浪费）引起的浪费。需要为每种结构体管理多个实例。 2. **内核代码/数据通常不参与分页**：许多操作系统不将内核代码或数据放入分页系统。这意味着分配给内核的物理内存通常是常驻内存的，不会被交换到二级存储。这种设计会影响内核的总体设计。优点包括避免内核缺页带来的性能问题和复杂性；缺点可能包括消耗更多物理内存，以及在内存紧张时无法将内核部分内容换出。 3. **某些硬件需要连续的物理内存**：某些硬件设备（如直接与物理内存交互而无需虚拟内存接口的设备）可能需要驻留在物理上连续的页帧中的内存。 4. **性能要求高**：内核操作对性能非常敏感，内存分配和释放需要快速高效。 **内核内存分配方法** 由于上述特殊需求，内核通常使用专门的内存分配机制。资料中提到了两种主要的内核内存分配策略： 1. **伙伴系统 (Buddy System)** - **工作原理**：伙伴系统从一个固定大小的、由物理上连续的页组成的内存段中分配内存。它使用一种“幂等分配器”（power-of-2 allocator），以 2 的幂次方（如 4KB, 8KB, 16KB 等）为单位满足请求。如果请求的大小不是 2 的幂，系统会将其向上取整到下一个最大的 2 的幂。例如，请求 21KB 的内存会被分配一个 32KB 的段。初始时，一个大段会被递归地分成两个等大的“伙伴”子段，直到找到一个大小合适（向上取整后）的子段来满足请求。 - **优点**：相邻的空闲伙伴可以快速合并（称为 **coalescing**）成更大的段，这有助于减少外部碎片。 - **缺点**：向上取整到下一个 2 的幂可能会导致分配的段内部出现**内部碎片**，因为分配的块可能会显著大于实际请求的大小。例如，一个 33KB 的请求只能用 64KB 的段来满足。资料提到不能保证小于 50% 的已分配单元不会因内部碎片而浪费。 - **Linux 中的应用**：Linux 使用伙伴系统来管理物理页帧的分配，特别是按区域（zone）划分的物理内存。 2. **Slab 分配器 (Slab Allocator)** - **工作原理**：Slab 分配器使用**缓存 (cache)** 来存储唯一的内核数据结构。每种内核数据结构（例如，进程描述符、文件对象、信号量等）都有一个对应的缓存。一个缓存由一个或多个 **Slab** 组成。一个 Slab 则由一个或多个物理上连续的页组成。每个 Slab 被划分为多个**对象 (object)**，这些对象是该数据结构的实例。每个对象有两种状态：空闲 (free) 和已用 (used)。当内核需要某个数据结构的实例时，分配器会从该数据结构对应的缓存中分配一个空闲对象来满足请求。分配的对象会被标记为已用。当内核使用完一个对象并释放它时，它会被标记为空闲并返回到其缓存中，从而可用于后续请求。 - 优点 ： - **无碎片**：由于每个缓存是为特定大小的内核数据结构设计的，分配器会返回表示该对象所需的**精确数量的内存**。因此，不会因碎片而浪费内存。 - **分配速度快**：对象在创建缓存时就已预先分配好。当内核需要时，可以直接从缓存中获取一个空闲对象，这比动态分配内存要快得多。当对象被释放时，它被返回到缓存，立即可用。这对于频繁分配和释放对象的场景非常有效。 - **历史与 Linux 中的应用**：Slab 分配器最初出现在 Solaris 2.4 内核中。Linux 从版本 2.2 开始采用了 Slab 分配器，称为 SLAB。后续版本引入了 SLUB（自 2.6.24 起成为默认）和 SLOB（适用于内存有限的嵌入式系统）等改进型分配器。 - **示例**：在 Linux 中，进程描述符 `struct task_struct` 需要大约 1.7KB 内存。当 Linux 内核创建一个新任务时，它会从 `struct task_struct` 对应的缓存中请求所需的内存，缓存会分配一个已在 Slab 中分配且标记为空闲的对象来满足请求。 除了这两种主要方法，资料中关于 Linux 内核内存管理的部分还提到： - **`kmalloc()`**：用于处理任意大小的请求（大小不预先知道，可能只有几个字节）。它会按需分配完整的物理页，然后将它们分成更小的块。分配的内存必须通过 `kfree()` 显式释放。 - **`vmalloc()`**：用于将物理上不连续的物理页分配到一个虚拟上连续的内核内存区域。 - **`vremap()`**：用于将一系列虚拟地址映射到设备驱动程序用于内存映射 I/O 的内存区域。 **内核虚拟内存** 值得注意的是，内核的虚拟内存也需要管理。Linux 为每个进程保留了一个固定的、依赖于体系结构的虚拟地址空间区域用于自身内部使用。这些区域中的页表项被标记为受保护，因此当处理器运行在用户模式时，这些页面不可见或不可修改。这块内核虚拟内存包含一个静态区域，其中包含对系统中每个可用物理内存页的引用，使得在内核代码运行时可以进行简单的物理地址到虚拟地址的转换。内核的核心以及通过普通页分配器分配的所有页面都驻留在这个区域。这种设计（将内核代码映射到每个进程的地址空间中）有助于实现用户模式和内核模式之间更快的切换，因为不需要保存和恢复内存管理寄存器，并且缓存也不会失效。 总之，分配内核内存是一个专门化的过程，旨在高效、安全地为操作系统内核本身管理内存资源，以满足其特殊的需求，如处理各种大小的数据结构、支持不参与分页的常驻内存以及满足对物理连续性的要求。主要方法包括伙伴系统和 Slab 分配器，它们各自针对不同的分配场景提供了优化。 ## Other considerations 好的，您提供的这段文字出自关于**虚拟内存 (Virtual Memory)** 的章节，具体是探讨在实现虚拟内存和需求分页 (Demand Paging) 时的一些“其他考虑因素”。这些因素都是为了**减少缺页中断 (Page Faults)** 和**提高系统性能**。 这段内容主要说明了可以通过以下几个方面来优化分页系统的性能： 1. **预分页 (Prepaging)**: - 这是一种尝试减少进程启动时大量缺页中断的策略。 - 其思想是，在进程真正需要这些页面之前，就将它可能需要的部分或全部页面一次性加载到内存中。例如，在使用工作集模型 (working-set model) 的系统中，当一个进程被唤醒时，系统可能会尝试将其整个工作集（即最近经常使用的页面集合）预先加载到内存。 - **需要权衡 (Need to balance)**：预分页的成本是加载了可能不会立即使用（或根本不使用）的页面，这会浪费 I/O 和内存资源。其效益在于避免了后续对这些页面的单独缺页中断服务时间。是否使用预分页，以及预分页多少，取决于预分页页面中实际被使用的比例。 - 来源还提到了 Linux 的 `readahead()` 系统调用，用于预取文件内容到内存。 2. **页大小选择 (Page size selection)**: - 系统设计者在设计新机器时需要决定最佳的页大小。对于现有机器，页大小通常是固定的。 - 页大小的选择涉及多种权衡： - **页表大小 (Page table size)**：对于给定的虚拟内存空间，减小页大小会增加页数，从而增加页表的大小。较大的页大小有利于减小页表大小。 - **内存碎片 (Fragmentation)**：使用较小的页大小可以更好地利用内存，因为它能减少内部碎片（即分配的最后一个页帧未被完全使用造成的浪费）。平均而言，内部碎片约为半页大小。 - **I/O 时间和局部性 (I/O time and locality)**：较大的页大小意味着每次缺页中断时需要传输更多数据，但这通常减少了总体的缺页中断次数，因为局部性原理使得相邻数据也可能被需要。较小的页大小更准确地匹配程序局部性，但可能导致更多的缺页中断和 I/O 操作。 - 历史趋势是页大小逐渐变大。现代系统通常使用 4KB 或 8KB 的页，一些系统支持更大的页（如 x86-64 上的 2MB 或 1GB “大页/巨页”）。 - **需要权衡 (Need to balance)**：需要在页表大小、内部碎片、I/O 时间和局部性等因素之间找到平衡。 3. **TLB 覆盖范围 (TLB reach)**: - **TLB 覆盖范围**是指 TLB (Translation Look-aside Buffer) 所能直接访问的内存量，计算方式是 TLB 条目数乘以页大小。 - TLB 是页表的硬件缓存，用于加速地址翻译。TLB 命中率高意味着地址翻译快，性能好。 - 理想情况下，一个进程的工作集应该存储在 TLB 中。 - 增加 TLB 覆盖范围可以提高 TLB 命中率，从而减少通过页表查找物理地址的需要（这通常需要额外的内存访问）。 - 可以通过增加 TLB 的条目数（硬件成本高且耗电）或增加页大小来增加 TLB 覆盖范围。有些系统支持多种页大小来实现这一点。 - **需要权衡 (Need to balance)**：增加 TLB 条目数成本高，增加页大小又面临碎片等问题。因此也需要在 TLB 大小、页大小和性能/成本之间进行权衡。 4. **程序结构 (Program structure)**: - “程序员能做什么？” 这里探讨的是程序编写方式对分页性能的影响。 - 尽管需求分页对用户程序是透明的，但程序的结构（如何访问数据、数据结构的组织方式）会影响**局部性 (locality)**，进而影响缺页中断率和工作集的大小。 - 通过仔细选择数据结构和编程结构，程序员可以提高程序的局部性，从而降低缺页中断率。 - 来源提供了一个例子：初始化一个二维数组时，按行访问比按列访问可以显著减少缺页中断次数，前提是每行的数据能很好地适应页的大小。 总而言之，这段“其他考虑因素”内容是在讨论除了基本的页面置换算法和帧分配策略之外，系统设计者和（在某种程度上）程序员还可以采取哪些措施来优化基于需求分页的虚拟内存系统，核心目标都是为了减少代价高昂的缺页中断，从而提高系统整体性能。 最后修改：2025 年 05 月 27 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
