ui

一、進程

程序和進程

程序：是靜態的，編譯好的二進制文件，存儲在磁盤中，.exe程序

進程：是動態的，是程序的一次執行過程

進程控制塊（PCB）

• 進程id。系統中每個進程有唯一的id，在C語言中用pid_t類型表示，其實就是一個非負整數。
• 進程的狀態，有就緒、運行、掛起、停止等狀態。
• 進程切換時需要保存和恢復的一些CPU寄存器。
• 描述虛擬地址空間的信息。
• 描述控制終端的信息。
• 當前工作目錄（Current Working Directory）。
• umask掩碼。
• 文件描述符表，包含很多指向file結構體的指針。
• 和信號相關的信息。
• 用戶id和組id。
• 會話（Session）和進程組。
• 進程可以使用的資源上限（Resource Limit）。

進程的組成

PCB：

• 進程描述信息
• 進程控制和管理信息
• 資源分配清單
• 處理機相關信息

程序段：程序的代碼(指令序列)
數據段：運行過程中產生的各種數據 (如:程序中定義的變量)

進程的特征

• 動態性：進程是程序的一次執行過程，是動態地產生、變化和消亡的
• 并發性：內存中有多個進程實體，各進程可并發執行
• 獨立性：進程是能獨立運行、獨立獲得資源、獨立接受調度的基本單位
• 異步性：各進程按各自獨立的、不可預知的速度向前推進,操作系統要提供"進程同步機制"來解決異步問題
• 結構性：每個進程都會配置一個PCB。 結構上看，進程由程序段、數據段、PCB組成

進程的狀態與轉換

進程基本的狀態有5種。分別為運行狀態、就緒狀態、阻塞狀態、創建狀態、終止狀態。

創建態：進程正在被創建時，它的狀態是“創建態”，在這個階段操作系統會為進程分配資源、初始化PCB。

就緒態：當進程創建完成后，便進入“就緒態”，處于就緒態的進程已經具備運行條件，但由于沒有空閑CPU，就暫時不能運行。

運行態：如果一個進程此時在CPU上運行，那么這個進程處于“運行態”。CPU會執行該進程對應的程序（執行指令序列）

阻塞態：在進程運行的過程中，可能會請求等待某個事件的發生（如等待某種系統資源的分配，或者等待其他進程的響應）。在這個事件發生之前，進程無法繼續往下執行，此時操作系統會
讓這個進程下CPU，并讓它進入“阻塞態”當CPU空閑時，又會選擇另一個“就緒態”進程上CPU運行

終止態：一個進程可以執行 exit 系統調用，請求操作系統終止該進程。此時該進程會進入“終止態”，操作系統會讓該進程下CPU，并回收內存空間等資源，最后還要回收該進程的PCB。當終止進程的工作完成之后，這個進程就徹底消失了

進程狀態的轉換

就緒態->運行態：進程被調度
運行態-> 就緒態:時間片到，或CPU被其他高優先級的進程搶占
運行態-> 阻塞態:等待系統資源分配，或等待某事件發生(主動行為)
阻塞態->就緒態：資源分配到位，等待的事件發生(被動行為)
創建態-> 就緒態：系統完成創建進程相關的工作
運行態->終止態：進程運行結束，或運行過程中遇到不可修復的錯誤

進程的組織

鏈接方式

索引方式

進程的控制

進程的創建

步驟：

• 申請空白PCB
• 為新進程分配所需資源
• 初始化PCB
• 將PCB插入就緒隊列

引起進程創建的事件

• 用戶登錄：分時系統中，用戶登錄成功，系統會建立為其建立-個新的進程

• 作業調度：多道批處理系統中，有新的作業放入內存時，會為其建立-個新的進程

• 提供服務：用戶向操作系統提出某些請求時，會新建一個進程處理該請求

• 應用請求：由用戶進程主動請求創建一個子進程

進程的終止

步驟：

