1、存儲器管理 盡管最近存儲器的容量在不斷擴大。但軟件的種類、功能等所需的空間也在急劇膨脹，存儲空間仍然是寶貴資源。 本章主要討論內存管理：內存分配、分頁存儲管理與分段存儲管理方法等。第5章5.1 程序的裝入和鏈接在多道程序的環境下，把一個用戶的源程序變成可以的內存執行的程序，需要如下步驟：編譯：通過編譯程序把用戶的源代碼編譯成若干個目標模塊(Object Module)。鏈接：把目標代碼和所需的庫函數連接起來形成可裝入的模塊(Load Module)。裝入：由裝入程序把裝入模塊裝入到內存。源代碼庫可裝入模塊目標模塊編譯鏈接裝入內存一、程序的裝入如果程序為多個模塊，則需要進行鏈接；單個目標模塊無須

2、進行鏈接。在Unix/Linux鏈接有多種方式。單模塊的裝入方式：絕對裝入方式：按模塊中的地址，將程序和數據裝入到內存對應位置。可重定位方式：在裝入程序時，根據當時內存的實際使用情況，重新調整裝入的內存位置，把程序裝入到內存的適當地方。1、Absolute Loading Mode(ALM)絕對裝入方式：在編譯時，已經知道程序要駐留在內存的位置，如地址1024開始，則編譯程序直接產生從該地址向上開展的目標代碼，目標代碼中全部采用絕對地址。Jump kLoad mkmJump 1424Load 2224142422241024匯編/編譯Jump 1424Load 2224142422241024

3、裝入2、Relocatable Loading Mode-RLMALM存在問題：多道程序環境下，無法預先知道程序的裝入位置。重定位裝入：在程序裝入時，把目標程序中的指令和數據的相對地址(有效地址)修改成裝入位置處內存的物理地址。靜態重定位：地址變換只是在裝入時一次性完成，以后不在改變。Jump kLoad mkmJump 400Load 120040012000匯編/編譯Jump 1400Load 2200140022001000作業空間內存空間裝入3、Dynamic Run-Time Loading可重定位裝入方式存在問題：雖然可以把程序裝入到內存的任意位置，但不允許程序在內存中移動位置。如

4、果程序在內存中移動，就必須對程序中的地址進行修改才能正常運行。動態運行時裝入程序：把裝入模塊裝入內存時，不把程序中的地址轉換成實際的物理地址，而是在運行時才進行地址轉換。Jump kLoad mkmJump 400Load 120040012000匯編編譯Jump 400Load 1200140022001000作業空間內存空間裝入4001000+1200運行時 二、程序的鏈接鏈接的主要功能：把經匯編、編譯所得到的一組目標模塊和所需的庫函數目標模塊一起，裝配成一個完整的裝入模塊。有三種鏈接方法：靜態鏈接裝入時動態鏈接運行時動態鏈接1、靜態鏈接將幾個模塊鏈接裝配成一個模塊需要解決兩個問題：修改相

5、對地址：編譯產生的目標模塊起始地址為0，除第一塊外，其余的相對地址全部要修改。模塊ACall BReturn模塊BCall CReturn模塊CReturn0L-10M-10N-1模塊AJSR “L”Return模塊BJSR “L+M”Return模塊CReturn0L-1LL+M-1L+ML+M+N-1變換外部調用符號：把外部調用符號變換成相對地址形成可執行文件。靜態鏈接：進行事先鏈接，以后不再拆開的鏈接方式。可執行文件2、裝入時動態鏈接優點：便于軟件的版本修改和更新：只要對需要修改的模塊修改后編譯即可，保證所有的軟件同步升級。便于實現目標模塊的共享：實現多個模塊共享一個模塊、而不要每個程序

6、都含有該模塊的拷貝。模塊ACall BReturn模塊BCall CReturn模塊CReturn模塊AJSR “L”Return模塊BJSR “L+M”Return模塊CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1裝入過程獨立目標模塊在內存中3、運行時動態鏈接裝入鏈接的問題：程序運行期間、整個模塊的結構不變靜態結構。在運行期間有些模塊(如錯誤處理)可能不用、但一直占據內存。運行時鏈接：在運行期間需要一個模塊才裝載一個模塊。模塊ACall BReturn模塊BCall CReturn模塊CReturn模塊AJSR “L”Return模塊BJSR “L+M”Ret

