操作系统原理方敏存储管理.pptx

操作系统、实验操作系统、实验操作系统、实验操作系统、实验 第五章第五章 存储管理存储管理操作系统课程组操作系统课程组操作系统课程组操作系统课程组第2页内容回顾内容回顾死锁的检测死锁的检测死锁的检测死锁的检测v永久性资源的死锁检测永久性资源的死锁检测资源分配图资源分配图死锁定理死锁定理v临时资源的死锁检测临时资源的死锁检测死锁的解除死锁的解除死锁的解除死锁的解除v重新启动重新启动v撤销进程撤销进程v剥夺资源剥夺资源v进程回退进程回退第3页一、概述一、概述计算机的存储体系结构计算机的存储体系结构计算机的存储体系结构计算机的存储体系结构v计算机为什么要使用存储器？计算机为什么要使用存储器？冯冯 诺依曼原理诺依曼原理v为什么要进行存储管理？为什么要进行存储管理？存储器一直以来都是较为珍贵的系统资源，需要合理存储器一直以来都是较为珍贵的系统资源，需要合理使用。使用。程序的逻辑空间和实际的物理空间不甚相同，需要进程序的逻辑空间和实际的物理空间不甚相同，需要进行映射。行映射。第4页一、概述一、概述v存储结构层次存储结构层次访问访问速度速度频度频度成本成本容量容量 第5页一、概述一、概述存储管理的目的存储管理的目的存储管理的目的存储管理的目的v使得用户和用户程序不涉及内存物理的细节。使得用户和用户程序不涉及内存物理的细节。v自动完成用户程序的装入。自动完成用户程序的装入。v提高内存的利用率。提高内存的利用率。v解决内存速度与解决内存速度与CPU速度不匹配的问题。速度不匹配的问题。v实现内存共享。实现内存共享。方便使用者，有效利用存储资源，提高系统工作效率。方便使用者，有效利用存储资源，提高系统工作效率。第6页一、概述一、概述存储管理的任务存储管理的任务存储管理的任务存储管理的任务v在现代操作系统中，存储管理的主要任务有以下几个方在现代操作系统中，存储管理的主要任务有以下几个方面：面：地址变换地址变换(地址再定位地址再定位)存储资源的分配和回收存储资源的分配和回收存储共享和保护存储共享和保护存储器扩充存储器扩充覆盖技术覆盖技术交换技术交换技术第7页二、地址重定位二、地址重定位基本概念基本概念基本概念基本概念程序程序符号地址符号地址/名地址名地址编译编译0101010010110101010101101010目标文件目标文件逻辑地址逻辑地址/相对地址相对地址虚拟地址虚拟地址/程序地址程序地址加载加载内存内存物理地址物理地址/绝对地址绝对地址定义：当程序被装入内存时，程序的逻辑地址定义：当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址，这一过程称为地址被转换成内存的物理地址，这一过程称为地址重定位重定位(由内存管理单元由内存管理单元(MMU)完成完成)。第8页二、地址重定位二、地址重定位常见的地址重定位技术常见的地址重定位技术常见的地址重定位技术常见的地址重定位技术v绝对装入绝对装入(Absolute loading)/固定地址再定位固定地址再定位程序的地址再定位是在程序执行之前被确定的，也就程序的地址再定位是在程序执行之前被确定的，也就是在编译连接时直接生成实际存储器地址是在编译连接时直接生成实际存储器地址(物理地址物理地址)。在此，程序地址空间和内存地址空间是一一对应的。在此，程序地址空间和内存地址空间是一一对应的。优点：装入过程简单。优点：装入过程简单。缺点：与硬件的结构过于密缺点：与硬件的结构过于密切，缺乏灵活性。切，缺乏灵活性。0101010010110101010101101010目标文件目标文件加载加载内存内存逻辑地址逻辑地址物理地址物理地址一一对应一一对应例如：单片机，例如：单片机，MS-DOS中中.com格式程序。格式程序。第9页二、地址重定位二、地址重定位v可重定位装入可重定位装入(Relocatable Loading)即指程序装入内存时，由于程序的逻辑地址和物理地即指程序装入内存时，由于程序的逻辑地址和物理地址不一致，由逻辑地址到物理地址的映射过程。址不一致，由逻辑地址到物理地址的映射过程。分类分类静态再定位：指地址定位时修改程序的逻辑地址值，完成定静态再定位：指地址定位时修改程序的逻辑地址值，完成定位后，在程序的执行期间地址将不再发生变化。特点：在程位后，在程序的执行期间地址将不再发生变化。特点：在程序执行之前进行地址再定位。序执行之前进行地址再定位。优点：无需硬件支持，容易实现。优点：无需硬件支持，容易实现。早期的操作系统中大多数都采早期的操作系统中大多数都采用这种方法。用这种方法。缺点：必须分配连续的存储区域；缺点：必须分配连续的存储区域；执行期间不能扩充存储空间，执行期间不能扩充存储空间，也不能在内存中移动，内存利也不能在内存中移动，内存利用率低，不便于共享。用率低，不便于共享。第10页二、地址重定位二、地址重定位动态再定位：程序在装入内存时，不修改程序的逻辑动态再定位：程序在装入内存时，不修改程序的逻辑地址值，程序在访问物理内存之前，再实时地将逻辑地址值，程序在访问物理内存之前，再实时地将逻辑地址转换成物理地址。地址转换成物理地址。BR:基址寄存器，存放程序的起始地址基址寄存器，存放程序的起始地址VR:变址寄存器，存放需要变址寄存器，存放需要变换的逻辑地址变换的逻辑地址第11页二、地址重定位二、地址重定位优点：优点：程序在执行期间可以换入和换出内存，可以解决程序在执行期间可以换入和换出内存，可以解决内存紧张状态；内存紧张状态；可以在内存中移动可以在内存中移动把内存中的碎片集中起来，把内存中的碎片集中起来，可以充分利用空间；可以充分利用空间；不必给程序分配连续的内存空间，可以较好的利不必给程序分配连续的内存空间，可以较好的利用较小的内存块；用较小的内存块；若干用户可以共享同一程序，实现共享。若干用户可以共享同一程序，实现共享。缺点：需要附加的硬件支持，实现存储管理的软件算缺点：需要附加的硬件支持，实现存储管理的软件算法比较复杂。法比较复杂。第12页三、分区存储管理方案三、分区存储管理方案存储管理方案分类存储管理方案分类存储管理方案分类存储管理方案分类v从操作系统的发展历史来看，存储管理主要有以下几种从操作系统的发展历史来看，存储管理主要有以下几种方案：方案：分区存储管理方案。要求连续分配存储空间，且程序分区存储管理方案。要求连续分配存储空间，且程序要一次性全部装入内存。简单，但是有比较严重的要一次性全部装入内存。简单，但是有比较严重的内内碎块碎块和和外碎块外碎块。段式存储管理方案。不要求连续分配存储空间，段和段式存储管理方案。不要求连续分配存储空间，段和段之间可以不连续，但程序需要一次性全部装入内存。段之间可以不连续，但程序需要一次性全部装入内存。有比较严重的有比较严重的外碎块外碎块。页式存储管理方案。是一种不连续存储管理方案，也页式存储管理方案。是一种不连续存储管理方案，也需要一次性全部装入内存。在逻辑地址空间和物理地需要一次性全部装入内存。在逻辑地址空间和物理地址空间都采用分页的思想。缺点是每一个作业的最后址空间都采用分页的思想。缺点是每一个作业的最后一页有一页有内碎块内碎块。第13页三、分区存储管理方案三、分区存储管理方案段页式存储管理方案。是一种不连续存储方案，段式段页式存储管理方案。是一种不连续存储方案，段式存储管理和页式存储管理的结合。克服了纯分页和纯存储管理和页式存储管理的结合。克服了纯分页和纯分段存储管理思想的缺点。分段存储管理思想的缺点。交换技术和覆盖技术。交换技术和覆盖技术。虚拟存储管理方案。虚拟存储管理方案。第14页三、分区存储管理方案三、分区存储管理方案分区存储管理：分区存储管理：分区存储管理：分区存储管理：v是一种连续分配存储空间的管理方式。曾被广泛地应用是一种连续分配存储空间的管理方式。曾被广泛地应用于于19601970年代的操作系统中。年代的操作系统中。v思想：把内存分为一些大小相等或不等的分区思想：把内存分为一些大小相等或不等的分区(Partition)，装入时每个应用程序占用一个或几个分区，装入时每个应用程序占用一个或几个分区，操作系统占用其中一个分区。适用于多道程序系统和分操作系统占用其中一个分区。适用于多道程序系统和分时系统，支持多个程序并发执行。时系统，支持多个程序并发执行。v分类分类单一连续分区存储管理单一连续分区存储管理固定分区管理固定分区管理可变分区管理可变分区管理第15页三、分区存储管理方案三、分区存储管理方案单一连续分区存储管理单一连续分区存储管理单一连续分区存储管理单一连续分区存储管理特点：一次只能装入一个程序，程特点：一次只能装入一个程序，程序独占整个用户区，如果程序小于序独占整个用户区，如果程序小于用户区，则剩余的空间浪费，如果用户区，则剩余的空间浪费，如果大于，则无法装入。大于，则无法装入。优点：简单，适用于单用户、单任优点：简单，适用于单用户、单任务的操作系统，不需要复杂的硬件务的操作系统，不需要复杂的硬件支持。支持。缺点：一个作业运行时要占用整个缺点：一个作业运行时要占用整个内存地址空间，对内存造成了很大内存地址空间，对内存造成了很大的浪费，不支持大作业。的浪费，不支持大作业。第16页三、分区存储管理方案三、分区存储管理方案固定分区管理固定分区管理固定分区管理固定分区管理v支持多道程序技术支持多道程序技术v实现方法：实现方法：初始化内存空间初始化内存空间分区状态表分区状态表 程序程序A(30K)程序程序A已分配已分配内碎片：指占用分区之内未内碎片：指占用分区之内未被利用的空间被利用的空间。第17页三、分区存储管理方案三、分区存储管理方案v特点：特点：内存中同时可以容纳多道程序；内存中同时可以容纳多道程序；程序必须连续存放，且要一次全部装入。程序必须连续存放，且要一次全部装入。v优点：优点：比单一连续分配方法，内存的利用率提高了；比单一连续分配方法，内存的利用率提高了；可以支持多道程序；可以支持多道程序；实现简单，开销小。实现简单，开销小。v缺点：缺点：作业必须预先能够估计自己要占用多大的内存空间，作业必须预先能够估计自己要占用多大的内存空间，有时候这是难以做到的；有时候这是难以做到的；存在内碎片，造成存储空间的浪费；存在内碎片，造成存储空间的浪费；分区总数固定，限制了并发执行的程序数目。分区总数固定，限制了并发执行的程序数目。第18页三、分区存储管理方案三、分区存储管理方案可变分区可变分区可变分区可变分区(Dynamic Partitioning)(Dynamic Partitioning)v思想：预先不划分内存，当作业需要时向系统申请，系思想：预先不划分内存，当作业需要时向系统申请，系统从其中挖出一块给该作业，其大小等于作业所需内存统从其中挖出一块给该作业，其大小等于作业所需内存的大小，然后将剩下的部分再作为空表块，给下一次分的大小，然后将剩下的部分再作为空表块，给下一次分配使用。配使用。OSJob1Job2Job4Job3Q:如何管理这些空闲区？如何管理这些空闲区？m_sizem_addrm_sizem_addrm_sizem_addrm_sizem_addr0线性表格法线性表格法m_sizem_addrm_sizem_addr链接法链接法Job5第19页三、分区存储管理方案三、分区存储管理方案分区分配算法分区分配算法分区分配算法分区分配算法v最先适应算法最先适应算法(first-fit)分配方法：将所有的空闲分区按照地址递增的顺序排分配方法：将所有的空闲分区按照地址递增的顺序排列，按照分区的先后次序，从头开始查找，符合要求列，按照分区的先后次序，从头开始查找，符合要求的第一个分区就是要找的分区。的第一个分区就是要找的分区。OSJob2Job4Job5m_sizem_addrm_sizem_addrm_sizem_addr0第20页三、分区存储管理方案三、分区存储管理方案释放方法释放方法OSJob2Job4Job5规则：相邻合并，否则插入规则：相邻合并，否则插入第21页三、分区存储管理方案三、分区存储管理方案优点：优点：分配策略简单。分配策略简单。尽可能利用存储区低地址的空闲区，而在高地址尽可能利用存储区低地址的空闲区，而在高地址部分保存较大的空闲区，容易满足大作业。部分保存较大的空闲区，容易满足大作业。在释放内存分区时，如果有相邻的空白区就进行在释放内存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区。合并，使其成为一个较大的空白区。缺点：缺点：查找总是从表首开始，因此前面的空闲区往往被查找总是从表首开始，因此前面的空闲区往往被分割得很小时，查找次数增大。分割得很小时，查找次数增大。会产生外碎片会产生外碎片(指占用的分区之间难以利用的空闲指占用的分区之间难以利用的空闲分区分区)，这些碎片散布在存储器的各处，不能集中，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。使用，因而降低了存储器的利用率。第22页三、分区存储管理方案三、分区存储管理方案v下次适应算法下次适应算法(next-fit，循环最先适应算法，循环最先适应算法)分配方法：按分区的先后次序，从上次分配的分区起分配方法：按分区的先后次序，从上次分配的分区起查找，到最后分区时再回到开头，符合要求的第一个查找，到最后分区时再回到开头，符合要求的第一个分区就是找到的分区。分区就是找到的分区。释放方法：同于最先适应算法。释放方法：同于最先适应算法。优点：使空闲分区分布得更均匀，提高了分配查找的优点：使空闲分区分布得更均匀，提高了分配查找的速度。速度。缺点：较大的空闲分区不易保留。缺点：较大的空闲分区不易保留。第23页三、分区存储管理方案三、分区存储管理方案v最佳适应算法最佳适应算法(best-fit)分配方法：将所有的空闲分区按照其容量递增的顺序分配方法：将所有的空闲分区按照其容量递增的顺序排列，当要求分配一个空白分区时，由小到大进行查排列，当要求分配一个空白分区时，由小到大进行查找，找到最合适的分配。找，找到最合适的分配。释放方法：在整个链表上搜索地址相邻的空闲区，合释放方法：在整个链表上搜索地址相邻的空闲区，合并后，再插入到合适的位置。并后，再插入到合适的位置。优点：优点：分配后所剩余的空白块会最小，较大的空闲分区会被保留。分配后所剩余的空白块会最小，较大的空闲分区会被保留。平均，只要查找一半的表格便能找到最佳适应的空白区；平均，只要查找一半的表格便能找到最佳适应的空白区；如果有一个空白区的容量正好满足要求，则它必被选中。如果有一个空白区的容量正好满足要求，则它必被选中。缺点：空白区一般不可能恰好满足要求，在分配之后缺点：空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用，会形成的剩余部分通常非常小，以致小到无法使用，会形成较多外碎片。较多外碎片。第24页三、分区存储管理方案三、分区存储管理方案v最坏适应算法最坏适应算法(worst-fit)分配方法：与最佳适应算法相反，将所有的空白分区分配方法：与最佳适应算法相反，将所有的空白分区按容量递减的的顺序排列，最前面的最大的空闲分区按容量递减的的顺序排列，最前面的最大的空闲分区就是找到的分区。就是找到的分区。释放方法：同于最佳适应算法释放方法：同于最佳适应算法(best-fit)优点：分配的时候，只需查找一次，就可以成功，分优点：分配的时候，只需查找一次，就可以成功，分配的算法很快。配的算法很快。缺点：最后剩余的分区会越来越小，不会保留较大的缺点：最后剩余的分区会越来越小，不会保留较大的空闲分区，无法运行大程序。空闲分区，无法运行大程序。第25页三、分区存储管理方案三、分区存储管理方案可再定位式分区可再定位式分区可再定位式分区可再定位式分区v又称浮动分区分配，是解决碎片问题的简单而有效的办法。又称浮动分区分配，是解决碎片问题的简单而有效的办法。v基本思想：移动所有被分配的分区，使之成为一个连续区域，而留基本思想：移动所有被分配的分区，使之成为一个连续区域，而留下一个较大的空白区。下一个较大的空白区。“靠拢靠拢”或或“紧凑紧凑”Q:程序地址的再程序地址的再定位？定位？第26页提出原因提出原因提出原因提出原因四、页式存储管理四、页式存储管理分区存储管理方案分区存储管理方案要求作业存储时必须连续存放要求作业存储时必须连续存放OSJob1Job3Job2Job4Job5页式存储管理方案页式存储管理方案解决作业不连续存放的问题解决作业不连续存放的问题第27页逻辑地址空间逻辑地址空间01K2K3K4K四、页式存储管理四、页式存储管理基本原理基本原理基本原理基本原理物理地址空间物理地址空间0100K101K102K103K104K105K106K107K108K109KOS012345678实页实页/主页主页0123虚页：大小相同，虚页：大小相同，常为常为2的整数幂。的整数幂。2031Q:如何记录和管如何记录和管理这种映射关系？理这种映射关系？第28页四、页式存储管理四、页式存储管理页面变换表页面变换表页面变换表页面变换表(Page management table)(Page management table)v是一种特殊的数据结构是一种特殊的数据结构v用途：记录每一个作业的虚页号到物理内存中页号之间用途：记录每一个作业的虚页号到物理内存中页号之间的映射关系。每一个作业都拥有一个自己的页面变换表。的映射关系。每一个作业都拥有一个自己的页面变换表。v结构：结构：0虚页号虚页号3实页号实页号162135Job1Job2总页表总页表起始地址起始地址长度长度作业作业IDSL页表控制寄存器页表控制寄存器起始地址起始地址长度长度第29页四、页式存储管理四、页式存储管理物理地址空间物理地址空间OS012345678逻辑地址空间逻辑地址空间0123203101K2K3K4K0100K101K102K103K104K105K106K107K108K109K虚页号虚页号实页号实页号03162135LOAD A 逻辑地址逻辑地址3页号页号页内偏移量页内偏移量10013453K3100第30页四、页式存储管理四、页式存储管理地址变换过程地址变换过程地址变换过程地址变换过程Q:为了取出一个为了取出一个数据，系统需要访数据，系统需要访问内存几次？问内存几次？第31页四、页式存储管理四、页式存储管理快表快表快表快表v由一组联想寄存器由一组联想寄存器(TLB,Translation Lookaside Buffer)组成。组成。v联想寄存器：一种按内容进行并行查找的快速寄存器，联想寄存器：一种按内容进行并行查找的快速寄存器，访问速度比主存快得多。访问速度比主存快得多。v原理：原理：第32页四、页式存储管理四、页式存储管理经常要访问的页表经常要访问的页表表项。表项。第33页四、页式存储管理四、页式存储管理空闲内存页的管理空闲内存页的管理空闲内存页的管理空闲内存页的管理位示图位示图bitbyteQ:内存大小：内存大小：256M，每页，每页4K，位示图有多大？，位示图有多大？第34页四、页式存储管理四、页式存储管理优点优点优点优点v没有外碎片，每个内碎片不超过页大小。没有外碎片，每个内碎片不超过页大小。v程序不必连续存放。程序不必连续存放。主要缺点：主要缺点：主要缺点：主要缺点：v程序要一次全部装入内存才能执行。程序要一次全部装入内存才能执行。v采用动态地址变换机构会增加计算机的成本和降低处理采用动态地址变换机构会增加计算机的成本和降低处理机的速度。机的速度。v各种数据结构各种数据结构(页表，空闲页表页表，空闲页表)要占用一定的内存空间，要占用一定的内存空间，而且系统要花费一定的时间来建立和管理这些表格。而且系统要花费一定的时间来建立和管理这些表格。v依然存在内碎片。依然存在内碎片。第35页五、段式存储管理五、段式存储管理基本思想基本思想基本思想基本思想逻辑单位逻辑单位内存管理采用可变内存管理采用可变分区动态分配法。分区动态分配法。段表段表总段表总段表/系统段表系统段表起始地址起始地址长度长度作业作业ID第36页五、段式存储管理五、段式存储管理地址变换过程地址变换过程地址变换过程地址变换过程段表控制寄存器段表控制寄存器第37页五、段式存储管理五、段式存储管理优点优点优点优点v没有内碎片，外碎片可以通过内存紧缩来消除。没有内碎片，外碎片可以通过内存紧缩来消除。v便于实现共享，即允许若干个进程共享一个或者多个段。便于实现共享，即允许若干个进程共享一个或者多个段。第38页分页式管理和分段式管理的比较分页式管理和分段式管理的比较分页式管理和分段式管理的比较分页式管理和分段式管理的比较五、段式存储管理五、段式存储管理内容内容页式存储管理页式存储管理段式存储管理段式存储管理划分依据划分依据系统管理需要系统管理需要用户应用需要用户应用需要页页/段大小段大小各页面大小相同各页面大小相同段的大小不固定段的大小不固定逻辑地址逻辑地址只有一个逻辑地址空间只有一个逻辑地址空间每个段一个独立的逻辑地每个段一个独立的逻辑地址空间址空间页表页表/段表段表页面较多，页表较长，查找页面较多，页表较长，查找费时费时段较少，段表较短，查找段较少，段表较短，查找速度快速度快碎片碎片存在内碎片存在内碎片存在外碎片存在外碎片内存共享内存共享不支持不支持支持支持存储扩充存储扩充不支持不支持不支持不支持第39页六、段页式存储管理六、段页式存储管理思想：思想：思想：思想：逻辑地址空间逻辑地址空间物理地址空间物理地址空间.03K.0.5K03K逻辑地址格式逻辑地址格式?第40页六、段页式存储管理六、段页式存储管理第41页六、段页式存储管理六、段页式存储管理地址变换过程地址变换过程地址变换过程地址变换过程Q：为了获得一条指令或者数：为了获得一条指令或者数据，需要访问内存几次？据，需要访问内存几次？第42页七、内存扩充技术七、内存扩充技术提出原因提出原因提出原因提出原因v在基本的存储管理系统中，当一个作业的程序地址空间在基本的存储管理系统中，当一个作业的程序地址空间大于内存可以使用的空间时，该作业就不能装入运行，大于内存可以使用的空间时，该作业就不能装入运行，并发运行进程数受到了内存空间的限制。并发运行进程数受到了内存空间的限制。内存扩充技术内存扩充技术内存扩充技术内存扩充技术v就是借助大容量的辅存在逻辑上实现内存的扩充，来解就是借助大容量的辅存在逻辑上实现内存的扩充，来解决内存容量不足的问题。决内存容量不足的问题。第43页程序程序(190K)七、内存扩充技术七、内存扩充技术覆盖技术覆盖技术覆盖技术覆盖技术(Overlay)(Overlay)v目标：在较小的可用内存中运行较大的程序。目标：在较小的可用内存中运行较大的程序。v原理原理A(20K)B(50K)C(30K)D(20K)E(40K)F(30K)覆盖段覆盖段第44页七、内存扩充技术七、内存扩充技术v覆盖技术的优缺点覆盖技术的优缺点优点优点有效利用内存空间，提高系统的并发性。有效利用内存空间，提高系统的并发性。缺点缺点覆盖结构需要程序员在程序编写的时候精心安排，覆盖结构需要程序员在程序编写的时候精心安排，并用覆盖描述语言描述，增加编程复杂度；并用覆盖描述语言描述，增加编程复杂度；从外存装入覆盖文件，是以时间延长来换取空间从外存装入覆盖文件，是以时间延长来换取空间节省的；节省的；覆盖区仍然存在着碎片。覆盖区仍然存在着碎片。第45页内存内存七、内存扩充技术七、内存扩充技术交换技术交换技术交换技术交换技术(swapping)(swapping)v最早应用于最早应用于MIT开发的开发的CTSS中。中。v原理原理外存外存Job2Job3Job1Job4第46页七、内存扩充技术七、内存扩充技术v交换技术的优缺点交换技术的优缺点优点：优点：增加并发运行的程序数目增加并发运行的程序数目可以提供优先级服务可以提供优先级服务缺点：缺点：对换入和换出的控制增加处理机开销；对换入和换出的控制增加处理机开销；程序换入时的重定位问题。程序换入时的重定位问题。v交换技术和覆盖技术的区别交换技术和覆盖技术的区别内容内容覆盖技术覆盖技术交换技术交换技术适用情况适用情况作业内部作业内部作业之间作业之间对程序结构的影响对程序结构的影响有有无无第47页八、虚拟存储技术八、虚拟存储技术虚拟存储技术也是一种存储扩充技术。虚拟存储技术也是一种存储扩充技术。虚拟存储技术也是一种存储扩充技术。虚拟存储技术也是一种存储扩充技术。基础基础基础基础v程序中不是每一条指令都会在程序的一次运行过程中执程序中不是每一条指令都会在程序的一次运行过程中执行到。行到。错误处理子程序错误处理子程序条件语句条件语句(if.else.)v程序中有的指令可能只执行一次程序中有的指令可能只执行一次程序的初始化部分程序的初始化部分v程序执行的局部性原理：在一段时间内，作业一般不会程序执行的局部性原理：在一段时间内，作业一般不会执行到所有程序的指令，也不会存取绝大部分数据，执执行到所有程序的指令，也不会存取绝大部分数据，执行的代码和要存取的数据往往集中在某些区域中行的代码和要存取的数据往往集中在某些区域中(例如一例如一个循环、一个数组个循环、一个数组)。第48页八、虚拟存储技术八、虚拟存储技术原理：原理：原理：原理：v在程序装入时，不必一次将其全部读入到内存，而只需在程序装入时，不必一次将其全部读入到内存，而只需将当前需要执行的某些区域读入到内存，然后程序开始将当前需要执行的某些区域读入到内存，然后程序开始执行。在程序执行过程中，如果需执行的指令或访问的执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存，则由处理器通知操作系统将相应的区数据尚未在内存，则由处理器通知操作系统将相应的区域调入内存，然后继续执行。域调入内存，然后继续执行。带来的好处带来的好处带来的好处带来的好处v程序的大小可以突破内存容量限制，使得用户感觉到系程序的大小可以突破内存容量限制，使得用户感觉到系统好像提供了一个容量极大的统好像提供了一个容量极大的“主存主存”。v内存中容纳更多程序并发执行。内存中容纳更多程序并发执行。第49页八、虚拟存储技术八、虚拟存储技术虚拟存储技术分类虚拟存储技术分类虚拟存储技术分类虚拟存储技术分类v虚拟页式存储管理虚拟页式存储管理纯页式管理纯页式管理 请求调页请求调页v虚拟段式存储管理虚拟段式存储管理纯段式管理纯段式管理 请求调段请求调段v虚拟段页式存储管理虚拟段页式存储管理虚拟页式管理虚拟页式管理 虚拟段式管理虚拟段式管理第50页逻辑地址空间逻辑地址空间物理地址空间物理地址空间九、虚拟页式存储技术九、虚拟页式存储技术工作原理工作原理工作原理工作原理012345678.012CPUOS缺页中断缺页中断缺页中断处缺页中断处理子程序理子程序3页表页表Q：当内存中没有空闲页面时，如果还要调入一个新页，如何处理？：当内存中没有空闲页面时，如果还要调入一个新页，如何处理？第51页九、虚拟页式存储技术九、虚拟页式存储技术页面淘汰算法页面淘汰算法页面淘汰算法页面淘汰算法v页面置换算法决定在需要调入页面时，选择内存中哪个页面置换算法决定在需要调入页面时，选择内存中哪个物理页面被置换。物理页面被置换。v出发点：希望把未来不再使用的或者短时期内较少使用出发点：希望把未来不再使用的或者短时期内较少使用的页面调出。的页面调出。v常见的页面淘汰算法常见的页面淘汰算法第52页九、虚拟页式存储技术九、虚拟页式存储技术最佳算法最佳算法最佳算法最佳算法(OPT)(OPT)v思想：选择从当前时刻开始以后不在使用的页面淘汰，思想：选择从当前时刻开始以后不在使用的页面淘汰，如果没有这类页，则选择离当前页最远位置上出现的页如果没有这类页，则选择离当前页最远位置上出现的页面淘汰。面淘汰。v优点：使得页面调入调出的次数达到最小，这是一种理优点：使得页面调入调出的次数达到最小，这是一种理想情况。想情况。v缺点：实际上无法实现，因为系统无法预知未来页面的缺点：实际上无法实现，因为系统无法预知未来页面的访问情况。因此只能用作理论上性能评价的标准。访问情况。因此只能用作理论上性能评价的标准。第53页九、虚拟页式存储技术九、虚拟页式存储技术先进先出页面淘汰算法先进先出页面淘汰算法先进先出页面淘汰算法先进先出页面淘汰算法(FIFO)(FIFO)v思想：选择最早调入内存的页面淘汰。思想：选择最早调入内存的页面淘汰。v出发点：近期调入的页面被再次访问的概率要大于早期出发点：近期调入的页面被再次访问的概率要大于早期调入的页面。调入的页面。v问题：事实上并非所有的时候都这样。此时问题：事实上并非所有的时候都这样。此时FIFO算法的算法的性能较差。性能较差。v举例：举例：第54页九、虚拟页式存储技术九、虚拟页式存储技术设页面走向为设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主，主存容量存容量M=3，采用，采用FIFO进行页面淘汰。进行页面淘汰。缺页中断次数缺页中断次数F=9，而缺页率，而缺页率f=9/12=75%第55页九、虚拟页式存储技术九、虚拟页式存储技术Belady现象：可用页面增大，缺页率反而升高的现象。现象：可用页面增大，缺页率反而升高的现象。原因：原因：FIFO算法的置换特征与进程访问内存的动态特征是算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。矛盾的，即被置换的页面并不是进程不会访问的。主存容量主存容量M=4缺页中断次数缺页中断次数F=10，而缺页率，而缺页率f=9/12=83%第56页九、虚拟页式存储技术九、虚拟页式存储技术最近最少使用页面淘汰算法最近最少使用页面淘汰算法最近最少使用页面淘汰算法最近最少使用页面淘汰算法(LRU,Least Recently(LRU,Least Recently Used)Used)v思想：每次选择内存中离当前时刻最久未使用过的页面思想：每次选择内存中离当前时刻最久未使用过的页面淘汰。淘汰。v根据：局部性原理。根据：局部性原理。v实现方法实现方法硬件方法：硬件方法：一个特殊的栈：把被访问的页面移到栈顶，于是一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位每个页面设立移位寄存器：被访问时左边最高位置置1，定期右移并且最高位补，定期右移并且最高位补0，于是寄存器数值，于是寄存器数值最小的是最久未使用页面。最小的是最久未使用页面。第57页九、虚拟页式存储技术九、虚拟页式存储技术软件方法软件方法增加系统开销增加系统开销第58页九、虚拟页式存储技术九、虚拟页式存储技术v算法举例算法举例设页面走向为设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量，主存容量M=3，采用，采用LRU算法进行页面淘汰。算法进行页面淘汰。缺页中断次数缺页中断次数F=10，缺页率，缺页率f=1012=83 第59页九、虚拟页式存储技术九、虚拟页式存储技术主存容量主存容量M=4缺页中断次数缺页中断次数F=8，缺页率，缺页率f=8/12=67 结论：结论：LRU算法不会出现算法不会出现Belady现象。现象。第60页九、虚拟页式存储技术九、虚拟页式存储技术LRULRU算法的优缺点算法的优缺点算法的优缺点算法的优缺点v优点优点不会出现不会出现Belady现象现象性能较好，接近性能较好，接近OPT算法算法v缺点缺点算法效率不高算法效率不高需要对整个页表频繁进行维护。需要对整个页表频繁进行维护。比较是算法的基本操作，当页面较多时会消耗大比较是算法的基本操作，当页面较多时会消耗大量时间。量时间。第61页九、虚拟页式存储技术九、虚拟页式存储技术最近未使用页面淘汰算法最近未使用页面淘汰算法最近未使用页面淘汰算法最近未使用页面淘汰算法(NRU,Not Recently(NRU,Not Recently Used)Used)第二次机会淘汰算法第二次机会淘汰算法第二次机会淘汰算法第二次机会淘汰算法(SCR)(SCR)页面缓冲算法页面缓冲算法页面缓冲算法页面缓冲算法(Page Buffering)(Page Buffering)第62页九、虚拟页式存储技术九、虚拟页式存储技术性能分析性能分析性能分析性能分析v颠簸颠簸/抖动抖动(thrashing)页面在内存与外存之间频繁调度，以至于调度页面所页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。动。主要原因：主要原因：页面淘汰算法不合理。页面淘汰算法不合理。分配给进程的物理页面数太少。分配给进程的物理页面数太少。第63页九、虚拟页式存储技术九、虚拟页式存储技术v工作集工作集对一个作业来说，当分配给它的页面数目小于某一个对一个作业来说，当分配给它的页面数目小于某一个数值时，其缺页中断次数急剧增加，甚至出现页面抖数值时，其缺页中断次数急剧增加，甚至出现页面抖动现象；而高于这个页面数时，缺页中断次数不会明动现象；而高于这个页面数时，缺页中断次数不会明显减少。此时我们称这个页面数范围为页面的显减少。此时我们称这个页面数范围为页面的“工作工作集集”。影响工作集的因素影响工作集的因素作业的特征（结构、大小、访问数据的规律等）作业的特征（结构、大小、访问数据的规律等）作业的运行时间段等作业的运行时间段等第64页九、虚拟页式存储技术九、虚拟页式存储技术v如何提升系统性能、避免抖动现象如何提升系统性能、避免抖动现象系统可以动态的计算缺页中断率，从而估计工作集的系统可以动态的计算缺页中断率，从而估计工作集的大小，并根据情况给予调整。大小，并根据情况给予调整。例如：当系统中很多作业所分配到的页面大小小于工例如：当系统中很多作业所分配到的页面大小小于工作集时，应当挂起某些作业，然后将其所占用的主存作集时，应当挂起某些作业，然后将其所占用的主存空间分配给优先级高的作业，以避免抖动现象发生。空间分配给优先级高的作业，以避免抖动现象发生。第65页十、高速缓冲存储器十、高速缓冲存储器简称高速缓存简称高速缓存简称高速缓存简称高速缓存v是为了匹配是为了匹配CPU的处理速率与内存的访问速度而增加的的处理速率与内存的访问速度而增加的高速存储器。其目标是提高高速存储器。其目标是提高CPU的利用率。高速缓存的的利用率。高速缓存的使用对用户是透明的。使用对用户是透明的。v高速缓存大小有限，因此对高速缓存管理方法的设计十高速缓存大小有限，因此对高速缓存管理方法的设计十分重要，通过精心的选择缓存大小和设置合理的置换策分重要，通过精心的选择缓存大小和设置合理的置换策略，可以使得命中率达到略，可以使得命中率达到80%99%，从而极大的提高，从而极大的提高系统的性能。系统的性能。第66页十、高速缓冲存储器十、高速缓冲存储器v高速缓存的组织结构高速缓存的组织结构主要作用是缓存内存中数据，缓冲主要作用是缓存内存中数据，缓冲存储器分为若干块存储器分为若干块 描述各缓冲存储器描述各缓冲存储器块的状态，缓冲目块的状态，缓冲目录的表项与缓冲存录的表项与缓冲存储器块一一对应储器块一一对应负责缓存目录的维护和利负责缓存目录的维护和利用缓存淘汰算法进行缓存用缓存淘汰算法进行缓存的更新的更新第67页本章小结本章小结概述概述概述概述v存储体系层次存储体系层次v地址重定位地址重定位存储管理方案存储管理方案存储管理方案存储管理方案v分区存储管理方案分区存储管理方案v页式存储管理方案页式存储管理方案v段式存储管理方案段式存储管理方案v段页式存储管理方案段页式存储管理方案内存扩充技术内存扩充技术内存扩充技术内存扩充技术v覆盖技术覆盖技术v交换技术交换技术v虚拟存储技术虚拟存储技术请求页式存储管理请求页式存储管理性能：抖动，工作集等性能：抖动，工作集等高速缓冲技术高速缓冲技术高速缓冲技术高速缓冲技术第68页作业作业作业作业P192 习题习题 2，15，16，18，20