操作系统内存基础

1、1 1第四章：存储器管理2 2内容内容存储器的层次结构程序的装入与链接连续分配方式基本分页存储管理方式基本分段存储管理方式虚拟存储器的基本概念请求分页方式页面置换算法存储管理请求分段存储管理3 3存储器的层次结构理想状态下，程序员对内存的要求是： 大容量, 高速度, 和低价格现实状况是: 内存架构 CPU寄存器: 低容量、高速度、高价格 主存: 中容量、中速度、中价格 辅存: 大容量、低速度、低成本存储器层次架构寄存器主存（高速缓存、内存、磁盘缓存）辅存（磁盘、可移动存储介质）更大的存储空间更快的访问速度4 4 1. 处理器寄存器处理器寄存器用于存储处理器中与控制流和数据流相关的信息。访问速度

2、最快，价格十分昂贵，存储空间非常有限，只能存储少量信息。2. 高速缓存高速缓存为了解决处理器与内存之间速度不匹配而引入的存储空间。其存储容量比处理器寄存器大，访问速度比内存快。如果高速缓存的访问命中率高，则处理器从整体上以接近高速缓存的速度访问存储器，明显快于访问内存。存储器的层次结构5 53.3.内存内存也称为主存。内存中存放有处理器执行时所需要的代码和数据。内存空间远远大于高速缓存空间。一个计算机系统中所配置内存的大小是衡量计算机系统性能的一个非常重要的指标。4.4.外存外存外存是计算机系统中最大规模的存储器，存储有计算机系统所需要的各种软件资源。包括各种磁盘、磁带、光盘以及其他移动存储设

3、备。磁盘中的硬盘磁盘中的硬盘是计算机系统中大量联机信息的保存者是计算机系统中大量联机信息的保存者。在存储器管理和设备管理中，硬盘又被作为内存的补充，实现虚拟存储器和虚拟设备的管理。存储器的层次结构6 6物理地址 从内部结构上看，计算机存储器由大量的字节阵列或字阵列组成，每个字节或字都有自己的地址，要访问存储器中的信息必须知道信息的地址。计算机的内存也称为物理内存计算机的内存也称为物理内存，其地址从最低开始到最高上界，按照顺序编号，是一个一维线性存储空间。内存中的地址称为物理地址物理地址。 存储器的层次结构7 7地址空间 在操作系统中，存储器管理功能负责为进程分配和回收内存，实现内存空间在时间和

4、空间上的复用，在某一进程结束或撤销后，进程的内存空间可以由其它进程覆盖； 当内存空间占满时，通过外存与内存的对换实现内存空间的虚拟扩充。存储器管理在提供多进程共享内存的同时，还通过可靠的隔离机制阻止一个进程读写另一个进程的内存，实现内存地址空间的保护。存储器的层次结构8 8用户用高级语言编写的源程序，需要经过编译、链接和装入编译、链接和装入之后，才能被处理器运行运行。编译编译将用户用高级语言编写的源程序转换为目标模块；链接链接将用户程序需要的所有目标模块链接在一起，形成一个可执行模块，即装入模块；装入装入将装入模块放入内存。 用户程序的编译、链接和装入过程之间的关系下图所示。经过编译后源程序成

5、为目标模块，多个目标模块链接成一个绝对的装入模块。在进程被分配内存后，装入模块被装入到内存中。程序的装入和链接9 9程序的编译、链接、装入程序的装入和链接1010 在程序装入内存前，装入模块中给出的程序地址为程序的逻逻辑地址或相对地址辑地址或相对地址。一个用户作业的所有装入模块的逻辑地址集合称为该作业的逻辑地址空间逻辑地址空间。 当用户作业被装入内存后，其物理地址由用户作业所对应的进程物理地址体现，进程物理地址的总体构成了用户程序实际运行的物理地址空间物理地址空间。 为了保证用户作业的正确运行，必须把用户作业的逻辑地址转换为物理地址，这一工作由操作系统存储管理器在作业装入内存的过程中完成，称为

