第4章-存储器管理最终-2012级用

第四章

存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法1用户程序的主要处理阶段连续分配方式虚拟存储器的基本特征分页、分段存储管理技术

第四章

存储器管理2存储管理的功能内存分配——为每个进程分配一定的内存空间地址映射——把程序中所用的相对地址转换成内存的物理地址内存保护——检查地址的合法性，防止越界访问内存扩充——解决“求大于供”的问题，采用虚拟存储技术3第一节

存储器的层次结构存储器的层次结构存储器管理的功能41、

存储器的层次结构在现代计算机系统中，存储器是信息管理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质cpu寄存器主存辅存51、

存储器的层次结构寄存器：

容量最小、速度最快、最贵、易变的高速缓存Cache：少量的、非常快速、昂贵、易变的内存RAM：若干兆字节、中等速度、中等价格、易变的磁盘：数百兆或数千兆字节、低速、价廉、不易变的内存空间一般分为两部分：系统区和用户区操作系统等系统软件占用系统区，用户区用来存放用户程序，存储管理主要是针对内存用户区的管理。62、

存储器管理的功能地址变换内存的分配与回收内存的保护与共享内存的扩充7第二节

程序的装入和链接从源程序到程序执行基本概念程序的装入程序的链接8第二节

程序的装入和链接

从用户的源程序进入系统到相应程序在机器上运行，所经历的主要处理阶段有

，

，

和

。

编译阶段链接阶段装入阶段运行阶段91、从源程序到程序执行编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。装入：装入程序*由装入程序（Loader）将装入模块复制到内存中。10库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子2112、基本概念名空间：程序中由自定义的符号名构成的集合。地址空间：程序中用来访问信息所用地址单元的集合。其中的地址被称为逻辑地址（相对地址/程序地址/虚地址）,通常是以0为基址进行顺序编址。(程序员关心的问题)存储空间：物理存储器中全部物理存储单元的集合。每个存储单元都有它自己的编号，该编号被称为物理地址（绝对地址/内存地址/实地址）。一个程序只有从地址空间装入到存储空间后才能运行。12装入地址映射BR=1000LoadA,2003456

。

。

。1200内存空间LoadA,data1data13456名空间LoadA,20034560100200编译链接地址空间源程序目标程序运行程序13LOAD1,50012345LOAD1,5001234501005007005000510055005700程序A的地址空间程序A的内存空间..................143、程序的装入装入就是把链接好的装入模块装入“内存”。装入方式绝对装入：装入位置是固定的，由程序员直接编址或由汇编、编译程序给出地址，即按逻辑地址(=物理地址)装入内存。(只适用于单道系统)可重定位装入：即静态重定位动态运行时装入：即动态重定位15绝对装入方式逻辑地址与实际地址相同要求程序员熟悉内存的使用情况通常在程序中采用符号地址16可重定位装入方式目标模块从0编址，其它地址相对于起始地址计算重定位（地址映射）：由于作业装入到与其地址空间不一致的存储空间所引起的对地址变换的过程。逻辑地址变换为物理地址。17作业地址空间内存空间装入365LOAD1,25005000250001000365LOAD1,250015000125001000011000365LOAD1,1250015000125001000011000静态重定位18动态运行时装入方式在程序执行时将相对地址转换成为绝对地址允许程序在内存中移动19VR：逻辑地址寄存器BR：重定位寄存器动态重定位

LoadA,500123455001000

LoadA,50012345作业地址空间

内存空间BR+0100500VR100011001500204、程序的链接链接：将经过编译或汇编后所得到的一组目标模块及所需的库函数装配成一个完整的装入模块的过程。具体工作：对相对地址进行修改变换外部调用符号链接方式：静态链接：程序执行前链接装入时动态链接：便于修改和更新；便于共享。运行时动态链接：最小化快速装入，节省内存。21静态链接执行前将目标模块和他们的库函数，连接成一个完整的装入模块。两个问题：对相对地址修改变换外部调用符号22模块ACallB;Return;0L-1模块BCallC;Return;0M-1模块C……Return;0N-1链接模块AJSR“L”;Return;0L-1模块BJSR“L+M”;Return;LL+M-1模块C……Return;L+ML+M+N-1装入模块目标模块232.装入时动态链接

链接在装入时进行，即在装入一个模块时，若发生一个外部模块调用事件，则由装入程序去找出相应的外部模块，将它装入内存，并把它链接到调用模块上去这种链接方式的优点是便于对程序模块进行修改和更新，并且可以对目标模块实现共享，以提高内存和外存的利用率。243.运行时动态链接

将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。25第三节

连续分配方式

