操作系统讲稿-5-2013

第五章存储管理存储管理基础

存储管理的基本概念

覆盖与交换技术连续存储空间管理非连续分配管理方式虚拟存储器管理虚拟存储器的基本概念请求分页存储管理页面置换算法页面分配策略抖动请求分段管理方式存储管理基础

1.存储管理的基本概念内存管理的功能存储分配问题。重点是研究存储共享和各种主存空间的分配与回收。地址再定位问题。研究各种地址变换机构，将逻辑地址转换为物理地址。存储保护问题。研究保护各类程序、数据区的方法。由硬件和软件配合完成存储扩充问题。主要研究虚拟存储器问题及其各种调度算法。从逻辑上扩充内存容量。（1）物理地址与逻辑地址

物理地址与物理地址空间内存中的每个物理存储单元都有一个编号，这个编号称为内存地址，即物理地址（也称绝对地址）。存地址从0开始编号，最大值取决于内存的大小和地址寄存器所能表示的最大值物理地址的集合称为物理空间，也称存储空间逻辑地址与逻辑地址空间用户的源程序一旦编译之后，每个目标模块都以0为基地址进行编址，这种地址称为逻辑地址或相对地址。逻辑地址的集合形成了一个地址范围，这个范围称为逻辑地址空间，也称为地址空间。（2）用户程序的处理过程

用户作业的程序通常用高级语言编写，称为源程序。源程序是不能被计算机直接执行的，需要经过编译、链接和装入和执行几个步骤才能在内存中执行，如图所示。源程序装入模块库编译程序……目标模块链接程序装入程序内存图5.1用户程序处理过程示意图（3）主存空间的保护

计算机中使用的存储保护主要有界地址、存储键等保护方式。

上下界保护和地址检查机构

（3）主存空间的保护（续）基址、限长寄存器和动态地址转换机构

（4）地址重定位地址重定位用户程序放在逻辑地址空间（在外存），运行时装入内存，这就存在逻辑地址与物理地址的转换。将用户使用的逻辑地址转换成内存空间中的物理地址的过程就称为地址转换（映像），也称为地址重定位。（4）地址重定位(续)重定位类型静态地址重定位在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。动态地址重定位动态地址重定位是在程序执行过程中，在CPU访问内存之前,才将要访问的程序或数据地址转换成内存地址.动态重定位依靠硬件地址变换机构完成。（4）地址重定位(续)80KB50KB030KOSOS作业A地址空间作业A地址空间030KB0110KB主存主存80KB静态地址重定位（4）地址重定位(续)L1,50012345作业地址空间0100500600L1,50012345010001100150016001000500处理机一侧存储器一侧+BR有效地址再定位寄存器600LR界限寄存器主存动态地址重定位

2.覆盖与交换技术为什么引入？

在多道环境下扩充内存的方法，解决在较小的存储空间中运行较大程序时遇到的矛盾覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现交换技术与覆盖技术共同点：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换2.覆盖与交换技术（续）覆盖技术指一个作业的某些程序段，或几个作业的某些部分轮流使用某一段存储空间。基本思想是把内存中同一区域，静态地分配给一道程序的若干个子程序或数据段，在开始时只让一部分程序装入内存，根据运行的情况，交替轮流使用。和单用户连续区分配、分区分配技术配合使用。用户需要小心设计程序的数据结构，使其覆盖模块具有相对独立性。例2.覆盖与交换技术（续）缺点：对用户不透明，增加了用户负担例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构2.覆盖与交换技术（续）交换技术当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度多用于分时系统中使用外存做缓存，通过不断换出换入而运行大作业分进程交换和部分交换（页面交换和分段交换）提高内存利用率，增加并发进程数，提高系统效率交换使用的技术较多：换出进程的选择、交换时机的确定、需要一个盘交换区及管理、换入回内存时位置的确定等3.连续存储空间管理（1）单一连续存储管理基本原理

将内存划分为系统区和用户区；内存中仅驻留一道程序，整个系统资源和用户区只为一个用户所独占；仅适用于单用户、单任务操作系统。

优缺点简单、易实现仅适合单道程序，处理机和内存不能充分利用（1）单一连续存储管理（续1）主存空间的分配与回收主存空间的分配：系统区和用户区

主存空间的回收：运行结束，释放主存空间

