計算機操作系統(tǒng)原理 ch6 存儲管理.ppt

1、1,第六章 存儲管理,主存管理的功能 分區(qū)存貯管理 分頁存儲管理 分段存儲管理 段頁式存儲管理 覆蓋技術與交換技術 虛擬存儲,2,一、主存管理的功能,地址映射 主存分配 存儲保護 主存擴充(虛擬內存),3,地址映射(地址重定位),內存的每個存儲單元都有一個編號，這種編號稱為內存地址（或稱為物理地址，絕對地址）。 內存地址的集合稱為內存空間（或物理地址空間）。,4,要求用戶用內存地址編程是非常困難的，尤其是在多道程序設計的環(huán)境中。 用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址），由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）。,5,6,地址映射的方式,我們把用戶程序裝入內存時對有

2、關指令的地址部分的修改定義為從程序地址到內存地址的地址映射，或稱為地址重定位。 地址映射的方式： 1、靜態(tài)地址映射 2、動態(tài)地址映射,7,1、靜態(tài)地址映射,程序被裝入內存時由操作系統(tǒng)的連接裝入程序完成程序的邏輯地址到內存地址的轉換。,8,映射方法,假定程序裝入內存的首地址為BR，程序地址為VR，內存地址為MR，則地址映射按下式進行：MR=BR+VR 。 例如，程序裝入內存的首地址為1000，則裝配程序就按MR=1000+VR對程序中所有地址部分進行修改，修改后指令Load A，200就變?yōu)長oad A，1200,9,優(yōu)缺點,優(yōu)點：不需要硬件的支持。 缺點：程序必須占用連續(xù)的內存空間；一旦程序裝

3、入后不能移動。,10,2、動態(tài)地址映射,動態(tài)地址重定位是在程序執(zhí)行的過程中，每次訪問內存之前，將要訪問的程序地址轉換為內存地址。一般來說這種轉換是由專門的硬件機構來完成的。,11,映射方法,最簡單的硬件機構是重定位寄存器。 在地址重定位機構中，有一個基地址寄存器BR和一個程序地址寄存器VR，一個內存地址寄存器MR。,12,13,地址映射的具體過程,程序裝入內存后，它所占用的內存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。 在程序執(zhí)行的過程中，若要訪問內存，將訪問的邏輯地址送入VR中。 地址轉換機構把VR和BR中的內容相加，并將結果送入MR中，作為實際訪問的地址。,14,動態(tài)地址映射的優(yōu)缺點,優(yōu)點：

4、 程序占用的內存空間是動態(tài)可變的，當程序從某個存儲區(qū)移到另一個區(qū)域時，只需要修改相應的寄存器BR的內容即可。 一個程序不一定要求占用一個連續(xù)的內存空間。 可以部分地裝入程序運行。 便于多個進程共享同一個程序的代碼。 動態(tài)地址重定位的代價： 需要硬件的支持。 實現(xiàn)存儲管理的軟件算法較為復雜。,15,主存分配與回收,要完成內存的分配和回收工作，要求設計者選擇和確定以下幾種策略和結構： 調入策略 放置策略 置換策略 分配結構,16,調入策略,用戶程序在何時調入內存的策略。 目前有請調和預調兩種,17,放置策略,用戶程序調入內存時，確定將其放置在何處的策略。,18,置換策略,當需要將某個用戶程序調入內

5、存而內存空間又不夠時，就要確定哪個或哪些程序可以從內存中移走。,19,分配結構,分配結構是用來登記內存使用情況的數(shù)據結構。如空閑區(qū)表、空閑區(qū)隊列等。,20,引起內存分配和回收的原因,進程的開始的結束。 進程運行的過程中，它所占用的內存也可能發(fā)生變化。如棧的變化。 進程映像在內存和外存之間傳遞。由于內存有限，系統(tǒng)中不可能容納所有進程，有些進程的映像可以存放在外存，當要運行這些進程時，必須把它們調入內存。 系統(tǒng)為了充分利用內存空間，有時可能對內存空間進行調整。,21,存儲保護,保證在內存中的多道程序只能在給定的存儲區(qū)域內活動并互不產生干擾。 包括： 防止地址越界 防止越權(對共享區(qū)有訪問權),22

