页式存储
页式存储是现代操作系统中常用的一种内存管理技术。在这种机制下，程序的逻辑地址空间被划分为固定大小的页面，而物理内存也被划分为同样大小的页框（或称为物理页面）。这种划分使得内存管理更加高效，并支持虚拟内存的概念。
下面是一些关于页式存储的关键点：
- 页面和页框：
- 页面（Page）：程序逻辑地址空间中的固定大小块。
- 页框（Page Frame）：物理内存中的固定大小块，用于存放页面。
- 页面大小：
- 页面大小通常是2的幂次方，例如4KB、8KB等。页面大小的选择需要平衡多个因素，包括寻址开销、碎片率和TLB（Translation Lookaside Buffer）命中率。
- 页表：
- 每个进程都有一个页表，它记录了逻辑页面与物理页框之间的映射关系。
- 页表中的每一项称为页表项（Page Table Entry, PTE），通常包含物理页框号、有效位（是否已分配给某个页面）、保护位（读写权限）等信息。
- 地址转换：
- 地址转换由硬件的MMU（Memory Management Unit）完成，MMU根据页表将逻辑地址转换成物理地址。
- 逻辑地址由两部分组成：页面号和页内偏移量。MMU使用页面号索引页表以找到对应的物理页框号，然后加上页内偏移量得到最终的物理地址。
- 缺页处理：
- 当进程试图访问的页面不在物理内存中时，会发生缺页中断（Page Fault）。
- 缺页中断由操作系统处理，它负责从磁盘加载缺失的页面到物理内存，并更新页表。
- 页面置换算法：
- 当物理内存空间不足时，需要使用页面置换算法来决定从物理内存中替换出哪个页面，以便腾出空间给新的页面。
- 常见的页面置换算法包括最近最少使用（LRU）、先进先出（FIFO）和最优置换算法（Optimal）等。
- 分层页表和反向映射：
- 对于大内存空间，通常采用多级页表结构来减少页表占用的内存。
- 反向映射允许物理内存到逻辑地址的映射，这对于调试和监控系统行为很有帮助。
页式存储提供了灵活性和安全性，允许操作系统实现虚拟内存、内存保护和内存共享等功能。
页号是把虚拟地址分为多少个页，通过页号和页内地址找到虚拟地址（数据），
通过一个具体的例子来说明如何进行程序逻辑地址到物理地址的转换。
虚拟地址转换为物理地址过程
假设条件
- 页面大小：设定为4KB（即 2的12次方字节）。
- 逻辑地址空间：假设为32位地址空间，这意味着地址范围是从0到2的32次方-1
- 物理内存大小：假设为1GB（即 2的30次方字节）。
计算页面数量
- 逻辑页面数量：由于地址空间为32位，页面大小为4KB，我们可以计算逻辑页面的数量。逻辑地址空间大小为 2的32次方字节，每个页面大小为 2的12次方字节，所以逻辑页面数量为 2的32次方除以2的12次方=2的20次方
- 物理页框数量：物理内存大小为1GB，每个页框也是4KB，所以物理页框数量为
1GB = 1,073,741,824 字节 (因为 1GB = 2^30 字节) 每个页框大小为 4KB = 4096 字节 (因为 1KB = 2^10 字节)
那么物理页框的数量就是总字节数除以每个页框的字节数：
物理页框数量 = 1,073,741,824 字节 / 4096 字节/页框 = 262,144 页框
因此，1GB的物理内存可以划分为262,144个4KB大小的页框。
页表结构
- 页表项大小通常为4字节，因此页表本身占用的内存为2的20次方乘以4等于2的22次方 字节，即4MB。
- 每个页表项包含物理页框号，以及其他控制信息（例如有效位、读写权限等）。
地址转换过程
假设我们要访问的逻辑地址为 0x12345678
- 计算页面号：逻辑地址可以分为两部分：页面号和页内偏移量。页面号可以通过逻辑地址除以页面大小来计算，即 0x12345678/2的12次方。在32位地址空间中，页面号占用20位（因为 2的20次方个页面），页内偏移量占用12位。因此，页面号为 0x12345页内偏移量为 0x678
- 查询页表：使用页面号 0x12345作为索引去查询页表，假设该页表项中记录的物理页框号为 0x345678
- 计算物理地址：将物理页框号 0x345678左移12位（即乘以 2的12次方）再加上页内偏移量 0x678 得到最终的物理地址。因此，物理地址为 0x34567800+0x678=0x34567E78。
总结
- 逻辑地址：0x12345678
- 页面号：0x12345
- 页内偏移量：0x678
- 物理页框号：0x345678（假设）
- 物理地址：0x34567E78
这就是一个简单的逻辑地址到物理地址转换的例子。请注意，在实际的操作系统中，页表可能还会包含其他的信息，如访问权限、修改标志等。此外，对于更大的地址空间，可能会使用多级页表来减少页表的大小。
示例
进程P有8个页面，页号分别为0~7,页面大小为4K，假设系统给进程P分配了4个存储块，进程P的页面变换表如下所示。表中状态位等于1和0分别表示页面在内存和不在内存。
- 若进程P要访问的逻辑地址为十六进制5148H，则该地址经过变换后，其物理地址应为十六进制XXXX
- 如果进程P要 访问的页面6不在内存，那么应该淘汰页号为XXXX的页面（也就是需要调入页面6淘汰一个页面）
第一题：
根据题意，页面大小为4K,逻辑地址为十六进制5148H页号为5，页内地址为148H，查页表后可知页帧号(物理块号)为3，该地址经过变换后，其物理地址应为页帧号3拼上页内地址148H，即十六进制3148H。
之所以第一位为5，即可以通过查表来转换物理地址，最后拼上页内地址
主要的逻辑如下：
- 5148H转换为二进制为0101 0001 0100 1000
- 由于页面大小为4K字节，也就是12次方，对应上方二进制的后12位即为页内地址
- 通过查表可知，前面4个二进制代表5，对应表格为3。 最后拼接后面的地址 即3 148
第二题（先看访问位再看修改位，如果最近被访问过则不替换，如果都被访问了再看修改位）
据题意，页面变换表中状态位等于1和0分别表示页面在内存或不在内存，所以1、2、5和7号页面在内存。当访问的页面4不在内存时，系统应该首先淘汰未被访问的页面，因为根据程序的局部性原理，最近未被访问的页面下次被访问的概率更小;如果页面最近都被访问过，应该先淘汰未修改过的页面，因为未修改过的页面内存与辅存一致， 故淘汰时无须写回辅存，使系统页面置换代价更小。
综上分析，1、5和7号页面都是最近被访问过的，但2号页面最近未被访问过，故应该淘汰2号页面。
页面置换算法
页面置换算法是内存管理中的一个重要组成部分，用于决定当物理内存空间不足时，应该从内存中替换掉哪些页面。这些算法的目标是在保证进程运行效率的同时，尽量减少缺页中断的次数，以降低系统的整体响应时间和提高性能。
下面是几种常见的页面置换算法：
- 先进先出（FIFO, First-In First-Out）
- 这是最简单的页面置换算法。
- 它总是选择最早进入内存的页面进行替换。
- FIFO 算法可能导致“Belady 异常”，即增加物理页面的数量反而会导致更多的缺页中断。
- 最近最少使用（LRU, Least Recently Used）
- LRU 算法选择最近最久未使用的页面进行替换。
- 实现 LRU 需要维护一个能够快速查找每个页面最后使用时间的数据结构，这可能增加硬件成本。
- 在软件实现中，LRU 可以通过链表或其他数据结构来近似实现。
- 最近未使用（NRU, Not Recently Used）
- NRU 是一种简化的 LRU 算法，它基于每个页面的一个位来标记页面是否在最近的时间段内被访问过。
- 如果所有页面都被标记为最近使用过，则随机选择一个页面进行替换。
- 最佳置换算法（Optimal）
- 这是一种理论上的算法，它总是选择未来最长时间内不会被访问的页面进行替换。
- 由于它需要预知未来，所以在实际系统中无法实现，但它提供了一个基准，用于衡量其他算法的性能。
- 最近未用过（NUB, Never Used Before）
- NUB 算法选择从未被使用过的页面进行替换，适用于刚启动的应用程序或新加载的页面。
- 时钟置换算法（Clock）
- 时钟算法结合了 LRU 和 NRU 的思想。
- 每个页面有一个位来标记是否最近被访问过，以及一个指针来遍历页面。
- 算法遍历页面列表，找到第一个未被访问过的页面进行替换，并将所有被访问过的页面标记为未访问状态。
- 第二次机会（Second Chance）
- 这是时钟算法的一个变体。
- 当算法遍历时，如果页面的访问位被设置，则将其清除而不立即替换页面，给页面一个“第二次机会”。
- 这种方法有助于减少频繁替换最近使用过的页面的情况。
- 工作集（Working Set）
- 工作集算法考虑进程当前的工作集，即一段时间内访问的所有页面。
- 算法选择那些不在工作集内的页面进行替换，从而减少缺页中断。
- 最近最少使用近似（Approximate LRU, A-LRU）
- A-LRU 是 LRU 的近似实现，通常使用缓存行中的计数器来近似页面的使用情况。
- 计数器越低的页面被认为越少使用，从而被选择替换。
每种算法都有其优点和缺点，选择哪种算法取决于具体的应用场景和系统设计的需求。例如，LRU 被广泛认为是性能较好的算法之一，但由于其实现复杂度较高，有时会选择时钟算法或其变体作为替代方案。
示例
https://wenku.csdn.net/answer/ff8e13cb931f4d7983abc7c02a8463cc
某进程有4个页面，页号为0〜3，页面变换表及状态位、访问位和修改位的含义如下 图所示。若系统给该进程分配了3个存储块，当采用第二次机会页面替换算法时，当访问的页面1不在内存时，淘汰表中页号为 （D） 的页面代价最小。
页帖号就是物理块号，
不在内存中，是不能淘汰不在内存中的页号，当状态位和访问位都为1时，看修改位，先淘汰未修改过的，因为根据时间局限性，页面没被修改过，则不久以后也不会被修改，如下图所示：
分页内存管理的核心是将虚拟内存空间和物理内存空间皆划分为大小相同的页面，并以页面作为内存空间的最小分配单位，下图给出了内存管理单元的虚拟的物理页面翻译过程，假设页面大小为4KB，那么CPU发出虚拟地址0010000000000100，其访问的物理地址是（ ）。
解析：页面大小为4KB 即2的12次方，虚拟地址中后12位去掉，得到0010是对应的物理块2得到110地址，所以物理地址是110000000000100
为了解决程序比内存大的问题，我们可以允许一个进程的部分虚拟页面存放在物理页面之外，也就是磁盘上。在需要访问这些外部虚拟页面时，再将其调入物理内存。由此，交换系统的所有缺陷均被克服。
内存管理单元对虚拟地址的翻译只是对页面号的翻译，即将虚拟页面号翻译成物理页面号。而对于偏移值，则不进行任何操作。这是因为虚拟页表和物理页表大小完全一样，虚拟页面里的偏移值和物理页面里的偏移值完全一样，因此无须翻译。
在页式存储管理系统中，地址寄存器（也称为虚拟地址或线性地址）被分为两部分：页号（Page Number）和页内偏移（Offset）。给定的信息是地址寄存器长度为 24 位，其中页号占 12 位。这意味着剩余的 12 位用于页内偏移。
采用ECC校验技术，一个8位的数据产生的ECC码要占用5位的空间，一个32位的数据产生的ECC码要占用（ ）位的空间。
本题考查服务器技术的相关概念。ECC( Error Checking and Correcting ,错误检查和纠正)不是一种内存类型，而是一种内存技术。ECC纠错技术也需要额外的空间来存储校正码，但其占有的位数跟数据的长度并非成线性关系。ECC将信息进行8比特位的编码，采用这种方式可以恢复1比特的错误。每一次数据写入内存的时候，ECC码使用一种特殊的算法对数据进行计算，其结果称为校验位(Check Bits)。然后将所有校验位加在一起的和是“校验和”(checksum),校验与数据一起存放。当这些数据从内存中读出时，采用同一算法再次计算校验和，并和前面的计算结果相比较，如果结果相同，说明数据是正确的，反之说明有错误，ECC可以从逻辑上分离错误并通知系统。当只出现单比特下位错误的时候，ECC可以把错误改正过来不影响系统运行。一个8位的数据产生的ECC码要占用5位的空间，16位数据需占用6位；而32位的数据则只需再在原来基础上增加一位，即7位的ECC码即可，以此类推。
