操作系統——進程和線程

文章目錄

其他文章

進程

進程的概念

進程的狀態

五狀態模型

七狀態模型

進程的控制結構

進程的切換

線程

什么是線程？

線程的上下文切換

進程調度

什么時候調度進程

以什么原則來調度進程

進程調度算法

先來先服務

時間片輪轉調度

最短作業優先

最短剩余時間優先

優先級調度

多級反饋隊列調度

其他文章

操作系統——概述

操作系統——內存管理

操作系統——進程和線程

操作系統——進程間通信

操作系統——文件系統

操作系統——設備管理

操作系統——網絡系統

進程

進程的概念

我們編寫的代碼只是一個存儲在硬盤的靜態文件，通過編譯后就會生成二進制可執行文件，當我們運行這個可執行文件后，它會被裝載到內存中，接著 CPU 會執行程序中的每一條指令，那么這個運行中的程序，就被稱為「進程」。

我們把操作系統做某件事，抽象成一種概念，稱之為一個任務。一個進程可以對應一個任務，也可以對應多個任務。

早期的計算機只有一個 CPU，多個任務需要運行怎么辦？需要依次排隊等待，串行執行，一個任務執行完畢，才能執行下一個。這種方式存在著明顯的弊端，假設排在前面的 A 任務需要執行5小時，而排后面的B任務僅需要1分鐘，那么 B 任務必須等待 A 任務5小時完成后，才能執行，這種方式顯得極其不靈活。

后來就有了多任務系統，在CPU同一時間只能處理一個任務的前提下，每個任務有一定的執行時長，比如任務A執行0.001s，切換到任務B執行0.05s，再切換到任務C執行0.01s…不斷循環。這種機制也就可以在一定程度上解決上述任務B需要長時間等待的問題。

由于 CPU 速度非常快，這種多個任務不斷切換，會給用戶一種任務并行執行的錯覺，這種也被稱為是偽并行調度。既然有偽并行，那么也會有真并行。在現代計算機中，常見的CPU核數可以達到8核甚至更多，操作系統可將每一個核視為一個CPU，那么8核CPU就可以真并行執行8個任務。

并發和并行有什么區別？

偽并行雖然可以解決上述任務等待的問題，但是依然還存在一系列未解之謎：

每個任務應該執行多長時間？

如何找到要執行的下一個任務？

有些任務涉及了資源操作，執行到一半，切換任務，那么這些資源怎么辦？

為了解決上面一系列謎題，我們需要一種模型對任務進行詳盡的描述記錄。

進程的狀態

那么什么原因會導致進程會被創建，從而生成PCB呢？常見的有以下幾種

系統初始化

用戶通過系統提供的API創建新進程

批處理作業初始化 (什么是批處理作業)

由現有進程派生子進程

一個進程，因為某種原因被創建了，那么它可以按照以下步驟進行一系列的初始化

給新進程分配一個進程ID

分配內存空間

初始化PCB

進入就緒隊列

五狀態模型

如圖，進入就緒隊列，其狀態就會變為就緒態。各個狀態之間的關系描述如下：

就緒 -> 運行：當操作系統內存在著調度程序，當需要運行一個新進程時，調度程序選擇一個就緒態的進程，讓其進入運行態。

運行 -> 就緒：運行態的進程，會占有CPU（參照一開始的餅狀圖）。每個進程會被分配一定的執行時間，當時間結束后，重新回到就緒態。

運行 -> 阻塞：進程請求調用系統的某些服務，但是操作系統沒法立即給它（比如這種服務可能要耗時初始化，比如I/O資源需要等待），那么它就會進入阻塞態。

阻塞 -> 就緒：當等待結束了，就由阻塞態進入就緒態。

運行 -> 終止：當進程表示自己已經完成了，它會被操作系統終止。

