《实现生产者消费者问题和实现银行家算法的课程设计.doc》由会员分享，可在线阅读，更多相关《实现生产者消费者问题和实现银行家算法的课程设计.doc（29页珍藏版）》请在三一办公上搜索。
1、操作系统课程设计题目一：实现生产者消费者问题题目二：实现银行家算法 指导老师: * 班 级： *班 学 号： * 姓 名： * 2007年12月12日目 录第一部分：实现生产者与消费者问题一、题目21、课程设计目的22、课程设计要求2二、设计内容2三、开发环境3四、分析设计31、设计原理32、涉及的数据结构53、流程图6五、运行示例及结果分析81、运行示例82、运行结果分析：9六、个人体会9七、附录（源程序）10第二部分：实现银行家算法一、题目14课程设计目的14二、设计内容14三、开发环境14四、分析设计141、预备知识142、设计原理173、涉及的数据结构184、安全检测185、流程图19
2、五、运行示例及结果分析191、运行示例192、运行结果分析：20六、个人体会21七、附录（源程序）21参考文献29第一部分：实现生产者与消费者问题一、题目：实现生产者与消费者问题此问题是经典的进程同步互斥问题，问题描述参见教材第36页和第46页，要求编程实现，生产者放入产品的和消费者取走产品的速度可以调节。1、课程设计目的：在我们所学的操作系统这门课程中，关于经典进程的同步问题进行了一定的描述和探讨，介绍了几个经典的算法，需要我们在实践中学会熟练运用。在生产者与消费者问题中，需要我们了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥解决
3、生产者与消费者的冲突问题。2、课程设计要求：生产者与消费者问题可以算作是经典进程同步问题的典型代表。该课程设计要求运用基于单缓冲区和多缓冲区的生产者与消费者问题的多种实现机制,其中利用了数据结构中的循环队列和堆栈来模拟实现是一种比较容易实现的方法。这种思想能够帮助我们更好的理解所学内容，并加以锻炼我们的动手实践能力,实现它内在具有的超强的参考价值和实践意义。该课程设计通过了解进程间的两种制约关系，从而理解信号量机制；通过对实例的分析和讨论，理解信号量机制实现进程的同步及互斥的方法；通过对经典进程同步问题的剖析，初步掌握运用信号量解决进程同步问题的方法。二、设计内容在同一个进程地址空间内执行的两
4、个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来，我的具体做法也是如此，建立缓冲区，生产者生产的产品放入，消费者从中取产品，如果没有产品，则等待。三、开发环境此程序的设计在Windows XP操作系统下,基于Microsoft Visual C+6.00环境下的一个关于实现生产者与消费者问题的程序。用C语言实现编程。四、分析设计1、设计
5、原理进程同步是指几个进程相互合作，一个进程到达某个点后，除非另一个进程已经完成某些操作，否则就不得不停下来，等待这些操作的结束，这就是进程同步的概念。生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品
6、被生产出来。生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费或生产某类资源，当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。 通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者是相互等效的，只要缓冲区未满，生产者就可以将产品送入缓冲区，类似地，只要缓冲区未空，消费者就可以从缓冲区中去走物品并消费它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。 在生产者消费者问题中，信号灯具有两种功能。首先，它是跟踪资源的生产和消费的计数器；其次，它是协调资源
7、的生产者和消费者之间的同步器。消费者通过再一指派给它的信号灯上做P操作来表示消耗资源，而生产者通过在同一信号灯上做V操作来表示生产资源。再这种信号灯的实施中，计数在每次P操作后减1，而在每次V操作中加1。个这一计数器的初始值是可利用的资源数目。当资源是不可利用时，将申请资源的进程放置在等待队列中。如果有一个资源释放，在等待队列中的第一个进程被唤醒并得到资源的控制权。 为解决这一类生产者消费者问题，设置了两个同步信号灯，一个说明空缓冲区的数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明缓冲区的数目，用full表示，其初制值为0。由于有界缓冲区是一个零界资源，必须互斥使用，所以另外还
8、需设置一个互斥信号灯mutex,起初值为1。 假定在生产者和消费者之间的公用缓冲区中，具有n个缓冲区，这时可以利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者互相等效果，只要缓冲池未满，生产者便可以将消息送入缓冲池；只要缓冲池未空，消费者便可以从缓冲池中取走一个消息。在生产者-消费者问题中应注意：首先，在每个程序中用于互斥的wait(mutex)和signal(mutex)必须成对出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的
9、程序中。生产者与消费者进程共享一个大小固定的缓冲区。其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个或多个消费者从缓冲区中取数据。假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取出数据的存储单元，如图，指针in和out初始化指向缓冲区的第一个存储单元。生产者从第一个存储单元开始存放数据，一次存放一条数据一条数据且in指针向后移一个位置，当in 指针指向第n个存储单元，下一次将指向第一个存储单元，如此循环反复使用缓冲区。消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为
10、“空”，可以被生产者再次使用。每次取走一条数据，out指针向后移一个存储单元位置。试想，如果不控制生产者与消费者，将会产生什么结果？ 1 2 3 4 5 6 7 8 n In out 1 2 3 4 5 6 7 8 n In out 其中，in表示存数据位置，out表示取数据位置： ：被占用单元 ：空存储单元图：生产者/消费者循环使用缓冲区首先，生产者和消费者可能同时进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。这显然是不允许的。所以，必须使生产者和消费者互斥进入缓冲区。即某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其他任何生产者。其次，生产者不能向
11、满的缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用
12、权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图所示，伪代码如图所示。2、涉及的数据结构用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中县有RJ类资源K个。需求矩阵MAX。这是一个N*M的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。如果MAXi,j=K，则表示进程I需要RJ类资源的最大数目为K。矩阵Allocation。这也是一个N*M的矩阵，它定义了系统中每一类资源当前已分配给每一进
13、程的资源数。如果Allocationi,j=K，则表示进程i当前已分得RJ类资源的数目为K。矩阵Need。这也是一个N*M的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程I还需要RJ类资源K个，方能完成其任务。 上述三个矩阵间存在下述关系： Needi,j=MAXi,j-Allocationi,j3、流程图等待使用权，阻塞被唤醒等待资源，阻塞数据单元加1，唤醒一个消费者归还使用权存入一条数据生产一条数据是否可用存储单元 无 有是否可用 否被唤醒是否有数据单元等待资源，阻塞 有被唤醒是否可用 否消费数据空单元加1，唤醒一个生产者归还使用权被唤醒取走一条数据等待使用权
14、，阻塞 是五、运行示例及结果分析1、运行示例：2、运行结果分析：此程序可自动输入生产者、消费者数目等条件，但程序执行过程中也进入了一种无限循环状态，若要得到较好的结果和界面需要加强编程练习。六、个人体会经过快一个月的时间来弄这个大型作业。我当时真的有点力不从心。后来老师只要我们实现OS里面的一部分功能-进程的控制和管理。就是比较有名的那两个进程算法。有于当时在实验室就对进程之间的运转有了一个全面的了解，虽然好多的细节部分还不是太了解，但是对一个进程的流向和执行过程还是有个大概的认识，所以这个大型作业做起来也不是那么的简单。那些东西的详细说明在我们的教材上是没有的。后来，我就在网上和图书馆大量的
15、找资料。先对那些算法有一个大致全面的了解。经过两个多星期的查资料。我就开始对那两个算法的代码进行完善和修改，以达到我的要求。有经过了一个多星期的调试和运行终于达到了我的要求了。并把结果截取如下。在生产者与消费者问题的算法编写程序的时候要尽可能用全所学到的函数，因为这是检测我们用C语言进行程序设计的能力的重要方式。在编写程序的时候我们不可能一次就成功，往往一个图形要修改甚至是十几次数据才能得到预期的结果。因此在编写程序的时候一定不能急躁，要耐心地检测输入的数据和输出的结果，在没达到预期目的的情况下，要及时修改数据进行下一次的检测，只有这样才能成功地用C语言编写出需要的程序。 编写程序是一个长期的
16、过程，因此不能急躁，要坐的住。由于对C语言知识已经有些遗忘，所以我找出了以前的笔记，花了半天的时间去回忆和理解。对操作系统有关消费者-生产者问题的含义也已经有点模糊，我花了一天的时间看教材，还到图书馆借阅了相关的资料，才开始编程。刚开始对如何动态实现消费者-生产者问题一筹莫展，于是和一些同学就这个问题讨论过，但是没什么好的效果。编写程序有的时候需要的就是灵感，因此当有灵感的时候就要开始做，而不能等，必须在灵感未消失前付诸行动，所以才有了凌晨两点才最后做完大型作业。虽然很累，但是觉得值得。历经快一个月的时间让我马马乎乎的完成了它，从中让我得到了好多的东西，首先，这个过程锻炼了我的意志，还让我对进
17、程的控制和编写过程有了一个更深层次的认识和理解。其次，我现在对Windows操作系统执行流程有了一个透明的认识，同时也让我对它更有亲切感。总之，这次作业让我受益匪浅！七、附录(源程序) #include #include #include typedef HANDLE Semaphore; /信号量的Windows原型 #define P(S) WaitForSingleObject(S, INFINITE) /定义Windows下的P操作 #define V(S) ReleaseSemaphore(S, 1, NULL)/定义Windows下的V操作 #define rate 1000 #d
18、efine CONSUMER_NUM 4 /* 消费者个数 */ #define PRODUCER_NUM 4 /* 生产者个数 */ #define BUFFER_NUM 4 /* 缓冲区个数 */ char *thing10=s1, s2, s3, s4,; struct Buffer int productBUFFER_NUM; / 缓冲区 int start, end; / 两个指针 g_buf; Semaphore g_semBuffer, g_semProduct, g_mutex; /消费者线程 DWORD WINAPI Consumer(LPVOID para) /i表示第i个
19、消费者 Int i = *(int *)para; int ptr; /待消费的内容的指针 printf(小白兔-%03d:叶子n, i); Sleep(1800); while (1) printf(小白兔-%03d:我饿了.!n,i); /等待产品 P(g_semProduct); /有产品，先锁住缓冲区g_buf P(g_mutex); /记录消费的物品 ptr=g_buf.start; /再移动缓冲区指针 g_buf.start= (g_buf.start+1)%BUFFER_NUM; /让其他消费者或生产者使用g_buf V(g_mutex); printf(小白兔-%03d:我需要
20、buf%d = %sn, i, ptr, thingg_buf.productptr); Sleep(rate*rand()%10+1800); /消费完毕，并释放一个缓冲 printf(小白兔-%03d:吃绿叶buf%d = %sn,i, ptr, thingg_buf.productptr); V(g_semBuffer); Return 0; /生产者线程 DWORD WINAPI Producer(LPVOID para) int i=*(int*)para-CONSUMER_NUM; int ptr; int data; /产品 printf(小草-%03d:小白兔快来找我!n, i
21、); Sleep(1800); while (1) printf(小草-%03d:我爱阳光n, i); Sleep(rate*rand()%10+1800); data = rand()%10; printf(小草-%03d:我要长大!data = %s!n, i, thingdata); /等待存放空间 P(g_semBuffer); /有地方,先锁住缓冲区g_buf P(g_mutex); /记录消费的物品 ptr = g_buf.end; /再移动缓冲区指针 g_buf.end = (g_buf.end+1)%BUFFER_NUM; /让其他消费者或生产者使用 g_buf V(g_mut
22、ex); printf(小草-%03d:长大了!buf%d = %sn, i, ptr, thingdata); g_buf.productptr = data; Sleep(rate/2*rand()%10+1800); /放好了完毕，释放一个产品 printf(小草-%03d: buf%d=%s 小白兔快来!n,i, ptr,thingg_buf.productptr); V(g_semProduct); return 0; int main(int argc, char *argv) /线程技术，前面为消费者线程，后面为生产者线程 HANDLE hThreadCONSUMER_NUM+P
23、RODUCER_NUM; /线程计数 /srand(time(); DWORD tid; int i=0; /初始化信号量 g_mutex=CreateSemaphore(NULL,BUFFER_NUM,BUFFER_NUM,mutexOfConsumerAndProducer); g_semBuffer=CreateSemaphore(NULL,BUFFER_NUM,BUFFER_NUM,BufferSemaphone); g_semProduct= CreateSemaphore(NULL, 0, BUFFER_NUM, ProductSemaphone); if (!g_semBuffe
24、r|!g_semProduct|!g_mutex) printf(Create Semaphone Error!n); return -1; Int totalThreads = CONSUMER_NUM+PRODUCER_NUM; / 开启消费者线程 printf(先请小白兔就位！n); for (i=0; iCONSUMER_NUM; i+) hThreadi = CreateThread(NULL, 0, Consumer, &i, 0, &tid); if ( hThreadi ) WaitForSingleObject(hThreadi, 10); printf(请小草就位！n);
25、for (;i m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生6)、死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。破坏“不可剥夺”条件:在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件:要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 破坏“循环等待”条件:采用资源有序分配法：把系统中所有资源编
26、号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。7、安全状态与不安全状态 处理死锁的基本方法：为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。在系统中已经出现死锁后，则应及时检测到死锁的发生，并采取适当措施来解除死锁。目前，处理死锁的方法可以归结为以下四种：预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或是几个条件，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。避免死锁。该方法同样是属于事先
27、预防的策略，但它并不须事先采取限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某中方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需要先加以较弱的限制条件，便可获得较高的资源利用率和系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中，常用此方法避免发生死锁。检测死锁。这种方法并不须实现采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，即使地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，采取适当的措施，从系统中将已发生的死锁清处掉。解除死锁。这是与检测死锁相配套的一种措施。当
28、检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或是挂起一些进程，以便回收一些资源。再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。预防和避免死锁这两种方法，实质上都是通过施加某些限制条件的方法，来预防发生死锁。两者的主要差别在于：为预防死锁所施加的限制条件比较严格，这往往会影响进程的并发执行，而为避免死锁施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安
29、全状态。一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。2、设计原理设Request_i是进程i的请求向量，如果Request_ij=K ，表示进程Pi需要K 个Rj 类型的资源。当Pi 发出资源请求后，系统按下述步骤进行检查：(1) 如果Request_ij= Needi,j,便转向步骤(2);否则认为出错,因为它所需要的资源 数已超过它所宣布的最大值。(2)如果Request
30、_ij= Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值； Availablej：= Availablej- Request_ij； Allocationi,j：= Allocationi,j+ Request_ij； Needi,j：= Needi,j- Request_ij(4)系统执行安全性算法，检查此处资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3、数据结构可利用资源向量Available
31、。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K,则表示系统中现有Rj类资源K个。最大需求矩阵Max。n*m的矩阵，它定义了系统中n个进程中的每一个进程时m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。分配矩阵Allocation 。这也是一个n* m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allovationi,j=K，则表示进程 i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一
32、个 n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果 Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵间存在下述关系： Needi,j=Maxi,jAllocationi,j4、安全性检查 (1)设置两个工作向量WORK=AVAILABLE；FINISHM=FALSE (2)从进程集合中找到一个满足下述条件的进程， FINISHi=FALSE NEED=WORK 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 WORK=WORK+ALLOCATION FINISH=TRUE GO TO 2 (4)如所有的
33、进程FinishM=true，则表示安全；否则系统不安全5、流程图写入作业需求 For( )分配可用requestj=needij安全检查requestj=available j请求向量availablej=availablej-requestj;allocationij=allocationij+requestj;needij=needij-requestj;distribute(i,+j)循环检查输出Allocationi,j:=allocationi,j+requirej;输出结果查看Needi,j:=needi,j-requestj;五、运行示例及结果分析1、运行示例：2、运行结果分析：由运行结果可以看出，系统的总资源数和每个作业的需要的资源数都很明了的
