《操作系统课件.ppt》由会员分享，可在线阅读，更多相关《操作系统课件.ppt（49页珍藏版）》请在三一办公上搜索。
1、4.7 请求分页存储管理方式,二.内存分配策略和分配算法1.最小物理块数的确定保证进程正常运行所需的最少物理块数；与硬件结构有关，取决于指令的格式、功能和寻址方式。2.物理块的分配和置换策略分配策略：固定分配、动态分配置换策略：局部置换、全局置换,（1）固定分配局部置换（2）可变分配全局置换（3）可变分配局部置换,二.内存分配策略和分配算法,3.物理块的分配算法平均分配算法将空闲物理块，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配物理块的。考虑优先权的分配算法优先权高的一次分得的物理块数多。,三.调页策略,1.调入页面的时机预调页策略：一次调入若干相邻的页；用于进程首次调入内存时
2、请求调页策略：运行中发生缺页时，只调入所缺的那一页2.从何处调入页面的问题系统拥有足够的对换区空间：全部从对换区换入系统缺少足够的对换区空间：没运行过的页面、运行过但没被修改过的页面：文件区 被修改过之后，再被换出的页面：对换区UNIX方式：未运行过的页面：文件区运行后被换出的页面：对换区,3.页面的调入过程进程运行时，由地址变换机构向CPU发出缺页中断信号；CPU响应中断：保存进程的CPU现场，转中断处理程序；中断处理程序查找页表，得到该页在外存中的块号；若内存未满，则启动磁盘I/O读入缺页；若内存已满，先置换，再调入；最后修改页表对应项的内容。中断返回后，被中断进程产生缺页的那条指令将被重
3、新执行,三.调页策略,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计算缺页次数和缺
4、页率。,分析：如果所访问的页还没有装入内存，便将发生一次缺页中断。访问过程中发生缺页中断的次数就是缺页次数。缺页次数除以总的访问次数，就是缺页率。,缺页中断,m3,m2,5,3,2,5,3,2,5,3,2,5,3,4,5,3,4,5,3,4,5,3,2,5,3,2,1,3,2,3,2,3,2,2,m1,2,5,2,3,5,4,2,5,1,2,3,2,页面走向,使用OPT算法：,缺页次数：6，置换次数：3次，缺页率：6/12=50%,4.8 页面置换算法,一、最佳置换算法（OPT）特点：理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。,4.8 页面置换算法,二、先进先出页面
5、置换算法（FIFO）选择最先进入内存，即驻留内存时间最长的页予以淘汰。,例：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用FIFO计算缺页次数和缺页率。,缺页中断,m3,m2,2,5,3,4,5,3,4,2,3,4,2,3,4,2,5,4,2,5,1,2,5,1,3,5,1,3,2,3,2,3,2,2,m1,2,5,2,3,5,4,2,5,1,2,3,2,页面走向,使用FIFO算法:,缺页：9次，置换：6次，缺页率：(9/12)*100%=75%,4.8 页面置换算法,二、先进先出页面置换算法（FIFO）特点：
6、实现简单；与进程实际的运行规律不相适应。,例：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。,缺页中断,最后进入,4,3,5,4,3,5,3,5,2,5,2,1,5,2,1,5,2,1,2,1,4,1,4,3,4,3,2,3,2,1,2,1,1,最先进入,5,4,3,2,1,5,2,1,4,3,2,1,页面走向,使用FIFO算法物理块数为3:,缺页次数：9，置换次数：6，缺页率：9/12,最后进入,使用FIFO算法物理块数为4:,缺页次数：10，置换次数：
7、6次，缺页率：10/12内存块，缺页次数反而有可能 Belady现象。,缺页中断,5,4,3,2,4,3,2,1,3,2,1,5,2,1,5,4,1,5,4,3,5,4,3,2,4,3,2,1,4,3,2,1,4,3,2,1,3,2,1,2,1,1,最先进入,5,4,3,2,1,5,2,1,4,3,2,1,页面走向,4.8 页面置换算法,三、最近最久未使用置换算法（LRU）1.概念:选择在最近一段时间内最长时间未被使用（访问）的页面淘汰出去。,缺页中断,最近使用,2,5,3,5,2,3,2,3,5,3,5,4,5,4,2,4,2,5,2,5,1,5,1,2,1,2,3,2,3,3,2,2,最久
8、未用,2,5,2,3,5,4,2,5,1,2,3,2,页面走向,使用LRU算法：,缺页次数：7，缺页率：7/12,（1）移位寄存器 对正在执行的进程，为它每个在内存中的页面配置一个移位寄存器R：当进程访问一物理块时，将其对应寄存器的最高位置1；每隔一定时间将所有移位寄存器右移一位，高位填0；值最小的寄存器所对应的页面就是最近最久未使用的页面。,2.LRU置换算法的硬件支持：,LRU置换算法的硬件支持：,（2）栈 利用一个特殊的栈来保存当前使用的各个页面的页面号。当进程访问此页面时，将该页面的页面号从栈中移出，压入栈顶。因此栈顶是最新被访问页面的编号，栈底是最近最久未使用页面的页面号。,2.LR
9、U置换算法的硬件支持：,3.LRU置换算法的软件实现：每个页面设置一个年龄字段，每隔一定的时间将该字段加1，访问某个页时将该字段清0。选择年龄最大的页面换出。,4.8 页面置换算法,三、最近最久未使用置换算法（LRU）特点：性能较好实现复杂：软件实现费时；硬件实现，增加系统成本。,时间局部性原理,四、Clock置换算法（1）简单的clock置换算法：每页设置一位访问位。当某页被访问了，则访问位置“1”。内存中的所有页链接成一个循环队列；置换算法：循环检查各页面的使用情况。若访问位为“0”，选择该页淘汰；若访问位为“1”，复位访问位为“0”，查询指针前进一步。又称为“最近未使用”置换算法（NRU
10、）,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”，找到便将此页选作淘汰页；若扫描一轮后还未
11、找到，则重复，如仍然没找到，则再重复。,4.8 页面置换算法,五、最少使用置换算法（LFU）选择在最近时期使用次数最少的页面淘汰。（频率）需为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置1，此后每隔一定时间自动右移一位，最右边的位填充0。最近一段时间最少使用的页面是Ri 最小的页。,4.8页面置换算法,未被修改已被修改,4.8 页面置换算法,六、页面缓冲置换算法采用可变分配、局部置换策略；页面置换算法为FIFO算法,空闲页面链表已修改页面链表,空闲内存块,空白内存块或未修改淘汰页所在内存块,已修改淘汰页所在内存块,淘汰页,置换时，
12、分配给换入页的内存块并不是淘汰页的内存块。,：插入空闲页面链表末尾：插入已修改页面链表末尾,将空闲页面链表链首的内存块分配给换入页。,如：VAX/VMS操作系统,页面缓冲算法举例：,（1）系统初始化完成后假设系统内存有10个空闲块，则相应空闲内存块链表为：空闲页面链表：已修改页面链表：Null（2）创建P1进程，分配4个块，则分配到0,1,2,3四块，此时空闲页面链表变为：,页面缓冲算法举例：,（3）P1装入0,1,2,3四个页面：,（4）P1访问0页、1页、2页，其中0页修改，1页、2页不修改：,（5）若P1要写第5页,空闲页面链表,已修改页面链表,页面缓冲算法举例：,按照FIFO，淘汰第0
13、块中的第0页，因为该页已修改过，所以将空闲块0插入已修改页面链表；将空闲页面链表链首的第4块分配给P1，装入P1的第5页。,进程P1占据内存情况：,空闲页面链表,已修改页面链表,（6）若P1要读第6页,页面缓冲算法举例：,按照FIFO，淘汰第1块中的第1页，因为该页没修改过，所以将空闲块1插入空闲页面链表；将空闲页面链表链首的第5块分配给P1，装入P1的第6页。,进程P1占据内存情况：,空闲页面链表,已修改页面链表,（7）若P1要读第1页,页面缓冲算法举例：,按照FIFO，淘汰第2块中的第2页，因为该页没修改过，所以将空闲块2插入空闲页面链表；从空闲页面链表中摘下第1块（其中有P1的第1页）分
14、配给P1。,进程P1占据内存情况：,空闲页面链表,已修改页面链表,页面缓冲算法举例：,（7）P1读1页，系统处理方式为：已修改页面链表：空闲页面链表：进程P1占据内存情况：,一、缺页率对有效访问时间的影响 设缺页率为P，则有效访问时间为：(1-P)*内存访问时间+P*缺页中断处理时间,4.9请求分页系统的性能分析,缺页中断处理时间,缺页中断服务时间；读入缺页所需时间；重新执行访存指令时间。,例：若某请求分页系统的平均缺页中断时间约为25ms，存储器的平均访问时间为100 ns，设缺页率为P，则有效访问时间为：（1p）0.1+p25000=0.1+24999.9p（微秒）如果希望在缺页时，仅使有
15、效访问时间延长不超过10%，则可计算出缺页率p 0.1+24999.9p 0.1(1+10%)则P（0.01/24999.9）=0.0000004,一、缺页率对有效访问时间的影响：,由此可知，要求在2500000次的访问中，才发生一次缺页，即请求分页式存储管理应保持非常低的缺页率，否则将使程序的执行速度受到严重影响。此外，提高磁盘I/O速度，对改善请求分页系统的性能至关重要。为此，应选用高速磁盘和高速磁盘接口。,二、抖动的基本概念：1.抖动的概念及产生的原因：全局置换策略 2.抖动的预防：（1）采取局部置换策略；（2）引入工作集概念：工作集就是进程在某段时间段里实际要访问的页面的集合。具体地说
16、，运行进程在时间t到t这个时间段内所访问的页面的集合称为该进程在时间t的工作集，变量称为工作集“窗口尺寸”（Windows Size）。,4.9请求分页系统的性能分析,二、抖动的基本概念：2.抖动的预防：（3）L=S原则：L：进程产生缺页的平均时间；S：系统进行缺页中断处理的平均时间。（4）挂起若干进程，降低多道程序度。,4.9请求分页系统的性能分析,4.10请求分段存储管理方式,以基本分段内存管理为基础，程序运行前，只需先调入部分分段，便启动执行。其它分段在需要时，通过缺段中断处理程序临时调入。1 请求分段中的硬件支持2 请求分段中的分段共享3 请求分段中的分段保护,4.10请求分段存储管理
17、方式,请求分段存储管理系统的示意图：,存储空间,作业空间,10K,0,12K,0,8K,0,20K,0,（MAIN）=0,状态,段表,基址,段长,段号,20K,0,30K,8K,1,90K,12K,2,150K,10K,3,200K,1,1,0,1,4.10请求分段存储管理方式,一.请求分段中的硬件支持1.段表机制,(1)存取方式：存取属性为只执行、只读或允许读/写(2)访问字段A：记录该段被访问的频繁程度(3)修改位M：该段在进入内存后是否被修改过(4)存在位P：指示本段是否已调入内存(5)增补位：表示本段在运行过程中，是否做过动态增长(6)外存始址：本段在外存中的起始地址，即起始盘块号,一
18、.请求分段中的硬件支持,2.缺段中断机构,段基址，存在位,在指令执行期间产生和处理中断信号一条指令在执行期间可能产生多次缺段中断,一.请求分段中的硬件支持,3.地址变换机构,返回,W段长？,修改访问位、修改位,形成访问主存地址(A)=(主存始址)+(位移量W),是,符合存取方式？,段S在主存？,分段越界中断处理,分段保护中断处理,缺段中断处理,是,是,否,否,否,访问SW,S 段表长度？,分段越界中断处理,否,是,4.9请求分段存储管理方式,二.分段共享:1.共享段表公用信息；私用信息共享进程计数count：记录要共享该段的进程数目存取控制字段：对一共享段，给不同进程不同权限段号：不同进程可以
19、调用不同段号去共享某共享段,二.分段共享,2.共享段的内存分配（1）共享段第一次被访问：为共享段分配内存，并装入；修改进程段表；修改共享段表：增加一个共享段表项。（2）共享段已在内存 修改进程段表；修改共享段表：增加一个该进程的私有信息3.共享段的回收,4.10 请求分段存储管理方式,三.分段保护 1.越界检查段表寄存器：段表始址、段表长度逻辑地址：段号；段内地址。比较：段号段表长度2.存取控制检查段表项：存取控制字段（只读、只执行、读/写）,段长段内地址,4.10 请求分段存储管理方式,三.分段保护3.环保护机构低编号的环具有高优先权。程序可以访问驻留在相同环或较低特权环中的数据；程序可以调
20、用驻留在相同环或较高特权环中的服务。,3.环保护机制,0级：内核,1级：系统调用,2级：共享库,3级：应用程序,数据访问：内访外,功能调用：外调内,作业：,P159：5，6，7，12，15，26补充作业：1.什么叫重定位？它有哪两种方式？这两种方式有什么区别？2.某系统采用动态分区分配方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K
21、、作业6释放60K，请分别画图表示出，使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实际使用情况.,3.请求分页管理系统中，假设某进程的页表内容如下表所示:页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用LRU置换算法和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列2362H、1565H、25A5H，请问：（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。（2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。,
