《操作系統(tǒng)原理通用課件.ppt》由會員分享，可在線閱讀，更多相關《操作系統(tǒng)原理通用課件.ppt（168頁珍藏版）》請在匯文網(wǎng)上搜索。

1、第二章 存 儲 管 理 1第二章第二章 存儲管理存儲管理 2.1 2.1 存儲管理基礎存儲管理基礎 2.2 2.2 基本存儲管理方法基本存儲管理方法 2.3 2.3 可變分區(qū)存儲管理方法可變分區(qū)存儲管理方法 2.4 2.4 內(nèi)存擴充技術內(nèi)存擴充技術 2.5 2.5 純分頁的存儲管理純分頁的存儲管理 2.6 2.6 請求分頁系統(tǒng)請求分頁系統(tǒng) 2.7 2.7 段式存儲管理段式存儲管理 2.8 2.8 段頁式存儲管理段頁式存儲管理 2.9 Linux2.9 Linux存儲管理存儲管理第二章 存 儲 管 理 2存儲器可分為：內(nèi)存儲器和外存儲器；存儲器可分為：內(nèi)存儲器和外存儲器；內(nèi)存儲器：可以被內(nèi)存儲器

2、：可以被CPU直接訪問。直接訪問。外存儲器：不可以被外存儲器：不可以被CPU直接訪問，外存與直接訪問，外存與CPU之間只能夠在輸入輸出控制系統(tǒng)的管理下，進行信之間只能夠在輸入輸出控制系統(tǒng)的管理下，進行信息交換。息交換。第二章 存 儲 管 理 32.1 2.1 存儲管理基礎存儲管理基礎 2.1.1 2.1.1 虛擬地址與物理地址虛擬地址與物理地址第二章 存 儲 管 理 4內(nèi)存儲器是由一個個存儲單元組成，一個存儲單元可存放內(nèi)存儲器是由一個個存儲單元組成，一個存儲單元可存放若干個二進制的位（若干個二進制的位（bit），），8個二進制位被稱為一個字節(jié)個二進制位被稱為一個字節(jié)（Byte）。）。內(nèi)存中的存

3、儲單元按一定順序進行編號，每個單元所對應內(nèi)存中的存儲單元按一定順序進行編號，每個單元所對應的編號，稱為該單元的單元地址。的編號，稱為該單元的單元地址。物理地址物理地址（絕對地址，實地址）：內(nèi)存中存儲單元的地址。（絕對地址，實地址）：內(nèi)存中存儲單元的地址。物理地址可直接尋址。物理地址可直接尋址。邏輯地址邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式。編譯后形成目標代碼，目標代碼通常采用相對地址的形式。其首地址為其首地址為0 0，其余指令中的地址都相對于首地址來編，其余指令中的地址都相對于首地址來編址。

4、址。不能用邏輯地址在內(nèi)存中讀取信息。不能用邏輯地址在內(nèi)存中讀取信息。第二章 存 儲 管 理 5第二章 存 儲 管 理 6地址重定位地址重定位地址重定位（地址映射）地址重定位（地址映射）：將用戶程序中的邏輯地址：將用戶程序中的邏輯地址轉換為運行時由機器直接尋址的物理地址。轉換為運行時由機器直接尋址的物理地址。當程序裝入內(nèi)存時當程序裝入內(nèi)存時,操作系統(tǒng)要為該程序分配一個合操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物程序的邏輯地址與分配到內(nèi)存物理地址不一致理地址不一致,而而CPUCPU執(zhí)行指令時，是按物理地址進行執(zhí)行指令時，是按物理地址進行的，所以要進

5、行地址轉換。的，所以要進行地址轉換。第二章 存 儲 管 理 72.1.2 地址定位方式地址定位方式1.固定定位方式固定定位方式 由程序員在編寫程序時或由編譯連接程序對源程序進由程序員在編寫程序時或由編譯連接程序對源程序進行編譯連接時，直接指定程序在執(zhí)行時訪問的實際存儲器行編譯連接時，直接指定程序在執(zhí)行時訪問的實際存儲器地址的方式稱為固定定位方式。此種定位方式一般只適合地址的方式稱為固定定位方式。此種定位方式一般只適合于單板機或單用戶系統(tǒng)。在多道程序環(huán)境下，應保證各個于單板機或單用戶系統(tǒng)。在多道程序環(huán)境下，應保證各個作業(yè)的地址互不重疊，這就比較困難了。作業(yè)的地址互不重疊，這就比較困難了。第二章

