操作操作系统大型作业.docx
《操作操作系统大型作业.docx》由会员分享，可在线阅读，更多相关《操作操作系统大型作业.docx（21页珍藏版）》请在冰点文库上搜索。
操作操作系统大型作业
操作系统课程设计
所在班级：
0310401班
学生学号：
031040109
学生姓名：
李雨晴
论文题目：
生产者和消费者问题
任课教师：
李艳老师
完成日期：
2012年12月2日
目录
操作系统课程设计1
一、课程的地位、目标和任务3
二、课程设计的基本要求3
1.课程设计要求：
3
2.学习要求：
3
三、题目分析3
1.题目的特点：
3
2.采用信号量机制:
4
2.1.PV原语操作的动作4
2.2信号量4
四、课程设计的内容5
1.实验程序的结构图（流程图）5
2.数据结构及信号量定义的说明5
2.1CreateThread5
2.2.CreateMutex6
2.3.CreateSemaphore6
2.功能模块7
五、课程实现的内容7
1.课程设计的实验环境7
2.实验的步骤8
2.1打开VC8
2.2在工程中创建源文件"R_WP1.cpp"：
8
2.3通过调用菜单命令项build->buildall进行编译连接8
3.代码实现的具体分析8
3.1．使用信号量解决生产者-消费者问题10
3.2．使用消息传递解决生产者-消费者问题12
六、个人体会15
参考文献15
附录：
具体实现代码16
一、课程的地位、目标和任务
“操作系统”是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要实践环节。
本课程通过设计实现一个综合作业，加深对操作系统原理的理解，提高综合运用所学知识的能力，培养学生独立工作和解决问题的能力，取得设计与调试的实践经验，为今后进一步从事计算机系统软件和应用软件的分析、研制和开发打下良好的基础。
二、课程设计的基本要求
1.课程设计要求：
教学内容：
用信号量机制解决生产者和消费者问题。
重点：
信号量实现进程同步的算法
难点：
进程同步的实现
2.学习要求：
理解生产者和消费者模型，掌握利用信号量实现进程同步的方法，通过对实际问题的编程实现，获得实际应用和编程能力。
三、题目分析
1.题目的特点：
生产者-消费者（producer-consumer）问题，也称作有界缓冲区（bounded-buffer）问题，两个进程共享一个公共的固定大小的缓冲区。
其中一个是生产者，用于将消息放入缓冲区；另外一个是消费者，用于从缓冲区中取出消息。
问题出现在当缓冲区已经满了，而此时生产者还想向其中放入一个新的数据项的情形，其解决方法是让生产者此时进行休眠，等待消费者从缓冲区中取走了一个或者多个数据后再去唤醒它。
同样地，当缓冲区已经空了，而消费者还想去取消息，此时也可以让消费者进行休眠，等待生产者放入一个或者多个数据时再唤醒它。
2.采用信号量机制:
生产者-消费者（producer-consumer）问题非常适合用信号量机制来解决。
为了能让多个进程通过特殊变量展开交互，一个进程在某一关键点上被迫停止执行直至收到对应的特殊变量，通过这一措施，来达到复杂进程间的交互，这种特殊变量就是信号量。
为了能够用信号量传送信号，进程可用P、V两个特殊操作来发送和接收信号，如果协作进程的相应信号仍未送到，则进程被挂起直至信号达到为止。
信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用临界区的进程数。
Dijkstra同时提出了对信号量操作的PV原语。
2.1.PV原语操作的动作
P原语操作的动作是：
1．S减1；
2.若S减1后仍大于或等于零，则进程继续执行；
3.若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是：
1.S加1；
2.若相加结果大于零，则进程继续执行；
3.若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。
在PV原语执行期间不允许有中断的发生。
―――――――――――――――――――――――――――――――――――――
说明：
要保证PV是原子操作，对于操作系统，只须在操作过程中关中断即可。
AndrewS.Tanenbaum对信号量的定义有所不同，其PV操作也有区别。
―――――――――――――――――――――――――――――――――――――
2.2信号量
信号量是一个整数，其值不小于0。
它表示被积累下来的唤醒操作数。
P原语操作的动作是：
1.检查S是否大于0。
2.若S>0，则S=S–1；否则，执行P操作的进程将睡眠，并且此时P操作并未结束。
V原语操作的动作是：
1.S=S+1。
2.如果一个或多个进程在该信号量上睡眠，无法完成先前的P操作，则有系统选择其中一个并允许它完成P操作。
四、课程设计的内容
1.实验程序的结构图（流程图）
2.数据结构及信号量定义的说明
2.1CreateThread
功能——创建一个在调用进程的地址空间中执行的线程
格式
HANDLECreateThread（LPSECURITY_ATTRIBUTESlpThreadAttributes,
DWORDdwStackSize,
LPTHREAD_START_ROUTINElpStartAddress,
LPVOIDlpParamiter,
DWORDdwCreationFlags,
LpdwordlpThread）;
2.2.CreateMutex
功能——创建一个命名或匿名的互斥量对象
格式:
HANDLECreateMutex（LPSECURITY_ATTRIBUTESlpMutexAttributes,
BOOLbInitialOwner,
LPCTSTRlpName）;
参数说明:
lpMutexAttributes——必须取值NULL。
bInitialOwner——指示当前线程是否马上拥有该互斥量（即马上加锁）。
lpName——互斥量名称。
2.3.CreateSemaphore
功能——创建一个命名或匿名的信号量对象
格式:
HANDLECreateSemaphore（LPSECURITY_ATTRIBUTESlpSemaphoreAttributes,
LONGlInitialCount,
LONGlMaximumCount,
LPCTSTRlpName）;
参数说明:
lpSemaphoreAttributes——必须取值NULL。
lInitialCount——信号量的初始值。
该值大于0，但小于lMaximumCount指定的最大值。
lMaximumCount——信号量的最大值。
lpName——信号量名称。
参数说明:
lpThreadAttributes——指向一个LPSECURITY_ATTRIBUTES（新线程的安全性描述符）。
dwStackSize——定义原始堆栈大小。
lpStartAddress——指向使用LPTHRAED_START_ROUTINE类型定义的函数。
lpParamiter——定义一个给进程传递参数的指针。
dwCreationFlags——定义控制线程创建的附加标志。
lpThread——保存线程标志符（32位）
3.功能模块
五、课程实现的内容
1.课程设计的实验环境
本实验是在WinXP＋VC6.0环境下实现的，利用WindowsSDK编制实例程序。
所以试验需要在windows下安装VC后进行。
VC是一个集成开发环境，其中包含了WindowsSDK所有工具和定义；所以安装了VC后就不用特意安装SDK了。
2.实验的步骤
2.1打开VC
打开VC,选择菜单项file->new,选择projects选项卡并建立一个名为"R_WP1"的win32consoleapplicatoin工程；创建时注意指定创建该工程的目录；
2.2在工程中创建源文件"R_WP1.cpp"：
选择菜单项project->addtoproject->files，在选择框中输入自己想要创建的文件名，这里是"R_WP1.cpp"；在接下来询问是否创建新文件时回答"yes"；然后通过Workspace->FileView->SourceFiles打开该文件，在其中编辑源文件并保存.
2.3通过调用菜单命令项build->buildall进行编译连接
可以在指定的工程目录下得到debug->R_WP1.exe程序，然后把给定的test.txt文件存入该debug目录下，就可以在控制台进入该debug目录运行程序了。
需要强调的是在创建数据文件时，由于涉及到文件格式问题，最好在记事本中手工逐个输入数据，而不要拷贝粘贴数据。
3.代码实现的具体分析
为了跟踪缓冲区中的消息数目，需要一个变量count。
如果缓冲区最多存放N个消息，则生产者的代码会首先检查count是否达到N，如果是，则生产者休眠；否则，生产者向缓冲区中放入一个消息，并增加count的值。
消费者的代码也与此类似，首先检测count是否为0，如果是，则休眠；否则，从缓冲区中取出消息并递减count的值。
同时，每个进程也需要检查是否需要唤醒另一个进程。
代码可能如下：
//缓冲区大小
#defineN100
intcount=0;//跟踪缓冲区的记录数
/*生产者进程*/
voidprocedure（void）
{
intitem;//缓冲区中的数据项
while（true）//无限循环
{
item=produce_item（）;//产生下一个数据项
if（count==N）//如果缓冲区满了，进行休眠
{
sleep（）;
}
insert_item（item）;//将新数据项放入缓冲区
count=count+1;//计数器加1
if（count==1）//表明插入之前为空，
{//消费者等待
wakeup（consumer）;//唤醒消费者
}
}
}
/*消费者进程*/
voidconsumer（void）
{
intitem;//缓冲区中的数据项
while（true）//无限循环
{
if（count==0）//如果缓冲区为空，进入休眠
{
sleep（）;
}
item=remove_item（）;//从缓冲区中取出一个数据项
count=count-1;//计数器减1
if（count==N-1）//缓冲区有空槽
{//唤醒生产者
wakeup（producer）;
}
consume_item（item）;//打印出数据项
}
}
看上去很美，哪里出了问题，这里对count的访问是有可能出现竞争条件的：
缓冲区为空，消费者刚刚读取count的值为0，而此时调度程序决定暂停消费者并启动执行生产者。
生产者向缓冲区中加入一个数据项，count加1。
现在count的值变成了1.它推断刚才count为0，所以此时消费者一定在休眠，于是生产者开始调用wakeup（consumer）来唤醒消费者。
但是，此时消费者在逻辑上并没有休眠，所以wakeup信号就丢失了。
当消费者下次运行时，它将测试先前读到的count值，发现为0（注意，其实这个时刻count已经为1了），于是开始休眠（逻辑上）。
而生产者下次运行的时候，count会继续递增，并且不会唤醒consumer了，所以迟早会填满缓冲区的，然后生产者也休眠，这样两个进程就都永远的休眠下去了。
3.1．使用信号量解决生产者-消费者问题
首先了解一下信号量吧，信号量是E.W.Dijkstra在1965年提出的一种方法，它是使用一个整型变量来累计唤醒的次数，供以后使用。
在他的建议中，引入了一个新的变量类型，称为信号量（semaphore），一个信号量的取值可以为0（表示没有保存下来的唤醒操作）或者为正值（表示有一个或多个唤醒操作）。
并且设立了两种操作：
down和up（分别为一般化后的sleep和wakeup，其实也是一般教科书上说的P/V向量）。
对一个信号量执行down操作，表示检查其值是否大于0，如果该值大于0，则将其值减1（即用掉一个保存的唤醒信号）并继续；如果为0，则进程休眠，而且此时down操作并未结束。
另外，就是检查数值，修改变量值以及可能发生的休眠操作都作为单一的，不可分割的原子操作来完成。
下面开始考虑用信号量来解决生产者-消费者问题了，不过在此之前，再次分析一下这个问题的本质会更清晰点：
问题的实质在于发给一个（尚）未休眠进程（如上的消费者进程在只判断了count==0后即被调度出来，还未休眠）的wakeup信号丢失（如上的生产者进程在判断了count==1后以为消费者进程休眠，而唤醒它）了。
如果它没有丢失，则一切都会很好。
#defineN100//缓冲区中的槽数目
typedefintsemaphore;//信号量一般被定义为特殊的整型数据
semaphoremutex=1;//控制对临界区的访问
semaphoreempty=N;//计数缓冲区中的空槽数目
semaphorefull=0;//计数缓冲区中的满槽数目
/*生产者进程*/
voidproceducer（void）
{
intitem;
while
（1）
{
item=procedure_item（）;//生成数据
down（&empty）;//将空槽数目减1
down（&mutex）;//进入临界区
insert_item（item）;//将新数据放入缓冲区
up（&mutex）;//离开临界区
up（&full）;//将满槽的数目加1
}
}
/*消费者进程*/
voidconsumer（voi）
{
intitem;
while
（1）
{
down（&full）;//将满槽数目减1
down（&mutex）;//进入临界区
item=remove_item（）;//从缓冲区中取出数据项
up（&mutex）;//离开临界区
up（&empty）;//将空槽数目加1
consumer_item（item）;//处理数据项
}
}
3.2．使用消息传递解决生产者-消费者问题
这种IPC方式使用两条原语send和receive，也是系统调用。
如：
send（dest,&msg）//将消息msg发送到目标（进程）dest中
receive（src,&msg）//接收由src过来的msg,如果没有消息可用，则可能阻塞接收者
消息传递系统会面临位于网络中不同机器上的通信进程的情形，所以会更加的复杂。
如：
消息可能被网络丢失，一般使用确认（ACK）消息。
如果发送方在一定的时间段内没有收到确认消息，则重发消息。
如果消息本身被正确接收，但是返回的ACK消息丢失，发送方则重发消息，这样接收方就会收到两份同样的消息。
一般使用在每条原始消息的头部嵌入一个连续的序号来解决这个问题。
另外，消息传递系统还需要解决进程命名的问题，在send和receive系统调用中指定的进程必须没有二义性的。
还有其他的一些问题，如性能问题，身份认证等等，不过那个就会扯多了，还是看看如果解决这个生产者-消费者的问题吧：
#defineN100//缓冲区中的槽数目
/*生产者进程*/
voidproceducer（void）
{
intitem;
messagemsg;//消息缓冲区
while
（1）
{
item=procedure_item（）;//生成数据
receive（consumer,&msg）;//等待消费者发送空的缓冲区
build_msg（&msg,item）;//创建待发送消息
send（consumer,&msg）;//发送数据项给消费者
}
}
/*消费者进程*/
voidconsumer（voi）
{
intitem,i;
messagemsg;
for（i=0;isend（producer,&msg）;//发送给生产者N个空缓冲区
while
（1）
{
receive（producer,&msg）;//接收包含数据项的消息
item=extract_item（&msg）;//解析消息，并组装成数据项
send（proceduer,&msg）;//然后又将空缓冲区发送回生产者
consumer_item（item）;//处理数据项
}
}
运行结果：
在这个解决方案中，共使用了N条消息，有点类似于上一个的共享内存缓冲区的N个槽，消费者进程这边首先通过一个for循环将N条空消息发送给生产者。
当生产者向消费者传递一个数据项时，是通过取走每一条接收到的空消息，然后送回填充了内容的消息给消费者的。
通过这种方式，整个消息传递系统中的总的消息数（包括空的消息+存了数据项的消息==N）是不变的。
如果运行过程中，生产者进程的速度比消费者快，则所有的消息最终都会塞满，然后生产者进程就会等待消费者（即使调用procedure也是阻塞在receive处），直到消费者返回一条空的消息；反之亦然。
六、个人体会
生产者消费者问题是一个多线程同步问题的经典案例。
该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。
生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。
与此同时，消费者也在缓冲区消耗这些数据。
要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。
同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。
通常采用进程间通信的方法解决该问题，常用的方法有信号灯法[1]等。
如果解决方法不够完善，则容易出现死锁的情况。
出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。
该问题也能被推广到多个生产者和消费者的情形。
本次课程设计通过模拟计算机操作系统中经典的“生产者—消费者问题”，巩固了我在操作系统原理课上所学的知识，加深了对操作系统中进程同步和互斥等问题，完成了多进程同步方法解决生产者－消费者问题全部过程，结果满足设计要求。
设计过程中遇到不少困难，在反复研究老师的PPT及课本的原理后才逐渐明晰怎样将代码实现，以前学习C++没有深入了解到线程这个概念，在学习Java的时候才知道有专门的线程类。
通过本次设计，我掌握了通过研究进程机制和信号量实现生产者消费者问题的并发控制全过程，尤其是对多进程程序设计方法有了更深的理解，开拓了思路，锻炼了实践动手能手。
参考文献
【1】汤子瀛等.计算机操作系统.西安电子科技大学出版社.2007年2月
【2】张尧学等编著，计算机操作系统教程，清华出版社。
2002.2
【3】严蔚敏，吴伟民编著，数据结构，清华大学出版社。
2002
【4】陈向群编著，操作系统教程，北京大学出版社，2001.07
【5】面向对象程序设计与VisualC++6.0教程陈天华编著清华大学出版社.2009年7月
附录：
具体实现代码
#include
#include
constunsignedshortSIZE_OF_BUFFER=10;//缓冲区长度
unsignedshortProductID=0;//产品号
unsignedshortConsumeID=0;//将被消耗的产品号
unsignedshortin=0;//产品进缓冲区时的缓冲区下标
unsignedshortout=0;//产品出缓冲区时的缓冲区下标
intg_buffer[SIZE_OF_BUFFER];//缓冲区是个循环队列
boolg_continue=true;//控制程序结束
HANDLEg_hMutex;//用于线程间的互斥
HANDLEg_hFullSemaphore;//当缓冲区满时迫使生产者等待
HANDLEg_hEmptySemaphore;//当缓冲区空时迫使消费者等待
DWORDWINAPIProducer（LPVOID）;//生产者线程
DWORDWINAPIConsumer（LPVOID）;//消费者线程
intmain（）
{
//创建各个互斥信号
g_hMutex=CreateMutex（NULL,FALSE,NULL）;
g_hFullSemaphore=CreateSemaphore（NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL）;
g_hEmptySemaphore=CreateSemaphore（NULL,0,SIZE_OF_BUFFER-1,NULL）;
//调整下面的数值，可以发现，当生产者个数多于消费者个数时，
//生产速度快，生产者经常等待消费者；反之，消费者经常等待
constunsignedshortPRODUCERS_COUNT=3;//生产者的个数
constunsignedshortCONSUMERS_COUNT=1;//消费者的个数
//总的线程数
constunsignedshortTHREADS_COUNT=PRODUCERS_COUNT+CONSUMERS_COUNT;
HANDLEhThreads[PRODUCERS_COUNT];//各线程的handle
DWORDproducerID[CONSUMERS_COUNT];//生产者线程的标识符
DWORDconsumerID[THREADS_COUNT];//消费者线程的标识符
//创建生产者线程
for（inti=0;ihThreads[i]=CreateThread（NULL,0,Producer,NULL,0,&producerID[i]）;
if（hThreads[i]==NULL）return-1;
}
//创建消费者线程
for（i=0;ihThreads[PRODUCERS_COUNT+i]=CreateThread（NULL,0,Consumer,NULL,0,&
升级会员 