1、內存

程序為什么需要內存

? ? ?程序運行的目的：

程序運行是為了得到一定的結果，程序運行其實是在做一系列的數據計算，所以：程序=代碼+數據；

程序運行的目的不外乎2個：過程、結果； ? ?用函數來類比：函數的形參就相當于代加工的數據，函數的本體是代碼，函數的返回值就是結果，函數體的執行過程就是過程。如下列函數：

int add(int a, int b)
{return a + b;}           // 這個函數的執行就是為了得到結果
void add(int a, int b)
{int c;c = a + b;printf("c = %d.\n", c);} // 這個函數的執行重在過程（重在過程中的printf），返回值不需要

intadd(int a, int b)
{int c;c = a + b;printf("c = %d.\n", c);return c;
}           // 這個函數又重結果又重過程

?????計算機程序運行過程：

計算機程序運行的過程其實就是多個函數相繼運行的過程，程序由多個函數組成；
程序的本質是函數，函數的本質是加工數據的動作；

? ??

?????馮諾依曼結果和哈佛結構：

馮諾依曼：代碼和數據放在一起；
哈佛結構：代碼和數據分開存放；
代碼：函數； ? ?數據：全局變量和局部變量；

在S5PV210中運行的linux系統上，運行應用程序時：這時應用程序的代碼和數據都在DRAM，所以這種結構是馮諾依曼結構；在單片機中，我們把程序燒寫到Flash（NorFlash）中，然后在Flash中原地運行，程序中所涉及到的數據（全局變量、局部變量）不能放在Flash中，必須放在RAM（SRAM）中，這種就叫哈佛結構。

? ? ? 動態內存DRAM和靜態內存SRAM：

SRAM：靜態內存優點：不需要軟件初始化，上電就能用；缺點：容量小，價格高；
DRAM：動態內存優點：容量大，價格低；缺點：上電不能使用，需要軟件初始化；
單片機：內存需求量小，而且希望開發盡量簡單，適合使用SRAM；
PC機：內存需求量大，而且軟件復雜，不在乎DRAM的初始化開銷，適合全部使用DRAM；
嵌入式系統：內存需求量大，而且沒有NorFlash等啟動介質；

? ? ?總結：為什么需要內存？

內存是用來存儲數據的，數據在程序中表現為變量（在gcc中，其實常量也是儲存在內存中的）。
大部分的單片機代碼段儲存在flash中，數據常量儲存在flash中，對我們寫程序至關重要，與程序運行有本質關系；

內存管理是我們寫程序時很重要的話題，我們以前學過的很多編程的關鍵都是管理內存譬如數據結構（研究數據是如何組織的，數據放在內存中的）和算法（為了更有效更優秀的方法來加工數據，既然跟數據有關就離不開內存）

? ? ?深入思考：如何管理內存（有OS時，無OS時）

有OS時：操作系統管理所有的硬件內存，將內存分為一個一個的頁面（就是一塊，一般是4KB），然后以頁面為單位來管理。頁面內用更細小的方式以字節來管理。操作系統為我們提供了內存管理接口，我們只需要用API來管理內存，如C語言中的malloc、free這些接口來管理內存。

無OS時：在沒有操作系統（其實就是裸機程序）中，程序需要直接操作內存，編程者需要自己計算內存的使用和安排。如果編程者不小心把內存用錯了，錯誤結果需要自己承擔。

? ? ?各種語言管理內存的區別：

匯編：直接操作內存（如0xd0020010），非常麻煩；

C語言：匯編器幫我們管理內存，我們可以通過編譯器提供的變量名來訪問內存，操作系統下如果需要大塊內存，可以通過API接口（malloc、free）來訪問系統內存。裸機中需要大塊內存需要自己定義數組來解決；

C++：C++語言對內存的使用進一步封裝。我們可以用new來創建對象（其實就是為對象分配內存），然后使用完了用delete來刪除對象（其實就是釋放內存）。所以C++語言對內存的管理比C要高級一些，容易一些。但是C++中內存的管理還是靠程序員自己來做。如果程序員new了一個對象，但是用完了忘記delete就會造成這個對象占用的內存不能釋放，這就是內存泄漏。

Java/C#等語言：這些語言不直接操作內存，而是通過虛擬機來操作內存。這樣虛擬機作為我們程序員的代理，來幫我們處理內存的釋放工作。如果我的程序申請了內存，使用完成后忘記釋放，則虛擬機會幫我釋放掉這些內存。聽起來似乎C# java等語言比C/C++有優勢，但是其實他這個虛擬機回收內存是需要付出一定代價的，所以說語言沒有好壞，只有適應不適應。當我們程序對性能非常在乎的時候（譬如操作系統內核）就會用C/C++語言；當我們對開發程序的速度非常在乎的時候，就會用Java/C#等語言。