地址转换与存储保护：单用户连续存储管理的地址转换可以采用静态重定位和动态重定位两种方法。

（1）单一连续存储管理（续1）采用静态重定位方法采用静态重定位，程序执行之前由装入程序完成逻辑地址到物理地址的转换。如图所示。主要优点：实现简单，无需硬件地址转换机构支持。

作业1装入程序操作系统区作业1的程序和数据界限地址界限地址+逻辑地址（1）单一连续存储管理（续1）采用动态重定位方法设置一个定位寄存器，既用来指出主存中的系统区和用户区的地址界限，又作为用户区的基地址；通过装入程序把程序装入到从界限地址开始的区域，但此时并不进行地址转换；程序执行过程中动态地将逻辑地址与定位寄存器中的值相加就可得到物理地址。

基本原理

预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只能装一个作业存储分配：如果有一个空闲区，则分配给进程（2）固定分区存储管理（2）固定分区存储管理（续1）主存空间的分配与回收

数据结构与主存分区分配表(a)分区说明表(b)存储空间分配表分区号大小（K）起址地址（K）状态1816Job121624031640Job243256Job3操作系统Job10Job2Job3016K24K40K56K（2）固定分区存储管理（续2）固定式分区表

(a)分区号12345大小8

KB32

KB32

KB120

KB520

KB起始地址312

KB320

KB352

KB384

KB504

KB状态在使用在使用在使用未用未用(b)操作系统504KB384KB352KB320KB312KB0520KB120KB32KB32KB8KB312KB固定式分区举例固定式分区举例

分区号分区容量作业容量剩余容量123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合计712KB173KB539KB操作系统504KB384KB352KB320KB312KB0520KB120KB32KB32KB8KB312KBJ1J2J3J4J5内存利用率不高（2）固定分区存储管理（续2）地址转换与存储保护采用静态重定位方式。系统设置两个寄存器：上界寄存器和下界寄存器。上界寄存器用来存放分区的低地址，即起始地址；下界寄存器用来存放分区的高地址，即末址。装入程序在进行地址转换时，将CPU获得的逻辑地址首先与上下界寄存器的值进行比较，若超出上、下界寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理。运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和上、下界寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行

（2）固定分区存储管理（续3）管理特点

一个作业只能装入一个分区。当一个分区的大小不能满足一个作业的要求时，该作业暂时不能装入。通过对“分区分配表”的改写，来实现主存的分配与回收。简单、易行，适合多道程序设计。当分区较大而作业较小时，容易形成碎片，造成主存空间的浪费。这种方式分区总数固定，也限制了并发执行的作业数目。

定义：在存储分配过程中，分配给用户而未被利用的那部分内存，称为内存的“内零头”或“内碎片”

（3）可变分区存储管理基本原理内存不是预先划分好分区的，而是根据装入作业的实际需要动态地划分存储空间。分区的个数和大小是不固定的作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间（3）可变分区存储管理（续1）主存空间的分配数据结构已分配分区表未分配（空闲）分区表主存空间分配动态分配三种分配算法：首次适应算法、最佳适应算法、最坏适应算法（3）可变分区存储管理（续2）分区号起址（K）大小（K）状态分区号起址（K）大小（K）状态118601162Job12346022410Job235632034016job34………4………5………5………图5.8未分配分区表图5.9已分配分区表分区表格式：申请分配一个xKB大小的分区置空闲区号f=1f大于最后一个空闲区号？空闲区可用？保存空闲区的起始地址空闲区f的大小≥xKB空闲区的状态=空项修改空闲区的大小和起始地址在已分配表中找一个状态=空项的分区号

P置分区P的大小为

