第5章存儲管理存儲管理是對主存（又稱內存）的管理。內存：處理機可以直接存取指令和數據的存儲器，是進程得以運行的重要物質基礎，是計算機中的一種寶貴而緊俏的資源。近年，隨著硬件技術和生產水平的迅速發展，內存的成本迅速下降，容量一直不斷擴大，仍不能滿足各種軟件對存儲空間急劇增長的需求。對內存的有效管理和有效使用，是現代操作系統十分重要的問題。2024/11/41第5章存儲管理本章要點：5.1存儲管理的基本概念5.2連續分配方式5.3離散分配方式5.4虛擬存儲器5.5案例：Linux存儲管理5.6例題分析5.7本章小結2024/11/425.1存儲管理的基本概念知識點：§5.1.1存儲管理的功能§5.1.2存儲器管理方式§5.1.3地址重定位返回2024/11/43存儲管理的功能內存資源不足：單道程序階段，已經意識到存儲資源不足，開始研究如何從邏輯上擴充內存空間。多道程序出現后，這個問題更為突出，且提出如何使每道程序都能在不受干擾的環境中運行，并能盡量提高存儲器的利用率。為對主存進行有效的管理，存儲管理應具有以下功能：內存的分配和回收：為每道程序分配內存空間，由操作系統完成主存儲器空間的分配和管理，使程序員擺脫程序設計的麻煩，提高編程效率；回收系統或用戶釋放的存儲區。提高存儲器的利用率：分配內存空間時，盡量減少不可用的存儲空間（“零頭”），允許正在運行程序申請附加內存空間，使多道程序能動態地共享主存。2024/11/44地址映射：把進程地址空間中使用的邏輯地址變換成存儲空間中的物理地址的過程。目標程序限定的地址范圍稱該程序的地址空間，是程序訪問信息時用到的一系列地址單元的集合，地址空間中的地址是邏輯地址。內存空間是內存中物理地址的集合。兩者不一致。地址映射一般需要硬件或軟件的配合。存儲保護：確保進入主存的每道程序都在自己的內存空間運行，互不干擾。既要防止一道程序由于錯誤破壞其他程序，也要防止破壞系統程序。保護一般由硬件和軟件配合完成。擴充主存容量：借助虛擬存儲技術或其他自動覆蓋技術，為用戶提供比主存空間大的地址空間，實現擴充主存容量的目的。“提高存儲器的利用率”和“更好地滿足用戶需求”，是存儲管理方式不斷發展的推動力。返回存儲管理的功能2024/11/45存儲器管理方式一般有以下幾種分配方式：1.連續分配方式為一個系統或用戶程序分配一個連續的空間。有以下兩種方式：⑴單一連續分配方式單道程序的一種存儲管理方式，內存中僅駐留一道程序，整個用戶區為一個用戶獨占。不適用于多道程序。⑵分區分配方式可用于多道程序設計的較簡單的存儲管理方式。把內存劃分為若干分區，操作系統占用一個分區，其余每個分區容納一個進程。分區分配方式可以進一步分為兩種：①固定分區分配：將內存用戶區劃分為若干個固定大小的區域，每個區域中駐留一道程序；②動態分區分配：根據用戶程序大小，動態地對內存進行劃分，各分區大小不定，內存劃分為多個分區，數目可變。2024/11/462.離散分配方式為減少連續分配產生的碎片，提高存儲器的利用率，引入離散分配方式。可將一個用戶程序離散地分配到內存中多個不相鄰接的區域中。存儲器管理方式2024/11/47離散分配方式有三種：⑴分頁存儲管理：用戶程序的地址空間劃分成若干個固定大小的稱為“頁”的區域，相應將內存空間分成若干個物理塊，頁和塊大小相等。可將用戶程序的任一頁放入內存的任一塊中，實現離散分配，且內存中的碎片大小不會超過一頁。⑵分段存儲管理：用戶程序的地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，這些段在內存中可以不相鄰。⑶段頁式存儲管理：分頁和分段兩種存儲管理方式結合的產物，發揮兩者優點，既提高存儲器利用率，又能滿足用戶要求。返回存儲器管理方式2024/11/48地址重定位1.重定位及相關概念用匯編語言或高級語言編寫程序時，通過符號名訪問某單元。程序中由符號名組成的空間稱為名空間。一個應用程序編譯后，形成若干個目標程序，目標程序再經過鏈接形成可裝入程序，即轉換為相對地址編址形式。這些程序中地址都是以“0”為基址順序編址。由這些地址形成的地址范圍稱為地址空間，其中的地址稱為邏輯地址或相對地址。存儲空間是主存中一系列存儲信息的物理單元的集合，其中的地址稱為物理地址或絕對地址。即地址空間是邏輯地址的集合；存儲空間是物理地址的集合。一個是虛的概念，一個是實的物體。一個編譯好的程序保存在自己的地址空間中，需要在計算機上運行時才裝入存儲空間。2024/11/49一個程序在裝入時分配到的存儲空間與其地址空間不一致。程序運行時要訪問的指令、數據的實際地址和地址空間中的地址不同。若在程序裝入或運行時不對有關地址部分加以修改，將導致錯誤的結果。把一個相對地址空間的程序裝入到物理地址空間時，由于兩個空間不一致而需要進行的地址變換，稱地址重定位或地址映射。地址變換過程，把程序地址空間中使用的邏輯地址變換為存儲空間中的物理地址的過程。地址重定位2024/11/410根據地址變換持續的時間及采用技術的不同，可以把重定位分為靜態重定位和動態重定位兩類。⑴靜態重定位程序運行前，由鏈接裝入程序進行重定位。即：在程序裝入主存同時，將程序中邏輯地址轉換為物理地址。特點：無需增加硬件地址變換機構。要求為每個程序分配一個連續的存儲區；程序執行期間不移動，難以做到程序和數據的共享。地址重定位2024/11/411靜態重定位的實現：操作系統為程序分配一個以某地址為起始地址的連續內存區域，重定位時，將程序中指令或操作數的邏輯地址加上該起始地址，即可得到物理地址。例：圖5-1，程序裝到從1000開始的內存區域中，物理地址為邏輯地址值加上1000。圖5-1靜態重定位程序裝入示例地址重定位2024/11/412⑵動態重定位程序執行過程中，每當訪問指令或數據，將被訪問程序或數據的邏輯地址轉換為物理地址。重定位過程在程序執行期間隨指令執行逐步完成。一種允許程序在執行過程中在內存中移動的技術，必須獲得硬件地址變換機構的支持，在系統中增加一個重定位寄存器，用來裝入程序在內存中的起始地址。程序執行時，真正訪問內存的地址是有效地址與重定位寄存器中的地址相加形成。地址重定位2024/11/413動態重定位的原理：圖5-2。特點：●可以將程序分配到不連續的存儲區中；●程序運行前，可以只裝入部分代碼即投入運行；●程序運行期間，根據需要動態申請分配內存；●為便于程序段共享，可提供一個比主存空間大得多的地址空間。動態重定位需要附加的硬件支持，實現存儲管理的軟件算法比較復雜。地址重定位2024/11/414圖5-2動態重定位示意圖返回地址重定位2024/11/415關系地址重定位的方式+存儲管理方式：內存分配方式是緊密相關的。2024/11/4165.2連續分配方式知識點：§5.2.1單一連續分配§5.2.2分區存儲管理§5.2.3覆蓋與交換返回2024/11/4175.2.1單一連續分配應用環境：單一連續分配是最簡單的一種存儲管理方式，只能用于單用戶、單任務的操作系統。使用方法：將內存分為兩個存儲區，一個存儲區僅供操作系統使用（系統區），其余全部內存空間供用戶使用（用戶區）。主要采用靜態分配方式，進程一旦進入內存，直到執行結束后才釋放內存。主要特點：管理簡單，只需很少軟件和硬件支持，便于用戶了解和使用。優缺點：單用戶采用，內存只裝入一道進程運行，各類資源利用率不高。2024/11/418圖5-3單一連續分配返回5.2.1單一連續分配2024/11/419分區存儲管理分區存儲管理是滿足多道程序設計的一種最簡單的存儲管理方法，把內存劃分為若干分區，操作系統占用一個分區外，其余每個分區容納一個進程。1.固定分區分配特點：內存空間劃分為若干個固定大小的區域，每個區域邊界不能改變。主要劃分方式：各分區大小相等和分區的大小不等。每個區域中駐留一道程序。2024/11/420表5-1分區說明表分區號起始地址長度狀態進程名120K28K已分配P1248K32K空閑380K64K已分配P24144K112K空閑分區存儲管理2024/11/421分區存儲管理使用方式：根據各分區大小排隊，建立一張分區說明表（表5-1），記錄分區數目及每個分區的起始地址、大小及狀態（是否已分配）。用戶程序裝入時，內存分配程序檢索該表，找出一個能滿足要求、尚未分配的分區分配，修改分區說明表中該分區表項的狀態；若找不到大小足夠的分區，拒絕為分配內存。2024/11/422優缺點：進程的大小不一定與某個分區大小相等，絕大多數已分配的分區中都有一部分存儲空間被浪費。固定分區分配管理方法主存不能得到充分利用。圖5-4固定分區分配分區存儲管理2024/11/423分區存儲管理2024/11/4242.動態分區分配（可變分區分配）根據進程大小動態劃分分區，使分區的大小正好適應進程需要。各分區大小不定，內存中分區數目不定。進程進入系統前，根據進程大小申請所需存儲容量，由系統實施分配。為了管理主存分區的分配情況，建立兩張表，除分區說明表外，還有內存空閑分區表，登記內存中空閑分區的位置、大小等信息。有進程申請內存分區時，按一定分配算法從空閑分區表（或空閑分區鏈）中選出一個大于等于該進程所需容量的分區分配。若該分區大于進程所需容量，剩余的較小空白區仍留在空閑分區表中，并對空閑分區表進行相應修改。一個進程完成后，所占用的分區釋放，變成空白區，并與鄰接的空白區合并。分區存儲管理2024/11/4252.動態分區分配例子：分區存儲管理2024/11/4262.動態分區分配特點：可變式分區的存儲管理方式由兩個特點：第一個特點是分區個數是可變的，且分區大小也不是固定的；第二個特點是內存中分布著個數和大小都是變化的自由分區和碎片，這些自由分區有些可能相當大，有些則相當小。分區存儲管理2024/11/4272.動態分區分配可變式分區存儲管理所用的基本數據結構：為實現可變分區的管理，可以采用兩張表格記錄內存分區的情況，其中一張表格記錄已分配區的信息，另一張表格記錄空閑分區的信息，如圖所示。表格中狀態為“空表目”表示表示該表目中沒有登記分區的信息，當需要表目來登記分區信息時，可使用狀態為“空表目”的表目。可變分區的分區管理也廣泛采用空閑區鏈的方法。即把每個分區的起始若干各自接分為兩部分：前一部分作為鏈指針，指向下一空閑區的起始地址；后一部分指出本空閑區的大小。系統中用一固定單元作為鏈的頭指針，指向第一空閑區的起始地址。最后一個空閑區的鏈指針中存放鏈尾標志（如0）。這樣使用鏈指針把所有空閑分區鏈接在一起，構成一條空閑區鏈，如圖所示。分區存儲管理2024/11/4282.動態分區分配可變式分區存儲管理所用的基本數據結構：分區存儲管理分區表空閑塊鏈2024/11/429常用分配算法（四種）：⑴首次適應算法要求：空閑分區按地址遞增的次序排列。內存分配時，從空閑分區表（或空閑分區鏈）首開始順序查找，直到找到第一個能滿足大小要求的空閑分區為止。根據進程大小從該分區劃出一塊內存空間分配，余下空閑分區仍留在空閑分區表（或空閑分區鏈）中。特點：優先利用內存低地址部分的空閑分區，保留高地址部分的大空閑區。低地址部分不斷被劃分，低地址端留下許多難以利用的很小的空閑分區；每次查找從低地址部分開始，增加了查找可用空閑分區的開銷。分區存儲管理2024/11/430⑵循環首次適應算法由首次適應算法演變來。分配內存空間時，從上次找到的空閑分區的下一個空閑分區開始查找，直到找到第一個能滿足大小要求的空閑分區為止。根據進程大小從該分區中劃出一塊內存空間分配，余下空閑分區仍留在空閑分區表（或空閑分區鏈）中。特點：存儲空間的利用更均衡，不致使小的空閑區集中在存儲區的一端，但導致缺乏大的空閑分區。分區存儲管理2024/11/431⑶最佳適應算法“最佳”指每次分配內存時總是把既滿足要求，又是最小的空閑區分配給進程，避免了“大材小用”。為了快速查找到合適的空閑區，要求所有空閑區按大小遞增的順序排列。查找時，從空閑分區表首開始查找，找到的第一個能滿足大小要求的空閑分區。若找到的空閑分區大于進程的大小，切割剩余空閑區仍留在空閑分區表中。特點：若存在與進程大小一致的空閑分區，必然被選中；若不存在與進程大小一致的空閑分區，只劃分比進程稍大的空閑分區，保留大的空閑區。空閑區一般不可能正好和進程申請的內存空間大小一樣，分割成兩部分時，使剩下的空閑區非常小，在存儲器中留下許多難以利用的小空閑區。分區存儲管理2024/11/432⑷最壞適應算法要求：空閑分區按大小遞減次序排列。內存分配時，先檢查空閑分區表（或空閑分區鏈）中第一個空閑分區，若第一個空閑分區小于要求的大小，分配失敗；否則從該空閑分區中劃出進程大小的一塊內存空間分配，余下空閑分區仍留在空閑分區表（或空閑分區鏈）中。特點：總是挑選滿足要求的最大的分區分配，剩下的空閑區比較大，也能裝下其他進程。由于最大的空閑區總是首先被分配而劃分，大進程到來時，存儲空間的申請往往得不到滿足。分區存儲管理2024/11/433可變式分區分配算法：分區存儲管理2024/11/434可變式分區釋放算法：分區存儲管理2024/11/435可變式分區中的存儲保護與重定位：保護：界地址法重定位：動態重定位分區存儲管理2024/11/436可變式分區中的存儲保護與重定位：可變分區的存儲保護可使用“界地址法”，也可以使用一對基址、限長寄存器，其道理也與使用一對上、下界地址寄存器的道理相同，但基址寄存器還可以起到定位寄存器的作用。可變分區采用動態重定位的方式實現重定位，這樣即使移動內存中的作業使得其基地址發生變化，作業的執行也不會受到影響。圖中給出了存儲保護和地址重定位的關系。分區存儲管理2024/11/437可變分區方式的優缺點：優點：由于采用了拼接和移動技術，內存中不再有不能使用的碎片，從而能有效地利用主存空間，提高多道程序系統的多道程度，從而也提高了對處理機和外設的利用率。缺點：作業大小依然受內存容量的限制；對碎片問題的解決需要以增加系統開銷為代價；由于作業需要連續存放，使得內存的共享問題不好解決。分區存儲管理2024/11/438動態分區分配需要解決的問題有三個：（1）分區分配中所用的數據結構。（2）分區的分配算法。（3）分區的分配與回收操作。分區存儲管理2024/11/439動態分區分配需要解決的問題有三個：回收操作：回收分區的主要工作是：首先檢查是否有臨接的空閑區，如有則合并，使之成為一個連續的空閑區，而不是許多零散的小的部分；之后，修改有關的分區描述信息。一個回收分區鄰接空閑區的情況有四種：如圖4.13所示。第一種情況是回收分區r上鄰的一個空閑區，此時應合并成為一個連續的空閑區，其始址為r上鄰的空閑區始址，而大小為二者之和。第二種情況與r下面的空閑區相鄰。直接合并。第三種情況是與上下空閑區相鄰。將三個區域合并成一個連續的空閑區。第四種情況不和任何空閑區相鄰，應建立一個新的空閑區，并加到自由主存隊列中。分區存儲管理2024/11/440動態分區分配需要解決的問題有三個：回收操作：分區存儲管理fr作業1作業2rf2f1rf2作業1r作業2回收分區r上鄰的空閑區回收分區r下鄰的空閑區回收分區r上、下鄰的空閑區回收分區r單獨為空閑區2024/11/4413.碎片問題與拼接技術分區存儲管理實現了多道程序設計，同時也產生了一個非常嚴重的問題即碎片問題。碎片：內存中無法被利用的小的空閑區。分區存儲管理方式下，系統運行一段時間后，內存中碎片占據相當數量的空間，甚至當一個進程申請一定數量的主存時，雖然空閑區總和大于進程申請的容量，但沒有單個空閑區可以裝下該進程。解決辦法之一：采用拼接（緊縮、緊湊）技術。拼接：移動存儲器中所有已分配區到主存的一端，使分散的空閑區連成一個大的空閑區。分區存儲管理2024/11/4423.碎片問題與拼接技術：分區存儲管理操作系統用戶程序1用戶程序3用戶程序610kb30kb用戶程序914kb26kb操作系統用戶程序1用戶程序3用戶程序6用戶程序980KBa緊湊前b緊湊后緊湊的示意2024/11/443拼接技術有一個拼接的時機問題，有兩種解決方案。方案一：某個分區回收時立即進行拼接，使主存中總是只有一個連續的空閑區。拼接費時間，頻率過高使系統開銷加大。方案二：找不到足夠大的空閑區且空閑區的存儲容量可以滿足進程要求時拼接。拼接頻率相對較小，空閑區的管理稍為復雜些。返回分區存儲管理2024/11/444覆蓋與交換擴充內存的方法：覆蓋與交換技術是在多道程序環境下擴充內存的兩種方法。應用覆蓋技術主要用在早期操作系統；交換技術在現代操作系統仍使用；2024/11/445覆蓋與交換1．覆蓋技術覆蓋：程序中若干程序段或數據段按時間先后使用內存某個區域。實現方法：將程序必要部分的代碼和數據常駐內存，可選覆蓋部分平時存放在外存(覆蓋段)，需要時才裝入內存。不存在調用關系的模塊不必同時裝入到內存，從而可以相互覆蓋。每個覆蓋段是一個相對獨立的程序段，執行時不要求同時裝入內存的一系列覆蓋段組成一組（覆蓋段組），將一個覆蓋段組分配到同一個存儲區域，覆蓋段按照時間先后使用該存儲區域。作用：覆蓋(Overlay)技術可以在較小的可用內存中運行較大的程序。2024/11/446圖5-5覆蓋段組示意圖覆蓋與交換A-20kB-50kF-30kC-30kD-20kE-40kD-20kE-40kB-50kF-30k2024/11/447例：某進程的程序由A，B，C，D，E，F等6個程序段組成。調用關系：圖5-5。程序段A只調用程序段B和C，程序段B只調用程序段F，程序段C只調用D和E。即B不會調用C，C也不會調用B。解決方法：程序段A常駐內存，程序段B和程序段C無需同時在內存中。按圖分配程序段的調入。進程正文段所需要內存空間：A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)＝190K采用覆蓋技術后，只需要100K內存空間即可。覆蓋與交換2024/11/448優缺點：要求用戶清楚地了解程序結構，指定各程序段調入內存的先后次序，以及內存中可以覆蓋掉的程序段位置等，必須在編程時劃分程序模塊，確定模塊之間覆蓋關系，增加了編程復雜度；需要從外存裝入覆蓋文件，以時間延長換取空間節省。應用：早期采用的簡單的擴充主存的技術，用戶負擔重，程序段最大長度內存容量限制。覆蓋技術目前已不再普遍使用。覆蓋與交換2024/11/4492．交換技術含義：多個進程并發執行時，將暫時不能執行的進程送到外存中，獲得空閑內存空間裝入新的進程，或讀入保存在外存中需要執行的進程。交換又稱“對換”。特點：交換單位為整個進程的地址空間。應用：常用于多道程序系統或小型分時系統，與分區式存儲管理配合使用。返回覆蓋與交換2024/11/4502．交換技術優點：可以增加并發運行進程的數目，給用戶提供適當的響應時間。缺點：交換技術存在不足，如控制換入和換出增加處理機開銷，進程整個地址空間都進行對換。比較：與覆蓋技術相比，不要求程序員給出程序段之間的覆蓋結構，不影響程序結構。交換技術主要在進程間進行，覆蓋技術主要在同進程內進行。改進：傳統交換技術的交換單位為整個進程。如果交換單位為進程的一部分，內存利用率將進一步提升。返回覆蓋與交換2024/11/451分區分配方式會形成許多“碎片”，盡管通過拼接技術可以解決碎片問題，但花費代價很高。離散分配方式允許將一個進程直接分散地分配到許多不相鄰的分區中，不必再進行拼接。5.3離散分配方式返回2024/11/452知識點：

