研究三方面的問題：

取（fetch）

放（placement）

替換（replacement）請調、預調連續、非連續第六章存儲器管理第六章存儲器管理6.1主存管理功能6.2程序的裝入和鏈接6.3連續分配主存管理方式6.4覆蓋和對換技術6.5分頁存儲器管理方式6.6分段存儲管理方式6.7段頁式存儲管理方式主存分配地址轉換和重定位存儲保護和主存共享存儲擴充（虛擬存儲技術）6.1主存管理功能6.2程序的裝入和鏈接

1.程序的裝入絕對裝入方式靜態重定位裝入方式動態運行時裝入方式源程序目標模塊裝入模塊編譯鏈接裝入內存圖示如下：JUMP1424LOAD22241024142422240LOAD1，250036510002500500010000LOAD1,125003651100012500015000絕對裝入方式靜態重定位裝入方式JUMP1424LOAD2224102414242224靜態重定位裝入：在裝入一個作業時，把作業中的指令地址和數據地址全部轉換成絕對地址。這種轉換工作是在作業開始前集中完成的，在作業執行過程中無需再進行地址轉換。所以稱為“靜態重定位”。（1）靜態鏈接2.程序的鏈接

程序的連接方式有三種：靜態鏈接、裝入時動態鏈接和運行時鏈接。CallB模塊B模塊C0L-10M-10N-1JSR“L”模塊B模塊C0L-1LL+M-1L+ML+M+N-1鏈接目標模塊裝入模塊如：CALLB

JSR”L”需要解決的問題：相對地址的修改；外部調用符號的變換（2）裝入時動態鏈接

目標模塊在裝入內存的過程中鏈接，即邊裝入邊鏈接。優點：便于修改和更新便于實現目標模塊的共享6.2程序的裝入和鏈接（3）運行時動態鏈接將某些目標模塊的鏈接延遲到運行該模塊時才進行。即采用部分裝入運行方式。優點：節省內存空間便于實現目標模塊的共享連續分配方式是指為一個用戶程序分配一個連續的內存空間。分為：單一連續分配、固定分區分配、動態分區分配和動態重定位分區分配四種方式。1.單一（單道）連續分配方式主存系統區用戶區6.3連續分配主存管理方式內存空間安排特點：任一時刻內存只有一道作業，該作業連續存放于內存中。只適合單用戶、單任務環境。操作系統用戶程序0aa+1n界地址寄存器6.3連續分配的主存管理方式界地址寄存器主存A>a?cputruefalse地址A終止程序運行越界檢查機構：用戶程序每訪問一次主存，越界檢查機構將訪問的地址與界地址寄存器中的值比較。若越界，則終止其執行。（1）分區劃分方法分區大小相等分區大小不相等2.（多道）固定分區分配管理方式分區號大小始地址狀態11530已分配23065未分配3100125已分配（2）分配方法

數據結構：存儲分塊表MBT（如下表）特點：分區數和分區大小固定。優點：簡單、易實現。缺點：存在內部碎片，主存利用率不高。上下界寄存器和地址檢查機構。當作業被調度運行時，作業在內存中的上下界地址寄存器限定的地址范圍內。每次內存訪問時，地址檢查機構作越界檢查。作業程序是絕對地址或靜態重定位裝入。CPU主存下界寄存器上界寄存器><TrueTrue地址AF F程序性中斷（3）地址訪問保護有兩種方式：基址寄存器、長度寄存器和動態地址轉換機構。當作業被調度運行時，將作業所占內存基址及長度送基址、長度寄存器，每次內存訪問時，先看訪問地址是否小于長度，然后+基址進行訪存。用戶程序代碼是可動態浮動的。CPU主存基地址寄存器長度寄存器<+True地址AF 程序性中斷所謂程序浮動是指程序可以隨機地從主存的一個區域移動到另一個區域，程序被移動后仍不影響它的執行。若作業執行時，被改變的有效區域依然能正確執行，則稱程序是可浮動的。（4）存儲碎片

OS12k4k3K內部碎片OS4k6k12k作業長度：5K、8K、12K外部碎片內部碎片：存在于一個存儲分區內，當內存某存儲區大于其存放作業空間而剩下的那部分存儲空間。

