Linux進(jìn)程管理與調(diào)度

1、linux進(jìn)程管理與調(diào)度進(jìn)程管理與調(diào)度 關(guān)于進(jìn)程與線程 linux進(jìn)程實(shí)現(xiàn) linux進(jìn)程調(diào)度策略 linux進(jìn)程調(diào)度實(shí)現(xiàn)1 linux進(jìn)程與線程進(jìn)程與線程linux進(jìn)程進(jìn)程 linux線程線程進(jìn)程作為資源分配的基本單位而存在，線程作為調(diào)度的基本單位而存在我們都知道linux是不斷發(fā)展的.在早期版本中, linux的基本調(diào)度單元是task,只到現(xiàn)在, 依然是它. 在早期版本中, 一個(gè)task對(duì)應(yīng)著一個(gè)進(jìn)程, 完全沒有線程這個(gè)概念. 隨著時(shí)間的發(fā)展, 線程的概念出現(xiàn)的, 但是linux并沒有馬上接受這一概念, 要知道, 線程是現(xiàn)代操作系統(tǒng)的特征, 向一個(gè)現(xiàn)有的操作系統(tǒng)內(nèi)核引入線程是一件傷筋動(dòng)骨的

2、事情, 更何況在線程概念的早期, 受歷史原因(unix)和硬件的限制(多核尚不是主流), 線程的地位尚不確定. 所以, linux并沒有在內(nèi)核中引入線程的概念. 但是, linux提供了一個(gè)新的系統(tǒng)調(diào)用clone, 通過該系統(tǒng)調(diào)用, 內(nèi)核中的多個(gè)進(jìn)程可以共享一些信息, 比如進(jìn)程空間等. 注意, 此時(shí)linux內(nèi)核的基礎(chǔ)調(diào)度單元依然是task, 而且在內(nèi)核看來, 一個(gè)進(jìn)程依然對(duì)應(yīng)著一個(gè)task. 2 linux進(jìn)程實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)linux進(jìn)程描述符進(jìn)程描述符也稱 進(jìn)程控制塊pcb：shruct task_struct unsigned long state; /進(jìn)程的狀態(tài)，在2.6.23已經(jīng)有9個(gè)

3、狀態(tài) unsigned long policy; /描述進(jìn)程調(diào)度策略.判斷是實(shí)時(shí)進(jìn)程還是非實(shí)時(shí)進(jìn)程struct task_struct *parent; /組織進(jìn)程的層次關(guān)系，指向父進(jìn)程 struct list_head tasks; /通過list_head組織成雙向鏈表 pid_t pid; /每個(gè)進(jìn)程唯一的標(biāo)號(hào) . ; linux進(jìn)程描述符進(jìn)程描述符在內(nèi)核棧底創(chuàng)建新的結(jié)構(gòu)struct thread_infostruct thread_info struct task_struct *task; struct exec_domain *exec_domain; unsigned long

4、flags; unsigned long status; _u32 cpu; ;在linux內(nèi)核中，進(jìn)程被分為兩部分，一部分是thread_info,保存在內(nèi)核棧中，為了保持很小，因此只保存了必須的幾個(gè)域，它有一個(gè)變量task，指向task_struct,這個(gè)結(jié)構(gòu)保存了進(jìn)程相關(guān)的所有信息。而對(duì)應(yīng)的task_struct也保存了一個(gè)變量stack指向的就是一個(gè)thread_union的聯(lián)合體linux進(jìn)程實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)相關(guān)的系統(tǒng)調(diào)用相關(guān)的系統(tǒng)調(diào)用 fork(): 創(chuàng)建普通進(jìn)程,copy on write（要復(fù)制父進(jìn)程的頁表）創(chuàng)建后子進(jìn)程和父進(jìn)程指向同一內(nèi)存區(qū)域，僅當(dāng)子進(jìn)程有write發(fā)生時(shí)候，才會(huì)

5、把改動(dòng)的區(qū)域copy到子進(jìn)程新的地址空間 vfork()： 共享創(chuàng)建，完全無拷貝。（子進(jìn)程作為父進(jìn)程的一個(gè)單獨(dú)線程在其地址空間運(yùn)行，父進(jìn)程阻塞） clone(): 介于fork()和vfork()之間，可以指定共享什么，拷貝什么。說明：vfork()與clone()可用于創(chuàng)建新的內(nèi)核線程。linux進(jìn)程實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)相關(guān)的函數(shù)相關(guān)的函數(shù) do_fork()：/ 被clone(),fork(),vfork()調(diào)用，執(zhí)行步驟如下： 檢查父進(jìn)程標(biāo)志是否為空。 調(diào)用alloc_task_struct()為新進(jìn)程分配一段內(nèi)存空間，并將父進(jìn)程描述符的內(nèi)容拷貝到子進(jìn)程。 檢查進(jìn)程是否得到所需資源及系統(tǒng)當(dāng)前允許

