04存储管理课件

第四章存储器管理引言4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式第四章存储器管理引言存储组织存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、DDR、DRDRAM、DDR2、XDR、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外存”结构“寄存器-缓存-内存-外存”结构；存储组织存储器的功能是保存数据，存储器的发展方向是高速、大容存储层次结构快速缓存：SRAM内存：DRAM,SDRAM,DDR,DRDRAM、DDR2、XDR等；外存：软盘、硬盘、光盘、磁带等；微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态；存储层次结构快速缓存：SRAM存储管理的功能存储分配和回收：分配和回收算法及相应的数据结构。地址变换：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储管理的功能存储分配和回收：分配和回收算法及相应的数据结重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射。逻辑地址：应用程序经编译后形成目标程序，再经过链接后形成可装入程序，这些程序的地址都是从0开始，程序中的其他地址都是相对于起始地址计算的，这些地址为相对地址。物理地址：主存中一系列存储信息的物理单元的地址。重定位概念重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射4.1程序的装入和链接编辑―――编译―――链接―――装入―――运行4.1程序的装入和链接编辑―――编译―――链接―――装入4.1.1程序的装入1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：地址转换在装入时一次完成，由软件实现（重定位装入程序完成）。缺点：不允许程序在运行中在内存中移动位置。4.1.1程序的装入1、绝对装入：0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作业地址空间内存空间图4-20100025005000LOAD1,2500LOAD3.动态运行时装入在装入后不能移动，该情况一般在执行时才完成相对——绝对地址的转换且有硬件的支持,能保证进程的可移动性。04存储管理课件4.1.2程序的链接1、静态链接a．对相对地址的修改b．变换外部调用符号2、装入时动态链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接4.1.2程序的链接1、静态链接模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块模块A模块B模块C0L-10M-10N-1(a)目标模块模块4.2连续分配方式单一连续分配用于单用户，单任务中分区式分配固定式可变式可重定位分区分配4.2连续分配方式单一连续分配4.2.1单一连续分区内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单用户、单任务的OS。优点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。4.2.1单一连续分区内存分为两个区域：系统区，用户区。4.2.2固定分区特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构将分区按大小排序，并将其地址、分配标识作记录例：dos的MCB三、特点：简单，有碎片（内零头）4.2.2固定分区特点：有n个分区，则可同时装入n个作业分区说明表分区号大小（K)起址（K）状态11220已分配23232已分配36464已分配4128128已分配分区说明表分区号大小（K)起址（K）状态11220已分配23操作系统作业A作业B作业C24K32K64K128K256K~~~~分配情况操作系统作业A作业B作业C24K32K64K128K256K4.2.3可变式分区一、数据结构1．空闲分区表2．空闲分区链前向指针N个字节可用后向指针N+2N+20（分配标识）04.2.3可变式分区一、数据结构前向指针N个字节可用后向二、分配算法1．首次适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2．循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3．最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。二、分配算法三、分区分配分配算法三、分区分配分配算法F1回收区回收区F2F1回收区F24-7内存回收时的情况回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。F1回收区回收区F2F1回收区F24-7内存回收时的情况回例：在计算机系统中,按地址排列的内存中的空闲区大小是:10K,4K,20K,18K,7K,9K,12K,15K,对于连续的段请求:12K,10K,9K.使用循环适应算法和最佳适应算法将找出哪些空闲区?解：循环适应算法：20K,18K,9K最佳适应算法：12K,10K,9K例：在计算机系统中,按地址排列的内存中的空闲区大小是:10K4.2.4可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。作业的移动需重定位。是动态（因作业已经装入）4.2.4可重定位分区分配1.动态重定位的引入紧凑紧凑2、动态重定位的实现load1,2500365load1,25003650100250050002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址2、动态重定位的实现load1,2500365load1图4.10动态分区分配算法图4.10动态分区分配算法4.2.5对换1对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。4.2.5对换1对换的引入3换出与换入换出1．选出被换出进程： 因素：优先级，驻留时间，进程状态2．换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）换入：1．选择换入进程：优先级，换出时间等。2．申请内存。3．换入3换出与换入4.3基本分页存储管理连续分配引起:碎片碎片问题的解决：紧凑方式消耗系统开销。离散分配分页、分段、段页4.3基本分页存储管理连续分配引起:碎片1.页面页面和物理块：逻辑空间和内存空间页面大小页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构31 1211 0逻辑地址A；页大小L；页内偏移d 4.3.1页面与页表页号P位移W1.页面4.3.1页面与页表页号P位移W例：L=1000B，则第0页对应0-999，第1页对应1000-1999。设A=3456，则P=INT[3456/1000]=3，d=[3456]mod1000=456故A=3456→（3，456）

