1第四章存儲器管理

2第四章存儲器管理如何對存儲器進行有效的管理，不僅影響到存儲器的利用率，而且還對系統性能有重大影響。存儲器：內存（本章）外存（第六章）3主要內容new存儲器的層次結構4.1程序的裝入和鏈接4.2連續分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式4本章學習目標了解存儲管理的研究對象和目的了解存儲管理的基本功能和有關的基本概念掌握分頁存儲管理和分段存儲管理的基本概念掌握請求分頁和請求分段存儲管理的基本原理New4.1存儲器的層次結構1.多級存儲器結構2.主存儲器與寄存器3.高速緩存與磁盤緩存51.多級存儲器結構

寄存器高速緩存內存磁盤緩存磁盤可移動存儲器6三層由快到慢寄存器與主存（前四者）由操作系統直接管理，可快速訪問，稱為可執行存儲器。后兩者需要通過I/O訪問2.主存儲器與寄存器1.主存儲器容量大小2.寄存器速度與CPU完全協調長度以字為單位，幾十至幾百個73.高速緩存和磁盤緩存高速緩存局部性原理CPU與內存之間磁盤緩存頻繁使用的磁盤數據暫存在內存中的磁盤高速緩存中89預備知識地址空間的概念1．內存空間(物理空間)

內存是由若干個存儲單元組成的，每個存儲單元的編號稱為內存地址(或物理地址)2．邏輯空間經過匯編或編譯后形成目標程序是以0為基址順序進行編址的，目標程序占據的地址空間稱為作業的邏輯地址空間。邏輯空間中的地址稱為邏輯地址，這是一個相對地址。104.1程序的裝入和鏈接為作業創建進程需將其裝入內存。要把程序裝入內存，就要對程序進行編譯和鏈接。1.編譯由編譯程序把源程序翻譯成若干個目標模塊；2.鏈接由鏈接程序把目標模塊以及相關的庫函數鏈接在一起，形成完整的裝入模塊；3.裝入由裝入程序把裝入模塊裝入內存。114.1.1程序的裝入將一個裝入模塊裝入內存時，有三種方式：絕對裝入方式可重定位裝入方式動態運行時裝入方式關鍵在于將邏輯地址轉換為物理地址的時機不同121.絕對裝入方式

AbsoluteLoadingMode若編譯時知道程序將在內存的(起始)駐留地址，編譯程序將產生絕對(物理)地址的目標代碼。只適用單道程序環境。裝入模塊不需再地址轉換，直接裝入內存。絕對地址，即可在編譯或匯編時給出，也可由程序員直接給出。通常在程序中采用符號地址，在編譯或匯編時，再將其轉換為絕對地址。132.可重定位裝入方式

RelocationLoadingMode多道程序環境下，各目標模塊的起始地址均從0開始，程序中的其它地址都是相對于起始地址計算的，不是絕對的物理地址，編譯程序無法預知目標模塊應放于何處。裝入時，需根據內存當前的情況，將模塊裝入到內存的適當位置，存在一個邏輯地址空間到內存物理地址空間的轉換過程（即重定位）。142.可重定位裝入方式

RelocationLoadingMode邏輯地址與實際裝入內存的物理地址會不同。Load1,2500的作用是把2500單元中的數據送至寄存器1。在裝入時，指令的地址會由原來的1000，變為11000，取數地址2500也會變為12500。該例中，在裝入時對目標程序中指令和數據的地址修改過程稱為重定位。該地址變換是在裝入時一次完成的，不再改變，故稱為靜態重定位。153.動態運行時裝入方式

DynamicRun-timeLoading把程序裝入內存后，并不立即把裝入模塊中的邏輯地址轉換為物理地址，仍是相對地址。邏輯地址到物理地址的轉換直到程序真正運行時才進行。不僅允許裝入模塊裝入到內存中的任何位置，而且允許程序在運行時在內存中移動。（動態重定位分區分配）164.1.2程序的鏈接根據鏈接時間的不同，可分為：靜態鏈接裝入時動態鏈接運行時動態鏈接關鍵在于進行鏈接的時機171.靜態鏈接方式

StaticLinking在程序運行之前把各目標模塊及庫函數鏈接成一個完整的裝入模塊，以后不再拆開。裝配時需解決兩個問題：(1)對相對地址進行修改。(2)變換外部符號。18模塊ABC在鏈接前其內部地址均是相對于起始地址0而言的。鏈接成一個裝入模塊后，BC的首地址分別變成了L和L+M，這就需要修改BC中的相對地址，將其全部加上L或L+M；對于ABC各模塊中所使用的外部調用符號，也都需進行變換，CALLB需變換為JSLL。192.裝入時動態鏈接

Load-timeDynamicLinking編譯的目標模塊在裝入內存時，邊裝入邊鏈接。即在裝入一個目標模塊時，若發生一個外部模塊調用，將引起裝入程序去找出相應的外部目標模塊，并將它裝入內存，還需修改目標模塊中的相對地址。202.裝入時動態鏈接

Load-timeDynamicLinking優點:VS靜態鏈接

1.便于修改和更新

各目標模塊分開存放，便于修改或更新。靜態鏈接要修改或更新時，需重新打開裝入模塊，低效。

2.便于實現對目標模塊的共享

可將一個目標模塊鏈接到幾個應用模塊，實現多個應用程序對該模塊的共享。靜態鏈接，每個應用模塊都必須含有該目標模塊的完整拷貝，無法共享。213.運行時動態鏈接

Run-timeDynamicLinking把對某些模塊的鏈接推遲到執行時進行。在執行過程中，當發現一個被調用模塊尚未裝入內存時，立即由OS去找到該模塊并鏈接到調用者模塊上。優點：本次執行不需要的模塊不鏈接。可加快裝入過程，而且節省內存空間。224.1程序的裝入和鏈接小結程序的裝入絕對裝入方式可重定位裝入方式動態運行時裝入方式程序的鏈接靜態鏈接方式裝入時動態鏈接運行時動態鏈接234.2連續分配方式