6、存 儲 管 理 8第二章 存 儲 管 理 92.靜態(tài)重定位方式靜態(tài)重定位方式 源程序經(jīng)編譯和連接后生成目標代碼中的地址是以源程序經(jīng)編譯和連接后生成目標代碼中的地址是以0為起始地址的相對地址。為起始地址的相對地址。當需要執(zhí)行時，由裝入程序運行重定位程序模塊，當需要執(zhí)行時，由裝入程序運行重定位程序模塊，根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標代碼裝到指定內(nèi)存地址中，代碼裝到指定內(nèi)存地址中，并修改所有有關地址部分的并修改所有有關地址部分的值值。修改的方式是對每一個邏輯地址的值加上內(nèi)存區(qū)首修改的方式是對每一個邏輯地址的值加上內(nèi)存區(qū)首地址（或稱基地

7、址）值。地址（或稱基地址）值。第二章 存 儲 管 理 10第二章 存 儲 管 理 11靜態(tài)重定位的特點靜態(tài)重定位的特點（1 1）靜態(tài)重定位是在程序運行之前完成地址重定位工作的；靜態(tài)重定位是在程序運行之前完成地址重定位工作的；（2 2）靜態(tài)重定位由軟件實現(xiàn)，無須硬件提供支持；靜態(tài)重定位由軟件實現(xiàn)，無須硬件提供支持；（3 3）實行靜態(tài)重定位時，地址重定位工作是在程序裝入時被實行靜態(tài)重定位時，地址重定位工作是在程序裝入時被一次集中完成的；一次集中完成的；（4 4）絕對地址空間里的目標程序與原相對地址空間里的目標絕對地址空間里的目標程序與原相對地址空間里的目標程序面目已不相同，因為前者進行了地址調整；

8、程序面目已不相同，因為前者進行了地址調整；（5 5）實施靜態(tài)重定位后，若用戶程序在內(nèi)存中做了移動，那實施靜態(tài)重定位后，若用戶程序在內(nèi)存中做了移動，那么程序指令中的地址就不再反映所在的存儲位置了，除非么程序指令中的地址就不再反映所在的存儲位置了，除非重新進行地址重定位。重新進行地址重定位。第二章 存 儲 管 理 123.動態(tài)重定位方式動態(tài)重定位方式 采用動態(tài)重定位方式，將程序在裝入內(nèi)存時，不必修采用動態(tài)重定位方式，將程序在裝入內(nèi)存時，不必修改程序的邏輯地址值，程序執(zhí)行期間在訪問內(nèi)存之前，改程序的邏輯地址值，程序執(zhí)行期間在訪問內(nèi)存之前，再實時地將邏輯地址變換成物理地址。動態(tài)重定位要靠再實時地將邏輯

9、地址變換成物理地址。動態(tài)重定位要靠硬件地址變換機構實現(xiàn)。硬件地址變換機構實現(xiàn)。當程序開始執(zhí)行時，系統(tǒng)將程序在內(nèi)存的起始地址送當程序開始執(zhí)行時，系統(tǒng)將程序在內(nèi)存的起始地址送入地址變換機構中的入地址變換機構中的基地址寄存器基地址寄存器BR中。中。在執(zhí)行指令時，若涉及到邏輯地址，則先將該地址送在執(zhí)行指令時，若涉及到邏輯地址，則先將該地址送入入虛擬地址寄存器虛擬地址寄存器 VR，再將，再將BR 和和 VR 中的值相加后送中的值相加后送入地址寄存器入地址寄存器 MR，并按，并按 MR 中的值訪問內(nèi)存。中的值訪問內(nèi)存。（MR）=（BR）+（VR）第二章 存 儲 管 理 13第二章 存 儲 管 理 142.

10、2 2.2 基本存儲管理方法基本存儲管理方法2.2.1 單一連續(xù)分區(qū)存儲管理單一連續(xù)分區(qū)存儲管理 基本思想基本思想：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。應用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務的最簡單，適用于單用戶、單任務的OS；單用戶系；單用戶系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存。統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存。第二章 存 儲 管 理 15特點特點（1）系統(tǒng)總是把整個用戶區(qū)分配給一個用戶使用。系統(tǒng)總是把整個用戶區(qū)分配給一個用戶使用。（2）實際上，內(nèi)存用戶區(qū)又被分為實際上，內(nèi)存用戶

