操作系统习题Chapter 06-1.ppt

1、第六章 存储管理,存储管理功能 内存资源管理 存储管理方式 外存空间管理 虚拟存储系统,学习目标 明确存储管理的职能是对主存储器中的用户区域进行管理；理解在不同的管理方式下如何实现存储保护、地址转换、以及主存空间的分配和回收；比较各种管理方式的特点；掌握虚拟存储器的实现原理和方法。 学习要点 本章理解以下概念:逻辑地址,物理地址,可重定位地址,重定位,静态重定位,动态重定位,碎片,虚拟存储器等;对于每种存储管理技术应理解它解决什么问题,实现的思想是什么。本章主要介绍操作系统中有关存储管理的基本概念,几种常用的存储管理技术,分别讲述各自的基本思想,实现算法,硬件支持,并比较它们的特点.,编辑编译

2、链接装入运行,程序的装入和链接,多级存储器体系示意图,现代计算机系统多级存储器体系,第六章 存储管理,主存被划分成两部分： 系统区：用于存放操作系统的程序和数据 用户区：用于装入并存放各个用户进程的程序和数据 (各进程如何占用主存，由操作系统动态实现，存储器的管理主要是针对用户区的分配和管理) 存储管理需要完成的功能： 存储分配 存储共享 存储保护 存储扩充 地址映射,6.1 存储管理功能,存储分配 系统应具有如下功能： 记住内存每个位置的状态，即哪些是已经分配的，哪些是为分配的。 在系统程序或用户作业提出申请时，按照所需要的大小进行分配并确定分配区域 实施分配，修改分配记录表 回收系统或用户

3、释放的存储区，并修改分配记录表。,6.1 存储管理功能,存储共享 目的：节省内存、相互通讯 内容：代码、数据 存储保护 防止地址越界 防止操作越权,6.1 存储管理功能(Cont.),存储扩充 借助虚拟存储技术或自动覆盖技术来“扩充”主存容量 内存、外存结合，虚拟存储体系 速度接近内存，容量相当外存 地址映射 逻辑地址=物理地址 原因: 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换 硬件支持 基址寄存器(base)、限长寄存器(limit)、快表； 使用上述寄存器完成地址

4、映射过程； 不能正常完成地址映射时产生中断。,作业的逻辑地址空间和装入后的物理空间,当一个作业装入与其地址空间不一致的存储空间中，就得要地址变换。也就是说将逻辑地址映射为内存地址，把这种作法叫做地址重定位。 (1)静态地址重定位 在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。,地址映射,静态重定位示例： Mov Ax , 100 Xor Ax , Ax Mov 200 , Ax 如装入起始地址为10000H的内存块处，则经重定位后，程序段改为： Mov Ax , 10100 Xor Ax , Ax M

5、ov 10200 , Ax,（2）动态地址重定位： 动态地址重地位是在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。,（b）采用动态重定位时内存空间及地址重定位示意图,（a）采用静态重定位后的内存空间,静态地址重定位和动态地址重定位示意图,1、在作业的 过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在作业 过程中动态完成的。故称为动态重定位。 2、程序可随机的从主存的一个区域移动到另一个区域，程序移动后仍丝毫不影响它的执行，这种技术称为 。 3、动态重定位是在作业的_中进

6、行的。 A、编译过程 B、装入过程 C、修改过程 D、执行过程,6.2 内存资源管理,6.2.1 内存分区 分区时刻 静态分区：系统初始化时分； 动态分区：申请时分。 分区大小 等长分区：2i 异长分区：依程序、程序单位、对象大小。 通常作法 静态+等长（页式、段页式） 动态+异长（段式、界地址）,6.2.2 内存分配,静态等长分区的分配 字位映象图 空闲页面表 空闲页面链 动态异长分区的分配 最先适应 (First Fit) 最佳适应 (Best Fit) 最坏适应 (Worst Fit),字位映象图（bit map）,第0 页,第2 页,第1 页,第 k 页,第 n 页,.,.,分配：自头

