操作系统2002--存储管理(1)

1、基本概念基本概念单个分区的存储管理单个分区的存储管理多个分区的存储管理多个分区的存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理虚拟存储管理虚拟存储管理一、基本概念内存储器内存储器（简称内存、主存、物理存储器）（简称内存、主存、物理存储器） 处理机能直接访问的存储器。用来存放系统处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。储方式是以新换旧，断电信息丢失。外存储器外存储器（简称外存、辅助存储器）（简称外存、辅助存储器） 处理机不能直接访问的存储器。用来存放用处理机不能直接

2、访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中，但它可用来长期保存用户信息。在文件系统中介绍。介绍。存储器分类存储器分类指导思想：利用辅存（如磁盘、磁带等）提指导思想：利用辅存（如磁盘、磁带等）提供的大容量存储空间，存放准备运行的程序供的大容量存储空间，存放准备运行的程序和数据，当需要时或主存空间允许时，随时和数据，当需要时或主存空间允许时，随时将它们读入主存储器。将它们读入主存储器。信息的二级存储信息的二级存储CPU主主 存存辅辅 存存磁磁 盘盘磁磁 带带存储器的层次结构存储器的层次结构通

3、用寄存器通用寄存器高速缓存高速缓存主存主存硬盘硬盘大容量存储器大容量存储器存储容量增大存储容量增大单位容量的价格增加单位容量的价格增加存储管理存储管理内存的物理组织内存的物理组织物理地址物理地址： 把内存分成若干个大小相把内存分成若干个大小相等的存储单元，每个单元给等的存储单元，每个单元给一个编号，这个编号称为内一个编号，这个编号称为内存地址（物理地址、绝对地存地址（物理地址、绝对地址、实地址），存储单元占址、实地址），存储单元占8位，称作字节（位，称作字节（byte）。）。物理地址空间物理地址空间： 物理地址的集合称为物理物理地址的集合称为物理地址空间（主存地址空间）地址空间（主存地址空间）

4、，它是一个一维的线性空间，它是一个一维的线性空间。程序的逻辑结构程序的逻辑结构程序地址程序地址：用户编程序时所用的地址（或称逻辑地址：用户编程序时所用的地址（或称逻辑地址 、虚地址虚地址 ），基本单位可与内存的基本单位相同，也可以），基本单位可与内存的基本单位相同，也可以不相同。不相同。程序地址空间程序地址空间（逻辑地址空间、虚地址空间）（逻辑地址空间、虚地址空间）: :用户的程用户的程序地址的集合称为逻辑地址空间，它的编址总是从序地址的集合称为逻辑地址空间，它的编址总是从0 0开始开始的，可以是一维线性空间，也可以是多维空间。的，可以是一维线性空间，也可以是多维空间。存储管理的功能存储管理的

5、功能主存空间的分配和回收主存空间的分配和回收：一个有效的存储分配机制，应在用：一个有效的存储分配机制，应在用户提出需求时提供快速响应，为之分配相应的的存储空间；户提出需求时提供快速响应，为之分配相应的的存储空间；在用户作业不再需要它时，及时回收，以供其它用户使用在用户作业不再需要它时，及时回收，以供其它用户使用地址转换地址转换：存储管理必须能够配合硬件完成用户程序中所使：存储管理必须能够配合硬件完成用户程序中所使用的逻辑地址到程序实际执行时所使用的物理地址之间的转用的逻辑地址到程序实际执行时所使用的物理地址之间的转换工作，以保证处理器的正确执行。换工作，以保证处理器的正确执行。主存空间的扩充主

6、存空间的扩充：借助虚拟存储技术或其它交换技术，达到：借助虚拟存储技术或其它交换技术，达到在逻辑上扩充主存容量，亦即为用户提供主存物理空间大得在逻辑上扩充主存容量，亦即为用户提供主存物理空间大得多的地址空间，以至使得用户感觉他的作业是在这样一个大多的地址空间，以至使得用户感觉他的作业是在这样一个大的存储器中运行。的存储器中运行。主存空间的共享和保护主存空间的共享和保护：共享主存指的是多个作业共同使用：共享主存指的是多个作业共同使用主存中的某个区域，以提高主存利用率。主存的保护指的是主存中的某个区域，以提高主存利用率。主存的保护指的是确保多道程序都能在各自分配到的主存区域内工作，互不干确保多道程序

