第四章存儲管理

在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式——為一個用戶程序分配一個連續(xù)的主存空間。4.2連續(xù)存儲空間管理1第六章存儲管理一、單一連續(xù)分配（單個分區(qū)）最簡單的存儲管理方式，用于多道程序設計技術之前。內存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個連續(xù)的分區(qū)分配給一個作業(yè)。評價優(yōu)點：方法簡單，易于實現缺點：1.僅適用于單道程序，只能用于單用戶單任務的操作系統(tǒng)

2.系統(tǒng)資源利用率低系統(tǒng)區(qū)用戶區(qū)2第六章存儲管理分區(qū)存儲管理是滿足多道程序設計的最簡單的一種存儲管理方法，它允許多個用戶程序同時存在系統(tǒng)內存中，即共享內存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。 3第六章存儲管理二、

固定分區(qū)存儲管理1.基本思想把內存的用戶區(qū)預先劃分成多個分區(qū)，每個分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計算機的操作員或者由操作系統(tǒng)給出，并給出主存分配表）

分區(qū)個數固定，分區(qū)的大小固定。一個分區(qū)中可裝入一個作業(yè)，作業(yè)執(zhí)行過程中不會改變存放區(qū)域。早期的IBM的OS/MFT（具有固定任務數的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。4第六章存儲管理2.主存分配表為了說明各分區(qū)的分配和使用情況，需設置“主存分配表”，記錄各分區(qū)及其使用情況。主存分配表內容：分區(qū)號，分區(qū)的起始地址，長度，占用標志。3.主存空間分配主存存分配程序檢索主存分配表，從中找到還未分配且大小滿足要求的分區(qū)，則將此分區(qū)分配給該作業(yè)。若沒找到滿足條件的分區(qū)，則拒絕為該作業(yè)分配主存。5第六章存儲管理例：某系統(tǒng)的內存容量為256K，操作系統(tǒng)占用低地址的20K，其余空間劃分成4個固定大小的分區(qū)。如下圖分區(qū)號起始地址(KB)長度(KB)占用標志1208A22832C36064Ｂ4124132０主存分配表6第六章存儲管理４.固定分區(qū)性能分析在作業(yè)大小和出現頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當，這樣內存的使用效率較高。但是若作業(yè)的大小和出現的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，這樣就會造成存儲空間的浪費，從而影響整個系統(tǒng)的效率。

缺點：碎片問題，主存利用率很低。

7第六章存儲管理三、可變分區(qū)存儲管理（動態(tài)分區(qū)）1.基本思想內存不是預先劃分好的，而是在系統(tǒng)運行的過程中建立分區(qū).當作業(yè)裝入主存時，根據作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定,分區(qū)個數不固定.這種存儲管理的方法克服了固定分區(qū)嚴重浪費主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲管理。8第六章存儲管理

