操作系統(tǒng)教程-第3章存儲器管理.

1、第 3章 存儲器管理 操作系統(tǒng)教程主編主編 何櫻何櫻 連衛(wèi)民連衛(wèi)民中國水利水電出版社中國水利水電出版社第 3章 存儲器管理 第第 3 章存儲器管理章存儲器管理3.1 存儲器管理概述存儲器管理概述3.2 單用戶連續(xù)存儲管理方式單用戶連續(xù)存儲管理方式3.3 固定分區(qū)存儲管理方式固定分區(qū)存儲管理方式3.4 可變分區(qū)存儲管理方式可變分區(qū)存儲管理方式3.5 分頁式存儲管理方式分頁式存儲管理方式3.6 分段式存儲管理方式分段式存儲管理方式3.7 段頁式存儲管理方式段頁式存儲管理方式3.8 虛擬存儲管理方式虛擬存儲管理方式第 3章 存儲器管理 3.1 存儲器管理概述存儲器管理概述 存儲管理的主要任務是盡可能

2、方便用戶和提高主存儲器存儲管理的主要任務是盡可能方便用戶和提高主存儲器的使用效率，使主存儲器在成本、速度和規(guī)模之間獲得較的使用效率，使主存儲器在成本、速度和規(guī)模之間獲得較好的權(quán)衡。好的權(quán)衡。3.1.1 存儲器管理的主要功能存儲器管理的主要功能 1主存空間的分配和回收主存空間的分配和回收 2地址轉(zhuǎn)換地址轉(zhuǎn)換 3主存空間的共享與保護主存空間的共享與保護 4主存空間的擴充主存空間的擴充第 3章 存儲器管理 3.1.2 存儲器的層次存儲器的層次 目前，計算機均采用分層結(jié)構(gòu)的存儲子系統(tǒng)，以便在容量、速度目前，計算機均采用分層結(jié)構(gòu)的存儲子系統(tǒng)，以便在容量、速度和價格等因素中獲得較好的性價比。和價格等因素中

3、獲得較好的性價比。 圖中，上面的速度快，下面的容量大。寄存器、高速緩存、主存圖中，上面的速度快，下面的容量大。寄存器、高速緩存、主存和磁盤緩存屬于和磁盤緩存屬于OS存儲管理范圍，掉電后數(shù)據(jù)丟失；固定磁盤和可存儲管理范圍，掉電后數(shù)據(jù)丟失；固定磁盤和可移動存儲介質(zhì)屬于設備管理范圍，數(shù)據(jù)可長期保存；磁盤緩存本身并移動存儲介質(zhì)屬于設備管理范圍，數(shù)據(jù)可長期保存；磁盤緩存本身并不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存空間不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存空間的擴充。的擴充。寄存器寄存器高速緩存高速緩存主存儲器主存儲器磁盤緩存磁盤緩存固定磁盤固定磁盤可移動存儲介質(zhì)可移動

4、存儲介質(zhì)存儲管理設備管理第 3章 存儲器管理 寄存器訪問速度最快且最昂貴，它容量小，以字（寄存器訪問速度最快且最昂貴，它容量小，以字（word）為單位。一個計算機系統(tǒng)可能包括幾十個至上百）為單位。一個計算機系統(tǒng)可能包括幾十個至上百個寄存器，用于提高存儲訪問速度。比如，用寄存存放操個寄存器，用于提高存儲訪問速度。比如，用寄存存放操作數(shù)，或用地址寄存器加快地址轉(zhuǎn)換速度。作數(shù)，或用地址寄存器加快地址轉(zhuǎn)換速度。 高速緩存的容量稍大，速度快于主存，利用它存放主高速緩存的容量稍大，速度快于主存，利用它存放主存中馬上要訪問的指令，可大大提高執(zhí)行速度。主存的速存中馬上要訪問的指令，可大大提高執(zhí)行速度。主存的速

5、度為度為1s，高速緩存為，高速緩存為0.1s。 要執(zhí)行的程序必須先裝入主存，根據(jù)局部性原理，只要執(zhí)行的程序必須先裝入主存，根據(jù)局部性原理，只要將程序的一部分裝入主存就可以執(zhí)行，其余部分放在磁要將程序的一部分裝入主存就可以執(zhí)行，其余部分放在磁盤緩存。盤緩存。第 3章 存儲器管理 高速緩存（高速緩存（cache） 高速緩存是現(xiàn)代計算機結(jié)構(gòu)中的一個重要部件。高速緩存是現(xiàn)代計算機結(jié)構(gòu)中的一個重要部件。 有些有些cache由硬件實現(xiàn)由硬件實現(xiàn) 如，指令如，指令cache，用于暫存下一條欲執(zhí)行的指令，純硬，用于暫存下一條欲執(zhí)行的指令，純硬件件cache不需要不需要os控制?？刂?。 有些有些cache由程序

6、員、編譯系統(tǒng)和由程序員、編譯系統(tǒng)和os實現(xiàn)實現(xiàn) 如，快表。如，快表。 在采用在采用cache的系統(tǒng)中，要注意解決數(shù)據(jù)的一致性問題的系統(tǒng)中，要注意解決數(shù)據(jù)的一致性問題。因為這時數(shù)據(jù)可能出現(xiàn)在不同的層次上。在多處理機的。因為這時數(shù)據(jù)可能出現(xiàn)在不同的層次上。在多處理機的環(huán)境中，情況會更復雜。環(huán)境中，情況會更復雜。第 3章 存儲器管理 3.1.3 地址轉(zhuǎn)換地址轉(zhuǎn)換 源程序經(jīng)過編譯后得到的目標程序存在于它所限定的源程序經(jīng)過編譯后得到的目標程序存在于它所限定的地址范圍內(nèi)，這個范圍稱為地址空間。它總是從地址范圍內(nèi)，這個范圍稱為地址空間。它總是從0開始編開始編址，是一個相對于實際起始地址的相對地址，也稱為邏輯

7、址，是一個相對于實際起始地址的相對地址，也稱為邏輯地址。當將其裝入內(nèi)存后得到的地址才是其真正的內(nèi)存存地址。當將其裝入內(nèi)存后得到的地址才是其真正的內(nèi)存存儲地址，這個地址稱為物理地址或絕對地址。儲地址，這個地址稱為物理地址或絕對地址。 把程序和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址的過程稱為把程序和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址的過程稱為地址轉(zhuǎn)換或重定位。地址轉(zhuǎn)換有兩種方式，一種方式是在地址轉(zhuǎn)換或重定位。地址轉(zhuǎn)換有兩種方式，一種方式是在作業(yè)裝入時由作業(yè)裝入程序?qū)崿F(xiàn)地址轉(zhuǎn)換，稱為靜態(tài)地址作業(yè)裝入時由作業(yè)裝入程序?qū)崿F(xiàn)地址轉(zhuǎn)換，稱為靜態(tài)地址轉(zhuǎn)換；另一種方式是在程序執(zhí)行時實現(xiàn)地址轉(zhuǎn)換，稱為動轉(zhuǎn)換；另一種方式是在程序執(zhí)

8、行時實現(xiàn)地址轉(zhuǎn)換，稱為動態(tài)地址轉(zhuǎn)換。態(tài)地址轉(zhuǎn)換。 第 3章 存儲器管理 1靜態(tài)重定位靜態(tài)重定位 靜態(tài)重定位是在程序執(zhí)行之前，由作業(yè)裝入程序?qū)⒊天o態(tài)重定位是在程序執(zhí)行之前，由作業(yè)裝入程序?qū)⒊绦蜓b入內(nèi)存，同時實現(xiàn)地址轉(zhuǎn)換。一旦確定下來的地址就序裝入內(nèi)存，同時實現(xiàn)地址轉(zhuǎn)換。一旦確定下來的地址就不再改變。不再改變。 LOAD A,12500 36510000110001250015000LOAD A,2500 3655000010002500圖圖3-2 作業(yè)裝入主存時的情況作業(yè)裝入主存時的情況作業(yè)主存第 3章 存儲器管理 特點：靜態(tài)重定位程序在內(nèi)存中不能移動，而且必須連續(xù)存放。特點：靜態(tài)重定位程序在內(nèi)

