計算機(jī)操作系統(tǒng)存儲器管理復(fù)習(xí)資料

1、第四章 存儲器管理第一部分 教材習(xí)題（P159）15、在具有快表的段頁式存儲管理方式中，如何實現(xiàn)地址變換？答：在段頁式系統(tǒng)中，為了便于實現(xiàn)地址變換，須配置一個段表寄存器，其中存放段表始址和段長TL。進(jìn)行地址變換時，首先利用段號S，將它與段長TL進(jìn)行比較。若S<TL，表示未越界，利用段表始址和段號來求出該段所對應(yīng)的段表項在段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)頁的頁表項位置，從中讀出該頁所在的物理塊號b，再利用塊號b和頁內(nèi)地址來構(gòu)成物理地址。在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，須三次訪問內(nèi)存。第一次訪問內(nèi)存中的段表，從中取得頁表始址；第二次訪問內(nèi)存

2、中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或數(shù)據(jù)。顯然，這使訪問內(nèi)存的次數(shù)增加了近兩倍。為了提高執(zhí)行速度，在地址變換機(jī)構(gòu)中增設(shè)一個高速緩沖寄存器。每次訪問它時，都須同時利用段號和頁號去檢索高速緩存，若找到匹配的表項，便可從中得到相應(yīng)頁的物理塊號，用來與頁內(nèi)地址一起形成物理地址；若未找到匹配表項，則仍須再三次訪問內(nèi)存。19、虛擬存儲器有哪些特征？其中最本質(zhì)的特征是什么？答：虛擬存儲器有以下特征：多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，亦即在作業(yè)運(yùn)行時沒有必要將其全部裝入，只需將當(dāng)前要運(yùn)行的那部分程序

3、和數(shù)據(jù)裝入內(nèi)存即可；以后每當(dāng)要運(yùn)行到尚未調(diào)入的那部分程序時，再將它調(diào)入。多次性是虛擬存儲器最重要的特征，任何其他的存儲器管理方式都不具有這一特征。因此，認(rèn)為虛擬存儲器是具有多次性特征的存儲器系統(tǒng)。對換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出，也即，在進(jìn)程運(yùn)行期間，允許將那些暫不使用的程序和數(shù)據(jù)，從內(nèi)存調(diào)至外存的對換區(qū)（換出），待以后需要時再將它們從外存調(diào)至內(nèi)存（換進(jìn)）；甚至還允許將暫不運(yùn)行的進(jìn)程調(diào)至外存，待它們重又具備運(yùn)行條件時再調(diào)入內(nèi)存。換進(jìn)和換出能有效地提高內(nèi)存利用率?？梢?，虛擬存儲器具有對換性特征。虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實際內(nèi)存容量。這是虛擬存儲器

4、所表現(xiàn)出來的最重要特征，也是實現(xiàn)虛擬存儲器的最重要的目標(biāo)。虛擬性是以多次性和對換性為基礎(chǔ)的，多次性和對換性又必須建立在離散分配的基礎(chǔ)上。所以最本質(zhì)特征應(yīng)該是離散性。22、在請求分頁系統(tǒng)中，頁表應(yīng)包括哪些數(shù)據(jù)項？每項的作用是什么？答：在請求分頁系統(tǒng)中的每一個頁表項如下：頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址 l 狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考。l 訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁已有多長時間沒有被訪問，供選擇換出頁面時參考。l 修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過，由于內(nèi)存中的每一頁都在外存上保留一分副本，因此，若沒有被修改，在置

5、換該頁時就不需再將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)，若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。簡言之，M位供置換頁面時參考。l 外存地址，用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時參考。26、在一個請求分頁系統(tǒng)中，采用 LRU 、FIFO頁面置換算法時，如果一個作業(yè)的頁面走向為1、3、2、1、1、3、5、1、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。答：LRU133213513213221351321132113513215缺缺缺缺缺缺當(dāng)物理塊數(shù)為3時，

6、缺頁次數(shù)為6，缺頁率為6/12。 222553133213513213221351321132113513215缺缺缺缺當(dāng)物理塊數(shù)為4時，缺頁次數(shù)為4，缺頁率為4/12。FIFO 111132511313333251332132222513225缺缺缺缺缺缺缺缺當(dāng)物理塊數(shù)為3時，缺頁次數(shù)為8，缺頁率為8/12。111111111133333313333222222132222555555缺缺缺缺當(dāng)物理塊數(shù)為4時,缺頁次數(shù)為4，缺頁率為4/12。1、為什么要配置層次式存儲器？2、可采用哪幾種方式將程序裝入內(nèi)存？它們分別適用于何種場合？答: 絕對裝入方式，在編譯時，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位

