下面文章摘抄自Java建設者公衆号，下圖是該公衆号的二維碼。
排程
當一個計算機是多道程式設計系統時，會頻繁的有很多程序或者線程來同時競争 CPU 時間片。當兩個或兩個以上的程序/線程處于就緒狀态時，就會發生這種情況。如果隻有一個 CPU 可用，那麼必須選擇接下來哪個程序/線程可以運作。作業系統中有一個叫做 排程程式(scheduler) 的角色存在，它就是做這件事兒的，該程式使用的算法叫做 排程算法(scheduling algorithm) 。
盡管有一些不同，但許多适用于程序排程的處理方法同樣也适用于線程排程。當核心管理線程的時候，排程通常會以線程級别發生，很少或者根本不會考慮線程屬于哪個程序。下面我們會首先專注于程序和線程的排程問題，然後會明确的介紹線程排程以及它産生的問題。
排程介紹
讓我們回到早期以錄音帶上的卡片作為輸入的批處理系統的時代，那時候的排程算法非常簡單：依次運作錄音帶上的每一個作業。對于多道程式設計系統，會複雜一些，因為通常會有多個使用者在等待服務。一些大型機仍然将 批處理和 分時服務結合使用，需要排程程式決定下一個運作的是一個批處理作業還是終端上的使用者。由于在這些機器中 CPU 是稀缺資源，是以好的排程程式可以在提高性能和使用者的滿意度方面取得很大的成果。
程序行為
幾乎所有的程序（磁盤或網絡）I/O 請求和計算都是交替運作的
如上圖所示，CPU 不停頓的運作一段時間，然後發出一個系統調用等待 I/O 讀寫檔案。完成系統調用後，CPU 又開始計算，直到它需要讀更多的資料或者寫入更多的資料為止。當一個程序等待外部裝置完成工作而被阻塞時，才是 I/O 活動。
上面 a 是 CPU 密集型程序；b 是 I/O 密集型程序程序，a 因為在計算的時間上花費時間更長，是以稱為計算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因為I/O 發生頻率比較快是以稱為 I/O 密集型(I/O-bound)。計算密集型程序有較長的 CPU 集中使用和較小頻度的 I/O 等待。I/O 密集型程序有較短的 CPU 使用時間和較頻繁的 I/O 等待。注意到上面兩種程序的區分關鍵在于 CPU 的時間占用而不是 I/O 的時間占用。I/O 密集型的原因是因為它們沒有在 I/O 之間花費更多的計算、而不是 I/O 請求時間特别長。無論資料到達後需要花費多少時間，它們都需要花費相同的時間來發出讀取磁盤塊的硬體請求。
值得注意的是，随着 CPU 的速度越來越快，更多的程序傾向于 I/O 密集型。這種情況出現的原因是 CPU 速度的提升要遠遠高于硬碟。這種情況導緻的結果是，未來對 I/O 密集型程序的排程處理似乎更為重要。這裡的基本思想是，如果需要運作 I/O 密集型程序，那麼就應該讓它盡快得到機會，以便發出磁盤請求并保持磁盤始終忙碌。
何時排程
第一個和排程有關的問題是何時進行排程決策。存在着需要排程處理的各種情形。首先，在建立一個新程序後，需要決定是運作父程序還是子程序。因為二者的程序都處于就緒态下，這是正常的排程決策，可以任意選擇，也就是說，排程程式可以任意的選擇子程序或父程序開始運作。
第二，在程序退出時需要作出排程決定。因為此程序不再運作（因為它将不再存在），是以必須從就緒程序中選擇其他程序運作。如果沒有程序處于就緒态，系統提供的空閑程序通常會運作
什麼是空閑程序
空閑程序(system-supplied idle process) 是 Microsoft 公司 windows 作業系統帶有的系統程序，該程序是在各個處理器上運作的單個線程，它唯一的任務是在系統沒有處理其他線程時占用處理器時間。System Idle Process 并不是一個真正的程序，它是核心虛拟出來的，多任務作業系統都存在。在沒有可用的程序時，系統處于空運作狀态，此時就是System Idle Process 在正在運作。你可以簡單的了解成，它代表的是 CPU 的空閑狀态，數值越大代表處理器越空閑，可以通過 Windows 任務管理器檢視 Windows 中的 CPU 使用率
第三種情況是，當程序阻塞在 I/O 、信号量或其他原因時，必須選擇另外一個程序來運作。有時，阻塞的原因會成為選擇程序運作的關鍵因素。例如，如果 A 是一個重要程序，并且它正在等待 B 退出關鍵區域，讓 B 退出關鍵區域進而使 A 得以運作。但是排程程式一般不會對這種情況進行考量。
第四點，當 I/O 中斷發生時，可以做出排程決策。如果中斷來自 I/O 裝置，而 I/O 裝置已經完成了其工作，那麼那些等待 I/O 的程序現在可以繼續運作。由排程程式來決定是否準備運作新的程序還是重新運作已經中斷的程序。
如果硬體時鐘以 50 或 60 Hz 或其他頻率提供周期性中斷，可以在每個時鐘中斷或第 k 個時鐘中斷處做出排程決策。根據如何處理時鐘中斷可以把排程算法可以分為兩類。非搶占式(nonpreemptive) 排程算法挑選一個程序，讓該程序運作直到被阻塞（阻塞在 I/O 上或等待另一個程序），或者直到該程序自動釋放 CPU。即使該程序運作了若幹個小時後，它也不會被強制挂起。這樣會在時鐘中斷發生時不會進行排程。在處理完時鐘中斷後，如果沒有更高優先級的程序等待，則被中斷的程序會繼續執行。
另外一種情況是 搶占式 排程算法，它會選擇一個程序，并使其在最大固定時間内運作。如果在時間間隔結束後仍在運作，這個程序會被挂起，排程程式會選擇其他程序來運作（前提是存在就緒程序）。進行搶占式排程需要在時間間隔結束時發生時鐘中斷，以将 CPU 的控制權交還給排程程式。如果沒有可用的時鐘，那麼非搶占式就是唯一的選擇。
排程算法的分類
毫無疑問，不同的環境下需要不同的排程算法。之是以出現這種情況，是因為不同的應用程式和不同的作業系統有不同的目标。也就是說，在不同的系統中，排程程式的優化也是不同的。這裡有必要劃分出三種環境
- 批處理(Batch)
- 互動式(Interactive)
- 實時(Real time)
批處理系統廣泛應用于商業領域，比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計算、索賠處理和其他周期性作業。在批處理系統中，一般會選擇使用非搶占式算法或者周期性比較長的搶占式算法。這種方法可以減少線程切換是以能夠提升性能。
在互動式使用者環境中，為了避免一個程序霸占 CPU 拒絕為其他程序服務，是以需要搶占式算法。即使沒有程序有意要一直運作下去，但是，由于某個程序出現錯誤也有可能無限期的排斥其他所有程序。為了避免這種情況，搶占式也是必須的。伺服器也屬于此類别，因為它們通常為多個（遠端）使用者提供服務，而這些使用者都非常着急。計算機使用者總是很忙。
在實時系統中，搶占有時是不需要的，因為程序知道自己可能運作不了很長時間，通常很快的做完自己的工作并阻塞。實時系統與互動式系統的差别是，實時系統隻運作那些用來推進現有應用的程式，而互動式系統是通用的，它可以運作任意的非協作甚至是有惡意的程式。
## 排程算法的目标
為了設計排程算法，有必要考慮一下什麼是好的排程算法。有一些目标取決于環境（批處理、互動式或者實時）但大部分是适用于所有情況的，下面是一些需要考量的因素，我們會在下面一起讨論。
在所有的情況中，公平是很重要的。對一個程序給予相較于其他等價的程序更多的 CPU 時間片對其他程序來說是不公平的。當然，不同類型的程序可以采用不同的處理方式。
與公平有關的是系統的強制執行，什麼意思呢？如果某公司的薪資發放系統計劃在本月的15号，那麼碰上了疫情大家生活都很拮據，此時老闆說要在14号晚上發放薪資，那麼排程程式必須強制使程序執行 14 号晚上發放薪資的政策。
另一個共同的目标是保持系統的所有部分盡可能的忙碌。如果 CPU 和所有的 I/O 裝置能夠一直運作，那麼相對于讓某些部件空轉而言，每秒鐘就可以完成更多的工作。例如，在批處理系統中，排程程式控制哪個作業調入記憶體運作。在記憶體中既有一些 CPU 密集型程序又有一些 I/O 密集型程序是一個比較好的想法，好于先調入和運作所有的 CPU 密集型作業，然後在它們完成之後再調入和運作所有 I/O 密集型作業的做法。使用後者這種方式會在 CPU 密集型程序啟動後，争奪 CPU ，而磁盤卻在空轉，而當 I/O 密集型程序啟動後，它們又要為磁盤而競争，CPU 卻又在空轉。。。。。。顯然，通過結合 I/O 密集型和 CPU 密集型，能夠使整個系統運作更流暢，效率更高。
批處理系統
通常有三個名額來衡量系統工作狀态：吞吐量、周轉時間和 CPU 使用率，吞吐量(throughout) 是系統每小時完成的作業數量。綜合考慮，每小時完成 50 個工作要比每小時完成 40 個工作好。周轉時間(Turnaround time) 是一種平均時間，它指的是從一個批處理送出開始直到作業完成時刻為止平均時間。該資料度量了使用者要得到輸出所需的平均等待時間。周轉時間越小越好。
CPU 使用率(CPU utilization) 通常作為批處理系統上的名額。即使如此， CPU 使用率也不是一個好的度量名額，真正有價值的衡量名額是系統每小時可以完成多少作業（吞吐量），以及完成作業需要多長時間（周轉時間）。把 CPU 使用率作為度量名額，就像是引擎每小時轉動了多少次來比較汽車的性能一樣。而且知道 CPU 的使用率什麼時候接近 100% 要比什麼什麼時候要求得到更多的計算能力要有用。
互動式系統
對于互動式系統，則有不同的名額。最重要的是盡量減少響應時間。這個時間說的是從執行指令開始到得到結果的時間。再有背景程序運作（例如，從網絡上讀取和儲存 E-mail 檔案）的個人計算機上，使用者請求啟動一個程式或打開一個檔案應該優先于背景的工作。能夠讓所有的互動式請求首先運作的就是一個好的服務。
一個相關的問題是 均衡性(proportionality)，使用者對做一件事情需要多長時間總是有一種固定（不過通常不正确）的看法。當認為一個請求很複雜需要較多時間時，使用者會認為很正常并且可以接受，但是一個很簡單的程式卻花費了很長的運作時間，使用者就會很惱怒。可以拿彩印和影印來舉出一個簡單的例子，彩印可能需要1分鐘的時間，但是使用者覺得複雜并且願意等待一分鐘，相反，影印很簡單隻需要 5 秒鐘，但是影印機花費 1 分鐘卻沒有完成影印操作，使用者就會很焦躁。
實時系統
實時系統則有着和互動式系統不同的考量因素，是以也就有不同的排程目标。實時系統的特點是必須滿足最後的截止時間。例如，如果計算機控制着以固定速率産生資料的裝置，未能按時運作的話可能會導緻資料丢失。是以，實時系統中最重要的需求是滿足所有（或大多數）時間期限。
在一些實事系統中，特别是涉及到多媒體的，可預測性很重要。偶爾不能滿足最後的截止時間不重要，但是如果音頻多媒體運作不穩定，聲音品質會持續惡化。視訊也會造成問題，但是耳朵要比眼睛敏感很多。為了避免這些問題，程序排程必須能夠高度可預測的而且是有規律的。
批進行中的排程
現在讓我們把目光從一般性的排程轉換為特定的排程算法。下面我們會探讨在批進行中的排程。
先來先服務
很像是先到先得。。。可能最簡單的非搶占式排程算法的設計就是 先來先服務(first-come,first-serverd)。使用此算法，将按照請求順序為程序配置設定 CPU。最基本的，會有一個就緒程序的等待隊列。當第一個任務從外部進入系統時，将會立即啟動并允許運作任意長的時間。它不會因為運作時間太長而中斷。當其他作業進入時，它們排到就緒隊列尾部。當正在運作的程序阻塞，處于等待隊列的第一個程序就開始運作。當一個阻塞的程序重新處于就緒态時，它會像一個新到達的任務，會排在隊列的末尾，即排在所有程序最後。
這個算法的強大之處在于易于了解和程式設計，在這個算法中，一個單連結清單記錄了所有就緒程序。要選取一個程序運作，隻要從該隊列的頭部移走一個程序即可；要添加一個新的作業或者阻塞一個程序，隻要把這個作業或程序附加在隊列的末尾即可。這是很簡單的一種實作。
不過，先來先服務也是有缺點的，那就是沒有優先級的關系，試想一下，如果有 100 個 I/O 程序正在排隊，第 101 個是一個 CPU 密集型程序，那豈不是需要等 100 個 I/O 程序運作完畢才會等到一個 CPU 密集型程序運作，這在實際情況下根本不可能，是以需要優先級或者搶占式程序的出現來優先選擇重要的程序運作。
最短作業優先
批進行中，第二種排程算法是 最短作業優先(Shortest Job First)，我們假設運作時間已知。例如，一家保險公司，因為每天要做類似的工作，是以人們可以相當精确地預測處理 1000 個索賠的一批作業需要多長時間。當輸入隊列中有若幹個同等重要的作業被啟動時，排程程式應使用最短優先作業算法
如上圖 a 所示，這裡有 4 個作業 A、B、C、D ，運作時間分别為 8、4、4、4 分鐘。若按圖中的次序運作，則 A 的周轉時間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時間内為 14 分鐘。
現在考慮使用最短作業優先算法運作 4 個作業，如上圖 b 所示，目前的周轉時間分别為 4、8、12、20，平均為 11 分鐘，可以證明最短作業優先是最優的。考慮有 4 個作業的情況，其運作時間分别為 a、b、c、d。第一個作業在時間 a 結束，第二個在時間 a + b 結束，以此類推。平均周轉時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，是以 a 應該是最短優先作業，其次是 b，然後是 c ，最後是 d 它就隻能影響自己的周轉時間了。
需要注意的是，在所有的程序都可以運作的情況下，最短作業優先的算法才是最優的。
最短剩餘時間優先
最短作業優先的搶占式版本被稱作為 最短剩餘時間優先(Shortest Remaining Time Next) 算法。使用這個算法，排程程式總是選擇剩餘運作時間最短的那個程序運作。當一個新作業到達時，其整個時間同目前程序的剩餘時間做比較。如果新的程序比目前運作程序需要更少的時間，目前程序就被挂起，而運作新的程序。這種方式能夠使短期作業獲得良好的服務。
互動式系統中的排程
互動式系統中在個人計算機、伺服器和其他系統中都是很常用的，是以有必要來探讨一下互動式排程
輪詢排程
一種最古老、最簡單、最公平并且最廣泛使用的算法就是 輪詢算法(round-robin)。每個程序都會被配置設定一個時間段，稱為時間片(quantum)，在這個時間片内允許程序運作。如果時間片結束時程序還在運作的話，則搶占一個 CPU 并将其配置設定給另一個程序。如果程序在時間片結束前阻塞或結束，則 CPU 立即進行切換。輪詢算法比較容易實作。排程程式所做的就是維護一個可運作程序的清單，就像下圖中的 a，當一個程序用完時間片後就被移到隊列的末尾，就像下圖的 b。
時間片輪詢排程中唯一有意思的一點就是時間片的長度。從一個程序切換到另一個程序需要一定的時間進行管理處理，包括儲存寄存器的值和記憶體映射、更新不同的表格和清單、清除和重新調入記憶體高速緩存等。這種切換稱作 程序間切換(process switch) 和 上下文切換(context switch)。如果程序間的切換時間需要 1ms，其中包括記憶體映射、清除和重新調入高速緩存等，再假設時間片設為 4 ms，那麼 CPU 在做完 4 ms 有用的工作之後，CPU 将花費 1 ms 來進行程序間的切換。是以，CPU 的時間片會浪費 20% 的時間在管理開銷上。耗費巨大。
為了提高 CPU 的效率，我們把時間片設定為 100 ms。現在時間的浪費隻有 1%。但是考慮會發現下面的情況，如果在一個非常短的時間内到達 50 個請求，并且對 CPU 有不同的需求，此時會發生什麼？50 個程序都被放在可運作程序清單中。如果 CP畫U 是空閑的，第一個程序會立即開始執行，第二個直到 100 ms 以後才會啟動，以此類推。不幸的是最後一個程序需要等待 5 秒才能獲得執行機會。大部分使用者都會覺得對于一個簡短的指令運作 5 秒是很慢的。如果隊列末尾的某些請求隻需要幾秒鐘的運作時間的話，這種設計就非常糟糕了。
另外一個因素是如果時間片設定長度要大于 CPU 使用長度，那麼搶占就不會經常發生。相反，在時間片用完之前，大多數程序都已經阻塞了，那麼就會引起程序間的切換。消除搶占可提高性能，因為程序切換僅在邏輯上必要時才發生，即流程阻塞且無法繼續時才發生。
結論可以表述如下：将上下文切換時間設定得太短會導緻過多的程序切換并降低 CPU 效率，但設定時間太長會導緻一個短請求很長時間得不到響應。最好的切換時間是在 20 - 50 毫秒之間設定。
優先級排程
輪詢排程假設了所有的程序是同等重要的。但事實情況可能不是這樣。例如，在一所大學中的等級制度，首先是院長，然後是教授、秘書、後勤人員，最後是學生。這種将外部情況考慮在内就實作了優先級排程(priority scheduling)
它的基本思想很明确，每個程序都被賦予一個優先級，優先級高的程序優先運作。
但是也不意味着高優先級的程序能夠永遠一直運作下去，排程程式會在每個時鐘中斷期間降低目前運作程序的優先級。如果此操作導緻其優先級降低到下一個最高程序的優先級以下，則會發生程序切換。或者，可以為每個程序配置設定允許運作的最大時間間隔。當時間間隔用完後，下一個高優先級的程序會得到運作的機會。
可以靜态或者動态的為程序配置設定優先級。在一台軍用計算機上，可以把将軍所啟動的程序設為優先級 100，上校為 90 ，少校為 80，上尉為 70，中尉為 60，以此類推。UNIX 有一條指令為 nice ，它允許使用者為了照顧他人而自願降低自己程序的優先級，但是一般沒人用。
優先級也可以由系統動态配置設定，用于實作某種目的。例如，有些程序為 I/O 密集型，其多數時間用來等待 I/O 結束。當這樣的程序需要 CPU 時，應立即配置設定 CPU，用來啟動下一個 I/O 請求，這樣就可以在另一個程序進行計算的同時執行 I/O 操作。這類 I/O 密集型程序長時間的等待 CPU 隻會造成它長時間占用記憶體。使 I/O 密集型程序獲得較好的服務的一種簡單算法是，将其優先級設為 1/f，f 為該程序在上一時間片中所占的部分。一個在 50 ms 的時間片中隻使用 1 ms 的程序将獲得優先級 50 ，而在阻塞之前用掉 25 ms 的程序将具有優先級 2，而使用掉全部時間片的程序将得到優先級 1。
可以很友善的将一組程序按優先級分成若幹類，并且在各個類之間采用優先級排程，而在各類程序的内部采用輪轉排程。下面展示了一個四個優先級類的系統
它的排程算法主要描述如下：上面存在優先級為 4 類的可運作程序，首先會按照輪轉法為每個程序運作一個時間片，此時不理會較低優先級的程序。若第 4 類程序為空，則按照輪詢的方式運作第三類程序。若第 4 類和第 3 類程序都為空，則按照輪轉法運作第 2 類程序。如果不對優先級進行調整，則低優先級的程序很容易産生饑餓現象。
多級隊列
最早使用優先級排程的系統是 CTSS(Compatible TimeSharing System)。CTSS 是一種相容分時系統，它有一個問題就是程序切換太慢，其原因是 IBM 7094 記憶體隻能放進一個程序。
IBM 是哥倫比亞大學計算機中心在 1964 - 1968 年的計算機
CTSS 在每次切換前都需要将目前程序換出到磁盤，并從磁盤上讀入一個新程序。CTSS 的設計者很快就認識到，為 CPU 密集型程序設定較長的時間片比頻繁地分給他們很短的時間要更有效（減少交換次數）。另一方面，如前所述，長時間片的程序又會影響到響應時間，解決辦法是設定優先級類。屬于最高優先級的程序運作一個時間片，次高優先級程序運作 2 個時間片，再下面一級運作 4 個時間片，以此類推。當一個程序用完配置設定的時間片後，它被移到下一類。
最短程序優先
對于批處理系統而言，由于最短作業優先常常伴随着最短響應時間，是以如果能夠把它用于互動式程序，那将是非常好的。在某種程度上，的确可以做到這一點。互動式程序通常遵循下列模式：等待指令、執行指令、等待指令、執行指令。。。如果我們把每個指令的執行都看作一個分離的作業，那麼我們可以通過首先運作最短的作業來使響應時間最短。這裡唯一的問題是如何從目前可運作程序中找出最短的那一個程序。
一種方式是根據程序過去的行為進行推測，并執行估計運作時間最短的那一個。假設每個終端上每條指令的預估運作時間為 T0，現在假設測量到其下一次運作時間為 T1，可以用兩個值的權重來改進估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是盡快忘掉老的運作時間，還是在一段長時間内始終記住它們。當 a = 1/2 時，可以得到下面這個序列
可以看到，在三輪過後，T0 在新的估計值中所占比重下降至 1/8。
有時把這種通過目前測量值和先前估計值進行權重平均進而得到下一個估計值的技術稱作 老化(aging)。這種方法會使用很多預測值基于目前值的情況。
保證排程
一種完全不同的排程方法是對使用者做出明确的性能保證。一種實際而且容易實作的保證是：若使用者工作時有 n 個使用者登入，則每個使用者将獲得 CPU 處理能力的 1/n。類似地，在一個有 n 個程序運作的單使用者系統中，若所有的程序都等價，則每個程序将獲得 1/n 的 CPU 時間。
彩票排程
對使用者進行承諾并在随後兌現承諾是一件好事，不過很難實作。但是存在着一種簡單的方式，有一種既可以給出預測結果而又有一種比較簡單的實作方式的算法，就是 彩票排程(lottery scheduling)算法。
其基本思想是為程序提供各種系統資源（例如 CPU 時間）的彩票。當做出一個排程決策的時候，就随機抽出一張彩票，擁有彩票的程序将獲得該資源。在應用到 CPU 排程時，系統可以每秒持有 50 次抽獎，每個中獎者将獲得比如 20 毫秒的 CPU 時間作為獎勵。
George Orwell 關于 所有的程序是平等的，但是某些程序能夠更平等一些。一些重要的程序可以給它們額外的彩票，以便增加他們赢得的機會。如果出售了 100 張彩票，而且有一個程序持有了它們中的 20 張，它就會有 20% 的機會去赢得彩票中獎。在長時間的運作中，它就會獲得 20% 的CPU。相反，對于優先級排程程式，很難說明擁有優先級 40 究竟是什麼意思，這裡的規則很清楚，擁有彩票 f 份額的程序大約得到系統資源的 f 份額。
如果希望程序之間協作的話可以交換它們之間的票據。例如，用戶端程序給伺服器程序發送了一條消息後阻塞，用戶端程序可能會把自己所有的票據都交給伺服器，來增加下一次伺服器運作的機會。當服務完成後，它會把彩票還給用戶端讓其有機會再次運作。事實上，如果沒有客戶機，伺服器也根本不需要彩票。
可以把彩票了解為 buff，這個 buff 有 15% 的幾率能讓你産生 速度之靴 的效果。
公平分享排程
到目前為止，我們假設被排程的都是各個程序自身，而不用考慮該程序的擁有者是誰。結果是，如果使用者 1 啟動了 9 個程序，而使用者 2 啟動了一個程序，使用輪轉或相同優先級排程算法，那麼使用者 1 将得到 90 % 的 CPU 時間，而使用者 2 将之得到 10 % 的 CPU 時間。
為了阻止這種情況的出現，一些系統在排程前會把程序的擁有者考慮在内。在這種模型下，每個使用者都會配置設定一些CPU 時間，而排程程式會選擇程序并強制執行。是以如果兩個使用者每個都會有 50% 的 CPU 時間片保證，那麼無論一個使用者有多少個程序，都将獲得相同的 CPU 份額。
實時系統中的排程
實時系統(real-time) 是一個時間扮演了重要作用的系統。典型的，一種或多種外部實體裝置發給計算機一個服務請求，而計算機必須在一個确定的時間範圍内恰當的做出反應。例如，在 CD 播放器中的計算機會獲得從驅動器過來的位流，然後必須在非常短的時間内将位流轉換為音樂播放出來。如果計算時間過長，那麼音樂就會聽起來有異常。再比如說醫院特别護理部門的病人監護裝置、飛機中的自動駕駛系統、列車中的煙霧警告裝置等，在這些例子中，正确但是卻緩慢的響應要比沒有響應甚至還糟糕。
實時系統可以分為兩類，硬實時(hard real time) 和 軟實時(soft real time) 系統，前者意味着必須要滿足絕對的截止時間；後者的含義是雖然不希望偶爾錯失截止時間，但是可以容忍。在這兩種情形中，實時都是通過把程式劃分為一組程序而實作的，其中每個程序的行為是可預測和提前可知的。這些程序一般壽命較短，并且極快的運作完成。在檢測到一個外部信号時，排程程式的任務就是按照滿足所有截止時間的要求排程程序。
實時系統中的事件可以按照響應方式進一步分類為周期性(以規則的時間間隔發生)事件或 非周期性(發生時間不可預知)事件。一個系統可能要響應多個周期性事件流，根據每個事件處理所需的時間，可能甚至無法處理所有事件。例如，如果有 m 個周期事件，事件 i 以周期 Pi 發生，并需要 Ci 秒 CPU 時間處理一個事件，那麼可以處理負載的條件是
隻有滿足這個條件的實時系統稱為可排程的，這意味着它實際上能夠被實作。一個不滿足此檢驗标準的程序不能被排程，因為這些程序共同需要的 CPU 時間總和大于 CPU 能提供的時間。
舉一個例子，考慮一個有三個周期性事件的軟實時系統，其周期分别是 100 ms、200 m 和 500 ms。如果這些事件分别需要 50 ms、30 ms 和 100 ms 的 CPU 時間，那麼該系統是可排程的，因為 0.5 + 0.15 + 0.2 < 1。如果此時有第四個事件加入，其周期為 1 秒，那麼此時這個事件如果不超過 150 ms，那麼仍然是可以排程的。忽略上下文切換的時間。
實時系統的排程算法可以是靜态的或動态的。前者在系統開始運作之前做出排程決策；後者在運作過程中進行排程決策。隻有在可以提前掌握所完成的工作以及必須滿足的截止時間等資訊時，靜态排程才能工作，而動态排程不需要這些限制。
排程政策和機制
到目前為止，我們隐含的假設系統中所有程序屬于不同的分組使用者并且程序間存在互相競争 CPU 的情況。通常情況下确實如此，但有時也會發生一個程序會有很多子程序并在其控制下運作的情況。例如，一個資料庫管理系統程序會有很多子程序。每一個子程序可能處理不同的請求，或者每個子程序實作不同的功能（如請求分析、磁盤通路等）。主程序完全可能掌握哪一個子程序最重要（或最緊迫），而哪一個最不重要。但是，以上讨論的排程算法中沒有一個算法從使用者程序接收有關的排程決策資訊，這就導緻了排程程式很少能夠做出最優的選擇。
解決問題的辦法是将 排程機制(scheduling mechanism) 和 排程政策(scheduling policy) 分開，這是長期一貫的原則。這也就意味着排程算法在某種方式下被參數化了，但是參數可以被使用者程序填寫。讓我們首先考慮資料庫的例子。假設核心使用優先級排程算法，并提供了一條可供程序設定優先級的系統調用。這樣，盡管父程序本身并不參與排程，但它可以控制如何排程子程序的細節。排程機制位于核心，而排程政策由使用者程序決定，排程政策和機制分離是一種關鍵性思路。
線程排程
當若幹程序都有多個線程時，就存在兩個層次的并行：程序和線程。在這樣的系統中排程處理有本質的差别，這取決于所支援的是使用者級線程還是核心級線程（或兩者都支援）。
首先考慮使用者級線程，由于核心并不知道有線程存在，是以核心還是和以前一樣地操作，選取一個程序，假設為 A，并給予 A 以時間片控制。A 中的線程排程程式決定哪個線程運作。假設為 A1。由于多道線程并不存在時鐘中斷，是以這個線程可以按其意願任意運作多長時間。如果該線程用完了程序的全部時間片，核心就會選擇另一個程序繼續運作。
在程序 A 終于又一次運作時，線程 A1 會接着運作。該線程會繼續耗費 A 程序的所有時間，直到它完成工作。不過，線程運作不會影響到其他程序。其他程序會得到排程程式所配置設定的合适份額，不會考慮程序 A 内部發生的事情。
現在考慮 A 線程每次 CPU 計算的工作比較少的情況，例如：在 50 ms 的時間片中有 5 ms 的計算工作。于是，每個線程運作一會兒，然後把 CPU 交回給線程排程程式。這樣在核心切換到程序 B 之前，就會有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。 如下所示
運作時系統使用的排程算法可以是上面介紹算法的任意一種。從實用方面考慮，輪轉排程和優先級排程更為常用。唯一的局限是，缺乏一個時鐘中斷運作過長的線程。但由于線程之間的合作關系，這通常也不是問題。
現在考慮使用核心線程的情況，核心選擇一個特定的線程運作。它不用考慮線程屬于哪個程序，不過如果有必要的話，也可以這麼做。對被選擇的線程賦予一個時間片，而且如果超過了時間片，就會強制挂起該線程。一個線程在 50 ms 的時間片内，5 ms 之後被阻塞，在 30 ms 的時間片中，線程的順序會是 A1,B1,A2,B2,A3,B3。如下圖所示
使用者級線程和核心級線程之間的主要差别在于性能。使用者級線程的切換需要少量的機器指令（想象一下Java程式的線程切換），而核心線程需要完整的上下文切換，修改記憶體映像，使高速緩存失效，這會導緻了若幹數量級的延遲。另一方面，在使用核心級線程時，一旦線程阻塞在 I/O 上就不需要在使用者級線程中那樣将整個程序挂起。
從程序 A 的一個線程切換到程序 B 的一個線程，其消耗要遠高于運作程序 A 的兩個線程（涉及修改記憶體映像，修改高速緩存），核心對這種切換的消耗是了解到，可以通過這些資訊作出決定。
文章參考：
《現代作業系統》
《Modern Operating System》forth edition
https://www.encyclopedia.com/computing/news-wires-white-papers-and-books/interactive-systems
https://j00ru.vexillium.org/syscalls/nt/32/
https://www.bottomupcs.com/process_hierarchy.xhtml
https://en.wikipedia.org/wiki/Runtime_system
https://en.wikipedia.org/wiki/Execution_model
https://zhidao.baidu.com/question/113227654.html
https://baike.baidu.com/item/等待隊列/9223804?fr=aladdin
http://www.columbia.edu/cu/computinghistory/7094.html