操作系統(tǒng)

進程

進程是程序的一次執(zhí)行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位，目的是為了更好地描述和控制程序的并發(fā)執(zhí)行。

進程特征

進程狀態(tài)

進程控制

進程的創(chuàng)建

過程：

• 為新進程分配一個唯一的進程標識號，并申請一個空白的 PCB，若申請失敗則創(chuàng)建失敗。

• 為新進程的程序和數(shù)據(jù)分配內存空間，若資源不足會進入阻塞態(tài)。

• 初始化 PCB，主要包括標志信息、處理機狀態(tài)信息、以及設置進程優(yōu)先級等。

• 若進程就緒隊列未滿，就將新進程插入就緒隊列，等待被調度運行。

進程的終止

進程終止包括：正常結束，表示進程已經完成并準備退出；異常結束，表示進程在運行時發(fā)生異常，程序無法繼續(xù)運行，例如非法指令，IO 故障等；外界干預，指進程因為外界請求而終止，例如操作系統(tǒng)干預等。

過程：

• 根據(jù)被終止進程的標識符，檢索 PCB，讀出該進程的狀態(tài)。
• 若被終止的進程處于執(zhí)行狀態(tài)，終止執(zhí)行，將處理機資源分配給其他進程。
• 若進程還有子進程，將所有子進程終止。
• 將該進程的全部資源歸還給父進程或操作系統(tǒng)，并將 PCB 從隊列刪除。

進程的阻塞與喚醒

正在執(zhí)行的進程由于等待的事件未發(fā)生，由系統(tǒng)執(zhí)行阻塞原語，由運行態(tài)變?yōu)樽枞麘B(tài)。

阻塞過程：

• 找到將要被阻塞進程的 PCB。
• 如果進程為運行態(tài)，保護現(xiàn)場并轉為阻塞態(tài)，停止運行。
• 把 PCB 插入相應事件的等待隊列，當被阻塞進程期待的事件發(fā)生時，由相關進程調用喚醒原語，將進程喚醒。

喚醒過程：

• 在該事件的等待隊列中找到進程對應的 PCB。
• 將其從等待隊列中移除，設置狀態(tài)為就緒態(tài)。
• 將 PCB 插入就緒隊列，等待調度程序調度。

進程切換

進程切換是指處理機從一個進程的運行轉到另一個進程上運行。

進程切換過程：

• 保存處理機上下文，包括程序計數(shù)器和其他寄存器。
• 更新 PCB 信息，并把 PCB 移入相應的阻塞隊列。
• 選擇另一個進程執(zhí)行并更新其 PCB。
• 更新內存管理的數(shù)據(jù)結構，恢復處理機上下文。

進程通信?

管道通信

Linux 里的 | 就是一個管道，功能是將前一個命令的輸出作為后一個命令的輸入。

管道通信中存儲空間是內核緩沖區(qū)，只允許一邊寫、另一邊讀，只要緩沖區(qū)有數(shù)據(jù)，進程就能讀出。寫進程會先將緩沖區(qū)寫滿才讓讀進程讀，當緩沖區(qū)還有數(shù)據(jù)時，寫進程不會往緩沖區(qū)寫數(shù)據(jù)。因此管道是半雙工通信，效率低，不適合進程間頻繁交換數(shù)據(jù)。

消息隊列

消息隊列是保存在內核中的消息鏈表，消息的發(fā)送方和接收方要約定好消息體的數(shù)據(jù)類型，每個消息體都是固定大小的存儲塊，不像管道是無格式的字節(jié)流。如果進程從消息隊列中讀取了消息體，內核就會把這個消息體刪除。消息隊列的通信效率高于管道，進程發(fā)送消息時，把數(shù)據(jù)放在消息隊列后就可以正常返回。

消息隊列不適合較大數(shù)據(jù)的傳輸，因為內核中每個消息體都有最大長度限制。此外，消息隊列通信存在數(shù)據(jù)拷貝開銷，進程寫數(shù)據(jù)到消息隊列時，會發(fā)生從用戶態(tài)拷貝數(shù)據(jù)到內核態(tài)的過程，讀取數(shù)據(jù)時，會發(fā)生從內核態(tài)拷貝數(shù)據(jù)到用戶態(tài)的過程。

共享內存

共享內存解決了消息隊列中用戶態(tài)與內核態(tài)間的數(shù)據(jù)拷貝問題，將虛擬地址空間映射到相同的物理內存，當某個進程寫數(shù)據(jù)時，另一個進程馬上就能看到，不需要拷貝，提高通信效率。

線程

線程是進程中的一個實體，是操作系統(tǒng)獨立調度和分配的基本單位，由線程 ID、程序計數(shù)器、寄存器集合和堆棧組成。引入線程是為了減少程序并發(fā)執(zhí)行的開銷，進一步提高操作系統(tǒng)的并發(fā)性能。

線程和進程的區(qū)別?

調度：進程是分配資源的基本單位，而線程是獨立調度的基本單位。

資源：進程擁有系統(tǒng)資源，而線程只有一點運行必需的資源。如果線程也是分配資源的單位，切換就需要較大開銷，引入沒有意義。

開銷：進程切換涉及當前 CPU 環(huán)境的保存和設置，但線程切換只需要保存和設置少量的寄存器容量。

