管程
為了能夠編寫更加準確無誤的程序，Brinch Hansen 和 Hoare 提出了一個更高級的同步原語叫做 管程(monitor)。他們兩個人的提案略有不同，通過下面的描述你就可以知道。管程是程序、變量和數據結構等組成的一個集合，它們組成一個特殊的模塊或者包。進程可以在任何需要的時候調用管程中的程序，但是它們不能從管程外部訪問數據結構和程序。下面展示了一種抽象的，類似 Pascal 語言展示的簡潔的管程。不能用 C 語言進行描述，因為管程是語言概念而 C 語言並不支持管程。
monitor example
integer i;
condition c;
procedure producer();
...
end;
procedure consumer();
.
end;end monitor;
管程有一個很重要的特性，即在任何時候管程中只能有一個活躍的進程，這一特性使管程能夠很方便的實現互斥操作。管程是程式語言的特性，所以編譯器知道它們的特殊性，因此可以採用與其他過程調用不同的方法來處理對管程的調用。通常情況下，當進程調用管程中的程序時，該程序的前幾條指令會檢查管程中是否有其他活躍的進程。如果有的話，調用進程將被掛起，直到另一個進程離開管程才將其喚醒。如果沒有活躍進程在使用管程，那麼該調用進程才可以進入。
進入管程中的互斥由編譯器負責，但是一種通用做法是使用 互斥量(mutex) 和 二進位信號量(binary semaphore)。由於編譯器而不是程式設計師在操作，因此出錯的機率會大大降低。在任何時候，編寫管程的程式設計師都無需關心編譯器是如何處理的。他只需要知道將所有的臨界區轉換成為管程過程即可。絕不會有兩個進程同時執行臨界區中的代碼。
即使管程提供了一種簡單的方式來實現互斥，但在我們看來，這還不夠。因為我們還需要一種在進程無法執行被阻塞。在生產者-消費者問題中，很容易將針對緩衝區滿和緩衝區空的測試放在管程程序中，但是生產者在發現緩衝區滿的時候該如何阻塞呢？
解決的辦法是引入條件變量(condition variables) 以及相關的兩個操作 wait 和 signal。當一個管程程序發現它不能運行時（例如，生產者發現緩衝區已滿），它會在某個條件變量（如 full）上執行 wait 操作。這個操作造成調用進程阻塞，並且還將另一個以前等在管程之外的進程調入管程。在前面的 pthread 中我們已經探討過條件變量的實現細節了。另一個進程，比如消費者可以通過執行 signal 來喚醒阻塞的調用進程。
Brinch Hansen 和 Hoare 在對進程喚醒上有所不同，Hoare 建議讓新喚醒的進程繼續運行；而掛起另外的進程。而 Brinch Hansen 建議讓執行 signal 的進程必須退出管程，這裡我們採用 Brinch Hansen 的建議，因為它在概念上更簡單，並且更容易實現。
如果在一個條件變量上有若干進程都在等待，則在對該條件執行 signal 操作後，系統調度程序只能選擇其中一個進程恢復運行。
順便提一下，這裡還有上面兩位教授沒有提出的第三種方式，它的理論是讓執行 signal 的進程繼續運行，等待這個進程退出管程時，其他進程才能進入管程。
條件變量不是計數器。條件變量也不能像信號量那樣積累信號以便以後使用。所以，如果向一個條件變量發送信號，但是該條件變量上沒有等待進程，那麼信號將會丟失。也就是說，wait 操作必須在 signal 之前執行。
下面是一個使用 Pascal 語言通過管程實現的生產者-消費者問題的解法
monitor ProducerConsumer
condition full,empty;
integer count;
procedure insert(item:integer);
begin
if count = N then wait(full); insert_item(item);
count := count + 1;
if count = 1 then signal(empty); end;
function remove:integer;
begin
if count = 0 then wait(empty); remove = remove_item; count := count - 1;
if count = N - 1 then signal(full); end;
count := 0;
end monitor;
procedure producer;
begin
while true do
begin
item = produce_item; ProducerConsumer.insert(item); end
end;
procedure consumer;
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item); end
end;
讀者可能覺得 wait 和 signal 操作看起來像是前面提到的 sleep 和 wakeup ，而且後者存在嚴重的競爭條件。它們確實很像，但是有個關鍵的區別：sleep 和 wakeup 之所以會失敗是因為當一個進程想睡眠時，另一個進程試圖去喚醒它。使用管程則不會發生這種情況。管程程序的自動互斥保證了這一點，如果管程過程中的生產者發現緩衝區已滿，它將能夠完成 wait 操作而不用擔心調度程序可能會在 wait 完成之前切換到消費者。甚至，在 wait 執行完成並且把生產者標誌為不可運行之前，是不會允許消費者進入管程的。
儘管類 Pascal 是一種想像的語言，但還是有一些真正的程式語言支持，比如 Java （終於輪到大 Java 出場了），Java 是能夠支持管程的，它是一種 面向對象的語言，支持用戶級線程，還允許將方法劃分為類。只要將關鍵字 synchronized 關鍵字加到方法中即可。Java 能夠保證一旦某個線程執行該方法，就不允許其他線程執行該對象中的任何 synchronized 方法。沒有關鍵字 synchronized ，就不能保證沒有交叉執行。
下面是 Java 使用管程解決的生產者-消費者問題
public class ProducerConsumer {
// 定義緩衝區大小的長度
static final int N = 100;
// 初始化一個新的生產者線程
static Producer p = new Producer();
// 初始化一個新的消費者線程
static Consumer c = new Consumer(); // 初始化一個管程
static Our_monitor mon = new Our_monitor();
// run 包含了線程代碼
static class Producer extends Thread{
public void run(){ int item;
// 生產者循環
while(true){ item = produce_item();
mon.insert(item);
}
}
// 生產代碼
private int produce_item(){...} }
// run 包含了線程代碼
static class consumer extends Thread { public void run( ) { int item;
while(true){
item = mon.remove();
consume_item(item);
}
}
// 消費代碼
private int produce_item(){...} }
// 這是管程
static class Our_monitor { private int buffer[] = new int[N];
// 計數器和索引
private int count = 0,lo = 0,hi = 0; private synchronized void insert(int val){ if(count == N){
// 如果緩衝區是滿的，則進入休眠 go_to_sleep(); }
// 向緩衝區插入內容
buffer[hi] = val;
// 找到下一個槽的為止
hi = (hi + 1) % N;
// 緩衝區中的數目自增 1
count = count + 1; if(count == 1){
// 如果消費者睡眠，則喚醒
notify(); }
}
private synchronized void remove(int val){ int val;
if(count == 0){
// 緩衝區是空的，進入休眠
go_to_sleep(); }
// 從緩衝區取出數據
val = buffer[lo];
// 設置待取出數據項的槽
lo = (lo + 1) % N; // 緩衝區中的數據項數目減 1
count = count - 1; if(count = N - 1){
// 如果生產者睡眠，喚醒它
notify(); }
return val;
}
private void go_to_sleep() {
try{
wait( );
}catch(Interr uptedExceptionexc) {};
}
}
}
上面的代碼中主要設計四個類，外部類(outer class) ProducerConsumer 創建並啟動兩個線程，p 和 c。第二個類和第三個類 Producer 和 Consumer 分別包含生產者和消費者代碼。最後，Our_monitor 是管程，它有兩個同步線程，用於在共享緩衝區中插入和取出數據。
在前面的所有例子中，生產者和消費者線程在功能上與它們是相同的。生產者有一個無限循環，該無限循環產生數據並將數據放入公共緩衝區中；消費者也有一個等價的無限循環，該無限循環用於從緩衝區取出數據並完成一系列工作。
程序中比較耐人尋味的就是 Our_monitor 了，它包含緩衝區、管理變量以及兩個同步方法。當生產者在 insert 內活動時，它保證消費者不能在 remove 方法中運行，從而保證更新變量以及緩衝區的安全性，並且不用擔心競爭條件。變量 count 記錄在緩衝區中數據的數量。變量 lo 是緩衝區槽的序號，指出將要取出的下一個數據項。類似地，hi 是緩衝區中下一個要放入的數據項序號。允許 lo = hi，含義是在緩衝區中有 0 個或 N 個數據。
Java 中的同步方法與其他經典管程有本質差別：Java 沒有內嵌的條件變量。然而，Java 提供了 wait 和 notify 分別與 sleep 和 wakeup 等價。
通過臨界區自動的互斥，管程比信號量更容易保證並行編程的正確性。但是管程也有缺點，我們前面說到過管程是一個程式語言的概念，編譯器必須要識別管程並用某種方式對其互斥作出保證。C、Pascal 以及大多數其他程式語言都沒有管程，所以不能依靠編譯器來遵守互斥規則。
與管程和信號量有關的另一個問題是，這些機制都是設計用來解決訪問共享內存的一個或多個 CPU 上的互斥問題的。通過將信號量放在共享內存中並用 TSL 或 XCHG 指令來保護它們，可以避免競爭。但是如果是在分布式系統中，可能同時具有多個 CPU 的情況，並且每個 CPU 都有自己的私有內存呢，它們通過網絡相連，那麼這些原語將會失效。因為信號量太低級了，而管程在少數幾種程式語言之外無法使用，所以還需要其他方法。
消息傳遞
上面提到的其他方法就是 消息傳遞(messaage passing)。這種進程間通信的方法使用兩個原語 send 和 receive ，它們像信號量而不像管程，是系統調用而不是語言級別。示例如下
send(destination, &message);
receive(source, &message);
send 方法用於向一個給定的目標發送一條消息，receive 從一個給定的源接受一條消息。如果沒有消息，接受者可能被阻塞，直到接受一條消息或者帶著錯誤碼返回。
消息傳遞系統的設計要點
消息傳遞系統現在面臨著許多信號量和管程所未涉及的問題和設計難點，尤其對那些在網絡中不同機器上的通信狀況。例如，消息有可能被網絡丟失。為了防止消息丟失，發送方和接收方可以達成一致：一旦接受到消息後，接收方馬上回送一條特殊的 確認(acknowledgement) 消息。如果發送方在一段時間間隔內未收到確認，則重發消息。
現在考慮消息本身被正確接收，而返回給發送著的確認消息丟失的情況。發送者將重發消息，這樣接受者將收到兩次相同的消息。
對於接收者來說，如何區分新的消息和一條重發的老消息是非常重要的。通常採用在每條原始消息中嵌入一個連續的序號來解決此問題。如果接受者收到一條消息，它具有與前面某一條消息一樣的序號，就知道這條消息是重複的，可以忽略。
消息系統還必須處理如何命名進程的問題，以便在發送或接收調用中清晰的指明進程。身份驗證(authentication) 也是一個問題，比如客戶端怎麼知道它是在與一個真正的文件伺服器通信，從發送方到接收方的信息有可能被中間人所篡改。
假設所有的消息都有相同的大小，並且在尚未接受到發出的消息時，由作業系統自動進行緩衝。在該解決方案中共使用 N 條消息，這就類似於一塊共享內存緩衝區的 N 個槽。消費者首先將 N 條空消息發送給生產者。當生產者向消費者傳遞一個數據項時，它取走一條空消息並返回一條填充了內容的消息。通過這種方式，系統中總的消息數量保持不變，所以消息都可以存放在事先確定數量的內存中。
如果生產者的速度要比消費者快，則所有的消息最終都將被填滿，等待消費者，生產者將被阻塞，等待返回一條空消息。如果消費者速度快，那麼情況將正相反：所有的消息均為空，等待生產者來填充，消費者將被阻塞，以等待一條填充過的消息。
消息傳遞的方式有許多變體，下面先介紹如何對消息進行 編址。
一種方法是為每個進程分配一個唯一的地址，讓消息按進程的地址編址。
另一種方式是引入一個新的數據結構，稱為 信箱(mailbox)，信箱是一個用來對一定的數據進行緩衝的數據結構，信箱中消息的設置方法也有多種，典型的方法是在信箱創建時確定消息的數量。在使用信箱時，在 send 和 receive 調用的地址參數就是信箱的地址，而不是進程的地址。當一個進程試圖向一個滿的信箱發送消息時，它將被掛起，直到信箱中有消息被取走，從而為新的消息騰出地址空間。
屏障
最後一個同步機制是準備用於進程組而不是進程間的生產者-消費者情況的。在某些應用中劃分了若干階段，並且規定，除非所有的進程都就緒準備著手下一個階段，否則任何進程都不能進入下一個階段，可以通過在每個階段的結尾安裝一個 屏障(barrier) 來實現這種行為。當一個進程到達屏障時，它會被屏障所攔截，直到所有的屏障都到達為止。屏障可用於一組進程同步，如下圖所示
在上圖中我們可以看到，有四個進程接近屏障，這意味著每個進程都在進行運算，但是還沒有到達每個階段的結尾。過了一段時間後，A、B、D 三個進程都到達了屏障，各自的進程被掛起，但此時還不能進入下一個階段呢，因為進程 B 還沒有執行完畢。結果，當最後一個 C 到達屏障後，這個進程組才能夠進入下一個階段。
避免鎖：讀-複製-更新
最快的鎖是根本沒有鎖。問題在於沒有鎖的情況下，我們是否允許對共享數據結構的並發讀寫進行訪問。答案當然是不可以。假設進程 A 正在對一個數字數組進行排序，而進程 B 正在計算其平均值，而此時你進行 A 的移動，會導致 B 會多次讀到重複值，而某些值根本沒有遇到過。
然而，在某些情況下，我們可以允許寫操作來更新數據結構，即便還有其他的進程正在使用。竅門在於確保每個讀操作要麼讀取舊的版本，要麼讀取新的版本，例如下面的樹
上面的樹中，讀操作從根部到葉子遍歷整個樹。加入一個新節點 X 後，為了實現這一操作，我們要讓這個節點在樹中可見之前使它"恰好正確"：我們對節點 X 中的所有值進行初始化，包括它的子節點指針。然後通過原子寫操作，使 X 稱為 A 的子節點。所有的讀操作都不會讀到前後不一致的版本
在上面的圖中，我們接著移除 B 和 D。首先，將 A 的左子節點指針指向 C 。所有原本在 A 中的讀操作將會後續讀到節點 C ，而永遠不會讀到 B 和 D。也就是說，它們將只會讀取到新版數據。同樣，所有當前在 B 和 D 中的讀操作將繼續按照原始的數據結構指針並且讀取舊版數據。所有操作均能正確運行，我們不需要鎖住任何東西。而不需要鎖住數據就能夠移除 B 和 D 的主要原因就是 讀-複製-更新(Ready-Copy-Update,RCU)，將更新過程中的移除和再分配過程分離開。
調度
當一個計算機是多道程序設計系統時，會頻繁的有很多進程或者線程來同時競爭 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 的兩個線程（涉及修改內存映像，修改高速緩存），內核對這種切換的消耗是了解到，可以通過這些信息作出決定。