7、都能在各自分配到的主存区域内工作，互不干扰，防止一道程序破坏其它作业的信息，特别要防止破坏系扰，防止一道程序破坏其它作业的信息，特别要防止破坏系统程序。统程序。重定位重定位绝对地址绝对地址：主存中每个物理存储单元的编号称为：主存中每个物理存储单元的编号称为“绝对地址绝对地址”或或“物理地址物理地址”，它们可以被存储控制部件所识别。，它们可以被存储控制部件所识别。逻辑地址逻辑地址：源程序经编译后得到的目标程序总是以：源程序经编译后得到的目标程序总是以0 0为起始地为起始地址，其它地址都是以此顺序安排下来，都是相对于址，其它地址都是以此顺序安排下来，都是相对于0 0这个起始这个起始地址的，这种地址

8、称为地址的，这种地址称为“逻辑地址逻辑地址”。名空间名空间：我们把再一个用高级语言编写得源程序中由程序员建：我们把再一个用高级语言编写得源程序中由程序员建立得符号名字空间称为立得符号名字空间称为“名空间名空间”。地址空间地址空间：把源程序经编译后得到的目标程序所限定的地址范：把源程序经编译后得到的目标程序所限定的地址范围称为这个程序的围称为这个程序的“地址空间地址空间”。存储空间存储空间：主存中一系列物理单元的集合称为存储空间。：主存中一系列物理单元的集合称为存储空间。显然，地址空间是逻辑地址的集合，存储空间是绝对地址或物显然，地址空间是逻辑地址的集合，存储空间是绝对地址或物理地址的集合，一个

9、是逻辑的概念，一个是物理的实体。理地址的集合，一个是逻辑的概念，一个是物理的实体。重定位重定位：一个作业的逻辑地址向物理地址的转换，：一个作业的逻辑地址向物理地址的转换，称为重定位（也称为地址映射）。称为重定位（也称为地址映射）。编程或编译时确定地址映射关系编程或编译时确定地址映射关系：编程时确定虚：编程时确定虚实地址的关系是指在用机器指令编程时，程序实地址的关系是指在用机器指令编程时，程序员直接按物理内存地址编程，这种程序在系统中员直接按物理内存地址编程，这种程序在系统中是不能做任何移动的，否则就会出错。是不能做任何移动的，否则就会出错。静态重定位静态重定位： 地址变换过程发生在程序装入时，

10、地址变换过程发生在程序装入时，且由重定位装入程序完成。采用这种重定位方式且由重定位装入程序完成。采用这种重定位方式时，系统的存储分配只能采用静态分配策略。时，系统的存储分配只能采用静态分配策略。动态重定位动态重定位：地址变换过程发生在程序执行过程：地址变换过程发生在程序执行过程中访问每条指令和数据时连续进行，且由硬件重中访问每条指令和数据时连续进行，且由硬件重定位机构来实现。采用这种重定位方式时，系统定位机构来实现。采用这种重定位方式时，系统的存储分配可以采用动态分配策略。的存储分配可以采用动态分配策略。LOAD 1, 50012345LOAD 1, 550012345010050070005

11、000510055005700静态重定位静态重定位LOAD 1, 5001234501005005007005005000LOAD 1, 5001234505000510055005700+动态重定位动态重定位在装入作业时，不进行地址转换，而是直接把作在装入作业时，不进行地址转换，而是直接把作业装入到分配的主存区域中。在作业执行过程中，业装入到分配的主存区域中。在作业执行过程中，每当执行一条指令时，都由硬件的地址转换机构每当执行一条指令时，都由硬件的地址转换机构将指令中的逻辑地址转换成物理地址，地址转换将指令中的逻辑地址转换成物理地址，地址转换工作是在作业执行时完成的。工作是在作业执行时完成的

12、。存储保护存储保护 在多道程序设计的环境下，系统中有系统在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题扰？这就是存储保护所要解决的问题常用的存储保护有两种：常用的存储保护有两种： 上、下界寄存器保护上、下界寄存器保护 基址、限长寄存器保护基址、限长寄存器保护上下界寄存器保护上下界寄存器保护下界寄存器下界寄存器 存放程序装入内存后的开始地址（首址）存放程序装入内存后的开始地址（首址）上界寄存器上界寄存器 存放程序装入

13、内存后的末地址存放程序装入内存后的末地址判别式：判别式：下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器例题：例题： 有一程序装入内存的首地址是有一程序装入内存的首地址是500500，末地址是，末地址是15001500，访问内存的逻辑地址是，访问内存的逻辑地址是500500、345345、10001000。 下界寄存器：下界寄存器：500500 上界寄存器：上界寄存器：15001500 逻辑地址装入内存的首地逻辑地址装入内存的首地 物理地址物理地址1 1、500500500 500 1000 500 1000 1000 500 1000 150015002 2、345345500

