理解计算机系统_并发编程(8)_线程(五):生产者-消费者问题

前言
       

        以<深入理解计算机系统>(以下称“本书”)内容为基础，对程序的整个过程进行梳理。本书内容对整个计算机系统做了系统性导引,每部分内容都是单独的一门课.学习深度根据自己需要来定

引入

        接续理解计算机系统_并发编程(7)_线程(四):信号量和互斥锁-CSDN博客,前面分析了同步问题的产生,以及一种解决方案:基于信号量的互斥锁.这贴继续看生产者-消费者问题.

概述

        本书P704～P706讲的生产者-消费者问题.站在程序的角度来分析.

        首先,生产者-消费者是一个程序模型.能满足对应的场景.P705第3段讲了几处场景.笔者认为一个能提出程序模型的思路,和写出实现模型的代码的人应该称为it界巨擎("大神").当然对于绝大多数的程序员来说,写不出来也没什么关系,能熟练使用也很不错.

        其次,模型是为了满足需求.程序员怎样理解需求,也是很重要的.那么生产者-消费者对应什么样的需求呢?笔者简单理解:有就用,没有就等.需求来自场景,场景相对直观一些.一个完整程序可以看作多个场景所组成.他们之间的关系简单表达成以下形式:

      /*   由架构师分解程序任务,设立场景,选择对应模型.程序员要写出符合模型的代码.  */

        对于学习者来说,可能前面两点关系不大(既不需要考虑程序架构,也不要求写模型),面对的是如何写代码(当然本书也提供了代码,要是不想学,可以"复制粘贴",但如果是这样想的话,就跳过以下内容从"复制粘贴的改法"看起).这里需要的是对代码的驾驭能力---如何准确表达逻辑.从示例中可以看到熟悉的内容:队列.对应着程序员的基本功---数据结构和算法的理解和使用

生产者-消费者模型理解

        图片来源:本书P705

        

        一边生产数据,一边消费数据,中间建立一个数据缓冲区.本书P705第3段列举了两个使用场景

1>多媒体系统中的编码和解码

         本书原话:例如,在一个多媒体系统中,生产者编码视频帧,而消费者解码并在屏幕上呈现出来.缓冲区的目的是为了减少视频流的抖动,而这种抖动是由各个帧的编码和解码时与数据相关的差异引起的.   

         ---解读:笔者设想过动画的实现(但没有写过贴),通过对数据的理解做一些假设如下:

                a.视频=视频帧的集合(例如1秒视频等于24张(或n张)图片(视频帧))

                b.一个视频帧是一个矩阵图形类对象(见以前的贴)

                c.需要把视频帧写到硬件中(图片所在场景映射到屏幕上)

        其中a,b由生产者实现,c由消费者实现(这些内容不是这里的重点可以忽略).这里应想到的是在生产者那端,有许多线程来完成编码(从生成视频帧到生成视频)的任务.而由于CPU调度的原因,这些视频帧(图片)不是按照顺序一帧帧做好的,而是"无序"状态下完成的.但他们的"结果"是有序的(表现在视频将按照正确顺序播放).这中间起作用的就是"缓冲区".这里的缓冲和网上看视频的时候看见的提示:视频缓冲中,是一个意思.

2>图形用户接口设计中的鼠标和键盘事件

         本书原话:生产者检测到鼠标和键盘事件,并将他们插入到缓冲区中.消费者以某种基于优先级的方式从缓冲区中取出这些事件,并显示在屏幕上.

         ---解读:鼠标和键盘事件是怎样实现的,笔者之前写过一个关于鼠标的类(内容不太成熟),大概分为两部分:一是鼠标(键盘)状态扫描;二是执行被扫描的状态的函数---这个不是关注的重点.只需要明白他不管鼠标还是键盘事件,都是属于线程任务.而"某种基于优先级的方式从缓冲区中取出这些事件"---按照使用习惯,应该是先触发的事件先执行,这点和上面的视频缓冲是相同的(如果有特别要求,比如键盘事件优先于鼠标事件,要求必须先按键盘再点击鼠标才有效另当别论,尽管不太符合使用习惯但也是可以实现的)    

