精选习题解答.ppt

《精选习题解答.ppt》由会员分享，可在线阅读，更多相关《精选习题解答.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精選習題解答1著作權所有 旗標出版股份有限公司第2章 行程管理 2著作權所有 旗標出版股份有限公司行程管理-計算題1有一組行程如下：行程 CPU 暴衝時間（毫秒）P1 15 P2 7 P3 4 P4 10到達時間皆為 0，順序為 P1、P2、P3 和 P4請分別使用 FCFS 與不可搶先的 SJF 排程法，求出平均等待時間3著作權所有 旗標出版股份有限公司解答FCFS的平均等待時間：（0+15+22+26）/4=15.75 毫秒SJF的平均等待時間：（0+4+11+21）/4=9 毫秒4著作權所有 旗標出版股份有限公司行程管理-計算題2假設有四個行程 P1、P2、P3 和 P4，都在時間 0

2、到達，順序為 P1、P2、P3、P4，其 CPU 暴衝時間如下：行程 CPU 暴衝時間（毫秒）優先權 P1 6 2 P2 5 0 P3 7 3 P4 4 11.當使用 FCFS、SJF、不可搶先的優先權（數字愈小，優先權愈高）和 RR（時間切片=3）排程法時，行程的執行順序為何，請畫出與課文類似的圖。2.所有行程的平均等待時間為何？3.每個行程的回覆時間各為何？5著作權所有 旗標出版股份有限公司解答-行程的執行順序FCFS的排程如下：P1P2P3P40 6 11 18 22SJF的排程如下：P4P2P1P30 4 9 15 22不可搶先的優先權的排程如下：P2P4P1P30 5 9 15 22

3、RR的排程如下：P1P2P3P4P1P2P3P4P30 3 6 9 12 15 17 20 21 226著作權所有 旗標出版股份有限公司解答-平均等待時間FCFS的平均等待時間：（0+6+11+18）/4=8.75 毫秒SJF的平均等待時間：（0+4+9+15）/4=7 毫秒不可搶先的優先權的平均等待時間：（0+5+9+15）/4=7.25 毫秒RR的平均等待時間：(12-3)+(15-3)+(20 3)+(21 6)/4=13.25 毫秒7著作權所有 旗標出版股份有限公司解答-回覆時間FCFSSJF優先權RRP16151515P2119517P318222222P42249218著作權所有

4、旗標出版股份有限公司行程管理-進階題2Q：UNIX對fork()系統呼叫傳回值的做法為什麼不顛倒過來，在子行程中傳回父行程ID，在父行程中傳回0，然後讓父行程使用諸如getcpid()之類的系統呼叫來取得子行程ID？A：getppid()可以在任意時間呼叫，因為子行程一定只有一個父行程。但是如果是在一父多子的情況下，如果父行程在任意時間點呼叫getcpid()，則系統將不知道該傳回哪個子行程的ID。9著作權所有 旗標出版股份有限公司行程管理-進階題5Q：請說明當行程發生哪一些狀態轉換的時候，作業系統會重新排程？A：有 4 種行程的狀態轉換需要重新排程：n由執行狀態切換到就緒狀態（如發生中斷）。

5、n由執行狀態切換到等待狀態（如產生 I/O 的要求或是等待某些事件的發生）。n由執行狀態切換到結束狀態。n由等待狀態切換到就緒狀態（如完成 I/O）。10著作權所有 旗標出版股份有限公司行程管理-進階題7Q：一個排程法決定了行程的執行順序，假設系統中有 n 個不可搶先的行程需要排程，可能產生哪幾種不同的執行順序？請用 n 寫出一個公式。A：n!=n*(n-1)*(n-2)*2*111著作權所有 旗標出版股份有限公司行程管理-進階題8Q：很多排程法都需要設定一些參數，請問下列各組排程方法之間，是否有存在某些關係？如果有的話，是什麼樣的關係？1.優先權，SJF2.MFQ，FCFS3.優先權，FCF

