Linux內核奔跑卷

在閱讀本書之前，請讀者用兩小時來完成Linux內核奔跑卷，對Linux內核了解程度做簡要的了解。奔跑卷僅僅是Linux內核知識的娛樂游戲節目，希望能給讀者帶來一絲樂趣，套用國內某個科技圈里知名人士的名言“不服，來跑個分吧！”。

下面一共20道大題目，每道大題目10分，一共200分，讀者可以邊閱讀內核源代碼邊做題目，請在兩小時內完成。如沒有特殊說明，本奔跑卷基于Linux 4.0內核和ARM32/ARM64體系架構。

1．請簡述在你所熟悉的處理器中（比如雙核\2ortex-A9）一條存儲讀寫指令的執行全過程。

2．在一個32KB的4路組相聯的cache中，其中cache line為32Byte，請畫出這個cache組相聯的結構圖。

3．內核的一級頁表和二級頁表存放在什么地方？用戶進程的一級頁表和二級頁表分別存放在什么地方？

4．關于伙伴系統的幾個小問題：

? 系統初始化時，物理內存頁面是如何添加到伙伴系統中的？

? 系統運行時間長了物理內存會出現碎片化，伙伴系統如何避免物理內存的碎片化？

5．關于物理頁面內存分配器的幾個小問題：

? 請簡述Linux內核在理想情況下頁面分配器（page allocator）是如何分配出連續物理頁面的？

? 如何從分配掩碼中確定可以從哪些zone中分配內存？

? 頁面分配器是按照什么方向來掃描zone的？

6．關于slab分配器幾個小問題：

? slab分配器是如何分配和釋放小內存塊的？

? slab分配器中有一個著色的概念（cache color），著色有什么作用？

? slab分配器中的slab對象有沒有根據per-cpu做一些優化，為什么？

7．用戶進程使用malloc()來分配10個page大小的內存，請問內核是否馬上分配物理內存？請描述malloc()在內核空間的實現過程。

8．關于struct page數據結構的幾個小問題：

? struct page數據結構中的_count和_mapcount有什么區別？

? 匿名頁面和文件緩沖頁面有什么區別？

? trylock_page()和lock_page()有什么區別？

9．關于頁面回收的幾個小問題：

? LRU鏈表如何知道page的活動頻繁程度？

? kswapd是按照什么方向來掃描zone的？

? 內核有哪些頁面會被kswapd寫回到交換分區？

? 當page加入到lru鏈表中，被其他線程釋放了這個page，那么lru鏈表如何知道這個page已經被釋放了？

10．關于內存管理的幾個重要的數據結構的關系，如mm、vma、page、vaddr、paddr：

? 如何由mm數據結構和虛擬地址vaddr找到對應的VMA？

? 如何由page和VMA找到虛擬地址vaddr?

? 如何由page找到所有映射的VMA？

? 如何由VMA和虛擬地址vaddr，找出相應的page數據結構？

11．關于缺頁中斷和虛擬內存的幾個小問題：

? 如果用戶進程使用只讀屬性（PROT_READ）來mmap映射一個文件到用戶空間，然后使用memcpy來寫這段內存空間，會是什么樣的情況？

? 如果多個VMA的虛擬頁面同時映射了同一個匿名頁面，那么此時page->index應該等于多少？

12．關于進程的幾個小問題：

? 在內核中如何獲取當前進程的task_struct數據結構？

? 下面小代碼片段里，最后會打印出什么？

    int main(void)
    {
        int i;
        for(i=0; i＜2; i++){
              fork();
              printf("-\n");
        }
              wait(NULL);
              wait(NULL);
              return 0;
    }

? 優先級、nice和權重之間有什么關系？

13．關于CFS調度器的幾個小問題：

? 請簡述CFS調度器是如何工作的？

? vruntime是如何計算的？

? min_vruntime有什么作用？

? 對新創建的進程和剛喚醒的進程有何關照？

14．關于SMP負載均衡的幾個小問題：

? 普通進程的平均負載load_avg_contrib是如何計算的？runnable_avg_sum和runnable_avg_period是什么含義？

? 一個4核處理器里每個物理CPU核有獨立L1 cache并且只有一個線程，分成兩個簇cluster0和cluster1，每個簇包含兩個物理CPU核，簇中的CPU核共享L2 cache。請畫出該處理器在Linux內核里調度域和調度組的拓撲關系圖。

15．關于spinlock的幾個小問題：

? 為什么spinlock的臨界區不能睡眠（不考慮RT-Linux的情況）？

? 如果在spin_lock()和spin_unlock()的臨界區中發生了中斷，并且中斷處理程序恰巧也修改了該臨界資源，那么會發生什么后果？如何避免？

? Ticket-based的spinlock機制是如何實現的？有什么優缺點？

16．讀寫信號量使用的自旋等待機制（optimistic spinning）是如何實現的？

17．關于RCU的幾個小問題：

? 請解釋Quiescent State和Grace Period？

? 在mm/oom_kill.c的select_bad_process()函數中為什么要使用rcu_read_lock()？什么時候注冊RCU回調函數呢？

18．關于中斷的幾個小問題：

? 硬件中斷號和Linux內核的IRQ中斷號是如何映射的？

? 一個硬件中斷發生之后，Linux內核是如何響應并處理該中斷的？

? 為什么說中斷上下文不能執行睡眠操作？

19．關于軟中斷的幾個小問題：

? 軟中斷回調函數的執行過程中是否允許響應本地中斷？

? 同一類型的軟中斷是否允許多個CPU并行執行？

? 是否允許同一個Tasklet在多個CPU上并行執行？

20．關于workqueue的幾個小問題：

? workqueue是運行在中斷上下文，還是進程上下文？其回調函數允許睡眠嗎？

? 如果有多個work掛入到一個工作線程中執行，當某個work的回調函數執行了阻塞操作，那么剩下的work該怎么辦？

答案：

奔跑卷的答案都分布在本書的各個章節。

如果答對了90%以上，那么恭喜您，您是深入了解Linux內核的高手，本書可能不適合您，不過您可以轉給身邊有需要的小伙伴。

如果答對了30%以上，那么您對Linux內核有一定的了解，當然本書也適合您繼續深入了解。

如果答對題目少于30%，那么您還不是十分了解和精通Linux哦。現在就開始閱讀本書，與笨叔叔和小企鵝一起快樂奔跑吧！當然您也可以先閱讀Robert Love的《Linux內核設計與實現》，或者《Linux設備驅動程序》，然后再閱讀本書。