《存儲(chǔ)器管理》 (2)

1、第四章存儲(chǔ)器管理 4.1 存儲(chǔ)器的層次結(jié)構(gòu) 4.2程序的裝入和鏈接 4.3連續(xù)分配方式4.4基本分頁(yè)存儲(chǔ)管理方式4.5基本分段存儲(chǔ)管理方式4.6虛擬存儲(chǔ)器的基本概念4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.8頁(yè)面置換算法4.9請(qǐng)求分段存儲(chǔ)管理方式 精選ppt 存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的五大組成部分之一。隨著計(jì)算機(jī)技術(shù)的發(fā)展，存儲(chǔ)器容量一直在擴(kuò)充，但仍不能滿足現(xiàn)代軟件和用戶的需要，因此存儲(chǔ)器仍是一種寶貴、緊俏的資源。對(duì)存儲(chǔ)器加以有效管理，不僅直接影響存儲(chǔ)器的利用率，而且對(duì)系統(tǒng)性能有重大影響。存儲(chǔ)器管理的主要對(duì)象是內(nèi)存，對(duì)外存的管理在文件管理中。精選ppt存儲(chǔ)管理的主要功能有: 主存分配與回收 地址重定位(地址映射

2、) 存儲(chǔ)保護(hù) 主存擴(kuò)充(虛擬內(nèi)存) 提高內(nèi)存空間的利用率精選ppt4.1 存儲(chǔ)器的層次結(jié)構(gòu) 4.1.1 多級(jí)存儲(chǔ)器結(jié)構(gòu)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器是信息外理的來(lái)源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲(chǔ)裝置，都無(wú)法同時(shí)從速度與容量?jī)煞矫?，滿足用戶的需求。實(shí)際上它們組成了一個(gè)速度由快到慢，容量由小到大的存儲(chǔ)裝置層次。 對(duì)于通用計(jì)算機(jī)而言，存儲(chǔ)層次至少應(yīng)具有三級(jí)：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計(jì)算機(jī)中，還可以根據(jù)具體的功能分工細(xì)劃為寄存器、高速緩存、主存儲(chǔ)器、磁盤緩存、固定磁盤、可移動(dòng)存儲(chǔ)介質(zhì)等6層。精選ppt圖4-1 計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意 精選ppt

3、4.1.2 主存儲(chǔ)器與寄存器1主存儲(chǔ)器主存儲(chǔ)器(簡(jiǎn)稱內(nèi)存或主存)用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。其容量對(duì)于當(dāng)前的微機(jī)系統(tǒng)和大中型機(jī)，可能一般為數(shù)十MB到數(shù)GB，而且容量還在不斷增加，而嵌入式計(jì)算機(jī)系統(tǒng)一般僅有幾十KB到幾MB。CPU的控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)，數(shù)據(jù)能夠從主存儲(chǔ)器讀取并將它們裝入到寄存器中，或者從寄存器存入到主存儲(chǔ)器。CPU與外圍設(shè)備交換的信息一般也依托于主存儲(chǔ)器地址空間。由于主存儲(chǔ)器的訪問(wèn)速度遠(yuǎn)低于CPU執(zhí)行指令的速度，為緩和這一矛盾，在計(jì)算機(jī)系統(tǒng)中引入了寄存器和高速緩存。 精選ppt2寄存器寄存器訪問(wèn)速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十

4、分昂貴，因此容量不可能做得很大。寄存器的長(zhǎng)度一般以字(word)為單位。寄存器的數(shù)目，對(duì)于當(dāng)前的微機(jī)系統(tǒng)和大中型機(jī)，可能有幾十個(gè)甚至上百個(gè)；而嵌入式計(jì)算機(jī)系統(tǒng)一般僅有幾個(gè)到幾十個(gè)。寄存器用于加速存儲(chǔ)器的訪問(wèn)速度，如用寄存器存放操作數(shù)，或用作地址寄存器加快地址轉(zhuǎn)換速度等。 精選ppt4.1.3 高速緩存和磁盤緩存1高速緩存高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件，其容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級(jí)左右，從幾十KB到幾MB，訪問(wèn)速度快于主存儲(chǔ)器。根據(jù)程序執(zhí)行的局部性原理(即程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分)，將主存中一些經(jīng)常訪問(wèn)的信息存

5、放在高速緩存中，減少訪問(wèn)主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度。通常，進(jìn)程的程序和數(shù)據(jù)時(shí)存放在主存儲(chǔ)器中，每當(dāng)使用時(shí)，被臨時(shí)復(fù)制到一個(gè)速度較快的高速緩存中。精選ppt當(dāng)CPU訪問(wèn)一組特定信息時(shí)，首先檢查它是否在高速緩存中，如果已存在，可直接從中取出使用，以避免訪問(wèn)主存，否則，再?gòu)闹鞔嬷凶x出信息。精選ppt2磁盤緩存由于目前磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問(wèn)速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問(wèn)磁盤的次數(shù)。磁盤緩存本身并不是一種實(shí)際存在的存儲(chǔ)介質(zhì)，它利用主存中的存儲(chǔ)空間，來(lái)暫存從磁盤中讀出(或?qū)懭?的信息。主存也可以看做是輔存的高速緩存，因?yàn)椋o存中的數(shù)據(jù)

6、必須復(fù)制到主存方能使用；反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。 精選ppt一個(gè)文件的數(shù)據(jù)可能出現(xiàn)在存儲(chǔ)器層次的不同級(jí)別中，例如，一個(gè)文件數(shù)據(jù)通常被存儲(chǔ)在輔存中(如硬盤)，當(dāng)其需要運(yùn)行或被訪問(wèn)時(shí)，就必須調(diào)入主存，也可以暫時(shí)存放在主存的磁盤高速緩存中。大容量的輔存常常使用磁盤，磁盤數(shù)據(jù)經(jīng)常備份到磁帶或可移動(dòng)磁盤組上，以防止硬盤故障時(shí)丟失數(shù)據(jù)。有些系統(tǒng)自動(dòng)地把老文件數(shù)據(jù)從輔存轉(zhuǎn)儲(chǔ)到海量存儲(chǔ)器中，如磁帶上，這樣做還能降低存儲(chǔ)價(jià)格。 精選ppt4.2 程序的裝入和鏈接在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)

7、存中執(zhí)行的程序，通常要經(jīng)過(guò)以下幾步：（1）編譯。由編譯程序（Compiler）將用戶源代碼編譯成若干個(gè)目標(biāo)模塊（Object Module）；（2）鏈接。由鏈接程序（Linker）將編譯后形成的目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)，鏈接在一起，形成一個(gè)裝入模塊（Load Module）；（3）裝入。由裝入程序（Loader）將裝入模塊裝入內(nèi)存。精選ppt圖4-2對(duì)用戶程序的處理步驟 庫(kù)鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存精選ppt0 目標(biāo)模塊100 0 100 作業(yè)J200 512K 地址空間符號(hào)指令 數(shù)據(jù)說(shuō)明 I/O說(shuō)明名空間(作業(yè) J 的源程序)內(nèi)存空間裝入編譯

