第4章存储管理ppt课件.ppt

《第4章存储管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章存储管理ppt课件.ppt（95页珍藏版）》请在三一办公上搜索。

1、第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器 4.6 实例：Windows存储管理,本章主要内容,兰州理工大学计算机与通信学院,存储管理一直是操作系统中的重要组成部分，因为冯诺依曼体系结构就是建立在存储程序概念上的，访问存储器的操作占CPU时间的70%左右。计算机系统中的存储器一般分为主存储器（简称主存、内存）和辅助存储器（简称辅存）。由于CPU只能直接与内存进行通信，因此计算机系统的程序以及与该程序相关的数据，只有被装入到内存中才能有效地执行。计算机系统能否高效地管理内存空间，不仅直接反映存储器的利用率，还会影响整个

2、操作系统的性能。,兰州理工大学计算机与通信学院,第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器,兰州理工大学计算机与通信学院,4.1 概述,4.1.1 存储层次4.1.2 地址转换4.1.3 程序的装入,兰州理工大学计算机与通信学院,1层次结构,兰州理工大学计算机与通信学院,2高速缓存 高速缓存通常采用静态存储器（SRAM），速度小于25ns，常见的容量有128KB和256KB两种。它可以位于CPU和MMU之间（称为虚地址Cache），也可以位于MMU和内存之间（称为实地址Cache）。 Cache的管理 Cache数据

3、的一致性问题,兰州理工大学计算机与通信学院,4.1 概述,4.1.1 存储层次4.1.2 地址转换4.1.3 程序的装入,兰州理工大学计算机与通信学院,1逻辑地址和物理地址 通常用户程序是用高级语言编写的，并以二进制的形式保存在计算机的辅存中，称为源程序，源程序经过编译得到计算机能理解的目标程序，目标程序中的地址称为逻辑地址（相对地址） 。 计算机主存中每个存储单元都有一个编号与之对应，这些编号称为物理地址（绝对地址）。,兰州理工大学计算机与通信学院,2地址转换,将用户程序中的指令或数据的逻辑地址转换为存储空间中物理地址的工作称为地址转换或重定位。 地址转换有两种方法：静态重定位、 动态重定位

4、,兰州理工大学计算机与通信学院,静态地址重定位,兰州理工大学计算机与通信学院,动态地址重定位,兰州理工大学计算机与通信学院,4.1 概述,4.1.1 存储层次4.1.2 地址转换4.1.3 程序的装入,兰州理工大学计算机与通信学院,程序在运行期间，被分为不同的生命期，每一步地址都有不同形式：编译阶段 链接阶段装入阶段 执行阶段,兰州理工大学计算机与通信学院,第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器,兰州理工大学计算机与通信学院,4.2 基本存储空间管理,4.2.1 单用户存储管理4.2.2 固定分区存储管理4.2.

5、3 可变分区存储管理4.2.4 交换,兰州理工大学计算机与通信学院,这是最简单的一种存储管理方法，用于早期单用户系统中。 它的最大特点是内存分配方式简单，整个内存空间被分割成系统区和用户区两部分，系统区用来存放操作系统驻留代码和数据，剩余空间则全部作为用户区，分配给一个用户作业使用。,兰州理工大学计算机与通信学院,单用户存储管理内存分配,兰州理工大学计算机与通信学院,单用户存储管理的存储保护,兰州理工大学计算机与通信学院,4.2 基本存储空间管理,4.2.1 单用户存储管理4.2.2 固定分区存储管理4.2.3 可变分区存储管理4.2.4 交换,兰州理工大学计算机与通信学院,固定分区存储管理是

6、满足多道程序环境的最简单的存储管理方案。 “固定”是指分区的大小和个数是在开机时由系统管理员指定，直到关机都不会再重新划分。每个分区只能存储一个进程，进程也只能在它所驻留的分区中运行。 一个计算机系统中可以运行的进程数依赖于内存中的分区数量。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,在多道程序环境下，可能出现申请分配存储空间的进程数大于内存的分区数，这就需要先将这些进程排队，当出现空闲分区时再从队列中取出，为其分配分区。,兰州理工大学计算机与通信学院,固定分区存储管理的地址映射和存储保护,兰州理工大学计算机与通信学院,4.2 基本存储空间管理,4.2.1 单用户存储管理4.

