04存儲(chǔ)管理課件

第四章存儲(chǔ)器管理引言4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁(yè)存儲(chǔ)管理方式4.4基本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的基本概念4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.7頁(yè)面置換算法4.8請(qǐng)求分段存儲(chǔ)管理方式第四章存儲(chǔ)器管理引言存儲(chǔ)組織存儲(chǔ)器的功能是保存數(shù)據(jù)，存儲(chǔ)器的發(fā)展方向是高速、大容量和小體積。內(nèi)存在訪問(wèn)速度方面的發(fā)展：DRAM、SDRAM、DDR、DRDRAM、DDR2、XDR、SRAM等；硬盤技術(shù)在大容量方面的發(fā)展：接口標(biāo)準(zhǔn)、存儲(chǔ)密度等；存儲(chǔ)組織是指在存儲(chǔ)技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲(chǔ)結(jié)構(gòu)。其依據(jù)是訪問(wèn)速度匹配關(guān)系、容量要求和價(jià)格?！凹拇嫫?內(nèi)存-外存”結(jié)構(gòu)“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；存儲(chǔ)組織存儲(chǔ)器的功能是保存數(shù)據(jù)，存儲(chǔ)器的發(fā)展方向是高速、大容存儲(chǔ)層次結(jié)構(gòu)快速緩存：SRAM內(nèi)存：DRAM,SDRAM,DDR,DRDRAM、DDR2、XDR等；外存：軟盤、硬盤、光盤、磁帶等；微機(jī)中的存儲(chǔ)層次組織：訪問(wèn)速度越慢，容量越大，價(jià)格越便宜；最佳狀態(tài)應(yīng)是各層次的存儲(chǔ)器都處于均衡的繁忙狀態(tài)；存儲(chǔ)層次結(jié)構(gòu)快速緩存：SRAM存儲(chǔ)管理的功能存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。地址變換：可執(zhí)行文件生成中的鏈接技術(shù)程序加載(裝入)時(shí)的重定位技術(shù)進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)存儲(chǔ)共享和保護(hù)：代碼和數(shù)據(jù)共享地址空間訪問(wèn)權(quán)限（讀、寫、執(zhí)行）存儲(chǔ)器擴(kuò)充：存儲(chǔ)管理的功能存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)重定位：實(shí)現(xiàn)邏輯地址（相對(duì)地址）到物理地址（絕對(duì)地址）的映射。邏輯地址：應(yīng)用程序經(jīng)編譯后形成目標(biāo)程序，再經(jīng)過(guò)鏈接后形成可裝入程序，這些程序的地址都是從0開(kāi)始，程序中的其他地址都是相對(duì)于起始地址計(jì)算的，這些地址為相對(duì)地址。物理地址：主存中一系列存儲(chǔ)信息的物理單元的地址。重定位概念重定位：實(shí)現(xiàn)邏輯地址（相對(duì)地址）到物理地址（絕對(duì)地址）的映射4.1程序的裝入和鏈接編輯―――編譯―――鏈接―――裝入―――運(yùn)行4.1程序的裝入和鏈接編輯―――編譯―――鏈接―――裝入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)位置。4.1.1程序的裝入1、絕對(duì)裝入：0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作業(yè)地址空間內(nèi)存空間圖4-20100025005000LOAD1,2500LOAD3.動(dòng)態(tài)運(yùn)行時(shí)裝入在裝入后不能移動(dòng)，該情況一般在執(zhí)行時(shí)才完成相對(duì)——絕對(duì)地址的轉(zhuǎn)換且有硬件的支持,能保證進(jìn)程的可移動(dòng)性。04存儲(chǔ)管理課件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)鏈接4.1.2程序的鏈接1、靜態(tài)鏈接模塊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)裝入模塊模塊A模塊B模塊C0L-10M-10N-1(a)目標(biāo)模塊模塊4.2連續(xù)分配方式單一連續(xù)分配用于單用戶，單任務(wù)中分區(qū)式分配固定式可變式可重定位分區(qū)分配4.2連續(xù)分配方式單一連續(xù)分配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)存。4.2.1單一連續(xù)分區(qū)內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。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í)作記錄例：dos的MCB三、特點(diǎn)：簡(jiǎn)單，有碎片（內(nèi)零頭）4.2.2固定分區(qū)特點(diǎn)：有n個(gè)分區(qū)，則可同時(shí)裝入n個(gè)作業(yè)分區(qū)說(shuō)明表分區(qū)號(hào)大?。↘)起址（K）狀態(tài)11220已分配23232已分配36464已分配4128128已分配分區(qū)說(shuō)明表分區(qū)號(hào)大?。↘)起址（K）狀態(tài)11220已分配23操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K~~~~分配情況操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K4.2.3可變式分區(qū)一、數(shù)據(jù)結(jié)構(gòu)1．空閑分區(qū)表2．空閑分區(qū)鏈前向指針N個(gè)字節(jié)可用后向指針N+2N+20（分配標(biāo)識(shí)）04.2.3可變式分區(qū)一、數(shù)據(jù)結(jié)構(gòu)前向指針N個(gè)字節(jié)可用后向二、分配算法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)位置。二、分配算法三、分區(qū)分配分配算法三、分區(qū)分配分配算法F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時(shí)的情況回收：（1）上鄰空閑區(qū)：合并，改大?。?）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項(xiàng)。F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時(shí)的情況回例：在計(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例：在計(jì)算機(jī)系統(tǒng)中,按地址排列的內(nèi)存中的空閑區(qū)大小是:10K4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入連續(xù)式分配中，總量大于作業(yè)大小的多個(gè)小分區(qū)不能容納作業(yè)。緊湊通過(guò)作業(yè)移動(dòng)將原來(lái)分散的小分區(qū)拼接成一個(gè)大分區(qū)。作業(yè)的移動(dòng)需重定位。是動(dòng)態(tài)（因作業(yè)已經(jīng)裝入）4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入緊湊緊湊2、動(dòng)態(tài)重定位的實(shí)現(xiàn)load1,2500365load1,25003650100250050002500100001000010100+1250015000作業(yè)J處理機(jī)一側(cè)存儲(chǔ)器一側(cè)重定位寄存器相對(duì)地址2、動(dòng)態(tài)重定位的實(shí)現(xiàn)load1,2500365load1圖4.10動(dòng)態(tài)分區(qū)分配算法圖4.10動(dòng)態(tài)分區(qū)分配算法4.2.5對(duì)換1對(duì)換的引入將阻塞進(jìn)程，暫時(shí)不用的程序，數(shù)據(jù)換出。將具備運(yùn)行條件的進(jìn)程換入。類型：整體對(duì)換：進(jìn)程對(duì)換，解決內(nèi)存緊張部分對(duì)換：頁(yè)面對(duì)換/分段對(duì)換：提供虛存支持2對(duì)換空間的管理外存對(duì)換區(qū)比文件區(qū)側(cè)重于對(duì)換速度。因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類似于可變化分區(qū)分配。4.2.5對(duì)換1對(duì)換的引入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．換入3換出與換入4.3基本分頁(yè)存儲(chǔ)管理連續(xù)分配引起:碎片碎片問(wèn)題的解決：緊湊方式消耗系統(tǒng)開(kāi)銷。離散分配分頁(yè)、分段、段頁(yè)4.3基本分頁(yè)存儲(chǔ)管理連續(xù)分配引起:碎片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位移W1.頁(yè)面4.3.1頁(yè)面與頁(yè)表頁(yè)號(hào)P位移W例：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）例：L=1000B，則第0頁(yè)對(duì)應(yīng)0-999，第1頁(yè)對(duì)應(yīng)1003.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)021326384950123456789用戶程序頁(yè)表頁(yè)號(hào)塊號(hào)內(nèi)存3.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)0213263849504.2地址變換機(jī)構(gòu)基本任務(wù)：邏輯地址——物理地址的映射。