連續分配方式，指為一個用戶程序分配一個連續的內存空間。4.2.1單一連續分區分配4.2.2固定分區分配4.2.3動態分區分配4.2.4動態重定位分區分配4.2.5對換(Swapping)244.2.1單一連續分區分配1.內存劃分

(1)系統區僅提供給OS使用，通常為內存中的低址部分

(2)用戶區單一分區，除系統區外的全部內存空間，只提供給用戶使用2.適用環境只適用于單用戶、單任務環境？254.2.2固定分區分配最早使用的一種可運行多道程序的存儲管理方式。將內存空間劃分為若干個固定大小的區域，在每個分區中可以裝入一道作業，當內存中劃分成幾個分區時，便允許幾道作業并發運行；當有一個空閑分區時，便可從外存的后備隊列中，選擇一個適當大小的作業裝入該分區；當該作業結束時，又可從后備隊列中找出另一個作業調入該分區。劃分分區內存分配261.劃分分區的方法1.分區大小相等 使所有的內存分區大小相等。適用于利用一臺計算機去控制多個相同對象的場合。缺乏靈活性。2.分區大小不等 將內存區分為大小不等的多塊，靈活性稍好，可根據程序的大小為之分配適當的分區。272.內存分配把分區按大小排隊，并建立一個分區使用表。分區表中記錄各分區的起始地址、大小和狀態。分配內存時，檢索分區表，如果存在大小合適且未分配的分區，就把其分配給相應的程序，然后置“已分配”標志；若未找到大小足夠的分區，則拒絕為之分配內存。282.內存分配分區大小固定，靈活性仍不足，會產生內存碎片；在某些用于控制相同對象的場合仍有一定應用。作業2：30K作業1：112K294.2.3動態分區分配動態分區分配是根據進程的實際需要，動態地為之分配內存空間。又稱為可變分區分配。示意圖30可變分區內存使用示意圖314.2.3動態分區分配三個問題分區分配中的數據結構分區分配算法分區分配操作321.分區分配中的數據結構記錄內存的使用情況，為分配提供依據。(1)空閑分區表 在系統中設置一張空閑分區表，用于記錄每個空閑分區的情況。每個空閑分區占一個表目，表目中包括分區序號、分區始址及分區的大小等數據項。331.分區分配中的數據結構(2)空閑分區鏈 每個分區的起始部分，設置用于鏈接各分區的前向指針；在分區尾部設置一后向指針。通過前、后向鏈接指針，可將所有的空閑分區鏈接成一個雙向鏈。前后向指針，大小，狀態342.分區分配算法按照一定的分配算法，從空閑分區表或空閑分區鏈中選出一分區分配給該作業。常用的三種分配算法：首次適應算法循環適應算法最佳適應算法35(1)首次適應算法空閑分區以地址遞增的次序鏈接。分配時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區；然后根據作業的大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑鏈中。優點：傾向于利用內存中低址的空閑區，保留了高址部分的大空閑區，為以后到達的大作業分配大的內存空間創造了條件。 缺點：低址不斷被劃分，會產生大量的碎片；每次從低址開始查找，會增加查找可用空間的開銷。36(1)首次適應算法圖中采用的空閑分區鏈按地址由小到大的順序對空閑分區進行組織，開始指向以40k為首址的空閑分區（其大小為46k，下一個空閑分區為始址為118k）。作業5大小為36k37(2)循環首次適應算法分配時，不每次均從鏈首開始查找，而是從上次找到的空閑分區的下一個空閑分區開始查找，直至找到第一個能滿足要求的空閑分區，并從中劃出一塊與請求的大小相等的內存空間分配給作業。需設置一起始查尋指針，以指示下一次起始查尋的空閑分區，并采用循環查找方式。即如果最后一個(鏈尾)空閑分區，其大小仍不能滿足要求，應返回到第一個空閑分區，比較其大小是否滿足要求。找到后，應立即調整起始查尋指針。優點：空閑分區分布均更均勻，減少了查找空閑分區的開銷，但會導致缺乏大的空閑分區。38(3)最佳適應算法每次為作業分配內存時，總是把既能滿足要求，又是最小的空閑分區分配給作業，避免了“大材小用”。為了加速尋找，要求將所有的空閑區，按其容量大小以遞增的順序形成一空閑區鏈。這樣，第一次找到的滿足要求的空閑區，必然是最優的。特點：每次似乎是最佳的，然而在宏觀上卻不一定。每次分配后所切割下來的剩余部分總是最小的，在存儲器中會留下許多這樣難以利用的小空閑區。39(3)最佳適應算法圖中采用的空閑分區鏈按容量由小到大的順序組織403.分區分配操作(分配－回收)1)分配內存 若m.size-u.size<=size，說明多余部分太小，可不再切割，將整個分區分配給請求者；否則，從該分區中劃分出與請求的大小相等的內存空間分配出去，余下的部分仍留在空閑分區鏈或空閑分區表中。最后，將分配區的首址返回給調用者。m.size空閑分區大小u.size用戶作業大小413.分區分配操作2)回收內存當一個進程（或程序）釋放其所占內存區時，系統將首先檢查回收區是否與其它空閑區相鄰，若相鄰則合并成一個空閑區，否則，將回收區插入空閑分區表（或空閑分區鏈）中的適當位置。回收情況：A.只有前鄰空閑區B.只有后鄰空閑區C.既有前鄰空閑區又有后鄰空閑區D.沒有鄰接空閑區根據不同情況，A、B、C有不同的合并策略。42回收內存示意圖A.將R合并到f1，f1.addr；f1.size+R.size->f1.size

B.將f2

合并到R

，R.addr；f2.size+R.size->f2.size

