计算机操作系统之存储器管理

第四章存储器管理4.1程序的装入和链接

编辑―――编译―――链接―――装入―――运行图4.12007年1月4.1.1程序的装入

1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图4－2问题：如何知道哪些位置需调整？链接时产生可装入模块的具体功能?2007年1月0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作业地址空间内存空间图4-22007年1月4.1.1程序的装入

3.动态运行时装入在装入后不能移动，该情况一般在执行时才完成相对——绝对地址的转换且有硬件的支持,能保证进程的可移动性。2007年1月4.1.2程序的链接1、静态链接a．对相对地址的修改b．变换外部调用符号2、装入时动态链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接2007年1月模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块2007年1月4.2连续分配方式

单一连续分配用于单用户，单任务中分区式分配固定式可变式可重定位分区分配2007年1月4.2.1单一连续分区系统区用户区存贮保护一般不设置保护也可，因单任务。

2007年1月4.2.2固定分区特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构将分区按大小排序，并将其地址、分配标识作记录例：dos的MCB三、特点：简单，有碎片（内零头）2007年1月图4－4a分区号大小（K)起址（K）状态11220已分配23232已分配36464已分配4128128已分配2007年1月图4－4b操作系统作业A作业B作业C24K32K64K128K256K~~~~分配情况2007年1月4.2.3可变式分区（比固定式分区有改善）一、数据结构1．空闲分区表2．空闲分区链前向指针N个字节可用后向指针N+2N+20（分配标识）02007年1月4.2.3可变式分区（比固定式分区有改善）二、分配算法1．首次适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2．循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3．最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。2007年1月4.2.3可变式分区（比固定式分区有改善）三、分区分配1．分配：图4-62．回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。2007年1月2007年1月F1回收区回收区F2F1回收区F24-7内存回收时的情况2007年1月4.2.4可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。作业的移动需重定位。是动态（因作业已经装入）2007年1月紧凑操作系统用户程序110kb用户程序330kb用户程序614kb用户程序926kb操作系统用户程序1用户程序3用户程序6用户程序92007年1月2、动态重定位的实现25005000365load1,2500365load1,250001002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址2007年1月图4.10动态分区分配算法2007年1月4.2.5对换1对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。2007年1月4.2.5对换3换出与换入一、换出1．选出被换出进程： 因素：优先级，驻留时间，进程状态2．换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）二、换入：1．选择换入进程：优先级，换出时间等。2．申请内存。3．换入2007年1月4.3基本分页存储管理

连续分配引起:碎片碎片问题的解决：紧凑方式消耗系统开销。离散分配分页、分段、段页2007年1月1.页面页面和物理块：逻辑空间和内存空间由机器的地址结构决定页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构31 1211 0逻辑地址A；页大小L(设为1024)；页内偏移d d=AmodL如：A＝2170B.则P=2,d=1224.3.1页面与页表页号P位移W2007年1月3.页表n页5页4页3页2页1页0页594836231209876543210用户程序页表页号块号内存2007年1月4.2地址变换机构

完成：逻辑页号——物理块号的映射，由页表完成。一、基本地址变换机构： 越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。2007年1月2007年1月2.具有快表的地址变换机构

不具快表，则需两次访问内存。（1）访页表（2）得到绝对地址内容有快表，速度提高。快表贵，不能太多。2007年1月2.具有快表的地址变换机构2007年1月

例：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,

试问此时的存取时间是多少?2007年1月答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

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

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)2007年1月4.3.3两级和多级页表

页表可能很大，将其离散存放在不同页块中。建一“外部页表”来管理这些离散页表块。相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。64位机器页表一般>3级，最外层页表常驻。2007年1月2007年1月2007年1月例某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为：125C2007年1月例0A5C＝0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C2007年1月4.4基本分段存储管理

即多重定位分区管理4.4.1引入每个段可有其逻辑意义及功能，使得便于（1）方便编程；（2）分段共享；（3）分段保护；（4）动态链接；（5）动态增长；（如数据段的增长）2007年1月4.4.2分段系统的基本原理

分段对用户而言，分段是2维的。段号+段内地址。段表：逻辑段—map—物理段地址变换机构：图4－16，4－17分页与分段：（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维2007年1月2007年1月2007年1月4.4.3共享

段式系统易于共享例：图4-18及4-19

分页与分段共享比较可重入码（纯代码）各个进程应保留局部数据区2007年1月data10…data1ed40…ed2ed170…6160…2221ed40data10…data1data10…data1…ed2ed1…进程1进程2页表页表data10…data1ed40…ed2ed180…7160…2221主存分页系统中共享editor2007年1月分段系统中共享editoreditordata1editordata2段长基址1608040240段长基址1608040380editordata1…data22007年1月4.4.4段页式存储管理分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。一、段页式系统基本原理

段号+段内页号+页内地址注意： 对用户而言，仍然是二维编址。对系统而言，则是三维编址2007年1月4.4.4段页式存储管理二、地址变换

