操作系统第5章_2

1、15.15.1存储管理的功能存储管理的功能5.25.2分区存储管理分区存储管理5.35.3覆盖与交换技术覆盖与交换技术5.45.4页式管理页式管理5.55.5段式管理与段页式管理段式管理与段页式管理5.65.6局部性原理和抖动问题局部性原理和抖动问题6.66.6、UNIXUNIX存储管理存储管理第五章、存储管理第五章、存储管理 25.4 页式管理页式管理一、基本原理：一、基本原理：1）把作业地址空间划分为大小相等的页；）把作业地址空间划分为大小相等的页； 2）把内存存储空间划分为大小相等的页面；）把内存存储空间划分为大小相等的页面；3）作业需要）作业需要m页存储，则在内存中寻找页存储，则在内存

2、中寻找m个空闲页面分个空闲页面分配即可，无须连续。配即可，无须连续。1、页面大小设置：、页面大小设置：1K 4K2、逻辑地址结构设置：、逻辑地址结构设置：3、地址变换：页式虚拟地址、地址变换：页式虚拟地址 内存物理地址内存物理地址3二、静态页面管理二、静态页面管理原理：原理：把作业的全部程序和数据在执行前装入内存的若干页面。把作业的全部程序和数据在执行前装入内存的若干页面。1、数据结构：、数据结构：1）页表页表每个作业每个作业/进程一张，记录逻辑页号和物理页面号的进程一张，记录逻辑页号和物理页面号的对应关系。对应关系。2）请求表请求表系统一张，记录所有作业的申请和分配情况。系统一张，记录所有作

3、业的申请和分配情况。3）存储页面表存储页面表系统一张，记录内存所有页面的分配情况。系统一张，记录内存所有页面的分配情况。a）位示图：）位示图：每一位代表一页面：每一位代表一页面：1 - 已分，已分，0 - 未分未分b）空闲页面链法：）空闲页面链法：每页首单元存放下一空闲页面的地址。每页首单元存放下一空闲页面的地址。页号页号页面号页面号进程号进程号请求页数请求页数 页表始址页表始址页表长度页表长度状态状态42、分配与回收：、分配与回收：分配：分配：回收：回收：1）消除请求表的表项；）消除请求表的表项；2）把页表中各释放页）把页表中各释放页面号插入空闲页面表中；面号插入空闲页面表中；3）释放页表空

4、间。）释放页表空间。53、地址变换、地址变换 页表寄存器页表寄存器 页表长度页表长度 页表始址页表始址页号页号P 页内地址页内地址W 页式逻辑地址页式逻辑地址页号页号页面号页面号0pb请请 求求 表表越界越界+* 页长页长内存物理地址内存物理地址+64、快表、快表引入原因：引入原因：页式管理要访问内存两次，第一次访问页表得页面号，第页式管理要访问内存两次，第一次访问页表得页面号，第二次根据得到物理地址访问，速度慢。二次根据得到物理地址访问，速度慢。高速联想存储器（快表）：高速联想存储器（快表）：由半导体存储器组成，存储当前、最近、经常访问的页表项；由半导体存储器组成，存储当前、最近、经常访问的

5、页表项；查询页面号时，同时查快表：查询页面号时，同时查快表：在快表中，得页面号，停止查页表；在快表中，得页面号，停止查页表；不在快表中，把查页表所得结果填入快表。不在快表中，把查页表所得结果填入快表。特点：特点：需硬件得支持，开销大，但可换取访问速度的提高。需硬件得支持，开销大，但可换取访问速度的提高。75、静态页式管理的优缺点、静态页式管理的优缺点优点：优点：较好解决碎片问题，限制了碎片的大小和数量，提高较好解决碎片问题，限制了碎片的大小和数量，提高了内存利用率。了内存利用率。缺点：缺点：1）动态地址变换开销大，以时间换取空间；）动态地址变换开销大，以时间换取空间；2）出现页内碎片（每个作业

