课件操作系统存储管理.ppt

1、第四章 存 储 器 管 理 第四章第四章 存储器管理存储器管理 第四章 存 储 器 管 理 本章主要内容本章主要内容 程序的装入和链接程序的装入和链接 连续分配方式连续分配方式 基本分页存储管理方式基本分页存储管理方式 基本分段存储管理方式基本分段存储管理方式 虚拟存储器的基本概念虚拟存储器的基本概念 请求分页存储管理方式请求分页存储管理方式 页面置换算法页面置换算法 请求分段存储管理方式请求分段存储管理方式 第四章 存 储 器 管 理 存储器概述及相关概念1 存储体系 存储器的层次结构：Cache主存主存磁盘磁盘第四章 存 储 器 管 理 高速缓存Cache：少量的、非常快速、昂贵、易变的内

2、存RAM：若干兆字节、中等速度、中等价格、易变的 磁盘：数百兆或数千兆字节、低速、价廉、不易变的 第四章 存 储 器 管 理 由操作系统协调这些存储器的使用 重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥第四章 存 储 器 管 理 内存：是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器 内存可以分为：内存可以分为：系统区：用于存放操作系统系统区：用于存放操作系统 用户区：用于装入并

3、存放用户程序和数用户区：用于装入并存放用户程序和数据据 第四章 存 储 器 管 理 2 地址映射（地址重定位，地址变换）(1)逻辑地址（相对地址，虚地址）(2)物理地址（绝对地址，实地址）(3)地址映射第四章 存 储 器 管 理 地址映射地址映射Load A 200 3456 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000第四章 存 储 器 管 理(1)逻辑地址（相对地址，虚地址）用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其

4、首地址为0，其余指令中的地址都相对于首地址而编址 不能用逻辑地址在内存中读取信息第四章 存 储 器 管 理(2)物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址(3)地址映射地址映射 为了保证为了保证CPU执行指令时可正确执行指令时可正确访问存储单元，需将用户程序中的访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地寻址的物理地址，这一过程称为地址映射址映射第四章 存 储 器 管 理 12003456.LOAD A 200.0100200300.LOAD A 2003456逻辑地址空间逻辑地址空间13001400

5、1500物理地址空间物理地址空间200偏移偏移+1000基址基址第四章 存 储 器 管 理 原因:当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换第四章 存 储 器 管 理 3、存储扩充、存储扩充第四章 存 储 器 管 理 4、存储保护、存储保护第四章 存 储 器 管 理 第四章 存 储 器 管 理 4.1 程序的装入和链接程序的装入和链接 图图 4-1 对用户程序的处理步骤对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存第四章 存 储

6、 器 管 理 4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(Absolute Loading Mode)程序中所使用的绝对地址，既可在编译或汇编时给出，程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。也可由程序员直接赋予。但在由程序员直接给出绝对地址但在由程序员直接给出绝对地址时，时，不仅要求程序员熟悉内存的使用情况，而且一旦程序不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，通常是宁可在程序中采用符号地址，

7、然后在编译或汇编时，再将这些符号地址转换为绝对地址。再将这些符号地址转换为绝对地址。第四章 存 储 器 管 理 2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)图图 4-2 作业装入内存时的情况作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间第四章 存 储 器 管 理 3.动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)动态运行时的装入程序，在把装入模块装入内存后，动态运行时的装入程序，在把装入模块装入

8、内存后，并不立即把装入模块中的相对地址转换为绝对地址，而并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因是把这种地址转换推迟到程序真正要执行时才进行。因此，此，装入内存后的所有地址都仍是相对地址。装入内存后的所有地址都仍是相对地址。第四章 存 储 器 管 理 4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)图图 4-3 程序链接示意图程序链接示意图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模

9、块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a)目标模块(b)装入模块第四章 存 储 器 管 理 在将这几个目标模块装配成一个装入模块时，须解在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：决以下两个问题：(1)对相对地址进行修改。对相对地址进行修改。(2)变换外部调用符号。变换外部调用符号。第四章 存 储 器 管 理 2.装入时动态链接装入时动态链接(Loadtime Dynamic Linking)装入时动态链接方式有以下优点：装入时动态链接方式有以下优点：(1)便于修改和更新。便于修改和更新。(2)便于实现对目标模块的共享。便于实现对目标模块

