计算机操作系统第四章.pdf

《计算机操作系统第四章.pdf》由会员分享，可在线阅读，更多相关《计算机操作系统第四章.pdf（212页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章存储器管理4.1 4.1 存储器的层次结构存储器的层次结构4.24.2程序的装入和链接程序的装入和链接4.34.3连续分配方式连续分配方式4.44.4基本分页存储管理方式基本分页存储管理方式4.54.5基本分段存储管理方式基本分段存储管理方式4.64.6虚拟存储器的基本概念虚拟存储器的基本概念4.74.7请求分页存储管理方式请求分页存储管理方式4.84.8页面置换算法页面置换算法4.94.9请求分段存储管理方式请求分段存储管理方式第四章存储器管理第四章存储器管理存储器管理的功能存储器管理的功能存储器管理的功能存储器管理的功能存储器管理的功能存储器管理的功能4.1 4.1 存储器的层次结构

2、存储器的层次结构多级存储器结构多级存储器结构对于通用计算机而言对于通用计算机而言，存储层次至少应具有三级：最高层为存储层次至少应具有三级：最高层为CPU寄存器寄存器，中间为主存中间为主存，最底层是辅存最底层是辅存。在较高档的计算机中在较高档的计算机中，还可以还可以根据具体的功能分工细划为寄存器根据具体的功能分工细划为寄存器、高速缓存高速缓存、主存储器主存储器、磁盘缓存磁盘缓存、固定磁盘固定磁盘、可移动存储介质等可移动存储介质等6层层。如图如图4-1所示所示，在存储层次中越往在存储层次中越往上上，存储介质的访问速度越快存储介质的访问速度越快，价格也越高价格也越高，相对存储容量也越小相对存储容量也

3、越小。其中其中，寄存器寄存器、高速缓存高速缓存、主存储器和磁盘缓存均属于操作系统存储主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴管理的管辖范畴，掉电后它们存储的信息不再存在掉电后它们存储的信息不再存在。固定磁盘和可移固定磁盘和可移动存储介质属于设备管理的管辖范畴动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存它们存储的信息将被长期保存。图图4-1 计算机系统存储层次示意计算机系统存储层次示意寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存4.1 4.1 存储器的层次结构存储器的层次结构1 1主存储器主存储器主存储器主存储器(简称内存或主存简称内存或主存)是计算

4、机系统中一个主要部是计算机系统中一个主要部件件，用于保存进程运行时的程序和数据用于保存进程运行时的程序和数据，也称可执行存储器也称可执行存储器，其容量对于当前的微机系统和大中型机其容量对于当前的微机系统和大中型机，可能一般为数十可能一般为数十MB到数到数GB，而且容量还在不断增加而且容量还在不断增加，而嵌入式计算机系统而嵌入式计算机系统一般仅有几十一般仅有几十KB到几到几MB。CPU的控制部件只能从主存储器的控制部件只能从主存储器中取得指令和数据中取得指令和数据，数据能够从主存储器读取并将它们装入数据能够从主存储器读取并将它们装入到寄存器中到寄存器中，或者从寄存器存入到主存储器或者从寄存器存入

5、到主存储器。CPU与外围设与外围设备交换的信息一般也依托于主存储器地址空间备交换的信息一般也依托于主存储器地址空间。由于主存储由于主存储器的访问速度远低于器的访问速度远低于CPU执行指令的速度执行指令的速度，为缓和这一矛盾为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存在计算机系统中引入了寄存器和高速缓存。4.1 4.1 存储器的层次结构存储器的层次结构2 2寄存器寄存器寄存器访问速度最快，完全能与寄存器访问速度最快，完全能与CPU协调工作，但价格协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字以字(word)为单

6、位。寄存器的数目，对于当前的微机系统和为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器用于加速存储器的访问速度，一般仅有几个到几十个。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。度等。4.1 4.1 存储器的层次结构存储器的层次结构3 3高速缓存高速缓存高速缓存是现代计算机结构中的一个重要部件高速缓存是现代计算机结构中的一个重要部件，其容量其容量大于或远大于寄存器大于或远大

7、于寄存器，而比内存约小两到三个数量级左右而比内存约小两到三个数量级左右，从几十从几十KBKB到几到几MBMB，访问速度快于主存储器访问速度快于主存储器。根据程序执行的局部性原理根据程序执行的局部性原理(即程序在执行时将呈现出局即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部部性规律，在一较短的时间内，程序的执行仅局限于某个部分分)，将主存中一些经常访问的信息存放在高速缓存中，减少，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。访问主存储器的次数，可大幅度提高程序执行速度。4.1 4.1 存储器的层次结构存储器的层次结构