6、末页中）；）出现页内碎片（每个作业末页中）；3）作业仍需全部装入内存，作业大小受限制，没有实现）作业仍需全部装入内存，作业大小受限制，没有实现内存内存“扩充扩充”。8三、动态页式管理（请求页式）三、动态页式管理（请求页式）原理：原理：作业在允许前可以不全部装入内存，对即将执行的作业在允许前可以不全部装入内存，对即将执行的部分动态装入。部分动态装入。预调入方式：预调入方式：对外存中调入页的顺序分析、预测，把预计即将被访问的若干页提对外存中调入页的顺序分析、预测，把预计即将被访问的若干页提前调入内存；前调入内存；一次调入几页，缺页中断少，效率高；一次调入几页，缺页中断少，效率高；要求预测准确，否则

7、效率反而低。要求预测准确，否则效率反而低。请求页式：请求页式：当被访问的指令或数据不在内存时，才发生缺页中断，将其所在页当被访问的指令或数据不在内存时，才发生缺页中断，将其所在页调入；调入；容易实现，但经常缺页容易实现，但经常缺页 中断，系统开销大。中断，系统开销大。两两 种种 方方 式式91、数据结构、数据结构 页表：页表：2、地址变换机构：、地址变换机构： （基本同前）（基本同前）缺页中断缺页中断 地址变换地址变换缺页中断机构：缺页中断机构：1）发生在指令执行期；）发生在指令执行期；2）一条指令的执行期可能发生多次缺页中断。）一条指令的执行期可能发生多次缺页中断。页号页号页面号页面号 中断

8、位中断位外存始址外存始址 改变位改变位 访问位访问位10取指令取指令/数据数据是否在内存？是否在内存？ 缺页中断缺页中断，保护，保护CPU现场现场有无空闲页面有无空闲页面 选择一页选择一页淘汰置换淘汰置换调入所需页调入所需页地址变换地址变换得到实际地址得到实际地址执行执行3、管理流程、管理流程YYNN114、置换算法、置换算法功能：功能：缺页中断但内存无空闲页面时，选择哪一个缺页中断但内存无空闲页面时，选择哪一个页面调出外存腾出空页面？页面调出外存腾出空页面？抖动现象：抖动现象：由于置换算法选择不当，使刚换出的页由要由于置换算法选择不当，使刚换出的页由要马上调入内存，调入不久由被换出，使页面调

9、马上调入内存，调入不久由被换出，使页面调度过于频繁，花销增大。度过于频繁，花销增大。1）随机淘汰算法）随机淘汰算法2）轮转法）轮转法3）最近最久未用页面置换算法）最近最久未用页面置换算法4）理想型淘汰算法）理想型淘汰算法121）随机淘汰算法：）随机淘汰算法：原理：原理：随机选择任意一个页面的内容换出外存。随机选择任意一个页面的内容换出外存。特点：特点：简单，针对性不强。简单，针对性不强。132）轮转法和先进先出算法：）轮转法和先进先出算法：原理：原理：轮转法：轮转法：把满页面顺序连接起来，缺页时依次换出链把满页面顺序连接起来，缺页时依次换出链上页面，不管驻留内存的长短。上页面，不管驻留内存的长

10、短。先进先出算法：先进先出算法：把页面按驻留内存时间长短链接，置把页面按驻留内存时间长短链接，置换指针指向最久页面，换出该指针指向页面，调入页换指针指向最久页面，换出该指针指向页面，调入页入链尾。入链尾。特点：特点：基于基于CPU按线性顺序访问地址空间的思想，忽略按线性顺序访问地址空间的思想，忽略了非线性访问的情况，效率不一定高。了非线性访问的情况，效率不一定高。Belady现象：现象：作业可用页面数增多，缺页次数反而增加作业可用页面数增多，缺页次数反而增加。14一进程有一进程有5页，访问顺序是：页，访问顺序是：1-2-3-4-1-2-5-1-2-3-4-5可用可用3个页面时：缺页个页面时：缺

11、页9次次123412512345111444555555222111113333332222244可用可用4个页面时：缺页个页面时：缺页10次次12341251234511111155554422222211115333333222244444433315123412512345111111111333222222222443444555555可用可用4个页面时，个页面时，最近最久未用页面置换算法：最近最久未用页面置换算法：123412512345111111111115222222222223333555544444444333可用可用3个页面时，理想型淘汰算法：个页面时，理想型淘汰算法：

