第四章存储管理课件

操作系统原理第四章存储管理1简介

操作系统中的存储管理主要是指对主存的管理。

主存即内存，是指处理机可以直接存取指令和数据的存储器。主存是现代操作系统进行操作的中心，是计算机系统中的一种重要资源。作为系统资源管理程序的操作系统，必须对主存施以有效、精心的管理。

多道程序设计技术出现后，对存储管理提出了更高要求。一方面，要使主存得到充分、有效的利用；另一方面要为用户提供方便的使用环境。24.1存储器管理的基本概念4.1.1存储管理研究的课题计算机的存储设备可以分为三个层次：高速昂贵而易变（断电后信息丢失）的高速缓存和寄存器，数量很少；速度快，价格高且易变的主存储器(RAM)；速度较低，价格低廉，但不易变的辅存如软、硬磁盘、光盘等。34.1存储器管理的基本概念目前关于存储管理的主要研究课题归纳为四个方面存储分配问题：重点是研究存储共享和各种分配算法；记住主存各个位置的状态，哪些空间已分配，哪些空间设置相应的数据结构记录分配。按一定的策略为用户作业分配内存。实施分配，当用户作业申请时，按需分配，修改相应的表格。回收内存，作业完成，退出主存，修改相应的分配表格。地址再定位问题：研究各种地址变换机构，以及静态和动态再定位方法。地址重定位、地址映射。44.1存储器管理的基本概念存储保护问题：研究保护各类程序、数据区的方法。

为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。存储扩充问题：主要研究虚拟存储器问题及其各种调度算法。一方面需要提高主存利用率，共享主存；另一方面为用户提供一个远远大于主存的地址空间。54.1存储器管理的基本概念4.1.2地址再定位1.地址空间和存储空间地址空间（逻辑空间）：一个目标程序所限定的地址范围，成为该作业的地址空间。是虚的概念。相对地址（逻辑地址）：地址空间的地址都是相对于起始地址0为基准量的，称为相对地址。绝对地址（物理地址）：指存储控制部件能识别存储单元的号。存储空间（物理空间）：所有内存中实际的物理存储单元的集合。存储空间是一个“实”的物体。64.1存储器管理的基本概念名空间符号指令数据说明I/O说明地址空间目标程序（装配模块）存储空间0x01MB74.1存储器管理的基本概念2.地址的再定位

一个逻辑地址空间的程序装入到物理地址空间的时候，由于两个空间不一致，需要进行地址变换，或称地址映射，即地址的再定位。地址再定位有静态再定位和动态再定位两种。静态再定位是在程序执行之前进行地址再定位。通常由装配程序完成。84.1存储器管理的基本概念例现有一个作业A，它需要20K空间，两次运行分别被装入主存中的不同地址。A作业的地址空间0K20K操作系统操作系统主存100K120KA作业的地址空间0K20K主存120K140K94.1存储器管理的基本概念优点：容易实现，无需硬件支持，只要求程序本身时可再定位的。缺点：程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用；程序在存储空间中只能连续分配，不能分布在内存的不同区域；若干用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须使用自己的副本。104.1存储器管理的基本概念动态再定位是在程序执行期间，在每次存储访问之前进行的。作业在存储空间中的位置是装入时确定的，但在运行时允许“搬家”和附加存储空间。114.1存储器管理的基本概念优点：在执行过程中，用户程序在内存中可以移动，这有利于内存的充分利用；程序不必连续存放在内存中，可以分散在内存的若干个不同区域，这只需增加几对基址－限长寄存器，每对寄存器对应一个区域；若干用户可以共享同一程序。缺点：需要附加的硬件支持，实现存储管理的软件算法比较复杂。124.1存储器管理的基本概念4.1.3虚拟存储器概念的引入虚拟存储器的提出VirtualStore（VS）1.解决小内存运行大作业问题

连续区，分区的管理，分页式管理中，如作业长大于内存的用户区长，将无法运行该作业，因为作业一次全装入主存。在多道环境下，要求内存放入多个作业，问题更为突出。2.用户扩大内存的要求，以便有效地支持多道系统和大型程序的需要由于内存硬件价格贵，因此利用VS，可以从逻辑上扩充主存。134.1存储器管理的基本概念3.程序的访问局部性时间的局部性：刚刚访问的部分，可能马上还要访问。例如程序中有大量的循环语句。空间的局部性：被访问部分的邻近区域，可能马上就要被访问（程序的顺序性）。程序段的互斥性：不是每个程序段在执行时同时都运行到。144.1存储器管理的基本概念虚拟存储器的定义让用户编程使用的地址范围决定的虚存空间，远远大于实际的内存空间。对用户而言，它是一个比主存大得多的地址空间，可以按它来编程，而不必考虑主存的不足。对OS而言，是用各种表格机构构造的一个虚拟存储器。154.1存储器管理的基本概念VS的基本实现原理利用表格为用户构造一个虚拟空间，作为实现VS的机构。利用大容量的外存，存放进入VS中的信息,是VS的硬件基础。主存作为VS中的程序和数据得以运行的缓冲区。在内、外存之间信息调度。硬件提供动态地址转换机构。注VS的容量由虚拟地址结构决定，也受外存容量的限制。164.2早期的存储管理4.2.1单一连续分配

