現(xiàn)代操作系統(tǒng)unix.ppt

1、Chapter 7 Case study: Linux,2,Contents,Linux內(nèi)核結(jié)構(gòu) Linux的進程管理 Linux的進程調(diào)度 Linux的內(nèi)存管理,3,7.1 Linux內(nèi)核結(jié)構(gòu),4,7.2 Linux的進程管理,一般來說，Linux中的進程都具備以下四要素： 有一段程序供其執(zhí)行。 有起碼的“私有財產(chǎn)”，這就是系統(tǒng)專用的系統(tǒng)堆?？臻g。 有“戶口”，這就是在內(nèi)核中的一個task_struct數(shù)據(jù)結(jié)構(gòu)（在操作系統(tǒng)教科書中常稱為PCB）。 有獨立的存儲空間，意味著擁有專有的用戶空間。,注：缺了其中任何一條就不成其為“進程”。如果只具備了前面3條而缺第4條，那就稱為“線程”。特別地，如

2、果完全沒有用戶空間，就稱為“內(nèi)核線程”，而如果共享用戶空間則就稱為“用戶線程”。,5,task與process,Linux系統(tǒng)中的“進程” (process) 和“任務(wù)” (task)是同一個意思，在內(nèi)核代碼中也?；煊眠@兩個名詞。,6,7.2.1 進程描述符及任務(wù)結(jié)構(gòu),在內(nèi)核中，進程描述符是一個名為task_struct的結(jié)構(gòu)體，用于保存進程的屬性和其他信息，它在include/linux/sched.h中定義。 內(nèi)核用雙向循環(huán)鏈表task_list存放所有進程描述符；同時借助全局變量current保存當(dāng)前運行進程的task_struct。,7,進程描述符,進程描述符必須保存的信息類型有： 進

3、程的屬性 進程間的關(guān)系 進程的內(nèi)存空間 文件管理 信號量管理 進程的可信度 資源限制 與調(diào)度相關(guān)的域,8,7.2.2 進程狀態(tài),task_struct結(jié)構(gòu)中的state域描述了進程的當(dāng)前狀態(tài)。系統(tǒng)中的每個進程都必然處于幾種進程狀態(tài)之一。其具體定義見sched.h。,#define TASK_RUNNING0 #define TASK_INTERRUPTIBLE1 #define TASK_UNINTERRUPTIBLE2 #define TASK_STOPPED4 #define TASK_TRACED8 #define EXIT_ZOMBIE16 #define EXIT_DEAD32,9,

4、進程狀態(tài),TASK_RUNNING 可執(zhí)行狀態(tài)，表示這個進程可以被調(diào)度執(zhí)行而成為當(dāng)前進程。 當(dāng)進程處于這樣的可執(zhí)行狀態(tài)時，內(nèi)核就將該進程的task_struct結(jié)構(gòu)通過其隊列頭run_list掛入一個“運行隊列”。 TASK_INTERRUPTIBLE 進程睡眠，可因“信號到來”而被喚醒 TASK_UNINTERRUPTIBLE 進程深度睡眠，不受信號干擾 TASK_STOPPED 掛起狀態(tài)，主要用于調(diào)試目的 TASK_ZOMBIE 進程已經(jīng)結(jié)束，但資源未釋放，進程結(jié)構(gòu)還在（進程已經(jīng)“去世”但“戶口”尚未注銷）,10,進程狀態(tài)轉(zhuǎn)換,11,7.2.3 進程創(chuàng)建,Linux將進程的創(chuàng)建與目標(biāo)程序的

5、執(zhí)行分成兩步： 第一步：從已經(jīng)存在的“父進程”復(fù)制出一個“子進程”。復(fù)制出來的子進程有自己的task_struct和系統(tǒng)空間堆棧，但與父進程共享其它所有的資源。Linux為此提供了兩個系統(tǒng)調(diào)用：fork( )和clone( )。 第二步：讀取可執(zhí)行文件并將其載入地址空間開始運行。 Linux為此提供了一個函數(shù)族：exec( )。,12,fork( )與clone( )的區(qū)別,fork( )是全部復(fù)制，父進程所有的資源全都通過數(shù)據(jù)結(jié)構(gòu)的復(fù)制“遺傳”給子進程。 clone( )則可以將資源有選擇地復(fù)制給子進程，而沒有復(fù)制的數(shù)據(jù)結(jié)構(gòu)則通過指針的復(fù)制讓子進程共享。在極端的情況下，一個進程可以clone

