操作系統(tǒng)第四章存儲(chǔ)器管理

1、第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理本章主要內(nèi)容本章主要內(nèi)容 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.3 連續(xù)分配方式連續(xù)分配方式 4.4 對換對換 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.6 分段存儲(chǔ)管理方式分段存儲(chǔ)管理方式4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.1.1 多級存儲(chǔ)器結(jié)構(gòu)1.存儲(chǔ)器的多層結(jié)構(gòu)2.可執(zhí)行存儲(chǔ)器 寄存器和主存儲(chǔ)器又被稱為可執(zhí)行存儲(chǔ)器 訪問機(jī)制不同，所需耗費(fèi)的時(shí)間不同 進(jìn)程可以在很少的時(shí)鐘周期內(nèi)使用一條load或store指令對可執(zhí)行存儲(chǔ)器進(jìn)行訪問 輔存的訪問通過I/O 設(shè)備來實(shí)現(xiàn)，訪問中將涉及到訪問則中斷、設(shè)備

2、驅(qū)動(dòng)程序以及物理設(shè)備的運(yùn)行，所需耗費(fèi)的時(shí)間相差3個(gè)數(shù)量級甚至更多。4.1.2 主存儲(chǔ)器與寄存器 1主存儲(chǔ)器 主存儲(chǔ)器(簡稱內(nèi)存或主存)是計(jì)算機(jī)系統(tǒng)中一個(gè)主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器 CPU的控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)，數(shù)據(jù)能夠從主存儲(chǔ)器讀取并將它們裝入到寄存器中，或者相反 主存儲(chǔ)器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度，引入寄存器和高速緩存。 2寄存器 寄存器訪問速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十分昂貴，因此容量不可能做得很大 寄存器用于加速存儲(chǔ)器的訪問速度，如用寄存器存放操作數(shù)，或用作地址寄存器加快地址轉(zhuǎn)換速度等4.1.3 高速緩存和磁盤緩存

3、 1高速緩存 高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件，其容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級左右。 根據(jù)程序執(zhí)行的局部性原理，將主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度。 進(jìn)程的程序和數(shù)據(jù)是存放在主存儲(chǔ)器中，每當(dāng)使用時(shí)，被臨時(shí)復(fù)制到一個(gè)速度較快的高速緩存中。 當(dāng)CPU訪問一組特定信息時(shí)，首先檢查它是否在高速緩存中，如果已存在，可直接從中取出使用，以避免訪問主存，否則，再從主存中讀出信息。2磁盤緩存 由于目前磁盤的I/O 速度遠(yuǎn)低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。

4、 磁盤緩存本身并不是一種實(shí)際存在的存儲(chǔ)介質(zhì)，它依托于固定磁盤，提供對主存儲(chǔ)器存儲(chǔ)空間的擴(kuò)充，即利用主存中的存儲(chǔ)空間，來暫存從磁盤中讀出(或?qū)懭?的信息。 主存也可以看做是輔存的高速緩存 一個(gè)文件的數(shù)據(jù)可能出現(xiàn)在存儲(chǔ)器層次的不同級別中，例如，一個(gè)文件數(shù)據(jù)通常被存儲(chǔ)在輔存中(如硬盤)，當(dāng)其需要運(yùn)行或被訪問時(shí)，就必須調(diào)入主存，也可以暫時(shí)存放在主存的磁盤高速緩存中。 大容量的輔存常常使用磁盤，磁盤數(shù)據(jù)經(jīng)常備份到磁帶或可移動(dòng)磁盤組上，以防止硬盤故障時(shí)丟失數(shù)據(jù)本章主要內(nèi)容本章主要內(nèi)容4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接程序的裝入和鏈接 4.2 程序的裝入和鏈接程序的裝入和鏈接如