6、地址变换或重定位地址变换或重定位。程序的装入和链接11111 1链接链接 链接是将用户程序所需要的所有目标模块链接在一起的过程。 链接的方式有静态链接静态链接、装入时动态链接装入时动态链接和运行时动态链接运行时动态链接。程序的装入和链接1212（1）静态链接 静态链接指链接过程在程序装入内存前完成并形成整个程序静态链接指链接过程在程序装入内存前完成并形成整个程序的逻辑地址空间。的逻辑地址空间。 通常，由编译产生的所有目标模块的起始地址可能都是从0开始，每个模块中的程序代码地址都是相对于模块的起始地址。 例如，如果一个用户作业由3个目标模块A、B、C组成，长度分别为m、n、k，每个模块在链接前的

7、起始地址都从0开始，如下图（a）所示。 经过静态链接后，模块A、B和C被链接为一个大的模块，原来的模块B和C的起始地址根据模块A的地址进行了调整，分别为m和m + n，链接后的情况如下图（b）所示。 程序的装入和链接1313程序链接程序的装入和链接1414（2）装入时动态链接 装入时动态链接将目标模块的链接过程放在这些目标模块装入装入时动态链接将目标模块的链接过程放在这些目标模块装入内存的过程中完成。内存的过程中完成。 装入时动态链接的优点如下：便于模块的修改和更新 静态链接会使得系统每次修改或更新某个模块，都要重新完成所有模块的链接。装入时动态链接，只要模块没有装入内存，系统都可以随时修改和

8、更新模块。便于实现目标模块的共享 静态链接只要有某个目标模块被多个模块共享，会多次链接该目标模块，装入内存后，在内存中存在共享模块的多个副本。而装入时动态链接将共享模块只放一个版本在内存中，节约了内存，实现了真正的模块共享。程序的装入和链接1515（3）运行时动态链接 运行时动态链接是一种较先进的链接方式，在程序装入内存时不链接模块，将链接过程推迟到程序运行时进行将链接过程推迟到程序运行时进行。在程序运行过程中，若发现被调用的某个模块尚未装入内存，操作系统找到该模块，将其装入内存，同时链接到调用模块上。 运行时动态链接的优点运行时动态链接的优点除了具有装入时动态链接的优点外，还可以做到不运行的

9、模块，不需要链接。与静态链接和装入时动态链接相比，更节约内存。静态链接和装入时动态链接都需要将程序的全部目标模块进行链接，使得某些在运行时不需要的目标模块也进行了链接，造成了内存空间的浪费。程序的装入和链接16162 2装入装入 目标模块放入内存的过程为装入过程。 装入过程实现了程序的逻辑地址和物理地址之间的变换。 装入过程有三种方式，分别为：绝对装入方式、静态重定绝对装入方式、静态重定位装入方式和动态重定位装入方式位装入方式和动态重定位装入方式。程序的装入和链接1717（1）绝对装入方式 在编译前程序员写源程序的时候如果知道程序所对应的进程驻留在内存中的物理地址，则链接会按照模块在内存中的物

10、理地址生成逻辑地址，装入程序根据装入模块中的逻辑地址将程序装入内存，这样的装入方式称为绝对装入方式绝对装入方式。绝对装入方式下程序的逻辑地址和物理地址相同。 在前面3个目标模块A、B、C组成的作业中，如果链接后生成的逻辑地址从0开始，到（m + n + k 1）结束，则绝对装入方式将该装入模块装入内存时的物理地址从0开始，到（m + n + k 1）结束。 程序的装入和链接1818 绝对装入方式对程序员的要求很高。程序员在编程时必须熟悉内存的使用情况，知道程序的物理地址，能够在内存中调整程序和数据的地址。绝对装入方式适合用于实时操作系统和嵌入绝对装入方式适合用于实时操作系统和嵌入式操作系统式操