每个进程所需的空间分配到主存一块连续区。早期的单道成批处理或个人微机OS或专用OS多用。目的：解决成批作业自动接续问题，不提供共享主存功能。分配方法将主存分为二块连续区：系统区——存放OS和用户区— —存放用户程序；系统设置一个界限寄存器（Fenceregister）指出OS区和用户区的界限，当用户程序地址小于边界地址时，产 生越界中断；由装入程序每次装入一个作业到用户区，剩余的用户区空间浪费掉；采用静态重定位。174.2早期的存储管理特点单道运行，独占资源，浪费了内存碎片，资源利用率低。简单，OS可以小到1KB（一般几十KB），不需复杂的硬、软件支持。缺少灵活性，大作业不能在小内存运行。操作系统32KB作业64KB未用160KB分配给用户作业的空间184.2早期的存储管理4.2.2分区分配

分区分配是能满足多道程序设计需要的一种最简单的存储管理技术，分区管理法也称界地址存储管理法。通常，按照分区的划分方式，又可分为固定式分区、可变式分区、可再定位式分区和多重分区。1.固定式分区法思想：预先将主存用户区划成大小不等若干分区；分区的个数和长度保持固定，每个分区只装入一个作业。分区的个数等于作业的道数。固定分区是实现多道程序设计最简单的一种技术。194.2早期的存储管理分区的分配和释放作业都必须规定最大的存储量；OS设立一张分区说明表，指明块号、位置、长度和状态；装入一个作业时，由再定位装入程序按作业的内存需求量在表中找一个够大的未分配分区，用静态再定位方式装入作业，修改状态标志；回收时，将分区状态置0，即释放。204.2早期的存储管理分区号容量位置状态18KB312KB在使用232KB320KB在使用332KB352KB未用4120KB384KB未用5520KB504KB在使用操作系统312KB8KB32KB32KB120KB520KB0312KB320KB352KB384KB504KB214.2早期的存储管理存储保护设立上界寄存器和下界寄存器分别存放当前运行作业的分区最小绝对地址和最大绝对地址；当访问的地址小于上界或下界时产生越界中断。优点可以共享主存，提高主存利用率。程序一次性装入主存。由于静态再定位，程序不能移动。224.2早期的存储管理缺点分区内部碎片大，浪费内存。

例现有四个作业，其作业长度分别为1K，9K，23K，33K，总计长度为66K，为它们分配分区长分别为4K，12K，28K，44K，共占88K，浪费了22K。作业长度大于分区最大长度，无法分配。

这种方式适于能掌握作业大小、数量的系统及中型机以上的OS，如IBMOS/MFT（任务数固定的多道程序设计系统）。234.2早期的存储管理2.可变式分区法

为了解决固定分区的内部碎片问题，在固定分区管理技术上设计了可变分区管理，适用于多道系统。可变式分区法也就是动态划分存储器的分区方法，它是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业大小。在作业进入系统前，根据作业的大小来申请所需存储容量，然后由系统实施分配。系统为了管理主存分区分配情况，需建立两张表，分别登记已分配区和未分配区的分区容量、位置和状态信息。244.2早期的存储管理可变分区的分配思想新作业装入主存时，找一个足够大的空闲区，按作业长度划分，剩余仍为一个小空闲区；释放时，与相邻的空闲区合并。OS作业1（8KB）作业2（32KB）作业4（24KB）作业3（120KB）作业5（128KB）作业6（256KB）0312KB320KB352KB376KB384KB504KB632KB888KB1024KBOS作业1（8KB）作业2（32KB）作业3（120KB）0312KB320KB352KB384KB504KB1024KBOS作业1（8KB）作业4（24KB）作业5（128KB）作业6（256KB）0312KB320KB352KB376KB504KB632KB888KB1024KB254.2早期的存储管理可变分区管理的数据结构线性表结构

OS设立二张表，已分配区表和空闲区表（未分配区表）。

已分配区说明表未分配区说明表序号首址大小状态序号首址大小状态120K8K已分（1）156K30K可用（1）228K28K已分（1）228K28K空白（0）3142K100K空白（0）386K22K可用（1）4108K34K已分（1）4142K100K可用（1）…………………………………………可变式分区状态表264.2早期的存储管理链表结构：一种利用存储分块自身存放信息即分区附加数据集，并由链指针按照一定算法链接起来。FPBPFPBPFPBPFPBPFB空闲区链结构状态大小前向指针1N+2含有N个字的作业1N+2状态大小后向指针已分配区状态大小前向指针1M+2FP含有M个字的空闲区1M+2BP状态大小后向指针空闲区274.2早期的存储管理可变分区的管理——分配与回收分配的步骤按作业长度找一个够大的空闲区，划出作业长度，多余仍为空闲区；修改空闲区表，填写已分配区表。释放的步骤查看已分配区表，根据释放的地址、长度，得对应表项；该项状态置0，空白项；将释放区记入未分配表中空项，状态置为可用空间；与相邻区合并。284.2早期的存储管理合并邻接空闲区有四种情况合并上邻接区；合并下邻接区；上下两邻接区均可合并；上下两邻接区均不可合并。作业B回收区P上邻接区f1作业B上邻接区f1下邻接区f2回收区P回收区P回收区P作业A下邻接区f2作业A294.2早期的存储管理可变分区的分配算法最先适应法（firstfit）FF：找能满足需求的第一个空闲区，即可分配，剩余部分仍留在空闲区表中。可把空闲区表按地址大小由小到大排列。优点释放时，若有相邻区，易于合并；先分配低地址空间，保留高地址较大的的空间，以备大作业分配。304.2早期的存储管理最佳适应法（BFBestfit）