6、,存儲保護的硬件支持,界地址寄存器（界限寄存器） 存儲鍵,23,界地址寄存器（界限寄存器）,界地址寄存器被廣泛使用的一種存儲保護技術 機制比較簡單，易于實現(xiàn),24,實現(xiàn)方法,在CPU中設置一對下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址 也可將一個寄存器作為基址寄存器，另一寄存器作為限長寄存器（指示存儲區(qū)長度） 每當CPU要訪問主存，硬件自動將被訪問的主存地址與界限寄存器的內容進行比較，以判斷是否越界 如果未越界，則按此地址訪問主存，否則將產生程序中斷越界中斷（存儲保護中斷）,25,圖示,26,主存擴充(虛擬內存),為了使程序員在編程時不受內存的結構和容量的限制，系統(tǒng)為用戶構造一

7、種存儲器，其結構可能與內存結構不同，容量可能遠遠超過內存的實際容量。這種面向編程的存儲器稱為虛擬存儲器。由虛存構成的存儲空間稱為虛存空間?；蚍Q虛地址空間。,27,實現(xiàn)虛擬內存的基本原理,將程序正在使用的部分內容放在內存，而暫時不用的部分放在外存，在需要時由系統(tǒng)調入內存，并將不需要（或暫不需要）的部分調出內存。 由于程序在執(zhí)行時，在一段時間內一般僅使用它的程序的一部分（或一小部分），所以程序僅有部分裝入內存完全能夠正確執(zhí)行。 要由操作系統(tǒng)結合相關硬件來完成上述工件，這樣計算機好象為用戶提供了一個容量遠大于內存的存儲器，這個存儲器稱為虛擬存儲器。,28,二、分區(qū)存貯管理,把整個內存劃分為若干大小不

8、等的區(qū)域，操作系統(tǒng)占用一個區(qū)域，其它區(qū)域供系統(tǒng)中的多個進程共享，這種方法稱為分區(qū)存儲管理。 這是最簡單的一種存儲管理,按分區(qū)劃分的時機可分為 固定分區(qū) 動態(tài)分區(qū),29,固定分區(qū),固定分區(qū)就是把內存固定地劃分為若干個大小不等的區(qū)域。分區(qū)的劃分由計算機的操作員或者由操作系統(tǒng)給出，并給出分區(qū)說明表。 早期的IBM的OS/360MFT（具有固定任務數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。,30,舉例,某系統(tǒng)的內存容量為256K，操作系統(tǒng)占用低地址的20K，其余空間劃分成4個固定大小的分區(qū)。如下圖,31,圖示,32,分區(qū)說明表,33,固定分區(qū)性能分析,在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合

9、適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當，這樣內存的使用效率較高。 但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，這樣就會造成存儲空間的浪費，從而影響整個系統(tǒng)的效率。,34,動態(tài)分區(qū),動態(tài)分區(qū)是指在系統(tǒng)運行的過程中建立分區(qū)，并使分區(qū)的大小剛好與作業(yè)的大小相等。這種存儲管理的方法解決了固定分區(qū)嚴重浪費內存的問題。是一種較為實用的存儲管理方法。,35,實現(xiàn)動態(tài)分區(qū)需要的數(shù)據結構,在動態(tài)分區(qū)存儲管理中，要有相應的數(shù)據結構來登記空閑區(qū)的說明信息，它包括空閑區(qū)的大小和位置。 不同系統(tǒng)根據設計要求采用不同的結構。常用的有表結構和隊列結構。 系統(tǒng)還要設置了等待分區(qū)隊列，

