【作業系統原理】——行程

行程

什么是行程
??在作業系統中，作業系統需要對各種資源進行管理，大概可以分為以下幾類：記憶體，檔案，磁盤，行程，所謂行程就是作業系統有序管理應用程式的執行的方式，來保證以下幾點：
??1、所有資源對多個應用程式是可用的，
??2、物理處理器在多個應用程式中切換，保證所有程式都在執行中，
??3、處理器和I/O設備都能得到充分的利用，
??因此所有現代作業系統都依賴于一個模型，在該模型中，一個應用程式對應一個或多個行程，行程的定義有以下幾條：
??1、一個正在執行的程式，
??2、一個正在計算機上執行的程式實體，
??3、能分配給處理器并由處理器執行的物體，
??4、由一組執行的指令、一個當前狀態和一組相關的系統資源表征的活動單元，
??簡單來說什么是行程，行程就是正在執行中的程式，而在作業系統中，作業系統為了更好的描述一個行程，于是將行程視為一些元素組成的物體，而其中最重要的兩個元素是程式代碼和資料集，一般來說一個程式有了程式代碼和資料集就可以順利執行了，但是作業系統說還不夠，為了滿足作業系統對行程的控制，例如調度，中斷，執行等操作，作業系統將每個行程描述為一個叫做行程控制塊(PCB) 的資料結構，在PCB中存盤著作業系統對控制一個行程所需要的全部資訊，可以根據PCB找到程式代碼，找到程式的資料，程式獲得的資源等等，所以一個行程對于作業系統來說就是一個PCB，PCB中所存盤的資訊我們在下文中有詳細介紹，
??知道了作業系統是通過PCB管理行程的后接下來討論行程的狀態，

行程狀態

兩狀態模型
??在多道作業系統中，我們假設現在的處理器都是單核的即同時只能有一個行程正在處理器中執行，但是作業系統為了讓用戶看上去所有行程都在“同時”運行于是他在作業系統中設定了時間片，即一個行程可以連續執行的最大時間，并且按照調度演算法快速在不同行程間進行切換執行，執行中的行程狀態為運行態，而未執行的則成為非運行態，其中關系如下圖，
??
同時我們可以把非運行態的行程組織到佇列中，每次切換行程從佇列中調出一個行程開始運行，而切換下來的行程要么重新加入佇列要么執行完畢退出，如下圖，

?這里提一下可能導致創建新行程的事件和可能導致行程退出的事件，
??行程創建由以下4種事件觸發：
??1、新的批處理作業，新的批處理作業進入作業系統肯定會創建新的行程來執行批處理作業，
??2、用戶登錄，用戶登錄往往也會創建新行程來執行用戶指令，之所以使用行程是為了將用戶與作業系統隔離，一個用戶指令的崩潰不會影響到其他用戶乃至作業系統，
??3、為提供服務由作業系統創建，有時作業系統為了提供一個服務也會創建新的行程，例如用戶行程請求列印一個檔案，系統可以創建一個管理列印的行程，進而使請求行程可以繼續執行，
??4、由現有行程派生，當現有行程引發另一個行程的創建時，作業系統也會創建新的行程，這就是行程派生，這往往很有用，派生出的行程可以幫助主行程處理資料，組織資料等等，
??行程的終止由以下14種事件觸發：
??1、正常完成，正常結束運行，
??2、超過時限，行程運行超過規定的時限，
??3、無記憶體可用，系統無法滿足行程需要的記憶體，
??4、超出范圍，行程試圖訪問非法的記憶體單元，
??5、保護錯誤，行程試圖使用不允許使用的資源或檔案，
??6、算術錯誤，行程試圖進行被禁止的運算，
??7、時間超出，行程等待某一事件發生的時間超過了規定的時間，
??8、I/O失敗，在輸入輸出期間發生錯誤，
??9、無效指令，行程試圖執行一個不存在的指令，
??10、特權指令，行程試圖使用為作業系統保留的指令，
??11、資料誤用，錯誤型別或未初始化的一塊資料，
??12、操作員或作業系統干涉，操作員或作業系統終止行程，
??13、父行程終止，在某些作業系統中，父行程終止時作業系統會自動終止該行程的所有子行程，
??14、父行程請求，父行程要求終止其子行程，