找能满足作业需要的最小分区分配。将空闲区按长度由小到大排列，即X1≤X2≤X3≤……≤Xn，其中Xi为第i分空闲区长度。S为作业的需要量，则从X1顺序比，直到S≤Xi，从Xi中分配，若Xn不能分，则失败。如Xi>S，剩余的插入合适位置。314.2早期的存储管理优点平均查到一半时，即可以找到最佳空闲区，若有Xi=S，必被选中。保留与S相差大的空闲区，每次分相差小的空闲区。缺点碎片太小，无法利用；分配、回收查找费时；合并不易，要对各空闲区计算最高地址，然后比较，找邻接区，费时。合并后，要插入合适位置也费时。324.2早期的存储管理最坏适应法（worstfit）：每次总是选最大的空闲区分配。将空闲区按长度由大到小排列：X1≥X2≥X3≥……≥Xn，若X1≥S，从X1中分X1-S≠0，剩余的插入合适位置，X1不够大，失败！优点分配速度快，只比较X1长度，即可确定分配；X1分配后，剩余仍较大，可满足以后的需求。缺点各区都均等地减小，不能满足大作业需要。334.2早期的存储管理操作系统作业A2n130K作业D1n214K作业C3N310K作业A1n470K（a）存储器示意图序号首址大小状态1n2+13K1K12n310K13n130K14n470K15m160K06m220K0（c）分配后的最佳适应算法空闲区表序号首址大小状态1n4+13K57K12n130K13n214K14n310K15m160K06m220K0（d）分配后的最差适应算法空闲区表序号首址大小状态1n1+13K17K12n214K13n310K14n470K15m160K06m220K0（b）分配后的首次适应算法空闲区表344.2早期的存储管理3.可再定位式分区分配碎片：内存中无法被利用的小的空闲分区。可再定位式分区分配即浮动分区分配，是解决碎片问题的简单而有效的方法。其基本思想是移动所有被分配了的分区，使之称为一个连续区域，而留下一个较大的空白区。由于程序涉及到基址寄存器、访问内存指令、访问参数表或数据结构，所以一个作业移动位置后，通常无法保证程序在新位置上能够正确运行，为此，应解决程序的可再定位（浮动）问题。354.2早期的存储管理操作系统操作系统用户程序A用户程序A10K用户程序B用户程序B用户程序C50K用户程序D用户程序C105K45K用户程序（a）紧凑前（b）紧凑后紧凑内存示意图364.2早期的存储管理解决程序的可再定位（浮动）问题的方法：使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始执行。缺点花费较多的处理机时间；如果程序已经执行了一段时间，必须从头开始，否则将引起混乱。动态再定位技术。当一个作业装入与其地址空间不一致的存储空间时，可在访问指令或数据时，通过再定位寄存器（或称浮动寄存器）来自动修改访问存储器的地址。因此，一个作业再主存中移动后，只需要改变再定位寄存器的内容即可。374.2早期的存储管理

可再定位分区分配算法和固定式（或可变式）分区分配算法基本相同。问题是何时进行靠拢，一般有两种时机的选择当某个分区内的作业一完成，就立即靠拢。这样的靠拢操作是比较频繁的，由于实施程序的移动要花费较多的处理机时间，因此应尽可能减少靠拢操作的次数；在为某一作业请求一个分区时，当时内存没有足够大的空白区，但各空白区之和可以满足该作业存储要求，此时须进行靠拢操作。这样的靠拢次数要少得多，从而可以节省处理机时间。384.2早期的存储管理分配算法流程图请求分配一个大小为xKB的分区有大于xKB的空白区吗？空白区的总和≥xKB执行靠拢操作并修改状态表此时无法分配返回一个分区号分配一个分区并修改状态表NNYY394.2早期的存储管理4.多重分区分配

通常一个作业由一些相对独立的程序段和数据段组成，如主程序、子程序、数据组等。这些程序段中的每一个在逻辑上必须是连续的，但是相应的各分区不要求是连续的。采用多重分区分配方案，作业可以在其执行期间申请附加的分区。优点：可使存储空间的利用率提高。缺点：作业分段越多，分区越小，存储器过碎，造成没有较大的空白区；实现多重分区要求更多的硬件支持，管理也比较复杂。404.2早期的存储管理5.分区的保护措施

