生產(chǎn)者消費(fèi)者問題操作系統(tǒng)課程設(shè)計(jì)報告

1、-. z. . . . 資料 . .目錄 TOC o 1-3 h z u HYPERLINK l _Toc4406165241 緒論 PAGEREF _Toc440616524 h 3HYPERLINK l _Toc4406165251.1 實(shí)現(xiàn)的功能 PAGEREF _Toc440616525 h 3HYPERLINK l _Toc4406165261.2 P V 操作 PAGEREF _Toc440616526 h 3HYPERLINK l _Toc4406165272 生產(chǎn)者消費(fèi)者問題。 PAGEREF _Toc440616527 h 4HYPERLINK l _Toc440616528

2、2.1 要求 PAGEREF _Toc440616528 h 4HYPERLINK l _Toc4406165292.2 生產(chǎn)者和消費(fèi)者兩個進(jìn)程的程序 PAGEREF _Toc440616529 h 4HYPERLINK l _Toc4406165302.3進(jìn)程控制塊PCB。 PAGEREF _Toc440616530 h 5HYPERLINK l _Toc4406165312.4處理器的模擬。 PAGEREF _Toc440616531 h 5HYPERLINK l _Toc4406165322.5程序設(shè)計(jì) PAGEREF _Toc440616532 h 6HYPERLINK l _Toc4

3、406165333設(shè)計(jì)步驟 PAGEREF _Toc440616533 h 7HYPERLINK l _Toc4406165343.1課程分析 PAGEREF _Toc440616534 h 7HYPERLINK l _Toc4406165353.1.2 流程圖 PAGEREF _Toc440616535 h 7HYPERLINK l _Toc4406165363.1.3 測試程序 PAGEREF _Toc440616536 h 9HYPERLINK l _Toc440616537測試結(jié)果分析 PAGEREF _Toc440616537 h 14HYPERLINK l _Toc44061653

4、85 結(jié)論 PAGEREF _Toc440616538 h 15HYPERLINK l _Toc440616539參考文獻(xiàn) PAGEREF _Toc440616539 h 161 緒論生產(chǎn)者-消費(fèi)者問題是一個經(jīng)典的進(jìn)程同步問題，該問題最早由Dijkstra提出，用以演示他提出的信號量機(jī)制。模擬實(shí)現(xiàn)用同步機(jī)構(gòu)防止發(fā)生進(jìn)程執(zhí)行時可能出現(xiàn)的與時間有關(guān)的錯誤。進(jìn)程是程序在一個數(shù)據(jù)集合上運(yùn)行的過程，進(jìn)程是并發(fā)執(zhí)行的，也即系統(tǒng)中的多個進(jìn)程輪流地占用處理器運(yùn)行。我們把假設(shè)干個進(jìn)程都能進(jìn)展和修改的那些變量稱為公共變量。由于進(jìn)程是并發(fā)地執(zhí)行的，所以，如果對進(jìn)程公共變量不加限制，則就會產(chǎn)生“與時間有關(guān)的錯誤，即進(jìn)

5、程執(zhí)行后所得到的結(jié)果與公共變量的時間有關(guān)。為了防止這類錯誤，系統(tǒng)必須要用同步機(jī)構(gòu)來控制進(jìn)程對公共變量的。一般說，同步機(jī)構(gòu)是由假設(shè)干條原語同步原語所組成。本實(shí)習(xí)要求學(xué)生模擬PV操作同步機(jī)構(gòu)的實(shí)現(xiàn)，模擬進(jìn)程的并發(fā)執(zhí)行，了解進(jìn)程并發(fā)執(zhí)行時同步機(jī)構(gòu)的作用。1.1 實(shí)現(xiàn)的功能生產(chǎn)者-消費(fèi)者問題是一個經(jīng)典的進(jìn)程同步問題，有m個生產(chǎn)者和n個消費(fèi)者，它們共享可存放k件產(chǎn)品的緩沖區(qū)。生產(chǎn)者進(jìn)程生產(chǎn)物品，然后將物品放置在一個空緩沖區(qū)中，供消費(fèi)者進(jìn)程消費(fèi)。消費(fèi)者進(jìn)程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)物品時，如果沒有空緩沖區(qū)可用，則生產(chǎn)者進(jìn)程必須等待消費(fèi)者線程釋放出一個空緩沖區(qū)。當(dāng)消費(fèi)者進(jìn)程消費(fèi)物品

