第3章 進(jìn)程與進(jìn)程管理

1、第3章 進(jìn)程與進(jìn)程管理,操作系統(tǒng)（第3版）,第3章 進(jìn)程與進(jìn)程管理,3.1 進(jìn)程的引入 3.2 進(jìn)程 3.3 進(jìn)程調(diào)度 3.4 線程的基本概念 3.5 Linux的進(jìn)程與進(jìn)程管理,3.1 進(jìn)程的引入,前趨圖的定義 前趨圖（Procedence Graph）是一個(gè)有向無(wú)循環(huán)圖（DAG）。圖中的每個(gè)結(jié)點(diǎn)可用于表示一條語(yǔ)句、一個(gè)程序段或進(jìn)程；結(jié)點(diǎn)間的有向邊則表示在兩結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“”，=(Pi，Pj)| Pi必須在Pj開(kāi)始前完成 。,3.1 進(jìn)程的引入,程序順序執(zhí)行 定義 程序在執(zhí)行時(shí)，必須按照某種先后次序逐個(gè)執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作 程序順序執(zhí)行的特征 程序執(zhí)行的

2、順序性 處理機(jī)的操作嚴(yán)格按程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后才能執(zhí)行后繼操作,3.1 進(jìn)程的引入,程序執(zhí)行的封閉性 程序一旦開(kāi)始運(yùn)行，其執(zhí)行結(jié)果不受外界因素的影響 程序執(zhí)行結(jié)果的確定性 程序執(zhí)行的結(jié)果與它的執(zhí)行速度、時(shí)間無(wú)關(guān) 程序結(jié)果的可再現(xiàn)性 程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序多次重復(fù)執(zhí)行時(shí)，都將獲得相同的結(jié)果,3.1 進(jìn)程的引入,程序并發(fā)執(zhí)行 定義 在上圖中的輸入程序、計(jì)算程序和打印程序三者之間，存在著IiCiPi這樣的前趨關(guān)系，以致對(duì)一個(gè)作業(yè)的輸入、計(jì)算和打印三個(gè)操作必須順序執(zhí)行，但并不存在PiIi+1關(guān)系，因而在對(duì)一批程序進(jìn)行處理時(shí)，可使它們并發(fā)執(zhí)行。,3.1 進(jìn)程的引入,程

3、序并發(fā)執(zhí)行特征 程序執(zhí)行的間斷性 程序執(zhí)行的相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行暫停執(zhí)行執(zhí)行”這種間斷性的活動(dòng)規(guī)律 程序執(zhí)行失去封閉性 因多個(gè)程序共享系統(tǒng)中的資源，所以某程序在執(zhí)行時(shí)必然會(huì)受到其他程序的影響,3.1 進(jìn)程的引入,程序執(zhí)行結(jié)果的不可再現(xiàn)性 由于失去了封閉性，也將導(dǎo)致失去其可再現(xiàn)性 資源共享 系統(tǒng)中的硬件資源和軟件資源不再被單個(gè)用戶或程序獨(dú)占，而為多個(gè)用戶或作業(yè)共同使用 程序和計(jì)算不再一一對(duì)應(yīng) 程序和計(jì)算是兩個(gè)不同的概念，在程序并發(fā)執(zhí)行中一個(gè)共享程序可對(duì)應(yīng)多個(gè)“計(jì)算”，程序與“計(jì)算”已不再一一對(duì)應(yīng),3.1 進(jìn)程的引入,多道程序設(shè)計(jì) 定義 在采用多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，允許多個(gè)程序同

4、時(shí)進(jìn)入一個(gè)計(jì)算機(jī)系統(tǒng)的內(nèi)存儲(chǔ)器并運(yùn)行，這種讓多個(gè)程序同時(shí)進(jìn)入計(jì)算機(jī)計(jì)算的方法稱為多道程序設(shè)計(jì)。 目的 提高處理器的效率，從而提高整個(gè)系統(tǒng)的效率 必須解決的問(wèn)題 存儲(chǔ)保護(hù)與程序浮動(dòng) 處理器的管理和調(diào)度 系統(tǒng)資源的管理和調(diào)度,3.2 進(jìn)程,引入進(jìn)程的原因 為了使程序在多道程序環(huán)境下能夠并發(fā)執(zhí)行，并對(duì)并發(fā)執(zhí)行的程序加以控制和描述，引入進(jìn)程的概念 程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成了一個(gè)進(jìn)程的實(shí)體 進(jìn)程的概念 進(jìn)程的定義 進(jìn)程是具有獨(dú)立功能的可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位。或者說(shuō)，“進(jìn)程”是進(jìn)程實(shí)體的運(yùn)行過(guò)程。,3.2 進(jìn)程,程序與進(jìn)程的區(qū)別與聯(lián)系 區(qū)

