【文章內(nèi)容簡介】 60。}4)獲取當(dāng)前CPU邏輯號，如果當(dāng)前運(yùn)行隊(duì)列為空，則調(diào)用idle_balance(cpu, rq)從其他CPU運(yùn)行隊(duì)列上拉進(jìn)程到本地CPU的運(yùn)行隊(duì)列上。如果調(diào)整后，當(dāng)前運(yùn)行隊(duì)列仍為空則next賦為idle進(jìn)程，跳轉(zhuǎn)到任務(wù)切換代碼行去。if (unlikely(!rqnr_running)) {idle_balance(cpu, rq)。if (!rqnr_running) {next = rqidle。rqexpired_timestamp = 0。goto switch_tasks。}}5)如果runqueue中有進(jìn)程，并且當(dāng)前活得進(jìn)程數(shù)為0，則交換active和expired隊(duì)列指針。array = rqactive。if (unlikely(!arraynr_active)) {schedstat_inc(rq, sched_switch)。rqactive = rqexpired。rqexpired = array。array = rqactive。rqexpired_timestamp = 0。rqbest_expired_prio = MAX_PRIO。}6)從運(yùn)行隊(duì)列的活動prio_array數(shù)據(jù)的位圖中查找第一個(gè)位設(shè)置為1的索引，根據(jù)索引找到該優(yōu)先級隊(duì)列的第一個(gè)task。idx = sched_find_first_bit(arraybitmap)。queue = arrayqueue + idx。next = list_entry(queuenext, struct task_struct, run_list)。7)如果next是普通進(jìn)程，并且nextsleep_type是SLEEP_INTERACTIVE或SLEEP_INTERRUPTED，則重新計(jì)算進(jìn)程睡眠時(shí)間和進(jìn)程優(yōu)先級。進(jìn)程切換工作：8)更新sched_goidle，預(yù)期next結(jié)構(gòu)數(shù)據(jù)，清除TIF_NEED_RESCHED標(biāo)志，設(shè)置quiescent狀態(tài)計(jì)數(shù)為1：rcu_datapassed_quiesc = 1。switch_tasks:if (next == rqidle)schedstat_inc(rq, sched_goidle)。prefetch(next)。prefetch_stack(next)。clear_tsk_need_resched(prev)。rcu_qsctr_inc(task_cpu(prev))。9)更新prev進(jìn)程運(yùn)行時(shí)間戳prevsleep_avg，prevtimestamp。10)調(diào)度信息切換到next，更新next。時(shí)間戳和運(yùn)行隊(duì)列信息：sched_info_switch(prev, next)。if (likely(prev != next)) {nexttimestamp = nextlast_ran = now。rqnr_switches++。rqcurr = next。++*switch_count?！瓆11)進(jìn)行進(jìn)程切換，context_switch參見前面的分析，它進(jìn)行進(jìn)程空間和內(nèi)核堆棧切換。prepare_lock_switch功能是在定義了__ARCH_WANT_INTERRUPTS_ON_CTXSW情況下，在切換前開中斷spin_unlock_irq(amp。rqlock)。barrier()是保證代碼執(zhí)行順序不變。prepare_task_switch(rq, next)。prev = context_switch(rq, prev, next)。barrier()。finish_task_switch(this_rq(), prev)。進(jìn)程切換后的工作：進(jìn)程切換context_switch語句之后的代碼并不是由next進(jìn)程立即執(zhí)行的，而是由調(diào)度器選擇prev進(jìn)程繼續(xù)執(zhí)行的。次時(shí)prev變量指向的已經(jīng)是被prev進(jìn)程替換的其他進(jìn)程的指針。12)finish_task_switch()必須與prepare_task_switch配對使用，并主要鎖的順序。它所做的工作，finish_lock_switch調(diào)用local_irq_enable(),獲取prev的狀態(tài)和rqprev_mm，如果mm非空，則調(diào)用mmdrop(mm)減少mm的引用計(jì)數(shù)，如果為0則釋放進(jìn)程頁表和虛擬空間。如果prev_state為TASK_DEAD則釋放進(jìn)程的task結(jié)構(gòu)。struct mm_struct *mm = rqprev_mm。long prev_state。rqprev_mm = NULL。prev_state = prevstate。finish_arch_switch(prev)。finish_lock_switch(rq, prev)。if (mm)mmdrop(mm)。if (unlikely(prev_state == TASK_DEAD)) {kprobe_flush_task(prev)。put_task_struct(prev)。}13)最后，if (unlikely(tasklock_depth = 0))則重新獲取大內(nèi)核鎖__reacquire_kernel_lock，否則goto need_resched_nonpreemptible。允許搶占，如果TIF_NEED_RESCHED被設(shè)置，則跳轉(zhuǎn)到need_resched重新進(jìn)行調(diào)度。prev = current。if (unlikely(reacquire_kernel_lock(prev) 0))goto need_resched_nonpreemptible。preempt_enable_no_resched()。if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))goto need_resched。三、Linux缺頁中斷處理1．請求調(diào)頁中斷：進(jìn)程線性地址空間里的頁面不必常駐內(nèi)存，例如進(jìn)程的分配請求被理解滿足，空間僅僅保留vm_area_struct的空間，頁面可能被交換到后援存儲器，或者寫一個(gè)只讀頁面(COW)。Linux采用請求調(diào)頁技術(shù)來解決硬件的缺頁中斷異常，并且通過預(yù)約式換頁策略。主缺頁中斷和次缺頁中斷，費(fèi)時(shí)的需要從磁盤讀取數(shù)據(jù)時(shí)就會產(chǎn)生主缺頁中斷。每種CPU結(jié)構(gòu)提供一個(gè)do_page_fault(struct pt_regs *regs, error_code)處理缺頁中斷，該函數(shù)提供了大量信息，如發(fā)生異常地址，是頁面沒找到還是頁面保護(hù)錯(cuò)誤，是讀異常還是寫異常，來自用戶空間還是內(nèi)核空間。它負(fù)責(zé)確定異常類型及異常如何被體系結(jié)構(gòu)無關(guān)的代碼處理。下圖是Linux缺頁中斷處理流程：圖Linux缺頁中斷處理一旦異常處理程序確定異常是有效內(nèi)存區(qū)域中的有效缺頁中斷，將調(diào)用體系結(jié)構(gòu)無關(guān)的函數(shù)handle_mm_fault()。如果請求頁表項(xiàng)不存在，就分配請求的頁表項(xiàng)，并調(diào)用handle_pte_fault()。第一步調(diào)用pte_present檢查PTE標(biāo)志位，確定其是否在內(nèi)存中，然后調(diào)用pte_none()檢查PTE是否分配。如果PTE還沒有分配的話，將調(diào)用do_no_page()處理請求頁面的分配，否則說明該頁已經(jīng)交換到磁盤，也是調(diào)用do_swap_page()處理請求換頁。如果換出的頁面屬于虛擬文件則由do_no_page()處理。第二步確定是否寫頁面。如果PTE寫保護(hù)，就調(diào)用do_swap_page()，因?yàn)檫@個(gè)頁面是寫時(shí)復(fù)制頁面。COW頁面識別方法：頁面所在VMA標(biāo)志位可寫，但相應(yīng)的PTE確不是可寫的。如果不是COW頁面，通常將之標(biāo)志為臟，因?yàn)樗呀?jīng)被寫過了。第三步確定頁面是否已經(jīng)讀取及是否在內(nèi)存中，但還會發(fā)生異常。這是因?yàn)樵谀承w系結(jié)構(gòu)中沒有3級頁表，在這種情況下建立PTE并標(biāo)志為新即可。2．請求頁面分配：第一次訪問頁面，首先分配頁面，一般由do_no_page()填充數(shù)據(jù)。如果父VMA的vm_area_struct－vm_ops提供了nopage()函數(shù)，則用它填充數(shù)據(jù)；否則調(diào)用do_anonymous_page()匿名函數(shù)來填充數(shù)據(jù)。如果被文件或設(shè)備映射，如果時(shí)文件映射，filemap_nopage()將替代nopage()函數(shù)，如果由虛擬文件映射而來，則shmem_nopage()。每種設(shè)備驅(qū)動將提供不同的nopage()函數(shù)，該函數(shù)返回struct page結(jié)構(gòu)。3．請求換頁：將頁面交換至后援存儲器后，函數(shù)do_swap_page()負(fù)責(zé)將頁面讀入內(nèi)存，將在后面講述。通過PTE的信息就足夠查找到交換的頁面。頁面交換出去時(shí)，一般先放到交換高速緩存中。缺頁中斷時(shí)如果頁面在高速緩存中，則只要簡單增加頁面計(jì)數(shù)，然后把它放到進(jìn)程頁表中并計(jì)數(shù)次缺頁中斷發(fā)生的次數(shù)。如果頁面僅存在磁盤中，Linux將調(diào)用swapin_readahead()讀取它及后續(xù)的若干頁面。4．頁面幀回收除了slab分配器，系統(tǒng)中所有正在使用的頁面都存放在頁面高速緩存中，并由pagelru鏈接在一起。Slab頁面不存放到高速緩存中因?yàn)榛诒籹lab使用的對象對頁面計(jì)數(shù)很困難。除了查找每個(gè)進(jìn)程頁表外沒有其他方法能把struct page映射為PTE，查找頁表代價(jià)很大。如果頁面高速緩存中存在大量的進(jìn)程映射頁面，系統(tǒng)將會遍歷進(jìn)程頁表，通過swap_out()函數(shù)交換出頁面直到有足夠的頁面空閑，而共享頁會給swap_out()帶來問題。如果一個(gè)頁面是共享的，同時(shí)一個(gè)交換項(xiàng)已經(jīng)被分配，PTE就會填寫所需信息以便在交換分區(qū)里重新找到該頁并將引用計(jì)數(shù)減1。只有引用計(jì)數(shù)為0時(shí)該頁才能被替換出去。內(nèi)存和磁盤緩存申請?jiān)絹碓蕉嗟捻撁娴_無法判斷如何釋放進(jìn)程頁面，請求分頁機(jī)制在進(jìn)程頁面缺失時(shí)申請新頁面，但它卻不能強(qiáng)制釋放進(jìn)程不再使用的頁面。The Page Frame Reclaiming Algorithm(PFRA)頁面回收算法用于從用戶進(jìn)程和內(nèi)核cache中回收頁面放到伙伴系統(tǒng)的空閑塊列表中。PFRA必須在系統(tǒng)空閑內(nèi)存達(dá)到某個(gè)最低限度時(shí)進(jìn)行頁面回收，回收的對象必須是非空閑頁面?？蓪⑾到y(tǒng)頁面劃分為四種：1)Unreclaimable不可回收的，包括空閑頁面、保留頁面設(shè)置了PG_reserved標(biāo)志、內(nèi)核動態(tài)分配的頁面、進(jìn)程內(nèi)核棧的頁面、設(shè)置了PG_locked標(biāo)志的臨時(shí)鎖住的頁面、設(shè)置了VM_LOCKED標(biāo)志的內(nèi)存頁面。2)Swappable可交換的頁面，用戶進(jìn)程空間的匿名頁面(用戶堆棧)、tmpfs文件系統(tǒng)的映射頁面（入IPC共享內(nèi)存頁面），頁面存放到交換空間。3)Syncable可同步的頁面，入用戶態(tài)地址空間的映射頁面、保護(hù)磁盤數(shù)據(jù)的頁面緩存的頁面、塊設(shè)備緩沖頁、磁盤緩存的頁面（入inode cache），如果有必要的話，需同步磁盤映像上的數(shù)據(jù)。4)Discardable可丟棄的頁面，入內(nèi)存緩存中的無用頁面（slab分配器中的頁面）、dentry cache的頁面。PFRA算法是基于經(jīng)驗(yàn)而非理論的算法，它的設(shè)計(jì)原則如下：1)首先釋放無損壞的頁面。進(jìn)程不再引用的磁盤和內(nèi)存緩存應(yīng)該先于用戶態(tài)地址空間的頁面釋放。2)標(biāo)志所有進(jìn)程態(tài)進(jìn)程的頁面為可回收的。3)多進(jìn)程共享頁面的回收，要先清除引用該頁面的進(jìn)程頁表項(xiàng)，然后再回收。4)回收“不在使用的”頁面。PFRA用LRU鏈表把進(jìn)程劃分為inuse和unused兩種，PFRA僅回收unused狀態(tài)的頁面。Linux使用PTE中的Accessed比特位實(shí)現(xiàn)非嚴(yán)格的LRU算法。頁面回收通常在三種情況下執(zhí)行：1)系統(tǒng)可用內(nèi)存比較低時(shí)進(jìn)行回收(通常發(fā)生在申請內(nèi)存失敗)。2)內(nèi)核進(jìn)入suspendtodisk狀態(tài)時(shí)進(jìn)行回收。3)周期性回收，內(nèi)核線程周期性激活并在必要時(shí)進(jìn)行頁面回收。Low on memory回收有以下幾種情形：1)_ _getblk( )調(diào)用的grow_buffers( )函數(shù)分配新緩存頁失敗；2)create_empty_buffers( )調(diào)用的alloc_page_buffers( )函數(shù)為頁面分配臨時(shí)的buffer head失敗；3)_ _alloc_pages( )函數(shù)在給定內(nèi)存區(qū)里分配一組連續(xù)的頁面幀失敗。周期性回收涉及的兩種內(nèi)核線程：1)Kswapd內(nèi)核線程在內(nèi)存區(qū)中檢測空閑頁面是否低于pages_high的門檻值；2)預(yù)定義工作隊(duì)列中的事件內(nèi)核線程，PFRA周期性調(diào)度該工作隊(duì)列中的task回收slab分配器中所有空閑的slab；所有用戶空間進(jìn)程和頁面緩存的頁面被分為活動鏈表和非活動鏈表，統(tǒng)稱LRU鏈表。每個(gè)區(qū)描述符中包括active_list和inactive_list兩個(gè)鏈表分別將這些頁面鏈接起來。nr_active和nr_inactive分別表示這兩種頁面數(shù)量，lru_lock用于同步。頁描述符中的PG_lru用于標(biāo)志一個(gè)頁面是否屬于LRU鏈表，PG_active用于標(biāo)志頁面是否屬于活動鏈表，lru字段用于把LRU中的鏈表串起來。活動鏈表和非活動鏈表的頁面根據(jù)最近的訪問情況進(jìn)行動態(tài)調(diào)整。PG_referenced標(biāo)志就是此用途。處理LRU鏈表的函數(shù)有：add_page_to_active_list()、add_page_to_inactive_list()、activate_page()、lru_cache_add()、lru_cache_add_active()等，這些函數(shù)比較簡單。shrink_active_list ( )用于將頁表從活動鏈表移到非活動鏈表。該函數(shù)在shrink_zone()函數(shù)執(zhí)行用戶地址空間的頁面回收時(shí)執(zhí)行。5．交換分區(qū)：系統(tǒng)可以有MAX_SWAPFILES的交換分區(qū)，每個(gè)分區(qū)可放在磁盤分區(qū)上或者普通文件里。每個(gè)交換區(qū)由一系列頁槽組成。每個(gè)交換區(qū)有個(gè)swap_header結(jié)構(gòu)描述交換區(qū)版本等信息。每個(gè)交換區(qū)有若干個(gè)swap_extent組成，每個(gè)swap_extent是連續(xù)的物理區(qū)域。對于磁盤交換區(qū)只有一個(gè)swap_extent，對于文件交換區(qū)則由多個(gè)swap_extent組成，因?yàn)槲募⒉皇欠旁谶B續(xù)的磁盤塊上的。mkswap命令可以創(chuàng)建交換分區(qū)。圖 交換分區(qū)結(jié)構(gòu)圖 交換頁結(jié)構(gòu)swp_type()和swp_offset()函數(shù)根據(jù)頁槽索引和交換區(qū)號得到type和offset值，函數(shù)swp_entry(type,offset)得到交換槽。最后一位總是清0表示頁不在RAM上。槽最大224(64G)。第一個(gè)可用槽索引為1。槽索引不能全為0。一個(gè)頁面可能被多個(gè)