操作系统第5章-2

15.1 存储管理的功能5.2 分区存储管理5.3 覆盖与交换技术5.4 页式管理5.5 段式管理与段页式管理5.6 局部性原理和抖动问题6.6、UNIX存储管理第五章、存储管理25.4 页式管理一、基本原理：

1）把作业地址空间划分为大小相等的页；

2）把内存存储空间划分为大小相等的页面；

3）作业需要m页存储，则在内存中寻找m个空闲页面分配即可，无须连续。1、页面大小设置：1K~4K2、逻辑地址结构设置：3、地址变换：页式虚拟地址 内存物理地址3二、静态页面管理原理：把作业的全部程序和数据在执行前装入内存的若干页面。1、数据结构：

1）页表—每个作业/进程一张，记录逻辑页号和物理页面号的对应关系。

2）请求表—系统一张，记录所有作业的申请和分配情况。

3）存储页面表—系统一张，记录内存所有页面的分配情况。

a）位示图：每一位代表一页面：1-已分，0-未分

b）空闲页面链法：每页首单元存放下一空闲页面的地址。页号页面号进程号请求页数页表始址页表长度状态42、分配与回收：分配：回收：1）消除请求表的表项；2）把页表中各释放页面号插入空闲页面表中；3）释放页表空间。53、地址变换

页表寄存器页表长度页表始址页号P

页内地址W

页式逻辑地址页号页面号0……pb……请求表越界<+*页长内存物理地址+64、快表引入原因：

页式管理要访问内存两次，第一次访问页表得页面号，第二次根据得到物理地址访问，速度慢。高速联想存储器（快表）： 由半导体存储器组成，存储当前、最近、经常访问的页表项； 查询页面号时，同时查快表： 在快表中，得页面号，停止查页表； 不在快表中，把查页表所得结果填入快表。特点： 需硬件得支持，开销大，但可换取访问速度的提高。75、静态页式管理的优缺点优点： 较好解决碎片问题，限制了碎片的大小和数量，提高了内存利用率。缺点：1）动态地址变换开销大，以时间换取空间；2）出现页内碎片（每个作业末页中）；3）作业仍需全部装入内存，作业大小受限制，没有实现内存“扩充”。8三、动态页式管理（请求页式）原理：

作业在允许前可以不全部装入内存，对即将执行的部分动态装入。预调入方式：

对外存中调入页的顺序分析、预测，把预计即将被访问的若干页提前调入内存； 一次调入几页，缺页中断少，效率高； 要求预测准确，否则效率反而低。请求页式：

当被访问的指令或数据不在内存时，才发生缺页中断，将其所在页调入； 容易实现，但经常缺页中断，系统开销大。两种方式91、数据结构——页表：2、地址变换机构：（基本同前）

缺页中断——地址变换

缺页中断机构：

1）发生在指令执行期；

2）一条指令的执行期可能发生多次缺页中断。

页号页面号中断位外存始址改变位访问位10取指令/数据是否在内存？ 缺页中断，保护CPU现场有无空闲页面 选择一页淘汰置换调入所需页地址变换得到实际地址执行3、管理流程YYNN114、置换算法功能：

缺页中断但内存无空闲页面时，选择哪一个页面调出外存腾出空页面？抖动现象： 由于置换算法选择不当，使刚换出的页由要马上调入内存，调入不久由被换出，使页面调度过于频繁，花销增大。

1）随机淘汰算法

2）轮转法

3）最近最久未用页面置换算法

4）理想型淘汰算法121）随机淘汰算法：原理： 随机选择任意一个页面的内容换出外存。特点： 简单，针对性不强。13

2）轮转法和先进先出算法：原理：

轮转法：把满页面顺序连接起来，缺页时依次换出链上页面，不管驻留内存的长短。

先进先出算法：把页面按驻留内存时间长短链接，置换指针指向最久页面，换出该指针指向页面，调入页入链尾。特点：

基于CPU按线性顺序访问地址空间的思想，忽略了非线性访问的情况，效率不一定高。Belady现象：