8、4 4磁盘缓存磁盘缓存由于目前磁盘的由于目前磁盘的I/OI/O速度远低于对主存的访问速度速度远低于对主存的访问速度，因因此将频繁使用的一部分磁盘数据和信息此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓暂时存放在磁盘缓存中存中，可减少访问磁盘的次数可减少访问磁盘的次数。磁盘缓存本身并不是一种实磁盘缓存本身并不是一种实际存在的存储介质际存在的存储介质，它依托于固定磁盘它依托于固定磁盘，提供对主存储器存提供对主存储器存储空间的扩充储空间的扩充，即利用主存中的存储空间即利用主存中的存储空间，来暂存从磁盘中来暂存从磁盘中读出读出(或写入或写入)的信息的信息。主存也可以看做是辅存的高速缓存主存也可以

9、看做是辅存的高速缓存，因为因为，辅存中的数据必须复制到主存方能使用；反之辅存中的数据必须复制到主存方能使用；反之，数据数据也必须先存在主存中也必须先存在主存中，才能输出到辅存才能输出到辅存。4.1 4.1 存储器的层次结构存储器的层次结构4.24.2程序的装入和链接程序的装入和链接图4-2对用户程序的处理步骤4.24.2程序的装入和链接程序的装入和链接4.34.3连续分配方式连续分配方式早期早期PCPC使用的使用的内存管理方式内存管理方式（MSMS-DOSDOS）固定分区分配固定分区分配该算法又称为分类搜索法，是将空闲分区根据其容量该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对

10、于每一类具有相同容量的所有空闲分区，大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大等，对于其它大小的分区，如小的

11、分区，如7 KB这样的空闲区，既可以放在这样的空闲区，既可以放在8 KB的链表的链表中，也可以放在一个特殊的空闲区链表中。中，也可以放在一个特殊的空闲区链表中。快速适应算法快速适应算法(quick fit)(quick fit)该算法的优点该算法的优点是查找效率高是查找效率高，仅需要根据进程的长度仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表寻找到能容纳它的最小空闲区链表，并取下第一块进行分配并取下第一块进行分配即可即可。另外该算法在进行空闲分区分配时另外该算法在进行空闲分区分配时，不会对任何分区不会对任何分区产生分割产生分割，所以能保留大的分区所以能保留大的分区，满足对大空间的需求满足

12、对大空间的需求，也也不会产生内存碎片不会产生内存碎片。该算法的缺点该算法的缺点是在分区归还主存时算法复杂，系统开销是在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存储空间浪费，这是典型的以空严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。间换时间的作法

13、。快速适应算法快速适应算法(quick fit)(quick fit)固定分区和动态分区方式都有不足之处：固定分区和动态分区方式都有不足之处：固定分区方式固定分区方式：限制了活动进程的数目限制了活动进程的数目，当进程大小与空闲分区大当进程大小与空闲分区大小不匹配时小不匹配时，内存空间利用率很低内存空间利用率很低。动态分区方式动态分区方式：算法复杂算法复杂，回收空闲分区时需要进行分区合并等回收空闲分区时需要进行分区合并等，系统开销较大系统开销较大。伙伴系统方式：伙伴系统方式：是对以上两种内存方式的一种折衷方案是对以上两种内存方式的一种折衷方案。伙伴系统规定伙伴系统规定，无论已分配分区或空闲分区无

14、论已分配分区或空闲分区，其大小均为其大小均为2 2的的k k次次幂幂，k k为整数为整数，lkm，其中：其中：21表示分配的最小分区的大小表示分配的最小分区的大小，2m表示表示分配的最大分区的大小分配的最大分区的大小，通常通常2m是整个可分配内存的大小是整个可分配内存的大小。伙伴系统伙伴系统假设系统的可利用空间容量为假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内个字，则系统开始运行时，整个内存区是一个大小为存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小可

15、能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲个空闲分区链表。分区链表。伙伴系统伙伴系统当需要为进程分配一个长度为当需要为进程分配一个长度为n的存储空间时，首先计算一个的存储空间时，首先计算一个i值，使值，使2i1n2i，然后在空闲分区大小为，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，的空闲分区链表中查找。若找到，即把该空闲分区分配给进程

