【说在前面的话】有人说世间问题再多无非就是时间和空间的问题。每每看到这类说法都不禁会让我想起小时候看的《天龙八部》中的一处情节彼时彼刻少林寺正在被江湖歹人围攻方丈情急之下问虚竹外面有多少人虚竹傻不啦叽的说好多人呢作为装逼界的老把式方丈故作高深的说错只有两个人名和利。原本这一教科书式的逼我可以给90分无奈后面分分钟打脸的情节破坏了逼格的美感——虚竹听信了方丈的“教诲”正若有所思时方丈也在为这个逼装得恰如其分而沾沾自喜但突然意识到刀已经架到自己脖子上了于是立马回到现实中让虚竹再去看看外面有多少人虚竹记下了方丈的教诲当然说只有两个人。这可把方丈开心死了高喊这下少林寺有救了谁料自己推门一看这啪啪啪的立即就被打了脸。每次想到这个情节我都忍俊不禁。时过境迁突然轮到自己要说其实计算机科学中只有两个问题——时间和空间的问题——不由得担心起来生怕打在老和尚脸上的巴掌已经等着我了。然而事实告诉我这并不是故弄玄虚为了证明这一点在未来的很长时间内我将会用一系列的文章来介绍嵌入式系统设计中、乃至是计算机科学中常见的“时间和空间”问题的实例。今天我们就从简单的流Stream和块Block的使用哲学说起。【串行的“流”和随机的“块”】虽然不是Linux提出的概念但流Stream和块Block处理的深入人心绝对离不开流文件和块文件的功劳。然而流和块其实是更为通用的概念它们分别代表了数据处理中 “以时间换空间” 和 “以空间换时间” 的两种截然不同的偏重策略。1、以空间换时间的块处理说到块处理其最显著的特征就是将所要处理的数据用一段连续的存储器保存下来我们可以随机的以任意的顺序和方式对这些数据进行访问和处理——简单说就是牺牲一定的存储器空间换取了数据访问的便利性降低了访问和处理的时间成本——因此我们可以说块处理是一个典型的用存储器空间换取处理时间的策略。举例来说假设我们需要从一段文字中中处理其中某几个单词我们可以先简单的将整段文字连续的保存在RAM中然后使用基于块的字符串处理函数对其进行操作。由于访问方式简单直接随机访问因此字符串处理的效率主要由处理的算法决定字符串访问的顺序和次数并不存在限制。这里我我需要特别指出块处理中字符串处理效率的瓶颈是由算法本身决定的与之相比数据访问的成本是固定的随机访问。块处理的优势体现在当我们以任意顺序访问块中的任意数据时这里的访问成本是最低的。块处理往往可以理解为批量的处理是效率的代名词流处理中字符串处理效率的瓶颈往往受限于“从串行的流中获取一个数据的时间成本”——甚至比较来说有时处理数据的时间小到可以忽略的程度。常见的情形是算法处理好当前字符后喝了茶、打了个瞌睡再一看——“下一个字符还没有就绪”。又或者处理器处理一个字符所消耗的时间远没有从流中读取下一个字符来得长。实际应用中这两种情形往往是结合在一起的——当某个任务“焦急”的从串口缓冲区中尝试读取下一个字符以便进行数据帧解析时队列操作的时间、等待字符接收完成的时间通常比单独一个字符的处理时间高出好几个数量级。说了那么多废话让我们来做一个小结块Block处理就是消耗存储器空间将目标数据都存储下来方便数据处理算法以任意有利的方式随机的对其进行访问从而提升整体吞吐量节省时间的一种数据处理方式。这是一个以存储器空间换取访问时间的策略。块的表现形式是一段可随机访问的存储器空间。“可随机访问”是其本质而并不要求数据在空间上是连续的。比如你可以把很多空间上离散的数据块用某种哈希算法联系起来。2、以时间换空间的流处理流处理最显著的特点就是数据的出现在时间轴上存在单向性——也就是我们常说的串行性。数据的处理方一次只能接收或者处理一个数据单元。流处理最大的限制是数据访问顺序的限制——所有的数据单元必须按照流发送方提供的顺序进行访问。正是由于这种访问顺序的限制让流的处理方常常觉得“谁用谁知道”的别扭。——很多时候为了数据访问的方便会将一部分流先缓冲成小的数据块再以块的方式进行处理——典型的例子就是串行数据通信中常见的数据帧Frame。如果不是因为贫穷谁会愿意在时间轴上限制自己的访问自由呢如果贫穷是逃避不了的宿命比如带宽限制、存储器大小限制等等……那么我们不妨换一个角度来看——通过对数据访问的顺序进行限制我们可以节省大量的资源比如带宽、缓存……因此我们可以这么说流处理的好处也是显而易见的由于不需要大块的存储器空间用于数据的暂存因而在小资源的处理器尤其是小SRAM的MCU中尤其流行。代价是受制于访问顺序流处理的算法往往较为复杂有些功能甚至是无法实现的单凭流处理本身无法实现需要局部应用快处理同时流处理的数据存取时间造成的浪费也非常可观。人常说流处理的本质就是零库存的手工作坊一切都得按步就班的来提高流处理效率的方法就是把数据传输所需的等待时间以流水线的方式利用起来。小结一下流Stream处理是以消耗更多处理器时间并增加访问顺序的限制的方法节省存储器空间的一种处理方式。这是一个以时间换空间的策略。【流块互转】流和块各有各的优势各有各的缺点那么在嵌入式系统中是否可以把它们的特点结合起来根据应用场景的不同只凸显优势而隐藏或者弱化缺点呢在常见的嵌入式系统数据流中每一个数据处理环节简称数据处理Process对时间和空间的偏好是不同的。注意到以下一些事实这里的数据流可能包含多个分工不同的子系统处理器甚至包含远端的服务器系统有的Process对性能时间敏感并拥有宽裕的RAM显然应该利用块处理“以空间换时间”的特性将RAM富余的优势更多的转化为性能优势有的Process对空间敏感往往是成本敏感导致的对性能则要求不高比如UART9600甚至是2400波特率传输信息比如红外遥控器传输遥控信息这种情况下以流处理换取更多的成本优势几乎是不二的选择。那么当一个数据流中相邻的Process存在不同的偏好时怎么协调呢生产者Process使用“流”处理消费者Process使用“块”处理由消费者提供一个队列Q该队列将用于保存数据的块MEM提供给Q作为缓冲区初始化为空队列永久封堵的出队接口将的入队接口提供给生产者当队列满时将MEM取出交给消费者处理如果MEM是堆分配的则尝试从堆中获取一个新的MEM重复1的步骤当消费者完成对数据MEM的处理后应当在随后适当的位置将MEM释放回堆中生产者Process使用“块”处理消费者Process使用“流”处理由生产者提供一个队列Q并将保存数据的块MEM提供给Q作为缓冲区初始化为满队列永久封堵Q的入队接口将的出队接口提供给消费者当队列为空时如果MEM是堆分配的则将MEM释放回堆并等待生产者提供可用的数据块进而回到步骤12如果MEM是静态分配的唯一的则在此时还给生产者做下一次的数据生产通过上面的描述我们发现队列Queue在流块互转间扮演了关键的桥梁作用。这里不仅有传统意义上“将队列初始化为空”的操作还引入了“将队列初始化为满”的概念。简单来说封住出口初始化为空的队列可以用来把流转化成块而封住入口初始化为满的队列可以用来把块还原成流。——队列是一个典型的时空转换机构。【说个题外话】相信各位九年义务制教育的受害者们一定都还记得小学时候逆天的浪费水资源的游泳池放水问题吧当入水速度比出水速度快的时候游泳池的水位是一定会上涨的——泳池的深度只能决定多久这个池子会溢出来当入水速度小于出水速度的时候游泳池的水位一定是会下降的或者说存不住水的。队列本质上也就是个游泳池。如果入队速度恒定大于出队速度那么队列的深度只是决定了多久这个队列就会爆掉。但如果入队速度平均来说是小于等于出队速度的那么在入队速度瞬时超过出队速度时队列的深度直接决定了队列能对抗这种“瞬时”究竟多长时间。我们有很多“同志”总是把队列当成万能药只要觉得数据传输“可能出现速度不一致的问题”就吃一粒也不管这种速度差异是不是恒定的——就好像用了队列就可以高枕无忧——把脑袋扎进沙子里——而所有通信的问题就不存在了一样“我用队列了阿为什么还有问题”——呵呵‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧关注我的微信公众号回复“星球”加入知识星球有问必答。点击“阅读原文”查看知识星球详情欢迎点分享、收藏、点赞、在看。