前言

RT????? RealTime實(shí)時(shí)調(diào)度

CPU?單處理器芯片

pcpu????單處理器芯片中的一個(gè)核。

vcpu??? Xen的基本調(diào)度單位，可理解為進(jìn)程。

預(yù)算??? Xen的RT調(diào)度中預(yù)算指的是任務(wù)的剩余運(yùn)行時(shí)間

文檔所分析代碼為Xen4.11版本。

經(jīng)過(guò)編寫(xiě)過(guò)程中的反復(fù)查看，發(fā)現(xiàn)本文易讀性較差，因此引入彩色字體，

淡灰色字體表示與主題相關(guān)性不大；

紅色字體表示重要信息；

紫色字體是為了提神；

各色字體交織使用表示同色字體的連續(xù)性。

認(rèn)真講，我并不十分看好Xen on arm的發(fā)展(代碼量不小、前有seL4，后有Ziron)，但是不得不說(shuō)他是目前我們唯一可獲得、可用的arm端支持虛擬化的微內(nèi)核，所有微內(nèi)核都是有其共同點(diǎn)的，即保留最核心內(nèi)核功能(其實(shí)我認(rèn)為應(yīng)該做出某種權(quán)衡，在微內(nèi)核、宏內(nèi)核之間，是否可以進(jìn)行更細(xì)的分割，以平衡生態(tài)、代碼量、可移植性)。于是其他基于微內(nèi)核的虛擬化實(shí)現(xiàn)，必然會(huì)走與Xen相似、甚至相同的路，如果能有其他更優(yōu)秀的實(shí)現(xiàn)路線：比如不再依賴(lài)Domain0、更靈活的硬件外設(shè)驅(qū)動(dòng)方案，也是會(huì)與Xen的思想有著千絲萬(wàn)縷的聯(lián)系(就像Xen與Linux很多思想是一致的。于是我認(rèn)為對(duì)Xen的解析，對(duì)HYP微內(nèi)核的深刻理解，是可以為在微內(nèi)核上的進(jìn)一步發(fā)展提供靈感的，Xen當(dāng)然是并不完善的，但是其優(yōu)秀的成分必然也不少(不然誰(shuí)會(huì)為止貢獻(xiàn)代碼呢)，你可以肆意的優(yōu)化甚至大規(guī)模改變流程，但是對(duì)于一個(gè)微內(nèi)核虛擬化方案，所有Xen需要支持的東西，我們肯定是無(wú)法錯(cuò)過(guò)的；于是作為一個(gè)切入點(diǎn)，Xen是值得的。

?

目錄

前言

從核心的啟動(dòng)函數(shù)start_xen()說(shuō)起

在start_xen()

軟中斷softirq執(zhí)行路線

軟定時(shí)器機(jī)制struct timers和struct timer

總結(jié)

一次調(diào)度的處理

在schedule()

描述Xen的調(diào)度單位vcpu

Xen向GuestOS伸出了魔爪

小結(jié)

RT調(diào)度的do_schedule()

RT調(diào)度的預(yù)算補(bǔ)充

RT調(diào)度的喚醒

RT調(diào)度的優(yōu)先級(jí)

RT調(diào)度的數(shù)據(jù)結(jié)構(gòu)

RT調(diào)度的deadline

小結(jié)

進(jìn)一步

?

從核心的啟動(dòng)函數(shù)start_xen()說(shuō)起

調(diào)度時(shí)內(nèi)核最核心功能之一，從內(nèi)核啟動(dòng)開(kāi)始就會(huì)對(duì)啟動(dòng)調(diào)度做準(zhǔn)備，于是分析Xen內(nèi)核啟動(dòng)過(guò)程中對(duì)調(diào)度的預(yù)初始化和初始化，是分析調(diào)度的初始步驟。Xen內(nèi)核啟動(dòng)，會(huì)執(zhí)行start_xen()過(guò)程，start_xen()是Xen微內(nèi)核C代碼的入口。

在start_xen()

1.??setup_cache();

微內(nèi)核會(huì)檢查cache屬性(略)；

2.??percpu_init_areas();

為每個(gè)pcpu分配空間，因?yàn)楹芏鄶?shù)據(jù)各pcpu都會(huì)有，比如cpu的頻率、id等[1]。此空間用于存放各pcpu自有數(shù)據(jù)，避免各個(gè)pcpu競(jìng)爭(zhēng)使用造成饑餓，一般稱(chēng)這種變量為per-cpu變量。[1]

3.??set_processor_id(0);

Xen微內(nèi)核啟動(dòng)首先會(huì)在第一個(gè)pcpu上執(zhí)行，并設(shè)置所在的pcpu的id。[2]

4.??set_current((structvcpu *)0xfffff000); idle_vcpu[3][0]=?current[4];

現(xiàn)在代碼處于Xen微內(nèi)核啟動(dòng)的第一個(gè)執(zhí)行vcpu?[5]，其他的pcpu并未啟動(dòng)，最終，本vcpu會(huì)退化成為一個(gè)idle_vcpu?[6]。

5.??setup_virtual_regions(NULL,NULL);

略。

6.??init_traps();

運(yùn)行在Xen上的GuestOS(包含特權(quán)域)都會(huì)認(rèn)為自己擁有整個(gè)硬件[7]，于是所有的GuestOS都會(huì)嘗試執(zhí)行所有計(jì)算指令(包括特權(quán)指令)，而這就是CPU對(duì)虛擬化支持的意義所在(指令被分為EL0-EL3(aarch64)特權(quán)等級(jí))，每一個(gè)特權(quán)指令都不會(huì)被隨意執(zhí)行，當(dāng)運(yùn)行在Xen之上的GuestOS在硬件執(zhí)行了EL2級(jí)特權(quán)指令(GuestOS內(nèi)核才被允許在EL1執(zhí)行)，EL2特權(quán)指令將會(huì)產(chǎn)生異常，被Xen捕獲，init_traps()就是在初始化捕獲器，包含關(guān)鍵的CP15 CR12中HVBAR[8]等。這也是ARM架構(gòu)規(guī)定特權(quán)指令等級(jí)的實(shí)施方式。

7.??smp_clear_cpu_maps();

Xen要根據(jù)設(shè)備樹(shù)進(jìn)行初始化設(shè)置，清除CPU位圖后，將當(dāng)前CPU0設(shè)入位圖。

8.??device_tree_flattened=early_fdt_map(fdt_paddr);

fdt_paddr在啟動(dòng)start_xen()時(shí)傳入，是設(shè)備樹(shù)的起始地址；FDT(flatted device tree)的DTB存放有板級(jí)設(shè)備信息，大小不超過(guò)2M，最少8byte對(duì)齊，early_fdt_map()會(huì)對(duì)DTB合法性進(jìn)行檢查，并創(chuàng)建對(duì)內(nèi)存的映射[9]，device_tree_flattened應(yīng)該是指向DTB所在內(nèi)存起始地址。

9.??其他初始化

Xen在隨后根據(jù)DTB信息進(jìn)行了大量初始化，設(shè)置啟動(dòng)地址、設(shè)置頁(yè)表、根據(jù)平臺(tái)初始化ACPI(Advanced Configuration and Power Management Interface)的AP、完成內(nèi)存初始化，這些操作與Xen調(diào)度分析關(guān)系不大，此處均不詳述(主要是有些東西弄清楚耗時(shí)太長(zhǎng))。

10.?system_state=SYS_STATE_boot；

system_state全局變量標(biāo)志的Xen當(dāng)前的狀態(tài)[10]。當(dāng)前，Xen完成了內(nèi)存子系統(tǒng)的初始化，從early_boot進(jìn)入boot狀態(tài)。

