OS学习笔记：内存管理

四、内存管理

1.内存管理的基本概念

操作系统对内存的划分和动态分配

程序的编译

由编译程序将用户源代码编译成cpu可执行的目标代码&＃xff08;.o文件&＃xff09;&＃xff0c;产生了若干个目标模块&＃xff08;即若干程序段&＃xff09;。

程序的链接

根据外部访问符号名表&＃xff08;如变量名、函数名等&＃xff09;&＃xff0c;将经过编译或汇编 得到的一组目标模块以及它们所需要的库函数&＃xff0c;装配成一个完整的装入模块 。

静态链接

下图B和C都属于外部调用符号&＃xff0c;在将这几个目标模块装配成一个装入模块时&＃xff0c;须解决以下两个问题&＃xff1a;

(1) 对相对地址进行修改。

(2) 变换外部调用符号。

这种先进行链接所形成的一个完整的装入模块&＃xff0c;又称为可执行文件。通常都不再拆开它&＃xff0c;要运行时可直接将它装入内存。这种事先进行链接&＃xff0c;以后不再拆开的链接方式&＃xff0c;称为静态链接方式。

装入时动态链接&＃xff08;所有的模块都装入内存&＃xff09;

用户源程序经编译后所得的目标模块&＃xff0c;是在装入内存时边装入边链接的&＃xff0c; 然后再按照上图所示的方式来修改目标模块中的相对地址。

优点&＃xff1a;

1. 便于修改和更新。对于经静态链接装配在一起的装入模块&＃xff0c;如果要修改或更新其中的某个目标模块&＃xff0c;则要求重新打开装入模块。这不仅是低效的&＃xff0c;而且有时是不可能的。若采用动态链接方式&＃xff0c;由于各目标模块是分开存放的&＃xff0c;所以要修改或更新各目标模块是件非常容易的事。
2. 便于实现对目标模块的共享。在采用静态链接方式时&＃xff0c;每个应用模块都必须含有其目标模块的拷贝&＃xff0c;无法实现对目标模块的共享。但采用装入时动态链接方式&＃xff0c;OS则很容易将一个目标模块链接到几个应用模块上&＃xff0c;实现多个应用程序对该模块的共享。

运行时动态链接&＃xff08;需要某个模块时才装入内存&＃xff09;

在许多情况下&＃xff0c;应用程序在运行时&＃xff0c;每次要运行的模块可能是不相同的。但由于事先无法知道本次要运行哪些模块&＃xff0c;故只能是将所有可能要运行到的模块都全部装入内存&＃xff0c;并在装入时全部链接在一起。显然这是低效的&＃xff0c;因为往往会有些目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块&＃xff0c;如果程序在整个运行过程中都不出现错误&＃xff0c;则显然就不会用到该模块。

在执行过程中&＃xff0c;当发现一个被调用模块尚未装入内存时&＃xff0c;立即由OS去找到该模块并将之装入内存&＃xff0c;把它链接到调用者模块上。凡在执行过程中未被用到的目标模块&＃xff0c;都不会被调入内存和被链接到装入模块上&＃xff0c;这样不仅可加快程序的装入过程&＃xff0c;而且可节省大量的内存空间。

####程序的装入

由装入程序将装入模块装入内存&＃xff0c;构造PCB&＃xff0c;形成进程&＃xff0c;开始运行(使用物理地址)。

绝对装入方式

在编译时&＃xff0c;如果知道程序将驻留在内存的什么位置&＃xff0c;那么&＃xff0c;编译程序将产生绝对地址的目标代码。 绝对装入程序按照装入模块中的地址&＃xff0c;将程序和数据装入内存。 装入模块被装入内存后&＃xff0c;由于程序中的逻辑地址与实际内存地址完全相同&＃xff0c;故不须对程序和数据的地址进行修改。程序中所使用的绝对地址&＃xff0c;既可在编译或汇编时给出&＃xff0c;也可由程序员直接赋予。

注&＃xff1a;
由于内存划分为系统区和用户区&＃xff0c;程序实际在用户区执行&＃xff0c;故实际上程序的实际内存地址也有一定的增加&＃xff0c;不可能像逻辑地址一样从0开始。

• 优点&＃xff1a;使CPU执行目标代码快
• 缺点&＃xff1a;
  1. 由于内存大小限制&＃xff0c;能装入内存并发执行的进程数大大减少
  2. 编译程序必须知道内存的当前空闲地址部分和其地址&＃xff0c;并且把进程的不同程序段连续地存放起来&＃xff0c;编译非常复杂。

