2022/11/19第四章存儲器管理第四章

存儲器管理4.1存儲器的層次結構4.2程序的裝入和鏈接 4.3連續分配方式4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式今天雖然主存價格已相當便宜，但主存容量仍然是計算機四大硬件資源中最關鍵的資源。因此對主存的管理和有效使用仍然是今天操作系統十分重要的內容。許多操作系統之間最明顯的區別特征之一往往是所使用的存儲管理方法不同。第四章

存儲器管理存儲管理功能存儲分配回收存儲共享存儲保護存儲擴充地址映射分配回收對象內存、外存(相同方法)分配回收時刻進程創建、撤銷、交換、長度變化目的：節省內存、相互通信內容：代碼、數據防止地址越界防止操作越權內存、外存結合，虛擬存儲體系速度接近內存，容量相當外存邏輯地址=>物理地址硬件支持基址寄存器(base)、限長寄存器(limit)、快表；4.1存儲器的層次結構4.1.1多級存儲器結構對于通用計算機而言，存儲層次至少應具有三級：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計算機中，還可以根據具體的功能分工細劃為寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質等。存儲空間的分類與性質4.1.1多級存儲器結構4.1.2主存儲器與寄存器1.主存儲器寄存器訪問速度最快，完全能與CPU協調工作，但價格卻十分昂貴，因此容量不可能做得很大。寄存器用于加速存儲器的訪問速度。用于保存進程運行時的程序和數據，也稱可執行存儲器。CPU的控制部件只能從主存儲器中取得指令和數據。2.寄存器4.1.3高速緩存和磁盤緩存1．高速緩存容量大于或遠大于寄存器，而比內存約小兩到三個數量級左右。將主存中一些經常訪問的信息存放在高速緩存中,可大幅度提高程序執行速度。2．磁盤緩存磁盤的I/O速度遠低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數據和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數。4.2程序的裝入和鏈接用戶源程序變為一個可在內存中執行的程序.3.裝入由裝入程序將裝入模塊裝入內存。1.編譯由編譯程序源代碼編譯成若干個目標模塊2.鏈接由鏈接程序將目標模塊和它們所需要的庫函數鏈接在一起，形成一個完整的裝入模塊4.2程序的裝入和鏈接……鏈接程序裝入模塊裝入程序第一步第二步第三步編譯程序產生的目標模塊庫地址空間程序的名空間用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址）。由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）。內存的每個存儲單元都有一個編號，這種編號稱為內存地址（或稱為物理地址，絕對地址）。內存地址的集合稱為內存空間（或物理地址空間）。地址映射LoadA2003456

。。物理地址空間LoadAdata1data13456名空間LoadA2003456編譯連接邏輯地址空間

源程序經過匯編或編譯后，形成目標程序，每個目標程序都是以0為基址順序進行編址的，原來用符號名訪問的單元用具體的數據——單元號取代。這樣生成的目標程序占據一定的地址空間，稱為作業的邏輯地址空間，簡稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問的操作數地址統稱為邏輯地址。地址空間地址映射LoadA2003456

。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=1000

把內存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內存地址（物理地址、絕對地址、實地址），存儲單元占8位，稱作字節（byte）。物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。4.2.1程序的裝入將一個模塊裝入內存時，可采用三種方式：絕對裝入方式重定位裝入方式

動態運行時裝入方式

在多道程序環境下，要使程序運行，必須為之先建立進程。創建進程的第一件事是將程序和數據裝入內存。如果在編譯時知道程序駐留在主存的具體位置,則編譯程序將產生物理地址的目標代碼.模塊裝入后,由于程序中的邏輯地址與實際主存的地址完全相同,故不需要對程序和數據的地址進行修改.1絕對裝入方式絕對裝入方式只能將目標模塊裝入到主存事先指定的固定位置,只適用于單道程序環境.MoveAX,[2500]543212000210025003000絕對裝入方式編譯時產生的絕對地址MoveAX,[2500]5432120002100250030000內存空間FFFF重定位（Relocation）★重定位：在一般情況下，一個作業在裝入時分配到的存儲空間和它的地址空間是不一致的。由于不一致所引起的對有關地址部分的調整過程，就是我們所說的地址重定位。靜態重定位動態重定位在多道程序環境下，目標模塊的起始地址通常從0開始，程序中的其他地址都是相對于起始地址計算的。因此應采用可重定位裝入方式，根據內存的當前情況，將裝入模塊裝入到內存的適當位置。靜態重定位:是在裝入時由裝配程序一次性完成的，以后不再改變.物理地址=邏輯地址+程序在內存的首地址優點：無需硬件支持，容易實現。缺點：

1.程序經地址重定位后不能再移動了；

2.程序在內存空間只能連續存儲；2可重定位裝入方式LoadBX,032543210832124LoadBX,13254321100108132244內存空間FFFF裝入程序靜態重定位邏輯地址空間3．動態運行時裝入方式程序執行過程中，當訪問指令或數據時，才進行的地址變換方法，稱為動態重定位。靠硬件地址變換機構實現的。基地址寄存器和一個地址轉換線路組成物理地址=邏輯地址+基址寄存器優點：可對內存進行非連續分配；提供了實現虛存的基礎；有利于程序段的共享。LoadBX,032543210832124