7、置，那么編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼?？芍囟ㄎ谎b入方式，在多道程序環(huán)境下，由于編譯程序不能預(yù)知所編譯的目標(biāo)模塊在內(nèi)存的什么位置，因此目標(biāo)模塊的起始地址通常從0開始，程序中所有其他地址都相對于起始地址計算。動態(tài)運(yùn)行時裝入方式，程序在裝入內(nèi)存中后，允許程序在運(yùn)行中在內(nèi)存中移動位置。3、何謂靜態(tài)鏈接？何謂裝入時動態(tài)鏈接和運(yùn)行時的動態(tài)鏈接？答: 靜態(tài)鏈接:在程序運(yùn)行之前,先將各目標(biāo)模塊及它們所需的庫函數(shù),鏈接成一個完整的裝入模塊,以后不再拆開。這種事先進(jìn)行鏈接的方式叫靜態(tài)鏈接方式。裝入時動態(tài)鏈接:用戶源程序編譯后所得的一組目標(biāo)模塊,在裝入內(nèi)存時,采用邊裝入邊鏈接的鏈接方式。運(yùn)行時的動態(tài)鏈接:對某些

8、目標(biāo)模塊的鏈接,是在程序執(zhí)行中需要該目標(biāo)模塊時,才對它進(jìn)行的鏈接。4、在進(jìn)行程序鏈接時，應(yīng)完成哪些工作？答：在進(jìn)行程序鏈接時，應(yīng)完成：對相對地址的修改變換外部調(diào)用符號5、在動態(tài)分區(qū)分配方式中，應(yīng)如何將各空閑分區(qū)鏈接成空閑分區(qū)鏈？答：為了現(xiàn)實對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個雙向的鏈，如圖所示（空閑鏈結(jié)構(gòu)），為了檢索方便，在分區(qū)尾部重復(fù)設(shè)置狀態(tài)位的分區(qū)大小表目。當(dāng)分區(qū)被分配出去以后，把狀態(tài)位由“0”改為“1”，此時，前、后向指針已沒有意義。前向指針N+20后向指針N+2

9、0N個字節(jié)可用6、為什么要引入動態(tài)重定位？如何實現(xiàn)？答：在連續(xù)分配方式中，必須把一個系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。如果在系統(tǒng)中只有若干個小的分區(qū)，即使它們?nèi)萘康目偤痛笥谝b入的程序，但由于這些分區(qū)不相鄰接，也無法把該程序裝入內(nèi)存。若想把作業(yè)裝入，可采用的一種方法是：將內(nèi)存中的所有作業(yè)進(jìn)行移動，使它們?nèi)枷噜徑?，這樣，即可把原來分散的多個小分區(qū)拼接成一個大分區(qū)，這時就可把作業(yè)裝入該區(qū)。這種通過移動內(nèi)存中作業(yè)的位置，以把原來多全分散的小分區(qū)拼接成一個大分區(qū)的方法方法，稱為“拼接”或“緊湊”見圖所示。由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化，此時若不對程序和數(shù)據(jù)的地址加以修改（變換

10、），則程序必將無法執(zhí)行。為此，在每次“緊湊”后，都必須對移動了的程序或數(shù)據(jù)進(jìn)行重定位，這也就引入的動態(tài)重定位。操作系統(tǒng)用戶程序110KB用戶程序330KB用戶程序614KB用戶程序926KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序680KB（A）緊湊前（B）緊湊后7、在采用首次適應(yīng)算法回收內(nèi)存時，可能出現(xiàn)哪幾種情況？應(yīng)怎樣處理這些情況？答: 當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四種情況之一：l 回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰，見圖（a）。此時應(yīng)將回收區(qū)與插入點的前一區(qū)合并，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)F1的

11、大小。l 回收區(qū)與插入點的后空閑分區(qū)F2相鄰接，見圖（b）。此時也可瘵兩分區(qū)合并，形成拳的空閑分區(qū)，但用回收的首址作為新空閑分區(qū)的首址，大小為兩者之和。l 回收區(qū)同時與插入點的前、后兩個分區(qū)相鄰接，見圖(C)。此時將三個分區(qū)合并使用F1的首址，取消F2的表項，大小為三者之和。l 回收區(qū)既不與F1相鄰接，也不與F2相鄰接。這時應(yīng)為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。F1回收區(qū)F2回收區(qū)F1回收區(qū)F2ABC8、令buddyk(x)表示大小為2k、地址為x的塊的伙伴系統(tǒng)地址，試寫出buddyk(x)的通用表達(dá)式。9、分區(qū)存取管理中常用哪些分配策略？比

12、較它們的優(yōu)缺點。10、在系統(tǒng)中引入對換后可帶來哪些好處？答：引入對換后，可以解決由于內(nèi)存不足而無法同時容納多個用戶程序的問題，并可以進(jìn)一步提高內(nèi)存的利用率。11、為實現(xiàn)對換，系統(tǒng)應(yīng)具備哪幾方面的功能？答:為了現(xiàn)實進(jìn)程的對換，系統(tǒng)必須能實現(xiàn)三方面的功能：對換空間的主管理，進(jìn)程的換出，以及進(jìn)程的換入。12、在以進(jìn)程為單位進(jìn)行對換時，每次是否都將整個進(jìn)程換出？為什么？答：并非要將整個進(jìn)程換出，換出程序（進(jìn)程）要換出某個進(jìn)程時，只能換出那些非共享的程序和數(shù)據(jù)段。對于共享的程序段和數(shù)據(jù)段，則須先對每個段的引用計數(shù)執(zhí)行減1操作。若其結(jié)果值不為0時，表示仍有進(jìn)程需要用它，因而不能換出；否則表示該程序段或數(shù)據(jù)