10、當系統(tǒng)中無空閑區(qū)或無滿足要求的空閑區(qū)時，則把申請者送入等待隊列中，等待別的進程釋放內存之后再喚醒隊列中的進程。,36,空閑區(qū)表和空閑區(qū)隊列舉例,37,動態(tài)分區(qū)的分配和回收,1、分區(qū)的分配 在采用分區(qū)存儲管理的系統(tǒng)中，系統(tǒng)初啟后。除操作系統(tǒng)占用一個分區(qū)外，其余存儲區(qū)為一個大的空閑區(qū)。 分區(qū)的分配是指系統(tǒng)根據用戶的請求，在空閑區(qū)表或空閑區(qū)隊列中尋找一個滿足用戶要求的空閑區(qū)，把這個空閑區(qū)分配給用戶。 以空閑區(qū)表為例，當用戶要求一個大小為SIZE的存儲空間時，系統(tǒng)查詢空閑區(qū)表，找一個大于或等于SIZE的空閑區(qū)。,38,分配時的三種情況,其一是系統(tǒng)中無滿足要求的空閑區(qū)，則分配失敗。 其二是空閑區(qū)大小與S

11、IZE相等，則修改空閑區(qū)表相應表目，向用戶返回該空閑區(qū)首址，表示此空閑區(qū)已分給了要求的用戶。,39,其三是空閑區(qū)大于SIZE，這時將空閑區(qū)一分為二。 將一個空閑區(qū)分成二部分有兩種辦法： 一是從空閑區(qū)的上部開始劃出SIZE大小的空閑區(qū)給用戶； 二是從空閑區(qū)的底部開始向上劃出SIZE大小的空閑區(qū)給用戶。 一般常采用第二種辦法，因為這樣劃分時，余下的部分在空閑區(qū)表中的首地址不變，只需要修改一下大小就行了。,40,分區(qū)的回收,當某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當位置。,41,釋放區(qū)與

12、空閑區(qū)相鄰的四種情況,42,說明,釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。 釋放區(qū)與前后兩個空閑區(qū)相鄰：將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個區(qū)大小之和，并取消原后空閑區(qū)表目。 釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大小之和。 釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當位置。,43,三種放置策略,1、空閑區(qū)表或隊列的排序 2、首次適應法 3、最佳適應法 4、最壞適應法 5、三種策略比較,44,1、空閑區(qū)表或隊列的排序

13、,按空閑區(qū)首址遞增的次序歸類組織空閑區(qū)表或空閑區(qū)隊列 按空閑區(qū)大小的遞增或遞減次序組織空閑區(qū)表或隊列,45,2、首次適應法,要求空閑區(qū)按首址遞增的次序組織空閑區(qū)表（隊列）。,46,分配：當進程申請大小為SIZE的內存時，系統(tǒng)從空閑區(qū)表的第一個表目開始查詢，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小。,47,回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)，將其大小和首址按照首地址大小遞增的順序插入到空閑

14、區(qū)表的適當位置。,48,分析,注意：每次分配和回收后空閑區(qū)表或空閑區(qū)隊列都要按首址遞增的次序排序。 首次適應法的優(yōu)點： 釋放某一存儲區(qū)時，若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去，這種情況并不改變該區(qū)在表中的位置，只要修改其大小或首址。 這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。,49,最佳適應法,要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊列）。,50,分配：當進程申請一個存儲區(qū)時，系統(tǒng)從表頭開始查找，當找到第一個滿足要求的空閑區(qū)時，停止查找，并且這個空閑區(qū)是最佳的空閑區(qū)。 所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。,51,回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊

15、列） ，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)插入空閑區(qū)表（隊列） 。 分配和回收后要對空閑區(qū)表（隊列）重新排序。,52,分析,優(yōu)點： 在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，而首次適應法則不一定。 若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。 缺點： 空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲區(qū)的大量浪費。,53,最壞適應法,要求空