LoadBX,03254321100108132244內存空間FFFF裝入程序作業的裝入CPU+邏輯地址032100基地址寄存器物理地址LoadBX,03254321100108132244內存空間FFFF地址轉換動態重定位1324.2.2程序的鏈接根據鏈接時間的不同，可把鏈接分成如下三種：(1)靜態鏈接。(2)裝入時動態鏈接。(3)運行時動態鏈接。1靜態鏈接方式在程序運行之前，先將各個目標模塊及他們所需的庫函數，鏈接成一個完整的裝入模塊，運行時直接裝入內存。這種事先進行鏈接，以后不再拆開的鏈接方式稱之靜態鏈接。需要解決兩個問題此時必須修改被調用模塊的邏輯地址。同時轉變模塊中使用的外部調用符號。模塊ACALLB;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標模塊模塊AJSRL;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊2.裝入時動態鏈接將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。優點:(1)便于修改和更新(2)便于對目標模塊的共享3.運行時動態鏈接指某些目標模塊，當在程序執行中需要該模塊時，才對它進行的鏈接。在執行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅加快了程序的裝入過程，而且可節省大量的內存空間。4.3連續分配方式把主存中的用戶區作為一個連續區域或者分成若干個連續區域進行管理。可分為：單道連續分配固定分區分配動態分區分配動態重定位分區分配4.3.1單一連續分配內存分為系統區和用戶區；操作系統占用系統區,其余的主存空間分配給一個用戶程序使用。特點：管理簡單，主存利用率低，不支持多道，程序的運行受主存容量限制。在任何時刻主存中最多只存有一個作業。4.3.2固定分區分配將內存劃分成若干個連續區域，稱為分區。每個分區的大小可以相同也可以不同，每個分區只能存儲一個程序。(1)分區大小相等。即使所有的內存分區大小相等。其缺點是缺乏靈活性。(2)分區大小不等。把內存區劃分成含有多個較小的分區、適量的中等分區及少量的大分區。2．內存分配數據結構：分區使用表為了便于內存分配，通常將分區按大小進行排隊，并為之建立一張分區使用表，其中各表項包括每個分區的分區號、起始地址、大小及狀態(是否已分配)。區號大小(KB)起址(KB)狀態18K20K已分配232K28K已分配364K60K已分配4132K124K未分配OS20K28K60K124K256K進程A（6K）（a）分區說明表 （b）存儲空間分配情況圖固定分區使用表進程B（25K）進程C（36K）2．內存分配固定分區分配算法流程圖要求xk大小的分區取分區說明表的第一項該分區空閑嗎？分區大小xk表結束嗎？返回分區號狀態位置1無法分配取下一項NNNYYY固定分區分配存儲保護：兩種方法提供上、下界寄存器和地址檢查機構。基址寄存器、長度寄存器和動態地址轉換機構。固定分區分配優點：易于實現，開銷小。可放多道程序缺點：存在零頭（即存在碎片）。分區總數固定，限制了并發執行的程序數目。4.3.3動態分區分配工作原理存儲空間的劃分是在裝入作業時進行的，根據作業的需求和內存空間的使用情況來決定是否分配。且使分區大小正好適應作業的需要。數據結構空閑分區表：序號，大小，起址，狀態空閑分區鏈：在每個分區中附上一個表格信息，狀態（0，1），大小，指針（空白分區才有）1．分區分配中的數據結構圖空閑鏈結構前向指針N個字節可用后向指針N+2N+20（分配標識）00K15K38K48K68K80K110K120K空閑區表已分配區表始址長度標志15K23K未分配48K20K未分配80K30K未分配空空始址長度標志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分區分配表：圖分區分配表0K15K38K48K68K80K110K120K空閑區表已分配區表始址長度標志15K23K未分配48K20K未分配98K12K未分配空空始址長度標志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K

2．分區分配算法常用的分區分配算法有以下幾種：首次適應算法循環首次適應算法最佳適應算法最壞適應算法快速適應算法4.分配算法1)首次適應算法算法思想按分區先后次序，從頭查找，找到符合要求的第一個分區。盡可能利用存儲區低地址空閑區，盡量在高地址部分保存較大空閑區，以便一旦有分配大空閑區要求時，容易得到滿足。算法實質1）首次適應算法1）首次適應算法

切割空閑區有兩種方法：從空閑區頭開始從空閑區尾開始空閑區大小50KB，首址156KB，申請34KB。從該空閑區中截取所需大小，修改調整可用表從空閑區表第一表目順序查找從可用表中移去該表目，調整可用表取下一表項無法分配該空閑區長度≥SIZE？該空閑區長度=SIZE？表目查完？返回分配起始地址否否否是是是首次適應算法1）首次適應算法指針10k60k90k20k有四塊空閑區(從低地址高地址)，來了一個作業需分配19k內存。例：1）首次適應算法指針10k60k90k20k41k在高地址空閑區中保持較大空閑區(每次從10k開始分配尋找)。1）首次適應算法優點分配簡單，合并相鄰空閑區也比較容易缺點查找總是從表首開始，前面空閑區往往被分割的很小時，滿足分配要求的可能性較小，查找次數較多。針對這個問題，對最先適應法稍加改進，就有了循環最先適應法。2)循環首次適應算法(nextfit)算法的分配和釋放的時間性能較好，使空閑分區分布得更均勻，但較大的空閑分區不易保留。算法思想算法特點按分區先后次序，從上次分配的分區起查找(到最后分區時再回到開頭)，找到符合要求的第一個分區。12指針移動2)循環首次適應算法(nextfit)3)最佳適應算法算法思想

空閑存儲區管理表采用從小到大的順序結構在所有大于或者等于要求分配長度的空閑區中挑選一個最小的分區，即對該分區所要求分配的大小來說，是最合適的。分配后，所剩余的塊會最小。算法實現3)最佳適應算法3)最佳適應算法優點

這種算法最大的缺點是分割后的空閑區將會很小，直至無法使用，而造成浪費。缺點

較大的空閑分區可以被保留示例指針10k20k60k90k來一個19k的作業指針10k20k60k90k1k4)最壞適應算法算法思想

空閑區按由大到小排序分配時選取所有空閑區中最大的一塊，把剩余的塊再變成一個新的空閑區。其依據是當一個很大的空閑區被切割了一部分后可能仍是一個較大的空閑區。避免了空閑區越分越小的問題。算法實現4)最壞適應算法示例指針90k60k20k10k71k指針90k60k20k10k來一個19k的作業4)最壞適應算法優點分配時，產生的空白區可供以后使用。只需查找一次，就可成功，分配算法很快。缺點最后剩余分區會越來越小，無法運行大程序5）快速適應算法算法思想

