《操作系统课件.ppt》由会员分享，可在线阅读，更多相关《操作系统课件.ppt（49页珍藏版）》请在第壹文秘上搜索。
1、1. 最小物理块数的确定最小物理块数的确定 保证进程正常运行所需的最少物理块数；保证进程正常运行所需的最少物理块数； 与硬件结构有关，取决于指令的格式、功能和寻址方与硬件结构有关，取决于指令的格式、功能和寻址方式式。2.物理块的分配和置换策略物理块的分配和置换策略 分配策略：固定分配、动态分配分配策略：固定分配、动态分配 置换策略：局部置换、全局置换置换策略：局部置换、全局置换（1）固定分配局部置换）固定分配局部置换（2）可变分配全局置换）可变分配全局置换（3）可变分配局部置换）可变分配局部置换3. 物理块的分配算法物理块的分配算法 平均分配算法平均分配算法将空闲物理块，平均分配给各个进程。将
2、空闲物理块，平均分配给各个进程。 按比例分配算法按比例分配算法根据进程的大小按比例分配物理块的。根据进程的大小按比例分配物理块的。 考虑优先权的分配算法考虑优先权的分配算法优先权高的一次分得的物理块数多。优先权高的一次分得的物理块数多。1. 调入页面的时机调入页面的时机 预调页策略：一次调入若干相邻的页；预调页策略：一次调入若干相邻的页； 用于进程首次调入内存时用于进程首次调入内存时 请求调页策略：运行中发生缺页时，只调入所缺的那一页请求调页策略：运行中发生缺页时，只调入所缺的那一页2. 从何处调入页面的问题从何处调入页面的问题 系统拥有足够的对换区空间：系统拥有足够的对换区空间： 全部从对换
3、区换入全部从对换区换入 系统缺少足够的对换区空间系统缺少足够的对换区空间 ： 没运行过的页面、运行过但没被修改过的页面：文件区没运行过的页面、运行过但没被修改过的页面：文件区 被修改过之后，再被换出的页面：对换区被修改过之后，再被换出的页面：对换区 UNIX方式：方式：未运行过的页面：文件区未运行过的页面：文件区运行后被换出的页面：对换区运行后被换出的页面：对换区3. 页面的调入过程页面的调入过程 进程运行时，由地址变换机构向进程运行时，由地址变换机构向CPU发出缺页中断信号；发出缺页中断信号； CPU响应中断：保存进程的响应中断：保存进程的CPU现场，转中断处理程序；现场，转中断处理程序；
4、中断处理程序查找页表，得到该页在外存中的块号；中断处理程序查找页表，得到该页在外存中的块号； 若内存未满，则启动磁盘若内存未满，则启动磁盘I/O读入缺页；若内存已满，先置读入缺页；若内存已满，先置换，再调入；换，再调入； 最后修改页表对应项的内容。最后修改页表对应项的内容。 中断返回后，被中断进程产生缺页的那条指令将被重新执行中断返回后，被中断进程产生缺页的那条指令将被重新执行 要调入缺页时，若内存中已没有空闲块，则必须要调入缺页时，若内存中已没有空闲块，则必须根据一定的策略从内存中选择一个页面换出到外根据一定的策略从内存中选择一个页面换出到外存。选择换出页面的算法称为页面置换算法。存。选择换
5、出页面的算法称为页面置换算法。 最佳置换算法（最佳置换算法（OPT） 先进先出（先进先出（FIFO） 最近最久未使用置换算法（最近最久未使用置换算法（LRU） Clock置换算法（置换算法（NRU） 最少使用置换算法（最少使用置换算法（LFU） 页面缓冲置换算法（页面缓冲置换算法（PBA） 选择以后选择以后永远不会被使用永远不会被使用的页面或的页面或将来最长时将来最长时间内不会被访问间内不会被访问的页面淘汰出去。的页面淘汰出去。 例：在一个请求分页系统中，假定系统分给一个作例：在一个请求分页系统中，假定系统分给一个作业的业的物理块数为物理块数为3，并且此作业的页面走向为，并且此作业的页面走向为
6、2，3，2，1，5，2，4，5，3，2，5，2。用。用OPT计算缺页次数和计算缺页次数和缺页率。缺页率。 分析：如果所访问的页还没有装入内存，便将发生分析：如果所访问的页还没有装入内存，便将发生一次缺页中断。访问过程中发生缺页中断的次数就是一次缺页中断。访问过程中发生缺页中断的次数就是缺缺页次数。页次数。缺页次数除以总的访问次数，就是缺页次数除以总的访问次数，就是缺页率。缺页率。缺页缺页中断中断m3m253253253253453453453253213232322m1252354251232页面页面走向走向使用使用OPT算法：算法：缺页次数：缺页次数：6，置换次数：，置换次数：3次，缺页率：
7、次，缺页率：6/12=50% 特点：特点：理论上，性能最佳；实际上，无法实现；理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。通常用该算法来评价其他算法的优劣。 选择选择最先进入内存，即驻留内存时间最长的页最先进入内存，即驻留内存时间最长的页予以淘汰。予以淘汰。 例：在一个请求分页系统中，假定系统分给一个作例：在一个请求分页系统中，假定系统分给一个作业的业的物理块数为物理块数为3，并且此作业的页面走向为，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用。用FIFO计算缺页次数计算缺页次数和缺页率。和缺页率。缺页缺页中断中断m3m2253453423
8、42342542512513513232322m1252354251232页面页面走向走向使用使用FIFO算法算法:缺页：缺页：9次，置换：次，置换：6次，缺页率：次，缺页率：(9/12) *100%=75% 特点：特点：实现简单；实现简单；与进程实际的运行规律不相适应。与进程实际的运行规律不相适应。 例：在一个请求分页系统中，假如一个作业的页面走例：在一个请求分页系统中，假如一个作业的页面走向为向为1，2，3，4，1，2，5，1，2，3，4，5, 当分给该当分给该作业的物理块数作业的物理块数M分别为分别为3和和4时，请用时，请用FIFO计算缺页计算缺页次数和缺页率，并比较所得的结果。次数和缺
9、页率，并比较所得的结果。缺页缺页中断中断最后最后进入进入435435352521521521214143432321211最先最先进入进入543215214321页面页面走向走向使用使用FIFO算法算法物理块数为物理块数为3:缺页次数：缺页次数：9，置换次数：，置换次数：6，缺页率：，缺页率：9/12最后最后进入进入使用使用FIFO算法算法物理块数为物理块数为4:缺页次数：缺页次数：10，置换次数：，置换次数：6次，缺页率：次，缺页率：10/12内存块内存块，缺页次数反而有可能，缺页次数反而有可能 Belady现象。现象。缺页缺页中断中断5432432132152154154354324321
10、43214321321211最先最先进入进入543215214321页面页面走向走向 1. 概念概念: 选择在选择在最近一段时间内最长时间未被使最近一段时间内最长时间未被使用（访问）用（访问）的页面淘汰出去。的页面淘汰出去。缺页缺页中断中断最近最近使用使用25352323535454242525151212323322最久最久未用未用252354251232页面页面走向走向使用使用LRU算法：算法：缺页次数：缺页次数：7，缺页率：，缺页率：7/12（ 1）移位寄存器）移位寄存器 对正在执行的进程，为它每个在内存中的页面配置一个移位寄对正在执行的进程，为它每个在内存中的页面配置一个移位寄存器存器
11、R： 当进程访问一物理块时，将其对应寄存器的最高位置当进程访问一物理块时，将其对应寄存器的最高位置1； 每隔一定时间将所有移位寄存器右移一位，高位填每隔一定时间将所有移位寄存器右移一位，高位填0； 值最小的寄存器所对应的页面就是最近最久未使用的页面。值最小的寄存器所对应的页面就是最近最久未使用的页面。2. LRU2. LRU置换算法的硬件支持：置换算法的硬件支持：101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页实页LRULRU置换算法的硬件支持：置换算法的硬件支
12、持：（ 2）栈）栈 利用一个利用一个特殊的栈特殊的栈来保存当前使用的各个页面的来保存当前使用的各个页面的页面号。当进程访问此页面时，将该页面的页面号页面号。当进程访问此页面时，将该页面的页面号从栈中移出，压入栈顶。因此栈顶是最新被访问页从栈中移出，压入栈顶。因此栈顶是最新被访问页面的编号，面的编号，栈底栈底是最近最久未使用页面的页面号。是最近最久未使用页面的页面号。2.LRU2.LRU置换算法的硬件支持：置换算法的硬件支持：3.LRU3.LRU置换算法的软件实现：置换算法的软件实现： 每个页面设置一个年龄字段，每隔一定的时间将每个页面设置一个年龄字段，每隔一定的时间将该字段加该字段加1 1，访
13、问某个页时将该字段清，访问某个页时将该字段清0 0。选择年龄。选择年龄最大的页面换出。最大的页面换出。 特点：特点：性能较好性能较好实现复杂：软件实现费时；硬件实现，增加系统成实现复杂：软件实现费时；硬件实现，增加系统成本。本。时间局部性原理时间局部性原理 （1）简单的）简单的clock置换算法：置换算法： 每页设置一位访问位。每页设置一位访问位。当某页被访问了，则访问位置当某页被访问了，则访问位置“1”。 内存中的所有页链接成一个循环队列；内存中的所有页链接成一个循环队列； 置换算法：置换算法： 循环检查各页面的使用情况。循环检查各页面的使用情况。 若访问位为若访问位为“0”，选择该页淘汰；
14、若访问位为，选择该页淘汰；若访问位为“1”，复位访问位为，复位访问位为“0”，查询指针前进一步。，查询指针前进一步。又称为又称为“最近未使用最近未使用”置换算法（置换算法（NRU）（2）改进型）改进型Clock置换算法置换算法 访问位访问位A、修改位、修改位M 页面的四种状态：页面的四种状态： A=0,M=0：最近未被访问也未被修改：最近未被访问也未被修改 A=0,M=1：最近未被访问但已被修改：最近未被访问但已被修改 A=1,M=0：最近已被访问但未被修改：最近已被访问但未被修改 A=1,M=1：最近已被访问且被修改：最近已被访问且被修改最佳淘汰页最佳淘汰页第二选择第二选择不应淘汰的页不应淘
15、汰的页（2）改进型）改进型Clock置换算法置换算法 选择淘汰页的过程（最多可能要四轮扫描）：选择淘汰页的过程（最多可能要四轮扫描）：第一轮扫描：查找第一轮扫描：查找A=0,M=0页面，找到便将此页选作淘页面，找到便将此页选作淘汰页；若扫描一轮后还未找到，则进入下一步；汰页；若扫描一轮后还未找到，则进入下一步；第二轮扫描：查找第二轮扫描：查找A=0,M=1页面，查找过程中需将页面，查找过程中需将A位位复位为复位为“0”，找到便将此页选作淘汰页；若扫描一轮后，找到便将此页选作淘汰页；若扫描一轮后还未找到，则重复还未找到，则重复 ，如仍然没找到，则再重复，如仍然没找到，则再重复 。 选择在最近时期
16、使用次数最少的页面淘汰。（频率）选择在最近时期使用次数最少的页面淘汰。（频率） 需为在内存中的每个页面设置一个移位寄存器，用来需为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。记录该页面被访问的频率。 每次访问某页时，便将该移位寄存器的最高位置每次访问某页时，便将该移位寄存器的最高位置1，此，此后每隔一定时间自动右移一位，最右边的位填充后每隔一定时间自动右移一位，最右边的位填充0。 最近一段时间最少使用的页面是最近一段时间最少使用的页面是Ri 最小的页。最小的页。101101108110000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R实页实页未被修改未被修改已被修改已被修改 采用可变分配、局部置换策略；采用可变分配、局部置换策略； 页面置换算法为页面置换算法为FIFO算法算法空闲页面链表空闲页面链表已修改页面链表已修改页面链表 空闲内存块空闲内存块 空白内存块或未修改空白内存块或未修改淘汰页所在内存块淘汰页所在内存块已修改淘汰页所在内已修改淘汰页所在内存块存块
