计算机操作系统学习笔记----进程管理
進程與線程
進程是資源分配的基本單位，也是獨立運行的基本單位。進程是資源分配的基本單位，這是與線程的主要區別。
?
程序的順序執行具有如下特征：
- 順序性；處理器的操作嚴格按照程序所規定的順序執行。
- 封閉性：程序一旦開始運行，其執行結果不受外界因素影響。
- 可再現性：只要執行時的初始條件與執行環境形同，當程序重復執行時，都將得到相同的結果。
?
程序的并發執行是指若干個程序（或程序段）同時在系統中運行，這些程序（或程序段）的執行在時間上是重疊的。
?
程序的并發執行的特征：
- 間斷性：有共享資源而產生的程序間的間接制約關系導致并發程序具有“執行-暫停-執行”這種間斷性的活動規律。
- 失去封閉性：多個程序共享系統中的各種資源，因而這些資源的狀態有多個程序來改變，致使程序的運行失去封閉性。
- 不可再現性：由于失去了封閉性 ，導致程序失去其運行結果的可再現性。
?
程序并發執行的條件（Bernstein條件）：
，表示程序在執行期間所需引用的所有變量的集合，成為讀集。
，表示程序在執行期間要改變的所有變量的集合，稱為寫集。
若兩個程序滿足下述的三個條件（又稱為Bernstein條件）,它們便可以并發執行，且其結果據哦于可再現性。
?
進程
進程：進程是可以并發執行的計算部分。
?
進程的特征：
動態性、并發性、獨立性、異步性、結構特征。
結構特征：每個進程都由程序段、數據段和一個進程控制塊（PCB）組成。
?
進程和程序的關系
- 進程是動態的，程序是靜止的。進程是程序的執行，程序是有序代碼的集合，無執行含義。
- 進程是暫時的，程序是永久的。進程是一個狀態變化的過程，程序可以長久保存。
- 進程與程序的組成不同。
- 通過多次執行，一個程序可以產生多個不同的進程；通過調用關系，一個進程可以執行多個程序。進程可創建其他進程，程序不能形成新的程序。
- 進程具有并行特性（獨立性、異步性），程序沒有。
?
進程映像（不重要）
由程序段、相關數據段、PCB三部分構成了進程映像，也叫進程實體。進程映像是靜態的，進程是動態的，進程是進程實體的運行過程。
?
作業的定義見此處
?
進程和作業的區別
作業是用戶需要計算機完成某項任務而要求計算機所做的工作的集合；進程是已提交完畢的作業的執行過程，是資源分配的基本單位。
兩者主要區別如下：
- 作業時用戶向計算機提交任務的任務實體，進程則是完成用戶任務的執行實體。
- 一個任務可以由一個或多個進程組成，但進程不能構成多個作業。
- 作業的概念主要用于批處理系統中，進程的概念幾乎都有雨多道程序系統中。
?
進程的組成
進程控制塊（PCB）：每個進程均有一個PCB，它是一個即能標識進程的存在、又能刻畫執行瞬間特征的數據結構。
程序段：程序段是進程中能被進程調度程序調度到CPU上執行的程序代碼段，能實現相應的特定功能。
數據段：一個進程的數據段可以是進程對應的程序加工處理的原始數據，也可以是程序執行時產生的中間結果或結果數據。
?
通常PCB都包括以下內容：
進程標識符（PID）
進程當前狀態
進程隊列指針：用于記錄PCB隊列中下一個PCB的地址。
程序和數據地址
CPU現場保護區 ：當進程因某種原因釋放處理器時，CPU現場信息（如指令計數器、狀態寄存器、通用寄存器等）被保證在PCB的該區域中，以便該進程重新獲得處理器后 能繼續執行。
通信信息
家族聯系
占有資源清單
?
PCB的作用
保證程序的并發執行。創建進程，實質上是創建進程的PCB；撤銷進程則是撤銷進程的PCB。
?
為什么PCB是進程的存在的唯一標志
系統總是通過PCB對進程進行控制的。
?
進程的狀態與轉換
創建狀態：進程在創建時需要申請一個空白PCB，向其中填寫控制和管理進程的信息，完成資源分配。如果創建工作無法完成，比如資源無法滿足，就無法被調度運行，把此時進程所處狀態稱為創建狀態
就緒狀態：進程已經準備好，已分配到所需資源，只要分配到CPU就能夠立即運行
執行狀態：進程處于就緒狀態被調度后，進程進入執行狀態
阻塞狀態：正在執行的進程由于某些事件（I/O請求，申請緩存區失敗）而暫時無法運行，進程受到阻塞。在滿足請求時進入就緒狀態等待系統調用
終止狀態：進程結束，或出現錯誤，或被系統終止，進入終止狀態。無法再執行
?
進程狀態的相互轉換，省略了創建和刪除。
?
進程的控制
包括進程的創建、進程的撤銷、進程阻塞和喚醒、進程的切換等。
?
線程
定義：線程是進程內一個相對獨立的、可調度的執行單元。
?
線程與進程的異同
- 調度：線程是獨立調度的基本單位，進程是擁有資源的基本單位。
- 擁有資源：進程是擁有資源的基本單位，而線程進擁有一點必不可少的資源（如程序計數器、一組寄存器和棧），但線程可以訪問其隸屬進程的系統資源。
- 并發性：在引入線程的操作系統中，不僅進程間可以并發執行，同一進程內的多個線程也可以并發執行。使操作系統具有更好的并發性，大大提高了系統的吞吐量。
- 系統開銷：線程的創建、撤銷、切換所需的系統開銷都比線程的大得多。
?
進程通信
進程通信指的使進程之間的信息交換。
高級進程通信方式可以分為3大類：共享存儲器系統、消息傳遞系統、管道通信系統。
?
處理器調度
處理器的三級調度
調度是操作系統的一個基礎功能，幾乎所有資源在使用前都需要調度，調度設計均圍繞如何高效利用CPU展開。
?
高級調度（作業調度）：主要任務是按照一定的原則從外存上出于后備狀態的作業中選擇一個或者多個，給它們分配內存、輸入／輸出設備等必要資源，別難過建立相應的進程，以使改作業具有競爭處理器的權利。作業調度的運行頻率較低，通常為幾分鐘一次。
中級調度：主要任務使按照給定的原則和策略，將出于外存對換區中具備運行條件的進程調入內存，并將其狀態修改為就緒狀態，掛在就緒隊列上等待；或者將出于內存中在世不餓能運行的進程交換到外存對換區，將此時的進程狀態稱為掛起狀態。主要涉及內存管理和擴充。
低級調度（進程調度）：主要任務使按照某種策略和方法從就緒隊列中選取一個進程，將處理器分配給它。進程調度的運行頻率很高，一般幾十毫秒運行一次。
?
高級調度與低級調度的區別：
- 作業調度為進程調度做準備，進程調度使進程被調用。
- 作業調度頻率低，進程調度頻率高。
- 有的系統可以不設置作業調度，但進程調度必須有。
?
調度的基本原則
標傲世單位時間內CPU完成作業的數量。
周轉時間：指作業從提交至完成的時間間隔，包括等待時間和執行時間。周轉時間用公式表示為
????????????????? 作業i的周轉時間=作業i的完成時間-作業i的提交時間
平均周轉時間：至多個作業周轉時間的平均值。
帶權周轉時間：指作業周轉時間與運行時間的比。作業i的帶權周轉時間用公式表示為
???????????????????????? =作業i的周轉時間/作業i的運行時間
平均帶權周轉時間：與平均周轉時間類似，求平均即可。
調度算法
1. 先來先服務調度算法（FCFS）（作業調度、進程調度）
2.短作業優先調度算法（SJF）（作業調度、進程調度）
3.優先級調度算法（作業調度、進程調度）
4.時間片輪轉調度算法（進程調度）
?????? 系統將所有就緒進程按到達時間的先后次序排成一個隊列，進門處調度程序總是選擇隊列中的第一個進程執行，并規定執行一定時間，稱為時間片。當該進程用完這一時間片時（即是進程并未執行結束），系統將他送至就緒隊列隊尾，在把處理器分配給下一個就緒進程。
?????? 時間片的大小通常由以下因素確定：系統相應時間、就緒隊列中的進程數目、系統處理能力
5. 高響應比優先調度算法（作業調度）
??? 響應比=作業響應時間/估計運行時間
??? 即
??? 響應比=（作業等待時間+估計運行時間）/估計運行時間
6. 多級隊列調度算法（進程調度）
??? 基本思想：根據進程的性質或類型，將就緒隊列劃分為若干個獨立的隊列，每個進程固定地分屬于一個隊列。每個隊列采取一種調度算法，不同的隊列可以采用不同的調度算法。
7. 多級反饋隊列調度算法（進程調度）
??? 多級反饋隊列調度算法時時間片輪轉調度算法和優先級調度算法的綜合和發展。通過動態調整進程優先級和時間片大小，可兼顧多方面的系統目標。
?
同步與互斥
基本概念
兩種形式的制約關系
間接相互制約關系（互斥）：若某一進程要求使用某種資源，而該資源正被另一進程使用，并且該資源不允許兩個進程同時使用，那么該進程只好等待已占用資源的進程釋放資源后在使用。這種制約關系的基本形式是“進程-資源-進程”。
直接相互制約關系（同步）：某一進程若收不到另一進程給他提供的必要信息就不能繼續運行下去，這種情況表明了兩個進程之間ian在某些點上要交換信息i，相互交流運行情況。這種制約關系的基本形式是“進程-進程”。
區分方法：同類進程即為互斥關系，不同類進程為同步關系。
?
臨界資源與臨界區
臨界資源：同時僅允許一個進程使用的資源。
臨界資源的訪問可以分為四個部分：
進入區
臨界區。進程中用于訪問臨界資源的代碼。
退出區
剩余區
臨界資源與臨界區的區別：臨界資源是一種系統資源，需要不同進程互斥訪問；臨界區是每個進程中訪問臨界資源的一段代碼，是屬于對應進程的。
?
互斥的概念與要求
為禁止兩個進程同時進入臨界區，軟件算法或同步機構都應遵循以下準則。
- 空間讓進
- 忙則等待
- 有限等待
- 讓權等待
?
同步的概念與實現機制
可以用信號量實現同步。
?
互斥實現方法
1.軟件方法
算法1：設置一個公用整形變量turn，用來表示允許進入臨界區的進程標識。若turn為0，則允許進程P0進入臨界區；否則循環檢查該變量，直到turn變為本進程標識；在推出去，修改允許進入進程的標識turn為1. 進程P1的算法于此類似，兩個進程的程序結構如下：
int turn = 0; P0:{Do{While(turn!=0); //當turn不為0時循環檢查，直到為0（進入區）進程P0的臨界區代碼CS0； //（臨界區）turn=1； //退出區進程P0 的其他代碼；}While（true） //循環執行這段代碼}P1:{Do{While(turn!=1); // 進入區）進程P0的臨界區代碼CS1； //（臨界區）turn=0； //退出區進程P1 的其他代碼；}While（true） //循環執行這段代碼}此方法可以保證互斥訪問臨界資源，但存在的問題是強制兩個進程以交替次序進入臨界區，很容易造成資源利用不充分。例如，當進程P0退出臨界區后將turn設置為1，但此時P1暫時不要求訪問該臨界資源，而P0又想再次訪問臨界資源，則它將無法進入臨界區。可見，此算法無法保證實現“空閑讓進”準則。
算法2：設置標志數組flag[]表示進程是否在臨界區中執行，初值均為假。在每個進程訪問該臨界資源之前，現檢查另一個進程是否在臨界區中，若不再，則修改本進程的臨界區標志為真，并進入臨界區，在推出區修改本進程臨界區標志為假。兩進程的程序結構如下：
enmu boolean{false,true}; //設置數組元素類型 boolean flag[2]={false,false}; //設置標志數組 P0:{DO{While flag[1]; //flag[1]為真表示P1在訪問臨界區，P0等待 （進入區）flag[0] = true; //進入區進程P0的臨界區代碼CS0; //臨界區flag[0] = flase; //退出區進程P0的其他代碼；}While(true)}P1:{DO{While flag[0]; //flag[0]為真表示P0在訪問臨界區，P0等待 （進入區）flag[1] = true; //進入區進程P0的臨界區代碼CS1; //臨界區flag[1] = flase; //退出區進程P1的其他代碼；}While(true)}此算法解決了‘空閑讓進“的問題，但當兩個進程都為進入臨界區時，此時各自的訪問標志都為false，若此時兩個進程同時想進入臨界區，并發現對方的標志值為false，于是兩個進程同時進入了各自的臨界區，違背了臨界區的訪問規則”忙則等待“。
?
算法3：仍然設置flag[]，但標志用來表示進程是否希望進入臨界區，每個進程在訪問臨界資源之前，先將自己的標志設置為真，然后檢查另一個進程的標志。若另一個進程的標志為真，則進程等待；反之則進入臨界區。兩進程的程序結構如下：
enmu boolean{false,true}; //設置數組元素類型 boolean flag[2]={false,false}; //設置標志數組 P0:{DO{flag[0] = true; //進入區While flag[1]; //flag[1]為真表示P1希望訪問臨界區，P0等待 （進入區）進程P0的臨界區代碼CS0; //臨界區flag[0] = flase; //退出區進程P0的其他代碼；}While(true)}P1:{DO{flag[1] = true; //進入區While flag[0]; //flag[0]為真表示P0希望訪問臨界區，P0等待 （進入區）進程P0的臨界區代碼CS1; //臨界區flag[1] = flase; //退出區進程P1的其他代碼；}While(true)}與算法2類似，同時請求時，兩進程標志都為true，都認為對方希望進入臨界區，并阻塞自己，造成”死等“現象，違背了”有限等待“準則。
?
算法4：算法3與1的結合。標志數組flag[]表示進程是否希望進入臨界區或是否在臨界區中執行。此外，還是只一個turn變量，用于表示允許進入臨界區的進程表示。兩進程的程序結構如下：
enmu boolean{false,true}; //設置數組元素類型 boolean flag[2]={false,false}; //設置標志數組 int turn; P0:{DO{flag[0] = true; //進入區turn =1; //此時P0未進入臨界區，仍然允許P1進入臨界區（進入區）While (flag[1] && turn==1); //flag[1]為真表示P1希望訪問臨界區，turn為1表示P1可以進入臨界區，P0等待 （進入區）進程P0的臨界區代碼CS0; //臨界區flag[0] = flase; //退出區進程P0的其他代碼；}While(true)}P1:{DO{flag[1] = true; //進入區turn = 0; //此時P1未進入臨界區，仍然允許P0進入臨界區（進入區）While (flag[0] && turn == 0); //flag[0]為真表示P0希望訪問臨界區，turn為0表示P0可以進入臨界區，P1等待 （進入區）進程P1的臨界區代碼CS1; //臨界區flag[1] = flase; //退出區進程P1的其他代碼；}While(true)}此算法可以完全正常工作。
?
2.硬件方法
?
信號量
信號量是一個確定的二元組（s,q），其中s是一個具有非負初值的整型變量，q是一個初始狀態為空的隊列。s表示系統中某類資源的數目，當其值大于0時，表示系統中當前可用資源的數目；當小于0時，其絕對值表示系統中因請求該類資源而被阻塞的進程數目。
P操作：先執行s=s-1；若s>=0，則該進程繼續運行；若s<0，則阻塞該進程，并將它插入該信號量的等待隊列中。相當于申請資源
V操作：先執行s=s+1；若s>0，則該進程繼續執行；若s<=0，則從該信號量等待隊列中移出第一個進程，使其變為就緒狀態并插入就緒隊列，然后再返回原進程繼續執行難。相當于釋放資源。
信號量的應用
1.實現進程同步
假設存在并發進程P1，P2.P1中有一條語句S1，P2中有一條語句S2，要求S1必須在S2之前執行。
semaphore N=0; //設置信號量并設置初始值為0P1() {...S1;V(N)... } P2() {...P(N)S2;... }2.實現進程互斥
semaphore N=1; //設置信號量并設置初始值為0P1() {...P(N);P1的臨界區代碼；V(N)... } P2() {...P(N)P2的臨界區代碼；V(N);... }經典同步問題
生產者-消費者問題
它描述的是一組生產者向一組消費者提供產品，它們共享要給有界緩沖區，生產者向其中投入產品，消費者從中取走產品。
Semaphore full=0; //滿緩沖區數目 Semaphore empty=n; //空緩沖區數目 Semaphore mutex=1; //對有界緩沖區進行操作的互斥信號量Producer() {while(true){Produce an imtem put in nextp; //nextp為臨時緩沖區P(empty);P(mutex);將產品放入緩沖池V(mutex);V(full);} }Consumer() {while(true){P(full); //申請一個滿緩沖區P(mutex); //申請使用緩沖區取出產品V(mutex); //緩沖池使用完畢，釋放互斥信號量V(empty); //增加一個空緩沖區Consumer the item in nextc; //消費掉產品} }?
信號量機制問題的解題步驟
管程
管程定義了一個數據結構和能為并發進程所執行的一組操作，這組操作能同步進程和改變管程中的數據。
管程具有以下基本特征
- 局部于管程的數據只能被局部于管程的過程所訪問。
- 一個進程只能通過調用管程內的過程才能進入管程的訪問共享數據。
- 每次僅允許一個進程在管程內執行某個內部過程，即進程互斥地通過調用內部過程進入管程。
- 局限于管程并僅能從管程內進行訪問的若干條件變量，用于區別各種不同的等待原因。
- 在條件變量上進行操作的兩個函數過程wait和signal。
?
死鎖
定義：當多個進程因競爭系統資源或相互通信而出于永久阻塞狀態時，若無外力作用，這些進程都將無法向前推進。這些進程中的每一個進程，均無限期地等待詞組進程中某個其他進程占有的、自己永遠無法得到的資源，這種現象叫死鎖。
死鎖產生的原因和必要條件
資源分類：可剝奪資源；不可剝奪資源
死鎖產生的原因：系統資源不足、進程推進順序不當。系統資源不足是產生死鎖的根本原因，進程推進不當是產生死鎖的重要原因。
死鎖產生的必要條件：互斥條件、不剝奪條件、請求與保持條件、環路等待條件。要產生死鎖，4個條件缺一不可，因此可以通過破話其中一個或幾個條件來避免死鎖的產生。
處理死鎖的基本方法
- 鴕鳥算法。不理睬死鎖。
- 預防死鎖。通過設置某些條件，區破壞產生死鎖的4個必要條件中的一個或幾個。
- 避免死鎖。在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而避免死鎖的產生。
- 檢測及解除死鎖。通過系統的檢測機構及時檢測出死鎖的發生，然后采取某種措施解成死鎖。
預防和避免的區別：
死鎖的預防方法中，總的來說都施加了較強的限制條件，雖然實現較為簡單，卻嚴重損害了系統性能。在避免死鎖的辦法中，所施加的條件較弱，可以獲得較好的系統性能。
死鎖的預防（嚴格）
4個條件的破壞
互斥條件：不大可能破壞。
不剝奪條件：對于一個已經獲得了某些資源的進程，若新的資源請求不能立即得到滿足，澤它必須釋放所有已經獲得的資源，以后需要資源時再重新申請。該策略實現比較復雜，且會增加系統開銷，降低系統吞吐量。通常不會用于剝奪資源后代價較大的場合，如打陰界。
請求與保持條件：為破壞請求與保持條件，可以采用預先靜態分配方法。預先靜態分配發要求進程再其運行之前一次性申請所需要的全部資源，再它的資源未滿足前不投入運行，一旦投入運行，這些資源就一直歸它所有，也不再提出其他資源請求。降低資源利用率，容易導致其他進程殘生“饑餓”現象。
環路等待條件：未了破壞環路等待條件，可以采用有序資源分配法。有序資源分配法時將系統中的所有資源都按類型賦予一個編號（如打印機為1，磁帶機為2），要求每一個進程均嚴格按照編號遞增的次序請求資源，同類資源一次申請完。造成資源浪費，增加程序復雜性。
死鎖的避免（相對寬松）
若在某一時刻，系統能按某種順序來為每個進程分配其所需的資源，直至最大需求，使每個進程都可順利完成，則稱此時的系統狀態為安全狀態，稱該序列為安全序列。
若某一時刻系統中不存在安全序列，則稱此時的系統狀態為不安全狀態。
PS：1.不安去狀態不是指系統中已經產生死鎖。處于不安全狀態的系統不會必然導致死鎖。
銀行家算法
簡單說就是分為以下步驟：
1，先看進程請求的資源是否小于或等于其所需的，是則進行，否則報錯
2.看進程請求的資源是否小于或等于可用的，是則進行，否則報錯
3.資源預分配
4.對于修改后的向量，調用安全性算法，安全則執行，否則讓進程等待，并恢復第三步中所改變的向量。
懶得打，網上找的
死鎖的檢測與解除
死鎖定理
可以用簡化資源分配圖的方法來檢測系統狀態S是否是死鎖狀態。簡化方法如下：
- 在資源分配圖中，找出一個既不阻塞又非孤立的進程結點Pi（即從進程集合中找到一個存在連接的邊，且資源申請數量小于系統中已有空閑資源數量的進程）。因進程Pi獲得了所需的資源，他能繼續運行直到完成，然后釋放器占有資源（相當于消去Pi的所有申請邊與分配邊，使之編程孤立的結點）。
- 在進程Pi釋放資源后，可以喚醒因等待這些資源而阻塞的進程，根據第一步的方法，進一步消去邊。
- 重復前兩步，若能使所有結點編程孤立結點，則稱改圖是可完全簡化的。
系統狀態S為死鎖的條件是：當且僅當S章臺的資源分配圖是不可完全簡化的，該定理稱為死鎖定理。
死鎖解除
剝奪資源。從其他進程中搶占足夠的資源給死鎖的進程以解除其死鎖狀態。
撤銷進程。撤銷一些進程，直到有足夠的資源分配給其他進程，解除死鎖狀態。
進程回退。讓一個或多個進程回退到足以回避死鎖的地步，進程回退時資源釋放資源。
死鎖與餓死
當等待四件給進程推進和響應帶來明顯影響時，則稱此時發生了進程饑餓，當進程饑餓到一定程度，進程所賦予的任務即使完成也不再具有實際意義時，稱該進程被餓死。
餓死與死鎖的聯系：二者都是由于競爭資源而引起的。
區別：
- 死鎖進程都出一等待狀態；忙時等待的進程并非處于等待狀態，但卻可能被餓死。
- 死鎖進程等待的時永遠不會釋放的資源；餓死進程等待的時會被釋放但卻不會分配給自己的資源，表現為等待時間沒有上界。
- 死鎖一定發生了循環等待，餓死則不然。
- 死鎖一定涉及多個進程，而饑餓或二四的進程可能只有一個。
?
?
?
?
?
?
總結
以上是生活随笔為你收集整理的计算机操作系统学习笔记----进程管理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： sencha app watch php
- 下一篇： GOLANG工厂模式、简单工厂模式、抽象