11、區(qū)又被分為“使用區(qū)使用區(qū)”和和“空閑區(qū)空閑區(qū)”兩部分。兩部分。在操作系統(tǒng)中，把分配給用戶、但又未使用的區(qū)域稱為在操作系統(tǒng)中，把分配給用戶、但又未使用的區(qū)域稱為“內(nèi)部碎片內(nèi)部碎片”。（3）由于任何時刻內(nèi)存的用戶區(qū)中只有一個作業(yè)運行，因由于任何時刻內(nèi)存的用戶區(qū)中只有一個作業(yè)運行，因此這種系統(tǒng)只使用于單用戶的情況。此這種系統(tǒng)只使用于單用戶的情況。（4）進入內(nèi)存的作業(yè)，獨享系統(tǒng)中的所有資源，包括內(nèi)存進入內(nèi)存的作業(yè)，獨享系統(tǒng)中的所有資源，包括內(nèi)存中的整個用戶區(qū)。中的整個用戶區(qū)。第二章 存 儲 管 理 16特點特點（5）由于整個用戶區(qū)都分配給了一個用戶使用，因此作業(yè)由于整個用戶區(qū)都分配給了一個用戶使用，因

12、此作業(yè)進入用戶區(qū)后，沒有移動的必要。采用這種存儲分配策進入用戶區(qū)后，沒有移動的必要。采用這種存儲分配策略時，將對用戶程序實行略時，將對用戶程序實行靜態(tài)重定位靜態(tài)重定位。（6）實行靜態(tài)重定位，并不能阻止用戶有意無意地通過不實行靜態(tài)重定位，并不能阻止用戶有意無意地通過不恰當?shù)刂噶铌J入操作系統(tǒng)所占用的存儲區(qū)域，如何阻止恰當?shù)刂噶铌J入操作系統(tǒng)所占用的存儲區(qū)域，如何阻止對操作系統(tǒng)的侵擾，就是所謂的對操作系統(tǒng)的侵擾，就是所謂的“存儲保護存儲保護”問題。問題。用于存儲保護的專用寄存器用于存儲保護的專用寄存器“界限寄存器界限寄存器”第二章 存 儲 管 理 17存儲保護過程存儲保護過程：在：在用戶態(tài)用戶態(tài)下，對

13、內(nèi)存的每一次訪問，都下，對內(nèi)存的每一次訪問，都要要在硬件的控制在硬件的控制下，與界限寄存器中的內(nèi)容進行比較。下，與界限寄存器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會產(chǎn)生產(chǎn)生“地址越界地址越界”中斷，阻止這次訪問的進行。中斷，阻止這次訪問的進行。優(yōu)點優(yōu)點：易于管理，便于用戶的了解和使用。：易于管理，便于用戶的了解和使用。缺點缺點：由于每次只能有一個作業(yè)進入內(nèi)存，故它不適用于多由于每次只能有一個作業(yè)進入內(nèi)存，故它不適用于多道程序設計，整個系統(tǒng)的工作效率不高，資源利用率道程序設計，整個系統(tǒng)的工作效率不高，資源利用率底下。底下。

14、只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會形成碎片，只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會形成碎片，造成內(nèi)存儲器資源的浪費。造成內(nèi)存儲器資源的浪費。若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)就無法運行。就無法運行。第二章 存 儲 管 理 182.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理 把內(nèi)存區(qū)把內(nèi)存區(qū)固定固定地劃分為若干個大小相等（和不等）的地劃分為若干個大小相等（和不等）的連續(xù)分區(qū)。連續(xù)分區(qū)。每個分區(qū)裝一個且只能裝每個分區(qū)裝一個且只能裝一個一個作業(yè)，分區(qū)作業(yè)，分區(qū)的劃分原則一般由系統(tǒng)操作員或操作系統(tǒng)決定，分區(qū)的劃分原則一般由系統(tǒng)操作員或操作系統(tǒng)

