操作系統(tǒng)計(jì)算機(jī)考研統(tǒng)考專業(yè)課——操作系統(tǒng)湯PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 操作系統(tǒng)計(jì)算機(jī)考研統(tǒng)考專業(yè)課操作系統(tǒng)計(jì)算機(jī)考研統(tǒng)考專業(yè)課操操 作系統(tǒng)湯作系統(tǒng)湯PPT課件課件 4.1 程序的裝入和鏈接程序的裝入和鏈接 圖 4-1 對用戶程序的處理步驟 庫 鏈接 程序 裝入模塊 裝入 程序 編譯程序產(chǎn) 生的目標(biāo)模 塊 第一步第二步第三步 內(nèi)存 第1頁/共83頁 4.1.1 程序的裝入程序的裝入 1. 絕對裝入方式絕對裝入方式(Absolute Loading Mode) 程序中所使用的絕對地址，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對地址時(shí)， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。

2、因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對地址。 第2頁/共83頁 2. 可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 圖 4-2 作業(yè)裝入內(nèi)存時(shí)的情況 LOAD 1,2500 365 LOAD 1,2500 365 10000 11000 12500 15000 5000 2500 1000 0 作業(yè)地址空間 內(nèi)存空間 第3頁/共83頁 3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Denamle Run-time Loading) 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為

3、絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對地址。 第4頁/共83頁 4.1.2 程序的鏈接程序的鏈接 1. 靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking) 圖 4-3 程序鏈接示意圖 模塊 A CALL B； Return； 0 L1 模塊 B CALL C； Return； 0 M1 模塊 C Return； 0 N1 0 模塊 A JSR“L” Return；L1 模塊 B JSR“LM” Return； L LM1 LM LMN1 模塊 C Return； (a) 目標(biāo)模塊(b) 裝入模塊 第5頁/共83頁 在將這幾個(gè)目標(biāo)模

4、塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題： (1) 對相對地址進(jìn)行修改。 (2) 變換外部調(diào)用符號(hào)。 第6頁/共83頁 2. 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Loadtime Dynamic Linking) 裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)： (1)便于修改和更新。 (2) 便于實(shí)現(xiàn)對目標(biāo)模塊的共享。 第7頁/共83頁 3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking) 近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，是對上述在裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去

5、找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 第8頁/共83頁 4.2 連續(xù)分配方式連續(xù)分配方式 4.2.1 單一連續(xù)分配單一連續(xù)分配 這是最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。 第9頁/共83頁 4.2.2 固定分區(qū)分配固定分區(qū)分配 1. 劃分分區(qū)的方法劃分分區(qū)的方法 (

6、1)分區(qū)大小相等， 即使所有的內(nèi)存分區(qū)大小相等。 (2) 分區(qū)大小不等。 第10頁/共83頁 2. 內(nèi)存分配內(nèi)存分配 圖 4-4 固定分區(qū)使用表 第11頁/共83頁 4.2.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) (1)空閑分區(qū)表。 (2) 空閑分區(qū)鏈。 圖 4-5 空閑鏈結(jié)構(gòu) 前 向 指 針 N 2 0 N個(gè)字節(jié)可用 后 向 指 針 N 2 0 第12頁/共83頁 2. 分區(qū)分配算法分區(qū)分配算法 (1)首次適應(yīng)算法FF。 (2) 循環(huán)首次適應(yīng)算法，該算法是由首次適應(yīng)算法演變而成的。 (3) 最佳適應(yīng)算法。 第13頁/共83頁 3. 分區(qū)分配操作分區(qū)分配操

7、作 1) 分配內(nèi)存 從頭開始查表 檢索完否？ m.sizeu.size? m.sizeu.sizesize? 從該分區(qū)中劃出 u.size大小的分區(qū) 將該分區(qū)分配給請求者修 改有關(guān)數(shù)據(jù)結(jié)構(gòu) 返回 返回 繼續(xù)檢索下一個(gè)表項(xiàng) 將該分區(qū)從鏈中移出 Y N N Y Y N 圖 4-6 內(nèi)存分配流程 第14頁/共83頁 2) 回收內(nèi)存 圖 4-7 內(nèi)存回收時(shí)的情況 第15頁/共83頁 4.2.4 可重定位分區(qū)分配可重定位分區(qū)分配 1. 動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入 圖 4-8 緊湊的示意 操作系統(tǒng) 用戶程序1 用戶程序3 10 KB 30 KB 用戶程序6 14 KB 用戶程序9 26 KB 操作系