位、字節、半字、字和內存字寬

? ? ?什么是內存：

硬件角度：SRAM、DRAM（DRAM分為多代：SDRAM、DDR...）
邏輯角度：內存可以隨機訪問，并可以讀寫；內存在編程過程中，天然用來定義變量（因為有內存，所以C語言才能定義變量），程序中一個變量，代表內存中一個內存地址；
?

?????內存的邏輯抽象圖：

?一個大格子中有許多小格子，每個格子對應一個內存地址；
系統位數（32位、64位）與數據總線有關，內存也與數據總線有關，32位系統內存為4G（2^32）

?????位和字節：

內存單元大小單位有4個：位（1bit）、字節（8bit）、半字（一般16bit）、字（一般32bit）；
所有系統中，位都是1bit，字節都是8bit；

?????

? ? ?字和位寬：

歷史上出現過16位、32位、64位操作系統，字的大小與操作系統有關，所以沒必要可以記住這些單位的大小；
實際工作中在每種平臺上，先搞清楚這個平臺的定義；
編程時，一般是以字為單位，用不到這些概念，區分這個概念主要是因為有些文檔中會用到，如果不區分，可能會造成對程序的誤解；
在linux+ARM這個軟硬件平臺上，字是32位的；

? ? ?內存位寬（硬件和邏輯兩個角度）：

硬件角度：硬件本身是有寬度的，硬件寬度可以通過級聯的方式進行擴展，如16位內存條可以通過并聯，得到32位內存條；
邏輯角度：內存的位寬可以是任意位的，我們直接操作即可，但實際操作限制于硬件特性，所以我們的很多實際操作都限制于硬件的特性；

? ? ?

內存編址和尋址、內存對齊

? ? ?內存的編址方法：

計算機中CPU實際只認識內存地址，而不關心這個地址所代表的空間在哪里、怎么分布，因為硬件設計保證了按照這個地址就能找到這個格子，所以內存的單元的2個概念：地址和內存單元的兩個方面。

? ? ?關鍵：內存編址是以字節為單位的：

把內存比喻成一棟樓，那么每個樓里的一個一個房間就好像一個內存格子，這個格子的大小是固定的，就好像這個大樓里面所有的房間戶型都是一樣的；

? ? ?內存和數據類型的關系：

C語言常用的數據類型有：char、short、int、long、float、double；
整形int體現他和CPU本身的數據位寬是一樣的，比如32位CPU，整形int就是32位的；
數據類型和內存的關系在于：數據類型是用來定義變量的，而這些變量需要存儲、運算在內存中，所以數據類型必須和內存相匹配才能獲得最好的性能，否則可能不工作或者效率低下；
32位系統最好用int，因為效率最高，原因在于32位的系統本身配合內存等也是32位，這樣的硬件配置天生適合定義32位的int類型變量，效率最高。也能定義8位char類型變量或者16位short類型變量，但實際上訪問效率不高；
32位環境下，實際定義bool類型變量（實際1bit就夠了）都是用int來實現bool的，也就是說我們定義一個bool時，編譯器實際幫我們分配了32位的內存來存儲這個bool變量。編譯器這么做浪費了31位的內存，但是好處是效率高；

編程時以省內存為主還是重效率？ ? ?內存很小時以省內存為主，但是現在寫程序一般以效率為主；

? ? ?內存對齊：

在C程序中：int a；為a分配4個字節，有兩種分配方式：

第一種：0 1 2 3； ? ? ? ? ? ? ?對齊訪問
第二種：1 2 3 4或 3 4 5 6 ? ? ?非對齊訪問；

內存對齊訪問不是邏輯問題，而是硬件問題，從硬件角度來說，32位的內存“0 1 2 3”四個單元本身邏輯上就有相關性，四個字節組合作為一個int，硬件上就是合適的，所以效率高，非對齊方式和硬件本省不搭，所以訪問效率低（一般硬件也支持非對齊訪問，但效率很低）；

? ? ?從內存編址看數組的意義：

C語言如何操作內存

?????C語言對內存地址的封裝：

用變量名訪問內存、數據類型的含義、函數名的含義；如：int a；a=5;a+=4; ? ? //a==4；
定義一個變量a；編譯器把變量和這個地址綁定，將變量的值放到地址空間中；讀取內存單元中的值，然后+4，然后再放入地址空間；