7、2.2 固定分区存储管理4.2.3 可变分区存储管理4.2.4 交换,兰州理工大学计算机与通信学院,1、可变分区存储管理的基本原理 系统初启后，在内存中除常驻操作系统，其余空间为一个完整的大空闲区。当有进程申请分配内存空间时，系统从该空闲区中划分出一块与进程大小相同的区域进行分配。,兰州理工大学计算机与通信学院,可变分区存储管理中可以采用两种数据结构来完成存储空间的分配和回收。 空闲分区表 空闲分区链,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,例：假设一个计算机系统的内存为2560KB，采用可变分区存储管理，操作系统占用内存低地址的400KB，则用户区的内存为2160KB 。

8、,输入队列如下：进程 内存（KB） 时间 J1 600 10 J2 400 5 J3 900 10 J4 300 18 J5 800 20,兰州理工大学计算机与通信学院,2分区的分配策略常用的分配策略有五种： 最先适应算法（First Fit，FF） 下次适应算法（Next Fit，NF） 最佳适应算法（Best Fit，BF） 最坏适应算法（Worst Fit，WF） 快速适应法 (Quick Fit，QF),兰州理工大学计算机与通信学院,3可变分区的回收 外部碎片有两种含义：一是指很小且很难分出的内存空间；另一种是当内存中的所有空闲分区的长度之和足够装入一个进程，但各个单个空闲分区的长度却

9、不够装入一个进程，这些空闲分区就称为外部碎片。 随着运行时间的增加，外部碎片的数量也会增多，这就势必会增加内存空间的浪费，而且空闲分区的查找效率也要降低。解决外部碎片的办法，就是紧凑（Compaction）。在空闲分区回收时将它与相邻的分区进行合并，形成一个大的空闲分区。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,4地址转换与存储保护 地址转换机构中的两个寄存器：界限寄存器和基址寄存器，分别存放作业占用的连续存储空间的长度，和分配给作业的分区的最小绝对地址值。 在进程运行过程中执行紧凑操作，需要移动内存中的代码，这时只要用新的起始地址代替基址寄存器中的地址即可，而不需要修改程

10、序。有些系统为计算机提供多对基址/限长寄存器，允许一个进程占用多个分区。这些寄存器中有一对寄存器所指示的区域是共享的，可以存放共享代码和数据。,兰州理工大学计算机与通信学院,4.2 基本存储空间管理,4.2.1 单用户存储管理4.2.2 固定分区存储管理4.2.3 可变分区存储管理4.2.4 交换,兰州理工大学计算机与通信学院,利用交换（Swapping）技术可以有效缓解内存紧张的问题。 交换又称对换，指在内存空间不够时，先把内存中暂时不用的程序和数据换出到辅存，将已具备运行条件的进程调入到内存。 一般交换是以进程为单位的，称为“进程交换”，因此进程的大小必须小于内存的大小，大于内存的进程还是

11、无法运行。,兰州理工大学计算机与通信学院,1进程的换出 当系统发现内存不够时，将调用对换程序逐个检查内存中驻留的进程，从处于阻塞或睡眠状态的进程中，按一定规则选出一个进程换出。 系统首先申请辅存存储空间，申请成功后便将程序和数据写入辅存，并调用释放内存的程序，释放该进程所占有的内存空间，修改相应的内存分配表等数据结构。,兰州理工大学计算机与通信学院,2进程的换入 首先要检查所有状态为“就绪且换出”的进程，为了避免一些优先级低的进程会被频繁执行对换操作，要优先考虑换出时间长的进程作为换入对象。 然后根据进程的大小在内存中申请空间，如果没有合适大小的内存空间，则要将一些进程先换出。,兰州理工大学计

12、算机与通信学院,第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器,兰州理工大学计算机与通信学院,4.3 分页存储管理,4.3.1 分页存储管理的基本原理4.3.2 硬件结构4.3.3 页表结构,兰州理工大学计算机与通信学院,1页框的划分 内存空间被划分为等长的区域，每个区域称为一个页框。页框的大小是由硬件决定的，通常情况下每个页框的大小是2i，起始地址由0开始，则页框内的地址范围是02i1，这称为页框内地址。 假设内存空间地址是2n，则可划分为2n-i个页框，每个页框也从0开始进行编号，称为页框号。 计算可知，内存中第k个

13、页框的地址范围是：k2i（k1）2i1。,兰州理工大学计算机与通信学院,对于一个内存单元，其物理地址可由以下公式计算得到： 物理地址第k页框起始地址页框内地址 页框号2k页框内地址 通过该公式可以看出，页框号是物理地址的高n-i位，而页框内地址是低i位，则物理地址可表示为：,兰州理工大学计算机与通信学院,2页的划分 用户进程的逻辑空间也被划分为若干等长的区域，每个区域称为页。 页的长度与页框长度相同，即共有2i个存储单元。与页框类似，也从0开始依次编号，称为页号。 每个页内单元从0开始依次编址，到2i1结束，称为页内地址。,兰州理工大学计算机与通信学院,页号=逻辑地址/页长 页内地址=逻辑地址

