操作系統(tǒng)原理第2章進(jìn)程與線程12.1什么是進(jìn)程 2.2進(jìn)程控制 2.3線程 2.4處理器調(diào)度 目錄2教學(xué)目的與要求3了解：

1.進(jìn)程控制塊的作用、包含信息和組織方式，操作系統(tǒng)內(nèi)核的主要功能；2.進(jìn)程創(chuàng)建、終止、阻塞、喚醒、掛起、激活的過程；3.各類進(jìn)程控制原語(yǔ)的執(zhí)行過程，線程的基本概念。理解：1.前趨圖的作用；2.程序順序執(zhí)行和并發(fā)執(zhí)行的特征。教學(xué)目的與要求4掌握：1.進(jìn)程的概念和特征；2.進(jìn)程的基本狀態(tài)及轉(zhuǎn)換；3.進(jìn)程控制基本；重點(diǎn)：1.進(jìn)程的基本狀態(tài)及轉(zhuǎn)換；2.處理調(diào)度常用算法。難點(diǎn)：1.各類進(jìn)程控制原語(yǔ)的執(zhí)行過程；2.進(jìn)程創(chuàng)建、終止、阻塞、喚醒、掛起、激活的過程；3.各類調(diào)度算法的編程實(shí)現(xiàn)；2025/2/18本章知識(shí)點(diǎn)：程序以進(jìn)程的形式來(lái)占用處理器和系統(tǒng)資源。處理器管理中最重要的是處理器調(diào)度，即進(jìn)程調(diào)度，也就是控制、協(xié)調(diào)進(jìn)程對(duì)處理器的競(jìng)爭(zhēng)。不同類型的操作系統(tǒng)可能采取不同的調(diào)度策略。2025/2/18問題導(dǎo)入6

2025/2/18現(xiàn)在怎樣來(lái)描述編譯程序P的狀態(tài)呢?稱它在B點(diǎn)等待磁盤傳輸狀態(tài)，還是稱它正在從A點(diǎn)開始執(zhí)行的狀態(tài)？現(xiàn)代操作系統(tǒng)實(shí)現(xiàn)多道程序，最主要的特點(diǎn)：并發(fā)執(zhí)行和資源共享2.1.1進(jìn)程的引入 2.1.2進(jìn)程與進(jìn)程控制塊 2.1什么是進(jìn)程72.1.1進(jìn)程的引入8前趨圖是一個(gè)有向無(wú)循環(huán)圖，用于描述程序、程序段或語(yǔ)句執(zhí)行的先后次序。1.圖中每個(gè)節(jié)點(diǎn)可以表示一條語(yǔ)句、一個(gè)程序段或一個(gè)進(jìn)程；2.節(jié)點(diǎn)間的有向邊“→”表示兩個(gè)節(jié)點(diǎn)之間的前趨關(guān)系：→={(Pi,Pj)|Pi必須在Pj開始執(zhí)行前完全執(zhí)行完}。3.(Pi,Pj)∈→，可寫成Pi→Pj，Pi是Pj的直接前趨，Pj是Pi的直

接后繼。4.把沒有前驅(qū)的節(jié)點(diǎn)稱為初始節(jié)點(diǎn)，把沒有后繼的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。2025/2/182.1.1進(jìn)程的引入9圖2-2給出了一個(gè)具有九個(gè)節(jié)點(diǎn)的前趨圖，該前趨圖中存在下面的前趨關(guān)系：2025/2/18P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P92.1.1

進(jìn)程的引入

10

2025/2/18P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}應(yīng)當(dāng)注意，前趨圖中是不允許有循環(huán)的，否則必然會(huì)產(chǎn)生不可能實(shí)現(xiàn)的前趨關(guān)系。2.1.1進(jìn)程的引入11例如，對(duì)于如下具有4條語(yǔ)句的程序段：P1：a=x+1；P2：b=y+2；P3：c=a+b；P4：d=c+3；請(qǐng)畫出前趨圖來(lái)描述這四條語(yǔ)句之間的執(zhí)行次序，并加以說明。2025/2/182.1.1進(jìn)程的引入121．程序的順序執(zhí)行在單道方式下，程序處在一個(gè)順序的環(huán)境中，多個(gè)程序在這一環(huán)境中是順序執(zhí)行的如圖所示，兩個(gè)作業(yè)之間的運(yùn)行方式就是單道順序執(zhí)行的方式。2025/2/182.1.1進(jìn)程的引入13程序的順序執(zhí)行的特征：（1）順序性：處理器嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在前一個(gè)操作結(jié)束之后開始。（2）封閉性：程序在封閉的環(huán)境下運(yùn)行，即程序運(yùn)行時(shí)獨(dú)占全部系統(tǒng)資源。（3）可再現(xiàn)性：只要程序的初始條件相同，則其執(zhí)行結(jié)果相同，無(wú)論何時(shí)執(zhí)行，也無(wú)論運(yùn)行速度怎樣都不會(huì)影響最后的運(yùn)行結(jié)果。2025/2/18

2.1.1進(jìn)程的引入

14在多道方式下，程序處在一個(gè)并發(fā)的執(zhí)行環(huán)境中，多個(gè)程序在這一環(huán)境中是并發(fā)執(zhí)行的，即若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始。如圖所示，兩個(gè)程序投入系統(tǒng)中的并發(fā)執(zhí)行方式，陰影部分所表示的時(shí)間就是他們并發(fā)執(zhí)行的時(shí)間。2025/2/182.1.1進(jìn)程的引入15程序的并發(fā)執(zhí)行具有如下一些特征：（1）間斷性:（2）失去封閉性：（3）不可再現(xiàn)性：2025/2/18由于對(duì)資源的競(jìng)爭(zhēng)和共享，或者相互協(xié)作共同完成某個(gè)任務(wù)而存在著相互制約的關(guān)系，也可能在運(yùn)行時(shí)由于一個(gè)時(shí)間片用完而中斷，放棄CPU使自己無(wú)法繼續(xù)運(yùn)行下去。由于資源共享以及相互協(xié)作，打破了程序單道執(zhí)行時(shí)所具有的封閉性。由于失去了封閉性，多個(gè)程序并發(fā)執(zhí)行時(shí)的相對(duì)速度是不確定的，每個(gè)程序都會(huì)經(jīng)歷“停停走走”的過程。2.1.1進(jìn)程的引入16舉例說明：例：N=N+1在print(N)和N=0之前

N=N+1在print(N)和N=0之后

N=N+1在print(N)和N=0之間2025/2/182.1.1進(jìn)程的引入17舉例說明：

為了了解某單行道的交通流量，在路口安放一個(gè)監(jiān)視器，功能是有車經(jīng)過該路段時(shí)，就向計(jì)算機(jī)發(fā)送一個(gè)信號(hào)。兩個(gè)程序的描述如下：程序A：

程序B：while(1)

while(1){

{A1:收到監(jiān)視器的信號(hào)；B1:延遲半小時(shí)；A2：COUNT=COUNT+1；B2:打印COUNT的值；}

B3：COUNT=0；

}2025/2/182.1.1進(jìn)程的引入18在多道程序環(huán)境下，程序的執(zhí)行屬于并發(fā)執(zhí)行，此時(shí)它們將失去其封閉性，并具有間斷性，以及其運(yùn)行結(jié)果不可再現(xiàn)性的特征。由此，決定了通常的程序是不能參與并發(fā)執(zhí)行的，否則，程序的運(yùn)行也就失去了意義。為了能使程序并發(fā)執(zhí)行，并且可以對(duì)并發(fā)執(zhí)行的程序加以描述和控制，人們引入了“進(jìn)程”的概念。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊191．進(jìn)程的概念引入進(jìn)程的目的:刻畫系統(tǒng)的動(dòng)態(tài)性，發(fā)揮系統(tǒng)的并發(fā)性。解決共享性，正確的描述程序的執(zhí)行狀態(tài)。進(jìn)程的定義：

進(jìn)程是可并發(fā)執(zhí)行的程序在某個(gè)數(shù)據(jù)集合上的一次計(jì)算活動(dòng)，也是操作系統(tǒng)進(jìn)行資源分配和運(yùn)行調(diào)度的基本單位。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊20進(jìn)程和程序的關(guān)系：（1）進(jìn)程是一個(gè)動(dòng)態(tài)概念，而程序是一個(gè)靜態(tài)概念。（2）進(jìn)程具有并發(fā)特性，而程序沒有。（3）進(jìn)程間會(huì)相互制約，而程序沒有。（4）進(jìn)程與程序之間存在多對(duì)多的聯(lián)系。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊212．進(jìn)程的特征（1）動(dòng)態(tài)性。（2）并發(fā)性。

