ARM Linux進程調(diào)度.doc

ARM Linux進程調(diào)度小弟最近研究了一段時間的ARM Linux,想把進程管理方面的感受跟大家交流下，不對的地方多多指點Process Creation and TerminationProcess Scheduling and DispatchingProcess SwitchingPorcess Synchronization and support for interprocess communicationManagement of process control block-from 進程調(diào)度 Linux2.4.x是一個基于非搶占式的多任務(wù)的分時操作系統(tǒng)，雖然在用戶進程的調(diào)度上采用搶占式策略，但是而在內(nèi)核還是采用了輪轉(zhuǎn)的方法，如果有個內(nèi)核態(tài)的線程惡性占有CPU不釋放，那系統(tǒng)無法從中解脫出來，所以實時性并不是很強。這種情況有望在Linux 2.6版本中得到改善，在2.6版本中采用了搶占式的調(diào)度策略。內(nèi)核中根據(jù)任務(wù)的實時程度提供了三種調(diào)度策略：1. SCHED_OTHER為非實時任務(wù)，采用常規(guī)的分時調(diào)度策略；2. SCHED_FIFO為短小的實時任務(wù)，采用先進先出式調(diào)度，除非有更高優(yōu)先級進程申請運行，否則該進程將保持運行至退出才讓出CPU；3. SCHED_RR任務(wù)較長的實時任務(wù)，由于任務(wù)較長，不能采用FIFO的策略，而是采用輪轉(zhuǎn)式調(diào)度，該進程被調(diào)度下來后將被置于運行隊列的末尾，以保證其他實時進程有機會運行。需要說明的是，SCHED_FIFO和SCHED_RR兩種調(diào)度策略之間沒有優(yōu)先級上的區(qū)別，主要的區(qū)別是任務(wù)的大小上。另外，task_struct結(jié)構(gòu)中的policy中還包含了一個SCHED_YIELD位，置位時表示該進程主動放棄CPU。在上述三種調(diào)度策略的基礎(chǔ)上，進程依照優(yōu)先級的高低被分別調(diào)系統(tǒng)。優(yōu)先級是一些簡單的整數(shù)，它代表了為決定應(yīng)該允許哪一個進程使用CPU的資源時判斷方便而賦予進程的權(quán)值優(yōu)先級越高，它得到CPU時間的機會也就越大。在Linux中，非實時進程有兩種優(yōu)先級，一種是靜態(tài)優(yōu)先級，另一種是動態(tài)優(yōu)先級。實時進程又增加了第三種優(yōu)先級，實時優(yōu)先級。1. 靜態(tài)優(yōu)先級（priority）被稱為“靜態(tài)”是因為它不隨時間而改變，只能由用戶進行修改。它指明了在被迫和其它進程競爭CPU之前該進程所應(yīng)該被允許的時間片的最大值（20）。2. 動態(tài)優(yōu)先級（counter）counter 即系統(tǒng)為每個進程運行而分配的時間片，Linux兼用它來表示進程的動態(tài)優(yōu)先級。只要進程擁有CPU，它就隨著時間不斷減??；當(dāng)它為0時，標(biāo)記進程重新調(diào)度。它指明了在當(dāng)前時間片中所剩余的時間量（最初為20）。3. 實時優(yōu)先級(rt_priority)值為1000。Linux把實時優(yōu)先級與counter值相加作為實時進程的優(yōu)先權(quán)值。較高權(quán)值的進程總是優(yōu)先于較低權(quán)值的進程，理L垠I-;供Yo6網(wǎng)n,如果一個進程不是實時進程，其優(yōu)先權(quán)就遠小于1000，所以實時進程總是優(yōu)先。在每個tick到來的時候（也就是時鐘中斷發(fā)生），系統(tǒng)減小當(dāng)前占有CPU的進程的counter，如果counter減小到0，則將need_resched置1，中斷返回過程中進行調(diào)度。update_process_times()為時鐘中斷處理程序調(diào)用的一個子函數(shù)：void update_process_times(int user_tick) struct task_struct *p = current; int cpu = smp_processor_id(), system = user_tick 1; update_one_process(p, user_tick, system, cpu); if (p-pid) if (-p-counter counter = 0; p-need_resched = 1; if (p-nice 0) kstat.per_cpu_nicecpu += user_tick; else kstat.per_cpu_usercpu += user_tick; kstat.per_cpu_systemcpu += system; else if (local_bh_count(cpu) | local_irq_count(cpu) 1) kstat.per_cpu_systemcpu += system;Linux中進程的調(diào)度使在schedule（）函數(shù)中實現(xiàn)的，該函數(shù)在下面的ARM匯編片斷中被調(diào)用到：/* This is the fast syscall return path. We do as little as* possible here, and this includes saving r0 back into the SVC* stack.*/ret_fast_syscall: ldr r1, tsk, #TSK_NEED_RESCHED ldr r2, tsk, #TSK_SIGPENDING teq r1, #0 need_resched | sigpending teqeq r2, #0 bne slow fast_restore_user_regs/* Ok, we need to do extra processing, enter the slow path.*/slow: str r0, sp, #S_R0+S_OFF! returned r0 b 1f/* slow syscall return path. why tells us if this was a real syscall.*/reschedule: bl SYMBOL_NAME(schedule)ENTRY(ret_to_user)ret_slow_syscall: ldr r1, tsk, #TSK_NEED_RESCHED ldr r2, tsk, #TSK_SIGPENDING1: teq r1, #0 need_resched = schedule() bne reschedule 如果需要重新調(diào)度則調(diào)用schedule teq r2, #0 sigpending = do_signal() blne _do_signal restore_user_regs而這段代碼在中斷返回或者系統(tǒng)調(diào)用返回中反復(fù)被調(diào)用到。1 進程狀態(tài)轉(zhuǎn)換時： 如進程終止，睡眠等,當(dāng)進程要調(diào)用sleep（）或exit（）等函數(shù)使進程狀態(tài)發(fā)生改變時，這些函數(shù)會主動調(diào)用schedule（）轉(zhuǎn)入進程調(diào)度。2 可運行隊列中增加新的進程時；ENTRY(ret_from_fork) bl SYMBOL_NAME(schedule_tail) get_current_task tsk ldr ip, tsk, #TSK_PTRACE check for syscall tracing mov why, #1 tst ip, #PT_TRACESYS are we tracing syscalls? beq ret_slow_syscall mov r1, sp mov r0, #1 trace exit IP = 1 bl SYMBOL_NAME(syscall_trace) b ret_slow_syscall 跳轉(zhuǎn)到上面的代碼片斷3 在時鐘中斷到來后：Linux初始化時，設(shè)定系統(tǒng)定時器的周期為10毫秒。當(dāng)時鐘中斷發(fā)生時，時鐘中斷服務(wù)程序timer_interrupt立即調(diào)用時鐘處理函數(shù)do_timer( )，在do_timer()會將當(dāng)前進程的counter減1，如果counter為0則置need_resched標(biāo)志，在從時鐘中斷返回的過程中會調(diào)用schedule.4 進程從系統(tǒng)調(diào)用返回到用戶態(tài)時；判斷need_resched標(biāo)志是否置位，若是則轉(zhuǎn)入執(zhí)行schedule()。系統(tǒng)調(diào)用實際上就是通過軟中斷實現(xiàn)的，下面是ARM平臺下軟中斷處理代碼。 .align 5ENTRY(vector_swi) save_user_regs zero_fp get_scno enable_irqs ip str r4, sp, #-S_OFF! push fifth arg get_current_task tsk ldr ip, tsk, #TSK_PTRACE check for syscall tracing bic scno, scno, #0xff000000 mask off SWI op-code eor scno, scno, #OS_NUMBER 20 check OS number adr tbl, sys_call_table load syscall table pointer tst ip, #PT_TRACESYS are we tracing syscalls? bne _sys_trace adrsvc al, lr, ret_fast_syscall 裝載返回地址，用于在跳轉(zhuǎn)調(diào)用后返回到 上面的代碼片斷中的ret_fast_syscall cmp scno, #NR_syscalls check upper syscall limit ldrcc pc, tbl, scno, lsl #2 call sys_* routine add r1, sp, #S_OFF2: mov why, #0 no longer a real syscall cmp scno, #ARMSWI_OFFSET eor r0, scno, #OS_NUMBER active_mm) BUG();need_resched_back: prev = current; this_cpu = prev-processor; if (unlikely(in_interrupt() printk(Scheduling in interruptn); BUG(); release_kernel_lock(prev, this_cpu); /* * sched_data is protected by the fact that we can run * only one process per CPU. */ sched_data = & aligned_datathis_cpu.schedule_data; spin_lock_irq(&runqueue_lock); /* move an exhausted RR process to be last. */ if (unlikely(prev-policy = SCHED_RR) /* * 如果采用輪轉(zhuǎn)法調(diào)度，則重新檢查counter是否為0, 若是則將其掛到運行隊列的最后 */ if (!prev-counter) prev-counter = NICE_TO_TICKS(prev-nice); move_last_runqueue(prev); switch (prev-state) case TASK_INTERRUPTIBLE: /* * 如果是TASK_INTERRUPTIBLE,并且能夠喚醒它的信號已經(jīng)來臨, * 則將狀態(tài)置為TASK_RUNNING */ if (signal_pending(prev) prev-state = TASK_RUNNING; break; default: del_from_runqueue(prev); case TASK_RUNNING:; prev-need_resched = 0; /* * this is the scheduler proper: */repeat_schedule: /* * Default process to select. */ next = idle_task(this_cpu); c = -1000; list_for_each(tmp, &runqueue_head) /* * 遍歷運行隊列,查找優(yōu)先級最高的進程, 優(yōu)先級最高的進程將獲得CPU */ p = list_entry(tmp, struct task_struct, run_list); if (can_schedule(p, this_cpu) /* * goodness()中，如果是實時進程，則weight = 1000 p-rt_priority, * 使實時進程的優(yōu)先級永遠比非實時進程高 */ int weight = goodness(p, this_cpu, prev-active_mm); if (weight c) /注意這里是”而不是”=”，如果權(quán)值相同，則先來的先上 c = weight, next = p; /* Do we need to re-calculate counters? */ if (unlikely(!c) /* * 如果當(dāng)前優(yōu)先級為0,那么整個運行隊列中的進程將重新計算優(yōu)先權(quán) */ struct task_struct *p; spin_unlock_irq(&runqueue_lock); read_lock(&tasklist_lock); for_each_task(p) p-counter = (p-counter 1) NICE_TO_TICKS(p-nice); read_unlock(&tasklist_lock); spin_lock_irq(&runqueue_lock); goto repeat_schedule; /* * from this point on nothing can prevent us from * switching to the next task, save this fact in sched_data. */ sched_data-curr = next; task_set_cpu(next, this_cpu); spin_unlock_irq(&runqueue_lock); if (unlikely(prev = next) /* We wont go through the normal tail, so do this by hand */ prev-policy &= SCHED_YIELD; goto same_process; kstat.context_swtch ; /* * there are 3 processes which are affected by a context switch: * * prev = . = (last = next) * * Its the much more previous prev that is on nexts stack, * but prev is set to (the just run) last process by switch_to(). * This might sound slightly confusing but makes tons of sense. */ prepare_to_switch(); struct mm_struct *mm = next-mm; struct mm_struct *oldmm = prev-active_mm; if (!mm) /如果是內(nèi)核線程的切換，則不做頁表處理 if (next-active_mm) BUG(); next-active_mm = oldmm; atomic_inc(&oldmm-mm_count); enter_lazy_tlb(oldmm, next, this_cpu); else if (next-active_mm != mm) BUG(); switch_mm(oldmm, mm, next, this_cpu); /如果是用戶進程，切換頁表 if (!prev-mm) prev-active_mm = NULL; mmdrop(oldmm); /* * This just switches the register state and the stack. */ switch_to(prev, next, prev); _schedule_tail(prev);same_process: reacquire_kernel_lock(current); if (current-need_resched) goto need_resched_back; return;switch_mm中是進行頁表的切換，即將下一個的pgd的開始物理地址放入CP15中的C2寄存器。進程的pgd的虛擬地址存放在task_struct結(jié)構(gòu)中的pgd指針中，通過_virt_to_phys宏可以轉(zhuǎn)變成成物理地址。static inline voidswitch_mm(struct mm_struct *prev, struct mm_struct *next, struct task_struct *tsk, unsigned int cpu) if (prev != next) cpu_switch_mm(next-pgd, tsk);#define cpu_switch_mm(pgd,tsk) cpu_set_pgd(_virt_to_phys(unsigned long)(pgd)#define cpu_get_pgd() ( unsigned long pg; _asm_(mrc p15, 0, %0, c2, c0, 0 : =r (pg); pg &= 0x3fff; (pgd_t *)phys_to_virt(pg); )switch_to()完成進程上下文的切換，通過調(diào)用匯編函數(shù)_switch_to完成，其實現(xiàn)比較簡單，也就是保存prev進程的上下文信息，該上下文信息由context_save_struct結(jié)構(gòu)描述，包括主要的寄存