第三章 内存管理_最新发布页

  

内存

内存的基础知识

内存可存放数据，程序执行前需要先放到内存中才能被CPU处理，缓和CPU和硬盘之间的速度矛盾。按字节编址：每个存储单元大小为1字节，1B=8个二进制位bit。按字编址：如果字长为16位，则每个存储单元大小为1个字，每个字的大小为16个二进制位

进程运行的基本原理

指令的工作原理：指令的工作基于“地址”，每个地址对应一个数据的存储单元

逻辑地址(相对地址)：程序通过编译，链接后生成的指令中指明的是逻辑地址，即相对与进程起始地址而言的地址。逻辑地址转为物理地址的三种装入方式。

• 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码，装入程序按照装入模块中的地址，将程序和数据装入内存，只适用于单道程序环境。
• 可重定位装入(静态定位)：编译，链接后的装入模块都是从0开始，指令中使用的地址，数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置，装入时对地址进行重定位，讲逻辑地址变换为物理地址(地址变换是在装入时一次完成的)。在一个作业装入内存时必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业，作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
• 动态定位(动态运行时装入)：编译，链接后的装入模块的之地都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址，需要重定位寄存器支持。

写程序-->运行程序：程序员---(编辑)--->源代码---(编译)--->目标模块---(链接)--->装入模块---(装入)--->内存。

编译：由编译程序将用户源代码编译成若干个目标模块。

链接：由链接程序将编译后的形成的目标模块以及所需库函数链接在一起，形成一个完整的装入模块。

装入：由装入程序将装入模块装入内存运行。

链接的三种方式：

• 静态链接：在程序运行之前，先将个目标模块及他们所需的库函数连接成一个完整的可执行文件(装入模块)，之后不再拆开。
• 装入时动态链接：将各目标模块装入内存时，边装入便链接。
• 运行时动态链接：在程序执行中需要该目标模块时才对它进行链接，便于修改和更新，便于实现对目标模块的共享。

内存管理

操作系统负责内存空间的分配与回收；

操作系统需要提供某种技术从逻辑上对内存进行扩充；

操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址转换(三种装入方式)；

操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行，互不干扰：法一：在CPU中设置一对上、下限寄存器，存放进程的上下限地址。进程的指令要访问某个地址时，CPU检查是否越界。法二：采用重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)进行越界检查。重定位寄存器中存放的进程是起始物理地址；界地址寄存器中存放的是进程最大的逻辑地址。

覆盖与交换(实现内存扩充)

覆盖：

解决”程序大小超过物理内存总和“的问题。将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段需要时调用。

内存中分为一个”固定区“和若干个”覆盖区“。需要常驻内存的段放在”固定区中“，调入后就不再调出(除非运行结束)，不常用的段放在”覆盖区“，需要用到时调入内存，用不到时调出内存。按照自身逻辑结构，让那些不可能被同时访问的程序段共享一个覆盖区。必须有程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担。

交换：

内存紧张时，系统将内存中的某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)中级调度。暂时换出外存等待的进程状态为挂起态，进一步细分为阻塞挂起和就绪挂起。

在外存的什么位置保存被换出的进程？具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换区的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，通常采用连续分配方式。

什么时候交换？交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。

换出哪些进程？可优先换出阻塞进程；可换出优先级低的进程；为了防止低优先级的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。

覆盖与交换的区别：

覆盖是同一程序或进程中的；交换是在不同进程(或作业)之间的。

连续分配管理方式(内存空间的分配与回收)

单一连续分配：

内存被分为系统区和用户区。系统区常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个内存空间。

优点：实现简单，无外部碎片；可采用覆盖技术扩充内存，不一定要采取内存保护。

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储利用率极低。

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上就是内部碎片。

固定区分配：

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。

若分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个对象的场合。

若分区大小不等：增加了灵活性，可以满足不同的大小的进程的需求，根据常在系统中运行的作业大小情况进行划分。

操作系统需要建立一个数据结构---分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小，起始地址，状态(是否已满)。

优点：实现简单，无外部碎片。

缺点：当用户程序太大时可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但会降低性能；会产生内部碎片，内存利用率低。