为用户程序分配一个连续的内存空间，曾被广泛应用，且现在仍被采用。单一连续分配固定分区分配动态分区分配可重定位分区分配261、单一连续分配基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在低址部分；系统区以外的全部内存空间是用户区。在内存中仅驻留一道程序，整个用户区为一用户独占。特点方法简单，对硬件要求低，易于实现；很难实现共享内存和CPU利用率低，只能用于单用户单任务OS；实例CP/M，MS-DOS，嵌入式系统27单一连续分配DOS内存分区CP/M内存分区系统参数区BIOSCCPBDOS系统区系统区282、固定分区分配把内存划分为若干个固定大小的连续分区；最简单的一种可运行多道程序的存储管理方式。划分分区的方法分区大小相等：缺乏灵活性，用于控制多个相同对象的系统（群控系统）分区大小不等：多个较小分区、适量中等分区、少量大分区内存分配管理将分区按大小排队建立分区说明表—分区号、起址、大小、状态程序装入时，由内存分配程序检索分区说明表，找到符合要求的分区，并进行标记。29分区号大小(k)起址(k)状态11220已分配232已分配364

已分配4128已分配30分区号大小(k)起址(k)状态11220已分配23232已分配364

已分配4128已分配31分区号大小(k)起址(k)状态11220已分配23232已分配36464已分配4128已分配32分区号大小(k)起址(k)状态11220已分配23232已分配36464已分配4128128已分配33分区号大小起址状态18K512K未使用232K520K未使用332K552K未使用4128K584K未使用5512K712K未使用…………系统区分区1分区4分区5分区2分区3系统区分区1分区4分区5分区2分区3作业1作业2作业3已使用已使用已使用作业1进入，大小30K作业2进入，大小500K作业3进入，大小8K优点：易于实现，开销小。缺点：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。343、动态分区分配数据结构分区分配算法分配与回收操作35分区分配中的数据结构空闲分区表空闲分区链36空闲分区表每个分区占一个表目，包含分区序号、分区始址、分区大小分区号大小（K）起址（K）状态16444可用224232可用3空表目4空表目5………37空闲分区链在每一个分区的起始部分设置用于控制分区的信息、向前指针，在分区尾部设置一个向后指针，形成双向链表。前向指针+2N0

后向指针+2N0

N个字节可用空闲链表结构38分区分配算法*FF首次适应算法：空闲分区按起址递增次序排列，从头开始直至找到第一个满足要求的空闲分区。特点：内存低端会留下小的空闲区，高端有大的空闲区；每次查找从低址开始，会增加查找开销。*NF循环首次适应算法(下次适应)：从上次分配的空闲区位置之后开始查找(到最后分区时再回到开头)特点：减少查询次数，内存分配均匀；但缺乏大的空闲分区。*BF最佳适应算法：空闲分区按大小递增的次序排列，从头开始找到第一个满足要求的空闲分区。特点：会留下大量难以利用的小碎片。39WF最差适应算法：空闲分区按大小递减的次序排列，最前面的最大的空闲分区就是找到的分区。特点：查找速度快，分配后剩下的可用空间比较大；但一段时间后会缺乏较大空闲区。以上四种算法，统称为顺序搜索法。

这些算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。QF快速适应算法(分类搜索法)：按进程常用空间大小对空闲分区进行划分，形成多类分区链表，并设立一张分区管理索引表。特点：查找效率高，可满足大空间需求；但分区归还算法复杂、空间开销大。40例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列：经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。1、首次适应算法2、最佳适应法3、最坏适应法410K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空首次适应算法FFJ1J2J3J4有个5K的作业J5，24K的作业J6到来：20KJ5104KJ6始址长度标志20K18K未分配48K20K未分配104K6K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ415K5KJ580K24KJ642分区分配操作

1）分配内存2）回收内存43分配内存设请求的分区大小：u.size设空闲分区大小：

m.size不可再切割的剩余分区大小：size如果m.size-u.size≤size将整个分区分配给请求者，否则剩余部分留在空闲分区链（表）中。将分区的首址返回给调用者44查找空闲分区链表第一项检索完否？m.size>u.size?m.size-u.size≦size?划出u.size大小的分区修改有关的数据结构返回将该分区从链表中移出继续检索下一个表项YYYNNN内存分配流程45回收内存

当进程释放内存时，系统根据回收区的首值，从空闲区链（表）中找到相应的插入点，回收区可能出现四种情况：（1）与插入点的前一个空闲区F1相邻接。（2）与插入点的后一空闲分区F2相邻接。（3）同时与插入点的前、后两个分区邻接。（4）既不与F1邻接，又不与F2邻接。46

F1

回收区

F1回收区与插入点的前一个空闲区F1相邻接