一般来说，页面尺寸应该是2的幂。这样的优点是可以省去除法，由硬件自动把地址场中的数拆成两部分来决定对应的页号和页内地址。例：页的大小为1KB，则逻辑地址4101的页号、页内地址可这样定：1K=1024=210(页内地址位数为10)4101=212+22+20，逻辑地址字如下：0001000000000101页号页内地址故A=4101→（4，5）例：L=1000B，则第0页对应0-999，第1页对应1003.页表0页1页2页3页4页5页n页021326384950123456789用户程序页表页号块号内存3.页表0页1页2页3页4页5页n页0213263849504.2地址变换机构基本任务：逻辑地址——物理地址的映射。

页号→块号通过页表来完成页内地址→块内地址无需转换一、基本地址变换机构： 越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。4.2地址变换机构基本任务：逻辑地址——物理地址的映射04存储管理课件

需要考虑的问题：页表放在哪里？整个系统的页表空间有多大？直接映像的分页系统对系统效能的不利影响？（影响执行速度，因为CPU至少要访问两次主存才能存取到所要数据）

基本的地址变换机构①页表驻留在内存中。②系统中设置一个页表寄存器存放页表在内存中的始址和页表的长度。③缺点：两次访问主存，速度降低近1/2

需要考虑的问题：2.具有快表的地址变换机构不具快表，则需两次访问内存。（1）访页表（2）得到绝对地址内容有快表，速度提高。快表贵，不能太多。2.具有快表的地址变换机构不具快表，则需两次访问内存。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级，最外层页表常驻。4.3.3两级和多级页表页表可能很大，将其离散存放在不04存储管理课件04存储管理课件1.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。（1）写出逻辑地址的格式。（2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？（3）如果物理空间减少一半，页表结构应相应作怎样的改变？2.已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。（2）以十进制的逻辑地址1023为例画出地址变换过程图。练习：1.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K1.(1)系统拥有逻辑地址空间32页，则逻辑地址中页号需用5位描述；每页2K，则页内地址用11位描述。（2）进程页表项数为32，另外页表项中只给出页所对应的物理块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。（3）如果物理空间减少一半，则页表中页表项数不变，每项的长度可减少1位。1.2.(1)逻辑地址1023：1023/1024，得页号0，页内地址1023，查页表的相应块号2，故物理地址为2*1024+1023=3071逻辑地址2500：2500/1024，得页号2，页内地址452，查页表的相应块号6，故物理地址为6*1024+452=6596逻辑地址3500：3500/1024，得页号3，页内地址428，查页表的相应块号7，故物理地址为7*1024+428=7596逻辑地址4500：4500/1024，得页号4，页内地址404，因页号大于页表长度产生越界中断。2.(1)4.4基本分段存储管理4.4.1引入

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

分段基本思想：按程序的逻辑结构，将程序的地址空间划分为若干段，各段大小可不相同。在进行存储分配时，以段为单位，这些段在内存中可以不相邻接。分段地址中的地址具有如下结构：段号段内地址31161502.段表

4.4.2分段系统的基本原理分段分段地址中的地址具有如图4-16利用段表实现地址映射图4-16利用段表实现地址映射图4-17分段系统的地址变换过程3.地址变换机构

图4-17分段系统的地址变换过程3.地址变换机构4.分页和分段的主要区别

（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维4.分页和分段的主要区别（1）页是信息的物理单位，段4.4.3信息共享

图4-18分页系统中共享editor的示意图4.4.3信息共享图4-18分页系统中共享edit图4-19分段系统中共享editor的示意图图4-19分段系统中共享editor的示意图段式管理的优缺点优点：程序的各段可独立编译（修改一个过程不会影响其它无关过程）可采用不同的保护措施（段只包含一种类型的对象，可以有针对这种特定类型的合适的保护）便于共享某些段（常见的例子是共享库，如图形库）缺点：段长受限制（段长不定会出现空闲区上内存的浪费）段是作为一个整体调入调出，操作时间长段式管理的优缺点4.4.4段页式存储管理方式

基本原理面对用户程序的地址空间，采用段式分割内存分为长度相等的若干块将每段划分为页，也常与内存块相等

分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。4.4.4段页式存储管理方式基本原理分页优点：提高内存图4-20作业地址空间和地址结构图4-20作业地址空间和地址结构图4-21利用段表和页表实现地址映射图4-21利用段表和页表实现地址映射2.地址变换过程

图4-22段页式系统中的地址变换机构2.地址变换过程图4-22段页式系统中的地址变换机构例：对于下表所示段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，230）转换成物理地址。段号基址段长050K10K160K3K270K5K3120K8K例：对于下表所示段表，请将逻辑地址（0，137），（1，404.5虚拟存储器的基本概念

4.5.1虚拟存储器的引入1.常规存储器管理方式的特征一次性（指全部装入）。

