當計算機系統是多道程序設計系統時，常常會出現多個進程或線程競爭CPU的情況。如果有大于處理器數的進程(線程)處于就緒態時，就必須要選擇下一個要執行的進程(線程)。在操作系統，用于選擇接下來要執行的進程的程序稱之為調度程序(Scheduler)，調度程序相應的算法稱之為調度算法(Schedule Algorithm)。雖然進程調度和線程調度有些許不同，但是許多適用于進程調度的處理方法大多也適用于線程的調度。

• 進程的行為

幾乎所有的進程的I/O請求和計算都是交替發生的，典型的，CPU不間斷的執行一段時間，當CPU發現需要執行I/O操作，發出系統調用來完成I/O請求，當/O請求執行完成后CPU繼續計算，直到進程需要執行其他的I/O操作或者執行完成。某些進程花費大量的時間在計算上(使用CPU)，這類型進程稱之為CPU密集型進程(compute-bound)，典型的CPU密集型進程具有較長時間的CPU集中使用和較小頻度的I/O操作。相反，某些進程花費大量時間用于處理I/O請求，這類進程稱之為I/O密集型進程(I/O-bound)，典型的I/O密集型進程具有較短的CPU集中使用和頻度較大的I/O操作。隨著CPU的速度的不斷提升，進程更加偏向于I/O密集型，因為因此如果需要運行/O密集型進程，那么應當勁量讓/O密集型進程得到執行，以便發出磁盤請求并保持磁盤忙碌。因為I/O操作遠遠慢于CPU的速度，對于/O密集型進程的調度就更加重要了。

• 何時調度

有關調度的一個關鍵問題是在何時進行調度？考慮如下的情形：

在進程創建子進程后，需要決定調用子進程還是父進程，因為子進程和父進程都處于就緒態，因此可以任意決定選擇那個進程執行。

當一個進程執行結束退出時，調度程序(Scheduler)需要從就緒隊列中選擇一個進程執行，如果就緒隊列沒有就緒進程，那么應該調用操作系統提供的空閑進程。

當一個進程因為I/O、信號量或其他原因陷入阻塞時，調度程序需要從就緒隊列中選擇一個進程執行。

在一個I/O中斷發生時，必須做出調度決策，如果終中斷來自I/O設備，而設備完成中斷工作后，被阻塞的進程此時處于就緒狀態，那么此時是繼續執行正在執行的進程還是調度完成中斷的進程將由調度程序決定。或者讓剛剛中斷發生的的進程執行，或者讓某個其他進程執行。

根據如何處理時鐘中斷，可以把調度算法分為兩類。非搶占式調度算法是挑選一個進程讓其執行，直到該進程阻塞(I/O請求或其它原因)或者主動釋放CPU，即使該進程執行了若干小時也不會強制掛起。這樣做的結果是在時鐘中斷發生時不會進行調度，在處理完時鐘中斷后，如果沒有優先級更高的進程，該進程會繼續執行。搶占式調度算法是挑選一個進程，讓進程執行一個給定的最大運行時間(時間片)，如果在給定的最大執行時間后進程仍然在執行，那么會強制掛起該進程，調度程序選擇另一個進程執行。

• 調度算法分類

調度算法的分類主要是根據其執行的環境，不同的執行環境使用不同的調度算法。大致可以劃分出三種環境：批處理、交互式、實時。

• 調度算法的目標

前面我們知道，對于不同的環境使用不同的調度算法，因為在不同的環境所追求的性能指標也不盡相同，有些是所有環境都適合，有些則適合于特定的環境。

所有系統公平——保證每個進程由公平的CPU份額策略強制執行——保證指定的策略能夠被執行平衡——保持系統所有的部分都是忙碌的 批處理系統吞吐量——每小時完成最大的作業數周轉時間——任務從被提交到執行完成的最小時間CPU利用率——CPU的使用情況 交互式系統響應時間——快速響應時間均衡性——滿足用戶的請求 實時系統滿足截止時間——避免丟失數據可預測性——在多媒體系統中避免品質降低

對于所有情形，公平性十分重要，進程應該得到公平的CPU的份額，在理論上能夠達到公平。再者，盡量保證系統的各個部分都保持忙碌，保證CPU和I/O設備都在處理任務，這樣比CPU空轉或I/O設備空閑會更加高效。因此調度程序在把進程調入到內存時，保證內存中既有CPU密集型進程和I/O密集型進程是較好的想法。好于內存中先全部都是CPU密集型進程然后在全是I/O密集型進程。如果是后一種策略，在CPU密集型進程執行時會競爭CPU并且磁盤空閑，而后面執行I/O密集型進程時會競爭磁盤，而CPU卻空轉。因此保證內存中的進程既包含CPU密集型又包含I/O密集型能夠讓系統的性能好一些。

• 批處理系統中的調度算法

先來先服務：在所有調度算法中，最簡單的莫過于非搶占式的先來先服務調度算法(first-come first-served)，使用該調度算法時，進程按照請求CPU的時間的先后來使用CPU。基本上會有一個就緒進程的隊列，每個請求CPU的進程會被放入到就緒隊列中，然后CPU從隊列頭部選擇進程執行，新來的進程會被放入到隊列尾部。當正在執行的進程陷入阻塞時，CPU會從就緒隊列首部中選擇一個進程執行，當被阻塞的進程變為就緒態時，它就行剛剛請求CPU的進程一樣被放入到隊列尾部。該算法的優點在于便于理解并且容易在程序中應用。 缺點是對長作業比較有利，而不利于短作業，因為短作業執行的時間很短，但卻要等待很多長時間才能執行。當內存中的進程大部分為I/O密集型進程時，CPU在這些進程間交替時會導致很多進程競爭I/O資源而導致CPU處于空閑。

