存儲(chǔ)管理市公開(kāi)課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

第四章存放器管理引言4.1程序裝入和鏈接4.2連續(xù)分配方式4.3基本分頁(yè)存放管理方式4.4基本分段存放管理方式4.5虛擬存放器基本概念4.6請(qǐng)求分頁(yè)存放管理方式4.7頁(yè)面置換算法4.8請(qǐng)求分段存放管理方式存儲(chǔ)管理第1頁(yè)存放組織存放器功效是保留數(shù)據(jù)，存放器發(fā)展方向是高速、大容量和小體積。內(nèi)存在訪問(wèn)速度方面發(fā)展：DRAM、SDRAM、DDR、DRDRAM、DDR2、XDR、SRAM等；硬盤技術(shù)在大容量方面發(fā)展：接口標(biāo)準(zhǔn)、存放密度等；存放組織是指在存放技術(shù)和CPU尋址技術(shù)許可范圍內(nèi)組織合理存放結(jié)構(gòu)。其依據(jù)是訪問(wèn)速度匹配關(guān)系、容量要求和價(jià)格。“存放器-內(nèi)存-外存”結(jié)構(gòu)“存放器-緩存-內(nèi)存-外存”結(jié)構(gòu)；存儲(chǔ)管理第2頁(yè)存放層次結(jié)構(gòu)快速緩存：SRAM內(nèi)存：DRAM,SDRAM,DDR,DRDRAM、DDR2、XDR等；外存：軟盤、硬盤、光盤、磁帶等；微機(jī)中存放層次組織：訪問(wèn)速度越慢，容量越大，價(jià)格越廉價(jià)；最正確狀態(tài)應(yīng)是各層次存放器都處于均衡繁忙狀態(tài)；存儲(chǔ)管理第3頁(yè)存放管理功效存放分配和回收：分配和回收算法及對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)。地址變換：可執(zhí)行文件生成中鏈接技術(shù)程序加載(裝入)時(shí)重定位技術(shù)進(jìn)程運(yùn)行時(shí)硬件和軟件地址變換技術(shù)和機(jī)構(gòu)存放共享和保護(hù)：代碼和數(shù)據(jù)共享地址空間訪問(wèn)權(quán)限（讀、寫、執(zhí)行）存放器擴(kuò)充：存儲(chǔ)管理第4頁(yè)重定位：實(shí)現(xiàn)邏輯地址（相對(duì)地址）到物理地址（絕對(duì)地址）映射。邏輯地址：應(yīng)用程序經(jīng)編譯后形成目標(biāo)程序，再經(jīng)過(guò)鏈接后形成可裝入程序，這些程序地址都是從0開(kāi)始，程序中其它地址都是相對(duì)于起始地址計(jì)算，這些地址為相對(duì)地址。物理地址：主存中一系列存放信息物理單元地址。重定位概念存儲(chǔ)管理第5頁(yè)4.1程序裝入和鏈接編輯―――編譯―――鏈接―――裝入―――運(yùn)行存儲(chǔ)管理第6頁(yè)4.1.1程序裝入1、絕對(duì)裝入：編譯后，裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地址），裝入時(shí)不再作地址重定位。絕對(duì)地址產(chǎn)生：（1）由編譯器完成，（2）由程序員編程完成。對(duì)（1）而言，編程用符號(hào)地址。2、可重定位裝入；靜態(tài)重定位：地址轉(zhuǎn)換在裝入時(shí)一次完成，由軟件實(shí)現(xiàn)（重定位裝入程序完成）。缺點(diǎn)：不允許程序在運(yùn)行中在內(nèi)存中移動(dòng)位置。存儲(chǔ)管理第7頁(yè)0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作業(yè)地址空間內(nèi)存空間圖4-2存儲(chǔ)管理第8頁(yè)3.動(dòng)態(tài)運(yùn)行時(shí)裝入在裝入后不能移動(dòng)，該情況普通在執(zhí)行時(shí)才完成相對(duì)——絕對(duì)地址轉(zhuǎn)換且有硬件支持,能確保進(jìn)程可移動(dòng)性。存儲(chǔ)管理第9頁(yè)4.1.2程序鏈接1、靜態(tài)鏈接a．對(duì)相對(duì)地址修改b．變換外部調(diào)用符號(hào)2、裝入時(shí)動(dòng)態(tài)鏈接a.便于修改和更新b.便于實(shí)現(xiàn)對(duì)目標(biāo)模塊共享3、運(yùn)行時(shí)動(dòng)態(tài)鏈接存儲(chǔ)管理第10頁(yè)模塊ACALLB;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標(biāo)模塊模塊AJSRL;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊存儲(chǔ)管理第11頁(yè)4.2連續(xù)分配方式單一連續(xù)分配用于單用戶，單任務(wù)中分區(qū)式分配固定式可變式可重定位分區(qū)分配存儲(chǔ)管理第12頁(yè)4.2.1單一連續(xù)分區(qū)內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡(jiǎn)單，適合用于單用戶、單任務(wù)OS。優(yōu)點(diǎn)：易于管理。缺點(diǎn)：對(duì)要求內(nèi)存空間少程序，造成內(nèi)存浪費(fèi)；程序全部裝入，極少使用程序部分也占用內(nèi)存。存儲(chǔ)管理第13頁(yè)4.2.2固定分區(qū)特點(diǎn)：有n個(gè)分區(qū)，則可同時(shí)裝入n個(gè)作業(yè)/任務(wù)。一、分區(qū)大?。合嗟?不相等：不相等利用率更高。二、內(nèi)存分配：數(shù)據(jù)結(jié)構(gòu)將分區(qū)按大小排序，并將其地址、分配標(biāo)識(shí)作統(tǒng)計(jì)例：dosMCB三、特點(diǎn)：簡(jiǎn)單，有碎片（內(nèi)零頭）存儲(chǔ)管理第14頁(yè)分區(qū)說(shuō)明表分區(qū)號(hào)大?。↘)起址（K）狀態(tài)11220已分配23232已分配36464已分配4128128已分配存儲(chǔ)管理第15頁(yè)操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K~~~~分配情況存儲(chǔ)管理第16頁(yè)4.2.3可變式分區(qū)一、數(shù)據(jù)結(jié)構(gòu)1．空閑分區(qū)表2．空閑分區(qū)鏈前向指針N個(gè)字節(jié)可用后向指針N+2N+20（分配標(biāo)識(shí)）0存儲(chǔ)管理第17頁(yè)二、分配算法1．首次適應(yīng)算法FF。要求：分區(qū)按低址――高址鏈接特點(diǎn)：找到第一個(gè)大小滿足分區(qū)，劃分。有外零頭，低址內(nèi)存使用頻繁。2．循環(huán)首次適應(yīng)算法。從1中上次找到空閑分區(qū)下一個(gè)開(kāi)始查找。特點(diǎn)：空閑分區(qū)分布均勻，提升了查找速度；缺乏大空閑分區(qū)。3．最正確適應(yīng)算法分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。存儲(chǔ)管理第18頁(yè)三、分區(qū)分配分配算法存儲(chǔ)管理第19頁(yè)F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時(shí)情況回收：（1）上鄰空閑區(qū)：合并，改大小（2）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項(xiàng)。存儲(chǔ)管理第20頁(yè)例：在計(jì)算機(jī)系統(tǒng)中,按地址排列內(nèi)存中空閑區(qū)大小是:10K,4K,20K,18K,7K,9K,12K,15K,對(duì)于連續(xù)段請(qǐng)求:12K,10K,9K.使用循環(huán)適應(yīng)算法和最正確適應(yīng)算法將找出哪些空閑區(qū)?解：循環(huán)適應(yīng)算法：20K,18K,9K最正確適應(yīng)算法：12K,10K,9K存儲(chǔ)管理第21頁(yè)4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位引入連續(xù)式分配中，總量大于作業(yè)大小多個(gè)小分區(qū)不能容納作業(yè)。緊湊經(jīng)過(guò)作業(yè)移動(dòng)將原來(lái)分散小分區(qū)拼接成一個(gè)大分區(qū)。作業(yè)移動(dòng)需重定位。是動(dòng)態(tài)（因作業(yè)已經(jīng)裝入）存儲(chǔ)管理第22頁(yè)緊湊存儲(chǔ)管理第23頁(yè)2、動(dòng)態(tài)重定位實(shí)現(xiàn)load1,2500365load1,25003650100250050002500100001000010100+1250015000作業(yè)J處理機(jī)一側(cè)存放器一側(cè)重定位存放器相對(duì)地址存儲(chǔ)管理第24頁(yè)圖4.10動(dòng)態(tài)分區(qū)分配算法存儲(chǔ)管理第25頁(yè)4.2.5對(duì)換1對(duì)換引入將阻塞進(jìn)程，暫時(shí)不用程序，數(shù)據(jù)換出。將具備運(yùn)行條件進(jìn)程換入。類型：整體對(duì)換：進(jìn)程對(duì)換，處理內(nèi)存擔(dān)心部分對(duì)換：頁(yè)面對(duì)換/分段對(duì)換：提供虛存支持2對(duì)換空間管理外存對(duì)換區(qū)比文件區(qū)側(cè)重于對(duì)換速度。所以，對(duì)換區(qū)普通采取連續(xù)分配。采取數(shù)據(jù)結(jié)構(gòu)和分配回收類似于可改變分區(qū)分配。存儲(chǔ)管理第26頁(yè)3換出與換入換出1．選出被換出進(jìn)程： 原因：優(yōu)先級(jí)，駐留時(shí)間，進(jìn)程狀態(tài)2．換出過(guò)程：對(duì)于共享段：計(jì)數(shù)減1，是0則換出，不然不換修改PCB和MCB（或內(nèi)存分配表）換入：1．選擇換入進(jìn)程：優(yōu)先級(jí)，換出時(shí)間等。2．申請(qǐng)內(nèi)存。3．換入存儲(chǔ)管理第27頁(yè)4.3基本分頁(yè)存放管理連續(xù)分配引發(fā):碎片碎片問(wèn)題處理：緊湊方式消耗系統(tǒng)開(kāi)銷。離散分配分頁(yè)、分段、段頁(yè)存儲(chǔ)管理第28頁(yè)1.頁(yè)面頁(yè)面和物理塊：邏輯空間和內(nèi)存空間頁(yè)面大小頁(yè)太大，頁(yè)內(nèi)碎片大。頁(yè)太小：頁(yè)表可能很長(zhǎng)，換入/出效率低2.地址結(jié)構(gòu)31 1211 0邏輯地址A；頁(yè)大小L；頁(yè)內(nèi)偏移d 4.3.1頁(yè)面與頁(yè)表頁(yè)號(hào)P位移W存儲(chǔ)管理第29頁(yè)例：L=1000B，則第0頁(yè)對(duì)應(yīng)0-999，第1頁(yè)對(duì)應(yīng)1000-1999。設(shè)A=3456，則P=INT[3456/1000]=3，d=[3456]mod1000=456故A=3456→（3，456）

