陳小蘭, 楊 斌

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,四川成都 610031）

1 引言

順應(yīng)對(duì)稱(chēng)多處理器（Symmetric Multi-Processor,SMP）及多核的出現(xiàn),Linux操作系統(tǒng)經(jīng)過(guò)不斷地完善和發(fā)展,早就針對(duì)SMP體系結(jié)構(gòu)作了很大的改動(dòng),實(shí)現(xiàn)了對(duì)多處理器的支持,但目前針對(duì)多處理及多核平臺(tái)的系統(tǒng)移植及多核平臺(tái)的應(yīng)用程序多核化還存大很大的空白,因此有必要深入理解內(nèi)核級(jí)的多處理器支持。位圖是內(nèi)核中進(jìn)行操作系統(tǒng)資源管理分配的重要手段之一,文中分析的多處理器平臺(tái)下Linux 2.6啟動(dòng)過(guò)程中的位圖,就是希望能為多處理及多核平臺(tái)的系統(tǒng)移植及多核平臺(tái)的應(yīng)用程序開(kāi)發(fā)提供一些指導(dǎo)。

分析基于Intel X86 SMP體系結(jié)構(gòu),Linux操作系統(tǒng)內(nèi)核為2.6.10。

2 Linux下的位圖及類(lèi)型

2.1 單處理器結(jié)構(gòu)下Linux中的位圖及類(lèi)型

位圖是Linux內(nèi)核中一個(gè)32位的全局變量,其中的每一位對(duì)應(yīng)一種狀態(tài),在單處理器結(jié)構(gòu)下,位圖主要用于調(diào)度、內(nèi)存管理等,以更快地索引當(dāng)前應(yīng)投入運(yùn)行的任務(wù)或是查找空閑塊等。

2.2 多處理器結(jié)構(gòu)下Linux中的位圖及類(lèi)型

在多處理器結(jié)構(gòu)下也有上述單處理器結(jié)構(gòu)中的位圖,但卻增加了與多處理器啟動(dòng)過(guò)程相關(guān)的位圖,這些位圖是Linux內(nèi)核中32位的全局CPU變量,其中每一位都與某一個(gè)特定的CPU相對(duì)應(yīng),分別對(duì)應(yīng)0和1兩種狀態(tài),但所起的作用在多處理器啟動(dòng)過(guò)程中的不同階段卻各不相同。隨著Linux操作系統(tǒng)對(duì)SMP支持的不斷完善和發(fā)展,2.6版本的內(nèi)核中還增加了新的和SMP啟動(dòng)相關(guān)的位圖,所有這些位圖都將在下面進(jìn)行詳細(xì)分析。

3 多處理器結(jié)構(gòu)下的位圖建立

3.1 多處理器系統(tǒng)啟動(dòng)的總體流程

位圖是在系統(tǒng)啟動(dòng)過(guò)程中依次建立起來(lái)的,因此,要分析位圖的作用首先要弄清系統(tǒng)啟動(dòng)的整個(gè)過(guò)程。

系統(tǒng)啟動(dòng)過(guò)程主要包括以下幾個(gè)步驟:

（1）系統(tǒng)加電后,BIOS初始化,自檢（屏蔽AP）;

（2）BIOS將MBR里面的引導(dǎo)程序（Grub,Lilo等）調(diào)入內(nèi)存,并由該引導(dǎo)程序?qū)inux內(nèi)核調(diào)入;

（3）Linux操作系統(tǒng)啟動(dòng)部分運(yùn)行setup.S和head.S,將內(nèi)核解壓到內(nèi)存,并進(jìn)行實(shí)模式下及保護(hù)模式下的初始化[1];

（4）進(jìn)入執(zhí)行內(nèi)核中的start-kernel（）函數(shù),對(duì)系統(tǒng)的各種資源進(jìn)行初始化,創(chuàng)建BSP的空閑進(jìn)程;（5）init（）函數(shù)的執(zhí)行,首先完成對(duì)SMP系統(tǒng)的初始化,再進(jìn)行上層應(yīng)用的初始化。

3.2 Linux SMP初始化過(guò)程中的位圖處理機(jī)制

在SMP體系結(jié)構(gòu)下,SMP的初始化包括主CPU（BSP）和次CPU（AP）的初始化,相關(guān)位圖就是在這兩個(gè)過(guò)程中依次建立起來(lái)的。

從BIOS初始化到start-kernel函數(shù)的執(zhí)行,系統(tǒng)都還沒(méi)有對(duì)AP做任何處理,一直是BSP在運(yùn)行,BSP在start-kernel（）中進(jìn)行自身的初始化工作,并設(shè)置好自己相應(yīng)的cpu-online-map位圖和 cpu-callout-map位圖[2]。cpu-online-map表示當(dāng)前聯(lián)機(jī)的CPU,僅在CPU已經(jīng)可以用于內(nèi)核調(diào)度或接收設(shè)備中斷時(shí)設(shè)置。而cpu-callout-map是每次CPU啟動(dòng)后向主CPU發(fā)出通知時(shí),由主CPU負(fù)責(zé)設(shè)置,而主CPU自身所對(duì)應(yīng)的這個(gè)位圖的相應(yīng)位則由主CPU自己在此進(jìn)行設(shè)置。BSP在start-kernel（）中調(diào)用smp-prepare-boot-cpu（）就是將cpu-online-map位圖和cpu-callout-map位圖中與主CPU相對(duì)應(yīng)的那一位設(shè)置為1,表示BSP已經(jīng)初始化。

