技工院--苹果-桔子问题的实现.doc

《操作系统》课程设计任务书
题目： 苹果-桔子问题的实现
学生姓名： 邢海啸 班 级： 物联网工程1班
学 号： 14480136 指导教师： 张清/贾娟娟
一、 设计目的
学生通过该题目的设计过程，掌握进程同步问题的原理、软件开发方法并提高解决实际问题的能力。
二、 设计内容
1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。
2、编写程序实现苹果-桔子问题。桌上有一个空盘子，只允许放一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果。
三、 设计要求及工作量
1、 分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数据结构）。
2、 设计合适的测试用例，对得到的运行结果要有分析。
3、 设计中遇到的问题，设计的心得体会。
4、文档：课程设计打印文档每个学生一份，并装在统一的资料袋中。
5、光盘：每个学生的文档和程序资料建在一个以自己学号和姓名命名的文件夹下，刻录一张光盘，装入资料袋中。
四、 要提交的成果
1. 设计说明书一份，内容包括：
1) 中文摘要100字；关键词3-5个；
2) 设计思想；
3）各模块的伪码算法；
4）函数的调用关系图；
5）测试结果；
6）源程序（带注释）；
7）设计总结；
8) 参考文献、致谢等。
2. 刻制光盘一张。
五、设计进度计划及时间安排
周次
日期
内容
地点
第1周
星期一~二
教师讲解设计要求
查找参考资料
教室
图书馆
星期三~五
算法设计，编程实现
教室
第2周
星期一~三
调试测试，撰写文档
教室
星期四~五
检查程序，答辩
教室
六、主要参考资料
1.汤子瀛，哲凤屏.《计算机操作系统》.西安电子科技大学学出版社.
2.王清，李光明.《计算机操作系统》.冶金工业出版社.
3.孙钟秀等. 操作系统教程. 高等教育出版社
4.曾明.  Linux操作系统应用教程. 陕西科学技术出版社.
5. 张丽芬，刘利雄.《操作系统实验教程》. 清华大学出版社.
6. 孟静， 操作系统教程－－原理和实例分析. 高等教育出版社
7. 周长林，计算机操作系统教程. 高等教育出版社
8. 张尧学，计算机操作系统教程，清华大学出版社
9. 任满杰，操作系统原理实用教程，电子工业出版社
10.张坤.操作系统实验教程，清华大学出版社

目 录
1.绪论 1
1.1设计任务 1
1.2设计思想 1
1.3基础知识 2
2.各模块伪码算法 3
2.1父亲进程模块 3
2.2母亲进程模块 5
2.3儿子进程模块 7
2.4女儿进程模块 9
2.5Print函数 11
3. 函数调用关系图 12
3.1函数调用图 12
4.测试结果 13
5.源程序 17
6.设计总结 22
参考文献 23
致 谢 24

摘 要
本设计实际是生产者—消费者的变形，通过有界缓冲区把生产者和消费者联系起来。假定生产者和消费者的优先级是相同的，只要缓冲区未满，生产者就可以往缓冲区内放入产品。苹果与橘子的问题是典型的进程同步问题。本问题利用C语言实现相应的P、V原语。主要过程可用生产消费者来模拟，这里，生产者（父亲和母亲）放入缓冲区（盘子）的产品有两类（苹果和桔子），消费者（女儿和儿子）也有两类，每类消费者只消费其中固定的一类产品。生产者和消费者共享缓冲区，缓冲区中有空时，生产者可放入产品（不许放重），待缓冲区中有产品时，消费者可取出产品（不许取重），否则等待。
关键字：进程同步；P、V操作；信号量

