基于信号量的生产者_消费者问题设计与分析_图文

1、第22卷第5期合肥工业大学学报(社会科学版Vo l.22No.5 2008年10月JOU RNAL OF H EFEI U NIVE RSIT Y OF T ECH NOLOGY(Social S ciencesOct.2008基于信号量的生产者 消费者问题设计与分析刘晓平, 石 慧, 凌 实, 杜 琳, 田卫东(合肥工业大学计算机与信息学院,合肥 230009摘 要:生产者 消费者问题是操作系统课程教学中进程同步与互斥的经典问题,深刻理解此问题对理解操作系统中的进程管理具有重要意义。文章应用可视化的方法、基于多线程方式,对生产者 消费者问题进行了模拟,并通过实际测试比较了生产者、消费者之间设

2、置单一互斥信号量与设置两个互斥信号量两种不同方式对程序运行效率的影响。在给学生以直观映像的同时,引导学生对此问题进行深入思考,激发学生的创新意识。关键词:操作系统;生产者 消费者问题;进程同步;可视化;程序设计中图分类号:T P391 文献标志码:A 文章编号:1008 3634(200805 0084 05Design and A nalysis of Producer consumerProblem Based on Semaphore M echanismLIU Xiao ping, SH I H ui, LING Shi, DU Lin, TIAN Wei dong (School o

3、f Com puter Science and Information Engin eering,H efei U nivers ity of T echnology,Hefei230009,Chin aAbstract:Pro ducer consumer problem is a classic example of processes synchronization and mutual ex clusion in teaching of operating sy stem.Deep understanding that is o f great sig nificance for ri

4、ght un der standing of the process manag em ent.In this paper,a m ulti threaded based sim ulation progr am m ing o f this pro blem is presented.Tw o different sem aphore mechanism s:producer and consumer pro cesses w ith shared m utex o r two different mutex es,are compar ed on the impact o f o pera

5、tional effi ciency by actual test.In addition to a visual image to students,it can also g uide students on the prob lem in depth reflection and inspire their aw areness of innovation.Key words:operating system;pr oducer consumer pro blem;process synchro nization;visualization; pro gramm ing操作系统(Oper

6、ating System是高等学校计算机科学与技术专业一门重要的专业基础课程,掌握了操作系统才能领会计算机系统核心软件的本质,才能自如地进行计算机软件开发、能动地推进计算机应用向纵深方向发展。在操作系统课程的教学中,进程管理、内存管理和文件管理1三大部分是主要内容。其中如何有效地使用信号量机制来实现并发进程的同步与互斥是在进程管理教学中面临的主要问题。历来研究进程同步的经典问题有 生产者 消费者问题 哲学家进餐问题和 读者写者问题等。 生产者 消费者问题作为其中较为基础的问题,对理解进程同步互斥具有重要意义,进而有利于学生引申思考和解决其他进程同步问题,因此,本文将以此为研究对象,探讨进程同步

7、问题。收稿日期:2007 09 20基金项目:国家自然科学基金资助项目(60673028作者简介:刘晓平(1964-,男,山东济南人,教授,博士生导师。一、生产者 消费者问题生产者 消费者(Producer Consumer问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程和消费者进程能并发进行,在他们之间设置了一个具有N 个缓冲区的缓冲池,生产者进程可以将其所生产的产品放入一个缓冲区中,消费者进程可以从一个缓冲区中取得产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式进行的,但他们之间必须保持同步,即不允许消费者进

8、程到一个空的缓冲区中去取产品,也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品2。文献2,3中对于此问题的解决是分别通过记录型信号量和AND 信号量来实现进程间的同步与互斥。文献4中采用有限状态机(FSM 和Petri 网的方法描述生产者 消费者问题,并对FSM 和Petri 网进行了比较。文献5提出了在Window s 平台下通过动态链接库(DLL,实现多个生产者与消费者进程共享缓冲区的解决办法,以提高参与通信进程的数据交换速度。文献6则采用Java 语言通过管程机制实现了生产者 消费者问题,使得用户摆脱在操作PV 原语时的复杂性和困难性,为进程同步问题研究提供了另一种有效的

9、方法。以上文献均是对生产者 消费者问题进行原理性验证和定性的有益探讨,对学生理解进程同步与互斥的概念和思想具有一定的推动作用。笔者也在长期的教学工作中结合大量的课堂教学与相应课程设计进行了有益的探索。本文通过可视化设计,实时重现生产者 消费者问题的运行过程,并采用单一信号量与多信号量两种机制的实现对比,定性结合定量的研究方法分析不同信号量设置对程序效率的影响,从而加强学生对进程同步问题的原理和算法的理解,指导学生应用科学的方法分析问题和解决问题;同时通过程序的设计实现,还可以提高学生应用C/C+进行程序设计的能力,激发学生的新思路。二、算法描述1.临界区和w ait(S /sig nal(S

10、操作(1临界区:临界区是指并发进程中与共享变量有关的程序段。(2信号量S :可用临界资源数量,取值只允许为 0 和 1 的信号量称为二元信号量,主要用作互斥变量(m utex;取值允许为整数的信号量称为一般信号量(semaphor e,主要用于进程间的同步问题。(3w ait(S /sig nal(S 操作:最初由Dijkstra 提出的两个原子操作概念2,信号量除初始化外仅能通过这两个标准的原子操作w ait(S 和signal(S 来访问。原子操作在执行时是不可中断的,即当一个进程在修改某信号量时,没有其他进程可同时对该信号量进行修改,以解决进程间同步和互斥的问题。w ait(S 操作:对

11、某资源信号量S 作w ait 操作,表示申请资源,可用资源数S =S 1;如果S 0,表示无资源可用,本进程挂起,变成等待资源S 的 等待 状态。signal(S 操作:对某资源信号量S 作sig nal 操作,表示释放资源,可用资源数S =S +1;如果S !0,表示有进程在等待该资源,则释放该进程,即将等待该资源S 的首进程的状态变为 就绪 状态,去等待CPU 继续运行。2.基于信号量的生产者 消费者问题算法假定在生产者和消费者之间的共用缓冲区中,缓冲区的数量为n ,这时利用互斥信号量mutex 实现诸进程对缓冲区的互斥使用;利用信号量sem aphoreEmpty 和sem aphore

12、Full 分别表示缓冲区中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效,只要缓冲区未满,生产者便可将消息送入缓冲区;只要缓冲区未空,消费者便可从缓冲区中取走一个消息。根据对互斥信号量mutex 的不同设置方式,有两种不同的算法:(1生产者、消费者共用一个互斥信号量mutex ,即生产者进程间、消费者进程间和生产者、消费者85第5期 刘晓平,等:基于信号量的生产者 消费者问题设计与分析进程均互斥,同一时间仅能有一个进程访问缓冲区,两类进程的算法流程如图1 所示。(2生产者、消费者分别设置各自的互斥信号量,即生产者进程间使用producerMutex 进行互斥,消费者进程间使用con

13、sumerMutex 进行互斥,而生产者进程与消费者进程间不互斥。只要有可用资源,两类进程可以同时访问缓冲区,同一时间最多允许两个进程访问缓冲区,两类进程的算法流程如图2所示。需要区别的是,两种算法除了互斥信号量设置方式的不同之外,对缓冲区的结构有着不同的要求。算法1由于同一时间仅能有一个进程访问缓冲区,所以缓冲区只需一个指针p 来记录当前的读写位置即可;算法2同一时间最多允许两个进程访问缓冲区,需要有两个指针ptop 、pbottom 来分别指向生产者、消费者的下一个写入、读取位置。了解对两种不同互斥信号量的设置方式对程序及操作系统造成的影响,能有效地帮助学生深入理解生产者 消费者问题,进而

14、更好地理解进程间同步和互斥的概念及实现方法。为了在教学过程中给学生以更直观的展示,笔者设计和开发了一个生产者 消费者问题的仿真程序,用多线程的方式来模拟多进程的行为,并以可视化的方式实时地将运行过程展示出来。程序界面以方块表示每个线程,并标明属性,以颜色区别生产者和消费者线程,同时动态地绘制每个线程生产和消费的物品数量。程序分别对上述两种算法进行了实现,如图3、图4所示。二者在界面部分的主要区别是缓冲区Buff er 部分,由于两种算法对缓冲区的结构有着不同要求,图3是以堆栈的存取方式来演示只有一个指针标记的方式,而图4 是以类似循环队列的方式来演示两个指针的标记方式。86 合肥工业大学学报(

15、社会科学版 2008年10月三、测试比较1.评价模型和测试用例这里利用Amdahl 7定律评价上述两种算法,Amdahl 定律定义了由于采用特殊的方法所能获得的加速比的大小,即绝对加速比(SpeedupS :其中,为设置一个互斥信号量(算法1时实际生产/消费一定数量的物品所需要的时间;为分别设置两个互斥信号量(算法2时实际生产/消费同样数量的物品所需要的时间。Amdahl 定律适用于负载固定的情况。具体到这两个算法的比较即要尽量保持测试时的参数及运行环境的一致。根据上述对两个算法的描述,对于相同数量的任务量(完全生产和消费完该数量的物品所需要的时间主要受如下参数影响,如表1所示:表1 算法涉及

16、参数因 素参 数缓冲区生产者进程消费者进程可以看到程序的运行时间受到许多参数的影响,为了尽量准确地比较两种算法,现做如下讨论:(1缓冲区的数量需要设置足够大,使程序运行过程中不会出现因缓冲区不足而造成的等待时间,以尽可能排除由于对信号量semaphoreFull 进行的wait 和signal 操作造成的影响;(2生产者总的生产能力(个数*(生产一个产品时间+写入缓冲区时间应与消费者总的消费能力(个数*(消费1个产品时间+读取缓冲区时间相同,使程序运行过程中不会出现过分空闲的状态,以尽可能排除由于对信号量semaphoreEmpty 进行的wait 和signal 操作造成的影响;(3由于实际

17、生产产品和消费产品的操作均在互斥区外进行,对两种互斥变量设置方法造成的影响是相同的,因此这里设生产一个产品时间和消费一个产品时间相等,且为一个定值。因此,这里仅对生产者、消费者不同进程个数(2、4、8和读/写缓冲区时间(0ms 、10ms 、100ms 、1000ms的不同情况进行测试和比较。2.试结果与分析测试环境为:硬件:CPU 采用Intel Pentium 4(3.06GHz软件:操作系统为Window s XP Pro sp2图5-7分别是生产者、消费者线程各2、4、8个时,算法2相对于算法1在生产、消费相同数量物品时不同读/写缓冲区时间的设定条件下得到的加速比。可以看到,在读、写缓

18、冲区时间设置较小,线程数较少时,算法2较算法1的加速效果并不明显,而读、写缓冲区时间较大时(1000ms,稳定于接近两倍的加速。87第5期 刘晓平,等:基于信号量的生产者 消费者问题设计与分析这主要是由于较大的读写缓冲区时间使互斥变量的设置方式对程序运行时间的影响占了主导地位,即算图7 生产者 消费者线程数分别为4时加速比法2对算法1的修改占程序运行时间的比例加大,由Amdahl 定律可知程序的加速比得以体现。这里需要指出的是在读、写缓冲区时间设置为10ms 的情况时,算法2较算法1的效率甚至有所下降,加速比呈现小于1的趋势,该现象本文目前尚不能给出圆满的解答,尚需进一步实例测试并与计算环境相

19、结合进行研究。由上述测试实验可以清楚地看出两种互斥变量的设置方式对程序造成的影响。算法2由于使用两个互斥变量使生产者和消费者之间不互斥,在读/写缓冲区时间较大时,较算法1在执行效率上有较大提升,能得到理想的两倍加速比。四、结束语生产者 消费者问题历来是研究进程同步的典型问题,深刻理解此问题对理解操作系统中进程同步的本质具有重要意义,进而为后期的学习打下坚实的基础。本文以此为对象,作为探讨进程同步问题的切入点。经典教材中的生产者 消费者问题均以单一互斥信号量的方式进行描述,即生产者、消费者共用一个互斥信号量。这样虽然简化了模型,易于学生理解,但就问题本身的约束条件而言,并没有要求生产者与消费者之间要互斥的访问缓冲区。对设置两个互斥信号量与设置单个信号量两种不同方式的比较,对学生进一步理解该问题具有积极作用。合肥工业大学计算机与信息学院可视化与协同计算研究室(VCC,在可视化、仿真技术等方面有着丰富的经验,所以在探讨此问题上,本文采用可视化的方式实时地演示了程序的运行过程,使得学生对原本理论性较强、内容抽象的该问题有了一个直观的理解;通过对设置两个互斥信号量与设置单个信号量两种不同方式的测试对比,运用定性结合定量的分析方法比较不同信号量设置的效率问题,进一步加深了学生对进程同