Linux Kernel Development 學習

處理器的活動可以分為3類：

運作于使用者空間，執行使用者程序

運作于核心空間，處于程序上下文，代表某個特定的程序進行

運作于核心空間，處于中斷上下文，與任何程序都無關，處理某個特定的中斷

包含了所有情況，邊邊角角也不例外。例如CPU空閑時，核心就運作一個空程序，處于程序上下文，但運作于核心空間

微核心架構（Micro kernel）和單核心架構（Monolithic kernel）的差別。

－－微核心——

最常用的功能被設計在核心模式（x86上為 0權限下），其他不怎麼重要的功能都作為單獨的程序運作在使用者模式下（3權限下），通過

消息傳遞進行通訊（windows采用程序間通信IPC機制，IPC（Inter Process Communication） 最基本的思想是盡量的小，通常微核心隻

包括程序排程，記憶體管理和程序間通信這幾個基本功能。

好處：增加了靈活性，易于維護，易于移植。其他的核心功能子產品都隻依賴于微核心子產品和其他子產品，并不直接依賴硬體。

由于子產品化設計，不包含在微核心内的驅動程式可以動态的加載或者解除安裝。

還具有的好處就是實時性、安全性較好，并且更适合于建構分布式作業系統和面向對象作業系統。

典型的作業系統中例子：Mach（非原生的分布式作業系統，被應用在Max OS X上）、IBM AIX、BeOS以及Windows NT

－－單核心－－

單核心是個很大的程序，内部又被分為若幹的子產品（或層次，或其他），但在運作時，是一個單獨的大型二進制映像／因為在同一個程序

内，其子產品間的通訊是通過直接調用其他子產品中的函數實作的，而不是微核心中多個程序間的消息傳遞，運作效率上單核心有一定的好處。

典型的作業系統中的例子：大部分Linux、包括BSD在内的所有Linux（編譯過 Linux的人知道Linux核心有數十MB）

即：

IPC機制的開銷多于函數調用，又因為會涉及核心空間與使用者空間的上下文切換，是以消息傳遞需要一定的周期，而單核心中的函數調用則沒有這些開銷。

結果實際上基于微核心的系統都讓大部分或者全部伺服器位于核心，這樣可以直接調用函數，消除頻繁的上下文切換。

Linux與傳統Unix不同的地方：

1. Linux支援動态的加載核心子產品。雖然是單核心的， 但是允許在需要的時候動态地解除安裝和加載部分核心代碼。

2. Linux支援對稱多處理（SMP）機制，傳統的Unix并不支援這種機制。

3. Linux核心可搶占。Linux核心具有允許在核心運作的任務優先執行的能力。

4.Linux對線程的支援：并不區分線程和其他的一般程序。

核心配置要麼是2選1，要麼是3選1：

2選1就是yes或no，3選1的話為yes, no和module

module代表被標明，但編譯時這部分的功能實作代碼是子產品，yes選項代表把代碼編譯進主核心子產品中，而不是作為一個子產品。

驅動程式一般選用3選1的配置。

Linux輸出重定向：

> 直接把内容生成到指定檔案，會覆寫源檔案中的内容，還有一種用途是直接生成一個空白檔案，相當于touch指令
>> 尾部追加，不會覆寫掉檔案中原有的内容

      

make程式能把編譯過程拆分成多個并行的作業。其中每個作業獨立并發的運作，這有助于極大地加快多處理器系統上的編譯過程，也有利于改善處理器的使用率。

内聯函數的定義： inline int add_int(int x, int y, int z){return x+y+z};

通常将對時間要求比較高，本身長度比較短的函數定義成内聯函數。若函數較大且會被反複調用，不贊成定義為内聯函數。

在程式中，調用其函數時，該函數在編譯時被替代（即将調用表達式用内聯函數體來替換），而不是在運作時被調用。

要注意：内聯函數内不允許用循環和開關語句。

有意思：#define MAX(a, b) (a) > (b) ? (a) : (b)

如果你在代碼中這樣寫：

int a = 10, b = 5;

// int max = MAX(++a, b); // a自增了兩次

// int max = MAX(++a, b+10); // a自增了一次

程序管理：

