[微知识]时间和空间的游戏——流/块篇

Gorgon_Meducer

---

说在前面的话

---

       有人说，世间问题再多，无非就是时间和空间的问题。每每看到这类说法，都不禁会让我想起
小时候看的《天龙八部》中的一处情节：彼时彼刻，少林寺正在被江湖歹人围攻，方丈情急之下问
虚竹外面有多少人，虚竹傻不啦叽的说好多人呢，作为装逼界的老把式，方丈故作高深的说：错，
只有两个人，名和利。原本这一教科书式的逼，我可以给90分，无奈后面分分钟打脸的情节破坏了
逼格的美感——虚竹听信了方丈的“教诲”，正若有所思时，方丈也在为这个逼装得恰如其分而沾沾
自喜，但突然意识到刀已经架到自己脖子上了，于是立马回到现实中，让虚竹再去看看外面有多少
人，虚竹记下了方丈的教诲，当然说只有两个人。这可把方丈开心死了，高喊这下少林寺有救了，
谁料自己推门一看，这啪啪啪的立即就被打了脸。

　　每次想到这个情节，我都忍俊不禁。时过境迁，突然轮到自己要说，其实计算机科学中只有两
个问题——时间和空间的问题——不由得担心起来，生怕打在老和尚脸上的巴掌已经等着我了。然
而，事实告诉我这并不是故弄玄虚，为了证明这一点，在未来的很长时间内，我将会用一系列的文
章来介绍嵌入式系统设计中、乃至是计算机科学中常见的“时间和空间”问题的实例。

　　今天，我们就从简单的流（Stream）和块（Block）的使用哲学说起。

---

　　虽然不是Linux提出的概念，但流（Stream）和块（Block）处理的深入人心绝对离不开流文件和
块文件的功劳。然而，流和块其实是更为通用的概念，它们分别代表了数据处理中 “以时间换空间”
和 “以空间换时间” 的两种截然不同的偏重策略。

1、以空间换时间的块处理
　　说到块处理，其最显著的特征就是，将所要处理的数据用一段连续的存储器保存下来，我们可以
随机对对这些数据进行访问和处理——简单说就是以保存数据所占用的存储器空间换取了访问的便利
性，降低了访问和处理的时间成本——因此我们可以说，块处理是一个典型的用存储器空间换取处理
时间的策略。
　　举例来说，假设我们需要从一段文字中中处理其中某几个单词，我们可以先简单的将整段文字连
续的保存在RAM中，然后使用基于块的字符串处理函数对其进行操作。由于访问方式简单直接（随机
访问），因此字符串处理的效率主要由处理的算法决定，字符串访问并不是瓶颈——简单说，就是算
法能多快快，整个操作就有多快，对字符串的访问并不存在额外的时延。

　　实际上，这个例子看似存在问题，因为字符串处理的基本单位仍然是字符，虽然目标数据被完整
地保存在数据块中，但常见的字符串操作仍然和流一样需要“一个字符一个字符”的顺次进行（例如比
较字符串，或者是查找字符串位置）。但我不得不举这个例子，因为它不仅仅是最常见的流操作和块
操作的目标，更重要的是，这种 “一个字符一个字符处理” 的特性让人们对流处理和块处理的特点在认
识上造成了模糊。因此，这里我想通过这个例子特别指出：

> 块处理中，字符串处理效率的瓶颈是由算法本身决定的，与之相比，数据访问的成本几乎可以忽略
不计（随机访问）。块处理的优势体现在，当我们以任意顺序访问块中的任意数据时，这里的访问成
本是最低的。块处理往往可以理解为：批量的处理，是效率的代名词；

> 流处理中，字符串处理效率的瓶颈是数据的访问，与之相对，算法的效率问题几乎可以忽略（顺序
访问）——要么是程序处理好当前字符后，喝完茶、打了个瞌睡，下一个字符还没有就绪；要么是处
理器处理一个字符所消耗的时间远没有从流中读取下一个字符来得长（考虑多任务间的队列通信）。
实际应用中，这两种情形往往是结合在一起的——当某个任务“焦急”的从串口缓冲区中尝试读取下一
个字符以便进行数据帧解析时，队列操作的时间、等待字符接收完成的时间通常比单独一个字符的处
理时间高出好几个数量级。

　　说了那么多废话，让我们来做一个小结：块（Block）处理就是消耗存储器空间将目标数据都存储
下来，以方便数据处理算法随机的对其进行访问，从而至少节省访问时间的一种处理方式（由于访问
是随机的，可选用的算法就变得多样起来，选择最优的算法也会带来额外的好处）。这是一个以存储
器空间换取访问时间的策略。

　　块的表现形式，是一段可随机访问的存储器空间。“可随机访问”是其时间上的本质，而块并不要
求数据在空间上是连续的（虽然字面上感觉应该要连续，但这种连续性并不是强制的）。

2、以时间换空间的流处理
　　流处理最显著的特点就是，大的数据块被人为拆分成小的数据单元，数据的处理方一次只能接收
或者处理一个数据单元。流处理最大的限制是数据访问顺序的限制——所有的数据单元必须按照流发
送方提供的顺序进行访问。正是由于这种访问顺序的限制，让流的处理方常常觉得“谁用谁知道”的别
扭。——很多时候，为了数据访问的方便，会将一部分流先缓冲成小的数据块，再以块的方式进行处
理——典型的例子就是串行数据通信中常见的数据帧（Frame）。
　　流处理的好处也是显而易见的，由于不需要大块的存储器空间用于数据的暂存，因而在小资源的
处理器，尤其是小SRAM的MCU中尤其流行。缺点是，受制于访问顺序，流处理的算法往往较为复杂，
有些功能甚至是无法实现的（单凭流处理本身无法实现，需要局部应用快处理）；同时流处理的数据
存取时间造成的浪费也非常可观。人常说，流处理的本质就是零库存的手工作坊，一切都得按步就班
的来，提高流处理效率的方法就是把数据传输所需的等待时间以流水线的方式利用起来。

