4.1

存儲器工作原理

4.2連續存儲空間管理4.3分頁式存儲管理4.4分段式存儲管理4.5虛擬存儲管理第四章存儲管理如何對存儲器加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統性能有重大影響。存儲器管理的主要對象是內存。存儲管理的功能:分配和去配、抽象和映射、隔離與共享、存儲擴充。4.1.1存儲器的層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質4.1

存儲器訪問速度往上越高容量越往下越大如何將一個用戶源程序變成一個可在內存中執行的程序，通常要經過3步驟：編譯:由編譯程序（Compiler）將用戶源代碼編譯成若個目標模塊（ObjectModule）。鏈接:由鏈接程序（Linker）將編譯后形成的一組目標模塊，以及它們所需要的庫函數鏈接在一起，形成一個完整的裝入模塊。裝入:由裝入程序（Loader）將裝入模塊裝入內存。-程序的裝入和鏈接4.1.2地址轉換與存儲保護編輯―――編譯―――鏈接―――裝入―――運行1.程序編譯源程序經過編譯程序或匯編程序的處理來獲得多個目標模塊處理時編譯程序負責記錄模塊內引用的發生位置目標模塊附有供引用使用的內部符號表和外部符號表符號表給出了各個符號名及在本目標模塊中的名字地址，在模塊被鏈接時進行轉換2.程序鏈接1)靜態鏈接:在程序裝入之前，先將各目標模塊及它們所需的庫函數，鏈接成一個完整的裝配模塊，以后不再拆開。2)裝入時動態鏈接:這是指將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。a.便于修改和更新b.便于實現對目標模塊的共享3)運行時動態鏈接:這是指對某些目標模塊的鏈接，是在程序執行中需要該(目標)模塊時，才對它進行的鏈接。模塊Aifx>1CALLB;elseCALLC;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標模塊模塊Aifx>1JSRL;elseJSRL+M;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊三種裝入方式：絕對裝載方式、可重定位裝載方式、動態運行時轉載方式。1、絕對裝載：編譯后，裝入前已產生了絕對地址（內存地址），裝載時不再作地址重定位。絕對地址的產生：（1）由編譯器完成，（2）由程序員編程完成。對（1）而言，編程用符號地址。

程序每次必須裝入同一內存區；程序員必須事先了解內存的使用情況，根據內存情況確定程序的邏輯地址；程序的修改將引起整個程序中指令地址的變動；程序所有的存儲引用（函數調用），在裝入之前都必須轉換為物理地址，這不利于存儲共享。3.程序轉載2、可重定位裝載方式

(靜態地址重定位)目標模塊的起始地址通常是從0開始的，程序中的其它地址也都是相對于起始地址計算的。由裝載程序將裝載模塊裝入內存后，裝載模塊中程序所訪問的所有邏輯地址與實際裝載內存的物理地址不同，必須進行地址映射，將邏輯地址轉換為物理地址。靜態重定位技術：地址映射在程序裝載時進行，以后不再更改程序地址。0100025005000LOAD1,2500LOAD1,1250036536510000110001250015000目標模塊裝入內存LOADj365符號地址相對地址絕對地址裝入模塊j3.動態重定位在程序運行時動態進行程序的地址轉換。硬件的支持，即重定位寄存器，用于保存程序的在內存中的起始地址。能保證進程的可移動性，有效的提高內存的使用效率。運行時重定位有利于多道程序環境下，進程的換進/換出及實現緊湊技術。load1,2500365load1,25003650100250050002500500005000050100+5250055000作業J處理機一側存儲器一側重定位寄存器(分區首地址寄存器)相對地址4.2.1固定分區存儲管理4.2.2可變分區存儲管理

