第四章存儲(chǔ)管理

操作系統(tǒng)教程課件第1頁(yè)第四章存儲(chǔ)管理4.1存儲(chǔ)管理概述4.2程序的裝入與鏈接4.3連續(xù)存儲(chǔ)空間管理4.4頁(yè)式存儲(chǔ)管理4.5段式存儲(chǔ)管理4.6段頁(yè)式存儲(chǔ)管理4.7虛擬存儲(chǔ)管理方式本章小結(jié)4.1存儲(chǔ)管理概述存儲(chǔ)器用于存放程序(指令)、操作數(shù)(數(shù)據(jù))以及操作結(jié)果。計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器一般分為主存儲(chǔ)器和輔助存儲(chǔ)器兩大類。CPU可以直接訪問(wèn)主存儲(chǔ)器中的指令和數(shù)據(jù)，但不能直接訪問(wèn)輔助存儲(chǔ)器。在I/O控制系統(tǒng)管理下，輔助存儲(chǔ)器與主存儲(chǔ)器之間可以進(jìn)行信息傳遞。主存儲(chǔ)器簡(jiǎn)稱主存，或稱為內(nèi)存。主存可分為系統(tǒng)區(qū)和用戶區(qū)兩個(gè)區(qū)域。存儲(chǔ)管理是對(duì)主存中的用戶區(qū)進(jìn)行管理，其目的是盡可能地方便用戶和提高主存空間的利用率，使主存在成本、速度和規(guī)模之間獲得較好的權(quán)衡。操作系統(tǒng)教程課件第2頁(yè)4.1.1存儲(chǔ)器的存儲(chǔ)結(jié)構(gòu)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)部件通常是采用層次結(jié)構(gòu)來(lái)組織，以便在成本、速度和規(guī)模等諸因素中獲得較好的性能價(jià)格比。現(xiàn)代通用計(jì)算機(jī)，存儲(chǔ)層次至少應(yīng)具有三級(jí)：最高層為CPU寄存器，中間層為主存，最底層為輔存。在較高檔的計(jì)算機(jī)中，還可以根據(jù)具體的功能分工細(xì)劃為寄存器、高速緩存、主存儲(chǔ)器、磁盤(pán)緩存、磁盤(pán)、可移動(dòng)存儲(chǔ)介質(zhì)等組成操作系統(tǒng)教程課件第3頁(yè)4.1.1存儲(chǔ)器的存儲(chǔ)結(jié)構(gòu)如圖4-1所示，在存儲(chǔ)層次中越往上，存儲(chǔ)介質(zhì)的訪問(wèn)速度越快，價(jià)格也越高，相對(duì)存儲(chǔ)容量也較小。操作系統(tǒng)教程課件第4頁(yè)其中，寄存器、高速緩存、主存儲(chǔ)器和磁盤(pán)緩存均屬于操作系統(tǒng)存儲(chǔ)管理的管轄范疇，掉電后它們存儲(chǔ)的信息不再存在。固定磁盤(pán)和可移動(dòng)存儲(chǔ)介質(zhì)屬于設(shè)備管理的管轄范疇，它們存儲(chǔ)的信息將被長(zhǎng)期保存。而磁盤(pán)緩存本身并不是一種實(shí)際存在的存儲(chǔ)介質(zhì)，它依托于固定磁盤(pán)，提供對(duì)主存儲(chǔ)器存儲(chǔ)空間的擴(kuò)充。圖4-1計(jì)算機(jī)系統(tǒng)存儲(chǔ)器層次4.1.2存儲(chǔ)管理的功能1．主存空間的分配和去配2．實(shí)現(xiàn)地址轉(zhuǎn)換3．主存空間的共享和保護(hù)4．主存空間的擴(kuò)充

操作系統(tǒng)教程課件第5頁(yè)4.2.1物理地址和邏輯地址主存儲(chǔ)器的存儲(chǔ)單元以字節(jié)（每個(gè)字節(jié)為8個(gè)二進(jìn)制位）為單位編址，每個(gè)存儲(chǔ)單元都有一個(gè)地址與其相對(duì)應(yīng)。假定主存儲(chǔ)器的容量為n，則該主存就有n個(gè)字節(jié)的存儲(chǔ)空間，其地址編號(hào)為0，1，2…，n－1。這些地址稱為主存儲(chǔ)器的“物理地址”（絕對(duì)地址），由物理地址所對(duì)應(yīng)的主存空間稱“物理地址空間”。在多道程序設(shè)計(jì)系統(tǒng)中，主存中同時(shí)存放了多個(gè)用戶作業(yè)。每次調(diào)入運(yùn)行時(shí)，操作系統(tǒng)將根據(jù)主存的使用情況為用戶分配主存空間。為了方便程序的編制，每個(gè)用戶可以認(rèn)為自己作業(yè)的程序和數(shù)據(jù)存放在一組以“0”地址開(kāi)始的連續(xù)空間中。用戶程序中所使用的地址稱為“邏輯地址”，由邏輯地址對(duì)應(yīng)的存儲(chǔ)空間稱為“邏輯地址空間”。操作系統(tǒng)教程課件第6頁(yè)4.2.2程序的裝入將一個(gè)用戶的源程序裝入主存中并執(zhí)行，通常需要經(jīng)過(guò)以下幾個(gè)步驟：首先編譯，由編譯程序(Compiler)將用戶源代碼編譯成若干個(gè)目標(biāo)模塊（ObjectModule）；然后鏈接，由鏈接程序（Linker）將編譯后形成的一組目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊(LoadModule)；最后裝入，由裝入程序(Loader)將裝入模塊裝入主存。如圖4-2所示。操作系統(tǒng)教程課件第7頁(yè)4.2.2程序的裝入將一個(gè)裝入模塊裝入主存，可以有絕對(duì)裝入方式、靜態(tài)重定位裝入方式和動(dòng)態(tài)重定位裝入方式。1．絕對(duì)裝入方式如果在編譯時(shí)知道程序駐留在主存的具體位置，則編譯程序?qū)a(chǎn)生物理地址的目標(biāo)代碼。絕對(duì)裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入主存。模塊裝入后，由于程序中的邏輯地址與實(shí)際主存的地址完全相同，所以不需要對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。絕對(duì)裝入方式只能將目標(biāo)模塊裝入到主存儲(chǔ)器事先指定的固定位置，它只適用于單道程序環(huán)境。操作系統(tǒng)教程課件第8頁(yè)4.2.2程序的裝入

2．靜態(tài)重定位裝入方式在裝入作業(yè)時(shí)，把該作業(yè)中的指令地址和數(shù)據(jù)地址一次性全部轉(zhuǎn)換成物理地址，這樣在作業(yè)執(zhí)行過(guò)程中無(wú)需再進(jìn)行地址轉(zhuǎn)換工作，這種地址轉(zhuǎn)換方式稱“靜態(tài)重定位”。而這種作業(yè)裝入的方式稱為“靜態(tài)重定位裝入方式”。如圖4-3所示靜態(tài)重定位裝入的過(guò)程。操作系統(tǒng)教程課件第9頁(yè)4.2.2程序的裝入

3．動(dòng)態(tài)重定位裝入方式在裝入作業(yè)時(shí)，裝入程序直接把作業(yè)裝入到所分配的主存區(qū)域中。在作業(yè)執(zhí)行過(guò)程中，隨著每條指令或數(shù)據(jù)的訪問(wèn)由硬件地址轉(zhuǎn)換機(jī)制自動(dòng)地將指令中的邏輯地址轉(zhuǎn)換成對(duì)應(yīng)的物理地址。這種地址轉(zhuǎn)換的方式是在作業(yè)執(zhí)行過(guò)程中動(dòng)態(tài)完成的，故稱為“動(dòng)態(tài)重定位”。而這種作業(yè)裝入的方式稱為“動(dòng)態(tài)重定位裝入方式”。如圖4-4所示動(dòng)態(tài)重定位裝入過(guò)程。

操作系統(tǒng)教程課件第10頁(yè)4.2.2程序的裝入操作系統(tǒng)教程課件第11頁(yè)圖4-4動(dòng)態(tài)重定位4.2.2程序的裝入

采用動(dòng)態(tài)重定位時(shí)，由于裝入主存的作業(yè)仍保持邏輯地址，所以必要時(shí)可改變作業(yè)在主存儲(chǔ)器中的存放區(qū)域。作業(yè)在主存中被移動(dòng)位置后，只需要把新區(qū)域的起始地址代替原來(lái)基址寄存器中的地址，這樣，作業(yè)執(zhí)行時(shí)，硬件地址轉(zhuǎn)換機(jī)制將按新區(qū)域的起始地址與邏輯地址相加，轉(zhuǎn)換成新的物理地址，使作業(yè)仍可正確執(zhí)行。

若作業(yè)執(zhí)行時(shí)被改變了存儲(chǔ)區(qū)仍能正確運(yùn)行，則稱程序是可浮動(dòng)的。采用動(dòng)態(tài)重定位的系統(tǒng)支持“程序浮動(dòng)”。而采用靜態(tài)重定位時(shí)，由于被裝入主存儲(chǔ)器中的作業(yè)信息都已轉(zhuǎn)換為物理地址，作業(yè)執(zhí)行過(guò)程中，不再進(jìn)行地址的轉(zhuǎn)換，故作業(yè)執(zhí)行過(guò)程中是不能改變存放位置的，即采用靜態(tài)重定位的系統(tǒng)不支持“程序浮動(dòng)”。操作系統(tǒng)教程課件第12頁(yè)4.2.3程序的鏈接源程序經(jīng)過(guò)編譯后，得到一組目標(biāo)模塊，再通過(guò)鏈接程序?qū)⑦@組目標(biāo)模塊鏈接，形成一個(gè)完整的裝入模塊。程序鏈接示意如圖4-5所示。操作系統(tǒng)教程課件第13頁(yè)4.2.3程序的鏈接

根據(jù)鏈接時(shí)間不同，程序的鏈接可分成如下三種方式：1．靜態(tài)鏈接。在程序運(yùn)行之前，首先將各個(gè)目標(biāo)模塊以及所需要的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝入模塊，又稱為可執(zhí)行文件，運(yùn)行時(shí)可直接將它裝入主存。經(jīng)過(guò)編譯后得到的目標(biāo)模塊，每個(gè)模塊的起始地址都為“0”，模塊中的地址都是相對(duì)于起始地址計(jì)算的，在鏈接成一個(gè)裝入模塊后，程序中被調(diào)用模塊的起始地址不再是“0”，此時(shí)須修改被調(diào)用模塊的邏輯地址，同時(shí)每個(gè)模塊中使用的外部調(diào)用符號(hào)也相應(yīng)轉(zhuǎn)變?yōu)檫壿嫷刂?。如圖3-5（b）中，B和C模塊的起始地址分別變更為L(zhǎng)和L+M，而原B模塊中的所有邏輯地址都要加上L，原C模塊中的所有邏輯地址都要加上L+M。

操作系統(tǒng)教程課件第14頁(yè)4.2.3程序的鏈接

