江苏师范大学操作系统ppt第4章-1

1、第1/96页 4.1 内存管理功能内存管理功能 4.2 分区管理分区管理 4.3 页式管理页式管理 4.4 段式管理段式管理 4.5 段页式管理段页式管理第2/96页内存空间的分配、回收内存空间的分配、回收地址重定位地址重定位内存空间的共享与保护内存空间的共享与保护内存空间的逻辑扩充内存空间的逻辑扩充 第3/96页 内存分配按分配时机的不同，可分为两种方式：内存分配按分配时机的不同，可分为两种方式： 静态分配静态分配 指内存分配是在作业运行之前各目标模块连接后，把整个指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业一次性全部装入内存

2、，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。配是在作业运行前一次性完成的。 动态分配动态分配 作业要求的基本内存空间是在目标模块装入内存时分配的，作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。第4/96页内存的物理地址内存的物理地址

3、把内存分成若干个大小相等把内存分成若干个大小相等的存储单元，每个单元给一个的存储单元，每个单元给一个编号，这个编号称为编号，这个编号称为内存地址内存地址（物理地址、绝对地址、实地（物理地址、绝对地址、实地址址），存储单元占），存储单元占8位，称作位，称作字节（字节（byte）。）。物理地址空间物理地址空间 物理地址的集合称为物理地址物理地址的集合称为物理地址空间（主存地址空间），它是空间（主存地址空间），它是一个一维的线性空间。一个一维的线性空间。第5/96页逻辑地址逻辑地址 目标程序所用的地址（或称程序地址目标程序所用的地址（或称程序地址 、虚地址、相对地址、虚地址、相对地址 ），），基本单

4、位可与内存的基本单位相同，也可以不相同。它的编址基本单位可与内存的基本单位相同，也可以不相同。它的编址总是从总是从0开始的。开始的。逻辑地址空间（程序地址空间、虚地址空间）逻辑地址空间（程序地址空间、虚地址空间） 由逻辑地址组成的集合称为逻辑地址空间。由逻辑地址组成的集合称为逻辑地址空间。源源 程程 序序编译编译目标模块目标模块库库.链接链接程序程序装入模块装入模块装入装入程序程序内存内存第6/96页 将逻辑地址空间中使用的逻辑地址变换成主存中的将逻辑地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址的过程称为地址映射或地址变换地址映射或地址变换，有时也称为，有时也称为地址重定位地址重定

5、位 。地址映射地址映射Load A 200 3456 1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000第7/96页静态重定位静态重定位 在程序装入内存时，把程序中的逻辑地址全部转换为绝对地址。在程序装入内存时，把程序中的逻辑地址全部转换为绝对地址。地址转换工作是在程序执行前集中一次完成的）在程序执行过程中地址转换工作是在程序执行前集中一次完成的）在程序执行过程中就无须再进行地址转换工作。就无须再进行地址转换工作。映射方法映射方法v假定程序装入内存的首地址为假

6、定程序装入内存的首地址为BRBR，则地址映射按下式进行：，则地址映射按下式进行：物物理地址理地址=BR+=BR+逻辑地址逻辑地址 。v例如，程序装入内存的首地址为例如，程序装入内存的首地址为100100，则装入程序就按，则装入程序就按MR=100+VRMR=100+VR对程序中所有地址部分进行修改对程序中所有地址部分进行修改优点优点 实现简单，不要硬件的支持。实现简单，不要硬件的支持。缺点缺点 程序一旦装入内存，就不能移动；程序一旦装入内存，就不能移动； 程序必须占用连续的内存空间。程序必须占用连续的内存空间。0204060Load 1, 402340100140160120Load 1, 1

7、40234重定位装入程序重定位装入程序逻辑地址空间逻辑地址空间内存空间内存空间第8/96页 动态重地位动态重地位是在程序执行过程中，在是在程序执行过程中，在CPUCPU访问内访问内存之前存之前, ,将要访问的程序或数据地址转换成内存地址。将要访问的程序或数据地址转换成内存地址。 动态重定位依靠硬件地址变换机构完成。动态重定位依靠硬件地址变换机构完成。 Load 1,500Load 1,500Load 1,500Load 1,500物理地址物理地址= =逻辑地址逻辑地址+ +基址基址优点优点程序占用的内存空间是动态可变的，当程序从某个存储区移到另程序占用的内存空间是动态可变的，当程序从某个存储区

8、移到另 一个区域时，只需要修改相应的重定位寄存器一个区域时，只需要修改相应的重定位寄存器BRBR的内容即可。的内容即可。缺点缺点 需要硬件的支持；实现存储管理的软件算法较为复杂需要硬件的支持；实现存储管理的软件算法较为复杂第9/96页内存共享内存共享 指两个或多个进程共用内存中相同的区域，即它们的内指两个或多个进程共用内存中相同的区域，即它们的内存空间有重叠的部分，这样被共享的程序和数据，只需在内存空间有重叠的部分，这样被共享的程序和数据，只需在内存中保留一个副本。存中保留一个副本。 程序共享程序共享 为了节省内存空间，提高内存利用率。为了节省内存空间，提高内存利用率。 数据共享数据共享 为了

