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