L4(操作系統(tǒng)：存儲管理)

Fundamentals

of

Software

軟件技術(shù)基礎(chǔ)

自動化學(xué)院儀器科學(xué)與技術(shù)系徐生林Email:xusl@Tel:86919131(O)、

88915606(O)MP/p>

QQ群:40048788周一上午3-5：3教301周四下午6-8：3教211Part1:OperatingSystem

第4講:存儲管理

一、存儲器的存儲結(jié)構(gòu)Part1:OperatingSystem

Lecture4:MemoryManagement二、存儲管理的任務(wù)1、主存空間的分配作業(yè)進(jìn)入內(nèi)存后放在哪里，運(yùn)行進(jìn)程申請內(nèi)存如何分配2、地址映射程序中的邏輯地址如何轉(zhuǎn)換成內(nèi)存物理地址3、地址保護(hù)保護(hù)進(jìn)程的物理地址空間不被非法訪問4、內(nèi)存的“擴(kuò)充”“擴(kuò)充”物理內(nèi)存Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位1、地址靜態(tài)定位Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位(續(xù))2、地址與地址空間邏輯地址由處理機(jī)(CPU)分析指令時產(chǎn)生,就是指令中的地址,或者說是用戶程序空間中的地址物理地址內(nèi)存中的地址，通過對該地址的譯碼找到內(nèi)存單元邏輯地址空間用戶程序空間，所有邏輯地址的集合，地址范圍：0-max物理地址空間內(nèi)存物理地址的集合，大小由地址總線決定用戶程序處理邏輯地址，用戶都認(rèn)為他的程序在地址范圍0—max進(jìn)行運(yùn)行，這里的max為邏輯地址的最大值。Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位(續(xù))3、動態(tài)重定位程序中的地址是邏輯地址，該地址程序運(yùn)行時轉(zhuǎn)換為內(nèi)存物理地址的，程序可“搬家”用基地址寄存器或重定位寄存器實(shí)現(xiàn)動態(tài)重定位Part1:OperatingSystem

Lecture4:MemoryManagementPart1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(Memorymanagementscheme)1、單一連續(xù)分區(qū)在操作系統(tǒng)起動后，內(nèi)存被分成兩個區(qū)域，一個區(qū)域存放操作系統(tǒng)，另一區(qū)域存放用戶的程序,該方法只適用于單道程序的運(yùn)行優(yōu)點(diǎn)：實(shí)現(xiàn)簡單;操作系統(tǒng)開銷小缺點(diǎn)：只適用于單道程序，內(nèi)存利用率低Part1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))2、固定分區(qū)在操作系統(tǒng)起動后，內(nèi)存被分成一系列固定不變的分區(qū)(partition)，一次內(nèi)存分配以一塊分區(qū)為單位，進(jìn)程被裝入到一塊或連續(xù)的幾塊分區(qū)（進(jìn)程大于一塊分區(qū)）優(yōu)點(diǎn)：實(shí)現(xiàn)簡單;操作系統(tǒng)開銷小缺點(diǎn)：由于產(chǎn)生內(nèi)部碎片，內(nèi)存利用率低Part1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))2、固定分區(qū)(續(xù))內(nèi)部碎片Part1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))3、動態(tài)分區(qū)(Dynamicpartitioning)除了操作系統(tǒng)占用的內(nèi)存外，剛開始內(nèi)存是一片連續(xù)的空間（一塊分區(qū)），進(jìn)程裝入內(nèi)存或進(jìn)程申請空間，要求多少給多少，從而一點(diǎn)都不浪費(fèi)，申請一次，產(chǎn)生一塊分區(qū)。但經(jīng)過多次的申請和釋放，就出現(xiàn)一些很小的不連續(xù)的分區(qū)，這些小分區(qū)都暫時小于申請空間，也就產(chǎn)生了外部碎片（不是分區(qū)內(nèi)部的）優(yōu)點(diǎn)：無內(nèi)部碎片;比固定分區(qū)的內(nèi)存使用率高缺點(diǎn)：要通過中央處理機(jī)去把這些不連續(xù)的外部碎片連在一起，使得這些外部碎片變成一塊大的分區(qū)，增加了中央處理機(jī)的負(fù)擔(dān)。Part1:OperatingSystem

Lecture4:MemoryManagement動態(tài)分配空間的效果Part1:OperatingSystem

Lecture4:MemoryManagement動態(tài)分配空間的過程Part1:OperatingSystem

