基于源碼分析的多核操作系統研究與人才培養實踐

　　文章編號：1672-5913(2011)21-0081-03 中圖分類號：G642 文獻標識碼：A
　　基金項目：2010年“國家大學生創新性實驗計劃項目”資助(101002827)；“2011年首都師范大學課程建設立項項目”資助。
　　作者簡介：徐遠超，男，講師，研究方向為多核操作系統、并行與分布式計算。
　　
　　摘 要：多核已成為處理器的主流，在傳統的操作系統教學中引入操作系統如何支持多核的內容十分必要。本文從多核操作系統啟動流程分析和多核操作系統調度兩方面介紹基于源碼分析的研究方法，借助現有的文獻資料，學生不僅加深了對操作系統抽象概念的理解，也可以優化和修改內核。該方法目標準確，避免了盲目性。實踐經驗表明，經過幾個月的高強度訓練，學生的能力提升明顯。
　　關鍵詞：操作系統；調度；多核；人才培養；源碼分析
　　
　　“操作系統”是計算機系統的核心，是計算機系統結構領域最重要的基礎課程。世界著名大學都把操作系統的教學和研究擺在極其重要的位置，通常由資深教授擔綱主講，如美國UCSD大學主講“Principles of Computer Operating Systems”的Yuanyuan Zhou教授就是系統結構領域世界著名的學者。國家重大科技專項“核心電子器件、高端通用芯片及基礎軟件產品”也對國產操作系統研發和應用提出了更高的要求，且急需大量高端人才。
　　然而，操作系統的學習和研究相對其他課程而言略顯困難，原因在于概念比較抽象不容易理解、實踐內容較為復雜不容易自學，內核不容易調試，缺少友好的人機界面，顯得枯燥。因此，愿意從事操作系統研究的人很少。有些同學對Linux內核表現出興趣，但缺少教師指導，深陷在無窮無盡的代碼閱讀中，始終找不到成就感或遇到困難沒有人交流指導而不得不放棄。
　　筆者主講“嵌入式操作系統”，除教學與科研外，每年指導幾名本科生課外科研活動，如“校級學生科學研究項目”、“全國大學生創新性實驗計劃”等，課外實踐是學生能力有效提升的最佳手段[1]。在選題時，“實用性、原創性、前瞻性、挑戰性、延續性” 是考慮的重點，即研究的內容要有意義，必須對教學或科研有直接或間接的促進作用，如果通過大量的中英文文獻檢索確定研究的問題還沒有滿意的解決方案，那么，我們就需要尋找和設計新的方法，堅持高起點，不做純粹的工程。另外，每年研究的問題要相對聚焦，在某一個方面做得盡可能深入，而不是淺嘗輒止。
　　多核已成為處理器的主流，然而，操作系統教學中對操作系統如何支持多核的介紹卻顯得不足，如多核的啟動流程、多核操作系統調度，等等[2]。本文將從這兩個方面闡述如何引導學生開展這方面的研究，從而加深對操作系統的理解。
　　1 多核操作系統啟動流程分析
　　由于多核與多處理器(SMP)十分相似，使得現有的多處理器操作系統基本不用修改就可以用在多核上。然而，很多講解Linux內核的書都提到了Linux的啟動流程，但很少詳細闡述多核環境下的啟動流程，網上的文獻資料也都比較簡單。
　　了解Linux的啟動流程對深入了解操作系統的啟動過程以及優化操作系統的快速啟動很有幫助，于是，我們組織學生從閱讀源碼入手，借助相關文獻，熟悉啟動流程，陳莉君老師也十分認同此種做法[3]。
　　Linux中SMP啟動主要流程如下。
　　1) BIOS初始化(屏蔽AP-Application Processor，建立系統配置表格)。
　　2) MBR里面的引導程序(Grub，Lilo等)將內核加載到內存。
　　3) 執行head.S中的startup_32函數(最后將調用start_kernel)。
　　4) 執行start_kernel()，這個函數相當于應用程序里面的main。
　　5) start_kernel()進行一系列初始化，最后將執行smp_init() 啟動各個AP。
　　6) rest_init()，調用init()創建1號進程，自身執行 cpu_idle()成為0號進程。
　　7) 1號進程即init進程完成余下的工作。
　　由于BIOS代碼并不是支持多線程的，所以在SMP中，系統必須讓所有AP進入中斷屏蔽狀態，不與BP一起執行BIOS代碼。BIOS要同時完成對APIC以及其他與MP相關的系統組件初始化過程，并建立相應的系統配置表格，以便操作系統使用。到了啟動的第2步，BIOS開始調入執行啟動引導區程序，錄入Linux操作系統的啟動部分。因此我們可以看到，在系統加電啟動過程中，實際上只有一個CPU(BP-bootstrap processor)負責啟動工作，而其他的CPU則處于中斷屏蔽狀態，等待著操作系統的激活。
　　在初始化階段，BP先完成自身的初始化，進入保護模式并開啟分頁式存儲管理機制，在完成系統特別是內存的初始化，然后從start_kernel調用smp_init進行SMP結構的初始化，代碼在init/main.c中。這個函數的主體是smp_boot_cpus，它依次啟動系統中各個AP，讓他們各自走過初始化的第一個階段。內核中有個全局變量MAX_CPUS，表示系統識別的最大的CPU數量，可以在內核配置菜單中設置。各個AP在完成了自身的初始化以后都要停下來等待一個統一的“起跑”命令。而BP則在完成所有AP的啟動以后通過smp_commence發出這個命令。初始化的方式是通過APIC發送IPI。當BP初始化完畢所有的AP之后，就繼續執行start_kernel中的其余部分代碼。
　　BP將AP在一開始被喚醒后需要執行的代碼(trampoline.S)的首地址寫入熱啟動向量(warm reset vector)，即從40:67開始的兩個字。這樣，當BP對AP發送IPI時，AP響應中斷，自動跳入這個trampoline.S代碼部分繼續執行。為了AP有足夠的時間響應中斷，BP在發送中斷請求后要延遲一段時間，在這以后，事實上AP已經在工作了。AP響應中斷直接跳轉至trampoline.S的入口處，trampoline.S在載入符號表(GDT)和局部符號表(LDT)之后進入保護模式并跳至head.S的入口處。AP轉入head.S繼續執行，但是執行的代碼與BP所執行的并不完全一致。由于ready的值被改變，不再等于1，所以就繼續向前執行，調用initialize_secondary函數，而不是像BP一樣調用start_kernel函數。initialize_secondary是一段內嵌匯編程序，將程序跳轉至current->thread.esp，即前面的idle->thread.esp)處。CPU執行start_secondary函數，進入空閑狀態，等待以后的系統調度。
　　至此，一個AP的初始化過程就完成了。所有的AP啟動后，系統中所有的CPU就不再有主次之分，即它們是完全平等的。
　　2 多核操作系統調度
　　調度是操作系統的基本功能，單核上的調度器只需要解決何時(when)運行哪一個任務的問題，主要實現輪轉方式或高優先級優先的方式進行任務的切換。
　　多核環境下的調度器不僅要完成任務的切換，還要解決任務在哪個核上(where)運行的問題，這使得問題一下子復雜了很多，雖然有大量的文獻資料介紹各種版本的調度原理，但都不完備。為了讓學生深入了解任務調度的全過程，我們安排學生閱讀了從任務創建、分配、調度運行以及負載均衡相關的所有核心代碼，并做了詳細的注解。源碼是信息的第一手資料，最真實可信。盡管有一些文獻可參閱，但閱讀的過程仍不輕松，但理解和印象卻十分深刻。通過源碼分析，學生了解到，當任務創建時，存在任務到核之間的首次分配問題，如果分配不合理，還有機會通過負載均衡得到修正，但并不能保證一定會被遷移。在此過程中，學生了解了調度域的概念，也了解了核的負載計算辦法、任務遷移規則、時間片的計算以及如何保證調度的公平。
　　
　　考慮到高版本的Linux內核過于復雜，也不容易編譯通過，我們選取了比較常用的2.6.18版本。在深入了解了調度器的工作原理后，我們又組織學生開展了異構多核調度器的研究工作，這是一個探索性課題。
　　異構多核處理器是近年逐漸被企業認可的一種新型體系結構，即片上多個核不完全一致，表現為功能異構或性能異構。所謂功能異構是指每個核的處理單元存在差異，往往表現為指令集異構；性能異構是指每個核的性能存在差異，指令集完全相同。研究發現，不同的程序之間甚至同一個程序運行時的不同階段常常表現出不同的行為特性，對于這種程序行為的多樣性，理論與實驗都已證明，使用異構多核處理器比使用同構多核處理器往往具有更好的性能功耗比，程序行為的差異越大，性能功耗比越明顯。異構多核處理器的設計并不復雜，但所有的處理器廠商都沒有推出商用的異構多核處理器，根本原因就在于目前的所有操作系統，包括Windows和Linux都不支持異構多核。操作系統設計者在設計之初就沒有想到異構，比如Linux，在啟動時查詢BP的特征，然后直接將其它核AP的特征視為與BP一樣，CPU的頻率也只定義了一個變量cpu_khz，并沒有定義成數組。異構感知是有效調度的基礎，因此必須對內核代碼加以修改。同樣，只有將線程合理的映射到最適合的核上，功效才會最佳，但實現這種合理的映射除了知道核的快慢外，還要清楚線程的屬性，傳統的調度器絲毫沒有考慮到程序行為的差異，而如何將程序行為分析與操作系統調度有機結合是必須解決的關鍵問題，信息是否準確、運行時開銷、對程序員是否透明是考慮的重點。最后就是調度策略問題，尤其是負載均衡調度策略，由于頻率的差異，core的負載需要重新折算，在遷移時，還要考慮目標core的屬性與待遷移線程是否滿足資源按需分配的原則。
　　在閱讀了大量英文資料后，學生進行了初步設計，開始了代碼修改和調試工作，這一過程十分艱辛，但收獲很大，從項目之初畏懼代碼、看不懂代碼到項目結束時充滿自信、可以輕松修改調試代碼。
　　實際上，圍繞多核和調度還有很多的工作可以去做，比如，功耗感知的多核調度器，雖然這是一個經典問題，但遠未成熟；如何編寫適應多核調度的多線程程序，程序的性能不僅取決于調度，還取決于程序編寫的質量。
　　3 結語
　　以上的嘗試都是依托學生課外實踐活動完成的，參與的學生是來自計算機學科各個專業的Linux內核愛好者，每年這樣的學生只有幾名，但足以組成一個團隊，對于學生能力普遍較強的高校，可以采取研究型教學[4]。興趣是學習的最大動力，沒有興趣，面對枯燥的代碼、艱難的調試是很難堅持的，這也是因材施教的體現方式[5]。
　　
　　參考文獻:
　　[1]