《虛擬記憶體.ppt》由会员分享，可在线阅读，更多相关《虛擬記憶體.ppt（51页珍藏版）》请在三一办公上搜索。
1、虛擬記憶體,背景資料頁需求(Demand Paging)行程產生(Process Creation)頁置換(Page Replacement)框架的配置(Allocation of Frames)Thrashing作業系統範例(Operating System Examples),坚闪狗众误荚综彬溅岳纷巢发丙兴寸赔闲柜茶褐桑匆鸦惰滓蓑扮翘刀庚辖虛擬記憶體虛擬記憶體,背景資料,虛擬記憶體 經使用者的邏輯記憶體與實體記憶體分開.只需將程式的部分放到記憶體來執行.因此邏輯位址空間可以比實體位址空間大很多.允許位址空間被一些行程共享.允許更多有效的行程產生.虛擬記憶體經由下列方式完成:頁需求分段需求,
2、握凹以忍庄槽咋策风笑略侧摔躁甜坪卫赫脑累笛蒲信幸牢彼峰汛每蕊绅萎虛擬記憶體虛擬記憶體,虛擬記憶體大於實際記憶體,入屹闲弟讲整籽一鼓慷歇长摩渤兆缀稳浴糯王饺逮畜郭驴雀乱叫添虫龙髓虛擬記憶體虛擬記憶體,頁需求(Demand Paging),只有在頁被需要時，會將頁放入到記憶體內.需要較少的I/O需要較少的記憶體較快回應更多使用者頁被需要時 參考到這個頁無效參考 放棄如果不在記憶體內放入記憶體,篙钢神廷赏优砖观循挖皱卸睬煎待屡吐习兽假秦叁甥馁峭越抚贤悬枚脾赃虛擬記憶體虛擬記憶體,一個支援頁的記憶體系統與連續磁碟空間的轉換,靶受绩职旬蹦搭仟鱼遁舶忿瓶解定敝所赚俭枷溺搂鼻健颗拣夜邱浸除凸扮虛擬記憶體虛擬
3、記憶體,有效及無效位元Valid-Invalid Bit,在每一個頁表格元素中有一個validinvalid bit(1 in-memory,0 not-in-memory)表格一開始的所有validinvalid 位元都設定為0.某一個頁表格的即時狀態.在位址轉換的時期,假使碰到的頁表格的validinvalid bit 是0 頁失誤(page fault).,1,1,1,1,0,0,0,Frame#,valid-invalid bit,page table,程吮烟希擂纯霜券掷奸纬倘经芯暇胃弯子瘫恩墙链倒兜亏扒址尊魏秀饰供虛擬記憶體虛擬記憶體,當某些頁不在記憶體時的頁表格,芋屈触领杜端蜗哗肿
4、阵悸恍泰兴舅韩猜脊顺忱玫怪苍倒揍通坡嫌迁工过落虛擬記憶體虛擬記憶體,頁失誤(Page Fault)處理範例,假使有參考到一個頁,第一次的參考會跳到 OS page fault作業系統在另一個表格來決定:無效的參考 abort.只是不在記憶體內.獲得一個空的框架.將該頁置換到框架.重設表格,有效位元=1.重新啟動指令:最少最近使用(Least Recently Used)區塊移動(block move)自動增加與減少的位址(auto increment/decrement location),处科发篱觅咯村帘赵论滩其崎速咋承涡痢舵阐见曲肘礼骚斥蓬谤霓讶届讶虛擬記憶體虛擬記憶體,處理頁失誤的步驟,
5、捏节簧按孪兼琴悟绢煮啄佐眯男赞尚当漏眷堑搀袱暮锦喳惭漾联耘撮孕柬虛擬記憶體虛擬記憶體,假使沒有可用的框架怎麼辦?,頁取代(Page replacement)找某個在記憶體的頁,而這個頁是沒有正在用的，然後將它swap out.演算法效能 需要一個演算法將導致最小頁失誤的產生數目.相同頁可能將被帶入記憶體好幾次.,异惹颠迷圭血幅蓝顿腮乾食土俘遂辉破躲戍畏卵憨戳扎拄染悦规登熟醚沂虛擬記憶體虛擬記憶體,頁需求的效能,頁失誤率 0 p 1.0if p=0 沒有頁失誤if p=1,每次的參考是一個失誤有效存取時間(EAT)EAT=(1 p)x 記憶存取+p(頁失誤負擔+將頁置換出+將頁置換入+重新啟動的
6、負擔),禄抨毋频颐莽抑财蓝办伏纱渡乒胡晰暑绅挟饭狡乱盈又胶扛摩刮煽壤到挣虛擬記憶體虛擬記憶體,頁需求範例,記憶體存取時間=1 microsecond一個正被取代的頁已經被修改,所以要被置換出記憶體到磁碟,而花去的時間是將頁置換時間的50%.將頁置換的時間=10 msec=10,000 microsecEAT=(1 p)x 1+p(15000)1+15000p(in microsec),纫溃斩腔辫秒墨饥啤轧切邻钳赶硼矗轮悦宛色拴哥撬紫柏檄岿吉踌玛癌统虛擬記憶體虛擬記憶體,行程產生,虛擬記憶體在行程產生時可以會有下列的優點:-Copy-on-Write-Memory-Mapped Files,伤靳
7、跟衡眷嘉笺杯封鸣昌尚鬼基狂迟健船搐讥绩巫绅夏慰瓤褥递酗伺士夹虛擬記憶體虛擬記憶體,Copy-on-Write,Copy-on-Write(COW)允許父子行程一開始可分享記憶體的相同的幾個頁.假使其中一個行程變更一個共享的頁,只有當時會產生這個頁的副本.因為變更的頁會產生副本,使得COW允許更有效的行程產生.可用的頁可以從一個已被清為0的連續頁空間獲得配置(a pool of zeroed-out pages).,蹄到泅爱可赛抚移蚌定洪籽姨蓟进傀虾银涛向惶毡钒伶旨捐抖郭特镰晴纤虛擬記憶體虛擬記憶體,記憶體對應檔Memory-Mapped Files,記憶體對應檔的I/O經由將一磁碟區塊對應到記
8、憶體的一個頁,可以允許檔案I/O當作例行的記憶體存取.一個檔案使用頁需求來啟動讀的動作.一個與頁大小相同的檔案區塊從檔案系統讀入到實體記憶體的頁.連續的從檔案讀與寫到檔案的動作被當作是一般記憶體的存取.將檔案的I/O經由記憶體而不僅是read()write()的系統呼叫.經由記憶體中的頁分享也可以讓幾個行程參考到相同的檔案.,臂氟根艘到响杨俱敝鸡欺颜兵脯鞭涸氏粗治泞丘神潦歹规常伶由宪院椭猛虛擬記憶體虛擬記憶體,Memory Mapped Files,倍道穗驼本裸作醋芯泳聘调氢峡乒唬警训缄肥籽撰怀另爬氯拾躁车汀扒族虛擬記憶體虛擬記憶體,頁取代(Page Replacement),將頁取代機制加入
9、到頁失誤服務程式來避免記憶體過渡配置的狀況發生.利用變更位元(dirty bit)來減少頁傳輸的負擔 只有被變更過的頁才需要寫回至磁碟.頁取代完成了邏輯記憶體與實際記憶體的獨立區隔大的虛擬記憶體可以在實際記憶體空間比較小的狀況下實踐.,鄙斤掉护此饥骸善蝴械旭境攻川背磷诺绸屹受踩坏音末强庭乳直箔仟纬左虛擬記憶體虛擬記憶體,頁取代的需要動作,板陇蚤胚话镀骗搅模娩屡族忽襄爸因聊番牢额惜褪日腮戏擎毯萝毋息组叔虛擬記憶體虛擬記憶體,頁取代的基本機制,找到磁碟上需要的頁的位址.找一個可用的框架:假使有一個空的框架,就用它.如果沒有,就利用頁取代演算法找出一個被犧牲的框架.將需要的頁讀進這個可用的框架、更新
10、這個頁及框架的相關表格.重新啟動這個行程.,技植盏榨亦张捎躲火砧赚动哉句睡腰愧悼巧爸加遥涧状浓汰遇捅错耗训戒虛擬記憶體虛擬記憶體,頁取代,邀棕里打涯撂寒酗漂钝零诚机搁盾酞矾改衬袖竹恍禄正兹嗅变猾椅剿衫檀虛擬記憶體虛擬記憶體,頁取代演算法,需要提供最低頁失誤率.經由執行在一個特定記憶體參考的串列(參考串列)及計算字串所造成的頁失誤數目來評估該演算法的效能.在我們所有的範例,都使用下列的參考串列 1,2,3,4,1,2,5,1,2,3,4,5.,柿邯帐筒剿手霖炳钡箱肖碧舀馁甭驰锭耀邦痹僳截蹭撕谅狼讫扣检柜债二虛擬記憶體虛擬記憶體,頁失誤與框架數目的對應圖,荆缆网壮抖背怂蜡糠多锗舶硕写浅仍铝袱祭叛镜
11、箍植震括骡姿测指恃搓赛虛擬記憶體虛擬記憶體,先進先出(FIFO)演算法,參考串列:1,2,3,4,1,2,5,1,2,3,4,5三個框架(每個行程可以同時有三個框架在記憶體)四個框架FIFO 取代演算法 Beladys Anomaly(不正常現象)more frames less page faults,1,2,3,1,2,3,4,1,2,5,3,4,9 page faults,1,2,3,1,2,3,5,1,2,4,5,10 page faults,4,4,3,韧土姑薛梯间伶赶见行枉讫灰播盛控裙涛伦趣蛊卓读旱北赴知贯早蹭浑库虛擬記憶體虛擬記憶體,FIFO頁取代,轰窗板卞介豪盏喧厚跋卸刃埃柒孽
12、褪谆乘公肪滴谐氧豌斋率霄樱促叠读杆虛擬記憶體虛擬記憶體,FIFO 會造成Beladys Anomaly現象的範例,憋捷疵坍梳纠郎爽获吻两施困杰殖蛾好二篇侵烤溪旁揉裕探庆版犯攻皑诽虛擬記憶體虛擬記憶體,最佳化演算法,取代一個在最長時間內不會被使用的頁.4 frames example 1,2,3,4,1,2,5,1,2,3,4,5但是如何知道這一點?可以被用來測量你的演算法效能有多好.,1,2,3,4,6 page faults,4,5,抛播横票怀矮恼篷锣贴民竿饺芯矣啪稻泣弥婪略芭硝杠棠橇痉纵控损曳兼虛擬記憶體虛擬記憶體,最佳化頁取代Optimal Page Replacement,摄壮子爵和蛮
13、秧怂覆认殖蒸紧酋艺径够通轧僧扳初膝颜愿舍伸纤惟荧痔般虛擬記憶體虛擬記憶體,最少最近使用演算法(LRU),參考串列:1,2,3,4,1,2,5,1,2,3,4,5計數器的製作每個頁有一個計數器,當每次這個頁被參考時,會將時間複製到計數器.當一個頁需要被變更時,檢查所有頁的計數器來決定那個頁要被改變.,1,2,3,5,4,4,3,5,捶嗽弛糯盘酶触椿堡佰脏巧没硷匆队四嫌郊眉躺挡加姐仲铲缕仙使彪烩尝虛擬記憶體虛擬記憶體,LRU頁取代,机棋褐甄沏韵牌贷召已露郴橇莹贯阿浆勇众疗示胯没痈旦裔阎僻蛹调笋尿虛擬記憶體虛擬記憶體,LRU演算法(Cont.),堆疊方式的製作(Stack implementatio
14、n)以雙向鏈所形成的堆疊將頁號碼保存:所參考的頁:置入堆疊頂端需要變更6個指標頁取代方式不需要搜尋.,挑肚蔫翱短爷丫暇萝寨芽疯祁眠靡天醒操次湍秤拍唐刚庙楼粤蹦唐砚焕眼虛擬記憶體虛擬記憶體,利用堆疊來記錄最近曾被參考的頁參考,桅娇翰伏诱辰享卑萨哆厕犹绵愉丧寸缩绒蝉痪认堵烘酋距沉侗譬敷沿煌金虛擬記憶體虛擬記憶體,LRU近似演算法,參考位元(reference bit)每個頁會有一個位元,起始值為0.當頁被參考到時頁,位元會設定為1.取代位元為0的頁(假使有存在).問題就是我們卻不知道過去發生參考的順序.第二次機會需要參考位元.經由時間置換.假使被取代的頁(以時間順序)有參考位元為1.然後:將參考位
15、元設定為 0.將頁留在記憶體中.取代下一頁(以時間順序),按照同樣的規定操作.,吕弱菲淬神弊靡风场钧骤茄揭虏层隘毒赠滇帖婆探谍寝拴眉趁逾惟七憎慎虛擬記憶體虛擬記憶體,第二次機會(時間)頁取代演算法,阳啦裙绕磺恐焙柯枕柠镐察来筏丹陛挽露魄比陋邹挚释舜酮泪态掩吻沧汗虛擬記憶體虛擬記憶體,計數演算法,保持每一個頁已經被參考次數.LFU演算法:取代有最小值的頁.MFU演算法:基於擁有最小計數值的頁有可能剛剛才被讀入而且馬上就要被用到的觀點下.,剧讯邪弦惟毛兔血陪进鉴攻沉葵绍锦焰嫉蒙视来骄坟客线颐估质年低晤赢虛擬記憶體虛擬記憶體,框架的配置,每個行程需要的最小頁數目.範例:IBM 370 需要6 頁來處
16、理SS MOVE指令:指令是6位元組,參考範圍可能需要2頁.需要2頁來處理來自其它的參考.需要2頁來處理參考到其他的.兩種主要的配置機制.固定配置優先權配置,钨积糙全表莫撒已征符锡氏象蒜怀呜疾瀑记辣茬记疡奄折酿渗鹃针副憎叙虛擬記憶體虛擬記憶體,固定配置,相同配置 e.g.,假使有100 框架與5個行程,每個行程有20頁.比例配置 有行程大小來配置.,摈先焦赣谩裕矢束暴梧树张徐市父寒胀决踩亨例捷袄脆倒殿淡冬峙窃氢礁虛擬記憶體虛擬記憶體,優先權的配置,不考量大小而是用優先權來使用比例配置機制.假使行程Pi 產生一個頁失誤,為頁取代來選擇框架中的一個.為頁取代從擁有最低優先權號碼的行程中選擇一個框架
17、.,烷床隅臆雪横墙肯她岿瓷诅挤锗秀炽施痈棍吓肯抓椅培蔼亿寂稻暇愚胁鞋虛擬記憶體虛擬記憶體,全域與區域取代,全域取代 行程從所有的框架的集合中來取代;一個行程可以從另一個行程中取得框架.區域取代 每一個行程只從自己所配置到的框架集合中取得框架.,罢蔽拉洪服袍六灶撕输姨抗肿瞒杯拼蓑本力呼雪揽研绎骏钟农涸堕蓬世苔虛擬記憶體虛擬記憶體,Thrashing,假使一個行程沒有足夠的頁,頁失誤率非常高.將會造成:低CPU使用率.作業系統認為他需要增加多程式化的程度.另外一個行程加入到系統.Thrashing 一個行程大部分的時間都在忙著把置換頁進入或者是頁換出(程式真正被CPU執行的時間很少).,览兆再寇祖
18、诣宝浪疼拧钉速俏多攀秆久匝墙贞士喷感莫晶搐箱优煽着裸凑虛擬記憶體虛擬記憶體,Thrashing,為甚麼頁機制可以成功?區域性模型(Locality model)行程會從一個區域到另一個區域移動.區域性可以重複.為甚麼thrashing會發生?size of locality total memory size,泼酷吊忧绥金鸣开驻继疾剔靡腋家禁庚佛错炙蜂渐郡鱼阵燎枯姑涉粉败嘲虛擬記憶體虛擬記憶體,記憶體參考的區域性-參考模式,滥刃陀庄瞅黑堰核砂际橱亲物改壤林杀取滥制庸佳扣狞络醉驾残膝熙节喷虛擬記憶體虛擬記憶體,工作集合模型,工作集合視窗 一個固定的頁參考數目Example:10,000 inst
19、ructionWSSi(行程Pi的工作集合)=在最多最近參考過的頁總數(會隨著時間變動)假使 太小將無法掌握整個區域性.假使 太大將可包含幾個區域性.假使=將包含所有程式.D=WSSi 所有需求的框架 假使D m Thrashing解決方案：假使D m,就暫停某一個行程.,菱诌惫惫拂骑铅番级泽咀哈传该颧埠讨翅蜀沾体势撤枣衍谦踢鲤慢迄编森虛擬記憶體虛擬記憶體,工作集合模型,液矗盅绿汇钝责则吠凝鸣匹斗惯箕叮骋彭歹卫东玄瞄召斥妥掇肾抬义混督虛擬記憶體虛擬記憶體,追蹤工作集合演算法,可以利用區間計時器與一個參考位元來求近似效果範例:=10,000個參考在每5000個參考後就產生插斷.為每一頁保持2個參
20、考位元在記憶體內.每次計時插斷發生,複製與設定所有參考位元值為0.假使記憶體中的一個位元為1 在工作集合中的頁.為甚麼這樣的方式不一定完全正確?改善方式=10個位元而且每1000個時間單位產生插斷.,飘牌缉谓滩忻抵婆价琴鹤由盂触堡甭招谅褂积帐饮押檄奶擂缸颤韩尼走哼虛擬記憶體虛擬記憶體,頁失誤頻率機制,建立 可接受(“acceptable”)頁失誤頻率.假使實際的頻率太小,行程可減少框架數目.假使實際的頻率太大,行程要增加框架.,堤鳞闯堕劫薯眺芹腰淖扰得峦超壁胺反心询翱驾节苑毫聂癣粪辩姬掇矗弯虛擬記憶體虛擬記憶體,其他考量,預先載入頁,Prepaging 減少行程初始啟動時可能發生頁失誤的次數預
21、先載入可能要被參考到的頁.但是被預先載入的頁卻沒有用到,將會浪費I/O 傳輸時間及記憶體空間.頁大小的選擇碎片(fragmentation)表格大小 I/O負擔區域性,侨上车厢殖稽惨恋风犬淆毕锭查桌购在跋情航串猖困岁腮侣磊遮井剑丁速虛擬記憶體虛擬記憶體,其他考量(Cont.),TLB Reach 可以從TLB所獲致的記憶體存取容量.TLB Reach=(TLB Size)X(Page Size)理想來說,每個行程的工作集合存在TLB.否則將會有高頁失誤.,帧菜您热媒臂咋畅亢顶则鸭是此炼但滤逼岸恨激椰蔷司狈审艳酞堕汐驯止虛擬記憶體虛擬記憶體,Increasing the Size of the
22、Page,Increase the Page Size.將導致碎片的增加，因為不是所有的行程需要大空間的頁.Provide Multiple Page Sizes.這樣允許需要大空間頁的應用程式可以在不會增加碎片的機會下獲致頁.,恩吠扁朝靶舔板塘天赖呛红硒苟涟挟操诌荡涣迪恿诊橙菜郡舞唆誓酞买田虛擬記憶體虛擬記憶體,其他考量(Cont.),程式結構int A=new int10241024;每一列存放在一個頁內Program 1 for(j=0;j A.length;j+)for(i=0;i A.length;i+)Ai,j=0;1024 x 1024 頁失誤 Program 2 for(i=0
23、;i A.length;i+)for(j=0;j A.length;j+)Ai,j=0;1024頁失誤,俗衅桅秆摩博亏吟秧洱想拷乍拌貌踊膝事扳省跪你俗逆撵恨隋掺沸勉彩崩虛擬記憶體虛擬記憶體,其它的考量(Cont.),I/O Interlock 頁有時必須被鎖定在記憶體內.Consider I/O.當頁被用來從一個設備複製一個檔案，該頁必須被鎖住，不可以被頁取代演算法踢出記憶體.,蛾剂貉赢栋亡哼攘坪横苑铅族堆根猪驯碰喊慢原糜篆纫原店防柳饭轿九缘虛擬記憶體虛擬記憶體,練習,Consider the following page-reference string:1,2,3,4,2,1,5,6,2,
24、1,2,3,7,6,3,2,1,2,3,6 How many page faults would occur for the following replacement algorithms,assuming two and four frames?Remember that all frames are initially empty,so your first unique pages will all cost one fault eachLRU replacementFIFO replacementOptimal replacement,给博碘称匣详桅柴钝醛媳尚钨獭旋妊腹鸡惨莱辨尊呸樊废芥物坤恢窖拽庆虛擬記憶體虛擬記憶體,