對于每一類具有相同容量的所有空閑分區，設立一個空閑分區鏈表。再設立一張管理索引表，該表的每一個表項對應了一個空閑分區鏈表。

是將空閑分區根據其容量大小進行分類，在進行內存分配的時候，不需要對分區進行切割。算法實現5）快速適應算法該算法的優點：查找效率高。不會對任何分區分割，能保留大的分區。也不會產生內存碎片。該算法的缺點：在分區歸還主存時算法復雜，系統開銷較大。一個分區只屬于一個進程，存在空間浪費。3．分區分配操作1)分配內存設請求的分區大小為u.size，表中每個空閑分區的大小表示為m.size，若m.size-u.sizesize(規定的不再切割的分區大小)，將整個分區分配給請求者，否則從分區中按請求的大小劃出一塊內存空間分配出去，余下部分留在空閑鏈中，將分配區首址返回給調用者。從頭開始查表檢索完否？m.Size>u.size?m.size-u.size<=size?從該分區中劃出u.size大小的分區將該分區分配給請求者修改有關數據結構返回返回繼續檢索下一個表項將該分區從鏈中移出YNNYYN

2)回收內存當進程運行完畢釋放內存時,可能出現以下四種情況之一：(1)回收區與前一個空閑分區相鄰。(2)回收分區與后一空閑分區相鄰。(3)回收區同時與前、后兩個分區鄰。(4)回收區前后都不鄰空閑區。圖內存回收時的情況4.3.4伙伴系統固定分區和動態分區方式都有不足之處。伙伴系統方式是對以上兩種內存方式的一種折衷方案。伙伴系統規定，無論已分配分區或空閑分區，其大小均為2的k次冪，k為整數，l≤k≤m，其中：21表示分配的最小分區的大小，2m表示分配的最大分區的大小，通常2m是整個可分配內存的大小。當把一個存儲塊分為大小相等的兩半時，則它們互為伙伴。[大小為2k的伙伴的首地址之間的關系](0)0000(8)100000000100100011002323222222222121000000104.3.4伙伴系統標志位：

tag=1占用塊

0空閑塊202k2m0km0k0knodesizefirst按k值索引，相同k值的塊構成子表(雙鏈表)4.3.4伙伴系統

分配算法1)計算k值：k=log2n2)從子表k開始找可用的塊

2.1)k子表有，取出分配，結束；

2.2)否則，若從k向下找到i(i>k)子表有可用塊

(起始地址為p)，則取出2k分配，剩余的塊大小2i-12i-2......2k

起始地址p+2i-1p+2i-2......p+2k

插入相應的子表。p2i分配2k2i-12i-2回收時，只有伙伴才合并，并將合并后的新空閑塊加入上一級大小的空閑塊鏈表中。4.3.5哈希算法哈希算法就是利用哈希快速查找的優點，以及空閑分區在可利用空間表中的分布規律，建立哈希函數，構造一張以空閑分區大小為關鍵字的哈希表。當進行空閑分區分配時，根據所需空閑分區大小，通過哈希函數計算，即得到在哈希表中的位置。4.3.5哈希算法算法思想

構造一張以空閑分區大小為關鍵字的哈希表。根據所需空閑分區大小，通過哈希函數計算，即得到在哈希表中的位置。利用哈希快速查找的優點，以及空閑分區在可利用空間表中的分布規律，建立哈希函數，實現快速查找定位分區。算法實現

優點：便于動態申請內存便于共享內存便于動態鏈接缺點：碎片問題(外碎片)，內存利用率不高，受實際內存容量限制分區式存儲管理的優缺點

碎片問題經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片造成存儲資源的浪費碎片問題解決的方法：(I)將程序裝入分散存儲區中–––多重分區(II)將碎片集中(緊湊或拼接)–––動態重定位分區分配問題：開銷大；移動時機4.3.6可重定位分區分配1．動態重定位的引入在連續分配方式中，必須把一個系統或用戶程序裝入一連續的內存空間。緊湊技術：通過在內存移動程序，將所有小的空閑區域合并為大的空閑區域（緊縮技術，緊致技術，浮動技術，搬家技術）如果在系統中只有若干個小的分區，它們容量的總和大于要裝入的程序，怎么辦？1．動態重定位的引入緊湊2．動態重定位的實現

作業裝入內存后的所有地址都仍然是相對地址。將相對地址轉換為物理地址的工作，被推遲到程序指令要真正執行時進行。當系統對內存進行了“緊湊”而使若干程序從內存的某處移至另一處時，只要用該程序在內存的新起始地址，去置換原來的起始地址即可。2．動態重定位的實現load1,2500365load1,25003650100250050002500100001000010100+1250015000作業J處理機一側存儲器一側重定位寄存器相對地址3.動態重定位分區分配算法動態重定位分區的優缺點優點:解決了可變分區分配所引入的“外零頭”問題。消除內存碎片，提高內存利用率。缺點:提高硬件成本，緊湊時花費ＣＰＵ時間。1．對換(Swapping)的引入4.3.7對換對換：不能運行的進程調出到外存，程序、數據。具備運行條件的進程調入內存，程序和數據。對換是提高內存利用率的有效措施。1．對換實現：通過中級調度。分類：進程對換：以整個進程為單位；頁/段對換：虛存管理技術；為了實現進程對換，系統必須能實現三方面的功能：對換空間的管理、進程的換出，以及進程的換入。對2、對換空間管理外存：是提高進程換入和換出的速度。為此，采取的是連續分配方式。分為文件區和對換區。對對換空間管理的主要目標：3．進程的換出與換入(1)進程的換出系統應定時地查看所有進程的狀態，從中找出“就緒”狀態但已換出的進程，將其中換出時間最久的進程作為換入進程，將之換入。每當一進程由于創建子進程而需要更多的內存空間，但又無足夠的內存空間等情況發生時，系統應將某進程換出。(2)進程的換入3．進程的換出與換入(1)進程的換出(2)進程的換入4.4基本分頁存儲管理方式造成這樣問題的主要原因是用戶程序裝入內存時是整體裝入的，為解決這個問題，提出了分頁存儲管理技術。分區存儲管理的主要問題是碎片問題。4.4.1頁面與頁表--頁面1)頁面和物理塊在分頁系統中的頁面其大小應適中。頁面大小應是2的冪，通常為512B～8KB。頁框(塊f)：把主存空間劃分成與頁相同的片。