4.2.3伙伴系統4.2.4主存不足的存儲管理技術4.2連續存儲管理4.2.1固定分區存儲管理分區管理：是一種簡單使用的存貯管理方案，把內存空間靜態的（動態的）分割成若干大小可以不等的區域，每個作業分配一片連續的存儲空間，程序一次整體裝入固定式分區管理：將內存空間靜態的分割成若干大小可以不等的區域，每個分區只能裝入一道作業，分區的個數是內存中作業的最大道數操作系統區用戶分區1用戶分區2用戶分區3固定分區存儲管理(續)劃分分區的方法：分區大小相等：將內存分割成若干個大小相等的區（太大造成內存的浪費，太小不能裝入進程運行，缺乏靈活性）分區大小不等：一部分大的一部分小的，一部分適中的注意：一個分區分配了一個作業后剩余空間便不能再用，這稱為內碎片；當一個區域小于一個作業時便整塊被丟棄，稱為外碎片為了記住哪些分區是空閑分區，哪些分區是已分配分區，系統可設置如下主存分配表：分區號大小(KB)起址(KB)狀態1824已分配21632已分配33248已分配46480未分配5128144已分配操作系統作業A(7K)作業B(13K)作業C(23K)空閑分區作業D(80K)24K32K48K144K272K~~80K分區描述表內存分配情況碎片固定分區存儲管理(續)缺點：固定分區存儲管理限制了程序的大小,無法運行超過分區大小的程序內存空間利用率不高不便于程序動態擴充內存限制了程序道數固定分區存儲管理適合于程序大小和出現頻率已知的情形4.2.2可變分區存儲管理按照作業的大小來劃分分區，劃分的時間、大小和位置都是動態的。系統啟動后用戶作業裝入內存之前，整個用戶區是一個大的空閑分區，隨著作業的裝入和撤離，內存空間被分成許多大小不一的分區，有的分區正被作業占用，有的分區是空閑的。當一個新的作業要求裝入時，必須找到一個足夠大的空閑區，如果找到的空閑分區大于作業需要量，則把該空閑分區分成兩部分，一部分分配給作業，另一部分作為一個較小的空閑分區。當一個作業運行結束時，它歸還的分區如果與其它空閑分區相鄰，則還要進行合并，形成一個大的空閑分區。一、分區組織1．空閑分區表：在系統中設置一張空閑分區表，用于記錄每個空閑分區的情況。2．空閑分區鏈：為了實現對空閑分區的分配和鏈接，設置前向指針和后向指針，通過前、后向鏈接指針將所有的空閑分區鏈接成一個雙向鏈。前向指針分區信息N個字節可用后向指針系統區A(8K)B(16K)C(20K)D(28K)E(56K)F(2K)G(40K)..024K32K48K68K96K152K154K194K256kA、B、C、D、E、F、G任務陸續進入內存進行執行，T0時刻，A、C、E、G已經完成，請畫出當前時刻空閑分區表。如果此時有來了一個15K大小H任務，會分在哪個空閑分區里面。分區號大小(KB)起址(KB)狀態1824未分配22048未分配35696未分配440154未分配562194未分配空閑分區表1．最先適應算法（首次適應算法）。每次都從頭開始，尋找第一個滿足需求的空閑分區。特點：找到第一個大小滿足的分區，劃分。有碎片（外零頭），低址內存使用頻繁。2．下次首次適應算法（循環首次適應算法）。與1類似，從上次找到的空閑分區的下一個開始查找。特點：空閑分區分布均勻，提高了查找速度；缺乏大的空閑分區3．最佳適應算法（最優適應算法）分區按大小遞增排序；分區釋放時需插入到適當位置。特點：產生無法利用的小碎片。4.最壞適應算法掃描整個空閑分區表或空閑分區鏈,總是挑選一個最大的空閑區分割給作業使用特點：分割剩余的空閑區不至于太小二、分區分配當進程運行完畢釋放內存時，需合并相鄰的空閑分區，形成大的分區，稱為合并技術。（1）上鄰空閑區：合并，改大小（2）下鄰空閑區：合并，改大小，首址。（3）上、下鄰空閑區：合并，改大小。（4）不鄰接，則建立一新表項。三、分區回收進程1F1回收區進程2進程3進程1進程2回收區F2進程3進程1F1回收區F2進程2內存回收時的情況F1進程1回收區進程2F22.地址轉換與存儲保護可變分區方式采用動態重定位裝入作業,作業程序和數據的地址轉換由硬件完成.硬件設置兩個控制寄存器:基址寄存器和限長寄存器.基址寄存器存放分配給作業使用的分區的起始地址,限長寄存器存放作業占用的連續存儲空間的長度當作業占有CPU運行時,操作系統把作業所占分區的始址和長度送入基址寄存器和限長寄存器.隨著逐條指令的執行和數據訪問完成地址轉換當邏輯地址小于限長值時，可獲得絕對地址，大于時，不允許訪問基址基址寄存器邏輯地址CPU絕對地址操作系統區空閑分區1用戶作業1空閑分區2限長限長寄存器<限長越界中斷動態分區特點系統初啟時，整個內存只有一個自由塊需調入一個作業時，查找所有的自由塊直到找到一個滿足要求的并把它分給該作業當自由塊較大以至滿足一個作業的需求后仍有剩余則將剩余量構成一個新的自由塊交給系統當一個作業運行完畢并釋放了其所得到的空間時，要考慮它上下是否鄰接自由塊，若有合并它們為一個較大的自由塊解決了內碎片的問題，但會產生很多較小的外碎片（相對的概念）固定分區和動態分區方式都有不足之處。固定分區方式限制了活動進程的數目，當進程大小與空閑分區大小不匹配時，內存空間利用率很低。動態分區方式算法復雜，回收空閑分區時需要進行分區合并等，系統開銷較大。伙伴系統方式是對以上兩種內存方式的一種折衷方案。伙伴系統規定，無論已分配分區或空閑分區，其大小均為2的k次冪，k為整數，l≤k≤m，其中：21表示分配的最小分區的大小，2m表示分配的最大分區的大小，通常2m是整個可分配內存的大小。4.2.4動態分區的實例——伙伴系統當需要為進程分配一個長度為n的存儲空間時，首先計算一個i值，使2i－1<n≤2i，然后在空閑分區大小為2i的空閑分區鏈表中查找。若找到，即把該空閑分區分配給進程。否則，表明長度為2i的空閑分區已經耗盡，則在分區大小為2i＋1的空閑分區鏈表中尋找。若存在2i＋1的一個空閑分區，則把該空閑分區分為相等的兩個分區，這兩個分區稱為一對伙伴，其中的一個分區用于分配，而把另一個加入分區大小為2i的空閑分區鏈表中。若大小為2i＋1的空閑分區也不存在，則需要查找大小為2i＋2的空閑分區，若找到則對其進行兩次分割：第一次，將其分割為大小為2i＋1的兩個分區，一個用于分配，一個加入到大小為2i＋1的空閑分區鏈表中；第二次，將第一次用于分配的空閑區分割為2i的兩個分區，一個用于分配，一個加入到大小為2i的空閑分區鏈表中。若仍然找不到，則繼續查找大小為2i＋3的空閑分區，以此類推。由此可見，在最壞的情況下，可能需要對2k的空閑分區進行k次分割才能得到所需分區。

