21春《操作系统》大作业题目及要求答案（题目三）.doc

1、 网络教育学院操作系统课 程 设 计 题 目： 题目三参考 学习中心： 专 业： 年 级： 学 号： 学 生： 1.谈谈你对本课程学习过程中的心得体会与建议？答：每一次课程设计度让我学到了在平时课堂不可能学到的东西。所以我对每一次课程设计的机会都非常珍惜。不一定我的课程设计能够完成得有多么完美，但是我总是很投入的去研究去学习。所以在这两周的课设中，熬了2个通宵，生物钟也严重错乱了。但是每完成一个任务我都兴奋不已。一开始任务是任务，到后面任务就成了自己的作品了。总体而言我的课设算是达到了老师的基本要求。总结一下有以下体会。1、网络真的很强大，用在学习上将是一个非常高效的助手。几乎所有的资料都能够

2、在网上找到。从linux虚拟机的安装，到linux的各种基本命令操作，再到gtk的图形函数，最后到文件系统的详细解析。这些都能在网上找到。也因为这样，整个课程设计下来，我浏览的相关网页已经超过了100个(不完全统计)。当然网上的东西很乱很杂，自己要能够学会筛选。不能决定对或错的，有个很简单的方法就是去尝试。就拿第二个实验来说，编译内核有很多项小操作，这些小操作错了一项就可能会导致编译的失败，而这又是非常要花时间的，我用的虚拟机，编译一次接近3小时。所以要非常的谨慎，尽量少出差错，节省时间。多找个几个参照资料，相互比较，慢慢研究，最后才能事半功倍。2、同学间的讨论，这是很重要的。老师毕竟比较忙。

3、对于课程设计最大的讨论伴侣应该是同学了。能和学长学姐讨论当然再好不过了，没有这个机会的话，和自己班上同学讨论也是能够受益匪浅的。大家都在研究同样的问题，讨论起来，更能够把思路理清楚，相互帮助，可以大大提高效率。3、敢于攻坚，越是难的问题，越是要有挑战的心理。这样就能够达到废寝忘食的境界。当然这也是不提倡熬夜的，毕竟有了精力才能够打持久战。但是做课设一定要有状态，能够在吃饭，睡觉，上厕所都想着要解决的问题，这样你不成功都难。4、最好在做课设的过程中能够有记录的习惯，这样在写实验报告时能够比较完整的回忆起中间遇到的各种问题。比如当时我遇到我以前从未遇到的段错误的问题，让我都不知道从何下手。在经过大

4、量的资料查阅之后，我对段错误有了一定的了解，并且能够用相应的办法来解决。题目四：进程同步与互斥 生产者-消费者问题一、设计思路：1.1生产者消费者问题生产者消费者问题（Producer_consumer）是一个经典的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将此产品提供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在它们之间设置有个缓冲区的缓冲池，生产者进程可将它所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区取得一个产品消费。尽管所有的生产者进程和消费者进程都是以异步的方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者

5、进程向一个已装有消息尚未被取走产品的缓冲区投放产品。如下图所示：1.2、生产者和消费者原理分析在同一个进程地址空间内执行两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻挡，直到新的物品被生产出来。1.3、生产者与消费者功能描述：生产者功能描述：在同一个进程地址空间内执行两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。当生产者线程生产

6、物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。消费者功能描述：消费者线程从缓冲区获得物品，然后释放缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。二、基本内容进程同步是指几个进程相互合作，一个进程到达某个点后，除非另一个进程已经完成某些操作，否则就不得不停下来，等待这些操作的结束，这就是进程同步的概念。生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中

7、供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费或生产某类资源，当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。 通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者是相互等效的，只要缓冲区未满，生产者就可以将产品送入缓冲区，类似地，只要缓冲区

8、未空，消费者就可以从缓冲区中去走物品并消费它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。 在生产者消费者问题中，信号灯具有两种功能。首先，它是跟踪资源的生产和消费的计数器；其次，它是协调资源的生产者和消费者之间的同步器。消费者通过再一指派给它的信号灯上做P操作来表示消耗资源，而生产者通过在同一信号灯上做V操作来表示生产资源。再这种信号灯的实施中，计数在每次P操作后减1，而在每次V操作中加1。个这一计数器的初始值是可利用的资源数目。当资源是不可利用时，将申请资源的进程放置在等待队列中。如果有一个资源释放，在等待队列中的第一个进程被唤醒并得到资源