11.?vm_init();

虛擬內(nèi)存管理的初始化。

12.?init_IRQ();

各個(gè)中斷TYPE的初始化為IRQ_TYPE_INVALID(即IRQ正在初始化)[11]。

13.?platform_init();

根據(jù)硬件平臺(tái)的初始化，有廠商編寫(xiě)并根據(jù)Xen的接口封裝，Xen會(huì)根據(jù)DTB信息進(jìn)行匹配，得到可用的硬件平臺(tái)接口，并調(diào)用接口初始化函數(shù)。[12]

14.?對(duì)定時(shí)器、中斷控制器GIC、串口輸出、各pcpu預(yù)初始化。

preinit_xen_time();??初始化啟動(dòng)所在CPU的定時(shí)器[13]，查找定時(shí)器在DTB的節(jié)點(diǎn)，設(shè)置設(shè)備節(jié)點(diǎn)的使用者為DOMID_XEN[14]；調(diào)用平臺(tái)接口初始化此定時(shí)器，記錄啟動(dòng)時(shí)間[15]。

gic_preinit();???????初始化中斷控制器節(jié)點(diǎn)。[16]

串口初始化???????初始化UART設(shè)備、串口輸出的中斷、申請(qǐng)串口環(huán)形緩沖區(qū)。

CPU初始化???????檢測(cè)各pcpu可用性、一般屬性，初始化CPU位圖，更新nr_cpu_ids(保存有pcpu數(shù))。

15.?init_xen_time();

獲得定時(shí)器中斷資源，放入timer_irq數(shù)組。

16.?gic_init();

GIC私有structgic_hw_operations * gic_hw_ops是GIC設(shè)備接口入口，此處調(diào)用其init()接口對(duì)GIC設(shè)備初始化。

17.?tasklet_subsys_init();

對(duì)tasklet機(jī)制[17]進(jìn)行初始化，對(duì)各pcpu創(chuàng)建tasklet_list和softirq_tasklet_list；注冊(cè)一個(gè)CPU的Notifiter[18]；打開(kāi)TASKLET_SOFTIRQ，并設(shè)定tasklet_softirq_action()為軟中斷處理函數(shù)。tasklet_softirq_action()調(diào)用do_tasklet_work()將struct tasklet從原有鏈表摘下并執(zhí)行其內(nèi)部提供的處理函數(shù)；執(zhí)行完成后，若struct tasklet->scheduled_on[19]>=0則調(diào)用tasklet_enqueue()。tasklet_enqueue()會(huì)根據(jù)struct tasklet->is_softirq[20]決定將tasklet加入指定pcpu的softirq_tasklet_list[21]或tasklet_list[22]，softirq_tasklet_list將會(huì)在軟中斷執(zhí)行，tasklet_list則會(huì)置位對(duì)應(yīng)pcpu的tasklet_work_to_do變量的_TASKLET_enqueued位[23]。

18.?xsm_dt_init();

Xen Security Modules。Xen限制Domain的安全訪問(wèn)控制機(jī)制，可以定義域間、域與HYP以及相關(guān)內(nèi)存、設(shè)備資源的通訊、使用。類(lèi)SELinux。

19.?init_timer_interrupt();

通過(guò)request_irq()，將timer_irq定時(shí)器中斷資源與處理函數(shù)timer_interrupt()連接。[24]

20.?timer_init();

執(zhí)行open_softirq(TIMER_SOFTIRQ,timer_softirq_action)，將TIMER_SOFTIRQ[25]打開(kāi)，并設(shè)置處理函數(shù)為timer_softirq_action()。timer_softirq_action()主要將當(dāng)前pcpu的structtimer中的function執(zhí)行。

21.?init_idle_domain();

執(zhí)行open_softirq(SCHEDULE_SOFTIRQ,schedule)，將SCHEDULE_SOFTIRQ軟中斷打開(kāi)并將schedule()調(diào)度函數(shù)給入；將所用調(diào)度器給入全局struct scheduler ops，然后執(zhí)行cpu_schedule_up()，其中init_timer()將s_timer_fn()設(shè)入當(dāng)前pcpu的struct schedule_data –> struct timer –>function中，s_timer_fn()會(huì)raise_softirq(SCHEDULE_SOFTIRQ)啟動(dòng)調(diào)度。最后init_idle_domain創(chuàng)建了一個(gè)空閑域。

22.?其他初始化操作

start_xen()隨后對(duì)RCU進(jìn)行了初始化、創(chuàng)建了內(nèi)存管理相關(guān)的虛擬Domain、使能中斷、對(duì)SMP的預(yù)初始化、調(diào)用uart的驅(qū)動(dòng)接口初始化postirq、嘗試啟動(dòng)其余pcpu。最終start_xen()創(chuàng)建了特權(quán)域Domain0，并退化成為idle_vcpu。

軟中斷softirq執(zhí)行路線

1.??硬/軟中斷觸發(fā)與執(zhí)行

本質(zhì)上，Xen的軟硬中斷觸發(fā)執(zhí)行過(guò)程為：硬件中斷觸發(fā)軟件中斷TIMER_SOFTIRQ，TIMER_SOFTIRQ負(fù)責(zé)處理所有的軟定時(shí)器，軟定時(shí)器們有的負(fù)責(zé)觸發(fā)調(diào)度軟中斷、有的作為vcpu的虛擬定時(shí)器源。

a)??系統(tǒng)啟動(dòng)時(shí)執(zhí)行init_timer_interrupt();

b)??init_timer_interrupt()執(zhí)行request_irq()，將硬件定時(shí)器處理函數(shù)指向timer_interrupt()。[26]

c)??timer_interrupt()函數(shù)會(huì)raise_softirq(TIMER_SOFTIRQ)，預(yù)計(jì)softirq將會(huì)在中斷返回處執(zhí)行。

d)??do_softirq()[27]調(diào)用__do_softirq(0)執(zhí)行所有在softirq_handlers中的軟中斷函數(shù)。

e)??核心函數(shù)指針數(shù)組softirq_handlers，記錄有軟中斷處理函數(shù)，其主要元素有TIMER_SOFTIRQ[28]

SCHEDULE_SOFTIRQ[29]

NEW_TLBFLUSH_CLOCK_PERIOD_SOFTIRQ

RCU_SOFTIRQ

TASKLET_SOFTIRQ

NR_COMMON_SOFTIRQS。

2.??軟中斷/定時(shí)器設(shè)置

a)??open_softirq()時(shí)會(huì)把處理函數(shù)設(shè)入softirq_handler函數(shù)指針數(shù)組。

b)??init_timer()會(huì)將軟定時(shí)器放入per-cpu變量timers，并設(shè)置軟定時(shí)器處理函數(shù)。

軟定時(shí)器機(jī)制struct timers和struct timer

1.??管理timer的timers

struct timers是per-cpu變量timers的數(shù)據(jù)結(jié)構(gòu)，其中有struct timer，分為struct timer **heap，struct *list，struct timer *running，struct list_head inactive。

a)??structtimer **heap是一個(gè)timer堆，大概按照超時(shí)順序排列。如果發(fā)現(xiàn)所插入timer為堆內(nèi)首個(gè)timer，則會(huì)軟件產(chǎn)生一個(gè)TIMER_SOFTIRQ，堆滿(mǎn)才用鏈表。

