進(jìn)程管理解析

第二章進(jìn)程管理2.1進(jìn)程的引入2.2進(jìn)程概念2.3進(jìn)程控制2.4進(jìn)程互斥2.5進(jìn)程同步2.6

UNIX系統(tǒng)進(jìn)程管理

在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可以并發(fā)執(zhí)行，同時(shí)它們又要共享系統(tǒng)中的資源，這些資源有些是可共享使用的，如磁盤，有些是以獨(dú)占方式使用的，如打印機(jī)。由此將會(huì)引起一系列的矛盾，產(chǎn)生錯(cuò)綜復(fù)雜的相互制約的關(guān)系。

產(chǎn)生這種錯(cuò)綜復(fù)雜的相互制約關(guān)系的原因有二：

資源共享

進(jìn)程合作進(jìn)程的相互制約關(guān)系2.4進(jìn)程互斥

2.4.1互斥的概念

引例：宿舍電話的使用打印機(jī)的使用

1.臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。引例中的電話和打印機(jī)都屬于臨界資源。除此之外，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源。2、臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的那段程序段稱為臨界區(qū)（臨界段）。３．互斥定義:在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某臨界區(qū)時(shí)，就不允許其它進(jìn)程進(jìn)入，否則就會(huì)發(fā)生(后果)無法估計(jì)的錯(cuò)誤。我們把進(jìn)程之間的這種相互制約的關(guān)系稱為互斥。例如：飛機(jī)定票系統(tǒng)中的機(jī)票庫(kù)進(jìn)入臨界區(qū)的準(zhǔn)則：(1)每次至多有一個(gè)進(jìn)程處于臨界區(qū)；(2)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入；(3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間。

解決進(jìn)程互斥的最簡(jiǎn)單的辦法是加鎖。

在系統(tǒng)中為每個(gè)臨界資源設(shè)置一個(gè)鎖位，

0表示資源可用，

1表示資源已被占用（不可用）。這樣當(dāng)一個(gè)進(jìn)程使用某個(gè)臨界資源之前必須完成下列操作：1、考察鎖位的值；2、若原來的值是為“0”，將鎖位置為“1”（占用該資源）；3、若原來值是為“1”，（該資源已被別人占用），則轉(zhuǎn)到1。當(dāng)進(jìn)程使用完資源后，將鎖位置為“0”，稱為開鎖操作。2.4.2鎖和上鎖、開鎖操作改進(jìn)的算法2.4.3用上鎖原語和開鎖原語實(shí)現(xiàn)互斥設(shè)有兩個(gè)進(jìn)程共享打印機(jī)，兩個(gè)進(jìn)程中使用打印機(jī)的程序段為臨界區(qū)。為保證打印的正確，設(shè)置打印機(jī)的鎖位print,其初值為“0”，表示打印機(jī)可用。2.5信號(hào)燈和P、V操作信號(hào)燈的概念是由Dijkstra提出的（1968）。把互斥的關(guān)鍵概念抽象到信號(hào)量這個(gè)概念中，信號(hào)量是一個(gè)被保護(hù)的變量，只有P操作、V操作和一種稱為信號(hào)量初始化操作才能訪問和改變它的值。2.5.1信號(hào)燈的概念信號(hào)燈是一個(gè)確定的二元組（s,q），s是一個(gè)具有非負(fù)初值的整型變量，q是一個(gè)初始狀態(tài)為空的隊(duì)列。

S代表資源的實(shí)體。在實(shí)際應(yīng)用中應(yīng)準(zhǔn)確地說明s的意義和初值，每個(gè)信號(hào)燈都有一個(gè)隊(duì)列，其初始狀態(tài)為空。信號(hào)燈的定義：

2.5.2P、V操作信號(hào)燈的值僅能由P、V操作來改變，對(duì)信號(hào)燈的P操作記為：P(S)，P操作是一個(gè)原子操作。對(duì)信號(hào)燈的V操作記為：V(S),V操作是一個(gè)原子操作。在實(shí)際操作系統(tǒng)中，一般情況下是由機(jī)器硬件提供P、V操作的指令，當(dāng)然是原子操作，若機(jī)器不提供P、V操作的指令，則操作系統(tǒng)提供P、V操作原語。P操作：（1）s值減1；（2）若相減結(jié)果大于等于0，則進(jìn)程繼續(xù)執(zhí)行；（3）若結(jié)果小于0，則該進(jìn)程掛起。注：推起該進(jìn)程包括：保留調(diào)用進(jìn)程CPU現(xiàn)場(chǎng)；置“等待”狀態(tài)；入等待隊(duì)列；轉(zhuǎn)進(jìn)程調(diào)度；V操作：（1）s值加1；（2）若相加結(jié)果大于0，進(jìn)程繼續(xù)執(zhí)行；（3）否則，喚醒一個(gè)（或多個(gè)）等待該信號(hào)燈的進(jìn)程，然后本進(jìn)程繼續(xù)執(zhí)行。2.5.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用兩個(gè)進(jìn)程共享打印機(jī)的例子設(shè)信號(hào)燈print表示打印機(jī)，初值為1，表示打印機(jī)可用(也可理解為有一臺(tái)打印機(jī))。(print也是用于互斥的信號(hào)燈，教材上設(shè)置為mutex。)2.6進(jìn)程同步

2.6.1同步的例子引例1.兩位同學(xué)約好星期天去東湖，早上8:00在校門口，不見不散。當(dāng)一個(gè)同學(xué)先來到校門口，要等另一個(gè)同學(xué)，到齊后一道打的去東湖。2.6.2同步的概念互斥的概念來自于諸進(jìn)程對(duì)獨(dú)占使用資源（設(shè)備）的競(jìng)爭(zhēng)，同步來源于多個(gè)進(jìn)程的合作。在人類社會(huì)中競(jìng)爭(zhēng)與合作是永恒的。

同步：所謂同步就是并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要相互等待與互通消息，這樣的相互制約關(guān)系稱為進(jìn)程同步。2.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步在操作系統(tǒng)中，同步有各種各樣，但歸納起來有兩類：諸進(jìn)程合作完成某工作的邏輯順序；對(duì)系統(tǒng)資源的共享。如兩個(gè)進(jìn)程共享一個(gè)緩沖區(qū)完成謄抄問題（一）合作進(jìn)程的執(zhí)行次序用進(jìn)程流圖來描述諸進(jìn)程合作完成某一任務(wù)的次序，其規(guī)則如下：用信號(hào)燈及P、V操作來描述左圖1、說明進(jìn)程的同步關(guān)系進(jìn)程P1、P2可并行執(zhí)行，P3的執(zhí)行必須等待P1、P2都完成后才能開始執(zhí)行。2、設(shè)置信號(hào)燈，說明含義、初值。

s13=0表示進(jìn)程P1尚未執(zhí)行完成；

s23=0表示進(jìn)程P2尚未執(zhí)行完成；思考1司機(jī)進(jìn)程：while(1){啟動(dòng)車輛正常駕駛到站停車}…售票員進(jìn)程：while(1){關(guān)門售票開門}…用P.V操作解決司機(jī)與售票員的問題解設(shè)有兩個(gè)信號(hào)量S1，S2，初值均為0。司機(jī)進(jìn)程：while(1){

P(S1)啟動(dòng)車輛正常駕駛

到站停車

V(S2)}…售票員進(jìn)程：while(1){關(guān)門

V(S1)售票

P(S2)開門}…(二）共享緩沖區(qū)的合作進(jìn)程的同步設(shè)有一個(gè)緩沖區(qū)buffer，大小為一個(gè)字節(jié)，CP進(jìn)程不斷產(chǎn)生字符，送buffer，IOP進(jìn)程從buffer中取出字符打印。如不加控制，會(huì)有多種打印結(jié)果，這取決于這兩個(gè)進(jìn)程運(yùn)行的相對(duì)速度。在這眾多的打印結(jié)果中，只有CP、IOP進(jìn)程的運(yùn)行剛好匹配的一種是對(duì)的，其它均為錯(cuò)誤，并且不能重現(xiàn)。要保證打印結(jié)果的正確，CP、IOP必須遵循以下同步規(guī)則：(1)當(dāng)CP把結(jié)果送入buffer后，IOP才能從buffer中取，否則IOP必須等待；(2)當(dāng)IOP從buffer中取走數(shù)據(jù)后，CP才能將新產(chǎn)生數(shù)據(jù)送buffer，否則也必須等待。解決這個(gè)問題的步驟：(1)分析問題，弄清楚同步關(guān)系；(2)設(shè)置信號(hào)燈，說明含義、初值；(3)寫出程序描述。思考2用P.V操作解決下圖之同步問題提示：分別考慮對(duì)緩沖區(qū)S和T的同步，再合并考慮getcopyputst解設(shè)置四個(gè)信號(hào)量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）{

P(Sin）;

將數(shù)放入S;

V(Sout);}copy：while（1）{

P(Sout）;P(Tin）;

將數(shù)從S取出放入T;

V(Tout);V(Sin);}put：while（1）{

P(Tout）;

將數(shù)從T取走;

V(Tin);}思考3桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個(gè)蘋果或放一個(gè)桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。試用P、V操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。提示：設(shè)置一個(gè)信號(hào)量表示可否向盤中放水果，一個(gè)信號(hào)量表示可否取桔子，一個(gè)信號(hào)量表示可否取蘋果。解 設(shè)置三個(gè)信號(hào)量S,So,Sa，初值分別為1，0，0。分別表示可否向盤中放水果，可否取桔子，可否取蘋果。Father(){while(1){

p(S);

將水果放入盤中;

if(是桔子)v(So);elsev(Sa);}

}Son(){while(1){p(So)

取桔子

v(S);

吃桔子;}}Daughter(){while(1){p(Sa)

取蘋果

v(S);

吃蘋果;}}吃水果問題桌上有一只盤子，每次只能放一個(gè)水果，爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，則爸爸或媽媽可向盤中放水果，僅當(dāng)盤中有自己需要的水果時(shí)，兒子或女兒可從中取出，請(qǐng)給出四人之間的同步關(guān)系，并用P、V操作實(shí)現(xiàn)四人正確活動(dòng)的程序。四人之間的關(guān)系爸爸，媽媽要互斥使用盤子，所以兩者之間是互斥關(guān)系；爸爸放的蘋果，女兒吃，所以兩者是同步關(guān)系；媽媽放的桔子，兒子吃，所以兩者也是同步關(guān)系。

semaphores,sa,so=1,0,0;father(){while(1)P(s);putanapple;V(sa);}son(){while(1)P(so);getanorange;V(s);}mother(){while(1)P(s);putanorange;V(so);}daught(){while(1)P(sa);getanapple;V(s);}設(shè)信號(hào)量s表示是否有空盤子，信號(hào)量sa表示兒子能否取蘋果，so表示女兒能否取桔子2.6.4生產(chǎn)者－消費(fèi)者問題假定緩沖區(qū)buffer是一個(gè)有界緩沖區(qū)，可存放n個(gè)數(shù)據(jù)，同時(shí)假定有n個(gè)CP進(jìn)程不斷地產(chǎn)生數(shù)據(jù)，并送buffer；有m個(gè)IOP進(jìn)程從緩沖區(qū)中取數(shù)據(jù)打印。在我們生活中有很多這樣的例子。對(duì)于生產(chǎn)者進(jìn)程：產(chǎn)生一個(gè)數(shù)據(jù)，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿，若未滿，則可將數(shù)據(jù)送入緩沖區(qū)，并通知消費(fèi)者進(jìn)程；否則，等待；對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取數(shù)據(jù)時(shí)，要看緩沖區(qū)中是否有數(shù)據(jù)可取，若有則取走一個(gè)數(shù)據(jù)，并通知生產(chǎn)者進(jìn)程，否則，等待。這種相互等待，并互通信息就是典型的進(jìn)程同步。同時(shí)，緩沖區(qū)是個(gè)臨界資源，因此，諸進(jìn)程對(duì)緩沖區(qū)的操作程序是一個(gè)共享臨界區(qū)，因此，還有個(gè)互斥的問題。圖書館閱覽室問題假定閱覽室最多可同時(shí)容納100個(gè)人閱讀，讀者進(jìn)入時(shí)，必須在閱覽室門口的一個(gè)登記表上登記，內(nèi)容包括姓名、座號(hào)等，離開時(shí)要撤掉登記內(nèi)容。用P、V操作描述讀者進(jìn)程的同步算法。

(分析：讀者有任意多個(gè)，但進(jìn)入閱覽室閱讀最多為100人，為此可設(shè)一個(gè)信號(hào)量s，代表空座位的數(shù)目；另登記表為臨界資源，需設(shè)一個(gè)用于互斥的信號(hào)量mutex,防止2個(gè)及以上的讀者進(jìn)程同時(shí)對(duì)此表訪問。對(duì)于每個(gè)讀者的動(dòng)作包括進(jìn)入、閱讀、離開。)ints=100,mutex=1;readeri()(i=1,2,…,k){while(1){P(s);P(mutex);查登記表，置某座位為占用；V(mutex);……reading;……P(mutex);查登記表，置某座位為空;V(mutex);V(s);}}讀者寫者問題有十個(gè)讀者和兩個(gè)編輯同時(shí)處理一篇文章，對(duì)于讀操作是可以同時(shí)進(jìn)行的，若有讀者正在讀這篇文章，編輯就不能工作，若編輯正在處理這篇文章，讀者就不能作讀操作，編輯與編輯的工作也是互斥的，試用信號(hào)燈及P、V操作寫出讀者與編輯之間協(xié)同工作的程序描述。分析：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待讀者/寫者問題的解法設(shè)兩個(gè)信號(hào)量mutex=1，mutex1=1另設(shè)一個(gè)全局變量readcount=0mutex用于讀者和寫者、寫者和寫者之間的互斥readcount表示正在讀的讀者數(shù)目mutex1用于對(duì)readcount這個(gè)臨界資源的互斥訪問哲學(xué)家就餐問題有五個(gè)哲學(xué)家圍坐在一圓桌旁，每人面前有碗飯，每?jī)扇酥g放一只筷子；每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃飯；為了吃飯，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子。設(shè)fork[5]為5個(gè)信號(hào)量，初值為均1Philosopheri：while(1){

思考；

P(fork[i]);P(fork[(i+1)%5])；

進(jìn)食；

V(fork[i]);V(fork[(i+1)%5])；}解以上解法會(huì)出現(xiàn)死鎖為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)去拿左邊的筷子僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之

分析設(shè)fork[5]為5個(gè)信號(hào)量，初值為均1；設(shè)置信號(hào)量S限制同時(shí)進(jìn)餐的哲學(xué)家的數(shù)目，初值為4Philosopheri：while(1){

思考；P(S);

P(fork[i]);P(fork[(i+1)%5])；

進(jìn)食；

V(fork[i]);V(fork[(i+1)%5])；V(S);}