10、的共享。第四章 存 储 器 管 理 3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)近几年流行起来的运行时动态链接方式，是对上述在近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由发现一个被调用模块尚未装入内存时，立即由OS去找到该去找到该模块并将之装入内存，模块并将之装入内存，把它链接到调用者模块上。凡在执把它链接到调用者模

11、块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。可节省大量的内存空间。第四章 存 储 器 管 理 4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给存分为系

12、统区和用户区两部分，系统区仅提供给OS使用，使用，通常是放在内存的低址部分；用户区是指除系统区以外的通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，全部内存空间，提供给用户使用。提供给用户使用。第四章 存 储 器 管 理 用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0第四章 存 储 器 管 理 4.2.2 固定分区分配固定分区分配 1.划分分区的方法划分分区的方法(1)分区大小相等，分区大小相等，即使所有的

13、内存分区大小相等。即使所有的内存分区大小相等。(2)分区大小不等。分区大小不等。每个分区装一个且只能装一个作业每个分区装一个且只能装一个作业第四章 存 储 器 管 理 2.内存分配内存分配 图图 4-4 固定分区使用表固定分区使用表 第四章 存 储 器 管 理 固定分区的管理设置内存分配表内存分配：单一直接内存回收：简单缺点：内存利用率不高分区号分区号 起始地址起始地址长度长度状态状态进程名进程名第四章 存 储 器 管 理 基本思想 内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间4.

14、2.3 动态分区分配动态分区分配第四章 存 储 器 管 理 1.分区分配中的数据结构分区分配中的数据结构(1)空闲分区表。空闲分区表。记录了空闲区起始地址和长度(2)空闲分区链。空闲分区链。图图 4-5 空闲链结构空闲链结构 前向指针N20N个字节可用后向指针N20第四章 存 储 器 管 理 2.分区分配算法分区分配算法(1)首次适应算法首次适应算法FF。(2)循环首次适应算法，该算法是由首次适应算法演变而成的。循环首次适应算法，该算法是由首次适应算法演变而成的。(3)最佳适应算法。最佳适应算法。第四章 存 储 器 管 理 首先适配算法：当接到内存申请时，从头开始查空闲块表，找到第一个不小于请

15、求的空块，将其分割并分配（特点：简单、快速分配）演变：循环首次适应算法。分配时不在从头开始扫描，而是从上一次分配的位置开始向后扫描，循环往复。第四章 存 储 器 管 理 最佳适配算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配（特点：用最小空间满足要求）第四章 存 储 器 管 理 最坏适配算法：接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配（特点：当分割后空闲块仍为较大空块）第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空

16、空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98Kn空闲区按从小到大排列时空闲区按从小到大排列时,最先最先适用分配算法适用分配算法能尽可能使用低地址区能尽可能使用低地址区,从而高地址空间有较从而高地址空间有较大的空闲区容纳大的作业。大的空闲区容纳大的作业。n最优最优

17、适应分配算法的主存利用率最好适应分配算法的主存利用率最好,但可能但可能会导致空闲区分割下来的部分很小。会导致空闲区分割下来的部分很小。n最坏最坏适应分配算法：它选择最大空闲区适应分配算法：它选择最大空闲区,使得使得分配后剩余下来的空闲区不会太小分配后剩余下来的空闲区不会太小,仍能用于仍能用于再分配。再分配。分配算法比较分配算法比较n搜索空闲区速度及主存利用率搜索空闲区速度及主存利用率：最先适最先适应分配、最佳适应算法比最坏适应算法性应分配、最佳适应算法比最坏适应算法性能好。能好。n如果空闲区按从小到大排列如果空闲区按从小到大排列,则则最先最先适用适用分配算法分配算法等于等于最优最优适应分配算法

