Linux進(jìn)程調(diào)度切換和虛擬空間管理深入分析

1、.：.；一、Linux進(jìn)程切換深化分析#define CLONE_KERNEL(CLONE_FS | CLONE_FILES | CLONE_SIGHAND)創(chuàng)建內(nèi)核線程時(shí)運(yùn)用的CLONE標(biāo)志。1#define unlikely(x)_builtin_expect(!(x), 0)編譯器優(yōu)化，實(shí)踐前往值x是整型表達(dá)式，0表示并不預(yù)期該事件發(fā)生，也就是說x為0的能夠性很小，這是為了讓編譯器對下面得語句進(jìn)展優(yōu)化。2進(jìn)程內(nèi)核態(tài)堆棧構(gòu)造：進(jìn)程是動(dòng)態(tài)實(shí)體，進(jìn)程描畫符是存放在動(dòng)態(tài)內(nèi)存中的。在一塊進(jìn)程內(nèi)存區(qū)上，Linux存放了兩個(gè)數(shù)據(jù)構(gòu)造：指向task_struct得thread_info和內(nèi)核態(tài)的進(jìn)程棧。

2、大小普通2頁8K，這要求頁面幀對齊2的13次冪，在X86上編譯時(shí)可以配置大小為4K。thread_info在內(nèi)存區(qū)開場處，內(nèi)核棧從內(nèi)存尾向下增長。在C言語中可以用union構(gòu)造表示：圖1. 8K內(nèi)核棧和進(jìn)程描畫符task_struct及thread_info的相互關(guān)系union thread_union struct thread_info thread_info;unsigned long stack2048; /* 1024 for 4KB stacks */;CPU的esp存放器用于執(zhí)行堆棧的頂部指針，當(dāng)從用戶態(tài)轉(zhuǎn)向內(nèi)核態(tài)時(shí)，進(jìn)程內(nèi)核?？偸强盏模詄sp就會執(zhí)行堆棧底部。運(yùn)用alloc

3、_thread_info和free_thread_info用于分配和釋放一個(gè)存放thread_info構(gòu)造和內(nèi)核堆棧的內(nèi)存區(qū)。內(nèi)核經(jīng)過當(dāng)前esp指針可以很方便的得到thread_info構(gòu)造的地址。current_thread_info(void)的原理即如下：movl $0 xffff2000,%ecx /* or 0 xfffff000 for 4KB stacks */andl %esp,%ecxmovl %ecx,pthread_info中task指針是第一個(gè)，所以current宏相當(dāng)于current_thread_info( )-task，從而也就得到task指針。每個(gè)進(jìn)程有本人獨(dú)立

4、得進(jìn)程空間，一切進(jìn)程共享CPU存放器。進(jìn)程繼續(xù)執(zhí)行時(shí)必需裝入存放器恢復(fù)得數(shù)據(jù)集稱為硬件上下文環(huán)境。在Linux中部分硬件上下文存放在進(jìn)程描畫符中，部分存放到內(nèi)核態(tài)堆棧里。3.進(jìn)程切換堆棧原理：每個(gè)進(jìn)程有本人獨(dú)立得進(jìn)程空間，一切進(jìn)程共享CPU存放器。進(jìn)程繼續(xù)執(zhí)行時(shí)必需裝入存放器恢復(fù)得數(shù)據(jù)集稱為硬件上下文環(huán)境。在Linux中部分硬件上下文存放在進(jìn)程描畫符中，部分存放到內(nèi)核態(tài)堆棧里。80 x86體系支持在進(jìn)程TSS段跳轉(zhuǎn)時(shí)自動(dòng)執(zhí)行進(jìn)程硬件上下文切換。Linux運(yùn)用軟件方法實(shí)現(xiàn)。軟件方式效率差不多，當(dāng)更靈敏，可以控制流程，留下優(yōu)化空間。80 x86用TSS段保管硬件上下文內(nèi)容，每個(gè)CPU有一個(gè)TSS段

5、。從用戶態(tài)到內(nèi)核態(tài)切換時(shí)，從TSS中取出內(nèi)核棧地址。用戶態(tài)進(jìn)程訪問I/O端口時(shí)，TSS中的I/O訪問位圖可以驗(yàn)證權(quán)限。tss_struct描畫了TSS格式，init_tss存放初始TSS內(nèi)容，每次進(jìn)程切換，內(nèi)核更新TSS中的某些字段，以反映當(dāng)前運(yùn)轉(zhuǎn)進(jìn)程的權(quán)限等級。每個(gè)進(jìn)程有個(gè)反映義務(wù)CPU形狀的thread_struct構(gòu)造變量thread，除eax、ecx等通用存放器內(nèi)容保管在內(nèi)核態(tài)堆棧中，其他大部分存放器都保管在次構(gòu)造中。該構(gòu)造一部分對應(yīng)于tss_struct中的內(nèi)容，進(jìn)程切換時(shí)把thread中某些內(nèi)容更新到tss_struct中就可以反映當(dāng)前義務(wù)的運(yùn)轉(zhuǎn)CPU環(huán)境。struct tss_s

6、tructunsigned shortback_link,_blh;unsigned longesp0;unsigned shortss0,_ss0h;unsigned longesp1;unsigned shortss1,_ss1h;/* ss1 is used to cache MSR_IA32_SYSENTER_CS */unsigned longesp2;unsigned shortss2,_ss2h;unsigned long_cr3;unsigned longeip;unsigned longeflags;unsigned longeax,ecx,edx,ebx;unsigned