13、段，已不被其他進(jìn)程需要，于是可以將它們換出。13、為實現(xiàn)分頁存儲管理，需要哪些硬件支持？答：為了實現(xiàn)請求分頁，系統(tǒng)必須提供一定的硬件支持，除了需要一臺具有一定容量的內(nèi)存及外存的計算機(jī)以外，還需要有頁表機(jī)制、缺頁中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。l 頁表機(jī)制：作用是將用戶地址空間是的邏輯地址變換為內(nèi)存空間中的物理地址。l 缺頁中斷機(jī)構(gòu)：在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。缺頁中斷作為中斷，它們同樣需要經(jīng)歷諸如保護(hù)CPU環(huán)境，分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理、恢復(fù)CPU環(huán)境等幾個步驟。l 地址變換機(jī)構(gòu)：請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)，是在分

14、頁系統(tǒng)地址機(jī)構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器而增加了某種功能而形成的，如產(chǎn)生和處理缺頁中民，以及從內(nèi)存中換出一頁的功能等。在進(jìn)行地址變換時，首先去檢索快表，試圖從中找出所要訪問的頁，若找到，便修改頁表中的訪問位，對于寫指令還須將修改位置成“1”，然后利用頁表中給出的物理號和頁內(nèi)地址，形成頁內(nèi)物理地址。地址變換過程到此結(jié)束。14、較詳細(xì)地說明引入分段存儲管理是為了滿足用戶哪幾方面的需要。答：引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：l 方便編程：通常，用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干個段，每個段都是從0開始編址，并有自己的名字和長度。因此，在訪問的邏輯地址是由段名(段

15、號)和段內(nèi)偏移量(段內(nèi)地址)決定的。l 信息共享：要實現(xiàn)對程序和數(shù)據(jù)的共享時，是發(fā)信息的邏輯單位為基礎(chǔ)的。比如，共享某個例程和函數(shù)。分頁系統(tǒng)中的“頁”只是存放信息的物理單位(塊)，并無完整的意義，不便于實現(xiàn)共享，然而段卻是信息的邏輯單位，上此可知，為了現(xiàn)實段的共享，希望存儲器管理能與用戶程序分段的組織方式相適應(yīng)。l 信息保護(hù)：信息保護(hù)同樣是對信息的邏輯單位進(jìn)程保護(hù)，分段管理方式能更有效和方便地實現(xiàn)信息保護(hù)功能。l 動態(tài)增長：在實際應(yīng)用中，往往有些段，特別是數(shù)據(jù)段，在使用過程中會不斷地增長，而事先又無法確切知道數(shù)據(jù)段會增長到多大。前述的其它幾種存儲管理試，都難以應(yīng)付這種動態(tài)增長的情況，而分段存儲

16、管理方式卻能較好的解決這一問題。l 動態(tài)鏈接：動態(tài)鏈接是指在作業(yè)運(yùn)行之前，并不把目標(biāo)程序段鏈接起來。要運(yùn)行時，先將主程序所對應(yīng)的目標(biāo)程序裝入內(nèi)存并啟動運(yùn)行，當(dāng)運(yùn)行過程中又需要調(diào)用某段時，才將該段(目標(biāo)程序)調(diào)入內(nèi)存，并進(jìn)程鏈接，可見動態(tài)鏈接也要求以段作為管理的單位。16、為什么說分段系統(tǒng)比分頁系統(tǒng)更易于實現(xiàn)信息的共享和保護(hù)？答：分段系統(tǒng)允許若干個進(jìn)程共享一個或多個分段，對段的保護(hù)也十分簡單易行。在分頁系統(tǒng)中，雖然也能實現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)來的方便，可以通過一個例子來說明這個問題：例如：有一個多用戶系統(tǒng)，可同時接納40個用戶，它們都執(zhí)行一個文本編輯程序，如果文本編輯程。序有160

17、KB的代碼和加外40KB的數(shù)據(jù)區(qū)，由總共需有8MB的內(nèi)存空間來個用戶。如果160KB的代碼是可重入的，則無論是在分頁系統(tǒng)還是在分段系統(tǒng)中，該代碼都能被共享，在內(nèi)存中只需保留一份文本編輯程序的副本，此時所需要的內(nèi)存空間僅為1760KB(160+40*40)，假定每個頁面的大小為4KB，那么160KB的代碼將占用40個頁面，數(shù)據(jù)區(qū)占10個頁面。為實現(xiàn)代碼的共享，應(yīng)在每個進(jìn)程的頁表中都建立40個頁表項，它們的物理塊號都是21#60#。在每個進(jìn)程的頁表中，還須為自己的數(shù)據(jù)區(qū)建立頁表項，它們的物理塊號分別是61#70#，71#80#，81#90#，等等，如A圖為分頁系統(tǒng)中共享editor的示意圖。在分段

