第三章-内存管理(2)

操作系统原理与实践高等教育出版社第三章内存管理（2)主要内容3.5分页存储管理3.6分段存储管理3.7虚拟存储器3.8请求分页存储管理方式3.5.1页式存储管理的引入在动态分区的存储空间中，存在“零头”问题。尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高。3.5分页存储管理3.5.2页面与页表1.页面和物理块分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。1.页面和物理块2.页表列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。页面大小:页面的大小应选择得适中，且页面大小应是2的幂，通常为512B~8KB。2.页表一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。页表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。表目也称为页描述子。分页管理中页与页框的对应关系示意图3.地址结构分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP][3.5.3地址变换机构1.基本的地址变换机构分页系统的地址变换机构2.地址变换过程例如指令LOAD1,2500的地址变换过程如下：地址变换过程（续）把虚拟地址2500转换成页号P=2，位移量W=452；如果页号2大于页表大小，则中断；否则继续；页号2与页表起址1000运算（1000+2*20，设页描述子大小为20）得到页描述子地址为1040；从页描述子中读取块号8；根据页描述子的“存取控制”判断该指令是否被允许访问内存，如果不允许，则中断；否则继续；块号8与位移量452运算（8*1024+452=8644，1024为页面大小）得到物理地址8644；把内存地址8644单元中数字写进寄存器1。3.管理1）页表系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息2)空块管理位示图内存页表3)内存的分配与回收位示图法建立一张位示图，以反映整个存贮空间的分配情况，每一个字的每一位都对应一个物理块。0：未分配(空白块)1：已分配位字0123…………1415012…1100…………000100…………10………位示图法为了找到N个自由块，就需要搜索位示图，找到N个“0”位，再经过一个简单的换算就可得知相应的块地址(物理地址)，存贮空间的分配和回收工作较为方便，{0,1}转换。位示图法位示图法盘块的分配（1）顺序扫描找到一个或一组值为“0”的二进制位（2）转换成相应盘块号B=n×i+j（3）修改位示图map[I,j]=1位示图法盘块的回收（1）将回收盘块的盘块号转换为位示图的行号和列号i=bDIVnJ=bMODn（2）修改位示图令map[I,j]=0内存的分配计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图4.快表如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问页表，读出页描述子，之后根据形成的实际地址再访问主存，这样使访问主存的次数加倍，因而使总的处理速度明显下降。为了解决这个问题人们采用一组硬件寄存器，存放当前访问过的页的页描述子，每次访问主存时，首先查找快表，若找到所需的页描述子，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。具有快表的地址变换机构具有快表的地址变换机构3.5.4两级和多级页表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的内存空间。可采用两个方法来解决这一问题：①采用离散分配方式来解决难以找到一块连续的大内存空间的问题：②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。1.两级级页表32位进程页表多大？设：页面大小为4K用户空间4GB则：一个进程1M页设：每个内存块号4字节则：进程页表1K页,共占4M内存空间结论：一个进程的页表的各页之间可以不连续存放解决：页表本身使用地址索引——页目录1.两级页表逻辑地址结构可描述如下：两级页表结构1.两级页表页目录地址目录位移页表位移页位移虚拟地址页表地址...页目录（每进程一个）块号...页表代码或数据...内存块二级页表结构及地址映射++2.多级级页表64位进程页表多大？设：页面大小为4K用户空间则：一个进程252页设：每个内存块号4字节则：进程页表242（252/210页)，两级页表无法不能接受。结论：必需采用三级以上的多级页表。3.反置页表一般页表是按页号进行排序，而页表内容包括物理块号。反置页表则不然，它为每一个物理块设置一个表项，并将它们按物理块号进行排序，而表的内容包括对应页号及其隶属进程的标示符。在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构,造成共享、保护的困难。引入分段存储管理方式，主要是为了满足用户和程序员的下述需要：1)方便编程2)信息共享3)信息保护4)动态增长5)动态链接3.6.1分段式存储管理的引入3.6基本分段存储管理...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...3.6.2分段系统的基本原理1.分段分段地址中的地址具有如下结构：段号段内地址31161502.段表它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存,属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段地址01234操作系统分段管理中作业i与段表、存储空间的关系3.硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）4.地址变换机构分段系统的地址变换过程ClCb+段号S段内地址d比较比较b+d段表S=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d=1d=1地址映射及存储保护机制地址越界地址越界比较5.分页和分段的主要区别(1)页是信息的物理单位，段则是信息的逻辑单位；(2)页的大小固定且由系统决定，而段的长度却不固定；(3)分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的。3.6.3信息共享分页系统中共享editor的示意图分段系统中共享editor的示意图分段管理的优缺点优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片3.7段页存储管理1.产生背景：结合了段式与页式二者优点,克服了二者的缺点。2.基本思想用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址3.管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理4.地址空间和地址结构一个程序首先被划分成若干程序段，每一段给予不同的分段标识符然后，对每一分段又分成若干个固定大小的页面。如下图(a)所示，系统中的一个作业的地址空间结构页面尺寸为４Ｋ字节，该作业有三个分段，第一段为15K字节，占4页，最后一页只有1K未用；其它段同理。未足一页大小的补为一页。4.地址空间和地址结构1.作业地址空间:如图（a）所示2.地址结构如图（b）所示5.地址映射段页式系统的地址变换结构段表始址段表长度段表寄存器段号段内页号页内地址逻辑地址寄存器BlockNo分段页表BlockNo块内地址物理地址寄存器+≦越界中断页号物理块号段表段号页表长度+页表始址状态越界中断≦6.地址变换地址变换（续）从控制寄存器读取段表始址，找到段表；段号＋段表始址得到段描述子地址；从段描述子读取页表始址，找到页表；页号＋页表始址得到页描述子地址；从页描述子读取物理块号；物理块号＋页内位移量得到物理地址。上述的地址变换至少要访问主存三次，这将使执行程序的速度大大降低。为了解决上述问题，可以采取前边讲过的“快表”技术。1.交换技术与覆盖技术在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现3.8交换与覆盖共同点：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换不同点：如何控制交换？2.交换与覆盖异同点3.覆盖技术把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖对用户不透明，增加了用户负担目前这一技术用于小型系统中的系统程序的内存管理上MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构4.覆盖技术的缺点5.交换技术当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中1.选择原则:将哪个进程换出/内存？2.交换时机的确定3.交换时需要做哪些工作？4.换入回内存时位置的确定6.交换技术实现中的几个问题将哪个进程换出/内存？例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的需要特殊考虑的是：任何等待I/O进程中存在的问题解决：从不换出处于等待I/O状态的进程有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助7.选择原则何时需发生交换？例子：只要不用就换出（很少再用）只在内存空间不够或有不够的危险时换出8.交换时机的确定需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取9.交换时需要做哪些工作换出后再换入的内存位置一定要在换出前的原来位置上吗？受地址“绑定”技术的影响，即绝对地址产生时机的限制10.换入回内存时位置的确定与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段11.覆盖与交换的比较1.概述问题的提出:程序大于内存程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过