16、閑區(qū)按大小遞減的順序組織空閑區(qū)表（或隊列）。,54,分配：進程申請一個大小為SIZE的存儲區(qū)時，總是檢查空閑區(qū)表的第一個空閑區(qū)的大小是否大于或等于SIZE。若空閑區(qū)小于SIZE，則分配失??；否則從空閑區(qū)中分配SIZE的存儲區(qū)給用戶，然后修改和調整空閑區(qū)表。,55,回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊列） ，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)插入空閑區(qū)表（隊列） 。 分配和回收后要對空閑區(qū)表（隊列）重新排序。,56,分析,最壞適應法看起來公似乎有些荒唐，但在更加嚴密地考察后，還是有它的優(yōu)點： 當程序裝入內存中最大的空閑區(qū)后，剩

17、下的空閑區(qū)還可能相當大，還能裝下較大的程序。 另一方面每次僅作一次查詢工作。,57,三種策略比較,上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應針對具體作業(yè)序列來分析。 對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。 對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。,58,舉例,例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊列,59,60,經分析可知：最佳適應法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是

18、不合適的。,61,練習,有作業(yè)序列：作業(yè)A要求21K；作業(yè)B要求30K，作業(yè)C要求25K。,62,碎片問題,由于空閑區(qū)的大小與申請內存的大小相等的情況是很少的，絕大多數(shù)情況是從一個空閑區(qū)中切去一塊，剩下的部分作為一個空閑區(qū)仍留在空閑區(qū)表中，隨著時間的推移，空閑區(qū)的發(fā)展趨勢是越來越小，直至不能滿足任何用戶要求。 這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲空間的浪費。,63,在分區(qū)存儲管理中解決碎片的辦法,規(guī)定門限值（由操作系統(tǒng)規(guī)定，如1K），分割空閑區(qū)時，若剩余部分小于門限值，則不再分割此空閑區(qū)。 定期壓縮存儲空間，將所有空閑區(qū)集中到內存的一端，但這種方法的系統(tǒng)開銷太大。

19、,64,三、分頁存儲管理,分頁存儲管理基本思想 頁地址映射 頁式存儲管理方案小結,65,分頁存儲管理基本思想,在分區(qū)存儲管理中，不論采用什么辦法都會出現(xiàn)碎片問題，從而降低了內存的利用率。雖然采用壓縮存儲區(qū)的方法可以解決碎片問題，但系統(tǒng)開銷太大，而無實用價值，必須尋求新的技術來解決這一問題，于是分頁技術產生了。 分頁技術是由曼徹斯特大學提出，并于1960年前后在Atlas計算機上實現(xiàn)。這種技術對操作系統(tǒng)的發(fā)展產生了深遠影響。,66,用戶程序劃分 把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page） 。從0開始編制頁號，頁內地址是相對于0編址,67,邏輯地址 用戶程序的劃分是由系統(tǒng)自動完成的

20、，對用戶是透明的。一般，一頁的大小為2的整數(shù)次冪，因此，地址的高位部分為頁號，低位部分為頁內地址,68,內存空間 按頁的大小劃分為大小相等的區(qū)域，稱為塊或內存塊（物理頁面，頁框）,69,內存分配 以頁為單位進行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰,70,71,頁地址映射,1、頁表 2、頁大小的選擇 3、頁地址映射 4、分頁存儲管理中的信息保護 5、快表和聯(lián)想存儲器 6、兩級頁表和多級頁表,72,1、頁表,將頁號和頁內地址轉換成內存地址，必須要有一個數(shù)據結構，用來登記頁號和塊的對應關系和有關信息。 這樣的數(shù)據結構稱為頁表。,73,系統(tǒng)為每個進程建立一個頁表，頁表的長度

21、和首地址存放在該進程的進程控制塊（PCB）中。 占用處理機的現(xiàn)行進程的頁表必須駐留在內存，其首地址和長度由地址映射機構的頁表起址和長度寄存器指示。,74,頁表內容,頁表包含以下幾個表項： 頁號：登記程序地址空間的頁號。 塊號：登記相應的頁所對應的內存塊號 其它：登記與存儲信息保護有關的信息。,75,例,如圖，作業(yè)1有2頁分別裝入內存的第5、6塊；作業(yè)2有3頁裝入內存的第2、4、7塊；作業(yè)3有1 頁裝入內存的第8塊。,76,2、頁大小的選擇,太大：浪費；太?。喉摫磉^長。 IBM AS/400 VAX NS32032 ：512字節(jié) Intel 80386 Motorola 68030 4096字節(jié)