47

回收区F2

回收区回收区与插入点的后一空闲分区F2相邻接48F1

回收区F2F1回收区同时与插入点的前后两个分区邻接494、可重定位分区分配动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。通过“拼接”或“紧凑”来实现程序的浮动（动态重定位）。50OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片OS区Job2Job4Job3Job1Job5Job6Job7OS区Job2Job4Job3Job1Job5Job6Job7514.2.4可重定位分区分配1.动态重定位的引入图4-8紧凑的示意☆分配一个连续的内存空间“紧凑”52动态重定位的引入操作系统用户程序110KB用户程序330KB用户程序614KB用户程序926KB碎片：内存中不能被利用的小分区称为“零头”或“碎片”。

53动态重定位的引入操作系统用户程序1用户程序3用户程序6用户程序980KB分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。54动态重定位的实现地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位增设硬件机构：重定位寄存器。55动态重定位的实现处理机一侧存储器一侧作业J内存365LOAD1,2500500025001000365LOAD1,2500150001250010000110002500相对地址10000重定位寄存器000056动态重定位分区分配算法增加了紧凑功能设请求的分区大小：u.size设空闲分区大小：

m.size不可再切割的剩余分区大小：size可重定位分区分配算法动态分区+紧凑技术，与动态分区分配算法基本相同，但增加了紧凑功能。57动态重定位分区分配算法流程查找空闲分区链表第一项找到大于u.size的可用分区？按动态分区方式进行分配修改有关的数据结构返回分区号及首址进行紧凑形成连续空闲区YYNN请求分配u.size分区空闲分区总和≥u.size？修改有关的数据结构无法分配返回58优缺点分析优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。动态重定位分区分配算法595、覆盖技术覆盖技术是作业之间或作业内部的若干个程序段共享主存的技术。主程序子程序A子程序B子E子C子D子F调用子G调用调用2k3k4k1k4k4k4k3k子H3k调用主程序2k子程序A(B)4kC(D/E/F/G)4kH3k覆盖段覆盖段程序大小＝28K内存空间只需13K60简单覆盖应用示意图输入模块正常输出计算模块数据错误结束退出结果异常分析与报告输入模块计算模块结束退出正常输出数据错误结果异常分析与报告61对换的引入对换：指把内存中暂时不能运行的进程或暂时不用的程序和数据调出到外存，以腾出空间供具备运行条件的进程或其程序数据调入内存投入运行。（中级调度）目的：用于解决内存不足的问题；对换分类（1）整体对换：以整个进程为单位，又称进程对换（2）部分对换：页面对换，以“页”为单位；分段对换,以“段”为单位进程对换实现的功能对换空间的管理进程换入过程进程换出过程6、对换技术（Swapping）62文件区对换区外存对换空间的管理为提高空间利用率采用离散分配方式为提高对换速度采用连续分配方式63进程换出过程选择处于阻塞状态且优先级最低的进程作为换出进程将该进程的程序和数据传送到磁盘的对换区上若传送过程未出现错误，便可回收该进程所占用的内存空间，并修改该进程的PCB64进程换入过程定时查看进程状态将处于“就绪”态的换出时间最久的进程换入内存直至已无可换入的进程或无可换出的进程为止。65离散分配方式基本思想：将一个进程分散的装入不相邻的分区中。离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。66第四节

基本分页存储管理方式连续分配方式的不足，促使人们产生了离散分配的管理思想。从而引入了“分页”分配管理的管理方式。分为：基本分页（纯分页）和支持虚存管理的请求分页管理。基本分页存储管理方式不具备页面对换功能又称纯分页存储管理方式不支持虚拟存储器功能67分页存储管理将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页编号，从0开始，如第0页、第1页等。把内存空间分成与页面相同大小的若干个存储块，称为块或页框，也加以编号，如0#、1#块等。以块为单位将进程中的若干个页分别装入到多个可以不相临接的物理块中68页内碎片由于进程的最后一页经常不满一块而形成不可利用的碎片，称之为“页内碎片”。69页面大小通常1KB-8KB页面太小：页内碎片小，提高内存利用率，但页表过长，占内存；降低对换效率。页面太大：提高了对换速度。但页内碎片大，降低了内存利用率。701、页面与页表01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业02K-1第2页（页长2K）02K-14号页架（页长2K）实现原理：1．等分主存：每份称为物理块/页框/页架，编号：01234……2.划分地址空间：以块长为尺度将作业的地址空间从低地址端开始划分成片每片称为页/页面，编号：01234……

3.分配原则：主存以块为单位，作业以页为单位１页→１块分给一个作业的若干块不要求邻接