1.绪论
1.1设计任务
桌上有一个空盘子，只允许放一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果。
这个问题实际上是两个生产者和两个消费者被连接到仅能放一个产品的缓冲器上。生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者则各自去需要的产品消费，但消费的方式不同。解决此类问题利用记录型信号量机制和P、V操作来实现进程同步。进程同步是指一个进程的执行依赖于另一个进程的信号或消息，当一个进程没有得到来自与另一个进程的信号或消息时则等待，直到信号或消息到达才被唤醒。
1.2设计思想
本实验进行操作系统课设的主要任务是模拟生产者与消费者问题的一个衍生，即实现苹果--橘子问题。这个题目有两个生产者，分别生产橘子和苹果。有两个消费者，分别消费苹果和橘子。同时，因为两个生产者和两个消费者同时对一个缓冲区进行操作。所以应互斥的访问的缓冲区以保证程序的正确性。本次进程的目的就是加深个进程之间的正确有效的访问一个存储单元缓冲区，即同步和互斥。也要涉及到信号量在互斥访问中的使用,生产者和消费者问题的实现和流程问题。当计算机中两个或者多个进程在执行时需要使用公用缓冲区，并且对该缓冲区采取了互斥措施，这时如果并发执行这些进程的时候就会造成CPU时间的极大浪费，这是操作系统设计要求不允许的。而这种现象在操作系统和用户进程中大量存在。因此为了解决这一问题，提出了同步的概念，即把异部环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。
该问题是典型的进程同步问题。某些进程为了完成同一任务分工合作，由于合作的每一个进程都是独立的不可预知的推进，这就需要相互合作的进程在某些合作点上协调各自的工作。当合作进程中的一个到达合作点后，在尚未得到其他合作进程发来的消息或信号前应阻塞自己，直到其合作进程发来协调信号或消息后才能被唤醒。这就是进程同步要解决的问题。

1.3基础知识
生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
借助C语言实现进程同步经典问题—苹果-桔子问题，用高级语言编写和调试一个进程同步程序，以加深对进程同步机制的理解。通过用C语言模拟进程同步实现，加深理解有关进程同步机制的概念及P、V操作的应用。通过该题目的设计过程，掌握进程同步问题的原理、软件开发方法并提高解决实际问题的能力。
这是进程同步与互斥问题的模拟，可以把向盘子放或取水果的每一个过程可以转为一个进程的操作，这些进程是互斥的，同时也存在一定的同步关系。通过编程实践时，实际是随机的调用一个进程的操作，而这些进程的操作相当于程序中的函数调用。而计算机在执行时每一个时刻只能执行一个操作，这就是互斥的表现。同步的模拟可以类似于函数调用时的前提关系即先决条件。这样进程同步模拟就完全可以通过函数的调用来实现。为下面吃水果的问题创建进程并实现进程之间的同步模型。能够处理以下的情形：桌子上有一只盘子，最多可容纳两个水果，每次只能放入或者取出一个水果。爸爸专门向盘子中放苹果，妈妈专门向盘子中放橘子，两个儿子专门等待吃盘子中的橘子，两个女儿专门等吃盘子中的苹果。

2.各模块伪码算法
2.1父亲进程模块
爸爸向盘子中放一个苹果操作：Father()，plat_size表示盘子，初始值为0，plat_size=apple+orange，执行father操作后，plat_size=1；则daughter处于等待状态。
cout<<"Father调用."<<endl;
if(Plate_Size==1)
{ Father_lag=1; //Father()等待
Print();
if(Mother_lag==false)
MonFa_c=1; }
else
{ Father();
if(Daughter_lag==true)
{ Daughter01_lag=false;//Daughter等待取消
Daughter (); //处于等待的Daughter自动调用
}
} break;
爸爸放苹果进程的操作流程如图2.1：

开始
Plat_size=1?
father进程调用:apple++,
plat_size=orang+apple,调用print()
daughter等待
调用daughter进程
father处于等待状态
结束
否
是
是
否

图2.1爸爸放苹果进程操作流程图

2.2母亲进程模块
妈妈向盘子中放一个橘子操作：Mother() ，plat_size表示盘子，初始值为0，plat_size=apple+orange，执行mother操作后，plat_size=1；则son处于等待状态。如图所示，若mother放入前plat_size=1，则必须等待。
cout<<"Mother调用."<<endl;
if(Plate_Size==1)
{ Mother_lag=true; //Mother()等待
Print();
if(Father_lag==false)
MonFa_c=1; }
else
{ Mother();
if(Son_lag==true) //Son等待
{ Son_lag=false;//Son等待取消
Son(); //处于等待的Son()自动调用
}
} break;
妈妈放桔子进程的操作流程如图2.2：