14、%页长 即：将逻辑地址中的高n-i 位表示页号，低i位表示页内地址，则可得到逻辑地址。,兰州理工大学计算机与通信学院,3页与页框的对应关系页框中的碎片问题页框的大小页表 描述页号、页框号的对应关系。,兰州理工大学计算机与通信学院,4.3 分页存储管理,4.3.1 分页存储管理的基本原理4.3.2 硬件结构4.3.3 页表结构,兰州理工大学计算机与通信学院,1地址转换机构 分页存储管理的地址转换是动态地址重定位的过程：首先由CPU产生逻辑地址，并由系统将其划分为页号和页内地址两部分。然后以页号为进程页表的索引找到页框号。查找前要进行越界检查，查看页号是否大于页表的长度，如果大于则表示此次转换地址

15、已经超出范围，系统将产生一个越界中断。如果页号小于页表长度，则将页框号和页内地址合并得到物理地址。,兰州理工大学计算机与通信学院,+,兰州理工大学计算机与通信学院,2存储分配过程 要建立一个进程，操作系统将根据内存页框的大小将进程的逻辑存储空间划分成相应大小的页。 首先检查内存中的页框数是否满足该进程的要求； 根据总页表，从第0行开始给进程分配页框，找到总页表中内容为“0”的行，将该行改为“1”，并将行数顺序写入页表; 如果没有足够的空闲页框，则该进程放入等待队列排队。,兰州理工大学计算机与通信学院,3含有快表的地址转换 使用页表后，要两次访问内存后才能得到所需程序或数据，这样将使计算机的处理