6、S4.RR，SJFA：1.當最短的工作擁有最高的優先權時，優先權排程就等於SJF 排程。2.多層反饋佇列中的優先權最低的佇列，就等於FCFS 排程。3.等待時間最長的工作擁有最高的優先權時，優先權排程就等於FCFS 排程。4.RR排程法與SJF排程法無關，但時間切片很大的RR排程會很近似FCFS排程。12著作權所有 旗標出版股份有限公司行程管理-進階題9Q：考慮一個RR 排程法的變形版本：n假設就緒佇列中允許有兩個指標指向同一個行程，會造成什麼效果？n這樣的架構其主要優缺點為何？n在不使用兩個相同指標的原則下，要如何修改最原始的 RR 排程法，達到相同效果？A：n兩個指標共同指向的行程相當於有

7、較高的優先權，因為該行程會獲得兩倍的執行時間。n這樣的架構能夠給予重要的工作更多的執行時間，也就是給予較高的優先權，缺點是不適用於簡短的工作。n在原始的 RR 排程法中對於高優先權的工作給予較長的執行時間，例如2倍以上的時間切片。13著作權所有 旗標出版股份有限公司第3章 行程間通訊與同步14著作權所有 旗標出版股份有限公司行程間通訊與同步-進階題3Q：請利用swap指令，完成符合有限等待條件的臨界區設計 A：waitingpid=true;key=true;while(waitingpid&key)swap(lock,key);next_pid=(pid+1)%MAX_PID;while(n

8、ext_pid!=pid&waitingnext_pid=false)next_pid=(next_pid+1)%MAX_PID;if(next_pid=pid)lock=false;elsewaitingnext_pid=false;15著作權所有 旗標出版股份有限公司行程間通訊與同步-進階題5Q：請證明在第 6-2-4 節中所介紹的麵包店演算法中，下列條件恆成立：假如 Pi正在臨界區之中執行，且 Pj（j i）位於入口區並且已經取得號碼牌 numberj（0），則(numberi,i)(numberj,j)A：由於 Pi 已經在臨界區中執行，所以 Pj 不可能取到比Pi 更小的號碼。若兩行

9、程所取到的號碼相同，表示 Pj 在 Pi 進入臨界區前已經在進行取號碼牌的動作了，根據麵包店演算法，Pi 會等到所有正在取號碼牌的行程都取完號碼才開始比較號碼，Pi 能進入臨界區執行就表示 i j。因此我們可以知道(numberi,i)1)signal(mutex);wait(wait_cut);elsesignal(mutex);signal(cutHair);剪頭髮;wait(mutex);customer_cnt-;if(customer_cnt 0)signal(wait_cut);signal(mutex);理髮師的虛擬程式碼：while(true)wait(cut_hair);剪頭

10、髮;19著作權所有 旗標出版股份有限公司行程間通訊與同步-進階題10Q：請證明避免死結的安全演算法需要O（m n2）的運算才能夠完成A：安全演算法的步驟 2 可能需要執行 n+(n-1)+(n-2)+2+1=n(n+1)/2 次，而每次的執行都需要檢查 m 種資源，所以安全演算法需要O（m n2）的運算才能夠完成。20著作權所有 旗標出版股份有限公司行程間通訊與同步-進階題11Q：一個系統中有 5 個行程競爭 R 資源，系統中目前仍有 6 項 R 資源尚未配置，而每個行程最多只需要兩項 R 資源即可完成工作，請說明系統中的這 5 個行程不會發生死結。如果行程至多需要 3 項 R 資源才能完成工

