第05講_進(jìn)程調(diào)度

1、1第第 五五 講講清華大學(xué)軟件學(xué)院清華大學(xué)軟件學(xué)院22.6 進(jìn)程調(diào)度進(jìn)程調(diào)度在多道系統(tǒng)當(dāng)中，往往有多個進(jìn)程同時在內(nèi)存中在多道系統(tǒng)當(dāng)中，往往有多個進(jìn)程同時在內(nèi)存中運(yùn)行。在任何時刻，一個進(jìn)程只可能是以下三種運(yùn)行。在任何時刻，一個進(jìn)程只可能是以下三種狀態(tài)之一：狀態(tài)之一：v 運(yùn)行狀態(tài)：該進(jìn)程正在運(yùn)行狀態(tài)：該進(jìn)程正在CPU上運(yùn)行，每個上運(yùn)行，每個CPU 上最多只能有一個進(jìn)程在運(yùn)行；上最多只能有一個進(jìn)程在運(yùn)行；v 就緒狀態(tài)：進(jìn)程已經(jīng)就緒，隨時可以運(yùn)行；就緒狀態(tài)：進(jìn)程已經(jīng)就緒，隨時可以運(yùn)行；v 阻塞狀態(tài)：如在某個信號量上被阻塞，等待阻塞狀態(tài)：如在某個信號量上被阻塞，等待I/O與此相對應(yīng)，操作系統(tǒng)會維護(hù)相應(yīng)的

2、狀態(tài)隊(duì)列。與此相對應(yīng)，操作系統(tǒng)會維護(hù)相應(yīng)的狀態(tài)隊(duì)列。3就緒隊(duì)列和各種就緒隊(duì)列和各種I/O設(shè)備隊(duì)列設(shè)備隊(duì)列（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）選擇誰去運(yùn)行？選擇誰去運(yùn)行？4 在操作系統(tǒng)中，負(fù)責(zé)去做這個選擇的那在操作系統(tǒng)中，負(fù)責(zé)去做這個選擇的那 部分程序，稱為部分程序，稱為調(diào)度程序調(diào)度程序(scheduler)； 調(diào)度程序在決策過程中所采用的算法，調(diào)度程序在決策過程中所采用的算法， 稱為是稱為是調(diào)度算法調(diào)度算法； 調(diào)度程序是調(diào)度程序是CPU資源的管理者；資源的管理者； 調(diào)度的對象是進(jìn)程，也可以是

3、線程，大調(diào)度的對象是進(jìn)程，也可以是線程，大 多數(shù)的調(diào)度問題對兩者都是適用的。多數(shù)的調(diào)度問題對兩者都是適用的。52.6.1 關(guān)于調(diào)度的若干問題關(guān)于調(diào)度的若干問題1. 歷史背景q 在早期的簡單批處理系統(tǒng)當(dāng)中，調(diào)度算法很簡在早期的簡單批處理系統(tǒng)當(dāng)中，調(diào)度算法很簡 單：選擇磁帶上的下一個作業(yè)運(yùn)行；單：選擇磁帶上的下一個作業(yè)運(yùn)行；q 隨著分時系統(tǒng)的出現(xiàn)，同時有多個用戶在等待隨著分時系統(tǒng)的出現(xiàn)，同時有多個用戶在等待 服務(wù)，使得調(diào)度算法變得越來越復(fù)雜。有些大服務(wù)，使得調(diào)度算法變得越來越復(fù)雜。有些大 型機(jī)系統(tǒng)還把批處理與分時結(jié)合在一起，更增型機(jī)系統(tǒng)還把批處理與分時結(jié)合在一起，更增 大了難度。由于當(dāng)時的大了難度

4、。由于當(dāng)時的CPU時間是一種稀缺資時間是一種稀缺資 源，因此調(diào)度算法的好壞將直接影響到系統(tǒng)的源，因此調(diào)度算法的好壞將直接影響到系統(tǒng)的 性能和用戶的滿意度，算法的設(shè)計很受重視。性能和用戶的滿意度，算法的設(shè)計很受重視。6q 隨著個人計算機(jī)時代的到來，形勢發(fā)生了變化。隨著個人計算機(jī)時代的到來，形勢發(fā)生了變化。 首先，在首先，在PC上通常只有一個進(jìn)程在活動，這樣，上通常只有一個進(jìn)程在活動，這樣， 調(diào)度程序無事可做。其次，計算機(jī)變得越來越快調(diào)度程序無事可做。其次，計算機(jī)變得越來越快, CPU已不是稀缺資源了，哪個程序先運(yùn)行或運(yùn)行已不是稀缺資源了，哪個程序先運(yùn)行或運(yùn)行, 已經(jīng)不重要了。因此，調(diào)度算法的作用

5、已經(jīng)顯得已經(jīng)不重要了。因此，調(diào)度算法的作用已經(jīng)顯得 微不足道了。微不足道了。q 不過，對于那些高端聯(lián)網(wǎng)工作站和服務(wù)器而言，不過，對于那些高端聯(lián)網(wǎng)工作站和服務(wù)器而言， 多個進(jìn)程需要同時競爭多個進(jìn)程需要同時競爭CPU的使用權(quán)，因此調(diào)度的使用權(quán)，因此調(diào)度 問題又出現(xiàn)了。首先，調(diào)度程序要選擇合適的進(jìn)問題又出現(xiàn)了。首先，調(diào)度程序要選擇合適的進(jìn) 程去運(yùn)行，因?yàn)閷τ诓煌倪M(jìn)程，用戶期望的響程去運(yùn)行，因?yàn)閷τ诓煌倪M(jìn)程，用戶期望的響 應(yīng)時間和要求是不同的；其次，調(diào)度程序要注意應(yīng)時間和要求是不同的；其次，調(diào)度程序要注意 CPU的使用效率，因?yàn)檫M(jìn)程切換的開銷很大。的使用效率，因?yàn)檫M(jìn)程切換的開銷很大。72. 進(jìn)程的

