民國115年 高考三級 電信工程 計算機概論
第4題
在多執行緒（multithread）的作業系統，可能會有飢餓（starvation）或死 結（deadlock）的問題，請問它們各自是怎樣的情況會造成這樣的問題…
題目
在多執行緒（multithread）的作業系統，可能會有飢餓（starvation）或死 結（deadlock）的問題，請問它們各自是怎樣的情況會造成這樣的問題。 請各提出一個解決的方法，並說明為何可以解決問題。（20 分）
參考解答（AI 生成，非官方）
- 一、死結（deadlock）指一組執行緒互相等待對方持有的資源，若無外力介入則永遠無法前進。形成須同時滿足四項 Coffman 條件：互斥（mutual exclusion）、持有並等待（hold and wait）、不可搶佔（no preemption）、循環等待（circular wait）。例如執行緒 T1 持有鎖 A 等待鎖 B，T2 持有鎖 B 等待鎖 A，即構成循環。
- 二、解法一為資源全序法（resource ordering）。為每項資源編號，規定所有執行緒必須依編號遞增順序申請，則不可能出現「大編號等小編號、小編號等大編號」的環，直接破壞循環等待條件，死結因此不可能發生。另可用銀行家演算法（Banker's algorithm）於配置前檢查是否處於安全狀態（safe state），或建立資源配置圖偵測環並回滾（rollback）犧牲者。
- 三、飢餓（starvation）又稱無限延遲（indefinite blocking），指某執行緒雖未被死結卡住、系統仍持續運作，但其請求長期被忽略而無法獲得資源。常見於優先權排程下低優先權者永遠搶不到 CPU、最短工作優先（SJF）使長工作不斷被插隊、讀者優先的讀寫鎖使寫者久候，以及非公平鎖（unfair lock）下的競爭失利。
- 四、解法為老化（aging）。隨等待時間增加逐步提升該執行緒的優先權，或改用公平佇列（fair queue）、票券鎖（ticket lock）、讀寫鎖的公平模式，並設定最大等待時間後強制提升。因為等待越久優先權越高，終會高於新進者而取得資源，滿足有限等待（bounded waiting）的要求，飢餓即被消除。
- 五、比較與實務：死結是「環狀互等、無人能動」，屬安全性（safety）問題；飢餓是「能動但輪不到」，屬活性（liveness）與公平性問題。實務上以 lock ordering、tryLock 加逾時、避免巢狀鎖來防死結；以 aging、公平鎖與避免無上限優先權反轉來防飢餓。答題須寫出成因、對應解法與其所破壞的條件，方能得分。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。