• 從PCB集合中找到終止進程的PCB
• 若進程正在運行，立即剝奪CPU，將CPU分配給其他進程
• 終止其所有子進程（進程間的關系是樹形結構），將該進程擁有的所有資源歸還給父進程或操作系統
• 刪除PCB

引起進程終止的事件：

• 正常結束（進程自己請求終止(exit 系統調用)
• 異常結束（整數除以0、非法使用特權指令，然后被操作系統強行殺掉）
• 外界干預（Ctrl+Alt+delete，用戶選擇殺掉進程）

進程阻塞

步驟：

• 找到要阻塞的進程對應的PCB
• 保護進程運行現場，將PCB狀態信息設置為“阻塞態"，暫時停止進程運行
• 將PCB插入相應事件的等待隊列

引起進程阻塞的事件：

• 需要等待系統分配某種資源
• 需要等待相互合作的其他進程完成工作

進程喚醒

• 在事件等待隊列中找到PCB
• 將PCB從等待隊列移除，設置進程為就緒態
• 將PCB插入就緒隊列，等待被調度

引起進程喚醒的事件：

• 等待的事件發生

進程切換

步驟：

• 將運行環境信息（進程上下文）存入PCB
• PCB移入相應隊列
• 選擇另一個進程執行，并更新其PCB
• 根據PCB恢復新進程所需的運行環境

引起進程切換的事件：

• 當前進程時間片到
• 有更高優先級的進程到達
• 當前進程主動阻塞
• 當前進程終止

進程通信

共享存儲

在linux中，使用共享內存的方式來實現共享內存。要讓各個進程互斥的進行，可以采用加鎖或者pv操作。

消息傳遞

進程間的數據交換以格式化的消息（Message）為單位。進程通過操作系統提供的“發送消息/接收消息”兩個原語進行數據交換。

步驟：

• 1：進程p發送消息
• 2：通過消息隊列寫入數據，通常需要從進程拷貝到內核（進程X的pcb消息隊列中）。
• 3：進程X從內核拷貝到進程
• 4：然后再從進程中X拷貝到輸出文件

管道通信

• 管道只能采用半雙工通信，某一時間段內只能實現單向的傳輸。如果要實現雙向同時通信，則需要設置兩個管道。
• 各進程要互斥地訪問管道（由操作系統實現）
• 當管道寫滿時，寫進程將阻塞，直到讀進程將管道中的數據取走，即可喚醒寫進程。
• 當管道讀空時，讀進程將阻塞，直到寫進程往管道中寫入數據，即可喚醒讀進程。
• 管道中的數據一旦被讀出，就徹底消失。因此，當多個進程讀同一個管道時，可能會錯亂。對此，通常有兩種解決方案：①一個管道允許多個寫進程，一個讀進程②允
  許有多個寫進程，多個讀進程，但系統會讓各個讀進程輪流從管道中讀數據。

二、線程

什么是線程

線程可以理解為“輕量級進程”。線程是一個基本的CPU執行單元，也是程序執行流的最小單位。引入線程之后，不僅是進程之間可以并發，進程內的各線程之間也可以并發，從而進一步提升了系統的并發度，使得一個進程內也可以并發處理各種任務（如QQ視頻、文字聊天、傳文件）引入線程后，進程只作為除CPU之外的系統資源的分配單元（如打印機、內存地址空間等都是分配給進程的）。線程則作為處理機的分配單元。

線程的屬性

• 線程是處理機調度的單位
• 多CPU計算機中，各個線程可占用不同的CPU
• 每個線程都有一個線程ID、線程控制塊(TCB)
• 線程也有就緒、阻塞、運行三種基本狀態
• 線程幾乎不擁有系統資源
• 同一進程的不同線程間共享進程的資源
• 由于共享內存地址空間，同-進程中的線程間通信甚至無需系統干預
• 同一進程中的線程切換，不會引起進程切換
• 不同進程中的線程切換，會引起進程切換
• 切換同進程內的線程，系統開銷很小
• 切換進程，系統開銷較大

線程的實現

用戶級線程