每個線程都有一個獨立的程式計數器，程序棧和一組程序寄存器。

核心排程的對象是線程。

－－程序描述符和任務結構－－

進城的清單放在任務隊列（task list）的雙向循環連結清單中，每一項的結構都是task_struct，稱為程序描述符的（process discriptor）結構，包含一個具體程序的所有資訊。

task_struct相對較大，32位機器上大約有1.7KB，包括：所打開的檔案，挂起的信号，程序的狀态等

Linux通過slab配置設定器配置設定task _struct結構，各個程序的task _struct存放在核心棧的尾端，隻需在棧底（對于向下增長而言）建立一個新的結構 　struct thread_info  （這個結構使得彙編中計算其偏移變得十分容易）

核心中大部分處理程序的代碼都是直接通過 task_struct 進行的。PowerPC中目前的 task_struct 專門儲存在一個寄存器中，x86需要在尾端建立 thread_info 來計算偏移間接查找 task_struct 結構。

系統調用和異常處理程式是對核心明确定義的接口。程序隻有通過這些接口才能陷入核心執行——對核心的通路都需要經過這些接口。

核心經常需要在背景執行一些操作，這種任務可以通過核心線程（kernel thread）完成——獨立運作在核心空間的标準程序。和不同程序的差別在于：沒有獨立的位址空間（指向位址空間的mm指針被定為NULL），隻在核心空間運作，從來不切換到使用者空間中去。核心程序和普通程序一樣，可以被排程和搶占。

程序的終結發生在程序調用exit（）系統調用，可能顯式調用，也可能從某個程式的主函數傳回。

在删除程序描述符之前，程序存在的唯一目的就是向父程序提供資訊。

即程序終結時所需的清理工作和程序描述符的删除被分開執行。

最後的工作為從任務清單中删除此程序，同時釋放程序核心棧和thread_info所占的頁，并且釋放task_struct所占的slab高速緩存。

在為沒有父程序的子程序尋找父程序時使用的兩個連結清單：子程序連結清單和ptrace子程序連結清單

當一個程序被跟蹤時，臨時父親會被設定為調試程序。如果此時他的父程序退出了，則系統會子程序和其兄弟找一個新的父程序。

以前處理這個過程需要周遊系統來尋找子程序，現在在一個單獨的被ptrace跟蹤的子程序連結清單中搜尋相關的兄弟程序——用兩個較小的連結清單減輕了周遊帶來的消耗。

程序排程：

多任務系統分為兩類：非搶占式多任務（cooperative multitasking）和搶占式多任務（preemptive multitasking）

搶占式：程序被搶占之前能夠運作的時間是設定好的，叫做程序的時間片（timeslice）

非搶占式：程序主動挂起自己的操作稱為讓步（yielding）

Linux的2.5版本排程稱為O(1),但其對于排程那些響應時間敏感的程式卻有一些先天的不足，這些程式稱為互動程序。2.6版本為了提高對互動程式的排程性能引入了新的程序排程算法，最為著名的是“反轉樓梯最後期限排程算法”（Rotating Staircase Deadline scheduler）（RSDL），此算法吸收了隊列理論，将公平排程的概念引入了Linux排程程式。此刻完全替代了O(1)排程算法，被稱為“完全公平排程算法”，或者簡稱CFS。

－－政策－－

I/O消耗型和處理器消耗型的程序：

前者指的是程序的大部分時間都用來送出I/O請求或者是等待I/O請求。這樣的程序經常處于可運作狀态，但是都是運作短短的一會，因為等待請求時總會阻塞。

後者把時間用在執行代碼上，除非被搶占，通常都一直不斷的運作。從系統響應速度考慮，排程起不應該經常讓它們運作，政策通常是降低排程頻率，同時延長運作時間。（極限例子是無限循環的執行）

排程政策通常需要在兩者間找到平衡：程序響應迅速（響應時間短）和最大系統使用率（吞吐量）

總結：一個是等待I/O，一個是數學計算，Linux傾向于優先排程I/O消耗型

程序優先級：

Linux采用兩種優先級

1. nice值。範圍從－20到＋19，值越大優先級越低
2. 實時優先級。從0到99，包括0和99，數值越高優先級越高