8、關(guān)于三個(gè)空間的定義：邏輯地址或相對(duì)地址物理地址或絕對(duì)地址符號(hào)地址精選ppt4.2.1 程序的裝入 先介紹一個(gè)無(wú)須進(jìn)行鏈接的單個(gè)目標(biāo)模塊的裝入過(guò)程。此時(shí)目標(biāo)模塊就是裝入模塊。將一個(gè)裝入模塊裝入內(nèi)存時(shí)，有三種方式：絕對(duì)裝入方式可重定位裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式精選ppt 符號(hào)地址程 序JUMP iLOAD jDATAijab程 序JUMP 1424LOAD 2224DATA14242224絕對(duì)地址1024精選ppt365LOAD 1,2500365LOAD 1,2500 010002500500010000110001250015000作業(yè)地址空間內(nèi)存空間精選pptLoad 1,2500 365L

9、oad 1,2500 3650100025005000010000作業(yè)地址空間存儲(chǔ)空間重定位寄存器11000125002500 10000相對(duì)地址+由于這種地址變換是在作業(yè)執(zhí)行期間隨著每條指令的執(zhí)行自動(dòng)地、連續(xù)地進(jìn)行，所以稱之為動(dòng)態(tài)重定位。精選ppt4.2.2 程序的鏈接 程序經(jīng)過(guò)編譯后得到一組目標(biāo)模塊，再利用鏈接程序?qū)⒛繕?biāo)模塊鏈接，形成裝入模塊。根據(jù)鏈接時(shí)間的不同，把鏈接分成三種：靜態(tài)鏈接：在程序運(yùn)行前，將目標(biāo)模塊及所需的庫(kù)函數(shù)鏈接成一個(gè)完整的裝配模塊，以后不再拆開(kāi)。裝入時(shí)動(dòng)態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。運(yùn)行時(shí)動(dòng)態(tài)鏈接：指對(duì)某些目標(biāo)

10、模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對(duì)它進(jìn)行鏈接。精選ppt一、靜態(tài)鏈接： (Static Linking) 事先將幾個(gè)目標(biāo)鏈接裝配成一個(gè)裝入模塊，以后不再拆開(kāi)的鏈接方式，稱為靜態(tài)鏈接方式。如右圖： 模塊ACALL B;Return;0L-1模塊BCALL C;Return;0M-1模塊C Return;0N-10L-1模塊AJSR “L”Return;LL+M-1模塊BJSR “L+M”;Return;模塊C Return;L+ML+M+N-1精選pptSEQAMSUBR 1MAIN系統(tǒng)目標(biāo)庫(kù)當(dāng)前生成的目 標(biāo) 庫(kù)私有目標(biāo)庫(kù)MAIN .call SEQAM.call SURB 1.

11、查找引用讀入查找引用裝入模塊SEQAM RETURNSURB 1 RETURN精選ppt 如:主程序段ABif x0 then call A else call B 精選ppt靜態(tài)鏈接精選ppt動(dòng)態(tài)鏈接精選ppt4.2 連續(xù)分配方式 連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。分類：?jiǎn)我贿B續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配精選ppt4.2.1 單一連續(xù)分配 最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。 采用這種存儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常放在內(nèi)存低址部分，用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給

12、用戶使用。OS用戶區(qū)精選ppt工作流程 單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對(duì)地址是否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。精選ppt工作流程(續(xù))精選ppt4.2.2 固定分區(qū)分配將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中只裝入一道作業(yè)，這樣把用戶空間劃分為幾個(gè)分區(qū)，便允許有幾道作業(yè)并發(fā)執(zhí)行。當(dāng)有一空閑分區(qū)時(shí)，便可以再?gòu)耐獯娴暮髠渥鳂I(yè)隊(duì)列中，選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時(shí)，可再?gòu)暮髠渥鳂I(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。精選ppt分區(qū)大小相等 分區(qū)大小

13、不相等精選ppt2. 內(nèi)存分配為便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配)。精選ppt未分配1281284已分配64643已分配32322已分配24121狀態(tài)起址(K)大小(K)分區(qū)號(hào)分區(qū)說(shuō)明表作業(yè)C作業(yè)B作業(yè)A操作系統(tǒng) 24K32K64K128K256K存儲(chǔ)空間分配情況精選ppt固定分區(qū)分配算法流程圖要求xK大小的分區(qū)取分區(qū)說(shuō)明表的第一項(xiàng)該分區(qū)空閑嗎？分區(qū)大小xK表結(jié)束嗎？返回分區(qū)號(hào)狀態(tài)位置1無(wú)法分配取下一項(xiàng)NYYYNN分區(qū)回收？精選ppt 采用這種技術(shù)，雖然可以使多個(gè)作業(yè)共享主存，但仍不能充分利用它。因?yàn)?，?/p>

14、個(gè)作業(yè)的大小，只有當(dāng)作業(yè)調(diào)度程序在分析進(jìn)程創(chuàng)建請(qǐng)求時(shí)才能確定；而分區(qū)的大小是在系統(tǒng)初啟時(shí)劃定的。由于作業(yè)的大小不可能剛好等于某個(gè)分區(qū)的大小，所以，在每個(gè)分配的分區(qū)中，通常都有一部分未被作業(yè)占用而浪費(fèi)掉。這種分配給用戶而未被利用的部分，稱作存儲(chǔ)器的“內(nèi)零頭”(InternaI Fragmentation)。 固定分區(qū)方式存儲(chǔ)管理的優(yōu)點(diǎn)是分區(qū)方法特別簡(jiǎn)單，實(shí)現(xiàn)起來(lái)也很容易；缺點(diǎn)是存儲(chǔ)空間的利用率太低?，F(xiàn)在的操作系統(tǒng)幾乎不用它了。 精選ppt4.3.3 動(dòng)態(tài)分區(qū)分配所謂動(dòng)態(tài)式分區(qū)分配是指根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配連續(xù)的內(nèi)存空間。這種存儲(chǔ)管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問(wèn)題。是一種較為實(shí)

15、用的存儲(chǔ)管理方法。在實(shí)現(xiàn)過(guò)程中涉及三個(gè)問(wèn)題：分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配算法分區(qū)分配與回收操作精選ppt一、可變分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 常用的數(shù)據(jù)結(jié)構(gòu)有： 1. 空閑分區(qū)表： 序號(hào)始址長(zhǎng)度115K23K248K20K380K30K.2. 空閑分區(qū)鏈：N個(gè)字節(jié)可用（未分配）狀態(tài)位 大小 指針 0 N+2 前向指針 0 N+2 后向 指針 精選ppt精選ppt2. 分區(qū)分配算法系統(tǒng)運(yùn)行一段時(shí)間后，在整個(gè)存儲(chǔ)空間內(nèi)將出現(xiàn)許多大小不等的區(qū)域，有的仍被作業(yè)進(jìn)程占用，有的則因作業(yè)已退出系統(tǒng)而成為可用于再分配的區(qū)域?，F(xiàn)在假設(shè)有一個(gè)新的作業(yè)需調(diào)入主存，如何為其選擇一個(gè)合適的區(qū)域？常用的分配算法：(1) 首次適應(yīng)

16、算法FF(2) 循環(huán)首次適應(yīng)算法(3) 最佳適應(yīng)算法(4)最壞適應(yīng)算法(5) 快速適應(yīng)算法(quick fit)精選ppt(1) 首次適應(yīng)算法FFFF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。若從頭到尾不存在滿足要求的分區(qū)，則分配失敗。優(yōu)點(diǎn)：算法簡(jiǎn)單，查找速度快；優(yōu)先利用內(nèi)存低址部分的空閑分區(qū),留在高址部分的大的空白區(qū)被劃分的機(jī)會(huì)較少，因而在大作業(yè)到來(lái)時(shí)也比較容易得到滿足。缺點(diǎn)：低址部分不斷劃分，產(chǎn)生小碎片；每次查找從低址部分開(kāi)始，