xKB置分区起始地址置分区状态为已分配返回一个分区号此次无法分配f+1fYYNN<>=可变分区中请求一个分区的流程首次（最先）适应分配算法：未分配分区表按地址递增的顺序排列，每次分配时，从空闲分区表的第一个表目开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，把能够满足要求的空闲区分配给作业。该算法简单，尽可能地利用了低地址空间，把较大的空闲分区留在内存高端，有利于大作业的分配。但低端分区产生过多的小地址碎片，每次分配时查找时间开销增大，降低了主存空间的利用率。该算法改进后称为首次循环适应算法，它的分配和释放的时间性能较好，使空闲分区分布得更均匀，但不易保留较大的空闲分区。（3）可变分区存储管理（续3）（3）可变分区存储管理（续4）最佳适应分配算法未分配分区表按照分区的大小从小到大进行排列，分配时，自表头顺序开始查找到第一个满足要求的空闲分区。保证不去分割更大的区域，使装入大作业时比较容易得到满足。该算法的特点是可以解决大作业的分配问题；但是容易产生不可利用的小空闲区，降低了主存空间的利用率。最差（坏）适应分配算法未分配分区表按照分区的大小从大到小进行排列，分配时，只看第一个分区能否满足作业要求，若可以，将该分区分配给作业使用，否则作业不能执行。该算法的优点是查找效率很高；可使剩下的空闲区不至于太小，对中、小作业有利，对于大作业不利。（3）可变分区存储管理（续5）可变分区的分配和回收示例（3）可变分区存储管理（续6）主存空间回收合并

当某一块归还后，前后空间合并，修改内存空闲块表

考虑：上邻、下邻、上下相邻、上下不相邻情况1情况2情况3情况4…………作业B回收区P上邻空闲区f1作业B上邻空闲区f1下邻空闲区f1回收区P回收区P回收区P作业A下邻空闲区f1作业A…………图5.10可变式分区回收的四种情况请求释放一个分区P保存分区P的大小和起始地址置分区的状态为空项分区P有邻接的空闲区?修改新空闲区的大小起始地址和状态返回修改空闲区的状态修改新空闲区的大小和起始地址在未分配表中找一空表目置新空闲区大小和起始地址置空闲区状态为可用在两个空白区之间有一个空白区N可变分区中释放一个分区的流程（3）可变分区存储管理（续7）“碎片”问题经过一段时间的分配回收后，内存中存在很多小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为外碎片。

造成存储资源的浪费

注意：内部碎片是指已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；外碎片是指还没有被分配出去（不属于任何进程），但由于太小以至无法将它分配给申请内存的新进程。

（3）可变分区存储管理（续8）“碎片”问题解决使用紧凑技术：

通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域。见下图。（又称：紧缩技术，紧致技术，浮动技术，搬家技术）

问题：系统开销大移动时机最好定在内存某一分区不能满足分配需求，但空闲区总和能满足时（3）可变分区存储管理（续9）（3）可变分区存储管理（续10）地址转换与存储保护

地址转换

采用动态重定位方式装入作业，需设置硬件地址转换机构，包括基址寄存器和限长寄存器。地址转换步骤如下：当作业占用处理器时，进程调度程序把该作业所占分区的起始地址送入基址寄存器，把作业所占分区的最大长度送入限长寄存器。作业执行过程由硬件地址转换机构把逻辑地址转换成物理地址。即当取出一条指令后，把该指令中的逻辑地址与基址寄存器内容相加得到物理地址。

（3）可变分区存储管理（续11）存储保护把新作业所占分区的始址和总长度存入“基址寄存器”和“限长寄存器”，这两个专用寄存器中。

当处理器执行该作业的指令时必须核对表达式“始址<=绝对地址<=末址”是否成立。若成立，就执行该指令，否则就产生“地址越界”中断事件，停止执行该指令。

（3）可变分区存储管理（续12）管理特点可变式分区存储管理方式有如下特点：有助于多道程序设计分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业数来决定的分区的大小由作业的大小确定，提高了主存的使用效率在主存分配过程中，会产生许多主存“碎片”，这种在所有分区之外新增的“碎片”称作外部“碎片”，使主存空间仍有一定的浪费

表5.1连续存储空间分配算法比较分配方式有无内碎片有无外碎片优

点缺

点单一连续分配有无简单只能用在单用户、单任务、单道或专用的操作系统固定分区分配有无用于多道程序系统的最简单的分配方案存储空间浪费较多首次适应算法无有分区分配中最简单的方案，利于空白区合并低地址部分用得太多，高地址部分相对空闲，导致查找效率低循环首次适应算法无有查找时间很少，内存空间分布均匀会导致缺少大的空闲分区最佳适应算法无有使得外部碎片都很小，对于一次分配来说是最佳的。长时间来看可能留下了很多难以利用的小空闲区最差适应算法无有使得留下来的空闲区较大，便于下次利用过早用掉大的空闲区会导致以后难以找到足够大的空闲区来满足进程动态可重定位无有通过移动，内存利用率很高需要硬件支持地址转换浪费时间