實時優先級和nice優先級處于互不相交的兩個範疇，任何實時程序的優先級都高于普通的程序。

一般情況下預設的時間片都很短，通常為10ms。但是Linux的CFS排程器并沒有直接配置設定時間片到程序，而是将處理器的使用比劃分給了程序。這個比例還會受到nice值的影響，nice值作為權重将調整程序所使用的處理器時間使用比。同時Linux中的搶占時機也取決于新的可運作程式消耗了多少處理器使用比。若比目前程序小，則立即投入，搶占目前程序，否則推遲。

通過文本編輯和視訊處理例子了解處理器使用比！

－－Linux排程算法－－

Linux的排程器是以子產品方式提供的，允許不同類型的程序有針對性的選擇排程算法。

這種子產品化結構稱為排程器類（scheduler classes）。基礎的排程器會按照優先級順序周遊排程類

完全公平排程（CFS）是一個針對普通程序的排程類，在Linux中稱為SCHED_NORMAL（POSIX中稱為SCHED_OTHER）

基于nice值的排程算法可能出現的問題：

1.程序切換無法最優化：兩個同等低優先級的程序均隻能獲得很短的時間片，需要進行大量上下文切換

2.根據優先級不同，獲得的處理器時間差異很大（99和100差1，1和2也差一，但是2倍）

3.涉及到時間片的映射，需要配置設定一個絕對時間片，時間片也可能會随着定時器節拍的改變而改變。

4.優化喚醒時打破公平原則，獲得更多處理器時間的同時，損害其他程序的利益

公平排程：

每個程序能獲得1/n的處理器時間－－n指的是可運作程序的數量。

不再采取給每個程序時間片的做法，而是在所有可運作程序的總數基礎上計算一個程序應該運作多久。不依靠nice來計算時間片，而是計算作為程序獲得的處理器運作比的權重。nice低，權重高

CFS為無限小小排程周期的近似值設定了目标，稱為“目标延遲”

小的排程周期帶來了好的互動性，但是必須承受高的切換代價和更差的系統總吞吐能力

假設目标延遲為20ms，若有2個相同優先級的任務，每個運作10ms，4個則為5ms

當任務趨于無限的時候，處理器使用比趨于0，為此引入了時間片底線，稱為“最小粒度”，預設1ms

即可運作程序的數量趨于無限時，每個程序最少獲得1ms的運作時間

CFS中幾個重要概念：

1. nice值越小，程序的權重越大。同時nice值的相差使得權重間程倍數關系。

2. CFS排程器的一個排程周期值是固定的，由sysctl_sched_latency變量儲存。

3. 程序在一個排程周期中的運作時間為：

配置設定給程序的運作時間 ＝ 排程周期 ＊ 權重 ／ 所有程序的權重之和

    即權重越大，配置設定到的時間越多

4. 一個程序的實際運作時間和虛拟時間（vruntime）的關系

vruntime ＝ 實際運作時間 ＊ NICE_0_LOAD（1024）／ 程序權重

    程序權重越大，運作相同的實際時間，vruntime增長的越慢

5. 一個程序在一個排程周期内的虛拟運作時間大小代入前兩式可得

vruntime ＝ 排程周期 ＊ 1024 ／ 所有程序程序權重（定值！！）

    即所有程序的vruntime都是一樣的。

http://blog.csdn.net/liuxiaowu19911121/article/details/47070111

6. 紅黑樹中均為可執行的程序，若标記為休眠狀态，則從樹中移出。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

核心通過need_resched辨別來表明是否需要重新執行一次排程。每個程序都包含有這個标志，因為通路程序描述符内的數值比通路一個全局變量快（因為current宏速度很快并且描述符通常都在高速緩存中）

使用者搶占發生在：

1. 從系統調用傳回使用者空間時
2. 從中斷處理程式傳回使用者空間時

核心搶占：

隻要沒有鎖，核心就可以進行搶占。

通過設定thread_info中的preempt_count計數器，有鎖的時候加1，釋放－1，數值為0的時候核心可以進行搶占。

核心搶占發生在：