15、決定，分區(qū)一旦劃分結束，在整個執(zhí)行過程中每個分區(qū)的一旦劃分結束，在整個執(zhí)行過程中每個分區(qū)的長度長度和和內(nèi)存的總分區(qū)內(nèi)存的總分區(qū)個數(shù)個數(shù)將將保持不變保持不變。分區(qū)大小相等分區(qū)大小相等：只適合于多個相同程序的并發(fā)執(zhí)行：只適合于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象）。（處理多個類型相同的對象）。分區(qū)大小不等：分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、少量多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當前空閑的、適當?shù)拇蠓謪^(qū)。根據(jù)程序的大小，分配當前空閑的、適當大小的分區(qū)。大小的分區(qū)。第二章 存 儲 管 理 19固定分區(qū)固定分區(qū)固定分區(qū)固定分區(qū)(大小相同大小相同大小相同大小相

16、同)固定分區(qū)固定分區(qū)固定分區(qū)固定分區(qū)(多種大小多種大小多種大小多種大小)第二章 存 儲 管 理 20內(nèi)存分配內(nèi)存分配 為了便于內(nèi)存分配，通常將分區(qū)按大小進行排隊，為了便于內(nèi)存分配，通常將分區(qū)按大小進行排隊，并為之建立一張分區(qū)說明表，其中各表項包括每個分區(qū)并為之建立一張分區(qū)說明表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。的起始地址、大小及狀態(tài)（是否已分配）。當有一用戶程序要裝入時，由內(nèi)存分配程序檢索該當有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該應用程序，然后將該表項中的狀

17、態(tài)置為之分配給該應用程序，然后將該表項中的狀態(tài)置為“已已分配分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。序分配內(nèi)存。第二章 存 儲 管 理 21第二章 存 儲 管 理 22地址重定位與存儲保護地址重定位與存儲保護固定分區(qū)存儲管理中，每個分區(qū)只允許裝入一個作業(yè)，固定分區(qū)存儲管理中，每個分區(qū)只允許裝入一個作業(yè)，作業(yè)在運行期間沒有必要移動自己的位置，因此，應作業(yè)在運行期間沒有必要移動自己的位置，因此，應該對程序實行該對程序實行靜態(tài)重定位靜態(tài)重定位。在固定分區(qū)存儲管理中，不僅要防止用戶程序對操作在固定分區(qū)存儲管理中，不僅要防止用戶程序對操作系統(tǒng)

18、形成的侵擾，也要防止用戶程序與用戶程序之間系統(tǒng)形成的侵擾，也要防止用戶程序與用戶程序之間形成侵擾。因此必須在形成侵擾。因此必須在CPU中設置一對專用的寄存器，中設置一對專用的寄存器，用于存儲保護。將兩個專用寄存器分別起名為用于存儲保護。將兩個專用寄存器分別起名為“下下界界寄存器寄存器”和和“上界寄存器上界寄存器”第二章 存 儲 管 理 23存儲保護過程存儲保護過程當進程調度程序調度某個作業(yè)進程運行時，就把該作當進程調度程序調度某個作業(yè)進程運行時，就把該作業(yè)所在分區(qū)的低邊界地址裝入到低界限寄存器，高邊業(yè)所在分區(qū)的低邊界地址裝入到低界限寄存器，高邊界地址裝入到高界限寄存器。作業(yè)運行時，對內(nèi)存的界地

19、址裝入到高界限寄存器。作業(yè)運行時，對內(nèi)存的每一次訪問，都要每一次訪問，都要在硬件的控制在硬件的控制下，與兩個界限寄存下，與兩個界限寄存器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會產(chǎn)生限寄存器中的地址，就會產(chǎn)生“地址越界地址越界”中斷，阻中斷，阻止這次訪問的進行。止這次訪問的進行。第二章 存 儲 管 理 24固定分區(qū)存儲管理的特點固定分區(qū)存儲管理的特點（1）它是最簡單的、具有）它是最簡單的、具有“多道多道”色彩的存儲管理方色彩的存儲管理方案。案。（2）當把一個分區(qū)分配給某個作業(yè)時，該作業(yè)的程序）當把一個分區(qū)分配給某個作業(yè)時，該

20、作業(yè)的程序將一次性的全部被裝入到分配給它的連續(xù)分區(qū)里。將一次性的全部被裝入到分配給它的連續(xù)分區(qū)里。第二章 存 儲 管 理 25優(yōu)點：易于實現(xiàn)，開銷小。優(yōu)點：易于實現(xiàn)，開銷小。缺點：缺點：內(nèi)碎片造成浪費（小作業(yè)不能有效地利用分區(qū)空間。內(nèi)碎片造成浪費（小作業(yè)不能有效地利用分區(qū)空間。分區(qū)總數(shù)在系統(tǒng)生成時確定（固定），限制了并發(fā)分區(qū)總數(shù)在系統(tǒng)生成時確定（固定），限制了并發(fā)執(zhí)行的程序數(shù)目。執(zhí)行的程序數(shù)目。如果到達作業(yè)的尺寸比任何一個分區(qū)的長度都大，如果到達作業(yè)的尺寸比任何一個分區(qū)的長度都大，那么它就無法得到運行。那么它就無法得到運行。固定分區(qū)方式的評價固定分區(qū)方式的評價第二章 存 儲 管 理 262.3

21、 2.3 可變分區(qū)存儲管理可變分區(qū)存儲管理 基本思想：基本思想：內(nèi)存不是預先劃分好的，而是當作業(yè)裝入內(nèi)存不是預先劃分好的，而是當作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進若有足夠的空間，則按需要分割一部分分區(qū)給該進程程否則令其等待主存空間否則令其等待主存空間優(yōu)點優(yōu)點：沒有內(nèi)碎片。：沒有內(nèi)碎片。缺點缺點：有外碎片。：有外碎片。第二章 存 儲 管 理 27外部碎片問題外部碎片問題操作系統(tǒng)操作系統(tǒng)20KB0256KB作業(yè)作業(yè)A(16KB)A(16KB)空閑區(qū)空閑區(qū)(236KB)空閑區(qū)

22、空閑區(qū)(220KB)作業(yè)作業(yè)B(100KB)B(100KB)空閑區(qū)空閑區(qū)(120KB)(120KB)作業(yè)作業(yè)C(70KB)C(70KB)空閑區(qū)空閑區(qū)(50KB)(50KB)空閑區(qū)空閑區(qū)(100KB)(100KB)作業(yè)作業(yè)D(75KB)D(75KB)空閑區(qū)空閑區(qū)(25KB)(25KB)內(nèi)碎片：內(nèi)碎片：內(nèi)碎片：內(nèi)碎片：占用分占用分占用分占用分區(qū)之內(nèi)未被利用區(qū)之內(nèi)未被利用區(qū)之內(nèi)未被利用區(qū)之內(nèi)未被利用的空間的空間的空間的空間外碎片外碎片外碎片外碎片：占用分：占用分：占用分：占用分區(qū)之間難以利用區(qū)之間難以利用區(qū)之間難以利用區(qū)之間難以利用的空閑分區(qū)（通的空閑分區(qū)（通的空閑分區(qū)（通的空閑分區(qū)（通常是小空閑分

23、區(qū)）常是小空閑分區(qū)）常是小空閑分區(qū)）常是小空閑分區(qū)）。第二章 存 儲 管 理 282.3.1 空閑存儲區(qū)表空閑存儲區(qū)表 管理空閑內(nèi)存區(qū)的數(shù)據(jù)結構可采用鏈接法和連續(xù)線性表管理空閑內(nèi)存區(qū)的數(shù)據(jù)結構可采用鏈接法和連續(xù)線性表格法。下面舉一個連續(xù)線性表格管理空閑內(nèi)存的方法，格法。下面舉一個連續(xù)線性表格管理空閑內(nèi)存的方法，如采用鏈接法，就需要在表項中增加一個指向下一個空如采用鏈接法，就需要在表項中增加一個指向下一個空閑區(qū)的指針。閑區(qū)的指針。每一個空閑分區(qū)用一個每一個空閑分區(qū)用一個map結構管理：結構管理：struct map unsigned m_size;/空閑分區(qū)的長度空閑分區(qū)的長度 char*m_a

24、ddr;/空閑分區(qū)的起始地址空閑分區(qū)的起始地址 ;struct map coremapN;各個空閑分區(qū)按起始地址由低到高順次登記在空閑存儲區(qū)各個空閑分區(qū)按起始地址由低到高順次登記在空閑存儲區(qū)表中，表中，m_size為為0的表項是空白表項，它們集中在表的的表項是空白表項，它們集中在表的后部后部第二章 存 儲 管 理 29l在系統(tǒng)初始階段，在系統(tǒng)初始階段，擁有一塊很大的內(nèi)擁有一塊很大的內(nèi)存空白區(qū)，這時空存空白區(qū)，這時空閑存儲區(qū)表閑存儲區(qū)表coremapcoremap中只需有一項登記中只需有一項登記該空閑區(qū)。該空閑區(qū)。l其余的其余的coremapcoremap表表項為空白項，即項為空白項，即m_si