14、500 845 500 845 845 500 845 150015003 3、10001000500 500 1500 500 1500 1500 500 1500 15001500二、一个分区的存储管理二、一个分区的存储管理采用静态分配和静态重定位方式。采用静态分配和静态重定位方式。OS常住部分常住部分用户程序用户程序空闲区空闲区fence覆盖覆盖 所谓覆盖是指一个作业的若干程序段所谓覆盖是指一个作业的若干程序段（或数据段）间或几个作业的某些部分间共（或数据段）间或几个作业的某些部分间共享某主存空间。覆盖技术要求程序员提供一享某主存空间。覆盖技术要求程序员提供一个清楚的覆盖结构，即程序员要

15、把一个程序个清楚的覆盖结构，即程序员要把一个程序划分成不同的程序段，并规定好它们的执行划分成不同的程序段，并规定好它们的执行和覆盖的次序。操作系统则根据程序员提供和覆盖的次序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。的覆盖结构，完成程序段之间的覆盖。A（20k）C（30k）F（30k）程序结构程序结构B（50k）D（20k）E（40k）020k50k70k90k100kABCDEF020k20k70k70k100k20k50k50k70k50k90k程序的覆盖结构程序的覆盖结构交换交换 交换方式是由操作系统把那些在内存中处于等交换方式是由操作系统把那些在内存中处于等待状态的进

16、程换出内存，而把那些处于就绪状态的待状态的进程换出内存，而把那些处于就绪状态的进程换入内存进程换入内存操作系统操作系统用户区用户区进程进程P1进程进程P2换出换出换入换入三、多个分区的存储管理三、多个分区的存储管理固定分区固定分区 固定分区管理方式是预先把可分配的主存固定分区管理方式是预先把可分配的主存空间分割成若干个连续区域，每个区域的大小空间分割成若干个连续区域，每个区域的大小可以相同，也可以不同。一旦分好，则每个分可以相同，也可以不同。一旦分好，则每个分区的大小固定，不再变化，且分区的个数也不区的大小固定，不再变化，且分区的个数也不再改变。再改变。q 固定分区固定分区q 可变分区可变分区

17、q 可重定位分区可重定位分区作作业业1作作业业2作作业业3操作系统操作系统分区分区1分区分区2分区分区3CPU当前运行作当前运行作业所在分区业所在分区2bc上限寄存器上限寄存器下限寄存器下限寄存器abcdOS常住部分常住部分J1J2J3 032k48k16k80k144k256k32k64k112k 分分区区号号 起起始始地地址址 长长度度 状状态态 作作业业名名 1 32k 16k 1 J1 2 48k 32k 1 J2 3 80k 64k 1 J3 4 144k 112k 0 固定分区顺序分配的算法流程是是查看分区表查看分区表的第的第I个表目个表目已分配？已分配？分区长度分区长度xkI为分

18、区表最为分区表最后一个表目后一个表目置表目中置表目中状态位为状态位为1装入作业装入作业J无法分配，作业无法分配，作业J等待等待是是作业作业J申请申请xk主存主存否否是是否否I = 0I = I + 1否否地址转换：可采用静态重定位方式地址转换：可采用静态重定位方式存储保护措施：存储保护措施：CPUCPU 下界下界上界上界内存内存寻址错寻址错寻址错寻址错地址地址是是是是否否否否采用固定分区方式的问题：主存利用率不高。改采用固定分区方式的问题：主存利用率不高。改进的方法：进的方法：划分分区时按分区的大小顺序排列。划分分区时按分区的大小顺序排列。根据经常出现的作业的大小和频率划分分区。根据经常出现的

19、作业的大小和频率划分分区。按作业对主存的需求量排成多个作业。按作业对主存的需求量排成多个作业。操作系统操作系统分区分区1分区分区2分区分区3作业队列作业队列2作业队列作业队列1作业队列作业队列3L1L2L3可变分区可变分区 所谓可变分区是指，系统并不预先所谓可变分区是指，系统并不预先划分几个固定分区。分区的建立是划分几个固定分区。分区的建立是在在作作业的处理过程中进行的，其大小随作业业的处理过程中进行的，其大小随作业的主存需求量而决定。在这种管理方式的主存需求量而决定。在这种管理方式下，系统中任一时刻分区的大小及个数，下，系统中任一时刻分区的大小及个数，都是不固定而可改变的。都是不固定而可改变