9、存中不能移動，而且必須連續(xù)存放。優(yōu)點：不需要增加硬件地址變換裝置，實現(xiàn)簡單。優(yōu)點：不需要增加硬件地址變換裝置，實現(xiàn)簡單。缺點：缺點： 程序占用連續(xù)的存儲空間。程序占用連續(xù)的存儲空間。 如果沒有足夠大的連續(xù)空間，作業(yè)只能等待。如果沒有足夠大的連續(xù)空間，作業(yè)只能等待。 不能實現(xiàn)虛擬存儲技術(shù)。不能實現(xiàn)虛擬存儲技術(shù)。 因為程序只能一次完全裝入內(nèi)存。因為程序只能一次完全裝入內(nèi)存。 無法實現(xiàn)程序的共享。無法實現(xiàn)程序的共享。 不能尋址存儲區(qū)，每個程序的尋址范圍只在自己的存儲區(qū)不能尋址存儲區(qū)，每個程序的尋址范圍只在自己的存儲區(qū)范圍內(nèi)。范圍內(nèi)。 第 3章 存儲器管理 2動態(tài)重定位動態(tài)重定位 動態(tài)重定位是在程序執(zhí)

10、行過程中，隨著每條指令和數(shù)據(jù)的訪動態(tài)重定位是在程序執(zhí)行過程中，隨著每條指令和數(shù)據(jù)的訪問自動地連續(xù)地進行轉(zhuǎn)換，這種重定位的實現(xiàn)需要硬件的幫助問自動地連續(xù)地進行轉(zhuǎn)換，這種重定位的實現(xiàn)需要硬件的幫助，一般是靠硬件地址變換機構(gòu)實現(xiàn)的。，一般是靠硬件地址變換機構(gòu)實現(xiàn)的。特點：動態(tài)重定位程序在內(nèi)存中可不連續(xù)存放，并可在內(nèi)存中移動特點：動態(tài)重定位程序在內(nèi)存中可不連續(xù)存放，并可在內(nèi)存中移動。優(yōu)點：優(yōu)點： 可以對主存不連續(xù)分配，靈活、方便，存儲效率高?？梢詫χ鞔娌贿B續(xù)分配，靈活、方便，存儲效率高。 可以實現(xiàn)虛擬存儲技術(shù)。可以實現(xiàn)虛擬存儲技術(shù)。 可以實現(xiàn)程序的共享?？梢詫崿F(xiàn)程序的共享。缺點：缺點： 需要增加硬件（

11、界限寄存器、頁表寄存器）。需要增加硬件（界限寄存器、頁表寄存器）。 實現(xiàn)存儲管理的軟件算法比較復雜。實現(xiàn)存儲管理的軟件算法比較復雜。第 3章 存儲器管理 3.1.4 存儲管理方式存儲管理方式全部裝入全部裝入部分裝入部分裝入連續(xù)分配連續(xù)分配單用戶連續(xù)存儲管理方式單用戶連續(xù)存儲管理方式分區(qū)分配分區(qū)分配固定分區(qū)存儲管理方式固定分區(qū)存儲管理方式可變分區(qū)存儲管理方式可變分區(qū)存儲管理方式分頁式存儲管理方式分頁式存儲管理方式分段式存儲管理方式分段式存儲管理方式段頁式存儲管理方式段頁式存儲管理方式非連續(xù)分配非連續(xù)分配 請求分頁式虛擬存儲管理方式請求分頁式虛擬存儲管理方式請求分段式虛擬存儲管理方式請求分段式虛擬

12、存儲管理方式圖圖3-3 存儲管理方式層次圖存儲管理方式層次圖第 3章 存儲器管理 3.2 單用戶連續(xù)存儲管理方式單用戶連續(xù)存儲管理方式 3.2.1 基本原理基本原理 單用戶連續(xù)存儲管理方式是一種最簡單的存儲管理方單用戶連續(xù)存儲管理方式是一種最簡單的存儲管理方式，在這種管理方式下，在主存中僅駐留一道程序，整式，在這種管理方式下，在主存中僅駐留一道程序，整個用戶區(qū)為一個用戶所獨占。當用戶作業(yè)空間大于用戶個用戶區(qū)為一個用戶所獨占。當用戶作業(yè)空間大于用戶區(qū)時，該作業(yè)不能裝入。這種分配方式僅能用于單用戶區(qū)時，該作業(yè)不能裝入。這種分配方式僅能用于單用戶、單任務的操作系統(tǒng)中，不能用于多用戶系統(tǒng)和單用戶、單任

13、務的操作系統(tǒng)中，不能用于多用戶系統(tǒng)和單用戶多任務系統(tǒng)中。多任務系統(tǒng)中。第 3章 存儲器管理 3.2.2 主存空間的分配與回收主存空間的分配與回收1主存空間的分配主存空間的分配 主存空間分為兩個區(qū)：系統(tǒng)區(qū)和用戶區(qū)。主存空間分為兩個區(qū)：系統(tǒng)區(qū)和用戶區(qū)。（1）系統(tǒng)區(qū)）系統(tǒng)區(qū) 供操作系統(tǒng)使用，操作系統(tǒng)的常駐內(nèi)存部分存放在這供操作系統(tǒng)使用，操作系統(tǒng)的常駐內(nèi)存部分存放在這里。比如，里。比如，DOS的的文件（內(nèi)部命令解釋程文件（內(nèi)部命令解釋程序）。序）。（2）用戶區(qū)）用戶區(qū) 存放用戶作業(yè)。只能存放一道作業(yè)，并且這個程序不存放用戶作業(yè)。只能存放一道作業(yè)，并且這個程序不能大于內(nèi)存容量。能大于內(nèi)存容量。第 3章

14、存儲器管理 2主存空間的回收主存空間的回收 程序執(zhí)行完畢，系統(tǒng)全部回收所有主存空間，再分配程序執(zhí)行完畢，系統(tǒng)全部回收所有主存空間，再分配給下一個作業(yè)。給下一個作業(yè)。（只要設置一個狀態(tài)：（只要設置一個狀態(tài)：“空空”或或“不空不空”）第 3章 存儲器管理 3.2.2 管理特點管理特點 簡單：一次全部分配，一次全部回收。簡單：一次全部分配，一次全部回收。 資源利用率低：每次只運行一個作業(yè)。資源利用率低：每次只運行一個作業(yè)。 第 3章 存儲器管理 3.3 固定分區(qū)存儲管理方式固定分區(qū)存儲管理方式 3.3.1 基本原理基本原理 將用戶區(qū)劃分為多個固定大小的區(qū)域，每個區(qū)域稱為將用戶區(qū)劃分為多個固定大小的區(qū)

15、域，每個區(qū)域稱為一個分區(qū)，每個分區(qū)可裝入一個作業(yè)，每個作業(yè)只能裝入一個分區(qū)，每個分區(qū)可裝入一個作業(yè)，每個作業(yè)只能裝入一個分區(qū)。一個分區(qū)。分區(qū)的劃分方法：分區(qū)的劃分方法： 1分區(qū)大小相等分區(qū)大小相等 優(yōu)點：劃分方法簡單。優(yōu)點：劃分方法簡單。 缺點：大分區(qū)放小程序缺點：大分區(qū)放小程序浪費浪費 小分區(qū)放大程序小分區(qū)放大程序程序無法運行程序無法運行 2分區(qū)大小不等分區(qū)大小不等 在主存中劃分出多個較小的分區(qū)、適量的中等分區(qū)及在主存中劃分出多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣就可以滿足不同大小程序的要求。少量的大分區(qū)。這樣就可以滿足不同大小程序的要求。第 3章 存儲器管理 3.3.2 主存空

