特徵

並發

並發是指宏觀上在一段時間內能夠同時運行多個程序，而並行則指同一個時刻能運行多個指令。

並行需要硬體支持，如多流水線或者多處理器。

操作系統通過引入進程和線程，使得程序能夠並發運行。

共享

共享是指系統的資源可以被多個並發進程共同使用。

有兩種共享方式：互斥共享和同時共享。

互斥共享的資源稱為臨界資源，例如印表機等，在同一時間只允許一個進程訪問，需要同步機制來實現對臨界的訪問。

虛擬

虛擬技術把一個物理實體轉換為多個邏輯實體。

主要有兩種虛擬技術：時分復用技術和空分復用技術。

多個進程能在同一個處理器上並發使用時分復用技術，讓每個進程輪流佔有處理器

非同步

非同步指進程不是一次性完成的，而是走走停停，以不可知的速度向前推進。

進程管理

進程與線程

進程

進程是資源分配的基本單位。

進程式控制制塊（Process Control Block，pcb）描述進程的基本信息與運行狀態，所謂的創建進程和撤銷進程，都是指對PCB的操作。

線程

線程是獨立調度的基本單位。

一個進程可以有多個線程，它們共享進程資源。

區別

1、擁有資源

進程是資源分配的基本單位，但是線程不用有資源，線程可以訪問隸屬於進程的資源。

2、調度

3、系統開銷

4、通信

進程調度演算法

不同環境的調度演算法目標不同，因此需要針對不同環境來討論調度演算法。

批處理系統

批處理系統沒有太多的用戶操作，在該系統中，調度演算法目標是保證吞吐量和周轉時間（從提交到終止的時間）

先來先服務

按照請求的順序進行調度。

有利於長作業，但不利於短作業，因此短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。

短作業先執行

按估計運行時間最短的順序進行調度。

長作業可能會被餓死，處於一直等待短作業執行完畢的狀態。因此如果一直有短作業到來，那麼長作業永遠得不到調度。

響應比高優先調度演算法

是對FCFS和SJF的一種綜合平衡，FCFS只考慮作業的等待時間，而SJF只考慮作業的運行時間，這兩種方式在極端情況下都會帶來不便，HRN調度策略同時考慮每個策略的等待時間跟運行時間，從中選出響應比最高的作業。響應比R = (W + T) / T = 1 + W/T。其中T表示該作業估計得執行時間，W為作業在後備狀態隊列的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中的R最大者執行。這樣，即使長作業，隨著等待時間的增加，W / T也會隨著增加，也就有機會調度執行。

互動式系統

優先權調度演算法

分為靜態優先權跟動態優先權為每個進程分配一個優先權，按照優先權進行調度。為了防止優先順序低的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先順序。

輪轉法

也叫時間片輪轉，將所有就緒進程按FCFS的原則排成一個隊列，每次調度時，把cpu分配給首進程，讓該進程執行一個時間片。當時間片用完時，由定時器發出時間中斷，調度程序便停止該進程的運行，並將它運行送就緒隊列的末尾，同時將cpu分配給隊首的進程，時間片輪轉演算法的效率和時間片大小有很大關係，因為進程切換要保存進程的信息並且載入新進程的信息，如果時間片太小，會導致進程切換得太頻繁，在進程切換上就會花費過多的時間。

進程同步

臨界區

對臨界資源進行訪問的那段代碼稱為臨界區。

為了互斥訪問臨界資源，每個進程在進入臨界區之前，需要先進行檢查。

// entry section
// critical section;
// exit section

同步與互斥

• 同步：多個進程按一定順序執行。
• 互斥：多個進程同一時刻只有一個進程能夠進入臨界區。

信號量

信號量(Semaphore)是一個整形變數，可以對其執行down和up操作，也就是常見的P和V操作。

• down：如果信號量大於0，執行-1操作，如果信號量等於0，進程睡眠，等待信號量大於0。
• up：對信號量執行+1操作，喚醒睡眠的進程讓其完成down操作。