b)??structtimer list是一個(gè)timer鏈表，按照超時(shí)時(shí)間大小排列，在struct timer ** heap空間不夠時(shí)，才會(huì)用鏈表。發(fā)現(xiàn)所插入timer是鏈表第一個(gè)元素時(shí)會(huì)軟件產(chǎn)生TIMER_SOFTIRQ。

c)??structtimer running存放正在執(zhí)行的timer，在timer的function被執(zhí)行時(shí)會(huì)將其從timer堆或timer鏈表中移除，然后實(shí)際執(zhí)行時(shí)被加入到running鏈表。

d)??structtimer inactive是timer被deactivate之后的存放之處。

2.??vcpu的timer

a)??periodic_timer

用于發(fā)生vcpu的虛擬定時(shí)器中斷。

b)??singleshot_timer

c)??poll_timer

3.??調(diào)度觸發(fā)的timer

per-cpu變量struct schedule_data中的s_timer軟定時(shí)器是調(diào)度的觸發(fā)定時(shí)器，當(dāng)TIMER_SOFTIRQ觸發(fā)此軟定時(shí)器，軟定時(shí)器處理函數(shù)s_timer_fn()將會(huì)觸發(fā)SCHEDULE_SOFTIRQ軟中斷，發(fā)生調(diào)度。

4.??補(bǔ)充預(yù)算的timer-實(shí)時(shí)調(diào)度

structscheduler的sched_data元素指向?qū)崿F(xiàn)調(diào)度器算法的私有數(shù)據(jù)結(jié)構(gòu)，對(duì)于RT調(diào)度此數(shù)據(jù)為struct rt_private，rt_private中的repl_timer軟定時(shí)器是RT調(diào)度用于補(bǔ)充預(yù)算的定時(shí)器，每次補(bǔ)充預(yù)算完成后，會(huì)設(shè)置軟定時(shí)器的出發(fā)時(shí)間為下一個(gè)投入執(zhí)行的vcpu的deadline。

5.??Domain的看門(mén)狗(默認(rèn)每個(gè)域可有2個(gè))

structdomain中的watchdog_timer[]軟定時(shí)器保存有Domain的看門(mén)狗定時(shí)器，若被觸發(fā)說(shuō)明Domain沒(méi)有喂狗，可能出錯(cuò)，會(huì)將Domain關(guān)閉。

6.??structvtimer的定時(shí)器

與Domain虛擬中斷相關(guān)的軟定時(shí)器，略。

總結(jié)

start_xen()啟動(dòng)到當(dāng)前位置并未完成，Xen調(diào)度相關(guān)初始化主線已經(jīng)分析清楚。CPU硬件中斷[30]與處理函數(shù)綁定[31]，處理函數(shù)中會(huì)發(fā)起TIMER_SOFTIRQ軟中斷；系統(tǒng)軟中斷TIMER_SOFTIRQ綁定的處理函數(shù)[32]會(huì)執(zhí)行所有當(dāng)前pcpu掛載在timers中的軟定時(shí)器的處理函數(shù)；調(diào)度器的軟定時(shí)器處理函數(shù)是s_timer_fn()[33]，會(huì)觸發(fā)SCHEDULE_SOFTIRQ軟中斷；?SCHEDULE_SOFTIRQ軟中斷的處理函數(shù)為schedule()，是系統(tǒng)調(diào)度入口。[34]

一次調(diào)度的處理

Xen調(diào)度入口函數(shù)位于文件”./xen/common/schedule.c”中的static voidschedule(void)。調(diào)度的觸發(fā)方式會(huì)有多種，在Xen中確定已知的有定時(shí)觸發(fā)、中斷返回觸發(fā)、任務(wù)阻塞觸發(fā)[35]。所有觸發(fā)的調(diào)度最終都會(huì)傳導(dǎo)到schedule。

在schedule()

1.??switch( *tasklet_work )

tasklet_work[36]是當(dāng)前pcputasklet work的狀態(tài)標(biāo)志，可以為T(mén)ASKLET_enqueued、TASKLET_scheduled以及TASKLET_enqueued|TASKLET_scheduled，如果僅有TASKLET_scheduled置位，表示不需要處理，否則調(diào)度器會(huì)執(zhí)行idle_vcpu，idle_vcpu會(huì)執(zhí)行do_tasklet()，并調(diào)整標(biāo)志位。do_tasklet()會(huì)調(diào)用do_tasklet_work()，在do_tasklet_work()中，tasklet的func會(huì)被執(zhí)行；只有在tasklet鏈表中不再有元素時(shí)，do_tasklet()會(huì)清除TASKLET_enqueued標(biāo)志位。在TASKLET_enqueued標(biāo)志位被清除時(shí)schedule()會(huì)清除TASKLET_scheduled。

2.??stop_timer(&sd->s_timer);

sd是當(dāng)前pcpu的schedule_data，其中包含鎖、struct vcpu *curr[37]、void *sched_priv[38]、struct timer s_timer[39]、urgent的vcpu計(jì)數(shù)。各pcpu的struct timers數(shù)據(jù)[40]中有struct timer，分為struct timer **heap[41]，struct *list[42]，struct timer *running[43]，struct list_head inactive[44]，此處將struct timer->status設(shè)置為T(mén)IMER_STATUS_inactive，并加入timer所屬pcpu下struct timers數(shù)據(jù)的inactive鏈表。[45]

3.??next_slice= sched->do_schedule(sched, now, tasklet_work_scheduled);

調(diào)用當(dāng)前pcpu的調(diào)度器計(jì)算下一個(gè)要投入運(yùn)行的任務(wù)，其中next_slice包含3個(gè)元素：structvcpu *task[46]、s_time_t time[47]、bool_t migrated[48]；sched為調(diào)度器結(jié)構(gòu)體，指向當(dāng)前pcpu調(diào)度器指針；do_schedule()為調(diào)度器調(diào)度計(jì)算函數(shù)入口[49]；now=NOW()是CPU時(shí)間；tasklet_work_scheduled是tasklet需要調(diào)度投入執(zhí)行的標(biāo)志[50]。

4.??next =next_slice.task;

next是將會(huì)被投入運(yùn)行的任務(wù)。

5.??sd->curr= next;

至此，schedule函數(shù)選好了投入運(yùn)行的任務(wù)，記錄到sd的curr[51]。

6.??設(shè)置投運(yùn)任務(wù)的運(yùn)行時(shí)間

if (next_slice.time >= 0 ) set_timer(&sd->s_timer, now +next_slice.time);

next_slice.time只有在下一個(gè)任務(wù)使idle_vcpu的時(shí)候才會(huì)小于0；set_timer()將會(huì)給當(dāng)前pcpu的調(diào)度定時(shí)器續(xù)時(shí)，時(shí)長(zhǎng)決定于next_slice.time。

7.??省略

TRACE_3D()、TRACE_4D()會(huì)記錄調(diào)度的切換，不予分析；當(dāng)計(jì)算完發(fā)現(xiàn)即將投入運(yùn)行的任務(wù)還是之前的任務(wù)，則會(huì)直接投入運(yùn)行。

8.??vcpu_runstate_change();

修改被調(diào)度出局任務(wù)的runstate，runstate記錄有vcpu在各狀態(tài)停留時(shí)間，根據(jù)被調(diào)度出局的原因：阻塞、離線、可執(zhí)行[52]，是一個(gè)struct vcpu_runstate_info數(shù)據(jù)結(jié)構(gòu)，包含int state[53]、uint64_t state_entry_time[54]、uint64_t time[4][55]。

9.??prev->last_run_time= now;

記錄被調(diào)度出局的vcpu的出局時(shí)間。

10.?vcpu_runstate_change(next,RUNSTATE_running, now);