與一次分配可能要進行多次分割一樣，一次回收也可能要進行多次合并，如回收大小為2i的空閑分區時，若事先已存在2i的空閑分區時，則應將其與伙伴分區合并為大小為

2i＋1的空閑分區，若事先已存在2i＋1的空閑分區時，又應繼續與其伙伴分區合并為大小為2i＋2的空閑分區，依此類推。在伙伴系統中，其分配和回收的時間性能取決于查找空閑分區的位置和分割、合并空閑分區所花費的時間。與前面所述的多種方法相比較，由于該算法在回收空閑分區時，需要對空閑分區進行合并，所以其時間性能比前面所述的分類搜索算法差，但比順序搜索算法好，而其空間性能則遠優于前面所述的分類搜索法，比順序搜索法略差。當一個新的作業要求裝入,沒有一個空閑分區能夠滿足要求,但所有空閑分區之和能夠滿足要求時,可以移動內存作業,合并這些小的空閑分區,使之滿足新來的作業。作業移動后,要及時修改它們的基址。操作系統作業1空閑區作業2空閑區作業3空閑區操作系統作業1作業2作業3空閑區操作系統作業1作業2作業3空閑區作業44.2.3主存不足的存儲管理技術-移動技術

對換的引入將阻塞進程，暫時不用的程序、數據換出。將具備運行條件的進程換入。類型：整體對換：進程對換，解決內存緊張部分對換：頁面對換/分段對換：提供虛存支持對換空間管理外存對換區比文件區側重于對換速度。因此，對換區一般采用連續分配。采用數據結構和分配回收類似于動態分區分配。4.2.3主存不足的存儲管理技術-對換技術連續分配引起:碎片離散分配方式分頁存儲管理將一個進程的邏輯地址空間分成若干個大小相等的頁面，把內存空間分成與頁面相同大小的若干個存儲塊，稱為頁框，在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的頁框中。分段存儲管理作業的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個段都有自己的名字。每個段都從0開始編址，并采用一段連續的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。段頁存儲管理是分段和分頁原理的結合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。4.3.1分頁式存儲管理的基本原理4.3.2快表4.3.3分頁式存儲空間的分配和去配4.3.4分頁式存儲空間的頁面共享和保護4.3.5多級頁表4.3分頁存儲管理4.3.1分頁式存儲管理的基本原理將一個進程的邏輯地址空間分成若干個大小相等的區，稱為頁面或頁，相應地，也把內存空間分成與頁面相同大小的若干個存儲塊，稱為頁框，在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的頁框中。對頁框和頁面都加以編號，從0開始，如第0號、第1號等由于進程的最后一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”或稱為“內零頭”。1.頁面頁面和頁框：邏輯空間和內存空間由機器的地址結構決定頁太大，頁內碎片大。頁太小：頁表可能很長，換入/出效率低2.地址結構