C.f1、R、f2合并到f1，f1.addr；f1.size+R.size+f2.size->f1.size；撤消f2空閑區表項D.R作為一個新空閑區，插入到空閑區表（鏈）的適當位置。434.2.4動態重定位分區分配1.動態重定位的引入2.動態重定位的實現3.動態重定位分區分配算法441.動態重定位的引入為了充分利用內存碎片，可利用“緊湊”操作把多個碎片處理為一個比較大的分區，以便利用。經過緊湊后的某些用戶程序在內存中的位置發生了變化，此時需對程序和數據的地址加以修改（變換），即需要進行重定位。452.動態重定位的實現采用動態運行時裝入方式，地址轉換推遲到程序指令真正要執行時進行。為避免影響速度，必須有硬件地址變換機構的支持（重定位寄存器），用它來存放程序在內存中的起始地址。程序在執行時，真正訪問的內存地址是相對地址與重定位寄存器中的地址相加而形成的。地址變換過程是在程序執行期間，隨著對每條指令和數據的訪問而自動進行的，故稱為動態重定位。當系統對內存進行了“緊湊”，而使若干程序從內存的某處移至另一處時，不需對程序做任何修改，只要用該程序的新起始地址，去置換原來的起始地址即可。462.動態重定位的實現473.動態重定位分區分配算法與動態分區分配算法基本相同，差別僅在于：增加了緊湊功能，在找不到足夠大的空閑分區來滿足用戶需求時進行緊湊。483.動態重定位分區分配算法優點：解決了動態分區分配所引入的“內存零頭”問題。消除內存碎片，提高內存利用率。缺點：提高硬件成本，緊湊時花費CPU時間。49動態重定位VS靜態重定位靜態重定位:當用戶程序被裝入內存時，一次性實現邏輯地址到物理地址的轉換，以后不再轉換。動態重定位:在程序運行過程中要訪問數據時再進行地址變換。由地址變換機構進行的地址變換，硬件上需要重定位寄存器的支持。

動態重定位分區分配VS動態分區分配 相對而言，前者具有緊湊功能，需要重定位寄存器支持504.2.5對換(Swapping)1.對換的引入把內存中暫時不能運行的進程或暫時不用的程序和數據，換出到外存，而把已具備運行條件的進程或進程所需要的程序和數據，換入內存，使其投入運行(從而提高內存利用率)。如果對換以整個進程為單位，稱之為“整體對換”或“進程對換”。目的是為了解決內存緊張問題 如果對換以“頁”或“段”為單位，則稱之為“頁面對換”或“分段對換”。目的是為了支持虛擬存儲系統此小節僅介紹進程對換。為了進程對換，需三方面功能：對換空間的管理、進程的換出及換入。512.對換空間的管理把外存分為文件區和對換區文件區：用于存放文件；為了提高空間的利用率，對其采用離散分配方式。對換區：用于存放從內存換出的進程；因對換操作頻繁，為提高進程換入換出速度，對其采用連續分配方式。

(對換是在內存與外存的對換區之間進行）522.對換空間的管理為了對對換區中的空閑盤塊進行管理，在系統中應配置相應的數據結構，以記錄外存的使用情況。與內存在動態分區分配方式中所用的數據結構相似，同樣可以用空閑分區表或空閑分區鏈。對換空間的分配與回收，與動態分區分配方式中的內存分配與回收方法雷同。其分配算法可以是首次適應算法、循環首次適應算法或最佳適應算法。533.進程的換出和換入進程換出：選擇處于阻塞狀態且優先級最低的進程作為換出進程，將其程序和數據傳送到外存的對換區上，然后便可回收其所占用的內存空間，并對其PCB作相應修改。進程換入：查找處于“就緒”狀態但已換出的進程，將其中換出時間最久的進程作為換入進程，將其換入。544.2連續分配方式小結單一連續分配方式固定分區分配分區使用表動態分區分配首次適應算法循環首次適應算法最佳適應算法動態重定位分區分配“緊湊”動態重定位的實現（重定位寄存器）對換

554.3基本分頁存儲管理方式引入： 連續分配方式會形成許多“碎片”，雖然可通過“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出較大開銷。

?

如果允許將一個進程直接分散地分配到許多不相鄰接的分區中，就不必再進行“緊湊”。基于這一思想而產生了離散分配方式，相異于4.2所述連續分配方式。564.3基本分頁存儲管理方式分段存儲管理方式基本單位是段分頁存儲管理方式基本單位是頁基本的分頁存儲管理方式，要求把每個作業全部裝入內存后方能運行。（不具備頁面對換功能）4.3.1頁面和頁表4.3.2地址變換機構4.3.3兩級和多級頁表574.3.1頁面與頁表1.頁面1)頁面和物理塊頁面：將一個進程的邏輯地址空間分成若干個大小相等的片物理塊：內存物理空間分成與頁相同大小的若干個存儲塊分配內存時，可將進程中的若干頁(邏輯地址空間)分別裝入多個可以不相鄰接的塊(物理地址空間)中。 “頁內碎片”581.頁面2)頁面大小頁面大小應適中，且頁面大小應為2的冪，一般為512B~8KB。頁面太小，減少了內存碎片，有利于提高內存利用率；但也會導致頁面過多，頁表過長頁面太大，則會導致內存碎片較多592.分頁存儲的地址結構兩部分，前一部分為頁號P(220);后一部分為位移量W，即頁內地址(212)。從邏輯地址獲得頁號p和頁內偏移d p=INT(A/L) d=[A]MODL A——邏輯地址；L——頁大小602.地址結構613.頁表各頁離散存儲在任一物理塊，系統需記錄各頁面對應的物理塊。系統為每個進程建立一張頁面映射表，簡稱頁表。進程的所有頁，依次在頁表中有一頁表項，其中記錄了其對應的物理塊號。頁表的作用是實現從頁號到物理塊號的地址映射。查找頁表，即可找到每頁在內存中的物理塊號。62頁表的作用