C語言中數據類型的本質含義：表示一個內存格子的長度和解析方法；
數據類型決定長度的含義：我們一個內存地址（0x30000000），本來這個地址只代表1個字節的長度，但是實際上我們可以通過給他一個類型(int)，讓他有了長度(4)，這樣這個代表內存地址的數字(0x30000000)就能表示從這個數字(0x30000000)開頭的連續的n(4)個字節的內存格子了(0x30000000 + x30000001 + 0x30000002 + 0x30000003)。 ??
數據類型決定解析方法的含義：譬如我有一個內存地址（0x30000000），我們可以通過給這個內存地址不同的類型來指定這個內存單元格子中二進制數的解析方法。譬如我 (int)0x30000000，含義就是(0x30000000 + 0x30000001 + 0x30000002 + 0x30000003)這4個字節連起來共同存儲的是一個int型數據；那么我(float)0x30000000，含義就是(0x30000000 + 0x30000001 + 0x30000002 + 0x30000003)這4個字節連起來共同存儲的是一個float型數據；之前講過一個很重要的概念：內存單元格子的編址單位是字節。

(int?*)0;? ? ? ?//表示將0轉換成int型指針

(float?*)0;
(short)0;? ? ? ?//表示將數字0轉換成short型
(char)0;
int a; // int a;時編譯器會自動給a分配一個內存地址，譬如說是0x12345678
(int *)a; // 等價于(int *)0x12345678

(float?*)a;?

? ? ?用指針來間接訪問內存：

關于指針類型（不管是普通類型int 、float...，還是指針類型 int * 、float * ...）只要記住：類型只是對數字或符號（代表的是內存）所表征的一種長度規定和解析方法的規定；
指針變量和普通變量沒什么區別，如int a，int *p，都是代表一個地址（譬如是0x20000000），但是內存地址0x20000000的長度和解析方法不同，a是int型所以a的長度是4字節，解析方法是按照int的規定來的；p是int *類型，所以長度是4字節，解析方法是int *的規定來的（0x20000000開頭的連續4字節中存儲了1個地址，這個地址所代表的內存單元中存放的是一個int類型的數）。

? ? ?

? ? ?指針類型的含義：

指針變量和普通變量沒什么區別，如int a，int *p，都是代表一個地址（譬如是0x20000000），但是內存地址0x20000000的長度和解析方法不同，a是int型所以a的長度是4字節，解析方法是按照int的規定來的；p是int *類型，所以長度是4字節，解析方法是int *的規定來的（0x20000000開頭的連續4字節中存儲了1個地址，這個地址所代表的內存單元中存放的是一個int類型的數）。

? ? ?用數組來管理內存：

數組管理內存和變量沒什么本質區別，只是符號的解析方法不同。（普通變量、數組、指針變量其實沒什么差別，都是對內存地址的解析，只是解析方法不一樣）。

int?a;?// 編譯器分配4字節長度給a，并且把首地址和符號a綁定起來。
int?b[10];?//?編譯器分配40個字節長度給b，并且把首元素首地址和符號b綁定起來。

數組中第一個元素（a[0]）就稱為首元素；每一個元素類型都是int，所以長度都是4，其中第一個字節的地址就稱為首地址；首元素a[0]的首地址就稱為首元素首地址。

內存管理之結構體

? ? ?數據結構的意義：

研究數組如何組織

? ? ?最簡單的數據結構：數組

為什么要有數組？因為程序中有好多個類型相同、意義相關的變量需要管理，這時候如果用單獨的變量來做程序看起來比較亂，用數組來管理會更好管理。譬如 int ages[20];

? ? ?數組的優勢和缺陷：

優勢：數組簡單，使用下標進行隨機訪問；
缺陷：①數組中所有元素的數據類型必須相同；②數據的大小必須在定義時給出，而一旦確定就不能更改；

? ? ?結構體：

結構體的出現是為了解決數據的缺陷①；

//定義3個學生的年齡
//方法一：
int?age[3];
//方法二：
struct ages {
int age1;
int age2;
int age3;
}；
//相比之下使用數組更簡單；

//定義1個學生的身高、姓名、年齡
//就必須使用結構體，因為身高、姓名、年齡不是同一個類型
struct stu {
int age;
? ? float?name;
? ?float height;
};?

數組和結構體的本質差異在于對內存的管理方式；（數組是一種特殊的結構體）

結構體的使用方法，見：http://blog.csdn.net/tuoguang/article/details/46928481

? ? ?題外：結構體內嵌指針實現面向對象：

