【正文】 t6 t8 P3 t9 I1 P3 輸入 處理機 打印機 t1 t2 t3 t4 t5 I2 C1 I3 C2 P1 C3 P2 由于多道程序中 IK、 CJ與 PL之間不存在前趨關(guān)系， 程序之間可以并發(fā)執(zhí)行： 并發(fā)執(zhí)行后，系統(tǒng)效率提高 并發(fā)執(zhí)行后，系統(tǒng)效率提高 程序順序執(zhí)行與并發(fā)執(zhí)行例： 程序 1 …… x ＝ 3 ； y＝ x＋ 2 ； printf（ y）； …… 程序 2 …… x ＝ 1 ； y＝ x＋ 5 ； printf（ y）； …… x =3 y=x+2 printf(y) x =1 y=x+5 printf(y) 順序執(zhí)行 t2 t1 t3 t4 t5 t6 順序執(zhí)行 結(jié)果： y = 5 y = 6 并發(fā)執(zhí)行（一） x =3 y=x+2 printf(y) x =1 y=x+5 printf(y) 并發(fā)執(zhí)行 t2 t1 t3 t4 t5 t6 結(jié)果： y = 3 y = 3 并發(fā)執(zhí)行（二） x =3 y=x+2 printf(y) y =x＋ 5 x =1 printf(y) 并發(fā)執(zhí)行 t2 t1 t3 t4 t5 t6 結(jié)果： y = ？ y = 3 可見： 程序的概念已無法描述動態(tài)執(zhí)行過程中的并發(fā)活動，解決辦法？ —— 引入進程來描述程序的一次執(zhí)行，使并發(fā)執(zhí)行的程序保持“可再現(xiàn)性”。 進程的定義： 進程是可并發(fā)執(zhí)行的程序在給定數(shù)據(jù)集合上的一次執(zhí)行過程；是系統(tǒng)進行資源分配和調(diào)度的一個獨立的基本單位和實體；是指執(zhí)行一個映象程序的總環(huán)境。 內(nèi)容：調(diào)度信息和現(xiàn)場信息 典型的進程控制塊 PCB結(jié)構(gòu) 進程標識符 進程狀態(tài) CPU現(xiàn)場（ 程序狀態(tài)字、寄存器內(nèi)容等） 資源清單 優(yōu)先級 隊列指針、家族關(guān)系 通信機制（信箱或消息隊列） 同步機制（信號量） 存儲位置 一串數(shù)值，供計算機系統(tǒng)使用 PCB的作用 PCB可唯一標識一個進程 PCB中的信息為進程的控制提供依據(jù) PCB將程序變成了進程 PCB是進程在系統(tǒng)中存在的唯一標志。（唯一的） 因等待某種事件而暫時不能執(zhí)行 進程狀態(tài)的轉(zhuǎn)換 新進程 就緒 執(zhí)行 結(jié)束 阻塞 接納 進程調(diào)度 中斷或 時間片用完 完成 I/O請求或 等待某事件 I/O完成或 事件發(fā)生 狀態(tài)轉(zhuǎn)換原因圖 狀態(tài)轉(zhuǎn)換執(zhí)行圖 新進程 就緒 執(zhí)行 結(jié)束 阻塞 進入 就緒隊列 分配 CPU使用權(quán) 強制放棄 CPU 回到就緒隊列 釋放所有 資源 進程主動放棄 CPU 進入阻塞等待隊列 進程被釋放 回到就緒隊列 進程狀態(tài)轉(zhuǎn)換歸納： 新進程 就緒狀態(tài) 事件 動作 接納 進入就緒隊列 就緒 執(zhí)行 進程調(diào)度 分配 CPU 執(zhí)行 結(jié)束 完成 釋放資源 執(zhí)行 阻塞 時間片到時 高優(yōu)先中斷 系統(tǒng)剝奪 CPU 執(zhí)行 就緒 I/O請求 等待某事件 進程放棄 CPU 進入阻塞等待隊列 阻塞 就緒 阻塞事件釋放 進程進入就緒隊列 注意： 就緒 阻塞 阻塞 執(zhí)行 執(zhí)行 就緒 ? 進程從執(zhí)行態(tài)到阻塞態(tài)是主動的 進程發(fā)現(xiàn)需要等待某一事件，主動向系統(tǒng)申請進入阻塞態(tài) ? 進程從阻塞態(tài)到就緒態(tài)是被動的 當系統(tǒng)（或其它進程）發(fā)現(xiàn)阻塞進程阻塞的條件已釋放，向系統(tǒng)申請將該阻塞進程置為就緒態(tài) 進程的控制 ? 進程的控制 —— 控制進程在其生命周期的各種活動及狀態(tài)轉(zhuǎn)換。 原語：用以完成特定功能的不可分割的一段程序，原語的執(zhí)行過程是不可中斷的。為各個進程分配處理機 使每個進程都能合理的使用處理機，得到及時的響應 處于就緒隊列的進程 進程調(diào)度的任務(wù)是控制協(xié)調(diào)進程對 CPU的競爭，即按一定的調(diào)度算法從就緒隊列中選中一個進程，把 CPU的使用權(quán)交給被選中的進程。 高優(yōu)先權(quán) 短進程 二、進程調(diào)度的方式 三、進程調(diào)度的功能 記錄系統(tǒng)中所有 進程的執(zhí)行情況 1 確定分配 處理機的原則 2 處理機的 分配與回收 3 記錄系統(tǒng)中各進程的執(zhí)行情況和環(huán)境狀態(tài)，以便在處理機空閑的時候選擇合適的進程執(zhí)行。 在執(zhí)行（撤銷）進程時裝入（釋放） PCB信息。 算法簡單，易于實現(xiàn) 對長進程有利 短進程服務(wù)質(zhì)量差 （ 2）短進程優(yōu)先（ SCBF）算法 按照就緒進程對系統(tǒng)服務(wù)時間的需求確定優(yōu)先權(quán)，服務(wù)時間需求短 的 進程優(yōu)先被調(diào)度。 tn 為實際值 為控制值， 0≤ ≤1，常取 調(diào)度算法評價指標 周轉(zhuǎn)時間（ TT） 進程第一次進入就緒隊列到進程運行結(jié)束的時間間隔 TT ＝ 等待時間 (WT) ＋ 服務(wù)時間 (ST) 平均周轉(zhuǎn)時間（ ATT） 系統(tǒng)各進程周轉(zhuǎn)時間的平均值 ATT ＝ ΣTT / N 帶權(quán)周轉(zhuǎn)時間（ QTT） 進程周轉(zhuǎn)時間與系統(tǒng)服務(wù)時間的比值 QTT = TT / 服務(wù)時間 平均帶權(quán)周轉(zhuǎn)時間（ AQTT） 例 A B C WT 10 10 30 ST 2 100 10 TT 12 110 40 ATT 54 QTT 6 4 AQTT AQTT = Σ QTT / N 例： A請求系統(tǒng)服務(wù)時間 5s， B請求系統(tǒng)服務(wù)時間為 100s， 設(shè)第 0到第 5秒前， CPU運行 C進程。 問：分別計算 FCFS算法下和 SCBF算法下， A和 B的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間和系統(tǒng)平均周轉(zhuǎn)時間？ B A FCFS算法－－先來先服務(wù) ? A：周轉(zhuǎn)時間為 3+100+5＝ 108s 帶權(quán)周轉(zhuǎn)時間為 108/5 ＝ ? B：周轉(zhuǎn)時間為 4+100＝ 104s 帶權(quán)周轉(zhuǎn)時間為 104/100 ＝ ? 平均帶權(quán)周轉(zhuǎn)時間為 ( +)247。 2 ＝ 先調(diào)度 B 后調(diào)度 A 先調(diào)度 A 后調(diào)度 B （ 3）等時間片輪轉(zhuǎn)（ ERR）算法