31 1211 0邏輯地址A；頁大小L(設為4096)；頁內偏移d P=(int)A/Ld=AmodL如：A＝8210B.則P=2,d=18分頁存儲管理頁號P頁內位移d3、頁表0頁1頁2頁3頁4頁5頁n頁02132638495n0123456789用戶程序頁表頁面號頁框號內存地址轉換由頁表完成邏輯頁號—物理頁框號的映射。一、基本地址變換機構： 越界保護每個進程對應一頁表，其信息（如長度、始址）放在PCB中，執行時將其首地址裝入頁表寄存器。二、地址轉換的過程進程運行前系統把頁表基址存入頁表基址寄存器運行時硬件自動將邏輯地址分成兩部分，頁號P和頁內位移d找到頁表基址后，按頁號P作為索引查頁表，得到頁框號，根據公式完成地址轉換物理地址=頁框號×塊長+頁內位移分頁系統地址轉換頁表始址頁表長度＋頁號(3)頁內地址(342)頁表寄存器邏輯地址(12630)＜越界中斷5頁框號頁表頁號0123物理地址68155頁號012368154.3.2快表由于頁表放在內存中，這樣，CPU每存取一個數據時，需要兩次訪問內存一次訪問頁表取得物理塊號以形成物理地址第二次根據物理地址存取數據,速度降低了一倍為了提高速度,在存儲管理部件中增設一個專用的高速緩沖存儲器,用來存放最近訪問過的部分頁表,這種相聯存儲器稱為快表；快表昂貴，不易過多。如Intel80486的快表為32個單元具有快表的分頁系統地址轉換頁表始址頁表長度＋頁號(2)頁內地址(342)頁表寄存器邏輯地址＜越界中斷5頁框號頁表頁號0123物理地址6815相聯存儲器快表501268頁框號頁號有了快表,根據頁號查找對應的物理塊號時：首先查找快表，若找到則將物理塊號和頁內地址（也是塊內地址）拼接形成物理地址若在快表中未找到物理塊號，則再查找內存頁表，獲取物理塊號，一方面形成物理地址，另一方面將該表項抄到快表中，以備下次再次訪問該頁面有的系統查快表和查內存頁表是同時進行的，一旦從快表中找到了對應項，則立即停止對內存頁表的查找當快表已滿且要登記新頁時，需要淘汰舊快表項，最簡單的策略是“先進先出”

例：有一分頁式系統，其頁表存放在主存中：①如果對主存的一次存取需要10ns,試問實現一次頁面訪問的存取時間是多少?②如果系統加有快表,平均命中率為85%,當頁表項在快表中時,其查找時間為2ns,試問此時的存取時間是多少?答：若頁表存放在主存中，則要實現一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據該地址存取頁面數據。■頁表在主存的存取訪問時間

=10*2=20(ns)■增加快表后的存取訪問時間

=0.85*12+(1-0.85)*（2+10*2）=13.4(ns)4.3.3分頁式存儲空間的分配和去配位示圖由一些二進制位組成,每一位對應一個內存物理塊,位值表示所對應的物理塊是否已分配出去.分配和回收物理塊時只需修改位值即可鏈表方法1111100011111111110011111100011100000001111111111100000011111111111000000114.3.4分頁式存儲空間的共享與保護分頁存儲管理在實現共享時,必須區分數據共享和程序共享,實現數據共享時,允許不同的作業對共享的數據頁使用不同的頁號,只要讓各自頁表中的有關表目指向共享的數據信息塊就行了實現程序共享時,由于頁式存儲結構要求邏輯地址空間是連續的,所以程序運行前它們的頁號就確定了.對共享的程序必須規定一個統一的頁號.當共享程序的作業數增多時,要規定一個統一的頁號是困難的實現信息保護的辦法是在頁表中增加一些標志位,用來指出該頁的信息可讀/寫\只讀\只可執行\不可訪問等4.3.5

多級頁表現代的大多數計算機系統，都支持非常大的邏輯地址空間(232~264)。在這樣的環境下，頁表就變得非常大，要占用相當大的內存空間。例如，對于一個具有32位邏輯地址空間的分頁系統，規定頁面大小為4KB，則在每個進程頁表中的頁表項可達1兆個之多，又因為每個頁表項占用4個字節，故每個進程僅僅其頁表就要占用4MB的內存空間，而且還要求是連續的。多級頁表（續）多級頁表實現方法