普通來(lái)說(shuō)，頁(yè)面尺寸應(yīng)該是2冪。這么優(yōu)點(diǎn)是能夠省去除法，由硬件自動(dòng)把地址場(chǎng)中數(shù)拆成兩部分來(lái)決定對(duì)應(yīng)頁(yè)號(hào)和頁(yè)內(nèi)地址。例：頁(yè)大小為1KB，則邏輯地址4101頁(yè)號(hào)、頁(yè)內(nèi)地址可這么定：1K=1024=210(頁(yè)內(nèi)地址位數(shù)為10)4101=212+22+20，邏輯地址字以下：0001000000000101頁(yè)號(hào)頁(yè)內(nèi)地址故A=4101→（4，5）存儲(chǔ)管理第30頁(yè)3.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)021326384950123456789用戶程序頁(yè)表頁(yè)號(hào)塊號(hào)內(nèi)存存儲(chǔ)管理第31頁(yè)4.2地址變換機(jī)構(gòu)基本任務(wù)：邏輯地址——物理地址映射。

頁(yè)號(hào)→塊號(hào)經(jīng)過(guò)頁(yè)表來(lái)完成頁(yè)內(nèi)地址→塊內(nèi)地址無(wú)需轉(zhuǎn)換一、基當(dāng)?shù)刂纷儞Q機(jī)構(gòu)： 越界保護(hù)每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址裝入頁(yè)表存放器。存儲(chǔ)管理第32頁(yè)存儲(chǔ)管理第33頁(yè)