动态区分配(可变分区分配)：

不预先划分内存分区，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数量是可变的。

如何记录内存的使用情况：1.空闲分区表：每个空闲分区对应一个表项，表项包含分区号，分区大小，分区起始地址等信息。2.空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针，起始部分还可以记录分区大小等信息。

没有内部碎片但是有外部碎片。

外部碎片：指内存中的某些空间分区由于太小而难以利用。

在动态分区分配方式中2当很多个空间都能满足需求是应如何选择？

动态分区分配算法：

• 首次适应算法FF：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区的地址按递增的顺序排列，每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个分区。
• 最佳适应算法：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域，因此为了保证当大进程到来时能有连续的大片空间，可以尽可能多的留下大片的空闲区，即优先使用更小的空闲区。空闲区接受容量按递增顺序链接，每次分配内存时顺序查找空闲链表或空闲分区表，找到大小满足要求的第一个空闲分区。会产生很多外部碎片。
• 最坏适应算法：为了解决最佳适应算法的问题，在每次分配时优先使用最大的空闲连续空闲区，这样分配后的剩余空闲区不会太小，更方便使用空闲分区按容量递减的顺序链接，每次分配内存时顺序查找空闲分区链或空闲分区表，找到大小满足要求的第一个空闲区。但如果之后有大进程到达没有空闲分区可用了。
• 邻近适应算法：首次适应算法每次都从链头开始查找，这会导致低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始查找，就能解决上述问题，空闲分区以地址递增的顺序排列，每次分配内存时从上次查找结束的位置开始查找空闲分区链或空闲分区表，找到大小满足要求的第一个空闲分区。

非连续分配管理方式

基本分页存储管理

分页存储

将内存空间分为一个个大小相等的分区，每个分区就是一个”页框“(又称页帧，内存块，物理块，物理页面)，每一个页框有一个编号，即”页框号“(又称页帧号，内存块号，物理块号，物理页号)，页框号从0开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个”页“或”页面“，每个页面有一个编号即”页号“，从0开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个个页框中。进程的页面与内存的页框有一一对应的关系，各页面不必连续存放，可以放到不相邻的页框中。

如何实现地址的转换？1.确定逻辑地址A对应的页号P；2.查页表找到P号页面在内存中的起始地址；3.确定逻辑地址A的页内偏移量W。逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W。

例：在某计算机系统中，页面大小是50B，某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号，页内偏移量是？页号=逻辑地址/页面大小=110/50=2；页内偏移量=逻辑地址%页面大小=110%50=10。

如果每个页面大小为2^k B，用二进制数表示逻辑地址，则末尾k位用来表示页内偏移量W，其余为页号。如果有k为表示页内偏移量，则说明该系统中一个页面大小是2^k个内存单元，如果有m位表示页号，则说明在该系统中一个进程最多允许2^m个页面。

 基本地址变换机构

借助进程的页表将逻辑地址转换为物理地址，通常在系统中设置一个页表寄存器(PTR)存放页表在内存中的起始地址F和页表长度M。进程来执行时，页表的起始地址和页表长度放在PCB中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

1. 计算页号P和页内偏移量W。
2. 比较页号P和页表长度M，若P>=M则产生越界中断，否则继续执行。(页号是从0开始的，而页表长度至少是1，所以P=M也会产生越界)。
3. 页表中页号P对应的页表项地址=页表起始地址+P*页表项长度。取出该页表项内容b即为内存块号。
4. 计算E=b*L+W。

具有快表的地址变换机构

块表又称联想寄存器，是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加块地址变换的速度。

地址变换过程：

1. CPU给出逻辑地址，由某个硬件算的页号，页内偏移量，将页号与快表中的所有页号进行比较。
2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存快号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。若快表命中，增访问某个逻辑地址仅需一次访问内存。
3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应的页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存的单元，因此，若快表未命中，则访问某个逻辑地址需要两次访存。在找到页表项后，应同时将其放入快表，以便后面可能的再次访问。若快表已满，则必须按照一定的算法对旧的页表进行替换。

局部性原理：

时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。因为程序中存在大量的循环。

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。因为很多数据在内存中都是连续存放的。

