第五章存储管理.

实用操作系统教程第五章存储管理2本章内容5.1存储管理概述5.2程序的装入和链接5.3连续分配方式5.4基本分页存储管理方式5.5基本分段存储管理方式5.6基本段页式存储管理方式3本章学习目标理解程序从编译、链接到被装入执行的过程；理解逻辑地址和物理地址；几种基本的连续分配方案，理解内部碎片和外部碎片；掌握基本分页管理的地址变换过程及页表的作用；了解快表和多级页表的作用和原理；掌握基本分段管理的逻辑地址结构、段表结构、地址变换过程；理解分页和分段管理的区别和联系；掌握基本段页式管理方案的地址变换过程。45.1存储管理概述5.1.1存储器层次55.1.2存储管理任务操作系统须占用内存一部分存储空间存放自身的程序、数据、管理信息以及与硬件接口信息等，一般称这部分内存空间为系统区。系统区外的其余内存空间存放用户的程序和数据，称为用户区。存储管理主要是对用户区进行管理，它包括以下4项任务。（1）内存分配和回收（2）地址变换（3）内存保护（4）内存扩充65.1.3存储管理目标(1)内存结构细节对于用户和用户程序要透明。在高级程序设计语言和汇编语言中将源程序和目标程序进行分离，源程序独立于内存物理地址。(2)提高内存的利用率，解决大程序和小内存之间的矛盾。通过对存储空间采取不同的管理方式，解决内存管理中的碎片问题，提高内存利用率。(3)为用户程序完成程序装入。编译程序产生可执行程序时，在可执行目标程序中生成地址重定位所需信息，例如程序长度、数据区长度等。(4)解决内存速度与CPU速度不匹配问题。为了解决内存速度与CPU速度不匹配问题，引入了高速缓存。(5)实现内存保护和共享。内存保护是确保并发执行的各个进程在所分配的存储区内操作，互不干扰，通常由软硬件结合方式实现。75.2程序的装入和链接链接程序装入模块第二步第三步装入程序内存第一步库编译程序产生的目标模块…85.2.1几个基本概念1.相对地址与相对地址空间在用汇编语言或高级语言编写的程序中，数据和子程序通常用符号名进行访问。程序中各种符号名集合所限定的空间称作程序名字空间。经汇编或编译程序处理后，源程序中的各种符号名转换成由机器指令和数据组成的目标程序，用相对地址替换符号地址。目标程序中的逻辑地址集合称作该程序的相对地址空间，又称作逻辑地址空间95.2.1几个基本概念2.绝对地址与绝对地址空间程序在内存空间中的实际存储单元地址称做物理地址或绝对地址。内存空间是指物理内存中全部存储单元的集合所限定的空间。物理地址的总体构成运行用户程序的物理地址空间，又称绝对地址空间。CPU直接使用物理地址存取空间中的指令和数据，完成用户程序或系统程序。相对地址空间的大小由源程序决定，绝对地址空间的大小由系统硬件配置决定。一个程序只有从相对地址空间装入绝对地址空间后才能运行。105.2.1几个基本概念3.地址重定位当一个程序的相对地址装入到与其逻辑地址空间不一致的绝对地址空间中时，为了保证程序的正确运行，必须把指令和数据的逻辑地址转换为物理地址，这项工作称为地址重定位。地址重定位通常有静态地址重定位和动态地址重定位两种方式。①静态地址重定位②动态地址重定位115.2.2程序的装入程序的装入指给程序的指令和数据分配物理内存空间，也常被称为加载。一个程序要运行必须得装入内存，这需要将指令和数据的逻辑地址转换为物理地址，即需要进行地址变换。根据地址变换发生时机，装入方式分为绝对装入方式、可重定位装入方式和动态运行时装入方式三种。125.2.2程序的装入1、绝对装入方式在可执行文件中记录内存地址，装入时直接定位在上述(即文件中记录的地址)内存地址。优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。135.2.2程序的装入2、可重定位装入方式当一个地址装入与其地址空间不一致的存储空间中，就得要进行地址变换。也就是说将虚地址映射为内存地址，把这种作法叫做地址重定位或地址映射。在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。又称静态重定位装入方式。145.2.2程序的装入2、可重定位装入方式优点：不需硬件支持，可以装入有限多道程序（如MSDOS中的TSR）。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。155.2.2程序的装入3、动态运行时装入方式可重定位装入方式虽然可用于多道程序系统，但程序执行期间如果在内存中发生移动，则程序的物理地址都发生改变，须修改全部物理地址，否则程序将无法正确执行。所以，采用可重定位方式把程序装入内存后，程序在内存中一般不再移动。动态运行时装入方式的优点是操作系统可将一个程序离散地存放在内存空间。在程序的整个执行期间，允许程序在内存中改变位置。这种加载方式有利于提高内存利用率，也为实现虚拟存储器提供了基础。动态运行时装入方式的缺点是需要硬件支持，操作系统实现较为复杂。16动态地址重定位示意图150012345LoadA500内存空间5001000+VRBR50010012345LoadA5000虚拟空间（作业地址空间）…..3．动态运行时装入方式17重点回顾死锁避免：银行家算法死锁的检测与解除相对地址与相对地址空间绝对地址与绝对地址空间地址重定位18重点回顾程序的装入绝对装入方式可重定位装入方式动态运行时装入方式195.2.3程序的链接根据链接时间的不同，可把链接分成如下三种：(1)静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。(2)装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。(3)运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。201．静态链接方式(StaticLinking)(1)对相对地址进行修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。(2)变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如图4-4(b)所示。这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。215.2.3程序的链接222．装入时动态链接(Load-timeDynamicLinking)用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。233．运行时动态链接(Run-timeDynamicLinking)在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块都全部装入内存，并在装入时全部链接在一起。显然这是低效的。运行时动态链接方式，是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。245.3连续分配方式连续分配方式是指为用户进程分配连续内存空间的内存管理方式。早期操作系统都是采用连续分配方式管理内存。连续分配方式通常分为：单一连续分配、固定分区分配、可变分区分配、动态可重定位分区分配等255.3.1单一连续分配单一连续分配方式是最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。在此方式中，把内存分为系统区和用户区两部分。系统区仅提供给操作系统使用；用户区是指除系统区之外的全部内存空间，提供给用户作业使用，一次只允许一个作业进入内存。作业往往只占用户区的一部分，其余部分空闲，内存利用率较低。单一连续分配存储管理方式只适用于程序的绝对装入。265.3.2固定分区分配1.划分分区的方法①分区大小相等，即所有内存分区大小相等。其缺点是当分区太大时，会造成内存空间浪费；当分区太小时，会造成大作业无法运行。它主要适用于一台计算机控制多个相同对象的场合。②分区大小不等，即所有内存分区大小不等。可以把内存划分成多个较小分区、适量中等分区及少量大分区，以适应不同程序的需求275.3.2固定分区分配2.内存的分配与回收为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见下图a所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如下图b所示。2820K28K60K124K256K5.3.2固定分区分配OS进程A（6K）进程B（25K）进程C（36K）（a）分区说明表（b）内存状态区号分区长度起始地址状态18K20K已分配232K28K已分配364K60K已分配4132K124K未分配图固定分区使用表295.3.2固定分区分配当用户程序要装入执行时,通过请求表提出内存分配要求和所要求的内存空间大小。从分区说明表中查询，从中找出一个大小满足要求的空闲分区，并将其分配给申请者。固定分区的回收，只需将对应的分区状态置为未使用即可。30要求Xk大小分区取分区说明表第一项状态位置正在使用取下一表项无法分配该分区空闲？分区长度≥Xk?表结束？返回分区号否否否是是是图5.10固定分区分配算法315.3.2固定分区分配3.地址变换固定分区存储的地址变换即可采用静态重定位，也可采用动态重定位。325.3.2固定分区分配优点：实现简单、开销小缺点：必须预先能够估计作业要占用的空间，分区总数固定，限制了并发作业的的数目；内碎片（占用分区之内未被利用的空间）造成浪费335.3.3可变分区分配1.可变分区的原理固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。动态分区原则：存储空间的划分是在作业装入时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。动态分区，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。345.3.3可变分区分配进程A（8K）进程D（124K）进程B（16K）进程C（64K）…OS进程A(8K)进程B(16K)进程C(64K)进程D(124K)OS进程A(8K)进程B(16K)进程C(64K)OS进程A(8K)进程B(16K)OS进程A(8K)35内存分配变化过程OSA（8K）8K空闲区B（16K）E（50K）D（124K）14K空闲区F（16K）OSA（8K）8K空闲区空闲区16KE（50K）F（16K）空闲合并124+14=138K进程E（50K）进程F（16K）进入内存进程B（16K）进程D（124K）完成OSA（8K）24K空闲区B（16K）C完成（64K）空闲区D（124K）365.3.3可变分区分配2.可变分区分配的数据结构①空闲分区表。系统设置一张空闲分区表，记录内存中每个空闲分区的序号、大小和起始地址，每个空闲分区在空闲分区表中占一个表目。375.3.3可变分区分配2.可变分区分配的数据结构②空闲分区链。为了实现对空闲分区的分配和链接，在每个空闲分区的起始单元中存储两个值，一个是空闲分区的大小，另一个是指向下一空闲分区的指针。385.3.3可变分区分配3.常用的空闲分区分配算法有以下四种：①首次适应（firstfit）算法②循环首次适应（nextfit）算法③最佳适应（bestfit）算法④