（3）獨(dú)立性。

（4）異步性。

（5）結(jié)構(gòu)性。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊223．進(jìn)程控制塊的概念及其內(nèi)容

一個(gè)進(jìn)程創(chuàng)建后，需要有自己對(duì)應(yīng)的程序和該程序運(yùn)行時(shí)所需的數(shù)據(jù)，還需要數(shù)據(jù)結(jié)構(gòu)來(lái)刻畫進(jìn)程的動(dòng)態(tài)特征，描述進(jìn)程狀態(tài)，占有資源情況，調(diào)度信息等，通常使用一種稱為進(jìn)程控制塊的數(shù)據(jù)結(jié)構(gòu)來(lái)刻畫。

一個(gè)進(jìn)程要由3個(gè)部分組成：程序、數(shù)據(jù)集合以及進(jìn)程控制塊。由于進(jìn)程的狀態(tài)在不斷發(fā)生變化，某時(shí)刻進(jìn)程的內(nèi)容及其狀態(tài)集合稱之為進(jìn)程映像（ProcessImage）,其包括進(jìn)程控制塊，進(jìn)程程序段，進(jìn)程核心棧和進(jìn)程數(shù)據(jù)段4個(gè)要素。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊231.進(jìn)程控制塊是隨著進(jìn)程的創(chuàng)建而建立，隨著進(jìn)程的撤銷而取消的。2.PCB是進(jìn)程存在的唯一標(biāo)志，是操作系統(tǒng)用來(lái)記錄和刻畫進(jìn)程狀態(tài)及有關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。3.進(jìn)程控制塊應(yīng)常駐內(nèi)存，其包括進(jìn)程執(zhí)行時(shí)的情況以及進(jìn)程讓出CPU之后所處的狀態(tài)、斷點(diǎn)等信息。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊24進(jìn)程控制塊中的信息：（1）標(biāo)識(shí)信息。（2）現(xiàn)場(chǎng)信息。（3）調(diào)度信息。（4）控制信息。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊254.進(jìn)程控制塊的組織方式

進(jìn)程的特征主要由PCB來(lái)刻畫，為了便于對(duì)進(jìn)程進(jìn)行管理和調(diào)度，將進(jìn)程的PCB通過某種方法組織起來(lái)，有三種通用的組織方式：（1）線性方式。（2）鏈接方式。（3）索引方式。2025/2/182.1.2進(jìn)程與進(jìn)程控制塊26各個(gè)索引表在主存中的起始地址放在內(nèi)核的專用指針單元，如圖所示。進(jìn)程控制塊是操作系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)，它包含了操作系統(tǒng)所需要的關(guān)于進(jìn)程的所有信息。2025/2/182.2.1進(jìn)程的層次結(jié)構(gòu) 2.2.2進(jìn)程創(chuàng)建 2.2.3進(jìn)程終止 2.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換 2.2.5進(jìn)程的實(shí)現(xiàn) 2.2進(jìn)程控制272.2.1進(jìn)程的層次結(jié)構(gòu)28

一個(gè)進(jìn)程就有兩種基本狀態(tài)：運(yùn)行（Running）和非運(yùn)行（Not-running）。如何控制這些進(jìn)程，如何完善簡(jiǎn)單的兩種狀態(tài)，在了解層次結(jié)構(gòu)的基礎(chǔ)上，有必要討論進(jìn)程的創(chuàng)建和終止，在進(jìn)程的整個(gè)生命周期中介紹其狀態(tài)及狀態(tài)轉(zhuǎn)換的實(shí)現(xiàn)。對(duì)進(jìn)程的控制和管理由系統(tǒng)中的原語(yǔ)來(lái)實(shí)現(xiàn)。原語(yǔ)（Primitive）是完成系統(tǒng)特定功能的不可分割的過程，它具有原子性操作，其程序段不可以被中斷，或者說原語(yǔ)不能并發(fā)執(zhí)行。2025/2/182.2.1進(jìn)程的層次結(jié)構(gòu)29

不同操作系統(tǒng)創(chuàng)建進(jìn)程的方式不盡相同，傳統(tǒng)UNIX系統(tǒng)中是通過一個(gè)進(jìn)程創(chuàng)建另一個(gè)進(jìn)程，通常把創(chuàng)建進(jìn)程的進(jìn)程稱為父進(jìn)程，而把被創(chuàng)建的進(jìn)程稱為子進(jìn)程，子進(jìn)程繼承和共享父進(jìn)程的資源。子進(jìn)程可以繼續(xù)創(chuàng)建更多的子孫進(jìn)程，由此便形成了進(jìn)程的層次結(jié)構(gòu)，組成進(jìn)程家族。

2025/2/182.2.1進(jìn)程的層次結(jié)構(gòu)30

進(jìn)程圖是一種用于描述進(jìn)程家族關(guān)系的有向樹。

在圖中，節(jié)點(diǎn)代表進(jìn)程，圓圈中的符號(hào)是進(jìn)程名稱。進(jìn)程Pi創(chuàng)建了進(jìn)程Pj后（i，j=1，2，…，13），稱Pi是Pj的父進(jìn)程。2025/2/182.2.2進(jìn)程創(chuàng)建311.進(jìn)程創(chuàng)建的原因（1）用戶登錄。在一個(gè)交互式環(huán)境中，當(dāng)一個(gè)新用戶在終端鍵入登錄命令后，若是合法用戶，系統(tǒng)為該用戶建立一個(gè)進(jìn)程。（2）提供服務(wù)。當(dāng)運(yùn)行中的用戶程序提出某種請(qǐng)求后，系統(tǒng)將專門創(chuàng)建一個(gè)進(jìn)程來(lái)提供用戶所需要的服務(wù)。（3）作業(yè)調(diào)度。在批處理系統(tǒng)中，當(dāng)作業(yè)調(diào)度程序按一定的算法調(diào)度到某作業(yè)時(shí)，操作系統(tǒng)認(rèn)為有資源可運(yùn)行，便將該作業(yè)裝入內(nèi)存，為它分配必要的資源，并立即為它創(chuàng)建進(jìn)程。

（4）應(yīng)用請(qǐng)求。基于應(yīng)用進(jìn)程的需求，由它自己創(chuàng)建一個(gè)新進(jìn)程，以便使新進(jìn)程以并發(fā)運(yùn)行的方式完成特定的任務(wù)。2025/2/182.2.2進(jìn)程創(chuàng)建322．進(jìn)程創(chuàng)建的過程一般來(lái)說，進(jìn)程的創(chuàng)建過程如下：（1）在進(jìn)程列表中增加一項(xiàng)，申請(qǐng)一個(gè)空白PCB，為新進(jìn)程分配唯一的進(jìn)程標(biāo)識(shí)符。（2）為新進(jìn)程分配地址空間，以便容納進(jìn)程實(shí)體。由進(jìn)程管理程序確定加載至進(jìn)程地址空間中的程序。（3）為新進(jìn)程分配除主存空間以外的其他各種資源。（4）初始化PCB，如進(jìn)程標(biāo)識(shí)符，處理器初始狀態(tài)，進(jìn)程優(yōu)先級(jí)等。（5）將新進(jìn)程插入到相對(duì)應(yīng)的隊(duì)列。（6）通知操作系統(tǒng)的某些模塊，如性能檢測(cè)程序。2025/2/182.2.3進(jìn)程終止331．進(jìn)程終止的原因2025/2/18在任何計(jì)算機(jī)系統(tǒng)中，進(jìn)程必須有一種方法一表明其運(yùn)行結(jié)束，例如，批處理Halt指令或者os提供的終止指令。2.2.3進(jìn)程終止342．進(jìn)程終止的過程