記錄即將投運(yùn)任務(wù)的runstate。

11.?next->is_running= 1;

標(biāo)志著vcpu正在運(yùn)行中。

12.?stop_timer(&prev->periodic_timer);

關(guān)閉調(diào)度出局的vcpu的periodic_timer，其處理函數(shù)為vcpu_periodic_timer_fn()[56]，periodic_timer的作用是向vcpu定時(shí)發(fā)出虛擬中斷信號(hào)[57]；此處將之關(guān)閉即不再發(fā)出此虛擬中斷。

13.?if (next_slice.migrated ) sched_move_irqs(next);

對(duì)于即將投入運(yùn)行的vcpu，如果是從別的cpu遷移過(guò)來(lái)的，則需要調(diào)整他的IRQ到當(dāng)前的cpu上[58]。

14.?vcpu_periodic_timer_work(next);

即將投入運(yùn)行的vcpu的periodc_timer的啟動(dòng)：首先檢測(cè)當(dāng)前是否到vcpu的周期，決定是否發(fā)出virq；然后檢查并遷移periodic_timer到在當(dāng)前pcpu名下[59]；最后設(shè)置vcpu下一個(gè)virq發(fā)生點(diǎn)。

15.?context_switch(prev,next);

進(jìn)行了任務(wù)切換[60]。

描述Xen的調(diào)度單位vcpu

structvcpu?分析

vcpu是Xen的基本調(diào)度單位，其數(shù)據(jù)結(jié)構(gòu)structvcpu復(fù)雜[61]，下面將分析其關(guān)鍵元素。

structrt_vcpu分析

struct rt_vcpu是RT調(diào)度專(zhuān)有數(shù)據(jù)結(jié)構(gòu)，如下為全部元素：

Xen向GuestOS伸出了魔爪

之所以這么寫(xiě)這個(gè)標(biāo)題，是因?yàn)閷?xiě)到這里，我發(fā)現(xiàn)，這一部分的解析才剛剛露出冰山一角，這一部分是指Xen作為Hypervisor對(duì)操作GuestOS的支撐部分，我在想是不是要在這個(gè)文檔里寫(xiě)這個(gè)問(wèn)題；因?yàn)檫@。。。不屬于調(diào)度了吧（還是屬于？）？這已經(jīng)屬于GuestOS的調(diào)度基礎(chǔ)支撐了。

RT調(diào)度的do_schedule()

Xen的RT調(diào)度入口函數(shù)是位于文件”./xen/common/sched_rt.c”中的static struct task_slice?rt_schedule(conststruct scheduler *ops, s_time_t now,bool_t tasklet_work_scheduled)。主要處理：任務(wù)選擇，預(yù)算結(jié)算，返回所選擇的任務(wù)、將運(yùn)行時(shí)間以及是否遷移自其他pcpu。本章將會(huì)分析rt_schedule()函數(shù)的實(shí)現(xiàn)。

1.??cpumask_clear_cpu(cpu,&prv->tickled);

從tickled中清楚當(dāng)前pcpu位圖，tickled置位是因?yàn)閳?zhí)行了runq_tickle()，runq_tickle()有點(diǎn)發(fā)現(xiàn)優(yōu)先級(jí)排序不對(duì)了，會(huì)整理，然后就會(huì)產(chǎn)生一次軟中斷調(diào)度[62]。

2.??burn_budget(ops,scurr, now);

將當(dāng)前vcpu的預(yù)算結(jié)算掉(idle_vcpu除外)，對(duì)于RT調(diào)度，系統(tǒng)定義了私有的數(shù)據(jù)結(jié)構(gòu)struct rt_vcpu[63]，其中的last_start元素[64]記錄上次投入運(yùn)行的時(shí)間，可以計(jì)算出當(dāng)前vcpu已經(jīng)執(zhí)行的時(shí)長(zhǎng)[65]，在計(jì)算完后也要再次將last_start=now；cur_budget記錄vcpu運(yùn)行時(shí)預(yù)算[66]，當(dāng)cur_budget<=0，如果flags元素[67]中存在RTDS_exteratime標(biāo)志[68]，則提升其優(yōu)先級(jí)、補(bǔ)充其預(yù)算[69]，否則置位flags元素的RTDS_depleted標(biāo)志[70]；

3.??tasklet_work_scheduled[71]被置位時(shí)：snext = rt_vcpu(idle_vcpu[cpu]);

有tasklet需要正式調(diào)度過(guò)去執(zhí)行[72]，就不會(huì)發(fā)生runq_pick()[73]操作，即將要投入運(yùn)行的任務(wù)將會(huì)是idle_vcpu，只需做一些記錄即可，作為空閑vcpu會(huì)不停地執(zhí)行tasklet。

4.??snext=?runq_pick(ops, cpumask_of(cpu));

遍歷可執(zhí)行vcpu鏈表，綜合vcpu所處Domain的有效pcpu位圖[74]、vcpu的硬親和pcpu位圖[75]和實(shí)際pcpu位圖[76]，得到下一個(gè)運(yùn)行的vcpu[77]。需要注意的是這里的選擇vcpu并不考慮剩余預(yù)算的問(wèn)題，如果沒(méi)有預(yù)算，系統(tǒng)將會(huì)失敗，也就是說(shuō)，RunQ中vcpu必有預(yù)算。

5.??if (snext == NULL ) snext = rt_vcpu(idle_vcpu[cpu]);

如果沒(méi)有合適的vcpu被選到，則執(zhí)行idle_vcpu。

6.??查看是否需要執(zhí)行之前的vcpu

if(?!is_idle_vcpu(current)?&&??

vcpu_runnable(current)?&&

scurr->cur_budget > 0&&

(?is_idle_vcpu(snext->vcpu)?||compare_vcpu_priority(scurr, snext) > 0 )?)

snext = scurr

如果之前的vcpu，不是idle_vcpu、可執(zhí)行[78]、預(yù)算存在并且新選的vcpu是idle_vcpu或比之前vcpu優(yōu)先級(jí)低，則不會(huì)切換。

總結(jié)成人話就是：如果選完以后發(fā)現(xiàn)是空閑vcpu并且原先的vcpu不空閑，那么繼續(xù)執(zhí)行之前的vcpu；如果選出的vcpu優(yōu)先級(jí)不如之前的高，并且之前的vcpu還有預(yù)算，那么還是執(zhí)行之前的vcpu。這是RT調(diào)度的重要原則之一。

7.??if (?snext != scurr?&&

!is_idle_vcpu(current)?&&

vcpu_runnable(current)?)

__set_bit(__RTDS_delayed_runq_add, &scurr->flags);

如果下一個(gè)要投入運(yùn)行的vcpu不是當(dāng)前vcpu，并且當(dāng)前運(yùn)行的vcpu也不是idle_vcpu，并且當(dāng)前vcpu還是可執(zhí)行；置位struct rt_vcpu->flags的__RTDS_delayed_runq_add[79]。

8.??snext->last_start= now;

更新下一個(gè)投入執(zhí)行的vcpu的投入時(shí)間

9.??if (?snext->vcpu->processor != cpu?){

snext->vcpu->processor = cpu;

ret.migrated = 1;

}

檢查此vcpu是否遷移自非當(dāng)前pcpu[80]，對(duì)于產(chǎn)生遷移的需要更新vcpu->processor；ret是是函數(shù)返回值task_slice數(shù)據(jù)結(jié)構(gòu)，置位其migrated元素，提示遷移發(fā)生[81]。

10.?ret.time= snext->cur_budget;

