生产者消费者问题以及银行家算法.docx
《生产者消费者问题以及银行家算法.docx》由会员分享，可在线阅读，更多相关《生产者消费者问题以及银行家算法.docx（41页珍藏版）》请在冰点文库上搜索。
生产者消费者问题以及银行家算法
武汉工程大学
计算机科学与工程学院
综合设计报告
设计名称：
操作系统综合设计
设计题目：
进程同步与死锁
学生学号：
专业班级：
学生姓名：
学生成绩：
指导教师（职称）：
完成时间：
14年2月17日至14年2月28日
武汉工程大学计算机科学与工程学院制
说明：
1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。
2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。
3、指导教师评语一栏由指导教师就学生在整个综合设计期间的表现、设计完成情况、报告的质量及答辩等方面，给出客观、全面的评价。
4、所有学生必须参加综合设计的答辩环节。
凡不参加答辩者，其成绩一律按不及格处理。
答辩小组成员应由2人及以上教师组成。
5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。
6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。
7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。
答辩记录表
学生姓名：
学号：
班级：
答辩地点：
答辩内容记录：
答辩成绩
合计
分值
各项分值
评分标准
实际得分
合计得分
备注
25
10
在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。
15
在规定时间内能准确、完整、流利地回答教师所提出的问题。
答辩小组成员（签字）：
2014年2月28日
成绩评定表
学生姓名：
学号：
班级：
类别
合计
分值
各项分值
评分标准
实际得分
合计得分
备注
平时表现
10
10
按时参加综合设计，无旷课、迟到、早退、违反实验室纪律等情况。
完成情况
30
20
按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。
10
能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。
报告质量
35
10
报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。
5
课题背景介绍清楚，综述分析充分。
5
设计方案合理、可行，论证严谨，逻辑性强，具有说服力。
5
符号统一；图表完备、符合规范要求。
5
能对整个设计过程进行全面的总结，得出有价值的结论或结果。
5
参考文献数量在3篇以上，格式符合要求，在正文中正确引用。
答辩情况
25
10
在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。
15
在规定时间内能准确、完整、流利地回答教师所提出的问题。
总评成绩
指导教师评语
指导教师：
（签字）日期：
2014年2月28日
一、综合设计目的、条件、任务和内容要求：
《操作系统》在计算机科学中是一门核心专业基础课，涉及较多硬件和软件知识。
在计算机软、硬件课程的设置上，它起着承上启下的作用。
其特点是概念多、较抽象、涉及的知识面广。
《操作系统综合设计》是计算机科学与技术专业学生的一门实践课程，是学习完操作系统课程后的课程设计，本课程的教学目的是，通过学习，使学生了解计算机操作系统的发展特点；理解操作系统的基本概念、组成和各部分的功能；掌握计算机操作系统设计的基本原理和方法；理解常见操作系统的结构原理并能熟练使用。
《进程同步与死锁》课题，要求学生熟悉Windows中的线程及进程的创建，掌握利用Windows中的同步机制实现线程同步，掌握用银行家算法进行死锁的避免避免亮的____________________________________________________________________________________________________________________________。
培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力。
设计任务和内容要求：
实现生产者消费者问题，利用银行家算法实现进程的死锁避免。
二、进度安排：
第1周（2.17-2.18）：
学生熟悉课题的任务和要求，查阅相关文献和资料，并做好编码准备
第1周（2.19-2.21）：
程序编码、调试
第2周（2.24-2.27）：
程序编码、调试和测试，书写报告
第2周（2.28）：
答辩、检查、验收、递交设计报告
三、应收集资料及主要参考文献：
应收集的资料：
面向对象程序设计思想和方法
高级程序设计语言参考手册
操作系统、软件工程方面参考书籍
主要参考文献：
[1]汤子瀛等.计算机操作系统[M].西安：
西安电子科技大学出版社，2007.2.
[2]刘斌，王忠.面向对象程序设计VisualC++[M].北京：
清华大学出版社，2008.
[3]姬涛,周启生.计算机程序设计[M].北京：
中国传媒大学出版社,2010.263-284.
[4]CTrapsandPitfalls.C陷阱与缺陷[M].北京：
人民邮电出版社,2008.22-36.
四、摘要：
为了提高资源利用率和系统吞吐量，操作系统引入并发程序设计技术，程序的执行不再是顺序的，封闭的。
在多个进程并发运行的过程中，进程之间可能产生相互制约的关系，即竞争和协作。
为了协调各进程有序正确的进行，就需要各进程间能相互通信。
如果各进程之间不加以来控制，就会产生错误，如与时间有关的错误等。
这就需要考虑进程之间的同步和互斥等问题。
操作系统中经典的“生产者—消费者”问题正反映了进程并发执行的这种关系。
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
本课程设计所完成的就是对“生产者—消费者”问题的模拟，以及对银行家死锁避免算法设计。
本系统根据操作系统中并发进程、临界区、同步和互斥等基本概念及理论进行设计。
关键词：
进程；生产者；消费者；银行家；避免
五、Abstract：
Inordertoimproveresourceutilizationandthroughputofthesystem,operatingsystemintroducingconcurrentprogrammingtechniques,theexecutionoftheprogramisnolongerasequential,closed.Intheprocessofmultipleconcurrentprocessesrunning,theinteractionrelationshipbetweenprocessesispossible,competitionandcooperation.Inordertocoordinatetheprocessorderlycorrectly,youneedtocommunicatebetweenprocesses.Ifthecontrolhasnottheprocess,youwillgenerateanerror,suchastimerelatederrors.Problemswhichneedconsiderationofprocesssynchronizationandmutualexclusionbetweenetc..Operatingsystemintheclassic"producer-consumer"problemisareflectionoftheprocessoftheconcurrentexecutionofthisrelationship.Avoiddeadlockinthemethod,therestrictionsimposedbytheweakerconditions,canobtainsatisfactorysystemperformance.Thestateofthesystemisdividedintosecuritystatusandinsecurityinthemethod,aslongasthesystemcanalwaysbeinasafestate,canavoiddeadlock.Thebasicideaistoallocateresourcesbankersalgorithm,determinewhetherthesystemissafe;if,toassign.Thiscourseisdesignedtohaveachievedisto"producer-consumer"simulationproblems,andtoavoiddeadlockofbankersalgorithmdesign.Thissystemisdesignedbasedontheconceptofconcurrentoperatingsystemprocess,thecriticalregion,synchronizationandmutexandtheory.
Keywords：
process;producer;consumers;bankers;avoid
目录
摘要………………………………………………………………………………………II
Abstract…………………………………………………………………………………...III
第一章课题背景……………………………………………………….…………………..1
1.1课题背景………………………………………………………………………………...1
1.2课题目的…………………………………………………..……………………………1
1.3课题意义…………………………………………………..……………………………1
1.4应解决的问题……………………………………………..……………………………2
第二章设计简介及设计方案论述………………………………………………..………..3
2.1设计简介…………………………………………………..………………………….…3
2.2设计方案论述…………..…………………………………..………………………….…3
第三章详细设计…………………………………………………………..………………....5
3.1界面设计及流程…………………………………………..………………………….…...5
3.2主要函数功能及说明……………………………………………..………..………….….5
第四章设计结果及分析…………………………………………………..………………....8
4.1程序调试………………………….….…………...………………………………..….….8
4.2程序测试.…………………………………………………..……………………………...9
总结…….……………………………………………………..……………………………13
致谢…….……………………………………………………..……………………………14
参考文献…….………………..………………………………..……………………………15
附录主要程序代码………...………………………………..……………………………16
摘要
为了提高资源利用率和系统吞吐量，操作系统引入并发程序设计技术，程序的执行不再是顺序的，封闭的。
在多个进程并发运行的过程中，进程之间可能产生相互制约的关系，即竞争和协作。
为了协调各进程有序正确的进行，就需要各进程间能相互通信。
如果各进程之间不加以来控制，就会产生错误，如与时间有关的错误等。
这就需要考虑进程之间的同步和互斥等问题。
操作系统中经典的“生产者—消费者”问题正反映了进程并发执行的这种关系。
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
本课程设计所完成的就是对“生产者—消费者”问题的模拟，以及对银行家死锁避免算法设计。
本系统根据操作系统中并发进程、临界区、同步和互斥等基本概念及理论进行设计。
关键词：
进程；生产者；消费者；银行家；避免
Abstract
Inordertoimproveresourceutilizationandthroughputofthesystem,operatingsystemintroducingconcurrentprogrammingtechniques,theexecutionoftheprogramisnolongerasequential,closed.Intheprocessofmultipleconcurrentprocessesrunning,theinteractionrelationshipbetweenprocessesispossible,competitionandcooperation.Inordertocoordinatetheprocessorderlycorrectly,youneedtocommunicatebetweenprocesses.Ifthecontrolhasnottheprocess,youwillgenerateanerror,suchastimerelatederrors.Problemswhichneedconsiderationofprocesssynchronizationandmutualexclusionbetweenetc..Operatingsystemintheclassic"producer-consumer"problemisareflectionoftheprocessoftheconcurrentexecutionofthisrelationship.Avoiddeadlockinthemethod,therestrictionsimposedbytheweakerconditions,canobtainsatisfactorysystemperformance.Thestateofthesystemisdividedintosecuritystatusandinsecurityinthemethod,aslongasthesystemcanalwaysbeinasafestate,canavoiddeadlock.Thebasicideaistoallocateresourcesbankersalgorithm,determinewhetherthesystemissafe;if,toassign.Thiscourseisdesignedtohaveachievedisto"producer-consumer"simulationproblems,andtoavoiddeadlockofbankersalgorithmdesign.Thissystemisdesignedbasedontheconceptofconcurrentoperatingsystemprocess,thecriticalregion,synchronizationandmutexandtheory.
Keywords：
process;producer;consumers;bankers;avoid
第一章课题背景
1.1课题背景
本次课程设计通过模拟计算机操作系统中经典的“生产者—消费者问题”以及“银行家死锁避免算法”，生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。
在同一个进程地址空间内执行的两个线程。
生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。
消费者线程从缓冲区中获得物品，释放缓冲区。
当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。
当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。
用银行家算法实现资源分配，了解资源在进程并发执行的过程中的资源分配策略，一组进程在执行的时间上是重叠的，即进程并发执行[1]。
在多个进程并发运行的过程中，进程之间可能是无关的，也可能是交互的。
交互进程之间可能产生的关系，包括竞争和协作。
在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。
通过本次课程设计从而进行学习进程之间的互斥，对系统资源更好的分配[2]。
1.2课题目的
本次课程设计是课程结束后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，掌握同步互斥算法，理解生产者和消费者同步的问题模型，了解多线程的并发执行机制，线程间的同步互斥问题，加深对操作系统基础理论和重要算法的理解，深入理解生产者与消费者问题以及银行家算法的实质，了解进程在操作系统中是如何运行的，通过这次课程设计加强学生的动手能力。
在熟练掌握死锁发生原理和解决死锁问题的基础上，利用一种程序设计语言模拟实现利用银行家算法实现死锁避免，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
1.3课题意义
生产者消费者问题可以让我们更好的实现窗体应用编程，熟悉MFC变成思想和方法，巩固在操作系统原理课上所学的知识，加深对操作系统中进程同步和互斥、临界区管理，管程等问题的认识和理解。
在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁.所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，他们都无法在向前推进.要预防死锁，有摒弃“请求和保持"条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法.但是,在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生.而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法.利用银行家算法,我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生[3]。
在避免死锁方法中允许进程动态地申请资源，但系银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。
为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
1.4应解决的问题
在生产者消费者问题中，我们可以启动和关闭生产消费，设置生产速度和消费速度，当设置的数字越大，生产或者消费速度就越慢，生产者生产的产品最大只能存储100，如果到达100后，则消费和生产的速度就一致；在银行家死锁避免算法中，进行资源的动态合理分配，避免系统出现死锁状态。
第二章设计简介及设计方案论述
2.1设计简介
生产者消费者问题中点“启动”按钮，创建两组线程，一组为生产者，另一组为消息者，生产者线程每生产一件产品就对生产的产品数加1，并显示在第一个文本框；消费者线程每消费一件产品就对消费的产品数加1，并显示在第二个文本框。
缓冲区的大小为100（因为主要是为了演示同步问题，其实这里并没有分配缓冲区，只要生产的产品总数减消费的产品总数<=100，且消费的产品总数不超过生产的产品总数就达到了同步的要求了）。
在生产速度和消费速度对应的文本框中输入正整数，然后点“设置生产和消费速度”按钮，可以设置生产者和消费者的速度。
银行家死锁避免算法设计可以动态显示银行家算法及安全性算法的每一步的执行情况。
2.2设计方案论述
对于这次设计方案简述如下：
首先对于“生产者消费者问题”，运用MFC进行编程，创建两个进程，一个是生产者，另一个是消费者，然后创建线程，让生产速度和消费速度随着设定的速度不同而改变；银行家死锁避免算法是对于资源试图进行分配，若不能分配成功，则显示系统不安全，返回原来的状态，如果能分配成功，则显示分配成功，并且输出分配的序列。
流程图如下：
第三章界面及函数设计
3.1界面设计及流程
图3-1生产者消费者界面
Figure3-1producerconsumerinterface
3.2主要函数功能及说明
3.2.1生产消费速度函数设置
该函数可以由用户自己设置生产速度和消费速度，当设置的数字越大则速度越慢，生产者的速度要大于消费者的速度，否则消费者一直在等待生产者生产产品。
voidCMyDlg:
:
OnSetspeed（）
{
CStringstr;
CWnd*pWnd=GetDlgItem（IDC_EDITPRODUCER）;
pWnd->GetWindowText（str.GetBuffer（200）,200）;
m_PSpeed=atoi（str）;
pWnd=GetDlgItem（IDC_EDITCONSUMER）;
pWnd->GetWindowText（str.GetBuffer（200）,200）;
m_CSpeed=atoi（str）;
UpdateData（true）;
}
3.2.2程序启动函数
用户点击启动按钮，生产者开始生产产品，消费者消费产品，它们的速度一样。
voidCMyDlg:
:
OnOK（）
{
this->UpdateData（false）;
this->Init（）;
}
3.2.3银行家数据结构
（1）可利用资源向量Available，其中的每个元素代表一类可利用的资源数目；
（2）最大需求矩阵Max，它定义了系统中每个进程对每类资源的最大需求；
（3）分配矩阵Allocation，定义了系统中每个进
升级会员 