操作系统原理：第04章 存储器管理

2022/11/19第四章存储器管理第四章

存储器管理4.1存储器的层次结构4.2程序的装入和链接 4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式今天虽然主存价格已相当便宜，但主存容量仍然是计算机四大硬件资源中最关键的资源。因此对主存的管理和有效使用仍然是今天操作系统十分重要的内容。许多操作系统之间最明显的区别特征之一往往是所使用的存储管理方法不同。第四章

存储器管理存储管理功能存储分配回收存储共享存储保护存储扩充地址映射分配回收对象内存、外存(相同方法)分配回收时刻进程创建、撤销、交换、长度变化目的：节省内存、相互通信内容：代码、数据防止地址越界防止操作越权内存、外存结合，虚拟存储体系速度接近内存，容量相当外存逻辑地址=>物理地址硬件支持基址寄存器(base)、限长寄存器(limit)、快表；4.1存储器的层次结构4.1.1多级存储器结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等。存储空间的分类与性质4.1.1多级存储器结构4.1.2主存储器与寄存器1.主存储器寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器用于加速存储器的访问速度。用于保存进程运行时的程序和数据，也称可执行存储器。CPU的控制部件只能从主存储器中取得指令和数据。2.寄存器4.1.3高速缓存和磁盘缓存1．高速缓存容量大于或远大于寄存器，而比内存约小两到三个数量级左右。将主存中一些经常访问的信息存放在高速缓存中,可大幅度提高程序执行速度。2．磁盘缓存磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。4.2程序的装入和链接用户源程序变为一个可在内存中执行的程序.3.装入由装入程序将装入模块装入内存。1.编译由编译程序源代码编译成若干个目标模块2.链接由链接程序将目标模块和它们所需要的库函数链接在一起，形成一个完整的装入模块4.2程序的装入和链接……链接程序装入模块装入程序第一步第二步第三步编译程序产生的目标模块库地址空间程序的名空间用户编程所用的地址称为逻辑地址（或程序地址，或虚地址）。由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。地址映射LoadA2003456

。。物理地址空间LoadAdata1data13456名空间LoadA2003456编译连接逻辑地址空间

源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据——单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。地址空间地址映射LoadA2003456

。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000

把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。4.2.1程序的装入将一个模块装入内存时，可采用三种方式：绝对装入方式重定位装入方式

动态运行时装入方式

在多道程序环境下，要使程序运行，必须为之先建立进程。创建进程的第一件事是将程序和数据装入内存。如果在编译时知道程序驻留在主存的具体位置,则编译程序将产生物理地址的目标代码.模块装入后,由于程序中的逻辑地址与实际主存的地址完全相同,故不需要对程序和数据的地址进行修改.1绝对装入方式绝对装入方式只能将目标模块装入到主存事先指定的固定位置,只适用于单道程序环境.MoveAX,[2500]543212000210025003000绝对装入方式编译时产生的绝对地址MoveAX,[2500]5432120002100250030000内存空间FFFF重定位（Relocation）★重定位：在一般情况下，一个作业在装入时分配到的存储空间和它的地址空间是不一致的。由于不一致所引起的对有关地址部分的调整过程，就是我们所说的地址重定位。静态重定位动态重定位在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址都是相对于起始地址计算的。因此应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。静态重定位:是在装入时由装配程序一次性完成的，以后不再改变.物理地址=逻辑地址+程序在内存的首地址优点：无需硬件支持，容易实现。缺点：

1.程序经地址重定位后不能再移动了；

2.程序在内存空间只能连续存储；2可重定位装入方式LoadBX,032543210832124LoadBX,13254321100108132244内存空间FFFF装入程序静态重定位逻辑地址空间3．动态运行时装入方式程序执行过程中，当访问指令或数据时，才进行的地址变换方法，称为动态重定位。靠硬件地址变换机构实现的。基地址寄存器和一个地址转换线路组成物理地址=逻辑地址+基址寄存器优点：可对内存进行非连续分配；提供了实现虚存的基础；有利于程序段的共享。LoadBX,032543210832124

