操作系统课设

操作系统课程设计实现生产者消费者问题 题目一：实现生产者消费者问题一、实验题目解决生产者消费者问题二、设计内容有界缓冲区内设有个存储单元，放入取出的数据项设定为这个整形数。要求每个生产者和消费者对有界缓冲区进行操作后，即时显示有界缓冲区的全部内容、当前指针位置和生产者消费者标识符三、开发环境LINUX环境，工具为VI编辑器。四、分析设计（一）实验原理使用的生产者和消费者模型具有如下特点：(1)本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一个空缓冲区中。(2)消费者只消费指定生产者的产品。(3)在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。(4)本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该消费对象是否已经消费完毕并清除该产品。Windows 用来实现同步和互斥的实体。在Windows 中，常见的同步对象有：信号量(Semaphore)、互斥量(Mutex)、临界段(CriticalSection)和事件(Event)等。本程序中用到了前三个。使用这些对象都分为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程中都可以使用，从而实现同步互斥。当然，在进程间使用这些同步对象实现同步的方法是类似的。1用锁操作原语实现互斥 为解决进程互斥进人临界区的问题，可为每类临界区设置一把锁，该锁有打开和关闭两种状态，进程执行临界区程序的操作按下列步骤进行： 关锁。先检查锁的状态，如为关闭状态，则等待其打开；如已打开了，则将其关闭，继续执行步骤的操作。 执行临界区程序。 开锁。将锁打开，退出临界区。 2信号量及WAIT，SIGNAL操作原语 信号量的初值可以由系统根据资源情况和使用需要来确定。在初始条件下信号量的指针项可以置为0，表示队列为空。信号量在使用过程中它的值是可变的，但只能由WAIT，SIGNAL操作来改变。设信号量为S，对S的WAIT操作记为WAIT（S），对它的SIGNAL操作记为SIGNAL（S）。 WAIT（S）：顺序执行以下两个动作： 信号量的值减1，即S=S1； 如果S0，则该进程继续执行； 如果 S（0，则把该进程的状态置为阻塞态，把相应的WAITCB连人该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行SIGNAL操作，把它释放出来为止）。 SIGNAL（S）：顺序执行以下两个动作 S值加 1，即 S=S1； 如果S）0，则该进程继续运行； 如果S（0则释放信号量队列上的第一个PCB（既信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行SIGNAL操作的进程继续运行。 在具体实现时注意，WAIT，SIGNAL操作都应作为一个整体实施，不允许分割或相互穿插执行。也就是说，WAIT，SIGNAL操作各自都好像对应一条指令，需要不间断地做下去，否则会造成混乱。 从物理概念上讲，信号量S）时，S值表示可用资源的数量。执行一次WAIT操作意味着请求分配一个单位资源，因此S值减1；当S=0调用进程入等待队列转进程调度返回是否SIGNAL原语的操作主要动作是：（1） sem加1；（2） 若相加结果大于零，进程继续执行；（3） 若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。SIGNAL原语的功能框图如图：入 口sem=sem-1 sem=sem-1S=0唤醒等待队列中的一个进程式返回或转进程调度 返回否是3用WAIT，SIGNAL原语实现互斥 利用信号量和WAIT，SIGNAL操作实现互斥的一般模型是： 进程WAIT1 进程WAIT2 进程WAITn WAIT(mutex); WAIT(mutex); WAIT(mutex); 临界区 临界区 临界区 SIGNAL(mutex); SIGNAL(mutex）; SIGNAL(mutex); 其中信号量mutex用于互斥，初值为1。 用WAIT，SIGNAL操作实现互斥时应注意： 在每个程序中用于实现互斥的WAIT(mutex)和SIGNAL(mutex)必须成对出现，既先做WAIT，进临界区；后做SIGNAL，出临界区。 互斥信号量mutex的初值一般为1。（二）程序结构程序分为一个主函数、分别用于模拟消费和生产者的两个函数以及三个辅助性的函数。主函数用于初始化缓冲区和各个同步对象，并完成线程信息的读入和记录，最后根据该组线程记录启动模拟线程，并等待所有线程的运行结束后退出整个程序。消费者和生产者函数运行于相应线程中完成对缓冲区的读写动作，根据此处生产消费模型的特点，生产者和消费者线程之间通过同步对象的使用实现了生产和消费动作的同步与互斥，是本试验的核心所在。另外三个辅助函数被生产者和消费者函数调用，是上述生产和消费函数中对缓冲区访问功能的一些包装。（三）数据结构：(1)用一个整型数组Buffer_Critical 来代表缓冲区。不管是生产产品还是对已有产品的消费都需要访问该组缓冲区。(2)在程序中用一个自定义结构ThreadInfo记录一条线程的信息，即将测试用例文件中的一行信息记录下来，用于程序创建相应的生产者或者消费者。由于要创建多个线程，所以程序中使用了一个ThreadInfo结构的数组Thread lnfo。(3)在实现本程序的消费生产模型时，具体地通过如下同步对象实现互斥：一个互斥量h_mutex，以实现生产者在查询和保留缓冲区内的下一个空位置时进行互斥。每一个生产者用一个信号量与其消费者同步，通过设置h _SemaphoreMAXTHREAD_NUM信号量数组实现，该组信号量用于表示相应产品已生产。同时用一个表示空缓冲区数目的信号量empty_semaphore进行类似的同步，指示缓冲区中是否存在空位置，以便开始生产下一个产品。每一个缓冲区用一个同步对象实现该缓冲区上消费者之间的互斥，这通过设置临界区对象数组PC_CriticalMAX_BUFFER_NUM实现。(4)为了实现初始化的线程触发的模拟，还要自己额外定义一些东西。首先，建立一个线程信息的ThreadInfo类型的数组，用来储存从文件读入信息的。然后，由于我们并不知道消费者要消费多少个产品，因此我们的ThreadInfo类型必需要有一个数据结构用来存储这个信息，这里我用了vector去管理消费者的个数。用getline去读入文件每一行的信息，遇到0就结束，这样便可以方便的记录消费者对应的产品。接着，由于我们要求当消费者所有要求的产品都消费完后，一定要释放空间，我们怎样才能知道呢？通过查询h_Semaphore数组显然是不现实的。这里我用了一个数组：int prdt_timeMAXTHREAD_NUM+1; /每个生产者线程对应多少个消费者专门记录每个产品应该被消费多少次，当消费次数为0时，释放空间；这个数组的初始化随同文件读入完成。最后，也是最重要的，怎样模拟线程的产生呢？我们知道的是：要按文件提供的延迟来使线程生成。直接对ThreadInfo类型的数组进行排序，这样消耗很大，于是我自己定义一个节点结构：struct nodeint delay; /延迟int que_num; /从文件读入的序号,就是对应的thread_info队列的下标;如上代码解析所示，它包含线程的队列号，即ThreadInfo数组的下标，以及该线程的延迟；这个结构是专门用来为下面的结构服务的：vector Begin_que; /产生线程的次序队列这是个记录线程产生先后的队列，用sort算法对它的节点排序，延迟小的在队首，就可以实现线程生成的模拟了。(5)在结果输出时，还要主要输出流的互斥保护：CRITICAL_SECTION print_mutex;（四）详细设计Linux系统下的多线程遵循POSIX线程接口，称为pthread。编写Linux下的多线程程序，需要使用头文件pthread.h，连接时需要使用库libpthread.a。顺便说一下，Linux下pthread的实现是通过系统调用clone()来实现的。函数pthread_create用来创建一个线程，它的原型为：extern int pthread_create _P (pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg);函数pthread_join用来等待一个线程的结束。函数原型为：extern int pthread_join _P (pthread_t _th, void *_thread_return)创建键的函数原型为：extern int pthread_key_create _P (pthread_key_t *_key,void (*_destr_function) (void *);pthread_mutex_lock声明开始用互斥锁上锁，此后的代码直至调用pthread_mutex_unlock为止，均被上锁，即同一时间只能被一个线程调用执行。当一个线程执行到pthread_mutex_lock处时，如果该锁此时被另一个线程使用，那此线程被阻塞，即程序将等待到另一个线程释放此互斥锁。在上面的例子中，我们使用了pthread_delay_np函数，让线程睡眠一段时间，就是为了防止一个线程始终占据此函数。条件变量的结构为pthread_cond_t，函数pthread_cond_init()被用来初始化一个条件变量。它的原型为：extern int pthread_cond_init _P (pthread_cond_t *_cond,_const pthread_condattr_t *_cond_attr);信号量的数据类型为结构sem_t，它本质上是一个长整型的数。函数sem_init()用来初始化一个信号量。它的原型为：extern int sem_init _P (sem_t *_sem, int _pshared, unsigned int _value);五. 运行示例及结果分析调试问题分析：生产者消费者问题是一个著名的进程同步问题。具体描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有10个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品1定义程序中首先定义缓冲区，buf为10个，定义生产者消费者的处值，设互斥量置互斥。int buffer10=0,0,0,0,0,0,0,0,0,0;int i=0;int j=0;sem_t full;sem_t empty;pthread_mutex_t mutex;2生产与消费生产者：. produce a product and put it into buf pthread_mutex_lock(&mutex); bufferi=i+1; i=i+1; sem_post(&full); pthread_mutex_unlock(&mutex);.消费者： pthread_mutex_lock(&mutex); sem_wait(&full); if(bufferj=0) break; x=bufferj; bufferj=0; j=j+1;pthread_mutex_unlock(&mutex); sem_post(&empty);fetch the product in buf;按照老师要求产生10个生产者和十个消费者，因此在程序中加入循环变量，使其循环10次，即满足要求。并在其中加入输出函数，显示结果。3.创建和结束进程 pthread_create(&thread1,NULL,(void *)producer,NULL); pthread_create(&thread2,NULL,(void *)consumer,NULL); pthread_join(thread1,NULL); pthread_join(thread2,NULL);详细程序见附录部分。结果调试：调试工具：vi(visual editor)进入vi,直接执行 vi编辑程式即可：此刻萤幕上会出现 vi 的编辑视窗，同时 vi 会将文件复制一份至记忆体中的缓冲区 (buffer) 。vi会保留在磁盘中的文件不变，而先对缓冲区的档案作编辑，编辑完成后，使用者可决定是否要取代原来旧有的文件。所用指令模式:h 向左移一个字元 j 向上移一个字元 k 向下移一个字元l 向右移一个字元 0 移至该行之首 $ 移至该行之末。：q! 离开vi，并放弃刚在缓冲区内编辑的内容（强行退出）：w 将缓冲区内的资料写入磁盘中，但并不离开vix 删除游标所在字元。 dd 删除游标所在的列。 nj 下跳 n 行(hjkl分别表示左下上右都可仿照用之)p 粘贴拷贝的行u 返回上次编辑（相当于WIN中的撤消）:wq 存盘并退出:wq! 强行存盘退出（相当于ZZ）编译命令：cc -lpthread -o 目标文件名源文件名编译程序：cc lpthread o xuguang xuguang.c运行结果：详细的运行结果如下：there are 10 blocks in the buffer:0,1,2,3,4,5,6,7,8,9buffer : 0 0 0 0 0 0 0 0 0 0the number added by the producer is:1buffer : 1 0 0 0 0 0 0 0 0 0pointer is 1the number added by the producer is:2buffer : 1 2 0 0 0 0 0 0 0 0pointer is 2the number added by the producer is:3buffer : 1 2 3 0 0 0 0 0 0 0pointer is 3the number added by the producer is:4buffer : 1 2 3 4 0 0 0 0 0 0pointer is 4the number added by the producer is:5buffer : 1 2 3 4 5 0 0 0 0 0pointer is 5the number added by the producer is:6buffer : 1 2 3 4 5 6 0 0 0 0pointer is 6the number added by the producer is:7buffer : 1 2 3 4 5 6 7 0 0 0pointer is 7the number added by the producer is:8buffer : 1 2 3 4 5 6 7 8 0 0pointer is 8the number added by the producer is:9buffer : 1 2 3 4 5 6 7 8 9 0pointer is 9the number added by the producer is:10buffer : 1 2 3 4 5 6 7 8 9 10pointer is 10buffer : 1 2 3 4 5 6 7 8 9 10buffer : 0 2 3 4 5 6 7 8 9 101 is removed form the buffer by consumerThe present pointer is : 1buffer : 0 0 3 4 5 6 7 8 9 102 is removed form the buffer by consumerThe present pointer is : 2buffer : 0 0 0 4 5 6 7 8 9 103 is removed form the buffer by consumerThe present pointer is : 3buffer : 0 0 0 0 5 6 7 8 9 104 is removed form the buffer by consumerThe present pointer is : 4buffer : 0 0 0 0 0 6 7 8 9 105 is removed form the buffer by consumerThe present pointer is : 5buffer : 0 0 0 0 0 0 7 8 9 106 is removed form the buffer by consumerThe present pointer is : 6buffer : 0 0 0 0 0 0 0 8 9 107 is removed form the buffer by consumerThe present pointer is : 7buffer : 0 0 0 0 0 0 0 0 9 108 is removed form the buffer by consumerThe present pointer is : 8buffer : 0 0 0 0 0 0 0 0 0 109 is removed form the buffer by consumerThe present pointer is : 9buffer : 0 0 0 0 0 0 0 0 0 010 is removed form the buffer by consumerThe present pointer is : 10附录（源程序清单）#include #include #include #include #include #include int buffer10=0,0,0,0,0,0,0,0,0,0;int i=0;int j=0;sem_t full;sem_t empty;pthread_mutex_t mutex;void producer(void) int m; while(i10) pthread_mutex_lock(&mutex); bufferi=i+1; i=i+1; printf(nthere are 10 blocks in the buffer:0,1,2,3,4,5,6,7,8,9n); printf(nbuffer:); for(m=0;m10;m+) printf(%3d,bufferm); printf(nthe number added by the producer is:); printf(%d, bufferi); printf(npointer is %d,i); sem_post(&full); pthread_mutex_unlock(&mutex); void consumer(void) int m; while(j10) int x; pthread_mutex_lock(&mutex); sem_wait(&full); if(bufferj=0) break; x=bufferj; bufferj=0; j=j+1; printf(nbuffer:); for(m=0;m=mi ！而且如果之后操作系统又把资源分配给其他进程了，假设是 pj ， pj 还需要 mj 个资源，同理可知 m=mj ！也就是说在所有的进程中，还需要的资源数总是有小于 m 的！这样就可以保证资源数永远不会为 0 ，即使可能暂时性为 0 。另外，还需要保证资源数不会减少！而且，所有已经分配到资源的进程总有一天会归还它所拥有的资源！根据操作系统再分配的时候的状态即可判定。二程序结构当进程pi提出资源申请时，系统执行下列步骤：（1）若RequestiNeedi,转（2）；否则错误返回（2）若RequestiAvailable,转（3）；否则进程等待(3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1如果Request=Need,则转向2;否则,出错2如果Request=Available,则转向3,否则等待3系统试探分配请求的资源给进程4系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finishi=true;转24. 若所有进程的Finishi=true,则表示系统安全;否则,不安全!流程图如下：三数据结构：假设有M个进程N类资源，则有如下数据结构： MAXM*N M个进程对N类资源的最大需求量 AVAILABLEN 系统可用资源数 ALLOCATIONM*N M个进程已经得到N类资源的资源量 NEEDM*N M个进程还需要N类资源的资源量五. 运行示例及结果分析T0 时刻 可用资源(Available) A:3, B:3, C:2 请求分配时间： 14:07:29 经测试，可为该进程分配资源。以下为资源分配表 资源 Work Need Allocation Work+Alloc Finish ID A B C A B C A B C A B C P01 03 03 02 01 02 02 02 00 00 05 03 02 TRUE P03 05 03 02 00 01 01 02 01 01 07 04 03 TRUE P00 07 04 03 07 04 03 00 01 00 07 05 03 TRUE P02 07 05 03 06 00 00 03 00 02 10 05 05 TRUE P04 10 05 05 04 03 01 00 00 02 10 05 07 TRUE 进程 1 申请资源 A:2, B:1, C:1 时的安全性检查 请求分配时间： 14:07:39 进程请求的资源比Need多!不能为该进程分配资源！ 系统在 T0（Request） 时刻是不安全的! -尝试进行另外一个分配- 进程 1 申请资源 A:1, B:0, C:2 时的安全性检查 请求分配时间： 14:07:55 经测试，可为该进程分配资源。以下为资源分配表 资源 Work Need Allocation Work+Alloc Finish ID A B C A B C A B C A B C P01 02 03 00 00 02 00 03 00 02 05 03 02 TRUE P03 05 03 02 00 01 01 02 01 01 07 04 03 TRUE P00 07 04 03 07 04 03 00 01 00 07 05 03 TRUE P02 07 05 03 06 00 00 03 00 02 10 05 05 TRUE P04 10 05 05 04 03 01 00 00 02 10 05 07 TRUE 进程 4 申请资源 A:3, B:3, C:0 时的安全性检查 请求分配时间： 14:09:14 进程请求的资源比Avaliable(WORK)多!不能为该进程分配资源！ 系统在 T0（Request） 时刻是不安全的! -尝试进行另外一个分配- 进程 0 申请资源 A:0, B:2, C:0 时的安全性检查 请求分配时间： 14:09:23 系统进入不安全状态!不能为该进程分配资源！ 系统在 T0（Request） 时刻是不安全的! -尝试进行另外一个分配- 进程 1 申请资源 A:0, B:0, C:0 时的安全性检查 请求分配时间： 14:09:37 经测试，可为该进程分配资源。以下为资源分配表 资源 Work Need Allocation Work+Alloc Finish ID A B C A B C A B C A B C P01 02 03 00 00 02 00 03 00 02 05 03 02 TRUE P03 05 03 02 00 01 01 02 01 01 07 04 03 TRUE P00 07 04 03 07 04 03 00 01 00 07 05 03 TRUE P02 07 05 03 06 00 00 03 00 02 10 05 05 TRUE P04 10 05 05 04 03 01 00 00 02 10 05 07 TRUE运行结果显示：附录：（源程序清单）#include #include /A为已分配资源矩阵，C为请资源矩阵，V为可用资源。int A1010, C1010, V10; /flag为标识进程是否完成，0表示还没完成，1表示完成。int flag10=0;/扫描矩阵函数，看是否有可满足的进程，有则返回指向该进程的序号，还则返-1/maxpro为最大进程数，maxres为最大资源数int scan(int maxpro,int maxres);void main() int i, j, m, resTotal, proTotal; int sequen10; /保存安全序列 int selected; int k=0; printf(输入有多少种资源:); scanf(%d, &re