5、何將一個(gè)用戶源程序變成一個(gè)可在內(nèi)存中執(zhí)如何將一個(gè)用戶源程序變成一個(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過行的程序，通常要經(jīng)過3步驟：步驟： :由編譯程序（由編譯程序（Compiler）將用戶源代碼編）將用戶源代碼編譯成若個(gè)譯成若個(gè)目標(biāo)模塊目標(biāo)模塊 。:由鏈接程序（由鏈接程序（Linker）將編譯后形成的一）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的一起，形成一個(gè)完整的裝入模塊裝入模塊 。:由裝入程序（由裝入程序（Loader）將裝入模塊裝入內(nèi)）將裝入模塊裝入內(nèi)存。存。 1. 程序的裝入程序的裝入 (1)絕對裝入方式絕對裝入方式

6、 如果知道程序?qū)Ⅰv留在如果知道程序?qū)Ⅰv留在內(nèi)存內(nèi)存的什么位置，那么，的什么位置，那么，將產(chǎn)生將產(chǎn)生絕對絕對地址的目標(biāo)代碼。地址的目標(biāo)代碼。 按照裝入模塊中的地址，將程序和按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。數(shù)據(jù)裝入內(nèi)存。 由于程序中的由于程序中的 (2)可重定位裝入方式可重定位裝入方式 由裝入程序?qū)⒀b入模塊裝入內(nèi)存后，裝入模塊中由裝入程序?qū)⒀b入模塊裝入內(nèi)存后，裝入模塊中程序所訪問的所有程序所訪問的所有邏輯地址邏輯地址與實(shí)際裝入內(nèi)存的與實(shí)際裝入內(nèi)存的物物理地址理地址不同不同 ，必須進(jìn)行變換。，必須進(jìn)行變換。把在把在裝入裝入時(shí)對目標(biāo)程序中指令和數(shù)據(jù)的變換過程時(shí)對目標(biāo)程序中指令和數(shù)據(jù)的變換過

7、程稱為重定位。稱為重定位。 因?yàn)榈刂纷儞Q是在因?yàn)榈刂纷儞Q是在裝入裝入時(shí)一次完成的，以后不再時(shí)一次完成的，以后不再改變，故稱為改變，故稱為。 采用采用靜態(tài)靜態(tài)重定位方法將程序裝入內(nèi)存重定位方法將程序裝入內(nèi)存,稱為稱為 裝入程序?qū)⒛繕?biāo)模塊裝入內(nèi)存后，并不立即把裝入程序?qū)⒛繕?biāo)模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序執(zhí)行時(shí)進(jìn)行把這種地址轉(zhuǎn)換推遲到程序執(zhí)行時(shí)進(jìn)行，在硬，在硬件地址變換機(jī)構(gòu)的支持下，隨著對每條指令或件地址變換機(jī)構(gòu)的支持下，隨著對每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行地址變換，故稱為數(shù)據(jù)的訪問自動(dòng)進(jìn)行地址變換，故

8、稱為2. 程序的鏈接程序的鏈接 源程序經(jīng)過編譯后，得到一組目標(biāo)模塊，再利源程序經(jīng)過編譯后，得到一組目標(biāo)模塊，再利用鏈接程序?qū)⑵滏溄有纬裳b入模塊。用鏈接程序?qū)⑵滏溄有纬裳b入模塊。，可把鏈接分成如下三種：，可把鏈接分成如下三種：。在程序。在程序運(yùn)行運(yùn)行之前，先將各目之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊（又稱執(zhí)行模塊），以后不再拆開。的裝配模塊（又稱執(zhí)行模塊），以后不再拆開。 事先進(jìn)行鏈接的方式稱為靜態(tài)鏈接方式。事先進(jìn)行鏈接的方式稱為靜態(tài)鏈接方式。模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模