6、的最大進(jìn)程數(shù)。 如進(jìn)程需要引用內(nèi)核模塊，則增加模塊引用計(jì)數(shù)。 更新從父進(jìn)程拷貝來的信息。 系統(tǒng)調(diào)用get_pid()，將獲得的pid賦給新建的子進(jìn)程。 更新不能由父進(jìn)程繼承的域。 為新進(jìn)程的執(zhí)行設(shè)置跟蹤進(jìn)程的相關(guān)內(nèi)核數(shù)據(jù)結(jié)構(gòu)，新進(jìn)程入鏈表。置新進(jìn)程狀態(tài)為task_running, 。 向父進(jìn)程返回pid。說明：說明： 創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用返回時(shí)（ret_from_sys_call），將根據(jù)存放系統(tǒng)調(diào)用返回值寄存器eax的內(nèi)容(pid)是0還是一個(gè)小正整數(shù)來決定是運(yùn)行父進(jìn)程還是子進(jìn)程。在linux中第一個(gè)進(jìn)程是內(nèi)核進(jìn)程，pid為0，它是所有的進(jìn)程的父進(jìn)程。這個(gè)進(jìn)程也叫swapper，或者說是idl

7、e.linux進(jìn)程狀態(tài)進(jìn)程狀態(tài)task_running：進(jìn)程在運(yùn)行 ( 是系統(tǒng)的當(dāng)前進(jìn)程 ) 或者準(zhǔn)備運(yùn)行（等待被安排到系統(tǒng)的一個(gè)cpu上）。task_interruptible：進(jìn)程處于某個(gè)等待隊(duì)列中，它能夠被信號(hào)（signal）喚醒。等待資源的請(qǐng)求滿足時(shí)，也被喚醒。task_uninterruptible: :進(jìn)程處于某個(gè)等待隊(duì)列中，不能被信號(hào)或中斷喚醒，只有等待的資源被滿足時(shí)才被喚醒。task_zombie: : 進(jìn)程已經(jīng)停止，但還沒有釋放進(jìn)程控制塊。 task_stopped：可能是被特定的信號(hào)終止，也可能是受其它進(jìn)程的跟蹤調(diào)用而暫時(shí)將cpu交給跟蹤它的進(jìn)程。 linux狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)

8、換task_runningtask_runningtask_interruptibletask_interruptibletask_uninterruptibletask_uninterruptible擁有cpu擁有cputask_stoppedtask_stoppedtask_zombietask_zombiedo_fork()schedule()時(shí)間片到schedule()interruptible_sleep_on()schedule()sleep_on()do_exit()syscall_trace( )schedule( )sys_exit( )收到sig_kill或sig_cont

9、后，執(zhí)行wake_up( )wake_up()wake_up_interruptible()scheduler and dispatcher線程的實(shí)現(xiàn)線程的實(shí)現(xiàn)在在linux系統(tǒng)中，線程被當(dāng)作與其他進(jìn)程共享某些資源的進(jìn)程系統(tǒng)中，線程被當(dāng)作與其他進(jìn)程共享某些資源的進(jìn)程.線程的創(chuàng)建：與普通進(jìn)程相似，需要指明共享資源。線程的創(chuàng)建：與普通進(jìn)程相似，需要指明共享資源。如：如：clone (clone_vm | clone_fs | clone_files|clone_sighand,0);對(duì)比：對(duì)比：clone (sigchld, 0) /普通的fork() clone (clone_vfork | c

10、lone_vm | sigchld, 0)內(nèi)核線程：內(nèi)核進(jìn)程沒有獨(dú)立的地址空間，只在內(nèi)核空間運(yùn)內(nèi)核線程：內(nèi)核進(jìn)程沒有獨(dú)立的地址空間，只在內(nèi)核空間運(yùn)行。通常是一些后臺(tái)執(zhí)行的任務(wù)。行。通常是一些后臺(tái)執(zhí)行的任務(wù)。通過通過clone()的參數(shù)，新創(chuàng)建的進(jìn)程，也稱為的參數(shù)，新創(chuàng)建的進(jìn)程，也稱為lwp(lightweight process)與父進(jìn)程共享內(nèi)存空間，文件句柄，信號(hào)處理等，從與父進(jìn)程共享內(nèi)存空間，文件句柄，信號(hào)處理等，從而達(dá)到創(chuàng)建線程相同的目的。而達(dá)到創(chuàng)建線程相同的目的。5 linux進(jìn)程調(diào)度策略進(jìn)程調(diào)度策略1) 搶占式調(diào)度策略當(dāng)一個(gè)進(jìn)程進(jìn)入task_running狀態(tài)，內(nèi)核檢查其優(yōu)先級(jí)是否高

