操作系统总结
一：内存的基本知识
1：内存的分层体系
CPU微处理器（CPU寄存器+L1、L2高速缓存）：速度快，容量小
主存、物理内存：速度稍快，容量大。主要用于放置操作系统和代码。
磁盘（虚拟内存）：速度慢，容量最大用于扩充空间和备份数据
2：操作系统与内存
（1）操作系统的作用：
抽象：把物理地址抽象为逻辑地址
保护：每个进制都有独立的地址空间
共享：进程间通过访问相同的内存，传递数据
虚拟化：扩充地址空间
（2）操作系统的管理方法
程序重定位
分段
分页
虚拟内存
按需分与虚拟内存
（3）负责管理的硬件
MMU：内存管理单元，负责处理CPU的内存访问请求。
3：地址空间
（1）定义
物理地址空间：由硬件支持的内存条和主存构成，在此存储结构内能直接被访问的真实存储区域
逻辑地址空间：程序在运行过程中所占用的虚拟内存范围，并以符号名作为标识符依次对应不同的存储位置
（2）生成过程
程序所需的所有逻辑存储位置通过编译、汇编、链接及加载等操作被系统自动分配
（3）地址重定位
将逻辑地址映射为物理地址的过程
静止重定位：在程序装入主存时完成映射，不再变化
无需硬件地址变换机构的支持，只要求程序是可重定位的
必须给作业分配连续的存储区域
不能扩充存储空间
不能移动作业
多个作业难以共享同个程序的副本和数据
动态重定位：在程序运行期间完成映射
硬件地址变换机构的支持
程序可以换入换出主存，扩大主存空间
作业可以移动
可以利用较小的主存块
可以实现共享
（4）地址检查
基址/限长寄存器保护
检查逻辑地址空间的长度（界限寄存器）
加上逻辑地址空间的起始地址（基址寄存器），得到物理地址
上下界寄存器保护
检查逻辑地址空间的起始地址（上界寄存器）
检查逻辑地址空间的结束地址（下界寄存器）
二：内存的分配
1：连续分配——分区
（1）分配的问题
内存碎片：无法利用的空闲内存空间
外碎片：外部碎片指分布在各个单元之间的残留片段资源。
内碎片：内部碎片指的是已预先划分好的单元中的残留片段资源。
（2）分发时机：
程序在其运行期间需动态加载至内存以供调用。
程序在执行过程中必须频繁访问存储器中的数据块以完成操作。
（3）分发方式：
- 固定分区策略
系统预设若干个分区用于存储不同类型的进程资源。
这些区域的容量可设置为不等大小。
通过一个记录表来跟踪各区域的使用状态以便及时调整内存布局以优化资源利用率。
可能导致内存碎片的问题发生当程序或作业的执行规模与系统分区设置不相匹配时
具体来说
2：
可变分区是一种能够根据运行情况动态调整内存分配策略的技术
其核心机制在于将内存空间划分为可变大小的部分
并通过维护已分配内存表和未分配内存表来实现资源的有效管理
分配算法
1： 首次适配：第一匹配分配
First-fit algorithm: Starts from the lowest address and allocates the first available and having sufficient capacity free block. Loop-first fit algorithm: Begins allocation from the newly allocated empty space and selects the first available with sufficient capacity. The free blocks are sorted by their addresses. A suitable free block is identified and allocated when a process requires memory space. At recycling time, we check if adjacent free blocks can be merged to save space. The advantages of this algorithm include efficient memory management and reduced fragmentation.
简单
易于产生更大的空闲块（在地址空间结尾）
缺点
易于产生外碎片
不确定性
2： 最优适配：最合适匹配分配
为了不让大空闲块被分割开来的同时又能最大限度地减少外部碎片，在选择资源时应优先考虑那些既足够灵活又满足需求的空闲资源
将空闲块按照尺寸进行排序；识别合适的空闲块，并对其进行资源分配；在回收过程中检查是否能合并相邻的空闲块；该方法具有显著的优势。
较为简单
若大多数需求为小尺寸，则该方法表现优异
不足之处
该方案存在明显的效率瓶颈。
在资源重新分配过程中存在缓慢现象。
该方案容易形成低效的小规模碎片。
最差适配即指无法有效匹配资源的情况。
在分割大空闲块时，为了避免产生太小的碎片，在选择空闲块时优先考虑足够大的且其容量大于所需的最大空闲块。
将空闲块按照尺寸进行排序
直接将最大的可用空闲块进行分配
在回收过程中检查是否有相邻的空闲块可以合并
该算法在运行效率和资源利用率方面具有显著优势
如果大部分需求都是大尺寸的则非常有效
缺点
容易导致外存碎片
重分配效率低下
存在较大分区无法进行合理配置的情况
特定类型的虚拟机资源可通过重定位式分区技术实现
通过将所有已分配的分区重新排列成连续区域，则可有效消除外存碎片。
（4）碎片管理策略
采用压缩方式整合片段
通过重新配置程序实现动态聚合
重置时机：程序处于等待状态且未执行相关操作；交换式碎片整理；抢占运行中的程序并回收其内存，并将原本等待的程序转移至虚拟内存存储在磁盘上。
2：非连续分配——分页/段
（1）连续分配的问题
分配给一个程序的物理内存是连续的
内存利用率较低
会产生碎片问题
（2）非连续分配的优点
更好的利用、管理内存
支持共享代码与数据
支持动态加载，动态链接
（3） 分页机制
分页基础：
划分物理内存至固定大小的帧，同时划分逻辑地址空间至大小相同的页。帧是非连续的，页是连续的。不是所有的页都有对应的帧，因为可能在虚拟内存中。
地址结构
物理寻址：一个内存物理地址包含帧号和帧内偏移
帧号：表示为F-bit字段（该字段占存有2^F个连续内存块）
帧内偏移：表示为O-bit字段（每个字段对应存储连续的2^O个字节）
物理地址：
其中物理地址由两个部分组成：
一部分是FrameNumber f占用的空间（即2^f bit）
另一部分是FrameOffset o占用的空间
逻辑寻址：
其寻址方式与FrameOffset一致
但内存块的大小与FrameSize不完全一致
第一页包含
CPU首先直接访问高速缓存（fast table）以查找对应帧信息。若快表未找到对应的帧，则进行下一步操作。找到对应信息后将其加载到TLB缓存中以供后续使用。在空间布局上,我们采用多级 page table 和 inverted page table 的组合策略,避免因页面不存在而导致的空间浪费。分层存储机制将对各个层级的地址进行划分,其中每个层次负责一部分地址范围,并记录其对应的子层级起始地址关系,最终完成一个多层级间接寻址机制的设计,从而构建出一个多层次的索引结构。
CPU首先访问一级页表。基于位于PTBR中的起始信息，在该一级级联中处理当前位移值高位部分所对应的下一层级起始位置。随后，在该确定下的层级位置基础上处理当前位移值低位部分所对应的虚拟进程ID（VSI）。最后根据该虚拟进程ID与偏移量计算出最终的实际内存地址。反向映射时面临的问题在于...
采用页寄存器机制：通过帧号可寻址页号；但无法直接取得对应帧号。
当程序运行时，在内存管理中可采取关联内存方案：当帧数量较小时可将页寄存器置于关联内存中实现并行寻址；但这种方式会带来较大的内存占用问题。
采用哈希查找方法时：系统会根据当前进程PID值与目标页面建立哈希表；通过运行哈希函数计算出对应的页寄存器地址；从而获取目标页面对应的进程位移值。
分段时间管理机制：
程序整体架构由多个子程序模块与共享资源等基本单元构成；
数据存储则分布在堆区、栈区及共享数据区等专用区域；
实施分段时间管理：
程序地址空间虽为单一连续的整体；但被划分为多个独立的时间片区域；每个时间片对应特定的功能模块或数据块；
这种组织方式既便于代码调试维护；又能够提高资源利用率。
地址结构
物理寻址：一个内存物理地址包含帧号和帧内偏移
段号字段定义为S位，并表示当前的总分划数。
偏移字段占O位，并确定当前操作单元的空间大小。
物理内存位置由s和o共同决定：
总体位置 = s × (2 × O) + o
其转换机制由一个包含起始位置信息以及数据长度信息的数据结构来存储。
系统内存管理功能主要包含两类基本实现方式：
基准寻址模式以及基准加偏移模式
CPU完成一段寄存器与地址寄存器结合的运算过程。这种单地址机制下,CPU将逻辑地址分解为两个部分:一个代表程序运行时所处的功能模块,另一个则代表具体的位置信息。
当系统试图访问超出当前存储容量范围的逻辑位置时,会触发越界中断。
系统通过预先配置好的基址寄存器获取起始位置信息,并利用预先建立好的表格查找该位置对应的具体存储区域。
确定了具体的存储区域编号后,系统依据特定标志位来判断该区域是否存在相应数据。
如果发现该区域不存在数据,则会触发缺断中断;反之,则会计算出相应的物理内存地址。
这一机制的一个显著特点是可以提高资源利用率的同时保证了各功能模块之间的良好共享性。（5） 段页式内存管理机制
将主存储空间划分为大小相等的基本存储单元,并将用户程序的功能划分成若干功能模块,每个功能模块又被分割成若干个小页片。
以这些基本存储单元为单位进行离散式的内存分配方式,以便更好地管理内存资源和提高系统的效率。
地址变换机构用于获取物理地址的方式包括段表寄存器（通过计算页表起始地址与页表长度的和来确定物理地址）。
根据段号可快速定位对应的段表信息。
结合页号及起始位置即可准确找到目标块的位置。
通过已知块号及偏移量即可计算出完整的物理地址。
虚拟内存系统主要针对内存不足的问题提供三种解决方案：
第一种是局部存储策略：仅将当前使用的指令和数据保留在内存中以减少资源占用；
第二种是动态内存管理策略：当程序运行超出可用内存时会将暂时不需要的部分送入外存以释放空间；
第三种是分层存储机制：将程序划分为多个模块分别管理以提高资源利用率。
覆盖机制作为虚拟内存的重要组成部分主要包含以下功能：
首先定义该机制的具体实现方式；
其次明确其适用场景；
最后分析其对系统性能的影响。
该机制的核心思想在于在有限的内存资源下实现高效的程序运行，
具体表现为能够动态地分配和回收内存资源从而满足多任务处理的需求。
过程：
根据其自身的逻辑功能划分成独立的模块与区域。
这些必要的代码与数据被归类于固定区域，并占用固定内存空间，并负责调用其他程序。
可选代码与数据被分配到可变区域，并且在任何时刻都不会同时被执行（即它们之间不会互相调用）。当需要时，在这些代码与数据之间共享一块内存空间，并按时间顺序依次加载。
优势在于能够执行比当前空闲区域更大规模的任务。
缺点：
提升了系统开发难度
以时间换取内存空间
（3）交换技术（程序与程序之间）
定义：多道程序在同一内存中运行时所采用的技术，在运行中的程序或待运行程序可获得更多的内存资源。
过程
当某个程序暂时不需要运行时，将其地址空间的内容存储在外部存储设备中以便获取空闲块空间。
当外存中的某个程序需要执行时，将其地址空间加载到内存中。
其优势在于通过优化资源管理能够获取更多的空闲内存空间。
缺点：
对操作系统的性能有一定的影响。
它需要较大的交换区来容纳所有用户进程的内存映像副本。
此外，在运行过程中可能会采用动态地址映射机制。
（4）虚拟内存管理技术
在虚拟存储器系统中：
该系统具备请求加载功能并能执行按需置换页面的功能。
它能够在主机内存中仅加载作业的部分代码和数据即可开始执行作业。
该存储器系统的逻辑容量是由主存与外存总容量以及CPU可寻址范围共同决定的。
特点：
与覆盖技术类似，在程序运行时可动态加载所需代码段到内存中。
与交互技术不同的是，在内存与外存之间仅交换必要的数据块。
基于程序的空间局部性和时间局部性原理：
时间局部性表明：同一指令行或操作在同一时间段内频繁访问同一数据。
空间局部性则指出：当前指令行及其邻近操作通常仅涉及一组相近的数据。
过程：
当系统装入所需的代码段到内存中时，则可立即启动相应的功能模块。
在运行过程中若遇到地址超出当前内存范围的情况，则需CPU主动向操作系统提交缺页请求并调入相应页面至内存。
当内存空间不足时，则需操作系统主动释放不需要使用的一些页面至磁盘空闲区域供其他进程使用。
优势：
相比传统固定分区式的存储管理方法而言：
请求分页系统的灵活性较高；
采用分段策略可提高资源利用率；
允许空间地址不连续分布于物理存储器上；
其核心实现包括：
① 请求分页操作系统
② 请求分段操作系统
③ 请求段页式操作系统
硬件基础：
在虚拟存储器模型中（VRM），页面被映射到物理存储器中的特定文件位置。
数据：使用数据文件保存
代码段：使用可执行二进制文件保存
动态加载的程序段：使用动态调用的库文件
分区：使用特殊的交换区存储
页表中增加若干项字段
状态位
驻留位：表示该页是否在内存中
保护位：表示页的类型（只读，读写，可执行）
修改位：表示页是否被写过（如果写过，需要把新的数据写回外存中）
访问位：表示页是否被访问过
锁定位：表示必须常驻内存的页
辅存地址
访问字段
地址变换机构增加了产生和处理缺页中断、置换页等功能
2. 过程
调入内存：当一个用户程序需要运行时只装入部分页面
缺页中断：当需要的页面不在内存中时会发生缺页中断，请求调页
页面置换：系统将外存的页面调入内存
3. 缺页中断（驻留位=0）：
状态位：
过程：
如果在内存中有空闲的物理页面，则不需要置换页面，直接分配一个物理页帧f，转向第4步
采用置换算法，选择一个被置换的页帧f，它对应的逻辑页为Q，如果该页被修改过，则需要写回外存。
对Q所对应的页表项进行修改，驻留位=0
将需要访问的页P装入到物理页帧f中
修改P对应的页表项的内容，驻留位=1，物理页帧号=W
重新运行中断的指令
4. 页面置换算法
目的：尽可能减少缺页中断的次数
定义：在操作系统内存管理中处于核心地位的页面，在需要时不会被调出到换页空间，并且允许其他非核心页面进入内存空间
工作集：进程所使用的动态分配的逻辑页面集合（通常位于内存中），其状态会根据系统的运行情况持续更新。
W(t, Δ)被定义为运行时间段内所有访问过的网页页码所组成的群体；其规模|W(t, Δ)|则表示该群体中包含的具体网页数量。而常驻集则指的是进程在其运行过程中始终保有的物理页面集合，在任何时刻都必定存在于内存空间中。
一旦常驻集规模达到特定阈值时,系统将不再遭遇明显的缺页问题。
假设工作集中的绝大多数页面位于常驻集中,则系统运行将保持稳定且无中断;当工作集出现波动时,这一特性仍能得以维持。
局部页面置换策略基于固定物理页框和基于局部性原则的设计。
（1）理想置换策略OPT
对每个特定的页面来说,在能够预见其未来访问需求的情况下,选择预期等待时间最长的那个页面进行替换。
（2）先进先出算法FIFO（队列）
定义：选择在内存中驻留时间最长的页面。
特点：
实现较为简便
特点：
缺页次数较少意味着系统运行效率较高。然而系统开销较大仍是一个亟待解决的问题。
（4）基于时钟/最近未使用过页面置换策略（NUR）采用循环链表实现
定义如下：
每当一个新的页面被加载到内存中时
访问标志位设为0；
将所有页面按照进入内存的先后顺序排列成一个循环链表结构；
首先检查当前指向的页面是否满足条件。
如果该页面已被访问过则将其访问标志位重置并向前移动一位。
随后选择当前最先进入内存但尚未被访问过的那个节点作为置换对象。
二次机会算法（修改时钟）
定义：通过机制避免频繁将脏页写回至主存区，并使时钟能够维持这些未被正确回收的脏页；随后移除那些专用地址对应的只读页。进而脏页有机会在被再次使用后被重新评估以决定是否需要替换
在选中页面中，在满足以下条件时执行相应操作：
当访问与修改均为0时直接淘汰当前页面；
当访问为0而修改为1时，将修改归零并向下移动一位（提供额外一次机会）；
当访问为1且修改为0时，则将当前页面的访问标志清零并下移一位；
当当前页面的两个标志均为1时，则将该页面的访问标志清零，并下移一位（提供两次额外机会）。
（6）最不常用算法LFU（计数器）
定义：选择访问次数最少的页
特点：
在一段时间过后可能不再使用（计数器可右移除2）
侧重于提高访问频率
基于最近使用原则
该算法特点遵循特定顺序
无法动态适应环境
无法实现完全的动态适应性
按照页面首次进入内存的时间进行替换，并保持固定顺序
通过硬件模拟的方式实现对页面访问时间的动态跟踪
综合考虑了页面外存访问时间和动态调整策略
侧重于根据页面访问频率进行替换，并保持固定的更新顺序
该全局置换算法关注的是物理页资源数量进行调整
工作集置换算法基于窗口大小限定策略筛选出最合适的工作集，并预留足够的空闲页以供新页面替换
缺页率置换算法PFF
定义：在发生中断时进行判断，并根据缺页率的变化动态地调节常驻集合的规模。具体而言，在缺页率过高时会增加常驻集合的数量，在缺页率过低的情况下则会减少其规模。
缺页率：缺页次数/内存访问次数
影响因素：
页面置换算法
分配到的物理页面数量
页面大小
程序的局部性
过程：
为了优化系统性能需要对内存管理策略进行动态调整为此我们引入了基于时间间隔T的内存管理机制该机制通过监控缺页事件的时间分布来实现资源的最佳配置具体来说当上一次与当前一次缺页事件的时间间隔T明显大于预先设定的窗口大小时系统将减少常驻集合以释放不必要的工作集从而移除在此时间段内未被引用过的页面内容反之当T小于等于窗口大小时则会增加常驻集合直接加载本次出现的缺失页面以满足当前的工作需求在性能评估方面我们采用如下计算模型有效访问时间为访存周期与页面命中率之积再加上由于页面缺失造成的额外开销即缺页率乘以访问磁盘时间和进一步考虑数据 writes带来的影响最终得到完整的性能评估公式
抖动问题：多次缺页中断，频繁换页，影响性能。需要有一个合适的常驻集
预期缺损页的替换时间为PFST；该系统中平均缺损页的数量等于预期缺损页的替换时间；该系统中平均缺损页的数量等于预期缺损页的替换时间；
系统的工作集内存容量根据配置参数动态调整以满足性能需求；
当前并行运行的应用程序数量决定了系统的负载能力；