(2)驻留性（指驻留在内存不换出）。

4.5虚拟存储器的基本概念4.5.1虚拟存储器的引入2.局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3.虚拟存储器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。2.局部性原理4.5.2虚拟存储器的实现方式需要动态重定位一、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）4.5.2虚拟存储器的实现方式需要动态重定位二、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）二、请求分段系统4.5.3虚存特征1．离散性：部分装入 （若连续则不可能提供虚存），无法支持大作业小内存运行2．多次性：局部装入，多次装入。3．对换性：4．虚拟性.4.5.3虚存特征1．离散性：部分装入4.6请求分页存储管理方式

4.6.1请求分页中的硬件支持

1.页表机制

页号物理块号状态位P访问字段A修改位M外存地址4.6请求分页存储管理方式4.6.1请求分页中的硬件2.缺页中断机构

图4-23涉及6次缺页中断的指令缺页中断机构：可在指令执行期间产生，转入缺页中断处理程序。2.缺页中断机构图4-23涉及6次缺页中断的指令缺3.地址变换机构

图4-24请求分页中的地址变换过程3.地址变换机构图4-24请求分页中的地址变换过程4.6.2内存分配策略和分配算法一、最小物理块数不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。MovA,[B]4.6.2内存分配策略和分配算法一、最小物理块数二、页面分配和置换策略。1．固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高;多：浪费)2.可变分配全局置换3.可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。二、页面分配和置换策略。三、分配算法

1．平均分配算法2．按进程大小比例分配算法：3．考虑优先权分配算法三、分配算法1．平均分配算法4.6.3页面调入策略1.调入时机：预调：（根据空间局部性）目前：成功率≤50％请求调入：较费系统开销各有优劣2．从何处调页：对换区：全部从对换区调入所需页面， 快文件区：修改过的页面换出到对换区， 稍慢UNIX方式：未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，从对换区调入。对共享页，应判断其是否在内存区。3.页面调入过程4.6.3页面调入策略1.调入时机：4.7页面置换算法4.7.1最佳置换算法和先进先出置换算法

1.最佳(Optimal)置换算法

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。4.7页面置换算法4.7.1最佳置换算法和先进先出置换

假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

图4-25利用最佳页面置换算法时的置换图假定系统为某进程分配了三个物理块，并考虑有以2.先进先出(FIFO)页面置换算法图4-26利用FIFO置换算法时的置换图2.先进先出(FIFO)页面置换算法图4-26利用4.7.2最近最久未使用(LRU)置换算法1.LRU(LeastRecentlyUsed)置换算法的描述

图4-27LRU页面置换算法4.7.2最近最久未使用(LRU)置换算法1.LRU(2.LRU置换算法的硬件支持

1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为

R=Rn-1Rn-2Rn-3…R2R1R0

2.LRU置换算法的硬件支持1)寄存图4-28某进程具有8个页面时的LRU访问情况图4-28某进程具有8个页面时的LRU访问情况2)栈

图4-29用栈保存当前使用页面时栈的变化情况2)栈图4-29用栈保存当前使用页面时栈的变化情况4.7.3Clock置换算法

1.简单的Clock置换算法

图4-30简单Clock置换算法的流程和示例4.7.3Clock置换算法1.简单的Clock置换2.改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。2.改进型Clock置换算法由访问位A和修

其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

其执行过程可分成以下三步：

4.7.4请求分页系统的性能分析

请求分页系统是目前最常用的一种存储方式，但运行中产生的缺页情况会影响速度和系统性能，而缺页率的高低往往与进程所占用的物理块数有关。因此本节分析缺页率对系统性能的影响，以及应为每个进程所分配的物理块数目。1.缺页率与有效访问时间

有效访问时间=(1-p)*t+p*f