2．裝入時(shí)動(dòng)態(tài)鏈接。用戶源程序經(jīng)編譯后得到的一組目標(biāo)模塊，在裝入主存時(shí)，采用邊裝入邊鏈接的方式，即在裝入一個(gè)目標(biāo)模塊時(shí)，若需要調(diào)用一個(gè)模塊，則找出該模塊，并將它裝入主存，并修改目標(biāo)模塊中的邏輯地址。由于采用動(dòng)態(tài)鏈接的各個(gè)目標(biāo)模塊是分開(kāi)存放的，操作系統(tǒng)可以方便地將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，所以采用動(dòng)態(tài)鏈接方式，可以容易地實(shí)現(xiàn)對(duì)目標(biāo)模塊的修改和更新，同時(shí)便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。操作系統(tǒng)教程課件第15頁(yè)4.2.3程序的鏈接

3．運(yùn)行時(shí)動(dòng)態(tài)鏈接。在很多情況下，由于應(yīng)用程序每次運(yùn)行時(shí)的條件不同，需要調(diào)用的模塊有可能是不相同的。如果將所有目標(biāo)模塊裝入主存，并鏈接在一起，得到一個(gè)非常大的裝入模塊，其中可能存在某些目標(biāo)模塊根本就沒(méi)有條件運(yùn)行，這樣會(huì)引起程序裝入時(shí)間上和主存空間上的浪費(fèi)。運(yùn)行時(shí)動(dòng)態(tài)鏈接是指在程序執(zhí)行過(guò)程中當(dāng)需要該目標(biāo)模塊時(shí)，才把該模塊裝入主存，并進(jìn)行鏈接。這樣不僅可以加快程序裝入的速度，而且可以節(jié)省大量的主存空間。連續(xù)存儲(chǔ)空間管理，是指把主存儲(chǔ)器中的用戶區(qū)作為一個(gè)連續(xù)區(qū)域或者分成若干個(gè)連續(xù)區(qū)域進(jìn)行管理。連續(xù)存儲(chǔ)管理方式可分為單一連續(xù)分配、固定分區(qū)分配以及可變分區(qū)分配等方式。操作系統(tǒng)教程課件第16頁(yè)4.3.1單一連續(xù)存儲(chǔ)管理

單一連續(xù)存儲(chǔ)管理是一種最簡(jiǎn)單的存儲(chǔ)管理方式。在單一連續(xù)存儲(chǔ)管理方式下，操作系統(tǒng)占用一部分主存空間，其余的主存空間作為一個(gè)連續(xù)分區(qū)全部分配給一個(gè)作業(yè)使用，即在任何時(shí)刻主存儲(chǔ)器中最多只存有一個(gè)作業(yè)。這種存儲(chǔ)管理方式適合于單用戶、單任務(wù)的操作系統(tǒng)，在個(gè)人計(jì)算機(jī)和專用計(jì)算機(jī)系統(tǒng)中可采用。圖4-6所示為單一連續(xù)存儲(chǔ)管理的示意圖。操作系統(tǒng)教程課件第17頁(yè)4.3.1單一連續(xù)存儲(chǔ)管理

單一連續(xù)存儲(chǔ)管理每次只允許一個(gè)作業(yè)裝入主存儲(chǔ)器，因此可以不必考慮作業(yè)在主存中的移動(dòng)問(wèn)題，所以當(dāng)作業(yè)被裝入主存時(shí)，系統(tǒng)一般采用靜態(tài)重定位方式進(jìn)行地址轉(zhuǎn)換，當(dāng)然也可以采用動(dòng)態(tài)重定位方式。單一連續(xù)存儲(chǔ)管理方式下的存儲(chǔ)保護(hù)比較簡(jiǎn)單，即判斷物理地址≥界限地址，并且物理地址≤主存最大地址，若條件成立，則可執(zhí)行，否則有地址錯(cuò)誤，形成“地址越界”程序性中斷事件。當(dāng)采用靜態(tài)重定位裝入方式時(shí)，由裝入程序檢查其物理地址是否超過(guò)界限地址，若是，則可以裝入；否則，將產(chǎn)生地址錯(cuò)誤，程序不能裝入。這樣，一個(gè)被裝入的作業(yè)，總能保證在用戶區(qū)中執(zhí)行，避免破壞系統(tǒng)區(qū)中的信息，達(dá)到“存儲(chǔ)保護(hù)”的目的。操作系統(tǒng)教程課件第18頁(yè)4.3.1單一連續(xù)存儲(chǔ)管理單一連續(xù)存儲(chǔ)管理方式適用于單道程序系統(tǒng)，在20世紀(jì)70年代，由于小型計(jì)算機(jī)和微型計(jì)算機(jī)的主存容量有限，這種管理方式曾得到了廣泛應(yīng)用，例如IBM7094FORTRAN監(jiān)督系統(tǒng)、CP/M系統(tǒng)、DJS0520系統(tǒng)等均采用了單一連續(xù)存儲(chǔ)管理方式，但采用這種管理方式存在幾個(gè)主要缺點(diǎn)：①CPU利用率比較低。當(dāng)正在執(zhí)行的作業(yè)出現(xiàn)某個(gè)等待事件時(shí)，CPU便處于空閑狀態(tài)。②存儲(chǔ)器得不到充分利用。不管用戶作業(yè)的程序和數(shù)據(jù)量的多少，都是一個(gè)作業(yè)獨(dú)占主存的用戶區(qū)。③計(jì)算機(jī)的外圍設(shè)備利用率不高。操作系統(tǒng)教程課件第19頁(yè)4.3.2固定分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第20頁(yè)固定分區(qū)存儲(chǔ)管理是預(yù)先把主存儲(chǔ)器中的用戶區(qū)分割成若干個(gè)連續(xù)區(qū)域，每一個(gè)連續(xù)區(qū)域稱為一個(gè)分區(qū)，每個(gè)分區(qū)的大小可以相同，也可以不同。但是一旦分割完成后，主存儲(chǔ)器中分區(qū)的個(gè)數(shù)固定不變，每個(gè)分區(qū)的大小固定不變。每個(gè)分區(qū)可以裝入一個(gè)作業(yè)，不允許一個(gè)作業(yè)跨分區(qū)存儲(chǔ)，也不允許多個(gè)作業(yè)同時(shí)存放在同一個(gè)分區(qū)中。因此，固定分區(qū)存儲(chǔ)管理適合多道程序設(shè)計(jì)系統(tǒng)。圖4-7所示為固定分區(qū)存儲(chǔ)管理方式的示意圖。

4.3.2固定分區(qū)存儲(chǔ)管理

1．空間的分配和去配為了管理各分區(qū)的分配和使用情況，系統(tǒng)需要設(shè)置一張“主存分配表”，以說(shuō)明各分區(qū)的分配情況。一個(gè)系統(tǒng)中分區(qū)分配表的長(zhǎng)度固定，由主存儲(chǔ)器中分區(qū)的個(gè)數(shù)所決定。主存分配表中記錄了各個(gè)分區(qū)的起始地址和長(zhǎng)度，并為每個(gè)分區(qū)設(shè)一個(gè)狀態(tài)標(biāo)志位，當(dāng)狀態(tài)標(biāo)志位為“0”時(shí)，表示該分區(qū)是空閑分區(qū)，當(dāng)標(biāo)志位為非“0”時(shí)，表示該分區(qū)已被占用。圖4-8表示主存儲(chǔ)器被劃分成四個(gè)分區(qū)，每個(gè)分區(qū)的大小并不相同，其中分區(qū)1、分區(qū)3和分區(qū)4分別被作業(yè)名為JOBA、JOBB和JOBC的作業(yè)所占用，分區(qū)2為空閑分區(qū)。

操作系統(tǒng)教程課件第21頁(yè)4.3.2固定分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第22頁(yè)圖4-8四個(gè)分區(qū)的分區(qū)分配表4.3.2固定分區(qū)存儲(chǔ)管理

當(dāng)作業(yè)隊(duì)列中有作業(yè)要求裝入主存時(shí)，存儲(chǔ)管理可采用“順序分配算法”進(jìn)行主存空間的分配。分配時(shí)順序查找主存分配表，選擇標(biāo)志位為“0”的分區(qū)，將作業(yè)的地址空間大小與該分區(qū)長(zhǎng)度進(jìn)行比較，如果能容納該作業(yè)，則將此分區(qū)分配給該作業(yè)，且在此分區(qū)的占用標(biāo)志欄中填入該作業(yè)名。如果作業(yè)的地址空間大于此空閑分區(qū)的長(zhǎng)度，則重復(fù)上述過(guò)程繼續(xù)查找，查找空閑區(qū)長(zhǎng)度大于等于該作業(yè)的地址空間大小且標(biāo)志位為“0”的空閑分區(qū)，若有，則分配，否則該作業(yè)暫時(shí)不能裝入主存儲(chǔ)器。圖4-9所示給出固定分區(qū)順序分配算法的流程。裝入后的作業(yè)在執(zhí)行結(jié)束后必須歸還所占用的分區(qū)。存儲(chǔ)管理根據(jù)作業(yè)名查找主存分配表，找到該作業(yè)所占用的分區(qū)，將該分區(qū)的狀態(tài)標(biāo)志位重新設(shè)置為“0”，表示該分區(qū)現(xiàn)在是空閑區(qū)，可以裝入新的作業(yè)。

操作系統(tǒng)教程課件第23頁(yè)4.3.2固定分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第24頁(yè)圖4-9固定分區(qū)順序分配算法流程4.3.2固定分區(qū)存儲(chǔ)管理

2．地址轉(zhuǎn)換和存儲(chǔ)保護(hù)固定分區(qū)存儲(chǔ)管理下，作業(yè)在執(zhí)行過(guò)程中是不會(huì)被改變存儲(chǔ)區(qū)域的，因此可以采用靜態(tài)重定位裝入方式裝入作業(yè)。由裝入程序把作業(yè)中的邏輯地址與分區(qū)的下限地址相加，得到對(duì)應(yīng)的物理地址。當(dāng)一個(gè)已經(jīng)被裝入主存的作業(yè)占有處理器運(yùn)行時(shí)，進(jìn)程調(diào)度程序?qū)⒃撟鳂I(yè)所在分區(qū)的下限地址和上限地址分別存儲(chǔ)在處理器的“下限寄存器”和“上限寄存器”中。處理器執(zhí)行該作業(yè)指令時(shí)必須判斷：下限地址≤物理地址<上限地址如果物理地址在上、下限地址范圍內(nèi)，則可按物理地址訪問(wèn)主存儲(chǔ)器；如果條件不成立，則產(chǎn)生“地址越界”的中斷事件，達(dá)到存儲(chǔ)保護(hù)的目的。作業(yè)運(yùn)行結(jié)束時(shí)，調(diào)度程序選擇另一個(gè)可運(yùn)行的作業(yè)，同時(shí)修改下限寄存器和上限寄存器的內(nèi)容，以保證處理器能控制該作業(yè)的正確執(zhí)行。

操作系統(tǒng)教程課件第25頁(yè)4.3.2固定分區(qū)存儲(chǔ)管理3．主存空間的利用率固定分區(qū)存儲(chǔ)管理方式總是為作業(yè)分配一個(gè)不小于作業(yè)地址空間的分區(qū)，因此在分區(qū)中產(chǎn)生一部分空閑區(qū)域，影響了主存空間的利用率。為了提高主存空間的利用率采用如下幾種方法：（1）根據(jù)經(jīng)常出現(xiàn)的作業(yè)的大小和頻率劃分分區(qū)。（2）劃分分區(qū)時(shí)按分區(qū)大小順序排列。（3）按作業(yè)對(duì)主存空間的需求量排成多個(gè)作業(yè)隊(duì)列，規(guī)定每個(gè)作業(yè)隊(duì)列中的各作業(yè)只能依次裝入對(duì)應(yīng)的分區(qū)中；不同作業(yè)隊(duì)列中的作業(yè)分別依次裝入不同的分區(qū)中，不同的分區(qū)中可同時(shí)裝入作業(yè)；某作業(yè)隊(duì)列為“空”時(shí)，該作業(yè)隊(duì)列對(duì)應(yīng)的分區(qū)也不能用來(lái)裝其他作業(yè)隊(duì)列中的作業(yè)。操作系統(tǒng)教程課件第26頁(yè)4.3.2固定分區(qū)存儲(chǔ)管理圖4-10為多個(gè)作業(yè)隊(duì)列的固定分區(qū)法。操作系統(tǒng)教程課件第27頁(yè)