7、longesp;unsigned longebp;unsigned longesi;unsigned longedi;unsigned shortes, _esh;unsigned shortcs, _csh;unsigned shortss, _ssh;unsigned shortds, _dsh;unsigned shortfs, _fsh;unsigned shortgs, _gsh;unsigned shortldt, _ldth;unsigned shorttrace, io_bitmap_base;/* The extra 1 is there because the CPU wi

8、ll access an* additional byte beyond the end of the IO permission* bitmap. The extra byte must be all 1 bits, and must* be within the limit.*/unsigned longio_bitmapIO_BITMAP_LONGS + 1;/* Cache the current maximum and the last task that used the bitmap:*/unsigned long io_bitmap_max;struct thread_stru

9、ct *io_bitmap_owner;/* pads the TSS to be cacheline-aligned (size is 0 x100)*/unsigned long _cacheline_filler35;/* . and then another 0 x100 bytes for emergency kernel stack*/unsigned long stack64; _attribute_(packed);struct thread_struct/* cached TLS descriptors. */struct desc_struct tls_arrayGDT_E

10、NTRY_TLS_ENTRIES;unsigned longesp0;unsigned longsysenter_cs;unsigned longeip;unsigned longesp;unsigned longfs;unsigned longgs;/* Hardware debugging registers */unsigned longdebugreg8;/* %db0-7 debug registers */* fault info */unsigned longcr2, trap_no, error_code;/* floating point info */union i387_

11、unioni387;/* virtual 86 mode info */struct vm86_struct _user * vm86_info;unsigned longscreen_bitmap;unsigned longv86flags, v86mask, saved_esp0;unsigned intsaved_fs, saved_gs;/* IO permissions */unsigned long*io_bitmap_ptr;unsigned longiopl;/* max allowed port in the bitmap, in bytes: */unsigned long

12、io_bitmap_max;4進(jìn)程切換流程解析switch_to進(jìn)程切換本質(zhì)上兩步：1)進(jìn)程頁表PGD切換；2)內(nèi)核態(tài)堆棧和硬件上下文切換包括CPU存放器；上面兩步經(jīng)過context_switch()實(shí)現(xiàn)，它經(jīng)過調(diào)用switch_mm()切換進(jìn)程空間，switch_to切換內(nèi)核上下文環(huán)境。首先看看context_switch()做了些什么：1)進(jìn)程描畫符中active_mm執(zhí)行進(jìn)程運(yùn)用的地址空間，mm執(zhí)行進(jìn)程擁有的地址空間，對于普通進(jìn)程它們一樣。對于內(nèi)核線程，它的mm總為NULL。所以context_switch()首先判別if (!next-mm)即next為內(nèi)核線程，那么運(yùn)用prev的進(jìn)程

13、地址空間：if (!next-mm) next-active_mm = prev-active_mm; atomic_inc(&prev-active_mm-mm_count); enter_lazy_tlb(prev-active_mm, next);2)否那么，假設(shè)next是普通進(jìn)程，那么用next進(jìn)程空間交換prev的地址空間：switch_mm(oldmm, mm, next);3)假設(shè)prev是內(nèi)核線程或者正在退出，那么設(shè)置prev-active_mm和runqueue的prev_mm為NULL：if (!prev-mm) prev-active_mm = NULL;WARN_ON(

14、rq-prev_mm);rq-prev_mm = oldmm;下面看看switch_mm()如何切換進(jìn)程空間：1)獲取cpu邏輯號。2)cpu_clear(cpu, prev-cpu_vm_mask)去除cpu_vm_mask位標(biāo)志。3)per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK設(shè)置cpu_tlbstate形狀。4)per_cpu(cpu_tlbstate, cpu).active_mm = next設(shè)置cpu_tlbstate的active_mm為next。5)cpu_set(cpu, next-cpu_vm_mask)設(shè)置next的cpu_

15、vm_mask標(biāo)志。6)load_cr3(next-pgd)裝載next的pgd頁表到cr3存放器。7)假設(shè)next的LDT描畫符改動(dòng)，那么加載next的LDT描畫符。if (unlikely(prev-context.ldt != next-context.ldt)load_LDT_nolock(&next-context);最后，switch_to進(jìn)展內(nèi)核堆棧和CPU環(huán)境切換操作：#define switch_to(prev,next,last) do unsigned long esi,edi;asm volatile(pushflnt/* Save flags */pushl %ebp

16、ntmovl %esp,%0nt/* save ESP */movl %5,%espnt/* restore ESP */movl $1f,%1nt/* save EIP */pushl %6nt/* restore EIP */jmp _switch_ton1:tpopl %ebpntpopfl:=m (prev-thread.esp),=m (prev-thread.eip),=a (last),=S (esi),=D (edi):m (next-thread.esp),m (next-thread.eip),2 (prev), d (next); while (0)流程描畫，prev是進(jìn)

17、程A的task構(gòu)造，next是進(jìn)程B的task構(gòu)造，last是進(jìn)程C的構(gòu)造：1)保管prev和next指針的值到eax和edx：movl prev, %eaxmovl next, %edx2)保管eflags和ebp存放器內(nèi)容到prev內(nèi)核態(tài)堆棧中：pushflpushl %ebp3)將esp內(nèi)容保管到prev-thread.esp中，該字段執(zhí)行prev內(nèi)核堆棧的top地址。movl %esp,484(%eax)4)將next-thread.esp加載到esp中，如今開場，esp執(zhí)行next的內(nèi)核堆棧，進(jìn)程切換完成。movl 484(%edx), %esp5)保管下面Label 1到prev-