當有作業(yè)完成后釋放所占用的存儲區(qū)。在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)，稱空閑區(qū)。9第六章存儲管理2.實現動態(tài)分區(qū)需要的數據結構在動態(tài)分區(qū)存儲管理中，要有相應的數據結構來登記空閑區(qū)信息，它包括空閑區(qū)的大小和位置。不同系統(tǒng)根據設計要求采用不同的結構。常用的有表結構和鏈結構。系統(tǒng)還要設置了等待分區(qū)隊列，當系統(tǒng)中無空閑區(qū)或無滿足要求的空閑區(qū)時，則把申請者送入等待隊列中，等待別的進程釋放內存之后再喚醒隊列中的進程。10第六章存儲管理例:11第六章存儲管理3.分區(qū)分配算法空閑區(qū)表（鏈）中的空閑區(qū)可按一定規(guī)則排列，例如按空閑區(qū)大小的升序（降序）排列；按空閑區(qū)地址升序（降序）組織。根據空閑區(qū)表（鏈）排列方法不同，對應不同的分配算法，常用的可變分區(qū)分配算法有最先適應算法，下次適應分配算法，最優(yōu)適應算法、最壞適應算法等。12第六章存儲管理(1)最先適應算法空閑區(qū)按地址從小到大的次序排列。分配：當進程申請大小為SIZE的內存時，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為SIZE的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)，但要修改其首址和大小。優(yōu)點：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，有利于大作業(yè)的裝入。缺點:主存低地址和高地址分區(qū)利用不均衡。在低地址部分,集中了許多非常小的空閑區(qū)(碎片),降低了主存的利用率。13第六章存儲管理（２）下次適應分配算法最先適應算法的變種?？偸菑目臻e區(qū)上次掃描結束處順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。14第六章存儲管理(３)最優(yōu)適應算法空閑區(qū)按容量遞增的次序排列。分配：當進程申請存儲空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止。采用最優(yōu)適應算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。15第六章存儲管理優(yōu)點：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲空間的浪費。16第六章存儲管理(４)最壞適應算法要求空閑區(qū)按容量遞減的順序排列。分配：進程申請存儲區(qū)時，檢查空閑區(qū)表（鏈）的第一個空閑區(qū)的大小是否滿足要求，若不滿足則令進程等待；若滿足則從該空閑區(qū)中分配一部分存儲區(qū)給用戶，剩下的部分仍作為空閑區(qū)。為了克服最佳適應算法把空閑區(qū)切割得太小的缺點，人們提出了一種最壞適應算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。17第六章存儲管理分析:當程序裝入內存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當大，還能裝下較大的程序。另一方面每次僅作一次查詢工作，查找效率高。18第六章存儲管理例：某時刻系統(tǒng)中有三個空閑區(qū),有一作業(yè)大小25k。大小起始位置30k48k28k138k45k210k首次適應算法：最優(yōu)適應算法：最壞適應算法：19第六章存儲管理4.可變分區(qū)的回收當某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當位置。釋放區(qū)與空閑區(qū)相鄰的四種情況釋放區(qū)與前空閑區(qū)相鄰釋放區(qū)與后空閑區(qū)相鄰釋放區(qū)與前后兩個空閑區(qū)相鄰釋放區(qū)不與任何空閑區(qū)相鄰20第六章存儲管理(a)釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。(b)釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大小之和。(c)釋放區(qū)與前后兩個空閑區(qū)相鄰：將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個區(qū)大小之和，并取消原后空閑區(qū)表目。(c)釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當位置。21第六章存儲管理可變分區(qū)存儲管理分析優(yōu)點:1.有助于多道程序設計2.不需過多硬件,僅需界地址寄存器用于存儲保護3.所采用的算法都比較簡單,易于實現缺點:1.碎片問題由于空閑區(qū)的大小與申請內存的大小相等的情況是很少的，絕大多數情況是從一個空閑區(qū)中切去一塊，剩下的部分作為一個空閑區(qū)仍留在空閑區(qū)表中，隨著時間的推移，空閑區(qū)的發(fā)展趨勢是越來越小，直至不能滿足任何用戶要求。這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現造成了存儲空間的浪費。2.分區(qū)大小受主存容量限制,無法擴充主存容量22第六章存儲管理四、可重定位分區(qū)存儲管理解決碎片問題的一種簡單方法是采用可重定位分區(qū)分配.1.基本思想例:內存中現有3個空閑區(qū)，如圖所示，現有一作業(yè)到達，要求獲得30k內存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內存中所有作業(yè)進行移動，這樣把原來分散的空閑區(qū)匯集成一個大的空閑區(qū)。操作系統(tǒng)作業(yè)1空閑區(qū)(15k)作業(yè)2空閑區(qū)(15k)作業(yè)3空閑區(qū)(20k)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)（50k）操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)(20k)作業(yè)423第六章存儲管理

將內存中的作業(yè)進行移動,使它們連接在一起,把原來分散的多個小分區(qū)拼接成一個大的空閑區(qū).這個過程稱為”緊湊”或”移動”.

需解決的問題:每次”緊湊”后,程序或數據裝入的物理地址變化,采用動態(tài)重定位.24第六章存儲管理2.動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本相同,差別在找不到足夠大的空閑分區(qū)時進行”緊湊”.

25第六章存儲管理分區(qū)分配方案評價優(yōu)點:1.實現了主存共享,有助于多道程序設計,提高了系統(tǒng)資源的利用率;

