進(jìn)程調(diào)度的任務(wù)

1. 保存處理機(jī)的現(xiàn)場(chǎng)信息勋陪。括當(dāng)前進(jìn)程的現(xiàn)場(chǎng)信息，如程序計(jì)數(shù)器硫兰，多個(gè)通用寄存器中的內(nèi)容等诅愚。
2. 按照某種算法選取進(jìn)程。調(diào)度程序按照某種算法從就緒隊(duì)列中選取一個(gè)進(jìn)程劫映，將其狀態(tài)改為運(yùn)行狀態(tài)违孝，并準(zhǔn)備把處理機(jī)分配給它刹前。
3. 把處理器分配給進(jìn)程。由分派程序把處理器分配給該進(jìn)程雌桑，此時(shí)需要將選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場(chǎng)的信息裝入處理器相應(yīng)的各個(gè)寄存器中喇喉，把處理器的控制權(quán)交給該進(jìn)程，讓它從上次的斷點(diǎn)處恢復(fù)運(yùn)行

進(jìn)程調(diào)度的機(jī)制

進(jìn)程調(diào)度機(jī)制

為了實(shí)現(xiàn)進(jìn)程調(diào)度校坑，在進(jìn)程調(diào)度機(jī)制中拣技，應(yīng)具有如下三個(gè)基本部分：

1. 排隊(duì)器
   為了提高進(jìn)程調(diào)度的效率，應(yīng)實(shí)現(xiàn)將系統(tǒng)中所有的就緒進(jìn)程按照一定的策略排成一個(gè)或多個(gè)隊(duì)列耍目，以便調(diào)度程序能盡快地找到它膏斤。以后每當(dāng)有一個(gè)進(jìn)程轉(zhuǎn)變成就緒狀態(tài)時(shí)，排隊(duì)器便將它插入到就緒隊(duì)列邪驮。
2. 分派器
   分派器依據(jù)進(jìn)程調(diào)度程序所選定的程序莫辨，將其從就緒隊(duì)列中取出，然后進(jìn)行從分派器到新選出進(jìn)程間的上下文切換毅访，將處理機(jī)分配給新選出的進(jìn)程衔掸。
3. 上下文切換器
   • 在對(duì)處理機(jī)進(jìn)行上下文切換時(shí)，會(huì)發(fā)生兩步對(duì)上下文切換的操作：
     1. OS保存當(dāng)前進(jìn)程上下文俺抽，即把當(dāng)前進(jìn)程的處理機(jī)寄存器內(nèi)容保存到該進(jìn)程的進(jìn)程控制塊內(nèi)的相應(yīng)單元，再裝入分派程序的上下文较曼，以便分派程序的運(yùn)行
     2. 移出分派程序的上下文磷斧，而把新選進(jìn)程的CPU現(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)的寄存器中，以便新選進(jìn)程運(yùn)行

在進(jìn)行上下文切換時(shí)捷犹，需要執(zhí)行大量的load和store等操作指令弛饭，以保存寄存器的內(nèi)容

進(jìn)程調(diào)度方式

• 非搶占式

  • 機(jī)制：
    一旦把處理機(jī)分配給某個(gè)進(jìn)程后，就讓它一直運(yùn)行下去萍歉，絕不會(huì)因?yàn)闀r(shí)鐘中斷或其他原因去搶占當(dāng)前正在運(yùn)行的處理機(jī)侣颂，直到該進(jìn)程完成，或因?yàn)榘l(fā)生某事件而被阻塞時(shí)枪孩，才會(huì)把處理機(jī)分配給其它進(jìn)程

  • 引起調(diào)度的因素：
    1.進(jìn)程執(zhí)行完畢或因某事件而使其無(wú)法再繼續(xù)運(yùn)行
    2.正在執(zhí)行的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行
    3.在進(jìn)程通信或者同步過(guò)程中憔晒，執(zhí)行了某種原語(yǔ)操作，如BLOCK原語(yǔ)

  • 優(yōu)缺點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單蔑舞，系統(tǒng)開(kāi)銷(xiāo)小拒担，適用于大多數(shù)批處理系統(tǒng)，但它不能用于分時(shí)系統(tǒng)和大多數(shù)實(shí)時(shí)系統(tǒng)

