計算機操作系統(tǒng)之存儲器管理

第四章存儲器管理4.1程序的裝入和鏈接

編輯―――編譯―――鏈接―――裝入―――運行圖4.12007年1月4.1.1程序的裝入

1、絕對裝入：編譯后，裝入前已產(chǎn)生了絕對地址（內(nèi)存地址），裝入時不再作地址重定位。絕對地址的產(chǎn)生：（1）由編譯器完成，（2）由程序員編程完成。對（1）而言，編程用符號地址。2、可重定位裝入；靜態(tài)重定位：裝入時完成，主要工作是對相對地址中的指令和數(shù)據(jù)地址的調(diào)整過程，例：圖4－2問題：如何知道哪些位置需調(diào)整？鏈接時產(chǎn)生可裝入模塊的具體功能?2007年1月0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作業(yè)地址空間內(nèi)存空間圖4-22007年1月4.1.1程序的裝入

3.動態(tài)運行時裝入在裝入后不能移動，該情況一般在執(zhí)行時才完成相對——絕對地址的轉(zhuǎn)換且有硬件的支持,能保證進程的可移動性。2007年1月4.1.2程序的鏈接1、靜態(tài)鏈接a．對相對地址的修改b．變換外部調(diào)用符號2、裝入時動態(tài)鏈接a.便于修改和更新b.便于實現(xiàn)對目標模塊的共享3、運行時動態(tài)鏈接2007年1月模塊ACALLB;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標模塊模塊AJSRL;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊2007年1月4.2連續(xù)分配方式

單一連續(xù)分配用于單用戶，單任務中分區(qū)式分配固定式可變式可重定位分區(qū)分配2007年1月4.2.1單一連續(xù)分區(qū)系統(tǒng)區(qū)用戶區(qū)存貯保護一般不設置保護也可，因單任務。

2007年1月4.2.2固定分區(qū)特點：有n個分區(qū)，則可同時裝入n個作業(yè)/任務。一、分區(qū)大小：相等:不相等：不相等利用率更高。二、內(nèi)存分配：數(shù)據(jù)結構將分區(qū)按大小排序，并將其地址、分配標識作記錄例：dos的MCB三、特點：簡單，有碎片（內(nèi)零頭）2007年1月圖4－4a分區(qū)號大?。↘)起址（K）狀態(tài)11220已分配23232已分配36464已分配4128128已分配2007年1月圖4－4b操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24K32K64K128K256K~~~~分配情況2007年1月4.2.3可變式分區(qū)（比固定式分區(qū)有改善）一、數(shù)據(jù)結構1．空閑分區(qū)表2．空閑分區(qū)鏈前向指針N個字節(jié)可用后向指針N+2N+20（分配標識）02007年1月4.2.3可變式分區(qū)（比固定式分區(qū)有改善）二、分配算法1．首次適應算法FF。要求：分區(qū)按低址――高址鏈接特點：找到第一個大小滿足的分區(qū)，劃分。有外零頭，低址內(nèi)存使用頻繁。2．循環(huán)首次適應算法。從1中上次找到的空閑分區(qū)的下一個開始查找。特點：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)。3．最佳適應算法分區(qū)按大小遞增排序；分區(qū)釋放時需插入到適當位置。2007年1月4.2.3可變式分區(qū)（比固定式分區(qū)有改善）三、分區(qū)分配1．分配：圖4-62．回收：（1）上鄰空閑區(qū)：合并，改大?。?）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項。2007年1月2007年1月F1回收區(qū)回收區(qū)F2F1回收區(qū)F24-7內(nèi)存回收時的情況2007年1月4.2.4可重定位分區(qū)分配1.動態(tài)重定位的引入連續(xù)式分配中，總量大于作業(yè)大小的多個小分區(qū)不能容納作業(yè)。緊湊通過作業(yè)移動將原來分散的小分區(qū)拼接成一個大分區(qū)。作業(yè)的移動需重定位。是動態(tài)（因作業(yè)已經(jīng)裝入）2007年1月緊湊操作系統(tǒng)用戶程序110kb用戶程序330kb用戶程序614kb用戶程序926kb操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序92007年1月2、動態(tài)重定位的實現(xiàn)25005000365load1,2500365load1,250001002500100001000010100+1250015000作業(yè)J處理機一側存儲器一側重定位寄存器相對地址2007年1月圖4.10動態(tài)分區(qū)分配算法2007年1月4.2.5對換1對換的引入將阻塞進程，暫時不用的程序，數(shù)據(jù)換出。將具備運行條件的進程換入。類型：整體對換：進程對換，解決內(nèi)存緊張部分對換：頁面對換/分段對換：提供虛存支持2對換空間的管理外存對換區(qū)比文件區(qū)側重于對換速度。因此，對換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結構和分配回收類似于可變化分區(qū)分配。2007年1月4.2.5對換3換出與換入一、換出1．選出被換出進程： 因素：優(yōu)先級，駐留時間，進程狀態(tài)2．換出過程：對于共享段：計數(shù)減1，是0則換出，否則不換修改PCB和MCB（或內(nèi)存分配表）二、換入：1．選擇換入進程：優(yōu)先級，換出時間等。2．申請內(nèi)存。3．換入2007年1月4.3基本分頁存儲管理