存储保护是为了防止一个作业有意或无意的破坏操作系统或其他作业。通常采用界限寄存器或者存储保护键两种方法。界限寄存器定位寄存器和界限寄存器：利用定位寄存器的值（=存储空间首址减去地址空间首址的值)，和界限寄存器的值进行存储访问检查(界限寄存器的值存放作业地址空 间的大小）。上下限寄存器。每次访主存时,其地址值与上限寄存器值(物理地址的最高地址)和下限寄存器值(最低物理地址)比较：若大于上限或小于下限时则中断访问主存。414.2早期的存储管理下界寄存器60KB基址寄存器60KB限长寄存器64KB上界寄存器124KB060KB作业2的分区124KB256KB060KB作业2的分区124KB256KB上下界寄存器进行存储保护基址寄存器进行存储保护424.2早期的存储管理存储保护键将主存静态分成若干块，一般是等分为1k~2k大小分块；每块都指定一个单独的保护键，保护键由保护字和保护方式组成：保护方式分为写保护、读写保护两种，而保护字由一组代码组成；每个作业赋于一个不同代码并存入该作业的程序状态字中，访问主存时用此代码(钥匙)与保护键进行匹配检查；先进行保护方式检查，若是写保护，则对一切读指令都不进行匹配检查允许访问主存，但对写指令必须进行匹配检查；若是读写保护，则对任何指令都进行匹配检查。匹配检查是用作业代码钥匙与主存的代码锁相比较，若相同则允许访问主存，否则作为访问主存出错被中断；一般系统都将操作系统的程序状态字(PSW)钥匙置为0，它具有万能钥匙之功效——可访问任一主存块。434.2早期的存储管理444.2早期的存储管理6.分区分配方案的评价优点对多道程序设计，实现了存储的共享，更有效地使用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相应的改善；高了主存利用率，可变式分区高于固定式分区，可定位式分区更高；实现存储保护的措施比较简单；多重分区分配方案能实现对子数据、程序段的共享。454.2早期的存储管理缺点：主存仍不能充分利用，存在严重碎片问题(可重定位分区分配除外)；不能实现对主存的扩充，作业大小受到主存可用空间的限制；和单一连续分配一样，要求一个作业在执行之间必须全部装入内存，因此在主存中可能包含从未使用过的信息。采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本。464.3分页存储管理

可再定位（即浮动）式分区分配技术，使用这种分配技术可以消除碎片，使一些零散的空白区汇合成较大的连续的空白区，提高主存的利用率。但是，各作业分区的靠拢花费了较多的处理机时间，并不可取。这是由于我们提出了每个作业占有的存储空间必须是连续的。避开这一要求，就引进了分页存储管理技术。474.3分页存储管理4.3.1分页原理

用户作业地址空间起点与分区的物理位置无关，所以作业的地址空间通常从0开始。分页存储管理就是从逻辑地址空间到物理地址空间的一种变换，即f：L→S，其中，L、S分别表示逻辑地址空间和物理地址空间。页框（物理块）：将主存按2n划成位置固定，长度相等的块，称为页框（pageframe）或物理页。如1KB，PC机为4KB一页。对页框进行统一编号0，1，2，……，n-1，称为块号（页框号﹑页架号﹑物理页号﹑绝对页号）；页框是分配内存的基本单位。484.3分页存储管理页面(页)：作业的虚拟地址空间也按同样长度分成页面(虚页，虚拟页面)，对其统一编号0，1，2…，m-1，称为页面号(虚页号﹑逻辑页号﹑相对页号)。一个作业的逻辑地址空间的所有页面是邻接的，而变换到物理存储空间的各块可以不邻接。逻辑地址空间和物理地址 空间的对应关系由称为页 面变换表的PMT指出，

PMT也简称为页表。虚页号页框号0317218…………页表（PAGETABLE）494.3分页存储管理在分页存储管理方式中，系统以页框为单位把主存分给进程，并且每个进程分给的各页框不一定相邻和连续。页表的作用是实现从页号到物理块号的地址映射。每一个进程对应一张页表，一个页表表项的数目等于其所记录的进程逻辑地址空间的页面数。CPU中设立一个页表地址寄存器。例作业A的地址空间为11KB，按4KB分页，分为0，1，2页。504.3分页存储管理作业101KB2KB作业201KB2KB3KB作业301KB操作系统作业2（0页）作业2（1页）作业1（0页）作业1（1页）作业2（2页）作业3（0页）物理地址空间页号块号051601KB2KB3KB4KB5KB6KB7KB8KB9KB10KB02142708页面变换表逻辑地址空间514.3分页存储管理L1，2KB＋6001557100作业2的地址空间05181KB2KB2KB＋60L1，2KB＋6001557100存储空间2KB3KB4KB5KB6KB7KB7KB＋608KB021427页面变换表页面变换表保证了作业的正确执行524.3分页存储管理4.3.2地址变换机构1.动态地址变换机构DAT

考察计算机系统指令LR1，D2（X2，B2），其中，X2、B2、D2为第二操作数域使用的变址寄存器、基址寄存器和位移量，R1是第一操作数域的通用寄存器。指令格式为图LR1X2B2D207811121516192031534.3分页存储管理

指令的第二操作数的有效地址为E2＝（X2）＋（B2）＋D2，该指令的有效地址占24位。因此，逻辑地址空间最大可达224＝16MB。假定页面大小为4KB，于是逻辑地址空间可达4096个页面，每个页面4096个字节。24位有效地址自然地被划分为两部分，前12位为页号，后12位为页内地址。页号页内地址078192031544.3分页存储管理

动态地址变换机构自动地将所有地址划分为页号和页内地址两部分。利用PMT表将页号代之以块号，得到要使用的物理存储地址。LR1，D2（X2，B2）LR1X2B2D2（7）000000000111（144）000010010000有效地址（2）000000000000（144）000010010000页号页内地址页号块号011427……255页面变换表554.3分页存储管理

每个作业都有一个页面变换表，通常各作业的页面变换表放在操作系统的一个工作区中，由页面变换地址寄存器（PMTAR）指出作业的页面变换表的起始地址。当处理机执行一个新作业或恢复一个旧作业时，只要修改PMTAR的内容，使之指向要执行作业的PMT起始地址即可。564.3分页存储管理PMTAR34160长度PMT起始地址0KB4KB8KB12KB0页1页2页作业2的地址空间4字节247作业2（0页）作业2（1页）作业2（2页）操作系统用04KB块2块4块74160PMTAR、PMT、页面和块之间的关系574.3分页存储管理2.高速页面变换寄存器

为了实现从作业地址空间到物理地址空间变换，可采用硬件的高速寄存器来实现。3.联想存储器

页面变换表存放在主存，由操作系统实施管理，在作业执行时，每条指令的执行都必须进行地址变换。每条指令必须两次访问存储器：一次把页号变成物理块号，一次进行实际存取所要的数据或指令，增加了指令执行的机器时间，影响了计算机的速度。

采用高速寄存器方法，如果作业地址空间较大，所需存储器较多，花费较高。584.3分页存储管理

因此采用一种折衷办法来解决这一矛盾，即把高速寄存器作为DAT的辅助机构来实行地址变换。这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为联想存储器，也称快表。在联想存储器中，存放正运行作业当前最常用的页号和相应块号，具有并行查询能力。594.3分页存储管理有效地址PW页号P块号B…BW物理地址输入寄存器输出寄存器604.3分页存储管理

在采用联想存储器的系统中，通常采用“双管齐下”的方针，既按给出的页号检索联想存储器中的相应块号，同时按PMT表进行查找块号，同时进行。如果在联想存储器中，检索到所要块号，立即停止PMT表的查找，利用联想存储器给出的块号访问主存。如果联想存储器检索不到需要的块号，将PMT表查找到的页号以及所对应的块号填入联想寄存器内的空白单元中，如没有空白单元，根据某种规则淘汰一个单元内容后填入。614.3分页存储管理例设CPU访问内存要200ns，访问快表一次要40ns，命中率为90%，求一次访问内存的平均时间是多少？比慢表访问下降了多少？解访问内存的平均时间为：（40+200)*0.9+(200+200)*0.1=216+40=256（ns）不用快表，每取一指令或数据要用