5、別: 進(jìn)程是程序的一次執(zhí)行，是一個(gè)動(dòng)態(tài)的概念，程序是完成某個(gè)特定功能的指令的有序序列，是一個(gè)靜態(tài)的概念 一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，同一程序也可能由多個(gè)進(jìn)程同時(shí)執(zhí)行 進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，程序則不是 程序可以作為一種軟件資源長(zhǎng)期保存，而進(jìn)程是程序的一次執(zhí)行過(guò)程，它是臨時(shí)的，有生命期的 進(jìn)程是具有結(jié)構(gòu)的 聯(lián)系:進(jìn)程是程序的運(yùn)行,3.2 進(jìn)程,進(jìn)程的特征 動(dòng)態(tài)性：進(jìn)程的基本特性。進(jìn)程是進(jìn)程實(shí)體的執(zhí)行過(guò)程； 并發(fā)性:進(jìn)程的主要特征。多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行； 獨(dú)立性：進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。

6、 異步性：進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)；或者說(shuō)，進(jìn)程按異步方式運(yùn)行。 結(jié)構(gòu)特征：從結(jié)構(gòu)上看，進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分組成，有人把這三部分統(tǒng)稱為“進(jìn)程映像”。,3.2 進(jìn)程,進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換 進(jìn)程的三種基本狀態(tài) 就緒狀態(tài) 當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源后，只要能再獲得處理機(jī)便可立即執(zhí)行，這時(shí)的狀態(tài)稱為就緒狀態(tài) 執(zhí)行狀態(tài) 指進(jìn)程已獲得處理機(jī)，其程序正在執(zhí)行 阻塞狀態(tài) 進(jìn)程因發(fā)生某種事件（如I/O請(qǐng)求、申請(qǐng)緩沖空間等）而暫停執(zhí)行時(shí)的狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，故稱這種狀態(tài)為阻塞狀態(tài)，有時(shí)也稱為“等待”狀態(tài)或“睡眠”狀態(tài)。 思考:剛剛創(chuàng)建的進(jìn)程應(yīng)該處

7、于哪種狀態(tài)?,3.2 進(jìn)程,進(jìn)程狀態(tài)的轉(zhuǎn)換 就緒執(zhí)行狀態(tài) 處于就緒狀態(tài)的進(jìn)程，當(dāng)進(jìn)程調(diào)度為之分配了處理機(jī)后 執(zhí)行阻塞狀態(tài) 正在執(zhí)行的進(jìn)程因發(fā)生某種事件而無(wú)法執(zhí)行 執(zhí)行就緒狀態(tài) 正在執(zhí)行的進(jìn)程如因時(shí)間片用完或一個(gè)優(yōu)先權(quán)高的進(jìn)程到來(lái)而被暫停執(zhí)行 阻塞就緒狀態(tài) 處于阻塞狀態(tài)的進(jìn)程，其等待的事件已經(jīng)發(fā)生 思考:其他狀態(tài)轉(zhuǎn)換可以存在嗎?,3.2 進(jìn)程,3.2 進(jìn)程,進(jìn)程的掛起狀態(tài) 掛起狀態(tài)的引入 終端用戶的需要 當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問(wèn)題時(shí)，往往希望暫時(shí)使自己的進(jìn)程靜止下來(lái)。 父進(jìn)程的需要 父進(jìn)程常常希望考察和修改子進(jìn)程或者當(dāng)要協(xié)調(diào)各子進(jìn)程間的活動(dòng) 操作系統(tǒng)的需要 操作系統(tǒng)有時(shí)需要掛起

