操作系统课件第4章

1、第四章存储器管理4.1 存存 储储 器器 的的 层层 次次 结结 构构多级存储器结构多级存储器结构存储层次：存储层次：CPU寄存器寄存器，主存主存，辅存辅存。高档计算机中：寄存器、高速缓存、主存储器、磁盘缓存、固定高档计算机中：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质。磁盘、可移动存储介质。计算机系统存储层次示意计算机系统存储层次示意 在存储层次中越往上，存储在存储层次中越往上，存储介质的访问速度越快，价格也介质的访问速度越快，价格也越高，相对存储容量也越小。越高，相对存储容量也越小。CPU寄存器寄存器主存主存辅存辅存n3主存储器主存储器主存储器主存储器( (内存内存)

2、)保存进程运行时的程序和数据。保存进程运行时的程序和数据。 寄存器访问速度最快寄存器访问速度最快,协调协调CPU工作，价格昂贵，容量很小。工作，价格昂贵，容量很小。n1. 寄存器寄存器n2 2高速缓存高速缓存容量大于寄存器容量大于寄存器,小于主存。小于主存。 访问速度比主存快。将经常访访问速度比主存快。将经常访问的信息存放在高速缓存中。问的信息存放在高速缓存中。n4磁盘缓存磁盘缓存利用主存中的存储空间，暂时存放从磁盘中读出利用主存中的存储空间，暂时存放从磁盘中读出(或写入或写入)的的信息。信息。台式台式PCPC机内存插槽和内存条机内存插槽和内存条4.2 程程 序序 的的 装装 入入 和和 链链

3、 接接 编译，源代码编译，源代码目标模块。目标模块。 链接，目标模块，库函数链接，目标模块，库函数装入模块。装入模块。 装入，装入模块装入，装入模块内存。内存。第一步第一步编译程序编译程序产生的目产生的目标模块标模块库库内存内存链接链接程序程序装入装入程序程序装入模块装入模块 第二步第二步第三步第三步 程序的装入程序的装入n1. 绝对装入方式绝对装入方式按照按照绝对地址绝对地址装入。装入。只适用于单道程序环境。只适用于单道程序环境。n2可重定位装入方式可重定位装入方式首址可以首址可以平移。平移。装入时地装入时地址修改。址修改。整体搬移整体搬移连续存放连续存放。n3动态运行时装入方式动态运行时装

4、入方式装入内存后的所有地址都是相对地址。地址修改推迟到程序执装入内存后的所有地址都是相对地址。地址修改推迟到程序执行时进行行时进行 ，动态重定位。，动态重定位。装入装入时地时地址不址不变，变，运行运行时地时地址修址修改。改。LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作 业 地 址 空 间内 存 空 间程序的链接程序的链接 1. 静态链接方式（在外存形成装入模块）静态链接方式（在外存形成装入模块）模块 ACALL B；Return；0L 1模块 BCALL C；Return；0M 1模块 CReturn；0N 10模

5、块 AJSR“L”Return；L 1模块 BJSR“L M”Return；LL M 1L ML M N 1模块 CReturn；(a) 目标模块(b) 装入模块2. 装入时动态链接（进内存后形成装入模块）装入时动态链接（进内存后形成装入模块）装入时动态链接方式有以下优点：装入时动态链接方式有以下优点：(1)便于修改和更新。便于修改和更新。 (2) 便于实现对目标模块的共享。便于实现对目标模块的共享。 高档操作高档操作系统流行系统流行方式方式Windows Windows LinuxLinux等通等通用技术用技术OSOS下存有下存有大量的大量的DLLDLL动态连接动态连接库文件。库文件。3.

6、运行时动态链接运行时动态链接执行过程中，当一个被调用模块尚未装入内存时，由执行过程中，当一个被调用模块尚未装入内存时，由OSOS找找到该模块并将之装入内存，到该模块并将之装入内存， 把它链接到调用者模块上。把它链接到调用者模块上。当前不用的目标模块，都不会进内存。加快程序的装入过当前不用的目标模块，都不会进内存。加快程序的装入过程，节省大量的内存空间。程，节省大量的内存空间。 高档操作系统流行方式高档操作系统流行方式Windows Windows 、LinuxLinux、SolarsSolars、MachMach等等OSOS通用的技术（使用通用的技术（使用DLLDLL文件）文件）4.3 连连