4.非连续分配管理方式（1）分页存储管理基本原理页面在分页存储管理中，将用户作业的地址空间分成若干个大小相同的区域，称为页面或页，页面是从“0”开始编号，每个页内地址也是相对于0编址。物理块内存空间也划分为与页的大小相等的若干个存储块，称为物理块或页框（frame），并且采用同样的方式为它们进行编号，整个主存的块是从0开始编号，分别称为0块，1块，…，n-1块，块内地址也是相对于0编址。

（1）分页存储管理（续1）逻辑地址的表示用户的逻辑地址从基址0开始编址，即是相对地址。每个相对地址用一个数对（p,w）表示，其中：p是页号w是页内地址，是该页内的偏移量210=1K211=2K212=4K

（1）分页存储管理（续2）注意:逻辑地址与页号及页内偏移地址之间的关系PageNo=INT[Addr/PageLength]PageOffset=AddrMODPageLength举例：对于1KB页面，若给定逻辑地址2170B，则PageNo=2，PageOffset=122页的划分是由系统自动完成的，对用户是透明的。一页的大小为2的整数次幂，地址的高位部分为页号，低位部分为页内地址页面大小选择由机器的地址结构所决定页面大/小各有利弊210-212KB之间（1）分页存储管理（续3）实现的基本思想作业的逻辑地址是连续的。用户在编制程序时只须使用顺序的地址，而不必考虑如何去分页。由地址转换机构和操作系统来决定页面和主存块的大小。用户程序装入主存时是按页装入，页与页之间的地址可以不连续，但页内地址是连续的。存储地址由连续到离散的变化，即分配时，逻辑上相邻的页，物理上不一定相邻的快逻辑地址空间计算举例设一个逻辑地址空间有8页，每页1024字节，映射到32块的物理内存上。试问：（1）逻辑地址空间需要多少位来表示？（2）物理地址空间需要多少位来表示？（1）逻辑地址空间需要13位来表示。其中页号需要3位，因为23=8；页内地址需要10位，因为210=1024。（2）物理地址空间需要15位来表示。其中块号需要5位，因为25=32；块内地址需要10位，因为210=1024。

（1）分页存储管理（续4）主存空间的分配与回收采用的数据结构

页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。页表放在内存，属于进程的现场信息作业表：也叫主存分配表，包括作业名，作业对应页表的起始地址和页表的长度。内存中的每个作业在作业表中有一个登记项。整个系统只有一张作业表。位示图：空闲块管理。页式存储管理以块为单位分配主存空间，由于块的大小是固定的，所以只要在主存分配表中指出哪些块已分配和哪些块未分配以及当前剩余的空闲块数。最简单的办法是用一张“位示图”构成主存分配表。（1）分页存储管理（续5）（1）分页存储管理（续6）

（1）分页存储管理（续7）主存空间的分配系统初启时，系统初始化位示图，把操作系统已占用的物理块的对应位置成“1”，其余位全部置为“0”，空闲块数置为当前可用的空闲块总数。

主存空间分配步骤如下：计算一个进程所需要的总块数N查位示图：是否还有N个空闲块如有足够的空闲块，则页表长度设为N，可填入作业表中；申请页表区，把页表始址填入作业表依次分配N个空闲块，将块号和页号填入页表修改位示图在一个分页存储管理系统中，页的大小为2KB。设主存容量为512KB，描述主存分配的位示图如图所示，0表示未分配，l表示已分配，此时系统要将一个9KB的作业装入内存，回答以下问题：为作业分配内存后，请给出该作业的页表（分配内存时首先分配内存的低地址端）。分页存储管理有无碎片存在？若有，会存在什么碎片？为该作业分配内存后，会产生零头吗？如果产生，碎片大小为多少？11111101111111111101110011100110000010111111111110000000000000001111100000101010…页号块号06118222323427分页存储管理有碎片存在，分页存储管理存在内部碎片，为该作业分配内存会产生大小为IKB的内部碎片。

（1）分页存储管理（续8）地址转换机构由硬件实现，操作系统配合。关键在于页号到物理块号的转换系统设置一对寄存器页表始址寄存器

用于保存正在运行进程的页表的始址页表长度寄存器