9、塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊對相對地址進(jìn)行修改對相對地址進(jìn)行修改 目標(biāo)模塊中，使用的都是相對地址，其目標(biāo)模塊中，使用的都是相對地址，其起始地址都為起始地址都為0，在鏈接成一個(gè)裝入模塊時(shí)，在鏈接成一個(gè)裝入模塊時(shí)修改模塊的相對地址。修改模塊的相對地址。 如把原如把原B中的所有相對地址都加上中的所有相對地址都加上L，把，把原原C中所有相對地址都加上中所有相對地址都加上LM。變換外部引用地址變換外部引用地址 將每個(gè)模塊中所用的外部調(diào)用符號也都將每個(gè)模塊中所

10、用的外部調(diào)用符號也都變換為相對地址。例如將變換為相對地址。例如將call B 變換為變換為JSR “L”是指將用戶源程序編譯后所得到的一組目標(biāo)是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接邊裝入邊鏈接的鏈接的鏈接方式。方式。 在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存標(biāo)模塊，并將它裝入內(nèi)存 即即分別裝入各模塊，并且在裝入的過程中修改分別裝入各模塊，并且在裝入的過程中修改相對地址和外部引用地址。相對地址

11、和外部引用地址。 便于修改和更新便于修改和更新 若采用動(dòng)態(tài)鏈接方式，由于各目標(biāo)模塊是分若采用動(dòng)態(tài)鏈接方式，由于各目標(biāo)模塊是分開存放的，所以要修改或更新各目標(biāo)模塊，是件開存放的，所以要修改或更新各目標(biāo)模塊，是件非常容易的事。非常容易的事。便于實(shí)現(xiàn)對目標(biāo)模塊的共享便于實(shí)現(xiàn)對目標(biāo)模塊的共享 在采用裝入時(shí)動(dòng)態(tài)鏈接方式時(shí)，在采用裝入時(shí)動(dòng)態(tài)鏈接方式時(shí)，OS則很容易則很容易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。個(gè)應(yīng)用程序?qū)υ撃K的共享。 各模塊被獨(dú)立裝入系統(tǒng)，而且也不進(jìn)行鏈接，各模塊被獨(dú)立裝入系統(tǒng)，而且也不進(jìn)行鏈接，運(yùn)運(yùn)行時(shí)行時(shí)發(fā)現(xiàn)引用

12、的地址是相對地址或者外部地址時(shí)，發(fā)現(xiàn)引用的地址是相對地址或者外部地址時(shí)，才發(fā)起鏈接，尋找正確的引用地址。才發(fā)起鏈接，尋找正確的引用地址。：凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都：凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。間。該方法是目前最常使用的鏈接方式。該方法是目前最常使用的鏈接方式。本章主要內(nèi)容本章主要內(nèi)容 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.3 連續(xù)分配方式連續(xù)分配方

13、式4.3 連續(xù)分配方式連續(xù)分配方式連續(xù)分配方式，是指連續(xù)分配方式，是指為一個(gè)用戶程序分配為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間一個(gè)連續(xù)的內(nèi)存空間。 連續(xù)分配方式有四種：連續(xù)分配方式有四種：單一連續(xù)分配單一連續(xù)分配固定分區(qū)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配1. 可重定位分區(qū)分配可重定位分區(qū)分配(湯子瀛湯子瀛)4.3.1 單一連續(xù)分配單一連續(xù)分配 這是最早、最簡單的一種存儲(chǔ)分配方式。這是最早、最簡單的一種存儲(chǔ)分配方式。它規(guī)定它規(guī)定整個(gè)內(nèi)存的用戶區(qū)中只駐留一個(gè)用整個(gè)內(nèi)存的用戶區(qū)中只駐留一個(gè)用戶的一個(gè)程序戶的一個(gè)程序，因此該方式，因此該方式只適用于單用只適用于單用戶、單任務(wù)的操作系統(tǒng)戶、單任務(wù)的操