静态地址重定位

绝对装入方式只能将目标模块装入到内存中事先指定的位置。在多道程序环境下&＃xff0c;编译程序不可能预知所编译的目标模块应放在内存的何处&＃xff0c;因此&＃xff0c;绝对装入方式只适用于单道程序环境。

在多道程序环境下&＃xff0c;所得到的目标模块的起始地址通常是从 0 开始的&＃xff0c;程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式&＃xff0c;根据内存的当前情况&＃xff0c;将装入模块装入到内存的适当位置。

静态地址重定位&＃xff1a;即在程序装入对目标代码装入内存的过程中完成&＃xff0c;是指在程序开始运行前&＃xff0c;程序中指令和数据的各个地址均已完成重定位&＃xff0c;即完成虚拟地址到内存地址映射。地址变换通常是在装入时一次完成的&＃xff0c;以后不再改变。

• 优点&＃xff1a;无需硬件支持
• 缺点&＃xff1a;
  1. 程序重定位之后就不能在内存中搬动了&＃xff1b;
  2. 要求程序的存储空间是连续的&＃xff0c;不能把程序放在若干个不连续的区域中。

动态地址重定位

可重定位装入方式可将装入模块装入到内存中任何允许的位置&＃xff0c;故可用于多道程序环境&＃xff1b;但这种方式并不允许程序运行时在内存中移动位置。因为&＃xff0c;程序在内存中的移动&＃xff0c;意味着它的物理位置发生了变化&＃xff0c; 这时必须对程序和数据的地址(是绝对地址)进行修改后方能运行。然而&＃xff0c;实际情况是&＃xff0c;在运行过程中它在内存中的位置可能经常要改变&＃xff0c;此时就应采用动态运行时装入的方式。

动态地址重定位&＃xff1a;不是在程序执行之前而是在程序执行过程中进行地址变换。更确切的说&＃xff0c;是把这种地址转换推迟到程序真正要执行时才进行&＃xff0c;即在每次访问内存单元前才将要访问的程序或数据地址变换成内存地址。动态重定位可使装入模块不加任何修改而装入内存。为使地址转换不影响指令的执行速度&＃xff0c;这种方式需要一个重定位寄存器的支持。

优点&＃xff1a;

1. 目标模块装入内存时无需任何修改&＃xff0c;因而装入之后再搬迁也不会影响其正确执行&＃xff0c;这对于存储器紧缩、解决碎片问题是极其有利的&＃xff1b;
2. 一个程序由若干个相对独立的目标模块组成时&＃xff0c;每个目标模块各装入一个存储区域&＃xff0c;这些存储区域可以不是顺序相邻的&＃xff0c;只要各个模块有自己对应的定位寄存器就行。

缺点&＃xff1a;需要硬件支持。

逻辑地址和物理地址空间

程序经过编译后&＃xff0c;每个目标模块都是从0号单元开始编址&＃xff0c;称为该目标模块的相对地址&＃xff08;或逻辑地址&＃xff09;。

物理地址空间是指内存中物理单元的集合&＃xff0c;它是地址转换的最终地址&＃xff0c;进程在运行时执行指令和访问数据都要通过物理地址从主存中存取。当装入程序&＃xff08;Loader&＃xff09;将可执行代码装入内存时&＃xff0c;必须通过地址转换将逻辑地址转换成物理地址&＃xff0c;这个过程称为地址重定位。

对换与覆盖

覆盖与对换技术是在多道程序环境下用来扩充内存的两种方法。

覆盖与对换可以解决在小的内存空间运行大作业的问题&＃xff0c;是“扩充”内存容量和提高内存利用率的有效措施。

覆盖技术主要用在早期的 OS 中&＃xff0c;对换技术则用在现代OS 中。

对换

摘自&＃xff1a;操作系统存储器管理之覆盖与对换

所谓“对换” &＃xff0c;是指将暂时不用的某个进程及数据&＃xff08;首先是处于阻塞状态优先级最低的&＃xff09;部分&＃xff08;或全部&＃xff09;从内存移到到外存&＃xff08;备份区或对换区&＃xff09;中去&＃xff0c;让出内存空间&＃xff0c;同时将某个需要的进程调入到内存中&＃xff0c;让其运行。

交换技术也是“扩充”内存容量和提高内存利用率的有效措施。

