Chapter-02(進(jìn)程與線程)

1、1主要內(nèi)容第2章 進(jìn)程與線程2.1 進(jìn)程2.2 線程2.3 進(jìn)程間通信2.4 調(diào)度2.5 經(jīng)典的IPC問題22.1 進(jìn)程（補(bǔ)充1） 程序 指令或語句序列，體現(xiàn)了某種算法所有程序是順序的 順序程序 計(jì)算機(jī)系統(tǒng)中只有一個(gè)程序在運(yùn)行，該程序獨(dú)占系統(tǒng)中的所有資源，其執(zhí)行不受外界影響 特征：順序性、封閉性、可再現(xiàn)性32.1 進(jìn)程（補(bǔ)充2） 多道程序執(zhí)行系統(tǒng)中程序的執(zhí)行：多道程序執(zhí)行系統(tǒng)中程序的執(zhí)行：同時(shí)處理多個(gè)具有獨(dú)立功能的程序，應(yīng)具有以下特點(diǎn)：同時(shí)處理多個(gè)具有獨(dú)立功能的程序，應(yīng)具有以下特點(diǎn)：獨(dú)立性：多個(gè)程序邏輯獨(dú)立，并可獨(dú)立運(yùn)行獨(dú)立性：多個(gè)程序邏輯獨(dú)立，并可獨(dú)立運(yùn)行隨機(jī)性：多用戶環(huán)境下程序的運(yùn)行是隨機(jī)

2、的隨機(jī)性：多用戶環(huán)境下程序的運(yùn)行是隨機(jī)的資源共享：資源共享： 并發(fā)執(zhí)行的程序：并發(fā)執(zhí)行的程序：并發(fā)：兩個(gè)或多個(gè)事件在并發(fā)：兩個(gè)或多個(gè)事件在同一個(gè)時(shí)間間隔同一個(gè)時(shí)間間隔之內(nèi)同時(shí)發(fā)生之內(nèi)同時(shí)發(fā)生并行：兩個(gè)或多個(gè)事件在并行：兩個(gè)或多個(gè)事件在同一個(gè)時(shí)刻同一個(gè)時(shí)刻同時(shí)發(fā)生同時(shí)發(fā)生特點(diǎn)：隨機(jī)性，失去了程序順序執(zhí)行所具有的封閉性和可再現(xiàn)性特點(diǎn)：隨機(jī)性，失去了程序順序執(zhí)行所具有的封閉性和可再現(xiàn)性4例：有棧例：有棧S, top為棧頂指針，為棧頂指針，getaddr(top)從棧中取內(nèi)存數(shù)據(jù)塊從棧中取內(nèi)存數(shù)據(jù)塊地址，地址，reladdr(bld)將內(nèi)存數(shù)據(jù)塊地址將內(nèi)存數(shù)據(jù)塊地址blk放入放入S中中Procedur

3、e getaddr(top) begin local r r - (top) top - top-1 return(r) endProcedure reladdr(blk) begin top - top+1 (top) - blk endabeftop r=?52.1.2 進(jìn)程的定義：進(jìn)程的定義： 定義：定義：A Procss is just an executing program (Include : PC, R ,variables etc.)或：可以與其他程序并發(fā)執(zhí)行的程序的一次執(zhí)行，是系統(tǒng)或：可以與其他程序并發(fā)執(zhí)行的程序的一次執(zhí)行，是系統(tǒng)資源分配的基本單位資源分配的基本單位 特征：

