第4章 内存管理精选文档.ppt

《第4章 内存管理精选文档.ppt》由会员分享，可在线阅读，更多相关《第4章 内存管理精选文档.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 内存管理本讲稿第一页，共八十七页4.1 4.1 内存管理的功能内存管理的功能 内存空间的分配和回收内存空间的分配和回收地址转换地址转换内存空间的共享和保护内存空间的共享和保护内存空间的逻辑扩充内存空间的逻辑扩充本讲稿第二页，共八十七页4.1.1 4.1.1 内存的分配与回收内存的分配与回收内存分配按分配时机的不同，可分为三种方式：内存分配按分配时机的不同，可分为三种方式：1.1.直接分配直接分配 采采用用物物理理内内存存地地址址编编写写程程序序。使使用用这这种种方方式式，必必须须事事先先划划定定内内存存的的使使用用空空间间，因因此此，内内存存利利用用率率不不高高，用用户户使使用较困难。

2、用较困难。2.2.静态分配静态分配 在在作作业业运运行行之之前前各各目目标标模模块块连连接接后后，把把整整个个作作业业一一次次性性全全部部装装入入内内存存，并并在在作作业业的的整整个个运运行行过过程程中中，不不允允许许作作业业再再申申请请其其他他内内存存，或或在在内内存存中中移移动动位位置置。也也就就是是说说，内内存分配是在作业运行前一次性完成的。存分配是在作业运行前一次性完成的。本讲稿第三页，共八十七页4.1.1 4.1.1 内存的分配与回收内存的分配与回收3.3.动态分配动态分配 作作业业要要求求的的基基本本内内存存空空间间是是在在目目标标模模块块装装入入内内存存时时分分配配的的，但但在在

3、作作业业运运行行过过程程中中，允允许许作作业业申申请请附附加加的的内内存存空空间间，或或是是在在内内存存中中移移动动，即即分分配配工工作作可可以以在在作业运行前及运行过程中逐步完成。作业运行前及运行过程中逐步完成。本讲稿第四页，共八十七页4.1.2 4.1.2 地址转换地址转换 把用户程序装入内存时对有关指令的地把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址址部分的修改定义为从程序地址到内存地址的的地址转换地址转换，或称为，或称为地址重定位地址重定位。1.1.物理地址与逻辑地址物理地址与逻辑地址 物物理理地地址址也也称称内内存存地地址址，它它是是用用于于唯唯一一标标识

4、识一一个个内内存存单单元元的的编编号号。所所有有的的物物理理地地址址构构成了成了物理空间物理空间。本讲稿第五页，共八十七页4.1.2 4.1.2 地址转换地址转换 逻逻辑辑地地址址也也称称程程序序地地址址，它它是是指指在在源源程程序序经经过过汇汇编编或或编编译译后后形形成成的的目目标标代代码码中中，用用于于反反映映目目标标代代码码中中指指令或数据的相对位置关系的地址。令或数据的相对位置关系的地址。逻逻辑辑地地址址都都是是以以“0 0”为为基基址址顺顺序序进进行行编编址址的的，这这样样生生成成的的目目标标程程序序占占据据一一定定的的地地址址空空间间，称称为为程程序序的的逻辑地址空间逻辑地址空间，

5、简称，简称逻辑空间逻辑空间。用符号地址（符号名）表示的程序空间称为用符号地址（符号名）表示的程序空间称为名空间名空间。地址重定位的原因是什么地址重定位的原因是什么?本讲稿第六页，共八十七页 因因为为程程序序在在装装入入内内存存后后，其其逻逻辑辑地地址址和和物理地址不一致。物理地址不一致。本讲稿第七页，共八十七页地址映射地址映射Load A 200Load A 200 3456 3456 。12001200物理地址空间物理地址空间Load A data1Load A data1data1 3456data1 3456源程序源程序Load A 200Load A 200 3456 34560 01

6、00100200200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000BA=1000（名空间）（名空间）本讲稿第八页，共八十七页静态重定位静态重定位 是在程序执行之前由操作系统的连接装入程序完成地是在程序执行之前由操作系统的连接装入程序完成地址转换。址转换。优点：不需要硬件的支持。优点：不需要硬件的支持。缺点：程序必须占用连续的内存空间；缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。一旦程序装入后不能移动。2.2.地址重定位的方式地址重定位的方式本讲稿第九页，共八十七页动态重定位动态重定位 在程序执行期间进行的地址转换，是由专门的硬在程序执行期间进行的地址转换，是由专门的硬件