22、 頁的大小是2K ， k： 9-12。,77,3、頁地址映射,分頁中的地址映射其實與通常的地址映射的概念是一樣的，即把程序地址轉換成內存地址，這個轉換過程是在程序執(zhí)行過程中完成的，是動態(tài)地址映射。 在現(xiàn)代計算機系統(tǒng)中，由系統(tǒng)提供的地址映射硬件來完成地址映射工作。,78,例,設頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖。,79,說明,在執(zhí)行指令MOV r1，2500時，地址轉換步驟如下： 取出程序地址字2500送虛地址寄存器VR，然后由硬件分離出頁號P和頁內地址W，實際上分離出頁號和頁內地址是一件很簡單的事，因為頁長為1K，所以頁內地址占10位（0-9位），頁號占6位（10-15位

23、），所以硬件只要簡單地取出VR寄存器中的高6位即為頁號，低10 位即為頁內地址。 當然我們通過計算可以得到P=2，W=452。,80,根據頁號P=2，硬件自動查該進程的頁表，找到第2頁對應的塊號為7，將塊號送到內存地址寄存器MR的高10位中。 將VR中的W的值452復制到MR的低10位中，從而形成內存地址。系統(tǒng)就以MR中的地址訪問內存 硬件能自動分離出頁號和頁內地址，但我們只能通過計算才能得到。,81,計算時要注意： 若給出的地址字為16進制，則將其轉換為二進制，然后，根據頁長及程序地址字的長度，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內地址。如頁長為2K，程序地址字為16位，則高5位

24、為頁號，低11位為頁內地址。,82,若給出的地址字為10進制，則用公式： 程序地址字/頁長 商為頁號，余數(shù)為頁內地址。 如程序地址為8457， 頁長為4KB，則8457/4096可得：商為2，余數(shù)為265。,83,4、分頁存儲管理中的信息保護,分頁存儲管理中的存儲信息保護從兩個方面來實現(xiàn)。 一、在分離程序地址字的頁號和頁內地址時判別訪問是否合法，若產生的頁號滿足下式為合法： 0=頁號程序地址空間的頁數(shù) 上述判斷由硬件自動做，若不合法，硬件產生越界中斷，由操作系統(tǒng)的越界中斷處理程序進行處理。,84,二、在頁表中增加用于存取控制和存儲保護的信息，當要訪問某頁時系統(tǒng)要根據該頁的存取控制和存儲保護信息

25、檢查訪問是否合法。（主要用來判斷訪問是否越權）,85,5、快表和聯(lián)想存儲器,在前述的頁地址變換過程中有一個嚴重的問題，那就是每一次對內存的訪問都要訪問頁表，頁表是放在內存中的，也就是說每一次訪問內存的指令至少要訪問兩次內存，運行速度要下降一半。 若不解決這一問題是不能令人忍受的。,86,解決這個問題的一種方法是把頁表放在一組快速存儲器中（Cache），從而加快訪問內存的速度。我們把這種快速存儲器組成的頁表稱為快表，把存放在內存中的頁表稱為慢表。 快表又叫相聯(lián)(聯(lián)想)存儲器（associative memory）或 TLB（Translation lookaside buffers）,87,討論

26、,深入一點的討論： 一個程序可能會很大，如1M，若頁長為1K，則該程序有1000個頁，則該程序的頁表就需要1000個表項，當程序更大時，頁表會更大，那么我們應該有一個多大的快速存儲器才能滿足要求呢？這會遇到兩個問題： 可能快速存儲器多大都是不夠的，因為程序可能會更大。 快速存儲器是非常非常昂貴的。,88,實際上我們并不需要一個很大的快速存儲器，有一個能存放16個頁表表目的快速存儲器就夠了。 硬件根據需要將頁表中當前需要的少量表目讀入快表，其它表目仍留在內存的頁表中，當需要時讀入新的表目，并淘汰適當?shù)谋砟俊?快表表項： 頁號；內存塊號；標識位；淘汰位,89,90,分析,當調度合理時，可以達到97

