[理工] 100台大資工
作者: galapous (墨) 2015-01-28 21:52:58
這份有幾題想請教大家，
DS&ALGO
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100418.pdf
1(c) binary tree的delete可以取左子樹最大或右子樹最小來取代，所以這題是要都
畫出來嗎？或是自己假設可選擇時哪種優先在畫出來這樣？
2(b) 想問successful search是要把紅黑樹當作平衡的情況下去算平均搜尋次數嗎？
我的想法是1*1+2*2+3*4....+logn*2^([logn)-1]
(n代表阿發,我不會打XD)
CA&OS
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100417.pdf
1. 這題想討論的是multiprocessor(不是題目中提到的SMT)和multicore的差異，
估狗查到multicore有自己的運算單元跟L1cache而L2cache有可能是共享的，
想問假如都是在同一台電腦，2-core processor跟2顆單core processor執行程式
的能力差在哪呢？
附上估狗參考資料:
![]()
(內容有提及此題SMT的部分)
3(c) 這題要提出兩個解決race condition並且避免polling的方法，
只想到disable interrupt，還有什麼方法方法不會用到spinlock的嗎?
4(a)(b) 爬過文有討論到這題但還是不太清楚，題目所謂200ms in average to
complete its computation是單指CPU time還是包含等待I/O的時間？
然後要如何判斷是否要migrate到別的core上？
感謝看完。
DS&ALGO
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100418.pdf
1(c) binary tree的delete可以取左子樹最大或右子樹最小來取代，所以這題是要都
畫出來嗎？或是自己假設可選擇時哪種優先在畫出來這樣？
2(b) 想問successful search是要把紅黑樹當作平衡的情況下去算平均搜尋次數嗎？
我的想法是1*1+2*2+3*4....+logn*2^([logn)-1]
(n代表阿發,我不會打XD)
CA&OS
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100417.pdf
1. 這題想討論的是multiprocessor(不是題目中提到的SMT)和multicore的差異，
估狗查到multicore有自己的運算單元跟L1cache而L2cache有可能是共享的，
想問假如都是在同一台電腦，2-core processor跟2顆單core processor執行程式
的能力差在哪呢？
附上估狗參考資料:
(內容有提及此題SMT的部分)3(c) 這題要提出兩個解決race condition並且避免polling的方法，
只想到disable interrupt，還有什麼方法方法不會用到spinlock的嗎?
4(a)(b) 爬過文有討論到這題但還是不太清楚，題目所謂200ms in average to
complete its computation是單指CPU time還是包含等待I/O的時間？
然後要如何判斷是否要migrate到別的core上？
感謝看完。
作者: qoojordon (穎川琦) 2015-01-28 22:44:00
OS,3c 我不太確定是不是nonbusy wait的那種semaphore?
作者: galapous (墨) 2015-01-28 22:58:00
我也在猜是不是要答那個,但它不是底層c.s.其實還是會用到spinlock
作者: zero0o0o8279 2015-01-29 01:34:00
Message passing?
作者: killerw74 (killerw74) 2015-01-29 02:22:00
第二題b應該是直接用紅黑樹的search就好吧 ！lognMultiprocessor 之間的資源分享沒有像 multicore那麼好吧！在我理解中，Multiprocessor 可以執行一個以上的程式而multicore則讓一個程式內的thread 共用全部資源 以達到最高效率
作者: galapous (墨) 2015-01-29 08:00:00
第二題b不是unsucessful search才會每次都找到最後@@multicore的部分共用資源是指什麼資源呢？不太清楚第四題我寫的時候想法也是這樣,但看以前的討論的答案是相反,附上文章編號#1F9jz58O第二題b成功搜尋應該有可能發生在紅黑樹中的任何節點?所以我才想說是不是要平均起來算,但紅黑樹又不算平衡樹搞不太清楚怎麼下手
作者: killerw74 (killerw74) 2015-01-29 12:05:00
第二題我以為你問unsuccessful search....平均成功搜尋不知怎求..但wiki上也只寫logn而已multicore共用資源類似L2cache可以存放code以全域變數但我看了網路上解答，也覺得有道理，這題感覺講太不明我本來也寫類似那文章的答案應該看你怎麼假定八 如果50ms還沒運算完就是上面答案如果50ms已經在io等待，就是那文章寫的答案吧!
作者: cvbndbjzxcv (藍天) 2015-01-30 12:46:00
1.c 洪逸是說沒講就都畫出來 但是我寫好幾間的答案都是拿左子樹最大的概掉