能做wordpress的网站,花都营销型网站,长沙h5手机网站制作,吸引人的软文操作系统#xff08;三#xff09;- 存储管理 1. 内存的基础知识1.1 存储单元与内存地址1.2 按字节编址和按字编址1.3 指令1.4 物理地址和逻辑地址1.5 从写程序到程序运行1.6 链接1.6.1 静态链接1.6.2 装入时动态链接1.6.3 运行时动态链接 1.7 装入1.7.1 概念1.7.2 绝对装入1… 操作系统三- 存储管理 1. 内存的基础知识1.1 存储单元与内存地址1.2 按字节编址和按字编址1.3 指令1.4 物理地址和逻辑地址1.5 从写程序到程序运行1.6 链接1.6.1 静态链接1.6.2 装入时动态链接1.6.3 运行时动态链接 1.7 装入1.7.1 概念1.7.2 绝对装入1.7.3 静态重定位1.7.4 动态重定位 2. 内存管理的概念3. 内存空间分配 - 连续分配3.1 单一连续分配3.2 固定分区分配3.3 动态分区分配3.3.1 首次适应3.3.2 最佳适应3.3.3 最坏适应3.3.4 邻近适应 4. 内存空间分配 - 非连续分配4.1 基本分页存储管理4.1.1 例题4.1.2 基本地址变换机构4.1.3 快表4.1.4 两级页表 4.2 基本分段存储管理4.2.1 段表4.2.2 分段、分页管理的对比 4.3 段页式存储管理4.3.1 分页和分段的优缺点分析 5. 内存空间的扩充5.1 覆盖技术5.2 交换技术5.3 虚拟内存技术5.3.1 传统存储管理方式的特征、缺点5.3.2 局部性原理5.3.3 虚拟内存的定义和特征5.3.4 如何实现虚拟内存技术5.3.5 请求分页管理方式**① 请求分页与基本分页的区别**② 请求页表机制③ 缺页中断机构④ 地址变换机构 5.3.6 页面置换算法5.3.7 页面分配策略、抖动、工作集5.3.8 内存映射文件 1. 内存的基础知识
内存Memory也称为主存储器或随机存取存储器RAM Random Access Memory是计算机系统中用于临时存储数据和程序的硬件。内存是计算机系统的核心组件之一其主要作用是在处理器执行任务时为其提供快速访问的数据存储空间。意思就是我们写好的程序在运行时必定会被先加载到内存中然后CPU从内存中拿取数据。
作用
存储正在使用的数据和程序 内存用于存储计算机当前正在运行的操作系统、应用程序以及这些程序所需要的数据。处理器可以快速访问这些数据从而实现高效的程序执行。 提高数据访问速度 相比硬盘等外部存储设备内存的读写速度要快得多。将数据从硬盘加载到内存后处理器可以更快速地访问这些数据减少延迟提高系统性能。 支持多任务处理 通过内存计算机可以同时运行多个程序如浏览器、文字处理器、音乐播放器等。操作系统会将每个程序的数据和状态存储在内存中以便快速切换和处理不同任务。 缓存数据 内存还可以用作缓存存储经常使用的数据和指令减少处理器从较慢的存储设备读取数据的次数从而进一步提升性能。 临时存储 内存用于存储临时数据像是正在编辑的文档、未保存的文件、以及中间计算结果等。当程序关闭或计算机关机时内存中的数据会被清空因为内存是易失性存储器。
特性
易失性Volatile 内存是易失性存储器这意味着当电源关闭时存储在内存中的数据将会丢失。这与硬盘等非易失性存储设备不同。高速性 内存的访问速度远快于硬盘等存储设备使得处理器可以更快地获取和处理数据从而提高整个系统的运行速度。
1.1 存储单元与内存地址
存储单元
概念存储单元是计算机内存中最小的存储单位用于存储一小部分数据。通常一个存储单元可以存储1个字节8位的数据但具体大小取决于计算机系统的设计。作用存储单元是内存的基本构成部分每个单元保存一个小的数据块。计算机通过访问这些存储单元来读写数据执行程序。
内存地址
概念内存地址是用于标识和定位特定存储单元的唯一编号。每个存储单元都有一个唯一的内存地址使得计算机能够精确地找到并访问存储在该单元中的数据。作用内存地址是访问内存中存储单元的桥梁。通过指定内存地址计算机能够读取或写入对应的存储单元中的数据。
存储单元与内存地址之间的联系
一一对应关系在内存中每个存储单元都有一个唯一的内存地址与之对应。这意味着一个存储单元的地址是它在内存中的位置标识符。内存可以被视为一组连续排列的存储单元每个单元按顺序编号每个编号就是内存地址。数据访问当计算机需要访问某个数据时CPU会通过内存地址找到对应的存储单元然后进行数据的读取或写入操作。内存地址的唯一性和存储单元的固定性使得数据访问过程准确无误。
举例说明
假设计算机内存有4个存储单元每个存储单元能够存储1个字节的数据
存储单元 单元0存储了字节数据 10101010单元1存储了字节数据 11001100单元2存储了字节数据 11110000单元3存储了字节数据 00001111 内存地址 单元0的地址为 0000单元1的地址为 0001单元2的地址为 0010单元3的地址为 0011
如果CPU需要读取存储在单元2中的数据它会使用地址 0010 来定位该存储单元从而读取到数据 11110000。
总结
存储单元是内存中实际保存数据的最小单元。内存地址是定位和访问存储单元的唯一标识符。
两者的联系在于每个存储单元都有一个对应的内存地址计算机通过内存地址访问存储单元中的数据这一机制使得数据存储和检索过程得以准确和高效地进行。
1.2 按字节编址和按字编址
按字节编址和按字编址是两种不同的内存地址表示方式它们决定了如何在内存中访问数据。下面是对这两个概念的详细解释
按字节编址Byte Addressing 概念按字节编址是指内存地址以字节为单位进行编号。每个内存地址对应一个字节的数据存储单元。 特点 每个内存地址只指向一个字节。内存地址从0开始依次递增且每个地址增加1表示访问下一个字节。这种方式常用于大多数现代计算机系统因为它支持对内存中的任意字节进行精确访问。 举例 假设有一个32位系统其中每个内存地址可以存储1个字节8位。如果有一个整型变量占4字节存储在内存地址 0x0000则其存储在内存中的位置如下 地址0x0000存储第1个字节地址0x0001存储第2个字节地址0x0002存储第3个字节地址0x0003存储第4个字节
按字编址Word Addressing 概念按字编址是指内存地址以字Word为单位进行编号。一个“字”通常由多个字节组成例如2个字节、4个字节或8个字节具体取决于系统的架构。 特点 每个内存地址指向一个“字”而不是一个字节。内存地址从0开始依次递增但每个地址增加1表示访问下一个“字”。这种方式在一些早期计算机系统或特定的嵌入式系统中使用较多。 举例 假设有一个16位系统其中每个内存地址存储1个“字”即2个字节。如果有两个字分别存储在内存地址 0x0000和0x0001则其存储在内存中的位置如下 地址0x0000存储第1个字由2个字节组成地址0x0001存储第2个字由2个字节组成
按字节编址与按字编址的区别 地址单位 按字节编址每个地址单位是1个字节。按字编址每个地址单位是1个“字”多个字节。 数据访问的粒度 按字节编址可以精确访问到每个字节适合处理较小的数据或字节级别的操作。按字编址只能访问到“字”级别适合于系统设计时将数据以“字”为基本操作单位的场景。 内存空间的表示 在按字节编址的系统中地址范围较大因为每个字节都有一个独立的地址。 在按字编址的系统中地址范围相对较小因为每个地址代表一个较大的数据块。
应用场景
按字节编址广泛应用于现代计算机系统中包括PC、服务器、智能手机等允许更灵活和精确的数据访问。按字编址通常应用在一些嵌入式系统或早期的计算机系统中在特定情况下可以简化系统设计和操作。
总结
按字节编址和按字编址是两种不同的内存寻址方式前者以字节为单位编址后者以“字”为单位编址。现代计算机通常采用按字节编址方式因为它更灵活、精确适应性更强。
1.3 指令
CPU指令通常以二进制格式表示可以由操作码和地址码组成。
操作码Opcode
操作码是指令中的部分用于指定CPU要执行的操作类型如算术运算、逻辑运算、数据传输等。操作码是指令中的一个字段通常是固定长度的二进制值代表特定的操作。
地址码Address Code
地址码是指令中的部分用于指定操作数所在的存储位置。地址码可能直接表示内存地址也可能是间接寻址模式下需要进一步计算的地址。在一些指令集架构中地址码也可能指定寄存器或其他存储位置。
可以看以下代码示例
int a 2,b3,c1,y0;
void main(){y a*bc
}以上代码在编译成机器码后可以假设为以下表格, 其中ACC为CPU中的寄存器不要太过于纠结。 可见我们写的代码要翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址读/写数据这个数据应该做什么样的处理。在这个例子中我们默认让这个进程的相关内容从地址#0开始连续存放指令中的地址参数直接给出了各个变量在主存中实际的物理存储地址。
1.4 物理地址和逻辑地址
物理地址Physical Address
定义物理地址是实际的内存地址用于标识内存中的具体位置。这是物理内存芯片上的地址用于访问内存中的字节、字或其他数据单元。
逻辑地址Logical Address
定义逻辑地址也称为虚拟地址是由CPU生成的地址用于访问内存中的数据。这个地址是程序看到的内存地址空间。
在上一小节简单了解了指令的工作原理有一个问题需要想想我们假设相关进程的内容在主存上是从#0开始存储的但是一台计算机上往往不会只运行一个进程如果是在分配以上程序的内存地址之前就有程序占据了#0到#8内存地址且此时程序已经编译好了意思就是指令就是上个例子中表格的指令了这些指令操作的内存地址我们称为逻辑地址那程序按照以上指令执行的话必然是不正确的。
怎么解决以上问题的我们继续往下看。
1.5 从写程序到程序运行 编译由编译程序将用户源代码编译成若干个目标模块(编译就是把高级语言翻译为机器语言)
链接由链接程序将编译后形成的一组目标模块以及所需库函数链接在一起形成一个完整的装入模块
装入(装载)由装入程序将装入模块装入内存运行
1.6 链接
1.6.1 静态链接
在程序运行之前先将各个目标模块以及它们所需的库函数链接成一个完整的可执行模块之后不再分开。 1.6.2 装入时动态链接
将各个目标模块装入内存时边装入边链接的链接方式。
1.6.3 运行时动态链接
运行时动态链接:在程序执行中需要该目标模块时才对它进行链接。其优点是便于修改和更新便于实现对目标模块的共享。 1.7 装入
1.7.1 概念
在操作系统中装入Loading 是指将程序从外部存储设备如硬盘加载到内存中准备执行的过程。装入是程序从静态文件变为可执行进程的关键步骤。
1.7.2 绝对装入
绝对装入Absolute Loading是操作系统的一种早期的装入技术。在绝对装入中程序的每条指令和数据都具有一个固定的、绝对的内存地址。装入器在装入程序时不需要进行地址重定位relocation直接将程序加载到预先指定的内存地址上。
特点
固定的内存地址 在绝对装入中程序在编译或汇编时已经确定了每条指令和数据的内存地址。这些地址在程序运行时保持不变。 无地址重定位 由于内存地址是固定的装入器不需要对程序进行地址重定位装入过程相对简单。 依赖特定的内存位置 绝对装入要求程序在一个特定的内存地址运行。如果内存中该地址已经被其他程序占用那么该程序无法被装入并执行。 编程复杂性 编写绝对装入程序需要对内存布局非常了解因为程序员需要手动指定每个部分的内存地址这使得程序开发和维护变得复杂。
缺点
灵活性差 绝对装入严重依赖程序的特定内存位置这导致程序无法在不同的内存位置运行限制了多任务操作系统的实现。 资源浪费 如果多个程序需要运行操作系统需要确保每个程序使用不同的内存地址这可能导致内存资源的浪费。 不适合现代系统 在现代操作系统中内存管理需要动态分配、地址重定位和虚拟内存技术绝对装入的固定地址机制不适合多任务、多用户和大内存环境。
使用场景
虽然绝对装入在现代操作系统中已经很少使用但它在一些特定场景下仍然可能出现
嵌入式系统 一些简单的嵌入式系统内存资源有限且不需要复杂的内存管理功能可能仍然使用绝对装入技术。 引导加载器Boot Loader 操作系统的引导加载器在启动时通常会使用绝对装入方式因为它需要在系统非常早期阶段将操作系统内核加载到内存中的特定位置。 早期计算机系统 在早期的计算机系统中绝对装入是主要的装入方式因为这些系统通常运行单一程序且内存资源有限。
1.7.3 静态重定位
静态重定位Static Relocation是一种在程序装入内存时进行地址重定位的技术。在静态重定位中程序的内存地址在装入时被一次性确定并在整个程序执行过程中保持不变。该技术通常用于早期的操作系统以及一些简单的嵌入式系统中。
工作原理
编译时生成相对地址 程序在编译或汇编时所有的指令和数据地址都是相对于程序起始地址相对地址的。这些相对地址在程序中被标记出来以便在装入时进行重定位。 装入时的地址重定位 当操作系统决定将程序装入内存时首先为程序选择一个合适的基地址即程序在内存中的起始位置。装入器根据这个基地址将程序中的所有相对地址与基地址相加生成实际的物理地址。这一过程称为静态地址重定位。 程序装入内存 完成重定位后操作系统将程序的代码和数据装入内存中相应的位置。由于地址已经固定程序在运行时无需再进行任何地址转换。
特点 一次性地址重定位 静态重定位在程序装入时只进行一次地址转换。所有相对地址在装入后都变成了绝对地址程序在运行过程中不再进行任何额外的地址转换。 内存地址固定 程序一旦装入内存地址在整个执行过程中保持不变。这意味着程序在同一时间内只能在一个特定的内存位置运行。 低运行时开销 由于地址转换仅在装入时进行静态重定位不会在程序运行过程中引入额外的开销。这使得静态重定位适用于对性能要求较高的系统。
优点
简单静态重定位技术相对简单容易实现和管理。低开销在程序运行时没有额外的地址转换开销执行效率高。适合小型系统对于不需要复杂内存管理的小型或嵌入式系统静态重定位是一个有效的选择。
缺点
灵活性差程序在装入后地址固定无法在不同内存位置运行限制了内存的利用效率。不支持动态内存分配静态重定位不适用于需要动态内存管理的复杂系统因为它不支持程序在运行时改变其内存地址。内存浪费当程序地址被固定后如果内存中的其他部分无法利用这可能导致内存浪费。
应用场景
早期操作系统 在早期的计算机操作系统中静态重定位是一种常见的技术因为当时的计算环境比较简单内存管理功能有限。 嵌入式系统 一些嵌入式系统由于硬件资源有限且不需要复杂的内存管理可能依然采用静态重定位。 单任务系统 在只需要运行单一任务的系统中静态重定位可以简化操作系统的设计和实现。
1.7.4 动态重定位
动态重定位Dynamic Relocation是一种在程序执行过程中进行地址重定位的技术允许程序在内存中随时移动并且支持更灵活的内存管理。动态重定位通过硬件如内存管理单元MMU和操作系统的协同作用来实现使得程序能够在不同的物理内存位置执行而无需进行重新装入。
工作原理
逻辑地址与物理地址的分离 程序使用逻辑地址或虚拟地址来引用内存位置这些地址在编译时生成。逻辑地址与实际的物理内存地址无关。动态重定位通过硬件设备如MMU将逻辑地址动态转换为物理地址使得程序可以在任何物理内存位置执行。 地址转换Address Translation 当程序访问内存时CPU首先生成逻辑地址然后通过动态重定位机制通常是分页或分段机制将逻辑地址映射到物理地址。这种映射是通过一个叫做页表Page Table或段表Segment Table的数据结构来完成的页表或段表记录了逻辑地址到物理地址的映射关系。 内存管理单元MMU MMU是实现动态重定位的关键硬件组件它在每次内存访问时将逻辑地址动态地转换为物理地址。这种转换是实时的并且对程序员透明。MMU支持分页、分段等机制使得内存管理更加灵活和高效。 支持虚拟内存 动态重定位通常与虚拟内存结合使用。虚拟内存允许程序的逻辑地址空间大于物理内存通过将不活跃的页面暂时交换到硬盘即页面置换来扩展内存容量。操作系统根据需要将页面调入和调出内存而动态重定位机制确保程序始终能正确访问其数据。
优点
灵活性高 程序可以在内存的任何位置运行操作系统可以根据当前内存使用情况动态分配和调整内存区域提高了内存的利用率。 支持多任务处理 多个程序可以共享相同的物理内存区域而每个程序都认为自己占有独立的地址空间。这使得操作系统能够高效地管理多任务环境。 支持虚拟内存 动态重定位与虚拟内存机制相结合可以使程序的地址空间大于实际物理内存从而支持运行更大的程序和更复杂的应用。 程序位置独立性 程序员不需要关心程序在内存中的具体位置操作系统会自动管理地址转换。这简化了编程和程序管理。
实现技术
分页Paging 分页是一种将内存分成固定大小的块页面的技术逻辑地址空间和物理地址空间都分成大小相等的页面。页面表维护着逻辑页面到物理页面的映射MMU根据页面表实时将逻辑地址转换为物理地址。 分段Segmentation 分段将程序分为多个段每个段表示程序的不同部分如代码段、数据段、堆栈段。每个段可以有不同的大小并且独立地映射到物理内存。段表记录每个段的基地址和大小MMU根据段表将逻辑地址转换为物理地址。 分页与分段结合 在复杂的内存管理系统中分页和分段可以结合使用既提供了段的逻辑分组又利用了分页的内存利用效率。
应用场景
现代操作系统 动态重定位是现代操作系统如Windows、Linux、macOS的核心技术支持多任务处理、虚拟内存管理等高级功能。 虚拟机和容器 虚拟机和容器技术利用动态重定位来隔离和管理虚拟环境中的内存使得多个虚拟机或容器能够共享物理硬件资源。 大规模分布式系统 在大规模分布式系统中动态重定位允许操作系统在不同的物理机器之间动态分配内存提高系统的灵活性和资源利用率。
2. 内存管理的概念
内存空间的分配与回收
内存空间的分配与回收是指在计算机程序运行过程中如何为数据提供存储空间分配以及在数据不再需要时释放这些存储空间回收的过程。这个过程是计算机系统管理内存资源的核心部分确保系统能够高效地使用内存并避免内存泄漏或耗尽内存资源。
内存空间的扩充
内存空间扩充的概念是指在计算机程序运行过程中当现有内存资源不够用时通过增加可用内存来满足程序的需求。内存扩充通常涉及操作系统和应用程序层面的机制以确保程序能够继续运行而不会因为内存不足而崩溃。内存空间扩充的常见方法覆盖技术、交换技术、虚拟内存技术
地址转换
地址转换通常指的是将虚拟地址转换为物理地址的过程。
内存保护
是操作系统提供的一项关键功能旨在防止一个进程访问、修改或破坏另一个进程的内存空间以及保护操作系统本身的内存空间。它确保每个进程只能访问自己分配的内存区域从而提高系统的安全性和稳定性。
3. 内存空间分配 - 连续分配
3.1 单一连续分配
单一连续分配Single Contiguous Allocation是早期操作系统内存管理的一种简单方法主要用于没有虚拟内存的计算机系统中。它的基本思想是将整个可用的内存分为两个部分一部分给操作系统另一部分给用户进程。用户进程的内存区域是连续的、单一的。
关键特点
单一用户进程: 在这种分配方式下内存中一次只能有一个用户进程运行。这个进程会占用除操作系统保留区域之外的所有剩余内存。 内存分区: 内存通常被分为两个部分操作系统驻留部分和用户程序驻留部分。操作系统部分通常位于内存的低地址区域而用户进程占用剩余的连续内存空间。 简单的内存管理: 内存分配和管理非常简单因为操作系统只需要处理一个用户进程的内存分配问题。内存分配的开始和结束都是连续的没有内存碎片问题。 缺点: 低效的内存利用: 由于一次只能有一个用户进程驻留在内存中这种方法无法充分利用系统的内存资源特别是在多任务系统中显得非常低效。内存浪费: 如果用户进程所需的内存远小于可用内存的大部分那么剩余的内存就会被浪费。没有保护机制: 在这种模型下用户进程可能会不小心或恶意地覆盖操作系统的内存区域导致系统崩溃。
实际应用
单一连续分配通常用于简单、早期的计算机系统例如一些早期的操作系统或嵌入式系统。这种方法几乎不再使用因为它不能支持现代操作系统的多任务和内存保护要求。
示例
假设系统内存为64KB其中8KB用于操作系统剩余的56KB用于单一的用户进程。当一个用户进程加载到内存时它会占用从地址8KB到64KB的所有空间。该进程运行时如果它需要更多的内存且超出56KB可能会导致内存溢出。
3.2 固定分区分配
固定分区分配Fixed Partition Allocation是早期内存管理的一种方法用于支持多任务环境中的内存分配。在这种方法中物理内存被划分成若干个固定大小的分区每个分区可以容纳一个进程。该方法的目标是通过允许多个进程同时驻留在内存中来提高系统的利用率。 操作系统需要建立一个数据结构–分区说明表来实现各个分区的分配与回收。每个表项对应一个分区通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)。当某用户程序要装入内存时由操作系统内核程序根据用户程序大小检索该表从中找到一个能满足大小的、未分配的分区将之分配给该程序然后修改状态为“已分配”。 关键特点
内存分区: 物理内存被划分为若干个固定大小的分区每个分区大小是预先定义的。这些分区可以是相同大小也可以是不同大小。 单进程/分区: 每个分区一次只能容纳一个进程即一个进程分配到一个固定分区。当进程终止或被换出时分区会被释放可以用于其他进程。 内存分配的简单性: 由于分区大小固定内存分配比较简单。当一个进程需要加载到内存中时操作系统会在可用的分区中找到一个大小合适的分区分配给它。 内存浪费内部碎片: 由于分区大小固定如果进程所需的内存小于分区大小剩余的内存就会被浪费这种情况称为“内部碎片”。例如一个100KB的分区中如果进程只需要80KB那么剩下的20KB将无法使用造成内存浪费。 分区数量的限制: 分区数量是固定的意味着系统能同时驻留的进程数也是有限的。如果所有分区都被占用新进程只能等待直到有分区被释放。 不灵活性: 固定分区分配的灵活性较差因为分区大小和数量在系统启动时就已经确定一旦设置就无法改变。这使得系统难以应对动态变化的负载需求。
示例
假设有一台计算机的内存大小为1024KB操作系统预留了128KB剩下的896KB被划分为4个固定分区每个分区大小为224KB。
分区1: 224KB分区2: 224KB分区3: 224KB分区4: 224KB
当一个进程A需要加载时如果它的大小为180KB它会被分配到一个224KB的分区中剩余的44KB将形成内部碎片不能用于其他进程。
优缺点总结
优点: 分区管理简单容易实现。允许多个进程并发运行提高了内存利用率。 缺点: 内部碎片问题可能会导致内存浪费。不灵活无法动态调整分区大小可能无法有效利用内存资源。分区数量固定限制了同时运行的进程数量。
3.3 动态分区分配
这种分配方式不会预先给进程分配内存而是根据进程所需内存的大小来建立分区使得分区的大小正好适合进程的需要。因此系统的分区的大小和多少是可变的。(eg假设某计算机内存大小为64MB系统区 8MB用户区共 56MB…)
一、 系统要用什么样的数据结构记录内存的使用情况?
两种常用的数据结构空闲分区表和空闲分区链 空闲分区表 每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息 空闲分区链 主要分以下部分组成 分区起始地址: 每个节点或条目通常包含一个指向空闲分区起始地址的指针。这使得操作系统能够快速找到和访问空闲内存块。 分区大小: 除了起始地址链表中的每个节点还可能包含分区的大小信息。这有助于操作系统决定哪个空闲块可以满足当前的内存请求。 链表节点: 每个节点包含指向下一个空闲分区的指针。通过这些指针操作系统可以遍历整个链表找到合适的空闲分区。
二、当很多个空闲分区都能满足需求时应该选择哪个分区进行分配? 假如现在有一个进程5需要4MB的内存空间。应该用最大的分区进行分配?还是用最小的分区进行分配?又或是用地址最低的部分进行分配?
把一个新作业装入内存时须按照一定的动态分区分配算法从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响因此人们对它进行了广泛的研究。分为四种分区算法首次适应、最佳适应、最坏适应、邻近适应具体是怎样实现的可以继续往下看。
三、如何进行分区的分配与回收操作? 分配 假设我们现在使用的是空闲分区表来记录内存的空闲情况 假设现在有一个新的进程需要4MB 且使用的是首次适应的算法那结果将会如下。 假设现在有一个新的进程需要4MB 且使用的是最佳适应的算法那结果将会如下。 回收(如下四种情况)
3.3.1 首次适应
工作原理
内存空闲块列表: 操作系统维护一个内存空闲块列表这些空闲块代表可以分配的连续内存区域。空闲块通常按地址顺序排列。分配内存: 当一个新进程请求内存时操作系统从空闲块列表的开始位置遍历寻找第一个能够容纳该进程的内存块。一旦找到合适的空闲块操作系统就将这个块划分为两个部分一部分分配给进程另一部分保留为新的空闲块如果分配后有剩余空间。该进程占用的内存块从空闲块列表中移除或调整其大小以反映新的空闲区域。 释放内存: 当进程结束时操作系统将其占用的内存块重新标记为空闲并将其合并到空闲块列表中。如果释放的内存块与现有的空闲块相邻则系统会将这些块合并成一个更大的空闲块。
优点
简单性: 首次适应算法容易实现因为它只需要顺序遍历空闲块列表即可找到适合的内存块。快速响应: 因为它通常会很快找到合适的内存块因此能够快速响应内存请求。
缺点
外部碎片: 首次适应可能会导致外部碎片即许多小的、无法使用的内存空洞因为它倾向于选择靠前的空闲块。性能问题: 由于每次分配内存时都需要从头遍历空闲块列表在空闲块列表很长时可能会导致性能下降。
在动态分区分配的首次适应算法中适应性指的是系统对内存需求变化的响应能力。由于算法总是从头开始寻找可用块因此它能够快速适应简单的需求变化但在长期运行时可能需要配合其他碎片整理策略以减少外部碎片对系统性能的影响。
3.3.2 最佳适应
算法思想:由于动态分区分配是一种连续分配方式为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间可以尽可能多地留下大片的空闲区即优先使用更小的空闲区。
如何实现:
工作原理
内存空闲块列表: 操作系统维护一个按大小排序通常是按升序的内存空闲块列表。每个空闲块代表一个可供分配的连续内存区域。分配内存: 当一个进程请求内存时操作系统会遍历整个空闲块列表寻找能够容纳该进程的最小空闲块。找到最适合的空闲块后将该块分配给进程并更新空闲块列表。分配后的剩余空间如果有将作为一个新的空闲块继续保留在列表中。 释放内存: 当进程释放内存时操作系统将其占用的内存重新标记为空闲并将其合并到空闲块列表中。如果释放的内存块与相邻的空闲块接壤则操作系统会将它们合并成一个更大的空闲块。
优点
减少外部碎片: 通过选择最适合的空闲块最佳适应算法能够最大限度地减少未使用的小内存空洞减少外部碎片的产生。提高内存利用率: 该算法有助于在内存使用时更加精确避免较大的空闲块被小进程占用从而提高整体内存的利用率。
缺点
算法复杂度较高: 由于需要遍历整个空闲块列表以找到最适合的块最佳适应算法比首次适应算法的开销更大尤其是在内存请求频繁的情况下。分配效率较低: 在进行内存分配时可能会花费较多时间在查找最适合的空闲块上从而导致分配效率较低。小碎片积累: 尽管最佳适应算法旨在减少外部碎片但它可能会导致很多小碎片积累在内存的不同区域这些碎片可能在将来无法有效利用。
适用场景
最佳适应算法适用于内存资源紧张且碎片管理要求较高的场景。在这些场景中通过精确分配内存块可以有效减少碎片提高内存利用率但同时需要接受分配和释放内存时可能产生的性能开销。
3.3.3 最坏适应
工作原理
内存空闲块列表: 操作系统维护一个内存空闲块列表通常按块大小降序排列。列表中的每个条目代表一个连续的空闲内存区域。分配内存: 当进程请求内存时操作系统会遍历空闲块列表选择其中最大的空闲块来分配给进程。将该空闲块分成两部分一部分分配给进程另一部分如果有剩余空间作为新的空闲块保留在列表中。 释放内存: 当进程结束并释放其占用的内存时操作系统将该内存块标记为空闲并将其插入到空闲块列表中。如果释放的内存块与相邻的空闲块接壤操作系统会将它们合并成一个更大的空闲块。
优点
减少小碎片: 最坏适应算法将内存请求分配到最大的空闲块中这样剩余的空闲块更大减少了产生无法使用的小碎片的可能性。简单实现: 算法的实现较为简单只需要找到最大的空闲块进行分配适用于列表较短的情况。
缺点
可能导致较大的内存碎片: 因为它总是将进程分配到最大的空闲块剩余的部分可能会很大且在之后的内存分配过程中可能无法被有效利用。降低内存利用率: 在高负载情况下大块内存被分割成多个小块可能导致内存利用率的降低。
适用场景
最坏适应算法通常适用于需要将小碎片集中到少数大块中的场景。它的目标是避免频繁产生的小碎片但在内存需求复杂或多变的场景中可能不太理想。
3.3.4 邻近适应
邻近适应算法Next Fit是动态分区分配内存管理中的一种算法类似于首次适应算法First Fit但它在处理连续的内存分配请求时有一个关键的不同之处它不是从空闲块列表的开头开始搜索而是从上一次分配结束的位置继续向前搜索。
工作原理
内存空闲块列表: 操作系统维护一个空闲块列表这些空闲块代表可供分配的连续内存区域。分配内存: 当进程请求内存时邻近适应算法从上一次内存分配结束的位置开始搜索下一个适合的空闲块。它会沿着空闲块列表依次检查直到找到一个足够大的空闲块来容纳进程。如果找到则分配内存块如果列表走到末尾而未找到合适的空闲块则从头开始继续搜索。一旦找到合适的空闲块将其分配给进程剩余部分如果有将作为新的空闲块保留在列表中。 释放内存: 当进程结束并释放内存时操作系统将其占用的内存重新标记为空闲并尝试将其与相邻的空闲块合并更新空闲块列表。
优点
减少碎片化: 由于邻近适应算法不会总是从列表的开头开始搜索而是从上一次分配的位置继续这可以有效避免反复分配和释放导致的集中碎片化问题。提高分配效率: 与首次适应算法相比邻近适应算法在分配连续内存请求时效率较高因为它避免了每次分配都从头遍历列表的情况。
缺点
外部碎片问题: 尽管邻近适应算法能够避免部分碎片化问题但随着时间推移仍可能导致外部碎片尤其是在内存请求频繁变化的情况下。低效分配: 如果分配点处于列表末尾且空闲块无法满足请求则需要回到列表开头重新遍历可能导致分配效率降低。
适用场景
邻近适应算法适用于需要频繁连续内存分配的场景在这种情况下它比首次适应算法能更有效地利用内存资源。它在一些特定的高频内存分配场景下表现优异。 4. 内存空间分配 - 非连续分配
为用户进程分配的是一些分散的内存空间。
4.1 基本分页存储管理
分页存储是一种内存管理技术用于将计算机的物理内存和虚拟内存结合使用以更有效地管理内存资源。它通过将程序的虚拟地址空间分割成固定大小的块称为页page然后将这些页映射到物理内存中的物理页框page frame上。分页存储的主要目的是通过虚拟内存来支持程序所需的更大地址空间并提高内存使用效率。
页框和页框号
将实际的物理内存空间分为一个个大小相等的分区每一个分区就位一个“页框”每个页框都会有一个编号即页框号页框号从0开始编号。
页页面和页号
将进程的逻辑地址空间也分为和页框大小相等的小块每一个小块我们称之为“页”或者“页面”。每个页面都会有一个编号我们称之为页号。页号也是从0开始编号的。
页框号和页号
从逻辑角度来看无论是物理内存空间还是进程的逻辑地址空间都可以类比为一个数组结构。而页框号和页号就像是数组的下标。所以操作系统中的页框号和页号都是逻辑上的概念而不是在实际物理内存中存储的值。
页表和页表项
操作系统以页框为单位为各个进程分配内存空间进程的每个页面分别放入一个页框中。并且进程中各个页面在实际内存中连续存放也就是说进程的页面与内存的页框是有一一对应的映射关系的用来存储此关系的结构我们称之为页表。而其中一条条映射关系我们可以理解为一个个页表项。关于页表和页表项有以下需要注意的几点。
一个进程都会对应一张页表。页表不是直接存储在PCB进程控制块中而是存储在内存中的某个位置PCB 中只保存页表的指针或地址一级页表通常需要存储在连续的内存空间中因为它通常实现为一个线性数组。进程中的每个页号都会对应页表中的一个页表项。一级页表中虽然在逻辑意义每个页表项会有页号和页框号的映射关系实际内存中的页表是一个线性数组而页号恰巧可以使用数组的下标来表示所以内存中页表中的页表项只存储一个线性的页框号就可以了。在一个进程中页号通常都是从0开始的但是并不代表一个进程的逻辑地址是从0开始的。在这里我们先不展开讲。 4.1.1 例题
问题1
假设操作系统按照字节编址物理内存大小为4GB页面大小为4KB则每一个页表项占用多少字节假设进程A占用的内存空间大小为16MB则其页表占用的内存空间大小是多少
先求出物理内存总共分为多少个页框4GB ÷ 4KB 232 / 212 220即总共220个页框。要表示 220页框至少需要 20 个比特位。因为 20 个比特位可以产生220 种不同的组合对应于每个页框的唯一地址。且页框和页面大小肯定是相等的则每个页表项需要足够的位数来表示 20 位的物理页框号且计算机是按照字节编址的。所以20除以8向上取整就为3。即3个字节所以每个页表项至少占用3个字节。求出进程A总共分为多少个页表项。16MB ÷ 4KB 224 / 212 212即总共212个页面。一个页面对应一个页表项则进程A对应的页表项的数量为212个根据页表项的数量和一个页表项占用的字节可以求出页表大小。212 x 3B 12KB。
问题2
将进程逻辑地址空间分页后操作系统如何实现逻辑地址到物理地址之间的转换呢
比如已知操作系统按照字节编址进程的逻辑起始地址为1024每个页面的大小为4KB页表如下图请计算逻辑地址为14565的实际内存地址为多少 因为进程的逻辑起始地址为1024所以进程逻辑地址14565在计算页号时候需要减去1024得到地址13541我们需要根据逻辑地址13541计算页号。系统按照字节编址且页面大小为4KB每个页面会有 4 x 210 4096 个内存地址。那逻辑地址13541对应第 13541/4096 3 个页面即页号为2页内偏移量为 13541 % 4096 1253根据页表我们可以知道页号为2对应的页框号为4那么物理内存地址 页框号 × 每个页面的有多少个内存地址 偏移量 即4×40961253 17637。
结论1
页号 逻辑地址/页面大小即取整。
页面偏移量 逻辑地址 % 页面大小即取整。
页框号 需根据页表和页号查找。
页框内偏移量 页内偏移量。
物理地址 页框号 * 页面大小 页内偏移量。
结论2
在计算机内部地址是用二进制表示的如果页面大小 刚好是2的整数幂则计算机硬件可以很快速的把逻辑地址拆分成(页号页内偏移量)。
假设某计算机用32 个二进制位表示逻辑地址页面大小为4KB 4096B。
0号页的逻辑地址范围应该是 0~4095用二进制表示应该是
00000000000000000000 000000000000 ~ 00000000000000000000 111111111111
1号页的逻辑地址范围应该是 4096~8191用二进制表示应该是
00000000000000000001 000000000000 ~ 00000000000000000001 111111111111
2号页的逻辑地址范围应该是 8192~12287用二进制表示应该是
00000000000000000010 000000000000 ~ 00000000000000000010 111111111111
例1
逻辑地址2用二进制表示应该是 00000000000000000000 000000000010
页号2/4096 0 00000000000000000000页内偏移量 2%4096 2 000000000010
例2
逻辑地址4097用二进制表示应该是 00000000000000000001 000000000001
页号4097/4096 1 00000000000000000001页内偏移量 4097%4096 1 000000000001
总结如果每个页面大小为2KB用二进制数表示逻辑地址则末尾K位即为页内偏移量其余部分就是页号。
结论3
假设物理内存的地址也是用32个二进制位表示由于内存块的大小页面大小因此
0号页框的起始地址是00000000000000000000 000000000000
1号页框的起始地址是00000000000000000001 000000000000
2号页框的起始地址是00000000000000000010 000000000000
3号页框的起始地址是00000000000000000011 000000000000
假设通过查询页表得知1号页面存放的内存块号是9(1001)则9号内存块的起始地址9*409600000000000000001001000000000000则逻辑地址4097对应的物理地址页面在内存中存放的起始地址页内偏移量(00000000000000001001000000000001)。
总结如果页面大小刚好是2的整数幂则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址。
妈的真是天才。
结论4
页面大小是2的整数幂的好处是什么
逻辑地址拆分的就更加迅速。如果页面大小为2K用二进制位表示逻辑地址那么用末尾的K位即可表示页内偏移量其余的部分就是页号。这样就不必进行逻辑运算从而提升了运行速度。
物理地址计算的就更加迅速。在上面我们已经得到了页号和页内偏移量了所以我们只需要根据页号在页表中找到对应的页框号然后将页框号和页内偏移量拼接在一起就可以得到一个实际的物理地址了。
4.1.2 基本地址变换机构
基本地址变换机构Basic Address Translation Mechanism通常指的就是内存管理单元MMU Memory Management Unit。
基本地址变换机构可以将进程的逻辑地址转换为内存中的物理地址。
通常会在系统中设置一个页表寄存器PTR存放页表在内存中的起始地址F和页表长度M。
进程未被调度时候页表的起始地址和页表长度会被存储在进程的PCB中。当进程被调度时操作系统内核会把它们放在页表寄存器中。
案例1
设页面大小是L且是2的整数幂。逻辑地址A到物理地址E的变换过程如下。
①计算页号P和页内偏移量W( 如果用十进制数手算则 PA/LWA%L但是在计算机实际运行时逻辑地址结构是固定不变的因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量。
②比较页号P和页表长度M若P≥M则产生越界中断否则继续执行。注意页号是从0开始的而页表长度至少是1因此PM 时也会越界。
③页表中页号P对应的页表项地址 页表起始地址F 页号P * 页表项长度取出该页表项中的内容b即为页框号。
④计算 E b*LW用得到的物理地址E 去访存。 案例2
例若页面大小为 1KB页号2对应的页框号为8将逻辑地址 2500 转换为物理地址。
①计算页号、页内偏移量。页号 2500/10242页内偏移量 2500%1024 452
②根据题中条件可知页号2没有越界其存放的页框号为8
③物理地址 8 * 1024 425 8644
案例3
假设操作系统按照字节编址物理内存大小为4GB页面大小为4KB总共有220个页框每个页表项的大小至少为3B。各个页表项会连续的存放在内存中如果该页表在内存中的起始地址为X则M号页对应的页表项是存放在内存地址为X3*M。
一个页面的大小为4KB则每一个页面可以存放4096/3 1365个页表项但是这个页面会剩余4096%3 1B的内部内存碎片。
4.1.3 快表
快表又称联想寄存器 (TLB translation lookaside buffer是一种访问速度比内存快很多的高速缓存TLB不是内存用来存放最近访问的页表项的副本可以加速地址变换的速度。与此对应内存中的页表常称为慢表。
虽然快表的访问速度很快但是高速缓存很贵所以是不能将整个快表都放在高速缓存中的。 案例1 CPU给出逻辑地址由某个硬件算得页号、页内偏移量将页号与快表中的所有页号进行比较。如果找到匹配的页号说明要访问的页表项在快表中有副本则直接从中取出该页对应的内存块号再将内存块号与页内偏移量拼接形成物理地址最后访问该物理地址对应的内存单元。因此若快表命中则访问某个逻辑地址仅需一次访存即可。如果没有找到匹配的页号则需要访问内存中的页表找到对应页表项得到页面存放的内存块号再将内存块号与页内偏移量拼接形成物理地址最后访问该物理地址对应的内存单元。因此若快表未命中则访问某个逻辑地址需要两次访存注意在找到页表项后应同时将其存入快表以便后面可能的再次访问。但若快表已满则必须按照一定的算法对旧的页表项进行替换。
案例2
例某系统使用基本分页存储管理并采用了具有快表的地址变换机构。访问一次快表耗时 1us访问一次内存耗时 100us。 若快表的命中率为 90%那么访问一个逻辑地址的平均耗时是多少
(1100) * 0.9 (1100100) * 0.1 111us
有的系统支持快表和慢表同时查询那就是另一种结果了
(1100) * 0.9 (100100) * 0.1 110.9us
若未采用快表机制访问内存中的数据需要
100 100 200us
以下是左图是不支持快表和慢表同时查询右图是支持 快表和慢表同时查询
基本地址变换机构和具有快表的地址变换机构的区别 4.1.4 两级页表
单级页表中存在什么问题
假设某计算机系统按字节寻址支持32位的逻辑地址采用分页存储管理页面大小为4KB页表项长度为 4B。
因为页面大小为4KB即212B所以页内地址需要用12位表示剩下的20位可以用来可以表示页号。那么用户进程最多有220个页面。相应的一个进程对应的页表中也会有220个页表项所以页表需要一块220 * 4B 222 B的连续的内存来存储该页表也就需要连续的222B / 212B 210 个页框存储该页表。这显然违背了我们离散型存储的思想。根据局部性原理可知很多时候进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。
根据以上案例我们可以总结出以下问题
问题一页表必须连续存放因此当页表很大时需要占用很多个连续的页框。
问题一我们可以考虑将长长的页表进行分组使每个页框刚好可以放入一个分组。因此每1K个连续的页表项为一组每组刚好占一个内存块再将各组离散地放到各个内存块中
另外要为离散的表再创建一张页表称为页目录表或称为外层页表。 例题
在多级页表中当某一级的页表大小超过一个页面时该级页表也会被分页管理需要进一步进行分页处理。
某系统按照字节编址采用40位逻辑地址页面大小为4KB页表项大小为4B假设采用纯页式存储则页内偏移量为多少位需要采用几级页表 因为页内偏移量表示的是一个页面内的地址范围既然页面大小为 4KB那么从0到 212−1 的字节地址都在同一个页面内。用二进制来表示这个范围需要 12 位。 40位逻辑地址可以代表240B的内存空间一个页面大小为4KB 212B那么总共需要分为240B / 212B 228 页即页表中页表项总共有228个即页表总共需要28位表示。而当某一级的页表大小超过一个页面时也需要进一步进行分页处理则每个页面的页表项数量 页面大小 / 页表项大小 4KB / 4B 210 个则证明每级页表最多只能用10位表示。页表总共需要位数(28) ÷ 每级页表最多能使用位数(10) 页表级数(2.8)。即共需要三级页表一级为8位二级为10位三级为10位。大致如下图。
4.2 基本分段存储管理
进程的地址空间按照程序自身的逻辑关系划分为若干个段每个段都有一个段名在低级语言中程序员使用段名来编程每段从0开始编址。
内存分配规则以段为单位进行分配每个段在内存中占据连续的内存空间但各段之间可以不相邻。
优点按照逻辑功能模块划分用户编程更方便程序的可读性高。
分段系统的逻辑地址结构段名由段号和段内地址段内偏移量组成。
段号的位数决定了每个进程最多可以分为多少段。 段内地址的位数决定了每个段的最大长度是多少。
在上图中若系统是按照字节寻址的则段号占16位因此在该系统中每个进程最多有216 64K个段。
段内地址占16位因此每个段的最大长度是216 64KB。
4.2.1 段表
程序分为多个段各段离散的装入内存为了保证程序能够正常有序的执行就必须能从物理内存中找到各个逻辑段的位置。为此需要为每个进程建立一张段映射表简称段表。
每个段对应一个段表项其中记录了每个段的段长每个段在内存中的起始位置基址。各个段表项的长度是相同的。例如在某系统按照字节寻址内存采用分段式管理。逻辑结构为段号占用16位段内地址占用16位因此需要用16位表示段长。若系统的物理内存为4GB则需要用32位表示基址。因此每个段表项占用1632 48位即6B。由于段表项的长度是相同的所以段号是可以隐藏的不占用内存空间。若段表存放的起始地址为M则K号段对应的段表项存放的地址为M6*K。
寻址过程 4.2.2 分段、分页管理的对比
页是信息的物理单位。分页的主要目的是为了实现离散分配提高内存利用率。分页管理是系统上的需要完全是系统行为对用户是不可见的。
段是信息的逻辑单位。分段的目的主要是为了满足用户的需求。一个段通常包含着一组属于一个逻辑模块的信息。分段是对用户可见的用户编程时需要显示的给出段名。
页的大小固定且由系统决定。段的长度却不固定决定于用户编写的程序
分页的用户进程地址空间是一维的程序员只需给出一个记忆符即可表示一个地址。
分页的用户进程地址空间是二维的程序员在标识一个地址时既要给出段名又要给出段内地址。
分段比分页更容易实现内存共享和保护
不能被修改的代码称为纯代码或可重入代码。这样的代码是可以共享的。可以修改的代码或者可以说是资源是不能共享的比如代码中有很多的变量各个进程并发的同时访问可能会造成数据的不一致。
需要几次访存
分页(单级页表)第一次访存–查内存中的页表第二次访存–访问目标内存单元。总共两次访存
分段第一次访存查内存中的段表第二次访存–访问目标内存单元。总共两次访存
与分页系统类似分段系统中也可以引入快表机构将近期访问过的段表项放到快表中这样可以少一次访问加快地址变换速度。
4.3 段页式存储管理
4.3.1 分页和分段的优缺点分析 段页式管理 段号的位数决定了进程最多可以分为多少段。
页号的位数决定了每个段最大有多少页。
页内偏移量决定了页面的大小页框的大小。 在上述例子中若系统是按照字节寻址的段号占用16位因此在该系统中每个进程最多有216个段。
页号占用4位则每个段最多有24个页面。
页内偏移量占用12位因此每个页面的大小为212 B4KB。 5. 内存空间的扩充
内存空间扩充的概念是指在计算机程序运行过程中当现有内存资源不够用时通过增加可用内存来满足程序的需求。内存扩充通常涉及操作系统和应用程序层面的机制以确保程序能够继续运行而不会因为内存不足而崩溃。
内存空间扩充的常见方法覆盖技术、交换技术、虚拟内存技术
5.1 覆盖技术
覆盖技术的核心思想是将程序分成多个模块或段这些模块在运行时根据需要加载到内存中而不是一次性将整个程序加载到内存。通过在内存中动态地加载和卸载这些模块操作系统可以在有限的内存空间中执行较大的程序。
早期的计算机内存很小比如IBM推出的第一台PC机最大只支持1MB大小的内存。因此经常会出现内存大小不够的情况。
后来人们引入了覆盖技术用来解决“程序大小超过物理内存总和”的问题。
覆盖技术的思想将程序分为多个段常用的段常驻内存不常用的段在需要时调入内存。
需要常驻内存的段放在固定区调入后就不再调出除非运行结束。
不常驻内存的段放在覆盖区需要用到时调入内存用不到时调出内存。 缺点
必须由程序员声明覆盖结构操作系统完成自动覆盖对用户不透明增加了用户变成负担。覆盖技术只用于早期的操作系统已经成为历史。
5.2 交换技术
内存空间紧张时系统将内存中某些进程暂时换出到外村把外存中某些已经具备运行条件的进程换入到内存进程在内存和磁盘之间动态调度。比如一些交互式的进程优先级要高于后台批处理进程这种情况就可以把批处理进程暂时换出到外存并将其PCB放在挂起队列中把外存中处于可运行的交互式进程换入内存。 应该在磁盘的什么位置保存被换出的进程 具有对换功能的操作系统中通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件主要追求存储空间的利用率因此对文件区空间的管理采用离散分配方式对换区空间只占磁盘空间的小部分被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度因此对换区空间的管理主要追求换入换出速度因此通常对换区采用连续分配方式学过文件管理章节后即可理解。总之对换区的I/O速度比文件区的更快。 什么时候应该交换 交换通常在许多进程运行且内存吃紧时进行而系统负荷降低就暂停。例如在发现许多进程运行时经常发生缺页就说明内存紧张此时可以换出一些进程如果缺页率明显下降就可以暂停换出。 应该换出哪些进程 可优先换出阻塞进程可换出优先级低的进程为了防止优先级低的进程在被调入内存后很快又被换出有的系统还会考虑进程在内存的驻留时间。
5.3 虚拟内存技术
虚拟内存技术是一种内存管理机制使操作系统能够为每个进程提供一个连续的虚拟地址空间而不必与物理内存的实际布局严格对应。虚拟内存技术允许程序运行时使用的内存地址与实际物理内存地址分离从而提供了更高的内存管理灵活性和程序隔离性。虚拟内存技术为每个进程提供一个独立的虚拟地址空间。这些虚拟地址空间的大小通常远大于物理内存的实际容量。例如一个程序可以有一个4GB的虚拟地址空间即使系统的实际物理内存只有2GB。虚拟地址空间的大小取决于操作系统和硬件架构的支持。
5.3.1 传统存储管理方式的特征、缺点 一次性
作业必须一次性全部装入内存后才能开始运行。这会造成两个问题1、作业很大时不能全部装入内存导致大作业无法运行。2、当大量作业要求运行时由于内存无法容纳所有的作业因此只有少量作业才能运行导致多道程序并发度下降。
驻留性
一旦作业调入内存后将一直驻留在内存直至作业运行结束。事实上在一个时间段内只需要访问作业的一小部分数据即可正常运行。这就导致了内存中会驻留大量的暂时用不到数据。导致了内存空间的浪费。
而以上问题都是可以通过虚拟内存技术进行解决的。
5.3.2 局部性原理 时间局部性 如果系统执行了程序中的某段代码或者某条指令那么在不久后这条指令或者这段代码很有可能会再次执行如果数据被访问过不久后该数据很可能会再次被访问。因为代码中存在着大量的循环 空间局部性 一旦程序访问了某个存储单元在不久后其附近的存储单元也很有可能被访问。因为程序中很多数据在内存中都是连续存放的并且程序的指令也是顺序的在内存中存放的。
5.3.3 虚拟内存的定义和特征
基于局部性原理在程序装入时可以将程序中很快会用到的部分装入内存暂时用不到的部分装到外存这样并不需要将程序的所有的数据装入到内存才能执行。
在程序执行过程中当访问的信息不再内存时由操作系统负责将所需信息从外存调入内存然后继续执行程序。
若操作系统内存不够时由操作系统将内存中暂时用不到的数据调出到外存。
在操作系统的管理下在用户看来程序可用的内存要比实际内存要大得多这就是虚拟内存技术。
虚拟内存有一下三个主要特征:
多次性无需在作业运行时一次性全部装入内存而是允许被分成多次调入内存。
对换性在作业运行时无需一直常驻内存而是允许在作业运行过程中将作业换入、换出。
虚拟性从逻辑上扩充了内存的容量使用户看到的内存容量远大于实际的容量。
5.3.4 如何实现虚拟内存技术
虚拟内存技术允许一个作业分多次调入内存。如果采用连续分配方式会不方便实现。因此虚拟内存的实现需要建立在离散分配的内存管理方式基础上。 两者的主要区别
在程序执行过程中传统的管理方式是一次性将数据全部加载到内存中。虚拟存储管理是需要时才将数据从外存中加载到内存中内存不够用时将暂时不需要的数据从内存换出到外存。 5.3.5 请求分页管理方式
① 请求分页与基本分页的区别
页面加载方式
基本分页存储管理 在基本分页中整个进程的所有页面都需要事先装入内存。如果进程有多个页面则每一个页面必须先装入内存才能执行程序。一旦内存装满如果需要执行新的程序系统可能会通过替换策略如FIFO、LRU将一些页面换出。 请求分页存储管理 请求分页采用按需加载的方式。页面只有在进程实际需要时即发生页面缺失时才被加载到内存中这有效节省了内存空间和减少不必要的页面装载。当需要访问的页面不在内存时会触发页面错误Page Fault然后系统会将缺失的页面从外存中加载到内存中。
内存使用效率
基本分页存储管理 内存使用效率较低因为每次进程执行时都需要将其所有页面加载到内存即使有些页面不被使用也会占据内存空间。可能会浪费大量的内存资源特别是当进程的页面很大时。 请求分页存储管理 内存使用效率较高因为只有真正需要的页面才会被加载到内存中。通过按需加载减少了不必要的内存消耗。提高了内存的利用率特别适合内存资源有限的系统。
页面错误处理
基本分页存储管理 在基本分页中如果进程所需的页面不在内存中会直接发生缺页错误需要进行页面置换。页面错误发生频率较低因为一般情况下所有页面已经在进程开始前加载完毕。 请求分页存储管理 在请求分页中页面错误是一种常见现象。因为只有当页面被访问时才会加载因此当进程首次访问某个页面时通常会发生页面错误。页面错误会触发操作系统的页面调度程序将缺失的页面从外存调入内存。
程序启动时间
基本分页存储管理 由于所有页面在进程开始时必须全部装入内存因此启动时间较长。 请求分页存储管理 请求分页可以显著缩短进程的启动时间因为进程启动时不需要所有页面都加载到内存中进程可以在部分页面装入后立即开始执行。
外存空间的使用
基本分页存储管理 依赖操作系统的页面置换机制当内存不足时将某些不常用的页面移到外存中重新装入时需要额外的管理操作。 请求分页存储管理 请求分页广泛使用外存作为页面存储的扩展。当内存中没有某些页面时可以从外存中请求加载。更好地管理了外存和内存的交互外存中的页面可以随时被加载和置换。
页面替换策略
基本分页存储管理 页面替换的次数相对较少因为在进程执行前通常会尽量确保所需的页面都已装入内存。 请求分页存储管理 页面替换策略非常重要因为频繁的页面错误会导致系统经常需要从外存调入新的页面因此请求分页通常结合页面替换算法如 LRU、FIFO来提高性能。
区别总结
特性基本分页存储管理请求分页存储管理页面加载方式预先加载所有页面按需加载页面内存使用效率较低可能浪费内存较高按需分配内存页面错误频率较低较高首次访问页面时程序启动时间较长较短只加载部分页面外存使用可选用于替换页面经常与外存交互按需加载页面替换策略替换次数较少页面替换频繁需要高效策略
总的来说请求分页管理通过按需加载页面和灵活的内存管理优化了系统资源的使用效率特别适合多任务或内存资源紧张的环境。
② 请求页表机制
请求分页与基本分页相比请求分页需要知道要用的页面有没有调入内存就算是没有调入内存也需要知道页面在外存中的位置。
当内存不够时操作系统需要实现页面置换。而在页面置换之前操作系统需要确认内存中的页面有没有被修改过如果没有修改过自然也就不用再进行置换。如果修改过需要进行置换。因此操作系统需要记录页面修改状态。 ③ 缺页中断机构
如果内存中有空闲块 如果内存中没有空闲块
缺页中断是因为当前执行的执行想要访问的目标页面没有调入内存而产生的因此属于内中断。
一条指令在执行的时候有可能会产生多次中断。例如copy A to B就是将逻辑地址A中的数据复制到逻辑地址B中而AB属于不同的页面且这两个页面恰巧都不在内存中这样的话就会产生两次中断。
④ 地址变换机构
请求分页与基本分页的主要区别在于
在程序执行过程中所访问的信息不在内存中时操作系统会负责将所需信息从外存加载到内存。
当内存空间不够时操作系统负责将暂时用不到的且已经修改的页面换出内存。 补充细节在上图中有以下补充细节
①只有写指令访问内存时才需要修改 ”修改位“。并且修改时只需要修改快表中的数据只有将快表项删除时才需要将数据写会慢表。
②和普通中断处理一样缺页中断同样需要保存CPU现场。
③需要结合具体的页面置换算法决定换出哪一个页面。
④换入换出页面都需要启动慢速的I/O操作可见如果换入换出太频繁就会有很大的开销。
⑤页面调入内存后需要修改慢表同时将表项复制到快表中。
5.3.6 页面置换算法 最优页面置换算法Optimal ReplacementOPT 每次选择淘汰的是永不使用或者在最长时间内不再被访问的页面这样可以保证最低的缺页率。 例如假设系统为某进程分配了三个内存块并考虑到有以下页面号引用串 70120 304230321201701 虽然最优页面置换算法可以保证最低的缺页率但实际上只有在进程执行过程中才能知道接下来会访问到的是哪一个页面。操作系统无法提前预判页面的访问序列因此此算法无法实现。 先进先出算法First In First OutFIFO 每次选择淘汰的页面是最早进入内存的页面。 实现方法把调入内存的页面根据调入的先后顺序排成一个队列需要换出页面时选择对头页面即可队列的最大长度取决于操系统为进程分配了多少个内存块。 例假设系统为进程分配了三个内存块而进程总共4个页面。且进程有以下引用串。 321032432104 假设此时增加内存块为4个正常应该完全满足内存需求。但是缺页次数反而增多了
这就是Belady异常为进程分配的物理内存块数变多时缺页次数不减反增的异常现象。
只有FIFO算法才会产生被Belady异常。另外虽然此算法实现简单但是性能差。因为最先进入内存的页面也有可能经常访问。 最近最久未使用算法Least Recently Used 每次被淘汰的都是最近未使用的页面。 实现方法使用页表项中的访问字段记录该页面自上次被访问以来的时间t。当需要淘汰一个页面时选择现有页面中t值最大的即最近最久未使用的页面。 此算法性能虽然很好但是需要专门的硬件支持算法开销大。 时钟页面置换算法 时钟置换算法是一种性能和开销较均衡的算法又称CLOCK算法或最近未用算法 (NRU Not Recently Used) 简单的CLOCK算法实现方法为每个页面设置一个访问位再将内存中的页面都通过链按指针链接成一个循环队列。当某页被访问时其访问位置为1。当需要淘汰一个页面时只需检查页的访问位如果是0就选择该页换出如果是1则将它置为0暂不换出继续检查下一个页面若第一轮扫描中所有页面都是1则将这些页面的访问位依次置为0后再进行第二轮扫描第二轮扫描中一定会有访问位为0的页面因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描。 下图为时钟页面置换算法的一个例子。这里有 12个逻辑页面。以A到L它们被组织成一个环形链表的形式每个页面类似于钟面上的一个整点时间。每个页面旁边的数宇表示其访问位的值。假设在当前状态下指针所指向的是页面C。然后发生了一个缺页中断需要把一个页面淘汰出局。根据时钟页面置换算法的思路首先考察页面C的访问位发现它的值等于1这说明它在内存的这段时间内曾经被访问过。当然具体被访问了多少次是什么时候被访问的这些都不知道无法获取这些信息。因为访问位只有一位它的值要么是1要么是0。而对于 LFU 算法和 LRU 算法这些信息是知道的。在LFU 算法中有一个计数器来记录页面的访问次数。而在 LRU 算法中每当一个页面被访问时就会调整它在队列当中的位置把它排在最前面。 由于页面C的访问位的值为1因此就不能把它淘汰出局而是把它的访问位的值设置为0然后往下移动一格继续考察页面D。结果发现D 的访问位的值也等于1所以不能把它淘汰出局而是把它的访问位的值设置为0然后再往下移动一格继续考察页面E。结果发现E的访问位的值等于0因此就选中它来作为被淘汰的页面把新的页面 M 装人它所在的物理页面当中然后把指针往下移动一格。 改进型的时钟置换算法 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上如果被淘汰的页面没有被修改过就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时才需要写回外存。因此除了考虑一个页面最近有没有被访问过之外操作系统还应考虑页面有没有被修改过。在其他条件都相同时应优先淘汰没有修改过的页面避免I/O操作。这就是改进型的时钟置换算法的思想。修改位0表示页面没有被修改过修改位1表示页面被修改过。为方便讨论用(访问位修改位)的形式表示各页面状态。如(1,1)表示一个页面近期被访问过且被修改过。 算法规则:将所有可能被置换的页面排成一个循环队列 第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位 第二轮:若第一轮扫描失败则重新扫描查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0 第三轮:若第二轮扫描失败则重新扫描查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位 第四轮:若第三轮扫描失败则重新扫描查找第一个(0,1)的帧用于替换。由于第二轮已将所有帧的访问位设为0因此经过第三轮、第四轮扫描一定会有一个帧被选中因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描 总结来说这种算法的基本原则就是优先空闲且没有被修改过的的内存块然后是空闲但被修改后的内存块。 只需要一轮扫描的情况 需要两轮扫描的情况 第一轮扫描没有找到(0,0)的内存块。 第二轮扫描会将扫描过的内存块的访问位设置为0。直到扫描到第一个(0,1)的内存块为止。 需要扫描三轮的情况 第一轮扫描没有找到(0,0)的内存块。 第二轮扫描会将扫描过的内存块的访问位设置为0。且没有找到(0,1)的内存块。 第三轮扫描找到(0,0)的内存块。 需要四轮扫描的情况 第一轮循环找(0,0)的内存块但是没有扫描到(0,0)的内存块。 第二轮循环找(0,1)的内存块但是没有找到。并且把扫描过的内存块的访问位设置为0。 第三轮循环找(0,0)的内存块但是没有扫描到(0,0)的内存块。 第四轮查找第一个(0,1)的帧用于替换。
5.3.7 页面分配策略、抖动、工作集 驻留集 指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中驻留集大小一般小于进程的总大小。 考虑一个极端情況若某进程共有100个页面则该进程的驻留集大小为100时进程可以全部放入内存运行期间不可能再发生缺页。若驻留集大小为1则进程运行期间必定会极频繁地缺页。 若驻留集太小就会导致频繁缺页这样系统就会花费大量的时间处理缺页实际用于进程推进的时间就会很少。 若驻留集太大就会导致系统多道程序并发度降低资源利用率变低。 所以应该为驻留集选择一个合适的大小。 页面分配、置换策略 页面分配 固定分配系统为每个进程分配一组固定大小的内存块在程序运行期间不再改变。即驻留集的大小不变。 可变分配系统先为进程分配一定数目的内存块在程序运行期间可以根据情况做适当的增加或减少。即驻留集的大小可以改变。 置换策略 局部置换发生缺页时只选择进程自己的内存块进行置换。 全局置换可以将操作系统保留的空闲物理块分配给缺页进程也可以将别进程持有的内存块置换到外存后再分配给缺页进程。 固定分配局部置换 系统为每个进程分配一定数量的内存块在程序整个运行期间都不在改变当进程发生缺页现象时候只能在分配给本进程的内存块中的页面选取一页换出到外存然后再需要的页面从外存调入到内存。这种策略的缺点是很难再刚开始运行时就确定内存所需驻留集大小。采用这种策略的系统可以根据进程大小优先级或者是根据程序员给出的参数来确定为一个进程分配的内存块数。 可变分配全局置换 进程刚刚开始运行时系统会分配一定数量的内存块并且操作系统会维护一个空闲物理内存的队列。当进程发生缺页时从空闲队列中选择一块空闲的物理内存进行分配。如果操作系统中没有空闲的物理内存块后可以选择一个未锁定有一些内存块有可能存储内核态的数据这些数据是不能被置换出内存的且这些内存块是被标识为锁定的状态的页面换出到外存然后再将此物理块换出到外存。采用这种策略时只要进程发生缺页都将获得新的物理块仅当物理块用完时系统才会选择一个未锁定的页面调出。被选择调出的页可能是任何进程的页面这样被调出页面的进程的可用物理页面会减少缺页率会增加。 可变分配局部置换 进程刚刚开始运行时系统会分配一定数量的内存块。当进程发生缺页现象时只允许在进程自己的物理块中选择一个换出。如果在进程运行的过程中频繁发生缺页现象系统会为该进程多分配几个内存块直至缺页率适当降低为止。反之如果进程的缺页率一直很低系统可适当减少分配给该进程的物理块。 可变分配全局置换只要进程发生缺页就为其分配新的物理块。 可变分配局部置换要根据进程发生缺页的频率来动态地增加或者减少进程的物理块。 调入页面的时机 预调页策略根据空间局部性原理一次调入若干个相邻的页面可能比一次调入一个页面更加高效。但如果预先调入的页面是在大多数情况下都没有被调用过的页面这种策略又是低效的。因此可以预测不久后可能访问到的页面将他们预先调入到内存但目前的预测成功率只有50%左右。因此这种策略主要用于进程的首次调入由程序员指定应该先调入哪些页面。 请求调入策略 进程在运行期间发现有缺页时才将所缺页面调入内存。由这种策略调入内存的页面一定会被访问到。但是由于一次只能调入一页而每次调入内存都要进行I/O操作因此开销会比较大。 从何处调页 (1) 系统拥有足够的兑换区空间页面的调入、调出都是在内存与对换区之间进行这样可以保证页面的调入、调出速度很快。在进程运行前需将进程相关的数据从文件区复制到对换区。 (2) 系统缺少足够的兑换区空间凡是不会被修改的数据都是从文件区直接调入到内存这些数据在用完后不必被再写回到外存下次再用到时再从文件区调入即可。对于可能被修改的部分换出时需写回到磁盘的对换区下次需要时再从兑换区调入。 (3) UNIX方式在进程运行之前所有的数据都是存储在文件区的。在进程运行时会将需要的数据从文件区加载到内存当这些数据暂时用不到时会被换出到磁盘的对换区需要时会再从对换区再载入数据到内存。 抖动现象 刚刚换出的页面马上又要换入内存刚刚换入的页面马上又要换出外存这种频繁的页面调度行为称为抖动或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够) 工作集 指在某段时间间隔内进程实际访问页面的集合。 工作集大小可能小于窗口尺寸实际应用中操作系统可以统计进程的工作集大小根据工作集大小给进程分配若干内存块。如窗口尺寸为5经过一段时问的监测发现某进程的工作集最大为3那么说明该进程有很好的局部性可以给这个进程分配3个以上的内存块即可满足进程的运行需要。一般来说驻留集大小不能小于工作集大小否则进程运行过程中将频繁缺页。 拓展基于局部性原理可知进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此可以根据进程近期访问的页面集合工作集来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。
5.3.8 内存映射文件
内存映射文件是一种将文件或设备映射到进程的虚拟内存空间的技术使得应用程序可以像访问内存一样直接访问文件内容。这种机制允许文件的部分或全部内容被映射到内存中从而提供高效的文件读写操作。其原理和页表的原理很类似。
如果有一个100页的文件内存映射文件通常会维护100个映射关系。每个映射关系对应文件中的一页操作系统通过这些映射关系来管理文件的访问。
主要特点
直接内存访问通过映射程序可以直接读取和写入文件数据无需显式的读写操作。按需加载只有在访问特定数据时相关文件页才会被加载到内存。共享内存多个进程可以映射同一文件实现在进程间共享数据。性能优势内存映射文件通常比传统的文件 I/O 操作更快特别是在处理大文件时。
工作原理
操作系统为文件创建一个映射允许文件的内容在内存中直接访问。通过页表管理虚拟内存与物理内存之间的映射关系。数据的读取和修改会反映在内存中操作系统会在适当的时机将更改写回文件。
应用场景
大文件处理如视频、数据库和日志文件。进程间通信通过共享映射区域进行数据交换。高性能计算需要频繁访问文件的场景。