20、的。可变可变分区管理的数据结构分区管理的数据结构操作系统操作系统J1J3400k01000k2000k2300k2560k始始址址 长长度度 标标志志 400 600 J1 2000 300 J3 空空 始始址址 长长度度 标标志志 1000 1000 未未分分配配 2300 260 未未分分配配 空空 已分配区表已分配区表空闲区表空闲区表分区的分配算法分区的分配算法最优适应算法最优适应算法：将空闲分区按其存储空间的大小，从小：将空闲分区按其存储空间的大小，从小到大顺序组成链。每次查找从链首开始，第一个满足要到大顺序组成链。每次查找从链首开始，第一个满足要求的空闲分区将被分配求的空闲分区将被分

21、配最坏适应算法最坏适应算法：空闲分区按其空间大小，从大到小组成：空闲分区按其空间大小，从大到小组成链。每次查找从链首开始，第一个满足要求的空闲分区链。每次查找从链首开始，第一个满足要求的空闲分区将被分配将被分配最先适应算法最先适应算法：空闲分区按其在存储空间中的地址，以：空闲分区按其在存储空间中的地址，以递增顺序组成链。每次查找从链首开始，第一个满足要递增顺序组成链。每次查找从链首开始，第一个满足要求的空闲分区将被分配求的空闲分区将被分配下次适应算法下次适应算法：是最先适应算法的一种改进。空闲分区：是最先适应算法的一种改进。空闲分区的链接顺序同最先适应算法，但它是一个循环链。每次的链接顺序同最

22、先适应算法，但它是一个循环链。每次为存储请求查找合适的空闲分区时，总是从上次查找结为存储请求查找合适的空闲分区时，总是从上次查找结束的地方开始。束的地方开始。空闲分区空闲分区1空闲分区空闲分区2free空闲分区空闲分区n按分区的大小从小到大链接按分区的大小从小到大链接空闲分区空闲分区1空闲分区空闲分区2free空闲分区空闲分区n按分区的大小从大到小链接按分区的大小从大到小链接最优适应算法最优适应算法最坏适应算法最坏适应算法空闲分区空闲分区1空闲分区空闲分区2free空闲分区空闲分区n按分区的地址从低到高链接按分区的地址从低到高链接空闲分区空闲分区1空闲分区空闲分区2free空闲分区空闲分区n按

23、分区的地址从低到高链接按分区的地址从低到高链接最先适应算法最先适应算法下次适应算法下次适应算法分区的回收分区的回收a 回收区下面回收区下面邻接空闲区邻接空闲区b 回 收 区 上回 收 区 上面面邻接空闲区邻接空闲区c 回收区上、回收区上、下邻接空闲区下邻接空闲区d 回收区不邻回收区不邻接任何空闲区接任何空闲区回收区回收区使用区使用区空闲区空闲区地址转换地址转换：一般可采用动态重定位方式，基址寄：一般可采用动态重定位方式，基址寄存器的内容加上逻辑地址（相对地址）就可得到存器的内容加上逻辑地址（相对地址）就可得到绝对地址（物理地址）。绝对地址（物理地址）。存储保护存储保护：将逻辑地址（相对地址）与

24、限长寄存：将逻辑地址（相对地址）与限长寄存器的内容进行比较，如逻辑地址（相对地址）大器的内容进行比较，如逻辑地址（相对地址）大于限长寄存器的值，表明地址越界。于限长寄存器的值，表明地址越界。 地址越界地址越界CPUCPU内存内存逻辑地址逻辑地址是是否否限长限长基址基址物理地址物理地址例题：在可变分区管理中，有那些分区分配算法？各有何优缺点？例题：在可变分区管理中，有那些分区分配算法？各有何优缺点？最优适应算法最优适应算法 空闲分区按空间大小的顺序从小到大链接在一起。系统在查找空闲分区按空间大小的顺序从小到大链接在一起。系统在查找空闲分区时，总是从最小的一个开始。其实质是，在系统中寻找与空闲分区

25、时，总是从最小的一个开始。其实质是，在系统中寻找与要求大小最接近的空闲分区。要求大小最接近的空闲分区。优点：如果存在有在正好满足所要求大小的空闲分区，则必然被选优点：如果存在有在正好满足所要求大小的空闲分区，则必然被选中，或者只对比要求稍大的空闲分区进行划分，而绝不会划分一个中，或者只对比要求稍大的空闲分区进行划分，而绝不会划分一个更大的空闲分区。更大的空闲分区。缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空闲区插入到链中合适的位置较为费时；系统中，小的空闲区较多。闲区插入到链中合适的位置较为费时；系统中，小的空闲区较多。最

