操作系统课件教材

4.7请求分页存储管理方式二.内存分配策略和分配算法1.最小物理块数的确定保证进程正常运行所需的最少物理块数；与硬件结构有关，取决于指令的格式、功能和寻址方式。2.物理块的分配和置换策略分配策略：固定分配、动态分配置换策略：局部置换、全局置换（1）固定分配局部置换

（2）可变分配全局置换

（3）可变分配局部置换

二.内存分配策略和分配算法3.物理块的分配算法平均分配算法将空闲物理块，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配物理块的。考虑优先权的分配算法优先权高的一次分得的物理块数多。三.调页策略1.调入页面的时机预调页策略：一次调入若干相邻的页；

用于进程首次调入内存时请求调页策略：运行中发生缺页时，只调入所缺的那一页2.从何处调入页面的问题系统拥有足够的对换区空间： 全部从对换区换入系统缺少足够的对换区空间：没运行过的页面、运行过但没被修改过的页面：文件区被修改过之后，再被换出的页面：对换区UNIX方式：未运行过的页面：文件区运行后被换出的页面：对换区3.页面的调入过程进程运行时，由地址变换机构向CPU发出缺页中断信号；CPU响应中断：保存进程的CPU现场，转中断处理程序；中断处理程序查找页表，得到该页在外存中的块号；若内存未满，则启动磁盘I/O读入缺页；若内存已满，先置换，再调入；最后修改页表对应项的内容。中断返回后，被中断进程产生缺页的那条指令将被重新执行三.调页策略4.8页面置换算法要调入缺页时，若内存中已没有空闲块，则必须根据一定的策略从内存中选择一个页面换出到外存。选择换出页面的算法称为页面置换算法。最佳置换算法（OPT）先进先出（FIFO）最近最久未使用置换算法（LRU）Clock置换算法（NRU）最少使用置换算法（LFU）页面缓冲置换算法（PBA）4.8页面置换算法一、最佳置换算法（OPT）选择以后永远不会被使用的页面或将来最长时间内不会被访问的页面淘汰出去。例：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用OPT计算缺页次数和缺页率。分析：如果所访问的页还没有装入内存，便将发生一次缺页中断。访问过程中发生缺页中断的次数就是缺页次数。缺页次数除以总的访问次数，就是缺页率。缺页中断m3m2×532×532√532×534×534√534×532√532√132×32√32√2m1252354251232页面走向使用OPT算法：缺页次数：6，置换次数：3次，缺页率：6/12=50%4.8页面置换算法一、最佳置换算法（OPT）特点：理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。4.8页面置换算法二、先进先出页面置换算法（FIFO）选择最先进入内存，即驻留内存时间最长的页予以淘汰。例：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用FIFO计算缺页次数和缺页率。缺页中断m3m2√253√453×423√423×425√425√125√135√132×32√32√2m1252354251232页面走向使用FIFO算法:缺页：9次，置换：6次，缺页率：(9/12)*100%=75%4.8页面置换算法二、先进先出页面置换算法（FIFO）特点：实现简单；与进程实际的运行规律不相适应。例：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。缺页中断最后进入↓435√435√352521521√521√214√143√432√321√21√1最先进入543215214321页面走向使用FIFO算法——物理块数为3:缺页次数：9，置换次数：6，缺页率：9/12最后进入使用FIFO算法——物理块数为4:缺页次数：10，置换次数：6次，缺页率：10/12内存块↑，缺页次数反而有可能↑——Belady现象。缺页中断√5432√4321√3215√2154√1543√543243214321√4321√321√21√1最先进入543215214321页面走向4.8页面置换算法三、最近最久未使用置换算法（LRU）

1.概念:选择在最近一段时间内最长时间未被使用（访问）的页面淘汰出去。缺页中断最近使用↓253523√235√354542√425251√512√12323√32√2最久未用252354251232页面走向使用LRU算法：缺页次数：7，缺页率：7/12（1）移位寄存器

对正在执行的进程，为它每个在内存中的页面配置一个移位寄存器R：当进程访问一物理块时，将其对应寄存器的最高位置1；每隔一定时间将所有移位寄存器右移一位，高位填0；值最小的寄存器所对应的页面就是最近最久未使用的页面。2.LRU置换算法的硬件支持：101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页LRU置换算法的硬件支持：（2）栈