7、机构来完成的。件机构来完成的。优点：程序占用的内存空间是动态可变的，当程序从某个存储优点：程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器区移到另一个区域时，只需要修改相应的寄存器BRBR的内容即的内容即可。可。缺点：需要硬件的支持；缺点：需要硬件的支持；实现存储管理的软件算法较为复杂。实现存储管理的软件算法较为复杂。本讲稿第十页，共八十七页03456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR动态重定位示意图动态重定位示意图本讲稿第十一页，共八十七页4.1.3 4.1.3

8、内存的共享和保护内存的共享和保护内存空间的共享：内存空间的共享：内存空间的共享：内存空间的共享：在多道程序设计系统中，同时进入主存执行的作业可在多道程序设计系统中，同时进入主存执行的作业可在多道程序设计系统中，同时进入主存执行的作业可在多道程序设计系统中，同时进入主存执行的作业可能需要调用相同的程序或数据，这就是能需要调用相同的程序或数据，这就是能需要调用相同的程序或数据，这就是能需要调用相同的程序或数据，这就是内存的共享内存的共享内存的共享内存的共享。例如，调用编译程序进行编译，把这个编译程序例如，调用编译程序进行编译，把这个编译程序例如，调用编译程序进行编译，把这个编译程序例如，调用编译程

9、序进行编译，把这个编译程序存放在某个区域中，各作业要调用时就访问这个区域，存放在某个区域中，各作业要调用时就访问这个区域，存放在某个区域中，各作业要调用时就访问这个区域，存放在某个区域中，各作业要调用时就访问这个区域，因此这个区域就是共享的。因此这个区域就是共享的。因此这个区域就是共享的。因此这个区域就是共享的。同样也可以实现公共数据的共享。同样也可以实现公共数据的共享。同样也可以实现公共数据的共享。同样也可以实现公共数据的共享。本讲稿第十二页，共八十七页4.1.3 4.1.3 内存的共享和保护内存的共享和保护 在实现内存分配与共享时，必须解决内存中信息在实现内存分配与共享时，必须解决内存中信

10、息的保护问题。存储保护的工作一般由硬件和软件配合的保护问题。存储保护的工作一般由硬件和软件配合实现。实现。1.1.上、下界存储保护上、下界存储保护：系统可为每个作业设置一对上、下：系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。边界地址，用它们来限制用户程序的活动范围。2.2.基址限长存储保护基址限长存储保护：上、下界保护的一个变种是采用：上、下界保护的一个变种是采用基址基址限长存储保护。限长存储保护。本讲稿第十三页，共八十七页4.1.3 4.1.3 内存的保护内存的

11、保护本讲稿第十四页，共八十七页4.1.4 4.1.4 内存空间的逻辑扩充内存空间的逻辑扩充 对内存进行逻辑上的扩充，现在普遍采用覆盖、对内存进行逻辑上的扩充，现在普遍采用覆盖、交换和虚拟存储器技术。交换和虚拟存储器技术。虚拟存储器虚拟存储器是具有请求调入功能和置换功能，能仅把是具有请求调入功能和置换功能，能仅把作业的一部分装入内存便可运行作业的存储器系统，它是一作业的一部分装入内存便可运行作业的存储器系统，它是一种能从逻辑上对内存容量进行扩充的虚构的存储器系统。种能从逻辑上对内存容量进行扩充的虚构的存储器系统。虚拟存储器的理论基础是程序的局部性原理。包括虚拟存储器的理论基础是程序的局部性原理。

12、包括时间时间局部性局部性和和空间局部性空间局部性。什么是时间局部性什么是时间局部性?什么是空间局部性什么是空间局部性?本讲稿第十五页，共八十七页4.1.4 4.1.4 内存空间的逻辑扩充内存空间的逻辑扩充 虚拟存储器的基本思想虚拟存储器的基本思想是把有限的内存空间与大是把有限的内存空间与大容量的外存统一管理，构成一个远大于实际内存的、容量的外存统一管理，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，虚拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。当作一级存储

13、器来看待。一个作业运行时，其全部信息装入虚存，实际上一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，其他可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系统自动则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。将其从外存调入内存。本讲稿第十六页，共八十七页4.2.1 4.2.1 单分区管理单分区管理4.2.2 4.2.2 固定分区固定分区4.2.3 4.2.3 可变分区可变分区4.2.4 4.2.4 覆盖与交换覆盖与交换4.2 4.2 分区管理分区管理 本讲稿第十七页，共八十七页4.2.1 4.2.1 单分

14、区管理单分区管理 这这是是一一种种最最简简单单的的连连续续存存储储管管理理方方式式。但但只只能能用用于于单单用用户户、单任务的操作系统中。单任务的操作系统中。系系统统区区：仅仅提提供供给给操操作作系系统统使使用用，通通常常设设置置在在内内存存的的低低址部分；址部分；用用户户区区：指指除除系系统统区区以以外外的的全全部部内内存存空空间间，提提供供给给用户使用。用户使用。空闲区：指剩余部分存储区。空闲区：指剩余部分存储区。本讲稿第十八页，共八十七页4.2.2 4.2.2 固定分区固定分区 把把可可用用空空间间划划分分成成若若干干个个固固定定大大小小的的存存储储区区，除除操操作作系系统统占占用用一一

15、个个区区域域外外，其其余余区区域域为为系系统统中中多多个个用用户户共共享享，因因为为在在系系统统运运行行期期间间，分分区区大大小小、数数目目都都不不变变，所所以以固固定定分分区区也也称称为为静态分区静态分区。本讲稿第十九页，共八十七页分区说明表分区说明表本讲稿第二十页，共八十七页4.2.3 4.2.3 可变分区可变分区1 1、基基本本思思想想：分分区区大大小小、数数目目可可变变，所所以以可可变变分分区也称为区也称为动态分区动态分区。它是根据用户作业的大小，在作业要求装入主存时，它是根据用户作业的大小，在作业要求装入主存时，动态地划分分区，使分区的大小正好适应作业的要求。动态地划分分区，使分区的

16、大小正好适应作业的要求。可变分区存储管理方式必须解决三个问题：可变分区存储管理方式必须解决三个问题：一是分区分配中所用的数据结构；一是分区分配中所用的数据结构；二是分区的分配算法；二是分区的分配算法；三是分区的分配和回收。三是分区的分配和回收。本讲稿第二十一页，共八十七页 可变分区内存使用情况示意图可变分区内存使用情况示意图本讲稿第二十二页，共八十七页2 2可变分区管理中的数据结构可变分区管理中的数据结构 本讲稿第二十三页，共八十七页最先适应算法最先适应算法 按空闲区地址递增的次序分配按空闲区地址递增的次序分配最优适应算法最优适应算法 按空闲区由小到大的次序分配按空闲区由小到大的次序分配最坏适

17、应算法最坏适应算法 按空闲区由大到小的次序分配按空闲区由大到小的次序分配3 3内存的分配算法内存的分配算法 本讲稿第二十四页，共八十七页（1 1）最先适应分配算法（）最先适应分配算法（FFFF）它要求空闲分区表中的记录它要求空闲分区表中的记录按地址递增的顺序排列按地址递增的顺序排列。在每次分配主存时，总是从第在每次分配主存时，总是从第1 1条记录开始顺序查找空闲条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区。一部分分配给作业，另一部分仍作为空割这个空闲区。一部分分配给作业，另一部分仍作为空闲区。闲区。特点是算法

18、简单，容易产生过多的主存碎片。特点是算法简单，容易产生过多的主存碎片。主存碎片主存碎片是指小的不能使用的主存空间；这种算是指小的不能使用的主存空间；这种算法把大的空闲区分成了小的空闲区，当有大作业要求法把大的空闲区分成了小的空闲区，当有大作业要求分配时，不能满足要求，降低了系统的效率。分配时，不能满足要求，降低了系统的效率。本讲稿第二十五页，共八十七页（2 2）最优适应分配算法（）最优适应分配算法（BFBF）它是从所有的空闲分区中挑选一个能满足作业要求它是从所有的空闲分区中挑选一个能满足作业要求它是从所有的空闲分区中挑选一个能满足作业要求它是从所有的空闲分区中挑选一个能满足作业要求的最小空闲区

19、进行分配。这样可以保证不去分割一个更的最小空闲区进行分配。这样可以保证不去分割一个更的最小空闲区进行分配。这样可以保证不去分割一个更的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。为实大的空闲区，使装入大作业时比较容易得到满足。为实大的空闲区，使装入大作业时比较容易得到满足。为实大的空闲区，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区现这种算法，把空闲区现这种算法，把空闲区现这种算法，把空闲区按长度递增次序按长度递增次序按长度递增次序按长度递增次序登记在空闲分区表登记在空闲分区表登记在空闲分区表登记在空闲分区表中，分配时，顺序查找。中，分

20、配时，顺序查找。中，分配时，顺序查找。中，分配时，顺序查找。它的优点是解决了大作业的分配问题，不足是它的优点是解决了大作业的分配问题，不足是它的优点是解决了大作业的分配问题，不足是它的优点是解决了大作业的分配问题，不足是容易产生主存碎片，降低了主存空间的利用率。另容易产生主存碎片，降低了主存空间的利用率。另容易产生主存碎片，降低了主存空间的利用率。另容易产生主存碎片，降低了主存空间的利用率。另外收回主存时，要按长度递增顺序插入到空闲分区外收回主存时，要按长度递增顺序插入到空闲分区外收回主存时，要按长度递增顺序插入到空闲分区外收回主存时，要按长度递增顺序插入到空闲分区表中，增加了系统开销。表中，

21、增加了系统开销。表中，增加了系统开销。表中，增加了系统开销。本讲稿第二十六页，共八十七页（3 3）最坏适应分配算法（）最坏适应分配算法（WFWF）它每次分配主存时总是挑选一个最大的空闲区，分它每次分配主存时总是挑选一个最大的空闲区，分它每次分配主存时总是挑选一个最大的空闲区，分它每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小而成为割一部分给作业使用，使剩下的部分不至于太小而成为割一部分给作业使用，使剩下的部分不至于太小而成为割一部分给作业使用，使剩下的部分不至于太小而成为主存碎片。为实现这种算法，把空闲区主存碎片。为实现这种算法，把空闲区主存碎片。为实现这

22、种算法，把空闲区主存碎片。为实现这种算法，把空闲区按长度递减的次按长度递减的次按长度递减的次按长度递减的次序序序序登记在空闲分区表中，分配时，顺序查找。登记在空闲分区表中，分配时，顺序查找。登记在空闲分区表中，分配时，顺序查找。登记在空闲分区表中，分配时，顺序查找。它的优点是不会产生过多的碎片。不影响大作业的分它的优点是不会产生过多的碎片。不影响大作业的分它的优点是不会产生过多的碎片。不影响大作业的分它的优点是不会产生过多的碎片。不影响大作业的分配。另外收回主存时，要按长度递减的顺序插入到空闲分配。另外收回主存时，要按长度递减的顺序插入到空闲分配。另外收回主存时，要按长度递减的顺序插入到空闲分

23、配。另外收回主存时，要按长度递减的顺序插入到空闲分区表中，增加了系统开销。区表中，增加了系统开销。区表中，增加了系统开销。区表中，增加了系统开销。本讲稿第二十七页，共八十七页 有有作作业业序序列列：作作业业A A要要求求18K18K；作作业业B B要求要求25K25K，作业，作业C C要求要求30K30K。如下图。如下图。系系统统中中空空闲闲区区按按三三种种算算法法组组成成的的空空闲闲区区队队列列如如下下，经经分分析析可可知知：最最佳佳适适应应法法对对这这个个作作业业序序列列是是合合适适的的，而而其其它它两两种种对对该该作作业业序列是不合适的。序列是不合适的。举例举例本讲稿第二十八页，共八十七

24、页本讲稿第二十九页，共八十七页 有作业序列：作业有作业序列：作业A A要求要求21K21K；作业；作业B B要求要求30K30K，作业，作业C C要求要求25K25K，分析使用哪种分配算法最佳？，分析使用哪种分配算法最佳？课堂练习：课堂练习：本讲稿第三十页，共八十七页4 4内存的回收内存的回收 当当某某一一个个用用户户作作业业完完成成释释放放所所占占分分区区时时，系统应进行回收。系统应进行回收。在在可可变变式式分分区区中中，应应该该检检查查回回收收区区与与内内存存中中前后空闲区是否相邻：前后空闲区是否相邻：若若相相邻邻，则则应应进进行行合合并并，形形成成一一个个较较大大的的空空闲闲区区，并并对

25、对相相应应的的链链表表指指针针进进行行修修改改；若若不不相相邻邻，应应将将空空闲闲区区插插入入到到空空闲闲区区链链表表的的适当位置。适当位置。本讲稿第三十一页，共八十七页n回收的分区前后没有相邻的空闲分区。回收的分区前后没有相邻的空闲分区。n回收分区的前面有相邻的空闲分区。回收分区的前面有相邻的空闲分区。n回收分区的后面有相邻的空闲分区。回收分区的后面有相邻的空闲分区。n回收分区的前后都有相邻的空闲分区。回收分区的前后都有相邻的空闲分区。本讲稿第三十二页，共八十七页5 5、分区保护、分区保护 存储保护是为了防止一个作业破坏操作系统或其他作业。存储保护是为了防止一个作业破坏操作系统或其他作业。1

26、.1.上、下界寄存器保护法：上、下界寄存器保护法：上界寄存器上界寄存器物理地址物理地址下界下界寄存器，超出这个范围便产生保护性中断。寄存器，超出这个范围便产生保护性中断。2.2.基址、限长寄存器保护法：基址、限长寄存器保护法：基址寄存器基址寄存器物理地址物理地址基基址寄存器址寄存器+限长寄存器，如果超过了限长，则发出越界中断限长寄存器，如果超过了限长，则发出越界中断信号，并停止作业的运行。信号，并停止作业的运行。3.3.存储保护键方法：存储保护键方法：系统为每个分区设一个保护键，在程序状态字中也设同系统为每个分区设一个保护键，在程序状态字中也设同样的保护键字段，访问内存时检查键的配对情况，如果

27、不匹样的保护键字段，访问内存时检查键的配对情况，如果不匹配则产生保护性中断。配则产生保护性中断。本讲稿第三十三页，共八十七页4.2.4 碎片问题及其解决办法碎片问题及其解决办法 在分区分配方式中经过不断地分配和释放后，内存中空在分区分配方式中经过不断地分配和释放后，内存中空闲分区会变得越来越多和越来越小，产生了许多碎片。闲分区会变得越来越多和越来越小，产生了许多碎片。所谓所谓碎片碎片是指内存中出现的一些零散的小空闲区域。是指内存中出现的一些零散的小空闲区域。由于碎片都很小，故无法再利用。如果内存中碎片很由于碎片都很小，故无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。多，将会造成严

28、重的存储资源浪费。本讲稿第三十四页，共八十七页4.2.4 碎片问题及其解决办法碎片问题及其解决办法移动移动(紧凑紧凑/紧缩紧缩/拼接拼接)技术：技术：解决碎片的方法是移动所有的占用区域，使所有的解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为空闲区合并成一片连续区域，这一技术称为移动技术移动技术（拼接）（拼接）。移动技术可解决碎片问题，从而提高内存的利用率。移动技术可解决碎片问题，从而提高内存的利用率。移动技术可以集中分散的空闲区，便于作业动态扩充移动技术可以集中分散的空闲区，便于作业动态扩充内存。内存。本讲稿第三十五页，共八十七页4.2.5 覆盖与交换覆盖与

29、交换n覆盖覆盖：一个作业的若干程序段，或几个作业的某些：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。部分共享某一个存储空间。n程序段先保存在磁盘上，当有关程序段的前一部分执行程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段。结束，把后续程序段调入内存，覆盖前面的程序段。n一般要求作业各模块之间有明确的调用结构，程序员一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆要向系统指明覆盖结构，然后由操作系统完成自动覆盖。盖。本讲稿第三十六页，共八十七页A8KE4KF10KC10KB8KD12K作业

30、作业X的调用结构的调用结构作业作业X X的常驻区的常驻区 A A（8K8K）覆盖区覆盖区0（10K）覆盖区覆盖区1（12K）BC C D E F本讲稿第三十七页，共八十七页为什么引入交换技术？为什么引入交换技术？当内存空间紧张时，系统将内存中某些进程当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。外存之间的动态调度。多用于分时系统中。多用于分时系统中。2.2.交换交换本讲稿第三十八页，共八十七页 与覆盖技术相比，交换技

31、术不要求用户给与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。出程序段之间的逻辑覆盖结构。交换与覆盖的不同之处：交换与覆盖的不同之处：交换发生在进程或作业之间，而覆盖发生在同一交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。进程或作业内。覆盖只能覆盖那些与覆盖段无关的程序段。覆盖只能覆盖那些与覆盖段无关的程序段。2.2.交换交换本讲稿第三十九页，共八十七页4.3 4.3 页式管理页式管理 4.3.1 4.3.1 页式管理概述页式管理概述1.1.基本原理：基本原理：分分页页存存储储管管理理是是将将一一个个进进程程的的地地址址空空间间划划分分成成若若干干个大小相等的区域，称

32、为个大小相等的区域，称为页页。相相应应地地，将将内内存存空空间间划划分分成成与与页页相相同同大大小小的的若若干个物理块，称为干个物理块，称为块或页帧块或页帧。在在为为进进程程分分配配内内存存时时，将将进进程程中中若若干干页页分分别别装装入多个不相邻接的块中。入多个不相邻接的块中。本讲稿第四十页，共八十七页4.3.1 4.3.1 页式管理概述页式管理概述2.2.地址结构：地址结构：分分页页系系统统的的地地址址结结构构由由两两部部分分组组成成：前前一一部部分分为为页号页号P P；后一部分为位移量；后一部分为位移量W W，即，即页内位移页内位移。在在下下图图中中地地址址为为3232位位，其其中中0

33、01111位位为为页页内内位位移移（每每页页的的大大小小为为4K4K），12123131位位为为页页号号，所所以以允允许许地地址址空空间间的的大大小小最多为最多为1M1M个页。个页。本讲稿第四十一页，共八十七页地址结构示例地址结构示例 31 12 11 0 页号页号 P 位移量位移量W本讲稿第四十二页，共八十七页4.3.2 4.3.2 静态分页静态分页 基本思想是必须装入作业的全部页面后才能执基本思想是必须装入作业的全部页面后才能执行该作业。行该作业。1.1.页表：页表：系统为每个进程建立了一张系统为每个进程建立了一张页面映射表页面映射表，简，简称称页表页表。每个页在页表中占一个表项，记录该页

34、在内存中对应每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。每页所对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。页表的作用是实现从页号到物理块号的地址映射。本讲稿第四十三页，共八十七页页号页号块号块号0 02 21 13 32 28 8页表页表本讲稿第四十四页，共八十七页地址空间地址空间物理空间物理空间本讲稿第四十五页，共八十七页4.3.2 4.3.2 静态分页静态分页 2.2.静态页式管理的分配与回收：静态页式管理的分配与回收：内存空间以块为单位，内存空间以块

35、为单位，要用数据结构记录内存中块的情况。要用数据结构记录内存中块的情况。1 1、位示图：、位示图：每一位对应一个块，每一位对应一个块，0 0 空闲，空闲，1 1 已分配。已分配。2 2、空闲块链：、空闲块链：所有空闲块组成一个空闲块链，链首分配，所有空闲块组成一个空闲块链，链首分配，链尾回收。链尾回收。3 3、内存分块表：、内存分块表：表项包括块号，进程号，页号，状态等。表项包括块号，进程号，页号，状态等。状态为状态为0 0，空闲，空闲，1 1，已分配。，已分配。本讲稿第四十六页，共八十七页4.3.2 4.3.2 静态分页静态分页3.3.地址转换：地址转换：当进程要访问某个逻辑地址当进程要访问

36、某个逻辑地址M M中的数据时，需做如下中的数据时，需做如下地址变换：地址变换：1 1、将地址空间的逻辑地址、将地址空间的逻辑地址M M转换为转换为页式逻辑地址页式逻辑地址；2 2、以页号、以页号P P为索引去检索页表，找到相对应表项页表始为索引去检索页表，找到相对应表项页表始址页号址页号P P；从中读出对应的物理块号从中读出对应的物理块号B B；3 3、计算物理地址、计算物理地址BB页长页内位移页长页内位移W W。本讲稿第四十七页，共八十七页 求出有效地址求出有效地址20442044所对所对应的物理地址，要求写出地应的物理地址，要求写出地址转换过程。址转换过程。页式逻辑地址：页号：页式逻辑地址

37、：页号：2044/1024=1 2044/1024=1，页内位，页内位移量：移量：2044 MOD 1024=10202044 MOD 1024=1020物理地址：物理地址：5*1024+1020=61405*1024+1020=6140在采用页面存储管理的系统中，某作业的逻在采用页面存储管理的系统中，某作业的逻辑地址空间为辑地址空间为4 4页（每页页（每页1k1k），且已知该作业），且已知该作业的页表如下：的页表如下：页号页号块号块号0 07 71 15 52 23 33 39 9本讲稿第四十八页，共八十七页分页中的地址转换机构分页中的地址转换机构页表始址页表始址页表长度页表长度页表寄存器页

