計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：生產(chǎn)者-消費(fèi)者問(wèn)題的模擬實(shí)現(xiàn)專業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師完成日期信 息 工 程 學(xué) 院13操作系統(tǒng)課程設(shè)計(jì)（2015）目 錄1 概述21.1 設(shè)計(jì)目的21.2 設(shè)計(jì)要求22 設(shè)計(jì)原理22.1 P、V操作同步機(jī)構(gòu)22.2生產(chǎn)者消費(fèi)者問(wèn)題32.3進(jìn)程控制塊PCB42.4處理器的模擬43 概要設(shè)計(jì)53.1 功能結(jié)構(gòu)53.2 模塊劃分54 詳細(xì)設(shè)計(jì)54.1初始化程序模塊設(shè)計(jì)54.2 處理器調(diào)度程序模塊設(shè)計(jì)64.3 模擬處理器執(zhí)行程序模塊設(shè)計(jì)75 測(cè)試與分析85.1 測(cè)試方案85.2 測(cè)試結(jié)果85.3 結(jié)果分析96 設(shè)計(jì)小結(jié)97 參考文獻(xiàn)10附錄 源程序代碼11 題目：生產(chǎn)者-

2、消費(fèi)者問(wèn)題的模擬實(shí)現(xiàn)1 概述1.1 設(shè)計(jì)目的進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，進(jìn)程是并發(fā)執(zhí)行的，也即系統(tǒng)中的多個(gè)進(jìn)程輪流地占用處理器運(yùn)行。把若干個(gè)進(jìn)程都能進(jìn)行訪問(wèn)和修改的那些變量稱為公共變量。 由于進(jìn)程是并發(fā)地執(zhí)行的，所以，如果對(duì)進(jìn)程訪問(wèn)公共變量不加限制，那么就會(huì)產(chǎn)生“與時(shí)間有關(guān)”的錯(cuò)誤，即進(jìn)程執(zhí)行后所得到的結(jié)果與訪問(wèn)公共變量的時(shí)間有關(guān)。為了防止這類錯(cuò)誤，系統(tǒng)必須要用同步機(jī)構(gòu)來(lái)控制進(jìn)程對(duì)公共變量的訪問(wèn)。一般說(shuō)，同步機(jī)構(gòu)是由若干條原語(yǔ)（同步原語(yǔ)）所組成。本設(shè)計(jì)要求學(xué)生模擬進(jìn)程的并發(fā)執(zhí)行和 PV 操作同步機(jī)構(gòu)的實(shí)現(xiàn)，且用 P、V 操作解決生產(chǎn)者消費(fèi)者問(wèn)題，了解進(jìn)程并發(fā)執(zhí)行時(shí)同步機(jī)構(gòu)的作用。1.

3、2 設(shè)計(jì)要求a)每個(gè)生產(chǎn)者和消費(fèi)者對(duì)有界緩沖區(qū)進(jìn)行操作后,即時(shí)顯示有界緩沖區(qū)的全部?jī)?nèi)容,當(dāng)前指針位置和生產(chǎn)者/消費(fèi)者進(jìn)程的標(biāo)識(shí)符。b)生產(chǎn)者和消費(fèi)者各有兩個(gè)以上。 c)多個(gè)生產(chǎn)者或多個(gè)消費(fèi)者之間須有共享對(duì)緩沖區(qū)進(jìn)行操作的函數(shù)代碼（注意互斥與同步）。2 設(shè)計(jì)原理2.1 P、V 操作同步機(jī)構(gòu)由 P 操作原語(yǔ)和 V 操作原語(yǔ)組成，它們的定義如下：P 操作原語(yǔ) P (s)：將信號(hào)量 s 減去 1，若結(jié)果小于 0，則執(zhí)行原語(yǔ)的進(jìn)程被置成等待信號(hào)量 s 的狀態(tài)。V 操作原語(yǔ) V(s)：將信號(hào)量 s 加 1，若結(jié)果不大于 0，則釋放一個(gè)等待信號(hào)量 s的進(jìn)程。這兩條原語(yǔ)是如下的兩個(gè)過(guò)程：procedure p

