1、1 第四章 并發處理2第四章 并發處理4.1 并發活動進程的引人 操作系統的特性之一是并發與共享，即在系統中（內存）同時存在幾個相互獨立的程序，這些程序在系統中既交叉地運行，又要共享系統中的資源，這就會引起一系列的問題，包括：對資源的競爭、運行程序之間的通信、程序之間的合作與協同等符。 要解決這些問題，用程序的概念已經不能描述程序在內存中運行的狀態，必須引人新的概念進程。34.1 并發活動進程的引人4.1.1 程序的順序執行 一、概念 一個程序由若干個程序段組成，而這些程序段的執行必須是順序的，這種程序執行的方式就稱為程序的順序執行。 例如： 44.1 并發活動進程的引人4.1.1 程序的順序

2、執行 二、程序順序執行的特點1.順序性 處理機嚴格按照程序所規定的順序執行，即每個操作必須在下一個操作開始之前結束。2.封閉性 程序一旦開始執行，其計算結果不受外界的影響，當程序的初始條件給定之后，其后的狀態只能由程序本身確定，即只有本程序才能改變它。3.可再現性 程序執行的結果與初始條件有關，而與執行時間無關。即只要程序的初始條件相同，它的執行結果是相同的，不論它在什么時間執行，也不管計算機的運行速度。54.1 并發活動進程的引人4.1.2 程序的并發執行例： 在系統中有n個作業，每個作業都有三個處理步驟，輸入數據、處理、輸出，即Ii,Ci,Pi (i=1,2,3,.,n)。 這些作業系統中

3、執行時是對時間的偏序，有些操作必須在其它操作之前執行，這是有序的，但有些操作是可以同時執行的。例如: I1、C1、P1的執行必須嚴格按照I1，C1，P1的順序，而P1與I2，C1與I2，I3與P1是可以同時執行的。64.1 并發活動進程的引人4.1.2 程序的并發執行例如: I1、C1、P1的執行必須嚴格按照I1，C1，P1的順序，而P1與I2，C1與I2,I3與P1是可以同時執行的。74.1 并發活動進程的引人4.1.2 程序的并發執行程序并發執行 （定義） 若干個程序段同時在系統中運行，這些程序的執行在時間上是重迭的，一個程序段的執行尚未結束，另一個程序段的執行已經開始，即使這種重迭是很小

4、的，也稱這幾個程序段是并發執行的。84.1 并發活動進程的引人4.1.2 程序的并發執行程序并發執行的描述 cobegin S1;S2;S3;.;SN coend; Si(i=1,2,3,.,n)表示n個語句（程序段），這n個語句用cobegin和coend括起來表示這n個語句是可以并發執行的。co是concurrent的頭兩個字符。 這是Dijkstra提出的。94.1 并發活動進程的引人4.1.2 程序的并發執行假設有一個程序由S0Sn+1個語句，其中 S1Sn語句是并發執行的，程序如下： S0; cobegin S1;S2;S3;.;SN coend; Sn+1;104.1 并發活動進程