4、特征： 動(dòng)態(tài)動(dòng)態(tài)并發(fā)并發(fā)獨(dú)立獨(dú)立異步異步結(jié)構(gòu)結(jié)構(gòu)6 進(jìn)程與程序的區(qū)別及聯(lián)系：進(jìn)程與程序的區(qū)別及聯(lián)系：進(jìn)程是動(dòng)態(tài)的，而程序是靜態(tài)的進(jìn)程是動(dòng)態(tài)的，而程序是靜態(tài)的進(jìn)程可以并發(fā)，而程序則沒有進(jìn)程可以并發(fā)，而程序則沒有進(jìn)程是資源競爭的基本單位進(jìn)程是資源競爭的基本單位聯(lián)系：聯(lián)系：一個(gè)程序可以生成多個(gè)不同的進(jìn)程一個(gè)程序可以生成多個(gè)不同的進(jìn)程 進(jìn)程的層次結(jié)構(gòu)：（進(jìn)程樹）進(jìn)程的層次結(jié)構(gòu)：（進(jìn)程樹）系統(tǒng)中除根進(jìn)程外，每個(gè)進(jìn)程都有且只有一個(gè)父進(jìn)程系統(tǒng)中除根進(jìn)程外，每個(gè)進(jìn)程都有且只有一個(gè)父進(jìn)程每個(gè)子進(jìn)程均由它的父進(jìn)程創(chuàng)建每個(gè)子進(jìn)程均由它的父進(jìn)程創(chuàng)建一個(gè)父進(jìn)程可以有多個(gè)子進(jìn)程一個(gè)父進(jìn)程可以有多個(gè)子進(jìn)程72.1 進(jìn)程2.

5、1.1 進(jìn)程模型 含有4道程序的多道程序 4個(gè)獨(dú)立的順序進(jìn)程的概念模型 在任意時(shí)刻僅有一個(gè)程序是活躍的82.1.2 創(chuàng)建進(jìn)程4種主要事件導(dǎo)致進(jìn)程的創(chuàng)建1. 系統(tǒng)初始化2. 執(zhí)行了正在運(yùn)行的進(jìn)程所調(diào)用的進(jìn)程創(chuàng)建系統(tǒng)調(diào)用3. 用戶請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程4. 一個(gè)批處理作業(yè)的初始化92.1.3 進(jìn)程的終止引起進(jìn)程終止的條件：1. 正常退出 (自愿的)2. 錯(cuò)誤退出 (自愿地)3. 嚴(yán)重錯(cuò)誤 (非自愿地)4. 被其他進(jìn)程殺死 (非自愿地)102.1.4 進(jìn)程的層次結(jié)構(gòu) 父進(jìn)程創(chuàng)建一個(gè)子進(jìn)程，子進(jìn)程可以創(chuàng)建屬于自己的更多進(jìn)程 Unix中所有子女和后裔共同組成一個(gè)進(jìn)程組 UNIX 叫 “進(jìn)程組 Windows

6、 沒有進(jìn)程層次的概念 所有的進(jìn)程都是地位相同的112.1.5 進(jìn)程的狀態(tài) (1) 進(jìn)程的狀態(tài) running（運(yùn)行態(tài)） blocked(阻塞態(tài)) ready（就緒態(tài)） 上圖顯示出各狀態(tài)之間的轉(zhuǎn)換1.進(jìn)程為等待輸入而阻塞進(jìn)程為等待輸入而阻塞2.調(diào)度程序選擇另一個(gè)進(jìn)程調(diào)度程序選擇另一個(gè)進(jìn)程3.調(diào)度程序選擇這個(gè)進(jìn)程調(diào)度程序選擇這個(gè)進(jìn)程4.出現(xiàn)有效輸入出現(xiàn)有效輸入122.1.5 進(jìn)程的狀態(tài) (2) 以進(jìn)程構(gòu)造的操作系統(tǒng)最底層 處理中斷, 調(diào)度 在該層之上是順序進(jìn)程132.1.6 進(jìn)程的實(shí)現(xiàn)（補(bǔ)充）進(jìn)程控制塊（用來標(biāo)識(shí)進(jìn)程存在于系統(tǒng)中的唯進(jìn)程控制塊（用來標(biāo)識(shí)進(jìn)程存在于系統(tǒng)中的唯一的實(shí)體，部分或全部常駐內(nèi)