作业可用页面数增多，缺页次数反而增加。14一进程有5页，访问顺序是：1-2-3-4-1-2-5-1-2-3-4-5可用3个页面时：缺页9次

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

163）最近最久未用页面置换算法：

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

访问位：记录上次缺页至今页面的访问次数； 缺页时选访问位值最小的淘汰，而后全部清零。最近未用页面淘汰算法

周期性对所有访问位置0（未访），一个周期内被访问，置1；缺页时，再访问位为0的页面中选择淘汰。174）理想型淘汰算法：原理：

欲知进程访问页的顺序，把当前页后不再出现的页或离当前页最远的页（最长时间不访问）淘汰。特点：

无法实现，仅作为比较、评价其它算法的一个标准。185、动态页式管理优缺点优点：

1）“扩充”内存，作业不需全装入，有效利用内存，提高并发程度；

2）便于共享公共信息：通过页表连接；

3）基本解决碎片问题。缺点：

1）地址变换、缺页中断机构需要软硬件的支持，开销大；

2）置换算法不当容易产生“抖动”现象；

3）仍存在页内碎片。19页式管理评价1、解决外碎片，出现少量内碎片；2、动态页式管理扩充了内存；3、开销大，以时间换取空间。页式管理的局限数据的动态变化？编译链接的方便？程序或数据的共享？逻辑空间的限制？20215.5 段式管理与段页式管理（一）段式管理一、基本原理1、引入

分区和分页管理： 一维线性空间，空间不连续，逻辑关系连续； 难于共享公共子程序和数据。

考虑把逻辑功能上独立的程序和数据自成一段存储。222、原理

把逻辑上独立的信息定义为一段，每段有段名、段号，段内从0开始编址，形成一维线性空间，段长不固定； 每个作业由若干段构成，地址空间是二维的：段号S段内地址W233、分段与分页的区别分页分段“页”是信息的物理单位，大小固定。“段”是信息的逻辑单位，长度不定。分页对用户不透明，主要针对内存管理。分段用户可见，便于信息的共享。一维线性地址空间，页间逻辑地址连续。二维线性地址空间，段间逻辑地址不连续，段内连续。24二、段式管理的实现1、数据结构：

1）段表：

（每个作业一个） 记录作业中每段的基本情况。

2）内存分配表：

（系统一张） 记录内存空闲区的情况。

空闲区表、空闲区链

3）作业表：

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

1、最先适应算法

2、最佳适应算法

3、最坏适应算法淘汰置换算法：

1、轮转法

2、先进先出算法

3、最近最久未用段置换算法：

最不经常使用段淘汰算法 最近未用段淘汰算法

29算法比较碎片大空闲区搜索释放速度最先适应法低址多有快（一般不排序）循环首次适应算法分布均匀无最佳适应法小碎片多有较慢（链重排）最坏适应法少无30地址变换313、地址变换

段表寄存器段表长度段表始址段号S

段内地址W

段式逻辑地址段号始址0……S？K……作业表越界<+内存物理地址+快表323、段的共享1）一个副本，多个进程享用，节省存储空间；2）共享段的程序和数据不允许修改；3）对每个共享段设置共享进程计数count：

分配：第一个共享请求，将段调入内存，count加1；其后的请求，只需对count加1。 释放：count减1，当count=0时，可以被淘汰出内存。334、段的保护1）地址越界保护：

每段设置段表寄存器，记录该段始址和长度，每条指令执行前判断是否越界。2）存取方式控制保护：

段表项中设“存取方式”一项，规定进程访问该段的权限： 共享段：赋予共享该段的进程不同的权限； 非共享段：对过程段只调用，对数据段只读或特定用户写。34三、段式管理的优缺点优点：

1、便于程序的模块化处理；

2、便于共享分段；

3、实现了内存的扩充。

4、便于实现动态链接；

5、段长可以动态增长，便于处理变化的数据结构；缺点：

1、碎片较多，影响内存利用率；

2、分段段长受内存可用空间的限制；

3、硬件支持多，开销大；

4、采用拼接手段，增加难度；

