計算機(jī)軟件及應(yīng)用處理器管理課件

處理器管理

本章考核知識點(diǎn)：1.多道程序設(shè)計2.進(jìn)程3.進(jìn)程狀態(tài)4.進(jìn)程控制塊5.進(jìn)程隊列6.可再入程序7.中斷及中斷響應(yīng)8.中斷優(yōu)先級9.進(jìn)程調(diào)度自學(xué)要求：通過本章學(xué)習(xí)應(yīng)該掌握多道程序設(shè)計是如何提高計算機(jī)系統(tǒng)效率的；進(jìn)程與程序有什么區(qū)別；進(jìn)程的基本狀態(tài)以及狀態(tài)變化；進(jìn)程隊列及進(jìn)程調(diào)度策略；中斷的作用。重點(diǎn)是：多道程序設(shè)計；進(jìn)程的定義和屬性；進(jìn)程調(diào)度策略。處理器管理本章考核知識點(diǎn)：1.多道程序設(shè)計2.進(jìn)程3.13.1、多道程序設(shè)計（領(lǐng)會）3.1.1什么是多道程序設(shè)計讓多個計算問題同時裝入一個計算機(jī)系統(tǒng)的主存儲器并行執(zhí)行，這種設(shè)計技術(shù)稱“多道程序設(shè)計”，這種計算機(jī)系統(tǒng)稱“多道程序設(shè)計系統(tǒng)”或簡稱“多道系統(tǒng)”。3.1、多道程序設(shè)計（領(lǐng)會）2在多道程序設(shè)計的系統(tǒng)中，有三點(diǎn)基本要求：用"存儲保護(hù)"的方法保證各道程序互不侵犯；用"程序浮動"技術(shù)讓程序能靈活地改變存放區(qū)域且能正確執(zhí)行；必須對資源按一定的策略分配和調(diào)度。程序浮動：在多道程序設(shè)計系統(tǒng)中，對程序有一些特殊要求，也就是說，程序可以隨機(jī)地從主存的一個區(qū)域移動到另一個區(qū)域，程序被移動后仍絲毫不影響它的執(zhí)行，這種技術(shù)稱為“程序浮動“在多道程序設(shè)計的系統(tǒng)中，有三點(diǎn)基本要求：33.1.2為什么采用多道程序設(shè)計程序的順序執(zhí)行程序的并行執(zhí)行P363.1.2為什么采用多道程序設(shè)計程序的順序執(zhí)行4多道程序設(shè)計利用了系統(tǒng)與外圍設(shè)備的并行工作能力，從而提高工作效率。具體表現(xiàn)為：提高了處理器的利用率；充分利用外圍設(shè)備資源：發(fā)揮了處理器與外圍設(shè)備以及外圍設(shè)備之間的并行工作能力；從總體上說，采用多道程序設(shè)計技術(shù)后，可以有效地提高系統(tǒng)中資源的利用率，增加單位時間內(nèi)的算題量，從而提高了吞吐率。多道程序設(shè)計利用了系統(tǒng)與外圍設(shè)備的并行工作能力，從而提高工作53.1.3采用多道程序設(shè)計注意的問題

可能延長程序的執(zhí)行時間；

并行工作道數(shù)與系統(tǒng)效率不成正比從表面上看，增加并行工作道數(shù)就可提高系統(tǒng)效率，但實(shí)際上并行工作道數(shù)與系統(tǒng)效率是不成正比，因為并行的道數(shù)要根據(jù)系統(tǒng)配置的資源和用戶對資源的要求而定：(1)主存儲器的大小限制了可同時裝入的程序數(shù)量；

(2)外圍設(shè)備的數(shù)量也是一個制約條件；

(3)多個程序同時要求使用同一資源的情況也會經(jīng)常發(fā)生。3.1.3采用多道程序設(shè)計注意的問題6

總之，多道程序設(shè)計能提高系統(tǒng)資源的使用效率，增加單位時間的算題量；但是對每個計算問題來說，從算題開始到全部完成所需要的時間可能延長，另外在確定并行工作道數(shù)時應(yīng)綜合系統(tǒng)的資源配置和用戶對資源的要求。

7思考多道程序設(shè)計環(huán)境中，內(nèi)存中有多個程序，但是某時刻只有一個程序占用CPU運(yùn)行，其他程序在做什么？思考多道程序設(shè)計環(huán)境中，內(nèi)存中有多個程序，但是某時刻只有一個8S1:a:=x+y；S2:b:=a-5；S3:c:=b+1；S4:w=3+a

S5:x=c+w程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行S1S2S3例如對一個程序的多條語句:三條語句的順序執(zhí)行

3.2進(jìn)程S4S5S1:a:=x+y；程序的順序執(zhí)行及其特征1.程序的順序9

2.程序順序執(zhí)行時的特征

(1)順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在上一個操作結(jié)束之后開始。

(2)封閉性：程序是在封閉的環(huán)境下執(zhí)行的，即程序運(yùn)行時獨(dú)占全機(jī)資源，資源的狀態(tài)(除初始狀態(tài)外)只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響。

(3)可再現(xiàn)性：只要程序執(zhí)行時的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。優(yōu)點(diǎn)：程序的編制、調(diào)試方便，缺點(diǎn)：計算機(jī)系統(tǒng)效率不高。

程序的順序執(zhí)行及其特征2.程序順序執(zhí)行時的特征程序的順序執(zhí)行及其特征10程序的并發(fā)執(zhí)行及其特征

1．程序的并發(fā)執(zhí)行

若干個程序段同時在系統(tǒng)中運(yùn)行，這些程序段的執(zhí)行在時間上是重疊的，一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始，即使這種重疊是很小的一部分，也稱這幾個程序段是并發(fā)執(zhí)行的。PQR例：三個并發(fā)執(zhí)行的程序段。程序的并發(fā)執(zhí)行及其特征PQR例：三個并發(fā)執(zhí)行的程序段。11程序的并發(fā)執(zhí)行及其特征

1．程序的并發(fā)執(zhí)行在圖中存在Ii→Ci→Pi前趨關(guān)系，以至對一個作業(yè)的輸入、計算和打印三個操作，必須順序執(zhí)行，但并不存在Pi→Ii+1的關(guān)系，因而在對一批程序進(jìn)行處理時，可使它們并發(fā)執(zhí)行。i1p1icpo1i2p2o2i3p3o3t1t2t3進(jìn)程時間程序的并發(fā)執(zhí)行及其特征i1p1icpo1i2p2o2i3p12在該例中存在下述關(guān)系：

Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1

而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段：S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+b在該例中存在下述關(guān)系：Ii→Ci，Ii→Ii+1，Ci→P13練習(xí)：已知一個求值公式(A×A＋3B)/(B+5A)若A和B已經(jīng)賦值，試畫出該公式求解的前趨圖S1:W=A×AS2:V=3×B……練習(xí)：已知一個求值公式14

2．程序并發(fā)執(zhí)行時的特征

1)間斷性：走走停停

2)失去封閉性：資源狀態(tài)有多個程序改變3)不可再現(xiàn)性：計算結(jié)果和執(zhí)行速度有關(guān)例如，有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N:=N+1操作；程序B每執(zhí)行一次時，都要執(zhí)行print(N)操作，然后再將N置成“0”。A：while(1)B:while(1)N:＝N+1;{print(N)；N:=0;}程序A和B以不同的速度運(yùn)行。這樣，可能出現(xiàn)下述三種情況(假定某時刻變量N的值為n)。2．程序并發(fā)執(zhí)行時的特征15(1)N:=N+1;print(N);N:=0;N值分別為n+1，n+1，0。(2)print(N);N:=0;N:=N+1;值分別為n，0，1。(3)print(N);N:=N+1;N:=0;N值分別為n，n+1，0。上述情況說明，程序在并發(fā)執(zhí)行時，由于失去了封閉性，其計算結(jié)果已與并發(fā)程序的執(zhí)行速度有關(guān)，從而使程序的執(zhí)行失去了可再現(xiàn)性。不可再現(xiàn)性：程序經(jīng)過多次執(zhí)行后，雖然它們執(zhí)行時的環(huán)境和初始條件相同，但得到的結(jié)果卻各不相同。(1)N:=N+1;print(N);N:=0;N值分別為n16進(jìn)程的定義較典型的進(jìn)程定義有：(1)進(jìn)程是程序的一次執(zhí)行。(2)進(jìn)程是一個程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時所發(fā)生的活動。(3)進(jìn)程是程序在一個數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位。我們給出的進(jìn)程的定義：

進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位。3.2進(jìn)程3.2.1進(jìn)程的定義進(jìn)程的定義3.2進(jìn)程173.2進(jìn)程進(jìn)程三要素：程序、數(shù)據(jù)、CPU進(jìn)程與程序的區(qū)別及關(guān)系。程序是靜止的，進(jìn)程是動態(tài)的。進(jìn)程包括程序和程序處理的對象（數(shù)據(jù)集），進(jìn)程能得到程序處理的結(jié)果。進(jìn)程是一個獨(dú)立的運(yùn)行單位，能與其它進(jìn)程并行（并發(fā)）活動。而程序則不是。進(jìn)程是競爭計算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。進(jìn)程和程序并非一一對應(yīng)的，一個程序運(yùn)行在不同的數(shù)據(jù)集上就構(gòu)成了不同的進(jìn)程。一個程序可以作為多個進(jìn)程的運(yùn)行程序，一個進(jìn)程也可以運(yùn)行多個程序。3.2進(jìn)程18進(jìn)程與程序的區(qū)別簡單例子《操作系統(tǒng)課程》－－程序教師－－CPU學(xué)生學(xué)習(xí)過程－－進(jìn)程同一個教師教的A和B班學(xué)習(xí)進(jìn)度不一樣，所以可以比喻為一個程序擁有2個進(jìn)程思考：還有類似的例子嗎？進(jìn)程與程序的區(qū)別簡單例子19