7、续续 分分 配配 方方 式式单一连续分配单一连续分配只能用于单用户、单任务操作系统中。内存分为系统区和用只能用于单用户、单任务操作系统中。内存分为系统区和用户区两部分。户区两部分。OSUSERAREA操作系统默认存操作系统默认存放在内存低端放在内存低端作业操作系统未用32 KB64 KB160 KB分配给用户作业的空间每次一个作业，每次一个作业，上一个完成退上一个完成退出，下一个才出，下一个才能进入能进入利用率极低利用率极低固定分区分配固定分区分配用户空间划分为若干个固定大小的区域，在每个分区中装入一用户空间划分为若干个固定大小的区域，在每个分区中装入一道作业，允许几道作业并发运行。道作业，允

8、许几道作业并发运行。 简单、可靠，但产生分区简单、可靠，但产生分区“内零头内零头”，内存利用效低。，内存利用效低。系统区系统区分区分区 1 1分区分区 4 4分区分区 5 5分区分区 2 2分区分区 3 3区号/键大小起址状态18 KB512K已分配232 KB520K已分配332 KB552K未分配4128 KB584K未分配5512 KB712K已分配系统区系统区作业作业 3 3分区分区 4 4作业作业 2 2作业作业 1 1分区分区 3 3动态分区分配动态分区分配根据进程的实际需要，动态地为之分配内存空间。根据进程的实际需要，动态地为之分配内存空间。(1)空闲分区表空闲分区表记录每个空闲

9、分区的情况。记录每个空闲分区的情况。 (2) 空闲分区链空闲分区链将所有的空闲分区链接成一个将所有的空闲分区链接成一个双向链双向链。前向指针0N个字节可用后向指针0N+2N+2当分区被分配出去以后，把状态当分区被分配出去以后，把状态位由位由“0”改为改为“1”，此时，前、，此时，前、后向指针已无意义。后向指针已无意义。OS区区Job1Job2Job3Job4Job5Job6OS区区Job1Job2Job3Job4Job5空闲分区链空闲分区链头指针头指针Job6分区分配算法分区分配算法1) 首次适应算法首次适应算法(first fit) 空闲分区链空闲分区链以地址递增的次序以地址递增的次序链接。

10、从链首开始顺序查找，直链接。从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给作业，余下的空的大小，从该分区中划出一块内存空间分配给作业，余下的空闲分区仍留在空闲链中。闲分区仍留在空闲链中。 该算法的优缺点：该算法的优缺点：为大作业分配大的内存空间创造了条件。为大作业分配大的内存空间创造了条件。低址部分不断被划分，会留下许多难以利用的、很小的空闲低址部分不断被划分，会留下许多难以利用的、很小的空闲分区。分区。新作业装入内存时，按照一定的分配算法，从空闲分区表或新作业装入内存时

11、，按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的分配算法：空闲分区链中选出一分区分配给该作业。常用的分配算法： 2) 循环首次适应算法循环首次适应算法(next fit) 将所有的将所有的空闲分区构成一个循环链表空闲分区构成一个循环链表。采用循环查找。采用循环查找方式，设置一个起始查寻指针，用于指示下一次起始查方式，设置一个起始查寻指针，用于指示下一次起始查寻的空闲分区。寻的空闲分区。该算法的优缺点：该算法的优缺点：能使内存中的空闲分区分布得更均能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏匀，从而减少了查找空闲分区时的开销，但这样

12、会缺乏大的空闲分区。大的空闲分区。为进程分配内存时，不再是每次都从链首开始查找，而是从为进程分配内存时，不再是每次都从链首开始查找，而是从上次找到空闲分区的下一个空闲分区开始查找，直到找到上次找到空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。一个能满足要求的空闲分区。3) 最佳适应算法最佳适应算法( (best fit) )将所有的空闲分区将所有的空闲分区按容量以从小到大的顺序形成空闲分区链按容量以从小到大的顺序形成空闲分区链。该算法的优缺点：该算法的优缺点：为大作业分配大的内存空间创造了条为大作业分配大的内存空间创造了条件。每次分配后所切割下来的剩余部分总是最小的，这样