18、。适应分配算法。n如果空闲区按从大到小排列如果空闲区按从大到小排列,则则最先最先适用适用分配算法分配算法等于等于最坏最坏适应分配算法。适应分配算法。n最先适应算法简单、快速，在实际的操作系统中用得较多；n其次是最佳适应算法。回收算法(1)(1)其邻近都有进程（其邻近都有进程（A A和和B B）上下不相邻）上下不相邻(2)(2)一边有进程（一边有进程（A A或或B B）上邻、下邻）上邻、下邻(3)(3)两边均为空闲区上下相邻两边均为空闲区上下相邻 A X B A B A X A X B B x 变为变为变为变为X终止前X终止后第四章 存 储 器 管 理 3.分区分配操作分区分配操作 1)分配内存

19、分配内存 从头开始查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图图 4-6 内存分配流程内存分配流程第四章 存 储 器 管 理 碎片问题：经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片 造成存储资源的浪费4.2.4 可重定位分区分配可重定位分区分配 第四章 存 储 器 管 理 碎片问题的解决：紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空

20、闲区域 （紧缩技术，紧致技术，浮动技术，搬家技术）问题：开销大；移动时机第四章 存 储 器 管 理 动态重定位的引入 由于有大量的内存空间碎片，如果要将他们进行合并操作，以使新作业得以装入内存执行，那么原来装入的作业就要被移动，而不再停留在原来的位置了。即每次移动后，需要对移动了的程序或数据进行重定位。第四章 存 储 器 管 理 图图 4-8 紧凑的示意紧凑的示意 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a)紧凑前(b)紧凑后第四章 存 储 器 管 理 2.动态重定位的实现动态重定位的实

21、现 图图 4-9 动态重定位示意图动态重定位示意图 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存增加一个重定位寄存器，用来存放程序的起始地址。第四章 存 储 器 管 理 3.动态重定位分区分配算法动态重定位分区分配算法 图图 4-10 动态分区分配算法流程图动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空

22、闲区修改有关的数据结构否是无法分配返回否第四章 存 储 器 管 理 4.2.5 交换技术(swapping)当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。第四章 存 储 器 管 理 交换技术实现中的几个问题：1、选择原则 即：将哪个进程换出/换入内存？例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的第四章 存 储 器 管 理 (1)进程的换出。进程的换出。每当一进程由于创建子进程而需要更多的内存空间，每当一进程由于创建子进程而需要更多的内存空间，

23、但又无足够的内存空间等情况发生时，系统应将某进程换但又无足够的内存空间等情况发生时，系统应将某进程换出。出。其过程是：系统首先选择处于阻塞状态且优先级最低其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。块做相应的修改。第四章 存 储 器 管 理 (2)进程的换入。进程的换入。系统应定时

24、地查看所有进程的状态，从中找出系统应定时地查看所有进程的状态，从中找出“就绪就绪”状态但已换出的进程，将其中换出时间状态但已换出的进程，将其中换出时间(换出到磁盘上换出到磁盘上)最最久的进程作为换入进程，将之换入，直至已无可换入的进久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。程或无可换出的进程为止。第四章 存 储 器 管 理 2、交换时机的确定 何时需发生交换？例子：只要不用就换出（很少再用）只在内存空间不够或有不够的危险时换出第四章 存 储 器 管 理 3、交换时需要做哪些工作？需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映

25、像的直接存取4、换入回内存时位置的确定 换出后再换入的内存位置一定要在换出前的原来位置上吗？受地址“绑定”技术的影响，即绝对地址产生时机的限制.第四章 存 储 器 管 理 2.对换空间的管理对换空间的管理 采用连续空间的分配方式采用连续空间的分配方式，以提高进程换入，以提高进程换入/换出的速换出的速度。度。为了能对对换区中的空闲盘块进行管理，在系统中应配为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。置相应的数据结构，以记录外存的使用情况。用空闲分区表或空闲分区链。用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，在空闲分区表中的每个表目中应包含两项，即对换区的即对换区的首址及其大小，它们的单位是盘块号和盘块数。首址及其大小，它们的单位是盘块号和盘块数。