6、時，如果沒有滿的緩沖區(qū)，則消費(fèi)者進(jìn)程將被阻塞，直到新的物品被生產(chǎn)出來。1.2 P V 操作(1) PV操作同步機(jī)構(gòu)，由P操作原語和V操作原語組成，它們的定義如下：P操作原語P (s)：將信號量s減去1，假設(shè)結(jié)果小于0，則執(zhí)行原語的進(jìn)程被置成等待信號量s的狀態(tài)。V操作原語V (s)：將信號量s加1，假設(shè)結(jié)果不大于0，則釋放一個等待信號量s的進(jìn)程。這兩條原語是如下的兩個過程：procedure P (var s: semaphore);begin s: = s-1; if s0 then W (s)end pprocedure V(var s: semaphore);egin s: = s+1;

7、if s0 then R (s)end v其中Ws表示將調(diào)用過程的進(jìn)程置為等待信號量s的狀態(tài)；Rs表示釋放一個等待信號量s的進(jìn)程。在系統(tǒng)初始化時應(yīng)把semaphore定義為*個類型，為簡單起見，在模擬實(shí)習(xí)中可把上述的semaphore直接改成integer。2 生產(chǎn)者消費(fèi)者問題。2.1 要求假定有一個生產(chǎn)者和一個消費(fèi)者，生產(chǎn)者每次生產(chǎn)一件產(chǎn)品，并把生產(chǎn)的產(chǎn)品存入共享緩沖器以供消費(fèi)者取走使用。消費(fèi)者每次從緩沖器取出一件產(chǎn)品去消費(fèi)。制止生產(chǎn)者將產(chǎn)品放入已滿的緩沖器，制止消費(fèi)者從空緩沖器以產(chǎn)品。假定緩沖器可同時存放10件產(chǎn)品。則，用PV操作來實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的同步2.2生產(chǎn)者和消費(fèi)者兩個進(jìn)程的

8、程序B: array 0.9 of products;s1, s2; semaphore;s1: =10, s2: =0;in, out: integer;in: =0; out: =0;cobegin procedure producer; c: products; beginL1:produce (c); P (s1); Bin: =C;in: =(in+1)mod 10; V (s2); goto L1 end; procedure consumer; *: products; begin L2: P(s2); *: =Bout; out: =(out+1) mod10; v (s1);

9、 consume (*); goto L2 end;coend.其中的semaphore和products是預(yù)先定義的兩個類型，在模擬實(shí)現(xiàn)中semaphore用integer代替，products可用integer或char等代替。2.3進(jìn)程控制塊PCB。為了記錄進(jìn)程執(zhí)行時的情況，以及進(jìn)程讓出處理器后的狀態(tài)，斷點(diǎn)等信息，每個進(jìn)程都有一個進(jìn)程控制塊PCB。在模擬實(shí)習(xí)中，假設(shè)進(jìn)程控制塊的構(gòu)造如圖1。其中進(jìn)程的狀態(tài)有：運(yùn)行態(tài)、就緒態(tài)、等待態(tài)和完成態(tài)。當(dāng)進(jìn)程處于等待態(tài)時，在進(jìn)程控制塊PCB中要說明進(jìn)程等待原因在模擬實(shí)習(xí)中進(jìn)程等待原因是為等待信號量s1或s2；當(dāng)進(jìn)程處于等待態(tài)或就緒態(tài)時，PCB中保存了斷

