单片机资源：时间和空间的思考
扫描二维码
随时随地手机看文章
最近看了看书，看了看博客，听了听高人们的谈论，心里有些体会，记录下来，算是最近写的一个关于堆代码的总结吧，虽然是很简单的应用，但是自己从中学到了知识，也算收货不少。某位伟人说的，人生每天进步一点点，（后面是啥，忘记了。。。）。好了，不扯淡了，开始话题。
首先，我来说下怎么用单链表去模拟一个堆（准确说是一个内存池）。
用单链表去记录一些可用的memory，主要是用单链表把这些可用的内存记录起来。
用自己的malloc去从单链表中返回一个可用内存，并把这片可用内存从链表中删除。
用自己的free把用完的内存再添加到可用内存链表中。
有个memory_add函数，把一片可用内存初始化为可用的内存链表。
具体实现：
void free_check_str_t(check_str_t *ptItem)
{
check_t* ptThis = (check_t*)ptItem;
check_t* ptTempList = s_ptFreeList;
if(NULL == ptThis){
return;
}
s_ptFreeList = &this;
this.ptNext = ptTempList;
}
check_str_t *malloc_check_str_t(void)
{
check_t *ptThis = s_ptFreeList;
if(NULL == ptThis){
return NULL;
}
s_ptFreeList = this.ptNext;
this.ptNext = NULL;
return (check_str_t*)(&this.tItem);
}
bool add_memory_block_to_check_str_t_heap(void *pBlock, uint32_t wBlockSize)
{
check_t *ptNew = NULL;
uint8_t *pchTemp = pBlock;
uint32_t wi = 0;
if(NULL == pBlock){
return false;
}
if(CHECK_LIST_ITEM_SIZE > wBlockSize){
return false;
}
//添加新的节点
for(wi=0;wi
return true;
}
ptNew = (check_t *)(pchTemp+wi);
free_check_str_t((check_str_t*)ptNew);
}
return true;
}
这样就是实现了一个简单的专用堆，准确说是栈结构的。这样做比用static的变量去实现有什么好处呢？
先说缺点：
1、相同的变量比原来要多一个指针空间（不是链表自身，而是存储申请的HEAP地址）；
2、这个缺点很重要，一不小心就内存泄漏；
既然有缺点，为什么人们还热此不彼的去用专用堆呢？
我开始没理解，后来还是没理解。原来这么做是为了以时间换空间（引出了今天的话题）。什么意思呢？
比方说，上面是一个可重入的模块，它提供某项服务（需要消耗一个struct 空间）。
有三个任务A/B/C都要需要调用这个服务。假如RAM宽裕，可以为每个任务都单独提供一个struct（为了重入），
那么这个时候这三个任务不需要等待，就可以同时运行，也就是通过牺牲RAM（空间），换取三个任务同时运行时间。
假如RAM不够大，那么只能用一个struct，大家轮流去申请，谁申请到谁用，用完释放掉，这样本来三个可以并行运行的任务，
由于RAM限制，不得不顺序执行，这就是以时间换空间。也就是说用提供模块的专用堆，我们可以很方便的根据实际RAM大小去选择
运行方案，而不需要更要上层调用逻辑。这就是专用HEAP作用。
其实说来这么多废话，主要是想引出下面这边博客（不要骂我无耻，其实我就是菜鸟，才刚学）：
出处：http://www.amobbs.com/thread-5642364-1-1.html
虽然不是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）在流块互转间扮演了关键的桥梁作用。这里不仅有传
统意义上“将队列初始化为空”的操作，还引入了“将队列初始化为满”的概念。
为什么队列如此神奇呢？因为其本质是：用存储器空间为“出队”、“入队”之间偶尔的瞬间速度差争
取时间。（相信大家都知道小学时候变态的泳池放水模型）队列是一个典型的用空间换时间的数据结
构。它能争取的是“出队”、“入队”之间由于速度差导致的时间差异，能换多少时间，完全由缓冲区大小
决定。
我们有很多“同志”总是把队列当成万能药，只要觉得数据传输“可能出现速度不一致的问题”，就吃
一粒，也不管这种速度差异是不是恒定的（如果入队比出队恒定大，则队列必溢出，时间早晚由队列
缓冲大小决定）；就好像用了队列就可以当自己为鸵鸟——把脑袋扎进沙子里——而所有通信的问题就
不存在了一样：
恩！存在也不是速度差异的问题——“我用队列了阿？为什么还有问题？”——呵呵哒！
其实，整篇文章铺垫那么多，就是为了最后一处吐槽作铺垫，吐完收工！畅快！舒服～哈哈哈哈。
下载文档
