刑事警察人員 103 年計算機系統考古題

試以卡諾圖（Karnaugh map）化簡下列布林式。（10 分）

試解釋何謂重要區塊（critical section）？（5 分） 並說明解決重要區塊問題（the critical section problem）時須滿足那些要求？（15 分）

CPU 排程為作業系統中重要的議題之一。今給定三程序P1、P2 與 P3，其所需之 CPU 時間分別為24、4、3 單位時間；假設此三程序依照P1 →P2 →P3 之順序分別 於時間單位0、1、2 時刻產生，並假設此時CPU 已為可用狀態且僅需用於處理這 三個程序。試以甘特圖（Gantt chart）表示先到先處理（first-come first-served）以及 最短工作先處理（shortest-job-first）兩排程的結果，並分別計算兩排程下的平均等 待時間（average waiting time）。（20 分）

在死結（deadlock）發生時，一定會有循環等待（circular wait）的情形，試提出一 解決循環等待的方法，並證明該方法之正確性。（20 分）

虛擬記憶體（virtual memory）的技術允許我們執行一未完全載入於主記憶體中的程 序；但此技術可能會造成猛移現象（thrashing）。試解釋猛移現象一詞，並作適當 的說明。（10 分）

在多工作業系統中，本文交換（context switch）為CPU 頻繁執行的動作之一。試 解釋本文交換一詞，並作適當的說明。（10 分）

今欲存取磁碟上位於磁柱編號98, 183, 37, 122, 14, 124, 65, 67 上的資料，試寫下 SCAN 演算法（也稱為電梯演算法）對上述各磁柱的存取順序（假設磁碟讀寫頭目 前位於編號53 的磁柱，並往編號0 的磁柱移動；且上述磁柱編號即代表目前已發 生的存取請求，且不會再有其他請求發生）。（10 分）