計(jì)算機(jī)操作系統(tǒng)第六章課件

主要內(nèi)容基礎(chǔ)知識(shí)請(qǐng)求分頁存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理第6章虛擬存儲(chǔ)器

16.1基礎(chǔ)知識(shí)6.1.1覆蓋技術(shù)

覆蓋技術(shù)，是程序運(yùn)行過程中，在不同時(shí)刻把同一存儲(chǔ)區(qū)分配給不同程序段或數(shù)據(jù)段，實(shí)現(xiàn)存儲(chǔ)區(qū)共享的一種內(nèi)存分配技術(shù)。覆蓋技術(shù)通常與單一連續(xù)區(qū)分配、固定分區(qū)分配和動(dòng)態(tài)分區(qū)分配等存儲(chǔ)管理技術(shù)配合使用。每一個(gè)用戶程序都被分為若干程序段，一部分是經(jīng)常要用的基本部分，作為常駐程序；另一部分不經(jīng)常使用，可以讓它們?cè)谛枰獣r(shí)臨時(shí)裝入。當(dāng)一段在內(nèi)存中的程序運(yùn)行完畢（或者暫時(shí)不運(yùn)行）時(shí)，可以令它們放棄駐留權(quán)，讓另一段程序占用它在內(nèi)存中的位置。2例如，某進(jìn)程的程序段由A、B、C、D、E、F、G和H等8個(gè)程序段組成。它們之間的調(diào)用關(guān)系如圖（a）所示。3操作系統(tǒng)管理下磁盤空間被劃分為兩部分：文件區(qū)和交換區(qū)。二者的區(qū)別主要有3點(diǎn)：存儲(chǔ)方式不同。文件區(qū)中的信息是以文件形式存放的，為了提高空間利用率，一般采取離散存儲(chǔ)方式；而交換區(qū)是按字符流方式存放，多采用連續(xù)存儲(chǔ)形式。

訪問速度不同。文件區(qū)的存儲(chǔ)空間特別大，為了提高檢索效率一般通過建立目錄對(duì)文件實(shí)現(xiàn)訪問，也就是間接地址訪問；而交換區(qū)空間較小，可按外存地址直接訪問，因此速度快。存儲(chǔ)時(shí)間不同。文件區(qū)的存儲(chǔ)適合于較長久的數(shù)據(jù)存儲(chǔ)；而交換區(qū)作為臨時(shí)數(shù)據(jù)的存放處，只存放短期的數(shù)據(jù)。

5二、進(jìn)程調(diào)出進(jìn)程調(diào)出操作，需要選擇一個(gè)近期無運(yùn)行要求的進(jìn)程調(diào)出內(nèi)存。這里，處于阻塞狀態(tài)的進(jìn)程是首選的，其次是就緒狀態(tài)的進(jìn)程，一個(gè)正在共享的程序不在考慮之列。選擇過程中的另一個(gè)參數(shù)是進(jìn)程的優(yōu)先級(jí)或響應(yīng)比。三、進(jìn)程調(diào)入進(jìn)程調(diào)入操作需要選擇一個(gè)具有運(yùn)行條件且最迫切的進(jìn)程，將它調(diào)入。一般來說，選擇過程就是前面所講的“中級(jí)調(diào)度”，選出的進(jìn)程可通過“進(jìn)程激活”裝入內(nèi)存。一般來講，系統(tǒng)選擇的對(duì)象是處于“掛起就緒”狀態(tài)的進(jìn)程，處于“掛起阻塞”狀態(tài)的進(jìn)程不在考慮之列。66.1.3局部性原理

從程序?qū)Σ僮鲾?shù)的訪問來看，一般情況下，一段程序訪問的操作數(shù)也都局部于某個(gè)數(shù)據(jù)塊中。因此在一個(gè)較短的時(shí)間內(nèi)，程序執(zhí)行中對(duì)內(nèi)存地址的訪問往往局限于一個(gè)較小的空間上。1968年，P.Denning提出了一個(gè)著名的“局部性原理”，并通過一幅運(yùn)行圖予以說明（見圖所示）。76.2請(qǐng)求分頁存儲(chǔ)管理