頁(yè)號(hào)→塊號(hào)通過(guò)頁(yè)表來(lái)完成頁(yè)內(nèi)地址→塊內(nèi)地址無(wú)需轉(zhuǎn)換一、基本地址變換機(jī)構(gòu)： 越界保護(hù)每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址裝入頁(yè)表寄存器。4.2地址變換機(jī)構(gòu)基本任務(wù)：邏輯地址——物理地址的映射04存儲(chǔ)管理課件

需要考慮的問(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

需要考慮的問(wèn)題：2.具有快表的地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。（1）訪頁(yè)表（2）得到絕對(duì)地址內(nèi)容有快表，速度提高?？毂碣F，不能太多。2.具有快表的地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。2.具有快表的地址變換機(jī)構(gòu)2.具有快表的地址變換機(jī)構(gòu)

例：有一頁(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í)間是多少?例：有一頁(yè)式系統(tǒng)，其頁(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)答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不同頁(yè)塊中。建一“外部頁(yè)表”來(lái)管理這些離散頁(yè)表塊。相當(dāng)于單級(jí)頁(yè)表中的頁(yè)表寄存器，一般應(yīng)常駐內(nèi)存。每項(xiàng)記錄頁(yè)表始址，且增加存在位。64位機(jī)器頁(yè)表一般>3級(jí)，最外層頁(yè)表常駐。4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不04存儲(chǔ)管理課件04存儲(chǔ)管理課件1.某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略，擁有邏輯空間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)相應(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í)：1.某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略，擁有邏輯空間32頁(yè)，每頁(yè)2K1.(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位。1.2.(1)邏輯地址1023：1023/1024，得頁(yè)號(hào)0，頁(yè)內(nèi)地址1023，查頁(yè)表的相應(yīng)塊號(hào)2，故物理地址為2*1024+1023=3071邏輯地址2500：2500/1024，得頁(yè)號(hào)2，頁(yè)內(nèi)地址452，查頁(yè)表的相應(yīng)塊號(hào)6，故物理地址為6*1024+452=6596邏輯地址3500：3500/1024，得頁(yè)號(hào)3，頁(yè)內(nèi)地址428，查頁(yè)表的相應(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)生越界中斷。2.(1)4.4基本分段存儲(chǔ)管理4.4.1引入

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

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

4.4.2分段系統(tǒng)的基本原理分段分段地址中的地址具有如圖4-16利用段表實(shí)現(xiàn)地址映射圖4-16利用段表實(shí)現(xiàn)地址映射圖4-17分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)