26、坏适应算法最坏适应算法 空闲分区按空间大小的顺序从大到小链接在一起。系统在查找空闲分区按空间大小的顺序从大到小链接在一起。系统在查找空闲分区时，总是从最大的一个开始。空闲分区时，总是从最大的一个开始。优点：克服了最优适应算法留下许多小的碎片的不足优点：克服了最优适应算法留下许多小的碎片的不足缺点：保留大的空闲区的可能性减小了，而且分区的回收也和最优缺点：保留大的空闲区的可能性减小了，而且分区的回收也和最优适应算法一样复杂。适应算法一样复杂。最先适应算法最先适应算法 空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，即每个后继空闲

27、区的起始地址总是比前面的大。系统在查找空闲分区即每个后继空闲区的起始地址总是比前面的大。系统在查找空闲分区时，按照空闲区的链的顺序，依次查询，直到找到第一个满足要求的时，按照空闲区的链的顺序，依次查询，直到找到第一个满足要求的空闲区为止。其实质是，尽可能利用存储器的低地址部分，尽量保存空闲区为止。其实质是，尽可能利用存储器的低地址部分，尽量保存高地址部分的空闲区。高地址部分的空闲区。优点：当需要一个较大的分区时，容易得到满足。优点：当需要一个较大的分区时，容易得到满足。缺点：在回收一个分区时，需要花费较多的时间查找链表，以确定插缺点：在回收一个分区时，需要花费较多的时间查找链表，以确定插入位置

28、。入位置。下次适应算法下次适应算法 空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，与最先适应算法不同的是，每次查找都是从上次查找结束的位置开始。与最先适应算法不同的是，每次查找都是从上次查找结束的位置开始。其实质是，空闲分区可以比较均匀的分布在内存中。其实质是，空闲分区可以比较均匀的分布在内存中。缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空闲缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空闲区插入到链中合适的位置较为费时。区插入到链中合适的位置较为费时。例题：对下图所示的分区分配情况（其中，阴影部分表

29、示已占用例题：对下图所示的分区分配情况（其中，阴影部分表示已占用分区，空白部分表示空闲分区），若要申请一块分区，空白部分表示空闲分区），若要申请一块40KB40KB的分区：的分区： 100KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB 对于最优适应分配算法得到的空闲分区的首地对于最优适应分配算法得到的空闲分区的首地址是址是 ：A A、110KB B110KB B、190BK C190BK C、330BK D330BK D、410BK410BK 若要使被分配得到的空闲分区的首地址最大，若要使

30、被分配得到的空闲分区的首地址最大，则应采取的分配策略是则应采取的分配策略是 ：A A、最先适应分配算法、最先适应分配算法 B B、最优适应分配算法、最优适应分配算法C C、最坏适应分配算法、最坏适应分配算法D D、单一连续区的分配算法、单一连续区的分配算法100KB0KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB60KBFREE80KB90KB101KB最优适应分配算法得到的空闲分区的首地址最优适应分配算法得到的空闲分区的首地址为为330KB 330KB 申请一块申请一块40KB40KB的

31、分区的分区60KBFREE80KB90KB101KB330KB100KB190KB410KB80KBFREE90KB60KB101KB100KB190KB330KB410KB101KBFREE90KB80KB60KB410KB190KB100KB330KB最优适应分配算最优适应分配算法的空闲分区链。法的空闲分区链。第一个满足要求第一个满足要求的空闲分区首地的空闲分区首地址为：址为：330BK最先适应分配算最先适应分配算法的空闲分区链。法的空闲分区链。第一个满足要求第一个满足要求的空闲分区首地的空闲分区首地址为：址为：100BK最坏适应分配算最坏适应分配算法的空闲分区链。法的空闲分区链。第一个满

32、足要求第一个满足要求的空闲分区首地的空闲分区首地址为：址为：410BK 可见，只有采用最坏分配算法时，得到可见，只有采用最坏分配算法时，得到的首地址最大，为的首地址最大，为410KB410KB。答案为。答案为C C。100KB0KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB采用多重分区的管理方法能够实现主存的共享采用多重分区的管理方法能够实现主存的共享。 所谓多重分区技术指的是系统中设置了多对（一般不所谓多重分区技术指的是系统中设置了多对（一般不超过超过3 34 4对）界地址寄存器，并且在

33、为每个作业分配主存对）界地址寄存器，并且在为每个作业分配主存时，可按界地址寄存器对的个数分配多个不相邻接的空闲时，可按界地址寄存器对的个数分配多个不相邻接的空闲分区。分区。操作系统操作系统作业作业A（0分区）分区）作业作业B（0分区）分区）作业作业C作业作业A（1分区）分区）作业作业B（1分区）分区）空闲区空闲区多重分区分配多重分区分配10002000下界下界上界上界0分区寄存器对分区寄存器对50005500下界下界上界上界1分区寄存器对分区寄存器对 在共享主存空间时，每个作业即可访问自在共享主存空间时，每个作业即可访问自己所在的分区，也可访问公共区域。但应注意，己所在的分区，也可访问公共区域

