第四章_存儲(chǔ)器管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、作業(yè)隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)。劃分分區(qū)的方法n分區(qū)大小相等分區(qū)大小相等：所有的內(nèi)存分區(qū)大小相等。這種方法只適合于多個(gè)相同程序的并發(fā)執(zhí)行。n分區(qū)大小不等分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，可根據(jù)程序的大小為之分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。固定分區(qū)Operating System8M8M8M8M8M固定分區(qū)（大小相同）固定分區(qū)（大小相同）Operating System8M2M6M8M12M4M固定分區(qū)（大小不同）固定分區(qū)（大小不同）固定分區(qū)的內(nèi)存分配分區(qū)號(hào)分區(qū)號(hào)大小大小起始地址起始地址狀態(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ū)說(shuō)明表分區(qū)說(shuō)明表存儲(chǔ)空間分配情況存儲(chǔ)空間分配情況n 建立分區(qū)說(shuō)明表來(lái)描述各個(gè)分區(qū)的分配情況。固定分區(qū)n優(yōu)點(diǎn)：簡(jiǎn)單n缺點(diǎn)：內(nèi)存利用不充分。因?yàn)樽鳂I(yè)的大小不可能剛好等于某個(gè)分區(qū)的大小，絕大多數(shù)已分配的分區(qū)中，都有一部分存儲(chǔ)空間被浪費(fèi)掉了，這個(gè)被浪費(fèi)的空間叫做內(nèi)部碎片（占用分區(qū)之內(nèi)未被利用的空間）。動(dòng)態(tài)分區(qū)分配n系統(tǒng)初始化時(shí)，除了操作系統(tǒng)中常駐主存部分以外，只存在一個(gè)空閑分區(qū)n分配程序根據(jù)進(jìn)程的大小動(dòng)態(tài)的劃分分區(qū)n特點(diǎn)：p各分區(qū)的大小是不定的p內(nèi)存中分區(qū)的

21、數(shù)目也是不定的動(dòng)態(tài)分區(qū)分配FIFO調(diào)度方式時(shí)的內(nèi)存初始分配情況調(diào)度方式時(shí)的內(nèi)存初始分配情況動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)n空閑分區(qū)表（鏈）：所有的空閑分區(qū)組成的一個(gè)表（鏈），用來(lái)記錄內(nèi)存中每個(gè)空閑分區(qū)的情況：包括分區(qū)序號(hào)，分區(qū)始址，分區(qū)大小等數(shù)據(jù)項(xiàng)。n已分配分區(qū)表：所有已分配分區(qū)組成的一個(gè)表，用來(lái)記錄內(nèi)存中每個(gè)已分配分區(qū)的情況：包括分區(qū)序號(hào)，分區(qū)始址，分區(qū)大小等數(shù)據(jù)項(xiàng)。動(dòng)態(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ǐng)求的分區(qū)的差值大于事先規(guī)定的不再切割的剩余分區(qū)的大小，則將空閑分區(qū)一分為二，一部分分配給進(jìn)程，另一部分仍作為空閑區(qū)留在表中。n(3)將分配區(qū)的首址返回給調(diào)用者。動(dòng)態(tài)分區(qū)分配算法動(dòng)態(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)存分配時(shí)，從空閑區(qū)鏈（表）鏈?zhǔn)组_(kāi)始順序查找，直到找到第一個(gè)能滿足其大小要求的空閑區(qū)為止。分

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

24、為最小的空閑區(qū)。如果該空閑分區(qū)大于作業(yè)的大小，則將剩余空閑區(qū)仍留在空閑區(qū)鏈表中。n可從小到大對(duì)空閑區(qū)排序，方便查找。n特點(diǎn)：p因?yàn)榉峙浞謪^(qū)要查找整個(gè)鏈表，所以比首次適應(yīng)算法效率低。p因?yàn)樗赡馨阎鞔鎰澐值酶?，成為無(wú)用的碎片（外部碎片），所以它比首次適應(yīng)要浪費(fèi)更多的存儲(chǔ)空間?；厥諆?nèi)存操作n進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈（表）中找到插入點(diǎn)。可能會(huì)出現(xiàn)以下四種情況之一：F1回收區(qū) 回收區(qū)F2F1回收區(qū)F2F1回收區(qū)F2回收內(nèi)存操作p回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)相鄰接：此時(shí)將回收區(qū)與前一個(gè)分區(qū)合并，不必為回收分區(qū)分配新的表項(xiàng)，只需修改前一分區(qū)的大小。p回收分區(qū)與插入點(diǎn)的后

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

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

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

28、段，則稱為分段式存儲(chǔ)管理方式。4.4 4.4 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式的實(shí)現(xiàn)原理n將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的頁(yè)，同時(shí)把內(nèi)存空間以與頁(yè)相等的大小劃分為大小相等的內(nèi)存塊（物理塊），這些內(nèi)存塊為系統(tǒng)中的任何進(jìn)程所共享。在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的物理塊中。實(shí)現(xiàn)原理示意圖用戶程序0 頁(yè)1 頁(yè)2 頁(yè)3 頁(yè)4 頁(yè)5 頁(yè)n 頁(yè)內(nèi)存012345678910指定進(jìn)程頁(yè)到空閑物理塊01234567891011121314內(nèi)存15個(gè)可用幀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)程頁(yè)到空閑物理塊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頁(yè)面和物理塊n頁(yè)面：進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)，并為各頁(yè)加以編號(hào)，從0開(kāi)始，如第0頁(yè)、第1頁(yè)等。n物理塊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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