【正文】 院 鹿文鵬100分段系統(tǒng)中共享分段系統(tǒng)中共享 editor示意示意editordata1editordata2段長(zhǎng)段長(zhǎng) 基址基址160 8040 240段長(zhǎng)段長(zhǎng) 基址基址160 8040 380editordata1……data2進(jìn)程 2進(jìn)程 1在分段系統(tǒng)中，實(shí)現(xiàn)共享只需在每個(gè)進(jìn)程的段表中為文本編輯程序代碼段設(shè)置一個(gè)段表項(xiàng)，比分頁(yè)系統(tǒng)簡(jiǎn)單的多。系統(tǒng)則能很好地滿(mǎn)足用戶(hù)需要。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬106，從中得到該段的頁(yè)表始址； P獲得對(duì)應(yīng)頁(yè)的頁(yè)表項(xiàng)位置，從中讀出該頁(yè)所在的物理塊號(hào) b； b和頁(yè)內(nèi)地址來(lái)構(gòu)成物理地址。 分段系統(tǒng)的地址變換過(guò)程分段系統(tǒng)的地址變換過(guò)程187。 不再運(yùn)行的程序模塊仍將占用寶貴的內(nèi)存資源不再運(yùn)行的程序模塊仍將占用寶貴的內(nèi)存資源n 一次性及駐留性是否是必需的？一次性及駐留性是否是必需的？齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬112 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入n n 程序執(zhí)行時(shí)的特點(diǎn)：程序執(zhí)行時(shí)的特點(diǎn)：– 程序執(zhí)行時(shí)，除少部分轉(zhuǎn)移和過(guò)程調(diào)用指令外，程序執(zhí)行時(shí)，除少部分轉(zhuǎn)移和過(guò)程調(diào)用指令外，大多仍是順序執(zhí)行的。一段時(shí)間內(nèi)所訪(fǎng)問(wèn)的地址可能集中于一定的范圍之內(nèi)。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬114 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入n 引入虛擬存儲(chǔ)器引入虛擬存儲(chǔ)器– 基于局部性原理，程序可僅將需運(yùn)行的部分頁(yè)或基于局部性原理，程序可僅將需運(yùn)行的部分頁(yè)或段裝入內(nèi)存便可開(kāi)始執(zhí)行。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬115 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入n – 具有具有 請(qǐng)求調(diào)入請(qǐng)求調(diào)入 功能和功能和 置換置換 功能，能從功能，能從 邏輯上對(duì)內(nèi)邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充存容量進(jìn)行擴(kuò)充 的一種存儲(chǔ)系統(tǒng)。n 為什么？為什么？– 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 請(qǐng)求調(diào)入請(qǐng)求調(diào)入 頁(yè)面轉(zhuǎn)換頁(yè)面轉(zhuǎn)換– 若采用連續(xù)分配方式，一次性將全部數(shù)據(jù)調(diào)入若采用連續(xù)分配方式，一次性將全部數(shù)據(jù)調(diào)入，無(wú)需虛擬存儲(chǔ)。換功能，調(diào)入需要的段，同時(shí)將暫不需要的調(diào)出。頁(yè)號(hào)頁(yè)號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P訪(fǎng)問(wèn)字訪(fǎng)問(wèn)字段段 A修改位修改位M外存地外存地址址P:是否已調(diào)入內(nèi)存A:一段時(shí)間內(nèi)使用的次數(shù)或多久未使用M:調(diào)入內(nèi)存后是否修改過(guò)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬124 請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持n – 當(dāng)訪(fǎng)問(wèn)的頁(yè)不在內(nèi)存中時(shí)便產(chǎn)生缺頁(yè)中斷，請(qǐng)當(dāng)訪(fǎng)問(wèn)的頁(yè)不在內(nèi)存中時(shí)便產(chǎn)生缺頁(yè)中斷，請(qǐng)求求 OS將其調(diào)入。 一條指令在執(zhí)行期間，可能要產(chǎn)生多次中斷。結(jié)束。返回從外存將。如未找到，則轉(zhuǎn) 3。內(nèi)存即產(chǎn)生；通常是在等到指令執(zhí)行完畢后。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬122 請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式n 請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持n 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法n 調(diào)頁(yè)策略調(diào)頁(yè)策略齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬123 請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持n – 由于應(yīng)用程序只是一部分調(diào)入內(nèi)存即只有部由于應(yīng)用程序只是一部分調(diào)入內(nèi)存即只有部分頁(yè)位于內(nèi)存中，須在頁(yè)表中增加若干項(xiàng)，分頁(yè)位于內(nèi)存中，須在頁(yè)表中增加若干項(xiàng)，供程序（數(shù)據(jù)）換進(jìn)換出時(shí)參考。只裝入部分段即可運(yùn)行，可通過(guò)調(diào)段和段置。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬116 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法n 虛擬存儲(chǔ)器是建立在虛擬存儲(chǔ)器是建立在 離散分配的存儲(chǔ)管理方離散分配的存儲(chǔ)管理方式基礎(chǔ)上式基礎(chǔ)上 的。也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。（循環(huán)操作）n 根據(jù)局部性原理，程序在運(yùn)行之前沒(méi)有必要根據(jù)局部性原理，程序在運(yùn)行之前沒(méi)有必要一次性全部裝入，也沒(méi)必要長(zhǎng)期駐留內(nèi)存。– 程序中存在循環(huán)結(jié)構(gòu)，它們將多次執(zhí)行程序中存在循環(huán)結(jié)構(gòu)，它們將多次執(zhí)行– 程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往局限于較小的范程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往局限于較小的范圍內(nèi)圍內(nèi)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬113 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入n n 局部性的表現(xiàn)：局部性的表現(xiàn)：– 空間局限性。 這可能導(dǎo)致大作業(yè)無(wú)法裝入這可能導(dǎo)致大作業(yè)無(wú)法裝入187。段表和頁(yè)表存儲(chǔ)在高速緩沖中。先查段表，再查該段的頁(yè)表，才能找到物理塊號(hào)。如：號(hào)共享同一段。頁(yè)面。（舉例對(duì)比）n 可重入代碼：一種允許多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)（可重入代碼：一種允許多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)（可被共享）的代碼；不允許任何進(jìn)程對(duì)它進(jìn)可被共享）的代碼；不允許任何進(jìn)程對(duì)它進(jìn)行修改?？棾梢粋€(gè)地址空間；標(biāo)識(shí)地址需給出段名和段內(nèi)地址。用于保存最近常用的段表項(xiàng)。n 為了能將物理內(nèi)存與邏輯段地址對(duì)應(yīng)起來(lái)，為了能將物理內(nèi)存與邏輯段地址對(duì)應(yīng)起來(lái)，需為每個(gè)進(jìn)程建立一張需為每個(gè)進(jìn)程建立一張 段映射表段映射表 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬89 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理n n n 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬90n 作業(yè)的地址空間被作業(yè)的地址空間被 劃分為若干個(gè)段劃分為若干個(gè)段 ，每個(gè)段，每個(gè)段用來(lái)定義一組邏輯信息，均用來(lái)定義一組邏輯信息，均 從從 0開(kāi)始開(kāi)始 編址，編址，并采用一段并采用一段 連續(xù)的連續(xù)的 地址空間。2)信息共享信息共享實(shí)現(xiàn)共享是以信息的邏輯單位－段為基礎(chǔ)的實(shí)現(xiàn)共享是以信息的邏輯單位－段為基礎(chǔ)的。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬84 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式 小結(jié)小結(jié)n 頁(yè)面、物理塊與頁(yè)表頁(yè)面、物理塊與頁(yè)表 n 分頁(yè)地址結(jié)構(gòu)：分頁(yè)地址結(jié)構(gòu)： 頁(yè)號(hào)＋頁(yè)內(nèi)地址頁(yè)號(hào)＋頁(yè)內(nèi)地址n 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) – 基本的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)– 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)n 兩級(jí)和多級(jí)頁(yè)表兩級(jí)和多級(jí)頁(yè)表齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬85 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式n 存儲(chǔ)管理方式從固定分區(qū)到動(dòng)態(tài)分區(qū)分配，存儲(chǔ)管理方式從固定分區(qū)到動(dòng)態(tài)分區(qū)分配，進(jìn)而到分頁(yè)存儲(chǔ)管理方式主要是為了提高內(nèi)進(jìn)而到分頁(yè)存儲(chǔ)管理方式主要是為了提高內(nèi)存的利用率。在外層頁(yè)表的表項(xiàng)中，需增設(shè)一個(gè)狀態(tài)位，表示相在外層頁(yè)表的表項(xiàng)中，需增設(shè)一個(gè)狀態(tài)位，表示相應(yīng)的頁(yè)表分頁(yè)是否已調(diào)入內(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)成了要訪(fǎng)問(wèn)的內(nèi)存的物理地，即構(gòu)成了要訪(fǎng)問(wèn)的內(nèi)存的物理地址。第二次才根據(jù)該地址面的物理地址（稱(chēng)為定位）。認(rèn)為不再需要的頁(yè)表項(xiàng)換出。（意味著這些頁(yè)表項(xiàng)不在存放在。l 2)在檢索頁(yè)表前，在檢索頁(yè)表前， 將頁(yè)號(hào)與頁(yè)表長(zhǎng)度比較將頁(yè)號(hào)與頁(yè)表長(zhǎng)度比較 ，如果越，如果越界則產(chǎn)生一越界中斷，本次訪(fǎng)問(wèn)失敗界則產(chǎn)生一越界中斷，本次訪(fǎng)問(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)部分。變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。 “頁(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è)大學(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)。n 對(duì)換空間的對(duì)換空間的 分配與回收分配與回收 ，與動(dòng)態(tài)分區(qū)分配方，與動(dòng)態(tài)分區(qū)分配方式中的內(nèi)存分配與回收方法雷同。為了進(jìn)程對(duì)換，需三方面功能：對(duì)換空間的管理、進(jìn)程的換出及換入。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持地址變換，硬件上需要重定位寄存器的支持。消除內(nèi)存碎片，提高內(nèi)存利用問(wèn)題。n 為避免影響速度，為避免影響速度， 必須有硬件地址變換機(jī)構(gòu)的支持必須有硬件地址變換機(jī)構(gòu)的支持（重定位寄存器）（重定位寄存器） ，用它來(lái)存放程序在內(nèi)存中的起，用它來(lái)存放程序在內(nèi)存中的起始地址。區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。每次分配后所切割下來(lái)的剩余部分總是最小的。n 優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分區(qū)的開(kāi)銷(xiāo)，但會(huì)導(dǎo)致缺乏大的空閑分區(qū)。作業(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è)能滿(mǎn)足要求的空閑分區(qū)，并從中劃出一塊到第一個(gè)能滿(mǎn)足要求的空閑分區(qū)，并從中劃出一塊與請(qǐng)求的大小相等的內(nèi)存空間分配給作業(yè)。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ū) 以地址遞增以地址遞增 的次序鏈接。每個(gè)空閑分區(qū)占一個(gè)表目目 ，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。在某些用于控制相同對(duì)象的場(chǎng)合仍有一定應(yīng)用。區(qū)。找出另一個(gè)作業(yè)調(diào)入該分區(qū)。n 優(yōu)點(diǎn)：本次執(zhí)行優(yōu)點(diǎn)：本次執(zhí)行 不需要的模塊不鏈接不需要的模塊不鏈接 。 可將一個(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的共享 。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。（。在裝入時(shí)，指令的地址會(huì)由原來(lái)的 1000，變?yōu)?11000，取數(shù)地址 2500也會(huì)變?yōu)?12500。地址。齊魯工業(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)代碼代碼 。邏輯空間中的地址稱(chēng)為邏輯地址的邏輯地址空間。后兩者需要通過(guò) I/O訪(fǎng)問(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 高速緩存高速緩存– 局部性原理局部性原理–