34、。但应注意，对公共区域的访问是受限的。一般地说，使用对公共区域的访问是受限的。一般地说，使用共享信息（即访问公共区域）只能采用共享信息（即访问公共区域）只能采用“读读”或或“执行执行”的方式。的方式。操作系统操作系统共享程序共享程序J1J2J3可重定位分区可重定位分区 为了消除外部零头，进一步提高主存的利用为了消除外部零头，进一步提高主存的利用率，定时的（或在主存空间紧张时）把主存中的率，定时的（或在主存空间紧张时）把主存中的作业作业“搬家搬家”，集中在主存的一端，另一端就将，集中在主存的一端，另一端就将产生一个较大的空闲区。这种技术称为存储器的产生一个较大的空闲区。这种技术称为存储器的“紧缩

35、紧缩”（或称移动）。采用了紧缩技术的多个（或称移动）。采用了紧缩技术的多个分区的管理方法就是可重定位分区管理方法。分区的管理方法就是可重定位分区管理方法。采用紧缩（移动）技术时应注意的问题：采用紧缩（移动）技术时应注意的问题：1 1、移动会增加系统的开销、移动会增加系统的开销2 2、移动是有条件的、移动是有条件的操作系统操作系统J1（200k）J2（100k）400kJ3（200k）300kJ4（400k）200k操作系统操作系统J1（200k）J2（100k）J3（200k）J4（400k）900k操作系统操作系统J1（200k）J2（100k）J3（200k）J4（400k）900kA 起

36、始分配起始分配B 移动移动600kD 移动移动200k操作系统操作系统J1（200k）J2（100k）J3（200k）J4（400k）900kC 移动移动400k采用移动技术时应尽量减少移动的作业数和信采用移动技术时应尽量减少移动的作业数和信息量。息量。一种可行的方法：改变作业装入主存的方式一种可行的方法：改变作业装入主存的方式操作系统操作系统J1J2J3J4空闲区空闲区操作系统操作系统J1J3J4J2空闲区空闲区A 一头装入一头装入B 两头装入两头装入 当作业当作业J1J1完成后，它所占的分区成为空闲区，这完成后，它所占的分区成为空闲区，这样，主存中就有两个空闲区。若有新作业样，主存中就有两

37、个空闲区。若有新作业J5J5进入系统，进入系统，要求的内存容量大于任何一个空闲区，但不超过两个要求的内存容量大于任何一个空闲区，但不超过两个空闲区之和。此时需移动作业，以将两个空闲区合并空闲区之和。此时需移动作业，以将两个空闲区合并为一个较大的空闲区。为一个较大的空闲区。操作系统操作系统空闲区空闲区J2J3J4空闲区空闲区操作系统操作系统空闲区空闲区J3J4J2空闲区空闲区A 一头装入一头装入B 两头装入两头装入向上移动三个作业向上移动三个作业向上移动一个作业向上移动一个作业四、页式存储管理四、页式存储管理1 1、问题的提出、问题的提出 分区存储管理的主要问题是碎片问题。分区存储管理的主要问题

38、是碎片问题。 在采用分区存储管理的系统中，会形成一些非在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。的任何用户（程序）利用而浪费。 造成这样问题的主要原因是用户程序装入内存造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存时是整体装入的，为解决这个问题，提出了分页存储管理技术。储管理技术。2 2、基本原理、基本原理 所谓分页，就是把主存存储空间按大小一所谓分页，就是把主存存储空间按大小一定的块划分，称为物理块、或页框（定的块划分，称为物理块、或页框（

39、page page frameframe），同时，按同样的尺寸去划分作业的），同时，按同样的尺寸去划分作业的地址空间，形成一个个相等的页面，称为逻辑地址空间，形成一个个相等的页面，称为逻辑页或虚页。页或虚页。 为了便于利用硬件进行地址的转换工作，为了便于利用硬件进行地址的转换工作，页面大小通常是页面大小通常是2 2的幂次方，分页的过程对用的幂次方，分页的过程对用户是透明的。户是透明的。01234560123456作业的地址空间作业的地址空间页表页表主存中的物理块主存中的物理块分页存储管理的基本做法：分页存储管理的基本做法：（1 1）等分主存：把主存划分成相同大小的存储块，）等分主存：把主存划分

40、成相同大小的存储块，成为块（或称为页架）。对特定计算机，块的大成为块（或称为页架）。对特定计算机，块的大小通常是固定不变的。小通常是固定不变的。（2 2）用户逻辑地址的分页：把用户的逻辑地址空）用户逻辑地址的分页：把用户的逻辑地址空间（虚拟地址空间）划分成若干个与块大小相同间（虚拟地址空间）划分成若干个与块大小相同的部分（称为页），并依次编号。的部分（称为页），并依次编号。（3 3）逻辑地址表示：一般从基地址）逻辑地址表示：一般从基地址“0”0”开始编开始编址（相对地址）。每个相对地址用一对数字（址（相对地址）。每个相对地址用一对数字（p,dp,d）表示，其中表示，其中p p是页号，是页号，d

41、 d是页内位移。是页内位移。如用如用A A表示相对地址，页面大小为表示相对地址，页面大小为L L，则，则LAINTp LMODAd)(（4 4）主存分配原则：系统以块为单位把主存分）主存分配原则：系统以块为单位把主存分给作业或进程（它们不一定是相邻和连续的）。给作业或进程（它们不一定是相邻和连续的）。（5 5）页表：系统为每个进程设立一个页面映象）页表：系统为每个进程设立一个页面映象表（简称页表），使页和块建立的一一对应的关表（简称页表），使页和块建立的一一对应的关系。系。页表应包括如下信息：页表应包括如下信息： 页号页号 块号：指页面装入系统的第几号块块号：指页面装入系统的第几号块 状态：表

42、示该页是否在主存中（以状态：表示该页是否在主存中（以IBM4300IBM4300为为例：断开、连接、可寻址）例：断开、连接、可寻址）另外还可能有的其它信息：修改位（修改过否）、另外还可能有的其它信息：修改位（修改过否）、访问位（有几个进程访问）、引用位（最近被引访问位（有几个进程访问）、引用位（最近被引用过否）、外存地址等。用过否）、外存地址等。（6 6）分页系统中的地址结构：通常将地址域分成）分页系统中的地址结构：通常将地址域分成两部分，一部分表示地址所在的页号，另一部分表两部分，一部分表示地址所在的页号，另一部分表示页内地址。至于它们各占几位，则主要取决于页示页内地址。至于它们各占几位，则

43、主要取决于页的大小。的大小。（7 7）页面尺寸应是）页面尺寸应是2 2的幂：目的在于不经运算即可得到的幂：目的在于不经运算即可得到p p和和d d。页号页号p页内地址页内地址d07 819 2031例子：假定页的大小为例子：假定页的大小为1KB1KB，指令的地址域长度为，指令的地址域长度为1616位，位，则逻辑地址则逻辑地址41014101的页号、页内地址可以这样来确定：的页号、页内地址可以这样来确定：10210241KB逻辑地址逻辑地址02122224101的机内表示形式为：的机内表示形式为：0 00 10 00 115 14 13 12 11 10 9 8 7 6 5 4 3 2 1 00

44、 00 00 00 1可立即得到页号为可立即得到页号为4 4，页内地址为，页内地址为5 5计算机类型页面字节数IBM AS/400VAX 系列NS32032Intel 80386Motorola 6803051251251240964096两级和多级页表两级和多级页表：现代大多数计算机系统，都支持：现代大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就非常大的逻辑地址空间。在这样的环境下，页表就会变得非常大，本身就要占用非常大的内存空间。会变得非常大，本身就要占用非常大的内存空间。页面大小的选择页面大小的选择：页面大小一般是由机器的地址：页面大小一般是由机器的地址结构所决定的

45、，亦即由硬件决定的。页面的大小结构所决定的，亦即由硬件决定的。页面的大小通常在通常在12922之间，即在之间，即在512512字节到字节到4KB4KB之间。之间。目前常见的几种计目前常见的几种计算机中所选用的页面大小如下所示：算机中所选用的页面大小如下所示：解决的办法：解决的办法：1 1、对页表所需的内存空间，采用离散的分配办法；、对页表所需的内存空间，采用离散的分配办法；2 2、只将当前需要的部分表项调入内存。、只将当前需要的部分表项调入内存。两级页表的逻辑地址结构：两级页表的逻辑地址结构：p1P2d3122 2112 110外层页号外层页号外层页内地址外层页内地址页内地址页内地址两级页表结

46、构：两级页表结构：外部页表外部页表第第0页页表页页表第第1页页表页页表第第n页页表页页表内存空间内存空间具有两级页表的地址变换机构具有两级页表的地址变换机构p1P2d外层页号外层页号外层页内地址外层页内地址页内地址页内地址外部页表寄存器外部页表寄存器外部页表外部页表物理地址物理地址页表页表+bd对于具有更大存储容量的计算机系统，可能需要采对于具有更大存储容量的计算机系统，可能需要采用同样的原理建立更多级的页表用同样的原理建立更多级的页表3、存储空间的分配和回收、存储空间的分配和回收 对于存储空间的管理，最简单的办法是建立对于存储空间的管理，最简单的办法是建立一张一张“位示图位示图”，其中每一位

47、对应一个物理块，其中每一位对应一个物理块，用用1 1和和0 0分别表示对应的物理块已占用或空闲。另分别表示对应的物理块已占用或空闲。另外再增加一个字节记录当前系统中空闲块的总数。外再增加一个字节记录当前系统中空闲块的总数。假定主存有假定主存有256256个物理块，则可用字长为个物理块，则可用字长为3232位的位的8 8个字作为位示图：个字作为位示图：空闲块数空闲块数字长字长32位位8个字个字1为已分配为已分配0为空闲为空闲增 加 的增 加 的 1个字节个字节 在进行物理块的分配时，可按下述公式计算物理在进行物理块的分配时，可按下述公式计算物理块的块号：块的块号：块号块号 = = 字号字号 字长

48、字长 + + 位号位号 在进行物理块的回收时，假定被回收的物理块在进行物理块的回收时，假定被回收的物理块的块号为的块号为i i，则在位示图中的对应位置为：，则在位示图中的对应位置为：字号字号 = i / = i / 字长字长 位号位号 = i mod = i mod 字长字长4 4、地址转换、地址转换 将得到的逻辑地址分成两个部分：页号和将得到的逻辑地址分成两个部分：页号和 页内地址；页内地址； 根据页号查找页表，得到对应的物理块号；根据页号查找页表，得到对应的物理块号； 根据得到的物理块号和页内地址，计算出根据得到的物理块号和页内地址，计算出 实际的物理地址（绝对地址）实际的物理地址（绝对地

49、址） CPUPdf逻辑地址逻辑地址物理地址物理地址页表页表内内存存P操作系统操作系统第一步第一步第二步第二步第三步第三步fd页号页号块号块号02142638例题：例题： 在采用页式存储管理的系统中，某作业在采用页式存储管理的系统中，某作业J J的逻辑的逻辑地址空间为地址空间为4 4页（每页页（每页20482048字节），且已知该作业的字节），且已知该作业的页面映像表如下图。试借助地址变换图（即要求画页面映像表如下图。试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址出地址变换图）求出有效逻辑地址48654865所对应的物所对应的物理地址。理地址。控制寄存器控制寄存器控制寄存器页表地址页表

50、地址2769012324686769主主 存存13057页号块号021426384865 - 2，764物理地址：物理地址：6204876413057需要考虑的问题：需要考虑的问题：1 1、页表放在哪里？、页表放在哪里？ 多数的系统是在系统表格区专门开辟一个集中多数的系统是在系统表格区专门开辟一个集中的页表空间。在建立页表之前先向系统请求分配的页表空间。在建立页表之前先向系统请求分配页表空间。页表空间。2 2、对系统性能有何不利影响？、对系统性能有何不利影响？ 由于由于CPUCPU存取一次数据至少要访问两次内存存取一次数据至少要访问两次内存（间接寻址对内存的访问多于两次），因此计算（间接寻址对

51、内存的访问多于两次），因此计算机存取内存信息的时间至少比原来多了一倍。机存取内存信息的时间至少比原来多了一倍。地址变换过程为：地址变换过程为： 在在CPUCPU给出地址变换机构后，由地址变换机构自动地将页号给出地址变换机构后，由地址变换机构自动地将页号p p送入快表，并将此页号与快表中的所有页号同时进行比较。若送入快表，并将此页号与快表中的所有页号同时进行比较。若其中由与此相匹配的页号，则表明所要访问的页表项在快表中，其中由与此相匹配的页号，则表明所要访问的页表项在快表中，于是可直接读出该页所对应的物理块号，并送物理地址寄存器。于是可直接读出该页所对应的物理块号，并送物理地址寄存器。如在快表中未找到对应的页表项，还需看访问内存中页表的结如在快表中未找到对应的页表项，还需看访问内存中页表的结果，如找到，则从页表中读出物理块号送地址寄存器；同时还果，如找到，则从页表中读出物理块号送地址寄存器；同时还需将次页表项填入快表中的一个寄存器单元，即修改快表，以需将次页表项填入快表中的一个寄存器单元，即修改快表，以保存最近访问过的页表项保留在快表中。保存最近访问过的页表项保留在快表中。5 5、快表、快表 为了提高地址变换速度，可在地址变换机构中，增设一个为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查询能力的特殊高速缓冲存