8、統(tǒng) 用戶程序1 用戶程序3 用戶程序6 用戶程序9 80 KB (a) 緊湊前(b) 緊湊后 第16頁/共83頁 2. 動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位的實(shí)現(xiàn) 圖 4-9 動(dòng)態(tài)重定位示意圖 LOAD1,2500 365 0 100 2500 5000 2500 相對地址 10000 重定位寄存器 LOAD1,2500 365 10000 10100 12500 15000 作業(yè)J 處理機(jī)一側(cè) 存儲(chǔ)器一側(cè) 主存 第17頁/共83頁 3. 動(dòng)態(tài)重定位分區(qū)分配算法動(dòng)態(tài)重定位分區(qū)分配算法 圖 4-10 動(dòng)態(tài)分區(qū)分配算法流程圖 請求分配 u.size分區(qū) 檢索空閑分區(qū)鏈(表) 找到大于u.size 的可用區(qū)否

9、? 按動(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) 否 是 無法分配 返回 否 第18頁/共83頁 4.2.5 對換對換(Swapping) 1. 對換的引入對換的引入 所謂“對換”， 是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。 第19頁/共83頁 2. 對換空間的管理對換空間的管理 為了能對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄

10、外存的使用情況。其形式與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)， 即對換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。 第20頁/共83頁 3. 進(jìn)程的換出與換入進(jìn)程的換出與換入 (1) 進(jìn)程的換出。 每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。 其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。 第21

11、頁/共83頁 (2) 進(jìn)程的換入。 系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。 第22頁/共83頁 4.3 基本分頁存儲(chǔ)管理方式基本分頁存儲(chǔ)管理方式 4.3.1 頁面與頁表頁面與頁表 1. 頁面頁面 1) 頁面和物理塊 分頁存儲(chǔ)管理，是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁加以編號(hào)，從0開始，如第0頁、第1頁等。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁框(frame)， 也同樣為它們加以編號(hào)，如0塊、

12、1塊等等。在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。 第23頁/共83頁 2) 頁面大小 在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間， 有利于提高內(nèi)存利用率，但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存； 此外，還會(huì)降低頁面換進(jìn)換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會(huì)使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的冪，通

13、常為512 B8 KB。 第24頁/共83頁 2. 地址結(jié)構(gòu)地址結(jié)構(gòu) 分頁地址中的地址結(jié)構(gòu)如下： 頁號(hào)P位移量W 31 12110 對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L，則頁號(hào)P和頁內(nèi)地址d可按下式求得： MODLAd L A INTP 第25頁/共83頁 3. 頁表頁表 圖 4-11 頁表的作用 用戶程序 0 頁 1 頁 2 頁 3 頁 4 頁 5 頁 n 頁 頁表 頁號(hào)塊號(hào) 02 13 26 38 49 5 內(nèi)存 0 1 2 3 4 5 6 7 8 9 10 第26頁/共83頁 4.3.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 1. 基本的地址變換機(jī)構(gòu)基

14、本的地址變換機(jī)構(gòu) 圖 4-12 分頁系統(tǒng)的地址變換機(jī)構(gòu) 頁表寄存器 頁表始址頁表長度頁號(hào)(3)頁內(nèi)地址 邏輯地址L 越界中斷 1 塊號(hào) b 頁表 頁號(hào) 0 1 2 物理地址 3 第27頁/共83頁 2. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu) 圖 4-13 具有快表的地址變換機(jī)構(gòu) 頁表寄存器 頁表始址頁表長度頁號(hào)頁內(nèi)地址 邏輯地址L 越界中斷 塊號(hào) b 頁表 頁號(hào)頁號(hào) 輸 入 寄 存 器 塊號(hào) b b 快表 d 物理地址 第28頁/共83頁 4.3.3 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表 現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232264)。在這樣的環(huán)境下，頁表就變得非常大，要占

15、用相當(dāng)大的內(nèi)存空間。例如，對于一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4 KB即212 B，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)1兆個(gè)之多。又因?yàn)槊總€(gè)頁表項(xiàng)占用一個(gè)字節(jié)， 故每個(gè)進(jìn)程僅僅其頁表就要占用4 KB的內(nèi)存空間，而且還要求是連續(xù)的。 可以采用這樣兩個(gè)方法來解決這一問題： 采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題： 只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存， 其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。 第29頁/共83頁 1. 兩級(jí)頁表兩級(jí)頁表(Two-Level Page Table) 邏輯地址結(jié)構(gòu)可描述如下： 第30頁/共83頁 圖 4-14 兩級(jí)頁表結(jié)構(gòu) 1011 1