5、的引人4.1.3 并發執行實行謄抄一、一個循環程序順序執行的謄抄算法1：輸入：f 輸出：g while (f 不為空） input ; output ; 由這個程序完成謄抄工作是不會出錯的。114.1 并發活動進程的引人4.1.3 并發執行實行謄抄二、兩個程序并發執行完成謄抄 設有一臺標準輸入設備（鍵盤），和一臺標準輸出設備（顯示器或打印機），輸入程序負責從標準設備中讀取一個字符，送緩沖區中。輸出程序從緩沖區中取數據，送標準設備輸出。124.1 并發活動進程的引人4.1.3 并發執行實行謄抄二、兩個程序并發執行完成謄抄算法：2 cobegin while (不為結束符）/* 輸入程序段 */

6、input; /* 從標準輸入設備讀入一個數據 */ send; /* 將讀入的數據送到bufferf */ while(buffer不為空） /* 輸出程序段 */ receive; /* 從bufferf中取數據 */ output; /* 送打印機輸出 */ coend 134.1 并發活動進程的引人4.1.3 并發執行實行謄抄二、兩個程序并發執行完成謄抄這兩個程序段并發執行時可能出現如下情況：1、輸出程序運行的速度比輸入程序快時，有些輸出會重復； 如輸入送入了一個字符“A”，輸出取出打印“A”，當輸入還未送入新的數據，輸出程序已執行，又取出“A”打印，這樣“A”的輸出就重復了，出錯。2

7、、輸入程序執行的速度比輸出程序快時，有些數據會丟失； 如輸入程序送入一個字符“B”，緊接著（當輸出程序還未取走字符“B”）又送入字符“N”，這時輸出程序取走的是“N”，“B”就丟失了。144.1 并發活動進程的引人4.1.3 并發執行實行謄抄 三、三個并發執行程序的謄抄get程序負責人輸入序列f中讀取字符并送到緩沖區s中;copy程序把緩沖區s中的數據復制到緩沖區t中去;put程序從緩沖區t中取出數據打印。154.1 并發活動進程的引人4.1.3 并發執行實行謄抄 三、三個并發執行程序的謄抄 假設有兩個緩沖區，每個緩沖區只存放一個字符，get程序負責從輸入序列f中讀一個字符，然后，送到緩沖區s

8、中，copy程序負責將s中的字符復制到t中，put負責從t中提取字符打印。這個算法是正確的。164.1 并發活動進程的引人4.1.4 與時間有關的錯誤假定f系列中有記錄 f=(R1,R2,.,Rn) g=()在謄抄完成后： f=() g=(R1,R2,.,Rn)算法中的：copyt=s put put(t,g) get get(s,f)174.1 并發活動進程的引人4.1.4 與時間有關的錯誤若程序錯寫成：while(謄抄未完成） cobegin copy; put; get; coend 初始狀態： f=(R1,R2,.,Rn) s=() t=() g=()首先執行了get(s,f) f=(

9、R1,R2,.,Rn) s=R1,t=(),g=()184.1 并發活動進程的引人4.1.4 與時間有關的錯誤然后，copy,put,get三個程序段并發執行，就有六種組合：1、copy;put;get 導致結果：g=(R1,R2) 2、copy;get;put 導致結果：g=(R1,R2) 3、put;copy;get 導致結果：g=(R1,R1) 4、put;get;copy 導致結果：g=(R1,R1) 5、get;copy;put 導致結果：g=(R1,R3) 6、get;put;copy 導致結果：g=(R1,R1) 這就是與時間有關的錯誤。194.1 并發活動進程的引人4.1.5

10、程序并發執行的特點一、失去了程序的封閉性 如果程序執行的結果是一個與時間無關的函數，即具有封閉性。 若一個程序的執行可改變另一個程序的變量，象二個并發程序完成謄抄的例子，程序執行的結果不僅依賴于程序的初始條件，還依賴于程序執行時的相對速度，在這種情況下就失去了程序的封閉性。 教材P62介紹了兩個并發程序共享變量的例子204.1 并發活動進程的引人4.1.5 程序并發執行的特點二、程序與計算不再一一對應 在程序順序執行時，一個程序總是對應一個具體的計算，但在程序的并發執行時，可能有多用戶共享使用同一個程序，但處理（計算）的對象卻是不同的，例如，在多用戶環境下，可能同時有多個用戶調用C語言的編譯程

11、序，這就是典型的一個程序對應多個用戶源程序的情況。214.1 并發活動進程的引人4.1.5 程序并發執行的特點三、程序并發執行的相互制約 在多道程序設計的環境下，程序是并發執行的。即系統中有多道程序在“同時”執行，這些程序之間要共享系統的資源，程序之間有合作（通信）的關系。合作與競爭產生一系列的矛盾，這些矛盾實際上是一種相互制約，有直接的，也有間接。 回頭來，我們再看看操作系統的第三個特性： 不確定性*224.2 進程概念(process) 4.2.1 進程的定義 在多道程序設計的環境下，為了描述程序在計算機系統內的執行情況，必須引人新的概念進程。 進程的概念來自于麻省理工的MULTICS、I

12、BM的 TSS/360，在IBM的OS/360/370系統中也曾叫過任務（task)。234.2 進程概念(process) 4.2.1 進程的定義進程的定義（枚舉法）行為的一個規則叫做程序，程序在處理機上執行時所發生的活動稱為進程（Dijkstra)。進程是這樣的計算部分，它是可以和其它計算并行的一個計算。(Donovan)進程（有時稱為任務）是一個程序與其數據一道通過處理機的執行所發生的活動。（Alan.C. Shaw)進程是執行中的程序。（Ken Thompson and Dennis Ritchie )教材上給出的進程的定義： 進程，即是一個具有一定獨立功能的程序關于某個數據集合的一次