12、163）最近最久未用页面置换算法：）最近最久未用页面置换算法：原理：原理：某页刚被访问，则可能马上还要被访问；若长期不被某页刚被访问，则可能马上还要被访问；若长期不被访问，则近期也不会被访问；因此选择自上次访问到现在访问，则近期也不会被访问；因此选择自上次访问到现在期间最长的页面淘汰。期间最长的页面淘汰。实施：实施：每个页表项增加一个访问位，记录上次访问以来经历每个页表项增加一个访问位，记录上次访问以来经历的时间的时间t，选择，选择t最大的页面淘汰。最大的页面淘汰。近似算法：近似算法：最不经常使用页面淘汰算法最不经常使用页面淘汰算法访问位：记录上次缺页至今页面的访问次数；访问位：记录上次缺页至

13、今页面的访问次数；缺页时选访问位值最小的淘汰，而后全部清零。缺页时选访问位值最小的淘汰，而后全部清零。最近未用页面淘汰算法最近未用页面淘汰算法周期性对所有访问位置周期性对所有访问位置0（未访），一个周期内被访问，（未访），一个周期内被访问，置置1；缺页时，再访问位为；缺页时，再访问位为0的页面中选择淘汰。的页面中选择淘汰。174）理想型淘汰算法：）理想型淘汰算法：原理：原理：欲知进程访问页的顺序，把当前页后不欲知进程访问页的顺序，把当前页后不再出现的页或离当前页最远的页（最长时间再出现的页或离当前页最远的页（最长时间不访问）淘汰。不访问）淘汰。特点：特点：无法实现，仅作为比较、评价其它算法无法

14、实现，仅作为比较、评价其它算法的一个标准。的一个标准。185、动态页式管理优缺点、动态页式管理优缺点优点：优点：1）“扩充扩充”内存，作业不需全装入，有效利用内存，提高内存，作业不需全装入，有效利用内存，提高并发程度；并发程度；2）便于共享公共信息：通过页表连接；）便于共享公共信息：通过页表连接；3）基本解决碎片问题。）基本解决碎片问题。缺点：缺点：1）地址变换、缺页中断机构需要软硬件的支持，开销大；）地址变换、缺页中断机构需要软硬件的支持，开销大；2）置换算法不当容易产生）置换算法不当容易产生“抖动抖动”现象；现象；3）仍存在页内碎片。）仍存在页内碎片。19页式管理评价页式管理评价1、解决外

15、碎片，出现少量内碎片；、解决外碎片，出现少量内碎片；2、动态页式管理扩充了内存；、动态页式管理扩充了内存；3、开销大，以时间换取空间。、开销大，以时间换取空间。页式管理的局限页式管理的局限 数据的动态变化？数据的动态变化？ 编译链接的方便？编译链接的方便？ 程序或数据的共享？程序或数据的共享？ 逻辑空间的限制？逻辑空间的限制？20215.5 段式管理与段页式管理段式管理与段页式管理（一）段式管理（一）段式管理一、基本原理一、基本原理1、引入、引入分区和分页管理分区和分页管理 ： 一维线性空间，空间不连续，逻辑关系连续；一维线性空间，空间不连续，逻辑关系连续； 难于共享公共子程序和数据。难于共享

16、公共子程序和数据。考虑把逻辑功能上独立的程序和数据自成一段存储。考虑把逻辑功能上独立的程序和数据自成一段存储。222、原理、原理把逻辑上独立的信息定义为一段，每段有段名、段把逻辑上独立的信息定义为一段，每段有段名、段号，段内从号，段内从0开始编址，形成一维线性空间，段长不固开始编址，形成一维线性空间，段长不固定；定；每个作业由若干段构成，地址空间是二维的：每个作业由若干段构成，地址空间是二维的：段号段号S段内地址段内地址W233、分段与分页的区别、分段与分页的区别分分 页页分分 段段“页页”是信息的物理单位，是信息的物理单位，大小固定。大小固定。“段段”是信息的逻辑单位，是信息的逻辑单位，长度