11、作系统，其他的操作系统很少采用。程序的装入和链接1919（2）静态重定位装入方式 静态重定位装入方式将程序装入内存时，系统根据内存当时的实际使用情况，将装入模块装入到内存的适当位置。 “重定位重定位”是指程序在内存中的物理地址不再是原来程序的逻辑地址，而是根据内存的情况被重新定位。 “静态静态”指的是用户程序从逻辑地址到物理地址的变换过程在程序执行前完成，在执行期间不再改变。如果物理地址要发生改变，则需要进行重新装入。 程序的装入和链接2020 在3个目标模块组成的用户作业中，链接后生成的逻辑地址从0开始，到（m + n + k 1）结束。在装入内存时，如果内存只能从内存地址1 000开始容纳

12、该作业的目标模块，则静态重定位装入方式下该程序装入内存时的物理地址为从1 000开始，到（1 000 + m + n + k1）结束，如下图所示。静态重定位装入方式程序的装入和链接2121 静态重定位装入方式的优点是实现简单，从逻辑地址到物理地址变换不需要专门的硬件便能完成； 缺点是程序在执行过程中不能在内存中移动。程序的装入和链接2222（3）动态重定位装入方式 在多道程序环境下，静态重定位装入方式虽然可以在用户程序运行前根据内存的使用情况将用户程序装入内存，但是程序在程序在运行时不能在内存中移动或重新定位地址运行时不能在内存中移动或重新定位地址。因此，静态重定位限制了程序运行时系统对内存的

13、调整，不能适应虚拟存储器管理等进一步的存储管理。这是因为在虚拟存储器管理中，需要用户程序的代码多次换出换入内存，每次程序代码进入内存后的地址可能不同。 而如果采用动态重定位装入方式则可以避免这种情况，动态重定位装入方式可以使程序运行时重新定位程序在内存中的地址，实现内存管理的灵活性，提高内存空间的利用率。 程序的装入和链接2323 动态重定位的优点是内存的使用灵活有效，容易实现内存的动态扩充和共享； 缺点是实现过程中需要附加硬件（重定位寄存器）支持，内存管理更加复杂。程序的装入和链接2424存储器管理目标达到两个目标: 地址独立地址独立程序发出的地址应与物理主存地址无关程序发出的地址应与物理主

14、存地址无关 地址保护地址保护一个进程不能访问另一个进程的地址空间一个进程不能访问另一个进程的地址空间2525连续分配方式连续分配方式 指为一个用户程序分配一个连续的内存空间。可以被进一步划分为: 单一连续分配应用于单道编程 固定分区分配应用于多道编程 动态分区分配应用于多道编程 动态重定位分区分配2626单一连续分配最简单的存储管理方式 只用于单用户、单任务的操作系统中内存分为：系统区和用户区 系统区系统区仅提供给操作系统使用 用户区用户区提供给用户使用内存组织方式（操作系统和用户进程）0 xFFF0OS in RAMUserprogram2727单一连续分配达到地址独立 将用户进程装载到同一

15、个物理地址上 物理地址可以被事先计算出来达到地址保护: 整个系统就只有一个用户程序!单一连续分配的问题? 将整个程序加载到内存空间 (没有足够的空间?) 浪费资源 (CPU 和 Memory)2828固定分区分配多道编程中最简单的内存管理方式 将内存划分为几个固定的区域，可同时装入多个作业/任务 程序被加载到固定的分区分区大小 分区大小相等缺乏灵活性 分区大小不等多个较小的分区、适量的中等分区及少量的大分区2929固定分区分配内存分配将分区按大小排队，并将其地址、分配标识做记录分区号大小（K)起址（K）状态11220已分配23232已分配36464已分配4128128未分配分区说明表3030操

16、作系统操作系统作业作业A A作业作业B B作业作业C C20K32K64K128K256K分配情况固定分区分配3131固定分区分配将程序加载到固定内存分区的两种选择 给每个分区一个队列新进程被分配到固定的分区 单一输入队列新进程可以进入任何一个分区假定分区有足够的空间加载进程3232固定分区分配3333固定分区分配与单用户连续管理方式相同，固定分区分配中的地址变换也有静态重定位方式和动态重定位方式地址变换借助于两个寄存器：上限寄存器和下限寄存器。下限寄存器中的地址作为基地址，进程的逻辑地址加下限寄存器中的基址为内存中的物理地址。将物理地址与上限寄存器中的地址比较，如果物理地址落入上、下限寄存器

