操作系统04_存储管理.ppt

《操作系统04_存储管理.ppt》由会员分享，可在线阅读，更多相关《操作系统04_存储管理.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 存 储 器 管 理 第四章第四章 存储器管理存储器管理 引言引言4.1 4.1 程序的装入和链接程序的装入和链接 4.2 4.2 连续分配方式连续分配方式 4.3 4.3 基本分页存储管理方式基本分页存储管理方式 4.4 4.4 基本分段存储管理方式基本分段存储管理方式 4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.6 4.6 请求分页存储管理方式请求分页存储管理方式 4.7 4.7 页面置换算法页面置换算法 4.8 4.8 请求分段存储管理方式请求分段存储管理方式 第四章 存 储 器 管 理 存储组织v存储器的存储器的功能功能是是保存数据保存数据，存储器的，存储器的发

2、展方向发展方向是是高速、大容高速、大容量和小体积量和小体积。内存内存在访问速度方面的发展：在访问速度方面的发展：DRAMDRAM、SDRAMSDRAM、DDRDDR、DRDRAMDRDRAM、DDR2DDR2、XDRXDR、SRAMSRAM等；等；硬盘硬盘技术在大容量方面的发展：接口标准、存储密度等；技术在大容量方面的发展：接口标准、存储密度等；v存储组织存储组织是指在是指在存储技术存储技术和和CPUCPU寻址技术寻址技术许可的范围内组织许可的范围内组织合合理的存储结构理的存储结构。其依据是访问速度匹配关系、容量要求和价格。其依据是访问速度匹配关系、容量要求和价格。“寄存器寄存器-内存内存-外

3、存外存”结构结构“寄存器寄存器-缓存缓存-内存内存-外存外存”结构；结构；第四章 存 储 器 管 理 存储层次结构v快速缓存：快速缓存：SRAMSRAMv内存：内存：DRAM,SDRAM,DDR,DRDRAMDRAM,SDRAM,DDR,DRDRAM、DDR2DDR2、XDRXDR等；等；v外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；v微机中的存储层次组织：微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜；最佳状态应是最佳状态应是各层次的存储器各层次的存储器都处于都处于均衡的繁忙状态均衡的繁忙状态；第四章 存 储 器 管 理 存储

4、管理的功能v存储存储分配和回收分配和回收：分配和回收算法及相应的数据结构。：分配和回收算法及相应的数据结构。v地址变换地址变换：可执行文件生成中的链接技术可执行文件生成中的链接技术程序加载程序加载(装入装入)时的重定位技术时的重定位技术进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构v存储存储共享和保护共享和保护：代码和数据共享代码和数据共享地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）v存储器存储器扩充扩充：第四章 存 储 器 管 理 v重定位：实现逻辑地址（相对地址）到物理地址重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射。（

5、绝对地址）的映射。v逻辑地址：应用程序经编译后形成目标程序，再经逻辑地址：应用程序经编译后形成目标程序，再经过链接后形成可装入程序，这些程序的地址都是从过链接后形成可装入程序，这些程序的地址都是从0 0开始，程序中的其他地址都是相对于起始地址计算的，开始，程序中的其他地址都是相对于起始地址计算的，这些地址为相对地址。这些地址为相对地址。v物理地址：主存中一系列存储信息的物理单元的地物理地址：主存中一系列存储信息的物理单元的地址。址。重定位概念第四章 存 储 器 管 理 4.1 4.1 4.1 4.1 程序的装入和链接程序的装入和链接程序的装入和链接程序的装入和链接 v编辑编辑编译编译链接链接装

6、入装入运行运行第四章 存 储 器 管 理 4.1.1 4.1.1 4.1.1 4.1.1 程序的装入程序的装入程序的装入程序的装入 1 1、绝对装入：、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。入时不再作地址重定位。绝对地址的产生：（绝对地址的产生：（1 1）由编译器完成，（）由编译器完成，（2 2）由程序）由程序员编程完成。员编程完成。对（对（1 1）而言，编程用符号地址。）而言，编程用符号地址。2 2、可重定位装入；、可重定位装入；静态重定位：地址转换在装入时一次完成，由软件实静态重定位：地址转换在装入时一次

