操作系統(tǒng)學(xué)位復(fù)習(xí)

第8章實(shí)存儲(chǔ)器管理技術(shù)2023/2/51物理主存主存為操作系統(tǒng)、各種系統(tǒng)程序和用戶程序所共享，任何程序的執(zhí)行最終都要從主存中存取指令和數(shù)據(jù)，都必須和主存打交道；現(xiàn)代操作系統(tǒng)可區(qū)分兩類主存：物理主存和邏輯主存；共享的基礎(chǔ)是物理主存；物理主存由0~(m-1)個(gè)物理地址組成；物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱為絕對(duì)地址或?qū)嵉刂?，處理器依?jù)絕對(duì)地址可以隨機(jī)存取存放在其內(nèi)的信息；物理地址的集合所對(duì)應(yīng)的空間組成了主存空間；而主存中的一個(gè)區(qū)域是物理地址集合的一個(gè)遞增整數(shù)序列子集（如n,n+1,…,n+m）所對(duì)應(yīng)的主存空間。2023/2/52邏輯主存如果直接以物理地址提交給用戶使用，對(duì)用戶來(lái)說(shuō)是十分困難的事情；采用了多道程序設(shè)計(jì)技術(shù)之后，多個(gè)用戶程序共享主存，由用戶自行分配主存更是不可能的事；因此，為支持多道程序運(yùn)行，方便用戶，系統(tǒng)必須為每個(gè)用戶提供0~(n-1)的一組邏輯地址，即提供一個(gè)虛擬地址空間；用戶的程序地址（指令地址或操作數(shù)地址）均為邏輯地址，或稱為相對(duì)地址；根據(jù)邏輯地址不能直接到主存中去存取信息；邏輯地址與物理地址之間有一定的映射關(guān)系，程序執(zhí)行時(shí)，必須將邏輯地址正確地轉(zhuǎn)換為物理地址，這就叫做地址映射。2023/2/53主存儲(chǔ)器的物理組織主存的結(jié)構(gòu)組織和實(shí)現(xiàn)方法，很大程度上決定了計(jì)算機(jī)系統(tǒng)的功能；主存的功能：存放內(nèi)核和用戶程序的指令和數(shù)據(jù)；每一項(xiàng)信息都存放在主存的特定位置上；信息在主存是按“位”存放的；編址；目前多數(shù)計(jì)算機(jī)以字節(jié)為單位進(jìn)行編址。2023/2/54計(jì)算機(jī)系統(tǒng)存儲(chǔ)器層次寄存器高速緩存主存儲(chǔ)器磁盤(pán)緩存固定磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)2023/2/55主存儲(chǔ)器管理功能（1）主存分配可以使多個(gè)程序同時(shí)駐留在主存中，以提高CPU利用率；保證系統(tǒng)的高性能，提高存儲(chǔ)利用率和提高主存的分配和釋放（回收）速度，以加快任務(wù)的執(zhí)行；地址轉(zhuǎn)換和重定位程序不必事先約定存放地址，可在執(zhí)行過(guò)程中移動(dòng)；可以運(yùn)行只裝入了一部分的程序，縮短程序的啟動(dòng)時(shí)間；研究和使用各種有效的地址轉(zhuǎn)換技術(shù)以及相應(yīng)的地址轉(zhuǎn)換機(jī)構(gòu)；2023/2/56主存儲(chǔ)器管理功能（2）存儲(chǔ)保護(hù)和主存共享研究如何保護(hù)各存儲(chǔ)區(qū)中信息不被破壞和偷竊；由于許多不同的任務(wù)可能要執(zhí)行同一個(gè)程序，進(jìn)程中多個(gè)合作進(jìn)程要訪問(wèn)相同的數(shù)據(jù)結(jié)構(gòu)，所以存儲(chǔ)保護(hù)機(jī)制要提供進(jìn)程對(duì)某些主存區(qū)共享的靈活性；存儲(chǔ)擴(kuò)充使用有效的存儲(chǔ)管理技術(shù)來(lái)實(shí)現(xiàn)邏輯上的擴(kuò)充—即虛擬存儲(chǔ)技術(shù)；運(yùn)行的程序應(yīng)不受主存大小的限制，理想情況下應(yīng)能運(yùn)行任意大小的程序。2023/2/57主存映射什么是地址映射？首先，在多用戶共享主存時(shí)，需要由系統(tǒng)分配主存；一般情況下，一個(gè)作業(yè)程序分配到的存儲(chǔ)空間和它的地址空間是不一致的；因此作業(yè)的相應(yīng)進(jìn)程在處理器上運(yùn)行時(shí)，所要訪問(wèn)的指令和數(shù)據(jù)的實(shí)際地址和地址空間中的地址是不同的；所以，處理器在執(zhí)行指令時(shí)，必須把邏輯地址轉(zhuǎn)換為絕對(duì)地址后，方能訪問(wèn)信息。地址映射方式編程或編譯時(shí)確定地址映射關(guān)系如果虛—實(shí)地址間的對(duì)應(yīng)關(guān)系是在程序編寫(xiě)或者程序編譯時(shí)實(shí)現(xiàn)的，則結(jié)果為一個(gè)不能浮動(dòng)的程序模塊，它必須被放在主存某一確定的地址中，而且永不會(huì)改變，因?yàn)樗娜康刂范际侵鞔娴刂罚谶@種情況下，把這樣一個(gè)程序裝入主存，就必須在申請(qǐng)主存時(shí)，具體地提出申請(qǐng)的主存容量和主存地址，因此主存分配程序在分配時(shí)將沒(méi)有什么活動(dòng)余地。靜態(tài)地址映射動(dòng)態(tài)地址映射2023/2/58程序的邏輯組織傳統(tǒng)計(jì)算機(jī)的主存儲(chǔ)器是一個(gè)一維的存儲(chǔ)空間，它的地址從零開(kāi)始到主存上界順序編號(hào)，這是存儲(chǔ)器的組織方式；程序一般有兩種組織方式程序的地址空間是一維線性的所有的程序和數(shù)據(jù)經(jīng)編譯、連接后成為一個(gè)連續(xù)的地址空間；程序的地址空間是二維段式結(jié)構(gòu)將程序分成若干模塊或過(guò)程，并把可修改的數(shù)據(jù)和不可修改的數(shù)據(jù)分開(kāi)，一個(gè)程序可由代碼段、數(shù)據(jù)段、棧段、特別分段等組成，編譯時(shí)就明確加以區(qū)分，經(jīng)編譯、連接后成為可執(zhí)行代碼，系統(tǒng)有指向各分段的指針，在程序執(zhí)行時(shí)可方便地實(shí)現(xiàn)地址變換。把地址空間邏輯上劃分成對(duì)應(yīng)的程序段和數(shù)據(jù)段的優(yōu)點(diǎn)：首先，它符合人們的習(xí)慣；其次，只要增加少量開(kāi)銷就能對(duì)不同的段賦予不同的保護(hù)級(jí)別；另外，還可實(shí)現(xiàn)動(dòng)態(tài)連接，即對(duì)分段單獨(dú)進(jìn)行編譯，只有當(dāng)某一段要調(diào)用另一分段時(shí)，才由系統(tǒng)在運(yùn)行時(shí)動(dòng)態(tài)連接。2023/2/59固定分區(qū)存儲(chǔ)管理（1）把主存分成若干個(gè)固定大小的存儲(chǔ)區(qū)（又稱存儲(chǔ)塊），每個(gè)存儲(chǔ)區(qū)分給某一個(gè)作業(yè)使用，直到該作業(yè)完成后才把該存儲(chǔ)區(qū)歸還系統(tǒng)；分單道作業(yè)和多道作業(yè)兩種情況；單用戶、單道作業(yè)情況（教材圖8.2）多道作業(yè)情況（教材圖8.3）操作系統(tǒng)區(qū)、用戶使用的分區(qū)主存中分區(qū)的區(qū)數(shù)是固定不變的，每區(qū)的大小也是固定不變的分給每個(gè)作業(yè)一塊大于或等于作業(yè)大小的主存分區(qū)，不允許兩個(gè)作業(yè)同時(shí)放于同一個(gè)分區(qū)中；問(wèn)題：分區(qū)中常有未用的、剩下的空閑部分，即存儲(chǔ)碎片，降低了主存的利用率；存儲(chǔ)分塊表：主存分區(qū)情況說(shuō)明信息，存儲(chǔ)區(qū)的使用狀況信息，包括大小、位置和狀態(tài)三項(xiàng)信息。2023/2/510固定分區(qū)存儲(chǔ)管理（2）操作系統(tǒng)區(qū)作業(yè)i的程序、數(shù)據(jù)等界限地址柵欄寄存器作業(yè)2作業(yè)1界限地址+邏輯地址裝入程序采用靜態(tài)重定位的單用戶連續(xù)存儲(chǔ)管理操作系統(tǒng)區(qū)用戶區(qū)界限地址定位寄存器邏輯地址CPU絕對(duì)地址采用動(dòng)態(tài)重定位的單用戶連續(xù)存儲(chǔ)管理2023/2/511固定分區(qū)存儲(chǔ)管理（3）存儲(chǔ)分塊表大?。褐赋鲈摯鎯?chǔ)塊的大小，以字節(jié)為單位；位置：指出該存儲(chǔ)塊在主存中的起始地址；狀態(tài)：表明該存儲(chǔ)塊是否已被使用。存儲(chǔ)保護(hù)功能一對(duì)“界地址寄存器”，如果處理器要訪問(wèn)主存某單元時(shí)，系統(tǒng)硬件自動(dòng)將該單元地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷此次訪問(wèn)是否合法；優(yōu)點(diǎn)：簡(jiǎn)單，要求的硬件支持只是一對(duì)界地址寄存器，軟件算法簡(jiǎn)單；缺點(diǎn)：主存利用率不高。2023/2/512固定分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換（1）固定分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換可以采用靜態(tài)定位方式，裝入程序在進(jìn)行地址轉(zhuǎn)換時(shí)檢查其絕對(duì)地址是否在指定的分區(qū)中，若是，則可把程序裝入，否則不能裝入，且應(yīng)歸還所分得的存儲(chǔ)區(qū)域；固定分區(qū)方式的主存去配很簡(jiǎn)單，只需將主存分配表中相應(yīng)分區(qū)的占用標(biāo)志位置成“0”即可。2023/2/513固定分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換（2）固定分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換也可以采用動(dòng)態(tài)定位方式，如下圖示；系統(tǒng)專門(mén)設(shè)置一對(duì)地址寄存器—上限/下限寄存器；當(dāng)一個(gè)進(jìn)程占有CPU執(zhí)行時(shí)，操作系統(tǒng)就從主存分配表中取出相應(yīng)的地址占有上限/下限寄存器；硬件的地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)下限寄存器中保存的基地址B與邏輯地址得到絕對(duì)地址；硬件的地址轉(zhuǎn)換機(jī)構(gòu)同時(shí)把絕對(duì)地址和上限/下限寄存器中保存的相應(yīng)地址進(jìn)行比較，而實(shí)現(xiàn)存儲(chǔ)保護(hù)。B下限寄存器邏輯地址CPU絕對(duì)地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器<B+L2越界中斷用戶分區(qū)1用戶分區(qū)2用戶分區(qū)32023/2/514可變分區(qū)存儲(chǔ)管理概念所謂可變分區(qū)，是指主存事先并未劃分成一塊塊分區(qū)，而是在作業(yè)進(jìn)入主存時(shí)，按該作業(yè)的大小建立分區(qū)，分給作業(yè)使用；特點(diǎn)：分區(qū)個(gè)數(shù)是可變的，每個(gè)分區(qū)的大小也是不固定的；主存中分布著個(gè)數(shù)和大小都是變化的空閑分區(qū)或碎片，這些空閑分區(qū)有些可能相當(dāng)大，而有些則相當(dāng)小。2023/2/515數(shù)據(jù)基的組織方法（1）存儲(chǔ)分塊表（教材圖8.5）這種存儲(chǔ)分塊表存在兩個(gè)缺點(diǎn)：由于分區(qū)個(gè)數(shù)是變化的，所以表長(zhǎng)不好確定，造成表格管理上的困難，若給該表留的空間不足，又無(wú)法登記各分區(qū)的情況，若留的空間過(guò)大，造成浪費(fèi)；分配主存時(shí)，為查找一塊合適的空閑分區(qū)所需掃描的表目增加了，查找速度變慢了；分開(kāi)設(shè)置兩個(gè)存儲(chǔ)管理表（教材圖8.6）用已使用分區(qū)表（UBT）和空閑分區(qū)表（FBT）分別登記和管理系統(tǒng)中的已分分區(qū)和空閑分區(qū)；減少存儲(chǔ)分配和釋放時(shí)查找表格的長(zhǎng)度，提高查找速度；2023/2/516數(shù)據(jù)基的組織方法（2）空閑存儲(chǔ)塊鏈（教材圖8.7）使用鏈指針把所有的空閑分區(qū)鏈結(jié)在一起，構(gòu)成一條空閑存儲(chǔ)塊鏈；實(shí)現(xiàn)方法：把每個(gè)空閑存儲(chǔ)塊的起始若干個(gè)字節(jié)分成兩部分，前一部分作為鏈指針，指向下一空閑存儲(chǔ)塊的起始地址，后一部分指出本空閑存儲(chǔ)塊的大小，用一固定單元作為空閑存儲(chǔ)鏈的頭指針用以指出該鏈中的第一塊空閑存儲(chǔ)塊的起始地址，最后一塊空閑存儲(chǔ)塊的鏈指針中放著鏈尾標(biāo)志；這種方法使得數(shù)據(jù)基的管理和維護(hù)比較簡(jiǎn)單。2023/2/517存儲(chǔ)分配算法最佳適應(yīng)法從所有未分配的分區(qū)中挑選一個(gè)最接近作業(yè)尺寸且大于或等于作業(yè)大小的分區(qū)分給要求的作業(yè)；從而使分區(qū)內(nèi)未用部分即碎片最少；最先適應(yīng)法按分區(qū)序號(hào)從存儲(chǔ)分塊表的第一個(gè)表目起查找該表，把最先找到的且大于或等于作業(yè)大小的未分配分區(qū)分給要求的作業(yè)；可以縮短查找時(shí)間；最壞適應(yīng)法從所有未分配的分區(qū)中挑選最大的且大于或等于作業(yè)大小的分區(qū)分給要求的作業(yè)；可用于可變分區(qū)分配技術(shù)中。2023/2/518三種放置策略的說(shuō)明作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存(a)最先適應(yīng)法(b)最佳適應(yīng)法(c)最壞適應(yīng)法2023/2/519各種存儲(chǔ)分配算法的分析與比較最佳適應(yīng)法：盡量多保留大的分區(qū)，使被選中分區(qū)剩下盡可能小的未用碎片；使系統(tǒng)中產(chǎn)生了許多小得無(wú)法再用的碎片；最先適應(yīng)法：盡可能地縮短了存儲(chǔ)分配時(shí)間；對(duì)空閑塊的管理采取不同的辦法：表格法、空閑存儲(chǔ)塊鏈法、位圖法；最壞適應(yīng)法：保證分配后剩下的分區(qū)足夠大，以便滿足后續(xù)要求。2023/2/520碎片問(wèn)題和存儲(chǔ)器的緊縮由于各作業(yè)請(qǐng)求和釋放主存塊的結(jié)果，產(chǎn)生很多小的碎片，碎片的存在降低了多道的程度，造成了主存空間的大量浪費(fèi)；解決碎片問(wèn)題：把程序分成幾部分裝入不同的分區(qū)中去，改變一直把程序作為一個(gè)連續(xù)的整體在主存中存放的要求；改善了碎片問(wèn)題，但卻增加了程度管理和執(zhí)行的復(fù)雜性；把小碎片集中起來(lái)使之成為一個(gè)大分區(qū)；移動(dòng)各用戶分區(qū)中的程序，使它們集中于主存的一端，使碎片集中于另一端，從而連成一個(gè)完整的大分區(qū)，即存儲(chǔ)器的“緊縮”或“澄清”。2023/2/521動(dòng)態(tài)重定位動(dòng)態(tài)重定位：是指程序的重定位時(shí)機(jī)不是在程序執(zhí)行前進(jìn)行，而是在程序執(zhí)行過(guò)程中才進(jìn)行地址轉(zhuǎn)換，更確切地說(shuō)是在每次訪問(wèn)主存單元前才進(jìn)行地址轉(zhuǎn)換（教材圖8.9）；重定位過(guò)程：首先將用戶按相對(duì)地址編址的目標(biāo)程序原封不動(dòng)地裝入主存中分給該用戶使用的分區(qū)中；當(dāng)該用戶程序被調(diào)度到處理器上執(zhí)行時(shí)，操作系統(tǒng)自動(dòng)將該用戶作業(yè)的起址由作業(yè)表中取出，并將分區(qū)起始地址減去用戶目標(biāo)程序的相對(duì)基地址，然后將其減得值裝入定位寄存器中；當(dāng)處理器要訪問(wèn)主存時(shí)，地址轉(zhuǎn)換硬件自動(dòng)將程序中的相對(duì)地址與定位寄存器中的內(nèi)容相加，并按相加的和作為主存絕對(duì)地址去訪問(wèn)數(shù)據(jù)。采用動(dòng)態(tài)重定位后，由于目標(biāo)程序裝入主存后不需要修改地址指針及所有與地址有關(guān)的項(xiàng)，因而程序可在主存中隨意浮動(dòng)而不影響其正確執(zhí)行，從而可以方便地進(jìn)行存儲(chǔ)器緊縮，較好地解決了碎片問(wèn)題。2023/2/522動(dòng)態(tài)重定位的硬件支持及軟件算法硬件支持：定位寄存器、加法器進(jìn)行存儲(chǔ)器緊縮的兩種時(shí)機(jī)：在某個(gè)分區(qū)被釋放后立即進(jìn)行緊縮，此時(shí)系統(tǒng)中總是只有一個(gè)連續(xù)的空閑分區(qū)為無(wú)碎片；當(dāng)“請(qǐng)求分配模塊”找不到足夠大的空閑分區(qū)給用戶時(shí)再進(jìn)行緊縮，這樣緊縮的次數(shù)要少些，但表格管理復(fù)雜了（教材圖8.10）。動(dòng)態(tài)重定位技術(shù)的優(yōu)點(diǎn)：可以消除碎片，能有效利用主存空間，提高多道程序系統(tǒng)的多道程度，從而也提高了對(duì)處理器和外設(shè)的利用率；缺點(diǎn)：首先，需要?jiǎng)討B(tài)重定位硬件機(jī)構(gòu)支持，提高了計(jì)算機(jī)成本，減低了速度，其次，緊縮工作要花費(fèi)一定的機(jī)時(shí)。2023/2/523多重分區(qū)/多對(duì)界地址管理單對(duì)界地址管理技術(shù)：每個(gè)用戶只占據(jù)主存的一個(gè)分區(qū)，存儲(chǔ)保護(hù)只需使用一對(duì)界地址寄存器；弊?。菏紫?，解決碎片問(wèn)題時(shí)，移動(dòng)程序進(jìn)行存儲(chǔ)器緊縮時(shí)需要硬件支持；其次，不便于在進(jìn)程之間共享數(shù)據(jù)。多對(duì)界地址管理技術(shù)：系統(tǒng)中設(shè)置多對(duì)界地址寄存器，并且在為每個(gè)作業(yè)或進(jìn)程分配主存時(shí)，可按界地址寄存器對(duì)的個(gè)數(shù)為其分配多個(gè)不相鄰接的空閑分區(qū)；該技術(shù)既可以改善碎片情況，又便于共享；但是，在實(shí)存管理技術(shù)中，多重分區(qū)的多重程度不宜過(guò)多，否則會(huì)增加管理的復(fù)雜性。2023/2/524簡(jiǎn)單分頁(yè)（1）前述固定分區(qū)和可變分區(qū)存儲(chǔ)技術(shù)存在著一定的缺點(diǎn)；分頁(yè)技術(shù)思想的由來(lái)；分頁(yè)存儲(chǔ)管理技術(shù)中的基本作法；等分主存；（頁(yè)架）用戶邏輯地址空間的分頁(yè)；（頁(yè)）邏輯地址的表示。（數(shù)對(duì)（p,d））主存分配原則；分頁(yè)情況下，系統(tǒng)以頁(yè)架為單位把主存分給進(jìn)程，分給一個(gè)進(jìn)程的各頁(yè)架不一定是相鄰和連續(xù)的；頁(yè)表—指出每個(gè)進(jìn)程的各頁(yè)放在主存的哪些頁(yè)架中；分頁(yè)系統(tǒng)中的地址結(jié)構(gòu)—分為兩部分；頁(yè)面尺寸應(yīng)是2的冪—可以省去除法運(yùn)算，拆分地址場(chǎng)中的數(shù)即可。（如p159例）2023/2/525簡(jiǎn)單分頁(yè)（2）地址轉(zhuǎn)換過(guò)程：首先將邏輯地址左邊表示頁(yè)號(hào)部分的頁(yè)號(hào)抽取出來(lái)；以頁(yè)號(hào)作為索引查找該進(jìn)程頁(yè)表，找出該頁(yè)存放的主存頁(yè)架號(hào)；用此頁(yè)架號(hào)（二進(jìn)制形式）取代邏輯地址的左邊部分，并與右邊的頁(yè)內(nèi)地址合并成相應(yīng)的物理地址去訪問(wèn)主存。簡(jiǎn)單分頁(yè)方法的優(yōu)點(diǎn)：它基本沒(méi)有頁(yè)內(nèi)碎片，只是在每個(gè)進(jìn)程的最后一頁(yè)中，會(huì)有頁(yè)內(nèi)碎片；也不會(huì)有小到不可再用的頁(yè)外碎片，主存的利用率高；不管采用哪種數(shù)據(jù)結(jié)構(gòu)（空閑頁(yè)架表、位圖、空閑頁(yè)架鏈表等），分配和釋放存儲(chǔ)都很快；管理簡(jiǎn)單（類似于固定分區(qū)的情況）。2023/2/526頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)頁(yè)表始址頁(yè)表長(zhǎng)度作業(yè)名…A頁(yè)表始址…xxxxxx頁(yè)表長(zhǎng)度…3作業(yè)表塊號(hào)比較頁(yè)號(hào)頁(yè)內(nèi)地址塊號(hào)頁(yè)內(nèi)地址頁(yè)表頁(yè)表控制寄存器絕對(duì)地址邏輯地址地址越界2023/2/527程序的分段結(jié)構(gòu)子程序段X數(shù)組段A┇call[X]∣<E<(調(diào)用X段的入口E)┇call[Y]∣<F<(調(diào)用Y段的入口F)┇load1,[A]∣<G<(調(diào)用數(shù)組段A[G])┇主程序段┇E：┅┅┅┅┅┅┇┇F：┅┅┅┅┅┅┇子程序段Y┇G：┅┅┅┅┅┅┇┇┇┇工作區(qū)段2023/2/528簡(jiǎn)單分段（1）為什么需要按段分配主存？事先將用戶邏輯地址空間連接成一維線性地址空間，既費(fèi)時(shí)又不便于作業(yè)的執(zhí)行，尤其不便于共享；因此，人們希望按照程序模塊來(lái)劃分段，并按這些段來(lái)分配主存；段，就是一組邏輯信息的集合，如子程序、數(shù)組和數(shù)據(jù)區(qū)等。分段存儲(chǔ)管理的基本概念進(jìn)程的邏輯地址空間（二維的，用段名和段內(nèi)地址兩個(gè)成分來(lái)描述）程序的地址結(jié)構(gòu)主存分配段表（每個(gè)進(jìn)程一個(gè)段表，用來(lái)指出進(jìn)程的某段放在主存中的何處，以及該段的長(zhǎng)度等信息）段的地址轉(zhuǎn)換（把邏輯地址左邊段號(hào)部分提取出來(lái)，作為索引，查找進(jìn)程的段表，將段內(nèi)地址與段的長(zhǎng)度比較，如果大于段的長(zhǎng)度，則引起非法訪問(wèn)中斷，即越界訪問(wèn)，如果訪問(wèn)合法，就將段的起始地址與段內(nèi)地址相加，就得到所要訪問(wèn)的物理地址。）2023/2/529分段式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)段控制寄存器段表始址段表長(zhǎng)度段號(hào)s位移d段長(zhǎng)基址物理地址越界?段表2023/2/530簡(jiǎn)單分段（2）簡(jiǎn)單分段的優(yōu)點(diǎn)是沒(méi)有段內(nèi)碎片，只有外部碎片；簡(jiǎn)單分段也是基于多重分區(qū)技術(shù)的進(jìn)一步發(fā)展而來(lái)的；簡(jiǎn)單分段對(duì)用戶是可見(jiàn)的，而且分段需要用戶提供支持，用戶也需要知道系統(tǒng)的最大段長(zhǎng)度限制；當(dāng)進(jìn)程被交換出主存時(shí)，它的頁(yè)表或段表也需隨進(jìn)程一起撤出主存。2023/2/531分段和分頁(yè)的比較分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見(jiàn)，段長(zhǎng)可根據(jù)用戶需要來(lái)規(guī)定，段起始地址可以從任何主存地址開(kāi)始；在分段方式中，源程序(段號(hào)，段內(nèi)位移)經(jīng)連結(jié)裝配后仍保持二維結(jié)構(gòu)。分頁(yè)是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無(wú)關(guān)，用戶不可見(jiàn)，頁(yè)長(zhǎng)由系統(tǒng)確定，頁(yè)面只能以頁(yè)大小的整倍數(shù)地址開(kāi)始。在分頁(yè)方式中，源程序(頁(yè)號(hào)，頁(yè)內(nèi)位移)經(jīng)連結(jié)裝配后變成了一維結(jié)構(gòu)。2023/2/532單項(xiàng)選擇題1.設(shè)內(nèi)存的分配情況如下圖所示，若要申請(qǐng)一塊40K字節(jié)的內(nèi)存空間，若采用最佳適應(yīng)算法，則所得到的分區(qū)首址為（c）。A.100KB.190KC.330KD.410K占用占用占用占用0100K180K190K280K330K390K410K512K—12023/2/5332.在可變式分區(qū)存儲(chǔ)管理中的拼接技術(shù)可以（a）。A.集中空閑區(qū)B.增加主存容量C.縮短訪問(wèn)周期D.加速地址轉(zhuǎn)換3.分區(qū)管理中采用“最佳適應(yīng)”分配算法時(shí)，宜把空閑區(qū)按（a）次序登記在空閑區(qū)表中。A.長(zhǎng)度遞增B.長(zhǎng)度遞減C.地址遞增D.地址遞減4.在固定分區(qū)分配中，每個(gè)分區(qū)的大小是（c）A.相同B.隨作業(yè)長(zhǎng)度變化C.可以不同但預(yù)先固定D.可以不同但根據(jù)作業(yè)長(zhǎng)度固定5.把作業(yè)地址空間中使用的邏輯地址變成內(nèi)存中物理地址的過(guò)程稱為（a）A.重定位B.物理化C.邏輯化D.加載6.在分頁(yè)系統(tǒng)環(huán)境下，程序員編制的程序，其地址空間是連續(xù)的，分頁(yè)是由（d）完成的。A.程序員B.編譯地址C.用戶D.系統(tǒng)7.如果一個(gè)程序?yàn)槎鄠€(gè)進(jìn)程所共享，那么該程序的代碼在執(zhí)行的過(guò)程中不能被修改，即程序應(yīng)該是（b）。A.可執(zhí)行碼B.可重入碼C.可改變碼D.可再現(xiàn)碼2023/2/534第9章虛擬存儲(chǔ)管理2023/2/535虛擬存儲(chǔ)系統(tǒng)的基本概念實(shí)存管理技術(shù)特點(diǎn)在作業(yè)運(yùn)行時(shí)，整個(gè)作業(yè)的邏輯地址空間必須全部裝入主存；當(dāng)作業(yè)尺寸大于主存可用空間時(shí)，該作業(yè)就無(wú)法運(yùn)行。虛擬存儲(chǔ)器：一種實(shí)際上并不以物理形式存在的虛假的存儲(chǔ)器；把被運(yùn)行進(jìn)程訪問(wèn)的地址同主存的物理地址區(qū)別開(kāi)來(lái)；一個(gè)程序被編譯連接后產(chǎn)生目標(biāo)程序，該目標(biāo)程序所限定的地址的集合稱為邏輯地址空間，目標(biāo)程序中指令和數(shù)據(jù)放置的位置稱相對(duì)地址或邏輯地址；而CPU能直接訪問(wèn)的主存稱為物理地址空間或?qū)嵈娴刂房臻g；虛擬地址：運(yùn)行進(jìn)程訪問(wèn)的地址；實(shí)地址：處理器可直接訪問(wèn)的主存地址；虛擬地址空間：運(yùn)行進(jìn)程可以訪問(wèn)的虛地址的集合；實(shí)地址空間：計(jì)算機(jī)的主存；由動(dòng)態(tài)地址映象機(jī)構(gòu)來(lái)完成虛地址到實(shí)地址的轉(zhuǎn)換；虛實(shí)地址的區(qū)分，為使進(jìn)程的虛擬地址空間大于主存實(shí)地址空間創(chuàng)造了條件，也為作業(yè)大小可大于主存空間創(chuàng)造了條件。2023/2/536虛存管理技術(shù)在虛擬存儲(chǔ)系統(tǒng)中，用戶認(rèn)為機(jī)器具有無(wú)窮大的存儲(chǔ)空間，并且只有這一個(gè)用戶在使用機(jī)器；用戶只使用了物理主存的很少部分；原因：操作系統(tǒng)內(nèi)核只把進(jìn)程當(dāng)前要用的部分放在主存中，不僅能減少進(jìn)程啟動(dòng)和滾進(jìn)滾出的開(kāi)銷，而且主存中也可以同時(shí)容納大量的進(jìn)程，提高了系統(tǒng)多道程度和并行性；代價(jià)：主存管理要為地址轉(zhuǎn)換表和其他一些數(shù)據(jù)結(jié)構(gòu)付出額外的主存開(kāi)銷；地址轉(zhuǎn)換增加了每條指令的執(zhí)行時(shí)間。常用虛存管理技術(shù)分頁(yè)技術(shù)（paging）分段技術(shù)（segmentation）分段加分頁(yè)技術(shù)（segmentationwithpaging）2023/2/537分頁(yè)系統(tǒng)中的地址映象技術(shù)（1）分頁(yè)系統(tǒng)主要目的：讓程序能在它的虛擬地址空間中運(yùn)行并實(shí)現(xiàn)由虛擬地址到主存物理地址的轉(zhuǎn)換；幾種地址轉(zhuǎn)換方法直接映象的頁(yè)地址轉(zhuǎn)換多級(jí)頁(yè)表的地址轉(zhuǎn)換反向頁(yè)表的地址轉(zhuǎn)換快表的地址轉(zhuǎn)換2023/2/538分頁(yè)系統(tǒng)中的地址映象技術(shù)（2）