17、增加了查找的開(kāi)銷要求:空閑區(qū)表或空閑區(qū)鏈按地址從低到高排列.精選ppt例：指針10k60k90k20k有四塊空白區(qū)(從低地址高地址)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。指針10k60k90k20k41k解：精選ppt(2) 循環(huán)首次適應(yīng)算法（下次適應(yīng)算法 next fit NF） 在分配內(nèi)存空間時(shí)，從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直到找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)算法，需要：設(shè)置一起始查尋指針采用循環(huán)查找方式優(yōu)點(diǎn)：使內(nèi)存中空閑分區(qū)分布均勻，減少查找的開(kāi)銷缺點(diǎn)：缺乏大的空閑分區(qū)要求:空閑區(qū)表或空閑區(qū)鏈按地址從低到高排列.精選ppt(

18、3) 最佳適應(yīng)算法(Best fit: BF) 所謂“最佳”是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。要求:空閑分區(qū)表或空閑分區(qū)鏈按其容量從小到大排列。優(yōu)點(diǎn)：如果存儲(chǔ)空間中具有正好是所要求大小的存儲(chǔ)空白區(qū)，則必然被選中；如果不存在這樣的空白區(qū)，也只對(duì)比要求稍大的空白區(qū)進(jìn)行劃分，而絕不會(huì)去劃分一個(gè)更大的空白區(qū)。因此，其后遇到大作業(yè)到來(lái)時(shí)，作業(yè)要求的存儲(chǔ)區(qū)域就比較容易得到滿足。缺點(diǎn)：產(chǎn)生許多難以利用的小空閑區(qū)；在回收一個(gè)分區(qū)時(shí)，為了把它插入到空白區(qū)鏈中合適的位置上也頗為費(fèi)時(shí)。所以，這種算法乍看起來(lái)是最佳的，其實(shí)則不然。精選ppt指針10k60k90

19、k20k例：有四塊空白區(qū)(從小容量大容量)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。指針10k20k60k90k1k解：再排序精選ppt練習(xí)： 某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55MB（初始為空閑），采用最佳適配（Best Fit）算法，分配和釋放的順序?yàn)椋悍峙?5MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時(shí)主存中最大空閑分區(qū)的大小是（ ）。 【聯(lián)考2010】 A.7 MB B.9 MB C.10 MB D.15 MB精選ppt (4) 最壞(差)適應(yīng)算法(Worst fit: WF)所謂“最壞”是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最大的空閑分區(qū)分配給作業(yè)。要求

20、:空閑分區(qū)表或空閑分區(qū)鏈按其容量從大到小排列。指針90k60k20k10k71k再排序指針90k20k10k60k例：有四塊空閑區(qū)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。精選ppt優(yōu)點(diǎn)：在劃分后剩下的空白區(qū)也是最大的，產(chǎn)生碎片幾率最小，有利于中小作業(yè)；查找效率很高。缺點(diǎn)：大的空閑區(qū)不容易保留，當(dāng)有大的作業(yè)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往得不到滿足。 精選ppt外零頭:把存儲(chǔ)空間中這些小的無(wú)用的分區(qū)稱為 “外零頭” (Externa1 Fragmentation)。內(nèi)零頭:分配給用戶而未被利用的部分，稱作存儲(chǔ)器的“內(nèi)零頭”(InternaI Fragmentation)。什么樣的分配方式產(chǎn)生外零頭？什么樣的分配

21、方式產(chǎn)生內(nèi)零頭？精選ppt四種策略比較上述四種分配策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來(lái)分析。對(duì)于某一作業(yè)序列來(lái)說(shuō)，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說(shuō)該算法對(duì)這一作業(yè)序列是合適的。對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對(duì)該作業(yè)序列是不合適的。對(duì)分配策略的一種有用的度量是，系統(tǒng)對(duì)選定的一組作業(yè)來(lái)運(yùn)行，比較第一次發(fā)生不能滿足存儲(chǔ)請(qǐng)求所經(jīng)歷的時(shí)間。精選ppt舉例：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其

22、它兩種對(duì)該作業(yè)序列是不合適的。精選pptOS30K使用20K使用5K使用46K020K100K160K210K255K分區(qū)號(hào)大小起始地址130K20K220K100K35K160K446K210K首次適應(yīng)算法空閑分區(qū)表分區(qū)號(hào)大小起始地址15K160K220K100K330K20K446K210K最佳適應(yīng)算法空閑分區(qū)表分區(qū)號(hào)大小起始地址146K210K230K20K320K100K45K160K最壞適應(yīng)算法空閑分區(qū)表OS30K使用20K使用5K使用46K020K100K160K210K255K作業(yè)A18K作業(yè)序列作業(yè)A18KOS30K使用20K使用5K使用46K020K100K160K210K2

23、55K作業(yè)序列255KOS30K使用20K使用5K使用46K020K100K160K210K作業(yè)A18K作業(yè)序列12K 38K2K 118K28K 228K2 30K 20K 1 28K 228K 2 2K 118K 1 5K 160K 例子精選ppt練習(xí)有作業(yè)序列：作業(yè)A要求21K；作業(yè)B要求30K，作業(yè)C要求25K。精選ppt5) 快速適應(yīng)算法(quick fit)該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型

24、，并記錄了該類型空閑分區(qū)鏈表表頭的指針。 空閑分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分，如2 KB、4 KB、8 KB等，對(duì)于其它大小的分區(qū)，如7 KB這樣的空閑區(qū)，既可以放在8 KB的鏈表中，也可以放在一個(gè)特殊的空閑區(qū)鏈表中。 精選ppt優(yōu)點(diǎn)：查找效率高，僅需要根據(jù)進(jìn)程的長(zhǎng)度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進(jìn)行分配即可。另外該算法在進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對(duì)任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對(duì)大空間的需求，也不會(huì)產(chǎn)生內(nèi)存碎片。缺點(diǎn)：在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷較大。此外，該算法在分配空閑分區(qū)時(shí)是以進(jìn)程為單位，一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中

25、，或多或少地存在一定的浪費(fèi)。精選ppt3. 分區(qū)分配操作分配內(nèi)存利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小表示為m.size，若m.size- u.sizesize(規(guī)定的不再切割的分區(qū)大小)，將整個(gè)分區(qū)分配給請(qǐng)求者，否則從分區(qū)中按請(qǐng)求的大小劃出一塊內(nèi)存空間分配出去，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者。精選ppt從頭開(kāi)始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出Y

26、YYNNN精選ppt回收內(nèi)存 當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)首址，在空閑分區(qū)鏈(表)中找到相應(yīng)插入點(diǎn)，此時(shí)可能有四種情況：(1) 回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)F1鄰接(2) 回收區(qū)與插入點(diǎn)的后一個(gè)分區(qū)F2鄰接(3) 回收區(qū)與插入點(diǎn)的前后兩個(gè)分區(qū)F1、F2鄰接(4) 回收區(qū)既不與F1鄰接，又不與F2鄰接精選ppt作業(yè)：某操作系統(tǒng)采用可變分區(qū)分配存儲(chǔ)管理方法，用戶區(qū)為512K，始址為0，用空閑分區(qū)表管理空閑分區(qū)。若分配時(shí)采用分配空閑區(qū)低地址部分的方案，且初始時(shí)用戶區(qū)的512K空間空閑，對(duì)下述申請(qǐng)序列：申請(qǐng)300K，申請(qǐng)100K，釋放300K，申請(qǐng)150K，申請(qǐng)30K，申請(qǐng)40K，申請(qǐng)60K

