作業系統--行程管理

作業系統中需要管理的其中一項重要資源就是CPU時間，現代的作業系統為了提高效率，都會同時執行多個程式，以同時服務更多位使用者，也就必須更精確地控制分配CPU時間給每個程式執行。為了區分程式是否有取得CPU時間，又另外定義了所謂的行程(process)，這指的是正在執行中的程式。程式是一組靜態的指令，而行程則是程式在執行時的動態實體。在電腦系統中，每個行程都會歷經從建立、準備好可以執行、正在執行、等待某項資源、直到最後結束之間的幾個狀態，如圖所示。


1.建立(new)：行程一開始產生時是處於建立狀態，此時它尚未得到作業系統的允許進入記憶體。
2.就緒(ready)：作業系統將行程載入記憶體後，它就進入就緒狀態。在就緒狀態下的行程都是可以立即執行的，只有在等待CPU而已。
3.執行中(running)：行程目前正在使用CPU時間執行中，作業系統會決定在就緒狀態下的哪個行程可以下一個使用CPU，等到CPU一被釋放，該行程就可以開始使用CPU。
4.等待中(waiting)：行程因為某種原因進入等待中狀態，通常是需要某個除了CPU以外的資源，在取得所需的資源之前，它都無法繼續執行，會一直停留在等待中狀態，直到獲得解決後，再進入就緒狀態，等待下一次使用CPU。
5.結束(terminated)：行程已經執行完畢，作業系統也就無須維護其相關資訊。

由於程式的功能日益強大，使用者可能希望在程式執行當中同時進行多個工作，因此許多現代的作業系統會把行程更進一步劃分成多個執行緒(thread)，每個執行緒有各自的控制流程，但共同相同的程式碼區塊、資料區塊和作業系統資源。由此發展出一種新的多工方式，稱為多執行緒(multithreading)，它允許電腦在單一程式中執行多個工作。為了要使用多執行緒，程式設計人員必須將程式劃分成多個分離的執行緒。

CPU排程演算法(CPU sheduling)的目的是找出下一個可以取得CPU使用權的行程，也就是決定就緒狀態下的哪個行程可以進入執行中狀態，為了解決這個問題所發展出來的CPU排程演算法相當多，常用的有下列幾種：

先來先做(FCFS, First-Come First-Served)
原理是依照行程到達的先後順序來執行，先來的先做，直到做完再輪到下一個，就像排隊買票一樣。FCFS演算法雖然容易實作，但是它忽略了某些重要的因素，導致並不實際。萬一CPU分配給一個需要很長的執行時間的行程，但是它的後面卻排了一堆急著要執行的短行程，結果這些行程都必須等待很長的時間才能輪到。

最短工作先做(SJF, Shortest Job First)
原理是先檢查一遍在就緒狀態下的所有行程，將它們所需的執行時間從小到大排序，然後從時間最短的行程開始執行。一般來說，SJF演算法的平均等待時間可以證明出是最佳的，問題在於它是仰賴對於未來的猜測計算，作業系統必須事先「知道」每個行程的執行時間才能安排順序，但這是不可能的。因此，作業系統會根據一些經驗值和機率因子來推測，若推測與事實相差太遠，則SJF演算法的執行效能就會不如預期。

優先權(Priority)
原理是依照事先決定的優先權定義(例如期限、所需要的記憶體大小…等)，計算出每個行程的優先順序，然後依照優先須序給予CPU使用權。

循環分配(RR, Round Robin)
原理是專為分時系統所設計，作業系統事先定義一個固定的時間配額，並將CPU時間劃分成一個個時間配額，再對每個行程執行完畢，下一次就再分配一個時間配額給它，而行程在時間配額用完後，就立刻交出CPU的使用權，讓下一個行程使用，重複這個過程直到行程結束為止。