總體來說，C語言是面向過程的，但C語言寫出的linux系統是面向對象的，非面向對象的語言同能但寫出面向對象的代碼，但沒有面向對象的語言來的直接；
使用C語言寫的linux內核代碼能實現面向對象，主要是在結構體中內嵌指針來實現的：

struct?stu
{
int?age;? ? ? ? ? ? ? ? ? ? //?普通變量
void?(*pFunc)(void);? ? ? ?//?函數指針，指向?void?func(void)這類的函數
};?
使用這樣的結構體就能實現面向對象

這種包含函數指針的結構體就類似面向對象中的class，結構體中的變量就類似于class中的成員變量，結構體中的指針就類似于class中的成員方法；

內存管理之棧（stack）

? ? ?什么是棧：

棧是一種數據結構，C語言中使用棧來保存局部變量。棧是用來內存管理的

? ? ?棧管理內存的特點：

? ? ? ? ?

bottom指針在最低，不能移動，top指針在上層，能自由移動；
先進后出FILO （fast in last out） ? ?棧
先進先出FIFO （fast in fast out） ? ?隊列
棧的特點是只有入口即出口，另一個口是堵死的。所以先進去的必須后出來。
隊列的特點是入口和出口都有，必須從入口進去，從出口出來，所以先進去的必須先出來，否則就堵住后面的。

? ? ?棧的應用舉例：局部變量

C語言中的局部變量使用棧來實現的；
我們在C中定義一個局部變量（int a；）時，編譯器會在棧中分配一段空間（4字節）給這個局部變量用（分配時棧頂指針會移動給出空間，給局部變量a用的意思就是，將這4字節的棧內存的內存地址和我們定義的局部變量名a給關聯起來），對應棧的操作是入棧。

注意：這里棧指針的移動和內存分配是自動的（棧自己完成，不用我們寫代碼去操作）。

然后等我們函數退出的時候，局部變量要滅亡。對應棧的操作是彈棧（出棧）。出棧時也是棧頂指針移動將棧空間中與a關聯的那4個字節空間釋放。這個動作也是自動的，也不用人寫代碼干預。

?????棧的優點：

棧管理內存，好處是方便，分配和最后回收都不用程序員操心，C語言自動完成。

分析一個細節：C語言中，定義局部變量時如果未初始化，則值是隨機的，為什么？ ??
定義局部變量，其實就是在棧中通過移動棧指針來給程序提供一個內存空間和這個局部變量名綁定。因為這段內存空間在棧上，而棧內存是反復使用的（臟的，上次用完沒清零的），所以說使用棧來實現的局部變量定義時如果不顯式初始化，值就是臟的。如果你顯式初始化怎么樣？
C語言是通過一個小手段來實現局部變量的初始化的。

int?a?=?15;? ? ?//?局部變量定義時初始化
C語言編譯器會自動把這行轉成：
int?a;? ? ? ? ?//?局部變量定義
a?=?15;? ? ? ? ?//?普通的賦值語句?

　　棧的約束：

棧是有大小的，所以棧內存大小不好設置。如果太小怕溢出，太大怕浪費內存。（缺點優點像數組）；
棧的溢出危害很大，一定要避免（C語言本身不會檢測棧是否溢出），所以在C語言中定義局部變量時，不能定義太大或者太小，（譬如不能定義局部變量時 int a[10000];使用遞歸來解決問題時，一定要注意遞歸收斂）；

內存管理之堆：（heap）

? ? ?什么是堆：

堆（heap）是一種內存管理方式。內存管理對操作系統來說是一件非常復雜的事情，因為首先內存容量很大，其次內存需求在時間和大小塊上沒有規律（操作系統上運行著的幾十、幾百、幾千個進程隨時都會申請或者釋放內存，申請或者釋放的內存塊大小隨意）。
堆這種內存管理方式特點就是自由（隨時申請、釋放；大小塊隨意）。堆內存是操作系統劃歸給堆管理器（操作系統中的一段代碼，屬于操作系統的內存管理單元）來管理的，然后向使用者（用戶進程）提供API（malloc、free）來使用堆內存。

我們什么時候使用堆內存？ ? ?需要內存容量比較大時；需要反復使用及釋放時；很多數據結構（譬如鏈表）的實現都要使用堆內存。? ?

?????

? ? ?堆管理內存的特點：

