一、簡答題

1.存儲器管理的基本任務，是為多道程序的并發(fā)執(zhí)行提供良好的存儲器環(huán)境。請問好的存儲器環(huán)境”應包含哪幾個方面？

答：

2.內(nèi)存保護是否可以完全由軟件實現(xiàn)？為什么？

答：內(nèi)存保護的主要任務是確保每道程序都只在自己的內(nèi)存區(qū)內(nèi)運行。這就要求系統(tǒng)能對每條指令所訪問的地址進行越界檢查。若發(fā)生越界,系統(tǒng)應能立即發(fā)現(xiàn),并發(fā)出越界中斷請求,以拋棄該指令。若每次檢查完全由軟件實現(xiàn),則每執(zhí)行一條指令時,都要增加若干條指令去執(zhí)行越界的檢查功能,這無疑將降低程序的執(zhí)行速度,因此,越界檢查通常由硬件實現(xiàn),并使指令的執(zhí)行與越界檢查功能并行執(zhí)行,從而不使程序的運行速度降低。當然,對發(fā)現(xiàn)有越界后的處理需與軟件配合來完成。因此說內(nèi)存保護功能是由硬件和軟件協(xié)同完成的。

3.請解釋什么是重定位？為什么要重定位？

答：重定位：允許作業(yè)在運行過程中在內(nèi)存中移動的技術,必須獲得硬件地址變換機構的支持。即在系統(tǒng)中增加一個重定位寄存器,用它來裝入程序在內(nèi)存中的起始地址。程序在執(zhí)行時,真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而成的,這就叫做重定位。在連續(xù)分配方式中,為了利用“碎片”將作業(yè)裝入,需要將內(nèi)存中分散的小分區(qū)拼接成大分區(qū),稱為”拼接”或”緊湊”,但由于經(jīng)過緊湊后的用戶程序在內(nèi)存中的位置發(fā)生了變化,若不對程序和數(shù)據(jù)的地址進行修改, 程序將無法執(zhí)行,所以必須進行重定位。

4.動態(tài)重定位的實現(xiàn)方式有哪幾種？

答：

5.可采用哪幾種方式將程序裝入內(nèi)存？它們分別適用于何種場合？

答:

(1) 絕對裝入方式,適用于單道程序系統(tǒng)。

(2) 可重定位裝入方式,適用于分區(qū)式存儲管理系統(tǒng)。

(3) 動態(tài)運行時裝入方式,適用于分頁、分段式存儲管理系統(tǒng)。

根據(jù)信息的性質來劃分。(3)分頁的作業(yè)地址空間是一維的,而分段作業(yè)地址空間則是二維的。

6.何謂靜態(tài)鏈接？靜態(tài)鏈接時需要解決哪兩個問題？

答：

靜態(tài)鏈接的定義：程序運行之前，先將各目標及它們所需的庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開，這種事先進行鏈接的方式稱為。

7.編寫程序時，源代碼必須經(jīng)過編譯和鏈接生成目標代碼，請問什么是鏈接？鏈接主要解決了什么問題？簡述鏈接的主要類型及其優(yōu)缺點。

答：

? ? ?????????鏈接（Linking）?是計算機程序構建過程中的一個階段，其主要任務是將一個或多個由編譯器生成的目標文件（包括庫文件）組合成一個可執(zhí)行文件、共享庫或者其他類型的目標代碼。鏈接主要解決的問題包括：

? ? ? ? ? 符號解析 ：編譯時，函數(shù)和變量的具體地址尚未確定。這些未確定的函數(shù)和變量被稱為“外部符號”。鏈接器的任務之一是找到這些符號的真實地址，并替換相應的引用。

?????????空間和地址分配：鏈接器為每個模塊分配空間，并決定每個函數(shù)和變量在最終輸出中的地址。

? ? ? ? ?庫處理：程序員經(jīng)常使用標準庫或其他庫中的函數(shù)。鏈接器從庫中選擇所需的模塊并將其包含在最終的可執(zhí)行文件中。

鏈接的主要類型包括：

靜態(tài)鏈接?
? 優(yōu)點：
? ? ?- 生成的可執(zhí)行文件是獨立的，不依賴于外部的庫文件，方便部署和分發(fā)。
? ? ?- 有時可能會有更好的性能，因為所有的代碼都在一個單一的二進制文件中。
? 缺點：
? ? ?- 如果多個程序使用相同的庫，靜態(tài)鏈接會導致每個程序都有庫的一個副本，浪費磁盤和內(nèi)存資源。
? ? ?- 如果庫更新，需要重新鏈接和部署應用程序。

