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