1、问题问题:怎样实现存储器的扩充？怎样实现存储器的扩充？程序局部性原理与程序的局部装入程序局部性原理与程序的局部装入程序局部性原理程序局部性原理：对几乎所有的程序，在一段时间内，：对几乎所有的程序，在一段时间内，CPUCPU总是集中地访问程序中的某一个部分而不是随机地对总是集中地访问程序中的某一个部分而不是随机地对程序所有部分具有平均访问的概率。程序所有部分具有平均访问的概率。表现：时间局限性和空间局限性。表现：时间局限性和空间局限性。理解：进程的工作集理解：进程的工作集 (1)(1)程序在大多数情况下仍是顺序执行的。程序在大多数情况下仍是顺序执行的。(2)(2)过程调用的深度有限。过程调用的深
2、度有限。(3)(3)循环结构使得少数指令多次执行。循环结构使得少数指令多次执行。(4)(4)对数据结构的处理往往都局限于很小的范围内。对数据结构的处理往往都局限于很小的范围内。上述原理为在程序装载时只装入部分程序提供了理论上述原理为在程序装载时只装入部分程序提供了理论基础。基础。对页式管理：对页式管理：作业开始运行时只装入部分页面到内存中，如果要作业开始运行时只装入部分页面到内存中，如果要操作不在内存中的页，则由硬件产生缺页中断，请求将操作不在内存中的页，则由硬件产生缺页中断，请求将需要的页调入内存。需要的页调入内存。辅助页表（外页表）：在作业装载时建立在辅存上，辅助页表（外页表）：在作业装载
3、时建立在辅存上，记载虚页在辅存上的位置，以便在调页时能够快速地找记载虚页在辅存上的位置，以便在调页时能够快速地找到页的具体内容。到页的具体内容。4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 页表机制页表机制 请求分页的页表数据结构要能够记录页是否装入，请求分页的页表数据结构要能够记录页是否装入，同时还要为页面的换入换出提供支持。页表是实现请求同时还要为页面的换入换出提供支持。页表是实现请求分页的关键数据结构。分页的关键数据结构。在基本页表的基础上改进。在基本页表的基础上改进。页号 物理块号 状态位P 访问字段A 修改位M外存
4、地址 2.2.缺页中断机构缺页中断机构 每当程序要访问的页面不在内存时便产生一缺页每当程序要访问的页面不在内存时便产生一缺页中断，以请求中断，以请求OSOS将所缺的页调入内存将所缺的页调入内存页面B：A：654321指令copy ATO B缺页中断的特点：缺页中断的特点：在指令执行期间产生和处理中在指令执行期间产生和处理中断信号；断信号；一条指令执行期间，可能产生一条指令执行期间，可能产生多次缺页中断多次缺页中断调页中断：完成具体的调页操作，过程如下：调页中断：完成具体的调页操作，过程如下：查存储块表（查存储块表（MBTMBT）有无空闲块，有则装载页然后修改）有无空闲块，有则装载页然后修改PM
5、TPMT，MBTMBT；无则需按一定无则需按一定算法算法淘汰某页，如果该页修改过还要将淘汰某页，如果该页修改过还要将其写回辅存，装载页后修改其写回辅存，装载页后修改PMTPMT，MBTMBT。抖动：对同一页反复进行出页和入页操作的现象。也叫抖动：对同一页反复进行出页和入页操作的现象。也叫系统颠簸。系统颠簸。3.地地址址变变换换机机构构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否
6、页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是了解：了解：4.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.1.最小物理块数的确定最小物理块数的确定 指能保证进程正常运行所需的最小物理块数。进程应获指能保证进程正常运行所需的最小物理块数。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、格式、功能和寻址方式。如机器允许间接寻址时，则至少要功能和寻址方式。如机器允许间接寻址时，则至少要求有三个物理块。求有三个物理块。2.2.物理块的分配策略物理块的分配策略 在请求分页系统中，结合可采取的
7、内存分配和置换策在请求分页系统中，结合可采取的内存分配和置换策略，可组合出以下三种适用的策略。略，可组合出以下三种适用的策略。1)1)固定分配局部置换固定分配局部置换 2)2)可变分配全局置换可变分配全局置换 3)3)可变分配局部置换可变分配局部置换3.物理块分配算法物理块分配算法 1)平均分配算法 将系统中所有可供分配的物理块，平均分配给各个进程。但未考虑到各进程本身的大小。2)按比例分配算法 根据进程的大小按比例分配物理块的算法。3)考虑优先权的分配算法 在比例分配的基础上，根据各进程的优先权，适当地增加其相应份额。缺页率缺页率=缺页中断的次数缺页中断的次数/页面的总访问次数页面的总访问次
8、数 了解：了解：4.6.3 调页策略调页策略 1.1.何时调入页面何时调入页面1)1)预调页策略预调页策略 2)2)请求调页策略请求调页策略 2.2.从何处调入页面从何处调入页面 请求分页系统中外存分为两部分：文件区和用于存请求分页系统中外存分为两部分：文件区和用于存放对换页面的对换区。通常对换区是采用连续分配方式。放对换页面的对换区。通常对换区是采用连续分配方式。1 1）全部从对换区调入所需页面。）全部从对换区调入所需页面。2 2）不会被修改的文件，都直接从文件区调入。）不会被修改的文件，都直接从文件区调入。3 3）UNIXUNIX方式。凡未运行过的页面，都从文件区调入。方式。凡未运行过的页
9、面，都从文件区调入。曾经运行过但又被换出的页面，从对换区调入。曾经运行过但又被换出的页面，从对换区调入。UNIXUNIX系系统允许页面共享进一步减少调页。统允许页面共享进一步减少调页。4.7 页面置换算法页面置换算法 页面置换：页面淘汰。进程运行时不能从内存中获得新的页面置换：页面淘汰。进程运行时不能从内存中获得新的块来装载页，产生缺页中断，操作系统必须按一定的算法块来装载页，产生缺页中断，操作系统必须按一定的算法把已在主存的某页淘汰出去。把已在主存的某页淘汰出去。1.1.最佳最佳(Optimal)(Optimal)置换算法（置换算法（OPT OPT）最佳置换算法是由最佳置换算法是由Belad
10、yBelady于于19661966年提出的一种理论上年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长或许是在最长(未来未来)时间内不再被访问的页面。采用最佳时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，并考虑有以并考虑有以下的页面号引用串：下的页面号引用串：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
11、 1，7 7，0 0，1 1页面引用70770170122010320304243230321201201770101页框(物理块）203实际产生缺页时，操作系统不知道每个页的下次访问时间。实际产生缺页时，操作系统不知道每个页的下次访问时间。所以这种算法只具有理论意义。用来衡量算法的性能。所以这种算法只具有理论意义。用来衡量算法的性能。2.2.先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法选择在主存驻留时间最长（最先进入）的那一页淘汰。选择在主存驻留时间最长（最先进入）的那一页淘汰。系统保有相应的数据结构内存中的页。系统保有相应的数据结构内存中的页。页面引用707701701
12、22010323104430230321013201770201页框2304204230230127127011缺页中断的次数缺页中断的次数 12，是，是OPT方式的方式的2倍倍先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法特点：易实现，但效率不高。特点：易实现，但效率不高。有可能出现抖动：因为在主存时间最长的页很可能是访有可能出现抖动：因为在主存时间最长的页很可能是访问频率最高的页，则频繁地调入调出。问频率最高的页，则频繁地调入调出。了解：了解：BeladyBelady异常：异常：BeladyBelady在在19691969年发现，采用年发现，采用FIFOFIFO算法算法时
13、，为作业分配的主存块越多时，有时产生的缺页中断次时，为作业分配的主存块越多时，有时产生的缺页中断次数反而增多。数反而增多。q例：例：123412512345的访问序列在内存块为的访问序列在内存块为3和和4时的情况。时的情况。3.最近最久未使用最近最久未使用(LRU)置换算法置换算法 1 1）LRU(Least Recently Used)LRU(Least Recently Used)置换算法的描述置换算法的描述 遵循程序局部性原理，用遵循程序局部性原理，用“最近的过去最近的过去”作为作为“最近最近的将来的将来”的近似。有较好的实际效果。的近似。有较好的实际效果。引用序列70770170122
14、010320304403230321132201710701页框4024320321022）LRU置换算法的硬件支持置换算法的硬件支持（1）寄存器：每个在内存中的页面配置一个移位寄存器）寄存器：每个在内存中的页面配置一个移位寄存器R记记录每个页被访问的情况，定时右移录每个页被访问的情况，定时右移1位，这样值最小的位，这样值最小的R指示指示的是最近最久未访问的页。的是最近最久未访问的页。（2)栈：栈：每当进程访问某页面时，便将该页面的页面号从每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈顶始终是最新被访问页面的栈中移出，将它压入栈顶。栈顶始终是最新被访问页面的编号，而栈底则
15、是最近最久未使用的页面编号。编号，而栈底则是最近最久未使用的页面编号。44747074070471704101740107412107421207412107426210764.LRU近似算法近似算法 Clock置换算法置换算法 1 1）简单的）简单的ClockClock置换算法（置换算法（NRUNRU算法）算法）入口查寻指针前进一步，指向下一个表目页面访问位 0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针了解：了解：2 2）改进型改进型ClockClock置换算法置换算法 由访问位由访问位A和修改位和修改位M可组合成四种类型的页面：可组
16、合成四种类型的页面：1类类(A=0,M=0):最佳淘汰页。最佳淘汰页。2类类(A=0,M=1)：不是很好的淘汰页。：不是很好的淘汰页。3类类(A=1,M=0)：有可能再被访问。有可能再被访问。4类类(A=1,M=1):可能再被访问。可能再被访问。其执行过程可分成三步：其执行过程可分成三步：(1)从当前位置开始寻找从当前位置开始寻找A=0且且M=0的页面，的页面，将所遇到的第一个页面作将所遇到的第一个页面作为所选中的淘汰页。第一次不改变访问位为所选中的淘汰页。第一次不改变访问位A。(2)第二轮扫描寻找第二轮扫描寻找A=0且且M=1的页面，将所遇到的第一个这类页面作的页面，将所遇到的第一个这类页面
17、作为淘汰页。将所有扫描过的页面的访问位都置为淘汰页。将所有扫描过的页面的访问位都置0。(3)将指针返回到开始的位置，并将所有的访问位复将指针返回到开始的位置，并将所有的访问位复0。然后重复第一然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。u 虚拟存储器虚拟存储器 常规存储器管理方式的特征：一次性；驻留性。常规存储器管理方式的特征：一次性；驻留性。虚拟存储器的特征：多次性；对换性；虚拟性。虚拟存储器的特征：多次性；对换性；虚拟性。通过局部装入程序和缺页中断调页，可以实现为用户通过局部装入程序和缺页中断调
18、页，可以实现为用户提供一个比主存空间大得多的逻辑空间。提供一个比主存空间大得多的逻辑空间。特点：本质上是以处理机时间为代价，在内外存之间特点：本质上是以处理机时间为代价，在内外存之间不断交换信息；用户使用具有透明性方便；用户编程空间不断交换信息；用户使用具有透明性方便；用户编程空间不受限（只受处理机的地址空间限制）。不受限（只受处理机的地址空间限制）。：是指仅把作业的一部分装入内存便可运行作：是指仅把作业的一部分装入内存便可运行作业的存储器系统；是通过请求调入功能和置换功能，从逻业的存储器系统；是通过请求调入功能和置换功能，从逻辑上对内存容量进行扩充的一种存储器系统。辑上对内存容量进行扩充的一
19、种存储器系统。4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段存储管理方式的引入分段存储管理方式的引入 采用段式存储的必要性采用段式存储的必要性 线性地址空间的局限：线性地址与程序的逻辑结构线性地址空间的局限：线性地址与程序的逻辑结构无关，而作业自身逻辑结构上不同的部分（数据和子程序代无关，而作业自身逻辑结构上不同的部分（数据和子程序代码段）往往需要做针对性的处理。码段）往往需要做针对性的处理。如子程序的共享，数据段的动态增长。如子程序的共享，数据段的动态增长。共享逻辑上完整的代码的需要：按程序名或数据块名共享逻辑上完整的代码的需要：按程序名或数据块名共享。页面的共享不能实现
20、这一要求。共享。页面的共享不能实现这一要求。动态连接的需要动态连接的需要 数据的动态增长：在实际段长小于允许的最大段长的数据的动态增长：在实际段长小于允许的最大段长的范围内变化。范围内变化。4.4.2 4.4.2 分段系统的基本原理分段系统的基本原理 u段式存储的二维性：段地址是二维结构，各段的长度不段式存储的二维性：段地址是二维结构，各段的长度不定，段号之间无顺序关系，为一维；段内地址为一维线性定，段号之间无顺序关系，为一维；段内地址为一维线性空间，以空间，以“0”0”为首地址。为首地址。分段地址中的地址结构如下分段地址中的地址结构如下：段内连续。段间可以不连续。可装载段的最大长度受段内连续
21、。段间可以不连续。可装载段的最大长度受可用内存大小的限制可用内存大小的限制u 数据结构（段表数据结构（段表SMTSMT）：）：每一作业均有一个每一作业均有一个SMTSMT段号段号S S 段内偏移段内偏移W W利用段表实现地址映射 作业空间(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K30K20K15K10K40K80K120K150K段长 基址段号(MAIN)=030K(X)=120K(D)=215K(S)=310K040K80K120K150K段表内存空间0123控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008
22、 K9200基址位移量W82928K82928692主存物理地址有效地址分段系统的地址变换过程 u请求分段存储管理方式请求分段存储管理方式 1.1.请求分段中的硬件支持请求分段中的硬件支持 1 1）段表（段表（SMT)SMT)机制机制 段名 段长 段的基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存始址 每一作业均有一个每一作业均有一个SMTSMT，其中存在位（状态位）用于表，其中存在位（状态位）用于表示该段是否在主存；访问位和修改位作用类似请求分页的示该段是否在主存；访问位和修改位作用类似请求分页的页表，作为可否移出到辅存的依据；存取方式规定对本段页表，作为可否移出到辅存的依据；
23、存取方式规定对本段的访问方式。的访问方式。系统在内存中开辟固定的区域存放段表。系统在内存中开辟固定的区域存放段表。2）缺段中断机构缺段中断机构 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是3）地址变换机构）地址变换机构 访问sww段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A)(主存始址)(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否请求分段系统的地址变换过程2 分段的共享与保
24、护分段的共享与保护 1.1.共享段表共享段表:系统设置的数据结构系统设置的数据结构段名段长 内存始址 状态外存始址共享进程计数 count状态 进程名 进程号段号存取控制共享段表2.共享段的分配与回收共享段的分配与回收 1)共享段的分配 第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，在共享段表中增加一表项，把count置为1；当又有其它进程需要调用该共享段时，在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作。2)共享段的回收 撤销在进程段表中共享段所对应的表项，执行 count=count-1操作。若结果为0，才回收该共享段的物理内存。3.
25、分段保护分段保护 越界检查 2)存取控制检查 只读；只执行；读/写 3)环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据。一个程序可以调用驻留在相同环或较高特权环中的服务。环保护机构 调用返回调用返回环0环1环2(a)程序间的控制传输数据访问环0环1环2(b)数据访问数据访问4.分页和分段的主要区别分页和分段的主要区别 (1)(1)分页是为实现离散分配方式，以消减内存碎片，分页是为实现离散分配方式，以消减内存碎片，提高内存的利用率。是系统管理的需要。段则是信息的逻提高内存的利用率。是系统管理的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的辑单位，它含有一组其
26、意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。是为了能更好地满足用户的需要。(2)(2)页的大小固定且由系统决定，在系统中只能有一页的大小固定且由系统决定，在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写种大小的页面；而段的长度却不固定，决定于用户所编写的程序。的程序。(3)(3)分页的作业地址空间是一维的；分段的作业地址空分页的作业地址空间是一维的；分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。又需给出段内地址。（4）信息共享信息共享 ed 1ed 2ed 40data
27、 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表分页系统中共享是通过页表指向同样的块来实现分段系统中共享通过段表指向同样的段来实现 editor进程1data 1进程2editordata 2段表段长 基址16080402401608040380editordata 1data 280240280380420段式管理特点段式管理特点 优点：有效实现存储器的扩充和保护；便于实现段优点：有效实现存储器的扩充
28、和保护；便于实现段的动态连接，数据的动态增长，以及段的共享。的动态连接，数据的动态增长，以及段的共享。缺点：段内连续的特点使每个段的长度受可用连续缺点：段内连续的特点使每个段的长度受可用连续内存块大小的限制，碎片问题会出现，若要消除碎需要内存块大小的限制，碎片问题会出现，若要消除碎需要额外的系统开销。段式管理也可能出现抖动，一个操作额外的系统开销。段式管理也可能出现抖动，一个操作也要两次访问内存。也要两次访问内存。段页式管理段页式管理 将段式管理有利于段的动态增长和共享与页式管理将段式管理有利于段的动态增长和共享与页式管理克服碎片、提高存储器利用率结合起来的存储器管理模克服碎片、提高存储器利用
29、率结合起来的存储器管理模式。式。特点：特点：“段式管理，页次度量段式管理，页次度量”4.4.4 段页式存储管理方式段页式存储管理方式 基本原理基本原理 作业地址空间和地址结构如下：作业地址空间和地址结构如下：04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段利用段表和页表实现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器2.地址变换过程地址变换过程 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度段页式管理性能段页式管理性能优点：有效地实现存储管理的各项功能；优点：有效地实现存储管理的各项功能；兼有段式管理和页式管理的优点，即：消除碎兼有段式管理和页式管理的优点，即：消除碎 片，利于段的动态增长和共享。片，利于段的动态增长和共享。缺点：地址变换的系统开销较大。缺点：地址变换的系统开销较大。现代现代CPUCPU中都设计有实现段页式管理的机构，以用硬中都设计有实现段页式管理的机构，以用硬件来实现地址变换，保证执行的速度。件来实现地址变换，保证执行的速度。