動態(tài)鏈接：
? ?-優(yōu)點：
? ? ?- 節(jié)省磁盤空間和內(nèi)存，因為多個運行的程序可以共享同一個庫的副本。
? ? ?- 庫更新時，通常不需要重新鏈接和部署應用程序。
? ?缺點：
? ? ?- 運行時需要庫文件。如果庫文件丟失或與應用程序版本不兼容，可能會導致程序無法運行。
? ? ?- 有時可能有額外的性能開銷，因為需要解析動態(tài)符號和加載共享庫。

在實際開發(fā)中，靜態(tài)鏈接和動態(tài)鏈接各有應用場景，選擇哪種鏈接方式取決于項目的具體需求和目標。

8.為什么要引入對換？對換可分為哪幾種類型？

答：答:在多道環(huán)境下,一方面,在內(nèi)存中的某些進程由于某事件尚未發(fā)生而被阻塞,但它卻占用了大量的內(nèi)存空間,甚至有時可能出現(xiàn)在內(nèi)存中所有進程都被阻塞而迫使CPU停止下來等待的情況;另一方面,卻又有著許多作業(yè)在外存上等待,因無內(nèi)存而不能進入內(nèi)存運行的情況。顯然這對系統(tǒng)資源是一種嚴重的浪費,且使系統(tǒng)吞吐量下降。為了解決這一問題,在操作系統(tǒng)中引入了對換(也稱交換)技術。 可以將整個進程換入、換出,也可以將進程的一部分(頁、段)換入、換出。前者主要用于緩解目前系統(tǒng)中內(nèi)存的不足,后者主要用于實現(xiàn)虛擬存儲。

9.在對換技術中，對文件區(qū)管理的目標和對對換空間管理的目標有何不同？

答：

?????????對文件區(qū)管理的主要目標是提高文件存儲空間的利用率，然后才提高對文件的訪問速度，因此，對文件區(qū)空間的管理采取離散分配方式。

????????對對換空間管理的主要目標是提高進程換入和換出的速度，然后才是提高文件存儲空間的利用率，因此，對對換區(qū)空間的管理采取連續(xù)分配方式，較少的考慮外存中的碎片問題。

10.為什么說分段系統(tǒng)較分頁系統(tǒng)更易實現(xiàn)信息共享與保護？

答:

????????無論是分頁系統(tǒng)、還是分段系統(tǒng),都允許多個進程共享程序中的代碼或公共數(shù)據(jù)。分頁系統(tǒng)實現(xiàn)頁共享的方法是,在共享進程中將共享頁對應的頁表項指向同一個內(nèi)存塊。由于分頁系統(tǒng)的地址空間是一維的,頁的劃分由系統(tǒng)自動進行,因此會造成共享代碼或數(shù)據(jù)與非共享代碼或數(shù)據(jù)共處一頁的情況,從而使信息的共享變得十分困難。而分段系統(tǒng)則在用戶編程時,自然地進行分段的劃分,每個分段中的信息具有相對完整的邏輯意義,正好與分段存儲系統(tǒng)相適應,因此它比分頁更容易實現(xiàn)信息的共享。?

????????對信息的保護來說,也是按信息的邏輯單位進行保護,也與分段存儲系統(tǒng)相適應,OS應保證用戶進程只按允許的方式訪問共享信息,而對他人的非共享信息則不允許進行任何形式的訪問。分段系統(tǒng)比分頁系統(tǒng)更容易實現(xiàn)信息的保護,我們可按各個分段的含義來對每個分段進行不同的保護,如子程序段的存取權限是只能執(zhí)行,數(shù)據(jù)段的存取權限是可讀可寫等。

11.提高內(nèi)存利用率的途徑主要有哪些？

答：

(1)改連續(xù)分配方式為離散分配方式;

(2)增加對換和覆蓋機制;

(3)引入動態(tài)機制;

(4)引入虛擬存儲器機制;

(5)引入存儲器共享機制。

二、計算題

12.假設一個分頁存儲系統(tǒng)具有快表，多數(shù)活動頁表項都可以存在于其中若頁表放在內(nèi)存中，內(nèi)存訪問時間是1ns，快表的命中率是85%，快表的訪問時間為0.1ns，財效存取時間為多少？

答：

????????在有快表的分頁存儲系統(tǒng)中，計算有效存取時間時，需注意訪問快表與訪問內(nèi)存的時間關系。通常系統(tǒng)中，先訪問快表，未命中時再訪問內(nèi)存；但如果題中有具體的說明，計算時則應注意區(qū)別。?計算過程：[(0.1+1)×85%+(0.1+1+1)×(1-85%)]μs=1.25μs。