由于局部性原理，可能连续很多次查到的都是同一个页表项。

两级页表

页表必须连续存放，当页表很大时，需要占用很多个连续的页框。

将页表进行分组，使每个内存块刚好可以放入一个分组，为离散分配的页表再建一张页表，成为页目录表(外层页表，顶层页表)。

按照地址结构将逻辑地址拆分成三部分。从PCB中读出页表目录起始地址，再根据一级页号差页目录表，找到下一级页表在内存中存放的位置。根据二级页号查表，找到最终想要访问的内存号，结合页内偏移量的到物理地址。

若采用多级页表机制，则各页表项的大小不能超过一个页面。

基本分段存储管理

分段：进程的地址空间按照程序自身的逻辑关系划分为若干个段。每个段都有一个段名，每段从0开始编址。

内存分配规则：以段位单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

段表

 分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)组成。段号的位数决定了每个进程最多可以分为几段；段内地址决定了每个段的最大长度；每个段对应一个段表项，其中记录了该段在内存中的起始位置(基址)和段的长度

各个段表项的长度是相同的，因此段号是隐含的，不占用存储空间。若段表存放的起始地址为M，则K号段对应的表项存放的地址为M+K*段表项的长度。

地址转换：

1. 根据逻辑地址得到段号，段内地址
2. 判断段号是否越界，若越界则产生越界中断，否则继续执行
3. 查询中段表，找到对应的段表项，段表项的存放地址为：段表始址+段表长度*段表项长度
4. 检查段内地址是否越界，若超过则产生越界中断
5. 计算得到物理地址：段基址+段内地址
6. 访问目标内存单元

分段分页管理的对比：

• 页是信息的物理单位。分页的主要目的是为了实现离散分配。提高内存利用率，分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。段是信息的逻辑单位。分段的主要目的是更好的满足用户需求，一个段通常包含着一组属于一个逻辑模块的信息。分段是对用户可见的，用户编程时需显示的给出段名。
• 页的大小固定且由系统决定。段的长度不固定，决定于用户编写的程序。
• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地址时既要给出段名也要给出段内地址。
• 分段比分页更容易实现信息的共存和保护。不能修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的，可修改的代码不能共享。

段页式存储管理

将进程按逻辑模块分段，再将各段分页，再将内存空间分为大小相同的内存块(页框/页帧/物理块)。

 段号的位数决定了每个进程最多可分为几个段。

段内页号位数决定了每个段最大有多少页。

段内地址(页内偏移量)决定了页面大小，内存块大小是多少。

每个段对应一个段表项，每个段表项由段号，页表长度，页表存放块号组成。每个段表项长度相等，段号隐藏。每个页面对应一个页表项，每个页表由页号，页面存放的内存块号组成，每个页表项的长度相等，页号隐藏。

地址变换：

1. 根据逻辑地址得到段号，页号，页内偏移量。
2. 判断段号是否越界。
3. 查询段表，找到相对应的段表项，段表项的存放地址=段表始址=段号*长度。
4. 检查页号是否越界。
5. 根据页表存放块号，段内页号查询页表，找到对应表项。
6. 根据内存块号，页内偏移量得到物理地址

访问一个逻辑单元需访存3次：第一次段表，第二次页表，第三次目标单元。

虚拟内存

基本概念

传统管理方式的特征：

一次性：作业必须一次性全部装入内存后才能开始运行，这会造成两个问题：1.作业很大时，不能全部装入内存，导致大作业无法运行；2.当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发下降。

驻留性：一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束。

虚拟内存的定义：

基于局部性原理，在程序装入时，可将程序中很快用到的部分装入内存，暂时用不到的部分留在外存。

在程序执行过程中，当所有访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

虚拟内存的特征：

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入
• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中将作业换入换出
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存的容量远大于实际容量

虚拟内存的实现：

请求分页存储管理，请求分段存储管理，请求段页式存储管理

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页功能)；内存空间不够时，将内存中暂时不用的信息换出到外存(页面置换功能)。

请求分页管理方式

页表机制：

 状态位：是否已调入内存