17、不定。长度不定。分页对用户不透明，主要针分页对用户不透明，主要针对内存管理。对内存管理。分段用户可见，便于信息的分段用户可见，便于信息的共享。共享。一维线性地址空间，页间逻一维线性地址空间，页间逻辑地址连续。辑地址连续。二维线性地址空间，段间逻二维线性地址空间，段间逻辑地址不连续，段内连续。辑地址不连续，段内连续。24二、段式管理的实现二、段式管理的实现1、数据结构：、数据结构：1）段表：段表： （每个作业一个）（每个作业一个）记录作业中每段的基本情况。记录作业中每段的基本情况。2）内存分配表：内存分配表： （系统一张）（系统一张）记录内存空闲区的情况。记录内存空闲区的情况。空闲区表、空闲区链

18、空闲区表、空闲区链3）作业表：作业表： （系统一张）（系统一张）记录每个作业的段表起始地址和长度。记录每个作业的段表起始地址和长度。段号段号始址始址 长度长度 存取方式存取方式 内内/外存外存 访问位访问位修改位修改位25262、分配与回收、分配与回收访问段在内存？访问段在内存？缺段中断缺段中断有无空闲区装该段？有无空闲区装该段？选一段选一段/几段淘汰到外存几段淘汰到外存调入该段调入该段地址变换地址变换NNYY回收：回收：修改该段表项修改该段表项回收区插入内回收区插入内存分配表存分配表27缺段中断处理过程缺段中断处理过程28相关算法相关算法空闲区分配算法：空闲区分配算法：1、最先适应算法最先适

19、应算法2、最佳适应算法、最佳适应算法3、最坏适应算法、最坏适应算法淘汰置换算法：淘汰置换算法：1、轮转法轮转法2、先进先出算法、先进先出算法3、最近最久未用段置换算法：、最近最久未用段置换算法： 最不经常使用段淘汰算法最不经常使用段淘汰算法 最近未用段淘汰算法最近未用段淘汰算法29算法比较算法比较碎片碎片大空闲区大空闲区搜索释放速度搜索释放速度最先适应法最先适应法低址多低址多有有快快（一般不排序）（一般不排序）循环首次适循环首次适应算法应算法分布均匀分布均匀无无最佳适应法最佳适应法 小碎片多小碎片多有有较慢较慢（链重排）（链重排）最坏适应法最坏适应法少少无无30地址变换地址变换313、地址变换

20、、地址变换 段表寄存器段表寄存器 段表长度段表长度 段表始址段表始址段号段号S 段内地址段内地址W 段式逻辑地址段式逻辑地址段号段号始址始址0S？K作作 业业 表表越界越界+内存物理地址内存物理地址+快表快表323、段的共享、段的共享1）一个副本，多个进程享用，节省存储空间；）一个副本，多个进程享用，节省存储空间；2）共享段的程序和数据不允许修改；）共享段的程序和数据不允许修改；3）对每个共享段设置共享进程计数）对每个共享段设置共享进程计数count：分配：第一个共享请求，将段调入内存，分配：第一个共享请求，将段调入内存， count加加1；其后的请求，；其后的请求，只需对只需对count加加

21、1。释放：释放： count减减1，当，当count=0时，可以被淘汰出内存。时，可以被淘汰出内存。334、段的保护、段的保护1）地址越界保护：）地址越界保护：每段设置段表寄存器，记录该段始址和长度，每条每段设置段表寄存器，记录该段始址和长度，每条指令执行前判断是否越界。指令执行前判断是否越界。2）存取方式控制保护：）存取方式控制保护：段表项中设段表项中设“存取方式存取方式”一项，规定进程访问该段的权一项，规定进程访问该段的权限：限：共享段：共享段：赋予共享该段的进程不同的权限；赋予共享该段的进程不同的权限；非共享段：非共享段：对过程段只调用，对数据段只读或特定用户写。对过程段只调用，对数据段

22、只读或特定用户写。34三、段式管理的优缺点三、段式管理的优缺点优点：优点：1、便于程序的模块化处理；、便于程序的模块化处理；2、便于共享分段；、便于共享分段；3、实现了内存的扩充。、实现了内存的扩充。4、便于实现动态链接；、便于实现动态链接；5、段长可以动态增长，便于处理变化的数据结构；、段长可以动态增长，便于处理变化的数据结构；缺点：缺点：1、碎片较多，影响内存利用率；、碎片较多，影响内存利用率；2、分段段长受内存可用空间的限制；、分段段长受内存可用空间的限制；3、硬件支持多，开销大；、硬件支持多，开销大；4、采用拼接手段，增加难度；、采用拼接手段，增加难度；5、段长可以动态变化，对外存的管

