第8章 换入换出

操作系统OperatingSystem第8章换入换出Chapter10:SwapIn/Out内存管理视图cs:ip逻辑地址0x00345008线性地址内存操作系统段04G用户代码段用户数据段用户栈段地址空间物理地址0x7008对用户是透明的用户眼里的内存!cs:ip逻辑地址操作系统段04G用户代码段用户数据段用户栈段地址空间1个4GB(很大)的地址空间用户可随意使用该地址空间，就象单独拥有4G内存该地址空间就被称为“虚拟内存”这个地址空间怎么映射到物理内存，用户全然不知必须映射，否则不能用!虚拟内存的优点内存04G地址空间优点1:地址空间>物理内存用户可以编写比内存大的程序4G空间可以使用，简化编程优点2:部分程序放入物理内存内存中可以放更多进程，并发度好，效率高将需要的部分放入内存，有些用不到的部分从来不放入内存，内存利用率高如一些处理异常的代码!程序开始执行、响应时间等更快虚拟内存思想既有利于系统，又有利于用户如何实现虚拟内存!从段页式内存管理开始页框号保护5R1R/W3R/W7R基址长度保护段号0x40000x0800R00x48000x1400R/W10xF0000x1000R/W20x00000x3000R3段号+偏移(cs:ip)逻辑地址页号偏移偏移物理地址物理页号线性地址部分逻辑地址对应段表项，发现缺段后调入部分线性地址对应页表项，发现缺页后调入分页易于硬件实现、对用户透明，适合请求调入请求调页!磁盘页表物理内存虚拟内存中的页面映射关系部分线性地址(逻辑页)对应物理页，那其它页呢?磁盘页表物理内存请求调页过程当访问没有映射的线性地址时…load[addr]i页错误处理程序(1)(2)(3)(4)(5)(6)但完成这个过程很费时间(有时候一条指令会引起几次调页)!显然是一个很好理解的过程请求调页的性能分析分析的背景:又一个计算机基本特征!决定了请求调页是否可用RegistersDatapath处理器MainMemory(DRAM)1ns10msSpeed(ns):100ns100sGsSize(bytes):MsSecondaryStorage(Disk)存储器层次请求调页时的有效访问时间有效访问时间=(1-p)ma+p调页时间100(1-p)+10000000p=100+9999900p110p<0.000001缺页率(页错误率)应该很小:1/105为什么请求调页仍是可行的?分配给一个进程的物理页框数应该足够多!页面应该足够大!这又违背了分页和请求调页的原则，又需要折衷!如何设计这些参数?再从计算机的基本特征开始!

实践性很强的学科怎么学?内存地址访问频率物理内存90/10原则!90%的程序访问10%的地址!页面4K，调入一页后许多指令不出现页错误这些参数从实践中获得!

请求调页的具体实现细节(1):load[addr]，而addr没有映射到物理内存物理内存磁盘页表load[addr]i页错误处理程序(1)(2)(3)(4)(5)(6)根据addr查页表(MMU)，页表项的P位为0，引起缺页中断(pagefault)(2):

设置“缺页中断”即可(3):“缺页中断处理程序”需要读磁盘(4):

选一个空闲页框学过磁盘处理后自然就明白了!(5):

修改页表(6):

重新开始指令如何重新开始指令?在指令执行过程中出现页错误addr1,r2,r3mov+(sp),(r2)页错误分配页面从磁盘读入设置映射OS指令重执行显然这一切应该对用户透明!需要一点硬件支持Fault:epc=0xffdd0页错误处理程序jmp0xffdd00xffdcc:addr1,r2,r30xffdd0:ldr1,0(sp)如何选一个空闲页框?没有空闲页框怎么办?分配的页框数是有限的页面淘汰(置换)需要选择一页淘汰有多种淘汰选择。如果某页刚淘汰出去马上又要用…FIFO，最容易想到，怎么评价?有没有最优的淘汰方法，MIN最优淘汰方法能不能实现，能否借鉴思想，LRU再来学习几种经典方法，它可以用在许多需要淘汰(置换)的场合…FIFO页面置换淘汰算法:FIFO一实例:分配了3个页框(frame)，页面引用序列为ABCABDADBCBCBADCBABCBDADBACBA321Ref:Page:评价准则:缺页次数；本实例，FIFO导致7次缺页D换A不太合适!选A、B、C中最远将使用的MIN页面置换MIN算法:选最远将使用的页淘汰。是一种最优的方案，可以证明缺页数最小!继续上面的实例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本实例，MIN导致5次缺页可惜，MIN需要知道将来发生的事…怎么办?LRU页面置换用过去的历史预测将来。LRU算法:选最近最长一段时间没有使用的页淘汰(最近最少使用)。继续上面的实例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本实例，LRU也导致5次缺页LRU是公认的很好的页置换算法，怎么实现?和MIN完全一样!LRU的准确实现每页维护一个时间戳(timestamp)继续上面的实例:(3frame)ABCABDADBCBBCBDADBACBAtimestampA1BC0D001200123042304530选具有最小时间戳的页!453675367538793879108选A淘汰!711108每次地址访问都需要修改时间戳，需维护一个全局时钟(该时钟溢出怎么办?)，需要找到最小值