利用一个特殊的栈来保存当前使用的各个页面的页面号。当进程访问此页面时，将该页面的页面号从栈中移出，压入栈顶。因此栈顶是最新被访问页面的编号，栈底是最近最久未使用页面的页面号。2.LRU置换算法的硬件支持：3.LRU置换算法的软件实现：

每个页面设置一个年龄字段，每隔一定的时间将该字段加1，访问某个页时将该字段清0。选择年龄最大的页面换出。

4.8页面置换算法三、最近最久未使用置换算法（LRU）特点：性能较好实现复杂：软件实现费时；硬件实现，增加系统成本。时间局部性原理四、Clock置换算法

（1）简单的clock置换算法：每页设置一位访问位。当某页被访问了，则访问位置“1”。内存中的所有页链接成一个循环队列；置换算法：循环检查各页面的使用情况。若访问位为“0”，选择该页淘汰；若访问位为“1”，复位访问位为“0”，查询指针前进一步。又称为“最近未使用”置换算法（NRU）4.8页面置换算法四、Clock置换算法（2）改进型Clock置换算法访问位A、修改位M页面的四种状态：A=0,M=0：最近未被访问也未被修改A=0,M=1：最近未被访问但已被修改A=1,M=0：最近已被访问但未被修改A=1,M=1：最近已被访问且被修改最佳淘汰页第二选择不应淘汰的页四、Clock置换算法（2）改进型Clock置换算法选择淘汰页的过程（最多可能要四轮扫描）：①第一轮扫描：查找A=0,M=0页面，找到便将此页选作淘汰页；若扫描一轮后还未找到，则进入下一步；②第二轮扫描：查找A=0,M=1页面，查找过程中需将A位复位为“0”，找到便将此页选作淘汰页；若扫描一轮后还未找到，则重复①，如仍然没找到，则再重复②。4.8页面置换算法五、最少使用置换算法（LFU）选择在最近时期使用次数最少的页面淘汰。（频率）需为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置1，此后每隔一定时间自动右移一位，最右边的位填充0。最近一段时间最少使用的页面是∑Ri

最小的页。4.8页面置换算法101101108110000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页×√未被修改已被修改4.8页面置换算法六、页面缓冲置换算法采用可变分配、局部置换策略；页面置换算法为FIFO算法空闲页面链表已修改页面链表空闲内存块

空白内存块或未修改淘汰页所在内存块已修改淘汰页所在内存块淘汰页置换时，分配给换入页的内存块并不是淘汰页的内存块。：插入空闲页面链表末尾：插入已修改页面链表末尾将空闲页面链表链首的内存块分配给换入页。如：VAX/VMS操作系统页面缓冲算法举例：（1）系统初始化完成后假设系统内存有10个空闲块，则相应空闲内存块链表为：空闲页面链表：已修改页面链表：Null（2）创建P1进程，分配4个块，则分配到0,1,2,3四块，此时空闲页面链表变为：0198765432987654页面缓冲算法举例：（3）P1装入0,1,2,3四个页面：0132013201320132M的值：100（4）P1访问0页、1页、2页，其中0页修改，1页、2页不修改：（5）若P1要写第5页987654空闲页面链表已修改页面链表页面缓冲算法举例：按照FIFO，淘汰第0块中的第0页，因为该页已修改过，所以将空闲块0插入已修改页面链表；将空闲页面链表链首的第4块分配给P1，装入P1的第5页。009876551324132M：1000进程P1占据内存情况：空闲页面链表已修改页面链表（6）若P1要读第6页页面缓冲算法举例：按照FIFO，淘汰第1块中的第1页，因为该页没修改过，所以将空闲块1插入空闲页面链表；将空闲页面链表链首的第5块分配给P1，装入P1的第6页。0062535243M：0001进程P1占据内存情况：空闲页面链表已修改页面链表（7）若P1要读第1页198761页面缓冲算法举例：按照FIFO，淘汰第2块中的第2页，因为该页没修改过，所以将空闲块2插入空闲页面链表；从空闲页面链表中摘下第1块（其中有P1的第1页）分配给P1。0013651354M：0100进程P1占据内存情况：空闲页面链表已修改页面链表987622页面缓冲算法举例：（7）P1读1页，系统处理方式为：已修改页面链表：空闲页面链表：进程P1占据内存情况：9876225314531M的值：1000600一、缺页率对有效访问时间的影响

设缺页率为P，则有效访问时间为：