頁面(頁P)：把每個作業(進程)虛擬(邏輯)地址空間劃分成若干大小相等的片.2)頁面大小2．地址結構用戶程序中的邏輯地址包括頁號和頁內地址（頁內位移）

區分頁號和頁內地址的依椐是頁的大小，頁內地址占邏輯地址的低位部分，頁號占邏輯地址的高位部分。分頁地址中的地址結構如下：2．地址結構分頁地址中的地址結構確定了主存儲器的分頁大小,也決定了頁面大小.

頁號P頁內地址(偏移量)31 1211 0若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P和頁內地址d可按下式求得：

P=INT[A/L]d=[A]MODL例如：假定頁面大小1024字節，虛地址共占用2個字節(16位)

頁號頁內地址（位移量）

PW1510902．地址結構2．地址結構3．頁表頁號塊號021326為了能在內存中找到每個頁面所對應的物理塊，系統為每個進程建立了一張頁面映象表，即頁表頁表的作用是實現從頁號到物理塊號的地址映射頁表由頁號和塊號組成，指出邏輯地址中頁號與主存中物理塊號的對應關系3.頁表0頁1頁2頁3頁4頁5頁n頁021326384950123456789用戶程序頁表頁號塊號內存頁表位于內存4.4.2地址變換機構通過硬件的地址轉換機構實現從邏輯地址到物理地址的轉換工作。地址轉換機構的任務實際上是將邏輯地址中的頁號轉換成為主存中的物理塊號。頁表是硬件地址轉換的依據。頁式存儲管理采用動態重定位方式裝入方式。物理地址=塊號*塊長+頁內地址1．基本的地址變換機構頁表始址頁表長度＋頁號(3)頁內地址頁表寄存器邏輯地址>越界中斷1b塊號頁表頁號0123物理地址頁號

塊號

存取控制頁描述符+如果頁號>頁表長度，則中斷，否則繼續.如果訪問非法，則中斷，否則繼續。頁號位移量虛擬地址

LA

塊號位移量物理地址頁表始址長度頁表寄存器PTR頁表

塊號存取控制頁表項頁號

01

...塊號位移量

1．基本的地址變換機構有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。虛地址3412P＝3412％2048＝1d＝3412mod2048

＝1364MR=9*2048+1364=19796虛地址3412的內存地址是：19796虛地址7145P＝7145％2048＝3d＝7145mod2048

＝1001MR=5*2048+1001=11241虛地址7145的內存地址是：112412．具有快表的地址變換機構執行一次訪內操作至少要訪問主存兩次。增加一個具有并行查詢功能的高速緩沖存儲器，存放在高速緩沖存儲器中的頁表叫快表，他是用來存放當前訪問最頻繁的少數活動頁面的頁表項。解決方法第一次訪頁表第二次是根據地址取數據或指令。具有快表的地址變換機構頁表始址頁表長度＋頁號頁內地址頁表寄存器邏輯地址>越界中斷1b塊號頁表頁號bd物理地址輸入寄存器b頁號塊號快表現代的大多數計算機系統，都支持非常大的邏輯地址空間(232～264)。頁表就變得非常大。4.4.3兩級和多級頁表(2)只將當前需要的部分頁表項調入內存，其余的頁表項仍駐留在磁盤上，需要時再調入。解決方法：(1)采用離散分配方式來解決難以找到一塊連續的大內存空間的問題；將頁表進行分頁，并離散地將各個頁面分別存放在不同的物理塊中，同樣也要為離散分配的頁表再建立一張頁表，稱為外層頁表。1．兩級頁表兩級頁表外層頁號 外層頁內地址 頁內地址31222112110外層頁表頁表1．兩級頁表………012345671141151468內存空間…641第0頁頁表012…1023115114第1頁頁表012…10231468第n頁頁表012…1023174210781011012n外部頁表兩級分頁結構1．兩級頁表外部頁表寄存器外部頁表頁表db物理地址++dP2P1邏輯地址外部頁號外部頁內地址頁內地址具有兩級頁表的地址變換機構：二級頁表地址變換需三次訪問主存兩級頁表對32位機器適用，64位呢？ 頁面大小為4KB即212B，還剩52位，按物理塊大小212位來劃分頁表，則剩余40位用于外層頁號，此時外層頁表可能有1024G個頁表項，要占用4096GB的連續存儲空間

2．多級頁表解決方法：采用多級頁表，將外層頁表再進行分頁。

例:在一個分頁式存儲管理系統中,某作業的頁表如下所示。已知頁面大小為1024B,試將邏輯地址1011,2148,3000,4000,5012轉化為相應的物理地址.頁號塊號021321364.5基本分段存儲管理方式在分頁存儲系統中，作業的地址空間是一維線性的，這破壞了程序內部天然的邏輯結構,造成共享、保護的困難。一個用戶程序往往由幾個程序段（主程序、子程序和函數）所組成，當一個程序裝入內存時，按段進行分配，每個段的大小是不相等的。4.5.1分段式存儲管理的引入引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述需要：

1)方便編程

2)信息共享

3)信息保護