7、urn模塊CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1獨立目標模塊在內存中運行時裝入運行時裝入4、Linux的靜態和共享函數庫Linux生成目標代碼： gcc -c 源程序文件名將生成一個與源程序同名的.o目標代碼文件。直接用目標代碼文件生成可運行文件 gcc o可執行文件名 目標代碼文件 目標代碼文件 源程序文件生成一個可執行文件。Linux C有兩種風格的函數庫：靜態函數庫共享函數庫靜態函數庫的維護生成一個靜態函數庫ar r libtools.a m1.o m2.o m3.o ar -Linux的歸檔命令。r表示生成一個名字為libtools.a的靜態函數

8、庫。 如果該函數庫不存在，創建函數庫。 如果函數庫存在，庫中沒有指定的目標模塊，則把目標模塊追加到函數庫中；如果函數庫中有同名的目標模塊存在，替換成當前的目標模塊。注意：函數庫名一定是以“lib”開頭，后綴為“.a”ar 的其他參數： t顯示在函數庫中的所有目標模塊 tv顯示庫中目標模塊的詳細信息。使用自己的靜態函數庫使用自己創建的靜態函數庫：gcc -o可執行文件名 靜態函數庫名 源程序 目標模塊說明：在編譯、連接時把靜態函數庫作為一個參數加到命令行中即可。例如： gcc omax1 libtools.a m1.o m2.o m3.o 在鏈接時也可以使用如下參數：gcc -L函數庫位置 -l

9、函數庫名 源程序 目標模塊其中：-L 指出函數庫在什么路徑。如:-L.表示當前目錄。默認的路徑“/usr/lib”可以不給出。-l 給出函數庫名，但不要前綴和后綴。如:-ltools表示使用函數庫libtools.a使用自己的共享函數庫生成自己的共享函數庫：生成共享函數庫和生成一個程序一樣簡單。gcc m1.o m2.o mn.o shared -o共享函數庫名參數： -shared 要求gcc輸出生成一個共享函數庫 共享函數庫名前綴為“lib”，后綴為“.so”使用共享函數庫鏈接方法同上。如果在同一位置靜態函數庫和共享函數庫都可用，默認鏈接共享函數庫，要用靜態函數庫時使用鏈接參數“-stat

10、ic”。使用自己的共享函數庫檢查共享函數庫的使用ldd 可執行文件名例如：ldd mmm1 libttl.so = not found libc.so.6=/lib/linc.so.6(0 x40001c000) /lib/ld-linux.so.2=/lib/ld-linux.so.2(0 x4000000)這說明確實正在使用共享庫，但沒有找到。/lib/ld-linux.so.2幫助其它共享庫裝載/動態鏈接的動態裝載器。 指定動態裝載器的查找路徑方法：在文件“/etc/ld.so.conf”設定。在環境變量LD_LIBRARY_PASTH中設定。 在“/etc/ld.so.conf”設定要

11、求：具有root權限。步驟：用vi編輯/文件，把共享函數庫的路徑加入到該文件中。退回到系統根目錄運行/sbin/ldconfig,用文件/的內容更新緩存文件/etc/ld.so.cache(真正起作用的文件)。這時可以運行在共享庫在指定路徑的程序。注意：無論何時，任何一個配置目錄中的共享文件發生變化，都必須運行/sbin/ldconfig來更新緩存文件/etc/ld.so.cache。使用變量LD_LIBRARY_PATH如果沒有root權限，則可以使用LD_LIBRARY_PATH環境變量進行設置。設置：export LD_LIBRARY_PATH=“$LD_LIBRARY_PATH:.”可