7、存）一的實(shí)體，部分或全部常駐內(nèi)存）程序程序數(shù)據(jù)集數(shù)據(jù)集 ：系統(tǒng)用反映進(jìn)程的動(dòng)態(tài)特征，內(nèi)容包括：系統(tǒng)用反映進(jìn)程的動(dòng)態(tài)特征，內(nèi)容包括：描述信息：進(jìn)程名（標(biāo)識(shí)號(hào)），用戶名（標(biāo)識(shí)號(hào)），家族鏈描述信息：進(jìn)程名（標(biāo)識(shí)號(hào)），用戶名（標(biāo)識(shí)號(hào)），家族鏈控制信息：狀態(tài)，優(yōu)先級(jí)，內(nèi)存始址，計(jì)時(shí)，通信信息控制信息：狀態(tài)，優(yōu)先級(jí)，內(nèi)存始址，計(jì)時(shí)，通信信息資源管理信息：內(nèi)存大小，設(shè)備等資源管理信息：內(nèi)存大小，設(shè)備等現(xiàn)場保護(hù)機(jī)構(gòu)：中設(shè)有現(xiàn)場保護(hù)機(jī)構(gòu)：中設(shè)有142.1.6 進(jìn)程的實(shí)現(xiàn) (1)典型的進(jìn)程表表項(xiàng)中的一些字段進(jìn)程表表項(xiàng)進(jìn)程表表項(xiàng)進(jìn)程控制塊的主要字段進(jìn)程控制塊的主要字段152.1.6 進(jìn)程的實(shí)現(xiàn)(2)當(dāng)中斷發(fā)生后操作

8、系統(tǒng)最底層的工作步驟1.硬件壓入堆棧程序計(jì)數(shù)器等。硬件壓入堆棧程序計(jì)數(shù)器等。2.硬件從中斷向量裝入新的程序計(jì)數(shù)器。硬件從中斷向量裝入新的程序計(jì)數(shù)器。3.匯編語言過程保存寄存器值。匯編語言過程保存寄存器值。4.匯編語言過程設(shè)置新的堆棧。匯編語言過程設(shè)置新的堆棧。5.C中斷服務(wù)例程運(yùn)行（典型的讀和緩沖輸入）。中斷服務(wù)例程運(yùn)行（典型的讀和緩沖輸入）。6.調(diào)度程序決定下一個(gè)將運(yùn)行的進(jìn)程。調(diào)度程序決定下一個(gè)將運(yùn)行的進(jìn)程。7.C過程返回至匯編代碼過程返回至匯編代碼8.匯編語言過程開始運(yùn)行新的當(dāng)前進(jìn)程匯編語言過程開始運(yùn)行新的當(dāng)前進(jìn)程中斷發(fā)生時(shí)，底層處理步驟中斷發(fā)生時(shí)，底層處理步驟16進(jìn)程與程序的區(qū)別（補(bǔ)充）

9、 進(jìn)程更能真實(shí)的描述并發(fā)（程序不能） 進(jìn)程是由程序和數(shù)據(jù)兩部分組成的 程序是靜態(tài)的。進(jìn)程是動(dòng)態(tài)的 進(jìn)程有生命周期，有誕生有消亡，短暫的；而程序是相對(duì)長久的 一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程 進(jìn)程具有創(chuàng)建其他進(jìn)程的功能17 線程 線程是輕量級(jí)的進(jìn)程，它是一個(gè)進(jìn)程內(nèi)的基本調(diào)度單位，有自己的程序計(jì)數(shù)器、寄存器及堆棧。 多線程與多進(jìn)程-多線程系統(tǒng)允許多個(gè)線程共享一個(gè)進(jìn)程的地址空間、打開文件、全局變量等資源。-多進(jìn)程系統(tǒng)允許多個(gè)進(jìn)程共享物理內(nèi)存、磁盤、打印機(jī)等資源。 線程與進(jìn)程 - 進(jìn)程是資源管理的基本單位 -線程是調(diào)度的基本單位 2.2 線程線程2.2.1 線程的概念線程的概念182.2.2 線程模型線程模型

10、(a) 三個(gè)進(jìn)程，每個(gè)進(jìn)程有三個(gè)進(jìn)程，每個(gè)進(jìn)程有1個(gè)線程個(gè)線程(b) 一個(gè)進(jìn)程有一個(gè)進(jìn)程有3個(gè)線程個(gè)線程112319線程的實(shí)現(xiàn)（線程的實(shí)現(xiàn)（TCB） 一個(gè)進(jìn)程中所有線程共享內(nèi)容一個(gè)進(jìn)程中所有線程共享內(nèi)容 每個(gè)線程自己的內(nèi)容每個(gè)線程自己的內(nèi)容20每個(gè)線程有自己的堆棧(kernel&user stack,TCB)212.2.3 引入線程的原因引入線程的原因 偽并行，進(jìn)一步提高并發(fā)度 更小的系統(tǒng)開銷 更高的性能 有利于在多CPU系統(tǒng)中實(shí)現(xiàn)真正的并行222.2.4 在用戶空間實(shí)現(xiàn)線程在用戶空間實(shí)現(xiàn)線程用戶級(jí)線程包用戶級(jí)線程包232.2.5 在內(nèi)核中實(shí)現(xiàn)線程在內(nèi)核中實(shí)現(xiàn)線程內(nèi)核管理的線程包內(nèi)核管