27、，釋放30K回答以下問(wèn)題：（1）采用首次適應(yīng)算法，空閑分區(qū)有哪些空塊（給出始址、大?。?？（2）采用最佳適應(yīng)算法，空閑分區(qū)有哪些空塊（給出始址、大?。浚?）如再申請(qǐng)100K，針對(duì)（1）和（2）各有什么結(jié)果？精選ppt4.3.6 可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入隨著系統(tǒng)接收的作業(yè)的增加，內(nèi)存中連續(xù)的大塊分區(qū)將不存在，產(chǎn)生了大量的“碎片”。問(wèn)題:新的作業(yè)無(wú)法裝入到每個(gè)“碎片”小分區(qū)上運(yùn)行，但所有碎片的空間總和可能大于需求。解決方案:通過(guò)移動(dòng)內(nèi)存中作業(yè)的位置，把原來(lái)多個(gè)分散的小分區(qū)“拼接”成一個(gè)大分區(qū)的方法，稱為“拼接”或“緊湊” /“緊縮”/“澄清”。缺點(diǎn)：用戶程序在內(nèi)存中的地址發(fā)生變化，必須

28、重定位。精選pptOS區(qū)Job2Job4Job3Job1Job5Job6Job7OS區(qū)Job2Job4Job3Job1Job5Job6Job7OS區(qū)Job2Job4Job3Job1Job5Job6Job7“零頭”碎片圖4-8 緊湊的示意精選ppt2.動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位概念: 作業(yè)被裝入到內(nèi)存中的相對(duì)地址要轉(zhuǎn)換為物理地址，被推遲到程序指令真正要執(zhí)行的時(shí)候進(jìn)行。精選ppt 地址空間 0 100 Load 1,500 500 Y 1K 存儲(chǔ)空間 0 1K1124 Load 1,5001524 Y 2K 512K 有效地址 500重定位寄存器1K處理機(jī)一側(cè)存儲(chǔ)器一側(cè)實(shí)現(xiàn)：（1）必須由硬件地址變

29、換機(jī)構(gòu)重定位寄存器支持：存放程序的起始地址;（2）真正訪問(wèn)的內(nèi)存物理地址=相對(duì)地址+重定位寄存器中地址，當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了“緊湊”，并不需要對(duì)程序作修改。精選ppt優(yōu)點(diǎn)：消除“碎片”，提高了內(nèi)存利用率，同時(shí)提高了系統(tǒng)效率。缺點(diǎn)：（1）需要?jiǎng)討B(tài)重定位“硬件”機(jī)構(gòu)支持，增加了系統(tǒng)成本；（2）輕度降低了程序執(zhí)行速度；（3）“緊湊”處理增加了系統(tǒng)開(kāi)銷。精選ppt三、動(dòng)態(tài)重定位分區(qū)分配算法請(qǐng)求分配一個(gè)大小為xk的分區(qū)有大于xk的空閑區(qū)嗎？空閑區(qū)的總和xk嗎？緊縮存儲(chǔ)并相應(yīng)地修改諸表(得到一個(gè)完整的空閑區(qū)xk)分配分區(qū)并修改諸表此刻已經(jīng)無(wú)法分配一個(gè)分區(qū)返回一個(gè)分區(qū)號(hào)數(shù)是是否否精選ppt說(shuō)明：1. 動(dòng)態(tài)重定

30、位分區(qū)分配法是利用分區(qū)的“拼接”(對(duì)空白區(qū)而言)或“緊湊”(作業(yè)程序而言)技術(shù)解決“零頭”。2. 問(wèn)題 拼湊時(shí)機(jī)的選擇 (i)出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)被釋放后即緊縮)緊縮工作大，開(kāi)銷大，但管理簡(jiǎn)單 (ii)存貯不足(空白分區(qū)不夠大)時(shí)進(jìn)行拼接。緊縮次數(shù)少，但管理(算法)較復(fù)雜。精選ppt4.3.7對(duì)換1. 對(duì)換（Swapping）的引入多道程序環(huán)境下存在的問(wèn)題：阻塞進(jìn)程占據(jù)大量?jī)?nèi)存空間許多作業(yè)在外存而不能進(jìn)入內(nèi)存運(yùn)行所謂“對(duì)換”，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程和進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。精選p

31、pt分類：整體對(duì)換(或進(jìn)程對(duì)換)：以整個(gè)進(jìn)程為單位頁(yè)面對(duì)換或分段對(duì)換：以頁(yè)或段為單位實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須具備的功能：對(duì)換空間的管理進(jìn)程的換出進(jìn)程的換入精選ppt2. 對(duì)換空間的管理外存存儲(chǔ)內(nèi)容駐留時(shí)間主要目標(biāo)分配方式文件區(qū)文件較長(zhǎng)久提高文件存儲(chǔ)空間的利用率離散對(duì)換區(qū)從內(nèi)存換出的進(jìn)程短暫提高進(jìn)程換入和換出的速度連續(xù)為了能對(duì)交換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以記錄外存的使用情況（空閑分區(qū)表或空閑分區(qū)鏈）對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收雷同。精選ppt3、進(jìn)程的換入和換出 a.進(jìn)程的換出：條件:創(chuàng)建進(jìn)程需更多的內(nèi)存空間時(shí), 或內(nèi)存空間不夠用時(shí);過(guò)程:選擇阻

32、塞、優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程啟動(dòng)盤塊將進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。 b.進(jìn)程的換入：條件:當(dāng)內(nèi)存空間稍有空閑時(shí);過(guò)程:找出就緒、但已經(jīng)換出（到磁盤上）的進(jìn)程將其中換出時(shí)間最久的進(jìn)程將其換出,直至已經(jīng)無(wú)可以換入的進(jìn)程或或已無(wú)法獲得足夠大的內(nèi)存來(lái)?yè)Q入進(jìn)程為止。精選ppt4.4 基本分頁(yè)存儲(chǔ)管理方式 連續(xù)分配方式會(huì)形成“碎片”，雖然可以通過(guò)“緊湊”解決，但開(kāi)銷大。如果允許將一個(gè)進(jìn)程直接分散地裝入許多不相鄰的分區(qū)中，則無(wú)需“緊湊”，由此產(chǎn)生離散分配方式。 分類：分頁(yè)存儲(chǔ)管理方式：離散分配的基本單位是頁(yè) （1）基本分頁(yè)（純分頁(yè)）管理：不具備頁(yè)面置換功能；不具備支持實(shí)現(xiàn)虛擬存儲(chǔ)器的功能；要求

33、把每個(gè)作業(yè)全部裝入內(nèi)存后才能運(yùn)行。 （2）支持虛存管理的請(qǐng)求分頁(yè)管理。分段存儲(chǔ)管理方式：離散分配的基本單位是段精選ppt4.4.1 頁(yè)面與頁(yè)表1. 頁(yè)面頁(yè)面和物理塊分頁(yè)存儲(chǔ)管理是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片稱為頁(yè)面或頁(yè)，并為各頁(yè)加以編號(hào)，從0開(kāi)始。同時(shí)把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為（物理）塊或頁(yè)框。順序編號(hào)（也從0開(kāi)始）。精選ppt01234567891110內(nèi)存第0頁(yè)第1頁(yè)第2頁(yè)第3頁(yè)第4頁(yè)第5頁(yè)第6頁(yè)用戶作業(yè)02K-1第2頁(yè)（頁(yè)長(zhǎng)2K）02K-14號(hào)頁(yè)框（頁(yè)長(zhǎng)2K）精選ppt在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰的物理塊中