頁式存儲管理

段式存儲管理

段頁式存儲管理5.3離散分配方式返回2024/11/453頁式系統應解決的問題：采用“緊湊”技術解決按區分配中存在的碎片問題，是以花費CPU時間為代價換來的。為了尋找解決碎片問題的新途徑，人們很容易想到讓程序不連續存放，例如，有一個作業要求投入運行，其程序的地址空間是3KB,而主存當前只有兩個各為1KB和2KB的空閑區。顯然各空閑區的大小比該程序的地址空間小，而總和卻相同。這樣就考慮將程序分開存放。放在不相鄰的兩個區域中。這正是分頁的思想。在分頁存儲管理中，主存被分成一系列的塊，程序的地址空間被分成一系列的頁面。然后將頁面存放在主存塊中。為了便于實現動態地址變，一般主存的塊和頁面大小相等并為2的冪次。頁式存儲管理2024/11/4541.頁式存儲管理的實現思想：用戶進程的地址空間劃分成若干個大小相等的區域，稱為頁或頁面。相應將主存存儲空間分成與頁大小相等的區域，稱塊或物理塊或頁框。頁的大小與塊的大小完全相同。為進程分配存儲空間時，以塊為單位分配，可以將進程的任意一頁放到主存任意一個塊中。調度進程運行時，必須將進程所有頁面一次調入主存，若主存沒有足夠的物理塊，進程等待。例如：一個作業若有n個頁，那么就為它分配n個塊，每頁裝入一塊。通常作業的最后一頁不滿，但是也分配一塊。分頁式管理分配給作業的塊不要求是相互鄰接的，即塊間的地址可以是不連續的，但是塊內地址連續，塊的大小固定。頁式存儲管理2024/11/455頁式存儲管理內存分配示例：頁式存儲管理最后一頁可以不滿內存中離散不連續分配2024/11/456頁表：頁式存儲管理用戶程序0頁1頁2頁3頁4頁5頁n頁內存0塊1塊2塊3塊4塊5塊6塊7塊8塊9塊10塊2塊3塊6塊8塊9塊2024/11/457頁表：頁式存儲管理用戶程序0頁1頁2頁3頁4頁5頁n頁內存0塊1塊2塊3塊4塊5塊6塊7塊8塊9塊10塊2塊3塊6塊8塊9塊2頁3頁6頁8頁9頁塊號0頁1頁2頁3頁4頁5頁n頁頁號頁表對應項2024/11/458在分頁系統中，允許進程的每一頁離散地存儲在內存的任一物理塊中，但系統應能保證進程的正確運行。即能在內存中找到每個頁面所對應的物理塊。為此系統又為每個進程建立一張頁面映象表，簡稱頁表。在進程地址空間的所有頁內（0~n），依次在頁表中有一頁表項，其中記錄了相應頁在內存中對應的物理塊。見圖的中間部分。頁表的作用：實現了從頁號到物理塊號的地址映象。即使在簡單的分頁系統中，也常在頁表的表項中設置一存取控制字。用于對存儲塊中內容進行保護。頁式存儲管理2024/11/459目的：為便于在內存中找到進程每個頁對應的物理塊，系統為每個進程建立一張頁面映象表，簡稱頁表。位置：頁表一般放在內存中。表項：進程地址空間內每一頁與頁表中一個表項對應，記錄相應頁在內存中對應的物理塊號（圖5-6）。頁式存儲管理2024/11/460作業的邏輯地址空間一般是一個從零開始的一維線性地址空間，但是通常塊和頁的大小是2的冪，如1K、2K、4K字節等，所以作業的邏輯地址可以解釋為由兩部分組成：頁號頁內偏移例如：學號：目的是反過來用身份證號：目的是反過來用頁式存儲管理2024/11/461頁內偏移范圍與內存塊的大小有關，頁號的范圍還取決于邏輯地址的位數。例如：若地址寄存器的長度為16位，塊的大小為1K字節，則頁內偏移變化范圍為0~1023（即1×1024-1）字節，這需要10位來進行描述，剩下的6位就是用來描述頁號，其范圍是0~63（即26-1），地址結構如下：15————109————————0

