Linux進程管理與調(diào)度.ppt

Linux進程管理與調(diào)度,關(guān)于進程與線程 Linux進程實現(xiàn) Linux進程調(diào)度策略 Linux進程調(diào)度實現(xiàn),1 Linux進程與線程,Linux進程 Linux線程,進程作為資源分配的基本單位而存在，線程作為調(diào)度的基本單位而存在 我們都知道linux是不斷發(fā)展的.在早期版本中, linux的基本調(diào)度單元是Task, 只到現(xiàn)在, 依然是它. 在早期版本中, 一個Task對應(yīng)著一個進程, 完全沒有線程這個概念. 隨著時間的發(fā)展, 線程的概念出現(xiàn)的, 但是linux并沒有馬上接受這一概念, 要知道, 線程是現(xiàn)代操作系統(tǒng)的特征, 向一個現(xiàn)有的操作系統(tǒng)內(nèi)核引入線程是一件傷筋動骨的事情, 更何況在線程概念的早期, 受歷史原因(UNIX)和硬件的限制(多核尚不是主流), 線程的地位尚不確定. 所以, linux并沒有在內(nèi)核中引入線程的概念. 但是, linux提供了一個新的系統(tǒng)調(diào)用clone, 通過該系統(tǒng)調(diào)用, 內(nèi)核中的多個進程可以共享一些信息, 比如進程空間等. 注意, 此時linux內(nèi)核的基礎(chǔ)調(diào)度單元依然是Task, 而且在內(nèi)核看來, 一個進程依然對應(yīng)著一個Task.,2 Linux進程實現(xiàn),Linux進程描述符也稱 進程控制塊PCB： shruct task_struct unsigned long state; /進程的狀態(tài)，在2.6.23已經(jīng)有9個狀態(tài) unsigned long policy; /描述進程調(diào)度策略.判斷是實時進程還是非實時進程 struct task_struct *parent; /組織進程的層次關(guān)系，指向父進程 struct list_head tasks; /通過list_head組織成雙向鏈表 pid_t pid; /每個進程唯一的標(biāo)號 ; ,Linux進程描述符,在內(nèi)核棧底創(chuàng)建新的結(jié)構(gòu)struct thread_info Struct thread_info struct task_struct *task; struct exec_domain *exec_domain; unsigned long flags; unsigned long status; _u32 cpu; ; 在linux內(nèi)核中，進程被分為兩部分，一部分是thread_info,保存在內(nèi)核棧中，為了保持很小，因此只保存了必須的幾個域，它有一個變量task，指向task_struct,這個結(jié)構(gòu)保存了進程相關(guān)的所有信息。而對應(yīng)的task_struct也保存了一個變量stack指向的就是一個thread_union的聯(lián)合體,Linux進程實現(xiàn)相關(guān)的系統(tǒng)調(diào)用,fork(): 創(chuàng)建普通進程,copy on write（要復(fù)制父進程的頁表） 創(chuàng)建后子進程和父進程指向同一內(nèi)存區(qū)域，僅當(dāng)子進程有write發(fā)生時候，才會把改動的區(qū)域copy到子進程新的地址空間 vfork()： 共享創(chuàng)建，完全無拷貝。（子進程作為父進程的一個單獨線程在其地址空間運行，父進程阻塞） clone(): 介于fork()和vfork()之間，可以指定共享什么，拷貝什么。 說明：vfork()與clone()可用于創(chuàng)建新的內(nèi)核線程。,Linux進程實現(xiàn)相關(guān)的函數(shù),do_fork()：/ 被clone(),fork(),vfork()調(diào)用，執(zhí)行步驟如下： 檢查父進程標(biāo)志是否為空。 調(diào)用alloc_task_struct()為新進程分配一段內(nèi)存空間，并將父進程描述符的內(nèi)容拷貝到子進程。 檢查進程是否得到所需資源及系統(tǒng)當(dāng)前允許的最大進程數(shù)。 如進程需要引用內(nèi)核模塊，則增加模塊引用計數(shù)。 更新從父進程拷貝來的信息。 系統(tǒng)調(diào)用get_pid()，將獲得的pid賦給新建的子進程。 更新不能由父進程繼承的域。,為新進程的執(zhí)行設(shè)置跟蹤進程的相關(guān)內(nèi)核數(shù)據(jù)結(jié)構(gòu)，新進程入鏈表。 置新進程狀態(tài)為task_running, 。 向父進程返回pid。 說明： 創(chuàng)建進程的系統(tǒng)調(diào)用返回時（ret_from_sys_call），將根據(jù)存放系統(tǒng)調(diào)用返回值寄存器EAX的內(nèi)容(pid)是0還是一個小正整數(shù)來決定是運行父進程還是子進程。 在linux中第一個進程是內(nèi)核進程，pid為0，它是所有的進程的父進程。這個進程也叫swapper，或者說是idle.,Linux進程狀態(tài),TASK_RUNNING：進程在運行 ( 是系統(tǒng)的當(dāng)前進程 ) 或者準(zhǔn)備運行（等待被安排到系統(tǒng)的一個CPU上）。 TASK_INTERRUPTIBLE：進程處于某個等待隊列中，它能夠被信號（signal）喚醒。等待資源的請求滿足時，也被喚醒。 TASK_UNINTERRUPTIBLE: 進程處于某個等待隊列中，不能被信號或中斷喚醒，只有等待的資源被滿足時才被喚醒。 TASK_ZOMBIE: 進程已經(jīng)停止，但還沒有釋放進程控制塊。 TASK_STOPPED：可能是被特定的信號終止，也可能是受其它進程的跟蹤調(diào)用而暫時將CPU交給跟蹤它的進程。,Linux狀態(tài)轉(zhuǎn)換,scheduler and dispatcher,線程的實現(xiàn) 在Linux系統(tǒng)中，線程被當(dāng)作與其他進程共享某些資源的進程. 線程的創(chuàng)建：與普通進程相似，需要指明共享資源。 如：clone (CLONE_VM | CLONE_FS | CLONE_FILES|CLONE_SIGHAND,0); 對比：clone (SIGCHLD, 0) /普通的fork() clone (CLONE_VFORK | CLONE_VM | SIGCHLD, 0) 內(nèi)核線程：內(nèi)核進程沒有獨立的地址空間，只在內(nèi)核空間運行。通常是一些后臺執(zhí)行的任務(wù)。 通過clone()的參數(shù)，新創(chuàng)建的進程，也稱為LWP(Lightweight process)與父進程共享內(nèi)存空間，文件句柄，信號處理等，從而達到創(chuàng)建線程相同的目的。,5 Linux進程調(diào)度策略,1) 搶占式調(diào)度策略 當(dāng)一個進程進入TASK_RUNNING狀態(tài)，內(nèi)核檢查其優(yōu)先級是否高于當(dāng)前進程。 當(dāng)一個進程的時間片為0時，也會被搶占。 搶占： 用戶搶占：need_resched標(biāo)志設(shè)置即發(fā)生，包括從系統(tǒng)調(diào)用返回用戶空間、 從中斷處理程序返回用戶空間的情況。 內(nèi)核搶占：為每個進程的thread_info引入了preempt_count計數(shù)器，該計數(shù) 器初值為0，加鎖時，其值加1，其數(shù)值為0時，內(nèi)核可執(zhí)行搶 占。中斷返回內(nèi)核空間時產(chǎn)生。,Linux進程調(diào)度策略,2) 時間片調(diào)度策略 內(nèi)核根據(jù)時間片是否耗盡為標(biāo)準(zhǔn)，將就緒進程分為active, expired兩類。 新創(chuàng)建的子進程和父進程均分父進程的剩余時間片 時間片的計算以靜態(tài)優(yōu)先級為基礎(chǔ)，即由task_timeslice()函數(shù)根據(jù)靜態(tài)優(yōu)先級按照比例縮放。 時間片的遞減和重置在時鐘中斷中進行，sheduler_tick() 時間片計算： MIN_TIMESLICE+(MAX_TIMESLICE MIN_TIMESLICE)*(MAX_PRIO-1-(p)-static_prio)/(MAX_USER_PRIO-1) 即：將100139的優(yōu)先級映射到200ms10ms的時間片上,5 Linux進程調(diào)度策略,3) 優(yōu)先級調(diào)度策略 基于動態(tài)優(yōu)先級的調(diào)度策略 進程優(yōu)先級取值范圍：0139，動態(tài)優(yōu)先級prio根據(jù)靜態(tài)優(yōu)先級static_prio變化，由effective_prio()函數(shù)取得，該函數(shù)根據(jù)進程實際的睡眠平均時間分級成-50+5獎罰優(yōu)先級值范圍。 用戶賦予優(yōu)先級nice轉(zhuǎn)換為靜態(tài)優(yōu)先級：static_prio=120+nice 動態(tài)優(yōu)先級設(shè)置時機： 1）進程創(chuàng)建時 2）喚醒休眠進程時，會修正進程的優(yōu)先級 3）在時鐘中斷中的schedule_tick()中 4）其他：IDLE進程初始化、負載平衡、修改nice值、修改調(diào)度策略,effective_prio()函數(shù)： 計算非實時進程的優(yōu)先級，主要步驟如下： 算出當(dāng)前進程平均睡眠時間。 得到進程的動態(tài)優(yōu)先級。 static int effective_prio(task_t *p) if (rt_task(p) return p- prio; bonus = CURRENT_BONUS(p) MAX_BONUS / 2; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計算出bonus. bonus = （進程睡眠jiffers/HZ )*10 - 5,effective_prio()函數(shù)： 計算非實時進程的優(yōu)先級，主要步驟如下： 算出當(dāng)前進程平均睡眠時間。 得到進程的動態(tài)優(yōu)先級。 static int effective_prio(task_t *p) if (rt_task(p) return p- prio; bonus = CURRENT_BONUS(p) MAX_BONUS / 2; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計算出bonus. bonus = （進程睡眠jiffers/HZ )*10 - 5,6 Linux進程調(diào)度實現(xiàn),可執(zhí)行隊列 基本數(shù)據(jù)結(jié)構(gòu)：runqueue 定義在kernel/sched.c中 struct runqueue spinlock_t lock; /運行隊列自旋鎖 unsigned long ru_running; /任務(wù)數(shù)目 struct prio_array *active; /活動優(yōu)先級隊列 struct prio_array *expired; /超時優(yōu)先級隊列 struct prio_array arrays2; /實際優(yōu)先級數(shù)組 ,Linux進程調(diào)度實現(xiàn),優(yōu)先級數(shù)組 struct prio_array int nr_active; /任務(wù)數(shù)目 unsigned long bitmapBITMAP_SIZE;/優(yōu)先級位圖 struct list_head queueMAX_PRIO;/優(yōu)先級隊列 說明：每個運行隊列有2個優(yōu)先級數(shù)組，一個活躍的，一個過期的。能夠 提供 O(1)級算法復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)。,Linux進程調(diào)度實現(xiàn),優(yōu)先級數(shù)組的重置 通過維護2個優(yōu)先級數(shù)組,active,expired, active數(shù)組上的進程還有剩余時間片，expired數(shù)組上的進程全部耗盡了時間片。 當(dāng)一個進程時間片到了會從active數(shù)組移到expired數(shù)組，而時間片事先計算好了，這里的重新計算時間片只需在兩個數(shù)組之間切換即可。,調(diào)度的實現(xiàn),每個進程的進程描述符中與進程調(diào)度相關(guān)的域如下： volatile long need_resched； 確定是否需要重新調(diào)度的標(biāo)志。 unsigned long policy； 確定調(diào)度策略 SCHED_FIFO /先進先出的實時調(diào)度 SCHED_RR /基于優(yōu)先級的循環(huán)輪轉(zhuǎn)實時調(diào)度 SCHED_NORMAL /普通分時調(diào)度,rt_priority；實時進程的優(yōu)先級（099） nice：用戶可控制的進程優(yōu)先級因子。（-2019） prio : 進程的動態(tài)優(yōu)先級 static_prio: 進程的靜態(tài)優(yōu)先級 sleep_avg: 進程的平均睡眠時間 static_prio = MAX_RT_PRIO + nice + 20,schedule()函數(shù) 功能：選擇一個合適的進程運行。 主要步驟 清理當(dāng)前運行進程 選擇下一個運行的進程 設(shè)置新進程的運行環(huán)境 執(zhí)行進程上下文切換 后期整理,直接啟動調(diào)度： 發(fā)生在當(dāng)前進程因等待資源而需要進入被阻塞狀態(tài)時。 把當(dāng)前進程放到適當(dāng)?shù)牡却犃兄?把當(dāng)前進程的state設(shè)為TASK_INTERRUPTIBEL或者TASK_UNINTERRUPTIBEL; 調(diào)用schedule(), 準(zhǔn)備讓新的進程使用CPU； 檢查當(dāng)前進程所需的資源是否可用，如果是，把當(dāng)前進程從等待隊列里刪除，否則回到第2