最近看了看書，看了看博客，聽了聽高人們的談論，心里有些體會，記錄下來，算是最近寫的一個關于堆代碼的總結吧，雖然是很簡單的應用，但是自己從中學到了知識，也算收貨不少。某位偉人說的，人生每天進步一點點，（后面是啥，忘記了。。。）。好了，不扯淡了，開始話題。
首先，我來說下怎么用單鏈表去模擬一個堆（準確說是一個內存池）。
用單鏈表去記錄一些可用的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;
}
//添加新的節(jié)點
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限制，不得不順序執(zhí)行，這就是以時間換空間。也就是說用提供模塊的專用堆，我們可以很方便的根據實際RAM大小去選擇
運行方案，而不需要更要上層調用邏輯。這就是專用HEAP作用。
其實說來這么多廢話，主要是想引出下面這邊博客（不要罵我無恥，其實我就是菜鳥，才剛學）：
出處：http://www.amobbs.com/thread-5642364-1-1.html
雖然不是Linux提出的概念，但流（Stream）和塊（Block）處理的深入人心絕對離不開流文件和
塊文件的功勞。然而，流和塊其實是更為通用的概念，它們分別代表了數據處理中 “以時間換空間”
和 “以空間換時間” 的兩種截然不同的偏重策略。
1、以空間換時間的塊處理
說到塊處理，其最顯著的特征就是，將所要處理的數據用一段連續(xù)的存儲器保存下來，我們可以
隨機對對這些數據進行訪問和處理——簡單說就是以保存數據所占用的存儲器空間換取了訪問的便利
性，降低了訪問和處理的時間成本——因此我們可以說，塊處理是一個典型的用存儲器空間換取處理
時間的策略。
舉例來說，假設我們需要從一段文字中中處理其中某幾個單詞，我們可以先簡單的將整段文字連
續(xù)的保存在RAM中，然后使用基于塊的字符串處理函數對其進行操作。由于訪問方式簡單直接（隨機
訪問），因此字符串處理的效率主要由處理的算法決定，字符串訪問并不是瓶頸——簡單說，就是算
法能多快快，整個操作就有多快，對字符串的訪問并不存在額外的時延。
實際上，這個例子看似存在問題，因為字符串處理的基本單位仍然是字符，雖然目標數據被完整
地保存在數據塊中，但常見的字符串操作仍然和流一樣需要“一個字符一個字符”的順次進行（例如比
較字符串，或者是查找字符串位置）。但我不得不舉這個例子，因為它不僅僅是最常見的流操作和塊
操作的目標，更重要的是，這種 “一個字符一個字符處理” 的特性讓人們對流處理和塊處理的特點在認
識上造成了模糊。因此，這里我想通過這個例子特別指出：
> 塊處理中，字符串處理效率的瓶頸是由算法本身決定的，與之相比，數據訪問的成本幾乎可以忽略
不計（隨機訪問）。塊處理的優(yōu)勢體現在，當我們以任意順序訪問塊中的任意數據時，這里的訪問成
本是最低的。塊處理往往可以理解為：批量的處理，是效率的代名詞；
> 流處理中，字符串處理效率的瓶頸是數據的訪問，與之相對，算法的效率問題幾乎可以忽略（順序
訪問）——要么是程序處理好當前字符后，喝完茶、打了個瞌睡，下一個字符還沒有就緒；要么是處
理器處理一個字符所消耗的時間遠沒有從流中讀取下一個字符來得長（考慮多任務間的隊列通信）。
實際應用中，這兩種情形往往是結合在一起的——當某個任務“焦急”的從串口緩沖區(qū)中嘗試讀取下一
個字符以便進行數據幀解析時，隊列操作的時間、等待字符接收完成的時間通常比單獨一個字符的處
理時間高出好幾個數量級。
說了那么多廢話，讓我們來做一個小結：塊（Block）處理就是消耗存儲器空間將目標數據都存儲
下來，以方便數據處理算法隨機的對其進行訪問，從而至少節(jié)省訪問時間的一種處理方式（由于訪問
是隨機的，可選用的算法就變得多樣起來，選擇最優(yōu)的算法也會帶來額外的好處）。這是一個以存儲
器空間換取訪問時間的策略。
塊的表現形式，是一段可隨機訪問的存儲器空間?！翱呻S機訪問”是其時間上的本質，而塊并不要
求數據在空間上是連續(xù)的（雖然字面上感覺應該要連續(xù)，但這種連續(xù)性并不是強制的）。
2、以時間換空間的流處理
流處理最顯著的特點就是，大的數據塊被人為拆分成小的數據單元，數據的處理方一次只能接收
或者處理一個數據單元。流處理最大的限制是數據訪問順序的限制——所有的數據單元必須按照流發(fā)
送方提供的順序進行訪問。正是由于這種訪問順序的限制，讓流的處理方常常覺得“誰用誰知道”的別
扭?！芏鄷r候，為了數據訪問的方便，會將一部分流先緩沖成小的數據塊，再以塊的方式進行處
理——典型的例子就是串行數據通信中常見的數據幀（Frame）。
流處理的好處也是顯而易見的，由于不需要大塊的存儲器空間用于數據的暫存，因而在小資源的
處理器，尤其是小SRAM的MCU中尤其流行。缺點是，受制于訪問順序，流處理的算法往往較為復雜，
有些功能甚至是無法實現的（單憑流處理本身無法實現，需要局部應用快處理）；同時流處理的數據
存取時間造成的浪費也非?？捎^。人常說，流處理的本質就是零庫存的手工作坊，一切都得按步就班
的來，提高流處理效率的方法就是把數據傳輸所需的等待時間以流水線的方式利用起來。
小結一下，流（Stream）處理是以消耗更多處理器時間，并增加訪問順序的限制（順序限制仍然
是時間軸上的一種限制）的方法，節(jié)省存儲器空間的一種處理方式。這是一個以時間換空間的策略。
3、流和塊的互換
在常見的嵌入式系統(tǒng)數據流中，每一個數據處理環(huán)節(jié)（簡稱數據處理Process）對時間和空間的偏
好是不同的。這里的數據流可能包含多個分工不同的子系統(tǒng)（處理器），甚至包含遠端的服務器系統(tǒng)。
有的Process對性能（時間）敏感并擁有寬裕的RAM，顯然應該利用塊處理“以空間換時間”的特性，將
RAM富余的優(yōu)勢更多的轉化為性能優(yōu)勢；有的Process對空間敏感（往往是成本敏感導致的），對性能
則要求不高（比如UART，9600，甚至是2400波特率傳輸信息，比如紅外遙控器傳輸遙控信息），這
種情況下，以流處理換取更多的成本優(yōu)勢幾乎是不二的選擇。
那么，當一個數據流中，相鄰的Process存在不同的偏好時怎么協調呢？
> 生產者Process使用“流”處理；消費者Process使用“塊”處理
１、由消費者提供一個隊列Q，該隊列將用于保存數據的塊MEM提供給Q作為緩沖區(qū)初始化為空隊列；
２、永久封堵Ｑ的出隊接口
３、將Ｑ的入隊接口提供給生產者
４、當隊列滿時，將MEM取出，交給消費者處理；
５、如果MEM是堆分配的，則嘗試從堆中獲取一個新的MEM，重復1的步驟；當消費者完成對數據MEM
的處理后，應當在隨后適當的位置將MEM釋放回堆中
> 生產者Process使用“塊”處理；消費者Process使用“流”處理
１、由生產者提供一個隊列Q，并將保存數據的塊MEM提供給Q作為緩沖區(qū)初始化為滿隊列；
２、永久封堵Q的入隊接口
３、將Ｑ的出隊接口提供給消費者
４、當隊列為空時，１）如果MEM是堆分配的，則將MEM釋放回堆，并等待生產者提供可用的數據塊，
進而回到步驟1；2）如果MEM是靜態(tài)分配的，唯一的，則在此時還給生產者做下一次的數據生產；
通過上面的描述，我們發(fā)現，隊列（Queue）在流塊互轉間扮演了關鍵的橋梁作用。這里不僅有傳
統(tǒng)意義上“將隊列初始化為空”的操作，還引入了“將隊列初始化為滿”的概念。
為什么隊列如此神奇呢？因為其本質是：用存儲器空間為“出隊”、“入隊”之間偶爾的瞬間速度差爭
取時間。（相信大家都知道小學時候變態(tài)的泳池放水模型）隊列是一個典型的用空間換時間的數據結
構。它能爭取的是“出隊”、“入隊”之間由于速度差導致的時間差異，能換多少時間，完全由緩沖區(qū)大小
決定。
我們有很多“同志”總是把隊列當成萬能藥，只要覺得數據傳輸“可能出現速度不一致的問題”，就吃
一粒，也不管這種速度差異是不是恒定的（如果入隊比出隊恒定大，則隊列必溢出，時間早晚由隊列
緩沖大小決定）；就好像用了隊列就可以當自己為鴕鳥——把腦袋扎進沙子里——而所有通信的問題就
不存在了一樣：
恩！存在也不是速度差異的問題——“我用隊列了阿？為什么還有問題？”——呵呵噠！
其實，整篇文章鋪墊那么多，就是為了最后一處吐槽作鋪墊，吐完收工！暢快！舒服～哈哈哈哈。
下載文檔
