本來不打算在現在這個階段來看操作系統書籍的，但是入手一本《iOS逆向工程》，看它需要MAC OS的相關知識，便入手了一本《深入解析 MAC OS X & IOS 操作系統》，發現看它需要操作系統的相關知識，所以有了這些筆記，果然，no zuo no die。

 

1、進程

一個進程就是一個正在運行的程序，它有自己的地址空間，在進程內的所有線程共享這個進程的地址空間，也就是說，共享這個進程的資源，包括程序計數器、寄存器和變量的當前值。

在單核計算機年代，任何多道程序設計系統中，CPU由一個進程快速切換到另一個進程，使得每個進程在1s內各自運行幾十毫秒到幾百毫秒。嚴格的說，在某一個瞬間，CPU只能運行一個進程，但在1s期間，它可能運行多個進程，這樣就產生了並行的錯覺，在這個章節，默認講解的是單核計算機。

由於CPU在各個進程之間來回快速切換，所以每個進程其執行速度都是不確定的，而且當同一進程再次運行時，其運算速度通常也不可再現。每一個進程都是一個獨立的實體，有其自己的程序計數器和內部狀態，但是進程之間是可以相互作用的，一個進程的輸出結果可以作為另一個進程的輸入。

當一個進程在邏輯上不能繼續運行時，它就會被堵塞，典型的例子是它在等待可以使用的輸入。還會存在這樣的情況：一個概念上能夠運行的進程被迫停止，因為操作系統調用另一個進程占用了CPU。（例如，當一個進程從設備文件讀取數據時，如果沒有有效的輸入存在，則進程會被自動阻塞）

 

進程表：為了實現進程模型，操作系統維護著一張表格（數組），即進程表，每個進程占用一個進程表項。該表保存了進程狀態的重要信息，包括程序計數器、堆棧指針、內存分配狀況、所打開文件的狀態、賬號和調度信息，以及其他在進程由運行態轉換到就緒態或者堵塞態時必須保存的信息，從而保證該進程隨後能再次啟動，就像從未被中斷過一樣。

運行態：該時刻進程實際占用CPU

就緒態：可運行，但因為其他進程正在運行而暫時停止

阻塞態：除非某種外部事件發生，否則進程不能運行

 

多道程序設計模型：采用多道程序設計可以提高CPU的利用率。嚴格的說，如果進程用於計算的平均時間是進程在內存中停留時間的百分之二十，且內存中同時有五個進程，則CPU一直將滿負載運行，然而這個模型在現實中過於樂觀，因為它假設這五個進程不會同時等待I/O。

更好的模型是從概率的角度來看待CPU的利用率的，假設一個進程等待I/O操作的時間與其停留在內存中的時間比為p，當內存中有n個進程時，則所有n個進程都在等待I/O（CPU空轉）的概率是p的n次方，所有可以得到CPU的利用率：

CPU的利用率 = 1 - p^n；

 

 

2、線程

為什麼需要多線程？主要原因是在一個進程中會同時發生著多種活動， 其中某些活動隨著時間的推移會被堵塞，通過將這些活動分解成可以准並行運行的多個順序線程，程序設計模型會變得更簡單。由於線程比進程更輕量級，所有它比進程更容易創建和撤銷。

進程之間各自空間地址不同，但是同一個進程裡面的線程，它們共享著同一個空間地址和所有可用數據的能力。

還有一個原因就是性能方面的問題，若多個線程是CPU密集型的，那麼並不能獲得性能上的加強，但是如果存在大量的計算和大量的I/O處理，擁有多個線程允許這些活動彼此重疊進行，從而會加快應用程序執行的速度。

線程中有一個程序計數器，用來記錄接著要執行哪一條指令；有寄存器，用來保存線程當前的工作變量；還有一個堆棧，用來記錄執行歷史，其中每一幀保存了一個已調用但還沒有從中返回的過程。

盡管線程必須在某個進程中執行，但是線程和它的進程是不同的概念，並且可以分別處理。進程用於把資源集中到一起，而線程則是在CPU上被調度執行的實體。

線程與進程一樣，也可以處於若干狀態中的任何一個：運行、堵塞、就緒、終止。正在運行的線程擁有CPU並且是活躍的，被堵塞的線程正在等待某個釋放它的事件，就緒線程可被調度運行，並且只要輪到它就可以很快運行，線程狀態之間的轉化與進程是一致的。

