OS中處理機調度模型和調度算法

OS中處理機調度模型和調度算法

調度層次

1.1. 高級調度（長程調度，作業調度）

功能：根據某種算法，把在外存隊列上處於後備隊列的那些作業調入內存，以作業為操做對象。

作業：比程序更為廣泛的概念，不僅包含通常的程序和數據，還包含一份作業說明書，系統根據作業說明書對程序的運行進行控制。

作業步：每個作業都要經過若干個相對獨立而又相互關聯的順序加工步驟才能得到結果，我們把每一個步驟稱為一個作業步。

作業流：若干個作業進入系統後被依次存放在外存上，這樣便形成了輸入的作業流。

作業控制塊（JCB）：JCB是作業在系統中存在的標志，保存著系統對作業進行管理和調度所需的全部信息，具體包含的內容根據系統而異。

作業調度 的作用：

1.2. 中級調度（中程調度，對換）

功能：將暫時不能運行的進程調到外存上，使其處於外存就緒狀態或者外存掛起狀態，提高系統的利用率和吞吐量。

3. 低級調度 （短程調度，進程調度）

功能：最基本的一種調度 ，主要用來保存處理機的現場信息（進行進程調度時首先保存當前進程的現場信息，將現場信息保存到該進程PCB的相應位置），按某種算法選取進程（根據算法選進程），把處理機分配給進程（由進程分配程序將處理機分配給進程）。

基本機制：排隊器，分派器，上下文切換機制。

排隊器： 事先將系統的就緒隊列中所有的就緒進程按照一定的方式排成一個或者是多個隊列。

分派器：將進程調度程序所選定的的進程從就緒隊列中取出。

上下文切換機制： 對處理機進行切換時，會出現兩次的上下文切換。系統首先保存當前進程的上下文，裝入分派程序的上下文；最後移除分派程序，把選中的進程的CPU現場信息裝入各個相應的寄存器。

調度方式：搶占式 || 非搶占式

非搶占式：一旦將處理機分配個某進程，不管運行多長時間，決不允許因為時鐘中斷而搶占處理機，也不允許其他進程搶占已經分配給他的處理機。除非進程執行結束或者是其自身由於某種原因而發生了阻塞時，才會把處理機交個其他的進程。

搶占式：允許調度程序基於某種原則而暫停當前正在占用處理機的進程，而將處理機分配給其他的進程。（原則：優先權原則，短作業（進程）優先原則，時間片原則）

調度隊列模型及准則

2.1 調度隊列模型

2.1.1 僅有進程調度的調度隊列模型：

每個進程在執行時都可能出現以下三種情況：

(1) 任務在給定的時間片內已經完成，該進程便在釋放處理機後進入完成狀態

(2) 任務在本次分得的時間片內尚未完成，OS便將該任務再放入就緒隊列的末尾；

(3) 在執行期間，進程因為某事件而被阻塞後，被OS放入阻塞隊列。
　

2.1.2 具有低級和高級調度的隊列模型：

由作業調度按一定的作業調度算法，從外存的後備隊列中選擇一批作業調入內存，並為它們建立進程，送入就緒隊列，然後才由進程調度按照一定的進程調度算法選擇一個進程，把處理機分配給該進程。

2.1.3 三級調度隊列模型：

在引入中級調度之後，將進程的就緒狀態分為內存就緒和外存就緒，類似的也可以將阻塞狀態進行劃分，分為內存阻塞和外存阻塞，在調度操作下，進程可以由內存阻塞轉換為外存阻塞。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+Mi4yILX3tsjXvNTyPC9zdHJvbmc+PC9wPg0KPHA+PGVtPjIuMi4xIMPmz/LTw7uno7o8L2VtPjwvcD4NCjxwPjxzdHJvbmc+o6gxo6nW3NeqyrG85LbMo7o8L3N0cm9uZz7L+c691tzXqsqxvOSjrMrH1ri009f30rWxu8zhvbu4+M+1zbO/qsq8o6y1vdf30rXN6rPJzqrWudXits7KsbzkvOS49KGjPC9wPg0KPHA+xuSw/Lqsy8Syv7fWyrG85KO6MSZndDvX99K11NrN4rTmuvOxuLbTwdC1yLT9tfe2yMqxvOSjrDImZ3Q7vfizzNTavs3Q97bTwdDJz7XItP2197bIyrG85KOsMyZndDu9+LPM1NpjcHXJz9a00NC1xMqxvOSjrDQmZ3Q7vfizzLXItP1JL0+y2df3zeqzycqxvOShozwvcD4NCjxwPsa9vvnW3NeqyrG85KO6yKuyv9f30rW1xNbc16rKsbzk19y6zdPr1/fStcr9wb+1xLHI1rWhozxub2JyPlQ9MW5bJnN1bTtuaT0xVGldPC9ub2JyPjwvcD4NCjxwPrT4yKjW3NeqyrG85KO61/fStbXE1tzXqsqxvOQ8bm9icj5UPC9ub2JyPrrNz7XNs86qy/zM4bmpt/7O8bXEyrG85Dxub2JyPlRzPC9ub2JyPtauscg8bm9icj5XPVRUczwvbm9icj48L3A+DQo8cD7Gvb75tPjIqNbc16rKsbzko7o8bm9icj5XPTFuWyZzdW07bmk9MVRpVHNdPC9ub2JyPjwvcD4NCjxwPjxzdHJvbmc+o6gyo6nP7NOmyrG85L/so7o8L3N0cm9uZz7L+c69tcTP7NOmyrG85KOsysfWuLTT08O7p8zhvbvSu7j2x+vH87+qyryjrLW9z7XNs8rXtM6y+sn6z+zTps6q1rm1xMqxvOSho8rH0aHU8bfWyrHPtc2z1tC9+LPMtfe2yLXE1tjSqte81PLWrtK7oaM8L3A+DQo8cD48c3Ryb25nPqOoM6OpvdjWucqxvOS1xLGj1qSjujwvc3Ryb25nPsv5zr292Na5yrG85KOsysfWuMSzyM7O8bHY0Ou/qsq81rTQ0LXE1+6z2cqxvOSjrLvT18Wx2NDrzeqzybXE1+6z2cqxvOSho8rHxsC828q1yrHPtc2ztcTW2NKq1rix6qGjPC9wPg0KPHA+PHN0cm9uZz6jqDSjqdPFz8jIqNSt1PKjujwvc3Ryb25nPiDU2tGh1PG197bIy+O3qMqxo6y++b/J1/HRrdPFz8jIqNSt1PKjrMjDvfS8sbXEyM7O8bXDtb28sMqxtcS0psDtoaOx2NKqyrHSqrLJ08PHwNW8yr21xLX3tsi3vcq9o6yyxcTcsaPWpL30vLHX99K1vLDKsbSmwO2hozwvcD4NCjxwPjxlbT4yLjIuMiDD5s/yz7XNs6O6PC9lbT48YnIgLz4NCs+1zbPNzM3Cwb+436OstKbA7bv6wPvTw8LKusOjrLj3wODXytS0xr264sD708OhozwvcD4NCjxwPjxzdHJvbmc+Mi4zILX3tsjL47eoPC9zdHJvbmc+PC9wPg0KPHA+PHN0cm9uZz48ZW0+o6gxo6nPyMC0z8i3/s7xy+O3qKOoRkNGU6Opo7o8L2VtPjwvc3Ryb25nPtfuvPK1pbXEtfe2yMvjt6ijrLzIv8nTw9Pa1/fStbX3tsijrNKyxNzTw9PavfizzLX3tsihozxzdHJvbmc+06bTw9Ta1/fStbX3tsjKsTwvc3Ryb25nPqOsw7+0zra8yse007rzsbjX99K1ttPB0NbQ0aHU8dK7uPa78tXftuC49tfu1Oe9+MjruMO208HQtcTX99K1o6y9q8bktffI68TatOajrM6qxuS31sXk0OjSqrXE18rUtKOstLS9qL34s8yjrMztvNPI677N0Pe208HQzrKyv6GjPHN0cm9uZz7TptPD1Nq9+LPMtfe2yMqxPC9zdHJvbmc+o6zDv7TOtfe2yLa8yse0077N0Pe208HQ1tDRodTx0ru49tfu1Oe9+MjrttTB0NbQtcS9+LPMo6zOqsbkt9bF5LSmwO27+qOs1rG1vbjDvfizzLfFxvq0psDtu/qhozwvcD4NCjxwPtPFyLG146O609DA+9Pas6TX99K1o6i9+LPMo6mjrLK7wPvT2rbM1/fStaOovfizzKOpPC9wPg0KPHA+PHN0cm9uZz48ZW0+o6gyo6m2zNf30rWjqL34s8yjqdPFz8jL47eoo6hTSkYvU1BGo6mjujwvZW0+PC9zdHJvbmc+tNO687G4ttPB0NbQ0aHU8dK7uPa78tXftuC49rnAvMbUy9DQyrG85LbMtcTX99K1u/LV3734s8yjrL2ry/vDx7X3yOvE2rTmu/LV38rHzqrG5LfWxeS0psDtu/qhozwvcD4NCjxwPtPFyLG146O6xNzD98/UtcS4xMnGxr2++bT4yKjW3NeqyrG85KOs08jG5MrHttS2zNf30rW2+NHUoaO1q8rHuMPL47eottSzpNf30rWyu8D7o6y2+MfSzrS/vMLH1/fStbXEvfTGyLPMtsijrNTayrW8yta00NC5/bPM1tCjrMbAxdDSwL7d1rvKx9PDu6fM4bmptcS5wLzG1rTQ0MqxvOSjrLb408O7p9PQv8nE3M7e0uK78tXf09DS4rXEy/W2zLnAvMbUy9DQyrG85KOstbzWwrK70ru2qMTc1ebV/bXE1/a1vbbM1/fStdPFz8ihozwvcD4NCjxwPjxzdHJvbmc+PGVtPqOoM6OpuN/Txc/IyKjTxc/Itfe2yMvjt6ijqEZQRqOpo7o8L2VtPjwvc3Ryb25nPr/J08PT2tf30rW197bIus29+LPMtfe2yKOstbG9+NDQtfe2yMqxo6zRodTxyPS4ybj208XPyMiouN+1xNf30rW78tXfyse9+LPMtffI68TatOa78tXfysfOqsbkt9bF5LSmwO27+qGjPC9wPg0KPHA+08XPyMiotcTIt7aot9bOqsG9wOCjujwvcD4NCjxwPqOoMy4xo6m+ssys08XPyMioo7rU2rS0vai9+LPMyrHTxc/IyKix49LRvq3It7aoo6yyosfS1NrV+7j21MvQ0MbavOSxo7PWsrux5KGjyLe2qNLAvt3T0KO6MSZndDu9+LPMwODQzaOozaizo8+1zbO9+LPMtcTTxc/IyKi439Pa0ruw49PDu6e1xNPFz8jIqKOpMiZndDu9+LPMttTXytS0tcTQ6Mfzo6i21NfK1LTSqsfzydm1xNOmuMO4s9Povc+437XE08XPyMioo6kzJmd0O9PDu6fSqsfzo6jTydPDu6e9+LPMtcS99MbIs8y2yNLUvLDTw7uny/m4trfR08PAtMi3tqjTxc/IyKijqTwvcD4NCjxwPqOoMy4yo6m2r8ys08XPyMioo7q2r8ys08XPyMioysfWuNTatLS9qL34s8zKscv5uLPT6LXE08XPyMioo6zKx7/J0tTL5r34s8y1xM3Gvfi78svmxuS1yLT9yrG85LXE1Pa807b4uMSx5LXEo6zS1LHju/G1w7j8usO1xLX3tsjQ1MTcoaM8L3A+DQo8cD7TxcixteOjusTcuty6w7XEzOXP1tf30rWjqL34s8yjqb30vLGzzLbIo6yyorj5vt3Txc/IvLbAtL340NC197bIo6y1q8rH0qq197bIx7DSqrHIvc+78tXfvMbL49f30rW1xNPFz8i8tqOs1Pa808HLz7XNs7XEv6rP+qGjPC9wPg0KPHA+PHN0cm9uZz48ZW0+o6g0o6m438/s06axyNPFz8jL47eoo7o8L2VtPjwvc3Ryb25nPs6qw7+49tf30rXS/cjrtq/MrLXE08XPyMioo6zKubXD1/fStbXE08XPyMioy+bXxbXItP3KsbzktcTU9rzTtvjS1MvZwsphzOG436GjPC9wPg0KPHA+PG5vYnI+08XPyMioPbXItP3KsbzkK9Kqx/O3/s7xyrG85NKqx/O3/s7xyrG85D3P7NOmyrG85NKqx/O3/s7xyrG85Dwvbm9icj48L3A+DQo8cD7TxcixteOjurjDy+O3qLzI1dW5y8HLtszX99K1o6zT1r+8wsfBy9f30rW1vbTvtcTPyLrztM7Q8qOssru74cq5tcOzpNf30rWzpMqxvOS1w7K7tb23/s7xoaO1q8rHuMPL47eow7+0zrX3tsjHsLa80qq9+NDQz+zTprHItcS8xsvjo6zU9rzTz7XNs7XEv6rP+qGjPC9wPg0KPHA+PHN0cm9uZz6jqDWjqbv509rKsbzkxqy1xMLW16q197bIy+O3qKO6PC9zdHJvbmc+PC9wPg0KPHA+PHN0cm9uZz67+bG+1K3A7aO6PC9zdHJvbmc+z7XNs72ry/nT0LXEvs3Q9734s8ywtM/IwLTPyLf+zvG1xNSt1PLFxbPJ0ru49rbTwdCjrMO/tM6197bItry9q2Nwdb27uPi208rXtcS9+LPMo6zB7sbk1rTQ0NK7uPbKsbzkxqy1xMqxvOSjrNa00NC1xMqxvOTGrNPDzeq+zcHuuMO9+LPMt8XG+sqxvOTGrKOssqK9q8bkudLI67bTzrK9+NDQz8LSu7TOtcS1yLT9oaM8L3A+DQo8cD48c3Ryb25nPsqxvOTGrLTz0KG1xMi3tqijqLrL0MSjqaO6PC9zdHJvbmc+1NrKsbzkxqzC1teqt6jW0KOs1+66y9DEtcS+zcrHyrG85MastPPQobXEtu7It7aoo6zKsbzkxqy089ChttTPtc2ztcTQ1MTc09C63LTztcTTsM/soaPKsbzkxqzMq7bMo6zT0MD709q2zNf30rWjrLWru+HGtbextcS3osn61tC2z6Oso6y9+LPMyc/Pws7EtcTH0Lu7o6zU9rzTz7XNs7+qz/qju8qxvOTGrMyrs6SjrMq5tcPDv9K7uPa9+LPM1NrSu7j2yrG85MastaXOu8TatrzE3M3qs8nIzs7xo6zL47eosePNy7uvs8nBy0ZDRlPL47eoo6zO3reowvrX4727u6XKvdDox/Oho9fuzqq6z8DttcTKx6OsyrG85MaswtS089Pa0ru0zrXk0M21xL27u6XL+dDotcTKsbzkoaM8L3A+DQo8cD7TxcixteOjurv509rKsbzkxqzC1teqo6zE3MjDw7+49sjOzvG2vNPQyrG85LXDtb3WtNDQo6zT0L3PusO1xL27u6XQ1KOsyLG148rHyrG85MastcTIt7aosci9z7i01NOhozwvcD4NCjxwPjxzdHJvbmc+o6g2o6m24Ly2t7TAobbTwdC197bIy+O3qKO6PC9zdHJvbmc+PC9wPg0KPHA+PHN0cm9uZz7UrcDto7o8L3N0cm9uZz48YnIgLz4NCqOoMaOpyejWw7bguPa+zdD3ttPB0KOssqLOqrj3uPa208HQuLPT6LK7zay1xNPFz8i8tqGjILXa0ru49rbTwdC1xNPFz8i8ttfuuN+jrLXatv649rbTwdC0ztauo6zG5NPguPe208HQtcTTxc/IyKjW8Lj2vbW1zaGjuMPL47eouLPT6Lj3uPa208HQ1tC9+LPM1rTQ0MqxvOTGrLXEtPPQodKyuPeyu8/gzayjrNTa08XPyMio0/q437XEttPB0NbQo6zOqsO/uPa9+LPMy/m55raotcTWtNDQyrG85Masvs3T+tChoaM8YnIgLz4NCqOoMqOptbHSu7j2vfizzL34yOvE2rTmyrGjrMrXz8i9q8bkt8XI67Xa0ru208HQo6ywtEZDRlPUrdTyxcW207XIuvK197bIoaO1sbX3tsi1vbjDvfizzMqxo6zI9MTc1NrKsbzkxqzE2s3qs8mjrLHjs7fA68+1zbOjrMj01NrSu7j2yrG85MasxNrOtM3qs8mjrL2rxuS50sjrtdq2/rbTwdC2086yo6zU2bC01dVGQ0ZT1K3U8r340NDFxbbTtci68qOs1q6687C01dW12tK7ttPB0LXEt73Kvb340NDWtNDQoaM8YnIgLz4NCqOoM6Opvfa1sbXa0ru208HQv9XP0Mqxo6yyxbvhtfe2yLXatv6208HQ1tC1xL34s8yjrL32tbG12jF+o6hpLTGjqbbTwdC++b/Vz9DKsaOsssW74bX3tsi12mm208HQ1tC1xL34s8yhozwvcD4NCjxwPjxpbWcgYWx0PQ=="多級反饋隊列調度算法" src="http://www.2cto.com/uploadfile/Collfiles/20160411/20160411143456366.png" title="" />

優缺點：有較好的性能，能很好的滿足各類型用戶的需求，缺點是有很多的排隊隊列，要消耗系統資源。