LoadBX,03254321100108132244内存空间FFFF装入程序作业的装入CPU+逻辑地址032100基地址寄存器物理地址LoadBX,03254321100108132244内存空间FFFF地址转换动态重定位1324.2.2程序的链接根据链接时间的不同，可把链接分成如下三种：(1)静态链接。(2)装入时动态链接。(3)运行时动态链接。1静态链接方式在程序运行之前，先将各个目标模块及他们所需的库函数，链接成一个完整的装入模块，运行时直接装入内存。这种事先进行链接，以后不再拆开的链接方式称之静态链接。需要解决两个问题此时必须修改被调用模块的逻辑地址。同时转变模块中使用的外部调用符号。模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块2.装入时动态链接将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。优点:(1)便于修改和更新(2)便于对目标模块的共享3.运行时动态链接指某些目标模块，当在程序执行中需要该模块时，才对它进行的链接。在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅加快了程序的装入过程，而且可节省大量的内存空间。4.3连续分配方式把主存中的用户区作为一个连续区域或者分成若干个连续区域进行管理。可分为：单道连续分配固定分区分配动态分区分配动态重定位分区分配4.3.1单一连续分配内存分为系统区和用户区；操作系统占用系统区,其余的主存空间分配给一个用户程序使用。特点：管理简单，主存利用率低，不支持多道，程序的运行受主存容量限制。在任何时刻主存中最多只存有一个作业。4.3.2固定分区分配将内存划分成若干个连续区域，称为分区。每个分区的大小可以相同也可以不同，每个分区只能存储一个程序。(1)分区大小相等。即使所有的内存分区大小相等。其缺点是缺乏灵活性。(2)分区大小不等。把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。2．内存分配数据结构：分区使用表为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的分区号、起始地址、大小及状态(是否已分配)。区号大小(KB)起址(KB)状态18K20K已分配232K28K已分配364K60K已分配4132K124K未分配OS20K28K60K124K256K进程A（6K）（a）分区说明表 （b）存储空间分配情况图固定分区使用表进程B（25K）进程C（36K）2．内存分配固定分区分配算法流程图要求xk大小的分区取分区说明表的第一项该分区空闲吗？分区大小xk表结束吗？返回分区号状态位置1无法分配取下一项NNNYYY固定分区分配存储保护：两种方法提供上、下界寄存器和地址检查机构。基址寄存器、长度寄存器和动态地址转换机构。固定分区分配优点：易于实现，开销小。可放多道程序缺点：存在零头（即存在碎片）。分区总数固定，限制了并发执行的程序数目。4.3.3动态分区分配工作原理存储空间的划分是在装入作业时进行的，根据作业的需求和内存空间的使用情况来决定是否分配。且使分区大小正好适应作业的需要。数据结构空闲分区表：序号，大小，起址，状态空闲分区链：在每个分区中附上一个表格信息，状态（0，1），大小，指针（空白分区才有）1．分区分配中的数据结构图空闲链结构前向指针N个字节可用后向指针N+2N+20（分配标识）00K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表：图分区分配表0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K

2．分区分配算法常用的分区分配算法有以下几种：首次适应算法循环首次适应算法最佳适应算法最坏适应算法快速适应算法4.分配算法1)首次适应算法算法思想按分区先后次序，从头查找，找到符合要求的第一个分区。尽可能利用存储区低地址空闲区，尽量在高地址部分保存较大空闲区，以便一旦有分配大空闲区要求时，容易得到满足。算法实质1）首次适应算法1）首次适应算法

切割空闲区有两种方法：从空闲区头开始从空闲区尾开始空闲区大小50KB，首址156KB，申请34KB。从该空闲区中截取所需大小，修改调整可用表从空闲区表第一表目顺序查找从可用表中移去该表目，调整可用表取下一表项无法分配该空闲区长度≥SIZE？该空闲区长度=SIZE？表目查完？返回分配起始地址否否否是是是首次适应算法1）首次适应算法指针10k60k90k20k有四块空闲区(从低地址高地址)，来了一个作业需分配19k内存。例：1）首次适应算法指针10k60k90k20k41k在高地址空闲区中保持较大空闲区(每次从10k开始分配寻找)。1）首次适应算法优点分配简单，合并相邻空闲区也比较容易缺点查找总是从表首开始，前面空闲区往往被分割的很小时，满足分配要求的可能性较小，查找次数较多。针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。2)循环首次适应算法(nextfit)算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。算法思想算法特点按分区先后次序，从上次分配的分区起查找(到最后分区时再回到开头)，找到符合要求的第一个分区。12指针移动2)循环首次适应算法(nextfit)3)最佳适应算法算法思想

空闲存储区管理表采用从小到大的顺序结构在所有大于或者等于要求分配长度的空闲区中挑选一个最小的分区，即对该分区所要求分配的大小来说，是最合适的。分配后，所剩余的块会最小。算法实现3)最佳适应算法3)最佳适应算法优点

