2014年華北電力大學計算機專業考研專業課複習3 操作系統部分

1、處理機調度的基本概念

2、調度方式及算法

3、算法

4、死鎖的基本概念

5、死鎖的處理策略

方法/步驟

1

處理機調度的基本概念 就緒隊列中只要有兩個以上的進程存在就會競爭CPU的使用權。如果只有1個CPU可用，那麼就必須選擇下一個要運行的進程。完成選擇工作的這一部分稱為調度程序（scheduler），該程序使用的算法稱為調度算法（scheduling algorithm）。

2

調度方式及算法 不可搶佔調度方式：一個進程若被選中，就一直運行下去，直到它被阻塞（I/O，或正在等待其他的進程），或主動地交出CPU。可搶佔調度方式：當一個進程在運行時，調度程序可以打斷它。另外，在其他的一些情形下，如就緒隊列中有進程的優先級高於當前運行進程的優先級，也可能立即進行調度。

3

算法 先來先服務（First Come First Served，FCFS； First In First Out，FIFO）：按照作業到達的先後次序進行調度；不可搶佔方式：當前進程佔用CPU，直到執行完或被阻塞，才讓出CPU給另外一個進程；在進程被喚醒後（如I/O完成），並不立即恢復執行，而是放在就緒隊列的末尾；優點：簡單，易於理解也易於實現。現實生活中應用廣泛：排隊。短作業優先（Shortest Job First，SJF），設計目標是改進FCFS算法，減少平均週轉時間；SJF算法要求作業在開始執行時預計執行時間，對預計執行時間短的作業優先分派處理器兩種實現方案：不可搶佔方式：當前作業在運行時不會被打斷，只有運行完畢或阻塞時，才讓出CPU；可搶佔方式：如果一個新的短作業到來，其運行時間小於當前正在運行作業的剩餘時間，則搶佔CPU運行，稱為SRTF（Shortest Remaining Time First）。一種動態優先權算法 最高應比作業優先算法是對FCFS方式和SJF方式的一種綜合平衡。響應比R定義為系統對作業的響應時間與作業要求運行時間的比值R＝響應時間 / 要求運行時間＝(作業等待時間＋需運行時間)/ 需運行時間＝1＋已等待時間 / 需運行時間＝1＋W/T優先級調度算法是從就緒隊列中選出優先級別最高的進程。讓它佔用CPU運行靜態優先級：靜態優先級調度算法是指在創建 進程時就確定下來的，而且在進程的整個運行 期間其優先級是維持不變的動態優先級：動態優先級是隨着進程的推進而不斷變化的 (例如HRN)在時間片輪轉算法（Round-Robin，RR）中，將所有的就緒進程按照FCFS原則，排成一個隊列每次調度時將處理器分派給隊首進程，讓其執行一小段CPU時間（時間片time quantum）在一個時間片結束時，如果進程還沒有執行完的話，將發生時鐘中斷，在時鐘中斷中，進程調度程序將暫停當前進程的執行，並將其送到就緒隊列的末尾，然後執行當前的隊首進程如果一個進程在它的時間片用完之前就已結束或被阻塞，那麼立即讓出CPU多級隊列算法（Multilevel Queue）引入多個就緒隊列，通過各個隊列的區別對待，達到一個綜合的調度目標。根據進程的性質或類型的不同，將就緒隊列再分為若干個子隊列，如系統進程、用户交互進程、批處理進程等；不同的隊列可以有不同的優先級；不同的隊列可以採用各自不同的調度算法，如前台式進程可採用RR算法，後台的批處理進程可採用FCFS算法。在各個隊列之間也必須進行調度：固定優先級調度：按照各種類型的進程的優先級別從高到低地進行，先運行最高優先級的所有進程，再運行次一級所有進程，依此類推。 問題：可能導致“飢餓”；時間片方法：把CPU時間按比例分配給不同的隊列，然後再由各個隊列的調度算法去調度，如80％給前台的交互式進程隊列（RR算法），20％給後台的批處理進程隊列FCFS）。多級反饋隊列算法 (Multilevel Feedback Queue)即根據一個進程的運行反饋信息，動態地調整它所在的隊列。三種優先級別，3最高、1最低，三個就緒隊列。時間片長度分別為N、2N和4N；新進程進入內存後，優先級為3，加入隊列3的末尾，按FCFS算法調度；若一個時間片內未能執行完，則優先級降為2，加入到隊列2的末尾，同樣按FCFS算法調度；依此類推。僅當較高優先級的隊列為空，才調度較低優先級的隊列中的進程執先級的隊列，則搶先執行新進程。在實時系統中，對時間的要求是非常嚴格的。典型的例子是：一個或多個外部的物理設備定期或不定期地生成激勵信號，而計算機必須在一定的時間期限內做出恰當的反應。根據任務的開始截止時間確定任務優先級，截止時間越早，優先級越高。可用於搶佔和非搶佔式。最低鬆弛度優先算法該算法是根據任務緊急(或鬆弛)的程度，來確定任務的優先級。任務的緊急程度愈高，為該任務所賦予的優先級就愈高，以使之優先執行。鬆弛度＝必須完成時間－本身運行時間－當前時間

4

死鎖的基本概念 在一組進程中，每個進程都佔用着若干個資源，同時又在等待得到該組進程中另一進程所佔用的資源，因而造成的所有進程都無法進展下去的現象，這種現象稱為死鎖，這一組進程就稱為死鎖進程。死鎖的4個必要條件：互斥條件：在任何時刻，每一個資源最多隻能被一個進程所使用；請求和保持條件：進程在佔用若干個資源的同時又可以請求新的資源；不可搶佔條件：進程已經佔用的資源，不會被強制性拿走，而必須由該進程主動釋放；環路等待條件：存在一條由兩個或多個進程所組成的環路鏈，其中每一個進程都在等待環路鏈中下一個進程所佔用的資源。

5

死鎖的處理策略 忽略死鎖，無為而治Windows、UNIX檢測並恢復動態避免 小心的進行資源分配預防 破壞死鎖的4個必要條件之一銀行家算法在小鎮上，有一位銀行家和一些需要貸款服務的客户。銀行家根據每一位客户的背景情況，為之設定了相應的最高貸款限額。現在的問題是銀行家必須設計出一種算法，以保證借貸過程的順利進行，也就是説，當某個客户提出了一個貸款申請時，該算法必須判斷，如果批准了這個申請，是否會導致一種不安全的狀態，如果是的話，就拒絕該申請；如果否的話，就批准該申請。求安全序列。