主存利用率:可重定位分區(qū)分配>動態(tài)分區(qū)分配>固定分區(qū)分配2.與后面所介紹的存儲管理方式相比,實現分區(qū)分配所使用的表格,占用的存儲空間較少,算法也相對簡單;3.實現存儲保護的措施也較簡單。缺點:1.主存仍不能充分利用,除了可重定位分區(qū)法外,都存在碎片問題.2.采用”緊湊”方法,雖解決了碎片問題,但系統(tǒng)開銷太大.3.不能實現對主存的擴充.因此作業(yè)大小受到主存可用空間限制.26第六章存儲管理五、覆蓋技術與對換技術1.為什么引入？在多道環(huán)境下擴充內存的方法，用以解決在較小的存儲空間中運行較大程序時遇到的矛盾。覆蓋技術主要用在早期的操作系統(tǒng)中。對換技術被廣泛用于小型分時系統(tǒng)中，交換技術的發(fā)展導致了虛存技術的出現。27第六章存儲管理2.覆蓋技術把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結構將那些不會同時執(zhí)行的程序段共享同一塊內存區(qū)域程序段先保存在磁盤上，當有關程序段的前一部分執(zhí)行結束，把后續(xù)程序段調入內存，覆蓋前面的程序段（內存“擴大”了）覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間一般要求作業(yè)各模塊之間有明確的調用結構，程序員要向系統(tǒng)指明覆蓋結構，然后由由操作系統(tǒng)完成自動覆蓋28第六章存儲管理A8KE4KF10KC10KB8KD12K作業(yè)X的調用結構作業(yè)X的常駐區(qū)

A（8K）覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）

BC

D

E

F圖示29第六章存儲管理缺點：對用戶不透明，增加了用戶負擔。

例子：目前這一技術用于小型系統(tǒng)中的系統(tǒng)程序的內存管理上，MS-DOS的啟動過程中，多次使用覆蓋技術；啟動之后，用戶程序區(qū)TPA的高端部分與COMMAND.COM暫駐模塊也是一種覆蓋結構?，F代操作系統(tǒng)極少使用覆蓋技術。分析30第六章存儲管理3.對換技術為平衡系統(tǒng)負載，通過選擇一個進程，把其暫時移出到磁盤，騰出空間給其他進程使用，同時把磁盤中的某個進程再換進主存，讓其投入運行，這種互換稱對換。多用于分時系統(tǒng)中31第六章存儲管理選擇原則（即：將哪個進程換出內存？）時間片輪轉法或基于優(yōu)先數的調度算法，通常把時間片耗盡或優(yōu)先級較低的進程換出，因為短時間內它們不會被投入運行。對換時機（即：何時需發(fā)生對換）批處理系統(tǒng)中，當有進程要求動態(tài)擴充主存且得不到滿足時可觸發(fā)對換；分時系統(tǒng)中，對換可與調度結合在一起，每個時間片結束或執(zhí)行I/O操作時實施。

32第六章存儲管理分析與覆蓋技術相比，交換技術不要求用戶給出程序段之間的邏輯覆蓋結構；交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內。覆蓋只能覆蓋那些與覆蓋段無關的程序段。33第六章存儲管理上節(jié)所介紹的連續(xù)分配方式，會出現碎片問題，雖然采用“緊湊”的方法將許多碎片拼接成可用的大塊空間，但須為之付出很大開銷，而無實用價值。如果允許將一個進程直接分散地裝入到許多不相鄰的分區(qū)中，則無須再進行“緊湊”?；谶@一思想而產生了離散分配方式。離散分配方式：給進程分配幾個不連續(xù)的內存區(qū)域，并可保證進程的正確執(zhí)行。離散分配方式按分配基本單位不同分為分頁存儲管理和分段存儲管理。34第六章存儲管理4.3分頁存儲管理分頁技術是由曼徹斯特大學提出，并于1960年前后在Atlas計算機上實現。這種技術對操作系統(tǒng)的發(fā)展產生了深遠影響。35第六章存儲管理一、基本原理1.頁面

把一個進程的邏輯地址空間分成若干大小相等的片，每個片稱為頁面或頁

。從0開始編制頁號。 頁面的大小應選擇適中，一般頁的大小為2的冪，通常為512B～8KB。2.邏輯地址分頁存儲管理邏輯地址分為兩部分：地址的高位部分為頁號，低位部分為頁內位移。頁號頁內位移例：邏輯地址32位，頁大小4k，則頁內位移占12位，頁號占20位。頁號頁內位移31.….1211……..……….036第六章存儲管理3.物理塊（頁框）把主存的物理地址空間分成和頁面大小相等的區(qū)，每個區(qū)稱為物理塊或頁框。從0開始編制塊號。4.物理地址5.分頁存儲管理基本原理