cur_budget存有當(dāng)前vcpu將會(huì)被投入運(yùn)行的時(shí)長(zhǎng)，放入在返回值struct task_slice中time元素[82]。

11.?ret.task= snext->vcpu;

將選定的vcpu設(shè)置到返回值中。

RT調(diào)度的預(yù)算補(bǔ)充

當(dāng)vcpu的預(yù)算消耗完，需要補(bǔ)充預(yù)算的vcpu們會(huì)被放到ReplQ鏈表，由軟定時(shí)器repl_timer[83]觸發(fā)的處理函數(shù)repl_timer_handler()將會(huì)為之補(bǔ)充預(yù)算。下面將分析repl_timer_handler()功能。

1.??遍歷ReplQ鏈表，在遍歷過(guò)程中，會(huì)不斷給ReplQ中的vcpu元素補(bǔ)充預(yù)算、按周期延展deadline、將優(yōu)先級(jí)置0，并加入到臨時(shí)鏈表等待進(jìn)一步處理；預(yù)算補(bǔ)充完后，檢測(cè)如果vcpu還在RunQ/DeplQ，則會(huì)拔、插[84]回RunQ/DeplQ[85]。再次遍歷過(guò)程中，如果遇到deadline未到的vcpu應(yīng)截止遍歷，僅處理已補(bǔ)充預(yù)算的vcpu。

2.??遍歷上一步補(bǔ)充過(guò)預(yù)算的vcpu，如果發(fā)現(xiàn)vcpu正在運(yùn)行，但優(yōu)先級(jí)并不比RunQ上的下一個(gè)vcpu高[86]，這是不合理的，觸發(fā)runq_tickle()[87]；如果vcpu不在執(zhí)行，判斷其RTDS_depleted標(biāo)志位(判斷完清除之)并確認(rèn)其在RunQ/DeplQ，同樣觸發(fā)runq_tickle()。

RT調(diào)度的喚醒

vcpu任務(wù)的喚醒由rt_vcpu_wake()執(zhí)行，對(duì)于以下vcpu狀態(tài)：

1.??vcpu正在指定的pcpu執(zhí)行，更改per-cpu狀態(tài)vcpu_wake_running，喚醒結(jié)束。

2.??vcpu處于RunQ/DeplQ，更改per-cpu狀態(tài)vcpu_wake_onrunq，喚醒結(jié)束。

喚醒vcpu可直接執(zhí)行完畢。

對(duì)于普通情況，檢測(cè)vcpu處于可執(zhí)行狀態(tài)/不可執(zhí)行狀態(tài)，相應(yīng)的更改per-cpu狀態(tài)標(biāo)志。如果vcpu的deadline已超時(shí)，更新其deadline、預(yù)算、last_start=now、優(yōu)先級(jí)置0[88]；否則無(wú)需操作。如果vcpu RTDS_scheduled[89]置位，則置位RTDS_delayed_runq_add，以便于在此vcpu經(jīng)過(guò)rt_context_saved()時(shí)會(huì)將之加入RunQ/DeplQ；如果之前判斷deadline超時(shí)，則此處需要將其在ReplQ上插拔一次，以防止其在ReplQ鏈表不存在或順序問(wèn)題，完成后喚醒即結(jié)束。對(duì)于vcpu RTDS_scheduled未置位，即vcpu未在pcpu上執(zhí)行，則需要將其插入ReplQ、RunQ/DeplQ、然后用runq_tickle()檢查一下是否該觸發(fā)軟中斷[90]，喚醒結(jié)束。

RT調(diào)度的優(yōu)先級(jí)

RT調(diào)度的優(yōu)先級(jí)首先由struct rt_vcpu->priority_level決定，priority_level越小的vcpu優(yōu)先級(jí)越高；在同優(yōu)先級(jí)的情況下，會(huì)比較structrt_vcpu->cur_deadline，deadline越近的vcpu優(yōu)先級(jí)越高。具體可查看函數(shù)compare_vcpu_priority()。

RT調(diào)度的數(shù)據(jù)結(jié)構(gòu)

RT調(diào)度有3個(gè)鏈表[91]，由所有的pcpu[92]共享一個(gè)是有序[93]的RunQ鏈表，鏈接有預(yù)算且可執(zhí)行的vcpu；一個(gè)是無(wú)序DeplQ鏈表，鏈接沒(méi)有預(yù)算等待補(bǔ)充預(yù)算之后就能跑的vcpu；最后是一個(gè)有序[94]的ReplQ鏈表，鏈接等待補(bǔ)充預(yù)算的vcpu。

RunQ和DeplQ是互斥的兩個(gè)鏈表，即一個(gè)vcpu不能同時(shí)在RunQ和DeplQ上；但一個(gè)vcpu應(yīng)該同時(shí)在RunQ和ReplQ上，或同時(shí)在DeplQ和ReplQ上。

ReplQ只能在vcpu喚醒、初創(chuàng)的時(shí)候，插入RunQ/DeplQ(或is_running態(tài))才會(huì)被插入ReplQ；當(dāng)vcpu不再被調(diào)度時(shí)，需要離開(kāi)ReplQ(也會(huì)離開(kāi)RunQ/DeplQ)。

如果vcpu是由于進(jìn)入睡眠[95]、被銷(xiāo)毀[96]、遷移離開(kāi)調(diào)度[97]，則離開(kāi)3大鏈表。

RT調(diào)度的deadline

RT調(diào)度的deadline位于rt_vcpu->cur_deadline，唯一可以補(bǔ)充cur_deadline的位置是rt_update_deadline()，而在普通運(yùn)行階段[98]，唯有軟定時(shí)器repl_tmer的處理函數(shù)repl_timer_handler()會(huì)調(diào)用rt_update_deadline()為vcpu更新deadline，軟定時(shí)器repl_timer的觸發(fā)時(shí)間總是按照RunQ即將投入運(yùn)行的任務(wù)的cur_deadline設(shè)定。

進(jìn)一步

經(jīng)過(guò)上述分析可以全面的了解Xen調(diào)度的前因后果，RT調(diào)度的實(shí)現(xiàn)考量，之后還需要進(jìn)一步分析以及目前Xen的調(diào)度在ARM平臺(tái)存在的一些問(wèn)題如下。

1.??總結(jié)分析可能觸發(fā)調(diào)度的點(diǎn)。

2.??Xen對(duì)vcpu的切換過(guò)程，如寄存器保存、新寄存器值設(shè)入。

3.??Xen在已啟動(dòng)的pcpu中如何啟動(dòng)其他pcpu。

在vcpu_initialise()時(shí)，會(huì)有

???vcpu->arch.saved_context.sp = (register_t)v->arch.cpu_info;

???vcpu->arch.saved_context.pc = (register_t)continue_new_vcpu;

????是如何工作的。

4.??目前的RT調(diào)度，各CPU均采用同一任務(wù)鏈表，調(diào)度需要獲取鎖，是存在存在競(jìng)爭(zhēng)、浪費(fèi)的。

5.??Xen跨CPU調(diào)度僅根據(jù)一些固定設(shè)置，不是阻尼的方式防止，這很明顯會(huì)引起不必要的cachemiss降低效率。

6.??Xen不能感知GuestOS的空閑、于是當(dāng)vcpu執(zhí)行idle線程時(shí)，Xen也不會(huì)有動(dòng)作，是否可以修改GuestOS的idle線程。

7.??Xen對(duì)大小核并未考慮。

?

[1]?Xen應(yīng)該是繼承自Linux的各pcpu變量定義：DECLARE_PER_CPU(unsignedint, cpu_id)是獲得已被定義的per-cpu變量。一次引用聲明，各pcpu分別有了cpuid變量，當(dāng)代碼所處pcpu執(zhí)行this_cpu(cpuid)，即可獲得此pcpu的cpuid