13、，件。每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。在存储器中会留下许多难以利用的小空闲区。把能满足要求、又是最小的空闲分区分配给作业。把能满足要求、又是最小的空闲分区分配给作业。 4) 最坏适应算法最坏适应算法( (worst fit) ) 该算法要扫描整个空闲分区表或链表，总是挑选一个该算法要扫描整个空闲分区表或链表，总是挑选一个最最大的空闲区大的空闲区分割给作业使用，其优点是可使剩下的空闲区不分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，但查找效率很高。至于太小，产生碎片的几率最小，但查找效率很高。所有的空闲分区按容量从

14、大到小的顺序形成空闲分区链，查所有的空闲分区按容量从大到小的顺序形成空闲分区链，查找时只要看第一个分区能否满足作业要求。该算法的找时只要看第一个分区能否满足作业要求。该算法的缺点缺点是是它会使存储器中缺乏大的空闲分区。它会使存储器中缺乏大的空闲分区。 最坏适应算法与首次适应算法、循环首次适应算法、最最坏适应算法与首次适应算法、循环首次适应算法、最佳适应算法一起，也称为佳适应算法一起，也称为顺序搜索法顺序搜索法。 5) 快速适应算法快速适应算法( (quick fit) ) 该算法又称为分类搜索法，是将空闲分区根据其容量大该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有

15、相同容量的所有空闲分区，小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个单独设立一个空闲分区链表，这样，系统中存在多个空闲空闲分区链表分区链表，同时在内存中设立一张，同时在内存中设立一张管理索引表管理索引表。 该算法的该算法的优点优点是查找效率高，仅需要根据进程的长度，是查找效率高，仅需要根据进程的长度，找到能容纳它的最小空闲区链表即可；另外不会对任何分找到能容纳它的最小空闲区链表即可；另外不会对任何分区产生分割，满足对大空间的需求，不会产生内存碎片。区产生分割，满足对大空间的需求，不会产生内存碎片。 缺点缺点是在分区归还主存时算法复杂，系统开销

16、较大。是在分区归还主存时算法复杂，系统开销较大。可重定位分区分配可重定位分区分配操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a) 紧凑前(b) 紧凑后经过紧凑后，用户程序在经过紧凑后，用户程序在内存中的位置发生了变化，内存中的位置发生了变化，所以必须对移动了的程序所以必须对移动了的程序或数据进行重定位。或数据进行重定位。紧凑技术紧凑技术,也称为也称为“拼凑拼凑”技术，解决可变分区中产生的技术，解决可变分区中产生的“外零头外零头”。移动某些已分。移动某些已分配分区，使配分区，使“外零头外零头”

17、合并为一个大的连续空闲区。合并为一个大的连续空闲区。以时间和技术换以时间和技术换内存空间。内存空间。作业7(256 KB)(a)(b)(c)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS作业7 (256 KB)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB376 KB作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS可以装入作业可以装入作业7暂不能装入暂不能装入J7重定位

18、寄存器重定位寄存器，存放程序，存放程序(数据数据)在内存中的起始地址。程序在执在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址相加而形成的。动态重定位的实现原理动态重定位的实现原理365365LOAD 1,2500LOAD 1,2500500050002500250010001000365365LOAD 1,2500LOAD 1,250015000150001250012500100001000011000110002500相对地址相对地址10000重定位重定位寄存器寄存器处理机一侧处理机

19、一侧 存储器一侧存储器一侧作业作业J内存内存重定位是一种运算寻址，需硬件支持重定位是一种运算寻址，需硬件支持4.4基基 本本 分分 页页 存存 储储 管管 理理 方方 式式 将一个将一个进程的逻辑地址空间进程的逻辑地址空间分成若干个大小相等的分成若干个大小相等的片，称为片，称为页页，并为各页编号。，并为各页编号。 把把内存空间内存空间分成与页相同大小的若干个存储块，称分成与页相同大小的若干个存储块，称为为块块，同样予以编号。，同样予以编号。 页的大小通常为页的大小通常为512 B8 KB。若干个页分别装入可以不相邻接的物理块中。最后一若干个页分别装入可以不相邻接的物理块中。最后一页经常装不满一