down和up操作需要被設計成原語，不可分割，通常的做法是執行這些操作時候屏蔽中斷。

如果信號量的取值只能0或者1，那麼久成為了互斥量，0表示臨界區已經加鎖，1表示臨界區解鎖。

管程

管程有一個重要的特性：在一個時刻只能有一個進程使用管程，進程在無法繼續執行的時候不能一直佔有管程，否則其他進程永遠不能使用管程。

管程引入了條件變數以及相關操作，wait()和signal()來實現同步操作。對條件變數執行wait()操作會導致調用進程阻塞，把管程讓出來給另一個進程持有。signal()操作用來喚醒被阻塞的進程。

進程通信

進程同步跟通信的區別：

• 進程同步：控制多個進程按照一定順序執行。
• 進程通信：進程間傳遞信息。

進程通信是一種手段，而進程同步是一種目的。也可以說，為了能夠達到進程同步的目的，需要讓進程進行通信，傳輸一些進程同步所需要的信息。

管道

管道是通過pipe函數創建的，df[0]用於讀，df[1]用於寫。

它具有一下限制：

• 只支持半雙工通信。
• 只能在父子進程中使用。

FIFO

也稱為命名管道，去除了管道只能在父子進程中使用的限制。

消息隊列

相比於FIFO，消息隊列具有以下特點：

• 消息隊列可以獨立於讀寫進程存在，從而避免了FIFO中同步管道的打開和關閉可能產生的困難。
• 避免了FIFO的同步阻塞問題，不需要進程自己提供同步方法。
• 讀進程可以根據消息類型選擇地接收信息，而不像FIFO那樣只能默認地接收。

信號量

它是一個計數器，用於為多個進程提供共享數據對象的訪問。

共享內存

允許多個進程共享一個給定的存儲區。因為數據不需要在進程之間複製，所以這個最快的一種IPC。

需要使用信號量來同步對共享存儲的訪問。

多個進程將同一個文件映射到它們的地址空間從而實現共享內存。另外XSI共享內存不是使用文件，而是使用內存的匿名段。

套接字

與其他通信機制不同的是，它可以用於不同機器間的通信。

死鎖

產生死鎖的主要原因

• 系統資源不足。
• 進程運行推進的順序不當。
• 資源分配不當等。

死鎖的四個必要條件

• 互斥：每個資源只能同一時間只能給一個進程使用。、
• 佔有且等待：一個進程因請求資源阻塞時，對已有資源保持不放。
• 不可搶佔：進程已獲得的資源，在未使用完成之前不能強行剝奪。
• 循環等待：兩個或兩個以上進程之間形成一種頭尾相接的循環等待資源關係。

這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件就必然成立，而只要上述條件之一不成立，就不會發生死鎖。

死鎖的解除與預防

理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。所以在系統統計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配演算法，避免進程永久佔據系統資源。此外也要預防進程處於等待狀態得情況下佔用資源。因此，對資源的分配要給予合理的規劃。

操作系統內存管理

虛擬內存

• 虛擬內存的目的是為了讓物理內存擴充成更大的邏輯內存，從而讓程序獲得更多的內存。
• 為了更好的管理內存，操作系統將內存抽象成地址空間。每個程序擁有自己的地址空間，這個地址空間被分割成多塊，每塊稱為一頁。這些也被映射到物理內存，但不需要映射到連續的物理內存，也不需要所有的也都必須在物理內存中。當程序引用到不在物理內存的頁時，由硬體執行必要的映射，將確實部分裝入物理內存並重新執行失敗的指令。

用戶態跟內核態

內核態跟用戶態是操作系統的兩種運行級別，intel cpu提供Ring0 - Ring3四種級別的運行模式，Ring0級別最高，Ring3級別最低，其中Ring0是留給操作系統代碼，設備驅動代碼使用的，它們工作系統和心態；而Ring3則給普通的用戶程序使用，它們工作在用戶態。