27、的效率。也就是說訪問頁表的速度大致相當了訪問快表的速度，考慮到快表的速度是內存速度的數(shù)倍或數(shù)十倍，那么相對于內存速度，訪問頁表的時間可以忽略不計。也就是說頁地址變換不會造成進程運行速度的下降。,91,6、兩級頁表和多級頁表,當頁表項很多時，僅采用一級頁表需要大片連續(xù)空間，可將頁表也分頁，并對頁表所占的空間進行索引形成外層頁表。由此構成二級頁表。 更進一步可形成多級頁表。,92,二級頁表結構及地址映射,93,圖: 三級頁表結構及其地址映射過程,94,頁式存儲管理方案小結,優(yōu)點：解決了碎片問題 便于管理 缺點：不易實現(xiàn)共享 不便于動態(tài)連接,95,四、分段存儲管理,分段存儲管理基本思想 段地址映射

28、段式存儲管理方案小結,96,分段存儲管理基本思想,用戶程序劃分 按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內也從0開始編址，段內地址是連續(xù)的 邏輯地址,97,內存劃分 內存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定 內存分配 以段為單位分配內存，每一個段在內存中占據連續(xù)空間（內存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放,98,0,116,N,99,操作系統(tǒng),100,段地址映射,1、 地址映射數(shù)據結構 段地址映射的數(shù)據結構有段表、段表首址指針和段表的長度。段表首址指針和段表長度存放在

29、進程自己的PCB中。段表一般包括有段的長度、段的首址和存取狀態(tài)等信息。 每一進程有個段表，程序的每一個段在段表中占用一個表目。,101,2、內存的分配,空閑塊管理 空閑塊表（隊列） 內存分配算法（三種） 首次 最佳 最壞 與動態(tài)分區(qū)管理相同,102,3、段地址變換,段地址變換由硬件地址變換機構完成,103,說明,段地址映射過程為： 程序地址字送入虛地址寄存器VR中。 取出段號S和段內位移W。 根據段表首址指針找到段表，查找段號為S的表目，得到該段的首地址。 把段首地址與段內位移相加，形成內存地址送入MR中，并以此地址訪問內存。,104,4、快表,同頁地址變換一樣，在段地址變換過程中，也有兩次訪

30、問內存的問題。為了加快訪問內存的速度也可采用快速存儲器組成快表。,105,Cl,Cb,+,段號S 段內地址d,比較,比較,b + d,段表,S= Cl,快表,物理地址,段表始址寄存器,段表長度寄存器,邏輯地址,L,b,.,.,.,S,L,b,地址越界,d=L,d=L,地址映射及存儲保護機制,地址越界,地址越界,比較,106,5、分段與分頁技術的比較,分段與分頁主要有以下差別： 段是依據程序的邏輯結構劃分的，頁是按內存線性空間物理劃分的。 段式技術中程序地址空間是二維的，分頁技術中程序地址空間是一維的。 段是面向用戶的，頁對用戶而言是透明的。,107,段長由用戶決定，且各段的大小一般不相等，唯一

31、的限制是最大長度。而頁長是由系統(tǒng)決定的，各頁的長度必須相等。 段的共享比頁的共享更容易。,108,段式存儲管理方案小結,優(yōu)點： 便于動態(tài)申請內存 管理和使用統(tǒng)一化 便于共享 便于動態(tài)鏈接 缺點：產生碎片 思考：與可變分區(qū)存儲管理方案的相同點與不同點？,109,五、段頁式存儲管理方式,產生背景: 結合頁式段式優(yōu)點，克服二者的缺點 段頁式存儲管理基本思想 地址映射,110,段頁式存儲管理基本思想,用戶程序劃分 按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統(tǒng)講，按頁劃分每一段） 邏輯地址 內存劃分 按頁式存儲管理方案 內存分配 以頁為單位進行分配,111,段表：記錄了每一段的頁表始址和頁表長