——直接映象的頁(yè)地址轉(zhuǎn)換實(shí)現(xiàn)過(guò)程（教材圖9.1）當(dāng)進(jìn)程被調(diào)度到處理器上運(yùn)行時(shí)，操作系統(tǒng)自動(dòng)將該進(jìn)程的頁(yè)表起始地址裝入頁(yè)表地址寄存器中；當(dāng)該進(jìn)程要訪問(wèn)某個(gè)虛地址時(shí)，分頁(yè)的地址映象硬件自動(dòng)按頁(yè)面大小將地址場(chǎng)從某位起截成頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分；以頁(yè)號(hào)為索引查找頁(yè)表（查找工作由硬件自動(dòng)進(jìn)行），得到頁(yè)架號(hào)，進(jìn)而得到實(shí)際主存的絕對(duì)地址。該映象技術(shù)對(duì)系統(tǒng)效能的影響影響了處理器執(zhí)行指令的速度，使速度降低為原來(lái)的一半；原因：CPU至少要訪問(wèn)兩次主存才能存取到所要數(shù)據(jù)，第一次查頁(yè)表以找出對(duì)應(yīng)的頁(yè)架號(hào)，第二次真正訪問(wèn)所需數(shù)據(jù)。2023/2/539分頁(yè)系統(tǒng)中的地址映象技術(shù)（3）

