linux核心基礎層的學習（1）

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/45072905

一：核心基礎層資料結構

1：雙向連結清單list

a）：連結清單的定義

struct list_head{
 struct list_head *next,*pre;
 }           

b）：container對象和list_entry

#define container_of(ptr,type,member){  \
    const typeof(((type *)0->member) *_mptr = (ptr); \
    (type*)((char*)_mptr-offset(type,member));})           

#define list_entry(ptr,type,member) \
    container_of(ptr,type,member)           

對雙向連結清單的詳細介紹請參考我的部落格：

linux核心list.h的學習

2：hash連結清單

a）：定義

struct hlist_head{
    struct hlist_head *first;
}           

b）:hash連結清單庫

與list相同

請參考下面文章的後面部分就是hash連結清單的内容：

3：紅黑樹

a）：實質上是自平衡二叉樹

b）：定義在rbtree.c檔案中（靜待部落格更新，對rbtree的介紹）

c）：應用場景

主要用在記憶體管理，IO排程算法等實作了紅黑樹

4：radix輸–基樹

a）：定義在/lib/radix_tree.c中

b）：radix樹是一種空間換時間的資料結構，通過空間的備援減少了時間上的消耗

（靜待部落格更新，對radix_tree的介紹）

c）：page cache的管理使用了radix tree

二：核心基礎層的同步機制

1：自旋鎖

a）：作用

（1）：如果資料未鎖，那麼就擷取鎖并運作，如果資料已鎖，那麼就一定旋轉（其實是反複執行一條指令）

（2）：單處理器環境（非搶占式核心）下，自旋鎖其實不起作用

（3）：單處理器，搶占式核心環境下，自旋鎖起的作用就是禁止搶占

b）：自旋鎖的調用

（1）：spin_lock

（2）：spin_unlock

2：核心信号量

a）：定義在檔案semaphore.h檔案裡

b)：semaphore和mutex

（1）：sema_init：計數可以為多

（2）：init_mutex：計數為1的信号量

c）：信号量的操作

（1）：up：釋放信号量

（2）：down：擷取信号量，如果不能擷取，則進入睡眠狀态

（3）：down_trylock：擷取信号量，如果不能擷取則立即傳回，程序不進入睡眠狀态

注意：

自旋鎖和信号量的差別

1：自旋鎖可以用在中斷處理函數和tasklet等不可睡眠的場景，而信号量不行

2：可睡眠的場景既可以使用信号量，也可以使用自旋鎖，自旋鎖通常用在輕量級場景

3：同步機制–原子變量

a）：原子變量提供了一種原子的資料結構，對這種資料結構的讀寫不可被細分和打斷

b）：原子變量提供的調用

（1）：atomic_add：加一個整數到原子變量

（2）：automic_sub：從原子變量減去一個整數

（3）：automic_set：設定原子變量的數值

（4）：automic_read：讀取原子變量的數值

4：同步機制–completion

a）：completion提供了一種等待完成的機制

b）：提供的調用

（1）：wait_for_completion：等待操作完成

（2）：complete：完成的信号

5：其他核心同步機制

a）：CPU變量 DEFINE_PER_CPU

b）：RCU鎖

c）：順序鎖