以頁為單位進行分配。當一個進程裝入內存時，將進程的多個頁面分別裝入內存的多個物理塊中，這些物理塊可以是不相鄰的。塊號塊內位移37第六章存儲管理例：頁面大小1k進程2（3k）進程1（1.8k）01012內存012

34567...38第六章存儲管理6.頁表進程的各個頁面分散存放在主存不相鄰的物理塊中，系統(tǒng)如何知道頁面和物理塊的對應關系。這就需要系統(tǒng)為每個進程建立一個頁表，用來登記頁號和塊的對應關系和有關信息。一個進程有多少個頁面，頁表就有多少項。進程的頁表大多駐留在內存中，頁表在主存的首地址和長度存放在該進程的進程控制塊。39第六章存儲管理例：頁面大小1k0115進程2（3k）進程1（1.8k）01012內存012

34567...進程1頁表頁號塊號頁號塊號進程2頁表03142740第六章存儲管理二、地址轉換把程序的邏輯地址轉換成內存的物理地址。1.分析：程序邏輯地址：內存物理地址：頁號頁內位移塊號塊內位移頁表41第六章存儲管理進程的頁表放在內存中，頁表在主存的首地址和頁表長度保存在本進程的PCB中。系統(tǒng)設置了一個頁表寄存器，當系統(tǒng)調度一個進程運行前，系統(tǒng)把該進程的頁表首地址和頁表長度送入到該頁表寄存器中，以便地址轉換時使用。42第六章存儲管理2.地址轉換過程：p’頁表地址越界中斷

L比較P>=L

b+頁號p

頁內地址d塊號P’塊內地址d物理地址頁表首址寄存器頁表長度寄存器邏輯地址P*表項長度p43第六章存儲管理三、快表和相聯存儲器在頁式存儲技術中，我們可看到每次存取數據，就要做兩次訪問內存的工作，一次是地址轉換查頁表時要作一次訪問內存的工作，然后是根據轉換后的物理地址訪問內存存取數據，這樣存取速度降低一倍，將會影響整個系統(tǒng)的使用效率?？梢姡源烁甙捍鷥r來換取存儲器空間利用率的提高，是得不償失的。44第六章存儲管理為了提高提高地址變換速度，通常都設置一個專用的高速存儲器，用來存放頁表的一部分，這種高速存儲器稱為相聯存儲器（associativememory），存放在相聯存儲器中的頁表稱快表。相聯存儲器的存取時間是遠小于主存的，但造價高，故一般都是小容量的，只能存放幾十個頁表項。在采用了快表的系統(tǒng)中，通常采用“雙管齊下“的方針，一方面檢索相聯存儲器，而同時又檢索內存的頁表，在相聯存儲器中一旦檢索到所要的塊號，便立即停止頁表的檢索，若相聯存儲器中找不到所要的塊號，就應利用主存中頁表查找的到，并將此頁表項填入相聯存儲器中。根據程序執(zhí)行局部性的特點，所以快表的命中率可達90%以上。45第六章存儲管理p’頁表地址越界

L比較P>=Lpp’...快表

b+頁號p

頁內地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址46第六章存儲管理硬件能自動分離出頁號和頁內地址，但我們只能通過計算才能得到。計算時要注意：(1)邏輯地址以十六進制、八進制、二進制的形式給出將邏輯地址轉換成二進制的數；按頁的大小分離出頁號和頁內地址（低位部分是頁內地址，高位部分是頁號）；根據題意產生頁表；將頁內地址直接復制到物理地址的低位部分；以頁號查頁表，得到對應頁裝入內存的塊號，并將塊號轉換成二進制數填入地址的高位部分，從而形成內存物理地址。47第六章存儲管理例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內存的第7、9、A、5塊，試將邏輯地址0AFEH，1ADDH轉換成內存地址。邏輯地址1ADDH=0001101011011101頁號P＝3頁內地址d＝01011011101物理地址＝0010101011011101＝2ADDH邏輯地址0AFEH=0000101011111110B

2k=211