6、行為 CPU繁忙（繁忙（CPU-bound）的進(jìn)程：大部分時間的進(jìn)程：大部分時間 處于運(yùn)行和就緒狀態(tài)；處于運(yùn)行和就緒狀態(tài)； I/O繁忙（繁忙（I/O-bound）的進(jìn)程：大部分時間處的進(jìn)程：大部分時間處 于阻塞狀態(tài)。于阻塞狀態(tài)。8（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）CPU繁忙與繁忙與I/O繁忙繁忙CPU繁忙繁忙I/O繁忙繁忙9 內(nèi)部因素：進(jìn)程自身的功能決定了它的各種工內(nèi)部因素：進(jìn)程自身的功能決定了它的各種工作量。例如，矩陣相乘進(jìn)程的計算量大，文件作量。例如，矩陣相乘進(jìn)程的計算量大，文件管理進(jìn)程的管理進(jìn)程的I/O需

7、求很大；需求很大； 外部因素：計算機(jī)系統(tǒng)的運(yùn)行速度決定了完成外部因素：計算機(jī)系統(tǒng)的運(yùn)行速度決定了完成這些工作量所需要的時間長短。工作量和工作這些工作量所需要的時間長短。工作量和工作時間是兩回事，判斷一個進(jìn)程是屬于時間是兩回事，判斷一個進(jìn)程是屬于CPU繁忙繁忙還是屬于輸入輸出繁忙，主要看它的計算時間還是屬于輸入輸出繁忙，主要看它的計算時間和輸入輸出時間；和輸入輸出時間； I/O設(shè)備的運(yùn)行速度較慢，設(shè)備的運(yùn)行速度較慢，CPU的運(yùn)行速度較的運(yùn)行速度較快，而且更新?lián)Q代的速度快，將來進(jìn)程都趨向快，而且更新?lián)Q代的速度快，將來進(jìn)程都趨向于于I/O繁忙。繁忙。CPU繁忙還是繁忙還是I/O繁忙？繁忙？10 VC

8、D播放軟件；播放軟件； WORD文字編輯器；文字編輯器； 磁盤碎片整理工具磁盤碎片整理工具defrag。CPU繁忙還是繁忙還是I/O繁忙？（續(xù)）繁忙？（續(xù)）113. 何時調(diào)度？1. 當(dāng)一個新的進(jìn)程被創(chuàng)建時，是執(zhí)行新進(jìn)程還當(dāng)一個新的進(jìn)程被創(chuàng)建時，是執(zhí)行新進(jìn)程還是繼續(xù)執(zhí)行父進(jìn)程？是繼續(xù)執(zhí)行父進(jìn)程？2. 當(dāng)一個進(jìn)程運(yùn)行完畢時；當(dāng)一個進(jìn)程運(yùn)行完畢時；3. 當(dāng)一個進(jìn)程由于當(dāng)一個進(jìn)程由于I/O、信號量或其他的某個原、信號量或其他的某個原因被阻塞時；因被阻塞時；4. 當(dāng)一個當(dāng)一個I/O中斷發(fā)生時，表明某個中斷發(fā)生時，表明某個I/O操作已經(jīng)操作已經(jīng)完成，而等待該完成，而等待該I/O操作的進(jìn)程轉(zhuǎn)入就緒狀態(tài)；操作

9、的進(jìn)程轉(zhuǎn)入就緒狀態(tài)；5. 在分時系統(tǒng)中，當(dāng)一個時鐘中斷發(fā)生時。在分時系統(tǒng)中，當(dāng)一個時鐘中斷發(fā)生時。12不可搶占調(diào)度方式不可搶占調(diào)度方式：一個進(jìn)程若被選中，就：一個進(jìn)程若被選中，就一直運(yùn)行下去，直到它被阻塞（一直運(yùn)行下去，直到它被阻塞（I/O，或正在，或正在等待其他的進(jìn)程），或主動地交出等待其他的進(jìn)程），或主動地交出CPU。以。以上的情形上的情形13均可發(fā)生調(diào)度；均可發(fā)生調(diào)度；可搶占調(diào)度方式可搶占調(diào)度方式：當(dāng)一個進(jìn)程在運(yùn)行時，調(diào)：當(dāng)一個進(jìn)程在運(yùn)行時，調(diào)度程序可以打斷它。以上的情形度程序可以打斷它。以上的情形15均可發(fā)均可發(fā)生調(diào)度，另外，在其他的一些情形下，如就生調(diào)度，另外，在其他的一些情形下，如

10、就緒隊(duì)列中有進(jìn)程的優(yōu)先級高于當(dāng)前運(yùn)行進(jìn)程緒隊(duì)列中有進(jìn)程的優(yōu)先級高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級，也可能立即進(jìn)行調(diào)度。的優(yōu)先級，也可能立即進(jìn)行調(diào)度。兩種調(diào)度方式兩種調(diào)度方式134. 調(diào)度算法的類別不同的不同的OS有不同的目標(biāo)，對調(diào)度程序有不同的有不同的目標(biāo)，對調(diào)度程序有不同的要求，因此需要不同類型的調(diào)度算法。要求，因此需要不同類型的調(diào)度算法。批處理系統(tǒng)：無須及時的用戶響應(yīng)，采用不批處理系統(tǒng)：無須及時的用戶響應(yīng)，采用不可搶占的調(diào)度方式，或時間間隔很長的可搶可搶占的調(diào)度方式，或時間間隔很長的可搶占調(diào)度方式，從而允許進(jìn)程能長時間運(yùn)行，占調(diào)度方式，從而允許進(jìn)程能長時間運(yùn)行，減少進(jìn)程的切換次數(shù)，提高系統(tǒng)的性能；減