400ns，则（400-256）/400=36%624.3分页存储管理例CPU访问慢表为100ns，访问快表为20ns，希望把进行一次访问内存存取指令的或数据的时间控制在140ns，求此时快表的命中率。解设命中率为X，列方程：（100+20）*X+（100+100）*（1-X）=14080X=60X=75%所以，命中率至少要75%。634.3分页存储管理4.3.3分页存储管理算法

为实现分页储存管理，在软件方面应建立如下表格，并由操作系统实施管理。作业表（JT）。整个系统一张表。每个作业在作业表中对应一个表目，包括该作业的页表地址、页表长度和状态信息。当作业调度程序调度到某个作业时，如果存储要求可以得到满足，就在此表上进行登记。当作业轮到处理时，就从此表把页表始址和页表长度送到控制寄存器中。644.3分页存储管理存储分块表（MBT）。整个系统一张表。该表中每一表目对应一个存储块，记录了该块的状态：已分配或空闲。页面变换表（PMT）。每个作业一张表。页面变换表，用于该作业的地址变换，该作业有多少页面就有多少表目，表目内记录对应的存储块号。654.3分页存储管理作业表作业号页表长度PMT始址状态123600已分配234160已分配313820已分配4－－空项块号563600作业1的PMT块号2474160作业2的PMT块号83820作业3的PMT块号状态0OS1OS2作业23可用4作业25作业16作业17作业28作业39可用存储分块表MBT664.3分页存储管理请求分配xKB的地址空间计算所需块数NN＝[xKB/4KB]有N个可用的块？本次无法分配在作业表中找空表目置页表长度＝N，状态＝已分配分配该作业的PMT表，并在作业表中登记该PMT的始址检查内存分块表，分配N个可用存储块，在每块的状态栏内填入作业序号，再将存储块号填入PMT表返回分页存储分配算法流程图674.3分页存储管理4.3.4分页存储管理方案的评价分页存储管理方案不必像浮动分区法那样执行费时的靠拢操作，消除了碎片，便于多道程序设计，提高了处理机和主存的利用率。缺点：采用动态地址变换会增加计算机成本和降低处理机的速度；各种表格要占用一定容量的主存空间，而且还要花费一部分处理机时间用来建立和管理这些表格；碎片虽然消除，但每个作业的最后一页一般不能充分利用。存储扩充问题仍然没有解决。684.4请求分页存储管理4.4.1请求分页原理基本原理将作业的地址空间按同等大小划分成页面（虚页），将主存空间划分成同样大小的页框（实页）；将页面不是全部装入主存，而是装入一部分。作业运行时，至少装入一个页面；每次访问的页面如果不在主存中，就从辅存中调入主存。694.4请求分页存储管理请求分页存储中，必须解决几个问题：1.如果一个作业不把它的整个地址空间同时全部装入主存，那么该作业是否能开始运行并运行一段时间？2.在作业运行一段时间后，必然要访问到没有装入的页面，也就是说，要访问的虚页不在实存。那么，这个问题系统是怎样发现的？3.如果系统已经发现某虚页不在实存，就应将其装入实存。问题是从何处装入，装入到何处，如果实存空间已满怎么办？704.4请求分页存储管理1.一个作业的地址空间不同时全部装入主存时，这个作业可以开始运行不能运行一段时间，因为作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分；程序的局部性：顺序执行的指令和线性结构的数据（如数组），它们通常被限定在某一连续区域。一旦某一位置被访问后，那么它附近的位置很快也会被访问。作业被调度投入运行前，通常只装入其虚页0到实存，作业所需其它各页，根据请求而被装入，这就保证了一个作业在运行前可以不必装入该作业的全部地址空间。714.4请求分页存储管理2.在PMT中增加一个状态位，规定该位为0表示该页已装入主存，该位为1表示该页不在主存，当地址变换机构检测到虚页的状态位为1时，表示该页不在主存，规定由硬件产生缺页中断，转入中断处理程序，虽然这不是用户程序的错误，但它是属于程序中断。724.4请求分页存储管理作业101KB作业201KB2KB作业300块1块2块L1，1KB＋αA1，2KB＋β3块4块5块6块7块8块006802009块存储空间块号状态506001KB2KB3KB4KB5KB6KB7KB8KB9KB204070803090－1－1页面变换表地址空间L1，1KB＋αA1，2KB＋β0068020000615100作业401001041KB1KB＋α2KB2KB＋β3KB734.4请求分页存储管理3.当发现虚页不在实存时，引起缺页中断，利用中断处理程序完成该页的装入。中断处理程序把所需页面装入实存后，修改PMT的状态位，然后重新执行该指令。