五狀態模型
??如果所有行程都做好了準備，作業系統會從未運行佇列中以輪轉的方式調度每個行程，但是這里有個問題，如果并非所有行程都做好了準備呢？也許未運行的行程中有些行程正在等待某一事件的發生，也就是處于阻塞，因此單純的對所有未運行的行程進行輪轉是不科學的，應該對所有已經就緒的行程進行調度，解決這種問題的最好方法就是將未執行行程佇列拆分為兩個佇列分別是就緒佇列和阻塞佇列，由此行程的狀態由2狀態變為了3狀態，此外還要增加新建和退出態，這十分有必要，改進后的狀態模型如下圖所示，
?? ??運行態：行程正在執行，
??就緒態：行程做好了準備，隨時接收調度，
??阻塞態：行程在等待某些事件的發生，在事件發生前不能執行，如I/O操作，
??新建態：剛剛新建的行程，作業系統還未將其加載至記憶體，通常是PCB已經創建但是還并未加載到記憶體中的新程式，
??退出態：作業系統從可執行行程組中釋放的行程，
??新建態與退出態十分有必要，在一個行程被新建時它并非絕對會被調入記憶體，通常是分兩步，首先創建該行程的PCB，并與之關聯，但是此時可能面臨記憶體不足或者作業系統限制了最大行程數導致這個行程還無法被調入行程，因此該行程被暫時留在新建態，在這個狀態的行程PCB已經創建并且加載進記憶體，但是行程的代碼和資料往往還留在外存中等待加載，
??退出態也和新建態同理，當行程因為某些原因要被終止時，此時并不直接將其調出記憶體，首先作業系統會停止執行該行程的代碼，但是暫時讓其留在記憶體中，因為某些輔助程式或是支持程式會來記錄該行程相關資料和資訊，此時行程停留在退出態，等相關程式收集完所需資訊后，再將其所有資料從記憶體中移除，
??關于阻塞，就緒和運行三種狀態的轉換更為普遍和便于理解，作業系統從就緒佇列中調度某個行程進入運行態運行，當時間片結束后作業系統將其放回就緒態執行其他行程，如果在執行期間行程必須等待某些事件，便將其放入阻塞態，然后調度其他行程執行，當該行程等待的事件完成后作業系統則將其放回就緒態等待調度，
??但是此時又有一個問題，如果所有阻塞行程放在同一個阻塞佇列中，當一個事件完成后作業系統不得不掃描整個佇列找到那些等待該事件的行程然后將其放進就緒佇列中，這樣的效率十分低下，因此通常是為每一個事件創建一個阻塞佇列，同理當按照優先級進行調度時，也會將優先級相同的行程放進一個就緒佇列，避免掃描等低效的做法，這是典型的用空間換時間的做法，
??
七狀態模型
??在介紹七狀態模型前，我們思考一個問題，三個基本狀態（就緒，運行和阻塞）的所有行程都必須存盤在記憶體中，此時就可能出現一種情況，即所有行程都處于阻塞態，沒有就緒狀態的行程，此時又開始了處理器的空轉，處理器沒辦法執行行程只能開始等待行程從阻塞態恢復就緒態，并且加入此時又有新的行程處于新建態，由于記憶體不足，處于新建態的行程也沒辦法進入記憶體無法執行，這是一個十分致命的處理器空轉問題，解決這個問題有兩個方法：擴大記憶體，很顯然成本太高了；將阻塞態的行程暫時調出記憶體放回磁盤，來讓新建態的行程有足夠記憶體進入就緒態開始處理器的調度和運行，
??但是在將一個阻塞態行程掛起后，作業系統可以選擇接納一個新建態行程進入就緒佇列，也可以選擇將一個之前掛起的行程恢復就緒態，并且為了減少作業系統的負載作業系統更傾向于后者，但是處于掛起的行程也可能還并未接觸阻塞，將一個阻塞行程放回記憶體沒有任何意義，于是更好的方法是將掛起區分為兩個狀態即就緒/掛起態和阻塞/掛起態，這樣每次作業系統就只需要考慮是否應該把行程從就緒/掛起態換回就緒態即可，完整的七狀態模型如下：
??
阻塞/掛起態：行程在外存中并等待一個事件，
??就緒/掛起態：行程在外存中，但只要載入記憶體即可開始運行，
??并且作業系統允許行程從就緒變為就緒/掛起態，或從阻塞/掛起態變更為阻塞態，只是這樣做的意義不大，因此并不會這樣做，
??導致行程被掛起的事件有以下幾種：
??1、交換，為了釋放記憶體空間，
??2、其他OS原因，作業系統可能會掛起后臺行程或者工具行程，或掛起可能會導致問題的行程，
??3、互動式用戶請求，用戶希望掛起一個行程來進行除錯，
??4、定時，行程可被周期性的執行，并在等待下一個時間間隔時掛起，
??5、父行程請求，父行程可能希望掛起后代行程的執行，以檢查或修改掛起的行程，