實現從頁號到物理塊號的地址映射作業每頁1K內存每塊1K634.3.2地址變換機構功能：完成從邏輯地址（頁號+頁內地址）到物理地址的轉換。(頁與物理塊的大小完全一致，故)頁內地址和內存物理塊中的物理地址是一一對應的，無需再轉換頁號需轉換成內存中的物理塊號，這也是地址變換機構的實質需做的工作。借助于頁表完成。兩種實現方法基本的地址變換機構具有快表的地址變換機構641.基本的地址變換機構由于頁表項的總數很多，不可能均用寄存器來實現，頁表大多駐留在內存中。需設置一個頁表寄存器PTR（TableRegister），存放頁表在內存的始址和頁表的長度。進程未執行時，這兩個數據存于進程的PCB中；執行時，才將它們裝入PTR。651.基本的地址變換機構地址變換過程：1)分頁地址變換機構自動將有效地址分為頁號和頁內地址兩部分，再以頁號為索引去檢索頁表。2)在檢索頁表前，將頁號與頁表長度比較，如果越界則產生一越界中斷，本次訪問失敗3)如果未越界，則頁表始址+頁號*頁表項長度得到該頁號在頁表中的位置，從中可得到該頁的物理塊號，將之裝入物理地址的物理塊號部分。4)最后再將有效地址中的頁內地址送入物理地址寄存器的塊內地址中。66分頁系統的地址變換機構67分頁系統的地址變換實例邏輯地址為3BADH頁面大小為2KB頁表寄存器681.基本的地址變換機構一個問題？頁表是存放在內存中的，這使CPU每次要存取一個數據時，都要兩次訪問內存。第一次是訪問內存中的頁表，從中找到該頁的物理塊號，將此塊號與頁內偏移量W拼接以形成物理地址；第二次訪問內存時，才是從第一步所得地址中獲得所需數據(或向此地址中寫入數據)。將使計算機的處理速度降低近1/2。？692.具有快表的地址變換機構增設一個具有并行查尋能力的特殊高速緩沖寄存器，又稱為“聯想寄存器”(AssociativeMemory)或“快表”，用于存放當前訪問的那些頁表項。（意味著這些頁表項不在存放在內存中）702.具有快表的地址變換機構地址變換過程：在CPU給出有效地址后，由地址變換機構自動地將頁號P送入高速緩沖存儲器（快表），將此頁號與其中的頁號進行比較若有相匹配的頁號（在快表中），直接讀出其所對應的物理塊號，并送物理地址寄存器中。若沒有匹配的，還需訪問內存中的頁表。找到后，把對應的物理塊號送地址寄存器；也將此頁表項存入快表中。但如果快表已滿，則將一個老的且已被認為不再需要的頁表項換出。712.具有快表的地址變換機構722.具有快表的地址變換機構由于成本，快表不可能做的很大，一般只存放16~512個頁表項。但對于中小型作業來說，已有可能把全部頁表項放在快表中，但對于大型作業，則只能將其一部分頁表項放入其中。從快表中能找到所需頁表項的機率，可達90%以上。73練習

例：有一頁式系統，其頁表存放在主存中：①如果對主存的一次存取需要1.5μs,試問實現一次頁面訪問的存取時間是多少?②如果系統加有快表,平均命中率為85%,當頁表項在快表中時,其查找時間忽略為0,試問此時的存取時間是多少?74練習答：若頁表存放在主存中，則要實現一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據該地址存取頁面數據。■頁表在主存的存取訪問時間

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

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)75練習某存儲器的用戶編程空間共32個頁面，每頁為1KB，內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面對應的物理塊號如下表：頁號物理塊號051102437則邏輯地址0A5C（H）所對應的物理地址為：125C76練習0A5C＝0000,1010,0101,1100頁號為2，對應塊號為4，有：物理地址：0001，0010,0101,1100即：125C774.3.3兩級和多級頁表引入： 計算機支持的邏輯地址空間非常大(232~264)，每個進程的頁表項也非常龐大，需占據大量的連續內存空間，這顯然不現實。如何解決？

1.采用離散分配方式－－解決需大量連續內存空間問題

(將頁表再次進行分塊)

2.只將當前需要的部分頁表項調入內存－－使頁表需占用的內存減少781.兩級頁表將頁表進行分頁，并離散地將各個頁面分別存放在不同的物理塊中，同時為離散的頁表再建立一張頁表，稱為外層頁表，其每個表項記錄了頁表分頁的物理塊號。邏輯地址結構如下：791.兩級頁表頁內地址:12位，頁面大小為212，4KB外層頁內地址:10位，每個頁表分頁中最多可包含210個頁表項（對應210個物理塊）外層頁號:10位，最多允許210個頁表分頁80兩級頁表示意圖外層頁表的每個表項存放的是某頁表分頁的在內存中的物理塊號頁表(分頁)的每個表項存放的是某頁在內存中的物理塊號可利用兩級頁表，實現邏輯地址到物理地址的轉換這里只是物理塊號，并不是內存單元的編號比如外層頁號為1,外層頁內地址也為1,尋址81具有兩級頁表的地址變換外層頁表寄存器，用于存放外層頁表的始址d01.以邏輯地址中的外層頁號p1，作為外層頁表的索引，找到d0和p1對應的表項，從中可知指定頁表分頁的始址d1(物理塊號)；2.以外部頁內地址p2，作為指定頁內分頁的索引，找到d1和p2對應的表項，從中可知該頁在內存的物理塊號b3.物理塊號b與頁內地址d，即構成了要訪問的內存的物理地址。d0d182如何減少頁表所占的內存空間上述離散分配空間的辦法只解決了大頁表無需大片連續存儲空間的問題，并未減少頁表所占的內存空間。如何減少？只把當前需要的一些頁表項調入內存，以后再根據需要陸續調入其它的。在采用兩級頁表的情況下，需把外層頁表全部調入內存，對于頁表分頁只需調入需要使用的。 在外層頁表的表項中，需增設一個狀態位，表示相應的頁表分頁是否已調入內存。 （請求分頁存儲，虛擬存儲器中再作詳細介紹）832.多級頁表對于64位機器，若采用兩級頁表，頁內地址12位，外部頁內地址10位，這時外部頁號會達42位，每個表項占4個字節，就需要244B的連續內存空間。顯然無法接受。采用多級頁表，將外層頁表再進行分頁，將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系。844.3基本分頁存儲管理方式小結頁面、物理塊與頁表分頁地址結構：頁號＋頁內地址地址變換機構基本的地址變換機構具有快表的地址變換機構兩級和多級頁表854.4基本分段存儲管理方式存儲管理方式從固定分區到動態分區分配，進而到分頁存儲管理方式主要是為了提高內存的利用率。提出基本分段存儲管理方式主要是為了滿足用戶（程序員）在編程和使用上的多方面的要求。864.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式874.4.1分段存儲管理方式的引入為了滿足用戶和程序的如下需要：