三次访内存操作，为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache）2007年1月4.5虚拟存储器4.5.1引入1.常规存储管理的特征：一次性（指全部装入）、驻留性（指驻留在内存不换出）2、局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3、虚拟存贮器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚拟大小由_______决定。2007年1月4.5.2虚拟存储器的实现方式需要动态重定位一、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）二、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）2007年1月4.5.3虚存特征1．离散性：部分装入 （若连续则不可能提供虚存），无法支持大作业小内存运行2．多次性：局部装入，多次装入。3．对换性：4．虚拟性.2007年1月4.6.1请求分页中的数据结构及硬件支持一、页表机制页表项：二、缺页中断机构：可在指令执行期间产生（如图4-23） 转入缺页中断处理程序。三、地址变换机构 比较简单分页机制，增加了中断处理，图4.244.6请求分页存储管理页号物理块号状态位P访问字段A修改位M外存地址2007年1月

图4－23涉及6次缺页中断的指令2007年1月4.6.2内存分配策略和分配算法一、最小物理块数不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。

MovA,[B]2007年1月4.6.2内存分配策略和分配算法二、页面分配和置换策略。1．固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高多：浪费)2.可变分配全局置换3.可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。2007年1月三、分配算法

1．平均分配算法2．按进程大小比例分配算法：3．考虑优先权分配算法2007年1月4.6.3页面调入策略

1.调入时机：预调：（根据空间局部性）目前：成功率≤50％请求调：较费系统开销各有优劣2．从何处调页：对换区：修改过的页被换出时入对换区， 快文件区： 稍慢对共享页，应判断其是否在内存区。3.页面调入过程2007年1月目的：减少对换量，提高系统性能4.7.1最佳置换算法和先进先出算法一、最佳置换算法（理论上的）4.7页置换算法

2007年1月4.7页置换算法

目的：减少对换量，提高系统性能4.7.1最佳置换算法和先进先出算法二、FIFO2007年1月4.7.2最近最久未用LRU置换一、算法描述将“最近的过去”，作为“最近的将来”。图4-27二、LRU算法的硬件支持：（用来记录谁最近最久未访问）1．位移寄存器：（定时右移）

R=Rn-1…R0图4-282．栈：当进程访问某页时，将其移出压入“栈顶”，“栈底”换出。

图4-292007年1月LRU2007年1月4.7.3clock置换（LRU近似算法：硬件消耗少）一、简单算法：设一访问位：图4-30循环扫描，每次扫描时将访问位复位。2007年1月2007年1月2007年1月4.7.3clock置换（LRU近似算法：硬件消耗少）二、改进：

A=0;M=02007年1月4.7.4其它一、最少使用（是频率）与LRU类似（记录访问次数），设置一个访问计数器。二、页面缓冲算法：特点：淘汰的页只是修改标志；若页被修改过，则在欲复盖它时回写，否则成批回写。在欲重访问该页时，若页换出则只需修改标志。2007年1月4.8请求分段存储管理方式段表：段名段长段基址存取方式访问字段A修改字段M存在位P增补位外存起址二、缺段中断机构：段不定长，处理起来比缺页中断复杂。

三、地址变换机构

2007年1月4.8.2分段的共享与保护一、共享段表：（整个系统一张）

1.共享进程计数。2.存取控制字段。3.段号：不同的进程可以使用不同的段号去共享段。2007年1月段名段长内存地址状态外存地址共享进程计数状态进程名进程号段号存取控制2007年1月4.8.2分段的共享与保护二、共享段的分配与回收1.分配：第一次访问：分配内存，（1）增加共享段表；（2）修改进程段表。第二次访问：（1）修改共享段表；（2）修改进程段表。2.回收：（1）count=0（2）count<>02007年1月4.8.2分段的共享与保护三、分段保护1.越界检查段号越界检查。段内偏移越界检查。2.存取控制检查。R；R/W；E3.环保护机构（1）内环可访问外环数据；（2）外环可请求内环服务。2007年1月试验

实现LRU算法和FIFO算法要求给出任意的输入流、计算失效率。输入流长度、cache尺寸可定制。测试：Cache＝5，从0－9可数字的任意排序，长度为30。例如：12568,36536,56892,70495,36745,873452007年1月保护模式虚地址和虚地址空间虚地址：程序中的地址，如MOVEREG,2000内存管理单元（MMU）：完成地址转换（图4.1）2007年1月段机制和页机制虚拟地址空间：二维：16k*4G=64T（LDT8K＋GDT8K）线性地址空间:一维：4G物理地址空间:一维：4G选择子偏移量：段机制313101500页机制310线性地址物理地址2007年1月段机制段基地址段界限段属性以上三者存储在段描述符表中2007年1月图4.42007年1月描述符：图4.5、图4.6－4.8G：粒度位，＝0时，段长表示段格式的字节长度，即一个段最长可达1M字节；＝1时，段长表示段格式以4K字节为一页的页目录数，即一个段最长可达1M*4K=4GD：表示缺省操作数的大小，=0操作数为16位。＝1为32位2007年1月P:存在位。描述段是否在内存S:表示该段是系统段（0）还是用户段（1）DPL:该段的特权级类型：数据段还是代码段A:该段是否被访问2007年1月3位:为0表示数据段，1表示代码段W:为0表示不可写，为1表示可写2007年1月R:该段可读否C:一致位，当C=1时，若