外部碎片：通常指一個暫時不能使用的存儲分區。當內存某存儲分區容不下要運行的作業時發生。3.可變分區多道管理技術（1）概念主存事先并未劃分成一個個分區，當作業進入主存時，按作業的實際大小建立和分配分區。（2）特點分區數可變分區大小不固定可能存在大小不等的外部碎片例：假設任一時間段內，內存中每一作業的運行時間相等。作業到來次序所需存儲量運行時間160102100533020470855015OS040256J1J2J3J4J53.可變分區多道管理技術（3）數據結構常用的數據結構有以下兩種：存儲分塊表空閑分區表或空閑分區鏈3.可變分區多道管理技術分區號大小始地址115K30K1040K253K3100K125K………空閑分區表分區號大小始地址514K30K924K65K642K100K………已使用分區表存儲分塊表（表的維護較困難，存在表格碎片）已使用分區表UBT（分區狀態為忙）空閑分區表FBT（分區狀態為可用）06K28k8K4k20K28k4k18k頭指針8KB20KB6KB18k已分配未分配空閑分區鏈（單向鏈）指向下一個分區的指針分區大小空閑分區鏈（雙向鏈）前向指針后向指針N+2N+2N個可用字節表示分區的大小00表示分區的狀態1）首次適應算法以空閑分區鏈為例，每次從鏈首開始順序查找，直到找到一個大小能滿足要求的空閑分區為止。（一般要求空閑分區鏈以某種順序鏈接，如地址遞增。）通常有三種分配算法：（4）存儲分配算法缺點：低地址端留下許多很小的、難以利用的空閑分區。運行一段時間后，使得查找的開銷增加。優點：內存的高地址端保留了較大的空間。首次適應算法的內存分配過程從空閑分區表的開始或空閑分區鏈的鏈首查找。置空閑分區號F=1空閑分區表（鏈）檢索完？F.size≥Xk?F.size-Xk≤size?F=F+1

從分區中劃出Xk大小的分區

修改空閑分區表和已使用分區表返回失敗返回noyes

將分區分配給請求的進程yesnoyesnosize為事先規定不再劃分的剩余分區的大小。當前進程申請一Xk大小的內存分區2）循環首次適應算法

設置查找指針，每次分配內存時，從查找指針開始查找空閑分區表或空閑分區鏈。優點：內存的空閑分區利用均勻（4）存儲分配算法3）最佳適應算法

將滿足需求的最小空閑分區分配給請求內存分配的進程。（一般要求空閑分區按由小到大的順序排列）缺點：將在內存中留下許多碎片(內部碎片)。4）最壞適應算法在所有未分配的分區中挑選最大的，且滿足作業主存要求的分區分配給當前作業。（4）存儲分配算法優點：能使分配后的剩余分區足夠大，內部碎片減少缺點：運行一段時間后，難以找到用戶程序需要的較大空閑分區。（5）基本操作主要的操作有：分配內存和回收內存。

1）分配內存選擇一種分配算法將滿足條件的內存分區分配給當前申請的進程。2）內存回收待回收的分區可能存在的情況有以下四種：回收區不與任何空閑分區鄰（如圖（1））回收區與插入點的前一個空閑分區相鄰（如圖（2））回收區與插入點的后一分區相鄰（如圖（3））回收區與插入點的前、后兩個分區同時相鄰（如圖（4））F1R作業作業R作業作業RF2F1RF2圖（1）圖（2）圖（3）圖（4）回收過程的流程圖：申請回收分區RSIZE=R的大小LOC=R的始址置R的狀態為空表目R與F2相鄰？R與F1相鄰？在空閑分區表中找一空表目該分區的大小=SIZE始址=LOC狀態=可用SIZE=SIZE+F2的大小R與F1相鄰？置F2的狀態為空表目F1的大小=F1的大小+SIZEF2的大小=SIZEF2的始址=LOC返回yesnoyesnonoyes（1）緊湊