我們舉一個例子，比如在有一個用戶程序notepad.exe(記事本)，當(dāng)它存放在磁盤上時，就是一個程序，在windows操作系統(tǒng)下運(yùn)行它時，就會在內(nèi)存中建立一個記事本程序的進(jìn)程，而我們在記事本中編輯的當(dāng)前文字就是這個進(jìn)程的數(shù)據(jù)集，操作系統(tǒng)會為當(dāng)前的進(jìn)程設(shè)置一個進(jìn)程控制塊。如果我們再打開一個記事本程序的窗口，就會建立另一個進(jìn)程，此時運(yùn)行的是同一個程序，但存在兩個進(jìn)程，第二個窗口中的編輯內(nèi)容就是第二個進(jìn)程的數(shù)據(jù)集。

203.2.2為什么引入進(jìn)程提高資源利用率正確描述程序的執(zhí)行情況3.2.2為什么引入進(jìn)程提高資源利用率21

進(jìn)程的類型在系統(tǒng)中同時有多個進(jìn)程存在，但歸納起來有兩大類：（1）系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程起著資源管理和控制的作用。

或者：執(zhí)行操作系統(tǒng)核心代碼的進(jìn)程。（2）用戶進(jìn)程執(zhí)行用戶程序的進(jìn)程。進(jìn)程的類型22系統(tǒng)進(jìn)程與用戶進(jìn)程的區(qū)別系統(tǒng)進(jìn)程被分配一個初始的資源集合，這些資源可以為它獨(dú)占，也能以最高優(yōu)先權(quán)的資格使用。用戶進(jìn)程通過系統(tǒng)服務(wù)請求的手段競爭使用系統(tǒng)資源；用戶進(jìn)程不能直接做I/O操作，而系統(tǒng)進(jìn)程可以做顯式的、直接的I/O操作。系統(tǒng)進(jìn)程在管態(tài)下活動，而用戶進(jìn)程則在用戶態(tài)（目態(tài)）下活動。另一種分類：計算進(jìn)程，I/O進(jìn)程等注意：在UNIX系統(tǒng)中沒有這樣對進(jìn)程進(jìn)行分類。系統(tǒng)進(jìn)程與用戶進(jìn)程的區(qū)別233.2.3進(jìn)程狀態(tài)（領(lǐng)會）

進(jìn)程的三種基本狀態(tài)：等待態(tài)：等待某個事件的完成；就緒態(tài)：等待系統(tǒng)分配處理器以便運(yùn)行；運(yùn)行態(tài)：占有處理器正在運(yùn)行。3.2.3進(jìn)程狀態(tài)（領(lǐng)會）24

1)就緒狀態(tài)(Ready)當(dāng)進(jìn)程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執(zhí)行，進(jìn)程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。

2)執(zhí)行狀態(tài)(Running）進(jìn)程已獲得CPU，其程序正在執(zhí)行。在單處理機(jī)系統(tǒng)中，只有一個進(jìn)程處于執(zhí)行狀態(tài)；在多處理機(jī)系統(tǒng)中，則有多個進(jìn)程處于執(zhí)行狀態(tài)。3.2.3進(jìn)程狀態(tài)（領(lǐng)會）1)就緒狀態(tài)(Ready)2)執(zhí)行狀態(tài)(Runni25

3)等待狀態(tài)（Wait/Block)正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)，這種暫停狀態(tài)稱為等待狀態(tài)（阻塞狀態(tài)或封鎖狀態(tài)）。

3)等待狀態(tài)（Wait/Block)26進(jìn)程的狀態(tài)變化進(jìn)程在執(zhí)行中狀態(tài)會不斷地改變，每個進(jìn)程在任何時刻總是處于上述三種基本狀態(tài)的某一種基本狀態(tài)，進(jìn)程狀態(tài)之間轉(zhuǎn)換關(guān)系如下圖所示：進(jìn)程的狀態(tài)變化27進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換

進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換28

運(yùn)行態(tài)→等待態(tài)往往是由于等待外設(shè)，等待主存等資源分配或等待人工干預(yù)而引起的。

等待態(tài)→就緒態(tài)則是等待的條件已滿足，只需分配到處理器后就能運(yùn)行。

運(yùn)行態(tài)→就緒態(tài)不是由于自身原因，而是由外界原因使運(yùn)行狀態(tài)的進(jìn)程讓出處理器，這時候就變成就緒態(tài)。例如時間片用完，或有更高優(yōu)先級的進(jìn)程來搶占處理器等。

就緒態(tài)→運(yùn)行態(tài)系統(tǒng)按某種策略選中就緒隊列中的一個進(jìn)程占用處理器，此時就變成了運(yùn)行態(tài)。運(yùn)行態(tài)→等待態(tài)往往是由于等待外設(shè)，等待主存等資源分配29進(jìn)程及狀態(tài)的例子醫(yī)院體檢體檢表——程序體檢過程——進(jìn)程體檢中等待、就緒、運(yùn)行對應(yīng)進(jìn)程的三種狀態(tài)進(jìn)程及狀態(tài)的例子醫(yī)院體檢30問題：單CPU系統(tǒng)中，如果系統(tǒng)中有N個進(jìn)程，運(yùn)行進(jìn)程最多幾個，最少幾個？就緒進(jìn)程最多幾個，最少幾個？等待進(jìn)程最多幾個，最少幾個？解答：運(yùn)行進(jìn)程最多1個，最少0個； 就緒進(jìn)程最多N-1個，最少0個； 等待進(jìn)程最多N個，最少0個；問題：單CPU系統(tǒng)中，如果系統(tǒng)中有N個進(jìn)程，解答：運(yùn)行進(jìn)程最31

小問題

下列進(jìn)程狀態(tài)變化中，______變化是不可能產(chǎn)生的？A運(yùn)行－>就緒B運(yùn)行－>阻塞C阻塞－>運(yùn)行D阻塞－>就緒小問題下列進(jìn)程狀態(tài)變化中，_32其他教材給出的進(jìn)程的狀態(tài)變圖

運(yùn)行

等待就緒服務(wù)請求(請求I/O等)服務(wù)完成/事件來到進(jìn)程調(diào)度時間片到運(yùn)行等待就緒服務(wù)請求服務(wù)完33

討論進(jìn)程狀態(tài)變遷

運(yùn)行

等待

就緒變遷1變遷4變遷3變遷2變遷1——>變遷3？變遷4——>變遷3？討論進(jìn)程狀態(tài)變遷運(yùn)行34問題：如果操作系統(tǒng)里面存在多個進(jìn)程，找出所有的可能狀態(tài)轉(zhuǎn)換。解答：

就緒—運(yùn)行:不一定（系統(tǒng)中僅一個進(jìn)程） 轉(zhuǎn)換條件：被調(diào)度程序選中

運(yùn)行—就緒:一定（討論就緒隊列的長度） 轉(zhuǎn)換條件：時間片到時,或有更高優(yōu)先級 的進(jìn)程出現(xiàn)

運(yùn)行—等待:不一定（考慮死鎖） 轉(zhuǎn)換條件：等待某事件發(fā)生

等待—就緒:不一定 轉(zhuǎn)換條件：考慮就緒隊列的長度問題：如果操作系統(tǒng)里面存在多個進(jìn)程，找出所有的可能狀態(tài)轉(zhuǎn)換。35例1：設(shè)有3個排序程序。程序A：采用冒泡排序算法，在屏幕的左1/3處開設(shè)一個窗口顯示其排序過程。程序B：采用堆排序算法，在屏幕的中1/3處開設(shè)一個窗口顯示其排序過程。程序C：采用快速排序算法，在屏幕的右1/3處開設(shè)一個窗口顯示其排序過程。(1)在不支持進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下運(yùn)行(2)在支持進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下運(yùn)行

例1：設(shè)有3個排序程序。36

例2：設(shè)有2個程序，程序C是打印工資報表的程序，程序D是計算1000以內(nèi)所有素數(shù)并顯示最后結(jié)果程序。(1)在不支持進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下運(yùn)行。(2)在支持進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下運(yùn)行。例2：解答(1)在不支持進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下，依次執(zhí)行程序C、程序D，可以看到，先是打印機(jī)不停地打印工資報表，打完后，接著運(yùn)行程序C，不停地計算，最后顯示所計算的結(jié)果。

(2)在支撐進(jìn)程運(yùn)行環(huán)境的操作系統(tǒng)下，創(chuàng)建進(jìn)程C和進(jìn)程D。由于進(jìn)程C是I/O量較大的進(jìn)程，而進(jìn)程D是計算量較大的進(jìn)程，故在系統(tǒng)進(jìn)程調(diào)度的控制下，兩個進(jìn)程并發(fā)執(zhí)行?？梢钥吹酱蛴C(jī)不斷打印工資報表，而處理機(jī)不停地計算，最后屏幕顯示計算的結(jié)果。例2：設(shè)有2個程序，程序C是打印工37進(jìn)程屬性：動態(tài)性

多個不同的進(jìn)程可以包含相同的程序并發(fā)執(zhí)行并發(fā)執(zhí)行的進(jìn)程輪流占用處理器

進(jìn)程有三種基本狀態(tài)[計算機(jī)軟件及應(yīng)用]處理器管理課件38可再入程序（識記）（1）什么是可再入程序。一個能被多個用戶同時調(diào)用的程序稱做"可再入"的程序。（2）可再入程序的性質(zhì)?？稍偃氤绦虮仨毷羌兇a，在執(zhí)行時自身不改變；一個可再入程序要求調(diào)用者提供工作區(qū)，以保證程序以同樣方式為各用戶服務(wù)。編譯程序和操作系統(tǒng)程序通常都是"可再入"程序，能同時被不同用戶調(diào)用而構(gòu)成不同的進(jìn)程。可再入程序（識記）39進(jìn)程三個特性：動態(tài)性從誕生、運(yùn)行，直至消滅。并發(fā)性并發(fā)執(zhí)行的進(jìn)程輪流占用處理器