711、页面与页表页面页面和物理块（页框/架）：顺序编号，页内碎片页面大小：2nBytes一般在：1K~8K地址结构

逻辑地址 物理地址页内地址d物理块号P

位移量W页号P例如：位移量（页内地址）W页号P3112110每页大小：212=4KB地址空间中最多有：220=1M页721、页面与页表例如：位移量W页号P151090计算一共划分了多少页，每一页有多大？每页大小：210=1KB地址空间中最多有：26=64页73已知：逻辑地址空间中的地址A，页面大小L页号P和页内地址d的计算公式P＝INT[A/L]INT：整除函数d＝[A]MODLMOD：取余函数例如：某系统的页面大小为1KB，地址A=2170B，则求得P=2，d=1221、页面与页表74页表——页面映像表定义：为便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映像表，简称页表，记录页面在内存中对应的物理块号。数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。1、页面与页表7523579…11104内存第0页第1页第2页第3页第4页第5页第6页012356789101112用户作业第0页第1页第2页第3页第4页第5页第6页…第n页块号页号1051169453327120页表……页表的作用问题：分页存储管理方式要想从内存读取一个信息，需要访问几次内存？两次。76表项中常设有存取控制字段一位：允许读/写只读两位：

允许读/写只读只执行77

例题:在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一个逻辑地址为2F6AH，且第0、1、2页依次放在物理块号10、12、14中，问相应的物理地址是多少？解答：因逻辑地址长度为16位，页面大小4096字节，所以，前面的4位表示页号。2F6AH的二进制表示：0010

1111

0110

1010可知页号为2，故放在14号物理块中十六进制表示为：EF6AH78某存储器中的用户空间共有32个页面，每页1KB，主存32KB。假定某时刻系统为用户的笫0、1、2、3页分别分配物理块为5、10、4、7，地址0A6F对应的物理地址为多少?

解：0A6F对应的二进数16位为：0000101001101111（1分），可见是第2个页，其对应的物理块号为4（2分）。故物理地址为：0001001001101111，即126F792、地址变换机构基本的地址变换机构地址变换机构的任务：实现地址映射，即从逻辑地址到物理地址的变换过程。实际上是将逻辑地址中的页号转换为内存中的物理块号。地址变换任务是借助于页表来完成的，页表存放在内存系统区的一个连续空间中；系统中只设置一个页表寄存器PTR，存放页表在内存的始址和页表的长度(即页数)。进程未执行时，页表的始址和页表长度存放在本进程PCB中，当调度到进程时装入页表寄存器中。地址映射过程：自动的将逻辑地址分为页号和页内地址根据页号查询页表：页表首地址+页号*表项长度80页表始址页表长度页表寄存器≤页表块号页号53327120物理地址页号(3)页内地址逻辑地址越界中断找到该页对应的物理块号，装入物理地址寄存器将页内地址送入物理地址寄存器。81例1：已知某分页系统，主存容量为64k，页面大小为1k，对一个4页大的作业，第0、1、2、3页被分配到内存的2、4、6、7块中。求：将十进制的逻辑地址1023、2500、4500转换成物理地址。解:(1)1023/1K，得到页号为0，页内地址1023。又对应的物理块号为2，故物理地址为2*1k+1023=3071(2)2500/1K，得到页号为2，页内地址452。又对应的物理块号为6，故物理地址为6*1k+452=6596(3)4500/1K，得到页号为4，页内地址404。因为页号不小于页表长度，故产生越界中断。82快表引入原因cpu存取一个数据时要两次访问内存第一次是访问页表，找到指定页的物理块号，再将块号与页内偏移量w拼接形成物理地址。第二次访问内存是从所得地址中获得所需数据（或向此地址中写入数据）cpu的工作效率大约减少一半83为提高地址变换速度增设一个具有并行查询能力的高速缓冲寄存器，称为“联想寄存器”或“快表”，用于存放当前访问的页表项。84地址变换过程cpu给出有效地址，由地址变换机构自动地将页号p送入高速缓冲存储器，并将此页号与高速缓存中的所有页号进行比较，若有与此相匹配的页号，则表示所要访问的页表项在快表中。于是，可直接读出该页所对应的物理块号，并送物理地址寄存器中。如在快表中未找列对应的页表项，还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，还将此页表项存入快表中的一个寄存器单元中，亦即重新修改快表、但如果联想存储器巳满，则os必须找到一个老的且已被认为不再需要的页表项将它换出。局部性原理85页表始址页表长度页表寄存器≤页表块号页号5332712031250物理地址21250逻辑地址越界中断快表块号页号2051145320输入寄存器具有快表的地址变换机构86页表始址页表长度页表寄存器≤页表块号页号5332712071250物理地址11250逻辑地址越界中断快表块号页号2051145320输入寄存器具有快表的地址变换机构87快表通常只存放16~512个页表项对于中、小型作业来说，已有可能把全部页表项放在快表中大型作业只能将其一部分页表项放入其中从快表能找到所需页表项的命中率可达90%88例：检索联想寄存器的时间为20ns，访问内存的时间为100ns。如果能在联想存储器中检索出页号，则cpu存取数据共需要