4、 (var s:semaphore);begin s: =s-1;if s<0then W(s)end pprocedure v (var s:semaphore);egin s: =s+1;if s0then R (s)end v其中 W（s）表示將調(diào)用過(guò)程的進(jìn)程置為等待信號(hào)量 s 的狀態(tài)；R（s）表示釋放一個(gè)等待信號(hào)量 s 的進(jìn)程。在系統(tǒng)初始化時(shí)應(yīng)把 semaphore 定義為某個(gè)類型，為簡(jiǎn)單起見(jiàn)，在模擬實(shí)習(xí)中可把上述的 semaphore 直接改成 integer。2.2生產(chǎn)者消費(fèi)者問(wèn)題假定有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，生產(chǎn)者每次生產(chǎn)一件產(chǎn)品，并把生產(chǎn)的產(chǎn)品存入共享緩沖器以供消費(fèi)者取走

5、使用。 消費(fèi)者每次從緩沖器內(nèi)取出一件產(chǎn)品去消費(fèi)。禁止生產(chǎn)者將產(chǎn)品放入已滿的緩沖器內(nèi)，禁止消費(fèi)者從空緩沖器內(nèi)取產(chǎn)品。 假定緩沖器內(nèi)可同時(shí)存放 10 件產(chǎn)品。那么，用 PV 操作來(lái)實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的同步，生產(chǎn)者和消費(fèi)者兩個(gè)進(jìn)程的程序如下：B:array 0.9of products;s1, s2; semaphore;s1: =10, s2: =0;in, out:integer;in: =0; out: =0;cobeginprocedure producer;c:products;beginL1:Produce (c);P (s1);Bin: =C;in: =(in+1)mod 10;V

6、(s2);goto L1end;procedure consumer;x:products;begin L2:p (s2);x: =Bout;out: =(out+1) mod10;v (s1);consume (x);goto L2end;coend.其中的semaphore和products是預(yù)先定義的兩個(gè)類型，在模擬實(shí)現(xiàn)中semaphore用integer代替，products可用integer或char等代替。2.3進(jìn)程控制塊 PCB為了記錄進(jìn)程執(zhí)行時(shí)的情況，以及進(jìn)程讓出處理器后的狀態(tài)，斷點(diǎn)等信息，每個(gè)進(jìn)程都有一個(gè)進(jìn)程控制塊 PCB。在模擬實(shí)習(xí)中，假設(shè)進(jìn)程控制塊的結(jié)構(gòu)如圖 1-3 所示

7、。 其中進(jìn)程的狀態(tài)有：運(yùn)行態(tài)、 就緒態(tài)、等待態(tài)和完成態(tài)。 當(dāng)進(jìn)程處于等待態(tài)時(shí)，在進(jìn)程控制塊 PCB 中要說(shuō)明進(jìn)程等待原因（在模擬設(shè)計(jì)中進(jìn)程等待原因是為等待信號(hào)量 s1 或 s2）；當(dāng)進(jìn)程處于等待態(tài)或就緒態(tài)時(shí)，PCB 中保留了斷點(diǎn)信息，一旦進(jìn)程再度占有處理器則就從斷點(diǎn)位置繼續(xù)運(yùn)行；當(dāng)進(jìn)程處于完成狀態(tài)，表示進(jìn)程執(zhí)行結(jié)束。圖1-3 進(jìn)程控制塊結(jié)構(gòu)進(jìn)程名狀態(tài)等待原因斷點(diǎn)2.4處理器的模擬計(jì)算機(jī)硬件提供了一組機(jī)器指令，處理器的主要職責(zé)是解釋執(zhí)行機(jī)器指令。為了模擬生產(chǎn)者和消費(fèi)者進(jìn)程的并發(fā)執(zhí)行，我們必須模擬一組指令和處理職能。模擬的一組指令見(jiàn)表 1-1 所示，其中每條指令的功能由一個(gè)過(guò)程來(lái)實(shí)現(xiàn)。用變量 PC