8、某些進(jìn)程，檢查運(yùn)行中資源的使用情況及進(jìn)行記賬，以便改善系統(tǒng)運(yùn)行的性能。,3.2 進(jìn)程,對(duì)換的需要 為了緩解內(nèi)存緊張的情況，即將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程換至輔存上，使進(jìn)程又處于一種有別于阻塞狀態(tài)的新?tīng)顟B(tài)。 負(fù)荷調(diào)節(jié)的需要 進(jìn)程狀態(tài)的轉(zhuǎn)換 在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱靜止?fàn)顟B(tài)）到非掛起狀態(tài)（又稱活動(dòng)狀態(tài)）的轉(zhuǎn)換 活動(dòng)就緒靜止就緒 活動(dòng)阻塞靜止阻塞 靜止就緒活動(dòng)就緒 靜止阻塞活動(dòng)阻塞,3.2 進(jìn)程,進(jìn)程控制塊PCB 進(jìn)程控制塊的作用 進(jìn)程控制塊記錄進(jìn)程信息 操作系統(tǒng)是根據(jù)進(jìn)程控制塊PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的 PCB是進(jìn)程存在的唯一標(biāo)志 思考:進(jìn)程控制塊應(yīng)該存放在何處?需要

9、存放在磁盤中嗎? 進(jìn)程控制塊中的信息 進(jìn)程標(biāo)識(shí)符信息 進(jìn)程標(biāo)識(shí)符用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程，通常有外部標(biāo)識(shí)符和內(nèi)部標(biāo)識(shí)符,3.2 進(jìn)程,外部標(biāo)識(shí)符。由創(chuàng)建者提供，通常由字母、數(shù)字所組成，往往是由用戶（進(jìn)程）在訪問(wèn)該進(jìn)程時(shí)使用。 內(nèi)部標(biāo)識(shí)符。這是為了方便系統(tǒng)使用而設(shè)置的。在所有操作系統(tǒng)中都為每一個(gè)進(jìn)程賦予一個(gè)惟一的整數(shù)作為內(nèi)部標(biāo)識(shí)符，它通常就是一個(gè)進(jìn)程的序號(hào)。 處理機(jī)狀態(tài)信息 處理機(jī)狀態(tài)信息主要是由處理機(jī)各種寄存器中的內(nèi)容所組成 ：通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字PSW、用戶棧指針。 進(jìn)程調(diào)度信息 存放了一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息：進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級(jí)、進(jìn)程調(diào)度所需的其他信息、事件。,3.

10、2 進(jìn)程,進(jìn)程控制信息 程序和數(shù)據(jù)的地址、 進(jìn)程同步和通信機(jī)制、資源清單、鏈接指針。 PCB的組織方式 - 鏈接方式 把具有相同狀態(tài)的PCB鏈接成一個(gè)隊(duì)列，這樣可形成就緒隊(duì)列、若干個(gè)阻塞隊(duì)列和空隊(duì)列等 - 索引方式 系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表,思考:你認(rèn)為圖中缺少什么內(nèi)容嗎?,3.2 進(jìn)程,進(jìn)程控制 進(jìn)程控制的主要任務(wù)是創(chuàng)建和撤消進(jìn)程以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換，進(jìn)程控制一般由操作系統(tǒng)的內(nèi)核來(lái)實(shí)現(xiàn)。操作系統(tǒng)內(nèi)核通常是運(yùn)行在系統(tǒng)態(tài)的。 操作系統(tǒng)內(nèi)核 定義 通常，將一些與硬件緊密相關(guān)的模塊諸如中斷處理程序、各種常用設(shè)備的驅(qū)動(dòng)程序以及運(yùn)行頻率較高的模塊都安排在緊靠硬件的軟件層次中并使它們常駐內(nèi)存

11、，以便提高操作系統(tǒng)的運(yùn)行效率，并對(duì)它們加以特殊的保護(hù)，把這一部分稱為操作系統(tǒng)的內(nèi)核,3.2 進(jìn)程,操作系統(tǒng)內(nèi)核的功能 中斷處理：中斷處理功能在操作系統(tǒng)中，既是內(nèi)核的最基本功能，也是整個(gè)操作系統(tǒng)賴以活動(dòng)的基礎(chǔ)，即操作系統(tǒng)的重要活動(dòng)最終都將依賴于中斷。 進(jìn)程管理：進(jìn)程創(chuàng)建、撤消、進(jìn)程狀態(tài)的轉(zhuǎn)換 、進(jìn)程調(diào)度等。 資源管理中的基本操作：包括對(duì)時(shí)鐘、I/O設(shè)備和文件系統(tǒng)進(jìn)行控制和管理的基本操作。 原子操作 所謂原子操作是指：一個(gè)操作中的所有動(dòng)作，要么全做，要么全不做。換言之，原子操作是一個(gè)不可分割的操作 內(nèi)核在執(zhí)行上述操作時(shí)，往往是通過(guò)執(zhí)行各種原語(yǔ)操作來(lái)實(shí)現(xiàn)的。,3.2 進(jìn)程,進(jìn)程的創(chuàng)建 進(jìn)程圖 進(jìn)程圖