異步性不可預(yù)知的速度向前推進(jìn)[計算機(jī)軟件及應(yīng)用]處理器管理課件40進(jìn)程控制塊的作用

進(jìn)程控制塊(ProcessControlBlock,簡稱PCB)，是操作系統(tǒng)為進(jìn)程分配的用于標(biāo)志進(jìn)程，記錄各進(jìn)程執(zhí)行情況的。進(jìn)程控制塊是進(jìn)程存在的標(biāo)志，它記錄了進(jìn)程從創(chuàng)建到消亡動態(tài)變化的狀況，進(jìn)程隊列實(shí)際也是進(jìn)程控制塊的鏈接。操作系統(tǒng)利用進(jìn)程控制塊對進(jìn)程進(jìn)行控制和管理。作用：(1)記錄進(jìn)程的有關(guān)信息，以便操作系統(tǒng)的進(jìn)程調(diào)度程序?qū)M(jìn)程進(jìn)行調(diào)度。這些信息包括標(biāo)志信息、說明信息、現(xiàn)場信息和管理信息等；(2)標(biāo)志進(jìn)程的存在，進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志

進(jìn)程的組成：程序+數(shù)據(jù)+PCB3.3進(jìn)程隊列3.3.1進(jìn)程控制塊（領(lǐng)會）進(jìn)程控制塊的作用3.3進(jìn)程隊列413.3進(jìn)程隊列3.3.1進(jìn)程控制塊（領(lǐng)會）進(jìn)程控制塊的基本內(nèi)容。標(biāo)志信息含唯一的進(jìn)程名說明信息有進(jìn)程狀態(tài)、等待原因、進(jìn)程程序存放位置和進(jìn)程數(shù)據(jù)存放位置現(xiàn)場信息包括通用、控制和程序狀態(tài)字寄存器的內(nèi)容管理信息存放程序優(yōu)先數(shù)和隊列指針3.3進(jìn)程隊列42PCB的主要內(nèi)容

PCB的主要內(nèi)容433.3進(jìn)程隊列3.3.2進(jìn)程的創(chuàng)建和撤銷3.3進(jìn)程隊列441．進(jìn)程圖(ProcessGraph)一個進(jìn)程可以創(chuàng)建另一個進(jìn)程，進(jìn)程圖是用于描述一個進(jìn)程的家族關(guān)系的有向樹，結(jié)點(diǎn)(圓圈)代表進(jìn)程。進(jìn)程樹

父進(jìn)程祖先子進(jìn)程1．進(jìn)程圖(ProcessGraph)進(jìn)程樹父進(jìn)程祖45

2．引起創(chuàng)建進(jìn)程的事件用戶登錄->分時OS作業(yè)調(diào)度->批處理OS提供服務(wù)應(yīng)用請求系統(tǒng)內(nèi)核創(chuàng)建應(yīng)用程序自己創(chuàng)建2．引起創(chuàng)建進(jìn)程的事件系統(tǒng)內(nèi)核創(chuàng)建應(yīng)用程序自己創(chuàng)建46

3．進(jìn)程的創(chuàng)建(CreationofProcess)調(diào)用進(jìn)程創(chuàng)建原語Creat()按下述步驟創(chuàng)建一個新進(jìn)程。申請空白PCB。為新進(jìn)程分配資源。初始化進(jìn)程控制塊將新進(jìn)程插入就緒隊列

代碼是什么樣的？

3．進(jìn)程的創(chuàng)建(CreationofProcess)47創(chuàng)建原語流圖創(chuàng)建原語流圖48進(jìn)程的撤銷1．引起進(jìn)程撤銷的事件1)正常結(jié)束例如，批處理系統(tǒng)中，Holt分時系統(tǒng)中，Logsoff2)異常結(jié)束越界﹑保護(hù)錯﹑特權(quán)指令錯﹑非法指令錯﹑運(yùn)行超時﹑等待超時﹑算術(shù)運(yùn)算錯﹑I/O故障3)外界干預(yù)操作員或操作系統(tǒng)﹑父進(jìn)程請求﹑父進(jìn)程終止進(jìn)程的撤銷492．進(jìn)程的撤銷過程如果系統(tǒng)中發(fā)生了上述要求終止進(jìn)程的某事件，OS便調(diào)用進(jìn)程終止原語destroy

.(1)根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。2．進(jìn)程的撤銷過程50

(3)若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防它們成為不可控的進(jìn)程。？(4)將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。(5)將被終止進(jìn)程(PCB)從所在隊列(或鏈表)中移出，等待其他程序來搜集信息。(3)若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終51撤消原語流圖撤消原語流圖52進(jìn)程的阻塞與喚醒

1.引起進(jìn)程阻塞和喚醒的事件有下述幾類事件會引起進(jìn)程阻塞或被喚醒。1)請求系統(tǒng)服務(wù)：打印機(jī)2)啟動某種操作：I/O3)新數(shù)據(jù)尚未到達(dá)：合作4)無新工作可做：發(fā)送數(shù)據(jù)

進(jìn)程的阻塞與喚醒532．進(jìn)程阻塞過程正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞原語block把自己阻塞。過程：停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”，并將PCB插入阻塞隊列;將本進(jìn)程插入到具有相同事件的阻塞(等待)隊列;轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程并進(jìn)行切換，2．進(jìn)程阻塞過程54入口將現(xiàn)行進(jìn)程的pcb現(xiàn)場送該進(jìn)程的pcb現(xiàn)場保護(hù)區(qū)置該進(jìn)程狀態(tài)為阻塞把該進(jìn)程插入相應(yīng)的等待隊列轉(zhuǎn)進(jìn)程調(diào)度程序進(jìn)程阻塞原語的實(shí)現(xiàn)，這里，轉(zhuǎn)進(jìn)程調(diào)度程序是很重要的，否則，處理機(jī)將會出現(xiàn)空轉(zhuǎn)而浪費(fèi)資源。入口將現(xiàn)行進(jìn)程的pcb現(xiàn)場送該進(jìn)程的pcb現(xiàn)場保護(hù)55

3．進(jìn)程喚醒過程當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時，則由有關(guān)進(jìn)程調(diào)用喚醒原語wakeup()，將等待該事件的進(jìn)程喚醒。執(zhí)行過程：把被阻塞的進(jìn)程從等待該事件的阻塞隊列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒;再將該P(yáng)CB插入到就緒隊列中。

3．進(jìn)程喚醒過程56圖喚醒原語[計算機(jī)軟件及應(yīng)用]處理器管理課件57小結(jié)

操作系統(tǒng)的順序程序和并發(fā)進(jìn)程執(zhí)行的各自特點(diǎn)(1)順序性1)間斷性

(2)封閉性2)失去封閉性(3)可再現(xiàn)性3)不可再現(xiàn)性

進(jìn)程基本概念進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位進(jìn)程的三個基本狀態(tài)及轉(zhuǎn)換1)就緒(Ready)狀態(tài)2)執(zhí)行狀態(tài)3)阻塞狀態(tài)進(jìn)程控制小結(jié)

操作系統(tǒng)的順序程序和并發(fā)進(jìn)程執(zhí)行的各自特點(diǎn)583.3.3進(jìn)程隊列的鏈接在多道程序設(shè)計的系統(tǒng)中往往會同時創(chuàng)建多個進(jìn)程。在單處理器的情況下，每次只能讓一個進(jìn)程運(yùn)行，其他的進(jìn)程處于就緒狀態(tài)或等待狀態(tài)。為了便于管理，經(jīng)常把處于相同狀態(tài)的進(jìn)程鏈接在一起，稱“進(jìn)程隊列”,由于進(jìn)程控制塊能標(biāo)志進(jìn)程的存在和動態(tài)刻畫進(jìn)程的特性，因此，進(jìn)程隊列可以用進(jìn)程控制塊的連接來形成。鏈接的方式有兩種：單向鏈接和雙向鏈接。

3.3.3進(jìn)程隊列的鏈接59基本隊列就緒隊列：由若干就緒進(jìn)程按一定次序鏈接起來的隊列。

等待隊列：把等待資源或等待某些事件的進(jìn)程排列的隊列進(jìn)程的入隊和出隊。出隊和入隊：當(dāng)發(fā)生的某個事件使一個進(jìn)程的狀態(tài)發(fā)生變化時，這個進(jìn)程就要退出所在的某個隊列而排入到另一個隊列中去。

出隊：一個進(jìn)程從所在的隊列退出的操作稱為出隊

入隊：一個進(jìn)程排入到一個指定的隊列的操作稱為入隊?；娟犃?0