14、作系統(tǒng)。4.3.1 單一連續(xù)分配單一連續(xù)分配為了防止為了防止OS的代碼和數(shù)據(jù)被用戶進(jìn)程所破壞，的代碼和數(shù)據(jù)被用戶進(jìn)程所破壞，把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分：把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分：系統(tǒng)區(qū)：系統(tǒng)區(qū)：僅提供給僅提供給0S使用，通常是放在內(nèi)存的低使用，通常是放在內(nèi)存的低址部分；址部分；用戶區(qū)：用戶區(qū)：是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給唯一的用戶使用，存放用戶程序和數(shù)據(jù)。供給唯一的用戶使用，存放用戶程序和數(shù)據(jù)。 1. 優(yōu)缺點(diǎn)：優(yōu)缺點(diǎn)：簡單、內(nèi)存利用率低。簡單、內(nèi)存利用率低。4.3.2 分區(qū)管理分區(qū)管理-固定分區(qū)分配固定分區(qū)分配固定分區(qū)分配思想：固定分區(qū)分配

15、思想：將內(nèi)存用戶空間劃分為將內(nèi)存用戶空間劃分為若干個(gè)若干個(gè)固定大小固定大小的區(qū)域，每個(gè)區(qū)域稱為一個(gè)的區(qū)域，每個(gè)區(qū)域稱為一個(gè)分區(qū)（分區(qū)（region），在每個(gè)分區(qū)中只裝入），在每個(gè)分區(qū)中只裝入一道一道作業(yè)作業(yè) ，從而支持多道程序并發(fā)設(shè)計(jì)。，從而支持多道程序并發(fā)設(shè)計(jì)。 。當(dāng)程序太小時(shí)，會(huì)造成內(nèi)存空。當(dāng)程序太小時(shí)，會(huì)造成內(nèi)存空間的浪費(fèi)間的浪費(fèi) 。當(dāng)程序太大時(shí)，一個(gè)分區(qū)又不足以。當(dāng)程序太大時(shí)，一個(gè)分區(qū)又不足以裝入該程序，致使該程序無法運(yùn)行。裝入該程序，致使該程序無法運(yùn)行。 ?？砂褍?nèi)存區(qū)劃成含有多個(gè)較小?？砂褍?nèi)存區(qū)劃成含有多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)

16、。 1、如何知道哪些分區(qū)可以分配？、如何知道哪些分區(qū)可以分配？采用分區(qū)描述表記錄每個(gè)分區(qū)的狀態(tài)信息，如下采用分區(qū)描述表記錄每個(gè)分區(qū)的狀態(tài)信息，如下圖所示。圖所示。內(nèi)存分配情況內(nèi)存分配情況分區(qū)分區(qū)編號編號大?。ù笮。↘B） 起始地址起始地址（KB）狀態(tài)狀態(tài)13030分配分配24060分配分配330100分配分配440130未分配未分配540170分配分配作業(yè)作業(yè)D空閑分區(qū)空閑分區(qū)作業(yè)作業(yè)C作業(yè)作業(yè)B作業(yè)作業(yè)A操作系統(tǒng)操作系統(tǒng)03060100130170210分區(qū)描述表分區(qū)描述表 2、如何分配各分區(qū)？、如何分配各分區(qū)？當(dāng)有作業(yè)要裝入內(nèi)存時(shí)，當(dāng)有作業(yè)要裝入內(nèi)存時(shí)，內(nèi)存分配程序內(nèi)存分配程序檢索分檢索分

17、區(qū)描述表，從中找出尚未使用的區(qū)描述表，從中找出尚未使用的最接近大小最接近大小的分的分區(qū)分配給該作業(yè)，然后修改分區(qū)的狀態(tài)；如果找區(qū)分配給該作業(yè)，然后修改分區(qū)的狀態(tài)；如果找不到合適的分區(qū)就拒絕為該作業(yè)分配內(nèi)存。不到合適的分區(qū)就拒絕為該作業(yè)分配內(nèi)存。當(dāng)程序運(yùn)行完成時(shí)，系統(tǒng)回收內(nèi)存資源，并修當(dāng)程序運(yùn)行完成時(shí)，系統(tǒng)回收內(nèi)存資源，并修改分區(qū)描述表中分區(qū)的狀態(tài)。改分區(qū)描述表中分區(qū)的狀態(tài)。4.3.2 分區(qū)管理分區(qū)管理-固定分區(qū)分配固定分區(qū)分配 固定分區(qū)式分配固定分區(qū)式分配 的的優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)：可運(yùn)行多道程：可運(yùn)行多道程序的存儲(chǔ)管理方式序的存儲(chǔ)管理方式 。存在。存在“內(nèi)零頭內(nèi)零頭”會(huì)造成會(huì)造成存儲(chǔ)空間的浪費(fèi)。存儲(chǔ)

