和尚挑水问题课程设计.doc

课 程 设 计 书学 院 计算机学院 专 业 计算机科学与技术 班 级 课 程 题 目 和尚挑水问题 教 师 学 生 摘 要Linux是一类Unix计算机操作系统的统称，也是自由软件和开放源代码发展中最著名的例子。Linux作为一个免费、自由软件，内核版本不断升级。新的内核修订了旧内核的bug，并增加了许多新的特性。同时也使得Linux系统更加稳定、更加安全，进一步满足用户的功能需求。Linux 中的信号量(semphore)是一种资源锁，如果有一个任务试图获得一个已经被占用的信号量时，信号量会将其推到一个等待队列中，这时处理器会重获自由从而去执行其它代码，当持有信号量的进程将信号量释放后，处于等待队列中的那个任务将会被唤醒，并将获得该信号量。信号量是一种对多个进程访问共享资源进行控制的机制，其实为了解决互斥共享资源的同步问题而引入的机制。不能单独定义一个信号量，而只能定义一个信号量集，其中包括一组信号量，同一信号量集中的信号量使用同一引用ID，这样设置是为了多个资源或同步操作的需要。关键词：信号量，同步，互斥 I目 录1课程设计的目的及要求11.1课程设计的目的11.2课程设计的要求12准备工作22.1硬件及软件需要22.2了解信号量及信号量的系统调用函数：22.2.1信号量定义22.2.1信号量集得创建与打开semget()32.2.2信号量的操作semop()42.2.3信号量的控制semctl()63需求分析74整体设计84.1概要设计84.2程序流程图及运行结果8实验结果14总 结15参考文献16附 录17II1课程设计的目的及要求1.1课程设计的目的某寺庙中有小和尚、老和尚若干人。庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳 30 桶水，每次入水、取水仅为 1 桶，不可同时进行。水取自同一水井，水井路窄，每次只能容纳一个水桶取水，设水桶个数为 5 个。和尚挑水问题就是使用某种机制，能够使得若干名老和尚可以顺利地喝到水，若干名小和尚之间能够有条不紊地往水缸中入水。本课程设计的目的是使用Linux的信号量机制编程解决和尚挑水问题，通过本课程设计掌握Linux进程创建的方法，掌握信号量的使用方法。1.2课程设计的要求本课题所设计的系统要求实现以下功能。编写 2 个程序，程序 1 创建 3 个子进程，分别编号 A、B、C，用于模拟 3 名老和尚；程序 2 创建 3 个子进程，分别编号 C、D、E，用于模拟 3名小和尚。通过向屏幕输出语句模拟取水过程，如输出“目前水缸水量为 10 桶”表示目前水缸中有存水 10桶；输出“小和尚取水成功”表示从水井中成功取到 1 桶水；输出“小和尚倒 1 桶水到水缸中”表示小和尚将 1 桶水倒入水缸中。通过观察输出语句，可以发现执行过程是否发成冲突。使用 Linux 的信号量机制，编写解决和尚挑水问题的代码。要求给出编译所用到的 makefile 文件。2准备工作2.1硬件及软件需要CentOS6.4 gcc编译器 vim编辑器2.2了解信号量及信号量的系统调用函数：2.2.1信号量定义最简单的信号量是一个只有0与1两个值的变量，二值信号量。这是最为通常的形式。具有多个正数值的信号量被称之为通用信号量。在本章的其余部分，我们将会讨论二值信号量。P与V的定义出奇的简单。假定我们有一个信号量变量sv，两个操作定义如下：P(sv)如果sv大于0，减小sv。如果sv为0，挂起这个进程的执行。V(sv)如果有进程被挂起等待sv，使其恢复执行。如果没有进行被挂起等待sv，增加sv。信号量的另一个理解方式就是当临界区可用时信号量变量sv为true，当临界区忙时信号量变量被P(sv)减小，从而变为false，当临界区再次可用时被V(sv)增加。注意，简单的具有一个我们可以减小或是增加的通常变量并不足够，因为我们不能用C，C+或是其他的编程语言来表述生成信号，进行原子测试来确定变量是否为true，如果是则将其变为false。这就是使得信号量操作特殊的地方。信号量函数定义如下：#includeintsemctl(intsem_id,intsem_num,intcommand,.);intsemget(key_tkey,intnum_sems,intsem_flags);intsemop(intsem_id,structsembuf*sem_ops,size_tnum_sem_ops);事实上，为了获得我们特定操作所需要的#define定义，我们需要在包含sys/sem.h文件之前通常需要包含sys/types.h与sys/ipc.h文件。而在某些情况下，这并不是必须的。因为我们会依次了解每一个函数，记住，这些函数的设计是用于操作信号量值数组的，从而会使用其操作向比单个信号量所需要的操作更为复杂。注意，key的作用类似于一个文件名，因为他表示程序也许会使用或是合作所用的资源。相类似的，由semget所返回的并且为其他的共享内存函数所用的标识符与由fopen函数所返回的FILE*十分相似，因为他被进程用来访问共享文件。而且与文件类似，不同的进程会有不同的信号量标识符，尽管他们指向相同的信号量。key与标识符的用法对于在这里所讨论的所有IPC程序都是通用的，尽管每一个程序会使用独立的key与标识符。2.2.1信号量集得创建与打开semget()semget函数创建一个新的信号量或是获得一个已存在的信号量键值。调用原型：int semget(key_t key,int num_sems,int sem_flags);第一个参数key是一个用来允许不相关的进程访问相同信号量的整数值。所有的信号量是为不同的程序通过提供一个key来间接访问的，对于每一个信号量系统生成一个信号量标识符。信号量键值只可以由semget获得，所有其他的信号量函数所用的信号量标识符都是由semget所返回的。还有一个特殊的信号量key值，IPC_PRIVATE(通常为0)，其作用是创建一个只有创建进程可以访问的信号量。这通常并没有有用的目的，而幸运的是，因为在某些Linux系统上，手册页将IPC_PRIVATE并没有阻止其他的进程访问信号量作为一个bug列出。num_sems参数是所需要的信号量数目。这个值通常总是1。sem_flags参数是一个标记集合，与open函数的标记十分类似。低九位是信号的权限，其作用与文件权限类似。另外，这些标记可以与IPC_CREAT进行或操作来创建新的信号量。设置IPC_CREAT标记并且指定一个已经存在的信号量键值并不是一个错误。如果不需要，IPC_CREAT标记只是被简单的忽略。我们可以使用IPC_CREAT与IPC_EXCL的组合来保证我们可以获得一个新的，唯一的信号量。如果这个信号量已经存在，则会返回一个错误。如果成功，semget函数会返回一个正数；这是用于其他信号量函数的标识符。如果失败，则会返回-1。2.2.2信号量的操作semop()函数semop用来改变信号量的值：调用原型：int semop(int sem_id,struct sembuf*semops, size_tnum_sem_ops);第一个参数，sem_id，是由semget函数所返回的信号量标识符。第二个参数，sem_ops，是一个指向结构数组的指针，其中的每一个结构至少包含下列成员：structsembufshortsem_num;shortsem_op;shortsem_flg;第一个成员，sem_num，是信号量数目，通常为0，除非我们正在使用一个信号量数组。sem_op成员是信号量的变化量值。（我们可以以任何量改变信号量值，而不只是1）通常情况下中使用两个值，-1是我们的P操作，用来等待一个信号量变得可用，而+1是我们的V操作，用来通知一个信号量可用。最后一个成员，sem_flg，通常设置为SEM_UNDO。这会使得操作系统跟踪当前进程对信号量所做的改变，而且如果进程终止而没有释放这个信号量，如果信号量为这个进程所占有，这个标记可以使得操作系统自动释放这个信号量。将sem_flg设置为SEM_UNDO是一个好习惯，除非我们需要不同的行为。如果我们确实变我们需要一个不同的值而不是SEM_UNDO，一致性是十分重要的，否则我们就会变得十分迷惑，当我们的进程退出时，内核是否会尝试清理我们的信号量。semop的所用动作会同时作用，从而避免多个信号量的使用所引起的竞争条件。2.2.3信号量的控制semctl()semctl函数允许信号量信息的直接控制调用原型：int semctl(int sem_id,int sem_num,int command,.);第一个参数，sem_id，是由semget所获得的信号量标识符。sem_num参数是信号量数目。当我们使用信号量数组时会用到这个参数。通常，如果这是第一个且是唯一的一个信号量，这个值为0。command参数是要执行的动作，而如果提供了额外的参数，则是unionsemun，根据X/OPEN规范，这个参数至少包括下列参数：unionsemunintval;structsemid_ds*buf;unsignedshort*array;许多版本的Linux在头文件(通常为sem.h)中定义了semun联合，尽管X/Open确认说我们必须定义我们自己的联合。有多个不同的command值可以用于semctl。在这里我们描述两个会经常用到的值。这两个通常的command值为：SETVAL：用于初始化信号量为一个已知的值。所需要的值作为联合semun的val成员来传递。在信号量第一次使用之前需要设置信号量。IPC_RMID：当信号量不再需要时用于删除一个信号量标识。semctl函数依据command参数会返回不同的值。对于SETVAL与IPC_RMID，如果成功则会返回0，否则会返回-1。3需求分析某寺庙中有小和尚、老和尚若干人。庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳 30 桶水，每次入水、取水仅为 1 桶，不可同时进行。水取自同一水井，水井路窄，每次只能容纳一个水桶取水，设水桶个数为 5 个。和尚挑水问题就是使用某种机制，能够使得若干名老和尚可以顺利地喝到水，若干名小和尚之间能够有条不紊地往水缸中入水。先创建一个程序，创建三个子进程A、B、C模拟三个老和尚，隔一段时间久从水缸中取水饮用；创建另外一个程序，创建三个子进程a、b、c模拟三个小和尚，隔一段时间获得一个水桶并从水井中取水注入水缸中。如果水缸中没有水，老和尚就停止从水缸中取水，并等待小和尚加水；而当水缸中容量少于30桶，那么小和尚就向水缸中加水，直到水缸注满为止。如此循环不止。实现功能如下：（1）创建进程：手动创建A、B、C、a、b、c六个进程，都在界面上完成；要求包括进程的名称（不能重复）、执行时间和申请资源的等待时间等。在同一时刻可能有多个进行在内存申请资源，即可以输入多个进程的资源申请。（2）临界资源的管理，包括申请以及分配等，通过信号量和信号量集实现。（3）生产者消费者算法，判断是否可以进行资源的分配。任务目标通过信号量实现多进程之间对共享资源的互斥和同步。4整体设计4.1概要设计系统2个模块：输入输出，进程对资源的随机申请及分配，通过信号量和信号量集机制及生产者消费者算法实现临界资源管理，避免死锁。输入输出：包括系统运行所需要的进程的名称，执行时间，申请资源的等待时间，进程对资源的需要量等信息以及系统所要显示出的进程的创建信息，资源的分配信息，进行执行信息，进行动态申请资源信息等。进程对资源的随机申请及分配：根据所输入的进程、资源、以及进程对资源的最大申请情况，随机产生进程当前对资源的申请，输出相应的分配信息与进程执行信息并使用生产者消费者算法对进程的资源申请进行判断。临界资源的管理：创建相应个数的进程，完成进程的并发执行，使用互斥信号量使各进程互斥的进入各自的临界区对资源进行申请，进程执行完毕后，互斥的对资源进行恢复。避免死锁：对当前进程对资源的申请利用生产者消费者算法进行判断，看系统分配后是否处于安全状态，若处于安全状态，则将资源分配给进程，并输出分配信息，否则对不予以分配。4.2程序流程图及运行结果下图为master程序的流程图 见图 开始调用fork（）产生子进程 pidA调用fork（）产生子进程pidB调用fork（）产生子进程pidCPidA=0？PidB=0？PidC=0？pidA=-1？PidB=-1？PidC=-1？ 出错返回 结束循环调用m-w-s（）循环调用m-w-s（）NYNYYNYYNYYYN Y发出取水通知取水水缸中有没有水？调用m-w-s（）N等待2s 图1程序运行结果为下图：如上图当水缸没水的时候执行acolyte程序开始Pida=0？Pidb=0？Pidc=0？pidA=-1？PidB=-1？PidC=-1？ 出错返回 结束循环调用FILL-THE-BARREK（）循环调用FILL-THE-BARREK（）NYYYYY调用FILL-THE-BARREK（）水缸水量30桶？桶和井可同时取用？取水入缸 水满放弃已得到的桶或井NYNYNY调用fork()创建三个子程序 此图为acolyte程序的流程图，下图为程序执行结果：当水缸有水时，老和尚可以喝水：实验结果总 结经过这次的课程设计，让我经历了一次有意义的过程，让我了解了团队合作的重要性，起初我们只是在不停的各干各的，发现根本不可能完成预期的任务，后来我们坐下来讨论了系统的功能，然后各司其职，发现效果真的不一样，虽然在这一周的时间里我们做了很多，中间也遇到了一些问题，比如说临界资源管理和算法模块怎样结合起来，起初是将两个交叉起来，可是效果不是很好，最后还是决定将它们分开，慢慢地其他问题也同样得到了解决，这就是团队合作的力量，这个系统需要完善的内容还有很多，我们以后还会在一起讨论完善并改进，在此过程中，我也发现了编程是需要绝对的耐心与细心的，不然会造成一些难以修改的错误，导致整个程序进展出现问题。这对我们真的是一次很好的锻炼。参考文献1 华清远见嵌入式培训中心嵌入式Linux应用程序开发第二版人民邮电出版社，2013.12 鸟哥Linux私房菜基础学习篇第三版人民邮电出版社，2010.7附 录程序master.c：#include #include #include #include #include #include #include #define SLEEP_TIME2#define VAT_VOLUME30static int count;int M_w_s(int, const char);int main(void) pid_t pidA,pidB,pidC;int vat_id,vats;vat_id = semget(ftok(., v), 1, 0666|IPC_CREAT);init_sem(vat_id, VAT_VOLUME); /the barrels volumepidA = fork();if(pidA = 0)while(1)vats = M_w_s(vat_id, A);sem_p(vat_id);printf(Master A is coming to drink:)%d-1n,vats);else if(pidA 0)pidB = fork();if(pidB = 0)while(1)vats = M_w_s(vat_id, B);sem_p(vat_id);printf(Master B is coming to drink:)%d-1n,vats);else if(pidB 0)pidC = fork();if(pidC = 0)while(1)vats = M_w_s(vat_id, C);sem_p(vat_id);printf(Master C is coming to drink:)%d-1n,vats);else if(pidC = -1)perror(cannt create the fork Cn);return -47;elseperror(cannt create the fork Bn);return -53;elseperror(cannt create the fork An);return -59;exit(0);int M_w_s(int vat_id, const char ch)union semun vat_union;int vats = 0;if(!(vats = semctl(vat_id, 0, GETVAL, vat_union) & !count) count+;printf(Oh,acolytes,your Master %c wannna drink and fill up the vat quicliy:*n,ch);sleep(SLEEP_TIME);return vats;程序acolyte.c#include #include #include #include #include #include #include #define SLEEP_TIME2#define VAT_VOLUME30static int count;int M_w_s(int, const char);int main(void) pid_t pidA,pidB,pidC;int vat_id,vats;vat_id = semget(ftok(., v), 1, 0666|IPC_CREAT);init_sem(vat_id, VAT_VOLUME); /the barrels volumepidA = fork();if(pidA = 0)while(1)vats = M_w_s(vat_id, A);sem_p(vat_id);printf(Master A is coming to drink:)%d-1n,vats);else if(pidA 0)pidB = fork();if(pidB = 0)while(1)vats = M_w_s(vat_id, B);sem_p(vat_id);printf(Master B is coming to drink:)%d-1n,vats);else if(pidB 0)pidC = fork();if(pidC = 0)while(1)vats = M_w_s(vat_id, C);sem_p(vat_id);printf(Master C is coming to drink:)%d-1n,vats);else if(pidC = -1)perror(cannt create the fork Cn);return -47;elseperror(cannt create the fork Bn);return -53;elseperror(cannt create the fork An);return -59;exit(0);int M_w_s(int vat_id, const char ch)union semun vat_union;int vats = 0;if(!(vats = semctl(vat_id, 0, GETVAL, vat_union) & !count) count+;printf(Oh,acolytes,your Master %c wannna drink and fill up the vat quicliy:*n,ch);sleep(SLEEP_TIME);return vats;头文件sem_com.h：/* sem_com.h */#ifndefSEM_COM_H#defineSEM_COM_H#include #include union semunint val;struct semid_ds *buf;unsigned short *array;int init_sem(int, int);int del_sem(int);int sem_p(int);int sem_v(int); #endif /* SEM_COM_H */程序sem_com.c：#include #include #include #include #include #include #include #define SLEEP_TIME2#define VAT_VOLUME30static int count;int M_w_s(int, const char);int main(void) pid_t pidA,pidB,pidC;int vat_id,vats;vat_id = semget(ftok(., v), 1, 0666|IPC_CREAT);init_sem(vat_id, VAT_VOLUME); /the barrels volumepidA = fork();if(pidA = 0)while(1)vats = M_w_s(vat_id, A);sem_p(va