從代碼的角度看，線程其實就是一段代碼邏輯。上述三段代碼邏輯上可以看作三個“線程”。
while 循環就是一個最弱智的“線程庫”，線程庫完成了對線程的管理工作（如調度）。

1. 用戶級線程由應用程序通過線程庫實現，所有的線程管理工作都由應用程序負責（包
   括線程切換）
2. 用戶級線程中，線程切換可以在用戶態下即可完成，無需操作系統干預。
3. 在用戶看來，是有多個線程。但是在操作系統內核看來，并意識不到線程的存在。“用戶級線程”就是“從用戶視角看能看到的線程”

優缺點
優點：用戶級線程的切換在用戶空間即可完成，不需要切換到核心態，線程管理的系統
開銷小，效率高
缺點：當一個用戶級線程被阻塞后，整個進程都會被阻塞，并發度不高。多個線程不可
在多核處理機上并行運行。

內核級線程

1. 內核級線程的管理工作由操作系統內核完成。
2. 線程調度、切換等工作都由內核負責，因此內核級線程的切換必然需要在核心態下才
   能完成。
3. 操作系統會為每個內核級線程建立相應的TCB（Thread Control Block，線程控制塊），
   通過TCB對線程進行管理。“內核級線程”就是“從操作系統內核視角看能看到的線程”

優缺點
優點：當一個線程被阻塞后，別的線程還可以繼續執行，并發能力強。多線程可在多核
處理機上并行執行。
缺點：一個用戶進程會占用多個內核級線程，線程切換由操作系統內核完成，需要切換到
核心態，因此線程管理的成本高，開銷大。

多線程模型

一對一模型：一個用戶級線程映射到一個內核級線程。每個用戶進程有與用戶級線程同
數量的內核級線程。
優點：當一個線程被阻塞后，別的線程還可以繼續執行，并發能力強。多線程可在多核
處理機上并行執行。
缺點：一個用戶進程會占用多個內核級線程，線程切換由操作系統內核完成，需要切換到
核心態，因此線程管理的成本高，開銷大

多對一模型：多個用戶級線程映射到一個內核級線程。且一個進程只被分配一個內核級
線程。
優點：用戶級線程的切換在用戶空間即可完成，不需要切換到核心態，線程管理的系統
開銷小，效率高
缺點：當一個用戶級線程被阻塞后，整個進程都會被阻塞，并發度不高。多個線程不可
在多核處理機上并行運行

多對多模型：n 用戶及線程映射到 m 個內核級線程（n >= m）。每個用戶進程對應 m 個內核級線程。克服了多對一模型并發度不高的缺點（一個阻塞全體阻塞），又克服了一對一模型中一個用戶進程占用太多內核級線程，開銷太大的缺點

處理機調度

高級調度

高級調度（作業調度）。按一定的原則從外存的作業后備隊列中挑選一個作業調入內存，并創建進程。每個作業只調入一次，調出一次。作業調入時會建立PCB，調出時才撤銷PCB。

低級調度

低級調度（進程調度/處理機調度）：按照某種策略從就緒隊列中選取一個進程，將處理機分配給它。

中級調度

內存不夠時，可將某些進程的數據調出外存。等內存空閑或者進程需要運行時再重新調入內存。暫時調到外存等待的進程狀態為掛起狀態。被掛起的進程PCB會被組織成掛起隊列
中級調度（內存調度）—按照某種策略決定將哪個處于掛起狀態的進程重新調入內存。一個進程可能會被多次調出、調入內存，因此中級調度發生的頻率要比高級調度更高。

三種調度的聯系、對比

調度算法

先來先服務（FCFS）

短作業優先

高響應比優先

時間片輪轉

優先級調度算法

多級反饋隊列調度算法

三、進程同步和互斥

進程的同步：并發性帶來了異步性，有時需要通過進程同步解決這種異步問題。有的進程之間需要相互配合地完成工作，各進程的工作推進需要遵循一定的先后順序。

進程互斥：對臨界資源的訪問，需要互斥的進行。即同一時間段內只能允許一個進程訪問該資源

