操作系統(tǒng)OS提高

1、1共一百二十頁(yè)第四章 并發(fā)(bngf)處理2共一百二十頁(yè)4.1 并發(fā)活動(dòng)進(jìn)程(jnchng)的引人操作系統(tǒng)的特性是并發(fā)與共享資源的競(jìng)爭(zhēng)程序間的合作與協(xié)同要解決(jiju)這些問(wèn)題，程序已經(jīng)不能描述程序在內(nèi)存中運(yùn)行的狀態(tài)，必須引人新的概念進(jìn)程。3共一百二十頁(yè)4.1.1 程序的順序(shnx)執(zhí)行I1作業(yè)1C1P1作業(yè)2I2C2P2一、概念 一個(gè)程序由若干個(gè)程序段組成，而這些(zhxi)程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式稱為程序的順序執(zhí)行。4共一百二十頁(yè)二、程序(chngx)順序執(zhí)行的特點(diǎn)1.順序性 處理機(jī)嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在下一個(gè)操作開(kāi)始之前結(jié)束。2.封閉性

2、程序一旦開(kāi)始執(zhí)行，其計(jì)算結(jié)果不受外界的影響。3.可再現(xiàn)性 程序執(zhí)行的結(jié)果只與初始條件有關(guān)，與其它(qt)無(wú)關(guān)。5共一百二十頁(yè)二、程序順序執(zhí)行(zhxng)的特點(diǎn) 程序(chngx)順序執(zhí)行的缺點(diǎn)： 效率太低。6共一百二十頁(yè)4.1.2 程序的并發(fā)(bngf)執(zhí)行例：在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有三個(gè)處理步驟，輸入數(shù)據(jù)(shj)、處理、輸出，即Ii,Ci,Pi (i=1,2,3,.,n)。7共一百二十頁(yè)I1I2I3I4C1C2C3P1P2C1與I2, I3、C2、P1是可以同時(shí)(tngsh)執(zhí)行的。4.1 并發(fā)活動(dòng)進(jìn)程的引人4.1.2 程序(chngx)的并發(fā)執(zhí)行I1、C1、P1的執(zhí)行是順序的8

3、共一百二十頁(yè)4.1 并發(fā)活動(dòng)進(jìn)程的引人(yn rn)4.1.2 程序的并發(fā)執(zhí)行程序并發(fā)執(zhí)行(zhxng) （定義） 若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，若這些程序的執(zhí)行在時(shí)間上存在重迭，則稱為程序并發(fā)執(zhí)行。p1p2p39共一百二十頁(yè)4.1.2 程序的并發(fā)(bngf)執(zhí)行程序(chngx)并發(fā)執(zhí)行的描述 cobegin S1; S2; S3; .; SN； coend；co是concurrent的頭兩個(gè)字符。 這是Dijkstra提出的。10共一百二十頁(yè)4.1.2 程序(chngx)的并發(fā)執(zhí)行S0Sn+1S1S2S3SN假設(shè)(jish)有一個(gè)程序中 S1Sn語(yǔ)句是并發(fā)執(zhí)行的，程序如下： S0; cob

