iT邦幫忙

0

【小黑馬作業系統考古】範圍: 恐龍書第五章~第七章

<撰文緣由>: 作業系統是當今資工重要科目,
然而讀了上課講義、恐龍書,
卻無法有效檢測自己讀懂了沒,
即便於網上找了考古題,
卻苦於無人整理正確答案,
無法知道自己是否理解正確。

小馬將整理自己一學期來修課及準備考試的心路歷程,
期由【小黑馬作業系統考古】整理真實考試常出現的問題,
幫助莘莘學子準備作業系統科目。
(如有發現答案有錯可不吝告訴小馬,小馬不勝感激)

<整理範圍>: 恐龍書第五章~第七章,內容涵蓋:
Ch5 排程 (CPU scheduling)
Ch6 程式同步問題 (synchronization)
Ch7 死結 (deadlock)

題目統整(以下題目與答案間刻意留白,方便有心練習的人先思考後再對答案)

【清大博士班資格考- 2011秋】
Please give short description for the following terms:
(a) preemptive and non –preemptive
(b) Interrupt and Trap
(c) Time sharing
(d) What is the relationship between (a) and (c)
(e) What is the relationship between (b) and (c)





答案解析:
(a)

  • preemptive: 程式在CPU burst time 結束前,可以被其它程式搶先執行
  • non-preemptive: 程式在CPU burst time 結束前,不可以被其它程式搶先執行

(b) trap 和 interrupt都是打斷CPU工作的「打斷源」,但trap通常指來自軟體的打斷,interrupt通常指來自硬體的打斷。
(c) Time sharing指的是OS讓很多process可以同時執行的機制
(d) 透過程式可以被打斷的機制,達成Time sharing system希望每支程式可以輪流的執行到的需求,比如說RR scheduling
(e) Time sharing 的系統會固定時間發送interrupt以觸發scheduler 做 context switch.




【清大博士班資格考- 2016春】
In most modern OSs including windows and Linux, they tend to increase the scheduling priority for the jobs that return from sleep or I/O operations. What is the reason for that?





答案: 因為sleep or I/O特別耗時,先做它則可以空出CPU給其它程式使用




【清大博士班資格考- 2016春】
(a) What is the difference between a preemptive scheduling and non-preemptive scheduling?
(b) Why preemptive scheduling usually can achieve better system performance?
(c) Why non-preemptive scheduling can prevent “kernel synchronization”?






答案:
(a) 差別在程式在CPU brust time 之是否可被其它程式搶先。Preemptive可以,non-preemptive 不行。
(b) 因為用preemptive 排程的演算法可以設計的更有彈性,避免單一程式執行時間過長霸占CPU
(c) 因為可以避免在memory的值不穩定之前就進行context switch



【清大博士班資格考- 2016春】
The following code presents a synchronization solution for two processes, i=0 or 1. Does this code satisfy all critical section requirements? If yes, please prove it. Otherwise, please explain which requirement(s) it violates. (Notice that Line3 is modified from the Peterson’s solution.)
https://ithelp.ithome.com.tw/upload/images/20200115/20117114SiubPMA3NH.png





答案:
會違反bounded waitng。假設P0想進入CS,P1可以賴皮似的一直重複搶進CS,當P1離開CS時,雖然將flag[1]設為FALSE,但是馬上緊接著做flag[1]=TRUE; turn=1,於是P1又可以再度進入CS,如此反覆。


【清大博士班資格考- 2016春】
(a) What is the difference between deadlock avoidance and deadlock prevention?
(b) Give a solution to prevent deadlock by removing the “circular wait” condition
(c) Prove the correctness of your solution briefly.





答案:
(a)

  • deadlock prevention: 在OS的排程設計上,避開deadlock 的四個必要條件: mutual exclusion, hold and wait, no preemption, circular wait
  • deadlock avoidance: 在process 發出資源請求時,確保存在Safe sequence 以避免deadlock (即Banker's algorithm 做的事)

(b) 假設有resource R1, R2,…, Rn,則任何process在要資源Rj之前,必須先把index大於j的資源都放掉
(c) 假設會產生deadlock,即P0等P1,P1等P2,…Pn等P0,並假設Pi握有的資源的index為ai,則根據我們的解法,a0<a1<a2<…<an<a0,矛盾。


尚未有邦友留言

立即登入留言