，如果不能在联想存储器中找到该页号，则总共需要

。再假定访问联想存储器的命中率分别为0%，50%，80%，90%，98%，计算有效访问时间。有效访问时间：T命中率：hT=h*t1+（1-h）*t289命中率%T=h*t1+（1-h）*t202205017080140901309812290例如：有32位逻辑地址空间的分页系统，规定页面大小为4KB，即212B,则在每个进程页表中页表项可达1兆（220）个之多。又因为每个页表项占用4个字节，故每个进程仅仅其页表就要占用4MB的内存空间，而且还要求是连续的。解决方法：（1）用离散分配方式解决难以找到连续的大内存空间的问题。（2）只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。91两级页表

为离散分配的页表再建立的一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。923、两级和多级页表两级页表解决大页表占用大的连续存储空间的问题；将在内存中离散分配的页表再建立一张页表，称为外层页表。逻辑地址： 外层页号+外层页内地址+页内地址增设外层页表寄存器，存放外层页表的始址10位10位12位933、两级和多级页表以32位逻辑地址空间为例当页面大小为4KB时（12位），若采用一级页表结构，应具有20位的页号，即页表项应有1M个；用两级页表时，再对页表进行分页，使每页中包含210个页表项，最多允许有210个页表分页，即外层页表中的外层页内地址P2为10位，外层页号P1也为10位。94逻辑地址结构外层页号外层页内地址页内地址3122211211095963、两级和多级页表外部页表块号页号321078110110页表分页11223120211130……01231121131011……97外部页表外部页表寄存器物理地址外部页号P1外部页内地址P2逻辑地址页内地址d…………页表具有两级页表的地址变换机构984、基本分页的特点优点：存在页内碎片，但碎片相对较小，内存利用率较高实现了离散分配，消除了程序浮动；缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。99第五节

基本分段存储管理方式基本分段管理思想的引入基本原理地址变换分段与分页的主要区别段页式存储管理方式1001、分段管理思想的引入分段存储管理方式主要是为了满足用户和程序员的下述需要：方便编程：LOAD1,[A]|<D>;信息共享：共享的实现以是信息的逻辑单位为基础信息保护：同样是对逻辑单位进行保护动态增长：如数据段动态链接：运行时调入内存并链接101在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义一组逻辑信息。每个段都从0开始编址，采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而段长不等整个作业的地址空间分成多个段，是二维的。2、基本原理102分段地址中的地址具有如下结构：

段号段内地址31

16150允许一个作业最多有64K个段每个段的最大长度为64K103系统为每一个进程建立一张段映射表，简称段表。用于实现从逻辑段到物理内存的映射。（段表的定义及作用）段表1042、基本原理分段作业（逻辑地址）空间分段，每个段都有名字：主程序段、子程序段、数据段、栈段等逻辑地址：二维地址（段号，段内地址）每个段装入内存中的一个连续的内存空间段表段号、段基址、段长度等每个段在段表中占一个表项段表寄存器：存放段表的起址和长度利用段表实现地址映射1052、基本原理内存第0段第1段第2段第3段用户作业段表基址段长150K35K500K9K300K20K100K42K3210段号第0段第1段第2段第3段1063、地址变换及变换机构基本分段管理的地址变换与基本分页管理的变换机构和过程类似段表寄存器存放段表的起始地址和段表长度越界访问控制逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较。107段表始址段表长度（4）段表寄存器≤8292物理地址段号2100逻辑地址越界中断段表基址段长92002008K5004K6006K1K3210段号内存108例2：对于如下所示的段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，230）转换成物理地址。解:(1)段号0<段表长，且137<段长10k，故段号、段内地址全部合法。得物理地址为50k+137=51337段号内存始址段长050k10k160k3k270k5k3120k8k4150k4k解:(2)段号1<段表长，段号合法。4000>段长3k，因此产生越界中断。解:(3)段号2<段表长，且3600<段长5k，故段号、段内地址全部合法。得物理地址为70k+3600=75280解:(4)段号5＝段表长，故段号不合法。产生越界中断。1094、分段与分页的主要区别（重点）页是信息的物理单位，分页是为了满足系统管理的需要；段是信息的逻辑单位，分段是为了满足用户的需要；页的大小固定且由系统决定，段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。分页系统中的逻辑地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址；分段系统中的是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。110内存页表editor1data1进程1data1进程2editor2…editor40editor1editor2…editor40…data10…data102122…6061…702122…6071…80editor1data1data1editor2…editor40…data10…data10021226061707180可重入代码(纯代码)：允许多个进程同时访问但不允许修改的代码（程序的编译器）111内存段表基址段长240K40K80K160K10段号editorJob1数据进程1editorJob2数据进程2基址段长380K40K80K160K10段号editorJob1数据Job2数据112段号S段内页号P页内地址W5、段页式存储管理方式基本思想结合分页和分段技术；分页：有效提高内存利用率分段：很好的满足用户需求原理对内存进行分页（物理块/页架）；对用户作业先分段，各段再分页。地址结构与地址变换段号、段内页号、页内地址三部分段表和页表113段页式存储管理方式