18、系統(tǒng)中，實現(xiàn)共享則容易得多，只需要在每個進(jìn)程的段中為文本編輯程序設(shè)置一個段表項。圖B是分段系統(tǒng)中共享editor的示意圖。進(jìn)程1頁表進(jìn)程2頁表Ed1Ed2Ed40Data1Data10Ed1Ed2Ed40Data1Data1021226071802122607180主存Ed40Data1Data10Data1Data10Ed2Ed1021226061707180A圖editorData 1進(jìn)程1editorData 2進(jìn)程2段長16040基址8024段表1604080380editorData 1Data 280240280380420B圖17、分頁和分段存儲管理有何區(qū)別？答：分頁和分段系統(tǒng)有

19、許多相似之處。比如，兩者都采用離散分配方式，且都要通過地址映射機(jī)構(gòu)來實現(xiàn)地址變換。但在概念上兩者完全不同，主要表現(xiàn)在下述的三個方面：l 頁是信息的物理單位，分頁是為離散實現(xiàn)分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段由是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。l 頁的大小固定全由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分產(chǎn)號和怘內(nèi)的地址兩部分，是由機(jī)器硬件實現(xiàn)的，因而在 只能有一種大小的頁面原則是段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編時，根據(jù)信息的性質(zhì)來劃分。l 分

20、頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識一個地址時，即需給出段名，又需給出段內(nèi)地址。分頁分段信息單位物理單位邏輯單位信息完整性離散分配方式意義相對完整需要系統(tǒng)管理的需要用戶的需要頁的大小固定，由系統(tǒng)決定不固定，由用戶決定地址空間一維二維試述分頁系統(tǒng)和分段系統(tǒng)的主要區(qū)別。解：分頁和分段有許多相似之處，比如兩者都不要求作業(yè)連續(xù)存放。但在概念上兩者完全不同，主要表現(xiàn)在以下幾個方面：（1）頁是信息的物理單位，分頁是為了實現(xiàn)非連續(xù)分配，以便解決內(nèi)存碎片問題，或者說分頁是由于系統(tǒng)管理的需要。段是信息的邏輯單位，它

21、含有一組意義相對完整的信息，分段的目的是為了更好地實現(xiàn)共享，滿足用戶的需要。（2）頁的大小固定且由系統(tǒng)確定，將邏輯地址劃分為頁號和頁內(nèi)地址是由機(jī)器硬件實現(xiàn)的。而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時根據(jù)信息的性質(zhì)來劃分。（3）分頁的作業(yè)地址空間是一維的。分段的地址空間是二維的。18、試全面比較連續(xù)分配和離散分配方式?答：連續(xù)分配是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。又可進(jìn)一步分為單一連續(xù)分配、固定分區(qū)分配、動態(tài)分區(qū)分配和動態(tài)重定位分區(qū)分配四種方式。連續(xù)分區(qū)方式可使一個進(jìn)程分得一個連續(xù)的內(nèi)存空間，這樣一來有利于程序的執(zhí)行，但同時又會產(chǎn)生很多的碎片，浪費(fèi)大

22、量的系統(tǒng)資源。離散分區(qū)是采用段式或頁式或段頁式的分配方式將一個進(jìn)程裝入一些離散的內(nèi)存中，這樣有利于內(nèi)存的利用，并且可以方便程序員在更大的空間進(jìn)行編程工作。20、實現(xiàn)虛擬存儲器需要哪些硬件支持？答：主要的硬件支持有：l 請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)。l 缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面還沒有調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存。l 地址變換機(jī)構(gòu)，它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。21、實現(xiàn)虛擬存儲器需要哪幾個關(guān)鍵技術(shù)？答：為實現(xiàn)虛擬存儲器，首先需要擴(kuò)充頁表，增加狀態(tài)位以指出所需頁是否在內(nèi)存，增加外存

23、始址以便調(diào)入頁面，增加引用位以供置換算法用，增加修改位使得換出時減少寫盤次數(shù)。另外，還要使用兩種關(guān)鍵技術(shù)：（1）請求調(diào)頁技術(shù)。指及時將進(jìn)程所要訪問的、不在內(nèi)存中的頁調(diào)入內(nèi)存。該功能是由硬件（缺頁中斷機(jī)構(gòu)發(fā)現(xiàn)缺頁）和軟件（將所需頁調(diào)入內(nèi)存）配合實現(xiàn)的。（2）置換頁技術(shù)。當(dāng)內(nèi)存中已無足夠空間用來裝入即將調(diào)入的頁時，為了保證進(jìn)程能繼續(xù)運(yùn)行，系統(tǒng)必須換出內(nèi)存中的部分頁，以騰出足夠的空間。具體的置換操作并不復(fù)雜，其關(guān)鍵是應(yīng)將哪些頁換出，即采用什么置換算法。23、在請求分頁系統(tǒng)中，應(yīng)從何處將所需頁面調(diào)入內(nèi)存？答：在請求分頁系統(tǒng)中將頁面調(diào)入內(nèi)存大致分為三種：系統(tǒng)擁有足夠的對換空間，這時可以全部從對換區(qū)調(diào)入所