18、thread.eip指針中，當(dāng)prev進(jìn)程恢復(fù)運(yùn)轉(zhuǎn)時(shí)，從該位置開場運(yùn)轉(zhuǎn)。movl $1f, 480(%eax)6)將next-thread.eip的指針內(nèi)容壓到next的內(nèi)核態(tài)堆棧中，通常它的內(nèi)容也是Label 1。pushl 480(%edx)7)跳轉(zhuǎn)到_switch_toC函數(shù)執(zhí)行。jmp _switch_to8)被交換的進(jìn)程A繼續(xù)執(zhí)行，它在Label 1處，首先是恢復(fù)eflags和ebp存放器內(nèi)容。留意這里是發(fā)生在調(diào)度器選擇prev在CPU上運(yùn)轉(zhuǎn)后，次數(shù)esp曾經(jīng)執(zhí)行了prev的內(nèi)核堆棧。1:popl %ebppopfl9)將eax內(nèi)容保管到last義務(wù)構(gòu)造中。這里eax是被進(jìn)程A切換下

19、來的進(jìn)程C的task構(gòu)造指針。movl %eax, last5_switch_to深化分析_switch_to參數(shù)是存放在eax和edx中的內(nèi)容，這經(jīng)過#define fastcall_attribute_(regparm(3)通知gcc編譯器。1)獲取tss_struct tss、prev_p和next_p的thread_struct構(gòu)造prev和next、當(dāng)前CPU邏輯ID。2)調(diào)用_unlazy_fpu(prev_p)根據(jù)條件標(biāo)志選擇能否保管prev_p的FPU, MMX,和XMM存放器內(nèi)容。3)load_esp0(tss, next)將next的堆棧地址存放到tss中：tss-esp0

20、 = thread-esp0。4)savesegment(gs, prev-gs)保管gs存放器到prev-gs，fs曾經(jīng)在棧入口保管，es和ds在內(nèi)核態(tài)下不需求保管。5)load_TLS(next, cpu)從next的tls_array緩存中加載線程的Thread-Local Storage描畫符。TLS在GDT表中位置6、7、8。cpu_gdt_tablecpu6 = next_p-thread.tls_array0;cpu_gdt_tablecpu7 = next_p-thread.tls_array1;cpu_gdt_tablecpu8 = next_p-thread.tls_arr

21、ay2;6)假設(shè)當(dāng)前特權(quán)級別是0并且prev-iopl != next-iopl那么恢復(fù)IOPL設(shè)置set_iopl_mask(next-iopl)。7)根據(jù)thread_info的TIF標(biāo)志_TIF_WORK_CTXSW和TIF_IO_BITMAP判別能否需求處置debug存放器和IO位圖：_switch_to_xtra(next_p, tss);l只需當(dāng)next_p掛起時(shí)即if (test_tsk_thread_flag(next_p, TIF_DEBUG)運(yùn)用了debug存放器才需求恢復(fù)set_debugreg(next-debugregi, i)。只需調(diào)試器需求監(jiān)控prev的形狀時(shí)，p

22、rev_p-thread.debugreg數(shù)組的內(nèi)容才會被修正。Debug存放器dr0dr7，dr4和dr5不用。l當(dāng)prev_p或者next_p定義了本人的I/O訪問位圖時(shí)，必需更新TSS的I/O bitmap。if (prev_p-thread.io_bitmap_ptr | next_p-thread.io_bitmap_ptr)handle_io_bitmap(&next_p-thread, &init_tsscpu);進(jìn)程的I/O訪問位圖存放在io_bitmap_ptr指針里，通常進(jìn)程很少修正IO位圖，只需當(dāng)前時(shí)間片中訪問IO端口才會把實(shí)踐的IO位圖加載到TSS中。當(dāng)next_p沒有

23、自定義位圖時(shí)：tss-io_bitmap_base = INVALID_IO_BITMAP_OFFSET;前往假設(shè)next = tss-io_bitmap_owner那么設(shè)置有效的偏移量：tss-io_bitmap_base = IO_BITMAP_OFFSET;前往否那么tss-io_bitmap_base = INVALID_IO_BITMAP_OFFSET_LAZY;只需第二種情況tss-io_bitmap_base設(shè)置的是有效的io_bitmap偏移量，對于其他兩種情況，當(dāng)用戶進(jìn)程訪問I/O端口時(shí)將會觸發(fā)General protection的異常，do_general_protecti

24、on( )異常處置函數(shù)根據(jù)io_bitmap的值處置異常：假設(shè)是0 x8000(INVALID_IO_BITMAP_OFFSET)那么發(fā)送SIGSEGV信號給用戶進(jìn)程；假設(shè)是0 x9000(INVALID_IO_BITMAP_OFFSET_LAZY)那么拷貝進(jìn)程的thread中的io_bitmap_ptr內(nèi)容到io_bitmap中，并設(shè)置io_bitmap_base為正確的偏移量(104)。8)disable_tsc(prev_p, next_p)設(shè)置cr4中的TSC Disable位。9)arch_leave_lazy_cpu_mode()設(shè)置CPU的lazy方式。10)假設(shè)next_p-f