行程描述

行程在作業系統中的描述方式
??作業系統可以管理計算機內的任何資源，包括記憶體、設備、檔案和行程， 但是作業系統是如何管理的呢？對于作業系統來說，所有的資源都被組織成對應的資料結構，記憶體對應記憶體表，設備對應設備表，檔案對應檔案表，行程自然也有行程表，如下圖，接下來我們將詳細介紹作業系統如何描述作業系統中的所有行程，也就是行程表的結構，
??
如上圖所示，行程表中存放著一個一個行程，而每個行程項都指向一個行程映像，什么是行程映像呢？我們說一個行程最基本的元素是用戶代碼以及元素集，初次之外還有若干作業系統控制行程所需的資訊，這些資訊都存放在行程映像中，并且還有一個行程用于存盤臨時資料的堆疊，因此行程映像中的典型元素可以概括如下：
??1、用戶資料，用戶空間中的可修改部分，包括程式資料、用戶堆疊區域和可修改的程式，
??2、用戶程式，待執行的程式，
??3、堆疊，每個行程有一個或多個后進先出堆疊，堆疊用于保存引數、程序呼叫地址和系統呼叫地址，
??4、行程描述塊，作業系統控制行程所需的資料，
??有了以上資訊就有了一個行程調度，運行所需的全部資料，這些資料在記憶體中有可能是連續的也有可能是不連續的，這根據作業系統記憶體管理的方式來決定，但是但從作業系統描述管理行程方式來看，作業系統通過在記憶體中的主行程表，每一表項都至少包含一個指向行程映像的指標，通過行程表作業系統可以找到控制行程所需的全部資料，

行程屬性

我們知道了作業系統通過行程表和行程映像描述行程，行程映像中的用戶資料和用戶程式都是根據用戶所寫的程式而定的，堆疊也只是用來保存引數呼叫地址所用的臨時儲存空間，但是其中我們要尤為重要介紹PCB（行程描述塊），正如之前所說行程描述塊中儲存了作業系統控制行程所需的一切資訊，對于作業系統來說拿到行程控制塊就可以控制行程進行調度等操作，那么行程控制塊中到底存放了行程哪些資訊呢？
??不同作業系統的PCB中組織的資訊是不同的，但是PCB中所有作業系統都需要的共用基礎資訊一共8種：
??1、識別符號：PID，與行程相關的唯一識別符號，
??2、狀態：行程狀態，狀態的劃分是接下來介紹的重點，
??3、優先級：與行程調度有關的優先級，
??4、程式計數器：程式中即將執行的下一條指令的地址，
??5、背景關系資料：行程執行時處理器的暫存器中的資料，
??6、記憶體指標：包括程式代碼及相關資料的指標，以及與其他行程共享記憶體的指標，
??7、I/O狀態資訊：行程的I/O請求，分配給行程的I/O設備和行程使用檔案
??8、記賬資訊：包括處理器時間綜合、使用的時鐘數綜合、時間限制、記帳號等，
??這些資訊一共可以分為三類行程標識資訊、處理器狀態資訊、行程控制資訊，行程標識資訊典型的就是識別符號，他是一個作業系統中唯一標識一個行程的基本索引，處理器狀態資訊由處理器暫存器的內容組成，中斷行程時，必須保存暫存器中的所有資訊，以便行程恢復時使用，這些資訊就保存在PCB中，典型的有背景關系資料，行程控制資訊是作業系統控制和協調各種活動行程所需的額外資訊，例如行程優先級，
??根據以上的介紹，行程映像在虛存中的結構基本如下圖所示，但是具體情況還得視作業系統的具體管理方案而定，
??