這便是對于單個進程，經典的五狀態模型。當存在多個進程時，由于同一時間只能有一個進程在執行，那么如何去管理這一系列的處于阻塞態和就緒態的進程呢？一般來說，會使用就緒隊列，和阻塞隊列，讓處于阻塞態和就緒態的進程進入隊列，排隊執行。

七狀態模型

一旦排隊的進程多了，對于有限的內存空間將會是極大的考驗。為了解決內存占用問題，可以將一部分內存中的進程交換到磁盤中，這些被交換到磁盤的進程，會進入掛起狀態

掛起狀態可以分為兩種：

阻塞掛起狀態：進程在外存（硬盤）并等待某個事件的出現；

就緒掛起狀態：進程在外存（硬盤），但只要進入內存，即刻立刻運行；

這兩種掛起狀態加上前面的五種狀態，就變成了七種狀態變遷，見如下圖：

進程的控制結構

對于一個被執行的程序，操作系統會為該程序創建一個進程。進程作為一種抽象概念，可將其視為一個容器，該容器聚集了相關資源，包括地址空間，線程，打開的文件，保護許可等。而操作系統本身是一個程序，有一句經典的話 程序 = 算法 + 數據結構，因此對于單個進程，可以基于一種數據結構來表示它，這種數據結構稱之為進程控制塊(PCB)

在操作系統中，是用進程控制塊（process control block，PCB）數據結構來描述進程的。

PCB 是進程存在的唯一標識，這意味著一個進程的存在，必然會有一個 PCB，如果進程消失了，那么 PCB 也會隨之消失。

PCB 具體包含什么信息呢？

每個 PCB 是如何組織的呢？

通常是通過鏈表的方式進行組織，把具有相同狀態的進程鏈在一起，組成各種隊列。比如：

將所有處于就緒狀態的進程鏈在一起，稱為就緒隊列；

把所有因等待某事件而處于等待狀態的進程鏈在一起就組成各種阻塞隊列；

另外，對于運行隊列在單核 CPU 系統中則只有一個運行指針了，因為單核 CPU 在某個時間，只能運行一個程序。

那么，就緒隊列和阻塞隊列鏈表的組織形式如下圖：

除了鏈接的組織方式，還有索引方式，它的工作原理：將同一狀態的進程組織在一個索引表中，索引表項指向相應的 PCB，不同狀態對應不同的索引表。

一般會選擇鏈表，因為可能面臨進程創建，銷毀等調度導致進程狀態發生變化，所以鏈表能夠更加靈活的插入和刪除。

進程的切換

當一個正在運行中的進程被中斷，操作系統指定另一個就緒態的進程進入運行態，這個過程就是進程切換，也可以叫上下文切換。

該切換過程一般涉及以下步驟：

1.保存處理器上下文環境：將CPU程序計數器和寄存器的值保存到當前進程的私有堆棧里

2.更新當前進程的PCB（包括狀態更變）

3.將當前進程移到就緒隊列或者阻塞隊列

4.根據調度算法，選擇就緒隊列中一個合適的新進程，將其更改為運行態

5.更新內存管理的數據結構

6.新進程內對堆棧所保存的上下文信息載入到CPU的寄存器和程序計數器，占有CPU

發生進程上下文切換有哪些場景？

為了保證所有進程可以得到公平調度，CPU 時間被劃分為一段段的時間片，這些時間片再被輪流分配給各個進程。這樣，當某個進程的時間片耗盡了，就會被系統掛起，切換到其它正在等待 CPU 的進程運行；

進程在系統資源不足（比如內存不足）時，要等到資源滿足后才可以運行，這個時候進程也會被掛起，并由系統調度其他進程運行；

當進程通過睡眠函數 sleep 這樣的方法將自己主動掛起時，自然也會重新調度；

當有優先級更高的進程運行時，為了保證高優先級進程的運行，當前進程會被掛起，由高優先級進程來運行；

發生硬件中斷時，CPU 上的進程會被中斷掛起，轉而執行內核中的中斷服務程序；