…这样的实现代价较大

几乎没人用LRU准确实现之页码栈维护一个页码栈继续上面的实例:(3frame)ABCABDADBCBBCBDADBACBA页码栈每次地址访问都需要修改栈(修改10次左右栈指针)…实现代价仍然较大

LRU准确实现用的少AABCABABCBCA选栈底页淘汰!DABABDDBABADCDBBDCLRU近似实现将时间计数变为是和否每个页加一个引用位(referencebit)每次访问一页时，硬件自动设置该位选择淘汰页：扫描该位，是1时清0，并继续扫描；是0时淘汰该页再给一次机会(SecondChanceReplacement)组织成循环队列较合适！R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=0SCR这一实现方法称为ClockAlgorithmClock算法实例继续上面的实例:(3frame)ABCABDADBCB**C********D*******C***B**A*BCBDADBACBA321Ref:Page:本实例，Clock算法也导致5次缺页Clock算法是公认的很好的近似LRU的算法引用位！扫描指针！Clock算法分析的改造如果缺页很少，会?R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1所有的R=1handscan一圈后淘汰当前页，将调入页插入hand位置，hand前移一位退化为FIFO!原因:记录了太长的历史信息…怎么办?定时清除R位…再来一个扫描指针!R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1用来清除R位，移动速度要快!用来选择淘汰页，移动速度慢!更像Clock吧!清除R位的hand如何定速度，若太快?又成了FIFO!来看一个实际例子Solaris下键入命令:vmstat-sR=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1free?>>14157550pagesexaminedbyclockdaemon>>13065972pagesfreedbyclockdaemon>>110revolutionsofclockhand#sinceboot!原理:

第2条指针不是在缺页时工作，而是定期执行，检查引用位，将为0的页释放到空闲链表中。使用freelist回收最近一段时间没引用指针扫描速度如何定?一个定时调度的内核任务继续这个实际例子设定值吗?在slowscan和fastscan之间调整系统负载并不固定…slowsacnfastsacn空闲内存比率lotsfreeminfree空闲内存比率高于lotsfree时，扫描速度设为slowscan,并往大调稳定在这个区间上!清除指针和扫描指针的距离:handspread参数R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1一个夹角scanrate=100,handspread=1000

两针间隔=10s两种置换策略Solaris换页daemon中的freelist使用freelist回收DBBCADAB全局置换局部置换想一想前面的例子!只能淘汰进程自己的页面可以淘汰别的进程的页面全局置换:实现简单但全局置换不能实现公平、保护:一个经过巧妙优化的程序里会出现大量goto，则…局部置换需要考虑的关键问题给进程分配多少页框(帧frame)分配的多，请求调页的意义就没了!一定要少?至少是多少?

可执行任意一条指令，如mov[a],[b]是不是就选该下界值?最坏情况需要6帧!来看一个实例:操作系统监视CPU使用率，发现CPU使用率太低时，向系统载入新进程。会发生什么?多道程序程度CPU利用率急剧下降CPU利用率急剧下降的原因系统内进程增多

每个进程的缺页率增大

缺页率增大到一定程度，进程总等待调页完成

CPU利用率降低进程进一步增多，缺页率更大…多道程序程度CPU利用率急剧下降此时:进程调入一页，需将一页淘汰出去，刚淘汰出去的页马上要需要调入，就这样……称这一现象为颠簸(thrashing)显然，防止的根本手段给进程分配足够多的帧问题时怎么确定进程需要多少帧才能不颠簸?工作集模型任何计算都需要一个模型!要确定进程所需的帧数该依靠什么信息呢?从请求调页的可行性开始!访问频率局部性现象!只要分配的帧空间能覆盖整个局部就不会出现太多的缺页!工作集模型就用来计算一个局部的宽度(帧数)工作集定义进程Pi工作集合WSi=在最近的时间内访问的页面集合，其中为工作集窗口一个例子:

定义为10个页引用数!10个页引用WSi的用法:(1)计算D=|WSi|;(2)如果D>m，则选择一个进程换出;(3)如果D<m，可以选一个进程换入。选择哪个进程换入、换出，中程调度工作集的计算根据定义，每次引用都重新计算WS，会很低效

该定为多少?太小盖不住一个局部，太大会包含多个局部。试试看?但系统有时并不敏感提出了基于页错误率的帧分配方案工作集大小定期扫描+定期计算(在定时中断中)是近似计算一种方案:每个页增加一个属性idletime()。扫描:如果访问位R为1，=0，R=0;否则+=CPU执行时间。计算WS：在WS中。UNIX,扫描周期:几秒.计算周期:几分钟.基于页错误率的帧分配页错误率(PFF)=页错误/指令执行条数