9、实现进程间的通信。为了实现进程间的通信。 第10/96页上、下界存储保护上、下界存储保护 系统可为每个进程设置一对上、下界寄存器，分别用来存系统可为每个进程设置一对上、下界寄存器，分别用来存放当前运行进程在内存空间的上、下边界地址，用它们来限放当前运行进程在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。制用户程序的活动范围。 进程进程第11/96页 基址限长存储保护基址限长存储保护 上、下界保护的一个变种是采用基址上、下界保护的一个变种是采用基址限长存储保护。限长存储保护。 进程进程第12/96页物理存储器的结构是个一维的线性空间，容量是物理存储器的结构是个一维的线性空间，容量是有

10、限的。有限的。物理存储器管理方式的特征：物理存储器管理方式的特征： 一次性一次性：程序要全部一次性装入内存后才能运行程序要全部一次性装入内存后才能运行 驻留性驻留性：程序装入内存后，一直驻留在内存中，程序装入内存后，一直驻留在内存中，直至作业运行结速。直至作业运行结速。用户程序的大小，可能比内存容量小，也可能比用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。内存容量大，有时候要大得多。如何将大于物理内存容量的用户程序装入运行？如何将大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。

11、存储技术发展的原动力。第13/96页 指程序在执行过程中的一个较短时间内，所执行指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空间局部性。域中。又可细分时间局部性和空间局部性。时间局部性时间局部性 一条指令被执行了，则在不久的将来它可能再被一条指令被执行了，则在不久的将来它可能再被执行。执行。空间局部性空间局部性 若某一存储单元被使用，则在一定时间内，与该若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。存储单元相邻的单元可能被使用。第14/96页虚拟存储器虚拟存

12、储器 是采用是采用请求调入功能和置换功能请求调入功能和置换功能，把内存与外存把内存与外存有机的结合起来使用，从逻辑上有机的结合起来使用，从逻辑上为用户提供一个比为用户提供一个比物理主存容量大得多的，可寻址的一种物理主存容量大得多的，可寻址的一种“主存储主存储器器” ” ，这就是虚存。，这就是虚存。虚拟存储器的容量虚拟存储器的容量 是有限的；是有限的； 由内存容量和外存容量之和所决定，受计算机的由内存容量和外存容量之和所决定，受计算机的地址结构限制。地址结构限制。 以以CPU时间和外存空间换取昂贵内存空间，这时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术是操作系统中的资源转换技术。

13、第15/96页常规存储器的特征常规存储器的特征v一次性一次性v驻留性驻留性虚拟存储器特征虚拟存储器特征v多次性多次性v对换性对换性v虚拟性虚拟性第16/96页实现虚拟存储器必须解决好以下有关问题实现虚拟存储器必须解决好以下有关问题v主存辅存统一管理问题主存辅存统一管理问题v逻辑地址到物理地址的转换问题逻辑地址到物理地址的转换问题v部分装入和部分对换问题部分装入和部分对换问题虚拟存储管理主要采用以下技术实现虚拟存储管理主要采用以下技术实现v页式虚存管理页式虚存管理v段式虚存管理段式虚存管理v段页式虚存管理段页式虚存管理第17/96页 连续分配方式连续分配方式 a. 单一连续分配方式单一连续分配方

14、式(单分区管理单分区管理)； b. 分区管理方式：又分固定分区方式和可变分区方式。分区管理方式：又分固定分区方式和可变分区方式。 离散分配方式离散分配方式 a. 分页存储管理方式；分页存储管理方式； b. 分段存储管理方式；分段存储管理方式； c. 段页式存储管理方式。段页式存储管理方式。 虚拟存储管理方式虚拟存储管理方式 a. 请求分页管理方式请求分页管理方式 ； b. 请求分段管理方式；请求分段管理方式； c. 请求段页式管理方式。请求段页式管理方式。第18/96页4.2.1 单分区管理单分区管理4.2.2 固定分区固定分区4.2.3 可变分区可变分区4.2.4 碎片问题碎片问题4.2.5

15、 覆盖与交换覆盖与交换 第19/96页 单用户单任务系统在一段时间内，只有一个进程在内单用户单任务系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用。为两个区域，一个供操作系统使用，一个供用户使用。v静态重定位静态重定位 v界限寄存器界限寄存器v重定位和存储保护重定位和存储保护操作系统区操作系统区作业作业i i的的程序、程序、数据等数据等界限地址界限地址界限寄存器界限寄存器作业作业2 2作业作业1 1界限地址界限地址 + + 逻辑地址逻辑地址装入程序装入程序第20/96