[2]?具體代碼為this_cpu(cpuid)=0，第一個(gè)percpu變量的使用實(shí)例。

[3]?idle_vcpu是一個(gè)全局?jǐn)?shù)組，每一個(gè)物理pcpu都會(huì)有一個(gè)idle_vcpu，當(dāng)這個(gè)物理pcpu沒(méi)有任務(wù)時(shí)，就會(huì)把它取出來(lái)執(zhí)行。

[4]?current是一個(gè)宏變量，通過(guò)this_vcpu(curr_vcpu)獲得，即為本物理pcpu中執(zhí)行的vcpu。

[5]?Xen想要將所有的執(zhí)行進(jìn)程都作為vcpu來(lái)表述，可以理解為vcpu即為Xen的進(jìn)程，vcpu是Xen微內(nèi)核的關(guān)鍵概念，后續(xù)還會(huì)提到并解釋。

[6]?idle_vcpu是Xen中空閑進(jìn)程的。

[7]?想象沒(méi)有CPU對(duì)虛擬化的硬支持，Xen如何實(shí)現(xiàn)對(duì)GuestOS的管控：對(duì)于GuestOS下發(fā)的每一條計(jì)算機(jī)指令，Xen都需要將這條指令檢查過(guò)之后再投入計(jì)算機(jī)執(zhí)行，如同Java的虛擬機(jī)(效率更低)，效率就像是笑話(CPU50%以上的時(shí)間在檢查指令)。但如果不這樣做，一旦被GuestOS獲得CPU的使用權(quán)，GuestOS將會(huì)獲得完整的硬件使用權(quán)，如果GuestOS將硬件調(diào)度定時(shí)器的處理函數(shù)指向自己的調(diào)度函數(shù)，Xen就會(huì)像BootLoader一樣被扔到一邊，之后的GuestOS也都成為廢紙，所謂域間隔離也都只能是空談。

[8]?CP15 CR12下HVBAR是Hypervisor的Vector Base Address Register存儲(chǔ)異常向量地址；注意aarch64，與aarch32一些特權(quán)寄存器使用方式有變化。

[9]?early_fdt_map()調(diào)用的create_mappings()函數(shù)透露出Xen對(duì)內(nèi)存管理的信息，但由于本文檔重點(diǎn)分析Xen的調(diào)度機(jī)制，在此不予詳述。

[10]?Xen的狀態(tài)可能為：SYS_STATE_early_boot、SYS_STATE_boot、SYS_STATE_smp_boot、SYS_STATE_active、SYS_STATE_suspend、SYS_STATE_resume等

[11]?其他還有IRQ_TYPE_NONE(默認(rèn)的普通IRQ_TYPE)、IRQ_TYPE_EDGE_RISING(上升沿觸發(fā)的中斷)、IRQ_TYPE_EDGE_FALLING(下降沿觸發(fā)的中斷)、IRQ_TYPE_EDGE_BOTH(上升、下降沿均會(huì)觸發(fā)的中斷)，其他還有IRQ_TYPE_LEVEL_HIGH、IRQ_TYPE_LEVEL_LOW、IRQ_TYPE_LEVEL_MASK、IRQ_TYPE_SENSE_MASK等類(lèi)型或組合類(lèi)型的中斷。

[12]?此處Xen需要的初始化的接口少的可憐，init()估計(jì)是留給廠商將硬件啟動(dòng)，init_time()獲得硬件提供的一個(gè)定時(shí)器來(lái)作為系統(tǒng)的時(shí)鐘滴答(內(nèi)核基于此感知時(shí)間，如觸發(fā)調(diào)度，超時(shí)操作)；specific_mapping()讓廠商把外設(shè)的內(nèi)存地址送到struct domain，后期啟動(dòng)Dom0時(shí)，Dom0能看到外設(shè)。另外Xen還需要廠商提供的reset()、poweroff()，估計(jì)是重啟、關(guān)機(jī)操作。另外還可以有給出一個(gè)禁止pass-through的設(shè)備表告訴Xen。quirks()函數(shù)未知。arm32還會(huì)有smp_init()、cpu_up()函數(shù)。

[13]?對(duì)于啟動(dòng)了ACPI的設(shè)備，ACPI會(huì)接管初始化操作

[14]?這可能是Xen作為一個(gè)域的編號(hào)7FF2U，Dom0由此編號(hào)訪問(wèn)Hypervisor(如xl對(duì)Xen的操作？)。

[15]?啟動(dòng)時(shí)間的記錄在boot_count，從P15 CR14讀出。

[16]?GIC是中斷控制器，對(duì)于無(wú)ACPI平臺(tái)，系統(tǒng)直接讀DTB完成初始化，對(duì)于有ACPI節(jié)點(diǎn)，由ACPI提供的接口完成。

[17]?Xen中tasklet.c源碼中顯示是由1992年Linus Torvalds的代碼基礎(chǔ)上修改而來(lái)，總體機(jī)制變化不大。

[18]?Notifiter是內(nèi)核的常用通信機(jī)制，主體為一個(gè)按優(yōu)先級(jí)排列的鏈表，被插入當(dāng)前pcpu下。

[19]?scheduled_on>=0表示此tasklet應(yīng)該放在某pcpu上執(zhí)行，而scheduled_on的值即為pcpu的id，因此應(yīng)被放到對(duì)應(yīng)pcpu的softirq_tasklet_list或tasklet_list，如果為-1則不會(huì)特別處理。

[20]?is_softirq將會(huì)只能在軟中斷處理。

[21]?加入softirq_tasklet_list的同時(shí)，指定pcpu的softirq_tasklet_list無(wú)內(nèi)容，則為此CPU軟產(chǎn)生一個(gè)TASKLET_SOFTIRQ軟中斷。

[22]?加入tasklet_list時(shí)若指定pcpu的tasklet_list無(wú)內(nèi)容則為此CPU軟產(chǎn)生一個(gè)SCHEDULE_SOFTIRQ。

[23]?在REF _Ref517287190 \h??\* MERGEFORMAT?一次調(diào)度的處理?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380037003100390030000000，?REF_Ref517287151 \h??\* MERGEFORMAT?next_slice = sched->do_schedule(sched, now,tasklet_work_scheduled); 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380037003100350031000000會(huì)用到此變量。

[24]?timer_irq數(shù)組有四個(gè)成員TIMER_PHYS_SECURE_PPI、TIMER_PHYS_NONSECURE_PPI、TIMER_VIRT_PPI、TIMER_HYP_PPI，詳見(jiàn)章節(jié)REF _Ref517685421 \h??\* MERGEFORMAT?軟中斷softirq執(zhí)行路線?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003600380035003400320031000000。

[25]?TIMER_SOFTIRQ的處理函數(shù))是所有軟中斷啟動(dòng)之源

[26]?timer_irq數(shù)組記錄有定時(shí)器中斷資源，將與處理函數(shù)timer_interrupt()連接；timer_irq數(shù)組有四個(gè)成員及其處理函數(shù)：TIMER_PHYS_SECURE_PPI(可能是TZ相關(guān))、TIMER_PHYS_NONSECURE_PPI <->timer_interrupt、???TIMER_VIRT_PPI <->timer_interrupt、TIMER_HYP_PPI<->timer_interrupt。

[27]?分析猜測(cè)do_softirq()

[28]?由硬件中斷觸發(fā)