7、寻找第一个为0的位，改为1，返回页号； 去配：页号对应的位(bit)置为0。,用一个bit代表一页状态，0表空闲，1表占用。（ 多单元）,空闲页面表,特点：可以分配连续页面。,占用,占用,120页,121页,122页,123页,.,.,空闲页面链,占用,占用,占用,Head:,优点：节省空间。 （不适合管理外存）,动态异长分区的分配,数据结构：,Criteria: 尽量使空闲区域连续。,初始时一个连续空闲区。 长度=0为表尾。,（1）最先适应法：按照某种次序依次检查各个空闲区，把第一个找到能容纳申请要求的内存区分配给申请者。空闲区按地址顺序从小到大登记。 （2）最佳适应算法：全部空闲区按其大小

8、递增的顺序排序，按照某一从小到大次序依次检查所有的空闲区，把能容纳申请要求的一个最接近尺寸且大于或等于作业大小的分区给申请的作业。 3）最坏适应算法 全部空闲区按其大小递减的顺序组成空闲区可用表或自由链，当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项所有空闲区长度小于申请，则失败，否则从空闲区可用表或自由链分配相应的空间给用户，然后修改和调整空闲区可用表或由由链,从该空闲区中截取所需 大小，修改调整可用表,从空闲区表第一 表目顺序查找,从可用表中移去该 表目，调整可用表,取下一表项,无法分配,该 空

9、闲区 长度SIZE？,该 空闲区 长度=SIZE？,表目查完？,返回分配起始地址,否,否,否,是,是,是,最先适应算法,最先适应算法（First Fit）,空闲区：首址递增排列； 申请：取第一个可满足区域； 优点：尽量使用低地址空间， 高区保持大空闲区域。 缺点：可能分割大空闲区。 Eg. 申请32将分割第 一个区域。,最佳适应算法（Best Fit）,空闲区：大小递增排列； 申请：取最小可满足区域； 优点：尽量使用小空闲区， 保持大空闲区。 缺点：可能形成碎片 (fragment)。 Eg. 申请30将留下长 度为2的空闲区。,最坏适应算法（Worst Fit）,空闲区：递减排列； 申请：取

10、最大可满足区域； 优点：防止形成碎片。 缺点：分割大空闲区域。,例1：在一个分区存储管理系统中，按地址从低到高排列的空闲分区的长度分别是10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于下列顺序的段请求12KB、10KB、15KB、18KB，分别采用最先适应算法、最佳适应算法和最坏适应算法，试说明空间的使用情况。,分区号,分区长度,1,2,3,4,5,6,7,8,10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB,(2)最佳适应算法空闲分区图,分区号,2,5,6,1,7,8,4,3,分区长度,20KB,18KB,15KB,12KB,10KB,9

11、KB,7KB,4KB,例2： 用可变分区方式管理主存储器时，假定主存中按地址顺序依次有5个空闲区，空闲区的大小依次为32K、10K、5K、228K和100K，现有5个作业J1、J2、J3、J4、J5，它们各需主存1K、10K、108K、28K和15K，若采用最先适应分配算法能把这5个作业按J1J5的次序全部装入主存么？你认为按怎样的次序装入这5个作业可使主存储器空间利用率最高？,6.2.3 碎片处理,紧凑：移动占用区域，使所有空闲区域连成一片（开销很大）。,OS,P1(248k),P2(250k),8k,6k,4k,256k:,512k:,768k:,264k:,518k:,256k:,504

12、k:,754k:,18k,6.3 存储管理方式,界地址管理方式（一维地址） 页式管理方式（一维地址） 段式管理方式（二维地址） 段页式管理方式（二维地址）,6.3.1 界地址管理方式,4.3.1.1 基本原理 1. 内存空间划分：动态异长； 2. 进程空间划分：一个进程一个区域，逻辑地址0l-1 3. 进程空间与内存空间对应关系（可以浮动）：,0:,l-1:,.,.,b:,l,b+l-1:,进程空间,内存空间,6.3.1 界地址管理方式,4. 所需表目： (1)内存分配表-在PCB中； (2)空闲区域表：array of (addr,size)。 5. 所需寄存器： (1)基址寄存器； (2)

13、限长寄存器。 6. 地址映射：,6.3.1 界地址管理方式,0:,l-1:,.,.,b:,l,b+l-1:,l,b,逻辑地址,CP,+,a,a+b,步骤：(1) 由程序确定逻辑地址a； (2) a与l比较判断是否越界， 不满足：0al-1，越界； (3) a与b相加得到物理地址。,进程空间,内存空间,6.3.1 界地址管理方式,6.3.1.2 双对界 代码：一对界 数据：一对界 6.3.1.3 交换技术(swapping) 交换原则：外存有可运行进程内存 (1)内存有空间，直接移入； (2)内存空间不够，移出SWAIT, SSTOP状态进程； (3)如果还不够，移出SSLEEP, SRUN状态