生产者---消费者模型的特点

        综合上述分析,生产者---消费者模型有以下特点:

        一.基于线程.重复强调线程,他不同于非线程中的先来后到的任务

        二.缓冲区的结果是有序的.不管生产者中的线程是怎样执行,但在缓冲区中的数据有先后顺序.

        三.缓冲区是某种数据的集合,数据类型可能是data(图片/数据),也可能是fun(函数/事件),而本书的示例代码用的是int * buff(一个整型的动态数组)

代码设计

        本书P705第4段原话:在本节中,我们将开发一个简单的包,叫做SBUF,用来构造生产者-消费者程序.

         ---解读:在程序构建过程中,经常听到什么什么的"包".内容是一个文件或者包含多个文件的文件夹.从这里可以推导:"包"是为实现某种模型而建立的,模块化的文件.进一步推导:既然包是文件,那么包的内容就是数据类型定义,和函数(笔者用的办法可能比较"土",此处略)

        还有一点,包的内容应该独立,也就是"低耦合".

缓冲区类型定义

        本书P705中间sbuf.h

typedef struct{int *buf;     //第1项int n;        //第2项        int front;    //第3项int rear;     //第4项 sem_t mutex;  //第5项sem_t slots;  //第6项sem_t items;  //第7项
}sbuf_t;

        ---解读:和前面讲过的数据类型定义一样,可以边思考边定义,有冗余属性也无所谓(代码优化时候再考虑).

队列部分

        首先,根据需求分析(先进先出),缓冲区里有一个队列,前4项的数据声明都围绕着队列.

=============================内容分割线↓===================================

回顾数据结构应有的内容:

        数据结构表示某种数据类型对象的集合(类型无关),能满足某种逻辑(如先进先出,后进先出等)

        1>物理结构:数组或链表,包括动态数组

        2>特别位置的指针:一般是首尾

        3>算法:包含增删查        

=============================内容分割线↑===================================

        队列是一个个数为n的整型动态数组(第1,2项),有首尾指针(第3,4项)

信号量部分

        本书P705第2段:更新共享变量,必须保证对缓冲区的访问是互斥的,---第5项是缓冲区互斥锁.

        slots和items信号量分别记录空槽位和可用项目的数量. ---为缓冲区数据进出提供依据.

算法设计

        本书P706有完整代码

         sbuf_init:初始化,把信号量mutex设置为1(互斥锁需要),slots设置为n,items设置为0(对应槽个数n,项目个数0)

         sbuf_insert和sbuf_remove对应缓冲区插入元素和删除元素(一进一出),注意第26行和第37行代码,用的是是循环队列的算法(参考书:浙江大学<数据结构>(第2版)P85).写法上,第1个元素进去后索引是1(不是一般想的0),由于是循环队列所以不影响(在取出数据的算法中把第1个元素定位到索引1).

          另外在第24行往缓冲区里增加元素时,首先用空槽个数做判断,若slots等于0则不能加入,必须等待先执行消费者线程腾出空槽位.与此对应的是第35行,如果已有元素个数items等于0,则不能取出,必须先执行生产者线程往缓冲区里增加元素.---这用到了slots和items信号量.

复制粘贴的改法

        如果弄不懂,只想修修改改能用,笔者讲一讲写法(不保证准确),思路是弄清楚缓冲区的数据是什么,把源码中对应的类型修改即可.以本书P705的两个场景为例:

        1>多媒体系统,把typedef中的int类型改为"Pic"或者"Motions",类型需要自己写.

         2>鼠标键盘事件,把typedef中的int类型改为函数指针.当然鼠标事件函数或键盘事件函数要归于同一函数指针下,比如

void mouseLeft();      //鼠标左键单击
void keyboardPress();  //按下键盘

        这样写可能会有问题,例如按下键盘的函数keyboardPress()显然会有参数来表示按下的是键盘上的哪个键,那么就无法统一函数指针.如果在C++中可以用函数符,再加一个接口来解决.所以只谈谈思路,具体就不展开了.

小结

        虽然本书对于生产者-消费者的篇幅不多,但他是一种经典的程序模型,而且从程序设计的角度,实现代码的角度都有许多地方值得反复思考,所以应得到重视.