1. 中斷處理程式在執行，且傳回核心空間之前
2. 核心代碼再一次具有可搶占性的時候
3. 核心任務顯示調用schedule()
4. 核心中的任務阻塞（導緻調用schedule()）

Linux中的實時排程政策：SCHED_FIFO和SCHED_RR，非實時的排程政策時SCHED_NORMAL

實時政策并不被CFS管理，而是用一個特殊的實時排程器管理

SCHED_FIFO不是用時間片，可運作态的SCHED_FIFO比任何SCHED_NORMAL都先得到排程

隻要其在運作，較低級别的程序隻有等待其變成不可運作狀态後才有機會執行。

SCHED_RR是帶有時間片的SCHED_FIFO，隻有消耗事先配置設定的時間片後就不能繼續執行

實時優先級範圍從0－99，SCHED_NORMAL程序的nice值共享了這個取值空間，即其－19到20為100到139的實時優先級範圍

Linux 的5個段：

BSS段：(bss segment) 通常用來存放程式中未初始化的全局變量的一塊記憶體區域。BSS是Block Started by Symbol 的簡稱，BSS段屬于靜态記憶體配置設定。

資料段：(data segment)：通常用來存放程式中已初始化的全局變量的一塊記憶體區域，屬于靜态配置設定

代碼段：(code segment)：通常指的是存放程式執行代碼的一塊記憶體區域。區域的大小在程式執行前就已經确定，記憶體區域屬于隻讀。（某些架構支援可寫，即允許修改程式）

堆：(heap)：用于存放程序運作中被動态配置設定的記憶體段，大小不确定，可以動态的擴張或縮減。調用malloc等函數配置設定記憶體時，新配置設定的記憶體被動态添加到堆上；free程式釋放記憶體時，被釋放的記憶體從堆中被剔除。(堆的位置在BSS的後面，并從其後開始增長)

棧：(stack)：使用者存放程式臨時建立的變量，即函數｛｝中存放的變量（但不包括static聲明的變量，其存放在資料段中）；同時函數被調用時，參數也會被壓入被調用的程序棧中。是由作業系統配置設定的，記憶體的申請和回收都由OS管理。

PS：

bss段（未手動初始化的段）并不給該段配置設定空間，隻是記錄資料所需空間的大小

data段（已手動初始化的資料）為資料配置設定空間，資料段包括經過初始化的全局變量以及它們的值。BSS的大小可以從可執行檔案中得到，然後連結器得到這個大小的記憶體塊，緊跟在資料段後面。包括資料塊和BSS段的整個區段成為資料區。

定時器和時間管理：

預設的系統定時器頻率根據體系結構的不同會有所不同，但基本上都是100HZ

更高的時鐘中斷頻度和更高的準确度使得依賴定時值執行的系統調用，譬如poll(), select()能夠以更高的精度運作；對諸如資源消耗和系統運作時間的測量會有更精細的解析度；提高程序搶占的準确度。

劣勢在于：時鐘中斷的頻率越高，系統的負擔越重，中斷處理程式占用的處理器的時間越多。

jiffies：全局變量jiffies用來記錄自系統啟動以來産生的節拍的總數。啟動時，核心将該變量初始化為0，此後每次時鐘中斷處理程式就會增加改變該變量的值。

把時鐘作為秒經常會用在核心和使用者空間程序互動的時候：

unsigned long next_stick ＝ jiffies ＋ 5 ＊ HZ     ／＊從現在開始5s＊／

注意：jiffies的類型為無符号長整形（unsigned long）（32位），用其他任何類型存放它都不正确

jiffies的回繞（wrap around），超過最大範圍後就會發生溢出。

核心提供了4個宏來幫忙比較節拍計數。

#define time_after(unknown, known)   ——   ( (long)(known) - (long)(unknown) < 0 )

#define time_before(unknown, known)   ——   ( (long)(unknown) - (long)(known) < 0 )

其中

time_after(unknown, known)當unknown超過指定的known時，傳回真，否則傳回假；

time_before相反 

實時時鐘（RTC）用來持久存放系統時間的裝置。在PC體系結構中，RTC和CMOS內建在一起，而且RTC的運作和BIOS的儲存設定都是通過同一個電池供電的。RTC最主要的作用是啟動時初始化xtime變量。