一旦上述事件發(fā)生，系統(tǒng)或進(jìn)程將調(diào)用撤銷原語(yǔ)來(lái)終止進(jìn)程或子進(jìn)程。具體的過程如下：（1）根據(jù)終止進(jìn)程的標(biāo)識(shí)號(hào)，從相應(yīng)的隊(duì)列中查找并移除它。（2）若被終止進(jìn)程正處于運(yùn)行狀態(tài)，則立即停止該進(jìn)程的運(yùn)行，并重新調(diào)度。（3）將子進(jìn)程所擁有的資源歸還給父進(jìn)程或操作系統(tǒng)。（4）若此進(jìn)程擁有子進(jìn)程，先終止其所有子進(jìn)程，以防止它們脫離控制。（5）回收PCB，并將其歸還至PCB池。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換351.三狀態(tài)模型2025/2/18進(jìn)程周期：從創(chuàng)建而產(chǎn)生到終止而消亡的整個(gè)過程。運(yùn)行狀態(tài)：占用處理器執(zhí)行。非運(yùn)行狀態(tài)：分不到處理器而不能運(yùn)行；處理器空閑但因等待某個(gè)事件發(fā)生而無(wú)法執(zhí)行。說明進(jìn)程是活動(dòng)的且有狀態(tài)變化，狀態(tài)及狀態(tài)之間的轉(zhuǎn)換體現(xiàn)進(jìn)程的動(dòng)態(tài)性。2.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換361．三狀態(tài)模型（1）執(zhí)行態(tài)（running）：進(jìn)程占用處理器并執(zhí)行的狀態(tài)。在單處理器系統(tǒng)中，由于處理器的惟一性，至多只能有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)。（2）就緒態(tài)（ready）：進(jìn)程具備執(zhí)行條件，即已分配到除處理器以外的所有必要的資源，等待系統(tǒng)分配處理器以便其運(yùn)行的狀態(tài)。（3）阻塞態(tài)（blocked）：正在執(zhí)行的進(jìn)程由于發(fā)生某事件（如I/O請(qǐng)求，申請(qǐng)緩沖區(qū)失敗）暫時(shí)無(wú)法繼續(xù)執(zhí)行時(shí)的狀態(tài)，進(jìn)程的執(zhí)行受阻，此時(shí)引起進(jìn)程調(diào)度，OS把處理機(jī)分配給另一個(gè)就緒進(jìn)程，而讓阻塞的進(jìn)程處于暫停狀態(tài)。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換371．三狀態(tài)模型引起進(jìn)程狀態(tài)轉(zhuǎn)換的具體原因有以下幾點(diǎn)。（1）就緒態(tài)—執(zhí)行態(tài)。進(jìn)程調(diào)度程序根據(jù)調(diào)度算法把處理器分配給某個(gè)就緒進(jìn)程，并把控制轉(zhuǎn)到該進(jìn)程，使它由就緒態(tài)變?yōu)閳?zhí)行態(tài)，進(jìn)程投入運(yùn)行。（2）執(zhí)行態(tài)—就緒態(tài)。執(zhí)行中的進(jìn)程因所分配給它的時(shí)間片用完而被暫停運(yùn)行時(shí)，該進(jìn)程便由執(zhí)行態(tài)回到就緒態(tài)。（3）執(zhí)行態(tài)—阻塞態(tài)。因發(fā)生某事件而使進(jìn)程的執(zhí)行受阻（例如等待文件的輸入），使得進(jìn)程無(wú)法繼續(xù)執(zhí)行，該進(jìn)程將由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)。（4）阻塞態(tài)—就緒態(tài)。阻塞進(jìn)程在所等待的事件完成后，并不能立即投入運(yùn)行，需要通過進(jìn)程調(diào)度程序統(tǒng)一調(diào)度才能獲得處理器，此時(shí)將該進(jìn)程的狀態(tài)變?yōu)榫途w態(tài)繼續(xù)等待處理機(jī)。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換382．五狀態(tài)模型

在很多操作系統(tǒng)中，增加兩個(gè)進(jìn)程狀態(tài)：新建態(tài)（new）和終止態(tài)（exit）。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換392．五狀態(tài)模型（1）新建態(tài)（new）。進(jìn)程剛建立，還沒有被OS提交到可運(yùn)行進(jìn)程隊(duì)列。（2）終止態(tài)（exit）。進(jìn)程已正常或異常結(jié)束，被OS從可運(yùn)行進(jìn)程隊(duì)列中釋放出來(lái)。

處于終止態(tài)的進(jìn)程不再被調(diào)度執(zhí)行，在與該任務(wù)相關(guān)的表格或其它信息抽取完畢以后，OS也不必再保存與進(jìn)程有關(guān)的信息。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換402．五狀態(tài)模型下面簡(jiǎn)單介紹一下新增的幾種狀態(tài)轉(zhuǎn)換。（1）新建態(tài)—就緒態(tài)。對(duì)一個(gè)處于新建態(tài)的進(jìn)程，在就緒隊(duì)列能夠接納新進(jìn)程時(shí)，將被系統(tǒng)接收并進(jìn)入就緒隊(duì)列，此時(shí)的進(jìn)程狀態(tài)就從新建態(tài)轉(zhuǎn)為就緒態(tài)。（2）執(zhí)行態(tài)—終止態(tài)。對(duì)于一個(gè)處于執(zhí)行狀態(tài)的進(jìn)程，當(dāng)其正常執(zhí)行結(jié)束，或者因?yàn)榘l(fā)生了某種事件而被異常結(jié)束時(shí)，進(jìn)程的狀態(tài)就從執(zhí)行態(tài)轉(zhuǎn)換為終止態(tài)。

2025/2/18注意：在五狀態(tài)模型中，一個(gè)進(jìn)程在運(yùn)行期間，將仍然不斷的從一種狀態(tài)轉(zhuǎn)換到另一種狀態(tài)。一個(gè)進(jìn)程可能多次處于就緒、執(zhí)行和阻塞態(tài)，處于新建態(tài)和終止態(tài)的次數(shù)有且僅有一次。總之，進(jìn)程“生”與“死”都經(jīng)過一次，中間的狀態(tài)可以多次反復(fù)，很好的體現(xiàn)了進(jìn)程的生命周期。2.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換413．七狀態(tài)模型為了更好地管理和調(diào)度進(jìn)程以及適應(yīng)系統(tǒng)的功能目標(biāo)，引入掛起狀態(tài)。掛起進(jìn)程可以定義為暫時(shí)被淘汰出內(nèi)存的進(jìn)程（其PCB仍然保留在內(nèi)存），機(jī)器的資源是有限的，在資源不足的情況下，操作系統(tǒng)對(duì)在內(nèi)存中的進(jìn)程進(jìn)行合理的安排，其中有的進(jìn)程被暫時(shí)調(diào)離出內(nèi)存，當(dāng)條件允許的時(shí)候，會(huì)被操作系統(tǒng)再次調(diào)回內(nèi)存。具有掛起進(jìn)程功能的系統(tǒng)中的進(jìn)程狀態(tài)，兩個(gè)新狀態(tài)是掛起就緒態(tài)（readysuspend）和掛起阻塞態(tài)（blockedsuspend）。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換423．七狀態(tài)模型2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換433．七狀態(tài)模型（1）掛起就緒態(tài)（readysuspend）。進(jìn)程具備運(yùn)行條件，但目前在輔助存儲(chǔ)器中，只有當(dāng)進(jìn)程被兌換到主存時(shí)才能調(diào)度執(zhí)行。（2）掛起阻塞態(tài)（blockedsuspend）。進(jìn)程正在等待某一事件發(fā)生且進(jìn)程在輔助存儲(chǔ)器中。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換44引起進(jìn)程掛起的原因如下：（1）終端用戶的請(qǐng)求。當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問題時(shí)，希望暫停自己的程序。（2）父進(jìn)程的請(qǐng)求。有時(shí)父進(jìn)程希望掛起自己的某個(gè)子進(jìn)程，以便考察和修改子進(jìn)程，或者協(xié)調(diào)各子進(jìn)程間的活動(dòng)。（3）負(fù)荷調(diào)節(jié)的需要。當(dāng)實(shí)時(shí)系統(tǒng)中的工作負(fù)荷較重，可能影響到對(duì)實(shí)時(shí)任務(wù)的控制時(shí)，可由系統(tǒng)把一些不重要的進(jìn)程掛起，以保證系統(tǒng)能正常運(yùn)行。（4）操作系統(tǒng)的需要。操作系統(tǒng)有時(shí)希望掛起某些進(jìn)程，以便檢查資源使用情況或進(jìn)行記賬。（5）對(duì)換的需要。為了緩和內(nèi)存緊張的情況，將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程換至外存。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換45如果一個(gè)進(jìn)程原來(lái)處于執(zhí)行態(tài)或就緒態(tài)，此時(shí)可因掛起命令而由原來(lái)狀態(tài)變?yōu)閽炱鹁途w態(tài)，處于掛起就緒態(tài)的進(jìn)程不能參與處理器競(jìng)爭(zhēng)；當(dāng)處于掛起就緒狀態(tài)的進(jìn)程接到激活命令后，它就由原狀態(tài)變?yōu)榫途w態(tài)。具體可有以下幾種情況。（1）阻塞態(tài)—掛起阻塞態(tài)：如果當(dāng)前不存在就緒進(jìn)程，系統(tǒng)根據(jù)資源分配狀況和性能要求，選擇阻塞態(tài)進(jìn)程對(duì)換出去，使之處于掛起阻塞態(tài)。（2）掛起阻塞態(tài)—掛起就緒態(tài)：導(dǎo)致進(jìn)程阻塞的事件完成后，相應(yīng)的處于掛起阻塞態(tài)的進(jìn)程將轉(zhuǎn)化為掛起就緒態(tài)。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換46（3）掛起就緒態(tài)—就緒態(tài)：當(dāng)主存中不存在就緒進(jìn)程，或者掛起就緒態(tài)進(jìn)程具有比就緒態(tài)進(jìn)程更高的優(yōu)先級(jí)，系統(tǒng)將把掛起就緒態(tài)進(jìn)程換回主存并轉(zhuǎn)換成就緒態(tài)。（4）就緒態(tài)—掛起就緒態(tài)：系統(tǒng)根據(jù)當(dāng)前資源分配狀況和性能要求，決定把就緒態(tài)進(jìn)程對(duì)換出去，使之成為掛起就緒態(tài)。（5）掛起阻塞態(tài)—阻塞態(tài)：進(jìn)程等待事件發(fā)生時(shí)，原則上無(wú)需將其調(diào)入主存，但當(dāng)某些進(jìn)程終止后，系統(tǒng)擁有足夠的自由空間，而某個(gè)掛起阻塞態(tài)進(jìn)程具有較高的優(yōu)先級(jí)，且系統(tǒng)得知導(dǎo)致其阻塞的事件即將結(jié)束，便可能發(fā)生這一類狀態(tài)轉(zhuǎn)換。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換47（6）執(zhí)行態(tài)—掛起就緒態(tài)：當(dāng)一個(gè)具有較高優(yōu)先級(jí)的掛起阻塞進(jìn)程所阻塞的事件完成后，它需要搶占CPU，而此時(shí)主存空間不足，可能會(huì)導(dǎo)致正在運(yùn)行的進(jìn)程轉(zhuǎn)換為掛起就緒態(tài)。另外，執(zhí)行態(tài)進(jìn)程也可自我掛起。（7）新建態(tài)—掛起就緒態(tài)：考慮系統(tǒng)當(dāng)前資源分配狀況和性能要求，決定將新進(jìn)程對(duì)換出去，使之處于掛起就緒態(tài)。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換48