34、。例如：一個(gè)作業(yè)的地址空間有m頁(yè)。那么，只要分配給它m個(gè)頁(yè)框，每一頁(yè)分別裝入一個(gè)頁(yè)框內(nèi)即可。這里，并不要求這些頁(yè)框是連續(xù)的。說(shuō)明：（1）在進(jìn)程調(diào)度時(shí)，必須把它的所有頁(yè)一次裝入到主存的頁(yè)框內(nèi)；如果當(dāng)時(shí)頁(yè)框數(shù)不足，則該進(jìn)程必須等待，系統(tǒng)再調(diào)度另外的進(jìn)程。（純分頁(yè)方式）（2）進(jìn)程的最后一頁(yè)經(jīng)常裝不滿而形成“頁(yè)內(nèi)碎片”。即存在內(nèi)零頭。精選ppt.0塊1塊2塊3塊4塊5塊6塊0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)作業(yè)的地址空間頁(yè)框（物理塊）內(nèi)存精選ppt二、頁(yè)面大小在分頁(yè)系統(tǒng)中對(duì)頁(yè)面的大小應(yīng)選擇得適當(dāng)。因?yàn)椋喝暨x擇的頁(yè)面較小，一方面可使內(nèi)存碎片小，并減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率；但另一方面，也會(huì)使每個(gè)進(jìn)程

35、要求較多的頁(yè)面，從而導(dǎo)致頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存；還會(huì)降低頁(yè)面換進(jìn)換出的效率。若選擇的頁(yè)面較大，雖然可減少頁(yè)表長(zhǎng)度，提高換進(jìn)換出效率，但又會(huì)使頁(yè)內(nèi)碎片增大。頁(yè)面的大小通常在512B8KB選擇，但總是2的冪。精選ppt2.地址結(jié)構(gòu) 邏輯地址n-1 k k-1 0頁(yè)號(hào)P位移量W線性的邏輯地址長(zhǎng)度為n位, 包括兩部分：頁(yè)號(hào)P：n-k位,即:地址空間最多允許有2n-k頁(yè)；位移量W（頁(yè)內(nèi)位移量，即頁(yè)內(nèi)地址）：k位,頁(yè)內(nèi)地址大小=2kB 若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則可以由公式求出： 頁(yè)號(hào)P=INTA/L，頁(yè)內(nèi)地址d=A mod L 例如：系統(tǒng)的頁(yè)面大小L為1KB，A=2170B， 求

36、出P=2,d=122 精選ppt邏輯地址31 12 11 0位移量W 頁(yè)號(hào)P 頁(yè)號(hào)P：1231共20位 地址空間最多允許有220=1M頁(yè)，即每個(gè)進(jìn)程占用1M個(gè)頁(yè)。位移量W：011共12位 頁(yè)內(nèi)地址大小（即每頁(yè)的大?。?12B=4KB。 例：現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)的邏輯地址空間都支持很大的邏輯地址空間（232264）B，如下邏輯地址長(zhǎng)度為32位，包括兩部分：精選ppt(357101)8(011,101,111,001,000,001)2 (01,110,1111,001,000,001)2例：設(shè)虛地址為(357101)8 每一塊為1K字節(jié)塊（頁(yè)）的大小：1K=2101 6 7 1 1 0 1位

37、移量為(1101)8, 頁(yè)號(hào)為(167)8精選ppt3.頁(yè)表 在分頁(yè)系統(tǒng)中，存儲(chǔ)分配問(wèn)題變得非常簡(jiǎn)單，作業(yè)的一頁(yè)可以分配到存儲(chǔ)空間中任何一個(gè)可用的頁(yè)框。 問(wèn)題： (1)系統(tǒng)怎么知道作業(yè)的哪一頁(yè)分配在存儲(chǔ)空間的哪一頁(yè)框內(nèi)？ (2)如何實(shí)現(xiàn)以及何時(shí)實(shí)現(xiàn)把作業(yè)的邏輯地址變換為主存的物理地址。 精選ppt頁(yè)表： 系統(tǒng)為每一個(gè)進(jìn)程建立的，在內(nèi)存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊號(hào)的一張頁(yè)面映像表。 一個(gè)進(jìn)程占用多少頁(yè)，就在頁(yè)表中有多少頁(yè)表項(xiàng)。 頁(yè)表的作用：實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。數(shù)據(jù)結(jié)構(gòu)： 頁(yè)號(hào)、塊號(hào)、存取控制字段（控制存儲(chǔ)塊中的內(nèi)容是允許讀/寫(xiě)、只讀、只執(zhí)行）。根據(jù)每頁(yè)內(nèi)容的不同，可以設(shè)置不同的存取

38、限制。所以，在頁(yè)表的表目中除了包含指向所在頁(yè)框的指針外，還包括一個(gè)存取控制字段，這個(gè)表目也稱為頁(yè)描述子。精選ppt01234567891110內(nèi)存第0頁(yè)第1頁(yè)第2頁(yè)第3頁(yè)第4頁(yè)第5頁(yè)第6頁(yè)用戶作業(yè)塊號(hào)頁(yè)號(hào)1051169453327120頁(yè)表第0頁(yè)第1頁(yè)第2頁(yè)第3頁(yè)第4頁(yè)第5頁(yè)第6頁(yè)圖4-12頁(yè)表的作用精選ppt4.4.2 地址變換機(jī)構(gòu)地址映射從邏輯地址到物理地址的變換過(guò)程。將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，系統(tǒng)設(shè)置了地址變換機(jī)構(gòu)。 由于頁(yè)內(nèi)地址和物理地址一一對(duì)應(yīng)，所以地址變換機(jī)構(gòu)只是將邏輯地址中的頁(yè)號(hào)，轉(zhuǎn)換為內(nèi)存中的物理地址的物理塊號(hào)。借助頁(yè)表完成。邏輯地址 物理地址物理塊

39、號(hào)P頁(yè)內(nèi)地址d頁(yè)號(hào)P位移量W精選ppt1.基本的地址變換機(jī)構(gòu)在實(shí)際系統(tǒng)中，為了減少硬件成本，將頁(yè)表存放在被保護(hù)的系統(tǒng)區(qū)內(nèi)的一個(gè)連續(xù)空間中。這張頁(yè)表是在進(jìn)程裝入主存時(shí)，由系統(tǒng)根據(jù)內(nèi)存分配情況建立的。精選ppt分頁(yè)地址變換機(jī)構(gòu)變換過(guò)程：（1）進(jìn)程執(zhí)行之前：PCB（內(nèi)存中的頁(yè)表始址+頁(yè)表長(zhǎng)度）（2）進(jìn)程調(diào)度后：頁(yè)表寄存器PTR （內(nèi)存中的頁(yè)表始址+頁(yè)表長(zhǎng)度）（3）檢索頁(yè)表： 條件：頁(yè)表長(zhǎng)度邏輯地址中的頁(yè)號(hào)不成立：所訪問(wèn)的地址越界，產(chǎn)生一地址越界中斷；成立：未地址越界，則：由“頁(yè)表始址+頁(yè)號(hào)x頁(yè)表項(xiàng)長(zhǎng)度”找到該頁(yè)號(hào)在頁(yè)表中的位置。精選ppt圖4-13 分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)