1)方便編程 用戶通常將作業按邏輯關系劃分為若干段。希望要訪問的邏輯地址是由段名和段內偏移量決定。2)信息共享 實現共享是以信息的邏輯單位－段為基礎的。為實現段的共享，希望存儲管理能與用戶程序分段的組織方式相適應。884.4.1分段存儲管理方式的引入3)信息保護 對信息的邏輯單位－段進行保護4)動態增長 段在使用過程中可能會不斷增長，唯有分段存儲可較好解決該問題5)動態鏈接 動態鏈接在運行時，只將主程序對應的目標程序段裝入內存。在需調用某些段時才將其裝入，需要以段作為存儲管理的單位。894.4.2分段系統的基本原理1.分段2.段表3.地址變換機構901.分段作業的地址空間被劃分為若干個段，每個段用來定義一組邏輯信息，均從0開始編址，并采用一段連續的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。邏輯地址由段號和段內地址組成。912.段表進程的多個段被離散的放入內存不同位置。為了能將物理內存與邏輯段地址對應起來，需為每個進程建立一張段映射表。每個段在表中占有一個表項，記錄了該段在內存中的始址和段的長度。進程可通過查找段表，找到每個段對應的內存區，實現從邏輯段到物理內存區的映射。92利用段表實現地址映射933.地址變換機構段表寄存器存放段表始址和段表長度SL。94與分頁系統一樣，當段表放在內存中時，每訪問一個數據，都須訪問兩次內存。解決方法也類似，增設一個高速緩沖寄存器用于保存最近常用的段表項。954.分頁和分段的主要區別分頁是出于系統管理的需要，分段是出于用戶應用的需要一條指令或一個操作數可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處。頁大小是系統固定的，而段大小則通常不固定。邏輯地址表示：分頁是一維地址空間，各個模塊在鏈接時組織成同一個地址空間；只利用一個標記符即可表示一個地址。分段是二維地址空間，各個模塊在鏈接時可以每個段組織成一個地址空間；標識地址需給出段名和段內地址。通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。964.4.3信息共享分段系統的突出優點，易于實現段的共享，即允許若干個進程共享一個或多個分段。分頁系統也可實現程序和數據的共享，但不如分段系統來得方便。（舉例對比）可重入代碼：一種允許多個進程同時訪問（可被共享）的代碼；不允許任何進程對它進行修改。974.4.3信息共享例：多用戶系統，可同時接納40個用戶，每個用戶均可執行文本編輯程序。文本編輯程序有160KB代碼和40KB數據區，若代碼為非可重入的，需要8000KB內存空間支持40個用戶。如果160KB程序代碼為可重入的，則不論在分頁還是在分段系統中該代碼均可被共享，此時所需內存空間為160+40*40=1760KB。984.4.3信息共享分頁系統中：假定每個頁面大小為4KB，代碼需占用40個頁面，數據需占10頁面。每個用戶進程的頁表中均需建立相應的頁表項。如圖:99ed1ed2…ed40data1…data102122…6061…70…ed1ed2…ed40data1…data10data1…data10進程1進程2頁表頁表ed1ed2…ed40data1…data102122…6071…80主存分頁系統中共享editor，需建立比較復雜的頁表021226061707180100分段系統中共享editor示意editordata1editordata2段長基址1608040240段長基址1608040380editordata1…data2進程2進程1在分段系統中，實現共享只需在每個進程的段表中為文本編輯程序代碼段設置一個段表項，比分頁系統簡單的多。101略過：關于共享的進一步說明頁式地址是一維的，即每個邏輯地址是一個整數，由硬件將其分成：頁號|頁內位移,故頁號是唯一的，程序段的共享必須用相同頁號。如：

call2148—〉call2|100段式地址是二維的，兩個數字。各進程的段號未必一致，因此不同的進程可用不同的段號共享同一段。如：