需要考慮問(wèn)題：頁(yè)表放在哪里？整個(gè)系統(tǒng)頁(yè)表空間有多大？直接映像分頁(yè)系統(tǒng)對(duì)系統(tǒng)效能不利影響？（影響執(zhí)行速度，因?yàn)镃PU最少要訪問(wèn)兩次主存才能存取到所要數(shù)據(jù)）

基本地址變換機(jī)構(gòu)①頁(yè)表駐留在內(nèi)存中。②系統(tǒng)中設(shè)置一個(gè)頁(yè)表存放器存放頁(yè)表在內(nèi)存中始址和頁(yè)表長(zhǎng)度。③缺點(diǎn)：兩次訪問(wèn)主存，速度降低近1/2存儲(chǔ)管理第34頁(yè)2.含有快表地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。（1）訪頁(yè)表（2）得到絕對(duì)地址內(nèi)容有快表，速度提升?？毂碣F，不能太多。存儲(chǔ)管理第35頁(yè)2.含有快表地址變換機(jī)構(gòu)存儲(chǔ)管理第36頁(yè)

例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：①假如對(duì)主存一次存取需要1.5μs,試問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)存取時(shí)間是多少?②假如系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁(yè)表項(xiàng)在快表中時(shí),其查找時(shí)間忽略為0,試問(wèn)此時(shí)存取時(shí)間是多少?存儲(chǔ)管理第37頁(yè)答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：一次是訪問(wèn)頁(yè)表，確定所存取頁(yè)面物理地址（稱為定位）。第二次才依據(jù)該地址存取頁(yè)面數(shù)據(jù)?！鲰?yè)表在主存存取訪問(wèn)時(shí)間=1.5*2=3(μs)■增加緊表后存取訪問(wèn)時(shí)間=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)存儲(chǔ)管理第38頁(yè)4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不一樣頁(yè)塊中。建一“外部頁(yè)表”來(lái)管理這些離散頁(yè)表塊。相當(dāng)于單級(jí)頁(yè)表中頁(yè)表存放器，普通應(yīng)常駐內(nèi)存。每項(xiàng)統(tǒng)計(jì)頁(yè)表始址，且增加存在位。64位機(jī)器頁(yè)表普通>3級(jí)，最外層頁(yè)表常駐。存儲(chǔ)管理第39頁(yè)存儲(chǔ)管理第40頁(yè)存儲(chǔ)管理第41頁(yè)1.某系統(tǒng)采取頁(yè)式存放管理策略，擁有邏輯空間32頁(yè)，每頁(yè)2K，擁有物理空間1M。（1）寫出邏輯地址格式。（2）若不考慮訪問(wèn)權(quán)限等，進(jìn)程頁(yè)表有多少項(xiàng)？每項(xiàng)最少有多少位？（3）假如物理空間降低二分之一，頁(yè)表結(jié)構(gòu)應(yīng)對(duì)應(yīng)作怎樣改變？2.已知某分頁(yè)系統(tǒng)，主存容量為64K，頁(yè)面大小為1K，對(duì)一個(gè)4頁(yè)大作業(yè)，其0、1、2、3頁(yè)分別被分配到主存2、4、6、7塊中。（1）將十進(jìn)制邏輯地址1023、2500、3500、4500轉(zhuǎn)換成物理地址。（2）以十進(jìn)制邏輯地址1023為例畫出地址變換過(guò)程圖。練習(xí)：存儲(chǔ)管理第42頁(yè)1.(1)系統(tǒng)擁有邏輯地址空間32頁(yè)，則邏輯地址中頁(yè)號(hào)需用5位描述；每頁(yè)2K，則頁(yè)內(nèi)地址用11位描述。（2）進(jìn)程頁(yè)表項(xiàng)數(shù)為32，另外頁(yè)表項(xiàng)中只給出頁(yè)所對(duì)應(yīng)物理塊號(hào)，1M物理空間可分為29個(gè)內(nèi)存塊，故每個(gè)頁(yè)表項(xiàng)最少有9位。（3）假如物理空間降低二分之一，則頁(yè)表中頁(yè)表項(xiàng)數(shù)不變，每項(xiàng)長(zhǎng)度可降低1位。存儲(chǔ)管理第43頁(yè)2.(1)邏輯地址1023：1023/1024，得頁(yè)號(hào)0，頁(yè)內(nèi)地址1023，查頁(yè)表對(duì)應(yīng)塊號(hào)2，故物理地址為2*1024+1023=3071邏輯地址2500：2500/1024，得頁(yè)號(hào)2，頁(yè)內(nèi)地址452，查頁(yè)表對(duì)應(yīng)塊號(hào)6，故物理地址為6*1024+452=6596邏輯地址3500：3500/1024，得頁(yè)號(hào)3，頁(yè)內(nèi)地址428，查頁(yè)表對(duì)應(yīng)塊號(hào)7，故物理地址為7*1024+428=7596邏輯地址4500：4500/1024，得頁(yè)號(hào)4，頁(yè)內(nèi)地址404，因頁(yè)號(hào)大于頁(yè)表長(zhǎng)度產(chǎn)生越界中止。存儲(chǔ)管理第44頁(yè)4.4基本分段存放管理4.4.1引入