以上，就是發生進程上下文切換的常見場景了。

線程

在早期的操作系統中都是以進程作為獨?運?的基本單位，直到后?，計算機科學家們?提出了更?的能獨?運?的基本單位，也就是線程。

什么是線程？

線程是進程當中的?條執?流程。

同?個進程內多個線程之間可以共享代碼段、數據段、打開的?件等資源，但每個線程各?都有?套獨?的寄存器和棧，這樣可以確保線程的控制流是相對獨?的。

我們一開始提及過，操作系統底層存在調度程序，調度程序可調度任務，而單線程進程，每個進程可以對應一個任務。現在，對于多線程的進程，每一個線程最終對于調度程序來說，都是一個任務，如下圖（Linux系統）。因此也有一種流行的說法線程是CPU調度的基本單位

線程的上下文切換

線程與進程最大的區別在于：線程是調度的基本單位，而進程則是資源擁有的基本單位。

所以，所謂操作系統的任務調度，實際上的調度對象是線程，而進程只是給線程提供了虛擬內存、全局變量等資源。

對于線程和進程，我們可以這么理解：

當進程只有一個線程時，可以認為進程就等于線程；

當進程擁有多個線程時，這些線程會共享相同的虛擬內存和全局變量等資源，這些資源在上下文切換時是不需要修改的；

另外，線程也有自己的私有數據，比如棧和寄存器等，這些在上下文切換時也是需要保存的。

線程上下文切換的是什么？

這還得看線程是不是屬于同一個進程：

當兩個線程不是屬于同一個進程，則切換的過程就跟進程上下文切換一樣；

當兩個線程是屬于同一個進程，因為虛擬內存是共享的，所以在切換時，虛擬內存這些資源就保持不動，只需要切換線程的私有數據、寄存器等不共享的數據；

所以，線程的上下文切換相比進程，開銷要小很多。

進程調度

進程都希望自己能夠占用 CPU 進行工作，那么這涉及到前面說過的進程上下文切換。

一旦操作系統把進程切換到運行狀態，也就意味著該進程占用著 CPU 在執行，但是當操作系統把進程切換到其他狀態時，那就不能在 CPU 中執行了，于是操作系統會選擇下一個要運行的進程。

選擇一個進程運行這一功能是在操作系統中完成的，通常稱為調度程序（scheduler）。

那到底什么時候調度進程，或以什么原則來調度進程呢？

什么時候調度進程

在進程的生命周期中，當進程從一個運行狀態到另外一狀態變化的時候，其實會觸發一次調度。

比如，以下狀態的變化都會觸發操作系統的調度：

從就緒態 -> 運行態：當進程被創建時，會進入到就緒隊列，操作系統會從就緒隊列選擇一個進程運行；

從運行態 -> 阻塞態：當進程發生 I/O 事件而阻塞時，操作系統必須另外一個進程運行；

從運行態 -> 結束態：當進程退出結束后，操作系統得從就緒隊列選擇另外一個進程運行；

因為，這些狀態變化的時候，操作系統需要考慮是否要讓新的進程給 CPU 運行，或者是否讓當前進程從 CPU 上退出來而換另一個進程運行。

另外，如果硬件時鐘提供某個頻率的周期性中斷，那么可以根據如何處理時鐘中斷

，把調度算法分為兩類：

非搶占式調度算法挑選一個進程，然后讓該進程運行直到被阻塞，或者直到該進程退出，才會調用另外一個進程，也就是說不會理時鐘中斷這個事情。

搶占式調度算法挑選一個進程，然后讓該進程只運行某段時間，如果在該時段結束時，該進程仍然在運行時，則會把它掛起，接著調度程序從就緒隊列挑選另外一個進程。這種搶占式調度處理，需要在時間間隔的末端發生時鐘中斷，以便把 CPU 控制返回給調度程序進行調度，也就是常說的時間片機制。

以什么原則來調度進程

五種調度原則：

