【正文】 1 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 第二章 進(jìn)程管理 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程同步問題 進(jìn)程通信 管程與線程 2 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 3 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 前趨圖舉例 ? ?={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7),(P6,P7)} ? Pi?Pj ? 稱 Pi是 Pj的直接前趨， Pj是 Pi的直接后繼 P1 P2 P3 P4 P5 P6 P7 4 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 前趨圖中必須不存在循環(huán) ? 圖例中存在前趨關(guān)系 S2?S3和 S3 ?S2，顯然，這種前趨關(guān)系是無法滿足的。 S1 S2 S3 5 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 6 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序順序執(zhí)行 ? 程序執(zhí)行過程中通常存在順序執(zhí)行問題 ? 構(gòu)成程序的若干個程序段之間 ? 組成程序段的多條語句之間 Ii Ci Pi S1: a:=x+y。 S2: b:=a5。 S3: c:=b+1。 7 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序順序執(zhí)行時的特征 ? 順序性 ? 處理機(jī)的操作，嚴(yán)格按照規(guī)定順序執(zhí)行 ? 封閉性 ? 封閉環(huán)境下運(yùn)行，程序獨(dú)占全機(jī)資源 ? 只有當(dāng)前運(yùn)行程序才能改變資源狀態(tài) ? 程序執(zhí)行結(jié)果不受外界因素的影響 ? 可再現(xiàn)性 ? 只要程序執(zhí)行時的環(huán)境和初始條件相同，程序重復(fù)執(zhí)行結(jié)果相同 8 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序順序執(zhí)行時的特性，將為程序員檢測和校正程序的錯誤，帶來極大的方便 9 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 10 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序并發(fā)執(zhí)行 例 1 ? 程序段語句間并發(fā)執(zhí)行 ? S1: a:=x+2 S2: b:=y+4 ? S3: c:=a+b S4: d:=c+6 S1 S3 S4 S2 11 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序并發(fā)執(zhí)行 例 2 ? 一批程序 Ii?Ci ?Pi并發(fā)執(zhí)行 ? Ii?Ii+1 Ci?Ci+1 Pi?Pi+1 I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 12 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序并發(fā)執(zhí)行時的特征 ? 間斷性 ? “執(zhí)行 —暫停執(zhí)行 —執(zhí)行”的活動規(guī)律 ? 失去封閉性 ? 系統(tǒng)資源共享及 資源狀態(tài)改變的多樣性，致使程序運(yùn)行失去封閉性，程序運(yùn)行必然會受到其它程序的影響 ? 不可再現(xiàn)性 ? 并發(fā)執(zhí)行的程序，計算結(jié)果與其執(zhí)行速度及時間有關(guān) 13 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 程序并發(fā)執(zhí)行不可再現(xiàn)性舉例 ? 共享初值為 0的變量 N的兩程序段 A、 B ? A: N:=N+1 ? B: Print(N)。 N:=0 ? 執(zhí)行結(jié)果分析 ? 先 A: 1, 1, 0 ? 中 A: 0, 1, 0 ? 后 A: 0, 0, 1 14 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 15 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的引入 ? 并發(fā) 、 共享及多道程序環(huán)境 ? 基于程序的概念已不能完整 、 有效地描述并發(fā)程序在內(nèi)存中的運(yùn)行狀態(tài) ? 必須建立并發(fā)程序的新的描述和控制機(jī)制 ? 基于程序段 、 數(shù)據(jù)段和進(jìn)程控制塊而引入進(jìn)程的概念以對應(yīng)程序的運(yùn)行過程 ? 進(jìn)程控制塊存放了進(jìn)程標(biāo)識符 、 進(jìn)程運(yùn)行的當(dāng)前狀態(tài) 、 程序和數(shù)據(jù)的地址以及關(guān)于該程序運(yùn)行時的 CPU環(huán)境信息 16 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的定義 ? 進(jìn)程是可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運(yùn)行過程 ， 亦即進(jìn)程實(shí)體的運(yùn)行過程 ? 進(jìn)程實(shí)體由程序段 、 數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成 ? 進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位 17 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的特征 ? 與程序的區(qū)別與聯(lián)系 ? 結(jié)構(gòu)特征 ? 程序段 、 數(shù)據(jù)段及進(jìn)程控制塊 ? 動態(tài)性 ? 生命周期及 “ 執(zhí)行 ” 本質(zhì) ? 并發(fā)性 ? 共存于內(nèi)存 、 宏觀同時運(yùn)行 ? 獨(dú)立性 ? 調(diào)度 、 資源分配 、 運(yùn)行 ? 異步性 ? 推進(jìn)相互獨(dú)立 、 速度不可預(yù)知 18 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 19 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本狀態(tài)及狀態(tài)轉(zhuǎn)換 新 狀 態(tài) 就 緒 狀 態(tài) 運(yùn) 行 狀 態(tài) 終 止 狀 態(tài)阻 塞 狀 態(tài)接 納調(diào) 度結(jié) 束I/O完成或事件發(fā)生超時I/O請求或等待某事件20 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 引入掛起狀態(tài)的可能原因 ? 終端用戶的請求 ? 程序運(yùn)行期間發(fā)現(xiàn)可疑問題暫停進(jìn)程 ? 父進(jìn)程的請求 ? 考察、修改或協(xié)調(diào)子進(jìn)程 ? 操作系統(tǒng)的需要 ? 運(yùn)行中資源使用情況的檢查和記賬 ? 負(fù)載調(diào)節(jié)的需要 ? 負(fù)荷調(diào)節(jié)和保證實(shí)時系統(tǒng)正常運(yùn)行 21 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 就 緒 掛 起 狀 態(tài) 就 緒 狀 態(tài) 運(yùn) 行 狀 態(tài) 終 止 狀 態(tài)阻 塞 狀 態(tài)調(diào) 度結(jié) 束I/O完成或事件發(fā)生超時I/O請求或等待某事件阻 塞 掛 起 狀 態(tài)新 狀 態(tài)接納接納激活掛起激活掛 起I/O完成或事件發(fā)生掛 起22 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 23 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 作業(yè)題 ? 比較程序的順序執(zhí)行和并發(fā)執(zhí)行。 ? 比較程序和進(jìn)程。 ? 試對進(jìn)程的狀態(tài)及狀態(tài)轉(zhuǎn)換進(jìn)行總結(jié)，注意狀態(tài)轉(zhuǎn)換的物理含義及轉(zhuǎn)化條件。 24 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 第二章 進(jìn)程管理 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程同步問題 進(jìn)程通信 管程與線程 25 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制 進(jìn)程控制塊 進(jìn)程圖 進(jìn)程的創(chuàng)建與終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 UNIX進(jìn)程描述與控制 26 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制塊 ? 進(jìn)程實(shí)體的一部分，擁有描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息的記錄性數(shù)據(jù)結(jié)構(gòu) ? 使一個在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序，成為一個能獨(dú)立運(yùn)行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程 ? 操作系統(tǒng) 控制和管理 并發(fā)執(zhí)行進(jìn)程的依據(jù) ? 進(jìn)程存在的惟一標(biāo)志 ? 常駐內(nèi)存并存放于操作系統(tǒng)專門開辟的 PCB區(qū) ？ 27 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制塊中的信息 ? 進(jìn)程標(biāo)識符 ? 內(nèi) /外部、父 /子進(jìn)程、用戶標(biāo)識符 ? 處理器狀態(tài)信息 ? 通用、 PC、 PSW、用戶棧指針寄存器 ? 進(jìn)程調(diào)度信息 ? 進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級、事件及其它 ? 進(jìn)程控制信息 ? 程序和數(shù)據(jù)地址、進(jìn)程同步通信機(jī)制 ? 資源清單、鏈接指針 28 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制塊的組織方式 1? 鏈接方式 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 ...... 空閑隊列指針 執(zhí)行指針 就緒隊列指針 阻塞隊列指針 6 7 5 10 8 29 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制塊的組織方式 2? 索引方式 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 ...... 執(zhí)行指針 就緒表指針 阻塞表指針 就緒索引表 阻塞索引表 30 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制 進(jìn)程控制塊 進(jìn)程圖 進(jìn)程的創(chuàng)建與終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 UNIX進(jìn)程描述與控制 31 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程圖（進(jìn)程樹） ?描述進(jìn)程家族關(guān)系的有向樹 ?結(jié)點(diǎn) /有向邊 ?父 /子進(jìn)程 ?祖父進(jìn)程 /祖先 A B C D E H L M I J F G K 有什么用 ？ 32 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制 進(jìn)程控制塊 進(jìn)程圖 進(jìn)程的創(chuàng)建與終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 UNIX進(jìn)程描述與控制 33 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 引起創(chuàng)建 /終止進(jìn)程的事件 ? 用戶登錄 ? 分時系統(tǒng)中，驗(yàn)證為合法的終端用戶登錄 ? 作業(yè)調(diào)度 ? 批處理系統(tǒng)中作業(yè)調(diào)度程序調(diào)度到某作業(yè) ? 提供服務(wù) ? 運(yùn)行中的用戶程序提出某種請求 ? 應(yīng)用請求 ? 基于應(yīng)用進(jìn)程的需要由其自身創(chuàng)建新進(jìn)程 ? 正常結(jié)束 ? 批處理系統(tǒng)中 Halt，分時系統(tǒng)中 LogsOff ? 異常結(jié)束 ? 越界錯誤、保護(hù)錯 ? 特權(quán)指令錯 ? 非法指令錯 ? 運(yùn)行超時、等待超時 ? 算術(shù)運(yùn)算錯、 I/O故障 ? 外界干預(yù) ? 操作員或操作系統(tǒng)干預(yù) ? 父進(jìn)程請求 /終止 34 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程創(chuàng)建 /終止過程 Create()原語 分配標(biāo)識符，并申請空白進(jìn)程控制塊 為新進(jìn)程的程序和數(shù)據(jù)及用戶棧分配必要的內(nèi)存空間 ? 所需內(nèi)存大小問題 初始化進(jìn)程控制塊 ? 自身 /父進(jìn)程標(biāo)識符 ? 處理機(jī)狀態(tài) /調(diào)度信息 將新進(jìn)程插入到就緒進(jìn)程隊列 Terminate()原語 檢索被終止進(jìn)程 PCB，讀取進(jìn)程狀態(tài) 若其正處于執(zhí)行狀態(tài)，應(yīng)立即中止執(zhí)行并設(shè)置調(diào)度標(biāo)志為真，以指示調(diào)度新進(jìn)程 終止子孫進(jìn)程 資源歸還 移出被終止進(jìn)程 PCB，等待其它程序利用 35 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 進(jìn)程控制 進(jìn)程控制塊 進(jìn)程圖 進(jìn)程的創(chuàng)建與終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 UNIX進(jìn)程描述與控制 36 2022年 10月 23日星期日 北京交通大學(xué)計算機(jī)學(xué)院 引起進(jìn)程阻塞 /喚醒的事件 ? 請求系統(tǒng)服務(wù) ? 但不能立即滿足 ? 啟動某種操作 ? 且必須在該操作完成之后才能繼續(xù)執(zhí)行 ? 新數(shù)據(jù)尚未到達(dá) ? 相互合作進(jìn)程的一方需首先獲得另一進(jìn)程數(shù)據(jù)才能繼續(xù) ? 無新工作可做 ? 特定功能系統(tǒng)進(jìn)程當(dāng)完成任務(wù)且暫無任務(wù) ? 系統(tǒng)服務(wù)滿足