臨界資源分為四個部分：

• 進入區，檢查是否可進入臨界區， 若可進入，需要"上鎖”
• 臨界區，訪問臨界資源的那段代碼
• 退出區，負責"解鎖"
• 剩余區，其余代碼部分

需要遵循的原則：

• 空閑讓進，臨界區空閑時， 應允許一個進程訪問
• 忙則等待，臨界區正在被訪問時，其他試圖訪問的進程需要等待
• 有限等待，要在有限時間內進入臨界區，保證不會饑餓
• 讓權等待，進不了臨界區的進程，要釋放處理機，防止忙等

四、死鎖

死鎖：各進程互相等待對方手里的資源，導致各進程都阻塞，無法向前推進的現象
饑餓：由于長期得不到想要的資源，某進程無法向前推進的現象。
死循環：某進程執行過程中一直跳不出某個循環的現象。

死鎖產生的必要條件

• 互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖
• 不剝奪條件：進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。
• 請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。
• 循環等待條件：存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求。

預防死鎖

靜態策略

破壞互斥條件

互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖。

如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態。比如: SPOOLing技術。操作系統可以采用 SPOOLing 技術把獨占設備在邏輯上改造成共享設備。比如，用SPOOLing技術將打印機改造為共享設備

破壞不剝奪條件

不剝奪條件：進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。

• 方案一：當某個進程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。
• 方案二：當某個進程需要的資源被其他進程所占有的時候，可以由操作系統協助，將想要的資源強行剝奪。這種方式一般需要考慮各進程的優先級（比如：剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的進程使用）

破壞請求和保持條件

請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。

可以采用靜態分配方法，即進程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運行。一旦投入運行后，這些資源就一直歸它所有，該進程就不會再請求別的任何資源了。

破壞循環等待條件

循環等待條件：存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求。
可采用順序資源分配法。首先給系統中的資源編號，規定每個進程必須按編號遞增的順序請求資源， 同類資源（即編號相同的資源）一次申請完。

原理分析：一個進程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規則，已持有大編號資源的進程不可能逆向地回來申請小編號的資源，從而就不會產生循環等待的現象。

動態策略

安全序列

所謂安全序列，就是指如果系統按照這種序列分配資源，則每個進程都能順利完成。只要能找出一個安全序列，系統就是安全狀態。當然，安全序列可能有多個。

如果分配了資源之后，系統中找不出任何一個安全序列，系統就進入了不安全狀態。這就意味著之后可能所有進程都無法順利的執行下去。當然，如果有進程提前歸還了一些資源，那系統也有可能重新回到安全狀態，不過我們在分配資源之前總是要考慮到最壞的情況。

如果系統處于安全狀態，就一定不會發生死鎖。如果系統進入不安全狀態，就可能發生死鎖（處于不安全狀態未必就是發生了死鎖，但發生死鎖時一定是在不安全狀態）因此可以在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求。這也是“銀行家算法”的核心思想

銀行家算法

死鎖的檢測和解除

死鎖的檢測

為了能對系統是否已發生了死鎖進行檢測，必須：

• 用某種數據結構來保存資源的請求和分配信息；
• 提供一種算法，利用上述信息來檢測系統是否已進入死鎖狀態

死鎖的解除

解除死鎖的主要方法有：

1. 資源剝奪法。掛起（暫時放到外存上）某些死鎖進程，并搶占它的資源，將這些資源分配給其他的死鎖進程。但是應防止被掛起的進程長時間得不到資源而饑餓。
2. 撤銷進程法（或稱終止進程法）。強制撤銷部分、甚至全部死鎖進程，并剝奪這些進程的資源。這種方式的優點是實現簡單，但所付出的代價可能會很大。因為有些進程可能已經運行了很長時間，已經接近結束了，一旦被終止可謂功虧一簣，以后還得從頭再來。
3. 進程回退法。讓一個或多個死鎖進程回退到足以避免死鎖的地步。這就要求系統要記錄進程的歷史信息，設置還原點。