9、的控制权。 为解决这一类生产者消费者问题，设置了两个同步信号灯，一个说明空缓冲区的数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明缓冲区的数目，用full表示，其初制值为0。由于有界缓冲区是一个零界资源，必须互斥使用，所以另外还需设置一个互斥信号灯mutex,起初值为1。 假定在生产者和消费者之间的公用缓冲区中，具有n个缓冲区，这时可以利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者互相等效果，只要缓冲池未满，生产者便可以将消息送入缓冲池；只要缓冲池未空，消费者便可以从缓冲池中取

10、走一个消息。在生产者-消费者问题中应注意：首先，在每个程序中用于互斥的wait(mutex)和signal(mutex)必须成对出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。生产者与消费者进程共享一个大小固定的缓冲区。其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个或多个消费者从缓冲区中取数据。假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取出数据的存储单元，如图，指针in和out初始化指向缓冲区的第一个存

11、储单元。生产者从第一个存储单元开始存放数据，一次存放一条数据一条数据且in指针向后移一个位置，当in 指针指向第n个存储单元，下一次将指向第一个存储单元，如此循环反复使用缓冲区。消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”，可以被生产者再次使用。每次取走一条数据，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表示取数据位置： ：被占用单元 ：空存储单元图：生产者/消费者循环使用缓冲区首先，生产者和消

12、费者可能同时进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。这显然是不允许的。所以，必须使生产者和消费者互斥进入缓冲区。即某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其他任何生产者。其次，生产者不能向满的缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则

13、，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图所示，伪代码如图所示。2、涉及的数据结构用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中县有RJ类资源K个。需求矩阵M

14、AX。这是一个N*M的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。如果MAXi,j=K，则表示进程I需要RJ类资源的最大数目为K。矩阵Allocation。这也是一个N*M的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得RJ类资源的数目为K。矩阵Need。这也是一个N*M的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程I还需要RJ类资源K个，方能完成其任务。 上述三个矩阵间存在下述关系： Needi,j=MAXi,j-Allocationi,j三、数据流程图：3.1、生产者

15、3.2、消费者3.3模块说明：const unsigned short SIZE_OF_BUFFER = 10; /缓冲区长度 unsigned short ProductID = 0; /产品号 unsigned short ConsumeID = 0; /将被消耗的产品号 unsigned short in = 0; /产品进缓冲区时的缓冲区下标 unsigned short out = 0; /产品出缓冲区时的缓冲区下标 int g_bufferSIZE_OF_BUFFER; /缓冲区是个循环队列 bool g_continue = true; /控制程序结束 HANDLE g_hMut

16、ex; /用于线程间的互斥 HANDLE g_hFullSemaphore; /当缓冲区满时迫使生产者等待 HANDLE g_hEmptySemaphore; /当缓冲区空时迫使消费者等待 DWORD WINAPI Producer(LPVOID); /生产者线程 DWORD WINAPI Consumer(LPVOID); /消费者线程 3.4源程序#include #include const unsigned short SIZE_OF_BUFFER = 20;/有界缓冲区长度int g_bufferSIZE_OF_BUFFER;/开辟缓冲区，用数组表示，可以看成是一个循环队列unsig

17、ned short ProductID = 0;/新生产出来的产品的产品号unsigned short ConsumeID = 0;/被消耗的产品的产品号unsigned short in = 0;/产品进缓冲区时的缓冲区下标，用于记录生产者的指针位置unsigned short out = 0;/产品出缓冲区时的缓冲区下标，用于记录消费者的指针位置bool g_continue = 1;/控制程序运行：1表示继续运行，0表示停止运行HANDLE g_hMutex;/线程间的互斥信号量HANDLE g_hFullSemaphore;/资源信号量：缓冲区满HANDLE g_hEmptySemap

18、hore;/资源信号量：缓冲区空DWORD WINAPI Producer(LPVOID);/生产者线程DWORD WINAPI Consumer(LPVOID);/消费者线程const unsigned short PRODUCERS_COUNT=4;/生产者的个数const unsigned short CONSUMERS_COUNT=3;/消费者的个数const unsigned short THREADS_COUNT=PRODUCERS_COUNT+CONSUMERS_COUNT;/总线程数HANDLE hThreadsPRODUCERS_COUNT;/各线程的handleDWORD

