第5章 存储器管理2_chd

第五章存储管理（2）概述分区存储管理页式存储管理交换技术与覆盖技术虚拟存储程序的装入和链接对用户程序的处理步骤程序的装入1.绝对装入方式程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。2.可重定位装入方式作业装入内存时的情况在装入时对目标程序中指令和数据的修改过程称为重定位。因地址变换是在装入时一次完成的，以后不再改变，故称为静态重定位。--------导致不允许程序运行时在内存中移动位置3.动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，需重定位寄存器的支持程序的链接图程序链接示意图1.静态链接方式两个问题需解决：相对地址的修改、变换外部调用符号这种先进行链接所形成的一个完整的装入模块称为可执行文件通常不再拆开它，要运行时可直接装入内存若要修改或更新其中的某个目标模块，则要求重新打开装入模块2.装入时动态链接装入目标模块时，边装入边链接。装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。3.运行时动态链接这种链接方式是将对某些模块的链接推迟到执行时才执行，即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。5.3单用户连续存储管理单用户存储管理在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连续区存储管理。单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0图单一连续区存储分配示意图工作流程单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。工作流程(续)分时系统中可用对换方式让多个用户的作业轮流进入主存储器执行按时间片方式轮流地被换出和换入。由于单用户连续存储管理每次只允许一个作业进入主存储器，因此不必考虑作业在主存的移动问题，可用静态重定位硬件不必有地址转换机构单用户系统缺点不支持多道。主存利用率不高。程序的运行受主存容量限制。存储保护自动地址修改例如，存储器的地址空间为１２Ｋ，而操作系统位于低址端的４Ｋ内。对于这样的系统，我们给用户一个１３位的地址空间，并对其每个存储器访问自动加上４Ｋ。如果操作系统占用高址端的４Ｋ，则我们取每一个存储访问Ｒ，而实际上，其地址为（Ｒｍｏｄ８Ｋ）。从而实现了对操作系统的保护。存储保护（续）０页、１页寻址通过对每个用户生成的地址左端拼接上一位１来实现ＯＳ区与用户区。把操作系统确定在０页，而把用户作业放在１页。界限寄存器通过增加界限寄存器，划分ＯＳ区与用户区。分区存储管理方案系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区固定分区可变分区5.4固定分区存储管理预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只能装一个作业存储分配：如果有一个空闲区，则分配给进程分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统内存分配管理图4-3-3固定分区使用表（教材上用标志0代表未分配）通过设置内存分配表，内存分配简单固定分区分配算法要求xk大小的分区取内存分配表表的第一项该分区空闲吗？分区大小xk表结束吗？返回分区号状态位置1无法分配取下一项NNNYYY5.4.2地址转换和存储保护作业执行过程中不会改变存放区域，可采用静态重定位方式存储保护：一对寄存器，“下限寄存器”、“上限寄存器”5.4.3如何提高主存空间的利用率根据经常出现作业的大小和数量来划分分区，尽可能使每个分区被充分利用分区按大小排列按作业对主存空间的需求量排成多个作业队列（防止小作业装入大分区，减少闲置的主存空间量）基本思想内存不是预先划分好的作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用0～20KB的内存空间，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它，如图所示。5.5可变分区存储管理方案当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区。分区存储管理技术的实现：1、地址映射2、动态存储管理的机构（数据结构）3、分区的分配和回收4、三种基本的主存分配方法1、用基地址寄存器实现动态地址映射在这种存储管理技术中，系现设置一个专用寄存器，称为基地址寄存器，当一个进程（或程序、作业）被调度运行时，系统首先从PCB中取出该进程的首地址装入基地址寄存器中，在该进程运行的过程中实现动态地址映射。2、分区分配机构分区存储管理使用的数据结构主要是空闲区表、空闲区队列两种。其形式如图所示。0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度状态15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K分区的分配与回收一、分配算法介绍空闲区表数据结构的分配算法。注：1、分配算法中切割空闲区是从低地址开始的，例如，一个空闲区大小是100KB，首址是230KB，一申请者要求80KB，分配时将从230KB开始的80KB分配给申请者，剩下的部分仍作为一个空闲区，其首址是310KB，大小是20KB。2、门限值是切割空闲区后剩下的区域若小于门限值，就不切割该空闲区，统统分给申请者。分区分配操作1)分配内存图4-3-6内存分配流程分区的分配与回收二、回收算法当一个进程（或程序）释放某内存区时，要调用存储区释放算法release,它将首先检查释放区是否与空闲区表（队列）中的其它空闲区相邻，若相邻则合并成一个空闲区，否则，将释放为一个空闲区插入空闲区表（或队列）中的适当位置。空闲释放区与空闲区相邻有四种情况。分区的分配与回收A、将r合并到f1，f1.addr;f1.size+r.size=f.sizeB、将r合并到f2,r.addr;r.size+r.size=f2.sizeC、f1、r、f2合并到f1,f1.addr;f1.size+r.size+f2.size=f1.size撤消f2空闲区D、r作为一个空闲区，并插入到空闲区表的适当位置。内存分配动态分配四种分配算法：首次适应算法、循环首次适应、最佳适应算法、最坏适应算法(i)首次适应算法(FirstFit:FF)顺序查找空闲区表，找到第一个满足的就分割。分配算法简单，但可能把大的主存空间分割成许多小的空闲区，即碎片分区管理算法(可适应于固定分区及可变分区)改进：将空白区按存贮顺序链成一个队列，用一指针指向队首分配时将找到的第一个满足要求的空白区分配给它。分配时总是利用低地址部分空闲区，使高地址部分保持有较大的空闲区例：指针10k60k90k20k有四块空白区(从低地址高地址)，来了一个作业需分配19k内存。指针10k60k90k20k41k在高地址空白区中保持较大空白区(每次从10k开始分配寻找)。解：FF特点：(ii)循环首次适应(Nextfit:NF)将空白区组成环状队列，按循环顺序寻找空白区，从上次找到的空闲分区的下一个空闲分区开始查找。(与FF区别，头指针从低地址开始向高地址循环移动)12指针移动使得小空白区均匀分布，易于与其它空白区合并。NF特点：(iii)最佳适应算法(Bestfit:BF)将空白区按大小排成队列，寻找时总是以最小的空白区开始，找到第一个合适的分区指针10k60k90k20k例：来一个19k的作业最佳地利用分区；开销比较大，并不是最好算法。指针10k20k60k90k1k特点：解：(iv)最坏适应算法(Worstfit:WF)将空白区排序(按从大到小)找最大空白区如上例：指针90k60k20k10k71k不会出现小的空白区。特点：例：设系统空白链表为指针7k3k10k8k20k5kabcdef用户先后申请7.5k，4k试用四种算法，求出分配块。FF:c,a3k3k2.5k8k20k5kabcdefNF:c,d7k3k2.5k4k20k5kabcdef3k5k7k8k10k20kbfadceBF:首先从小到大排序7k3k10k8k20k5kabcdef先后申请7.5k，4k3k5k7k0.5k10k20kbfadce3k5k7k0.5k10k20kbfadce后申请4k，再排序从小到大分配块为d,f先申请7.5k0.5k3k1k7k10k20kdbface8.5k10k8k7k5k3kecdafbWF:e,e7k3k10k8k20k5kabcdef题目：先后申请7.5k，4k20k10k8k7k5k3kecdafb先排序：5.5.2地址转换和存储保护采用动态重定位方式装入作业硬件设专用控制寄存器：基址寄存器和限长寄存器（作业所占分区的最大地址）基址寄存器内容=绝对地址=限长寄存器内容（p49图3-13）可变式分区与固定式分区分配方案相比，一般来说其存储空间的利用率高些，但是，由于存在着一些分散的，较小的空白区，仍然不能充分利用－称之为存储器的“零头”。(d)碎片(零头)问题：存在于已分配的分区之间的一些不能充分利用的空白区(i)原因：请求释放使存区分割(ii)碎片总和nk，但不能装入nk作业将碎片集中(紧凑或拼接)–––可重定位分配可重定位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术解决“零头”。（移动：把作业从一个存储区域移到另一个存储区域的工作）(iii)解决的方法：移动技术达到两个目的：1集中分散的空闲区2便于作业动态扩充主存可重定位分区分配(a)概要：移动内存已分配区的信息，使得所有分配区靠在一起使空白区连成一片，采用浮动方法。(b)紧凑(重定位－动态)进行主存的压缩，就要将主存中用户程序移动(浮动)，对作业中与地址有关的部分进行调整。请求分配一个大小为xk的分区有大于xk的空闲区吗？空闲区的总和xk吗？紧缩存储并相应地修改诸表(得到一个完整的空闲区xk)分配分区并修改诸表此刻已经分配一个分区返回一个分区号数是是否否(c)动态重定位可变分区分配算法：例20k28k88k132k182ko.s作业1(8k)(36k)作业3(24k)(24k)作业2(20k)作业4(50k)(74k)64k112k256k(a)初始状态20k2