12、是用于描述進(jìn)程家族關(guān)系的有向樹 子進(jìn)程可以繼承父進(jìn)程所擁有的資源，當(dāng)子進(jìn)程撤銷時(shí)，應(yīng)將從父進(jìn)程那里獲得的資源歸還給父進(jìn)程；在撤銷父進(jìn)程時(shí)，也必須同時(shí)撤銷其所有的子進(jìn)程 引起創(chuàng)建進(jìn)程的事件 用戶登錄 作業(yè)調(diào)度 提供服務(wù) 應(yīng)用請(qǐng)求,3.2 進(jìn)程,進(jìn)程的創(chuàng)建過(guò)程 調(diào)用進(jìn)程創(chuàng)建原語(yǔ)create( )創(chuàng)建進(jìn)程 申請(qǐng)空白PCB 為新進(jìn)程分配資源 初始化進(jìn)程控制塊 將新進(jìn)程插入就緒隊(duì)列 思考:前兩步驟是否可以顛倒順序?,3.2 進(jìn)程,進(jìn)程的終止 引起進(jìn)程終止的事件 - 正常結(jié)束 - 異常結(jié)束 - 外界干預(yù) 進(jìn)程的終止過(guò)程 調(diào)用進(jìn)程終止原語(yǔ)destroy( )終止進(jìn)程 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符從PCB集合中檢索

13、出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài) 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行并設(shè)置調(diào)度標(biāo)志為真,3.2 進(jìn)程,若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止 將該進(jìn)程所擁有的全部資源，或者歸還其父進(jìn)程或者歸還給系統(tǒng) 釋放進(jìn)程的PCB 進(jìn)程的阻塞與喚醒 引起進(jìn)程阻塞和喚醒的事件 - 請(qǐng)求系統(tǒng)服務(wù) - 啟動(dòng)某種操作 - 新數(shù)據(jù)尚未到達(dá) - 無(wú)新工作可作,3.2 進(jìn)程,進(jìn)程阻塞過(guò)程 進(jìn)程便通過(guò)調(diào)用阻塞原語(yǔ)block（）把自己阻塞 立即停止當(dāng)前進(jìn)程的執(zhí)行 把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”，并把它插入到阻塞隊(duì)列 思考:是否轉(zhuǎn)向進(jìn)程調(diào)度? 進(jìn)程喚醒過(guò)程 調(diào)用喚醒原語(yǔ)wake

14、up( )將等待該事件的進(jìn)程喚醒 把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出 將其PCB中的現(xiàn)行狀態(tài)由“阻塞”改為“就緒” 然后再將該進(jìn)程插入到就緒隊(duì)列中,3.2 進(jìn)程,進(jìn)程的掛起與激活 進(jìn)程的掛起過(guò)程 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，系統(tǒng)就利用掛起原語(yǔ)suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起 檢查被掛起進(jìn)程的狀態(tài)，若正處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將其改為靜止阻塞 進(jìn)程保存于外存對(duì)換區(qū) 如被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)度,3.2 進(jìn)程,進(jìn)程的激活過(guò)程 當(dāng)發(fā)生激活進(jìn)程的事件時(shí)系統(tǒng)將利用激活原語(yǔ)active( )將指定進(jìn)程激活 將進(jìn)程從外存調(diào)