認識到每個線程有自己的堆棧很重要，每個線程堆棧都有一幀，供各個被調用但是還沒從中返回的過程使用。在該幀中存放了相應過程的局部變量以及過程調用完成之後使用的返回地址。例如，如果過程x調用過程y，而y又調用z，那麼當z執行時，供x、y、z使用的幀都會存在堆棧中。通常每個線程會調用不同的過程，從而有一個各自不同的執行歷史，這就是為什麼每個線程都有自己的堆棧的原因。

 

3、進程間通信

進程通常需要與其他進程通信，但可能會產生一些問題。

 

a、競爭條件

在操作系統中，協作的進程可能共享一些彼此都能讀寫的公共存儲區，這個公共存儲區可能在內存中，也可能是一個共享文件。當兩個或者多個進程讀寫某些共享資源，而最終結果取決於進程運行的精確時序，成為競爭條件。

b、臨界區

 怎樣避免競爭條件？實際上凡是涉及多個進程讀寫某一共享資源的情況，關鍵是要找出某種途徑來組織多個線程同時讀寫共享的資源。換而言之，我們需要的是互斥，即以某種手段確保當一個進程在使用一個共享變量或文件時，其他進程不能做同樣的操作。

我們把對共享內存進行訪問的程序片段稱之為臨界區。如果我們能夠適當的安排，使得兩個進程不可能同時處於臨界區中，就能夠避免競爭條件。

對於一個好的解決方案，要滿足下面的條件：

任何兩個進程不能同時處於其臨界區

不應對CPU的速度和數量做任何假設

臨界區外運行的進程不能阻塞其他進程

不得使進程無限期等待進入臨界區

c、忙等待的互斥

 屏蔽中斷：

在單處理器中，最簡單的辦法是使每個進程在剛剛進入臨界區後立即屏蔽所有中斷，並在就要離開之前再打開中斷。屏蔽中斷後，時鐘中斷也被屏蔽，CPU只有發生時鐘中斷或其他中斷時才會進行進程切換，這樣，在屏蔽中斷後CPU將不會被切換到其他進程。於是，當某個進程屏蔽中斷之後，它就可以檢查和修改共享內存，而不必擔心其他進程介入。

這個方案並不好，因為把屏蔽中斷的權利交給用戶進程是不明智的。如果一個進程屏蔽中斷後不再打開，整個系統可能會因此而終止。如果是多處理器系統（即多核CPU），則屏蔽中斷僅僅對執行disable指令的那個CPU有效，其他CPU將繼續運行，並可以訪問共享內存。

屏蔽中斷對於操作系統本身而言是一項很有用的技術，但是對於用戶進程則不是一種合適的通用互斥機制。

 

鎖變量：

設想有一個共享變量，其初始值為0，當一個進程想進入臨界區時，它首先測試這把鎖，如果該鎖值為0，則進程進入臨界區，並把鎖設置為1。如果該鎖為1，那麼進程將等待直至其值變為0，於是，0表示臨界區內沒有進程，1表示已經有某個進程進入臨界區。

但是，這種想法是有疏漏的，假設一個進程讀出鎖變量的值為0，而恰好在它將其值設置為1之前，另一個進程被調度執行，將該鎖變量設置為1，當第一個進程再次能運行時，它同樣也將該鎖設置為1，則此時，同事有兩個進程進入臨界區。

 

嚴格輪換法：

 整型變量turn，初始值為0，用於記錄輪到哪個進程進入臨界區，並堅持或者更新共享內存。開始時，進程0堅持true，發現其值為0，於是進入臨界區。進程1也發現其值為0，所以在一個等待循環中不停的測試ture，看其值何時變為1。連續測試一個變量，直到某個值出現為止，稱為忙等待。由於這種方式浪費CPU時間，所以通常應該避免。

 

進程0離開臨界區時，將turn值設置為1，以便進程1進入臨界區，假設進程1很快就離開了臨界區，則此時兩個進程都在臨界區之外，turn值又被設置為0。現在進程0很快就執行完其整個循環，它退出臨界區，並將turn的值設置為1，兩個進程都在其臨界區之外執行。

突然，進程0結束了非臨界區的操作並返回到循環的開始。但是，這時它不能進入臨界區，因為turn的當前值為1，而此時進程1還在忙於非臨界區的操作，進程0只有繼續while循環，知道進程1將turn的值改為0。這說明，在一個進程比另一個進程慢了很多的情況下，輪流進入臨界區並不是一個好辦法。 

 

Peterson解法：