用于保存正在运行进程的页表的长度地址转换过程见下图地址转换过程位移量进程地址转换机构内存逻辑地址页表寄存器块号页框页号块号页号块号位移量+页表始址页表长度页表物理地址块号位移量PCB页表始址页表长度>越界中断12345红线部分的工作在进程被调度时由调度程序完成绝对地址计算：块号×块长＋位移量地址变换举例1

某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内地址。请问：（1）这样的地址结构一页有多少字节？逻辑地址可有多少页？一个作业最大的使用空间是多少？（2）逻辑地址2318、4096、850对应的页号、页内地址分别是多少？地址变换举例1【解】（1）由于低10位为页内地址，寻址能力为：210=1024于是一页有1024个字节（或1KB）。逻辑地址共有页面26=64。一个作业最大的使用空间是：641024=64KB。（2）每页大小为1KB，所以逻辑地址除以页面大小，商为页号，余数为页内地址。于是：逻辑地址2318：页号为2，页内地址为270；逻辑地址4096：页号为4，页内地址为0；逻辑地址850：页号为0，页内地址为850。地址转换举例2页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址转换过程如图所示。假定页面的大小为8K，计算图中所示的十进制逻辑地址9612经过地址转换后，形成的物理地址a应为多少？

地址转换举例2【解】计算逻辑地址9612的页号和页内位移为：页号：9612/（8*1024）=1（取整）页内位移：9612－8*1024=1420通过页表查询，知1页的内容存放在3号物理块中，根据题意页面的大小为8K，将物理块号与逻辑地址中的页内位移拼接，形成物理地址：

3*（8*1024）+1420=25996所以，十进制逻辑地址9612经过地址转换后，形成的物理地址a是25996。地址变换举例3某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C（H）所对应的物理地址是什么？页号物理块号051102437地址变换举例3【解】0A5C(H)：00001010

01011100

2查表得：4

0100拼接得：0001001001011100125C(H)

逻辑地址0A5C（H）所对应的物理地址是125C（H）

（1）分页存储管理（续9）相联存储器——快表快表（联想存储器）用途：为了提高地址映射速度(两次读内存)保存正在运行进程的页表的子集（部分页表项）特点：按内容并行查找快表表项：页号；内存块号；具有块表地址转换过程

见下图

（1）分页存储管理（续10）页表始址页表长度逻辑地址L页表寄存器页表页号页内地址页号>页表长度+页号块号快表输入寄存器物理地址db越界中断b页号块号b图5.17具有快表的地址转换是否（1）分页存储管理（续11）层次化（多级）页表现代计算机系统支持非常大的逻辑地址空间(232-264)，页表变得庞大。例如，对于具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个；若同时设定页表项大小为4B，则每个进程仅页表便需占用4MB内存空间，且要求是连续的。解决方案多级页表(将页表本身也以页面为单位进行分页，分成一张张的页表页

)或反置页表一个简单的解决方法是使用两层分页方法，就是将页表再分页，如下图所示。多级页表举例某计算机采用二级页表的分页存储管理方式，按字节编址，页的大小为210字节，页表项大小为2字节，逻辑地址结构为：页目录号页号页内偏移量逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含页目录表项的个数至少是（）。A、64B、128C、256D、512每个页表中最多页表项数=210/2=29，页目录表中最多项数=216/29=27=128分页存储管理特点

（1）程序和数据存放在不连续的主存空间，不必通过紧凑来解决“碎片”问题。（2）通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间。（3）要求有相应的硬件支持，增加了系统成本，也增加了系统开销。如需要地址转换机构、快表等。（4）仍然存在不可利用的空间，最后一页没有放满（页内碎片）等。页的大小固定，不能随程序的大小而变，对程序的共享和使用造成了许多困难。

（2）段式存储管理

段式存储管理方式的引入主要是为了满足程序员在编程和使用上的要求。基本思想用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的逻辑地址表示实现可以基于可变分区存储管理的原理，但是以段为单位，不是以作业为单位。

（2）段式存储管理（续1）主存空间的分配与回收

采用的数据结构

空闲分区表：整个主存设置一张空闲分区表,用于记录主存中空闲区的序号、起始地址和大小。段表：系统为每个进入内存的作业建一张段表，记录了段号，段的首（地）址和长度之间的关系，放在内存属于进程的现场信息（2）段式存储管理（续2）作业表