开始
Plat_size=1?
mother进程调用：orange++,
plat_size=orang+apple,调用print()
son等待
调用son进程
mother处于等待状态
结束
否
是
是
否

图2.2妈妈放桔子进程操作流程图

2.3儿子进程模块
儿子从盘子取一个橘子操作：Son()，son操作要进行，则必须plat_size=1，且盘子中必须有orange。若orange==0，则son必须等待。
cout<<"Son调用."<<endl;
if(orange==0)
{ Son_lag=true; //Son处于等待
Print();
}
else
{ Son();
if((Father_lag==true)&&(Mother_lag==true))
{ if(MonFa_c==1) //Father和Mother同时处于等待，但Father先等待，因此先调用
{ Father_lag=false;
Father();
MonFa_c=2; }
else //Father和Mother同时处于等待，但Mother先等待，因此先调用 { Mother_lag=false;
Mother();
MonFa_c=1; }
}
} break;
儿子取桔子的操作流程如图2.3：

开始
orange==0?
Son进程处于等待状态
是
son进程调用：orange--；plat_size--；
调用print()
否
Mother/father等待状态
按等待先后顺序调用mother()或father()操作
结束
是
否

图2.3儿子取桔子操作流程图

2.4女儿进程模块
女儿从盘子取一个苹果操作：Daugther()，daughter操作要进行，则必须plat_size=1，且盘子中必须有apple。若apple==0，则daughter必须等待。Daghter进程调用中apple--;plat_size--;
cout<<"Daughter调用."<<endl;
if(apple==0)
{ Daughter_lag=true; //Daughter等待
Print();
}
else
{ Daughter ();
if((Father_lag==true)&&(Mother_lag==true))
{ if(MonFa_c==1) //Father和Mother同时处于等待，但Father先等待，因此先调用 { Father_lag=false;
Father();
MonFa_c=2; }
else //Father和Mother同时处于等待，但Mother先等待，因此先调用 { Mother_lag=false;
Mother();
MonFa_c=1;
}
女儿取苹果的操作流程如图2.4：

开始
apple==0?
daughter进程处于等待状态
是
daughter进程调用：apple--；plat_size--；
调用print()

否
Mother/father等待状态
按等待先后顺序调用mother()或father()操作
结束
是
否

图2.4 女儿取苹果操作流程图

2.5 Print模块
用于输出盘子中苹果和橘子的个数，水果总个数及有哪些进程处于等待状态。
void Print() //Print函数（打印盘子剩余水果及各进程等待状态）
{
cout<<"现在盘子里有"<<apple<<"个苹果,"<<orange<<"个橘子,"<<"共有
"<<apple+orange<<"个水果."<<endl;
if(Father_lag==1)
cout<<"Father进程处于等待状态,";
if(Mother_lag==1)
cout<<"Mother进程处于等待状态,";
if(Son_lag==1)
cout<<"Son进程处于等待状态,";
if(Daughter_lag==1)
cout<<"Daughter进程处于等待状态,";
if(((Father_lag==0)
&&(Mother_lag==0)&&(Son_lag==0)&&(Daughter_lag==0))!=1)
cout<<endl;
}
输出模块的操作流程如图2.5：

开始

输出水果个数

Father_lag==1?

N

Y
输出父亲进程正在等待

Mother_lag==1?

N

Y
输出母亲进程正在等待

Son_lag==1?

N

Y
输出儿子进程正在等待

转下页

接上页
Daughter_lag==1?

N

输出女儿进程正在等待
Y

Father_lag==0?

N

输出结束
Y

结束

图2.5Print模块

3.函数调用关系图
本程序有6个函数组成：main主函数，father父亲函数，mother母亲函数，son儿子函数，daughter女儿函数，print输出函数。
主函数调用父亲函数、母亲函数、儿子函数、女儿函数、输出函数。
父亲函数、母亲函数、儿子函数、女儿函数调用输出函数。

Main

Son
Daughter
Mather
Father

Print

图3.1函数调用关系图