4、egin S1;S2;S3;.;SN； coend; Sn+1;11共一百二十頁(yè)4.1.3 并發(fā)執(zhí)行(zhxng)實(shí)行謄抄一、順序執(zhí)行(zhxng)的謄抄算法1：輸入：f 輸出：g while (f 不為空） input ; output ; 由這個(gè)程序完成(wn chng)謄抄工作是不會(huì)出錯(cuò)的。12共一百二十頁(yè)4.1.3 并發(fā)(bngf)執(zhí)行實(shí)行謄抄二、兩個(gè)程序并發(fā)執(zhí)行完成謄抄f緩沖區(qū)輸入程序輸出程序g 設(shè)有一臺(tái)輸入設(shè)備，和一臺(tái)輸出設(shè)備，輸入程序負(fù)責(zé)從輸入設(shè)備讀取一個(gè)(y )字符，送緩沖區(qū)中。輸出程序從緩沖區(qū)中取數(shù)據(jù)，送準(zhǔn)輸出設(shè)備。13共一百二十頁(yè)4.1.3 并發(fā)執(zhí)行實(shí)行謄抄二、兩個(gè)程序(c

5、hngx)并發(fā)執(zhí)行完成謄抄算法：2 cobegin while (不為結(jié)束符） /* 輸入程序段 */ input; /* 讀入數(shù)據(jù)(shj) */ send; /* 數(shù)據(jù)送緩沖區(qū) */ while(buffer不為空） /* 輸出程序段 */ receive; /* 緩沖區(qū)中取數(shù)據(jù) */ output; /* 輸出 */ coend 14共一百二十頁(yè)4.1.3 并發(fā)執(zhí)行實(shí)行謄抄二、兩個(gè)程序(chngx)并發(fā)執(zhí)行完成謄抄程序并發(fā)執(zhí)行時(shí)情況1、輸出程序運(yùn)行的速度(sd)比輸入程序快時(shí)，某些輸出可能會(huì)重復(fù)；2、輸入程序執(zhí)行的速度比輸出程序快時(shí)，有些數(shù)據(jù)會(huì)丟失；15共一百二十頁(yè)4.1.3 并發(fā)執(zhí)行(

6、zhxng)實(shí)行謄抄 三、三個(gè)并發(fā)執(zhí)行程序的謄抄f緩沖區(qū)getput緩沖區(qū)copyg兩個(gè)(lin )緩沖區(qū)？三個(gè)緩沖區(qū)？16共一百二十頁(yè)4.1.3 并發(fā)執(zhí)行實(shí)行(shxng)謄抄 三、三個(gè)并發(fā)執(zhí)行程序的謄抄假設(shè)有兩個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只存放一個(gè)字符，get程序?qū)⑿蛄衒中的一個(gè)字符讀到緩沖區(qū)s中，copy程序?qū)中的字符復(fù)制到t中，put從t中提取(tq)字符并打印。這個(gè)算法是正確的。17共一百二十頁(yè)4.1.4 與時(shí)間有關(guān)(yugun)的錯(cuò)誤假定f系列中有記錄(jl)f=(R1,R2,.,Rn)g=()在謄抄完成后：f=(R1,R2,.,Rn)g=(R1,R2,.,Rn)算法中的：copy t=

7、s put put(t,g) get get(s,f)18共一百二十頁(yè)4.1.4 與時(shí)間有關(guān)(yugun)的錯(cuò)誤若程序(chngx)錯(cuò)寫(xiě)成：while(謄抄未完成） cobegin copy; put; get; coend 初始狀態(tài)： f=(R1,R2,.,Rn) s=() t=() g=()首先執(zhí)行了get(s,f) f=(R1,R2,.,Rn) s=R1,t=(),g=()19共一百二十頁(yè)4.1.4 與時(shí)間(shjin)有關(guān)的錯(cuò)誤copy,put,get三個(gè)程序段并發(fā)(bngf)執(zhí)行，就有六種組合：1、copy;put;get 導(dǎo)致結(jié)果：g=(R1,R2) 2、copy;get;put

8、導(dǎo)致結(jié)果：g=(R1,R2) 3、put;copy;get 導(dǎo)致結(jié)果：g=(R1,R1) 4、put;get;copy 導(dǎo)致結(jié)果：g=(R1,R1) 5、get;copy;put 導(dǎo)致結(jié)果：g=(R1,R3) 6、get;put;copy 導(dǎo)致結(jié)果：g=(R1,R1) 這就是與時(shí)間有關(guān)的錯(cuò)誤。20共一百二十頁(yè)4.1.5 程序并發(fā)執(zhí)行(zhxng)的特點(diǎn)一、失去(shq)了程序的封閉性封閉性是程序執(zhí)行的結(jié)果與時(shí)間無(wú)關(guān)。 程序的執(zhí)行的結(jié)果與時(shí)間有關(guān)，則失去了封閉性。例如：謄抄，程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時(shí)的相對(duì)速度21共一百二十頁(yè)4.1.5 程序并發(fā)執(zhí)行(zhxng)

9、的特點(diǎn)二、程序與計(jì)算不再一一對(duì)應(yīng) 在程序順序執(zhí)行時(shí)，一個(gè)程序總是對(duì)應(yīng)一個(gè)具體的計(jì)算，但在程序的并發(fā)(bngf)執(zhí)行時(shí)，可能有多用戶共享同一個(gè)程序，但處理（計(jì)算）的對(duì)象卻是不同的。22共一百二十頁(yè)4.1.5 程序并發(fā)(bngf)執(zhí)行的特點(diǎn)三、程序并發(fā)執(zhí)行的相互制約程序并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的競(jìng)爭(zhēng)程序間有合作 合作與競(jìng)爭(zhēng)產(chǎn)生一系列的矛盾，存在矛盾就會(huì)產(chǎn)生相互制約的關(guān)系。 回頭來(lái)，我們?cè)倏纯?kn kn)操作系統(tǒng)的第三個(gè)特性： 不確定性*23共一百二十頁(yè)4.2 進(jìn)程(jnchng)概念(process) 4.2.1 進(jìn)程(jnchng)的定義在多道程序(chngx)設(shè)計(jì)的環(huán)境下，為了描述程序(chng

10、x)在計(jì)算機(jī)系統(tǒng)內(nèi)的執(zhí)行情況，必須引人新的概念進(jìn)程。進(jìn)程的概念源于麻省理工學(xué)院的MULTICSIBM的 TSS/360，OS/360/370（task)。24共一百二十頁(yè)4.2.1 進(jìn)程(jnchng)的定義進(jìn)程的定義（枚舉法）行為的一個(gè)規(guī)則叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)(hu dng)稱為進(jìn)程（Dijkstra)。進(jìn)程是這樣的計(jì)算部分，它是可以和其它計(jì)算并行的一個(gè)計(jì)算。(Donovan)進(jìn)程（有時(shí)稱為任務(wù)）是一個(gè)程序與其數(shù)據(jù)一道通過(guò)處理機(jī)的執(zhí)行所發(fā)生的活動(dòng)。 （Alan.C. Shaw)25共一百二十頁(yè)4.2.1 進(jìn)程(jnchng)的定義進(jìn)程的定義（枚舉法）進(jìn)程是執(zhí)行中的程序。

11、（UNIX Ken Thompson and Dennis Ritchie )教材上給出的進(jìn)程的定義： 進(jìn)程，即是一個(gè)(y )具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次活動(dòng)。26共一百二十頁(yè)4.2.1 進(jìn)程的定義 進(jìn)程與程序(chngx)的區(qū)別與聯(lián)系1、程序靜態(tài)的。 進(jìn)程是動(dòng)態(tài)的念。2、進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，而程序則不是(b shi)。3、進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。4、一個(gè)程序可以作為多個(gè)進(jìn)程的運(yùn)行程序，一個(gè)進(jìn)程也可以運(yùn)行多個(gè)程序。27共一百二十頁(yè)4.2.1 進(jìn)程的定義 進(jìn)程與程序(chngx)的區(qū)別與聯(lián)系：例子：光盤(pán)（CD、VCD）光盤(pán)（程序