每個(gè)段可有其邏輯意義及功效，使得便于（1）方便編程；（2）分段共享；（3）分段保護(hù)；（4）動(dòng)態(tài)鏈接；（5）動(dòng)態(tài)增加；（如數(shù)據(jù)段增加）存儲(chǔ)管理第45頁(yè)4.4.2分段系統(tǒng)基本原理

分段基本思想：按程序邏輯結(jié)構(gòu)，將程序地址空間劃分為若干段，各段大小可不相同。在進(jìn)行存放分配時(shí)，以段為單位，這些段在內(nèi)存中能夠不相鄰接。分段地址中地址含有以下結(jié)構(gòu)：段號(hào)段內(nèi)地址31161502.段表

存儲(chǔ)管理第46頁(yè)圖4-16利用段表實(shí)現(xiàn)地址映射存儲(chǔ)管理第47頁(yè)圖4-17分段系統(tǒng)地址變換過(guò)程3.地址變換機(jī)構(gòu)

存儲(chǔ)管理第48頁(yè)4.分頁(yè)和分段主要區(qū)分

（1）頁(yè)是信息物理單位，段是邏輯單位（2）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）（3）一維與二維存儲(chǔ)管理第49頁(yè)4.4.3信息共享

圖4-18分頁(yè)系統(tǒng)中共享editor示意圖存儲(chǔ)管理第50頁(yè)圖4-19分段系統(tǒng)中共享editor示意圖存儲(chǔ)管理第51頁(yè)段式管理優(yōu)缺點(diǎn)優(yōu)點(diǎn)：程序各段可獨(dú)立編譯（修改一個(gè)過(guò)程不會(huì)影響其它無(wú)關(guān)過(guò)程）可采取不一樣保護(hù)辦法（段只包含一個(gè)類型對(duì)象，能夠有針對(duì)這種特定類型適當(dāng)保護(hù)）便于共享一些段（常見(jiàn)例子是共享庫(kù)，如圖形庫(kù)）缺點(diǎn)：段長(zhǎng)受限制（段長(zhǎng)不定會(huì)出現(xiàn)空閑區(qū)上內(nèi)存浪費(fèi)）段是作為一個(gè)整體調(diào)入調(diào)出，操作時(shí)間長(zhǎng)存儲(chǔ)管理第52頁(yè)4.4.4段頁(yè)式存放管理方式