——多級(jí)頁(yè)表的地址轉(zhuǎn)換因?yàn)榇箜?yè)表不能全放在主存中，所以對(duì)頁(yè)表本身也采取分頁(yè)措施，把頁(yè)表本身按固定大小分成一個(gè)個(gè)頁(yè)面；教材圖9.2；通過(guò)二級(jí)頁(yè)表的地址映射訪問(wèn)主存存取數(shù)據(jù)需要三次訪問(wèn)主存，所需時(shí)間是原來(lái)的三倍；一次頁(yè)目錄一次頁(yè)表數(shù)據(jù)所在的物理地址2023/2/540分頁(yè)系統(tǒng)中的地址映象技術(shù)（4）

——反向頁(yè)表的地址轉(zhuǎn)換教材圖9.3；實(shí)現(xiàn)過(guò)程當(dāng)給出進(jìn)程的虛地址后，存儲(chǔ)管理單元通過(guò)一個(gè)哈希定位表數(shù)據(jù)結(jié)構(gòu)，把虛頁(yè)號(hào)經(jīng)哈希函數(shù)轉(zhuǎn)換為一個(gè)哈希值；以該哈希值為索引，它指向反向頁(yè)表中的一個(gè)表目；由這個(gè)表目中的虛頁(yè)號(hào)得到相應(yīng)的頁(yè)架號(hào)，再與偏移量拼接成物理地址，訪問(wèn)主存。2023/2/541分頁(yè)系統(tǒng)中的地址映象技術(shù)（5）