整个系统设置一张作业表，记录主存中各作业的作业名、段表始址和段表长度，段表长度为段表中的最大序号。（2）段式存储管理（续3）主存空间的分配作业分配时用作业的长度与空闲分区表的所有记录的长度之和进行比较。若大于则不能装入。否则，装入该作业，为该作业创建一张段表。根据每个作业段的大小在空闲分区表中查找满足其大小的空闲块，把该段装入，并在段表中填入该段的段长和段的起始地址；如果此空闲块可以分割，则剩余部分仍作为空闲分区登记在空闲分区表中，直至所有段分配完毕。若找不到足够大的空闲分区，可以采用紧凑技术，合并分散的空闲区后，再装入该作业段。最后，在主存分配表中，登记该作业段表的起始地址和段表的长度。（2）段式存储管理（续4）主存空间的回收当作业运行结束时，根据该作业段表的每一条记录，去修改空闲分区表。修改的方式与可变分区回收主存空间相同。然后删除该作业的段表和主存分配表中该作业的记录。

（2）段式存储管理（续5）地址转换机构系统设置一对寄存器段表始址寄存器：

用于保存正在运行进程的段表的始址段表长度寄存器

用于保存正在运行进程的段表的长度地址变换见下图相联存储器——快表

快表项目：段号；段始址；段长度地址越界段号>段表长度段号S段内位移W段表始址段表长度逻辑地址段表寄存器+段表B+W+段号0Sn段长基址W>C...:...............主存......C............B......物理地址0:B+W图5.23段式管理地址转换过程地址越界是是否否S（2）段式存储管理（续6）分段管理举例1某段表内容如下：

试问：[2,154],[3,2049]的实际物理地址为多少？段号段首地址段长度0120k40k1760k30k2480k20k3370k2k分段管理举例1【解】由[2,154]表示可知，访问地址为2段，段内地址为154。根据题意，2段的段首地址为480K，段长20K，故[2,154]访问地址为：480K+154=480×1024＋154。由[3,2049]表示可知，访问地址为3段，段内地址2049。根据题意，3段的段首地址为370K，段长2K，[3,2049]的段内地址为2049，超过段表中规定的段长2K（2048），故产生越界中断。

（2）段式存储管理（续7）段的共享与保护段的共享

通过不同作业段表中的项指向同一个段基址来实现的。于是，几道作业共享的程序可放在一个段中，供各道作业共享具有相同的基址/限长值就行了。段的保护主要进行地址越界保护和共享段的存取方式控制保护。地址越界保护是利用段表中的段长和逻辑地址中的段内相对地址相比较共享段的存取方式控制保护主要是用访问权限进行访问共享段。

（2）段式存储管理（续8）段式存储管理的特点消除了碎片。没有内碎片，仍然存在外碎片，若采用移动技术合并空闲区，会增加系统开销。便于两个或两个以上的作业共享同一子程序。硬件支持更多，成本较高。另外，段的大小受主存可用空闲区大小的限制。分页和分段存储管理的比较相似之处实现机制（地址映射、离散分配）区别分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见。分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，段长可根据用户需要来规定，段起始地址可以从任何主存地址开始。页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。分页的作业地址空间是一维的。分段的作业地址空间是二维的，程序员在标识一个地址时，需给出段名和段内地址。（3）段页式存储管理段页式存储管理方式的引入分页与分段存储管理各有优缺点分页系统能有效地提高内存利用率分段系统则能很好地满足用户需要分页与分段存储管理各取所长、有机结合既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点；又能像分页系统那样很好地解决内存的外部碎片问题以及为各个分段离散地分配内存等问题

（3）段页式存储管理（续1）基本思想用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分）；对系统讲，按页划分每一段逻辑地址表示

内存划分：按页式存储管理方案内存分配：以页为单位进行分配主程序段04K8K12K15K16K子程序段04K8K数据段04K8K10K12K段号段内页号页内地址