10、點(diǎn)信息，一旦進(jìn)程再度占有處理器則就從斷點(diǎn)位置繼續(xù)運(yùn)行；當(dāng)進(jìn)程處于完成狀態(tài)，表示進(jìn)程執(zhí)行完畢。進(jìn)程名狀態(tài)等待原因斷點(diǎn)圖1 進(jìn)程控制塊構(gòu)造2.4處理器的模擬。計(jì)算機(jī)硬件提供了一組機(jī)器指令，處理器的主要職責(zé)是解釋執(zhí)行機(jī)器指令。為了模擬生產(chǎn)者和消費(fèi)者進(jìn)程的并發(fā)執(zhí)行，我們必須模擬一組指令和處理職能。模擬的一組指令見圖2，其中每條指令的功能由一個過程來實(shí)現(xiàn)。用變量PC來模擬“指令計(jì)數(shù)器，假設(shè)模擬的指令長度為1，每執(zhí)行一條模擬指令后，PC加1，提出下一條指令地址。使用模擬的指令，可把生產(chǎn)者和消費(fèi)者進(jìn)程的程序表示為圖3的形式。定義兩個一維數(shù)組PA0.4和SA0.4，每一個PAi存放生產(chǎn)者程序中的一條模擬指令執(zhí)

11、行的入口地址；每個SAi存放消費(fèi)者程序中的一條模擬指令執(zhí)行的入口地址。于是模擬處理器執(zhí)行一條指令的過程為：取出PC之值，按PAPC或SAPC得模擬指令執(zhí)行的入口地址，將PC之值加1，轉(zhuǎn)向由入口地址確定的相應(yīng)的過程執(zhí)行。2.5程序設(shè)計(jì)實(shí)習(xí)中的程序由三局部組成：初始化程序、處理器調(diào)度程序、模擬處理器指令執(zhí)行程序。各局部程序的功能及相互間的關(guān)系由圖4至圖7指出。模擬的指令功 能P(s) 執(zhí)行P操作原語V(s) 執(zhí)行V操作原語PUTBin: =product; in: = (in+1) mod 10GET*: =Bout; out: =(out+1) mod 10produce 輸入一個字符放入C中c

12、onsume 打印或顯示*中的字符GOTO L PC: =LNOP 空操作圖2模擬的一組指令序號生產(chǎn)者程序消費(fèi)者程序0produceP(s2)1P(s1)GET2PUTV(s1)3V(s2)consume4goto 0goto 0圖3 生產(chǎn)者和消費(fèi)者程序初始化程序：模擬實(shí)習(xí)的程序從初始化程序入口啟動，初始化工作包括對信號量s1、s2賦初值，對生產(chǎn)者、消費(fèi)者進(jìn)程的PCB初始化。初始化后轉(zhuǎn)向處理調(diào)度程序，其流程如圖4。處理器調(diào)度程序：在計(jì)算機(jī)系統(tǒng)中，進(jìn)程并發(fā)執(zhí)行時，任一進(jìn)程占用處理器執(zhí)行完一條指令后就有可能被打斷而讓出處理器由其它進(jìn)程運(yùn)行。故在模擬系統(tǒng)中也類似處理，每當(dāng)執(zhí)行一條模擬的指令后，保護(hù)當(dāng)

13、前進(jìn)程的現(xiàn)場，讓它成為非運(yùn)行態(tài)，由處理器調(diào)度程序按隨機(jī)數(shù)再選擇一個就緒進(jìn)程占用處理器運(yùn)行。處理器調(diào)度程序流程見圖5。模擬處理器指令執(zhí)行程序：按“指令計(jì)數(shù)器PC之值執(zhí)行指定的指令，且PC加1指向下一條指令。模擬處理器指令執(zhí)行程序的流程圖見圖6和圖7。 (a) 模擬P (s) (b) 模擬V (s)另外，為了使得模擬程序有一個完畢條件，在圖6中附加了“生產(chǎn)者運(yùn)行完畢的條件判斷，模擬時可以采用人工選擇的方法實(shí)現(xiàn)。圖7給出了Ps和Vs模擬指令執(zhí)行過程的流程。其它模擬指令的執(zhí)行過程已在圖2中指出。3設(shè)計(jì)步驟3.1課程分析3.1.1 根本原理分析假定有一個生產(chǎn)者和一個消費(fèi)者，生產(chǎn)者每次生產(chǎn)一件產(chǎn)品，并把生