24、需頁面，以提高調(diào)頁速度。系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時就不必?fù)Q出到對換區(qū)，以后再調(diào)入，仍從文件區(qū)直接調(diào)入。對于可能被修改的部分，換出時須換到對換區(qū)，以后需要時就須從對換區(qū)調(diào)入。對UNIX方式，由于系統(tǒng)中允許頁面共享，某進(jìn)程所請求的頁面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時就無須再從對換區(qū)調(diào)入。24、在請求分頁系統(tǒng)中，常采用哪幾種頁面置換算法？25、在請求分頁系統(tǒng)中，通常采用哪種頁面分配方式？為什么？27、實現(xiàn)LRU算法所需的硬件支持是什么？答：LRU算法須要有以下兩類硬件支持：l 寄存器：為了記錄某進(jìn)程在內(nèi)存中各頁的使用說明，須為每個在內(nèi)存

25、中的頁面配置一個移位寄存器，可表示為： R=Rn-1Rn-2Rn-3R2R1R0,當(dāng)進(jìn)程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置變成1，此時，定時信號將每隔一定時間將寄存器右移一位。l 棧：可利用一個特殊的棧來保存當(dāng)前使用的各個頁面號，每當(dāng)進(jìn)程訪問某頁面時，便將該頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最久沒有使用的頁面號，假定現(xiàn)有一進(jìn)程所訪問的頁面號序列為：4、7、0、7、1、0、1、2、1、2、6隨著進(jìn)程的訪問，棧中頁面號的變化情況如下圖所示，在訪問頁面6時發(fā)生了缺頁，此時頁面4是最近最久沒有被訪問的頁，應(yīng)將它置換出去。4477400747704

26、11704001741107422107411207422107466210728、試說明改進(jìn)型Clock置換算法的基本原理。29、說明請求分頁系統(tǒng)中的缺頁中斷處理過程。30、如何實現(xiàn)分段共享？答：為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項。表項中記錄了共享段的段號、段長、內(nèi)存始址、存在位等信息，并記錄了人共享此分段的每個進(jìn)程的情況。共享段表如下圖所示。其中的各項說明如下：l 共享進(jìn)程計數(shù)count。非共享段僅為一個進(jìn)程所需要。當(dāng)進(jìn)程不再需要該段時，可立即釋放該段，并由系統(tǒng)回收該段所有占用的空間。而共享段是為多個進(jìn)程所需要的，當(dāng)某進(jìn)程不再需要而釋放它時，

27、系統(tǒng)并不回收該段所占內(nèi)存，僅當(dāng)所有共享該段的進(jìn)程全部都不再需要它時，才由系統(tǒng)回收該段所占內(nèi)存區(qū)。為了記錄有多少個進(jìn)程需要共享該分段，特設(shè)置了一個整型變量count.l 存取控制字段。對于一個共享段，應(yīng)給不同的進(jìn)程以不同的存取權(quán)限。例如，對于文件主，通常允許他讀和寫，而對其它進(jìn)程，則可能只允許讀，甚至只允許執(zhí)行。l 段號。對于一個共享段，不同的進(jìn)程可以各用不同的段號去共享該段。共享段表段名 段長 內(nèi)存始址 狀態(tài)外存始址 狀態(tài)進(jìn)程名 進(jìn)程號段號存取控制 共享進(jìn)程計數(shù)count 第二部分 分析計算題1、在一請求分頁系統(tǒng)中，采用LRU頁面置換算法時，假如一個作業(yè)的頁面走向為1、3、1、1、3、5、1、

28、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別分3和4時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得到的結(jié)果。M=3時：11133311311133135535115133132232112155缺 缺 缺 缺 缺 缺頁率為：5/11=71.43%M=4時：11133311311133531331511535315255213153212 缺 缺 缺 缺缺頁率為：4/11=36.37%比較：利用此算法的好處為，當(dāng)分配的物理塊數(shù)足夠多時，可以將缺頁率降低到每頁只一次調(diào)入(如M=4的情況)。顯然M=4時的缺頁率小于M=3時的缺頁率，但就內(nèi)存的使用情況來就，M=3時的內(nèi)存使用少于M=4時