圖4-17分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)4.分頁(yè)和分段的主要區(qū)別

（1）頁(yè)是信息的物理單位，段是邏輯單位（2）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）（3）一維與二維4.分頁(yè)和分段的主要區(qū)別（1）頁(yè)是信息的物理單位，段4.4.3信息共享

圖4-18分頁(yè)系統(tǒng)中共享editor的示意圖4.4.3信息共享圖4-18分頁(yè)系統(tǒng)中共享edit圖4-19分段系統(tǒng)中共享editor的示意圖圖4-19分段系統(tǒng)中共享editor的示意圖段式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：程序的各段可獨(dú)立編譯（修改一個(gè)過(guò)程不會(huì)影響其它無(wú)關(guān)過(guò)程）可采用不同的保護(hù)措施（段只包含一種類型的對(duì)象，可以有針對(duì)這種特定類型的合適的保護(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)段式管理的優(yōu)缺點(diǎn)4.4.4段頁(yè)式存儲(chǔ)管理方式

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

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

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

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

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

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

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

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

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.6.1請(qǐng)求分頁(yè)中的硬件2.缺頁(yè)中斷機(jī)構(gòu)

圖4-23涉及6次缺頁(yè)中斷的指令缺頁(yè)中斷機(jī)構(gòu)：可在指令執(zhí)行期間產(chǎn)生，轉(zhuǎn)入缺頁(yè)中斷處理程序。2.缺頁(yè)中斷機(jī)構(gòu)圖4-23涉及6次缺頁(yè)中斷的指令缺3.地址變換機(jī)構(gòu)

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

1．平均分配算法2．按進(jìn)程大小比例分配算法：3．考慮優(yōu)先權(quán)分配算法三、分配算法1．平均分配算法4.6.3頁(yè)面調(diào)入策略1.調(diào)入時(shí)機(jī)：預(yù)調(diào)：（根據(jù)空間局部性）目前：成功率≤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ò)程4.6.3頁(yè)面調(diào)入策略1.調(diào)入時(shí)機(jī)：4.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法

最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。4.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換

假定系統(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í)的置換圖假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用FIFO置換算法時(shí)的置換圖2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用4.7.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述

圖4-27LRU頁(yè)面置換算法4.7.2最近最久未使用(LRU)置換算法1.LRU(2.LRU置換算法的硬件支持

1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為

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

2.LRU置換算法的硬件支持1)寄存圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況2)棧

圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況2)棧圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況4.7.3Clock置換算法

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

圖4-30簡(jiǎn)單Clock置換算法的流程和示例4.7.3Clock置換算法1.簡(jiǎn)單的Clock置換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)。2.改進(jìn)型Clock置換算法由訪問(wèn)位A和修

其執(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è)。

其執(zhí)行過(guò)程可分成以下三步：

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

請(qǐng)求分頁(yè)系統(tǒng)是目前最常用的一種存儲(chǔ)方式，但運(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í)間4.7.4請(qǐng)求分頁(yè)系統(tǒng)的性能分析請(qǐng)求分頁(yè)系統(tǒng)說(shuō)明：現(xiàn)代計(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í)間。由于CPU時(shí)間很快，所以（1）（3）可以不超過(guò)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。說(shuō)明：如果希望在缺頁(yè)時(shí)有效訪問(wèn)時(shí)間延長(zhǎng)不超過(guò)10%，則有0.11>0.1+24999.9*p則p<0.01/24999.9=0.0000004

結(jié)論：有效訪問(wèn)時(shí)間直接比例與缺頁(yè)率，改善請(qǐng)求分頁(yè)系統(tǒng)的性能，需要保持非常低的缺頁(yè)率，同時(shí)提高I/O的速度。如果希望在缺頁(yè)時(shí)有效訪問(wèn)時(shí)間延長(zhǎng)不超過(guò)10%，則有結(jié)論：有效2.抖動(dòng)——是這樣一種系統(tǒng)狀態(tài)，即系統(tǒng)花在頁(yè)面替換上的時(shí)間遠(yuǎn)遠(yuǎn)大于執(zhí)行進(jìn)程的時(shí)間。抖動(dòng)產(chǎn)生的原因：由于分配給進(jìn)程的頁(yè)面數(shù)大小少于進(jìn)程所需要的最低頁(yè)面數(shù)，導(dǎo)致出現(xiàn)接連不斷的缺頁(yè)中斷，引起抖動(dòng)。