8、 來(lái)模擬“指令計(jì)數(shù)器”，假設(shè)模擬的指令長(zhǎng)度為 1，每執(zhí)行一條模擬指令后，PC 加 1，提出下一條指令地址。使用模擬的指令，可把生產(chǎn)者和消費(fèi)者進(jìn)程的程序表示為表 1-2 所示的形式。定義兩個(gè)一維數(shù)組 PA0.4和 SA0.4，每個(gè) PAi存放生產(chǎn)者程序中的一條模擬指令執(zhí)行的入口地址；每個(gè) SAi存放消費(fèi)者程序中的一條模擬指令執(zhí)行的入口地址。于是模擬處理器執(zhí)行一條指令的過(guò)程為：取出 PC 之值，按 PAPC或 SAPC得模擬指令執(zhí)行的入口地址，將 PC 之值加 1，轉(zhuǎn)向由入口地址確定的相應(yīng)的過(guò)程執(zhí)行。表1-1模擬的處理器指令模擬的指令功能p(s)執(zhí)行P操作原語(yǔ)v(s)執(zhí)行V操作原語(yǔ)putBin:=

9、product;in:=(in+1) mod 10GETx:=Bout; out:=(out+1) mod 10produce輸入一個(gè)字符放入 C 中consume打印或顯示 x 中的字符GOTO LPC: =LNOP 空操作表1-2生產(chǎn)者和消費(fèi)者程序序號(hào)生產(chǎn)者程序消費(fèi)者程序0producep (s2)1p (s1) GET2PUT v (s1)3v (s2) consume4goto 0 goto 03 概要設(shè)計(jì)3.1 功能結(jié)構(gòu)生產(chǎn)者功能描述：在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行兩個(gè)線程。生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)。當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒(méi)有空緩沖區(qū)可用，

10、那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放出一個(gè)空緩沖區(qū)。消費(fèi)者功能描述：消費(fèi)者線程從緩沖區(qū)獲得物品，然后釋放緩沖區(qū)，當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒(méi)有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻塞，直到新的物品被生產(chǎn)出來(lái)。3.2 模塊劃分程序可以分成三個(gè)模塊：a.初始化程序模塊b.處理器調(diào)度程序模塊c.模擬處理器執(zhí)行程序模塊4 詳細(xì)設(shè)計(jì)4.1初始化程序模塊設(shè)計(jì)創(chuàng)建各個(gè)互斥信號(hào)；創(chuàng)建生產(chǎn)者，消費(fèi)者線程；設(shè)置緩沖區(qū)長(zhǎng)度；設(shè)置生產(chǎn)者和消費(fèi)者個(gè)數(shù)。可以發(fā)現(xiàn)，當(dāng)生產(chǎn)者個(gè)數(shù)多于消費(fèi)者個(gè)數(shù)時(shí)，生產(chǎn)速度快，生產(chǎn)者經(jīng)常等待消費(fèi)者；反之，消費(fèi)者經(jīng)常等待。設(shè)置按回車后終止程序運(yùn)行。數(shù)據(jù)定義及其詳細(xì)解釋：const unsigned

11、short SIZE_OF_BUFFER = 20; /緩沖區(qū)長(zhǎng)度 unsigned short ProductID = 0; /產(chǎn)品號(hào) unsigned short ConsumeID = 0; /將被消耗的產(chǎn)品號(hào) unsigned short in = 0; /產(chǎn)品進(jìn)緩沖區(qū)時(shí)的緩沖區(qū)下標(biāo) unsigned short out = 0; /產(chǎn)品出緩沖區(qū)時(shí)的緩沖區(qū)下標(biāo) int g_bufferSIZE_OF_BUFFER; /緩沖區(qū)是個(gè)循環(huán)隊(duì)列 bool g_continue = true; /使程序跳出循環(huán)，控制程序結(jié)束 HANDLE g_hMutex; /用于線程間的互斥 HANDLE g