32、度 頁表：記錄了邏輯頁號與內存塊號的對應關系（每一段有一個，一個程序可能有多個頁表） 內存分配管理：同頁式管理,地址映射,112,圖示,113,思考,在具有快表的段頁式存儲管理方案中，如何實現(xiàn)地址變換？,114,六、覆蓋技術與交換技術,1、為什么引入？ 在多道環(huán)境下擴充內存的方法，用以解決在較小的存儲空間中運行較大程序時遇到的矛盾 覆蓋技術主要用在早期的操作系統(tǒng)中 交換技術被廣泛用于小型分時系統(tǒng)中，交換技術的發(fā)展導致了虛存技術的出現(xiàn),115,交換技術與覆蓋技術共同點： 進程的程序和數(shù)據主要放在外存，當前需要執(zhí)行的部分放在內存，內外存之間進行信息交換 不同點：如何控制交換？,116,2、覆蓋技術

33、,把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結構將那些不會同時執(zhí)行的程序段共享同一塊內存區(qū)域 程序段先保存在磁盤上，當有關程序段的前一部分執(zhí)行結束，把后續(xù)程序段調入內存，覆蓋前面的程序段（內存“擴大”了） 覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間 一般要求作業(yè)各模塊之間有明確的調用結構，程序員要向系統(tǒng)指明覆蓋結構，然后由由操作系統(tǒng)完成自動覆蓋,117,圖示,118,缺點： 對用戶不透明，增加了用戶負擔 例子：目前這一技術用于小型系統(tǒng)中的系統(tǒng)程序的內存管理上，MS-DOS的啟動過程中，多次使用覆蓋技術；啟動之后，用戶程序區(qū)TPA的高端部分與COMMAND

34、.COM暫駐模塊也是一種覆蓋結構,分析,119,3、交換技術,為什么引入交換技術？ 當內存空間緊張時，系統(tǒng)將內存中某些進程暫時移到外存，把外存中某些進程換進內存，占據前者所占用的區(qū)域，這種技術是進程在內存與外存之間的動態(tài)調度 多用于分時系統(tǒng)中,120,交換技術實現(xiàn)中的幾個問題,選擇原則 即：將哪個進程換出內存？ 例子：分時系統(tǒng)，時間片輪轉法或基于優(yōu)先數(shù)的調度算法，在選擇換出進程時，換出要長時間等待的進程。,121,交換時機的確定,何時需發(fā)生交換？ 例子： 只要不用就換出（或很少再用） 只在內存空間不夠或有不夠的危險時換出,122,交換時需要做哪些工作？,需要一個盤交換區(qū)： 必須足夠大以存放用戶

35、程序的內存映像的拷貝； 必須對這些內存映像直接存取。,123,換入回內存時位置的確定,換出后再換入的內存位置一定要在換出前的原來位置上嗎？ 受地址映射技術的影響，即絕對地址產生時機的限制,124,分析,與覆蓋技術相比，交換技術不要求用戶給出程序段之間的邏輯覆蓋結構； 交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內。 覆蓋只能覆蓋那些與覆蓋段無關的程序段,125,七、虛擬存儲,以CPU時間和外存空間換取昂貴內存空間，這是操作系統(tǒng)中的資源轉換技術 概述 虛擬頁式存儲管理 虛擬段式存儲管理,126,概述,程序局部性原理 時間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行 空間局部性

36、若某一存儲單元被使用，則在一定時間內，與該存儲單元相鄰的單元可能被使用,127,虛擬頁式存儲管理,1、基本思想 在進程開始運行之前，不是裝入全部頁面，而是裝入幾個或零個頁面，之后根據進程運行的需要，動態(tài)裝入其它頁面； 當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面,128,129,2、頁表表項,頁號、內存塊號、駐留位、外存地址、訪問位、修改位 駐留位（中斷位）：表示該頁是在內存還是在外存 訪問位：根據訪問位來決定淘汰哪頁（由不同的算法決定） 修改位：查看此頁是否在內存中被修改過,130,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1