（1）把整個頁表進行分頁，分成一張張小頁表(稱為頁表頁或頁目錄表)，小頁表的大小與頁框相同，為進行索引查找，為這些小頁表建一張頁目錄表，其表項指出小頁表所在頁框號及相關信息（2）系統為每個進程建一張頁目錄表，它的每個表項對應一個頁表頁，而頁表頁的每個表項給出了頁面和頁框的對應關系,頁目錄表是一級頁表，頁表頁是二級頁表（3）邏輯地址結構有三部分組成：頁目錄、頁表頁和位移

B

offset目錄位移頁表頁位移

頁內位移BF進程一級頁表進程二級頁表物理地址邏輯地址頁目錄表控制寄存器4.4.1程序分段結構4.4.2分段式存儲管理的基本原理4.4.3段的共享和保護4.4.4分段和分頁的比較4.4分段式存儲管理基于模塊化的程序設計，通常將一個大任務分成若干個相對獨立的子任務，對應于子任務編寫子程序，稱為段。各個子程序可以獨立的編輯、編譯、鏈接和執行各個子程序由實現的功能決定，長度各不相同。執行時，根據實際需要將各個子程序鏈接成一個大程序。4.4.1

程序分段結構-分段存儲管理的引入4.4.2分段式存儲管理的基本原理

段號

段內偏移量在分段存儲管理方式中，作業的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個段都有自己的名字。每個段都從0開始編址，并采用一段連續的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。整個作業的地址空間，由于是分成多個段，因而是二維的，亦即，其邏輯地址由段號（段名）和段內地址所組成。分段地址中的地址具有如下結構：作業空間（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k內存空間30k40k20k80k15k120k10k150k段長段首址段號0123段表段表：為每個分段分配一個連續的分區，而進程中的各個段可以離散地移入內存中不同的分區中。段表始址段表長度＋段號（2)100段表寄存器邏輯地址＜越界中斷122980物理地址分段系統地址變換機構＋30k40k20k80k15k120k10k150k段長段首址段號0123段表例題對以下段表,請將邏輯地址(0,137),(1,4000),(2,3600),(5,230)轉換成物理地址.段號起始地址段長050K10KB160K3KB2120K5KB370K8KB4150K4KB4.4.3