40、表塊號(hào)頁(yè)號(hào)5332712052018物理地址頁(yè)號(hào)（3）頁(yè)內(nèi)地址2018邏輯地址越界中斷精選ppt關(guān)于分頁(yè)的地址變換計(jì)算 頁(yè)式地址映射設(shè)頁(yè)面大小為2KB精選ppt例1：某采用分頁(yè)存儲(chǔ)管理的系統(tǒng)中，物理地址占20位，邏輯地址中頁(yè)號(hào)占6位，頁(yè)面大小為1KB，問(wèn)： 該系統(tǒng)的內(nèi)存空間大小為多少？每個(gè)存儲(chǔ)塊的大小為多少？邏輯地址共幾位？每個(gè)作業(yè)的最大長(zhǎng)度為多少？ 若第0、1、2頁(yè)分別放在第3、7、9存儲(chǔ)塊中，則邏輯地址0420H對(duì)應(yīng)的物理地址是多少？精選ppt 解： 物理地址占20位，所以該系統(tǒng)的內(nèi)存空間大小為：220=1MB 存儲(chǔ)塊的大小與頁(yè)面大小相同，而頁(yè)面大小為1KB，因此存儲(chǔ)塊的大小為：1KB 由

41、于頁(yè)面大小為1KB，占10位，而頁(yè)號(hào)占6位，因此邏輯地址共16位。 邏輯地址共16位，從而該系統(tǒng)中的每個(gè)作業(yè)大小為：216=64KB精選ppt 邏輯地址到物理地址轉(zhuǎn)換的計(jì)算方法 ： 分頁(yè)系統(tǒng)中基本的地址變換：有兩種方式，一種是十進(jìn)制計(jì)算方法，另一種是二進(jìn)制計(jì)算方法。 十進(jìn)制計(jì)算方法：設(shè)頁(yè)號(hào)為P、頁(yè)內(nèi)位移為W、邏輯地址為A、物理地址為M、頁(yè)面大小為L(zhǎng)。 第一步，根據(jù)公式計(jì)算頁(yè)號(hào)和位移量: 頁(yè)號(hào)：P=int(A/L)，位移量：W=A mod L 第二步，查找頁(yè)表，確定第一步中計(jì)算得到的頁(yè)號(hào)所對(duì)應(yīng)的塊號(hào)。 第三步，計(jì)算物理地址，M=塊號(hào)*L+W精選ppt十進(jìn)制計(jì)算方法第一步： 將邏輯地址轉(zhuǎn)換成10進(jìn)

42、制：0420H=1056 頁(yè)號(hào)：P=int(A/L)=int（1056/1024）=1 位移量：W=A mod L=1056 mod 1024=32 第二步： 查頁(yè)表，1號(hào)頁(yè)面對(duì)應(yīng)7號(hào)物理塊，每個(gè)物理塊大小為1K。第三步： 物理地址為：71K+32=7200。 精選ppt 邏輯地址到物理地址轉(zhuǎn)換的計(jì)算方法 ：二進(jìn)制計(jì)算方法： 第一步，將邏輯地址以二進(jìn)制形式表示。 第二步，根據(jù)頁(yè)面大小，計(jì)算位移量所占二進(jìn)制位數(shù)，并將邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)位移量?jī)刹糠帧?第三步，把第二步中劃分得到的頁(yè)號(hào)部分轉(zhuǎn)換為十進(jìn)制，查找頁(yè)表，確定所對(duì)應(yīng)的塊號(hào)。 第四步，將第三步中得到的塊號(hào)轉(zhuǎn)換為二進(jìn)制，并與第二步中劃分得到

43、的頁(yè)內(nèi)位移量拼接（頁(yè)內(nèi)位移量作為低地址部分），至此物理地址計(jì)算完畢。也可以將物理地址轉(zhuǎn)換為十六進(jìn)制表示方式。 說(shuō)明：一定要能夠根據(jù)頁(yè)面大小確定位移量所占二進(jìn)制位數(shù)。常見(jiàn)頁(yè)面大小為1K、2K、4K和8K，所需二進(jìn)制位數(shù)依次為10、11、12和13。精選ppt二進(jìn)制計(jì)算方法：第一步，將邏輯地址轉(zhuǎn)換為二進(jìn)制： 0420H=0000 0100 0010 0000第二步，頁(yè)面大小為1K，所以位移量占10個(gè)二進(jìn)制位，將邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)位移量?jī)刹糠郑?0000 0100 0010 0000第三步，把頁(yè)號(hào)部分轉(zhuǎn)換為十進(jìn)制，查找頁(yè)表，確定所對(duì)應(yīng)的塊號(hào)： (0000 01)2=1，1號(hào)頁(yè)對(duì)應(yīng)7號(hào)物理塊。第

44、四步，將第三步中得到的塊號(hào)轉(zhuǎn)換為二進(jìn)制，并與第二步中劃分得到的頁(yè)內(nèi)位移量拼接，即得物理地址: 0001 1100 0010 0000 也可以轉(zhuǎn)換為十六進(jìn)制：1C20H。精選ppt練習(xí)：在分頁(yè)存儲(chǔ)系統(tǒng)中地址結(jié)構(gòu)的長(zhǎng)度為20位，頁(yè)面大小為2K，作業(yè)地址空間為8K，該作業(yè)各頁(yè)依次存放在1，3，6，7號(hào)物理塊中，相對(duì)地址4000處有一條指令 Store l，2500，請(qǐng)給出該作業(yè)的頁(yè)表，并分別指出該指令所在頁(yè)號(hào)和對(duì)應(yīng)的物理單元及數(shù)據(jù)存放所在的頁(yè)號(hào)和物理單元。 精選ppt 由題意，頁(yè)面大小為2K，該作業(yè)的地址空間為8K，因此該作業(yè)有4頁(yè)，其頁(yè)表為： 01132637計(jì)算相對(duì)地址4000的物理地址 頁(yè)號(hào)：

45、P=int(A/L)=int（4000/2048）=1 位移量：W=A mod L=4000 mod 2048=1952 物理地址為：3*2048+1952=8096計(jì)算相對(duì)地址2500的物理地址 頁(yè)號(hào)：P=int(A/L)=int（2500/2048）=1 位移量：W=A mod L=2500 mod 2048=452 物理地址為：3*2048+452=6596精選ppt作業(yè)1：某虛擬存儲(chǔ)器的用戶空間共有32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB。試問(wèn)：（1）邏輯地址的有效位是多少？（2）物理地址需要多少位？（3）假定某時(shí)刻系統(tǒng)用戶的第0，1，2，3頁(yè)分別分配的物理塊號(hào)為5，10，4，7，試將虛地

46、址0A5C和093C變換為物理地址。作業(yè)2：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。精選ppt提出改進(jìn)的原因： 計(jì)算機(jī)CPU存取數(shù)據(jù)需要訪問(wèn)內(nèi)存兩次，處理速度降低為1/2。改進(jìn)方法： 利用聯(lián)想寄存器（快表）并行查詢； 空間大?。?幾K到幾百K ，存放16512個(gè)頁(yè)表項(xiàng)；2.具有快表的地址變換機(jī)構(gòu)精選ppt實(shí)現(xiàn)原理： 快表與頁(yè)表同時(shí)訪問(wèn)：（1）在快表中找到相匹配的頁(yè)號(hào) 直接從快表中讀出對(duì)應(yīng)物理塊號(hào)；（2）在快表中沒(méi)有找到相匹配的頁(yè)號(hào) 還須找頁(yè)表，再?gòu)捻?yè)表中對(duì)出物理塊號(hào)； 再將此頁(yè)表項(xiàng)存入快表中