这种算法最大的缺点是分割后的空闲区将会很小，直至无法使用，而造成浪费。缺点

较大的空闲分区可以被保留示例指针10k20k60k90k来一个19k的作业指针10k20k60k90k1k4)最坏适应算法算法思想

空闲区按由大到小排序分配时选取所有空闲区中最大的一块，把剩余的块再变成一个新的空闲区。其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。算法实现4)最坏适应算法示例指针90k60k20k10k71k指针90k60k20k10k来一个19k的作业4)最坏适应算法优点分配时，产生的空白区可供以后使用。只需查找一次，就可成功，分配算法很快。缺点最后剩余分区会越来越小，无法运行大程序5）快速适应算法算法思想

对于每一类具有相同容量的所有空闲分区，设立一个空闲分区链表。再设立一张管理索引表，该表的每一个表项对应了一个空闲分区链表。

是将空闲分区根据其容量大小进行分类，在进行内存分配的时候，不需要对分区进行切割。算法实现5）快速适应算法该算法的优点：查找效率高。不会对任何分区分割，能保留大的分区。也不会产生内存碎片。该算法的缺点：在分区归还主存时算法复杂，系统开销较大。一个分区只属于一个进程，存在空间浪费。3．分区分配操作1)分配内存设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size-u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。从头开始查表检索完否？m.Size>u.size?m.size-u.size<=size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN

2)回收内存当进程运行完毕释放内存时,可能出现以下四种情况之一：(1)回收区与前一个空闲分区相邻。(2)回收分区与后一空闲分区相邻。(3)回收区同时与前、后两个分区邻。(4)回收区前后都不邻空闲区。图内存回收时的情况4.3.4伙伴系统固定分区和动态分区方式都有不足之处。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。当把一个存储块分为大小相等的两半时，则它们互为伙伴。[大小为2k的伙伴的首地址之间的关系](0)0000(8)100000000100100011002323222222222121000000104.3.4伙伴系统标志位：

tag=1占用块

0空闲块202k2m0km0k0knodesizefirst按k值索引，相同k值的块构成子表(双链表)4.3.4伙伴系统

分配算法1)计算k值：k=log2n2)从子表k开始找可用的块

2.1)k子表有，取出分配，结束；

2.2)否则，若从k向下找到i(i>k)子表有可用块

(起始地址为p)，则取出2k分配，剩余的块大小2i-12i-2......2k

起始地址p+2i-1p+2i-2......p+2k

插入相应的子表。p2i分配2k2i-12i-2回收时，只有伙伴才合并，并将合并后的新空闲块加入上一级大小的空闲块链表中。4.3.5哈希算法哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置。4.3.5哈希算法算法思想

构造一张以空闲分区大小为关键字的哈希表。根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置。利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，实现快速查找定位分区。算法实现

优点：便于动态申请内存便于共享内存便于动态链接缺点：碎片问题(外碎片)，内存利用率不高，受实际内存容量限制分区式存储管理的优缺点

碎片问题经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片造成存储资源的浪费碎片问题解决的方法：(I)将程序装入分散存储区中–––多重分区(II)将碎片集中(紧凑或拼接)–––动态重定位分区分配问题：开销大；移动时机4.3.6可重定位分区分配1．动态重定位的引入在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）如果在系统中只有若干个小的分区，它们容量的总和大于要装入的程序，怎么办？1．动态重定位的引入紧凑2．动态重定位的实现

作业装入内存后的所有地址都仍然是相对地址。将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。2．动态重定位的实现load1,2500365load1,25003650100250050002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址3.动态重定位分区分配算法动态重定位分区的优缺点优点:解决了可变分区分配所引入的“外零头”问题。消除内存碎片，提高内存利用率。缺点:提高硬件成本，紧凑时花费ＣＰＵ时间。1．对换(Swapping)的引入4.3.7对换对换：不能运行的进程调出到外存，程序、数据。具备运行条件的进程调入内存，程序和数据。对换是提高内存利用率的有效措施。1．对换实现：通过中级调度。分类：进程对换：以整个进程为单位；页/段对换：虚存管理技术；为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程的换出，以及进程的换入。对2、对换空间管理外存：是提高进程换入和换出的速度。为此，采取的是连续分配方式。分为文件区和对换区。对对换空间管理的主要目标：3．进程的换出与换入(1)进程的换出系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将之换入。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。(2)进程的换入3．进程的换出与换入(1)进程的换出(2)进程的换入4.4基本分页存储管理方式造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。分区存储管理的主要问题是碎片问题。4.4.1页面与页表--页面1)页面和物理块在分页系统中的页面其大小应适中。页面大小应是2的幂，通常为512B～8KB。页框(块f)：把主存空间划分成与页相同的片。