7、完成，由软件实现（重定位装入程序完成）。现（重定位装入程序完成）。缺点：不允许程序在运行中在内存中移动位置。缺点：不允许程序在运行中在内存中移动位置。第四章 存 储 器 管 理 0100025005000LOAD 1,2500LOAD 1,250036536510000110001250015000作业地址空间作业地址空间内存空间内存空间图图4-2第四章 存 储 器 管 理 3.3.动态运行时装入动态运行时装入在装入后不能移动，在装入后不能移动，该情况一般在执行时才完成相对该情况一般在执行时才完成相对绝对地址绝对地址的转换且有硬件的支持的转换且有硬件的支持,能保证进程的可移动能保证进程的可移动

8、性。性。第四章 存 储 器 管 理 4.1.2 4.1.2 4.1.2 4.1.2 程序的链接程序的链接程序的链接程序的链接1 1、静态链接、静态链接a a对相对地址的修改对相对地址的修改b b变换外部调用符号变换外部调用符号2 2、装入时动态链接、装入时动态链接a.a.便于修改和更新便于修改和更新b.b.便于实现对目标模块的共享便于实现对目标模块的共享3 3、运行时动态链接、运行时动态链接第四章 存 储 器 管 理 模块模块A ACALL B;CALL B;RETURNRETURN模块模块B BCALL C;CALL C;RETURNRETURN模块模块C CRETURNRETURN0 0L

9、-1L-10 0M-1M-10 0N-1N-1(a)(a)目标模块目标模块模块模块A AJSR L;JSR L;RETURNRETURN模块模块B BJSR L+M;JSR L+M;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)装入模块装入模块第四章 存 储 器 管 理 4.24.24.24.2连续分配方式连续分配方式连续分配方式连续分配方式 v单一连续分配单一连续分配用于单用户，单任务中用于单用户，单任务中v分区式分配分区式分配固定式固定式可变式可变式可重定位分区分配可重定位分区分

10、配第四章 存 储 器 管 理 4.2.1 4.2.1 4.2.1 4.2.1 单一连续分区单一连续分区单一连续分区单一连续分区v内存分为两个区域：系统区，用户区。应用程内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。序装入到用户区，可使用用户区全部空间。v最简单，适用于单用户、单任务的最简单，适用于单用户、单任务的OSOS。v优点优点：易于管理。：易于管理。v缺点缺点：对要求内存空间少的程序，造成内存浪：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占费；程序全部装入，很少使用的程序部分也占用内存用内存。第四章 存 储 器 管 理 4.2

11、.2 4.2.2 4.2.2 4.2.2 固定分区固定分区固定分区固定分区v特点：有特点：有n n个分区，则可同时装入个分区，则可同时装入n n个作业个作业/任务。任务。v一、分区大小：一、分区大小：相等相等:不相等：不相等利用率更高。不相等：不相等利用率更高。v二、内存分配：二、内存分配：数据结构数据结构 将分区按大小排序，并将其地址、分配标识作记录将分区按大小排序，并将其地址、分配标识作记录例：例：dosdos的的MCBMCBv三、特点：三、特点：简单，有碎片（内零头）简单，有碎片（内零头）第四章 存 储 器 管 理 分区说明表分区说明表分区说明表分区说明表分区号分区号 大小（大小（K)起

12、址起址（K）状态状态11220已分配已分配23232已分配已分配36464已分配已分配4128128已分配已分配第四章 存 储 器 管 理 操作系统操作系统作业作业A A作业作业B B作业作业C C24K32K64K128K256K分配情况分配情况第四章 存 储 器 管 理 4.2.3 4.2.3 4.2.3 4.2.3 可变式分区可变式分区可变式分区可变式分区一、数据结构一、数据结构1 1空闲分区表空闲分区表2 2空闲分区链空闲分区链前向指前向指针针N N个字节可用个字节可用后向指后向指针针N+2N+2N+2N+20 0（分配（分配标识）标识）0 0第四章 存 储 器 管 理 二、分配算法二

13、、分配算法1 1首次适应算法首次适应算法FFFF。要求：分区按低址要求：分区按低址高址链接高址链接特点：找到第一个大小满足的分区，划分。有外零头，特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。低址内存使用频繁。2 2循环首次适应算法。循环首次适应算法。从从1 1中上次找到的空闲分区的下一个开始查找。中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。的空闲分区。3 3最佳适应算法最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。分区按大小递增排序；分区释放时需插入到适当位置。