11、少進(jìn)程的切換次數(shù)，提高系統(tǒng)的性能；交互式系統(tǒng)：及時的用戶響應(yīng)非常重要，必交互式系統(tǒng)：及時的用戶響應(yīng)非常重要，必須采用可搶占的調(diào)度方式。以防單個進(jìn)程占須采用可搶占的調(diào)度方式。以防單個進(jìn)程占用太多用太多CPU時間，影響到其他進(jìn)程的運(yùn)行。時間，影響到其他進(jìn)程的運(yùn)行。實(shí)時系統(tǒng)：對響應(yīng)時間要求苛刻，每個進(jìn)程實(shí)時系統(tǒng)：對響應(yīng)時間要求苛刻，每個進(jìn)程運(yùn)行時間很短，可采用可搶占的調(diào)度方式。運(yùn)行時間很短，可采用可搶占的調(diào)度方式。145. 調(diào)度算法的目標(biāo)算法調(diào)度的目標(biāo)是多元的，有些是可以共存的，算法調(diào)度的目標(biāo)是多元的，有些是可以共存的，也有些是相互牽制的，對于一個實(shí)際的調(diào)度算法也有些是相互牽制的，對于一個實(shí)際的調(diào)度

12、算法來說，有一個綜合權(quán)衡的過程。來說，有一個綜合權(quán)衡的過程。所有系統(tǒng)普遍適用的目標(biāo)：所有系統(tǒng)普遍適用的目標(biāo)： 公平：大致相當(dāng)?shù)膬蓚€進(jìn)程所得到的公平：大致相當(dāng)?shù)膬蓚€進(jìn)程所得到的CPU時間時間 也應(yīng)是大致相同的；也應(yīng)是大致相同的； 對已制訂的調(diào)度策略必須能貫徹執(zhí)行；對已制訂的調(diào)度策略必須能貫徹執(zhí)行； 均衡：盡可能使整個系統(tǒng)的各部分都忙起來，均衡：盡可能使整個系統(tǒng)的各部分都忙起來， 提高系統(tǒng)資源的使用效率。提高系統(tǒng)資源的使用效率。15批處理系統(tǒng)中調(diào)度算法的評價指標(biāo)：批處理系統(tǒng)中調(diào)度算法的評價指標(biāo)： 吞吐量吞吐量（Throughput）：單位時間內(nèi)所完成的）：單位時間內(nèi)所完成的 作業(yè)數(shù)，與作業(yè)本身特性

13、和調(diào)度算法有關(guān)；作業(yè)數(shù)，與作業(yè)本身特性和調(diào)度算法有關(guān)； 周轉(zhuǎn)時間周轉(zhuǎn)時間（Turnaround time）：一個批處理作）：一個批處理作 業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間。業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間。 包括：在收容隊(duì)列中等待，包括：在收容隊(duì)列中等待，CPU上執(zhí)行，就緒上執(zhí)行，就緒 隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待；隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待；C 平均周轉(zhuǎn)時間：一批作業(yè)的周轉(zhuǎn)時間的平均值；平均周轉(zhuǎn)時間：一批作業(yè)的周轉(zhuǎn)時間的平均值；C 平均帶權(quán)周轉(zhuǎn)時間：權(quán)值是實(shí)際執(zhí)行時間的倒數(shù)平均帶權(quán)周轉(zhuǎn)時間：權(quán)值是實(shí)際執(zhí)行時間的倒數(shù); CPU的利用率的利用率：大中型主機(jī)的：大中型主機(jī)

14、的CPU較貴，所以較貴，所以 讓它時刻不停地轉(zhuǎn)著。讓它時刻不停地轉(zhuǎn)著。16周轉(zhuǎn)時間：周轉(zhuǎn)時間：iiiSET（Ei表示作業(yè)表示作業(yè)i完成時間，完成時間， Si表示作業(yè)表示作業(yè)i提交時間）提交時間）平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：NiiTNT11(N表示作業(yè)的個數(shù)表示作業(yè)的個數(shù))平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：NiiirTNW11(ri表示作業(yè)表示作業(yè)i的實(shí)際執(zhí)行時間的實(shí)際執(zhí)行時間)17交換式系統(tǒng)中調(diào)度算法的評價指標(biāo)：交換式系統(tǒng)中調(diào)度算法的評價指標(biāo)： 響應(yīng)時間：用戶輸入一個請求（如擊鍵）到系統(tǒng)響應(yīng)時間：用戶輸入一個請求（如擊鍵）到系統(tǒng) 給出首次響應(yīng)（如屏幕顯示）的時間。響應(yīng)時間給出首次響應(yīng)（如屏幕

15、顯示）的時間。響應(yīng)時間 越短越好，優(yōu)先考慮交互式進(jìn)程；越短越好，優(yōu)先考慮交互式進(jìn)程； 相稱性：滿足用戶對程序運(yùn)行時間的期望值。相稱性：滿足用戶對程序運(yùn)行時間的期望值。實(shí)時系統(tǒng)中調(diào)度算法的評價指標(biāo)：實(shí)時系統(tǒng)中調(diào)度算法的評價指標(biāo)： 實(shí)時響應(yīng)：必須嚴(yán)格地遵守時間期限；實(shí)時響應(yīng)：必須嚴(yán)格地遵守時間期限； 可預(yù)測性：在實(shí)時多媒體系統(tǒng)中，信號的播放必可預(yù)測性：在實(shí)時多媒體系統(tǒng)中，信號的播放必 須連貫，不能時斷時續(xù)。須連貫，不能時斷時續(xù)。182.6.2 批處理系統(tǒng)中的調(diào)度算法批處理系統(tǒng)中的調(diào)度算法1. 先來先服務(wù) 先來先服務(wù)先來先服務(wù)（First Come First Served，F(xiàn)CFS； First

16、In First Out，F(xiàn)IFO）：按照作業(yè)到達(dá)的）：按照作業(yè)到達(dá)的 先后次序進(jìn)行調(diào)度；先后次序進(jìn)行調(diào)度； 不可搶占方式：當(dāng)前進(jìn)程占用不可搶占方式：當(dāng)前進(jìn)程占用CPU，直到執(zhí)行，直到執(zhí)行 完或被阻塞，才讓出完或被阻塞，才讓出CPU給另外一個進(jìn)程；給另外一個進(jìn)程； 在進(jìn)程被喚醒后（如在進(jìn)程被喚醒后（如I/O完成），并不立即恢復(fù)完成），并不立即恢復(fù) 執(zhí)行，而是放在就緒隊(duì)列的末尾；執(zhí)行，而是放在就緒隊(duì)列的末尾； 優(yōu)點(diǎn)：簡單、公平，易于理解也易于實(shí)現(xiàn)。優(yōu)點(diǎn)：簡單、公平，易于理解也易于實(shí)現(xiàn)。 現(xiàn)實(shí)生活中應(yīng)用廣泛：排隊(duì)。現(xiàn)實(shí)生活中應(yīng)用廣泛：排隊(duì)。19問題問題1. 平均周轉(zhuǎn)時間取決于各作業(yè)到達(dá)的順序，若平