容量不限（常規使用的需求容量都能滿足）；
申請及釋放都需要手工進行，程序員需寫代碼明確進行申請malloc及釋放free。如果程序員未及時申請內存并使用后釋放，這段內存就丟失了，稱為內存泄漏。在C/C++語言中，內存泄漏是最嚴重的程序bug，這也是別人認為Java/C#等語言比C/C++優秀的地方。

? ? ?C語言操作堆內存的接口：（malloc、free）

堆內存釋放最簡單，直接調用free釋放即可。原型為：void free（void *ptr）；
堆內存申請時，有3個可選擇的類似功能的函數：malloc、calloc、realloc；原型分別為：

void?*malloc(size_t?size);
void?*calloc(size_t?nmemb,?size_t?size);? ?//?nmemb個單元，每個單元size字節
void?*realloc(void?*ptr,?size_t?size);? ? ?//?改變原來申請的空間的大小的?

譬如申請10個int元素的內存： ? ??

//使用后者更好，有利于不同平臺的程序移植
malloc(40);? ? ? ??(int *)malloc(10*sizeof(int));?
calloc(10,4); ? ? ?(int *)calloc(10,sizeof(int));??

數組定義時，必須同時給出數組元素個數（數組大小），而且一旦定義再無法修改。在Java等高級語言中，有一些語法技巧可以更改數組大小，但其實這只是一種障眼法。它的工作原理是：先重新創建一個新的數組大小為要更改后的數組，然后將原數組的所有元素復制進新的數組，然后釋放掉原數組，最后返回新的數組給用戶；

堆內存申請時必須給定大小，一旦申請完成大小不能該更，如果要改變，只能調用接口函數?realloc。realloc的實現原理類似于上面說的Java中的可變大小的數組的方式。

? ? ?堆的優勢和劣勢；（管理大塊內存、靈活、容易內存泄漏）

優勢：靈活；
劣勢：需要程序員去處理各種細節，所以容易出錯，嚴重依賴于程序員的水平； ? ?

復雜數據結構

? ? ?鏈表：

嵌入式領域中，鏈表是最重要的，鏈表在linux內核中使用非常多，驅動、應用編寫很多時候都需要使用鏈表。所以鏈表必須掌握。掌握到：會自己定義結構體來實現鏈表、會寫鏈表的節點插入（前插、后插）、節點刪除、節點查找、節點遍歷等。（至于像逆序這些很少用，掌握了前面那幾個這個也不難）。

? ? ?哈希表：

哈希表不是很常用，一般不需要自己寫實現，而直接使用別人實現的哈希表比較多。對我們來說最重要的是要明白哈希表的原理、從而知道哈希表的特點，從而知道什么時候該用哈希表，當看到別人用了哈希表的時候要明白別人為什么要用哈希表、合適不合適？有沒有更好的選擇？（哈希表和數組的區別：數組的下標是依次排列的，而哈希表的下標是亂序的，是通過一定的公式計算得到的，可以將其看作是由數組映射得到的。）

? ? ?二叉樹、圖等：

二叉樹、圖等。對于這些復雜數據結構，不要太當回事。這些復雜數據結構用到的概率很小（在嵌入式開發中），其實這些數據結構被發明出來就是為了解決特定問題的，你不處理特定問題根本用不到這些，沒必要去研究。

? ? ?為什么需要更復雜的數據結構：

因為現實中的實際問題是多種多樣的，問題的復雜度不同，所以需要解決問題的算法和數據結構也不同。所以當你處理什么復雜度的問題，就去研究針對性解決的數據結構和算法；當你沒有遇到此類問題（或者你工作的領域根本跟這個就沒關系）時就不要去管了。

? ? ?

? ? ?數據結構和算法的關系：

數據結構的發明都是為了配合一定的算法；算法是為了處理具體問題，算法的實現依賴于相應的數據結構；
當前我們說的算法和純數學是不同的（算法是基于數學的，大學計算機系研究生博士生很多本科都是數學相關專業的），因為計算機算法要求以數學算法為指導，并且結合計算機本身的特點來改進，最終實現一個在計算機上可以運行的算法（意思就是用代碼可以表示的算法）。

? ? ?應該怎樣學習：

數據結構和算法是相輔相成的，要一起研究；
數據結構和算法對于嵌入式來說不全是重點，不要盲目的去研究這個；
一般在實際應用中，實現數據結構與算法的人和使用數據結構與算法的人是分開的。實際中有一部分人的工作就是研究數據結構和算法，并且試圖用代碼來實現這些算法（表現為庫）；其他做真正工作的人要做的就是理解、明白這些算法和數據結構的意義、優劣、特征，然后在合適的時候選擇合適的數據結構和算法來解決自己碰到的實際問題。