16、078 0 1 2 1742n 第0頁頁表 1 4 6 0 1 2 1023 第1頁頁表 114 115 0 1 1023 外部頁表 0 1 2 3 4 5 6 7 114 115 1468 第n頁頁表 1468 0 1 2 1023 內(nèi)存空間 第31頁/共83頁 圖 4-15 具有兩級(jí)頁表的地址變換機(jī)構(gòu) 外部頁號(hào) P1P2 外部頁內(nèi)地址頁內(nèi)地址 d邏輯地址 外部頁表寄存器 外部頁表 db 頁表頁表 物理地址 第32頁/共83頁 2. 多級(jí)頁表多級(jí)頁表 對于32位的機(jī)器，采用兩級(jí)頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采用4 KB即212 B，那么還剩下52位， 假定仍按物理塊的大

17、小(212位)來劃分頁表，則將余下的42位用于外層頁號(hào)。此時(shí)在外層頁表中可能有4096 G個(gè)頁表項(xiàng)， 要占用16384 GB的連續(xù)內(nèi)存空間。 必須采用多級(jí)頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁表來映射它們之間的關(guān)系。 對于64位的計(jì)算機(jī)，如果要求它能支持2(=1844744 TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級(jí)頁表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無此必要。 第33頁/共83頁 4.4 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式 4.4.1 分段存儲(chǔ)管理方式的引入分段存儲(chǔ)管理方式的引入 引入分段存儲(chǔ)管理方式， 主要是為了滿足用戶

18、和程序員的下述一系列需要： 1) 方便編程 2) 信息共享 3) 信息保護(hù) 4) 動(dòng)態(tài)增長 5) 動(dòng)態(tài)鏈接 第34頁/共83頁 4.4.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 1. 分段分段 分段地址中的地址具有如下結(jié)構(gòu)： 段號(hào)段內(nèi)地址 31 16 15 0 2. 段表段表 第35頁/共83頁 圖 4-16 利用段表實(shí)現(xiàn)地址映射 作業(yè)空間 (MAIN)0 0 30K (X)1 0 20K (D)2 0 15K (S)3 0 10K 30K 20K 15K 10K 40K 80K 120K 150K 段長基址段號(hào) (MAIN)0 30K (X)1 20K (D)2 15K (S)3 10K 0

19、 40K 80K 120K 150K 段表 內(nèi)存空間 0 1 2 3 第36頁/共83頁 控制寄存器 段表始址段表長度2100 段號(hào)S 越界 1 K 段長 600 段號(hào) 0 1 2 3 6 K 4 K 500 200 8 K 9200 基址 位移量W 8292 8K 8292 8692 主存 物理地址 有效地址 圖 4-17 分段系統(tǒng)的地址變換過程 3. 地址變換機(jī)構(gòu) 第37頁/共83頁 4. 分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 (1) 頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭， 提高內(nèi)存的利用率?；蛘哒f， 分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息

