操作系统chapter课件5

第三章存储管理◆存储管理是指主存管理(外存管理见文件系统)，包括给进程分配主存片段，收回进程释放的主存片段，为分配出去的主存片段提供保护与共享，以及为作业提供一个虚拟的存储空间

第三章存储管理◆存储管理是指主存管理(外存管理见文件系统)，1第三章存储管理3.1物理主存

◆物理主存简称主存，它是计算机系统中的存储装置

◆个人计算机上通常都配有128MB的RAM，除了操作系统代码占用一部分外，余者皆为用户区域，由用户进程瓜分

第三章存储管理3.1物理主存◆物理主存简称主存，它是计2存储管理3.2存储概念和虚存管理

◆链接工作的实质是按照各个程序段之间的调用关系把各段的地址统一成从0开始的一维线性地址。链接既可在作业运行之前，也可在作业的程序段执行过程中依调用关系动态地进行。前者称为静态链接，由link程序完成；后者称为动态链接存储管理3.2存储概念和虚存管理◆链接工作的实质是按照3第三章存储管理3.2存储概念和虚存管理

◆从0开始的指令地址和数据段地址组成作业的地址空间，它是逻辑上的，与主存地址毫不相干，因此称为虚拟空间或虚拟存储器。虚存的容量与主存大小无关，它是由计算机系统的地址结构和寻址方式确定的

第三章存储管理3.2存储概念和虚存管理◆从0开始的指令4操作系统chapter课件55第三章存储管理3.2存储概念和虚存管理

◆

WindowsAPI控制进程的虚拟地址空间

◆(1)私用堆

用户使用HeapCreate()来产生私用堆空间

HANDLEHeapCreate(flOptions,dwInitialSize,dwMaximumSize)DWORDflOptions; //堆的分配标记

DWORDdwInitialSize; //堆的初始长度

DWORDdwMaximumSize;//堆的最大长度

第三章存储管理3.2存储概念和虚存管理◆Window6第三章存储管理3.2存储概念和虚存管理

◆(2)保留虚空间

LPVOIDVirtualAlloc(lpvAddress,cbSize,fdwAllocationType,fdwProtect)LPVOIDlpvAddress; //该区虚地址

DWORDcbSize; //该区域的长度

DWORDfdwAllocationType; //该区域被指定的类型

DWORDfdwProtect; //该区域的访问保护即访问权限

第三章存储管理3.2存储概念和虚存管理◆(2)保留虚7第三章存储管理3.2存储概念和虚存管理

◆(3)存储映射文件.最主要的虚存管理特性是通过存储映射支持共享虚存区域LPVOIDMapViewOfFile(hmapObect,fdwAccess,OffsetHigh,dwOffsetlow,cbMap)HANDLEhmapObject; //存储映射对象的句柄

DWORDfdwAccess; //访问模式

DWORDdwOffsetHigh; //32位地址的高位部分

DWORDdwOffsetLow; //32位地址的低位部分

DWORDcbMap; //映射的字节数

第三章存储管理3.2存储概念和虚存管理◆(3)存储映8第三章存储管理3.3地址变换

◆物理主存空间地址是一维线性排列的，不妨记作M={0,1,2,…,2m-1},表示主存容量为2m。例如，当m=23时，主存的容量为8MB。虚存的一维线性空间和二维线性空间分别记为：V1={0,1,2,…,2v-1}V2={0段{0,1,2,…,n0},1段{0,1,2,…,n1},…，s段{0,1,2,…,ns}}第三章存储管理3.3地址变换◆物理主存空间地址是一维线9第三章存储管理3.3地址变换

◆所谓地址变换(又称地址映射)就是把多个V空间映射到M空间上去，或者说是把虚存地址变换成物理主存地址