?理論：?

????????在這個分頁存儲系統(tǒng)中，當需要訪問內(nèi)存時，系統(tǒng)首先查找快表（TLB）。如果找到了對應的頁表項（即快表命中），則直接使用該信息進行內(nèi)存訪問；如果沒有找到（即快表未命中），則需要首先從內(nèi)存中查找頁表項，然后再訪問實際的數(shù)據(jù)。

1. 快表命中：此時的訪問時間包括查找快表的時間和1次實際的內(nèi)存訪問時間。

2. 快表未命中：此時的訪問時間包括查找快表的時間、從內(nèi)存中獲取頁表項的時間以及1次實際的內(nèi)存訪問時間。

13.對一個將頁表存放在內(nèi)存中的分頁系統(tǒng)：
（1）如果訪問內(nèi)存需要0.2μs，則有效訪問時間為多少？
（2）如果加一快表，且假定在快表中找到頁表項的概率高達90%，則有效訪問時間又s是多少（假定查快表須花費的時間為0）？

答：

(1)不使用快表：

每次內(nèi)存訪問實際上需要兩次真正的內(nèi)存訪問：一次是為了獲取頁表項，一次是為了獲取實際數(shù)據(jù)。

所以有效訪問時間 = 2 × 內(nèi)存訪問時間 = 2 × 0.2μs = 0.4μs

所以，有效訪問時間為0.4μs。

(2)使用快表：

快表（或稱為TLB：Translation Lookaside Buffer）用于緩存頁表項，大大減少了頁表查詢的時間。

考慮兩種情況：

1. 快表命中：此時只需1次內(nèi)存訪問即可。
2. 快表未命中：此時需要2次內(nèi)存訪問。

有效訪問時間 = 快表命中概率 × 1次內(nèi)存訪問時間 + 快表未命中概率 × 2次內(nèi)存訪問時間 = 0.9 × 0.2μs + 0.1 × 0.4μs = 0.18μs + 0.04μs = 0.22μs

14.某系統(tǒng)采用分頁存儲管理方式，擁有邏輯空間32頁，每頁2KB，擁有物理空間1MB。
（1）寫出邏輯地址的格式。
（2）若不考慮訪問權限等，則進程的頁表有多少項？每項至少有多少位？
（3）如果物理空間減少一半，則頁表結構應相應地做怎樣的改變？

答：

由題意：邏輯空間 = 32頁????????每頁大小 = 2KB = (2^{11})B (因為1KB = 2^{10})B)
物理空間 = 1MB = (2^{20})B

(1) 寫出邏輯地址的格式：?

邏輯地址由頁號和頁內(nèi)地址組成。頁號用于索引頁表，而頁內(nèi)地址表示在該頁中的偏移量。

- 頁號（Page Number）：由于總共有32頁，所以需要(log_2 32 = 5)位來表示。
??
- 頁內(nèi)地址（Page Offset）：由于每頁大小為2KB = (2^{11})B，所以需要11位來表示。

因此，邏輯地址格式為：[5位頁號 | 11位頁內(nèi)地址]

**(2) 若不考慮訪問權限等，則進程的頁表有多少項？每項至少有多少位？**

- 頁表的項數(shù)與邏輯空間的頁數(shù)相同，即32項。
- 每一項的大小是決定于物理地址空間的。1MB的物理空間對應的頁數(shù)是：( frac{1MB}{2KB} = 512)頁。因此，需要(log_2 512 = 9)位來表示物理頁號。

所以，每項至少有9位。

**(3) 如果物理空間減少一半，則頁表結構應相應地做怎樣的改變？**

物理空間減少一半意味著新的物理空間為0.5MB = (2^{19})B。與2KB每頁相除，得到新的物理空間頁數(shù)為256頁。因此，新的物理頁號需要(log_2 256 = 8)位來表示。

因此，當物理空間減少一半時，頁表中的每項從原來的9位減少到8位。

15.已知某分頁系統(tǒng)，內(nèi)存容量為64KB，頁面大小為1KB，對一個4頁大的作業(yè)，其)
1、2、3頁分別被分配到內(nèi)存的2、4、6、7塊中。
（1）將十進制的邏輯地址1023、2500、3500、4500變換為物理地址。
（2）以十進制的邏輯地址1023為例，畫出地址變換過程圖。

答：

由題意：