采用多個(gè)作業(yè)隊(duì)列的固定分區(qū)法可以有效地防止小作業(yè)占用大分區(qū)，從而減少了閑置的主存空間量。但是如果分區(qū)劃分不合適，則會(huì)造成某個(gè)作業(yè)隊(duì)列經(jīng)常為空隊(duì)列，使對(duì)應(yīng)分區(qū)經(jīng)常無(wú)作業(yè)被裝入，反而使分區(qū)的利用率不高。所以采用多個(gè)作業(yè)隊(duì)列的固定分區(qū)法時(shí)，可結(jié)合作業(yè)的大小和出現(xiàn)的頻率劃分分區(qū)，以達(dá)到更好的空間利用率。

4.3.3可變分區(qū)存儲(chǔ)管理

可變分區(qū)存儲(chǔ)管理并不是預(yù)先將主存儲(chǔ)器中的用戶區(qū)域劃分成若干個(gè)固定分區(qū)，而是在作業(yè)要求裝入主存時(shí)，根據(jù)作業(yè)需要的地址空間的大小和當(dāng)時(shí)主存空間的實(shí)際使用情況決定是否為該作業(yè)分配一個(gè)分區(qū)。如果有足夠的連續(xù)空間，則按需要分割一部分空間分區(qū)給該作業(yè)；否則令其等待主存空間。所以，在可變分區(qū)存儲(chǔ)管理中，主存儲(chǔ)器中分區(qū)的大小是可變的，根據(jù)作業(yè)的實(shí)際需求進(jìn)行分區(qū)的劃分；主存中分區(qū)的個(gè)數(shù)是可變的，隨著裝入主存的作業(yè)數(shù)量而變化；主存中的空閑分區(qū)個(gè)數(shù)也隨著作業(yè)的裝入與撤離而發(fā)生變化。圖4-11是可變分區(qū)存儲(chǔ)管理方式的存儲(chǔ)空間分配示意圖。操作系統(tǒng)教程課件第28頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第29頁(yè)圖4-11可變分區(qū)存儲(chǔ)分配與回收示意圖4.3.3可變分區(qū)存儲(chǔ)管理

1．空間的分配和去配系統(tǒng)初始時(shí)，把主存中整個(gè)用戶區(qū)看作一個(gè)大的空閑分區(qū)。當(dāng)作業(yè)要求裝入主存時(shí)，系統(tǒng)根據(jù)作業(yè)對(duì)主存空間的實(shí)際需求量進(jìn)行分配。圖4-11（a）給出了作業(yè)被裝入時(shí)主存空間分配的情況。裝入主存儲(chǔ)器中的作業(yè)執(zhí)行結(jié)束后，它所占用的分區(qū)被收回，成為一個(gè)新的空閑區(qū)，可以用來(lái)裝入新的作業(yè)。隨著作業(yè)不斷的裝入和作業(yè)執(zhí)行完后的撤離，主存儲(chǔ)區(qū)被分成若干分區(qū)，其中有的分區(qū)被作業(yè)占用，有的分區(qū)空閑。圖4-11（b）給出了作業(yè)被裝入、執(zhí)行結(jié)束后撤離的主存空間分配情況。4.3.3可變分區(qū)存儲(chǔ)管理1.可變分區(qū)數(shù)據(jù)結(jié)構(gòu)采用可變分區(qū)存儲(chǔ)管理方式管理諸存儲(chǔ)空間時(shí)，主存中已占用分區(qū)和空閑區(qū)的數(shù)目和大小都是可變的。為了實(shí)現(xiàn)可變分區(qū)存儲(chǔ)管理，系統(tǒng)必須設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為系統(tǒng)空間分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式。（1）分區(qū)表。系統(tǒng)設(shè)置“空閑分區(qū)表”和“已分配分區(qū)表”，用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為系統(tǒng)空間分配提供依據(jù)。已分配分區(qū)表記錄已裝入的作業(yè)在主存空間中占用分區(qū)的始址和長(zhǎng)度，用標(biāo)志位指出占用該分區(qū)的作業(yè)名?？臻e分區(qū)表記錄主存中可供分配的空閑分區(qū)的始址和長(zhǎng)度，用標(biāo)志位指出該分區(qū)是未分配的空閑分區(qū)。操作系統(tǒng)教程課件第31頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

圖4-12為可變分區(qū)存儲(chǔ)管理方式的主存分配表。系統(tǒng)按一定的規(guī)則組織主存分配表，當(dāng)作業(yè)要求裝入時(shí)，從空閑分區(qū)表查找一個(gè)長(zhǎng)度大于作業(yè)要求的空閑分區(qū)。操作系統(tǒng)教程課件第32頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

（2）分區(qū)鏈。為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接前一個(gè)分區(qū)的前向指針；在分區(qū)尾部則設(shè)置一后向指針，通過(guò)前、后向鏈接指針，可以將所有的空閑分區(qū)聯(lián)結(jié)成一個(gè)雙向鏈。為了檢索的方便，在分區(qū)尾部重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目。如圖4-13所示。操作系統(tǒng)教程課件第33頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

2.可變分區(qū)分配算法將一個(gè)作業(yè)裝入主存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個(gè)分區(qū)分配給該作業(yè)?？勺兎謪^(qū)存儲(chǔ)管理常用的空間分配算法有：“最先適應(yīng)”分配算法、“最優(yōu)適應(yīng)”分配算法和“最壞適應(yīng)”分配算法。以下以空閑分區(qū)表為例說(shuō)明各種算法。操作系統(tǒng)教程課件第34頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

（1）最先適應(yīng)分配算法最先適應(yīng)分配算法在主存空間分配時(shí)，總是順序查找空閑分區(qū)表，選擇第一個(gè)滿足作業(yè)地址空間要求的空閑分區(qū)進(jìn)行分割，一部分分配給作業(yè)，而剩余部分仍為空閑分區(qū)。最先適應(yīng)分配算法實(shí)現(xiàn)簡(jiǎn)單，但是經(jīng)過(guò)若干次作業(yè)的裝入與撤離后，有可能把較大的主存空間分割成若干個(gè)小的、不連續(xù)的新空閑分區(qū)，這些空閑分區(qū)的長(zhǎng)度可能比較小，不能滿足主存再次分配的需要，從而使主存空間的利用率大大降低，這些空閑分區(qū)稱為“碎片”。操作系統(tǒng)教程課件第35頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

（2）最優(yōu)適應(yīng)分配算法 最優(yōu)適應(yīng)分配算法總是選擇一個(gè)滿足作業(yè)地址空間要求的最小空閑分區(qū)進(jìn)行分配，這樣每次分配后總能保留下較大的分區(qū)，使裝入大作業(yè)時(shí)比較容易獲得滿足。在實(shí)現(xiàn)過(guò)程中，空閑分區(qū)按其長(zhǎng)度以遞增順序登記在空閑分區(qū)表中。這樣，系統(tǒng)分配時(shí)順序查找空閑分區(qū)表，找到的第一個(gè)滿足作業(yè)空間要求的空閑分區(qū)一定是能夠滿足該作業(yè)要求的所有分區(qū)中的最小一個(gè)分區(qū)。采用最優(yōu)適應(yīng)分配算法，每次分配后分割的剩余空間總是最小的，這樣形成的“碎片”非?！傲闵ⅰ保y以再次分配使用，從而影響了主存空間的利用率。操作系統(tǒng)教程課件第36頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理（3）最壞適應(yīng)分配算法最壞適應(yīng)分配算法與最優(yōu)適應(yīng)分配算法相反，總是選擇一個(gè)滿足作業(yè)地址空間要求的最大空閑分區(qū)進(jìn)行分割，按作業(yè)需要的空間大小進(jìn)行分配給作業(yè)使用后，剩余部分的空間不致于太小，仍然可以供系統(tǒng)再次分配使用。這種分配算法對(duì)中小型作業(yè)是有利的。實(shí)現(xiàn)最壞適應(yīng)分配算法時(shí)，空閑分區(qū)按其長(zhǎng)度以遞減順序登記在空閑分區(qū)表中。系統(tǒng)分配時(shí)順序查找空閑分區(qū)表，表中的第一個(gè)登記項(xiàng)即對(duì)應(yīng)著當(dāng)前主存的最大空閑分區(qū)。同樣，當(dāng)作業(yè)歸還主存空間時(shí)，則需要按分區(qū)的大小按遞減順序登記到空閑分區(qū)表的適當(dāng)位置。操作系統(tǒng)教程課件第37頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第38頁(yè)圖4-14可變分區(qū)分配算法示例4.3.3可變分區(qū)存儲(chǔ)管理裝入的作業(yè)執(zhí)行結(jié)束后，它所占據(jù)的分區(qū)將被回收，回收后的空閑分區(qū)登記在空閑分區(qū)表中，用來(lái)裝入新的作業(yè)?；厥湛臻g時(shí)應(yīng)檢查是否存在與回收區(qū)相鄰的空閑分區(qū)，如果有，則將其合并成為一個(gè)新的空閑分區(qū)進(jìn)行登記管理。一個(gè)回收區(qū)可能存在上鄰空閑分區(qū)，也可能存在下鄰空閑分區(qū)，或既存在上鄰又存在下鄰空閑分區(qū)，或既無(wú)上鄰又無(wú)下鄰空閑分區(qū)，如圖4-15所示。假定作業(yè)歸還的分區(qū)始址為S，長(zhǎng)度為L(zhǎng)。操作系統(tǒng)教程課件第39頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理操作系統(tǒng)教程課件第40頁(yè)圖4-15主存回收示意圖4.3.3可變分區(qū)存儲(chǔ)管理圖4-16給出了合并下鄰/上鄰空閑分區(qū)的回收算法流程。

4.3.3可變分區(qū)存儲(chǔ)管理

2．地址轉(zhuǎn)換和存儲(chǔ)保護(hù)采用可變分區(qū)存儲(chǔ)管理方式，一般均采用動(dòng)態(tài)重定位方式裝入作業(yè)。為使地址的轉(zhuǎn)換不影響到指令的執(zhí)行速度，必須有硬件地址轉(zhuǎn)換機(jī)構(gòu)的支持。硬件地址轉(zhuǎn)換機(jī)構(gòu)包括兩個(gè)專用控制寄存器：基址寄存器和限長(zhǎng)寄存器，以及一些加法、比較線路等?；芳拇嫫饔脕?lái)存放作業(yè)所占分區(qū)的起始地址，限長(zhǎng)寄存器用來(lái)存放作業(yè)所占分區(qū)長(zhǎng)度。