页面(页P)：把每个作业(进程)虚拟(逻辑)地址空间划分成若干大小相等的片.2)页面大小2．地址结构用户程序中的逻辑地址包括页号和页内地址（页内位移）

区分页号和页内地址的依椐是页的大小，页内地址占逻辑地址的低位部分，页号占逻辑地址的高位部分。分页地址中的地址结构如下：2．地址结构分页地址中的地址结构确定了主存储器的分页大小,也决定了页面大小.

页号P页内地址(偏移量)31 1211 0若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址d可按下式求得：

P=INT[A/L]d=[A]MODL例如：假定页面大小1024字节，虚地址共占用2个字节(16位)

页号页内地址（位移量）

PW1510902．地址结构2．地址结构3．页表页号块号021326为了能在内存中找到每个页面所对应的物理块，系统为每个进程建立了一张页面映象表，即页表页表的作用是实现从页号到物理块号的地址映射页表由页号和块号组成，指出逻辑地址中页号与主存中物理块号的对应关系3.页表0页1页2页3页4页5页n页021326384950123456789用户程序页表页号块号内存页表位于内存4.4.2地址变换机构通过硬件的地址转换机构实现从逻辑地址到物理地址的转换工作。地址转换机构的任务实际上是将逻辑地址中的页号转换成为主存中的物理块号。页表是硬件地址转换的依据。页式存储管理采用动态重定位方式装入方式。物理地址=块号*块长+页内地址1．基本的地址变换机构页表始址页表长度＋页号(3)页内地址页表寄存器逻辑地址>越界中断1b块号页表页号0123物理地址页号

块号

存取控制页描述符+如果页号>页表长度，则中断，否则继续.如果访问非法，则中断，否则继续。页号位移量虚拟地址

LA

块号位移量物理地址页表始址长度页表寄存器PTR页表

块号存取控制页表项页号

01

...块号位移量

1．基本的地址变换机构有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。虚地址3412P＝3412％2048＝1d＝3412mod2048

＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796虚地址7145P＝7145％2048＝3d＝7145mod2048

＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：112412．具有快表的地址变换机构执行一次访内操作至少要访问主存两次。增加一个具有并行查询功能的高速缓冲存储器，存放在高速缓冲存储器中的页表叫快表，他是用来存放当前访问最频繁的少数活动页面的页表项。解决方法第一次访页表第二次是根据地址取数据或指令。具有快表的地址变换机构页表始址页表长度＋页号页内地址页表寄存器逻辑地址>越界中断1b块号页表页号bd物理地址输入寄存器b页号块号快表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232～264)。页表就变得非常大。4.4.3两级和多级页表(2)只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。解决方法：(1)采用离散分配方式来解决难以找到一块连续的大内存空间的问题；将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，同样也要为离散分配的页表再建立一张页表，称为外层页表。1．两级页表两级页表外层页号 外层页内地址 页内地址31222112110外层页表页表1．两级页表………012345671141151468内存空间…641第0页页表012…1023115114第1页页表012…10231468第n页页表012…1023174210781011012n外部页表两级分页结构1．两级页表外部页表寄存器外部页表页表db物理地址++dP2P1逻辑地址外部页号外部页内地址页内地址具有两级页表的地址变换机构：二级页表地址变换需三次访问主存两级页表对32位机器适用，64位呢？ 页面大小为4KB即212B，还剩52位，按物理块大小212位来划分页表，则剩余40位用于外层页号，此时外层页表可能有1024G个页表项，要占用4096GB的连续存储空间

2．多级页表解决方法：采用多级页表，将外层页表再进行分页。

例:在一个分页式存储管理系统中,某作业的页表如下所示。已知页面大小为1024B,试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址.页号块号021321364.5基本分段存储管理方式在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构,造成共享、保护的困难。一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。4.5.1分段式存储管理的引入引入分段存储管理方式，主要是为了满足用户和程序员的下述需要：

1)方便编程

2)信息共享

3)信息保护

4)动态增长

5)动态链接...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...4.5.2分段系统的基本原理

1.分段