• 搶占式

  • 機(jī)制：
    允許調(diào)度程序按照某種原則攻询，去暫停某個(gè)正在執(zhí)行的進(jìn)程从撼，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程
  • 原則：
    1.優(yōu)先權(quán)原則：允許優(yōu)先級(jí)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)
    2.短進(jìn)程優(yōu)先原則：允許新到的短進(jìn)程（新到達(dá)進(jìn)程比正在執(zhí)行進(jìn)程尚需運(yùn)行的時(shí)間明顯短）可以搶占當(dāng)前長(zhǎng)進(jìn)程的處理機(jī)
    3.時(shí)間片原則：各進(jìn)程按時(shí)間片輪轉(zhuǎn)運(yùn)行時(shí)，正在執(zhí)行的進(jìn)程一個(gè)時(shí)間片用完钧栖，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度

調(diào)度算法：

1. 輪轉(zhuǎn)調(diào)度算法（round robin, RR）：

   • 機(jī)制：
     根據(jù)FCFS策略低零，將所有就緒進(jìn)程排成一個(gè)就緒隊(duì)列婆翔，并設(shè)置每隔一段時(shí)間產(chǎn)生一次中斷，激活系統(tǒng)中的進(jìn)程調(diào)度程序掏婶，完成一次調(diào)度啃奴，將CPU分配給隊(duì)首進(jìn)程，令其執(zhí)行气堕。若在時(shí)間片用完之前纺腊，正在運(yùn)行的進(jìn)程便已完成，就立刻激活調(diào)度程序茎芭，將它從就緒隊(duì)列中刪除揖膜，再開(kāi)始下一個(gè)循環(huán)。若時(shí)間片用完梅桩，進(jìn)程尚未執(zhí)行完畢壹粟，則調(diào)度程序就將其送至隊(duì)列的末尾。
   • 關(guān)鍵：
     時(shí)間片的選人薨佟：若太小趁仙，意味著會(huì)頻繁地執(zhí)行進(jìn)程調(diào)度和進(jìn)程上下文切換，這無(wú)疑會(huì)增加系統(tǒng)開(kāi)銷(xiāo)垦页。若太長(zhǎng)雀费，極端情況下，每個(gè)進(jìn)程都在一個(gè)時(shí)間片內(nèi)執(zhí)行完成痊焊，則算法退化為FCFS算法盏袄，無(wú)法滿足短作業(yè)和交互式用戶(hù)需求

2. 優(yōu)先級(jí)調(diào)度算法：

   • 類(lèi)型：
     靜態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)確定，在進(jìn)程整個(gè)運(yùn)行期間保持不變
     動(dòng)態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)賦一個(gè)初始值薄啥，隨進(jìn)程推進(jìn)或等待時(shí)間增加而改變
   • 機(jī)制：
     把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程辕羽。若為非搶占式優(yōu)先級(jí)算法，一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程后垄惧，該進(jìn)程便一直執(zhí)行下去直至完成刁愿，或者因該進(jìn)程發(fā)生某事件而放棄處理機(jī)時(shí)，系統(tǒng)方可將處理機(jī)重新分配給另一優(yōu)先級(jí)最高的進(jìn)程到逊。若為搶占式優(yōu)先級(jí)算法铣口，在進(jìn)程執(zhí)行期間，只要來(lái)了一個(gè)優(yōu)先級(jí)更高的進(jìn)程觉壶，調(diào)度程序就將處理機(jī)分配給新到的優(yōu)先級(jí)最高的進(jìn)程枷踏。
   • 關(guān)鍵：
     優(yōu)先級(jí)的確定與維護(hù)