牆上時間代表了目前的實際時間。

核心對于程序進行時間計數時，時根據中斷發生時處理器所處的模式進行分類統計的。

x86機器上時鐘中斷處理程式每秒執行100次或者1000次

定時器結構由timer_list表示，核心提供了一組和定時器相關的接口來簡化定時器操作，并不需要深入了解其資料結構：

建立時定義：struct timer_list my_timer;

初始化定時器資料結構内部的值

init_timer(&my_timer);

填充資料結構中的值：

my_timer.expires = jiffies + delay; 

my_timer.data = 0;

my_timer.function = my_function;

data參數可以利用同一個處理函數注冊多個定時器

最後激活定時器：

add_timer(&my_timer);

－－延時執行的方法－－

1.忙等待：

　　unsigned long timeout = jiffies + 10;

　　while (time_before(jiffies, timeout))

　　　　　　　　　　;

處理器隻能原地等待，不會去處理其他任務，是以基本不采用此方法。

2.更好的方法應該是在等待時允許核心重新排程執行其他任務：

　　unsigned long delay = jiffies + 5*HZ;

　　while(time_before(jiffies,delay))

　　cond_resched();

cond_resched()函數講排程一個新程式投入運作，但隻有設定完成need_resched标志才能生效

另外由于其需要調用排程程式，是以不能在中斷上下文中使用－－隻能在程序上下文中使用。

我們要求jiffies在每次循環時都必須重新裝載，因為在背景jieffies會随着時鐘中斷的發生而不斷增加。為了解決這個問題，<linux/jiffies.h>中的jiffies變量被标記為關鍵字volatile， 訓示編譯器在每次通路變量時都能重新從主記憶體中獲得，而不是通過寄存器中的變量别名來通路，進而確定循環中的jieffies每次被讀取都會重新載入。

短延遲

jiffies的節拍間隔可能超過10ms，不能用于短延遲。

核心提供了3個延遲函數，void udelay(), void ndelay() 以及void mdelay()。

系統調用：

核心提供了使用者程序與核心進行互動的一組接口，應用程式提供各種請求，而核心負責滿足這些請求。

作用：

1. 為使用者空間提供了一種硬體的抽象接口。例如讀寫檔案時無需考慮磁盤類型和媒體等
2. 保證了系統的安全和穩定。核心可以基于權限，使用者類型等對通路進行裁決

Linux 中，系統調用是使用者空間通路核心的唯一手段；除異常和陷入外，它們是核心唯一的合法入口。

應用程式通過使用者空間實作的應用程式設計接口（API）而不是直接通過系統調用來程式設計

一個API定義了一組應用程式使用的程式設計接口，可通過一個或多個甚至不使用系統調用來實作

Unix接口設計格言：提供機制而非政策

機制：mechanism（需要提供什麼樣的功能） 政策：policy（怎麼實作這樣的功能）

－－系統調用－－

線程組leader的PID（也就是線程組中頭一個輕量級線程的PID）被線程共享，儲存在thread_info->tgid中。 getpid()傳回tgid的值，而不是PID值。對thread group leader來說，tgid = pid

Linux中每個系統調用被賦予一個系統調用号。系統調用号一旦配置設定就不能再有任何變更；如果被删除，占用的系統号也不允許被回收利用。

系統中所有注冊過的系統調用，儲存在sys_call_table中。

系統調用的性能：Linux 的系統調用比其他許多作業系統執行的要快。Linux很短的上下文切換時間是一個重要原因；同時系統調用處理程式和每個系統調用本身也都非常簡潔。

用關空間的程式無法直接執行核心代碼，需要通知核心自己需要執行一個系統調用。

實作方法是軟中斷：通過引發一個異常來促使系統切換到核心态去執行異常處理程式，此時的異常處理就是系統調用處理程式。

x86系統上預定義的軟中斷是中斷号128，處理程式的名字叫system_call()

同時系統調用号是通過eax寄存器傳遞給核心的。

寫系統調用時，要時刻注意可移植性和健壯性。

參數驗證：系統調用在核心空間執行，如果有不合法的輸入傳遞給核心，系統的安全和穩定将面臨極大的考驗。