4.测试结果
4.1调用次数1次
初始运行状态如下：运行程序后界面上显示“请输入调用次数”，根据调用的次数，系统会做出相应的调用。初始设置了1次。初始为mather（）调用。此过程中初始化缓冲区（盘子）里有0个苹果，1个桔子。father，mother，son，daughter进程均处于等待状态。处于等待的son自动被调用。father,mother,daughter进程均处于等待状态如图所示：

图4.1 初始状态图

4.2调用次数4次
在第二次调用过程中，消费者daughter被调用。调用之后存储单元的缓冲区中没有任何生产者生产的产品。因此father,mother,son进程均处于等待状态。当出现daughter（）调用，son()调用时，缓冲区中没有可供消费的产品。若缓冲区没有可供消费的产品则消费者需等待。如图所示：

图 4.2daughter（）调用

4.3调用次数8次
前4次调用：
如图所示：该操作中设置了八次调用。下图是前四次的过程当执行father()操作时，缓冲区中有一个苹果。而执行mother()操作时，缓冲区有一个桔子。只有当缓冲区中有桔子或苹果时，才会有daughter()调用，son()调用，如下图第三次调用，若缓冲区有一个苹果，则daughter()操作自动被调用。

图4.3 father（）调用图

后4次调用：
在本次程序运行过程中，由于第八次是father调用，则该进程中消费者儿子与消费者女儿互斥。生产者放入存储缓冲区（盘子）的产品（苹果），被儿子取走后，另一位生产者才能生产（橘子）供女儿消费。当操作完成后，按任意键退出该程序界面。如图所示：

图4.4 father（）调用

5.源程序
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int apple=0;
int orange=0;
int father_lag=1;
int mother_lag=1;
int son_lag=1;
int daughter_lag=1;
int plat_size=0;
int mf=0;
void print();
void father() //父进程
{
apple++;
print();
}
void mother() //母进程
{
orange++;
print();
}
void son() //儿子进程
{
orange--;
print();
}
void daughter() //女儿进程
{
apple--;
print();
}
void print()
{
printf("There is %d Apple,%d Orange on the plate\n",apple,orange);
if(father_lag==1)
printf("father Process is in wait state\n");
if(mother_lag==1)
printf("mother Process is in wait state\n");
if(son_lag==1)
printf("son Process is in wait state\n");
if(daughter_lag==1)
printf("daughter Process is in wait state\n");
if((father_lag==0)&&(mother_lag==0)&&(son_lag==0)&&(daughter==0))
printf("\n");
}
int main()
{
int k;
int i;
int d;
printf("Please enter the number of calls: \n");
scanf("%d",&d);
srand((unsigned)time(NULL)); //随机产生一个以当前时间开始的随机种子
for(k=0;k<d;k++)
{
printf("━━━━━━━━━━━━━━━━━━━━━\n");
printf("The %d operation: \n",k+1);
i=rand()%4; //随机生成1-5
plat_size=apple+orange;
switch(i)
{
case 0:
printf("father Call.\n");
if(plat_size==1)
{
father_lag=1; //father处于等待状态
print();
if(mother_lag==0)
mf=1; // father与mother互斥信号量决定先后顺序
}
else{
father();
if(daughter_lag==1)
{
daughter_lag=0; //等待取消
printf("Waiting tasks in daughter Automatically called\n");
daughter();
}
}
printf("━━━━━━━━━━━━━━━━━━━━━\n");
break;
case 1:
printf("mother Call.\n");
if(plat_size==1)
{
mother_lag=1; //mother处于等待状态
print();
if(father_lag==0)
mf=2;
}
else{
mother();
// print();
if(son_lag==1) //等待取消
{
son_lag=0;
printf("Waiting tasks in son Automatically called.\n");
son();
}
}
printf("━━━━━━━━━━━━━━━━━━━━━\n");
break;
case 2:
printf("son Call.\n");
if(orange==0)
{
son_lag=1; //son处于等待状态
print();
}
else{
son();
if(mother_lag==1&&father_lag==1)
{
if(mf==1)
{
father_lag=0;
printf("Waiting tasks in father Automatically called\n");
father();
mf=2;
}
else{
mother_lag=0;
printf("Waiting tasks in mother Automatically called\n");
mother();
mf=1;
}
}
else {
if(mother_lag==1)
{
mother_lag=0;
printf("Waiting tasks in mother Automatically called\n");
mother();
mf=0;
}
else if(father_lag==1)
{
father_lag=0;
printf("Waiting tasks in father Automatically called\n");
father();
mf=0;
}
}
}
printf("━━━━━━━━━━━━━━━━━━━━━\n");
break;
case 3:
printf("daughter Call\n");
if(apple==0)
{
daughter_lag=1;
print();
}
else{
daughter();
//print();
if(mother_lag==1&&father_lag==1)
{
if(mf==1)
{
father_lag=0;
printf("Waiting tasks in father Automatically called\n");
father();
mf=2;
}
else{
mother_lag=0;
printf("Waiting tasks in mother Automatically called\n");
mother();
mf=1;
}
}
else {
if(mother_lag==1)
{
mother_lag=0;
printf("Waiting tasks in mother Automatically called\n");
mother();
mf=0;
}
else if(father_lag==1)
{
father_lag=0;
printf("Waiting tasks in father Automatically called\n");
father();
mf=0;
}
}
}
printf("━━━━━━━━━━━━━━━━━━━━━\n");
break;
}
}
}