25、pu_counter 5那么恢復(fù)next_p的FPU存放器內(nèi)容：math_state_restore()。FPU存放器存放在next_p-thread-i387中，i387是i387_union的union構(gòu)造：union i387_union struct i387_fsave_structfsave;struct i387_fxsave_structfxsave;struct i387_soft_struct soft;struct i387_fxsave_struct unsigned shortcwd;unsigned shortswd;unsigned shorttwd;unsign

26、ed shortfop;longfip;longfcs;longfoo;longfos;longmxcsr;longmxcsr_mask;longst_space32;/* 8*16 bytes for each FP-reg = 128 bytes */longxmm_space32;/* 8*16 bytes for each XMM-reg = 128 bytes */longpadding56; _attribute_ (aligned (16);11)假設(shè)需求，那么從next-gs中恢復(fù)gs存放器內(nèi)容。if (prev-gs | next-gs)loadsegment(gs, nex

27、t-gs);二、Linux實(shí)時(shí)調(diào)度schedule1概述三種調(diào)度戰(zhàn)略：SCHED_FIFO，SCHED_RR和SCHED_NORMAL。FIFO實(shí)時(shí)調(diào)度算法當(dāng)調(diào)度器將CPU指定給某個(gè)進(jìn)程時(shí)，它把該進(jìn)程放到運(yùn)轉(zhuǎn)隊(duì)列首；除非有更高優(yōu)先級的進(jìn)程，否那么該進(jìn)程將不斷占用CPU。Round Robin實(shí)時(shí)進(jìn)程調(diào)度把CPU指定給某進(jìn)程，把它放到運(yùn)轉(zhuǎn)隊(duì)列尾。時(shí)間片運(yùn)轉(zhuǎn)完再選擇其他進(jìn)程調(diào)度。這樣保證了同優(yōu)先級的公平競爭CPU。SCHED_NORMAL是普通的基于運(yùn)轉(zhuǎn)時(shí)間和等待時(shí)間等，動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級的一種調(diào)度戰(zhàn)略。實(shí)時(shí)進(jìn)程優(yōu)先級1100，普通101。2實(shí)時(shí)進(jìn)程調(diào)度的時(shí)機(jī)1)該進(jìn)程被更高優(yōu)先級的進(jìn)程搶占；2)

28、進(jìn)程執(zhí)行一個(gè)阻塞操作，被放到睡眠隊(duì)列，形狀為TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE；3)進(jìn)程被終止(形狀為TASK_STOPPED或TASK_TRACED)，或者進(jìn)程被殺死(形狀為EXIT_ZOMBIE或EXIT_DEAD)4)進(jìn)程調(diào)用sched_yield()自動(dòng)放棄CPU；5)RR實(shí)時(shí)進(jìn)程用完了CPU分配的時(shí)間片；3調(diào)度器相關(guān)函數(shù)1)scheduler_tick( )更新當(dāng)前進(jìn)程的運(yùn)轉(zhuǎn)時(shí)間片tick值，在update_process_times( )中調(diào)用，判別進(jìn)程的時(shí)間片能否用完。2)try_to_wake_up( )喚醒一個(gè)睡眠的進(jìn)程并把它的形狀

29、設(shè)為TASK_RUNNING，插入到運(yùn)轉(zhuǎn)隊(duì)列中。3)recalc_task_prio( )更新進(jìn)程的睡眠時(shí)間和動(dòng)態(tài)優(yōu)先級，SCHED_NORMAL調(diào)度。4)schedule( )進(jìn)程調(diào)度5)load_balance()SMP系統(tǒng)的負(fù)載平衡。4schedule( )函數(shù)進(jìn)程調(diào)度有兩種方式：直接調(diào)用和延遲調(diào)用。直接調(diào)用schedule，當(dāng)前進(jìn)程資源不可用時(shí)會直接調(diào)用調(diào)度器，這種情況下，內(nèi)核線程進(jìn)展如下處置：1)將current插入到適宜的等待隊(duì)列中；2)將current形狀變?yōu)門ASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE3)調(diào)用schedule();4)檢查資源能

30、否可用，假設(shè)不可用，轉(zhuǎn)到第2步；5)一旦資源可用，從等待隊(duì)列中移除current進(jìn)程；在設(shè)備驅(qū)動(dòng)程序中也經(jīng)常會檢查TIF_NEED_RESCHED并調(diào)用schedule()。延遲調(diào)用方式是經(jīng)過設(shè)置current進(jìn)程的TIF_NEED_RESCHED標(biāo)志為1。當(dāng)恢復(fù)用戶態(tài)進(jìn)程的執(zhí)行前，會檢查該標(biāo)志并決議能否調(diào)用schedule()。延遲調(diào)度的情形有：1)在scheduler_tick()中假設(shè)current用完了時(shí)間片那么設(shè)置該標(biāo)志；2)在try_to_wake_up( )中喚醒一個(gè)進(jìn)程并且該進(jìn)程比當(dāng)前運(yùn)轉(zhuǎn)進(jìn)程優(yōu)先級高。3)調(diào)用sched_setscheduler()時(shí)。schedule()函數(shù)