3. 多隊(duì)列調(diào)度算法：

   • 機(jī)制：
     該算法將系統(tǒng)中的就緒隊(duì)列從一個(gè)拆分為若干個(gè)，將不同類(lèi)型或性質(zhì)的進(jìn)程固定分配到不同的就緒隊(duì)列掰曾，不同的就緒隊(duì)列采用不同的調(diào)度算法旭蠕，一個(gè)就緒隊(duì)列中的進(jìn)程可以設(shè)置不同的優(yōu)先級(jí)，不同的就緒隊(duì)列本身也可以設(shè)置不同的優(yōu)先級(jí)。
   • 優(yōu)點(diǎn)：
     彌補(bǔ)了低級(jí)調(diào)度算法固定掏熬，單一佑稠，無(wú)法滿足系統(tǒng)中不同用戶(hù)對(duì)進(jìn)程調(diào)度策略的不同要求的缺點(diǎn)。同時(shí)在多處理機(jī)系統(tǒng)中旗芬，該算法由于安排了多個(gè)就緒隊(duì)列舌胶，因此，很方便為每個(gè)處理機(jī)設(shè)置一個(gè)單獨(dú)的就緒隊(duì)列疮丛，這樣幔嫂，不僅對(duì)每個(gè)處理機(jī)的調(diào)度可以實(shí)施不同的調(diào)度策略，對(duì)于一個(gè)含有多個(gè)線程的進(jìn)程而言誊薄，可以根據(jù)要求將其所有線程分配在一個(gè)就緒隊(duì)列履恩，全部在一個(gè)處理機(jī)上執(zhí)行。再者呢蔫，對(duì)于一組需要相互合作的進(jìn)程或線程而言切心，也可以將它們分配在一組處理機(jī)所對(duì)應(yīng)的多個(gè)就緒隊(duì)列，使得他們能同時(shí)獲得處理機(jī)并行執(zhí)行片吊。

4. 多級(jí)反饋隊(duì)列（multileved feedback queue）調(diào)度算法：

   • 機(jī)制：
     1. 設(shè)置多個(gè)就緒隊(duì)列
        在系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列绽昏，并為每個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第一個(gè)隊(duì)列的優(yōu)先級(jí)最高俏脊，第二個(gè)次之全谤，其余隊(duì)列的優(yōu)先級(jí)逐個(gè)降低，該算法為不同隊(duì)列中進(jìn)程所賦予的執(zhí)行時(shí)間片的大小也各不相同爷贫，在優(yōu)先級(jí)越高的隊(duì)列中认然，其時(shí)間片就越小。如第二個(gè)隊(duì)列時(shí)間片比第一個(gè)的長(zhǎng)一倍......第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)的時(shí)間片長(zhǎng)一倍沸久。以下為示意圖：
        
        多級(jí)反饋隊(duì)列調(diào)度算法
     2. 每個(gè)隊(duì)列都采用FCFS算法
        每當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾余蟹，按FCFS原則等待調(diào)度卷胯。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如果它能在該時(shí)間片內(nèi)完成威酒，便可撤離系統(tǒng)窑睁，否則，即它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成葵孤，調(diào)度程序?qū)⑺D(zhuǎn)入至第二隊(duì)列的末尾等待調(diào)度担钮；依此類(lèi)推，當(dāng)進(jìn)程被將至第n隊(duì)列后尤仍，則在第n隊(duì)列采用RR方式運(yùn)行
     3. 按隊(duì)列優(yōu)先級(jí)調(diào)度
        調(diào)度程序首先調(diào)度最高優(yōu)先級(jí)隊(duì)列中的諸程序運(yùn)行箫津，且僅當(dāng)?shù)?~(i-1)所有隊(duì)列均為空時(shí)，采取調(diào)度第i隊(duì)列中的程序運(yùn)行，若處理機(jī)正在處理的第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)又有新進(jìn)程進(jìn)入任一優(yōu)先級(jí)較高的隊(duì)列苏遥，此時(shí)必須把正在運(yùn)行的進(jìn)程放回第i隊(duì)列的末尾饼拍，而把處理機(jī)分配給新到的高優(yōu)先級(jí)進(jìn)程

如有敘述錯(cuò)誤，歡迎指正~