段的共享和保護段的共享是通過不同作業段表中的項指向同一個段基址來實現的于是，幾道作業共享的程序就可放在一個段中，只要讓各道作業的共享部分有相同的基址/限長值就可以了必須對共享段的信息進行存取控制和保護ed1ed2…ed40data1_1…data1_10021122……40604161……5070…ed1ed2…ed40data1_1…data1_10data2_1…data2_10進程1進程2頁表頁表ed1ed2…ed40data2_1…data2_10主存分頁系統中共享editor021122……40604161……分段系統中共享editoreditordata1editordata2段長基址1608040240段長基址1608040380editordata1…data2在分段系統中，實現共享則容易得多，只需在每個進程的段表中為文本編輯程序設置一個段表項。進程1進程2段表4.4.4分段和分頁的比較分段是信息的邏輯單位，由源程序的邏輯結構所決定,用戶可見；分頁是信息的物理單位，與源程序的邏輯結構無關，用戶不可見。段長可根據用戶需要來規定，段起始地址可從任何主存地址開始；頁長由系統確定，頁面只能以頁大小的整倍數地址開始。分段方式中,源程序(段號,段內位移)經連結裝配后地址仍保持二維結構;分頁方式中,源程序(頁號,頁內位移)經連結裝配后地址變成了一維結構思考在分頁存儲管理中,其邏輯地址空間是__維的.在分段存儲管理中,其邏輯地址空間是__維的.在沒有快表的情況下,分頁系統每訪問一次數據,要訪問__次內存;分段系統每訪問一次數據,要訪問__次內存.在分頁系統中為實現地址變換而設置了頁表寄存器,其中存放了__和__.程序未運行時,這些信息保存在__中.頁表中的基本數據項是__,段表中的基本數據項是__和__.把邏輯地址分成頁號和頁內地址是由__進行的,所以分頁系統的作業地址空間是__維的.把邏輯地址分成段號和段內地址是由__進行的,所以分段系統的作業地址空間是__維的.思考頁表寄存器的值為下面哪些頁表有錯（）5頁框號頁號01236815501236815頁表始址頁表長度464K5頁框號頁號01276815503468155頁框號頁號01268501268ABC4.5.1虛擬存儲器概念4.5.2請求分頁虛擬存儲管理4.5.4請求段頁式虛擬存儲管理4.5虛擬存儲管理4.5.1虛擬存儲器概念前面介紹的連續的（分區）、離散的（分頁和分段）管理均是將程序一次性全部裝入內存后才能運行，在下面情況下：（1）一個特別大的作業，不能夠一次裝入內存（2）有大量作業在外存上等待運行，而又沒有足夠大的內存容納這些作業，只能將少量作業裝入內存運行，大量的作業在外存上等待解決辦法：（1）可以從物理上擴大內存（2）邏輯上擴充內存，即虛擬內存技術局部性原理C++程序示例局部性原理程序執行的局部性是指在一段時間內，程序訪問的存儲空間僅限于某個區域（這稱為空間局部性），或者最近訪問過的程序代碼和數據很快會再被訪問（這稱為時間局部性）。第一，程序中只有少量分支和過程調用，大都是順序執行的指令。第二，程序包含若干循環，是由相對較少的指令組成，在循環過程中，計算被限制在程序中很小的相鄰部分中。第三，很少出現連續的過程調用，相反，程序中過程調用的深度限制在小范圍內，一段時間內，指令引用被局限在很少幾個過程中。第四，對于連續訪問數組之類的數據結構，往往是對存儲區域中相鄰位置的數據的操作。第五，程序中有些部分是彼此互斥的，不是每次運行時都用到的，如出錯處理程序。虛擬存儲系統思想基于局部性原理，程序在運行之前，沒有必要全部裝入內存，將將要運行的少數先裝內存便可開始運行,其余部分留在磁盤上。運行時，要訪問的如果已調入內存，繼續運行；如果未調入，通過操作系統“部分裝入”，再運行。如果內存已滿，用“部分替換”功能，將內存中暫時不用的部分調到磁盤上，把要訪問的調入。大的用戶程序在較小的內存空間運行。更多的作業并發執行。用戶角度看,系統所具有的內存容量,將比實際內存容量大得多。虛擬存儲器的定義在具有層次結構存儲器的計算機系統中，采用自動實現部分裝入和部分對換功能，為用戶提供一個比物理內存容量大得多的，可尋址的“內存儲器”。虛擬存儲器的容量取決于計算機的地址結構和可用的物理內存和外存的容量之和。邏輯地址空間處理器虛擬地址存儲管理部件物理地址主存輔存物理地址空間虛擬存儲管理的概念（續）實現虛擬存儲器必須解決好以下有關問題：主存輔存統一管理問題邏輯地址到物理地址的轉換問題部分裝入和部分對換問題虛擬存儲器的實現方法主要有：請求分頁式虛擬存儲管理請求段頁式虛擬存儲管理4.5.2請求分頁虛擬存儲管理1.請求分頁式虛擬存儲的硬件支撐2.請求分頁虛擬存儲的基本原理3.交換區4.頁面裝入策略和清除策略5.頁面分配策略6.缺頁中斷率7.頁面替換策略8.請求分頁虛擬存儲管理的幾個設計問題1.請求分頁式虛擬存儲管理的硬件支撐

存儲管理部件--MMU①管理硬件頁表寄存器：負責裝入將要占用處理器的進程的頁表②分解邏輯地址為頁號和頁內地址③管理快表：查找快表、裝入表目和清除表目④訪問頁表⑤當要訪問的頁面不在內存時發出缺頁中斷，頁面訪問越界時發出越界中斷⑥管理特征位：設置和檢查頁表中的狀態位、訪問字段、修改位、保護權限等2.請求分頁系統的基本原理在進程開始運行之前，不是裝入全部頁面，而是裝入一個或幾個頁面，進程運行過程中，訪問的頁面不在內存時，再裝入所需頁面；若內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面怎樣才能發現頁面不在內存中呢?怎樣處理這種情況呢?采用的辦法是：擴充頁表的內容，增加駐留標志位和頁面輔存的地址等信息頁號頁框號駐留位P引用位U修改位M外存地址是否已調入內存被訪問次數或多長時間未被訪問，供選擇換出頁面時參考是否被修改過,頁面置換時參考外存上的地址,調入時參考頁表機制邏輯地址空間主存(用戶區)CPU邏輯地址快表主存(系統區)運行進程頁表輔存缺頁中斷處理①分解地址③⑤訪問MMU②查快表③命中④不命中⑤頁表命中⑦發缺頁中斷⑧調頁⑨裝入、改表④查頁表運行進程頁表基址⑥裝入快表運行進程映象進程切換時裝入物理地址頁框頁內地址頁號頁內地址請求分頁的地址變換過程查快表有登記無登記查頁表登記入快表發缺頁中斷在主存在輔存形成絕對地址繼續執行指令重新執行被中斷指令恢復現場調整頁表和主存分配表裝入所需頁面主存有空閑塊保護現場有選擇調出頁面該頁是否修改未修改已修改把該頁寫回輔存相應位置操作系統-缺頁中斷處理程序硬件MMU邏輯地址無①②③④3.交換區