31、任務(wù)流程：進(jìn)程切換前的任務(wù)：1)制止內(nèi)核搶占，初始化部分變量prev，釋放prev占有的大內(nèi)核鎖；need_resched:preempt_disable();prev = current;release_kernel_lock(prev);2)讀取調(diào)度TSC時(shí)間，計(jì)算調(diào)整run_time時(shí)間， 更新調(diào)度形狀rq-sched_cnt參數(shù)，獲取rq的spin鎖：spin_lock_irq(&rq-lock)。3)檢查prev形狀：假設(shè)形狀不是TASK_RUNNING且沒有在內(nèi)核態(tài)被搶占，那么從運(yùn)轉(zhuǎn)隊(duì)列中移除；但是假設(shè)prev形狀是TASK_INTERRUPTIBLE并且擁有非阻塞掛起的信號，那么

32、把進(jìn)程形狀設(shè)為TASK_RUNNING不移出運(yùn)轉(zhuǎn)隊(duì)列。if (prev-state & !(preempt_count() & PREEMPT_ACTIVE) switch_count = &prev-nvcsw;if (unlikely(prev-state & TASK_INTERRUPTIBLE) &unlikely(signal_pending(prev)prev-state = TASK_RUNNING;else if (prev-state = TASK_UNINTERRUPTIBLE)rq-nr_uninterruptible+;deactivate_task(prev, rq)

33、;4)獲取當(dāng)前CPU邏輯號，假設(shè)當(dāng)前運(yùn)轉(zhuǎn)隊(duì)列為空，那么調(diào)用idle_balance(cpu, rq)從其他CPU運(yùn)轉(zhuǎn)隊(duì)列上拉進(jìn)程到本地CPU的運(yùn)轉(zhuǎn)隊(duì)列上。假設(shè)調(diào)整后，當(dāng)前運(yùn)轉(zhuǎn)隊(duì)列仍為空那么next賦為idle進(jìn)程，跳轉(zhuǎn)到義務(wù)切換代碼行去。if (unlikely(!rq-nr_running) idle_balance(cpu, rq);if (!rq-nr_running) next = rq-idle;rq-expired_timestamp = 0;goto switch_tasks;5)假設(shè)runqueue中有進(jìn)程，并且當(dāng)前活得進(jìn)程數(shù)為0，那么交換active和expired隊(duì)列指針。

34、array = rq-active;if (unlikely(!array-nr_active) schedstat_inc(rq, sched_switch);rq-active = rq-expired;rq-expired = array;array = rq-active;rq-expired_timestamp = 0;rq-best_expired_prio = MAX_PRIO;6)從運(yùn)轉(zhuǎn)隊(duì)列的活動(dòng)prio_array數(shù)據(jù)的位圖中查找第一個(gè)位設(shè)置為1的索引，根據(jù)索引找到該優(yōu)先級隊(duì)列的第一個(gè)task。idx = sched_find_first_bit(array-bitmap);

35、queue = array-queue + idx;next = list_entry(queue-next, struct task_struct, run_list);7)假設(shè)next是普通進(jìn)程，并且next-sleep_type是SLEEP_INTERACTIVE或SLEEP_INTERRUPTED，那么重新計(jì)算進(jìn)程睡眠時(shí)間和進(jìn)程優(yōu)先級。進(jìn)程切換任務(wù)：8)更新sched_goidle，預(yù)期next構(gòu)造數(shù)據(jù)，去除TIF_NEED_RESCHED標(biāo)志，設(shè)置quiescent形狀計(jì)數(shù)為1：rcu_data-passed_quiesc = 1;switch_tasks:if (next = rq

36、-idle)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)轉(zhuǎn)時(shí)間戳prev-sleep_avg，prev-timestamp;10)調(diào)度信息切換到next，更新next;時(shí)間戳和運(yùn)轉(zhuǎn)隊(duì)列信息：sched_info_switch(prev, next);if (likely(prev != next) next-timestamp = next-last_ran = no

37、w;rq-nr_switches+;rq-curr = 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(&rq-lock);barrier()是保證代碼執(zhí)行順序不變。prepare_task_switch(rq, next);prev = context_switch(rq, prev, next);barrier();finish_task_s

38、witch(this_rq(), prev);進(jìn)程切換后的任務(wù)：進(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配對運(yùn)用，并主要鎖的順序。它所做的任務(wù)，finish_lock_switch調(diào)用local_irq_enable(),獲取prev的形狀和rq-prev_mm，假設(shè)mm非空，那么調(diào)用mmdrop(mm)減少mm的援用計(jì)數(shù)，假設(shè)為0那么釋放進(jìn)程頁表和虛擬空間。假

39、設(shè)prev_state為TASK_DEAD那么釋放進(jìn)程的task構(gòu)造。struct mm_struct *mm = rq-prev_mm;long prev_state;rq-prev_mm = NULL;prev_state = prev-state;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

40、(task-lock_depth = 0)那么重新獲取大內(nèi)核鎖_reacquire_kernel_lock，否那么goto need_resched_nonpreemptible;允許搶占，假設(shè)TIF_NEED_RESCHED被設(shè)置，那么跳轉(zhuǎn)到need_resched重新進(jìn)展調(diào)度。prev = current;if (unlikely(reacquire_kernel_lock(prev) vm_ops提供了nopage()函數(shù)，那么用它填充數(shù)據(jù)；否那么調(diào)用do_anonymous_page()匿名函數(shù)來填充數(shù)據(jù)。假設(shè)被文件或設(shè)備映射，假設(shè)時(shí)文件映射，filemap_nopage()將替代no

41、page()函數(shù)，假設(shè)由虛擬文件映射而來，那么shmem_nopage()。每種設(shè)備驅(qū)動(dòng)將提供不同的nopage()函數(shù)，該函數(shù)前往struct page構(gòu)造。3懇求換頁：將頁面交換至后援存儲器后，函數(shù)do_swap_page()擔(dān)任將頁面讀入內(nèi)存，將在后面講述。經(jīng)過PTE的信息就足夠查找到交換的頁面。頁面交換出去時(shí)，普通先放到交換高速緩存中。缺頁中斷時(shí)假設(shè)頁面在高速緩存中，那么只需簡單添加頁面計(jì)數(shù)，然后把它放到進(jìn)程頁表中并計(jì)數(shù)次缺頁中斷發(fā)生的次數(shù)。假設(shè)頁面僅存在磁盤中，Linux將調(diào)用swapin_readahead()讀取它及后續(xù)的假設(shè)干頁面。4頁面幀回收除了slab分配器，系統(tǒng)中一切正在

42、運(yùn)用的頁面都存放在頁面高速緩存中，并由lru鏈接在一同。Slab頁面不存放到高速緩存中由于基于被slab運(yùn)用的對象對頁面計(jì)數(shù)很困難。除了查找每個(gè)進(jìn)程頁表外沒有其他方法能把struct page映射為PTE，查找頁表代價(jià)很大。假設(shè)頁面高速緩存中存在大量的進(jìn)程映射頁面，系統(tǒng)將會遍歷進(jìn)程頁表，經(jīng)過swap_out()函數(shù)交換出頁面直到有足夠的頁面空閑，而共享頁會給swap_out()帶來問題。假設(shè)一個(gè)頁面是共享的，同時(shí)一個(gè)交換項(xiàng)曾經(jīng)被分配，PTE就會填寫所需信息以便在交換分區(qū)里重新找到該頁并將援用計(jì)數(shù)減1。只需援用計(jì)數(shù)為0時(shí)該頁才干被交換出去。內(nèi)存和磁盤緩存懇求越來越多的頁面但確無法判別如何釋放進(jìn)程

43、頁面，懇求分頁機(jī)制在進(jìn)程頁面缺失時(shí)懇求新頁面，但它卻不能強(qiáng)迫釋放進(jìn)程不再運(yù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)核動(dòng)態(tài)分配的頁面、進(jìn)程內(nèi)核棧的頁面、設(shè)置了PG_locked標(biāo)志的暫時(shí)鎖住的頁面、設(shè)置了VM_LOCKED標(biāo)志的內(nèi)存頁面。2)Swappable

44、可交換的頁面，用戶進(jìn)程空間的匿名頁面(用戶堆棧)、tmpfs文件系統(tǒng)的映射頁面入IPC共享內(nèi)存頁面，頁面存放到交換空間。3)Syncable可同步的頁面，入用戶態(tài)地址空間的映射頁面、維護(hù)磁盤數(shù)據(jù)的頁面緩存的頁面、塊設(shè)備緩沖頁、磁盤緩存的頁面入inode cache，假設(shè)有必要的話，需同步磁盤映像上的數(shù)據(jù)。4)Discardable可丟棄的頁面，入內(nèi)存緩存中的無用頁面slab分配器中的頁面、dentry cache的頁面。PFRA算法是基于閱歷而非實(shí)際的算法，它的設(shè)計(jì)原那么如下：1)首先釋放無損壞的頁面。進(jìn)程不再援用的磁盤和內(nèi)存緩存應(yīng)該先于用戶態(tài)地址空間的頁面釋放。2)標(biāo)志一切進(jìn)程態(tài)進(jìn)程的頁面為