11、作的話，則系統中至少需要幾項 R 資源行程才不會發生死結A:死結發生的必要條件之一是佔用與等待，這 5 個行程最差的情況是各佔用 1 項 R 資源並等待另 1 項 R 資源，因為系統中有 6 項 R 資源尚未配置，因此仍會有 1 項 R 資源可以配置而讓其中一個行程完成工作，所以並不會發生死結。同理，如果行程需要 3 項 R 資源的話，最差的情況是每個行程都佔用 2 項 R 資源並等待另 1 項 R 資源，為了不使系統發生死結，所以必須要有另外 1 項 R 資源可以配置，因此系統中最少需要 11 項 R 資源。21著作權所有 旗標出版股份有限公司行程間通訊與同步-進階題13Q：請舉例說明死結偵

12、測演算法如何偵測死結。A：假設系統中有兩個行程 P1、P2與 5 個資源 R1，P1 目前持有 2 個R1，而 P2 持有 1 個R1。P1 現在想請求 3 個 R1以完成工作，P2也想請求 3 個 R1。此時，各陣列的值如下：Available0=2 Allocation00=2,Allocation10=1 Request00=3,Request10=3將這些值代入死結偵測演算法中：1.宣告Work 與 Finish陣列下：Work0=2、Finish0=FALSE、Finish1=FALSE2.Finish0=FALSE，但是 Request00 WORK03.Finish1=FALSE

13、，但是 Request10 WORK04.Finish1=FALSE、Finish2=FALSE，表示系統已經發生死結22著作權所有 旗標出版股份有限公司第4章 記憶體管理23著作權所有 旗標出版股份有限公司記憶體管理 進階題1o請參考好搭檔系統的記憶體搜尋程式碼，以遞迴形式完成好搭檔系統的記憶體釋放虛擬程式碼假設m指向所要釋放的記憶體分割區，i表示該分割區的長度為2i：merge_hole(*m,i)if(i H)/超過區塊上限return;if(可用清單中相鄰的洞n長度也是2i)m=m+n;merge_hole(m,i+1);else將m放入可用清單中;24著作權所有 旗標出版股份有限公司

14、記憶體管理 進階題2Q：請解釋內部碎片與外部碎片的發生原因有何不同，哪一種碎片可以完全消除？A：兩種碎片的發生：外部碎片：因為行程持續地被載入與置換，使得可用的記憶體空間被分割成許多不連續的區塊。雖然記憶體所剩空間總和足夠讓新行程執行，卻因為空間不連續，導致程式無法載入執行內部碎片：發生在以固定長度分割區來進行配置的記憶體中。當一個程式載入到固定大小的分割區時，假如程式小於分割區，則剩餘的空間將無法被使用，稱為內部碎片利用聚集或分頁可以消除外部碎片。25著作權所有 旗標出版股份有限公司記憶體管理 進階題3Q：考慮一個置換系統，在記憶體中包含許多可用的空間且順序如下：10 KB、4 KB、20

15、KB、18 KB、7 KB、9 KB、12 KB 與 15 KB，在先適法、次適法、最適法、與最不適法下，如何依序配置（a）12 KB（b）10 KB（c）9 KB 的記憶體需求？(配置區域，剩餘空間配置區域，剩餘空間)演算法12KB10KB9KB先適法20 KB，8 KB10 KB，0KB18 KB，9 KB次適法20 KB，8 KB18 KB，8 KB9 KB，0KB最適法12KB，0KB10 KB，0KB9 KB，0KB最不適法20 KB，8 KB18 KB，8 KB 15 KB，6 KB26著作權所有 旗標出版股份有限公司記憶體管理 進階題4Q：假設每一分頁大小為 4 K，請問下列這些

16、 16 進位的邏輯位址分頁碼與頁偏移各是多少？n20000n32768n60000A：分頁大小為 4 K（212），所以頁偏移量長度為 12 位元這些 16 進位的位址長度為 20 位元，所以頁面編號為8 位元長(a)2000016=0010 0000 0000 0000 00002分頁碼=0010 00002=2016，頁偏移=0000 0000 00002=00016(b)3276816=0011 0010 0111 0110 10002 分頁碼=0011 00102=3216，頁偏移=0111 0110 10002=76816(c)6000016=0110 0000 0000 0000