行程控制

執行模式
??作業系統必須保證自己的安全性，因此再讓用戶行程運行時并不能將所有的權限交給用戶，這樣作業系統很可能會被行程搞到崩潰，最好的方式是作業系統將一些特權指令不進行公開，用戶行程不能直接執行這些指令，但是作業系統允許行程發起使用特權指令的請求，然后再有作業系統自己代替用戶執行指令，這樣可以大大增強作業系統的健壯性，同時記憶體也并不會讓用戶行程都可以訪問到，如果修改了作業系統即內核可能會發生致命錯誤，于是這中間作業系統加入了種種限制，先從一個行程的執行上來說，作業系統將其分為了兩種模式用戶模式（用戶態/目態）和內核模式（內核態/管態），
??用戶行程默認是在用戶模式下運行，在用戶模式下行程的權限受到控制，而如果發生了一些特殊事件，例如請求系統呼叫模式會從用戶模式轉換為內核模式，說白了用戶模式即處理器在執行用戶代碼，內核模式即處理器目前在執行內核代碼，那么這樣有出現兩個問題，處理器如何知道它正在什么模式下執行？一般情況下，程式狀態中通常存在一個指示執行模式的位，該位會因模式的變化而變化，也就是說在處理器的一個暫存器中存盤了當前處理器處于什么模式下的資訊，例如Intel Itanium處理器中就有一個包含2位CPL（當前特權級別）欄位的處理器狀態暫存器用于存盤模式資訊，

行程創建

作業系統在創建一個行程的時候會進行哪些作業呢？當作業系統決定創建一個行程時會執行以下操作：
??1、為新行程分配一個唯一的行程描述符，
??2、為行程分配空間，
??3、初始化PCB，
??4、設定正確的鏈接，例如將行程放到就緒佇列中，而就緒佇列是一個鏈表，此時就需要在資料結構上進行連接，
??5、創建或擴充其他資料結構，例如創建賬單和評估性能，

行程切換和模式切換

行程切換
??行程切換在什么時候發生呢？理論上在任何時刻只要作業系統拿到控制權就可以進行行程切換，那么什么時候作業系統會重新拿到控制權呢？
??這里首先考慮中斷的情況，而中斷又可分為兩種：中斷和陷阱，中斷一般是與當前正運行行程無關的某種外部事件相關，例如完成了一次I/O操作，中斷處理器完成一些基本的輔助操作后將控制權轉給與已發生的終端相關的作業系統歷程，簡單來說中斷的發生屬于正常的事件，不過是作業系統暫時停止執行當前行程轉為處理另外一件更加緊急的事情，例如以下三種中斷：
??1、時鐘中斷，當前行程時間片到期，轉為從就緒佇列中調度新的行程開始運行，
??2、I/O中斷，某一I/O完成，作業系統判斷是否有正在等待該I/O的行程，如果有將其放回就緒態，隨后作業系統根據調度演算法調度合適的行程繼續運行，
??3、缺頁中斷，處理器遇到一個參考不存在記憶體中的虛存地址時，此時會發生缺頁中斷，然后作業系統要根據演算法將訪問的頁調入記憶體，這塊的處理與作業系統對記憶體管理有很大關系，
??除了中斷，陷阱也有可能會導致行程狀態的切換，所謂陷阱就是例外或者錯誤，即發生在程式內部的不可預期的非法錯誤，如果錯誤致命則將當前行程改為退出態，不致命時作業系統的行為決定于作業系統的設計，有可能是簡單的通知用戶，也有可能是嘗試恢復，
??還有一種可能會導致行程切換的事件，就是系統呼叫，當用戶行程發起一個特權指令（系統呼叫）時，作業系統會將當前用戶行程設定為阻塞態，然后會呼叫系統例程執行系統呼叫指令，當執行完畢會在此調度用戶行程開始執行，
??綜上所述，可能造成行程狀態切換的事件有三種中斷，陷阱(例外)，系統呼叫，

模式切換
??作業系統為了安全設定了不同的執行模式，那么作業系統何時進行模式切換呢？我們知道內核模式就是處理器在執行內核中的系統代碼，那么不難得出，只要發生狀態轉換的事件一定會造成模式轉換，例如中斷，不管時哪一種中斷，都少不了作業系統要根據調度演算法重新調度行程開始運行，更不用說缺頁中斷中作業系統還需要進入內核狀態執行記憶體置換演算法換頁等等；例外也是需要作業系統判斷如何進行下一步處理也需要進行模式切換；系統呼叫就是在執行系統歷程，更需要模式的切換，因此我們可以得出行程模式切換的基本事件就是中斷，陷阱（例外），系統呼叫，
??但是要注意的時，并非模式切換一定會導致運行態行程切換，例如在中斷后作業系統根據調度演算法決定繼續執行當前用戶行程，那么當前用戶行程就完全不需要改變狀態，相比切換運行態行程單單切換模式，作業系統所要做的操作可要少多了，所以行程切換一定會導致模式切換，但行程模式切換并不一定會發生行程狀態切換，

作業系統的組織形式

我們之前的介紹都基于作業系統是在所有行程獨立外的一個大型程式，是一組行程，那么作業系統到底是行程么？如果是行程的話又要怎么控制它？
??以下是幾種作業系統內核的設計方式，
??
在用戶行程內運行
??較小的計算機作業系統通常采用這種設計方式，這種方式是將系統內核代碼放到每個行程虛存中的共享區，這樣做的好處是如果要執行系統代碼不需要像無行程內核那樣切換代碼及資料以切換系統歷程，這種方式仍然是在每個用戶及行程內部執行作業系統代碼，不需要切換行程，只用在同一行程中切換模式即可，所帶來的系統開銷更小，更加快捷，并且在一個行程內用戶程式和作業系統程式都可執行，而在不同用戶行程中執行的作業系統程式是相同的，這也是為什么要將系統內核放到共享地址空間的原因，在這種方式下一個行程在虛存中的映像如下：

基于行程的作業系統
??這種設計方式是把作業系統作為一組系統行程來實作，和其他方法一樣同樣是在內核模式下運行系統代碼，但是在這種情況下是吧內核功能都組織為獨立的行程，但同時往往也將一些進行行程切換作業的代碼獨立出來，這種方式的好處是使用模塊化系統設計的原理，可以將一些作業系統功能作為獨立行程來實作，同時這種方式在多處理或多繼環境中很有用，這種設計方式的示意圖如下：
??

Linux的行程管理

Linux屬于類UNIX作業系統，實作的原理與UNIX行程的實作方法類似，其實大部分的作業系統都要遵循系統設計的基本原理，但是實作細節上會有所不同，在Linux上行程狀態轉換如下圖：

在Linux系統實作中最大的變化就是將阻塞態變為了可中斷和不可中斷兩個狀態，并且加入了停止態，
??1、可中斷：這是一個阻塞態，行程正在等待一個事件的結束，
??2、不可中斷：這是一個阻塞態，與可中斷的區別是，此時行程正在等待一個硬體條件，因此屏蔽任何信號，
??3、停止：行程收到信號要求被其他行程暫停執行，并且只能由另一個行程的主動動作恢復運行，

行程和執行緒之間的區別

這是十分常見的問題，在此做同一歸納和梳理：
??1、行程是資源分配的基本單位，執行緒是處理器調度的基本單位，
??2、同一行程內執行緒共享行程狀態和資源，例如資料段，代碼段，I/O資訊等，但是每個執行緒內也有獨立的資料，每個執行緒都擁有屬于自己的堆疊，執行緒屬性資訊存在執行緒控制塊中，例如背景關系資料，執行緒狀態，調度資訊等，
??3、執行緒是輕量級行程，因此創建和銷毀所消耗的系統資源更少，更快，
??4、同一行程內執行緒切換所消耗的資源相比行程切換更少且更快，
??5、同一行程內執行緒共享大部分資料因此通信起來更加方便，無需借助內核，