11、理的線程包242.2.6 混合實(shí)現(xiàn)混合實(shí)現(xiàn) 用戶級(jí)線程與內(nèi)核線程復(fù)用用戶級(jí)線程與內(nèi)核線程復(fù)用252.3 進(jìn)程間通信進(jìn)程間通信 并發(fā)進(jìn)程間的相互制約：并發(fā)進(jìn)程間的相互制約：間接制約：諸進(jìn)程對(duì)共享資源的使用通過系統(tǒng)來協(xié)調(diào)，使得間接制約：諸進(jìn)程對(duì)共享資源的使用通過系統(tǒng)來協(xié)調(diào)，使得進(jìn)程間執(zhí)行速度相互影響進(jìn)程間執(zhí)行速度相互影響直接制約：諸進(jìn)程自行使用共享資源或由進(jìn)程合作引起，某直接制約：諸進(jìn)程自行使用共享資源或由進(jìn)程合作引起，某一進(jìn)程直接通過某機(jī)構(gòu)發(fā)消息給其他進(jìn)程，從而直接其他進(jìn)程一進(jìn)程直接通過某機(jī)構(gòu)發(fā)消息給其他進(jìn)程，從而直接其他進(jìn)程的執(zhí)行的執(zhí)行 基本概念：基本概念：臨界資源：一次只允許一個(gè)進(jìn)程使用的資

12、源臨界資源：一次只允許一個(gè)進(jìn)程使用的資源臨界區(qū)：在每個(gè)進(jìn)程中，訪問臨界資源的那部分代碼（那段程臨界區(qū)：在每個(gè)進(jìn)程中，訪問臨界資源的那部分代碼（那段程序）序）2.3.1 進(jìn)程通信進(jìn)程通信262.3.2 互斥互斥 定義定義: 不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，稱為互斥區(qū)，稱為互斥 并發(fā)進(jìn)程互斥執(zhí)行準(zhǔn)則：并發(fā)進(jìn)程互斥執(zhí)行準(zhǔn)則：不假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度不假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度出于臨界區(qū)外的進(jìn)程不能阻止其他進(jìn)程進(jìn)入臨界區(qū)出于臨界區(qū)外的進(jìn)程不能阻止其他進(jìn)程進(jìn)入臨界區(qū)任何時(shí)刻只允許一個(gè)進(jìn)程處于臨界區(qū)中任何時(shí)刻只允許一個(gè)進(jìn)程處于臨界

13、區(qū)中不能使進(jìn)程在臨界區(qū)外永遠(yuǎn)等待不能使進(jìn)程在臨界區(qū)外永遠(yuǎn)等待27 互斥的實(shí)現(xiàn)：互斥的實(shí)現(xiàn)：關(guān)中斷法：每個(gè)進(jìn)程進(jìn)入臨界區(qū)后先關(guān)中斷，離開前開中斷關(guān)中斷法：每個(gè)進(jìn)程進(jìn)入臨界區(qū)后先關(guān)中斷，離開前開中斷缺點(diǎn)：系統(tǒng)可能終止缺點(diǎn)：系統(tǒng)可能終止多多CPU時(shí)，無用時(shí)，無用加鎖法：用鎖變量來表示臨界區(qū)是否可用加鎖法：用鎖變量來表示臨界區(qū)是否可用加鎖后的臨界區(qū)描述如下：lock(keys) /s為臨界區(qū)類名 unlock(keys) /keys為鎖變量，為1表示臨界區(qū) /可用，為0表示臨界區(qū)不能使用28 lock(keys) L: if keys=0 then goto L else keys=0 unlock(

14、keys) keys= 1 PA() L1: lock(keys) unlock(keys) goto L1PB() L2: lock(keys) unlock(keys) goto L2缺點(diǎn)：不斷循環(huán)測試，缺點(diǎn)：不斷循環(huán)測試，CPU費(fèi)時(shí)費(fèi)時(shí)存在不公平現(xiàn)象存在不公平現(xiàn)象29嚴(yán)格的輪轉(zhuǎn)法：用標(biāo)志嚴(yán)格控制輪流使用臨界區(qū)嚴(yán)格的輪轉(zhuǎn)法：用標(biāo)志嚴(yán)格控制輪流使用臨界區(qū)PA()while(true) while(turn!=0); /wait critical_region(); turn=1; noncritical_region(); PB() while(true) while(turn!=1); /