16、。否则，表明长度为即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，的空闲分区已经耗尽，则在分区大小为则在分区大小为2i1的空闲分区链表中寻找。若存在的空闲分区链表中寻找。若存在2i1的一个空闲分区，的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若的空闲分区链表中。若大小为大小为2i1的空闲分区也不存在，则需要查找大小为的空闲分区也不存在，则需要查找大小为2i2的空闲分区，若的

17、空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为找到则对其进行两次分割：第一次，将其分割为大小为2i1的两个分区，的两个分区，一个用于分配，一个加入到大小为一个用于分配，一个加入到大小为2i1的空闲分区链表中；第二次，将第的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到的两个分区，一个用于分配，一个加入到大小为大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对闲分区，以此类推。由此可见，

18、在最坏的情况下，可能需要对2k的空闲分的空闲分区进行区进行k次分割才能得到所需分区。次分割才能得到所需分区。伙伴系统伙伴系统与一次分配可能要进行多次分割一样与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合一次回收也可能要进行多次合并并，如回收大小为如回收大小为2i的空闲分区时的空闲分区时，若事先已存在若事先已存在2i的空闲分区时的空闲分区时，则应则应将其与伙伴分区合并为大小为将其与伙伴分区合并为大小为2i1的空闲分区的空闲分区，若事先已存在若事先已存在2i1的空的空闲分区时闲分区时，又应继续与其伙伴分区合并为大小为又应继续与其伙伴分区合并为大小为2i2的空闲分区的空闲分区，依此类依

19、此类推推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。能则远优于前面所述的分类搜索法，比顺序搜索法略差

20、。伙伴系统伙伴系统在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应的空闲分区链查找得到一个空

21、闲分区。如果对空闲分区分类较细，则相应的空闲分区链表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。哈希算法哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈

22、希函数计算，当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。策略。哈希算法哈希算法2 2动态重定位的实现动态重定位的实现在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地执行时进行。为使地址的转