每个段定义了一组逻辑信息，主程序段，子程序段，数据段等两维逻辑地址：段号＋段内地址分段地址中的地址具有如下结构：段号段内地址31161502.段表为了实现段的逻辑地址到物理地址的转换，系统为每个进程设置了一张段表；它记录了段号，段的首（地）址和长度之间的关系。段号012段首址段长度58K20K100K110K260K140K2.段表作业空间（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k段长基址30k40k20k80k15k120k10k150k段号0123内存空间040K80K120K150K3.地址变换机构从逻辑地址到物理地址的转换工作过程：将逻辑地址中的段号与段表长度进行比较，若超过了段表长度则产生越界中断；根据段号和段表始址计算出该段在段表中的位置。检查段内位移是否超过该段的段长；将该段在内存中的起始地址与逻辑地址的段内位移相加即得到要访问的物理地址。段表长度段表始址控制寄存器物理地址<+越界中断分段系统的地址变换机构1002段号S位移量W段表92002008K5004K6006K1K段长基址段号0123+82928K82928692主存段号内存起始地址段长02105002100904193895段号段内位移043025004112532例：在一个段式存储管理系统中，其段表如表所示。

逻辑地址

段表试求表所示中的逻辑地址所对应的物理地址？4.分页和分段的主要区别(1)页是信息的物理单位，段则是信息的逻辑单位(2)页的大小固定且由系统决定，而段的长度却不固定(3)分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的4.5.3信息共享分段易于实现段的共享，即允许若干个进程共享一个或多个分段。段的共享，是通过不同段表中的段表项指向同一个段基址来实现。对共享段的信息必须进行保护分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。图分页系统中共享editor的示意图data10…data1ed40…ed2ed1进程1data10…data1ed40…ed2ed1进程270…6160…2221页表80…7160…2221页表data10…data1data10…data1ed40…ed2ed1…021226061707180主存图分段系统中共享editor的示意图data1editor进程1data2editor进程22404080160基址段长段表3804080160基址段长段表data2…data1editor80240280380420主存可重入代码可重入代码又称为“纯代码”，是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这时的可共享代码即成为可重入码。

分段管理的优缺点优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？4.5.4段页式存储管理分页优点：提高内存利用率分段优点：满足用户需要。因此可以将两者结合成一种新的存储管理方式系统称为“段页式系统”。结合了段式与页式二者优点克服了二者的缺点

1．基本原理作业仍按逻辑分段，但对每一段不是按单一的连续整体存放到存储器中，而是把每个段再分成若干个页面，每一段不必占据连续的主存空间，可把它按页存放在不连续的主存块中。04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K数据段1．基本原理

内存划分：按页式存储管理方案内存分配：以页为单位进行分配地址结构：页内地址(W)段内页号(P)段号(S)1．基本原理段页式存储管理为每一个装入主存的作业建立一张段表,每个段又被分成若干个固定大小的页面，那么每个段又必须建立一张页表把段中的虚页变换成内存中的实际页面。每个段有一个页表，段表中应有专项指出该段所对应页表的页表始址和页表长度。段号状态页表长度页表始址01510

212段表大小段表始址段表控制寄存器页号状态块号011211192121304115段表、页表与内存关系内存空间页表页表段表页号状态块号012911302．地址变换过程地址变换过程Q：为了获得一条指令或者数据，需要访问内存几次？段页式存储管理的优缺点优点：连续空间分配与不连续空间分配方式都属于实存管理技术。不存在外碎片、段可动态增长、便于共享和控制存取访问。硬件成本增加、软件复杂性和管理开销增加、存在内碎片。缺点：4.6虚拟存储器的基本概念前面的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行：(1)有的作业很大，其所要求的内存空间超过了内存总容量。(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业。1．常规存储器管理方式的特征

驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。一次性。要求将作业全部装入内存后方能运行，即作业在运行前需一次性地全部装入内存。2．局部性原理局部性原理：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。具体地表现为：时间局部性和空间局部性2．局部性原理①时间的局限性，如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；某个数据被访问，则不久以后该数据可能被再次访问。②空间的局限性，一旦程序访问了某个存储单元，在不久以后，其附近的存储单元也被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内。3．虚拟存储器的定义具有请求调入功能和置换功能，能从逻辑上对内存进行扩充的一种存储器系统，其逻辑容量由内存和外存容量之和决定，其运行速度接近于内存的速度，而成本接近于外存。虚拟存储器：虚拟存储是一种性能非常优越的存储器管理技术3．虚拟存储器的定义

实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。目的：提高内存利用率。4.6.2虚拟存储器的实现方法1．分页请求系统这是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。1)硬件支持①请求分页的页表机制；②缺页中断机构；③地址变换机构。2)实现请求分页的软件4.6.2虚拟存储器的实现方法2．请求分段系统这是在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。系统同样需要必要的硬件支持：(1)请求分段的段表机制。(2)缺段中断机构。(3)地址变换机构。4.6.3虚拟存储器的特征多次性：一个作业分成多次调入主存运行；对换性：每个作业不是全部一次性地装入内存，将当前不运行的程序、数据调至外存盘交换区；虚拟性：虚存是从逻辑上扩充内存容量，使用户编程所用到的地址空间远大于实际内存容量。4.7请求分页存储管理方式基本思想作业运行的过程中，页面只有需要时才请求被换入内存，而暂不运行的页面置换到外存，从而减少对换时间和所需内存数量，增加多道程序的道数。换入和换出是以页面为基本单位。