12、(chngx)） 放光盤(pán)的活動(dòng)（進(jìn)程）28共一百二十頁(yè)4.2.2 進(jìn)程(jnchng)的類型1、系統(tǒng)(xtng)進(jìn)程 系統(tǒng)進(jìn)程起著資源管理和控制的作用。 或者：執(zhí)行操作系統(tǒng)核心代碼的進(jìn)程。2、用戶進(jìn)程 執(zhí)行用戶程序的進(jìn)程。29共一百二十頁(yè)4.2.2 進(jìn)程(jnchng)的類型系統(tǒng)進(jìn)程(jnchng)與用戶進(jìn)程(jnchng)的區(qū)別：1、系統(tǒng)進(jìn)程被分配一個(gè)初始的資源集合，這些資源可以為它獨(dú)占，也能以最高優(yōu)先權(quán)的資格使用；2、用戶進(jìn)程不能做直接I/O操作，而系統(tǒng)進(jìn)程可以做顯示的、直接的I/O操作。3、系統(tǒng)進(jìn)程在核態(tài)下活動(dòng)，而用戶進(jìn)程則在用戶態(tài)下活動(dòng)。30共一百二十頁(yè)4.2.3 進(jìn)程(jnchng)

13、的狀態(tài)一、進(jìn)程(jnchng)的基本狀態(tài)進(jìn)程在系統(tǒng)中的活動(dòng)規(guī)律執(zhí)行暫停完成31共一百二十頁(yè)4.2.3 進(jìn)程(jnchng)的狀態(tài)進(jìn)程的三種基本狀態(tài)： 運(yùn)行狀態(tài) 就緒(jix)狀態(tài) 等待狀態(tài)（又稱阻塞、掛起、睡眠）32共一百二十頁(yè)4.2.3 進(jìn)程的狀態(tài)(zhungti)一、進(jìn)程的基本狀態(tài)1、就緒狀態(tài)（Ready) 進(jìn)程(jnchng)已經(jīng)準(zhǔn)備就緒，一旦得到CPU，就立即可以運(yùn)行。此時(shí)進(jìn)程(jnchng)所取的狀態(tài)為就緒狀態(tài)。（有多個(gè)進(jìn)程(jnchng)處于此狀態(tài)）33共一百二十頁(yè)4.2.3 進(jìn)程(jnchng)的狀態(tài) 一、進(jìn)程的基本狀態(tài)2、運(yùn)行狀態(tài)(zhungti)(Running） 進(jìn)程得到C

14、PU控制權(quán)，其程序正在運(yùn)行，進(jìn)程所處的狀態(tài)為運(yùn)行狀態(tài)。系統(tǒng)中處于運(yùn)行狀態(tài)的進(jìn)程數(shù)？34共一百二十頁(yè)4.2.3 進(jìn)程的狀態(tài)(zhungti) 一、進(jìn)程的基本狀態(tài)等待狀態(tài)（Wait) 若一個(gè)進(jìn)程正在(zhngzi)等待某個(gè)事件的發(fā)生（如等待I/O的完成），而暫停執(zhí)行，這時(shí)，即使給它CPU時(shí)間，它也無(wú)法執(zhí)行，則稱該進(jìn)程處于等待狀態(tài)。35共一百二十頁(yè)運(yùn)行就緒等待等待某事件的發(fā)生時(shí)間片到事件已發(fā)生進(jìn)程調(diào)度4.2.3 進(jìn)程(jnchng)的狀態(tài)二、進(jìn)程(jnchng)狀態(tài)變遷圖36共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述進(jìn)程組成： 進(jìn)程控制塊（數(shù)據(jù)結(jié)構(gòu)） 進(jìn)程的執(zhí)行程序（一個(gè)可執(zhí)行文件） 進(jìn)程總是