狀態(tài)的轉(zhuǎn)換需要原語(yǔ)來(lái)實(shí)現(xiàn)。下面介紹一些相關(guān)的狀態(tài)轉(zhuǎn)換控制原語(yǔ)。（1）進(jìn)程的阻塞一個(gè)正在運(yùn)行的進(jìn)程，因?yàn)槟M足其所需求的資源而被迫處于阻塞狀態(tài)，等待所需事件的發(fā)生，進(jìn)程的這種狀態(tài)的變化就是通過進(jìn)程本身調(diào)用阻塞原語(yǔ)實(shí)現(xiàn)的。阻塞是進(jìn)程的自主行為，進(jìn)程阻塞的步驟如下：步驟1：停止進(jìn)程執(zhí)行，將現(xiàn)場(chǎng)信息保存到PCB；步驟2：修改進(jìn)程PCB的有關(guān)內(nèi)容，如進(jìn)程狀態(tài)由執(zhí)行態(tài)改為阻塞態(tài)等，并把狀態(tài)已修改的進(jìn)程移入相應(yīng)事件的阻塞隊(duì)列中；步驟3：轉(zhuǎn)進(jìn)程調(diào)度程序，調(diào)度其他進(jìn)程運(yùn)行。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換49（2）進(jìn)程的喚醒當(dāng)?shù)却录瓿蓵r(shí)，會(huì)產(chǎn)生一個(gè)中斷，激活操作系統(tǒng)，在系統(tǒng)的控制之下將被阻塞的進(jìn)程喚醒，是被動(dòng)的過程。進(jìn)程喚醒的步驟如下：步驟1：從相應(yīng)的阻塞隊(duì)列里移出進(jìn)程；步驟2：修改進(jìn)程PCB的有關(guān)內(nèi)容，如進(jìn)程狀態(tài)改為就緒態(tài)，并將進(jìn)程移入就緒隊(duì)列；步驟3：若被喚醒的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)高，重新設(shè)置調(diào)度標(biāo)志。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換50（3）進(jìn)程的掛起當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)(例如，用戶進(jìn)程請(qǐng)求將自己掛起，或父進(jìn)程請(qǐng)求掛起某子進(jìn)程)調(diào)用掛起原語(yǔ)，進(jìn)程掛起的步驟如下:步驟1：檢查被掛起進(jìn)程的狀態(tài)，若處于就緒態(tài)，便將

其改為掛起就緒；對(duì)于阻塞態(tài)的進(jìn)程，則將之改為掛起阻塞，并將其移入到指定隊(duì)列；步驟2：把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域；步驟3：若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。2025/2/182.2.4進(jìn)程的狀態(tài)與轉(zhuǎn)換51（4）進(jìn)程的激活當(dāng)系統(tǒng)資源充裕或請(qǐng)求激活指定進(jìn)程時(shí)，系統(tǒng)或相關(guān)進(jìn)程會(huì)調(diào)用激活原語(yǔ)把指定進(jìn)程激活，激活的步驟如下：步驟1：先將進(jìn)程從外存調(diào)入內(nèi)存步驟2：檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是掛起就緒，便將之改為就緒；若為掛起阻塞便將之改為阻塞，并將進(jìn)程移入相應(yīng)隊(duì)列。2025/2/182.2.5進(jìn)程的實(shí)現(xiàn)52

為了實(shí)現(xiàn)進(jìn)程模型，操作系統(tǒng)維護(hù)著一張表格（一個(gè)結(jié)構(gòu)數(shù)組），即進(jìn)程表（processtable）。每個(gè)進(jìn)程占用一個(gè)進(jìn)程表項(xiàng)，即PCB。為了實(shí)現(xiàn)進(jìn)程并行執(zhí)行的錯(cuò)覺，操作系統(tǒng)需不斷的對(duì)進(jìn)程切換，實(shí)質(zhì)上，為了完成進(jìn)程的切換，還需要環(huán)境的支撐，如硬件寄存器，程序狀態(tài)字寄存器等。在操作系統(tǒng)中，進(jìn)程物理實(shí)體和支持進(jìn)程運(yùn)行的環(huán)境合成進(jìn)程上下文（processcontext）,進(jìn)程在當(dāng)前上下文中運(yùn)行，當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理器時(shí)，新老進(jìn)程隨之發(fā)生上下文切換，進(jìn)程上下文由三部分組成。2025/2/182.2.5進(jìn)程的實(shí)現(xiàn)53（1）用戶級(jí)上下文（userlevelcontext）由正文（程序），數(shù)據(jù)，共享存儲(chǔ)區(qū)，用戶棧所組成。（2）寄存器上下文（registercontext）由程序狀態(tài)字寄存器，指令計(jì)數(shù)器，棧指針（機(jī)器狀態(tài)決定它指向用戶棧或核心棧），控制寄存器，通用寄存器等組成。（3）系統(tǒng)級(jí)上下文（systemlevelcontext）由進(jìn)程控制塊，主存管理信息，核心棧等組成。2025/2/182.2.5進(jìn)程的實(shí)現(xiàn)54

當(dāng)該例程結(jié)束后，它調(diào)用一個(gè)C過程處理某個(gè)特定的中斷類型剩下的工作（假設(shè)操作系統(tǒng)由C語(yǔ)言編寫）。在完成有關(guān)工作之后，接著調(diào)用調(diào)度程序，決定隨后該運(yùn)行哪個(gè)進(jìn)程。隨后將控制權(quán)轉(zhuǎn)給一段匯編語(yǔ)言代碼，為當(dāng)前的進(jìn)程裝入寄存器值以及內(nèi)存映射并啟動(dòng)該進(jìn)程運(yùn)行。中斷處理和調(diào)度的過程具體如下：（1）硬件將程序計(jì)數(shù)器等壓入堆棧。（2）硬件從中斷向量裝入新的程序計(jì)數(shù)器。（3）匯編語(yǔ)言過程保存寄存器值。2025/2/182.2.5進(jìn)程的實(shí)現(xiàn)55（4）匯編語(yǔ)言過程設(shè)置新的堆棧。（5）C中斷服務(wù)例程運(yùn)行（如讀或緩沖輸入等）。（6）調(diào)度程序決定下一個(gè)將運(yùn)行的進(jìn)程。（7）C過程返回至匯編代碼。（8）匯編語(yǔ)言過程開始運(yùn)行新的當(dāng)前進(jìn)程。2025/2/182.3.1線程的引入及定義