将某一页从实存移到辅存称为“出页”，从辅存调入实存称为“入页”，入页和出页的操作称为“分页”操作。在请求分页系统中，从实存中刚刚移走某个页面后，根据请求马上又调入该页，这种反复进行入页和出页的现象称为“抖动”，也叫做系统颠簸。它浪费了大量的处理机时间，所以应尽可能避免“抖动”的发生。744.4请求分页存储管理执行一条指令形成有效地址计算页号该页在实存吗？取数据完成该指令取下一条指令缺页中断入口有空闲的实页吗？取出保存的页号找出磁盘地址入页修改PMTMBT表重新执行被中断的指令出页修改PMTMBTC=1?复制到辅存硬件软件YYYNNN754.4请求分页存储管理4.4.2页面置换算法

通常一个置换算法的效能与作业运行过程中访问地址空间的变化规律密切相关，而这个规律难以预测。因此，人们对不同类型的作业，从不同角度，提出了许多不同的置换算法。1.先进先出算法（First-inFirst-out，FIFO）先进先出算法的基本思想是：总是淘汰那些驻留在主存时间最长的页面，即先到主存的页面先被淘汰。理由是：最早调入主存的页面，其不再被访问的可能性最大，这种算法实现起来比较简单。该算法只是在按线性顺序访问地址空间的情况下才是理想的，否则效率不高。764.4请求分页存储管理块号页号指针01246342∧56577142替换指针（指向最老的页）块号页号指针0126∧342256577146替换指针（指向最老的页）774.4请求分页存储管理2.最近最久未用置换算法（LRU）基本思想：如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很久没有被访问，那么最近也不再会被访问。这种思想来源于程序设计的局部化程度。实质是，当需要置换一页时，选择在最近一段时间最久未用的也予以淘汰。实现这种技术，是通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页。最近最久未用置换算法简称LRU（LeastRecentlyUsed）算法，它能够比较普遍地适用于各类类型的程序，但是实现起来比较困难。784.4请求分页存储管理3.LRU近似算法需要在存储分块表MBT（或页表PMT）中设一“引用位”，当存储分块表中的页被访问时，该位由硬件自动置“1”，而由页面管理软件周期地（设周期为T）把所有应用位置“0”。这种算法比较简单，易于实现。缺点是：周期T的大小不易确定。另外，如果缺页中断刚好发生在系统对所有引用位重置“0”之后，则几乎所有块的引用位为“0”，因此也有可能把常用的页淘汰出去。794.4请求分页存储管理入口替换指针前进一步指向下一存储块其引用位＝0？选择该页淘汰返回置引用位＝0LRU近似算法的流程804.4请求分页存储管理块号页号引用位指针0124034215650711替换指针块号页号引用位指针01240342056517116替换指针LRU近似算法例814.4请求分页存储管理4.第二次机会页面替换算法思想：为了避免FIFO可能会把经常使用的页替换出去的问题，我们可以对它做一个简单的修改，对最老页面的R位进行检查。如果R位是0,那么这个页既老又没用，应该被立刻替换掉；如果是1,就清除这个位，把这个页放到页链表的尾端，修改它的装入时间让它就像刚装入的一样，然后继续搜索。824.4请求分页存储管理A0B3C7D8E12F14G15H18第一个装入的页最近装入的页（a）页面按先进先出的顺序排列A0BC7D8E12F14G15H18A被像新装入的页面一样对待（b）在时间20发生页面故障并且A的R位已经设置时的页面链20第二次机会页面替换算法834.4请求分页存储管理5.时钟页面替换算法（CLC算法）把所有的页面保存在一个类似钟表表面的环形链表中，有一个表针指向最老的页面。在发生缺页中断时，该算法首先检查表针指向的页面，如果它的R位是0就淘汰掉这个页， 并把新页插入这个位置， 然后把表针前移一个位置； 如果R位是1就清除R位并把 表针前移一个位置，重复这 个过程直到找到一个R位为

