第一篇：操作系统课程设计生产者消费者
湖北民族学院信息工程学院11级计算机专业操作系统课程设计
（操作系统课程设计）
生 产 者 和 消 费 湖北民族学院信息工程学院11级计算机专业操作系统课程设计
者
学生姓名： 学生学号： 班 级： 0311401、02、03、04班制
二〇一三年十二月
一、课程题目分析
这个题目是生产者向消费者提供商品，消费者消耗商品，并且两组人共用同一缓冲区。生产者提供了商品之后消费者才能去取商品，消费者若不取走商品则当缓冲区用完之后生产者则不能再向缓冲区中添加新的商品。
思考问题：
（1）对于生产者进程：每产生一个数据，则需去访问共用缓冲区是否有已满，未满则可以将该数据存入并通知消费者进程，否则不能。
（2）对于消费者进程：每当想去消费（取出数据）时，则需访问缓冲区是否为空，为空则不能消费（取出数据），否则可以取，并通知生产者。
（3）缓冲区是个临界资源，所有的进程对于该空间都是共享的，所以，还有互斥问题存在。
二、课程设计目的
通过实验模拟生产者与消费者之间的关系，了解并掌握他们之间的关系及原理。由此增加对进程同步问题的了解：
（1）掌握基本的同步互斥算法，理解生产者与消费者模型
（2）了解windows中多线程（多进程）的并发执行机制，线程（进程）间的同步于互斥
（3）学习使用windows中基本的同步对象，掌握相应的API。
三、课程设计内容
有n个生产者和m个消费者，连接在具有k个单位缓冲区的有界环转缓冲上，湖北民族学院信息工程学院11级计算机专业操作系统课程设计
故又称有界缓冲问题。其中Pi和Cj都是并发进程，只要缓冲区未满，生产者进程Pi所生产的产品就可投入缓冲区；类似地，只要缓冲区非空，消费者进程Cj就可以从缓冲区取走并消耗产品。
四、开发环境
操作系统：Windows系统 编写语言：C++语言
五、系统分析设计
（一）算法原理
生产者——消费者问题是典型的进程同步问题，这些进程必须按照一定的生产率和消费率来访问共享缓冲区，用P、V操作解决生产者和消费者共享单缓冲区的问题，可设置两个信号量empty和full，其初值分别为1和0，empty指示能否向缓冲区放入产品，full指示能否从缓冲区取出产品。为了使其协调工作，必须使用一个信号量mutex（初值为1），以限制生产者和消费者互斥地对缓冲区进行存取，另用两个信号量empty1（初值为缓冲区大小）和full1（初值为0），以保证生产者不向已满的缓冲区中放入产品，消费者不从空缓冲区中取产品。
（二）功能描述
生产者功能描述：在同一个进程地址空间内执行两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。
消费者功能描述：消费者线程从缓冲区获得物品，然后释放缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。
（三）算法流程图
生产者流程图： 消费者流程图：
湖北民族学院信息工程学院11级计算机专业操作系统课程设计
总的流程图：
湖北民族学院信息工程学院11级计算机专业操作系统课程设计
开始Int i=1，n键盘输入数字，初始化 n SeqSquare *b;b=new SeqSquare(n)；键盘输入数字，改变i的值i==0？Y退出Ncout<<“请输入正确的菜单项进行操作!”< (四)数据结构及部分函数描述 （1）类SeqSquare：对类SeqSquare的声明及其中一些函数 class SeqSquare { public: SeqSquare(int n);~SeqSquare();void P(int x);//p操作 void V(int x);//v操作 bool IsEmpty();//判断是否为空 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 bool IsFull();//判断是否已满 void deca();void decb();int getSize();int getmaxSize();int gettop();int geta();int getb();protected: private: };说明：①用动态整型数组*elements来代表缓冲区，不管是生产产品还是对已有产品的消费都需要访问该缓冲区。②函数IsFull（）用于判断缓冲区是否已满，生产者能否使用缓冲区。③函数IsEmpty（）用于判断缓冲区是否为空，消费者能否使用缓冲区。 （2）生产者和消费者操作及显示函数showbuf： void producer(SeqSquare *a)//生产者操作 { } void consumer(SeqSquare *a)//消费者操作 { } //缓冲区显示 void showbuf(SeqSquare *a){ }（3）在实现本程序的生产者消费者模型时，具体地通过以下同步对象实现互斥： int *elements;int top,a,b,maxSize;a->P(1);a->V(1);int i=a->getSize();湖北民族学院信息工程学院11级计算机专业操作系统课程设计 ①设一个互斥量Mutex，以实现生产者在查询和保留缓冲区的下一个空位置时进行互斥。 ②每一个生产者用一个信号量与消费者同步，通过设置Full实现，该组信号量用于表示相应产品以生产。同时用一个表示空缓冲区数目的信号量Empty进行类似的同步，指示缓冲区中是否存在空位置，以便开始生产下一个产品。 （四）调试过程 为解决生产者、消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用Full表示，其初值为用户输入的缓冲区的大小，另一个表示缓冲区中产品的数目，用Empty表示，其初值为0.另外，由于缓冲区是一个临界资源，必须互斥使用，所以还需要再设置一个互斥信号量Mutex，其初值为1.在生产者、消费者问题中，信号量实现两种功能。首先，他是生产产品和消费产品的计数器，计数器的初值是可使用的资源数目（缓冲区的长度）。其次，他是确保产品的生产者和消费者之间的动作同步的同步器。 生产者要生产一个产品时，首先对资源信号量Full和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话，就生产一个产品，并把产品送人缓冲区。然后对互斥信号量Mutex和资源信号量Empty进行V操作，释放资源。 消费者要消费一个产品时，首先对资源信号量Empty和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话就从缓冲区取出一个产品并消费掉。然后对互斥信号量Mutex和资源信号量Full进行V操作，释放资源。 如果缓冲区中已经没有可用资源，就把申请资源的进程添加到等待队列的队尾。如果有一个资源被释放，在等待队列中的第一个进程被唤醒并取得这个资源的使用权。 （五）参考资料 《操作系统教程》 孙钟秀 高等教育出版社 《C++程序设计》 谭浩强 高等教育出版社 六、运行实例及结果分析 （一）运行实例 缓冲区大小为3，先生产一件产品，显示缓冲区，再接着生产一件产品，消耗一件产品，显示缓冲区，在消耗两件产品，再生产4件产品，改变缓冲区的大小为6，显示缓冲区，选择一个未出现的选项，退出程序。 （二）结果显示 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 （三）结果分析 （1）在每个程序中需要先做P，后做V，二者要成对出现，夹在二者中间的代码段就是该进程的临界区。 （2）对同步信号量full和empty的P,V操作同样必须成对出现，但它们分别位于不同的程序中。 （3）无论在生产者进程中还是消费者进程中，两个P操作的次序不能颠倒：应先执行同步信号量的P操作，然后执行互斥信号量的P操作。否则可能造成进程死锁。 七、个人体验 虽然我也很想用java语言写这个程序，但是由于自己学艺不精，所以只能用C++写。通过这个实验我发现我以前有很多知识都忘记了，重新拿起课本学习9 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 时发现原来很多不懂得问题都有了新的认识，有一种豁然开朗的感觉。也为我考研开了一个好的开头。 我认为我完成的这个设计做的比较出色的地方是对C++语言中类以及数组的运用，其实这里我对数组的操作是按照“先进先出”的方法进行运作的，这是参考了栈的工作原理，因为缓冲区一般也是堆栈，比较符合设计要求。 这次实验中我感觉做的很粗糙，自己所想的模拟过程的确得到实现了，但是感觉灵活性不太高，思考还不过全面，应该以后多注意一下，多考虑考虑才是。 在这次实验中我重新将《C++程序设计》和《数据结构》的几个重要章节复习了一遍，对类、数组、C++的I/O流类库以及堆栈的语句格式、注意细节都再一次熟悉，感觉蛮有趣的。不过，在编程过程中许多语句的小问题还真是出现不少，而且感觉自己对C++强大丰富的语句方法用得太呆板，不够灵活，总是想到那些常用的，而忽略了颗粒让语句更简短的方法，以后要多多注意才是。 八、附录 // 生产者消费者1.cpp : Defines the entry point for the console application.// #include “stdafx.h” #include “iostream” using namespace std;class SeqSquare { public: SeqSquare(int n);~SeqSquare();void P(int x); //p操作 void V(int x); //v操作 bool IsEmpty(); //判断是否为空 bool IsFull(); //判断是否已满 void deca();void decb();int getSize();int getmaxSize();int gettop();int geta();int getb();protected: private: int *elements;int top,a,b,maxSize;};10 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 bool SeqSquare::IsEmpty() //判断是否为空 { return(top==-1)?true:false;} bool SeqSquare::IsFull() //判断是否已满 { return(top>=maxSize-1)?true:false;} void SeqSquare::deca(){ a--;} void SeqSquare::decb(){ b--;} int SeqSquare::getSize(){ return top+1;} int SeqSquare::getmaxSize(){ return maxSize;} int SeqSquare::gettop(){ return top;} int SeqSquare::geta(){ return a;} int SeqSquare::getb(){ 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 return b;} SeqSquare::SeqSquare(int n){ top =-1;a = b =0;maxSize = n;elements = new int[maxSize];} void SeqSquare::P(int x){ if(IsFull()==true){ a=a+1;} else { elements[++top] = x; } } void SeqSquare::V(int x){ if(IsEmpty()==true){ b = b+1;} else { x = elements[top--]; } } 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 void producer(SeqSquare *a) //生产者操作 { a->P(1);} void consumer(SeqSquare *a) //消费者操作 { a->V(1);} SeqSquare::~SeqSquare(){ delete elements;} //缓冲区显示 void showbuf(SeqSquare *a){ int i=a->getSize(); } int main(){ int i,n;cout<<“请输入缓冲区大小：”< cout<<“请选择操作： ”< 4.退出系统。 ”< ”< switch(i) { case 1: producer(s); if(s->geta()==0) { 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 cout< } else { cout< s->deca(); } break; case 2: consumer(s); if(s->getb()==0) { cout< } else { cout< } break; case 3: showbuf(s); cout< ”<<“可用空间为：”<<(n-s->getSize())< break; case 4: cout< break; case 5: cout< cin>>n; s = new SeqSquare(n); cout< break; default: cout< } } return 0;} 闽江学院 计算机系 网络操作系统课程设计 设计内容：进程机制与并发程序设计——linux下生产者与消费者的问题实现 目录： 一、设计内容····························3 二、设计思想····························4 三、系统结构····························5 四、PV操作代码··························5 五、C++程序代码·························6 六、运行结果截图························9 七、参考文献····························11 八、实验总结····························11 一、设计内容 进程机制与并发程序设计————linux下生产者与消费者的问题实现 1．实验目的 （1）掌握基本的同步互斥算法，理解生产者和消费者同步的问题模型。（2）了解linux中多线程的并发执行机制，线程间的同步和互斥。 2、实验环境：C/C++语言编译器 3、实验要求 （1）创建生产者和消费者线程 在linux环境下，创建一个控制台进程，在此进程中创建n个线程来模拟生产者或者消费者。这些线程的信息由本程序定义的“测试用例文件”中予以指定。 该文件的格式和含义如下： 3 1 P 3 2 P 4 3 C 4 1 4 P 2 5 C 3 1 2 4 第一行说明程序中设置几个临界区，其余每行分别描述了一个生产者或者消费者线程的信息。每一行的各字段间用Tab键隔开。不管是消费者还是生产者，都有一个对应的线程号，即每一行开始字段那个整数。第二个字段用字母P或者C区分是生产者还是消费者。第三个字段表示在进入相应线程后，在进行生产和消费动作前的休眠时间，以秒计时；这样做的目的是可以通过调整这一列参数，控制开始进行生产和消费动作的时间。如果是代表生产者，则该行只有三个字段。如果代表消费者，则该行后边还有若干字段，代表要求消费的产品所对应的生产者的线程号。所以务必确认这些对应的线程号存在并且该线程代表一个生产者。（2）生产和消费的规则 在按照上述要求创建线程进行相应的读写操作时，还需要符合以下要求： ①共享缓冲区存在空闲空间时，生产者即可使用共享缓冲区。 ②从上边的测试数据文件例子可以看出，某一生产者生产一个产品后，可能不止一个消费者，或者一个消费者多次地请求消费该产品。此时，只有当所有的消费需求都被满足以后，该产品所在的共享缓冲区才可以被释放，并作为空闲空间允许新的生产者使用。 ③每个消费者线程的各个消费需求之间存在先后顺序。例上述测试用例文件包含一行信息“5 C 3 l 2 4”，可知这代表一个消费者线程，该线程请求消费1，2，4号生产者线程生产的产品。而这种消费是有严格顺序的，消费1号线程产品的请求得到满足后才能继续往下请求2号生产者线程的产品。 ④要求在每个线程发出读写操作申请、开始读写操作和结束读写操作时分别显示提示信息。（3）相关基础知识 本实验所使用的生产者和消费者模型具有如下特点： 本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一个空缓冲区中。 消费者只消费指定生产者的产品。 在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。 本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该消费对象是否已经消费完毕并清除该产品。 linux用来实现同步和互斥的实体。在linux中，常见的同步对象有：信号量(Semaphore)、互斥量(Mutex)、临界段(CriticalSection)等。使用这些对象都分为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程中都可以使用，从而实现同步互斥。 二、设计思想 生产者进程与消费者进程是经典的同步互斥关系。系统创建两类进程：proceducer()和consumer()，分别用来描述生产者和消费者的行为。生产者与消费者问题是指若干进程通过循环缓冲池区交换数据。如下图所示，生产者进程不断向循环缓冲池区中写入数据（即生产数据），而消费者进程不断从循环缓冲池区中读出数据（即消费数据）。循环缓冲池共有N个缓冲区，缓冲区可以暂存一个产品，任何时刻只能有一个进程课对循环缓冲池进行操作。所有生产者和消费者要协调工作，以完成数据的交换。只要有空缓冲区，生产者就可以把产品送入缓冲区；只要有满缓冲区，消费者就可以从缓冲区中取走物品。 为了解决生产者和消费者问题，应该设置信号量和变量如下： full： 满缓冲区资源信号量，初值为0； empty：空缓冲区资源信号量，初值为n； in： 生产者指针，初值均为0； out： 消费者指针，均为0； mutex：缓冲区操作的互斥信号量，初值为1 三、系统结构 PCB* readyhead=NULL, * readytail=NULL;// 就绪队列——链表结构 PCB* consumerhead=NULL, * consumertail=NULL;// 消费者队列 PCB* producerhead=NULL, * producertail=NULL;// 生产者队列 processproc()---给PCB分配内存，产生相应的的进程 Pempty()---如果缓冲区满，该进程进入生产者等待队列； linkqueue(exe,&producertail);// 把就绪队列里的进程放入生产者队列的尾部 执行顺序：Main()---empty---in---full---out---finish 当缓冲池为空时，生产者生产产品in缓冲池 in=in+1 当缓冲池为满时，消费者消费产品out缓冲池 out=out+1 四、PV操作代码 semaphore empty=n;semaphore full=0;semaphore mutex=1;message buffer[n];int in=0; int out=0;void main(){ parbegin(proceducer(),consumer());} void proceducer(){ do { prodece a new meddage;P(empty);P(mutex);send a new message to buffer[in];in=(in+1)%n;V(mutex);V(full);} while(true);} void consumer(){ do { P(full);P(mutex);get a message from buffer[out];out=(out+1)%n;V(mutex);V(empty);comsume a message;}while(true);} 五、C++程序代码 #include “windows.h” #include “iostream.h” #include “math.h” #define random(rand()*10000)/RAND_MAX //定义一个随机函数来生产产品，并且使两个顾产品间的时间少于10秒 int long waiting(0);//正在等待的产品的数目 int buffer;//空位的总数目 char empty;//缓冲区空 char full;//缓冲区满 int count(0);//产品的号码数 int finish(0);//生产完毕的产品数目 DWORD a;void proceduce() { Sleep(10000);cout<<“缓冲区已空!”< } void getconsum(){ Sleep(10001);//产品被生产的函数，为了合理区分生产产品 cout<<“第”< HANDLE Mutex=CreateMutex(NULL, FALSE, “Mutex”);//用来实现进程的互斥 HANDLE proceducer=CreateSemaphore(NULL, 1,1, “proceducer”);//定义信号量来进行线程间的同步 HANDLE consumer=CreateSemaphore(NULL,0,3,“consum”);DWORD WINAPI consum(LPVOID pParm2)//消费的线程 { WaitForSingleObject(Mutex ,INFINITE);//p(mutex)来进行互斥操作 count++;//生产的是第几个产品 cout<<“第 ”< { if(waiting!=0){ cout<<“此时有”< else cout<<“没有产品在等待”< ReleaseMutex(Mutex);//释放互斥量，以便其他线程使用 WaitForSingleObject(proceducer,INFINITE);//等待生产 getconsum();//消费并取走 } else { cout<<“缓冲区已满，第”< return 0;} DWORD WINAPI proceducers(LPVOID pParm1)//生产者的线程 { while(true)//一直执行 { WaitForSingleObject(consum,INFINITE);//p(customers)，等待产品 WaitForSingleObject(Mutex,INFINITE);//等待互斥量 waiting--;//等待的产品数减一 ReleaseSemaphore(proceducer,1,NULL);//释放信号量 ResumeThread(proceducer);//唤醒消费进程 ReleaseMutex(Mutex);//v(mutex);proceduce();//生产 finish++;//消费的产品数加1 } return 0;} int main(int argc, char* argv[]){ cout<<“请输入缓冲区空位的总数目:”;cin>>buffer;cout<<“缓冲区共有”< cout< HANDLE hThread1;HANDLE hThread2;hThread2=::CreateThread(NULL,0,proceducers,NULL,0,NULL);//产生一个生产者进程 while(full!='y'){ Sleep(random);//产品随机进入 hThread1=::CreateThread(NULL,0,consum,NULL,a,NULL);cout< { cout<<“已经为”< else;} if(full=='y'){ cout<<“********对不起，缓冲区已满********”< } 六、运行结果截图 缓冲区空位总数目为1时运行结果截图： 缓冲区空位总数目为0和3时运行结果截图（其余部分如上当缓冲区空位总数目为1时的截图） 七、参考文献 1、计算机网络操作系统原理与应用 孔宪军 吕滨（本学期教科书） 2、网络操作系统课程设计计划书 陈卫老师 3、C程序设计（第三版）谭浩强 八、实验总结 刚刚看到课程设计的内容与要求时，不禁有点无从下手的感觉。经过一番思考后，才决定选择设计“进程机制与并发程序设计——linux下生产者与消费者的问题实现”这部分。设计这部分不仅仅需要用到C/C++编程，还需要编写相关的PV原语。由于自己的PV原语部分和C/C++编程学的不是很好，因此对我来说有点难。于是我就积极利用书本上的知识来编写PV原语，C/C++编程是参考书上的指点以及网络资源编写出来的。不懂得地方查资料、上网找、问问其他同学，最后终于慢慢的把课程设计做出来了。通过这次课程设计，才感觉到自己还是平时动手少，要经常动手去做实验才能真正学到东西。尤其是一些C/C++编程和PV原语的编写更需要平时多加练习才能学好用好。特别是C/C++编程在遇到语法有多处错误时，不能急，要冷静下来慢慢修改，知道程序正确。虽然是自己独立做的课程设计，但是其中还是有很多不懂的东西是问同学的，因此了解到学习不是单独的，应该是相互交流相互学习的。 实 验 二 经 典 的 生 产 者 — 消 费 者 问 题 一、目的 实现对经典的生产者—消费者问题的模拟，以便更好的理解经典进程同步问题。 二、实验内容及要求 编制生产者—消费者算法，模拟一个生产者、一个消费者，共享一个缓冲池的情形。 1、实现对经典的生产者—消费者问题的模拟，以便更好的理解此经典进程同步问题。生产者－ 消费者问题是典型的 PV 操作问题，假设系统中有一个比较大的缓冲池，生产者的任务是只要缓冲池未满就可以将生产出的产品放入其中，而消费者的任务是只要缓冲池未空就可以从缓冲池中拿走产 品。缓冲池被占用时，任何进程都不能访问。 2、每一个生产者都要把自己生产的产品放入缓冲池，每个消费者从缓冲池中取走产品消费。在这种情况下，生产者消费者进程同步，因为只有通过互通消息才知道是否能存入产品或者取走产品。他们之间也存在互斥，即生产者消费者必须互斥访问缓冲池，即不能有两个以上的进程同时进行。 三、生产者和消费者原理分析 在同一个进程地址空间内执行两个线程。 生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。 消费者线程从缓冲区中获得物品，然后释放缓冲区。 当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放一个空缓冲区。 当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻挡，直到新的物品被生产出来。 四、生产者与消费者功能描述： 生产者功能描述：在同一个进程地址空间内执行两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。 消费者功能描述：消费者线程从缓冲区获得物品，然后释放缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。 五、实验环境 操作系统环境： Windows 系统。编程语言： C#。 六、生产者与消费者的思路和设计 1、程序流程图 (1)生产者 开 始 生产产品 Wait empty ≤ 0 Y N Wait 缓冲区内已满，已无 可用缓冲区 N Mutex=1 Y 缓冲区正被其他 程占用 进 存入缓冲区 empty = empty-1 Signal Signal(full)结 束 (2)消费者 开 始 Wait(full)消费请求 full ≤ 0 Y N Wait 缓冲区内产品已空，不能进行消费 N Mutex=1 Y 消 费 缓冲区正被其他 程占用 进 full = full-1 Signal Signal 结 束 2、主要程序代码 // 初始化变量 private void Form1_Load(object sender, EventArgs e){ mutex = 1;// 互斥信号量 full = 0;// 缓冲池中满缓冲区的数量 empty = 5;// 缓冲池中空缓冲区的数量 count1 = 0;// 生产的产品数目 i = 0;= “1”;= “0”;= “5”;} // 消费者从缓冲区中消费一个产品 private void consumer_Click(object sender, EventArgs e){ if(full > 0){ // 消费者已进入互斥临界区 if(mutex == 1)// 申请进入临界区 { mutex = 0;// 消费者已进入互斥临界区 = “0”;= true;// 启动消费者消费缓冲区产品 } else {(“ 缓冲区被占用，请等待。。 ”, “ 信息提 ”;} } else {(“ 缓冲区为空，不能消费!”, “ 信息提示 ”,;} } // 生产者向缓冲区中存入一个产品 private void producer_Click(object sender, EventArgs e){ count1 = count1 + if(empty > 0){ 1; // // 生产一个产品 有缓冲区可放产品 if(mutex == 1){ // 申请进入临界区 mutex = 0; // 生产者已进入临界区 = “0”; ();// 启动生产者将产品放入缓冲区 } else { // 不能进入临界区 count1 = count1-1;(“ 缓冲区被占用，请等待。。 ”, “ 信息提示 ”,;} } else {(“ 缓冲区已满!”, “ 信息提示 ”,;// 无缓冲区可放产品 count1 = count1-1;} } // 生产者 private void timer1_Tick_1(object sender, EventArgs e){ if(bool1){ switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} = “ 生产者进程占用缓冲区，请等待。。 ”;bool1 = false;} else { switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} = “ 生产者进程占用缓冲区，请等待。。 ”;bool1 = true;} i = i + 1;if(i == 5) { // 循环缓冲区，首尾相接 i = 0;= false;mutex = 1;= “1”;switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} full = full + 1;=();empty = empty-1;=();= “ 生产结束!”;} } // 消费者 private void timer_consumer_Tick(object sender, EventArgs e){ if(bool1){ switch(count1){ case 1: = true;break;case 2: = true;break;case 3: = true;break;case 4: = true;break;case 5: = true;break;} = “ 消费者进程占用缓冲区，请等待。。 ”;bool1 =false;} else{ switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} = “ 消费者进程占用缓冲区，请等待。。 ”;bool1= true;} i = i + 1;if(i==5){ i = 0;= false;mutex = 1;= “1”;switch(count1){ case 1: = false;break;case 2: = false;break;case 3: = false;break;case 4: = false;break;case 5: = false;break;} count1 = count1-1;full = full-1;=();empty = empty+1;=();=“ 消费结束！ ”;} 3、运行界面和运行结果 一般情况下，点一次生产者按纽，mutex 由 1 变为 0，缓冲区呈现闪烁状态（表示正在存储），此时不可以再进行缓冲区操作，否则将显示“生产者进程正在占用缓冲区，请等待”。闪烁约秒后，mutex 由 0 变为 1，闪烁停止，表示存储过程结束；点一次消费者按纽，mutex 由 1 变为 0，缓冲区呈现闪烁状态（表示正在消费），此时不可以再进行缓冲区操作，否则将显示“消费者进程正在占用缓 冲区，请等待”。闪烁约秒后，mutex 由 0 变为 1，闪烁停止，表示消费过程结束。缓冲池满后，若再点生产者按纽，会给出信息提示： “缓冲区已满!”。 缓冲池空后，若再点消费者按纽，也会给出信息提示： “缓冲区为空，不能消费!”。 在存储状态或消费状态（闪烁状态），无论是点生产者按纽还是消费者按纽都会给出“缓冲区被占用，请等待。”信息提示。 七、心得体会 本次实验是关于生产者与消费者之间互斥和同步的问题。问题的是指是 P、V 操作，实验设一个共享缓冲区，生产者和消费者互斥的使用，当一个线程使用缓冲区的时候，另一个让其等待直到前一 个线程释放缓冲区为止。 生产者与消费者是一个与现实有关的经验问题，通过此原理举一反三可以解决其他类似的问题。 通过本实验设计，我们对操作系统的 P、V 进一步的认识，深入的了解 P、V 操作的实质和其重 要性。课本的理论知识进一步阐述了现实中的实际问题。 实验中，我们小组分工合作，共同学习，虽然在实验中遇到了一些问题，但在老师和同学的细心指导和热心帮助下解决了。同时，了解到团队精神的重要性，也为以后的学习和工作打下了坚实的基础，同时积累了宝贵的经验。 临界区管理实现 本组组员：周琪皓，董泉伟，钟佳锋，张倬慎 0 引言 随着多处理机体系结构的演变和分布式与并行系统的发展，并发多任务的程序设计技术已愈来愈显得重要，多线程设计模式在这些技术的发展中起着重要作用。在现代操作系统中，利用进(线)程间的并发性实现程序中并发成分的并行执行，可大大提高系统的处理能力和效率，但也可能带来诸如执行结果的不确定性等不良现象，因此并发系统中处理好进(线)程间的互斥与同步就显得至关重要。C++语言中的多线程机制是解决线程间的互斥与同步问题的重要工具，其应用(如网络多媒体应用、工业自动化控制等)很广泛，很复杂且常易出错。因此在应用程序设计过程中，要考虑多个线程如何同步使用进程的共享资源，如何让一个线程与另一个线程协调合作，以免产生线程间的访问冲突。语言提供的多线程机制能有避免同一共享互斥资源被多个线程同时访问，维护数据的一致性、安全性。生产者/消费者问题可作为并发进程的同步和互斥问题的一个抽象模型，广泛应用于通信和控制系统中。本文基于C++语言中的多线程机制，实现操作系统中生产者/消费者问题，以助人们更好地透解同步概念及其实现方法。1 课程设计目的 通过模拟操作者生产者经典问题的实现，以及关于信号量和互斥锁对于多线程的运用，深入理解操作系统中多线程同步法的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法,更好地掌握操作系统的原理及实现方法,提高综合运用各专业课知识的能力。2 课程设计题目和要求 2.1 课程设计题目 题目: 临界区管理实现.2.2课程设计目的与要求 初始条件： 1.操作系统：Windows 2.程序设计语言：C++语言 3.有界缓冲区内设有20个存储单元，其初值为0。放入／取出的数据项按增序设定为1－20这20个整型数。 技术要求： 1、生产者和消费者各有两个以上。多个生产者或 多个消费者之间须有共享对缓冲区进行操作 的函数代码。每个生产者和消费者对有界缓冲 区进行操作后，即时显示有界缓冲区的全部内 容，当前指针位置。 2、编写多线程同步方法解决生产者-消费者的程 序，并完成对进程进行模拟同步和互斥的控制。2 设计总体思路 2.1 多线程编程思想 编写Windows下的多线程程序，需要使用头文件pthread.h以及windows.h.在LINUX下进行多线程编程首先要用到CreateThread()这个函数.函数CreateThread()用来创建一个线程，它的原型为： HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes, // pointer to security attributes DWORD dwStackSize, // initial thread stack size LPTHREAD_START_ROUTINE lpStartAddress, // pointer to thread function LPVOID lpParameter, // argument for new thread DWORD dwCreationFlags, // creation flags LPDWORD lpThreadId);// pointer to receive thread ID 第一个参数是指向SECURITY_ATTRIBUTES型态的结构的指针。在Windows 98中忽略该参数。在Windows NT中，它被设为NULL。第二个参数是用于新线程的初始堆栈大小，默认值为0。在任何情况下，Windows根据需要动态延长堆栈的大小。第三个参数是指向线程函数的指标。函数名称没有限制，但是必须以下列形式声明： DWORD WINAPI ThreadProc(PVOID pParam);第四个参数为传递给ThreadProc的参数。这样主线程和从属线程就可以共享数据。第五个参数通常为0，但当建立的线程不马上执行时为旗标CREATE_SUSPENDED。线程将暂停直到呼叫ResumeThread来恢复线程的执行为止。第六个参数是一个指标，指向接受执行绪ID值的变量。2.1.1线程数据 在单线程的程序里，有两种基本的数据：全局变量和局部变量。但在多线程程序里，还有第三种数据类型：线程数据。它和全局变量很象，在线程内部，各个函数可以象使用全局变量一样调用它，但它对线程外部的其它线程是不可见的。这种数据的必要性是显而易见的。例如我们常见的变量errno，它返回标准的出错信息。它显然不能是一个局部变量，几乎每个函数都应该可以调用它；但它又不能是一个全局变量，否则在A线程里输出的很可能是B线程的出错信息。ThreadHandle[0]=CreateThread(NULL,0,Producer,NULL,0,&producer1)其六个参数分别表示为安全设置，堆栈大小，入口函数，函数参数，启动选项，输出线程 ID，返回线程句柄。2.1.2 互斥锁 互斥锁用来保证一段时间内只有一个线程在执行一段代码，必要性显而易见：假设各个线程向同一个文件顺序写入数据，最后得到的结果一定是灾难性的.函数mutex = CreateMutex(NULL,FALSE,NULL);用来生成一个互斥锁.NULL参数表明使用默认属性.如果需要声明特定属性的互斥锁，须调用函数 CreateMutex(NULL,FALSE,NULL) WaitForSingleObject(mutex,INFINITE)声明开始用互斥锁上锁，直至调用ReleaseMutex(mutex)为止，均被上锁，即同一时间只能被一个线程调用执行.当一个线程执行到pthread_mutex_lock处时，如果该锁此时被另一个线程使用，那么此线程被阻塞，即程序将等待到另一个线程释放此互斥锁.2.1.3 信号量 信号量本质上是一个非负的整数计数器，它被用来控制对公共资源的访问。当公共资源增加时，调用函数aitForSingleObject(empty,INFINITE)增加信号量。只有当信号量值大于０时，才能使用公共资源，使用后，函数WaitForSingleObject(full,INFINITE)减少信号量。 函数 ReleaseSemaphore(full,1,NULL)用来增加信号量的值。当有线程阻塞在这个信号量上时，调用这个函数会使其中的一个线程不在阻塞，选择机制同样是由线程的调度策略决定的。函数ReleaseSemaphor()用来释放信号量。2.2 设计原理 生产者线程和消费者线程共享同一个缓冲队列，生产者线程向缓冲区中写数据，消费者线程从缓冲区中取数据。但两者必须在使用缓冲队列资源时保持互斥，否则可能会导致在写入时产生数据覆盖，在读出时得到错误数据。因而要在程序中设置一个互斥锁或公用信号量，用于保证线程间的互斥执行。同时生产者线程和消费者线程必须保持同步关系，因为生产者线程的执行为消费者线程提供了需要的数据，是其执行的前提。反之，消费者线程的执行为生产者线程腾出了空闲的缓冲单元，为写数据提供了条件。即消费者线程执行的前提：缓冲队列中至少有一个单元有数据；生产者线程执行的前提：缓冲队列中至少有一个单元是空的。在设计过程中，利用信号量和wait、signal原语操作来实现。如图1所示： 图1 生产者、消费者共享有界缓冲区 2.3 原语操作实现 The structure of the producer process do { // 生产产品 wait(empty);wait(mutex);// 往Buffer中放入产品 signal(mutex);signal(full);} while(true);The structure of the consumer process do { wait(full);wait(mutex);// 从Buffer中取出产品 signal(mutex);signal(empty);// 消费产品 } while(true);3 开发环境与工具 系统平台：Windows环境 实现语言：C++语言 开发工具：Vs2012 4 概要设计 4.1 数据结构设计 通过分析课程设计要求，具体设计出如下数据结构: 1.int buffer[20]={0};//定义缓冲区空间大小 2.包含数据结构pthread_t 它记录一个线程的号，主要包括下面几个函数，完成不同的功能： ThreadHandle[0]=CreateThread(NULL,0,Producer,NULL,0,&producer1);//创建一个线程。ExitThread(0);CloseHandle(ThreadHandle[0]);//等待一个线程结束。4.2 程序模块实现 4.2.1 生产者（Producer）模块 生产者线程向一缓冲区中写入数据，且写入缓冲区的数目不能超过缓冲区容量。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权，其流程图如图2所示： 生产一条数据No是否可用存储单元等待资源，阻塞Yes被唤醒No是否可用Yes存入一条数据等待使用权，阻塞被唤醒归还使用权数据单元加1，唤醒消费者 图生产者流程图 //生产者线程 DWORD WINAPI Producer(LPVOID lpPara){ do{ WaitForSingleObject(empty,INFINITE);冲区减1 WaitForSingleObject(mutex,INFINITE);上锁 //空缓//信号量 buffer[in]=in+1;//往Buffer中放入产品 in=(in+1)%BUFFER_SIZE;//放入指针调整，为下次送出做准备 printAll();ReleaseMutex(mutex);//信号量解锁 ReleaseSemaphore(full,1,NULL);//满缓冲区加1，即当公共资源增加时，调用函数ReleaseSemaphore（）增加信号量 }while(1);} 4.2.2 消费者(Consumer)模块 消费者线程从缓冲区中读取数据，且消费者读取的数目不能超过生产者写入的数目。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图3所示： No是否可用存储单元等待资源，阻塞Yes被唤醒是否可用No等待使用权，阻塞Yes被唤醒取出一条数据归还使用权空缓冲区加1，唤醒一个生产者消费数据 图3 消费者流程图 //消费者线程 DWORD WINAPI Consumer(LPVOID lpPara){ do{ WaitForSingleObject(full,INFINITE);区减1 WaitForSingleObject(mutex,INFINITE);量上锁 //满缓冲 //信号 buffer[out]=0;//从Buffer中取出产品 out=(out+1)%BUFFER_SIZE;//取指针调整，为下次取做准备 printAll();ReleaseMutex(mutex);//信号量解锁 ReleaseSemaphore(empty,1,NULL);//空缓冲区加1 }while(1);} 5 详细设计 5.1 源程序代码 #include #include 进入Windows开发环境后，通过Vs2012编辑器在其中编写。进入Vs2012的命令，对程序执行编译运行命令后，即可在屏幕上显示出程序运行的结果，其运行结果如下图5所示： 总结 其实在做这道题目时花费了好长时间，第一点是书上大多介绍的是关于UNIX系统下的消费者生产者线程问题，因此一开始调试不出来，后来查阅了有一些资料知道要在windows平台下运行必须要导入 以及 操作系统课程设计 注意事项： 0.请每位同学必须按时提交课程设计报告（包括电子版和纸质版），算入期末成绩 1.在三个题目中选择一个 2.如果选择题目 （一）进程调度算法，要求实现其中2个以上（包括2个）进程调度算法 3.如果选择题目 （二）银行家算法，要求能够判断系统的安全状态 4.如果选择题目 （三）页面调度算法，要求实现其中2个以上（包含2个）进程调度算法 5.报告应包含算法分析、实验截图、核心算法源代码，请各位同学认真对待，独立完成 6.提交要求：电子版（包括实验程序）请发至ropeal@163.com，纸质版请班长收齐，由班长统一在课堂上提交（并提交未交人员名单），截止时间第16周周三(2014.1.31)7.格式要求： 7.1 A4纸10页左右 7.2 封面请注明班级、姓名、学号、所选题目 7.3 电子版发送时，请打包成一个文件，将文件名设置为：学号+姓名+题目名称（如20130000张三进程调度算法课程设计），邮件主题同文件名 一、进程调度算法 1.1 实验目的： a、设计进程控制块PCB表结构，模拟实现进程调度算法：FIFO，静态优先级调度，时间片轮转调度，多级反馈队列调度。（实现其中之二）。* b、建立进程就绪队列。对不同算法编制入链子程序。c、编写一进程调度程序模拟程序。模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。* 由用户输入进程名和进程长度，然后按照短进程优先的进程处理顺序给出进程的排序。 1.2 实验原理 调度算法是指：根据系统的资源分配策略所规定的资源分配算法。1.2.1 先来先服务和短作业（进程）优先调度算法 1.先来先服务调度算法。先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业，而不利于I/O繁忙型的作业（进程）。 2.短作业（进程）优先调度算法。短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度，也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。1.2.2 高优先权优先调度算法 1.优先权调度算法的类型。为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度，将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时，又可以进一步把该算法分成以下两种： 1)非抢占式优先权算法 2)抢占式优先权调度算法（高性能计算机操作系统） 2.优先权类型。对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权，以及如何确定进程的优先权。3．高响应比优先调度算法 为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间 1.2.3 基于时间片的轮转调度算法 1.时间片轮转法。时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。2.多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。其实施过程如下： 1)设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中，为每个进程所规定的执行时间片就越小。 2)当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度„„ 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。3)仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1到第（i-1）队列空时，才会调度第i队列中的进程运行，并执行相应的时间片轮转。4)如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列，则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。 1．3 实验要求 a、使用模块化设计思想来设计； b、给出算法的流程图或伪码说明。c、学生可按照自身条件，随意选择采用的算法，（例如：采用冒泡法编写程序，实现短进程优先调度的算法） d、进程调度程序模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。 1.4 算法简析 a、每个进程可有三个状态，并假设初始状态为就绪状态。b、为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。c、在优先数算法中，优先数可以先取值为（50-该进程所需时间），进程每执行一次，优先数减3，CPU时间片数（CPUtime）加1，* 进程还需要的时间片数（needtime）减1。在时间片轮转算法中，采用固定时间片 （即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片（CPUtime）数加2，* 进程还需要的时间片数（needtime）减2，并排列到就绪队列的尾上。 d、对于遇到优先数一致的情况，采用FIFO策略解决。 二、银行家算法 2.1 概述 2.1.1 设计目的1、了解多道程序系统中，多个进程并发执行的资源分配。 2、掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。 3、掌握预防死锁的方法，系统安全状态的基本概念。 4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。 5、理解死锁避免在当前计算机系统不常使用的原因 2.2 关于死锁 2.2.1 死锁概念： 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 2.2.2 关于死锁的一些结论： 参与死锁的进程最少是两个（两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 2.2.3 资源分类： 永久性资源： 可以被多个进程多次使用（可再用资源），分为：可抢占资源与不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式 2.2.4 产生死锁的四个必要条件： 1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 4、循环等待 存在一个进程等待队列 {P1 , P2 , „ , Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，„，Pn等待P1占有的资源，形成一个进程等待环路 2.2.5 死锁的解决方案 1 产生死锁的例子 申请不同类型资源产生死锁 P1： „ 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 „ P2： „ 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 „ 申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程P1,P2,„,Pn（n > m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生 2死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 ①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 ②破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 ③破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 2.2.6 安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，„Pn，则系统处于安全状态。一个进程序列{P1，„，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量之和，系统处于安全状态(安全状态一定是没有死锁发生的)。 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。 2.3 数据结构设计 1.可利用资源向量矩阵AVAILABLE。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果AVAILABLE [j]= K，则表示系统中现有R类资源K个 2.最大需求矩阵MAX。这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果MAX [i,j]=K，则表示进程i需要R类资源的数目为K。 3.分配矩阵ALLOCATION。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATION [i,j]=K，则表示进程i当前已分得R类资源的数目为K。 4.需求矩阵NEED。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果NEED [i,j]=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系： NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j] 2.4 算法的实现 2.4.1 初始化 由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。2.4.2 银行家算法 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 2.4.3 安全性检查算法 (1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。 三、页面调度算法 3.1 实验名称 页式虚拟存储管理：页面调度算法 3.2 实验目的 页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。3.3 实验原理 页面调度算法 目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。 下面对各调度算法的思想作一介绍。 <1> 先进先出调度算法 先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。 <2>最近最少调度算法 先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。 <3>最近最不常用调度算法 由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。 缺页调度次数和缺页中断率、缺页置换率计算 缺页中断次数是缺页时发出缺页中断的次数。 缺页中断率=缺页中断次数/总的页面引用次数*100% 缺页调度次数是调入新页时需要进行页面调度的次数 缺页置换率=缺页调度次数/总的页面引用次数*100% 3.4 实验内容 （1）设计程序实现以上三种页面调度算法，要求： ①.可以选择页面调度算法类型； ②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，可以从键盘输入页面序列，也可从文件中读取； ③.随时计算当前的页面调度次数的缺页中断率； ④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝； ⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上； ⑥.存盘及读盘功能，可以随时将数据存入磁盘文件，供以后重复实验时使用。 （2）假定进程分配到3个物理块，对于下面的页面引用序列：（test.txt） 7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1 请分别用先进和先出调度算法，最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。 再假定进程分配到4、5个物理块，重复本实验。 （3）假定进程分配到3个物理块，对于下面的页面引用序列：（test2.txt） 4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9 请分别用先进先出调度算法、最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。 再假定进程分配到4、5个物理块，重复本实验。 （4）假定进程分配到3个物理块，使用程序的动态页面序列生成算法，生成一个页面序列，将此序列存入磁盘文件。再从磁盘文件读入该序列，用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。第二篇：生产者与消费者的问题-----操作系统课程设计
第三篇：操作系统实验报告经典生产者—消费者问题
第四篇：操作系统课程设计__用多线程同步方法解决生产者
第五篇：操作系统课程设计
点击咨询 