進程調度
無論是在批處理系統還是分時系統中，用戶進程數一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。
這就要求進程調度程序按一定的策略，動態地把處理機分配給處於就緒隊列中的某一個進程，以使之執行。
進程調度具有四條基本屬性和三個基本狀態：
基本屬性：
1、多態性 從誕生、運行，直至消滅；
2、多個不同的進程可以包括相同的程序；
3、三種基本狀態 它們之間可進行轉換；
4、並發性並發執行的進程輪流占用處理器。
基本狀態：
1、等待態：等待某個事件的完成；
2、就緒態：等待系統分配處理器以便運行；
3、運行態：占有處理器正在運行。
一、先來先服務和短作業(進程)優先調度算法1、先來先服務FCFS（first come first
served）
算法思想：先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用於作業調度，也可用於進程調度。當在作業調度中采用該算法時，每次調度都
是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中采用
FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而
阻塞後才放棄處理機。
優缺點：（1）有利於長作業進程，而不利於短作業進程。因為若一個長作業先到達系統，就會使許多短作業等待很長的時間，引起許多短作業用戶的不滿。
（2）有利於CPU繁忙型作業，不利於I/O，忙的作業。現在操作系統中，已很少用該算法作為主要調度策略，尤其是在分時系統和實時系統中。但它
常被結合在其它調度策略中使用。
先來先服務算法的特點是：算法比較簡單，可以實現基本上的公平。
2、短作業（進程）優先SJF（short job first）
算法思想：短作業(進程)優先調度算法SJ(P)F，是指對短作業或短進程優先調度的算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度算法是從後
備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進
程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。
優缺點：優點：能有效地降低平均周轉時間，提高系統的吞吐量。
缺點：
1）要預先知道每個作業的運行時間。
2）對於長作業不利，周轉時間明顯變長。
3）不考慮作業的緊迫程度，故不能保證緊迫性作業能夠得到及時處理。
4）在采用SJF算法時，人機無法實現交互。
在采用這種算法時，要先知道每個作業運行時間。即使是程序員也很難估計作業的運行時間，如果估計過低，系統就可能按照估計的時間終止作業
的運行，但此時作業並沒有完成，故一般都會偏長估計。
二、高優先權優先調度算法為了照顧緊迫型作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先(FPF)調度算法。此算法常被用於批處理系統中，作為作業調度
算法，也作為多種操作系統中的進程調度算法，還可用於實時系統中。當把該算法用於作業調度時，系統將從後備隊列中選擇若干個優先權最高的作業
裝入內存。當用於進程調度時，該算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該算法分成如下兩種。
1、優先權調度算法的類型
1） 非搶占式優先權算法
在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理
機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。
2） 搶占式優先權調度算法
在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度
程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在采用這種調度算法時，是每當系統中
出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止
Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統
中，以及對性能要求較高的批處理和分時系統中。
2、高響應比優先調度算法
算法思想：在批處理系統中，短作業優先算法是一種比較好的算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所述的動
態優先權，並使作業的優先級隨著等待時間的增加而以速率a 提高，則長作業在等待一定的時間後，必然有機會分配到處理機。該優先權的變化規律可
描述為：
由於等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當於響應比RP。據此，又可表示為：
優缺點：
由上式可以看出：
(1) 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利於短作業。
(2) 當要求服務的時間相同時，作業的優先權決定於其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。
(3) 對於長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。簡言之，該算
法既照顧了短作業，又考慮了作業到達的先後次序，不會使長作業長期得不到服務。因此，該算法實現了一種較好的折衷。當然，在利用該算法時，每
要進行調度之前，都須先做響應比的計算，這會增加系統開銷。
間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序便據此信號來停止該進程的執行，並將
它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一
給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用戶的請求。
2、多級反饋隊列調度算法
前面介紹的各種用作進程調度的算法都有一定的局限性。如短進程優先的調度算法，僅照顧了短進程而忽略了長進程，而且如果並未指明進程的長度，則短進程優先和基於進程長度的搶占式調度算法都將無法使用。而多級反饋隊列調度算法則不必事先知道各種進程所需的執行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度算法。在采用多級反饋隊列調度算法的系統中，調度算法的實施過程如下所述。
1）應設置多個就緒隊列，並為各個隊列賦予不同的優先級。
第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。
2）當一個新進程進入內存後，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。
當輪到該進程執行時，如它能在該時間片內完成，便可准備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列後，在第n隊列便采取按時間片輪轉的方式運行。
3）僅當第一隊列空閒時，調度程序才調度第二隊列中的進程運行；僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。
如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。
在多級反饋隊列調度算法中，如果規定第一個隊列的時間片略大於多數人機交互所需之處理時間時，便能夠較好的滿足各種類型用戶的需要。
分析多種算法的適用情況1) 如等待時間相同,則要求服務時間愈短,其優先權愈高—SPF。就是短作業優先算法。
2) 如要求服務時間相同,優先權決定於等待時間----FCFS。就是先來先服務算法。
3) 對長作業,若等待時間足夠長，優先權也高，也能獲得CPU。是本算法的優點，解決了短作業優先算法中，長作業的運行得不到保證的情況。也就是引入該算法的原因。
衡量進程調度性能的指標有：周轉時間、響應時間、CPU-I/O執行期。