2.3.2線程的狀態(tài)

2.3.3線程的特征

2.3.4線程的分類

2.3.5多核和多線程

2.3線程562.3.1線程的引入及定義57

線程（Thread）是現(xiàn)代操作體統(tǒng)中出現(xiàn)的一個(gè)重要技術(shù)，目前流行的操作系統(tǒng)幾乎都采用了線程機(jī)制。線程的引入進(jìn)一步提供了程序執(zhí)行的并發(fā)性，提高了系統(tǒng)的效率。在傳統(tǒng)的操作系統(tǒng)中，進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位，以進(jìn)程為單位分配存放其映像所需要的虛地址空間，執(zhí)行所需要的主存空間，完成任務(wù)需要的其他各類外圍設(shè)備資源和文件。2025/2/182.3.1線程的引入及定義58

所謂線程，是進(jìn)程內(nèi)的一個(gè)相對(duì)獨(dú)立的，可獨(dú)立調(diào)度和指派的執(zhí)行單元。是進(jìn)程的組成部分。線程的組成部分有：（1）線程的唯一標(biāo)識(shí)符及線程狀態(tài)信息，即線程控制塊（TCB）。（2）未運(yùn)行時(shí)所保存的進(jìn)程上下文，可把線程看成進(jìn)程中一個(gè)獨(dú)立的程序計(jì)數(shù)器。（3）核心棧，在核心態(tài)工作時(shí)保存參數(shù)，在函數(shù)調(diào)用時(shí)返回地址，等等。（4）用于存放線程局部變量和用戶棧的私有存儲(chǔ)區(qū)。2025/2/182.3.1線程的引入及定義59傳統(tǒng)的操作系統(tǒng)一般只支持單線程結(jié)構(gòu)進(jìn)程，但像windows，Solaris等很多操作系統(tǒng)多線程結(jié)構(gòu)進(jìn)程，如圖所示。2025/2/182.3.2線程的狀態(tài)60與進(jìn)程一樣，線程是個(gè)動(dòng)態(tài)的概念，也有生命周期，在這一過程中它具有各種狀態(tài)，雖然在不同的操作系統(tǒng)中，線程的狀態(tài)不完全相同，但下述三個(gè)關(guān)鍵的狀態(tài)是共有的。（1）就緒狀態(tài)：線程已具備執(zhí)行條件，調(diào)度程序可以為其分配一個(gè)CPU執(zhí)行。（2）運(yùn)行狀態(tài)：線程正在某一個(gè)CPU內(nèi)運(yùn)行。（3）阻塞狀態(tài)：線程正在等待某個(gè)事件發(fā)生，則被阻塞。2025/2/182.3.2線程的狀態(tài)61線程的狀態(tài)轉(zhuǎn)換是通過相關(guān)的控制原語(yǔ)實(shí)現(xiàn)的。常用的原語(yǔ)有：創(chuàng)建線程，終止線程，線程阻塞等。創(chuàng)建線程通常被稱為派生，它可以在進(jìn)程內(nèi)派生出來(lái)，也可以由線程派生。一個(gè)新派生的線程具有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)指針和變量，然后放入就緒隊(duì)列。如果一個(gè)線程執(zhí)行完后終止該線程，它的寄存器上下文以及堆棧內(nèi)容將被釋放。2025/2/182.3.3線程的特征62

根據(jù)線程的概念，線程具有以下一些特征。（1）線程是進(jìn)程中的一個(gè)相對(duì)可獨(dú)立運(yùn)行的單元。（2）線程是操作系統(tǒng)中的基本調(diào)度單位，在線程中包含調(diào)度所需要的基本信息。（3）在具備線程機(jī)制的操作系統(tǒng)中，進(jìn)程不再是調(diào)度單位，一個(gè)進(jìn)程中至少包含一個(gè)線程，以線程作為調(diào)度單位。（4）線程自己并不擁有資源，它與同進(jìn)程中的其它線程共享該進(jìn)程所擁有的資源。由于線程之間涉及資源共享，所以需要同步機(jī)制來(lái)實(shí)現(xiàn)進(jìn)程內(nèi)多線程之間的通信。（5）與進(jìn)程類似，線程還可以創(chuàng)建其他線程，線程也有生命周期，也有狀態(tài)的變化。2025/2/182.3.3線程的特征63線程與進(jìn)程的區(qū)別

（1）擁有資源方面。不管是以進(jìn)程為基本單位的操作系統(tǒng)，還是在引進(jìn)線程的操作系統(tǒng)中，進(jìn)程都是獨(dú)立擁有資源的一個(gè)基本單位。（2）調(diào)度方面。引入線程后，進(jìn)程是資源的擁有者，線程是處理機(jī)調(diào)度和分配的單位。（3）并發(fā)性方面。引入線程后，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且一個(gè)進(jìn)程內(nèi)的多個(gè)線程之間也可以并發(fā)執(zhí)行，因此系統(tǒng)具有了更好的并發(fā)性，進(jìn)而提高了系統(tǒng)的資源利用率和吞吐量。（4）系統(tǒng)開銷方面。進(jìn)程切換時(shí)有很大的時(shí)空開銷，而線程切換時(shí)只需要保存和設(shè)置少量的寄存器，時(shí)空開銷很小。2025/2/182.3.4線程的分類64將多線程的實(shí)現(xiàn)方法分成3類：用戶級(jí)線程、內(nèi)核支持線程和混合式線程，如圖所示。2025/2/182.3.4線程的分類651．用戶級(jí)線程用戶級(jí)線程（User-LevelThread，ULT）由用戶程序創(chuàng)建，并由用戶程序?qū)ζ溥M(jìn)程調(diào)度和管理。這種方法有以下優(yōu)點(diǎn)：（1）用戶級(jí)線程的切換無(wú)需通過陷入(內(nèi)中斷)進(jìn)入內(nèi)核，切換操作在進(jìn)程的用戶空間中進(jìn)行，用于管理線程的數(shù)據(jù)結(jié)構(gòu)均保存在進(jìn)程的用戶空間內(nèi)，因此用戶級(jí)線程的切換速度高于內(nèi)核支持線程的切換速度，而且系統(tǒng)開銷小。（2）用戶級(jí)線程可以運(yùn)行在任何操作系統(tǒng)上，就是在不支持線程的操作系統(tǒng)上也可以實(shí)現(xiàn)用戶級(jí)線程。2025/2/182.3.4線程的分類66（3）由于線程調(diào)度由線程庫(kù)實(shí)現(xiàn)，而線程庫(kù)的線程調(diào)度算法與系統(tǒng)的進(jìn)程調(diào)度算法無(wú)關(guān)，因此線程調(diào)度靈活方便。各應(yīng)用程序可以根據(jù)需要在線程庫(kù)中選擇不同的線程調(diào)度算法，而不會(huì)干擾內(nèi)核的進(jìn)程調(diào)度程序。這種方法有以下缺點(diǎn)：（1）由于內(nèi)核不知道用戶級(jí)線程的存在，因此，當(dāng)用戶級(jí)線程執(zhí)行一個(gè)系統(tǒng)調(diào)用時(shí)，系統(tǒng)將阻塞該線程所屬的整個(gè)進(jìn)程，使得該進(jìn)程內(nèi)的所有線程都不能運(yùn)行，從而降低了線程的并發(fā)性。（2）在ULT方式下，多線程不便利用多處理器，因?yàn)槊看沃挥幸粋€(gè)進(jìn)程的一個(gè)線程在一個(gè)CPU上運(yùn)行。2025/2/182.3.4線程的分類672．內(nèi)核級(jí)線程內(nèi)核級(jí)線程（Kernel-LevelThread，KLT）中，所有線程的創(chuàng)建，調(diào)度，管理都由操作系統(tǒng)內(nèi)核負(fù)責(zé)。這種方法有以下優(yōu)點(diǎn)：（1）在引入內(nèi)核支持線程的操作系統(tǒng)中，調(diào)度以線程為單位，內(nèi)核能夠同時(shí)調(diào)度一個(gè)進(jìn)程內(nèi)的多個(gè)線程并發(fā)執(zhí)行；而在多處理器系統(tǒng)中，則能同時(shí)將多個(gè)線程分配到各個(gè)處理器上并行執(zhí)行；因此，內(nèi)核支持線程比較適合多處理器系統(tǒng)。（2）在引入內(nèi)核支持線程的操作系統(tǒng)中，一個(gè)線程因等待某個(gè)事件而阻塞不會(huì)影響其他線程執(zhí)行。（3）內(nèi)核支持線程本身只使用了很小的數(shù)據(jù)結(jié)構(gòu)和堆棧，切換速度較快，加之內(nèi)核本身也可以采用多線程技術(shù)實(shí)現(xiàn)。2025/2/182.3.4線程的分類68這種方法的缺點(diǎn)是線程運(yùn)行在用戶態(tài)，而線程的調(diào)度和管理由內(nèi)核實(shí)現(xiàn)，以至于同一進(jìn)程中的線程需要在用戶態(tài)和核心態(tài)之間來(lái)回切換，系統(tǒng)開銷較大。3．混合式線程混合式線程將上述用戶級(jí)與內(nèi)核級(jí)結(jié)合。在這種方式下，一方面內(nèi)核支持多線程的創(chuàng)建、調(diào)度和管理等操作，另一方面系統(tǒng)為用戶提供一個(gè)線程庫(kù)，允許用戶程序建立、調(diào)度和管理用戶級(jí)線程。2025/2/182.3.5多核和多線程69所謂多核是將兩個(gè)或多個(gè)完整的CPU，通常稱為核（core）,放到同一芯片上（技術(shù)上來(lái)說是同一小硅片）。2025/2/182.3.5多核和多線程70這樣的設(shè)計(jì)結(jié)果是多核芯片就相當(dāng)于小的多處理機(jī)。實(shí)際上，多核芯片時(shí)常被稱為片級(jí)多處理機(jī)（Chip-levelMultiProcessors，CMP）。從軟件的角度來(lái)看，CMP與基于總線的多處理機(jī)和使用交換網(wǎng)絡(luò)的多處理機(jī)并沒有太大的差別。不過它們還是存在著若干的差別。例如，基于總線的多處理機(jī)，每個(gè)CPU擁有自己的高速緩存，因特爾使用的共享高速緩存的設(shè)計(jì)并沒有出現(xiàn)在其它的多處理器中。CMP與其它多處理器的另一個(gè)差異是容錯(cuò)。因?yàn)镃PU之間的連接非常緊密，一個(gè)共享模塊的失效可能導(dǎo)致許多CPU同時(shí)出錯(cuò)。而這樣的情況在傳統(tǒng)的多處理機(jī)中是很少出現(xiàn)的。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)