操作系統在磁盤上定義一個交換區用來保存臨時換出的頁面，交換區是物理內存的擴展，它和內存一起組成虛擬存儲空間，文件系統不能占用交換區空間。

交換區管理重點是維護交換區映射表，該表用來記錄所有被換出內存的頁面在交換區中的位置，以便在需要時再次換入內存。當頁面第二次被換出內存時，僅當頁面修改過（臟頁）才寫入交換區，否則因已有副本就直接將它丟棄。4.頁面裝入策略和清除策略頁裝入策略：請頁式調入：在需要訪問程序和數據時,才把所在頁面裝入主存優點是確保只有被訪問的頁才調入內存，節省了主存空間缺點是處理缺頁中斷和調頁的系統開銷較大，每次僅調一頁,增加了磁盤I/O次數預調式調入：由系統預測進程將要使用的頁面,使用前預先調入主存,每次調入若干頁面,而不是僅調一頁優點是減少磁盤I/O啟動次數，節省尋道和收索時間缺點是可能所調入頁面大多未使用，效率低。頁面清除策略請頁式清除僅當一頁選中被替換,且之前它又被修改過,才把這個頁面寫回輔存預約式清除對所有更改過的頁面,在需要之前就把它們都寫回外存4.頁面裝入策略和清除策略(續)5.頁面分配策略系統為進程分配主存,需考慮因素:①分給進程的空間越小,同一時間處于內存的進程就越多，至少有一個進程處于就緒態的可能性就越大②如果進程只有小部分在主存里,即使局部性很好,缺頁中斷率還會增加③分給進程的內存超過一定限度后，再增加內存空間,不會明顯降低進程的缺頁中斷率假設固定分配，運行FORTRAN程序，共有0.25×106次頁面引用，頁面大小為256個字。分給進程的頁框數分別為6、8、10、12和14FIFO所產生的缺頁中斷基本上是Opt的2倍，Clock則比較接近于LRU0510152025354030068101214分配的頁數每千次訪問的缺頁中斷數

FIFO

CLOCK

LRU