47、，重新更新快表。優(yōu)點(diǎn)：加快了地址變換的速度。精選ppt頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)表塊號(hào)頁(yè)號(hào)5332712051250物理地址頁(yè)號(hào)（3）頁(yè)內(nèi)地址（1250）邏輯地址越界中斷快表塊號(hào)頁(yè)號(hào)2051145320輸入寄存器圖4-14 具有快表的地址變換機(jī)構(gòu)精選ppt 當(dāng)調(diào)度合理時(shí)，命中率可以達(dá)到90以上?？紤]到快表的速度是內(nèi)存速度的數(shù)倍或數(shù)十倍，那么相對(duì)于內(nèi)存速度，訪問(wèn)頁(yè)表的時(shí)間可以忽略不計(jì)。也就是說(shuō)頁(yè)地址變換不會(huì)造成進(jìn)程運(yùn)行速度下降多少。精選ppt例：設(shè)訪問(wèn)主存時(shí)間為200ns,訪問(wèn)聯(lián)想存貯器為40ns，命中率為90，則平均存取時(shí)間為多少？查頁(yè)表兩次訪存：平均為200200400ns查快表，平均為：

48、 (200+40)90(200+200+40)10260ns解：方法1：方法2：精選ppt4.3.3 兩級(jí)和多級(jí)頁(yè)表 現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間(232264)，頁(yè)表就非常大，需占用較大的地址空間。例如：一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB即212B，則每個(gè)進(jìn)程頁(yè)表的頁(yè)表項(xiàng)可達(dá)1M個(gè)，若每個(gè)頁(yè)表項(xiàng)占用一個(gè)字節(jié)，則每個(gè)進(jìn)程的頁(yè)表就要占據(jù)1MB的內(nèi)存空間，而且要求連續(xù)存放。解決方法：采用離散方式只將當(dāng)前所需頁(yè)表項(xiàng)調(diào)入內(nèi)存精選ppt1. 兩級(jí)頁(yè)表 將頁(yè)表分頁(yè)，并離散地將各個(gè)頁(yè)面分別存放在不同的物理塊中，同時(shí)為離散分配的頁(yè)表再建立一張頁(yè)表，稱為外層頁(yè)表，其每個(gè)頁(yè)表項(xiàng)

49、記錄了頁(yè)表頁(yè)面的物理塊號(hào)。精選ppt例如： 32位邏輯地址空間，頁(yè)面大小為4KB(即12位)，每個(gè)頁(yè)表項(xiàng)占4個(gè)字節(jié)，若采用一級(jí)頁(yè)表機(jī)構(gòu)，應(yīng)有20位頁(yè)號(hào)，即頁(yè)表項(xiàng)應(yīng)有1M個(gè)；在采用兩級(jí)頁(yè)表機(jī)構(gòu)時(shí)，再對(duì)頁(yè)表進(jìn)行分頁(yè)，使每頁(yè)包含210(即1024)個(gè)頁(yè)表項(xiàng)，最多允許有210個(gè)頁(yè)表分頁(yè)。即頁(yè)內(nèi)地址外層頁(yè)內(nèi)地址外層頁(yè)號(hào)dp2p1 31 22 21 12 11 0 精選ppt012345671141151468內(nèi)存空間641第0頁(yè)頁(yè)表0121023115114第1頁(yè)頁(yè)表01210231468第n頁(yè)頁(yè)表0121023174210781011012n外部頁(yè)表兩級(jí)分頁(yè)結(jié)構(gòu)頁(yè)表頁(yè)目錄表精選ppt外部頁(yè)表外層頁(yè)表始

50、址d物理地址外部頁(yè)號(hào)P1外部頁(yè)內(nèi)地址P2邏輯地址頁(yè)內(nèi)地址db頁(yè)表圖4-16 具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)外部頁(yè)表寄存器（包含頁(yè)表分頁(yè)始址）（包含該頁(yè)中的物理塊號(hào)b） 精選ppt 上述方法用離散分配空間解決了大頁(yè)表無(wú)需大片存儲(chǔ)空間的問(wèn)題，但并未減少頁(yè)表所占的內(nèi)存空間。 解決方法是把當(dāng)前需要的一批頁(yè)表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。精選ppt2. 多級(jí)頁(yè)表兩級(jí)頁(yè)表對(duì)32位機(jī)器適用，64位呢？頁(yè)面大小為4KB即212B，還剩52位，按物理塊大小212B來(lái)劃分頁(yè)表，則剩余42位用于外層頁(yè)號(hào)，此時(shí)外層頁(yè)表可能有4096G個(gè)頁(yè)表項(xiàng)，要占用16384GB的連續(xù)存儲(chǔ)空間解決方法：采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)

51、行分頁(yè)。將各個(gè)分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層來(lái)映射它們之間的關(guān)系。邏輯地址映射到物理地址的方法和二級(jí)頁(yè)表相同。精選ppt 練習(xí)：某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)大小為210字節(jié)，頁(yè)表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為： ，邏輯地址空間大小為216頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包含表項(xiàng)的個(gè)數(shù)至少是（ ）。【聯(lián)考 2010】 A.64 B.128 C.256 D.512 【分析】本題目關(guān)鍵是確定頁(yè)目錄號(hào)占用多少位。已知頁(yè)大小為210字節(jié)，頁(yè)表項(xiàng)大小為2字節(jié)，因此，每頁(yè)可以包含29個(gè)頁(yè)表項(xiàng)，即頁(yè)號(hào)部分占用9位；又已知邏輯地址空間大小為216頁(yè)，即頁(yè)目

52、錄號(hào)和頁(yè)號(hào)總共占用16位，因此，頁(yè)目錄號(hào)占用7位，所以應(yīng)該選擇B。精選ppt例：一個(gè)由四個(gè)頁(yè)面（頁(yè)號(hào)為03），每頁(yè)由1024個(gè)字節(jié)組成的程序，把它裝入由8個(gè)物理塊（塊號(hào)為07）組成的存儲(chǔ)器中，裝入情況如下表所示。已知下面的邏輯地址（其中方括號(hào)中的第一個(gè)元素為頁(yè)號(hào)，第二個(gè)元素為頁(yè)內(nèi)地址），請(qǐng)按頁(yè)表求出對(duì)應(yīng)的物理地址。（1）0，100； （2）1，179； （3）2，785；邏輯頁(yè)號(hào)內(nèi)存塊號(hào)03152632解答：因?yàn)槊宽?yè)有1024B，所以內(nèi)存中每塊也有1024B。物理地址 塊號(hào)塊長(zhǎng) + 頁(yè)內(nèi)地址，得到：（1）的物理地址為：31024+100=3072+100=3172 （2）的物理地址為：5102

53、4+179=5120+179=5299（3）的物理地址為：61024+785=6144+785=6929 精選ppt作業(yè)：已知某系統(tǒng)頁(yè)面長(zhǎng)4KB，每個(gè)頁(yè)表項(xiàng)為4B，采用多層分頁(yè)策略映射64位的用戶地址空間。若限定最高層頁(yè)表只占1頁(yè)，則它可采用幾層分頁(yè)策略？精選ppt4.5 基本分段存儲(chǔ)管理方式提出分段管理的目的除了可以提高內(nèi)存空間的利用率外，主要是為了更好地實(shí)現(xiàn)程序的共享和動(dòng)態(tài)鏈接，并方便用戶編程。頁(yè)式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進(jìn)程邏輯相一致。精選ppt4.5.1 分段存儲(chǔ)管理方式的引入 主要是為了滿足用戶的下述一系列要求：1.方便編程。一個(gè)段可定義為一組