請(qǐng)求分頁（DemandPaging）存儲(chǔ)管理是在普通的分頁管理基礎(chǔ)上，采用了虛擬技術(shù)發(fā)展起來的。由于分頁管理中的頁面長度是固定的，調(diào)出調(diào)入比較容易實(shí)現(xiàn)，因此目前許多操作系統(tǒng)中都支持這種管理方式。

6.2.1地址變換

硬件上除了支持請(qǐng)求分頁管理的內(nèi)存和外存外，還要有相應(yīng)的頁表和地址變換機(jī)制，以及出現(xiàn)缺頁（即某個(gè)需要運(yùn)行的頁面不在內(nèi)存）時(shí)的中斷響應(yīng)機(jī)制等。91．頁表虛擬分頁系統(tǒng)與普通分頁系統(tǒng)的區(qū)別是，進(jìn)程只有一部分頁面進(jìn)入內(nèi)存。因此頁表需要記錄哪些頁面在內(nèi)存，哪些不在內(nèi)存。并且，頁表中還要記錄頁面的外存位置，以便當(dāng)某個(gè)需要運(yùn)行的頁面不在內(nèi)存時(shí)，系統(tǒng)能夠立即找到它，將它裝載進(jìn)來。

2．地址變換機(jī)制當(dāng)調(diào)度一個(gè)進(jìn)程時(shí)，系統(tǒng)將其頁表首址裝入CPU中的頁表控制寄存器。運(yùn)行中用相對(duì)地址的高端部分作為頁號(hào)去檢索頁表，看該頁是否已在內(nèi)存。若已在內(nèi)存就按普通分頁機(jī)制的方式直接生成物理地址，并將訪問標(biāo)志和修改標(biāo)志設(shè)置好。如果該頁不在內(nèi)存，則產(chǎn)生缺頁中斷信號(hào)，通過中斷處理過程將缺頁裝入。103．中斷處理機(jī)制缺頁中斷是指令執(zhí)行過程中產(chǎn)生的中斷，而非（一般的中斷）在一條指令執(zhí)行完成后產(chǎn)生的。當(dāng)CPU執(zhí)行指令希望訪問一個(gè)不在內(nèi)存的頁面時(shí)，將產(chǎn)生缺頁中斷，系統(tǒng)開始運(yùn)行中斷處理程序。此時(shí)指令計(jì)數(shù)器（PC）的值尚未來得及增加就被壓入堆棧，因此壓入的斷點(diǎn)必然是本次被中斷的指令地址，而非下一條指令的地址。11地址變換流程13

虛擬分頁系統(tǒng)中的頁面分配應(yīng)當(dāng)以減少缺頁率為目標(biāo)。實(shí)踐證明，進(jìn)程占用的存儲(chǔ)容量越小，缺頁中斷率就越高。Madnick曾經(jīng)描述了一個(gè)真正的System360系統(tǒng)中的程序缺頁中斷曲線（稱為下降曲線），見圖所示。

14

分配算法有以下3種：

l

平均分配法——系統(tǒng)的可用空間平均分配給所有進(jìn)程，讓它們都占有相等數(shù)量的幀。這樣分配對(duì)短作業(yè)來說是很有利的。而對(duì)于一些較大的進(jìn)程，缺頁率必然居高不下。l

優(yōu)先權(quán)分配法——考慮進(jìn)程的優(yōu)先運(yùn)行權(quán)，給高優(yōu)先的進(jìn)程分配較多的幀，使它的缺頁率相對(duì)少一些。這里，我們可把優(yōu)先權(quán)理解為高響應(yīng)比、高優(yōu)先級(jí)、最短剩余時(shí)間優(yōu)先等。l