访问字段：记录最近被访问过几次，或记录上次访问的时间，共置换算法换出页面使参考

修改位：页面调入内存后是否被修改过

外存地址：页面在外存中存放的地址

缺页中断机构：

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

此时，缺页的进程阻塞，放入阻塞队列，调页完成完成之后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则需要将其写回外存。

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，属于内中断。

地址变换机构：

找到页表项检查页面是否在内存中：若页面不存在，请求调页；若内存空间不够，换出页面。页面调入内存后，修改相应页表项。

页面置换算法

最佳置换算法OPT：

优先淘汰最长时间内不会被访问的页面。缺页率最小，性能最好，但无法实现。

先进先出置换算法FIFO：

优先淘汰最先进入内存的页面。实现简单，但性能差，可能出现Belady异常(页框增多缺页次数反而增多)

最久未使用置换算法LRU：

优先淘汰最近最久没访问的页面。性能好，但需要硬件支持，算法开销大。

时钟置换算法CLOCK(URN)：

每个页面都与一个访问位相关联，初始值为0。当页面被访问时置为1，循环扫描各页面，第一轮淘汰访问位为0的页；扫描过程中若为1，重新置为0。若第一轮没选中，则进行第二轮扫描。实现简单，算法开销小，但未考虑页面是否被修改过。

改进型CLOCK：

采用(访问位，修改位)的形式表述，则：第一轮淘汰(0，0)，第二轮淘汰(0，1)，将被扫描过的页面的访问位置0。第三轮淘汰(0，0)，第四轮淘汰(0，1)。算法开销小，性能也不错。

页面分配策略，置换策略

驻留集：

指请求分页存储管理中各进程分配的物理块(内存块)的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要花很多时间来处理缺页，实际用于推进进程的时间很少；若驻留集太大，又会导致多道程序并发执行下降，资源利用率下降。

页面分配、置换策略：

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，即驻留集大小不变。

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做出适当的增加或减少，即驻留集大小可变。

局部置换：发生缺页时，只能选进程自己的物理块进行置换

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给却也进程。

• 固定分配局部置换(固定分配没有全局置换!)：进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的某一页。缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。
• 可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。
• 可变分配全局置换：只要缺页就分配新的物理块，可能来自空闲物理块，也可能需要换出别的进程页面。

何时调入页面？

• 预调页策略：根据局部性原理(主要指空间局部性)，一次性调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没有被访问过，则又是低效的。因此可预测不久之后可能访问到的页面，将他们预先调入内存，但预测成功率只有50%，主要用于进程的首次调入，运行前调入
• 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。I/O开销大，运行时调入

从何处调入页面：

将磁盘分为对换区和文件区。

对换区：读/写速度更快，采用连续分配方式。

文件区：读/写速度更慢，采用离散分配方式。

• 系统拥有足够的对换区间：页面的调入调出都是在内存与对换区之间进行，保证页面的调入，调出速度很快。在进程运行前，将进程相关的数据从文件区复制到对换区。
• 系统缺少足够的对换区：不会修改的数据直接从文件区调入，可能被修改的部分换出时需写回磁盘对换区，下次需要时从对换区调入。

UNIX方式中，运行之前进程有关的数据全部存放在文件区，故用来使用的页面都可以从文件区调用。若被使用过的页面需换出，则写回对换区，下次需要时再从对换区调入。

抖动(颠簸)现象：刚刚换出的页面马上又要换入内存，刚刚换入内存的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，主要原因是分给进程的物理块不够。

工作集：指在某一段时间间隔李2，进程时间访问页面的集合。驻留集大小一般不能小于工作集的大小。

内存映射文件

操作系统向上层程序员提供的功能(系统调用)。方便程序员访问文件数据，方便进程共享同一个文件。

特性：

• 进程可使用系统调用请求操作系统将文件映射到进程的虚拟地址空间。
• 以访问内存的方式读写文件
• 进程关闭文件时，操作系统负责将文件数据写回磁盘，并解除内存映射。
• 多个进程可以映射同一个文件，方便共享。

优点：程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可。文件数据的读写完全由操作系统负责，I/O效率可以由操作系统负责优化。