20、块形成页经常装不满一块形成“页内碎片页内碎片”。 页式最先实现了作业空间的离散分配！页式最先实现了作业空间的离散分配！地址结构地址结构 页号页号 P 位移量位移量 W3112 110前一部分为前一部分为页号页号P，后一部分为位移量后一部分为位移量W(或称为或称为页内地址页内地址)。例：地址长度为例：地址长度为32位，位，011位为页内地址，位为页内地址，1231位为页号。位为页号。 若逻辑地址为若逻辑地址为A A，页的大小为，页的大小为L L，则页号，则页号P P和页内地址和页内地址d d可按下式求得：可按下式求得： APIN TLdA M O D L页号：页号：页面地址：页面地址：作业分页，

21、内存分块作业分页，内存分块页块等大，对应存放页块等大，对应存放建立页表，查表访问建立页表，查表访问页表页表页表放在内存中，它的页表放在内存中，它的作用作用是实现从页号到物理块号的地址映射。是实现从页号到物理块号的地址映射。 用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910页表的作用页表的作用 分页系统的地址变换机构分页系统的地址变换机构地址变换机构地址变换机构页表页表物理地址物理地址页表始址页表始址页表长度页表长度页表寄存器页表寄存器5201832018逻辑地址逻辑地址越界中断越界中断+块号块号页号页号5332712054.5基基

22、 本本 分分 段段 存存 储储 管管 理理 方方 式式作业的地址空间划分为若干个段，每个段都有自己的名字。通作业的地址空间划分为若干个段，每个段都有自己的名字。通常用一个段号来代替段名，每个段都是从常用一个段号来代替段名，每个段都是从0开始编址的。开始编址的。地址结构地址结构 段号段号S 段内位移量段内位移量W31 16 15 0 段表段表分段地址变换由段表实现，在作业被调入时，为其建立一张段表。分段地址变换由段表实现，在作业被调入时，为其建立一张段表。作业空间(MAIN)=0030 K(X)=1020 K(D)=2015 K(S)=3010 K30 K20 K15 K10 K40 K80 K

23、段长 基址段号(MAIN)=030 K(X)=120 K(D)=215 K(S)=310 K040 K80 K120 K150 K段表内存空间0123120 K150 K利用段表实现利用段表实现 地址映射地址映射每个段在表中占有一每个段在表中占有一个表项，其中记录了个表项，其中记录了该段在内存中的起始该段在内存中的起始地址地址( (又称为又称为“基址基址”) )和段的长度和段的长度程序按段存放程序按段存放运行查段表进行运行查段表进行地址变换机构地址变换机构分段系统的地址变换过程分段系统的地址变换过程 n 段号段号S 段表长度段表长度TL- 访问越界。否则，从段表访问越界。否则，从段表项中读出该

24、段在内存的起始地址。项中读出该段在内存的起始地址。n 段内地址段内地址d 段长段长SL-越界中断。否则，基址越界中断。否则，基址 + 段内地址段内地址d = 内存物理地址。内存物理地址。段表始址段表始址段表长度段表长度2100段表寄存器段表寄存器逻辑地址逻辑地址越界中断越界中断段长段长 基址基址段表段表段号段号01238292物理地址物理地址段号段号S S位移量位移量W W92002008K5004K6006K1K0111101110100000页号页号位移量位移量011001200011010001010页表页表0111101110011000不变不变(a)分页分页页号页号 块号块号0000

25、111101001000段号段号段内地址段内地址段表段表0000100011000100(a)分段分段0001011101110000001000000000010111100111100010000000100000段号段号 段长段长 基址基址分页和分段的主要区别分页和分段的主要区别分分 页页分 段信息的物理单位信息的逻辑单位出于系统管理的需要出于用户的需要大小固定由系统确定长度不固定由编译确定作业地址空间一维作业地址空间二维页内碎片外部碎片不易共享易共享页表较长，查找费时段表较短，查找速度快段页式存储管理方式段页式存储管理方式 将分页管理和分段管理的优点集中起来。将分页管理和分段管理的优点