頁號P頁內偏移W

頁式存儲管理2024/11/462對邏輯地址的解釋與理解：如何利用頁表進行地址變換，找到子令或數據的物理地址，這和計算機所采用的地址結構有關。而地址結構又與所選擇的頁面尺寸有關。比如，當CPU給出的虛地址長度為32位，頁面的大小為4kb時，在分區系統中的地址格式如圖所示：頁號頁內偏移量：頁式存儲管理頁號頁內偏移量4kb=22×210=212頁內偏移量占12位0111231頁號占20位32-12=202024/11/463小結：目的：為便于在內存中找到進程每個頁對應的物理塊，系統為每個進程建立一張頁面映象表，簡稱頁表。進程地址空間內每一頁與頁表中一個表項對應，記錄相應頁在內存中對應的物理塊號（圖5-6）。位置：頁表一般放在內存中。邏輯地址包含兩部分：頁號P，頁內位移W。兩部分構成的地址長度為16位。其中，0～9位頁內地址（每頁1K）；10～15位頁號，地址空間最多允許64項。作業的邏輯地址到物理地址的變換是通過頁表來實現的，即動態地址重定位是通過頁表來實現的。頁式存儲管理系統中的邏輯地址結構如下：頁號P頁內位移W1510

0頁式存儲管理2024/11/464圖5-6頁表的作用頁式存儲管理2024/11/465含義：頁號：指定在頁表中的位置，頁號為幾即在頁表中的第幾個頁表項（加1）。即：用頁號索引頁表，可以得到這一頁在內存中的物理塊號。頁內偏移量：在頁內的位置，因為頁與塊是一樣大，因此也代表在塊內的位置，即：頁內的相對位置與塊內的相對位置是相同的。頁式存儲管理系統中的邏輯地址結構如下：頁號P頁內位移W1510