[29]?由軟定時(shí)器觸發(fā)，軟定時(shí)器由TIMER_SOFTIRQ觸發(fā)；這就是調(diào)度的軟中斷。

[30]?詳情見(jiàn)章節(jié)REF _Ref517291038 \h??\* MERGEFORMAT?在start_xen()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F00520065006600350031003700320039003100300033003800000012.init_IRQ()、14.preinit_xen_time()、15.init_xen_time()。

[31]?詳情見(jiàn)章節(jié)REF _Ref517291038 \h??\* MERGEFORMAT?在start_xen()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F00520065006600350031003700320039003100300033003800000019. init_timer_interrupt()。

[32]?詳情見(jiàn)章節(jié)REF _Ref517291038 \h??\* MERGEFORMAT?在start_xen()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F00520065006600350031003700320039003100300033003800000020.timer_init()。

[33]?詳情見(jiàn)章節(jié)REF _Ref517291038 \h??\* MERGEFORMAT?在start_xen()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F00520065006600350031003700320039003100300033003800000021.init_idle_domain()。

[34]?根據(jù)Linux內(nèi)核，軟中斷的處理會(huì)在中斷退出時(shí)發(fā)生，可能寫(xiě)在匯編代碼中，內(nèi)核代碼中找到的對(duì)do_softirq函數(shù)的調(diào)用，并不能確認(rèn)有效。

[35]分析能觸發(fā)調(diào)度的時(shí)機(jī)是非常重要的，但由于能力所限，短時(shí)間內(nèi)不能枚舉，此處僅列舉分析過(guò)程中確定可以觸發(fā)調(diào)度的時(shí)機(jī)。

[36]?tasklet_work=&this_cpu(tasklet_work_to_do)是當(dāng)前pcpu變量，由DECLARE_PER_CPU定義。

[37]?當(dāng)前正在運(yùn)行的任務(wù)vcpu數(shù)據(jù)結(jié)構(gòu)指針。

[38]?這是調(diào)度器的私有數(shù)據(jù)結(jié)構(gòu)入口。

[39]?調(diào)度定時(shí)器，軟中斷將會(huì)處理其內(nèi)function函數(shù)。

[40]?struct timers也是per-cpu變量，依舊是繼承自Linux的各pcpu變量定義，struct timers并未被DECLARE_PER_CPU引用聲明，由宏DEFINE_PER_CPU定義，DEFINE_PER_CPU是對(duì)per-cpu變量的真實(shí)定義，而DECLARE_PER_CPU是對(duì)per-cpu變量的引用聲明。&this_cpu(a)訪問(wèn)本pcpu的per-cpu變量&per_cpu(a,cpu0)訪問(wèn)cpu0核的per-cpu變量。

[41]根據(jù)add_to_heap()和remove_from_heap()的分析，struct timer **heap是一個(gè)timer堆，大概按照超時(shí)順序排列。如果發(fā)現(xiàn)所插入timer為堆內(nèi)首個(gè)timer，則會(huì)軟件產(chǎn)生一個(gè)TIMER_SOFTIRQ，堆滿(mǎn)才用鏈表。

[42]?struct timers中的struct timer list是一個(gè)timer鏈表，按照超時(shí)時(shí)間大小排列，在struct timer ** heap空間不夠時(shí)，才會(huì)用鏈表。發(fā)現(xiàn)所插入timer是鏈表第一個(gè)元素時(shí)會(huì)軟件產(chǎn)生TIMER_SOFTIRQ。

[43]?struct timers中的struct timer running在timer的function被執(zhí)行時(shí)(見(jiàn)20.中timer_softirq_action())，會(huì)從timer堆或timer鏈表中移除，然后實(shí)際執(zhí)行時(shí)(execute_timer())被加入到running鏈表。

[44]?struct timers中的struct timer inactive是timer被deactivate之后的存放之處。

[45]?timers和timer有著完整的機(jī)制描述，可在章節(jié)?REF _Ref517280274 \h? \* MERGEFORMAT?軟定時(shí)器機(jī)制struct timers和struct timer?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380030003200370034000000查看。

[46]?vcpu是Xen調(diào)度的基本單位。

[47]?指示當(dāng)前task_slice將會(huì)運(yùn)行多久，主要來(lái)自調(diào)度器自定數(shù)據(jù)結(jié)構(gòu)中xx_vcpu->cur_budget。

[48]?指示這個(gè)任務(wù)是否是從其他pcpu遷移到這里的。

[49]?下文分析了?REF _Ref517285580 \h? \* MERGEFORMAT?RT調(diào)度的do_schedule()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380035003500380030000000的實(shí)現(xiàn)。

[50]?tasklet_work_scheduled的設(shè)置在本章?REF_Ref517287690 \r \h??\* MERGEFORMAT?1 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380037003600390030000000.處完成在RT調(diào)度中，tasklet_work_scheduled置位會(huì)使調(diào)度器在選擇任務(wù)使選中idle_vcpu，idle_vcpu內(nèi)有tasklet處理函數(shù)入口do_tasklet()。

[51]?sd變量描述同本章?REF _Ref517288519 \r \h? \* MERGEFORMAT?2 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380038003500310039000000

[52]?可執(zhí)行狀態(tài)RUNSTATErunnable遇到tasklet占用、高優(yōu)先級(jí)的vcpu等是會(huì)被調(diào)度出去的。

[53]?state元素記錄vcpu當(dāng)前所處狀態(tài)：RUNSTATE_running、RUNSTATE_runnable、RUNSTATE_blocked、RUNSTATE_offline，詳情可見(jiàn)章節(jié)?REF _Ref517290931 \h? \* MERGEFORMAT?描述Xen的調(diào)度單位vcpu?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200390030003900330031000000。

[54]?vcpu進(jìn)入當(dāng)前狀態(tài)的時(shí)間。

[55]?state元素的4個(gè)狀態(tài)，分別對(duì)應(yīng)數(shù)組中的四個(gè)元素，記錄有當(dāng)前vcpu在四個(gè)狀態(tài)的累計(jì)時(shí)間。

[56]?init_timer(&v->periodic_timer,vcpu_periodic_timer_fn, v, v->processor);詳見(jiàn)章節(jié)REF _Ref517280274 \h??\* MERGEFORMAT?軟定時(shí)器機(jī)制structtimers和struct timer?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380030003200370034000000。

[57]?通過(guò)evtchn_port_set_pending()向vcpu發(fā)送了一個(gè)中斷信號(hào)，章節(jié)’?REF _Ref517344185 \h? \* MERGEFORMAT?Xen向GuestOS伸出了魔爪?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300340034003100380035000000可能有。

[58]?這又是一個(gè)大活兒啊，另外還涉及到Xen對(duì)中斷機(jī)制的操作，同樣去章節(jié)’?REF _Ref517344185 \h? \* MERGEFORMAT?Xen向GuestOS伸出了魔爪?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300340034003100380035000000可能有。

[59]?migrate_timer()完成，詳見(jiàn)章節(jié)?REF_Ref517280274 \h??\* MERGEFORMAT?軟定時(shí)器機(jī)制structtimers和struct timer?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380030003200370034000000(不一定有)。

[60]?context_switch()需要做很多很多事，不過(guò)功能卻只有一個(gè)，任務(wù)切換，于是先不分析細(xì)節(jié)。

[61]?還好我已經(jīng)搞明白了不少。

[62]?查找到3處使用runq_tickle()的位置，分別是vcpu剛醒、上下文切換時(shí)剛保存完當(dāng)前vcpu現(xiàn)場(chǎng)，調(diào)度完