比例分配法——這種分配方法比較公平，小進(jìn)程分配小空間，大進(jìn)程分配大空間。當(dāng)可用空間為M個(gè)幀，系統(tǒng)當(dāng)前的進(jìn)程數(shù)為n，每個(gè)進(jìn)程的頁面數(shù)量為si，那么按比例分配法，應(yīng)當(dāng)分配給進(jìn)程i的頁數(shù)pi為：

15

3．LRU（最近最久未使用）算法

被置換的頁面是最長時(shí)間未訪問的頁面。這種算法所依據(jù)的原理是程序執(zhí)行時(shí)所具有的局部性，即那些剛被使用過的頁面可能馬上再次被使用，而那些最久未使用的頁面一般不會(huì)馬上被用到。4．Clock（鐘表算法）算法

這是一個(gè)建立在循環(huán)檢測基礎(chǔ)上的LRU近似算法，試圖以較小的開銷獲得接近LRU的性能。該算法中將被置換的候選幀集合構(gòu)成一個(gè)環(huán)狀緩沖區(qū)，并設(shè)一個(gè)循環(huán)移動(dòng)指針。初始時(shí)，該指針指向緩沖區(qū)的頭部。當(dāng)某頁被選擇置換后，指針將順序指向緩沖區(qū)的下一個(gè)幀。環(huán)狀緩沖區(qū)中的每個(gè)候選幀關(guān)聯(lián)一個(gè)“訪問位”，記作A，當(dāng)某幀的A=0時(shí)，說明該幀最近未被訪問。顯然，一個(gè)剛剛調(diào)入頁面的幀，以及剛剛訪問過的幀，其A=1。175．改進(jìn)的Clock算法

一個(gè)提高Clock算法效率的方法是，為每個(gè)幀增設(shè)一個(gè)關(guān)聯(lián)的“修改位”，記作M。如果M=1表示該幀中的頁面被修改了，置換之前必須寫到外存上。若將訪問情況與修改情況一起考慮，每一幀可處于4種情況之一。l

A=0且M=0：該幀中所存的頁面最近沒有訪問，也沒有修改。l

A=1且M=0：該幀中所存的頁面最近訪問過，但沒有修改。l

A=0且M=1：該幀中所存的頁面最近沒有訪問，但修改了。l

A=1且M=1：該幀中所存的頁面最近訪問過，也修改過。18據(jù)此給出改進(jìn)的Clock算法的處理過程：（1）從指針當(dāng)前位置開始，循環(huán)掃描候選幀，遇到的第1個(gè)A=0且M=0的幀，將該幀中的頁面置換后返回。（2）若循環(huán)一周后沒有找到可置換的幀，則繼續(xù)循環(huán)掃描，遇到的第1個(gè)A=0且M=1的幀，將該幀中的頁面置換后返回。在這個(gè)過程中，每跳過一個(gè)幀就將它的訪問位A設(shè)置為0。（3）若第（2）步仍沒有找到可置換的幀，則重復(fù)（1）和（2）必將能夠找到一個(gè)可置換的幀。19

6．幾種算法的性能比較

置換算法的選擇，將直接影響到內(nèi)存的利用率和系統(tǒng)效率。對(duì)于上述四種算法，計(jì)算機(jī)學(xué)者Baer曾于己于1980年做過一個(gè)實(shí)驗(yàn)，選取的頁面尺寸為256個(gè)字，分別實(shí)驗(yàn)了6、8、10、12、14幀的情況。當(dāng)分配的幀數(shù)比較多時(shí)，四種算法的區(qū)別不太明顯；而當(dāng)分配的比較少時(shí)，它們的區(qū)別就相當(dāng)顯著了。特別是，當(dāng)進(jìn)程只有6個(gè)幀時(shí)，F(xiàn)IFO算法比OPT算法的缺頁次數(shù)提高1倍還多。21實(shí)驗(yàn)結(jié)果如圖所示。其中，橫坐標(biāo)是幀數(shù)，縱坐標(biāo)是缺頁次數(shù)。22

一、頁面調(diào)入策略