callac1|100進程1：ac1=2；進程2：ac1=41024.4.4段頁式存儲管理方式分頁系統能有效地提高內存利用率，而分段系統則能很好地滿足用戶需要。？段頁式系統1031.基本原理將分段和分頁原理結合，先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。段頁式系統中，地址結構由段號、段內頁號及頁內地址三部分組成。頁104利用段表和頁表實現地址映射每個作業一張段表，每段一張頁表。先查段表，再查該段的頁表，才能找到物理塊號。再將其與頁內地址組合1052.地址變換過程1.利用段表始址d0和段號s來求出該段所對應的段表項在段表中的位置，從中得到該段的頁表始址d1；2.利用頁表始址d1和段內頁號P獲得對應頁的頁表項位置，從中讀出該頁所在的物理塊號P’；3.利用塊號P’和頁內地址d來構成物理地址。1062.地址變換過程1.利用段表始址和段號來求出該段所對應的段表項在段表中的位置，從中得到該段的頁表始址；2.利用頁表始址和段內頁號P獲得對應頁的頁表項位置，從中讀出該頁所在的物理塊號b；3.利用塊號b和頁內地址來構成物理地址。1072.地址變換過程段頁式系統中，訪問數據需三次訪問內存。 第一次訪問內存中的段表，取得頁表始址；第二次訪問內存的頁表，取得該頁的物理塊號，并與頁內地址一起組成實際的物理地址；第三次從物理地址中取出指令或數據。為了避免每次均需三次訪問，可在地址變換機構中增設一個高速緩沖寄存器，將常用的段表和頁表存儲在高速緩沖中。1084.4基本分段存儲管理方式小結分段存儲管理方式的引入方便用戶分段系統的基本原理分段系統的地址變換過程段表始址+段號->段的基址與段內地址結合->物理地址信息共享分頁系統與分段系統的比較段頁式存儲管理方式段表始址+段號->頁表始址與頁號結合->頁面對應的物理塊號與頁內地址結合->物理地址1094.5虛擬存儲器的基本概念連續分配方式、基本分頁、基本分段存儲管理方式均需將一個作業全部裝入內存后方能運行，這將導致大作業無法運行。解決方法：物理上增加內存容量有一定限制從邏輯上擴充內存容量此即虛擬存儲器所要解決的主要問題1104.5虛擬存儲器的基本概念4.5.1虛擬存儲器的引入4.5.2虛擬存儲器的實現方法4.5.3虛擬存儲器的特征1114.5.1虛擬存儲器的引入1.常規存儲器管理方式的特征一次性：作業運行前需一次性全部裝入內存這可能導致大作業無法裝入并非全部程序和數據都需用到，一次裝入，浪費內存駐留性：一旦裝入便一直駐留內存直至作業結束不再運行的程序模塊仍將占用寶貴的內存資源一次性及駐留性是否是必需的？1124.5.1虛擬存儲器的引入2.局部性原理程序執行時的特點：程序執行時，除少部分轉移和過程調用指令外，大多仍是順序執行的。過程調用雖可導致程序由一區域轉至另一區域，但調用深度大多不超過5。程序在一段時間內都局部于這些過程的范圍內執行。程序中存在循環結構，它們將多次執行程序中對數據結構的處理，往往局限于較小的范圍內1134.5.1虛擬存儲器的引入2.局部性原理局部性的表現：空間局限性。一段時間內所訪問的地址可能集中于一定的范圍之內。（程序的順序執行）時間局限性。某條指令或數據可能被再次執行或訪問。（循環操作）根據局部性原理，程序在運行之前沒有必要一次性全部裝入，也沒必要長期駐留內存。1144.5.1虛擬存儲器的引入引入虛擬存儲器基于局部性原理，程序可僅將需運行的部分頁或段裝入內存便可開始執行。執行中，如果訪問的頁段已調入內存便可繼續；否則，應利用OS提供的請求調頁(段)功能將它們調入內存。若此時內存已滿，應利用頁(段)置換功能，將暫時不用的調出，騰出地方調入需要的頁(段)。這樣，便可使一個大的程序在較小的空間中運行;也可使內存中同時裝入更多的進程并發執行。1154.5.1虛擬存儲器的引入3.虛擬存儲器定義具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲系統。實質：以時間換空間，但時間犧牲不大。虛擬大小由內存容量和外存容量之和決定。1164.5.2虛擬存儲器的實現方法虛擬存儲器是建立在離散分配的存儲管理方式基礎上的。為什么？虛擬存儲器請求調入頁面轉換若采用連續分配方式，一次性將全部數據調入，無需虛擬存儲。實現的兩種方式:請求分頁請求分段1171.分頁請求系統在分頁系統的基礎上，增加了請求調頁功能和頁面置換功能。只裝入部分頁面即可運行，可通過調頁和頁面置換功能，調入需要的頁面，同時將暫不需要的換出。以頁為單位置換需硬件：請求分頁的頁表機制缺頁中斷機構地址變換機構需軟件：實現請求調頁的軟件實現頁面置換的軟件1182.請求分段系統在分段系統的基礎上，增加了請求調段及分段置換功能。只裝入部分段即可運行，可通過調段和段置換功能，調入需要的段，同時將暫不需要的調出。以段為單位置換需硬件：請求分段的段表結構缺段中斷機構地址變換機構需軟件：請求調段和置換軟件1194.5.3虛擬存儲器的特征1.離散性：離散分配內存2.多次性：多次裝入3.對換性：允許作業運行中進行換進換出4.虛擬性：從邏輯上擴充內存虛擬性以多次性和對換性為基礎，而多次性和對換性又必須建立在離散分配的基礎上。最本質的特征是離散性，在此基礎上又形成了多次性和對換性，所表現出來的最重要的特征是