地址空間：進程的地址空間互相獨立，同一進程的線程共享進程資源，進程內的線程對其他進程不可見。

通信：進程通信需要同步和互斥手段的輔助，保證數(shù)據(jù)一致性。線程可以直接讀寫進程數(shù)據(jù)段（全局變量）來進行通信。

線程實現(xiàn)

內核級線程 1:1 實現(xiàn)

內核通過操縱調度器對線程進行調度，并將線程的任務映射到處理器上。程序一般不會直接使用內核線程，而是使用內核線程的一種高級接口，輕量級進程，即通常意義上的線程。

優(yōu)點：當一個線程被阻塞時，允許其他線程繼續(xù)執(zhí)行。

缺點：代價相對較高，需要在用戶態(tài)和內核態(tài)來回切換。

用戶級線程 1:N 實現(xiàn)

從廣義上講，一個線程只要不是內核線程，就可以認為是用戶線程。狹義上的用戶線程指的完全建立在用戶空間的線程庫上，系統(tǒng)內核不能感知到用戶線程的存在及其是如何實現(xiàn)的。

優(yōu)點：由于線程管理在用戶空間進行，不需要切換到內核態(tài)，開銷小，支持大規(guī)模并發(fā)。

缺點：一個線程在使用內核服務時被阻塞，整個進程都會被阻塞。

混合方式 N:M 實現(xiàn)

混合模式下既存在用戶線程，也存在輕量級進程。用戶線程完全建立在用戶空間中，因此開銷依然很小，可以支持大規(guī)模并發(fā)。輕量級進程作為用戶線程和內核線程之間的橋梁，使用內核提供的線程調度功能及處理器映射，降低整個進程阻塞的風險。

死鎖?

死鎖就是指多個進程因為互相競爭資源而造成的一種互相等待的僵局，若無外力作用，這些進程都無法繼續(xù)向前推進。

死鎖的原因

不可剝奪資源數(shù)量的不足，如打印機，對可剝奪資源的競爭不會造成死鎖。

進程請求和釋放資源的順序不當，例如進程 P1 和 P2 分別占用資源 R1 和 R2，而此時 P1 和 P2 又分別申請資源 R2 和 R1。

信號量的使用不當，進程間彼此互相等待對方發(fā)來的消息，也會使進程無法推進。

必要條件

互斥條件：進程對資源的占有具有排它性，如果進程請求的資源已被占用，請求就會被阻塞。

不可剝奪條件：進程獲得的資源沒有使用完成前，不能被其它進程強行獲取，只能由占有它的進程主動釋放。

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

循環(huán)等待條件：存在一個進程資源的循環(huán)等待鏈，鏈中每個進程已經占有的資源同時是其他進程請求的資源。

死鎖處理

預防

• 破壞互斥條件

  允許系統(tǒng)資源共享，但有的資源不可能同時訪問，如打印機等臨界資源。

• 破壞不可剝奪條件

  允許剝奪其他進程已占有的資源，但釋放已獲得的資源可能會造成前一段工作的失效。

• 破壞請求和保持條件

  采用預先資源分配法，在進程運行前一次性分配它需要的所有資源，缺點是有些資源可能僅在運行初期或快結束時才使用。

• 破壞循環(huán)等待條件

  采用順序資源分配法， 給系統(tǒng)資源編號，規(guī)定每個進程必須按編號遞增的順序請求資源。

避免

同樣屬于事先預防，但并不是事先采取某種限制措施，而是動態(tài)地根據(jù)情況處理。

• 系統(tǒng)安全狀態(tài)

  不安全狀態(tài)可能會導致死鎖，如果一次分配不會導致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程，否則就讓進程等待。

  安全狀態(tài)是指系統(tǒng)能按照某種進程推進順序為每個進程分配資源，直到滿足每個進程對資源的需求。

• 銀行家算法

  把操作系統(tǒng)視為銀行家，資源視為資金，進程向操作系統(tǒng)申請資源相當于用戶向銀行家貸款。操作系統(tǒng)按照規(guī)則為進程分配資源，當進程首次申請資源時，要測試系統(tǒng)現(xiàn)存資源能否滿足其最大需求量，可以則按申請量分配，否則推遲分配。

  當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占有的資源數(shù)與申請的資源數(shù)之和是否超過該進程對資源的最大需求量，如果超過則拒絕分配，否則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，如果滿足則按申請量分配，否則推遲分配。

檢測

系統(tǒng)死鎖可用資源分配圖描述，圓圈表示進程，框表示資源。從進程到資源的有向邊是請求邊，從資源到進程的邊是分配邊。

簡化資源分配圖可以檢測系統(tǒng)狀態(tài)是否為死鎖狀態(tài)。在資源分配圖中，找出既不阻塞也不孤立的進程，消去它的所有請求邊和分配邊，使之成為孤立的點。如果系統(tǒng)狀態(tài)不可被完全簡化，那么代表死鎖。

解除

• 資源剝奪法

  掛起某些死鎖進程，搶占其資源，分配給其它死鎖進程。

• 撤銷進程法

  強制撤銷部分甚至全部死鎖進程，可以按進程優(yōu)先級和撤銷代價進行。

• 進程回退法

  讓一個或多個進程回退到足以避免死鎖的地步，要求系統(tǒng)保持進程的歷史信息，設置還原點。