14、进程， 6.3.1.4 覆盖技术(overlay),离散分配方式可分为三种： 分页式存储管理 分段式存储管理 段页式存储管理,6.3.2 页式存储管理,6.3.2.1 基本思想（工作原理）,页面与页表,1.页面：把逻辑地址空间划分为一些相等的片，这些片称为页面。 2.页框：物理地址空间被划分为同样大小的片，称为物理块或页框。,页号 块号 0 3 1 5 2 6 3 2,0 1 2 3 4 5 6 7,内存,分页式存储管理中的地址结构：,页号P,页内位移量W,若给定一个逻辑地址空间中的地址位A,页面大小为L,则页号P和页内地址d，可得： P=INTA/L d=AMODL 设页面大小为1KB,A=

15、2170B,则可求得 P=2170/1024=2, d=2170%1024=122,分页存储管理的基本思想是：以块为单位把内存分给作业或进程，并且一个进程的若干个页可分别装入物理上不相邻的内存块中。即作业在内存中存放时会出现页号连续、而块号不连续的情况。 页面映象表 逻辑页 物理块 （ 页表）,页表的作用：实现从页号到物理块号的地址映射。,分页存储管理示意图,分页系统中的地址映射,通常，页表都放在内存中。当进程要访问某个逻辑地址中的数据时，分页地址映象硬件自动按页面大小将CPU得到的有效地址（相对地址）分成两部分：页号和页内地址（p，d）。以页号为索引去检索页表。从页表中得到该页的物理块号，把

16、它装入物理地址寄存器中。同时，将页内地址d直接送入物理地址寄存器的块内地址字段中。即物理地址寄存器中的内容是二者拼接成的实际访问内存的地址。,分页中的地址转换机构,CPU,p,逻辑地址,物理地址,f,d,物理地址寄存器,拼接,例题：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048个字节，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？,例题： 在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页表如下： 页号 块号 0 2 1 4 2 6 3 8 试借助地址变换图求出有效地址4865所对应的物理地址。,联想寄

17、存器,从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。 应用联想寄存器和页表相结合的方式，可有效地提高系统动态地址转换的速度，是一种行之有效的方法。,逻辑地址(p,d)物理地址(f,d) (1) 由程序确定逻辑地址(p,d)； (2) 由p查快表得页架号f； 如查不到： (a) 由p与l比较，判别是否越界： 不满足：0pl-1，越界； (b) 由p和b查页表得f, (p,f)快表，如满淘汰一个； (c) 转

18、(2); (3) f与d合并得物理地址,地址映射 : (p,d)(f,d),地址映射机制,采用快表和页表相结合的分页地址变换过程示意图,6.3.2.2 多级页表,提出背景 进程虚拟空间大幅度增加 单级页表需要很大连续内存空间 多线程设计导致进程虚拟空间不连续性 页表所占内存空间浪费 例如 32位进程地址空间，页长4k（占12位），页号20位，页表需要220个入口！ 解决策略 对页表所需的内存空间，采取离散分配方式，来解决难以找到一块连续的大内存空间的问题 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再将他们调入内存。,1. 二级页表,针对难于找到大的连续内存空间以存放页

19、表的问题，可利用将页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0#页、1#页n#页。可以离散的将各个页面分别放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为外页表(Out Page Table)。,1.Two-Level Page-Table Scheme,2.多级页表,对于64位机器，若采用二级页表结构，页面仍采取4KB即212B,假定仍按物理块的大小210位来划分页表，则将有余下的42位用于外层页号。此时在外层页表中有4096G个页表；若按220来划分页表，将有余下的32位用于外层页表，每个分页将达到1MB,外层页表仍有4G个页表项，

20、要占用16GB的连续内存空间。必须采用多级页表。,Linux的三级页表结构,6.3.2.3 反置页表(inverted page table),传统页表面向进程空间 每个进程逻辑页面有一表项 当进程空间很大时，页表很大 反置页表面向内存空间 为每个物理块设置一个页表项并将它们按物理块号排序，其中的内容则是页号及其隶属进程的标识符。 大小固定,反置页表-工作原理,程序,物理 内存,f d,pid p d,f,逻辑地址,物理地址,反置页表,分段式存储管理,.分段存储管理方式的引入 （1）方便编程 （2）信息共享 （3）信息保护 （4）动态链接 （5）动态增长,主程序,子程序A,子程序B,子程序C,