17、均周轉(zhuǎn)時間取決于各作業(yè)到達(dá)的順序，若短作業(yè)位于長作業(yè)之后，將增大平均周轉(zhuǎn)時間。短作業(yè)位于長作業(yè)之后，將增大平均周轉(zhuǎn)時間。例如，三個作業(yè)例如，三個作業(yè)A、B、C的運(yùn)行時間為的運(yùn)行時間為24、3、3時間時間 24 27 30ABC平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間(24+27+30)/327平均等待時間平均等待時間(0+24+27)/317時間時間 3 6 30ABC平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間(3+6+30)/313平均等待時間平均等待時間(0+3+6)/3320問題問題2. 無法充分利用無法充分利用CPU繁忙的作業(yè)與繁忙的作業(yè)與I/O繁忙的繁忙的作業(yè)之間的互補(bǔ)關(guān)系。如果作業(yè)之間的互補(bǔ)關(guān)系。如果CPU繁忙的作

18、業(yè)獨(dú)占很繁忙的作業(yè)獨(dú)占很長時間的長時間的CPU，使得，使得I/O設(shè)備空閑，也使得設(shè)備空閑，也使得I/O繁忙繁忙的作業(yè)無法運(yùn)行。的作業(yè)無法運(yùn)行。作業(yè)作業(yè)A作業(yè)作業(yè)BCPUI/O作業(yè)作業(yè)A作業(yè)作業(yè)B時間時間t0t1 t2t3t4212. 短作業(yè)優(yōu)先 短作業(yè)優(yōu)先短作業(yè)優(yōu)先（Shortest Job First，SJF），設(shè)計），設(shè)計 目標(biāo)是改進(jìn)目標(biāo)是改進(jìn)FCFS算法，減少平均周轉(zhuǎn)時間；算法，減少平均周轉(zhuǎn)時間； SJF算法要求作業(yè)在開始執(zhí)行時預(yù)計執(zhí)行時間，算法要求作業(yè)在開始執(zhí)行時預(yù)計執(zhí)行時間， 對預(yù)計執(zhí)行時間短的作業(yè)優(yōu)先分派處理器；對預(yù)計執(zhí)行時間短的作業(yè)優(yōu)先分派處理器； 兩種實(shí)現(xiàn)方案：兩種實(shí)現(xiàn)方案：Q

19、 不可搶占方式：當(dāng)前作業(yè)在運(yùn)行時不會被打不可搶占方式：當(dāng)前作業(yè)在運(yùn)行時不會被打 斷，只有運(yùn)行完畢或阻塞時，才讓出斷，只有運(yùn)行完畢或阻塞時，才讓出CPU；Q 可搶占方式：如果一個新的短作業(yè)到來，其可搶占方式：如果一個新的短作業(yè)到來，其 運(yùn)行時間小于當(dāng)前正在運(yùn)行作業(yè)的剩余時間，運(yùn)行時間小于當(dāng)前正在運(yùn)行作業(yè)的剩余時間， 則搶占則搶占CPU運(yùn)行，稱為運(yùn)行，稱為SRTF（Shortest Remaining Time First）。）。22 可以證明：對于一組同時到達(dá)的作業(yè)，采用可以證明：對于一組同時到達(dá)的作業(yè)，采用SJF 算法將得到一個算法將得到一個最小最小的平均周轉(zhuǎn)時間。的平均周轉(zhuǎn)時間。D時間時間A

20、Ca a+b a+b+c a+b+c+d 例如，考察例如，考察4個作業(yè)個作業(yè)A、B、C、D，其運(yùn)行時間分，其運(yùn)行時間分別為別為a、b、c、dBA、B、C、D的周轉(zhuǎn)時間分別為的周轉(zhuǎn)時間分別為a、a+b、a+b+c和和a+b+c+d，因此平均周轉(zhuǎn)時間為：，因此平均周轉(zhuǎn)時間為：(4a+3b+2c+d)/4顯然，當(dāng)顯然，當(dāng)a b c d時，平均周轉(zhuǎn)時間最小。時，平均周轉(zhuǎn)時間最小。23取得最優(yōu)解的前提之一：這組作業(yè)必須同時到達(dá)；取得最優(yōu)解的前提之一：這組作業(yè)必須同時到達(dá)；例如：例如：進(jìn)程進(jìn)程到達(dá)時間到達(dá)時間運(yùn)行時間運(yùn)行時間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（不可搶占）

21、：（不可搶占）：P1P3P2P403781216平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(7 + 10 + 4 + 11) / 4 = 8平均等待時間：平均等待時間：(0 + 6 + 3 + 7) / 4 = 4若按若按P2,P3,P4,P1順序順序, 平均周轉(zhuǎn)和等待時間平均周轉(zhuǎn)和等待時間7.75, 3.7524進(jìn)程進(jìn)程到達(dá)時間到達(dá)時間運(yùn)行時間運(yùn)行時間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（可搶占）：（可搶占）：P1P3P2P4P2P1027411165平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(16 + 5 + 1 + 6) / 4 = 7平均等待時間：平均等待時間：(9 + 1 +

22、0 + 2) / 4 = 325前提條件之二：需要事先估計作業(yè)的運(yùn)行時間前提條件之二：需要事先估計作業(yè)的運(yùn)行時間如何知道作業(yè)的運(yùn)行時間？如何知道作業(yè)的運(yùn)行時間？% 該時間只可能是一個估計值；該時間只可能是一個估計值；% 讓提交該作業(yè)的用戶來提供。不太實(shí)用；讓提交該作業(yè)的用戶來提供。不太實(shí)用；% 使用前面的使用前面的CPU運(yùn)行時間來預(yù)測后面的運(yùn)行時間來預(yù)測后面的CPU運(yùn)運(yùn) 行時間，通過過去的行為來預(yù)測將來的行為。行時間，通過過去的行為來預(yù)測將來的行為。C 如果一個作業(yè)已經(jīng)運(yùn)行很長時間了，那它可能如果一個作業(yè)已經(jīng)運(yùn)行很長時間了，那它可能 還會運(yùn)行更長的時間；還會運(yùn)行更長的時間；C 使用指數(shù)平均值函