通過移動的方法，把內存中分散的各個小的存儲分區拼湊成大存儲區的過程。4.動態重定位的可變分區分配OS用戶程序A用戶程序B用戶程序C用戶程序DOS用戶程序A用戶程序B用戶程序C用戶程序D緊湊緊湊后需要對移動了的數據和程序進行重定位。重定位：邏輯地址到物理地址的變換過程。（1）基本概念物理地址/絕對地址:指令或數據的主存地址。4.動態重定位的可變分區分配邏輯地址：指目標程序所限定地址集合中的地址。邏輯地址是相對于某個基準量（通常為零）編址時所使用的地址，因此，也稱相對地址。相對地址空間：是指相對地址的全體。也稱邏輯地址空間或用戶地址空間。0LOAD1，250036510002500500010000LOAD1,125003651100012500015000靜態重定位：在裝入一個作業時，由裝入鏈接程序在程序執行前進行的重定位，即把作業中的指令地址和數據地址全部轉換成絕對地址。靜態重定位是由重定位裝配程序完成，一般不支持程序浮動。

4.動態重定位的可變分區分配動態重定位：在裝入一個作業時，不進行地址轉換，而是直接把作業直接裝入到分配的主存區域中。在作業指令執行時，由硬件地址轉換機構將指令或數據的地址轉換成絕對地址。地址變換是在程序執行期間，隨著對每條指令或數據的訪問而進行。動態重定位的特點：動態重定位由硬件機構完成，硬件機構包括重定位寄存器和加法器。在程序執行的過程中進行邏輯地址到物理地址的轉換。目標程序可以在內存中移動且可以不連續。0LOAD1，250036510002500500010000LOAD1，12500365110001250015000重定位寄存器100002500+相對地址（絕對地址或物理地址）地址空間（相對地址或邏輯地址）（2）動態重定位的過程如下：重定位硬件（3）動態重定位分區分配算法

請求分配u.size分區檢查空閑分區表（鏈）找到≥u.size的空閑分區？按動態分區方式進行分配修改相關數據結構返回分區號和始址空閑分區總和≥u.size？進行緊湊修改相關數據結構失敗返回是否是否

6.4覆蓋和對換技術因內存空間小于作業的程序空間而引入覆蓋。將主存的用戶空間劃分成一個固定區和多個覆蓋區。主程序放固定區依次調用的子程序則放在同一個覆蓋區操作系統提供覆蓋系統調用函數，在轉子程序前調用1.覆蓋技術覆蓋（overlap）A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)操作系統固定區(4k)覆蓋區(6k)覆蓋區(10k)覆蓋技術是早期擴大內存容量的一種技術，并在單道連續存儲管理中使用。覆蓋順序和結構由程序員規定。基本思想：將處于等待狀態(等I/O)的進程或暫時不用的程序或數據從主存換出到輔存的對換區，把將要執行的進程移入主存。2.對換（交換）技術為了支持交換，必須在系統空間設立I/O緩沖區。6.4覆蓋和對換技術2.對換技術（1）對換的形式進程對換：即整體對換，以進程為對換單位，目標是提高主存的利用率。部分對換：包括頁面對換和分段對換，目的是支持虛擬存儲器系統。文件區：管理的目標是提高文件存儲空間的利用率。對換區：采用動態分區分配的管理方式，目的是提高交換速度。外存（2）對換空間的管理1）目標：提高換進、換出的速度。2）數據結構：對換區的空閑分區表（或鏈），每個表項應包括分區的首址和大小。（即開始盤塊號和盤塊數）3）對換區的分配和回收對換區的分配一般采用連續分配方式，與動態分區的內存分配與回收基本相同。2.對換技術（3）進程的換進與換出1）進程的換進從交換區中尋找處于“就緒”狀態且換出時間最長的進程換進。申請內存空間執行換入操作成功2.對換技術2）進程的換出選擇處于阻塞或掛起狀態且優先級最低的進程換出。（注：正在被共享的程序段或數據不能換出）申請對換區空間執行換出操作成功2.對換技術注意：對換技術沒有從邏輯上擴充主存空間給用戶使用（即不提供虛擬地址空間）！！6.5基本分頁存儲管理方式（不支持頁面對換功能）1.基本概念頁：將進程的邏輯地址空間分成若干大小相等的片，這樣的片稱為頁面，頁面從0開始連續編號，如0，1，2，……物理塊：將內存地址空間分成與頁面大小相同的存儲塊，稱之為物理塊或頁框，物理塊或頁框也從0開始連續編號，也稱頁幀。有效地址：也稱“虛擬地址”或“相對地址”，有效地址用一數對(p,d)表示，結構如下：回收：當進程結束時，系統回收它的所有物理頁幀入空閑隊列。分配：初始時，所有頁幀都在空閑隊列中，當用戶進程被創建時，系統按需要量從空閑隊列獲得相應數量的頁幀。2.動態地址轉換機構

