作者wheels ()
看板Grad-ProbAsk
標題Re: [理工] [OS]台大100 第四題
時間Tue Jan 31 02:19:47 2012
※ 引述《DiLegend (JOU)》之銘言：
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100417.pdf
: 第四題
: a跟b完全不知道該怎麼處理
: c的演算法
: 一個要minimize average response time
: 一個要real time
: 是一個SJF 一個FCFS嗎?
a.
computation intensive表示thread幾乎都在使用cpu作運算，
如果將一個已經完成50ms的thread migrate給另一個core的話，
則原本core的cache對這個thread的block要清除(or write back)，
且另一個core的cache要重新fetch block for this thread，
然後thread才可以開始繼續運算。
在這種情況下thread在new core裡要idle一段不小的時間for cache miss，
且原core也要花時間清除cache，沒辦法馬上對下一個thread開工。
這些時間對幾乎都在使用cpu運算的thread而言是很大的idle。
b.
I/O intensive表示thread幾乎都在等待I/O，用cpu運算的時間很少。
如果將一個已經完成50ms的thread migrate給另一個core的話，
則此thread還在等待I/O的機會非常高，也就是它正在waiting queue裡。
雖然原本core的cache可能也要把這個thread的block清空，
但是它可以在下一個thread作I/O的時候把原thread的block清除(or write back)，
(or下下個 or下下下個，只要在migrate過去的thread要開工前把cache清完就好)
這樣原core不需要有thread ready卻要等core清cache的多餘時間，
而new core也可以在thread I/O時prefetch block進cache裡，
這樣I/O完成就可以馬上開工不需要有額外的等待時間。
(ab推文中有更深入的想法。)
c.
要minimize average response time要用RR，
要support real-time要用preemptive priority或是multilevel queue等
可以支援preemptive priority者。
其實c的問法會讓人想回答
"preemptive priority queue給越晚到的process越高priority"，
因為這種如果用這種scheduling那average reponse time幾乎是0。
不過開公司的話應該不能這樣搞XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.24.171.176
※ 編輯: wheels 來自: 114.24.171.176 (01/31 02:50)
推 onlyeric23:感謝說明 01/31 13:19
推 robert527152:對於ab有其他想法，不過想問一下你的想法的根據是? 01/31 14:55
→ wheels:根據就是migrate需要考慮各core的cache問題。 01/31 15:58
→ wheels:為了避免這個問題，才會有所謂的processor affinity。 01/31 16:00
→ wheels:也就是能盡量避免migration就盡量避免。 01/31 16:00
→ wheels:要不要說說看你的想法一起討論？ 01/31 16:01
→ robert527152:喔隊先問一下你是輪子嗎XD我是那個學弟 02/01 00:15
→ robert527152:其實關於multicore的load balancing與affinity的衝突 02/01 00:16
→ robert527152:我今天花了半個下午在網路上找paper= =，得出的結論 02/01 00:16
→ robert527152:是linux在origin上對於一個thread是否要migrate 02/01 00:17
→ robert527152:取決於cache是hot還是cold，若是cold表示cache 02/01 00:18
→ robert527152:沒有使用必須有額外的cost.之類的 02/01 00:21
→ robert527152:所以我覺得cpu要migrate i/o則否，其實還有好多內容 02/01 00:24
→ robert527152:可以討論，要不然站內信吧 02/01 00:24
→ wheels:對我是XD 竟然遇到熟人XD 02/01 13:03
※ 編輯: wheels 來自: 140.112.30.141 (02/01 13:10)
→ wheels:我是只引用migrate層面來解讀它，要往更深入應該要照你說的 02/01 13:11
→ wheels:沒錯:) 02/01 13:11
→ robert527152:因為其實對於這個問題其實是一個很廣的研究@@台大出 02/01 14:03
→ robert527152:這題好奇怪QQ 他會有很多種演算法來決定 02/01 14:04
→ wheels:而且才配3分，似乎就是要你掰東西給它XD 02/01 14:16