45、可回收的。3)多進(jìn)程共享頁面的回收，要先去除援用該頁面的進(jìn)程頁表項(xiàng)，然后再回收。4)回收“不在運(yùn)用的頁面。PFRA用LRU鏈表把進(jìn)程劃分為in-use和unused兩種，PFRA僅回收unused形狀的頁面。Linux運(yùn)用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)入suspend-to-disk形狀時(shí)進(jìn)展回收。3)周期性回收，內(nèi)核線程周期性激活并在必要時(shí)進(jìn)展頁面回收。Low on memory回收有以下幾種情形：1)_ _getblk( )調(diào)用的grow_buffers( )函數(shù)分

46、配新緩存頁失?。?)create_empty_buffers( )調(diào)用的alloc_page_buffers( )函數(shù)為頁面分配暫時(shí)的buffer head失?。?)_ _alloc_pages( )函數(shù)在給定內(nèi)存區(qū)里分配一組延續(xù)的頁面幀失敗。周期性回收涉及的兩種內(nèi)核線程：1)Kswapd內(nèi)核線程在內(nèi)存區(qū)中檢測空閑頁面能否低于pages_high的門檻值；2)預(yù)定義任務(wù)隊(duì)列中的事件內(nèi)核線程，PFRA周期性調(diào)度該任務(wù)隊(duì)列中的task回收slab分配器中一切空閑的slab；一切用戶空間進(jìn)程和頁面緩存的頁面被分為活動(dòng)鏈表和非活動(dòng)鏈表，統(tǒng)稱LRU鏈表。每個(gè)區(qū)描畫符中包括active_list和inac