18、空間的浪費(fèi)。 內(nèi)零頭內(nèi)零頭在分區(qū)內(nèi)沒有利用的部分稱為在分區(qū)內(nèi)沒有利用的部分稱為內(nèi)零頭。內(nèi)零頭。4.3.3 分區(qū)管理分區(qū)管理-動(dòng)態(tài)分區(qū)方式動(dòng)態(tài)分區(qū)方式 動(dòng)態(tài)分區(qū)分配思想：動(dòng)態(tài)分區(qū)分配思想：分區(qū)數(shù)量和大小都不固分區(qū)數(shù)量和大小都不固定，根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)定，根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。存空間。 記錄系統(tǒng)中各空閑分區(qū)的情況，以便分配時(shí)能記錄系統(tǒng)中各空閑分區(qū)的情況，以便分配時(shí)能找到可以分配的空間。找到可以分配的空間。在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況（包含空閑分區(qū)號、分區(qū)大小、錄每個(gè)空閑分區(qū)的情況（包含空閑分區(qū)號、分

19、區(qū)大小、起始地址）。起始地址）。 。為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，設(shè)置前向指針和后向指針，通過前、后向鏈接指針將設(shè)置前向指針和后向指針，通過前、后向鏈接指針將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。所有的空閑分區(qū)鏈接成一個(gè)雙向鏈?？臻e分區(qū)鏈表空閑分區(qū)鏈表前向指針N20N個(gè)字節(jié)可用后向指針N20(2) 分區(qū)分配算法分區(qū)分配算法 )：要求要求空閑分空閑分區(qū)鏈以地址遞增的次序鏈接區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止。滿足要求的空閑分區(qū)為止。為大作業(yè)分配大的內(nèi)

20、存空間創(chuàng)造了為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。低址部分不斷被劃分，會(huì)留下許多難條件。低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑分區(qū)。以利用的、很小的空閑分區(qū)。 : 將所有的空將所有的空閑分區(qū)構(gòu)成一個(gè)循環(huán)鏈表。每次查找時(shí)不是閑分區(qū)構(gòu)成一個(gè)循環(huán)鏈表。每次查找時(shí)不是從頭開始，而是從上次結(jié)束位置開始。從頭開始，而是從上次結(jié)束位置開始。能使內(nèi)存中的空閑分區(qū)分布得更均能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會(huì)缺乏大的空閑分區(qū)。這樣會(huì)缺乏大的空閑分區(qū)?？偸前涯軡M足要求、又是最小的空閑分區(qū)分配給作總是把能滿足要求、又是最小的空閑

21、分區(qū)分配給作業(yè)，避免業(yè)，避免“大材小用大材小用” 該算法要求將所有的空閑分區(qū)按其容量以該算法要求將所有的空閑分區(qū)按其容量以從小到從小到大大的順序形成一空閑分區(qū)鏈。從頭開始查找的順序形成一空閑分區(qū)鏈。從頭開始查找，將表中，將表中第一個(gè)大于所需求空間大小的空閑區(qū)分配給作業(yè)第一個(gè)大于所需求空間大小的空閑區(qū)分配給作業(yè)。為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。每為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。每次分配后所切割下來的剩余部分總是最小的，這樣，次分配后所切割下來的剩余部分總是最小的，這樣，在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。 4.最壞適應(yīng)算法 與最佳適應(yīng)算法相反，

