|
Linux Kernel 排程機(jī)制介紹 hlchou@mail2000.com.tw by loda. 2011/12/2 多核心架構(gòu)儼然是目前智慧型手機(jī)方案的新趨勢(shì),隨著省電與效能上的考量,多核心的架構(gòu)各家方案也都有所差異.為能讓同一個(gè)Linux Kernel在不同效能的處理器上能即時(shí)運(yùn)作,其中關(guān)鍵的部份便是核心的排程機(jī)制,也因此本文將以此為主題進(jìn)行介紹,希望能對(duì)目前投入這領(lǐng)域的開發(fā)者有所助益. 前一段時(shí)間,看到Qualcomm關(guān)於Snapdragon S4產(chǎn)品的新聞,這產(chǎn)品最讓人印象深刻的部份在於它支援a(chǎn)SMP(Asynchronous Symmetrical Multi-Processing)的處理器架構(gòu),基於ARMv7 Dual/Quad-Core 的Krait多核心處理器架構(gòu),可讓個(gè)別處理器根據(jù)執(zhí)行時(shí)期的負(fù)荷,動(dòng)態(tài)調(diào)整時(shí)脈(根據(jù)晶片型號(hào)差異,時(shí)脈最高可達(dá) 2.5Ghz)與電壓的DCVS (Dynamic Clock and Voltage Scaling)技術(shù). 每個(gè)aSMP的處理器都能獨(dú)立的調(diào)整電壓與時(shí)脈,並能夠關(guān)閉用不到的處理器,節(jié)省功耗. 由於可以根據(jù)需求個(gè)別調(diào)整主處理器的時(shí)脈,因此在aSMP架構(gòu)下,當(dāng)需要有類似Companion處理器的角色時(shí),就可以把其中一個(gè)主處理器降頻,同時(shí)兼顧到省電與執(zhí)行低算運(yùn)需求的目的 (Qualcomm採用的是28nm,省電製程.). 也因此,就無需在主處理器之外,額外提供一個(gè)運(yùn)算能力較低且低功耗的處理器,用來支援待機(jī)或是背景音樂播放的需求. 在同一則新聞中也提到NvidiaTegra3支援的Quad-Core與vSMP(Variable Symmetric Multiprocessing)架構(gòu).參考Nvidia的技術(shù)文件「Variable SMP – A Multi-Core CPU Architecture for Low Power and High Performance」,我們知道 Tegra3不同於前一代Tegra2是由兩個(gè)Cortex A9搭配一個(gè)低階ARM7的架構(gòu),以NVIDIA Kal -El的vSMP方案來說,會(huì)提供五個(gè)Cortex A9處理器(組合方式為4 個(gè)高效能Cortex A9主處理器 搭配 1個(gè)效能較低但強(qiáng)調(diào)省電的Cortex A9 Companion處理器),其中4個(gè)Cortex A9主處理器採用標(biāo)準(zhǔn)製程(時(shí)脈可到GHz.),以訴求較高的執(zhí)行效率,而剩下一個(gè)Companion Cortex A9處理器(時(shí)脈最高為500MHz),會(huì)採用低功耗(Low Power)的製程,可用於運(yùn)算量較低的待機(jī)或背景執(zhí)行需求. 基於vSMP的架構(gòu),這五個(gè)處理器,可以根據(jù)執(zhí)行的實(shí)際狀況,選擇主處理器或是Companion處理器運(yùn)作,並透過DVFS(Dynamic Voltage and Frequency Scaling) 動(dòng)態(tài)調(diào)整主處理器的頻率與電壓降低功耗,進(jìn)行Power Gating與利用目前Linux Kernel所支援的CPU Up/Down HotPlug機(jī)制,讓4個(gè)主處理器可以動(dòng)態(tài)的 CPU-Up/Down 掛起或移出Linux Kernel Tasks的排程範(fàn)圍(ex,Task Migration),以便讓閒置的處理器關(guān)閉節(jié)省功耗. 參考Tegra的WhitePaper,vSMP並不允許Companion處理器與主處理器被同時(shí)啟用,也因此Tegra3有提供軟硬體配套的CPU Governor 與 CPU Management Logic 去監(jiān)控處理器的執(zhí)行負(fù)荷,能在系統(tǒng)繁忙時(shí),關(guān)閉Companion CPU,把工作轉(zhuǎn)到4個(gè)主處理器上執(zhí)行,並監(jiān)控處理器執(zhí)行負(fù)載,動(dòng)態(tài)調(diào)整主時(shí)脈與哪個(gè)主處理器能被卸載. 也就是說,如果是處於待機(jī)或是背景音樂播放,系統(tǒng)就只開啟Companion 處理器,但若是需要上網(wǎng)或執(zhí)行更繁重的工作,就會(huì)卸載Companion 處理器,然後根據(jù)需求開啟1個(gè),2個(gè)或同時(shí)把4個(gè)主處理器致能. 基於這樣的設(shè)計(jì),也能對(duì)主處理器的時(shí)脈進(jìn)行調(diào)整,但不同於aSMP架構(gòu)的是,這4個(gè)主處理器的時(shí)脈會(huì)調(diào)整為一樣的時(shí)脈,要拉高就一起拉高,要降低就一起降低,因此對(duì)Linux Kernel的排程來說,並不會(huì)有參與排程的處理器運(yùn)算能力不一致的問題. 相對(duì)於上述提到的aSMP或vSMP架構(gòu),我們比較跟使用一個(gè)效率高的主處理器搭配一個(gè)省電且運(yùn)算能力較弱的Companion處理器的差異,例如 ARM9/ARM11 +DSP 或是一個(gè) Cortex A9 + ARM7,由於這兩個(gè)主處理器與Compaion處理器基礎(chǔ)架構(gòu)不同,兩個(gè)處理器的Memory Management與L2 Cache並沒有共用,甚至兩者在指令集的層次就完全不同,例如ARM環(huán)境中運(yùn)作的Linux Kernel配置好的記憶體分頁,或是多工環(huán)境下的Tasks,就不能直接透過排程分到DSP上運(yùn)作.而是必須在設(shè)計(jì)階段,就考慮到這兩個(gè)處理器協(xié)同運(yùn)作的配套機(jī)制,例如Linux Kernel,人機(jī)介面與檔案系統(tǒng)是運(yùn)作在ARM端,而Audio Codec是放在DSP上執(zhí)行,此時(shí)會(huì)由ARM去處理人機(jī)介面互動(dòng)並透過檔案系統(tǒng)把音樂檔案載入,讓DSP端可以播放. 兩個(gè)處理器之間,需要設(shè)計(jì)彼此溝通的介面機(jī)制,隨著應(yīng)用情境的多元化,在設(shè)計(jì)上的複雜度也會(huì)相對(duì)增加. 而aSMP與vSMP的優(yōu)點(diǎn)在於上面的主處理器與Companion處理器採用同樣的核心技術(shù),有一樣的指令集,共用同樣的Memory Management記憶體管理與L2 Cache共用. 以vSMP來說, Companion處理器跟主處理器有各自的L1 Cache,但共用同樣的L2 Cache與Memory Management,因此當(dāng)Linux Kernel在上面運(yùn)作時(shí),包括4GB的記憶體分頁,應(yīng)用程式的多工執(zhí)行環(huán)境,就能在有開啟Linux Kernel CPU Up/Down HotPlug的機(jī)制下無縫銜接,且上面運(yùn)作的Task能跨不同的處理器進(jìn)行Task Migration,無需解決跨到不同處理器與映射到不同記憶體空間的複雜問題. 談到這,不論是aSMP或是vSMP都有其擁護(hù)者,並能充分發(fā)揮Linux Kernel CPU Up/Down HotPlug的特性,也都各自具備相當(dāng)?shù)陌l(fā)展?jié)摿? 但要能讓這樣的設(shè)計(jì)充分發(fā)揮效益,還有一些在核心與排程機(jī)制上,需要優(yōu)化的空間. 以目前Linux Kernel的Tasks排程機(jī)制實(shí)作來說,並沒有考慮到每個(gè)處理器具備不同運(yùn)算能力的條件,就算是對(duì)處理器有Load Weight的計(jì)算,也是以該處理器所負(fù)荷的排程單元Load Weight來做統(tǒng)計(jì),只能反映出哪個(gè)處理器目前排程單元的負(fù)荷,但並不能根據(jù)個(gè)別處理器的效能,而給予合理的排程負(fù)荷計(jì)算參數(shù). 因此,如果有一個(gè)aSMP架構(gòu)的處理器動(dòng)態(tài)把時(shí)脈降低,而這處理器又跟其他運(yùn)算能力較高的處理器一起進(jìn)行Tasks排程,就有可能讓重要的Task被放到運(yùn)算能力較低,且當(dāng)下負(fù)荷又已經(jīng)過重的處理器上執(zhí)行,而導(dǎo)致在產(chǎn)品端的執(zhí)行效果不如預(yù)期. 本文,會(huì)把焦點(diǎn)放在排程機(jī)制的介紹上,有關(guān)產(chǎn)品上的實(shí)作與技術(shù)問題,開發(fā)者可以根據(jù)自己所面對(duì)的平臺(tái)與對(duì)於核心排程技術(shù)的了解,來進(jìn)行設(shè)計(jì). 本文主要參考的Linux核心有 2.6.10, 2.6.38.6 與 3.0.4,但由於Linux核心仍在持續(xù)的演進(jìn)中,若你使用的版本跟筆者不同,還請(qǐng)以你手中的Linux Kernel Source Code為依據(jù). 最後,所有的內(nèi)容筆者會(huì)盡力確保資訊的正確性,若有不足之處,還請(qǐng)不吝指教. Linux Kernel 的排程機(jī)制. 如下圖所示,在linux Kernel 2.4 時(shí),多核心的架構(gòu)下是共用同一個(gè)Task Queue,且採用O(N)排程算法,在排程效率與對(duì)多核心的支援是相對(duì)較弱的.
在linux Kernel 2.6 時(shí),每個(gè)處理器都有兩個(gè)Task Queue,當(dāng)位於Active Task Queue的行程執(zhí)行完畢,就會(huì)依據(jù)行程的優(yōu)先級(jí),計(jì)算Priority與Time Slice,然後放到Expired Task Queue中,當(dāng)Active Task Queue執(zhí)行完畢後,就會(huì)Switch這兩個(gè)Task Queue,讓經(jīng)過計(jì)算後的新Active Task Queue可以立刻加入排程.
struct task_struct { volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ struct thread_info *thread_info; atomic_t usage; unsigned long flags; /* per process flags, defined below */ unsigned long ptrace; int lock_depth; /* Lock depth */ int prio, static_prio; struct list_head run_list; ….. } 而結(jié)構(gòu)list_head的宣告如下所示, struct list_head { struct list_head *next, *prev; }; 在每個(gè)Task被產(chǎn)生時(shí),會(huì)透過巨集INIT_LIST_HEAD初始化Task的run_list,把Link List的頭尾 next/prev都指向自己,而在Task被排入執(zhí)行時(shí)就會(huì)透過函式enqueue_task執(zhí)行巨集list_add_tail把Task的Link List放到對(duì)應(yīng)的Priority Link List 結(jié)尾,而在Task被移出執(zhí)行時(shí),就會(huì)透過函式dequeue_task執(zhí)行巨集list_del,把Task的Link List從對(duì)應(yīng)的Priority Link List移出. 執(zhí)行的概念如下圖所示,
對(duì)同一個(gè)Task Priority來說,被排定執(zhí)行的Task就會(huì)透過 run_list Link List串連起來,依序執(zhí)行,並且在移除執(zhí)行時(shí),從Link List Node中移出. 參考kernel/sched.c中的原始碼, Priority Array會(huì)根據(jù)目前140個(gè)Priority層級(jí) (MAX_PRIO=140),幫每個(gè)Task Priority都配置一個(gè)Link List的 Queue Head,並且用unsigned long針對(duì)這140個(gè)Priority層級(jí),透過Bits為0或1,來表示該Task Priority層級(jí)是否有需要被執(zhí)行的Task在排程等待執(zhí)行中,相關(guān)代碼如下所示 #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)) struct prio_array { unsigned int nr_active; unsigned long bitmap[BITMAP_SIZE]; struct list_head queue[MAX_PRIO]; }; 如下圖所示,以目前140bits的Task Priroty來說,會(huì)透過五個(gè)unsigned long,來表示完整的140bits.
執(zhí)行時(shí)期,再透過巨集sched_find_first_bit （這部份會(huì)依據(jù)平臺(tái)以處理器優(yōu)化的指令集來處理）,針對(duì)這140bits,找出第一個(gè)目前有Task在其中等待執(zhí)行的Task Priority. 整體運(yùn)作的概念,如下圖所示
雖然有了O(1)的實(shí)作,而且基於這實(shí)作,也確實(shí)可以很快讓排程機(jī)制很有效率的運(yùn)作,然而處理器雖然是具備多工的能力,但真實(shí)的情況下,一個(gè)處理器同一時(shí)間只能執(zhí)行一個(gè)Task,也就是說,在不考慮觸發(fā)中斷與重新觸發(fā)排程機(jī)制的情況下,在當(dāng)前Task的Time Slice尚未執(zhí)行完畢前,其他的Task是沒有機(jī)會(huì)被執(zhí)行的. 也因此,在Linux Kernel 2.6.23之後,Linux核心採用了新的 CFS(Completely Fair Scheduler)排程機(jī)制(作者為Ingo Molnar),希望可以基於排程的改善,盡可能的讓每個(gè)不同等級(jí)的Task可以更公平的分配到處理器的時(shí)間,基於RB Tree的概念,可以讓越少被執(zhí)行到的Task,有更高的優(yōu)先機(jī)率被處理器執(zhí)行到,避免優(yōu)先級(jí)較低的Task,被延遲較久的時(shí)間才得到被處理器執(zhí)行的機(jī)會(huì). 參考Linux Kernel 3.0.4中有關(guān)CFS的Design文件 (路徑在Documentation/scheduler/sched-design-CFS.txt),作者試著用一句 "CFS basically models an "ideal, precise multi-tasking CPU" on real hardware." 來簡要說明CFS 80%設(shè)計(jì)精神 .所謂理想的多工處理器,就是當(dāng)處理器有100%的能力,且系統(tǒng)中有兩個(gè)Tasks正在運(yùn)作,這兩個(gè)Tasks可以各自取得處理器50%的執(zhí)行能力,並被處理器平行執(zhí)行,也就是說任意時(shí)間間隔來看(例如,隨機(jī)取10ms間隔),這兩個(gè)Tasks都是分配到處理器50%的執(zhí)行能力. 以實(shí)際的處理器運(yùn)作行為來說,一個(gè)處理器同一時(shí)間只能執(zhí)行一個(gè)Task,當(dāng)這個(gè)Task Time-Slice結(jié)束後,會(huì)透過Context-Switch切換下一個(gè)Task進(jìn)來執(zhí)行,當(dāng)系統(tǒng)中的Tasks個(gè)數(shù)便多時(shí),在特定的時(shí)間間隔來看,處理器等於執(zhí)行特定Task的時(shí)間較長,而對(duì)於優(yōu)先級(jí)較低的Task,卻可能在該區(qū)間中都沒有得到執(zhí)行權(quán). 換個(gè)角度來說,Tasks有優(yōu)先級(jí)也有Time Slice長度的區(qū)別,假設(shè)Task #A Time Slice長度為10ms,以總Tasks數(shù)量與總Time Slice長度來說,會(huì)取得處理器5%的執(zhí)行時(shí)間,最理想的狀況是,我們?cè)谌我庖幻氲拈g隔來看,Task#A都可以分到處理器5%的執(zhí)行時(shí)間,但在現(xiàn)實(shí)的狀況來說,在任意一秒的間隔來看,只要有優(yōu)先級(jí)高的Task被排程到,且該Task分配到的Time Slice較長,就會(huì)讓Task#A呈現(xiàn)在一個(gè)不公平的時(shí)間分配中. 雖然,用較長的時(shí)間來看一定是公平的,但CFS希望解決的就是讓目前處理器執(zhí)行的機(jī)制上,可以盡可能的做到即時(shí)的公平. 因此,CFS導(dǎo)入了"Virtual Runtime"的概念(單位為nanosec),根據(jù)目前總共的Tasks數(shù)量,用以作為選擇下一個(gè)執(zhí)行Task Time Slice的依據(jù).例如,CFS會(huì)選擇目前p->se.vruntime值最低的Task來執(zhí)行(也就是距離上一次被執(zhí)行時(shí)間間隔最久的Task),會(huì)在每一次觸動(dòng)排程機(jī)制時(shí),盡可能的達(dá)到"理想的多工處理器"的目標(biāo). 然而,在實(shí)際Linux Kernel的Time Slice與Priority來看,CFS的概念還必須要考慮到依據(jù)每個(gè)Task的Nice Value所計(jì)算的Time Slice長度不一定每個(gè)Task都一切,而且每個(gè)Task的Real-Time Priority值也不盡相同,有關(guān)Task 計(jì)算Time Slice與Real-Time Priority的說明,會(huì)另外在下一段文章中介紹. 每次Scheduler Tick觸發(fā)時(shí),所進(jìn)行的動(dòng)作 不論是O(N),O(1)與CFS,系統(tǒng)的排程都是基於固定的Scheduling Tick來觸發(fā),也因此,每一次的Scheduling Tick觸發(fā),都攸關(guān)Task執(zhí)行的週期與是否要進(jìn)行Task的切換,也是排程機(jī)制核心的部分. Linux Kernel的Scheduling機(jī)制,會(huì)根據(jù)編譯核心時(shí)配置的HZ值來決定,一般來說是每1/100秒或每1/1000秒觸發(fā)一次Scheduling Tick,讓系統(tǒng)的排程機(jī)制可以去計(jì)算每個(gè)Task執(zhí)行的時(shí)間,並藉此決定是不是要進(jìn)行Task Context-Switch. 以支援CFS的Linux Kernel 2.6.38.6來說,每次觸發(fā)Scheduling Tick都會(huì)執(zhí)行下述的動(dòng)作 1,取得目前的CPU ID,與目前CPU的 RunQueue指標(biāo),與目前RunQueue中正在執(zhí)行的Curr Task指標(biāo) 2,呼叫 sched_clock_tick (實(shí)作在kernel/sched_clock.c中),這函式需在有設(shè)定Unstable CPU Clock時(shí)才有作用,如果全域變數(shù)sched_clock_stable為1,這個(gè)函式就會(huì)不作用直接返回.(ARM環(huán)境中,這個(gè)變數(shù)並無作用.) 3,取得 RunQueue SpinLock 4,呼叫update_rq_clock (實(shí)作在kernel/sched.c中), 若runQueue沒有設(shè)定skip_clock_update,這函式會(huì)更新RunQueue的Clock值.並呼叫函式update_rq_clock_task, 更新RunQueue clock_task值,clock_task會(huì)把前後兩次RunQueue Clock的Delta值,減去處理器進(jìn)行Soft-IRQ與Hardware-IRQ的時(shí)間差值後,對(duì)clock_task進(jìn)行累加. 可用以反應(yīng)出RunQueue中Task實(shí)際被處理器執(zhí)行的時(shí)間累加值. 5,呼叫update_cpu_load_active,會(huì)透過函式update_cpu_load在每次Tick觸發(fā)時(shí),更新RunQueue cpu_load Array,用以反應(yīng)目前RunQueue所在的處理器負(fù)載. 6,執(zhí)行目前Task 所在Class的Tick函式(ex, curr->sched_class->task_tick),若Current Task是屬於Fair Class,就會(huì)呼叫task_tick_fair (實(shí)作在kernel/sched_fair.c中). 依序若Current Task為Stop/Real-Time/Idle Scheduling Class就會(huì)呼叫函式 task_tick_stop/ task_tick_rt/ task_tick_idle. 7,釋放RunQueue SpinLock 8,呼叫perf_event_task_tick (若編譯時(shí),沒設(shè)定CONFIG_PERF_EVENTS,這函式會(huì)是inline的空函式),主要用以支援核心處理器效能的監(jiān)聽動(dòng)作. 9,在SMP架構(gòu)下,會(huì)呼叫函式idle_cpu,用以更新RunQueue的idle_at_tick值,為1表示目前CPU RunQueue執(zhí)行的是Idle Task,反之為0,則非Idle Task. 可供判斷目前這RunQueue所在處理器是否處於閒置的狀態(tài). 10,在SMP架構(gòu)下,會(huì)呼叫trigger_load_balance, 若已達(dá)到RunQueue設(shè)定下一次觸發(fā)Load Balance的jiffies時(shí)間值(next_balance),就會(huì)觸發(fā)Scheduling Softare IRQ,並在Software IRQ中透過函式rebalance_domains,執(zhí)行Scheduling Domain Load Balance動(dòng)作.若未達(dá)RunQueue下一次觸發(fā)Load Balance的jiffies時(shí)間值,且在編譯核心時(shí)有設(shè)定CONFIG_NO_HZ （NO HZ可支援處理器執(zhí)行Idle Task時(shí),停止系統(tǒng)的Scheduling Tick,可在進(jìn)入pm_idle時(shí),減少Timer中斷觸發(fā)(例如HZ=100,每秒就有一百次Tick Timer中斷觸發(fā)),減少系統(tǒng)被觸發(fā)醒來的機(jī)會(huì).）,就會(huì)呼叫函式nohz_balancer_kick,Kick一個(gè)處理器進(jìn)行No Hz Load Balance.被Kick選擇為進(jìn)行No Hz Load Balance的處理器所屬RunQueue的nohz_balance_kick值會(huì)設(shè)定為1. 以上總結(jié)每次觸發(fā)Scheduling Tick時(shí),主要進(jìn)行的工作內(nèi)容.接下來我們?cè)偻高^pick_next_task,看在目前系統(tǒng)支援四種Scheduling Class的排程下,一個(gè)Task是如何被撿選出來執(zhí)行的. 從pick_next_task看Scheduling Class對(duì)排程的影響 檢視CFS對(duì)不同Scheduling Class行為最好的入口就是函式pick_next_task (實(shí)作在 kernel/sched.c中),在函式pick_next_task中會(huì)執(zhí)行如下的流程找到下一個(gè)要被載入執(zhí)行的Task 1,檢查目前總Runnable Task數(shù)量是否跟放在Fair Class中的數(shù)量一致 (rq->nr_running == rq->cfs.nr_running),若成立,就執(zhí)行執(zhí)行Fair Scheduling Class的pick_next_task抓取下一個(gè)執(zhí)行的Task 2,若1不成立,就會(huì)執(zhí)行 for_each_class(class) {….}迴圈,可以參考如下define宣告 #define sched_class_highest (&stop_sched_class) #define for_each_class(class) \ for (class = sched_class_highest; class; class = class->next) 目前優(yōu)先級(jí)最高的Scheduling Class為 Stop-Task Scheduling Class,而在函式pick_next_task中,就會(huì)依序執(zhí)行 Stop-Task, Real-Time,Fair 與 Idle-Task Scheduling Class所實(shí)作的pick_next_task函式,先找到的Task就會(huì)由函式pick_next_task回傳. 也因此,當(dāng)有Task存在 Stop-Task或是Real-Time Scheduling Class中時(shí),這時(shí)屬於Fair Scheduling Class中的Task執(zhí)行的優(yōu)先級(jí)就會(huì)降低. 總結(jié)運(yùn)作的概念,可以參考下圖所示
CSF RBTREE(Red-Black Tree) – O(Log2(N)) CFS挑選Task的機(jī)制為RB-Tree,概念如下圖所示,包括Task或是Task Group,都會(huì)是RBTree中的一個(gè)Node支點(diǎn),每次選擇Task來執(zhí)行時(shí),都會(huì)選擇左邊目前Virtual RunTime最低的Task(也就是最久沒有被執(zhí)行到的Task)來執(zhí)行,雖然Virtual RunTime會(huì)根據(jù)Task的Priority而有增長的差異,例如:Nice Priority低的Task Virutal RunTime會(huì)增長的比較快,相對(duì)佔(zhàn)據(jù)處理器執(zhí)行的時(shí)間就會(huì)比較短,反之,Nice Priority 高的Task會(huì)因?yàn)閂irutal RunTime增長的慢,而得到相對(duì)比較多實(shí)際的處理器執(zhí)行時(shí)間. 但在理想的情況下,如果大家都是Nice 0的情況,基於CFS RBTree的機(jī)制,可以讓多數(shù)的Task能相對(duì)均勻的得到處理器的執(zhí)行時(shí)間,而避免有特定的Task等待比較久的時(shí)間沒有得到處理器的執(zhí)行機(jī)會(huì).
對(duì)CFS與RBTree建立基本的概念後,接下來讓我們進(jìn)一步的探討處理器排程RunQueue的資料結(jié)構(gòu),更清楚的掌握排程運(yùn)作的內(nèi)涵. 處理器的RunQueue 在目前的Linux Kernel中,每個(gè)處理器都會(huì)配置一個(gè)RunQueue,而從了解RunQueue的資料結(jié)構(gòu)著手,我們能對(duì)排程的運(yùn)作有更清楚的藍(lán)圖,進(jìn)而在程式碼的閱讀上,可以更加清晰. 在本節(jié),筆者會(huì)把RunQueue的資料結(jié)構(gòu)struct rq (宣告在 kernel/sched.c中)進(jìn)行介紹,讓各位可以知道核心排程是基於哪些參數(shù)進(jìn)行運(yùn)作,這參數(shù)的內(nèi)容比較繁瑣,建議可以先有個(gè)概念,若有興趣進(jìn)一步探究的,再回到本節(jié)即可. 如下所示,處理器RunQueue主要包含以下的參數(shù)與對(duì)應(yīng)的說明
至此,有關(guān)RunQueue的結(jié)構(gòu)說明告一段落. CFS的Scheduling Classes 與 Scheduling Policies CFS排程機(jī)制在設(shè)計(jì)時(shí),考慮到排程機(jī)制的彈性,定義了Scheduler Class的機(jī)制,讓排程機(jī)制可以根據(jù)設(shè)計(jì)的需求,延伸不同的排程模組進(jìn)來,每個(gè)新加入的排程機(jī)制都必須要提供Scheduler Class的實(shí)作,結(jié)構(gòu)為 struct sched_class (定義在檔案include/linux/sched.h中). 舉sched_fair.c的實(shí)作來說, Scheduler Class實(shí)作的宣告如下
其中相關(guān)函式的行為簡述如下
此外,在Linux Kernel SMP的架構(gòu)下,還會(huì)支援如下的函式
有關(guān)的巨集 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) #define this_rq() (&__get_cpu_var(runqueues)) #define task_rq(p) cpu_rq(task_cpu(p)) #define cpu_curr(cpu) (cpu_rq(cpu)->curr) #define raw_rq() (&__raw_get_cpu_var(runqueues)) sched_class Class中宣告的Method,就是要在Linux Kernel排程中新增一個(gè)Scheduler Class所要實(shí)作的內(nèi)容,讓Linux Kernel可以根據(jù)不同行程的需求,調(diào)度這些在系統(tǒng)中有註冊(cè)的排程模組,讓系統(tǒng)可以達(dá)到預(yù)定的執(zhí)行目標(biāo)與行為. 以Linux Kernel 2.6.38來說,目前共支援4種Scheduler Class,包括 1,Fair Scheduler Class (實(shí)作在檔案 sched_fair.c中): 目前包括有 1.a, SCHED_NORMAL (也稱為SCHED_OTHER): 主要用以排程一般目的的Task. 1.b, SCHED_BATCH: 主要用以讓Task可以延長執(zhí)行的時(shí)間(Time Slice),減少被中斷發(fā)生Task Context-Switch的次數(shù).藉此可以提高 Cache的利用率 (每次Context-Switch都會(huì)導(dǎo)致Cache-Flush). 比較適合用在固定週期執(zhí)行的Batch Jobs任務(wù)主機(jī)上,而不適合用在需要使用者互動(dòng)的產(chǎn)品 (會(huì)由於Task切換的延遲,而感覺到系統(tǒng)效能不佳或是反應(yīng)太慢). 2,Real-Time Scheduler Class (實(shí)作在檔案 sched_rt.c中): 支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR. (SCHED_RR task預(yù)設(shè)的 Time Slice長度為100 msecs.). 3,Idle Task Scheduler Class (實(shí)作在檔案 sched_idletask.c中): 支援SCHED_IDLE,為系統(tǒng)中的Idle Task排程. 4,Stop Scheduler Class (實(shí)作在檔案 sched_stoptask.c中):屬於 Stop-Task Scheduling Class的Task是屬於系統(tǒng)中最高權(quán)限的Task,會(huì)中斷所有任務(wù)的執(zhí)行,並且不會(huì)被其他任務(wù)所中斷. 目前系統(tǒng)中,Scheduling Class的優(yōu)先級(jí)順序?yàn)?Stop-Task > Real-Time > Fair > Idle-Task,開發(fā)者可以根據(jù)自己的設(shè)計(jì)需求,來把所屬的Task配置到不同的Scheduling Class中. 在支援Fair Group Scheduling環(huán)境下,以CGroup (Control Group) Scheduler分配Task與Group的處理器執(zhí)行時(shí)間. Control Group 提供了Linux核心可以把Tasks進(jìn)行整合/區(qū)分或是依據(jù)子Group進(jìn)行分派的動(dòng)作. 根據(jù)Control Group文件中的定義,一個(gè)CGroup可以關(guān)聯(lián)到屬於1或多組SubSystem中的多個(gè)Tasks. SubSystem主要是基於CGroup提供的Task Group機(jī)制,扮演類似資源管控的角色,用以設(shè)定調(diào)配每個(gè)Group使用資源的限制. 在支援Control Group的Linux Kernel中,每一個(gè)Task在系統(tǒng)中都會(huì)屬於一個(gè)CGroup與一個(gè)SubSystem,每一個(gè)SubSystem都會(huì)有一個(gè)系統(tǒng)設(shè)定的組態(tài),並配置到對(duì)應(yīng)的CGroup中. 每一個(gè)Hierarchy架構(gòu),都有一個(gè)屬於CGroup虛擬檔案系統(tǒng)的Instance參考. 在系統(tǒng)運(yùn)作時(shí),會(huì)有多個(gè)有從屬關(guān)係的Task Groups同時(shí)運(yùn)作,每一個(gè)Hierarchy都會(huì)屬於這系統(tǒng)中所有Tasks的一部分. 使用者可以透過CGroup虛擬檔案系統(tǒng)中的目錄名稱產(chǎn)生或刪除對(duì)應(yīng)的CGroup,並可以查詢哪個(gè)CGroup有Task被指派,或是列出對(duì)應(yīng)CGroup中所有被指派的Task PIDs. 藉由CGroup的設(shè)計(jì),還可支援基於使用者帳號(hào)(Account)的處理器資源調(diào)配目的.(包括可以限定能使用的處理器或是Memory Node.) 參考 include/linux/cgroup_subsys.h的實(shí)做,目前CGroup包括以下的SubSystem, 1,cpuset (CONFIG_CPUSETS):用以限定指定的Tasks使用的CPU與Memory資源,有關(guān)cpuset的使用可以透過函式sched_setaffinity,sched_getaffinity,set_mempolicy,get_mempolicy,mbind. 例如下述的例子,可以由應(yīng)用程式透過函式sched_setaffinity指定當(dāng)應(yīng)用程式執(zhí)行時(shí),所要使用的處理器編號(hào).
2,cpu_cgroup (CONFIG_CGROUP_SCHED):這選項(xiàng)會(huì)支援Tasks能被群組(Group)化與依據(jù)設(shè)定切割群組佔(zhàn)用的處理器執(zhí)行時(shí)間. 更進(jìn)一步,還可以設(shè)定CONFIG_RT_GROUP_SCHED用以支援群組的 Real-Time排程 (支援包括 SCHED_FIFO 與 SCHED_RR). 與可以設(shè)定CONFIG_FAIR_GROUP_SCHED 用以支援群組的CFS排程機(jī)制(支援包括SCHED_NORMAL與SCHED_BATCH). 3,cpuacct (CONFIG_CGROUP_CPUACCT):這選項(xiàng)用以支援CPU Accounting Controller機(jī)制,透過CGroup機(jī)制群組Task,並依據(jù)使用者的帳號(hào)(Account)所產(chǎn)生的Task群組來劃分處理器的執(zhí)行時(shí)間. 4,debug (CONFIG_CGROUP_DEBUG):用以支援CGroup的Debug機(jī)制,像是Task Reference Count等統(tǒng)計(jì)資訊. 其它SubSystem還包括 ns (CONFIG_CGROUP_NS),mem_cgroup (CONFIG_CGROUP_MEM_RES_CTLR),devices (CONFIG_CGROUP_DEVICE),freezer (CONFIG_CGROUP_FREEZER),net_cls (CONFIG_NET_CLS_CGROUP),blkio (CONFIG_BLK_CGROUP). 在一個(gè)基於CGroup FileSystem的 Task-Group機(jī)制下,會(huì)統(tǒng)籌100%的處理器資源. 所有的處理器支援會(huì)根據(jù)root_task_group與所屬的子Task-Group的 Weight (=se->load.weight)基於Fair-Scheduling機(jī)制來進(jìn)行處理器資源的分配工作. 舉實(shí)際的例子來說,當(dāng)root_task_group中有十個(gè)Tasks且每個(gè)Task的Weight值為1024,在root_task_group之下又有兩個(gè)子Task Groups且這兩個(gè)子Task Group的Weight也都為1024,此時(shí)這兩個(gè)子Task Group所分配到的處理資源為 1024 / (10*1024 + 1024 + 1024) = 8.33% . 我們可以參考如下操作流程,產(chǎn)生一個(gè)驗(yàn)證Control Group的目錄,並在其中產(chǎn)生cpu目錄,並掛起CPU與CGroup相關(guān)的Device Node. [root@localhost ~]# mkdir /cgroup [root@localhost ~]# mount -t tmpfs cgroup_root /cgroup [root@localhost ~]# mkdir /cgroup/cpu [root@localhost ~]# mount -t cgroup -ocpu none /cgroup/cpu [root@localhost ~]# ls /cgroup/cpu cgroup.clone_children cgroup.event_control cgroup.procs cpu.rt_period_us cpu.rt_runtime_us cpu.shares notify_on_release release_agent tasks [root@localhost ~]# 我們可以從tasks檔案看到目前處理器上所有執(zhí)行的Task Process ID,並從cpu.shares知道目前處理器所分擔(dān)的CPU Load基數(shù). 接下來,我們透過Control Group產(chǎn)生 GroupA與GroupB兩個(gè)Task Group群組,如下所示 [root@localhost cpu]# mkdir GroupA [root@localhost cpu]# mkdir GroupB 然後透過設(shè)定 cpu.shares,把GroupA的cpu.shares設(shè)定為4096,GroupB的cpu.shares設(shè)定為1024,也就是說在實(shí)際執(zhí)行上,屬於GroupA的Tasks會(huì)比 GroupB的Tasks多得到約4倍的實(shí)際處理器執(zhí)行時(shí)間. [root@localhost cpu]# echo 4096 > GroupA/cpu.shares [root@localhost cpu]# echo 1024 > GroupB/cpu.shares 接下來我們用如下的程式碼,分別編譯為GroupA與GroupB的執(zhí)行檔名稱,兩者唯一的差異只在於讓printf顯示的字串各別表示出自己是由GroupA或 GroupB所吐出的內(nèi)容而已. #include <stdio.h> #define PrintThreshold 0×10000000 int main() { int i,vCount; i=0; vCount=0; while(1) { i++; if(i>PrintThreshold) { i=0; vCount++; printf("GroupA:%ld\n",vCount); } } return 0; } 執(zhí)行編譯好的GroupA與GroupB執(zhí)行檔,兩者Process ID分別為 1738與 1739,然後把這兩個(gè)Process ID分別設(shè)定給我們已經(jīng)設(shè)定好差距四倍處理器執(zhí)行時(shí)間的兩個(gè)Control Group目錄下的檔案tasks. [root@localhost cpu]# echo 1738 > GroupA/tasks [root@localhost cpu]# echo 1739 > GroupB/tasks 我們可以透過top 指令查看這兩個(gè)程式執(zhí)行時(shí)各自所佔(zhàn)的CPU比率與兩者的差距,如下所示,GroupA佔(zhàn)據(jù)處理器約80.6%的執(zhí)行時(shí)間而GroupB佔(zhàn)據(jù)處理器約19.9%的執(zhí)行時(shí)間. (兩者相加為100.5%,超過100%,但這是筆者環(huán)境中top的真實(shí)結(jié)果(或該說誤差),在此就不作討論),以比率來說兩者所佔(zhàn)CPU實(shí)際執(zhí)行時(shí)間差距大約也是四倍,符合我們透過Control Group對(duì)Task執(zhí)行時(shí)間比率所做的設(shè)定. PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 1738 root 20 0 3880 264 212 R 80.6 0.0 2:02.50 GroupA 1739 root 20 0 3880 264 212 R 19.9 0.0 0:41.98 GroupB 再以實(shí)際的執(zhí)行結(jié)果來看,由於GroupA比GroupB多分到四倍的處理器執(zhí)行時(shí)間,也因此在Console所顯示的結(jié)果上,GroupA大約每顯示四個(gè)字串結(jié)果後,GroupB才有機(jī)會(huì)顯示一次,如此也符合我們透過Control Group所設(shè)定分配的處理器執(zhí)行資源比率. GroupA:27 GroupA:28 GroupA:29 GroupA:30 GroupB:21 GroupA:31 GroupA:32 GroupA:33 GroupA:34 GroupB:22 GroupA:35 GroupA:36 GroupA:37 GroupA:38 GroupB:23 GroupA:39 GroupA:40 GroupA:41 GroupA:42 GroupB:24 GroupA:43 GroupA:44 GroupA:45
在Control Group之後,我們?cè)籴槍?duì)原本Linux Kernel 2.6與在支援CFS排程機(jī)制後的核心排程,進(jìn)一步的加以說明.
CFS(Kernel 2.6.23)之前Linux Kernel 2.6 Time Slice與Real Time優(yōu)先級(jí)的簡要介紹 如下圖所示為CFS之前,Linux Kernel 2.6排程的優(yōu)先級(jí)機(jī)制,右邊是屬於Task Real-Time優(yōu)先權(quán)，左邊是Task的Nice Value,系統(tǒng)初始化後,一個(gè)最原始的行程產(chǎn)生時(shí),預(yù)設(shè)的Real-Time優(yōu)先權(quán)為0,而Nice優(yōu)先權(quán)亦為0. Linux Kernel會(huì)根據(jù)Nice Value來計(jì)算該Task執(zhí)行時(shí)間Time-Slice值的大小. 當(dāng)使用者把行程的Nice Value遞減時(shí)(最低為-20),就表示該行程的優(yōu)先權(quán)提高,相對(duì)的在排程時(shí)就會(huì)取得比較多的Time-Slice. 相對(duì)的,若不斷的增加Nice值(最大為19),就表示該行程的優(yōu)先權(quán)降低,所取得的Time-Slice亦較低.
但若使用者有Real-Time的需求時(shí)，希望特定的行程可以以較高的優(yōu)先權(quán)執(zhí)行,但又不希望如同增加Nice值一般,也對(duì)應(yīng)增加了Time-Slice時(shí),就必須要設(shè)定屬於Real-Time的優(yōu)先權(quán). 而real-Time的優(yōu)先權(quán)最小為1，最大為99，該值越大在排程時(shí)會(huì)越先被執(zhí)行到. 有關(guān)Linux Kernel 2.6.10 核心Nice Value與對(duì)應(yīng)之Time-Slice關(guān)係,可以參考下表
如下圖所示,筆者把Nice值對(duì)應(yīng)到的Task Priority與對(duì)應(yīng)的排程機(jī)制進(jìn)行對(duì)比,我們可以看到在Task Priority 100-139 (對(duì)應(yīng)為Nice -20 – 19 或 User Priority 0-39)的區(qū)間內(nèi),為一般應(yīng)用Task的排程機(jī)制,使用的Scheduling Class為Normal與Batch,而屬於Real-Time排程機(jī)制對(duì)應(yīng)到的Task Priority為0-99,使用的Scheduling Class為Round-Robin與FIFO.
CFS在Linux Kernel 2.6.23之後,參考Tasks優(yōu)先級(jí)所施行的Time Slice與Real-Time措施 基於CFS RBTree的概念,由於會(huì)一直確保Virtual RunTime值的平衡,透過抓取佔(zhàn)據(jù)Virtual RunTime執(zhí)行時(shí)間最短的Task來執(zhí)行,因此像是原本排程中會(huì)透過Nice值計(jì)算對(duì)應(yīng)Task可運(yùn)作Time Slice的設(shè)計(jì)方式,就變的需要有所調(diào)整,也因此在CFS中會(huì)透過函式calc_delta_mine (實(shí)作在 kernel/sched.c),根據(jù)目前Task的優(yōu)先級(jí)計(jì)算在排程時(shí)每次一個(gè)Scheduling Tick要增加的Delta值,也就是說如果該Task Nice值越高(優(yōu)先級(jí)越低)該Delta值就越大,對(duì)該執(zhí)行的Task來說就是Virtual RunTime在運(yùn)作時(shí),增加的速度越快(等於縮短實(shí)際執(zhí)行的時(shí)間),反之,如果該Task Nice值越低(優(yōu)先級(jí)越高)則Delta值就越小,在每次Scheduling Tick觸發(fā)時(shí),Virtual RunTime增加的速度越慢,能獲得處理器執(zhí)行的實(shí)際時(shí)間也就越長. 參考kernel/sched_fair.c的實(shí)作,函式calc_delta_mine的呼叫來源有兩處,
以筆者在 64bits處理器下,所使用的Linux Kernel 2.6.38.6來說,函式calc_delta_mine的幾個(gè)關(guān)鍵數(shù)字如下所示 1,NICE_0_LOAD 為1024 (參考kernel/sched.c原始碼 NICE_0_LOAD=SCHED_LOAD_SCALE,並參考include/linux/sched.h中 SCHED_LOAD_SCALE = (1L << SCHED_LOAD_SHIFT), 而SCHED_LOAD_SHIFT = 10) 2,LONG_MAX為9223372036854775807 (ㄟ…我是用64bits處理器驗(yàn)證,所以該值為0x7FFFFFFFFFFFFFFF) (參考原始碼include/linux/kernel.h,其中LONG_MAX = ((long)(~0UL>>1)) ) 3,SRR(x, y) 為 (((x) + (1UL << ((y) – 1))) >> (y)) (參考原始碼kernel/sched.c) 4,BITS_PER_LONG:64 5,WMULT_CONST:4294967296 (=0×100000000) 6,WMULT_SHIFT:32 函式calc_delta_mine宣告原型如下 static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight, struct load_weight *lw) 根據(jù)目前的實(shí)作,Delta的返回值會(huì)透過如下流程來計(jì)算 1,如果lw->inv_weight 為0,就會(huì)執(zhí)行下列的計(jì)算 lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1); 2,Temp-Delta值為delta_exec * weight 2-1,如果Temp-Delta > 0×100000000 2-1-1,Delta = SRR(SRR(Temp-Delta, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2); 2-2,如果Temp-Delta <= 0×100000000 2-2-1,Delta = SRR(Temp-Delta * lw->inv_weight, WMULT_SHIFT); 舉實(shí)際的例子來說,當(dāng)傳入的參數(shù) 1,delta_exec=6000000 2,weight=1024 3,lw->weight=1024 4,lw->inv_weight=0 由於 lw->inv_weight為0,因此會(huì)進(jìn)行如下的計(jì)算 lw->inv_weight=1 + ( 0×100000000 – 1024/2) / (1024+1) = 4190212. 而Temp-Delta 的值 = delta_exec * weight = 6000000 * 1024 = 6144000000=0x16E360000,大於 WMULT_CONST的值 (0×100000000). 因此,最後的Delta執(zhí)會(huì)進(jìn)行如下計(jì)算 Delta = SRR(SRR(Temp-Delta, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2) =SRR(SRR(0x16E360000, 32/2) * 4190212,32/2) =SRR(((0x16E360000 + 1<<15)>>16)* 4190212,16) =SRR( ( 0x16E368000 >>16)* 4190212,16) =SRR( 0x16E36* 4190212,16) =SRR( 392832375000,16) = (392832375000 + 1<15) >> 16 =5994146. 對(duì)應(yīng)到不同函式參數(shù)所換算回來的Delta值,筆者整理如下表所示
透過上述的計(jì)算,我們可以知道影響Virtual RunTime Slice增加的Delta值最大的關(guān)鍵是在下面三個(gè)參數(shù),筆者在此也簡述這三個(gè)參數(shù)的意義. 1,delta_exec: 是目前Virtual RunTime Slice的Delta值,會(huì)用來當(dāng)作calc_delta_mine的第一個(gè)參數(shù),用以計(jì)算出新的Delta值. 根據(jù)目前的實(shí)作,這個(gè)值可以表示在呼叫函式calc_delta_mine前,該Task所執(zhí)行的時(shí)間間隔,也就是說如果該值越大,表示該Task在這次呼叫函式calc_delta_mine前,所得到的執(zhí)行時(shí)間越長,相對(duì)的再透過Weight的計(jì)算後,下一次得到的Delta值就越大,對(duì)應(yīng)到真實(shí)執(zhí)行時(shí)間就會(huì)越少 (因?yàn)镈elta值變大,執(zhí)行時(shí)Virtual RunTime增加的速度就越快.). 2,weight:為目前Task的Load Weight,若Task的Nice值為 0,則此值為1024. 這個(gè)值越大,透過calc_delta_mine所計(jì)算的inv_weight 值越小,對(duì)應(yīng)該 Task所計(jì)算出來的Delta值也越小,也就表示該Task的Virtual RunTime增加的越慢,因此實(shí)際得到處理器執(zhí)行的真實(shí)時(shí)間就越長. 3,lw->weight:為目前排程單位sched_entity的Load Weight . 如果se->load.weight等於Nice 0的 Load Weight (1024),函式calc_delta_fair就會(huì)直接返回所傳入的Delta值,反之才會(huì)進(jìn)入函式calc_delta_mine,重新計(jì)算新的Delta值. RunQueue的參數(shù)load->weight,會(huì)等於該RunQueue中所有Schedule Entity的load->weight總合,分別表示整個(gè)RunQueue執(zhí)行單元的負(fù)荷與個(gè)別執(zhí)行單元的負(fù)荷. 參考函式set_load_weight的實(shí)作(in kernel/sched.c),我們可以把不同的Task Priority ,Nice值與所對(duì)應(yīng)的Scheduling Entity Load Weight值對(duì)應(yīng)如下表所示
一般來說,如果Nice值加一 (也就是優(yōu)先級(jí)降低一),大約會(huì)減少10%處理器的執(zhí)行時(shí)間,而如果是Nice值減一(也就是優(yōu)先級(jí)調(diào)升),大約就會(huì)增加10%處理器的執(zhí)行時(shí)間.而參考上表整理的結(jié)果,每個(gè)Nice值的區(qū)間所對(duì)應(yīng)的Weight大約會(huì)相差1.25倍. 例如15*1.25=18.75,18*1.25=22.5… 介紹到此,我們可以發(fā)現(xiàn)像是O(N),O(1)或是CFS (O(Log2(N))),都沒有把處理器不等速的問題考慮進(jìn)來.也因此,在支援像是aSMP架構(gòu)時(shí),這部份的排程機(jī)制改善,就是攸關(guān)能否發(fā)揮aSMP架構(gòu)優(yōu)勢(shì)的關(guān)鍵. 結(jié)語 多核心架構(gòu)肯定會(huì)是未來智慧型手機(jī)晶片的主流,要能在智慧型手機(jī)方案中發(fā)揮架構(gòu)的優(yōu)勢(shì),了解Linux Kernel的排程機(jī)制,會(huì)是一個(gè)必要的基礎(chǔ)功課. 本文主要著重在Linux Kernel排程的介紹,從前一代的Linux核心排程機(jī)制談起,到目前基於CFS的核心排程與相關(guān)資料結(jié)構(gòu)的說明. 但要發(fā)揮多核心的優(yōu)勢(shì),除了Linux Kernel的層次外,在Android Framework上也需有所因應(yīng),後續(xù)筆者會(huì)再進(jìn)一步的加以介紹.希望能讓閱讀本文的開發(fā)者有所助益.
People who looked at this item also looked at…
Related items |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