23、换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序序(数据数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。图对地址与重定位寄存器中的地址相加而形成的。图4-10示出了动态重定位示出了动态重定位的实现原理。地址变换过程是在程序执行期间，随着对每条指令或数据的的实现原理。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进

24、行了访问自动进行的，故称为动态重定位。当系统对内存进行了“紧凑紧凑”而使而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。程序在内存的新起始地址，去置换原来的起始地址即可。可重定位分区分配可重定位分区分配图 4-10动态重定位示意图LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存可重定位分区分配可重定位分区分配3 3动态重定位分

25、区分配算法动态重定位分区分配算法动态重定位分区分配算法与动态分区分配算法基本上相动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。图凑。图4-11示出了动态重定位分区分配算法。示出了动态重定位分区分配算法。可重定位分区分配可重定位分区分配图4-11动态分区分配算法流程图请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回

26、分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否可重定位分区分配可重定位分区分配1 1对换对换(Swapping)(Swapping)的引入的引入在多道程序环境下在多道程序环境下，一方面一方面，在内存中的某些进程由于某事件尚未发在内存中的某些进程由于某事件尚未发生而被阻塞运行生而被阻塞运行，但它却占用了大量的内存空间但它却占用了大量的内存空间，甚至有时可能出现在内甚至有时可能出现在内存中所有进程都被阻塞而迫使存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面停止下来等待的情况；另一方面，却又却又有着许多作业在外存上等待有着许多作业在外存

27、上等待，因无内存而不能进入内存运行的情况因无内存而不能进入内存运行的情况。显然显然这对系统资源是一种严重的浪费这对系统资源是一种严重的浪费，且使系统吞吐量下降且使系统吞吐量下降。为了解决这一问为了解决这一问题题，在系统中又增设了对换在系统中又增设了对换(也称交换也称交换)设施设施。所谓所谓“对换对换”，是指把内存是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾以便腾出足够的内存空间出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数再把已具备运行条件的进程或进程所需要的程序和数据调入内存据调入内存。对

28、换是提高内存利用率的有效措施对换是提高内存利用率的有效措施。自从在自从在60年代初期出现年代初期出现“对换对换”技术后技术后，它便引起了人们的重视它便引起了人们的重视，现在该技术已被广泛地应用于现在该技术已被广泛地应用于操作系统中操作系统中。对对换换如果对换是以整个进程为单位的，便称之为如果对换是以整个进程为单位的，便称之为“整体对换整体对换”或或“进程进程对换对换”。这种对换被广泛地应用于分时系统中，其目的是用来解决内存。这种对换被广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存的利用率。而如果对换是以紧张问题，并可进一步提高内存的利用率。而如果对换是以“页页”或或“

29、段段”为单位进行的，则分别称之为为单位进行的，则分别称之为“页面对换页面对换”或或“分段对换分段对换”，又，又统称为统称为“部分对换部分对换”。这种对换方法是实现后面要讲到的请求分页和请。这种对换方法是实现后面要讲到的请求分页和请求分段式存储管理的基础，其目的是为了支持虚拟存储系统。在此，我求分段式存储管理的基础，其目的是为了支持虚拟存储系统。在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。为了们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进

30、程的换出，以及进程的换入。的换出，以及进程的换入。对对换换2 2对换空间的管理对换空间的管理在具有对换功能的在具有对换功能的OSOS中中，通常把外存分为文件区和对换区通常把外存分为文件区和对换区。前者用前者用于存放文件于存放文件，后者用于存放从内存换出的进程后者用于存放从内存换出的进程。由于通常的文件都是较由于通常的文件都是较长久地驻留在外存上长久地驻留在外存上，故对文件区管理的主要目标故对文件区管理的主要目标，是提高文件存储空是提高文件存储空间的利用率间的利用率，为此为此，对文件区采取离散分配方式对文件区采取离散分配方式。然而然而，进程在对换区进程在对换区中驻留的时间是短暂的中驻留的时间是短

31、暂的，对换操作又较频繁对换操作又较频繁，故对对换空间管理的主要故对对换空间管理的主要目标目标，是提高进程换入和换出的速度是提高进程换入和换出的速度。为此为此，采取的是连续分配方式采取的是连续分配方式，较少考虑外存中的碎片问题较少考虑外存中的碎片问题。为了能对对换区中的空闲盘块进行管理为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数在系统中应配置相应的数据结构据结构，以记录外存的使用情况以记录外存的使用情况。其形式与内存在动态分区分配方式中其形式与内存在动态分区分配方式中所用数据结构相似所用数据结构相似，即同样可以用空闲分区表或空闲分区链即同样可以用空闲分区表或空闲分区链。在空闲分在空

32、闲分区表中的每个表目中应包含两项区表中的每个表目中应包含两项，即对换区的首址及其大小即对换区的首址及其大小，分别用盘分别用盘块号和盘块数表示块号和盘块数表示。对对换换3 3进程的换出与换入进程的换出与换入进程的换出进程的换出。每当一进程由于创建子进程而需要更多的内存空间每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时但又无足够的内存空间等情况发生时，系统应将某进程换出系统应将某进程换出。其过程是：其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启然后启动磁盘动磁盘，将该进程的程序和数据传送

33、到磁盘的对换区上将该进程的程序和数据传送到磁盘的对换区上。若传送过程未若传送过程未出现错误出现错误，便可回收该进程所占用的内存空间便可回收该进程所占用的内存空间，并对该进程的进程控制并对该进程的进程控制块做相应的修改块做相应的修改。进程的换入。进程的换入。系统应定时地查看所有进程的状态，从中找出系统应定时地查看所有进程的状态，从中找出“就绪就绪”状态但已换出的进程，将其中换出时间最久状态但已换出的进程，将其中换出时间最久(换出到磁盘上换出到磁盘上)的进程作为换的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。对对

34、换换4.44.4基本分页存储管理方式基本分页存储管理方式基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理的基本原理基本分页存储管理基本分页存储管理(或称静态页面管理或称静态页面管理)图4-14具有快表的地址变换机构页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址具有快表的地址变换机构具有快表的地址变换机构4.54.5基本分段存储管理方式基本分段存储管理方式页式管理是把内存视为一维线性空间；

35、而段式管页式管理是把内存视为一维线性空间；而段式管理是把内存视为理是把内存视为二维空间二维空间，与进程逻辑相一致与进程逻辑相一致。将程序的地址空间划分为将程序的地址空间划分为若干个段若干个段(segment)，程序加载时，分配其所需的所有段（内存分程序加载时，分配其所需的所有段（内存分区），这些段区），这些段不必连续不必连续；物理内存的管理采；物理内存的管理采用用动态分区动态分区。需要硬件支持需要硬件支持。4.4.2 4.4.2 分段系统的基本原理分段系统的基本原理 程序通过分段程序通过分段(segmentation)划分为多个模块，如代码划分为多个模块，如代码段、数据段、共享段。段、数据段、

36、共享段。可以分别可以分别编写和编译编写和编译 可以针对不同类型的段采取不同的可以针对不同类型的段采取不同的保护保护 可以按段为单位来进行可以按段为单位来进行共享共享，包括通过动态链接进，包括通过动态链接进行代码共享行代码共享 优点：优点：没有内碎片，外碎片可以通过内存紧缩来消除。没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。便于改变进程占用空间的大小。缺点：缺点：进程全部装入内存。进程全部装入内存。4.4.2 分段系统的基本原理分段系统的基本原理B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000

37、PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址01234操作系统操作系统段号段号段表段表所需表目所需表目(1)段表：每进程一个段表：每进程一个段首址段首址段长度段长度100k40k80k60k段号段号0:1:2:3:20k200k320k300k(2)空闲表：系统一个空闲表：系统一个array of(addr,size)所需寄存器所需寄存器(1)段表寄存器：段表寄存器：bl段表首址段表首址段表长度段表长度系统一系统一个个(2)快表：系统一组：快表：系统一组：段号段号段首址段首址段长度段长度.ls.b.4.4.2 分段系统的基本原理分段系统的

38、基本原理1.分段分段分段地址中的地址具有如下结构：段号段内地址31 16 15 0该地址结构允许一个作业最长有该地址结构允许一个作业最长有64K个段，每个段，每段的最大长度为段的最大长度为64KB。2.段表段表段表可以存放在寄存器中，但更多的段表可以存放在寄存器中，但更多的是存放在内存中。是存放在内存中。段表可以实现从逻辑段到物理内存区段表可以实现从逻辑段到物理内存区的映射。的映射。4.4.2 分段系统的基本原理分段系统的基本原理利用段表实现地址映射M(0)30KX(1)20KD(2)15KF(3)10K用户作业作业空间内存空间M(0)30KX(1)20KD(2)15KF(3)10K040K8

39、0K120K150K30K40K20K80K15K120K10K150K段表段长基址01234.4.2 分段系统的基本原理分段系统的基本原理分段系统的地址变换过程分段系统的地址变换过程3.地址变换机构地址变换机构段号段号S位移量位移量W210K控制寄存器控制寄存器段表始址段表始址200K段表长度段表长度4越界越界+30K40K20K80K15K120K10K150K段长段长基址基址+内存内存040K80K120K150K越界越界例例:段表如下：段表如下：回答下列问题：回答下列问题：1计算该作业访问计算该作业访问 0，432，1，10，2，500，3，400 时的绝对地址时的绝对地址2总结段式存

40、储管理的地址转换过程。总结段式存储管理的地址转换过程。段号段号段长段长主存起始地址主存起始地址01234660140100580960221933009012371959段表如下：段表如下：计算该作业访问计算该作业访问 0，216，1，120，2，210，3，456 时的绝对地址时的绝对地址段号段号段长段长主存起始地址主存起始地址01234660140100580960221933009012371959课堂练习课堂练习注意：注意：当段表存放在内存中时，每当段表存放在内存中时，每访问一个数据，都需访问两次内存，访问一个数据，都需访问两次内存，降低了计算机的速率。降低了计算机的速率。解决方法：设

41、置联想寄存器，用于解决方法：设置联想寄存器，用于保存最近常用的段表项。保存最近常用的段表项。4.分页和分段的主要区别分页和分段的主要区别相似点：相似点：采用离散分配方式，通过地址映射机构实现地址变换采用离散分配方式，通过地址映射机构实现地址变换不同点：不同点：页是信息的物理单位，分页是为了满足系统的需要；段是信页是信息的物理单位，分页是为了满足系统的需要；段是信息的逻辑单位，含有一组意义相对完整的信息，分段是为了息的逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。满足用户的需要。页的大小固定且由系统确定，由系统把逻辑地址分为页号和页的大小固定且由系统确定，由系统把逻辑地址分为页

42、号和页内地址，由机器硬件实现；段的长度不固定，取决于用户页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。程序，编译程序对源程序编译时根据信息的性质划分。分页的作业地址空间是一维的；分段的作业地址空间是二维分页的作业地址空间是一维的；分段的作业地址空间是二维的。的。4.4.3 信息共享信息共享分页系统中共享editor的示意图（页面大小为1K）两个进程共享文本编辑程序Editor，程序大小4K，另每个进程自身的数据2K进程1ed1ed2ed3ed4data1data2进程2ed1ed2ed3ed4data1data2页表202122234041

43、页表202122235051主存0Ed120Ed221Ed322ed423data1 40data2 41data1 50data2 51分段系统中共享editor的示意图进程1editordata1进程2editordata2段表段长基址4K20K2K40K段表段长基址4K20K2K50K主存020editor40data150data2分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。段的共享段的共享段长段长段首段首址址 .l b.段号段号si.P1段表：段表：段长段长段首段首址址 .l b.段号段号sj.P2段表：段表：共享段共享段.b

44、:l内存空间内存空间段名段名共享记数共享记数段长段长段首址段首址其它其它 .vi 3 35k 125k?.共享段表：共享段表：进程段表进程段表(n)共享段表共享段表(1)共享段共享段(1)段的保护段的保护(1)段表的改进：段表的改进：段长段长段首址段首址 .l b 1 0 1段号段号s.访问权限访问权限R W E .段号段号段长段长段首段首址址 .s l b 1 0 1访问权限访问权限R W E(2)快表的改进：快表的改进：.4.4.4 段页式存储管理段页式存储管理(segmentation with paging)段式优于页式段式优于页式 便于共享和保护便于共享和保护 页式优于段式页式优于段

45、式 消除“外碎片”问题消除“外碎片”问题 段页式：结合二者优点段页式：结合二者优点 每个进程包含若干段每个进程包含若干段 每个段包含若干页每个段包含若干页1.基本原理基本原理图 4-20 作业地址空间和地址结构04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段页4.4.4 段页式存储管理段页式存储管理(segmentation with paging)基本原理基本原理 内存空间划分：内存空间划分：(同页式同页式)静态等长，静态等长，2i,称为一页。称为一页。物理地址物理地址=(块号块号,块内地址块内地址)=(f,

46、w)进程空间划分：进程空间划分：一个进程一个进程若干个段若干个段一个段一个段若干个页若干个页逻辑地址逻辑地址=(段号段号,逻辑页号逻辑页号,页内地址页内地址)=(s,p,w)4.4.4 段页式存储管理段页式存储管理(segmentation with paging)利用段表和页表实现地址映射主程序段0123子程序段01数据段012段号 状态页表大小页表始址041001220023400段表页号 状态存储块#020122223324页表页号 状态存储块#040142页表页号 状态存储块#050151252页表主存02021222324404142505152段表长度段表长度段表始址段表始址段表寄

47、存器段表寄存器块内地址块内地址块号块号b物理地址物理地址+段超段超长长2.段页式系统的地址变换机段页式系统的地址变换机构：构：页内地址页内地址页号页号P段号段号Sf1块号块号页号页号页页表表0123+段表段表0123页表长度页表长度页表始址页表始址4.64.6虚拟存储器的基本概念虚拟存储器的基本概念4.64.6虚拟存储器的基本概念虚拟存储器的基本概念局部性原理局部性原理4.74.7请求分页存储管理方式请求分页存储管理方式4.74.7请求分页存储管理方式请求分页存储管理方式2 2、页表机制、页表机制图 4-25请求分页中的地址变换过程4.84.8 页面置换算法页面置换算法4.8.1 1.最佳最佳

48、(Optimal)最佳置换算法是由最佳置换算法是由Belady于于1966年提出的一种理论年提出的一种理论上的算法上的算法。其所选择的被淘汰页面其所选择的被淘汰页面，将是以后永不使用将是以后永不使用的的，或许是在最长或许是在最长(未来未来)时间内不再被访问的页面时间内不再被访问的页面。采采用最佳置换算法用最佳置换算法，通常可保证获得最低的缺页率通常可保证获得最低的缺页率。用于：页淘汰、段淘汰、快表淘汰。用于：页淘汰、段淘汰、快表淘汰。假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，并考虑有以并考虑有以7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3

49、 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 7F7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1引用引用序列序列缺页缺页标志标志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺页缺页9 9次，总访问次数次，总访问次数2020次，缺页率次，缺页率9/209/204545页面置换页面置换6 6次，置换率次，置换率6/20=30%6/20=30%最佳置换算法（最佳置换算

50、法（OPT）例）例2.2.先进先出先进先出(FIFO)(FIFO)该算法的实质是：总是选择作业中在主存驻留总是选择作业中在主存驻留时间最长（即最老）的一页淘汰时间最长（即最老）的一页淘汰。即先进入主存的页先退出主存。其理由是，最早调入主存的页，其不再被使用的可能性比最近调入主存的页要大。7F7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1引用引用序列序列缺页缺页标志标志70F701F201F201231F230F430F420F423F023F023023013F012F0120127