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

Linux進(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)程與線程,Linux進(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)骨的事情, 更何況在線程概念的早期, 受歷史原因(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),Linux進(jìn)程描述符也稱 進(jìn)程控制塊PCB： shruct task_struct unsigned long state; /進(jìn)程的狀態(tài)，在2.6.23已經(jīng)有9個(gè)狀態(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)程描述符,在內(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)核中，進(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)相關(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ì)把改動(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)相關(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)前允許的最大進(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，或者說是idle.,Linux進(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)換,scheduler and dispatcher,線程的實(shí)現(xiàn) 在Linux系統(tǒng)中，線程被當(dāng)作與其他進(jìn)程共享某些資源的進(jìn)程. 線程的創(chuàng)建：與普通進(jìn)程相似，需要指明共享資源。 如：clone (CLONE_VM | CLONE_FS | CLONE_FILES|CLONE_SIGHAND,0); 對(duì)比：clone (SIGCHLD, 0) /普通的fork() clone (CLONE_VFORK | CLONE_VM | SIGCHLD, 0) 內(nèi)核線程：內(nèi)核進(jìn)程沒有獨(dú)立的地址空間，只在內(nèi)核空間運(yùn)行。通常是一些后臺(tái)執(zhí)行的任務(wù)。 通過clone()的參數(shù)，新創(chuàng)建的進(jìn)程，也稱為LWP(Lightweight process)與父進(jìn)程共享內(nèi)存空間，文件句柄，信號(hào)處理等，從而達(dá)到創(chuàng)建線程相同的目的。,5 Linux進(jìn)程調(diào)度策略,1) 搶占式調(diào)度策略 當(dāng)一個(gè)進(jìn)程進(jìn)入TASK_RUNNING狀態(tài)，內(nèi)核檢查其優(yōu)先級(jí)是否高于當(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)度策略,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ù)根據(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)度策略,3) 優(yōu)先級(jí)調(diào)度策略 基于動(dòng)態(tài)優(yōu)先級(jí)的調(diào)度策略 進(jìn)程優(yōu)先級(jí)取值范圍：0139，動(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í)間分級(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ù)： 計(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; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計(jì)算出bonus. bonus = （進(jìn)程睡眠jiffers/HZ )*10 - 5,effective_prio()函數(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; prio = p-static_prio bonus; return prio; 說明：系統(tǒng)通過一系列宏計(jì)算出bonus. bonus = （進(jìn)程睡眠jiffers/HZ )*10 - 5,6 Linux進(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ì)列 struct prio_array arrays2; /實(shí)際優(yōu)先級(jí)數(shù)組 ,Linux進(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),優(yōu)先級(jí)數(shù)組的重置 通過維護(hù)2個(gè)優(yōu)先級(jí)數(shù)組,active,expired, active數(shù)組上的進(jìn)程還有剩余時(shí)間片，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),每個(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：用戶可控制的進(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ù) 功能：選擇一個(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)度： 發(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)程所需的資源是否可用，如果是，把當(dāng)前進(jìn)程從等待隊(duì)列里刪除，否則回到第2