將鎖變量與警告變量的思想結合，提出了一個不需要嚴格輪換的軟件互斥算法：

 在進入臨界區之前（使用共享變量之前），各個進程使用0或1作為參數來調用enter_region。該調用在需要時，將使進程等待，直到能安全的進入臨界區，在完成對共享變量的操作之後，進程調用leave_region表示操作完成。若其他進程希望進入臨界區，則現在就可以進入。

一開始沒有任何進程處於臨界區之中，現在進程0調用enter_region，它通過設置其數組元素和將turn設置為0來標識它希望進入臨界區。由於進程1並不想進入臨界區，所以enter_region很快就會返回。如果線程1現在調用enter_region，進程1將在此處掛起，知道interseted[0]變成FALSE，該事件只有在進程0調用leave_region才會發生。

現在考慮兩個進程幾乎同時調用enter_region的情況，它們都將自己的進程號存入turn，但只有後被保存進去的進程號才有效，前一個因被重寫而丟失。假設進程1是後寫入的，則turn為1，當兩個進程都運行到while語句時，進程0將循環0次進入臨界區，而進程1將不停的循環並且不能進入臨界區，直到進程0退出臨界區為止。

 

TSL指令：

某些計算機中，特別是多處理器計算機中，都有下面的這條指令：

TSL RX,LOCK

稱為測試並加鎖，它將一個內存字lock讀入寄存器RX中，然後在該內存地址存入一個非零值。讀字與寫字保證是不可分割的，即該指令結束之前其他處理器均不容許訪問該內存字。執行TSL指令的CPU將鎖住內存總線，以禁止其他CPU在本指令結束前訪問內存。

鎖住存儲總線不等於屏蔽中斷，就屏蔽中斷來說，它在讀內存字之後跟著寫操作，並不能阻止總線上的第二個處理器在讀操作與寫操作之間訪問該內存字。也就是說，在處理器1上屏蔽中斷，對於處理器2來說，是沒有影響的。讓處理器2遠離內存直到處理器1完成，唯一方法就是鎖住總線。

 

d、睡眠與喚醒

Peterson解法和TSL都是正確的，但它們都有忙等待的缺點，這些解法的本質是這樣的：當一個進程想進入臨界區時，先檢查是否允許進入，如果不允許，則該線程原地等待，知道允許為止。

這種方法不僅浪費CPU，而且還可能引起預想不到的結果。考慮到一台計算機的兩個進程，H優先級較高，L優先級較低。調度規則規定，只要H處於就緒狀態，就可以運行，在某一時刻，L處於臨界區，此時H變為就緒態，准備運行。現在H開始忙等待，但由於當H就緒時L不會被調度，也就無法離開臨界區，所以H將永遠等待下去，這種情況有時候被稱為優先級反轉問題。（在iOS開發中，蘋果文檔建議我們少使用dispatch_priority的高優先級別，盡量使用默認優先級別，也是有這種考慮在內的吧，但是那是線程，而不是進程）。

有幾條進程間通信的原語，它們無法進入臨界區時將阻塞，而不是忙等待。還有sleep和wakeup，sleep是一個將引起調用進程阻塞的系統調用，即被掛起，直到另一個進程將其喚醒。wakeup有一個參數，即要被喚醒的進程。

生產者-消費者問題，也稱作界緩沖區問題。兩個進程共享一個公共的固定大小的緩沖區，其中一個是生產者，將信息放入緩沖區，另一個是消費者，從緩沖區取出信息。

問題在於，當緩沖區已經滿了，而此時生產者還想向其中放入一個新的數據項的情況，其解決方法是，讓生產者睡眠，待消費者從緩沖區取出一個或者多個數據項時，再喚醒它。同樣的，當消費者試圖從緩沖區取出數據而發現緩沖區為空時，消費者就睡眠，知道生產者放入了一些數據再將消費者喚醒。

 現在回到競爭條件的問題，這裡可能會出現競爭條件，其原因是對count的訪問沒有加以限制。有可能會出現這種情況：緩沖區為空，消費者剛剛讀取到count的值發現它為0，此時調度程序決定暫停消費者並啟動運行生產者。生產者向緩沖區中加入一個數據項，count++，現在count的值變為1了，它推斷認為由於count剛才為0，所以消費者此時一定在睡眠，於是生產者調用wakeup來喚醒消費者。