15、wait critical_region(); turn=0; noncritical_region(); 缺點(diǎn)：當(dāng)一個(gè)進(jìn)程比另一進(jìn)程慢很多時(shí)不好缺點(diǎn)：當(dāng)一個(gè)進(jìn)程比另一進(jìn)程慢很多時(shí)不好30TSL指令指令用用TSL指令進(jìn)入和離開臨界區(qū)指令進(jìn)入和離開臨界區(qū)31 信號(hào)量法：信號(hào)量法：信號(hào)量：是中表示資源的物理實(shí)體，是一個(gè)與隊(duì)列相關(guān)的信號(hào)量：是中表示資源的物理實(shí)體，是一個(gè)與隊(duì)列相關(guān)的整型變量，其值僅由整型變量，其值僅由down，up原語改變原語改變信號(hào)量的表示意義：信號(hào)量的表示意義：設(shè)設(shè)sem為信號(hào)量，則：為信號(hào)量，則：當(dāng)當(dāng)sem=0時(shí)，表示可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)時(shí)，表示可供并發(fā)進(jìn)程使用的資源實(shí)

16、體數(shù) 當(dāng)當(dāng)sem =0調(diào)用進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度返回入口 s=s+1 s=0喚醒等待隊(duì)列中的一個(gè)進(jìn)程返回或轉(zhuǎn)進(jìn)程調(diào)度返回down原語原語up原語原語YYNN33用用down，up原語實(shí)現(xiàn)互斥：原語實(shí)現(xiàn)互斥：A： down(sem) up(sem) B： down(sem) up(sem) 設(shè)一個(gè)互斥的信號(hào)量設(shè)一個(gè)互斥的信號(hào)量sem描述：描述：S為臨界區(qū)的類名為臨界區(qū)的類名34管程管程一種更為高級(jí)的同步原語，更便于使用，管程的互斥由編譯一種更為高級(jí)的同步原語，更便于使用，管程的互斥由編譯 器負(fù)責(zé)，使用者只需將所有臨界區(qū)轉(zhuǎn)換為管程即可。器負(fù)責(zé)，使用者只需將所有臨界區(qū)轉(zhuǎn)換為管程即可。一個(gè)管程是由過

17、程、條件變量及數(shù)據(jù)結(jié)構(gòu)等組成的特殊模塊一個(gè)管程是由過程、條件變量及數(shù)據(jù)結(jié)構(gòu)等組成的特殊模塊 或軟件包。進(jìn)程僅能通過管程訪問其中的數(shù)據(jù)結(jié)構(gòu)?；蜍浖＿M(jìn)程僅能通過管程訪問其中的數(shù)據(jù)結(jié)構(gòu)。 管程的特性：任一時(shí)刻管程中只能有一個(gè)活躍進(jìn)程。管程的特性：任一時(shí)刻管程中只能有一個(gè)活躍進(jìn)程。352.3.3 進(jìn)程同步進(jìn)程同步例：設(shè)有計(jì)算進(jìn)程及打印進(jìn)程通過共用一個(gè)例：設(shè)有計(jì)算進(jìn)程及打印進(jìn)程通過共用一個(gè)buf緩沖區(qū)進(jìn)行工作，緩沖區(qū)進(jìn)行工作，如兩進(jìn)程獨(dú)立工作，則過程可描述如下：如兩進(jìn)程獨(dú)立工作，則過程可描述如下：Pc: . A: local Buf repeat buf - Buf until Buf = null