系統(tǒng)中負(fù)責(zé)進(jìn)程入隊和出隊的工作稱為隊列管理。無論單向鏈接還是雙向鏈接，解決入，出隊問題，都是首先找到該隊列的隊首指針，沿鏈找出要入隊的進(jìn)程以及它要插入的位置，或找出要出隊的進(jìn)程，然后修改本進(jìn)程指針（入隊情況）和相鄰進(jìn)程的有關(guān)指針值即可。系統(tǒng)中負(fù)責(zé)進(jìn)程入隊和出隊的工作稱為隊列管理。61[計算機(jī)軟件及應(yīng)用]處理器管理課件623.4UNIX系統(tǒng)中的進(jìn)程3.4.1UNIX進(jìn)程的特點(diǎn)UNIX中分為用戶進(jìn)程和系統(tǒng)進(jìn)程，用戶進(jìn)程工作在用戶態(tài)執(zhí)行，系統(tǒng)進(jìn)程工作在核心態(tài)執(zhí)行。如果在用戶態(tài)的進(jìn)程要請求系統(tǒng)功能調(diào)用的話，需要使用訪管指令。3.4UNIX系統(tǒng)中的進(jìn)程3.4.1UNIX進(jìn)程的特點(diǎn)633.4UNIX系統(tǒng)中的進(jìn)程3.4.2UNIX進(jìn)程的組成進(jìn)程控制塊（包括進(jìn)程基本控制塊和進(jìn)程擴(kuò)充控制塊）、正文段、數(shù)據(jù)段（1）進(jìn)程基本控制塊（proc）中包含的內(nèi)容PS：進(jìn)程基本控制塊的內(nèi)容是常駐主存的。A,標(biāo)識信息：包括用戶標(biāo)識和進(jìn)程標(biāo)識。B,有關(guān)進(jìn)程非常駐主存的信息。C,進(jìn)程調(diào)度的一些信息。D,其他信息（2）進(jìn)程擴(kuò)充控制塊（user）隨用戶程序一起裝入主存和調(diào)出主存，包括：標(biāo)識，現(xiàn)場保護(hù)，主存管理，文件讀寫，系統(tǒng)調(diào)用，進(jìn)程控制與管理等。進(jìn)程控制塊并不全部在內(nèi)存。P46-48正文段:可供多個進(jìn)程共享的程序。數(shù)據(jù)段:進(jìn)程執(zhí)行費(fèi)共享的程序和程序執(zhí)行時所用到的數(shù)據(jù)。3.4UNIX系統(tǒng)中的進(jìn)程3.4.2UNIX進(jìn)程的組成643.4UNIX系統(tǒng)中的進(jìn)程3.4.3UNIX進(jìn)程的狀態(tài)（1）運(yùn)行狀態(tài)（2）就緒狀態(tài)（3）睡眠狀態(tài)（4）創(chuàng)建狀態(tài)（5）僵死狀態(tài)3.4UNIX系統(tǒng)中的進(jìn)程3.4.3UNIX進(jìn)程的狀態(tài)65

在UNIX系統(tǒng)中進(jìn)程控制的系統(tǒng)調(diào)用有：fork()創(chuàng)建子進(jìn)程sleep()進(jìn)程睡眠exit()進(jìn)程自已終止（自殺）wait()(父）等待子進(jìn)程終止wakeup()進(jìn)程喚醒

在UNIX系統(tǒng)中進(jìn)程控制的系統(tǒng)調(diào)用有：663.4UNIX系統(tǒng)中的進(jìn)程3.4.4UNIX進(jìn)程的創(chuàng)建和終止（1）unix進(jìn)程樹unix系統(tǒng)被啟動后，首先執(zhí)行0號進(jìn)程，0號進(jìn)程是運(yùn)行持續(xù)工作在核心態(tài)的進(jìn)程，它的功能是執(zhí)行進(jìn)程調(diào)度和讓進(jìn)程在主存和磁盤上進(jìn)行交換。0號進(jìn)程又稱為交換進(jìn)程。0號進(jìn)程又創(chuàng)建一個1號進(jìn)程，1號進(jìn)程又稱為初始化進(jìn)程。1號進(jìn)程在用戶態(tài)運(yùn)行，每當(dāng)有終端有用戶請求注冊時，1號進(jìn)程就為該用戶創(chuàng)建1個login進(jìn)程。如果有多個用戶注冊，那么就創(chuàng)建多個login進(jìn)程。如果用戶登陸成功login進(jìn)程就創(chuàng)建1個shell進(jìn)程。------------------------這樣的創(chuàng)建過程像一棵樹（2）unix進(jìn)程的創(chuàng)建在unix中除了1號進(jìn)程和0號進(jìn)程外其他進(jìn)程都是用fork()系統(tǒng)調(diào)用創(chuàng)建的，形成父子關(guān)系。由fork()創(chuàng)建的新進(jìn)程實(shí)際上是父進(jìn)程的一個映像。3.4UNIX系統(tǒng)中的進(jìn)程3.4.4UNIX進(jìn)程的創(chuàng)建和67fork主要工作如下：a,在進(jìn)程proc[]中找出一個空閑的表項，用來存放proc結(jié)構(gòu)b,為子進(jìn)程分配一個唯一的標(biāo)識號c,把父進(jìn)程的proc[]中的字段復(fù)制到子進(jìn)程的proc中，但把分配到得標(biāo)識號置于p_pid中，把p_ppid置為父進(jìn)程的的標(biāo)識號，把p_stat置為創(chuàng)建狀態(tài)。d,按父進(jìn)程中p_size所示的長度為子進(jìn)程申請分配內(nèi)存。（3）unix進(jìn)程的終止fork主要工作如下：68過程：以shell進(jìn)程為例，shell進(jìn)程通過接收用戶的命令，然后通過fork()創(chuàng)建子進(jìn)程處理命令exec，父進(jìn)程通過wait等待子進(jìn)程的結(jié)束，子進(jìn)程是通過系統(tǒng)調(diào)用exit請求終止自己，并釋放父進(jìn)程。系統(tǒng)調(diào)用exit的主要任務(wù)是把終止進(jìn)程自被創(chuàng)建以來所占用的系統(tǒng)資源退還給系統(tǒng)。關(guān)閉該進(jìn)程的打開文件，釋放它對正文段的使用權(quán)。把user結(jié)構(gòu)換出到磁盤兌換區(qū)并收回數(shù)據(jù)段占用的主存空間。然后把子進(jìn)程改為僵死狀態(tài)，像父進(jìn)程發(fā)出信號，由父進(jìn)程作善后處理。

系統(tǒng)調(diào)用wait對exit終止信號作善后處理。wait的任務(wù)是先查找僵死狀態(tài)的子進(jìn)程，若子進(jìn)程未僵死，則讓該進(jìn)程等待，直到子進(jìn)程成為僵死狀態(tài)后釋放。當(dāng)父進(jìn)程釋放后，wait繼續(xù)執(zhí)行，再從磁盤對換區(qū)中把子進(jìn)程的user結(jié)構(gòu)讀入主存，釋放user在對換區(qū)中所占的空間，然后把user存放的時間信息加在本進(jìn)程的user結(jié)構(gòu)中，再釋放主緩沖去，把子進(jìn)程子proc中的表項刪除。

綜上所述：一個子進(jìn)程終止后，其父進(jìn)程的善后處理工作主要是釋放子進(jìn)程的proc和user，并把user存放的時間信息累加到父進(jìn)程中。過程：以shell進(jìn)程為例，shell進(jìn)程通過接收用戶的命令69fork調(diào)用的一個奇妙之處就是它僅僅被調(diào)用一次，卻能夠返回兩次，它可能有三種不同的返回值：在父進(jìn)程中，fork返回新創(chuàng)建子進(jìn)程的進(jìn)程ID；在子進(jìn)程中，fork返回0；如果出現(xiàn)錯誤，fork返回一個負(fù)值P54實(shí)驗二進(jìn)程管理fork調(diào)用的一個奇妙之處就是它僅僅被調(diào)用一次，卻能夠返回兩70/*fork_test.c*/

#include<sys/types.h>

#inlcude<unistd.h>

main()

{

pid_tpid;

/*此時僅有一個進(jìn)程*/

pid=fork();

/*此時已經(jīng)有兩個進(jìn)程在同時運(yùn)行*/

if(pid<0)

printf("errorinfork!");

elseif(pid==0)

printf("Iamthechildprocess,myprocessIDis%d\n",getpid());

else

printf("Iamtheparentprocess,myprocessIDis%d\n",getpid());

}

編譯并運(yùn)行：$gccfork_test.c-ofork_test

$./fork_test

Iamtheparentprocess,myprocessIDis1991

Iamthechildprocess,myprocessIDis1992

/*fork_test.c*/

#include<sys713.4.5unix進(jìn)程的換進(jìn)換出概念：動態(tài)的對內(nèi)存中把就緒進(jìn)程從磁盤交換區(qū)移入，把等待進(jìn)程移到磁盤交換區(qū)，稱這種行為叫做進(jìn)程的換進(jìn)換出。意義：使系統(tǒng)運(yùn)行效率提高。3.4.6unix進(jìn)程的睡眠與喚醒3.4.5unix進(jìn)程的換進(jìn)換出概念：動態(tài)的對內(nèi)存中把就緒723.5中斷技術(shù)3.5.1、中斷和中斷的類型中斷一個進(jìn)程占有處理器運(yùn)行時，由于自身或者外界的原因（出現(xiàn)了事件）使運(yùn)行被打斷，讓操作系統(tǒng)處理所出現(xiàn)的事件，到適當(dāng)?shù)臅r候再讓被打斷的進(jìn)程繼續(xù)運(yùn)行，這個過程稱為"中斷"。3.5中斷技術(shù)73從中斷事件的性質(zhì)出發(fā)，中斷可以分為兩大類：強(qiáng)迫性中斷事件包括硬件故障中斷，程序性中斷，外部中斷和輸入輸出中斷等自愿性中斷事件是由正在運(yùn)行的進(jìn)程執(zhí)行一條訪管指令用以請求系統(tǒng)調(diào)用而引起的中斷，這種中斷也稱為"訪管中斷"。自愿中斷的斷點(diǎn)是確定的，而強(qiáng)迫性中斷的斷點(diǎn)可能發(fā)生在任何位置。從中斷事件的性質(zhì)出發(fā)，中斷可以分為兩大類：743.5.2中斷的響應(yīng)中斷響應(yīng)(硬件即中斷裝置操作)處理器每執(zhí)行一條指令后，硬件的中斷位置立即檢查有無中斷事件發(fā)生，若有中斷事件發(fā)生，則暫停現(xiàn)行進(jìn)程的執(zhí)行，而讓操作系統(tǒng)的中斷處理程序占用處理器，這一過程稱為"中斷響應(yīng)"。3.5.2中斷的響應(yīng)中斷響應(yīng)(硬件即中斷裝置操作)75中斷響應(yīng)過程中，中斷裝置要做以下三項工作：是否有中斷事件發(fā)生

判別自愿性中斷，只要檢查操作碼是否為訪管指令。

判別強(qiáng)迫性中斷，則要檢查中斷寄存器內(nèi)容。若為0，則無中斷；若非0，則表示有中斷事件發(fā)生。若有中斷發(fā)生，保護(hù)斷點(diǎn)信息

每個程序都有一個程序狀態(tài)字(PSW)來反映本狀態(tài)的執(zhí)行狀態(tài)，如基本狀態(tài)、中斷碼和中斷屏蔽位等內(nèi)容。處理器設(shè)有一個"程序狀態(tài)字寄存器"用來存放當(dāng)前運(yùn)行程序的PSW。程序狀態(tài)字可分為當(dāng)前PSW、舊PSW和新PSW。

當(dāng)出現(xiàn)中斷事件后，把被中斷進(jìn)程的PSW保存為舊PSW，即完成斷點(diǎn)信息保護(hù)。啟動操作系統(tǒng)的中斷處理程序工作

中斷裝置通過"交換PSW"過程完成此項任務(wù)，即把出現(xiàn)的中斷事件存放到當(dāng)前PSW中斷碼位置，然后把該當(dāng)前PSW保存為舊PSW，再把操作系統(tǒng)中斷處理程序的新PSW送到程序狀態(tài)字寄存器中，成為當(dāng)前的PSW。中斷響應(yīng)過程中，中斷裝置要做以下三項工作：763.5.4中斷處理(軟件即操作系統(tǒng)操作)操作系統(tǒng)的中斷處理程序?qū)χ袛嗍录M(jìn)行處理時，大致要做三方面的工作：保護(hù)被中斷進(jìn)程的現(xiàn)場信息

