跳至內容

調度 (計算機)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

調度(英語:Scheduling)在計算機中是分配工作所需資源的方法。資源可以指虛擬的計算資源,如線程進程數據流;也可以指硬件資源,如處理器、網絡連接或擴展卡

進行調度工作的程序叫做調度器。調度器通常的實現使得所有計算資源都處於忙碌狀態(在負載均衡中),允許多位用戶有效地同時共享系統資源,或達到指定的服務質量。調度是計算自身的基礎,同時也是編程語言計算模型固有的部分。調度器使得在單處理器上通過多任務處理,從而讓執行多個進程成為可能。

調度器可能會針對不同的目標設計,例如:吞吐率最大化、響應時間最小化、最低延遲[1]、或最大化公平。在實踐中,這些目標通常是互相衝突的,因此,調度器會實現一個權衡利弊的折中方案,而側重點則可能是前文提到的任何一種,這取決於用戶的需求和目的。

在實時環境,例如工業上用於自動控制(如機器人)的嵌入式系統,調度器必須保證進程的調度不能超過最後期限 —— 這是保持系統穩定運行的關鍵因素。調度也可能是通過一個管理性的後端進行,而任務是通過網絡發配到若干遠程設備上的。

操作系統調度器的種類

[編輯]

調度器是操作系統的一個模塊,它能夠選擇將被系統處理的下一個任務,或執行的下一個進程。操作系統可能會提供三種不同類型的調度器:長期調度器、中期調度器和短期調度器。這些名字表明了任務被執行的頻率。

進程調度器

[編輯]

進程調度器是操作系統的一部分,決定了何時運行什麼進程。它通常能夠暫停一個運行中的進程,將它放回到運行隊列當中,並運行一個新進程,我們把這樣的調度器叫做搶占調度器。否則,它就是協同調度器。

長期調度器

[編輯]

長期調度器,決定了任務或進程是否會被就緒隊列(內存中)所接納。當一個運行程序的嘗試被做出後,長期調度器或允許,或是延遲將它作為當前執行的一個進程。因此,這種調度器掌控着能在系統上運行的進程。調度器同時還決定並發的程度:同時執行程序的多少,在I/O密集型和CPU密集型進程之前做出劃分。

通常,大多數進程可以分為I/O密集型[2]和CPU密集型。I/O密集型程序將大多數時間都花在了I/O操作而不是運算上,而CPU密集型程序正好相反,將大多數時間花在了運算上,而很少產生I/O操作。選出一個I/O密集型和CPU密集型程序的良好組合,對於長期調度器是非常重要的。否則,假如所有的程序都是CPU密集型的,那麼I/O隊列將會幾乎永遠都是空的,這樣就會導致一些設備從來沒被人用過,系統資源分配就是不均衡的。顯然,性能極佳的系統必然是CPU密集型和I/O密集型程序的組合。在現代操作系統中,這被用來保證實時進程能獲得足夠的CPU時間來完成任務。[3]

長期調度對大型系統,例如批處理系統、計算機集群、超級計算機和渲染場來說同樣重要。例如,在並發系統中,為了避免交互的多個進程,把時間都花在等待對方而產生阻塞,通常是需要進行協同調度的。在這種情況下,處理操作系統底層的調度器之外,還需要符合要求的額外調度程序來實現必要的功能。

中期調度器

[編輯]

中期調度器臨時將進程從內存中去除,放入第二儲存設備(如硬盤)中,或亦而反之。這通常被稱為「換出」和「換入」(同時也被錯誤叫做「分頁入」和「分頁出」)。中期調度器可能會將那些一直不活躍的進程,優先級低的進程,頻繁產生頁錯誤的進程,或者占用大量內存的進程放入交換區,為其它程序釋放內存。當系統內存充足時,或者程序不再處於阻塞狀態時,調度器又會將剛剛被放入交換區中的進程重新放入內存中。

短期調度器

[編輯]

短期調度器(也就是CPU調度器)決定了在一個時鐘中斷、I/O中斷、系統調用其它種類的信號之後,應該執行(分配CPU)給哪些內存中的進程。可見,短期調度器作出決定的頻率比長期或中期調度器更加頻繁 —— 每隔一段非常短的固定時間,調度器就將做出一次決定。這種調度器可以是搶占式的,能夠強行把一個在CPU運行中的程序中斷,然後分配給其它進程;也可以是非搶占式的,這類調度器無法強行把進程從CPU上中斷。

搶占式調度器的功能需要一個運行在內核態,能被中斷處理程序捕獲的可編程定時器才能實現。

調度規則

[編輯]

調度規則就是在同時占用資源的多方之間進行資源分配的算法。在路由器操作系統硬盤打印機,大多數嵌入式系統等設備中,都能看到調度規則的應用。

調度算法的主要目標,是使資源飢餓最小化,並保證使用資源多方的公平性。調度器需要處理在大量請求下如何分配資源的難題。調度算法種類很多,在這一章,將會介紹幾種常見算法。

封包交換的計算機網絡和其它統計多路復用領域,需要一個合適的調度算法而不是一個先到先得的數據包隊列。

參考來源

[編輯]
  1. ^ Remzi H. Arpaci-Dusseau; Andrea C. Arpaci-Dusseau. Chapter 7: Scheduling: Introduction, Section 7.6: A New Metric: Response Time. Operating Systems: Three Easy Pieces (PDF). January 4, 2015: 6 [February 2, 2015]. (原始內容 (PDF)存檔於2018-10-13). 
  2. ^ Priya Ranjan. I/O-Bound. [2014-08-09]. (原始內容存檔於2014-09-28). 
  3. ^ Abraham Silberschatz, Peter Baer Galvin and Greg Gagne. Operating System Concepts 9. John Wiley & Sons,Inc. 2013. ISBN 978-1-118-06333-0.