但是，消費者此時在邏輯上並未睡眠，所以wakeup信號丟失。當消費者下次運行時，它將測試先前讀到的count值，發現它為0，於是睡眠。生產者遲早會填滿整個緩沖區，然後進入睡眠，這樣一來，兩個進程都將永遠睡眠下去。

 

e、信號量

它使用一個整型變量來累計喚醒的次數，供以後使用。一個信號量的取值可以為0（表示沒有保存下來的喚醒操作）或者為正值（表示有一個或多個喚醒操作）。

信號量有down和up操作，對一信號量進行down操作，先檢查其數值，如果該值大於0，則減1（表示用掉一個信號量）並繼續，如果為0，則進程將進入睡眠。檢查數值、修改變量值、以及可能發生的睡眠操作是作為一個單一的、不可分割的原子操作完成的。保證一旦一個信號量開始，則在該操作完成或阻塞之前，其他進程均不可以訪問該信號量。這種原子性，對於解決同步問題和避免競爭條件是決定必要的。所謂原子操作，是指一組相關聯的操作要麼不間斷的執行，要麼都不執行。

up操作對信號量的值加1。如果一個或者多個進程在該信號量上睡眠，無法完成一個先前的down操作，則由系統選擇其中一個，並允許該進程完成它的down操作。

 用信號量解決丟失的wakeup問題，為確保信號量可以正確的工作，最重要的是采用一種不可分割的方式來實現它。通常是將down\up作為系統調用實現，而且操作系統只在執行以下操作時，暫時屏蔽全部中斷：測試信號量、更新信號量以及在需要時使某個進程睡眠。由於這些動作只需要幾條指令，所以屏蔽中斷不會帶來副作用。如果使用多個CPU，則每個信號量應由一個鎖變量進行保護。

信號量的另一種用途是為了實現同步，信號量full和empty用來保證某種事件的順序發送或者不發生。在本例中，它保證了當緩沖區滿的時候生產者停止運行，以及當緩沖區空的時候消費者停止運行。

 

f、互斥量

 如果不需要使用信號量的計數能力，有時可以使用信號量的一個簡化版本，稱為互斥量，它僅僅適用於管理共享資源或一小段代碼。

互斥量是可以處於兩態之一的變量：解鎖和加鎖。這樣，只需要一個二進制位表示它，不過實際上，常常使用一個整形量，0表示解鎖，其他值表示加鎖。互斥量使用的兩個過程：當一個線程（或者進程）需要訪問臨界區時，它調用mutex_lock，如果該互斥量當前是解鎖的（即臨界區可用），此調用成功，調用線程可自由進入該臨界區。

另一方面，如果該互斥量已經加鎖，調用線程被阻塞，直到在臨界區的線程完成並調用mutex_unlock。如果多個線程被阻塞在該互斥量上，將隨機選擇一個線程並允許它獲得鎖。

 

g、管程

一個管程是一個由過程、變量、以及數據結構等組成的一個集合，它們組成了一個特殊的模塊或者軟件包。進程可以在任何需要的時候調用管程中的過程，但它們不能在管程聲明之外的過程中直接訪問管程內的數據結構。

管程有一個很重要的特性，即任一時刻，管程中只能有一個活躍進程，這一特性使得管程能有效的完成互斥。管程是編程語言的組成成分，編譯器知道它們的特殊性，因此可以采用與其他過程調用不同的方法來處理對管程的調用。典型的處理方法是：當一個進程調用管程過程時，該過程的前幾條指令會檢查在管程中是否有其他活躍進程，如果有，調用進程將被掛起，直到另一個進程離開管程將其喚醒。如果沒有活躍進程在使用管程，則該調用進程可以進入。

 

4、調度

當計算機系統是多道程序設計系統時，通常會有多個進程或者線程同時競爭CPU，只要有兩個或者更多的進程處於就緒態，這種情況就會發生。如果只有一個CPU可以使用，那麼就必須選擇下一個要運行的進程。在操作系統中，完成選擇工作的這一部分稱為調度，該程序使用的算法稱為調度算法。

盡管有些不同，但許多適用於進程調度的處理方法同時也適用於線程調度。當內核管理線程的時候，調度經常是按線程級別的，與線程所屬的進程基本或根本沒有關聯。

 

a、批處理系統中的調度算法

先來先服務：