CPU 利用率：調度程序應確保 CPU 是始終匆忙的狀態，這可提高 CPU 的利用率；

系統吞吐量：吞吐量表示的是單位時間內 CPU 完成進程的數量，長作業的進程會占用較長的 CPU 資源，因此會降低吞吐量，相反，短作業的進程會提升系統吞吐量；

周轉時間：周轉時間是進程運行和阻塞時間總和，一個進程的周轉時間越小越好；

等待時間：這個等待時間不是阻塞狀態的時間，而是進程處于就緒隊列的時間，等待的時間越長，用戶越不滿意；

響應時間：用戶提交請求到系統第一次產生響應所花費的時間，在交互式系統中，響應時間是衡量調度算法好壞的主要標準。

說白了，這么多調度原則，目的就是要使得進程要「快」。

進程調度算法

常見的進程調度算法有：

先來先服服務

時間片輪轉

最短作業優先

最短剩余時間優先

優先級調度

多級反饋隊列調度

先來先服務

先來先服務（First Come First Serverd, FCFS）。先進就緒隊列，則先被調度，先來先服務是最簡單的調度算法。

先來先服務存在上面談論過的問題：當前面任務耗費很長時間執行，那么后面的任務即使只需要執行很短的時間，也必須一直等待。屬于非搶占式

時間片輪轉調度

每一個進程會被分配一個時間片，表示允許該進程在這個時間段運行，如果時間結束了，進程還沒運行完畢，那么會通過搶占式調度，將CPU分配給其他進程，該進程回到就緒隊列。這是一種最簡單最公平的調度算法，但是有可能會存在問題。由于進程的切換，需要耗費時間，如果時間片太短，頻繁進行切換，會影響效率。如果進程時間片太長，有可能導致排后面的進程等待太長時間。因此時間片的長度，需要有大致合理的數值。（《現代操作系統》的觀點是建議時間片長度在20ms~50ms）。

最短作業優先

最短作業優先（Shortest Job First, SJF），顧名思義即進程按照作業時間長短排隊，作業時間段的排前面先執行，如 下圖。

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那么就會使得長作業不斷的往后推，周轉時間變長，致使長作業長期不會被運行。

最短剩余時間優先

最短剩余時間優先（Shortest Remaining Time Next），從就緒隊列中選擇剩余時間最短的進程進行調度。該算法可以理解最短作業優先和時間片輪轉的結合。如果沒有時間片，那么最短剩余時間其實就是最短作業時間，因為每個進程都是從頭執行到尾。

優先級調度

假設就緒隊列中有如下進程

按照優先級調度，執行順序為p1->p3->p2。如果多個進程優先級相同，則按照先來先服務的方式依次執行。

優先級調度可以進一步細分為搶占式和非搶占式。

非搶占式：和上面提及的非搶占式類似，一旦該進程占有CPU就將一直執行到結束或者阻塞。

搶占式：進程執行期間，一旦有更高優先級的進程進入就緒隊列，那么該進程就會被暫停，重回就緒隊列，讓更高優先級的進程執行。但是為了防止最高優先級進程一直執行，每個進程依然有自己的時間片，每次時間片結束后，會根據一定規則降低該進程優先級，避免某些最高優先級長作業進程一直占用CPU。

但是依然有缺點，可能會導致低優先級的進程永遠不會運行。

多級反饋隊列調度

多級反饋隊列調度基于時間片輪轉和優先級調度，設置多個就緒隊列，賦予每個就緒隊列優先級，優先級越高的隊列進程的時間片越短。如下圖，第1級就緒隊列優先級最高，進程的時間片長度最短，第2級就緒隊列次之，以此類推。