14、產(chǎn)的產(chǎn)品存入共享緩沖器以供消費(fèi)者取走使用。消費(fèi)者每次從緩沖器取出一件產(chǎn)品去消費(fèi)。制止生產(chǎn)者將產(chǎn)品放入已滿的緩沖器，制止消費(fèi)者從空緩沖器以產(chǎn)品。假定緩沖器可同時存放10件產(chǎn)品。則，用PV操作來實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的同步3.1.2 流程圖本實(shí)習(xí)中的程序由三局部組成：初始化程序、處理器調(diào)度程序、模擬處理器指令執(zhí)行程序。各局部程序的功能及相互間的關(guān)系由圖初始化流程初始化程序：模擬實(shí)習(xí)的程序從初始化程序入口啟動，初始化工作包括對信號量s1、s2賦初值，對生產(chǎn)者、消費(fèi)者進(jìn)程的PCB初始化。初始化后轉(zhuǎn)向處理調(diào)度程序，其流程如圖3-4。模擬處理器調(diào)度處理器調(diào)度程序：在計(jì)算機(jī)系統(tǒng)中，進(jìn)程并發(fā)執(zhí)行時，任一進(jìn)程占

15、用處理器執(zhí)行完一條指令后就有可能被打斷而讓出處理器由其它進(jìn)程運(yùn)行。故在模擬系統(tǒng)中也類似處理，每當(dāng)執(zhí)行一條模擬的指令后，保護(hù)當(dāng)前進(jìn)程的現(xiàn)場，讓它成為非運(yùn)行態(tài)，由處理器調(diào)度程序按隨機(jī)數(shù)再選擇一個就緒進(jìn)程占用處理器運(yùn)行。模擬處理器指令執(zhí)行模擬處理器指令執(zhí)行程序：按“指令計(jì)數(shù)器PC之值執(zhí)行指定的指令，且PC加1指向下一條指令。模擬處理器指令執(zhí)行程序的流程圖模擬PV操作的執(zhí)行生產(chǎn)者運(yùn)行完畢的條件判斷，模擬時可以采用人工選擇的方法實(shí)現(xiàn)。3.1.3 測試程序*include *include *include *include *define NULL 0struct spcb char name; cha

16、r state; char why; int dd ;typedef struct spcb pcb;pcb producter,consumer,*process,*process1;int s1,s2,i,j,in,out,pc,m;char array10;char c,*;int pa6,sa6;int p(int s) /* p操作原語 */s=s-1;if(sstate=B; /* B表示阻塞*/process-why=s;elseprocess-state=W; /* W表示就緒*/return(s);int v(int s) /*v操作原語*/s=s+1;if(sstate=W

17、;process-state=W;return(s);char RanChar()char arr10=a,b,c,d,e,f,g,h,i,j;return arrabs(rand()%10);void put()/printf(n please product anychar!);/scanf(n%c,&c);Sleep(1000);arrayin=RanChar();in=(in+1)%10;printf( product a char is %c!n ,arrayin-1);int k = 0; for(m=0;m10;m+)if (arraym!= ) printf(%c,arraym

18、);k = k+1; printf(緩沖池中有%d個產(chǎn)品n,k);void get()Sleep(1000);*=arrayout; printf(n%c get a char fron buffer,*);printf(n); arrayout= ;out=(out+1)%10; int k = 0; for(m=0;mname); printf(|%ct,process-state); printf(|%ct,process-why); printf(|%dt,process-dd);printf(n); void init()/*初始化程序*/s1=10;/*s1表示空緩沖區(qū)的數(shù)量*/s

19、2=0; /*s2表示滿緩沖區(qū)的數(shù)量*/=p;/*對生產(chǎn)者進(jìn)程初始化*/producter.state=W;producter.why= ;producter.dd=0;=c;/*對消費(fèi)者進(jìn)程初始化*/consumer.state=W;consumer.why= ;consumer.dd=0;for(int k=0;k10;k+)arrayk = ;void bornpa() /*將生產(chǎn)者程序裝入pa中*/for(i=0;i=3;i+) pai=i;void bornsa()/*將消費(fèi)者程序裝入sa中*/for(i=0;idd;i=pc;/*此時把PC的值付給I*/if(process-name=p)&(process-state=W)j=pai;pc=i+1;sw