與I/O相關的系統調用必須檢查檔案描述符是否有效，與程序相關的函數必須檢查提供的PID是否有效。程序不應當讓核心去通路那些它無權通路的資源。

最重要的檢查是檢查使用者提供的指針是否有效，核心必須保證：

• 指針指向的記憶體區域屬于使用者空間，不允許讀取核心空間的資料
• 指針指向的記憶體區域在程序的位址空間裡。絕不能哄騙核心去讀其他程序的資料
• 如果為讀／寫／執行，該記憶體應該被标記為可讀／可寫／可執行。不能繞過記憶體通路限制

核心提供了兩個方法來完成必須的檢查，以及核心空間和使用者空間之間資料的來回拷貝。

1.寫資料提供了copy_to_user()，讀資料提供了copy_from_user()

均需要三個參數，程序空間中的記憶體位址，核心空間的原位址，需要拷貝的資料長度（位元組數）

2.最後一項檢查是否具有合法權限。

老版本Linux核心需要超級使用者權限的系統調用來調用suser()函數來完成檢查。（這個函數隻檢查是否為超級使用者）

新的系統允許檢查針對特定資源的特殊權限：

調用者可以使用capable()函數來檢查是否有權能對指定的資源進行操作，傳回非0則有權操作，傳回0則無權操作。

例如capable(CAP_SYS_NICE)可以檢查調用者是否有權改變其他程序的nice值。

參見<linux／capability.h>，其中包含一份所有這些權能和其對應的權限的清單。

建立一個新的系統調用十分容易，但是不提倡這麼做。

替代方法：實作一個裝置節點，對此實作read()和write()。使用ioctl()對特定的設定進行操作或者對特定的資訊進行檢索。

核心資料結構：

1.連結清單資料結構

Linux核心方式與衆不同，它不是将資料結構塞傳入連結表，而是将連結清單節點塞入資料結構！

即将現有的資料結構改造成連結清單，通過塞傳入連結表節點！

核心提供的連結清單操作例程，比如list_add()方法加入一個新節點到連結清單中。這些方法都有一個特點：隻接受list_head結構作為參數

使用宏container_of()我們可以很友善地從連結清單指針找到父結構中包含的任何變量。因為C語言中，一個給定結構的變量偏移在編譯時位址就被ABI固定下來了。

使用container，定義list_entry()，就可以傳回包含list_head的父類型的結構體

同時核心提供了建立，操作以及其他連結清單管理的各種例程。

核心連結清單的特性在于，所有的struct節點都是無差别的－－每一個包含一個list_head()，即可以從任何一個節點周遊連結清單。不過有時需要一個特殊指針索引。

核心提供的函數都是用C語言以内聯函數的方式實作的，原型存在于檔案<linux／list.h>

指向一個連結清單結構的指針通常是無用的；我們需要的是一個指向包含list_head的結構體的指針。

2.隊列

Linux核心通用隊列實作稱為kfifo，提供兩個主要的操作：enqueue(入隊列)和dequeue(出隊列)

kfifo對象維護了兩個偏移量：入口偏移和出口偏移

入口偏移指的是入隊列的位置，出口偏移指的是出隊列的位置。

出口偏移總是小于入口偏移。

enqueue操作拷貝資料到入口偏移位置，動作完成後，入口偏移加上推入的元素數目；

dequeue操作從隊列出口偏移拷貝資料，動作完成後，出口偏移減去摘取的元素數目。

－－建立隊列－－

動态建立：

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t, gfp_mask);

該函數會初始化一個大小為size的kfifo，核心使用gfp_mask辨別配置設定隊列，成功傳回0，失敗傳回錯誤碼

struct kfifo fifo;

int ret;

ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);

if ( ret )

return ret;

若自己想配置設定緩沖，可以調用：

void kfifo_init(struct knife *fifo, void *buffer, unsigned int size);

該函數建立并初始化一個kfifo對象，它将使用由buffer指向的size位元組大小的記憶體，對于kfifo_alloc()和kfifo_init()，size必須是2的幂

轉載于:https://www.cnblogs.com/lzhdcyy/p/6554884.html