16、間的分配與回收主存空間的分配與回收1采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) 設置了一張分區(qū)分配表。分區(qū)分配表的內(nèi)容包括分設置了一張分區(qū)分配表。分區(qū)分配表的內(nèi)容包括分區(qū)號、起始地址、大小、狀態(tài)。分區(qū)表如下表所示。區(qū)號、起始地址、大小、狀態(tài)。分區(qū)表如下表所示。第 3章 存儲器管理 2主存空間的分配主存空間的分配 在初始狀態(tài)下，狀態(tài)欄的初值為在初始狀態(tài)下，狀態(tài)欄的初值為0。主存空間的分配步驟為：主存空間的分配步驟為：從作業(yè)隊列取出一個作業(yè)。從作業(yè)隊列取出一個作業(yè)。搜索分區(qū)表中狀態(tài)為搜索分區(qū)表中狀態(tài)為“0”的分區(qū)。的分區(qū)。將作業(yè)大小與分區(qū)大小進行比較，直到找到滿足條件的將作業(yè)大小與分區(qū)大小進行比較，直到找到滿足

17、條件的分區(qū)。分區(qū)。若未找到滿足條件的分區(qū)，則給出提示信息，返回第若未找到滿足條件的分區(qū)，則給出提示信息，返回第步。步。把作業(yè)裝入該分區(qū)，作業(yè)名寫入狀態(tài)欄。返回第步。把作業(yè)裝入該分區(qū)，作業(yè)名寫入狀態(tài)欄。返回第步。第 3章 存儲器管理 3主存空間的回收主存空間的回收 根據(jù)作業(yè)名到分區(qū)表的狀態(tài)欄中查找，找到后將狀態(tài)根據(jù)作業(yè)名到分區(qū)表的狀態(tài)欄中查找，找到后將狀態(tài)欄置欄置“0”，表示該分區(qū)空閑，可以用來裝入新的作業(yè)。，表示該分區(qū)空閑，可以用來裝入新的作業(yè)。3.3.3 地址轉(zhuǎn)換與存儲保護地址轉(zhuǎn)換與存儲保護1地址轉(zhuǎn)換地址轉(zhuǎn)換 因為分區(qū)的大小和個數(shù)是固定的，因此既可以采用靜因為分區(qū)的大小和個數(shù)是固定的，因此既

18、可以采用靜態(tài)重定位方式，也可以采用動態(tài)重定位方式。態(tài)重定位方式，也可以采用動態(tài)重定位方式。 第 3章 存儲器管理 2存儲保護存儲保護 存儲保護是使作業(yè)只在自己的分區(qū)內(nèi)進行存儲，存儲保護是使作業(yè)只在自己的分區(qū)內(nèi)進行存儲，即：下限寄存器即：下限寄存器絕對地址絕對地址上限寄存器，當絕對地址超出此上限寄存器，當絕對地址超出此范圍時，提示范圍時，提示“地址越界地址越界”。CPU+主主存存下限寄存器下限寄存器上限寄存器上限寄存器邏輯地址邏輯地址物理地址物理地址否否是是地址越界地址越界低地址低地址高地址高地址第 3章 存儲器管理 例例3-1 在某系統(tǒng)中采用固定分區(qū)分配管理方式，主存分區(qū)在某系統(tǒng)中采用固定分區(qū)

19、分配管理方式，主存分區(qū)情況如圖情況如圖3-9（a）所示?，F(xiàn)有大小為）所示?，F(xiàn)有大小為1KB、9KB、33KB、121KB的多個作業(yè)要求進入主存，試畫出它們進入主存后的多個作業(yè)要求進入主存，試畫出它們進入主存后的空間分配情況，并說明主存浪費有多大？的空間分配情況，并說明主存浪費有多大？3.3.4 管理特點管理特點 固定分區(qū)解決了單用戶連續(xù)存儲管理中內(nèi)存只裝入一固定分區(qū)解決了單用戶連續(xù)存儲管理中內(nèi)存只裝入一道作業(yè)的問題，內(nèi)存中同時裝入多道作業(yè)，提高了內(nèi)存利道作業(yè)的問題，內(nèi)存中同時裝入多道作業(yè)，提高了內(nèi)存利用率，并實現(xiàn)了并發(fā)執(zhí)行。用率，并實現(xiàn)了并發(fā)執(zhí)行。 但是，主存利用率還是存在浪費現(xiàn)象，因為每個作

20、業(yè)但是，主存利用率還是存在浪費現(xiàn)象，因為每個作業(yè)不可能與固定分區(qū)一樣大小。不可能與固定分區(qū)一樣大小。第 3章 存儲器管理 3.4 可變分區(qū)存儲管理方式可變分區(qū)存儲管理方式3.4.1 基本原理基本原理 可變分區(qū)存儲管理方式是在作業(yè)要求裝入主存時，可變分區(qū)存儲管理方式是在作業(yè)要求裝入主存時，根據(jù)作業(yè)的大小動態(tài)地劃分分區(qū)，使分區(qū)的大小正好適應根據(jù)作業(yè)的大小動態(tài)地劃分分區(qū)，使分區(qū)的大小正好適應作業(yè)的要求。各分區(qū)的大小是不確定的，主存中分區(qū)的數(shù)作業(yè)的要求。各分區(qū)的大小是不確定的，主存中分區(qū)的數(shù)目也是不確定的。目也是不確定的。第 3章 存儲器管理 3.4.2 主存空間的分配與回收主存空間的分配與回收1采用

21、的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) 第 3章 存儲器管理 2主存空間的分配與回收主存空間的分配與回收 首先初始化已分分區(qū)表（首先初始化已分分區(qū)表（0個記錄）和空閑分區(qū)表（個記錄）和空閑分區(qū)表（1個記錄），整個用戶區(qū)為一個空閑區(qū)，在空閑分區(qū)表中填個記錄），整個用戶區(qū)為一個空閑區(qū)，在空閑分區(qū)表中填入用戶區(qū)的始址和大小。主存空間的分配見書中圖入用戶區(qū)的始址和大小。主存空間的分配見書中圖3-11 。 當作業(yè)執(zhí)行完畢回收存儲區(qū)時，在已分分區(qū)表中，只當作業(yè)執(zhí)行完畢回收存儲區(qū)時，在已分分區(qū)表中，只要按照作業(yè)的首地址找到相應分區(qū)，將分區(qū)的狀態(tài)項置要按照作業(yè)的首地址找到相應分區(qū)，將分區(qū)的狀態(tài)項置0即可；即可；第 3章 存

22、儲器管理 在空閑分區(qū)表中，回收分為以下四種情況：在空閑分區(qū)表中，回收分為以下四種情況：（1）回收的分區(qū)前后沒有相鄰的空閑分區(qū)。）回收的分區(qū)前后沒有相鄰的空閑分區(qū)。（2）回收分區(qū)的前面有相鄰的空閑區(qū)。）回收分區(qū)的前面有相鄰的空閑區(qū)。（3）回收分區(qū)的后面有相鄰的空閑分區(qū)。）回收分區(qū)的后面有相鄰的空閑分區(qū)。（4）回收分區(qū)的前后都有相鄰的空閑分區(qū)。）回收分區(qū)的前后都有相鄰的空閑分區(qū)?；厥辗謪^(qū)回收分區(qū)回收分區(qū)回收分區(qū)空閑分區(qū)空閑分區(qū)回收分區(qū)回收分區(qū)空閑分區(qū)空閑分區(qū)回收分區(qū)回收分區(qū)空閑分區(qū)空閑分區(qū)空閑分區(qū)空閑分區(qū)（a）（b）（c）（d）圖圖3-6 空閑分區(qū)修改圖空閑分區(qū)修改圖第 3章 存儲器管理 3常用主

