【正文】 一些頁(yè)表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入其它的。d0 d1齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬82如何減少頁(yè)表所占的內(nèi)存空間如何減少頁(yè)表所占的內(nèi)存空間n 上述離散分配空間的辦法只解決了大頁(yè)表無(wú)需大片上述離散分配空間的辦法只解決了大頁(yè)表無(wú)需大片連續(xù)存儲(chǔ)空間的問(wèn)題，并未減少頁(yè)表所占的內(nèi)存空連續(xù)存儲(chǔ)空間的問(wèn)題，并未減少頁(yè)表所占的內(nèi)存空間。n 邏輯地址結(jié)構(gòu)如下：邏輯地址結(jié)構(gòu)如下：齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬79n 頁(yè)內(nèi)地址頁(yè)內(nèi)地址 :12位，頁(yè)面大小為位，頁(yè)面大小為 212， 4KBn 外層頁(yè)內(nèi)地址外層頁(yè)內(nèi)地址 :10位，每個(gè)頁(yè)表分頁(yè)中最多位，每個(gè)頁(yè)表分頁(yè)中最多可包含可包含 210個(gè)頁(yè)表項(xiàng)（對(duì)應(yīng)個(gè)頁(yè)表項(xiàng)（對(duì)應(yīng) 210個(gè)物理塊）個(gè)物理塊）n 外層頁(yè)號(hào)外層頁(yè)號(hào) :10位，最多允許位，最多允許 210個(gè)頁(yè)表分頁(yè)個(gè)頁(yè)表分頁(yè)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬80兩級(jí)頁(yè)表示意圖兩級(jí)頁(yè)表示意圖外層頁(yè)表的每個(gè)表項(xiàng)存放的是某頁(yè)表分頁(yè)的在內(nèi)存中的物理塊號(hào)頁(yè)表 (分頁(yè) )的每個(gè)表項(xiàng)存放的是某頁(yè)在內(nèi)存中的物理塊號(hào)可利用兩級(jí)頁(yè)表，實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換這里只是物理塊號(hào)，并不是內(nèi)存單元的編號(hào)比如外層頁(yè)號(hào)為 1,外層頁(yè)內(nèi)地址也為 1,尋址齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬81具有兩級(jí)頁(yè)表的地址變換具有兩級(jí)頁(yè)表的地址變換n 外層頁(yè)表寄存器，用于存放外層頁(yè)表的始址外層頁(yè)表寄存器，用于存放外層頁(yè)表的始址 d0n p1，作為外層頁(yè)表的索引，找到，作為外層頁(yè)表的索引，找到d0和和 p1對(duì)應(yīng)的表項(xiàng)，從中可知指定頁(yè)表分頁(yè)的始址對(duì)應(yīng)的表項(xiàng)，從中可知指定頁(yè)表分頁(yè)的始址 d1(物理物理塊號(hào)塊號(hào) )；；n p2，作為指定頁(yè)內(nèi)分頁(yè)的索引，找到，作為指定頁(yè)內(nèi)分頁(yè)的索引，找到 d1和和p2對(duì)應(yīng)的表項(xiàng)，從中可知該頁(yè)在內(nèi)存的物理塊號(hào)對(duì)應(yīng)的表項(xiàng)，從中可知該頁(yè)在內(nèi)存的物理塊號(hào) bn b與頁(yè)內(nèi)地址與頁(yè)內(nèi)地址 d，即構(gòu)成了要訪問(wèn)的內(nèi)存的物理地，即構(gòu)成了要訪問(wèn)的內(nèi)存的物理地址。這顯然不現(xiàn)實(shí)。假定某時(shí)刻一用戶頁(yè)表中。存取頁(yè)面數(shù)據(jù)。第二次才根據(jù)該地址面的物理地址（稱為定位）。以上。從快表中能找到所需頁(yè)表項(xiàng)的機(jī)率，其中。但對(duì)于中小型作業(yè)來(lái)說(shuō)個(gè)頁(yè)表項(xiàng)。認(rèn)為不再需要的頁(yè)表項(xiàng)換出。但如果快表已滿，則將一個(gè)老的且已被入快表中。找到后，若沒(méi)有匹配的，還需訪問(wèn)內(nèi)存中的頁(yè)表。應(yīng)的物理塊號(hào)，并送物理地址寄存器中。（意味著這些頁(yè)表項(xiàng)不在存放在。n 將使計(jì)算機(jī)的處理速度降低近將使計(jì)算機(jī)的處理速度降低近 1/2。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬66分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬67分頁(yè)系統(tǒng)的地址變換分頁(yè)系統(tǒng)的地址變換 實(shí)例實(shí)例邏輯地址為 3BADH 頁(yè)面大小為 2KB頁(yè)表寄存器齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬68n 一個(gè)問(wèn)題？一個(gè)問(wèn)題？n 頁(yè)表是存放在內(nèi)存中的，這使頁(yè)表是存放在內(nèi)存中的，這使 CPU每次要存取一個(gè)每次要存取一個(gè)數(shù)據(jù)時(shí)，都要兩次訪問(wèn)內(nèi)存數(shù)據(jù)時(shí)，都要兩次訪問(wèn)內(nèi)存 。l 4)最后再將有效地址中的最后再將有效地址中的 頁(yè)內(nèi)地址送入頁(yè)內(nèi)地址送入 物理地址寄物理地址寄存器的塊內(nèi)地址中。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è)表中的位置，從中可 得到該頁(yè)的物得到該頁(yè)的物理塊號(hào)理塊號(hào) ，將之裝入物理地址的物理塊號(hào)部分。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬65n 地址變換過(guò)程：地址變換過(guò)程：l 1)分頁(yè)地址變換機(jī)構(gòu)自動(dòng)將有效地址分頁(yè)地址變換機(jī)構(gòu)自動(dòng)將有效地址 分為頁(yè)號(hào)和頁(yè)分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分內(nèi)地址兩部分 ，再以頁(yè)號(hào)為索引去檢索頁(yè)表。進(jìn)程未執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)存于進(jìn)。n 兩種實(shí)現(xiàn)方法兩種實(shí)現(xiàn)方法l基本的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)l具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬64n 由于頁(yè)表項(xiàng)的總數(shù)很多，不可能均用寄存器由于頁(yè)表項(xiàng)的總數(shù)很多，不可能均用寄存器來(lái)實(shí)現(xiàn)，頁(yè)表來(lái)實(shí)現(xiàn)，頁(yè)表 大多駐留在內(nèi)存中大多駐留在內(nèi)存中 。變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。到物理地址的轉(zhuǎn)換。物理塊號(hào)。查找頁(yè)表，即可找到每頁(yè)在內(nèi)存中的。表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。頁(yè)表。頁(yè)面對(duì)應(yīng)的物理塊。后一部分為后一部分為位移量位移量 W，即頁(yè)內(nèi)地址，即頁(yè)內(nèi)地址 (212)。 “頁(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。（全部裝入內(nèi)存后方能運(yùn)行。所述連續(xù)分配方式。?如果允許將一個(gè)進(jìn)程直接分散地分配到許多如果允許將一個(gè)進(jìn)程直接分散地分配到許多不相鄰接的分區(qū)中，就不必再進(jìn)行不相鄰接的分區(qū)中，就不必再進(jìn)行 “緊湊緊湊 ”。齊魯工業(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ò) “緊湊緊湊 ”方法將碎片拼接成可用的大塊空間方法將碎片拼接成可用的大塊空間，但須為此付出較大開銷。n 進(jìn)程換入：查找處于進(jìn)程換入：查找處于 “就緒就緒 ”狀態(tài)但已換出的狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入。齊魯工業(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īng)算法、循環(huán)首次適應(yīng)算法法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法。n 對(duì)換空間的對(duì)換空間的 分配與回收分配與回收 ，與動(dòng)態(tài)分區(qū)分配方，與動(dòng)態(tài)分區(qū)分配方式中的內(nèi)存分配與回收方法雷同。與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用的數(shù)據(jù)結(jié)構(gòu)相似，同樣可以用空閑分區(qū)表用的數(shù)據(jù)結(jié)構(gòu)相似，同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。(對(duì)換是在對(duì)換是在 內(nèi)存與內(nèi)存與 外存的對(duì)換區(qū)之間進(jìn)行外存的對(duì)換區(qū)之間進(jìn)行））齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬52n 為了對(duì)對(duì)換區(qū)中的空閑盤塊進(jìn)行管理，在系為了對(duì)對(duì)換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的統(tǒng)中應(yīng)配置相應(yīng)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) ，以記錄外存的，以記錄外存的使用情況。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬51n 把把 外存分為外存分為 文件區(qū)和對(duì)換區(qū)文件區(qū)和對(duì)換區(qū)l 文件區(qū)文件區(qū) ：用于：用于 存放文件存放文件 ；為了提高空間的利；為了提高空間的利用率，對(duì)其采用用率，對(duì)其采用 離散分配方式離散分配方式 。為了進(jìn)程對(duì)換，需三方面功能：對(duì)換空間的管理、進(jìn)程的換出及換入。目的是為了支持虛擬存儲(chǔ)系統(tǒng)n 此小節(jié)僅介紹進(jìn)程對(duì)換。目的是為了解決內(nèi)存緊張問(wèn)題如果對(duì)換如果對(duì)換 以以 “頁(yè)頁(yè) ”或或 “段段 ”為單位為單位 ，則稱之為，則稱之為 “頁(yè)面對(duì)頁(yè)面對(duì)換換 ”或或 “分段對(duì)換分段對(duì)換 ”。n 如果對(duì)換如果對(duì)換 以整個(gè)進(jìn)程為單位以整個(gè)進(jìn)程為單位 ，稱之為，稱之為 “整體對(duì)換整體對(duì)換 ”或或“進(jìn)程對(duì)換進(jìn)程對(duì)換 ”。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持地址變換，硬件上需要重定位寄存器的支持。n 動(dòng)態(tài)重定位動(dòng)態(tài)重定位 :在程序運(yùn)行過(guò)程中要訪問(wèn)數(shù)據(jù)在程序運(yùn)行過(guò)程中要訪問(wèn)數(shù)據(jù)時(shí)再進(jì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)換。率。消除內(nèi)存碎片，提高內(nèi)存利用問(wèn)題。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬46齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬47與動(dòng)態(tài)分區(qū)分配算法基本相同，差別僅在于：增加了緊湊功能 ，在找不到足夠大的空閑分區(qū)來(lái)滿足用戶需求時(shí)進(jìn)行緊湊。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)的起始地址即可。程序在執(zhí)行時(shí)， 真正訪問(wèn)的內(nèi)存地址是相真正訪問(wèn)的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的對(duì)地址與重定位寄存器中的地址相加而形成的 。n 為避免影響速度，為避免影響速度， 必須有硬件地址變換機(jī)構(gòu)的支持必須有硬件地址變換機(jī)構(gòu)的支持（重定位寄存器）（重定位寄存器） ，用它來(lái)存放程序在內(nèi)存中的起，用它來(lái)存放程序在內(nèi)存中的起始地址。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬45n 采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式，地址轉(zhuǎn)換推遲到程序指采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式，地址轉(zhuǎn)換推遲到程序指令真正要執(zhí)行時(shí)進(jìn)行。齊魯工業(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ū)，以便利用。有不同的合并策略。區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。調(diào)用者。最后，空閑分區(qū)表中。在存儲(chǔ)器中會(huì)留下許多這樣難以利用的小空閑區(qū)。每次分配后所切割下來(lái)的剩余部分總是最小的。到的滿足要求的空閑區(qū)，必然是最優(yōu)的。這樣，第一次找。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬38(3)最佳適應(yīng)算法最佳適應(yīng)算法n 每次為作業(yè)分配內(nèi)存時(shí)，每次為作業(yè)分配內(nèi)存時(shí)， 總是把既能滿足要求，又總是把既能滿足要求，又是最小的空閑分區(qū)分配給作業(yè)是最小的空閑分區(qū)分配給作業(yè) ，避免了，避免了 “大材小用大材小用 ”。n 優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分區(qū)的開銷，但會(huì)導(dǎo)致缺乏大的空閑分區(qū)。找到后，應(yīng)立即調(diào)整起始查尋指針。 即如果最后一個(gè)即如果最后一個(gè)(鏈尾鏈尾 )空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回到第一個(gè)空閑分區(qū)，比較其大小是否滿足要求。n 需需 設(shè)置一起始查尋指針，以指示下一次起始查尋的設(shè)置一起始查尋指針，以指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式。作業(yè) 5大小為 36k齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬37(2)循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法n 分配時(shí)，分配時(shí)， 不每次均從鏈?zhǔn)组_始查找，而是從上次找不每次均從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找 ，直至找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊與請(qǐng)求的大小相等的內(nèi)存空間分配給作業(yè)。從低址開始查找，會(huì)增加查找可用空間的開銷。內(nèi)存空間創(chuàng)造了條件。 分配時(shí)，從鏈?zhǔn)追峙鋾r(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空開始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)閑分區(qū) ；； 然后根據(jù)作業(yè)的大小，從該分區(qū)中劃出一然后根據(jù)作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中空閑鏈中 。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ū) 以地址遞增以地址遞增 的次序鏈接。 前后向指針，大小，狀態(tài)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬34n 按照一定的分配算法，從空閑分區(qū)表或空閑按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。通過(guò)前、后向鏈接指針前、后向鏈接指針，可將所有的空閑，可將所有的空閑分區(qū)鏈接成一個(gè)雙分區(qū)鏈接成一個(gè)雙向鏈。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬33n (2)空閑分區(qū)鏈空閑分區(qū)鏈每個(gè)分區(qū)的每個(gè)分區(qū)的 起始起始 部部分，設(shè)置用于鏈接分，設(shè)置用于鏈接各分區(qū)的前向指針各分區(qū)的前向指針；在分區(qū)；在分區(qū) 尾部尾部 設(shè)置設(shè)置一后向指針。每個(gè)空閑分區(qū)占一個(gè)表目目 ，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。n (1)空閑分區(qū)表空閑分