CPU利用率與多道程序度的關(guān)系：多道程序度指在內(nèi)存中并發(fā)執(zhí)行的程序數(shù)目。兩者關(guān)系如下：在低度情況下，CPU利用率呈線性變化關(guān)系。隨著度的上升，CPU利用率也逐漸上升，最終上升到一個(gè)最大值，若在這種情況下，進(jìn)一步增加度，則系統(tǒng)發(fā)生抖動(dòng)，且CPU利用率將迅速惡化。結(jié)論：系統(tǒng)可以利用CPU利用率與多道程序度進(jìn)行比較的方法檢測(cè)抖動(dòng)，一旦發(fā)生抖動(dòng)，可以通過(guò)減少多道程序度的方法來(lái)消除。2.抖動(dòng)——是這樣一種系統(tǒng)狀態(tài)，即系統(tǒng)花在頁(yè)面替換上的時(shí)間遠(yuǎn)例：考慮一個(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%；例：考慮一個(gè)請(qǐng)求分頁(yè)系統(tǒng)，它采用全局置換策略和平均分配內(nèi)存塊答：（1）此時(shí)發(fā)生抖動(dòng)現(xiàn)象。增加多道程序度會(huì)進(jìn)一步增加缺頁(yè)率，使系統(tǒng)性能進(jìn)一步惡化，所以不能用增加多道程序度數(shù)來(lái)增加CPU的利用率。（2）CPU利用率已經(jīng)相當(dāng)高，盤利用率卻相當(dāng)?shù)?，即進(jìn)程的缺頁(yè)率很低，此時(shí)應(yīng)適當(dāng)增加多道程序度數(shù)來(lái)增加CPU的利用率。（3）CPU利用率相當(dāng)?shù)?，盤利用率也相當(dāng)?shù)停硎緝?nèi)存中可運(yùn)行的程序數(shù)不足，此時(shí)應(yīng)增加多道程序度數(shù)來(lái)增加CPU的利用率。答：4.8請(qǐng)求分段存儲(chǔ)管理方式

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

1.段表機(jī)制段名段長(zhǎng)段的基址存取方式訪問(wèn)字段A修改位M存在位P增補(bǔ)位外存始址4.8請(qǐng)求分段存儲(chǔ)管理方式4.8.1請(qǐng)求分段中的硬件支

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

圖4-31請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程2.缺段中斷機(jī)構(gòu)圖4-31請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)3.地址變換機(jī)構(gòu)

圖4-32請(qǐng)求分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)圖4-32請(qǐng)求分段系統(tǒng)的地址變換過(guò)程4.8.2分段的共享與保護(hù)

1.共享段表

圖4-33共享段表項(xiàng)4.8.2分段的共享與保護(hù)1.共享段表圖4-332.共享段的分配與回收

1)共享段的分配在為共享段分配內(nèi)存時(shí)，對(duì)第一個(gè)請(qǐng)求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時(shí)將該區(qū)的始址填入請(qǐng)求進(jìn)程的段表的相應(yīng)項(xiàng)中，還須在共享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時(shí)，由于該共享段已被調(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)程共享該段。2.共享段的分配與回收1)共享段的分配

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)記錄。2)共享段的回收3.分段保護(hù)

越界檢查2)存取控制檢查※只讀※只執(zhí)行※讀/寫3)環(huán)保護(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ù)。

