Re: [理工] OS幾個問題

[HiltonCool (野獸瘋)]

※ 引述《j897495 (咪咪)》之銘言：
: (1)Suppose a non-preemptive scheduler uses variable priorities
: and time quanta as the following table,where the highest priority is 5
: Priority   Time quantum     New priority after         New priority after
:                          time quantum is expired       returning from I/O
:     5           40                   4                          5
:     4           60                   3                          5
:     3          100                   2                          4
:     2          200                   1                          4
:     1          320                   1                          3
: Which of the following statements is "incorrect"?
: (A)Response time of interactive threads will increase.
: (B)Priorities of CPU-intensive threads will be lowered.
: (C)Time-quanta of I/O-bound threads will decrease.
: (D)None of the above.
  首先判斷這樣的排班法則是偏好 I/O-bound job 還是 CPU-bound job
  若一開始的優先權值為 3，則：
  (1)I/O-bound job：
     執行 100 單位 CPU computation 之後 time-out 被迫放掉 CPU
     等到下一次從 waiting queue 回來之後的優先權值會變成 4
     再執行 60 單位 CPU computation 之後 time-out 被迫放掉 CPU
     等到下一次從 waiting queue 回來之後的優先權值會變成 5
     再執行 40 單位 CPU computation 之後 time-out 被迫放掉 CPU
     所以每一次 time-out 回來之後可執行的 CPU computation 單位會逐漸遞減

  (2)CPU-bound job：
     執行 100 單位 CPU computation 之後 time-out 被迫放掉 CPU
     等到下一次從 waiting queue 回來之後的優先權值變成 2
     再執行 200 單位 CPU computation 之後 time-out 被迫放掉 CPU
     等到下一次從 waiting queue 回來之後的優先權值變成 1
     再執行 320 單位 CPU computation 之後 time-out 被迫放掉 CPU
     所以每一次 time-out 回來之後可執行的 CPU computation 單位會逐漸遞增

  從上述分析可以看出來這樣的排班法則是偏好 CPU-bound job

: 我的想法是Response time是第一次回應時間 所以RR的Quantum就是Response time
: 但優先權2和1的Process變為同樣優先權所以A是錯的
  因為 interactive threads 所需要的 CPU time 較少
  所以是屬於 I/O-bound job
  而此種排班法則是偏好 CPU-bound job
  所以對於 I/O-bound job 的 response time 會比較長
  所以(A)是正確的

: B的話CPU就是和I/O的優先權值相反  這樣對嗎?
  感覺上 CPU-intensive threads 應該是指這樣的 thread 是屬於 CPU-bound job
  因為沒有看過這個詞，所以我猜測應該是這個意思
  如果是基於這樣的假設條件的話，那這種 thread 的優先權值會逐漸降低是沒錯的
  所以(B)是正確的

: C的話我就不知道要看哪一個了
  由上述判斷可知 I/O-bound threads 的 time-quantum 會逐漸遞減
  所以(C)是正確的

  所以此題答案為(D)

: (2)另外我想知道有沒有開放式課程是講同步問題的MAILBOX
: 有點不是很清楚Blocking receive  ,  Non-Blocking receive之類system call的用法
: 還有分類題庫有看到的serializable transaction問題洪逸好像也沒教過
: 不知道有沒有網頁講的比較清楚的呢
: 謝謝各位撥空看我的問題
: 希望可以獲得解答^^

  這部分的話因為 OS 是歸類在 Process Synchronization 這一章
  而洪逸在講這一章的時候是著重在 Memory Sharing 的部分
  感覺他只用了 5% 左右的時間講 Message Passing 的部分
  其實只是簡單帶過而已
  如果是 for 研究所考試的話，我覺得洪逸的筆記大概看過，稍微了解一下就好
  畢竟考試大部分都考在 Memory Sharing 的部分
  但如果是要深入了解 Message Passing 的詳細內容、運作過程的話
  可能要找跟網路相關的課程吧...我也不知道XD

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.190.81
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1418665329.A.D04.html
推 j897495: 謝謝你詳細的解說 有幾點還是不太懂
→ j897495: 為什麼I/O是100》60》40這樣看而coy bounded-job是相反呢
→ j897495: Cpu 打錯XD
→ j897495: Interactive thread看到就是把它當成I/O bounded就好嗎
推 j897495: Cpu interactive threads就當成cou bounded job嗎
→ j897495: 因為我好像沒看過interactive thread這個詞
→ j897495: 這題答案書上是給A 但沒寫解析我也不知道為什麼XD
→ j897495: 這題是指5個processes還是一個但用不同time slice去看呢
因為 I/O-bound job 大部分的時間都在做 I/O，只有少部分時間做 CPU computation
所以 I/O-bound job time-out 回來之後的優先權是要看 after returing from I/O
相反的，CPU-bound job 大部分的時間都在做 CPU computation，所以 time-out 之後
會回到 ready queue 等待下一次的執行，所以要看 after time quantum is expired