20、的邏輯單位，它含有一組其意義相對完整的信息。 分段的目的是為了能更好地滿足用戶的需要。 第38頁/共83頁 (2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號(hào)和頁內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定， 決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。 (3) 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址； 而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名， 又需給出段內(nèi)地址。 第39頁/共83頁 4.4.3 信息共享信息共享 ed 1

21、 ed 2 ed 40 data 1 data 10 進(jìn)程1 21 22 60 61 70 頁表 ed 1 ed 2 ed 40 data 1 data 10 進(jìn)程2 21 22 60 71 80 ed 1 ed 2 ed 40 data 1 data 10 data 1 data 10 主存 0 21 22 60 61 70 71 80 頁表 圖 4-18 分頁系統(tǒng)中共享editor的示意圖 第40頁/共83頁 圖 4-19 分段系統(tǒng)中共享editor的示意圖 editor 進(jìn)程1 data 1 進(jìn)程2 editor data 2 段表 段長基址 16080 40240 16080 4038

22、0 editor data 1 data 2 80 240 280 380 420 第41頁/共83頁 4.4.4 段頁式存儲(chǔ)管理方式段頁式存儲(chǔ)管理方式 1. 基本原理基本原理 圖 4-20 作業(yè)地址空間和地址結(jié)構(gòu) 0 4K 8K 12K 15K 16K 子程序段 0 4K 8K 數(shù)據(jù)段 0 4K 8K 10K 12K (a) 段號(hào)(S)段內(nèi)頁號(hào)(P)段內(nèi)地址(W) (b) 主程序段 第42頁/共83頁 圖 4-21 利用段表和頁表實(shí)現(xiàn)地址映射 段號(hào)狀態(tài)頁表大小頁表始址 01 11 21 30 41 頁號(hào)狀態(tài)存儲(chǔ)塊# 01 11 21 30 41 操作系統(tǒng) 主存 頁表 段表 段表大小段表始址

23、段表寄存器 第43頁/共83頁 2. 地址變換過程地址變換過程 圖 4-22 段頁式系統(tǒng)中的地址變換機(jī)構(gòu) 段表寄存器 段表始址段表長度段號(hào)S頁號(hào)P 段超長 段表 0 1 2 3 頁內(nèi)地址 頁表 0 1 2 3 b塊號(hào) b塊內(nèi)地址 頁表始址頁表長度 第44頁/共83頁 4.5 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 4.5.1 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入 1. 常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征 (1)一次性。 (2) 駐留性。 第45頁/共83頁 2. 局部性原理局部性原理 早在1968年， Denning.P就曾指出： (1) 程序執(zhí)行時(shí)， 除了少部分的轉(zhuǎn)移和過程調(diào)用指

24、令外， 在大多數(shù)情況下仍是順序執(zhí)行的。 (2) 過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域， 但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。 (3) 程序中存在許多循環(huán)結(jié)構(gòu)， 這些雖然只由少數(shù)指令構(gòu)成， 但是它們將多次執(zhí)行。 (4) 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理， 如對數(shù)組進(jìn)行操作， 它們往往都局限于很小的范圍內(nèi)。 第46頁/共83頁 局限性又表現(xiàn)在下述兩個(gè)方面： (1) 時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。 (2)

25、 空間局限性。一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。 第47頁/共83頁 3. 虛擬存儲(chǔ)器定義虛擬存儲(chǔ)器定義 所謂虛擬存儲(chǔ)器， 是指具有請求調(diào)入功能和置換功能， 能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。可見，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、 中、 小型機(jī)器和微型機(jī)中。 第48頁/共83頁 4.5.2 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法

26、1. 分頁請求系統(tǒng)分頁請求系統(tǒng) (1)硬件支持。 請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)； 缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí) 便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存； 地址變換機(jī)構(gòu)， 它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。 (2) 實(shí)現(xiàn)請求分頁的軟件。 第49頁/共83頁 4.5.3 虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征 1.多次性多次性 2.對換性對換性 3. 虛擬性虛擬性 第50頁/共83頁 4.6 請求分頁存儲(chǔ)管理方式請求分頁存儲(chǔ)管理方式 4.6.1 請求分頁中的硬件支持請求分頁中的硬件支持 1. 頁表機(jī)

27、制頁表機(jī)制 頁號(hào) 物理塊號(hào) 狀態(tài)位P 訪問字段A 修改位M外存地址 第51頁/共83頁 2. 缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu) 圖 4-23 涉及6次缺頁中斷的指令 頁面 B： A： 6 5 4 3 2 1 指令 copy A TO B 第52頁/共83頁 3. 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 缺頁中斷處理 保留CPU現(xiàn)場 從外存中找到缺頁 內(nèi)存滿否？ 選擇一頁換出 該頁被修改否？ 將該頁寫回外存 OS命令CPU從外存讀缺頁 啟動(dòng)I/O硬件 將一頁從外存換入內(nèi)存 修改頁表 否 是 是 否 頁表項(xiàng)在快表中？ CPU檢索快表 訪問頁表 否 頁在內(nèi)存？ 修改訪問位和修改位 形成物理地址 地址變換結(jié)束 否 頁號(hào)頁表

28、長度? 開始 程序請求訪問一頁 產(chǎn)生缺頁中 斷請求調(diào)頁 修改快表 是 越界中斷 是 是 圖 4-24 請求分頁中的地址變換過程 第53頁/共83頁 4.6.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、 功能和尋址方式。對于某些簡單的機(jī)器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。如果該機(jī)器允許間接尋址時(shí)，則

29、至少要求有三個(gè)物理塊。對于某些功能較強(qiáng)的機(jī)器， 其指令長度可能是兩個(gè)或多于兩個(gè)字節(jié)，因而其指令本身有可能跨兩個(gè)頁面，且源地址和目標(biāo)地址所涉及的區(qū)域也都可能跨兩個(gè)頁面。 第54頁/共83頁 2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)， 也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。 1) 固定分配局部置換(Fixed Allocation, Local Replacement) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配

