linux內核的設計與實現
① linux內核探索
對待知識領域，我們總喜歡去下一個定義。操作系統是我們每天工作都要使用的東西，由於現代商業操作系統的復雜性和沒有統一的標准，若對一個操作系統下定義並不能精確的描述操作系統所屬領域。根據經驗我們可以認為操作系統就是在整個應用系統中負責最基本功能和系統管理的那部分。包括內核、設備驅動程序、啟動引導程序、命令行Shell或者GUI界面、基本文件管理工具和系統工具。
嚴格的來講linux只是操作系統內核本身，廣義上的linux則常用來指基於linux內二的完整的操作系統，它包括GUI組件和其它許多工具。
GUI其實只是操作系統的表象，內核才是操作系統內在的核心。系統的其它部分必須依靠內核所提供的服務，像管理硬體設備、分配系統資源等，內核有時候被稱為管理者或者操作系統核心。
通常一個內核由負責響應中斷的中斷服務程序，負責進程調度的CPU調度程序，負責管理進程地址空間的內存管理程序以及網路、進程間通信等系統服務共同組成的。
內核在有安全機制的操作系統中不同於普通程序，一般處於系統態(內核態)，擁有受保護的內存空間和訪問硬體設備的所有許可權。這種系統狀態和被保護起來的內存空間，統稱為 內核空間 。
與內核空間相對的，用戶所執行的應用程序在用戶空間執行。用戶態的應用程序只能訪問允許它們使用的系統資源，並且只使用某些特定的系統功能，不能直接訪問硬體，也不能訪問內核劃分給其它應用程序的內存空間。
應用程序通過系統調用來和內核通信，當一個應用程序發起系統調用時，內核便代其執行。在這種情況下應用程序通過系統調用在內核空間運行，而內核被稱為運行在進程上下文中。應用程序通過系統調用進入內核空間時應用完成其工作的基本方式。
操作系統內核可分為兩大陣營：單內核和微內核。
單內核是一種較為簡單的設計，通常以單個靜態二進制文件存儲在磁碟中，整體上作為一個單獨的大過程，所有的內核服務都在這樣的一個大內核地址空間上運行。內核服務都處於內核態，並身處同一內核地址空間，之間可以幾乎無性能損耗的相互通信。
單內核具有簡單和高性能等特點。
微內核根據功能被分割成多個獨立的過程，每個過程都叫做一個伺服器。所有的伺服器都運行在各自的地址空間上（大部分處於用戶空間），只有強烈請求特權服務的伺服器才運行在特權模式下。
微內核伺服器之間不能直接調用函數通信，而是通過 消息傳遞 通信。系統採用進程間通信(IPC)機制，服務之間各自獨立，通過IPC互換消息，有效的避免了服務之間的失敗傳染。
IPC機制的開銷遠高於函數調用，而且在運行時還會牽扯到內核空間和用戶空間上下文切換，所以消息傳遞需要一些開銷。所以在內核的實際實現上大部分微內核的操作系統也會讓大部分的服務放置與內核中，這樣就可以直接調用函數，消除消息傳遞的開銷。
windows NT和Mach(Mac OS X)都是典型的微內核，不過在實際實現上，其所有服務都運行在內核空間。
linux是一個單內核，不過linux汲取了微內核的精華，並擁有模塊化設計、搶占式內核、支持內核線程以及動態裝載內核模塊等特性。
linux內核在設計時充分參考了已有的很多UNIX的內核實現，並且有一些創新方案。linux內核和傳統的UNIX系統之間存在一些顯著的差異：
本文的寫作和學習中參考了以下資料
1.《Linux Kenel Development ~ Thrid Edition 》
② 學習linux內核設計與實現需要哪些基礎，看不懂啊！好迷茫。
最早接觸inux是看了《linux操作系統實用教程》，98~99年的光景，學習了簡單的操作和內核編譯，那時候開始注意並學習內核。看的第一本是《Unix環境高級編程》，看了一部分沒看完，開始對
if(!(p=fork()))
{
…………
}
else
{
……
}
結構恨意很疑惑，這和一般的應用程序邏輯相背，因此想搞明白內核在干什麼，怎麼乾的。開始買了《操作系統設計與實現》，上下冊，下冊全是minix操作系統內核代碼。它和linux完全不同的，一個是微內核，一個單內核。即便看懂了minix,linux也要從頭看起，反之亦然。因此後來沒鑽進去。我看的第一本Linux內核書是李善平老師的《linux操作系統實驗教程》，當時市面上關於內核的書很少，這本是講2.0.35版的好像，似懂非懂。就開始邊看邊讀源代碼，間或看點操作系統原理的書，有不懂得在論壇上提問，這樣慢慢琢磨，就有點懂了。現在比當時好多了，很多內核的書，各方面剖析得很詳盡。不過要學懂，還是要：1、有好奇心和興趣 2、看書、讀代碼，這樣能夠比較懂。要進一步提高的話還要學會修改內核。有以下書籍可以參考：
1、《linux內核完全剖析》0.11版內核
2、《深入理解linux內核》(1、2、3版) ，3個版本分別對應2.2、2.4、2.6版的內核。
3、《linux內核源代碼情景分析》2.4.0版內核
4、《linux內核設計與實現》
5、《linux設備驅動程序》
③ linux內核同步問題
Linux內核設計與實現 十、內核同步方法
手把手教Linux驅動5-自旋鎖、信號量、互斥體概述
== 基礎概念： ==
並發 ：多個執行單元同時進行或多個執行單元微觀串列執行，宏觀並行執行
競態 ：並發的執行單元對共享資源（硬體資源和軟體上的全局變數）的訪問而導致的竟態狀態。
臨界資源 ：多個進程訪問的資源
臨界區 ：多個進程訪問的代碼段
== 並發場合： ==
1、單CPU之間進程間的並發 :時間片輪轉，調度進程。 A進程訪問列印機，時間片用完，OS調度B進程訪問列印機。
2、單cpu上進程和中斷之間並發 ：CPU必須停止當前進程的執行中斷;
3、多cpu之間
4、單CPU上中斷之間的並發
== 使用偏向： ==
==信號量用於進程之間的同步，進程在信號量保護的臨界區代碼裡面是可以睡眠的（需要進行進程調度），這是與自旋鎖最大的區別。==
信號量又稱為信號燈，它是用來協調不同進程間的數據對象的，而最主要的應用是共享內存方式的進程間通信。本質上，信號量是一個計數器，它用來記錄對某個資源（如共享內存）的存取狀況。它負責協調各個進程，以保證他們能夠正確、合理的使用公共資源。它和spin lock最大的不同之處就是：無法獲取信號量的進程可以睡眠，因此會導致系統調度。
1、==用於進程與進程之間的同步==
2、==允許多個進程進入臨界區代碼執行，臨界區代碼允許睡眠；==
3、信號量本質是==基於調度器的==，在UP和SMP下沒有區別；進程獲取不到信號量將陷入休眠，並讓出CPU；
4、不支持進程和中斷之間的同步
5、==進程調度也是會消耗系統資源的，如果一個int型共享變數就需要使用信號量，將極大的浪費系統資源==
6、信號量可以用於多個線程，用於資源的計數（有多種狀態）
==信號量加鎖以及解鎖過程：==
sema_init(&sp->dead_sem, 0); / 初始化 /
down(&sema);
臨界區代碼
up(&sema);
==信號量定義：==
==信號量初始化：==
==dowm函數實現：==
==up函數實現：==
信號量一般可以用來標記可用資源的個數。
舉2個生活中的例子：
==dowm函數實現原理解析：==
（1）down
判斷sem->count是否 > 0，大於0則說明系統資源夠用，分配一個給該進程，否則進入__down(sem);
（2）__down
調用__down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);其中TASK_UNINTERRUPTIBLE=2代表進入睡眠，且不可以打斷；MAX_SCHEDULE_TIMEOUT休眠最長LONG_MAX時間；
（3）list_add_tail(&waiter.list, &sem->wait_list);
把當前進程加入到sem->wait_list中；
（3）先解鎖後加鎖;
進入__down_common前已經加鎖了，先把解鎖，調用schele_timeout(timeout)，當waiter.up=1後跳出for循環；退出函數之前再加鎖；
Linux內核ARM構架中原子變數的底層實現研究
rk3288 原子操作和原子位操作
原子變數適用於只共享一個int型變數；
1、原子操作是指不被打斷的操作，即它是最小的執行單位。
2、最簡單的原子操作就是一條條的匯編指令(不包括一些偽指令，偽指令會被匯編器解釋成多條匯編指令)
==常見函數：==
==以atomic_inc為例介紹實現過程==
在Linux內核文件archarmincludeasmatomic.h中。 執行atomic_read、atomic_set這些操作都只需要一條匯編指令，所以它們本身就是不可打斷的。 需要特別研究的是atomic_inc、atomic_dec這類讀出、修改、寫回的函數。
所以atomic_add的原型是下面這個宏：
atomic_add等效於：
result（%0） tmp（%1） (v->counter)（%2） (&v->counter)（%3） i（%4）
注意：根據內聯匯編的語法，result、tmp、&v->counter對應的數據都放在了寄存器中操作。如果出現上下文切換，切換機制會做寄存器上下文保護。
（1）ldrex %0, [%3]
意思是將&v->counter指向的數據放入result中，並且（分別在Local monitor和Global monitor中）設置獨占標志。
（2）add %0, %0, %4
result = result + i
（3）strex %1, %0, [%3]
意思是將result保存到&v->counter指向的內存中， 此時 Exclusive monitors會發揮作用，將保存是否成功的標志放入tmp中。
（4） teq %1, #0
測試strex是否成功（tmp == 0 ？？）
（5）bne 1b
如果發現strex失敗，從（1）再次執行。
Spinlock 是內核中提供的一種比較常見的鎖機制，==自旋鎖是「原地等待」的方式解決資源沖突的==，即，一個線程獲取了一個自旋鎖後，另外一個線程期望獲取該自旋鎖，獲取不到，只能夠原地「打轉」（忙等待）。由於自旋鎖的這個忙等待的特性，註定了它使用場景上的限制 —— 自旋鎖不應該被長時間的持有（消耗 CPU 資源），一般應用在==中斷上下文==。
1、spinlock是一種死等機制
2、信號量可以允許多個執行單元進入，spinlock不行，一次只能允許一個執行單元獲取鎖，並且進入臨界區，其他執行單元都是在門口不斷的死等
3、由於不休眠，因此spinlock可以應用在中斷上下文中；
4、由於spinlock死等的特性，因此臨界區執行代碼盡可能的短；
==spinlock加鎖以及解鎖過程：==
spin_lock(&devices_lock);
臨界區代碼
spin_unlock(&devices_lock);
==spinlock初始化==
==進程和進程之間同步==
==本地軟中斷之間同步==
==本地硬中斷之間同步==
==本地硬中斷之間同步並且保存本地中斷狀態==
==嘗試獲取鎖==
== arch_spinlock_t結構體定義如下： ==
== arch_spin_lock的實現如下： ==
lockval（%0） newval（%1） tmp（%2） &lock->slock（%3） 1 << TICKET_SHIFT（%4）
（1）ldrex %0, [%3]
把lock->slock的值賦值給lockval；並且（分別在Local monitor和Global monitor中）設置獨占標志。
（2）add %1, %0, %4
newval =lockval +（1<<16）; 相當於next+1；
（3）strex %2, %1, [%3]
newval =lockval +（1<<16）; 相當於next+1；
意思是將newval保存到 &lock->slock指向的內存中， 此時 Exclusive monitors會發揮作用，將保存是否成功的標志放入tmp中。
（4） teq %2, #0
測試strex是否成功
（5）bne 1b
如果發現strex失敗，從（1）再次執行。
通過上面的分析，可知關鍵在於strex的操作是否成功的判斷上。而這個就歸功於ARM的Exclusive monitors和ldrex/strex指令的機制。
（6）while (lockval.tickets.next != lockval.tickets.owner)
如何lockval.tickets的next和owner是否相等。相同則跳出while循環，否則在循環內等待判斷；
* （7）wfe()和smp_mb() 最終調用#define barrier() asm volatile ("": : :"memory") *
阻止編譯器重排，保證編譯程序時在優化屏障之前的指令不會在優化屏障之後執行。
== arch_spin_unlock的實現如下： ==
退出鎖時：tickets.owner++
== 出現死鎖的情況： ==
1、擁有自旋鎖的進程A在內核態阻塞了，內核調度B進程，碰巧B進程也要獲得自旋鎖，此時B只能自旋轉。 而此時搶占已經關閉，（單核）不會調度A進程了，B永遠自旋，產生死鎖。
2、進程A擁有自旋鎖，中斷到來，CPU執行中斷函數，中斷處理函數，中斷處理函數需要獲得自旋鎖，訪問共享資源，此時無法獲得鎖，只能自旋，產生死鎖。
== 如何避免死鎖： ==
1、如果中斷處理函數中也要獲得自旋鎖，那麼驅動程序需要在擁有自旋鎖時禁止中斷；
2、自旋鎖必須在可能的最短時間內擁有
3、避免某個獲得鎖的函數調用其他同樣試圖獲取這個鎖的函數，否則代碼就會死鎖；不論是信號量還是自旋鎖，都不允許鎖擁有者第二次獲得這個鎖，如果試圖這么做，系統將掛起；
4、鎖的順序規則（a) 按同樣的順序獲得鎖；b) 如果必須獲得一個局部鎖和一個屬於內核更中心位置的鎖，則應該首先獲取自己的局部鎖 ;c) 如果我們擁有信號量和自旋鎖的組合，則必須首先獲得信號量；在擁有自旋鎖時調用down(可導致休眠)是個嚴重的錯誤的；）
== rw（read/write）spinlock： ==
加鎖邏輯：
1、假設臨界區內沒有任何的thread，這個時候任何的讀線程和寫線程都可以鍵入
2、假設臨界區內有一個讀線程，這時候信賴的read線程可以任意進入，但是寫線程不能進入；
3、假設臨界區有一個寫線程，這時候任何的讀、寫線程都不可以進入；
4、假設臨界區內有一個或者多個讀線程，寫線程不可以進入臨界區，但是寫線程也無法阻止後續的讀線程繼續進去，要等到臨界區所有的讀線程都結束了，才可以進入，可見：==rw（read/write）spinlock更加有利於讀線程；==
== seqlock（順序鎖）： ==
加鎖邏輯：
1、假設臨界區內沒有任何的thread，這個時候任何的讀線程和寫線程都可以鍵入
2、假設臨界區內沒有寫線程的情況下，read線程可以任意進入；
3、假設臨界區有一個寫線程，這時候任何的讀、寫線程都不可以進入；
4、假設臨界區內只有read線程的情況下，寫線程可以理解執行，不會等待，可見：==seqlock（順序鎖）更加有利於寫線程；==
讀寫速度 ： CPU > 一級緩存 > 二級緩存 > 內存 ，因此某一個CPU0的lock修改了，其他的CPU的lock就會失效；那麼其他CPU就會依次去L1 L2和主存中讀取lock值，一旦其他CPU去讀取了主存，就存在系統性能降低的風險；
mutex用於互斥操作。
互斥體只能用於一個線程，資源只有兩種狀態（佔用或者空閑）
1、mutex的語義相對於信號量要簡單輕便一些，在鎖爭用激烈的測試場景下，mutex比信號量執行速度更快，可擴展
性更好，
2、另外mutex數據結構的定義比信號量小;、
3、同一時刻只有一個線程可以持有mutex
4、不允許遞歸地加鎖和解鎖
5、當進程持有mutex時，進程不可以退出。
• mutex必須使用官方API來初始化。
• mutex可以睡眠，所以不允許在中斷處理程序或者中斷下半部中使用，例如tasklet、定時器等
==常見操作：==
struct mutex mutex_1;
mutex_init(&mutex_1);
mutex_lock(&mutex_1)
臨界區代碼；
mutex_unlock(&mutex_1)
==常見函數：==
=
④ Linux內核設計與實現的內容簡介
《Linux內核設計與實現(原書第3版)》主要內容包括：進程管理、進程調度、時間管理和定時器、系統調用介面、內存定址、內存管理和頁緩存、VFS、內核同步以及調試技術等。同時《Linux內核設計與實現(原書第3版)》也涵蓋了Linux 2.6內核中頗具特色的內容，包括CFS調度程序、搶占式內核、塊I/O層以及I/O調度程序等。《Linux內核設計與實現(原書第3版)》採用理論與實踐相結合的路線，能夠帶領讀者快速走進Linux內核世界，真正開發內核代碼。《Linux內核設計與實現(原書第3版)》適合作為高等院校操作系統課程的教材或參考書，也可供相關技術人員參考。
如果你是一名linux內核愛好者，本書的內容可以幫助你大顯身手。如果你是一名普通程序員，本書的內容將會拓寬你的編程思路。如果你初次接觸linux內核，本書則可以幫助你對內核各個核心子系統有一個整體把握。
本版新增內容
·增加一章專門描述內核數據結構
·詳細描述中斷處理程序
·擴充虛擬內存和內存分配的內容
·調試linux內核的技巧
·內核同步和鎖機制的深度描述
·提交內核補丁以及參與linux內核社區的建設性建議
