计算机操作系统存储器管理.ppt
第四章,存储器管理,4.1 程序的装入和链接,编辑编译链接装入运行图4.1,4.1.1 程序的装入,1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图42问题：如何知道哪些位置需调整？链接时产生可装入模块的具体功能?,0,1000,2500,5000,LOAD 1,2500,LOAD 1,2500,365,365,10000,11000,12500,15000,作业地址空间,内存空间,图4-2,4.1.1 程序的装入,3.动态运行时装入在装入后不能移动，该情况一般在执行时才完成相对绝对地址的转换且有硬件的支持,能保证进程的可移动性。,4.1.2 程序的链接,1、静态链接a对相对地址的修改b变换外部调用符号2、装入时动态链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接,模块ACALL B;RETURN,模块BCALL C;RETURN,模块CRETURN,0,L-1,0,M-1,0,N-1,(a)目标模块,模块AJSR L;RETURN,模块BJSR L+M;RETURN,模块CRETURN,0,L-1,L,L+M-1,L+M,L+M+N-1,(b)装入模块,4.2连续分配方式,单一连续分配用于单用户，单任务中分区式分配固定式可变式可重定位分区分配,4.2.1 单一连续分区,系统区用户区存贮保护一般不设置保护也可，因单任务。,4.2.2 固定分区,特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构 将分区按大小排序，并将其地址、分配标识作记录例：dos的MCB三、特点：简单，有碎片（内零头）,图44a,图44b,24K,32K,64K,128K,256K,分配情况,4.2.3 可变式分区（比固定式分区有改善）,一、数据结构1空闲分区表2空闲分区链,4.2.3 可变式分区（比固定式分区有改善）,二、分配算法1首次适应算法FF。要求：分区按低址高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。,4.2.3 可变式分区（比固定式分区有改善）,三、分区分配1分配：图4-62回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。,4-7 内存回收时的情况,4.2.4 可重定位分区分配,1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。作业的移动需重定位。是动态（因作业已经装入）,紧凑,2、动态重定位的实现,0,100,2500,5000,2500,10000,10000,10100,+,12500,15000,作业J,处理机一侧,存储器一侧,重定位寄存器,相对地址,图4.10动态分区分配算法,4.2.5 对换,1 对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持2 对换空间的管理外存 对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。,4.2.5 对换,3 换出与换入一、换出1选出被换出进程：因素：优先级，驻留时间，进程状态2换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）二、换入：1选择换入进程：优先级，换出时间等。2申请内存。3换入,4.3基本分页存储管理,连续分配引起:碎片碎片问题的解决：紧凑方式消耗系统开销。离散分配分页、分段、段页,1.页面页面和物理块：逻辑空间和内存空间由机器的地址结构决定页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构3112 110逻辑地址A；页大小L(设为1024)；页内偏移dd=A mod L如：A2170B.则P=2,d=122,页面与页表,3.页表,用户程序,页表,页号,块号,内存,4.2 地址变换机构,完成：逻辑页号物理块号的映射，由页表完成。一、基本地址变换机构：越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。,2.具有快表的地址变换机构,不具快表，则需两次访问内存。（1）访页表（2）得到绝对地址内容有快表，速度提高。快表贵，不能太多。,2.具有快表的地址变换机构,例：有一页式系统，其页表存放在主存中：如果对主存的一次存取需要1.5 s,试问实现一次页面访问的存取时间是多少?如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?,答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。页表在主存的存取访问时间=1.5*2=3(s)增加快表后的存取访问时间=0.85*1.5+(1-0.85)*2*1.5=1.725(s),4.3.3 两级和多级页表,页表可能很大，将其离散存放在不同页块中。建一“外部页表”来管理这些离散页表块。相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。64位机器页表一般3级，最外层页表常驻。,例,某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：,则逻辑地址0A5C（H）所对应的物理地址为：125C,例,0A5C0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C,4.4基本分段存储管理,即多重定位分区管理 引入 每个段可有其逻辑意义及功能，使得便于（1）方便编程；（2）分段共享；（3）分段保护；（4）动态链接；（5）动态增长；（如数据段的增长）,4.4.2 分段系统的基本原理,分段对用户而言，分段是2维的。段号+段内地址。段表：逻辑段map物理段地址变换机构：图416，417分页与分段：（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维,4.4.3 共享,段式系统易于共享例：图4-18及4-19 分页与分段共享比较可重入码（纯代码）各个进程应保留局部数据区,进程1,进程2,页表,页表,主存,分页系统中共享editor,分段系统中共享editor,4.4.4 段页式存储管理,分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。一、段页式系统基本原理图4-20 图4-21段号+段内页号+页内地址注意：对用户而言，仍然是二维编址。对系统而言，则是三维编址,4.4.4 段页式存储管理,二、地址变换图4-22三次访内存操作，为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache）,4.5虚拟存储器,4.5.1 引入1.常规存储管理的特征：一次性（指全部装入）、驻留性（指驻留在内存不换出）2、局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3、虚拟存贮器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚拟大小由_决定。,4.5.2 虚拟存储器的实现方式,需要动态重定位一、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）二、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）,4.5.3 虚存特征,1离散性：部分装入（若连续则不可能提供虚存），无法支持大作业小内存运行2多次性：局部装入，多次装入。3对换性：4虚拟性.,4.6.1 请求分页中的数据结构及硬件支持一、页表机制页表项：二、缺页中断机构：可在指令执行期间产生（如图4-23）转入缺页中断处理程序。三、地址变换机构比较简单分页机制，增加了中断处理，图4.24,4.6 请求分页存储管理,图423涉及6次缺页中断的指令,4.6.2 内存分配策略和分配算法,一、最小物理块数不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。Mov A,B,4.6.2 内存分配策略和分配算法,二、页面分配和置换策略。1固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高 多：浪费)2.可变分配全局置换3.可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。,三、分配算法,1平均分配算法2按进程大小比例分配算法：3考虑优先权分配算法,4.6.3 页面调入策略,1.调入时机：预调：（根据空间局部性）目前：成功率50请求调：较费系统开销各有优劣2从何处调页：对换区：修改过的页被换出时入对换区，快文件区：稍慢对共享页，应判断其是否在内存区。3.页面调入过程,目的：减少对换量，提高系统性能 4.7.1 最佳置换算法和先进先出算法一、最佳置换算法（理论上的）,4.7 页置换算法,4.7 页置换算法,目的：减少对换量，提高系统性能 4.7.1 最佳置换算法和先进先出算法二、FIFO,4.7.2 最近最久未用LRU置换,一、算法描述将“最近的过去”，作为“最近的将来”。图4-27二、LRU算法的硬件支持：（用来记录谁最近最久未访问）1位移寄存器：（定时右移）R=Rn-1R0图4-282栈：当进程访问某页时，将其移出压入“栈顶”，“栈底”换出。图4-29,LRU,4.7.3 clock置换（LRU近似算法：硬件消耗少）,一、简单算法：设一访问位：图4-30循环扫描，每次扫描时将访问位复位。,4.7.3 clock置换（LRU近似算法：硬件消耗少）,二、改进：A=0;M=0,4.7.4 其它,一、最少使用（是频率）与LRU类似（记录访问次数），设置一个访问计数器。二、页面缓冲算法：特点：淘汰的页只是修改标志；若页被修改过，则在欲复盖它时回写，否则成批回写。在欲重访问该页时，若页换出则只需修改标志。补充：80386的页描述。,4.8 请求分段存储管理方式,段表：段名 段长 段基址 存取方式 访问字段A 修改字段M 存在位P 增补位 外存起址二、缺段中断机构：段不定长，处理起来比缺页中断复杂。图4.31三、地址变换机构图4.32,4.8.2 分段的共享与保护,一、共享段表：（整个系统一张）图4.331.共享进程计数。2.存取控制字段。3.段号：不同的进程可以使用不同的段号去共享段。,4.8.2 分段的共享与保护,二、共享段的分配与回收1.分配：第一次访问：分配内存，（1）增加共享段表；（2）修改进程段表。第二次访问：（1）修改共享段表；（2）修改进程段表。2.回收：（1）count=0（2）count0,4.8.2 分段的共享与保护,三、分段保护1.越界检查段号越界检查。段内偏移越界检查。2.存取控制检查。R；R/W；E3.环保护机构（1）内环可访问外环数据；（2）外环可请求内环服务。,试验,实现LRU算法和FIFO算法要求给出任意的输入流、计算失效率。输入流长度、cache尺寸可定制。测试：Cache5，从09可数字的任意排序，长度为30。例如：12568,36536,56892,70495,36745,87345,保护模式,虚地址和虚地址空间,虚地址：程序中的地址，如MOVE REG,2000内存管理单元（MMU）：完成地址转换（图4.1）,段机制和页机制,虚拟地址空间：二维：16k*4G=64T（LDT 8K GDT 8K）线性地址空间:一维：4G物理地址空间:一维：4G,选择子,偏移量,：,段机制,31,31,0,15,0,0,页机制,31,0,线性地址,物理地址,段机制,段基地址段界限段属性以上三者存储在段描述符表中,图4.4,描述符：图4.5、图4.64.8,G：粒度位，0时，段长表示段格式的字节长度，即一个段最长可达1M字节；1时，段长表示段格式以4K字节为一页的页目录数，即一个段最长可达1M*4K=4GD：表示缺省操作数的大小，=0操作数为16位。1为32位,P:存在位。描述段是否在内存S:表示该段是系统段（0）还是用户段（1）DPL:该段的特权级类型：数据段还是代码段A:该段是否被访问,3位:为0表示数据段，1表示代码段W:为0表示不可写，为1表示可写,R:该段可读否C:一致位，当C=1时，若当前进程特权级低于描述符特权级，且当前特权级保持不变，那么代码段只能执行。,系统段类型（图4.10）,门,用来控制访问在目标码段的入口点。类型调用门:将程序控制转移到一个更高特权级别任务门：切换任务中断门：中断处理陷阱门：陷阱处理TSS:任务状态段,包含了任务状态信息LDT:局部描述符表,门描述符（图4.11）,段基址由选择器指出。,描述符表,GDT包含系统中所有任务都可以用的描述符IDT包含任务门、中断门、陷阱门描述符LDT每任务一个。各任务也可有相同的描述符，以共享全局数据和代码每任务的LDT也用一个描述符来表示，即LDT描述符，在GDT中,选择器与描述符表寄存器,只有RPL大于等于相应的描述符DPL，描述符才能被存取。GDTR、IDTR、LDTR,无分页操作时，寻址过程（图4.17）,在段选择器中装入16位数，32位偏移。根据段选择器中的索引值、描述符表寄存器，取出相应描述符。将描述符中的段基地址和32位偏移相加，形成32位物理地址。,分页机制,线性地址转换为物理地址由CR0的PG位启用,状态和控制寄存器（图4.20,4.21）,CR0：PE位,用于启动保护模式。CR2:保存最后一次出现页故障的全32位线性地址。CR3:目录表的物理地址。,地址转换（图4.26）,控制转移,若控制转移要求特权级发生变化，则必须通过门。调用门，为任务内特权级转移提供安全可靠的方法。,小结,操作系统对虚拟存储器的实现是建立在硬件技术支持之上的。分页与分段的保护机制。,