交换到外存的进程需要时可以被再次交换回&＃xff08;选择换出时间最久的&＃xff09;内存中继续执行。

对换的类型

• 整体对换&＃xff1a;进程对换&＃xff0c;解决内存紧张问题。 &＃xff08;中级调度&＃xff09;
• 部分对换&＃xff1a;页面对换/分段对换&＃xff0c;提供虚存支持。

对换空间的管理

• 具有对换功能的 OS 中&＃xff0c;通常把外存分为文件区和对换区。前者用于存放文件&＃xff0c;后者存放从内存换出的进程。对换区比文件区侧重于对换速度。因此对换区一般采用连续分配。

进程的换出与换入

• 选择换出进程&＃xff1a;优先级&＃xff0c;进程状态。
• 选择换入进程&＃xff1a;优先级&＃xff0c;进程状态&＃xff0c;换出时间等。

重定位

2.连续内存分配方法

连续分配&＃xff1a;程序中代码或数据的逻辑地址相邻&＃xff0c;体现在内存空间分配时物理地址的相邻

2.1单一连续分配

• 简单&＃xff0c;无外部碎片
• 只能用于单用户、单任务的操作系统&＃xff0c;有内部碎片

2.2固定连续分配

• 无外部碎片
• 有内部碎片&＃xff0c;存储空间利用率低

2.3动态分区分配

• 无内部碎片&＃xff0c;有外部碎片
• 动态分区的分配策略&＃xff08;★★★★★&＃xff09;
• 首次适应&＃xff08;★★★★&＃xff09;&＃xff1a;按地址从小到大依次寻找空闲分区&＃xff0c;将第一个能满足要求的空闲分区分配给程序
• 最佳适应&＃xff1a;按容量从小到大依次寻找空闲分区&＃xff0c;将第一个能满足要求的空闲分区分配给程序
• 最坏适应&＃xff08;最大适应&＃xff09;&＃xff1a;按容量从大到小依次寻找空闲分区&＃xff0c;将第一个能满足要求的空闲分区分配给程序
• 邻近适应&＃xff08;循环首次适应&＃xff09;&＃xff1a;与首次适应类似&＃xff0c;但是查找开始位置为上一次查找结束的位置
• 动态分区的分配策略的比较
  • 首次适应&＃xff0c;简单&＃xff0c;最好、最快

3.1离散内存分配方法(分页、分段、段页)

3.1.1分页

#####逻辑地址到物理地址的转换

逻辑地址到物理地址的转换&＃xff08;不含快表&＃xff09;

• 设页面大小为 L&＃xff0c;逻辑地址A 到物理地址E的转换
  1. 分析出页号和页面偏移量&＃xff08;根据题设地址结构或者计算得出&＃xff09;&＃xff1a;计算页号 P &＃xff08; P &＃61; A / L &＃xff09;和页面偏移量 W &＃xff08;W &＃61; A % L &＃xff09;
  2. 判断页号合法性&＃xff1a;比较页号 P 和页表长度 M &＃xff0c;若 P ≥ M &＃xff0c;则产生越界中断&＃xff0c;否则继续执行。
  3. 查页表&＃xff0c;得块号&＃xff1a;页表中页号 P 对应的页表项地址&＃xff08;目的是在内存中找到相应的页表项&＃xff09; &＃61; 页表始址 F &＃43; 页号 P × 页表项长度&＃xff0c;取出该页表项内容 b &＃xff0c;即为物理块号。&＃xff08;注意区分页表长度和页表项长度。页表长度的值指一共有多少页&＃xff0c;页表项长度是指页地址占多大的存储空间&＃xff09;
  4. 拼接块号和页内偏移量&＃xff1a;计算 E &＃61; b × L &＃43; W &＃xff0c;用得到的物理地址 E 去访问内存

逻辑地址到物理地址的转换&＃xff08;含快表&＃xff09;

• 含快表的地址变换流程
  1. CPU 给出逻辑地址后&＃xff0c;由硬件进行地址转换&＃xff0c;将页号送入高速缓存寄存器&＃xff0c;并将此页号与快表中的所有页号进行比较
  2. 若能找到匹配的页号&＃xff0c;说明所要访问的页表项在快表中&＃xff0c;则直接从中取出该页对应的块号&＃xff0c;和页内偏移量拼接形成物理地址。&＃xff08;仅一次访存就可以存取数据&＃xff09;
  3. 若未找到&＃xff0c;类似不含快表对逻辑地址进行转换&＃xff0c;并把&＃xff08;页号&＃xff0c;块号&＃xff09;对存入快表。若快表已满&＃xff0c;则需依据相应的替换算法对快表中的元素进行替换