11、于當(dāng)前進(jìn)程。當(dāng)一個(gè)進(jìn)程的時(shí)間片為0時(shí)，也會(huì)被搶占。搶占：用戶搶占：need_resched標(biāo)志設(shè)置即發(fā)生，包括從系統(tǒng)調(diào)用返回用戶空間、 從中斷處理程序返回用戶空間的情況。內(nèi)核搶占：為每個(gè)進(jìn)程的thread_info引入了preempt_count計(jì)數(shù)器，該計(jì)數(shù) 器初值為0，加鎖時(shí)，其值加1，其數(shù)值為0時(shí)，內(nèi)核可執(zhí)行搶 占。中斷返回內(nèi)核空間時(shí)產(chǎn)生。linux進(jìn)程調(diào)度策略進(jìn)程調(diào)度策略2) 時(shí)間片調(diào)度策略內(nèi)核根據(jù)時(shí)間片是否耗盡為標(biāo)準(zhǔn)，將就緒進(jìn)程分為active, expired兩類。新創(chuàng)建的子進(jìn)程和父進(jìn)程均分父進(jìn)程的剩余時(shí)間片時(shí)間片的計(jì)算以靜態(tài)優(yōu)先級(jí)為基礎(chǔ)，即由task_timeslice()函數(shù)根

12、據(jù)靜態(tài)優(yōu)先級(jí)按照比例縮放。時(shí)間片的遞減和重置在時(shí)鐘中斷中進(jìn)行，sheduler_tick()時(shí)間片計(jì)算： min_timeslice+(max_timeslice min_timeslice)*(max_prio-1-(p)-static_prio)/(max_user_prio-1)即：將100139的優(yōu)先級(jí)映射到200ms10ms的時(shí)間片上5 linux進(jìn)程調(diào)度策略進(jìn)程調(diào)度策略3) 優(yōu)先級(jí)調(diào)度策略基于動(dòng)態(tài)優(yōu)先級(jí)的調(diào)度策略 進(jìn)程優(yōu)先級(jí)取值范圍：0.139，動(dòng)態(tài)優(yōu)先級(jí)prio根據(jù)靜態(tài)優(yōu)先級(jí)static_prio變化，由effective_prio()函數(shù)取得，該函數(shù)根據(jù)進(jìn)程實(shí)際的睡眠平均時(shí)間分

13、級(jí)成-50+5獎(jiǎng)罰優(yōu)先級(jí)值范圍。 用戶賦予優(yōu)先級(jí)nice轉(zhuǎn)換為靜態(tài)優(yōu)先級(jí)：static_prio=120+nice動(dòng)態(tài)優(yōu)先級(jí)設(shè)置時(shí)機(jī)： 1）進(jìn)程創(chuàng)建時(shí) 2）喚醒休眠進(jìn)程時(shí)，會(huì)修正進(jìn)程的優(yōu)先級(jí) 3）在時(shí)鐘中斷中的schedule_tick()中 4）其他：idle進(jìn)程初始化、負(fù)載平衡、修改nice值、修改調(diào)度策略 effective_prio()函數(shù)：函數(shù)： 計(jì)算非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)，主要步驟如下： 算出當(dāng)前進(jìn)程平均睡眠時(shí)間。得到進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。static int effective_prio(task_t *p) if (rt_task(p) return p- prio; bonus =

14、current_bonus(p) max_bonus / 2; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計(jì)算出bonus. bonus = （進(jìn)程睡眠jiffers/hz )*10 - 5 effective_prio()函數(shù)：函數(shù)： 計(jì)算非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)，主要步驟如下： 算出當(dāng)前進(jìn)程平均睡眠時(shí)間。得到進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。static int effective_prio(task_t *p) if (rt_task(p) return p- prio; bonus = current_bonus(p) max_bonus / 2

15、; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計(jì)算出bonus. bonus = （進(jìn)程睡眠jiffers/hz )*10 - 56 linux進(jìn)程調(diào)度實(shí)現(xiàn)進(jìn)程調(diào)度實(shí)現(xiàn) 可執(zhí)行隊(duì)列基本數(shù)據(jù)結(jié)構(gòu)：runqueue 定義在kernel/sched.c中struct runqueue spinlock_t lock; /運(yùn)行隊(duì)列自旋鎖unsigned long ru_running; /任務(wù)數(shù)目 struct prio_array *active; /活動(dòng)優(yōu)先級(jí)隊(duì)列struct prio_array *expired; /超時(shí)優(yōu)先級(jí)隊(duì)列s