（3）段页式存储管理（续2）管理段表：记录了每一段的页表始址和页表长度页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）空闲块管理：同页式管理分配：同页式管理利用段表和页表实现地址映射段号状态页表大小页表始址0111213041段表第0段页表内存页号状态物理块号0111213041第1段页表…页号状态物理块号0111213041段表大小段表始址段表寄存器段页式系统的地址变换结构虚拟存储器管理1.虚拟存储器的概念问题的提出“一次性”全部装入的问题前述各种存储管理方式均要求在作业运行前将作业全部装入内存，而实际上许多作业在每次运行时，并非用到其全部程序作业常驻内存的问题作业装入内存后，便一直驻留在内存直至作业运行结束，其中因输入输出操作尚未完成而处于长期等待状态的运行进程或某些一次性运行程序对宝贵的内存资源的占据来说是不合理的问题后果使一些需要运行的作业无法装入运行，从而严重降低内存利用率和减少系统吞吐量。1.虚拟存储器的概念（续1）虚拟存储器技术要点作业部分装入内存即可启动运行其余部分暂留磁盘程序执行页段访问已调入内存则直接访问尚未调入内存则缺页/段中断及请求调入页段置换功能技术效果大用户程序在小内存空间的运行多道程序并发度的提高1.虚拟存储器的概念（续2）虚拟存储器的定义是指仅把作业的一部分装入内存便可运行作业的存储器系统。是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。虚拟存储逻辑容量也不是无限的，它的最大的容量是由计算机的地址结构决定。1.虚拟存储器的概念（续3）局部性原理虚拟存储器的理论依据是程序的局部性.局部性原理是：在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间——数组的访问，往往局限于很小的范围内。1.虚拟存储器的概念（续4）局限性表现为：

时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。1.虚拟存储器的概念（续5）引入虚拟存储技术的好处可在较小的可用内存中执行较大的用户程序可在内存中容纳更多程序并发执行不必影响编程时的程序结构（与覆盖技术比较）提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)1.虚拟存储器的概念（续6）虚拟存储技术的特征离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。多次性：指将一个作分成多次调入内存。多次性是虚拟存储器最重要的特征。对换性：指允许在作业的运行过程中将暂不使用的程序与数据从内存调至对换区，待以后需要时再调入内存。提高内存利用率。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟存储器实现方式请求分页系统请求分段系统请求段页式系统

2.请求页式存储管理（1）基本思想在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面

（2）页表表项设计页号、状态位、内存块号、访问位、修改位等状态位P：标识该页面是否已调入内存中访问位A：记录该页面最近被访问的情况修改位M：记录该页面内容被调入内存后是否被修改过。外存地址：指出该页在外存上的地址状态位P访问位A修改位M物理块号外存地址页号图5.27请求分页存储管理的页表L1，1KB+aA1，2KB+b006802000块1

块2

块3

块4

块5

块6块7

块8块9块02KB3KB4KB5KB6KB7KB8KB9KB5060块号状态204070803090-1-1作业1作业2作业3L1,1KB+aA1,2KB+b00680200006151000101200123作业4地址空间页面变换表块号0/1页号状态0在内存1不在内存011121315存储空间01KB01KB2KB001001041KB1KB+a2KB2KB+b3KB（3）地址变换机构

请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。

在地址转换中，如果页表表项位的值是1，即为pagefault（缺页）请求分页系统地址变换过程程序请求访问一页CPU检索快表找到否？访问页表是否页在内存？否产生缺页中断请求调页是修改页表对应页表项引用位和修改位形成物理地址地址变换结束页号有效？是否越界中断修改快表执行一条指令形成有效地址计算页号该页在实存吗？缺页中断入口有空闲的实页码？出页修改页表该页修改？复制到辅存取出保存的页号入页找出磁盘地址修改页表重新执行被中断的指令取下一条指令取数据完成该指令硬件软件YNNYYN

（4）缺页中断（PageFault）处理在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的修改位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存

（4）缺页中断处理（续）缺页中断与一般中断的区别：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。654123页面copyATOBB:A:

3.页面置换算法

页面置换—找到内存中并没有使用的一些页，将它换出（1）页面调入策略为能使进程运行，必须事先将一部分要执行的程序和数据调入内存。调入页面的时机

预调页策略：是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于进程的首次调入。有的系统将预调页策略用于请求调页（1）页面调入策略（续1）请求调页策略：是指当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。（1）页面调入策略（续2）从何处调入页面在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区（连续分配）的磁盘I/O速度比文件区（离散分配）要高。每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？在UNIX系统中，对于从未运行过的页面，都应从硬盘文件区调入；对于曾经运行过而又被换出的页面，可以从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。（2）页面置换算法缺页率假定作业Ji共有m页，系统分配给它的主存块为n块，这里m>n。开始时，主存没有装入任何一页的信息。如果作业Ji在运行中成功访问的次数为S，不成功的访问次数为F(产生缺页中断的次数)，则作业执行过程中总的访问次数为A.A=S（成功访问的次数）+F（不成功的访问次数）作业Ji执行过程中的缺页率f=F/A。