15、入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)：若是靜止就緒，便將其改為活動(dòng)就緒；若為靜止阻塞，便將其改為活動(dòng)阻塞 假如采用的是搶占調(diào)度策略 ，檢查是否要進(jìn)行重新調(diào)度,3.3 進(jìn)程調(diào)度,調(diào)度的基本概念 高級(jí)、中級(jí)和低級(jí)調(diào)度 一個(gè)作業(yè)從提交開(kāi)始直到完成，往往要經(jīng)歷三級(jí)調(diào)度： 高級(jí)調(diào)度又稱為作業(yè)調(diào)度，它決定將哪些在外存上處于后備狀態(tài)的作業(yè)調(diào)入主機(jī)內(nèi)存，準(zhǔn)備執(zhí)行 低級(jí)調(diào)度又稱為進(jìn)程調(diào)度。它決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，并實(shí)際執(zhí)行將處理機(jī)分配給該進(jìn)程的操作 在有的系統(tǒng)中，可能增加一中級(jí)調(diào)度，主要作用是在內(nèi)存和外存對(duì)換區(qū)之間進(jìn)行進(jìn)程對(duì)換，以解決內(nèi)存緊張問(wèn)題,3.3 進(jìn)程調(diào)度,進(jìn)程調(diào)度的功能 進(jìn)程調(diào)度就是系統(tǒng)按照某種

16、算法把CPU動(dòng)態(tài)地分配給某一就緒進(jìn)程。進(jìn)程調(diào)度工作是通過(guò)進(jìn)程調(diào)度程序來(lái)完成的。 進(jìn)程調(diào)度程序的主要功能： 選擇進(jìn)程占有CPU 進(jìn)行進(jìn)程上下文的切換,3.3 進(jìn)程調(diào)度,調(diào)度方式 非剝奪方式 分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件（如提出I/O請(qǐng)求）而阻塞時(shí)才把處理機(jī)分配給另一進(jìn)程 優(yōu)點(diǎn)：簡(jiǎn)單，系統(tǒng)開(kāi)銷小， 缺點(diǎn)：貌似公正,可能導(dǎo)致系統(tǒng)性能的惡化 剝奪方式 該方式規(guī)定，當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程 剝奪原則：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則,3.3 進(jìn)程調(diào)度,進(jìn)程調(diào)度算法 先進(jìn)先出（FIFO）算

17、法 算法：把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程 優(yōu)點(diǎn)：易于實(shí)現(xiàn) 缺點(diǎn)：表面上公平，服務(wù)質(zhì)量不佳 、對(duì)短進(jìn)程不利 思考:算法實(shí)現(xiàn) 最短CPU運(yùn)行期優(yōu)先調(diào)度算法 算法：從就緒隊(duì)列中選出“下一個(gè)CPU執(zhí)行期”最短的進(jìn)程，為之分配處理機(jī)使之執(zhí)行 優(yōu)點(diǎn)：可獲得較好的調(diào)度性能 缺點(diǎn)： 進(jìn)程的CPU執(zhí)行期難以準(zhǔn)確得到、對(duì)長(zhǎng)進(jìn)程不利,3.3 進(jìn)程調(diào)度,最高響應(yīng)比優(yōu)先調(diào)度算法 算法：響應(yīng)比=（等待時(shí)間+要求的服務(wù)時(shí)間）/要求的服務(wù)時(shí)間 ，每次選取響應(yīng)比最高的進(jìn)程調(diào)度 優(yōu)點(diǎn)：所以對(duì)短進(jìn)程有利，并且考慮了等待時(shí)間 缺點(diǎn)：計(jì)算響應(yīng)比有一定的系統(tǒng)開(kāi)銷 優(yōu)先級(jí)調(diào)度算法 算法：將CPU分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程 靜態(tài)

18、優(yōu)先級(jí) 在進(jìn)程創(chuàng)建時(shí)確立，確定后運(yùn)行期間保持不變。確立依據(jù)有：進(jìn)程的類型、進(jìn)程對(duì)資源的需求、用戶申請(qǐng)的優(yōu)先級(jí) 優(yōu)點(diǎn)：簡(jiǎn)單 缺點(diǎn)：不能動(dòng)態(tài)反映進(jìn)程特點(diǎn)，系統(tǒng)調(diào)度性能差,3.3 進(jìn)程調(diào)度,動(dòng)態(tài)優(yōu)先級(jí) 進(jìn)程在開(kāi)始創(chuàng)建時(shí)，根據(jù)某種原則確定一個(gè)優(yōu)先級(jí)后，隨著進(jìn)程執(zhí)行時(shí)間的變化，其優(yōu)先級(jí)不斷地進(jìn)行動(dòng)態(tài)調(diào)整 確定依據(jù)：根據(jù)進(jìn)程占有的CPU時(shí)間的長(zhǎng)短來(lái)決定，占有時(shí)間越長(zhǎng)優(yōu)先級(jí)越低；根據(jù)進(jìn)程等待CPU的時(shí)間來(lái)決定，時(shí)間越長(zhǎng)優(yōu)先級(jí)越高,3.3 進(jìn)程調(diào)度,時(shí)間片輪轉(zhuǎn)調(diào)度算法 算法：通常用在分時(shí)系統(tǒng)，它輪流地調(diào)度系統(tǒng)中所有就緒進(jìn)程，使就緒進(jìn)程依次獲得一個(gè)時(shí)間片的運(yùn)行時(shí)間 時(shí)間片長(zhǎng)短確定遵循原則 既要保證系統(tǒng)各個(gè)用戶進(jìn)