????????內(nèi)存容量 = 64KB????????頁面大小 = 1KB = 210210B? ? 一個作業(yè)的頁面映射如下：1→2,2→4,3→6,4→71→2,2→4,3→6,4→7

????????因為每頁是1KB，所以邏輯地址的低10位（0-9位）是頁內(nèi)地址，而更高的位是用于表示頁號。

(1) 將十進制的邏輯地址1023、2500、3500、4500變換為物理地址：

• 1023的邏輯地址：

  • 頁號：1023/1024= 0（第一頁）
  • 頁內(nèi)地址：1023 % 1024 = 1023
  • 物理頁號：2
  • 物理地址 = 2 × 1024 + 1023 = 3071

• 2500的邏輯地址：

  • 頁號：2500/1024 = 2（第三頁）
  • 頁內(nèi)地址：2500 % 1024 = 452
  • 物理頁號：6
  • 物理地址 = 6 × 1024 + 452 = 6596

• 3500的邏輯地址：

  • 頁號：3500/1024 = 3（第四頁）
  • 頁內(nèi)地址：3500 % 1024 = 932
  • 物理頁號：7
  • 物理地址 = 7 × 1024 + 932 = 7932

• 4500的邏輯地址：

  • 頁號：4500/1024? = 4
  • 由題意，顯然只有4頁，所以4500這個邏輯地址是無效的，不能轉換為物理地址。

（2）具體圖像如下：

16.已知某系統(tǒng)頁面長4KB，每個頁表項的大小為4B，采用多層分頁策略映射64位的用戶地址空間。若限定最高層頁表只占1頁，問它可采用幾層分頁策略。

答：

????????方法一:由題意可知,該系統(tǒng)的用戶地址空間為2(64)B,而頁的大小為4KB,故作業(yè)最多可有(2^64)/(2^12)(即2^52)個頁,其頁表的大小則為2^(52)*4即2^(54)B。因此,又可將頁表分成2(42)個頁表頁,并為它建立兩級頁表,兩級頁表的大小為2(44)B。依次類推,可知道它的3、4、5、6級頁表的長度分別是2(34)B、2(24)B、2(14)B、2(4)B,故必須采取6層分頁策略。

???????? 方法二:頁面大小為4KB=2^(12)B,頁表項4B=2^(2)B,因此一個頁面可以存放2^(12)/2^(2)=2(10)個頁表項,因此分層數(shù)=INT[64/10]=6層。

17.對于表5-2所示的段表，請將邏輯地址（0,137），（1,4000)，（2,3600)，（5,230)
變換成物理地址。
?

段表 5-2

段號	內(nèi)存起始地址	段長
0	50K	10KB
1	60K	3KB
2	70K	5KB
3	120K	8KB
4	150K	4KB

答：

(0,137)對應的物理地址為:50K+137 = 50*1024+137 = 51337;

(1,4000)的段內(nèi)偏移地址越界,是一個不合法邏輯地址;

(2,3600)對應的物理地址為:70K+3600 = 75280

(5,230)的段號越界,是一個不合法邏輯地址。

三、綜合應用題

18.某系統(tǒng)采用動態(tài)分區(qū)分配方式管理內(nèi)存，內(nèi)存空間為640KB，低端40KB存放OS。系統(tǒng)為用戶作業(yè)分配空間時，從低地址區(qū)開始。針對下列作業(yè)請求序列，畫圖表示使用首次適應算法進行內(nèi)存分配和回收后內(nèi)存的最終映像。作業(yè)請求序列如下：
作業(yè)1申請200KB，作業(yè)2申請70KB；作業(yè)3申請150KB，作業(yè)2釋放70KB；作業(yè)4申請80KB，作業(yè)3釋放150KB；作業(yè)5申請100KB，作業(yè)6申請60KB；作業(yè)7申請50KB，作業(yè)6釋放60KB。

答：

內(nèi)存分配和回收的過程：

2）

19.某OS采用分段存儲管理方式，用戶區(qū)內(nèi)存為512KB，

空閑塊鏈入空閑塊表，分配時截取空閑塊的前半部分（小地址部分）。初始時全部空閑。執(zhí)行申請、釋放操作序列request(300KB）、request(100KB)、release (300KB)、request (150KB)、request(5OKB)、request（90KB)后：
（1）若采用首次適應算法，則空閑塊表中有哪些空閑塊（指出大小及起始地址）？
（2）若采用最佳適應算法，則空閑塊表中有哪些空閑塊（指出大小及起始地址）？
（3）若隨后又要申請80KB，則針對上述兩種情況會產(chǎn)生什么后果？這說明了什么問題？