需要解决的问题系统需要解决下面三个问题：系统如何获知进程当前所需页面不在主存。当发现缺页时，如何把所缺页面调入主存。当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。4.7.1请求分页中的硬件支持1.页表机制页号物理块号状态位P访问字段A修改位M外存地址指示该页是否已调入内存记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考该页在调入内存后是否被修改过，供置换页面时参考指出该页在外存上的地址，供调入该页时参考查页表时，当该页不在主存时，则引起一个缺页中断,它与一般的中断相比，主要区别表现在：

1)在指令执行期间产生和处理中断信号；

2)一条指令在执行期间，可能产生多次缺页中断(为什么？)B:A:指令TOBCopyA页面6543212.缺页中断机构

3．地址变换机构1、存储保护检查：页号>页表长度？是，越界中断；否则2；2、查快表：找到，修改访问位，对于写操作置修改位，并形成物理地址访问；若未找到，转3；3、查页表状态位：在主存，将表目写入快表；否则，缺页中断。地址变换过程请求访问一页页号页表长越界中断表项在快表中CPU检索快表访问页表页在内存YNYNY修改快表修改访问位和修改位形成物理地址N缺页中断地址变换过程缺页中断处理外存中找到所需页面有空页框吗N选择淘汰的页面更新页表、快表Y该页修改过Y把该页写回外存N保留CPU现场装入新页按逻辑地址查快表该页在快表中有登记?形成物理地址继续执行指令是发缺页中断查页表否该页在主存中形成物理地址将该页登记入快表是保护现场主存有空闲块?装入所需要的页调整页表和主存分配表恢复现场重启被中断的指令是选择调出的页该页被修改?将该页写回辅存相应位置否否是缺页中断处理流程硬件处理操作系统处理4.7.2内存分配策略和分配算法虚存请求分页管理在为进程分配内存时，必须考虑三个问题：第一，确定保证进程正常运行所需要的最小的物理块数；第二，物理块的分配策略；

第三，确定采用何种分配算法来进行页面分配1．最小物理块数的确定保证进程正常运行所需最小的物理块数，与计算机的硬件结构有关，其值取决于指令的格式、功能和寻址方式。采用直接寻址：最小物理块数为2；（存放指令的页和存放数据的页）采用间接寻址：最小物理块数为3；

2．物理块的分配策略1)固定分配局部置换

2)可变分配全局置换3)可变分配局部置换根据进程的类型，为每个进程分配固定数目的内存页框，整个运行期间不再改变。这种策略的难点在于，为每个进程分配的页框数N难以确定。操作系统自身保持一个空闲物理块队列；当某进程发生缺页中断时，由系统从空闲物理块队列中取出一块分配给该进程；但当进程缺页时，只允许从该进程的页面中选出一页换出。若进程缺页中断频繁，则系统须为该进程追加分配若干物理块。3．物理块分配算法平均分配算法按比例分配算法n个进程,进程的页面数为Si,物理块总数为m,每个进程所能分到的物理块数为bi