13、活動。244.2 進程概念(process) 4.2.1 進程的定義 進程與程序的區別與聯系：1、程序是指令的集合，是靜態的概念。 進程是程序在處理機上的一次執行的過程，是動態的概念。程序可以作為軟件資料長期保存。進程是有生命周期的。2、進程是一個獨立的運行單位，能與其它進程并行（并發）活動。而程序則不是。3、進程是競爭計算機系統有限資源的基本單位，也是進行處理機調度的基本單位。4、一個程序可以作為多個進程的運行程序，一個進程也可以運行多個程序。254.2 進程概念(process) 4.2.1 進程的定義 進程與程序的區別與聯系：例子：光盤（CD、VCD）光盤（程序） 放光盤的活動（進程）2

14、64.2 進程概念(process)4.2.2 進程的類型在系統中同時有多個進程存在，但歸納起來有兩大類：1、系統進程 系統進程起著資源管理和控制的作用。 或者：執行操作系統核心代碼的進程。2、用戶進程 執行用戶程序的進程。274.2 進程概念(process)4.2.2 進程的類型系統進程與用戶進程的區別：1、系統進程被分配一個初始的資源集合，這些資源可以為它獨占，也能以最高優先權的資格使用。用戶進程通過系統服務請求的手段競爭使用系統資源；2、用戶進程不能直接做I/O操作，而系統進程可以做顯示的、直接的I/O操作。3、系統進程在管態下活動，而用戶進程則在用戶態（目態）下活動。另一種分類：計算

15、進程，I/O進程等注意：在UNIX系統中沒有這樣對進程進行分類。284.2 進程概念(process)4.2.3 進程的狀態一、進程的基本狀態進程在系統中的活動規律是： 執行 暫停 執行進程的三種基本狀態： 運行狀態 就緒狀態 等待狀態（又稱阻塞、掛起、睡眠）294.2 進程概念(process)4.2.3 進程的狀態 一、進程的基本狀態1、就緒狀態（Ready) 存在于處理機調度隊列中的那些進程，它們已經準備就緒，一旦得到CPU，就立即可以運行，這些進程所取的狀態為就緒狀態。（有多個進程處于此狀態）2、運行狀態(Running） 當進程由調度/分派程序分派后，得到CPU控制權，它的程序正在運

16、行，該進程所處的狀態為運行狀態。（在系統中，總只有一個進程處于此狀態）3、等待狀態（Wait) 若一個進程正在等待某個事件的發生（如等待I/O的完成），而暫停執行，這時，即使給它CPU時間，它也無法執行，則稱該進程處于等待狀態。304.2 進程概念(process)4.2.3 進程的狀態二、進程狀態變遷圖進程的狀態不是固定不變的，而是在不斷變換。314.2 進程概念(process)4.2.3 進程的狀態二、進程狀態變遷圖運行 等待 等待某事件的發生（如等待I/O完成）等待 就緒 事件已經發生（如I/O完成）運行 就緒 時間片到（例如，兩節課時間到，下課）新建進程 就緒 新創建的進程進入就緒狀