23、理带来难度。、段长可以动态变化，对外存的管理带来难度。35（二）段页式存储管理（二）段页式存储管理一、基本原理：一、基本原理：1、引入：、引入：分页管理分页管理分段管理分段管理优优点点管理存储空间上的优点：管理存储空间上的优点：克服碎片，提高内存利用率。克服碎片，提高内存利用率。逻辑调用上的优点逻辑调用上的优点：反映逻辑结构，便于段的共享、反映逻辑结构，便于段的共享、动态增长和保护。动态增长和保护。缺缺点点难于共享：难于共享：共享某程序段时，需要进行共享某程序段时，需要进行多次页间链接。多次页间链接。内存利用率不高：内存利用率不高：段长受内存空间限制，存在碎段长受内存空间限制，存在碎片问题。片

24、问题。结结 分页管理内存分页管理内存合合 分段管理外存分段管理外存362、段页式管理原理、段页式管理原理把进程分为若干逻辑上独立的段；（程序员可见）把进程分为若干逻辑上独立的段；（程序员可见）每段分为若干页，每段内容可以分页存储；（系统自动完成）每段分为若干页，每段内容可以分页存储；（系统自动完成）内存分为大小相同的页面，存储某段的某页；内存分为大小相同的页面，存储某段的某页；段号段号S段内页号段内页号P页内偏址页内偏址d0 7 8 11 12 23段内偏址段内偏址WP = W/页长页长 d = W mod 页长页长37二、段页式管理的实现二、段页式管理的实现1、数据结构：、数据结构：1）作业

25、表：作业表：系统一张系统一张2）段表：段表：作业一张作业一张3）页表：页表：每段一张每段一张4）空闲页面表：空闲页面表：位示图位示图/空闲页面链空闲页面链段号段号页表始址页表始址页表长度页表长度其它其它页号页号页面号页面号内内/外存外存访问位访问位修改位修改位外存始址外存始址38段表始址段表始址 段表长度段表长度 作业表作业表段表寄存器段表寄存器段段号号其其它它页表页表长度长度页表页表始址始址0410241210282310300段页表段页表0 101 112 173 141段页表段页表2段页表段页表0 121 180 191 212 23102410271028102910301032101

26、1121314151617181920212223段段 表表392、动态访问、分配、调入：、动态访问、分配、调入：403、地址变换、地址变换 作业表作业表 段表寄存器段表寄存器 段段号号页表页表始址始址S始址始址+SPd逻逻 辑辑 地地 址址段表始址段表始址段表长度段表长度段表段表页页号号页面页面号号P页面页面号号P内存物理地址内存物理地址*页长页长页表页表快表快表41三、段页式管理的优缺点三、段页式管理的优缺点优点：优点：具有请求页式和分段管理的全部优点。具有请求页式和分段管理的全部优点。内存利用率、扩充程度、便于共享、模块化。内存利用率、扩充程度、便于共享、模块化。缺点：缺点：软硬件开销大

27、：缺段中断、缺页中断、地址变换软硬件开销大：缺段中断、缺页中断、地址变换管理表格占据存储空间大：段表、页表管理表格占据存储空间大：段表、页表42各存储管理方法的比较各存储管理方法的比较1、内存利用率、内存利用率 碎片多少？非连续存放？部分装入？碎片多少？非连续存放？部分装入？2、内存扩充、内存扩充 全装？全装？3、信息共享、信息共享 方便？方便？4、软硬件开销、软硬件开销 大小？大小？5、虚拟地址空间、虚拟地址空间 一维？二维？一维？二维？6、数据结构、数据结构 哪些表格？哪些表格？435.6 局部性原理和抖动问题局部性原理和抖动问题局部性原理：局部性原理：在一段时间内，在一段时间内，CPU总