25、zem_size皆為零。皆為零。第二章 存 儲 管 理 30l以后隨著很多作以后隨著很多作業(yè)的不斷申請內(nèi)存業(yè)的不斷申請內(nèi)存和釋放內(nèi)存，整個和釋放內(nèi)存，整個存儲空間將出現(xiàn)許存儲空間將出現(xiàn)許多大小不等的區(qū)域，多大小不等的區(qū)域，l存儲區(qū)表和實際存儲區(qū)表和實際的內(nèi)存空間就可能的內(nèi)存空間就可能變成如圖所示的情變成如圖所示的情況況。第二章 存 儲 管 理 312.3.2 首次適應算法首次適應算法 1.分配算法分配算法。u采用首次適應法為作業(yè)分配大小為采用首次適應法為作業(yè)分配大小為size的內(nèi)存空間時，的內(nèi)存空間時，總是從表的起始端的低地址部分開始查找?？偸菑谋淼钠鹗级说牡偷刂凡糠珠_始查找。u當?shù)谝淮握业酱?/p>

26、于或等于申請大小的空閑區(qū)時，就按當?shù)谝淮握业酱笥诨虻扔谏暾埓笮〉目臻e區(qū)時，就按所需大小分配給作業(yè)。所需大小分配給作業(yè)。u如果分配后原空閑區(qū)還有剩余空間，就修改原存儲區(qū)如果分配后原空閑區(qū)還有剩余空間，就修改原存儲區(qū)表項的表項的 m_size 和和 m_addr，使它記錄余下的，使它記錄余下的“零頭零頭”。u如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空閑區(qū)表項的閑區(qū)表項的m_size就成為就成為0。u接下來要刪除表中這個接下來要刪除表中這個“空洞空洞”，即將隨后的各非零，即將隨后的各非零表項依次上移一個位置表項依次上移一個位置第二章 存 儲 管 理

27、32char*malloc(mp,size)struct map*mp;unsigned size;register char*a;register struct map*bp;for(bp=mp;bp-m_size;bp+)if(bp-m_size=size)a=bp-m_addr;bp-m_addr+=size;if(bp-m_size-=size)=0)do bp+;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);return(a);return(0);第二章 存 儲 管 理 332.回收算法回收算法 l當某一作業(yè)釋放以前所分配

28、到的內(nèi)存時，就要將該內(nèi)當某一作業(yè)釋放以前所分配到的內(nèi)存時，就要將該內(nèi)存區(qū)歸還給系統(tǒng)，使其成為空閑區(qū)而可被其他作業(yè)使存區(qū)歸還給系統(tǒng)，使其成為空閑區(qū)而可被其他作業(yè)使用。用。l釋放區(qū)與原空閑區(qū)相鄰情況可歸納為如圖所示的釋放區(qū)與原空閑區(qū)相鄰情況可歸納為如圖所示的4種情種情況。況。第二章 存 儲 管 理 34u 僅與前空閑區(qū)相連僅與前空閑區(qū)相連：合并前空閑區(qū)和釋放區(qū)構成一：合并前空閑區(qū)和釋放區(qū)構成一塊大的新空閑區(qū)，并修改空閑區(qū)表項。該空閑區(qū)的塊大的新空閑區(qū)，并修改空閑區(qū)表項。該空閑區(qū)的m_addr不變，仍為原前空閑區(qū)的首地址，修改表項的不變，仍為原前空閑區(qū)的首地址，修改表項的長度域長度域m_size為原

29、為原m_size 與釋放區(qū)長度之和。與釋放區(qū)長度之和。u 與前空閑區(qū)和后空閑區(qū)都相連與前空閑區(qū)和后空閑區(qū)都相連：將三塊空閑區(qū)合并：將三塊空閑區(qū)合并成一塊空閑區(qū)。修改空閑區(qū)表中前空閑區(qū)表項，其起成一塊空閑區(qū)。修改空閑區(qū)表中前空閑區(qū)表項，其起始地址始地址m_addr仍為原前空閑區(qū)起始地址，其大小仍為原前空閑區(qū)起始地址，其大小m_size等于三個空閑區(qū)長度之和，這塊大的空閑區(qū)由等于三個空閑區(qū)長度之和，這塊大的空閑區(qū)由前空閑區(qū)表項登記。接下來還要在空閑區(qū)表中刪除后前空閑區(qū)表項登記。接下來還要在空閑區(qū)表中刪除后項，方法是將后項以下的非空白表項順次上移一個位項，方法是將后項以下的非空白表項順次上移一個位置