4.3.3可變分區(qū)存儲(chǔ)管理正在運(yùn)行的作業(yè)所占分區(qū)的起始地址和長(zhǎng)度被送入基址寄存器和限長(zhǎng)寄存器中。執(zhí)行過(guò)程中，處理器每執(zhí)行一條指令都要將該指令的邏輯地址與限長(zhǎng)寄存器中的值進(jìn)行比較，當(dāng)邏輯地址小于限長(zhǎng)值時(shí)，則把邏輯地址與基址寄存器的值相加就可得到對(duì)應(yīng)的物理地址。當(dāng)邏輯地址大于限長(zhǎng)寄存器中的限長(zhǎng)值時(shí)，表示欲訪問(wèn)的地址超出了所分配的分區(qū)范圍，這時(shí)形成一個(gè)“地址越界”的程序性中斷事件，達(dá)到存儲(chǔ)保護(hù)的目的。圖4-17示出了可變分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換示例。操作系統(tǒng)教程課件第43頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理

3移動(dòng)技術(shù)采用可變分區(qū)存儲(chǔ)管理主存時(shí)，可采用移動(dòng)技術(shù)使分散的空閑分區(qū)集中起來(lái)以容納新的作業(yè)，如圖4-18所示。

移動(dòng)技術(shù)為作業(yè)執(zhí)行過(guò)程中擴(kuò)充主存空間提供方便，一道作業(yè)在執(zhí)行中要求增加主存量時(shí)，只要適當(dāng)移動(dòng)鄰近的作業(yè)就可增加它所占的分區(qū)長(zhǎng)度。移動(dòng)可以集中分散的空閑分區(qū)，提高主存空間的利用率，移動(dòng)也為作業(yè)動(dòng)態(tài)擴(kuò)充主存空間提供了方便。但是，采用移動(dòng)技術(shù)時(shí)必須注意：（1）移動(dòng)會(huì)增加系統(tǒng)開(kāi)銷。（2）移動(dòng)是有條件的。操作系統(tǒng)教程課件第45頁(yè)4.3.3可變分區(qū)存儲(chǔ)管理采用移動(dòng)技術(shù)時(shí)應(yīng)該盡量減少移動(dòng)的作業(yè)數(shù)和信息量，以降低系統(tǒng)的開(kāi)銷、提高系統(tǒng)的效率。圖4-19給出了兩種作業(yè)裝入主存的方式。操作系統(tǒng)教程課件第46頁(yè)4.3.4覆蓋與交換技術(shù)覆蓋技術(shù)和交換技術(shù)是在多道環(huán)境下用來(lái)擴(kuò)充主存的兩種方法。這兩種技術(shù)都是用來(lái)解決主存容量不足及有效利用主存的方法。覆蓋技術(shù)主要用于早期的操作系統(tǒng)中，而交換技術(shù)在現(xiàn)代操作系統(tǒng)中仍有較強(qiáng)的生命力。單一連續(xù)存儲(chǔ)管理和分區(qū)存儲(chǔ)管理對(duì)作業(yè)的大小都有嚴(yán)格的限制，當(dāng)作業(yè)要求運(yùn)行時(shí)，系統(tǒng)將作業(yè)的全部信息一次裝入主存，并一直駐留在主存直至運(yùn)行結(jié)束。當(dāng)作業(yè)的大小大于主存可用空間時(shí)，該作業(yè)就無(wú)法運(yùn)行，這就限制了計(jì)算機(jī)系統(tǒng)上開(kāi)發(fā)較大程序的可能。覆蓋和交換技術(shù)是解決大作業(yè)與小主存矛盾的兩種存儲(chǔ)管理技術(shù)，他們實(shí)質(zhì)上是對(duì)主存進(jìn)行了邏輯擴(kuò)充。操作系統(tǒng)教程課件第47頁(yè)4.3.4覆蓋與交換技術(shù)覆蓋技術(shù)的基本思想是一個(gè)程序不需要把所有的指令和數(shù)據(jù)都裝入主存?？梢园殉绦騽潪槿舾晒δ苌舷鄬?duì)獨(dú)立的程序段，讓那些不會(huì)同時(shí)執(zhí)行的程序段共享一塊主存。這樣使用戶看起來(lái)好像主存擴(kuò)大了，從而達(dá)到了主存擴(kuò)充的目的。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐主存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中（覆蓋文件），在需要用到時(shí)才裝入到主存；不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到主存，從而可以相互覆蓋(即不同時(shí)用的模塊可共用一個(gè)分區(qū))。把可以相互覆蓋的程序段叫做覆蓋，可共享的主存區(qū)叫做覆蓋區(qū)。操作系統(tǒng)教程課件第48頁(yè)4.3.4覆蓋與交換技術(shù)操作系統(tǒng)教程課件第49頁(yè)圖4-20覆蓋技術(shù)示意圖4.3.4覆蓋與交換技術(shù)為了實(shí)現(xiàn)覆蓋管理，系統(tǒng)必須提供相應(yīng)的覆蓋管理控制程序。當(dāng)作業(yè)裝入運(yùn)行時(shí)，由系統(tǒng)根據(jù)用戶提供的覆蓋結(jié)構(gòu)進(jìn)行覆蓋處理。當(dāng)程序中引用當(dāng)前尚未裝入覆蓋區(qū)的覆蓋中的例程時(shí)，則調(diào)用覆蓋管理控制程序，請(qǐng)求將所需的覆蓋裝入覆蓋區(qū)中，系統(tǒng)響應(yīng)請(qǐng)求，并自動(dòng)將所需覆蓋裝入主存覆蓋區(qū)中。覆蓋技術(shù)打破了必須將一個(gè)作業(yè)的全部信息裝入主存后才能運(yùn)行的限制。在一定程度上解決了小主存運(yùn)行大作業(yè)的矛盾。但是，采用覆蓋技術(shù)編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加了編程復(fù)雜度；從外存裝入覆蓋文件，是以時(shí)間延長(zhǎng)來(lái)?yè)Q取空間節(jié)省。操作系統(tǒng)教程課件第50頁(yè)交換最早用在麻省理工學(xué)院的兼容分時(shí)系統(tǒng)CTSS中，其基本思想是把主存中暫時(shí)不能運(yùn)行的進(jìn)程或暫時(shí)不使用的程序和數(shù)據(jù)換出到外存，以騰出足夠的主存空間，把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)換入主存。交換技術(shù)并不要求程序員做特殊的工作。交換完全由操作系統(tǒng)進(jìn)行，整個(gè)過(guò)程對(duì)進(jìn)程是透明的。交換的對(duì)象可以是整個(gè)進(jìn)程，此時(shí)成為“整體交換”或“進(jìn)程交換”。圖4-21為作業(yè)交換的示意圖。操作系統(tǒng)教程課件第51頁(yè)4.3.4覆蓋與交換技術(shù)4.3.4覆蓋與交換技術(shù)實(shí)現(xiàn)交換技術(shù)需要后援存儲(chǔ)器，通常是硬盤(pán)，它必須具備兩個(gè)顯著的特征：數(shù)據(jù)傳輸快，容量足夠大。交換技術(shù)主要是在進(jìn)程或作業(yè)之間進(jìn)行，而覆蓋則主要是在同一個(gè)作業(yè)或進(jìn)程內(nèi)進(jìn)行。

操作系統(tǒng)教程課件第52頁(yè)4.4頁(yè)式存儲(chǔ)管理

連續(xù)分配方式要求作業(yè)一次性、連續(xù)裝入在主存空間，對(duì)空間的要求較高，而且可能形成很多“碎片”，雖然可以通過(guò)移動(dòng)技術(shù)將零散的空閑分區(qū)匯集成可用的大塊空間，但需要增加系統(tǒng)的額外開(kāi)銷。如果采用不連續(xù)存儲(chǔ)的方式，把邏輯地址連續(xù)的作業(yè)分散存放到幾個(gè)不連續(xù)的主存區(qū)域中，并能保證作業(yè)的正確執(zhí)行。這樣既可充分利用主存空間，減少主存的碎片，又可避免移動(dòng)所帶來(lái)的額外開(kāi)銷。操作系統(tǒng)教程課件第53頁(yè)4.4.1基本原理

頁(yè)式存儲(chǔ)管理是把主存儲(chǔ)器劃分成大小相等的若干區(qū)域，每個(gè)區(qū)域稱為一塊，并對(duì)它們加以順序編號(hào)，如0#塊、1#塊等等。與此對(duì)應(yīng)，用戶程序的邏輯地址空間劃分成大小相等的若干頁(yè)，同樣為它們加以順序編號(hào)，從0開(kāi)始，如第0頁(yè)、第1頁(yè)等。頁(yè)的大小與塊的大小相等。分頁(yè)式存儲(chǔ)管理的邏輯地址由兩部分組成：頁(yè)號(hào)和頁(yè)內(nèi)地址。其格式為：操作系統(tǒng)教程課件第54頁(yè)頁(yè)內(nèi)地址W頁(yè)號(hào)P31121104.4.2存儲(chǔ)空間的分配與去配

分頁(yè)式存儲(chǔ)管理把主存空間劃分成若干塊，以塊為單位進(jìn)行主存空間的分配。由于塊的大小是固定的，系統(tǒng)可以采用一張主存分配表來(lái)記錄已分配的塊、尚未分配的塊以及當(dāng)前剩余的空閑塊總數(shù)。最簡(jiǎn)單的辦法可用一張“位示圖”來(lái)記錄主存的分配情況。例如主存的用戶區(qū)被劃分成512塊，則可用字長(zhǎng)為32位的16個(gè)字的位示圖來(lái)構(gòu)成一張主存分配表，位示圖中的每一位與一個(gè)物理塊對(duì)應(yīng)，用0/1表示對(duì)應(yīng)塊的占用標(biāo)志（空閑/已占用），另用一個(gè)字節(jié)記錄當(dāng)前系統(tǒng)的剩余空閑塊總數(shù)，如圖4-22所示。操作系統(tǒng)教程課件第55頁(yè)4.4.2存儲(chǔ)空間的分配與去配操作系統(tǒng)教程課件第56頁(yè)進(jìn)行主存分配時(shí)，首先查看空閑塊總數(shù)是否能夠滿足作業(yè)要求，若不能滿足，則不進(jìn)行分配；若能滿足，則從位示圖中找出為“0”的位，并且將其占用標(biāo)志置為“1”，并從空閑塊總數(shù)中減去本次占用的塊數(shù)，按找到的位計(jì)算出對(duì)應(yīng)的塊號(hào)，建立該作業(yè)的頁(yè)表，并把作業(yè)裝入對(duì)應(yīng)的物理塊中。4.4.2存儲(chǔ)空間的分配與去配

由于每一塊的大小相等，在位示圖中查找到一個(gè)為“0”的位后，根據(jù)它所在的字號(hào)、位號(hào)，按如下公式可計(jì)算出對(duì)應(yīng)的塊號(hào)：塊號(hào)＝字號(hào)×字長(zhǎng)＋位號(hào)當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束時(shí)，則應(yīng)該收回作業(yè)所占的主存塊。根據(jù)歸還的塊號(hào)計(jì)算出該塊在位示圖中對(duì)應(yīng)的位置，將占用標(biāo)志修改為“0”，同時(shí)把歸還塊數(shù)加入到空閑塊總數(shù)中。假定歸還塊的塊號(hào)為i，則在位示圖中對(duì)應(yīng)的位置為：字號(hào)＝[i/字長(zhǎng)]，位號(hào)＝imod字長(zhǎng)其中[]表示對(duì)i除以字長(zhǎng)后取其整數(shù)，而mod表示對(duì)i除以字長(zhǎng)后取其余數(shù)部分。