3.分段保護(hù)越界檢查典型問(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)象？典型問(wèn)題分析：（1）中斷位：也稱狀態(tài)位，表示該頁(yè)是否已調(diào)入內(nèi)存；訪問(wèn)位：記錄本頁(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（1）中斷位：也稱狀態(tài)位，表示該頁(yè)是否已調(diào)入內(nèi)存；(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)入。(3)當(dāng)執(zhí)行到１５００單元指令（ＬＯＡＤ１，３６００）2.有一個(gè)二維數(shù)組：VarA:ARRAY[1..100,1..100]OFinteger;按先行后列的次序存儲(chǔ)。對(duì)一采用LRU置換算法的頁(yè)式虛擬存儲(chǔ)器系統(tǒng)，假設(shè)每頁(yè)可存放200個(gè)整數(shù)。若分配給一個(gè)進(jìn)程的內(nèi)存塊數(shù)為3，其中一塊用來(lái)裝入程序和變量i、j，另外兩塊專門用來(lái)存放數(shù)組（不作它用），且程序段已在內(nèi)存，但數(shù)據(jù)頁(yè)尚未裝入內(nèi)存。請(qǐng)分別就下列程序計(jì)算執(zhí)行過(guò)程中的缺頁(yè)次數(shù)。程序1程序2FORi:=1TO100DOFORj:=1TO100DOFORj:=1TO100DOFORi:=1TO100DOA[i,j]:=0;A[i,j]:=0;2.有一個(gè)二維數(shù)組：2.答：對(duì)程序1，首次缺頁(yè)中斷（訪問(wèn)A[0,0]時(shí)產(chǎn)生）將裝入數(shù)組的第1、2行共200個(gè)整數(shù)，由于程序是按行對(duì)數(shù)組進(jìn)行訪問(wèn)，只有在處理完200個(gè)整數(shù)后才會(huì)再次產(chǎn)生缺頁(yè)中斷；以后每調(diào)入一頁(yè)，也能處理200個(gè)整數(shù)，因此處理100*100個(gè)整數(shù)共將發(fā)生50次缺頁(yè)。對(duì)程序2，首次缺頁(yè)中斷同樣將裝入數(shù)組的第1、2行共200個(gè)整數(shù)，但由于程序是按列隊(duì)數(shù)組進(jìn)行訪問(wèn)，因此在處理完2個(gè)整數(shù)后又會(huì)再次產(chǎn)生缺頁(yè)中斷；以后每調(diào)入一頁(yè)，也只能處理2個(gè)整數(shù)，因此，處理100*100個(gè)整數(shù)共將產(chǎn)生5000次調(diào)頁(yè)。2.答：對(duì)程序1，首次缺頁(yè)中斷（訪問(wèn)A[0,0]時(shí)產(chǎn)生）將裝3.現(xiàn)有一請(qǐng)求調(diào)頁(yè)系統(tǒng)，頁(yè)表保存在寄存器中，若有一個(gè)被替換的頁(yè)未被修改，則處理一個(gè)缺頁(yè)中斷需要8ms，若被替換頁(yè)修改過(guò)，則處理一個(gè)缺頁(yè)中斷需要20ms。內(nèi)存存取時(shí)間為1μs，訪問(wèn)頁(yè)表時(shí)間可忽略不計(jì)。假定70%被替換的頁(yè)被修改過(guò)，為保證有效存取時(shí)間不超過(guò)2μs，可接受最大的缺頁(yè)率是多少？3.現(xiàn)有一請(qǐng)求調(diào)頁(yè)系統(tǒng)，頁(yè)表保存在寄存器中，若有一個(gè)被替換的3.答：用p表示缺頁(yè)率，則有效時(shí)間不超過(guò)2μs可表示為：(1-p)*1μs+p*(0.7*20ms+0.3*8ms+1μs)<=2μsp<=1/16400=0.00006即可接受的最大缺頁(yè)率為0.00006。3.答：用p表示缺頁(yè)率，則有效時(shí)間不超過(guò)2μs可表示為：本章作業(yè)：1.存儲(chǔ)器的用戶空間共有32個(gè)頁(yè)面，每頁(yè)1K，主存16K。假定某時(shí)刻.某虛擬系統(tǒng)為用戶的第0、1、2、3頁(yè)分配的物理塊號(hào)為5、10、4、7。而該用戶作業(yè)的長(zhǎng)度為6頁(yè)，試將十六進(jìn)制的虛擬地址0A5C、103C、1A5C轉(zhuǎn)換成物理地址。本章作業(yè)：2.假如一個(gè)程序的段表如下，其中存在位為1表示段在內(nèi)存，對(duì)于下面指令，在執(zhí)行時(shí)會(huì)產(chǎn)生什么樣的結(jié)果。段號(hào)存在位內(nèi)存始址段長(zhǎng)存取控制00500100W11100030R213000200E31800080R40500040R(1)STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,20](4)LOADR1,[3,100](5)JMP[2,100]2.假如一個(gè)程序的段表如下，其中存在位為1表示段在內(nèi)存，對(duì)于第四章存儲(chǔ)器管理引言4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁(yè)存儲(chǔ)管理方式4.4基本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的基本概念4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.7頁(yè)面置換算法4.8請(qǐng)求分段存儲(chǔ)管理方式第四章存儲(chǔ)器管理引言存儲(chǔ)組織存儲(chǔ)器的功能是保存數(shù)據(jù)，存儲(chǔ)器的發(fā)展方向是高速、大容量和小體積。內(nèi)存在訪問(wèn)速度方面的發(fā)展：DRAM、SDRAM、DDR、DRDRAM、DDR2、XDR、SRAM等；硬盤技術(shù)在大容量方面的發(fā)展：接口標(biāo)準(zhǔn)、存儲(chǔ)密度等；存儲(chǔ)組織是指在存儲(chǔ)技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲(chǔ)結(jié)構(gòu)。其依據(jù)是訪問(wèn)速度匹配關(guān)系、容量要求和價(jià)格?！凹拇嫫?內(nèi)存-外存”結(jié)構(gòu)“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；存儲(chǔ)組織存儲(chǔ)器的功能是保存數(shù)據(jù)，存儲(chǔ)器的發(fā)展方向是高速、大容存儲(chǔ)層次結(jié)構(gòu)快速緩存：SRAM內(nèi)存：DRAM,SDRAM,DDR,DRDRAM、DDR2、XDR等；外存：軟盤、硬盤、光盤、磁帶等；微機(jī)中的存儲(chǔ)層次組織：訪問(wèn)速度越慢，容量越大，價(jià)格越便宜；最佳狀態(tài)應(yīng)是各層次的存儲(chǔ)器都處于均衡的繁忙狀態(tài)；存儲(chǔ)層次結(jié)構(gòu)快速緩存：SRAM存儲(chǔ)管理的功能存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。地址變換：可執(zhí)行文件生成中的鏈接技術(shù)程序加載(裝入)時(shí)的重定位技術(shù)進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)存儲(chǔ)共享和保護(hù)：代碼和數(shù)據(jù)共享地址空間訪問(wèn)權(quán)限（讀、寫、執(zhí)行）存儲(chǔ)器擴(kuò)充：存儲(chǔ)管理的功能存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)重定位：實(shí)現(xiàn)邏輯地址（相對(duì)地址）到物理地址（絕對(duì)地址）的映射。邏輯地址：應(yīng)用程序經(jīng)編譯后形成目標(biāo)程序，再經(jīng)過(guò)鏈接后形成可裝入程序，這些程序的地址都是從0開(kāi)始，程序中的其他地址都是相對(duì)于起始地址計(jì)算的，這些地址為相對(duì)地址。物理地址：主存中一系列存儲(chǔ)信息的物理單元的地址。重定位概念重定位：實(shí)現(xiàn)邏輯地址（相對(duì)地址）到物理地址（絕對(duì)地址）的映射4.1程序的裝入和鏈接編輯―――編譯―――鏈接―――裝入―――運(yùn)行4.1程序的裝入和鏈接編輯―――編譯―――鏈接―――裝入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)位置。4.1.1程序的裝入1、絕對(duì)裝入：0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作業(yè)地址空間內(nèi)存空間圖4-20100025005000LOAD1,2500LOAD3.動(dòng)態(tài)運(yùn)行時(shí)裝入在裝入后不能移動(dòng)，該情況一般在執(zhí)行時(shí)才完成相對(duì)——絕對(duì)地址的轉(zhuǎn)換且有硬件的支持,能保證進(jìn)程的可移動(dòng)性。04存儲(chǔ)管理課件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)鏈接4.1.2程序的鏈接1、靜態(tài)鏈接模塊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)裝入模塊模塊A模塊B模塊C0L-10M-10N-1(a)目標(biāo)模塊模塊4.2連續(xù)分配方式單一連續(xù)分配用于單用戶，單任務(wù)中分區(qū)式分配固定式可變式可重定位分區(qū)分配4.2連續(xù)分配方式單一連續(xù)分配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)存。4.2.1單一連續(xù)分區(qū)內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。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í)作記錄例：dos的MCB三、特點(diǎn)：簡(jiǎn)單，有碎片（內(nèi)零頭）4.2.2固定分區(qū)特點(diǎn)：有n個(gè)分區(qū)，則可同時(shí)裝入n個(gè)作業(yè)分區(qū)說(shuō)明表分區(qū)號(hào)大小（K)起址（K）狀態(tài)11220已分配23232已分配36464已分配4128128已分配分區(qū)說(shuō)明表分區(qū)號(hào)大?。↘)起址（K）狀態(tài)11220已分配23操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K~~~~分配情況操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K4.2.3可變式分區(qū)一、數(shù)據(jù)結(jié)構(gòu)1．空閑分區(qū)表2．空閑分區(qū)鏈前向指針N個(gè)字節(jié)可用后向指針N+2N+20（分配標(biāo)識(shí)）04.2.3可變式分區(qū)一、數(shù)據(jù)結(jié)構(gòu)前向指針N個(gè)字節(jié)可用后向二、分配算法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)位置。二、分配算法三、分區(qū)分配分配算法三、分區(qū)分配分配算法F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時(shí)的情況回收：（1）上鄰空閑區(qū)：合并，改大小（2）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項(xiàng)。F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時(shí)的情況回例：在計(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例：在計(jì)算機(jī)系統(tǒng)中,按地址排列的內(nèi)存中的空閑區(qū)大小是:10K4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入連續(xù)式分配中，總量大于作業(yè)大小的多個(gè)小分區(qū)不能容納作業(yè)。緊湊通過(guò)作業(yè)移動(dòng)將原來(lái)分散的小分區(qū)拼接成一個(gè)大分區(qū)。作業(yè)的移動(dòng)需重定位。是動(dòng)態(tài)（因作業(yè)已經(jīng)裝入）4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入緊湊緊湊2、動(dòng)態(tài)重定位的實(shí)現(xiàn)load1,2500365load1,25003650100250050002500100001000010100+1250015000作業(yè)J處理機(jī)一側(cè)存儲(chǔ)器一側(cè)重定位寄存器相對(duì)地址2、動(dòng)態(tài)重定位的實(shí)現(xiàn)load1,2500365load1圖4.10動(dòng)態(tài)分區(qū)分配算法圖4.10動(dòng)態(tài)分區(qū)分配算法4.2.5對(duì)換1對(duì)換的引入將阻塞進(jìn)程，暫時(shí)不用的程序，數(shù)據(jù)換出。將具備運(yùn)行條件的進(jìn)程換入。類型：整體對(duì)換：進(jìn)程對(duì)換，解決內(nèi)存緊張部分對(duì)換：頁(yè)面對(duì)換/分段對(duì)換：提供虛存支持2對(duì)換空間的管理外存對(duì)換區(qū)比文件區(qū)側(cè)重于對(duì)換速度。因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類似于可變化分區(qū)分配。4.2.5對(duì)換1對(duì)換的引入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．換入3換出與換入4.3基本分頁(yè)存儲(chǔ)管理連續(xù)分配引起:碎片碎片問(wèn)題的解決：緊湊方式消耗系統(tǒng)開(kāi)銷。離散分配分頁(yè)、分段、段頁(yè)4.3基本分頁(yè)存儲(chǔ)管理連續(xù)分配引起:碎片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位移W1.頁(yè)面4.3.1頁(yè)面與頁(yè)表頁(yè)號(hào)P位移W例：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）例：L=1000B，則第0頁(yè)對(duì)應(yīng)0-999，第1頁(yè)對(duì)應(yīng)1003.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)021326384950123456789用戶程序頁(yè)表頁(yè)號(hào)塊號(hào)內(nèi)存3.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)0213263849504.2地址變換機(jī)構(gòu)基本任務(wù)：邏輯地址——物理地址的映射。