38、表寄存器页号页号P P页内地址页内地址W W页式逻辑地址页式逻辑地址越界中断越界中断=Lpp.快表快表 b+页号页号p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址4.4.引入快表的地址转换引入快表的地址转换本讲稿第五十二页，共八十七页5 5页的共享和保护页的共享和保护（1 1）页的共享。）页的共享。页的共享可以节省主存空间。页式存储管理页的共享可以节省主存空间。页式存储管理能方便地实现多个作业共享程序和数据。能方便地实现多个作业共享程序和数据。共享的方法是共享的方法是使各自页表中的有关表目指向共享信使各自页表中的有关表目指向共

39、享信息的主存块。息的主存块。（2 2）页的保护。）页的保护。在页式存储管理方式下的保护有三种情况：在页式存储管理方式下的保护有三种情况：共享页的保护、不同作业所占空间的保护、逻辑共享页的保护、不同作业所占空间的保护、逻辑地址转换成物理地址的保护。地址转换成物理地址的保护。本讲稿第五十三页，共八十七页4.3.3 4.3.3 动态分页动态分页(请求分页请求分页)1.1.基本思想：基本思想：采用采用虚拟存储技术虚拟存储技术，只需装入作业的部分页面，只需装入作业的部分页面就能启动作业的运行。就能启动作业的运行。以后再通过调页功能和页面置换功能，陆续以后再通过调页功能和页面置换功能，陆续把将要运行的页面

40、调入内存，同时把暂不运行的把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。页面置换到外存上，置换时以页面为单位。本讲稿第五十四页，共八十七页2.2.扩充的页表结构扩充的页表结构 0 0 1 1 0 0 0 0修改位修改位 1 1 220 220 3 3 1 1 0 0 200 200 15 15 0 0 0 0 50 50 14 14 1 1 1 1 112 112 10 10 1 1访问位访问位外存地址外存地址块号块号驻留位驻留位 3 3 2 2 1 1 0 0页号页号本讲稿第五十五页，共八十七页3.3.缺页中断缺页中断 在在请请求求分分页页系系统统中中，每每

41、当当所所要要访访问问的的页页面面不不在在内内存时，便要产生一存时，便要产生一缺页中断缺页中断，请求，请求OSOS将所缺页调入内存。将所缺页调入内存。与一般中断的主要区别在于：与一般中断的主要区别在于：缺缺页页中中断断在在指指令令执执行行期期间间产产生生和和处处理理中中断断信信号号，而而一一般般中断在一条指令执行完后检查和处理中断信号。中断在一条指令执行完后检查和处理中断信号。缺缺页页中中断断返返回回到到该该指指令令的的开开始始重重新新执执行行该该指指令令，而而一一般中断返回到该指令的下一条指令执行。般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间

42、，可能产生多次缺页中断。本讲稿第五十六页，共八十七页4.4.地址变换机构地址变换机构 请请求求分分页页系系统统中中的的地地址址变变换换机机构构，是是在在分分页页系系统统的的地地址址变变换换机机构构的的基基础础上上，再再为为实实现现虚虚拟拟存存储储器器而而增增加加了了某某些些功功能能所所形形成成的的，如如产产生生和和处处理理缺缺页页中中断断，以以及及从从内内存存中中换换出出一页的功能等等。一页的功能等等。本讲稿第五十七页，共八十七页5.5.页面置换算法页面置换算法 最优置换算法（最优置换算法（OPTOPT算法）算法）从从内内存存中中移移出出以以后后不不再再使使用用的的页页面面；如如无无这这样样的

43、的页页面面，则则选选择择以以后后最最长长时时间间内内不不需需要要访访问问的的页页。这这就就是是最最优优算算法法的的思思想想。这这种种算算法法本本身身不不是是一一种种实实际际的的方方法，因为页面访问的顺序是很难预知的。法，因为页面访问的顺序是很难预知的。先进先出算法（先进先出算法（FIFOFIFO算法）算法）总是先淘汰那些驻留在内存时间最长的页面，即先进总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最理由是：最先进入内存的页面不再被访问的可能性最大。大。本讲稿第五十八页，共八十七页 最近最少使用算法（最近

44、最少使用算法（LRULRU算法）算法）当当需需要要置置换换一一页页时时，选选择择在在最最近近一一段段时时间间最最少少使使用的页面予以淘汰。用的页面予以淘汰。Clock Clock置换算法置换算法 需要硬件支持，实现代价较大。需要硬件支持，实现代价较大。如何评价算法如何评价算法?缺页中断率缺页中断率=不成功的访问次数不成功的访问次数/访问总次数访问总次数 =缺页中断次数中断次数/访问总次数访问总次数本讲稿第五十九页，共八十七页OPTOPT算法性能分析（算法性能分析（M=3M=3）时刻时刻 012345678910 11 12页面页面走向走向531525423525块块1块块2块块3缺页缺页中断中

