第四章_存儲器管理

1、第四章第四章 存儲器管理存儲器管理計算機(jī)系統(tǒng)存儲層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質(zhì)Cpu內(nèi)部寄存器內(nèi)存外存n存儲器包括內(nèi)存和外存；n外存容量大，速度慢，價格低（每位價格） ，可以長期保存程序和數(shù)據(jù)；n內(nèi)存容量小，速度快，價格高（每位價格），內(nèi)存是易失性的，不能永久存儲信息；n在計算機(jī)系統(tǒng)中，外存是作為外部設(shè)備存在的；n本章主要討論對內(nèi)存的管理存儲器管理的對象外存內(nèi)存OS裝入內(nèi)容提要內(nèi)容提要n 存儲器管理的任務(wù)n 程序的裝入和鏈接n 內(nèi)存分配技術(shù)n 虛擬存儲管理技術(shù) 請求分頁式存儲管理方式 頁面置換算法 請求分段式存儲管理方式4.1 4.1 存儲器管理的任務(wù)存儲器管理的任務(wù)

2、存儲器管理的任務(wù)n內(nèi)存的分配與回收n地址重定位n存儲共享n存儲保護(hù)n存儲擴(kuò)充存儲分配與回收n基本任務(wù)：管理內(nèi)存空間的分配與回收n計算機(jī)內(nèi)存被劃分成兩部分：系統(tǒng)區(qū)和用戶區(qū)系統(tǒng)區(qū)：用于存放操作系統(tǒng)的程序和數(shù)據(jù)用戶區(qū)：用于裝入并存放各個用戶進(jìn)程的程序和數(shù)據(jù)n內(nèi)存空間的分配與回收主要是針對用戶區(qū)的分配和管理分配基本內(nèi)存空間增加新的內(nèi)存空間 動態(tài)申請或釋放內(nèi)存空間回收內(nèi)存空間地址空間和邏輯地址n用戶源程序經(jīng)編譯鏈接后形成的代碼所限定的地址叫做該程序的地址空間。n地址空間中各個地址叫做相對地址，或邏輯地址，又叫虛地址。n邏輯地址的特點：其首地址為0，其余指令的地址都相對于首地址來編址不能用邏輯地址在內(nèi)存中

3、讀取信息存儲空間和物理地址n指物理存儲器中全部物理存儲單元的集合所限定的空間。n每個存儲單元都有它自己的編號地址，該地址被稱為絕對地址，或物理地址，也叫實地址。n存儲空間的大小由系統(tǒng)的硬件配置決定。進(jìn)程在內(nèi)存的映像進(jìn)程控制塊程序數(shù)據(jù)棧進(jìn)程控制信息程序入口點當(dāng)前棧頂跳轉(zhuǎn)指令數(shù)據(jù)訪問地址值增加進(jìn)程執(zhí)行時的尋址地址重定位n地址重定位：對目標(biāo)程序中的指令和數(shù)據(jù)地址進(jìn)行修改的過程。n把程序地址空間的邏輯地址轉(zhuǎn)換為存儲空間的物理地址的工作叫做地址重定位，又叫地址映射或地址變換。源程序源程序邏輯地址空間邏輯地址空間物理地址空間物理地址空間編譯連接編譯連接地址映射地址映射0100200邏輯地址、物理地址和地址

4、映射邏輯地址、物理地址和地址映射mov r1, data1data1 3456mov r1, 2003456100011001200mov r1, 12003456BA=1000地址重定位分類n靜態(tài)地址重定位n動態(tài)地址重定位靜態(tài)地址重定位n靜態(tài)地址重定位：重定位工作是在程序裝入主存時，由靜態(tài)重定位裝入程序集中一次完成，程序運行時不再改變。源程序源程序邏輯地址空間邏輯地址空間物理地址空間物理地址空間編譯鏈接編譯鏈接裝入裝入0100200邏輯地址、物理地址和地址映射邏輯地址、物理地址和地址映射mov r1, data1data1 3456mov r1, 2003456100011001200mov

5、 r1, 12003456BA=1000靜態(tài)重定位示意圖靜態(tài)地址重定位n特點：靜態(tài)重定位實現(xiàn)簡單，不需要硬件的支持靜態(tài)重定位方法將程序一旦裝入內(nèi)存就不能再移動，且必須在程序執(zhí)行之前將有關(guān)部分全部裝入，主存利用率低。使用靜態(tài)重定位方法進(jìn)行地址變換不適合多道程序系統(tǒng)；不允許系統(tǒng)執(zhí)行內(nèi)存的碎片整理；無法實現(xiàn)虛擬存儲器。不能做到程序和數(shù)據(jù)的共享。動態(tài)地址重定位n動態(tài)地址重定位：操作系統(tǒng)將程序裝入內(nèi)存之后，并不立即把目標(biāo)程序中的邏輯地址轉(zhuǎn)換為物理地址，而是在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前，將要訪問的程序或數(shù)據(jù)的邏輯地址轉(zhuǎn)換成內(nèi)存地址。n特點：動態(tài)地址重定位依靠硬件地址變換機(jī)構(gòu)完成。源程序源程序邏輯

6、地址空間邏輯地址空間物理地址空間物理地址空間編譯鏈接編譯鏈接裝入裝入0100200mov r1, data1data1 3456mov r1, 2003456100011001200mov r1, 2003456動態(tài)重定位示意圖動態(tài)重定位示意圖內(nèi)存重定位寄存器CPU1000邏輯地址物理地址2001200動態(tài)重定位優(yōu)點n動態(tài)重定位的優(yōu)點（1）可以對內(nèi)存進(jìn)行非連續(xù)分配。顯然，對于同一進(jìn)程的各分散程序段，只要把它們在內(nèi)存的首地址統(tǒng)一存放在不同的寄存器中，則可以由地址變換機(jī)構(gòu)得到正確的待訪問內(nèi)存地址。（2）將程序裝入內(nèi)存之后仍可以再移動。（3）動態(tài)重定位提供了實現(xiàn)虛擬存儲器的基礎(chǔ)。因為動態(tài)重定位不要求

7、在作業(yè)執(zhí)行前為所有程序分配內(nèi)存，也就是說，可以部分地、動態(tài)地分配內(nèi)存。（4）有利于程序段的共享。存儲保護(hù)n防止地址越界，防止操作越權(quán)n地址越界：進(jìn)程訪問不屬于自己的地址空間，或者說進(jìn)程在運行時所產(chǎn)生的物理地址超越其自身的地址空間范圍?？赡芮址钙渌脩暨M(jìn)程空間也可能侵犯操作系統(tǒng)的存儲空間n操作越權(quán)：進(jìn)程對共享存儲區(qū)的操作違反了系統(tǒng)規(guī)定的權(quán)限。存儲共享n為了進(jìn)程通信和節(jié)約內(nèi)存空間，兩個或多個進(jìn)程共用內(nèi)存中相同的分區(qū)，即他們的物理空間有相交的部分。n可以共享進(jìn)程的代碼，也可以共享進(jìn)程數(shù)據(jù)n一般地，進(jìn)程之間共享代碼的目的主要是為了節(jié)約內(nèi)存空間，共享數(shù)據(jù)的目的主要是為了實現(xiàn)進(jìn)程間相互通信。共享數(shù)據(jù)n通過