運行處理器的和心態代碼不受任何控制，可以自由地訪問任何有效地址。而運行於用戶態的代碼則要受到處理器的諸多檢查，它們只能訪問映射表其地址空間的頁表項規定的用戶態可訪問的頁面的虛擬地址。

當一個任務執行系統調用而陷入內核代碼執行時，我們就稱為進程處於內核運行態（內核態）。

當進程正在執行自己代碼時，則稱其處於用戶運行態（用戶態）。

當CPU處於內核態，可以隨意進入用戶態，而當CPU處於用戶態時，用戶從用戶態切換到內核態只有在系統調用和中斷兩種情況下發生。

內核線程和用戶線程

內核線程

特點：

• 由內核負責調度，一個內核線程處於阻塞狀態時不影響其他的內核線程，因為它是調度的基本的單位。
• 這些線程可以在全系統內進行資源的競爭
• 內核空間內為每一個內核支持的線程設置了一個線程式控制制塊(TCB)，內核根據該控制塊，感知線程的存在，並進行控制，只是創建、調度的開銷要比進程小。
• 內核線程由內核控制，當線程進行切換到時候，由用戶態轉為內核態，切換完畢要從內核態轉為用戶態，即存在用戶態和內核態之間的轉換。

優點：

• 在多處理器系統中，內核能夠同時調度同一進程中多個內核線程並執行到多個處理器中，如果進程中的一個線程被阻塞，內核可以調度到同一個進程中的另一線程。

缺點：

• 即使CPU在同一個進程的多個線程之間切換，也需要進入內核態，因此起速度和效率不如用戶線程

用戶線程

• 用戶線程在用戶空間實現，內核並不知道用戶線程，內核的調度對象和傳統進程一樣，還是進程（用戶進程）本身。
• 不需要內核支持而在用戶程序中實現的線程，其不依賴於操作系統核心，應用進程利用線程庫提供創建、同步、調度和管理線程的函數來控制用戶線程。
• 內核資源的分配仍然按照進程（用戶進程）進行分配，各個用戶線程只能在進程內競爭資源
• 用戶線程的由用戶態程序自己控制，不需要內核干涉，少了進出內核態的消耗，但不能很好的利用多核CPU
• 每個用戶線程並不具有自身的縣城上下文，因此，就線程的同時執行而言，任意給定時刻每個進程只能由一個線程執行，而且只有一個處理器內核會被分配給該進程。

優點：

• 線程切換無需進入內核，故切換開銷小

缺點：

• 系統調用的阻塞問題：對應用程序來講，同一進程中只能有一個線程在運行，一個線程的阻塞將導致整個進程中所有線程的阻塞，由於這裡的處理器時間片分配是以進程為基本單位，所以每個線程的執行時間相對減少

內核線程和用戶線程的聯繫

一對一模型：

• 每個用戶線程被映射一個內核線程，用戶線程在其生命期內都會被綁定到內核線程，一旦用戶線程終止，兩個線程都將離開系統。

弊端：

• 內核線程的數量有限
• 內核線程的調度開銷比較大

混合線程模型：

多對一：

• 多個用戶線程被映射到一個內核線程
• 多對一模型線程的切換速度要快很多（線程切換由用戶代碼來執行）

弊端：

• 如果某一個用戶線程阻塞，所有的線程都無法執行

多對多：

• 對上述兩種模型進行結合，即將多個用戶線程映射到不止一個內核線程中去
• 多對多模型對用戶線程的數量沒有什麼限制，在多處理器系統上也會有一定的性能提升，不過提升的幅度比不上一對一模型。

本內容參考：

死鎖的產生原因以及四個必要條件計算機操作系統內核線程與用戶線程的一點小總結 《程序員的自我修養》·筆記

推薦閱讀：

相关文章