16、页 基本思想基本思想 预先把可分配的主存储器空间分割成若干个固预先把可分配的主存储器空间分割成若干个固定大小的连续存储区（存储块），称为一个定大小的连续存储区（存储块），称为一个分区分区。每个分区的大小可以相同也可以不同。但分区大小每个分区的大小可以相同也可以不同。但分区大小固定不变，每个分区装一个且只能装一个作业。固定不变，每个分区装一个且只能装一个作业。 在系统运行期间，分区大小、数目都不变，所以在系统运行期间，分区大小、数目都不变，所以固定分区也称为固定分区也称为静态分区静态分区。第21/96页OSOS区（区（20KB20KB）分区分区1 1（50KB50KB）分区分区2 2 （50KB

17、50KB）分区分区3 3 （50KB50KB）分区分区4 4 （50KB50KB）分区大小相等分区大小相等OSOS区（区（20KB20KB）分区分区1 1（10KB10KB）分区分区2 2 （30KB30KB）分区分区3 3 （50KB50KB）分区分区4 4 （110KB110KB）分区大小不相等分区大小不相等根据分区大小是否相等根据分区大小是否相等, ,可采用两种方法划分分区可采用两种方法划分分区第22/96页124K256KOS20K28K60K 进程进程A（6K）进程进程B（25K）进程进程C（7K） 内存的分配与回收，需要借助于内存的分配与回收，需要借助于内存分配表内存分配表数据数据

18、结构来实现，该数据结构用于记录各分区的分配和使结构来实现，该数据结构用于记录各分区的分配和使用情况。用情况。内存分配表内存分配表区号区号分区长度分区长度起始地址起始地址状态状态1 18K8K20K20K空闲空闲2 232K32K28K28K空闲空闲3 364K64K60K60K空闲空闲4 4132K132K124K124K空闲空闲区号区号分区长度分区长度起始地址起始地址状态状态1 18K8K20K20K已分配已分配2 232K32K28K28K空闲空闲3 364K64K60K60K空闲空闲4 4132K132K124K124K空闲空闲区号区号分区长度分区长度起始地址起始地址状态状态1 18K8

19、K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K空闲空闲4 4132K132K124K124K空闲空闲区号区号分区长度分区长度起始地址起始地址状态状态1 18K8K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K已分配已分配4 4132K132K124K124K空闲空闲第23/96页优点优点 能使多个程序并发执行能使多个程序并发执行 改善了单分区管理中内存利用率低的问题改善了单分区管理中内存利用率低的问题缺点缺点 不能充分利用内存空间，会形成内碎片不能充分利用内存空间，会形成内碎片 限制了并发执行

20、的进程数目限制了并发执行的进程数目 限制了装入程序的大小限制了装入程序的大小第24/96页 基本思想基本思想 内存不是预先划分好的，而是当作业装入时，根据作内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按足够的空间，则按需要分割需要分割一部分分区给该进程；否则一部分分区给该进程；否则令其等待主存空间。令其等待主存空间。OS进程进程A进程进程 A（8K）进程进程 C（64K）OS进程进程A进程进程B进程进程C进程进程 D（124K）OS进程进程A进程进程B进程进程C进程进程D进程进程 B

21、（16K）OS进程进程A进程进程B第25/96页OSA（8K）24K空闲区空闲区B（16K）C (64K）D（124K）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）完成完成C完成（完成（64K）空闲区空闲区内存分配变化过程内存分配变化过程:第26/96页空闲分区表空闲分区表空闲分区链空闲分区链5 735 73若须分配若须分配25K25K

22、第27/96页首次适应算法首次适应算法循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法最坏适应算法最坏适应算法第28/96页 基本思想：基本思想：空闲区按地址大小递增顺序排列，在分配时，空闲区按地址大小递增顺序排列，在分配时，从头开始顺序查找到第一个大小能满足要求的空闲区。从头开始顺序查找到第一个大小能满足要求的空闲区。 特点：特点：简单简单第29/96页优点优点v尽可能地利用低地址空间，从而保证高地址空间尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。有较大的空闲区。缺点缺点v低地址部分不断划分，形成很多难以利用的小块低地址部分不断划分，形成很多难以利用的小块v每次从头开始

23、找，增加了查找的时间每次从头开始找，增加了查找的时间第30/96页基本思想基本思想 每次分配时每次分配时,从上一次找到的空闲分区的下一个开始查从上一次找到的空闲分区的下一个开始查找找,找到第一个大小满足要求的空闲分区为止找到第一个大小满足要求的空闲分区为止.优点优点 小的空闲分区均匀分布小的空闲分区均匀分布 减少了查找时间减少了查找时间缺点缺点 不能保留大的空闲区不能保留大的空闲区第31/96页 基本思想基本思想：空闲区按空闲区大小升序方法组织。分：空闲区按空闲区大小升序方法组织。分配时，按申请的大小逐个与空闲区大小进行比较，找到配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空

24、闲区，就分配给它。一个满足要求的空闲区，就分配给它。所谓最佳即选中所谓最佳即选中的空闲区是满足要求的最小空闲区。的空闲区是满足要求的最小空闲区。 特点：特点： 用最小空间满足要求用最小空间满足要求第32/96页优点优点v在系统中若存在一个与申请分区大小相等的空闲在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。区，必定会被选中，而首次适应法则不一定。v若系统中不存在与申请分区大小相等的空闲区，若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。致于毁掉较大的空闲区。缺

25、点缺点v分割后的空闲区将会很小，直至无法使用，而造分割后的空闲区将会很小，直至无法使用，而造成浪费。成浪费。v分配和回收后要对空闲区表（队列）重新排序。分配和回收后要对空闲区表（队列）重新排序。第33/96页 基本思想：基本思想：与最佳适应算法相反，空闲区按容量递减与最佳适应算法相反，空闲区按容量递减顺序排列。当接到内存申请时，如第一顺序排列。当接到内存申请时，如第一 个空区满足要求个空区满足要求就进行分配，就进行分配，修改空闲区的大小，并将它插入到空闲区修改空闲区的大小，并将它插入到空闲区表的适当位置；表的适当位置；否则分配失败。否则分配失败。 特点：特点：当分配后剩下的空区仍可为较大空区当

26、分配后剩下的空区仍可为较大空区第34/96页 优点优点v当程序装入内存中最大的空闲区后，剩下的空闲区当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。还可能相当大，还能装下较大的程序。v另一方面每次仅作一次查询工作另一方面每次仅作一次查询工作第35/96页 某时刻系统中有三个空闲区，大小和首址为：某时刻系统中有三个空闲区，大小和首址为： (35KB(35KB，100KB)100KB)、(12KB(12KB，156KB)156KB)、(28KB(28KB，200KB)200KB) 有一作业系列：有一作业系列： (JOB1(JOB1，12KB)12KB)、(JOB2(J

27、OB2，30KB)30KB)、(JOB3(JOB3，28KB)28KB)第36/96页作业序列：作业作业序列：作业A A要求要求21K21K；作业；作业B B要求要求30K30K，作业，作业C C要求要求25K25K。第37/96页 当某个进程释放某存储区时，系统首先检查释放当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。区插入到空闲区表的适当位置。 A X B A B A X A X B

28、B x 变为变为变为变为变为变为变为变为X终止前终止前X终止后终止后第38/96页释放区不与任何空闲区相邻释放区不与任何空闲区相邻 将释放区作为一个空闲区，将其大小和首址插入到空闲区链的适当将释放区作为一个空闲区，将其大小和首址插入到空闲区链的适当位置。位置。释放区与后空闲区相邻释放区与后空闲区相邻 则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大小之和。小之和。释放区与前空闲区相邻释放区与前空闲区相邻 将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，大小

29、为释放区大小与空闲区大小之和。大小为释放区大小与空闲区大小之和。释放区与前后两个空闲区相邻释放区与前后两个空闲区相邻 将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区结点。个区大小之和，并取消原后空闲区结点。第39/96页碎片（零头）碎片（零头）v经过一段时间的分配回收后，内存中存在很多很小的经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求，空闲块。它们每一个都很小，不足以满足分配要求，这些空闲块被称为这些空闲块被称为碎片碎片。但它们的总和可以满足作业。但

30、它们的总和可以满足作业的要求。的要求。v碎片的出现造成了存储空间的浪费。碎片的出现造成了存储空间的浪费。解决碎片的方法解决碎片的方法v移动技术（紧凑技术、动态地址重定位）移动技术（紧凑技术、动态地址重定位）例例第40/96页移动技术移动技术v若需装入若需装入95K的程序的程序v通过在内存移动程序，将所通过在内存移动程序，将所有小的空闲区域合并为大的有小的空闲区域合并为大的空闲区域。空闲区域。但这种方法的系但这种方法的系统开销太大。统开销太大。 问题问题v移动条件和移动时机移动条件和移动时机 操作系统操作系统进程进程1 1空闲区空闲区60K60K进程进程2 2空闲区空闲区30K30K进程进程3

31、3空闲区空闲区26K26K操作系统操作系统进程进程1 1进程进程2 2进程进程3 3空闲区空闲区116K116K操作系统操作系统进程进程1 1进程进程2 2进程进程3 3空闲区空闲区25K25K进程进程4 495K95K第41/96页引入引入 分区存储管理的主要问题是分区存储管理的主要问题是碎片问题碎片问题。动态重定位。动态重定位是解决存储器碎片问题的一种途径，但要移动大量是解决存储器碎片问题的一种途径，但要移动大量信息花去不少处理机时间信息花去不少处理机时间, ,代价比较高。这是因为这代价比较高。这是因为这种分配要求把作业必须安置在一连续存储区内的缘种分配要求把作业必须安置在一连续存储区内的

32、缘故故, ,而分页存储管理正是要避开这种连续性要求。而分页存储管理正是要避开这种连续性要求。离散分配方式离散分配方式v分页存储管理方式分页存储管理方式v分段存储管理方式分段存储管理方式v段页式存储管理方式段页式存储管理方式 第42/96页页面页面 把一个进程的逻辑地址空间划分成若干个大小相等的片，称为把一个进程的逻辑地址空间划分成若干个大小相等的片，称为页页（pagepage）或页面）或页面 。从。从0 0开始编制开始编制页号页号，页内地址是相对于，页内地址是相对于0 0编址。编址。块块 内存空间按页的大小划分为大小相等的区域，称为内存空间按页的大小划分为大小相等的区域，称为页框或内存页框或内

33、存块或物理块块或物理块。从。从0 0开始编制开始编制块号块号，块内地址是相对于，块内地址是相对于0 0编址。编址。 页大小页大小= =块大小块大小 例例页内碎片页内碎片 有时由于进程的最后一页装不满一块，就形成了不可利用的碎有时由于进程的最后一页装不满一块，就形成了不可利用的碎片，称为片，称为页内碎片页内碎片。页面大小页面大小 在划分页面时，其大小要适中。在划分页面时，其大小要适中。太小：可以减少内存碎片，提高利用率，但占用页面较多，页表太小：可以减少内存碎片，提高利用率，但占用页面较多，页表过长，占用大量内存空间。过长，占用大量内存空间。太大：可以减少页表长度，但增大页内碎片。太大：可以减少

34、页表长度，但增大页内碎片。 一般页面大小为一般页面大小为512B8KB，应是，应是2m第43/96页用户进程空间用户进程空间页大小页大小=1K=1K0页页1页页2页页0B0B1024B1024B2048B2048B3000B3000BOS0块块1块块2块块3块块N块块内存空间内存空间第44/96页逻辑地址逻辑地址 地址结构：地址结构： 用户程序的划分是由系统自动完成的，对用户是用户程序的划分是由系统自动完成的，对用户是透明的。透明的。 地址的高位部分为页号，低位部分为页内地址。地址的高位部分为页号，低位部分为页内地址。页号页号 页内地址页内地址0111223页号页号P页内位移量页内位移量W编号

35、编号04095B相对地址相对地址04095B第45/96页逻辑地址以十进制数给出逻辑地址以十进制数给出 a.a.页号逻辑地址页大小页号逻辑地址页大小 b.b.页内地址逻辑地址页内地址逻辑地址 mod mod 页大小页大小例例 页面大小是页面大小是1KB，逻辑地址是，逻辑地址是12574B 页号页号P=12，页内地址，页内地址W=286例例 页面大小是页面大小是2KB，逻辑地址是，逻辑地址是12574B 页号页号P=6，页内地址，页内地址W=286第46/96页逻辑地址（程序地址）以十六进制的形式给出逻辑地址（程序地址）以十六进制的形式给出 a.a.将逻辑地址转换成二进制的数；将逻辑地址转换成二

36、进制的数； b.b.按页的大小分离出页号和页内地址（低位部分是页内地址，高位按页的大小分离出页号和页内地址（低位部分是页内地址，高位部分是页号）；部分是页号）；第47/96页内存分配思想内存分配思想 要求程序全部装入内存后，才能开始运行。系统以要求程序全部装入内存后，才能开始运行。系统以块块为单位进为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。上不一定相邻。第48/96页页表页表 静态页式存储管理的数据结构，指出页面与内存块的静态页式存储管理的数据结构，指出页面与内存块的对应关系。其作用是实现从页号到物理块号的

37、地址映对应关系。其作用是实现从页号到物理块号的地址映射。射。页表结构页表结构v页号：登记程序地址空间的页号。页号：登记程序地址空间的页号。v块号：登记相应的页所对应的内存块号。块号：登记相应的页所对应的内存块号。系统为系统为每个进程建立一个页表每个进程建立一个页表，页表的长度和首地址，页表的长度和首地址存放在该进程的进程控制块（存放在该进程的进程控制块（PCBPCB）中。）中。页表必须驻留在内存。页表必须驻留在内存。第49/96页作业名BA页表始址XXXXXX页表长度XXXX第50/96页 在静态页式管理中在静态页式管理中, ,内存的分配以内存的分配以块块为单为单位位, ,应设置一个数据结构来

38、记录内存中块的使应设置一个数据结构来记录内存中块的使用情况用情况, ,以便实现内存的分配和回收以便实现内存的分配和回收. .位示图位示图空闲块链空闲块链内存分块表内存分块表第51/96页 位示图由内存中的若干个字节组成，位示图中的每一位示图由内存中的若干个字节组成，位示图中的每一位对应内存中的一个块。位对应内存中的一个块。 0 0表示空闲表示空闲 1 1表示已分配表示已分配例如：内存空间划分为例如：内存空间划分为128128块，则位示图应由块，则位示图应由1616个字节组成个字节组成第52/96页 顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二的二

39、进制位进制位(“0”表示空闲时表示空闲时)。 将所找到的一个或一组二进制位，将所找到的一个或一组二进制位， 转换成与之相应的转换成与之相应的 块号。假定找到的其值为块号。假定找到的其值为“0”的二进制位，位于位示图的二进制位，位于位示图 的第的第i行、第行、第j列，则其相应的块号应按下式计算：列，则其相应的块号应按下式计算： b=n(i-1)+j-1 式中，式中， n代表每行的位数。代表每行的位数。 修改位示图，修改位示图， 令令mapi,j=1。 第53/96页 将回收块的块号转换成位示图中的行号和列号。将回收块的块号转换成位示图中的行号和列号。 转换公转换公式为：式为： i=b DIV n

40、+1 j=b MOD n+1 修改位示图。修改位示图。 令令map i,j=0。 第54/96页将所有将所有空闲块空闲块链接成一个空闲块链。链接成一个空闲块链。分配时，从链首依次分配若干个空闲块。分配时，从链首依次分配若干个空闲块。回收时，将空闲块插入链尾。回收时，将空闲块插入链尾。 第55/96页 用于记录内存中用于记录内存中所有块所有块的使用情况，包含块号、进程的使用情况，包含块号、进程号、页号和状态等信息。号、页号和状态等信息。 状态为状态为0 0表示空闲表示空闲 状态为状态为1 1表示已分配表示已分配 第56/96页页表页表页表寄存器页表寄存器物理地址物理地址页表始址页表始址 页表长度

41、页表长度进程名进程名A A页表始址页表始址xxxxxxxxxxxx页表长度页表长度5050PCBPCB块号块号比较比较页号页号 页内地址页内地址块号块号 块内地址块内地址逻辑地址逻辑地址地址越界地址越界第57/96页判断页号是否越界判断页号是否越界CPU给出逻辑地址给出逻辑地址由分页地址机构把它分为两部分：页号和页内由分页地址机构把它分为两部分：页号和页内地址地址根据页表始址，以页号为索引，找到页所对应根据页表始址，以页号为索引，找到页所对应的块号的块号将块号与页内地址拼接在一起，形成了访问主将块号与页内地址拼接在一起，形成了访问主存的物理地址。存的物理地址。 第58/96页问题的提出问题的提

42、出 在前述的页地址变换过程中有一个严重的问题，那就在前述的页地址变换过程中有一个严重的问题，那就是每一次对内存的访问都要访问页表，页表是放在内存中是每一次对内存的访问都要访问页表，页表是放在内存中的，也就是说每一次访问内存的指令至少要的，也就是说每一次访问内存的指令至少要访问两次内存访问两次内存，运行速度要下降一半。运行速度要下降一半。问题的解决问题的解决 一种方法是把页表中最近常用的部分表目放在一组一种方法是把页表中最近常用的部分表目放在一组高高速存储器速存储器中（中（Cache），从而加快访问内存的速度。我们），从而加快访问内存的速度。我们把这种高速存储器组成的页表称为把这种高速存储器组成

43、的页表称为快表快表（也称为联想寄存（也称为联想寄存器），把存放在内存中的页表称为器），把存放在内存中的页表称为慢表慢表。快表是页表（慢表）的一个子集快表是页表（慢表）的一个子集第59/96页pp页表页表地址越界地址越界比较比较P=1P=1p ppp. . . .快表快表+页号页号P P 页内地址页内地址d dPPd d物理地址物理地址页表寄存器页表寄存器逻辑地址（有效地址寄存器）逻辑地址（有效地址寄存器）P Pb b页表始址页表始址b b页表长度页表长度l l第60/96页当调度程序调度到某个进程时，要从该进程的当调度程序调度到某个进程时，要从该进程的PCBPCB中把该进程的页表始中把该进程的

44、页表始址和页表长度放入址和页表长度放入页表寄存器页表寄存器。当进程要访问某个逻辑地址中的数据时，分页地址机构自动将逻辑地当进程要访问某个逻辑地址中的数据时，分页地址机构自动将逻辑地址分为页号和页内地址两部分，放入址分为页号和页内地址两部分，放入有效地址寄存器有效地址寄存器。用页号与页表长度进行比较，当页号用页号与页表长度进行比较，当页号 页表长度，则表示该地址已超出页表长度，则表示该地址已超出进程的地址空间，产生越界中断错误。进程的地址空间，产生越界中断错误。否则，查找快表，若能找到与该页号匹配的页表项，直接从快表中获否则，查找快表，若能找到与该页号匹配的页表项，直接从快表中获得该页对应的物理

45、块号，送入物理寄存器。得该页对应的物理块号，送入物理寄存器。若在快表中找不到对应的页表项，再访问内存中的页表，得到该页的若在快表中找不到对应的页表项，再访问内存中的页表，得到该页的物理块号。同时把该页表项存入快表的一个寄存器单元中，若快表已物理块号。同时把该页表项存入快表的一个寄存器单元中，若快表已满，从中找一个不再需要的页表项换出。满，从中找一个不再需要的页表项换出。第61/96页需要说明的是，快表的地址转换是非常快的，需要说明的是，快表的地址转换是非常快的，因为它是将页号与快表中的因为它是将页号与快表中的各行同时比较各行同时比较，从而大大减少了地址变换时间，基本上克服从而大大减少了地址变换

46、时间，基本上克服了两次访问主存的缺点。了两次访问主存的缺点。但由于快表成本很高，不能做得很大，通常但由于快表成本很高，不能做得很大，通常只存放只存放16512个页表项。个页表项。第62/96页 1. 数据共享数据共享 2. 程序共享程序共享 第63/96页 多级页表的引入多级页表的引入 页表存储开销太大：页表存储开销太大： CPUCPU具有具有3232位地址时位地址时 , ,使用使用2 23232逻辑地址空间的分页系统逻辑地址空间的分页系统, ,规定页面规定页面4KB4KB时时, ,每个进每个进程页表的表项有程页表的表项有1 1兆兆(2(22020) )个个, ,若表项占用若表项占用4 4个字

47、节个字节, ,则每则每个进程需要占用个进程需要占用4MB4MB连续内存空间存放页表。连续内存空间存放页表。 两级页表两级页表 当页表项很多时，仅采用一级页表需要大片连续空当页表项很多时，仅采用一级页表需要大片连续空间，可将页表也分页，并对页表建立一张外层页表，间，可将页表也分页，并对页表建立一张外层页表，由此构成由此构成二级页表二级页表。 多级页表多级页表 更进一步可形成更进一步可形成多级页表多级页表。第64/96页多级页表概念多级页表概念 页表和页面一样也进行分页，内存仅存放当前使用的页表页表和页面一样也进行分页，内存仅存放当前使用的页表, ,暂时暂时不用部分放在磁盘上不用部分放在磁盘上,

48、,待用到时再行调进。待用到时再行调进。具体做法具体做法 把整个页表进行分页把整个页表进行分页, ,分成一张张小页表分成一张张小页表( (称为称为页表页面页表页面) ) , ,每个每个页表页面的大小与物理块相同，为进行索引查找页表页面的大小与物理块相同，为进行索引查找, ,应该为这些页应该为这些页表页面建一张页表表页面建一张页表, ,称为称为外层页表外层页表，其表项指出页表页面所在物，其表项指出页表页面所在物理块号及相关信息。理块号及相关信息。 系统为每个进程建一张外层页表，它的每个表项对应一个页表页系统为每个进程建一张外层页表，它的每个表项对应一个页表页面面, ,而页表页面的每个表项给出了页面

49、和块号的对应关系而页表页面的每个表项给出了页面和块号的对应关系, ,外层页外层页表是一级页表表是一级页表, ,页表页面是二级页表。页表页面是二级页表。逻辑地址结构逻辑地址结构 外层页号、外层页内地址、页内地址外层页号、外层页内地址、页内地址第65/96页外层页表寄存器外层页表寄存器外层页号外层页号外层页内地址外层页内地址 页内地址页内地址逻辑地址逻辑地址页表地址页表地址.外层页表（每进程一个）外层页表（每进程一个）块号块号.页表页表代码或数据代码或数据.内存块内存块+块号块号 块内地址块内地址物理地址物理地址第66/96页优点优点 解决了碎片问题解决了碎片问题 便于管理便于管理缺点缺点 不易实

50、现存储共享不易实现存储共享 存在页内碎片存在页内碎片第67/96页基本原理基本原理 在进程开始运行之前，不是装入全部页面，而是装入一个或零在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。个页面，之后根据进程运行的需要，动态装入其它页面。 当内存空间已满，而又需要装入新的页面时，则根据某种算法当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。淘汰某个页面，以便装入新的页面。 例例怎样才能发现页面不在内存中呢怎样才能发现页面不在内存中呢? ?怎样处理这种情况怎样处理这种情况呢呢? ? 采用的办法是：采用的办

51、法是：扩充页表扩充页表的内容，增加驻留标志位和页面辅存的内容，增加驻留标志位和页面辅存的地址等信息的地址等信息。通过产生通过产生缺页中断缺页中断来处理来处理. .前进前进第68/96页151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间

52、 虚页虚页页框页框返回返回第69/96页 页号、内存块号、驻留位、外存地址、访问位、修改位页号、内存块号、驻留位、外存地址、访问位、修改位v驻留位（中断位）：表示该页是在内存还是在外存驻留位（中断位）：表示该页是在内存还是在外存v访问位：根据访问位来决定淘汰哪页（由不同的算法决访问位：根据访问位来决定淘汰哪页（由不同的算法决定）定）v修改位：查看此页是否在内存中被修改过修改位：查看此页是否在内存中被修改过页号页号驻留位驻留位辅存地址辅存地址访问位访问位 修改位修改位内存块号内存块号第70/96页1 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1驻留位驻留

53、位第71/96页 在地址映射过程中，在页表中发现所要访问的页在地址映射过程中，在页表中发现所要访问的页不在内存，则产生不在内存，则产生缺页中断缺页中断。操作系统接到此中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存。出的外存地址，准备将该页调入内存。v此时应将缺页的进程挂起（调页完成唤醒）此时应将缺页的进程挂起（调页完成唤醒）v如果内存中有空闲块，则分配一个块，将要调入如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项目的驻的页装入该块，并修改页表中相应页表项目的驻留位及

54、相应的内存块号留位及相应的内存块号v若此时内存中没有空闲块，则要淘汰某页（若被若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）淘汰页在内存期间被修改过，则要将其写回外存）第72/96页缺页中断和一般中断都是中断。缺页中断和一般中断都是中断。相同点：相同点：v保护现场保护现场 、中断处理、中断处理、 恢复现场恢复现场不同点：不同点：v一般中断是一般中断是一条指令完成后一条指令完成后检查和处理中断信号，缺页检查和处理中断信号，缺页中断是中断是一条指令执行时一条指令执行时产生和处理中断信号。产生和处理中断信号。v缺页中断缺页中断返回到该指令的开始返回到该指令的开

55、始重新执行该指令，而一般重新执行该指令，而一般中断返回到该指令的中断返回到该指令的下一条指令下一条指令执行。执行。v一条指令执行时可能产生多个缺页中断。如指令可能访一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。问多个内存地址，这些地址在不同的页中。 第73/96页系统为进程分配主存，需考虑因素系统为进程分配主存，需考虑因素: :v分给进程的空间越小，同一时间处于内存的进程就越分给进程的空间越小，同一时间处于内存的进程就越多，至少有一个进程处于就绪态的可能性就越大多，至少有一个进程处于就绪态的可能性就越大v如果进程只有小部分在主存里，即使局部性很好，缺如果

56、进程只有小部分在主存里，即使局部性很好，缺页中断率还会相当高页中断率还会相当高. .v因程序的局部性原理，分给进程的内存超过一定限度因程序的局部性原理，分给进程的内存超过一定限度后，再增加内存空间，不会明显降低进程的缺页中断后，再增加内存空间，不会明显降低进程的缺页中断率。率。 基于这些因素，在页式虚存系统中，可采用两种策基于这些因素，在页式虚存系统中，可采用两种策略分配页框给进程。略分配页框给进程。第74/96页内存分配策略分为两种内存分配策略分为两种 进程保持页框数进程保持页框数固定不变固定不变，称固定分配，称固定分配; ;进程分得的页框数可进程分得的页框数可变，称变，称可变分配可变分配。

57、固定分配固定分配 进程创建时，根据进程类型和程序员的要求决定页框数，只进程创建时，根据进程类型和程序员的要求决定页框数，只要有一个缺页中断产生，进程就会有一页被替换。即使内存中要有一个缺页中断产生，进程就会有一页被替换。即使内存中有空闲的物理块，也不分配给该进程。有空闲的物理块，也不分配给该进程。可变分配可变分配 先为每个进程分配一定数目的物理块，进程执行的某阶段缺先为每个进程分配一定数目的物理块，进程执行的某阶段缺页率较高，说明目前局部性较差，系统可多分些页框以降低缺页率较高，说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前局部性较好，可减少分给进程的页框页率，反之说明进程

58、目前局部性较好，可减少分给进程的页框数。数。第75/96页固定分配缺少灵活性，而可变分配的性能会更好些，固定分配缺少灵活性，而可变分配的性能会更好些，被许多操作系统采用。被许多操作系统采用。采用可变分配策略的困难在于操作系统要经常监视采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况，会增加活动进程的行为和进程缺页中断率的情况，会增加系统的开销。系统的开销。第76/96页全局置换全局置换v如果页面置换算法的作用范围是整个系统，称全如果页面置换算法的作用范围是整个系统，称全局页面置换算法，它可以在运行进程间动态地分局页面置换算法，它可以在运行进程间动态地分配页框。被

59、置换的页可以是内存中任一进程的页。配页框。被置换的页可以是内存中任一进程的页。局部置换局部置换v如果页面置换算法的作用范围局限于本进程，称如果页面置换算法的作用范围局限于本进程，称为局部页面置换算法，它实际上需要为每个进程为局部页面置换算法，它实际上需要为每个进程分配固定的页框。始终保持分配给该进程的物理分配固定的页框。始终保持分配给该进程的物理块数不变。块数不变。第77/96页固定分配局部置换策略固定分配局部置换策略 进程分得的页框数不变，发生缺页中断，只能从进程的页面进程分得的页框数不变，发生缺页中断，只能从进程的页面中选页置换，保证进程的页框总数不变。中选页置换，保证进程的页框总数不变。

60、策略难点策略难点 应给每个进程分配多少页框应给每个进程分配多少页框? ? 给少了，缺页中断率高；给多了，给少了，缺页中断率高；给多了，使内存中能同时执行的进程数减少，进而造成处理器和其它设使内存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。备空闲。采用固定分配算法，系统把页框分配给进程，采用：采用固定分配算法，系统把页框分配给进程，采用：1)1)平均分配平均分配2)2)按比例分配按比例分配3)3)优先权分配优先权分配第78/96页先每个进程分配一定数目页框，先每个进程分配一定数目页框，osos保留若干空闲保留若干空闲页框，进程发生缺页中断时，从系统空闲页框中页框，进程发生缺页中断时，