基本原理面對(duì)用戶程序地址空間，采取段式分割內(nèi)存分為長(zhǎng)度相等若干塊將每段劃分為頁(yè)，也常與內(nèi)存塊相等

分頁(yè)優(yōu)點(diǎn)：提升內(nèi)存利用率分段優(yōu)點(diǎn)：方便用戶，易于共享，保護(hù)，動(dòng)態(tài)鏈接。存儲(chǔ)管理第53頁(yè)圖4-20作業(yè)地址空間和地址結(jié)構(gòu)存儲(chǔ)管理第54頁(yè)圖4-21利用段表和頁(yè)表實(shí)現(xiàn)地址映射存儲(chǔ)管理第55頁(yè)2.地址變換過(guò)程

圖4-22段頁(yè)式系統(tǒng)中地址變換機(jī)構(gòu)存儲(chǔ)管理第56頁(yè)例：對(duì)于下表所表示段表，請(qǐng)將邏輯地址（0，137），（1，4000），（2，3600），（5，230）轉(zhuǎn)換成物理地址。段號(hào)基址段長(zhǎng)050K10K160K3K270K5K3120K8K存儲(chǔ)管理第57頁(yè)4.5虛擬存放器基本概念

4.5.1虛擬存放器引入1.常規(guī)存放器管理方式特征一次性（指全部裝入）。

(2)駐留性（指駐留在內(nèi)存不換出）。

存儲(chǔ)管理第58頁(yè)2.局部性原理時(shí)間局部性：如循環(huán)執(zhí)行空間局部性：如次序執(zhí)行。3.虛擬存放器含有請(qǐng)求調(diào)入功效和置換功效，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充一個(gè)存放系統(tǒng)。實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧牲不大。存儲(chǔ)管理第59頁(yè)4.5.2虛擬存放器實(shí)現(xiàn)方式需要?jiǎng)討B(tài)重定位一、請(qǐng)求分頁(yè)系統(tǒng)以頁(yè)為單位轉(zhuǎn)換需硬件：（1）請(qǐng)求分頁(yè)頁(yè)表機(jī)制（2）缺頁(yè)中止（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分頁(yè)機(jī)制軟件（置換軟件等）存儲(chǔ)管理第60頁(yè)二、請(qǐng)求分段系統(tǒng)以段為單位轉(zhuǎn)換:（1）請(qǐng)求分段段表結(jié)構(gòu)（2）缺段中止（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分段機(jī)制軟件（置換軟件等）存儲(chǔ)管理第61頁(yè)4.5.3虛存特征1．離散性：部分裝入 （若連續(xù)則不可能提供虛存），無(wú)法支持大作業(yè)小內(nèi)存運(yùn)行2．屢次性：局部裝入，屢次裝入。3．對(duì)換性：4．虛擬性.存儲(chǔ)管理第62頁(yè)4.6請(qǐng)求分頁(yè)存放管理方式

4.6.1請(qǐng)求分頁(yè)中硬件支持

1.頁(yè)表機(jī)制

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址存儲(chǔ)管理第63頁(yè)2.缺頁(yè)中止機(jī)構(gòu)

圖4-23包括6次缺頁(yè)中止指令缺頁(yè)中止機(jī)構(gòu)：可在指令執(zhí)行期間產(chǎn)生，轉(zhuǎn)入缺頁(yè)中止處理程序。存儲(chǔ)管理第64頁(yè)3.地址變換機(jī)構(gòu)

圖4-24請(qǐng)求分頁(yè)中地址變換過(guò)程存儲(chǔ)管理第65頁(yè)4.6.2內(nèi)存分配策略和分配算法一、最小物理塊數(shù)不一樣作業(yè)要求不一樣。如：允許間接尋址：則最少要求3個(gè)物理塊。MovA,[B]存儲(chǔ)管理第66頁(yè)二、頁(yè)面分配和置換策略。1．固定分配局部置換。缺點(diǎn)：難以確定固定分配頁(yè)數(shù).(少：置換率高;多：浪費(fèi))2.可變分配全局置換3.可變分配局部置換依據(jù)進(jìn)程缺頁(yè)率進(jìn)行頁(yè)面數(shù)調(diào)整，進(jìn)程之間相互不會(huì)影響。存儲(chǔ)管理第67頁(yè)三、分配算法