14、三、三、分区分配分区分配分配算法第四章 存 储 器 管 理 F1F1回收区回收区回收区回收区F2F2F1F1回收区回收区F2F24-7 4-7 内存回收时的情况内存回收时的情况回收：（回收：（1 1）上邻空闲区：合并，改大小）上邻空闲区：合并，改大小 （2 2）下邻空闲区：合并，改大小，首址。）下邻空闲区：合并，改大小，首址。（3 3）上、下邻空闲区：合并，改大小。）上、下邻空闲区：合并，改大小。（4 4）不邻接，则建立一新表项。）不邻接，则建立一新表项。第四章 存 储 器 管 理 例：在计算机系统中,按地址排列的内存中的空闲区大小是:10K,4K,20K,18K,7K,9K,12K,15K,

15、对于连续的段请求:12K,10K,9K.使用循环适应算法和最佳适应算法将找出哪些空闲区?解：循环适应算法：20K,18K,9K最佳适应算法：12K,10K,9K第四章 存 储 器 管 理 4.2.4 4.2.4 4.2.4 4.2.4 可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配1.1.动态重定位的引入动态重定位的引入连续式分配中，总量大于作业大小的多个小分连续式分配中，总量大于作业大小的多个小分区不能容纳作业。区不能容纳作业。紧凑紧凑通过作业移动将原来分散的小分区拼接成一通过作业移动将原来分散的小分区拼接成一个大分区。个大分区。作业的移动需重定位。是动态（因作业已经作业的

16、移动需重定位。是动态（因作业已经装入）装入）第四章 存 储 器 管 理 紧凑紧凑紧凑紧凑第四章 存 储 器 管 理 2 2 2 2、动态重定位的实现、动态重定位的实现、动态重定位的实现、动态重定位的实现load 1,2500load 1,2500365365load 1,load 1,250025003653650 0100100250025005000500025002500100001000010000100001010010100+12500125001500015000作业作业J J处理机一侧处理机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器相对地址相对地址第四章 存 储 器 管

17、理 图图图图4.104.104.104.10动态分区分配算法动态分区分配算法动态分区分配算法动态分区分配算法第四章 存 储 器 管 理 4.2.5 4.2.5 4.2.5 4.2.5 对换对换对换对换1 1 对换的引入对换的引入将阻塞进程，暂时不用的程序，数据换出。将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。将具备运行条件的进程换入。类型：类型：整体对换：进程对换，解决内存紧张整体对换：进程对换，解决内存紧张部分对换：页面对换部分对换：页面对换/分段对换：提供虚存支持分段对换：提供虚存支持2 2 对换空间的管理对换空间的管理外存外存 对换区对换区比比文件区文件区侧重于对换速

18、度。侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。分配回收类似于可变化分区分配。第四章 存 储 器 管 理 3 3 换出与换入换出与换入换出换出1 1选出被换出进程：选出被换出进程：因素：优先级，驻留时间，进程状态因素：优先级，驻留时间，进程状态2 2换出过程：换出过程：对于共享段：计数减对于共享段：计数减1 1，是是0 0则换出，否则不换则换出，否则不换修改修改PCBPCB和和MCBMCB（或内存分配表）（或内存分配表）换入：换入：1 1选择换入进程：优先级，换出时间等。选择换入进程：优先级，换出时间等。

19、2 2申请内存。申请内存。3 3换入换入第四章 存 储 器 管 理 4.34.34.34.3基本分页存储管理基本分页存储管理基本分页存储管理基本分页存储管理 v连续分配引起连续分配引起:碎片碎片v碎片问题的解决：紧凑方式消耗系统开销。碎片问题的解决：紧凑方式消耗系统开销。v离散分配离散分配分页、分段、段页分页、分段、段页第四章 存 储 器 管 理 v1.1.页面页面页面和物理块：逻辑空间和内存空间页面和物理块：逻辑空间和内存空间页面大小页面大小页太大，页内碎片大。页太大，页内碎片大。页太小：页表可能很长，换入页太小：页表可能很长，换入/出效率低出效率低v2.2.地址结构地址结构313112 1