在調(diào)頁過程中有兩個(gè)策略：一個(gè)是“隨用隨調(diào)”策略，另一個(gè)是“預(yù)調(diào)頁”策略。“預(yù)調(diào)頁”策略的好處是：一次讀多個(gè)連續(xù)的頁面，可以減少磁頭移動(dòng)的時(shí)間，對(duì)系統(tǒng)效率提高有很大好處。另一個(gè)好處是，當(dāng)發(fā)現(xiàn)缺頁已在內(nèi)存時(shí)，當(dāng)前進(jìn)程不必讓出控制權(quán)，僅僅將缺頁轉(zhuǎn)移到用戶區(qū)，修改頁表后就可繼續(xù)運(yùn)行。6.2.3駐留集和工作集

23

三、工作集

工作集（workingset）的概念是Denning提出來的，對(duì)虛擬存儲(chǔ)器的設(shè)計(jì)產(chǎn)生過重大影響。一個(gè)進(jìn)程的工作集W（t,）表示在時(shí)間t-到t之間進(jìn)程引用的一串頁面；工作集的尺寸記作w（t,），指的是W（t,）中的頁面數(shù)。w（t,）是的單調(diào)函數(shù)，也就是說，時(shí)間段越長，引用的頁面越多，直到接近實(shí)際所需的頁面總數(shù)（實(shí)際操作中，時(shí)間段長度往往用執(zhí)行指令的數(shù)量來度量，而不是實(shí)際經(jīng)歷的時(shí)間）。在進(jìn)程執(zhí)行期間可以容易地確定該進(jìn)程對(duì)存儲(chǔ)空間的需求，也就是它的工作集尺寸。操作系統(tǒng)可以用這種方法決定給誰分配更多的幀，以及哪個(gè)進(jìn)程應(yīng)當(dāng)讓出一些幀來。25下面是按照工作集決定駐留集的策略——工作集策略

(1)

監(jiān)視各進(jìn)程的工作集。(2)

周期性地從一個(gè)進(jìn)程中調(diào)出那些不在它的工作集中的頁，令其釋放部分幀。(3)

當(dāng)一個(gè)進(jìn)程的駐留集包含了它的工作集時(shí)，才可以執(zhí)行該進(jìn)程。否則為進(jìn)程增加新幀或者暫緩調(diào)度該進(jìn)程。26一、抖動(dòng)的產(chǎn)生及應(yīng)對(duì)措施產(chǎn)生抖動(dòng)的原因歸根到底是內(nèi)存駐留的進(jìn)程太多，下圖是處理機(jī)利用率與多道程序度（即進(jìn)程數(shù)量）之間的關(guān)系曲線。

29從圖中可以看出，當(dāng)多道程序度達(dá)到M點(diǎn)時(shí)，處理機(jī)利用率最大。當(dāng)系統(tǒng)處于M點(diǎn)左邊的位置，也就是說駐留在內(nèi)存的進(jìn)程數(shù)量較少時(shí)，處理機(jī)的利用率不高是因?yàn)樨?fù)荷太輕所致。此時(shí)應(yīng)當(dāng)增加內(nèi)存的進(jìn)程數(shù)量方可提高利用率。如果系統(tǒng)處于M點(diǎn)的右邊位置，也就是說內(nèi)存的駐留進(jìn)程較多時(shí)，處理機(jī)的利用率不高是因?yàn)橄到y(tǒng)過載而致。此種情況下，減少內(nèi)存的進(jìn)程數(shù)量是提高處理機(jī)利用率的當(dāng)務(wù)之急。30二、抖動(dòng)預(yù)防下面的方法可以預(yù)防抖動(dòng)的發(fā)生。1．在處理機(jī)調(diào)度中引入工作集策略2．采用局部置換策略防止抖動(dòng)擴(kuò)散3．掛起部分進(jìn)程一般選擇缺頁進(jìn)程、最后被激活的進(jìn)程、最大進(jìn)程駐留集最小的進(jìn)程、剩余執(zhí)行時(shí)間最多的進(jìn)程等。4．L=S準(zhǔn)則這一準(zhǔn)則中，L是產(chǎn)生缺頁的平均時(shí)間，S是系統(tǒng)處理缺頁的平均時(shí)間。理論證明，當(dāng)L=S是，處理機(jī)的利用率最高。該理論也得到實(shí)踐的檢驗(yàn)。316.3請(qǐng)求分段存儲(chǔ)管理

