第4章-存储器管理课件

第四章存储器管理4.1存储器的层次结构4.1.1多级存储器结构寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存速度↑价格↑容量↓存储管理设备管理4.1.2主存储器与寄存器1、主存储器用于保存程序运行时的程序和数据；CPU只能从主存中取得指令和数据，数据可以在主存和寄存器之间进行交换；CPU和外设交换的信息也依托于主存的地址空间。2、寄存器寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或作地址寄存器加快地址转换速度。4.1.3高速缓存和磁盘缓存1、高速缓存Cache少量的、非常快速、昂贵、易变的；将主存中一些经常访问的信息存放到高速缓存中，以减少访问主存的次数，可大大提高程序执行速度;CPU要访问一组特定信息时，先检查它是否在Cache中，在则直接取出信息，否则再访问主存，如果主存中还不存在，则检查虚拟内存，如果还不存在则从外存中调入到内存。多级缓存。一级缓存L1，速度高容量小，二级缓存L2，速度稍低容量稍大，以此类推。4.1.3高速缓存和磁盘缓存2、磁盘缓存因磁盘I/O速度<<主存的访问速度，所以，将频繁使用的一部分数据和信息，暂存在磁盘缓存中。可减少访问磁盘的次数。磁盘缓存本身并不是实际存在的存储介质，它依托于固定磁盘。提供对主存的扩充，所以，主存可看作是辅存的高速缓存。讲在前面－存储管理目的操作系统的“方便性”便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理性”合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定讲在前面－存储管理功能内存的管理、分配与回收内存空间的使用情况记录——位图、分配表、分区表内存空间的分配与回收——定长与不定长、静态与动态地址重定位（地址映射）物理地址与逻辑地址的差别实模式与保护模式共享与保护内存共享：进程与线程、中间件应用内存保护：如何防止地址越界或操作越权？内存的扩充虚拟存储：如何使用小内存空间来运行大的程序？讲在前面－地址空间程序的名空间用户编程所用的地址称为逻辑地址（或程序地址，或虚地址）。由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。地址映射LoadA2003456

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

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

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

把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。1、编辑阶段（形成符号空间）2、编译阶段（生成目标代码）

3、连接阶段(确定相对地址）将编译后得到的一组目标模块以及它们所需的库函数装配成一个完整的装入模块。4、装入阶段（可以确定物理地址）将装入模块放入分到的内存区中。这时需要进行重定位，即将装入模块的逻辑地址转变为内存的实际物理地址。5、运行阶段（可以确定物理地址）运行可执行的程序file1.exe。4.2程序的装入和链接用户GeditFile1.cgccFile1.oldFile1.exe装入程序内存进程运行编辑阶段编译阶段连接阶段装入阶段运行阶段程序处理图4.2程序的装入和链接4.2程序的装入和链接4.2.1程序的装入绝对装入方式可重定位装入方式动态运行时装入方式逻辑地址与实际内存地址一致适用于单道程序环境绝对装入方式可重定位装入方式动态运行时装入方式地址映射/地址重定位把程序中的逻辑地址变成内存中的物理地址的过程叫做重定位。静态地址映射动态地址映射4.2.1程序的装入静态重定位：在程序执行之前进行，由专门设计的重定位装配程序完成。动态重定位：在程序执行过程中，每次访问内存之前将程序地址变换为内存地址，这种变换是依靠硬件地址变换机构实现的。4.2.1程序的装入为何要进行地址映射？创建进程时，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。4.2.1程序的装入静态地址映射（静态重定位）程序被装入内存时，由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR。例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令LoadA，200就变为LoadA，1200优点：不需要硬件的支持。缺点：程序必须占用连续的内存空间，一旦程序装入后不能移动。如：LOAD1，2500这条指令是把相对地址为2500的存储单元的内容365装入1号累加器,而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500）,所以LOAD1，2500这条指令中的直接地址码要作相应的修改，即改为LOAD1，12500。4.2.1程序的装入动态地址映射（动态重定位）动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。最简单的硬件机构是重定位寄存器。在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。03456......LOADA200......0100200300.........LOADA2003456110012001300200VR+1000BR4.2.1程序的装入动态地址映射（动态重定位）过程描述：程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。4.2.1程序的装入动态地址映射（动态重定位）优点：程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。一个程序不一定要求占用一个连续的内存空间。可以部分地装入程序运行。便于多个进程共享同一个程序的代码。4.2.1程序的装入动态地址映射（动态重定位）缺点：需要硬件的支持。实现存储管理的软件算法较为复杂。4.2.1程序的装入静态重定位在装入时一次性集中把程序指令中所有地址全部加以重定位；动态重定位则是每执行一条指令时，才其地址加以重定位。静态重定位在程序运行之前完成地址转换；动态重定位则是将地址转换的时刻推迟到指令执行时进行。静态重定位和动态重定位的比较静态重定位由软件完成地址转换；动态重定位由硬件地址转换机构完成。静态重定位时原来的指令地址被修改了；实行动态重定位，不对指令本身做修改。4.2.2程序的链接静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。4.2.2程序的链接1.静态链接方式：事先进行链接，以后不再拆开将目标模块装配成装入模块时需解决的两个问题：(1)变换外部调用符号(2)对相对地址进行修改4.2.2程序的链接2.装入时动态链接：边装入边链接优点：(1)便于修改和更新(2)便于实现对目标模块的共享注：通常被链接的共享代码称为动态链接库(DLL,Dynamic-LinkLibrary)或共享库(sharedlibrary)。4.2.2程序的链接3.运行时动态链接：边执行边链接优点：加快装入过程、节省内存空间4.3连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。分类：单一连续分配固定分区分配动态分区分配可重定位分区分配4.3.1单一连续分区

最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分：系统区仅提供给OS使用，通常放在内存低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。4.3.1单一连续分区单一分区存储管理系统的特点：

总是把一个连续的用户区分配给一个用户使用，如图（a）中的a～b区域。这种系统只适用于单用户的情况。进入内存的作业，独享系统中的所有资源，包括内存中的整个用户区。由于整个用户区都分配给了一个用户，因此作业程序进入用户区后，没有移动的必要。所以采用这种存储管理策略，对用户程序实行静态重定位。4.3.1单一连续分区单一连续区存储分配示意图作业3作业2作业1内存0ab操作系统用户区内存0ab操作系统使用区空闲区用户区c(a)(b)4.3.2固定分区分配基本原理及技术把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个分区。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行问题：可能存在内碎片。内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。4.3.2固定分区分配划分分区的方法分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。缺乏灵活性。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。4.3.2固定分区分配内存操作系统第1分区（作业1）第2分区（作业2）第3分区（作业3）0abcdab-a基址寄存器界限寄存器CPU在固定分区存储管理中，每个分区只允许装入一个作业，作业在运行期间不会移动。因此，这时应该对程序实行静态重定位。在固定分区存储管理中，要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间形成的侵扰。因此必须在CPU中设置一对专用的寄存器，用于实现存储保护。两个专用寄存器起名为“基址寄存器”和“界限寄存器”。调度程序调度某个作业运行时，就把该作业所在分区的起始地址装入基址寄存器，把分区长度装入界限寄存器。4.3.2固定分区分配未分配1281284已分配64643已分配32322已分配2481状态起址(K)大小(K)分区号分区说明表作业C作业B作业A操作系统24K32K64K128K256K存储空间分配情况

当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。4.3.3动态分区分配在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。优点：没有内碎片。缺点：有外碎片；在实现过程中涉及三个问题：分区分配中的数据结构分区分配算法分区分配操作4.3.3动态分区分配基本思想:作业要求装入内存时，若内存有足够的连续存储空间供使用，那就依作业相对地址空间的大小，划分出一个分区分配给它。作业C10KB作业B20KB作业A15KB内存操作系统空闲区(a)内存操作系统空闲区作业A15KB内存操作系统空闲区作业A15KB作业B20KB内存操作系统空闲区作业A15KB作业B20KB作业C10KB(b)(c)(d)(e)图（a）表明后备作业队列里，作业A需要内存15KB，作业B需要20KB，作业C需要10KB，等等。图（b）表示系统初启时的情形，整个系统里没有作业运行，用户区空闲。图（c）表示作业A装入内存时，为它划分了尺寸为15KB的分区。用户区被分成两个分区，一个是已分配的，一个是空闲区。图（d）表示作业B装入内存时，为它划分了尺寸为20KB的分区，此时的用户区被分成了三个分区；图（e）表示作业C装入内存时，为它划分了一个尺寸为10KB的分区，此时的用户区被分成了四个分区。4.3.3动态分区分配随着作业对存储区域的不断申请与释放，发展趋势是：分区的数目会逐渐增加，有的分区尺寸在逐渐减小，甚至有可能出现内存里有空闲区、但每个都满足不了作业程序的要求而无法分配出去的情形。在存储管理中，把那些无法满足作业存储请求的空闲区称为“外部碎片”。内存操作系统空闲区236(a)020256内存操作系统空闲区220(b)020256作业A16作业B100内存操作系统空闲区120(c)020作业A16256作业C7036136作业B100内存操作系统空闲区50(d)020作业A1625636136作业C70空闲区100内存操作系统空闲区50(e)020作业A1625636136作业C70空闲区25内存操作系统空闲区50(f)020作业A1625636136作业D7520620620611136实行可变分区存储管理必须解决的问题：采用地址动态重定位技术，使程序能在内存中移动，为空闲区的合并提供保证。记住各个分区的使用情况，当一个分区被释放时，能方便地判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。给出分区分配算法。4.3.3动态分区分配1.分区分配中的数据结构空闲分区表空闲分区链空闲链结构4.3.3动态分区分配0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空分区分配表2常用的分配算法(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法(4)最差适应算法(5)快速适应算法4.3.3动态分区分配4.3.3动态分区分配优点：优先利用内存低址部分的内存空间缺点：低址部分不断划分，产生小碎片；每次查找从低址部分开始，增加了查找的开销空闲区首址空闲区长度128641024256322560......(1)首次适应算法FF(最先匹配法(first-fit))首址递增排列。4.3.3动态分区分配优点：使内存空闲分区分布均匀，减少查找的开销缺点：缺乏大的空闲分区(2)循环首次适应算法(下次匹配法(next-fit))在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现算法，需要：设置一起始查寻指针采用循环查找方式4.3.3动态分区分配(3)最佳适应算法(最佳匹配法(best-fit))

空闲区大小递增排列！

缺点：产生许多难以利用的小空闲区（外碎片）(4)最差适应算法(最坏匹配法(worst-fit))

空闲区大小递减排列！基本不留下小空闲分区，但较大的空闲分区不被保留。4.3.3动态分区分配(5)快速适应算法(分类搜索法(quick-fit))

将空闲区按容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲区链表，同时，在内存中设立一张管理索引表，此表的每一项对应一种空闲分区类型，并记录了该类型空闲分区链表表头指针。 优点：查找效率高； 缺点：分区归还主存时算法复杂，系统开销大。是一种以空间换时间的算法。3分区分配操作分配内存设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size-u.sizesize(规定的不再切割的分区大小)，说明多余部分太小，可不在切割，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中；将分配区首址返回给调用者。4.3.3动态分区分配回收内存： 当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，此时可能有四种情况：(1)回收区与插入点的前一个分区F1邻接：将回收区与F1合并，修改F1的表项的分区大小；(2)回收区与插入点的后一个分区F2邻接：将回收区与F2合并，修改F2的表项的首址、分区大小；4.3.3动态分区分配(3)回收区与插入点的前后两个分区F1、F2邻接：将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和；(4)回收区既不与F1邻接，又不与F2邻接：为回收区单独建立新表项，填写回收区的首址与大小，根据其首址插到空闲链中的适当位置。4.3.3动态分区分配4.3.3动态分区分配4.3.3动态分区分配内存回收流程【例】有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按首次适应法、最佳适应法、最坏适应法三种算法组成的空闲区队列。

说明：下图中，灰色区域表示空闲分区。【结论】经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。举例举例【练习】有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。练习【思考】用可变分区(动态重定位)方式管理主存时,假定主存中按地址顺序依次有5个空闲区，空闲区的大小依次为32K，10K，5K，228K和100K，现有5个作业A，B，C，D，E。它们各需主存1K，10K，108K，28K和115K。若采用最先适应算法能把这5个作业按顺序全部装入主存吗？你认为怎样的次序装入这5个作业可使主存的利用率最高？思考无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，l≤k≤m)。通常2m是整个可分配内存的大小(也就是最大分区的大小)。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了k个空闲分区链表。4.3.4伙伴系统4.3.4伙伴系统在伙伴系统中，对于一个大小为2k，地址为x的内存块，其伙伴块的地址则用buddyk(x)表示，其通式为：在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应索引表的表项也就较多，因此会显著地增加搜索索引表的表项的时间开销。4.3.5哈希算法4.3.6可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。作业的移动需重定位。是动态（因作业已经装入）操作系统用户程序110kb用户程序330kb用户程序614kb用户程序926kb操作系统用户程序1用户程序3用户程序6用户程序980KB紧凑紧凑前紧凑后2、动态重定位的实现load1,2500365load1,25003650100250050002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址3.动态分区分配算法4.3.7对换1.对换(Swapping)的引入多道程序环境下存在的问题：阻塞进程占据大量内存空间许多作业在外存而不能进入内存运行所有可运行的进程必须小于内存空间当进程处于阻塞或就绪时交换到磁盘进程在运行过程中将多次进出内存4.3.7对换4.3.7对换所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程和进程所需要的程序和数据，调入内存。分类：整体对换(或进程对换)：以整个进程为单位广泛用于分时系统页面对换或分段对换：以页或段为单位支持虚拟存储系统4.3.7对换实现进程对换，系统必须具备的功能：对换空间的管理进程的换出进程的换入4.3.7对换2.

对换空间的管理存储内容驻留时间主要目标分配方式文件区文件较长久提高文件存储空间的利用率离散对换区从内存换出的进程短暂提高进程换入和换出的速度连续在系统中设置相应的数据结构以记录外存的使用情况对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。4.3.7对换3.进程的换出与换入进程的换出

过程：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。进程的换入

系统应定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将换出最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。4.4基本分页存储管理连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式:分页存储管理方式：离散分配的基本单位是页分段存储管理方式：离散分配的基本单位是段段页存储管理方式：分页与分段相结合的管理方式4.4基本分页存储管理基本的分页存储管理方式(或纯分页存储管理方式)：不具备页面对换功能，不具有支持实现虚拟存储器的功能，要求把每个作业全部装入内存后方能运行1.页面将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始。把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。4.4.1页面与页表4.4.1页面与页表Page3Page2Page1Page0Page0Page3Page1Page2Logicalmemoryphysicalmemory0123456710734块号321页号Pagetable页内碎片页面太小优点：可使内存碎片减小，有利于提高内存利用率；缺点：①使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；②会降低页面换进换出的效率。页面较大优点：可以减少页表的长度，提高页面换进换出的速度；缺点：会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512B~8KB。4.4.1页面与页表页表 为了便于在内存找到进程的每个页面所对应块，系统为每个进程建立一张页面映象，简称页表。记录了页面在内存中对应的块号页表一般存放在内存中页表的基址及长度由页表寄存器给出访问一个字节的数据/指令需访问内存2次(页表一次,内存一次)，所以出现内存访问速度降低的问题。4.4.1页面与页表2.地址结构4.4.1页面与页表位移量W页号P3112110地址长度32位:011位为位移量(页内地址)，即每页的大小为4KB1231位为页号，地址空间最多允许有1M(220)页若给定一个逻辑地址空间中的地址为A，页面大小为L，则:

页号P=INT[A/L]页内地址d=[A]MODL【例】系统页面大小为1KB，设A=2170B，则: P=2，d=1224.4.1页面与页表n页…5页4页3页2页1页0页用户程序……59483623120页号块号页表内存203456789101页表的作用：4.4.2地址变换机构完成：逻辑页号—物理块号的映射，由页表完成。一、基本地址变换机构页表长度页表始址页表寄存器页内地址页号(3)逻辑地址L物理地址<+越界中断页表分页系统的地址变换机构块号*页面大小+页内地址页表始址+页号*页长度b1块号页号01234★逻辑地址1023：1023/1K得页号为0，页内地址为1023，查页表找到对应得物理块为2，故物理地址为 2*1K+1023=3071。★逻辑地址2500：2500/1K得页号为2，页内地址为452，查页表找到对应得物理块为6，故物理地址为 6*1K+452=6596。★逻辑地址4500：4500/1K得页号为4，页内地址为404，页号大于页表长度，产生越界中断【例1】某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、4500转换为物理地址【例2】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址需要多少位表示？（二进制）（2）绝对地址需要多少位表示？（二进制）地址转换例子2【解答】因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的绝对地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。地址转换例子2【例3】某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下： 页号 物理块号

0 5 1 10 2 4 3 7则逻辑地址0A5C(H)所对应的物理地址是什么？地址转换例子3【分析】页式存储管理的逻辑地址分为两部分：页号和页内地址。 由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。【解答】逻辑地址0A5C（H）所对应的二进制表示形式是：000101001011100

，根据上面的分析，下划线部分为页内地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：0100，拼接块内地址1001011100，得01001001011100，即125C（H）。地址转换例子3课堂练习假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2、4、1、6块。试问：该作业的总长度是多少字节？写出该作业每一页在主存中的起始地址；对多个逻辑地址[0，100]、[1，50]、[2，0]、[3，60]，试计算出相应的内存地址。4.4.2地址变换机构2.具有快表的地址变换机构CPU在每存取一个数据时，需要两次访问内存：第一次：访问内存中的页表，找到指定页的物理块号，将块号与页内偏移量拼接形成物理地址。第二次：从第一次所得地址中获得所需数据，或向此地址中写入数据。处理速度降低！解决方法：在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。页表长度页表始址页表寄存器页内地址页号(3)逻辑地址Ldb物理地址<+越界中断b1块号页号页表具有快表的分页系统的地址变换机构：b块号页号快表输入寄存器【例】有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?注：有效访问内存的时间

T=PTLB*（TTLB+TM）+（1-PTLB）*（TTLB+2TM）其中,PTLB为快表的命中率,TTLB为快表的访问时间,TM为内存的访问时间4.4.2地址变换机构【答】若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

=1.5*2=3(μs)■增加快表后的存取访问时间

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)4.4.2地址变换机构4.4.3两级和多级页表现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M（232/212=220）个，若每个页表项占用1个字节，则每个进程的页表就要占据1MB的内存空间，而且要求连续存放。解决方法：采用离散方式只将当前所需页表项调入内存4.4.3两级和多级页表两级页表将页表分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散分配的页表再建立一张页表，称为外层页表，其每个页表项记录了页表页面的物理块号。页内地址外层页内地址外层页号dp2p1312221121104.4.3两级和多级页表例如：32位逻辑地址空间，页面大小为4KB(即12位)，若采用一级页表机构，应有20位页号，即页表项应有1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即………012345671141151468内存空间…641第0页页表012…1023115114第1页页表012…10231468第n页页表012…1023174210781011012n外部页表两级分页结构4.4.3两级和多级页表外部页表寄存器外部页表页表db物理地址++dP2P1逻辑地址外部页号外部页内地址页内地址具有两级页表的地址变换机构：4.4.3两级和多级页表上述方法用离散分配空间解决了大页表无需大片存储空间的问题，但并未减少页表所占的内存空间。解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。2.多级页表两级页表对32位机器适用，64位呢？页面大小为4KB即212B，还剩52位，按物理块大小212位来划分页表，则剩余40位用于外层页号，此时外层页表可能有1024G个页表项，要占用4096GB的连续存储空间解决方法：采用多级页表，将外层页表再进行分页。4.5基本分段存储管理4.5.1分段存储管理方式的引入主要是满足用户和编程员的多方面要求：方便编程信息共享信息保护动态增长动态链接4.5.2分段系统的基本原理页式管理是把逻辑地址空间视为一维线性空间；而段式管理是把逻辑地址空间视为二维空间。物理地址空间是一维的。将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。4.5.2分段系统的基本原理1分段在分段存储管理方式中，作业地址空间被划分为若干个段，每个段定义了一组逻辑信息，都有自己的名字。通常用段号代替段名，每段从0开始编址，并采用一段连续地址空间。段长由逻辑信息组的长度决定。整个作业的地址空间分成多个段，逻辑地址由段号(段名)和段内地址所组成。该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。段内地址段号31161504.5.2分段系统的基本原理2段表在分段式存储管理系统中，系统为每个分段分配一个连续的分区，而进程中的各个段可以离散地装入内存中不同的分区中。为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(基址)和段的长度。作业空间(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K150K10K120K15K80K20K40K30K0123段号段长基址段表(S)=310K(D)=215K(X)=120K(MAIN)=030K内存空间040K80K120K150K利用段表实现地址映射段表长度段表始址控制寄存器物理地址<+越界中断分段系统的地址变换机构：1002段号S位移量W段表92002008K5004K6006K1K段长基址段号0123+82928K82928692主存3地址变换机构段表始址+段号*段表长度基址+位移量W4.5.2分段系统的基本原理4.分页和分段的主要区别相似点采用离散分配方式;通过地址映射机构实现地址变换4.5.2分段系统的基本原理页式存储管理段式存储管理目的实现非连续分配,解决碎片问题更好满足用户需要信息单位页（物理单位）段（逻辑单位）大小固定（由系统定）不定（由用户程序定）内存分配单位页段作业地址空间一维二维优点有效解决了碎片问题有效提高内存的利用率更好地实现数据共享与保护段长可动态增长便于动态链接4.5.3信息共享分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统方便。在分段系统中，实现共享十分容易，只需在每个进程的段表中为共享程序设置一个段表项。【例】40个用户同时执行一个文本编辑程序。4.5.3信息共享【分析】不共享：共需内存：40*(160+40)KB=8000KB共享Editor：共需内存：40*40+160KB=1760KB分页共享：设页大小为4KB，则160KB的代码要40个页，数据区要10个页，另外，要在每个进程的页表中建立40个页表项，同时，也要为自己的数据区建立10个页表项。分段共享：只需在每个进程的段表中为共享程序设置一个段表项。data10…data1ed40…ed2ed1进程1data10…data1ed40…ed2ed1进程270…6160…2221页表80…7160…2221页表data10…data1data10…data1ed40…ed2ed1…021226061707180主存分页系统中共享editordata1editor进程1data2editor进程22404080160基址段长段表3804080160基址段长段表data2…data1editor80240280380420主存分段系统中共享editor可重入代码又称为纯代码，是一种允许多个进程同时访问的代码，可重入代码不允许任何进程对它进行修改。4.5.4段页式存储管理分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。把两者结合成一种新的存储管理方式——段页式存储管理方式，具有两者的长处。1.基本原理先将用户程序分成若干段，再把每个段分成若干页，并为每个段赋予一个段名。4.5.4段页式存储管理在段页式系统中，地址结构由段号、段内页号和页内地址三部分所组成。内存空间划分：(同页式)静态等长，2i,称为一页。物理地址=(块号,块内地址)=(f,w)

进程空间划分：一个进程若干个段一个段若干个页逻辑地址=(段号,逻辑页号,页内地址)=(s,p,w)注意：对用户而言，仍然是二维编址。 对系统而言，则是三维编址4.5.4段页式存储管理04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K数据段作业地址空间：地址结构：页内地址(W)段内页号(P)段号(S)0页1页2页0页1页第1段：0页1页2页第0段：第2段：25页26页27页28页29页30页31页32页33页......内存空间进程空间4.5.4段页式存储管理在段页式系统中，为了获得一条指令或数据，需要访问三次内存：第一次：访问内存中的段表，取得页表始址第二次：访问内存中的页表，取得该页所在的物理块号，将块号与页内地址形成物理地址第三次：访问第二次所得的地址，取出指令或数据为提高执行速度可增设高速缓冲寄存器。4.5.4段页式存储管理利用段表和页表实现地址映射4.5.4段页式存储管理每个进程一张段表,每个段一张页表.段表含段号,页表始址和页表长度.页表含页号和块号.进行地址变换:

先用段号与段寄存器中的段长进行比较，若小于段长则利用段表始址和段号找出该段页表的始址,(否则越界中断)，再用逻辑地址中的段内页号在页表中找到相应的块号，最后与页内位移形成物理地址。段表长度段表始址段表寄存器块内地址块号b物理地址>+段超长段页式系统的地址变换机构：页内地址页号P段号Sb1块号页号页表0123+段表0123页表长度页表始址本章基础要点重定位是指

；重定位的方式有两种：从作业的逻辑地址到物理地址的转换过程。静态重定位和动态重定位。动态重定位的特点是：由硬件实现，在运行过程中进行地址变换。若计算机CPU给出的有效地址长度为32位,内存为32M，则该机的存储空间为

M，作业的地址空间为

：32M，232B。如果一个程序为多个进程所共享，那么该程序的代码在执行的过程中不能被修改即程序应该是：可重入码（纯代码）。本章基础要点把作业装入内存时随即进行地址变换的方式称为

；而在作业执行期间，当访问到指令或数据时才进行地址变换的方式称为

。静态重定位；动态重定位。用户程序中的地址称为逻辑地址，逻辑地址的集合称为

；内存中的地址称为物理地址，物理地址的集合称为

。地址空间；存储（物理）空间。在动态分区分配算法中，首次适应算法倾向于优先利用内存中的

地址部分的空闲分区，从而保留了

地址部分的大空闲区。

低；高。本章基础要点在分区管理中的移动（紧缩）技术可以集中

，消除

。空闲分区，外碎片。在可变分区管理中，分区的保护通常采用：界限寄存器。最佳适应算法是将作业放置到：

能满足要求的最小空闲。最佳适应算法的空闲区是按

顺序排列的。

大小递增。首次适应算法的空闲区是按

顺序排列的。

地址递增。本章基础要点在某系统中采用基址、限长寄存器的方法来保护存储信息，判断是否越界的条件是

。0≤被访问的逻辑地址＜限长寄存器的内容。内存中无法被利用的存储空间称为：碎片或零头。在存储管理中采用覆盖与交换技术的目的是：

节省内存空间、提高并发运行作业数。采用交换技术获得的好处是以牺牲

为代价的。CPU时间。