22、選擇一個(gè)最大的空閑區(qū)，分割一部分給作業(yè)使用，缺乏大的空閑分區(qū)。 優(yōu)點(diǎn)：剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小，有利于中，小作業(yè)； 查找效率很高。 在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中，主要的操作是分配內(nèi)存和回收內(nèi)存。 系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈中找到所需大小的分區(qū)。Size 是事先規(guī)定的不再切割的剩余分區(qū)的大小。（3）分區(qū)回收）分區(qū)回收 當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，需當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，需相鄰的空閑分區(qū)相鄰的空閑分區(qū)，形成大的分區(qū)，稱為合并技術(shù)。形成大的分區(qū)，稱為合并技術(shù)。 需要合并的情況有如下圖所示的三種，不論哪種情況，需要合并的情況有如下圖所示的三種，不論哪種情況，只需修改相應(yīng)的分

23、區(qū)信息來完成合并即可。只需修改相應(yīng)的分區(qū)信息來完成合并即可?；厥辗謪^(qū)前有空閑分區(qū)回收分區(qū)前有空閑分區(qū) 回收分區(qū)后有空閑分區(qū)回收分區(qū)后有空閑分區(qū) 回收分區(qū)前后都有空閑分區(qū)回收分區(qū)前后都有空閑分區(qū) 4.3.4 動(dòng)態(tài)分區(qū)示例動(dòng)態(tài)分區(qū)示例-快速適應(yīng)算法快速適應(yīng)算法 該算法又稱為分類搜索法 空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表 內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。 空閑分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分，如2 KB、4 KB、8 KB等，對于其它大小的分區(qū)，如7 KB這樣

24、的空閑區(qū)，既可以放在8 KB的鏈表中，也可以放在一個(gè)特殊的空閑區(qū)鏈表中。 優(yōu)點(diǎn)：查找效率高，僅需要根據(jù)進(jìn)程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進(jìn)行分配即可。 進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對大空間的需求，也不會(huì)產(chǎn)生內(nèi)存碎片。 缺點(diǎn)：分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開銷較大。 分配空閑分區(qū)時(shí)是以進(jìn)程為單位，一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中，或多或少地存在一定的浪費(fèi)?？臻e分區(qū)劃分越細(xì)，浪費(fèi)則越嚴(yán)重，整體上會(huì)造成可觀的存儲(chǔ)空間浪費(fèi)，這是典型的以空間換時(shí)間的作法。4.3.5 分區(qū)管理分區(qū)管理-動(dòng)態(tài)分區(qū)示例動(dòng)態(tài)分區(qū)示例-伙伴系統(tǒng)伙伴

25、系統(tǒng) 伙伴系統(tǒng)是一種不需要緊湊的動(dòng)態(tài)分區(qū)算法?；锇橄到y(tǒng)是一種不需要緊湊的動(dòng)態(tài)分區(qū)算法。 伙伴系統(tǒng)是內(nèi)存塊管理機(jī)制，采用伙伴系統(tǒng)是內(nèi)存塊管理機(jī)制，采用二進(jìn)制數(shù)二進(jìn)制數(shù)的方式來分配和回收空間。提高回收空間時(shí)的方式來分配和回收空間。提高回收空間時(shí)合并空閑分區(qū)的速度，合并空閑分區(qū)的速度，Linux操作系統(tǒng)使用操作系統(tǒng)使用該算法分配和回收頁面塊。該算法分配和回收頁面塊。 優(yōu)點(diǎn)：分配和回收內(nèi)存速度快，且不會(huì)產(chǎn)生優(yōu)點(diǎn)：分配和回收內(nèi)存速度快，且不會(huì)產(chǎn)生很多小碎片。很多小碎片。 缺點(diǎn)：內(nèi)存利用率不高，分配的內(nèi)存大小為缺點(diǎn)：內(nèi)存利用率不高，分配的內(nèi)存大小為2的冪，假如只需要的冪，假如只需要65個(gè)頁面，也需要分配個(gè)

