作者YankSC (′‧ω‧‵)
看板Grad-ProbAsk
標題Re: [理工] 97台大電機OS 同步問題~
時間Fri Jan 28 00:26:50 2011
以下為個人淺見
※ 引述《cutesteven (原野漫遊)》之銘言：
: 我有2題97電機丙OS想問
: 1.同步問題
: http://ppt.cc/rnpH
: 此題想問這題是否滿足同步所有條件
: 本來想說若count讀到相同的值則p0 p1就可能通過while判斷而違反mutual exclusion
: 可是題目已說這是mutual exclusion的"distributed system"@@
: 而我感覺是progress也沒有違反?
: 請教各位了~
Mutual Exclusion:
題目是Distributed System. 依照題義應該沒有問題 ok
Progress:
1. Remainder Section 不參與 Critical Section 決策過程 ok
因為一出Critical Section就重設為零了
2. Decision time is limited ok
一設為零，在busy-waiting的另一個就進了
Bounded Waiting:
alternately enter? 再重複進入之前設為零，就放另一個進去了 ok
答案選 (E) 均滿足
: 2.http://ppt.cc/Q~C4 (單選)
: 想問B選項.system call是特權指令嗎?
: D選項.SJF
: 哪個是錯的@@
A. Working Set可用來調配degree of Multiprogramming並控制thrashing
B. System Call是Process和OS之間的Communication interface.
OS透過 System Call ID 查表再啟動Service Routine回傳結果.
此題意指針對「以特權指令的權限」執行的System Call
user program 不可任意使用。
C. 階層式記憶體的確沒有保證資訊的取回。(待高手補強)
D. SJF是擁有future knowledge的optimal algorithm
E. 正確，可能諸如Hard Real-Time System的Instruction Set就不支援
答案選(D)
有錯還請版友指教 謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.176.27
1F：→ cutesteven:感謝原PO 我是在想C他寫"may not" 沒有特例可能滿足? 01/28 00:35
2F：→ YankSC:沒有。 SJF 是Best Case拿來當比較依據用的。 01/28 00:49
3F：→ YankSC:無論如何越短的Process越快執行完 後面所有的wait都變短 01/28 00:50
4F：→ YankSC:是可以被證明的 01/28 00:50
5F：→ dy957:我被搞混了 17943似乎有說a是錯的@@? 01/28 00:53
6F：推 cutesteven:我突然想到SRJF(可插隊的SJF)似乎waiting time更短? 01/28 01:09
7F：→ YankSC:或許是我錯了! 01/28 01:09
8F：→ cutesteven:可是我剛看17943 我認為A沒有問題@@ 01/28 01:10
9F：→ dy957:我是覺得working set不會改變process數目,只會更動page數 01/28 01:13
10F：→ dy957:所以嚴格來說不算更改mult-programming? 01/28 01:13
我重新整合一下題義的Ambiguity
對於Degree of Multiprogramming的定義
是可以簡單定義為「正在系統中執行的Process數量」
但對於系統來說，他是如何調配有多少程式可以執行呢？
系統中的Physical memory固定，調配Working Set Size的個數
會使每個Process所擁有的Page改變 在Summary不變情況下 只能更動Process個數
也就是現在的「Degree of Multiprogramming」
若是定義為「系統目前的狀態」 的確不能任意改變
但利用Working set間接的改變是可行的
再來是對於SJF的Ambiguity。
SJF is optimal in non-preemptive scheduling 沒有問題
證明如下
For each dispatched process, waiting time =
1st: 0
2nd: x1
3rd: x1 + x2
4th: x1 + x2 + x3
...
nth: x1 + x2 + ... + xn-1
=> Total waiting time
= (n-1) x1 + (n-2) x2 + ... + (2) xn-2 + (1) xn-1 + (0) xn
為了最小化 Xi 必須讓被乘的次數越少越好
但實際上，SRJF也算是SJF的一種。
--
有錯請指教 謝謝
※ 編輯: YankSC 來自: 114.25.176.27 (01/28 01:31)