把中斷時的通用寄存器，控制寄存器內(nèi)容及舊PSW保存到被中斷進(jìn)程的進(jìn)程控制塊中。分析中斷原因

根據(jù)舊PSW的中斷碼可知發(fā)生該中斷的具體原因。處理發(fā)生的中斷事件

一般只做一些簡單處理，在多數(shù)情況下把具體的處理交給其他程序模塊去做。3.5.4中斷處理(軟件即操作系統(tǒng)操作)773.5.4中斷優(yōu)先級和中斷屏蔽（識記）1、中斷優(yōu)先級是硬件設(shè)計時確定的。中斷裝置按預(yù)定的順序來響應(yīng)同時出現(xiàn)的中斷事件，這個預(yù)定的順序稱為"中斷優(yōu)先級"。中斷優(yōu)先級是按中斷事件的重要性和緊迫程度來確定的，是由硬件設(shè)計時固定下來的。一般情況下，優(yōu)先級的高低順序依次為：硬件故障中斷、自愿中斷、程序性中斷，外部中斷和輸入輸出中斷。3.5.4中斷優(yōu)先級和中斷屏蔽（識記）782、中斷的嵌套處理3、中斷屏蔽的作用。中斷優(yōu)先級只是規(guī)定了中斷裝置響應(yīng)同時出現(xiàn)的中斷的次序，當(dāng)中斷裝置響應(yīng)了某個中斷后中斷處理程序在進(jìn)行處理時，中斷裝置也可能去響應(yīng)另一個中斷事件。因此會出現(xiàn)優(yōu)先級低的中斷事件的處理打斷優(yōu)先級高的中斷事件的處理，使得中斷事件的處理順序與響應(yīng)順序不一致，而且會形成多重嵌套處理，使多現(xiàn)場保護(hù)、程序返回等工作變的復(fù)雜。2、中斷的嵌套處理79中斷屏蔽技術(shù)就是為了解決上述問題而提出的在一個中斷處理沒有結(jié)束之前不響應(yīng)其他中斷事件，或者只響應(yīng)比當(dāng)前級別高的中斷事件。于是，當(dāng)中斷裝置檢查到有中斷事件后，便去查看PSW中中斷屏蔽標(biāo)志，如果沒有屏蔽就響應(yīng)該中斷；否則，暫時不響應(yīng)該中斷，待屏蔽標(biāo)志消除后再響應(yīng)。自愿中斷是不能屏蔽的。中斷屏蔽技術(shù)就是為了解決上述問題而提出的在一個中斷處理沒有結(jié)803.6UNIX系統(tǒng)的中斷技術(shù)3.6UNIX系統(tǒng)的中斷技術(shù)813.7處理器調(diào)度（領(lǐng)會）1、進(jìn)程調(diào)度的職責(zé)。按選定的進(jìn)程調(diào)度算法從就緒隊列中選擇一個進(jìn)程，讓它占用處理器。2、選擇進(jìn)程調(diào)度算法的幾個準(zhǔn)則：·提高處理器利用率

·增大吞吐量

·減少等待時間

·縮短響應(yīng)時間3.7處理器調(diào)度（領(lǐng)會）82處理機(jī)是計算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度算法對整個計算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響不同的OS，處理機(jī)管理的策略不同可把處理機(jī)調(diào)度分成三個層次：高級調(diào)度中級調(diào)度低級調(diào)度處理機(jī)調(diào)度的層次

3.7處理器調(diào)度（領(lǐng)會）處理機(jī)是計算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度的層次3.783處理機(jī)調(diào)度的層次

高級調(diào)度（宏觀調(diào)度、作業(yè)調(diào)度、長程調(diào)度）主要功能：根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊列，準(zhǔn)備執(zhí)行。因此，有時也把作業(yè)調(diào)度稱為接納調(diào)度(AdmissionScheduling)。

處理機(jī)調(diào)度的層次高級調(diào)度（宏觀調(diào)度、作業(yè)調(diào)度、長程調(diào)度）84低級調(diào)度（微觀調(diào)度、進(jìn)程調(diào)度、短程調(diào)度）功能：決定就緒隊列中的哪個進(jìn)程(或內(nèi)核級線程)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作.中級調(diào)度（中程調(diào)度、交換調(diào)度）按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外存交換區(qū)中。目的：提高內(nèi)存的利用率和系統(tǒng)吞吐量。處理機(jī)調(diào)度的層次

低級調(diào)度（微觀調(diào)度、進(jìn)程調(diào)度、短程調(diào)度）處理機(jī)調(diào)度的層次85處理機(jī)調(diào)度的層次

1高級調(diào)度（只針對批處理系統(tǒng)）1．作業(yè)和作業(yè)步(1)作業(yè)(Job)=程序+數(shù)據(jù)+作業(yè)說明書系統(tǒng)根據(jù)說明書來對程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。輸入井：磁盤上用來存放作業(yè)信息的專用區(qū)域后備作業(yè)：在輸入井中等待處理的作業(yè)。

處理機(jī)調(diào)度的層次1高級調(diào)度（只針對批處理系統(tǒng)）86(2)作業(yè)步(JobStep)。通常，在作業(yè)運(yùn)行期間，每個作業(yè)都必須經(jīng)過若干個相對獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。①編譯②連結(jié)裝配③運(yùn)行

(3)作業(yè)流。若干個作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，形成輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進(jìn)行處理，形成處理作業(yè)流。

(2)作業(yè)步(JobStep)。通常，在作業(yè)運(yùn)行期間87

2．作業(yè)控制塊JCB(JobControlBlock)是作業(yè)在系統(tǒng)中存在的標(biāo)志保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶帳戶、作業(yè)類型(CPU繁忙型、I/O繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)已運(yùn)行時間)、資源需求(預(yù)計運(yùn)行時間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進(jìn)入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。作業(yè)的狀態(tài)作業(yè)從輸入到完成要經(jīng)歷提交，收容，執(zhí)行，完成四個階段。2．作業(yè)控制塊JCB(JobControlBlock88JCB主要信息JCB主要信息89作業(yè)的狀態(tài)及其轉(zhuǎn)換①提交狀態(tài)：一個作業(yè)被提交給機(jī)房后或用戶通過終端設(shè)備向計算機(jī)中輸入其作業(yè)時所處的狀況。②后備狀態(tài)：作業(yè)的全部信息都已輸入，并存放在磁盤中等待運(yùn)行。③運(yùn)行狀態(tài)：作業(yè)被調(diào)度程序選中而被送入主存中投入運(yùn)行。④完成狀態(tài)：作業(yè)完成其全部運(yùn)行，釋放其所占用的全部資源，準(zhǔn)備退出系統(tǒng)。作業(yè)的狀態(tài)及其轉(zhuǎn)換90提交后備運(yùn)行就緒等待完成作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入作業(yè)的狀態(tài)及轉(zhuǎn)換提交后備運(yùn)行就緒等待完成作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入作業(yè)的狀態(tài)及91

3．作業(yè)調(diào)度算法的選擇用戶：周轉(zhuǎn)時間少最好系統(tǒng)：作業(yè)的平均周轉(zhuǎn)時間盡可能少，有利于提高CPU的利用率和系統(tǒng)的吞吐量。既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。1)決定接納多少個作業(yè)：多道程序度的確定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度等情況做適當(dāng)?shù)恼壑?)決定接納哪些作業(yè)：作業(yè)調(diào)度算法