26、頁面，也需要分配128個(gè)頁面的塊，從而浪費(fèi)了個(gè)頁面的塊，從而浪費(fèi)了63個(gè)頁面，即個(gè)頁面，即產(chǎn)生內(nèi)部碎片。產(chǎn)生內(nèi)部碎片。4.3.5伙伴系統(tǒng) 伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2 的k 次冪，k 為整數(shù)， lkm，其中：21 表示分配的最小分區(qū)的大小，2m 表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。 假設(shè)系統(tǒng)的可利用空間容量為2m個(gè)字，則系統(tǒng)開始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分區(qū)。 在系統(tǒng)運(yùn)行過程中，由于不斷的劃分，可能會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)， 將這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每一類具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。

27、 不同大小的空閑分區(qū)形成了k(0km)個(gè)空閑分區(qū)鏈表 當(dāng)需要為進(jìn)程分配一個(gè)長度為n 的存儲(chǔ)空間時(shí)，首首先先計(jì)算一個(gè)i 值，使2i-1 越界； 段內(nèi)地址段長-越界 像分頁系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時(shí)，每要訪問一個(gè)數(shù)據(jù)，都須訪問兩次內(nèi)存，從而極大地降低了計(jì)算機(jī)的速率。 解決的方法增設(shè)一個(gè)聯(lián)想存儲(chǔ)器，用于保存最近常用的段表項(xiàng)。 段比頁大，段表項(xiàng)的數(shù)目比頁表項(xiàng)少，聯(lián)想存儲(chǔ)器也相對較小，便可以顯著地減少存取數(shù)據(jù)的時(shí)間 比起沒有地址變換的常規(guī)存儲(chǔ)器的存取速度來僅慢約10%15% 4分頁和分段的主要區(qū)別 ：（1）頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率。分頁僅僅是由

28、于系統(tǒng)管理的需要而不是用戶的需要. 段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。 （2）頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面； 段的長度不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。 （3）分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址； 分段的作業(yè)地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。 4.6.3信息共享 分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)，是易

29、于實(shí)現(xiàn)段的共享，即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段，且對段的保護(hù)也十分簡單易行。 在分頁系統(tǒng)中，實(shí)現(xiàn)代碼共享應(yīng)在每個(gè)進(jìn)程的頁表中都建立相同個(gè)頁表項(xiàng)和占用相同的頁號。例子 有一個(gè)多用戶系統(tǒng)，可同時(shí)接納40個(gè)用戶，他們都執(zhí)行一個(gè)文本編輯程序(Text Editor)。如果文本編輯程序有160 KB的代碼和另外40 KB的數(shù)據(jù)區(qū)， 則總共需有 8 MB的內(nèi)存空間來支持40 個(gè)用戶。 如果160 KB的代碼是可重入的(Reentrant)，則無論是在分頁系統(tǒng)還是在分段系統(tǒng)中，該代碼都能被共享，在內(nèi)存中只需保留一份文本編輯程序的副本，此時(shí)所需的內(nèi)存空間僅為 1760 KB(4040+160)，而不是8000 KB。 假定每個(gè)頁面的大小為 4 KB，那么，160 KB的代碼將占用 40 個(gè)頁面，數(shù)據(jù)區(qū)占 10 個(gè)頁面。 為實(shí)現(xiàn)代碼的共享，應(yīng)在每個(gè)進(jìn)程的頁表中都建立40個(gè)頁表項(xiàng)，它們的物理塊號都是21#60#。 在每個(gè)進(jìn)程的頁表中，還須為自己的數(shù)據(jù)區(qū)建立頁表項(xiàng)，它們的物理塊號分別是61#70#、71#80#、81#90#，等等 圖4-19 分頁系統(tǒng)中共享editor的示意圖 圖4-20 分段系統(tǒng)中