20、112 110 0逻辑地址逻辑地址A A；页大小；页大小L L；页内偏移；页内偏移d d4.3.14.3.14.3.14.3.1页面与页表页面与页表页面与页表页面与页表页号页号P P 位移位移W W 第四章 存 储 器 管 理 例：例：L=1000B，则第，则第0页对应页对应0-999，第，第1页对应页对应1000-1999。设设A=3456，则，则P=INT3456/1000=3，d=3456mod1000=456故故A=3456（3，456）一一般般来来说说，页页面面尺尺寸寸应应该该是是2 2的的幂幂。这这样样的的优优点点是是可可以以省省去去除除法法，由由硬硬件件自动把地址场中的数拆成两部

21、分来决定对应的页号和页内地址。自动把地址场中的数拆成两部分来决定对应的页号和页内地址。例：页的大小为例：页的大小为1KB，则逻辑地址，则逻辑地址4101的页号、页内地址可这样定：的页号、页内地址可这样定：1K=1024=210(页内地址位数为页内地址位数为10)4101=212+22+20，逻辑地址字如下：，逻辑地址字如下：0001000000000101页号页号页内地址页内地址故故A=4101（4，5）第四章 存 储 器 管 理 3.3.3.3.页表页表页表页表0 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页0 02 21 13 32 26 63 38 84 49 95

22、 50 01 12 23 34 45 56 67 78 89 9用户程序用户程序页表页表页号页号块号块号内存内存第四章 存 储 器 管 理 4.2 4.2 4.2 4.2 地址变换机构地址变换机构地址变换机构地址变换机构 v基本任务：逻辑地址基本任务：逻辑地址物理地址的映射。物理地址的映射。页号页号块号块号 通过页表来完成通过页表来完成 页内地址页内地址块内地址块内地址 无需转换无需转换v一、基本地址变换机构：一、基本地址变换机构：越界保护越界保护每个进程对应一页表，其信息（如长度、始址）放在每个进程对应一页表，其信息（如长度、始址）放在PCBPCB中，执行时将其首地址装入中，执行时将其首地址

23、装入页表寄存器页表寄存器。第四章 存 储 器 管 理 第四章 存 储 器 管 理 需要考虑的问题：需要考虑的问题：v页表放在哪里？整个系统的页表空间有多大？页表放在哪里？整个系统的页表空间有多大？v直直接接映映像像的的分分页页系系统统对对系系统统效效能能的的不不利利影影响响？（影影响响执执行行速度，因为速度，因为CPUCPU至少要访问两次主存才能存取到所要数据）至少要访问两次主存才能存取到所要数据）v基本的地址变换机构基本的地址变换机构页表驻留在内存中。页表驻留在内存中。系系统统中中设设置置一一个个页页表表寄寄存存器器存存放放页页表表在在内内存存中中的的始始址址和和页页表的长度。表的长度。缺点

24、：两次访问主存，速度降低近缺点：两次访问主存，速度降低近1/21/2第四章 存 储 器 管 理 2.2.2.2.具有快表的地址变换机构具有快表的地址变换机构具有快表的地址变换机构具有快表的地址变换机构 v不具快表，则需两次访问内存。不具快表，则需两次访问内存。（1 1）访页表）访页表（2 2）得到绝对地址内容）得到绝对地址内容v有快表，速度提高。有快表，速度提高。v快表贵，不能太多。快表贵，不能太多。第四章 存 储 器 管 理 2.2.2.2.具有快表的地址变换机构具有快表的地址变换机构具有快表的地址变换机构具有快表的地址变换机构第四章 存 储 器 管 理 例：有一页式系统，其页表存放在主存中

25、：例：有一页式系统，其页表存放在主存中：如果对主存的一次存取需要如果对主存的一次存取需要1.5 1.5 s,s,试问实试问实现一次页面访问的存取时间是多少现一次页面访问的存取时间是多少?如果系统加有快表如果系统加有快表,平均命中率为平均命中率为85%,85%,当页表当页表项在快表中时项在快表中时,其查找时间忽略为其查找时间忽略为0,0,试问此时试问此时的存取时间是多少的存取时间是多少?第四章 存 储 器 管 理 答：若页表存放在主存中，则要实现一次页面访问需两答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物次访问主存：一次是访问页表，确定所存取页面