54、邏輯信息，如子程序，數(shù)組或工作區(qū)，(分段是程序中自然劃分的一組邏輯意義完整的信息集合，它是用戶在編程時(shí)決定的)。因此，每個(gè)作業(yè)的地址空間是由一些分段構(gòu)成的，每段都有自己的名字，且都是一段連續(xù)的地址空間?？梢?jiàn)，整個(gè)作業(yè)的地址空間是二維的。CALL X|LOAD 1,A|STORE 1,B|分段MAIN(主程序) 01KY：分段X(子程序) 0640D：分段A (數(shù)組) 0500C：分段B(工作區(qū)) 0300精選ppt2.信息共享。一般實(shí)現(xiàn)程序和數(shù)據(jù)共享時(shí)都是以信息的邏輯單位為基礎(chǔ)的。在分頁(yè)系統(tǒng)中的每一頁(yè)都只是存放信息的物理單位，其本身并無(wú)完整意義，因而不便于實(shí)現(xiàn)信息共享，而段卻是信息的邏輯單位，

55、通常是可以表達(dá)某種意義的，采用分段存儲(chǔ)管理，更便于實(shí)現(xiàn)程序和數(shù)據(jù)的共享。3.信息保護(hù)。對(duì)內(nèi)存中的信息的保護(hù)，同樣也是對(duì)信息的邏輯單位進(jìn)行保護(hù)。采用分段存儲(chǔ)管理，對(duì)實(shí)現(xiàn)信息保護(hù)，將是更有效和方便。 4.動(dòng)態(tài)增長(zhǎng)。在實(shí)際使用中，往往有些段，特別是數(shù)據(jù)段會(huì)隨著程序的運(yùn)行不斷增大，而這種增長(zhǎng)事先并不知曉會(huì)增長(zhǎng)到多大，采用其它存儲(chǔ)管理方式是難以應(yīng)付的，而分段存儲(chǔ)管理卻能較好的解決這一問(wèn)題。5.動(dòng)態(tài)鏈接。前面已談到，采用動(dòng)態(tài)鏈接能更有效提高存儲(chǔ)空間的利用率。由于每個(gè)程序模塊構(gòu)成獨(dú)立的分段，并有自己的段名，因而實(shí)現(xiàn)動(dòng)態(tài)鏈接是比較容易的。 精選ppt4.5.2 分段系統(tǒng)的基本原理 1、分段 在分段管理系統(tǒng)中，

56、對(duì)所有地址空間的訪問(wèn)均要求兩個(gè)成分： (1)段的名字； (2)段內(nèi)地址。例如，可按下述調(diào)用：CALL X| 轉(zhuǎn)移到子程序X中的入口點(diǎn)YLOAD 1, A| 將數(shù)組A的D單元的值讀入寄存器1STORE 1,B| 將寄存器1的內(nèi)容存入分段B的C單元中這些符號(hào)程序經(jīng)匯編和裝配后，指令和數(shù)據(jù)的單元地址均由兩部分構(gòu)成：一是表示段名的段號(hào)S；一是位移量W，即段內(nèi)地址。所以，在分段系統(tǒng)中的地址結(jié)構(gòu)有如下形式：段號(hào)S 位移量W 邏輯地址23 1615 0精選ppt 一旦段號(hào)字段和位移量字段的長(zhǎng)度確定后，一個(gè)作業(yè)地址空間中允許的最多段數(shù)及段的長(zhǎng)度也就限定了。上述地址結(jié)構(gòu)表明，該系統(tǒng)可允許一個(gè)作業(yè)有256段，最大

57、段長(zhǎng)為64K字節(jié)。段號(hào)S 位移量W 邏輯地址23 1615 0精選ppt所謂分段管理，就是管理由若干分段組成的作業(yè)，且按分段來(lái)進(jìn)行存儲(chǔ)分配。實(shí)現(xiàn)分段管理的關(guān)鍵在于，如何保證分段(二維)地址空間中的一個(gè)作業(yè)在線性(一維)的存儲(chǔ)空間中正確運(yùn)行。分段式存儲(chǔ)管理的實(shí)現(xiàn)是基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的原理。系統(tǒng)為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)，而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)中。基本分段存儲(chǔ)管理方式中，進(jìn)程運(yùn)行時(shí)，其各段必須全部裝入內(nèi)存。精選ppt2. 段表 為使程序正常運(yùn)行，須在系統(tǒng)中為每個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱“段表”。每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址(段基址)和段的

58、長(zhǎng)度。 段表可以存放在寄存器中，但更多的是存放在內(nèi)存中。 段表可以實(shí)現(xiàn)從邏輯地址到內(nèi)存物理地址的映射。段號(hào)012段首址段長(zhǎng)度58K20K100K110K260K140K精選ppt作業(yè)空間(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K150K10K120K15K80K20K40K30K0123段號(hào)段長(zhǎng)基址段表(S)=310K(D)=215K(X)=120K(MAIN)=030K內(nèi)存空間040K80K120K150K利用段表實(shí)現(xiàn)地址映射:精選ppt3. 地址變換機(jī)構(gòu) 在系統(tǒng)中設(shè)置段表寄存器，用于存放段表始址和段表長(zhǎng)度，以實(shí)現(xiàn)從進(jìn)程的邏輯地址到物理地址的變換。 段表寄

59、存器和段表還有存儲(chǔ)保護(hù)的功能精選ppt段表長(zhǎng)度段表始址段表寄存器物理地址+越界中斷分段系統(tǒng)的地址變換機(jī)構(gòu)1002段號(hào)S位移量W段表92002008K5004K6006K1K段長(zhǎng)基址段號(hào)0123+82928K82928692主存精選ppt 問(wèn)題：當(dāng)段表存放在內(nèi)存中時(shí)，每訪問(wèn)一個(gè)數(shù)據(jù)，都需兩次訪問(wèn)內(nèi)存，降低了計(jì)算機(jī)的速率。 解決方法：設(shè)置聯(lián)想寄存器（快表），用于保存最近常用的段表項(xiàng)。這樣,比起沒(méi)有地址變換的常規(guī)存儲(chǔ)器的存取速度來(lái)僅慢約10%15%.精選ppt Cl Cb+段號(hào)S 段內(nèi)地址d比較比較b + d段表S= Cl快表物理地址段表始址寄存器段表長(zhǎng)度寄存器邏輯地址lb.Slb地址越界d=1d=

60、1地址映射地址越界地址越界比較精選ppt4. 分頁(yè)和分段的主要區(qū)別相似點(diǎn)：采用離散分配方式，通過(guò)地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換不同點(diǎn)：頁(yè)是信息的物理單位，分頁(yè)是為了滿足系統(tǒng)的需要,提高內(nèi)存利用率；段是信息的邏輯單位，含有一組意義相對(duì)完整的信息，分段是為了滿足用戶的需要。頁(yè)的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址，由機(jī)器硬件實(shí)現(xiàn)；段的長(zhǎng)度不固定，取決于用戶程序，編譯程序?qū)υ闯绦蚓幾g時(shí)根據(jù)信息的性質(zhì)劃分。分頁(yè)的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。精選ppt4.5.3 信息共享 分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享，允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段，且對(duì)段的保護(hù)十分簡(jiǎn)單