《存儲器管理》 (2)

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

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

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

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

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

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

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

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

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

10、模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時，才對它進(jìn)行鏈接。精選ppt一、靜態(tài)鏈接： (Static Linking) 事先將幾個目標(biāo)鏈接裝配成一個裝入模塊，以后不再拆開的鏈接方式，稱為靜態(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)庫當(dāng)前生成的目 標(biāo) 庫私有目標(biāo)庫MAIN .call SEQAM.call SURB 1.

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

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

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

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

15、用的存儲管理方法。在實現(xiàn)過程中涉及三個問題：分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配算法分區(qū)分配與回收操作精選ppt一、可變分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 常用的數(shù)據(jù)結(jié)構(gòu)有： 1. 空閑分區(qū)表： 序號始址長度115K23K248K20K380K30K.2. 空閑分區(qū)鏈：N個字節(jié)可用（未分配）狀態(tài)位 大小 指針 0 N+2 前向指針 0 N+2 后向 指針 精選ppt精選ppt2. 分區(qū)分配算法系統(tǒng)運行一段時間后，在整個存儲空間內(nèi)將出現(xiàn)許多大小不等的區(qū)域，有的仍被作業(yè)進(jìn)程占用，有的則因作業(yè)已退出系統(tǒng)而成為可用于再分配的區(qū)域。現(xiàn)在假設(shè)有一個新的作業(yè)需調(diào)入主存，如何為其選擇一個合適的區(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)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從頭到尾不存在滿足要求的分區(qū)，則分配失敗。優(yōu)點：算法簡單，查找速度快；優(yōu)先利用內(nèi)存低址部分的空閑分區(qū),留在高址部分的大的空白區(qū)被劃分的機會較少，因而在大作業(yè)到來時也比較容易得到滿足。缺點：低址部分不斷劃分，產(chǎn)生小碎片；每次查找從低址部分開始，

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

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

19、k20k例：有四塊空白區(qū)(從小容量大容量)，來了一個作業(yè)需分配19k內(nèi)存。指針10k20k60k90k1k解：再排序精選ppt練習(xí)： 某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB（初始為空閑），采用最佳適配（Best Fit）算法，分配和釋放的順序為：分配15MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時主存中最大空閑分區(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)存時，總是把能滿足要求、又是最大的空閑分區(qū)分配給作業(yè)。要求

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

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

22、它兩種對該作業(yè)序列是不合適的。精選pptOS30K使用20K使用5K使用46K020K100K160K210K255K分區(qū)號大小起始地址130K20K220K100K35K160K446K210K首次適應(yīng)算法空閑分區(qū)表分區(qū)號大小起始地址15K160K220K100K330K20K446K210K最佳適應(yīng)算法空閑分區(qū)表分區(qū)號大小起始地址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)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一種空閑分區(qū)類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、錄號和頁號總共占用16位，因此，頁目錄號占用7位，所以應(yīng)該選擇B。精選ppt例：一個由四個頁面（頁號為03），每頁由1024個字節(jié)組成的程序，把它裝入由8個物理塊（塊號為07）組成的存儲器中，裝入情況如下表所示。已知下面的邏輯地址（其中方括號中的第一個元素為頁號，第二個元素為頁內(nèi)地址），請按頁表求出對應(yīng)的物理地址。（1）0，100； （2）1，179； （3）2，785；邏輯頁號內(nèi)存塊號03152632解答：因為每頁有1024B，所以內(nèi)存中每塊也有1024B。物理地址 塊號塊長 + 頁內(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)頁面長4KB，每個頁表項為4B，采用多層分頁策略映射64位的用戶地址空間。若限定最高層頁表只占1頁，則它可采用幾層分頁策略？精選ppt4.5 基本分段存儲管理方式提出分段管理的目的除了可以提高內(nèi)存空間的利用率外，主要是為了更好地實現(xiàn)程序的共享和動態(tài)鏈接，并方便用戶編程。頁式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進(jìn)程邏輯相一致。精選ppt4.5.1 分段存儲管理方式的引入 主要是為了滿足用戶的下述一系列要求：1.方便編程。一個段可定義為一組

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

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

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

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

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

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

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