6、( )出一個線程。 fork( )是無參數(shù)的， clone( )是帶有參數(shù)的。,13,寫時拷貝 (copy_on_write),傳統(tǒng)的fork( )系統(tǒng)調(diào)用直接把所有的資源復(fù)制給新創(chuàng)建的進程。缺點：效率低下 Linux的fork( )使用寫時拷貝來實現(xiàn)。 寫時拷貝是一種可以推遲甚至免除拷貝數(shù)據(jù)的技術(shù)。新創(chuàng)建進程時，內(nèi)核并不復(fù)制整個進程地址空間，而是讓父進程和子進程共享同一個拷貝；只有在需要寫入的時候，數(shù)據(jù)才會被復(fù)制，從而使各個進程擁有各自的拷貝。,14,寫時拷貝,寫時拷貝技術(shù)使地址空間上的頁的拷貝被推遲到實際發(fā)生寫入的時候，在頁根本不會被寫入的情況下（如fork( )后立即調(diào)用exec( )）

7、，它們就無需復(fù)制了。 一般情況下，進程創(chuàng)建后都會馬上運行一個可執(zhí)行的文件，這種優(yōu)化可以避免拷貝大量根本就不會被使用的數(shù)據(jù)。,15,7.3 Linux的進程調(diào)度,調(diào)度程序是內(nèi)核的組成部分，它負責(zé)選擇下一個要運行的進程。 調(diào)度程序的基本工作：在一組處于可運行狀態(tài)的進程中選擇一個來執(zhí)行。 Linux提供搶占式的多任務(wù)模式。,16,7.3.1 調(diào)度策略 (policy),調(diào)度策略決定調(diào)度程序在何時讓什么進程運行。,17,(1) I/O消耗型和處理器消耗型進程,I/O消耗型進程：進程的大部分時間用來提交I/O請求或是等待I/O請求。這樣的進程經(jīng)常處于可運行狀態(tài)，但通常每次運行時間很短。 處理器消耗型進程

8、：它把時間大多用在執(zhí)行代碼上。 對于處理器消耗型進程，調(diào)度策略是盡量降低它們的運行頻率。,18,調(diào)度策略,調(diào)度策略通常要在兩個矛盾中尋找平衡： 進程響應(yīng)時間短 系統(tǒng)吞吐量高 Linux為了保證交互式應(yīng)用，更傾向于優(yōu)先調(diào)度I/O消耗型進程。,19,調(diào)度策略定義,在include/linux/sched.h中有如下定義：,#define SCHED_NORMAL0 / 默認(rèn)類型，普通的用戶進程，動態(tài)優(yōu)先調(diào)度策略 #define SCHED_FIFO1 / 實時進程，先進先出調(diào)度規(guī)則 #define SCHED_RR2 / 實時進程，循環(huán)round-robin調(diào)度規(guī)則,task_struct中的成員

9、policy是進程的調(diào)度策略，它的值為上述三種策略之一。,20,(2) 進程優(yōu)先級,基于優(yōu)先級的調(diào)度：調(diào)度程序總是選擇時間片未用盡而且優(yōu)先級最高的進程運行。 Linux實現(xiàn)了基于動態(tài)優(yōu)先級的調(diào)度方法。 Linux內(nèi)核提供了兩組獨立的優(yōu)先級： nice值：范圍從-2019，默認(rèn)值是0。值越大，優(yōu)先級越低。 實時優(yōu)先級：任何實時進程的優(yōu)先級都高于普通進程。,21,(3) 時間片,時間片大小的確定 太短 問題？ 太長 問題？ Linux的調(diào)度程序提供較長的默認(rèn)時間片給交互式程序。 Linux還能根據(jù)進程的優(yōu)先級動態(tài)調(diào)整分配給它的時間片，從而保證優(yōu)先級高的進程，執(zhí)行的頻率高，執(zhí)行時間長。,22,時間片

10、,當(dāng)一個進程的時間片耗盡時，就認(rèn)為進程到期了。 沒有時間片的進程不會再投入運行，除非等到其它所有的進程都耗盡了它們的時間片，這時，會重新計算所有進程的時間片。,23,(4) 進程搶占,兩種情況下會發(fā)生進程搶占： 有一個進程進入TASK_RUNNING狀態(tài)，而它的優(yōu)先級高于當(dāng)前正在運行的進程 當(dāng)正在運行的進程的時間片變?yōu)?時,24,7.3.2 Linux調(diào)度算法,Linux的調(diào)度程序在kernel/sched.c中定義。,25,(1) 可執(zhí)行隊列,可執(zhí)行隊列是調(diào)度程序中最基本的數(shù)據(jù)結(jié)構(gòu)，它定義于kernel/sched.c中，由結(jié)構(gòu)runqueue表示。 可執(zhí)行隊列是給定處理器上的可執(zhí)行進程的鏈