47、tive_list兩個(gè)鏈表分別將這些頁面鏈接起來。nr_active和nr_inactive分別表示這兩種頁面數(shù)量，lru_lock用于同步。頁描畫符中的PG_lru用于標(biāo)志一個(gè)頁面能否屬于LRU鏈表，PG_active用于標(biāo)志頁面能否屬于活動(dòng)鏈表，lru字段用于把LRU中的鏈表串起來?；顒?dòng)鏈表和非活動(dòng)鏈表的頁面根據(jù)最近的訪問情況進(jìn)展動(dòng)態(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_cach

48、e_add_active()等，這些函數(shù)比較簡單。shrink_active_list ( )用于將頁表從活動(dòng)鏈表移到非活動(dòng)鏈表。該函數(shù)在shrink_zone()函數(shù)執(zhí)行用戶地址空間的頁面回收時(shí)執(zhí)行。5交換分區(qū)：系統(tǒng)可以有MAX_SWAPFILES的交換分區(qū)，每個(gè)分區(qū)可放在磁盤分區(qū)上或者普通文件里。每個(gè)交換區(qū)由一系列頁槽組成。每個(gè)交換區(qū)有個(gè)swap_header構(gòu)造描畫交換區(qū)版本等信息。每個(gè)交換區(qū)有假設(shè)干個(gè)swap_extent組成，每個(gè)swap_extent是延續(xù)的物理區(qū)域。對于磁盤交換區(qū)只需一個(gè)swap_extent，對于文件交換區(qū)那么由多個(gè)swap_extent組成，由于文件并不是放在

49、延續(xù)的磁盤塊上的。mkswap命令可以創(chuàng)建交換分區(qū)。圖 交換分區(qū)構(gòu)造圖 交換頁構(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è)進(jìn)程共用，它能夠被從一個(gè)進(jìn)程地址空間換出但依然在物理內(nèi)存上，因此一個(gè)頁面能夠被多次換出。但物理上僅第一次被換出并存儲在交換區(qū)上，接下來的換出操作只是添加swap_map的援用計(jì)數(shù)。swap_duplicate(swp_entry_t en

50、try)的功能正是用戶嘗試換出一個(gè)曾經(jīng)換出的頁面。6交換緩存：多個(gè)進(jìn)程同時(shí)換進(jìn)一個(gè)共享匿名頁時(shí)或者一個(gè)進(jìn)程換入一個(gè)正被PFRA換出的頁時(shí)存在競爭條件，引入交換緩存處理這種同步問題。經(jīng)過PG_locked標(biāo)志可以保證對一個(gè)頁的并發(fā)的交換操作只作用在一個(gè)頁面上，從而防止競爭條件。7.頁面回收算法描畫：以下圖是各種情況下進(jìn)展頁面回收時(shí)的函數(shù)調(diào)用關(guān)系圖?？梢钥闯鲎罱K調(diào)用函數(shù)為cache_reap()、shrink_slab()和shrink_list()。cache_reap()用于周期性回收slab分配器中的無用slab。shrink_slab()用于回收磁盤緩存的頁面。shrink_list()是

51、頁面回收的中心函數(shù)，在最新代碼中該函數(shù)名改為shrink_page_list()。下面會重點(diǎn)講解。圖中shrink_caches()最新函數(shù)名為shrink_zones()、shrink_cache()最新函數(shù)名為shrink_inactive_list()。其他函數(shù)不變。圖PFRA函數(shù)構(gòu)造調(diào)用關(guān)系低內(nèi)存回收頁面：如上圖所示，當(dāng)內(nèi)存分配失敗時(shí)，內(nèi)核調(diào)用free_more_memory(),該函數(shù)首先調(diào)用wakeup_bdflush( )喚醒pdflush內(nèi)核線程觸發(fā)寫操作，從磁盤頁面緩沖中寫1024個(gè)dirty頁面到磁盤上以釋放包含緩沖、緩沖頭和VFS的數(shù)據(jù)構(gòu)造所占用的頁表；然后進(jìn)展系統(tǒng)調(diào)用s

52、ched_yield( )，以使pdflush線程可以有時(shí)機(jī)運(yùn)轉(zhuǎn)；最后該函數(shù)循環(huán)遍歷系統(tǒng)節(jié)點(diǎn)，對每個(gè)節(jié)點(diǎn)上的低內(nèi)存區(qū)(ZONE_DMA和ZONE_NORMAL)調(diào)用try_to_free_pages( )函數(shù)。try_to_free_pages(struct zone *zones, gfp_t gfp_mask)函數(shù)的目的是經(jīng)過循環(huán)調(diào)用shrink_slab()和shrink_zones()釋放至少32個(gè)頁幀，每次調(diào)用添加優(yōu)先級參數(shù)，初始優(yōu)先級是12，最高為0。假設(shè)循環(huán)13次，依然沒有釋放掉32個(gè)頁面，那么PFRA進(jìn)展內(nèi)存異出維護(hù)：調(diào)用out_of_memory()函數(shù)選擇一個(gè)進(jìn)程回收它一切

53、的頁面。shrink_zones(int priority, struct zone *zones,struct scan_control *sc)函數(shù)對zones列表中每個(gè)區(qū)調(diào)用shrink_zone()函數(shù)。調(diào)用shrink_zone()前，先用sc-priority的值更新zone描畫符中的prev_priority，假設(shè)zone-all_unreclaimable字段不為0且優(yōu)先級不是12，那么不對該區(qū)進(jìn)展頁面回收。shrink_zone(int priority, struct zone *zone, struct scan_control *sc)函數(shù)嘗試回收32個(gè)頁面。該函數(shù)循環(huán)

54、進(jìn)展shrink_active_list()和shrink_inactive_list的操作以到達(dá)目的。該函數(shù)流程如下：1)atomic_inc(&zone-reclaim_in_progress)添加區(qū)的回收計(jì)數(shù)；2)添加zone-nr_scan_active，根據(jù)優(yōu)先級，添加范圍是zone-nr_active/212tozone-nr_active/20。假設(shè)zone-nr_scan_active = 32那么賦給nr_active變量，同時(shí)zone-nr_scan_active設(shè)為0，否那么nr_active0；3)zone-nr_scan_inactive和nr_inactive做同樣

