计算机操作系统(汤子瀛)版chapter4-1

第四章存储器管理(1)第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式第四章存储器管理4.1存储器的层次结构4.1.1存储器的层次结构1.存储器的层次结构在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。存储器的层次结构2.各种存储器•高速缓存Cache：少量的、非常快速、昂贵、易变的•内存RAM：若干兆字节、中等速度、中等价格、易变的•磁盘：数百兆或数千兆字节、低速、价廉、不易变的•由操作系统协调这些存储器的使用4.1.2存储管理的目的1)主存的分配和管理：当用户需要内存时,系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。2)提高主存储器的利用率：不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。存储管理的目的（续）3)“扩充”主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。4)存储保护：确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。4.1.3.基本概念1.定位（存储分配）：为具体的程序和数据等分配存储单元或存储区工作。2.映射：把逻辑地址转换为相应的物理地址的过程。3.隔离：按存取权限把合法区与非法区分隔，实现存储保护。4.名空间•程序员在程序中定义的标识符•程序符号集合•由程序员自定义•没有地址的概念符号指令数据说明I/O说明地址空间及存储空间5.地址空间•程序用来访问信息所用地址单元的集合•逻辑（相对）地址的集合•由编译程序生成6.存储空间•主存中物理单元的集合•物理（绝对）地址的集合•由装配程序等生成地址映射LoadA2003456。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000图4－1名空间、地址空间、存储空间7.逻辑地址与物理地址•逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息•物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址8.存储共享•内存共享：两个或多个进程共用内存中相同区域•目的：节省内存空间，提高内存利用率•实现进程通信（数据共享）•共享内容：代码共享，要求代码为纯代码数据共享9.存储保护与安全保护目的：为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时,不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）1)存储保护•保护系统程序区不被用户侵犯（有意或无意的）•不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）2)保护过程---防止地址越界每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。10.内存“扩充”通过虚拟存储技术实现•用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间•具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制第四章存储器管理4.2程序的装入和链接4.2程序的装入和链接图4-2-1对用户程序的处理步骤4.2.1程序的装入1.绝对装入方式程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。2.可重定位装入方式图4-2-2作业装入内存时的情况3.动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。4.2.2程序的链接图4-2-3程序链接示意图1.静态链接方式2.装入时动态链接装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。3.运行时动态链接这种链接方式是将对某些模块的链接推迟到执行时才执行，即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.2.3重定位把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。如下图，作业i经过重定位，把地址集合映射到以1000为始址的内存中，作为作业i的存储空间。1.重定位的类型1)静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）作业i在执行前一次变址，直到该作业完成退出内存为止。2)动态重定位2)动态重定位在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。2.动态重定位的实现方式•重定位寄存器：在执行一条指令取操作数时，要将指令给出的有效地址(500)与重定位寄存器中的内容（1000）相加，得访问地址（1500），从而实现了地址动态修改。•映象方式：采用页表来描述虚、实页面的对应关系。第四章存储器管理4.3连续分配存储管理4.3.1单用户存储管理•在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连续区存储管理。•单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0图4-3-1单一连续区存储分配示意图工作流程单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。工作流程(续)单用户系统缺点•不支持多道。•主存利用率不高。•程序的运行受主存容量限制。存储保护•自动地址修改例如，存储器的地址空间为１２Ｋ，而操作系统位于低址端的４Ｋ内。对于这样的系统，我们给用户一个１３位的地址空间，并对其每个存储器访问自动加上４Ｋ。如果操作系统占用高址端的４Ｋ，则我们取每一个存储访问Ｒ，而实际上，其地址为（Ｒｍｏｄ８Ｋ）。从而实现了对操作系统的保护。存储保护（续）•０页、１页寻址通过对每个用户生成的地址左端拼接上一位１来实现ＯＳ区与用户区。把操作系统确定在０页，而把用户作业放在１页。•界限寄存器通过增加界限寄存器，划分ＯＳ区与用户区。4.3.2固定分区分配分区式管理是满足多道程序的最简单的存储管理方案。它的基本思想是将内存划分成若干个连续区域，称为分区。每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运行。•预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业•存储分配：如果有一个空闲区,则分配给进程1.固定分区分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统图4-3-2固定分区示意图2.内存分配管理图4-3-3固定分区使用表通过设置内存分配表，内存分配简单缺点：内存利用率不高4.3.2可变分区分配•基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间•内存管理：设置内存空闲块表——记录了空闲区起始地址和长度•内存分配：动态分配•内存回收：当某一块归还后，前后空间合并，修改内存空闲块表1.分区分配中的数据结构(1)分区分配表（见图4-3-5）(2)空闲分区链图4-3-4空闲链结构0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表：图4-3-5分区分配表0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K2.分区分配操作1)分配内存图4-3-6内存分配流程2)回收内存图4-3-7内存回收时的情况3.空闲分区链表•为了实现动态分配，系统设立空闲分区链表：每个空闲块的前后两个单元，放置必要的说明信息和指针。系统只要设立一个链首指针，指向第一个空闲块即可。分配程序可以依照自由块链表，来查找适合的空闲块进行分配。（如下图）4.分配算法按空闲块链接的方式不同，可以有以下四种算法：•最佳适应法•最坏适应法•首次适应法•下次适应法（循环首次适应法）1)最佳适应算法•接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配•为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。•特点：用最小空间满足要求2)最坏适应算法•接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配，与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空白区。•特点：当分割后空闲块仍为较大空块分配算法（续）3)首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。4)下次适应法类似首次适应法每次分区时，总是从上次查找结束的地方开始，找到一个足够大的空白区分配。5.碎片问题•经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片•造成存储资源的浪费碎片问题的解决•紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）•问题：开销大；移动时机优点：便于动态申请内存便于共享内存便于动态链接缺点：碎片问题(外碎片)，内存利用率不高，受实际内存容量限制6.分区式存储管理的优缺点4.3.3可重定位分区分配1.动态重定位的引入图4-3-1紧凑的示意2.动态重定位的实现图4-3-2动态重定位示意图3.动态重定位分区分配算法图4-3-3动态分区分配算法流程图4.可重定位分区的优缺点•优点:解决了可变分区分配所引入的“外零头”问题。消除内存碎片，提高内存利用率。•缺点:提高硬件成本，紧凑时花费ＣＰＵ时间。5.多重分区以上讨论都是基于一个作业在主存中占据的是一个连续分区的假定。为了支持结构化程序设计，操作系统往往把一道作业分成若干片段如子程序、主程序、数据组等）。这样，片段之间就不需要连续了。只要增加一些重定位寄存器，就可以有效地控制一道作业片段之间的调用。如下图所示，作业Ａ、Ｂ分别被分成两个片段放进