45、断本讲稿第六十页，共八十七页OPTOPT算法性能分析（算法性能分析（M=3M=3）时刻时刻 012345678910 11 12页面页面走向走向531525423525块块1555555444555块块233333333333块块31122222222缺页缺页中断中断缺页率缺页率6/12=0.5=50%本讲稿第六十一页，共八十七页FIFOFIFO算法性能分析（算法性能分析（m=3m=3）时刻时刻012345678910 11 12页面页面走向走向531525423525块块1块块2块块3缺页缺页中断中断本讲稿第六十二页，共八十七页FIFOFIFO算法性能分析（算法性能分析（m=3m=3）缺页率

46、缺页率9/12=75%时刻时刻012345678910 11 12页面页面走向走向531525423525块块1555522223333块块233335555522块块31111444445缺页缺页中断中断本讲稿第六十三页，共八十七页LRULRU算法性能分析（算法性能分析（M=3M=3）时刻时刻 012345678910 11 12页面页面走向走向531525423525块块1块块2块块3缺页缺页中断中断本讲稿第六十四页，共八十七页LRULRU算法性能分析（算法性能分析（M=3M=3）缺页率缺页率7/12=58.3%时刻时刻 012345678910 11 12页面页面走向走向53152542

47、3525块块1555555553333块块233322222222块块31111444555缺页缺页中断中断本讲稿第六十五页，共八十七页4.4 4.4 段式管理段式管理 引入段式存储管理方式的原因：引入段式存储管理方式的原因：1 1、一个作业是由若干自然段组成，用户希望能把自己的、一个作业是由若干自然段组成，用户希望能把自己的作业按照逻辑关系划分为若干段，可以通过每段的名字作业按照逻辑关系划分为若干段，可以通过每段的名字和长度来访问。和长度来访问。2 2、分段共享。程序和数据的共享是以信息的逻辑单位为基础、分段共享。程序和数据的共享是以信息的逻辑单位为基础的，若段的划分也与信息的逻辑单位相对应

48、，则易实现共享。的，若段的划分也与信息的逻辑单位相对应，则易实现共享。3 3、分段保护。在多道程序环境下，对主存信息的保护，同、分段保护。在多道程序环境下，对主存信息的保护，同样也是以信息的逻辑单位为基础的。样也是以信息的逻辑单位为基础的。4 4、动态链接也要求以段作为管理的单位。、动态链接也要求以段作为管理的单位。5 5、动态增长。、动态增长。本讲稿第六十六页，共八十七页4.4.1 4.4.1 段式管理概述段式管理概述 1 1、用户程序划分、用户程序划分 按程序自身的逻辑关系划分为若干个程序段，每个按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。程序段都有一个段

49、名，且有一个段号。段号从段号从0 0开始，每一段段内也从开始，每一段段内也从0 0开始编址，段内地开始编址，段内地址是连续的。址是连续的。本讲稿第六十七页，共八十七页3 3、内存分配、内存分配 以段为单位分配内存，每一个段在内存中以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。多少），但各段之间可以不连续存放。段号 段内地址2 2、逻辑地址结构：二维、逻辑地址结构：二维本讲稿第六十八页，共八十七页4.4.段表段表 在段式存储管理方式中，系统为每个段分配一个连续的在段式存储管理方式中，系统为每个

50、段分配一个连续的分区，而进程中的各个段可以离散放入内存中不同的分区中。分区，而进程中的各个段可以离散放入内存中不同的分区中。像页式存储管理方式那样，在系统中为每个进程建像页式存储管理方式那样，在系统中为每个进程建立一个段映射表，称为立一个段映射表，称为“段表段表”。段表可以存放在一组寄存器中，可以提高转换速度；段表可以存放在一组寄存器中，可以提高转换速度；也可以将段表放在内存中。段表的作用是实现了从逻辑段也可以将段表放在内存中。段表的作用是实现了从逻辑段到物理内存区的映射。到物理内存区的映射。本讲稿第六十九页，共八十七页4.4.段表段表本讲稿第七十页，共八十七页4.4.2 4.4.2 地址转换