其中：p为缺页率，t为内存访问时间，f为缺页中断时间4.7.4请求分页系统的性能分析请求分页系统说明：现代计算机系统，内存访问时间在10ns到数百ns之间。(以100ns为例计算）缺页中断时间包括三部分：（1）缺页中断服务时间；（2）将缺页读入的时间；（3）进程重新执行时间。由于CPU时间很快，所以（1）（3）可以不超过1ms；（2）则包括寻道时间、旋转时间和数据传送时间，大体需要24ms。代入上式得：

有效访问时间=（1-p）*0.1(μs)+p*25000(μs)=0.1+24999.9*p如果缺页率p=0.001（即在1000次的页面访问中，仅发生一次缺页）则有效访问时间约为25μs，与无缺页相比，速度降低至1/250。说明：如果希望在缺页时有效访问时间延长不超过10%，则有0.11>0.1+24999.9*p则p<0.01/24999.9=0.0000004

结论：有效访问时间直接比例与缺页率，改善请求分页系统的性能，需要保持非常低的缺页率，同时提高I/O的速度。如果希望在缺页时有效访问时间延长不超过10%，则有结论：有效2.抖动——是这样一种系统状态，即系统花在页面替换上的时间远远大于执行进程的时间。抖动产生的原因：由于分配给进程的页面数大小少于进程所需要的最低页面数，导致出现接连不断的缺页中断，引起抖动。

CPU利用率与多道程序度的关系：多道程序度指在内存中并发执行的程序数目。两者关系如下：在低度情况下，CPU利用率呈线性变化关系。随着度的上升，CPU利用率也逐渐上升，最终上升到一个最大值，若在这种情况下，进一步增加度，则系统发生抖动，且CPU利用率将迅速恶化。结论：系统可以利用CPU利用率与多道程序度进行比较的方法检测抖动，一旦发生抖动，可以通过减少多道程序度的方法来消除。2.抖动——是这样一种系统状态，即系统花在页面替换上的时间远例：考虑一个请求分页系统，它采用全局置换策略和平均分配内存块的算法（即若有m个内存块和n个进程，则每个进程分得m/n个内存块）。如果该系统测得如下CPU和对换盘利用率，请问能否用增加多道程序度数来增加CPU的利用率？为什么？（1）CPU利用率为13%，盘利用率为97%；（2）CPU利用率为87%，盘利用率为3%；（1）CPU利用率为13%，盘利用率为3%；例：考虑一个请求分页系统，它采用全局置换策略和平均分配内存块答：（1）此时发生抖动现象。增加多道程序度会进一步增加缺页率，使系统性能进一步恶化，所以不能用增加多道程序度数来增加CPU的利用率。（2）CPU利用率已经相当高，盘利用率却相当低，即进程的缺页率很低，此时应适当增加多道程序度数来增加CPU的利用率。（3）CPU利用率相当低，盘利用率也相当低，表示内存中可运行的程序数不足，此时应增加多道程序度数来增加CPU的利用率。答：4.8请求分段存储管理方式

4.8.1请求分段中的硬件支持

1.段表机制段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址4.8请求分段存储管理方式4.8.1请求分段中的硬件支

在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。在段表项中，除了段名(号)、段长、段在2.缺段中断机构

图4-31请求分段系统中的中断处理过程2.缺段中断机构图4-31请求分段系统中的中断处理过3.地址变换机构

图4-32请求分段系统的地址变换过程3.地址变换机构图4-32请求分段系统的地址变换过程4.8.2分段的共享与保护

1.共享段表

图4-33共享段表项4.8.2分段的共享与保护1.共享段表图4-332.共享段的分配与回收

1)共享段的分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。2.共享段的分配与回收1)共享段的分配

2)共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。2)共享段的回收3.分段保护

越界检查2)存取控制检查※只读※只执行※读/写3)环保护机构※一个程序可以访问驻留在相同环或较低特权环中的数据。※一个程序可以调用驻留在相同环或较高特权环中的服务。