55、處置；4)假設(shè)nr_active和nr_inactive不同時(shí)為空，那么進(jìn)展while循環(huán)進(jìn)展5、6步操作：5)假設(shè)nr_active非0，那么從active鏈表挪動(dòng)某些頁面到inactive鏈表：nr_to_scan = min(nr_active,(unsigned long)sc-swap_cluster_max);nr_active -= nr_to_scan;shrink_active_list(nr_to_scan, zone, sc, priority);6)假設(shè)nr_inactive非0，那么回收inactive鏈表中的頁面：nr_to_scan = min(nr_inacti

56、ve,(unsigned long)sc-swap_cluster_max);nr_inactive -= nr_to_scan;nr_reclaimed += shrink_inactive_list(nr_to_scan, zone, sc);7)atomic_dec(&zone-reclaim_in_progress)減小回收計(jì)數(shù)，并前往回收頁面數(shù)nr_reclaimed；shrink_inactive_list(unsigned long max_scan, struct zone *zone, struct scan_control *sc)函數(shù)從區(qū)的inactive鏈表中抽取一組頁

57、面，放到暫時(shí)鏈表中，調(diào)用shrink_page_list()對鏈表中的每個(gè)頁面進(jìn)展回收。下面是shrink_inactive_list()主要步驟：1)調(diào)用lru_add_drain()將當(dāng)前CPU上pagevec構(gòu)造的lru_add_pvecs和lru_add_active_pvecs中的頁面分別移到活動(dòng)鏈表和非活動(dòng)鏈表中；2)獲取LRU鎖spin_lock_irq(&zone-lru_lock);3)最多掃描max_scan個(gè)頁面，對每個(gè)頁面添加運(yùn)用計(jì)數(shù)，檢查該頁面能否正被釋放到同伴系統(tǒng)中，將該頁面挪動(dòng)一個(gè)暫時(shí)鏈表中；4)從zone-nr_inactive中減去移到暫時(shí)鏈表中的頁面數(shù)；5)

58、添加zone-pages_scanned計(jì)數(shù)；6)釋放LRU鎖：spin_unlock_irq(&zone-lru_lock)；7)對暫時(shí)鏈表調(diào)用shrink_page_list(&page_list, sc)回收頁面；8)添加nr_reclaimed計(jì)數(shù)；9)獲取LRU鎖spin_lock(&zone-lru_lock)；10)將shrink_page_list(&page_list, sc)沒有回收掉的頁面重新添加到active鏈表和inactive鏈表中。該函數(shù)在回收過程中能夠會設(shè)置PG_active標(biāo)志，所以也要思索往active鏈表中添加。11)假設(shè)掃描頁面數(shù)nr_scanned小于

59、max_scan那么循環(huán)進(jìn)展310的操作；12)前往回收的頁面數(shù)；shrink_page_list(struct list_head *page_list, struct scan_control *sc)做真正的頁面回收任務(wù)，該函數(shù)流程如下：圖shrink_page_list()頁面回收邏輯處置流程1)調(diào)用cond_resched()進(jìn)展條件調(diào)度；2)循環(huán)遍歷page_list中每個(gè)頁面，從列表中移出該頁面描畫符并回收該頁面，假設(shè)回收失敗，那么把該頁面插入一個(gè)部分鏈表中；該步流程參見流程圖。l調(diào)用cond_resched()進(jìn)展條件調(diào)度；l從LRU鏈表中取出第一個(gè)頁面并從LRU鏈表中刪除；l

60、假設(shè)頁面被鎖定，這調(diào)過該頁面，該頁加到暫時(shí)鏈表中；l假設(shè)頁面不能部分回收并且頁面是進(jìn)程頁表的映射，這跳過該頁；l假設(shè)進(jìn)程是回寫的dirty頁面，那么跳過；l假設(shè)頁面被援用并且頁面映射在運(yùn)用，這跳過并激活該頁面，以便后面放入active列表；l假設(shè)是匿名頁面且不在交換區(qū)中，這調(diào)用add_to_swap()為該頁面分配交換區(qū)空間并把該頁加到交換緩存中；l假設(shè)頁面是進(jìn)程空間映射并且頁面映射地址非空，那么調(diào)用try_to_unmap()移除該頁面的頁表映射；l假設(shè)頁面為dirty頁面并且無援用、交換可寫、且是fs文件系統(tǒng)映射，調(diào)用pageout()寫出該頁面。3)循環(huán)終了，把部分鏈表中的頁面移回到pa