頁內地址占低11位，高位為頁號頁號P＝1頁內地址d＝01011111110查頁表知第一頁裝入到內存第9塊中，9=1001B物理地址＝0100101011111110＝4AFEH48第六章存儲管理(2)邏輯地址以十進制數給出按下列公式計算出頁號和頁內地址

頁號＝邏輯地址％頁大小頁內地址＝邏輯地址mod頁大小根據題意產生頁表；以頁號查頁表，得到對應頁裝入內存的塊號內存地址＝塊號×頁大小＋頁內地址49第六章存儲管理例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。邏輯地址7145頁號P＝7145％2048＝3頁內地址d＝7145mod2048＝1001查頁表知第3頁裝入內存第5塊中物理地址=5*2048+1001=11241邏輯地址3412頁號P＝3412％2048＝1頁內地址d＝3412mod2048＝1364查頁表知第1頁裝入內存第9塊中物理地址=9*2048+1364=1979650第六章存儲管理位示圖記錄主存物理塊的使用情況四、分頁存儲空間的分配與回收0700111017……空閑塊數……110主存分配算法：計算一個進程所需要的總塊數N；查空閑塊數，看是否還有N個空閑塊，若沒有則令進程等待；如有足夠的空閑塊，則頁表長度設為N，可填入PCB中；申請頁表區(qū)，把頁表始址填入PCB查位示圖找出N個為“0”的位，計算對應的物理塊號，將塊號填入頁表；修改位示圖（相應位值占用標志，空閑塊數-N）；51第六章存儲管理主存回收算法進程執(zhí)行結束歸還主存時，根據歸還的物理塊號，計算出對應位在位示圖中的位置，將占有標志清“0”，并將歸還的塊數加入空閑塊數中。52第六章存儲管理五、兩級頁表和多級頁表當頁表項很多時，僅采用一級頁表需要大片邊續(xù)空間，可將頁表也分頁,由此構成二級頁表。具體做法：把整個頁表分成一張張小頁表,每個小頁表每個小頁表稱為頁表頁，大小與物理塊相同，對小頁表順序編號,允許小頁表分散存放在不連續(xù)的物理塊中,為了進行索引查找,應該為這些小頁表建一張頁目錄表,其表項指出小頁表所在物理塊號及相關信息。于是系統(tǒng)要為每個進程建一張頁目錄表,它的每個表項對應一個小頁表,而小頁表的每個表項給出了頁面和物理塊的對應關系,頁目錄表是一級頁表,小頁表是二級頁表。53第六章存儲管理邏輯地址結構有三部分組成：頁目錄位移、頁表頁位移和頁內位移。塊號頁內地址頁目錄位移頁表頁位移頁內位移物理塊地址頁表頁地址進程一級頁表進程二級頁表物理地址邏輯地址頁目錄表控制寄存器二級頁表地址轉換過程54第六章存儲管理解決頁表頁占用主存空間的問題進程運行涉及頁面的頁表頁應放在主存,其他頁表頁使用時再調入,在頁目錄表中增加特征位,指示對應的頁表頁是否已調入主存,地址轉換機構根據邏輯地址中的頁目錄位移,去查頁目錄表對應表項,如未調入,應產生一個”缺頁表頁”中斷信號，請求操作系統(tǒng)將頁表頁調入主存。55第六章存儲管理4.4分段存儲管理