18、 compute Buf - result goto A .Pp: . B: local Pri repeat Pri - buf until Pri = null print buf - null goto B .假定對(duì)假定對(duì)buf已采取的互斥措施已采取的互斥措施36 定義：定義：異步環(huán)境下，一組并發(fā)進(jìn)程因直接制約而相互發(fā)送消息，異步環(huán)境下，一組并發(fā)進(jìn)程因直接制約而相互發(fā)送消息，相互合作，相互等待，使各進(jìn)程按一定速度執(zhí)行的過程相互合作，相互等待，使各進(jìn)程按一定速度執(zhí)行的過程 同步的實(shí)現(xiàn)：同步的實(shí)現(xiàn)： 消息名法：消息名法：為同步進(jìn)程間發(fā)送的事件或消息賦予一個(gè)唯一的消息名，用：為同步進(jìn)程間發(fā)送的

19、事件或消息賦予一個(gè)唯一的消息名，用：wait(表示進(jìn)程等待合作進(jìn)程發(fā)來的消息表示進(jìn)程等待合作進(jìn)程發(fā)來的消息) signal(表示向合作進(jìn)程發(fā)送消息表示向合作進(jìn)程發(fā)送消息)則上例表示的同步關(guān)系如下：則上例表示的同步關(guān)系如下：設(shè)消息名設(shè)消息名Bufempty表示表示Buf為空，為空，Buffull表示表示Buf滿滿初始化：初始化：Bufempty=true, Buffull=false37描述：描述：Pc: A: wait(Bufempty) caculate Buf - result Bufempty - false signal(Buffull) Goto APp: B: wait(Buffu

20、ll) print Buf - null Buffull - false signal(Bufempty) Goto B38信號(hào)量法：信號(hào)量法：此處信號(hào)量只與制約及被制約進(jìn)程有關(guān)，故為私有的信號(hào)量此處信號(hào)量只與制約及被制約進(jìn)程有關(guān)，故為私有的信號(hào)量同例：同例：設(shè)設(shè)SA=0表示表示Buf中無可供打印的計(jì)算結(jié)果中無可供打印的計(jì)算結(jié)果SB=0表示表示Buf空，計(jì)算結(jié)果可放入空，計(jì)算結(jié)果可放入BufPcPp39Pc: A: caculate next number Buf - result count=count-1 V(SA) P(SB) if count=0 then destroy(Pc) el

21、se goto APp: B: P(SA) print 0) 對(duì)享受服務(wù)隊(duì)列：對(duì)享受服務(wù)隊(duì)列：b * t (ab0)新建就緒隊(duì)列進(jìn)程轉(zhuǎn)入享受服務(wù)隊(duì)列的時(shí)機(jī)：新建就緒隊(duì)列進(jìn)程轉(zhuǎn)入享受服務(wù)隊(duì)列的時(shí)機(jī)：就緒隊(duì)列的第一個(gè)進(jìn)程的優(yōu)先級(jí)（就緒隊(duì)列的第一個(gè)進(jìn)程的優(yōu)先級(jí)（a*(t-t1)）享受服務(wù)隊(duì)）享受服務(wù)隊(duì)列最后一個(gè)進(jìn)程的優(yōu)先級(jí)（列最后一個(gè)進(jìn)程的優(yōu)先級(jí)（b*t）時(shí)）時(shí)當(dāng)享受服務(wù)隊(duì)列為空時(shí)，新建就緒隊(duì)列頭一進(jìn)程可轉(zhuǎn)入享受服當(dāng)享受服務(wù)隊(duì)列為空時(shí)，新建就緒隊(duì)列頭一進(jìn)程可轉(zhuǎn)入享受服務(wù)隊(duì)列務(wù)隊(duì)列注：注：ab0 否則：否則：ba0，成為，成為 ab=0，成為，成為62例：有個(gè)進(jìn)程，它們的周期時(shí)值及優(yōu)先級(jí)如下表：周期性

22、優(yōu)先數(shù)進(jìn)入時(shí)刻）在非剝奪方式下，求它們的調(diào)度序列，平均等待時(shí)間，平均周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間）在可剝奪方式下，設(shè)優(yōu)先級(jí)按如下規(guī)律變化：連續(xù)執(zhí)行10ms以上后優(yōu)先數(shù)加，就緒隊(duì)列中的進(jìn)程每40ms優(yōu)先數(shù)減；則求它們的調(diào)度序列，平均等待時(shí)間，平均周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間63 多隊(duì)列輪轉(zhuǎn)法：多隊(duì)列輪轉(zhuǎn)法：進(jìn)程按不同的優(yōu)先級(jí)進(jìn)入不同的隊(duì)列，每個(gè)隊(duì)列又采用不同的進(jìn)程按不同的優(yōu)先級(jí)進(jìn)入不同的隊(duì)列，每個(gè)隊(duì)列又采用不同的算法，如圖所示：算法，如圖所示：cpu1cpu2cpun完成完成完成完成完成完成（時(shí)間片）（時(shí)間片）（時(shí)間片）（時(shí)間片）RR（時(shí)間片（時(shí)間片n）時(shí)間片到（剝奪）時(shí)間片到（剝奪）時(shí)間片到（剝奪