6.设计总结
在此次操作系统课程设计中,我的题目是：苹果—桔子问题的实现。刚拿到这个任务时就感觉到了一种困难和挑战。不知道从何下手开始设计程序，经过三天的思考，才有了一定的眉目。最后在老师和同学的帮助下，终于得出了一套可行的方案。依照策划的设计思想，又过了六天的编写和测试，终于实现了进程的同步功能，虽然整体还有待提高，但总算实现了基本功能，还算满意。
通过此次课程设计我对操作系统原理有了更进一步的了解，学会应用进程同步及P、V原语，相信会对以后的课程设计有很大的帮助作用。也体会了到同学之间的相互合作帮助可以克服一切困难，尤其是在理论联系实际的过程中。
我的同学在设计过程中为我发现许多错误，也帮助我解决了很多问题，在此我衷心的感谢他们。在以后的学习中我会更加注意各个方面的能力的协调发展，培养自己的动手能力和拓宽自己的知识面，逐渐提高自己的专业技能。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题一个一个的解决了，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。
总的来说这次试验比较成功，加深我对进程的理解，同时也提高了自己编程能力。编程是个长久的过程，平时要多去动手实践，去提高自己的分析问题、发现问题、解决问题的能力。

参考文献
[1]汤子瀛，哲凤屏.《计算机操作系统》.西安电子科技大学学出版社.
[2]王清，李光明.《计算机操作系统》.冶金工业出版社.
[3]孙钟秀等. 操作系统教程. 高等教育出版社
[4]曾明. Linux操作系统应用教程. 陕西科学技术出版社.
[5]张丽芬，刘利雄.《操作系统实验教程》. 清华大学出版社.
[6]孟静， 操作系统教程－－原理和实例分析. 高等教育出版社
[7]周长林，计算机操作系统教程. 高等教育出版社
[8]张尧学，计算机操作系统教程，清华大学出版社
[9]任满杰，操作系统原理实用教程，电子工业出版社
[10]张坤.操作系统实验教程，清华大学出版社

致 谢
首先感谢我的老师和同学们在设计过程中给我提出了许多宝贵的意见和建议，并细心的帮助我解决问题，还在最后的调试程序的过程中帮我找出了一些潜在的错误，没有他们，我也许发现不了这些错误，在此非常感谢他们。在这次课程设计的撰写过程中，我得到了许多人的帮助。 我要感谢我的老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计商的难题。同时也感谢学院为我提供良好的做毕业设计的环境。
总之，通过这次课程设计，我拓宽了知识面，锻炼了能力。尤其是观察、分析和解决问题的实际工作能力、从课堂走向实践。通过操作系统的课程设计，让我们找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识。最后再一次感谢所有在设计中曾经帮助过我的良师益友和同学。