既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等优点又能像分页系统那样解决内存的外部碎片问题，以及可为各个分段离散地分配内存等问题。114段页式存储管理基本原理

分段和分页原理结合先将用户分成若干个段再把每个段分成若干个页，并为每一个段赋予一个段名。

115作业地址空间116段页式地址结构117主程序段数据段子程序段118……段表始址段表长度段表13021110页表始址页表长度状态段号段表寄存器页表03121110存储块号状态页号页表1110存储块号状态页号119段表始址段表长度段表寄存器逻辑地址页号P页内地址段号S≤段表块号b块内地址物理地址越界中断页表xxxx2xxxx1xxxx0页表始址段号2b10存储块号页号120三次访问内存第一次访问段表，从中取得页表始值；第二次访问页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次真正访问指令或数据。121段页式存储管理的优缺点同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。访问效率下降：一次访问转换成了三次访问。122第六节

虚拟存储器的基本概念虚拟存储器的引入虚拟存储器的实现方法虚拟存储器的特征1231、虚拟存储器的引入内存空间的限制情况一：内存空间装不下的大作业无法运行情况二：作业量大时，无法允许更多的作业并发常规存储器管理方式的特点：一次性、驻留性虚拟存储器物理上不存在，利用海量外存进行内存“空间”扩展。允许作业部分装入，需要时再临时装入所需的部分。直到作业退出，某些部分也有可能没被装入过。*基于局部性原理—程序在执行时将呈现局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，它所访问的存储空间也局限于某个区域。124局部性原理几个论点程序多数情况是顺序执行的过程调用会使程序的执行由一部分区域转至另一部分区域，但过程调用的深度大多不超过5。程序将会在一段时间内都局限在这些过程的范围内运行。循环结构虽只由少数指令构成，但是他们将多次执行程序包括许多对数据结构的处理。125局部性表现时间局限性。某指令一旦执行，则不久后该指令可能再次执行；某数据被访问过，则不久后该数据可能再次被访问。空间局限性。程序在一段时间内访问的地址，可能集中在一定的范围之内，其典型的情况便是程序的顺序执行。126虚拟存储器定义：虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存和外存之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。1272、虚拟存储器的实现方法必须建立在离散分配的内存管理技术基础上。分页请求系统在分页系统的基础上、增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，便可启动运行。再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上、置换时以页面为单位1282、虚拟存储器的实现方法基本分页系统+请求调页功能+页面置换功能＝页式虚拟存储系统硬件支持：请求分页的页表机制、缺页中断机构、动态地址变换机构。软件支持：请求分页、页面置换1292、虚拟存储器的实现方法例：某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号031721138则逻辑地址0A5C(H)所对应的物理地址是什么？130请求分段系统基本分段系统+请求调段功能+分段置换功能＝段式虚拟存储系统硬件支持：请求分段的段表机制、缺段中断机构、动态地址变换机构。软件支持：请求分段、段的置换1313、虚拟存储器的特征离散性——最基本在内存分配时采用离散分配方式；多次性一个作业被分成多次调入内存运行；对换性允许在作业的运行过程中进行换进、换出；虚拟性——最重要能从逻辑上扩充内存容量，使用户“看到”的内存容量远大于实际大小。（总容量不超过物理内存和外存交换区容量之和）该特征是以上两个特征为基础的。132第七节

请求分页存储管理方式请求分页中的硬件支持内存分配策略和分配算法请求分页策略1331、请求分页中的硬件支持页表机制用于地址转换；增加页表项：页号物理块号状态位P访问字段A修改位M外存地址状态位P：用于指示该页是否已调入内存访问字段A：记录本页在一段时间内被访问的次数修改位M：该页在调入内存后是否被修改过外存地址：指示该页在外存上的地址134缺页中断机构请求分页系统中每当所要访问的页不在内存时，便引发一次缺页中断、请求将所缺之页调入内存。缺页中断与其他中断的不同：在指令执行期间产生和处理中断信号一条指令在执行期间可能产生多次缺页中断654321A:B:CopyAtoB指令135第八节