Lecture4:MemoryManagement動態(tài)分配空間的外碎片Part1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))3、動態(tài)分區(qū)(續(xù))空閑分區(qū)分配算法*首次適應(yīng)算法（FirstFit）分配首個符合要求的空閑區(qū)，如申請13K，第一行滿足要求最佳適應(yīng)算法（BestFit）分配符合要求的最小空閑區(qū)，如申請36K，第二行滿足要求最壞適應(yīng)算法（WorstFit）分配符合要求的最大空閑區(qū)，如申請36K，第三行滿足要求Part1:OperatingSystem

Lecture4:MemoryManagement緊湊或壓縮Part1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))4、分頁管理物理內(nèi)存被劃分成大小相等的塊，稱作物理幀（Frame）用戶程序邏輯空間被劃分成與物理塊一樣大小的頁（pages）分頁管理允許一個進(jìn)程在內(nèi)存的物理地址是不連續(xù)的，從而壓縮（compaction）不再需要，因此，外部碎片消失但是，內(nèi)部碎片出現(xiàn)（頁內(nèi)碎片），每一進(jìn)程的碎片平均是半頁（出現(xiàn)在進(jìn)程的最后一頁）此外，分頁的方法需要硬件的支持，如，頁表（包含頁號，頁內(nèi)偏移量）。每一進(jìn)程有自己的頁表，記錄物理內(nèi)存中那些塊是分配給它的。Part1:OperatingSystem

Lecture4:MemoryManagementAddressspace1p0p1p2p3p4p1p1p2Addressspace2p0p1Addressspace3p4p2p1p0p1p3p0p1p0p2PhysicalAddressLogicalViewPhysicalViewFigure4.5Memoryisdividedintofixed-sizepages分頁p4p2p1p0p1p3p0p1p0p2Part1:OperatingSystem

Lecture4:MemoryManagement

PhysicalAddressFramenumber:FPageoffset:D頁號:P頁內(nèi)偏移量:DLogicalAddress頁表20bits12bits4KpagesFigure4.6Translatelogicaladdressintophysicaladdressinpaging地址映射Part1:OperatingSystem

Lecture4:MemoryManagementPagePFrameFDPDLogicalAddressFDPhysicalAddressIDPDLBPageNumberRegisterBaseaddressinPT(ID)P>=L?Trap!?Yes+P+B……F……Pagetable(PT)01P-1Figure4.7MappingoflogicaladdresstophysicaladdressNoInternalfragmentationPart1:OperatingSystem

Lecture4:MemoryManagement

4.PagingPagePFrameFDPDLogicalAddressFDPhysicalAddressIDPDLBPageNumberRegisterBaseaddressinPT(ID)P>=L?Trap!?Yes+P+B……F……Pagetable(PT)01P-1Figure4.8AddressmappinginpagingWithFFTNo快速頁表

(FPT)PFN-flagA-flagPart1:OperatingSystem

Lecture4:MemoryManagement四、內(nèi)存管理方法(續(xù))5、分段管理（Segmentation）物理內(nèi)存與動態(tài)分區(qū)管理一樣（申請多少給多少）用戶程序邏輯空間被劃分成段（Segmentation）分段管理允許一個進(jìn)程在內(nèi)存的物理地址是不連續(xù)的。由于申請多少給多少，從而內(nèi)部碎片消失但經(jīng)過多次的申請和釋放，就出現(xiàn)一些很小的不連續(xù)的分區(qū)，這些小分區(qū)都暫時小于申請空間，也就產(chǎn)生了外部碎片，需要壓縮（compaction)此外，分段的方法需要硬件的支持，如，段表（包含段號，段內(nèi)偏移量）每一進(jìn)程有自己的段表，記錄物理內(nèi)存中那些分區(qū)是分配給她的Part1:OperatingSystem

Lecture4:MemoryManagementAddressspace1S0S1S2S3S0S1S2Addressspace2S2S0S1S3S0S1S2PhysicalAddressLogicalViewPhysicalViewFigure4.9Memoryisdividedintologicalsegments分段Part1:OperatingSystem

Lecture4:MemoryManagementPhysicalAddressSegmentnumber:S’Segmentoffset:D段號:S段內(nèi)偏移量:DLogicalAddressSegmentTableFigure4.10TranslatelogicaladdressintophysicaladdressinSegmentation地址映射Part1:OperatingSystem

Lecture4:MemoryManagement