[63]?詳見(jiàn)章節(jié)REF _Ref517353329 \h??\* MERGEFORMAT?RT調(diào)度的私有數(shù)據(jù)結(jié)構(gòu)?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350033003300320039000000。

[64]?下文中REF _Ref517362375 \h??\* MERGEFORMAT?snext->last_start = now; 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300360032003300370035000000在下一個(gè)vcpu投入運(yùn)行前更新了此元素。

[65]?在注釋中看到，這個(gè)時(shí)長(zhǎng)計(jì)算在嵌入式虛擬化中似乎會(huì)出現(xiàn)負(fù)數(shù)的錯(cuò)誤，并未弄清如何產(chǎn)生。

[66]?在此處RT調(diào)度的預(yù)算只可能被減少，另外有一個(gè)timer會(huì)調(diào)用repl_timer_handler()來(lái)為失去預(yù)算的vcpu補(bǔ)充預(yù)算。詳見(jiàn)章節(jié)REF _Ref517354017 \h??\* MERGEFORMAT?RT調(diào)度的預(yù)算補(bǔ)充?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350034003000310037000000。

[67]?flags同樣是struct rt_vcpu的元素，定義有詳盡的標(biāo)志位，詳見(jiàn)章節(jié)REF _Ref517353329 \h??\* MERGEFORMAT?RT調(diào)度的私有數(shù)據(jù)結(jié)構(gòu)?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350033003300320039000000。

[68]?根據(jù)注釋，RTDS_extratime標(biāo)志是想讓進(jìn)程有多x輪的預(yù)算，以至于在沒(méi)有優(yōu)先級(jí)比他高的vcpu，他就可以一直跑？因?yàn)槟J(rèn)sched_init_vcpu()創(chuàng)建vcpu時(shí)都會(huì)alloc_vdata()，alloc_vdata()是scheduler的接口，在RT的實(shí)現(xiàn)都給加了此標(biāo)志。只有在hypercall的do_domctl() XEN_DOMCTL_SCHEDOP_putvcpuinfo操作是沒(méi)有XEN_DOMCTL_SCHEDRT_extra標(biāo)志時(shí)，才會(huì)被清楚此標(biāo)志位。

[69]?我很懷疑這種操作的合理性，

[70]?表示vcpu預(yù)算耗盡，在之后的處理中將會(huì)被加入到預(yù)算耗盡的vcpu鏈表，等待補(bǔ)充預(yù)算。

[71]?tasklet需要處理標(biāo)志，詳見(jiàn)REF _Ref517358187 \h??\* MERGEFORMAT?在schedule()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350038003100380037000000的?REF_Ref517287690 \h??\* MERGEFORMAT?switch ( *tasklet_work ) 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380037003600390030000000。

[72]?此種情況發(fā)生在tasklet_list的任務(wù)在tasklet觸發(fā)后，發(fā)現(xiàn)需要此pcpu執(zhí)行，即當(dāng)前pcpu的tasklet_work_to_do被置位了，于是在調(diào)度時(shí)遇到，則需要執(zhí)行。詳見(jiàn)章節(jié)REF _Ref517291038 \h??\* MERGEFORMAT?在start_xen()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200390031003000330038000000的?REF_Ref517357878 \h??\* MERGEFORMAT?tasklet_subsys_init(); 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350037003800370038000000

[73]?算法選擇可投入執(zhí)行的vcpu

[74]?vcpu所在struct domain中有struct cpupool，cpupool內(nèi)cpu_valid用位圖表示可用pcpu們。

[75]?vcpu中有cpu_hard_affinity位圖，表示vcpu僅可在哪幾個(gè)pcpu上執(zhí)行。

[76]?smp_processor_id()可獲得。

[77]?找到的第一個(gè)vcpu即為投入運(yùn)行的vcpu，于是此鏈表順序很重要，包含調(diào)度原則。

[78]?沒(méi)有暫停標(biāo)志和暫停計(jì)數(shù)，并且其所在域也沒(méi)有

[79]?在rt_context_saved()這個(gè)vcpu會(huì)被加入到RunQ，rt_context_saved()是在啟動(dòng)投運(yùn)vcpu前執(zhí)行的context_saved()里調(diào)用。

[80]?跨pcpu的任務(wù)遷移必然會(huì)引起大量cache miss，降低效率，因此原則上跨pcpu的調(diào)度應(yīng)該有一定阻尼，很明顯Xen的RT沒(méi)有做。

[81]章節(jié)?REF_Ref517358187 \h??\* MERGEFORMAT?在schedule()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350038003100380037000000中?REF_Ref517287151 \h??\* MERGEFORMAT?next_slice = sched->do_schedule(sched, now,tasklet_work_scheduled); 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380037003100350031000000也有介紹，?REF_Ref517362153 \h??\* MERGEFORMAT?if ( next_slice.migrated ) sched_move_irqs(next); 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300360032003100350033000000同樣根據(jù)此處判斷結(jié)果。

[82]?章節(jié)REF _Ref517358187 \h??\* MERGEFORMAT?在schedule()?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300350038003100380037000000中?REF_Ref517363192 \h??\* MERGEFORMAT?設(shè)置投運(yùn)任務(wù)的運(yùn)行時(shí)間?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003300360033003100390032000000時(shí)使用此元素。

[83]?詳見(jiàn)章節(jié)REF _Ref517280274 \h??\* MERGEFORMAT?軟定時(shí)器機(jī)制structtimers和struct timer?08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F005200650066003500310037003200380030003200370034000000。

[84]?先從RunQ/DeplQ鏈表取出，再插入，可以重新決定vcpu進(jìn)RunQ/DeplQ，如果進(jìn)入RunQ還可以重新排列其位置。

[85]?此處預(yù)算剛補(bǔ)充完畢，應(yīng)該會(huì)插回RunQ。

[86]?因?yàn)閄en的RT調(diào)度所有pcpu共用待RunQ鏈表，經(jīng)過(guò)重新充能先后時(shí)可能出現(xiàn)低優(yōu)先級(jí)被先執(zhí)行的情況的。

[87]?runq_tickle()會(huì)檢查指定scheduler的新加vcpu是否有機(jī)會(huì)調(diào)度，如果有，則觸發(fā)調(diào)度軟中斷。

[88]?rt_update_deadline()操作。

[89]?標(biāo)志vcpu在pcpu上執(zhí)行。

[90]?如果被喚醒vcpu優(yōu)先級(jí)高的話。

[91]?每個(gè)RT調(diào)度的scheduler實(shí)體有3個(gè)鏈表，多個(gè)scheduler(RT/Credit)共存是可能的。

[92]?源文件中存在注釋表述的是CPU pool，用pcpu是為了不用解釋CPU pool。

[93]?排列順序是優(yōu)先級(jí)高在前，同優(yōu)先級(jí)的deadline緊急的靠前。

[94]?排列順序同樣是優(yōu)先級(jí)高在前，同優(yōu)先級(jí)的deadline緊急的靠前與RunQ用同樣的插入函數(shù)和優(yōu)先級(jí)比較方式。

[95]?rt_vcpu_sleep()是調(diào)度器接口sleep的RT實(shí)現(xiàn)

[96]?rt_vcpu_remove()是調(diào)度器接口remove_vcpu的RT實(shí)現(xiàn)，在銷(xiāo)毀vcpu(sched_destroy_vcpu())、遷移domain(sched_move_domain())被使用。

[97]?rt_context_saved()是調(diào)度器context_saved的RT實(shí)現(xiàn)，

[98]?vcpu初始化、vcpu喚醒也會(huì)執(zhí)行rt_update_deadline()操作。

?