26、集中起来。 即即对作业的地址空间分段，段内再分页对作业的地址空间分段，段内再分页。该作业有三个段，页面大小为该作业有三个段，页面大小为4KB。 0 4k 8k12k15k16k一段一段页页1 1页页2 2页页3 3页页三段三段 0 4k 8k10k12k0 0页页1 1页页2 2页页二段二段 0 4k 8k0 0页页1 1页页段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器段页式地址结构段页式地址结构 由段号由段号S、段内页号、段内页号P和页内地址和页内地址W三部分组成。三部分组成。通常，分段由程序员完成，分页由系统

27、自动完成。通常，分段由程序员完成，分页由系统自动完成。利用段表和页表实现地址映射利用段表和页表实现地址映射 地址变换过程地址变换过程段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度 段表寄存器段表寄存器 段段 表表 始始 址址段表长度段表长度TL段号段号S段页式系统中获得一条数据或指令，需访问内存几次？段页式系统中获得一条数据或指令，需访问内存几次？三次三次4.6 虚虚 拟拟 存存 储储 器器 的的 基基 本本 概概 念念常规存储器管理方式的特征常规存储器管理方式的特征1. 一次性一次性2.驻留性驻留性资源实体性和有限性资源实体性和

28、有限性局部性原理局部性原理在一较短的时间内，程序的执行仅局限于某个部分；相应地，在一较短的时间内，程序的执行仅局限于某个部分；相应地，它访问的存储空间也局限于某个区域。它访问的存储空间也局限于某个区域。(1)时间局部性时间局部性: 一个数据结构被访问，不久可能再次被访问。一个数据结构被访问，不久可能再次被访问。 典型原因：典型原因： 程序中存在大量的循环操作。程序中存在大量的循环操作。(2)空间局部性空间局部性:一段时间访问的地址可能集中在一定范围一段时间访问的地址可能集中在一定范围 。典型原因：程序顺序执行典型原因：程序顺序执行局部性原理是虚拟内存得以实现的本质局部性原理是虚拟内存得以实现的

29、本质虚拟存储器虚拟存储器实现思想实现思想：当进程运行时，先将：当进程运行时，先将一部分程序一部分程序装入内存，另一部装入内存，另一部分分暂时留在外存暂时留在外存，当要执行的指令不在内存时，由系统自动将，当要执行的指令不在内存时，由系统自动将它们它们从外存调入内存从外存调入内存。虚拟存储器定义：具有请求调入功能和置换功能，能从逻辑上虚拟存储器定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来使用，构成容量很大的机结合起来使用，构成容量很大的“内存内存”。虚拟存储器的特征虚拟存储器的特征1.

30、 多次性多次性 2. 对换性对换性 3. 虚拟性虚拟性 4.7 请求分页存储管理方式请求分页存储管理方式 请求分页中的硬件支持请求分页中的硬件支持 页表机制页表机制 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 主要是缺页中断机构主要是缺页中断机构地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?

31、开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是最小物理块数的确定最小物理块数的确定 能保证进程正常运行所需的最小物理块数。能保证进程正常运行所需的最小物理块数。页面调入过程页面调入过程当程序要访问的页面未在内存时，向当程序要访问的页面未在内存时，向CPU发出一缺页中断，中断处理程序保发出一缺页中断，中断处理程序保留留CPU环境，查找页表，得到该页在外存的物理块。环境，查找页表，得到该页在外存的物理块。如果此时内存能容纳新页，则启动磁盘如果此时内存能容纳新页，则启动磁盘I/O将所缺页调入内存，然后修改页将所缺页调入内存，然后修改页表。表。如果内存已满，选一页换出；再把所缺的页调入内存，如果内存已满，选一页换出；再把所缺的页调入内存， 并修改页表。并修改页表。4.8 页面置换算法页面置换算法