23、存分配算法常用主存分配算法（1）最先適應分配算法（）最先適應分配算法（FF） 空閑分區(qū)按地址遞增的順序排列，從頭開始查找，空閑分區(qū)按地址遞增的順序排列，從頭開始查找，找到第找到第1個滿足作業(yè)長度要求的空閑區(qū)，分割出作業(yè)需要個滿足作業(yè)長度要求的空閑區(qū)，分割出作業(yè)需要的長度分配給它。的長度分配給它。優(yōu)點：簡單、迅速。優(yōu)點：簡單、迅速。缺點：內(nèi)存區(qū)間利用率不均勻，低地址區(qū)用的多，容易產(chǎn)缺點：內(nèi)存區(qū)間利用率不均勻，低地址區(qū)用的多，容易產(chǎn)生過多的小地址碎片。生過多的小地址碎片。改進：循環(huán)最先適應分配算法。改進：循環(huán)最先適應分配算法。第 3章 存儲器管理 （2）最優(yōu)適應分配算法（）最優(yōu)適應分配算法（BF）

24、 最優(yōu)適應分配算法是按作業(yè)要求從所有的空閑分區(qū)中最優(yōu)適應分配算法是按作業(yè)要求從所有的空閑分區(qū)中挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣可保證不挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣可保證不去分割一個更大的區(qū)域，使裝入大作業(yè)時比較容易得到去分割一個更大的區(qū)域，使裝入大作業(yè)時比較容易得到滿足。為實現(xiàn)這種算法，把空閑區(qū)按長度遞增次序登記滿足。為實現(xiàn)這種算法，把空閑區(qū)按長度遞增次序登記在空閑分區(qū)表中，分配時順序查找。在空閑分區(qū)表中，分配時順序查找。優(yōu)點：保留了較大的連續(xù)內(nèi)存空間。優(yōu)點：保留了較大的連續(xù)內(nèi)存空間。缺點：容易產(chǎn)生碎片，每次內(nèi)存回收時都要重新排序。缺點：容易產(chǎn)生碎片，每次內(nèi)存回收時都要重新

25、排序。第 3章 存儲器管理 （3）最壞適應分配算法（）最壞適應分配算法（WF） 最壞適應分配算法每次分配主存時總是挑選一個最大最壞適應分配算法每次分配主存時總是挑選一個最大的空閑區(qū)，分割一部分給作業(yè)使用，使剩下的部分不至的空閑區(qū)，分割一部分給作業(yè)使用，使剩下的部分不至于太小，仍可供使用。為實現(xiàn)這種算法，把空閑區(qū)按長于太小，仍可供使用。為實現(xiàn)這種算法，把空閑區(qū)按長度遞減次序登記在空閑分區(qū)表中，分配時順序查找。度遞減次序登記在空閑分區(qū)表中，分配時順序查找。優(yōu)點：因為總是對大區(qū)間分割，因此不容易產(chǎn)生過多的碎優(yōu)點：因為總是對大區(qū)間分割，因此不容易產(chǎn)生過多的碎片。片。缺點：大作業(yè)的分配受影響。每次內(nèi)存回

26、收時空閑區(qū)都要缺點：大作業(yè)的分配受影響。每次內(nèi)存回收時空閑區(qū)都要重新排序。重新排序。 第 3章 存儲器管理 3.4.3 地址轉(zhuǎn)換與存儲保護地址轉(zhuǎn)換與存儲保護物理地址物理地址CPU+主主存存基址寄存器基址寄存器限長寄存器限長寄存器邏輯地址邏輯地址否否是是地址越界地址越界分區(qū)始址分區(qū)始址分區(qū)末址分區(qū)末址圖圖3-7 可變分區(qū)存儲管理的地址轉(zhuǎn)換可變分區(qū)存儲管理的地址轉(zhuǎn)換第 3章 存儲器管理 3.4.4 管理特點管理特點分區(qū)的長度不是預先固定的，而是按作業(yè)的實際需求來分區(qū)的長度不是預先固定的，而是按作業(yè)的實際需求來劃分的。分區(qū)的個數(shù)也不是預先確定的，而是由裝入的作劃分的。分區(qū)的個數(shù)也不是預先確定的，而是

27、由裝入的作業(yè)數(shù)決定的。業(yè)數(shù)決定的。分區(qū)的大小由作業(yè)大小來定，提高了主存的使用效率。分區(qū)的大小由作業(yè)大小來定，提高了主存的使用效率。在主存分配過程中，會產(chǎn)生許多主存在主存分配過程中，會產(chǎn)生許多主存“碎片碎片”。 有可能出現(xiàn)這種情況：內(nèi)存空閑分區(qū)的總?cè)萘窟€有有可能出現(xiàn)這種情況：內(nèi)存空閑分區(qū)的總?cè)萘窟€有30k，但都是一些不超過，但都是一些不超過5k的分區(qū)，這時有一個的分區(qū)，這時有一個10k的作業(yè)要的作業(yè)要裝入，可是它只能等待。裝入，可是它只能等待。 解決的方法是：采用移動或?qū)Q技術(shù)。解決的方法是：采用移動或?qū)Q技術(shù)。 第 3章 存儲器管理 3.4.5 采用的技術(shù)采用的技術(shù) 1移動技術(shù)移動技術(shù)說明：說

28、明： 正在與外設交換信息的作業(yè)不能移動。因為外設是根據(jù)已正在與外設交換信息的作業(yè)不能移動。因為外設是根據(jù)已確定的絕對地址完成信息傳輸?shù)?。確定的絕對地址完成信息傳輸?shù)摹?移動會增加系統(tǒng)開銷移動會增加系統(tǒng)開銷一般不會輕易使用移動技術(shù)。一般不會輕易使用移動技術(shù)。第 3章 存儲器管理 2對換技術(shù)（對換技術(shù)（Swapping） 對換是指把主存中暫時不能運行的進程，或暫時不對換是指把主存中暫時不能運行的進程，或暫時不用的程序和數(shù)據(jù)，換出到外存上，把已具備運行條件的用的程序和數(shù)據(jù)，換出到外存上，把已具備運行條件的進程，或進程所需要的程序或數(shù)據(jù)，換入主存的技術(shù)。進程，或進程所需要的程序或數(shù)據(jù)，換入主存的技術(shù)。

29、在以下幾種情況下需要使用對換技術(shù)：在以下幾種情況下需要使用對換技術(shù)：（1）必須把一部分進程調(diào)出主存，否則系統(tǒng)將因為主存不）必須把一部分進程調(diào)出主存，否則系統(tǒng)將因為主存不夠而發(fā)生死鎖。夠而發(fā)生死鎖。（2）主存中的進程全部處于阻塞狀態(tài)，）主存中的進程全部處于阻塞狀態(tài)，CPU空閑，需要把空閑，需要把內(nèi)存中的阻塞進程調(diào)出，將外存中就緒進程調(diào)入。內(nèi)存中的阻塞進程調(diào)出，將外存中就緒進程調(diào)入。 系統(tǒng)開銷大。系統(tǒng)開銷大。 第 3章 存儲器管理 對換到外存的進程存放在對換區(qū)，對換區(qū)采用可變分對換到外存的進程存放在對換區(qū)，對換區(qū)采用可變分區(qū)分配方式。區(qū)分配方式。換出進程選擇的步驟：換出進程選擇的步驟：（1）選擇阻