在start-kernel函數(shù)中,主要處理例如cache、內(nèi)存等初始化工作,最后在進(jìn)入BSP的空閑進(jìn)程前要調(diào)用kernel-thread（）創(chuàng)建init內(nèi)核線程[3],在init（）函數(shù)里,具體實(shí)現(xiàn)SMP系統(tǒng)各CPU的初始處理機(jī)制。分析相關(guān)的SMP初始化函數(shù),源代碼在linux/init/main.c中:

在函數(shù)smp-prepare-cpus中,調(diào)用smp-boot-cpus函數(shù)啟動(dòng)并初始化各AP,源代碼在linux/arch/i386/kernel/Smpboot.c中,這個(gè)函數(shù)的重點(diǎn)是對(duì)每個(gè)AP依次調(diào)用do-boot-cpu函數(shù),下面來(lái)看在do-boot-cpu中做了什么工作,關(guān)鍵代碼在linux/arch/i386/kernel/smpboot.c中。這一函數(shù)首先創(chuàng)建自己的idle進(jìn)程（即0號(hào)進(jìn)程）,然后BSP將AP在一開(kāi)始被喚醒后需要執(zhí)行的代碼（trampoline.S）的首地址寫(xiě)入熱啟動(dòng)向量。這樣,當(dāng)BSP對(duì)AP發(fā)送IPI時(shí),AP受到啟動(dòng)后響應(yīng)中斷,自動(dòng)跳入這個(gè)trampoline.S代碼部分繼續(xù)執(zhí)行。為了AP有足夠的時(shí)間響應(yīng)中斷,BSP在發(fā)送中斷請(qǐng)求后要延遲一段時(shí)間。在這期間,BSP是怎樣得知AP是否初始化完了呢?AP又是怎樣知道自已可以繼續(xù)往下執(zhí)行直到進(jìn)入空閑進(jìn)程呢?這就得依靠?jī)蓚€(gè)全局位圖cpu-callout-map和cpucallin-map了,具體實(shí)現(xiàn)流程如圖1所示。

引入cpu-callin-map和cpu-callout-map兩個(gè)位圖后,主CPU和次CPU之間的應(yīng)答變得非常容易,否則,主CPU和相應(yīng)的次CPU都無(wú)法繼續(xù)往下執(zhí)行,而需要靠處理器間中斷（IPI）來(lái)完成。

AP在跳入 trampoline.S代碼后,將載入符號(hào)表（gdt）和局部符號(hào)表（ldt）,然后進(jìn)入保護(hù)模式并跳至head.S的入口處,以下是進(jìn)入保護(hù)模式并跳至head.S的入口處的代碼片斷:源代碼在linux/arch/i386/kernel/trampoline.S中:

圖1 位圖cpu-callout-map和cpu-callin-map的設(shè)置

這段代碼通過(guò)將ax（第0位已置1）所指示的控制字裝入機(jī)器狀態(tài)字（即CR0的低5位）使處理器進(jìn)入保護(hù)模式運(yùn)行,然后通過(guò)一個(gè)長(zhǎng)跳轉(zhuǎn),到0x10:0x00100000,即內(nèi)核被解壓后的起始地址,也就是head.S的startup-32（）函數(shù)。

由此,各AP轉(zhuǎn)入head.S繼續(xù)執(zhí)行,在這一步中要依次為各個(gè)AP設(shè)置其相應(yīng)的0號(hào)進(jìn)程的task-struct和內(nèi)核堆棧,在支持SMP的Linux中,每個(gè)進(jìn)程相應(yīng)的task-struct結(jié)構(gòu)中新增加了一個(gè)cpus-allowed位圖,通過(guò)這個(gè)位圖,可以設(shè)置進(jìn)程在所希望的CPU上運(yùn)行。進(jìn)程遷移就是利用這個(gè)位圖進(jìn)行的。默認(rèn)情況下cpus-allowed的所有位都被設(shè)置為1,進(jìn)程可以在系統(tǒng)中所有可用的處理器上執(zhí)行[4]。當(dāng)然,這個(gè)位圖也可以在系統(tǒng)啟動(dòng)完成后由用戶(hù)通過(guò)相應(yīng)的系統(tǒng)調(diào)用設(shè)置一個(gè)不同的由一個(gè)或幾個(gè)位組合的位掩碼。當(dāng)這一處理器綁定關(guān)系改變時(shí),內(nèi)核就會(huì)采用遷移線程把任務(wù)推到合法的處理器上。在head.S中,AP執(zhí)行的代碼與BSP所執(zhí)行的并不完全一致,源代碼在linux/arch/i386/kernel/head.S中:

AP執(zhí)行head.S時(shí),當(dāng)執(zhí)行到上述代碼的時(shí)候,由于ready的值被改變,不再等于1,所以就繼續(xù)向前執(zhí)行,調(diào)用initialize-secondary函數(shù),而不是象BSP一樣執(zhí)行標(biāo)號(hào)1處的代碼（調(diào)用start-kernel函數(shù)）[5]。initializesecondary函數(shù)里面的代碼很簡(jiǎn)單,源代碼在linux/arch/i386/kernel/smpboot.c中:

這是一段內(nèi)嵌匯編程序,將程序跳轉(zhuǎn)至current-＞thread.eip（即前面的idle-＞thread.eip）處。CPU執(zhí)行start-secondary函數(shù),對(duì)相應(yīng)的AP進(jìn)行初始化。初始化完成后,則向主CPU一樣對(duì)cpu-online-map中與初始化目標(biāo)CPU相對(duì)應(yīng)的那一位進(jìn)行設(shè)置,表示該AP已經(jīng)初始化。最終,這個(gè)AP將進(jìn)入自己的空閑狀態(tài)。

這樣,一個(gè)AP的啟動(dòng)過(guò)程就完成了。每個(gè)AP的啟動(dòng)就是依次經(jīng)歷上述過(guò)程,并在上述過(guò)程中依次對(duì)相應(yīng)位圖進(jìn)行設(shè)置。

AP啟動(dòng)完成后,從函數(shù)調(diào)用返回到smp-boot-cpus（）,即回到主CPU的運(yùn)行中,這時(shí),所有次CPU都已啟動(dòng),接下來(lái)就是構(gòu)造cpu-sibling-map[]位圖數(shù)組,數(shù)組中的每一位保存同屬CPU的邏輯CPU號(hào),當(dāng)CPU支持超線程技術(shù)時(shí)就會(huì)表現(xiàn)出該位圖的優(yōu)勢(shì),利用它可以很快地找到當(dāng)前CPU核的兄弟CPU。當(dāng)然,如果一個(gè)物理CPU中只有一個(gè)邏輯核,則該位圖數(shù)組各元素的值就是自身的邏輯CPU號(hào)。圖2是以一個(gè)物理CPU中含有兩個(gè)邏輯核的體系結(jié)構(gòu)為例來(lái)說(shuō)明。

圖2 cpu-sibling-map位圖示例

smp-boot-cpus（）執(zhí)行完后,將調(diào)用下一函數(shù)fixup-cpu-present-map（）,該函數(shù)的作用是設(shè)置cpu-presentmap位圖。在Linux內(nèi)核不支持熱插撥時(shí),cpu-present-map可以用cpu-possible-map來(lái)代替,cpu-presentmap表示某一時(shí)刻計(jì)算機(jī)中使用的CPU位圖,而cpu-possible-map位圖是從開(kāi)機(jī)系統(tǒng)啟動(dòng)到某一時(shí)刻所有曾經(jīng)使用過(guò)的CPU位圖,這兩者在Linux內(nèi)核不支持熱插撥時(shí)代表相同的含義,但從2.6支持熱插撥以后,以前在smp-init（）中要激活所有CPU的,現(xiàn)在則只需根據(jù)cpu-present-map來(lái)激活相應(yīng)CPU即可。因此當(dāng)一個(gè)熱插撥CPU被插入時(shí),就要更新cpu-present-map的相應(yīng)位。

4 結(jié)束語(yǔ)

多處理器結(jié)構(gòu)下,位圖是很重要的。它在整個(gè)Linux內(nèi)核的引導(dǎo)過(guò)程中,起著重要的作用。

啟動(dòng)過(guò)程中位圖的使用使得CPU之間協(xié)調(diào)變得更加容易,不必處處都采用處理間中斷,從系統(tǒng)使用者的角度來(lái)講,則可以通過(guò)查看位圖來(lái)了解CPU的相關(guān)信息,使操作更加容易。通過(guò)剖析BSP和AP各自的啟動(dòng)過(guò)程,對(duì)其中所用到的位圖作了詳細(xì)分析,使整個(gè)BSP和AP的啟動(dòng)過(guò)程變得清晰明了,在此基礎(chǔ)上進(jìn)行多處理器結(jié)構(gòu)下不同平臺(tái)間的Linux系統(tǒng)移植也將變得更加容易。

[1] 賈秋亭,侯瑞蓮.嵌入式Linux的開(kāi)發(fā)[J].山東輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版）,2006,（4）.

[2] 何志宏,何為民.嵌入式Linux在開(kāi)發(fā)板gec2410上的完全啟動(dòng)過(guò)程[J].科技廣場(chǎng),2008,（8）.

[3] （美）BOVET&CESATI.陳莉君,馮銳,牛欣源譯.深入理解LINUX內(nèi)核[M].北京:中國(guó)電子出版社,2001:127.

[4] （美）Robert Love.陳莉君,康華,張波譯.Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)[M].北京:機(jī)械工業(yè)出版社,2006:47.

[5] 毛德操,胡希明.Linux內(nèi)核源代碼情景分析[M].杭州:浙江大學(xué)出版社,2009:1511.