30、局部置換(Variable Allocation, Local Replacemen 第55頁/共83頁 3. 物理塊分配算法物理塊分配算法 1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。 例如，當(dāng)系統(tǒng)中有100個(gè)物理塊，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁，只分配給它20個(gè)塊，這樣，它必然會(huì)有很高的缺頁率；而另一個(gè)進(jìn)程只有10頁，卻有10個(gè)物理塊閑置未用。 第56頁/共83頁 2) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n

31、個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為： 又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有： b應(yīng)該取整，它必須大于最小物理塊數(shù)。 n i i SS 1 m S S b i i 第57頁/共83頁 3) 考慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成， 應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。 第58

32、頁/共83頁 4.6.3 調(diào)頁策略調(diào)頁策略 1. 何時(shí)調(diào)入頁面何時(shí)調(diào)入頁面 1)預(yù)調(diào)頁策略 2) 請求調(diào)頁策略 第59頁/共83頁 2. 從何處調(diào)入頁面從何處調(diào)入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況： (1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前， 便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。 第60頁/共83頁

33、 (2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對換區(qū)，以后需要時(shí)，再從對換區(qū)調(diào)入。 (3) UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此， 某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。 第61頁/共83頁 3. 頁面調(diào)入過程頁

34、面調(diào)入過程 每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改， 則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存， 并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表， 去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。 第6

35、2頁/共83頁 4.7 頁面置換算法頁面置換算法 4.7.1 最佳置換算法和先進(jìn)先出置換算法最佳置換算法和先進(jìn)先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。 第63頁/共83頁 假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊， 并考慮有以下的頁面號(hào)引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0， 1 進(jìn)程運(yùn)行時(shí)， 先將7，0，1三個(gè)頁面裝入內(nèi)存。 以后， 當(dāng)進(jìn)程要訪問

36、頁面2時(shí)， 將會(huì)產(chǎn)生缺頁中斷。此時(shí)OS根據(jù)最佳置換算法， 將選擇頁面7予以淘汰。 引用率 70 77 0 1 7 0 1 2 2 0 1 03 2 0 3 04 2 4 3 230321 2 0 1 2017 7 0 1 01 頁框(物理塊） 2 0 3 圖 4-25 利用最佳頁面置換算法時(shí)的置換圖 第64頁/共83頁 2. 先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法 引用率 70 77 0 1 7 0 1 2 2 0 1 03 2 3 1 04 4 3 0 230321 0 1 3 2017 7 0 2 01 頁框 2 3 0 4 2 0 4 2 3 0 2 3 0 1 2 7 1

37、 2 7 0 1 1 圖 4-26 利用FIFO置換算法時(shí)的置換圖 第65頁/共83頁 4.7.2 最近最久未使用最近最久未使用(LRU)置換算法置換算法 1. LRU(Least Recently Used)置換算法的描述置換算法的描述 圖 4-27 LRU頁面置換算法 引用率 70 77 0 1 7 0 1 2 2 0 1 03 2 0 3 04 4 0 3 230321 1 3 2 2017 1 0 7 01 頁框 4 0 2 4 3 2 0 3 2 1 0 2 第66頁/共83頁 2. LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器寄存器 為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況

38、，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1R0 第67頁/共83頁 圖 4-28 某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況 第68頁/共83頁 2) 棧棧 圖 4-29 用棧保存當(dāng)前使用頁面時(shí)棧的變化情況 4 4 7 4 7 0 7 4 0 7 0 4 7 1 7 0 4 1 0 1 7 4 0 1 0 7 4 1 2 1 0 7 4 2 1 2 0 7 4 1 2 1 0 7 4 2 6 2 1 0 7 6 第69頁/共83頁 4.7.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 圖 4-30 簡單Clock置換算

39、法的流程和示例 入口 查尋指針前進(jìn)一步，指向 下一個(gè)表目 頁面訪問位0? 選擇該頁面淘汰 是 返回 置頁面訪 問位“0” 否 塊號(hào)頁號(hào)訪問位指針 0 1 240 3 421 5 650 711 替換 指針 第70頁/共83頁 2. 改進(jìn)型改進(jìn)型Clock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1)

40、: 最近已被訪問且被修改， 該頁可能再被訪問。 第71頁/共83頁 其執(zhí)行過程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個(gè)頁面作為所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁。 第72頁/共83頁 4.7.4 其它置換算法其它置換算法 1.最少使用(LFU： Least Frequently Used)置換算法 2. 頁面緩沖算法(PBA： Page Buffering Algorithm) 第73頁/共83頁 4.8 請求分段存