8、共享存儲區(qū)實現(xiàn)進(jìn)程通信一個進(jìn)程將共享數(shù)據(jù)寫入共享存儲區(qū)另一個進(jìn)程從共享存儲區(qū)讀出數(shù)據(jù)共享程序n設(shè)計程序時，一般包括程序代碼和數(shù)據(jù)兩部分。n如果存儲時，程序的代碼區(qū)和數(shù)據(jù)區(qū)分開存放，代碼區(qū)不包含運行程序時需要改變的數(shù)據(jù)，被處理的數(shù)據(jù)都放在獨立的數(shù)據(jù)區(qū)，這樣，進(jìn)程執(zhí)行過程中就不會修改代碼區(qū)中的任何代碼n很多的編譯程序支持可重入的程序設(shè)計，這樣，程序員在寫程序時不需要考慮將程序代碼和數(shù)據(jù)嚴(yán)格分開，編譯程序在編譯時會自動將數(shù)據(jù)和程序代碼分開存儲，以保證代碼部分是純的、可重入的。共享程序n可重入代碼：又稱純代碼，是指程序代碼的一個副本在同一段時間中可被多個進(jìn)程共享使用。n可重入的兩個重要特征：程序代碼不

9、能修改自身；每個用戶的局部數(shù)據(jù)必須單獨保存存儲擴(kuò)充n內(nèi)存：速度快、容量小、價格貴n外存：容量大、速度慢、價格便宜n目的：在多道程序系統(tǒng)中能運行更多、更大的程序，降低系統(tǒng)的造價，提高系統(tǒng)的性價比n存儲擴(kuò)充：采用軟件手段，在硬件的配合下，將部分外存空間虛擬為內(nèi)存空間，并將內(nèi)存和部分外存有機(jī)地結(jié)合起來，得到一個容量相當(dāng)于外存、速度接近內(nèi)存、價格十分便宜的虛擬存儲系統(tǒng)。存儲擴(kuò)充n虛擬存儲系統(tǒng)在邏輯上對外是一個整體，用戶感覺到系統(tǒng)提供了一個非常大的內(nèi)存空間。n操作系統(tǒng)負(fù)責(zé)完成內(nèi)存與外存之間的透明切換：進(jìn)程運行時將需要的數(shù)據(jù)或代碼從外存裝入內(nèi)存，并將內(nèi)存中暫時不用的部分交換到外存。4.2 4.2 程序的裝

10、入和鏈接程序的裝入和鏈接可執(zhí)行程序的生成步驟n 一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序通常要經(jīng)過以下幾個步驟：編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊；鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊以及它們需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊；裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存（構(gòu)造PCB，形成進(jìn)程）。對用戶程序的處理步驟對用戶程序的處理步驟對用戶程序的處理步驟可執(zhí)行程序的裝入n如何裝入待執(zhí)行的程序及其所需的數(shù)據(jù)？n何時將程序的邏輯地址轉(zhuǎn)換為物理地址？n3種裝入方式：p絕對裝入p可重定位裝入p動態(tài)運行時裝入絕對裝入n 程序運行之前，按照程序的邏輯地址，將程序和數(shù)據(jù)裝入內(nèi)存指定

11、的地方。n實現(xiàn)簡單，無須進(jìn)行邏輯地址到物理地址的映射。絕對裝入缺點n 程序每次必須裝入同一內(nèi)存區(qū)；n程序員必須事先了解內(nèi)存的使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；n程序的修改（增加或刪除指令）將引起整個程序中指令地址的變動；n程序中的所有存儲引用，例如函數(shù)調(diào)用或過程調(diào)用等，在裝入之前都必須轉(zhuǎn)換為物理地址，這不利于存儲共享。可重定位裝入n 允許將程序裝入與邏輯地址不同的物理內(nèi)存空間。即程序可以裝入到內(nèi)存的任何位置，其邏輯地址與裝入內(nèi)存后的物理地址無直接關(guān)系。n但是必須進(jìn)行地址映射，將邏輯地址轉(zhuǎn)換為物理地址。n靜態(tài)重定位技術(shù)：地址映射在程序裝入時進(jìn)行，以后不再更改程序地址?？芍囟ㄎ谎b入n但是，

12、靜態(tài)重定位不允許程序在內(nèi)存中移動。這不便于進(jìn)程交換和緊湊拼接操作，也很難實現(xiàn)多道程序環(huán)境下，多個程序同時裝入內(nèi)存的要求。n因此，重定位裝入方式只適合于單道程序環(huán)境?？芍囟ㄎ谎b入Mov r1,50012340100500599Mov r1,1500010001100150015991234OS作業(yè)的地址空間作業(yè)的地址空間存儲空間存儲空間裝入程序裝入程序把程序裝入起始地址為把程序裝入起始地址為1000的內(nèi)存區(qū)的內(nèi)存區(qū)可重定位裝入方式可重定位裝入方式動態(tài)運行時裝入n程序的地址轉(zhuǎn)換不是在裝入時進(jìn)行，而是在程序運行時動態(tài)進(jìn)行。n運行時動態(tài)裝入需要硬件支持，即重定位寄存器，用于保存程序在內(nèi)存中的起始地址。

13、n程序被執(zhí)行時，通過重定位寄存器內(nèi)的起始物理地址和指令或數(shù)據(jù)的邏輯地址計算其物理地址。n運行時動態(tài)裝入有利于多道程序環(huán)境下，進(jìn)程的換入/換出及實現(xiàn)緊湊技術(shù)。動態(tài)運行時裝入把程序裝入到起始地址為把程序裝入到起始地址為1000的內(nèi)存區(qū)的內(nèi)存區(qū)Mov r1,50012340100500599作業(yè)的地址空間作業(yè)的地址空間Mov r1,500010001100150015991234存儲空間存儲空間1000+BR邏輯地址邏輯地址物理地址物理地址動態(tài)運行時裝入動態(tài)運行時裝入100VR可執(zhí)行程序的鏈接n目標(biāo)模塊如何鏈接成裝入模塊？n2種鏈接方式：p靜態(tài)鏈接p動態(tài)鏈接： 裝入時動態(tài)鏈接 運行時動態(tài)鏈接靜態(tài)鏈接

14、n程序被裝入內(nèi)存之前，必須完全鏈接成一個裝入模塊，將其中的存儲引用全部轉(zhuǎn)換成相對地址跳轉(zhuǎn)語句，并將多個目標(biāo)模塊鏈接稱為一個模塊，使裝入模塊中的每一條指令具有相對于整個模塊的第一條語句的邏輯地址。n靜態(tài)鏈接生成的裝入模塊可以采用重定位裝入或運行時動態(tài)裝入方式。n靜態(tài)鏈接需要花費大量的處理機(jī)時間。而其中的很多模塊將不會運行，浪費存儲空間和處理機(jī)時間。目標(biāo)模塊鏈接成裝入模塊模塊1if(x1)call m1else call m2模塊m1模塊m2模塊1if(x1)模塊m1Else模塊m2鏈接目標(biāo)模塊裝入模塊動態(tài)鏈接n不用事先鏈接多個目標(biāo)模塊形成一個完備的裝入模塊，而是生成一個含有未被鏈接的外部模塊引用