17、態就緒 運行 當處理機空閉時，由調度（分派）程序從就緒進程隊列中選擇一個進程占用CPU。324.2 進程概念(process)4.2.3 進程的狀態三、作業、作業狀態及轉移 在批處理系統中一個用戶程序的執行的全過程稱為一個作業，當作業提交給計算中心（或機房）后，由機房工作人員錄入到存儲設備上（如磁帶、磁盤等），然后，由作業調度程序按某種調度策略將作業調入計算機系統執行，執行完成后，由作業調度程序做作業的善后處理工作，至此一個作業完成。334.2 進程概念(process)4.2.3 進程的狀態三、作業、作業狀態及轉移 我們把上述對作業的操作歸納成四種狀態：1、提交狀態 用戶將自己的程序和數據放

18、在輸入設備上，等待；2、后備狀態 系統響應用戶的要求，將作業帶領到直接存取的后援存儲器中，等待調度；3、執行狀態 從作業計算開始，到計算完成為止，該作業處于執行狀態。4、完成狀態 從作業計算完成開始，到善后處理完畢退出系統為止，稱為作業完成狀態。344.2 進程概念(process)4.2.3 進程的狀態三、作業、作業狀態及轉移354.2 進程概念(process) 4.2.4 進程描述在系統中一個進程存在： 進程控制塊（數據結構） 進程的執行程序（一個可執行文件） 進程總是位于某個隊列(就緒、等待某事件隊列) 處于某種狀態（運行、就緒、等待） 占用某些系統資源（內存，打開某些文件、處理機、外

19、設）364.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB (Process Control Block) 存放進程的管理和控制信息的數據結構稱為進程控制塊。它是進程管理和控制的最重要的數據結構，在創建時，建立PCB，并伴隨進程運行的全過程，直到進程撤消而撤消。PCB就象我們的戶口。374.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB 1、進程標識符 name 每個進程都必須有一個唯一的標識符，可以是字符串，也可以是一個數字。UNIX系統中就是一個整型數。在進程創建時由系統賦予。 2、進程當前狀態 status 說明進程當前所處的狀態。 為了管理的

20、方便，系統設計時會將相同的狀態的進程組成一個隊列，如就緒進程隊列，等待進程則要根據等待的事件組成多個等待隊列，如等待打印機隊列、等待磁盤I/O完成隊列等等。384.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB3、當前隊列指針 next 登記與本進程處于同一隊列的下一個進程的PCB的地址。394.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB4、總鏈指針 all-q-next5、執行程序開始地址 start-addr6、進程優先級 priority 進程的優先級反映進程的緊迫程序，通常由用戶指定和系統設置。UNIX系統采用用戶設置和系統計算相結合的方

21、式確定進程的優先級。404.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB7、CPU現場保護區 cpustatus 當進程因某種原因不能繼續占用CPU時（等待打印機），釋放CPU，這時就要將CPU的各種狀態信息保護起來，為將來再次得到處理機恢復CPU的各種狀態，繼續運行。例如，我們下課，這時我要記住這次講到什么地方，下次課接著講。8、通信信息 communication information 是指某個進程在運行的過程中要與其它進程進行通信，該區記錄有關進程通信方面的信息。414.2 進程概念(process)4.2.4 進程描述進程控制塊 PCB9、家族聯系 proce

22、ss family 有的系統允許一個進程可創建自已的子進程，子進程還可以創建，一個進程往往處在一個家族之中，就需要記錄進程在家族中位置的信息。10、占有資源清單 own-resource 進程占用系統資源的情況，不同的系統的處理差別很大，UNIX系統中就沒有此項。424.3 進程控制4.3.1 進程控制的概念 進程是有生命周期的，產生、運行、暫停、終止。對進程的這些操作叫進程控制。 進程控制的職責是對系統中全部進程實施有效的管理，它是處理機管理的部分（另一部分是進程調度），當系統允許多進程并發執行時，為了實現共享、協調并發進程的關系，處理機管理必須提供對進程實行有效的管理。434.3 進程控制