虛擬性.1204.5虛擬存儲器小結虛擬存儲器的引入大作業小內存運行局部性原理 具有請求調入功能和置換功能，能從邏輯上擴充內存虛擬存儲器的實現方法分頁請求系統 請求分段系統虛擬存儲器的特征離散性 多次性 對換性 虛擬性1214.6請求分頁存儲管理方式建立在基本分頁基礎上，為了支持虛擬存儲器功能，而增加了請求調頁功能和頁面置換功能。每次調入和換出的基本單位是固定長度的頁。1224.6請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內存分配策略和分配算法4.6.3調頁策略1234.6.1請求分頁中的硬件支持1.頁表機制由于應用程序只是一部分調入內存即只有部分頁位于內存中，須在頁表中增加若干項，供程序（數據）換進換出時參考。頁號物理塊號狀態位P訪問字段A修改位M外存地址P:是否已調入內存A:一段時間內使用的次數或多久未使用M:調入內存后是否修改過1244.6.1請求分頁中的硬件支持2.缺頁中斷機構當訪問的頁不在內存中時便產生缺頁中斷，請求OS將其調入。缺頁中斷具有一般中斷的入棧、轉中斷處理、出棧等過程，但又其特殊性：在指令執行期間產生和處理中斷。發現訪問的頁不在內存即產生；通常是在等到指令執行完畢后。一條指令在執行期間，可能要產生多次中斷。（如圖）125涉及6次缺頁中斷的指令頁面6543211264.6.1請求分頁中的硬件支持3.地址變換機構大致步驟：1)在地址變換時，首先檢索快表，試圖從中找到要訪問的頁。如找到，修改其訪問位；對于“寫”指令，還要設置修改位的值。如未找到，則轉3。2)利用頁表項中的物理塊號和頁內地址，形成物理地址，結束。3)查找頁表，找到頁表項后，判斷其狀態位P，查看該頁是否在內存中。如果在，則將該頁寫入快表（若快表已滿，則應該先調出某個或某些頁表項）。如果不在，則產生缺頁中斷，由OS從外存將該頁調入內存。返回1。參圖4-241271284.6.2內存分配策略和分配算法三個問題最小物理塊數的確定物理塊的分配策略物理塊的分配算法1291.最小物理塊數的確定最小物理塊數是指保證進程正常運行所需的最少物理塊數。與計算機的硬件機構有關，取決于指令的格式、功能和尋址方式。單地址指令且采用直接尋址方式，最少物理塊數為2(指令頁面數據頁面)單地址指令且采用間接尋址方式，3多字節指令，6（幻燈片125頁）1302.物理塊的分配策略1)固定分配局部置換2)可變分配全局置換3)可變分配局部置換1312.物理塊的分配策略1)固定分配局部置換每個進程分配固定數目的物理塊數，在整個運行期間都不改變如果缺頁，則只能從該進程在內存的頁面中選中一頁，進行換出操作，然后再調入一頁。特點：為每個進程分配多少頁是合適的值難以確定。此外，在對換時會浪費比較多的時間。1322.物理塊的分配策略2)可變分配全局置換每個進程預先分配一定數目的物理塊，同時OS也保持一個空閑物理塊隊列。（進程的塊數運行時可能會有變化）當缺頁時，首先將對OS所占有的空閑塊進行分配，從而增加各進程的物理塊數。當OS的空閑塊全部用完，將引起換出操作。（換出的頁可能是任一進程的中的一頁）1332.物理塊的分配策略3)可變分配局部置換思路：先為進程分配部分物理塊運行；系統根據缺頁率動態調整各進程占有的物理塊數目，使其保持在一個比較低的缺頁率狀態下（輕微缺頁時，僅允許從進程自身的頁面中選一頁換出再換入需要的；只有頻繁缺頁時，系統才為其分配附加的物理塊）。特點：使大部分進程可以達到比較近似的性能。1343.物理塊的分配算法

－－針對固定分配策略平均分配算法將物理塊平均分配給各進程未考慮進程本身的大小（頁數有多有少）按比例分配算法根據進程大小按比例分配物理塊

m為物理塊總數,S代表各進程頁數之和

b取整，且應大于最小物理塊數考慮優先權的分配算法物理塊分為兩部分：一部分按比例分配；一部分根據各進程優先權分配1354.6.3調頁策略1.何時調入頁面2.從何處調入頁面3.頁面調入過程1361.何時調入頁面根據將進程運行時所缺頁面調入內存的時機預調頁策略將那些預計在不久之后便會被訪問的頁面預先調入內存預測成功率僅約50%請求調頁策略在運行中，發現要訪問的頁面不在內存中，便提出請求，由OS將其調入每次僅能調入一頁，增加了磁盤的啟動頻率，系統開銷較大1372.從何處調入頁面請求分頁系統中外存分兩個部分：文件區和對換區。一般應當盡量使用對換區來調入頁面。對于不同情況，采用不同的策略：系統有足夠的對換空間全部由對換區調入，事先需將有數據從文件區拷貝到對換區系統對換空間不足凡是不會被修改的文件都直接從文件區調入，換出時不必再改動文件區；對于需修改的部分，換出時便調到對換區，需要時再從對換區調入。UNIX的調入方式未運行過的頁面均從文件區調入；對于曾經運行過但又被換出的頁面放在對換區，以后從對換區調入。1383.頁面調入過程

進程需要的頁面不在內存，引起缺頁中斷 中斷處理程序保留現場環境，轉入缺頁中斷處理程序

中斷處理程序如何調入頁面？

1.中斷處理程序查找頁表，得到對應的外存物理塊號。如果內存有空閑，則啟動磁盤操作，將所缺的頁面讀入，并修改頁表。否則，即內存無空閑時，轉2。

2.執行置換算法，選出要換出的頁面（如果該頁修改過，應將其寫入磁盤）然后將所缺頁調入內存，修改相應表項，將其狀態位設為"1"，并放入快表。

3.利用修改后的頁表，形成物理地址，訪問內存數據。1394.6請求分頁存儲管理方式小結請求分頁中的硬件支持頁表機制 缺頁中斷機構 地址變換機構內存分配策略和分配算法最小物理塊的確定物理塊的分配策略固定分配局部置換可變分配全局置換可變分配局部置換物理塊分配算法平均分配按比例分配考慮優先權的分配調頁策略何時調入（預調、請求）從何處調入（對換區）頁面調入過程（內存是否有空閑）1404.7頁面置換算法請求分頁存儲管理方式，若訪問的頁面不在內存，且內存已無空閑空間時，需首先從內存中調出一頁程序或數據，然后調入。需根據一定的算法來確定將哪個頁面調出，此算法即頁面置換算法，用來選擇需調出的頁面。理論目標：減少對換量，具有較低的頁面更換頻率。應優先將那些以后不再訪問或較長時間內不再訪問的頁面調出。1414.7頁面置換算法4.7.1最佳置換算法和先進先出置換算法4.7.2最近最久未使用(LRU)置換算法4.7.3Clock置換算法4.7.4其它置換算法 具體7種1424.7.1最佳置換算法和先進先出