0頁式存儲管理2024/11/466頁式存儲管理1KB2KB3KB-10mov1,[2500]123mov1,[2500]作業2的進程在CPU上運行0000100111000100091015mov1,[2500]123頁號p頁內偏移量02KB4KB7KB256KB-1+頁表始址寄存器0001110111000100091015p=2w=452頁內偏移量頁號p012247頁號塊號頁式系統地址變換結構01002500214876201024×2+100=2048+100=21481024×7+452=7168+452=76202500=2048+4520100=0000+1002024/11/467頁式存儲管理假設頁面大小為1kb，機器的地址長度為16位。下面以圖所示作業2程序中的一條指令的執行過程，來說明頁式系統中的地址變換過程。程序的地址空間中第100號單元處有一條指令為“movr1,[2500]”。這條指令在主存中的實際位置為2148號單元（第2塊452號單元），而這條指令要取的數123在程序的地址空間中位于2500號單元（第2頁的452號單元）處。它在主存中存于7620號單元（第7塊452號單元）。2024/11/468頁式存儲管理當作業2的相應進程在CPU上運行時，操作系統負責把該作業的頁表在主存中的起始地址（a）送到頁表起始地址寄存器中。以便在進程運行中進行地址變換時由它控制找到該作業的頁表。當作業2的程序執行到指令“movr1,[2500]”時，CPU給出的操作數地址為2500，首先由分頁機構自動把它分成兩部分，得到頁號p=2,頁內相對位移w=452。然后，根據頁表始址寄存器指示的頁表始地址，以頁號為索引，找到第2頁所對應的塊號7。然后，將塊號7和頁內位移量w拼接在一起，就形成了訪問主存的物理地址7620。這正是所取數123所在主存的實際位置。2024/11/469頁式存儲管理82024/11/470頁式存儲管理頁表是每個作業一張，正在運行的作業的頁表的起始地址和頁表長度要裝入頁表控制寄存器。上面的地址變換是借助硬件的地址變換結構來實現的。地址變換關系如下：頁表起始地址=（頁表控制寄存器）頁表中頁號為P的表目地址=（頁表控制寄存器）+頁表表目長度×P，由此獲得對應的內存塊號P’。物理地址=P’×塊長+頁內偏移W由圖上例子可見，雖然作業被存放在若干個不連續的塊中，但在作業執行中總是能按確切的地址進行存取。2024/11/4712.地址變換過程：進程訪問某個邏輯地址中的數據時，分頁地址變換機構自動將邏輯地址分為頁號和頁內位移兩部分，再以頁號為索引檢索頁表。檢索前，先將頁號與頁表長度比較，若頁號超過頁表長度，表示本次訪問的地址已超越進程的地址空間，系統產生地址越界中斷。若頁訪問合法，由頁表起始地址和頁號計算相應頁表項位置，得到該頁物理塊號。將塊號與邏輯地址中的頁內位移拼接，形成訪問主存的物理地址。圖5-7：頁式存儲管理系統中的地址變換過程。假定頁面大小1K字節，邏輯地址1148=（1×1024+124）頁號為1，頁內地址為124。由頁表知，第1頁對應物理塊號為3。將塊號3與頁內地址124拼接（3×1024+124=3196），得到物理地址3196。頁式存儲管理2024/11/472圖5-7頁式存儲管理系統的地址變換過程頁式存儲管理2024/11/4733.聯想存儲器：頁表存放在內存中。由地址變換過程可知，若頁表全部放在主存，存取一個數據或一條指令至少訪問兩次主存。第一次訪問頁表，確定物理地址；第二次根據地址存取數據或指令。這種方法比通常執行指令速度慢一倍。為提高查表速度，可在地址變換機構中增設一個具有并行查找能力的高速緩沖存儲器（聯想存儲器或快表），頁表放在這個高速緩沖存儲器中。高速緩沖存儲器一般是半導體存儲器，工作周期與CPU大致相同，造價較高。為降低成本，在快表中存放正在運行進程當前訪問的頁表項，頁表其余部分存放在內存中。頁式存儲管理2024/11/474頁式存儲管理快表：由于需要利用頁表進行地址變換，而頁表存放在內存，所以在按給定的邏輯地址進行一次讀/寫時，必須兩次訪問內存，即第一次訪問內存中的頁表，第二次讀/寫相應的內存單元，這使得存取速度下降。為了提高存取速度，改進的辦法是采用比內存速度快得多的高速存儲器來存放常用頁的頁表，這個快速頁表稱為快表。高速存儲器是比內存存取速度快得多，但是價格也更高的存儲器，故一般是小容量的。快表是頁表的一部分存放在高速存儲器中的一個副本。有一些系統將部分頁表放在快速存儲器中，其余部仍放在主存中。存放頁表部分內容的快速存儲器稱相聯存儲器，也稱為聯想存儲器。聯想存儲器中存放的部分頁表稱為“快表”。它的格式如下圖所示。這樣的聯想存儲器一般由8個~16個單元組成。它們用來存放正在運行進程的當前最常用的頁號和它相應的塊號，并具有進行查找的能力和通常的執行過程一樣，只要訪問一次主存，就可以取出指令或存取數據。如果所需要查的頁號和聯想存儲器中所有的頁號不匹配，則地址變換過程還得通過主存中的頁表進行。采用聯想存儲器和主存中頁表相結合的分頁地址變換過程如圖所示。2024/11/475頁式存儲管理頁表始址寄存器a+ba+pa塊號聯想存儲器不匹配時所有頁表在主存中PWpbbw分頁機構物理地址聯想存儲器2024/11/476頁式存儲管理2024/11/477頁式存儲管理引入快表后的地址變換過程：CPU給出邏輯地址后，地址變換機構自動將頁號與聯想存儲器中所有頁號并行比較，有匹配頁號，表示要訪問的頁表項在聯想存儲器中，取出該頁對應塊號與頁內地址拼接形成物理地址。若聯想存儲器中所有頁號與查找頁號不匹配，還需訪問主存中的頁表。查找同時進行，一旦在聯想存儲器中發現要查找的頁號，立即停止內存中頁表查找。若地址變換在查找內存中頁表完成，應將這次查到的頁表項存入聯想存儲器；若聯想存儲器已滿，須按某種原則淘汰一個表項以騰出位置。這種方案只要用8～16個表項的聯想存儲器，即可從聯想存儲器中找到所需頁號的概率達到90%左右。2024/11/478頁式存儲管理兩級和多級頁表：兩級頁表：針對難以找到大的存儲空間以存放頁表的問題，可利用頁表進行分頁的辦法，使每個頁面的大小與內存物理塊的大小相同，并為它們編號。可以離散地將各個頁面分別放在不同的物理塊中，同樣為每個離散的頁面建立一張頁表，稱為外層頁表。在每個頁表項中記錄物理塊號。如下圖所示。2024/11/479頁式存儲管理10230121640121141151023第0頁表第1頁表第n頁表012n101110781742外部頁表01214681023012345671141151468………內存空間分頁地址變換2024/11/480頁式存儲管理由圖可以看出，在頁表的每個表項中存放的是進程的某頁在內存中的物理塊號，如第0#頁存放在1號物理塊中，1#頁存放在4#物理塊中。而在外層頁表的每個頁表項中，所存放的是某頁表分頁的首址。如0#頁表存放在第1011#物理塊中。可以利用外層頁表和頁表這兩級頁表，來實現從進程的邏輯地址到內存地址的變換。2024/11/481頁式存儲管理外部頁表寄存器外部頁號外部頁內地址頁內地址p1p2d++bd外部頁表頁表物理地址具有兩級頁表的地址變換機構2024/11/482頁式存儲管理為了地址變換實現，在地址機構中同樣需要設置一個外層頁表寄存器，用于存放外層頁表的始址。并利用邏輯地址的外層頁號，作為外層頁表的索引。從中找到指定頁表分頁的首址。再利用P2作為指定頁表分頁的索引，找到指定的頁表項。其中即含有該頁在內存中的物理塊號。用該塊號和頁內地址d即可構成訪問內存的物理地址。上圖即為兩級頁表的地址變換機構。2024/11/483頁式存儲管理多級頁表結構：對于32位的機器，采用兩級頁表的結構是合適的。但對于64位的機器，對于二級頁表是否合適，需要簡單的分析。如果頁面大小仍采用4KB即212B,那么還剩52位，假定仍按物理塊的大小（210位）來劃分頁表，則將所有剩余的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，即使按220位來劃分頁表。此時，每個頁表分頁將達1MB;外層頁表仍有4G個頁表項。要占用16GB的連續內存空間。可見，不論怎樣劃分，其結果都是不能接受的。2024/11/4844.頁的共享與保護多道程序系統中，數據共享是重要的。頁式管理系統中，實現共享的方法是使共享用戶地址空間中的頁指向相同的塊號。頁式存儲管理2024/11/4854.頁的共享與保護頁式管理系統中實現共享比段式管理系統困難。原因：頁式系統將進程的地址空間劃分成頁面對用戶透明，同時，進程的地址空間是線性連續的。當系統將進程的地址空間分成大小相同的頁面時，被共享的部分不一定被包含在一個完整的頁面中。使不應共享的數據也被共享了，不利于保密。各進程的地址空間被劃分成頁的過程中，共享部分的起始單元在各自頁面中的頁內地址不同，共享比較困難。頁式存儲管理2024/11/486頁式存儲管理頁式管理可以為內存提供兩種保護方式：地址越界保護：由地址變換機構中頁表長度的值和要訪問的邏輯地址相比較完成；通過頁表中的訪問控制信息對內存信息提供保護。例如：在頁表中設置一個存取控制字段，根據頁面使用情況將該字段定義為讀、寫、執行等權限。地址變換時，不僅從頁表相應表項得到該頁對應塊號，還檢查本次操作與存取控制字段允許的操作是否相符，若不相符，由硬件捕獲并發出保護性中斷。2024/11/487頁式存儲管理5.頁式存儲管理系統的特點：不要求進程的程序和數據段在內存中連續存放，有效地解決碎片問題；要求硬件支持，增加了成本；消除了碎片，但每個進程最后一頁內總有部分空間得不到利用。進程的地址空間仍受主存實際容量的限制。返回2024/11/488從固定分區到可變分區，再到分頁系統，主要為了提高內存利用率。各種存儲管理方式都是提供線性連續的地址空間，通常，一個程序由多個程序段和數據段組成，編譯鏈接程序按一維線性地址排列，給程序及數據共享帶來困難。段式存儲管理方式能較好解決，還能實現分段保護和動態鏈接。5.3.2段式存儲管理2024/11/4895.3.2段式存儲管理段的概念：在分頁存儲管理中，雖然將用戶作業分頁，但是提供給用戶作業使用的邏輯地址都是一維線性地址。這與物理內存的地址形式是相同的，但與程序的邏輯結構卻大不相同。通常，用戶在實際問題的處理中，往往出現模塊化程序，例如一個程序往往有一個主程序段、若干子程序段、若干數據段和工作區段所組成，它們基本上是以段為單位出現，每個段具有完整的邏輯意義。為了與程序的這種邏輯結構相適應，提出了將程序邏輯地址空間按模塊分段組織管理的思想，即分段存儲管理。分段存儲管理以段為單位來管理內存，能更有效地利用內存，并且便于用戶使用。2024/11/4905.3.2段式存儲管理段的概念：在分段存儲管理中，每個作業的地址空間都按照作業本身的內在邏輯，劃分成若干段，即每個段是一組邏輯上完整的程序或數據。每一個段有一個名字，即段名。段名通常由用戶給出。作業程序經編譯連接后，段名轉換為段號。段號與段號之間無先后順序關系，例如可把一個作業劃分為四個段：主程序段、子程序段、數據段、工作區段。每段是一個首地址為零、連續的線性地址空間，并可根據需要而動態增長。對作業地址空間的訪問既要給出段名，還要給出段內地址。2024/11/4915.3.2段式存儲管理段的概念：每個作業的邏輯地址空間是二維的，邏輯地址包含兩部分：段號S和段內地址W。舉例：Call[X]|<Y>#轉向段名為X的子程序入口點Y。Load1，[A]|6#將段名為A的數組中第6個元素值讀到寄存器1中Store1，[B]|<C>#將寄存器1的值存入段名B段內地址為C的單元中以上指令中的段名X、A、B以及入口名Y、段內地址符號C等經編譯程序和連接程序編譯連接后轉換為機器內部可識別的段號和段內單元號。例如如果[X]對應的段號為3，<Y>對應的段內單元地址為50的話，CALL[X]|<Y>可被編譯成CALL3|<50>。2024/11/4925.3.2段式存儲管理段的概念：段式管理的基本原理：在分段存儲管理中，內存分配的單位是段。每段分配一個連續的內存區域，而各段之間可以分配不連續的內存區域。由于段的長度是不同的，所以分配給每個段的內存區域的長度是不同的。在分段存儲管理方式中，每段分配一個連續的內存區域，由于各段長度不同，這些區域的大小也就不一。因此，對于段的內存的管理采用可變式分區內存管理的方式，分配與釋放算法與可變式分區的內存分配與釋放算法相同。2024/11/4931.段式存儲管理的實現思想：段的概念：具有完整的邏輯意義的程序的單位。進程地址空間由若干個邏輯分段組成，每個分段是一組邏輯意義完整的信息集合，每段都有名字，每段都是首地址為0的連續一維地址空間。整個進程的地址空間是二維的。圖5-8：分段地址空間示例。基本原理：在分段存儲管理中，內存分配的單位是段。每段分配一個連續的內存區域，而各段之間可以分配不連續的內存區域。段式存儲管理以段為單位分配內存，每段分配一個連續內存區，各段之間不要求連續。內存的分配與回收類似于動態分區分配。5.3.2段式存儲管理2024/11/494圖5-8分段地址空間5.3.2段式存儲管理2024/11/495段式存儲管理系統中，進程地址空間二維。地址結構包括段號和段內位移兩部分，形式：段號S從0開始的連續正整數。段號長度和段內位移長度確定后，一個進程地址空間允許的最大段數和各段的長度確定。例：段號長度為8，段內位移的長度為16，一個進程最多可有256段，最大段長為64K字節。段式存儲管理以段為單位分配內存，每段分配一個連續的內存區域。各段長度不等，這些存儲區大小也不相等，同一進程包含的各段之間不要求連續。段號S段內位移W23161505.3.2段式存儲管理段號s段內偏移量w01516322024/11/496段表：段表：每個作業一張，基本內容包括段號、段長和段的內存起始地址。與頁式存儲管理類似，為實現邏輯地址到物理地址變換，系統為每個進程建立一個段表，每個表項描述一個分段信息，至少應包括段號、段長和該段的主存起始地址。地址變換：利用段表實現動態重定位。5.3.2段式存儲管理2024/11/4972.地址變換過程：為實現從進程邏輯地址到物理地址的轉換，設置段表寄存器，存放段表起始地址和段表長度。地址變換時，將邏輯地址中段號與段表長度比較，若段號超過段表長度，段號超界，產生越界中斷信號；若未越界，根據段表起始地址和段號計算對應段表項位置，讀出該段在內存中的起始地址，再檢查段內地址是否超過段長，若超過，發出越界中斷信號；若未越界，將段的起始地址與段內位移相加，得到物理地址。為提高內存訪問速度，可以用快表。圖5-9：段式系統的地址變換過程。5.3.2段式存儲管理2024/11/4985.3.2段式存儲管理段式方式地址變換示例：D的段內偏移100段的起始地址5460加段內偏移100=5460+100=5560得到12342024/11/4995.3.2段式存儲管理段式地址變換過程舉例說明：某作業經過編譯連接后，其MAIN段、X段、A段、B段的段號分別是0、1、2、3，A段的單元<D>的段內地址是100。在圖中，給出了該作業的段表的結構以及該作業的各段在內存中的存放情況。現在該作業被調度到處理器運行，其段表起始地址和長度裝入段表控制寄存器。當運行到指令LOAD1，[A]|<D>時，需要進行地址變換以便訪問內存單元。（1）系統查找段表得到2號段（即A段）的起始地址是5460；（2）將該段的起始地址與段內地址相加，即5460+100=5560；（3）以物理地址5560去訪問內存單元，取得要得到的數據1234。以上通過段表實現地址變換的過程是借助硬件來自動完成的。與分頁管理類似，分段管理每訪問一次內存數據也需要兩次尋址，即對段表的訪問和對內存塊地址的訪問。2024/11/4100圖5-9段式系統的地址變換過程5.3.2段式存儲管理2024/11/41013.段的共享與保護段是按邏輯意義來劃分的，可以按名存取，所以，段式存儲管理可以方便的實現內存的信息共享，并進行有效的內存保護。段的共享：段式系統中實現分段共享的方法：兩個進程段表中相應表項都指向被共享過程的同一個物理副本。段的共享是指量各以上的作業，使用同一個子程序，在內存中只包含一個副本。具體的操作是在每個進程的段表中，用相應的表項指向共享段在內存中的起始地址即可。當用戶進程或作業需要共享內存中某段的程序或數據時，則只要用戶使用相同的名字，就可以在新的段表中填入已存在段的內存起始地址，并設置一定的訪問權限，從而實現段的共享。當共享此段的某進程不再需要它時，應將該段釋放，取消在該進程中共享段所對應的表項。多道程序下，必須注意共享段中信息的保護。一個進程正從共享段中讀取數據時，必須防止另一個進程修改該段中數據。多數共享系統中，程序分成過程區和數據區。不能修改的過程稱為純過程或可重入過程，可以和不能修改的數據共享，可修改的程序和數據不能共享。5.3.2段式存儲管理2024/11/41025.3.2段式存儲管理段1操作系統進程2的空間進程1的空間段2段n進程1的段表共享段段1段2段n進程2的段表共享段分段系統中段的共享2024/11/41033.段的共享與保護段的保護：在分段系統中，由于每個分段在邏輯上是獨立的，因而比較容易實現信息保護。段的保護是為了實現段的共享和保證作業正常運行的一種措施。段式管理主要有兩種保護方法：地址越界保護法，存取控制保護法。地址越界保護法：段表寄存器中段表長度與邏輯地址中段號比較，段號超界產生越界中斷；再用段表項中段長與邏輯地址中段內位移比較，段內位移大于段長，產生越界中斷。在允許段動態增長系統中，允許段內位移大于段長。段表中應設置相應的增補位，以指示該段是否允許動態增長。段的存取控制：5.3.2段式存儲管理2024/11/41044.段式管理的特點：與頁式管理和分區管理相比，段長可根據需要動態增長，便于對具有完整邏輯功能的信息段共享，便于實現動態鏈接。每個分段是一組有意義的信息或具有獨立功能的程序段，段的地址空間二維，可以在進程運行過程中調用一個程序段或數據段時再進行鏈接。比其他幾種方式要求更多硬件支持，提高硬件成本。在內存空閑區管理方式上與分區式管理相同，存在碎片問題。每段長度受內存可用空閑區大小的限制。5.3.2段式存儲管理2024/11/41055.分頁和分段的主要區別：分頁和分段存儲管理系統雖然有很多地方相似，（1）頁是信息的物理單位，分頁是為了實現離散分配，提高內存利用率，便于系統管理；而段是信息的邏輯單位，每一段在邏輯上是相對完整的一組信息，如一個函數，一個過程，一個數組，分段是為了滿足用戶的需要。（2）分頁式存儲管理的作業的地址空間是一維的，地址從0開始編號一直到末尾，而分段式存儲管理作業地址空間是二維的，要識別一個地址，除給了段內地址外，還必須給出段號。（3）頁的長度由系統決定，是等長的。而段的長度是由具有相對完整意義上的信息長度決定。返回5.3.2段式存儲管理2024/11/4106段頁式存儲管理基本概念：段頁式存儲管理方便使用又提高了內存利用率，是目前用的較多的一種存儲管理方式。它主要涉及到以下的概念：（1）等分內存。它把內存分成大小相等的內存快，稱之為頁。（2）作業或進程的空間。采用分段方式，按程序的邏輯關系把進程的地址空間分成若干段，每一段都又一個段名。（3）段內分頁。按照內存的大小將各個段分成若干頁。每段從0開始依次編以連續的頁號。（4）內存分配。內存以頁為單位分配給每個進程。2024/11/4107頁式系統能有效提高內存利用率，段式系統能反映程序的邏輯結構并有利于段的共享。兩種存儲管理方式結合起來，形成段頁式存儲管理方式。段頁式存儲管理系統中，進程地址空間先分成若干個邏輯分段，每段有段號；將每一段分成若干大小固定的頁。主存空間管理與頁式管理一樣，分成若干個和頁面大小相同的存儲塊，對主存的分配以存儲塊為單位。進程的地址結構包含三部分：段號、頁號及頁內位移。其結構如下所示：段頁式存儲管理