17、地址中，则进程的物理地址有效。否则，进程的物理地址越界，拒绝将分区分配给进程。3434 上、下限寄存器起到保护分区的作用。固定分区地址变换过程如下图所示。固定分区地址变换固定分区分配3535固定分区的划分在操作系统初始化时完成。在系统启动时，系统操作员根据系统运行作业的需要划分分区大小。当用户作业进入分区时，按照用户作业的大小从分区表中选择空闲分区。与单一连续分配方式比较，固定分区分配方式使得系统的资源利用率和吞吐量有一定程度的提高。固定分区分配3636固定分区分配的缺点：固定分区分配的缺点：内存利用率不高内存利用率不高 由于分区大小固定，装入进程的大小受到限制。超过最大分区的进程，只有采用覆

18、盖技术才能在内存中运行，降低了系统的运行效率；较小的进程，造成内存“碎片”，降低了内存的利用率。划分分区大小困难划分分区大小困难 划分分区的大小对系统性能有很大影响，合理划分分区的大小很困难。需要预先知道进程大小需要预先知道进程大小 固定分区分配方式适合进程大小已知的情况，如果进程大小不知或进程大小变化很大，则采用固定分区分配不是特别适合。 固定分区分配3737动态分区分配根据作业的实际需要，动态地为之分配内存空间 不在系统初始化时进行分区划分，而在每个用户作业装入内存时，根据作业的大小和内存的使用情况，动态划分分区并分配。 克服了固定分区分配的内存利用率低的问题，更适合多道程序环境。 为了完

19、成有效分配和回收分区，需要构建对分区信息进行描述需要构建对分区信息进行描述的数据结构的数据结构，并在已知分区数据结构的基础上完成分区分配算分区分配算法法与回收方法回收方法。3838动态分区分配数据结构 空闲分区表：包括分区号、分区始址、分区大小等 空闲分区链：空闲分区链是空闲分区最常用的组织形式，操作系统将所有的空闲分区通过前向和后向指针串在一起组成双向空闲分区链双向空闲分区链。前向指针前向指针N N个字节可用个字节可用后向指针后向指针N+2N+2N+2N+20 0（分配（分配标识）标识）0 03939动态分区分配分区分配算法1、首次适应法 首先将空闲分区按照地址递增的顺序地址递增的顺序组织成

20、空闲分区链。 为作业分配内存时，系统根据作业大小，从空闲分区链的第一个空闲分区开始查找，只要找到第一个满足作业大小的空闲分区，从该空闲分区中分割一部分分配给作业，另一部分仍作为空闲分区； 如果空闲分区链全部查找完也不能满足作业要求，则系统不能为作业分配内存。4040 该分区分配算法首先利用内存中的低地址空闲分区，保留了高地址空闲分区。该分区分配算法存在的缺点如下： 系统每次都是从链首开始查找空闲分区，低地址段的大空闲分区被分配或被分割，剩下了小空闲分区或空闲分区“碎片”； 系统每次从链首开始查找空闲分区，增加查找开销。动态分区分配41412、循环首次适应算法 将空闲分区按照地址递增的顺序组织按

21、照地址递增的顺序组织成空闲分区链 为作业分配内存时，系统不是从空闲分区链的第一个空闲分区开始查找，而是从空闲分区链上，上次为作业分配分区后的位从空闲分区链上，上次为作业分配分区后的位置开始查找置开始查找，找到第一个满足作业大小的空闲分区，分割并分配该空闲分区。 如果找到空闲分区链的链尾还没有找到，系统可以再从链首开始查找。动态分区分配 该分区分配算法虽然克服了首次适应算法的缺点，使得空克服了首次适应算法的缺点，使得空闲分区的分布更加均匀闲分区的分布更加均匀，查找空闲分区所需要的时间更短，但是，空闲分区链中的小分区或“碎片”问题仍然不能解决。42423、最佳适应算法 扫描整个空闲分区链，从中挑选