29、的內(nèi)存，由此可見利降低缺頁率是物理塊為犧牲的。2、表4.2給出了某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略。現(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？分析及相關(guān)知識首次適應(yīng)算法要求空閑分區(qū)按地址遞增的次序排列，在進(jìn)行內(nèi)存分配時，總是從空閑分區(qū)表的首部開始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表中。最佳適應(yīng)算法要求空閑分區(qū)按大小遞增的次序排列，在進(jìn)行內(nèi)存分配時，總是從空閑分區(qū)表首開

30、始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑區(qū)仍留在空閑區(qū)表中。表4.2 空閑分區(qū)表分區(qū)號大小起始地址（遞增）132K100K210K150K35K200K4218K220K596K530K解：（1） 若采用最佳適應(yīng)算法，在申請96K存儲區(qū)時，選中的是5號分區(qū)，5號分區(qū)大小與申請空間大小一致，應(yīng)從空閑分區(qū)表中刪去該表項；接著申請20K時，選中1號分區(qū)，分配后1號分區(qū)還剩下12K；最后申請200K，選中4號分區(qū)，分配后剩下18K。顯然采用最佳適應(yīng)算法進(jìn)行內(nèi)存分配，可以滿足該作業(yè)序列的需求。為作業(yè)序列分配了內(nèi)存空間后，空閑

31、分區(qū)表如表4.3（a）所示。（2） 若采用首次適應(yīng)算法，在申請96K存儲區(qū)時，選中的是4號分區(qū)，進(jìn)行分配后4號分區(qū)還剩下122K；接著申請20K時，選中1號分區(qū)，分配后剩下12K；最后申請200K，現(xiàn)有的五個分區(qū)都無法滿足要求，該作業(yè)等待。顯然采用首次適應(yīng)算法進(jìn)行內(nèi)存分配，無法滿足該作業(yè)序列的需求。這時的空閑分區(qū)表如表4.3（b）所示。表4.3空閑分區(qū)表（a）分區(qū)號大小起始地址112K100K(120?)210K150K35K200K418K220K(420?)（b）分區(qū)號大小起始地址112K100K210K150K35K200K4122K220K596K530K3、某操作系統(tǒng)采用可變分區(qū)分配

32、存儲管理方法，用戶區(qū)為512K且始址為0，用空閑分區(qū)表管理空閑分區(qū)。若分配時采用分配空閑區(qū)低地址部分的方案，且初始時用戶區(qū)的512K空間空閑，對下述申請序列：申請300K，申請100K，釋放300K，申請150K，申請30K，申請40K，申請60K，釋放30K回答下列問題：（1） 采用首次適應(yīng)算法，空閑分區(qū)中有哪些空塊（給出始址、大?。?？（2） 采用最佳適應(yīng)算法，空閑分區(qū)中有哪些空塊（給出始址、大?。浚?） 如再申請100K，針對（1）和（2）各有什么結(jié)果？分析及相關(guān)知識為描述方便起見，本題用“（分區(qū)首址，分區(qū)長度）”的形式描述系統(tǒng)中的分區(qū)。由題中所給條件可知，最初系統(tǒng)中只有一個空閑區(qū)，大小

33、為512K，始址為0，即（0，512K）。操作已分配空間空閑塊初始無（0，512K）申請300K（0，300K）（300K，212K）申請100K（0，300K）（300K，100K）（400K，112K）釋放300K（300K，100K）（0，300K）（400K，112K）申請150K（0，150K）（300K，100K）（150K，150K）（400K，112K）申請30K（0，150K）（150K，30K）（300K，100K）（180K，120K）（400K，112K）申請40K（0，150K）（150K，30K）（180K，40K）（300K，100K）（220K，80K）（400

34、K，112K）申請60K（0，150K）（150K，30K）（180K，40K）（220K，60K）（300K，100K）（280K，20K）（400K，112K）釋放30K（0，150K）（180K，40K）（220K，60K）（300K，100K）（150K，30K）（280K，20K）（400K，112K）采用最佳適應(yīng)算法時的操作流程：操作已分配空間空閑塊初始無（0，512K）申請300K（0，300K）（300K，212K）申請100K（0，300K）（300K，100K）（400K，112K）釋放300K（300K，100K）（0，300K）（400K，112K）申請150K（0，1

35、50K）（300K，100K）（150K，150K）（400K，112K）申請30K（0，150K）（300K，100K）（400K，30K）（150K，150K）（430K，82K）申請40K（0，150K）（300K，100K）（400K，30K）（430K，40K）（150K，150K）（470K，42K）申請60K（0，150K）（150K，60K）（300K，100K）（400K，30K）（430K，40K）（210K，90K）（470K，42K）釋放30K（0，150K）（150K，60K）（300K，100K）（430K，40K）（210K，90K）（400K，30K）（470K

36、，42K）解：（1） 采用首次適應(yīng)算法，在完成了題目所給的系列申請及釋放內(nèi)存操作后，內(nèi)存分配情況如圖5.11所示（用陰影表示空閑空間），空閑分區(qū)表如下所示。400K180K280K150K作業(yè)40K作業(yè)60K作業(yè)100K作業(yè)0150K220K300K512K-1圖4.11采用首次適應(yīng)算法的內(nèi)存分配情況分區(qū)大小起始地址01230K20K112150K280K400K（2） 采用最佳適應(yīng)算法，完成了題目所給的系列申請及釋放內(nèi)存操作后，內(nèi)存分配情況如圖4.12所示（用陰影表示空閑空間），空閑分區(qū)表如下：150K作業(yè)60K作業(yè)100K作業(yè)40K作業(yè)0150K210K300K400K430K470K51

37、2K-1圖4.12 采用最佳適應(yīng)算法的內(nèi)存分配情況分區(qū)大小起始地址01230K42K90K400K470K210K如再申請100K空間，由上述結(jié)果可知，采用首次適應(yīng)算法后剩下的空閑分區(qū)能滿足這一申請要求；而采用最佳適應(yīng)算法后剩下的空閑分區(qū)不能滿足這一申請要求。4、設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個存儲塊，試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？分析及相關(guān)知識在頁式存儲管理中，用戶作業(yè)的地址空間被劃分成若干大小相等的區(qū)域，稱為頁。相應(yīng)地，將主存的存儲空間也分成與頁大小相等的區(qū)域，稱為塊。在為作業(yè)分配存儲空間時，總是以塊為單位來分配，

38、可以將作業(yè)中的任意一頁放到主存的任意一塊中。頁式存儲管理系統(tǒng)中的邏輯地址結(jié)構(gòu)為：頁號P頁內(nèi)位移W它包含兩部分，前一部分為頁號P，后一部分為頁內(nèi)位移W。解：（1） 本題中，每頁2048字節(jié)，所以頁內(nèi)位移部分地址需要占據(jù)11個二進(jìn)制位；邏輯地址空間最大為16頁，所以頁號部分地址需要占據(jù)4個二進(jìn)制位。故邏輯地址至少應(yīng)為15位。（2） 由于內(nèi)存共有8個存儲塊，在頁式存儲管理系統(tǒng)中，存儲塊大小與頁面的大小相等，因此內(nèi)存空間為8頁*2048字節(jié)=16K。5、有一頁式系統(tǒng)，其頁表存放在主存中。（4） 如果對主存的一次存取需要1.5微秒，試問實現(xiàn)一次頁面訪問的存取時間是多少？（5） 如果系統(tǒng)加有快表，平均命中

39、率為85%，當(dāng)頁表項在快表中時，其查找時間忽略為0，試問此時的存取時間為多少？解：若頁表存放在主存中，則要實現(xiàn)一次頁面訪問需要兩次訪問主存，一次是訪問頁表，確定所存取頁面的物理地址，第二次才根據(jù)物理地址存取頁面數(shù)據(jù)。（1） 由于頁表存放在主存，因此CPU必須兩次訪問主存才能獲得所需數(shù)據(jù)，所以實現(xiàn)一次頁面訪問的存取時間是1.5×2=3微秒（2） 在系統(tǒng)增加了快表后，在快表中找到頁表項的概率為85%，所以實現(xiàn)一次頁面訪問的存取時間為0.85×1.5+(1-0.85)×2×1.5=1.725微秒6、若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下所示。已知頁面大小為

40、1024字節(jié)，試將邏輯地址1011、2148、3000、4000、5012轉(zhuǎn)化為相應(yīng)的物理地址。頁號塊號01232316分析及相關(guān)知識在頁式存儲管理系統(tǒng)中，當(dāng)進(jìn)程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址變換機(jī)構(gòu)自動地將邏輯地址分為頁號和頁內(nèi)位移兩部分，再以頁號為索引去檢索頁表。在執(zhí)行檢索之前，先將頁號與頁表長度進(jìn)行比較，如果頁號超過了頁表長度，則表示本次所訪問的地址已超越進(jìn)程的地址空間，系統(tǒng)產(chǎn)生地址越界中斷。如果頁訪問合法，則由頁表始址和頁號計算出相應(yīng)頁表項的位置，從中得到該頁的物理塊號，并將它裝入物理地址寄存器的塊號部分。與此同時，再將邏輯地址寄存器中的頁內(nèi)地址直接送入物理地址寄存器的塊內(nèi)地址

41、部分，這樣便完成了從邏輯地址到物理地址的變換。解：本題中，為了描述方便，設(shè)頁號為P，頁內(nèi)位移為W，邏輯地址為A，頁面大小為L，則：p=int(A/L)w=A mod L·對于邏輯地址1011p=int(1011/1024)=0w=1011 mod 1024=1011查頁表第0頁在第2塊，所以物理地址為2*1024+1011=3059·對于邏輯地址2148p=int(2148/1024)=2w=2148 mod 1024=100查頁表第2頁在第1塊，所以物理地址為1124。·對于邏輯地址3000p=int(3000/1024)=2w=3000 mod 1024=95

42、2查頁表第2頁在第1塊，所以物理地址為1976·對于邏輯地址4000p=int(4000/1024)=3w=4000 mod 1024=928查頁表第3頁在第6塊，所以物理地址為7072。·對于邏輯地址5012p=int(5012/1024)=4w=5012 mod 1024=916因頁號超過頁表長度，該邏輯地址非法。7、已知頁面走向為1、2、1、3、1、2、4、2、1、3、4，且開始執(zhí)行時主存中沒有頁面。若只給該作業(yè)分配2個物理塊，當(dāng)采用FIFO頁面淘汰算法時缺頁率為多少？假設(shè)現(xiàn)有一種淘汰算法，該算法淘汰頁面的策略為當(dāng)需要淘汰頁面時，就把剛使用過的頁面作為淘汰對象，試問就

43、相同的頁面走向，其缺頁率為多少？分析及相關(guān)知識在進(jìn)行內(nèi)存訪問時，若所訪問的頁已在主存，則稱此次訪問成功；若所訪問的頁不在主存，則稱此次訪問失敗，并產(chǎn)生缺頁中斷。若程序P運(yùn)行過程中訪問頁面的總次數(shù)為s，其中產(chǎn)生缺頁中斷的訪問次數(shù)為f，則其缺頁率為：f/s。解：根據(jù)所給頁面走向，采用FIFO淘汰算法的頁面置換情況如下：頁面走向12131242134物理塊1（尾）1123122413物理塊2（頭）12231244134缺頁缺缺缺缺缺缺缺缺缺從上述頁面置換圖可以看出：頁面引用次數(shù)為11次，缺頁次數(shù)為9次，所以缺頁率為9/11。若采用后一種頁面淘汰策略，其頁面置換情況如下：頁面走向12131242134

44、物理塊1（尾）12131242134物理塊2(頭)1222111222缺頁缺缺缺缺缺缺缺缺從上述頁面置換圖可以看出：頁面引用次數(shù)為11次，缺頁次數(shù)為8次，所以缺頁率為8/11。8、有一請求分頁存儲管理系統(tǒng)，頁面大小為每頁100字節(jié)。有一個50×50的整型數(shù)組按行連續(xù)存放，每個整數(shù)占兩個字節(jié)，將數(shù)組初始化為0的程序描述如下：int a5050;int i,j;for (i=0;i<=49;i+) for (j=0;j<=49;j+)aij=0;若在程序執(zhí)行時內(nèi)存中只有一個存儲塊用來存放數(shù)組信息，試問該程序執(zhí)行時將產(chǎn)生多少次缺頁中斷？解：由題目可知，該數(shù)組中有2500個整數(shù)，

45、每個整數(shù)占用2個字節(jié)，共需存儲空間5000個字節(jié)；而頁面大小為每頁100字節(jié)，數(shù)組占用空間50頁。假設(shè)數(shù)據(jù)從該作業(yè)的第m頁開始存放，則數(shù)組分布在第m頁到第m+49頁中，它在主存中的排列順序為：a00, a01, a049 第m頁a10, a11, a149 第m+1頁a490,a491,a4949 第m+49頁由于該初始化程序是按行進(jìn)行的，因此每次缺頁中斷調(diào)進(jìn)一頁后，位于該頁內(nèi)的數(shù)組元素全部賦予0值，然后再調(diào)入下一頁，所以涉及的頁面走向為m，m+1，m+49，故缺頁次數(shù)為50次。9、在一個請求分頁存儲管理系統(tǒng)中，一個作業(yè)的頁面走向為4、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)

