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

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

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

3、程的屬性 進(jìn)程間的關(guān)系 進(jìn)程的內(nèi)存空間 文件管理 信號(hào)量管理 進(jìn)程的可信度 資源限制 與調(diào)度相關(guān)的域,8,7.2.2 進(jìn)程狀態(tài),task_struct結(jié)構(gòu)中的state域描述了進(jìn)程的當(dāng)前狀態(tài)。系統(tǒng)中的每個(gè)進(jìn)程都必然處于幾種進(jìn)程狀態(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、進(jìn)程狀態(tài),TASK_RUNNING 可執(zhí)行狀態(tài)，表示這個(gè)進(jìn)程可以被調(diào)度執(zhí)行而成為當(dāng)前進(jìn)程。 當(dāng)進(jìn)程處于這樣的可執(zhí)行狀態(tài)時(shí)，內(nèi)核就將該進(jìn)程的task_struct結(jié)構(gòu)通過其隊(duì)列頭run_list掛入一個(gè)“運(yùn)行隊(duì)列”。 TASK_INTERRUPTIBLE 進(jìn)程睡眠，可因“信號(hào)到來”而被喚醒 TASK_UNINTERRUPTIBLE 進(jìn)程深度睡眠，不受信號(hào)干擾 TASK_STOPPED 掛起狀態(tài)，主要用于調(diào)試目的 TASK_ZOMBIE 進(jìn)程已經(jīng)結(jié)束，但資源未釋放，進(jìn)程結(jié)構(gòu)還在（進(jìn)程已經(jīng)“去世”但“戶口”尚未注銷）,10,進(jìn)程狀態(tài)轉(zhuǎn)換,11,7.2.3 進(jìn)程創(chuàng)建,Linux將進(jìn)程的創(chuàng)建與目標(biāo)程序的

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

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

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

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

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

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

11、表，每個(gè)處理器一個(gè)。,26,可執(zhí)行隊(duì)列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)先級(jí)數(shù)組,每個(gè)運(yùn)行隊(duì)列有兩個(gè)優(yōu)先級(jí)數(shù)組，一個(gè)活躍的，一個(gè)過期的。 優(yōu)先級(jí)數(shù)組在kernel/sched.c中定義，是prio_array類型的結(jié)構(gòu)體。 優(yōu)先級(jí)數(shù)組是一種能夠提供O(1)算法復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)。,28,prio_array結(jié)構(gòu)體,MAX_PRIO定義了系統(tǒng)擁有的優(yōu)先級(jí)個(gè)數(shù)，默認(rèn)值是140，在sched.h中定義如下：,struct prio_array unsigned in

13、t nr_active; /可執(zhí)行進(jìn)程數(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)先級(jí)位圖數(shù)組的大小，定義如下：,#define BITMAP_SIZE (MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(lon

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

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

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

17、序的核心。,35,(4) 調(diào)度程序schedule( ),schedule( )函數(shù)完成的工作：選定下一個(gè)投入運(yùn)行的進(jìn)程，并切換到這個(gè)進(jìn)程。 在schedule( )函數(shù)中首先要判斷誰是優(yōu)先級(jí)最高的進(jìn)程，代碼見下頁。,36,判斷誰是優(yōu)先級(jí)最高的進(jìn)程,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) 計(jì)算優(yōu)先級(jí)和時(shí)間片,進(jìn)程有一個(gè)初始優(yōu)先級(jí)(也稱靜態(tài)優(yōu)先級(jí))，叫做nice值，范圍從-2019，默認(rèn)為0，它由用戶指定。 nice值越小，優(yōu)先級(jí)越高。 nice值通過轉(zhuǎn)換后存放在task_struct結(jié)構(gòu)的static_prio域中，轉(zhuǎn)換方法見下頁：,38,如何將nice轉(zhuǎn)換成static_prio,經(jīng)計(jì)算得：static_prio的范圍為100139，值越小，優(yōu)先級(jí)越高。,#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,動(dòng)態(tài)優(yōu)先級(jí)prio,調(diào)度程序要用到的動(dòng)態(tài)優(yōu)先級(jí)存放在task_struct結(jié)構(gòu)的prio域中。 動(dòng)態(tài)優(yōu)先級(jí)prio通過一個(gè)關(guān)于靜態(tài)優(yōu)先級(jí)和進(jìn)程交互性的函數(shù)關(guān)系計(jì)算而來。,40,計(jì)算進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí),effective_prio( )函數(shù)可以返回一個(gè)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。 該函數(shù)以nice值為基數(shù)，再加上-5到+5之間的進(jìn)程交互性的獎(jiǎng)勵(lì)或罰分。 該函

20、數(shù)在kernel/sched.c中實(shí)現(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的計(jì)算中需要用到的宏和函數(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的計(jì)算,通過計(jì)算得：MAX_BONUS=10； MAX_SLEEP_AVG100*101000。 假設(shè)進(jìn)程的休眠時(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é)論,通過以上分析可得出：休眠時(shí)間越長(zhǎng) bonus越大 prio越小進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)越高。因此進(jìn)程的休眠時(shí)間長(zhǎng)，它的優(yōu)先級(jí)就能得到提高。,45,調(diào)度程序如何了解進(jìn)程的交互性強(qiáng)不強(qiáng)？,以進(jìn)程休眠的時(shí)間長(zhǎng)短作為標(biāo)準(zhǔn)。 如果一個(gè)進(jìn)程大部分時(shí)間都在休眠I/O消耗型，交互性強(qiáng) 如果一個(gè)進(jìn)程執(zhí)行時(shí)間比休眠時(shí)間長(zhǎng)處理器消耗型 交互性強(qiáng)的進(jìn)程，在運(yùn)行過程中可得到獎(jiǎng)勵(lì)

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