3)考虑优先权的分配算法一部分按比例地分配；另一部分则根据优先权4.7.3调页策略1．调入页面的时机（2）预调(prepaging)将要访问时调入(根据程序顺序行为，不一定准）（根据空间局部性，目前：成功率≤50％）

（1）请调(demandpaging)发生缺页中断时调入（较费系统开销）

预调必须辅以请调。

2．确定从何处调入页面外存：文件区、对换区从何处将缺页调入内存，分成三种情况：系统拥有足够的对换区空间：系统缺少足够的对换区空间：UNIX方式：若系统拥有足够的对换区空间，则可全部从对换区调入所需页面如果系统缺少足够的对换区空间，对于不被修改的文件，则直接从文件区调入；对于可能被修改的文件，则从交换区调入；UNIX系统中，凡未运行过的页面都从文件区调入；对曾经运行过而又被换出的页面，则从交换区调入3．页面调入过程★缺页中断★保留CPU环境★缺页中断处理★访问内存数据整个页面的调入过程对用户是透明的。逻辑地址空间物理地址空间3．页面调入过程工作原理012345678...…012CPUOS缺页中断缺页中断处理子程序3页表4.8页面置换算法当出现要访问的页面不在内存，内存空间又不足的情况下，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。最佳置换算法先进先出置换算法最近最久未用置换算法Clock置换算法

4.8.1最佳置换算法和先进先出置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。基本思想：1.最佳置换算法选择从当前时刻开始以后不在使用的页面淘汰，如果没有这类页，则选择最长(未来)时间内不再被访问的页面淘汰。1.最佳置换算法例：一个有5个页面的进程，在内存为它分配3个物理块，其页面访问顺序如下：2，3，2，1，5，2，4，5，3，2，5，2进程运行时，会依次将2，3，1三个页面装入内存。以后，当进程要访问页面5时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面予以淘汰。232152453252223231235435235OTP算法：缺页次数=6232354354352352351.最佳置换算法％％＝缺页率为＝50100126×优点：使得页面调入调出的次数达到最小，这是一种理想情况。缺点：实际上无法实现，因为系统无法预知未来页面的访问情况。因此只能用作理论上性能评价的标准。1.最佳置换算法2．先进先出(FIFO)页面置换算法思想：选择最早调入内存的页面淘汰。出发点：近期调入的页面被再次访问的概率要大于早期调入的页面。问题：事实上并非所有的时候都这样。此时FIFO算法的性能较差。这里，我们仍用上面的例子，但采用FIFO算法进行页面置换232152453252FIFO算法：缺页次数=9223232315315215245243243243543522．先进先出(FIFO)页面置换算法％％＝缺页率为＝75100129×

采用FIFO算法还会产生一种奇怪现象。在某些情况下，当分配的物理块数增多反而导致更多的缺页中断，这种现象称为FIFO异常现象或称Belady现象。（根本原因就是没有考虑程序执行的动态特征）某进程共有5页,依次访问页面的序列为：1，2，3，4，1，2，5，1，2，3，4，5；当系统为该进程分配的物理块数为3和4时，它们的缺页情况如下表。2．先进先出(FIFO)页面置换算法123412555344123412225331234111255123444512345123334512341222345123111234512123412512345+++++++++++++++++++4.8.2最近最久未使用置换算法基本思想：每次选择内存中离当前时刻最久未使用过的页面淘汰。理由：如果某页被访问了，则它可能马上还要被访问，反之如果该页很长时间未被访问，则它在最近一段时间内也不会被访问。根据：局部性原理。232152453252223231251254352LRU算法：缺页次数=7354232512543523524.8.2最近最久未使用置换算法％％＝缺页率为＝58.3100127×2．LRU置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。寄存器栈每个页面设立移位寄存器,进程访问某物理块时,要将相应寄存器的最高位置成1。每隔一定时间将寄存器右移一位。用栈来保存当前使用的各个页面的页面号，当进程访问某页面时，将该页面的页面号从栈中移出，压入栈顶。某进程具有8个页面时的LRU访问情况1)寄存器

R0R1R2R3R4R5R6R7R实页0001011110011110011010110101010110001000010101011001100101001000123456782)栈假定现有一进程所访问的页面的页面号序列为：44747040740714710470147012470214701270126470710121263012634.8.3

Clock置换算法要实现LRU算法，需要付出很大的系统开销。1．简单的Clock置换算法Clock算法只要在页表中设一个“引用位”，当页表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。当需要置换一页面时，选择其引用位为0的页1．简单的Clock置换算法

简单Clock置换算法的流程和示例入口查寻指针前进一步，指向下一个表目页面访问位=0?选择该页面淘汰是返回置页面访问位＝“0”否块号页号访问位指针0124034215650711替换指针Page9use=1Page19Use=1Page1Use=1Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page222Use=0Page33Use=1下一个帧指针n-1012345678一个页替换前的缓冲区状态第1页框...下一页替换后的缓冲区状态Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page556Use=1Page13Use=0Page67Use=1Page222Use=0Page33Use=1.n012345678..2321524532522*Clock算法：缺页次数=82*3*2*3*2*3*1*5*2*15*2*4*5*2*4*3*243*2*43*2*5*3*2*5*1*3*2

1*3

2

1

3

2

1

3