1．平均分配算法2．按進(jìn)程大小百分比分配算法：3．考慮優(yōu)先權(quán)分配算法存儲(chǔ)管理第68頁(yè)4.6.3頁(yè)面調(diào)入策略1.調(diào)入時(shí)機(jī)：預(yù)調(diào)：（依據(jù)空間局部性）當(dāng)前：成功率≤50％請(qǐng)求調(diào)入：較費(fèi)系統(tǒng)開(kāi)銷各有優(yōu)劣2．從何處調(diào)頁(yè)：對(duì)換區(qū)：全部從對(duì)換區(qū)調(diào)入所需頁(yè)面， 快文件區(qū)：修改過(guò)頁(yè)面換出到對(duì)換區(qū)， 稍慢UNIX方式：未運(yùn)行過(guò)頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。曾經(jīng)運(yùn)行過(guò)但又被換出頁(yè)面，從對(duì)換區(qū)調(diào)入。對(duì)共享頁(yè)，應(yīng)判斷其是否在內(nèi)存區(qū)。3.頁(yè)面調(diào)入過(guò)程存儲(chǔ)管理第69頁(yè)4.7頁(yè)面置換算法4.7.1最正確置換算法和先進(jìn)先出置換算法

1.最正確(Optimal)置換算法

最正確置換算法是由Belady于1966年提出一個(gè)理論上算法。其所選擇被淘汰頁(yè)面，將是以后永不使用，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)頁(yè)面。存儲(chǔ)管理第70頁(yè)

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下頁(yè)面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

圖4-25利用最正確頁(yè)面置換算法時(shí)置換圖存儲(chǔ)管理第71頁(yè)2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用FIFO置換算法時(shí)置換圖存儲(chǔ)管理第72頁(yè)4.7.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法描述

圖4-27LRU頁(yè)面置換算法存儲(chǔ)管理第73頁(yè)2.LRU置換算法硬件支持

1)存放器為了統(tǒng)計(jì)某進(jìn)程在內(nèi)存中各頁(yè)使用情況，須為每個(gè)在內(nèi)存中頁(yè)面配置一個(gè)移位存放器，可表示為

R=Rn-1Rn-2Rn-3…R2R1R0

存儲(chǔ)管理第74頁(yè)圖4-28某進(jìn)程含有8個(gè)頁(yè)面時(shí)LRU訪問(wèn)情況存儲(chǔ)管理第75頁(yè)2)棧

圖4-29用棧保留當(dāng)前使用頁(yè)面時(shí)棧改變情況存儲(chǔ)管理第76頁(yè)4.7.3Clock置換算法

1.簡(jiǎn)單Clock置換算法

圖4-30簡(jiǎn)單Clock置換算法流程和示例存儲(chǔ)管理第77頁(yè)2.改進(jìn)型Clock置換算法

由訪問(wèn)位A和修改位M能夠組合成下面四種類型頁(yè)面：1類(A=0,M=0):表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最正確淘汰頁(yè)。2類(A=0,M=1)：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好淘汰頁(yè)。3類(A=1,M=0)：最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)。4類(A=1,M=1):最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)。存儲(chǔ)管理第78頁(yè)

其執(zhí)行過(guò)程可分成以下三步：(1)從指針?biāo)甘井?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找A=0且M=0第一類頁(yè)面，將所碰到第一個(gè)頁(yè)面作為所選中淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。(2)假如第一步失敗，即查找一周后未碰到第一類頁(yè)面，則開(kāi)始第二輪掃描，尋找A=0且M=1第二類頁(yè)面，將所碰到第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將全部掃描過(guò)頁(yè)面訪問(wèn)位都置0。(3)假如第二步也失敗，亦即未找到第二類頁(yè)面，則將指針?lè)祷氐介_(kāi)始位置，并將全部訪問(wèn)位復(fù)0。然后重復(fù)第一步，假如仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰頁(yè)。

存儲(chǔ)管理第79頁(yè)

4.7.4請(qǐng)求分頁(yè)系統(tǒng)性能分析

請(qǐng)求分頁(yè)系統(tǒng)是當(dāng)前最慣用一個(gè)存放方式，但運(yùn)行中產(chǎn)生缺頁(yè)情況會(huì)影響速度和系統(tǒng)性能，而缺頁(yè)率高低往往與進(jìn)程所占用物理塊數(shù)相關(guān)。所以本節(jié)分析缺頁(yè)率對(duì)系統(tǒng)性能影響，以及應(yīng)為每個(gè)進(jìn)程所分配物理塊數(shù)目。1.缺頁(yè)率與有效訪問(wèn)時(shí)間

有效訪問(wèn)時(shí)間=(1-p)*t+p*f

其中：p為缺頁(yè)率，t為內(nèi)存訪問(wèn)時(shí)間，f為缺頁(yè)中止時(shí)間存儲(chǔ)管理第80頁(yè)說(shuō)明：當(dāng)代計(jì)算機(jī)系統(tǒng)，內(nèi)存訪問(wèn)時(shí)間在10ns到數(shù)百ns之間。(以100ns為例計(jì)算）缺頁(yè)中止時(shí)間包含三部分：（1）缺頁(yè)中止服務(wù)時(shí)間；（2）將缺頁(yè)讀入時(shí)間；（3）進(jìn)程重新執(zhí)行時(shí)間。因?yàn)镃PU時(shí)間很快，所以（1）（3）能夠不超出1ms；（2）則包含尋道時(shí)間、旋轉(zhuǎn)時(shí)間和數(shù)據(jù)傳送時(shí)間，大致需要24ms。代入上式得：

