進程調(diào)度的任務

1. 保存處理機的現(xiàn)場信息。括當前進程的現(xiàn)場信息，如程序計數(shù)器，多個通用寄存器中的內(nèi)容等。
2. 按照某種算法選取進程。調(diào)度程序按照某種算法從就緒隊列中選取一個進程，將其狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。
3. 把處理器分配給進程。由分派程序把處理器分配給該進程，此時需要將選中進程的進程控制塊內(nèi)有關處理機現(xiàn)場的信息裝入處理器相應的各個寄存器中，把處理器的控制權交給該進程，讓它從上次的斷點處恢復運行

進程調(diào)度的機制

進程調(diào)度機制

為了實現(xiàn)進程調(diào)度，在進程調(diào)度機制中，應具有如下三個基本部分：

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

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

進程調(diào)度方式

• 非搶占式

  • 機制：
    一旦把處理機分配給某個進程后，就讓它一直運行下去，絕不會因為時鐘中斷或其他原因去搶占當前正在運行的處理機，直到該進程完成，或因為發(fā)生某事件而被阻塞時，才會把處理機分配給其它進程

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

  • 優(yōu)缺點：實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)，但它不能用于分時系統(tǒng)和大多數(shù)實時系統(tǒng)

• 搶占式

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

調(diào)度算法：

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

   • 機制：
     根據(jù)FCFS策略，將所有就緒進程排成一個就緒隊列，并設置每隔一段時間產(chǎn)生一次中斷，激活系統(tǒng)中的進程調(diào)度程序，完成一次調(diào)度，將CPU分配給隊首進程，令其執(zhí)行。若在時間片用完之前，正在運行的進程便已完成，就立刻激活調(diào)度程序，將它從就緒隊列中刪除，再開始下一個循環(huán)。若時間片用完，進程尚未執(zhí)行完畢，則調(diào)度程序就將其送至隊列的末尾。
   • 關鍵：
     時間片的選?。喝籼?，意味著會頻繁地執(zhí)行進程調(diào)度和進程上下文切換，這無疑會增加系統(tǒng)開銷。若太長，極端情況下，每個進程都在一個時間片內(nèi)執(zhí)行完成，則算法退化為FCFS算法，無法滿足短作業(yè)和交互式用戶需求

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

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

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

   • 機制：
     該算法將系統(tǒng)中的就緒隊列從一個拆分為若干個，將不同類型或性質(zhì)的進程固定分配到不同的就緒隊列，不同的就緒隊列采用不同的調(diào)度算法，一個就緒隊列中的進程可以設置不同的優(yōu)先級，不同的就緒隊列本身也可以設置不同的優(yōu)先級。
   • 優(yōu)點：
     彌補了低級調(diào)度算法固定，單一，無法滿足系統(tǒng)中不同用戶對進程調(diào)度策略的不同要求的缺點。同時在多處理機系統(tǒng)中，該算法由于安排了多個就緒隊列，因此，很方便為每個處理機設置一個單獨的就緒隊列，這樣，不僅對每個處理機的調(diào)度可以實施不同的調(diào)度策略，對于一個含有多個線程的進程而言，可以根據(jù)要求將其所有線程分配在一個就緒隊列，全部在一個處理機上執(zhí)行。再者，對于一組需要相互合作的進程或線程而言，也可以將它們分配在一組處理機所對應的多個就緒隊列，使得他們能同時獲得處理機并行執(zhí)行。

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

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

如有敘述錯誤，歡迎指正~