為了解決碎片問題，提高內存利用率引入了分頁存儲管理。引入分段存儲管理主要是滿足用戶（程序員）編程和使用上的要求。應用程序通常是由若干程序段（模塊）組成，例如由主程序段、子程序段、數據段等組成，每段具有完整的邏輯意義。在分頁存儲管理中，頁面是信息的物理單位，與源程序不存在邏輯關系，也就難以實現以段為單位的共享、保護、動態(tài)鏈接等。56第六章存儲管理一、基本原理用戶程序劃分一個用戶程序往往由幾個程序段（主程序、子程序和函數等）所組成。把程序按自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內也從0開始編址，段內地址是連續(xù)的。(分段是由用戶或編譯器負責的）邏輯地址（注意：分段地址空間是真正二維的）段號段內地址57第六章存儲管理...020k4工作區(qū)段[B]0主程序段[M]......0E40K1子程序段[X]0200K...CALL[X][E].........CALL[Y][F]CALL[A]116......0F50k2子程序段[Y]01165k3數組段[A]12345...例：58第六章存儲管理內存分配以段為單位分配內存，每一個段在內存中占據連續(xù)空間（內存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放。例：B020kA05kY050kX040kM0200K01234進程.100k320k500k600k800k40k100k20k50k5k內存操作系統(tǒng)59第六章存儲管理段表記錄了進程的每個邏輯段在內存中的起始地址和段長。每個進程設置一個段表，進程分為多少段，段表就應有幾項。段表放在內存，段表在內存首地址和段表長度存放在本進程的PCB中。上例：段表段號基址段長012100k320k40K100K50K600K5K800K20K500K3460第六章存儲管理二、地址變換段地址變換由硬件地址變換機構完成，系統(tǒng)設置一對寄存器段表始址寄存器：用于保存正在運行進程的段表的始址段表長度寄存器：用于保存正在運行進程的段表的長度（例如上圖的段表長度為5，它與段長及擴充段表目中的存取控制字一起用于分段管理中的存取保護）61第六章存儲管理

Cl

Cb+段號S段內地址d比較b+d段表S>=Cl物理地址段表始址寄存器段表長度寄存器邏輯地址段長l基址b地址越界d>=1分段地址轉換及存儲保護機制地址越界比較+段號*表項長度62第六章存儲管理快表同頁地址變換一樣，在段地址變換過程中，也有兩次訪問內存的問題。為了加快訪問內存的速度也可采用快速存儲器組成快表。

Cl

Cb+段號S段內地址d比較比較b

+d段表S>=Cl快表物理地址段表始址寄存器段表長度寄存器邏輯地址Lb...SLb地址越界d>=Ld>=L地址越界比較63第六章存儲管理三、段的共享在分段系統(tǒng)中實現段共享，只需在每個進程的段表中為共享段設置一個段表項。64第六章存儲管理四、分段和分頁的比較分段是信息的邏輯單位，由源程序的邏輯結構所決定，用戶可見，段長可根據用戶需要來規(guī)定，段起始地址可從任何主存地址開始。分段方式中，源程序(段號，段內位移)經連結裝配后地址仍保持二維結構。分頁是信息的物理單位，與源程序的邏輯結構無關，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數地址開始。分頁方式中，源程序(頁號，頁內位移)經連結裝配后地址變成了一維結構。65第六章存儲管理五、段頁式存儲管理方式分頁系統(tǒng)能解決碎片問題，提高內存利用率；分段系統(tǒng)能很好滿足用戶的需求，便于實現段的共享，保護和動態(tài)鏈接。將兩者結合形成一種新的存儲管理方式。66第六章存儲管理一、段頁式存儲管理基本思想用戶程序劃分 先將用戶程序分成若干個段，再把每個段分成若干個頁。邏輯地址內存劃分 按頁式存儲管理方案內存分配 以頁為單位進行分配段號段內頁號頁內位移67第六章存儲管理68第六章存儲管理段表：記錄了每一段的頁表始址和頁表長度頁表：記錄了邏輯頁號與內存塊號的對應關系（每一段有一個，一個程序可能有多個頁表）二、地址轉換69第六章存儲管理4.5虛擬存儲管理前面介紹的各種存儲管理方式中，在裝入一個作業(yè)時要求將它全部裝入內存，才可運行?？赡艹霈F兩種情況：（1）有些作業(yè)所需內存空間已超出內存總容量。（2）為提高系統(tǒng)資源效率，內存中同時裝入多道作業(yè)，用戶作業(yè)所需空間超出了內存空閑空間。如何解決？70第六章存儲管理1968年美國Denning提出程序局部性原理程序局部性原理程序在執(zhí)行時呈現出高度的局部性特征，即在一較短的時間內，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域。時間局部性一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行,典型原因是程序中的循環(huán)。空間局部性若某一存儲單元被訪問，則在不久之后，與該存儲單元相鄰的單元也可能被訪問,典型原因是程序的順利執(zhí)行。71第六章存儲管理基于程序局部性原理，就沒有必要把一個作業(yè)一次性全部裝入內存再開始運行。而是僅將當前使用部分裝入主存，其余部分存放在磁盤中，啟動程序運行，進程執(zhí)行過程中，若所訪問的程序和數據在主存時可順利執(zhí)行；若不在主存時，由系統(tǒng)自動將這部分信息從磁盤裝入主存（部分裝入），若裝入時沒有足夠空閑物理空間，便把主存中暫時不用的信息移至磁盤（部分替換）。這樣的計算機系統(tǒng)好像為用戶提供了一個存儲容量比實際主存大得多的存儲器，就稱為虛擬存儲器。72第六章存儲管理一、虛擬存儲器概念虛擬存儲器是為了邏輯擴充內存，以解決小內存無法運行大程序的問題而引入的，是一種以CPU時間和外存空間換取內存空間的技術（是OS中的資源轉換技術），也是迄今為止邏輯擴充內存程度最徹底的技術（遠強于覆蓋和交換技術）。虛擬存儲器是在1961年由英國曼徹斯特大學Fotheringham提出，并在該校的atlas機器上實現的一種存儲技術。從1970年后被廣泛應用。73第六章存儲管理1.虛擬存儲器定義在具有層次結構存儲器的計算機系統(tǒng)中，采用自動實現部分裝入和部分替換功能，為用戶提供一個比物理主存容量大得多的，可尋址的一種“主存儲器”。虛擬存儲器的容量受限于計算機的地址結構和可用的磁盤容量，如Intelx的地址線是32位，則程序的可尋址范圍是4G，Windows和Linux都為應用程序提供一個4G的邏輯主存。74第六章存儲管理2.虛擬存儲器實現方法

虛擬存儲器是建立在離散分配的內存管理技術基礎上的，它主要有以下3種實現方法：請求分頁虛擬存儲管理用戶程序要裝入內存時，僅裝入當前使用的頁面，啟動程序運行，在運行的過程中，若發(fā)現要訪問的頁面不在內存，則由系統(tǒng)自動裝入所需頁面，若內存空間已滿，則根據某種算法置換某個頁面，以便裝入新的頁面。請求分段虛擬存儲管理用戶程序要裝入內存時，首先把當前需要的段裝入主存，啟動程序運行，在運行的過程中，若發(fā)現要訪問的段不在內存，則由系統(tǒng)自動裝入所需段，若內存空間已滿，則根據某種算法置換某段，以便裝入新的段。請求段頁式虛擬存儲管理請求分頁+請求分段75第六章存儲管理二、請求分頁虛擬存儲管理請求分頁系統(tǒng)必須解決以下幾個問題：（1）當程序要訪問的某頁不在內存時，如何發(fā)現這種缺頁情況？發(fā)現后應如何處理？（2）當需要把外存上的某個頁面調入內存時，此時內存中沒有空閑物理塊，應置換哪些頁面，置換策略，置換算法。76第六章存儲管理1、頁表機制為了實現請求分頁技術，頁表應增加相應的內容，反映該頁是否在內存，在外存的位置，在內存的時間的長短等。駐留位：指示該頁是否在內存修改位：指示該頁調入內存后是否修改訪問字段：記錄該頁被訪問的次數，或者最近已有多長時間未被訪問，共選擇換出頁面時參考。外存地址：指示該頁在外存上的地址。頁號物理塊號駐留位修改位訪問字段外存地址77第六章存儲管理2、缺頁中斷處理在地址轉換過程中，在頁表中發(fā)現所要訪問的頁不在內存，則產生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調出缺頁中斷處理程序，根據頁表中給出的外存地址，準備將該頁調入內存此時應將缺頁的進程掛起（調頁完成喚醒）78第六章存儲管理指令執(zhí)行和缺頁中斷處理過程啟動一條指令硬件自動將邏輯地址分成頁號和頁內地址該頁在內存嗎？訪問存儲器完成此指令執(zhí)行下一條指令保護現場有空閑塊嗎？裝入所需頁面修改頁表和主存分配表選擇換出頁面調整頁表和主存分配表把該頁寫回外存該頁修改過嗎？是是是否否否硬件軟件缺頁中斷恢復現場79第六章存儲管理缺頁中斷同一般中斷的異同？相同點：保護現場中斷處理恢復現場不同點：缺頁中斷是在一條指令執(zhí)行期間產生和處理中斷，一般中斷是一條指令完成后CPU檢查是否有中斷；一條指令執(zhí)行時可能產生多次缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。80第六章存儲管理3.頁面分配策略固定分配進程保持物理塊數固定不變,稱固定分配;進程創(chuàng)建時,根據進程類型和程序員的要求決定物理塊數,只要有一個缺頁中斷產生,進程就會有一頁被替換?？勺兎峙溥M程分得的物理塊數可變,稱可變分配;進程執(zhí)行的某階段缺頁率較高,說明目前局部性較差，系統(tǒng)可多分些物理塊以降低缺頁率，反之說明進程目前的局部性較好,可減少分給進程的物理塊數。81第六章存儲管理4.頁面替換策略全局替換如果頁面替換算法的作用范圍是整個系統(tǒng)，稱全局頁面替換算法,它可以在運行進程間動態(tài)地分配頁框。局部替換如果頁面替換算法的作用范圍局限于本進程，稱為局部頁面替換算法,它實際上需要為每個進程分配固定的頁框。

82第六章存儲管理固定分配和局部替換策略配合使用進程分得的物理塊數不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁替換，保證進程的物理塊總數不變。

策略難點：應給每個進程分配多少物理塊?給少了,缺頁中斷率高;給多了,使主存中能同時執(zhí)行的進程數減少，進而造成處理器和其它設備空閑。

常用固定分配算法：①平均分配，②按比例分配,③優(yōu)先權分配。83第六章存儲管理可變分配和全局替換策略配合使用先每個進程分配一定數目物理塊,os保留若干空閑物理塊,進程發(fā)生缺頁中斷時，從系統(tǒng)空閑塊中選一個給進程,這樣產生缺頁中斷進程的主存空間會逐漸增大,有助于減少系統(tǒng)的缺頁中斷次數。系統(tǒng)擁有的空閑頁框耗盡時，會從主存中選擇一頁淘汰，該頁可以是主存中任一進程的頁面，這樣又會使那個進程的物理塊數減少，缺頁中斷率上升。84第六章存儲管理可變分配和局部替換配合使用實現要點:(1)新進程裝入主存時，根據應用類型、程序要求，分配給一定數目物理塊。(2)產生缺頁中斷時,從該進程頁面中選一個頁面替換。(3)不時重新評價進程的缺頁率，增加或減少分配給進程的物理塊以改善系統(tǒng)性能。85第六章存儲管理5、頁面置換算法

——PageReplacementAlgorithms當要將一頁面并裝入入到全滿的內存中時，必須把已在內存中的某一頁置換掉。用來選擇置換哪一頁的規(guī)則叫做頁面置換算法。顛簸（抖動）現象在虛存中，頁面在內存與外存之間頻繁調度，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。這種現象稱為顛簸或抖動。例如，一個每隔幾條指令就發(fā)生一次頁面故障的進程稱為在顛簸（因為一條指令的執(zhí)行只需幾納秒，而每從磁盤上讀入一個頁面則常需幾十毫秒）。系統(tǒng)發(fā)生顛簸的原因頁面置換算法不合理分配給進程的物理頁面數太少86第六章存儲管理（1）最佳頁面置換換算法（OPT算法）從內存中置換出以后永不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內不需要訪問的頁。1966年Belady提出的理想算法，但無法實現，因為頁面訪問的順序是很難預知的。主要用于評價其他置換算法。87第六章存儲管理例：設某請求分頁系統(tǒng)采用固定分配局部置換策略，一進程的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2，該進程分得3個物理塊，初始為空。OPT

23215245325223315555555522333333222222444444

xxxxx

x

缺頁次數=6次缺頁率=6/12=50%88第六章存儲管理（2）先進先出頁面置換算法（FIFO算法）置換駐留在內存時間最長的頁面，即先進入內存的頁面先被置換掉。理由是：最先進入內存的頁面不再被訪問的可能性最大。實現簡單：只需把進程在內存的頁面按先后次序鏈成1個隊列，并設置1個替換指針，使它總是指向內存中最老的頁面。缺點：效率不高89第六章存儲管理上例：FIFO

23215245325223315244335222315224435231552243

xxxxxxxxx缺頁次數=9次缺頁率=9/12=75%90第六章存儲管理（3）最近最久未使用頁面置換算法

（LRU算法）選擇在最近一段時間最久未使用的頁面予以置換。根據程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。91第六章存儲管理上例：LRU

23215245325223215