3.分段保护越界检查典型问题分析：1。设作业Ａ的页面映象表如下图所示：（一页=1KB）页号 块号 中断位访问位修改位辅存地址０ ８ １ １１１０００１ ５ １００３０００２ ７ １１０５０００３ ０００８０００问：①指出页表中中断位、访问位、修改位、辅存地址的含义？②当执行到１０００单元的指令“ＬＯＡＤ１，１８００”时，系统是怎样进行地址变换（即１８００在主存的哪个单元中）③当执行到１５００单元指令（ＬＯＡＤ１，３６００）时，会发生什么现象？典型问题分析：（1）中断位：也称状态位，表示该页是否已调入内存；访问位：记录本页在一段时间内被访问次数；修改位：表示该页调入内存后是否修改过；辅存地址：指出该页在辅存上的地址。（2）设页号为P，页内地址为d，逻辑地址为A，页面大小为L，则：P=INT[A/L]d=[A]modL当执行到１０００单元的指令“ＬＯＡＤ１，１８００”时，系统地址变换如下：L=1024B，A=1800，则P=INT[1800/1024]=1，d=[1800]mod1024=776故A=1800→（1，776）查页表第1页在第5块，所以物理地址为：5896（1）中断位：也称状态位，表示该页是否已调入内存；(3)当执行到１５００单元指令（ＬＯＡＤ１，３６００）时，系统地址变换如下：L=1024B，A=3600，则P=INT[3600/1024]=3，d=[3600]mod1024=528故A=3600→（3，528）查页表第3页未调入内存，所以产生缺页中断，从辅存8000位置将该页调入。(3)当执行到１５００单元指令（ＬＯＡＤ１，３６００）2.有一个二维数组：VarA:ARRAY[1..100,1..100]OFinteger;按先行后列的次序存储。对一采用LRU置换算法的页式虚拟存储器系统，假设每页可存放200个整数。若分配给一个进程的内存块数为3，其中一块用来装入程序和变量i、j，另外两块专门用来存放数组（不作它用），且程序段已在内存，但数据页尚未装入内存。请分别就下列程序计算执行过程中的缺页次数。程序1程序2FORi:=1TO100DOFORj:=1TO100DOFORj:=1TO100DOFORi:=1TO100DOA[i,j]:=0;A[i,j]:=0;2.有一个二维数组：2.答：对程序1，首次缺页中断（访问A[0,0]时产生）将装入数组的第1、2行共200个整数，由于程序是按行对数组进行访问，只有在处理完200个整数后才会再次产生缺页中断；以后每调入一页，也能处理200个整数，因此处理100*100个整数共将发生50次缺页。对程序2，首次缺页中断同样将装入数组的第1、2行共200个整数，但由于程序是按列队数组进行访问，因此在处理完2个整数后又会再次产生缺页中断；以后每调入一页，也只能处理2个整数，因此，处理100*100个整数共将产生5000次调页。2.答：对程序1，首次缺页中断（访问A[0,0]时产生）将装3.现有一请求调页系统，页表保存在寄存器中，若有一个被替换的页未被修改，则处理一个缺页中断需要8ms，若被替换页修改过，则处理一个缺页中断需要20ms。内存存取时间为1μs，访问页表时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2μs，可接受最大的缺页率是多少？3.现有一请求调页系统，页表保存在寄存器中，若有一个被替换的3.答：用p表示缺页率，则有效时间不超过2μs可表示为：(1-p)*1μs+p*(0.7*20ms+0.3*8ms+1μs)<=2μsp<=1/16400=0.00006即可接受的最大缺页率为0.00006。3.答：用p表示缺页率，则有效时间不超过2μs可表示为：本章作业：1.存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻.某虚拟系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7。而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。本章作业：2.假如一个程序的段表如下，其中存在位为1表示段在内存，对于下面指令，在执行时会产生什么样的结果。段号存在位内存始址段长存取控制00500100W11100030R213000200E31800080R40500040R(1)STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,20](4)LOADR1,[3,100](5)JMP[2,100]2.假如一个程序的段表如下，其中存在位为1表示段在内存，对于第四章存储器管理引言4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式第四章存储器管理引言存储组织存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、DDR、DRDRAM、DDR2、XDR、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外存”结构“寄存器-缓存-内存-外存”结构；存储组织存储器的功能是保存数据，存储器的发展方向是高速、大容存储层次结构快速缓存：SRAM内存：DRAM,SDRAM,DDR,DRDRAM、DDR2、XDR等；外存：软盘、硬盘、光盘、磁带等；微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态；存储层次结构快速缓存：SRAM存储管理的功能存储分配和回收：分配和回收算法及相应的数据结构。地址变换：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储管理的功能存储分配和回收：分配和回收算法及相应的数据结重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射。逻辑地址：应用程序经编译后形成目标程序，再经过链接后形成可装入程序，这些程序的地址都是从0开始，程序中的其他地址都是相对于起始地址计算的，这些地址为相对地址。物理地址：主存中一系列存储信息的物理单元的地址。重定位概念重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射4.1程序的装入和链接编辑―――编译―――链接―――装入―――运行4.1程序的装入和链接编辑―――编译―――链接―――装入4.1.1程序的装入1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：地址转换在装入时一次完成，由软件实现（重定位装入程序完成）。缺点：不允许程序在运行中在内存中移动位置。4.1.1程序的装入1、绝对装入：0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作业地址空间内存空间图4-20100025005000LOAD1,2500LOAD3.动态运行时装入在装入后不能移动，该情况一般在执行时才完成相对——绝对地址的转换且有硬件的支持,能保证进程的可移动性。04存储管理课件4.1.2程序的链接1、静态链接a．对相对地址的修改b．变换外部调用符号2、装入时动态链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接4.1.2程序的链接1、静态链接模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块模块A模块B模块C0L-10M-10N-1(a)目标模块模块4.2连续分配方式单一连续分配用于单用户，单任务中分区式分配固定式可变式可重定位分区分配4.2连续分配方式单一连续分配4.2.1单一连续分区内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单用户、单任务的OS。优点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。4.2.1单一连续分区内存分为两个区域：系统区，用户区。4.2.2固定分区特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构将分区按大小排序，并将其地址、分配标识作记录例：dos的MCB三、特点：简单，有碎片（内零头）4.2.2固定分区特点：有n个分区，则可同时装入n个作业分区说明表分区号大小（K)起址（K）状态11220已分配23232已分配36464已分配4128128已分配分区说明表分区号大小（K)起址（K）状态11220已分配23操作系统作业A作业B作业C24K32K64K128K256K~~~~分配情况操作系统作业A作业B作业C24K32K64K128K256K4.2.3可变式分区一、数据结构1．空闲分区表2．空闲分区链前向指针N个字节可用后向指针N+2N+20（分配标识）04.2.3可变式分区一、数据结构前向指针N个字节可用后向二、分配算法1．首次适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2．循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3．最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。二、分配算法三、分区分配分配算法三、分区分配分配算法F1回收区回收区F2F1回收区F24-7内存回收时的情况回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。F1回收区回收区F2F1回收区F24-7内存回收时的情况回例：在计算机系统中,按地址排列的内存中的空闲区大小是:10K,4K,20K,18K,7K,9K,12K,15K,对于连续的段请求:12K,10K,9K.使用循环适应算法和最佳适应算法将找出哪些空闲区?解：循环适应算法：20K,18K,9K最佳适应算法：12K,10K,9K例：在计算机系统中,按地址排列的内存中的空闲区大小是:10K4.2.4可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。作业的移动需重定位。是动态（因作业已经装入）4.2.4可重定位分区分配1.动态重定位的引入紧凑紧凑2、动态重定位的实现load1,2500365load1,25003650100250050002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址2、动态重定位的实现load1,2500365load1图4.10动态分区分配算法图4.10动态分区分配算法4.2.5对换1对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。4.2.5对换1对换的引入3换出与换入换出1．选出被换出进程： 因素：优先级，驻留时间，进程状态2．换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）换入：1．选择换入进程：优先级，换出时间等。2．申请内存。3．换入3换出与换入4.3基本分页存储管理连续分配引起:碎片碎片问题的解决：紧凑方式消耗系统开销。离散分配分页、分段、段页4.3基本分页存储管理连续分配引起:碎片1.页面页面和物理块：逻辑空间和内存空间页面大小页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构31 1211 0逻辑地址A；页大小L；页内偏移d 4.3.1页面与页表页号P位移W1.页面4.3.1页面与页表页号P位移W例：L=1000B，则第0页对应0-999，第1页对应1000-1999。设A=3456，则P=INT[3456/1000]=3，d=[3456]mod1000=456故A=3456→（3，456）