30、。置。第二章 存 儲 管 理 35u 僅與后空閑區(qū)相連僅與后空閑區(qū)相連：與后空閑區(qū)合并，使后空閑區(qū)：與后空閑區(qū)合并，使后空閑區(qū)表項的表項的m_addr為釋放區(qū)的起始地址，為釋放區(qū)的起始地址，m_size為釋放區(qū)為釋放區(qū)與后空閑區(qū)的長度之和。與后空閑區(qū)的長度之和。u 與前、后空閑區(qū)皆不相連與前、后空閑區(qū)皆不相連：在前、后空閑區(qū)表項中：在前、后空閑區(qū)表項中間插入一個新的表項，其間插入一個新的表項，其 m_addr為釋放區(qū)的起始地址，為釋放區(qū)的起始地址，m_size為釋放區(qū)的長度。為此，先要將后項及以下表為釋放區(qū)的長度。為此，先要將后項及以下表項都下移一個位置項都下移一個位置第二章 存 儲 管 理

31、36u若采用首次適應法，則其分配算法簡單且合并若采用首次適應法，則其分配算法簡單且合并相鄰空閑區(qū)也很容易。相鄰空閑區(qū)也很容易。u該算法的實質是盡可能利用存儲區(qū)低地址部分該算法的實質是盡可能利用存儲區(qū)低地址部分的空閑區(qū)，而盡量在高地址部分保存較大的空的空閑區(qū)，而盡量在高地址部分保存較大的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，容易得到滿足。容易得到滿足。u其缺點是由于查找總是從表首開始，前面的空其缺點是由于查找總是從表首開始，前面的空閑區(qū)往往被分割得很小，能滿足分配要求的可閑區(qū)往往被分割得很小，能滿足分配要求的可能性較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，

32、能性較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，這個問題就越嚴重。這個問題就越嚴重。第二章 存 儲 管 理 372.3.3 循環(huán)首次適應算法循環(huán)首次適應算法u把空閑表設計成順序結構或鏈接結構的循環(huán)隊列，把空閑表設計成順序結構或鏈接結構的循環(huán)隊列，各空閑區(qū)仍按地址從低到高的次序登記在空閑區(qū)的各空閑區(qū)仍按地址從低到高的次序登記在空閑區(qū)的管理隊列中。管理隊列中。u同時需要設置一個起始查找指針，指向循環(huán)隊列中同時需要設置一個起始查找指針，指向循環(huán)隊列中的一個空閑區(qū)表項。的一個空閑區(qū)表項。u循環(huán)首次適應法分配時總是從起始查找指針所指的循環(huán)首次適應法分配時總是從起始查找指針所指的表項開始查找。表項開始查找。u第

33、一次找到滿足要求的空閑區(qū)時，就分配所需大小第一次找到滿足要求的空閑區(qū)時，就分配所需大小的空閑區(qū)，修改表項，并調整起始查找指針，使其的空閑區(qū)，修改表項，并調整起始查找指針，使其指向隊列中被分配的后面的那塊空閑區(qū)。指向隊列中被分配的后面的那塊空閑區(qū)。u下次分配時就從新指向的那塊空閑區(qū)開始查找。下次分配時就從新指向的那塊空閑區(qū)開始查找。第二章 存 儲 管 理 382.3.3 循環(huán)首次適應算法循環(huán)首次適應算法u循環(huán)首次適應法的實質是起始查找指針所指的空閑循環(huán)首次適應法的實質是起始查找指針所指的空閑區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空閑區(qū)，它們已合并成為大的空閑區(qū)可能性較大。閑區(qū)，它們已合并成為大的空閑區(qū)可能性較大。u比起首次適應法來，在沒有增加多少代價的情況下比起首次適應法來，在沒有增加多少代價的情況下卻明顯地提高了分配查找的速度。釋放算法基本同