操作系統(tǒng)Windows和Linux存儲(chǔ)管理

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

頁式存儲(chǔ)管理

段式存儲(chǔ)管理

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

頁號(hào)P頁內(nèi)偏移W

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

0頁式存儲(chǔ)管理2024/11/464圖5-6頁表的作用頁式存儲(chǔ)管理2024/11/465含義：頁號(hào)：指定在頁表中的位置，頁號(hào)為幾即在頁表中的第幾個(gè)頁表項(xiàng)（加1）。即：用頁號(hào)索引頁表，可以得到這一頁在內(nèi)存中的物理塊號(hào)。頁內(nèi)偏移量：在頁內(nèi)的位置，因?yàn)轫撆c塊是一樣大，因此也代表在塊內(nèi)的位置，即：頁內(nèi)的相對(duì)位置與塊內(nèi)的相對(duì)位置是相同的。頁式存儲(chǔ)管理系統(tǒng)中的邏輯地址結(jié)構(gòu)如下：頁號(hào)P頁內(nèi)位移W1510

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

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

5.4虛擬存儲(chǔ)器2024/11/4121知識(shí)點(diǎn)：

請(qǐng)求頁式存儲(chǔ)管理

請(qǐng)求段式存儲(chǔ)管理

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