19、程及時(shí)地得到響應(yīng)，又不要由于時(shí)間片太短而增加調(diào)度的開(kāi)銷，降低系統(tǒng)的效率,3.3 進(jìn)程調(diào)度,進(jìn)程依次執(zhí)行時(shí)可能發(fā)生的三種情況 進(jìn)程未用完一個(gè)時(shí)間片便結(jié)束，這時(shí)系統(tǒng)應(yīng)提前進(jìn)行調(diào)度 進(jìn)程在執(zhí)行過(guò)程中提出I/O請(qǐng)求而阻塞，系統(tǒng)應(yīng)將它放入相應(yīng)的阻塞隊(duì)列并引起調(diào)度 進(jìn)程用完一個(gè)時(shí)間片后尚未完成。系統(tǒng)應(yīng)將它重新放到就緒隊(duì)列的末尾，等待下次執(zhí)行,3.3 進(jìn)程調(diào)度,3.3 進(jìn)程調(diào)度,前后臺(tái)調(diào)度算法 算法：該方法用在批處理和分時(shí)相結(jié)合的系統(tǒng)中。將分時(shí)用戶作業(yè)放在前臺(tái)，把批處理作業(yè)放在后臺(tái)。系統(tǒng)對(duì)前臺(tái)作業(yè)按照時(shí)間片輪轉(zhuǎn)法進(jìn)行調(diào)度，僅當(dāng)前臺(tái)無(wú)作業(yè)時(shí)，才把處理機(jī)分配給后臺(tái)作業(yè)的進(jìn)程。后臺(tái)進(jìn)程通常按先來(lái)先服務(wù)方式運(yùn)行 優(yōu)

20、點(diǎn)：使分時(shí)用戶進(jìn)程得到及時(shí)響應(yīng)，又提高了系統(tǒng)資源的利用率,3.3 進(jìn)程調(diào)度,多級(jí)反饋隊(duì)列輪轉(zhuǎn)算法 系統(tǒng)設(shè)置多個(gè)不同優(yōu)先級(jí)的就緒隊(duì)列，每次調(diào)度總是先調(diào)度優(yōu)先級(jí)高的隊(duì)列，僅當(dāng)該隊(duì)列空時(shí)，才調(diào)度次高優(yōu)先級(jí)隊(duì)列。 通常剛創(chuàng)建的進(jìn)程和因請(qǐng)求I/O未用完時(shí)間片的進(jìn)程排在最高優(yōu)先級(jí)隊(duì)列，在這個(gè)隊(duì)列中運(yùn)行2-3個(gè)時(shí)間片未完成的進(jìn)程排列下一個(gè)較低優(yōu)先級(jí)隊(duì)列。 不論什么時(shí)候，只要較高優(yōu)先級(jí)隊(duì)列有進(jìn)程進(jìn)入，立即轉(zhuǎn)進(jìn)程調(diào)度，及時(shí)調(diào)度較高優(yōu)先級(jí)隊(duì)列進(jìn)程。 優(yōu)點(diǎn)：能較好地滿足各類作業(yè)的用戶要求，既能使分時(shí)用戶作業(yè)得到滿意的響應(yīng)，又能使批處理用戶的作業(yè)獲得較合理的周轉(zhuǎn)時(shí)間,3.3 進(jìn)程調(diào)度,3.3 進(jìn)程調(diào)度,進(jìn)程調(diào)度的時(shí)機(jī)