2.4.2調(diào)度算法的目標(biāo)

2.4.3批處理作業(yè)調(diào)度

2.4.4交互系統(tǒng)進(jìn)程調(diào)度

2.4.5實(shí)時(shí)系統(tǒng)進(jìn)程調(diào)度

2.4.6線程調(diào)度

2.4處理器調(diào)度712.4.1調(diào)度的功能與時(shí)機(jī)72

在操作系統(tǒng)中完成選擇工作的那一部分稱為調(diào)度程序（scheduler）,該程序使用的算法稱為調(diào)度算法（schedulingalgorithm）。現(xiàn)代操作系統(tǒng)中，按照調(diào)度所實(shí)現(xiàn)的功能來(lái)分，通常把處理器分配給進(jìn)程或線程的調(diào)度稱為低級(jí)調(diào)度，除此之外，還有中級(jí)調(diào)度和高級(jí)調(diào)度，它們一起構(gòu)成三級(jí)調(diào)度體系。其中，低級(jí)調(diào)度是該體系中不可缺少的最基本調(diào)度。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)731．高級(jí)調(diào)度作業(yè)是一個(gè)比程序更廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來(lái)對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。作業(yè)通常分成若干個(gè)既相對(duì)獨(dú)立又互相關(guān)聯(lián)的加工步驟，每個(gè)步驟稱為一個(gè)作業(yè)步。每個(gè)作業(yè)步可能對(duì)應(yīng)一個(gè)或多個(gè)進(jìn)程。2025/2/18作業(yè)和作業(yè)步

(1)作業(yè)(Job)：程序、數(shù)據(jù)和作業(yè)說明書

(2)作業(yè)步(JobStep)：在一個(gè)作業(yè)的處理過程中，計(jì)算機(jī)所做的相對(duì)獨(dú)立的工作，即加工步驟

(3)作業(yè)流：若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流2.4.1調(diào)度的功能與時(shí)機(jī)

2.4.1調(diào)度的功能與時(shí)機(jī)75作業(yè)一般要經(jīng)歷“提交”、“后備”、“執(zhí)行”和“完成”4個(gè)狀態(tài)。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)76

高級(jí)調(diào)度（HighLevelScheduling）又稱作業(yè)調(diào)度或長(zhǎng)程調(diào)度，它是根據(jù)某種算法將外存上處于后備作業(yè)隊(duì)列中的若干作業(yè)調(diào)入內(nèi)存，為作業(yè)分配所需資源并建立相應(yīng)進(jìn)程。

高級(jí)調(diào)度決定允許哪些作業(yè)可進(jìn)入內(nèi)存，參與競(jìng)爭(zhēng)CPU和系統(tǒng)其它資源，將一個(gè)或一批作業(yè)從后備狀態(tài)變?yōu)閳?zhí)行狀態(tài)。被高級(jí)調(diào)度程序選中的作業(yè)可獲得基本內(nèi)存和相應(yīng)的系統(tǒng)資源，系統(tǒng)為之創(chuàng)建相應(yīng)的進(jìn)程。此后，該作業(yè)以進(jìn)程的形式參與并發(fā)執(zhí)行，同其它進(jìn)程競(jìng)爭(zhēng)CPU。高級(jí)調(diào)度為中級(jí)調(diào)度和低級(jí)調(diào)度做好了前期準(zhǔn)備。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)77在多道批處理系統(tǒng)中，為了管理和調(diào)度作業(yè)，系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊(JobControlBlock，JCB)，它記錄作業(yè)的相關(guān)信息。作業(yè)控制塊是作業(yè)存在的標(biāo)志，只有作業(yè)執(zhí)行完成或中途退出系統(tǒng)時(shí)，作業(yè)控制塊才被撤銷。在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)78

2．中級(jí)調(diào)度

中級(jí)調(diào)度(IntermediateLevelscheduling)又稱內(nèi)存調(diào)度，它是進(jìn)程在內(nèi)存和外存之間的對(duì)換，引入中級(jí)調(diào)度的目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量，控制系統(tǒng)并發(fā)度，降低系統(tǒng)開銷。中級(jí)調(diào)度實(shí)際上是存儲(chǔ)管理中的對(duì)換功能，它控制進(jìn)程對(duì)主存的使用。在虛擬存儲(chǔ)管理系統(tǒng)中，進(jìn)程只有被中級(jí)調(diào)度選中，才有資格占用主存。中級(jí)調(diào)度可以控制進(jìn)程對(duì)主存的使用，從某種意義上講，中級(jí)調(diào)度可通過設(shè)定內(nèi)存中能夠接納的進(jìn)程數(shù)來(lái)平衡系統(tǒng)負(fù)載，在一定時(shí)間內(nèi)起到平衡和調(diào)整系統(tǒng)負(fù)載的作用。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)793．低級(jí)調(diào)度

低級(jí)調(diào)度(LowLevelscheduling)又稱進(jìn)程調(diào)度、短程調(diào)度，它決定哪個(gè)就緒態(tài)進(jìn)程獲得處理器，即選擇某個(gè)進(jìn)程從就緒態(tài)變?yōu)閳?zhí)行態(tài)。執(zhí)行低級(jí)調(diào)度的原因多是處于執(zhí)行態(tài)的進(jìn)程由于某種原因放棄或被剝奪處理機(jī)。進(jìn)程調(diào)度的功能主要包括以下兩部分。（1）選擇就緒進(jìn)程。動(dòng)態(tài)查找就緒狀態(tài)進(jìn)程隊(duì)列中各進(jìn)程的優(yōu)先級(jí)和資源(主要是內(nèi)存)使用情況，按照一定的進(jìn)程調(diào)度算法確定處理機(jī)的分配對(duì)象。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)80（2）進(jìn)程切換。進(jìn)程切換是處理器分配的具體實(shí)施過程。正在處理器上執(zhí)行的進(jìn)程釋放處理器，將調(diào)度程序選中的就緒態(tài)進(jìn)程切換到處理器上執(zhí)行。進(jìn)程調(diào)度是最基本的一種調(diào)度，它可以采用非搶占方式和搶占方式。（1）非搶占方式在這種方式下，一旦分派程序把處理機(jī)分配給某個(gè)進(jìn)程后，便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一進(jìn)程。2025/2/182.4.1調(diào)度的功能與時(shí)機(jī)81（2）搶占方式在這種方式下，某個(gè)進(jìn)程正在運(yùn)行時(shí)可以被系統(tǒng)以某種原則剝奪已分配給它的處理器，將處理器分配給其他進(jìn)程。在上述三級(jí)調(diào)度中，低級(jí)調(diào)度是各類操作系統(tǒng)必備的功能，在純粹的分時(shí)操作系統(tǒng)或?qū)崟r(shí)操作系統(tǒng)中，通常不需要高級(jí)調(diào)度；一般的操作系統(tǒng)都配置高級(jí)調(diào)度和低級(jí)調(diào)度；而功能完善的操作系統(tǒng)為了提高主存的利用率和作業(yè)吞吐量，引入了中級(jí)調(diào)度。2025/2/182.4.2調(diào)度算法的目標(biāo)82