0的页为止。ABCDEFGHIJKL时钟页面替换算法844.4请求分页存储管理4.4.3性能分析

请求分页存储管理方案消除了对主存实际容量的限制，能使更多的作业按多道同时执行，从而提高了系统效率。由于页面的调入、调出要增加I/O的负担，而且影响系统的效率。早期的计算机系统中，为扩充主存的容量，采用请求分页存储管理方案实现虚拟存储系统，尽管要增加系统开销，也是必要的。但是，在今天硬件成本急剧下降，存储技术不断进步的形势下，是否仍采用请求分页存储管理是一个值得讨论的问题。854.4请求分页存储管理

为尽可能地减少缺页中断的次数，应从程序设计的质量，页面的大小，主存的容量以及页面置换算法等几方面考虑。程序设计的质量主要指程序局部化程度。包括时间局部化和空间局部化。时间局部化是指一旦某个位置（数据或指令）被访问了，它常常很快又要再次被访问。可通过循环、经常用到的变量和子程序等程序结构来实现。空间局部化是指一旦某个位置被访问到，那么它附近的位置很快也要用到。可通过尽量采用顺序的指令列、线性的数据结构来实现。设计请求分页存储系统，页面大小也是重要参数。864.4请求分页存储管理提供虚拟存储系统之后，每个作业只要分到一块主存空间就可以执行了。从表面上看，这增加了可同时运行的作业数，但实际上是低效的。一个作业的执行所产生的缺页中断的次数是存放页面的实际存储容量的函数。当主存容量增加时，缺页中断次数减少，到一定程度后，中断减少次数不明显。试验分析表明：对所有程序来说，要使其有效地工作，它在主存中的页面数应不低于它的总页面数的一半。

P121图4.26存储容量与缺页中断次数的关系874.4请求分页存储管理现在讨论运行的程序和页面置换算法的关系。例设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，置换算法采用FIFO。

P行表示页面走向，M行表示主存页面号，标“＋”表示新调入页面，加圆圈表示下一时刻被淘汰，F行表示是否引起缺页中断。缺页次数F=9，缺页率f=9/12=75%。时刻123456789101112P432143543215M4＋3＋2＋1＋4＋3＋5＋552＋1＋143214333522④③②①44④③55F＋＋＋＋＋＋＋＋＋884.4请求分页存储管理例设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=4，置换算法采用FIFO。

P行表示页面走向，M行表示主存页面号，标“＋”表示新调入页面，加圆圈表示下一时刻被淘汰，F行表示是否引起缺页中断。缺页次数F=10，缺页率f=10/12=83%。时刻123456789101112P432143543215M4＋3＋2＋1＋1＋15＋4＋3＋2＋1＋5＋43222154321433321543244④③②①⑤④3F＋＋＋＋＋＋＋＋＋＋894.4请求分页存储管理例设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，置换算法采用LRU。

P行表示页面走向，M行表示主存页面号，标“＋”表示新调入页面，加圆圈表示下一时刻被淘汰，F行表示是否引起缺页中断。缺页次数F=10，缺页率f=10/12=83%。时刻123456789101112P432143543215M4＋3＋2＋1＋4＋3＋5＋432＋1＋5＋43214354321④③②①43⑤④③2F＋＋＋＋＋＋＋＋＋＋904.4请求分页存储管理例设页面走向为P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=4，置换算法采用LRU。

P行表示页面走向，M行表示主存页面号，标“＋”表示新调入页面，加圆圈表示下一时刻被淘汰，F行表示是否引起缺页中断。缺页次数F=8，缺页率f=8/12=67%。时刻123456789101112P432143543215M4＋3＋2＋1＋435＋432＋1＋5＋43214354321432143543243②11①⑤④3F＋＋＋＋＋＋＋＋914.4请求分页存储管理4.4.4请求分页存储管理方案的评价

请求分页存储管理保留了分页存储管理的全部优点，特别是它解决了消除碎片的问题。优点提供了大容量的多个虚拟存储器，作业地址空间不再受实存容量的限制；更有效地利用了主存，一个作业的地址空间不必全部同时都装入主存，只装入其必要部分，其它部分根据请求装入，或者根本就不装入（错误处理程序等）；更加有利于多道程序的设计，从而提高了系统效率。方便了用户，特别是大作业用户。924.4请求分页存储管理缺点：为处理缺页中断，增加了处理机时间的开销，即请求分页系统是用时间的代价换取了空间的扩大；可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动；为防止系统抖动所采取的各种措施会增加系统的复杂性。934.5分段存储管理

对于模块化程序和变化的数据结构的处理，以及不同作业之间对某些公共子程序或数据块的共享等问题的解决，都存在着较大的困难。程序人员一般都希望把信息按内容和逻辑关系分成段，每个段都有自己的名字，且可以根据名字来访问相应的程序段或数据段。944.5分段存储管理4.5.1分段原理