26、的物理地址（称为定位）。第二次才根据该地址存取页面理地址（称为定位）。第二次才根据该地址存取页面数据。数据。页表在主存的存取访问时间页表在主存的存取访问时间 =1.5*2=3(=1.5*2=3(ss)增加快表后的存取访问时间增加快表后的存取访问时间 =0.85*1.5+(1-0.85)*2*1.5=1.725(s)=0.85*1.5+(1-0.85)*2*1.5=1.725(s)第四章 存 储 器 管 理 4.3.3 4.3.3 4.3.3 4.3.3 两级和多级页表两级和多级页表两级和多级页表两级和多级页表 v页表可能很大，将其离散存放在不同页块中。页表可能很大，将其离散存放在不同页块中。v

27、建一建一“外外部部页表页表”来管理这些离散页表块。来管理这些离散页表块。相当于单级相当于单级页表中页表中的页表寄存器，一般应常驻内存。的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。每项记录页表始址，且增加存在位。v6464位机器页表一般位机器页表一般33级，最外层页表常驻。级，最外层页表常驻。第四章 存 储 器 管 理 第四章 存 储 器 管 理 第四章 存 储 器 管 理 1.1.某系统采用页式存储管理策略，拥有逻辑空间某系统采用页式存储管理策略，拥有逻辑空间3232页，每页页，每页2K2K，拥有物理空间拥有物理空间1M1M。（1 1）写出逻辑地址的格式。）写出逻辑地址的格式

28、。（2 2）若不考虑访问权限等，进程的页表有多少项？每项至少有）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？多少位？（3 3）如果物理空间减少一半，页表结构应相应作怎样的改变？）如果物理空间减少一半，页表结构应相应作怎样的改变？2.2.已知某分页系统，主存容量为已知某分页系统，主存容量为64K64K，页面大小为，页面大小为1K1K，对一个，对一个4 4页大的作业，其页大的作业，其0 0、1 1、2 2、3 3页分别被分配到主存的页分别被分配到主存的2 2、4 4、6 6、7 7块块中。中。（1 1）将十进制的逻辑地址）将十进制的逻辑地址10231023、25002500、3500

29、3500、45004500转换成物理转换成物理地址。地址。（2 2）以十进制的逻辑地址）以十进制的逻辑地址10231023为例画出地址变换过程图。为例画出地址变换过程图。练习：练习：第四章 存 储 器 管 理 1.(1)系统拥有逻辑地址空间32页，则逻辑地址中页号需用5位描述；每页2K，则页内地址用11位描述。（2）进程页表项数为32，另外页表项中只给出页所对应的物理块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。（3）如果物理空间减少一半，则页表中页表项数不变，每项的长度可减少1位。第四章 存 储 器 管 理 2.(1)逻辑地址1023：1023/1024，得页号0，页内地址

30、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，因页号大于页表长度产生越界中断。第四章 存 储 器 管 理 4.4.2 4.4.2 4.4.2 4.4.2 分段系统的基本原理分段系统的基本原理分段系统的基本原理分段系统的基本原理1.分段分段v基本思想：按程序

31、的逻辑结构，将程序的地址空间划分基本思想：按程序的逻辑结构，将程序的地址空间划分为若干段，各段大小可不相同。在进行存储分配时，以为若干段，各段大小可不相同。在进行存储分配时，以段为单位，这些段在内存中可以不相邻接。段为单位，这些段在内存中可以不相邻接。分段地址中的地址具有如下结构：段号段内地址31161502.段表段表第四章 存 储 器 管 理 图4-16利用段表实现地址映射第四章 存 储 器 管 理 图4-17分段系统的地址变换过程3.3.地址变换机构地址变换机构第四章 存 储 器 管 理 4.4.分页和分段的主要区别分页和分段的主要区别（1 1）页是信息的物理单位，段是逻辑单位）页是信息的

32、物理单位，段是逻辑单位（2 2）页长度固定，段长度不固定（由用户指定）页长度固定，段长度不固定（由用户指定）（3 3）一维与二维）一维与二维第四章 存 储 器 管 理 4.4.3 4.4.3 信息共享信息共享图4-18分页系统中共享editor的示意图第四章 存 储 器 管 理 图4-19分段系统中共享editor的示意图第四章 存 储 器 管 理 段式管理的优缺点段式管理的优缺点优点：优点：1.程程序序的的各各段段可可独独立立编编译译（修修改改一一个个过过程程不不会会影影响响其其它它无关过程）无关过程）2.可可采采用用不不同同的的保保护护措措施施（段段只只包包含含一一种种类类型型的的对对象象

33、，可以有针对这种特定类型的合适的保护）可以有针对这种特定类型的合适的保护）3.便于共享某些段（常见的例子是共享库，如图形库）便于共享某些段（常见的例子是共享库，如图形库）缺点：缺点：1.段长受限制（段长不定会出现空闲区上内存的浪费）段长受限制（段长不定会出现空闲区上内存的浪费）2.段是作为一个整体调入调出，操作时间长段是作为一个整体调入调出，操作时间长第四章 存 储 器 管 理 4.4.4 4.4.4 4.4.4 4.4.4 段页式存储管理方式段页式存储管理方式段页式存储管理方式段页式存储管理方式1.1.基本原理基本原理面对用户程序的地址空间，采用段式分割面对用户程序的地址空间，采用段式分割内

34、存分为长度相等的若干块内存分为长度相等的若干块将每段划分为页，也常与内存块相等将每段划分为页，也常与内存块相等 v分页优点：提高内存利用率分页优点：提高内存利用率v分段优点：方便用户，易于共享，保护，动态链接。分段优点：方便用户，易于共享，保护，动态链接。第四章 存 储 器 管 理 图4-20作业地址空间和地址结构第四章 存 储 器 管 理 图4-21利用段表和页表实现地址映射第四章 存 储 器 管 理 2.2.地址变换过程地址变换过程图4-22段页式系统中的地址变换机构第四章 存 储 器 管 理 例：对于下表所示段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，23

35、0）转换成物理地址。段号基址段长050K10K160K3K270K5K3120K8K第四章 存 储 器 管 理 4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念4.5.1 4.5.1 虚拟存储器的引入虚拟存储器的引入1.1.常规存储器管理方式的特征常规存储器管理方式的特征(1)(1)一次性一次性（指全部装入）（指全部装入）。(2)(2)驻留性驻留性（指驻留在内存不换出）（指驻留在内存不换出）。第四章 存 储 器 管 理 2.2.局部性原理局部性原理时间局部性：如循环执行时间局部性：如循环执行空间局部性：如顺序执行。空间局部性：如顺序执行。3.3.虚拟存储器虚拟存储器具有具有请求调入请求

36、调入功能和功能和置换置换功能，能从逻辑功能，能从逻辑上对内存容量进行扩充的一种存储系统。上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺牲不大。第四章 存 储 器 管 理 4.5.2 4.5.2 4.5.2 4.5.2 虚拟存储器的实现方式虚拟存储器的实现方式虚拟存储器的实现方式虚拟存储器的实现方式v需要动态重定位需要动态重定位一、请求分页系统一、请求分页系统以页为单位转换以页为单位转换需硬件：需硬件：（1 1）请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构需实现请求分页机制的软件（置换

37、软件等）需实现请求分页机制的软件（置换软件等）第四章 存 储 器 管 理 二、请求分段系统二、请求分段系统以段为单位转换以段为单位转换:（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构需实现请求分段机制的软件（置换软件等）需实现请求分段机制的软件（置换软件等）第四章 存 储 器 管 理 4.5.3 4.5.3 4.5.3 4.5.3 虚存特征虚存特征虚存特征虚存特征1 1离散性：部分装入离散性：部分装入（若连续则不可能提供虚存），无法支持大作（若连续则不可能提供虚存），无法支持大作业小内存运行业小内存运行2 2多次性：局部装入，多

38、次装入。多次性：局部装入，多次装入。3 3对换性：对换性：4 4虚拟性虚拟性.第四章 存 储 器 管 理 4.6请求分页存储管理方式请求分页存储管理方式4.6.1请求分页中的硬件支持请求分页中的硬件支持1.1.页表机制页表机制页号物理块号状态位P访问字段A修改位M外存地址第四章 存 储 器 管 理 2.2.缺页中断机构缺页中断机构图4-23涉及6次缺页中断的指令缺页中断机构：可缺页中断机构：可在指令执行期间产在指令执行期间产生，转入缺页中断生，转入缺页中断处理程序。处理程序。第四章 存 储 器 管 理 3.3.地址变换机构地址变换机构图4-24请求分页中的地址变换过程第四章 存 储 器 管 理

39、 4.6.2 4.6.2 4.6.2 4.6.2 内存分配策略和分配算法内存分配策略和分配算法内存分配策略和分配算法内存分配策略和分配算法一、最小物理块数一、最小物理块数不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则至少如：允许间接寻址：则至少要求要求3 3个物理块。个物理块。Mov A,B Mov A,B 第四章 存 储 器 管 理 二、页面分配和置换策略。二、页面分配和置换策略。1 1固定分配局部置换。固定分配局部置换。缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(少：置换率高少：置换率高;多：浪费多：浪费)2.2.可变分配全局置换可变分配全局置换3.3.可变分

40、配局部置换可变分配局部置换根据进程的缺页率进行页面数调整，进程之根据进程的缺页率进行页面数调整，进程之间相互不会影响。间相互不会影响。第四章 存 储 器 管 理 三、分配算法三、分配算法 1 1平均分配算法平均分配算法2 2按进程大小比例分配算法：按进程大小比例分配算法：3 3考虑优先权分配算法考虑优先权分配算法 第四章 存 储 器 管 理 4.6.3 4.6.3 4.6.3 4.6.3 页面调入策略页面调入策略页面调入策略页面调入策略 1.1.调入时机：调入时机：预调：（根据空间局部性）预调：（根据空间局部性）目前：成功率目前：成功率5050请求调入：较费系统开销请求调入：较费系统开销各有优

41、劣各有优劣2 2从何处调页：从何处调页：对换区：全部从对换区调入所需页面，对换区：全部从对换区调入所需页面，快快文件区：修改过的页面换出到对换区，文件区：修改过的页面换出到对换区，稍慢稍慢UNIXUNIX方式：未运行过的页面，都应从文件区调入。曾经方式：未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，从对换区调入。对共享页，运行过但又被换出的页面，从对换区调入。对共享页，应判断其是否在内存区。应判断其是否在内存区。3.3.页面调入过程页面调入过程第四章 存 储 器 管 理 4.7 4.7 页面置换算法页面置换算法 4.7.1 4.7.1 最佳置换算法和先进先出置换算法最佳置换算法

42、和先进先出置换算法 1.1.最佳最佳(Optimal)(Optimal)置换算法置换算法 最最佳佳置置换换算算法法是是由由BeladyBelady于于19661966年年提提出出的的一一种种理理论论上上的的算算法法。其其所所选选择择的的被被淘淘汰汰页页面面，将将是是以以后后永永不不使使用用的的，或许是在最长或许是在最长(未来未来)时间内不再被访问的页面。时间内不再被访问的页面。第四章 存 储 器 管 理 假假定定系系统统为为某某进进程程分分配配了了三三个个物物理理块块，并并考考虑虑有有以以下下的页面号引用串：的页面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2

43、，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 图4-25利用最佳页面置换算法时的置换图第四章 存 储 器 管 理 2.2.先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法 图4-26利用FIFO置换算法时的置换图第四章 存 储 器 管 理 4.7.2 4.7.2 最近最久未使用最近最久未使用(LRU)(LRU)置换算法置换算法 1.LRU(Least Recently Used)1.LRU(Least Recently Used)置换算法的描述置换算法的描述图4-27LRU页面置换算法第四章 存 储 器 管 理 2.LRU2.LRU置

44、换算法的硬件支持置换算法的硬件支持1)1)寄存器寄存器 为为了了记记录录某某进进程程在在内内存存中中各各页页的的使使用用情情况况，须须为为每每个个在内存中的页面配置一个移位寄存器，可表示为在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0第四章 存 储 器 管 理 图4-28某进程具有8个页面时的LRU访问情况第四章 存 储 器 管 理 2)2)栈栈图4-29用栈保存当前使用页面时栈的变化情况第四章 存 储 器 管 理 4.7.3 Clock4.7.3 Clock置换算法置换算法1.1.简单的简单的ClockClock置换算法置换算法图4-30简单Clock置