如何選擇調(diào)度方式和算法很大程度上取決于操作系統(tǒng)的類型及其目標(biāo)，同時(shí)需要考慮用戶的要求和系統(tǒng)的總體性能。1．面向用戶（1）周轉(zhuǎn)時(shí)間短：用戶等待輸出的時(shí)間短。

周轉(zhuǎn)時(shí)間：從作業(yè)提交給系統(tǒng)到作業(yè)完成為止的這段時(shí)間間隔。

周轉(zhuǎn)時(shí)間包括四部分：作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間+進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間+進(jìn)程在CPU上執(zhí)行的時(shí)間+以及進(jìn)程等待I/O操作完成的時(shí)間。一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間等于作業(yè)的完成時(shí)間-到達(dá)時(shí)間，或者是執(zhí)行時(shí)間+等待時(shí)間。2025/2/182.4.2調(diào)度算法的目標(biāo)832025/2/18

每個(gè)用戶都希望自己作業(yè)的周轉(zhuǎn)時(shí)間盡可能的短。但是對(duì)于一個(gè)計(jì)算機(jī)系統(tǒng)而言，總是希望能是所有任務(wù)的平均周轉(zhuǎn)時(shí)間最短。平均周轉(zhuǎn)時(shí)間的定義為：，其中n為作業(yè)數(shù)，Ti為第i個(gè)作業(yè)周轉(zhuǎn)時(shí)間。在周轉(zhuǎn)時(shí)間里，一個(gè)執(zhí)行時(shí)間長(zhǎng)的作業(yè)和執(zhí)行時(shí)間短的作業(yè)去直接比較周轉(zhuǎn)時(shí)間是不公平的，所以提出了帶權(quán)周轉(zhuǎn)時(shí)間，即作業(yè)的周轉(zhuǎn)時(shí)間T與作業(yè)的執(zhí)行時(shí)間Ts之比：稱為作業(yè)i的帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間可表示為：。2.4.2調(diào)度算法的目標(biāo)84（2）響應(yīng)時(shí)間快，即用戶交互快捷。響應(yīng)時(shí)間是指從提交一個(gè)請(qǐng)求到開始接受響應(yīng)之間的這段時(shí)間。（3）截止時(shí)間保證。截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)度算法時(shí)，可以將急需處理的作業(yè)設(shè)置成較高的優(yōu)先權(quán)，然后根據(jù)優(yōu)先權(quán)高低選擇調(diào)度，使得優(yōu)先權(quán)高的作業(yè)能得到及時(shí)的處理。在實(shí)時(shí)系統(tǒng)中，有時(shí)為了確保作業(yè)能被及時(shí)處理，還需要選擇搶占式的調(diào)度方式。2025/2/182.4.2調(diào)度算法的目標(biāo)852．面向系統(tǒng)（1）資源利用率高。使得CPU或其他資源能夠并行工作，并且資源的利用率盡可能高。由于CPU價(jià)格昂貴，致使CPU的利用率成為衡量系統(tǒng)性能的十分重要的指標(biāo)。CPU的利用率＝CPU有效工作時(shí)間／CPU總的運(yùn)行時(shí)間。CPU總的運(yùn)行時(shí)間＝CPU有效工作時(shí)間十CPU空閑等待時(shí)間。（2）系統(tǒng)吞吐量高。吞吐量是單位時(shí)間內(nèi)處理的作業(yè)數(shù)。這是選擇批處理系統(tǒng)性能的一個(gè)重要指標(biāo)。（3）公平性。確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份額或其他資源份額，不會(huì)出現(xiàn)餓死的情況。2025/2/182.4.3批處理作業(yè)調(diào)度861．先來(lái)先服務(wù)先來(lái)先服務(wù)(First-comeFirst-served，F(xiàn)CFS)調(diào)度算法是最簡(jiǎn)單的一種調(diào)度算法，它不僅可以用于高級(jí)調(diào)度，也可以用于低級(jí)調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次從作業(yè)后備隊(duì)列中選擇一個(gè)等待時(shí)間最長(zhǎng)的作業(yè)調(diào)入內(nèi)存，并為其分配資源，建立進(jìn)程，然后放入就緒隊(duì)列。這是一種非剝奪式調(diào)度算法，易于實(shí)現(xiàn)，但效率不高。只顧及作業(yè)的等候時(shí)間，不考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短，不利于短作業(yè)而優(yōu)待長(zhǎng)作業(yè)。2025/2/182.4.3批處理作業(yè)調(diào)度87例表給出了五個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)間、運(yùn)行時(shí)間，給出作業(yè)的調(diào)度順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2025/2/182.4.3批處理作業(yè)調(diào)度88解：作業(yè)的調(diào)度順序：A-->B-->C-->D-->E作業(yè)的周轉(zhuǎn)時(shí)間：

作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間：

作業(yè)的平均周轉(zhuǎn)時(shí)間：作業(yè)的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.3批處理作業(yè)調(diào)度892．短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法(ShortJobFirst，SJF)是以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU運(yùn)行時(shí)間的長(zhǎng)短為標(biāo)準(zhǔn)，總是選取預(yù)計(jì)計(jì)算時(shí)間最短的作業(yè)優(yōu)先調(diào)度的算法。其從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短作業(yè)優(yōu)先調(diào)度算法是一種非搶占式的調(diào)度算法，能夠克服FCFS算法的缺點(diǎn)，易于實(shí)現(xiàn)，但執(zhí)行效率不高。2025/2/182.4.3批處理作業(yè)調(diào)度90短作業(yè)優(yōu)先調(diào)度算法存在的缺點(diǎn)。（1）該算法對(duì)長(zhǎng)作業(yè)不利。（2）該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會(huì)被及時(shí)處理。（3）由于作業(yè)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。2025/2/182.4.3批處理作業(yè)調(diào)度91按照SJF算法給出表作業(yè)的執(zhí)行順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2025/2/182.4.3批處理作業(yè)調(diào)度92解：作業(yè)的調(diào)度順序：A-->D-->B-->E-->C作業(yè)的周轉(zhuǎn)時(shí)間：

作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間：

作業(yè)的平均周轉(zhuǎn)時(shí)間：作業(yè)的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.3批處理作業(yè)調(diào)度933．高響應(yīng)比調(diào)度算法高響應(yīng)比優(yōu)先(HighestResponseRatioNext，HRRN)調(diào)度算法是對(duì)FCFS調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法的一種綜合平衡。

FCFS算法只考慮等待時(shí)間而未考慮運(yùn)行時(shí)間的長(zhǎng)短短作業(yè)優(yōu)先調(diào)度算法只考慮運(yùn)行時(shí)間而未考慮等待時(shí)間的長(zhǎng)短。因此這兩種調(diào)度算法在某些情況下都有不足之處。2025/2/182.4.3批處理作業(yè)調(diào)度94高響應(yīng)比優(yōu)先調(diào)度算法中的優(yōu)先權(quán)的變化規(guī)律可描述為：從上面的公式可以看出：（1）如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)越高，因此該算法在等待時(shí)間相同的作業(yè)中會(huì)選擇短作業(yè)，有利于短作業(yè)。2025/2/182.4.3批處理作業(yè)調(diào)度95（2）當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間越長(zhǎng)，其優(yōu)先權(quán)越高，因此對(duì)運(yùn)行時(shí)間相同的作業(yè)該算法會(huì)選擇等待時(shí)間長(zhǎng)的作業(yè)，即類似于先來(lái)先服務(wù)。（3）對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)。因此對(duì)長(zhǎng)作業(yè)而言，不會(huì)出現(xiàn)“饑餓”現(xiàn)象。總之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。2025/2/182.4.3批處理作業(yè)調(diào)度96例2-3按照HRRN算法給出表作業(yè)的執(zhí)行順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2025/2/182.4.3批處理作業(yè)調(diào)度97解：開始時(shí)只有作業(yè)A，作業(yè)A被選中，執(zhí)行時(shí)間4；作業(yè)A執(zhí)行完畢后，B，C，D，E的響應(yīng)比依次為6/3，7/5，3/2，4/4，作業(yè)B被選中，執(zhí)行時(shí)間3；作業(yè)B執(zhí)行完畢后，C，D，E的響應(yīng)比依次為10/5，6/2，7/4，作業(yè)D被選中，執(zhí)行時(shí)間2；作業(yè)D執(zhí)行完畢后，C，E的響應(yīng)比依次為12/5，9/4，作業(yè)C被選中，執(zhí)行時(shí)間5；最后作業(yè)E被選中，執(zhí)行時(shí)間4。所以有2025/2/182.4.3批處理作業(yè)調(diào)度98作業(yè)的調(diào)度順序：A-->B-->D-->C-->E作業(yè)的周轉(zhuǎn)時(shí)間：

