前兩篇部落格都是在講作業系統程序，包括程序狀态、PCB、程序同步、通信、線程等——我的作業系統複習——程序（上） 和 我的作業系統複習——程序（下），本篇開始講處理器排程，包括處理機排程算法、死鎖等。
一、處理機排程的類型
處理機排程程式按照某種算法将處理機配置設定給某個程序，這就叫處理機排程。總體而言，按層次分，有三種類型：
（1）作業排程（又稱進階排程、長程排程）。
作業排程的本質就是根據某種算法，把外存上的作業調入記憶體，并為之建立程序，配置設定處理機并執行。這裡有兩個概念：
1）作業（Job）
在作業系統概述中，我們了解過作業系統的發展曆程，在單道批處理系統和多道批處理系統中粗略了解過作業的概念。作業是一個比程式更廣泛的概念，可以包含多個程式和資料，還包含一份作業說明書，處理機根據作業說明書來對作業中的程式進行控制。一般而言，批處理系統中才會有進階排程。
2）作業步（Job Step）
作業步的本質就是程式。作業運作過程中的每一個步驟可以稱為一個作業步。典型的作業可分為三個作業步：編譯作業步->連續裝配作業步->運作作業步。相當于我們的程式代碼的整個執行步驟。
（2）程序排程（又稱低級排程、短程排程）。
程序排程的本質就是根據某種算法，把處理機配置設定給程序。程序排程首先會儲存處理機現場。将程式計數器等指定寄存器中的内容儲存到PCB中。然後将按照某種算法從就緒隊列中選取程序，把處理機配置設定給程序。最後，把指定程序的PCB中的處理機現場資訊恢複到處理機中，處理機配置設定給程序執行。這裡需要額外的了解一下程序排程中的三個基本機制和兩種排程方式：
1）程序排程中的三個基本機制
- 排隊器。将所有的就緒程序按照一定方式 （如優先級）排成一個隊列，以便排程程式找到。
- 分派器。把從就緒隊列中取出的程序，處理機上下文切換後，把處理機配置設定給該程序執行。
- 上下文切換機制。
（PS：這裡有一個額外的知識：通常每一次上下文切換需要花費幾毫秒的時間。有一種簡單的方式，通過多組寄存器來減少上下文切換的時間。一組寄存器供處理機在系統态使用，一組供處理機在應用程式狀态時使用。這樣，上下文切換的時候隻需要改變指針，指向目前的寄存器。）
（PSS：CPU的系統态就是CPU在執行作業系統，使用者态則是CPU在執行普通應用程式。）
2）程序排程的兩種排程方式
- 非搶占式（Nonpreemptive Mode）。說白了就是一旦把程序配置設定給某個程序，除非它自願退出，它将永遠運作下去。
- 搶占式（Preemptive Mode）。說白了就是可以根據某種條件，使正在運作的程序暫停，将處理機配置設定給另一個程序。相當于信号量機制中的條件變量。
（3）中級排程
中級排程的本質就是讓暫時不能運作的程序挂起，釋放記憶體資源，并把它們調到外存上去等待。什麼是外存？外存就是硬碟、磁盤等儲存設備。
二、排程算法
說到排程算法，那麼有幾個衡量程序運作效率的名詞需要了解一下，在做題的時候需要用到：
- 服務時間：程序總共需要占用處理機的時間長度。
- 開始執行時間：程序開始執行的時間點。
- 完成時間：程序執行完畢的時間點。
- 周轉時間：完成時間-到達時間。
- 帶權周轉時間：周轉時間/服務時間。
- 到達時間：程序進入就緒隊列的時間點
（1）先來先服務排程算法（FCFS）。
顧名思義。就是先來的先進入記憶體或占用處理機。對于作業排程，就是從後備作業隊列中選擇一個或多個最先進入隊列的作業，将其調入記憶體。對于程序排程就是從就緒隊列選擇最新進入的程序，為之配置設定處理機。
（2）短作業（程序）優先排程算法（SJ(P)F）
顧名思義。就是在選擇作業或程序的時候，先估算每個作業、程序的服務時間，選擇其中最短的優先獲得處理機。
（3）高優先權優先排程算法。
這種算法給程序加了一個屬性，那就是優先權。這個算法的本質就是，高優先權的優先調用。優先權有兩種類型，一種是靜态的，即每個程序、作業的優先權在它建立的時候就已經确定，此後都不能改變。另一種是動态的，即程序、作業的優先權是可以改變的。最常見的做法就是程序、作業在等待中，優先權以一定速率随時間增長，這樣等待時間越長，被調用的可能性就越大。
（4）基于時間片的輪轉排程法。
這就是分時系統中采用的排程算法。原理就是把所有的就緒隊列程序按先來先服務的原則排成隊列。每次都把CPU配置設定給隊首，讓其執行一個時間片，執行完畢，排程器中斷程序，并把該程序移至就緒隊列的隊尾，然後再取一個隊首程序，繼續執行下一個時間片。時間片是什麼，就是一段很短的CPU時間，幾毫秒到幾百毫秒不等。
（5）多級回報隊列排程算法。
這是當下公認的比較好的，使用最廣泛的排程算法。其原理也不難。例如，某計算機采用多級回報隊列排程算法，設定了5個就緒隊列。第一個就緒隊列優先級最高，時間片為2ms。第二個就緒隊列優先級第二，時間片為4ms，其餘隊列也一樣，優先級依次遞減，時間片依次增加。如果某個程序進入就緒隊列，首先把它放在第一個就緒隊列的末尾，輪到它執行就執行2ms，時間片結束，若該程序還沒有執行完畢，就把該程序移入第二個就緒隊列的末尾。隻有當第一個隊列的程序都執行完時間片，才會執行第二個隊列。如此依次執行，若該程序服務時間很長，将被移到最後一個就緒隊列。在最後一個就緒隊列，程序将按照時間片輪轉排程法執行。處理機執行過程中，隻有當優先級高的隊列中的線程都執行完畢，才會執行優先級低的隊列。如圖所示（懶得自己畫一遍了，直接從書上拿過來）：
三、死鎖
何謂死鎖？即多個程序在運作過程中因争奪資源造成的一種僵局。
（1）、産生死鎖的必要原因：
1）互斥條件。即一段時間内，某資源隻能由一個程序占用。這段時間，其他的程序隻能等待。
2）請求和保持條件。程序已經保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其它程序占有，此時請求程序阻塞，但又對自己已獲得的其它資源保持不放。
3）不剝奪條件。程序已獲得的資源，在未使用完之前，不能被剝奪
4）環路等待條件。
參考：《計算機作業系統(湯子瀛)》
/**
* ————————如果覺得本博文還行，别忘了推薦一下哦，謝謝！
* 作者：錢書康
* 歡迎轉載，請保留此段聲明。
* 出處：http://www.cnblogs.com/zrtqsk/
*/