45、换算法的流程和示例第四章 存 储 器 管 理 2.2.改进型改进型ClockClock置换算法置换算法由访问位由访问位A A和修改位和修改位M M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面：1 1类类(A=0,(A=0,M=0):M=0):表表示示该该页页最最近近既既未未被被访访问问，又又未未被被修修改，改，是最佳淘汰页。是最佳淘汰页。2 2类类(A=0,(A=0,M=1)M=1)：表表示示该该页页最最近近未未被被访访问问，但但已已被被修修改改，并不是很好的淘汰页。并不是很好的淘汰页。3 3类类(A=1,(A=1,M=0)M=0)：最最近近已已被被访访问问，但但未未被被修修改改

46、，该该页页有可能再被访问。有可能再被访问。4 4类类(A=1,M=1):(A=1,M=1):最近已被访问且被修改，最近已被访问且被修改，该页可能再该页可能再被访问。被访问。第四章 存 储 器 管 理 其执行过程可分成以下三步：其执行过程可分成以下三步：(1)(1)从从指指针针所所指指示示的的当当前前位位置置开开始始，扫扫描描循循环环队队列列，寻寻找找A=0A=0且且M=0M=0的的第第一一类类页页面面，将将所所遇遇到到的的第第一一个个页页面面作作为为所选中的淘汰页。所选中的淘汰页。在第一次扫描期间不改变访问位在第一次扫描期间不改变访问位A A。(2)(2)如如果果第第一一步步失失败败，即即查查