最短作業優先：每個進程都有使用CPU的時間，每次調度程序選擇進程時選擇使用CPU時間最短的進程執行，這種非搶占式調度算法稱之為最短作業優先(shortest job first)。最短作業優先算法能夠提升高系統的吞吐量，并且使得平均等待時間最小。有必要支持，只有在所有進程同時運行的情形，最短作業優先才是最有的。

最短剩余時間優先：最短作業優先算法的搶占式版本是最短剩余時間優先(shortest remaining time first)算法。調度程序總是挑選剩余運行時間最短的進程進行執行，因此每個進程的運行時間要可知。當有新進程請求CPU時，會比較正在執行的程序的剩余執行時間和新請求的進程的執行時間，如果新請求的進程的執行時間更短就會暫停正在執行的進程轉而執行最新請求的進程。否則新請求的進程放入到就緒隊列，CPU繼續執行當前進程。對于最短作業優先算法和最短剩余時間算法最大的問題在于需要知道每個進程運行的時間，對于這點往往是很難做到的。

• 交互式系統中的調度

輪轉算法：一種最古老、最簡單、最公平且使用最廣泛的算法是輪轉調度(round robin)。基本思想：為每個進程分配一個執行的時間段，成為時間片(quantum)，允許進程在時間片內使用CPU，如果在時間片結束時進程依然在執行，那么調度程序暫停正在執行的進程并分配CPU給其他的進程。如果正在執行的進程在時間片結束前終止或阻塞，那么調度程序立即調度進程執行CPU而不是等到時間片結束再調度。該調度算法中有趣的是時間片長度的選擇：從一個進程切換的另一個進程是需要時間進行事務管理的——保存前一個進程的寄存器，堆棧信息等信息并且裝入新進程的堆棧信息、寄存器信息等，這種方式稱之為進程切換(process switch)或者上下文切換(context switch)。如果時間片設置的過小，那么會有很多時間會用于進程的上下文切換的開銷上，如果時間片設置的比較大，那么在請求量很大的場景(例如Web服務器)，那么到來的請求要等很長的時間才有機會被調度。因此時間片過長或者過短都不合適，通常將時間片長度設置為20ms-50ms是比較合理的折中。

優先級調度：輪轉算法做出了一個假設那就是默認所有的進程的優先級一樣，但是現實的情況是有些進程的優先級高一些，有些不那么重要的進程的優先級可能相對低一些。因此在優先級調度算法中每個進程給予一個優先級，運行優先級最高的進程先執行。為了方式優先級高的進程一直運行，可以在時鐘滴答降低進程的優先級使得優先級相對低的進程也有機會執行。另一種方法是為進程賦予一個運行執行的最大時間片(時間片長度可能因進程的優先級的不同而不同)，當使用完時間片，優先級次高的進程也能被執行。優先級也可以由系統動態分配，例如有些I/O密集型進程大多數時間在等待I/O結束，當這類型的進程請求執行時應該勁量滿足，以便啟動下一次I/O請求。系統應該能適當的調整進程的優先級避免出現優先級較低的進程出現饑餓現象。

多級隊列：多級隊列(Multilevel Queue)調度算法是將就緒隊列分成介個單獨的隊列，一般根據進程的特性如占用內存的大小，進程的優先級，進程類型等，每個隊列都有自己的調度算法。

最短進程優先：對于交互式系統，用戶可能比較在意的指標是響應時間，因此最短進程優先常常伴隨著最短的響應時間，用戶體驗也越好。這里唯一的問題是如何從當前可執行的進程中找出最短的那一個進程？ 一種方法是根據進程過去的行為進行推測，并執行運行時間最短的那個。假設終端上每個命令的執行時間為T0，現在假設測量到下一次運行時間為T1，那么使用加權和來改進預計時間，即aT0+(1-a)T1，通過選擇a的值，可以決定盡快忘掉老的執行時機還是保留。當a = 1/2時，可得到如下的序列： T0，To/2 + T1/2，To/4 + T1/4 + T2/2 .........

• 線程調度

當進程擁有多個線程時，就存在兩個層次的并行：進程和線程，這兩種調度存在本質的區別，并且還取決于線程是用戶級線程還是內核級線程還是兩者的混合。首先考慮用戶級線程，操作系統不知道線程的存在，因此操作系統還是和以前一樣調度進程，而線程調度程序在進程內部，進程內的調度程序決定如何調度線程。因為多個線程不存在時鐘中斷，因此使用時間片是可行的方案。當進程的運行時間介紹內核就會調度其他進程。也就是說當調度程序分配給進程一定的執行時間，進程內的多個線程如何使用這段執行時間內核不關心，內核關系的是分配給進程的執行時間(時間片長度)。對于內核級線程，內核選擇一個特定的線程執行，它不用考慮該線程屬于那個進程，對于被選擇的進程賦予一個時間片，而且超過了時間片，就會強制掛起該線程。用戶級線程和內核級線程之間的差別在于性能，用戶級線程的線程切換需要更少的機器指令，甚至內核都不知道進行了線程切換，因為這是由進程內部的調度程序決定的，因此用戶級線程可以使用轉為應用程序定制的線程調度程序。另一方面，使用內核級線程時，一個線程被阻塞時不會出現像用戶級線程那樣掛起相應的進程的情況。

總結

以上是生活随笔為你收集整理的批处理结束某个进程_进程调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。