需要一个最小的缺页率！！！（2）页面置换算法页面置换算法有：最佳算法(OPT,optimal)先进先出算法(FIFO)Belady现象最近最久未使用算法(LRU,LeastRecentlyUsed)简单时钟算法

最佳页面置换算法理想淘汰算法—最佳页面算法（OPT）它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。实现？作用？

先进先出页面淘汰算法先进先出页面淘汰算法（FIFO）先进先出算法的基本思想是，总是先淘汰那些驻留在主存时间最长的页面，即先进入主存的页面先被淘汰。其理由是：最早调入主存的页面，其不再被访问的可能性最大，这种算法实现起来比较简单。

对照：超市撤换商品替换指针2451（指向最老的一页）页号最近最久未使用页面淘汰算法最近最久未使用页面淘汰算法（LRU——LeastRecentlyUsed）选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页实现代价很高

时间戳或硬件方法简单CLOCK算法CLOCK算法是LRU算法的近似算法。CLOCK算法给每个页面设置一个访问位，标识该页最近有没有被访问过，再将内存中的所有页面通过一个指针链接成一个循环队列。当程序需要访问链表中存在的页面时，该页面的访问位被置为1；若程序要访问的页面在链表中不存在，那就需要淘汰内存中的一个页面，于是一个指针p就从上次被淘汰页面的下一个位置开始顺序地去遍历这个循环链表，当指针p指向的页面的访问位为1时，就重新将它置为0，暂不换出，而给该页第二次驻留内存的机会，指针p再向下移动，当指针p所指的页面的访问位为0时，就选择这一页面淘汰，若遍历了一遍链表仍没有找到可以淘汰的页面，则继续遍历下去。由于该算法是循环地检查各页面的使用情况，故称为CLOCK算法。实现流程图例1在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向依次为3、4、2、6、4、3、7、4、3、6、3、4、8、4、6，根据上述OPT、FIFO和LRU算法的思想，可分别计算它们的缺页次数，见表5.2、表5.3和表5.4。表5.2OPT性能分析（M=3）页面访问次序342643743634846

333333333333888内存块数=3

44444444444444

2666777666666是否缺页√√√√

√

√

√

表5.3FIFO性能分析（M=3）页面访问次序342643743634846

332663744633846内存块数=3

44226377466384

3442633744638是否缺页√√√√

√√√

√√

√√√表5.4LRU性能分析（M=3）页面访问次序342643743634846

342643743634846内存块数=3

34264374363484

3426437446338是否缺页√√√√

√√

√

√

√例2某程序在内存中分配m页初始为空，页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5。当m=3，m=4时缺页中断分别为多少？用FIFO算法计算缺页次数及缺页率FIFO性能分析例(M=3)

FIFO性能分析例(M=4)m=3时，缺页中断9次，f=9/12=75%m=4时，缺页中断10次，f=10/12=83%注：FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加（3）影响缺页次数的因素缺页率是衡量页面置换算法的重要指标。通常缺页率受以下因素的影响：页面置换算法：其优劣影响缺页中断次数。主存物理块的数目：通常情况下，其数目越多，缺页率越低。页面大小：如果划分页面大，缺页率就低；反之，缺页率就高。程序特性：编程方法对缺页中断次数有影响。例3内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128×128按行存放.程序编制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;程序编制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;4.页面分配策略每个进程所需要的最少的页的数目根据不同的系统不一样1)最少物理块数在为进程分配物理块时，首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数（称为最小物理块数）。若系统为某进程所分配的物理块数少于此值时，进程将无法运行，这取决于指令的格式、功能和寻址方式。4.页面分配策略（续1）2)页面的分配和置换策略

在请求分页系统中，可采取固定和可变分配策略。在进行置换时，也可采取全局置换和局部置换。于是可组合成以下三种策略：固定分配局部置换策略：它基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。如果进程在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入另一页，保证分配给该进程的内存空间不变。4.页面分配策略（续2）可变分配全局置换策略系统为每个进程分配一定数目的物理块，而OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。4.页面分配策略（续2）可变分配局部