46、的物理塊數(shù)分別為3、4時，試計算采用下述頁面淘汰算法時的缺頁率（假設(shè)開始執(zhí)行時主存中沒有頁面），并比較所得結(jié)果。（1） 最佳置換淘汰算法（理論算法）（2） 先進(jìn)先出淘汰算法FIFO（3） 最近最久未使用淘汰算法LRU解：（1）根據(jù)所給頁面走向，使用最佳頁面淘汰算法時，頁面置換情況如下：（自己分析?。┳呦?32143543215塊1塊2塊3缺頁4缺43缺432缺431缺435缺235缺215缺缺頁率為：7/12走向432143543215塊1塊2塊3塊4缺頁4缺43缺432缺4321缺4325缺1325缺缺頁率為：6/12由上述結(jié)果可以看出，增加分配給作業(yè)的內(nèi)存塊數(shù)可以降低缺頁率。（2）根據(jù)所給

47、頁面走向，使用先進(jìn)先出頁面淘汰算法時，頁面置換情況如下：走向432143543215塊1塊2塊3缺頁4缺43缺432缺321缺214缺143缺435缺352缺521缺缺頁率為：9/12走向432143543215塊1塊2塊3塊4缺頁4缺43缺432缺4321缺3215缺2154缺1543缺5432缺4321缺3215缺缺頁率為：10/12由上述結(jié)果可以看出，對先進(jìn)先出算法而言，增加分配給作業(yè)的內(nèi)存塊數(shù)反而使缺頁率上升，這種異?，F(xiàn)象稱為Belady現(xiàn)象。（3）根據(jù)所給頁面走向，使用最近最久未使用頁面淘汰算法時，頁面置換情況如下：走向432143543215塊1塊2塊3缺頁4缺43缺432缺321

48、缺214缺143缺435缺354543432缺321缺215缺缺頁率為：10/12走向432143543215塊1塊2塊3塊4缺頁4缺43缺432缺4321缺321421431435缺135415435432缺4321缺3215缺缺頁率為：8 /12由上述結(jié)果可以看出，增加分配給作業(yè)的內(nèi)存塊數(shù)可以降低缺頁率。10、在一個請求分頁系統(tǒng)中，假定系統(tǒng)分配給一個作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁面走向為2、3、2、1、5、2、4、5、3、2、5、2。試用FIFO和LRU兩種算法分別計算出程序訪問過程中所發(fā)生的缺頁次數(shù)。解：在本題中，分配給作業(yè)的物理塊數(shù)為3。（1） 根據(jù)所給頁面走向，使用FIFO算法時