3．作業(yè)調(diào)度算法的選擇922低級調(diào)度調(diào)度的對象是進(jìn)程(或內(nèi)核級線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實(shí)時三種類型的OS中，都必須配置這級調(diào)度。1．低級調(diào)度的功能低級調(diào)度用于決定就緒隊列中的哪個進(jìn)程(或內(nèi)核級線程)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。2低級調(diào)度93

低級調(diào)度的主要功能如下：(1)保存處理機(jī)的現(xiàn)場信息。(2)按某種算法選取進(jìn)程。(3)把處理器分配給進(jìn)程。低級調(diào)度的主要功能如下：942．進(jìn)程調(diào)度中的三個基本機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個基本機(jī)制：(1)排隊器。就緒進(jìn)程按照一定的方式排成一個或多個隊列(2)分派器(分派程序)。從就緒隊列中取出選中進(jìn)程，然后進(jìn)行上下文切換，分配處理機(jī)。(3)上下文切換機(jī)制。當(dāng)對處理機(jī)進(jìn)行切換時，會發(fā)生兩對上下文切換操作。在第一對上下文切換時，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對上下文切換時，將移出分派程序，而把新選進(jìn)程的CPU現(xiàn)場信息裝入到處理機(jī)的各個相應(yīng)寄存器中。耗時？怎么辦？P862．進(jìn)程調(diào)度中的三個基本機(jī)制95進(jìn)程調(diào)度時機(jī)正在執(zhí)行的進(jìn)程執(zhí)行完畢。運(yùn)行中的進(jìn)程提出I/O請求。執(zhí)行某原語操作。在可剝奪調(diào)度方式中，一個具有更高優(yōu)先數(shù)的進(jìn)程進(jìn)入就緒隊列。在分時系統(tǒng)中，分配給該進(jìn)程的時間片已用完

進(jìn)程調(diào)度時機(jī)963．進(jìn)程調(diào)度方式（兩種）

1)非搶占方式(NonpreemptiveMode)分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時，才把處理機(jī)分配給另一個進(jìn)程。優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。缺點(diǎn)：難以滿足緊急任務(wù)的要求——立即執(zhí)行3．進(jìn)程調(diào)度方式（兩種）972)搶占方式(PreemptiveMode)當(dāng)一個進(jìn)程正在運(yùn)行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。

優(yōu)點(diǎn)：公平，能滿足對響應(yīng)時間有著較嚴(yán)格要求的實(shí)時任務(wù)的需求。缺點(diǎn)：開銷較大。原則：（1）優(yōu)先權(quán)（2）短作業(yè)（進(jìn)程）優(yōu)先（3）時間片選擇性剝奪調(diào)度2)搶占方式(PreemptiveMode)98

在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時系統(tǒng)中通常是10～100ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(批)作業(yè)進(jìn)入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘（幾小時）一次，因此把它稱為長程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時間。中級調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。

在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時系統(tǒng)中通993.7.2批處理作業(yè)的調(diào)度算法設(shè)計調(diào)度算法的原則公平性平衡資源利用極大的流量3.7.2批處理作業(yè)的調(diào)度算法設(shè)計調(diào)度算法的原則100周轉(zhuǎn)時間：從作業(yè)被提交給系統(tǒng)Si（進(jìn)入輸入井）開始，到作業(yè)完成為止Ei的這段時間間隔。Ti=Ei-Si平均周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間：作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間Ts之比，即W=T/Ts3.7.2批處理作業(yè)的調(diào)度算法周轉(zhuǎn)時間：從作業(yè)被提交給系統(tǒng)Si（進(jìn)入輸入井）開始，到作業(yè)完101平均帶權(quán)周轉(zhuǎn)時間：一般，總是T或W小的作業(yè)被選中，因為這樣資源利用率較高，用戶也滿意。平均帶權(quán)周轉(zhuǎn)時間：一般，總是T或W小的作業(yè)被選中，因為102作業(yè)調(diào)

度

算

法

1．先來先服務(wù)調(diào)度算法

先來先服務(wù)(FCFSFirstcomefirstserved

)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進(jìn)入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊列。作業(yè)調(diào)度算法1．先來先服務(wù)調(diào)度算法103FCFS算法比較有利于長作業(yè)，而不利于短作業(yè)。下表列出了A、B、C、D四個作業(yè)分別到達(dá)系統(tǒng)的時間、要求服務(wù)的時間、開始執(zhí)行的時間及各自的完成時間，并計算出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。FCFS算法比較有利于長作業(yè)，而不利于短作業(yè)。下表列出了104從表上可以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時間競高達(dá)100，這是不能容忍的；而長作業(yè)D的帶權(quán)周轉(zhuǎn)時間僅為1.99。據(jù)此可知，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)。從表上可以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時間競高達(dá)100105在此，我們通過一個例子來說明采用FCFS調(diào)度算法時的調(diào)度性能。圖3-4(a)示出有五個進(jìn)程A、B、C、D、E，它們到達(dá)的時間分別是0、1、2、3和4，所要求的服務(wù)時間分別是4、3、5、2和4，其完成時間分別是4、7、12、14和18。從每個進(jìn)程的完成時間中減去其到達(dá)時間，即得到其周轉(zhuǎn)時間，進(jìn)而可以算出每個進(jìn)程的帶權(quán)周轉(zhuǎn)時間。在此，我們通過一個例子來說明采用FCFS調(diào)度算法時的調(diào)度106圖3-4

FCFS和SJF調(diào)度算法的性能

開始時間開始時間圖3-4FCFS和SJF調(diào)度算法的性能開始時間開始時間1072．短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法SJF（Shortestjobfirst），是指對短作業(yè)優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運(yùn)行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。

和FCFS調(diào)度算法進(jìn)行比較2．短作業(yè)優(yōu)先調(diào)度算法和FCFS調(diào)度算法進(jìn)行比較108

SJF調(diào)度算法缺點(diǎn)：(1)該算法對長作業(yè)不利，可能出現(xiàn)饑餓現(xiàn)象(2)因而不能保證緊迫性作業(yè)會被及時處理。(3)不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

SJF調(diào)度算法缺點(diǎn)：109作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18.002.0028.500.5039.000.1049.500.20平均周轉(zhuǎn)時間t=平均帶權(quán)周轉(zhuǎn)時間w=FCFS、SJF算法填表（以十進(jìn)制計）

作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間181103．高響應(yīng)比優(yōu)先調(diào)度算法（HRN）

先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性，先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時間，而忽視了作業(yè)的運(yùn)行時間，短作業(yè)優(yōu)先算法則相反，只考慮了作業(yè)的運(yùn)行時間，而忽視了作業(yè)的等待時間。HRN（HighestResponse-ratioNext）是對FCFS和SJF方式的一種綜合平衡。3．高響應(yīng)比優(yōu)先調(diào)度算法（HRN）111由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故響應(yīng)比RP=優(yōu)先權(quán)。據(jù)此，又可表示為：

每當(dāng)要進(jìn)行調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中RP最大者投入執(zhí)行。作業(yè)A執(zhí)行時間是1小時，在上午8點(diǎn)到達(dá)，10開始調(diào)度，則A的響應(yīng)比是多少？由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故112由上式可以看出：(1)如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。

(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。長短作業(yè)都得到照顧，但是增加系統(tǒng)開銷。

由上式可以看出：(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以113這樣算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運(yùn)行時間，并要作浮點(diǎn)運(yùn)算（這是系統(tǒng)程序最忌諱的）浪費(fèi)大量的計算時間，這是系統(tǒng)程序所不允許的。這樣算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等1144優(yōu)先調(diào)度算法(1)優(yōu)先權(quán)調(diào)度算法的類型為了照顧緊迫型作業(yè)/進(jìn)程，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。

對每個進(jìn)程確定一個優(yōu)先數(shù)，該算法總是讓優(yōu)先數(shù)最高的進(jìn)程先使用處理器。對具有相同優(yōu)先數(shù)的進(jìn)程，再采用先來先服務(wù)的次序分配處理器。系統(tǒng)常以任務(wù)的緊迫性和系統(tǒng)效率等因素確定進(jìn)程的優(yōu)先數(shù)。進(jìn)程的優(yōu)先數(shù)可以固定的，也可隨進(jìn)程執(zhí)行過程動態(tài)變化。一個高優(yōu)先數(shù)的進(jìn)程占用處理器后，系統(tǒng)處理該進(jìn)程時有兩種方法，一是"非搶占式"，另一種是"可搶占式"。前者是此進(jìn)程占用處理器后一直運(yùn)行到結(jié)束，除非本身主動讓出處理器，后者則是嚴(yán)格保證任何時刻總是讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行。

4優(yōu)先調(diào)度算法115(2)優(yōu)先權(quán)的類型

如何確定？1)靜態(tài)優(yōu)先權(quán)

作業(yè)的優(yōu)先級確定原則 作業(yè)的緊急程度 作業(yè)類型 作業(yè)要求資源情況(2)優(yōu)先權(quán)的類型1162)動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。改變進(jìn)程優(yōu)先級的方式：線形優(yōu)先級調(diào)度策略新創(chuàng)建的進(jìn)程按FCFS方式排成就緒隊列，優(yōu)先級以a的速率增加，正在執(zhí)行的進(jìn)程優(yōu)先級以b的速率下降。非線形改變優(yōu)先級規(guī)則2)動態(tài)優(yōu)先權(quán)1175均衡調(diào)度算法根據(jù)作業(yè)對資源的要求進(jìn)行分類，作業(yè)調(diào)度從各類作業(yè)中挑選，盡可能使不同資源的作業(yè)同時執(zhí)行。提高資源利用率，減少作業(yè)等待時間，加快作業(yè)執(zhí)行。5均衡調(diào)度算法1183.7.3進(jìn)程調(diào)度算法常用算法：先來先服務(wù)、優(yōu)先數(shù)法、輪轉(zhuǎn)法、分級調(diào)度。先來先服務(wù)調(diào)度算法該算法按進(jìn)程進(jìn)入就緒隊列的先后次序選擇可以占用處理器的進(jìn)程。優(yōu)先數(shù)調(diào)度算法對每個進(jìn)程確定一個優(yōu)先數(shù)，該算法總是讓優(yōu)先數(shù)最高的進(jìn)程先使用處理器。對具有相同優(yōu)先數(shù)的進(jìn)程，再采用先來先服務(wù)的次序分配處理器。系統(tǒng)常以任務(wù)的緊迫性和系統(tǒng)效率等因素確定進(jìn)程的優(yōu)先數(shù)。進(jìn)程的優(yōu)先數(shù)可以固定的，也可隨進(jìn)程執(zhí)行過程動態(tài)變化。一個高優(yōu)先數(shù)的進(jìn)程占用處理器后，系統(tǒng)處理該進(jìn)程時有兩種方法，一是"非搶占式"，另一種是"可搶占式"。前者是此進(jìn)程占用處理器后一直運(yùn)行到結(jié)束，除非本身主動讓出處理器，后者則是嚴(yán)格保證任何時刻總是讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行。

