第3章-進(jìn)程管理與調(diào)度

1、LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)操作系統(tǒng)講義操作系統(tǒng)講義孫 清西安財(cái)經(jīng)學(xué)院LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院操作系統(tǒng)概述操作系統(tǒng)概述 系統(tǒng)啟動(dòng)及用戶界面系統(tǒng)啟動(dòng)及用戶界面進(jìn)程管理與調(diào)度進(jìn)程管理與調(diào)度進(jìn)程同步進(jìn)程同步第一章第二章第三章第四章設(shè)備管理設(shè)備管理 第七章Contents課程內(nèi)容安排課程內(nèi)容安排 西安財(cái)經(jīng)學(xué)院文件管理文件管理第六章存儲(chǔ)器管理存儲(chǔ)器管理 第五章LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院第三章第三章 進(jìn)程管理與調(diào)度進(jìn)程管理與調(diào)度 進(jìn)程的控制進(jìn)程的控制1進(jìn)程的狀態(tài)遷移及進(jìn)程的狀態(tài)遷移及PCB2處理機(jī)調(diào)度處理機(jī)調(diào)度3西安財(cái)經(jīng)學(xué)院線程及其基本概念線程及其基本概念 4Linux中相關(guān)源代碼

2、分析中相關(guān)源代碼分析5LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院3.1 進(jìn)程的狀態(tài)遷移及進(jìn)程的狀態(tài)遷移及PCB進(jìn)程進(jìn)程的定義的定義運(yùn)行中的程序，有生命周期，占用系統(tǒng)資源，包括：程序、數(shù)據(jù)、PCB(進(jìn)程控制塊)CPU處理機(jī)的工作狀態(tài)處理機(jī)的工作狀態(tài) 管態(tài)（核心態(tài)）：系統(tǒng)態(tài) 目態(tài)：用戶態(tài)狀態(tài)之間的轉(zhuǎn)換狀態(tài)之間的轉(zhuǎn)換 目態(tài)管態(tài)：唯一途徑是中斷 管態(tài)目態(tài)：設(shè)置程序狀態(tài)字PSWLOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程控制塊（進(jìn)程控制塊（PCB） PCB：用于存放管理進(jìn)程運(yùn)行的必要信息。 PCB處于核心段，用戶不能直接訪問和修改PCB。 OS把所有PCB組織在一起，放在固定的內(nèi)存區(qū)域，構(gòu)成PCB表。 PCB

3、表的大小決定了系統(tǒng)可同時(shí)運(yùn)行程序的最大數(shù)目-道數(shù)。 進(jìn)程的靜態(tài)組成包括進(jìn)程的程序、數(shù)據(jù)、系統(tǒng)/用戶棧和PCB，這些統(tǒng)稱為進(jìn)程影像。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院PCB包含四部分內(nèi)容包含四部分內(nèi)容 v進(jìn)程描述信息進(jìn)程描述信息：pid，gidv進(jìn)程控制信息進(jìn)程控制信息：狀態(tài)、優(yōu)先級(jí)、運(yùn)行統(tǒng)計(jì)信息、同步和通信、代碼執(zhí)行入口地址、程序的外存地址。v所擁有的資源和使用情況所擁有的資源和使用情況：占用內(nèi)存大小及其管理用數(shù)據(jù)結(jié)構(gòu)指針、虛擬地址空間、共享數(shù)據(jù)段、輸入/輸出設(shè)備、數(shù)據(jù)緩沖區(qū)、打開文件列表等。vCPU現(xiàn)場(chǎng)保護(hù)信息現(xiàn)場(chǎng)保護(hù)信息：寄存器值LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程的狀態(tài)遷移進(jìn)程

4、的狀態(tài)遷移LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院3.2 進(jìn)程的控制進(jìn)程的控制v進(jìn)程的控制使用原語實(shí)現(xiàn)。 原語（原語（primitive）是在管態(tài)下運(yùn)行，執(zhí)行期間不允許被中斷。v原語的實(shí)現(xiàn)方法是以系統(tǒng)調(diào)用方式提供原語接口，采用中斷屏蔽方式來實(shí)現(xiàn)原語功能。進(jìn)程的控制原語包括： 創(chuàng)建、撤銷、阻塞、喚醒、掛起、激活。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院1、進(jìn)程的創(chuàng)建、進(jìn)程的創(chuàng)建v父進(jìn)程創(chuàng)建子進(jìn)程時(shí)，系統(tǒng)從空PCB池中取一個(gè)空PCB，并在進(jìn)程表中增加一項(xiàng)；v為新進(jìn)程分配地址空間，傳遞環(huán)境變量，構(gòu)造共享地址空間；v查找輔存，將新進(jìn)程正文裝到內(nèi)存；v初始化PCB，為新進(jìn)程分配PID，初始化PSW；v加入就

5、緒隊(duì)列。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院用用fork()系統(tǒng)調(diào)用創(chuàng)建子進(jìn)程：系統(tǒng)調(diào)用創(chuàng)建子進(jìn)程：pid=fork()fork()的返回值：的返回值：0 在子進(jìn)程中；在子進(jìn)程中；0 在父進(jìn)程中；在父進(jìn)程中；-1 創(chuàng)建失敗。創(chuàng)建失敗。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院創(chuàng)建進(jìn)程實(shí)例創(chuàng)建進(jìn)程實(shí)例 #include main()int p1,p2,i;while (p1=fork()=-1) ;if (p1 =0)for(i=0;i10;i+)printf(“daughter %dn”,i);elsewhile (p2=fork()=-1) ;if (p2 =0)for(i=0;i10;i+)

6、printf (“son %dn”,i);else for(i=0;i10;i+) printf(“parent %dn”,i);LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院2、進(jìn)程的撤銷（或終止）、進(jìn)程的撤銷（或終止）撤銷進(jìn)程的情況： 正常終止； 由于錯(cuò)誤導(dǎo)致非正常終止； 由祖先進(jìn)程的要求而撤銷。調(diào)用exit()可終止進(jìn)程。 找到該進(jìn)程的PCB； 將該進(jìn)程擁有的資源歸還給父進(jìn)程或操作系統(tǒng)； 若該進(jìn)程擁有子進(jìn)程，應(yīng)先撤銷它的所有子孫進(jìn)程； 撤銷進(jìn)程出隊(duì)列，歸還它的PCB。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院3、進(jìn)程的阻塞、進(jìn)程的阻塞v從執(zhí)行態(tài)進(jìn)入等待態(tài)，由于等待某個(gè)事件（如，I/O存?。┑陌l(fā)生。v

7、停止進(jìn)程執(zhí)行，保存現(xiàn)場(chǎng)信息到PSW；v修改PCB的有關(guān)內(nèi)容，將進(jìn)程由執(zhí)行態(tài)改為等待態(tài)；v將PCB加入等待態(tài)隊(duì)列。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院4、進(jìn)程的喚醒、進(jìn)程的喚醒v當(dāng)進(jìn)程所等待的事件發(fā)生，由系統(tǒng)進(jìn)程或事件發(fā)生進(jìn)程調(diào)用喚醒原語。v將被喚醒的進(jìn)程置為就緒態(tài)，并將其PCB加入相關(guān)的就緒隊(duì)列。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院5、進(jìn)程的掛起、進(jìn)程的掛起v主要用于中級(jí)調(diào)度，可以對(duì)活動(dòng)等待態(tài)或活動(dòng)就緒態(tài)的進(jìn)程掛起到靜止等待態(tài)或靜止就緒態(tài)。v將被掛起進(jìn)程的非常駐部分交換到磁盤對(duì)換區(qū)。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院6、進(jìn)程的激活、進(jìn)程的激活v激活是掛起的逆過程v將被掛起進(jìn)程的非常駐部

8、分交換到內(nèi)存,并修改狀態(tài)。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院源代碼閱讀理解源代碼閱讀理解-fork.cvfork（）調(diào)用以下模塊： find_empty_process() copy_process() verify_area()：進(jìn)程內(nèi)存區(qū)域驗(yàn)證 copy_mem()：內(nèi)存分配函數(shù)v寫時(shí)復(fù)制機(jī)制(copy on write)： 在fork()執(zhí)行過程中，新進(jìn)程將與父進(jìn)程共同使用父進(jìn)程已有的代碼和數(shù)據(jù)內(nèi)存頁面。 只有當(dāng)以后執(zhí)行過程中，如果其中一個(gè)進(jìn)程以寫方式訪問內(nèi)存時(shí)，才會(huì)在寫操作前被復(fù)制到新申請(qǐng)的內(nèi)存頁面中。重點(diǎn)理解！LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院copy_process()v

9、用于創(chuàng)建并復(fù)制進(jìn)程的代碼段和數(shù)據(jù)段以及環(huán)境。v 為進(jìn)程申請(qǐng)一頁內(nèi)存放PCB，并復(fù)制當(dāng)前進(jìn)程的PCB作為新進(jìn)程的PCB模板。v 隨后對(duì)數(shù)據(jù)進(jìn)行修改，把當(dāng)前進(jìn)程設(shè)為父進(jìn)程，復(fù)位新進(jìn)程各統(tǒng)計(jì)值。v 設(shè)置新進(jìn)程的代碼段和數(shù)據(jù)段的基址和段限長，v 復(fù)制當(dāng)前進(jìn)程內(nèi)存分頁管理的頁目錄項(xiàng)和頁表項(xiàng)。Linux0.11版，所有進(jìn)程共用一個(gè)頁目錄表，新進(jìn)程的頁表則需要另申請(qǐng)一頁內(nèi)存。v 在GDT中設(shè)置新進(jìn)程的TSS和LDTv 將新進(jìn)程設(shè)置成可運(yùn)行狀態(tài)，并向當(dāng)前進(jìn)程返回新進(jìn)程號(hào)。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院linux系統(tǒng)進(jìn)程的創(chuàng)建順序系統(tǒng)進(jìn)程的創(chuàng)建順序v進(jìn)程0（內(nèi)核創(chuàng)建）進(jìn)程1（第一個(gè)用fork()創(chuàng)建的進(jìn)

10、程）tty終端進(jìn)程login進(jìn)程用戶進(jìn)程從命令的執(zhí)行開始解讀從命令的執(zhí)行開始解讀linux系統(tǒng)調(diào)用內(nèi)核代碼系統(tǒng)調(diào)用內(nèi)核代碼$ ls l /home/henry/shell 進(jìn)程會(huì)創(chuàng)建一個(gè)新進(jìn)程并在其中執(zhí)行/bin/ls命令。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院shellLOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院父子進(jìn)程關(guān)系示意圖父子進(jìn)程關(guān)系示意圖LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院3.3 處理器（處理器（CPU）調(diào)度）調(diào)度計(jì)算機(jī)調(diào)度分為三級(jí)：高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。1、高級(jí)調(diào)度高級(jí)調(diào)度（Long-term Scheduler） 允許作業(yè)或進(jìn)程進(jìn)入就緒態(tài)，用來控制作業(yè)或進(jìn)程的總量和順序。通

11、常用在大型機(jī)和批處理系統(tǒng)中。2、中級(jí)調(diào)度中級(jí)調(diào)度（Mid-term Scheduler） 主要用于將進(jìn)程在主存和輔存之間換入換出。3、低級(jí)調(diào)度低級(jí)調(diào)度（Short-term Scheduler） 也稱為CPU調(diào)度，是真正讓進(jìn)程占用CPU執(zhí)行的調(diào)度程序。通常在發(fā)生：時(shí)鐘中斷、I/O中斷、系統(tǒng)調(diào)用、或有其它形式的信號(hào)時(shí)。v 可以分為剝奪式調(diào)度和非剝奪式調(diào)度。v 另外一個(gè)調(diào)度組件（dispatcher）用于進(jìn)程切換和模式切換。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程的切換進(jìn)程的切換進(jìn)程切換程序（dispatch）： 保持處理機(jī)上下文 修改當(dāng)前進(jìn)程的PCB 選擇另一個(gè)進(jìn)程執(zhí)行(由scheduler實(shí)

12、施) 修改被選中進(jìn)程的PCB 將當(dāng)前進(jìn)程存儲(chǔ)管理數(shù)據(jù)結(jié)構(gòu)改為新選進(jìn)程的 恢復(fù)被選進(jìn)程的處理機(jī)現(xiàn)場(chǎng)LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院調(diào)度原則調(diào)度原則vCPU利用率: 使CPU盡量處于忙狀態(tài)。v吞吐率：單位時(shí)間內(nèi)完成進(jìn)程的個(gè)數(shù)。v周轉(zhuǎn)時(shí)間：從作業(yè)提交到完成所用的時(shí)間。v等待時(shí)間：是進(jìn)程在就緒隊(duì)列中總共等待的時(shí)間。v響應(yīng)時(shí)間：用于交互式系統(tǒng)。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院調(diào)度算法調(diào)度算法vFIFO(/FCFS)先進(jìn)先出或先來先服務(wù)vSJF最短作業(yè)優(yōu)先/最短剩余時(shí)間優(yōu)先vHPF基于優(yōu)先級(jí)的調(diào)度vRR輪轉(zhuǎn)法調(diào)度（給每個(gè)進(jìn)程固定的時(shí)間片）vHRN最高響應(yīng)比者優(yōu)先R=（作業(yè)處理時(shí)間+作業(yè)等待時(shí)間

13、）/作業(yè)處理時(shí)間v多級(jí)隊(duì)列調(diào)度v參考閱讀Linux調(diào)度模塊代碼： sched.c中的schedule()LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程調(diào)度舉例進(jìn)程調(diào)度舉例進(jìn)程P1P2P3P4P5創(chuàng)建時(shí)刻010122024需運(yùn)行時(shí)間405103015優(yōu)先級(jí)系統(tǒng)時(shí)間片：8按照某種算法給出進(jìn)程的調(diào)度時(shí)間序列，計(jì)算該算法的平均周轉(zhuǎn)時(shí)間。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院各種算法的比較各種算法的比較deadline是用戶作業(yè)中提供的最差完成時(shí)間starvation是用于測(cè)試多道系統(tǒng)中的死鎖問題。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院Linux中的調(diào)度中的調(diào)度 v從2.5內(nèi)核開始，Linux使用多級(jí)反饋隊(duì)

14、列，優(yōu)先級(jí)0140。其中099保留給實(shí)時(shí)進(jìn)程，100140留給普通進(jìn)程。v調(diào)用擁有最高優(yōu)先級(jí)的進(jìn)程在其時(shí)間片內(nèi)運(yùn)行；v分為活動(dòng)隊(duì)列和過期隊(duì)列。將用完時(shí)間片的進(jìn)程放入過期隊(duì)列；優(yōu)先調(diào)用活動(dòng)隊(duì)列中的進(jìn)程，只有活動(dòng)隊(duì)列空時(shí)，才將過期隊(duì)列轉(zhuǎn)為活動(dòng)隊(duì)列。vLinux中的PCB是由數(shù)據(jù)結(jié)構(gòu)task_struct來描述。vtask向量表是指向PCB的指針數(shù)組。vLinux將task向量表中的所有空槽位連成一個(gè)鏈表tarray_freelist。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院Linux 0.11版中進(jìn)程的狀態(tài)遷移圖版中進(jìn)程的狀態(tài)遷移圖系統(tǒng)調(diào)用/中斷返回終止暫停喚醒睡眠0032014Interrupti

15、bleUninterruptibleRunning in kernel modeRunning in user modeStoppedZombie調(diào)度睡眠繼續(xù)中斷/返回喚醒LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程運(yùn)行狀態(tài)進(jìn)程運(yùn)行狀態(tài)v TASK_RUNNING：標(biāo)號(hào)為0的狀態(tài)，若此時(shí)沒有被CPU運(yùn)行，則稱為就緒態(tài)。v TASK_INTERRUPTIBLE：當(dāng)系統(tǒng)發(fā)生中斷/釋放等待的資源/收到一個(gè)信號(hào)，則可以喚醒進(jìn)程到就緒態(tài)。v TASK_UNINTERRUPTIBLE：進(jìn)程需要不受干擾地等待或者所等待的事件會(huì)很快發(fā)生時(shí)使用。只有被使用wake_up()函數(shù)明確喚醒才能轉(zhuǎn)換到就緒態(tài)。v TAS

16、K_STOPPED：用于調(diào)試時(shí)暫停。當(dāng)進(jìn)程受到信號(hào)SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU時(shí)會(huì)進(jìn)入暫停態(tài)。可向其發(fā)送SIGCONT喜歡讓其進(jìn)入就緒態(tài)。v TASK_ZOMBIE：當(dāng)進(jìn)程停止運(yùn)行，但其父進(jìn)程還沒有調(diào)用wait()詢問其狀態(tài)時(shí)，該進(jìn)程處于此狀態(tài)。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院3.4 線程及其基本概念線程及其基本概念 線程（Thread）又稱為輕量級(jí)進(jìn)程。將進(jìn)程的資源分配與調(diào)度分開，引入線程的概念。 一個(gè)進(jìn)程至少有一個(gè)線程。 多個(gè)線程共享其所在進(jìn)程的資源，包括PCB。但所執(zhí)行的程序不同，映射到不同的物理地址，使用不同的棧。線程只由相關(guān)堆棧（用戶棧/核心棧）寄存器和TCB組成。對(duì)線程的調(diào)度即可以由OS進(jìn)行，也可以由用戶程序進(jìn)行。LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院線程的優(yōu)點(diǎn)線程的優(yōu)點(diǎn)v切換快速v管理開銷小v通信容易v線程數(shù)目可以很多LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院Word 進(jìn)程中的三個(gè)線程進(jìn)程中的三個(gè)線程LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院Web server 中的多線程中的多線程LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院進(jìn)程中線程的執(zhí)行過程示意圖進(jìn)程中線程的執(zhí)行過程示意圖LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院具有單個(gè)線程和多個(gè)線程的進(jìn)程示意圖具有單個(gè)線程和多個(gè)線程的進(jìn)程示意圖LOGO房地產(chǎn)房地產(chǎn)E網(wǎng)網(wǎng)西安財(cái)經(jīng)學(xué)院線程的實(shí)