15、位于某個(gè)隊(duì)列(就緒、等待隊(duì)列) 處于某種狀態(tài)（運(yùn)行、就緒、等待） 占用(zhn yn)某些系統(tǒng)資源37共一百二十頁(yè)大模式(msh)可執(zhí)行程序代碼數(shù)據(jù)棧程序(chngx)地址空間共享正文區(qū)user用戶棧區(qū)數(shù)據(jù)user核心棧用戶數(shù)據(jù)區(qū)進(jìn)程非運(yùn)行狀態(tài)時(shí)U區(qū)運(yùn)行狀態(tài)時(shí)注:放映顯示進(jìn)程圖象4.2.4 進(jìn)程描述38共一百二十頁(yè)大模式(msh)可執(zhí)行程序代碼數(shù)據(jù)棧程序(chngx)地址空間共享正文區(qū)user用戶棧區(qū)數(shù)據(jù)user核心棧用戶數(shù)據(jù)區(qū)進(jìn)程非運(yùn)行狀態(tài)時(shí)U區(qū)運(yùn)行狀態(tài)時(shí)注:放映顯示進(jìn)程圖象4.2.4 進(jìn)程描述進(jìn)程組成進(jìn)程映像(image)進(jìn)程上下文（context）39共一百二十頁(yè)4.2.4 進(jìn)程(jnc

16、hng)描述進(jìn)程(jnchng)控制塊PCB (Process Control Block)進(jìn)程控制塊是存放進(jìn)程的管理和控制信息的數(shù)據(jù)結(jié)。40共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述PCB就象我們(w men)的戶口PCB是進(jìn)程管理和控制的最重要的數(shù)據(jù)結(jié)構(gòu)，進(jìn)程創(chuàng)建時(shí)，建立PCB，并伴隨進(jìn)程運(yùn)行的全過(guò)程，直到進(jìn)程撤消而消亡。41共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述PCB結(jié)構(gòu)包含信息：進(jìn)程標(biāo)識(shí)符（name）進(jìn)程當(dāng)前狀態(tài)（status）當(dāng)前隊(duì)列(duli)指針（next）總鏈隊(duì)列指針（all_q_next）執(zhí)行程序首址（start_addr）現(xiàn)場(chǎng)保護(hù)區(qū)(CPU status）進(jìn)

17、程通信（communication）家族聯(lián)系（process family）42共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述1、進(jìn)程標(biāo)識(shí)符 name 進(jìn)程在系統(tǒng)中的唯一標(biāo)識(shí)符。UNIX系統(tǒng)的進(jìn)程標(biāo)識(shí)符是一個(gè)整型數(shù)。在進(jìn)程創(chuàng)建時(shí)由系統(tǒng)賦予。2、進(jìn)程當(dāng)前狀態(tài) status 說(shuō)明進(jìn)程當(dāng)前所處的狀態(tài)，就緒、運(yùn)行(ynxng)、等待狀態(tài)。 43共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述進(jìn)程控制塊 PCB3、當(dāng)前隊(duì)列指針 next登記與本進(jìn)程處于同一隊(duì)列的下一個(gè)(y )進(jìn)程的PCB的地址。44共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述進(jìn)程控制塊 PCB4、總鏈指針(zhzhn) all-q

18、-next5、執(zhí)行程序開(kāi)始地址 start-addr6、進(jìn)程優(yōu)先級(jí) priority 進(jìn)程的優(yōu)先級(jí)反映進(jìn)程的緊迫程序，通常由用戶指定和系統(tǒng)設(shè)置。45共一百二十頁(yè)4.2.4 進(jìn)程(jnchng)描述進(jìn)程控制塊 PCB7、CPU現(xiàn)場(chǎng)保護(hù)區(qū) cpustatus 當(dāng)進(jìn)程因某種原因釋放CPU時(shí)就要將CPU的各種狀態(tài)信息保護(hù)起來(lái)。例如，我們下課，這時(shí)我要記住這次講到什么地方，下次課接著講。8、通信信息 communication information 是指某個(gè)(mu )進(jìn)程在運(yùn)行的過(guò)程中要與其它進(jìn)程進(jìn)行通信，該區(qū)記錄有關(guān)進(jìn)程通信方面的信息。46共一百二十頁(yè)4.2.4 進(jìn)程描述(mio sh)進(jìn)程控制塊

19、PCB9、家族聯(lián)系 process family 有的系統(tǒng)允許一個(gè)進(jìn)程可創(chuàng)建自已的子進(jìn)程，子進(jìn)程還可以創(chuàng)建，一個(gè)進(jìn)程往往處在一個(gè)家族之中，就需要記錄進(jìn)程在家族中位置的信息。10、占有(zhnyu)資源清單 own-resource 進(jìn)程占用系統(tǒng)資源的情況，不同的系統(tǒng)的處理差別很大，UNIX系統(tǒng)中就沒(méi)有此項(xiàng)。47共一百二十頁(yè)4.3 進(jìn)程(jnchng)控制4.3.1 進(jìn)程(jnchng)控制的概念運(yùn)行就緒等待時(shí)間片到進(jìn)程調(diào)度進(jìn)程(jnchng)喚醒進(jìn)程創(chuàng)建進(jìn)程阻塞進(jìn)程撤消48共一百二十頁(yè)4.3.1 進(jìn)程控制(kngzh)的概念進(jìn)程是有生命周期的，具有三種基本狀態(tài)，控制進(jìn)程狀態(tài)轉(zhuǎn)換的操作稱為進(jìn)程控

20、制。包括：進(jìn)程創(chuàng)建(chungjin)、撤消、掛起和喚醒。在具體的操作系統(tǒng)中還會(huì)增加些進(jìn)程控制。49共一百二十頁(yè)進(jìn)程(jnchng)控制屬于處理機(jī)管理的一部分，另一部分是進(jìn)程調(diào)度，當(dāng)系統(tǒng)允許多進(jìn)程并發(fā)執(zhí)行時(shí)，為了實(shí)現(xiàn)共享、協(xié)同，必須提供對(duì)進(jìn)程實(shí)行有效的管理。4.3.1 進(jìn)程(jnchng)控制的概念50共一百二十頁(yè)4.3.1 進(jìn)程(jnchng)控制的概念這些操作都要對(duì)應(yīng)地執(zhí)行一個(gè)程序段（操作系統(tǒng)核心程序），同時(shí)通過(guò)系統(tǒng)調(diào)用為用戶(yngh)提供進(jìn)程控制的服務(wù)。教材上叫原語(yǔ)。進(jìn)程控制：進(jìn)程創(chuàng)建 進(jìn)程撤消進(jìn)程阻塞 進(jìn)程喚醒51共一百二十頁(yè)4.3.1 進(jìn)程(jnchng)控制的概念UNIX系統(tǒng)進(jìn)程

21、控制（主要）： fork() 創(chuàng)建子進(jìn)程 sleep() 進(jìn)程睡眠(shumin) exit() （子）進(jìn)程自已終止（自殺） wait() （父）等待子進(jìn)程終止 wakeup() 進(jìn)程喚醒52共一百二十頁(yè)4.3.2 進(jìn)程(jnchng)創(chuàng)建進(jìn)程(jnchng)創(chuàng)建系統(tǒng)調(diào)用： create(name,priority,start-addr)UNIX系統(tǒng)： fork()53共一百二十頁(yè)4.3.2 進(jìn)程(jnchng)創(chuàng)建54共一百二十頁(yè)nextPCB3nextPCB11nextPCB2 PCBnReady-q-startnextPCB67nextPCB22nextPCB34 PCBmall-q-s

22、tartnextPCBk進(jìn)程創(chuàng)建(chungjin)后相應(yīng)數(shù)據(jù)結(jié)構(gòu)變化55共一百二十頁(yè)4.3.3 進(jìn)程(jnchng)撤消進(jìn)程完成(wn chng)其任務(wù)，希望終止時(shí)，調(diào)用撤消進(jìn)程的系統(tǒng)調(diào)用撤消進(jìn)程。相當(dāng)于一個(gè)人死亡后，家人要去派出所消戶口。一般情況：killUNIX系統(tǒng)：exit() 56共一百二十頁(yè)4.3.3 進(jìn)程(jnchng)撤消算法:kill（）輸入:無(wú)輸出:無(wú) 取得當(dāng)前(dngqin)進(jìn)程標(biāo)識(shí)符；釋放本進(jìn)程占用的資源；從總鏈隊(duì)列中摘下本進(jìn)程的，并釋放；調(diào)用進(jìn)程調(diào)度程序；57共一百二十頁(yè)4.3.3 進(jìn)程(jnchng)撤消all-q-startall-q-nextall-q-next

23、all-q-next PCB1PCB2PCB3PCB158共一百二十頁(yè)all-q-startall-q-nextall-q-nextall-q-next PCB1PCB2PCB3PCB14.3.3 進(jìn)程(jnchng)撤消59共一百二十頁(yè)4.3.4 進(jìn)程(jnchng)掛起當(dāng)因等待某個(gè)事件的發(fā)生而不能繼續(xù)運(yùn)行時(shí)，將調(diào)用進(jìn)程(jnchng)掛起操作，進(jìn)程(jnchng)狀態(tài)置為阻塞狀態(tài)，并調(diào)用進(jìn)程(jnchng)調(diào)度程序（等于讓出處理機(jī)）。在UNIX系統(tǒng)中進(jìn)程掛起調(diào)用sleep(chan, pri)。60共一百二十頁(yè)4.3.4 進(jìn)程(jnchng)掛起調(diào)用進(jìn)程掛起操作是在進(jìn)程處于運(yùn)行狀態(tài)下執(zhí)行(

24、zhxng)的。它的執(zhí)行(zhxng)將引起等待某事件的隊(duì)列的改變。例如，進(jìn)程是因等待打印機(jī)而進(jìn)入阻塞狀態(tài)，則該進(jìn)程將加入到等待打印機(jī)的隊(duì)列。61共一百二十頁(yè)4.3.4 進(jìn)程(jnchng)掛起UNIX系統(tǒng)： sleep(chan,pri)； chan 進(jìn)程掛起（睡眠）的原因； pri 進(jìn)程被喚醒后的優(yōu)先數(shù) 一般(ybn)調(diào)用形式： susp(chan) chan 進(jìn)程等待的原因62共一百二十頁(yè)4.3.4 進(jìn)程(jnchng)掛起算法 susp（chan） 輸入：chan 等待的原因(yunyn) 輸出：無(wú) 進(jìn)程現(xiàn)場(chǎng)信息PCB； 進(jìn)程狀態(tài)置為“阻塞”； 插入到等待 “chan”等待隊(duì)列； 調(diào)用

25、進(jìn)程調(diào)度程序； 63共一百二十頁(yè)4.3.4 進(jìn)程(jnchng)掛起nextPCB3nextPCB11nextPCB2 PCBnwait-lpt-q-startnextPCBj next 64共一百二十頁(yè)4.3.5 進(jìn)程(jnchng)喚醒當(dāng)某事件發(fā)生后，系統(tǒng)將喚醒等待該事件發(fā)生的進(jìn)程，由進(jìn)程喚醒操作完成。例如(lr)，打印機(jī)完成中斷處理程序，在完成了打印完成的操作后，就去檢查等待打印機(jī)的隊(duì)列，若不為空，則調(diào)用進(jìn)程喚醒操作，喚醒一個(gè)（或多個(gè)）等待打印機(jī)的進(jìn)程。 65共一百二十頁(yè)4.3.5 進(jìn)程(jnchng)喚醒進(jìn)程(jnchng)喚醒原語(yǔ)的形式： wakeup(chan)； chan 喚醒進(jìn)

26、程阻塞的原因。66共一百二十頁(yè)4.3.5 進(jìn)程(jnchng)喚醒算法：wakeup輸入：chan:等待的事件（阻塞原因） 輸出：無(wú) 找到chan的等待隊(duì)列的指針； for(該隊(duì)列不為(b wi)空） 從隊(duì)列中移出一個(gè)進(jìn)程； 置進(jìn)程狀態(tài)為“就緒”，并加入到就緒隊(duì)列； 67共一百二十頁(yè)4.3.5 進(jìn)程(jnchng)喚醒把等待在chan事件上的所有進(jìn)程喚醒，類似于UNIX系統(tǒng)的處理方式。只喚醒一個(gè)等待chan事件的進(jìn)程，等待隊(duì)列就要按某種策略(cl)排隊(duì)。進(jìn)程喚醒操作會(huì)引起就緒隊(duì)列和等待chan事件的等待隊(duì)列發(fā)生變化。68共一百二十頁(yè)4.4進(jìn)程(jnchng)的相互制約關(guān)系產(chǎn)生相互(xingh)

27、制約關(guān)系的原因有二： 資源共享 進(jìn)程合作69共一百二十頁(yè)4.5 進(jìn)程(jnchng)互斥4.5.1 互斥的概念1. 臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。 引例中的電話和打印機(jī)都屬于臨界資源。除此之外，還有內(nèi)存變量、指針(zhzhn)、數(shù)組等等也是臨界資源。70共一百二十頁(yè)4.5.1 互斥的概念(ginin)2、臨界區(qū)：每個(gè)進(jìn)程(jnchng)中訪問(wèn)臨界資源的段程序段稱為臨界區(qū)（臨界段）。ab進(jìn)程AC d進(jìn)程Bef進(jìn)程CQ71共一百二十頁(yè)4.5.1 互斥的概念(ginin)進(jìn)入臨界區(qū)的準(zhǔn)則：(1) 每次至多有一個(gè)進(jìn)程處于臨界區(qū)；(2)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間(

28、shjin)內(nèi)使其進(jìn)入；(3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間。72共一百二十頁(yè)4.5.1 互斥的概念(ginin)互斥定義當(dāng)某一進(jìn)程正在訪問(wèn)某臨界區(qū)時(shí)，就不允許其它進(jìn)程進(jìn)入，否則就會(huì)發(fā)生無(wú)法估計(jì)的錯(cuò)誤。進(jìn)程之間的這種相互制約的關(guān)系(gun x)稱為互斥。例如：飛機(jī)定票系統(tǒng)中的機(jī)票庫(kù)73共一百二十頁(yè)4.5.2 鎖和上鎖(shn su)、開(kāi)鎖操作鎖操作(cozu)：1.考察鎖位的值；2.若原來(lái)的值是為“0”，將鎖位置為“1”（占用該資源）；3.若原來(lái)值是為“1”，（該資源已被占用），則轉(zhuǎn)到1。開(kāi)鎖操作：將鎖位置為“0”，稱為開(kāi)鎖操作。每個(gè)臨界資源設(shè)一個(gè)鎖位: 0:資源可用 1:資源占用74共一百二

29、十頁(yè)4.5.2 鎖和上鎖(shn su)、開(kāi)鎖操作算法：lock輸入(shr)：w （鎖變量）輸出：無(wú) test：if（w=1）/* 測(cè)鎖位值 */ goto test； else w=1；/* 上鎖鏈*/ 算法：unlock輸入：w （鎖變量）輸出：無(wú) w=0；/* 開(kāi)鎖 */ 75共一百二十頁(yè)4.5.2 鎖和上鎖、開(kāi)鎖操作改進(jìn)(gijn)的算法算法：lock（w）輸入：W（鎖變量(binling)）輸出：無(wú) if（w = 1） sleep(pri,w); W = 1； /* 上鎖 */ 算法：unlock（w）輸入：W（鎖變量）輸出：無(wú) if（等待W隊(duì)列不空） wakeup(w)； W =

30、 0； /* 開(kāi)鎖 */ 76共一百二十頁(yè)4.5.3 用上鎖(shn su)原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥假設(shè)(jish)有兩個(gè)進(jìn)程共享打印機(jī)，兩個(gè)進(jìn)程中使用打印機(jī)的程序段為臨界區(qū)。為保證打印的正確，設(shè)置打印機(jī)的鎖位print，其初值為“0”，表示打印機(jī)可。77共一百二十頁(yè)4.5.3 用上鎖(shn su)原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥main（） int print = 0； cobeginm ppa（）； ppb（）； coend ppa（） ； lock（print）； 使用(shyng)打印機(jī)； unlock（print）； ； ppb（） ； lock（print）； 使用打印機(jī)； unlock（p

31、rint）； ； 78共一百二十頁(yè)4.6 信號(hào)燈和P、V操作(cozu)4.6.1 信號(hào)燈的概念信號(hào)燈的概念(ginin)是由Dijkstra提出的（1968）。79共一百二十頁(yè)4.6.1 信號(hào)燈的概念(ginin)信號(hào)燈的定義：信號(hào)燈是一個(gè)確定的二元組（s,q），s 是一個(gè)具有非負(fù)初值的整型變量，q 是一個(gè)初始狀態(tài)為空的排隊(duì)站。 S代表資源的實(shí)體。在實(shí)際應(yīng)用(yngyng)中應(yīng)準(zhǔn)確地說(shuō)明s的意義和初值，每個(gè)信號(hào)燈都有一個(gè)等待隊(duì)列，其初始狀態(tài)為空。80共一百二十頁(yè)4.6.2 P、V操作(cozu)信號(hào)燈的值僅能由P、V操作(cozu)來(lái)改變，對(duì)信號(hào)燈的P操作記為：P(S)對(duì)信號(hào)燈的V操作記為：

32、V(S) P(S)和V(S)是操作系統(tǒng)程序。81共一百二十頁(yè)4.6.2 P、V操作(cozu)P操作(cozu)：（1）s值減1；（2）若相減結(jié)果大于等于0，則進(jìn)程繼續(xù)執(zhí)行；（3）若結(jié)果小于0，則該進(jìn)程掛起。算法 P輸入：s 輸出：無(wú)p（s） s - -； if （ s0 ） 進(jìn)程掛起； 原子操作82共一百二十頁(yè)4.6.2 P、V操作(cozu)V操作(cozu)：（1）s值加1；（2）若相加結(jié)果大于0，進(jìn)程繼續(xù)執(zhí)行；（3）否則，喚醒一個(gè)或多個(gè)等待該信號(hào)燈的進(jìn)程，然后本進(jìn)程繼續(xù)執(zhí)行。算法 v輸入：s 輸出：無(wú)v（s） s + +； if （ s=0 ） 喚醒等待S進(jìn)程； 原子操作83共一百二十

33、頁(yè)4.6.3 用信號(hào)燈實(shí)現(xiàn)(shxin)進(jìn)程互斥用兩個(gè)進(jìn)程共享打印機(jī)的例子(l zi)。 設(shè)信號(hào)燈mutex表示打印機(jī)，初值為1，表示打印機(jī)可用。(mutxe也可理解為互斥的信號(hào)燈）84共一百二十頁(yè)4.6.3 用信號(hào)燈實(shí)現(xiàn)(shxin)進(jìn)程互斥main（） int mutex = 1； cobeginm ppa（）； ppb（）； coend ppa（） ； p（mutex）； 使用(shyng)打印機(jī)； v（mutex）； ； ppb（） ； p（mutex）； 使用打印機(jī)； v（mutex）； ； 兩個(gè)進(jìn)程共用打印機(jī)mutex（1、0、-1）1：打印機(jī)空閑；0：有一個(gè)進(jìn)程正在使用打印機(jī)-1

34、：有一個(gè)進(jìn)程正在使用打印機(jī)，還有一個(gè)進(jìn)程等待使用打印機(jī)85共一百二十頁(yè)4.7 進(jìn)程同步(tngb)4.7.1 同步(tngb)的例子引例(yn l) 1 ：兩位同學(xué)約好星期天去東湖，早上8:00在校門(mén)口，不見(jiàn)不散。當(dāng)一個(gè)同學(xué)先來(lái)到校門(mén)口，要等另一個(gè)同學(xué)，到齊后一道打的去東湖。86共一百二十頁(yè)4.7.2 同步(tngb)的概念互斥的概念來(lái)自于諸進(jìn)程對(duì)獨(dú)占使用資源（設(shè)備）的競(jìng)爭(zhēng)同步源于多個(gè)進(jìn)程的合作在人類社會(huì)(shhu)中競(jìng)爭(zhēng)與合作是永恒的87共一百二十頁(yè)4.7.2 同步(tngb)的概念同步： 同步就是(jish)并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要相互等待與互通消息，這樣的相互制約關(guān)系稱為進(jìn)程同步。

35、88共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步同步可歸納為：諸進(jìn)程合作完成(wn chng)某工作的邏輯順序。對(duì)系統(tǒng)資源的共享。89共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步一. 合作進(jìn)程的執(zhí)行須序描述諸進(jìn)程合作完成某一任務(wù)的執(zhí)行順序(shnx)圖稱為進(jìn)程流圖。S程序開(kāi)始F程序結(jié)束程序執(zhí)行90共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步91共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)(shxin)進(jìn)程的同步用信號(hào)燈及P、V操作來(lái)描述左圖1、說(shuō)明進(jìn)程的同步(tngb)關(guān)系 進(jìn)程P1、P2可并行執(zhí)行，P3的執(zhí)行必須等待P1、P2都完成后才能開(kāi)始執(zhí)行

36、。2、設(shè)置信號(hào)燈，說(shuō)明含義、初值。 s13 = 0 表示進(jìn)程P1尚未執(zhí)行完成； s23 = 0 表示進(jìn)程P2尚未執(zhí)行完成；92共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步P1( ) ; v(s13); P2( ) ; v(s23); P3( ) p(s13); p(s23); .;main（） int s13，s23； cobegin p1；p2；p3； coend93共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步二. 共享緩沖區(qū)的合作(hzu)設(shè)緩沖區(qū)buffer，大小為一個(gè)字節(jié)，CP進(jìn)程不斷產(chǎn)生字符，送buffer；IOP進(jìn)程從buffer中取出字符打印。

37、不加任何控制？buffercpIOP94共一百二十頁(yè)P(yáng)1:設(shè)置日期P2:顯示/bin/ls目錄P3:打印程序結(jié)束main（） int re_code,k,lk,processorname;if(k = fork() = 0) exec(“/bin/date”, “NOV.25 2004”,0); /* 設(shè)置日期(rq) */if(lk = fork() = 0) exec(“/bin/ls”,”-l”,”/bin”,0); /* 以長(zhǎng)格式列“/bin/ls”目錄 */processorname = wait(&re_code); printf(“程序結(jié)束 n”); exit(0);SFP1P2

38、P395共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)進(jìn)程(jnchng)的同步要保證(bozhng)打印結(jié)果的正確，CP、IOP必須同步：當(dāng)CP把結(jié)果送入buffer后，IOP才能從buffer中取，否則IOP必須等待；當(dāng)IOP從buffer中取走數(shù)據(jù)后，CP才能將新產(chǎn)生數(shù)據(jù)送buffer，否則也必須等待。96共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)(shxin)進(jìn)程的同步解決這個(gè)問(wèn)題的步驟：(1)分析問(wèn)題，弄清楚同步關(guān)系(gun x)，如上分析；(2)設(shè)置信號(hào)燈，說(shuō)明含義、初值；(3)寫(xiě)出程序描述。97共一百二十頁(yè)4.7.3 用信號(hào)燈實(shí)現(xiàn)(shxin)進(jìn)程的同步main（） int sb=1，sa； c

39、obeging cp(); iop(); coend iop() while(打印(d yn)未完成） p（sa）； 從緩沖區(qū)中取字節(jié)； v（sb）； 打?。?cp() while(計(jì)算未完成） 產(chǎn)生一個(gè)字節(jié)； p（sb）； 字節(jié)送緩沖區(qū)； v（sa）； sb = 1，緩沖區(qū)空閑； sa = 0，緩沖區(qū)無(wú)打印字節(jié)。？！放映顯示98共一百二十頁(yè)4.7.4 生產(chǎn)者消費(fèi)者問(wèn)題(wnt)倉(cāng)庫(kù)有n個(gè)貨位生產(chǎn)者制造產(chǎn)品(chnpn)，并送倉(cāng)庫(kù)消費(fèi)者從倉(cāng)庫(kù)中取產(chǎn)品消費(fèi)buffer1.ncp1cp2cpnIOP1IOP2IOPm99共一百二十頁(yè)4.7.4 生產(chǎn)者消費(fèi)者問(wèn)題(wnt)生產(chǎn)者：產(chǎn)生一個(gè)數(shù)據(jù)送入bu

40、f時(shí)，要檢查buf是否已滿，若未滿，則送入數(shù)據(jù)，否則，等待(dngdi)；消費(fèi)者：當(dāng)去取數(shù)據(jù)時(shí)，要檢查buf中是否有數(shù)據(jù)，若有則取一個(gè)數(shù)據(jù)，否則，等待。典型的進(jìn)程同步。同時(shí)，buf是臨界資源，因此，諸進(jìn)程對(duì)buf操作是互斥的.100共一百二十頁(yè)4.7.4 生產(chǎn)者消費(fèi)者問(wèn)題(wnt)Full：緩沖區(qū)產(chǎn)品數(shù)目(shm)，初值為0；Empty：緩沖區(qū)可存放產(chǎn)品的空位，初值為n；Mutex：緩沖區(qū)互斥信號(hào)燈，初值為1。main（） int full，empty=n； int mutex=1； cobegin producer（）； consumer（）； coend； 101共一百二十頁(yè)4.7.4 生

41、產(chǎn)者消費(fèi)者問(wèn)題(wnt)Consumer（） while（還要繼續(xù)(jx)消費(fèi)） p（full）； p（mutex）； 從緩沖區(qū)中取出一個(gè)產(chǎn)品； v（mutex）； v（empty）； 消費(fèi)產(chǎn)品； producer（） while（生產(chǎn)未完成） 生產(chǎn)一個(gè)產(chǎn)品； p（empty）； p（mutex）； 將產(chǎn)品放入緩沖區(qū)； v（mutex）； v（full）； 102共一百二十頁(yè)讀者和編者(binzh)問(wèn)題有十個(gè)讀者和兩個(gè)編輯同時(shí)處理一篇文章(wnzhng)，對(duì)于讀操作是可以同時(shí)進(jìn)行的；若有讀者正在讀，編輯就不能工作；若編輯正在處理，讀者就不能讀，編輯與編輯的工作也是互斥的，試用信號(hào)燈及P、V操作

42、描述讀者與編輯之間協(xié)同工作，并給出類C程序。103共一百二十頁(yè)mail（） int mutey=1，couter=0； cobegin readi（）； editeri（）； coend readi() if(couter = = 0) p(mutex); couter +; 讀文章(wnzhng)； couter -; if(couter = 0) v(muter); editi() p(mutex); 處理(chl)文章; v(mutex); mutex：互斥信號(hào)燈，初值為1。一種解法，正確嗎？104共一百二十頁(yè)mutex:用于讀者與編輯(binj)、編輯(binj)與編輯(binj)的互

43、斥信號(hào)燈，初值為1mutex1:用于對(duì)couter操作的互斥的信號(hào)燈，初值為1。讀者、編輯(binj)問(wèn)題正解105共一百二十頁(yè)mail（） int mutex1= mutex=1， couter； cobegin readi（）； editeri（）； coend readi() p(mutex1); couter +; if(couter = = 1) p(mutex); v(mutex1); 讀文章(wnzhng)； p(mutex1); couter -; if(couter = 0) v(muter); v(mutex1) editi() p(mutex); 處理(chl)文章; v

44、(mutex); 106共一百二十頁(yè)讀者編者問(wèn)題(wnt)-單向通道管制 一個(gè)南北方向的橋梁的交通管制系統(tǒng)規(guī)定，在橋上不允許有相對(duì)行使的車(chē)輛，但同一個(gè)方向允許有多個(gè)車(chē)輛行使。試用信號(hào)燈及P、V操作來(lái)描述(mio sh)這個(gè)橋梁兩端的交通管制，要求用一種結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言寫(xiě)出程序描述(mio sh)。 107共一百二十頁(yè)讀者編者問(wèn)題(wnt)-單向通道管制信號(hào)燈設(shè)置(shzh)：mutex：互斥信號(hào)燈，初值為1。橋上只能單向通；scmuter：南橋頭計(jì)數(shù)器互斥信號(hào)燈，初值為1；ncmuter：北橋頭計(jì)數(shù)器互斥信號(hào)燈，初值為1；108共一百二十頁(yè)main( ) Int muter，cmuter,

45、 ncmuter, scouter,ncouter; muter=ncmuter=scmuter=1; cobegin sb( ); nb( ); coend 109共一百二十頁(yè)Sb( ) /* 橋南端(nn dun)控制程序*/ p(scmuter); scoter+; if(scouter=1) P(muter); v(scmuter); 車(chē)輛向北行過(guò)橋； p(scmuter); scoter-; if(scouter=0) v（muter); v(scmuter); nb( ) /* 橋北端控制程序*/ p(ncmuter); ncoter+; If(ncouter=1) P(muter); v(ncmuter); 車(chē)輛(chling)向南行過(guò)橋； p(nc muter); ncouter-; If(ncouter=0) v（muter); v(ncmuter); 110共一百二十頁(yè)十個(gè)計(jì)算進(jìn)程、2個(gè)打印進(jìn)程，共享10個(gè)緩沖區(qū)，計(jì)算進(jìn)程：申請(qǐng)一個(gè)空閑緩沖區(qū)，生產(chǎn)的數(shù)據(jù)存入緩沖區(qū)