【文章內(nèi)容簡(jiǎn)介】 與動(dòng)態(tài)分區(qū)分配方式中的內(nèi)存分配與回收方法雷同。其分配算式中的內(nèi)存分配與回收方法雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法?；蜃罴堰m應(yīng)算法。齊魯工業(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)修改。n 進(jìn)程換入：查找處于進(jìn)程換入：查找處于 “就緒就緒 ”狀態(tài)但已換出的狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入。進(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ò) “緊湊緊湊 ”方法將碎片拼接成可用的大塊空間方法將碎片拼接成可用的大塊空間，但須為此付出較大開銷。，但須為此付出較大開銷。?如果允許將一個(gè)進(jìn)程直接分散地分配到許多如果允許將一個(gè)進(jìn)程直接分散地分配到許多不相鄰接的分區(qū)中，就不必再進(jìn)行不相鄰接的分區(qū)中，就不必再進(jìn)行 “緊湊緊湊 ”?；谶@一思想而產(chǎn)生了基于這一思想而產(chǎn)生了 離散分配離散分配 方式，相異方式，相異于于 。所述連續(xù)分配方式。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬56 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式n 分段存儲(chǔ)管理方式分段存儲(chǔ)管理方式 基本單位是段基本單位是段n 分頁(yè)存儲(chǔ)管理方式分頁(yè)存儲(chǔ)管理方式 基本單位是頁(yè)基本單位是頁(yè)n 基本的分頁(yè)存儲(chǔ)管理方式基本的分頁(yè)存儲(chǔ)管理方式 ，要求把每個(gè)作業(yè)，要求把每個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。（全部裝入內(nèi)存后方能運(yùn)行。（ 不具備頁(yè)面對(duì)不具備頁(yè)面對(duì)換功能換功能 ））n 頁(yè)面和頁(yè)表頁(yè)面和頁(yè)表n 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)n 兩級(jí)和多級(jí)頁(yè)表兩級(jí)和多級(jí)頁(yè)表齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬57 頁(yè)面與頁(yè)表頁(yè)面與頁(yè)表n n 1)頁(yè)面和物理塊頁(yè)面和物理塊n 頁(yè)面：將一個(gè)進(jìn)程的頁(yè)面：將一個(gè)進(jìn)程的 邏輯地址空間邏輯地址空間 分成若干個(gè)大小分成若干個(gè)大小相等的片相等的片n 物理塊：內(nèi)存物理塊：內(nèi)存 物理空間物理空間 分成與頁(yè)相同大小的若干個(gè)分成與頁(yè)相同大小的若干個(gè)存儲(chǔ)塊存儲(chǔ)塊n 分配內(nèi)存時(shí)，可將進(jìn)程中的若干頁(yè)分配內(nèi)存時(shí)，可將進(jìn)程中的若干頁(yè) (邏輯地址空間邏輯地址空間 )分別裝入多個(gè)可以不相鄰接的塊分別裝入多個(gè)可以不相鄰接的塊 (物理地址空間物理地址空間 )中中。 “頁(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。l 頁(yè)面太小，減少了內(nèi)存碎片，有利于提高內(nèi)頁(yè)面太小，減少了內(nèi)存碎片，有利于提高內(nèi)存利用率；但也會(huì)導(dǎo)致頁(yè)面過(guò)多，頁(yè)表過(guò)長(zhǎng)存利用率；但也會(huì)導(dǎo)致頁(yè)面過(guò)多，頁(yè)表過(guò)長(zhǎng)l 頁(yè)面太大，則會(huì)導(dǎo)致內(nèi)存碎片較多頁(yè)面太大，則會(huì)導(dǎo)致內(nèi)存碎片較多齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬59n 兩部分，兩部分， 前一部分為頁(yè)號(hào)前一部分為頁(yè)號(hào) P (220)。后一部分為后一部分為位移量位移量 W，即頁(yè)內(nèi)地址，即頁(yè)內(nèi)地址 (212)。n 從邏輯地址獲得頁(yè)號(hào)從邏輯地址獲得頁(yè)號(hào) p和頁(yè)內(nèi)偏移和頁(yè)內(nèi)偏移 dp=INT(A/L)d=[A] MOD LA—— 邏輯地址；邏輯地址； L—— 頁(yè)大小頁(yè)大小齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬60齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬61n 各頁(yè)離散存儲(chǔ)在任一物理塊，系統(tǒng)需記錄各各頁(yè)離散存儲(chǔ)在任一物理塊，系統(tǒng)需記錄各頁(yè)面對(duì)應(yīng)的物理塊。頁(yè)面對(duì)應(yīng)的物理塊。n 系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)面映射表，簡(jiǎn)稱系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)面映射表，簡(jiǎn)稱頁(yè)表。頁(yè)表。 進(jìn)程的所有頁(yè)，依次在頁(yè)表中有一頁(yè)進(jìn)程的所有頁(yè)，依次在頁(yè)表中有一頁(yè)表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。n 頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射映射 。查找頁(yè)表，即可找到每頁(yè)在內(nèi)存中的。查找頁(yè)表，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)。物理塊號(hào)。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬62頁(yè)表的作用頁(yè)表的作用實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射作業(yè)每頁(yè) 1K 內(nèi)存每塊 1K齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬63 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)n 功能：功能： 完成從邏輯地址（頁(yè)號(hào)完成從邏輯地址（頁(yè)號(hào) +頁(yè)內(nèi)地址）頁(yè)內(nèi)地址）到物理地址的轉(zhuǎn)換。到物理地址的轉(zhuǎn)換。l(頁(yè)與物理塊的大小完全一致，故頁(yè)與物理塊的大小完全一致，故 )頁(yè)內(nèi)地址頁(yè)內(nèi)地址 和內(nèi)和內(nèi)存物理塊中的物理地址是一一對(duì)應(yīng)的，存物理塊中的物理地址是一一對(duì)應(yīng)的， 無(wú)需再無(wú)需再轉(zhuǎn)換轉(zhuǎn)換l頁(yè)號(hào)需轉(zhuǎn)換成內(nèi)存中的物理塊號(hào)頁(yè)號(hào)需轉(zhuǎn)換成內(nèi)存中的物理塊號(hào) ，這也是地址，這也是地址變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。 借助于頁(yè)表完成借助于頁(yè)表完成。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)存中 。n 需設(shè)置一個(gè)需設(shè)置一個(gè) 頁(yè)表寄存器頁(yè)表寄存器 PTR（（ PageTable Register），）， 存放頁(yè)表在內(nèi)存的始址和頁(yè)表存放頁(yè)表在內(nèi)存的始址和頁(yè)表的長(zhǎng)度的長(zhǎng)度 。進(jìn)程未執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)存于進(jìn)。進(jìn)程未執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)存于進(jìn)程的程的 PCB中；執(zhí)行時(shí)，才將它們裝入中；執(zhí)行時(shí)，才將它們裝入 PTR。齊魯工業(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è)表。，再以頁(yè)號(hào)為索引去檢索頁(yè)表。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)部分。，將之裝入物理地址的物理塊號(hào)部分。l 4)最后再將有效地址中的最后再將有效地址中的 頁(yè)內(nèi)地址送入頁(yè)內(nèi)地址送入 物理地址寄物理地址寄存器的塊內(nèi)地址中。存器的塊內(nèi)地址中。齊魯工業(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)存 。n 第一次是訪問(wèn)內(nèi)存中的頁(yè)表，從中找到該頁(yè)的物理第一次是訪問(wèn)內(nèi)存中的頁(yè)表，從中找到該頁(yè)的物理塊號(hào)，將此塊號(hào)與頁(yè)內(nèi)偏移量塊號(hào)，將此塊號(hào)與頁(yè)內(nèi)偏移量 W拼接以形成物理地拼接以形成物理地址；第二次訪問(wèn)內(nèi)存時(shí)，才是從第一步所得地址中址；第二次訪問(wèn)內(nèi)存時(shí)，才是從第一步所得地址中獲得所需數(shù)據(jù)獲得所需數(shù)據(jù) (或向此地址中寫入數(shù)據(jù)或向此地址中寫入數(shù)據(jù) )。n 將使計(jì)算機(jī)的處理速度降低近將使計(jì)算機(jī)的處理速度降低近 1/2。n ？？齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬692. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)n 增設(shè)增設(shè) 一個(gè)具有并行查尋能力的一個(gè)具有并行查尋能力的 特殊高速緩沖特殊高速緩沖寄存器寄存器 ，又稱為，又稱為 “聯(lián)想寄存器聯(lián)想寄存器 ”(Associative Memory)或或 “快表快表 ”， 用于存放當(dāng)前訪問(wèn)的那用于存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)些頁(yè)表項(xiàng) 。（意味著這些頁(yè)表項(xiàng)不在存放在。（意味著這些頁(yè)表項(xiàng)不在存放在內(nèi)存中）內(nèi)存中）齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬702. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)n 地址變換過(guò)程：地址變換過(guò)程：l 在在 CPU給出有效地址后，由地址變換機(jī)構(gòu)自動(dòng)地將給出有效地址后，由地址變換機(jī)構(gòu)自動(dòng)地將頁(yè)號(hào)頁(yè)號(hào) P送入高速緩沖存儲(chǔ)器（快表），將此頁(yè)號(hào)與送入高速緩沖存儲(chǔ)器（快表），將此頁(yè)號(hào)與其中的頁(yè)號(hào)進(jìn)行比較其中的頁(yè)號(hào)進(jìn)行比較l 若有相匹配的頁(yè)號(hào)（在快表中），直接讀出其所對(duì)若有相匹配的頁(yè)號(hào)（在快表中），直接讀出其所對(duì)應(yīng)的物理塊號(hào)，并送物理地址寄存器中。應(yīng)的物理塊號(hào)，并送物理地址寄存器中。l 若沒(méi)有匹配的，還需訪問(wèn)內(nèi)存中的頁(yè)表。找到后，若沒(méi)有匹配的，還需訪問(wèn)內(nèi)存中的頁(yè)表。找到后，把對(duì)應(yīng)的物理塊號(hào)送地址寄存器；也將此頁(yè)表項(xiàng)存把對(duì)應(yīng)的物理塊號(hào)送地址寄存器；也將此頁(yè)表項(xiàng)存入快表中。但如果快表已滿，則將一個(gè)老的且已被入快表中。但如果快表已滿，則將一個(gè)老的且已被認(rèn)為不再需要的頁(yè)表項(xiàng)換出。認(rèn)為不再需要的頁(yè)表項(xiàng)換出。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬712. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬722. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)n 由于成本，快表不可能做的很大，一般只存由于成本，快表不可能做的很大，一般只存放放 16~512個(gè)頁(yè)表項(xiàng)。但對(duì)于中小型作業(yè)來(lái)說(shuō)個(gè)頁(yè)表項(xiàng)。但對(duì)于中小型作業(yè)來(lái)說(shuō)，已有可能把全部頁(yè)表項(xiàng)放在快表中，但對(duì)，已有可能把全部頁(yè)表項(xiàng)放在快表中，但對(duì)于大型作業(yè)，則只能將其一部分頁(yè)表項(xiàng)放入于大型作業(yè)，則只能將其一部分頁(yè)表項(xiàng)放入其中。從快表中能找到所需頁(yè)表項(xiàng)的機(jī)率，其中。從快表中能找到所需頁(yè)表項(xiàng)的機(jī)率，可達(dá)可達(dá) 90%以上。以上。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬73練習(xí)練習(xí) 例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中： ①① 如果對(duì)主存的一次存取需要如果對(duì)主存的一次存取需要 μs, 試問(wèn)試問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少 ? ②② 如果系統(tǒng)加有快表如果系統(tǒng)加有快表 ,平均命中率為平均命中率為 85%,當(dāng)當(dāng)頁(yè)表項(xiàng)在快表中時(shí)頁(yè)表項(xiàng)在快表中時(shí) ,其查找時(shí)間忽略為其查找時(shí)間忽略為 0, 試問(wèn)此時(shí)的存取時(shí)間是多少試問(wèn)此時(shí)的存取時(shí)間是多少 ?齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬74練習(xí)練習(xí)答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：一次是訪問(wèn)頁(yè)表，確定所存取頁(yè)需兩次訪問(wèn)主存：一次是訪問(wèn)頁(yè)表，確定所存取頁(yè)面的物理地址（稱為定位）。第二次才根據(jù)該地址面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù)。存取頁(yè)面數(shù)據(jù)。 ■■ 頁(yè)表在主存的存取訪問(wèn)時(shí)間頁(yè)表在主存的存取訪問(wèn)時(shí)間 =*2=3(μs ) ■■ 增加快表后的存取訪問(wèn)時(shí)間增加快表后的存取訪問(wèn)時(shí)間 =*+()*2*=(μs)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬75練習(xí)練習(xí)n 某存儲(chǔ)器的用戶編程空間共某存儲(chǔ)器的用戶編程空間共 32個(gè)頁(yè)面，每頁(yè)為個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)存為，內(nèi)存為 16KB。假定某時(shí)刻一用戶頁(yè)表中。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：已調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：頁(yè)號(hào)頁(yè)號(hào) 物理塊號(hào)物理塊號(hào)0 51 102 43 7則邏輯地址 0A5C（ H）所對(duì)應(yīng)的物理地址為 ： 125C齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬76練習(xí)練習(xí)v 0A5C＝＝ 0000,1010,0101,1100v 頁(yè)號(hào)為頁(yè)號(hào)為 2，對(duì)應(yīng)塊號(hào)為，對(duì)應(yīng)塊號(hào)為 4，有：，有：v 物理地址：物理地址： 0001， 0010,0101,1100v 即：即： 125C齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬77 兩級(jí)和多級(jí)頁(yè)表兩級(jí)和多級(jí)頁(yè)表n 引入：引入：計(jì)算機(jī)支持的邏輯地址空間非常大計(jì)算機(jī)支持的邏輯地址空間非常大 (232~264)，每個(gè)進(jìn)程的每個(gè)進(jìn)程的 頁(yè)表項(xiàng)也非常龐大，需占據(jù)大量的頁(yè)表項(xiàng)也非常龐大，需占據(jù)大量的連續(xù)內(nèi)存空間連續(xù)內(nèi)存空間 ，這顯然不現(xiàn)實(shí)。，這顯然不現(xiàn)實(shí)。n 如何解決？如何解決？－－解決需大量連續(xù)內(nèi)存采用離散分配方式－－解決需大量連續(xù)內(nèi)存空間問(wèn)題空間問(wèn)題 (將頁(yè)表再次進(jìn)行分塊將頁(yè)表再次進(jìn)行分塊 )－－使只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存－－使頁(yè)表需占用的內(nèi)存減少頁(yè)表需占用的