多级页表

• 试和索引表比较一下
• 多级和一级的对比
  • 一级页表&＃xff0c;其存储页号到块号的存储极限取决于其本身的长度
  • 多级页表&＃xff0c;其存储页号到块号的存储极限取决于各级页表长度之积
  • 总结&＃xff1a;乘法比加法更能压缩空间
• 以二级为例&＃xff0c;分析其中的数据关系&＃xff08;注意举一反三&＃xff09;&＃xff08;★★★★★&＃xff09;
  • 32 位 逻辑地址空间、页面大小 4 KB、页表项 4 B&＃xff0c;以字节为编址单位&＃xff0c;试确定满足二级页表的逻辑地址空间格式&＃xff08;即求哪几位代表一级页号、二级页号、页内偏移&＃xff09;
    • 页内偏移位数 &＃61; log2页面大小log_2页面大小log2​页面大小 &＃xff08;本例即 log24K&＃61;12log_24K&＃61;12log2​4K&＃61;12&＃xff09;
    • 由于顶级页表最多一个页面&＃xff0c;故顶级&＃xff08;一级&＃xff09;页表总共能容纳 页面大小页表项大小页面大小/页表项大小 个页表项&＃xff08;本例为 4KB/4B &＃61; 1K&＃xff09;&＃xff0c;所需位数为 页表项个数log2(页表项个数)log_2(页表项个数)log2​(页表项个数) &＃xff08;本例为log2(1K)&＃61;10log_2(1K)&＃61;10log2​(1K)&＃61;10&＃xff09;
    • 剩下的 10 位&＃xff0c;即为二级页号。
    • 所以逻辑地址空间格式如下

3.1.2分段&＃xff08;两次访存&＃xff09;

• 逻辑地址A到物理地址E的转换
  1. 提取段号和页内偏移量&＃xff1a;逻辑地址 A 的结构&＃xff1a;前几位是段号 S &＃xff0c;后几位是段内偏移 W
  2. 判断段号合法性&＃xff1a;比较段号 S 和段表长度 M &＃xff0c;若 S ≥ M &＃xff0c;则产生越界中断&＃xff0c;否则继续执行
  3. 查段表&＃xff0c;找到段基址、段长&＃xff0c;并判段内偏移的合法性&＃xff1a;段表中段号 S 对应的段表项地址 &＃61; 段表首址 F &＃43; 段号 S × 段表项长度&＃xff0c;取出该段表项的前几位得到段长 C 。若段内偏移量 ≥ C&＃xff0c;则产生越界中断&＃xff0c;否则继续执行。
  4. 取出段基地址&＃xff0c;和段内偏移求和&＃xff1a;取出段表项中该段的基址 b &＃xff0c;计算 E &＃61; b &＃43; W

3.1.3段页&＃xff08;三次访存&＃xff09;

• 逻辑地址A到物理地址E的变换

1. 依据段号查段表&＃xff0c;找到页表始址
2. 依据页表始址和页号查页表&＃xff0c;得到块号
3. 将块号和页面偏移量拼接成物理地址

3.2虚拟内存分配方法

虚拟内存

概念

虚拟记忆体是电脑系统记忆体管理的一种技术。它使得应用程式认为它拥有连续可用的记忆体&＃xff08;一个连续完整的位址空间&＃xff09;&＃xff0c;而实际上实体记忆体通常被分隔成多个记忆体碎片&＃xff0c;还有部分暂时储存在外部磁碟记忆体上&＃xff0c;在需要时进行资料交换。与没有使用虚拟记忆体技术的系统相比&＃xff0c;使用这种技术使得大型程式的编写变得更容易&＃xff0c;对真正的实体记忆体&＃xff08;例如RAM&＃xff09;的使用也更有效率。此外&＃xff0c;虚拟记忆体技术可以使多个行程共享同一个执行库&＃xff0c;并通过分割不同行程的记忆体空间来提高系统的安全性。

请求分页(段)管理

地址变换过程

页面置换算法

最佳&＃xff08;OPT&＃xff09;置换算法

• 置换标准&＃xff1a;淘汰最长时间内不再被访问的页面
• 无法实现

先进先出&＃xff08;FIFO&＃xff09;置换算法