頁(yè)號(hào)→塊號(hào)通過(guò)頁(yè)表來(lái)完成頁(yè)內(nèi)地址→塊內(nèi)地址無(wú)需轉(zhuǎn)換一、基本地址變換機(jī)構(gòu)： 越界保護(hù)每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址裝入頁(yè)表寄存器。4.2地址變換機(jī)構(gòu)基本任務(wù)：邏輯地址——物理地址的映射04存儲(chǔ)管理課件

需要考慮的問(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

需要考慮的問(wèn)題：2.具有快表的地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。（1）訪頁(yè)表（2）得到絕對(duì)地址內(nèi)容有快表，速度提高。快表貴，不能太多。2.具有快表的地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。2.具有快表的地址變換機(jī)構(gòu)2.具有快表的地址變換機(jī)構(gòu)

例：有一頁(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í)間是多少?例：有一頁(yè)式系統(tǒng)，其頁(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)答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不同頁(yè)塊中。建一“外部頁(yè)表”來(lái)管理這些離散頁(yè)表塊。相當(dāng)于單級(jí)頁(yè)表中的頁(yè)表寄存器，一般應(yīng)常駐內(nèi)存。每項(xiàng)記錄頁(yè)表始址，且增加存在位。64位機(jī)器頁(yè)表一般>3級(jí)，最外層頁(yè)表常駐。4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不04存儲(chǔ)管理課件04存儲(chǔ)管理課件1.某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略，擁有邏輯空間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)相應(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í)：1.某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略，擁有邏輯空間32頁(yè)，每頁(yè)2K1.(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位。1.2.(1)邏輯地址1023：1023/1024，得頁(yè)號(hào)0，頁(yè)內(nèi)地址1023，查頁(yè)表的相應(yīng)塊號(hào)2，故物理地址為2*1024+1023=3071邏輯地址2500：2500/1024，得頁(yè)號(hào)2，頁(yè)內(nèi)地址452，查頁(yè)表的相應(yīng)塊號(hào)6，故物理地址為6*1024+452=6596邏輯地址3500：3500/1024，得頁(yè)號(hào)3，頁(yè)內(nèi)地址428，查頁(yè)表的相應(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)生越界中斷。2.(1)4.4基本分段存儲(chǔ)管理4.4.1引入

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

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

4.4.2分段系統(tǒng)的基本原理分段分段地址中的地址具有如圖4-16利用段表實(shí)現(xiàn)地址映射圖4-16利用段表實(shí)現(xiàn)地址映射圖4-17分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)