答：

由題意給定：用戶區(qū)內(nèi)存大小 = 512KB；初始時，所有內(nèi)存都是空閑的，即有一個空閑塊從地址0開始，大小為512KB。

執(zhí)行給定的操作序列：

request(300KB)：分配300KB的內(nèi)存 ????????????????request(100KB)：分配100KB的內(nèi)存
release(300KB)：釋放第一個申請的300KB ????????request(150KB)：分配150KB的內(nèi)存
request(50KB)：分配50KB的內(nèi)存????????????????request(90KB)：分配90KB的內(nèi)存

我們分別考慮兩種算法：

(1) 首次適應算法：

1. 分配300KB后，空閑塊：[300KB, 512KB-300KB = 212KB]
2. 分配100KB后，空閑塊：[400KB, 112KB]
3. 釋放300KB后，空閑塊：[0KB, 300KB], [400KB, 112KB]
4. 分配150KB后，空閑塊：[150KB, 150KB], [400KB, 112KB]
5. 分配50KB后，空閑塊：[200KB, 100KB], [400KB, 112KB]
6. 分配90KB后，空閑塊：[200KB, 100KB], [490KB, 22KB]

(2) 最佳適應算法：

1. 分配300KB后，空閑塊：[300KB, 212KB]
2. 分配100KB后，空閑塊：[400KB, 112KB]
3. 釋放300KB后，空閑塊：[0KB, 300KB], [400KB, 112KB]
4. 分配150KB后，空閑塊：[0KB, 150KB], [400KB, 112KB]
5. 分配50KB后，空閑塊：[0KB, 100KB], [450KB, 62KB]
6. 分配90KB后，空閑塊：[0KB, 10KB], [450KB, 62KB]

(3) 隨后申請80KB的后果：

????????對于首次適應算法：可以從200KB位置開始的100KB空閑塊中分配80KB。剩余的空閑塊為：[280KB, 20KB], [490KB, 22KB]。
??
????????對于最佳適應算法：可以從450KB位置開始的62KB空閑塊中分配80KB，但這個塊太小，所以這次分配請求會失敗。剩余的空閑塊不變，為：[0KB, 10KB], [450KB, 62KB]。

????????最佳適應算法可能會導致大量的小空閑塊，這使得大塊的內(nèi)存請求更有可能失敗，即使總的可用空閑空間可能足夠大。這說明了碎片化問題，特別是內(nèi)部碎片問題。最佳適應策略可能會導致更多的內(nèi)部碎片，而首次適應策略可能會導致內(nèi)存的低效利用，但在這種情況下，它能夠滿足80KB的請求。

20.某系統(tǒng)的空閑分區(qū)如表5-3所示，采用可變分區(qū)分配策略處理作業(yè)?，F(xiàn)有作業(yè)序列96KB、20KB、200KB，若采用首次適應算法和最佳適應算法來處理這些作業(yè)序列，則哪種算法能滿足該作業(yè)序列的請求？為什么？

表5-3空閑分區(qū)表

段號	內(nèi)存起始地址	段長
0	32K	100KB
1	10KB	150K
2	5KB	200K
3	218KB	220K
4	96KB	530K

答：

解:若采用最佳適應算法,在申請96K存儲區(qū)時,選中的是5號分區(qū),5號分區(qū)大小與申請空間大小一致,應從空閑分區(qū)表中刪去該表項;接著申請20K時,選中1號分區(qū),分配后1號分區(qū)還剩下12K;最后申請200K,選中4號分區(qū),分配后剩下18K。顯然采用最佳適應算法進行內(nèi)存分配,可以滿足該作業(yè)序列的需求。為作業(yè)序列分配了內(nèi)存空間后,空閑分區(qū)表如表(a)所示。

若采用首次適應算法,在申請96K存儲區(qū)時,選中的是4號分區(qū),進行分配后4號分區(qū)還剩下122K;接著申請20K,選中1號分區(qū),分配后剩下12K;最后申請200K,現(xiàn)有的五個分區(qū)都無法滿足要求,該作業(yè)等待。顯然采用首次適應算法進行內(nèi)存分配,無法滿足該作業(yè)序列的需求。這時的空閑分區(qū)表如表(b)所示。

分配后的空閑分區(qū)表

(a)

分區(qū)號	大小	起始地址
1	12K	100K
2	10K	150K
3	5K	200K
4	18K	220K

(b)

分區(qū)號	大小	起始地址
1	12K	100K
2	10K	150K
3	5K	200K
4	122K	220K
5	96K	530K