第三章存储管理3.3地址变换◆所谓地址变换(又称地址映10第三章存储管理3.4进程空间不大于主存空间的管理

图3-2第三章存储管理3.4进程空间不大于主存空间的管理图3-11图3-2固定分区原理图图3-2固定分区原理图12第三章存储管理3.4.1固定分区

◆由于进程空间(PS)的虚地址是从0开始递增编址的，因此装入模块在把它装入到分区时，必须把所有虚地址变换成从分区始址为起点的物理地址，其变换公式是：物理地址=虚地址+分区的始址

第三章存储管理3.4.1固定分区◆由于进程空间(PS)13第三章存储管理3.4.1固定分区

◆静态重定位(staticaddressrelocation)◆动态重定位(dynamicaddressrelocation)

如图3-3第三章存储管理3.4.1固定分区◆静态重定位(stat14图3-3动态重定位过程示意图图3-3动态重定位过程示意图15第三章存储管理3.4.1固定分区

◆固定分区的保护是指各进程空间在主存内运行时保证其每个物理地址都不超越自己的上下界限

◆

2种保护法（见图3-4）

◆对上下界保护法满足：(UR)≤物理地址<(LR)

◆对基址/限长保护法满足：(BR)≤物理地址<(BR)+(LR)

第三章存储管理3.4.1固定分区◆固定分区的保护是指各16操作系统chapter课件517第三章存储管理3.4.2可变分区

◆根据进程空间的实际大小按需分配主存空间

◆这种管理方法下，主存分区的个数，各区域的大小，在主存内活动的进程个数等都是随时间而变化的。所以，可变分区又称为动态分区

图3-5

图3-6第三章存储管理3.4.2可变分区◆根据进程空间的实际大18图3-5可变分区管理初始状态示例

图3-5可变分区管理初始状态示例19操作系统chapter课件520第三章存储管理3.4.2.1数据结构◆有2种数据结构，即自由区表FBT(FreeBlockTable)和自由区链FBC(FreeBlockChain)供可变分区管理选用

（图3-7）◆FBC的设计技巧在于，它利用自由区本身的空间记录自由区的大小及前后自由区的位置

第三章存储管理3.4.2.1数据结构◆有2种数据结构，21操作系统chapter课件522第三章存储管理3.4.2.2分区分配算法◆首次适应法(FirstFit)找到第1个能满足长度要求的自由区，从中截取所需空间

◆最佳适应法(BestFit)从自由区链中挑选能满足申请长度的最小自由区

◆最坏适应法(WorstFit)总是挑选最大的自由区分割给申请者

第三章存储管理3.4.2.2分区分配算法◆首次适应法(23第三章存储管理3.4.2.3分配/回收程序与优先级考虑

以首次适应算法和FBC结构为例，请求大小为x的自由存储区分配程序如下：

PROCEDUREget_block(x,p);BEGINi:=1;WHILE(FBC[i].size<>0)AND(FBC[i].size<x)DOi:=i+1;IFFBC[i].size=0THENp:=0ELSEBEGIN第三章存储管理3.4.2.3分配/回收程序与优先级考虑以首24存储管理3.4.2.3分配/回收程序与优先级考虑

p:=FBC[i].adder;y:=FBC[i].size-x;IFy>=THENBEGINFBC[i].size:=y;FBC[i].adder:=FBC[i].adder+x:ENDENDEND第三章存储管理3.4.2.3分配/回收程序与优先级考虑p25第三章存储管理3.4.2.3分配/回收程序与优先级考虑

◆回收过程(free_block)◆回收时要考虑回收的自由区是否与原自由区邻接

图3-8第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆回26操作系统chapter课件527第三章存储管理3.4.2.3分配/回收程序与优先级考虑

◆get_block算法越快，系统的性能越好

◆要研制快速get_block算法并且给予它以高的优先级以便尽快得到CPU响应

第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆28第三章存储管理3.4.2.4地址变换与保护图3-9地址变换与保护第三章存储管理3.4.2.4地址变换与保护图3-9地址29第三章存储管理3.4.2.5分区共享◆只要2个进程空间包含相同的虚地址(如Windows95)，物理主存分区即被2进程所共享。同理，允许多进程共享分区

第三章存储管理3.4.2.5分区共享◆只要2个进程空间包30第三章存储管理3.4.3页式管理◆把进程空间划分成较小的片段(称为页面)，把主存也划分成较小的片段(称为块)，使页长等于块长，恰好1页能占用主存的1块（图3-10）3.4.3.1数据结构◆图3-11◆图3-12第三章存储管理3.4.3页式管理◆把进程空间划分成较小的片31图3-10页式管理示意图进程空间分页页012块01234567主存分块图3-10页式管理示意图进程空间分页页012块012332图3-11虚空间表与各页表的关系

图3-11虚空间表与各页表的关系33图3-12主存空闲块表的数据结构

N-1N-20^┅head(a)空闲块链00110(b)位示图图3-12主存空闲块表的数据结构N-1N-2034图3-12主存空闲块表的数据结构

状态┇┇┇进程号┇

┇

┇页号┇

┇

┇n=当前空闲块数块号01┇┇┇N-1(c)主存分块表图3-12主存空闲块表的数据结构状态┇进程号┇页号35第三章存储管理3.4.3.2主存的分配与回收PROCEDUREcmalloc(x,p);BEGINK:=x/Block_size;IFN>=KTHENBEGINp:=getaPT; //申请一个页表区FORi=1TOKDOPT[i]:=getafreeblockEND //申请一个空闲块，把块号添入页表ELSEp:=0 //分配失败，返回零END.

其中x为进程所申请的主存空间大小，p为指向页表的指针。回收算法留给读者

第三章存储管理3.4.3.2主存的分配与回收PROCEDU36第三章存储管理3.4.3.3地址变换和保护措施◆图3-13◆图3-14第三章存储管理3.4.3.3地址变换和保护措施◆图3-1337图3-13页式地址变换控制寄存器有效地址寄存器页表长度页表始址pw┇B┇12345块号块Bw主存页表图3-13页式地址变换控制寄存器有效地址寄存器页表长度页38密码权限密钥现行PSW┄2┄正确访问：(密钥=密码）LOAD1块：不违反写保护STORE1块：不违反读保护非法访问STORE2块：违反写保护LOAD1块：密钥=密码块块块101112图3-14存储键保护法

密码权限密钥现行PSW┄2┄正确访问：(密钥=密码）LOA39第三章存储管理3.4.3.4性能研究◆通常在CPU和主存之间增设高速小型的联想寄存器组，称之为“快表”，用它存放现行进程页表中最近常用的部分表目

◆图3-15第三章存储管理3.4.3.4性能研究◆通常在CPU和主存之40图3-15快表的使用

页号┇块号┇pwBw页号块号图3-15快表的使用页号┇块号┇pwBw页号块号41第三章存储管理3.4.3.4性能研究◆设置快表后访问主存的流程如下：

(1)CPU给出虚地址(2)按p值联查快表，若找到块号B则转④否则转③(3)按p值找页表得号B，把p指向的页表表目读入快表，置换“旧表目”

(4)由B、w形成物理地址

(5)访问主存

(6)结束本次访问

第三章存储管理3.4.3.4性能研究◆设置快表后访问主存的42第三章存储管理3.4.3.5页面共享图3-16共享例程的页面

附接的共享页进程乙的原有页进程甲的原有页附接的共享页主存主存块号块号页号块5（共享例程第0页）块7（共享例程第1页）块9（共享例程第2页）页表第三章存储管理3.4.3.5页面共享图3-16共享例程43第三章存储管理3.4.4段式管理◆所谓“段(segment)”是指在逻辑上有完整意义的一组连续编址的代码◆段由程序员定义、能用<段名·段内符号地址>引用段内的信息◆经编译后，<段名·段内符号地址>转换成<段号·段内位移>第三章存储管理3.4.4段式管理◆所谓“段(segmen44第三章存储管理3.4.4段式管理◆每个分段必须分配在主存的一片地址连续的区域内，但各段之间不强求连续主存

◆同一作业内的各段组成二维地址空间V2图3-17第三章存储管理3.4.4段式管理◆每个分段必须分配在主存的45图3-17二维进程空间

主段子段其他段01┋K-1001┋K-1i01┋K-1m-i┉S0SiSm-i图3-17二维进程空间01┋K-1001┋K-1i46第三章存储管理3.4.4.1段式管理的实现◆段式管理的存储分配的描述性程序如下：

PROCEDUREcmalloc(k;s1,

s2,

…,Sk;p)；

BEGINp=getaST; //获得一个存放段表的空间

FORi:=1TokDOBEGINST[i]:=getaregion;IFnosuccessTHENp:=0ENDEND第三章存储管理3.4.4.1段式管理的实现◆段式管理的存储47图3-18段式地址变换图3-18段式地址变换48第三章存储管理3.5进程空间大于主存空间◆有2种主要的方法能“扩充”主存，第1种是覆盖，第2种是虚拟存储器

◆请求页式和请求段页式管理是实现虚存的2个具体方案

3.5.1请求页式管理3.5.1.1请求页式的实现第三章存储管理3.5进程空间大于主存空间◆有2种主要的方法49图3-20请求页式下指令执行过程

图3-20请求页式下指令执行过程50P——标记位，该页在主存置1，否则置0D——修改标记位，对该页内容修改时置1，否则置0A——引用标记位，任何一次对该页的引用，包括读、写、执行，都置1U/S——“用户/管理员”标记位

R/W——权限标记位

P——标记位，该页在主存置1，否则置051第三章存储管理3.5.1.1请求页面实现◆根据MBT可以回答“主存有空闲块吗”

◆一条指令的执行有可能产生多次缺页中断

◆对换区管理问题

第三章存储管理3.5.1.1请求页面实现◆根据MBT可以回52第三章存储管理3.5.1.2页面置换算法◆FIFO(FirstInFirstOut)即先进先出算法

页面访问序列： 7 0120304230321201701页面失效()：

图3-22当M=3时，FIFO算法示例

◆但FIFO有异常现象(Belady’sanomaly)，即M增加时

不能下降反而增加

第三章存储管理3.5.1.2页面置换算法◆FIFO(Fi53第三章存储管理3.5.1.2页面置换算法◆OPT(Optimal)即最优置换算法◆NUR(NotUsedRecently)算法

◆LRU(LeastRecentlyUsed)算法

①记时法

②寄存器法

第三章存储管理3.5.1.2页面置换算法◆OPT(Opt54第三章存储管理3.5.1.3性能研究

◆M与的关系

◆页面尺寸与的关系

◆

与主存有效存取时间的关系EAT≈页面传输时间ta

第三章存储管理3.5.1.3性能研究◆M与的关系◆55第三章存储管理3.5.1.3性能研究◆仅在本进程空间发生的颠簸称局部颠簸◆当系统内进程总数超过一定数额时，CPU的利用率反而急剧下降——系统进入颠簸

◆程序的局部性

第三章存储管理3.5.1.3性能研究◆仅在本进程空间发生的56第三章存储管理3.5.1.3性能研究◆工作集WS(workingset)是指在进程运行中距时刻ti最近的Δ次访问主存所涉及到的那些页面的集合

图3-23工作集第三章存储管理3.5.1.3性能研究◆工作集WS(work57第三章存储管理3.5.1.4对换区管理◆磁盘页表◆对换文件

第三章存储管理3.5.1.4对换区管理◆磁盘页表58第三章存储管理3.5.1.5页面共享图3-24请求页市式下的页面共享┅┅┇12┇┅100┇其它共享计数块号┅┅┇12┇┅100┇其它共享计数块号进程甲的页表进程乙的页表共享页┇┇主页块号100第三章存储管理3.5.1.5页面共享图3-24请求页59第三章存储管理3.5.1.6实例---UNIX系统V的存储管理

◆图3-25

◆图3-26第三章存储管理3.5.1.6实例---UNIX系统V的存储60图3-25虚存布局、地址结构与页表项格式图3-25虚存布局、地址结构与页表项格式61图3-26主存布局系统数据系统页表┇进程i的P0区页表进程i的P1区页表┇主存位示图进程0的页表进程0的栈区进程空间主存空闲快I/O专用≈≈图3-26主存布局系统数据系统页表┇进程i的P0区页62第三章存储管理3.5.2请求段页式管理3.5.2.1实现原理◆虚拟地址是二维的：<段号S,段内位移W>第三章存储管理3.5.2请求段页式管理3.5.2.1实现63图3-27请求段页式管理的地址变换

┇┇┇┇┇┇┇┇图3-27请求段页式管理的地址变换┇┇┇┇┇┇┇┇64第三章存储管理3.5.2.1实现原理◆越界中断处理

◆越权中断处理

◆缺页中断处理

◆链接中断处理

◆链接中断处理

第三章存储管理3.5.2.1实现原理◆越界中断处理◆越权65第三章存储管理3.5.2.2分段动态链接◆MULTICS方法（图）第三章存储管理3.5.2.2分段动态链接◆MULTICS66图3-28MULTICS的动态链接

┆load@13100┆L3104<X,Y>┆┆load@13100┆05120<X,Y>┆M段内部段号3(编译后链接前)内部段号3（链接后）间接字链接┆Y:12345┆0┆Y:12345┆1201485装入X段（未入主存）内部段号5（已入主存）┆┆3┆┆┆┆5段号段表图3-28MULTICS的动态链接┆load@67第三章存储管理3.5.2.2分段动态链接◆动态链接库(DLL)机制

◆动态链接程序分成链接和装入两个步骤

◆链接步骤中扫描DLL的输入库，并把一个目标模块名和一个数字入口点嵌入到用户的可执行文件中◆在装入步骤中，操作系统负责用那些在函数调用中能有效地使用的地址替换这些引用第三章存储管理3.5.2.2分段动态链接◆动态链接库(DL68第三章存储管理3.5.2.3分段共享图3-30第三章存储管理3.5.2.3分段共享图3-3069图3-29甲进程的5号段、乙进程的3号段共享X段

┇┇05M段：进程甲的段表X段的页表┇┇03N段：进程乙的段表图3-29甲进程的5号段、乙进程的3号段共享X段┇┇070第三章存储管理◆存储管理是指主存管理(外存管理见文件系统)，包括给进程分配主存片段，收回进程释放的主存片段，为分配出去的主存片段提供保护与共享，以及为作业提供一个虚拟的存储空间

第三章存储管理◆存储管理是指主存管理(外存管理见文件系统)，71第三章存储管理3.1物理主存

◆物理主存简称主存，它是计算机系统中的存储装置

◆个人计算机上通常都配有128MB的RAM，除了操作系统代码占用一部分外，余者皆为用户区域，由用户进程瓜分

第三章存储管理3.1物理主存◆物理主存简称主存，它是计72存储管理3.2存储概念和虚存管理

◆链接工作的实质是按照各个程序段之间的调用关系把各段的地址统一成从0开始的一维线性地址。链接既可在作业运行之前，也可在作业的程序段执行过程中依调用关系动态地进行。前者称为静态链接，由link程序完成；后者称为动态链接存储管理3.2存储概念和虚存管理◆链接工作的实质是按照73第三章存储管理3.2存储概念和虚存管理

◆从0开始的指令地址和数据段地址组成作业的地址空间，它是逻辑上的，与主存地址毫不相干，因此称为虚拟空间或虚拟存储器。虚存的容量与主存大小无关，它是由计算机系统的地址结构和寻址方式确定的

第三章存储管理3.2存储概念和虚存管理◆从0开始的指令74操作系统chapter课件575第三章存储管理3.2存储概念和虚存管理

◆

WindowsAPI控制进程的虚拟地址空间

◆(1)私用堆

用户使用HeapCreate()来产生私用堆空间

HANDLEHeapCreate(flOptions,dwInitialSize,dwMaximumSize)DWORDflOptions; //堆的分配标记

DWORDdwInitialSize; //堆的初始长度

DWORDdwMaximumSize;//堆的最大长度

第三章存储管理3.2存储概念和虚存管理◆Window76第三章存储管理3.2存储概念和虚存管理

◆(2)保留虚空间

LPVOIDVirtualAlloc(lpvAddress,cbSize,fdwAllocationType,fdwProtect)LPVOIDlpvAddress; //该区虚地址

DWORDcbSize; //该区域的长度

DWORDfdwAllocationType; //该区域被指定的类型

DWORDfdwProtect; //该区域的访问保护即访问权限

第三章存储管理3.2存储概念和虚存管理◆(2)保留虚77第三章存储管理3.2存储概念和虚存管理

◆(3)存储映射文件.最主要的虚存管理特性是通过存储映射支持共享虚存区域LPVOIDMapViewOfFile(hmapObect,fdwAccess,OffsetHigh,dwOffsetlow,cbMap)HANDLEhmapObject; //存储映射对象的句柄

DWORDfdwAccess; //访问模式

DWORDdwOffsetHigh; //32位地址的高位部分

DWORDdwOffsetLow; //32位地址的低位部分

DWORDcbMap; //映射的字节数

第三章存储管理3.2存储概念和虚存管理◆(3)存储映78第三章存储管理3.3地址变换

◆物理主存空间地址是一维线性排列的，不妨记作M={0,1,2,…,2m-1},表示主存容量为2m。例如，当m=23时，主存的容量为8MB。虚存的一维线性空间和二维线性空间分别记为：V1={0,1,2,…,2v-1}V2={0段{0,1,2,…,n0},1段{0,1,2,…,n1},…，s段{0,1,2,…,ns}}第三章存储管理3.3地址变换◆物理主存空间地址是一维线79第三章存储管理3.3地址变换

◆所谓地址变换(又称地址映射)就是把多个V空间映射到M空间上去，或者说是把虚存地址变换成物理主存地址

第三章存储管理3.3地址变换◆所谓地址变换(又称地址映80第三章存储管理3.4进程空间不大于主存空间的管理

图3-2第三章存储管理3.4进程空间不大于主存空间的管理图3-81图3-2固定分区原理图图3-2固定分区原理图82第三章存储管理3.4.1固定分区

◆由于进程空间(PS)的虚地址是从0开始递增编址的，因此装入模块在把它装入到分区时，必须把所有虚地址变换成从分区始址为起点的物理地址，其变换公式是：物理地址=虚地址+分区的始址

第三章存储管理3.4.1固定分区◆由于进程空间(PS)83第三章存储管理3.4.1固定分区

◆静态重定位(staticaddressrelocation)◆动态重定位(dynamicaddressrelocation)

如图3-3第三章存储管理3.4.1固定分区◆静态重定位(stat84图3-3动态重定位过程示意图图3-3动态重定位过程示意图85第三章存储管理3.4.1固定分区

◆固定分区的保护是指各进程空间在主存内运行时保证其每个物理地址都不超越自己的上下界限

◆

2种保护法（见图3-4）

◆对上下界保护法满足：(UR)≤物理地址<(LR)

◆对基址/限长保护法满足：(BR)≤物理地址<(BR)+(LR)

第三章存储管理3.4.1固定分区◆固定分区的保护是指各86操作系统chapter课件587第三章存储管理3.4.2可变分区

◆根据进程空间的实际大小按需分配主存空间

◆这种管理方法下，主存分区的个数，各区域的大小，在主存内活动的进程个数等都是随时间而变化的。所以，可变分区又称为动态分区

图3-5

图3-6第三章存储管理3.4.2可变分区◆根据进程空间的实际大88图3-5可变分区管理初始状态示例

图3-5可变分区管理初始状态示例89操作系统chapter课件590第三章存储管理3.4.2.1数据结构◆有2种数据结构，即自由区表FBT(FreeBlockTable)和自由区链FBC(FreeBlockChain)供可变分区管理选用

（图3-7）◆FBC的设计技巧在于，它利用自由区本身的空间记录自由区的大小及前后自由区的位置

第三章存储管理3.4.2.1数据结构◆有2种数据结构，91操作系统chapter课件592第三章存储管理3.4.2.2分区分配算法◆首次适应法(FirstFit)找到第1个能满足长度要求的自由区，从中截取所需空间

◆最佳适应法(BestFit)从自由区链中挑选能满足申请长度的最小自由区

◆最坏适应法(WorstFit)总是挑选最大的自由区分割给申请者

第三章存储管理3.4.2.2分区分配算法◆首次适应法(93第三章存储管理3.4.2.3分配/回收程序与优先级考虑

以首次适应算法和FBC结构为例，请求大小为x的自由存储区分配程序如下：

PROCEDUREget_block(x,p);BEGINi:=1;WHILE(FBC[i].size<>0)AND(FBC[i].size<x)DOi:=i+1;IFFBC[i].size=0THENp:=0ELSEBEGIN第三章存储管理3.4.2.3分配/回收程序与优先级考虑以首94存储管理3.4.2.3分配/回收程序与优先级考虑

p:=FBC[i].adder;y:=FBC[i].size-x;IFy>=THENBEGINFBC[i].size:=y;FBC[i].adder:=FBC[i].adder+x:ENDENDEND第三章存储管理3.4.2.3分配/回收程序与优先级考虑p95第三章存储管理3.4.2.3分配/回收程序与优先级考虑

◆回收过程(free_block)◆回收时要考虑回收的自由区是否与原自由区邻接

图3-8第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆回96操作系统chapter课件597第三章存储管理3.4.2.3分配/回收程序与优先级考虑

◆get_block算法越快，系统的性能越好

◆要研制快速get_block算法并且给予它以高的优先级以便尽快得到CPU响应

第三章存储管理3.4.2.3分配/回收程序与优先级考虑◆98第三章存储管理3.4.2.4地址变换与保护图3-9地址变换与保护第三章存储管理3.4.2.4地址变换与保护图3-9地址99第三章存储管理3.4.2.5分区共享◆只要2个进程空间包含相同的虚地址(如Windows95)，物理主存分区即被2进程所共享。同理，允许多进程共享分区

第三章存储管理3.4.2.5分区共享◆只要2个进程空间包100第三章存储管理3.4.3页式管理◆把进程空间划分成较小的片段(称为页面)，把主存也划分成较小的片段(称为块)，使页长等于块长，恰好1页能占用主存的1块（图3-10）3.4.3.1数据结构◆图3-11◆图3-12第三章存储管理3.4.3页式管理◆把进程空间划分成较小的片101图3-10页式管理示意图进程空间分页页012块01234567主存分块图3-10页式管理示意图进程空间分页页012块0123102图3-11虚空间表与各页表的关系

图3-11虚空间表与各页表的关系103图3-12主存空闲块表的数据结构

N-1N-20^┅head(a)空闲块链00110(b)位示图图3-12主存空闲块表的数据结构N-1N-20104图3-12主存空闲块表的数据结构

状态┇┇┇进程号┇

┇

┇页号┇

┇

┇n=当前空闲块数块号01┇┇┇N-1(c)主存分块表图3-12主存空闲块表的数据结构状态┇进程号┇页号105第三章存储管理3.4.3.2主存的分配与回收PROCEDUREcmalloc(x,p);BEGINK:=x/Block_size;IFN>=KTHENBEGINp:=getaPT; //申请一个页表区FORi=1TOKDOPT[i]:=getafreeblockEND //申请一个空闲块，把块号添入页表ELSEp:=0 //分配失败，返回零END.

其中x为进程所申请的主存空间大小，p为指向页表的指针。回收算法留给读者

第三章存储管理3.4.3.2主存的分配与回收PROCEDU106第三章存储管理3.4.3.3地址变换和保护措施◆图3-13◆图3-14第三章存储管理3.4.3.3地址变换和保护措施◆图3-13107图3-13页式地址变换控制寄存器有效地址寄存器页表长度页表始址pw┇B┇12345块号块Bw主存页表图3-13页式地址变换控制寄存器有效地址寄存器页表长度页108密码权限密钥现行PSW┄2┄正确访问：(密钥=密码）LOAD1块：不违反写保护STORE1块：不违反读保护非法访问STORE2块：违反写保护LOAD1块：密钥=密码块块块101112图3-14存储键保护法

密码权限密钥现行PSW┄2┄正确访问：(密钥=密码）LOA109第三章存储管理3.4.3.4性能研究◆通常在CPU和主存之间增设高速小型的联想寄存器组，称之为“快表”，用它存放现行进程页表中最近常用的部分表目

◆图3-15第三章存储管理3.4.3.4性能研究◆通常在CPU和主存之110图3-15快表的使用

页号┇块号┇pwBw页号块号图3-15快表的使用页号┇块号┇pwBw页号块号111第三章存储管理3.4.3.4性能研究◆设置快表后访问主存的流程如下：

(1)CPU给出虚地址(2)按p值联查快表，若找到块号B则转④否则转③(3)按p值找页表得号B，把p指向的页表表目读入快表，置换“旧表目”

(4)由B、w形成物理地址

(5)访问主存

(6)结束本次访问

第三章存储管理3.4.3.4性能研究◆设置快表后访问主存的112第三章存储管理3.4.3.5页面共享图3-16共享例程的页面

附接的共享页进程乙的原有页进程甲的原有页附接的共享页主存主存块号块号页号块5（共享例程第0页）块7（共享例程第1页）块9（共享例程第2页）页表第三章存储管理3.4.3.5页面共享图3-16共享例程113第三章存储管理3.4.4段式管理◆所谓“段(segment)”是指在逻辑上有完整意义的一组连续编址的代码◆段由程序员定义、能用<段名·段内符号地址>引用段内的信息◆经编译后，<段名·段内符号地址>转换成<段号·段内位移>第三章存储管理3.4.4段式管理◆所谓“段(segmen114第三章存储管理3.4.4段式管理◆每个分段必须分配在主存的一片地址连续的区域内，但各段之间不强求连续主存

◆同一作业内的各段组成二维地址空间V2图3-17第三章存储管理3.4.4段式管理◆每个分段必须分配在主存的115图3-17二维进程空间

主段子段其他段01┋K-1001┋K-1i01┋K-1m-i┉S0SiSm-i图3-17二维进程空间01┋K-1001┋K-1i116第三章存储管理3.4.4.1段式管理的实现◆段式管理的存储分配的描述性程序如下：

PROCEDUREcmalloc(k;s1,

s2,

…,Sk;p)；

BEGINp=getaST; //获得一个存放段表的空间

FORi:=1TokDOBEGINST[i]:=getaregion;IFnosuccessTHENp:=0ENDEND第三章存储管理3.4.4.1段式管理的实现◆段式管理的存储117图3-18段式地址变换图3-18段式地址变换118第三章存储管理3.5进程空间大于主存空间◆有2种主要的方法能“扩充”主存，第1种是覆盖，第2种是虚拟存储器

◆请求页式和请求段页式管理是实现虚存的2个具体方案

3.5.1请求页式管理3.5.1.1请求页式的实现第三章存储管理3.5进程空间大于主存空间◆有2种主要的方法119图3-20请求页式下指令执行过程

图3-20请求页式下指令执行过程120P——标记位，该页在主存置1，否则置0D——修改标记位，对该页内容修改时置1，否则置0A——引用标记位，任何一次对该页的引用，包括读、写、执行，都置1U/S——“用户/管理员”标记位

R/W——权限标记位

P——标记位，该页在主存置1，否则置0121第三章存储管理3.5.1.1请求页面实现◆根据MBT可以回答“主存有空闲块吗”

◆一条指令的执行有可能产生多次缺页中断

◆对换区管理问题

第三章存储管理3.5.1.1请求页面实现◆根据MBT可以回122第三章存储管理3.5.1.2页面置换算法◆FIFO(FirstInFirstOut)即先进先出算法

页面访问序列： 7 0120304230321201701页面失效()：

图3-22当M=3时，FIFO算法示例

◆但FIFO有异常现象(Belady’sanomaly)，即M增加时

不能下降反而增加

第三章存储管理3.5.1.2页面置换算法◆FIFO(Fi123第三章存储管理3.5.1.2页面置换算法◆OPT(Optimal)即最优置换算法◆NUR(NotUsedRecently)算法

◆LRU(LeastRecentlyUsed)算法

①记时法

②