一般来说，页面尺寸应该是2的幂。这样的优点是可以省去除法，由硬件自动把地址场中的数拆成两部分来决定对应的页号和页内地址。例：页的大小为1KB，则逻辑地址4101的页号、页内地址可这样定：1K=1024=210(页内地址位数为10)4101=212+22+20，逻辑地址字如下：0001000000000101页号页内地址故A=4101→（4，5）例：L=1000B，则第0页对应0-999，第1页对应1003.页表0页1页2页3页4页5页n页021326384950123456789用户程序页表页号块号内存3.页表0页1页2页3页4页5页n页0213263849504.2地址变换机构基本任务：逻辑地址——物理地址的映射。

页号→块号通过页表来完成页内地址→块内地址无需转换一、基本地址变换机构： 越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。4.2地址变换机构基本任务：逻辑地址——物理地址的映射04存储管理课件

需要考虑的问题：页表放在哪里？整个系统的页表空间有多大？直接映像的分页系统对系统效能的不利影响？（影响执行速度，因为CPU至少要访问两次主存才能存取到所要数据）

基本的地址变换机构①页表驻留在内存中。②系统中设置一个页表寄存器存放页表在内存中的始址和页表的长度。③缺点：两次访问主存，速度降低近1/2

需要考虑的问题：2.具有快表的地址变换机构不具快表，则需两次访问内存。（1）访页表（2）得到绝对地址内容有快表，速度提高。快表贵，不能太多。2.具有快表的地址变换机构不具快表，则需两次访问内存。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级，最外层页表常驻。4.3.3两级和多级页表页表可能很大，将其离散存放在不04存储管理课件04存储管理课件1.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。（1）写出逻辑地址的格式。（2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？（3）如果物理空间减少一半，页表结构应相应作怎样的改变？2.已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。（2）以十进制的逻辑地址1023为例画出地址变换过程图。练习：1.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K1.(1)系统拥有逻辑地址空间32页，则逻辑地址中页号需用5位描述；每页2K，则页内地址用11位描述。（2）进程页表项数为32，另外页表项中只给出页所对应的物理块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。（3）如果物理空间减少一半，则页表中页表项数不变，每项的长度可减少1位。1.2.(1)逻辑地址1023：1023/1024，得页号0，页内地址1023，查页表的相应块号2，故物理地址为2*1024+1023=3071逻辑地址2500：2500/1024，得页号2，页内地址452，查页表的相应块号6，故物理地址为6*1024+452=6596逻辑地址3500：3500/1024，得页号3，页内地址428，查页表的相应块号7，故物理地址为7*1024+428=7596逻辑地址4500：4500/1024，得页号4，页内地址404，因页号大于页表长度产生越界中断。2.(1)4.4基本分段存储管理4.4.1引入

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