页面置换算法*最佳置换算法（OPT）*先进先出（FIFO）*最近最久未使用置换算法（LRU）Clock置换算法（NRU）最少使用置换算法（LFU）页面缓冲置换算法（PBA）当内存中没有可以利用的页架时，根据一定的策略从内存中选择一个页面，把它置换到外存，称为页面置换算法。1361、最佳置换算法（OPT）

由Belady于1966年提出的一种理论上的算法，所淘汰的页面，将是永不使用的或是在最长时间内不被访问的页面（向将来看）。

例如，假定系统为某进程分配3个物理块，并考虑有以下页面引用串，需要注意的是：在某进程中，(有些页面经常被访问，如全局变量，常用函数，某些例程等)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1137引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用率70770170122010320304243230321201201770101页框(物理块）203采用最佳置换算法，共发生9次缺页，缺页率9/20=45%。1、最佳置换算法（OPT）1381、最佳置换算法（OPT）特点：理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。1392、先进先出（FIFO）基本思想：

FIFO置换算法的思想是：当发生页面置换时，总是选择在内存驻留时间最久的页面予以淘汰。对于上例，利用FIFO置换算法时，当访问2号页面时，由于7号页面驻留时间最长，故将7号页面置换出去，同理，对其它页面置换情况参照如下表所示。140引用率70770170122010323104430230321013201770201页框2304204230230127127011从表上可以看出，采用FIFO置换算法，共发生15次缺页，缺页率为15/20=75%，2、先进先出（FIFO）1412、先进先出（FIFO）特点：实现简单与进程实际的运行不相适应142先进先出算法虽然简单，但从数据分析可以看出该算法效果不够理想，由于程序执行具有局部性原理，所以该算法不能保证经常被访问的页面不被淘汰。同时，在FIFO置换算法中，随着分配给进程的物理块增多，反而缺页率增大了，这种现象称为Belady异常。只有FIFO置换算法有这种奇怪现象，其它算法没有。下面来看一个例子，设某进程的页面引用串如下：1，2，3，4，1，2，5，1，2，3，4，5当该进程分得3、4物理块时，其缺页次数分别是9，10。(具体分析)2、先进先出（FIFO）1433、最近最久未使用置换算法（LRU）基本思想：

根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近将来”的近似，选择最近最久未使用的页面予以淘汰。特点：性能较好实现复杂，需要硬件支持（每页配置一个寄存器、栈），增加系统负担。144引用率70770170122010320304403230321132201710701页框402432032102从上可以看出，采用LRU算法时，系统缺页12次，缺页率为12/20=60%3、最近最久未使用置换算法（LRU）1453、最近最久未使用置换算法（LRU）算法实现：

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T,当须淘汰一个页面时，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。146LRU置换算法的硬件支持：1）寄存器为每个在内存中的页面配置一个移位寄存器，表示为：R＝Rn-1Rn-2…R1R0当进程访问此物理块时，将Rn-1位置1。定时信号每隔一定时间将寄存器右移一位,并将最高位补0。具有最小数值的寄存器所对应的页面就是最近最久未使用的页面。147101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页某进程具有8个页面时的LRU访问情况1482）栈利用栈来保存当前使用的各个页面的页面号。当进程访问此页面时，将该页面的页面号从栈中移出，压入栈顶。因此栈顶是最新被访问页面的编号，栈底是最近最久未使用页面的页面号。例如：现有一进程所访问的页面号序列如下：4，7，0，7，1，0，1，2，1，2，6栈的变换情况为：4740741704017410742107412074210746210747067170401212149例1：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用FIFO、LRU、OPT计算缺页次数和缺页率。分析：如果所访问的页还没有装入内存，将发生一次缺页中断。访问过程中发生缺页中断的次数就是缺页次数。缺页次数除以总的访问次数，就是缺页率。150缺页中断32+253+453423+423425+425+125+135+13232+32+21252354251232页面走向使用FIFO算法:缺页次数：9，缺页率：9/12；页面置换6次驻留内存最久的页面——黄色标志151缺页中断32253253+253+453452+452152+152+13232+32+21252354251232页面走向使用LRU算法：长时间没有访问的页面——黄色标志刚刚访问过的页面——绿色标志缺页次数：7，缺页率：7/12；页面置换4次152缺页中断32532532+532534534+534532+532+13232+32+21352354251232页面走向使用OPT算法：将来再也不用或最长时间不用的页面——黄色标志缺页次数：6，缺页率：6/12，页面置换3次LRU最接近OPT，表明LRU优于FIFO。153例2：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。154缺页中断32435+435+235215215+215+214+314+324+321+21+11543215214321页面走向使用FIFO算法——物理块数为3:缺页次数：9，缺页率：9/12155使用FIFO算法——物理块数为4:缺页次数：10，缺页率：10/12这种异常现象称为Belady现象。缺页中断432+3254+3214+3215+4215+4315+432543214321+4321+321+21+11543215214321页面走向1564、最少使用置换算法（LFU）(不讲)选择在最近时期使用最少的页面淘汰。（频率）为每个页面配一个计数器。需为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置1，此后每隔一定时间自动右移一位。最近一段时间最少使用的页面是∑Ri最小的页。157101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页158第九节

请求分段存储管理方式请求分段中的硬件支持请求分段中的分段共享请求分段中的分段保护以基本分段内存管理为基础，程序运行前，只需先调入部分分段，便启动执行。其它分段在需要时，通过缺段中断处理程序临时调入。1591、请求分段中的硬件支持段表机制段名(号)段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址(1)存取方式：存取属性为只执行、只读或允许读/写(2)访问字段A：记录该段被访问的频繁程度(3)修改位M：该段在进入内存后是否被修改过(4)存在位P：指示本段是否已调入内存(5)增补位：表示本段在运行过程中，是否做过动态增长(6)外存始址：本段在外存中的起始地址，即起始盘块号160缺段中断机构以信息分段为单位操作。由于分段不定长，处理时较缺页中断复杂。虚段S不在内存返回阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空闲区链唤醒请求进程空区容量总和能否满足？否空区拼接，以形成一个合适的空区淘汰一个或几个实段以形成一个合适空区是否是161地址变换机构在基本分段系统地址变换机构的基础上形成，增加了分段不在内存时的缺段中断请求。访问[S][W]返回W≤段长？修改访问字段，如写访问，置修改位=1形成访问主存地址(A)=(主存始址)+(位移量W)是符合存取方式？段S在主存？分段越界中断处理分段保护中断处理缺段中断处理是是否否否1622、分段共享共享段表段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制…………共享进程计数count：记录要共享该段的进程数目存取控制字段：对一共享段，给不同进程不同权限段号：不同进程可以各用不同段号去共享某共享段163共享段的分配对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，在把共享段调入该区。同时将该区的始址填入该进程的段表中。在共享段表中增加一表项，置count=1其他进程要调用该共享段时，在进程的段表中增加一表项，填入该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1共享段的回收当进程不再需要共享段时，先释放，撤消共享段的表项，执行count=count-1仅当count=0时，由系统回收共享段的物理内存。1643、分段保护越界检查段表寄存器：段表始址、段表长度比较：段号—段表长度、段长—段内地址存取控制检查存取控制字段只读、只执行、读/写环保护机构环的设置：0-OS;1-实用程序和OS服务；2-应用程序优先级：低编号的环具有高优先权。程序可以访问驻留在相同环或较低特权环中的数据；程序可以调用驻留在相同环或较高特权环中的服务。165小结一.存储器的装入和链接1重定位的概念、装入方式；2链接方式二.连续分区分配1各连续分配方式的实现思想；2动态分区分配的常用算法；3覆盖和对换技术的概念和引入目的三.离散分区分配

1基本分页/分段/段页式管理的原理、地址映射过程；2引入快表的地址映射过程；3分页和分段的区别166小结四.虚拟存储管理1虚拟存储器的定义和特点；2请求分页/分段管理的原理、硬件支持；3页面置换算法167小结本章重点：动态分区分配算法；地址变换页面置换算法；基本分页/分段、请求分页/分段管理的原理和地址映射机构168补充有一页式系统，其页表存放在主存中。如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间是多少？如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间为多少？解：(1)由于页表存放在主存，因此CPU必须两次访问主存才能获得所需数据，所以实现一次页面访问的存取时间是：

1.5×2=3微秒

(2)在系统增加了快表后，在快表中找到页表项的概率为85%，所以实现一次页面的访问的存取时间是0.85×1.5+(1-0.85)×2×1.5=1.725微秒1691．在虚拟存储系统中，若进程在内存中占3块(开始时为空)，采用先进先出页面淘汰算法，当执行访问页号序列为1、2、3、4、1、2、5、1、2、3、4、5、6时，将产生

次缺页中断。A．7B．8C．9D．102．系统“抖动”现象的发生是由

引起的。A．置换算法选择不当B．交换