3.7.3進(jìn)程調(diào)度算法119進(jìn)程的切換進(jìn)程調(diào)度將從就緒隊列中另選一個進(jìn)程占用處理器，使一個進(jìn)程讓出處理器，由另一個進(jìn)程占用處理器的過程稱"進(jìn)程切換"。若有一個進(jìn)程從運(yùn)行態(tài)變成等待態(tài)，或完成工作后就撤消，則必定會發(fā)生進(jìn)程切換。若一個進(jìn)程從運(yùn)行態(tài)或等待態(tài)變成就緒態(tài)，則不一定發(fā)生進(jìn)程切換。進(jìn)程的切換進(jìn)程調(diào)度將從就緒隊列中另選一個進(jìn)程占用處理器，使120進(jìn)程的優(yōu)先級確定原則按進(jìn)程的類型賦予不同的優(yōu)先級用戶進(jìn)程類型：I/O忙，CPU忙，I/O與CPU均衡小系統(tǒng)進(jìn)程類型：調(diào)度進(jìn)程，I/O進(jìn)程，中斷處理，存儲各類等大進(jìn)程對資源的要求少的大用戶要求緊急大，付費(fèi)多的大將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進(jìn)程的優(yōu)先級。靜態(tài)優(yōu)先權(quán)特點(diǎn)：簡單易行，系統(tǒng)開銷小；不夠精確，可能出現(xiàn)優(yōu)先級低的作業(yè)或進(jìn)程，長期得不到調(diào)度。進(jìn)程的優(yōu)先級確定原則121時間片輪轉(zhuǎn)法

1)基本原理將CPU的處理時間分成固定大小的時間片，系統(tǒng)將所有就緒進(jìn)程按先來先服務(wù)的原則排成隊列。每次調(diào)度時，把CPU分配給隊首進(jìn)程，令其執(zhí)行一個時間片，時間片用完后，若進(jìn)程未結(jié)束，則重新排入就緒隊列尾部。2）時間片的劃分簡單循環(huán)輪轉(zhuǎn)調(diào)度時間片Q=R/NmaxR：響應(yīng)時間Nmax：最大進(jìn)程數(shù)

可變時間片輪轉(zhuǎn)調(diào)度時間片Q=R/NR：響應(yīng)時間N：實(shí)際進(jìn)程數(shù)[計算機(jī)軟件及應(yīng)用]處理器管理課件1222)時間片大小的確定

時間片很?。簩⒂欣诙套鳂I(yè)，會頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；

時間片太長，使得每個進(jìn)程都能在一個時間片內(nèi)完成，時間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求。若取時間片略大于一次典型的交互所需要的時間，這樣可使大多數(shù)進(jìn)程在一個時間片內(nèi)完成。

2)時間片大小的確定123下圖1時間片分別為q=1和q=4時，A、B、C、D、E五個進(jìn)程的運(yùn)行情況，而圖2為q=1和q=4時各進(jìn)程的平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。圖中的RR(RoundRobin)表示輪轉(zhuǎn)調(diào)度算法。A、B、C、D、E分別在0、1、2、3、4時刻到達(dá)，分別需要4、3、4、2、4個單位時間。下圖1時間片分別為q=1和q=4時，A、B、C、D、E五個進(jìn)124圖1q=1和q=4時的進(jìn)程運(yùn)行情況

A、B、C、D、E？A:4B:3C:4D:2E:4ABCDE圖1q=1和q=4時的進(jìn)程運(yùn)行情況A、B、C、D、E？125圖2q=1和q=4時進(jìn)程的周轉(zhuǎn)時間

圖2q=1和q=4時進(jìn)程的周轉(zhuǎn)時間126時間片輪轉(zhuǎn)調(diào)度法把規(guī)定進(jìn)程一次使用處理器的最長時間稱為"時間片"。時間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊列，每次總選擇該隊列中第一個進(jìn)程占用處理器，但規(guī)定只能使用一個時間片，如該進(jìn)程尚未完成，則排入隊尾，等待下一個供它使用的時間片。各個進(jìn)程就這樣輪轉(zhuǎn)運(yùn)行。時間片輪轉(zhuǎn)算法經(jīng)常用于分時操作系統(tǒng)中。

時間片輪轉(zhuǎn)調(diào)度法把規(guī)定進(jìn)程一次使用處理器的最長時間稱為"時127分級調(diào)度（多級反饋隊列調(diào)度）算法

(1)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3是多級反饋隊列算法的示意。分級調(diào)度（多級反饋隊列調(diào)度）算法128圖

多級反饋隊列調(diào)度算法

優(yōu)先級：隊列1>隊列2>隊列3>…>隊列nSi=2Si-1時間片到時間片到時間片到時間片到圖多級反饋隊列調(diào)度算法優(yōu)先級：隊列1>隊列2>隊列3>129多級反饋輪轉(zhuǎn)法設(shè)置多個就緒隊列,每個隊列賦予不同地優(yōu)先級。隊列按FCFS原則排列。各隊列時間片不同。當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先放在第一隊列尾，按FCFS原則調(diào)度；如果該時間片內(nèi)未結(jié)束，轉(zhuǎn)入第二隊列尾；直到最后的第N隊列，在第N隊列中便采取按時間片輪轉(zhuǎn)的方式執(zhí)行（不在轉(zhuǎn)下一個隊列了，因為在此隊列都執(zhí)行完了）。僅當(dāng)?shù)趇隊列空閑時，才調(diào)度第i+1隊列。如有新進(jìn)程進(jìn)入優(yōu)先級較高的隊列，則剝奪CPU執(zhí)行新進(jìn)程，舊進(jìn)程放入原隊列尾多級反饋輪轉(zhuǎn)法130多級反饋隊列調(diào)度算法性能終端型用戶：在第一隊列中完成，作業(yè)短，交互型。短批處理用戶：周轉(zhuǎn)時間較短，通常三個隊列即可完成。長批處理作業(yè)用戶：依次在前N-1個隊列中執(zhí)行，在第N個隊列中按輪轉(zhuǎn)方式運(yùn)行。多級反饋隊列調(diào)度算法性能131思考：如下調(diào)度用的進(jìn)程狀態(tài)變遷圖，有幾個隊列？調(diào)度算法和調(diào)度效果如何？

運(yùn)行低優(yōu)先就緒高優(yōu)先就緒等待首先選擇100ms其次選擇500ms請求I/OI/O完成超時間片思考：如下調(diào)度用的進(jìn)程狀態(tài)變遷圖，有幾個隊列？調(diào)度算法和調(diào)度132隊列結(jié)構(gòu)

I/O等待隊列——

一個進(jìn)程如果請求I/O，則進(jìn)入I/O等待隊列。低優(yōu)先就緒隊——一個進(jìn)程如果在運(yùn)行中超過了它的時間量就進(jìn)入低優(yōu)先就緒隊列。高優(yōu)先就緒隊列——當(dāng)進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時則進(jìn)入高優(yōu)先就緒隊列。

隊列結(jié)構(gòu)133進(jìn)程調(diào)度算法優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略：(1)當(dāng)CPU空閑時，若高優(yōu)先就緒隊列非空，則從高優(yōu)先就緒隊列中選擇一個進(jìn)程運(yùn)行，分配時間片為100ms。(2)當(dāng)CPU空閑時，若高優(yōu)先就緒隊列為空，則從低優(yōu)先就緒隊列中選擇一個進(jìn)程運(yùn)行，分配時間片為500ms。調(diào)度效果優(yōu)先照顧了I∕O量大的進(jìn)程；適當(dāng)照顧了計算量大的進(jìn)程。進(jìn)程調(diào)度算法1343.7.4UNIX系統(tǒng)的進(jìn)程調(diào)度算法動態(tài)優(yōu)先數(shù)調(diào)度算法設(shè)置法計算法進(jìn)程調(diào)度程序Switch3.7.4UNIX系統(tǒng)的進(jìn)程調(diào)度算法動態(tài)優(yōu)先數(shù)調(diào)度算法135思考若在操作系統(tǒng)的就緒進(jìn)程隊列中等待運(yùn)行的共有三個進(jìn)程P1、P2、P3，已知它們各自的運(yùn)行時間為a、b、c，且滿足關(guān)系a<b<c。請證明采用最短作業(yè)優(yōu)先調(diào)度算法能夠獲得最小平均周轉(zhuǎn)時間。思考若在操作系統(tǒng)的就緒進(jìn)程隊列中等待運(yùn)行的共有三個進(jìn)程P1、136證明：短作業(yè)優(yōu)先調(diào)度，調(diào)度順序為1，2，3，三個作業(yè)的總周轉(zhuǎn)時間為：T1=a+(a+b)+(a+b+c)若不按短作業(yè)優(yōu)先調(diào)度，采用非時間片輪轉(zhuǎn)法，不失一般性，假設(shè)調(diào)度順序為2，1，3，則總周轉(zhuǎn)時間為T2=由此可見，非時間片輪轉(zhuǎn)法中短作業(yè)優(yōu)先調(diào)度算法可獲得最小平均周轉(zhuǎn)時間。證明：137證明：

