Linux內核
自旋鎖與互斥鎖：
對於自旋鎖來說，它只需要消耗很少的資源來建立鎖；隨後當線程被阻塞時，它就會一直重複檢查看鎖是否可用了，也就是說當自旋鎖處於等待狀態時它會一直消耗CPU時間。
對於互斥鎖來說，與自旋鎖相比它需要消耗大量的系統資源來建立鎖；隨後當線程被阻塞時，線程的調度狀態被修改，並且線程被加入等待線程隊列；最後當鎖可用 時，在獲取鎖之前，線程會被從等待隊列取出並更改其調度狀態；但是在線程被阻塞期間，它不消耗CPU資源。
因此自旋鎖和互斥鎖適用於不同的場景。自旋鎖適用於那些僅需要阻塞很短時間的場景，而互斥鎖適用於那些可能會阻塞很長時間的場景。
總結下自旋鎖的特點：
(1)單CPU非搶佔內核下：自旋鎖會在編譯時被忽略（因為單CPU且非搶佔模式情況下，不可能發生進程切換，時鐘只有一個進程處於臨界區（自旋鎖實際沒什麼用了）
(2)單CPU搶佔內核下：自選鎖僅僅當作一個設置搶佔的開關（因為單CPU不可能有並發訪問臨界區的情況，禁止搶佔就可以保證臨街區唯一被擁有）
(3)多CPU下：此時才能完全發揮自旋鎖的作用，自旋鎖在內核中主要用來防止多處理器中並發訪問臨界區，防止內核搶佔造成的競爭。
linux發生搶佔的時間
linux搶佔發生的時間，搶佔分為用戶搶佔和內核搶佔。
用戶搶佔在以下情況下產生：
1 從系統調用返回用戶空間
2 從中斷處理程序返回用戶空間
內核搶佔會發生在：
1 當從中斷處理程序返回內核空間的時候，且當時內核具有可搶佔性
2 當內核代碼再一次具有可搶佔性的時候（如：spin_unlock時）
3 如果內核中的任務顯示的調用schedule()
基本的進程調度就是發生在時鐘中斷後，並且發現進程的時間片已經使用完了，則發生進程搶佔。通常我們會利用中斷處理程序返回內核空間的時候可進行內核搶佔這個特性來提高一些I/O操作的實時性，如：當I/O事件發生的時候，對應的中斷處理程序被激活，當它發現有進程在等待這個I/O事件的時候，它 會激活等待進程，並且設置當前正在執行進程的need_resched標誌，這樣在中斷處理程序返回的時候，調度程序被激活，原來在等待I/O事件的進程 （很可能）獲得執行權，從而保證了對I/O事件的相對快速響應（毫秒級）。可以看出，在I/O事件發生的時候，I/O事件的處理進程會搶佔當前進程，系統 的響應速度與調度時間片的長度無關。
volatile：確保本條指令不會因編譯器的優化而省略，且要求每次直接讀值。
優化器在用到這個變數時必須每次都從內存重新讀取這個變數的值，而不是使用保存在寄存器里的備份。下面是volatile變數的幾個例子：
1）並行設備的硬體寄存器（如：狀態寄存器）
2）一個中斷服務子程序中會訪問到的非自動變數（Non-automatic variables)
3）多線程應用中被幾個任務共享的變數
當要求使用volatile 聲明的變數的值的時候，系統總是重新從它所在的內存讀取數據，即使它前面的指令剛剛從該處讀取過數據。而且讀取的數據立刻被保存。
volatile用在如下的幾個地方：
1、中斷服務程序中修改的供其它程序檢測的變數需要加volatile；
2、多任務環境下各任務間共享的標誌應該加volatile；
3、存儲器映射的硬體寄存器通常也要加volatile說明，因為每次對它的讀寫都可能有不同意義；
另外，以上這幾種情況經常還要同時考慮數據的完整性（相互關聯的幾個標誌讀了一半被打斷了重寫），在1中可以通過關中斷來實現，2 中可以禁止任務調度，3中則只能依靠硬體的良好設計了。
夥伴系統
cache
內存映射
MMU
虛擬內存
物理內存
應用進程空間
內核進程空間
virt_to_phys():實現內核虛擬地址轉化為物理地址, 轉換過程是將虛擬地址減去3G（PAGE_OFFSET=0XC000000）。
phys_to_virt():將內核物理地址轉化為虛擬地址。
get_free_page: 申請連續的物理內存空間, __get_free_pages是基於buddy機制實現的
free_page
kmalloc：申請連續的物理內存空間, 基於slab機制實現的
kfree
vmalloc：申請連續的虛擬內存空間, 基於slab機制實現的
vfree
kzalloc
kcalloc
malloc
slab：slab依然是以頁為單位進行映射，只是映射之後分割這些頁為相同的更小的單元，從而節省了內存。slab分配的單元不能小於32B或大於128K。
//創建slab對象
struct kmem_cache_t *xj_sbcache;
xj_sbcache = kmem_cache_create("xjslab",sizeof(struct xj_unit_t),0,SLAB_CACHE_DMA|SLAB_PANIC，NULL,NULL);
//分配slab緩存
struct xj_unit_t *xj_unit;
xj_unit = kmem_cache_alloc(xj_sbcache,GFP_KERNEL);
/* 使用slab緩存 */
//使用slab緩存
/* 釋放slab緩存 */
kmem_cache_free(xj_sbcache, xj_unit);
/* 銷毀slab緩存 */
kmem_cache_destroy(xj_sbcache);
內存池：內存池主要是用來解決可能出現的內存不足的情況，因為一個內存池在創建的時候就已經分配好了一內存，當我們用mempool_alloc向一個已經創建好的內存池申請申請內存時，該函數首先會嘗試回調內存池創建時的分配內存函數，如果已經沒有內存可以分配，他就會使用內存池創建時預先分配的內存，這樣就可以避免因為無內存分配而陷入休眠，當然，如果預分配的內存也已經使用完畢，還是會陷入休眠。slab機制的目的是提高內存使用率以及內存管理效率，內存池的目的是避免內存的分配失敗。
mempool_t *mempool_create()
void * mempool_alloc()
void mempool_free()
void mempool_destroy()
memcpy
memmove
硬體如果要和cpu進行通信有那麼幾種方法，其實有：程序查詢法，中斷，DMA，通道
DMA: DMA傳輸需要使用物理地址連續的內存塊
中斷基礎
（1）中斷的概念:指CPU在執行過程中，出現某些突發事件急待處理，CPU暫停執行當前程序，轉去處理突發事件，處理完後CPU又返回原程序被中斷的位置繼續執行
（2）中斷的分類:內部中斷和外部中斷
內部中斷:中斷源來自CPU內部(軟體中斷指令、溢出、觸發錯誤等)
外部中斷:中斷源來自CPU外部，由外設提出請求
（3）屏蔽中斷和不可屏蔽中斷:
可屏蔽中斷:可以通過屏蔽字被屏蔽，屏蔽後，該中斷不再得到響應
不可屏蔽中斷:不能被屏蔽
（4）向量中斷和非向量中斷:
向量中斷:CPU通常為不同的中斷分配不同的中斷號,當檢測到某中斷號的中斷到來後,就自動跳轉到與該中斷號對應的地址執行
非向量中斷:多個中斷共享一個入口地址。進入該入口地址後再通過軟體判斷中斷標誌來識別具體哪個是中斷
//也就是說向量中斷由軟體提供中斷服務程序入口地址，非向量中斷由軟體提供中斷入口地址
/*典型的非向量中斷首先會判斷中斷源，然後調用不同中斷源的中斷處理程序*/
軟體中斷
硬體中斷
內部中斷:中斷源來自CPU內部(軟體中斷指令、溢出、觸發錯誤等)
外部中斷:中斷源來自CPU外部，由外設提出請求
同步中斷——異常
非同步中斷
由於碰到了不能定義的指令(除以0)的時候，就中斷當前的指令去處理這些異常。為什麼稱之為同步中斷，因為它是與時鐘是同步的，如果理解的簡單的話同步中斷是軟體引起的，而非同步中斷是硬體引起的
中斷處理程序(ISR)
中斷上半部
中斷下半部
中斷上下文：中斷上下文和當前進程沒任何的關係，與current宏也沒有關係(儘管它還會指向中斷的進程)。因為進程沒有背景，所以中斷處理程序是不能睡眠的。這也對中斷處理程序中使用的函數做出了限制了。
進程上下文：是一種內核所處的操作模式，此時內核是代表這進程執行的。在進程上下文中可以通過current宏關聯到當前的進程。因為進程以進程上下文的形式連接到內核中的，所以可以在進程上下文可以睡眠，或者調用調度程序。
內核進程
進程通信
內核線程
工作隊列
Tasklet
內核文件系統
printk列印級別
kmsg文件
平衡二叉樹
紅黑樹
排序
冒泡排序：雞尾酒排序
簡單選擇排序
直接插入排序：二分插入排序、希爾排序
歸併排序
堆排序
快速排序
查找
順序查找
二分查找（折半查找）
插值查找
斐波那契查找
樹表查找
分塊查找
哈希查找：哈希表（散列表）
kernel:
The Linux Kernel Archives
busybox:
BusyBox
uboot:
http://www.denx.de/wiki/U-Boot/SourceCode
推薦閱讀：