——快表的地址轉(zhuǎn)換（1）把一部分常用頁(yè)表表目放入高速緩沖中，通過(guò)快表進(jìn)行地址映射，快表中只包含一些最近使用的頁(yè)表的表目；快表的訪問(wèn)速度比主存的訪問(wèn)速度高一個(gè)數(shù)量級(jí)；快表的表目中包含：虛頁(yè)號(hào)以及該虛地址屬于哪個(gè)進(jìn)程、物理頁(yè)架號(hào)、頁(yè)面保護(hù)權(quán)限等。2023/2/542分頁(yè)系統(tǒng)中的地址映象技術(shù)（5）

——快表的地址轉(zhuǎn)換（2）教材圖9.4；當(dāng)運(yùn)行進(jìn)程要訪問(wèn)虛地址v，于是硬件將地址v截成頁(yè)號(hào)p和頁(yè)內(nèi)地址d；地址轉(zhuǎn)換機(jī)構(gòu)首先以頁(yè)號(hào)p和快表中各表目同時(shí)進(jìn)行比較，以便確定該頁(yè)是否在快表中；若在其中，則快表即送出相應(yīng)的頁(yè)架號(hào)與頁(yè)內(nèi)地址一起拼接成絕對(duì)地址，并按此地址訪問(wèn)主存；若該頁(yè)不在快表中，則使用直接映象方法查找進(jìn)程的頁(yè)表，找出其頁(yè)架號(hào)p’與頁(yè)內(nèi)地址拼接成絕對(duì)地址，并訪問(wèn)主存；同時(shí)將該頁(yè)的頁(yè)號(hào)及對(duì)應(yīng)的頁(yè)架號(hào)一起送入快表的空閑表目中去；若無(wú)空表目，通常把最先裝入的那個(gè)頁(yè)的有關(guān)信息淘汰掉，騰出表目位置。實(shí)際上，直接映象和快表同時(shí)進(jìn)行，當(dāng)快表成功，就自動(dòng)停止直接映象工作。2023/2/543缺頁(yè)中斷處理流程查快表有登記無(wú)登記查頁(yè)表登記入快表發(fā)缺頁(yè)中斷在主存在輔存形成絕對(duì)地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和主存分配表裝入所需頁(yè)面主存有空閑塊保護(hù)現(xiàn)場(chǎng)有選擇調(diào)出頁(yè)面該頁(yè)是否修改未修改已修改把該頁(yè)寫(xiě)回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無(wú)2023/2/544分段概述虛擬分段的優(yōu)點(diǎn)分段技術(shù)簡(jiǎn)化了對(duì)可以任意增長(zhǎng)和收縮的數(shù)據(jù)段的管理；分別編譯的段的連接十分簡(jiǎn)單；如果一個(gè)段的過(guò)程被修改并重新編譯，不會(huì)引起其他段修改，因?yàn)檫@些修改只涉及該段自己的地址空間；分段機(jī)制便于在進(jìn)程間共享過(guò)程和數(shù)據(jù)，只要把這些過(guò)程和數(shù)據(jù)，如同共享庫(kù)一樣，放在分別的段中，通過(guò)段表映射進(jìn)行共享；段是程序員可見(jiàn)的邏輯上的實(shí)體，如過(guò)程，數(shù)組和堆棧等，對(duì)不同段，程序員可以安排不同的保護(hù)類型。虛擬分段的缺點(diǎn)段大小不一致，段外碎片使存儲(chǔ)利用率下降。2023/2/545分段的實(shí)現(xiàn)每個(gè)虛擬地址由一個(gè)數(shù)對(duì)（段號(hào)，段內(nèi)偏移量）兩部分組成，每個(gè)進(jìn)程一個(gè)段表；每個(gè)段表的表目：段的起始地址段長(zhǎng)有效位修改位保護(hù)和共享信息實(shí)現(xiàn)過(guò)程（教材圖9.5）：當(dāng)進(jìn)程訪問(wèn)某虛擬地址（s,w）時(shí)，內(nèi)核將段表地址寄存器中內(nèi)容b與段號(hào)同段表表目長(zhǎng)的乘積相加后，得到該段的表目入口地址；由此表目中查得段s在主存中的起始地址s’；再將s’與段內(nèi)地址w相加，而得到欲訪問(wèn)單元的主存物理地址，并進(jìn)行訪問(wèn)。2023/2/546段頁(yè)式存儲(chǔ)管理的基本概念等分主存把整個(gè)主存分成大小相等的存儲(chǔ)塊，即頁(yè)架；進(jìn)程的地址空間采用分段的方式按程序的自然邏輯關(guān)系把進(jìn)程的地址空間分成若干段，每一段有自己的外部段名和內(nèi)部段號(hào)；進(jìn)程的每一段又采用分頁(yè)方法按主存頁(yè)架大小把每一段劃分成若干頁(yè)，每段從零開(kāi)始為自己段的各頁(yè)依次編頁(yè)號(hào)；邏輯地址結(jié)構(gòu)一個(gè)邏輯地址用三個(gè)參數(shù)表示，段號(hào)s，頁(yè)號(hào)p，頁(yè)內(nèi)地址偏移量d，記為v=(s,p,d)；主存分配主存以頁(yè)架為單位分配給每個(gè)進(jìn)程；段表、頁(yè)表、段表地址寄存器2023/2/547段頁(yè)式存儲(chǔ)管理中的地址轉(zhuǎn)換若運(yùn)行進(jìn)程訪問(wèn)虛地址v=(s,p,d)的地址轉(zhuǎn)換過(guò)程（教材圖9.6）：地址轉(zhuǎn)換硬件將段表地址寄存器內(nèi)容與指令地址場(chǎng)中的段號(hào)s相加，得到欲訪問(wèn)段s在該進(jìn)程的段表中表目入口地址；從該表的表目中得到該段的頁(yè)表起始地址，并將其與地址場(chǎng)中的頁(yè)號(hào)p相加后得到欲訪問(wèn)頁(yè)p在該段的頁(yè)表中的表目入口地址；從該頁(yè)表表目中取出其對(duì)應(yīng)的頁(yè)架號(hào)與指令地址場(chǎng)中的頁(yè)內(nèi)地址d拼接成主存物理地址。2023/2/548段頁(yè)式存儲(chǔ)管理算法教材圖9.8；s<=段表長(zhǎng)嗎？由硬件自動(dòng)將段號(hào)s與段表地址寄存器中的段表長(zhǎng)進(jìn)行比較；段在主存嗎？根據(jù)段表中狀態(tài)位值由硬件判別；p<=頁(yè)表長(zhǎng)嗎？根據(jù)段表的表目中的頁(yè)表長(zhǎng)度與p進(jìn)行比較，在有快表的情況下將p與快表中的該表目的“該段的頁(yè)表長(zhǎng)”進(jìn)行比較；訪問(wèn)類型合法嗎？將本次訪問(wèn)的類型與快表中的存取控制信息進(jìn)行比較；頁(yè)在主存嗎？根據(jù)該段的頁(yè)表中的相應(yīng)頁(yè)的狀態(tài)位判定；缺頁(yè)中斷處理2023/2/549段頁(yè)式存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)提供了虛擬存儲(chǔ)器的功能；因?yàn)橐皂?yè)架為單位分配主存，所以無(wú)緊縮問(wèn)題，也沒(méi)有頁(yè)外的碎片存在；便于處理變化的數(shù)據(jù)結(jié)構(gòu)，段可動(dòng)態(tài)增長(zhǎng)；便于共享，只要欲共享作業(yè)的段表中有相應(yīng)表目指向該共享段在主存中的頁(yè)表地址；便于控制存取訪問(wèn)。缺點(diǎn)增加了硬件成本，因?yàn)樾枰嗟挠布С?；增加了軟件?fù)雜性和管理開(kāi)銷；同分頁(yè)系統(tǒng)一樣仍然存在頁(yè)內(nèi)碎片。2023/2/550頁(yè)面置換算法的引出當(dāng)系統(tǒng)中沒(méi)有空閑頁(yè)時(shí)，就要進(jìn)行頁(yè)面置換，即挑選一個(gè)頁(yè)面淘汰出去，并把此頁(yè)架分給進(jìn)程使用；問(wèn)題挑選什么樣的頁(yè)面來(lái)淘汰？從該進(jìn)程已有頁(yè)面集中還是在全體頁(yè)面集中選擇淘汰頁(yè)，即局部置換還是全局置換？2023/2/551頁(yè)面置換算法（1）最佳置換算法淘汰在將來(lái)再也不被訪問(wèn)，或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)的頁(yè)；最近未使用置換算法不但希望淘汰的頁(yè)是最近未使用的頁(yè)，而且還希望被挑選的頁(yè)在主存駐留其間，其頁(yè)面內(nèi)的數(shù)據(jù)未被修改過(guò)；先進(jìn)先出置換算法選擇最早進(jìn)入主存的頁(yè)面淘汰，理由是其不再使用的可能性比最近調(diào)入的頁(yè)面要大；但只是在按線性順序訪問(wèn)地址空間時(shí)，才是理想的，否則效率不高；隨著分給的頁(yè)架數(shù)增加，缺頁(yè)頻率也增加；2023/2/552頁(yè)面置換算法（2）二次機(jī)會(huì)置換算法把先進(jìn)先出算法與使用頁(yè)表中的訪問(wèn)位結(jié)合起來(lái)；首先檢查先進(jìn)先出鏈上的最前面（最早進(jìn)入）的頁(yè)，如果它的訪問(wèn)位為0，則選擇該頁(yè)淘汰；如果它的訪問(wèn)位為1，則把該頁(yè)移到FIFO的鏈尾，即把它作為新調(diào)入的頁(yè)；繼續(xù)查找鏈上的下一個(gè)頁(yè)并檢查它們的訪問(wèn)頁(yè)，直到遇到訪問(wèn)位為0的那些較先進(jìn)入的頁(yè)，把它選擇為被淘汰的頁(yè)。時(shí)鐘頁(yè)面置換算法把進(jìn)程所訪問(wèn)的頁(yè)構(gòu)成一個(gè)象時(shí)鐘那樣的環(huán)形鏈表；產(chǎn)生缺頁(yè)