37、,000,0,000,0,000,0,000,0,111,1,000,0,101,1,000,0,000,0,000,0,011,1,100,1,000,1,110,1,001,1,010,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,110,在/不在內存,頁表,虛地址 8196,物理地址 24580,131,3、缺頁中斷（Page Fault）處理,在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內存，則產生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調出缺頁中斷處理程序，根據頁表中給出的外存地址，準備將該頁調入內

38、存 此時應將缺頁的進程掛起（調頁完成喚醒）,132,如果內存中有空閑塊，則分配一個塊，將要調入的頁裝入該塊，并修改頁表中相應頁表項目的駐留位及相應的內存塊號 若此時內存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內存期間被修改過，則要將其寫回外存）,133,思考,缺頁中斷同一般中斷的區(qū)別？,134,缺頁中斷同一般中斷都是中斷，相同點是： 保護現(xiàn)場 中斷處理 恢復現(xiàn)場 不同點： 一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時中斷 一條指令執(zhí)行時可能產生多個缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。,135,4、頁面淘汰算法,先進先出頁面淘汰算法（FIFO） 選擇在內存中駐留

39、時間最長的頁并淘汰之 第二次機會淘汰算法 (SCR) 按照先進先出算法選擇某一頁面，檢查其訪問位，如果為0，則淘汰該頁，如果為1，則給第二次機會，并將訪問位置0 理想淘汰算法最佳頁面算法（OPT） 淘汰以后不再需要的或最遠的將來才會用到的頁面,136,最近最久未使用頁面淘汰算法（LRU） 選擇最后一次訪問時間距離當前時間最長的一頁并淘汰之 即淘汰沒有使用的時間最長的頁 實現(xiàn)代價很高 軟件方法或硬件方法,137,LRU的硬件解法： 系統(tǒng)為每頁設置一個寄存器R，每當訪問這一頁時，將該頁對應的寄存器R置1，以后每個時間間隔將所有的R左移一位，當淘汰一頁時就選擇R值最大的頁。也就是說R值越大，對應的頁

40、未被使用的時間越長。所以淘汰的是最久未使用的頁。顯然，R的位數(shù)越多越精確。但系統(tǒng)硬件成本也就越高。,138,LRU軟件解法： 設置一個頁號棧，當一個頁面被訪問時，就立即將它的頁號壓入頁號棧，并檢查頁號棧中是否有與剛壓入棧頂?shù)南嗤捻撎枺粲?，則從頁號棧中抽出，以保證頁號棧中無相同的頁號。當系統(tǒng)要淘汰一節(jié)時，總是從頁號棧底取出一個頁號淘汰，即淘汰的頁是最久未使用的。,139,LRU近似算法： 在頁表中增加一訪問位，每當訪問一頁時，將該頁的訪問位由硬件置1，軟件周期（T）性地將所有訪問位置0。在時間T內，訪問過的頁其訪問位為1，反之為0，淘汰為0 的頁。 缺點：T難定。太小，訪問位為0的頁相當多，

41、所選的不一定是最久未用的。太大，所有頁的引用位可能都為1，找不到合適的淘汰頁。,140,最不經常使用（LFU） 選擇訪問次數(shù)最少的頁面淘汰之 與LRU的硬件解法類似。,141,某程序在內存中分配三個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分別計算缺頁次數(shù) 假設開始時所有頁均不在內存,例1,142,FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁1 4 3 2 1 4 3 5 5 5 2 1 1 頁2 4 3 2 1 4 3 3 3 5 2 2 頁3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x

42、共缺頁中斷9次,FIFO,143,LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁1 4 3 2 1 4 3 5 4 3 2 1 5 頁2 4 3 2 1 4 3 5 4 3 2 1 頁3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x 共缺頁中斷10次,LRU,144,OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁1 4 3 2 1 1 1 5 5 5 2 1 1 頁2 4 3 3 3 3 3 3 3 5 5 5 頁3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺頁中斷7次,OPT,145,練習,某程序在內存中分配四個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5