23、數(shù)來預(yù)測下一段使用指數(shù)平均值函數(shù)來預(yù)測下一段CPU時間時間;26指數(shù)平均值函數(shù)方法指數(shù)平均值函數(shù)方法.1 1nnnt1. tn 第第n個個CPU運(yùn)行時間的實(shí)際長度；運(yùn)行時間的實(shí)際長度；2. n+1 下一個下一個CPU運(yùn)行時間的預(yù)測長度；運(yùn)行時間的預(yù)測長度；3. 定義系數(shù)定義系數(shù) ，0 14. 定義：定義：273. 三層調(diào)度模型（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）28 準(zhǔn)入調(diào)度：決定哪一些作業(yè)能夠進(jìn)入系統(tǒng)運(yùn)行。準(zhǔn)入調(diào)度：決定哪一些作業(yè)能夠進(jìn)入系統(tǒng)運(yùn)行。 在這個層次上的調(diào)度算法主要有短作業(yè)優(yōu)先進(jìn)入在這個層次上的調(diào)度算

24、法主要有短作業(yè)優(yōu)先進(jìn)入, 以及把以及把CPU繁忙的作業(yè)和繁忙的作業(yè)和I/O繁忙的作業(yè)混合在繁忙的作業(yè)混合在 一起提交給系統(tǒng)；一起提交給系統(tǒng)； 存儲調(diào)度：決定哪一些進(jìn)程應(yīng)該留在內(nèi)存中，哪存儲調(diào)度：決定哪一些進(jìn)程應(yīng)該留在內(nèi)存中，哪 一些進(jìn)程應(yīng)該保存在磁盤上。需要考慮的因素包一些進(jìn)程應(yīng)該保存在磁盤上。需要考慮的因素包 括該進(jìn)程呆在內(nèi)存或磁盤上的時間長短，它所用括該進(jìn)程呆在內(nèi)存或磁盤上的時間長短，它所用 的的CPU時間以及它的優(yōu)先級等；時間以及它的優(yōu)先級等； CPU調(diào)度：從內(nèi)存當(dāng)中，選擇一個已經(jīng)就緒的進(jìn)調(diào)度：從內(nèi)存當(dāng)中，選擇一個已經(jīng)就緒的進(jìn) 程去運(yùn)行。程去運(yùn)行。批處理系統(tǒng)中的三層調(diào)度模型批處理系統(tǒng)中的

25、三層調(diào)度模型292.6.3 交互式系統(tǒng)中的調(diào)度算法交互式系統(tǒng)中的調(diào)度算法1. 時間片輪轉(zhuǎn)法 在在時間片輪轉(zhuǎn)算法時間片輪轉(zhuǎn)算法（Round-Robin，RR）中，將）中，將 所有的就緒進(jìn)程按照所有的就緒進(jìn)程按照FCFS原則，排成一個隊(duì)列；原則，排成一個隊(duì)列； 每次調(diào)度時將處理器分派給隊(duì)首進(jìn)程，讓其執(zhí)行每次調(diào)度時將處理器分派給隊(duì)首進(jìn)程，讓其執(zhí)行 一小段一小段CPU時間（時間片）；時間（時間片）； 在一個時間片結(jié)束時，如果進(jìn)程還沒有執(zhí)行完的在一個時間片結(jié)束時，如果進(jìn)程還沒有執(zhí)行完的 話，將發(fā)生時鐘中斷，在時鐘中斷中，進(jìn)程調(diào)度話，將發(fā)生時鐘中斷，在時鐘中斷中，進(jìn)程調(diào)度 程序?qū)和．?dāng)前進(jìn)程的執(zhí)行，并將其

26、送到就緒隊(duì)程序?qū)和．?dāng)前進(jìn)程的執(zhí)行，并將其送到就緒隊(duì) 列的末尾，然后執(zhí)行當(dāng)前的隊(duì)首進(jìn)程；列的末尾，然后執(zhí)行當(dāng)前的隊(duì)首進(jìn)程； 如果一個進(jìn)程在它的時間片用完之前就已結(jié)束或如果一個進(jìn)程在它的時間片用完之前就已結(jié)束或 被阻塞，那么立即讓出被阻塞，那么立即讓出CPU。30開始時，進(jìn)程開始時，進(jìn)程B位于隊(duì)列之首，因此被調(diào)度執(zhí)行。當(dāng)位于隊(duì)列之首，因此被調(diào)度執(zhí)行。當(dāng)它的時間片用完后，就把它送到就緒隊(duì)列的末尾。它的時間片用完后，就把它送到就緒隊(duì)列的末尾。同時，進(jìn)程同時，進(jìn)程F成為隊(duì)首進(jìn)程，被調(diào)度運(yùn)行。成為隊(duì)首進(jìn)程，被調(diào)度運(yùn)行。（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Oper

27、ating Systems” ）31Round robin, too.32 優(yōu)點(diǎn)：優(yōu)點(diǎn)：e 公平性公平性：各個就緒進(jìn)程平均地分配：各個就緒進(jìn)程平均地分配CPU的使用的使用 時間。假設(shè)有時間。假設(shè)有n個就緒進(jìn)程，時間片大小為個就緒進(jìn)程，時間片大小為q， 那么每個進(jìn)程將得到那么每個進(jìn)程將得到1/n的的CPU時間；時間；e 活動性活動性：每個進(jìn)程最多等待：每個進(jìn)程最多等待(n-1)q時間就能夠時間就能夠 再次得到再次得到CPU去運(yùn)行；去運(yùn)行；e 一般來說，平均周轉(zhuǎn)時間較一般來說，平均周轉(zhuǎn)時間較SJF算法為長，但算法為長，但 能夠得到能夠得到較短的平均響應(yīng)時間較短的平均響應(yīng)時間； 缺點(diǎn)：缺點(diǎn)：q的大小

