【正文】 若每頁可以存放 200 。 a[i][j]=0。i100。j100。i100。i100。假設程序已經在內存中占用 1 塊，其余 2 塊空閑。 (19) 有一個矩陣 int a[100][100] 以行為先進行存儲。 解 : 因為頁面的大小為 100 字，該程序的基 本可用內存為 200 字，即可用內存為 2 塊。 ④ [3,400]。如指令可能訪問多個內存地址，這些地址在不同的頁中。然而，缺頁中斷則是在指令執(zhí)行期間，發(fā)現所訪問的指令或數據不在內存時所產生和處理的。通常，CPU 都是在一條指令執(zhí)行完之后，才檢查是否有中斷請求到達。接著處理器將重新執(zhí)行缺頁時打斷的指令。中斷處理程序將把控制轉向缺頁中斷子程序。 (16) 試述缺頁中斷與一般中斷的主要區(qū)別。若該頁被修改過還需寫回外存，調入所需的頁 面。 2 如果有空閑存儲塊，則根據頁表提供的磁盤地址調入所需的頁面，修改頁表和分塊表后返回。如果在內存，則進行地址變換，按變換后的地址取出操作數；如果不在內存，則引起缺頁中斷，進入缺頁中斷處理程序。其實現方法如下： 當 CPU 執(zhí)行一條指令時，形成操作數的有效地址。當缺頁被調入，使中斷恢復，進程就可以繼續(xù)執(zhí)行它的程序了。 解： 虛擬頁式存儲系統(tǒng)中，系統(tǒng)允許作業(yè)的一部分頁面在內存。主要區(qū)別是：交換技術調入 /調出整個進程，因此一 個進程的大小要受內存容量大小的限制；而虛存中使用的調入 /調出技術在內存和外存之間來回傳遞的是頁面或分段，而不是整個進程，從而使得進程的地址映射具有了更大的靈活性，且允許進程的大小比可用的內存空間大。 交換技術就是把暫時不用的某個程序及數據從內存移到外存中去，以便騰出必要的內存空間，或把指定的程序或數據從外存讀到內存中以允許其運行的一種內存擴充技術。 (14) 覆蓋技術和虛擬存儲技術有何區(qū)別，交換技術和虛擬存儲器中使用的調入和調出技術有何區(qū)別和聯(lián)系？ 解 : 覆蓋技術與虛擬存儲技術最本質的不同在于覆蓋程序段的最大長度要受內存容量大小的限制 ，而虛擬存儲器中程序的最大長度不受內存容量的限制，只受計算機地址結構的限制。因為該用戶作業(yè)的長度為 6 頁，最大的頁號為 5 號。頁內偏移量占 10 位地址碼，為 25C。這樣，其物理地址為十六進制的 113C。頁號占 6 位地址碼，為 2 號頁。 2. 虛擬地址為 093C，對應的二進制數為： 0000 1001 0011 1100。因第 2 頁存儲在 4 號塊中，其基地址為： 0001 0000 0000 0000，即十六進制的 1000H。其中，頁內偏移量占10 位地址碼，為 25C。 (13) 某虛擬內存的用戶編程空間共 32 頁，每頁的大小為 1 KB，內存為 16 KB，假設某時刻系統(tǒng)為用戶的第 0、 3 頁分配的物理塊為 7，而該用戶作業(yè)的長度為 6 頁，試將 16 進制的虛擬地址 0A5C、 093C、 1A5C 轉換成物理地址。 ① 分別畫出采用首次適應算法、最佳適應算法進行內存分配后的內存分配圖和空閑區(qū)隊列； ② 若隨后又申請 80KB，針對上述兩種情況會產生什么后果？ 解 : 采用首次適應算法、最佳適應算法進行內存分配后的內存分配圖和空閑區(qū)隊列圖如下所示。操作系統(tǒng)占用了低地址端的 100KB 的空間，用戶區(qū)從 100KB 處開始共占用 512KB，初始時，用 戶區(qū)全部空閑，分配時截取空閑區(qū)的低地址部分作為一個分配區(qū)。由圖可知，最佳適應算法的內存利用率高。當用戶作業(yè)申請一個空閑區(qū)時，先檢查空閑分區(qū)表 (鏈 )的第一個空閑分區(qū)的大小是否大于或等于所要求的內存長度，若空閑分區(qū)表 (鏈 )的第一項長度小于所要求的大小，則分配失敗，否則從該空閑分區(qū)中劃出與作業(yè)大小相等的一塊內存空間分配給作業(yè)，余下的空閑分區(qū)仍然留在空閑分區(qū)表(鏈 )中。如果空閑分區(qū)大于作業(yè)的大小，則與最先適應算法相同，將減去作業(yè)請求長度后的剩余空閑區(qū)仍然留在空閑分區(qū)表 (鏈 )中。當用戶作業(yè)申請一個空閑區(qū)時，存儲管理程序從空閑分區(qū)表 (鏈 )首開始順序查找，當找到第一個滿足要求的空閑區(qū)時，停止查找。然后，該算法從該分區(qū)中劃出所要求的內存長度分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表 (鏈 )中，同時修改其相應的表 (鏈 )項。 (9) 描述下列算法： ①首次適應；②最佳適應；③最差適應 解： 最先適應算法又稱首次適應算法， 該算法要求空閑分區(qū)表或空閑分區(qū)鏈按起始地址遞增的次序排列。 (8) 一個計算機系統(tǒng)的虛擬存儲器，其最大容量和實際容量分別由什么決定？ 解： 虛擬存儲器的最大容量由主存和輔存的容量之和確定。從用戶的角度來看，該系統(tǒng)所具有的內存容量比實際內存容量大了很多。如果內存已滿，無法裝入新調入的頁 (段 )，則必須利用一定的頁 (段 )置換功能，將內存中暫時不用的頁 (段 )換到外存中，以騰出足夠的空間來存放新調入的頁 (段 )，從而保證程序的順利執(zhí)行。程序在執(zhí)行時，如果它所訪問的頁 (段 )已經調入內存，便可繼續(xù)執(zhí)行下去。盡管進程在運行中會因 I/O 等原因而長期處于阻塞狀態(tài)，或有的程序模塊在運行過一次后就不再需要，但它們都仍將繼續(xù)占用寶貴的內存資源。 解： 虛擬存儲器是指在具有層次結構存儲器的計算機系統(tǒng)中，具有請求調入和交換功能，為用戶提供一個比實際物理內存容量大得多的可尋址的一種存儲器系統(tǒng)，它能從邏輯上對內存容量進行擴充。 3. 分頁的進程地址空間是一維的，即單一的線性空間；而分段的進程地址空間是二維的，由段號和段內地址兩部分組成。 2. 頁的大小由系統(tǒng)確定，由系統(tǒng)把邏輯地址劃分為頁號和頁內地址兩部分，整個系統(tǒng)只能有一種大小的頁面；而段的長度卻不固定，它取決于用戶的程序。段的長度不是固定的，取決于用戶所編寫的程序。或者說，分頁是由于系統(tǒng)管理的需要，而不是用戶的需要。但二者在概念上卻完全不同，具體表現在下述三個方面： 1. 頁是信息的物理單位，而段是信息的邏輯單位。段式管理程序以段為單位進行內存分 配，然后通過地址映射機構把段式虛擬地址轉換為實際的內存物理地址。 在分段存儲管理方式中，程序按內容或過程 (函數 )關系劃分為若干個段，每個段定義一組邏輯信息，都有自己的名字。同樣，每個物理塊也有一個編號，塊號也是從 0 開始依次順序排列。頁號一般從 0 開始，如 0， 1， 2，?，等。 (6) 什么是分頁和分段存儲技術，兩者有何區(qū)別？ 解： 在分頁系統(tǒng)中，系統(tǒng)會把用戶程序的地址空間劃分成若干個大小相等的區(qū)域，每個區(qū)域稱作一個頁面或頁。 (5) 什么是內部碎片和外部碎片？。靜態(tài)地址重定位的地址變換只是在裝入時一次完成，而在程序運行期間不再變化。 (4) 地址重定位，靜態(tài)地址重定位和動態(tài)地址重定位有什么區(qū)別？ 解： 地址重定位指從邏輯地址到物理地址的映射過程，也稱為地址映射。用戶程序的邏輯地址可以是一維線性或多維 線性，而內存中的每一個存儲單元都有相應的內存地址相對應，屬于一維線性地址。物理地址空間也是從零號地址碼開始的。每個應用程序的邏輯地址空間都是從零號地址碼開始的。大容量的輔存常常使用磁盤，磁盤數據經常備份在可移動磁盤或者光盤上 ，以防止硬盤故障時丟失數據。根據具體功能還可以細分為寄存器、高速緩存、主存儲器、磁盤緩存、輔存儲設備 (固定磁盤、可移動存儲介質 )5 層。對換的目的主要是為了提高內存利用率，提高系統(tǒng)的吞吐量。 5. 主存儲空間的擴充。 3. 主存空間的共享。 為了完成上述任務，現代操作系統(tǒng)的存儲管理應具有以下功能： 1. 存儲空間的分配和回收。 3. 提高存儲器的利用率和系統(tǒng)吞吐量。 第 5章 存 儲 管 理 (1) 存儲管理的任務和功能是什么？ 解： 存儲管理的主要任務是： 1. 支持多道程序的并發(fā)執(zhí)行，使多道程序能共享存儲資源，在互不干擾的環(huán)境中并發(fā)執(zhí)行。 4. 不會發(fā)生死鎖。 3. 會發(fā)生死鎖。 2. 不會發(fā)生死鎖。當 M、 N、 W 分別取下列值時，試判斷哪些情形可能會發(fā)生死鎖，為什么？ (1)M=2， N=2， W=1； (2)M=3， N=2， W=2； (3)M=3， N=2， W=3； (4)M=5， N=3， W=2； 解： 1. 不會發(fā)生死鎖。 此時的 Work 小于任意的 Need[i]向量，所以系統(tǒng)處于不安全狀態(tài)，即認為不能分配資源（ 0,2,0）給 P2。 } } (21) 在銀行家算法中，若出現下述資源分配情況： Process Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 0 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 試問： ① 該狀態(tài)是否安全？ ② 若進程 P2 提出請求 Request( 1, 2, 2, 2 )后，系統(tǒng)能否將資源分配給它？ 解 ： 現在對該時刻的狀態(tài)進行安全分析： 由于 Available 向量為（ 1， 6， 2， 2），所以 Work 向量初始化為（ 1， 6， 2， 2）該時刻的安全性檢查表如下： Work Need Allocation Work+Allocation Finish A B C D A B C D A B C D A B C D P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 True P3 1 6 5 4 0 6 5 2 0 0 3 2 1 6 8 6 True P4 1 6 8 6 0 6 5 6 0 0 1 4 1 6 9 10 True P2 1 6 9 10 2 3 5 6 1 3 5 4 2 9 14 14 True P1 2 9 14 14 1 7 5 0 1 0 0 0 3 9 14 14 True 如表所示，存在安全序列 P0， P3， P4， P2， P1，所以該時刻處于安全狀態(tài)。 signal(full)。 wait(vat)。 wait(well)。 } } // 小和尚進程 little_monk(){ while(1){ wait(empty)。 signal(empty)。 wait(vat)。 // 保證互斥地訪問臨界資源水桶的信號量 // 大和尚進程 big_monk(){ while(1){ wait(full)。 // 表示水缸中剩余的空間能容納的水的桶數 semaphore full=0。 // 保證互斥地訪問水井的信號量 semaphore vat=1。試給出取水、入水的同步算法。水桶總數為 3。水缸可以容 10 桶水，水取自同一井。 Get(){ while(1){ wait(empty1) in1=(in1+1)mod11 signal(full1) } } Process（） { while(1){ wait(full1) out1=(out1+1)mod11 signal(empty1) signal(empty2) in2=(in2+1)mod5 signal(full2) } } Put(){ while(1){ wait(full2) out2=(out2+1)mod5 signal(empty2) } } (20) 某寺廟有大、小和尚若干，另有一水缸。 //buffer2 空的數量 semaphore full2=0。 //buffer1 空的數量 semaphore full1=2。試用信號量機制實現它們的同步與互斥。假設buffer1 中最多可以放 11 個信息，現在已經放入了兩個信息； buffer2 最多可以放 5 個信息。 女兒： P(Sa)。同步描述如下： 爸爸 : P(S)。規(guī)定當盤空時一次只能放一只水果供吃者用，請用信號量實現爸爸、兒子和女兒 3 個并發(fā)進程的同步。 end parend end (18) 桌上有一空盤，允許存放一只水果。 pute data in nextc。 signal(mutex)。 wait(mutex)。 until false。 signal(mutex)。 wait(mutex)。 begin parbegin collect: begin