操作系統(tǒng)原理-進(jìn)程調(diào)度

進(jìn)程調(diào)度進(jìn)程調(diào)度教學(xué)內(nèi)容調(diào)度概念調(diào)度的原則進(jìn)程調(diào)度過程作業(yè)調(diào)度算法進(jìn)程調(diào)度算法Linux進(jìn)程調(diào)度Linux進(jìn)程調(diào)度實(shí)現(xiàn)教學(xué)重點(diǎn)調(diào)度概念作業(yè)調(diào)度算法進(jìn)程調(diào)度算法Linux進(jìn)程調(diào)度教學(xué)難點(diǎn)進(jìn)程調(diào)度算法Linux進(jìn)程調(diào)度6.1調(diào)度概念6.1操作系統(tǒng)直觀認(rèn)識(shí)和定義教學(xué)內(nèi)容調(diào)度的定義調(diào)度的分類教學(xué)重點(diǎn)6.1.1調(diào)度的定義6.1.1調(diào)度的定義調(diào)度調(diào)度在廣義上是指在一個(gè)隊(duì)列中，按照某種策略從中選擇一個(gè)最合適的個(gè)體。這個(gè)隊(duì)列一般是因?yàn)橥辉?、同一目?biāo)而聚合在一起的同一類對(duì)象的有序集合調(diào)度是操作系統(tǒng)的基本功能之一，幾乎所有的計(jì)算機(jī)資源在使用前都需要被合理調(diào)度。6.1.2調(diào)度的分類6.1.2調(diào)度的分類調(diào)度的分類按照調(diào)度的層次或原因可以分成長程調(diào)度、中程調(diào)度、短程調(diào)度和I/O調(diào)度。長程調(diào)度：宏觀調(diào)度或作業(yè)調(diào)度中程調(diào)度：交換調(diào)度短程調(diào)度：進(jìn)程調(diào)度I/O調(diào)度：設(shè)備調(diào)度6.1.2調(diào)度的分類調(diào)度的分類6.1.2調(diào)度的分類長程調(diào)度或作業(yè)調(diào)度在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，先駐留在磁盤上，組織成批處理隊(duì)列，稱為后備作業(yè)隊(duì)列。長程調(diào)度的功能是從多個(gè)作業(yè)構(gòu)成的后備作業(yè)隊(duì)列中，根據(jù)調(diào)度算法選取一個(gè)合適的作業(yè)調(diào)入內(nèi)存。6.1.2調(diào)度的分類中程調(diào)度或交換調(diào)度中程調(diào)度的主要目的是短期調(diào)節(jié)系統(tǒng)的負(fù)荷。中程調(diào)度的對(duì)象是進(jìn)程，把進(jìn)程在內(nèi)存和磁盤交換空間之間進(jìn)行對(duì)換（也稱為交換）。對(duì)換進(jìn)程的原因主要有兩個(gè)一是，內(nèi)存資源緊張需要騰空內(nèi)存空間，因此會(huì)掛起一些進(jìn)程，將這些暫時(shí)不運(yùn)行的進(jìn)程移到磁盤的交換空間；二是，為系統(tǒng)減負(fù)即減少并發(fā)性以降低系統(tǒng)開銷。6.1.2調(diào)度的分類短程調(diào)度或進(jìn)程調(diào)度短程調(diào)度是指進(jìn)程調(diào)度，決定哪個(gè)進(jìn)程將被執(zhí)行、哪些進(jìn)程將處于就緒狀態(tài)、哪些進(jìn)程處于等待狀態(tài)。進(jìn)程在運(yùn)行、就緒、阻塞3個(gè)基本狀態(tài)之間的轉(zhuǎn)換過程是由短程調(diào)度來驅(qū)動(dòng)的。短程調(diào)度的目標(biāo)之一就是使整個(gè)隊(duì)列被調(diào)度的延遲最小，并優(yōu)化系統(tǒng)的執(zhí)行效率。6.1.2調(diào)度的分類I/O調(diào)度或設(shè)備調(diào)度I/O調(diào)度是指當(dāng)I/O設(shè)備可用時(shí)，調(diào)度相應(yīng)的等待隊(duì)列中的進(jìn)程使用該設(shè)備。I/O調(diào)度屬于設(shè)備管理模塊的功能。I/O調(diào)度就是確定一個(gè)合適的順序來執(zhí)行來自進(jìn)程的I/O請(qǐng)求。6.2調(diào)度的原則6.2調(diào)度的原則教學(xué)內(nèi)容調(diào)度的宏觀原則調(diào)度的時(shí)間性能測度教學(xué)重點(diǎn)6.2.1調(diào)度的宏觀原則6.2.1調(diào)度的宏觀原則調(diào)度的宏觀原則（1）響應(yīng)速度盡可能快。對(duì)于交互程序來說，用戶期望完成輸入之后能夠盡快獲得輸出結(jié)果。（2）進(jìn)程處理的時(shí)間盡可能短。對(duì)于用戶來說，感興趣的進(jìn)程應(yīng)該盡可能多地占用CPU，盡量少地被從CPU上切出。（3）系統(tǒng)吞吐量盡可能大。該要求意味著系統(tǒng)應(yīng)在單位時(shí)間內(nèi)盡可能多地運(yùn)行用戶程序，處理更多的用戶數(shù)據(jù)。6.2.1調(diào)度的宏觀原則調(diào)度的宏觀原則（4）資源利用率盡可能高。資源利用率高意味著包括CPU在內(nèi)的所有資源都被盡量保持著忙碌。（5）對(duì)所有進(jìn)程要公平。調(diào)度程序應(yīng)該平等地調(diào)度每個(gè)進(jìn)程。（6）避免饑餓。調(diào)度程序不應(yīng)該忽略某些進(jìn)程，使其長時(shí)間得不到運(yùn)行或得不到所需要的I/O設(shè)備。（7）避免死鎖。調(diào)度程序確保分配資源的順序合理，不會(huì)造成兩個(gè)或多個(gè)進(jìn)程陷入死鎖。上述原則都是理想化的原則。理論上，任何一個(gè)操作系統(tǒng)都無法同時(shí)滿足上述原則。6.2.2調(diào)度的時(shí)間性能測度6.2.2調(diào)度的時(shí)間性能測度周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間是指作業(yè)從提交給計(jì)算機(jī)開始到給出結(jié)果所花費(fèi)的時(shí)間。詳細(xì)來說，這個(gè)時(shí)間包括在后備作業(yè)隊(duì)列上的等待時(shí)間、對(duì)應(yīng)進(jìn)程在內(nèi)存就緒隊(duì)列中的等待時(shí)間、對(duì)應(yīng)進(jìn)程在CPU上真正運(yùn)行的時(shí)間、對(duì)應(yīng)進(jìn)程等待I/O操作完成的阻塞時(shí)間等。t=tc

–tsts：作業(yè)的提交時(shí)刻（Start）tc：作業(yè)的完成時(shí)刻（Complete）6.2.2調(diào)度的時(shí)間性能測度周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間的長短說明了作業(yè)在系統(tǒng)中停留時(shí)間的長短。這個(gè)時(shí)間越短越好，時(shí)間越短用戶體驗(yàn)越好。平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間是指一批作業(yè)的周轉(zhuǎn)時(shí)間的平均值。用t'表示平均周轉(zhuǎn)時(shí)間，計(jì)算公式如下：t'=（t1+t2+…+tn）/n其中：t1，t2，…，tn是n個(gè)作業(yè)各自的周轉(zhuǎn)時(shí)間。平均周轉(zhuǎn)時(shí)間意味著一批作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間長短。平均周轉(zhuǎn)時(shí)間比單個(gè)作業(yè)的周轉(zhuǎn)時(shí)間更能描述系統(tǒng)的整體性能。6.2.2調(diào)度的時(shí)間性能測度帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與執(zhí)行時(shí)間的比值。用w表示帶權(quán)周轉(zhuǎn)時(shí)間，計(jì)算公式如下：w=t/tr其中：t：進(jìn)程的周轉(zhuǎn)時(shí)間tr：進(jìn)程的運(yùn)行時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間的意義在于表明了作業(yè)在系統(tǒng)中的相對(duì)停留時(shí)間，消除了因?yàn)樽鳂I(yè)大小不同而導(dǎo)致絕對(duì)的周轉(zhuǎn)時(shí)間缺少比較價(jià)值的問題。6.2.2調(diào)度的時(shí)間性能測度平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間是一組作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間的平均值。用w'表示平均帶權(quán)周轉(zhuǎn)時(shí)間，計(jì)算公式：w'=（w1+w2+…+wn）/n其中：w1，w2，…，wn是n個(gè)作業(yè)各自的帶權(quán)周轉(zhuǎn)時(shí)間。平均帶權(quán)周轉(zhuǎn)時(shí)間意味著一批作業(yè)在系統(tǒng)內(nèi)相對(duì)停留的時(shí)間長短。平均帶權(quán)周轉(zhuǎn)時(shí)間比平均周轉(zhuǎn)時(shí)間更能公平地描述系統(tǒng)的整體性能。6.3進(jìn)程調(diào)度過程6.3進(jìn)程調(diào)度過程教學(xué)內(nèi)容進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的方式教學(xué)重點(diǎn)6.3.1進(jìn)程調(diào)度的功能6.3.1進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的功能根據(jù)一定的調(diào)度策略或指標(biāo)遍歷所有的就緒進(jìn)程，從中選擇一個(gè)最合適的進(jìn)程。選擇該進(jìn)程的過程實(shí)際是用戶按特定指標(biāo)對(duì)所有進(jìn)程進(jìn)行排隊(duì)的過程。6.3.2進(jìn)程調(diào)度的時(shí)機(jī)6.3.2進(jìn)程調(diào)度的時(shí)機(jī)1．時(shí)鐘中斷時(shí)鐘中斷是最頻繁且周期性地引發(fā)進(jìn)程調(diào)度的事件之一。2．I/O中斷外部設(shè)備發(fā)生了I/O中斷，在中斷服務(wù)程序返回用戶態(tài)之前。3．異常當(dāng)進(jìn)程運(yùn)行過程中，有異常發(fā)生。4．進(jìn)程結(jié)束當(dāng)進(jìn)程結(jié)束后，系統(tǒng)會(huì)選擇一個(gè)新進(jìn)程來運(yùn)行。5．系統(tǒng)調(diào)用一般是在執(zhí)行完系統(tǒng)調(diào)用，系統(tǒng)程序返回用戶進(jìn)程之前6．主動(dòng)調(diào)度當(dāng)進(jìn)程因?yàn)楦鞣N原因被阻塞時(shí)6.3.3進(jìn)程調(diào)度的方式6.3.3進(jìn)程調(diào)度的方式進(jìn)程調(diào)度的方式非搶占方式又稱非剝奪式調(diào)度它是指進(jìn)程調(diào)度程序一旦把CPU分配給某進(jìn)程后，該進(jìn)程可以一直運(yùn)行下去，在它的時(shí)間片用完之前，或任務(wù)完成之前，或因?yàn)镮/O請(qǐng)求被阻塞之前，決不允許其他進(jìn)程搶走它的CPU。搶占方式又稱剝奪式調(diào)度搶占方式允許進(jìn)程調(diào)度程序根據(jù)某種策略終止當(dāng)前正在運(yùn)行的進(jìn)程，將其移入就緒隊(duì)列，再根據(jù)某種調(diào)度算法選擇另一個(gè)進(jìn)程投入運(yùn)行。當(dāng)高優(yōu)先級(jí)進(jìn)程來到時(shí)，進(jìn)程調(diào)度程序會(huì)把當(dāng)前進(jìn)程切出，把CPU讓給新進(jìn)程。搶占方式調(diào)度開銷大，但是其優(yōu)點(diǎn)是實(shí)時(shí)性好，系統(tǒng)整體性能較高。6.4作業(yè)調(diào)度算法6.4作業(yè)調(diào)度算法教學(xué)內(nèi)容先來先服務(wù)調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法教學(xué)重點(diǎn)6.4.1先來先服務(wù)調(diào)度算法6.4.1先來先服務(wù)調(diào)度算法先來先服務(wù)（FirstComeFirstService，F(xiàn)CFS）基本思路：按照作業(yè)進(jìn)入系統(tǒng)的時(shí)間先后次序從后備作業(yè)隊(duì)列中挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被運(yùn)行，一直到該作業(yè)運(yùn)行完畢才讓出處理機(jī)。特點(diǎn)先來先服務(wù)調(diào)度算法容易實(shí)現(xiàn)，但是效率不高。該算法只考慮作業(yè)的等待時(shí)間，而沒考慮運(yùn)行時(shí)間的長短。因此一個(gè)晚來但是很短的作業(yè)可能需要等待很長時(shí)間才能被運(yùn)行，因而算法不利于短作業(yè)。先來先服務(wù)調(diào)度算法很少單獨(dú)用作調(diào)度策略，通常與其他調(diào)度算法聯(lián)合使用。6.4.1先來先服務(wù)調(diào)度算法先來先服務(wù)（FirstComeFirstService，F(xiàn)CFS）例子：假設(shè)系統(tǒng)中有4個(gè)作業(yè)先后投入，它們的作業(yè)大小和進(jìn)入時(shí)間如表（作業(yè)大小和時(shí)間單位分鐘）作業(yè)大小進(jìn)入時(shí)刻開始時(shí)刻結(jié)束時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間A200020201.0046.252.19B40102060501.25C30156090752.50D106090100404.006.4.2短作業(yè)優(yōu)先調(diào)度算法6.4.2短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先（ShortestJobFirst，SJF）調(diào)度算法參考運(yùn)行時(shí)間，從后備作業(yè)隊(duì)列中選取運(yùn)行時(shí)間最短的作業(yè)優(yōu)先投入運(yùn)行。特點(diǎn)短作業(yè)優(yōu)先調(diào)度算法易于實(shí)現(xiàn)，能較好降低一組作業(yè)的平均等待時(shí)間，有利于提高系統(tǒng)的吞吐量。算法忽視了作業(yè)等待時(shí)間，一個(gè)早來，但是很長的作業(yè)將會(huì)在很長時(shí)間得不到調(diào)度，易出現(xiàn)資源“饑餓”的現(xiàn)象。6.4.2短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先（ShortestJobFirst，SJF）例子：假設(shè)系統(tǒng)中有4個(gè)作業(yè)先后投入，它們的作業(yè)大小和進(jìn)入時(shí)間如表（作業(yè)大小和時(shí)間單位分鐘）作業(yè)大小進(jìn)入時(shí)刻開始時(shí)刻結(jié)束時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間A200020201.0043.752.04B40105090802.00C30152050351.17D106090100404.006.4.3響應(yīng)比高者優(yōu)先調(diào)度算法6.4.3響應(yīng)比高者優(yōu)先調(diào)度算法作業(yè)的響應(yīng)比作業(yè)的響應(yīng)比被定義為作業(yè)的響應(yīng)時(shí)間和運(yùn)行時(shí)間的比值，計(jì)算公式為：響應(yīng)比=響應(yīng)時(shí)間/運(yùn)行時(shí)間

=（等待時(shí)間+運(yùn)行時(shí)間）/運(yùn)行時(shí)間

=1+等待時(shí)間/運(yùn)行時(shí)間響應(yīng)比高者優(yōu)先調(diào)度算法計(jì)算作業(yè)列表中每個(gè)作業(yè)的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)優(yōu)先投入運(yùn)行。該算法同時(shí)考慮了作業(yè)的等待時(shí)間長短和作業(yè)的大小，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。6.4.3響應(yīng)比高者優(yōu)先調(diào)度算法特點(diǎn)響應(yīng)比高者優(yōu)先調(diào)度算法有利于短作業(yè)。如果作業(yè)等待時(shí)間相同，則運(yùn)行時(shí)間越短的作業(yè)，其響應(yīng)比越高，因此越容易被調(diào)度。響應(yīng)比高者優(yōu)先調(diào)度算法有利于等候已久的作業(yè)。如果作業(yè)運(yùn)行時(shí)間相同，則等待時(shí)間越長的作業(yè)，其響應(yīng)比越高，因此越容易被調(diào)度。因而有利于等待時(shí)間很長的作業(yè)。響應(yīng)比高者優(yōu)先調(diào)度算法有利于長作業(yè)。對(duì)于運(yùn)行時(shí)間長的作業(yè)，其響應(yīng)比可以隨等待時(shí)間的增加而提高，當(dāng)其等待足夠久的時(shí)侯，也有可能獲得CPU。6.4.3響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法例子：假設(shè)系統(tǒng)中有4個(gè)作業(yè)先后投入，它們的作業(yè)大小和進(jìn)入時(shí)間如表（作業(yè)大小和時(shí)間單位分鐘）作業(yè)大小進(jìn)入時(shí)刻開始時(shí)刻結(jié)束時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間A200020201.0046.252.19B40102060501.25C30156090752.50D106090100404.006.5進(jìn)程調(diào)度算法6.5進(jìn)程調(diào)度算法教學(xué)內(nèi)容優(yōu)先數(shù)高者優(yōu)先調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法多重時(shí)間片輪轉(zhuǎn)調(diào)度算法教學(xué)重點(diǎn)6.5.1優(yōu)先數(shù)高者優(yōu)先調(diào)度算法6.5.1優(yōu)先數(shù)高者優(yōu)先調(diào)度算法優(yōu)先數(shù)高者優(yōu)先（HighestPriorityFirst,HPF）算法根據(jù)進(jìn)程的優(yōu)先數(shù)，把CPU分配給最高的進(jìn)程。該算法同樣適合于作業(yè)調(diào)度，給每個(gè)作業(yè)分配合適的優(yōu)先數(shù)，就可以根據(jù)該參數(shù)來調(diào)度作業(yè)。優(yōu)先數(shù)描述了進(jìn)程需要運(yùn)行的緊迫程度。進(jìn)程優(yōu)先數(shù)包括靜態(tài)優(yōu)先數(shù)和動(dòng)態(tài)優(yōu)先數(shù)兩個(gè)參數(shù)。靜態(tài)優(yōu)先數(shù)是進(jìn)程創(chuàng)建時(shí)確定的，在整個(gè)進(jìn)程運(yùn)行期間不再改變；而動(dòng)態(tài)優(yōu)先數(shù)在進(jìn)程運(yùn)行期間可以根據(jù)運(yùn)行環(huán)境和進(jìn)程自身狀態(tài)進(jìn)行微調(diào)。6.5.1優(yōu)先數(shù)高者優(yōu)先調(diào)度算法靜態(tài)優(yōu)先數(shù)靜態(tài)優(yōu)先數(shù)根據(jù)進(jìn)程的靜態(tài)特性，在進(jìn)程創(chuàng)建之時(shí)進(jìn)行設(shè)置，一旦開始執(zhí)行之后就不能改變。確定進(jìn)程的靜態(tài)優(yōu)先數(shù)可以從以下3個(gè)方面考慮。（1）基于進(jìn)程所需資源的多少確定（2）基于進(jìn)程運(yùn)行時(shí)間的長短確定（3）基于進(jìn)程的類型確定。6.5.1優(yōu)先數(shù)高者優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先數(shù)在進(jìn)程運(yùn)行過程中微調(diào)優(yōu)先數(shù)，這就是動(dòng)態(tài)優(yōu)先數(shù)進(jìn)程的動(dòng)態(tài)優(yōu)先數(shù)一般根據(jù)以下原則確定。（1）當(dāng)使用CPU超過一定時(shí)長時(shí)（2）當(dāng)進(jìn)程等待時(shí)間超過一定時(shí)長時(shí)（3）當(dāng)進(jìn)行I/O操作后6.5.2時(shí)間片輪轉(zhuǎn)調(diào)度算法6.5.2時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)（RoundRobin，RR）調(diào)度算法把所有就緒進(jìn)程按先進(jìn)先出的原則排成隊(duì)列。新來進(jìn)程加到隊(duì)列末尾。進(jìn)程以時(shí)間片q為單位輪流使用CPU。剛剛運(yùn)行了一個(gè)時(shí)間片的進(jìn)程排到隊(duì)列末尾，等候下一輪調(diào)度。隊(duì)列邏輯上構(gòu)成一個(gè)環(huán)。6.5.2時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法的優(yōu)點(diǎn)具有公平性和交互性。每個(gè)就緒進(jìn)程有平等機(jī)會(huì)獲得CPU；每個(gè)進(jìn)程僅需要等待(N-1)*q的時(shí)間就可以再次獲得CPU，其中N是就緒進(jìn)程的數(shù)量。時(shí)間片長度的選擇如果時(shí)間片太短，必然會(huì)導(dǎo)致時(shí)鐘中斷頻繁，進(jìn)程切換頻繁，這會(huì)增加系統(tǒng)額外的開銷。如果時(shí)間片太長，必然會(huì)降低系統(tǒng)交互性能，延長系統(tǒng)響應(yīng)時(shí)間。若時(shí)間片變得足夠長，時(shí)間片輪轉(zhuǎn)調(diào)度算法就退化為先來先服務(wù)調(diào)度算法。如果系統(tǒng)并發(fā)進(jìn)程數(shù)量少，可以適當(dāng)延長時(shí)間片，以便提升系統(tǒng)整體性能。6.5.3多重時(shí)間片輪轉(zhuǎn)調(diào)度算法6.5.3多重時(shí)間片輪轉(zhuǎn)調(diào)度算法多重時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法的拓展算法。系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)優(yōu)先級(jí)，從下到上各層的優(yōu)先數(shù)依次升高。各個(gè)就緒隊(duì)列所用的時(shí)間片不同，高優(yōu)先級(jí)的隊(duì)列時(shí)間片短，低優(yōu)先級(jí)的隊(duì)列時(shí)間片長。通常優(yōu)先級(jí)每提高一級(jí)時(shí)間片就降低一半。6.5.3多重時(shí)間片輪轉(zhuǎn)調(diào)度算法多重時(shí)間片輪轉(zhuǎn)調(diào)度算法系統(tǒng)先運(yùn)行第1個(gè)隊(duì)列中的進(jìn)程；僅當(dāng)?shù)?個(gè)隊(duì)列空后，才運(yùn)行第2個(gè)隊(duì)列中的進(jìn)程；僅當(dāng)前面所有的隊(duì)列為空時(shí)，才會(huì)運(yùn)行最后第N個(gè)隊(duì)列中的進(jìn)程。6.6Linux進(jìn)程調(diào)度6.6Linux進(jìn)程調(diào)度教學(xué)內(nèi)容Linux調(diào)度機(jī)制完全公平調(diào)度算法教學(xué)重點(diǎn)6.6.1Linux調(diào)度機(jī)制6.6.1Linux調(diào)度機(jī)制Linux進(jìn)程的優(yōu)先級(jí)Linux進(jìn)程的優(yōu)先級(jí)由靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)兩者組成，構(gòu)成一個(gè)全局優(yōu)先級(jí)來滿足調(diào)度要求。靜態(tài)優(yōu)先級(jí)在進(jìn)程創(chuàng)建時(shí)指定，也可以由用戶調(diào)用sys_setpriority()函數(shù)修改，或者修改進(jìn)程的nice值間接改變靜態(tài)優(yōu)先級(jí)。動(dòng)態(tài)優(yōu)先級(jí)在進(jìn)程運(yùn)行期間可以根據(jù)實(shí)際并發(fā)情況來調(diào)整。有一個(gè)基本原則就是只要進(jìn)程占用了CPU，其動(dòng)態(tài)優(yōu)先級(jí)就隨時(shí)間的流逝而不斷減小，直到0為止。6.6.1Linux調(diào)度機(jī)制調(diào)度策略對(duì)于普通進(jìn)程，即分時(shí)進(jìn)程使用基于動(dòng)態(tài)優(yōu)先級(jí)（SCHED_OTHER）的調(diào)度策略，即進(jìn)程每運(yùn)行一個(gè)時(shí)間片，當(dāng)該時(shí)間片結(jié)束時(shí)，重新計(jì)算就緒隊(duì)列中每個(gè)進(jìn)程的優(yōu)先級(jí)，若其他進(jìn)程的優(yōu)先級(jí)高于當(dāng)前進(jìn)程時(shí)，由調(diào)度函數(shù)調(diào)度優(yōu)先級(jí)高的進(jìn)程執(zhí)行，而把被搶占的進(jìn)程保存到就緒隊(duì)列中等候下一輪調(diào)度。對(duì)于實(shí)時(shí)進(jìn)程采用兩種調(diào)度策略：先進(jìn)先出（SCHED_FIFO）和時(shí)間片輪轉(zhuǎn)（SCHED_RR）。6.6.1Linux調(diào)度機(jī)制進(jìn)程控制塊task_struct與進(jìn)程調(diào)度有關(guān)的成員變量policy：指明進(jìn)程的調(diào)度策略，也用來區(qū)分實(shí)時(shí)進(jìn)程和普通進(jìn)程。可取值有SCHED_OTHER、SCHED_FIFO、SCHED_RR等。priority：指明進(jìn)程（包括實(shí)時(shí)和普通進(jìn)程）的靜態(tài)優(yōu)先級(jí)。rt_priority：指明實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)。counter：指明進(jìn)程還能連續(xù)運(yùn)行的最大時(shí)間片數(shù)量。counter的初值等于靜態(tài)優(yōu)先級(jí)priority。在進(jìn)程執(zhí)行期間，隨著占用CPU時(shí)間的延長而不斷減少。6.6.1Linux調(diào)度機(jī)制調(diào)度函數(shù)schedule()schedule()函數(shù)的作用是實(shí)現(xiàn)進(jìn)程調(diào)度，在就緒隊(duì)列中找到優(yōu)先級(jí)更高的進(jìn)程并給它分配CPU。兩個(gè)過程，一是選擇進(jìn)程，二是切換進(jìn)程。（1）選擇進(jìn)程選擇進(jìn)程主要是掃描就緒隊(duì)列的所有活動(dòng)進(jìn)程，從中選擇一個(gè)合適的進(jìn)程。選擇進(jìn)程的依據(jù)是采用函數(shù)goodness()計(jì)算每一個(gè)就緒進(jìn)程值得運(yùn)行的程度，即權(quán)值（weight）。goodness()在計(jì)算進(jìn)程的權(quán)值過程中，確保實(shí)時(shí)進(jìn)程的權(quán)值要比普通進(jìn)程大得多。6.6.1Linux調(diào)度機(jī)制調(diào)度函數(shù)schedule()schedule()函數(shù)的作用是實(shí)現(xiàn)進(jìn)程調(diào)度，在就緒隊(duì)列中找到優(yōu)先級(jí)更高的進(jìn)程并給它分配CPU。兩個(gè)過程，一是選擇進(jìn)程，二是切換進(jìn)程。（2）切換進(jìn)程切換進(jìn)程完成當(dāng)前進(jìn)程到新進(jìn)程的上下文切換。上下文包括頁全局目錄、內(nèi)核堆棧、CPU上下文等。切換頁全局目錄的目的是更新新的地址空間；切換內(nèi)核堆棧和CPU上下文是因?yàn)樗鼈兲峁┝藘?nèi)核執(zhí)行新進(jìn)程所需要的信息，包含CPU寄存器等。切換進(jìn)程由switch_to宏完成。6.6.1Linux調(diào)度機(jī)制進(jìn)程調(diào)度兩種方式：非搶占式調(diào)度和搶占式調(diào)度對(duì)非搶占式調(diào)度高優(yōu)先級(jí)的進(jìn)程不能中止正在內(nèi)核中運(yùn)行的低優(yōu)先級(jí)的進(jìn)程而搶占CPU運(yùn)行。搶占式調(diào)度支持在內(nèi)核搶占低優(yōu)先級(jí)進(jìn)程的CPU。6.6.1Linux調(diào)度機(jī)制進(jìn)程調(diào)度兩種方式：非搶占式調(diào)度和搶占式調(diào)度6.6.1Linux調(diào)度機(jī)制調(diào)度的時(shí)機(jī)調(diào)度的時(shí)機(jī)是指何時(shí)進(jìn)行重新調(diào)度，即重新分配CPU資源的問題。（1）當(dāng)正在執(zhí)行的進(jìn)程分到的時(shí)間片用完時(shí)。（2）進(jìn)程執(zhí)行exit()函數(shù)或阻塞調(diào)用sleep()函數(shù)時(shí)。（3）當(dāng)進(jìn)程從系統(tǒng)調(diào)用返回到用戶態(tài)時(shí)。（4）當(dāng)中斷處理程序返回用戶態(tài)時(shí)。（5）直接執(zhí)行調(diào)度函數(shù)schedule()。6.6.2完全公平調(diào)度算法6.6.2完全公平調(diào)度算法完全公平調(diào)度算法算法思路就是根據(jù)各個(gè)進(jìn)程的權(quán)重分配運(yùn)行時(shí)間。進(jìn)程的運(yùn)行時(shí)間計(jì)算公式為：調(diào)度周期是指讓所有處于TASK_RUNNING的進(jìn)程都調(diào)度運(yùn)行一次所花的時(shí)間和。系統(tǒng)中現(xiàn)在有3個(gè)進(jìn)程A、B、C，權(quán)重分別為1、2、2。假設(shè)調(diào)度周期為100ms，那么分配給A的CPU時(shí)間為20ms分配給進(jìn)程的運(yùn)行時(shí)間=調(diào)度周期×6.6.2完全公平調(diào)度算法完全公平調(diào)度算法進(jìn)程的運(yùn)行時(shí)間用VirtualRunTime（vruntime）來記錄，它記錄著進(jìn)程已經(jīng)運(yùn)行的時(shí)間，但是并不是直接記錄，而是根據(jù)進(jìn)程權(quán)重將實(shí)際運(yùn)行時(shí)間進(jìn)行了一個(gè)等比縮放。公平調(diào)度的思想確保所有進(jìn)程虛擬運(yùn)行時(shí)間vruntime的增長速度在宏觀上應(yīng)該是相同的。算法選擇虛擬運(yùn)行時(shí)間vruntime最小的進(jìn)程作為下一個(gè)要運(yùn)行的進(jìn)程。一個(gè)進(jìn)程的vruntime較小，就說明它累計(jì)占用的CPU時(shí)間較短，受到了“不公平”的對(duì)待，因此下一個(gè)運(yùn)行進(jìn)程就要選擇它。6.7Linux進(jìn)程調(diào)度實(shí)現(xiàn)6.7Linux進(jìn)程調(diào)度實(shí)現(xiàn)教學(xué)內(nèi)容Linux0.12進(jìn)程調(diào)度策略Linux0.12進(jìn)程切換過程Linux0.12進(jìn)程調(diào)度時(shí)機(jī)Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度Linux0.12進(jìn)程睡眠與喚醒Linux內(nèi)核搶占機(jī)制教學(xué)重點(diǎn)6.7.1Linux0.12進(jìn)程調(diào)度策略6.7.1Linux0.12進(jìn)程調(diào)度策略Linux0.12的調(diào)度策略調(diào)度程序會(huì)掃描任務(wù)數(shù)組，從中選擇時(shí)間片counter最大的就緒態(tài)（TASK_RUNNING）進(jìn)程，并切換到該進(jìn)程運(yùn)行。如果所有處于就緒態(tài)的進(jìn)程的時(shí)間片都已用完，調(diào)度程序就會(huì)根據(jù)每個(gè)進(jìn)程的priority字段，對(duì)所有進(jìn)程重新計(jì)算時(shí)間片counter=counter/2+priority重復(fù)上述過程重新調(diào)度如果沒有找到可運(yùn)行的進(jìn)程，調(diào)度執(zhí)行進(jìn)程0。進(jìn)程0是idle進(jìn)程，會(huì)調(diào)用pause()以再次調(diào)用schedule()來尋找可調(diào)度的進(jìn)程。6.7.1Linux0.12進(jìn)程調(diào)度策略Linux0.12中進(jìn)程調(diào)度的實(shí)現(xiàn)6.7.2Linux0.12進(jìn)程切換過程6.7.2Linux0.12進(jìn)程切換過程Linux0.12的進(jìn)程切換/任務(wù)切換采用宏switch_to()來實(shí)現(xiàn)進(jìn)程切換前首先判斷需要切換進(jìn)來的新進(jìn)程是否是當(dāng)前進(jìn)程。如果是，則什么都不做，直接返回；如果不是，則進(jìn)行進(jìn)程切換。6.7.3Linux0.12進(jìn)程調(diào)度時(shí)機(jī)6.7.3Linux0.12進(jìn)程調(diào)度時(shí)機(jī)Linux0.12定義的進(jìn)程狀態(tài)有5種#defineTASK_RUNNING

0

//在運(yùn)行或可被運(yùn)行狀態(tài)#defineTASK_INTERRUPTIBLE

1

//可被中斷阻塞狀態(tài)#defineTASK_UNINTERRUPTIBLE

2

//不可中斷阻塞狀態(tài)#defineTASK_ZOMBIE

3

//僵死狀態(tài)#defineTASK_STOPPED

4

//停止?fàn)顟B(tài)Linux0.12會(huì)在3種情況調(diào)用schedule()進(jìn)行進(jìn)程調(diào)度（1）時(shí)鐘中斷處理發(fā)現(xiàn)時(shí)間片用完且處于用戶態(tài)時(shí)；（2）系統(tǒng)調(diào)用時(shí)相應(yīng)的處理函數(shù)返回后；（3）睡眠函數(shù)sleep_on()內(nèi)。6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度基于時(shí)鐘中斷的進(jìn)程調(diào)度主要流程首先，內(nèi)核通過sched_init()函數(shù)完成時(shí)鐘中斷進(jìn)行調(diào)度管理的初始化工作。該函數(shù)在后半部分完成了時(shí)鐘調(diào)度管理的初始化工作。此外，該函數(shù)也在前半部分完成與調(diào)度管理無直接關(guān)系的初始化工作，包括初始化全局描述符表、初始化任務(wù)0的任務(wù)狀態(tài)段描述符和局部描述符表段描述符，設(shè)置系統(tǒng)調(diào)用相關(guān)的中斷門等。其次，通過時(shí)鐘中斷處理函數(shù)_timer_interrupt()完成進(jìn)程選擇和切換。該函數(shù)中調(diào)用了do_timer()函數(shù)、schedule()函數(shù)和switch_to()宏。6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度基于時(shí)鐘中斷的進(jìn)程調(diào)度主要流程時(shí)鐘中斷處理函數(shù)_timer_interrupt()6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度調(diào)度管理初始化函數(shù)sched_init()6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度時(shí)鐘中斷處理函數(shù)_timer_interrupt()6.7.4Linux0.12基于時(shí)鐘中斷的進(jìn)程調(diào)度