分段基本思想：按程序的逻辑结构，将程序的地址空间划分为若干段，各段大小可不相同。在进行存储分配时，以段为单位，这些段在内存中可以不相邻接。分段地址中的地址具有如下结构：段号段内地址31161502.段表

4.4.2分段系统的基本原理分段分段地址中的地址具有如图4-16利用段表实现地址映射图4-16利用段表实现地址映射图4-17分段系统的地址变换过程3.地址变换机构

图4-17分段系统的地址变换过程3.地址变换机构4.分页和分段的主要区别

（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维4.分页和分段的主要区别（1）页是信息的物理单位，段4.4.3信息共享

图4-18分页系统中共享editor的示意图4.4.3信息共享图4-18分页系统中共享edit图4-19分段系统中共享editor的示意图图4-19分段系统中共享editor的示意图段式管理的优缺点优点：程序的各段可独立编译（修改一个过程不会影响其它无关过程）可采用不同的保护措施（段只包含一种类型的对象，可以有针对这种特定类型的合适的保护）便于共享某些段（常见的例子是共享库，如图形库）缺点：段长受限制（段长不定会出现空闲区上内存的浪费）段是作为一个整体调入调出，操作时间长段式管理的优缺点4.4.4段页式存储管理方式

基本原理面对用户程序的地址空间，采用段式分割内存分为长度相等的若干块将每段划分为页，也常与内存块相等

分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。4.4.4段页式存储管理方式基本原理分页优点：提高内存图4-20作业地址空间和地址结构图4-20作业地址空间和地址结构图4-21利用段表和页表实现地址映射图4-21利用段表和页表实现地址映射2.地址变换过程

图4-22段页式系统中的地址变换机构2.地址变换过程图4-22段页式系统中的地址变换机构例：对于下表所示段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，230）转换成物理地址。段号基址段长050K10K160K3K270K5K3120K8K例：对于下表所示段表，请将逻辑地址（0，137），（1，404.5虚拟存储器的基本概念

4.5.1虚拟存储器的引入1.常规存储器管理方式的特征一次性（指全部装入）。

(2)驻留性（指驻留在内存不换出）。

4.5虚拟存储器的基本概念4.5.1虚拟存储器的引入2.局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3.虚拟存储器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。2.局部性原理4.5.2虚拟存储器的实现方式需要动态重定位一、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）4.5.2虚拟存储器的实现方式需要动态重定位二、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）二、请求分段系统4.5.3虚存特征1．离散性：部分装入 （若连续则不可能提供虚存），无法支持大作业小内存运行2．多次性：局部装入，多次装入。3．对换性：4．虚拟性.4.5.3虚存特征1．离散性：部分装入4.6请求分页存储管理方式

4.6.1请求分页中的硬件支持

1.页表机制

页号物理块号状态位P访问字段A修改位M外存地址4.6请求分页存储管理方式4.6.1请求分页中的硬件2.缺页中断机构

图4-23涉及6次缺页中断的指令缺页中断机构：可在指令执行期间产生，转入缺页中断处理程序。2.缺页中断机构图4-23涉及6次缺页中断的指令缺3.地址变换机构

图4-24请求分页中的地址变换过程3.地址变换机构图4-24请求分页中的地址变换过程4.6.2内存分配策略和分配算法一、最小物理块数不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。MovA,[B]4.6.2内存分配策略和分配算法一、最小物理块数二、页面分配和置换策略。1．固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高;多：浪费)2.可变分配全局置换3.可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。二、页面分配和置换策略。三、分配算法

1．平均分配算法2．按进程大小比例分配算法：3．考虑优先权分配算法三、分配算法1．平均分配算法4.6.3页面调入策略1.调入时机：预调：（根据空间局部性）目前：成功率≤50％请求调入：较费系统开销各有优劣2．从何处调页：对换区：全部从对换区调入所需页面， 快文件区：修改过的页面换出到对换区， 稍慢UNIX方式：未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，从对换区调入。对共享页，应判断其是否在内存区。3.页面调入过程4.6.3页面调入策略1.调入时机：4.7页面置换算法4.7.1最佳置换算法和先进先出置换算法

1.最佳(Optimal)置换算法

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。4.7页面置换算法4.7.1最佳置换算法和先进先出置换

假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

图4-25利用最佳页面置换算法时的置换图假定系统为某进程分配了三个物理块，并考虑有以2.先进先出(FIFO)页面置换算法图4-26利用FIFO置换算法时的置换图2.先进先出(FIFO)页面置换算法图4-26利用4.7.2最近最久未使用(LRU)置换算法1.LRU(LeastRecentlyUsed)置换算法的描述

