電腦硬體—調度與死鎖
- 2019 年 11 月 14 日
- 筆記
進程調度原因及調度切換時機，進程調度方式與實現及各種調度演算法的個人總結：
1.一般調度概念 1）什麼是調度 就是選出待分派的作業或進程。 作業系統管理了系統的有限資源，當有多個進程（或作業）發出請求要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（或作業）來佔用資源。這就是調度。
2）調度目的 1.控制資源使用者的數量 2.選取資源使用者 3.許可哪些使用者佔用資源 4.讓使用者直接佔用資源。
二、調度類型 1、高級調度(長程調度)。 即作業調度，選取輸入井中的作業，生成根進程。目的是控制使用系統資源的進程數。
2、中級調度（中程調度）。 指選取進程佔用記憶體或有資格佔用記憶體，又稱進程滾入滾出，中級調度將在存儲管理章節中介紹，有頁式調度、段式調度、段頁式調度等。
3、低級調度（短程調度） 指選取進程佔用處理機,又稱進程調度。 4、I/O調度 選取進程佔用I/O設備。
三、調度和狀態轉換 在許多系統中，調度被分為三種：長程、中程和短程。 1）調度和進程狀態轉換
從狀態轉換的觀點： 1、長程調度（作業調度）就是將一個或一批作業從後備狀態變為運行狀態。一個作業一旦被高級調度選中，便可獲得所需要的基本記憶體和設備資源，並被裝入記憶體，此後就以進程形式參與並發執行，與其它進程競爭CPU。
從狀態轉換的觀點： 2、中程調度就是將進程從活動態變為靜止的掛起態，或者將進程從掛起態變為就緒或阻塞態。 3、短程調度就是將某個進程從就緒態變為(在CPU上運行的)執行態。
2）調度的層次（調度作用的嵌套關係）
3）三級調度示意圖 調度從根本上講，是要使隊列延遲的時間最小，並優化系統的執行效率
4.1.2作業調度的功能
①記錄系統中各個作業的情況。 ②按照某種調度演算法從後備作業隊列中挑選作業，即決定接納多少個作業進入記憶體和挑選哪些作業進入記憶體。
③為選中的作業分配記憶體和外設等資源。 ④為選中的作業建立相應的進程，並把該進程放入就緒隊列中。 ⑤作業結束後進行善後處理工作。如輸出必要的資訊，收回該作業所佔用的全部資源，撤消與該作業相關的全部進程和該作業的JCB 。
4.1.3進程調度的功能與調度時機 一、進程調度的功能 (1)保存現場(2)挑選進程(3)恢復現場
二、進程調度的時機 一般在下列事件發生後要執行進程調度。 （1）創建進程。 當進程創建時，要決定是運行父進程還是子進程。 （2）進程終止。 （3）等待事件。 （4）中斷髮生。 （5）運行到時。
4.1.4進程調度的基本方式 1）非剝奪調度（非搶佔） 只有當處理機上的進程主動放棄處理機時，才重新調度。 2）剝奪調度（搶佔） 當進程運行時可以被系統以某種原則為由剝奪其處理機。
例：只有一部電話機，小李正在通電話，此時小張有急事也要打電話，此時小張的調度方式有兩種： 一種是非搶佔，即等待小李打完電話，自己再打電話。 另一種是搶佔，不等小李通完電話，搶過話筒就撥打電話。
3）進程調度在核心態進行。 ★CPU狀態有兩種，目態和管態。 管態——也稱核心態或系統態，系統程式在CPU上運行的狀態。 目態——用戶程式在CPU上運行的狀態。
4.2 調度演算法 4.2.1 常用的調度演算法
1. FCFS 誰先到就緒隊列就將處理機分給誰。 2. 短作業優先 取一個下次所需運行時間最短的作業(該演算法能使平均等待時間最短)。
3. 優先順序調度 選優先順序最高的進程佔用處理機（優先順序可動態改變）。 4.輪轉調度法 以先來後到的次序+ 時間片輪轉。
5.多隊列調度法 按屬性將就緒進程分類,不同類進程可有不同的調度演算法。 6.多級回饋隊列調度法 設置多條就緒隊列,進程被調度執行後,在被剝奪或放棄處理機後而在就緒時，可以改變其就緒隊列(見下圖）。
又一個多級回饋隊列調度演算法的例子：使用優先權實現調度。做法如下：
（1）以優先順序設置多隊列。 （2）各隊列的調度演算法採用FCFS+時間片輪轉. （3）進程優先順序升降原則是:等待過久升,輸入/輸出完成時升,運行完一個完整時間片降……
（4）進程最初進入就緒隊列以用戶初置優先順序為參數。 （5）開始調度時，先從最高優先權的就緒隊列（RQ0）開始選取一個進程，如果RQ0空，則檢查RQ1，如此下去。見下圖示：
4.2.2 調度策略的討論
一、調度性能評價準則 1、CPU利用率。 2、吞吐率。即每單位時間所完成的作業數目。 3、周轉時間。即從作業提交直至完成這一作業的時間間隔。
4、等待時間。即作業在就緒隊列中等待所花的時間。 5、響應時間。即從作業提交到首次產生回答資訊之間的時間。
二、主要的調度演算法 下面以表所示的進程集作為範例討論不同的調度策略。 到達時間：進程或作業提交時間。 服務時間：進程要求服務的時間，或完成作業所需的時間。
一、FCFS調度策略（或先進先出）
FCFS策略更適合於長進程。例：
註：周轉時間=完成時間—到達時間 tq/ts ：帶權周轉時間=周轉時間/服務時間
（1）進程C的等待標準化時間是不能容忍的。它位於系統的總時間是它所需服務時間的100倍。無論何時，一個長進程到後，一個短進程就會出現較長的等待。 （2）進程D的標準化等待時間尚可容忍，小於2.0。進程D的輪轉時間差不多是C的兩倍。
總結： FCFS（First Come First Served）即先來先服務，故它的本質是非搶佔的。它簡單易行，但調度性能較差，有可能使短的、重要的或緊迫的作業等進程長期等待，其實現過程容易，可採用FIFO隊列管理。