28、難以確定的大小難以確定（一般在（一般在2050ms）。）。e q太大：退化為太大：退化為FCFS算法，進(jìn)程在一個時間片算法，進(jìn)程在一個時間片 內(nèi)都執(zhí)行完，響應(yīng)時間長。如內(nèi)都執(zhí)行完，響應(yīng)時間長。如q=100ms；e q太?。好總€進(jìn)程都需要更多的時間片才能處理太?。好總€進(jìn)程都需要更多的時間片才能處理 完，進(jìn)程切換次數(shù)增加，增大系統(tǒng)開銷。如完，進(jìn)程切換次數(shù)增加，增大系統(tǒng)開銷。如q=4ms時間片輪轉(zhuǎn)法的特點(diǎn)時間片輪轉(zhuǎn)法的特點(diǎn)33進(jìn)程進(jìn)程CPU時間時間P153 P2 17 P368 P4 24一個例子：時間片長度一個例子：時間片長度q20P1P2P3P4P1P3P4P1P3P30 20 37 57 77

29、 97 117 121 134 154 162平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(134 + 37 + 162 + 121) / 4113.5SJF的平均周轉(zhuǎn)時間：的平均周轉(zhuǎn)時間： (94 + 17 + 162 + 41) / 478.5342. 優(yōu)先級算法1 輪轉(zhuǎn)法有一個缺省的前提，即各進(jìn)程同等重要；輪轉(zhuǎn)法有一個缺省的前提，即各進(jìn)程同等重要；1 “人人生而平等人人生而平等”？ 恐怕不太現(xiàn)實(shí)！同樣，并恐怕不太現(xiàn)實(shí)！同樣，并 不是每個進(jìn)程都同等重要，不是每個進(jìn)程都同等重要， 怎么辦？分等級！怎么辦？分等級！1 優(yōu)先級算法優(yōu)先級算法（Priority Scheduling）：給每個進(jìn)）：給每個進(jìn) 程設(shè)置

30、一個優(yōu)先級，然后在所有就緒進(jìn)程中選擇程設(shè)置一個優(yōu)先級，然后在所有就緒進(jìn)程中選擇 優(yōu)先級最高的那個進(jìn)程去運(yùn)行；優(yōu)先級最高的那個進(jìn)程去運(yùn)行；1 SJF就是一個優(yōu)先級算法，每個進(jìn)程的優(yōu)先級是就是一個優(yōu)先級算法，每個進(jìn)程的優(yōu)先級是 它的它的CPU運(yùn)行時間（時間越短，優(yōu)先級越高）；運(yùn)行時間（時間越短，優(yōu)先級越高）；1 分為分為可搶占可搶占和和不可搶占不可搶占兩種方式；各進(jìn)程優(yōu)先級兩種方式；各進(jìn)程優(yōu)先級 的確定方式可分為的確定方式可分為靜態(tài)靜態(tài)和和動態(tài)動態(tài)兩種。兩種。35靜態(tài)優(yōu)先級方式靜態(tài)優(yōu)先級方式 確定優(yōu)先級的依據(jù)：確定優(yōu)先級的依據(jù)： 進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級高于用戶進(jìn)程，進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級高于用

31、戶進(jìn)程，交互式進(jìn)程高于批處理進(jìn)程）；交互式進(jìn)程高于批處理進(jìn)程）； 對系統(tǒng)資源的需求（對對系統(tǒng)資源的需求（對CPU和內(nèi)存需求較少和內(nèi)存需求較少的進(jìn)程，優(yōu)先級較高）；的進(jìn)程，優(yōu)先級較高）； 用戶要求（用戶級別和付費(fèi)情況，如軍用電用戶要求（用戶級別和付費(fèi)情況，如軍用電腦、商用電腦）。腦、商用電腦）。 靜態(tài)方式的缺點(diǎn)：高優(yōu)先級的進(jìn)程一直占用靜態(tài)方式的缺點(diǎn)：高優(yōu)先級的進(jìn)程一直占用CPU，低優(yōu)先級的進(jìn)程，低優(yōu)先級的進(jìn)程“饑餓饑餓”。 靜態(tài)優(yōu)先級方式靜態(tài)優(yōu)先級方式是指在創(chuàng)建進(jìn)程時確定進(jìn)程優(yōu)先級，是指在創(chuàng)建進(jìn)程時確定進(jìn)程優(yōu)先級，并保持不變到進(jìn)程結(jié)束。并保持不變到進(jìn)程結(jié)束。36動態(tài)優(yōu)先級方式動態(tài)優(yōu)先級方式 為防

32、為防“饑餓饑餓”, 根據(jù)運(yùn)行時間和等待時間調(diào)整優(yōu)先根據(jù)運(yùn)行時間和等待時間調(diào)整優(yōu)先級級 進(jìn)程每執(zhí)行一個時間片就降低其優(yōu)先級。當(dāng)一進(jìn)程每執(zhí)行一個時間片就降低其優(yōu)先級。當(dāng)一個進(jìn)程持續(xù)執(zhí)行時，其優(yōu)先級降低到讓出個進(jìn)程持續(xù)執(zhí)行時，其優(yōu)先級降低到讓出CPU； 在就緒隊(duì)列中，等待時間延長則優(yōu)先級提高，在就緒隊(duì)列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進(jìn)程在等待足夠的時間后，從而使優(yōu)先級較低的進(jìn)程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行。其優(yōu)先級提高到可被調(diào)度執(zhí)行。 為了讓為了讓I/O忙起來，可提高忙起來，可提高I/O繁忙進(jìn)程的優(yōu)先級。繁忙進(jìn)程的優(yōu)先級。但如何判定一個進(jìn)程是但如何判定一個進(jìn)程是I