圖4-17分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)4.分頁(yè)和分段的主要區(qū)別

（1）頁(yè)是信息的物理單位，段是邏輯單位（2）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）（3）一維與二維4.分頁(yè)和分段的主要區(qū)別（1）頁(yè)是信息的物理單位，段4.4.3信息共享

圖4-18分頁(yè)系統(tǒng)中共享editor的示意圖4.4.3信息共享圖4-18分頁(yè)系統(tǒng)中共享edit圖4-19分段系統(tǒng)中共享editor的示意圖圖4-19分段系統(tǒng)中共享editor的示意圖段式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：程序的各段可獨(dú)立編譯（修改一個(gè)過(guò)程不會(huì)影響其它無(wú)關(guān)過(guò)程）可采用不同的保護(hù)措施（段只包含一種類型的對(duì)象，可以有針對(duì)這種特定類型的合適的保護(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)段式管理的優(yōu)缺點(diǎn)4.4.4段頁(yè)式存儲(chǔ)管理方式

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

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

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

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

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

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

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

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

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.6.1請(qǐng)求分頁(yè)中的硬件2.缺頁(yè)中斷機(jī)構(gòu)

圖4-23涉及6次缺頁(yè)中斷的指令缺頁(yè)中斷機(jī)構(gòu)：可在指令執(zhí)行期間產(chǎn)生，轉(zhuǎn)入缺頁(yè)中斷處理程序。2.缺頁(yè)中斷機(jī)構(gòu)圖4-23涉及6次缺頁(yè)中斷的指令缺3.地址變換機(jī)構(gòu)

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