段號s頁號p頁內位移d2024/11/4108對于三部分組成的虛地址，程序員可見段號s和段內位移w。地址變換機構將段內位移w的高幾位解釋為頁號p，剩下低位解釋為頁內位移d。為實現地址變換，設立段表和頁表。每個進程建立一張段表，每個分段一張頁表。段表表項至少包括段號、頁表始址和頁表長度。其中，頁表始址指出該段頁表在主存中的起始地址，頁表表項至少包括頁號和塊號。還有一個段表寄存器，指出進程的段表起始地址和段表長度。段頁式存儲管理2024/11/4109地址變換時，先將段號s與段表寄存器的段長比較，小于段長表示未越界，利用表始地址和段號求出該段對應段表項位置，從中得到該段頁表始址，利用邏輯地址中段內頁號p獲得對應頁表項的位置，讀出該頁所在物理塊號，與頁內地址拼接成物理地址。從地址變換過程可見，若段表和頁表全部放在主存中，訪問主存的一條指令或數據，至少需要訪問主存三次。為提高訪問內存速度，應考慮使用聯想寄存器。返回段頁式存儲管理2024/11/4110段頁式存儲管理段表、頁表和段表地址寄存器：為了實現從邏輯地址到物理地址的轉換，系統要為每個進程或作業建立一張段表，并且還要為該作業中的每一段建立一個頁表。這樣，作業段表的內容是頁表長度和頁表地址，為了指出運行作業的段表地址，系統有一個段表地址寄存器，它指出作業的段表長度和段表起始地址。下圖給出了段表、頁表和內存的關系。2024/11/4111段頁式存儲管理段號頁表長度頁表始址01222段表段號頁號其他頁面010段頁表頁號其他頁面011段頁表段號始址內存空間段表地址寄存器利用段表和頁表實現地址映射2024/11/4112段頁式存儲管理在段頁式存儲管理系統中：面向物理實現的地址空間是頁式劃分的；而面向用戶的地址空間是段式劃分的；也就是說，用戶程序被邏輯劃分為若干段，每段又劃分成若干頁面，內存劃分成對應大小的塊，進程映像是以頁為單位進行的，從而使邏輯上連續的段存入在分散內存塊中。2024/11/4113段頁式存儲管理地址轉換：在段頁式系統中，一個程序首先被分成若干程序段，每一段賦予不同的分段標識符，然后，將每一段又分成若干個固定大小的頁面。段頁式系統中地址轉換過程如下圖所示。2024/11/4114段頁式存儲管理3段表始址段表長度頁內地址頁號p段號s段超長+>+頁表長度頁表始址0123段表b0213塊號b塊內地址頁表段表寄存器段頁式系統中的地址轉換機構2024/11/4115段頁式存儲管理段頁式系統中的地址轉換過程大致如下：（1）首先利用段號s，將它與段長TL進行比較，若s<TL，表示未越界。于是地址轉換硬件將段表地址寄存器的內容和邏輯地址中的段號相加，得到訪問該作業段表的入口地址。（2）將段表中的頁表長度與邏輯地址中頁號p進行比較，如果頁號p大于頁表長度，則發生中斷，否則正常進行。（3）將該段的頁表基地址與頁號p相加，得到訪問段s的頁表和第p頁的入口地址。2024/11/4116段頁式存儲管理段頁式系統中的地址轉換過程大致如下：（4）從該頁表的對應的表項中讀出該頁所在的物理塊號f,再用塊號f和頁內地址d組成訪問地址。（5）如果對應的頁不在內存，則發生缺頁中斷，系統進行缺頁中斷處理，如果該段的頁表不在內存中，則發生缺段中斷，然后由系統為該段再內存建立頁表。2024/11/4117系統運行中經常出現：有的進程很大，要求內存空間超過內存總容量，進程不能全部被裝入內存，該進程無法投入運行。原因：內存容量不夠大。解決方法：物理上增加內存容量增加成本，受到限制；邏輯上擴充內存容量虛擬存儲技術。5.4虛擬存儲器2024/11/4118局部性原理早在1968年P.Denning就指出過，程序在執行時，將呈現出局部性規律，即在很短的時間內，程序的執行僅限于某個部分，相應的，它所訪問的存儲空間僅限于某個區域。他提出以下幾個論點：（1）程序在執行時，除少部分的轉移和過程調用外。大多數順序執行。（2）過程調用將會使程序的執行軌跡從一部分區域轉到另一部分區域。程序將在一段時間內在這些過程內運行。（3）程序中存在許多循環結構，它們有少數指令組成，但多次執行。（4）中還包括許多對對數據結構的處理。但對數組進行操作，往往局限于很小的范圍。局限性又表現在：（1）時間的局限性。即程序中某條指令一旦執行，不久又可能執行。某個數據結構被訪問不久又可能被訪問。（2）空間的局限性。一旦某個存儲單元被訪問，在不久后很快又會被訪問。5.4虛擬存儲器2024/11/4119應用：基于程序局部性原理（程序執行時，較短時間內的執行僅局限于某個部分），允許只將當前運行部分程序和數據先裝入內存運行，其余部分仍駐留外存，需要時再調入內存，可使進程順序運行。用戶角度：系統具有比實際內存容量大得多的存儲器虛擬存儲器。5.4虛擬存儲器2024/11/4120虛擬存儲器：具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的存儲器系統。用戶看到的大容量只是一種感覺，虛的；實際上，邏輯容量不能超過外存容量，容量大小受輔存容量的限制，也受到地址結構的限制。