• 置换标准&＃xff1a;淘汰最早进入内存的页面&＃xff08;用队列实现&＃xff09;
• 缺页率较高&＃xff0c;会产生所分配的物理块数增大而页故障数反减的异常现象

最近最久未使用&＃xff08;LRU&＃xff09;置换算法

• 置换标准&＃xff1a;淘汰最近最久未使用的页面
• 性能较好&＃xff0c;但需要寄存器和栈的硬件支持。
• 手算思路
  • 假想一个链表&＃xff0c;其最大长度为内存中能存下最多页面的个数。
  • 若页面不在该链表中&＃xff0c;且链表长度未超过最大长度&＃xff0c;则将这个页面插入到链表头部
  • 若页面不在该链表中&＃xff0c;且链表长度超过最大长度&＃xff0c;则将链表末尾元素删除&＃xff0c;并将新个页面插入到链表头部
  • 若页面在该链表中&＃xff0c;则将新页面移动到链表头部&＃xff0c;其他元素位置不变

时钟&＃xff08;CLOCK&＃xff09;置换算法&＃xff08;NRU&＃xff0c;最近未用&＃xff09;

• 置换标准&＃xff1a;淘汰访问位为 0 的页面
  • &＃xff08;具体算法流程详见教材&＃xff09;
• 改进的 CLOCK 算法&＃xff1a;多增一位修改位。
  • 假设 A 为访问位&＃xff0c; M 为修改位&＃xff0c;&＃xff08;A, M&＃xff09;所有可能取值&＃xff0c;淘汰顺序为
  • (0, 0) (0, 1) (1, 0) (1, 1) &＃xff08;优先换出未使用的&＃xff1b;若全部都已使用&＃xff0c;再考虑优先换出未被修改的&＃xff09;
  • &＃xff08;具体算法流程详见教材&＃xff09;

4.内存保护与共享

分段的共享和保护

共享段

为了实现分段共享&＃xff0c;可在系统中配置一张共享段表&＃xff0c;所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存.

分段保护

在分段系统中&＃xff0c;由于每个分段在逻辑上是独立的&＃xff0c;因而比较容易实现信息保护。目前常采用以下几种措施来确保信息的安全。

1. 越界检查

   在段表寄存器中放有段表长度信息&＃xff1b;同样&＃xff0c;在段表中也为每个段设置有段长字段。在进行存储访问时&＃xff0c;首先将逻辑地址空间的段号与段表长度

2. 存取控制检查

   在段表的每个表项中&＃xff0c;都设置了一个“存取控制”字段&＃xff0c;用于规定对该段的访问方式。通常的访问方式有

3. 环保护机构

   

5.抖动的概念和处理方法

概念

如果多道程度过高&＃xff0c;页面在内存与外存之间频繁调度&＃xff0c;以至于调度页面所需时间比进程实际运行的时间还多&＃xff0c;此时系统效率急剧下降&＃xff0c;甚至导致系统崩溃。这种现象称为颠簸或抖动&＃xff08;thrashing&＃xff09;

处理\预防方法

• 采取局部置换策略
• 在处理机调度中引入工作集策略
• 用 L&＃61;S 准则调节缺页率&＃xff08;Denning, 1980&＃xff09;
• 挂起若干进程

解题技巧与重要结论

• 物理地址 VS 逻辑地址
  • 物理地址&＃xff08;实地址&＃xff09;&＃xff0c;若其位数为 32 位&＃xff0c;意味着实际物理内存为 2322^{32}232B
  • 逻辑地址&＃xff08;虚地址&＃xff09;&＃xff0c;若其位数为 48 位&＃xff0c;意味着对用户来说内存大小为 2482^{48}248B &＃xff08;采用了虚拟内存技术&＃xff09;
• 含多级页表的逻辑地址的划分中的公式总结&＃xff08;对照教材中多级页表理解&＃xff09;
• 页内偏移位数页面大小页内偏移位数&＃61;log2页面大小log_2页面大小log2​页面大小
• 页号部分总位数逻辑地址总位数页内偏移位数页号部分总位数&＃61;$逻辑地址总位数$−$页内偏移位数$
• 一级页号位数&＃61;页面大小页表项大小\frac{页面大小}{页表项大小}页表项大小页面大小​
• 页表级数&＃61;页号部分总位数一级页号位数\frac{页号部分总位数}{一级页号位数}一级页号位数页号部分总位数​