30、塞狀態(tài)的進程，如果有多個，則選擇優(yōu)先級低）選擇阻塞狀態(tài)的進程，如果有多個，則選擇優(yōu)先級低的進程。的進程。（2）如果無阻塞進程，則選擇優(yōu)先級低的就緒進程。）如果無阻塞進程，則選擇優(yōu)先級低的就緒進程。換入進程的選擇：換入進程的選擇： 當有空閑內(nèi)存時，便執(zhí)行進程的換入操作。當有空閑內(nèi)存時，便執(zhí)行進程的換入操作。 首先選擇首先選擇“就緒且換出就緒且換出”狀態(tài)的進程換入，如果存在狀態(tài)的進程換入，如果存在多個，則選擇換出時間最久的進程。多個，則選擇換出時間最久的進程。第 3章 存儲器管理 3.4.6 可變分區(qū)存儲管理舉例可變分區(qū)存儲管理舉例【例例3-2】主存有兩個空閑區(qū)主存有兩個空閑區(qū)F1、F2如圖所示。

31、如圖所示。F1為為220KB，F(xiàn)2為為120KB，另外依次有，另外依次有J1 、J2、J3三個作業(yè)請求加三個作業(yè)請求加載運行，它們的主存需求量分別是載運行，它們的主存需求量分別是40KB、160KB、100KB，試比較最先適應算法、最優(yōu)適應算法和最壞適應，試比較最先適應算法、最優(yōu)適應算法和最壞適應算法的性能。算法的性能。第 3章 存儲器管理 3.5 分頁式存儲管理方式分頁式存儲管理方式 頁式存儲管理方式與前面介紹的存儲管理方式有著根本頁式存儲管理方式與前面介紹的存儲管理方式有著根本的不同：不連續(xù)存儲。的不同：不連續(xù)存儲。3.5.1 基本原理基本原理 作業(yè)分頁，內(nèi)存分塊，頁與塊大小相等，可存放在

32、不連作業(yè)分頁，內(nèi)存分塊，頁與塊大小相等，可存放在不連續(xù)的內(nèi)存塊中。續(xù)的內(nèi)存塊中。第 3章 存儲器管理 頁面大小：頁面大?。?頁面小，可以減小內(nèi)碎片，但頁表過長，占用內(nèi)存。頁面小，可以減小內(nèi)碎片，但頁表過長，占用內(nèi)存。 頁面大，可減小頁表長度，但會增加內(nèi)碎片。頁面大，可減小頁表長度，但會增加內(nèi)碎片。地址結(jié)構(gòu)：地址結(jié)構(gòu)： 圖中地址長度為圖中地址長度為32位，頁面大小為位，頁面大小為4K，最多可以有，最多可以有1M個頁面。個頁面。 因為頁與塊大小相同，所以，頁內(nèi)地址與塊內(nèi)地址相因為頁與塊大小相同，所以，頁內(nèi)地址與塊內(nèi)地址相同，所以從邏輯地址轉(zhuǎn)換到物理地址只是將頁號置換為塊同，所以從邏輯地址轉(zhuǎn)換到物理

33、地址只是將頁號置換為塊號即可。號即可。第 3章 存儲器管理 3.5.2 主存空間的分配與回收主存空間的分配與回收1采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu)（1）頁表）頁表頁表給出了邏輯地址中的頁號與主存中的塊號的對應關(guān)系頁表給出了邏輯地址中的頁號與主存中的塊號的對應關(guān)系第 3章 存儲器管理 （2）主存分配表（作業(yè)表）主存分配表（作業(yè)表） 作業(yè)表記錄了各作業(yè)的作業(yè)名、頁表始址和頁表長度，作業(yè)表記錄了各作業(yè)的作業(yè)名、頁表始址和頁表長度，頁表長度為頁表中的最大序號。頁表長度為頁表中的最大序號。第 3章 存儲器管理 （3）位示圖）位示圖 位示圖用于內(nèi)存塊的分配。對于以上例子，內(nèi)存共位示圖用于內(nèi)存塊的分配。對于以上

34、例子，內(nèi)存共8塊塊，就用，就用8位二進制數(shù)表示每一塊的狀態(tài)，如果一個塊已分位二進制數(shù)表示每一塊的狀態(tài)，如果一個塊已分配，則為配，則為1，未分配則為，未分配則為0，因此，上面例子的位示圖可表，因此，上面例子的位示圖可表示為：示為： 00101011 8位正好位正好1個字節(jié)，再用一個字節(jié)表示剩余空閑塊數(shù)，則位個字節(jié)，再用一個字節(jié)表示剩余空閑塊數(shù)，則位示圖共需要示圖共需要2字節(jié)。字節(jié)。 假如內(nèi)存容量假如內(nèi)存容量512k，塊的大小為，塊的大小為2k，共，共256塊，那么塊，那么用用256個二進制位來表示這個二進制位來表示這256塊，共塊，共32字節(jié)，用字節(jié)，用2字節(jié)表字節(jié)表示剩余空閑塊數(shù)，共需要示剩余

35、空閑塊數(shù)，共需要34字節(jié)來表示位示圖。字節(jié)來表示位示圖。第 3章 存儲器管理 2主存空間的分配主存空間的分配 首先，系統(tǒng)要初始化位示圖，即把位示圖中的標志位首先，系統(tǒng)要初始化位示圖，即把位示圖中的標志位全部置為全部置為“0”，空閑塊數(shù)置為主存的最大塊數(shù)。其分配過，空閑塊數(shù)置為主存的最大塊數(shù)。其分配過程見下圖所示。程見下圖所示。 第 3章 存儲器管理 結(jié)束結(jié)束作業(yè)隊列空？作業(yè)隊列空？開始開始空閑塊數(shù)空閑塊數(shù)=頁數(shù)？頁數(shù)？初始化位示圖初始化位示圖計算該作業(yè)的頁數(shù)計算該作業(yè)的頁數(shù)為該作業(yè)建立頁表為該作業(yè)建立頁表否否是是否否是是顯示主存不足，刪顯示主存不足，刪除該作業(yè)或入隊尾除該作業(yè)或入隊尾圖圖3-8

36、 頁式存儲管理的主存分配流程圖頁式存儲管理的主存分配流程圖根據(jù)位示圖裝入作業(yè)的每一頁，修改位示圖根據(jù)位示圖裝入作業(yè)的每一頁，修改位示圖中的標記，在頁表中填入頁號及對應的塊號中的標記，在頁表中填入頁號及對應的塊號從作業(yè)隊列中取出隊首作業(yè)從作業(yè)隊列中取出隊首作業(yè)修改位示圖中的空閑塊數(shù)，并在主存修改位示圖中的空閑塊數(shù)，并在主存分配表中填入該作業(yè)的相關(guān)記錄分配表中填入該作業(yè)的相關(guān)記錄第 3章 存儲器管理 3主存空間的回收主存空間的回收（1）根據(jù)作業(yè)名在作業(yè)表中查找到頁表地址。）根據(jù)作業(yè)名在作業(yè)表中查找到頁表地址。（2）取出頁表。）取出頁表。（3）逐項歸還每一塊。位示圖中相應塊的狀態(tài)置）逐項歸還每一塊。

37、位示圖中相應塊的狀態(tài)置0。（4）剩余塊數(shù)加頁數(shù)。）剩余塊數(shù)加頁數(shù)。（5）刪除頁表。）刪除頁表。（6）作業(yè)表中刪除該作業(yè)記錄。）作業(yè)表中刪除該作業(yè)記錄。 第 3章 存儲器管理 3.5.3 地址轉(zhuǎn)換與存儲保護地址轉(zhuǎn)換與存儲保護1地址轉(zhuǎn)換地址轉(zhuǎn)換 因為頁與塊大小相同，所以頁內(nèi)地址等于塊內(nèi)地址，因為頁與塊大小相同，所以頁內(nèi)地址等于塊內(nèi)地址，因此，地址轉(zhuǎn)換的任務實際上是將邏輯地址中的頁號，轉(zhuǎn)因此，地址轉(zhuǎn)換的任務實際上是將邏輯地址中的頁號，轉(zhuǎn)換為內(nèi)存中的塊號即可。換為內(nèi)存中的塊號即可。例如：頁表如下圖所示，頁長例如：頁表如下圖所示，頁長1k，用戶基址為，用戶基址為2000，將邏，將邏輯地址輯地址3000（