5.4虛擬存儲器2024/11/4121知識點：

請求頁式存儲管理

請求段式存儲管理

返回5.4虛擬存儲器2024/11/4122請求頁式存儲管理頁式存儲管理方式可解決內存碎片，要求將進程的所有頁面一次調入主存，主存可用空間不足或進程太大時，會限制一些進程進入主存運行。1.請求頁式存儲管理的實現思想在進程地址空間的分頁、存儲空間的分塊等概念上和頁式存儲管理完全一樣。區別：進程運行前，不需要整個進程的地址空間全部裝入內存，只將進程一部分頁面裝入主存即可運行。執行過程中，當所需頁面不在主存時再調入。提供一個比存儲空間大得多的地址空間。2024/11/4123進程運行前不要求將整個地址空間調入主存，進程運行過程中必然出現要訪問頁不在主存。如何發現和處理，是請求頁式存儲管理必須解決的基本問題。為記錄頁面在主存中狀態，擴充頁表表項，增加：狀態位、訪問字段、修改位和外存地址。頁在內存時，地址變換過程與頁式存儲管理相同；頁不在內存，先將該頁調入內存，再進行地址變換。狀態位標識該頁是否在主存中，訪問字段記錄本頁在一段時間內被訪問次數或最近已有多長時間未被訪問，修改位表示該頁調入內存后是否被修改過，外存地址指出該頁在外存上的地址。訪問字段和修改位為頁面置換而設置。為進行存儲保護，還可以增加一個存取控制字段。請求頁式存儲管理2024/11/4124請求頁式存儲管理在請求分頁系統中，頁表項包括下列信息：頁號物理塊號狀態位P訪問字段A修改位M外存地址2024/11/4125發現被訪問的頁不在主存時，產生缺頁中斷信號，用戶程序被中斷，控制轉到操作系統的調頁程序。調頁程序根據該頁在外存的地址調入主存。新調進頁在主存有空閑存儲塊情況下，只要裝入任何一個空閑存儲塊中，再把塊號填入頁表中相應表項，改變狀態位為在內存即可。需要調進新頁時，若主存中已無空閑存儲塊，必須先淘汰主存中的某一頁；若被淘汰的頁在主存中被修改過，要將其寫回輔存。請求頁式存儲管理2024/11/41262.頁面置換算法（置換算法）用來確定應該淘汰哪一頁。算法優劣直接影響系統效率，算法不合適，可能出現抖動或顛簸現象。即：剛淘汰的頁，不久又再次訪問而再次調入，調入后不久又再次被淘汰，然后又訪問，如此反復，系統大部分時間用在頁面調進調出。常用的置換算法：⑴最佳置換算法⑵先進先出（FIFO）置換算法⑶最近最久未使用（LRU）算法及其近似算法請求頁式存儲管理2024/11/4127⑴最佳置換算法最佳置換算法是一種理論上的理想算法。采用最佳置換算法可以保證最低的缺頁率。從主存中移出永遠不再需要的頁面，若無，選擇最長時間不需要訪問的頁面淘汰。頁面訪問的未來順序無法知道，不是一種實際的算法，但可與其他實用方法比較，評價優劣。最佳置換算法具有理論上的意義。請求頁式存儲管理2024/11/4128請求頁式存儲管理例：已知頁面走向為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系統為該作業分配三個內存塊。求頁面淘汰順序。頁面置換過程如圖所示。03170043022321201701770701243203201701201203利用最佳頁面置換算法時的置換圖2024/11/4129⑵先進先出（FIFO）置換算法考慮到最早調入主存中的頁不再被使用的可能性大一些，選擇在主存中駐留時間最長的頁淘汰，即先進入主存的頁先退出。算法實現較簡單，適合按線性順序訪問的程序，其他情況效率不高。某些情況會出現分配給進程的頁面數增多，缺頁次數反而增加的現象，稱Belady現象。請求頁式存儲管理2024/11/4130請求頁式存儲管理下例中，設某進程的最大頁面數為3，則對于所示頁面的走向，其頁面失效的次數為15，頁面失效率為3/4。FIFO置換算法是易于理解和實行的。實行時，只要建立一個FIFO隊列，并規定最新進入的頁面總排在隊列最前，而當需要置換時，總是把當前隊尾的那個頁面換掉。2024/11/4131請求頁式存儲管理然而，FIFO算法有可能產生異常現象。所謂異常，是指在相同的頁面走向下當分給某一進程的頁面數增多時，頁面失效不但不降，反而增加這種情況。頁面走向70120304230321201701頁面置換770701201231230403701702712012013023423420頁面置換算法2024/11/4132⑶最近最久未使用（LRU）算法及其近似算法選擇最近一段時間內最長時間沒有被訪問的頁淘汰。主要出發點：如果某頁被訪問，可能馬上還要被訪問。反過來，如果某頁很長時間未訪問，在最近一段時間內不會被訪問。請求頁式存儲管理2024/11/4133請求頁式存儲管理該算法在出現缺頁中斷時，總是選擇最近一段時間內，最長時間沒有被訪問過的頁面，將它喚出外存。假定現有一進程所訪問頁面的頁號序列為：4，7，0，7，1，0，1，2，1，2，6。隨著進程的訪問，棧中頁面號的變化情況如圖所示，當訪問頁面6時，發生缺頁，此時頁面4是最近最久未被訪問的頁，應將它置換出內存。頁面置換情況如下圖所示：2024/11/4134請求頁式存儲管理假定現有一進程所訪問頁面的頁號序列為：4，7，0，7，1，0，1，2，1，2，6。隨著進程的訪問，棧中頁面號的變化情況如圖所示，當訪問頁面6時，發生缺頁，此時頁面4是最近最久未被訪問的頁，應將它置換出內存。頁面置換情況如下圖所示：44444444447707071700171107072120712621070用棧保存當前使用頁面時棧的變化情況2024/11/4135必須為每一頁設置一個特定單元，記錄上次訪問以來經歷的時間t，需要置換頁時，選擇t值最大的頁淘汰。要求對每一頁的訪問情況不斷記錄和更新。用軟件實現，增加系統開銷；用硬件實現，增加硬件成本。完全實現算法十分困難。實際采用LRU的近似算法。較常用的LRU近似算法：選擇最近一段時間內未被訪問的頁淘汰。近似算法實現時，每個存儲塊設置一個引用位。某塊中的頁面被訪問時，引用位置為1，頁面管理軟件周期性將所有引用位重新置為0。一個周期內被訪問過的頁，引用位為1，未被訪問的頁，引用位為0。根據引用位的狀態判斷各頁最近使用情況，置換時，選擇引用位為0的頁淘汰。請求頁式存儲管理2024/11/41363.請求頁式存儲管理方法的特點主要優點：提供內存與外存統一管理的虛擬存儲實現方案，可利用存儲空間增加，既提高了主存的利用率，又有利于組織多道程序的執行。主要缺點：要求硬件支持，增加成本（如動態地址變換機構、快表、缺頁中斷的產生等，要求硬件支持）；增加系統開銷（如頁表的建立與管理、缺頁中斷處理等）；頁面淘汰算法如選擇不當，可能產生抖動現象。返回請求頁式存儲管理2024/11/41371.請求段式存儲管理的實現思想與請求頁式存儲管理系統一樣，提供一個比主存可用空間大得多的虛擬存儲器，實際容量由計算機地址結構確定。程序運行前，進程各分段副本保存在外存中。程序運行時，先把當前需要的若干段調入主存即可啟動運行。當訪問的段不在內存中時，請求系統將所缺的段調入內存。請求段式存儲管理2024/11/41381.請求段式存儲管理的實現思想段表表項擴充，擴充后段表包括：段名、段長、內存始址、存取方式、訪問位、修改位、存在位、增補位和外存地址等。段號、段長和內存始址三個信息是進行地址變換必需的；存取方式：標識分段的存取屬性是可執行、只讀還是允許讀寫；訪問位：記錄該段一段時間內被訪問次數或最近已有多長時間未被訪問；修改位：標識該段進入內存后是否被修改過，供置換時參考；存在位：指示該段是否已調入內存；增補位：請求段式管理中特有字段，表示該段在運行過程中是否做過動態增長；外存地址：該段在外存中的起始地址，即起始盤塊號。請求段式存儲管理2024/11/4139請求段式存儲管理請求段式存儲管理中，用的主要數據結構是段表。段表結構如下：段名段長段的基址存取方式訪問位A修改位