假設(shè)進(jìn)程被調(diào)度運(yùn)行的順序為P1、P2、P3，每個進(jìn)程的運(yùn)行時間為T1、T2、T3。若采用非時間片輪轉(zhuǎn)算法，則平均周轉(zhuǎn)時間的計算公式為：平均周轉(zhuǎn)時間＝（3T1+2T2＋T3）/3=T1+2T2/3+T3/3； 若采用時間片輪轉(zhuǎn)算法，設(shè)每個進(jìn)程需要N1,N2,N3個時間片可以運(yùn)行完，則周轉(zhuǎn)時間為:

其中Ts為時間片大小平均周轉(zhuǎn)時間＝顯然可見，采用非時間片輪轉(zhuǎn)的平均周轉(zhuǎn)時間小于采用時間片輪轉(zhuǎn)算法，在各種非時間片輪轉(zhuǎn)的線程調(diào)度算法中，保證平均周轉(zhuǎn)時間最小的條件為T1<T2<T3，即遵循最短作業(yè)優(yōu)先的思想調(diào)度進(jìn)程運(yùn)行。T=【(N1+N1-1+N1-1)+(N2+N1+N2-1)+(N3+N2+N1)】Ts=5T1+3T2+T3-3Ts證明：T=【(N1+N1-1+N1-1)+(N2+N1+N2138復(fù)習(xí)題1、實(shí)現(xiàn)多道設(shè)程序設(shè)計的前提條件是（）。A、成批處理作業(yè)B、分時多用戶C、設(shè)置管、目態(tài)D、處理機(jī)與外設(shè)并行操作2、進(jìn)程有多個狀態(tài)，不會發(fā)生的狀態(tài)轉(zhuǎn)換是（）A、就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)B、運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)C、就緒態(tài)轉(zhuǎn)換為等待態(tài)D、等待態(tài)轉(zhuǎn)換為就緒態(tài)3、進(jìn)程調(diào)度算法有多種，不是進(jìn)程調(diào)度算法的算法是（）。A、先來先服務(wù)調(diào)度算法B、最高響應(yīng)比優(yōu)先調(diào)度算法C、優(yōu)先數(shù)調(diào)度算法D、時間片輪轉(zhuǎn)調(diào)度算法復(fù)習(xí)題1、實(shí)現(xiàn)多道設(shè)程序設(shè)計的前提條件是（）。1394、多項選擇：進(jìn)程由（）組成。A、程序狀態(tài)字B、程序模塊C、就緒隊列D、數(shù)據(jù)集合E、進(jìn)程控制塊5、進(jìn)程所請求的一次打印輸出結(jié)束后，將使進(jìn)程狀態(tài)從（）。A、運(yùn)行態(tài)變?yōu)榫途w態(tài)B、運(yùn)行態(tài)變?yōu)榈却龖B(tài)C、就緒態(tài)變?yōu)檫\(yùn)行態(tài)D、等待態(tài)變?yōu)榫途w態(tài)多項選擇：引入多道程序設(shè)計的主要目的在于（）A、提高實(shí)時響應(yīng)速度B、充分利用處理機(jī)、減少處理機(jī)的空閑時間。C、有利于代碼共享D、充分利用外圍設(shè)備E、減少存儲器碎片4、多項選擇：進(jìn)程由（）組成。1407、進(jìn)程存在的標(biāo)志是__________，從操作系統(tǒng)的角度來看，可將進(jìn)程分為______________、_____________兩大類。8、進(jìn)程在用完一個器時間片后被強(qiáng)迫進(jìn)入的等待狀態(tài)屬于_________。9、簡答題：進(jìn)程調(diào)度中“可搶占”和“非搶占”兩種方式，哪一種系統(tǒng)的開銷更大？為什么？10、簡答題：簡述進(jìn)程調(diào)度的功能。11、簡答題：引起進(jìn)程調(diào)度的原因很多，試指出這些原因。7、進(jìn)程存在的標(biāo)志是__________，從操作系統(tǒng)的角度來1411、D2、C3、B4、BD5、D6、BD7、進(jìn)程控制塊系統(tǒng)進(jìn)程用戶進(jìn)程8、就緒態(tài)9、這兩種方式下，“可搶占”方式的系統(tǒng)開銷更大。因為此時系統(tǒng)必須監(jiān)視每一個進(jìn)入就緒態(tài)進(jìn)程的優(yōu)先數(shù)，當(dāng)優(yōu)先數(shù)高于當(dāng)前運(yùn)行態(tài)進(jìn)程時就產(chǎn)生中斷把更高優(yōu)先數(shù)的進(jìn)程調(diào)入運(yùn)行，這種情況勢必增加進(jìn)程調(diào)度的次數(shù)和保護(hù)現(xiàn)場的開銷。10、在多道程序設(shè)計系統(tǒng)中，同時有多個進(jìn)程處于就緒狀態(tài)，它們都要求占用處理器運(yùn)行。進(jìn)程調(diào)度的功能就是們競爭處理器問題的，它按照某種調(diào)度算法從就緒隊列中選擇一個進(jìn)程，讓它占用處理器。11、引起進(jìn)程調(diào)度的原因包括：（1）一個進(jìn)程從運(yùn)行狀態(tài)變成了等待狀態(tài)。（2）一個進(jìn)程從運(yùn)行狀態(tài)變成了就緒狀態(tài)。（3）一個進(jìn)程從等待狀態(tài)變成了就緒狀態(tài)（4）一個進(jìn)程完成工作后被撤消。1、D2、C3、B4、BD5、D6、BD142處理器管理

本章考核知識點(diǎn)：1.多道程序設(shè)計2.進(jìn)程3.進(jìn)程狀態(tài)4.進(jìn)程控制塊5.進(jìn)程隊列6.可再入程序7.中斷及中斷響應(yīng)8.中斷優(yōu)先級9.進(jìn)程調(diào)度自學(xué)要求：通過本章學(xué)習(xí)應(yīng)該掌握多道程序設(shè)計是如何提高計算機(jī)系統(tǒng)效率的；進(jìn)程與程序有什么區(qū)別；進(jìn)程的基本狀態(tài)以及狀態(tài)變化；進(jìn)程隊列及進(jìn)程調(diào)度策略；中斷的作用。重點(diǎn)是：多道程序設(shè)計；進(jìn)程的定義和屬性；進(jìn)程調(diào)度策略。處理器管理本章考核知識點(diǎn)：1.多道程序設(shè)計2.進(jìn)程3.1433.1、多道程序設(shè)計（領(lǐng)會）3.1.1什么是多道程序設(shè)計讓多個計算問題同時裝入一個計算機(jī)系統(tǒng)的主存儲器并行執(zhí)行，這種設(shè)計技術(shù)稱“多道程序設(shè)計”，這種計算機(jī)系統(tǒng)稱“多道程序設(shè)計系統(tǒng)”或簡稱“多道系統(tǒng)”。3.1、多道程序設(shè)計（領(lǐng)會）144在多道程序設(shè)計的系統(tǒng)中，有三點(diǎn)基本要求：用"存儲保護(hù)"的方法保證各道程序互不侵犯；用"程序浮動"技術(shù)讓程序能靈活地改變存放區(qū)域且能正確執(zhí)行；必須對資源按一定的策略分配和調(diào)度。程序浮動：在多道程序設(shè)計系統(tǒng)中，對程序有一些特殊要求，也就是說，程序可以隨機(jī)地從主存的一個區(qū)域移動到另一個區(qū)域，程序被移動后仍絲毫不影響它的執(zhí)行，這種技術(shù)稱為“程序浮動“在多道程序設(shè)計的系統(tǒng)中，有三點(diǎn)基本要求：1453.1.2為什么采用多道程序設(shè)計程序的順序執(zhí)行程序的并行執(zhí)行P363.1.2為什么采用多道程序設(shè)計程序的順序執(zhí)行146多道程序設(shè)計利用了系統(tǒng)與外圍設(shè)備的并行工作能力，從而提高工作效率。具體表現(xiàn)為：提高了處理器的利用率；充分利用外圍設(shè)備資源：發(fā)揮了處理器與外圍設(shè)備以及外圍設(shè)備之間的并行工作能力；從總體上說，采用多道程序設(shè)計技術(shù)后，可以有效地提高系統(tǒng)中資源的利用率，增加單位時間內(nèi)的算題量，從而提高了吞吐率。多道程序設(shè)計利用了系統(tǒng)與外圍設(shè)備的并行工作能力，從而提高工作1473.1.3采用多道程序設(shè)計注意的問題

可能延長程序的執(zhí)行時間；

并行工作道數(shù)與系統(tǒng)效率不成正比從表面上看，增加并行工作道數(shù)就可提高系統(tǒng)效率，但實(shí)際上并行工作道數(shù)與系統(tǒng)效率是不成正比，因為并行的道數(shù)要根據(jù)系統(tǒng)配置的資源和用戶對資源的要求而定：(1)主存儲器的大小限制了可同時裝入的程序數(shù)量；

(2)外圍設(shè)備的數(shù)量也是一個制約條件；

(3)多個程序同時要求使用同一資源的情況也會經(jīng)常發(fā)生。3.1.3采用多道程序設(shè)計注意的問題148

總之，多道程序設(shè)計能提高系統(tǒng)資源的使用效率，增加單位時間的算題量；但是對每個計算問題來說，從算題開始到全部完成所需要的時間可能延長，另外在確定并行工作道數(shù)時應(yīng)綜合系統(tǒng)的資源配置和用戶對資源的要求。

149思考多道程序設(shè)計環(huán)境中，內(nèi)存中有多個程序，但