至於 interactive thread(process) 這個詞我之前有問過洪逸，他是說這種互動型的
process 需要的 CPU time 很短，例如 ATM，我們人在操作提款機的時候可能只需要
幾分鐘的時間，但當我們結束操作之後，它會用大量的時間在處理I/O，像是我們剛剛
對它進行那些操作，對應到它所需要做的工作，洪逸最後說，就把它當 I/O-bound
process 看就對了

而 response time 這個選項我是依照洪逸在解一題交大考古題的時候作為解題依據
那一題跟這一題的題型非常相似，而這類型的題目整本洪逸的題庫也只有兩題
所以我記憶非常深刻，而交大給出來的數據經過分析之後是偏好 I/O-bound job
其中一個選項是 "This scheduling policy gives good throughput for CPU-bound
and good response time for interactive processes."
當時洪逸在講解這個選項時的說法是，因為這種排班法則有利於 I/O-bound job
而它所需要的 CPU time 較短，所以系統一定會先把 CPU 優先分配給此類型 job
所以 I/O-bound job 會有較佳的 throughput 和 response time
所以這個選項的敘述是錯的，而交大給出來的答案也確實沒有這個選項
我的理解是 "good response time" = "response time will decrease"
所以我才會認為(A)選項是錯的
其實課本對於 response time 的定義非常模糊，所以幾乎沒有學校會考 response time
的計算，但是近幾年台大電機瘋狂的考 average response time
連洪逸都不知道要怎麼算，而台大又不給答案的，所以...還是無解
不然我再把這個題目拿去問洪逸好了，或許是我中間有哪個環節出錯了也說不定
推 killerw74: 我覺得這題是io bound 雖然執行時間短 但是在選擇job
→ killerw74: 時 會優先執行優先權高的 。如果是這樣那麼response ti
→ killerw74: me是減少沒錯。
會優先執行優先權高的沒錯，但即使讓 I/O-bound 先執行了，也做不了幾個單位
但如果以第一個回應時間來看的話，I/O-bound 的 response time 值的確會遞減沒錯
不過這樣就跟交大那一題衝突了，一直覺得有哪裡怪怪的
待我向洪逸確認完畢，解開大家心中的疑惑
※ 編輯: HiltonCool (114.42.190.80), 12/17/2014 00:10:46
→ j897495: 這題的確是交大考古  你真的超厲害XD
→ j897495: 先謝謝你這麼熱心幫忙解答!!
疑？！這題是交大的？！可以問一下是哪一年的考題嗎？
整本題庫都翻完了就是沒看到這題，還是洪逸今年沒有收到這題
如果答案是(A)的話，那我就真的疑惑了
※ 編輯: HiltonCool (114.42.190.80), 12/17/2014 01:46:21
→ qoojordon: 交大97 OS , 本來想討論 , 可是題意太不明確惹...
推 j897495: 恩恩是97交大OS沒錯
OK~那我再問洪逸，因為101年也出過一次，所以感覺交大是有可能再考的
※ 編輯: HiltonCool (114.42.182.27), 12/17/2014 12:24:20