21、符号表,栈,数据,段的共享,段长 段首址, .,b l,. .,段号 si .,P1段表：,段长 段首址, .,b l,. .,段号 sj .,P2段表：,共享段,.,.,b:,l,内存空间,信息的保护,段长 段首址, . . .,l b 1 0 1,段号 s .,访问权限 R W E, . . .,段号 段长 段首址, . . .,s l b 1 0 1,访问权限 R W E, . . .,分段系统的基本原理,段式管理就是根据作业本身的内在逻辑联系，将作业划分成若干段，如把作业地址空间划分为主程序段，子程序段，数据段，工作区段，每段是一个首地址为零的连续线性地址空间，并可根据需要动态增长，每

22、段必须有一个唯一的段名，分段后，用户作业的地址空间是二维的。,分段存储管理的基本概念,1.分段：段是一组逻辑信息的集合，每个段都有自己的名字和长度。系统为段编号段号。每个段都从0开始编址并连续，段长由该段包含的逻辑信息长度决定，不等。,Main段,P段,D段,S段,0段,1段,2段,3段,分段的逻辑地址空间,main,x,y,d,对应关系,40k,60k,80k,20k,.,.,.,.,进程空间,内存空间,100k:,200k:,300k:,320k:,分段存储管理的地址变换,1程序的逻辑地址结构 2段表 3分段动态地址变换过程 4分段与分页的区别,1程序的逻辑地址结构,分段存储管理的逻辑地址

23、结构由段号s和段内位移量d组成，如下图所示。,2段表,类似于分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为：,段表：每进程一个,段首址,段长度,100k,40k,80k,60k,段号,0: 1: 2: 3:,20k,200k,320k,300k,所需寄存器,(1) 段表首址寄存器：,b,l,(2) 段表长度寄存器：,系统一个,系统一个,(3) 快表：系统一组：,段号 段首址 段长度,.,.,.,.,l,s,.,b,.,地址映射 : (s,d)(b+d) 逻辑地址(s,d)物理地址(b+d) (1

24、) 由程序确定逻辑地址(s,d); (2) 由s查快表得b和l 如查不到： (a) 由s与l比较判断是否越界 不满足：0sl-1，越界； (b)由s和b查段表，得b和l (s,b,l)快表, 如快表满淘汰一个； (c) 转(2) (3) 由d与l比较，判断是否越界 不满足：0dl-1，越界； (4) 由bd得物理地址。,段号,段长 段首址,., ., .,.,l b,s,l,b,b,l,.,.,PCB,段长 段首址,段号, .,l b,.,s,.,b+d,+,cp,s l b,物理地址,逻辑地址, .,cp,+,b:,4.分段与分页的区别,（1）页是信息的物理单位，分页是为实现离散分配方式，以

25、削减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。 而段是信息的逻辑单位，段的内容具有完整的逻辑意义，分段的目的是为了更好的满足用户的需要。 （2）页的大小固定且由操作系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统中只能有一种大小的页面； 段的长度不固定，决定于用户所写的程序，常由编译器在对原程序进行编译时，根据信息的性质来划分。 （3）分页的作业地址空间是一维线性连续的；而分段的作业地址空间是二维的，既需给出段名，又需给出段内地址。 （4）分页的活动对用户是透明的；而分段是用户可见的活动。,6.3.4 段页式存储管理(segmentation with paging),段式优于页式 便于共享和保护 页式优于段式 消除“碎片”问题 段页式：结合二者优点 每个进程包含若干段 每个段包含若干页,段页式存储管理,基本思想：用分段方法来分配和管理虚存，分页方法来分配和管理实存，在段页式管理系统中，每一段不再占有连续的实存空间，而被划分成若干个页面。,基本原理 1. 内存空间划分：(同页式) 静态等长，2i, 称为一页。 物理地址=(页架号,页内地址)=(f,d) 2. 进程空间划分： 一个进程若干个段 一个段若干个页 逻辑地址=(段号, 逻辑页号, 页内地址)=(s,p,d)