16、速度降低一半。 相联存储器（Associative Memory），也称转换检测缓冲区（Translation Look Aside Buffer，TLB） TLB的特点是，访问速度比内存要快，具备一定的逻辑判断能力，可实现按内容检索，但造价很高。,兰州理工大学计算机与通信学院,如果要查找的页号已经登记在快表中，则称为命中（Hit），否则称为失误（Miss）。命中率（Hit Ratio）指的是通过快表实现内存访问的比率，定义为： 命中率(命中次数/(命中次数失误次数)100 例：假设访问快表需要20ns，直接访问内存的时间为100ns，假设快表的命中率是90，则有效访问时间是： 12090%2

17、2010%130ns,兰州理工大学计算机与通信学院,4页的共享与保护 实现数据共享时，可允许不同的进程对共享数据页使用不同的页号，只要让各自页表中的相关项指向共享的页框就可以了。 程序共享实现时要复杂些，由于分页存储管理要求逻辑地址空间是连续的，所以程序运行前它们的页号就是确定的。 页的保护：保护权限位 、保护键,兰州理工大学计算机与通信学院,4.3 分页存储管理,4.3.1 分页存储管理的基本原理4.3.2 硬件结构4.3.3 页表结构,兰州理工大学计算机与通信学院,1两级页表 类似于对存储空间进行分页，也对页表所需的内存空间，采用离散分配方式。将页表再分成大小与页框相同的页，并从0开始进行

18、编号，这页框块称为页表页。 页表页可以离散地分配到内存的不同页框中，同时为它建立一张页表，称为外层页表或页目录。每个外层页表中的表项记录了页表页的页号。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,2多级页表 现代的计算机系统已经可以支持64位的虚拟地址，也就是说它的逻辑地址空间容量是264。如果还是采用二级页表结构，将页的大小设为4KB，逻辑地址中页内地址是12位，页表的大小是210，则最外层页表的索引将有42位。这242个页表项所组成的外层页表将会占用太大的连续存储空间，所以，二级页表结构显然不适合这些处理器。那么很自然的想法就是将外层页表继续分页，形成多级页表。,兰州理工

19、大学计算机与通信学院,3反置页表 反置页表面向的是内存的页框，即一个页表项对应一个页框，表项的顺序号就是内存的页框号，所以进程标识加上页号与内存的页框号是一一对应的，而且整个系统只有一个反置页表。 逻辑地址是由三个字段组成：进程标识（pid），进程的页号（p）和页内地址（d）。,兰州理工大学计算机与通信学院,反置页表是按物理地址的页框号排序的，在查找时是根据逻辑地址的页号查找，因此有可能要查找整个页表，这种顺序查找会花费很长时间。 可以使用哈希表（Hash Table）作为反置页表的上一级表，先将范围缩小到一个或几个表项再查找。使用哈希表也增加了一次对内存的访问，这样每次为了获取一个物理地址将

20、访问两次内存：一次是查找哈希表，另一次是查找页表。 为了提高性能，利用快表来加快查找速度，当失误时再去哈希表查找。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器,兰州理工大学计算机与通信学院,4.4 分段存储管理,4.4.1 程序分段4.4.2 分段存储管理的基本原理4.4.3 段的共享与保护4.4.4 段页式存储管理,兰州理工大学计算机与通信学院,程序分段的特点： 一般程序是由许多过程、函数和模块组成，此外还有一些数据结构，包括数组、堆栈、列表等。它们在物理

21、上被组织在一起成为段，每个段都从“0”开始编址，段内地址连续，每段都有名字，而且具有完整的逻辑意义 。 程序员使用段时，是通过段的名字调用它们，而对它们存放的物理空间并不关心，其先后顺序不会影响程序结果。因为分段时是按逻辑意义划分的，所以段与段之间的长度不同，相互间的地址也是不连续的，在段内的指令或数据，都是相对于段的起始地址而言。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,4.4 分段存储管理,4.4.1 程序分段4.4.2 分段存储管理的基本原理4.4.3 段的共享与保护4.4.4 段页式存储管理,兰州理工大学计算机与通信学院,1逻辑段与物理段 分段存储管理中，地址的分割

22、由用户进行的，用户根据程序需要来划分各个段。 进程空间按逻辑被划分为一些长度不同的区域，每个区域称为一个逻辑段。一个逻辑段对应一个进程单元，例如一个子程序、一个模块或一个数据段等. 一个进程是有若干逻辑段组成的，将这些段依次编号，称作段号。,兰州理工大学计算机与通信学院,2数据结构 需要为每个在内存中的进程建立一张表，记录该进程的逻辑段在内存中的分布情况，称为段表。 因为各个段的长度不是固定的，因此在段表中需要描述每个段的长度信息、该段的段号和起始地址。 在分段存储管理下，内存空间将分为两种类型：已用块和空闲块。这种情况与可变分区存储管理相似，因此也要使用一个空闲块表来记录内存中哪些块是空闲的

23、，哪些块是使用了的，称为空闲块表。,兰州理工大学计算机与通信学院,1500,1000,兰州理工大学计算机与通信学院,300,2000,5500,4010,1500,+,+,兰州理工大学计算机与通信学院,4.4 分段存储管理,4.4.1 程序分段4.4.2 分段存储管理的基本原理4.4.3 段的共享与保护4.4.4 段页式存储管理,兰州理工大学计算机与通信学院,1段的共享 在分段存储管理中，每一个段都是一个逻辑上独立的单元，因此更容易实现段的共享。两个进程要共享内存中的某一段程序时，只要在各自段表中的相应位置，填入该共享段的起始地址和长度即可。 2段的保护 通常是在段表中增加一个权限位。这个权限

24、位将指明该段是只读（例如共享数据段）、只执行（例如共享程序段）或可读/写。每次读取段表信息前，先比较所要执行的操作是否符合权限位要求。,兰州理工大学计算机与通信学院,1000,2700,1000,3000,兰州理工大学计算机与通信学院,4.4 分段存储管理,4.4.1 程序分段4.4.2 分段存储管理的基本原理4.4.3 段的共享与保护4.4.4 段页式存储管理,兰州理工大学计算机与通信学院,分页和分段存储管理方式都有其优、缺点。分页存储管理是基于系统存储器结构的存储管理技术，存储利用率高，可以解决外部碎片的问题，但不易实现存储共享、保护和动态扩充。分段存储管理是基于用户程序结构的存储管理技术

25、，能更好地满足程序员的要求，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护，但往往会生成段之间的碎片浪费存储空间。把两者的优点结合起来，在分页存储管理的基础上实现分段存储管理就是段页式存储管理。,兰州理工大学计算机与通信学院,基本原理,兰州理工大学计算机与通信学院,数据结构,兰州理工大学计算机与通信学院,地址转换,兰州理工大学计算机与通信学院,第4章 存储管理,4.1 概述 4.2 基本存储空间管理 4.3 分页存储管理 4.4 分段存储管理 4.5 虚拟存储器,兰州理工大学计算机与通信学院,4.5 虚拟存储器,4.5.1 虚拟存储器的基本原理4.5.2 请求分页虚拟存储管理4.5.

26、3 请求分段虚拟存储管理,兰州理工大学计算机与通信学院,虚拟存储的理论基础是程序的局部性原理，Denning于1968年提出的程序局部性原理指出“一个程序90的时间运行在10的代码上”。他经过研究发现程序和数据的访问都有聚集成群的倾向，相应地，它访问的存储空间也局限在某个区域。局部性通常表现为时间局部性和空间局部性。,1.虚拟存储的理论基础,兰州理工大学计算机与通信学院,2虚拟存储的基本思想 虚拟存储的基本思想是基于程序的局部性原理，仅把目前需要的部分程序加载到内存，其余暂时不用的程序及数据还保留在辅存中。在进程运行过程中，如果所要执行的程序不在内存，系统要将要执行的程序段自动调入内存。 此时

27、如果内存已满，则要通过置换操作将暂时不用的程序段先调出到辅存，然后将所需的程序段调入内存，继续执行该进程。,兰州理工大学计算机与通信学院,虚拟存储器的引入，实际上是利用了存储管理中逻辑地址空间和物理地址空间的关系，将计算机的内存和辅存结合起来，使得用户感觉具有大容量的内存，虚拟内存在将逻辑地址转换成物理地址时，必须通过一个内存管理单元MMU（Memory Management Unit）来完成。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,4.5 虚拟存储器,4.5.1 虚拟存储器的基本原理4.5.2 请求分页虚拟存储管理4.5.3 请求分段虚拟存储管理,兰州理工大学计算机与通

28、信学院,1基本原理 分页式虚拟存储系统将作业信息的副本存放在磁盘中，不把作业的程序和数据全部装入主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再把它们动态地装入。 问题：怎样才能发现页面不在内存中呢?怎样处理这种情况呢? 调页策略：请求式调页、预调式调页,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,2地址转换,在这个地址转换机构中，最重要的是MMU，它完成地址转换、缺页处理和页面置换的核心操作。其中页面置换主要由软件实施它的淘汰策略，而地址转换和缺页处理则要配合硬件操作。 这里要用到两个寄存器：页表基址寄存器、联想寄存器,兰州理工大学计算机与通信

29、学院,兰州理工大学计算机与通信学院,3 页的分配和置换策略,分配策略：固定分配、可变分配固定分配算法：平均分配、按进程长度分配、按进程优先级分配置换策略：全局置换、局部置换 固定分配局部置换 可变分配全局置换 可变分配局部置换,兰州理工大学计算机与通信学院,4页面置换算法, 最佳置换算法（Optimal Algorithm） 先进先出置换算法（FIFO Algorithm）(Belady反常情况) 第二次机会页面置换算法（FIFO+“引用位”） 最近最久未使用置换算法（LRU Algorithm）(访问时间计时器、计数器、引用标志位、移位寄存器) 时钟置换算法（Clock Algorithm）

30、 页面缓冲算法（Page Buffering Algorithm）,兰州理工大学计算机与通信学院,例：假设进程可用的页框数目为3个，进程的逻辑内存分成5页，编号分别从0到4，其分页的页面引用字符串为：0、1、2、3、0、1、4、0、1、2、3、4。试计算分别采用OPT、FIFO、LRU页面淘汰算法时会产生几次缺页中断？,兰州理工大学计算机与通信学院,4.5 虚拟存储器,4.5.1 虚拟存储器的基本原理4.5.2 请求分页虚拟存储管理4.5.3 请求分段虚拟存储管理,兰州理工大学计算机与通信学院,1.地址转换,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,2. 段的共享 利用分段结

31、构系统可以很容易的实现共享。这时系统需要建立一张共享段表，用来统一管理共享段的使用情况。在段表结构中除了记录共享段的段长、起始地址、存在位等信息外，还要记录共享该段的各个进程的情况。,兰州理工大学计算机与通信学院,3.段的保护 在访问某段时，系统先将指令的逻辑地址中的段号与段表长度进行比较，如果段号大于或等于段表长度，将会发出地址越界的中断信号，以保证每个进程只能在自己的地址空间内运行。 在共享段表中还有一项是“存取控制”，用于限制各段的访问方式。通常对分段有三种访问方式：只读、只执行和可读/写。,兰州理工大学计算机与通信学院,作 业习题四（P174）1、2、3、4、6、7、9、10、15、16、17、18、19,兰州理工大学计算机与通信学院,谢谢!,兰州理工大学计算机与通信学院,