[MAIN]=0L1，[A]|6ST，[B]|<C>[X]=3[A]=5[B]=6C:虚存空间0160034001000600160E04000123340E0346045100R03800660R/W1－SMT容量存取权限状态始址OS[X][A][MAIN]实存空间346038004000954.5分段存储管理

在分段存储管理系统中，可以用类似于分页管理用过的地址变换机构，实现分段管理的地址变换。使用的是段变换表SMT，它把作业地址空间变换为物理存储空间，作业地址空间的段与主存中的段大小相等。地址变换是在作业执行过程中由硬件自动完成的。964.5分段存储管理段号段内地址SB请求访问S段中的B单元段S在实存吗？B≤S段容量在访问权限之内？置访问位为1。若为写访问，则置改变位为1求段的始址L，加上段内地址B，便得实存地址A＝L＋B返回访问地址保护中断越界中断缺段中断由处理机产生由分段管理机构实现974.5分段存储管理4.5.2段变换表作业的地址空间被划分成若干段，每个段定义一个完整逻辑信息，从0开始编址；分页的作业是单一线性地址空间，分段作业的地址空间就是二维的，由“段名，段内地址”两个部份组成；“页”是信息的物理单位；“段”是信息的逻辑单位。从形状来说，页面大小固定，段的长度却不定；984.5分段存储管理从透明度上看，页面对于用户是不可知的，它仅仅用于对主存的管理，分段则对用户是可见的，分段可在编程或编译时即已确定和划分；分页管理实现单段式虚拟存储系统，而分段存储管理实现多段式虚拟存储系统。指令和数据的单元地址均由两部分构成；一是表示段名的段号S，一是段内位移量W，即段内地址。段与段之间不再连续。段号S段内地址W078151631994.5分段存储管理地址转换过程由控制寄存器找出正在运行作业的段表首址；利用有效地址中段号2作为进入段表的索引，得到该段在主存中的首址6K；根据段内位移W与段长比较结果，判断是否有越界，若有产生越界中断；取段保护方式检查指令是否符合存取方式,若不符合产生保护中断；将段内位移量W=100与段首址6K相加得出主存的物理地址6244；按物理地址6244访问。1004.5分段存储管理地址转换过程如图所示：1014.5分段存储管理4.5.3分段存储管理方案的评价优点消除了碎片。通过靠拢可移动任何段的位置（修改SMT表的起始地址），从而可将零散的空白区合并成一个较大的空白区，用于装入某一较大的段；提供了大容量的虚存。允许动态增加段的长度，容易处理变化的数据结构便于动态装入和链接。当两个或两个以上的作业要使用同一子程序时，在实存上就要有两个或两个以上的程序副本，造成浪费。通过分段管理和动态连接，可以做到几个作业共享一个程序。便于实现存储保护。1024.5分段存储管理[MAIN1][DATA1][SQRT]作业1[MAIN2]

[DATA2][SQRT]作业20123作业1的SMT01234作业2的SMTOS[MAIN1][DATA1][SQRT][MAIN2][DATA2]实存两个作业对SQRT的共享1034.5分段存储管理缺点进行地址变换和实现靠拢操作要花费处理机时间，为管理各分段，要设立若干表格，提供附加的存储空间；在辅存上管理可变长度的段比较困难；段的最大长度受到实存容量的限制；会出现系统抖动现象。1044.6段页式存储管理

用分段方法来分配和管理虚存：用分页方法来分配和管理实存。在段页管理系统中，每一段不再占有连续的实存空间，而被划分为若干个页面。段页存储管理实际上是对页面进行分配和管理的，因此有关段的靠拢、辅存管理以及段长限制等问题都得到很好的解决。而分段的优点，如允许动态扩大段长，分段的动态链接，段的共享，段的保护措施等却被保留下来。这一存储管理技术在大、中型计算机中已获得了广泛的应用。1054.6段页式存储管理4.6.1段页式存储管理的实现一、实现原理1.一个作业的地址空间被分成若干段，每段又被分成若干固定大小的页面；2.段末部分未占满一页的也算一页，如图所示，这就解决了外零头问题；1064.6段页式存储管理3.段页式地址结构是由段号S、页号P、页内地址W三部分组成。这种地址结构如下图所示；4.段号长度ns,确定了作业的最大段数2ns；页号P的占位数np确定了每个分段的最大页数为2np，而段内位移W的占位数nw确定了每页的最大容量2nw；例IBM370系统中，最多有256段（ns=8），每个分段最多16页（np=4）,每页最大4K（nW=12）。段号S页号P页内地址W07815161920311074.6段页式存储管理5.系统为每一个作业建立了一张段表，并为每个段建立了一张页表，段表的地址部分指向相应页表的首址。控制寄存器段表长度段表地址段号状态页表长度页表地址00L011·21·30L3段表页号状态实存页号00102030L000102030L3页表…OS实存1084.6段页式存储管理二、段页式的地址转换过程

1.由控制寄存器中查出段表起始址；2.根据段表首址及虚地址中段号S查段表,并根据段描述符知相应段信息；3.若段不在主存产生缺段中断；4.若操作不符存取方式，产生违例中断；5