因分頁存儲器管理方式中邏輯地址與物理地址之間失去自然聯系，故要通過頁表，并由硬件動態地址轉換機構將邏輯地址映射成物理地址才能正確訪存。6.5基本分頁存儲管理方式（不支持頁面對換功能）頁表：放在系統空間的頁表區，存儲邏輯頁與物理頁幀之間的對應關系。PCB表中有一指針指向頁表，即每一進程擁有一張頁表。18530498765432103210邏輯空間物理空間頁表頁號有效地址結構：6.5基本分頁存儲管理方式

邏輯地址=p(頁號)*頁面大小+d(頁內位移)

物理地址=f(頁幀號))*頁面大小+d(同上)p=線性邏輯地址/頁面大小；

d=線性邏輯地址-p*頁面大小。例如：頁面的大小為1KB，求邏輯地址4101的頁號和頁內位移。15141312111098665432100001000000000101得到頁號p=4，頁內位移d=56.5基本分頁存儲管理方式為了減少頁號和頁內位移的計算時間，一般規定頁面的大小為2的冪（與機器內部的二進制數的表示一致），且頁長在29~212之間，這樣可以根據頁面的長度方便地計算出頁號和頁內位移（獲取p和d的除、乘法通過移位就能實現）。頁號和頁內位移在機器指令的地址中各占幾位取決于頁的大小。頁號和頁內位移的分割由硬件完成。（1）基本地址變換機構3.地址變換頁表始址頁表長度p（3）d88d≤越界中斷有效地址物理地址+0123頁表寄存器頁表頁表寄存器PTR：存放頁表在內存的首地址和頁表的長度。頁表一般常駐內存問題：CPU在這樣的地址變換機構存取一個數據時，需要訪問內存幾次？快表：由一組高速緩沖寄存器組成，用來存放當前訪問過的頁表項，以減少地址轉換過程中的時間花費。快表的表目結構：系統中快表的表目一般有64~256個，快表的訪問速度比普通主存要高出一個數量級，以并行的方式查找快表中的各表目。

（2）帶有快表的地址變換機構頁號物理塊號進程號訪問權限如何用快表實現邏輯地址到物理地址的轉換？帶有快表的地址轉換過程(聯想存儲器可以看成是頁表的cache)PdN k-1 0fdn k-1 0P2f2P1f1......Pf......Pmfmf頁表始地+頁表聯想存儲器帶有快表的地址變換過程如下：CPU給出有效地址P是否在快表？讀出物理塊號查找頁表將新頁號寫入快表（若快表已滿需要進行置換）Pd讀出物理塊號P是否越界？否是否越界中斷是物理寄存器在進程被調度占用cpu時，將進程頁表始址裝入頁表地址寄存器。命中率：選用8-12項組成的聯想存儲器，并采用適當的替換策略，在聯想存儲器中匹配成功的可能性可達80-90%。等效訪問時間：設訪存時間為750ns，搜索聯想存儲器的時間為50ns，命中率為80%，則（這里假設先查聯想存儲器再查頁表）：

80%*（750+50）+20%*（750+50+750）

=950ns（2）帶有快表的地址變換機構4.可用空間管理可用bitmap數組或空閑頁幀鏈來管理可用頁幀。6.5基本分頁存儲管理方式5.共享與保護

通過頁表可以使幾個邏輯空間指向同一個物理空間，實現程序共享。

例：EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA3OSDATA1EDIT101234567891011EDIT2EDIT3DATA2DATA3P1 P2 P33461346734610頁表存儲保護越界保護：設置頁表長度寄存器，查頁表前，先檢查頁號是否越界。操作訪問保護：在每個頁表項中增設一存儲保護域，用于說明對該頁的訪問權限，每一個對該頁存儲的訪問都首先要比照是否滿足該頁訪問權限的說明，滿足則訪問，否則報錯。例：設為每一頁表項增加三位，R位表示讀權限，W位表示寫權限，E位表示執行權限。

R W E 0 0 0不可進行任何操作

0 0 1可以執行,不可以讀寫

0 1 0只可以寫