5、段长可以动态变化，对外存的管理带来难度。35（二）段页式存储管理一、基本原理：1、引入：

分页管理分段管理优点管理存储空间上的优点：克服碎片，提高内存利用率。逻辑调用上的优点：反映逻辑结构，便于段的共享、动态增长和保护。缺点难于共享：共享某程序段时，需要进行多次页间链接。内存利用率不高：段长受内存空间限制，存在碎片问题。结分页管理内存合分段管理外存362、段页式管理原理把进程分为若干逻辑上独立的段；（程序员可见）每段分为若干页，每段内容可以分页存储；（系统自动完成）内存分为大小相同的页面，存储某段的某页；段号S段内页号P页内偏址d0 78 111223段内偏址WP=[W/页长]d=Wmod页长37二、段页式管理的实现1、数据结构：

1）作业表：系统一张

2）段表：作业一张

3）页表：每段一张

4）空闲页面表：

位示图/空闲页面链段号页表始址页表长度其它页号页面号内/外存访问位修改位外存始址38段表始址段表长度

作业表段表寄存器段号其它页表长度页表始址0…410241…210282…310300段页表0…101…112…173…141段页表2段页表0…121…180…191…212…23102410271028102910301032…1011121314151617181920212223…段表392、动态访问、分配、调入：403、地址变换

作业表—段表寄存器段号页表始址……S始址……+++SPd逻辑地址段表始址段表长度段表页号页面号……P页面号P’……内存物理地址*页长页表快表41三、段页式管理的优缺点优点：

具有请求页式和分段管理的全部优点。 内存利用率、扩充程度、便于共享、模块化。缺点：

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

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

1、P139：5.13

2、对访问串：

1、2、3、4、1、2、3、5、1、2、3、4、5

指出在驻留集大小分别为3和4时，使用FIFO、LRU替换算法和理想淘汰算法的缺页次数。作业二47

3、某虚存的用户编程空间为32页，每页长1KB，内存容量16KB。若某时刻该用户已调入内存的页的虚页号与物理页面号对照表如下表所示。

求出虚地址0A8C(H）、18C5(H)相对应的物理单元地址，若不在内存，则表明“无法得地址”。（注：H表示16进制，结果也用16进制表示）

虚页号物理页面081724310486.6、UNIX存储管理一、空间的划分：（VAX-11） 虚拟空间划分为4个功能区，虚存寻址范围：0~232-1。P0（程序区）P1（控制区）核心区保留区进程空间系统空间0230231231+230232虚拟存储器512字节一页，共223-1页。物理存储器512字节一个页面，共221-1个页面。每个区有各自页表。页表的长度和起始地址记录在长度寄存器和基址寄存器中。0001101149地址结构虚页号页内偏移量分区页面号页内偏移量内存外存存取权限修改位访问位年龄位物理页面号虚拟地址：内存地址：页表项组成：31 98 03130 98 031302726252120 050核心区虚址空间与内存空间的对应关系核心正文段数据段核心页表内存位示图页表0#进程页表其他专用区页表诸进程页表…核心正文段数据段核心页表和进程页表内存位示图0#进程页表0#进程堆栈进程可用物理空间I/O专用区023151内存中核心页表和进程页表的关系52二、内存的分配和释放1、进程页表的分配：

特点：连续存放，变化少。

方式：最先适应算法（地址由低到高）

实施：sptalloc-malloc，sptfree-mfree532、P0和P1区的分配memall和释放memfree

：

位示图记录页面的分配回收情况，大小由内存大小和页面长度决定，内存起始地址为memvad。

mem结构—减少扫描位示图的次数：(

NICMEM<=100) struct { int m_free; /*mem结构中的空闲页面数*/ int m_lo; /*最低页面号*/ int m_hi; /*最高页面号*/ int m_ptr; /*上次查位示图时结束指针*/ int m_avail; /*内存总的空闲页面数*/ short m_pnum[NICMEM]/*本组记录空闲页面号*/ }mem;54分配函数：memall(页表始址base,申请数size)55释放函数：memfree(页表始址base,释放数size)1、对base所