12、以用set命令檢查以下該命令是否起作用。5.2 連續分配存儲管理方式連續分配存儲管理有兩種方式：單一連續分配方式：在內存中僅駐留一道程序，整個用戶區為一個用戶獨占。適用于：單用戶、單任務OS。分區式分配方式：可以分固定分區和動態分區。固定分區式：把內存用戶區劃分成若干個固定大小的區域，每個區域駐留一道程序。動態分區：根據用戶程序大小、動態地對內存進行劃分。特點：內存劃分成多少分區是可變的。一、單一連續分配方式內存劃分：系統區：僅給操作系統使用(可以放在低端或高端)，由于中斷向量駐留在低端、一般放在低端。用戶區：提供給用戶使用的區域。CPUsize劃出分區整塊分配修改有關數據NYNYNm.siz

13、e空閑分區大小u.size請求分區大小size不可在分割大小按分區分配算法內存的回收當一個進程運行結束，要釋放內存，操作回收內存，并把它插入到空閑區鏈表中。根據回收區的位置，有四種情況需要處理：空閑區回收區回收區空閑區空閑區回收區空閑區回收區情況1情況2情況3情況4四、動態重定位分區分配緊湊：把空閑區合并成一個連續區域。動態重定位：程序中的相對地址變換是在程序執行期間進行的。8K12K6K18K44K緊湊0Load 250010036525002500相對地址10000重定位寄存器10000Load 25001010036512500+處理機存儲器動態重定位分配算法原理：在動態分區分配算法中，

14、當找不到足夠大的空閑分區來滿足請求的空間時進行“緊湊”。請求分配分區檢索空閑分區鏈找到按動態分區分配方式進行分配空閑分區總和進行“緊湊”返回分區號及首址無法分配返回yNYN五、伙伴系統伙伴系統：內存的有效分區尺寸為2k,LkU；2L=最小的分區尺寸，2U=最大的分區尺寸1MBA：請求100K128KB：請求240K256K128KC：請求64K256K128K64KD：請求256K256K128K64K256K釋放A256K128K64K256K釋放D256K128K64KE：請求75K256K128K64K釋放C256K128K5.3 對換對換：把內存中暫時不能運行的進程或暫時不用的程序和數

15、據，換到外存，以騰出足夠的內存空間，把具備運行條件的進程或進程需要的程序和數據換到內存。進程對換：以整個進程為單位進行的對換分時系統。部分對換：以“頁”為單位的對換頁面對換；以“段”為單位的對換分段對換。兩者稱部分對換。進程對換時系統必備的功能：對換空間管理；進程的換出；進程的換入。1、對換空間的管理具有對換功能OS外存劃分：文件區和對換區。文件區：用于長期保存文件離散分配方式。目標提高存儲利用率。對換區：用于短時間存放內存換出的進程，要求較高的換進、換出速度采用連續分配。對換區管理的記錄方式：空閑分區表和空閑分區鏈與內存管理類似。以磁盤塊為單位。對換區的分配與回收與動態內存分配算法相同：Fi

16、rst Fit、Next Fit、Best Fit。2、進程的換出實質：把活動阻塞、就緒狀態的進程轉掛起狀態。 選擇被換出的進程實施換出換出進程考慮的因素：處于阻塞或睡眠狀態的、優先級最低的進程。無阻塞：選擇優先級低的就緒進程。考慮優先級低產生“換進、由換出”，兼顧在內存駐留時間。非共享的程序和數據段。如果是共享的，只能那些引用數-1后為零才能被換出。換出操作：申請對換空間，等申請成功繼續。把程序、數據寫入交換區，檢查寫入的正確性。釋放進程所占的內存空間。修改被換出的進程的控制塊、修改內存分配表。3、進程的換入實質：把掛起狀態-活動就緒或阻塞。進程換入考慮的因素：有足夠的內存空間“就緒掛起”優

17、先于“阻塞掛起”同一隊列中，優先級高、掛起時間長的優先換入。換入操作：多個進程依次換入。申請內存空間，如果申請成功繼續。把掛起進程換入。修改進程PCB和內存分配鏈(表)。如果內存申請失敗，首先實施進程換出。分頁、分段存儲管理方式內存分區管理存在問題：固定分區方式：將產生大量的內部“碎塊”；動態分區方式：將產生大量的外部“碎塊”，而進行“緊湊”則需要額外的開銷。思路：把用戶的程序空間劃分成若干塊，它們可以離散分配到內存中非連續的存儲區域中。充分利用內存。分類：按程序分塊的大小是否固定分為分頁存儲、分段存儲、段頁式存儲。5.4 分頁存儲管理方式實現方法：把用戶程序的地址空間劃分成若干固定大小的區域