15、的裝入模塊，這些外部模塊可以在裝入時鏈接，也可以在運行時鏈接。裝入時動態(tài)鏈接n 當(dāng)系統(tǒng)裝入含有未鏈接的外部模塊引用的裝入模塊時，每當(dāng)遇到一個外部模塊引用，則查找相應(yīng)的目標(biāo)模塊。將其裝入內(nèi)存，并將模塊內(nèi)的指令地址轉(zhuǎn)換為相對于整個裝入模塊起始地址的相對地址。n優(yōu)點：有利于目標(biāo)模塊的更新與升級；有利于代碼共享；有利于擴(kuò)充軟件的功能，可以將擴(kuò)充部分作為動態(tài)鏈接模塊。n但是，可能鏈接一些不會執(zhí)行的模塊，浪費存儲空間和處理機(jī)時間。運行時動態(tài)鏈接n外部模塊引用直至程序執(zhí)行時才裝入內(nèi)存，并鏈接到裝入模塊中，進(jìn)行地址轉(zhuǎn)換。n可以解決靜態(tài)鏈接和裝入時動態(tài)鏈接都面臨的存儲空間和處理機(jī)時間浪費問題，不需要執(zhí)行的模塊就

16、不會裝入內(nèi)存。n廣泛用于事務(wù)處理系統(tǒng)，如航空售票系統(tǒng)、銀行管理系統(tǒng)等。簡單存儲n簡單存儲，或基本存儲，相對于虛擬存儲而言，指為了實現(xiàn)簡單，執(zhí)行之前，操作系統(tǒng)必須將待執(zhí)行的程序全部裝入內(nèi)存。n然而，現(xiàn)代操作系統(tǒng)大都支持虛擬存儲功能，允許進(jìn)程裝入部分程序即可執(zhí)行，其余部分保留在外存。當(dāng)執(zhí)行所需的部分不在內(nèi)存時，中斷進(jìn)程執(zhí)行，使之阻塞等待，直到相應(yīng)部分裝入內(nèi)存。程序在內(nèi)存中如何組織n連續(xù)存儲：需要內(nèi)存中一塊連續(xù)的、足夠大的分區(qū) n如果內(nèi)存中沒有足夠大的連續(xù)內(nèi)存分區(qū)，但存在總量足夠的獨立小分區(qū)，即外零頭。系統(tǒng)要么拒絕分配空間，要么采用緊湊技術(shù)拼接外零頭。n采用的連續(xù)存儲技術(shù)：分區(qū)管理程序在內(nèi)存中如何組

17、織n非連續(xù)存儲：允許進(jìn)程的程序和數(shù)據(jù)分別裝在內(nèi)存的不同分區(qū)中n必須登記一個進(jìn)程分到的所有分區(qū)的位置、大小、使用情況等信息。n采用的非連續(xù)存儲技術(shù)：分頁存儲技術(shù)、分段存儲技術(shù)及段頁式存儲技術(shù)。4.3 4.3 連續(xù)分配方式連續(xù)分配方式連續(xù)分配n連續(xù)分配是指為用戶程序分配連續(xù)的內(nèi)存空間。n分類單一連續(xù)分配分區(qū)管理 固定分區(qū) 動態(tài)分區(qū) 動態(tài)重定位分區(qū) 單一連續(xù)分配方式n這是一種最簡單的存儲管理方式n在這種管理方式下，內(nèi)存區(qū)分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅供操作系統(tǒng)使用，用戶區(qū)提供給用戶使用n只能用于單用戶、單任務(wù)的操作系統(tǒng)中n不支持虛擬存儲方式單一連續(xù)分配方式n優(yōu)點：管理簡單，易于實現(xiàn)存儲保護(hù)n缺點

18、：系統(tǒng)的存儲空間浪費較大當(dāng)正在執(zhí)行的程序因等待某個事件，如等待外部設(shè)備輸入數(shù)據(jù)，處理機(jī)就處于空閑狀態(tài)。限制了用戶程序和系統(tǒng)程序的可重入性，因而主存中的程序和數(shù)據(jù)不能被共享。系統(tǒng)的外圍設(shè)備也只有一個程序使用，因此外圍設(shè)備的利用率低。分區(qū)管理n基本思想： 將內(nèi)存的用戶可用區(qū)劃分成若干個大小相等或不等的區(qū)域，每個進(jìn)程占據(jù)一個區(qū)域，從而實現(xiàn)多道程序設(shè)計環(huán)境下各并發(fā)進(jìn)程共享主存空間。n分類p固定分區(qū)p動態(tài)分區(qū)p可重定位分區(qū)固定分區(qū)管理n一種最簡單的可運行多道程序的存儲管理方式n將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，每個分區(qū)只裝入一道作業(yè)，這樣允許有幾道作業(yè)并發(fā)運行。n當(dāng)有空閑分區(qū)時，便可從外存的后備

19、作業(yè)隊列中選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)。劃分分區(qū)的方法n分區(qū)大小相等分區(qū)大小相等：所有的內(nèi)存分區(qū)大小相等。這種方法只適合于多個相同程序的并發(fā)執(zhí)行。n分區(qū)大小不等分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，可根據(jù)程序的大小為之分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。固定分區(qū)Operating System8M8M8M8M8M固定分區(qū)（大小相同）固定分區(qū)（大小相同）Operating System8M2M6M8M12M4M固定分區(qū)（大小不同）固定分區(qū)（大小不同）固定分區(qū)的內(nèi)存分配分區(qū)號分區(qū)號大小大小起始地址起始地址狀態(tài)狀態(tài)11220已分配已分配23232已分配已

20、分配36464已分配已分配4128128已分配已分配操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A作業(yè)作業(yè)B作業(yè)作業(yè)C作業(yè)作業(yè)D20K32K64K128K256K分區(qū)說明表分區(qū)說明表存儲空間分配情況存儲空間分配情況n 建立分區(qū)說明表來描述各個分區(qū)的分配情況。固定分區(qū)n優(yōu)點：簡單n缺點：內(nèi)存利用不充分。因為作業(yè)的大小不可能剛好等于某個分區(qū)的大小，絕大多數(shù)已分配的分區(qū)中，都有一部分存儲空間被浪費掉了，這個被浪費的空間叫做內(nèi)部碎片（占用分區(qū)之內(nèi)未被利用的空間）。動態(tài)分區(qū)分配n系統(tǒng)初始化時，除了操作系統(tǒng)中常駐主存部分以外，只存在一個空閑分區(qū)n分配程序根據(jù)進(jìn)程的大小動態(tài)的劃分分區(qū)n特點：p各分區(qū)的大小是不定的p內(nèi)存中分區(qū)的

21、數(shù)目也是不定的動態(tài)分區(qū)分配FIFO調(diào)度方式時的內(nèi)存初始分配情況調(diào)度方式時的內(nèi)存初始分配情況動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)n空閑分區(qū)表（鏈）：所有的空閑分區(qū)組成的一個表（鏈），用來記錄內(nèi)存中每個空閑分區(qū)的情況：包括分區(qū)序號，分區(qū)始址，分區(qū)大小等數(shù)據(jù)項。n已分配分區(qū)表：所有已分配分區(qū)組成的一個表，用來記錄內(nèi)存中每個已分配分區(qū)的情況：包括分區(qū)序號，分區(qū)始址，分區(qū)大小等數(shù)據(jù)項。動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表空閑分區(qū)表空閑分區(qū)鏈空閑分區(qū)鏈連續(xù)分配方式（續(xù)）連續(xù)分配方式（續(xù)）利用空閑區(qū)表和已分配區(qū)表分配內(nèi)存利用空閑區(qū)表和已分配區(qū)表分配內(nèi)存連續(xù)分配方式（續(xù)）連續(xù)分配方式（續(xù)）利用空閑區(qū)表和已分配區(qū)表分配內(nèi)存利

