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、- -内存内存- -外存外存”结构结构“ “寄存器寄存器- -缓存缓存- -内存内存- -外存外存”结构；结构；第四章 存 储 器 管 理 存储层次结构外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)v 快速缓存：快速缓存：SRAMSRAMv 内存：内存：DRAM,SDRAM,DDR,DRDRAMDRAM,SDRAM,DDR,DRDRAM、 DDR2DDR2、XDRXDR等；等；v 外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；v 微机中的存储层次组织：微机中的存储层次组织：
4、 访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜； 最佳状态应是最佳状态应是各层次的存储器各层次的存储器都处于都处于均衡的繁忙状态均衡的繁忙状态；第四章 存 储 器 管 理 存储管理的功能v 存储存储分配和回收分配和回收：分配和回收算法及相应的数据结构。：分配和回收算法及相应的数据结构。v 地址变换地址变换： 可执行文件生成中的链接技术可执行文件生成中的链接技术 程序加载程序加载( (装入装入) )时的重定位技术时的重定位技术 进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构v 存储存储共享和保护共享和保护： 代码和数据共享代码和数据共享
5、 地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）v 存储器存储器扩充扩充：第四章 存 储 器 管 理 v重定位：实现逻辑地址（相对地址）到物理地址重定位：实现逻辑地址（相对地址）到物理地址（绝对地址）的映射。（绝对地址）的映射。 v逻辑地址：应用程序经编译后形成目标程序，再经逻辑地址：应用程序经编译后形成目标程序，再经过链接后形成可装入程序，这些程序的地址都是从过链接后形成可装入程序，这些程序的地址都是从0 0开始，程序中的其他地址都是相对于起始地址计算开始，程序中的其他地址都是相对于起始地址计算的，这些地址为相对地址。的，这些地址为相对地址。 v物理地址：主存中一系列存储信
6、息的物理单元的地物理地址：主存中一系列存储信息的物理单元的地址。址。 重定位概念第四章 存 储 器 管 理 4.1 4.1 程序的装入和链接程序的装入和链接 v 编辑编辑编译编译链接链接装入装入运行运行第四章 存 储 器 管 理 4.1.1 4.1.1 程序的装入程序的装入 1 1、绝对装入：、绝对装入： 编译后，装入前已产生了绝对地址（内存地址），装编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。入时不再作地址重定位。 绝对地址的产生：（绝对地址的产生：（1 1）由编译器完成，（）由编译器完成，（2 2）由程序）由程序员编程完成。员编程完成。 对（对（1 1）而言，编程用
7、符号地址。）而言，编程用符号地址。2 2、可重定位装入；、可重定位装入； 静态重定位：地址转换在装入时一次完成，由软件实静态重定位：地址转换在装入时一次完成，由软件实现（重定位装入程序完成）。现（重定位装入程序完成）。 缺点：不允许程序在运行中在内存中移动位置。缺点：不允许程序在运行中在内存中移动位置。 第四章 存 储 器 管 理 0100025005000LOAD 1, 2500LOAD 1, 250036536510000110001250015000作业地址空间作业地址空间内存空间内存空间图图4-2第四章 存 储 器 管 理 3.3.动态运行时装入动态运行时装入 在装入后不能移动，在装入
8、后不能移动， 该情况一般在执行时才完成相对该情况一般在执行时才完成相对绝对地绝对地址的转换且有硬件的支持址的转换且有硬件的支持, ,能保证进程的可移能保证进程的可移动性。动性。第四章 存 储 器 管 理 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;RE
9、TURNRETURN模块模块B BCALL C;CALL C;RETURNRETURN模块模块C CRETURNRETURN0 0L-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.2连续分配方式连续分配方式 v 单一连续分配单一连续分配 用于单用户，单任
10、务中用于单用户，单任务中v 分区式分配分区式分配 固定式固定式 可变式可变式 可重定位分区分配可重定位分区分配第四章 存 储 器 管 理 4.2.1 4.2.1 单一连续分区单一连续分区v内存分为两个区域：系统区，用户区。应用程内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。序装入到用户区，可使用用户区全部空间。v最简单，适用于单用户、单任务的最简单，适用于单用户、单任务的OSOS。v优点优点：易于管理。：易于管理。v缺点缺点：对要求内存空间少的程序，造成内存浪：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占费；程序全部装入，很少使用的
11、程序部分也占用内存用内存。第四章 存 储 器 管 理 4.2.2 4.2.2 固定分区固定分区v 特点：有特点：有n n个分区，则可同时装入个分区，则可同时装入n n个作业个作业/ /任务。任务。v 一、分区大小：一、分区大小： 相等相等: : 不相等：不相等利用率更高。不相等：不相等利用率更高。v 二、内存分配：二、内存分配： 数据结构数据结构 将分区按大小排序，并将其地址、分配标识作记录将分区按大小排序，并将其地址、分配标识作记录 例：例：dosdos的的MCBMCBv 三、特点：三、特点： 简单，有碎片（内零头）简单，有碎片（内零头）第四章 存 储 器 管 理 分区说明表分区说明表分区号
12、分区号 大小（大小（K)起址（起址（K）状态状态11220已分配已分配23232已分配已分配36464已分配已分配4128128已分配已分配第四章 存 储 器 管 理 操作系统操作系统作业作业A A作业作业B B作业作业C C24K32K64K128K256K分配情况分配情况第四章 存 储 器 管 理 4.2.3 4.2.3 可变式分区可变式分区一、数据结构一、数据结构1 1 空闲分区表空闲分区表2 2 空闲分区链空闲分区链前向指前向指针针N N个字节可用个字节可用后向指后向指针针N+2N+2N+2N+20 0（分配（分配标识）标识）0 0第四章 存 储 器 管 理 二、分配算法二、分配算法1
13、 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,
15、15K,对于连续的段请求:12K,10K,9K.使用循环适应算法和最佳适应算法将找出哪些空闲区? 解：循环适应算法：20K,18K,9K 最佳适应算法：12K,10K,9K第四章 存 储 器 管 理 4.2.4 4.2.4 可重定位分区分配可重定位分区分配1.1.动态重定位的引入动态重定位的引入 连续式分配中，总量大于作业大小的多个小分连续式分配中，总量大于作业大小的多个小分区不能容纳作业。区不能容纳作业。 紧凑紧凑 通过作业移动将原来分散的小分区拼接成一通过作业移动将原来分散的小分区拼接成一个大分区。个大分区。 作业的移动需重定位。是动态（因作业已经作业的移动需重定位。是动态（因作业已经装入
16、）装入）第四章 存 储 器 管 理 紧凑紧凑操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a) 紧凑前(b) 紧凑后第四章 存 储 器 管 理 2 2、动态重定位的实现、动态重定位的实现load 1,2500load 1,2500365365load 1,load 1,250025003653650 0100100250025005000500025002500100001000010000100001010010100+ +12500125001500015000作业作业J J处理机一侧处理
17、机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器相对地址相对地址第四章 存 储 器 管 理 图图4.104.10动态分区分配算法动态分区分配算法第四章 存 储 器 管 理 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.3基本分页存储管理基本分页存储管理 v 连续分配引起连续分配引起: :碎片碎片v 碎片问题的解决：紧凑方式消耗系统开销。碎片问题的解决：紧凑方式消耗系统开销。v 离散分配离散分配 分页、分段、段页分页、分段、段页第四章 存 储 器 管 理 v 1.1.页面页面 页面和物理块：逻辑空间和内存空间页面和物理块：逻辑空间和内存空间 页面大小页面大小 页太大，页内碎片大。页太大，页内碎片大。 页太小：页表可能很长，换入页太小：页表可能很长，换入/ /出效率低出效率低v 2.2.地址结构
20、地址结构13 3112 1112 110 0 逻辑地址逻辑地址A A；页大小；页大小L L；页内偏移；页内偏移d d4.3.14.3.1页面与页表页面与页表页号页号P P 位移位移W W MODLAdLAINTP第四章 存 储 器 管 理 例：例：L=1000B，则第，则第0页对应页对应0-999，第，第1页对应页对应1000-1999。 设设A=3456，则，则P=INT3456/1000=3，d=3456 mod 1000=456 故故 A=3456（3，456） 一般来说，页面尺寸应该是一般来说，页面尺寸应该是2 2的幂。这样的优点是可以省去除法，由硬件的幂。这样的优点是可以省去除法，由
21、硬件自动把地址场中的数拆成两部分来决定对应的页号和页内地址。自动把地址场中的数拆成两部分来决定对应的页号和页内地址。例：页的大小为例：页的大小为1KB，则逻辑地址，则逻辑地址4101的页号、页内地址可这样定：的页号、页内地址可这样定： 1K=1024=210 (页内地址位数为页内地址位数为10) 4101=212+22+20 ，逻辑地址字如下：，逻辑地址字如下： 000100 0000000101页号页号页内地址页内地址故故 A=4101（4，5）第四章 存 储 器 管 理 3.3.页表页表0 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页0 02 21 13 32 26
22、63 38 84 49 95 50 01 12 23 34 45 56 67 78 89 9用户程序用户程序页表页表页号页号块号块号内存内存第四章 存 储 器 管 理 4.2 4.2 地址变换机构地址变换机构 v 基本任务：逻辑地址基本任务：逻辑地址物理地址的映射。物理地址的映射。 页号页号块号块号 通过页表来完成通过页表来完成 页内地址页内地址块内地址块内地址 无需转换无需转换v 一、基本地址变换机构：一、基本地址变换机构： 越界保护越界保护 每个进程对应一页表，其信息（如长度、始址）放在每个进程对应一页表，其信息（如长度、始址）放在PCBPCB中，执行时将其首地址装入中，执行时将其首地址装
23、入页表寄存器页表寄存器。第四章 存 储 器 管 理 第四章 存 储 器 管 理 需要考虑的问题：需要考虑的问题：v页表放在哪里？整个系统的页表空间有多大？页表放在哪里？整个系统的页表空间有多大？v直接映像的分页系统对系统效能的不利影响？（影响执行直接映像的分页系统对系统效能的不利影响？（影响执行速度，因为速度，因为CPUCPU至少要访问两次主存才能存取到所要数据）至少要访问两次主存才能存取到所要数据）v基本的地址变换机构基本的地址变换机构页表驻留在内存中。页表驻留在内存中。系统中设置一个页表寄存器存放页表在内存中的始址和页系统中设置一个页表寄存器存放页表在内存中的始址和页表的长度。表的长度。缺
24、点：两次访问主存，速度降低近缺点：两次访问主存，速度降低近1/21/2第四章 存 储 器 管 理 2.2.具有快表的地址变换机构具有快表的地址变换机构 v 不具快表，则需两次访问内存。不具快表，则需两次访问内存。（ （1 1）访页表）访页表（ （2 2）得到绝对地址内容）得到绝对地址内容v 有快表，速度提高。有快表，速度提高。v 快表贵，不能太多。快表贵，不能太多。第四章 存 储 器 管 理 2.2.具有快表的地址变换机构具有快表的地址变换机构第四章 存 储 器 管 理 例：有一页式系统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中： 如果对主存的一次存取需要如果对主存的一次存取需
25、要1.5 1.5 s,s,试问实试问实现一次页面访问的存取时间是多少现一次页面访问的存取时间是多少? ? 如果系统加有快表如果系统加有快表, ,平均命中率为平均命中率为85%,85%,当页表当页表项在快表中时项在快表中时, ,其查找时间忽略为其查找时间忽略为0, 0, 试试问此时问此时的存取时间是多少的存取时间是多少? ?第四章 存 储 器 管 理 答：若页表存放在主存中，则要实现一次页面访问需两答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面理地址（称为定
26、位）。第二次才根据该地址存取页面数据。数据。 页表在主存的存取访问时间页表在主存的存取访问时间 =1.5=1.5* *2=3(s)2=3(s) 增加快表后的存取访问时间增加快表后的存取访问时间 =0.85=0.85* *1.5+(1-0.85)1.5+(1-0.85)* *2 2* *1.5=1.725(s)1.5=1.725(s)第四章 存 储 器 管 理 4.3.3 4.3.3 两级和多级页表两级和多级页表 v 页表可能很大，将其离散存放在不同页块中。页表可能很大，将其离散存放在不同页块中。v 建一建一“外部页表外部页表”来管理这些离散页表块。来管理这些离散页表块。 相当于单级相当于单级页
27、表中页表中的页表寄存器，一般应常驻内存。的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。每项记录页表始址，且增加存在位。v 6464位机器页表一般位机器页表一般33级，最外层页表常驻。级，最外层页表常驻。 第四章 存 储 器 管 理 第四章 存 储 器 管 理 第四章 存 储 器 管 理 1.1.某系统采用页式存储管理策略，拥有逻辑空间某系统采用页式存储管理策略，拥有逻辑空间3232页，每页页，每页2K2K，拥有物理空间拥有物理空间1M1M。（1 1）写出逻辑地址的格式。）写出逻辑地址的格式。（2 2）若不考虑访问权限等，进程的页表有多少项？每项至少有）若不考虑访问权限等，进程的
28、页表有多少项？每项至少有多少位？多少位？（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、35003500、45004500转换成物理转换成物理地址。地址。（2 2）以十进制的逻辑地址
29、）以十进制的逻辑地址10231023为例画出地址变换过程图。为例画出地址变换过程图。练习：练习：第四章 存 储 器 管 理 1.(1)系统拥有逻辑地址空间32页，则逻辑地址中页号需用5位描述；每页2K，则页内地址用11位描述。（2）进程页表项数为32，另外页表项中只给出页所对应的物理块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。（3）如果物理空间减少一半，则页表中页表项数不变，每项的长度可减少1位。第四章 存 储 器 管 理 2.(1)逻辑地址1023：1023/1024，得页号0，页内地址1023，查页表的相应块号2，故物理地址为2*1024+1023=3071逻辑地址25
30、00： 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 4.4 基本分段存储管理基本分段存储管理 每个段可有其逻辑意义及功能，使得便于每个段可有其逻辑意义及功能，使得便于（1 1）方便编程；）方便编程；（2 2）分段共享；）分段共享；（3 3）分段保护；）分段保护；（4 4）动
31、态链接；）动态链接；（5 5）动态增长；（如数据段的增长）动态增长；（如数据段的增长）第四章 存 储 器 管 理 1. 分段分段v 基本思想：按程序的逻辑结构，将程序的地址空间划分基本思想：按程序的逻辑结构，将程序的地址空间划分为若干段，各段大小可不相同。在进行存储分配时，以为若干段，各段大小可不相同。在进行存储分配时，以段为单位，这些段在内存中可以不相邻接。段为单位，这些段在内存中可以不相邻接。分段地址中的地址具有如下结构： 段号段内地址31 16 15 02. 段表段表 第四章 存 储 器 管 理 图 4-16 利用段表实现地址映射 作业空间(MAIN)0030K(X)1020K(D)20
32、15K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123第四章 存 储 器 管 理 控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址图 4-17 分段系统的地址变换过程 3. 3. 地址变换机构地址变换机构 第四章 存 储 器 管 理 4. 4. 分页和分段的主要区别分页和分段的主要区别 （1 1）页是信息的物理单位，段是逻辑单位）页
33、是信息的物理单位，段是逻辑单位（2 2）页长度固定，段长度不固定（由用户指定）页长度固定，段长度不固定（由用户指定）（3 3）一维与二维）一维与二维第四章 存 储 器 管 理 4.4.3 4.4.3 信息共享信息共享 ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表图 4-18 分页系统中共享editor的示意图第四章 存 储 器 管 理 图 4-19 分段系统中共享e
34、ditor的示意图 editor进程1data 1进程2editordata 2段表段长基址16080402401608040380editordata 1data 280240280380420第四章 存 储 器 管 理 段式管理的优缺点段式管理的优缺点优点：优点：1. 程序的各段可独立编译（修改一个过程不会影响其它程序的各段可独立编译（修改一个过程不会影响其它无关过程）无关过程）2. 可采用不同的保护措施（段只包含一种类型的对象，可采用不同的保护措施（段只包含一种类型的对象，可以有针对这种特定类型的合适的保护）可以有针对这种特定类型的合适的保护）3. 便于共享某些段（常见的例子是共享库，如
35、图形库）便于共享某些段（常见的例子是共享库，如图形库）缺点：缺点：1. 段长受限制（段长不定会出现空闲区上内存的浪费）段长受限制（段长不定会出现空闲区上内存的浪费）2. 段是作为一个整体调入调出，操作时间长段是作为一个整体调入调出，操作时间长第四章 存 储 器 管 理 1.1. 基本原理基本原理面对用户程序的地址空间，采用段式分割面对用户程序的地址空间，采用段式分割内存分为长度相等的若干块内存分为长度相等的若干块将每段划分为页，也常与内存块相等将每段划分为页，也常与内存块相等 v分页优点：提高内存利用率分页优点：提高内存利用率v分段优点：方便用户，易于共享，保护，动态链接。分段优点：方便用户，
36、易于共享，保护，动态链接。第四章 存 储 器 管 理 04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段图 4-20 作业地址空间和地址结构 第四章 存 储 器 管 理 图 4-21 利用段表和页表实现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器第四章 存 储 器 管 理 2. 2. 地址变换过程地址变换过程 图 4-22 段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表01
37、23b块号 b块内地址页表始址页表长度第四章 存 储 器 管 理 例：对于下表所示段表，请将逻辑地址（0，137），（1，4000），（2，3600），（5，230）转换成物理地址。段号基址段长050K10K160K3K270K5K3120K8K第四章 存 储 器 管 理 4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.5.1 4.5.1 虚拟存储器的引入虚拟存储器的引入 1. 1. 常规存储器管理方式的特征常规存储器管理方式的特征 (1)(1)一次性（指全部装入）。一次性（指全部装入）。 (2) (2) 驻留性（指驻留在内存不换出）。驻留性（指驻留在内存不换出）。 第四章 存
38、储 器 管 理 2.2.局部性原理局部性原理 时间局部性：如循环执行时间局部性：如循环执行 空间局部性：如顺序执行。空间局部性：如顺序执行。3.3.虚拟存储器虚拟存储器 具有具有请求调入请求调入功能和功能和置换置换功能，能从逻辑功能，能从逻辑上对内存容量进行扩充的一种存储系统。上对内存容量进行扩充的一种存储系统。 实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺牲不大。第四章 存 储 器 管 理 4.5.2 4.5.2 虚拟存储器的实现方式虚拟存储器的实现方式v需要动态重定位需要动态重定位一、请求分页系统一、请求分页系统 以页为单位转换以页为单位转换 需硬件：需硬件：（1 1）
39、请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构 需实现请求分页机制的软件（置换软件等）需实现请求分页机制的软件（置换软件等）第四章 存 储 器 管 理 二、请求分段系统二、请求分段系统以段为单位转换以段为单位转换: :（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构需实现请求分段机制的软件（置换软件等）需实现请求分段机制的软件（置换软件等）第四章 存 储 器 管 理 4.5.3 4.5.3 虚存特征虚存特征1 1离散性：部分装入离散性：部分装入（若连续则不可能提供虚存），无法
40、支持大（若连续则不可能提供虚存），无法支持大作业小内存运行作业小内存运行2 2多次性：局部装入，多次装入。多次性：局部装入，多次装入。3 3对换性：对换性：4 4虚拟性虚拟性. .第四章 存 储 器 管 理 4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 1. 1. 页表机制页表机制 页号 物理块号 状态位P 访问字段A 修改位M外存地址 第四章 存 储 器 管 理 2. 2. 缺页中断机构缺页中断机构 图 4-23 涉及6次缺页中断的指令 页面B：A：654321指令copy ATO B缺页中断机构：可缺页中断机构：可在指令执行期间产在
41、指令执行期间产生，转入缺页中断生，转入缺页中断处理程序。处理程序。第四章 存 储 器 管 理 3. 3. 地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是图 4-24 请求分页中的地址变换过程 第四章 存 储 器 管 理 4.6.2 4.6.2 内存分配策略和分配算法内存分配策略和分
42、配算法一、最小物理块数一、最小物理块数不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则至少如：允许间接寻址：则至少要求要求3 3个物理块。个物理块。 MovMov A, B A, B 第四章 存 储 器 管 理 二、页面分配和置换策略。二、页面分配和置换策略。1 1固定分配局部置换。固定分配局部置换。 缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数. . ( (少：置换率高少：置换率高; ; 多：浪费多：浪费) )2.2.可变分配全局置换可变分配全局置换3.3.可变分配局部置换可变分配局部置换 根据进程的缺页率进行页面数调整，进程之根据进程的缺页率进行页面数调整，进程之间
43、相互不会影响。间相互不会影响。第四章 存 储 器 管 理 三、分配算法三、分配算法 1 1平均分配算法平均分配算法2 2按进程大小比例分配算法：按进程大小比例分配算法：3 3考虑优先权分配算法考虑优先权分配算法 mssbiiniiss1第四章 存 储 器 管 理 4.6.3 4.6.3 页面调入策略页面调入策略 1.1.调入时机：调入时机： 预调：（根据空间局部性）预调：（根据空间局部性） 目前：成功率目前：成功率5050 请求调入：较费系统开销请求调入：较费系统开销 各有优劣各有优劣2 2从何处调页：从何处调页： 对换区：全部从对换区调入所需页面，对换区：全部从对换区调入所需页面，快快 文件
44、区：修改过的页面换出到对换区，文件区：修改过的页面换出到对换区，稍慢稍慢 UNIXUNIX方式：未运行过的页面，都应从文件区调入。曾经方式：未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，从对换区调入。对共享页，运行过但又被换出的页面，从对换区调入。对共享页，应判断其是否在内存区。应判断其是否在内存区。3.3.页面调入过程页面调入过程第四章 存 储 器 管 理 1. 1. 最佳最佳(Optimal)(Optimal)置换算法置换算法 最佳置换算法是由最佳置换算法是由BeladyBelady于于19661966年提出的一种理论上年提出的一种理论上的算法。的算法。 其所选择的被淘汰页
45、面，将是以后永不使用的，其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长或许是在最长( (未来未来) )时间内不再被访问的页面。时间内不再被访问的页面。第四章 存 储 器 管 理 假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块， 并考虑有以下并考虑有以下的页面号引用串：的页面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 引用率70770170122010320304243230321201201770101页框(物理块）203图 4-25 利用
46、最佳页面置换算法时的置换图 第四章 存 储 器 管 理 2. 2. 先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法 引用率70770170122010323104430230321013201770201页框2304204230230127127011图 4-26 利用FIFO置换算法时的置换图 第四章 存 储 器 管 理 1. LRU(Least Recently Used)1. LRU(Least Recently Used)置换算法的描述置换算法的描述 图 4-27 LRU页面置换算法 引用率707701701220103203044032303211322017107
47、01页框402432032102第四章 存 储 器 管 理 2. LRU2. LRU置换算法的硬件支持置换算法的硬件支持 1) 1) 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器在内存中的页面配置一个移位寄存器，可表示为，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 第四章 存 储 器 管 理 图 4-28 某进程具有8个页面时的LRU访问情况 第四章 存 储 器 管 理 2) 2) 栈栈 图 4-29 用栈保存当前使用页面时栈的变化情况 447470740704717041017401074
48、1210742120741210742621076第四章 存 储 器 管 理 1. 1. 简单的简单的ClockClock置换算法置换算法 图 4-30 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针第四章 存 储 器 管 理 2. 2. 改进型改进型ClockClock置换算法置换算法 由访问位由访问位A A和修改位和修改位M M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面： 1 1类类(A=0, M=0): (A=0, M=0): 表示该页
49、最近既未被访问，表示该页最近既未被访问， 又未被修又未被修改，改， 是最佳淘汰页。是最佳淘汰页。 2 2类类(A=0, M=1)(A=0, M=1)： 表示该页最近未被访问，表示该页最近未被访问， 但已被修改，但已被修改， 并不是很好的淘汰页。并不是很好的淘汰页。 3 3类类(A=1, M=0)(A=1, M=0)： 最近已被访问，最近已被访问， 但未被修改，但未被修改， 该页该页有可能再被访问。有可能再被访问。 4 4类类(A=1, M=1): (A=1, M=1): 最近已被访问且被修改，最近已被访问且被修改， 该页可能再该页可能再被访问。被访问。 第四章 存 储 器 管 理 其执行过程可
50、分成以下三步：其执行过程可分成以下三步： (1) (1) 从指针所指示的当前位置开始，从指针所指示的当前位置开始， 扫描循环队列，扫描循环队列， 寻找寻找A=0A=0且且M=0M=0的第一类页面，的第一类页面， 将所遇到的第一个页面作为将所遇到的第一个页面作为所选中的淘汰页。所选中的淘汰页。 在第一次扫描期间不改变访问位在第一次扫描期间不改变访问位A A。 (2) (2) 如果第一步失败，即查找一周后未遇到第一类页面，如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找则开始第二轮扫描，寻找A=0A=0且且M=1M=1的第二类页面，将所遇到的第二类页面，将所遇到的第一个这类页