1．段表

為了實(shí)現(xiàn)段的動(dòng)態(tài)管理，我們要為每個(gè)進(jìn)程設(shè)置一個(gè)段表ST，并在ST中設(shè)立一些“控制位”記錄該段的控制信息

322．地址變換33

3．缺段中斷機(jī)制

與缺頁中斷類似，缺段中斷也是指令執(zhí)行過程中產(chǎn)生的中斷，而不是產(chǎn)生在一條指令執(zhí)行完成后。也就是說，進(jìn)程執(zhí)行一條指令產(chǎn)生缺段中斷時(shí)，壓入堆棧的斷點(diǎn)是當(dāng)前指令的地址。當(dāng)缺段被裝入內(nèi)存后，該段變成了“實(shí)段”。進(jìn)程再次恢復(fù)運(yùn)行時(shí)，CPU將重新執(zhí)行這條指令。

4．中斷處理程序當(dāng)?shù)趇#段是一個(gè)缺段，則缺段中斷處理過程為：(1)阻塞進(jìn)程。(2) LengthSTi(長度)。(3)檢索“內(nèi)存分配表”，若存在一個(gè)獨(dú)立的內(nèi)存塊長度Length，則：(3)-1將該內(nèi)存塊分配給進(jìn)程。34(3)-2首址B0；轉(zhuǎn)(6)。(4)若內(nèi)存可用空間總和<Length，則：(4)-1調(diào)用某種置換算法，選擇一個(gè)內(nèi)存中的段。(4)-2若該段被修改過，則，將它寫回外存。(4)-3

修改“內(nèi)存分配表”。(4)-4轉(zhuǎn)(3)。(5)內(nèi)存各進(jìn)程浮動(dòng)，拼接出一個(gè)足夠大的內(nèi)存空間；將該內(nèi)存塊分配給進(jìn)程；首址B0。(6)從外存讀入缺段，存入B0處。(7)STi(B)B0；STi(S)1。(8)修改內(nèi)存分配表。(9)喚醒進(jìn)程。(10)結(jié)束。356.3.2分段共享

1．共享段表SST

為了實(shí)現(xiàn)段的共享，系統(tǒng)設(shè)一個(gè)“共享段表”（SST，SharingSegmentTable），記載各個(gè)共享段的使用情況。任何一個(gè)進(jìn)程調(diào)用共享段時(shí)，系統(tǒng)都將訪問該表。2．共享段的分配

共享段的空間分配與一般段的分配有所不同，共享段在內(nèi)存中只駐留一個(gè)備份，所有共享該段的進(jìn)程都通過自己的邏輯段號(hào)映射到該共享段上。36分配過程為：（1）當(dāng)系統(tǒng)為一個(gè)進(jìn)程分配地址空間并創(chuàng)建段表ST時(shí)，若發(fā)現(xiàn)該進(jìn)程調(diào)用了某個(gè)共享段，比如說，Sqrt段，系統(tǒng)檢查內(nèi)存中的共享段表SST。（2）若SST中已包含Sqrt段，則系統(tǒng)就將Sqrt段的內(nèi)存基地址拷貝到進(jìn)程的ST中，并將SST中關(guān)于Sqrt段的共享計(jì)數(shù)字段加1，轉(zhuǎn)第（4）步。（3）若SST中未包含Sqrt段，說明該進(jìn)程是第一個(gè)使用該共享段Sqrt的進(jìn)程。系統(tǒng)需要為該共享段分配存儲(chǔ)空間，將該段加載到內(nèi)存中。此外，還要在SST中增加一個(gè)表項(xiàng)，將共享段的信息填入，并將共享計(jì)數(shù)字段加1。（4）將進(jìn)程的信息填入SST的相關(guān)字段中。3