作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間：

作業(yè)的平均周轉(zhuǎn)時(shí)間：作業(yè)的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度991．時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)法調(diào)度（RoundRobin，RR）也稱為時(shí)間片調(diào)度或輪轉(zhuǎn)調(diào)度，是分時(shí)系統(tǒng)中采用的調(diào)度算法，其基本思想是為每一個(gè)進(jìn)程分配一個(gè)時(shí)間段，該時(shí)間段被稱為時(shí)間片，即允許該進(jìn)程運(yùn)行的時(shí)間，通常情況下時(shí)間片的大小為幾十到幾百毫秒。時(shí)間片輪轉(zhuǎn)算法是一種搶占式調(diào)度算法。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度100例2-4當(dāng)時(shí)間片是1和4時(shí)，按照RR算法給出表2-2進(jìn)程的執(zhí)行順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度101解：時(shí)間片為1時(shí)進(jìn)程的執(zhí)行順序：進(jìn)程的周轉(zhuǎn)時(shí)間：

進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間：

進(jìn)程的平均周轉(zhuǎn)時(shí)間：進(jìn)程的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度102時(shí)間片為4時(shí)進(jìn)程的執(zhí)行順序

進(jìn)程的周轉(zhuǎn)時(shí)間：進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間：

進(jìn)程的平均周轉(zhuǎn)時(shí)間：進(jìn)程的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度1032．優(yōu)先級(jí)調(diào)度算法高優(yōu)先級(jí)調(diào)度算法的基本思想是：當(dāng)發(fā)生調(diào)度時(shí)，總是調(diào)度當(dāng)前處于就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程，使之獲得處理機(jī)。在這種算法中存在兩種方式；非搶占式優(yōu)先權(quán)調(diào)度算法和搶占式優(yōu)先權(quán)調(diào)度算法。而根據(jù)優(yōu)先權(quán)的類型，又可分為靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)。

非搶占式優(yōu)先級(jí)調(diào)度方式規(guī)定系統(tǒng)如果把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程將持續(xù)獲得CPU的使用權(quán)，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一個(gè)進(jìn)程。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度104

搶占式優(yōu)先級(jí)調(diào)度方式規(guī)定首先把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使該進(jìn)程占用CPU執(zhí)行。但在其執(zhí)行期間，如果系統(tǒng)中進(jìn)入了一個(gè)優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程（原優(yōu)先權(quán)最高的進(jìn)程）的執(zhí)行，重新將處理器分配給新到的優(yōu)先級(jí)最高的進(jìn)程。這種調(diào)度方式的優(yōu)點(diǎn)是能更好地滿足緊迫作業(yè)的要求，因此適用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)。在優(yōu)先級(jí)調(diào)度算法中，進(jìn)程的優(yōu)先級(jí)一般由優(yōu)先數(shù)決定。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度105靜態(tài)優(yōu)先數(shù)是指進(jìn)程在創(chuàng)建時(shí)就獲得一個(gè)整數(shù)數(shù)值，此數(shù)值在進(jìn)程的整個(gè)運(yùn)行過程中固定不變。優(yōu)先數(shù)的大小反映進(jìn)程優(yōu)先級(jí)的高低。有的系統(tǒng)規(guī)定越大的優(yōu)先數(shù)其優(yōu)先級(jí)越高，當(dāng)然也可以反過來(lái)規(guī)定。優(yōu)先數(shù)的決定一般取決于進(jìn)程類型，資源需求量，緊迫程度和用戶需求等。動(dòng)態(tài)優(yōu)先數(shù)是指進(jìn)程的優(yōu)先級(jí)隨著進(jìn)程的推進(jìn)可以動(dòng)態(tài)改變。現(xiàn)代操作系統(tǒng)中，采用優(yōu)先級(jí)調(diào)度算法的系統(tǒng)大多使用的是動(dòng)態(tài)優(yōu)先數(shù)的策略。動(dòng)態(tài)優(yōu)先數(shù)的選擇可以根據(jù)進(jìn)程占有CPU的時(shí)間長(zhǎng)短以及就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)短來(lái)確定。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度106例表2-3給出五個(gè)進(jìn)程到達(dá)就緒隊(duì)列是時(shí)間、執(zhí)行時(shí)間和優(yōu)先數(shù)，優(yōu)先數(shù)越大優(yōu)先級(jí)越高，按照優(yōu)先級(jí)調(diào)度算法采用搶占方式給出進(jìn)程的執(zhí)行順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2025/2/18進(jìn)程號(hào)ABCDE到達(dá)時(shí)間01234服務(wù)時(shí)間43524優(yōu)先數(shù)124352.4.4交互系統(tǒng)進(jìn)程調(diào)度107解：進(jìn)程的執(zhí)行順序進(jìn)程的周轉(zhuǎn)時(shí)間：進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間：

進(jìn)程的平均周轉(zhuǎn)時(shí)間：進(jìn)程的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度1083．多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度(Multi-LevelFeedbackQueue，MLFQ)又被稱為反饋循環(huán)隊(duì)列。2025/2/18說明將就緒隊(duì)列分為N級(jí)，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，時(shí)間片越短，級(jí)別越低，時(shí)間片越長(zhǎng)；系統(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谝患?jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，.....當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片，放棄CPU時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列末尾。

2.4.4交互系統(tǒng)進(jìn)程調(diào)度

2.4.4交互系統(tǒng)進(jìn)程調(diào)度110（1）終端型用戶。終端型用戶（分時(shí)交互型）所提交的大多屬于交互型，這種類型的進(jìn)程通常比較小，系統(tǒng)只要能使這些進(jìn)程在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，就可以使終端型用戶感到滿意。（2）短批處理用戶。短批處理進(jìn)程只需僅在第一隊(duì)列或在第一、第二隊(duì)列中各執(zhí)行一個(gè)時(shí)間片就能完成工作，周轉(zhuǎn)時(shí)間仍然很短。（3）長(zhǎng)批處理用戶。假如一個(gè)長(zhǎng)進(jìn)程進(jìn)入內(nèi)存，它最終必將移入優(yōu)先級(jí)最低的就緒隊(duì)列中，如果其后有源源不斷的短進(jìn)程進(jìn)入內(nèi)存，則長(zhǎng)進(jìn)程一直等待，陷入“饑餓”狀態(tài)。2025/2/182.4.4交互系統(tǒng)進(jìn)程調(diào)度111例設(shè)系統(tǒng)中有3個(gè)就緒隊(duì)列，第一個(gè)隊(duì)列的時(shí)間片為1，第二個(gè)隊(duì)列的時(shí)間片為2，第三個(gè)隊(duì)列的時(shí)間片為4。按照MLFQ算法給出表2-2進(jìn)程的執(zhí)行順序，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。解：進(jìn)程的執(zhí)行順序2025/2/18進(jìn)程號(hào)ABCDE到達(dá)時(shí)間01234服務(wù)時(shí)間435242.4處理器調(diào)度112進(jìn)程的周轉(zhuǎn)時(shí)間：

進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間：

進(jìn)程的平均周轉(zhuǎn)時(shí)間：進(jìn)程的平均帶權(quán)周轉(zhuǎn)時(shí)間：2025/2/182.4.5實(shí)時(shí)系統(tǒng)進(jìn)程調(diào)度113實(shí)時(shí)系統(tǒng)是一種時(shí)間起主導(dǎo)作用的系統(tǒng)，對(duì)時(shí)間有著嚴(yán)格的要求。在實(shí)時(shí)系統(tǒng)中，每