當有新的進程創建時，先進入第1級就緒隊列，時間片結束之前就運行完畢，則終止，否則進入第2級隊列等待下一次調度。在n級隊列之前，進程按照先到先服務規則依次調度，到了第n級隊列（最后一級）采用時間片輪轉調度。僅當第1級隊列為空時，才調度第2級隊列的進程，如果第i級隊列的進程正在運行，此時有一個更高優先級的進程進入，則會停下第i級的進程，讓它回到第i級隊列尾部，轉而執行更高優先級的進程，即滿足優先級調度算法的原則。

可以發現，對于短作業可能可以在第一級隊列很快被處理完。對于長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也會更長了，所以該算法很好的兼顧了長短作業，同時有較好的響應時間。

拿去銀行辦業務的例子，把上面的調度算法串起來

辦理業務的客戶相當于進程，銀行窗口工作人員相當于 CPU。

現在，假設這個銀行只有一個窗口（單核 CPU ），那么工作人員一次只能處理一個業務。

那么最簡單的處理方式，就是先來的先處理，后面來的就乖乖排隊，這就是先來先服務（FCFS）調度算法。但是萬一先來的這位老哥是來貸款的，這一談就好幾個小時，一直占用著窗口，這樣后面的人只能干等，或許后面的人只是想簡單的取個錢，幾分鐘就能搞定，卻因為前面老哥辦長業務而要等幾個小時，你說氣不氣人？

有客戶抱怨了，那我們就要改進，我們干脆優先給那些幾分鐘就能搞定的人辦理業務，這就是短作業優先（SJF）調度算法。聽起來不錯，但是依然還是有個極端情況，萬一辦理短業務的人非常的多，這會導致長業務的人一直得不到服務，萬一這個長業務是個大客戶，那不就撿了芝麻丟了西瓜

那就公平起見，現在窗口工作人員規定，每個人我只處理 10 分鐘。如果 10 分鐘之內處理完，就馬上換下一個人。如果沒處理完，依然換下一個人，但是客戶自己得記住辦理到哪個步驟了。這個也就是時間片輪轉（RR）調度算法。但是如果時間片設置過短，那么就會造成大量的上下文切換，增大了系統開銷。如果時間片過長，相當于退化成退化成 FCFS 算法了。

既然公平也可能存在問題，那銀行就對客戶分等級，分為普通客戶、VIP 客戶、SVIP 客戶。只要高優先級的客戶一來，就第一時間處理這個客戶，這就是最高優先級（HPF）調度算法。但依然也會有極端的問題，萬一當天來的全是高級客戶，那普通客戶不是沒有被服務的機會，不把普通客戶當人是嗎？那我們把優先級改成動態的，如果客戶辦理業務時間增加，則降低其優先級，如果客戶等待時間增加，則升高其優先級。

那有沒有兼顧到公平和效率的方式呢？這里介紹一種算法，考慮的還算充分的，多級反饋隊列（MFQ）調度算法，它是時間片輪轉算法和優先級算法的綜合和發展。它的工作方式：

銀行設置了多個排隊（就緒）隊列，每個隊列都有不同的優先級，各個隊列優先級從高到低，同時每個隊列執行時間片的長度也不同，優先級越高的時間片越短。

新客戶（進程）來了，先進入第一級隊列的末尾，按先來先服務原則排隊等待被叫號（運行）。如果時間片用完客戶的業務還沒辦理完成，則讓客戶進入到下一級隊列的末尾，以此類推，直至客戶業務辦理完成。

當第一級隊列沒人排隊時，就會叫號二級隊列的客戶。如果客戶辦理業務過程中，有新的客戶加入到較高優先級的隊列，那么此時辦理中的客戶需要停止辦理，回到原隊列的末尾等待再次叫號，因為要把窗口讓給剛進入較高優先級隊列的客戶。

可以發現，對于要辦理短業務的客戶來說，可以很快的輪到并解決。對于要辦理長業務的客戶，一下子解決不了，就可以放到下一個隊列，雖然等待的時間稍微變長了，但是輪到自己的辦理時間也變長了，也可以接受，不會造成極端的現象，可以說是綜合上面幾種算法的優點。

任務調度

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。