在所有調度算法中最簡單的是非搶占式的先來先服務算法，使用該算法，進程按照它們請求CPU的順序使用CPU。基本上，就是一個就緒進程的單一隊列，早上，當第一個作業從外部進入系統，就立即開始並允許運行它所期望的時間。不會中斷該作業，因為它需要很長的時間運行，當其他作業進入時，它們就被安排在隊列的尾部。當正在運行的進程被堵塞時，隊列中的第一個進程就接著運行，當被堵塞的進程變為就緒態時，它就像一個新來到的作業一樣，被排到隊列末尾。

 

最短作業優先：

它是適用於運行時間可以預知的另一個非搶占式的批處理算法。例如，一家保險公司，因為每天都做類似的工作，所以人們可以相當精確的預測處理1000個索賠的一批作業需要多少時間。當輸入隊列有若干個同等重要的作業被啟動時，調度程序應該使用最短作業優先算法。

 

最短剩余時間優先：

最短作業優先的搶占式算法就是最短剩余時間優先算法，使用這個算法，調度程序總是選擇剩余運行時間最短的那個算法。 

 

b、交互式系統中的調度

輪轉調度：

一種最古老、最簡單、最公平並且使用最廣的算法是輪轉算法。每個進程被分配一個時間段，稱為時間片，即允許該進程在該時間段中運行。如果在時間片結束時，該進程還在運行，則將剝奪CPU被分配給另一進程。如果該進程在時間片結束之前被堵塞或者結束，則CPU立刻進行切換。時間片輪轉調度很容易實現，調度程序所要做的就是維護一張可運行進程列表，當一個進程用完它的時間片之後，就被一到隊列末尾。

時間片輪轉調度唯一有趣的一點就是時間片的長度，從一個進程切換到另一個進程是需要一定時間進行事務處理的（保存和裝入寄存器值及內存映像、更新各種表格和列表、清楚和重新調入內存高速緩存等），稱為進程切換，也稱作上下文切換。

時間片設置得太短會導致過多的進程切換，降低了CPU效率；而設置太長又可能引起對短的交互請求的響應時間變長，將它設置為20ms~~50ms是一個比較合理的折中。

 

優先級調度：

輪轉調度做了一個隱含的假設，即所有的進程同等重要。而實際中即使是在只有一個用戶的PC上，也會有多個進程，其中一些比另一些更重要。

為了防止高優先級別的進程無休止的運行下去，調度程序可以在每個時鐘中斷降低當前線程的優先級別，如果這個行為導致當前進程的優先級別低於次高優先級的進程，則進行線程切換。一個可以采用的方法是，每個進程可以被賦予一個允許運行的最大時間片，當這個時間片用完時，下一個次高優先級的進程開始運行。 

如果不對優先級別進行調整，則低優先級別的進程很可能會產生饑餓現象。

 

最短進程優先：

 對於批處理系統而言，由於最短作業優先常常伴隨著最短響應時間，所以如果能夠把它用於交互進程，那將是非常好的。在某種程度上，的確可以做到這一點，交互進程通常遵循下列模式：等待命令、執行命令、等待命令、執行命令，反復循環。如果我們將每一個命令的執行看作是一個獨立的作業，則我們可以通過首先運行最短的作業來使響應時間最短。這裡唯一的問題是，如何從當前可運行進程中找出最短的那一個進程。

一種辦法是根據進程過去的行為進行推測，並執行估計運行時間最短的那一個。

 

還有其他的一些調度算法，但是不再做過多的描述。

 

c、線程調度

當若干進程都有多個線程時，就存在兩個層次的並行：進程和線程。在這樣的系統中調度處理有本質的區別，這取決於所支持的是用戶級線程還是內核級線程（或者兩者都支持）。

首先考慮用戶級線程，由於內核並不知道有線程存在，所以內核還是和以前一樣的操作，選擇一個進程A，並給予A以時間片控制。A中的線程調度程序決定哪個線程運行，假設是a線程運行。由於多道線程並不存在時鐘中斷，所以這個線程可以按照其意願任意運行多長時間。如果該線程用完了進程的全部時間片，內核就會選擇另一個進程運行。

考慮到使用內核級線程的情形，內核選擇一個特定的線程運行，它不用考慮這個線程屬於哪個進程，對被選擇的線程賦予一個時間片，如果超過了時間片，就強制掛起該線程。

用戶級線程與內核級線程的差別在於性能。用戶級線程切換只需要少量的機器指令，而內核級線程需要完整的上下文切換，修改內存映像，使告訴緩存失效，這導致了若干數量級的延遲。另一方面，使用內核級線程時，一旦線程阻塞在I/O上，就不需要像用戶級線程中那樣將整個進程掛起。