1．平均分配算法2．按進(jìn)程大小比例分配算法：3．考慮優(yōu)先權(quán)分配算法三、分配算法1．平均分配算法4.6.3頁(yè)面調(diào)入策略1.調(diào)入時(shí)機(jī)：預(yù)調(diào)：（根據(jù)空間局部性）目前：成功率≤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ò)程4.6.3頁(yè)面調(diào)入策略1.調(diào)入時(shí)機(jī)：4.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法

最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。4.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換

假定系統(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í)的置換圖假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用FIFO置換算法時(shí)的置換圖2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用4.7.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述

圖4-27LRU頁(yè)面置換算法4.7.2最近最久未使用(LRU)置換算法1.LRU(2.LRU置換算法的硬件支持

1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為

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

2.LRU置換算法的硬件支持1)寄存圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況2)棧

圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況2)棧圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況4.7.3Clock置換算法

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

圖4-30簡(jiǎn)單Clock置換算法的流程和示例4.7.3Clock置換算法1.簡(jiǎn)單的Clock置換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)。2.改進(jìn)型Clock置換算法由訪問(wèn)位A和修

其執(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è)。

其執(zhí)行過(guò)程可分成以下三步：

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

請(qǐng)求分頁(yè)系統(tǒng)是目前最常用的一種存儲(chǔ)方式，但運(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í)間4.7.4請(qǐng)求分頁(yè)系統(tǒng)的性能分析請(qǐng)求分頁(yè)系統(tǒng)說(shuō)明：現(xiàn)代計(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í)間。由于CPU時(shí)間很快，所以（1）（3）可以不超過(guò)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。說(shuō)明：如果希望在缺頁(yè)時(shí)有效訪問(wèn)時(shí)間延長(zhǎng)不超過(guò)10%，則有0.11>0.1+24999.9*p則p<0.01/24999.9=0.0000004

結(jié)論：有效訪問(wèn)時(shí)間直接比例與缺頁(yè)率，改善請(qǐng)求分頁(yè)系統(tǒng)的性能，需要保持非常低的缺頁(yè)率，同時(shí)提高I/O的速度。如果希望在缺頁(yè)時(shí)有效訪問(wèn)時(shí)間延長(zhǎng)不超過(guò)10%，則有結(jié)論：有效2.抖動(dòng)——是這樣一種系統(tǒng)狀態(tài)，即系統(tǒng)花在頁(yè)面替換上的時(shí)間遠(yuǎn)遠(yuǎn)大于執(zhí)行進(jìn)程的時(shí)間。抖動(dòng)產(chǎn)生的原因：由于分配給進(jìn)程的頁(yè)面數(shù)大小少于進(jìn)程所需要的最低頁(yè)面數(shù)，導(dǎo)致出現(xiàn)接連不斷的缺頁(yè)中斷，引起抖動(dòng)。

CPU利用率與多道程序度的關(guān)系：多道程序度指在內(nèi)存中并發(fā)執(zhí)行的程序數(shù)目。兩者關(guān)系如下：在低度情況下，CPU利用率呈線性變化關(guān)系。隨著度的上升，CPU利用率也逐漸上升，最終上升到一個(gè)最大值，若在這種情況下，進(jìn)一步增加度，則系統(tǒng)發(fā)生抖動(dòng)，且CPU利用率將迅速惡化。結(jié)論：系統(tǒng)可以利用CPU利用率與多道程序度進(jìn)行比較的方法檢測(cè)抖動(dòng)，一旦發(fā)生抖動(dòng)，可以通過(guò)減少多道程序度的方法來(lái)消除。2.抖動(dòng)——是這樣一種系統(tǒng)狀態(tài)，即系統(tǒng)花在頁(yè)面替換上的時(shí)間遠(yuǎn)例：考慮一個(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%；例：考慮一個(gè)請(qǐng)求分頁(yè)系統(tǒng)，它采用全局置換策略和平均分配內(nèi)存塊答：（1）此時(shí)發(fā)生抖動(dòng)現(xiàn)象。增加多道程序度會(huì)進(jìn)一步增加缺頁(yè)率，使系統(tǒng)性能進(jìn)一步惡化，所以不能用增加多道程序度數(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的利用率。答：4.8請(qǐng)求分段存儲(chǔ)管理方式

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

1.段表機(jī)制段名段長(zhǎng)段的基址存取方式訪問(wèn)字段A修改位M存在位P增補(bǔ)位外存始址4.8請(qǐng)求分段存儲(chǔ)管理方式4.8.1請(qǐng)求分段中的硬件支

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

圖4-31請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程2.缺段中斷機(jī)構(gòu)圖4-31請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)3.地址變換機(jī)構(gòu)

圖4-32請(qǐng)求分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)圖4-32