　　小结一下，流（Stream）处理是以消耗更多处理器时间，并增加访问顺序的限制（顺序限制仍然
是时间轴上的一种限制）的方法，节省存储器空间的一种处理方式。这是一个以时间换空间的策略。

3、流和块的互换
　　在常见的嵌入式系统数据流中，每一个数据处理环节（简称数据处理Process）对时间和空间的偏
好是不同的。这里的数据流可能包含多个分工不同的子系统（处理器），甚至包含远端的服务器系统。
有的Process对性能（时间）敏感并拥有宽裕的RAM，显然应该利用块处理“以空间换时间”的特性，将
RAM富余的优势更多的转化为性能优势；有的Process对空间敏感（往往是成本敏感导致的），对性能
则要求不高（比如UART，9600，甚至是2400波特率传输信息，比如红外遥控器传输遥控信息），这
种情况下，以流处理换取更多的成本优势几乎是不二的选择。
　　那么，当一个数据流中，相邻的Process存在不同的偏好时怎么协调呢？

> 生产者Process使用“流”处理；消费者Process使用“块”处理
１、由消费者提供一个队列Q，该队列将用于保存数据的块MEM提供给Q作为缓冲区初始化为空队列；
２、永久封堵Ｑ的出队接口
３、将Ｑ的入队接口提供给生产者
４、当队列满时，将MEM取出，交给消费者处理；
５、如果MEM是堆分配的，则尝试从堆中获取一个新的MEM，重复1的步骤；当消费者完成对数据MEM
的处理后，应当在随后适当的位置将MEM释放回堆中

> 生产者Process使用“块”处理；消费者Process使用“流”处理
１、由生产者提供一个队列Q，并将保存数据的块MEM提供给Q作为缓冲区初始化为满队列；
２、永久封堵Q的入队接口
３、将Ｑ的出队接口提供给消费者
４、当队列为空时，１）如果MEM是堆分配的，则将MEM释放回堆，并等待生产者提供可用的数据块，
进而回到步骤1；2）如果MEM是静态分配的，唯一的，则在此时还给生产者做下一次的数据生产；

　　通过上面的描述，我们发现，队列（Queue）在流块互转间扮演了关键的桥梁作用。这里不仅有传
统意义上“将队列初始化为空”的操作，还引入了“将队列初始化为满”的概念。

　　为什么队列如此神奇呢？因为其本质是：用存储器空间为“出队”、“入队”之间偶尔的瞬间速度差争
取时间。（相信大家都知道小学时候变态的泳池放水模型）队列是一个典型的用空间换时间的数据结
构。它能争取的是“出队”、“入队”之间由于速度差导致的时间差异，能换多少时间，完全由缓冲区大小
决定。

　　我们有很多“同志”总是把队列当成万能药，只要觉得数据传输“可能出现速度不一致的问题”，就吃
一粒，也不管这种速度差异是不是恒定的（如果入队比出队恒定大，则队列必溢出，时间早晚由队列
缓冲大小决定）；就好像用了队列就可以当自己为鸵鸟——把脑袋扎进沙子里——而所有通信的问题就
不存在了一样：

　　 恩！存在也不是速度差异的问题——“我用队列了阿？为什么还有问题？”——呵呵哒！

　　其实，整篇文章铺垫那么多，就是为了最后一处吐槽作铺垫，吐完收工！畅快！舒服～哈哈哈哈。

---

范例代码（模块）

---

Stream2Block
支持“初始化为满”的队列模板

---

---

如果你喜欢我的思维，欢迎订阅 裸机思维
所有内容原创，严禁任何形式的转载。

---

bg6agf

1L ！！！！！！！！！！！
或者。叫。沙发？

foxpro2005

紧跟学习

popwolf

看完顶贴，然后关注微信号，然后再看了几段，然后...就催书吧~~

liangyurongde

又有东西学了。

yu2008

继续等。。。。。。。。。。

FORDREAM0

很形象 很贴切 "流"和"块"

canspider

速率不匹配时需要分析阻塞链路，不能当鸵鸟
比如USB转串口应用
必须想办法把串口的阻塞传递到应用程序

mainbp

canspider 发表于 2016-1-19 22:45
速率不匹配时需要分析阻塞链路，不能当鸵鸟
比如USB转串口应用
必须想办法把串口的阻塞传递到应用程序 ...

虽然没做过这方方面的应用，但是思考LZ说的生产者消费者存在速度差的时候，很赞同你这种思路

ppdd

踩着点儿!

fangy

认真听课。   ，

didadida

“我用队列了阿？为什么还有问题？”

Gorgon_Meducer

道理虽然简单，应用到项目分析里面，却能解决相当大一部分问题。

xiaoliusheng

楼主 ，你的新书呢？

jianplx

感谢分享

joiway

嗯，关注楼主新书

eliterxzgxu

学习了，很有用

guolun

楼主的微信值得关注。对一些问题的探讨很精辟。

stevenh

公众号：裸机思维  为什么搜索不到？

panhai0101

没事多写点啊。

Xiyuhexuan

mark      

fangy

Gorgon_Meducer 膜拜

Gorgon_Meducer

更新范例代码