連續(xù)分配引起:碎片碎片問題的解決：緊湊方式消耗系統(tǒng)開銷。離散分配分頁、分段、段頁2007年1月1.頁面頁面和物理塊：邏輯空間和內(nèi)存空間由機器的地址結構決定頁太大，頁內(nèi)碎片大。頁太?。喉摫砜赡芎荛L，換入/出效率低2.地址結構31 1211 0邏輯地址A；頁大小L(設為1024)；頁內(nèi)偏移d d=AmodL如：A＝2170B.則P=2,d=1224.3.1頁面與頁表頁號P位移W2007年1月3.頁表n頁5頁4頁3頁2頁1頁0頁594836231209876543210用戶程序頁表頁號塊號內(nèi)存2007年1月4.2地址變換機構

完成：邏輯頁號——物理塊號的映射，由頁表完成。一、基本地址變換機構： 越界保護每個進程對應一頁表，其信息（如長度、始址）放在PCB中，執(zhí)行時將其首地址裝入頁表寄存器。2007年1月2007年1月2.具有快表的地址變換機構

不具快表，則需兩次訪問內(nèi)存。（1）訪頁表（2）得到絕對地址內(nèi)容有快表，速度提高?？毂碣F，不能太多。2007年1月2.具有快表的地址變換機構2007年1月

例：有一頁式系統(tǒng)，其頁表存放在主存中：①如果對主存的一次存取需要1.5μs,試問實現(xiàn)一次頁面訪問的存取時間是多少?②如果系統(tǒng)加有快表,平均命中率為85%,當頁表項在快表中時,其查找時間忽略為0,

試問此時的存取時間是多少?2007年1月答：若頁表存放在主存中，則要實現(xiàn)一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)。■頁表在主存的存取訪問時間

=1.5*2=3(μs)■增加快表后的存取訪問時間

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)2007年1月4.3.3兩級和多級頁表

頁表可能很大，將其離散存放在不同頁塊中。建一“外部頁表”來管理這些離散頁表塊。相當于單級頁表中的頁表寄存器，一般應常駐內(nèi)存。每項記錄頁表始址，且增加存在位。64位機器頁表一般>3級，最外層頁表常駐。2007年1月2007年1月2007年1月例某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內(nèi)存為16KB。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面對應的物理塊號如下表：頁號物理塊號051102437則邏輯地址0A5C（H）所對應的物理地址為：125C2007年1月例0A5C＝0000,1010,0101,1100頁號為2，對應塊號為4，有：物理地址：0001，0010,0101,1100即：125C2007年1月4.4基本分段存儲管理

即多重定位分區(qū)管理4.4.1引入每個段可有其邏輯意義及功能，使得便于（1）方便編程；（2）分段共享；（3）分段保護；（4）動態(tài)鏈接；（5）動態(tài)增長；（如數(shù)據(jù)段的增長）2007年1月4.4.2分段系統(tǒng)的基本原理

分段對用戶而言，分段是2維的。段號+段內(nèi)地址。段表：邏輯段—map—物理段地址變換機構：圖4－16，4－17分頁與分段：（1）頁是信息的物理單位，段是邏輯單位（2）頁長度固定，段長度不固定（由用戶指定）（3）一維與二維2007年1月2007年1月2007年1月4.4.3共享