16、truct prio_array arrays2; /實(shí)際優(yōu)先級(jí)數(shù)組 linux進(jìn)程調(diào)度實(shí)現(xiàn)進(jìn)程調(diào)度實(shí)現(xiàn) 優(yōu)先級(jí)數(shù)組 struct prio_array int nr_active; /任務(wù)數(shù)目unsigned long bitmapbitmap_size;/優(yōu)先級(jí)位圖struct list_head queuemax_prio;/優(yōu)先級(jí)隊(duì)列 說明：每個(gè)運(yùn)行隊(duì)列有2個(gè)優(yōu)先級(jí)數(shù)組，一個(gè)活躍的，一個(gè)過期的。能夠 提供 o(1)級(jí)算法復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)。linux進(jìn)程調(diào)度實(shí)現(xiàn)進(jìn)程調(diào)度實(shí)現(xiàn) 優(yōu)先級(jí)數(shù)組的重置 通過維護(hù)2個(gè)優(yōu)先級(jí)數(shù)組,active,expired, active數(shù)組上的進(jìn)程還有剩余時(shí)間片，

17、expired數(shù)組上的進(jìn)程全部耗盡了時(shí)間片。當(dāng)一個(gè)進(jìn)程時(shí)間片到了會(huì)從active數(shù)組移到expired數(shù)組，而時(shí)間片事先計(jì)算好了，這里的重新計(jì)算時(shí)間片只需在兩個(gè)數(shù)組之間切換即可。調(diào)度的實(shí)現(xiàn)調(diào)度的實(shí)現(xiàn) 每個(gè)進(jìn)程的進(jìn)程描述符中與進(jìn)程調(diào)度相關(guān)的域如下： volatile long need_resched； 確定是否需要重新調(diào)度的標(biāo)志。 unsigned long policy； 確定調(diào)度策略 sched_fifo /先進(jìn)先出的實(shí)時(shí)調(diào)度 sched_rr /基于優(yōu)先級(jí)的循環(huán)輪轉(zhuǎn)實(shí)時(shí)調(diào)度 sched_normal /普通分時(shí)調(diào)度 rt_priority；實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)（099） nice：用戶：用戶

18、可控制的進(jìn)程優(yōu)先級(jí)因子。（-2019） prio : 進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí) static_prio: 進(jìn)程的靜態(tài)優(yōu)先級(jí) sleep_avg: 進(jìn)程的平均睡眠時(shí)間 static_prio = max_rt_prio + nice + 20 schedule()函數(shù)函數(shù) 功能：功能：選擇一個(gè)合適的進(jìn)程運(yùn)行。主要步驟 清理當(dāng)前運(yùn)行進(jìn)程 選擇下一個(gè)運(yùn)行的進(jìn)程 設(shè)置新進(jìn)程的運(yùn)行環(huán)境 執(zhí)行進(jìn)程上下文切換 后期整理 直接啟動(dòng)調(diào)度：直接啟動(dòng)調(diào)度： 發(fā)生在當(dāng)前進(jìn)程因等待資源而需要進(jìn)入被阻塞狀態(tài)時(shí)。 把當(dāng)前進(jìn)程放到適當(dāng)?shù)牡却?duì)列中 把當(dāng)前進(jìn)程的state設(shè)為task_interruptibel或者task_uninterruptibel; 調(diào)用schedule(), 準(zhǔn)備讓新的進(jìn)程使用cpu； 檢查當(dāng)前進(jìn)程所需的資源是否可用