18、(fixed size chunk)，把它們叫“頁”（一般1頁為1KB）。把內存空間劃分成若干和“頁”大小相同的物理塊，這些物理塊叫“頁框”(frame)。內存分配：把用戶程序的任一頁分配到內存中的任一幀，從而實現非連續的、離散的內存分配。問題：如何管理、如何進行地址變換。一、分頁存儲管理基本方法程序A0頁1頁2頁3頁4頁5頁n頁進程A頁表00頁號塊號1124354859012345678內存9程序B0頁1頁2頁3頁4頁5頁m頁進程B頁表02頁號塊號132637自由頁框表塊號頁表作用：實現頁號到物理塊號的映射。返回分頁存儲管理方式的地址結構地址組成：頁號P+(頁內地址)位移量d例如：32位地址

19、，011為位移量(4KB/頁)，1231為頁號，最大可以有1M頁。頁號P和頁內地址d的確定：設邏輯地址空間中的地址為A，頁面大小為L:P= INT A / L d= A mod L地址結構：頁號P位移量d12 11031頁面大小的確定分頁系統中，頁面的大小是有硬件的地址結構所決定的。機器確定、頁面大小便確定。影響因素：頁面內部碎塊、內存的利用率頁面頁表、占用內存頁面頁面的換出換入效率。計算機類型頁面大小(B)IBM AS/400VAXIntel 80386Motorola 6803051251240964096常見機型頁面二、地址變換機構分頁存儲系統中，地址變換機構的任務：把邏輯地址中的頁號轉

20、換為內存中物理塊的塊號。注意：頁面大小與頁框大小一致，無須進行頁內地址轉換。實現轉換：借助于頁表。頁表的實現：寄存器：變換速度快、成本高，適應小型系統。頁表駐留在內存：速度較低、成本低，適應大系統。頁表頁表駐留在內存的變換機構在系統中設置一個頁表寄存器(PTRpage table register)：存放頁表在 內存的起始地址和頁表的長度；非執行狀態該數據保存在進程的PCB中。頁表寄存器頁表始址頁表長度邏輯地址頁號=2頁內地址=12800頁號塊號112435+4內存頁表越界中斷物理地址128具有快表的地址變換機構頁表存放在內存時CPU存取數據，訪問兩次內存：第一次：訪問內存頁表，找到物理塊號+

21、頁內地址，形成物理地址。第二次：訪問內存，讀/寫數據。具有快表：在地址變換機構中增設一個具有并行查詢能力的特殊高速緩沖存儲器聯想存儲器/快表。工作原理：CPU給出有效地址；如果地址“快表”中，直接讀出對應的物理塊號，送往物理地址寄存器；再訪問內存。如果快表沒有對應的地址，從內存“頁表”讀取地址送往物理地址寄存器，訪問內存；把頁表項存入快表或把老的頁表項換出。不設聯想存儲器：訪問時間延長一倍。具有快表的地址變換機構（續）頁表寄存器頁表始址頁表長度邏輯地址頁號頁內地址00頁號塊號112435+4內存頁表(慢表)越界中斷物理地址頁號塊號24輸入寄存器快表三、兩級、多級頁表一級頁表存在問題：支持的邏輯

22、空間越大，頁表就越大，頁表所占用的內存空間就越大。如：設32位邏輯空間，頁面大小為212B，需要220個表項，每個表項4B，則需要4M的連續內存空間。從兩個方面解決：離散分配頁表；部分頁表駐留在外存：需要時調入內存。1、兩級頁表實質：把大的頁表再進行分頁存放，實現存放頁表的頁面離散存放。外部頁表：存放每個頁表的物理塊號。邏輯地址結構：p1p2d外層頁號外層頁內地址頁內地址3122 2112 110邏輯地址外部頁表寄存器+外部頁表+頁表物理地址101110781742012n外部頁表135211212240第0頁頁表第1頁頁表12111212第n頁頁表內存空間012012012012345211