段式系統(tǒng)易于共享例：圖4-18及4-19

分頁與分段共享比較可重入碼（純代碼）各個進程應保留局部數(shù)據(jù)區(qū)2007年1月data10…data1ed40…ed2ed170…6160…2221ed40data10…data1data10…data1…ed2ed1…進程1進程2頁表頁表data10…data1ed40…ed2ed180…7160…2221主存分頁系統(tǒng)中共享editor2007年1月分段系統(tǒng)中共享editoreditordata1editordata2段長基址1608040240段長基址1608040380editordata1…data22007年1月4.4.4段頁式存儲管理分頁優(yōu)點：提高內(nèi)存利用率分段優(yōu)點：方便用戶，易于共享，保護，動態(tài)鏈接。一、段頁式系統(tǒng)基本原理

段號+段內(nèi)頁號+頁內(nèi)地址注意： 對用戶而言，仍然是二維編址。對系統(tǒng)而言，則是三維編址2007年1月4.4.4段頁式存儲管理二、地址變換

三次訪內(nèi)存操作，為提高速度，在地址變換機構中增設一高速緩沖寄存器（Cache）2007年1月4.5虛擬存儲器4.5.1引入1.常規(guī)存儲管理的特征：一次性（指全部裝入）、駐留性（指駐留在內(nèi)存不換出）2、局部性原理時間局部性：如循環(huán)執(zhí)行空間局部性：如順序執(zhí)行。3、虛擬存貯器具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲系統(tǒng)。實質(zhì)：以時間換空間，但時間犧牲不大。虛擬大小由_______決定。2007年1月4.5.2虛擬存儲器的實現(xiàn)方式需要動態(tài)重定位一、請求分頁系統(tǒng)以頁為單位轉(zhuǎn)換需硬件：（1）請求分頁的頁表機制（2）缺頁中斷（3）地址變換機構需實現(xiàn)請求分頁機制的軟件（置換軟件等）二、請求分段系統(tǒng)以段為單位轉(zhuǎn)換:（1）請求分段的段表結構（2）缺段中斷（3）地址變換機構需實現(xiàn)請求分段機制的軟件（置換軟件等）2007年1月4.5.3虛存特征1．離散性：部分裝入 （若連續(xù)則不可能提供虛存），無法支持大作業(yè)小內(nèi)存運行2．多次性：局部裝入，多次裝入。3．對換性：4．虛擬性.2007年1月4.6.1請求分頁中的數(shù)據(jù)結構及硬件支持一、頁表機制頁表項：二、缺頁中斷機構：可在指令執(zhí)行期間產(chǎn)生（如圖4-23） 轉(zhuǎn)入缺頁中斷處理程序。三、地址變換機構 比較簡單分頁機制，增加了中斷處理，圖4.244.6請求分頁存儲管理頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址2007年1月

圖4－23涉及6次缺頁中斷的指令2007年1月4.6.2內(nèi)存分配策略和分配算法一、最小物理塊數(shù)不同的作業(yè)要求不同。如：允許間接尋址：則至少要求3個物理塊。

MovA,[B]2007年1月4.6.2內(nèi)存分配策略和分配算法二、頁面分配和置換策略。1．固定分配局部置換。缺點：難以確定固定分配的頁數(shù).(少：置換率高多：浪費)2.可變分配全局置換3.可變分配局部置換根據(jù)進程的缺頁率進行頁面數(shù)調(diào)整，進程之間相互不會影響。2007年1月三、分配算法

1．平均分配算法2．按進程大小比例分配算法：3．考慮優(yōu)先權分配算法2007年1月4.6.3頁面調(diào)入策略

1.調(diào)入時機：預調(diào)：（根據(jù)空間局部性）目前：成功率≤50％請求調(diào)：較費系統(tǒng)開銷各有優(yōu)劣2．從何處調(diào)頁：對換區(qū)：修改過的頁被換出時入對換區(qū)， 快文件區(qū)： 稍慢對共享頁，應判斷其是否在內(nèi)存區(qū)。3.頁面調(diào)入過程2007年1月目的：減少對換量，提高系統(tǒng)性能4.7.1最佳置換算法和先進先出算法一、最佳置換算法（理論上的）4.7頁置換算法