33、/O繁忙的？可把進(jìn)程優(yōu)先繁忙的？可把進(jìn)程優(yōu)先級設(shè)為級設(shè)為1/f，f是在上一個時間片中所用的時間比例是在上一個時間片中所用的時間比例動態(tài)優(yōu)先級方式動態(tài)優(yōu)先級方式是指在創(chuàng)建進(jìn)程時賦予給進(jìn)程的優(yōu)是指在創(chuàng)建進(jìn)程時賦予給進(jìn)程的優(yōu)先級，在進(jìn)程運(yùn)行過程中可以動態(tài)改變，以便獲得先級，在進(jìn)程運(yùn)行過程中可以動態(tài)改變，以便獲得更好的調(diào)度性能。更好的調(diào)度性能。37優(yōu)先級類別優(yōu)先級類別（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）可以把進(jìn)程按照不同的優(yōu)先級別分組，然后在不同可以把進(jìn)程按照不同的優(yōu)先級別分組，然后在不同級別之間使用優(yōu)先級算法，而在同一

34、級別的各個進(jìn)級別之間使用優(yōu)先級算法，而在同一級別的各個進(jìn)程之間使用時間片輪轉(zhuǎn)法。程之間使用時間片輪轉(zhuǎn)法。383. 多級隊(duì)列算法多級隊(duì)列算法多級隊(duì)列算法（Multilevel Queue）引入多個就緒）引入多個就緒隊(duì)列，通過各個隊(duì)列的區(qū)別對待，達(dá)到一個綜合的隊(duì)列，通過各個隊(duì)列的區(qū)別對待，達(dá)到一個綜合的調(diào)度目標(biāo)。調(diào)度目標(biāo)。K 根據(jù)進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分根據(jù)進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分 為為若干個子隊(duì)列若干個子隊(duì)列，如系統(tǒng)進(jìn)程、用戶交互進(jìn)程、，如系統(tǒng)進(jìn)程、用戶交互進(jìn)程、 批處理進(jìn)程等；批處理進(jìn)程等；K 不同的隊(duì)列可以有不同的隊(duì)列可以有不同的優(yōu)先級不同的優(yōu)先級；K 不同的隊(duì)列

35、可以采用各自不同的隊(duì)列可以采用各自不同的調(diào)度算法不同的調(diào)度算法，如前，如前 臺的交互式進(jìn)程可采用臺的交互式進(jìn)程可采用RR算法，后臺的批處理進(jìn)算法，后臺的批處理進(jìn) 程可采用程可采用FCFS算法。算法。39K 在各個隊(duì)列之間也必須進(jìn)行調(diào)度：在各個隊(duì)列之間也必須進(jìn)行調(diào)度： 固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度：按照各種類型的進(jìn)程的優(yōu)先：按照各種類型的進(jìn)程的優(yōu)先 級別從高到低地進(jìn)行，先運(yùn)行最高優(yōu)先級的所級別從高到低地進(jìn)行，先運(yùn)行最高優(yōu)先級的所 有進(jìn)程，再運(yùn)行次一級所有進(jìn)程，依此類推。有進(jìn)程，再運(yùn)行次一級所有進(jìn)程，依此類推。 問題：可能導(dǎo)致問題：可能導(dǎo)致“饑餓饑餓”； 時間片方法時間片方法：把：把CPU時間按比

36、例分配給不同的時間按比例分配給不同的 隊(duì)列，然后再由各個隊(duì)列的調(diào)度算法去調(diào)度，隊(duì)列，然后再由各個隊(duì)列的調(diào)度算法去調(diào)度， 如如80給前臺的交互式進(jìn)程隊(duì)列（給前臺的交互式進(jìn)程隊(duì)列（RR算法），算法）， 20給后臺的批處理進(jìn)程隊(duì)列（給后臺的批處理進(jìn)程隊(duì)列（FCFS）。）。40（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）多級隊(duì)列算法的一個例子多級隊(duì)列算法的一個例子414. 多級反饋隊(duì)列算法J 多級隊(duì)列算法把每個進(jìn)程按照它的類型多級隊(duì)列算法把每個進(jìn)程按照它的類型固定固定在一在一 個隊(duì)列中，但問題是如何來確定進(jìn)

37、程的類型？個隊(duì)列中，但問題是如何來確定進(jìn)程的類型？ 而且有的進(jìn)程其類型可能動態(tài)變化，怎么辦？而且有的進(jìn)程其類型可能動態(tài)變化，怎么辦？ “路遙知馬力，日久見人心路遙知馬力，日久見人心”！J 多級反饋隊(duì)列算法多級反饋隊(duì)列算法 (Multilevel Feedback Queue) 即根據(jù)一個進(jìn)程的運(yùn)行反饋信息，即根據(jù)一個進(jìn)程的運(yùn)行反饋信息，動態(tài)地動態(tài)地調(diào)整它調(diào)整它 所在的隊(duì)列。所在的隊(duì)列。F 反饋反饋（Feedback）：即進(jìn)程在運(yùn)行當(dāng)中的表）：即進(jìn)程在運(yùn)行當(dāng)中的表 現(xiàn)，例如，它是否需要整個的時間片用于計現(xiàn)，例如，它是否需要整個的時間片用于計 算，或者它是否經(jīng)常地執(zhí)行算，或者它是否經(jīng)常地執(zhí)行I/O

38、操作？操作？42J 如何實(shí)現(xiàn)多級反饋隊(duì)列算法？需要確定以下的一如何實(shí)現(xiàn)多級反饋隊(duì)列算法？需要確定以下的一 些參數(shù)：些參數(shù)：F 隊(duì)列的個數(shù)；隊(duì)列的個數(shù)；F 每個隊(duì)列所用的調(diào)度算法；每個隊(duì)列所用的調(diào)度算法；F 用來確定何時給一個進(jìn)程用來確定何時給一個進(jìn)程“升級升級”的方法；的方法；F 用來確定何時給一個進(jìn)程用來確定何時給一個進(jìn)程“降級降級”的方法；的方法；F 用來確定一個進(jìn)程的初始隊(duì)列的方法；用來確定一個進(jìn)程的初始隊(duì)列的方法；43多級反饋隊(duì)列算法的一個例子多級反饋隊(duì)列算法的一個例子 三種優(yōu)先級別，三種優(yōu)先級別，3最高、最高、1最低，三個就緒隊(duì)列。時間片長度最低，三個就緒隊(duì)列。時間片長度 分別為分別