4)動態增長

5)動態鏈接...0S工作區段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N數組[A]12345...4.5.2分段系統的基本原理

1.分段

每個段定義了一組邏輯信息，主程序段，子程序段，數據段等兩維邏輯地址：段號＋段內地址分段地址中的地址具有如下結構：段號段內地址31161502.段表為了實現段的邏輯地址到物理地址的轉換，系統為每個進程設置了一張段表；它記錄了段號，段的首（地）址和長度之間的關系。段號012段首址段長度58K20K100K110K260K140K2.段表作業空間（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k段長基址30k40k20k80k15k120k10k150k段號0123內存空間040K80K120K150K3.地址變換機構從邏輯地址到物理地址的轉換工作過程：將邏輯地址中的段號與段表長度進行比較，若超過了段表長度則產生越界中斷；根據段號和段表始址計算出該段在段表中的位置。檢查段內位移是否超過該段的段長；將該段在內存中的起始地址與邏輯地址的段內位移相加即得到要訪問的物理地址。段表長度段表始址控制寄存器物理地址<+越界中斷分段系統的地址變換機構1002段號S位移量W段表92002008K5004K6006K1K段長基址段號0123+82928K82928692主存段號內存起始地址段長02105002100904193895段號段內位移043025004112532例：在一個段式存儲管理系統中，其段表如表所示。

邏輯地址

段表試求表所示中的邏輯地址所對應的物理地址？4.分頁和分段的主要區別(1)頁是信息的物理單位，段則是信息的邏輯單位(2)頁的大小固定且由系統決定，而段的長度卻不固定(3)分頁的作業地址空間是一維的，即單一的線性地址空間，分段的作業地址空間則是二維的4.5.3信息共享分段易于實現段的共享，即允許若干個進程共享一個或多個分段。段的共享，是通過不同段表中的段表項指向同一個段基址來實現。對共享段的信息必須進行保護分頁系統中雖然也能實現程序和數據的共享，但遠不如分段系統方便。圖分頁系統中共享editor的示意圖data10…data1ed40…ed2ed1進程1data10…data1ed40…ed2ed1進程270…6160…2221頁表80…7160…2221頁表data10…data1data10…data1ed40…ed2ed1…021226061707180主存圖分段系統中共享editor的示意圖data1editor進程1data2editor進程22404080160基址段長段表3804080160基址段長段表data2…data1editor80240280380420主存可重入代碼可重入代碼又稱為“純代碼”，是一種允許多個進程同時訪問的代碼。為使各個進程所執行的代碼完全相同，絕對不允許可重入代碼在執行中有任何改變。在每個進程中，都必須配以局部數據區，把在執行中可能改變的部分拷貝到該數據區，這時的可共享代碼即成為可重入碼。

分段管理的優缺點優點：便于動態申請內存管理和使用統一化便于共享便于動態鏈接缺點：產生碎片思考：與可變分區存儲管理方案的相同點與不同點？4.5.4段頁式存儲管理分頁優點：提高內存利用率分段優點：滿足用戶需要。因此可以將兩者結合成一種新的存儲管理方式系統稱為“段頁式系統”。結合了段式與頁式二者優點克服了二者的缺點

1．基本原理作業仍按邏輯分段，但對每一段不是按單一的連續整體存放到存儲器中，而是把每個段再分成若干個頁面，每一段不必占據連續的主存空間，可把它按頁存放在不連續的主存塊中。04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K數據段1．基本原理

內存劃分：按頁式存儲管理方案內存分配：以頁為單位進行分配地址結構：頁內地址(W)段內頁號(P)段號(S)1．基本原理段頁式存儲管理為每一個裝入主存的作業建立一張段表,每個段又被分成若干個固定大小的頁面，那么每個段又必須建立一張頁表把段中的虛頁變換成內存中的實際頁面。每個段有一個頁表，段表中應有專項指出該段所對應頁表的頁表始址和頁表長度。段號狀態頁表長度頁表始址01510

212段表大小段表始址段表控制寄存器頁號狀態塊號011211192121304115段表、頁表與內存關系內存空間頁表頁表段表頁號狀態塊號012911302．地址變換過程地址變換過程Q：為了獲得一條指令或者數據，需要訪問內存幾次？段頁式存儲管理的優缺點優點：連續空間分配與不連續空間分配方式都屬于實存管理技術。不存在外碎片、段可動態增長、便于共享和控制存取訪問。硬件成本增加、軟件復雜性和管理開銷增加、存在內碎片。缺點：4.6虛擬存儲器的基本概念前面的各種存儲器管理方式有一個共同的特點，即它們都要求將一個作業全部裝入內存后方能運行：(1)有的作業很大，其所要求的內存空間超過了內存總容量。(2)有大量作業要求運行，但由于內存容量不足以容納所有這些作業。1．常規存儲器管理方式的特征

駐留性。作業裝入內存后，便一直駐留在內存中，直至作業運行結束。一次性。要求將作業全部裝入內存后方能運行，即作業在運行前需一次性地全部裝入內存。2．局部性原理局部性原理：程序在執行時將呈現出局部性規律，即在一較短的時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域。具體地表現為：時間局部性和空間局部性2．局部性原理①時間的局限性，如果程序中的某條指令一旦執行，則不久以后該指令可能再次執行；某個數據被訪問，則不久以后該數據可能被再次訪問。②空間的局限性，一旦程序訪問了某個存儲單元，在不久以后，其附近的存儲單元也被訪問，即程序在一段時間內所訪問的地址可能集中在一定的范圍內。3．虛擬存儲器的定義具有請求調入功能和置換功能，能從邏輯上對內存進行擴充的一種存儲器系統，其邏輯容量由內存和外存容量之和決定，其運行速度接近于內存的速度，而成本接近于外存。虛擬存儲器：虛擬存儲是一種性能非常優越的存儲器管理技術3．虛擬存儲器的定義