12、_hFullSemaphore; /當(dāng)緩沖區(qū)滿時(shí)迫使生產(chǎn)者等待 HANDLE g_hEmptySemaphore; /當(dāng)緩沖區(qū)空時(shí)迫使消費(fèi)者等待 DWORD WINAPI Producer(LPVOID); /生產(chǎn)者線程 DWORD WINAPI Consumer(LPVOID); /消費(fèi)者線程 4.2 處理器調(diào)度程序模塊設(shè)計(jì)生產(chǎn)者線程調(diào)用void Produce()函數(shù)，void Append()函數(shù)，消費(fèi)者線程調(diào)用void Take()函數(shù)，void Consume()函數(shù)，實(shí)現(xiàn)線程間的互斥，當(dāng)緩沖區(qū)滿時(shí)迫使生產(chǎn)者等待，當(dāng)緩沖區(qū)空時(shí)迫使消費(fèi)者等待。生產(chǎn)者流程圖如圖4-2-1：sem=sem

13、-1入口s>=0調(diào)用進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度返回是否 圖4-2-1消費(fèi)者流程圖如圖4-2-2：入 口sem=sem-1 sem=sem-1S<=0喚醒等待隊(duì)列中的一個(gè)進(jìn)程式返回或轉(zhuǎn)進(jìn)程調(diào)度 返回否是圖4-2-24.3 模擬處理器執(zhí)行程序模塊設(shè)計(jì)void Produce()函數(shù)： 簡(jiǎn)單模擬生產(chǎn)一個(gè)產(chǎn)品，僅輸出新產(chǎn)品的ID號(hào)。void Produce() std:cerr << "Producing " << +ProductID << " . " std:cerr << "Succeed

14、" << std:endl;void Append()函數(shù)： 把新生產(chǎn)的產(chǎn)品放入緩沖區(qū)然后輸出緩沖區(qū)當(dāng)前的狀態(tài)。void Append() std:cerr << "Appending a product . " g_bufferin = ProductID; in = (in+1)%SIZE_OF_BUFFER; std:cerr << "Succeed" << std:endl; for (int i=0;i<SIZE_OF_BUFFER;+i) std:cout << i

15、<<": " << g_bufferi; if (i=in) std:cout << " <- 生產(chǎn)" if (i=out) std:cout << " <- 消費(fèi)" std:cout << std:endl; void Take()函數(shù)： 從緩沖區(qū)中取出一個(gè)產(chǎn)品然后輸出緩沖區(qū)當(dāng)前的狀態(tài)。 void Take() std:cerr << "Taking a product . " ConsumeID = g_bufferout; o

16、ut = (out+1)%SIZE_OF_BUFFER; std:cerr << "Succeed" << std:endl; for (int i=0;i<SIZE_OF_BUFFER;+i) std:cout << i <<": " << g_bufferi; if (i=in) std:cout << " <- 生產(chǎn)" if (i=out) std:cout << " <- 消費(fèi)" std:cout <

17、< std:endl; void Consume()函數(shù)：模擬消耗一個(gè)產(chǎn)品。 void Consume() std:cerr << "Consuming " << ConsumeID << " . " std:cerr << "Succeed" << std:endl; 5 測(cè)試與分析5.1 測(cè)試方案在C+環(huán)境下運(yùn)行程序，創(chuàng)建一個(gè)控制臺(tái)進(jìn)程，在該進(jìn)程中創(chuàng)建線程模擬生產(chǎn)者和消費(fèi)者，實(shí)現(xiàn)進(jìn)程(線程)的同步與互斥。模擬實(shí)現(xiàn)生產(chǎn)一個(gè)新產(chǎn)品放入緩沖區(qū)，從緩沖區(qū)中取出一個(gè)產(chǎn)品消費(fèi)。