5*1．简单的Clock置换算法在改进型Clock算法中首选置换页面：既是未使用过的页面；又是未修改的页面由访问位A和修改位M可以组合成四种类型的页面：(1)最近没有被引用,没有被修改(A=0,M=0)(2)最近没有被引用,但被修改(A=0,M=1)(3)最近被引用,没有被修改(A=1,M=0)(4)最近被引用过,也被修改过(A=1,M=1)2．改进型Clock置换算法置换步骤：步3：如果步2失败，再转向步1操作。2．改进型Clock置换算法步1：从指针当前位置开始,扫描循环队列。把找到的第一个A=0,M=0的页面作为淘汰页面，未找到，转步2。步2：查找A=0且M=1的页面，把找到的第一个这样的页面作为淘汰页面，所有经过的页面的访问位A置0。4.8.4其它置换算法1、最少使用置换算法把到当前为止被访问次数最少的页面淘汰。每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；2．页面缓冲算法它是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；设置两个链表，空闲链表和已修改页面链表。用FIFO选择被置换页如果被置换页没有发生修改，将它直接放入空闲链表否则放入到已修改页面的链表中。2．页面缓冲算法需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表。页面置换算法比较0510152025354030068101214FIFOCLOCK

LRUOPT分配的页数每千次访问的缺页中断数影响缺页次数的因素(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法(4)页面淘汰算法性能问题颠簸（抖动）:页面淘汰算法不合理分配给进程的物理页面数太少

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动原因：

工作集（WorkingSet）模型对一个作业来说，当分配给它的页面数目小于某一个数值时，其缺页中断次数急剧增加，甚至出现页面抖动现象；而高于这个页面数时，缺页中断次数不会明显减少。此时我们称这个页面数范围为页面的“工作集”。影响工作集的因素作业的特征（结构、大小、访问数据的规律等）作业的运行时间段等4.9请求分段存储管理方式与请求分页系统类似，在分段的基础上增加请求调段功能和段置换功能，便可形成具有虚拟存储器功能的请求分段系统。为实现请求分段式存储管理,需要有一定的硬件和相应的软件支持。段表机制缺段中断机构地址变换机构4.9.1请求分段中的硬件支持1．段表机制系统要为每一个作业建立一张段表。段表是进行段调度的主要依据。其一般格式为：段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址标志本分段的存取属性记录该段被访问的频繁程度（与分页相应字段同）该段在调入内存后是否被修改过，供置换时参考指示本段是否已调入内存，供程序访问时参考本段在运行过程中，是否做过动态增长本段在外存中的起始地址2．缺段中断机构在请求分段系统中，若进程访问的段尚未调入内存，缺段中断机制产生缺段中断信号，中断处理程序根据信号调入所需段。和缺页中断机制类似，在一条指令执行期间可能产生多次中断。和缺页中断机制不同的是，指令和操作数必定不会跨越段边界上；虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是3．地址变换机构请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。为此，在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。访问[S][W]W段长分段越界中断处理符合存取方式NYY分段保护中断处理段S在主存N缺段中断处理NY修改访问位、修改位形成物理地址

返回4.9.2分段的共享与保护1．共享段表为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。1．共享段表段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制………………共享段表1．共享段表(3)段号。对于一个共享段，不同的进程可以各用不同的段号去共享该段。(2)存取控制字段。对于一个共享段，应给不同的进程以不同的存取权限。(1)共享进程计数count。记录有多少个进程需要共享该分段，特设置了一个整型变量count。2．共享段的分配与回收1)共享段的分配第一个请求以后其它进程使用该共享段申请内存分区，调入，修改共享段表相应内容；在本进程段表中填入该共享段的物理地址；然后在共享段表中增加一表目，填入相应内容2．共享段的分配与回收2)共享段的回收撤消在该进程段表中共享段所对应的表项，以及执行count:=count-1操作。若count结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项。3．分段保护越界检查2)存取控制检查3)环保护机构段号与段表长度进行比较段内地址与段长进行比较(1)只读(2)只执行(3)读/写(1)可以访问在相同环或较低特权环中的数据。(2)可以调用在相同环或较高特权环中的服务。3．分段保护图环保护机构

练习1、考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3，5时，试问LRU、FIFO、OPT这三种置换算法的缺页次数各是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）时47分31秒内存块数为3,FIFO算法页面踪迹图％

％＝

缺页率为＝

80

100

2016

*

27637637637162162162561541342342312312161212342156212376321236++++ +++ + + + + +++++415321613213216内存块数为3,LRU算法页面踪迹图％

％＝

缺页率为＝

75

100

2015

*

2363