第一篇：操作系统课程设计__用多线程同步方法解决生产者
临界区管理实现 本组组员：周琪皓，董泉伟，钟佳锋，张倬慎 0 引言 随着多处理机体系结构的演变和分布式与并行系统的发展，并发多任务的程序设计技术已愈来愈显得重要，多线程设计模式在这些技术的发展中起着重要作用。在现代操作系统中，利用进(线)程间的并发性实现程序中并发成分的并行执行，可大大提高系统的处理能力和效率，但也可能带来诸如执行结果的不确定性等不良现象，因此并发系统中处理好进(线)程间的互斥与同步就显得至关重要。C++语言中的多线程机制是解决线程间的互斥与同步问题的重要工具，其应用(如网络多媒体应用、工业自动化控制等)很广泛，很复杂且常易出错。因此在应用程序设计过程中，要考虑多个线程如何同步使用进程的共享资源，如何让一个线程与另一个线程协调合作，以免产生线程间的访问冲突。语言提供的多线程机制能有避免同一共享互斥资源被多个线程同时访问，维护数据的一致性、安全性。生产者/消费者问题可作为并发进程的同步和互斥问题的一个抽象模型，广泛应用于通信和控制系统中。本文基于C++语言中的多线程机制，实现操作系统中生产者/消费者问题，以助人们更好地透解同步概念及其实现方法。1 课程设计目的 通过模拟操作者生产者经典问题的实现，以及关于信号量和互斥锁对于多线程的运用，深入理解操作系统中多线程同步法的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法,更好地掌握操作系统的原理及实现方法,提高综合运用各专业课知识的能力。2 课程设计题目和要求 2.1 课程设计题目 题目: 临界区管理实现.2.2课程设计目的与要求 初始条件：
1.操作系统：Windows 2.程序设计语言：C++语言
3.有界缓冲区内设有20个存储单元，其初值为0。放入／取出的数据项按增序设定为1－20这20个整型数。
技术要求：
1、生产者和消费者各有两个以上。多个生产者或 多个消费者之间须有共享对缓冲区进行操作 的函数代码。每个生产者和消费者对有界缓冲 区进行操作后，即时显示有界缓冲区的全部内 容，当前指针位置。
2、编写多线程同步方法解决生产者-消费者的程 序，并完成对进程进行模拟同步和互斥的控制。2 设计总体思路 2.1 多线程编程思想 编写Windows下的多线程程序，需要使用头文件pthread.h以及windows.h.在LINUX下进行多线程编程首先要用到CreateThread()这个函数.函数CreateThread()用来创建一个线程，它的原型为：
HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes, // pointer to security attributes DWORD dwStackSize, // initial thread stack size LPTHREAD_START_ROUTINE lpStartAddress, // pointer to thread function LPVOID lpParameter, // argument for new thread DWORD dwCreationFlags, // creation flags LPDWORD lpThreadId);// pointer to receive thread ID 第一个参数是指向SECURITY_ATTRIBUTES型态的结构的指针。在Windows 98中忽略该参数。在Windows NT中，它被设为NULL。第二个参数是用于新线程的初始堆栈大小，默认值为0。在任何情况下，Windows根据需要动态延长堆栈的大小。第三个参数是指向线程函数的指标。函数名称没有限制，但是必须以下列形式声明： DWORD WINAPI ThreadProc(PVOID pParam);第四个参数为传递给ThreadProc的参数。这样主线程和从属线程就可以共享数据。第五个参数通常为0，但当建立的线程不马上执行时为旗标CREATE_SUSPENDED。线程将暂停直到呼叫ResumeThread来恢复线程的执行为止。第六个参数是一个指标，指向接受执行绪ID值的变量。2.1.1线程数据 在单线程的程序里，有两种基本的数据：全局变量和局部变量。但在多线程程序里，还有第三种数据类型：线程数据。它和全局变量很象，在线程内部，各个函数可以象使用全局变量一样调用它，但它对线程外部的其它线程是不可见的。这种数据的必要性是显而易见的。例如我们常见的变量errno，它返回标准的出错信息。它显然不能是一个局部变量，几乎每个函数都应该可以调用它；但它又不能是一个全局变量，否则在A线程里输出的很可能是B线程的出错信息。ThreadHandle[0]=CreateThread(NULL,0,Producer,NULL,0,&producer1)其六个参数分别表示为安全设置，堆栈大小，入口函数，函数参数，启动选项，输出线程 ID，返回线程句柄。2.1.2 互斥锁 互斥锁用来保证一段时间内只有一个线程在执行一段代码，必要性显而易见：假设各个线程向同一个文件顺序写入数据，最后得到的结果一定是灾难性的.函数mutex = CreateMutex(NULL,FALSE,NULL);用来生成一个互斥锁.NULL参数表明使用默认属性.如果需要声明特定属性的互斥锁，须调用函数
CreateMutex(NULL,FALSE,NULL)
WaitForSingleObject(mutex,INFINITE)声明开始用互斥锁上锁，直至调用ReleaseMutex(mutex)为止，均被上锁，即同一时间只能被一个线程调用执行.当一个线程执行到pthread_mutex_lock处时，如果该锁此时被另一个线程使用，那么此线程被阻塞，即程序将等待到另一个线程释放此互斥锁.2.1.3 信号量 信号量本质上是一个非负的整数计数器，它被用来控制对公共资源的访问。当公共资源增加时，调用函数aitForSingleObject(empty,INFINITE)增加信号量。只有当信号量值大于０时，才能使用公共资源，使用后，函数WaitForSingleObject(full,INFINITE)减少信号量。
函数 ReleaseSemaphore(full,1,NULL)用来增加信号量的值。当有线程阻塞在这个信号量上时，调用这个函数会使其中的一个线程不在阻塞，选择机制同样是由线程的调度策略决定的。函数ReleaseSemaphor()用来释放信号量。2.2 设计原理 生产者线程和消费者线程共享同一个缓冲队列，生产者线程向缓冲区中写数据，消费者线程从缓冲区中取数据。但两者必须在使用缓冲队列资源时保持互斥，否则可能会导致在写入时产生数据覆盖，在读出时得到错误数据。因而要在程序中设置一个互斥锁或公用信号量，用于保证线程间的互斥执行。同时生产者线程和消费者线程必须保持同步关系，因为生产者线程的执行为消费者线程提供了需要的数据，是其执行的前提。反之，消费者线程的执行为生产者线程腾出了空闲的缓冲单元，为写数据提供了条件。即消费者线程执行的前提：缓冲队列中至少有一个单元有数据；生产者线程执行的前提：缓冲队列中至少有一个单元是空的。在设计过程中，利用信号量和wait、signal原语操作来实现。如图1所示：
图1 生产者、消费者共享有界缓冲区
2.3 原语操作实现 The structure of the producer process do { // 生产产品 wait(empty);wait(mutex);// 往Buffer中放入产品 signal(mutex);signal(full);} while(true);The structure of the consumer process do { wait(full);wait(mutex);// 从Buffer中取出产品 signal(mutex);signal(empty);// 消费产品 } while(true);3 开发环境与工具 系统平台：Windows环境 实现语言：C++语言 开发工具：Vs2012 4 概要设计 4.1 数据结构设计 通过分析课程设计要求，具体设计出如下数据结构: 1.int buffer[20]={0};//定义缓冲区空间大小 2.包含数据结构pthread_t 它记录一个线程的号，主要包括下面几个函数，完成不同的功能： ThreadHandle[0]=CreateThread(NULL,0,Producer,NULL,0,&producer1);//创建一个线程。ExitThread(0);CloseHandle(ThreadHandle[0]);//等待一个线程结束。4.2 程序模块实现 4.2.1 生产者（Producer）模块 生产者线程向一缓冲区中写入数据，且写入缓冲区的数目不能超过缓冲区容量。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权，其流程图如图2所示： 生产一条数据No是否可用存储单元等待资源，阻塞Yes被唤醒No是否可用Yes存入一条数据等待使用权，阻塞被唤醒归还使用权数据单元加1，唤醒消费者 图生产者流程图
//生产者线程 DWORD WINAPI Producer(LPVOID lpPara){ do{ WaitForSingleObject(empty,INFINITE);冲区减1 WaitForSingleObject(mutex,INFINITE);上锁 //空缓//信号量 buffer[in]=in+1;//往Buffer中放入产品 in=(in+1)%BUFFER_SIZE;//放入指针调整，为下次送出做准备 printAll();ReleaseMutex(mutex);//信号量解锁 ReleaseSemaphore(full,1,NULL);//满缓冲区加1，即当公共资源增加时，调用函数ReleaseSemaphore（）增加信号量 }while(1);}
4.2.2 消费者(Consumer)模块 消费者线程从缓冲区中读取数据，且消费者读取的数目不能超过生产者写入的数目。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图3所示：
No是否可用存储单元等待资源，阻塞Yes被唤醒是否可用No等待使用权，阻塞Yes被唤醒取出一条数据归还使用权空缓冲区加1，唤醒一个生产者消费数据 图3 消费者流程图 //消费者线程 DWORD WINAPI Consumer(LPVOID lpPara){ do{ WaitForSingleObject(full,INFINITE);区减1 WaitForSingleObject(mutex,INFINITE);量上锁 //满缓冲 //信号 buffer[out]=0;//从Buffer中取出产品 out=(out+1)%BUFFER_SIZE;//取指针调整，为下次取做准备 printAll();ReleaseMutex(mutex);//信号量解锁 ReleaseSemaphore(empty,1,NULL);//空缓冲区加1 }while(1);} 5 详细设计 5.1 源程序代码 #include #include 进入Windows开发环境后，通过Vs2012编辑器在其中编写。进入Vs2012的命令，对程序执行编译运行命令后，即可在屏幕上显示出程序运行的结果，其运行结果如下图5所示： 总结 其实在做这道题目时花费了好长时间，第一点是书上大多介绍的是关于UNIX系统下的消费者生产者线程问题，因此一开始调试不出来，后来查阅了有一些资料知道要在windows平台下运行必须要导入 以及 题目: 用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)初始条件： 1．操作系统：Linux 2．程序设计语言：C语言 3.设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．技术要求： 1）为每个理发师／顾客产生一个线程，设计正确的同步算法 2）每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。3）至少有10个顾客，每人理发至少3秒钟。4）多个顾客须共享操作函数代码。 2． 设计说明书内容要求： 1)设计题目与要求 2)总的设计思想及系统平台、语言、工具等。3）数据结构与模块说明（功能与流程图） 4）给出用户名、源程序名、目标程序名和源程序及其运行结果。（要注明存储各个程序及其运行结果的主机IP地址和目录。） 5）运行结果与运行情况 （提示:(1)连续存储区可用数组实现。 (2)编译命令可用： cc-lpthread-o 目标文件名 源文件名(3)多线程编程方法参见附件。） 1设计题目与要求 1.1 设计题目 用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)1.2 设计要求 1.2.1 初始条件 （1）操作系统：Linux（2）程序设计语言：C语言 （3）设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。 1.2.2 技术要求 （1）为每个理发师／顾客产生一个线程，设计正确的同步算法 （2）每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。（3）至少有10个顾客，每人理发至少3秒钟。（4）多个顾客须共享操作函数代码。总体设计思想及开发环境与工具 2.1 总体设计思想 题目中要求描述理发师和顾客的行为，因此需要两类线程barber()和customer()分别描述理发师和顾客的行为。其中，理发师有活动有理发和睡觉两个事件；等待和理发二个事件。店里有固定的椅子数，上面坐着等待的顾客，顾客在到来这个事件时，需判断有没有空闲的椅子，理发师决定要理发或睡觉时，也要判断椅子上有没有顾客。所以，顾客和理 发师之间的关系表现为： （1）理发师和顾客之间同步关系：当理发师睡觉时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师睡觉。 （2）理发师和顾客之间互斥关系：由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n把，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。（3）故引入3个信号量和一个控制变量： ⅰ控制变量waiting用来记录等候理发的顾客数，初值为0； ⅱ信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0； ⅲ信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为1； ⅳ信号量mutex用于互斥，初值为1 2.2 多线程编程原理 此次在Linux下进行多线程编程需要用到pthread_create和pthread_join这两个函数。 2.2.1 创建一个线程 pthread_create用来创建一个线程，原型为： extern int pthread_create((pthread_t *__thread，__const pthread_attr_t *__attr,void *(*__start_routine)(void *), void *__arg))第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。函数thread不需要参数时，最后一个参数设为空指针。第二个参数设为空指针时，将生成默认属性的线程。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。 2.2.2 等待一个线程结束 pthread_join用来等待一个线程的结束，函数原型为： extern int pthread_join __P((pthread_t __th, void **__thread_return)); 第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存 储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被 等待的线程结束为止，当函数返回时，被等待线程的资源被收回。 2.2.3 信号量 （1）函数sem_init（）用来初始化一个信号量，函数原型为： extern int sem_init __P((sem_t *__sem, int __pshared, unsigned int __value));sem为指向信号量结构的一个指针；pshared不为０时此信号量在进程间共享，否则只能为当前进程的所有线程共享；value给出了信号量的初始值。（2）函数sem_post(sem_t *sem)用来增加信号量的值。 当有线程阻塞在这个信号量上时，调用这个函数会使其中的一个线程不在阻塞，选择机制同样是由线程的调度策略决定的。 （3）函数sem_wait(sem_t *sem)被用来阻塞当前线程直到信号量sem的值大于0，解除阻塞后将sem的值减一，表明公共资源经使用后减少。函数sem_trywait(sem_t *sem)是函数sem_wait（）的非阻塞版本，它直接将信号量sem的值减一。 2.3 伪码实现 difine n 5； //为顾客准备的椅子数为5 semaphore mutex=1； //用于互斥 semaphore customers=0；//等候理发的顾客数 semaphore barbers=1；//正在等候顾客的理发师数 int waiting=0； //等候理发的顾客数 //理发师线程 void barber(){ while(true)//判断有无顾客 { wait(customers);//若无顾客,理发师睡眠 wait(mutex);//互斥 waiting--;//等候顾客数少一个 signal(mutex);//释放临界资源 signal(barber);//cut_hair;// } } //顾客线程 void customer(){ wait(mutex);// if(waiting 理发师去为一个顾客理发 正在理发 互斥 如果有空椅子，则等待 等候顾客数加1 释放临界资源 如果理发师睡觉，唤醒理发师理发师在理发, 顾客等候 顾客坐下等理发师 店里人满了,顾客离开 2.4 开发环境与工具 系统平台：LINUX环境 实现语言：C语言 开发工具：NANO编辑器 3数据结构与模块说明 3.1 数据结构 通过分析课程设计要求，定义以下的数据: sem_t mutex,customers,barbers;//design three semaphores: mutex,customer,barbers int waiting=0;//the number of waiting customers int chair[5];3.2程序模块说明 3.2.1主函数模块 主函数流程图如下： 3.2.2 理发师模块 理发师模块函数流程图如下： 3.2.3 顾客模块 顾客模块函数流程图如下： 源程序代码 #include #include //design three semaphores: mutex,customer,barbers sem_t mutex,customers,barbers;int waiting=0;//the number of waiting customers int chair[5];void * barber();void * customer(void *arg); int main(int argc,char *argv[]){ //create 10 semaphores and one Barber semaphore pthread_t Customer_id[10],Barber_id;int i;sem_init(&mutex,0,1);//init mutex semaphore to 1 sem_init(&customers,0,0);//init semaphore customers to 0 sem_init(&barbers,0,1); for(i=0;i<5;i++)pthread_create(&Barber_id,NULL,(void*)barber,NULL);for(i=0;i<10;i++)pthread_create(&Customer_id[i],NULL,(void*)customer,(void*)(i+1));for(i=0;i<10;i++)pthread_join(Customer_id[i],NULL);for(i=0;i<5;i++)pthread_join(Barber_id,NULL);return 0;} //creat barber pthread void * barber(){ int i;int next;//wait(customers),if no customers,barber sleeping sem_wait(&customers);sem_wait(&mutex);//wait(mutex)waiting--;//the numer of waiting reduce one for(i=0;i<5;i++){ if(chair[i]!=0){ next= chair[i];chair[i]=0;break;} } printf(“The barber is cutting %dth customer's hairn”,next);sleep(3);sem_post(&mutex);sem_post(&barbers);} //creat customer pthread void * customer(void *arg){ int i;sem_wait(&mutex);//wait(mutex)if(waiting if(waiting waiting++;//the numer of waiting plus one for(i=0;i<5;i++){ if(chair[i]==0){ chair[i]=(int)arg;break;} } printf(“***************************************************n”);printf(“Entered:Number %d customer comes,and sits at %d n”,(int)arg,(i+1));printf(“There are %d customer on the chairn”,waiting);printf(“The customers' location are:”);for(i=0;i<5;i++)printf(“%d ”,chair[i]);printf(“n”); sleep(1);sem_post(&mutex);//signal(mutex)sem_post(&customers);//signal(customers)sem_wait(&barbers);//wait(barbers)} else chair { printf(“Number %d comes,there are no chairs,the customer %d is leavingn”,(int)arg,(int)arg);sem_post(&mutex);} } 5.2.1 编辑，编译和运行的过程图 5.2.2 错误部分截图 5.2.3 正确运行结果图 第一次运行结果如下图： 第二次运行结果如下图： 第三次运行结果如下图； 6调试记录 6.1调试记录 周一因有培训与课设时间冲突，故没有上机操作，查阅了相关书籍，并在网上查找了相关资料，了解了linux多线程编程的原理，应注意的问题，及一些常用命令 周二先设计出了该程序的伪代码即其wait、signal操作。然后，根据其要求进行编程，由于使用的是多线程编程，开始进行编译的时候，编译命令输入错误，没有输入-lpthread，程序总是出现错误。同时，创建线程函数时，由于对其格式输入错误导致程序无法运行。例如sb.c，sb1.c等都为本次调试时的程序。 周三主要是不断的调试并完善程序。程序可以运行，但与要求总有些不符，故不断的进行修改，并对其输出的格式进行完善，使其输出看起来美观一些，容易观察一些。例如s.c，b.c等程序为此次调试结果。 周四主要是在原有代码的基础上，使程序更完整些。并进行结果的截图，开始设计并编写课程设计报告。 6.2自我评析和总结 通过本次编程我熟悉了linux 下的多线程编程和信号量实现wait、signal操作的全过程，对同步和互斥问题也有了更深一步的理解，同时，也使我对linux编程有了更多的了解，在很多方面，它与在windows下编程有着很大的不同，对与多线程来说更方便一些。 设计过程中也遇到不少困难，尤其是对于多线程的实现，结果总是不如想象中完美。比如其顾客编号的输出有时会不按顺序，输入有点乱。另外，有时，输出结束后，程序仍无法结束，必须强制性关闭终端才可以结束程序，这是本程序的一个不足之处。 在本次课程设计中我深深感觉到自己掌握的知识还远远不够，我明白光是知道书本上的知识是远远不够的，一定要把理论知识和实践结合起来。同时，要多多学习linux的操作。 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 （操作系统课程设计） 生 产 者 和 消 费 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 者 学生姓名： 学生学号： 班 级： 0311401、02、03、04班制 二〇一三年十二月 一、课程题目分析 这个题目是生产者向消费者提供商品，消费者消耗商品，并且两组人共用同一缓冲区。生产者提供了商品之后消费者才能去取商品，消费者若不取走商品则当缓冲区用完之后生产者则不能再向缓冲区中添加新的商品。 思考问题： （1）对于生产者进程：每产生一个数据，则需去访问共用缓冲区是否有已满，未满则可以将该数据存入并通知消费者进程，否则不能。 （2）对于消费者进程：每当想去消费（取出数据）时，则需访问缓冲区是否为空，为空则不能消费（取出数据），否则可以取，并通知生产者。 （3）缓冲区是个临界资源，所有的进程对于该空间都是共享的，所以，还有互斥问题存在。 二、课程设计目的 通过实验模拟生产者与消费者之间的关系，了解并掌握他们之间的关系及原理。由此增加对进程同步问题的了解： （1）掌握基本的同步互斥算法，理解生产者与消费者模型 （2）了解windows中多线程（多进程）的并发执行机制，线程（进程）间的同步于互斥 （3）学习使用windows中基本的同步对象，掌握相应的API。 三、课程设计内容 有n个生产者和m个消费者，连接在具有k个单位缓冲区的有界环转缓冲上，湖北民族学院信息工程学院11级计算机专业操作系统课程设计 故又称有界缓冲问题。其中Pi和Cj都是并发进程，只要缓冲区未满，生产者进程Pi所生产的产品就可投入缓冲区；类似地，只要缓冲区非空，消费者进程Cj就可以从缓冲区取走并消耗产品。 四、开发环境 操作系统：Windows系统 编写语言：C++语言 五、系统分析设计 （一）算法原理 生产者——消费者问题是典型的进程同步问题，这些进程必须按照一定的生产率和消费率来访问共享缓冲区，用P、V操作解决生产者和消费者共享单缓冲区的问题，可设置两个信号量empty和full，其初值分别为1和0，empty指示能否向缓冲区放入产品，full指示能否从缓冲区取出产品。为了使其协调工作，必须使用一个信号量mutex（初值为1），以限制生产者和消费者互斥地对缓冲区进行存取，另用两个信号量empty1（初值为缓冲区大小）和full1（初值为0），以保证生产者不向已满的缓冲区中放入产品，消费者不从空缓冲区中取产品。 （二）功能描述 生产者功能描述：在同一个进程地址空间内执行两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。 消费者功能描述：消费者线程从缓冲区获得物品，然后释放缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。 （三）算法流程图 生产者流程图： 消费者流程图： 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 总的流程图： 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 开始Int i=1，n键盘输入数字，初始化 n SeqSquare *b;b=new SeqSquare(n)；键盘输入数字，改变i的值i==0？Y退出Ncout<<“请输入正确的菜单项进行操作!”< (四)数据结构及部分函数描述 （1）类SeqSquare：对类SeqSquare的声明及其中一些函数 class SeqSquare { public: SeqSquare(int n);~SeqSquare();void P(int x);//p操作 void V(int x);//v操作 bool IsEmpty();//判断是否为空 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 bool IsFull();//判断是否已满 void deca();void decb();int getSize();int getmaxSize();int gettop();int geta();int getb();protected: private: };说明：①用动态整型数组*elements来代表缓冲区，不管是生产产品还是对已有产品的消费都需要访问该缓冲区。②函数IsFull（）用于判断缓冲区是否已满，生产者能否使用缓冲区。③函数IsEmpty（）用于判断缓冲区是否为空，消费者能否使用缓冲区。 （2）生产者和消费者操作及显示函数showbuf： void producer(SeqSquare *a)//生产者操作 { } void consumer(SeqSquare *a)//消费者操作 { } //缓冲区显示 void showbuf(SeqSquare *a){ }（3）在实现本程序的生产者消费者模型时，具体地通过以下同步对象实现互斥： int *elements;int top,a,b,maxSize;a->P(1);a->V(1);int i=a->getSize();湖北民族学院信息工程学院11级计算机专业操作系统课程设计 ①设一个互斥量Mutex，以实现生产者在查询和保留缓冲区的下一个空位置时进行互斥。 ②每一个生产者用一个信号量与消费者同步，通过设置Full实现，该组信号量用于表示相应产品以生产。同时用一个表示空缓冲区数目的信号量Empty进行类似的同步，指示缓冲区中是否存在空位置，以便开始生产下一个产品。 （四）调试过程 为解决生产者、消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用Full表示，其初值为用户输入的缓冲区的大小，另一个表示缓冲区中产品的数目，用Empty表示，其初值为0.另外，由于缓冲区是一个临界资源，必须互斥使用，所以还需要再设置一个互斥信号量Mutex，其初值为1.在生产者、消费者问题中，信号量实现两种功能。首先，他是生产产品和消费产品的计数器，计数器的初值是可使用的资源数目（缓冲区的长度）。其次，他是确保产品的生产者和消费者之间的动作同步的同步器。 生产者要生产一个产品时，首先对资源信号量Full和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话，就生产一个产品，并把产品送人缓冲区。然后对互斥信号量Mutex和资源信号量Empty进行V操作，释放资源。 消费者要消费一个产品时，首先对资源信号量Empty和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话就从缓冲区取出一个产品并消费掉。然后对互斥信号量Mutex和资源信号量Full进行V操作，释放资源。 如果缓冲区中已经没有可用资源，就把申请资源的进程添加到等待队列的队尾。如果有一个资源被释放，在等待队列中的第一个进程被唤醒并取得这个资源的使用权。 （五）参考资料 《操作系统教程》 孙钟秀 高等教育出版社 《C++程序设计》 谭浩强 高等教育出版社 六、运行实例及结果分析 （一）运行实例 缓冲区大小为3，先生产一件产品，显示缓冲区，再接着生产一件产品，消耗一件产品，显示缓冲区，在消耗两件产品，再生产4件产品，改变缓冲区的大小为6，显示缓冲区，选择一个未出现的选项，退出程序。 （二）结果显示 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 （三）结果分析 （1）在每个程序中需要先做P，后做V，二者要成对出现，夹在二者中间的代码段就是该进程的临界区。 （2）对同步信号量full和empty的P,V操作同样必须成对出现，但它们分别位于不同的程序中。 （3）无论在生产者进程中还是消费者进程中，两个P操作的次序不能颠倒：应先执行同步信号量的P操作，然后执行互斥信号量的P操作。否则可能造成进程死锁。 七、个人体验 虽然我也很想用java语言写这个程序，但是由于自己学艺不精，所以只能用C++写。通过这个实验我发现我以前有很多知识都忘记了，重新拿起课本学习9 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 时发现原来很多不懂得问题都有了新的认识，有一种豁然开朗的感觉。也为我考研开了一个好的开头。 我认为我完成的这个设计做的比较出色的地方是对C++语言中类以及数组的运用，其实这里我对数组的操作是按照“先进先出”的方法进行运作的，这是参考了栈的工作原理，因为缓冲区一般也是堆栈，比较符合设计要求。 这次实验中我感觉做的很粗糙，自己所想的模拟过程的确得到实现了，但是感觉灵活性不太高，思考还不过全面，应该以后多注意一下，多考虑考虑才是。 在这次实验中我重新将《C++程序设计》和《数据结构》的几个重要章节复习了一遍，对类、数组、C++的I/O流类库以及堆栈的语句格式、注意细节都再一次熟悉，感觉蛮有趣的。不过，在编程过程中许多语句的小问题还真是出现不少，而且感觉自己对C++强大丰富的语句方法用得太呆板，不够灵活，总是想到那些常用的，而忽略了颗粒让语句更简短的方法，以后要多多注意才是。 八、附录 // 生产者消费者1.cpp : Defines the entry point for the console application.// #include “stdafx.h” #include “iostream” using namespace std;class SeqSquare { public: SeqSquare(int n);~SeqSquare();void P(int x); //p操作 void V(int x); //v操作 bool IsEmpty(); //判断是否为空 bool IsFull(); //判断是否已满 void deca();void decb();int getSize();int getmaxSize();int gettop();int geta();int getb();protected: private: int *elements;int top,a,b,maxSize;};10 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 bool SeqSquare::IsEmpty() //判断是否为空 { return(top==-1)?true:false;} bool SeqSquare::IsFull() //判断是否已满 { return(top>=maxSize-1)?true:false;} void SeqSquare::deca(){ a--;} void SeqSquare::decb(){ b--;} int SeqSquare::getSize(){ return top+1;} int SeqSquare::getmaxSize(){ return maxSize;} int SeqSquare::gettop(){ return top;} int SeqSquare::geta(){ return a;} int SeqSquare::getb(){ 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 return b;} SeqSquare::SeqSquare(int n){ top =-1;a = b =0;maxSize = n;elements = new int[maxSize];} void SeqSquare::P(int x){ if(IsFull()==true){ a=a+1;} else { elements[++top] = x; } } void SeqSquare::V(int x){ if(IsEmpty()==true){ b = b+1;} else { x = elements[top--]; } } 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 void producer(SeqSquare *a) //生产者操作 { a->P(1);} void consumer(SeqSquare *a) //消费者操作 { a->V(1);} SeqSquare::~SeqSquare(){ delete elements;} //缓冲区显示 void showbuf(SeqSquare *a){ int i=a->getSize(); } int main(){ int i,n;cout<<“请输入缓冲区大小：”< cout<<“请选择操作： ”< 4.退出系统。 ”< ”< switch(i) { case 1: producer(s); if(s->geta()==0) { 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 cout< } else { cout< s->deca(); } break; case 2: consumer(s); if(s->getb()==0) { cout< } else { cout< } break; case 3: showbuf(s); cout< ”<<“可用空间为：”<<(n-s->getSize())< break; case 4: cout< break; case 5: cout< cin>>n; s = new SeqSquare(n); cout< break; default: cout< } } return 0;} 闽江学院 计算机系 网络操作系统课程设计 设计内容：进程机制与并发程序设计——linux下生产者与消费者的问题实现 目录： 一、设计内容····························3 二、设计思想····························4 三、系统结构····························5 四、PV操作代码··························5 五、C++程序代码·························6 六、运行结果截图························9 七、参考文献····························11 八、实验总结····························11 一、设计内容 进程机制与并发程序设计————linux下生产者与消费者的问题实现 1．实验目的 （1）掌握基本的同步互斥算法，理解生产者和消费者同步的问题模型。（2）了解linux中多线程的并发执行机制，线程间的同步和互斥。 2、实验环境：C/C++语言编译器 3、实验要求 （1）创建生产者和消费者线程 在linux环境下，创建一个控制台进程，在此进程中创建n个线程来模拟生产者或者消费者。这些线程的信息由本程序定义的“测试用例文件”中予以指定。 该文件的格式和含义如下： 3 1 P 3 2 P 4 3 C 4 1 4 P 2 5 C 3 1 2 4 第一行说明程序中设置几个临界区，其余每行分别描述了一个生产者或者消费者线程的信息。每一行的各字段间用Tab键隔开。不管是消费者还是生产者，都有一个对应的线程号，即每一行开始字段那个整数。第二个字段用字母P或者C区分是生产者还是消费者。第三个字段表示在进入相应线程后，在进行生产和消费动作前的休眠时间，以秒计时；这样做的目的是可以通过调整这一列参数，控制开始进行生产和消费动作的时间。如果是代表生产者，则该行只有三个字段。如果代表消费者，则该行后边还有若干字段，代表要求消费的产品所对应的生产者的线程号。所以务必确认这些对应的线程号存在并且该线程代表一个生产者。（2）生产和消费的规则 在按照上述要求创建线程进行相应的读写操作时，还需要符合以下要求： ①共享缓冲区存在空闲空间时，生产者即可使用共享缓冲区。 ②从上边的测试数据文件例子可以看出，某一生产者生产一个产品后，可能不止一个消费者，或者一个消费者多次地请求消费该产品。此时，只有当所有的消费需求都被满足以后，该产品所在的共享缓冲区才可以被释放，并作为空闲空间允许新的生产者使用。 ③每个消费者线程的各个消费需求之间存在先后顺序。例上述测试用例文件包含一行信息“5 C 3 l 2 4”，可知这代表一个消费者线程，该线程请求消费1，2，4号生产者线程生产的产品。而这种消费是有严格顺序的，消费1号线程产品的请求得到满足后才能继续往下请求2号生产者线程的产品。 ④要求在每个线程发出读写操作申请、开始读写操作和结束读写操作时分别显示提示信息。（3）相关基础知识 本实验所使用的生产者和消费者模型具有如下特点： 本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一个空缓冲区中。 消费者只消费指定生产者的产品。 在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。 本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该消费对象是否已经消费完毕并清除该产品。 linux用来实现同步和互斥的实体。在linux中，常见的同步对象有：信号量(Semaphore)、互斥量(Mutex)、临界段(CriticalSection)等。使用这些对象都分为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程中都可以使用，从而实现同步互斥。 二、设计思想 生产者进程与消费者进程是经典的同步互斥关系。系统创建两类进程：proceducer()和consumer()，分别用来描述生产者和消费者的行为。生产者与消费者问题是指若干进程通过循环缓冲池区交换数据。如下图所示，生产者进程不断向循环缓冲池区中写入数据（即生产数据），而消费者进程不断从循环缓冲池区中读出数据（即消费数据）。循环缓冲池共有N个缓冲区，缓冲区可以暂存一个产品，任何时刻只能有一个进程课对循环缓冲池进行操作。所有生产者和消费者要协调工作，以完成数据的交换。只要有空缓冲区，生产者就可以把产品送入缓冲区；只要有满缓冲区，消费者就可以从缓冲区中取走物品。 为了解决生产者和消费者问题，应该设置信号量和变量如下： full： 满缓冲区资源信号量，初值为0； empty：空缓冲区资源信号量，初值为n； in： 生产者指针，初值均为0； out： 消费者指针，均为0； mutex：缓冲区操作的互斥信号量，初值为1 三、系统结构 PCB* readyhead=NULL, * readytail=NULL;// 就绪队列——链表结构 PCB* consumerhead=NULL, * consumertail=NULL;// 消费者队列 PCB* producerhead=NULL, * producertail=NULL;// 生产者队列 processproc()---给PCB分配内存，产生相应的的进程 Pempty()---如果缓冲区满，该进程进入生产者等待队列； linkqueue(exe,&producertail);// 把就绪队列里的进程放入生产者队列的尾部 执行顺序：Main()---empty---in---full---out---finish 当缓冲池为空时，生产者生产产品in缓冲池 in=in+1 当缓冲池为满时，消费者消费产品out缓冲池 out=out+1 四、PV操作代码 semaphore empty=n;semaphore full=0;semaphore mutex=1;message buffer[n];int in=0; int out=0;void main(){ parbegin(proceducer(),consumer());} void proceducer(){ do { prodece a new meddage;P(empty);P(mutex);send a new message to buffer[in];in=(in+1)%n;V(mutex);V(full);} while(true);} void consumer(){ do { P(full);P(mutex);get a message from buffer[out];out=(out+1)%n;V(mutex);V(empty);comsume a message;}while(true);} 五、C++程序代码 #include “windows.h” #include “iostream.h” #include “math.h” #define random(rand()*10000)/RAND_MAX //定义一个随机函数来生产产品，并且使两个顾产品间的时间少于10秒 int long waiting(0);//正在等待的产品的数目 int buffer;//空位的总数目 char empty;//缓冲区空 char full;//缓冲区满 int count(0);//产品的号码数 int finish(0);//生产完毕的产品数目 DWORD a;void proceduce() { Sleep(10000);cout<<“缓冲区已空!”< } void getconsum(){ Sleep(10001);//产品被生产的函数，为了合理区分生产产品 cout<<“第”< HANDLE Mutex=CreateMutex(NULL, FALSE, “Mutex”);//用来实现进程的互斥 HANDLE proceducer=CreateSemaphore(NULL, 1,1, “proceducer”);//定义信号量来进行线程间的同步 HANDLE consumer=CreateSemaphore(NULL,0,3,“consum”);DWORD WINAPI consum(LPVOID pParm2)//消费的线程 { WaitForSingleObject(Mutex ,INFINITE);//p(mutex)来进行互斥操作 count++;//生产的是第几个产品 cout<<“第 ”< { if(waiting!=0){ cout<<“此时有”< else cout<<“没有产品在等待”< ReleaseMutex(Mutex);//释放互斥量，以便其他线程使用 WaitForSingleObject(proceducer,INFINITE);//等待生产 getconsum();//消费并取走 } else { cout<<“缓冲区已满，第”< return 0;} DWORD WINAPI proceducers(LPVOID pParm1)//生产者的线程 { while(true)//一直执行 { WaitForSingleObject(consum,INFINITE);//p(customers)，等待产品 WaitForSingleObject(Mutex,INFINITE);//等待互斥量 waiting--;//等待的产品数减一 ReleaseSemaphore(proceducer,1,NULL);//释放信号量 ResumeThread(proceducer);//唤醒消费进程 ReleaseMutex(Mutex);//v(mutex);proceduce();//生产 finish++;//消费的产品数加1 } return 0;} int main(int argc, char* argv[]){ cout<<“请输入缓冲区空位的总数目:”;cin>>buffer;cout<<“缓冲区共有”< cout< HANDLE hThread1;HANDLE hThread2;hThread2=::CreateThread(NULL,0,proceducers,NULL,0,NULL);//产生一个生产者进程 while(full!='y'){ Sleep(random);//产品随机进入 hThread1=::CreateThread(NULL,0,consum,NULL,a,NULL);cout< { cout<<“已经为”< else;} if(full=='y'){ cout<<“********对不起，缓冲区已满********”< } 六、运行结果截图 缓冲区空位总数目为1时运行结果截图： 缓冲区空位总数目为0和3时运行结果截图（其余部分如上当缓冲区空位总数目为1时的截图） 七、参考文献 1、计算机网络操作系统原理与应用 孔宪军 吕滨（本学期教科书） 2、网络操作系统课程设计计划书 陈卫老师 3、C程序设计（第三版）谭浩强 八、实验总结 刚刚看到课程设计的内容与要求时，不禁有点无从下手的感觉。经过一番思考后，才决定选择设计“进程机制与并发程序设计——linux下生产者与消费者的问题实现”这部分。设计这部分不仅仅需要用到C/C++编程，还需要编写相关的PV原语。由于自己的PV原语部分和C/C++编程学的不是很好，因此对我来说有点难。于是我就积极利用书本上的知识来编写PV原语，C/C++编程是参考书上的指点以及网络资源编写出来的。不懂得地方查资料、上网找、问问其他同学，最后终于慢慢的把课程设计做出来了。通过这次课程设计，才感觉到自己还是平时动手少，要经常动手去做实验才能真正学到东西。尤其是一些C/C++编程和PV原语的编写更需要平时多加练习才能学好用好。特别是C/C++编程在遇到语法有多处错误时，不能急，要冷静下来慢慢修改，知道程序正确。虽然是自己独立做的课程设计，但是其中还是有很多不懂的东西是问同学的，因此了解到学习不是单独的，应该是相互交流相互学习的。 操 作 系 统 实 验 报 告 (2)学院：计算机科学与技术学院 班级：计091 学号：姓名： 时间：2011/12/30 目 录 1.实验名称……………………………………………………3 2.实验目的……………………………………………………3 3.实验内容……………………………………………………3 4.实验要求……………………………………………………3 5.实验原理……………………………………………………3 6.实验环境……………………………………………………4 7.实验设计……………………………………………………4 7.1数据结构设计……………………………………………………………………4 7.2算法设计…………………………………………………………………………6 7.3功能模块设计……………………………………………………………………7 8.实验运行结果………………………………………………8 9.实验心得……………………………………………………9 附录：源代码（部分）…………………………………………………………………9 一、实验名称： 用C++实现银行家算法 二、实验目的： 通过自己编程来实现银行家算法，进一步理解银行家算法的概念及含义，提高对银行家算法的认识，同时提高自己的动手实践能力。 各种死锁防止方法能够阻止发生死锁，但必然会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁。本实验旨在了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生。 三、实验内容： 利用C++,实现银行家算法 四、实验要求： 1.完成银行家算法的设计 2.设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。 五、实验原理： 系统中的所有进程放入进程集合，在安全状态下系统收到进程的资源请求后，先把资源试探性的分配给它。之后，系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较，找出剩余资源能够满足的最大需求量的进程，从而保证进程运行完毕并归还全部资源。这时，把这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多，反复执行上述步骤。最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正执行本次分配，否则，本次资源分配暂不实施，让申请资源的进程等待。 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量之和。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定： (1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客； (2)顾客可以分期贷款，但贷款的总数不能超过最大需求量； (3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款； (4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。 六、实验环境： Win-7系统 Visual C++ 6.0 七、实验设计： 1.数据结构设计 定义结构体： struct Process//进程属性构成 { Source claim;//进程最大需求量 Source allocation;//进程占有量 Source claim_allocation;//进程需求量 Source currentAvail;//进程可获得量 }; 定义类对象： class Source //资源的基本构成以及功能 { private: public: int R1;//定义三类类资源 int R2;int R3; Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;} Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;} void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//设置各类资源 { R1=r1;R2=r2;R3=r3;} void add(Source s)//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;} void sub(Source s)//减法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;} bool lower(Source s)//比较 { if(R1 > s.R1)return false; if(R2 > s.R2)return false; if(R3 > s.R3)return false; return true;} }; class Data//封装所有数据 { public: Process *p;//进程指针 Source sum;//总资源量 Source available;//可获得量 Source ask;//请求量 int pLength;//进程个数 int * ruler;//逻辑尺 void clearProcess()//进程currentAvail清零 { for(int i=0;i { p[i].currentAvail.setSource(0, 0, 0);} } }; class DataInit//封装初始化数据函数类 { private: public: DataInit()//构造函数 { } void initLength(Data *db)//设置进程个数 { int n; cout<<“输入进程数: ”; cin>>n; db->pLength = n; db->p = new Process[n]; if(!db->p) {cout<<“error!no enough memory space！”;return;} db->ruler = new int[n]; if(!db->ruler) {cout<<“error!no enough memory space！”;return;} } 2.算法设计 class FindSafeList//寻找安全序列 { private: public: FindSafeList()//构造函数 {} bool checkList(Data *db)//检查一个序列安全性 { int i=0;//i用于循环 db->p[db->ruler[i]].currentAvail.add(db->available);//将当前系统可用资源量赋给该序列的第一个进程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若当前进程currentAvail大于该进程总资源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//该序列进程安全。返回true } bool exsitSafeList(Data *db)//判断是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//设置逻辑尺的刻度值 { db->ruler[i] = i;} while(1) //该循环将检测逻辑尺刻度值的全排列 { if(checkList(db)) //找到一个安全序列，返回true { return true;} db->clearProcess();//将所有进程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完毕后退出生成排列库函数的调用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//寻找安全序列 { //请求值大于系统当前可用资源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //请求值大于当前进程需求资源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根据请求，分配资源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判断是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滚，恢复分配前状态，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，将请求资源置零，返回3 return 3;} };3.功能模块设计 class Data//封装所有数据 class DataInit//封装初始化数据函数类 class Display//封装显示方法 class FindSafeList//寻找安全序列 struct Process//进程属性构成 void main()//主函数 八、实验运行结果： 输入进程数，及相关资源数量分配 选择算法完成的操作：1 查看进程情况 请求分配 2.1分配失败 2.2 分配成功 2.3 继续分配失败，退出 九、实验心得： 通过此次实验，我能够更加深入的理解银行家算法的执行过程，也懂得用银行家算法去防止发生死锁，有效地解决了资源利用率低的问题，保证了系统的安全性。 当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。 附录：源代码（部分） #include class Source //资源的基本构成以及功能 { private: public: int R1;//定义三类类资源 int R2;int R3; Source(int r1 = 0,int r2 = 0,int r3 = 0){ R1=r1;R2=r2;R3=r3;} Source(Source& s){ R1=s.R1;R2=s.R2;R3=s.R3;} void setSource(int r1 = 0,int r2 = 0,int r3 = 0)//设置各类资源 { R1=r1;R2=r2;R3=r3;} void add(Source s)//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;} void sub(Source s)//减法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;} bool lower(Source s)//比较 { if(R1 > s.R1)return false; if(R2 > s.R2)return false; if(R3 > s.R3)return false; return true;} }; struct Process//进程属性构成 { Source claim;//进程最大需求量 Source allocation;//进程占有量 Source claim_allocation;//进程需求量 Source currentAvail;//进程可获得量 }; class Data//封装所有数据 { public: Process *p;//进程指针 Source sum;//总资源量 Source available;//可获得量 Source ask;//请求量 int pLength;//进程个数 int * ruler;//逻辑尺 void clearProcess()//进程currentAvail清零 { for(int i=0;i { p[i].currentAvail.setSource(0, 0, 0);} } }; class DataInit//封装初始化数据函数类 { private: public: DataInit()//构造函数 { } void initLength(Data *db)//设置进程个数 { int n; cout<<“输入进程数: ”; cin>>n; db->pLength = n; db->p = new Process[n]; if(!db->p) {cout<<“error!no enough memory space！”;return;} db->ruler = new int[n]; if(!db->ruler){cout<<“error!no enough memory space！”;return;} } void setAsk(Data *db)//设置请求资源量 { int r1,r2,r3;r1=0;r2=0;r3=0; db->ask.setSource(r1,r2,r3);} void initSum(Data *db)//设置总资源量 { int r1,r2,r3;cout<<“Available(R1,R2,R3): ”;cin>>r1>>r2>>r3;db->sum.setSource(r1,r2,r3);} void initAvail(Data *db)//设置可获得量 { int r1,r2,r3;cout<<“输入初始分配 Allocation:n”;cout<<“available[R1,R2,R3]:n ”; cin>>r1>>r2>>r3; db->available.setSource(r1,r2,r3);} void initProcess(Data *db)//设置各进程属性值 { int r1,r2,r3;cout<<“输入t0时分配 Allocation:n”;for(int i=0;i cout<<'p'< cin>>r1>>r2>>r3; db->p[i].allocation.setSource(r1,r2,r3); cout<<'p'< cin>>r1>>r2>>r3; db->p[i].claim.setSource(r1,r2,r3); r1=db->p[i].claim.R1-db->p[i].claim.R1;//设置进程p[i] 的 claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource(r1, r2, r3); } } }; class Display//封装显示方法 { private: public: Display()//构造函数 { } void displaySource(Source s)//设置基本资源显示方式 {cout< displayAvailable(Source s)//显示可获得资源量 {displaySource(s);} void displayProcess(Process *p,int length)//显示进程基本信息 { for(int i=0;i { cout<<“ p”< displaySource(p[i].claim); cout<<“tt”; displaySource(p[i].allocation); cout< } cout< void displaySafeList(Data *db)//显示安全序列 { for(int i=0;i { cout<<“ p”< ”; displaySource(db->p[db->ruler[i]].currentAvail); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim); cout<<“ ”; displaySource(db->p[db->ruler[i]].allocation); cout<<“ ”; displaySource(db->p[db->ruler[i]].claim_allocation); cout<<“ true”; cout< } } void displayAskResult(Data *db,int n)//显示请求资源结果 { if(n==0) {cout<<“不分配，请求量大于当前可获得量!n”;return;} if(n==1) {cout<<“不分配，请求量大于当前可获得量!n”;return;} if(n==2) {cout<<“不分配，找不到安全序列!n”;return;} if(n==3) { cout<<“存在安全序列:”; for(int i=0;i {cout< cout< char c='N'; cout<<“查看安全序列详情?(Y/N)”; cin>>c; if(c=='Y'||c=='y') { cout<<“ 进程 currentavail claim allocation claim-allocation possiblen”; displaySafeList(db); } return; } } }; class FindSafeList//寻找安全序列 { private: public: FindSafeList()//构造函数 {} bool checkList(Data *db)//检查一个序列安全性 { int i=0;//i用于循环 db->p[db->ruler[i]].currentAvail.add(db->available);//将当前系统可用资源量 赋给该序列的第一个进程 if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail))//若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false {return false;} for(i=1;i< db->pLength;i++) { //当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvail db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].currentAvail); //当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量 db->p[db->ruler[i]].currentAvail.add(db->p[db->ruler[i-1]].allocation); //若当前进程currentAvail小于该进程需求量(claim-allocation)，返回false if(!db->p[db->ruler[i]].claim_allocation.lower(db->p[db->ruler[i]].currentAvail)) { return false;} //若当前进程currentAvail大于该进程总资源量，返回false if(!db->p[db->ruler[i]].currentAvail.lower(db->sum)) { return false;} } return true;//该序列进程安全。返回true } bool exsitSafeList(Data *db)//判断是否存在安全序列 { int i = 0; for(i = 0;i < db->pLength;i++)//设置逻辑尺的刻度值 { db->ruler[i] = i;} while(1) //该循环将检测逻辑尺刻度值的全排列 { if(checkList(db)) //找到一个安全序列，返回true { return true;} db->clearProcess();//将所有进程的currentAvail清零 if(!next_permutation(db->ruler,db->ruler+db->pLength)) //所有排列完毕后退出生成排列库函数的调用 { return false; } } return false;} int findSafeList(Data *db, int i=0)//寻找安全序列 { //请求值大于系统当前可用资源值，返回0 if(!db->ask.lower(db->available)) { return 0;} //请求值大于当前进程需求资源值，返回1 if(!db->ask.lower(db->p[i].claim_allocation)) { return 1;} Source s(db->p[i].allocation);//根据请求，分配资源值 db->available.sub(db->ask); db->p[i].allocation.add(db->ask); db->p[i].claim_allocation.sub(db->ask); if(!exsitSafeList(db))//判断是否存在安全序列 { db->available.add(db->ask); //不存在安全序列，回滚，恢复分配前状态，并返回2 db->p[i].allocation.sub(db->ask); db->p[i].claim_allocation.add(db->ask); return 2; } db->ask.setSource(0,0,0);//找到安全序列，将请求资源置零，返回3 return 3;} }; void main(){ Data *db;db=new Data;if(!db){ cout<<“error!no enough memory space！”;return;} DataInit dataInit;dataInit.initLength(db);//设置进程个数 dataInit.initSum(db);//设置系统总资源量 dataInit.initAvail(db);//设置当前系统可获得资源量 dataInit.initProcess(db);//设置t0时刻进程基本状态 Display display;FindSafeList findSafeList;int r1=0,r2=0,r3=0;int c;db->ask.setSource(r1,r2,r3);//设置请求资源为0，即无请求 c=findSafeList.findSafeList(db,0);//寻找安全序列，返回结果 if(c!=3){ cout<<“t0时刻的进程组不存在安全序列!n”;return;} int choice=1;int pi; while(choice){ cout<<“n 选择操作:n 查看进程情况n 请求分配资源n 0 退出n ”; cin>>choice;switch(choice){ case 1: { } case 2: { } case 0: { default: { } } } cout<<“当前资源量available[R1,R2,R3]:n ”;display.displayAvailable(db->available);cout<第二篇：操作系统课程设计--用多线程同步方法解决睡眠理发师问题(Sleeping-Barber_Problem)
第三篇：操作系统课程设计生产者消费者
第四篇：生产者与消费者的问题-----操作系统课程设计
第五篇：操作系统课程设计实验报告-用C++实现银行家算法
点击咨询 