實現思想：當進程運行時，先將一部分程序裝入內存，另一部分暫時留在外存，當要執行的指令不在內存時，由系統自動完成將它們從外存調入內存工作。目的：提高內存利用率。4.6.2虛擬存儲器的實現方法1．分頁請求系統這是在分頁系統的基礎上，增加了請求調頁功能和頁面置換功能所形成的頁式虛擬存儲系統。1)硬件支持①請求分頁的頁表機制；②缺頁中斷機構；③地址變換機構。2)實現請求分頁的軟件4.6.2虛擬存儲器的實現方法2．請求分段系統這是在分段系統的基礎上，增加了請求調段及分段置換功能后所形成的段式虛擬存儲系統。系統同樣需要必要的硬件支持：(1)請求分段的段表機制。(2)缺段中斷機構。(3)地址變換機構。4.6.3虛擬存儲器的特征多次性：一個作業分成多次調入主存運行；對換性：每個作業不是全部一次性地裝入內存，將當前不運行的程序、數據調至外存盤交換區；虛擬性：虛存是從邏輯上擴充內存容量，使用戶編程所用到的地址空間遠大于實際內存容量。4.7請求分頁存儲管理方式基本思想作業運行的過程中，頁面只有需要時才請求被換入內存，而暫不運行的頁面置換到外存，從而減少對換時間和所需內存數量，增加多道程序的道數。換入和換出是以頁面為基本單位。

需要解決的問題系統需要解決下面三個問題：系統如何獲知進程當前所需頁面不在主存。當發現缺頁時，如何把所缺頁面調入主存。當主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據什么策略選擇欲淘汰的頁面。4.7.1請求分頁中的硬件支持1.頁表機制頁號物理塊號狀態位P訪問字段A修改位M外存地址指示該頁是否已調入內存記錄本頁在一段時間內被訪問的次數，或記錄本頁最近已有多長時間未被訪問，供選擇換出頁面時參考該頁在調入內存后是否被修改過，供置換頁面時參考指出該頁在外存上的地址，供調入該頁時參考查頁表時，當該頁不在主存時，則引起一個缺頁中斷,它與一般的中斷相比，主要區別表現在：

1)在指令執行期間產生和處理中斷信號；

2)一條指令在執行期間，可能產生多次缺頁中斷(為什么？)B:A:指令TOBCopyA頁面6543212.缺頁中斷機構

3．地址變換機構1、存儲保護檢查：頁號>頁表長度？是，越界中斷；否則2；2、查快表：找到，修改訪問位，對于寫操作置修改位，并形成物理地址訪問；若未找到，轉3；3、查頁表狀態位：在主存，將表目寫入快表；否則，缺頁中斷。地址變換過程請求訪問一頁頁號頁表長越界中斷表項在快表中CPU檢索快表訪問頁表頁在內存YNYNY修改快表修改訪問位和修改位形成物理地址N缺頁中斷地址變換過程缺頁中斷處理外存中找到所需頁面有空頁框嗎N選擇淘汰的頁面更新頁表、快表Y該頁修改過Y把該頁寫回外存N保留CPU現場裝入新頁按邏輯地址查快表該頁在快表中有登記?形成物理地址繼續執行指令是發缺頁中斷查頁表否該頁在主存中形成物理地址將該頁登記入快表是保護現場主存有空閑塊?裝入所需要的頁調整頁表和主存分配表恢復現場重啟被中斷的指令是選擇調出的頁該頁被修改?將該頁寫回輔存相應位置否否是缺頁中斷處理流程硬件處理操作系統處理4.7.2內存分配策略和分配算法虛存請求分頁管理在為進程分配內存時，必須考慮三個問題：第一，確定保證進程正常運行所需要的最小的物理塊數；第二，物理塊的分配策略；

第三，確定采用何種分配算法來進行頁面分配1．最小物理塊數的確定保證進程正常運行所需最小的物理塊數，與計算機的硬件結構有關，其值取決于指令的格式、功能和尋址方式。采用直接尋址：最小物理塊數為2；（存放指令的頁和存放數據的頁）采用間接尋址：最小物理塊數為3；

2．物理塊的分配策略1)固定分配局部置換

2)可變分配全局置換3)可變分配局部置換根據進程的類型，為每個進程分配固定數目的內存頁框，整個運行期間不再改變。這種策略的難點在于，為每個進程分配的頁框數N難以確定。操作系統自身保持一個空閑物理塊隊列；當某進程發生缺頁中斷時，由系統從空閑物理塊隊列中取出一塊分配給該進程；但當進程缺頁時，只允許從該進程的頁面中選出一頁換出。若進程缺頁中斷頻繁，則系統須為該進程追加分配若干物理塊。3．物理塊分配算法平均分配算法按比例分配算法n個進程,進程的頁面數為Si,物理塊總數為m,每個進程所能分到的物理塊數為bi