19、producerIDCONSUMERS_COUNT;/生产者线程的标识符DWORD consumerIDTHREADS_COUNT;/消费者线程的标识符/*-生产一个产品开始-*/生产一个产品，输出其ID号void Produce()std:coutstd:endl;std:cerr生产一个产品: +ProductID;std:coutstd:endl;/*-生产一个产品结束-*/*-把新生产的产品放入缓冲区开始-*/把新生产的产品放入缓冲区void Append()std:cerr把生产的产品送入缓冲区;g_bufferin=ProductID;in=(in+1)%SIZE_OF_BUFFE

20、R;std:cerrstd:endl;std:cout缓冲区 产品 生产者/消费者std:endl;/新产品放入缓冲区后，输出缓冲区当前的状态for(int i=0;iSIZE_OF_BUFFER;+i) /输出缓冲区下标if (i10)std:couti g_bufferi;elsestd:couti g_bufferi;if(i=in)if(g_bufferi10)std:cout ;elsestd:cout ;std:cout - 生产者;/输出生产者的指针位置if(i=out)if(g_bufferi10)std:cout ;elsestd:cout ;std:cout - 消费者;/

21、输出消费者的指针位置std:coutstd:endl;/*-把新生产的产品放入缓冲区结束-*/*-消费一个产品开始-*/void Consume()/消费一个产品std:coutstd:endl;std:cerr消费一个产品: ConsumeID;std:coutstd:endl;/*-消费一个产品结束-*/*-从缓冲区中取出一个产品开始-*/从缓冲区中取出一个产品void Take()std:coutstd:endl;std:cerr从缓冲区取出一个产品;ConsumeID=g_bufferout;out=(out+1)%SIZE_OF_BUFFER;std:cerrstd:endl;std

22、:coutstd:endl;std:cout缓冲区 产品 生产者/消费者std:endl;/取出一个产品后，输出缓冲区当前的状态for(int i=0;iSIZE_OF_BUFFER;+i) /输出缓冲区下标if(i10)std:couti g_bufferi;elsestd:couti g_bufferi;if(i=in)if(g_bufferi10)std:cout ;elsestd:cout ;std:cout - 生产者;/输出生产者的指针位置if(i=out)if(g_bufferi10)std:cout ;elsestd:cout ;std:cout - 消费者;/输出消费者的指针

23、位置std:coutstd:endl;/*-从缓冲区中取出一个产品结束-*/*-生产者线程开始-*/生产者线程DWORD WINAPI Producer(LPVOID lpPara) while(g_continue)/资源信号量的P操作WaitForSingleObject(g_hFullSemaphore,INFINITE); /互斥信号量的P操作WaitForSingleObject(g_hMutex,INFINITE); /生产一个产品Produce();/把新生产的产品放入缓冲区Append();Sleep(2000);/互斥信号量的V操作ReleaseMutex(g_hMutex)

24、; /资源信号量的V操作ReleaseSemaphore(g_hEmptySemaphore,1,NULL); return 0;/*-生产者线程结束-*/*-消费者线程开始-*/消费者线程DWORD WINAPI Consumer(LPVOID lpPara) while(g_continue)/资源信号量的P操作WaitForSingleObject(g_hEmptySemaphore,INFINITE); /互斥信号量的P操作WaitForSingleObject(g_hMutex,INFINITE); /从缓冲区中取出一个产品Take();/消费一个产品Consume();Sleep(

25、2000);/互斥信号量的V操作ReleaseMutex(g_hMutex); /资源信号量的V操作ReleaseSemaphore(g_hFullSemaphore,1,NULL); return 0;/*-消费者线程结束-*/*-创建生产者线程开始-*/void createPT()/创建生产者线程for(int i=0;iPRODUCERS_COUNT;+i)hThreadsi=CreateThread(NULL,0,Producer,NULL,0,&producerIDi);if(hThreadsi=NULL)g_continue=0;/*-创建生产者线程结束-*/*-创建消费者线程开

26、始-*/void createCT()/创建消费者线程for (int j=0;jCONSUMERS_COUNT;+j)hThreadsPRODUCERS_COUNT+j=CreateThread(NULL,0,Consumer,NULL,0,&consumerIDj);if (hThreadsj=NULL)g_continue=0;/*-创建消费者线程结束-*/*-主函数开始-*/void main()/创建互斥信号量g_hMutex=CreateMutex(NULL,FALSE,NULL); /创建资源信号量g_hFullSemaphore=CreateSemaphore(NULL,SIZ

27、E_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL);g_hEmptySemaphore=CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL);/创建生产者线程createPT();/创建消费者线程createCT();/不按回车键的话程序会一直运行下去while(g_continue) /按回车键终止程序if(getchar()g_continue = 0;/*-主函数结束-*/四、 总结：生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。