高考申論題
111年
[電力工程] 計算機概論
第 二 題
📖 題組：
假設在時間 0 的時候，行程（process）P1，P2，P3，P4，P5，依序進來系統。其需要的 CPU 處理時間（burst time）和優先權（priority）的資訊如下表： Process Burst time priority P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 分別使用 FCFS、SJF、nonpreemptive priority（數字小代表優先權高）、RR（quantum 為 1）的排程演算法，詳細畫出甘特圖（Gantt chart）表示執行這些行程所需時間。每單位時間執行那個行程必須標示清楚。（20 分）
假設在時間 0 的時候，行程（process）P1，P2，P3，P4，P5，依序進來系統。其需要的 CPU 處理時間（burst time）和優先權（priority）的資訊如下表： Process Burst time priority P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 分別使用 FCFS、SJF、nonpreemptive priority（數字小代表優先權高）、RR（quantum 為 1）的排程演算法，詳細畫出甘特圖（Gantt chart）表示執行這些行程所需時間。每單位時間執行那個行程必須標示清楚。（20 分）
📝 此題為申論題，共 3 小題
小題 (二)
那如果春嬌收到信後，回確認信給志銘說會準時赴約，那請問春嬌按約定時間到達約會地點時，她能確定志銘一定會在那邊嗎？會或不會，都請解釋原因。（5 分）
思路引導 VIP
進入兩軍問題的第二階段：加入了確認機制 (ACK, Acknowledgement)。 思考邏輯：春嬌收到了信，並且回信（發送 ACK）。此時春嬌知道約會資訊，她會去。但題目問的是「她能確定志銘一定在那邊嗎？」。志銘要赴約的前提是他必須知道春嬌願意來。如果春嬌的「回信」遺失了，志銘會以為春嬌沒收到信而不去。春嬌自己寄出回信後，無從得知回信是否成功送達志銘手上。因此，春嬌去的時候，心裡會忐忑不安，無法確定志銘是否在那邊。答案是「不會」。
小題 (一)
志銘跟春嬌是很好的朋友，有邀約的話一定會欣然赴約。現在志銘想要跟春嬌約會，因為沒有網路，所以用傳統寫信的方式，寄給春嬌跟她約定約會的時間與地點。但因為傳統寄信的方式，可能因為某些因素，信件沒有送達或延遲很久時間才送達。那麼請問志銘如果按照他定的時間地點準時赴約，春嬌一定會去嗎？會或不會，都請解釋原因。（10 分）
思路引導 VIP
本題雖然包裝成愛情故事，但實質上是計算機網路與分散式系統中非常著名的「兩軍問題 (Two Generals' Problem)」。 在第一小題中，志銘是發送端 (Sender)，春嬌是接收端 (Receiver)。通訊通道是不可靠的（信件可能遺失）。
小題 (三)
繼上述，那如果志銘有收到春嬌的確認信後，再回信說，讚，我一定會去的。請問那這次，兩個人都會確定對方一定會準時到現場赴約嗎？請分析各種可能性。（5 分）
思路引導 VIP
進入兩軍問題的核心結論：無論來回確認幾次，共識都不可能完美達成。 思考邏輯：現在志銘發送了 ACK 的 ACK。志銘確定春嬌知道約會了，但他不確定春嬌是否收到他的「讚」。如果春嬌沒收到「讚」，春嬌又會回到上一題的狀態（不確定志銘有沒有收到確認信）。為了解決這個疑慮，春嬌又要發送一個 ACK 給志銘的「讚」...這會陷入無窮迴圈。這就是分散式系統的定理：在不可靠通道上，不可能透過有限次的訊息交換達到 100% 的完美共識。