3)考慮優先權的分配算法一部分按比例地分配；另一部分則根據優先權4.7.3調頁策略1．調入頁面的時機（2）預調(prepaging)將要訪問時調入(根據程序順序行為，不一定準）（根據空間局部性，目前：成功率≤50％）

（1）請調(demandpaging)發生缺頁中斷時調入（較費系統開銷）

預調必須輔以請調。

2．確定從何處調入頁面外存：文件區、對換區從何處將缺頁調入內存，分成三種情況：系統擁有足夠的對換區空間：系統缺少足夠的對換區空間：UNIX方式：若系統擁有足夠的對換區空間，則可全部從對換區調入所需頁面如果系統缺少足夠的對換區空間，對于不被修改的文件，則直接從文件區調入；對于可能被修改的文件，則從交換區調入；UNIX系統中，凡未運行過的頁面都從文件區調入；對曾經運行過而又被換出的頁面，則從交換區調入3．頁面調入過程★缺頁中斷★保留CPU環境★缺頁中斷處理★訪問內存數據整個頁面的調入過程對用戶是透明的。邏輯地址空間物理地址空間3．頁面調入過程工作原理012345678...…012CPUOS缺頁中斷缺頁中斷處理子程序3頁表4.8頁面置換算法當出現要訪問的頁面不在內存，內存空間又不足的情況下，系統需淘汰一頁。用來選取淘汰哪一頁的規則，叫置換算法。最佳置換算法先進先出置換算法最近最久未用置換算法Clock置換算法

4.8.1最佳置換算法和先進先出置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。基本思想：1.最佳置換算法選擇從當前時刻開始以后不在使用的頁面淘汰，如果沒有這類頁，則選擇最長(未來)時間內不再被訪問的頁面淘汰。1.最佳置換算法例：一個有5個頁面的進程，在內存為它分配3個物理塊，其頁面訪問順序如下：2，3，2，1，5，2，4，5，3，2，5，2進程運行時，會依次將2，3，1三個頁面裝入內存。以后，當進程要訪問頁面5時，將會產生缺頁中斷。此時OS根據最佳置換算法，將選擇頁面予以淘汰。232152453252223231235435235OTP算法：缺頁次數=6232354354352352351.最佳置換算法％％＝缺頁率為＝50100126×優點：使得頁面調入調出的次數達到最小，這是一種理想情況。缺點：實際上無法實現，因為系統無法預知未來頁面的訪問情況。因此只能用作理論上性能評價的標準。1.最佳置換算法2．先進先出(FIFO)頁面置換算法思想：選擇最早調入內存的頁面淘汰。出發點：近期調入的頁面被再次訪問的概率要大于早期調入的頁面。問題：事實上并非所有的時候都這樣。此時FIFO算法的性能較差。這里，我們仍用上面的例子，但采用FIFO算法進行頁面置換232152453252FIFO算法：缺頁次數=9223232315315215245243243243543522．先進先出(FIFO)頁面置換算法％％＝缺頁率為＝75100129×

采用FIFO算法還會產生一種奇怪現象。在某些情況下，當分配的物理塊數增多反而導致更多的缺頁中斷，這種現象稱為FIFO異常現象或稱Belady現象。（根本原因就是沒有考慮程序執行的動態特征）某進程共有5頁,依次訪問頁面的序列為：1，2，3，4，1，2，5，1，2，3，4，5；當系統為該進程分配的物理塊數為3和4時，它們的缺頁情況如下表。2．先進先出(FIFO)頁面置換算法123412555344123412225331234111255123444512345123334512341222345123111234512123412512345+++++++++++++++++++4.8.2最近最久未使用置換算法基本思想：每次選擇內存中離當前時刻最久未使用過的頁面淘汰。理由：如果某頁被訪問了，則它可能馬上還要被訪問，反之如果該頁很長時間未被訪問，則它在最近一段時間內也不會被訪問。根據：局部性原理。232152453252223231251254352LRU算法：缺頁次數=7354232512543523524.8.2最近最久未使用置換算法％％＝缺頁率為＝58.3100127×2．LRU置換算法的硬件支持LRU置換算法雖然是一種比較好的算法，但要求系統有較多的支持硬件。寄存器棧每個頁面設立移位寄存器,進程訪問某物理塊時,要將相應寄存器的最高位置成1。每隔一定時間將寄存器右移一位。用棧來保存當前使用的各個頁面的頁面號，當進程訪問某頁面時，將該頁面的頁面號從棧中移出，壓入棧頂。某進程具有8個頁面時的LRU訪問情況1)寄存器

R0R1R2R3R4R5R6R7R實頁0001011110011110011010110101010110001000010101011001100101001000123456782)棧假定現有一進程所訪問的頁面的頁面號序列為：44747040740714710470147012470214701270126470710121263012634.8.3

Clock置換算法要實現LRU算法，需要付出很大的系統開銷。1．簡單的Clock置換算法Clock算法只要在頁表中設一個“引用位”，當頁表中的某一頁被訪問時，該位由硬件自動置1，并由頁面管理軟件周期性把所有引用位置0。當需要置換一頁面時，選擇其引用位為0的頁1．簡單的Clock置換算法

簡單Clock置換算法的流程和示例入口查尋指針前進一步，指向下一個表目頁面訪問位=0?選擇該頁面淘汰是返回置頁面訪問位＝“0”否塊號頁號訪問位指針0124034215650711替換指針Page9use=1Page19Use=1Page1Use=1Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page222Use=0Page33Use=1下一個幀指針n-1012345678一個頁替換前的緩沖區狀態第1頁框...下一頁替換后的緩沖區狀態Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page556Use=1Page13Use=0Page67Use=1Page222Use=0Page33Use=1.n012345678..2321524532522*Clock算法：缺頁次數=82*3*2*3*2*3*1*5*2*15*2*4*5*2*4*3*243*2*43*2*5*3*2*5*1*3*2

1*3

2

1

3

2

1

3