操作系統(tǒng)教程課件第57頁(yè)4.4.3頁(yè)表與地址轉(zhuǎn)換在分頁(yè)式存儲(chǔ)管理系統(tǒng)中，允許將作業(yè)的每一頁(yè)離散地存儲(chǔ)在主存的物理塊中，但系統(tǒng)必須能夠保證作業(yè)的正確運(yùn)行，即能在主存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊。為此，系統(tǒng)為每個(gè)作業(yè)建立了一張頁(yè)面映像表，簡(jiǎn)稱頁(yè)表。頁(yè)表實(shí)現(xiàn)了從頁(yè)號(hào)到主存塊號(hào)的地址映像。作業(yè)中的所有頁(yè)（0~n）依次地在頁(yè)表中記錄了相應(yīng)頁(yè)在主存中對(duì)應(yīng)的物理塊號(hào)，如圖4-23所示。頁(yè)表的長(zhǎng)度由進(jìn)程或作業(yè)擁有的頁(yè)面數(shù)決定。操作系統(tǒng)教程課件第58頁(yè)4.4.3頁(yè)表與地址轉(zhuǎn)換操作系統(tǒng)教程課件第59頁(yè)圖4-23頁(yè)表示意圖4.4.3頁(yè)表與地址轉(zhuǎn)換操作系統(tǒng)教程課件第60頁(yè)頁(yè)式存儲(chǔ)管理采用動(dòng)態(tài)重定位方式裝入作業(yè)，作業(yè)執(zhí)行時(shí)通過(guò)硬件的地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)從用戶空間中的邏輯地址到主存空間中物理地址的轉(zhuǎn)換工作。由于頁(yè)內(nèi)地址和物理塊內(nèi)的地址是一一對(duì)應(yīng)的。因此，地址變換機(jī)構(gòu)的任務(wù)，實(shí)際上是將邏輯地址中的頁(yè)號(hào)，轉(zhuǎn)換成為主存中的物理塊號(hào)。頁(yè)表是硬件進(jìn)行地址轉(zhuǎn)換的依據(jù)。4.4.3頁(yè)表與地址轉(zhuǎn)換

調(diào)度程序在選擇作業(yè)后，將選中作業(yè)的頁(yè)表始址送入硬件設(shè)置的頁(yè)表控制寄存器中。地址轉(zhuǎn)換時(shí)，只要從頁(yè)表寄存器中就可找到相應(yīng)的頁(yè)表。當(dāng)作業(yè)執(zhí)行時(shí)，分頁(yè)地址變換機(jī)構(gòu)會(huì)自動(dòng)將邏輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，以頁(yè)號(hào)位索引檢索頁(yè)表，如果頁(yè)表中無(wú)此頁(yè)號(hào)，則產(chǎn)生一個(gè)“地址錯(cuò)”的程序性中斷事件；如果頁(yè)表中有此頁(yè)號(hào)，則可得到對(duì)應(yīng)的主存塊號(hào)，再按邏輯地址中的頁(yè)內(nèi)地址計(jì)算出欲訪問(wèn)的主存單元的物理地址。因?yàn)閴K的大小相等，所以物理地址=塊號(hào)×塊長(zhǎng)＋頁(yè)內(nèi)地址圖4-24給出分頁(yè)式存儲(chǔ)管理的地址變換機(jī)構(gòu)示例。操作系統(tǒng)教程課件第61頁(yè)4.4.3頁(yè)表與地址轉(zhuǎn)換操作系統(tǒng)教程課件第62頁(yè)圖4-24分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)示意圖4.4.4快表由于頁(yè)表是存放在主存儲(chǔ)器中的，這樣取一個(gè)數(shù)據(jù)或指令至少需要訪問(wèn)主存兩次以上。第一次是訪問(wèn)主存中的頁(yè)表，查找到指定頁(yè)面所對(duì)應(yīng)的物理塊號(hào)，將塊號(hào)與頁(yè)內(nèi)地址拼接，計(jì)算出數(shù)據(jù)或指令的物理地址。第二次訪問(wèn)主存時(shí)，根據(jù)第一次得到的物理地址進(jìn)行數(shù)據(jù)的存取操作。為了提高存取速度，可以設(shè)想把頁(yè)表存放在一組寄存器中，但寄存器成本太高，數(shù)量有限，不可行。通常在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查找能力的小容量高速緩沖寄存器，又稱“相聯(lián)寄存器”。利用高速緩沖寄存器存放頁(yè)表的一部分，把存放在高速緩沖寄存器中的這部分頁(yè)表稱“快表”?？毂碇械怯浟水?dāng)前執(zhí)行程序中最常用的頁(yè)號(hào)與主存中塊號(hào)的對(duì)應(yīng)關(guān)系，圖4-25給出具有快表的地址變換機(jī)構(gòu)示例。操作系統(tǒng)教程課件第63頁(yè)4.4.4快表操作系統(tǒng)教程課件第64頁(yè)圖4-25具有快表的地址變換機(jī)構(gòu)示意圖4.4.5頁(yè)的共享與保護(hù)

采用頁(yè)式存儲(chǔ)管理能方便地實(shí)現(xiàn)程序和數(shù)據(jù)的共享。在多道程序系統(tǒng)中，編譯程序、編輯程序、解釋程序、公共子程序、公共數(shù)據(jù)等都是可共享的，這些共享的信息在主存儲(chǔ)器中只需要保留一個(gè)副本，大大提高了主存空間的利用率。在實(shí)現(xiàn)共享時(shí)，必須區(qū)分?jǐn)?shù)據(jù)的共享和程序的共享。實(shí)現(xiàn)數(shù)據(jù)共享時(shí)，可允許不同的作業(yè)對(duì)共享的數(shù)據(jù)頁(yè)采用不同頁(yè)號(hào)，只需要將各自的有關(guān)表目指向共享的數(shù)據(jù)信息塊即可。而實(shí)現(xiàn)程序共享時(shí)，由于頁(yè)式存儲(chǔ)結(jié)構(gòu)要求邏輯地址空間是連續(xù)的，所以在程序運(yùn)行前它們的頁(yè)號(hào)是確定的。操作系統(tǒng)教程課件第65頁(yè)4.4.5頁(yè)的共享與保護(hù)圖4-26所示給出了兩個(gè)作業(yè)共享一個(gè)程序和一個(gè)數(shù)據(jù)段的情況。操作系統(tǒng)教程課件第66頁(yè)4.5段式存儲(chǔ)管理

用戶編制的程序是由若干段組成的：一個(gè)程序可以由一個(gè)主程序、若干子程序、符號(hào)表、棧以及數(shù)據(jù)等若干段組成。每一段都有獨(dú)立、完整的邏輯意義，每一段程序都可獨(dú)立編制，且每一段的長(zhǎng)度可以不同。段式存儲(chǔ)管理支持用戶的分段觀點(diǎn)，具有邏輯上的清晰和完整性，它以段為單位進(jìn)行存儲(chǔ)空間的管理。操作系統(tǒng)教程課件第67頁(yè)4.5.1原理每個(gè)作業(yè)由若干個(gè)相對(duì)獨(dú)立的段組成，每個(gè)段都有一個(gè)段名，為了實(shí)現(xiàn)簡(jiǎn)單，通?？捎枚翁?hào)代替段名，段號(hào)從“0”開(kāi)始，每一段的邏輯地址都從“0”開(kāi)始編址，段內(nèi)地址是連續(xù)的，而段與段之間的地址是不連續(xù)的。其邏輯地址由段號(hào)和段內(nèi)地址兩部分所組成：操作系統(tǒng)教程課件第68頁(yè)段內(nèi)地址W段號(hào)S31161504.5.2空間的分配與去配

分段式存儲(chǔ)管理是在可變分區(qū)存儲(chǔ)管理方式的基礎(chǔ)上發(fā)展而來(lái)的。在分段式存儲(chǔ)管理方式中，以段為單位進(jìn)行主存分配，每一個(gè)段在主存中占有一個(gè)連續(xù)空間，但各個(gè)段之間可以離散地存放在主存不同的區(qū)域中。為了使程序能正常運(yùn)行，即能從主存中正確找出每個(gè)段所在的分區(qū)位置，系統(tǒng)為每個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱“段表”。每個(gè)段在表中占有一個(gè)表項(xiàng)，記錄該段在主存儲(chǔ)器中的起始地址和長(zhǎng)度，如圖4-27所示。段表實(shí)現(xiàn)了從邏輯段到主存空間之間的映射。操作系統(tǒng)教程課件第69頁(yè)4.5.2空間的分配與去配操作系統(tǒng)教程課件第70頁(yè)圖4-27段的裝入示意圖4.5.2空間的分配與去配

如果在裝入某段信息時(shí)找不到滿足該段地址空間大小的空閑區(qū)，則可采用移動(dòng)技術(shù)合并分散的空閑區(qū)，以利于大作業(yè)的裝入。當(dāng)采用分段式存儲(chǔ)管理的作業(yè)執(zhí)行結(jié)束后，它所占據(jù)的主存空間將被回收，回收后的主存空間登記在空閑分區(qū)表中，可以用來(lái)裝入新的作業(yè)。系統(tǒng)在回收空間時(shí)同樣需要檢查是否存在與回收區(qū)相鄰的空閑分區(qū)，如果有，則將其合并成為一個(gè)新的空閑分區(qū)進(jìn)行登記管理。段表存放在主存儲(chǔ)器中，在訪問(wèn)一個(gè)數(shù)據(jù)或指令時(shí)至少需要訪問(wèn)主存兩次以上。為了提高對(duì)段表的存取速度，通常增設(shè)一個(gè)相聯(lián)寄存器，利用高速緩沖寄存器保存最近常用的段表項(xiàng)。

操作系統(tǒng)教程課件第71頁(yè)4.5.3地址轉(zhuǎn)換與存儲(chǔ)保護(hù)

段式存儲(chǔ)管理采用動(dòng)態(tài)重定位方式裝入作業(yè)，作業(yè)執(zhí)行時(shí)通過(guò)硬件的地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換工作，段表的表目起到了基址寄存器和限長(zhǎng)寄存器的作用，是硬件進(jìn)行地址轉(zhuǎn)換的依據(jù)。圖4-28給出分段式存儲(chǔ)管理的地址變換示例。

操作系統(tǒng)教程課件第72頁(yè)4.5.4段的共享

由于段是按邏輯意義來(lái)劃分的，可以按段名進(jìn)行訪問(wèn)，因此分段式存儲(chǔ)管理系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)，是可以方便地實(shí)現(xiàn)段的共享，即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)段。為實(shí)現(xiàn)某段代碼的共享，在分段式存儲(chǔ)管理系統(tǒng)中，各個(gè)進(jìn)程對(duì)共享段使用相同的段名，在各自的段表中填入共享段的起始地址，并置以適當(dāng)?shù)淖x寫(xiě)控制權(quán)，即可做到共享一個(gè)邏輯上完整的主存段信息。例如一個(gè)多用戶系統(tǒng)，可同時(shí)接納40個(gè)用戶，他們都需要執(zhí)行一個(gè)文本編輯程序（TextEditor）。如果文本編輯程序有160KB的代碼和40KB的數(shù)據(jù)區(qū)，則總共需要8MB的主存空間來(lái)支持40個(gè)用戶的訪問(wèn)。如果160KB的代碼是可重入的，則該代碼只需要在主存中保留一份文本編輯程序的副本，此時(shí)所需要的主存空間僅為1760KB（40×40+160），只需要在每個(gè)進(jìn)程的段表中為文本編輯程序設(shè)置一個(gè)段表項(xiàng)。