22、用空閑區(qū)表和已分配區(qū)表分配內(nèi)存分配內(nèi)存操作n(1)利用某種算法，從空閑分區(qū)中找到所需大小的分區(qū)。n(2)若找到的空閑分區(qū)和請求的分區(qū)的差值大于事先規(guī)定的不再切割的剩余分區(qū)的大小，則將空閑分區(qū)一分為二，一部分分配給進(jìn)程，另一部分仍作為空閑區(qū)留在表中。n(3)將分配區(qū)的首址返回給調(diào)用者。動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法n首次適應(yīng)算法（First Fit，F(xiàn)F）n循環(huán)首次適應(yīng)算法(Next Fit，NF)n最佳適應(yīng)法(Best Fit，BF)首次適應(yīng)算法n首次適應(yīng)算法：要求空閑分區(qū)按地址遞增的次序排列。當(dāng)進(jìn)行內(nèi)存分配時，從空閑區(qū)鏈（表）鏈?zhǔn)组_始順序查找，直到找到第一個能滿足其大小要求的空閑區(qū)為止。分

23、一塊給請求者，余下部分仍留在空閑鏈中。n特點：優(yōu)先利用低地址部分的空閑分區(qū)，保留了高地址部分的大空閑區(qū)。低地址端可能留下許多很小的空閑分區(qū)，而每次查找是從低地址部分開始，會增加查找開銷。連續(xù)分配方式（續(xù)）連續(xù)分配方式（續(xù)）循環(huán)首次適應(yīng)算法n由首次適應(yīng)算法演化而來。在為進(jìn)程分配內(nèi)存空間時，不再每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，從中劃分出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。n特點：p使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時的開銷。p缺乏大的空閑分區(qū)。最佳適應(yīng)法n要掃描所有的空閑分區(qū)，以獲得能滿足進(jìn)程需求的且

24、為最小的空閑區(qū)。如果該空閑分區(qū)大于作業(yè)的大小，則將剩余空閑區(qū)仍留在空閑區(qū)鏈表中。n可從小到大對空閑區(qū)排序，方便查找。n特點：p因為分配分區(qū)要查找整個鏈表，所以比首次適應(yīng)算法效率低。p因為它可能把主存劃分得更小，成為無用的碎片（外部碎片），所以它比首次適應(yīng)要浪費更多的存儲空間?；厥諆?nèi)存操作n進(jìn)程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈（表）中找到插入點?？赡軙霈F(xiàn)以下四種情況之一：F1回收區(qū) 回收區(qū)F2F1回收區(qū)F2F1回收區(qū)F2回收內(nèi)存操作p回收區(qū)與插入點的前一個空閑分區(qū)相鄰接：此時將回收區(qū)與前一個分區(qū)合并，不必為回收分區(qū)分配新的表項，只需修改前一分區(qū)的大小。p回收分區(qū)與插入點的后

25、一空閑分區(qū)相鄰接：此時將兩個分區(qū)合并，形成新的空閑分區(qū)，用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。p回收區(qū)同時與插入點的前后兩個分區(qū)鄰接：此時將三個分區(qū)合并，使用前一個分區(qū)的表項和首址，取消后一個分區(qū)的表項，大小為三個分區(qū)大小之和。p回收區(qū)既不與插入點的前一個空閑分區(qū)鄰接，也不與后一個空閑分區(qū)鄰接：這時應(yīng)為回收區(qū)單獨建一個表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑區(qū)鏈（表）的適當(dāng)位置。分區(qū)管理方式n 優(yōu)點：p有助于多道程序設(shè)計，提高了內(nèi)存的利用率p要求硬件支持少，代價低 p管理算法簡單，實現(xiàn)容易n 缺點：p必須給作業(yè)分配一連續(xù)的內(nèi)存區(qū)域 p不能實現(xiàn)對內(nèi)存的擴(kuò)充p碎片問題嚴(yán)重，

26、內(nèi)存仍不能得到充分利用 n 解決“碎片”問題的一種方法緊湊 內(nèi)存拼接（緊湊）n如果作業(yè)請求的存儲空間大于系統(tǒng)中任何一個空閑分區(qū)，但小于這些分區(qū)容量的總和時，利用動態(tài)重定位方法，移動內(nèi)存中的所有作業(yè)，使它們在內(nèi)存相鄰接。這樣，我們不需要對作業(yè)做任何修改，只要用該作業(yè)在內(nèi)存的新起始地址，去置換原來的起始地址即可。n這種通過移動內(nèi)存中作業(yè)的位置，把原來多個分散的小的空閑分區(qū)拼接成一個大空閑分區(qū)的方法，稱為“拼接”或“緊湊”。內(nèi)存拼接（緊湊）內(nèi)存拼接（緊湊）n 代價與時間 緊湊的開銷很大，當(dāng)系統(tǒng)中每個空閑區(qū)域單獨均不能滿足進(jìn)程請求的空間大小，但所有空閑區(qū)域之和能夠滿足時才進(jìn)行一次緊湊。n 思考:如何實

27、現(xiàn)緊湊? 動態(tài)地址重定位加入緊湊功能的動態(tài)重定位分區(qū)分配算法 動態(tài)分區(qū)分配算法流程圖動態(tài)分區(qū)分配算法流程圖 請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否連續(xù)分配和離散分配n連續(xù)分配即要求給進(jìn)程分配連續(xù)的內(nèi)存空間。n連續(xù)分配方式會形成許多“碎片”，系統(tǒng)為拼接碎片會花費很大的系統(tǒng)開銷。n離散分配：即允許一個進(jìn)程直接分散地裝入到許多不相鄰接的分區(qū)中。n如果離散分配的基本單位是頁，則稱之為分頁式存儲管理方式；如果離散分配的基本單位是

28、段，則稱為分段式存儲管理方式。4.4 4.4 基本分頁存儲管理方式基本分頁存儲管理方式基本分頁存儲管理方式的實現(xiàn)原理n將一個進(jìn)程的邏輯地址空間分成若干個大小相等的頁，同時把內(nèi)存空間以與頁相等的大小劃分為大小相等的內(nèi)存塊（物理塊），這些內(nèi)存塊為系統(tǒng)中的任何進(jìn)程所共享。在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。實現(xiàn)原理示意圖用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁內(nèi)存012345678910指定進(jìn)程頁到空閑物理塊01234567891011121314內(nèi)存15個可用幀A.0A.1A.2A.301234567891011121314內(nèi)存加載進(jìn)程A

29、A.0A.1A.2A.3B.0B.1B.201234567891011121314內(nèi)存加載進(jìn)程BA.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.301234567891011121314內(nèi)存加載進(jìn)程C指定進(jìn)程頁到空閑物理塊A.0A.1A.2A.3C.0C.1C.2C.301234567891011121314內(nèi)存換出BA.0A.1A.2A.3D.0D.1D.2C.0C.1C.2C.3D.3D.401234567891011121314內(nèi)存加載進(jìn)程D頁面和物理塊n頁面：進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。n物理塊