22、出一个满足进程要求的最小分挑选出一个满足进程要求的最小分区区进行分配，避免分割大空闲分区，使得内存“碎片”更小。 空闲分区链需要按照分区大小递增的顺序组织分区大小递增的顺序组织，每次查找时从链首的最小分区开始，直到找到第一个满足作业要求的分区为止。因此，被分配的空闲分区是大小最适合的分区。动态分区分配 该算法克服了首次适应算法和循环首次适应算法的缺点，是一种较优的分区分配算法。该算法由于找到的空闲分区是最该算法由于找到的空闲分区是最小能够满足要求的分区，剩余的空闲分区很小小能够满足要求的分区，剩余的空闲分区很小，这一部分很小的“碎片”，难以再次利用。43434、最坏适应算法挑选满足作业要求的最

23、大分区挑选满足作业要求的最大分区，使得分配的空闲分区分配给作业后剩下的部分比较大，能够再作为空闲分区进行分配。减少了内存中“碎片”的大小和个数。 空闲分区链需要按照分区大小递减的顺序组织按照分区大小递减的顺序组织，每次从链首最大的分区开始分配，只要能够满足作业要求就分配。动态分区分配该算法存在的问题是最后会导致系统缺乏较大的空闲分区。44445、快速适应算法 将空闲分区根据容量大小进行分类容量大小进行分类，并单独设立空闲分区链。 内存中设立一张管理索引表管理索引表，每一个表项对应了空闲分区类型。 空闲分区管理索引表有每个空闲分区链的长度范围和开始指针。为作业分配内存时，首先根据作业大小查找空闲

24、分区管理索引表，得到空闲分区链的起始指针，然后再从相应的空闲分区链中为作业分配一个空闲分区动态分区分配 该算法的优点是能够快速得到空闲分区，查找效率高，不会分割空闲分区，并能够保留大的空闲分区，对大的作业也不会产生内存“碎片”。该算法的缺点是回收分区较困难，算法复杂，系统的开销较大。4545分区分配和回收操作分区分配和回收操作分区分配： 分区分配操作首先根据分配算法从空闲分区表中查找所需大小首先根据分配算法从空闲分区表中查找所需大小的分区的分区，如果用户进程的大小为u.size，空闲分区的大小为m.size，则m.size与u.size之差为分配后的剩余部分，首次适应法和循环首次适应法只需要该

25、差值大于0即可，最佳适应法需要该差值为最小，最差适应法需要该差值为最大。如果能够分配分区，则分区分配成功后会将分配区的首址返回给分配过程的调用者。动态分区分配4646内存分配流程4747动态分区分配分区回收 当作业完成时会释放内存，系统需要回收为作业分配的内存，回收的内存需要进入空闲分区链中才能被再次分配。 分区回收时根据回收区的首址，采取不同的回收方法。4848动态分区分配四种情况： 上邻空闲区：合并，修改大小 下邻空闲区：合并，修改大小、首址 上、下邻空闲区：合并，修改大小 不邻接：则建立一新表项，插入空闲链的适当位置。F1F1回收区回收区（a）回收区回收区F2F2（b）F1F1回收区回收

26、区F2F2（c）内存回收时的情况内存回收时的情况4949动态分区分配存在的问题 很难增长进程空间如栈、数据等 解决方案:为增长的数据段分配空间为增长的栈和数据段分配空间5050动态分区分配5151可重定位分区分配动态重定位的引入 连续分配方式中，总量大于作业大小的多个小分区不能容纳作业。 操作系统操作系统用户程序用户程序1 110kb10kb用户程序用户程序3 330kb30kb用户程序用户程序6 614kb14kb用户程序用户程序9 926kb26kb操作系统操作系统用户程序用户程序1 1用户程序用户程序3 3用户程序用户程序6 6用户程序用户程序9 95252可重定位分区分配紧凑 通过作业移动将原来分散的小分区拼接成一个大分区 作业的移动需重定位。是动态的（因作业已经装入）。5353可重定位分区分配动