UNIX內(nèi)核分析1課件

UNIX內(nèi)核分析參考教材：UNIX操作系統(tǒng)教程

前序UNIX系統(tǒng)1969年誕生，以其特有的簡潔性和開放性獲得贊同與青睞，已經(jīng)被移植到數(shù)十種硬件平臺上。

UNIX是通用的，交互式的分時系統(tǒng)。UNIX系統(tǒng)已遠(yuǎn)遠(yuǎn)超出一個OS軟件所起的作用，它在方方面面潛移默化地影響著人們對軟件的設(shè)計和開發(fā)，其蘊(yùn)含的設(shè)計思想至今仍然是十分值得借鑒的。UNIX系統(tǒng)特點(diǎn)已有技術(shù)的精選、提煉和發(fā)展，簡潔實(shí)用，短小精悍，功能強(qiáng)大具有分層、可裝卸的文件卷系統(tǒng)任何一個程序可不加改變地在前臺/后臺異步運(yùn)行將文件、目錄和設(shè)備均統(tǒng)一看作文件提供I/O緩沖技術(shù)提供功能完備、使用靈活的命令語言豐富的核外系統(tǒng)程序采用高級語言編寫，可移植性好UNIX核心源程序結(jié)構(gòu)以UNIXV6為例，其內(nèi)核源程序約一萬行，按編譯方式大致分3類44個文件：.c文件：28個文件，190個可單獨(dú)編譯的子程序.h文件：全局變量，14個文件.s文件：匯編程序文件，約1000條，2個文件33個子程序進(jìn)程描述

——程序狀態(tài)字和通用寄存器PDP-11程序狀態(tài)字組成1514131211109876543210當(dāng)前態(tài)以前態(tài)優(yōu)先級/8級TNZVC進(jìn)程分Kernel/User2種運(yùn)行狀態(tài)，區(qū)別進(jìn)程處于不同地址空間：核心態(tài)/用戶態(tài)空間可否執(zhí)行特權(quán)指令使用不同的棧頂指針寄存器r6進(jìn)程描述

——程序狀態(tài)字和通用寄存器通用寄存器PDP-11/40有9個通用寄存器，長度16位，編號r0-r7r0-r1：I/O參數(shù)傳遞r2-r4：存放過程執(zhí)行時的局部變量r5：環(huán)境指針r6：堆棧指針，kernel/user態(tài)各1個r7：PC進(jìn)程描述

——進(jìn)程的存儲影響進(jìn)程映像中最為關(guān)鍵的部分是存儲映像。存儲映像由5部分組成：進(jìn)程控制塊PCB共享正文段數(shù)據(jù)段共享內(nèi)存段工作區(qū)進(jìn)程控制塊PCBUnix為了節(jié)省PCB所占主存，PCB分為2部分常駐內(nèi)存部分：Proc結(jié)構(gòu)。包含進(jìn)程調(diào)度必須的信息；非常駐內(nèi)存部分：User結(jié)構(gòu)。包含進(jìn)程運(yùn)行時才要用到的更多其他信息，它隨用戶程序和數(shù)據(jù)部分換進(jìn)/換出主存。User區(qū)的字段只能由正在運(yùn)行的進(jìn)程存取。即只有占用CPU的進(jìn)程才能訪問屬于當(dāng)前進(jìn)程的私有User區(qū)。整個系統(tǒng)有一個進(jìn)程表，稱為Proc數(shù)組。Unix系統(tǒng)最多有50個進(jìn)程；每個進(jìn)程有專用的User區(qū)，但核心根據(jù)進(jìn)程頁表，通過地址映射機(jī)構(gòu)，可訪問當(dāng)前進(jìn)程的User區(qū)。(好像系統(tǒng)中僅有一個User區(qū))共享正文段是指可由多個進(jìn)程共享的區(qū)域，包括純代碼形式的程序參數(shù)一個進(jìn)程的正文段也可以不存在工作區(qū)進(jìn)程的用戶棧和核心棧分別為進(jìn)程用戶態(tài)和核心態(tài)下運(yùn)行的工作區(qū)用于函數(shù)調(diào)用時的常數(shù)傳遞，現(xiàn)場保留，返回地址保存，局部變量存儲等進(jìn)程映像在存儲器中的分布PDP-11/40最多配置248K內(nèi)存，進(jìn)程映像分為常駐/非常駐內(nèi)存部分常駐部分：Proc，共享正文段的控制信息塊非常駐部分：數(shù)據(jù)段，共享正文段，工作區(qū)。Unix將除了共享正文段以外的其他部分作為一個整體處理，(結(jié)構(gòu)見下頁)無論在主存還是在盤交換區(qū)，該部分占用連續(xù)存儲區(qū)作為整體入/出主存Unix設(shè)置text數(shù)組(共40個元素)管理所有可共享正文段，表目內(nèi)容主要有：共享正文段外存地址，段長度，共享該段的進(jìn)程數(shù)等非常駐部分的分布結(jié)構(gòu)ppda區(qū)只有核心態(tài)進(jìn)程可以訪問User結(jié)構(gòu)系統(tǒng)棧區(qū)↓用戶程序/數(shù)據(jù)段用戶棧區(qū)↓底部/02891024頂部進(jìn)程數(shù)據(jù)區(qū)/ppdaPerProcessDataArea進(jìn)程的數(shù)據(jù)結(jié)構(gòu)

——進(jìn)程的擴(kuò)充控制塊/User結(jié)構(gòu)(1)每個進(jìn)程User結(jié)構(gòu)的虛擬起始地址都是u=14000。操作系統(tǒng)通過編譯、鏈接給u變量賦值，其地址空間對應(yīng)核心空間第7頁，其物理地址可以映射到主存中各進(jìn)程的user結(jié)構(gòu)。User結(jié)構(gòu)含有當(dāng)進(jìn)程換出內(nèi)存候不需要訪問的所有數(shù)據(jù)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)

——進(jìn)程的擴(kuò)充控制塊/User結(jié)構(gòu)(2)Structuser(主要部分){intu-rsav[2];/*調(diào)度進(jìn)程的正常保留區(qū)：r5，r6intu-qsav[2];/*中止系統(tǒng)調(diào)用的越級返回保留區(qū)intu-ssav[2];/*fork時恢復(fù)子進(jìn)程運(yùn)行的保留區(qū)charu-segflg;/*I/O標(biāo)志，0/1/2分別為：用戶數(shù)據(jù)/系統(tǒng)/用戶指令空間charu-error;/*出錯返回碼charu-uid;/*有效用戶標(biāo)識號charu-gid;/*有效用戶組標(biāo)識號charu-ruid/*實(shí)際用戶標(biāo)識號charu-rgid;/*實(shí)際用戶組標(biāo)識號intu-procp;/*指向本進(jìn)程的proc結(jié)構(gòu)指針char*u-base;/*I/O基址，文件傳輸中表示主存地址，R/W-目標(biāo)/信息源指針char*u-count;/*I/O字節(jié)數(shù)char*u-offset[2];/*文件傳輸中表示文件內(nèi)相對位移量(字節(jié))char*u-cdir;/*當(dāng)前目錄項(xiàng)i節(jié)點(diǎn)指針charu-dbuf[DIRSIZE];/*保留當(dāng)前用到的文件路徑名char*u-dirp;/*當(dāng)前目錄文件名指針進(jìn)程的數(shù)據(jù)結(jié)構(gòu)

——進(jìn)程的擴(kuò)充控制塊/User結(jié)構(gòu)(3)Struct{intu-ino/*i結(jié)點(diǎn)號/*該結(jié)構(gòu)保存一個文件目錄項(xiàng)charu-name[DIRSIZE];/*該文件路徑名分量}u-dent;int*u-pdir;/*父目錄項(xiàng)i結(jié)點(diǎn)指針charu-uisa[16];/*存放本進(jìn)程用戶空間地址寄存器內(nèi)容charu-uisd[16];/*存放本進(jìn)程用戶空間說明寄存器內(nèi)容charu-o];/*用戶打開文件表，共15個表目charu-arg[5];/*用戶傳入的自變量charu-tsize/*本進(jìn)程正文段塊數(shù)charu-dsize;/*本進(jìn)程數(shù)據(jù)段塊數(shù)intu-ssize;/*本進(jìn)程堆棧段塊數(shù)charu-signal[NSIG];/*軟中斷處理程序入口表，20個表目charu-utime;/*進(jìn)程用戶態(tài)下運(yùn)行時間charu-stime;/*進(jìn)程核心態(tài)下運(yùn)行時間charu-cutime;/*已中止子進(jìn)程用戶態(tài)下運(yùn)行時間總和charu-cstime;/*已中止子進(jìn)程核心態(tài)下運(yùn)行時間總和charu-intflag;/*系統(tǒng)調(diào)用是否執(zhí)行完成標(biāo)志}u;進(jìn)程映像的基本結(jié)構(gòu)圖p-addrp-sizep-textpx-daddrx-caddrx-iptr

共享正文段user核心棧數(shù)據(jù)段用戶棧ppdau-dsizeu-ssizeProc[]text[]file[]inode[]盤交換區(qū)P-sizex-sizeProc[n]text[m]進(jìn)程的狀態(tài)進(jìn)程在其生命周期的不同時刻有不同狀態(tài)；同一時刻不同進(jìn)程有不同狀態(tài)Unix系統(tǒng)中，進(jìn)城的完整狀態(tài)有9種。(轉(zhuǎn)換圖見下一頁)①創(chuàng)建狀態(tài)②內(nèi)存就緒③就緒且換出：新創(chuàng)建/原就緒進(jìn)程，因內(nèi)存緊張而換出④核心態(tài)執(zhí)行⑤用戶態(tài)執(zhí)行⑥內(nèi)存中睡眠：執(zhí)行I/O操作進(jìn)程，等待⑦睡眠且換出：內(nèi)存緊張時，睡眠進(jìn)程首先被換出⑧被剝奪狀態(tài)：進(jìn)程被調(diào)度程序剝奪了處理機(jī)后的狀態(tài)⑨僵死狀態(tài)：類似于中止?fàn)顟B(tài)進(jìn)程狀態(tài)轉(zhuǎn)換圖被剝奪485926371內(nèi)存外存盤交換區(qū)內(nèi)存足內(nèi)存不足調(diào)度exit中斷/返回中斷返回返回用戶態(tài)睡眠/喚醒睡眠fork調(diào)度調(diào)度喚醒被剝奪態(tài)進(jìn)程上下文進(jìn)程上下文由三部分組成：用戶級上下文：正文，數(shù)據(jù)，堆棧，共享內(nèi)存段寄存器上下文：PC,PS,SP,r0,…系統(tǒng)級上下文：Proc[],User,核心棧上下文切換時，要保證內(nèi)部數(shù)據(jù)的完整性和一致性。所以切換有嚴(yán)格的條件：當(dāng)進(jìn)程是自己進(jìn)入睡眠時系統(tǒng)調(diào)用/中斷完成返回用戶態(tài)而被剝奪以exit退出時Q：進(jìn)程從用戶態(tài)到核心態(tài)切換時，是否為上下文切換？進(jìn)程管理

——Unix進(jìn)程的各種調(diào)度狀態(tài)(1)UnixV6中進(jìn)程的調(diào)度狀態(tài)有6種，由p-stat描述。1SSLEEP：高優(yōu)先權(quán)睡眠狀態(tài)2SWAIT：低優(yōu)先權(quán)睡眠狀態(tài)3SRUN：運(yùn)行/可運(yùn)行狀態(tài)4SIDL：創(chuàng)建子進(jìn)程的中間狀態(tài)5SZOMB：進(jìn)程終止時的中間狀態(tài)6SSTOP：暫停/正被跟蹤狀態(tài)進(jìn)程管理——睡眠狀態(tài)等待時間發(fā)生而停止運(yùn)行的一種狀態(tài)，特點(diǎn)：P-stat為SSLEEP或SWAIT，不參與競爭處理機(jī)P-flag可能包含SLOAD標(biāo)志，也可能不包含KISA6,KISD6不反映進(jìn)程圖像在內(nèi)存的位置睡眠原因：進(jìn)程間同步與互斥引起使用互斥資源無法滿足同步等待I/O結(jié)束同步等待出現(xiàn)處理對象，如0#進(jìn)程/sched暫時沒有處理對象進(jìn)程間的其他同步操作，sleep(),wait()..臨界區(qū)互斥進(jìn)程管理

——高低優(yōu)先權(quán)睡眠狀態(tài)核心態(tài)下執(zhí)行sleep進(jìn)入睡眠狀態(tài)P-pri由系統(tǒng)按照睡眠原因設(shè)置，-100-+127SSLEEP:P-pri<0，高優(yōu)先權(quán)睡眠0#進(jìn)程：-100請求資源：-50等快速設(shè)備I/O：-50SWAIT:P-pri>0，低優(yōu)先權(quán)睡眠父子進(jìn)程同步：40等低速設(shè)備I/O：10-20喚醒：wakeup程序完成，喚醒后P-pri<100。有時還要由sched完成內(nèi)存/盤交換區(qū)的交換進(jìn)程調(diào)度算法

——動態(tài)優(yōu)先權(quán)法Unix采用動態(tài)優(yōu)先權(quán)法，采用的策略有：核心態(tài)運(yùn)行時，除非自動放棄，不重新調(diào)度，保證高速；進(jìn)程睡眠喚醒后，較其他就緒進(jìn)程有高的優(yōu)先權(quán)。因?yàn)樵擃愡M(jìn)程將繼續(xù)執(zhí)行OS程序；進(jìn)程睡眠喚醒后，按照等待事件的緊迫程度，賦予不同優(yōu)先權(quán)。即同一程序不同段有不同優(yōu)先權(quán)；高級用戶進(jìn)程較一般用戶進(jìn)程有較高的優(yōu)先級；使用處理機(jī)程度低、交互作用平凡的進(jìn)程賦予較高優(yōu)先權(quán)，以獲得比較合理的響應(yīng)時間。進(jìn)程調(diào)度算法

——進(jìn)程優(yōu)先數(shù)計算方法(1)優(yōu)先數(shù)確定的兩種方法設(shè)置方式：用于高/低優(yōu)先權(quán)睡眠進(jìn)程計算方式：包括計算方法和計算時機(jī)進(jìn)程正在/即將轉(zhuǎn)入用戶態(tài)運(yùn)行時，用計算方式確定其優(yōu)先權(quán)對于一般用戶進(jìn)程來說，用計算方式獲得的優(yōu)先數(shù)大于設(shè)置獲得的優(yōu)先數(shù)進(jìn)程調(diào)度算法

——進(jìn)程優(yōu)先數(shù)計算方法(2)算式：p-pri=min{127,(p-cpu/16+PUSER+p-nice)}說明：P-pri:字符型變量，-128~+127，最低-100PUSER:固定偏置值。設(shè)置目的是：為了使被喚醒的睡眠進(jìn)程應(yīng)具有的優(yōu)先數(shù)相銜接。被喚醒進(jìn)程優(yōu)先數(shù)：-100~100V6:PUSER=100;S5:PUSER=60進(jìn)程調(diào)度算法

——進(jìn)程優(yōu)先數(shù)計算程序Setpri(up)/*up是proc結(jié)構(gòu)指針{register*pp,p;pp=up;p=(pp→p-cpu&0377)/16;/*p-cpu最大值為255p=+PUSER+pp→p-nice;if(p>127)p=127;if(p>curpri)runrun++;/*curpri:現(xiàn)行運(yùn)行進(jìn)程被調(diào)度占用處理機(jī)時的優(yōu)先數(shù)/*runrun:進(jìn)程調(diào)度標(biāo)志，為0表示不要求進(jìn)行切換調(diào)度pp→p-pri=p;}進(jìn)程調(diào)度算法——關(guān)于p-niceP-nice反映進(jìn)程具有的相對優(yōu)先程度一般用戶可設(shè)置范圍：0~20；高級用戶：-128~20通過系統(tǒng)調(diào)用nice(priority)完成設(shè)置，代碼：{registern;n=u.uar0[R0];/*u.uar0[R0]保存系統(tǒng)調(diào)用參數(shù)if(n>20)n=20;if(n<0&&!suser())n=0;/*!suser()判斷是否為高級用戶u.u-proc→p-nice=n;}進(jìn)程調(diào)度算法——關(guān)于p-cpuP-cpu反映進(jìn)程使用cpu程度每個時鐘周期+1

rt=tu/tl=tu/(tu+tnu)其中:rt:進(jìn)程使用cpu的時間比

tu:進(jìn)程生成后使用cpu時間的累計值

tl:進(jìn)程生成后所經(jīng)時間

tnu:進(jìn)程生成候不占用cpu的時間累計值進(jìn)程調(diào)度算法

——計算進(jìn)程優(yōu)先數(shù)的3個時機(jī)時鐘中斷處理程序中，每隔一秒，對所有優(yōu)先數(shù)大于PUSER的進(jìn)程復(fù)算優(yōu)先數(shù)；陷入處理結(jié)束前，重新計算本進(jìn)程優(yōu)先數(shù)；現(xiàn)進(jìn)程執(zhí)行時鐘中斷處理程序時，如果中斷前為用戶態(tài)，每隔一秒，重新計算本進(jìn)程優(yōu)先數(shù)。進(jìn)程調(diào)度算法

——進(jìn)程切換調(diào)度的2個時機(jī)(1)當(dāng)前運(yùn)行進(jìn)程不再具備運(yùn)行條件，自動放棄CPU進(jìn)程結(jié)束進(jìn)程等待子進(jìn)程進(jìn)入暫停狀態(tài)，等待父進(jìn)程處理執(zhí)行進(jìn)程申請擴(kuò)充主存，無法滿足，入盤交換區(qū)執(zhí)行進(jìn)程要求調(diào)入某一共享正文段，則先將該進(jìn)程圖像調(diào)出，等到適當(dāng)時機(jī)按下列順序調(diào)入：

共享正文段，ppda，數(shù)據(jù)段，用戶棧段進(jìn)程調(diào)度算法

——進(jìn)程切換調(diào)度的2個時機(jī)(2)系統(tǒng)中存在較當(dāng)前執(zhí)行進(jìn)程更適宜占用CPU的進(jìn)程，于是系統(tǒng)在中斷/陷入處理末尾強(qiáng)迫當(dāng)前運(yùn)行進(jìn)程放棄CPU強(qiáng)迫調(diào)度標(biāo)志是runrun，它的設(shè)置時機(jī)為：睡眠進(jìn)程被喚醒，或被暫停運(yùn)行進(jìn)程變?yōu)檫\(yùn)行狀態(tài)時，發(fā)現(xiàn)其優(yōu)先權(quán)高于現(xiàn)運(yùn)行進(jìn)程Setpri程序中，發(fā)現(xiàn)計算所的進(jìn)程優(yōu)先數(shù)高于當(dāng)前運(yùn)行進(jìn)程被調(diào)度運(yùn)行時的優(yōu)先數(shù)/curpri。下列2種情況現(xiàn)運(yùn)行進(jìn)程計算所的優(yōu)先數(shù)大于原先值：進(jìn)程由核心態(tài)變?yōu)橛脩魬B(tài)用戶態(tài)下運(yùn)行進(jìn)程已占用了一段處理機(jī)時間，使p-cpu增大進(jìn)程調(diào)度算法

——進(jìn)程切換調(diào)度程序swtchSwtch任務(wù)：選擇進(jìn)程占用CPU，保存/恢復(fù)現(xiàn)場Swtch執(zhí)行可能涉及三個處于核心態(tài)的進(jìn)程原運(yùn)行進(jìn)程，即調(diào)用swtch的進(jìn)程，保存現(xiàn)場，恢復(fù)0#系統(tǒng)調(diào)度進(jìn)程0#：從內(nèi)存就緒隊列選一個進(jìn)程占用CPU新選中運(yùn)行進(jìn)程：1)設(shè)置UISA,UISD寄存器組2)從核心棧中恢復(fù)PC，返回原核心態(tài)進(jìn)程的睡眠和喚醒進(jìn)程間實(shí)施互斥、同步機(jī)制時，需要進(jìn)入睡眠狀態(tài)睡眠原因消失，進(jìn)程被喚醒進(jìn)程睡眠sleep()Sleep(chan,pri)可使進(jìn)程進(jìn)入高/低優(yōu)先權(quán)睡眠Chan：睡眠原因Pri：睡眠后預(yù)置的優(yōu)先數(shù)，>0低優(yōu)先權(quán)主要工作：設(shè)置欲睡眠進(jìn)程的p-whan/原因,p-stat,p-pri，并調(diào)用swtch進(jìn)行調(diào)度rp→p-wchan=chan;rp→p-stat=SSLEEP/SWAIT;rp→p-pri=pri設(shè)置過程執(zhí)行語句為臨界區(qū)，執(zhí)行前處理既優(yōu)先級提高為6級(避免中斷)進(jìn)程睡眠sleep()說明若進(jìn)程欲進(jìn)入低優(yōu)先權(quán)睡眠，首先應(yīng)檢測是否收到不可忽略的信號p-flag。如果收到，先轉(zhuǎn)去執(zhí)行信號處理程序；系統(tǒng)設(shè)置runrun標(biāo)志，說明是否有在盤交換區(qū)的進(jìn)程準(zhǔn)備就緒而因內(nèi)存不足無法進(jìn)入。若runrun已經(jīng)設(shè)置，則將低優(yōu)先級睡眠進(jìn)程入盤交換區(qū)，并調(diào)用sched.睡眠喚醒wakeup()wakeup(chan)喚醒因chan原因睡眠的進(jìn)程，并將其狀態(tài)置為SRUN主要工作：搜索proc[]區(qū)，由setrun喚醒所有因chan睡眠的進(jìn)程：p-wchan=0;p-stat=SRUN說明：系統(tǒng)設(shè)置runout標(biāo)志，表示盤交換區(qū)無進(jìn)程圖像可入內(nèi)存。若runout>=1,則執(zhí)行sched的0#進(jìn)程睡眠，否則喚醒。進(jìn)程圖像在內(nèi)存/盤交換區(qū)間傳遞圖像傳遞由0#進(jìn)程調(diào)用sched完成圖像入內(nèi)存算法：sched按照盤交換區(qū)中就緒進(jìn)程p-time，從長到短逐個調(diào)入內(nèi)存，直到全部調(diào)入，或者無足夠內(nèi)存圖像出內(nèi)存算法：若調(diào)入進(jìn)程因內(nèi)存不足無法調(diào)入時，sched試圖從內(nèi)存調(diào)出一進(jìn)程，然后再次執(zhí)行調(diào)入操作。調(diào)出算法考慮因素某些進(jìn)程不應(yīng)該被調(diào)出：P-flag為SSYS和SLOCK的進(jìn)程優(yōu)先調(diào)出：p-stat為SWAIT和SSTOP的進(jìn)程。若上述優(yōu)先進(jìn)程，則優(yōu)先考慮：p-stat為SSLEEP或SRUN中在內(nèi)存駐留時間最長/p-time的進(jìn)程。同時要求：內(nèi)存被選中進(jìn)程p-time>2s盤交換區(qū)欲入內(nèi)存進(jìn)程p-time>3s否則，不執(zhí)行調(diào)出操作進(jìn)程的創(chuàng)建Unix進(jìn)程創(chuàng)建有2種方式