30、：內(nèi)存空間被分成與頁面相同大小的若干個存儲塊，稱為物理塊或內(nèi)存塊， 也同樣為它們加以編號，如0塊、1塊等等。頁表n頁表是系統(tǒng)為每個用戶進(jìn)程建立的一張頁面映像表，用來記錄進(jìn)程的每個頁面對應(yīng)的物理塊，一般放在內(nèi)存。n頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射頁表的作用用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內(nèi)存012345678910頁面大小n在分頁系統(tǒng)中頁面的大小是由機(jī)器的地址結(jié)構(gòu)所決定的，亦即由硬件決定。對于某一種機(jī)器只能采用一種大小的頁面。n頁面的大小要選擇的適中。p若選擇的頁面較小，雖然可使內(nèi)存碎片減小，提高內(nèi)存利用率，但也會使每個進(jìn)程占用較多的

31、頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存； p若選擇的頁面較大，雖然可以減少頁表的長度，但卻又會使頁內(nèi)碎片增大。p通常頁面的大小是2的冪，且常在29-212之間，即在512字節(jié)-4K字節(jié)之間地址變換n地址變換即通過地址變換機(jī)構(gòu)把邏輯地址變換成相應(yīng)的物理地址，實際上是將邏輯地址中的頁號，轉(zhuǎn)換為內(nèi)存中的物理塊號。因為頁表的作用就是用于實現(xiàn)頁號到物理塊號的地址映射，因此，地址變換任務(wù)是借助于頁表來完成的n除此以外，系統(tǒng)設(shè)置了一個頁表寄存器PTR,其中存放頁表在內(nèi)存的始址和頁表的長度 頁表寄存器頁表寄存器n用來存放頁表在內(nèi)存的起始地址和長度的寄存器。n平時，進(jìn)程未執(zhí)行時，頁表的始址和頁表長度存放在本

32、進(jìn)程的PCB中，當(dāng)調(diào)度程序調(diào)度到某進(jìn)程時，才將這兩個數(shù)據(jù)裝入頁表寄存器。 動態(tài)地址變換n 地址結(jié)構(gòu)p邏輯地址可以分解成：頁號、頁內(nèi)位移量（頁內(nèi)地址） p物理地址可以分解成：物理塊號、物理塊內(nèi)位移（物理塊內(nèi)地址） 頁號頁號p p 頁內(nèi)位移量頁內(nèi)位移量w w 0 0111112 12 3131p=邏輯地址/頁面大小 w=邏輯地址%頁面大小地址變換過程 根據(jù)邏輯地址計算出頁號p和頁內(nèi)地址d， p=邏輯地址/頁面大小 d=邏輯地址%頁面大小 根據(jù)頁號p查頁表，得到對應(yīng)塊號f 塊內(nèi)地址和頁內(nèi)地址相同，計算物理地址 物理地址=f塊大小+d （塊大小等于頁大?。﹏ 由于頁面大小為2的冪，則頁號和頁內(nèi)地址可以

33、直接取高位和低位部分獲得，物理地址可以用塊號和塊內(nèi)地址拼接而成分頁系統(tǒng)的地址變換機(jī)構(gòu)分頁系統(tǒng)的地址變換機(jī)構(gòu)頁表寄存器頁表始址頁表長度頁號(3)頁內(nèi) 地 址邏輯地址L越界中斷1塊號b頁表頁號012物理地址3分頁系統(tǒng)的地址變換機(jī)構(gòu)分頁系統(tǒng)的地址變換機(jī)構(gòu)示例示例1 例例 說明運行作業(yè)的地址變換過程。說明運行作業(yè)的地址變換過程。 如下頁圖所示，作業(yè)地址空間共有如下頁圖所示，作業(yè)地址空間共有7 7個頁，每頁的大小個頁，每頁的大小為為10241024。其對應(yīng)的主存塊在頁表中已列出。其對應(yīng)的主存塊在頁表中已列出。 假定頁表假定頁表在主存始址為在主存始址為500500，頁表中每個頁表項占用一個字節(jié)。，頁表中每

