【文章內(nèi)容簡介】 ， 不同大小的空閑分區(qū)形成了 k(0≤k≤m)個(gè)空閑分區(qū)鏈表 。 當(dāng)需要為進(jìn)程分配一個(gè)長度為 n的存儲空間時(shí)，首先計(jì)算一個(gè) i值，使 2i－ 1n≤2i，然后在空閑分區(qū)大小為 2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長度為 2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為 2i＋ 1的空閑分區(qū)鏈表中尋找。若存在 2i＋ 1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為 2i的空閑分區(qū)鏈表中。若大小為 2i＋ 1的空閑分區(qū)也不存在，則需要查找大小為 2i＋ 2的空閑分區(qū)，若找到則對其進(jìn)行兩次分割：第一次，將其分割為大小為 2i＋ 1的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為 2i＋ 1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為2i的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為 2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為 2i＋ 3的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可能需要對 2k的空閑分區(qū)進(jìn)行 k次分割才能得到所需分區(qū)。 ? 哈希算法 以 空閑分區(qū)大小 為關(guān)鍵字建立適當(dāng)?shù)墓：瘮?shù)，形成哈希表。該表的每一個(gè)表項(xiàng)記錄了一個(gè) 空閑分區(qū)鏈表表頭指針 。 當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計(jì)算，得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。 6. 可重定位分區(qū)分配 1）動態(tài)重定位的引入 碎片 緊湊 程序地址變化 操作系統(tǒng) P1 10K P3 15K P7 30K P8 操作系統(tǒng) P1 10K P3 15K P7 30K P8 緊湊技術(shù) paction 2 動態(tài)重定位示意圖 L O A D 1 , 2 5 0 03650100250050002500相對地址10000重定位寄存器＋L O A D 1 , 2 5 0 036510000101001250015000作業(yè) J處理機(jī)一側(cè) 存儲器一側(cè)主存3 ）動態(tài)重定位分區(qū)分配算法 動態(tài)分區(qū)分配算法流程圖 請求分配u . s i z e 分區(qū)檢索空閑分區(qū)鏈( 表)找到大于 u . s i z e的可用區(qū)否?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和≥ u . s i z e ?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否交換（ Swapping） ?交換 (Swapping)的引入 – 為了提高內(nèi)存的利用率，出現(xiàn)了交換技術(shù)。 – 進(jìn)程在運(yùn)行過程中經(jīng)常因?yàn)檫M(jìn)行 I/O操作和等待其他事件而阻塞，無法執(zhí)行。系統(tǒng)在內(nèi)存緊張時(shí)把這些進(jìn)程暫時(shí)換出內(nèi)存放入外存，騰出內(nèi)存分配給有條件運(yùn)行的進(jìn)程。 – 所謂“對換”， 是指把內(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)存。對換是提高內(nèi)存利用率的有效措施。 – 以進(jìn)程為單位進(jìn)行交換 ?對換空間的管理 – 在外存上，系統(tǒng)管理著專門的空間用于存放從內(nèi)存換出的進(jìn)程，這空間稱為 對 換區(qū)。 – 為了能對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。 ?進(jìn)程的換出與換入 – 進(jìn)程的換出：每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。 其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作為換出進(jìn)程，然后啟動盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改 ? 選擇阻塞、優(yōu)先級低 》 將次進(jìn)程保持到交換區(qū) 》回收內(nèi)存 – 進(jìn)程的換入 交換區(qū)中選擇“就緒”、時(shí)間最久 》 換入到內(nèi)存。 四、基本分頁存儲管理 ? 基本原理 – 把用戶的程序空間 (邏輯地址空間）劃分成大小相等的塊，稱為 頁（面）、邏輯頁 ，從 0開始給頁編號。 – 頁的大小應(yīng)是 2的 n次冪，通常是 512B～ 8KB – 物理內(nèi)存按照頁的大小也劃分成大小相等的區(qū)域，稱為 頁框、物理頁、物理塊 ，從 0開始編號 – 內(nèi)存分配：將進(jìn)程空間中的邏輯頁面映射到物理空間中空閑的頁面 . . . 0 1 2 3 4 5 6 程序邏輯空間 內(nèi)存物理空間 0 1 2 3 4 5 6 7 要求要把程序的 所有頁 都裝入到內(nèi)存后，程序才能運(yùn)行。 用戶程序分頁邏輯地址的結(jié)構(gòu)： 32位 0~11位頁內(nèi)地址（每頁大小為 4KB=212KB）；12~31頁號（地址空間最多允許有 1M=220頁） 頁號 頁內(nèi)地址 0 11 12 31 對于某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為 A，頁面的大小為 L，則頁號 P和頁內(nèi)地址 d可按下式求得： [ A] MODLdLAI NTP????????其中， INT是整除函數(shù)， MOD是取余函數(shù)。例如，其系統(tǒng)的頁面大小為 1 KB，設(shè) A = 2170 B 則由上式可以求得 P = 2， d = 122。 數(shù)據(jù)結(jié)構(gòu) （ 1）內(nèi)存頁表： 要完成內(nèi)存物理頁的分配，則必須知道哪些物理頁空閑，哪些被占用。要用一個(gè)數(shù)據(jù)結(jié)構(gòu)來隨時(shí)記錄內(nèi)存的情況，這個(gè)數(shù)據(jù)結(jié)構(gòu)稱為 內(nèi)存頁表 。 0 1 2 3 4 n … 0，空閑 1，被占用 問題：內(nèi)存頁表有多少項(xiàng)？與哪些因素有關(guān)？ 回答： 內(nèi)存頁表的行數(shù) ＝內(nèi)存的大小 / 頁的大小 （ 2）進(jìn)程頁表 內(nèi)存頁表中的空閑物理頁是隨著不斷的分配與回收而隨機(jī)分布的。因此一個(gè)程序的所有頁裝入到哪些內(nèi)存物理頁也是隨機(jī)的。這就需要為 每一個(gè)進(jìn)程 建立一張表，來記錄該進(jìn)程的每一頁都裝入到哪個(gè)物理頁去了，這張表稱為 進(jìn)程頁表。 – 進(jìn)程頁表 0 1 2 3 4 5 6 用戶程序空間 內(nèi)存物理空間 0 1 2 3 4 5 6 7 4 2 13 11 2