38、101110111000）轉(zhuǎn)換為物理地址。）轉(zhuǎn)換為物理地址。 第 3章 存儲器管理 圖圖3-9 頁式系統(tǒng)的地址轉(zhuǎn)換圖頁式系統(tǒng)的地址轉(zhuǎn)換圖14057頁號頁號=頁長頁長頁表始址頁表始址 頁表長度頁表長度 2 769頁號頁號 頁內(nèi)地址頁內(nèi)地址頁表寄存器頁表寄存器 + 0 2 1 4 2 6 3 8 頁號頁號 塊號塊號 6 769塊號塊號 越界越界CPU主主存存4865物理地址物理地址邏輯地址邏輯地址頁長頁長第 3章 存儲器管理 2頁的共享與保護頁的共享與保護（1）頁的共享）頁的共享 前面所講的連續(xù)存儲方式無法做到程序的共享，而頁前面所講的連續(xù)存儲方式無法做到程序的共享，而頁式方式因為不再是連續(xù)存儲，

39、因此可以實現(xiàn)頁的共享。式方式因為不再是連續(xù)存儲，因此可以實現(xiàn)頁的共享。 第 3章 存儲器管理 （2）頁的保護）頁的保護 頁式存儲管理方式下的保護有頁式存儲管理方式下的保護有3情況：共享頁的保情況：共享頁的保護、不同作業(yè)所占空間的保護、邏輯地址轉(zhuǎn)換成物理地護、不同作業(yè)所占空間的保護、邏輯地址轉(zhuǎn)換成物理地址的保護。址的保護。共享頁的保護。其方法是在頁表中設置一個權(quán)限位，共享頁的保護。其方法是在頁表中設置一個權(quán)限位，指出該信息可讀指出該信息可讀/寫、只讀、只執(zhí)行等權(quán)限。寫、只讀、只執(zhí)行等權(quán)限。 不同作業(yè)所占空間的保護。通過位示圖中的每個存儲不同作業(yè)所占空間的保護。通過位示圖中的每個存儲塊的標志位，來

40、保護已經(jīng)分配到主存中的作業(yè)空間，不塊的標志位，來保護已經(jīng)分配到主存中的作業(yè)空間，不被新作業(yè)覆蓋。被新作業(yè)覆蓋。 邏輯地址轉(zhuǎn)換成物理地址的保護。邏輯地址轉(zhuǎn)換成物理地址的保護。第 3章 存儲器管理 3.5.4 對頁式存儲管理的改進對頁式存儲管理的改進1具有快表的地址變換具有快表的地址變換 CPU在存取數(shù)據(jù)時，每次要訪問主存兩次。分頁存儲解決在存取數(shù)據(jù)時，每次要訪問主存兩次。分頁存儲解決了碎片問題，提高了內(nèi)存利用率，實際上是以時間做為代價了碎片問題，提高了內(nèi)存利用率，實際上是以時間做為代價的，即以時間換空間。的，即以時間換空間。 為了解決多次訪問內(nèi)存的問題，可以把頁表放在一個可并為了解決多次訪問內(nèi)存

41、的問題，可以把頁表放在一個可并行操作的存儲器中，稱為行操作的存儲器中，稱為“聯(lián)想存儲器聯(lián)想存儲器” ，又稱為快表。，又稱為快表。關(guān)于聯(lián)想存儲器（關(guān)于聯(lián)想存儲器（Associative Memory） ： 不按地址而按給定內(nèi)容的特征進行存取的存儲器。如要對不按地址而按給定內(nèi)容的特征進行存取的存儲器。如要對兩個存儲單元中的內(nèi)容作某種運算，并將結(jié)果存入其中一個兩個存儲單元中的內(nèi)容作某種運算，并將結(jié)果存入其中一個單元，則選用按地址存取的存儲器比較適宜。如果根據(jù)某些單元，則選用按地址存取的存儲器比較適宜。如果根據(jù)某些內(nèi)容特征來查找存儲單元，則使用聯(lián)想存儲器能更快地得到內(nèi)容特征來查找存儲單元，則使用聯(lián)想存

42、儲器能更快地得到結(jié)果。結(jié)果。第 3章 存儲器管理 特點：特點： 除有存儲功能外，還具有信息處理功能。它能根據(jù)送來除有存儲功能外，還具有信息處理功能。它能根據(jù)送來內(nèi)容的特征查找存儲單元。內(nèi)容的特征查找存儲單元。 對各個存儲單元并行進行查找，因而能顯著提高查找速對各個存儲單元并行進行查找，因而能顯著提高查找速度。度。組成：組成： 聯(lián)想存儲器由多個寄存器和存儲體組成，要查找的變聯(lián)想存儲器由多個寄存器和存儲體組成，要查找的變量放在寄存器中，存儲體中的每個存儲單元都含有存儲、量放在寄存器中，存儲體中的每個存儲單元都含有存儲、比較、讀寫、控制等電路。比較、讀寫、控制等電路。 因為其價格昂貴，不能做得很大，

43、因此一個大作業(yè)的因為其價格昂貴，不能做得很大，因此一個大作業(yè)的頁表只能有一部分放入聯(lián)想存儲器。頁表只能有一部分放入聯(lián)想存儲器。486的聯(lián)想存儲器是的聯(lián)想存儲器是32個。從中能找到所需頁的概率為個。從中能找到所需頁的概率為90%。第 3章 存儲器管理 優(yōu)點：查找速度快，功能強。優(yōu)點：查找速度快，功能強。缺點：所含的電路較多，造價很高。缺點：所含的電路較多，造價很高。 設訪問主存時間為設訪問主存時間為100ns（納秒），訪問聯(lián)想存儲器的（納秒），訪問聯(lián)想存儲器的時間為時間為20ns，聯(lián)想存儲器的命中率為，聯(lián)想存儲器的命中率為90%，則按邏輯地址，則按邏輯地址訪問主存的平均時間為：訪問主存的平均時間

44、為：（100+20)*90%+(100+100+20)*10%=130ns第 3章 存儲器管理 2兩級頁表的地址轉(zhuǎn)換兩級頁表的地址轉(zhuǎn)換 大作業(yè)的邏輯地址空間可能會非常大（大作業(yè)的邏輯地址空間可能會非常大（232264） ，它，它的頁表就會很長，有時會占據(jù)很大的存儲空間。的頁表就會很長，有時會占據(jù)很大的存儲空間。 比如，邏輯地址空間比如，邏輯地址空間232，若每頁，若每頁4KB，則需要，則需要1M個頁個頁表項，若每個頁表項占表項，若每個頁表項占4B，則頁表需要占主存，則頁表需要占主存4MB。 要在主存中找到這么大的一個連續(xù)存儲空間是很困難要在主存中找到這么大的一個連續(xù)存儲空間是很困難的。我們可以

45、把頁表也分頁存儲，頁的大小與主存物理塊的。我們可以把頁表也分頁存儲，頁的大小與主存物理塊大小相同。原來頁表只有一個，現(xiàn)在有多個頁表，所以必大小相同。原來頁表只有一個，現(xiàn)在有多個頁表，所以必須再為這些分散的頁表再建立一個頁表，稱為外層頁表。須再為這些分散的頁表再建立一個頁表，稱為外層頁表。 外層頁號、外層頁內(nèi)地址、頁內(nèi)地址外層頁號、外層頁內(nèi)地址、頁內(nèi)地址 第 3章 存儲器管理 3.5.5 管理特點管理特點1可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間，也不必象可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間，也不必象可變分區(qū)管理那樣通過增加系統(tǒng)開銷來解決可變分區(qū)管理那樣通過增加系統(tǒng)開銷來解決“碎片碎片”問問題，