(1-P)*内存访问时间+P*缺页中断处理时间4.9请求分页系统的性能分析缺页中断处理时间缺页中断服务时间；读入缺页所需时间；重新执行访存指令时间。例：若某请求分页系统的平均缺页中断时间约为25ms，存储器的平均访问时间为100ns，设缺页率为P，则有效访问时间为：

（1－p）×0.1+p×25000=0.1+24999.9p

（微秒）如果希望在缺页时，仅使有效访问时间延长不超过10%，则可计算出缺页率p0.1+24999.9p<0.1×(1+10%)则P＜（0.01/24999.9）=0.0000004一、缺页率对有效访问时间的影响：

由此可知，要求在2500000次的访问中，才发生一次缺页，即请求分页式存储管理应保持非常低的缺页率，否则将使程序的执行速度受到严重影响。此外，提高磁盘I/O速度，对改善请求分页系统的性能至关重要。为此，应选用高速磁盘和高速磁盘接口。二、抖动的基本概念：

1.抖动的概念及产生的原因：全局置换策略

2.抖动的预防：

（1）采取局部置换策略；（2）引入工作集概念：工作集就是进程在某段时间段Δ里实际要访问的页面的集合。具体地说，运行进程在时间t－Δ到t这个时间段内所访问的页面的集合称为该进程在时间t的工作集，变量Δ称为工作集“窗口尺寸”（WindowsSize）。4.9请求分页系统的性能分析二、抖动的基本概念：2.抖动的预防：（3）L=S原则：

L：进程产生缺页的平均时间；

S：系统进行缺页中断处理的平均时间。（4）挂起若干进程，降低多道程序度。4.9请求分页系统的性能分析4.10请求分段存储管理方式

以基本分段内存管理为基础，程序运行前，只需先调入部分分段，便启动执行。其它分段在需要时，通过缺段中断处理程序临时调入。1请求分段中的硬件支持2请求分段中的分段共享3请求分段中的分段保护4.10请求分段存储管理方式请求分段存储管理系统的示意图：存储空间作业空间10K0（S）=312K0（D）=28K0（X）=120K0（MAIN）=0状态段表基址段长段号20K030K8K190K12K2150K10K3200K1101200K030K90K150K(MAIN)=020K（X）=18K（S）=310K4.10请求分段存储管理方式一.请求分段中的硬件支持1.段表机制段名(号)段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址(1)存取方式：存取属性为只执行、只读或允许读/写(2)访问字段A：记录该段被访问的频繁程度(3)修改位M：该段在进入内存后是否被修改过(4)存在位P：指示本段是否已调入内存(5)增补位：表示本段在运行过程中，是否做过动态增长(6)外存始址：本段在外存中的起始地址，即起始盘块号一.请求分段中的硬件支持2.缺段中断机构虚段S不在内存返回阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空闲区链唤醒请求进程空区容量总和能否满足？否空区拼接，以形成一个合适的空区淘汰一个或几个实段以形成一个合适空区是否是段基址，存在位在指令执行期间产生和处理中断信号一条指令在执行期间可能产生多次缺段中断一.请求分段中的硬件支持3.地址变换机构返回W≤段长？修改访问位、修改位形成访问主存地址(A)=(主存始址)+(位移量W)是符合存取方式？段S在主存？分段越界中断处理分段保护中断处理缺段中断处理是是否否否访问[S][W]S＜段表长度？分段越界中断处理否是4.9请求分段存储管理方式二.分段共享:

1.共享段表公用信息；私用信息共享进程计数count：记录要共享该段的进程数目存取控制字段：对一共享段，给不同进程不同权限段号：不同进程可以调用不同段号去共享某共享段段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制…………二.分段共享2.共享段的内存分配（1）共享段第一次被访问：为共享段分配内存，并装入；修改进程段表；修改共享段表：增加一个共享段表项。

（2）共享段已在内存修改进程段表；修改共享段表：增加一个该进程的私有信息3.共享段的回收4.10请求分段存储管理方式三.分段保护

1.越界检查段表寄存器：段表始址、段表长度逻辑地址：段号；段内地址。比较：段号—段表长度2.存取控制检查段表项：存取控制字段（只读、只执行、读/写）段长—段内地址4.10请求分段存储管理方式三.分段保护3.环保护机构低编号的环具有高优先权。程序可以访问驻留在相同环或较低特权环中的数据；程序可以调用驻留在相同环或较高特权环中的服务。3.环保