文章目录
- 虚拟内存
- 请求分页管理方式
- 页面置换算法
- 最佳置换算法
- 工作原理
- OPT 算法的示例
- 最佳置换算法的优点和缺点
- 先进先出置换算法
- 最近最久未使用
- 时钟置换算法
- 时钟置换算法的工作原理:
- 算法的步骤:
- 改进型时钟置换算法
- 改进型时钟置换算法的特点:
- 常见的改进型时钟置换算法:
- **二位标志改进版**
- 页面分配
- 驻留集的定义:
- 驻留集分配的基本概念:
- 内存分配的抖动(颠簸)
- 驻留集管理的关键问题:
- 内存映射文件
- 内存映射文件的工作原理
- 内存映射文件的优点
虚拟内存
基于时间局限性和空间局限性,
多次性:无需在作业运行时一次性全部装入内存,而是允许被分成多次调入内存。
对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入换出。
虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量。
请求分页管理方式
访问的页面不存在,就会产生缺页中断(内中断)。有空闲块,则放进去,并修改页表项。没有空闲块,则需要淘汰一个空闲块。
虚拟内存请求分页结合了虚拟内存的概念和请求分页的机制,具体工作过程如下:
- 地址映射:每个进程拥有独立的页表,页表存储了虚拟地址到物理地址的映射关系。每次内存访问,虚拟地址会被转换成物理地址。
- 缺页中断处理:当页面不在内存中时,缺页中断被触发。操作系统查找缺页所在的页面,并将其从磁盘加载到内存中。
- 页面替换:当内存不足时,操作系统需要选择一个页面换出,以腾出空间供新的页面使用。操作系统使用特定的替换算法(如LRU、FIFO等)来管理页面的替换。
- 继续执行:页面加载完成后,操作系统更新页表,重新执行引发缺页的指令,进程继续运行。
页面置换算法
最佳置换算法
最佳置换算法(Optimal Page Replacement Algorithm,简称OPT)是一种理想化的页面替换算法,在缺页时选择将“未来最长时间不再被访问”的页面进行替换,从而使得系统的缺页次数最小。
工作原理
在最佳置换算法中,当发生缺页并且内存已满时,系统选择一个页面将其替换出内存。具体来说,最佳置换算法会执行以下步骤:
- 查看未来的页面访问顺序:分析当前内存中各个页面的未来访问情况。
- 选择最长时间不再被访问的页面:找到内存中未来最久不再被访问的页面,将其替换出去。
最佳置换算法的特点在于:在所有页面替换算法中,它能保证最小的缺页次数,因此是理论上的最佳方案。最佳置换算法是一个理论算法,因为它需要“预知未来”来确定页面的访问顺序,而实际系统中无法实现。
OPT 算法的示例
假设有一个内存容量为 3 页框的系统,页面访问序列如下:
7, 0, 1, 2, 0, 3, 0, 4
按照最佳置换算法的流程:
-
访问 7:内存为空,将 7 加入内存。当前内存:
[7]
-
访问 0:内存未满,将 0 加入内存。当前内存:
[7, 0]
-
访问 1:内存未满,将 1 加入内存。当前内存:
[7, 0, 1]
-
访问 2:内存已满,需要替换页面。查看未来访问情况:
- 7 最早被替换(不再访问),0、1 会更早被访问。
- 替换掉 7。当前内存:
[2, 0, 1]
-
访问 0:0 已在内存中,不发生缺页。当前内存:
[2, 0, 1]
-
访问 3:内存已满,需要替换页面。查看未来访问情况:
- 2 最早被访问,因此选择替换掉 2。
- 当前内存:
[3, 0, 1]
-
访问 0:0 已在内存中,不发生缺页。当前内存:
[3, 0, 1]
-
访问 4:内存已满,需要替换页面。查看未来访问情况:
- 3 不再被访问,1 和 0 仍有访问。
- 替换掉 3。当前内存:
[4, 0, 1]
最终内存中存储的页面为 [4, 0, 1]
。在该序列中,总共发生了 6 次缺页。
最佳置换算法的优点和缺点
- 缺页率最低:最佳置换算法理论上可以达到最低的缺页率,因为它能够“预知未来”并选择最优的替换方案。
- 不可实现性:最佳置换算法在实际系统中无法实现,因为实际系统无法提前知道程序的未来页面访问顺序。通常在操作系统中使用接近最佳置换算法的启发式算法(如 LRU)。
先进先出置换算法
先进来的先滚
但是会产生Belady异常,进程分配块数增大,缺页次数增加。
最近最久未使用
淘汰最近最久未使用的页面。性能很好,但是开销大
时钟置换算法
时钟置换算法(Clock Replacement Algorithm)是一种常用的页面置换算法,旨在模拟一种“环形缓冲区”机制来决定哪个页面需要被替换。它是一个类似于**最近最少使用(LRU)**算法的近似方法,但具有较低的开销。时钟算法是操作系统中页面管理的一种常用策略,尤其适用于硬件实现的页面替换。
时钟置换算法的工作原理:
时钟算法将页面管理看作一个圆形缓冲区,其中每个页面都标记一个位(称为“访问位”或“使用位”)。该位的作用是标记页面是否被访问过。时钟算法使用一个指针指向缓冲区中的当前页面,并按照时钟的方式循环访问这些页面。
算法的步骤:
-
初始化:
- 每个页面都有一个访问位,初始值为
0
(未被访问)。
- 每个页面都有一个访问位,初始值为
-
页面访问:
- 当程序请求一个页面时,首先检查该页面是否已经存在于页面缓冲区中。
- 如果页面已经在缓冲区中,则将该页面的访问位设置为
1
,表示该页面被访问过。 - 如果页面不在缓冲区中,则需要进行页面置换。
-
页面置换:
- 指针从当前页面开始顺时针逐个检查页面。
- 如果访问位是
1
,则将其设置为0
,表示该页面最近被访问过,但可以被替换;指针继续向下移动到下一个页面。 - 如果访问位是
0
,表示该页面在一段时间内没有被访问过,可以被替换。将当前页面替换成新的页面,并将指针指向下一个页面。 - 如果所有页面的访问位都是
1
,则开启第二轮查找,由于之前有清零操作,所以一定可以替换
-
循环继续:
- 一旦一个页面被替换,指针继续顺时针移动,进行下一轮检查。
改进型时钟置换算法
改进型时钟置换算法(Enhanced Clock Replacement Algorithm)会结合更多的标志位或使用其他策略,来使得页面替换更加智能,接近于**最近最少使用(LRU)**或其他更先进的算法。
改进型时钟置换算法的特点:
-
多位标志: 在传统时钟算法中,每个页面仅有一个“访问位”,而在改进型算法中,通常会引入多个标志位,比如:
- 访问位(Access bit): 标记页面是否被访问过。
- 修改位(Modified bit)或脏位(Dirty bit): 标记页面是否被修改过,如果被修改过,必须写回磁盘。
- 计数器: 用于记录页面被访问的次数,进一步模拟LRU。
-
页面访问频率: 通过引入访问频率或周期性更新计数器,使得替换算法可以更准确地选择最不常用的页面。
-
页面优先级: 在某些改进型时钟算法中,页面优先级可以与访问位结合,使得当多个页面都未被访问时,替换时能考虑页面的优先级。
常见的改进型时钟置换算法:
二位标志改进版
在传统时钟算法中,每个页面只有一个“访问位”,这意味着它只能记录页面是否被访问过。二位标志算法扩展了这一点,为每个页面增加两个标志位:
- 访问位(A)
- 修改位(M)
具体操作如下:
- 每次访问页面时,如果页面存在,设置其访问位为1。如果页面在内存中且被修改过,设置修改位为1。
- 如果需要替换页面,检查访问位和修改位:
- 如果访问位为0,说明该页面在一段时间内未被访问,可以被替换。
- 如果访问位为1,说明页面刚刚被访问过,可以将访问位重置为0,然后指针移动到下一个页面,继续检查。
- 如果访问位和修改位均为1,说明该页面被频繁访问且已被修改,需要优先考虑替换,但可能需要先将修改内容写回磁盘。
这种算法通过考虑修改位的情况,使得修改过的页面不容易被替换,避免了频繁写入磁盘,提高了效率。
总的来说,改进型时钟置换算法通过引入更多的状态信息和策略,提升了页面替换的效率和准确性,但在实现上会有一定的开销。它适用于对性能要求较高且页面访问模式复杂的系统。
页面分配
驻留集分配(Resident Set Allocation)是操作系统中的一种内存管理策略,用于控制在物理内存中驻留的页面集合。它决定了哪些页面可以保留在物理内存中,以及什么时候将页面换出或换入磁盘,以便程序能够高效运行。
驻留集的定义:
驻留集(Resident Set)指的是程序在物理内存中保持活跃的页面集合。操作系统通过驻留集管理来确保程序能够高效执行,同时避免频繁的页面交换操作(页面置换),从而减小**页面失效(Page Fault)**的开销。
驻留集分配的基本概念:
在现代操作系统中,物理内存是有限的,因此不可能将所有程序的页面都保持在物理内存中。驻留集分配的目标是根据程序的需求动态调整驻留集的大小,使得程序可以尽量不发生页面失效,或者减少页面置换的频率。
- 工作集模型(Working Set Model):
- 工作集模型提出了一个动态调整驻留集大小的概念。根据工作集模型,程序的驻留集大小应该根据其“工作集”的大小来调整。
- 工作集指的是程序在某段时间内频繁访问的页面集合。操作系统会通过监测程序访问的页面集合,动态调整驻留集,以保证程序的效率。
- 优点:根据程序实际的内存访问需求调整内存分配,有效减少页面失效率。
- 缺点:需要复杂的内存管理算法,增加了系统的管理开销。
内存分配的抖动(颠簸)现象是指在内存管理过程中,尤其是在动态内存分配和回收时,系统发生不规则、波动性高的内存分配和释放,导致内存使用效率不高或者内存管理的不稳定。这种现象常见于复杂系统中,当频繁地分配和释放内存时,可能会造成系统响应不稳定,甚至影响程序的执行性能。
内存分配的抖动(颠簸)
内存分配的抖动(颠簸)现象通常是由于频繁的内存分配和释放、内存碎片化、不高效的内存管理器等原因引起的。它可能导致系统性能下降、内存浪费以及程序不稳定等问题。解决这一问题可以通过使用内存池、优化内存分配算法、垃圾回收优化、延迟分配、批量分配等技术,从而提高内存管理的效率和稳定性,确保系统的高性能和稳定运行。
驻留集管理的关键问题:
驻留集的平衡:
驻留集的大小不仅需要考虑程序的内存需求,还要综合考虑系统中的其他程序的内存需求,避免过多的驻留集占用过多的物理内存,导致系统内存不足。需要考虑工作集实际访问页面的集合
内存映射文件
**内存映射文件(Memory-Mapped Files)**是一种将文件的内容直接映射到进程的虚拟内存空间中的技术。通过这种方式,操作系统允许程序像操作内存一样操作文件。内存映射文件通常用于高效地处理大文件,避免频繁的磁盘I/O操作,同时也能够让多个进程共享文件内容,提高数据交换效率。
内存映射文件的工作原理
内存映射文件通过操作系统的内存管理机制将一个文件的内容加载到进程的虚拟地址空间。这样,程序可以通过指针直接访问文件中的数据,而不需要显式地读取和写入文件。
-
映射过程:
操作系统为文件分配一块虚拟内存空间,并将文件的内容加载到这块内存区域。这一过程通常通过操作系统提供的系统调用(如mmap
)来实现。映射的文件内容会在需要时由操作系统自动加载到物理内存中,使用时无需显式地读取磁盘。 -
页面化机制:
内存映射文件的一个关键特点是采用页面(page)管理机制。当程序访问映射的内存区域时,如果该页面还没有加载到内存,操作系统会通过页面调度机制将相应的数据从磁盘加载到内存中。这种按需加载的方式大大提高了程序的效率。 -
修改文件内容:
对映射区域的修改会直接影响文件内容,因为映射区域实际上就是文件在虚拟内存中的映射。修改内存中的数据就像修改文件内容一样。操作系统会根据映射模式和内存管理策略,决定是否在修改时直接同步到磁盘。
内存映射文件的优点
-
高效的磁盘I/O:
内存映射文件允许程序直接通过内存访问文件内容,避免了传统的文件读取和写入操作中频繁的磁盘I/O。这使得访问大型文件时更加高效,尤其是对于随机访问或按需加载的场景。 -
内存共享:
内存映射文件可以让多个进程共享相同的文件映射区域。多个进程可以直接访问同一块内存区域,从而避免了通过进程间通信(IPC)传递数据的开销,尤其在处理大型数据时非常高效。
-
自动页面管理:
操作系统通过页面管理机制实现内存映射文件的按需加载,程序不需要自己管理文件的读取和写入,降低了内存和磁盘的管理复杂性。 -
数据一致性:
-
内存节省: