進(jìn)程調(diào)度
面試的時(shí)候被問到進(jìn)程調(diào)度，當(dāng)時(shí)不清楚，場(chǎng)面一度十分尷尬崎苗，下來之后自己又復(fù)習(xí)了一下。
多任務(wù)
1.多任務(wù)操作系統(tǒng)就是能同時(shí)并發(fā)的執(zhí)行多個(gè)進(jìn)程的操作系統(tǒng)舀寓。
2.多任務(wù)操作系統(tǒng)使多個(gè)進(jìn)程處于阻塞或者睡眠狀態(tài)胆数，實(shí)際不被投入執(zhí)行，這些任務(wù)盡管位于內(nèi)存互墓，但是并不處于可運(yùn)行狀態(tài)必尼。
3.多任務(wù)系統(tǒng)分類：
(1) 非搶占式多任務(wù)
(2) 搶占式多任務(wù)
- linux提供了搶占式的多任務(wù)模式。在此模式下篡撵，由調(diào)度程序來決定什么時(shí)候停止一個(gè)進(jìn)程的運(yùn)行判莉，以便其他進(jìn)程能夠得到執(zhí)行機(jī)會(huì)。這個(gè)強(qiáng)制的掛起動(dòng)作叫做搶占育谬。進(jìn)程被搶占之前能夠運(yùn)行的時(shí)間是預(yù)先設(shè)置好的券盅，叫進(jìn)程的時(shí)間片。時(shí)間片實(shí)際上就是分配給每個(gè)可運(yùn)行進(jìn)程的處理器時(shí)間段膛檀。
- 在非搶占式多任務(wù)模式下锰镀，除非進(jìn)程自己主動(dòng)停止運(yùn)行，否則它會(huì)一直執(zhí)行咖刃。進(jìn)程主動(dòng)掛起自己的操作稱為讓步泳炉。但這種機(jī)制有很多缺點(diǎn)：調(diào)度程序無法為每個(gè)進(jìn)程執(zhí)行多長時(shí)間做出統(tǒng)一規(guī)定，所以進(jìn)程獨(dú)占的處理器時(shí)間可能會(huì)超過用戶的預(yù)料：更糟的是嚎杨，一個(gè)絕不做出讓步的懸掛進(jìn)程就能使系統(tǒng)崩潰胡桃。
linux的進(jìn)程調(diào)度
- O(1)調(diào)度器擁有數(shù)以十計(jì)的多處理器的環(huán)境，但缺少交互進(jìn)程磕潮。
- 反轉(zhuǎn)樓梯最后期限調(diào)度算法翠胰，吸取隊(duì)列理論容贝，公平調(diào)度。又被稱為完美公平調(diào)度算法（CFS）之景。
策略
- 決定調(diào)度程序在何時(shí)讓進(jìn)程運(yùn)行
I/O消耗型和處理器消耗型的進(jìn)程
1.進(jìn)程可以分為：
（1）I/O消耗型：進(jìn)程的大部分時(shí)間用來提交I/O請(qǐng)求或者等待I/O請(qǐng)求斤富，經(jīng)常處于可運(yùn)行狀態(tài)但是運(yùn)行時(shí)間很短，等待更多的請(qǐng)求時(shí)最后總會(huì)阻塞锻狗。
(2) 處理器消耗型：把時(shí)間大多用在執(zhí)行代碼上满力，除非被搶占，否則通常都會(huì)不停地運(yùn)行轻纪。因?yàn)樗麄儧]有太多的I/O需求油额。不屬于I/O驅(qū)動(dòng)類型。
2.調(diào)度策略：盡量降低它們的調(diào)度頻率刻帚，延長其運(yùn)行時(shí)間潦嘶。
- 調(diào)度策略通常要在兩個(gè)矛盾的目標(biāo)中間尋求平衡：
（1）進(jìn)程調(diào)度迅速（響應(yīng)時(shí)間短）
(2) 最大系統(tǒng)利用率（高吞吐量） - linux傾向于有限調(diào)度I/O消耗型進(jìn)程。
進(jìn)程優(yōu)先級(jí)
1.調(diào)度算法種最基本的一類就是基于優(yōu)先級(jí)的調(diào)度崇众，這是一種根據(jù)進(jìn)程的價(jià)值和其對(duì)處理器時(shí)間的需求來對(duì)進(jìn)程分級(jí)的想法掂僵。
- 調(diào)度程序總是選擇時(shí)間片未用盡而且優(yōu)先級(jí)較高的進(jìn)程運(yùn)行。
- linux采用了兩種不同的優(yōu)先級(jí)范圍：
（1）nice
范圍[-20,19]顷歌，默認(rèn)值為0锰蓬；nice值越大，優(yōu)先級(jí)越低眯漩；
linux系統(tǒng)中nice值代表時(shí)間片的比例芹扭，可以通過ps -el命令查看系統(tǒng)中進(jìn)程列表，結(jié)果中標(biāo)記NI的一列及時(shí)進(jìn)程對(duì)應(yīng)得nice值赦抖。
（2）實(shí)時(shí)優(yōu)先級(jí)
其值可以配置舱卡，默認(rèn)變化范圍是[0,99];值越高優(yōu)先級(jí)越高
4.任何實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)都高于普通的進(jìn)程，也就是說實(shí)時(shí)優(yōu)先級(jí)和nice優(yōu)先級(jí)處于互不相交的兩個(gè)范疇摹芙。 - 通過命令ps -eo state,uid,pid,ppid,rtprio,time,comm.查看系統(tǒng)中的進(jìn)程列表以及對(duì)應(yīng)的實(shí)時(shí)優(yōu)先級(jí)（位于RTPRIO列下）灼狰，其中如果進(jìn)程對(duì)應(yīng)顯示“-”,則說明它不是實(shí)時(shí)進(jìn)程宛瞄。
時(shí)間片
1.時(shí)間片表示進(jìn)程在被搶占前所能持續(xù)運(yùn)行運(yùn)行的時(shí)間浮禾。
2.I/O消耗型進(jìn)程不需要很長的時(shí)間片，而處理器消耗型進(jìn)程希望時(shí)間片越長越好份汗。
3.linux的CFS調(diào)度器沒有直接分配時(shí)間片到進(jìn)程盈电，而是將處理器的使用比化分給進(jìn)程。這樣一來杯活，進(jìn)程鎖獲得的處理器時(shí)間和系統(tǒng)密切相關(guān)匆帚。這個(gè)比例受nice值影響，nice值作為權(quán)重來調(diào)整所使用的處理器時(shí)間使用比旁钧。
4.linux系統(tǒng)是搶占式的吸重，是否要將一個(gè)進(jìn)程立刻投入運(yùn)行（也就是搶占當(dāng)前進(jìn)程）互拾，是完全由進(jìn)程的優(yōu)先級(jí)和是否有時(shí)間片來決定。
5.CFS調(diào)度器：搶占時(shí)機(jī)取決于新的可執(zhí)行程序消耗了多少處理器使用比嚎幸，如果消耗的使用比當(dāng)前進(jìn)程醒湛蟆：新程序立刻投入運(yùn)行，搶占當(dāng)前進(jìn)程嫉晶，否則推遲骑疆。
調(diào)度策略的活動(dòng)
1.文字編譯程序顯然是I/O消耗型的，因?yàn)樗蟛糠謺r(shí)間都在等待用戶的鍵盤輸入（無論用戶的輸入速度有多快替废，都不可能趕上處理的速度）用戶總是希望按下鍵系統(tǒng)就能馬上響應(yīng)箍铭。
2.視頻編碼程序是處理器消耗型的。
3.CFS總是會(huì)毫不猶豫地讓文本編輯器在需要時(shí)被投入運(yùn)行椎镣，而讓視頻處理程序只能在剩下的時(shí)刻運(yùn)行诈火。
linux調(diào)度算法
調(diào)度器類
- linux調(diào)度器是以模塊方式提供，目的是允許不同類型的進(jìn)程可以有針對(duì)性地選擇調(diào)度算法衣陶。這種模塊化結(jié)構(gòu)被稱為調(diào)度器類柄瑰，它允許多種不同的可動(dòng)態(tài)添加的調(diào)度算法并存，調(diào)度屬于自己范疇的進(jìn)程剪况。
2.基礎(chǔ)的調(diào)度器代碼定義在kernel/sched.c文件中
3.每個(gè)調(diào)度器有一個(gè)優(yōu)先級(jí)教沾，會(huì)按照優(yōu)先級(jí)順序遍歷調(diào)度類，選擇優(yōu)先級(jí)最高的調(diào)度器類译断。
4.完全公平調(diào)度CFS是針對(duì)一個(gè)普通進(jìn)程的調(diào)度類授翻。
操作系統(tǒng)的常見的進(jìn)程調(diào)度算法
1.先來先服務(wù)：在所有調(diào)度算法中，最簡單的是非搶占式的FCFS算法
在所有的調(diào)度算法中孙咪，最簡單的是非搶占式的FCS算法堪唐。
算法原理：進(jìn)程按照他們請(qǐng)求CPU的順序使用CPU,就像你買東西去排隊(duì)，誰第一個(gè)排翎蹈，誰就先被執(zhí)行淮菠，在它執(zhí)行的過程中，不會(huì)中斷它荤堪。當(dāng)其他人也想進(jìn)入內(nèi)存被執(zhí)行合陵，就要排隊(duì)等著，如果在執(zhí)行過程中出現(xiàn)一些事澄阳，他現(xiàn)在不想排隊(duì)了拥知，下一個(gè)排隊(duì)的就補(bǔ)上。此時(shí)如果他又想排隊(duì)了碎赢，只能站到隊(duì)列尾去低剔。
算法優(yōu)點(diǎn)：易于理解且簡單，只需要一個(gè)隊(duì)列（FIFO），且相當(dāng)公平襟齿。
算法缺點(diǎn)：比較有利于長進(jìn)程姻锁，而不利于短進(jìn)程，有利于CPU繁忙的進(jìn)程猜欺，而不利于I/O繁忙的進(jìn)程屋摔。
2.最短作業(yè)優(yōu)先
短作業(yè)優(yōu)先又稱為“短進(jìn)程優(yōu)先”SPN; 這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間替梨。
算法原理：對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的進(jìn)程優(yōu)先分派處理機(jī)钓试。通常后來的短進(jìn)程不搶占正在執(zhí)行的進(jìn)程。
算法優(yōu)點(diǎn)：相比FCFS算法副瀑，該算法可改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間弓熏，縮短進(jìn)程的等待時(shí)間，提高系統(tǒng)的吞吐量糠睡。
算法缺點(diǎn)：對(duì)長進(jìn)程非常不利挽鞠，可能長時(shí)間得不到執(zhí)行，且未能依據(jù)進(jìn)程的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)狈孔，以及難以準(zhǔn)確估計(jì)進(jìn)程的執(zhí)行時(shí)間信认，從而影響調(diào)度性能。
3.時(shí)間片輪轉(zhuǎn)(RR)調(diào)度算法
RR調(diào)度算法與FCFS調(diào)度算法在選擇進(jìn)程上類似均抽，但在調(diào)度的時(shí)機(jī)選擇上不同嫁赏。RR調(diào)度算法定義了一個(gè)時(shí)間單元，稱為時(shí)間片油挥。一個(gè)時(shí)間片通常在1~100ms之間潦蝇。當(dāng)正在運(yùn)行的進(jìn)程用完時(shí)間片后，即使此進(jìn)程還要運(yùn)行深寥，操作系統(tǒng)也不讓它繼續(xù)運(yùn)行攘乒，而是從就緒隊(duì)列依次選擇下一個(gè)處于就緒態(tài)的進(jìn)程執(zhí)行，而被剝奪CPU使用的進(jìn)程返回到就緒隊(duì)列的末尾惋鹅，等待再次被調(diào)度则酝。時(shí)間片的大小可以調(diào)整，如果時(shí)間片大到讓一個(gè)進(jìn)程足以完成其全部工作闰集，這種算法就退化為FCFS調(diào)度算法沽讹；若時(shí)間片設(shè)置得很小，那么處理及在進(jìn)程之間上下文切換工作過于頻繁返十，使得真正用于用戶程序的時(shí)間減小妥泉。時(shí)間片可以靜態(tài)設(shè)置好椭微，也可以根據(jù)系統(tǒng)當(dāng)前負(fù)載狀況和運(yùn)行情況動(dòng)態(tài)調(diào)整洞坑，時(shí)間大小的動(dòng)態(tài)調(diào)整需要考慮就緒態(tài)進(jìn)程個(gè)數(shù)、進(jìn)程上下文開銷蝇率、系統(tǒng)吞吐量迟杂、系統(tǒng)響應(yīng)時(shí)間等多方面因素刽沾。
**4.高響應(yīng)比優(yōu)先調(diào)度算法(HRRF)：HRRF調(diào)度算法是介于先來先服務(wù)算法與最短進(jìn)程優(yōu)先算法之間的一種折中算法。先來先服務(wù)算法只考慮進(jìn)程的等待時(shí)間而忽視了進(jìn)程的執(zhí)行時(shí)間排拷，而最短進(jìn)程優(yōu)先調(diào)度算法只考慮用戶估計(jì)的進(jìn)程的執(zhí)行時(shí)間而忽視了就緒進(jìn)程的等待時(shí)間侧漓。HRRF調(diào)度算法二者兼顧，既考慮進(jìn)程的執(zhí)時(shí)間监氢，為此定義了響應(yīng)比(Rp)這個(gè)指標(biāo)：
Rp = (等待時(shí)間+預(yù)計(jì)執(zhí)行時(shí)間)/執(zhí)行時(shí)間=響應(yīng)時(shí)間/執(zhí)行時(shí)間
上述表達(dá)式假設(shè)等待時(shí)間與預(yù)計(jì)執(zhí)行時(shí)間智和等于響應(yīng)時(shí)間布蔗。HRRF調(diào)度算法將選擇Rp最大值的進(jìn)程執(zhí)行，這樣既照顧了短進(jìn)程又不使長進(jìn)程的等待時(shí)間過長浪腐，改進(jìn)了調(diào)度性能纵揍。但HRRF調(diào)度算法需要每次計(jì)算各個(gè)進(jìn)程的響應(yīng)比Rp，這會(huì)帶來較大的時(shí)間開銷（特別是在就緒進(jìn)程個(gè)數(shù)比較多的情況下）议街。
5.多級(jí)反饋隊(duì)列調(diào)度算法
在采用多級(jí)反饋隊(duì)列調(diào)度算法的執(zhí)行邏輯流程如下：
設(shè)置多個(gè)就緒隊(duì)列泽谨，并未各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)較高特漩，第二隊(duì)次之吧雹，其余隊(duì)列優(yōu)先級(jí)依次降低。僅當(dāng)?shù)?~i-1個(gè)隊(duì)列為空時(shí)涂身，操作系統(tǒng)調(diào)度器才會(huì)調(diào)度第i個(gè)隊(duì)列中的進(jìn)程運(yùn)行雄卷。賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同。在優(yōu)先級(jí)越高的隊(duì)列中蛤售，每個(gè)進(jìn)程的執(zhí)行時(shí)間片就越小或越大龙亲。
當(dāng)一個(gè)就緒進(jìn)程需要鏈入就緒隊(duì)列時(shí)，操作系統(tǒng)首先將它放入第一隊(duì)列的末尾悍抑，按FCFS的原則排隊(duì)等待調(diào)度鳄炉。若輪到該進(jìn)程執(zhí)行且在一個(gè)時(shí)間片結(jié)束尚未完成，則操作系統(tǒng)調(diào)度器便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾搜骡，再童言按先來先服務(wù)原則等待調(diào)度執(zhí)行拂盯。如此下去，當(dāng)一個(gè)長進(jìn)程從第一個(gè)隊(duì)列降到最后一個(gè)隊(duì)列后记靡，在最后一個(gè)隊(duì)列中谈竿，可使用FCFS或RR調(diào)度算法來運(yùn)行處于隊(duì)列中的進(jìn)程。
如果處理機(jī)正在第i(i>1)隊(duì)列中為某進(jìn)程服務(wù)時(shí)摸吠，又有新進(jìn)程進(jìn)入第k(k<i)的隊(duì)列空凸，則新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在執(zhí)行進(jìn)程放回第i隊(duì)列末尾寸痢，重新將處理機(jī)分配給處于第k隊(duì)列的新進(jìn)程呀洲。
從MLFQ調(diào)度算法可以看出長進(jìn)程無法長期占用處理機(jī)，且系統(tǒng)的響應(yīng)時(shí)間會(huì)縮短，吞吐量也不錯(cuò)(前提是沒有頻繁的短進(jìn)程)道逗。所以MLFQ調(diào)度算法是一種合適不同類型應(yīng)用特征的綜合進(jìn)程調(diào)度算法兵罢。
6.最高優(yōu)先級(jí)優(yōu)先調(diào)度算法
進(jìn)程的優(yōu)先級(jí)用于表示進(jìn)程的重要性及運(yùn)行的優(yōu)先性。一個(gè)進(jìn)程的優(yōu)先級(jí)可分為兩種：靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)滓窍。
靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的卖词。一旦確定后，在整個(gè)進(jìn)程運(yùn)行期間不再改變吏夯。靜態(tài)優(yōu)先級(jí)一般由用戶依據(jù)包括進(jìn)程的類型此蜈、進(jìn)程所使用的資源、進(jìn)程的估計(jì)運(yùn)行時(shí)間等因素來設(shè)置噪生。一般而言舶替，若進(jìn)程需要的資源越多、估計(jì)運(yùn)行的時(shí)間越長杠园，則進(jìn)程的優(yōu)先級(jí)越低顾瞪；反之，對(duì)于I/O bounded的進(jìn)程可以把優(yōu)先級(jí)設(shè)置得高抛蚁。
動(dòng)態(tài)優(yōu)先級(jí)是指在進(jìn)程運(yùn)行過程中陈醒，根據(jù)進(jìn)程執(zhí)行情況的變化來調(diào)整優(yōu)先級(jí)。動(dòng)態(tài)優(yōu)先級(jí)一般根據(jù)進(jìn)程占有CPU時(shí)間的長短瞧甩、進(jìn)程等待CPU時(shí)間的長短等因素確定钉跷。占有處理機(jī)的時(shí)間越長，則優(yōu)先級(jí)越低肚逸，等待時(shí)間越長爷辙，優(yōu)先級(jí)越高。那么進(jìn)程調(diào)度器將根據(jù)靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)的總和現(xiàn)在優(yōu)先級(jí)最高的就緒進(jìn)程執(zhí)行朦促。