23、21224012111212優點：可以把暫時不用的頁表存放在外存。但不能沒有減少存儲空間。2、多級頁表結構32位機器用兩級頁表結構合適。64位用兩級將產生非常大的外層頁表：如：頁面大小為212B,頁表大小為210項，則外部頁表：242項=4096G個表項。多級頁表實質：對大的外部頁表進行分頁分成若干級外部頁表，實現存放外部頁表的頁面離散存放。第一級第二級第三級頁內偏移量外部頁表寄存器PFNPFNPFNPFNPage Frame Number四、反置頁表(Inverted Page table)分頁系統中為每個進程配置一張頁表，進程的邏輯空間每一頁在頁表中一個表項頁表非常龐大。反置頁表：為每一物

24、理塊(頁框)分配一個表項，按物理塊號排序，表項的內容是頁號及所屬的進程標識符。反置頁表的優缺點：頁表的大小與物理空間有關。但只包含調入內存的頁面，沒有包括未調入內存的進程頁面。利用進程ID和頁號檢索很費時，要通過Hash表進行檢索。CPUpidpdiidd第i幀物理地址邏輯地址頁表反置頁表地址轉換過程物理幀號PID頁號外部頁表5.5 分段存儲管理分段存儲管理方式引入的目的：物理分頁邏輯分段。方便編程：用戶把作業分成若干邏輯段，每段有自己的名字和長度，邏輯地址由段名和段內偏移量決定。分段共享：分頁實現程序、函數困難。分段保護：便于對信息的邏輯單位進行保護。動態鏈接：動態鏈接是以段為單位調入內存。

25、動態增長：實際使用中，數據段的長度不能預先確定，需要動態增加。一、分段系統的基本原理分段：把作業的地址空間劃分若干段，每一定義一組邏輯信息：段名、段的長度。段名：用段號來替代。段的長度：由相應的邏輯信息組的(不等)長度決定。邏輯地址：Segment NumberOffset3116 15064K個段64KB長度段表：系統為每段分配一段連續區域，而進程中的各段則離散存放在不同的分區中。段表：記錄邏輯段與內存物理位置的對應映射關系。段號段長基址030K40K120K80K215K120K段表(MAIN)=0(x)=1(D)=2內存空間作業空間015K(MAIN)=007K(X)=108K(D)=2

26、40K80K120K段表還有：外存基址，狀態地址變換機構：段表始址段表長度段表寄存器2段號段內偏移量100+段號段長基址01K6K16004K25008K32009200段表+越界中斷+8292物理地址012內存空間8K為提高數據存取速度，減少內存訪問次數，分段存儲管理方式增設一個聯想存儲器。分頁與分段的區別分塊方式使用碎片長度目的分頁存儲管理物理分塊，系統決定對程序員是不可見，使用簡單每個進程只有一個內部碎片，大小不超過1頁固定提高內存的利用率分段存儲管理邏輯分塊，大小與信息塊有關，由編譯系統劃分對程序員可見，使用方便，但難度大每個進程有多個外部碎片不確定便于信息保護與共享，方便用戶二、共享

27、與保護可重入代碼：純代碼，允許多個進程同時訪問同一代碼，可重入代碼不允許用戶對代碼進行修改。分頁：(p161)實現代碼共享、保護比較困難。要求每個進程的每個頁表項都指向共享頁。分段：實現代碼共享、保護簡單。只要每個進程的段表項指向共享段就可以實現。三、段頁式存儲方式基本原理：先把用戶的程序分為若干個段，再把每個段劃分成若干頁。主程序段04K8K12K16K子程序段04K8K數據段04K8K12K段號段內頁號頁內地址邏輯地址：段頁式存儲管理的地址轉換:段號=3頁號=2d邏輯地址段表始址段表長度段表寄存器+越界中斷段號段長頁表始址頁表長度狀態0123頁號頁框號外存地址狀態012+物理地址段表頁表采用段頁式存儲管理方式,訪問數據需要三次訪存.5.6 Linux存儲管理Linux存儲管理的特點:“按需分頁”的段頁式存儲管理技術：運行時需要的內容按頁調入內存，不執行的內容仍然存放在交換區。高速緩存：緩沖區緩存(Buffer Cach