17、00002分頁碼=0110 00002=6016，頁偏移=0000 0000 00002=0001627著作權所有 旗標出版股份有限公司記憶體管理 進階題7o根據以下分段表的內容，請寫出下列邏輯位址（段編號，位移量）所對應到的實體位址：（a）(0，480)（b）(1，12)（c）(1，36)（d）(2，652)分段基底長度031250012566122352475028著作權所有 旗標出版股份有限公司解答（a）(0，480)：312+480=792（b）(1，12)：2566+12=2578（c）(1，36)：該分段長度只有12邏輯位址超過合法範圍產生定址錯誤的例外中斷（d）(2，652)：3

18、524+652=4176 29著作權所有 旗標出版股份有限公司第5章 虛擬記憶體30著作權所有 旗標出版股份有限公司虛擬記憶體 進階題2Q：假設電腦中有 4 個頁框，下面是其中每個頁面的載入時間、最後存取時間、與參考位元：a.依據FIFO演算法，哪一個頁面將會被替換？b.依據LRU演算法，哪一個頁面將會被替換？c.依據二次機會演算法，哪一個頁面將會被替換？頁框號碼載入時間最後存取時間參考位元0126280112302650214027003110285131著作權所有 旗標出版股份有限公司解答a.頁面3b.頁面1c.頁面232著作權所有 旗標出版股份有限公司虛擬記憶體 進階題4Q：假設有一個行

19、程的頁面使用順序如下：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3若此行程可以使用4個頁框，在純粹需求分頁的情況下，當採用下列不同的分頁替換演算法時，各會產生幾次分頁錯誤？a.FIFO演算法b.LRU演算法c.最佳演算法A：a.14 次b.10 次c.9 次33著作權所有 旗標出版股份有限公司虛擬記憶體 進階題5Q：如果記憶體中有 4 個頁框，每個頁框的大小為 200 個位元組，一個整數佔有2個位元組，其中一個頁框固定給下列程式碼使用。如果陣列是以列優先方式存放在記憶體中，則執行此程式會發生多少次分頁錯誤？如果把程式碼 Aij 改成 Aji，那麼會有多少次分頁錯誤

20、？int A100100;for j=1 to 100for i=1 to 100Aij=0;34著作權所有 旗標出版股份有限公司解答每個頁框可存放 200/2=100 個整數。若以原本程式碼的執行順序，內層 i 迴圈每執行一次便發生一次分頁錯誤，再加上外層迴圈執行，共會發生 100 x 100 =10000 次分頁錯誤。若程式碼由Aij 改成 Aji，一層 j 迴圈只發生一次分頁錯誤，故共會發生 1 x 100=100 次分頁錯誤。35著作權所有 旗標出版股份有限公司虛擬記憶體 進階題7Q：在一個頁面大小為 4096 位元組的系統中，假設有一個行程的程式碼大小為 32768 個位元組，資料大

21、小為 16386 個位元組，堆疊大小為 15870 個位元組1.這個行程一共需要幾個頁面？若分頁表每個項目的長度為4位元組時，分頁表的總長度為多少？2.如果分頁大小變成 512 位元組，狀況又如何？36著作權所有 旗標出版股份有限公司解答1.當 頁面大小為 4096 位元組時o程式碼需 32768/4096=8 個頁面o資料需要 16386/4096 約 5 個頁面o堆疊需要 15870/4096 約 4 個頁面o總共需要8+5+4=17 個頁面o因為分頁表的每個項目為 4 個位元組，所以一共需要 17 x 4=68 個位元組2.當頁面大小為 512 位元組時o程式碼需 32768/512=6