OPT頁面分配策略固定分配：固定分配使進程在生命周期中保持固定數目的物理塊，每個進程物理塊的分配方式主要有：平均分配按比例分配考慮優先權的分配可變分配不時重新評價進程的缺頁率，增加或減少進程的頁框數，以改善系統的總性能。頁面替換策略局部替換：局部替換在進程發生缺頁時僅從該進程的物理塊中淘汰頁面,以調入所缺頁面全局替換：全局替換則在進程發生缺頁時可從系統中任一進程的物理塊中淘汰頁面頁面分配和替換常用的組合策略有三種:固定分配局部置換、可變分配全局置換和可變分配局部置換6.缺頁中斷率頁面替換主存空間已經用完，而又要裝入新頁時，必須把主存的一些頁面調出去，叫頁面替換頁面淘汰算法確定被淘汰頁的算法“抖動”(Thrashing)(“顛簸”)現象是淘汰算法不好而產生的一種現象。剛淘汰的頁面又立即要用，又將其調入，然后再淘汰、再調入。浪費大量CPU的時間假定作業p共計n頁，系統分配給它的主存塊只有m塊（１≤m≤n）。如果作業p在運行中成功的訪問次數為S，不成功的訪問次數（缺頁次數）為F，則總的訪問次數Ａ為：A=S+F，又定義：f=F/A稱f為缺頁中斷率6.缺頁中斷率影響缺頁中斷率f的因素有：(1)主存頁框數(2)頁面大小(3)頁面替換算法(4)程序特性程序要將128×128的數組置“0”。分給的主存只一塊，頁面尺寸為每頁128個字，數組中的元素每行存放在一頁中。intA[128][128];for(intj=0;j<128;j++)for(inti=0;i<128;i++)A[i][j]:=0總共產生（128*128－1）次缺頁中斷intA[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++)A[i][j]:=0總共產生（128－1）次缺頁中斷請求分頁虛擬存儲管理（續）幾種頁面替換策略:最佳頁面算法(OPT、Belady算法)先進先出頁面淘汰算法(FIFO)最近最久未使用頁面淘汰算法(LRU)Clock置換算法最佳頁面替換算法(OPT)其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面。采用最佳頁面置換算法，通常可保證獲得最低的缺頁率。假定系統為某進程分配了三個頁框（物理塊），并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1；70770170122010320304243230321201201770101203共缺頁中斷9次，缺頁中斷率為9/20=45%;頁面替換6次總是淘汰最先進入內存的頁面.頁面按先后次序鏈接成一個隊列設置一個替換指針,指向最老的頁面先進先出（FIFO）頁面替換算法70770170122010323104230230321013201771201023430420423012702701共缺頁中斷15次，缺頁中斷率為15/20=75%;頁面替換12次最近最少使用LRU替換算法訪問字段，上次被訪問以來所經歷的時間t選擇t值最大的頁面淘汰用“最近的過去”作為“最近的將來”的近似70770170122010320304230321132201710201032403402432107共缺頁中斷12次，缺頁中斷率為12/20=60%;頁面替換9次1）引用位法方法：每頁設置一個引用標志位R，訪問某頁時，由硬件將頁標志位R置1，隔一定時間t將所有頁的標志R均清0發生缺頁中斷處理：從標志位R為0的頁中挑選一頁淘汰。并將所有頁的標志位R清0主要問題：時間間隔t的選擇，t太大則標志位R均為1，t太小則標志位R均為0LRU算法的硬件支持2）計數器法方法：每個頁面設置一個多位計數器，每當訪問一頁時，就使它對應的計數器加1。又叫最不常用頁面替換算法LFU。發生缺頁中斷處理：選擇計數值最小的對應頁面淘汰，并將所有計數器全部清0。LRU算法的硬件支持3）計時法方法：為每個頁面設置一個多位計時器，每當頁面被訪問時，系統的絕對時間記入計時器缺頁中斷處理：比較各頁面的計時器的值，選最小值的未使用的頁面淘汰，因為，它是最“老”的未使用的頁面。時鐘頁面替換算法一個頁面首次裝入主存，其“引用位”置1。主存中的任何頁面被訪問時,“引用位”置1。淘汰頁面時,從指針當前指向的頁面開始掃描循環隊列，把遇到的“引用位”是1的頁面的“引用位”清0,跳過這個頁面;把所遇到的“引用位”是0的頁面淘汰掉,指針推進一步。掃描循環隊列時，如果遇到的所有頁面的“引用位”為1，指針就會繞整個循環隊列一圈，把碰到的所有頁面的“引用位”清0;指針停在起始位置，并淘汰掉這一頁,然后，指針推進一步。P9U1P19U1P1U0P45U1P191U1P556U0P13U0P67U1P33U1P222U0

：：下幀指針n012345678一個頁替換前的緩沖區狀態P9U1P19U1P1U0P45U0P191U0P727U1P13U0P67U1P33U1P222U0n012345678替換一頁后的緩沖區狀態頁框號

：：時鐘頁面替換算法的改進算法把”引用位”和”修改位”結合起來使用，共組合成四種情況：(1)最近沒有被引用,沒有被修改(r=0,m=0)(2)最近被引用,沒有被修改(r=1,m=0)(3)最近沒有被引用,但被修改(r=0,m=1)(4)最近被引用過,也被修改過(r=1,m=1)步1：選擇最佳淘汰頁面，從指針當前位置開始,掃描循環隊列。掃描過程中不改變“引用位”，把找到的第一個r=0,m=0的頁面作為淘汰頁面。步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把找到的第一個這樣的頁面作為淘汰頁面，而在掃描過程中把指針所掃過的頁面的“引用位”r置0。步3：如果步2失敗，指針再次回到了起始位置，由于此時所有頁面的“引用位”r均己為0，再轉向步1操作，必要時再做步2操作，這次一定可以挑出一個可淘汰的頁面。時鐘頁面替換算法的改進算法工作集模型用于模擬實現局部最佳頁面替換算法使用滑動窗口，但不向前查看引用串，而是向后看通過考察最近主存需求來估計進程將需要的頁框數

進程工作集

在某一段時間間隔內進程運行所需訪問的頁面集合W(t,△)表示在時刻t-△到時刻t自己所訪問的頁面集合，它就是進程在時刻t的工作集。變量△稱為“工作集窗口尺寸”，工作集所包含的頁面數稱為“工作集尺寸”工作集替換示例頁面引用串與上例相同，△=3。當系統有空閑頁框供分配，并在時刻t=0時，初始工作集為（p1，p4，p5），其中，p1在時刻t=0被引用，p4在時刻t=-1被引用，而p5在時刻t=-2時刻被引用。第一次缺頁中斷發生在時刻t=1，頁面p3被裝入一個空閑頁框，另外3個