2007年1月4.7頁置換算法

目的：減少對換量，提高系統(tǒng)性能4.7.1最佳置換算法和先進先出算法二、FIFO2007年1月4.7.2最近最久未用LRU置換一、算法描述將“最近的過去”，作為“最近的將來”。圖4-27二、LRU算法的硬件支持：（用來記錄誰最近最久未訪問）1．位移寄存器：（定時右移）

R=Rn-1…R0圖4-282．棧：當進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。

圖4-292007年1月LRU2007年1月4.7.3clock置換（LRU近似算法：硬件消耗少）一、簡單算法：設一訪問位：圖4-30循環(huán)掃描，每次掃描時將訪問位復位。2007年1月2007年1月2007年1月4.7.3clock置換（LRU近似算法：硬件消耗少）二、改進：

A=0;M=02007年1月4.7.4其它一、最少使用（是頻率）與LRU類似（記錄訪問次數(shù)），設置一個訪問計數(shù)器。二、頁面緩沖算法：特點：淘汰的頁只是修改標志；若頁被修改過，則在欲復蓋它時回寫，否則成批回寫。在欲重訪問該頁時，若頁換出則只需修改標志。2007年1月4.8請求分段存儲管理方式段表：段名段長段基址存取方式訪問字段A修改字段M存在位P增補位外存起址二、缺段中斷機構：段不定長，處理起來比缺頁中斷復雜。

三、地址變換機構

2007年1月4.8.2分段的共享與保護一、共享段表：（整個系統(tǒng)一張）

1.共享進程計數(shù)。2.存取控制字段。3.段號：不同的進程可以使用不同的段號去共享段。2007年1月段名段長內(nèi)存地址狀態(tài)外存地址共享進程計數(shù)狀態(tài)進程名進程號段號存取控制2007年1月4.8.2分段的共享與保護二、共享段的分配與回收1.分配：第一次訪問：分配內(nèi)存，（1）增加共享段表；（2）修改進程段表。第二次訪問：（1）修改共享段表；（2）修改進程段表。2.回收：（1）count=0（2）count<>02007年1月4.8.2分段的共享與保護三、分段保護1.越界檢查段號越界檢查。段內(nèi)偏移越界檢查。2.存取控制檢查。R；R/W；E3.環(huán)保護機構（1）內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù)；（2）外環(huán)可請求內(nèi)環(huán)服務。2007年1月試驗

實現(xiàn)LRU算法和FIFO算法要求給出任意的輸入流、計算失效率。輸入流長度、cache尺寸可定制。測試：Cache＝5，從0－9可數(shù)字的任意排序，長度為30。例如：12568,36536,56892,70495,36745,873452007年1月保護模式虛地址和虛地址空間虛地址：程序中的地址，如MOVEREG,2000內(nèi)存管理單元（MMU）：完成地址轉(zhuǎn)換（圖4.1）2007年1月段機制和頁機制虛擬地址空間：二維：16k*4G=64T（LDT8K＋GDT8K）線性地址空間:一維：4G物理地址空間:一維：4G選擇子偏移量：段機制313101500頁機制310線性地址物理地址2007年1月段機制段基地址段界限段屬性以上三者存儲在段描述符表中2007年1月圖4.42007年1月描述符：圖4.5、圖4.6－4.8G：粒度位，＝0時，段長表示段格式的字節(jié)長度，即一個段最長可達1M字節(jié)；＝1時，段長表示段格式以4K字節(jié)為一頁的頁目錄數(shù)，即一個段最長可達1M*4K=4GD：表示缺省操作數(shù)的大小，=0操作數(shù)為16位。＝1為32位2007年1月P:存在位。描述段是否在內(nèi)存S:表示該段是系統(tǒng)段（0）還是用戶段（1）DPL:該段的特權級類型：數(shù)據(jù)段還是代碼段A:該段是否被訪問2007年1月3位:為0表示數(shù)據(jù)段，1表示代碼段W:為0表示不可寫，為1表示可寫2007年1月R:該段可讀否C:一致位，當C=1時，若