11、表，每個處理器一個。,26,可執(zhí)行隊列runqueue,struct runqueue spinlock_t lock; unsigned long nr_running; unsigned long long nr_switches; unsigned long nr_uninterruptible; unsigned long expired_timestamp; unsigned long long timestamp_last_tick; task_t *curr, *idle; struct mm_struct *prev_mm; prio_array_t *active, *exp

12、ired, arrays2; atomic_t nr_iowait; task_t *migration_thread; struct list_head migration_queue; ;,27,(2) 優(yōu)先級數(shù)組,每個運行隊列有兩個優(yōu)先級數(shù)組，一個活躍的，一個過期的。 優(yōu)先級數(shù)組在kernel/sched.c中定義，是prio_array類型的結(jié)構(gòu)體。 優(yōu)先級數(shù)組是一種能夠提供O(1)算法復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)。,28,prio_array結(jié)構(gòu)體,MAX_PRIO定義了系統(tǒng)擁有的優(yōu)先級個數(shù)，默認(rèn)值是140，在sched.h中定義如下：,struct prio_array unsigned in

13、t nr_active; /可執(zhí)行進程數(shù)目 unsigned long bitmapBITMAP_SIZE; struct list_head queueMAX_PRIO; ;,#define MAX_USER_RT_PRIO100 #define MAX_RT_PRIOMAX_USER_RT_PRIO #define MAX_PRIO(MAX_RT_PRIO + 40),29,prio_array結(jié)構(gòu)體分析,BITMAP_SIZE是優(yōu)先級位圖數(shù)組的大小，定義如下：,#define BITMAP_SIZE (MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(lon

14、g),由以上定義，計算出BITMAP_SIZE=5。 數(shù)組bitmapBITMAP_SIZE為unsigned long型，長32位，如果每位代表一個優(yōu)先級的話，共有32*5160位，足夠表示前面提到的140個優(yōu)先級。,30,prio_array結(jié)構(gòu)體分析,每個優(yōu)先級數(shù)組都包含一個這樣的位圖成員，至少為每個優(yōu)先級準(zhǔn)備一位。初始時，所有的位都置0；當(dāng)擁有某個優(yōu)先級的進程準(zhǔn)備執(zhí)行時，位圖中的相應(yīng)位就被置1。 這樣，查找系統(tǒng)中最高的優(yōu)先級就變成了查找位圖中被設(shè)置的第一個位。因為優(yōu)先級的個數(shù)是定值(140個)，所以查找時間恒定，并不受系統(tǒng)到底有多少可執(zhí)行進程的影響。,31,prio_array結(jié)構(gòu)體分

15、析,每個prio_array包含一個叫作queue的數(shù)組，該數(shù)組的每個元素都是一個struct list_head類型的隊列。每個隊列與一個給定的優(yōu)先級相對應(yīng)。 prio_array中還包含了一個計數(shù)器nr_active，記錄該優(yōu)先級數(shù)組內(nèi)可執(zhí)行進程的數(shù)目。,32,(3) 重新計算時間片,重新計算時間片的老方法：,for (系統(tǒng)中的每個任務(wù)) 重新計算優(yōu)先級 重新計算時間片 ,存在的弊端： 耗費的時間長 必須靠鎖來保護任務(wù)隊列，加劇對鎖的爭用 重新計算時間片的時機不確定 實現(xiàn)粗糙,33,新的Linux調(diào)度程序如何計算時間片,Linux調(diào)度程序為每個處理器維護兩個優(yōu)先級數(shù)組： 活動數(shù)組：其中的可

16、執(zhí)行隊列上的進程都還有時間片剩余 過期數(shù)組：其中的可執(zhí)行隊列上的進程都耗盡了時間片 當(dāng)一個進程的時間片耗盡時，它會被移至過期數(shù)組，但在此之前，時間片已給它重新計算好了。,34,活動數(shù)組和過期數(shù)組的切換,現(xiàn)在，重新計算時間片只需要在活動數(shù)組和過期數(shù)組之間來回切換就行了。這個動作由schedule( )完成，部分代碼如下：,prio_array_t *array; array = rq-active; if (!array-nr_active) rq-active = rq-expired; rq-expired = array; array = rq-active; ,這種交換是O(1)級調(diào)度程

17、序的核心。,35,(4) 調(diào)度程序schedule( ),schedule( )函數(shù)完成的工作：選定下一個投入運行的進程，并切換到這個進程。 在schedule( )函數(shù)中首先要判斷誰是優(yōu)先級最高的進程，代碼見下頁。,36,判斷誰是優(yōu)先級最高的進程,struct task_struct *prev, *next; struct runqueue *rq; struct prio_array *array; struct list_head *queue; int idx; prev = current; array = rq-active; idx = sched_find_first_bit