46、它有效地解決了題，它有效地解決了“碎片碎片”多的問題。多的問題。 2通過位示圖和頁表來記錄主存的使用情況和每個作業(yè)的通過位示圖和頁表來記錄主存的使用情況和每個作業(yè)的分配情況，當主存很大，并且作業(yè)也很大時，位示圖和分配情況，當主存很大，并且作業(yè)也很大時，位示圖和頁表都有可能占用較大的存儲空間。另外，它要求有相頁表都有可能占用較大的存儲空間。另外，它要求有相應的硬件支持，從而增加了系統(tǒng)成本，也增加了系統(tǒng)開應的硬件支持，從而增加了系統(tǒng)成本，也增加了系統(tǒng)開銷。銷。3.5.6 頁式存儲管理舉例頁式存儲管理舉例 第 3章 存儲器管理 【例例3-3】設一頁式存儲管理系統(tǒng)，向用戶提供邏輯地址空設一頁式存儲管理

47、系統(tǒng)，向用戶提供邏輯地址空間最大為間最大為16頁，每頁頁，每頁2048字節(jié)，主存總共有字節(jié)，主存總共有8個存儲塊，個存儲塊，試問邏輯地址應為多少位？主存空間有多大？試問邏輯地址應為多少位？主存空間有多大？【解解】頁式存儲管理系統(tǒng)中的邏輯地址結(jié)構(gòu)為：頁號頁式存儲管理系統(tǒng)中的邏輯地址結(jié)構(gòu)為：頁號+頁內(nèi)頁內(nèi)地址。本題中，每頁地址。本題中，每頁2048字節(jié)，所以頁內(nèi)地址部分地址需字節(jié)，所以頁內(nèi)地址部分地址需要占據(jù)要占據(jù)11個二進制位；邏輯地址空間最大為個二進制位；邏輯地址空間最大為16頁，所以頁頁，所以頁號部分地址需要占據(jù)號部分地址需要占據(jù)4個二進制位。故邏輯地址至少為個二進制位。故邏輯地址至少為15

48、位。位。 由于主存共有由于主存共有8個存儲塊，在頁式存儲管理系統(tǒng)中，個存儲塊，在頁式存儲管理系統(tǒng)中，存儲塊大小與頁面的大小相等。因此，主存空間為存儲塊大小與頁面的大小相等。因此，主存空間為16K。第 3章 存儲器管理 【例例3-4】在一個頁式存儲管理系統(tǒng)中，某作業(yè)的頁表如下在一個頁式存儲管理系統(tǒng)中，某作業(yè)的頁表如下表所示。已知頁面大小為表所示。已知頁面大小為1024字節(jié)，用戶區(qū)的基址為字節(jié)，用戶區(qū)的基址為1000，試將邏輯地址，試將邏輯地址1011、2148、3000、4000、5012轉(zhuǎn)換為相轉(zhuǎn)換為相應的物理地址。應的物理地址。第 3章 存儲器管理 【例例3-5】假設主存用戶區(qū)大小為假設主存

49、用戶區(qū)大小為200MB，作業(yè)的大小為，作業(yè)的大小為100KB，頁面大小為，頁面大小為4KB，頁表項長度為，頁表項長度為4字節(jié)，采用頁字節(jié)，采用頁式存儲管理方式管理主存，請計算位示圖和頁表的大小。式存儲管理方式管理主存，請計算位示圖和頁表的大小。解：解：200M/4K=50K=51200（塊）（塊） 51200/8=6400（字節(jié)）（字節(jié)） 剩余空閑塊數(shù)需要剩余空閑塊數(shù)需要2字節(jié)。字節(jié)。 位示圖需要占用位示圖需要占用6402字節(jié)。字節(jié)。 100K/4K*4字節(jié)字節(jié)=100字節(jié)字節(jié) 所以頁表占所以頁表占100字節(jié)。字節(jié)。第 3章 存儲器管理 3.6 分段式存儲管理方式分段式存儲管理方式 3.6.1

50、 基本原理基本原理 段式存儲是將作業(yè)分段，按段存儲。段是按照作業(yè)的段式存儲是將作業(yè)分段，按段存儲。段是按照作業(yè)的邏輯關(guān)系劃分，比如：主程序段、子程序段、數(shù)據(jù)段、邏輯關(guān)系劃分，比如：主程序段、子程序段、數(shù)據(jù)段、棧段等，每個段有一個段號，每段都從棧段等，每個段有一個段號，每段都從0開始編址，因此開始編址，因此段的邏輯地址是二維的，由段號和段內(nèi)地址組成。段的邏輯地址是二維的，由段號和段內(nèi)地址組成。 在內(nèi)存中，每個段占用一段連續(xù)的存儲空間，而段與在內(nèi)存中，每個段占用一段連續(xù)的存儲空間，而段與段之間可不連續(xù)。如果沒有足夠大的連續(xù)空間，則采用段之間可不連續(xù)。如果沒有足夠大的連續(xù)空間，則采用移動技術(shù)，拼接出

51、大的空間。移動技術(shù)，拼接出大的空間。 第 3章 存儲器管理 段地址結(jié)構(gòu)：段地址結(jié)構(gòu)： 在該地址結(jié)構(gòu)中，一個作業(yè)最多可有在該地址結(jié)構(gòu)中，一個作業(yè)最多可有256（28）個段，每段最）個段，每段最長為長為16MB（224） 。3.6.2 主存空間的分配與回收主存空間的分配與回收1采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu)（1）段表）段表 第 3章 存儲器管理 與頁表一樣，與頁表一樣，CPU在存取數(shù)據(jù)時也要訪問主存兩次，在存取數(shù)據(jù)時也要訪問主存兩次，一次是訪問段表，得到段的首地址，合成物理地址后，一次是訪問段表，得到段的首地址，合成物理地址后，再按物理地址訪問主存得到數(shù)據(jù)。不同的是，頁表較大再按物理地址訪問主存得到

52、數(shù)據(jù)。不同的是，頁表較大，不能把它們?nèi)糠湃肼?lián)想存儲器以制成，不能把它們?nèi)糠湃肼?lián)想存儲器以制成“快表快表”，而，而段表較小，通?？梢詫⑺鼈?nèi)糠湃肼?lián)想存儲器中，因段表較小，通?？梢詫⑺鼈?nèi)糠湃肼?lián)想存儲器中，因此，分段方式不會在速度上有太大損失。此，分段方式不會在速度上有太大損失。 第 3章 存儲器管理 （2）主存分配表（作業(yè)表）主存分配表（作業(yè)表）第 3章 存儲器管理 （3）空閑分區(qū)表）空閑分區(qū)表 段式存儲的內(nèi)存空間分配類似于可變分區(qū)，需要建立段式存儲的內(nèi)存空間分配類似于可變分區(qū)，需要建立一個表來記錄內(nèi)存中的空閑分區(qū)一個表來記錄內(nèi)存中的空閑分區(qū) 。2主存空間的分配過程主存空間的分配過程 其