47、找找一一周周后后未未遇遇到到第第一一类类页页面面，则则开开始始第第二二轮轮扫扫描描，寻寻找找A=0A=0且且M=1M=1的的第第二二类类页页面面，将将所所遇遇到到的的第第一一个个这这类类页页面面作作为为淘淘汰汰页页。在在第第二二轮轮扫扫描描期期间间，将将所所有有扫描过的页面的访问位都置扫描过的页面的访问位都置0 0。(3)(3)如如果果第第二二步步也也失失败败，亦亦即即未未找找到到第第二二类类页页面面，则则将将指指针针返返回回到到开开始始的的位位置置，并并将将所所有有的的访访问问位位复复0 0。然然后后重重复复第第一一步步，如如果果仍仍失失败败，必必要要时时再再重重复复第第二二步步，此此时时就

48、就一一定定能能找到被淘汰的页。找到被淘汰的页。第四章 存 储 器 管 理 4.7.4 4.7.4 4.7.4 4.7.4 请求分页系统的性能分析请求分页系统的性能分析请求分页系统的性能分析请求分页系统的性能分析 请求分页系统是目前最常用的一种存储方式，但运行中产生的缺页情请求分页系统是目前最常用的一种存储方式，但运行中产生的缺页情况会影响速度和系统性能，而缺页率的高低往往与进程所占用的物理块数况会影响速度和系统性能，而缺页率的高低往往与进程所占用的物理块数有关。因此本节分析缺页率对系统性能的影响，以及应为每个进程所分配有关。因此本节分析缺页率对系统性能的影响，以及应为每个进程所分配的物理块数目