28、是集中地访问程序中的某一部总是集中地访问程序中的某一部分，而不是随机地对程序所有部分具有平均访问概率。分，而不是随机地对程序所有部分具有平均访问概率。内存大小与内外内存大小与内外存交换频率关系存交换频率关系抖动：抖动：内外存频繁交换造成内外存频繁交换造成输入输出处理时间增输入输出处理时间增加，使系统性能大大加，使系统性能大大下降。下降。44解决抖动问题的办法解决抖动问题的办法1、扩大工作集：不让缺页进程换出。、扩大工作集：不让缺页进程换出。2、选择适合的淘汰算法。、选择适合的淘汰算法。45存储管理总结存储管理总结分区分区分页分页分段分段段页段页静态静态动态动态静态静态动态动态碎片问题碎片问题非

29、连续存放非连续存放全部装入全部装入内存利用率内存利用率扩充内存扩充内存方便共享方便共享461、P139：5.132、对访问串：、对访问串：1、2、3、4、1、2、3、5、1、2、3、4、5指出在驻留集大小分别为指出在驻留集大小分别为3和和4时，使用时，使用FIFO、LRU替换算法和理想淘汰算法的缺页次数。替换算法和理想淘汰算法的缺页次数。作作 业业 二二473、某虚存的用户编程空间为、某虚存的用户编程空间为32页，每页长页，每页长1KB，内，内存容量存容量16KB。若某时刻该用户已调入内存的页的虚页号与。若某时刻该用户已调入内存的页的虚页号与物理页面号对照表如下表所示。物理页面号对照表如下表所

30、示。求出虚地址求出虚地址0A8C(H）、）、18C5(H)相对应的物理单元相对应的物理单元地址，若不在内存，则表明地址，若不在内存，则表明“无法得地址无法得地址”。（注：。（注：H表示表示16进制，结果也用进制，结果也用16进制表示）进制表示）虚页号虚页号物理页面物理页面081724310486.6、UNIX存储管理存储管理一、空间的划分：一、空间的划分： （VAX-11）虚拟空间划分为虚拟空间划分为4个功能区，虚存寻址范围：个功能区，虚存寻址范围：0 232 - 1 。P0（程序区）（程序区）P1（控制区）（控制区）核心区核心区保留区保留区进程空间进程空间系统空间系统空间0230231231

31、 + 230232虚拟存储器虚拟存储器512字节一页，共字节一页，共223 - 1 页。页。物理存储器物理存储器512字节一个页面，共字节一个页面，共221 - 1 个页面。个页面。每个区有各自页表。每个区有各自页表。页表的长度和起始地址记录在长度寄存器和基址寄存器中。页表的长度和起始地址记录在长度寄存器和基址寄存器中。0001101149地址结构地址结构虚页号虚页号页内偏移量页内偏移量分分 区区页面号页面号页内偏移量页内偏移量内存内存外存外存存取存取权限权限修改修改位位访问位访问位年龄位年龄位物理物理页面号页面号虚拟地址：虚拟地址：内存地址：内存地址：页表项组成：页表项组成：31 9 8 0

32、31 30 9 8 031 30 27 26 25 21 20 050核心区核心区虚址空间虚址空间与与内存空间内存空间的对应关系的对应关系核心正文段核心正文段数据段数据段核心页表核心页表内存位示图页表内存位示图页表0#进程页表进程页表其他专用区页表其他专用区页表诸进程页表诸进程页表核心正文段核心正文段数据段数据段核心页表核心页表和和进程页表进程页表内存位示图内存位示图0#进程页表进程页表0#进程堆栈进程堆栈进程可用物理空间进程可用物理空间I/O专用区专用区023151内存中核心页表和进程页表的关系内存中核心页表和进程页表的关系52二、内存的分配和释放二、内存的分配和释放1、进程页表的分配：、进程页表的分配：特点：特点：连续存放，变化少。连续存放，变化少。方式：方式：最先适应算法（地址由低到高）最先适应算法（地址由低到高）实施：实施：sptalloc - malloc，sptfree - mfree532、P0和和P1区的分配区的分配memall和释放和释放memfree ：位示图记录页面的分配回收情况，大小由内存大小和页面位示图记录页面的分配回收情况，大小由内存大小和页面长