图4-27LRU页面置换算法4.7.2最近最久未使用(LRU)置换算法1.LRU(2.LRU置换算法的硬件支持

1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为

R=Rn-1Rn-2Rn-3…R2R1R0

2.LRU置换算法的硬件支持1)寄存图4-28某进程具有8个页面时的LRU访问情况图4-28某进程具有8个页面时的LRU访问情况2)栈

图4-29用栈保存当前使用页面时栈的变化情况2)栈图4-29用栈保存当前使用页面时栈的变化情况4.7.3Clock置换算法

1.简单的Clock置换算法

图4-30简单Clock置换算法的流程和示例4.7.3Clock置换算法1.简单的Clock置换2.改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。2.改进型Clock置换算法由访问位A和修

其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

其执行过程可分成以下三步：

4.7.4请求分页系统的性能分析

请求分页系统是目前最常用的一种存储方式，但运行中产生的缺页情况会影响速度和系统性能，而缺页率的高低往往与进程所占用的物理块数有关。因此本节分析缺页率对系统性能的影响，以及应为每个进程所分配的物理块数目。1.缺页率与有效访问时间

有效访问时间=(1-p)*t+p*f

其中：p为缺页率，t为内存访问时间，f为缺页中断时间4.7.4请求分页系统的性能分析请求分页系统说明：现代计算机系统，内存访问时间在10ns到数百ns之间。(以100ns为例计算）缺页中断时间包括三部分：（1）缺页中断服务时间；（2）将缺页读入的时间；（3）进程重新执行时间。由于CPU时间很快，所以（1）（3）可以不超过1ms；（2）则包括寻道时间、旋转时间和数据传送时间，大体需要24ms。代入上式得：

有效访问时间=（1-p）*0.1(μs)+p*25000(μs)=0.1+24999.9*p如果缺页率p=0.001（即在1000次的页面访问中，仅发生一次缺页）则有效访问时间约为25μs，与无缺页相比，速度降低至1/250。说明：如果希望在缺页时有效访问时间延长不超过10%，则有0.11>0.1+24999.9*p则p<0.01/24999.9=0.0000004

结论：有效访问时间直接比例与缺页率，改善请求分页系统的性能，需要保持非常低的缺页率，同时提高I/O的速度。如果希望在缺页时有效访问时间延长不超过10%，则有结论：有效2.抖动——是这样一种系统状态，即系统花在页面替换上的时间远远大于执行进程的时间。抖动产生的原因：由于分配给进程的页面数大小少于进程所需要的最低页面数，导致出现接连不断的缺页中断，引起抖动。

CPU利用率与多道程序度的关系：多道程序度指在内存中并发执行的程序数目。两者关系如下：在低度情况下，CPU利用率呈线性变化关系。随着度的上升，CPU利用率也逐渐上升，最终上升到一个最大值，若在这种情况下，进一步增加度，则系统发生抖动，且CPU利用率将迅速恶化。结论：系统可以利用CPU利用率与多道程序度进行比较的方法检测抖动，一旦发生抖动，可以通过减少多道程序度的方法来消除。2.抖动——是这样一种系统状态，即系统花在页面替换上的时间远例：考虑一个请求分页系统，它采用全局置换策略和平均分配内存块的算法（即若有m个内存块和n个进程，则每个进程分得m/n个内存块）。如果该系统测得如下CPU和对换盘利用率，请问能否用增加多道程序度数来增加CPU的利用率？为什么？（1）CPU利用率为13%，盘利用率为97%；（2）CPU利用率为87%，盘利用率为3%；（1）CPU利用率为13%，盘利用率为3%；例：考虑一个请求分页系统，它采用全局置换策略和平均分配内存块答：（1）此时发生抖动现象。增加多道程序度会进一步增加缺页率，使系统性能进一步恶化，所以不能用增加多道程序度数来增加CPU的利用率。（2）CPU利用率已经相当高，盘利用率却相当低，即进程的缺页率很低，此时应适当增加多道程序度数来增加CPU的利用率。（3）CPU利用率相当低，盘利用率也相当低，表示内存中可运行的程序数不足，此时应增加多道程序度数来增加CPU的利用率。答：4.8请求分段存储管理方式

4.8.1请求分段中的硬件支持

1.段表机制段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址4.8请求分段存储管理方式4.8.1请求分段中的硬件支

在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。在段表项中，除了段名(号)、段长、段在2.缺段中断机构

图4-31请求分段系统中的中断处理过程2.缺段中断机构图4-31请求分段系统中的中断处理过3.地址变换机构

图4-32请求分段系统的地址变换过程3.地址变换机构图4-32