21、和過(guò)程 進(jìn)程調(diào)度的時(shí)機(jī) 正在執(zhí)行的進(jìn)程運(yùn)行完畢 正在執(zhí)行的進(jìn)程調(diào)用阻塞原語(yǔ)將自己阻塞起來(lái)進(jìn)入等待狀態(tài) 在采用搶占式優(yōu)先級(jí)調(diào)度時(shí)，有優(yōu)先級(jí)高于正在運(yùn)行進(jìn)程的進(jìn)程進(jìn)入就緒隊(duì)列 在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完 CPU方式是可剝奪時(shí)，就緒隊(duì)列中的某個(gè)進(jìn)程 優(yōu)先級(jí)變得高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí),3.3 進(jìn)程調(diào)度,進(jìn)程調(diào)度的過(guò)程 進(jìn)程調(diào)度所依賴的數(shù)據(jù)結(jié)構(gòu)通常是調(diào)度隊(duì)列，由于調(diào)度的原因不同，在單處理器系統(tǒng)中設(shè)置了多種等待隊(duì)列 只有就緒隊(duì)列中的進(jìn)程能夠獲得處理器而最終運(yùn)行，其他隊(duì)列中的進(jìn)程從隊(duì)列中出來(lái)后，必須進(jìn)入就緒隊(duì)列才能分配處理器 隊(duì)列數(shù)據(jù)結(jié)構(gòu)的建立結(jié)構(gòu)與調(diào)度算法密切相關(guān) 進(jìn)程調(diào)度算法只是決定哪一個(gè)進(jìn)程將獲得處

22、理機(jī)，而將處理機(jī)分配給該進(jìn)程的具體操作是由分派程序完成的,3.3 進(jìn)程調(diào)度,void dispatcher()if (RQ=0) if (EP=0) idler(); else continue;enqueue(RQ,i);if (EP=0) go to L;j=EP;if(i.priorityj.priority), stop(j); j.status=ready; j.sdata=EPdata; enqueue(RQ,j);L:dequeue(RQ,i) i.status=executing; EP=i; else continue; ,例：,3.4 線程,線程的引入 在操作系統(tǒng)中引入進(jìn)程

23、的目的是為了使多個(gè)程序并發(fā)執(zhí)行以改善資源利用率及提高系統(tǒng)的吞吐量； 在操作系統(tǒng)中再引入線程，則是為了減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，使操作系統(tǒng)具有更好的并發(fā)性,3.4 線程,線程的定義和屬性 線程的定義 在引入線程的操作系統(tǒng)中，線程是進(jìn)程的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。線程自己基本上不擁有系統(tǒng)資源，只擁有一點(diǎn)在運(yùn)行中必不可少的資源，但它可與同屬一個(gè)進(jìn)程的其他線程共享進(jìn)程所擁有的全部資源。 一個(gè)線程可以創(chuàng)建和撤銷另一個(gè)線程；同一進(jìn)程中的多個(gè)線程之間可以并發(fā)執(zhí)行,3.4 線程,線程的屬性 線程的狀態(tài) 由于線程之間的相互制約，致使線程在運(yùn)行中也呈現(xiàn)出間斷性。相應(yīng)地，線程也同樣有就緒

24、、阻塞和執(zhí)行三種基本狀態(tài) 線程的屬性 每個(gè)線程有一個(gè)惟一的標(biāo)識(shí)符和一張線程描述表，線程描述表記錄了線程執(zhí)行的寄存器和棧等現(xiàn)場(chǎng)狀態(tài) 不同的線程可以執(zhí)行相同的程序,3.4 線程,同一進(jìn)程中的各個(gè)線程共享該進(jìn)程的內(nèi)存地址空間 線程是處理器的獨(dú)立調(diào)度單位，多個(gè)線程是可以并發(fā)執(zhí)行的 一個(gè)線程被創(chuàng)建后便開(kāi)始了它的生命周期，直至終止，線程在生命周期內(nèi)會(huì)經(jīng)歷等待狀態(tài)、就緒態(tài)和運(yùn)行態(tài)等各種狀態(tài)變化,3.4 線程,引入線程的好處 創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少（結(jié)束亦如此） 兩個(gè)線程的切換花費(fèi)時(shí)間少 由于同一進(jìn)程內(nèi)的線程共享內(nèi)存和文件，線程之間相互通信無(wú)須調(diào)用內(nèi)核，故不需要額外的通信機(jī)制，使通信更簡(jiǎn)便，信息傳送速度也快 線程能獨(dú)立