39、為N、2N和和4N； 新進(jìn)程進(jìn)入內(nèi)存后，優(yōu)先級為新進(jìn)程進(jìn)入內(nèi)存后，優(yōu)先級為3，加入隊(duì)列，加入隊(duì)列3的末尾，按的末尾，按FCFS 算法調(diào)度；若一個時間片內(nèi)未能執(zhí)行完，則優(yōu)先級降為算法調(diào)度；若一個時間片內(nèi)未能執(zhí)行完，則優(yōu)先級降為2，加，加 入到隊(duì)列入到隊(duì)列2的末尾，同樣按的末尾，同樣按FCFS算法調(diào)度；依此類推。算法調(diào)度；依此類推。 如果進(jìn)程在時間片用完之前即被阻塞，則增加它的優(yōu)先級；如果進(jìn)程在時間片用完之前即被阻塞，則增加它的優(yōu)先級； 僅當(dāng)較高優(yōu)先級的隊(duì)列為空，才調(diào)度較低優(yōu)先級的隊(duì)列中的進(jìn)僅當(dāng)較高優(yōu)先級的隊(duì)列為空，才調(diào)度較低優(yōu)先級的隊(duì)列中的進(jìn) 程執(zhí)行。若進(jìn)程執(zhí)行時有新進(jìn)程進(jìn)入較高優(yōu)先級的隊(duì)列，則

40、搶程執(zhí)行。若進(jìn)程執(zhí)行時有新進(jìn)程進(jìn)入較高優(yōu)先級的隊(duì)列，則搶 先執(zhí)行新進(jìn)程。先執(zhí)行新進(jìn)程。優(yōu)先級優(yōu)先級32144多級反饋隊(duì)列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算多級反饋隊(duì)列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法法的綜合和發(fā)展。其特點(diǎn)是：的綜合和發(fā)展。其特點(diǎn)是： 為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進(jìn)程：新進(jìn)程一進(jìn)來即賦予最高優(yōu)先級。進(jìn)程：新進(jìn)程一進(jìn)來即賦予最高優(yōu)先級。 為獲得較好的為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時間而設(shè)備利用率和縮短響應(yīng)時間而照顧了照顧了I/O繁忙的進(jìn)程：繁忙的進(jìn)程： I/O繁忙進(jìn)程：讓其進(jìn)入最高優(yōu)先級隊(duì)列，以及時啟繁忙進(jìn)程：讓其進(jìn)入最高

41、優(yōu)先級隊(duì)列，以及時啟動動I/O操作。通常只需一個小時間片，即可處理完一操作。通常只需一個小時間片，即可處理完一次次I/O請求，然后轉(zhuǎn)入到阻塞隊(duì)列。請求，然后轉(zhuǎn)入到阻塞隊(duì)列。 CPU繁忙進(jìn)程：每次都執(zhí)行完時間片，進(jìn)入更低級隊(duì)繁忙進(jìn)程：每次都執(zhí)行完時間片，進(jìn)入更低級隊(duì)列。最終采用最大時間片來執(zhí)行，減少調(diào)度次數(shù)。列。最終采用最大時間片來執(zhí)行，減少調(diào)度次數(shù)。 不必估計進(jìn)程的執(zhí)行時間，動態(tài)調(diào)節(jié)，能夠適應(yīng)不必估計進(jìn)程的執(zhí)行時間，動態(tài)調(diào)節(jié)，能夠適應(yīng)一個進(jìn)程在不同時間段的不同運(yùn)行特點(diǎn)。一個進(jìn)程在不同時間段的不同運(yùn)行特點(diǎn)。452.6.4 實(shí)時系統(tǒng)中的調(diào)度算法實(shí)時系統(tǒng)中的調(diào)度算法 在實(shí)時系統(tǒng)中，對時間的要求是非常

42、嚴(yán)格的。典在實(shí)時系統(tǒng)中，對時間的要求是非常嚴(yán)格的。典 型的例子是：一個或多個外部的物理設(shè)備定期或型的例子是：一個或多個外部的物理設(shè)備定期或 不定期地生成激勵信號，而計算機(jī)必須在一定的不定期地生成激勵信號，而計算機(jī)必須在一定的 時間期限內(nèi)做出恰當(dāng)?shù)姆磻?yīng)。時間期限內(nèi)做出恰當(dāng)?shù)姆磻?yīng)。 硬實(shí)時硬實(shí)時：有一個絕對的時間期限，計算機(jī)的反應(yīng)：有一個絕對的時間期限，計算機(jī)的反應(yīng) 動作必須在此期限之前完成，如核電站的控制系動作必須在此期限之前完成，如核電站的控制系 統(tǒng)；統(tǒng)；軟實(shí)時軟實(shí)時：偶爾錯過一次期限雖然是令人不快：偶爾錯過一次期限雖然是令人不快 的，但也是可以容忍的，如的，但也是可以容忍的，如VCD的播放系統(tǒng)；的播放系統(tǒng)； 實(shí)時調(diào)度算法可以是實(shí)時調(diào)度算法可以是靜態(tài)的靜態(tài)的或或動態(tài)的動態(tài)的，前者在系，前者在系 統(tǒng)開始運(yùn)行之前即已做好調(diào)度決策；而后者是在統(tǒng)開始運(yùn)行之前即已做好調(diào)度決策；而后者是在 運(yùn)行中做出調(diào)度決策。運(yùn)行中做出調(diào)度決策。462.6.5 線程調(diào)度線程調(diào)度在進(jìn)程調(diào)度中，如果每個進(jìn)程都帶有多個的在進(jìn)程調(diào)度中，如果每個進(jìn)程都帶有多個的線程，那么我們就有了兩個層面上的并行關(guān)線程，那么我們就有了兩個層面上的并行關(guān)