操作系統(tǒng)教程課件第73頁(yè)4.5.4段的共享操作系統(tǒng)教程課件第74頁(yè)圖4-29段的共享示意圖4.5.4段的共享

在多道程序設(shè)計(jì)系統(tǒng)中，由于進(jìn)程的并發(fā)執(zhí)行，一個(gè)程序段為多個(gè)進(jìn)程共享時(shí)，有可能出現(xiàn)多次同時(shí)重復(fù)執(zhí)行該段程序的情況，而該共享程序段的指令和數(shù)據(jù)在執(zhí)行過(guò)程中是不能被修改的。此外，共享段也有可能被置換出主存，顯然，一個(gè)正在被某個(gè)進(jìn)程使用或即將被某個(gè)進(jìn)程使用的共享段是不應(yīng)該置換出主存的，因此可以在段表中設(shè)置共享位來(lái)判別該段是否正在被某個(gè)進(jìn)程調(diào)用。操作系統(tǒng)教程課件第75頁(yè)4.5.5分頁(yè)和分段存儲(chǔ)管理的主要區(qū)別分頁(yè)和分段系統(tǒng)都采用離散分配主存方式，都需要通過(guò)地址映射機(jī)構(gòu)來(lái)實(shí)現(xiàn)地址變換，有許多相似之處。但兩者又是完全不同的。具體表現(xiàn)如下。①頁(yè)是信息的物理單位，是系統(tǒng)管理的需要而不是用戶的需要；而段則是信息的邏輯單位，它含有一組意義相對(duì)完整的信息，分段是為了更好地滿足用戶的需要。②頁(yè)的大小固定且由系統(tǒng)決定，因而一個(gè)系統(tǒng)只能有一種大小的頁(yè)面；而段的長(zhǎng)度卻不固定，由用戶所編寫(xiě)的程序決定，通常由編譯程序?qū)υ闯绦蜻M(jìn)行編譯時(shí)根據(jù)信息的性質(zhì)來(lái)劃分。③分頁(yè)式作業(yè)的地址空間是一維的，頁(yè)間的邏輯地址是連續(xù)的；而分段式作業(yè)的地址空間則是二維的，段間的邏輯地址是不連續(xù)的。操作系統(tǒng)教程課件第76頁(yè)4.6段頁(yè)式存儲(chǔ)管理

段式存儲(chǔ)管理支持了用戶的觀點(diǎn)，但每段必須占據(jù)主存儲(chǔ)器的連續(xù)區(qū)域，有可能需要采用移動(dòng)技術(shù)匯集主存空間，為此，兼用分段和分頁(yè)的方法，構(gòu)成可分頁(yè)的段式存儲(chǔ)管理，通常被稱為是“段頁(yè)式存儲(chǔ)管理”。段頁(yè)式存儲(chǔ)管理兼顧了段式在邏輯上的清晰和頁(yè)式在管理上方便的優(yōu)點(diǎn)。用戶對(duì)作業(yè)采用分段組織，每段獨(dú)立編程，在主存空間分配時(shí)，再把每段分成若干個(gè)頁(yè)面，這樣每段不必占據(jù)連續(xù)的主存空間，可把它按頁(yè)存放在不連續(xù)的主存塊中。段頁(yè)式存儲(chǔ)管理的邏輯地址格式如下：操作系統(tǒng)教程課件第77頁(yè)4.6段頁(yè)式存儲(chǔ)管理

段頁(yè)式存儲(chǔ)管理為每一個(gè)裝入主存的作業(yè)建立一張段表，且對(duì)每一段建立一張頁(yè)表。段表的長(zhǎng)度由作業(yè)分段的個(gè)數(shù)決定，段表中的每一個(gè)表目指出本段頁(yè)表的始址和長(zhǎng)度。頁(yè)表的長(zhǎng)度則由對(duì)應(yīng)段所劃分的頁(yè)面數(shù)所決定，頁(yè)表中的每一個(gè)表目指出本段的邏輯頁(yè)號(hào)與主存物理塊號(hào)之間的對(duì)應(yīng)關(guān)系。段頁(yè)式存儲(chǔ)管理中段表、頁(yè)表之間的關(guān)系如圖4-30所示。操作系統(tǒng)教程課件第78頁(yè)4.6段頁(yè)式存儲(chǔ)管理

執(zhí)行指令時(shí)，地址機(jī)構(gòu)根據(jù)邏輯地址中的段號(hào)查找段表，得到該段的頁(yè)表始址，然后根據(jù)邏輯地址中的頁(yè)號(hào)查找該頁(yè)表，得到對(duì)應(yīng)的主存塊號(hào)，由主存塊號(hào)與邏輯地址中的頁(yè)內(nèi)地址形成可訪問(wèn)的物理地址。如果邏輯地址中的段號(hào)超出了段表中的最大段號(hào)或者頁(yè)號(hào)超出了該段頁(yè)表中的最大頁(yè)號(hào)，都將形成“地址越界”的程序性中斷事件?？梢钥闯?，由邏輯地址到物理地址的變換過(guò)程中，需要三次訪問(wèn)主存，第一次是訪問(wèn)主存中的段表，獲得該段對(duì)應(yīng)頁(yè)表的始址，第二次是訪問(wèn)頁(yè)表，獲得指令或數(shù)據(jù)的物理地址，最后再按物理地址存取信息。段頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換機(jī)構(gòu)如圖4-31所示。操作系統(tǒng)教程課件第79頁(yè)4.6段頁(yè)式存儲(chǔ)管理操作系統(tǒng)教程課件第80頁(yè)圖4-31段頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換機(jī)構(gòu)示意圖4.7虛擬存儲(chǔ)管理方式前面所介紹的各種存儲(chǔ)管理方式具有一個(gè)共同的特點(diǎn)，即作業(yè)必須一次性全部裝入主存空間后才能運(yùn)行，直至作業(yè)運(yùn)行結(jié)束后才釋放所占有的全部主存資源。這樣就會(huì)出現(xiàn)以下情況：（1）當(dāng)主存空間不能滿足作業(yè)地址空間要求時(shí)，作業(yè)就不能裝入主存，無(wú)法運(yùn)行。（2）當(dāng)有大量作業(yè)要求運(yùn)行時(shí)，由于主存容量有限，只能將少數(shù)作業(yè)裝入主存運(yùn)行，而其他作業(yè)留在輔存上等待。

操作系統(tǒng)教程課件第81頁(yè)4.7虛擬存儲(chǔ)管理方式

早在1968年，Denning.P就曾指出：程序執(zhí)行時(shí)呈現(xiàn)出局部性特征，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；而它所訪問(wèn)的存儲(chǔ)空間也局限在某個(gè)區(qū)域中。局限性表現(xiàn)在時(shí)間局限性和空間局限性兩方面。（１）時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問(wèn)，則不久以后該數(shù)據(jù)可能再次被訪問(wèn)。例如程序中存在著的大量的迭代循環(huán)、臨時(shí)變量和子程序調(diào)用等。（２）空間局限性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，在不久以后，其附近的存儲(chǔ)單元也將被訪問(wèn)，即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍之內(nèi)。例如對(duì)數(shù)組、表或數(shù)據(jù)堆棧進(jìn)行操作。

4.7.1虛擬存儲(chǔ)器基于局部性原理，可以把作業(yè)信息保存在磁盤(pán)上，當(dāng)作業(yè)請(qǐng)求裝入時(shí)，只需將當(dāng)前運(yùn)行所需要的一部分信息先裝入主存，作業(yè)執(zhí)行過(guò)程時(shí)，如果所要訪問(wèn)的信息已調(diào)入主存，則可繼續(xù)執(zhí)行；如果信息尚未裝入主存，再將這些信息調(diào)入主存，使程序繼續(xù)執(zhí)行；如果此時(shí)主存已滿，無(wú)法再裝入新的信息，則系統(tǒng)將主存中暫時(shí)不用的信息置換到磁盤(pán)上，騰出主存空間后，再將所需要的信息調(diào)入主存，使程序繼續(xù)執(zhí)行。這樣，可使一個(gè)大的用戶程序得以在比較小的主存空間中運(yùn)行，也可以在主存中同時(shí)裝入更多的作業(yè)使它們并發(fā)執(zhí)行。這不僅使主存空間能充分地被利用，而且用戶編制程序時(shí)可以不必考慮主存儲(chǔ)器的實(shí)際容量，允許用戶的邏輯地址空間大于主存的實(shí)際容量。從用戶的角度來(lái)看，好像計(jì)算機(jī)系統(tǒng)提供了一個(gè)容量很大的主存儲(chǔ)器，我們稱它為“虛擬存儲(chǔ)器”。

操作系統(tǒng)教程課件第83頁(yè)4.7.1虛擬存儲(chǔ)器虛擬存貯器指一種實(shí)際上并不存在的虛假存貯器，它是系統(tǒng)為了滿足應(yīng)用對(duì)存貯器容量的巨大需求而構(gòu)造的一個(gè)非常大的地址空間。它使用戶在編程時(shí)無(wú)需擔(dān)心存貯器之不足，好像有一個(gè)無(wú)限大的存貯器供其使用一樣。虛擬存儲(chǔ)器是建立在離散分配的存儲(chǔ)管理方式的基礎(chǔ)上，它允許將一個(gè)作業(yè)分多次調(diào)入主存。虛擬存儲(chǔ)器實(shí)際上是為了擴(kuò)大主存容量而采用的一種設(shè)計(jì)技巧，虛擬存儲(chǔ)器的容量由計(jì)算機(jī)的地址結(jié)構(gòu)和輔助存儲(chǔ)器的容量所決定，與實(shí)際主存儲(chǔ)器的容量無(wú)關(guān)，其邏輯容量由主存和輔存容量之和決定，其運(yùn)行速度接近于主存儲(chǔ)器的速度，而每位的成本卻又接近輔助存儲(chǔ)器?？梢?jiàn)，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)。操作系統(tǒng)教程課件第84頁(yè)4.7.1虛擬存儲(chǔ)器

虛擬存儲(chǔ)器具有離散性、多次性、對(duì)換性和虛擬性四大主要特征。1、離散性2、多次性3、對(duì)換性4、虛擬性

操作系統(tǒng)教程課件第85頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理是在頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求分頁(yè)功能和頁(yè)面置換功能實(shí)現(xiàn)的虛擬存儲(chǔ)系統(tǒng)。請(qǐng)求分頁(yè)式存儲(chǔ)管理允許作業(yè)只裝入部分頁(yè)面，就啟動(dòng)運(yùn)行，在執(zhí)行過(guò)程中，如果所要訪問(wèn)的頁(yè)已調(diào)入主存，則進(jìn)行地址轉(zhuǎn)換，得到欲訪問(wèn)的主存物理地址；如果所要訪問(wèn)的頁(yè)面不在主存中，則產(chǎn)生一個(gè)“缺頁(yè)中斷”，如果此時(shí)主存能容納新頁(yè)，則啟動(dòng)磁盤(pán)I/O將其調(diào)入主存；如果主存已滿，則通過(guò)頁(yè)面置換功能將當(dāng)前所需的頁(yè)面調(diào)入。操作系統(tǒng)教程課件第86頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

1.請(qǐng)求分頁(yè)式存儲(chǔ)的管理為了實(shí)現(xiàn)請(qǐng)求分頁(yè)和頁(yè)面置換功能，系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件支持。一般需要以下支持：

◆請(qǐng)求分頁(yè)的頁(yè)表機(jī)制

◆缺頁(yè)中斷機(jī)構(gòu)

◆地址變換機(jī)構(gòu)

◆頁(yè)面置換算法

操作系統(tǒng)教程課件第87頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理（1）頁(yè)表機(jī)制請(qǐng)求分頁(yè)式存儲(chǔ)管理的主要依據(jù)就是頁(yè)表。由于只是將作業(yè)的部分頁(yè)面調(diào)入主存，其余部分仍存放在輔助存儲(chǔ)器上，因此必須指出哪些頁(yè)面已在主存，哪些頁(yè)面還沒(méi)有裝入。為此需要將頁(yè)表增加若干項(xiàng)，修改后的頁(yè)表格式如下所示：操作系統(tǒng)教程課件第88頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（2）缺頁(yè)中斷機(jī)構(gòu)請(qǐng)求分頁(yè)式存儲(chǔ)管理中，當(dāng)所要訪問(wèn)的頁(yè)面不在主存時(shí)，則由硬件發(fā)出一個(gè)缺頁(yè)中斷，操作系統(tǒng)必須處理這個(gè)中斷，將所需要的頁(yè)面調(diào)入主存，圖4-32給出缺頁(yè)中斷處理的流程。在處理缺頁(yè)中斷的過(guò)程中，同樣需要保護(hù)現(xiàn)場(chǎng)、分析中斷源、轉(zhuǎn)入中斷處理程序進(jìn)行處理、恢復(fù)現(xiàn)場(chǎng)等步驟，但缺頁(yè)中斷又與一般的中斷有著明顯的區(qū)別，主要表現(xiàn)在：操作系統(tǒng)教程課件第89頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理操作系統(tǒng)教程課件第90頁(yè)圖4-32缺頁(yè)中斷處理流程4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

在處理缺頁(yè)中斷的過(guò)程中，同樣需要保護(hù)現(xiàn)場(chǎng)、分析中斷源、轉(zhuǎn)入中斷處理程序進(jìn)行處理、恢復(fù)現(xiàn)場(chǎng)等步驟，但缺頁(yè)中斷又與一般的中斷有著明顯的區(qū)別，主要表現(xiàn)在：1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。通常，CPU在一條指令結(jié)束后接收中斷請(qǐng)求并響應(yīng)。而缺頁(yè)中斷則是在指令執(zhí)行期間，所要訪問(wèn)的指令或數(shù)據(jù)不在主存時(shí)所產(chǎn)生和處理的。2）一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁(yè)中斷。操作系統(tǒng)教程課件第91頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

3）地址變換機(jī)構(gòu)在請(qǐng)求分頁(yè)式存儲(chǔ)管理中，當(dāng)作業(yè)訪問(wèn)某頁(yè)時(shí)，硬件的地址轉(zhuǎn)換機(jī)構(gòu)首先查找快表，若找到，并且其狀態(tài)位為“1”，則按指定的物理塊號(hào)進(jìn)行地址轉(zhuǎn)換，得到其對(duì)應(yīng)的物理地址；若該頁(yè)的狀態(tài)位為“0”，則由硬件發(fā)出一個(gè)“缺頁(yè)中斷”，按照頁(yè)表中指出的輔存地址，由操作系統(tǒng)將其調(diào)入主存，并在頁(yè)表中填上其分配的物理塊號(hào)，修改狀態(tài)位、訪問(wèn)位，對(duì)于寫(xiě)指令，置修改位為“1”，然后按頁(yè)表中的物理塊號(hào)和頁(yè)內(nèi)地址形成物理地址，圖4-34給出請(qǐng)求分頁(yè)式存儲(chǔ)管理中的地址變換過(guò)程。如果在快表中未找到該頁(yè)的頁(yè)表項(xiàng)時(shí)，則到主存中查找頁(yè)表，若該頁(yè)尚未調(diào)入主存，系統(tǒng)產(chǎn)生缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將該頁(yè)面調(diào)入，同時(shí)將此頁(yè)表項(xiàng)寫(xiě)入快表。

操作系統(tǒng)教程課件第92頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理操作系統(tǒng)教程課件第93頁(yè)圖4-34請(qǐng)求式分頁(yè)存儲(chǔ)管理地址變換過(guò)程4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

2．頁(yè)面置換算法在作業(yè)運(yùn)行過(guò)程中，如果所要訪問(wèn)的頁(yè)面不在主存中，需要把他們調(diào)入主存，但主存中已沒(méi)有空閑空間時(shí)，為了保證作業(yè)的運(yùn)行，系統(tǒng)必須按一定的算法選擇一個(gè)已在主存中的頁(yè)面，將它暫時(shí)調(diào)出主存，讓出主存空間，用來(lái)存放所需調(diào)入的頁(yè)面，這個(gè)工作稱為“頁(yè)面置換”。選擇換出頁(yè)面的算法稱為“頁(yè)面置換算法”。剛被調(diào)出的頁(yè)面又立即要用，因而又要把它調(diào)入，而調(diào)入不久又被選中調(diào)出，調(diào)出不久又被調(diào)入，如此反復(fù)，使調(diào)度非常頻繁，以至于大部分時(shí)間都花費(fèi)在來(lái)回調(diào)度上。這種現(xiàn)象稱為“抖動(dòng)”或稱“顛簸”。一個(gè)好的置換算法應(yīng)該盡可能地減少和避免抖動(dòng)現(xiàn)象的發(fā)生。

操作系統(tǒng)教程課件第94頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（1）最佳置換算法（OPT）最佳置換算法選擇被淘汰的頁(yè)面將是以后永遠(yuǎn)不再使用，或者是在將來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，這樣，產(chǎn)生的缺頁(yè)中斷次數(shù)將會(huì)是最少的。采用最佳置換算法通常可獲得最低的缺頁(yè)中斷率，但這是一種理想化的算法，無(wú)法實(shí)現(xiàn)。但是這個(gè)算法可以作為衡量其它算法的標(biāo)準(zhǔn)。操作系統(tǒng)教程課件第95頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理假定某進(jìn)程共有8頁(yè)，且系統(tǒng)為之分配了三個(gè)物理塊，并有以下頁(yè)面調(diào)度序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1采用最佳置換算法，只發(fā)生了9次頁(yè)面置換，缺頁(yè)中斷率為45%。操作系統(tǒng)教程課件第96頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（2）先進(jìn)先出頁(yè)面置換算法（FIFO）先進(jìn)先出頁(yè)面置換算法認(rèn)為剛被調(diào)入的頁(yè)面在最近的將來(lái)被訪問(wèn)的可能很大，而在主存中駐留時(shí)間最長(zhǎng)的頁(yè)面在最近的將來(lái)被訪問(wèn)的可能性最小。因此，F(xiàn)IFO算法總是淘汰最先進(jìn)入主存的頁(yè)面，即淘汰在主存中駐留時(shí)間最長(zhǎng)的頁(yè)面。FIFO算法只需要把裝入主存的頁(yè)面按調(diào)入的先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，指針始終指向最先裝入主存的頁(yè)面，每次頁(yè)面置換時(shí)，總是選擇替換指針?biāo)甘镜捻?yè)面調(diào)出。操作系統(tǒng)教程課件第97頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理圖4-36給出了以O(shè)PT算法中的例子采用FIFO算法時(shí)保留在主存中頁(yè)面變化的情況。采用FIFO置換算法一共發(fā)生了15次頁(yè)面置換，缺頁(yè)中斷率為75%，頁(yè)面淘汰的順序?yàn)?，0，1，2，3，0，4，2，3，0，1，2。FIFO算法簡(jiǎn)單，易實(shí)現(xiàn)，但效率不高。操作系統(tǒng)教程課件第98頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理先進(jìn)先出算法存在一種異?，F(xiàn)象。一般來(lái)說(shuō)，對(duì)于任一個(gè)作業(yè)，系統(tǒng)分配給它的主存物理塊數(shù)越接近于它所要求的頁(yè)面數(shù)，則發(fā)生缺頁(yè)中斷的次數(shù)會(huì)越少，如果一個(gè)作業(yè)獲得它所要求的全部物理塊數(shù)，則不會(huì)發(fā)生缺頁(yè)中斷現(xiàn)象。但是，采用FIFO算法時(shí)，在未給作業(yè)分配滿足它所要求的頁(yè)面時(shí)，有時(shí)會(huì)出現(xiàn)這樣的奇怪現(xiàn)象：分配的物理塊數(shù)增多，而缺頁(yè)中斷次數(shù)反而增加。這種現(xiàn)象稱之為Belady現(xiàn)象。操作系統(tǒng)教程課件第99頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理操作系統(tǒng)教程課件第100頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（3）最近最少用頁(yè)面置換算法（LRU）最近最少用頁(yè)面置換算法總是選擇最近一段時(shí)間內(nèi)最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)面調(diào)出。LRU的提出基于程序執(zhí)行的局部性原理，即認(rèn)為那些剛被訪問(wèn)的頁(yè)面，可能在最近的將來(lái)還會(huì)經(jīng)常訪問(wèn)它們，而那些在較長(zhǎng)時(shí)間里未被訪問(wèn)的頁(yè)面，一般在最近的將來(lái)不會(huì)再訪問(wèn)。為了記錄頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)過(guò)的時(shí)間，需要在頁(yè)表中增加一個(gè)“引用位”標(biāo)志，在每次被訪問(wèn)后將引用位置零，重新計(jì)時(shí)，這樣，在發(fā)生缺頁(yè)中斷需要調(diào)入新的頁(yè)面時(shí)，通過(guò)檢查頁(yè)表中各頁(yè)的引用位，選擇計(jì)時(shí)最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)面淘汰，并且把主存中所有頁(yè)面的引用位全部清零，重新計(jì)時(shí)。

操作系統(tǒng)教程課件第101頁(yè)圖4-39所示為在OPT算法的例子中采用LRU算法時(shí)，保留在主存中頁(yè)面的變化情況。該進(jìn)程執(zhí)行過(guò)程中，共產(chǎn)生了12次缺頁(yè)中斷，缺頁(yè)中斷率為60%，頁(yè)面淘汰的順序?yàn)?，1，2，3，0，4，0，3，2。操作系統(tǒng)教程課件第102頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

LRU近似算法（時(shí)鐘置換算法Clock）是在頁(yè)表中為每一頁(yè)增加一個(gè)引用位信息，當(dāng)該頁(yè)被訪問(wèn)時(shí)，由硬件將它的引用位信息置為1，操作系統(tǒng)選擇一個(gè)時(shí)間周期T，每隔一個(gè)周期T，將頁(yè)表中所有頁(yè)面的引用位信息置0，這樣，在時(shí)間周期T內(nèi)，被訪問(wèn)過(guò)的頁(yè)面的引用位為1，而沒(méi)有被訪問(wèn)過(guò)的頁(yè)面的引用位仍為0。當(dāng)產(chǎn)生缺頁(yè)中斷時(shí)，可以從引用位為0的頁(yè)面中選擇一頁(yè)調(diào)出，同時(shí)將所有頁(yè)面的引用位信息全部重置0。這種近似算法的實(shí)現(xiàn)比較簡(jiǎn)單，但關(guān)鍵在于時(shí)間周期T大小的確定。T太大，可能所有的引用位都變成1，找不出最近最少使用的頁(yè)面淘汰；T太小，引用位為0的頁(yè)面可能很多，而無(wú)法保證所選擇的頁(yè)面是最近最少使用的。操作系統(tǒng)教程課件第103頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