5*1．簡單的Clock置換算法在改進型Clock算法中首選置換頁面：既是未使用過的頁面；又是未修改的頁面由訪問位A和修改位M可以組合成四種類型的頁面：(1)最近沒有被引用,沒有被修改(A=0,M=0)(2)最近沒有被引用,但被修改(A=0,M=1)(3)最近被引用,沒有被修改(A=1,M=0)(4)最近被引用過,也被修改過(A=1,M=1)2．改進型Clock置換算法置換步驟：步3：如果步2失敗，再轉向步1操作。2．改進型Clock置換算法步1：從指針當前位置開始,掃描循環隊列。把找到的第一個A=0,M=0的頁面作為淘汰頁面，未找到，轉步2。步2：查找A=0且M=1的頁面，把找到的第一個這樣的頁面作為淘汰頁面，所有經過的頁面的訪問位A置0。4.8.4其它置換算法1、最少使用置換算法把到當前為止被訪問次數最少的頁面淘汰。每頁設置訪問計數器，每當頁面被訪問時，該頁面的訪問計數器加1；發生缺頁中斷時，淘汰計數值最小的頁面，并將所有計數清零；2．頁面緩沖算法它是對FIFO算法的發展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面；設置兩個鏈表，空閑鏈表和已修改頁面鏈表。用FIFO選擇被置換頁如果被置換頁沒有發生修改，將它直接放入空閑鏈表否則放入到已修改頁面的鏈表中。2．頁面緩沖算法需要調入新的物理頁面時，將新頁面內容讀入到空閑頁面鏈表的第一項所指的頁面。空閑頁面和已修改頁面，仍停留在內存中一段時間，如果這些頁面被再次訪問，只需較小開銷。當已修改頁面達到一定數目后，再將它們一起調出到外存，然后將它們歸入空閑頁面鏈表。頁面置換算法比較0510152025354030068101214FIFOCLOCK

LRUOPT分配的頁數每千次訪問的缺頁中斷數影響缺頁次數的因素(1)分配給進程的物理頁面數(2)頁面本身的大小(3)程序的編制方法(4)頁面淘汰算法性能問題顛簸（抖動）:頁面淘汰算法不合理分配給進程的物理頁面數太少

在虛存中，頁面在內存與外存之間頻繁調度，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統效率急劇下降，甚至導致系統崩潰。這種現象稱為顛簸或抖動原因：

工作集（WorkingSet）模型對一個作業來說，當分配給它的頁面數目小于某一個數值時，其缺頁中斷次數急劇增加，甚至出現頁面抖動現象；而高于這個頁面數時，缺頁中斷次數不會明顯減少。此時我們稱這個頁面數范圍為頁面的“工作集”。影響工作集的因素作業的特征（結構、大小、訪問數據的規律等）作業的運行時間段等4.9請求分段存儲管理方式與請求分頁系統類似，在分段的基礎上增加請求調段功能和段置換功能，便可形成具有虛擬存儲器功能的請求分段系統。為實現請求分段式存儲管理,需要有一定的硬件和相應的軟件支持。段表機制缺段中斷機構地址變換機構4.9.1請求分段中的硬件支持1．段表機制系統要為每一個作業建立一張段表。段表是進行段調度的主要依據。其一般格式為：段名段長段的基址存取方式訪問字段A修改位M存在位P增補位外存始址標志本分段的存取屬性記錄該段被訪問的頻繁程度（與分頁相應字段同）該段在調入內存后是否被修改過，供置換時參考指示本段是否已調入內存，供程序訪問時參考本段在運行過程中，是否做過動態增長本段在外存中的起始地址2．缺段中斷機構在請求分段系統中，若進程訪問的段尚未調入內存，缺段中斷機制產生缺段中斷信號，中斷處理程序根據信號調入所需段。和缺頁中斷機制類似，在一條指令執行期間可能產生多次中斷。和缺頁中斷機制不同的是，指令和操作數必定不會跨越段邊界上；虛段S不在內存阻塞請求進程內存中有合適的空閑區嗎？從外存讀入段S修改段表及內存空區鏈喚醒請求進程返回空區容量總和能否滿足？空區拼接，以形成一個合適的空區淘汰一個或幾個實段，以形成一個合適空區否否是是3．地址變換機構請求分段系統中的地址變換機構是在分段系統地址變換機構的基礎上形成的。在地址變換時，若發現所要訪問的段不在內存，必須先將所缺的段調入內存，并修改段表，然后才能再利用段表進行地址變換。為此，在地址變換機構中又增加了某些功能，如缺段中斷的請求及處理等。訪問[S][W]W段長分段越界中斷處理符合存取方式NYY分段保護中斷處理段S在主存N缺段中斷處理NY修改訪問位、修改位形成物理地址

返回4.9.2分段的共享與保護1．共享段表為了實現分段共享，可在系統中配置一張共享段表，所有各共享段都在共享段表中占有一表項。表項中記錄了共享段的段號、段長、內存始址、存在位等信息，并記錄了共享此分段的每個進程的情況。1．共享段表段名段長內存始址狀態外存始址共享進程計數count狀態進程名進程號段號存取控制………………共享段表1．共享段表(3)段號。對于一個共享段，不同的進程可以各用不同的段號去共享該段。(2)存取控制字段。對于一個共享段，應給不同的進程以不同的存取權限。(1)共享進程計數count。記錄有多少個進程需要共享該分段，特設置了一個整型變量count。2．共享段的分配與回收1)共享段的分配第一個請求以后其它進程使用該共享段申請內存分區，調入，修改共享段表相應內容；在本進程段表中填入該共享段的物理地址；然后在共享段表中增加一表目，填入相應內容2．共享段的分配與回收2)共享段的回收撤消在該進程段表中共享段所對應的表項，以及執行count:=count-1操作。若count結果為0，則須由系統回收該共享段的物理內存，以及取消在共享段表中該段所對應的表項。3．分段保護越界檢查2)存取控制檢查3)環保護機構段號與段表長度進行比較段內地址與段長進行比較(1)只讀(2)只執行(3)讀/寫(1)可以訪問在相同環或較低特權環中的數據。(2)可以調用在相同環或較高特權環中的服務。3．分段保護圖環保護機構

練習1、考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當內存塊數量分別為3，5時，試問LRU、FIFO、OPT這三種置換算法的缺頁次數各是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產生一次缺頁。）時47分31秒內存塊數為3,FIFO算法頁面蹤跡圖％

％＝

缺頁率為＝

80

100

2016

*

27637637637162162162561541342342312312161212342156212376321236++++ +++ + + + + +++++415321613213216內存塊數為3,LRU算法頁面蹤跡圖％

％＝

缺頁率為＝

75

100

2015

*

2363