哈工大张英涛操作系统视频对应课件31_41(全)

操作系统第31讲主讲人：张英涛哈尔滨工业大学远程教育课程分页请求系统在分页系统的基础上、增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页(而非全部程序)的用户程序和数据，便可启动运行。再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上、置换时以页面为单位。分页请求系统硬件支持[1]请求分页的页表机制[2]缺页中断机构[3]地址变换机构某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号031721138则逻辑地址0A5C(H)所对应的物理地址是什么？0A5C(H)：00001010010111002查表得：11001011拼接得：00101110010111002E5C(H)请求分段系统在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。它允许只装人若干段(而非所有的段)的用户程序和数据，即可启动运行。再通过调段功能和段的置换功能，将暂不运行的段调出，同时调入即将运行的段，置换是以段为单位进行的。请求分段的硬件支持（1）请求分段的段表机制。（2）缺段中断机制。（3）地址变换机制。虚拟存储器特征1．多次性2．对换性3．虚拟性请求分页存储管理方式请求分页中的硬件支持内存分配策略和分配算法调页策略页表机制基本作用是将逻辑地址变换为物理地址，在页表中再增加若干项，供换进换出时参考。状态位P：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。修改位M：该页调入内存后是否被修改过外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考缺页中断机构请求分页系统中每当所要访问的页面不在内存时，便要产生缺页中断、请求将所缺之页调人内存。与一般中断的区别：（1）在指令执行期间产生和处理中断信号。（2）一条指令在执行期间，可能产生多次缺页中断。内存分配的三个问题最小物理块数物理块的分配策略物理块的分配算法最小物理块数能保证进程正常运行所需的最少物理块数。若系统为进程所分配的物理块数少于此值时进程将无法运行。最少物理块数与计算机的硬件结构有关．取决于指令的格式、功能和寻址方式。物理块的分配策略1）固定分配局部置换2）可变分配全局置换3）可变分配局部置换固定分配局部置换为每个进程分配一固定页数的内存空间．在整个远行期间都不改变。如果缺页．则只能从该进程的页面中选出一页换出，再调入一页。困难：应为每个进程分配多少个面的内存难以确定，若太少会频繁地出现缺页中断降低吞吐量；太多，又使内存中进程数减少．进而可能造成CPU或其它资源空闲，而且进程对换时会花费更多的时间。可变分配全局置换先为每个进程分配一定数目的物理块。os保持一个空闲物理块队列。缺页时．系统从空闲物理块队列中，取出一个物理块分配给该进程．并将欲调入的缺页装入其中。当空闲物理块队列空时从内存中选择一页调出。最易实现可变分配局部置换基于进程的类型或程序员的要求．为每个进程分配一定数目的物理块。缺页时从该进程的页面中选出一页换出。如果进程频繁地发生缺页中断，则再为该进程分配附加的物理块。若一个进程的缺页率特别低，则可适当减少该进程的物理块．谢谢收看操作系统第31讲哈尔滨工业大学张英涛操作系统第32讲主讲人：张英涛哈尔滨工业大学远程教育课程物理块分配算法平均分配算法按比例分配算法考虑优先权的分配算法平均分配算法将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配物理块的算法。如果系统中共有N个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：S=∑Sii=1n假定系统中可用的物理块总数为M，则每个进程所能分到的物理块数为B，将有bi=Si/S*mbi应该取整，它必须大于最小物理块数。考虑优先权的分配算法物理块分成两部分：一部分按比例地分配个进程；另一部分根据各进程的优先权，适当地增加其相应份额后，分配各进程。有的系统可能是完全按优先权分配物理块。调页策略何时调入页面从何处调入页面页面调入过程调页时机1）预调页策略将那些预计在不久之后便会被访问的页面，预先调入内存。主要应用于进程首次调入2）请求调页策略运行中要访问某程序和数据时，若其页面不再内存，立即提出请求，os调入。从何处调入页面可分成三种情况：（1）有足够对换区空间。可全部从对换区调入所需页面。因此进程运行前，便将与该进程有关的文件，从文件区拷贝到对换区。（2）无足够对换区空间。不会被修改的文件从文件区调入；会被修改的文件从对换区调入。（3）UNIX方式。未运行过的页面，从文件区调入。运行过被换出的页面从对换区调入。页面调入过程程序发出缺页中断，中断处理程序保留cpu环境，转入缺页中断处理程序。查页表．求该页的外存物理块号。如果内存未满，则调入内存修改页表。如果内存已满，则按照某种置换算法．从内存中选出一页换出；如果此页已被修改．则必须将它重新写回磁盘。将缺页调入内存．并修改相应页表项，将其存在位置为1，再将此页表项写入快表中。页面置换算法进程访问的页面不在内存而内存巳无空闲空间时，系统必须从内存中调出一页送磁盘的对换区中。把选择换出页面的算法称为页面置换算法应将那些以后不再会访问的页面或在较长时间内不会再访问的页面调出。抖动刚被换出的页很快又被访问，需重新调入，又需再选一页调出，如此频繁地更换页面的现象称为抖动．抖动导致进程在运行中，把大部分时间花费在页面置换上。最佳置换算法选择被淘汰页是永不使用的、或者是在最长时间内不再被访问的页面。采用最佳置换算法可保证获得最低的缺页率。但由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的。可利用该算法去评价其它算法。假定某进程有8个页面，系统为分配了三个物理块．并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1使用最佳置换算法发生几次页面置换？701701203042303212017012107220001117012030423032120170172220000111370120304230321201701722220000011133701203042303212017017222220000041113337012030423032120170172222220000044111333370120304230321201701722222220000044411133333701203042303212017017222222220000044401113333337012030423032120170172222222222200000444000011133333333170120304230321201701722222222222222000004440000000111333333331111701203042303212017017222222222222227000004440000000011133333333111117012030423032120170172222222222222277700000444000000000011133333333111111170120304230321201701最佳置换算法发生6次页面置换谢谢收看操作系统第32讲哈尔滨工业大学张英涛操作系统第33讲主讲人：张英涛哈尔滨工业大学远程教育课程先进先出页面置换算法淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单假定某进程有8个页面，系统为分配了三个物理块．并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1使用先进先出页面置换算法发生几次页面置换？7017012030423032120170121072200011170120304230321201701722200031111701203042303212017017222200033111107012030423032120170172222400033311110070120304230321201701722224400033321111000701203042303212017017222244400033322111100037012030423032120170172222444000000077700033322222111110011110003333322222170120304230321201701发生11次页面置换最近最久未使用置换算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T，当须淘汰一个页面时，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。假定某进程有8个页面，系统为分配了三个物理块．并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1使用最近最久未使用算法发生几次页面置换？70170120304230321201701210722000111701203042303212017017222000011137012030423032120170172222000001113370120304230321201701722224000000111333701203042303212017017222244000000011133327012030423032120170172222444000111111100000003333330000011133322222222277770120304230321201701发生8次页面置换每页设置一位访问位。再将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置1。淘汰时检查其访问位，如果是0就换出；若为1则重新将它复0。再按FIFO算法检查下个页面。到队列中的最后—个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。又称为最近未用算法。简单CLOCK算法最少使用置换算法为每个页面设置一个移位寄存器，用来记录该页面被访问的频率。选择在最近时期使用最少的页面作为淘汰页。72222443333333177100000000000000000011133322222122222270120304230321201701发生9次页面置换页面缓冲算法采用可变分配和局部置换方式如果页面末被修改，就将它直接放入空闲链表；否则，放入已修改页面的链表中。页面在内存并不做物理移动而只是将页表中的表项移到链表之中。谢谢收看操作系统第33讲哈尔滨工业大学张英涛操作系统第34讲主讲人：张英涛哈尔滨工业大学远程教育课程请求分段存储管理请求分段中的硬件支持分段的共享与保护请求分段中的硬件支持段表机制缺段中断机制地址变换机制段表段名段长段的基址存取方式访问字段修改位存在位增补位外存始址存取方式。表示本段属性：只读、只执行、允许读/写访问字段A。访问频率修改位M。用于表示该页在进入内存后，是否被修改过，供置换页面时参考。存在位P。指示本段是否已调入内存，供程序访问时参考。增补位。特有的字段，用于本段在运行过程中，是否做过动态增长。外存始值。本段在外存中的起始地址，即起始盘块号。缺段中断处理过程请求分段地址变换过程共享段表（1）共享进程计数COUNT。（2）存取控制字段。对于一个共享段，应给不同的进程以下不同的存取权限。（3）段号。对于一个共享段