有效訪問(wèn)時(shí)間=（1-p）*0.1(μs)+p*25000(μs)=0.1+24999.9*p假如缺頁(yè)率p=0.001（即在1000次頁(yè)面訪問(wèn)中，僅發(fā)生一次缺頁(yè)）則有效訪問(wèn)時(shí)間約為25μs，與無(wú)缺頁(yè)相比，速度降低至1/250。存儲(chǔ)管理第81頁(yè)假如希望在缺頁(yè)時(shí)有效訪問(wèn)時(shí)間延長(zhǎng)不超出10%，則有0.11>0.1+24999.9*p則p<0.01/24999.9=0.0000004

結(jié)論：有效訪問(wèn)時(shí)間直接百分比與缺頁(yè)率，改進(jìn)請(qǐng)求分頁(yè)系統(tǒng)性能，需要保持非常低缺頁(yè)率，同時(shí)提升I/O速度。存儲(chǔ)管理第82頁(yè)2.抖動(dòng)——是這么一個(gè)系統(tǒng)狀態(tài)，即系統(tǒng)花在頁(yè)面替換上時(shí)間遠(yuǎn)遠(yuǎn)大于執(zhí)行進(jìn)程時(shí)間。抖動(dòng)產(chǎn)生原因：因?yàn)榉峙浣o進(jìn)程頁(yè)面數(shù)大小少于進(jìn)程所需要最低頁(yè)面數(shù)，造成出現(xiàn)接連不停缺頁(yè)中止，引發(fā)抖動(dòng)。

CPU利用率與多道程序度關(guān)系：多道程序度指在內(nèi)存中并發(fā)執(zhí)行程序數(shù)目。二者關(guān)系以下：在低度情況下，CPU利用率呈線性改變關(guān)系。伴隨度上升，CPU利用率也逐步上升，最終上升到一個(gè)最大值，若在這種情況下，深入增加度，則系統(tǒng)發(fā)生抖動(dòng)，且CPU利用率將快速惡化。結(jié)論：系統(tǒng)能夠利用CPU利用率與多道程序度進(jìn)行比較方法檢測(cè)抖動(dòng)，一旦發(fā)生抖動(dòng)，能夠經(jīng)過(guò)降低多道程序度方法來(lái)消除。存儲(chǔ)管理第83頁(yè)例：考慮一個(gè)請(qǐng)求分頁(yè)系統(tǒng)，它采取全局置換策略和平均分配內(nèi)存塊算法（即若有m個(gè)內(nèi)存塊和n個(gè)進(jìn)程，則每個(gè)進(jìn)程分得m/n個(gè)內(nèi)存塊）。假如該系統(tǒng)測(cè)得以下CPU和對(duì)換盤利用率，請(qǐng)問(wèn)能否用增加多道程序度數(shù)來(lái)增加CPU利用率？為何？（1）CPU利用率為13%，盤利用率為97%；（2）CPU利用率為87%，盤利用率為3%；（1）CPU利用率為13%，盤利用率為3%；存儲(chǔ)管理第84頁(yè)答：（1）此時(shí)發(fā)生抖動(dòng)現(xiàn)象。增加多道程序度會(huì)深入增加缺頁(yè)率，使系統(tǒng)性能深入惡化，所以不能用增加多道程序度數(shù)來(lái)增加CPU利用率。（2）CPU利用率已經(jīng)相當(dāng)高，盤利用率卻相當(dāng)?shù)停催M(jìn)程缺頁(yè)率很低，此時(shí)應(yīng)適當(dāng)增加多道程序度數(shù)來(lái)增加CPU利用率。（3）CPU利用率相當(dāng)?shù)停P利用率也相當(dāng)?shù)?，表示?nèi)存中可運(yùn)行程序數(shù)不足，此時(shí)應(yīng)增加多道程序度數(shù)來(lái)增加CPU利用率。存儲(chǔ)管理第85頁(yè)4.8請(qǐng)求分段存放管理方式

4.8.1請(qǐng)求分段中硬件支持

1.段表機(jī)制段名段長(zhǎng)段基址存取方式訪問(wèn)字段A修改位M存在位P增補(bǔ)位外存始址存儲(chǔ)管理第86頁(yè)

在段表項(xiàng)中，除了段名(號(hào))、段長(zhǎng)、段在內(nèi)存中起始地址外，還增加了以下諸項(xiàng)：(1)存取方式。(2)訪問(wèn)字段A。(3)修改位M。(4)存在位P。(5)增補(bǔ)位。(6)外存始址。存儲(chǔ)管理第87頁(yè)2.缺段中止機(jī)構(gòu)