置換算法1.最佳置換算法 理論上的算法，其所選擇的被淘汰頁將是以后永不使用，或者是最長時間內不再被訪問的頁。 無法預知頁面被訪問的次序，無法實現，但可用來評價其它算法。1431.最佳置換算法每次選擇最長時間內不再訪問的頁面調出內存“向后看”缺頁次數為6，缺頁率6/12＝50%1442.先進先出(FIFO)頁面置換算法最早出現的置換算法總是淘汰最先進入內存的頁面實現簡單，只需把一個進程已調入內存的頁面，按先后次序鏈接成一個隊列，并設置一個替換指針（總是指向最老的頁面）該算法不能保證經常使用的頁面不被淘汰，會導致缺頁率較高。1452.先進先出(FIFO)頁面置換算法每次選擇最早進入的頁面調出內存缺頁次數為9，缺頁率9/12＝75%1464.7.2最近最久未使用(LRU)

置換算法1.算法描述LeastRecentlyUsed根據頁面調入內存后的使用情況進行決策，利用“最近的過去”作為“最近的將來”的近似，選擇最近最久未使用的頁面予以淘汰。為每個頁面設置一個訪問字段，記錄一個頁面自上次被訪問以來所經歷的時間t。1471.LRU算法描述每次選擇最近最久未使用的頁面調出內存“向前看”缺頁次數為7，缺頁率7/12＝58.3%1482.LRU置換算法的硬件支持LRU算法為了記錄哪一頁是最近最久未使用的頁面，需要以下兩類硬件之一支持寄存器棧1491)寄存器為每個在內存中的頁面配置一個n位移位寄存器，R=Rn-1Rn-2Rn-3…R2R1R0定時將所有寄存器右移一位（其值將會減小）；當進程訪問某頁時，便將該頁相應寄存器的最高位Rn-1置1（其值將會增大）。最久未訪問的頁面對應的寄存器的值肯定最小，據此可找到要淘汰的頁面。1501)寄存器1512)棧利用一個特殊的棧來記錄頁面的使用次序當進程訪問某頁時，將其從棧中移出壓入“棧頂”；換出時，將“棧底”換出。這樣可以保證：棧頂總是最新被訪問頁面的頁號，而棧底則是最近最久未使用頁面的頁號。1522)棧進程訪問頁面的序列為：

4,7,0,7,1,0,1,2,1,2,6棧的變化情況訪問6時缺頁將棧底換出1534.7.3Clock置換算法LRU算法較好，但硬件要求較高，在實際應用中多采用其近似算法，Clock算法是其中一種。1.簡單的Clock置換算法2.改進型Clock置換算法1541.簡單的Clock置換算法內存中所有頁面通過鏈接指針形成一個循環隊列每頁有一個使用訪問位(usebit)，若該頁被訪問則置其usebit=1。缺頁置換時采用一個指針，從當前指針位置開始按地址依次檢查各頁：尋找usebit=0的頁面作為被置換頁指針經過的userbit=1的頁都修改userbit=0,暫不換出最后指針停留在被置換頁的下一個頁。1551.簡單的Clock置換算法1562.改進型Clock置換算法該算法中，除考慮頁面的最近使用情況外，還須再增加一個因素－－置換代價。在頁面換出時，如果該頁修改過，便須將它重新寫回磁盤，相對于未修改過的頁面，其置換代價就高。1572.改進型Clock置換算法選擇頁面時，盡量選擇既未使用又沒有修改的頁面。頁面（訪問位A，修改位M）有四種不同情形：1類(A=0,M=0）既未訪問，又沒有修改，最佳淘汰頁2類(A=0,M=1）最近未訪問，但已被修改，效率低的淘汰頁3類(A=1,M=0）被訪問，但沒有修改，可能再次被訪問4類(A=1,M=1）既被訪問，又有修改 淘汰頁優先選擇前兩類，實在沒有才考慮后兩類1582.改進型Clock置換算法執行過程：（1）指針從當前位置開始，開始第一輪掃描循環隊列，尋找未訪問且沒有修改過的頁面（第1類頁面），找到則可換出。（2）如果找不到，則開始第二輪掃描，尋找未訪問但修改過的頁面（第2類頁面），并且每經過一個頁面時，將其訪問位A設置為0（未訪問）。如果找到一個第2類頁面，則可換出。（3）如果仍舊未找到合適的換出頁面，則此時指針回到初始位置，且所有頁面其訪問位A置為0。再轉回（1）繼續工作，這時肯定可以經由前兩步找到換出頁面。可有效減少磁盤I/O操作，但算法本身開銷有所增大1594.7.4其它置換算法1.最少使用(LFU:LeastFrequentlyUsed)置換算法2.頁面緩沖算法(PBA:PageBufferingAlgorithm)1601.最少使用置換算法LFU目的：選擇到當前時間為止被訪問次數最少的頁面被置換；實現方法1：每頁設置訪問計數器，每當頁面被訪問時，該頁面的訪問計數器加1；發生缺頁中斷時，淘汰計數值最小的頁面；因頁面訪問次數可能極多，要求計數器容量極大，此法不可行。實現方法2：類似于LRU算法，每個頁面設立n位移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補0，這樣，在最近一段時間內時用最少的頁面將是ΣRi最小的頁。1612.頁面緩沖算法PBA對FIFO算法的發展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面；被置換頁面的選擇和處理：由操作系統中專門的頁面置換進程，用FIFO算法選擇被置換頁，把被置換的頁面放入內存中的兩個鏈表（空閑頁面鏈表和已修改頁面鏈表）之一：如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾否則將其歸入到已修改頁面鏈表。1622.頁面緩沖算法這種算法被換出的頁面，鏈接在空閑頁面鏈表和已修改頁面鏈表中，仍留在內存中。當進程再訪問時，只需花