SegmentSSegmentS’DSDLogicalAddressS’DPhysicalAddressIDSDLBSegmentNumberRegisterBaseaddressofST(ID)S>=L?Trap!?Yes+S+BFrametable(FT)01F-1Figure4.7MappingoflogicaladdresstophysicaladdressNoSBSL……s’s’L……D>=S’L?YesNoExternalfragmentationPart1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理1、虛擬存儲管理（Virtualmemorymanagement）前面的內(nèi)存管理方法（1）（5）都要求：在進(jìn)程運(yùn)行時，要求整個進(jìn)程的代碼和數(shù)據(jù)被一次裝入內(nèi)存。但是，在大多數(shù)情況下，一次運(yùn)行一個程序時，不會運(yùn)行進(jìn)程所有的代碼，如，你執(zhí)行你的程序不會調(diào)用所有的子程序。其次，由于存在時間局部性（一條指令被執(zhí)行，不久又可能被執(zhí)行，稱程序的局部性原理）和空間局部性（一個數(shù)據(jù)被訪問，不久又可能被訪問，稱數(shù)據(jù)的局部性原理），在進(jìn)程內(nèi)存的頁不是被訪問一次就不再被訪問了，而是可能經(jīng)常被訪問。如循環(huán)體?；谝陨咸攸c(diǎn)，考慮利用外存作為虛擬的內(nèi)存，只有需要執(zhí)行的代碼和數(shù)據(jù)才裝入內(nèi)存，否則存儲在比內(nèi)存大得多的外存上，這就是虛擬存儲管理技術(shù)的總體思想。Part1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理(續(xù))2、請求式分頁管理(DemandPaging)核心問題還是解決邏輯地址到物理地址的轉(zhuǎn)換，與分頁管理的不同在于請求分頁不需要一個進(jìn)程所有的頁一次裝入內(nèi)存由于不是進(jìn)程所有的頁調(diào)入內(nèi)存，在進(jìn)程執(zhí)行時，就會出現(xiàn)下一條要執(zhí)行的指令不在內(nèi)存的情況，此時，操作系統(tǒng)就請求把包括該指令的頁從磁盤調(diào)入內(nèi)存,故稱請求分頁管理。請看下圖，請求分頁與分頁的區(qū)別在于頁表，一個進(jìn)程的那些頁在內(nèi)存，那些也不在內(nèi)存。Part1:OperatingSystem

Lecture4:MemoryManagement地址映射與缺頁中斷Part1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理(續(xù))2、請求式分頁管理(續(xù))頁面替換算法（Pagereplacementalgorithms）由于內(nèi)存可能無空的頁，就要把其他進(jìn)程的頁換出到磁盤，得到的空頁給申請缺頁的進(jìn)程。替換算法的好壞主要體現(xiàn)在頁面缺頁率低先進(jìn)先出算法（Firstinfirstout–FIFOpagereplacement）依據(jù)：在內(nèi)存最長時間的也可能不再被用到，即程序執(zhí)行的時間上的局部性特點(diǎn)Part1:OperatingSystem

Lecture4:MemoryManagementFIFO頁面置換算法案例Part1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理(續(xù))2、請求式分頁管理(續(xù))對有些頁面替換算法，當(dāng)內(nèi)存的空頁增加時，缺頁率反而增加，該現(xiàn)象稱為Belady’現(xiàn)象。FIFO算法就是其中之一同學(xué)們可以對訪問頁的順序?yàn)椋?，2，3，4，1，2，5，1，2，3，4，5。在內(nèi)存總數(shù)分別為1、2、3、4、5、6頁的情況下，求FIFO算法的缺頁率。Part1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理(續(xù))2、請求式分頁管理(續(xù))最近最少使用換頁算法(Least-recently-unusedreplacement)選擇內(nèi)存中最長時間未被使用的頁換到磁盤。Unix采用之。依據(jù)：程序執(zhí)行的空間局部性特點(diǎn)Part1:OperatingSystem

Lecture4:MemoryManagementLRU頁面置換算法案例共訪問20頁面，12次缺頁P(yáng)art1:OperatingSystem

Lecture4:MemoryManagement四、虛擬存儲管理(續(xù))2、請求式分頁管理(續(xù))最佳頁面換頁算法(OptimalAlgorithm)選擇內(nèi)存中將在最長時間內(nèi)不會使用的頁換到磁盤。不幸的是，很難判斷最佳頁面3、抖動（thrashing

）過高缺頁率的現(xiàn)象，系統(tǒng)用于交換頁面的時間遠(yuǎn)遠(yuǎn)大于CPU執(zhí)行的時間影響缺頁率的主要因素分配的頁面數(shù)，一般的，moreframes?lesspagefaultsPart1:OperatingSystem