34、個頁表項占用一個字節(jié)。若該程序從第若該程序從第0 0頁開始運行，且現(xiàn)程序計數(shù)器內(nèi)容（邏頁開始運行，且現(xiàn)程序計數(shù)器內(nèi)容（邏輯地址）為：輯地址）為：0100邏輯地址邏輯地址示例示例1頁表寄存器頁表寄存器邏輯地址邏輯地址L500 70 ( (頁號）頁號） 100（頁內(nèi)地址）（頁內(nèi)地址）+頁表頁表5（內(nèi)存塊號）內(nèi)存塊號） 100（頁內(nèi)地址）（頁內(nèi)地址）1234頁式地址變換過程頁式地址變換過程012345657915131016500每頁的大小每頁的大小為為10241024內(nèi)存地址：內(nèi)存地址：5 51024+100=52201024+100=5220500+0500+0* *1=5001=500示例2例

35、：在分頁存儲管理系統(tǒng)中，允許作業(yè)最大64KB，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址是多少？分析：塊內(nèi)地址=頁內(nèi)地址 塊大小=頁大小 假設(shè)為塊大小2n字節(jié),則頁內(nèi)地址和塊內(nèi)地址占n位 邏輯地址的位數(shù)為s，則作業(yè)最大可以為2s字節(jié) 邏輯地址的低n位為頁內(nèi)地址，高s-n位為頁號 物理地址的位數(shù)為t，則內(nèi)存空間大小為2t字節(jié) 物理地址的低n位為塊內(nèi)地址，高t-n位為塊號 示例2答：由題目所給條件可知，分頁存儲管理系統(tǒng)的邏輯地址結(jié)構(gòu)為： 15 12 11 0 邏輯地址2F6AH的二進(jìn)制表示如下： 0010 11110110

36、1010 頁號 頁內(nèi)位移 由此可知邏輯地址2F6AH的頁號為2，小于頁表長度3，沒有越界，該頁存放在第11個物理塊中，用十六進(jìn)制表示塊號為B，所以物理地址為BF6AH。 頁號頁號 頁內(nèi)位移頁內(nèi)位移快表n由于頁表存儲在內(nèi)存中，所以當(dāng)要按照給定的邏輯地址進(jìn)行讀/寫時，需要兩次訪問內(nèi)存:p第一次是根據(jù)頁號訪問頁表，讀出頁表相應(yīng)欄中的塊號以便形成物理地址；p第二次是根據(jù)物理地址進(jìn)行讀/寫操作。n這樣比通常執(zhí)行指令的速度慢一倍。為了提高存取速度，在地址變換機(jī)構(gòu)中增設(shè)了一個具有并行查找能力的特殊高速緩沖存儲器，又稱為“聯(lián)想存儲器”或“快表”，用來存儲當(dāng)前訪問的哪些頁表項。快表地址映象快表的格式- - 訪問

37、位：指示該頁最近是否被訪問過。訪問位：指示該頁最近是否被訪問過。0 0表示沒有被訪表示沒有被訪問，問，1 1表示訪問過表示訪問過 ；- - 狀態(tài)位：指示該寄存器是否被占用。狀態(tài)位：指示該寄存器是否被占用。0 0表示空閑，表示空閑，1 1表表示占用。示占用。頁頁 號號 塊塊 號號 訪訪 問問 位位 狀狀 態(tài)態(tài) 位位利用快表進(jìn)行讀/寫操作的過程n首先按邏輯地址中的頁號先查快表，若該頁在快表中，則立即能得到相應(yīng)的物理塊號并與頁內(nèi)地址形成物理地址；n若該頁不在快表中，則再查內(nèi)存中的頁表找到相應(yīng)的塊號，形成物理地址，同時將該頁的對應(yīng)項寫入快表。n若快表已滿，則按照一定策略淘汰一個舊項。最簡單的策略是“先

38、進(jìn)先出”原則，即淘汰最先進(jìn)入快表的那一項。具有快表的地址變換機(jī)構(gòu)頁表寄存器頁表始址頁表長度頁號頁內(nèi) 地 址邏輯地址L越界中斷塊號b頁表頁號頁號輸入寄存器塊號bb快表d物理地址具有快表的地址變換機(jī)構(gòu)頁表寄存器頁表寄存器邏輯地址邏輯地址L500 70 ( (頁號）頁號） 100（頁內(nèi)地址）（頁內(nèi)地址）+頁表頁表5（內(nèi)存塊號）內(nèi)存塊號） 100（頁內(nèi)地址）（頁內(nèi)地址）12345使用快表后的地址變換過程使用快表后的地址變換過程012345657915131016500每頁的大小每頁的大小為為10241024內(nèi)存地址：內(nèi)存地址：5 51024+100=52201024+100=5220500+0=500

39、500+0=50005快表快表越界中斷越界中斷基本分頁存儲管理方式的分配算法基本分頁存儲管理方式的分配算法請求請求n個頁面?zhèn)€頁面空閑頁面表中有空閑頁面表中有n個個空閑頁面嗎？空閑頁面嗎？設(shè)置頁表，將頁表始址設(shè)置頁表，將頁表始址頁表長度置入頁表寄存器頁表長度置入頁表寄存器搜索內(nèi)存空閑頁面，分配搜索內(nèi)存空閑頁面，分配n個頁面，個頁面，將頁面號和對應(yīng)的物理塊號填入頁表將頁面號和對應(yīng)的物理塊號填入頁表無法分配無法分配否否是是分頁存儲管理的評價n徹底消除了外部碎片，僅有很少的內(nèi)部碎片，提高了內(nèi)存利用率。n分頁操作由系統(tǒng)自動完成，一個頁面不能實現(xiàn)某種邏輯功能。用戶看到的邏輯地址是一維的，無法調(diào)試執(zhí)行其中的

40、某個子程序或子函數(shù)。n采用分頁技術(shù)不易實現(xiàn)存儲共享，也不便于進(jìn)程的動態(tài)鏈接。4.5 4.5 基本分段存儲管理方式基本分段存儲管理方式基本分段存儲管理n基于模塊化的程序設(shè)計時，常常需要將一個大任務(wù)劃分成若干相對獨立的子任務(wù)，對應(yīng)于子任務(wù)編寫子程序，稱為段。n每個子程序可以獨立的編輯、編譯、鏈接和執(zhí)行n各個子程序由實現(xiàn)的功能決定，長度各不相同。執(zhí)行時，根據(jù)實際需要，將若干子程序鏈接成一個大程序?；痉侄未鎯芾矸绞降膶崿F(xiàn)原理n每個作業(yè)的邏輯地址空間按照自身的邏輯關(guān)系劃分成若干段（比如主程序段、子程序段、數(shù)據(jù)段、堆棧段等）。n每個段都有自己的名字，通常可用一個段號來代替段名。n每個段都從0開始獨立編

41、址，段內(nèi)地址連續(xù)。n段的長度由相應(yīng)的邏輯信息組的長度決定，因而各段的長度不等。n分配內(nèi)存時，為每個段分配一連續(xù)的存儲空間，段間地址空間可以不連續(xù)。作業(yè)空間(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段長 基址段號(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表內(nèi)存空間01230123邏輯段號實現(xiàn)原理段式地址結(jié)構(gòu) 段號段號 段內(nèi)地址段內(nèi)地址31 12 11 0n 每個段的地址空間都是從“0”開始編址的一維地址空間；n作業(yè)的地址空間是二維地址空間；n每一個邏

42、輯地址均由兩部分組成：段號和段內(nèi)位移；段表n用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射；n進(jìn)程的每個段在段表中占有一個表項，稱為段表項；n每個段表項由段基址、段長度和段的存取方式組成。段表作業(yè)空間(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段長 基址段號(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表內(nèi)存空間0123利用段表實現(xiàn)地址映射地址變換機(jī)構(gòu)分段系統(tǒng)的地址變換過程分段系統(tǒng)的地址變換過程8K+100存儲保護(hù)n 在分段存儲管理方式中，用戶各分段是信息的邏輯單位

43、，因此容易對各段實現(xiàn)保護(hù) 。p越界保護(hù) 在地址變換過程中，段號和段表長度的比較，以及段內(nèi)地址和段長的比較。p越權(quán)保護(hù) 在段表中設(shè)置存取控制字段來對各段進(jìn)行保護(hù)。分段系統(tǒng)的快表n分段系統(tǒng)中，為了訪問內(nèi)存中的一條指令或數(shù)據(jù)，需要兩次訪問內(nèi)存：第一次，訪問內(nèi)存中的段表，獲得段的起始地址。根據(jù)段的起始地址和段內(nèi)偏移量，計算出物理地址第二次，根據(jù)計算得到的物理地址，訪問內(nèi)存中的指令或數(shù)據(jù)。n為了提高系統(tǒng)效率，可以為分段系統(tǒng)增加一個快表，用于保存最近使用過的段表項。對分段系統(tǒng)的評價n有效消除了內(nèi)部碎片，提高了內(nèi)存利用率n允許子程序獨立編譯和修改，而不需要重新編譯或鏈接其他相關(guān)子程序n容易實現(xiàn)存儲共享n具有

44、較高的安全保障n很容易滿足程序段的動態(tài)增長需要。分頁和分段的比較n都采用非連續(xù)存儲，由地址映射實現(xiàn)地址變換n區(qū)別：頁是信息的物理單位，分頁是為了系統(tǒng)管理內(nèi)存的方便而進(jìn)行的，故對用戶而言，分頁是不可見的，是透明的；段是信息的邏輯單位，分段是作業(yè)邏輯上的要求，對用戶而言，分段是可見的。頁的大小是固定的，由系統(tǒng)決定；段的大小是不固定的，由用戶作業(yè)本身決定。從用戶角度看，分頁的地址空間是一維的，而段的地址空間是二維的 。段的共享與保護(hù)n段是信息的邏輯單位，分段式存儲管理可以方便的實現(xiàn)內(nèi)存信息共享，并有效進(jìn)行內(nèi)存保護(hù)。信息共享例：一個多用戶系統(tǒng)，可同時接納40個用戶，他們都執(zhí)行一個文本編輯程序。如果文本

45、編輯程序有160KB的代碼和另外40KB的數(shù)據(jù)區(qū)，則總共需要8MB的內(nèi)存空間來支持40個用戶。如果160KB的代碼是可重入的代碼，則無論是在分頁式系統(tǒng)還是在分段式系統(tǒng)中，該代碼都可以被共享，即在內(nèi)存中只保留一份文本編輯程序的副本，此時需要的內(nèi)存空間僅為1760KB。分頁式系統(tǒng)中的信息共享ed 1ed 2ed 40data 1data 10進(jìn)程12122606170頁表ed 1ed 2ed 40data 1data 10進(jìn) 程 22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180頁表分頁系統(tǒng)中共享editor的示意

46、圖分段式系統(tǒng)中的信息共享editor進(jìn)程1data 1進(jìn)程2editordata 2段表段長 基址16080402401608040380editordata 1data 280240280380420分段系統(tǒng)中共享editor的示意圖段的共享n段的共享是指兩個以上的作業(yè)使用某個子程序或數(shù)據(jù)段，而在內(nèi)存中只保留該信息的一個副本n實現(xiàn)：只需在每個進(jìn)程的段表中，用相應(yīng)的表項來指向共享段在內(nèi)存的起始地址即可。n在共享中必須小心處理的一個問題是共享段的保護(hù)問題。共享段表n由于各進(jìn)程對共享段的使用情況不同，每個進(jìn)程為其分配的段號也不同。為了便于多進(jìn)程共享主存中的公用子程序，可在內(nèi)存中設(shè)置一個共享段段表。

47、共享段表n共享進(jìn)程計數(shù) 記錄有多少個進(jìn)程需要共享該分段n存取控制字段 用來記錄不同的進(jìn)程對于同一共享段具有的不同的存取權(quán)限n段號 不同的進(jìn)程可以用不同的段號去共享該段共享段的分配與回收n分配 在為共享段分配內(nèi)存時，對第一個請求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進(jìn)程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段表中，增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進(jìn)程的進(jìn)程名、

48、存取控制等，再執(zhí)行count =count+1操作，以表明有兩個進(jìn)程共享該段。共享段的分配與回收n回收 當(dāng)共享此段的某進(jìn)程不再需要該段時，應(yīng)將該段釋放， 包括撤銷在該進(jìn)程在共享段表中共享段所對應(yīng)的表項，以及執(zhí)行count =count-1操作。若結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項， 表明此時已沒有進(jìn)程使用該段；否則(減1結(jié)果不為0)， 則只是取消調(diào)用者進(jìn)程在共享段表中的有關(guān)記錄。分段保護(hù) n在分段存儲管理方式中，用戶各分段是信息的邏輯單位，因此容易對各段實現(xiàn)保護(hù) 。n越界檢查p邏輯地址中的段號和段表寄存器中的段表長度比較，若段號段長，則發(fā)出地址越界

49、中斷信號；p利用段表中的段長和邏輯地址中的段內(nèi)地址相比較，如段內(nèi)地址段長，則發(fā)出地址越界中斷，系統(tǒng)便會對段進(jìn)行保護(hù)。n存取控制檢查（訪問越權(quán)保護(hù)）p只讀 p只執(zhí)行 p讀/寫 分段保護(hù)n環(huán)保護(hù)機(jī)構(gòu) 這是一種功能較完善的保護(hù)機(jī)制，該機(jī)制規(guī)定，低編號的環(huán)具有高優(yōu)先權(quán)。Os核心處于0環(huán)，某些重要的實用程序和操作系統(tǒng)服務(wù)占據(jù)中間環(huán)（1環(huán)），而一般的應(yīng)用程序在最外環(huán)（2環(huán)）。環(huán)系統(tǒng)中遵循以下規(guī)則：一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)分段保護(hù)調(diào)用返回調(diào)用返回環(huán)0環(huán)1環(huán)2(a) 程序間的控制傳輸數(shù)據(jù)訪問環(huán)0環(huán)1環(huán)2(b) 數(shù)據(jù)訪問數(shù)據(jù)訪問段頁式存儲管

50、理方式n分頁存儲管理有利于內(nèi)存利用率的提高，分段存儲管理有利于程序設(shè)計，把兩種方式結(jié)合起來，形成了段頁式存儲管理方式。n基本思想：采用分段方法組織用戶程序，采用分頁方法分配和管理內(nèi)存。n即，用戶程序可以用模塊化思想進(jìn)行設(shè)計，一個用戶程序由若干段組成；系統(tǒng)將內(nèi)存劃分成固定大小的物理塊，并將程序的每一段分割成若干頁后裝入內(nèi)存并執(zhí)行。段頁式存儲管理方式 n基本原理04K8K12K15K16K子 程 序 段04K8K數(shù) 據(jù) 段04K8K10K12K(a)段 號 (S)段 內(nèi) 頁 號 (P)段 內(nèi) 地 址 (W)(b)主 程 序 段作業(yè)地址空間和地址結(jié)構(gòu)段頁式系統(tǒng)中的地址映射段號 狀態(tài) 頁表大小頁表始址

51、0111213041頁號 狀態(tài) 存儲塊#0111213041操作系統(tǒng)主存頁表段表段表大小段表始址段表寄存器利用段表和頁表實現(xiàn)地址映射段頁式系統(tǒng)中的地址變換過程 段表寄存器段表始址 段表長度段號 S 頁號 P段超長段表0123頁內(nèi)地址頁表0123b塊號 b 塊內(nèi)地址頁表始址頁表長度段頁式系統(tǒng)中的地址變換機(jī)構(gòu)快表n第一次，訪問段表，從中取得該段的頁表首址n第二次，訪問頁表，從中取出邏輯地址指定的頁面所在的物理塊號，并將該物理塊號和頁內(nèi)地址相加，形成指令或數(shù)據(jù)的物理地址。n第三次，訪問內(nèi)存，根據(jù)前面計算得到的物理地址，取出對應(yīng)存儲單元的指令或數(shù)據(jù)。n可以在地址變換機(jī)構(gòu)中增設(shè)一個高速緩沖存儲器，里面保

52、存 最近使用過的頁號及其所屬的段號。4.7 4.7 虛擬存儲器虛擬存儲器簡單存儲n簡單存儲：要求將一個進(jìn)程所需要的程序和數(shù)據(jù)全部裝入內(nèi)存方可運行。n簡單存儲中出現(xiàn)的兩種情況：p對于大進(jìn)程，如果其要求的內(nèi)存空間超過了內(nèi)存最大容量，致使進(jìn)程無法運行；p對于多道程序系統(tǒng)，由于每一個進(jìn)程需要全部裝入主存，使同時駐留內(nèi)存的進(jìn)程數(shù)量受到限制。雖然也能通過提高內(nèi)存容量來解決，但代價高。解決方法n如果能將一部分價格較低的外存空間充當(dāng)內(nèi)存使用，從邏輯上擴(kuò)充內(nèi)存容量。進(jìn)程運行之前，僅需要將一部分程序和數(shù)據(jù)（幾個頁面或段）裝入內(nèi)存，便可啟動運行，其余部分暫時保留在磁盤上。那么，將獲得更高的性價比。虛擬存儲技術(shù)的理論

53、依據(jù)n程序的局部性原理：研究表明，程序在執(zhí)行過程中呈現(xiàn)局部性原理。n這種局部性表現(xiàn)在兩個方面：p時間局部性：一條指令被執(zhí)行后，那么它可能很快會再次被執(zhí)行； p空間局部性：若某一存儲單元被訪問，那么與該存儲單元相鄰的單元可能也會很快被訪問。n因此，只要保證進(jìn)程執(zhí)行所需要的部分程序和數(shù)據(jù)駐留內(nèi)存，一段時間內(nèi)進(jìn)程都能順利執(zhí)行。實現(xiàn)虛擬存儲的一般過程n進(jìn)程運行之前，僅需要將一部分頁面或段裝入內(nèi)存，便可啟動運行，其余部分暫時保留在磁盤上；n進(jìn)程運行時，如果它所需要訪問的頁面（段）已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去；n如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，則發(fā)生缺頁（段）中斷，進(jìn)程阻塞；n此時，系統(tǒng)將啟

54、動請求調(diào)頁（段）功能，將進(jìn)程所需的頁（段）裝入內(nèi)存。實現(xiàn)虛擬存儲的一般過程n如果當(dāng)前內(nèi)存已滿，無法裝入新的頁面（段） ，則還需要利用頁（段）置換功能，將內(nèi)存中暫時不用的頁（段）交換到磁盤上，以騰出足夠的內(nèi)存空間。n再將進(jìn)程所需的頁（段）裝入內(nèi)存，喚醒阻塞的進(jìn)程，使之重新參與調(diào)度執(zhí)行。虛擬存儲器n指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。n虛擬存儲器的邏輯容量由內(nèi)存和部分外存之和來確定，其運行速度接近于內(nèi)存速度，而每位的成本接近于外存。引入虛擬存儲技術(shù)的好處n大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；n大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間遠(yuǎn)遠(yuǎn)大于物理

55、內(nèi)存(real memory)；n并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；n易于開發(fā)：與覆蓋技術(shù)比較，不需要提供編程時的程序結(jié)構(gòu)。虛擬存儲器的特征n多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行， 多次性是虛擬存儲器最重要的特征。n對換性：指允許在作業(yè)的運行過程中進(jìn)行換進(jìn)、換出。 換進(jìn)和換出能有效地提高內(nèi)存利用率n虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實際內(nèi)存容量。注意： 虛擬性以多次性和對換性為基礎(chǔ)。而多次性和對換性，又必須建立在離散分配的基礎(chǔ)上 虛擬存儲器的實現(xiàn)n虛擬存儲器的實現(xiàn)建立在離散分配的存儲管理方式基礎(chǔ)上p在分頁系統(tǒng)的基礎(chǔ)上增加請求調(diào)頁功能和頁面置換功能，形成頁式虛

56、擬存儲系統(tǒng) p在分段系統(tǒng)的基礎(chǔ)上增加請求調(diào)段功能和分段置換功能，形成段式虛擬存儲系統(tǒng)虛擬存儲技術(shù)的技術(shù)支持n首先，必須有相應(yīng)的硬件支持，用以實現(xiàn)分頁或分段存儲管理。n其次，操作系統(tǒng)必須提供相應(yīng)的軟件支持，管理頁或段在內(nèi)存和外存之間的移動。虛擬存儲的好處n可以運行大程序，包括超過內(nèi)存實際容量的大程序。n可以在有限的物理內(nèi)存中運行更多的程序。4.8 4.8 請求分頁式存儲管理方式請求分頁式存儲管理方式基本原理n在作業(yè)或進(jìn)程開始執(zhí)行之前，只裝入作業(yè)或進(jìn)程的一部分，其他部分則在執(zhí)行過程中動態(tài)裝入。n調(diào)入方式：當(dāng)需要執(zhí)行某條指令而又發(fā)現(xiàn)它不在內(nèi)存時或當(dāng)執(zhí)行某條指令需要訪問其他的數(shù)據(jù)或指令時，該指令和數(shù)據(jù)

57、不在內(nèi)存中，從而發(fā)生缺頁中斷，系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存。請求分頁中的硬件支持 頁表頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存地址外存地址 狀態(tài)位P：指示該頁是否在內(nèi)存訪問字段A：指示該頁最近是否被訪問過修改位：記錄頁面在調(diào)入內(nèi)存后是否被修改過外存地址：記錄該頁在外存上的地址請求分頁中的硬件支持缺頁中斷機(jī)構(gòu)n請求分頁式系統(tǒng)中，CPU硬件一定要提供對缺頁中斷的支持，根據(jù)頁表項中的狀態(tài)位判斷是否產(chǎn)生缺頁中斷。n缺頁中斷是一個比較特殊的中斷，主要體現(xiàn)在以下方面：p缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號。 通常，CPU都是在一條指令執(zhí)行完后去檢查是否有中斷

58、請求到達(dá)。缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時產(chǎn)生的。p一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。 因此，系統(tǒng)中的硬件機(jī)構(gòu)應(yīng)能保存多次中斷時的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處繼續(xù)執(zhí)行。n發(fā)生缺頁中斷后，操作系統(tǒng)做什么？去外存調(diào)頁。n調(diào)頁過程？ 請求分頁中的地址變換過程請求分頁中的地址變換過程請求分頁中的硬件支持地址變換機(jī)構(gòu) 發(fā)生缺頁中斷時，操作系統(tǒng)要去外存調(diào)頁。中斷處理程序首先保存CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺頁面調(diào)入內(nèi)存，讓后修改頁表。如果

59、內(nèi)存已滿，則需要按照某種頁面置換算法從內(nèi)存中選出一頁準(zhǔn)備換出，如果此頁未被修改過，可不必將該頁寫回磁盤，但如果此頁已被修改，則必須將它寫回磁盤，然后將所缺的頁面調(diào)入內(nèi)存，并修改頁表中相應(yīng)表項，并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個頁面調(diào)入過程對用戶是透明的。虛擬存儲系統(tǒng)的軟件策略n最小物理塊數(shù)的確定n物理塊的分配策略n調(diào)頁策略n置換策略n置換算法n清除策略最小物理塊數(shù)的確定n最小物理塊數(shù)：是指能保證進(jìn)程正常運行所需的最少物理塊數(shù)。n分配給每個活躍進(jìn)程的物理塊數(shù)越少，同時駐留內(nèi)存的活躍進(jìn)程數(shù)就越多，進(jìn)程調(diào)度能調(diào)度就緒進(jìn)程的

60、概率就越大。然而，這將導(dǎo)致進(jìn)程發(fā)生缺頁中斷的概率較大；n為進(jìn)程分配過多的物理塊數(shù)，并不能顯著地降低其缺頁中斷率。n最少物理塊數(shù)與計算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。物理塊的分配策略n固定分配：基于進(jìn)程的類型或根據(jù)程序員的建議，為每個進(jìn)程分配一定數(shù)量的物理塊，在整個運行期間都不再改變n可變分配：根據(jù)進(jìn)程的類型或根據(jù)程序員的要求，為每個進(jìn)程分配一定數(shù)目的物理塊；隨著程序的執(zhí)行，可以動態(tài)的為進(jìn)程增加或減少物理塊。物理塊的分配算法n平均分配算法:將系統(tǒng)中所有可供分配的物理塊，等分給各個的進(jìn)程。n按比例分配算法：根據(jù)進(jìn)程的大小按比例分配物理塊。如果系統(tǒng)各進(jìn)程頁面數(shù)總和為S,又假設(shè)m為