23、4.3.1 進程控制的概念 進程控制包括： 進程創建、 進程撤消、 進程阻塞、 進程喚醒。 這些操作都要對應地執行一個特殊的程序段（操作系統核心程序），同時系統也通過系統調用給用戶提供進程控制的功能。教材上叫原語（一種特殊的系統調用）。444.3 進程控制4.3.1 進程控制的概念運行狀態 等待狀態 進程阻塞等待狀態 就緒狀態 進程喚醒新建進程置為就緒狀態 進程創建進程終止（消亡） 進程撤消就緒狀態 運行狀態 進程調度454.3 進程控制4.3.1 進程控制的概念 在UNIX系統中進程控制的系統調用有： fork() 創建子進程 sleep() 進程睡眠 exit() 進程自已終止（自殺） w

24、ait() (父）等待子進程終止 wakeup() 進程喚醒 在4.9節介紹。464.3 進程控制4.3.2 進程創建 在UNIX系統中用戶鍵人一個命令（如date, ps,ls)，shell就創建一個進程。 一個程序（可執行的）如果可分成幾個程序段，并且這些程序段可并發執行，用戶程序可使用創建程序的系統調用創建多個進程，每個進程執行一個程序段。例如，放VCD程序。 進程創建類似于人出生后要到派出所報戶口。474.3 進程控制4.3.2 進程創建進程創建系統調用： create(name,priority,start-addr)UNIX系統： fork()484.3 進程控制4.3.2 進程創

25、建494.3 進程控制4.3.3 進程撤消 進程完成其任務，希望終止時，調用撤消進程的系統調用（進程撤消原語）撤消進程。相當于一個人死亡后，家人要去派出所消戶口。 在一般操作系統中進程撤消的系統調用是：kill UNIX系統中是exit()。 504.3 進程控制4.3.3 進程撤消514.3 進程控制4.3.3 進程撤消524.3 進程控制4.3.4 進程掛起 當一個處在運行狀態的進程，因等待某個事件的發生（如等待打印機）而不能繼續運行時，將調用進程掛起系統調用，把進程的狀態置為阻塞狀態，并調用進程調度程序（等于讓出處理機）。在UNIX系統中進程掛起調用sleep(chan, pri)。53

26、4.3 進程控制4.3.4 進程掛起 進程從運行狀態轉換成阻塞狀態是由進程掛起原語實現的，因此，調用進程掛起操作是在進程處于運行狀態下執行的。它的執行將引起等待某事件的隊列的改變. 例如，進程是因等待打印機而進入阻塞狀態，則該進程將加入到等待打印機的隊列。進程掛起系統調用的算法和隊列變化如下。544.3 進程控制4.3.4 進程掛起進程掛起的內部調用形式（UNIX系統）： sleep(chan,pri) 其中：chan 進程掛起（睡眠）的原因； pri 進程被喚醒后的優先級 一般調用形式： susp(chan) 其中：chan 進程等待的原因554.3 進程控制4.3.4 進程掛起564.3

27、進程控制4.3.4 進程掛起574.3 進程控制4.3.5 進程喚醒 一個正在運行的進程會因等待某事件（例如，等待打印機）的發生，由運行狀態轉換成阻塞狀態，當它等待的事件發生后，這個進程將由阻塞狀態轉換成就緒狀態。這種轉換由進程喚醒操作完成。 調用進程喚醒操作一般在中斷處理、進程通信等過程中。例如，打印機完成中斷處理程序， 在完成了打印完成的操作后，就去檢查等待打印機的隊列，若不為空，則調用進程喚醒操作，喚醒一個（或多個）等待打印機的進程。 584.3 進程控制4.3.5 進程喚醒進程喚醒原語的形式： wakeup(chan) 其中：chan 喚醒進程阻塞的原因。594.3 進程控制4.3.5 進程喚醒算法：wakeup輸入：chan:等待的事件（阻塞原因）輸出：無 找到chan的等待隊列的指針； for(該隊列不為空） 從隊列中移出一個進程； 置進程狀態為“就緒”，并加入到就緒隊列； 604.3 進程控制4.3.5 進程喚醒 按此算法，是把等待在chan事件上的所有進程喚醒，類似于UNIX系統的處理方式。也有的系統只喚醒一個等待chan事件的進程，若這樣處理，等待隊列就要按某