【正文】 So)。 將水果放入盤中 從盤子中取出桔子 從盤子中取出蘋果 if (放入的是桔子 ) v(So)； V（ S）； V（ S）； else v(Sa)； 吃桔子 吃蘋果 ； (19) 設(shè)某系統(tǒng)中有 3 個(gè)進(jìn)程 Get、 Process 和 Put， 共用兩個(gè)緩沖區(qū) buffer1 和 buffer2。Get 進(jìn)程負(fù)責(zé)不斷地將輸入信息送入 buffer1 中， Process 進(jìn)程負(fù)責(zé)從 buffer1 中取出信息進(jìn)行處理，并將處理結(jié)果送到 buffer2 中， Put 進(jìn)程負(fù)責(zé)從 buffer2 中讀取結(jié)果并輸出。 解： semaphore empty1=9。 //buffer1滿的數(shù)量 semaphore empty2=5。 //buffer2滿的數(shù)量 in1,in2,out1,out2:integer := 2,0,1,0。由小和尚挑水入缸供大和尚飲用。水井很窄，每次只能容一個(gè)水桶取水。每次入、取 缸水僅為 1 桶，且不可同時(shí)進(jìn)行。 解： semaphore well=1。 // 保證互斥地訪問水缸的信號量 semaphore empty=10。 // 表示水缸中水的桶數(shù) semaphore pail=3。 wait(pail)。 use pail to get water from vat signal(vat)。 drink water in the pail signal(pail)。\ wait(pail)。 use pail to get water from well signal(well)。 pour water to the vat signal(vat)。 signal(pail)。 由于 Request2(1,2,2,2)Available（ 1,6,2,2）且 Request2（ 1,2,2,2） Need2（ 2,3,5,6），所以先試著把 P2 所申請的資源分 配給它， Available 變?yōu)椋?0,4,0,0）得到系統(tǒng)狀態(tài)如下表所示： Allocation Need Available A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 0 4 0 0 P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 0 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 然后進(jìn)行安全性檢測，此時(shí) Available 為（ 0,4,0,0），所以 Work 初始化為（ 0,4,0,0）。 (22) 設(shè)系統(tǒng)中僅有一類數(shù)量為 M 的獨(dú)占型資源，系統(tǒng)中有 N 個(gè)進(jìn)程競爭該類資源，其中各進(jìn)程對該類資源的最大需求量為 W。因?yàn)閮蓚€(gè)進(jìn)程需要的最多資源量都是 1 個(gè)，而系統(tǒng)擁有的資源量正好是 2 個(gè)，兩個(gè)進(jìn)程都能順利運(yùn)行完，所以不會(huì)死鎖。因?yàn)?2 個(gè)進(jìn)程需要的最多的資源量都是 2 個(gè)，而系統(tǒng)擁有的資源量是 3 個(gè)，所以總會(huì)有 1 個(gè)進(jìn)程得到 2 個(gè)資源后被運(yùn)行，運(yùn)行完畢后釋放資源，于是另一個(gè)進(jìn)程也能順利運(yùn)行完，所以不會(huì)死鎖。當(dāng)一個(gè)進(jìn)程占有 1 個(gè)資源，另一個(gè)進(jìn)程占有 2 個(gè)資源時(shí)， 2 個(gè)進(jìn)程都要再申請資源，但是系統(tǒng)已經(jīng)沒有資源了，所以就發(fā)生死鎖了。因?yàn)槿齻€(gè)進(jìn)程需要的資源最大數(shù)量都是 2 個(gè)，而系統(tǒng)有 5 個(gè) 資源，所以至少有 2 個(gè)進(jìn)程可以拿到足夠的資源運(yùn)行，運(yùn)行完后再釋放資源，最后一個(gè)進(jìn)程也能得到運(yùn)行，所以不會(huì)死鎖。 2. 方便用戶，使用戶減少甚至擺脫對存儲(chǔ)器的管理，使用戶從存儲(chǔ)器的分配、保護(hù)和共享等繁瑣事物中解脫出來。 4. 從邏輯上擴(kuò)充內(nèi)存空間，支持大程序能在小的內(nèi)存空間運(yùn)行或允許更多的進(jìn)程并發(fā)執(zhí)行。 2. 地址轉(zhuǎn)換，實(shí)現(xiàn)邏輯地址到物理地址的映射。 4. 主存空間的保護(hù)。 6. 對換，對換的主要任務(wù)是實(shí)現(xiàn)在內(nèi)存和外存之間的全部或部分進(jìn)程的對換，即將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程調(diào)換到外存上，而將外存上處于就緒狀態(tài)的進(jìn)程換入內(nèi)存。 (2) 為什么要配置層次式存儲(chǔ)器？ 解： 為了解決 CPU 和存儲(chǔ)器之間速度上的不匹配，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)系統(tǒng)通常采用層次結(jié)構(gòu)，存儲(chǔ)層次可粗略分為三級：最高層為 CPU 寄存器，中間為主存，最底層是輔存。一個(gè)文件的數(shù)據(jù)可能出現(xiàn)在存儲(chǔ)系統(tǒng)的不同層次中，例如，一個(gè)文件數(shù)據(jù)通常被存儲(chǔ)在輔存中 (如硬盤 )，當(dāng)其需要運(yùn)行或被訪問時(shí)，就必須調(diào)入主存，也可以暫時(shí)存放在主存的磁盤高速緩存中。 (3) 什么是邏輯地址？什么是物理地址？為什么要進(jìn)行二者的轉(zhuǎn)換工作？ 解： 邏輯地址是應(yīng)用程序中使用的訪存地址，有時(shí)也稱為相對地址，由邏輯地址構(gòu)成的地址空間稱為邏輯空間。 物理地址是內(nèi)存儲(chǔ)器的實(shí)際存儲(chǔ)單元地址，有時(shí)也稱為絕對地址，由物理地址構(gòu)成的地址空間稱為物理空間。 在多道程序環(huán)境下，程序邏輯地址空間和內(nèi)存物理地址空間是不一致的。在將用戶程序部分或全部地裝入內(nèi)存空間時(shí)，要實(shí)現(xiàn)邏輯地址到物理地址的映射。 靜態(tài)地址重定位是指在用戶程序執(zhí)行之前完成地址映射工作，即把程序的邏輯地址都轉(zhuǎn)換為實(shí)際的內(nèi)存物理地址。 動(dòng)態(tài)地址重定位是指在程序執(zhí)行過程中， CPU 在訪問內(nèi)存之前，將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換為內(nèi)存地址。 解： 在一個(gè)分區(qū)內(nèi)部出現(xiàn)的碎片 (即被浪費(fèi)的空間 )稱作內(nèi)部碎片，如固定分區(qū)法就會(huì)產(chǎn)生內(nèi)部碎片； 在所有分區(qū)之外新增的碎片稱作外部碎片，如在動(dòng)態(tài)分區(qū)法實(shí)施過程中出現(xiàn)的越來越多的小空閑塊就是外部碎片，由于它們太小，無法裝入一個(gè)進(jìn)程，因而被浪費(fèi)掉。每個(gè)頁都有一個(gè)編 號，叫做頁號。類似地，也把內(nèi)存空間劃分成若干和頁大小相同的物理塊，這些物理塊叫“幀” (frame)或內(nèi)存塊。系統(tǒng)為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干頁分別裝入多個(gè)可以不相鄰接的塊中。一個(gè)用戶作業(yè)所包含的段對應(yīng)于一個(gè)二維線性虛擬空間，也就是一個(gè)二維虛擬存儲(chǔ)器。 分段和分頁有許多相似之處，比如，二者在內(nèi)存中都采用離散分配方式，而不是整體連續(xù)分配方式，而且都要通過地址映射機(jī)構(gòu)來實(shí)現(xiàn)地址轉(zhuǎn)換。分頁是為了實(shí)現(xiàn)離散分配，減少內(nèi)存碎片，提高內(nèi)存利用率。段則是信息的邏輯單位，它含有一組意義相對完整的信息。分段的目的是為 了能更好地滿足用戶的需要，更方便用戶編程，更好地實(shí)現(xiàn)信息共享和保護(hù)。通常由編譯程序在對源碼進(jìn)行編譯時(shí)，根據(jù)程序的性質(zhì)來劃分。 (7) 什么是虛擬存儲(chǔ)器？列舉采用虛擬存儲(chǔ)器的必要性和可能性。 采用虛擬存儲(chǔ)器的必要性：傳統(tǒng)存儲(chǔ)管理方式要求將作業(yè)全部裝入內(nèi)存之后才能運(yùn)行，這一特征導(dǎo)致大作業(yè)和多個(gè)作業(yè)要求運(yùn)行時(shí)系統(tǒng)無法滿足；另外，傳統(tǒng)存儲(chǔ)管理方式具有駐留性，即作業(yè)裝入內(nèi)存直到運(yùn)行結(jié)束，便一直駐留在內(nèi)存中。 采用虛擬存儲(chǔ)器的可能性：根據(jù)程序的局部性定理，應(yīng)用程序在執(zhí) 行之前，沒有必要全部裝入內(nèi)存，而只需要將那些當(dāng)前要運(yùn)行的部分頁或段先裝入內(nèi)存即可運(yùn)行，其余部分可以仍然留在外存。但如果程序所要訪問的頁 (段 )不在內(nèi)存中 (稱為缺頁或缺段 )，此時(shí)程序可以利用操作系統(tǒng)提供的請求調(diào)頁 (段 )功能，將它們調(diào)入內(nèi)存，以便程序能夠繼續(xù)執(zhí)行下去。這樣， 一個(gè)大的程序就可以在較小的內(nèi)存空間中執(zhí)行。但實(shí)際上，用戶所看到的大容量存儲(chǔ)器是不存在的，只是虛擬的，故把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。 虛擬存儲(chǔ)器的實(shí)際容量由指令中表示地址的字長決定，也就是計(jì)算機(jī)的地址結(jié)構(gòu)決定的。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表 (鏈 )首開始順序查找，一旦找到大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束查找。 最佳適應(yīng)算法要求空閑分區(qū)按容量大小遞增的次序排列。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與 作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。 最壞適應(yīng)算法要求空閑分區(qū)按其大小遞減的順序組成空閑分區(qū)表 (鏈 )。 (10) 如果內(nèi)存劃分為 100KB、 500KB、 200 KB、 300 KB 和 600 KB(按順序 )，那么，首次適應(yīng)、最佳適應(yīng)和最差適應(yīng)算法各自將如何放置大小分別為 215 KB、 414 KB、 110 KB 和 430 KB(按順序 )的進(jìn)程，哪一種算法的內(nèi)存利用率高？ 解 : 見下圖，在首次適應(yīng)和最差適應(yīng)算法中，最后 430KB 沒有空間分配。 (11) 某操作系統(tǒng)采用分區(qū)存儲(chǔ)管理技術(shù)。在執(zhí)行了如下的申請、釋放操作序列后： 作業(yè) 1 申請 300KB、作業(yè) 2 申請 100KB、作業(yè) 1 釋放 300KB、作業(yè) 3 申請 150KB、作業(yè) 4申請 50KB、作業(yè) 5 申請 90KB。 若隨后又申請 80KB，只有 采用首次適應(yīng)算法的內(nèi)存分配還有空間可以分配，分配圖如下： (12) 假設(shè)一個(gè)有 8 個(gè) 1024 字節(jié)頁面的邏輯地址空間，映射到一個(gè)有 32 幀的物理內(nèi)存： ① 邏輯地址有多少位？ ② 物理地址有多少位？ 解： 邏輯地址有 13 位；物理地址有 15 位。 解： 1. 虛擬地址為 0A5C,對應(yīng)的二進(jìn)制數(shù)為： 0000 1010 0101 1100。頁號占 6 位地址碼，為 2 號頁。這樣，其物理地址為十六進(jìn)制的 125C。其中，頁內(nèi)偏移量占 10 位地址碼，為 13C。因第 2 頁存儲(chǔ)在 4 號塊中，其基地址為： 0001 0000 0000 0000，即十六進(jìn)制的 1000H。 3. 虛擬地址為 1A5C，對應(yīng)的二進(jìn)制數(shù)為： 0001 1010 0101 1100。頁號占 6 位地址碼，為 6 號頁。因?yàn)樘摂M地址為 1A5C 對應(yīng)的 6 號頁超出了地址范圍，所以屬于越界。另外，覆蓋技術(shù)中的覆蓋段由程序員設(shè)計(jì)，且要求覆蓋段中的各個(gè)覆蓋具有相對的獨(dú)立性，不存在直接聯(lián)系或相互交叉訪問；而虛擬存儲(chǔ)技術(shù)對用戶的程序段之間沒有這種要求。交換技術(shù)與虛存中使用的調(diào)入 /調(diào)出技術(shù)的主要相同點(diǎn)是：都要在內(nèi)存與外存之間交換信息。 (15) 在虛擬頁式存儲(chǔ)系統(tǒng)中引入了缺頁中斷，說明引入缺頁中斷的原因，并給出其實(shí)現(xiàn)的方法。當(dāng)系統(tǒng)產(chǎn)生了缺頁中斷后，操作系統(tǒng)才能將不在內(nèi)存的頁面從外存調(diào)入內(nèi)存。 缺頁中斷的實(shí)現(xiàn)由硬件和軟件兩 部分組成。其中的頁號部分用來檢查頁表，看該頁是否在內(nèi)存。在缺頁中斷處理程序中，主要的處理為： 1 利用存儲(chǔ)器分塊表檢查實(shí)存是否有空閑頁面。 3 如果沒有空閑存儲(chǔ)塊，則選擇一頁淘汰掉。然后修改頁表和分塊表，返回。 解： 程序在執(zhí)行時(shí)，當(dāng)訪問的頁面不在內(nèi)存時(shí)，便產(chǎn)生缺頁中斷，請求操作系統(tǒng)將所缺頁調(diào)入內(nèi)存。然后系統(tǒng)執(zhí)行此子程序，把所缺頁面裝入主存中。缺頁中斷是一種特殊的中斷，也就是說，缺頁中斷同樣需要經(jīng)歷諸如保護(hù) CPU 環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理、恢復(fù) CPU 環(huán)境等幾個(gè)步驟，但與一般的中斷相比，它又具有以下不同點(diǎn)： 1. 一般中斷是一條指令完成后中斷，而 缺頁中斷是在一條指令執(zhí)行時(shí)中斷。如果有，便去響應(yīng)中斷，否則，繼續(xù)執(zhí)行下一條指令。 2. 一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。 (17) 假設(shè)有下面的段表： 下面邏輯地址的物理地址分別是多少？ ① [0,430]； ② [1,12]； ③ [2,500]。 ⑤ [4,122] 段 基址 長度 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 解： ①： 649；②： 2312；③：越界；④： 1727；⑤：越界 (18) 考慮下面存儲(chǔ)訪問序列，該程序的大小為 460 字 (以下數(shù)字均為十進(jìn)制數(shù)字 )： 1 10 170、 7 30 18 24 24 43 45 364 該頁面的大小為 100 字，該程序的基本可用內(nèi)存為 200 字，計(jì)算采用 FIFO、 LRU 和 OPT置換算法的缺頁次數(shù)。程序的存儲(chǔ)訪問序列可轉(zhuǎn)換為如下頁面訪問序列： 4 采用 FIFO、 LRU 和 OPT 置換算法的訪問序列如下： 由圖可知 FIFO 算法的缺頁次數(shù)為 6 次， LRU 的缺頁次數(shù)為 7 次， OPT 的缺頁次數(shù)為 5次。有一虛擬存儲(chǔ)系統(tǒng)，物理內(nèi)存共有 3塊，其中 1 塊用于存放程序，其余 2 塊用于存放數(shù)據(jù)。 程序 A: 程序 B: for (i=0。i++) for (j=0。j++) for (j=0。j++) for (i=0。i++) a[i][j]=0。 若每頁可存放 200 個(gè)整數(shù)，則程序 A 和程序 B 在執(zhí)行過程中各會(huì)發(fā)生多少次缺頁？若每頁只能存放 100 個(gè)整數(shù)呢？以上說明了什么問題？ 解： 由題目所給條件可知，數(shù)組 a 有 100?100=10000 個(gè)整數(shù)，系統(tǒng)中共有 2 個(gè)內(nèi)存塊用于存放數(shù)組信息，數(shù)組中的元素按行