【正文】 的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。通過(guò)一后向指針。每個(gè)空閑分區(qū)占一個(gè)表個(gè)空閑分區(qū)的情況。又稱(chēng)為可變分區(qū)分配。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬28n 分區(qū)大小固定，靈活性仍不足，會(huì)產(chǎn)生內(nèi)存碎片；分區(qū)大小固定，靈活性仍不足，會(huì)產(chǎn)生內(nèi)存碎片；在某些用于控制相同對(duì)象的場(chǎng)合仍有一定應(yīng)用。分區(qū)表中記錄各分區(qū)的起始地址、大小和狀態(tài)。n 2. 分區(qū)大小不等分區(qū)大小不等將內(nèi)存區(qū)分為大小不等的多塊，靈活性將內(nèi)存區(qū)分為大小不等的多塊，靈活性稍好，可根據(jù)程序的大小為之分配適當(dāng)?shù)姆稚院?，可根?jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。適用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合。n 將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中可以裝入一道作業(yè)在每個(gè)分區(qū)中可以裝入一道作業(yè) ，當(dāng)內(nèi)存中，當(dāng)內(nèi)存中劃分成幾個(gè)分區(qū)時(shí)，便允許幾道作業(yè)并發(fā)運(yùn)劃分成幾個(gè)分區(qū)時(shí)，便允許幾道作業(yè)并發(fā)運(yùn)行；行； 當(dāng)有一個(gè)空閑分區(qū)時(shí)，便可從外存的后當(dāng)有一個(gè)空閑分區(qū)時(shí)，便可從外存的后備隊(duì)列中，選擇一個(gè)適當(dāng)大小的作業(yè)裝入該備隊(duì)列中，選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)分區(qū) ；當(dāng)該作業(yè)結(jié)束時(shí)，又可從后備隊(duì)列中；當(dāng)該作業(yè)結(jié)束時(shí)，又可從后備隊(duì)列中找出另一個(gè)作業(yè)調(diào)入該分區(qū)。快裝入過(guò)程，而且節(jié)省內(nèi)存空間。接到調(diào)用者模塊上。整拷貝，無(wú)法共享。塊，低效。標(biāo)模塊中的相對(duì)地址。而言的。對(duì)相對(duì)地址進(jìn)行修改。n 不僅允許裝入模塊裝入到內(nèi)存中的任何位置不僅允許裝入模塊裝入到內(nèi)存中的任何位置，而且，而且 允許程序在運(yùn)行時(shí)在內(nèi)存中移動(dòng)允許程序在運(yùn)行時(shí)在內(nèi)存中移動(dòng) 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬15Dynamic Runtime Loadingn 把程序裝入內(nèi)存后，并不立即把裝入模塊中把程序裝入內(nèi)存后，并不立即把裝入模塊中的邏輯地址轉(zhuǎn)換為物理地址，仍是相對(duì)地址的邏輯地址轉(zhuǎn)換為物理地址，仍是相對(duì)地址。Load 1,2500 的作用是把 2500單元中的數(shù)據(jù)送至寄存器 1。n 裝入時(shí)，需根據(jù)內(nèi)存當(dāng)前的情況，將模塊裝裝入時(shí)，需根據(jù)內(nèi)存當(dāng)前的情況，將模塊裝入到內(nèi)存的適當(dāng)位置，入到內(nèi)存的適當(dāng)位置， 存在一個(gè)邏輯地址空存在一個(gè)邏輯地址空間到內(nèi)存物理地址空間的轉(zhuǎn)換過(guò)程間到內(nèi)存物理地址空間的轉(zhuǎn)換過(guò)程 （即（即 重定重定位位 ）。通常在程序中采用符號(hào)地址，在編譯或匯編時(shí)，再將其轉(zhuǎn)換為絕對(duì)地址，在編譯或匯編時(shí)，再將其轉(zhuǎn)換為絕對(duì)地址。n 裝入模塊不需再地址轉(zhuǎn)換，直接裝入內(nèi)存。由裝入程序把裝入模塊裝入內(nèi)存。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬10 程序的裝入和鏈接程序的裝入和鏈接n 為作業(yè)創(chuàng)建進(jìn)程需將其裝入內(nèi)存。后兩者需要通過(guò) I/O訪問(wèn)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬n – 容量大小容量大小n – 速度與速度與 CPU完全協(xié)調(diào)完全協(xié)調(diào)– 長(zhǎng)度以字為單位長(zhǎng)度以字為單位 ，幾十至幾百個(gè)，幾十至幾百個(gè)7齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬n 高速緩存高速緩存– 局部性原理局部性原理– CPU與內(nèi)存之間與內(nèi)存之間n 磁盤(pán)緩存磁盤(pán)緩存– 頻繁使用的磁盤(pán)數(shù)據(jù)暫存在內(nèi)存中的頻繁使用的磁盤(pán)數(shù)據(jù)暫存在內(nèi)存中的 磁盤(pán)高速磁盤(pán)高速緩存中緩存中8齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬9預(yù)備知識(shí)預(yù)備知識(shí)n 地址空間的概念地址空間的概念n 1．內(nèi)存空間．內(nèi)存空間 (物理空間物理空間 ) 內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元的編號(hào)稱(chēng)為內(nèi)存地址元的編號(hào)稱(chēng)為內(nèi)存地址 (或物理地址或物理地址 )n 2．邏輯空間．邏輯空間 經(jīng)過(guò)匯編或編譯后形成目標(biāo)程序是以經(jīng)過(guò)匯編或編譯后形成目標(biāo)程序是以 0為基址順為基址順序進(jìn)行編址的，目標(biāo)程序占據(jù)的地址空間稱(chēng)為作業(yè)序進(jìn)行編址的，目標(biāo)程序占據(jù)的地址空間稱(chēng)為作業(yè)的邏輯地址空間。1第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬2第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 如何對(duì)存儲(chǔ)器進(jìn)行有效的管理，不僅影響到如何對(duì)存儲(chǔ)器進(jìn)行有效的管理，不僅影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。邏輯空間中的地址稱(chēng)為邏輯地址的邏輯地址空間。為作業(yè)創(chuàng)建進(jìn)程需將其裝入內(nèi)存。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬11 程序的裝入程序的裝入n 將一個(gè)裝入模塊裝入內(nèi)存時(shí)，有三種方式：將一個(gè)裝入模塊裝入內(nèi)存時(shí)，有三種方式：l絕對(duì)裝入方式絕對(duì)裝入方式l可重定位裝入方式可重定位裝入方式l動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式關(guān)鍵在于將邏輯地址轉(zhuǎn)換為物理地址的時(shí)機(jī)不同齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬12Absolute Loading Moden 若編譯時(shí)知道程序?qū)⒃趦?nèi)存的若編譯時(shí)知道程序?qū)⒃趦?nèi)存的 (起始起始 )駐留地駐留地址，址， 編譯程序?qū)a(chǎn)生絕對(duì)編譯程序?qū)a(chǎn)生絕對(duì) (物理物理 )地址的目標(biāo)地址的目標(biāo)代碼代碼 。裝入模塊不需再地址轉(zhuǎn)換，直接裝入內(nèi)存。地址。）。在裝入時(shí)，指令的地址會(huì)由原來(lái)的 1000，變?yōu)?11000，取數(shù)地址 2500也會(huì)變?yōu)?12500。邏輯地址到物理地址的。（。– (2)變換外部符號(hào)。n 鏈接成一個(gè)裝入模塊后，鏈接成一個(gè)裝入模塊后， BC的首地址分別變成了的首地址分別變成了 L和和 L+M，這就需要修改，這就需要修改 BC中的中的 相對(duì)地址相對(duì)地址 ，將其全，將其全部加上部加上 L或或 L+M；對(duì)于；對(duì)于 ABC各模塊中所使用的各模塊中所使用的 外部外部調(diào)用符號(hào)調(diào)用符號(hào) ，也都需進(jìn)行變換，也都需進(jìn)行變換， CALL B需變換為需變換為JSL L。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬20Loadtime Dynamic Linkingn 優(yōu)點(diǎn)優(yōu)點(diǎn) : VS 靜態(tài)鏈接靜態(tài)鏈接 各目標(biāo)模塊分開(kāi)存放，便于修改或更新各目標(biāo)模塊分開(kāi)存放，便于修改或更新 。 可將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊，實(shí)可將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬21Runtime Dynamic Linkingn 把對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)進(jìn)行。n 優(yōu)點(diǎn)：本次執(zhí)行優(yōu)點(diǎn)：本次執(zhí)行 不需要的模塊不鏈接不需要的模塊不鏈接 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬22 程序的裝入和鏈接程序的裝入和鏈接 小結(jié)小結(jié)n 程序的裝入程序的裝入– 絕對(duì)裝入方式絕對(duì)裝入方式– 可重定位裝入方式可重定位裝入方式– 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式n 程序的鏈接程序的鏈接– 靜態(tài)鏈接方式靜態(tài)鏈接方式– 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接– 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬23 連續(xù)分配方式連續(xù)分配方式連續(xù)分配方式，指為一個(gè)用戶程序分配一連續(xù)分配方式，指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。找出另一個(gè)作業(yè)調(diào)入該分區(qū)。用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合。區(qū)。狀態(tài)。在某些用于控制相同對(duì)象的場(chǎng)合仍有一定應(yīng)用。n 示意圖示意圖齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬30可變分區(qū)內(nèi)存使用示意圖可變分區(qū)內(nèi)存使用示意圖齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬31 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配n 三個(gè)問(wèn)題三個(gè)問(wèn)題– 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)– 分區(qū)分配算法分區(qū)分配算法– 分區(qū)分配操作分區(qū)分配操作齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬32n 記錄內(nèi)存的使用情況，為分配提供依據(jù)。每個(gè)空閑分區(qū)占一個(gè)表目目 ，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。通過(guò)前、后向鏈接指針前、后向鏈接指針，可將所有的空閑，可將所有的空閑分區(qū)鏈接成一個(gè)雙分區(qū)鏈接成一個(gè)雙向鏈。n 常用的三種分配算法：常用的三種分配算法：l首次適應(yīng)算法首次適應(yīng)算法l循環(huán)適應(yīng)算法循環(huán)適應(yīng)算法l最佳適應(yīng)算法最佳適應(yīng)算法齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬35(1)首次適應(yīng)算法首次適應(yīng)算法n 空閑分區(qū)空閑分區(qū) 以地址遞增以地址遞增 的次序鏈接。內(nèi)存空間創(chuàng)造了條件。作業(yè) 5大小為 36k齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬37(2)循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法n 分配時(shí)，分配時(shí)， 不每次均從鏈?zhǔn)组_(kāi)始查找，而是從上次找不每次均從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找 ，直至找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊與請(qǐng)求的大小相等的內(nèi)存空間分配給作業(yè)。 即如果最后一個(gè)即如果最后一個(gè)(鏈尾鏈尾 )空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回到第一個(gè)空閑分區(qū)，比較其大小是否滿足要求。n 優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分區(qū)的開(kāi)銷(xiāo)，但會(huì)導(dǎo)致缺乏大的空閑分區(qū)。這樣，第一次找。每次分配后所切割下來(lái)的剩余部分總是最小的。最后，空閑分區(qū)表中。區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬43 動(dòng)態(tài)動(dòng)態(tài) 重定位重定位 分區(qū)分配分區(qū)分配n n n 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬44n 為了充分利用內(nèi)存碎片為了充分利用內(nèi)存碎片，可利用，可利用 “緊湊緊湊 ”操作操作 把把多個(gè)碎片處理為一個(gè)比多個(gè)碎片處理為一個(gè)比較大的分區(qū)，以便利用較大的分區(qū)，以便利用。n 為避免影響速度，為避免影響速度， 必須有硬件地址變換機(jī)構(gòu)的支持必須有硬件地址變換機(jī)構(gòu)的支持（重定位寄存器）（重定位寄存器） ，用它來(lái)存放程序在內(nèi)存中的起，用它來(lái)存放程序在內(nèi)存中的起始地址。n 當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了 “緊湊緊湊 ”，而使若干程序從內(nèi)存，而使若干程序從內(nèi)存的某處移至另一處時(shí)，不需對(duì)程序做任何修改，只的某處移至另一處時(shí)，不需對(duì)程序做任何修改，只要用該程序的新起始地址，去置換原來(lái)的起始地址要用該程序的新起始地址，去置換原來(lái)的起始地址即可。消除內(nèi)存碎片，提高內(nèi)存利用問(wèn)題。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬49動(dòng)態(tài)重定位動(dòng)態(tài)重定位 VS 靜態(tài)重定位靜態(tài)重定位n 靜態(tài)重定位靜態(tài)重定位 :當(dāng)用戶程序被裝入內(nèi)存時(shí)，一當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持地址變換，硬件上需要重定位寄存器的支持。目的是為了解決內(nèi)存緊張問(wèn)題如果對(duì)換如果對(duì)換 以以 “頁(yè)頁(yè) ”或或 “段段 ”為單位為單位 ，則稱(chēng)之為，則稱(chēng)之為 “頁(yè)面對(duì)頁(yè)面對(duì)換換 ”或或 “分段對(duì)換分段對(duì)換 ”。為了進(jìn)程對(duì)換，需三方面功能：對(duì)換空間的管理、進(jìn)程的換出及換入。(對(duì)換是在對(duì)換是在 內(nèi)存與內(nèi)存與 外存的對(duì)換區(qū)之間進(jìn)行外存的對(duì)換區(qū)之間進(jìn)行））齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬52n 為了對(duì)對(duì)換區(qū)中的空閑盤(pán)塊進(jìn)行管理，在系為了對(duì)對(duì)換區(qū)中的空閑盤(pán)塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的統(tǒng)中應(yīng)配置相應(yīng)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) ，以記錄外存的，以記錄外存的使用情況。n 對(duì)換空間的對(duì)換空間的 分配與回收分配與回收 ，與動(dòng)態(tài)分區(qū)分配方，與動(dòng)態(tài)分區(qū)分配方式中的內(nèi)存分配與回收方法雷同。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬53n 進(jìn)程換出：選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低進(jìn)程換出：選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，將其程序和數(shù)據(jù)傳送的進(jìn)程作為換出進(jìn)程，將其程序和數(shù)據(jù)傳送到外存的對(duì)換區(qū)上，然后便可回收其所占用到外存的對(duì)換區(qū)上，然后便可回收其所占用的內(nèi)存空間，并對(duì)其的內(nèi)存空間，并對(duì)其 PCB作相應(yīng)修改。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬54 連續(xù)分配方式連續(xù)分配方式 小結(jié)小結(jié)n 單一連續(xù)分配方式單一連續(xù)分配方式n 固定分區(qū)分配固定分區(qū)分配 分區(qū)使用表分區(qū)使用表n 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 – 首次適應(yīng)算法首次適應(yīng)算法 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法 最佳適應(yīng)算法最佳適應(yīng)算法n 動(dòng)態(tài)重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配– “緊湊緊湊 ” 動(dòng)態(tài)重定位的實(shí)現(xiàn)（重定位寄存器）動(dòng)態(tài)重定位的實(shí)現(xiàn)（重定位寄存器）n 對(duì)換對(duì)換齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬55 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式n 引入：引入：連續(xù)分配方式會(huì)形成許多連續(xù)分配方式會(huì)形成許多 “碎片碎片 ”，雖然可通，雖然可通過(guò)過(guò) “緊湊緊湊 ”方法將碎片拼接成可用的大塊空間方法將碎片拼接成可用的大塊空間，但須為此付出較大開(kāi)銷(xiāo)。所述連續(xù)分配方式。 “頁(yè)內(nèi)碎片頁(yè)內(nèi)碎片 ”齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬58n 2)頁(yè)面大小頁(yè)面大小n 頁(yè)面大小應(yīng)適中，且頁(yè)面大小應(yīng)為頁(yè)面大小應(yīng)適中，且頁(yè)面大小應(yīng)為 2的冪，的冪，一般為一般為 512B~8KB。頁(yè)面對(duì)應(yīng)的物理塊。表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。物理塊號(hào)。變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。進(jìn)程未執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)存于進(jìn)。l 2)在檢索頁(yè)表前，在檢索頁(yè)表前， 將頁(yè)號(hào)與頁(yè)表長(zhǎng)度比較將頁(yè)號(hào)與頁(yè)表長(zhǎng)度比較 ，如果越，如果越界則產(chǎn)生一越界中斷，本次訪問(wèn)失敗界則產(chǎn)生一越界中斷，本次訪問(wèn)失敗l 3)如果未越界，則如果未越界，則 頁(yè)表始址頁(yè)表始址 +頁(yè)號(hào)頁(yè)號(hào) *頁(yè)表項(xiàng)長(zhǎng)度頁(yè)表項(xiàng)長(zhǎng)度 ? 得到該頁(yè)號(hào)在頁(yè)表中的位置，從中可得到該頁(yè)號(hào)在頁(yè)表中的