操作系统实验报告生产者与消费者算法实现.doc

1、操作系统课程设计生产者与消费者算法实现目 录实验一 生产者-消费者1一、设计思想描述1二、生产者与消费者实现代码2三、实验结果4四、心得体会5实验二 进程调度模拟程序6一、实验设计思想6二、算法中用到的数据结构7三、实验代码8四、实验结果14五、结果分析15六、实验总结15实验三 银行家算法16一、设计思想16二、算法描述及数据结构模型16三、数据结构17四、源代码17五、程序运行结果及分析23实验四 内存管理模拟系统25一、设计思想25二、算法用到的主要数据结构25三、模块调试27四、测试结果31实验一 生产者-消费者一、设计思想描述3.1生产者功能描述 在同一个进程地址空间内执行的两个线程

2、。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。3.2消费者功能描述消费者线程从缓冲区中获得物品，然后释放缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。3.3程序结构图： 二、生产者与消费者实现代码#include #include const unsigned short SIZE_OF_BUFFER = 10; /缓冲区长度unsigned short ProductID = 0; /产品号unsigned short

3、 ConsumeID = 0; /将被消耗的产品号unsigned short in = 0; /产品进缓冲区时的缓冲区下标unsigned short out = 0; /产品出缓冲区时的缓冲区下标int g_bufferSIZE_OF_BUFFER; /缓冲区是个循环队列bool g_continue = true; /控制程序结束HANDLE g_hMutex; /用于线程间的互斥HANDLE g_hFullSemaphore; /当缓冲区满时迫使生产者等待HANDLE g_hEmptySemaphore; /当缓冲区空时迫使消费者等待DWORD WINAPI Producer(LPVO

4、ID); /生产者线程DWORD WINAPI Consumer(LPVOID); /消费者线程int main() /创建各个互斥信号 g_hMutex = CreateMutex(NULL,FALSE,NULL); g_hFullSemaphore = CreateSemaphore(NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL); g_hEmptySemaphore = CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL); /调整下面的数值，可以发现，当生产者个数多于消费者个数时， /生产速度快，生产者经常

5、等待消费者；反之，消费者经常等待 const unsigned short PRODUCERS_COUNT = 3; /生产者的个数 const unsigned short CONSUMERS_COUNT = 1; /消费者的个数 /总的线程数 const unsigned short THREADS_COUNT = PRODUCERS_COUNT+CONSUMERS_COUNT; HANDLE hThreadsPRODUCERS_COUNT; /各线程的handle DWORD producerIDCONSUMERS_COUNT; /生产者线程的标识符 DWORD consumerIDTH

6、READS_COUNT; /消费者线程的标识符 /创建生产者线程 for (int i=0;iPRODUCERS_COUNT;+i) hThreadsi=CreateThread(NULL,0,Producer,NULL,0,&producerIDi); if (hThreadsi=NULL) return -1; /创建消费者线程 for (i=0;iCONSUMERS_COUNT;+i) hThreadsPRODUCERS_COUNT+i=CreateThread(NULL,0,Consumer,NULL,0,&consumerIDi); if (hThreadsi=NULL) retur