22、4 個頁面o資料需要 16386/512 約 33 個頁面o堆疊需要 15870/512 約 31 個頁面o總共需要64+33+31=128個頁面o分頁表的長度為128 x 4=512 個位元組，剛好佔據一個頁面37著作權所有 旗標出版股份有限公司虛擬記憶體 進階題9Q：一個有 32 位元位址的系統裡使用兩層式分頁法，一個邏輯位址分成 3 個部分，最前面 9 個位元為外層分頁表的索引，中間 11 個位元為內層分頁表的索引，剩餘的為頁偏移，請問每個頁面的大小？系統的位址空間多大？A：外層索引內層索引 頁偏移 9 11 12因為頁偏移有 12 位元，所以一個分頁的大小為212=4 K位址空間為 2

23、9*211*4 K=4 GB 38著作權所有 旗標出版股份有限公司虛擬記憶體 進階題11Q：假設採用分頁的方法來管理記憶體，存取 TLB 所需的時間為 50 ns，TLB 的擊中率為 75%，存取記憶體的時間為 750 ms。請算出記憶體有效的存取時間？A：0.75*(50+750)+0.25*(750+750)=600+375=975(ns)39著作權所有 旗標出版股份有限公司第6章 檔案系統40著作權所有 旗標出版股份有限公司檔案系統 進階題5Q：當一個目錄的存取權限被其擁有者所更改時，該目錄中的檔案以及子目錄的存取權限是否應該跟著改變？為什麼？A：否。由於可能有其他目錄連結到該目錄中的檔

24、案及子目錄，若修改該目錄的存取權限，其檔案及子目錄也跟著改變，有可能造成其他目錄的連結發生錯誤。在 Linux 的系統中，更改目錄存取權限時必須要加入-R 的指令，則其目錄中的檔案及子目錄的存取權限才會跟著改變。若沒有加入-R 的指令，則只會針對該目錄進行修改。這種做法是由使用者自行決定是否要將欲修改目錄中的檔案以及子目錄的存取權限一起改變。41著作權所有 旗標出版股份有限公司檔案系統 進階題6Q：在多個使用者共享的目錄中，其中一個使用者所建立的子目錄或是檔案的擁有者應該是該使用者，或是父目錄的建立者？為什麼？A：基於保護的考量，這個檔案或目錄的擁有者應該是建立該物件的使用者。例如在 Linu

25、x 的環境下，其使用者所建立的子目錄或檔案屬於該使用者，而其父目錄的建立者，則有刪除該子目錄或檔案的權限。42著作權所有 旗標出版股份有限公司檔案系統 進階題7Q：在一般圖狀的目錄結構中，因為符號鏈結可以連結到任意的目錄，所以在一個目錄中搜尋檔案時就會有進入無窮迴圈的可能，有哪些方法可以解決此問題？A：利用在搜尋檔案時判斷該目錄是否已經被搜尋過，來避免無窮迴圈的發生。或是在搜尋檔案時預先規定搜尋的目錄深度，在超過一定層次的子目錄後就不再繼續往下一層目錄搜尋，如此一來就可以避免檔案搜尋陷入無窮迴圈的困擾。43著作權所有 旗標出版股份有限公司檔案系統 進階題8Q：可否將同一個檔案系統掛載在檔案系統

26、的不同目錄中？可能會有什麼問題發生？A：不可以。若將同一個檔案系統掛載在不同目錄中，則會發生多個路徑指向同一個檔案，造成使用上的困難及在刪除時發生問題。44著作權所有 旗標出版股份有限公司檔案系統 進階題12Q：如果有二個以上的使用者同時開啟並修改了一個共享檔案的資料內容，會有什麼錯誤發生？如何避免這種錯誤的發生？A：先將檔案資料回存的使用者可能會失去其所修改的結果（被後回存的使用者覆蓋）。可以利用檔案鎖定機制來避免這種問題。45著作權所有 旗標出版股份有限公司第7章 裝置管理46著作權所有 旗標出版股份有限公司裝置管理 進階題4Q：在RAID 4的架構下，假設D4是用來存放同位位元的磁碟，且