23、）時(shí)間片到（剝奪） 注：注：n642.4.6 實(shí)時(shí)系統(tǒng)調(diào)度方法：實(shí)時(shí)系統(tǒng)調(diào)度方法： 實(shí)時(shí)系統(tǒng)處理的外部事件：實(shí)時(shí)系統(tǒng)處理的外部事件：硬實(shí)時(shí)任務(wù)：系統(tǒng)必須完全滿足任務(wù)的時(shí)限要求硬實(shí)時(shí)任務(wù)：系統(tǒng)必須完全滿足任務(wù)的時(shí)限要求軟實(shí)時(shí)任務(wù)：允許系統(tǒng)對(duì)任務(wù)的時(shí)限要求有一定的延遲軟實(shí)時(shí)任務(wù)：允許系統(tǒng)對(duì)任務(wù)的時(shí)限要求有一定的延遲 實(shí)時(shí)操作系統(tǒng)的功能實(shí)時(shí)操作系統(tǒng)的功能:快速的進(jìn)程或線程切換快速的進(jìn)程或線程切換快速的外部中斷響應(yīng)快速的外部中斷響應(yīng)基于優(yōu)先級(jí)的隨時(shí)強(qiáng)占式調(diào)度策略基于優(yōu)先級(jí)的隨時(shí)強(qiáng)占式調(diào)度策略 65 實(shí)時(shí)操作系統(tǒng)的調(diào)度算法：實(shí)時(shí)操作系統(tǒng)的調(diào)度算法：時(shí)限調(diào)度算法：時(shí)限調(diào)度算法：選擇時(shí)限要求最近的任務(wù)優(yōu)先占

24、有處理機(jī)，它是搶先式選擇時(shí)限要求最近的任務(wù)優(yōu)先占有處理機(jī)，它是搶先式的，即將新任務(wù)的時(shí)限與當(dāng)前任務(wù)的時(shí)限進(jìn)行比較，選擇時(shí)的，即將新任務(wù)的時(shí)限與當(dāng)前任務(wù)的時(shí)限進(jìn)行比較，選擇時(shí)限最近的執(zhí)行限最近的執(zhí)行（時(shí)限可以是處理開始時(shí)限或處理結(jié)束時(shí)限）（時(shí)限可以是處理開始時(shí)限或處理結(jié)束時(shí)限）頻率單調(diào)調(diào)度算法：頻率單調(diào)調(diào)度算法：周期長的任務(wù)優(yōu)先級(jí)越低周期長的任務(wù)優(yōu)先級(jí)越低（適用于多周期性實(shí)時(shí)任務(wù)）（適用于多周期性實(shí)時(shí)任務(wù)）1/n662.4.7 線程調(diào)度線程調(diào)度用戶級(jí)線程的可能調(diào)度用戶級(jí)線程的可能調(diào)度67內(nèi)核級(jí)線程的可能調(diào)度內(nèi)核級(jí)線程的可能調(diào)度682.5 經(jīng)典的進(jìn)程間通信問題經(jīng)典的進(jìn)程間通信問題2.5.1 生產(chǎn)者

25、生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題P1P2Pm12nC1C2C3有界緩沖區(qū)生產(chǎn)者消費(fèi)者之間滿足的條件：生產(chǎn)者消費(fèi)者之間滿足的條件：消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的有界緩沖區(qū)是臨界資源有界緩沖區(qū)是臨界資源69702.5.2 哲學(xué)家就餐問題哲學(xué)家就餐問題 哲學(xué)家的活動(dòng)：吃飯/思考 吃飯需要2把叉子 一次只拿一把? 給出描述哲學(xué)家行為的、不會(huì)死鎖的程序結(jié)構(gòu)* It is useful for modeling processes that are competing for exclusive acces