18、由于緩沖區(qū)是個(gè)循環(huán)隊(duì)列，按回車后終止程序運(yùn)行。5.2 測(cè)試結(jié)果運(yùn)行結(jié)果如圖5-2-1圖5-2-15.3 結(jié)果分析該程序設(shè)置的緩沖區(qū)數(shù)據(jù)長(zhǎng)度為10，生產(chǎn)者個(gè)數(shù)為3，消費(fèi)者個(gè)數(shù)為1，程序啟動(dòng)后，生產(chǎn)者先進(jìn)行生產(chǎn)，當(dāng)3個(gè)生產(chǎn)者全部生產(chǎn)完之后，消費(fèi)者開(kāi)始從緩沖區(qū)中取出產(chǎn)品，當(dāng)消費(fèi)者取出一個(gè)后，生產(chǎn)者開(kāi)始繼續(xù)生產(chǎn)，當(dāng)生產(chǎn)完3個(gè)之后，消費(fèi)者開(kāi)始從緩沖池中取產(chǎn)品，依次循環(huán)。即，只有在生產(chǎn)者生產(chǎn)了產(chǎn)品并將產(chǎn)品存放到緩沖池中消費(fèi)者才能去消費(fèi)，當(dāng)緩沖池為空時(shí)消費(fèi)者不能消費(fèi)6 設(shè)計(jì)小結(jié)本次課程設(shè)計(jì)主要是對(duì)操作系統(tǒng)中線程，進(jìn)程同步互斥等知識(shí)的應(yīng)用，生產(chǎn)者消費(fèi)者問(wèn)題是很著名的同步問(wèn)題，的確是既簡(jiǎn)單又復(fù)雜。此次編寫的程序

19、基本實(shí)現(xiàn)了設(shè)計(jì)要求的功能。通過(guò)本次課程設(shè)計(jì)，我對(duì)本學(xué)期所學(xué)的操作系統(tǒng)課程有了更深刻的理解，加強(qiáng)了對(duì)基礎(chǔ)的實(shí)踐運(yùn)用能力，加深對(duì)進(jìn)程同步問(wèn)題的認(rèn)識(shí)與理解，再次熟悉了VC的使用，提高了分析問(wèn)題、解決問(wèn)題的能力，讓我能把所學(xué)的知識(shí)融會(huì)貫通。對(duì)于老師提出的關(guān)于程序的一點(diǎn)修改及改進(jìn)仍未能解答出來(lái)，但是給我一點(diǎn)時(shí)間，我相信以后定能理解。7 參考文獻(xiàn)1 韓立毛，李先鋒. 計(jì)算機(jī)操作系統(tǒng)實(shí)踐教程M，南京：南京大學(xué)出版社，2011.10.2 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)M，北京：清華大學(xué)出版社，1997.3 張堯?qū)W，史美林. 計(jì)算機(jī)操作系統(tǒng)教程M，北京：清華大學(xué)出版社，2000.8.4 孫靜宇. 計(jì)算機(jī)操作系統(tǒng)課程

20、設(shè)計(jì)指導(dǎo)書M，山西：太原理工出版社，2006.4.附錄 源程序代碼#include <windows.h>#include <iostream>const unsigned short SIZE_OF_BUFFER = 10; /緩沖區(qū)長(zhǎng)度unsigned short ProductID = 0; /產(chǎn)品號(hào)unsigned short ConsumeID = 0; /將被消耗的產(chǎn)品號(hào)unsigned short in = 0; /產(chǎn)品進(jìn)緩沖區(qū)時(shí)的緩沖區(qū)下標(biāo)unsigned short out = 0; /產(chǎn)品出緩沖區(qū)時(shí)的緩沖區(qū)下標(biāo)int g_bufferSIZE_OF_