49、。的物理块数目。1.1.缺页率与有效访问时间缺页率与有效访问时间有效访问时间有效访问时间=(1-p)*t+p*f=(1-p)*t+p*f 其中：其中：p p为缺页率，为缺页率，t t为内存访问时间，为内存访问时间，f f为缺页中断时间为缺页中断时间第四章 存 储 器 管 理 说明：说明：v现现代代计计算算机机系系统统，内内存存访访问问时时间间在在10ns10ns到到数数百百nsns之之间间。(以以100ns100ns为例计算）为例计算）v缺缺页页中中断断时时间间包包括括三三部部分分：（1 1）缺缺页页中中断断服服务务时时间间；（2 2）将将缺缺页页读读入入的的时时间间；（3 3）进进程程重重新

50、新执执行行时时间间。由由于于CPUCPU时时间间很很快快，所所以以（1 1）（3 3）可可以以不不超超过过1ms1ms；（2 2）则则包包括括寻寻道道时时间间、旋旋转转时时间间和和数数据据传传送送时时间间，大大体体需需要要24ms24ms。代代入上式得：入上式得：有效访问时间有效访问时间=（1-p1-p）*0.1(s)+p*25000(s)0.1(s)+p*25000(s)=0.1+24999.9*p =0.1+24999.9*p如如果果缺缺页页率率p=0.001p=0.001（即即在在10001000次次的的页页面面访访问问中中，仅仅发发生生一一次缺页）次缺页）则则有有效效访访问问时时间间约