7、n -1; while(g_continue) if(getchar() /按回车后终止程序运行 g_continue = false; return 0;/生产一个产品。简单模拟了一下，仅输出新产品的ID号void Produce() std:cerr Producing +ProductID . ; std:cerr Succeed std:endl;/把新生产的产品放入缓冲区void Append() std:cerr Appending a product . ; g_bufferin = ProductID; in = (in+1)%SIZE_OF_BUFFER; std:cerr

8、Succeed std:endl; /输出缓冲区当前的状态 for (int i=0;iSIZE_OF_BUFFER;+i) std:cout i : g_bufferi; if (i=in) std:cout - 生产; if (i=out) std:cout - 消费; std:cout std:endl; /从缓冲区中取出一个产品void Take() std:cerr Taking a product . ; ConsumeID = g_bufferout; out = (out+1)%SIZE_OF_BUFFER; std:cerr Succeed std:endl; /输出缓冲区当

9、前的状态 for (int i=0;iSIZE_OF_BUFFER;+i) std:cout i : g_bufferi; if (i=in) std:cout - 生产; if (i=out) std:cout - 消费; std:cout std:endl; /消耗一个产品void Consume() std:cerr Consuming ConsumeID . ; std:cerr Succeed std:endl;/生产者DWORD WINAPI Producer(LPVOID lpPara) while(g_continue) WaitForSingleObject(g_hFullS

10、emaphore,INFINITE); WaitForSingleObject(g_hMutex,INFINITE); Produce(); Append(); Sleep(1500); ReleaseMutex(g_hMutex); ReleaseSemaphore(g_hEmptySemaphore,1,NULL); return 0; 三、实验结果/* 一个消费者三个生产者：四、心得体会本次课程设是关于生产者与消费者之间互斥和同步的问题。问题的实质是P、V操作，实验设一个共享缓冲区，生产者和消费者互斥的使用，当一个线程使用缓冲区的时候，另一个让其等待直到前一个线程释放缓冲区为止。 生产者

11、与消费者是一个与现实有关的经典问题，与“和尚挑水”问题的原理相同，通过此原理举一反三可以解决其他类似的问题。 通过本课程设计，我们对操作系统的p、v进一步的认识，深入的了解p、v操作的实质和其重要性。课本的理论知识进一步阐述了现实中的实际问题。 实验中，我们小组分工合作，共同学习，虽然在课程设计中遇到了一些问题，但在老师和同学的细心指导和热心帮助下解决了。同时，了解到团队精神的重要性，也为以后的学习和工作打下了坚实的基础，同时积累了宝贵的经验。 实验二 进程调度模拟程序一、实验设计思想将每个进程抽象成一个控制块PCB， PCB用一个结构体描述。构建一个进程调度类。将进程调度的各种算法分装在一个

12、类中。类中存在三个容器，一个保存正在或未进入就绪队列的进程，一个保存就绪的进程，另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、完成容器。当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入各个进程的信息，这些信息保存到进程容器中。进程信息输入完毕后，就开始了进程调度，每调度一次判断就绪队列是否为空，若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。二、算法中用到的数据结构struct fcfs /先来先服务算法

13、从这里开始 char name10; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; ; /定义一个结构体，里面包含的有一个进程相关的信息 1. 主要的常量变量vectorm_ProcessQueue;/进程输入队列vectorm_WaitQueue;/进程就绪队列vectorm_FinishQueue;/完成队列vector:iterator m_iter;/迭代器PCB m_runProcess;/运行中的进程int m_Process

14、Count;/进程数float m_RunTime;/运行时间int m_tagIsRun;/是否在运行标志。表示正在运行，表示没有float m_TimeSlice;/时间片大小int m_TimeSliceCount;/指时间片轮转中一次分到的时间片个数char m_SchedulerAlgorithm;/调度算法2. 主要模块void PCBInput();/输入进程信息void PCBSort();/对进程控制块按照优先级排序(采用冒泡排序)void ProcessSelect();/若当前就绪队列不为空则根据选择的调度算法开始调度。否则，系统时间加.以等待新的进程到来void PCB

15、Display();/打印当前状况下。就绪队列、完成队列、运行中的进程信息void ProcessRun();/进程运行一次。运行时间加个时间片。并判断进程是否达到完成条件。若是则ProcessStatus=f.否则为w;void ProcessQueueProcess();/查看当前时间下，有无进程加入。若有则把该进程调入就绪队列void ProcessDispatch();/进程分派，进程执行完成后决定进程该进入哪个队列(就绪、完成)void TimePast() m_RunTime +=m_TimeSlice; ProcessQueueProcess();/当前系统时间加个时间片，并检查

16、是否有新的进程加入void SchedulerStatistics();/调度统计，计算周转时间等void FCFS();/先来先服务void SJF();/最短进程优先调度void RR();/简单时间片轮转void PD();/最高优先数优先三、实验代码#include #include #include using namespace std;struct fcfs /先来先服务算法从这里开始 char name10; float arrivetime; float servicetime; float starttime; float finishtime; float zztime;

17、 float dqzztime; ; /定义一个结构体，里面包含的有一个进程相关的信息 fcfs a100; void input(fcfs *p,int N) int i; coutendl; printf( 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)nn); for(i=0;i=N-1;i+) printf( 请您输入进程%d的信息:t,i+1);scanf(ttt%s%f%f,&pi.name,&pi.arrivetime,&pi.servicetime); void Print(fcfs *p,float arrivetime,float serviceti

18、me,float starttime,float finishtime,float zztime,float dqzztime,int N) int k; printf(nn调用先来先服务算法以后进程运行的顺序是: ); printf(%s,p0.name); for(k=1;k%s,pk.name); coutendl; printf(n 具体进程调度信息:n); printf(t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间n); for(k=0;k=N-1;k+) printf(t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2

19、fn,pk.name,pk.arrivetime, pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime); getchar(); /此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪 void sort(fcfs *p,int N) /排序 for(int i=0;i=N-1;i+) for(int j=0;j=i;j+) if(pi.arrivetimepj.arrivetime) fcfs temp; temp=pi; pi=pj; pj=temp; void deal(fcf

20、s *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) /运行阶段 int k; for(k=0;k=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetim

21、e; for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; void FCFS(fcfs *p,int N) float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arriveti

22、me,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); /先来先服务算法到此结束 struct sjf/最短进程优先调度算法从这里开始 char name10;float arrivetime; /到达时间float servicetime; /运行时间float starttime; /开始时间float finishtime; /完成时间;sjf a1100;void input(sjf *p,int N1)/进程信息输入 int i;coutendl; printf( 请您输入进程的 名字 到达时间 服务时间:

23、 (例如: a 0 100)n); for(i=0;i=N1-1;i+) printf( 请您输入进程%d的信息:t,i+1); scanf(ttt%s%f%f,&pi.name,&pi.arrivetime,&pi.servicetime);void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)/最终结果输出 int k; printf(nt调用最短进程优先调度算法以后进程的调度顺序为:); printf(%s,p0.name); for(k=1;k%s,pk.

24、name); coutendl; printf(n给个进程具体调度信息如下:n); printf(nt进程名t到达时间t运行时间t开始时间t完成时间n); for(k=0;k=N1-1;k+) printf( t%st %-.2ftt %-.2ftt %-.2ftt %-.2ftn,pk.name,pk.arrivetime, pk.servicetime,pk.starttime,pk.finishtime); getchar(); void sort(sjf *p,int N1)/排序 for(int i=0;i=N1-1;i+) for(int j=0;j=i;j+) if(pi.arr

25、ivetimepj.arrivetime) sjf temp; temp=pi; pi=pj; pj=temp; void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)/运行阶段 int k; for(k=0;k=N1-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+float(pk.servicetime)/60; else pk.starttime=pk-1.finis

26、htime; pk.finishtime=pk-1.finishtime+float(pk.servicetime)/60; void sjff(sjf *p,int N1) float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;mN1-1;m+) if(m=0) pm.finishtime=pm.arrivetime+float(pm.servicetime)/60; else pm.finishtime=pm-1.finishtime+float(pm.servicetime)/

27、60; int i=0; for(int n=m+1;n=N1-1;n+) if(pn.arrivetime=pm.finishtime) i+; float min=pm+1.servicetime; int next=m+1; for(int k=m+1;km+i;k+) if(pk+1.servicetimemin) min=pk+1.servicetime; next=k+1; sjf temp; temp=pm+1; pm+1=pnext; pnext=temp; deal(p,arrivetime,servicetime,starttime,finishtime,N1); Prin

28、t(p,arrivetime,servicetime,starttime,finishtime,N1); getchar();/最短进程优先调度算法到这里结束 char menu()/用来输出相关信息的函数 char cse1; while(1) system(cls); fflush(stdin); coutendl; coutendl; coutt| 欢迎 |endl ; coutt| |endl ; coutt|t 实 验 一 进 程 调 度 算 法 实 验tt|endl; coutt| |endl ; coutt|tt 1.先来先服务调度算法 tt|endl; coutt| |endl

29、 ; coutt|tt 2.最短进程优先调度算法tt|endl; coutt| |endl ; coutt| |endl ; coutendl; coutendl; couttt 请输入您的选择（1/2）：; cse1=getchar(); if(cse12) cout你的输入有错！endl; else break; int main(int argc, char *argv) while(1) switch(menu() case 1: int N; coutendl; coutendl; printf(ttn); coutendl; printf(输入进程数目:); scanf(%d,&N); input(a,N); FCFS(a,N); case 2: int N1; coutendl; coutendl; printf(ttn); coutNeedi，n，则