淘汰一個(gè)頁(yè)面時(shí)，如果該頁(yè)面已被修改過(guò)，必須將它重新寫(xiě)回磁盤(pán)；但如果淘汰的是未被修改過(guò)的頁(yè)面，就不需要寫(xiě)盤(pán)操作了，這樣看來(lái)淘汰修改過(guò)的頁(yè)面比淘汰未被修改過(guò)的頁(yè)面開(kāi)銷要大。如果把頁(yè)表中的“引用位”和“修改位”結(jié)合起來(lái)使用可以改進(jìn)時(shí)鐘頁(yè)面替換算法，它們一共組合成四種情況：（1）最近沒(méi)有被引用，沒(méi)有被修改（r=0，m=0）（2）最近被引用，沒(méi)有被修改（r=1，m=0）（3）最近沒(méi)有被引用，但被修改（r=0，m=1）（4）最近被引用過(guò)，也被修改過(guò)（r=1，m=1）操作系統(tǒng)教程課件第104頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

改進(jìn)的時(shí)鐘頁(yè)面替換算法就是掃描隊(duì)列中的所有頁(yè)面，尋找一個(gè)既沒(méi)有被修改且最近又沒(méi)有被引用過(guò)的頁(yè)面，把這樣的頁(yè)面挑出來(lái)作為首選頁(yè)面淘汰是因?yàn)闆](méi)有被修改過(guò)，淘汰時(shí)不用把它寫(xiě)回磁盤(pán)。如果第一步?jīng)]找到這樣的頁(yè)面，算法再次掃描隊(duì)列，欲尋找一個(gè)被修改過(guò)但最近沒(méi)有被引用過(guò)的頁(yè)面；雖然淘汰這種頁(yè)面需寫(xiě)回磁盤(pán)，但依據(jù)程序局部性原理，這類頁(yè)面一般不會(huì)被馬上再次使用。如果第二步也失敗了，則所有頁(yè)面已被標(biāo)記為最近未被引用，可進(jìn)入第三步掃描。Macintosh的虛存管理采用了這種策略，其主要優(yōu)點(diǎn)是沒(méi)有被修改過(guò)的頁(yè)面會(huì)被優(yōu)先選出來(lái)，淘汰這種頁(yè)面時(shí)不必寫(xiě)回磁盤(pán)，從而節(jié)省時(shí)間，但查找一個(gè)淘汰頁(yè)面可能會(huì)經(jīng)過(guò)多輪掃描，算法的實(shí)現(xiàn)開(kāi)銷較大。操作系統(tǒng)教程課件第105頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理（4）最近最不常用頁(yè)面置換算法（LFU）最近最不常用置換算法總是選擇被訪問(wèn)次數(shù)最少的頁(yè)面調(diào)出，即認(rèn)為在過(guò)去的一段時(shí)間里被訪問(wèn)次數(shù)多的頁(yè)面可能經(jīng)常需要訪問(wèn)。一種簡(jiǎn)單的實(shí)現(xiàn)方法是為每一頁(yè)設(shè)置一個(gè)計(jì)數(shù)器，頁(yè)面每次被訪問(wèn)后其對(duì)應(yīng)的計(jì)數(shù)器加1，每隔一定的時(shí)間周期T，將所有計(jì)數(shù)器全部清零。這樣，在發(fā)生缺頁(yè)中斷時(shí)，選擇計(jì)數(shù)器值最小的對(duì)應(yīng)頁(yè)面淘汰，顯然它是最近最不常用的頁(yè)面，同時(shí)把所有計(jì)數(shù)器清零。這種算法實(shí)現(xiàn)比較簡(jiǎn)單，但代價(jià)很高，同時(shí)有一個(gè)關(guān)鍵問(wèn)題是如何選擇一個(gè)合適的時(shí)間周期T。

操作系統(tǒng)教程課件第106頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

3．缺頁(yè)中斷率分析虛擬存儲(chǔ)系統(tǒng)解決了有限主存貯器的容量限制問(wèn)題，能使更多的作業(yè)同時(shí)多道運(yùn)行，從而提高系統(tǒng)的效率，但缺頁(yè)中斷處理需要系統(tǒng)的額外開(kāi)銷，影響系統(tǒng)效率，因此應(yīng)盡可能減少缺頁(yè)中斷的次數(shù)，降低缺頁(yè)中斷率。假定一個(gè)作業(yè)共有n頁(yè)，系統(tǒng)分配給它的主存塊是m塊（m、n均為正整數(shù)，且1≤m≤n）。因此，該作業(yè)最多有m頁(yè)可同時(shí)被裝入主存。如果作業(yè)執(zhí)行中訪問(wèn)頁(yè)面的總次數(shù)為A，其中有F次訪問(wèn)的頁(yè)面尚未裝入主存，故產(chǎn)生了F次缺頁(yè)中斷。現(xiàn)定義：f＝F/A，則f稱為“缺頁(yè)中斷率”。

操作系統(tǒng)教程課件第107頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理缺頁(yè)中斷率與缺頁(yè)中斷的次數(shù)有關(guān)。因此影響缺頁(yè)中斷率的因素有：（1）分配給作業(yè)的主存塊數(shù)系統(tǒng)分配給作業(yè)的主存塊數(shù)多，則同時(shí)裝入主存的頁(yè)面數(shù)就多，那么缺頁(yè)中斷次數(shù)就少，缺頁(yè)中斷率就低，反之，缺頁(yè)中斷率就高。圖4-40示出了處理器的利用率與多道程序之間的關(guān)系。操作系統(tǒng)教程課件第108頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

圖4-41所示存儲(chǔ)容量與缺頁(yè)中斷次數(shù)的關(guān)系。

圖中可以看出，主存物理塊數(shù)增加到臨界值以后，即使再增加較多的物理塊，進(jìn)程的缺頁(yè)中斷次數(shù)也不再明顯減少。大多數(shù)程序都有這樣一個(gè)特定點(diǎn)，在這個(gè)特定點(diǎn)以后再增加主存容量，缺頁(yè)中斷次數(shù)的減少并不明顯。操作系統(tǒng)教程課件第109頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理程序在運(yùn)行時(shí)對(duì)頁(yè)面的訪問(wèn)是不均勻的，即往往在某段時(shí)間內(nèi)訪問(wèn)僅局限于較少的若干頁(yè)面，如果能夠預(yù)知程序在某段時(shí)間間隔內(nèi)要訪問(wèn)哪些頁(yè)面，并能將它們提前調(diào)入主存，將會(huì)大大地降低缺頁(yè)率，從而減少置換工作，提高CPU的利用率。對(duì)于給定的訪問(wèn)序列選取定長(zhǎng)的時(shí)間間隔(⊿

)，稱為工作集窗口，落在工作集窗口中的頁(yè)面集合稱為工作集。即工作集是指在某段時(shí)間間隔里，進(jìn)程實(shí)際要訪問(wèn)的頁(yè)面的集合。把某進(jìn)程在時(shí)間t的工作集記為w(t,⊿),把變量⊿稱為工作集“窗口尺寸”。操作系統(tǒng)教程課件第110頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

假如有以下頁(yè)面訪問(wèn)序列，窗口尺寸⊿=9：26157775162341234443434441327|-----------||-----------|⊿t1⊿t2則t1時(shí)刻的工作集w(t1)={1,2,5,6,7}；t2時(shí)刻的工作集w(t2)={3,4}操作系統(tǒng)教程課件第111頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

在有些操作系統(tǒng)中，如Windows，虛擬存儲(chǔ)管理程序?yàn)槊恳粋€(gè)進(jìn)程分配固定數(shù)量的物理塊，并且這個(gè)數(shù)目可以進(jìn)行動(dòng)態(tài)的調(diào)整。這個(gè)數(shù)目就是由每個(gè)進(jìn)程的工作集來(lái)確定，并且根據(jù)主存的負(fù)荷和進(jìn)程的缺頁(yè)情況動(dòng)態(tài)地調(diào)整其工作集。當(dāng)每個(gè)工作集都已達(dá)到最小值時(shí)，虛存管理程序跟蹤進(jìn)程的缺頁(yè)數(shù)量，根據(jù)主存中自由頁(yè)面數(shù)量可以適當(dāng)增加其工作集的大小。操作系統(tǒng)教程課件第112頁(yè)（2）頁(yè)面的大小頁(yè)面的大小影響頁(yè)表的長(zhǎng)度、頁(yè)表的檢索時(shí)間、置換頁(yè)面的時(shí)間、可能的頁(yè)內(nèi)零頭的大小等，對(duì)缺頁(yè)中斷的次數(shù)也有一定的影響。如果劃分的頁(yè)面大，一個(gè)作業(yè)的頁(yè)面數(shù)就少，頁(yè)表所占用的主存空間少且查表速度快，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁(yè)中斷的次數(shù)減少，降低了缺頁(yè)中斷率，但是一次換頁(yè)需要的時(shí)間延長(zhǎng)，可能產(chǎn)生的頁(yè)內(nèi)零頭所帶來(lái)的空間浪費(fèi)較大。反之，頁(yè)面小，一次換頁(yè)需要的時(shí)間就短，可能產(chǎn)生的頁(yè)內(nèi)零頭少，空間利用率提高，但是一個(gè)作業(yè)的頁(yè)面數(shù)多，頁(yè)表所占用的主存空間長(zhǎng)且查表速度慢，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁(yè)中斷的次數(shù)增多，增加了缺頁(yè)中斷率。

操作系統(tǒng)教程課件第113頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（3）程序編制方法程序編制的方法不同，對(duì)缺頁(yè)中斷的次數(shù)也有很大影響。缺頁(yè)中斷率與程序的局部化程度密切相關(guān)。一般，希望編制的程序能經(jīng)常集中在幾個(gè)頁(yè)面上進(jìn)行訪問(wèn)，以減少缺頁(yè)中斷次數(shù)，降低缺頁(yè)中斷率。例如，一個(gè)程序要將128×128數(shù)組置初值“0”?，F(xiàn)假設(shè)分配給該程序的主存塊數(shù)只有一塊，頁(yè)面的大小為每頁(yè)128個(gè)字，數(shù)組中每一行元素存放在一頁(yè)中。開(kāi)始第一頁(yè)已經(jīng)調(diào)入主存。操作系統(tǒng)教程課件第114頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理若程序如下，則產(chǎn)生（128*128-1）次缺頁(yè)中斷。intA［128］［128］;for(j=0;j<128;j++)for(i=0;i<128;i++)A［i］［j］=0;

如果重新編制這個(gè)程序：intA［128］［128］;for(i=0;i<128;i++)for(j=0;j<128;j++)A［i］[j］=0;則總共產(chǎn)生（128-1）次缺頁(yè)中斷。操作系統(tǒng)教程課件第115頁(yè)4.7.2請(qǐng)求分頁(yè)式存儲(chǔ)管理

（4）頁(yè)