高考申論題
112年
[資訊處理] 資料結構
第 二 題
📖 題組：
一、某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外，執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作（由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時，方可執行低優先執行佇列內的工作（由第一個開始執行）。 自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列 | H（低） | G（高） | F（高） | E（低） | D（高） | C（高） | B（低） | A（低） | |---|---|---|---|---|---|---|---| | 1 | 2 | 1 | 1 | 2 | 2 | 1 | 2 |
一、某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外，執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作（由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時，方可執行低優先執行佇列內的工作（由第一個開始執行）。 自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列 | H（低） | G（高） | F（高） | E（低） | D（高） | C（高） | B（低） | A（低） | |---|---|---|---|---|---|---|---| | 1 | 2 | 1 | 1 | 2 | 2 | 1 | 2 |
📝 此題為申論題，共 2 小題
小題 (二)
試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分）
思路引導 VIP
本題延續前一子題的推演結果，要求計算「平均等待時間」。 等待時間的計算公式為：等待時間 = 開始執行時間 - 放入(到達)時間。
小題 (一)
試計算執行此8個工作需要多少天方可完成。（10分）
思路引導 VIP
看到本題，首先要辨識出這是作業系統中 CPU 排程（CPU Scheduling）的問題，特別是具有優先權的多重佇列排程（Multi-level Queue Scheduling）。 接著應按照時間推進（時刻0, 1, 2...）來模擬工作的到達與執行情況。