18、(array-bitmap); queue = array-queue + idx; next = list_entry(queue-next, task_t, run_list);,37,(5) 計算優(yōu)先級和時間片,進程有一個初始優(yōu)先級(也稱靜態(tài)優(yōu)先級)，叫做nice值，范圍從-2019，默認(rèn)為0，它由用戶指定。 nice值越小，優(yōu)先級越高。 nice值通過轉(zhuǎn)換后存放在task_struct結(jié)構(gòu)的static_prio域中，轉(zhuǎn)換方法見下頁：,38,如何將nice轉(zhuǎn)換成static_prio,經(jīng)計算得：static_prio的范圍為100139，值越小，優(yōu)先級越高。,#define MAX_R

19、T_PRIO100 #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) struct task_struct *p; p-static_prio = NICE_TO_PRIO(nice);,39,動態(tài)優(yōu)先級prio,調(diào)度程序要用到的動態(tài)優(yōu)先級存放在task_struct結(jié)構(gòu)的prio域中。 動態(tài)優(yōu)先級prio通過一個關(guān)于靜態(tài)優(yōu)先級和進程交互性的函數(shù)關(guān)系計算而來。,40,計算進程的動態(tài)優(yōu)先級,effective_prio( )函數(shù)可以返回一個進程的動態(tài)優(yōu)先級。 該函數(shù)以nice值為基數(shù)，再加上-5到+5之間的進程交互性的獎勵或罰分。 該函

20、數(shù)在kernel/sched.c中實現(xiàn)，代碼見下頁。,41,effective_prio( )函數(shù),static int effective_prio(task_t *p) int bonus, prio; if (rt_task(p) return p-prio; bonus = CURRENT_BONUS(p) - MAX_BONUS / 2; prio = p-static_prio - bonus; if (prio MAX_PRIO-1) prio = MAX_PRIO-1; return prio; ,42,bonus的計算中需要用到的宏和函數(shù),# define HZ1000 #d

21、efine NS_TO_JIFFIES(TIME)(TIME) / (1000000000 / HZ) #define DEF_TIMESLICE(100 * HZ / 1000) #define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS) #define CURRENT_BONUS(p) (NS_TO_JIFFIES(p)-sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG),43,bonus的計算,通過計算得：MAX_BONUS=10； MAX_SLEEP_AVG100*101000。 假設(shè)進程的休眠時間為x，即x= (p)

22、- sleep_avg，則CURRENT_BONUS(p)= x/ (1000000000 / 1000)10/1000= x/108。 因此bonus = CURRENT_BONUS(p) - MAX_BONUS / 2x/108 -5。,44,結(jié)論,通過以上分析可得出：休眠時間越長 bonus越大 prio越小進程的動態(tài)優(yōu)先級越高。因此進程的休眠時間長，它的優(yōu)先級就能得到提高。,45,調(diào)度程序如何了解進程的交互性強不強？,以進程休眠的時間長短作為標(biāo)準(zhǔn)。 如果一個進程大部分時間都在休眠I/O消耗型，交互性強 如果一個進程執(zhí)行時間比休眠時間長處理器消耗型 交互性強的進程，在運行過程中可得到獎勵

23、，從而提高它的優(yōu)先級。,46,sleep_avg域,Linux記錄了一個進程用于休眠和用于執(zhí)行的時間。該值存放在task_struct結(jié)構(gòu)的sleep_avg域中，其范圍從0MAX_SLEEP_AVG，默認(rèn)值為10毫秒。 當(dāng)一個進程從休眠狀態(tài)恢復(fù)到執(zhí)行狀態(tài)時， sleep_avg會根據(jù)它休眠時間的長短而增長，直至達到MAX_SLEEP_AVG為止；相反，進程每運行一個時鐘節(jié)拍， sleep_avg就做相應(yīng)的遞減，到0為止。,47,重新計算時間片,重新計算時間片時，只需要以靜態(tài)優(yōu)先級為基礎(chǔ)。 新創(chuàng)建的子進程與父進程平分父進程剩余的時間片。 當(dāng)一個任務(wù)的時間片用完后，task_timeslice( )函數(shù)為給定任務(wù)返回一個新的時間片。時間片的計算只需要把優(yōu)先級按比例縮放，使其符合時間片的數(shù)值范圍就可以了。,48,task_timeslice( )函數(shù),#define SCALE_PRIO(x, pr