假設：有一個32位的分頁存儲器管理系統，頁面的大小規定為1KB，每個頁表項占4個字節，求頁表所占的最大內存空間？6.兩級頁表32位計算機系統的邏輯地址空間應是232，頁表長度為：232/210=222，則頁表所占的內存空間就是222×22=224個字節，即16MB。4.兩級頁表（1）原理：將頁表分成與內存物理塊大小相等的頁，在內存中采用離散方式存放；只把當前使用的那部分頁表項調入內存。（2）兩級頁表的邏輯結構外層頁表：將頁表進行分頁，并為其建立一張頁表。每個頁表分頁在外層頁表中占一表項，表項的內容為頁表頁在內存中對應的物理塊號。01…114115…10241025…

…………………01234...114…102410111068012…n第0號第n號第1號外層頁表（頁目錄）頁表01…頁表分頁外層頁號外層頁內地址頁內地址

（3）兩級頁表的地址變換1）邏輯地址結構2）地址變換過程外層頁號P1外層頁內地址P2頁內地址d外部頁表寄存器外層頁表頁表項塊號

d++外部頁表的始址物理寄存器P2P1例1：若在一個兩級頁表的存儲器管理系統中，某指令對應的有效地值為（1，10，253），頁面大小為1K,根據下表求該指令的物理地址。6113…2081號頁表分頁…11211205…1106…10第1205號物理塊第208號物理塊10511…AbdcIntx=20;dfgAsfsdagdhhgj253物理塊號為208，塊內位移為253物理地址=1024×208+253例2：已知某系統的頁面大小為4KB，每個頁表項大小占4B，現采用多層分頁策略映射64位有效地址空間。請問：若限定最高層頁表的大小占1頁，應采用幾層分頁策略？6層4.5分段存儲管理方式1.為什么要引入分段存儲管理方式分段共享和保護動態鏈接動態增長方便編程2.分段管理的基本原理將進程的地址空間劃分為若干個邏輯段，段的長度由邏輯信息本身的長度決定。每一段占一個連續內存分區。分段在編譯時由編譯程序完成。

3.分段管理的邏輯地址結構

段號段內位移

例：…CALL[X]|<Y>…LOAD1,[A]|6STORE1,[B]|C…分段MAIN…Y………C…分段X（子程序）分段A

（數據）分段B（工作區）15163104.分段管理的地址變換和數據結構

（1）段表

系統為每個進程建立一張段映射表，稱為段表。段長基地址30K40K20K80K15K120K……012…段號段表30K20K40K80K

15K120K內存段表放于系統空間，進程PCB表中存有段表始地址、段表長度。+（2）分段管理的地址變換機構段長基地址30K40K20K80K15K4K……

段號2段內位移量100段表始址段表長度012…段號+物理地址（4196）段表寄存器邏輯地址≤越界5.分頁與分段的比較頁是信息的物理單位；而段是信息的邏輯單位頁的大小固定；而段的大小是由它代表的邏輯信息來決定分頁管理的地址空間是一維的，而分段管理的地址空間是二維的4.5分段存儲管理方式6.分段管理的共享和保護（1）段的共享

對于那些被多個程序共享的段，在內存中只保留一個副本。副本采用可重入代碼。

4.5分段存儲管理方式可重入代碼：又稱“純代碼”，是一種允許多個進程同時訪問的代碼。可重入代碼在被訪問過程中不允許任何進程對其進行修改。段1段表1段2段n段1段2段n段表2……………內存進程1地址空間進程2地址空間共享段共享段分段共享的示意如下圖：（2）段的保護段式管理的保護方式主要有兩種：地址越界保護（上、下界寄存器或基址+限長寄存器）存儲保護鍵法（每個存儲塊分配一個單獨的保護鍵，每個進入系統的作業也賦予一保護鍵，相當于鑰匙。）存取控制4.5分段存儲管理方式4.6段頁式存儲管理方式1.基本原理首先，將用戶程序中所包含的具有獨立邏輯功能的程序或數據分成若干個段，并擁有各自的段號。然后再將每個段劃分成若干個頁，最后不足一頁的部分也占一頁。2.數據結構（1）段表（2）段頁表（3）段表寄存器三者的關系如下圖：

段表長度段表始址段號狀態頁表長度頁表始址01510241062056頁號狀態塊號0……頁號狀態塊號0…………………內存段表0號段頁表1號段頁表段表寄存器4.6段頁式