❶ 時間片輪轉演算法（RR）能不能用在作業調度上還是只能用在進程調度上
導師給出的答案是不能，但是吧友似乎有一些別的看法。
先來看作業調度的定義，高級調度又稱長程調度或作業調度，他的調度對象是作業。主要功能是根據演算法，決定將外存處於後備隊列的哪幾個作業調入內存，為他們創建進程，分配必要的資源，並將它們放入就緒隊列。分時和實時系統不設置高級調度。
其次簡單的敘述一下低級調度（進程調度）：對象為進程，功能是決定就緒隊列中的哪個進程應獲得處理機，並分配。
最後來看一下RR的核心，進程切換：在RR調度演算法中，應在合適進行進程的切換，可分為兩種情況：1，若一個時間片尚未用完，正在運行的進程便已經完成，立刻激活調度程序，將他從就緒隊列中刪除，再調度就緒隊列中對手的進程運行，並啟動一個新的時間片。2.在一個時間片用完時，計時調度器中斷處理程序被激活。如果進程尚未運行完畢，調度程序將把它送往就緒隊列的末尾。
可見，RR演算法在切換進程時只涉及了就緒隊列的c、a、o作，也就是只有低級調度參與，並沒有從外存將作業調入內存，另外，RR演算法常用於分時系統，分時系統也是不設置作業調度的。
❷ 常見的調度演算法總結
一、FCFS——先來先服務和短作業（進程）優先調度演算法
1. 先來先服務調度演算法。
先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。
2. 短作業（進程）優先調度演算法。
短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。
二、FPF高優先權優先調度演算法
1. 優先權調度演算法的類型。
為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：
1)非搶占式優先權演算法
2)搶占式優先權調度演算法（高性能計算機操作系統）
2. 優先權類型 。
對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。
3.動態優先權
高響應比優先調度演算法為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間
三、基於時間片的輪轉調度演算法
1.時間片輪轉法。
時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。
2. 多級反饋隊列調度演算法
多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：
1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。
2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。
3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；
僅當第1到第（ i-1 ）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。
4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。
❸ 處理機調度有哪幾種方式它們分別有什麼優缺點
先來先服務FCFS和短作業（進程）優先SJ(P)F調度演算法，SJF調度演算法用於作業和進程調度，能有效的降低作業的平均等待時間，提高系統吞吐量。缺點：該演算法對長作業不利，完全未考慮作業的緊迫程度，因此不能保證緊迫性作業會被及時處理，由於作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業優先調度。 高優先權優先調度演算法，優先權調度演算法包括非搶占式優先權演算法和搶占式優先權調度演算法；高響應比優先調度演算法，特點：有利於短作業、先來先服務、對於長作業也可獲得處理機。 基於時間片的輪轉調度演算法，時間片輪轉法和多級反饋隊列調度演算法。
❹ 單道批處理系統作業調度演算法有哪幾種
批處理系統常用調度演算法：
①、先來先服務：FCFS
②、最短作業優先
③、最短剩餘時間優先
④、響應比最高者優先
分時系統調度演算法：
①、輪轉調度
②、優先順序調度
③、多級隊列調度
④、彩票調度
實時系統調度演算法：
①、單比率調度
②、限期調度
③、最少裕度法
❺ 實時操作系統常用任務調度演算法有哪些
實時操作系統常用任務調度演算法有哪些
操作系統常用的批處理作業調度演算法
1．先來先服務調度演算法
先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
2．短作業(進程)優先調度演算法
❻ 進程調度演算法
調度算指:根據系統資源配策略所規定資源配算
、先先服務短作業(進程)優先調度算
1.
先先服務調度算先先服務(FCFS)調度算種簡單調度算該算既用於作業調度
用於進程調度FCFS算比較利於作業(進程)利於短作業(進程)由知本算適合於CPU繁忙型作業
利於I/O繁忙型作業(進程)
2.
短作業(進程)優先調度算短作業(進程)優先調度算(SJ/PF)指短作業或短進程優先調度算該算既用於作業調度
用於進程調度其作業利;能保證緊迫性作業(進程)及處理;作業短估算
二、高優先權優先調度算
1.
優先權調度算類型照顧緊迫性作業使進入系統便獲優先處理引入高優先權優先(FPF)調度算
算用批處理系統作作業調度算作種操作系統進程調度用於實系統其用於作業調度
備隊列若干優先權高作業裝入內存其用於進程調度處理機配給緒隊列優先權高進程
進步該算兩種:
1)非搶占式優先權算
2)搶占式優先權調度算(高性能計算機操作系統)
2.
優先權類型
於高優先權優先調度算其核於:使用靜態優先權態優先權
及何確定進程優先權
3.
高響應比優先調度算
彌補短作業優先算足我引入態優先權使作業優先等級隨著等待間增加速率a提高
該優先權變化規律描述:優先權=(等待間+要求服務間)/要求服務間;即
=(響應間)/要求服務間
三、基於間片輪轉調度算
1.
間片輪轉間片輪轉般用於進程調度每調度CPU配隊首進程並令其執行間片
執行間片用完由記器發鍾斷請求該進程停止並送往緒隊列末尾;依循環
2.
級反饋隊列調度算
級反饋隊列調度算級反饋隊列調度算必事先知道各種進程所需要執行間目前公認種較進程調度算
其實施程:
1)
設置緒隊列並各隊列賦予同優先順序優先權越高隊列
每進程所規定執行間片越
2)
新進程進入內存首先放入第隊列末尾按FCFS原則排隊等候調度
能間片完便撤離;未完轉入第二隊列末尾同等待調度……
作業(進程)第隊列依第n隊列(隊列)便按第n隊列間片輪轉運行
3)
僅第隊列空閑調度程序才調度第二隊列進程運行;僅第1第(i-1)隊列空
才調度第i隊列進程運行並執行相應間片輪轉
4)
處理機處理第i隊列某進程新進程進入優先權較高隊列
則新隊列搶占運行處理機並運行進程放第i隊列隊尾
❼ 作業調度演算法的選擇原則有哪幾個
批處理作業的調度演算法主要有以下幾種：
①先來先服務演算法。原則上按照作業進入輸入井的次序調度，如果作業的資源得不到滿足，將會推遲調度，它的資源得到滿足的時候會優先被調度進來。
優點：具有一定的公平性。
缺點：系統的吞吐率低，平均周轉時間長，有大作業到來的時，許多小作業推遲調度。
②計算時間短的作業優先．優先調度計算時間短的作業進行調度，資源不滿足的情況下推遲調度。在這種調度演算法下，要求用戶要對作業的計算時間預先有一個估計，調度以此為依據。
優點：由於被選中的作業計算時間，所以不能盡快地完成並退出系統，降低了作業的平均等待時間，提高了系統的吞吐率。
缺點：大作業會不滿意，而且極限情況下使得某些大作業始終得不到調度。
③響應比高者優先演算法。該演算法考慮了計算時間等待時間，既考慮了計算時間短的作業優先，又考慮了大作業長期等待的問題。所謂響應比是按照以下公式來定義的：
響應比R=等待時間/計算時間
這里的計算時間是估計的作業計算時間，從公式看，計算時間越短，響應比越高；而另一方面，大作業等待時間越長，響應比也會越大。一個作業完成以後，需要重新計算一下在輸入井中的各個作業的響應比，最高的將優先調度。
④優先數調度演算法。為每一個作業指定一個優先數，優先數高的作業先被調度。對於優先數相等的作業採用先來先服務的策略。優先數的制定原則是：作業的緩急程序，估計的計算時間，作業的等待時間，資源申請情況等因素綜合考慮。
⑤均衡調度演算法。使用不同資源的進程同時執行，減少作業等待同類設備而耗費的時間，加快作業的執行。
❽ 2018-06-09
一、常見的批處理作業調度演算法
1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。
2.短作業優先調度演算法(SPF): 就是優先調度並處理短作業，所謂短是指作業的運行時間短。而在作業未投入運行時，並不能知道它實際的運行時間的長短，因此需要用戶在提交作業時同時提交作業運行時間的估計值。
3.最高響應比優先演算法(HRN)：FCFS可能造成短作業用戶不滿，SPF可能使得長作業用戶不滿，於是提出HRN，選擇響應比最高的作業運行。響應比=1+作業等待時間/作業處理時間。
4. 基於優先數調度演算法(HPF)：每一個作業規定一個表示該作業優先順序別的整數，當需要將新的作業由輸入井調入內存處理時，優先選擇優先數最高的作業。
5.均衡調度演算法，即多級隊列調度演算法
基本概念：
作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)
作業平均周轉時間(T)＝周轉時間/作業個數
作業帶權周轉時間（Wi）＝周轉時間/運行時間
響應比＝（等待時間＋運行時間）/運行時間
二、進程調度演算法
1.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。
2. 時間片輪轉演算法(RR)：分時系統的一種調度演算法。輪轉的基本思想是，將CPU的處理時間劃分成一個個的時間片，就緒隊列中的進程輪流運行一個時間片。當時間片結束時，就強迫進程讓出CPU，該進程進入就緒隊列，等待下一次調度，同時，進程調度又去選擇就緒隊列中的一個進程，分配給它一個時間片，以投入運行。
3. 最高優先順序演算法(HPF)：進程調度每次將處理機分配給具有最高優先順序的就緒進程。最高優先順序演算法可與不同的CPU方式結合形成可搶占式最高優先順序演算法和不可搶占式最高優先順序演算法。
4. 多級隊列反饋法：幾種調度演算法的結合形式多級隊列方式。
三、空閑分區分配演算法
\1. 首先適應演算法：當接到內存申請時，查找分區說明表，找到第一個滿足申請長度的空閑區，將其分割並分配。此演算法簡單，可以快速做出分配決定。
2. 最佳適應演算法：當接到內存申請時，查找分區說明表，找到第一個能滿足申請長度的最小空閑區，將其進行分割並分配。此演算法最節約空間，因為它盡量不分割到大的空閑區，其缺點是可能會形成很多很小的空閑分區，稱為「碎片」。
3. 最壞適應演算法：當接到內存申請時，查找分區說明表，找到能滿足申請要求的最大的空閑區。該演算法的優點是避免形成碎片，而缺點是分割了大的空閑區後，在遇到較大的程序申請內存時，無法滿足的可能性較大。
四、虛擬頁式存儲管理中的頁面置換演算法
1.理想頁面置換演算法(OPT)：這是一種理想的演算法，在實際中不可能實現。該演算法的思想是：發生缺頁時，選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。
2.先進先出頁面置換演算法(FIFO)：選擇最先進入內存的頁面予以淘汰。
3. 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。
4.最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。
三、磁碟調度
1.先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置
2.最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題
3.掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。
4.循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。
對一個進程來說,一個重要的指標是它執行所需要的時間. 從進程提交到進程完成的時間間隔為周轉時間.也就是等待進入內存的時間,在就緒隊列中等待的時間,在 CPU中執行的時間和I/O操作的時間的總和.
例1.設一個系統中有5個進程，它們的到達時間和服務時間如下，A的到達時間為0，服務時間為3；B的到達時間為2，服務時間為6；C的到達時間為4，服務時間為4；D的到達時間為6，服務時間為5；E的 到達時間為8，服務時間為2，忽略1/0以及其他開銷時間，若分別按先來先服務（fFCFS）進行CPU調度，其平均周轉時間為？
10.2
6.4
8.6
4.5
先來先服務調度演算法
進程名 到達時間 服務時間 開始執行時間 完成時間 周轉時間
A 0 3 0 3 3
B 2 6 3 9 7
C 4 4 9 13 9
D 6 5 13 18 12
E 8 2 18 20 12
周轉時間 = 完成時間 - 到達時間
平均周轉時間 = 所有進程周轉時間 / 進程數 = （3+7+9+12+12）/ 5 = 8.6
單道批處理系統中有4個作業，J1的提交時間8.0，運行時間為2.0；J2的提交時間8.6，運行時間為0.6；J3提交時間8.8，運行時間為0.2；J4的提交時間9.0，運行時間為0.5。在採用響應比高者優先調度演算法時，其平均周轉時間為T為（）小時？
2.5
1.8
1.975
2.675
周轉時間=作業完成時間-作業提交時間
響應比=（作業等待時間+作業執行時間）/作業執行時間
當提交J1時，只有J1作業，執行J1，J1的周轉時間為2，此時時間為10.
J2、J3、J4提交時，由於正在執行J1，因此等待。
當J1執行完畢（此時時間為10），J2、J3、J4的等待時間分別為：1.4,1.2,1，
其響應比分別為：1.4/0.6+1=3.33 1.2/0.2+1=7 1/0.5+1=3，因此執行J3，J3的周轉時間為1.2+0.2=1.4
當J3執行完畢（此時時間為10.2），J2和J4的等待時間分別為1.6,1.2，
其響應比分別為：1.6/0.6+1=3.66 1.2/0.5+1=3.4，因此執行J2，J2的周轉時間為1.6+0.6=2.2
執行J2完畢後時間為10.8，接下來執行J4，執行完後時時間為11.3，J4的周轉時間為2.3
於是平均周轉時間為（2+1.4+2.2+2.3）/4=1.975
如果系統作業幾乎同時到達，則使系統平均作業周轉時間最短的演算法是短作業優先。
例3、
現有4個同時到達的作業J1,J2,J3和J4,它們的執行時間分別是3小時,5小時,7小時,9小時系統按單道方式運行且採用短作業優先演算法,則平均周轉時間是()小時
12.5
24
19
6
作業到達時間執行時間開始時間完成時間周轉時間
J103033
J20 5388
J30781515
J409152424
平均周轉時間（3+8+15+24）/4=12.5
有4個進程A,B,C,D,設它們依次進入就緒隊列，因相差時間很短可視為同時到達。4個進程按輪轉法分別運行11,7,2,和4個時間單位，設時間片為1。四個進程的平均周轉時間為 （）？
15.25
16.25
16.75
17.25
17.75
18.25
A:1 4 4 3 3 2 2 2 1 1 1 共24
B:2 4 4 3 3 2 2 共20
C:3 4 共7
D:4 4 3 3 共14
字母後面的數字為等待的時間加運行時間
平均周轉時間為（24+20+7+14）/4=16.25
例5、假設系統按單值方式運行且採用最短作業優先演算法，有J1,J2,J3,J4共4個作業同時到達，則以下哪幾種情況下的平均周轉時間為10分鍾?
執行時間J1:1分鍾 J2:5分鍾 J3:9分鍾 J4:13分鍾
執行時間J1:1分鍾 J2:4分鍾 J3:7分鍾 J4:10分鍾
執行時間J1:2分鍾 J2:4分鍾 J3:6分鍾 J4:8分鍾
執行時間J1:3分鍾 J2:6分鍾 J3:9分鍾 J4:12分鍾
首先，短作業優先則短時間的作業利用資源，其餘的作業等待
根據平均周轉時間概念，將所有作業"等待時間"加上"運行時間"除以"作業數量"即可得到平均周轉時間
A： (J1執行1分鍾 + J2等待1分鍾 + J2執行5分鍾 + J3等待6分鍾 + J3執行9分鍾 + J4等待15分鍾 + J4執行13分鍾) / 4 = 50/4 = 12.5
B： (J1執行1分鍾 + J2等待1分鍾 + J2執行4分鍾 + J3等待5分鍾 + J3執行7分鍾 + J4等待12分鍾 + J4執行10分鍾) / 4 = 40/4 = 10
C： (J1執行2分鍾 + J2等待2分鍾 + J2執行4分鍾 + J3等待6分鍾 + J3執行6分鍾 + J4等待12分鍾 + J4執行8分鍾) / 4 = 40/4 = 10
D： (J1執行3分鍾 + J2等待3分鍾 + J2執行6分鍾 + J3等待9分鍾 + J3執行9分鍾 + J4等待18分鍾 + J4執行12分鍾) / 4 = 50/4 = 12.5
例6、假設系統中有5個進程，它們的到達時間和服務時間見下表1，忽略I/O以及其他開銷時間，若按先來先服務（FCFS）、非搶占的短作業優先和搶占的短作業優先三種調度演算法進行CPU調度，請給出各個進程的完成時間、周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間，完成表2。 表1 進程到達和需要服務時間 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
表2 進程的完成時間和周轉時間
進程 A B C D E 平均
FCFS 完成時間 3 9 13 18 20
周轉時間 3 7 9 12 12 8.6
帶權周轉時間 1.00 1.17 2.25 2.40 6.00 2.56
SPF(非搶占) 完成時間 3 9 15 20 11
周轉時間 3 7 11 14 3 7.6
帶權周轉時間 1.00 1.17 1.75 2.80 1.50 1.84
SPF(搶占) 完成時間 3 15 8 20 10
周轉時間 3 13 4 14 2 7.2
帶權周轉時間 1.00 2.16 1.00 2.80 1.00 1.59
例7、假定在單道批處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示： 作業 進入系統時間 估計運行時間/分鍾 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18
5 9:10 5
如果應用先來先服務和應用最短作業優先的作業調度演算法，試將下面表格填寫完整。
(1) 如果應用先來先服務的作業調度演算法，試將下面表格填寫完整。
作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作業平均周轉時間T= 43.4 217
2）如果應用最短作業優先的作業調度演算法，試將下面表格填寫完整。 作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾 1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17作業平均周轉時間T= 37.2 186
CPU和兩台輸入/輸出設備(I1,I2)多道程序設計環境下,同時有三個作業J1,J2,J3進行,這三個作業
使用CPU和輸入/輸出設備的順序和時間如下所示:
J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)
J2:I1(25ms);CPU(30ms);I2(35ms)
J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);
假定CPU,I1,I2都能並行工作,J1的優先順序最高,J2次之,J3優先順序最低,優先順序高的作業可以搶占優先順序低的作業的CPU,但不能搶佔I1,I2,作業從J3開始到完成需要多少時間?