如果PFF>上限，增加分配帧数往往是PFF和WS互相配合如果没有空闲帧，则换出进程此种方法简单直接，在处理颠簸时常用。那WS呢?分配帧数PPF上限下限有趣的是，帧数越多，PPF并不一定下降但现代OS并不十分重视颠簸现象，因为CPU更快了，进程很快exit；内存更大了，局部的变化不大Belady异常来看一个例子!

引用序列1，2，3，4，1，2，5，1，2，3，4，5FIFO页置换13frame121234234134125125325349faults4frame112123123452345134512451234123452310faults什么样的页置换没有Belady异常看个模型!

引用序列1，2，3，4，1，2，5，1，2，3，4，5结论：栈式算法无Belady异常，LRU属于栈式算法!121321432114322143521431524321543321544321514325LRU栈实现m=3m=4m是分配的帧数特征:M(m,r)M(m+1,r)，如{5,2,1}{5,2,1,4}(m=3)满足这一特征的算法称为栈式算法!看看FIFO12323413412412312534m=312312341234123423451m=4不在一些技术预调页:

页可以不同自己的页错误而调入

进程创建(换入)时一次调入多个页(可由WS确定)页面尺寸:

该定为多少?受许多因素影响!减少碎片，页应该小程序结构:for(j..128){for(i..128){A[i][j]=0;}}//页大小128操作系统难吗?不难吗?难吗?不难吗?启动快，但可能有页用不着!页错误数降低页错误，页应大页大小碎片按行存储128*128faultsfor(i..128){for(j..128){A[i][j]=0;}}128faults整理一下前面的学习温故而知新虚拟内存的基本思想

将进程的一部分(不是全部)放进内存其他部分放在磁盘需要的时候调入:请求调页内存利用率高，程序编制容易，响应时间快…why?请求调页的基本思想

what?当MMU发现页不在内存时，中断CPUCPU处理此中断，找到一个空闲页框CPU将磁盘上的页读入到该页框如果没有空闲页框需要置换某页(LRU)how?一个实际系统的请求调页!Linux的请求调页从哪里开始这个故事?从缺页中断开始中断号名称说明10InvalidTSSCPU任务切换时发觉TSS无效12SegmentnotPresent描述符所指的段不存在14Pagefault页不在内存voidtrap_init(void){set_trap_gate(14,&page_fault);}#defineset_trap_gate(n,addr)\_set_gate(&idt[n],15,0,addr);dplLinux处理中断pagefault//在linux/mm/page.s中

.globl_page_faultxchgl%eax,(%esp)pushl%ecxpushl%edxpush%dspush%espush%fsmovl$0x10,%edxmov%dx,%dsmov%dx,%esmov%dx,%fsmovl%cr2,%edxpushl%edxpushl%eaxtestl$1,%eaxjne1fcall_do_no_pagejmp2f1:call_do_wp_page//保护2:add$8,%esppop%fspop%espop%dspop%edxpop%ecxpop%eaxiret测试标志P压入参数页错误线性地址取出错误码到eax置内核数据段选择符do_no_page//在linux/mm/memory.c中

voiddo_no_page(unsignedlongerror_code,unsignedlongaddress){intnr[4];unsignedlongtmp,page;intblock,i;address&=0xfffff000;//页面地址

tmp=address–cuurent->start_code;//页面对应逻辑地址

if(!current->executable||tmp>=current->end_data){

get_empty_page(address);return;}page=get_free_page();block=1+tmp/BLOCK_SIZE;for(i=0;i<4;block++,i++)nr[i]=bmap(current->executable,block);bread_page(page,current->executable->i_dev,nr);

不是代码和数据!指向可执行文件!需要等文件系统学完!do_no_page(续)voiddo_no_page(unsignedlongerror_code,unsignedlongaddress)...i=tmp+4096-current->end_data;tmp=page+4096;while(i-->0){tmp--;*(char*)tmp=0;}

put_page(page,address);//完成线性地址和物理地址的映射}

把超过end_data的数据清0//在linux/mm/memory.c中

voidget_empty_page(unsignedlongaddress){unsignedlongtmp=get_free_page();put_page(tmp,address;}put_page//在linux/mm/memory.c中unsignedlongput_page(unsignedlongpage,//物理地址

unsignedlongaddress){unsignedlongtmp，*page_table;page_table=(unsignedlong*)((address>>20)&ffc);if((*page_table)&1)page_table=(unsignedlong*)(0xfffff000&*page_table);else{tmp=get_free_page();*page_table=tmp|7;page_table=(unsignedlong*)tmp;}

page_table[(address>>12)&0x3ff]=page|7;returnpage;}页目录项_pg_dir=0do_wp_page//写时复制，进程创建//在linux/mm/memory.c中

voiddo_wp_page(xxerror_code,unsignedlongaddress){un_wp_page((unsignedlong*)(((address>>10)&0xffc)