21、BUFFER; /緩沖區(qū)是個(gè)循環(huán)隊(duì)列bool g_continue = true; /控制程序結(jié)束HANDLE g_hMutex; /用于線程間的互斥HANDLE g_hFullSemaphore; /當(dāng)緩沖區(qū)滿時(shí)迫使生產(chǎn)者等待HANDLE g_hEmptySemaphore; /當(dāng)緩沖區(qū)空時(shí)迫使消費(fèi)者等待DWORD WINAPI Producer(LPVOID); /生產(chǎn)者線程DWORD WINAPI Consumer(LPVOID); /消費(fèi)者線程int main() /創(chuàng)建各個(gè)互斥信號(hào) g_hMutex = CreateMutex(NULL,FALSE,NULL); g_hFullSem

22、aphore = CreateSemaphore(NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL); g_hEmptySemaphore = CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL); /調(diào)整下面的數(shù)值，可以發(fā)現(xiàn)，當(dāng)生產(chǎn)者個(gè)數(shù)多于消費(fèi)者個(gè)數(shù)時(shí)， /生產(chǎn)速度快，生產(chǎn)者經(jīng)常等待消費(fèi)者；反之，消費(fèi)者經(jīng)常等待 const unsigned short PRODUCERS_COUNT = 3; /生產(chǎn)者的個(gè)數(shù) const unsigned short CONSUMERS_COUNT = 1; /消費(fèi)者的個(gè)數(shù) /總的

23、線程數(shù) const unsigned short THREADS_COUNT = PRODUCERS_COUNT+CONSUMERS_COUNT; HANDLE hThreadsPRODUCERS_COUNT; /各線程的handle DWORD producerIDCONSUMERS_COUNT; /生產(chǎn)者線程的標(biāo)識(shí)符 DWORD consumerIDTHREADS_COUNT; /消費(fèi)者線程的標(biāo)識(shí)符 /創(chuàng)建生產(chǎn)者線程 for (int i=0;i<PRODUCERS_COUNT;+i) hThreadsi=CreateThread(NULL,0,Producer,NULL,0,&am

24、p;producerIDi); if (hThreadsi=NULL) return -1; /創(chuàng)建消費(fèi)者線程 for ( i=0;i<CONSUMERS_COUNT;+i) hThreadsPRODUCERS_COUNT+i=CreateThread(NULL,0,Consumer,NULL,0,&consumerIDi); if (hThreadsi=NULL) return -1; while(g_continue) if(getchar() /按回車后終止程序運(yùn)行 g_continue = false; return 0;/生產(chǎn)一個(gè)產(chǎn)品。簡(jiǎn)單模擬了一下，僅輸出新產(chǎn)品的ID

25、號(hào)void Produce() std:cerr << "Producing " << +ProductID << " . " std:cerr << "Succeed" << std:endl;/把新生產(chǎn)的產(chǎn)品放入緩沖區(qū)void Append() std:cerr << "Appending a product . " g_bufferin = ProductID; in = (in+1)%SIZE_OF_BUFFER; std:cerr &

26、lt;< "Succeed" << std:endl; /輸出緩沖區(qū)當(dāng)前的狀態(tài) for (int i=0;i<SIZE_OF_BUFFER;+i) std:cout << i <<": " << g_bufferi; if (i=in) std:cout << " <- 生產(chǎn)" if (i=out) std:cout << " <- 消費(fèi)" std:cout << std:endl; /從緩沖區(qū)中取出一個(gè)產(chǎn)品void Take() std:cerr << "Taking a product . " ConsumeID = g_bufferout; out = (out+1)%SIZE_OF_BUFFER; std:cerr << "Succeed" << std:endl; /輸出緩沖區(qū)當(dāng)前的狀態(tài) for (int i=0;i<