53、主存分配流程如圖其主存分配流程如圖3-10所示。所示。第 3章 存儲器管理 圖圖3-10 3-10 段式存儲管理主存分配段式存儲管理主存分配開始空閑區(qū)之和空閑區(qū)之和段長段長越界越界段始址段始址+段內(nèi)地址段內(nèi)地址段表段表CPU主主存存 段長段長 段始址段始址邏輯地址邏輯地址物理地址物理地址8292地址越界地址越界圖圖3-11 段式存儲管理主存分配流程圖段式存儲管理主存分配流程圖段號段號段號段號頁長頁長頁表頁表頁號頁號 塊號塊號否否是是第 3章 存儲器管理 3.7.4 管理特點管理特點（1）根據(jù)作業(yè)模塊把作業(yè)分成若干段，再根據(jù)頁面大小把）根據(jù)作業(yè)模塊把作業(yè)分成若干段，再根據(jù)頁面大小把每一段分成若干

54、頁，主存仍然分成與頁大小相等的塊。分每一段分成若干頁，主存仍然分成與頁大小相等的塊。分配主存時，把作業(yè)的每一段的頁分配到主存塊中。配主存時，把作業(yè)的每一段的頁分配到主存塊中。（2）這種分配方式既照顧到了用戶共享和使用方便的需求）這種分配方式既照顧到了用戶共享和使用方便的需求，又考慮到了主存的利用率，提高了系統(tǒng)的性能。，又考慮到了主存的利用率，提高了系統(tǒng)的性能。（3）這種分配方式的空間浪費要比頁式管理的多。作業(yè)各）這種分配方式的空間浪費要比頁式管理的多。作業(yè)各段的最后一頁都有可能浪費一部分空間。另外段表和頁表段的最后一頁都有可能浪費一部分空間。另外段表和頁表占用空間，都比頁式和段式的多，增加了系

55、統(tǒng)開銷。占用空間，都比頁式和段式的多，增加了系統(tǒng)開銷。第 3章 存儲器管理 3.8 虛擬存儲管理方式虛擬存儲管理方式 3.8.1 基本概念基本概念1問題的提出問題的提出 人們發(fā)現(xiàn)，作業(yè)執(zhí)行時實際上不會同時使用全部信息，有人們發(fā)現(xiàn)，作業(yè)執(zhí)行時實際上不會同時使用全部信息，有些程序段根本就不會執(zhí)行，比如錯誤處理程序。因此將作業(yè)全些程序段根本就不會執(zhí)行，比如錯誤處理程序。因此將作業(yè)全部裝入主存降低了主存的利用率。部裝入主存降低了主存的利用率。 在作業(yè)運行時，能否不把作業(yè)的全部信息同時裝入主存，在作業(yè)運行時，能否不把作業(yè)的全部信息同時裝入主存，而只是把當前使用的部分先裝入，其余部分先放在輔存中。這而只是

56、把當前使用的部分先裝入，其余部分先放在輔存中。這樣當主存空間小于作業(yè)需要量時，這個作業(yè)也能執(zhí)行，同時可樣當主存空間小于作業(yè)需要量時，這個作業(yè)也能執(zhí)行，同時可以裝入更多的作業(yè)，使并發(fā)度得到提高。以裝入更多的作業(yè)，使并發(fā)度得到提高。第 3章 存儲器管理 通過對程序執(zhí)行的分析，發(fā)現(xiàn)了以下一些情況：通過對程序執(zhí)行的分析，發(fā)現(xiàn)了以下一些情況： 程序中只有少量分支和過程調(diào)用，大部分是順序結(jié)構(gòu)，程序中只有少量分支和過程調(diào)用，大部分是順序結(jié)構(gòu)，執(zhí)行的下一條指令總是緊跟在當前指令之后；執(zhí)行的下一條指令總是緊跟在當前指令之后； 程序往往包含若干個循環(huán)，在循環(huán)過程中，在一段時間程序往往包含若干個循環(huán)，在循環(huán)過程中，

57、在一段時間內(nèi)總是在執(zhí)行同一段程序；內(nèi)總是在執(zhí)行同一段程序； 出錯處理程序僅當程序出現(xiàn)錯誤時才會用到。出錯處理程序僅當程序出現(xiàn)錯誤時才會用到。 程序的局部性原理程序的局部性原理 ： 程序在執(zhí)行時將呈現(xiàn)出局部性的規(guī)律，在一個時間段程序在執(zhí)行時將呈現(xiàn)出局部性的規(guī)律，在一個時間段內(nèi)，程序僅在某個部分執(zhí)行，而不是對程序的所有部分具內(nèi)，程序僅在某個部分執(zhí)行，而不是對程序的所有部分具有平均的訪問概率，或僅訪問存儲空間的某個區(qū)域。有平均的訪問概率，或僅訪問存儲空間的某個區(qū)域。 第 3章 存儲器管理 2虛擬存儲器的定義虛擬存儲器的定義 虛擬存儲器是指允許用戶作業(yè)的邏輯地址空間大于主存儲虛擬存儲器是指允許用戶作業(yè)

58、的邏輯地址空間大于主存儲器的絕對地址空間，只把作業(yè)的一部分裝入即可運行的存儲器器的絕對地址空間，只把作業(yè)的一部分裝入即可運行的存儲器系統(tǒng)。系統(tǒng)。 虛擬存儲器的容量與主存大小無直接關(guān)系，它受限于系統(tǒng)虛擬存儲器的容量與主存大小無直接關(guān)系，它受限于系統(tǒng)的地址結(jié)構(gòu)及可用的輔存容量大小的地址結(jié)構(gòu)及可用的輔存容量大小 。 如果地址線是如果地址線是32位，則虛擬存儲器的邏輯容量也稱為最大位，則虛擬存儲器的邏輯容量也稱為最大容量是容量是2324G。虛擬存儲器的實際容量為主存與硬盤容量之和。虛擬存儲器的實際容量為主存與硬盤容量之和。如果其總和不超過地址線的范圍，則是內(nèi)存。如果其總和不超過地址線的范圍，則是內(nèi)存+

59、外存，否則就外存，否則就是由地址線決定。是由地址線決定。 windows/XP就提供了就提供了4G的邏輯主存。的邏輯主存。 第 3章 存儲器管理 虛擬存儲器的好處：虛擬存儲器的好處：（1）小內(nèi)存運行大作業(yè)，用戶在編寫程序時不必考慮內(nèi)存）小內(nèi)存運行大作業(yè)，用戶在編寫程序時不必考慮內(nèi)存的大小。的大小。（2）內(nèi)存中可以裝入更多的作業(yè)，提高了系統(tǒng)的并發(fā)性，）內(nèi)存中可以裝入更多的作業(yè)，提高了系統(tǒng)的并發(fā)性，從而提高了系統(tǒng)效率。從而提高了系統(tǒng)效率。第 3章 存儲器管理 3虛擬存儲器存儲的特點虛擬存儲器存儲的特點（1）離散性）離散性 作業(yè)在內(nèi)存中的不連續(xù)存放，這是虛擬存儲的基礎。作業(yè)在內(nèi)存中的不連續(xù)存放，這是

60、虛擬存儲的基礎。（2）多次性）多次性 先裝入一部分就開始運行，以后用到哪部分，裝入哪先裝入一部分就開始運行，以后用到哪部分，裝入哪部分，分多次裝入。部分，分多次裝入。（3）對換性）對換性 需要的裝入，不需要的換出。需要的裝入，不需要的換出。（4）虛擬性）虛擬性 內(nèi)存的擴充是邏輯上的，借助于外存實現(xiàn)的，實際上內(nèi)存的擴充是邏輯上的，借助于外存實現(xiàn)的，實際上并沒有從物理上擴充內(nèi)存。并沒有從物理上擴充內(nèi)存。第 3章 存儲器管理 虛擬存儲管理主要通過以下幾種技術(shù)實現(xiàn)：虛擬存儲管理主要通過以下幾種技術(shù)實現(xiàn)： 請求分頁式、請求分段式、請求段頁式。請求分頁式、請求分段式、請求段頁式。第 3章 存儲器管理 3.