圖4-31請(qǐng)求分段系統(tǒng)中中止處理過(guò)程存儲(chǔ)管理第88頁(yè)3.地址變換機(jī)構(gòu)

圖4-32請(qǐng)求分段系統(tǒng)地址變換過(guò)程存儲(chǔ)管理第89頁(yè)4.8.2分段共享與保護(hù)

1.共享段表

圖4-33共享段表項(xiàng)存儲(chǔ)管理第90頁(yè)2.共享段分配與回收

1)共享段分配在為共享段分配內(nèi)存時(shí)，對(duì)第一個(gè)請(qǐng)求使用該共享段進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時(shí)將該區(qū)始址填入請(qǐng)求進(jìn)程段表對(duì)應(yīng)項(xiàng)中，還須在共享段表中增加一表項(xiàng)，填寫相關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時(shí)，因?yàn)樵摴蚕矶我驯徽{(diào)入內(nèi)存，故此時(shí)無(wú)須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程段表中，增加一表項(xiàng)，填寫該共享段物理地址；在共享段段表中，填上調(diào)用進(jìn)程進(jìn)程名、存取控制等，再執(zhí)行count∶=count+1操作，以表明有兩個(gè)進(jìn)程共享該段。存儲(chǔ)管理第91頁(yè)

2)共享段回收當(dāng)共享此段某進(jìn)程不再需要該段時(shí)，應(yīng)將該段釋放，包含撤在該進(jìn)程段表中共享段所對(duì)應(yīng)表項(xiàng)，以及執(zhí)行count∶=count-1操作。若結(jié)果為0，則須由系統(tǒng)回收該共享段物理內(nèi)存，以及取消在共享段表中該段所對(duì)應(yīng)表項(xiàng)，表明此時(shí)已沒(méi)有進(jìn)程使用該段；不然(減1結(jié)果不為0)，則只是取消調(diào)用者進(jìn)程在共享段表中相關(guān)統(tǒng)計(jì)。存儲(chǔ)管理第92頁(yè)3.分段保護(hù)

越界檢驗(yàn)2)存取控制檢驗(yàn)※只讀※只執(zhí)行※讀/寫3)環(huán)境保護(hù)護(hù)機(jī)構(gòu)※一個(gè)程序能夠訪問(wèn)駐留在相同環(huán)或較低特權(quán)環(huán)中數(shù)據(jù)?！粋€(gè)程序能夠調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中服務(wù)。

存儲(chǔ)管理第93頁(yè)經(jīng)典問(wèn)題分析：1。設(shè)作業(yè)Ａ頁(yè)面映象表以下列圖所表示：（一頁(yè)=1KB）頁(yè)號(hào) 塊號(hào) 中止位訪問(wèn)位修改位輔存地址０ ８ １ １１１０００１ ５ １００３０００２ ７ １１０５０００３ ０００８０００問(wèn)：①指出頁(yè)表中中止位、訪問(wèn)位、修改位、輔存地址含義？②當(dāng)執(zhí)行到１０００單元指令“ＬＯＡＤ１，１８００”時(shí)，系統(tǒng)是怎樣進(jìn)行地址變換（即１８００在主存哪個(gè)單元中）③當(dāng)執(zhí)行到１５００單元指令（ＬＯＡＤ１，３６００）時(shí)，會(huì)發(fā)生什么現(xiàn)象？存儲(chǔ)管理第94頁(yè)（1）中止位：也稱狀態(tài)位，表示該頁(yè)是否已調(diào)入內(nèi)存；訪問(wèn)位：統(tǒng)計(jì)本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)次數(shù)；修改位：表示該頁(yè)調(diào)入內(nèi)存后是否修改過(guò)；輔存地址：指出該頁(yè)在輔存上地址。（2）設(shè)頁(yè)號(hào)為P，頁(yè)內(nèi)地址為d，邏輯地址為A，頁(yè)面大小為L(zhǎng)，則：P=INT[A/L]d=[A]modL當(dāng)執(zhí)行到１０００單元指令“ＬＯＡＤ１，１８００”時(shí)，系統(tǒng)地址變換以下：L=1024B，A=1800，則P=INT[1800/1024]=1，d=[1800]mod1024=776故A=1800→（1，776）查頁(yè)表第1頁(yè)在第5塊，所以物理地址為：5896存儲(chǔ)管理第95頁(yè)(3)當(dāng)執(zhí)行到１５００單元指令（ＬＯＡＤ１，３６００）時(shí)，系統(tǒng)地址變換以下：L=1024B，A=3600，則P=INT[3600/1024]=3，d=[3600]mod1024=528故A=3600→（3，528）查頁(yè)表第3頁(yè)未調(diào)入內(nèi)存，所以產(chǎn)生缺頁(yè)中止，從輔存8000位置將該頁(yè)調(diào)入。存儲(chǔ)管理第96頁(yè)2.有一個(gè)二維數(shù)組：VarA:AR