27、磁碟D1運算前後的位元值為D1與D1，則新的同位位元的計算方式為：D4(i)=D1(i)D1(i)D4(i)請證明之。A：因為D1(i)=D0(i)D2(i)D3(i)D4(i)D0(i)D2(i)D3(i)=D1(i)D4(i)D4(i)=D1(i)D0(i)D2(i)D3(i)=D1(i)D4(i)D1(i)47著作權所有 旗標出版股份有限公司裝置管理 進階題10Q：假設磁碟驅動器具有 5000 個磁住，編號從 0 到 4999，現今磁頭正在服務磁柱 143 的要求，而前一次的要求是磁柱 125。如果佇列中未服務的要求以 FIFO 的次序排列如下：86、1470、913、958、1590、

28、1022、1657、173由目前的讀寫頭位置開始，對於下列的每一種磁碟排程演算法，它的磁碟臂的移動總距離（以磁柱數為單位）是多少？nSSTFnSCANnC-SCANnLOOKnC-LOOK48著作權所有 旗標出版股份有限公司習題解答oSSTF 1688。n143-173-86-913-958-1022-1470-1590-1657。oSCAN 9769。n143-173-913-958-1022-1470-1590-1657-4999-86。oC-SCAN 9941。n143-173-913-958-1022-1470-1590-1657-4999-0-86。oLOOK 3085。n143-1

29、73-913-958-1022-1470-1590-1657-86。oC-LOOK 3085。n143-173-913-958-1022-1470-1590-1657-86。49著作權所有 旗標出版股份有限公司裝置管理 進階題11Q：什麼樣的應用程式或磁碟存取的模式，對於 SSTF、SCAN 和 C-SCAN演算法有最短的磁碟臂移動距離？為什麼？A：對於SSTF，當大部分要求存取的位置集中於磁碟某一小區段時，因為位置都很相近，所以有最短的磁碟臂移動距離。SCAN 及 C-SCAN 因為本身的演算法就必須要來回於磁碟的最內側及最外側，所以對於不同的應用程式或磁碟存取的模式，都不會縮短磁碟臂移動距

30、離。50著作權所有 旗標出版股份有限公司第八章 安全性51著作權所有 旗標出版股份有限公司安全性-進階題2Q：如果只使用小寫字母與數字，可以建立多少種長度為6個字元的密碼？假設嘗試一個密碼（輸入並得到接受或拒絕）的時間是1 ms，破解6個字元長度密碼的平均時間為多久？A：366=2,176,782,336種破解密碼的最短時間：1ms（第一次就猜中）破解密碼的最長時間：2,176,782 s（最後一次才猜中）=平均的破解時間為：1,088,391秒52著作權所有 旗標出版股份有限公司安全性-進階題3Q：請指出下列威脅是屬於中斷、攔截、篡改、或偽造？n列印大量無用的長檔案來佔用列表機n建立一個虛構

31、銀行戶頭，將所有其他帳戶餘額的零頭（個位數）轉入這個戶頭n監聽網路以蒐集帳號與密碼n冒充學校送出愚人節停課的公告郵件給所有師生A：n中斷n篡改（其他帳戶餘額）與偽造（新帳戶）n攔截n偽造53著作權所有 旗標出版股份有限公司安全性-進階題4A：為什麼發動像阻絕服務之類的中斷攻擊，通常比入侵一台電腦要容易？Q：因為中斷服務只要利用大量的正常服務請求，就可以癱瘓伺服器的運作，而不需要深入瞭解被攻擊系統內部的設定或漏洞。但是要入侵一台電腦，則必須對該台對腦的組態、漏洞、或是使用者資訊等有比較深入的瞭解。54著作權所有 旗標出版股份有限公司安全性-進階題5Q：如果病毒必須被執行才能感染，為什麼Word之類的文書檔也能傳播病毒呢？A：這是因為這類文書編輯程式通常都支援包含可執行程式碼的巨集指令，所以病毒可以透過這類檔案的巨集來傳播。55著作權所有 旗標出版股份有限公司