您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 程式設計技術

操作系統筆記:進程與線程的核心概念

編輯:iOS 程式設計技術

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

 

1、進程

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

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

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

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

 

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

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

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

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

 

多道程式設計模型:採用多道程式設計可以提高 CPU 的利用率。嚴格地說,如果進程用於計算的平均時間是進程在記憶體中停留時間的 20%,且記憶體中同時有五個進程,則 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,所以在一個等待循環中不停測試 true,看其值何時變為 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 將在此處掛起,直到 interested[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 上,就不需要像使用者級線程中那樣將整個進程掛起。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved