操作系統(tǒng)第二章

1、第2章進(jìn)程管理2.1 進(jìn)程的引入與概念2.22.32.42.5進(jìn)程的描述進(jìn)程的控制線程的引入與概念處理機(jī)的調(diào)度22.1 進(jìn)程的引入與概念2.1.1 程序的順序執(zhí)行2.1.2 程序的并發(fā)執(zhí)行2.1.3 進(jìn)程的基本概念32.1.1 程序的順序執(zhí)行(1)例1：有一程序?qū)τ脩糨斎氲臄?shù)據(jù)進(jìn)行計(jì)算并打印計(jì)算結(jié)果。程序執(zhí)行步驟：輸入數(shù)據(jù)(I)計(jì)算(C)打印輸出(P)語(yǔ)句執(zhí)行順序?yàn)椋?I1C1P1I2C2P2例2：有一包含3條語(yǔ)句的程序段：S1： a=x+y;S2： b=a-5;S3： c=b+1;S1S2S32.1.1 程序的順序執(zhí)行(2)程序順序執(zhí)行的特點(diǎn)程序執(zhí)行的順序性程序環(huán)境的封閉性程序結(jié)果的可再現(xiàn)性

2、 優(yōu)點(diǎn)順序程序的封閉性和可再現(xiàn)性為程序員調(diào)試程序帶來了很大方便 缺點(diǎn)資源的獨(dú)占性使得系統(tǒng)資源利用率非常低52.1.2 程序的并發(fā)執(zhí)行(1)例3：系統(tǒng)中有多道程序?qū)τ脩糨斎氲臄?shù)據(jù)進(jìn)行計(jì)算并打印計(jì)算結(jié)果。程序執(zhí)行步驟：6P1P2P3P4I1I2I3I4C1C2C3C42.1.2 程序的并發(fā)執(zhí)行(2)程序并發(fā)執(zhí)行的特點(diǎn)增強(qiáng)了計(jì)算機(jī)系統(tǒng)的處理能力，提高了資源利用率程序執(zhí)行的間斷性：并行執(zhí)行的程序間產(chǎn)生了相互制約關(guān)系執(zhí)行暫停執(zhí)行因共享資源或協(xié)調(diào)完成同一任務(wù)引起間接制約：共享資源直接制約：協(xié)同完成任務(wù)72.1.2 程序的并發(fā)執(zhí)行(3)失去了程序的封閉性資源共享程序結(jié)果的不可再現(xiàn)性例4：有兩個(gè)并發(fā)執(zhí)行的程序

3、A和B，共享一個(gè)變量count，count的初值為N。Program A:Program B:Print(count);count=0;8S1 count=count+1;S2S32.1.2 程序的并發(fā)執(zhí)行(4)程序A和B執(zhí)行時(shí)count的結(jié)果取決于語(yǔ)句執(zhí)行順序S1,S2,S3，count：N+1,N+1,0S2,S3,S1，count：N,0,1S2,S1,S3，count：N,N+1,0程序與CPU執(zhí)行的活動(dòng)之間不再一一對(duì)應(yīng)程序是完成某一特定功能的指令序列，是靜態(tài)的CPU執(zhí)行的活動(dòng)是動(dòng)態(tài)的92.1.3 進(jìn)程的基本概念(1)進(jìn)程的定義進(jìn)程是程序的一次執(zhí)行進(jìn)程是可以并行執(zhí)行的計(jì)算進(jìn)程是一個(gè)程序

4、與其使用的數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)發(fā)生的活動(dòng)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位進(jìn)程是可以和其他程序并行執(zhí)行的程序的一次執(zhí)行102.1.3 進(jìn)程的基本概念(2)進(jìn)程的特性動(dòng)態(tài)性：進(jìn)程是程序的一次執(zhí)行，具有生命期獨(dú)立性：進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位并發(fā)性：進(jìn)程可以并發(fā)執(zhí)行異步性：進(jìn)程間的相互制約，使進(jìn)程執(zhí)行具有間隙結(jié)構(gòu)性：進(jìn)程具有結(jié)構(gòu)程序數(shù)據(jù)(地址空間、堆棧等）進(jìn)程控制塊(PCB)112.2 進(jìn)程的描述2.2.1 進(jìn)程控制塊2.2.22.2.3進(jìn)程的狀態(tài)進(jìn)程的組織122.2.1 進(jìn)程控制塊PCB(1)進(jìn)程存在的惟一標(biāo)識(shí) 進(jìn)程動(dòng)態(tài)性的集中表現(xiàn)

5、 包含進(jìn)程的描述信息和管理控制信息進(jìn)程標(biāo)識(shí)符：內(nèi)部/外部進(jìn)程的狀態(tài)（當(dāng)前狀態(tài)）進(jìn)程調(diào)度信息進(jìn)程優(yōu)先級(jí)進(jìn)程所在各種隊(duì)列的指針進(jìn)程的存儲(chǔ)管理信息132.2.1 進(jìn)程控制塊PCB(2)進(jìn)程要執(zhí)行程序的內(nèi)外存起始地址及采取的保護(hù)信息進(jìn)程使用的資源信息分配給進(jìn)程的I/O設(shè)備正在執(zhí)行的I/O請(qǐng)求信息當(dāng)前進(jìn)程正打開的文件CPU現(xiàn)場(chǎng)保護(hù)區(qū)程序計(jì)數(shù)器工作寄存器程序狀態(tài)字142.2.1 進(jìn)程控制塊PCB(3)堆棧指針記帳信息CPU占用量進(jìn)程之間的家族關(guān)系父進(jìn)程子進(jìn)程152.2.1 進(jìn)程控制塊PCB(4)Linux的進(jìn)程16struct task_struct pid_t pid; /進(jìn)程標(biāo)識(shí)符volatile l

6、ong state; /進(jìn)程狀態(tài)unsigned int time_slice; /進(jìn)程調(diào)度信息int prio, static_prio; /進(jìn)程優(yōu)先級(jí)struct files_struct *files; /打開文件列表struct mm_struct *mm, *active_mm; /進(jìn)程地址空間struct list_head tasks; /進(jìn)程任務(wù)鏈表void *stack; /進(jìn)程堆棧struct thread_info *thread_info; /當(dāng)前進(jìn)程基本信息.;2.2.2 進(jìn)程的狀態(tài)(1)三種基本狀態(tài)運(yùn)行態(tài)：正在CPU上運(yùn)行的進(jìn)程所處狀態(tài)。單CPU系統(tǒng)中，任何時(shí)候只能

7、有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。阻塞態(tài)/等候態(tài)：一個(gè)進(jìn)程因等待某事件發(fā)生而不能運(yùn)行時(shí)所處狀態(tài)。就緒態(tài)：已經(jīng)獲得了除CPU之外的全部資源并等待系統(tǒng)分配CPU，一旦獲得CPU即可以變?yōu)檫\(yùn)行態(tài)的進(jìn)程狀態(tài)。172.2.2 進(jìn)程的狀態(tài)(2)創(chuàng)建態(tài)與終止態(tài)創(chuàng)建態(tài)：進(jìn)程被創(chuàng)建時(shí)的狀態(tài)。終止態(tài)：進(jìn)程運(yùn)行完成時(shí)的狀態(tài)。 進(jìn)程狀態(tài)的轉(zhuǎn)換182.2.2 進(jìn)程的狀態(tài)(3)運(yùn)行態(tài)就緒態(tài)運(yùn)行態(tài)等待態(tài)就緒態(tài)運(yùn)行態(tài)等待態(tài)就緒態(tài)創(chuàng)建態(tài)就緒態(tài)操作系統(tǒng)準(zhǔn)備好再接納一個(gè)進(jìn)程時(shí)，把一個(gè)進(jìn)程從創(chuàng)建態(tài)變?yōu)榫途w態(tài)。運(yùn)行態(tài)終止態(tài)進(jìn)程已結(jié)束，但尚未撤消，以便其它進(jìn)程去收集該進(jìn)程的有關(guān)信息。192.2.2 進(jìn)程的狀態(tài)(4)進(jìn)程生命期狀態(tài)Linux進(jìn)程狀態(tài)

8、可運(yùn)行狀態(tài)：進(jìn)程正在或準(zhǔn)備在CPU上運(yùn)行的狀態(tài)可中斷的等待狀態(tài)：進(jìn)程睡眠等待系統(tǒng)資源可用或收到一個(gè)信號(hào)后，進(jìn)程被喚醒不可中斷的等待狀態(tài)：進(jìn)程睡眠等待一個(gè)不可被中斷的事件發(fā)生（很少使用）暫停狀態(tài)跟蹤狀態(tài)僵死狀態(tài)：進(jìn)程已終止，等待父進(jìn)程處理死亡狀態(tài)：系統(tǒng)刪除該進(jìn)程進(jìn)程退出狀態(tài)20僵死態(tài)執(zhí)行態(tài)就緒態(tài)調(diào)度被搶先2.2.2 進(jìn)程的狀態(tài)(5)暫停態(tài)創(chuàng)建運(yùn)行狀態(tài)收到暫停信號(hào)收到喚醒信號(hào)等待事件不可中斷等待態(tài)事件發(fā)生可中斷等待態(tài)Linux進(jìn)程狀態(tài)轉(zhuǎn)換圖212.2.3 進(jìn)程的組織(1)線性表方式將所有進(jìn)程的PCB組成一個(gè)數(shù)組，系統(tǒng)通過數(shù)組下標(biāo)訪問每一個(gè)PCB優(yōu)點(diǎn)簡(jiǎn)單，節(jié)省存儲(chǔ)空間缺點(diǎn)系統(tǒng)開銷大，查找一個(gè)指定的P

9、CB較費(fèi)時(shí)間22PCB(0)PCB(1)PCB(2).PCB(n-2) PCB(n-1)PCB集合線性表2.2.3 進(jìn)程的組織(2)鏈接方式將處于同一狀態(tài)的進(jìn)程按照一定方式鏈接成一個(gè)隊(duì)列23就緒隊(duì)列i的頭指針阻塞隊(duì)列l(wèi)的頭指針阻塞隊(duì)列n的頭指針PCBPCBPCBPCBPCBPCBPCB 0PCB 0PCB 0CUPROPCB進(jìn)程隊(duì)列2.2.3 進(jìn)程的組織(3)24就緒隊(duì)列和各種I/O設(shè)備隊(duì)列2.2.3 進(jìn)程的組織(4)25PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB943087901執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針2.2.3 進(jìn)程的組織(5)索引方式26P

10、CB1PCB2PCB3PCB4PCB5PCB6PCB7就緒索引表阻塞索引表執(zhí)行指針就緒表指針阻塞表指針2.2.3 進(jìn)程的組織(6)Linux進(jìn)程鏈表(list_head)所有進(jìn)程鏈表(tasks)可運(yùn)行進(jìn)程鏈表(run_list)子進(jìn)程鏈表(children)兄弟進(jìn)程鏈表(sibling)等待進(jìn)程鏈表互斥等待臨界資源的進(jìn)程非互斥等待的進(jìn)程272.3 進(jìn)程的控制2.3.1 進(jìn)程控制及原語(yǔ)2.3.22.3.32.3.42.3.5創(chuàng)建原語(yǔ)撤銷原語(yǔ)阻塞原語(yǔ)喚醒原語(yǔ)282.3.1 進(jìn)程控制及原語(yǔ)進(jìn)程控制系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間轉(zhuǎn)換等一系列有效管理一般由操作系統(tǒng)

11、內(nèi)核完成 原語(yǔ)某些程序段的執(zhí)行過程是不允許被中斷的，或者說其執(zhí)行過程不可分割。這樣的程序段叫原語(yǔ)292.3.2 創(chuàng)建原語(yǔ)(1)創(chuàng)建進(jìn)程的時(shí)機(jī)為新進(jìn)程分配資源初始化進(jìn)程控制塊將新進(jìn)程插入就緒隊(duì)列30系統(tǒng) 批處理系統(tǒng)中為每個(gè)作業(yè)創(chuàng)建一個(gè)進(jìn)程內(nèi)核 分時(shí)系統(tǒng)中為每個(gè)用戶創(chuàng)建一個(gè)進(jìn)程應(yīng)用程序創(chuàng)建應(yīng)用請(qǐng)求：已存在的進(jìn)程創(chuàng)建子進(jìn)程 創(chuàng)建原語(yǔ)的功能申請(qǐng)空白PCB創(chuàng)建進(jìn)程控制塊2.3.2 創(chuàng)建原語(yǔ)(2)創(chuàng)建進(jìn)程時(shí)需注意的問題資源共享父子進(jìn)程共享資源子進(jìn)程共享部分父進(jìn)程資源父子進(jìn)程不共享資源數(shù)據(jù)父進(jìn)程傳遞給子進(jìn)程初始數(shù)據(jù)地址空間子進(jìn)程復(fù)制父進(jìn)程的地址空間子進(jìn)程新創(chuàng)建自己的地址空間312.3.2 創(chuàng)建原語(yǔ)(3)進(jìn)程

12、執(zhí)行父子進(jìn)程并發(fā)執(zhí)行父進(jìn)程等待至子進(jìn)程執(zhí)行完畢 UNIX的進(jìn)程生成fork()系統(tǒng)調(diào)用創(chuàng)建新進(jìn)程，新進(jìn)程復(fù)制原進(jìn)程的地址空間在系統(tǒng)調(diào)用fork()之后，一個(gè)進(jìn)程會(huì)調(diào)用exec()，用新程序取代進(jìn)程的內(nèi)存空間32332.3.2 創(chuàng)建原語(yǔ)(4)int main()pid_t pid;/* fork another process */pid = fork();if (pid 0) /* error occurred */fprintf(stderr, Fork Failed);exit(-1);else if (pid = 0) /* child process */execlp(/bin/ls,

13、 ls, NULL);else /* parent process */* parent will wait for the child to complete */wait (NULL);printf (Child Complete);exit(0);2.3.2 創(chuàng)建原語(yǔ)(5)34UNIX的進(jìn)程生成2.3.2 創(chuàng)建原語(yǔ)(6)Win32 API創(chuàng)建進(jìn)程#include #include int main()STARTUPINFO si;/for new processPROCESS_INFORMATION pi;/allocate memoryZeroMemory(&si,sizeof

14、(si);si.cb=sizeof(si);ZeroMemory(&pi,sizeof(pi);/create child processesif(!CreateProcess(NULL,/use command lineC:WINDOWSsystem32mspaint.exe,NULL, /dont inherit process handleNULL, /dont inherit thread handle352.3.2 創(chuàng)建原語(yǔ)(7)36FALSE, /disable handle inheritance0, /no creation flagsNULL, /use parent

15、s environment blockNULL, /use parents existing directory&si,&pi) fprintf(stderr,create failed.);return -1;/parent will wait for the child to completeWaitForSingleObject(pi.hProcess,INFINITE);printf(Child Completed);/close handlesCloseHandle(pi.hProcess);CloaseHandle(pi.hThread);2.3.3 撤銷原語(yǔ)(1)

16、撤銷進(jìn)程的時(shí)機(jī)進(jìn)程已完成任務(wù)，正常結(jié)束由于故障不能繼續(xù)執(zhí)行，異常結(jié)束越界錯(cuò)誤、保護(hù)錯(cuò)、非法指令、運(yùn)行超時(shí)、算術(shù)運(yùn)算錯(cuò)、I/O故障外界干預(yù)操作員或操作系統(tǒng)干預(yù)：死鎖父進(jìn)程請(qǐng)求父進(jìn)程終止372.3.3 撤銷原語(yǔ)(2)撤銷原語(yǔ)的功能根據(jù)被終止進(jìn)程標(biāo)識(shí)符查找被撤銷進(jìn)程PCB終止該進(jìn)程，重新調(diào)度終止該進(jìn)程的全部子進(jìn)程回收資源釋放PCB 撤銷進(jìn)程時(shí)需注意的問題是否撤銷該進(jìn)程的子進(jìn)程382.3.4 阻塞原語(yǔ)阻塞進(jìn)程的時(shí)機(jī)處于運(yùn)行狀態(tài)的進(jìn)程等待某一事件發(fā)生等待磁盤數(shù)據(jù)傳輸完成等待其他進(jìn)程發(fā)送信息阻塞原語(yǔ)的功能處于運(yùn)行態(tài)的進(jìn)程中斷CPU，將其運(yùn)行現(xiàn)場(chǎng)保存在其PCB的CPU現(xiàn)場(chǎng)保護(hù)區(qū)將其狀態(tài)臵為阻塞態(tài)，并插入相應(yīng)

17、事件的等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度，選擇一個(gè)就緒進(jìn)程投入運(yùn)行阻塞原語(yǔ)由進(jìn)程自己執(zhí)行392.3.5 喚醒原語(yǔ)(1)喚醒進(jìn)程的時(shí)機(jī)進(jìn)程期待的事件到來時(shí) 喚醒原語(yǔ)的功能期待的事件是等待輸入輸出完成輸入/出完成后，由硬件提出中斷請(qǐng)求，CPU響應(yīng)中斷，暫停當(dāng)前進(jìn)程的執(zhí)行，轉(zhuǎn)去中斷處理，檢查有無等待該輸入/輸出完成的進(jìn)程有則將該進(jìn)程從等待隊(duì)列抽出，并將其由阻塞態(tài)臵為就緒態(tài)，插入就緒隊(duì)列，結(jié)束中斷處理402.3.5 喚醒原語(yǔ)(2)返回被中斷進(jìn)程繼續(xù)執(zhí)行，或者轉(zhuǎn)進(jìn)程調(diào)度，選擇一個(gè)就緒進(jìn)程投入運(yùn)行期待的事件是等待某進(jìn)程發(fā)送消息當(dāng)信息發(fā)送給該等待進(jìn)程時(shí)，由發(fā)送進(jìn)程把該等待進(jìn)程喚醒，并將其由阻塞態(tài)臵為就緒態(tài)，插入就緒隊(duì)列即可

18、412.4 線程的引入與概念2.4.1 線程的引入2.4.22.4.3線程的概念線程的實(shí)現(xiàn)2.4.4 多線程模型2.4.52.4.62.4.7線程庫(kù)線程實(shí)例進(jìn)程與線程的比較422.4.1 線程的引入(1)示例：?jiǎn)尉€程字處理程序假 定 一 個(gè) 用 戶 剛 剛 在 一 個(gè) 800 頁(yè) 的 文 檔的第一頁(yè)上刪掉一條語(yǔ)句 ，接著打算在第 600 頁(yè) 上 修 改 一 個(gè) 錯(cuò) 別 字 。 當(dāng) 用 戶 鍵入 一 條 命 令 通 知 字 處 理 程 序 轉(zhuǎn) 到 第 600頁(yè)時(shí)，字 處 理 程 序 對(duì) 該 文 檔 的 前 600 頁(yè) 重 新 進(jìn)行 格 式 處 理 ， 以 便 確 定 第 600 頁(yè) 的 第 一行

19、應(yīng)該在哪里，此時(shí)計(jì)算機(jī)可能要拖延相當(dāng)一段時(shí)間，才能顯示出第600頁(yè)。432.4.1 線程的引入(2)示例：多線程字處理程序一個(gè)交互線程，一個(gè)格式處理線程442.4.1 線程的引入(3)示例：多線程Web服務(wù)器452.4.1 線程的引入(4)引入進(jìn)程的原因使多個(gè)程序并發(fā)執(zhí)行，提高資源利用率與系統(tǒng)吞吐量 進(jìn)程的特點(diǎn)擁有資源的獨(dú)立單位進(jìn)行獨(dú)立調(diào)度的基本單位 進(jìn)程的局限作為資源的擁有者，在創(chuàng)建、撤銷和切換過程中要付出較大的時(shí)空開銷不能很好地利用多處理器系統(tǒng)462.4.1 線程的引入(5)引入線程的原因在更好地并發(fā)（并行）執(zhí)行的同時(shí)，盡量減少系統(tǒng)的開銷解決方法將擁有資源的基本單位與調(diào)度的基本單位分離線程

20、的優(yōu)點(diǎn)提高響應(yīng)速度資源共享系統(tǒng)開銷降低易于實(shí)現(xiàn)多處理器結(jié)構(gòu)472.4.2 線程的概念(1)線程的概念進(jìn)程內(nèi)的一個(gè)執(zhí)行單元進(jìn)程內(nèi)的一個(gè)可調(diào)度實(shí)體線程是程序（或進(jìn)程）中相對(duì)獨(dú)立的一個(gè)控制流序列線程是執(zhí)行的上下文，其含義是執(zhí)行的現(xiàn)場(chǎng)數(shù)據(jù)和其他調(diào)度所需的信息輕質(zhì)進(jìn)程(Light weight process)重質(zhì)進(jìn)程(Heavy weight process)傳統(tǒng)的進(jìn)程是擁有一個(gè)線程的進(jìn)程482.4.2 線程的概念(2)線程的特性獨(dú)立調(diào)度和分派的基本單位可并發(fā)（并行）執(zhí)行動(dòng)態(tài)性線程的狀態(tài)就緒態(tài)運(yùn)行態(tài)阻塞態(tài)/等待態(tài)結(jié)構(gòu)性（線程控制塊）線程的標(biāo)識(shí)492.4.2 線程的概念(3)線程狀態(tài)程序計(jì)數(shù)器執(zhí)行堆棧寄

21、存器集所有線程具有相同的地址空間（進(jìn)程地址空間），共享進(jìn)程資源地址空間代碼段數(shù)據(jù)段其他OS資源502.4.2 線程的概念(4)51進(jìn)程結(jié)構(gòu)與線程結(jié)構(gòu)2.4.2 線程的概念(5)52單線程進(jìn)程與多線程進(jìn)程2.4.2 線程的概念(6)線程的創(chuàng)建創(chuàng)建進(jìn)程時(shí)，系統(tǒng)同時(shí)為進(jìn)程創(chuàng)建第一個(gè)線程，即“初始化線程”由初始化線程根據(jù)需要再去創(chuàng)建若干個(gè)線程 線程的終止線程完成工作后自愿退出線程在運(yùn)行中出現(xiàn)錯(cuò)誤或由于某種原因而被其它線程強(qiáng)行終止532.4.3 線程的實(shí)現(xiàn)(1)內(nèi)核級(jí)線程所有線程（用戶進(jìn)程中的線程/系統(tǒng)進(jìn)程中的線程）的創(chuàng)建、撤銷、調(diào)度和管理都由OS依靠?jī)?nèi)核負(fù)責(zé)在內(nèi)核空間為每一個(gè)內(nèi)核支持線程設(shè)臵了一個(gè)線程

22、控制塊， 內(nèi)核根據(jù)線程控制塊感知線程的存在，并對(duì)其加以控制優(yōu)點(diǎn)可調(diào)度一個(gè)進(jìn)程中的多個(gè)線程同時(shí)在多個(gè)處理器上并行運(yùn)行，從而提高程序執(zhí)行速度和效率542.4.3 線程的實(shí)現(xiàn)(2)當(dāng)進(jìn)程中的一個(gè)線程被阻塞時(shí)，進(jìn)程中的其他線程仍可以被調(diào)度運(yùn)行具有很小的數(shù)據(jù)結(jié)構(gòu)和堆棧，線程切換較快，開銷較小內(nèi)核過程本身也可以以線程方式實(shí)現(xiàn)缺點(diǎn)同一用戶進(jìn)程中的線程切換經(jīng)歷兩次模式轉(zhuǎn)換用戶態(tài)內(nèi)核態(tài)內(nèi)核態(tài)用戶態(tài)創(chuàng)建和管理的開銷大，速度慢552.4.3 線程的實(shí)現(xiàn)(3)實(shí)現(xiàn)創(chuàng)建進(jìn)程時(shí)分配任務(wù)數(shù)據(jù)區(qū)空間56PTDA進(jìn)程資源TCB # 1TCB # 2TCB # 3TCB#nPTDA進(jìn)程資源TCB # 1TCB # 2TCB #

23、3TCB#nPTDA進(jìn)程資源TCB # 1TCB # 2TCB # 3TCB#n分配回收2.4.3 線程的實(shí)現(xiàn)(4)用戶級(jí)線程由用戶應(yīng)用程序建立的線程，并且由用戶應(yīng)用程序負(fù)責(zé)所有這些用戶級(jí)線程的調(diào)度執(zhí)行和管理工作僅存在于用戶空間，操作系統(tǒng)內(nèi)核完全不知道這些線程的存在優(yōu)點(diǎn)用戶應(yīng)用程序中的線程切換的開銷比內(nèi)核線程切換的開銷小線程庫(kù)的線程調(diào)度算法與操作系統(tǒng)的調(diào)度算法無關(guān)572.4.3 線程的實(shí)現(xiàn)(5)用戶級(jí)線程不要求內(nèi)核支持，可適用于任何操作系統(tǒng)缺點(diǎn)任一線程的阻塞將導(dǎo)致進(jìn)程中所有其他線程被阻塞可能導(dǎo)致線程獨(dú)自壟斷對(duì)處理器的控制，引起進(jìn)程中其他線程得不到運(yùn)行機(jī)會(huì)只能有一個(gè)線程在CPU上運(yùn)行，得不到多機(jī)

24、系統(tǒng)中多處理器的好處5859內(nèi)核用戶空間內(nèi)核空間進(jìn)程表線程表2.4.3 線程的實(shí)現(xiàn)(6)實(shí)現(xiàn)運(yùn)行時(shí)系統(tǒng)進(jìn)程線程運(yùn)行時(shí)系統(tǒng)2.4.3 線程的實(shí)現(xiàn)(7)內(nèi)核控制線程(輕型進(jìn)程LWP)用戶級(jí)線程通過LWP與內(nèi)核通信60CPU任務(wù)1任務(wù)2任務(wù)3用戶級(jí)線程輕型進(jìn)程內(nèi)核線程內(nèi) 核2.4.4 多線程模型(1)一對(duì)一模型每個(gè)用戶級(jí)線程映射一個(gè)內(nèi)核級(jí)線程612.4.4 多線程模型(2)多對(duì)一多個(gè)用戶級(jí)線程映射一個(gè)內(nèi)核級(jí)線程線程管理在用戶空間進(jìn)行622.4.4 多線程模型(3)多對(duì)多多個(gè)用戶級(jí)線程映射多個(gè)內(nèi)核級(jí)線程632.4.5 線程庫(kù)(1)線程庫(kù)為程序員提供創(chuàng)建和管理線程的API 實(shí)現(xiàn)方式在用戶空間提供沒有內(nèi)核

25、支持的庫(kù)所有代碼和數(shù)據(jù)存在于用戶空間用戶空間的本地函數(shù)調(diào)用由操作系統(tǒng)直接支持的內(nèi)核級(jí)的庫(kù)所有代碼和數(shù)據(jù)存在于內(nèi)核空間對(duì)內(nèi)核的系統(tǒng)調(diào)用642.4.5 線程庫(kù)(2)三種主要的線程庫(kù)POSIX Pthread可以提供用戶級(jí)或內(nèi)核級(jí)的線程庫(kù)Win32適用于Windows系統(tǒng)的內(nèi)核級(jí)線程庫(kù)Java通常采用宿主系統(tǒng)上的線程庫(kù)實(shí)現(xiàn) 利用線程庫(kù)創(chuàng)建線程示例：設(shè)計(jì)一個(gè)多線程程序，在獨(dú)立的線程中完成非負(fù)數(shù)整數(shù)的加法功能652.4.5 線程庫(kù)(3)66使用Pthread API的多線程C程序#include #include int sum;/this data is shared by the thread(s)

26、void* runner(void *param);/the threadint main(int argc, char* argv) pthread_t tid;pthread_attr_t_attr;if(argc!=2) fprintf(stderr,usage:a.out n);return -1;if(atoi(argv10) fprintf(stderr,%d must be=0n,atoi(argv1);return -1;672.4.5 線程庫(kù)(4)/get the default attributespthread_attr_init(&attr);/create t

27、he threadpthread_create(&tid,&attr,runner,argv1);/now wait for the thread to exitpthread_join(tid,NULL);printf(sum=%dn,sum);/the thread will begin control in this functionvoid* runner(void* param) int i,upper=atoi(param);sum=0;for(i=1;i=upper;i+)sum+=i;pthread_exit(0);2.4.5 線程庫(kù)(5)68使用Win32 A

28、PI的多線程C程序#include #include DWORD sum; /this data is shared by the thread(s)/the thread runs in this separate functionDWORD WINAPI Summation(LPVOID Param) DWORD Upper=*(DWORD*)Param;for(DWORD i=0;i=Upper;i+)sum+=i;return 0;int main(int argc, char* argv) DWORD ThreadId;HANDLE ThreadHandle;int Param;69

29、2.4.5 線程庫(kù)(6)if(argc!=2) fprintf(stderr,An integer param is requiredn);return -1;Param=atoi(argv1);if(Param=0 is requiredn);return -1;/create the threadThreadHandle=CreateThread(NULL,0,Summation,&Param,0,/default security attributes/default stack size/thread function/parameter to thread function/

30、default creation flags&ThreadId);/returns the thread identifier2.4.5 線程庫(kù)(7)70if(ThreadHandle!=NULL)/now wait for the thread to finishWaitForSingleObject(ThreadHandle,INFINITE);/close the thread handleCloseHandle(ThreadHandle);printf(sum=%dn,sum);2.4.5 線程庫(kù)(8)71非負(fù)整數(shù)累加的Java程序class Sum private int s

31、um;public int getSum() return sum;public void setSum(int value) this.sum=sum;class Summation implements Runnable private int upper;private Sum sumValue;2.4.5 線程庫(kù)(9)72public Summation(int upper,Sum sumValue) this.upper=upper;this.sumValue=sumValue;public void run() int sum=0;for(int i=0;i0) System.er

32、r.println(args0+ must be=0. );else 732.4.5 線程庫(kù)(10)/create the object to be sharedSum sum=new Sum();int upper=Integer.parseInt(args0);Thread thrd=new Thread(new Summation(upper,sum);thrd.start();trythrd.join();System.out.println(The sum of +upper+ is +sum.getSum();catch(interruptedException ie) elseS

33、ystem.err.println(Usage:Summation);2.4.6 線程實(shí)例(1)Windows XP線程Windows XP應(yīng)用程序以獨(dú)立進(jìn)程方式運(yùn)行，每個(gè)進(jìn)程可包括一個(gè)或多個(gè)線程Windows XP實(shí)現(xiàn)了一對(duì)一的映射，每個(gè)用戶線程映射到相關(guān)的內(nèi)核線程Windows XP也提供了對(duì)fiber庫(kù)的支持，該庫(kù)提供了多對(duì)多模型每個(gè)Windows XP線程包括一個(gè)線程ID，用于唯一標(biāo)識(shí)線程742.4.6 線程實(shí)例(2)一組寄存器集合，表示處理器狀態(tài)一個(gè)用戶棧和一個(gè)內(nèi)核棧，分別供線程在用戶模式和內(nèi)核模式下運(yùn)行一個(gè)私有存儲(chǔ)區(qū)域，為各種運(yùn)行時(shí)庫(kù)和動(dòng)態(tài)鏈接庫(kù)使用Windows XP線程的數(shù)據(jù)結(jié)

34、構(gòu)ETHREAD：執(zhí)行線程塊KTHREAD：內(nèi)核線程塊TEB：線程執(zhí)行環(huán)境塊75線程上下文內(nèi)核空間用戶空間2.4.6 線程實(shí)例(3)ETHREAD包括線程進(jìn)程的指針和線程開始控制的子程序的地址，以及相應(yīng)的KTHREAD的指針KTHREAD包括線程的調(diào)度和同步信息，以及內(nèi)核棧（線程在內(nèi)核模式下運(yùn)行時(shí)使用）和TEB的指針TEB包括線程相關(guān)信息、用戶模式棧和用于線程特定數(shù)據(jù)的數(shù)組762.4.6 線程實(shí)例(4)77Windows XP線程的數(shù)據(jù)結(jié)構(gòu)2.4.6 線程實(shí)例(5)Linux系統(tǒng)中不區(qū)分進(jìn)程與線程，對(duì)程序內(nèi)的控制流通常稱為任務(wù)(task)Linux的主進(jìn)程數(shù)據(jù)結(jié)構(gòu)中不包含進(jìn)程的整個(gè)上下文，進(jìn)程

35、的文件系統(tǒng)上下文、文件描述表、信號(hào)處理表和虛擬內(nèi)存上下文保存在獨(dú)立的數(shù)據(jù)結(jié)構(gòu)中 clone()系統(tǒng)調(diào)用的參數(shù)告訴它創(chuàng)建新進(jìn)程時(shí)，哪個(gè)上下文需要復(fù)制，哪個(gè)需要共享未設(shè)臵標(biāo)志時(shí)，不會(huì)共享任何信息，類似于fork系統(tǒng)調(diào)用78標(biāo) 志含 義CLONE_FS共享文件系統(tǒng)信息CLONE_VM共享內(nèi)存空間CLONE_SIGHAND共享信號(hào)處理程序CLONE_FILES共享打開文件集合2.4.6 線程實(shí)例(6)Linux中創(chuàng)建進(jìn)程與線程fork()系統(tǒng)調(diào)用提供復(fù)制進(jìn)程的傳統(tǒng)功能clone()系統(tǒng)調(diào)用提供創(chuàng)建線程的功能通過傳遞一組標(biāo)志，決定在父任務(wù)和子任務(wù)之間發(fā)生多少共享792.4.7 進(jìn)程與線程的比較(1)擁有

36、資源進(jìn)程擁有獨(dú)立的地址空間，若干代碼段和數(shù)據(jù)段，若干打開文件、主存以及至少一個(gè)線程一個(gè)進(jìn)程內(nèi)的多線程共享該進(jìn)程的所有資源，線程自己擁有很少資源 調(diào)度進(jìn)程調(diào)度需進(jìn)行進(jìn)程上下文切換，開銷大同一進(jìn)程內(nèi)的線程切換，僅交換線程擁有的一小部分資源，效率高；不同進(jìn)程的線程切換將引起進(jìn)程調(diào)度802.4.7 進(jìn)程與線程的比較(2)并發(fā)性引入線程后，系統(tǒng)并發(fā)執(zhí)行程度更高；進(jìn)程之間、進(jìn)程內(nèi)的多線程之間可以并發(fā)執(zhí)行 安全性同一進(jìn)程的多個(gè)線程共享進(jìn)程的所有資源，一個(gè)線程可以改變另一個(gè)線程的數(shù)據(jù)，而多進(jìn)程實(shí)現(xiàn)則不會(huì)產(chǎn)生此問題812.5 處理機(jī)的調(diào)度2.5.12.5.22.5.32.5.42.5.52.5.62.5.72.

37、5.82.5.92.5.10基本概念FCFS調(diào)度算法SJF調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級(jí)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法多級(jí)隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法線程調(diào)度操作系統(tǒng)實(shí)例822.5.1 基本概念(1)處理機(jī)調(diào)度級(jí)別高級(jí)調(diào)度（作業(yè)調(diào)度）選擇哪個(gè)作業(yè)進(jìn)入就緒隊(duì)列調(diào)度不頻繁低級(jí)調(diào)度（進(jìn)程調(diào)度）選擇哪個(gè)進(jìn)程可以占有CPU調(diào)度頻繁中級(jí)調(diào)度（交換調(diào)度）進(jìn)程換入換出提高內(nèi)存利用率和系統(tǒng)吞吐量83批處理系統(tǒng)分時(shí)系統(tǒng)就緒阻塞就緒阻塞運(yùn)行后備完成作業(yè)輸出作業(yè)輸入主存2.5.1 基本概念(2)外存交換作業(yè)狀態(tài)及其轉(zhuǎn)換842.5.1 基本概念(3)處理機(jī)調(diào)度的功能記錄系統(tǒng)中各進(jìn)程的執(zhí)行狀況選擇進(jìn)程真正占有CPU進(jìn)

38、行進(jìn)程上下文的切換 進(jìn)程調(diào)度方式非剝奪方式實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，適合于批處理系統(tǒng)剝奪方式優(yōu)先級(jí)/時(shí)間片，分時(shí)系統(tǒng)/實(shí)時(shí)系統(tǒng)852.5.1 基本概念(4)進(jìn)程調(diào)度時(shí)機(jī)現(xiàn)行進(jìn)程完成執(zhí)行或由于某種錯(cuò)誤而中止運(yùn)行正在執(zhí)行的進(jìn)程提出I/O請(qǐng)求，等待I/O完成分時(shí)系統(tǒng)中按照時(shí)間片輪轉(zhuǎn)調(diào)度策略，分配給進(jìn)程的時(shí)間片用完優(yōu)先級(jí)調(diào)度策略中，進(jìn)程有更高優(yōu)先級(jí)進(jìn)程變?yōu)榫途w進(jìn)程執(zhí)行了某種操作原語(yǔ)，如阻塞原語(yǔ)或喚醒原語(yǔ)時(shí)，可能引起進(jìn)程調(diào)度862.5.1 基本概念(5)處理機(jī)調(diào)度準(zhǔn)則CPU利用率高吞吐量高周轉(zhuǎn)時(shí)間/平均周轉(zhuǎn)時(shí)間短等待時(shí)間/平均等待時(shí)間短響應(yīng)時(shí)間短批處理系統(tǒng)：增加系統(tǒng)吞吐量和提高系統(tǒng)資源的利用率分時(shí)系統(tǒng)：保證

39、每個(gè)分時(shí)用戶的響應(yīng)時(shí)間872.5.2 FCFS調(diào)度算法(1)采用非剝奪調(diào)度方式 既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度 示例：3個(gè)進(jìn)程的到達(dá)順序及運(yùn)行時(shí)間為進(jìn)程：P1P2P333等待時(shí)間： P1 = 0; P2 = 24; P3 = 27平均等待時(shí)間： (0 + 24 + 27)/3 = 1788運(yùn)行時(shí)間： 24P1P2P324273002.5.2 FCFS調(diào)度算法(2)若進(jìn)程到達(dá)順序?yàn)镻2 , P3 , P1，則P1P3P20 3 6 30等待時(shí)間： P1 = 6; P2 = 0; P3 = 3平均等待時(shí)間： (6 + 0 + 3)/3 = 3 簡(jiǎn)單，但效率不高 有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作

40、業(yè)（進(jìn)程），容易被大作業(yè)（進(jìn)程）壟斷，使得平均等待時(shí)間很長(zhǎng)892.5.3 SJF調(diào)度算法(1)考慮作業(yè)（進(jìn)程）運(yùn)行時(shí)間 在長(zhǎng)期調(diào)度中頻繁使用 既可采用非剝奪調(diào)度方式，也可采用剝奪調(diào)度方式（Shortest-Remaining-Time-First，SRTF） 示例：4個(gè)進(jìn)程的到達(dá)時(shí)間及運(yùn)行時(shí)間為進(jìn)程P1P2P3P4到達(dá)時(shí)間0.02.04.05.0運(yùn)行時(shí)間7414902.5.3 SJF調(diào)度算法(2)非剝奪方式平均等待時(shí)間 (0 + 6 + 3 + 7)/4 = 4 剝奪方式平均等待時(shí)間 (9 + 1 + 0 +2)/4 =391P1P3P273160P4812P1P2 P342110P457P2

41、P1162.5.3 SJF調(diào)度算法(3)優(yōu)點(diǎn)SJF是一種最優(yōu)算法，它可以獲得最小平均等待時(shí)間，提高系統(tǒng)吞吐量 缺點(diǎn)對(duì)長(zhǎng)作業(yè)不利，容易產(chǎn)生“饑餓”現(xiàn)象未考慮作業(yè)的緊迫程度 困難難以確定進(jìn)程的執(zhí)行時(shí)間922.5.4 高響應(yīng)比優(yōu)先調(diào)度算法(1)優(yōu)點(diǎn)兼顧了運(yùn)行時(shí)間短和等待時(shí)間長(zhǎng)的作業(yè)（結(jié)合FCFS和SJF方法），優(yōu)先運(yùn)行短作業(yè)和等待時(shí)間足夠長(zhǎng)的長(zhǎng)作業(yè) 缺點(diǎn)較復(fù)雜，系統(tǒng)開銷大93作業(yè)等待時(shí)間作業(yè)估計(jì)運(yùn)行時(shí)間作業(yè)等待時(shí)間 作業(yè)估計(jì)運(yùn)行時(shí)間作業(yè)估計(jì)運(yùn)行時(shí)間響應(yīng)比 1 2.5.4 高響應(yīng)比優(yōu)先調(diào)度算法(2)響應(yīng)比計(jì)算若作業(yè)等待時(shí)間相同，則作業(yè)估計(jì)運(yùn)行時(shí)間越短，響應(yīng)比越高，因此有利于短作業(yè)若作業(yè)估計(jì)運(yùn)行時(shí)間相同

42、，則作業(yè)等待時(shí)間越長(zhǎng)，響應(yīng)比越高，此時(shí)算法即FCFS對(duì)長(zhǎng)作業(yè)來說，其響應(yīng)比將隨等待時(shí)間的增加而提高，當(dāng)?shù)却龝r(shí)間足夠長(zhǎng)時(shí)，響應(yīng)比將足夠高， 從而可以獲得處理機(jī)，避免產(chǎn)生“饑餓”現(xiàn)象942.5.5 優(yōu)先級(jí)調(diào)度算法(1)為每個(gè)進(jìn)程設(shè)定一個(gè)優(yōu)先級(jí) 既可采用非剝奪調(diào)度方式(批處理系統(tǒng)) 也可采用剝奪調(diào)度方式（實(shí)時(shí)系統(tǒng)） 優(yōu)先級(jí)設(shè)定進(jìn)程類型：系統(tǒng)進(jìn)程/用戶進(jìn)程進(jìn)程對(duì)資源的需求申請(qǐng)資源較多的進(jìn)程，優(yōu)先級(jí)較低用戶要求 優(yōu)先級(jí)類型952.5.5 優(yōu)先級(jí)調(diào)度算法(2)靜態(tài)優(yōu)先級(jí)進(jìn)程創(chuàng)建時(shí)確定，整個(gè)運(yùn)行期間保持不變不能反映進(jìn)程特點(diǎn)，調(diào)度性能差容易導(dǎo)致“饑餓”，即不能調(diào)度低優(yōu)先級(jí)進(jìn)程優(yōu)先級(jí)與優(yōu)先數(shù)動(dòng)態(tài)優(yōu)先級(jí)隨著進(jìn)程的

43、推進(jìn)或等待時(shí)間的增加而改變962.5.5 優(yōu)先級(jí)調(diào)度算法(3)示例：5個(gè)進(jìn)程的運(yùn)行時(shí)間及優(yōu)先級(jí)如下進(jìn)程運(yùn)行時(shí)間 優(yōu)先級(jí)P1P2P3P4P510121531452P5P3P1P4P20 1 6 16 18 19平均等待時(shí)間： (6+0+16+18+1)/5=8.2972.5.5 優(yōu)先級(jí)調(diào)度算法(4)示例：5個(gè)進(jìn)程的運(yùn)行時(shí)間及優(yōu)先級(jí)如下進(jìn)程到達(dá)時(shí)間 運(yùn)行時(shí)間 優(yōu)先級(jí)P1P2P3P4P50023510121531452P1P3P5P4P20 1 2 3 5 10 16 18 19平均等待時(shí)間 (1+5)+0+14+15+0)/5=798P12.5.6時(shí)間片輪轉(zhuǎn)調(diào)度算法(1)用于分時(shí)系統(tǒng) 采用剝奪調(diào)度

44、方式 時(shí)間片的確定既要保證系統(tǒng)各個(gè)用戶進(jìn)程及時(shí)地得到響應(yīng)，又不要由于時(shí)間片太短而增加調(diào)度的開銷，降低系統(tǒng)的效率992.5.6時(shí)間片輪轉(zhuǎn)調(diào)度算法(2)示例：時(shí)間片為20，4個(gè)進(jìn)程運(yùn)行時(shí)間為進(jìn)程P1P2P3P4運(yùn)行時(shí)間53176824平均等待時(shí)間(57+24)+20+(37+40+17)+(57+40)/4=73100P1P2P3P4P1P3P4P1P3P3020 37 57 77 97 117 121 134 154 1622.5.6時(shí)間片輪轉(zhuǎn)調(diào)度算法(3)周轉(zhuǎn)時(shí)間隨時(shí)間片大小變換1012.5.7 多級(jí)隊(duì)列調(diào)度算法(1)將就緒隊(duì)列分成多個(gè)獨(dú)立隊(duì)列 根據(jù)進(jìn)程的屬性（內(nèi)存大小、進(jìn)程優(yōu)先級(jí)、進(jìn)程類型），一個(gè)進(jìn)程被永久地分配到一個(gè)隊(duì)列 每個(gè)隊(duì)列有自己的調(diào)度算法 隊(duì)列之間進(jìn)行調(diào)度固定優(yōu)先級(jí)搶占調(diào)度1022.5.7 多級(jí)隊(duì)列調(diào)度算法(2)1032.5.8 多級(jí)反饋隊(duì)列調(diào)度算法(1)綜合考慮各種類型進(jìn)程的需要終端型作業(yè)用戶交互性好，響應(yīng)時(shí)間短短批處理作業(yè)用戶周轉(zhuǎn)時(shí)間短，在較短時(shí)間內(nèi)完成長(zhǎng)批處理作業(yè)用戶不會(huì)出現(xiàn)長(zhǎng)期得不到處理的“饑餓”現(xiàn)象 多級(jí)反饋隊(duì)列調(diào)度算法1042.5.8 多級(jí)反饋隊(duì)列調(diào)度算法(2)設(shè)臵多個(gè)就緒隊(duì)列，并