【正文】 TE BOOK Operating System 第 3 章 23 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ? 程序的并發(fā)執(zhí)行 例 1：程序 A和 B共享一個變量 N (當(dāng)前值為 n) 程序 A： ┅ N = N+1。 ┅ 在處理機上執(zhí)行關(guān)于 N的 3條指令，由于并發(fā)性，有理由假定 3個可能的執(zhí)行序列： ① N=N+1。 N=0。 N=0。(完全順序 B→A) ③ print(N)。 N=0。 NOTE BOOK Operating System 第 3 章 24 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 例 2：假定一個航班售票系統(tǒng)運行在一個多終端分時系統(tǒng)上共享主機系統(tǒng)數(shù)據(jù)（庫）資源 。 NOTE BOOK Operating System 第 3 章 25 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 var row， col : integer。 ┅ procedure booking 1： begin 2： if row = n 3： begin 4： ticket[row][col]:= 1。 6： col = col mod m + 1。 8： row= row + 1。 12： end 共享數(shù)據(jù) 1 2 3 4 ┅ m 1 2 3 4 ┅ i ┅ n 圖 航班座位示意圖 ： begin ： if row = n ： begin ： ticket[row][col]:= 1。 ┅ ： begin ： if row = n ： begin ： ticket[row][col]:= 1。 ┅ B1： B2： 1 2 3 4 5 中斷 1 2 3 4 5 當(dāng)前位置 row=3； col=4 row=3； col=4 row=3； col=4 下一步 row， col 還未被修改 ！ 造成一個座位賣給了兩位旅客 ！ 174。 NOTE BOOK Operating System 第 3 章 27 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ?程序并發(fā)執(zhí)行的條件 為保持可再現(xiàn)性，就需要考察程序并發(fā)執(zhí)行條件 。 NOTE BOOK Operating System 第 3 章 28 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ? 程序并發(fā)執(zhí)行的條件 1966年 Bernstein 提出了相鄰語句 S1， S2可以并發(fā)執(zhí)行的條件： ?語句 Si劃分兩個變量集合 R(Si)和 W(Si)；其中 ?R(Si)={a1， a2， …， am}是語句 Si在執(zhí)行期間對其進(jìn)行參考的變量； aj(j=1， … ， m)。 NOTE BOOK Operating System 第 3 章 29 2022年 4月 17日星期日 前驅(qū)圖和程序執(zhí)行 ? 程序并發(fā)執(zhí)行的條件 對于語句 S1 和 S2，討論 3 種情況： ① R(S1)∩ W(S2)={ }，即 S1讀變量不是 S2 修改的變量 ② W(S1)∩ R(S2)={ }，即 S2讀變量不是 S1 修改的變量 ③ W(S1)∩ W(S2)={ }，即雙方都不修改相同的變量 如有語句 c＝ a－ b 和 w ＝ c＋ 1，其 R()， W()分別為： R(c＝ a－ b)＝ { a， b }； W(c＝ a－ b)＝ { c } R(w＝ c＋ 1)＝ { c } ； W(w＝ c＋ 1)＝ { w } R(c＝ a－ b)∩W(w＝ c＋ 1)＝ { } R(w＝ c＋ 1)∩W(c＝ a－ b)＝ { c } 所以：兩條語句不能并發(fā)執(zhí)行 174。 NOTE BOOK Operating System 第 3 章 31 2022年 4月 17日星期日 進(jìn)程的描述 ?進(jìn)程的定義 60年代初期提出，有過許多定義（看 5個）： ?進(jìn)程是一個獨立的可以調(diào)度的活動（ ， … ） ?進(jìn)程是一抽象實體，當(dāng)它執(zhí)行某個任務(wù)時，將要分配和釋放各種資源（ ） ?行為的規(guī)則叫程序，程序在處理機上執(zhí)行時的活動稱為進(jìn)程（ ） ?進(jìn)程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位 ?在給定的活動空間和初始狀態(tài)下處理機一次執(zhí)行過程 174。進(jìn)程強調(diào)執(zhí)行過程，動態(tài)創(chuàng)建，被調(diào)度執(zhí)行后消亡 ?進(jìn)程有 并行 (單機 并發(fā) )特征，即獨立性和異步性 ?進(jìn)程是競爭計算機系統(tǒng)資源的基本單位 ?不同進(jìn)程可以對應(yīng)不同程序，也可以為同一程序（只要所對應(yīng)的數(shù)據(jù)集不同） ?作為被控制和管理的實體，除了程序本身和 所需數(shù)據(jù)集之外，應(yīng)包括 控制和管理信息 174。 NOTE BOOK Operating System 第 3 章 34 2022年 4月 17日星期日 進(jìn)程的描述 ?進(jìn)程的類型 從運行的目的，可以分成兩類： ?系統(tǒng)進(jìn)程 ——屬于操作系統(tǒng)用于完成系統(tǒng)的某些功能；其 優(yōu)先級一般高于用戶進(jìn)程 ?用戶進(jìn)程 ——外存調(diào)入內(nèi)存，完成某種應(yīng)用任務(wù) *當(dāng)然， 所謂用戶進(jìn)程并不一定是用戶所編寫的程序；編譯， IE，播放器等都 看成 是用戶進(jìn)程（不屬于 OS部分） 系統(tǒng)程序 = 系統(tǒng)進(jìn)程 ？ 174。 NOTE BOOK Operating System 第 3 章 36 2022年 4月 17日星期日 進(jìn)程控制塊 ?進(jìn)程由三部分組成 ： 進(jìn)程控制塊 PCB（ Process Control Block）， 程序段 和 數(shù)據(jù)集 ?進(jìn)程控制塊是系統(tǒng)建立和感知進(jìn)程的唯一實體，其 PCB結(jié)構(gòu)是常駐內(nèi)存的 PCB 程序 代碼 圖 進(jìn)程的組成 （ a） （ b） 程序 代碼 PCB 數(shù)據(jù)集合 174。 NOTE BOOK Operating System 第 3 章 38 2022年 4月 17日星期日 進(jìn)程控制塊 ?進(jìn)程控制塊（ PCB） 有關(guān)進(jìn)程控制塊強調(diào) 4 點： ?PCB 是系統(tǒng)感知進(jìn)程存在的唯一實體 ?通過對 PCB 的操作，進(jìn)行資源分配和調(diào)度 ?進(jìn)程結(jié)束，通過釋放 PCB 釋放所占有的資源 ?正是由于建立了 PCB，進(jìn)程才成為了資源分配、 CPU調(diào)度的單位 174。 NOTE BOOK Operating System 第 3 章 40 2022年 4月 17日星期日 進(jìn)程狀態(tài)及其轉(zhuǎn)換 ?進(jìn)程狀態(tài) 進(jìn)程可能由于等待 I/O操作、競爭資源、以及相互協(xié)作等原因產(chǎn)生了“ 走走停停 ”的動態(tài)性。 NOTE BOOK Operating System 第 3 章 41 2022年 4月 17日星期日 進(jìn)程狀態(tài)及其轉(zhuǎn)換 ?進(jìn)程狀態(tài) 增加的狀態(tài)：新建、完成 /終止 /結(jié)束狀態(tài) ?新建狀態(tài) ——剛剛定義的進(jìn)程，還未進(jìn)入就緒隊列的狀態(tài)（內(nèi)存尚待分配等）?；谀K化，或為了并發(fā)性，用戶程序可以指示創(chuàng)建多個進(jìn)程由現(xiàn)有的進(jìn)程派生操作系統(tǒng)可以創(chuàng)建一個進(jìn)程，代表用戶程序執(zhí)行一個功能（輸出進(jìn)程幫助用戶實現(xiàn)數(shù)據(jù)輸出，使用戶無需等待）操作系統(tǒng)因提供一項服務(wù)而創(chuàng)建終端用戶登陸到系統(tǒng)交互登陸通常位于磁帶，更一般地位于磁盤上的批處理作業(yè)流提供給操作系統(tǒng)。 NOTE BOOK Operating System 第 3 章 42 2022年 4月 17日星期日 ?進(jìn)程狀態(tài) 進(jìn)程狀態(tài)及其轉(zhuǎn)換 圖 進(jìn)程五狀態(tài)及轉(zhuǎn)換圖 事件發(fā)生 如 I/O完成 等待事件發(fā)生 如等待 I/O 時間片到 調(diào)度 接納 終止 就緒 運行 阻塞 新建 完成 空 → 新建： 批作業(yè) 交互登陸 系統(tǒng)服務(wù) 進(jìn)程創(chuàng)建 運行 → 完成 正常結(jié)束 硬件錯誤 非法指令 撤消子進(jìn)程 下一步 下一步下一步下一步下一步下一步下一步174。 NOTE BOOK Operating System 第 3 章 44 2022年 4月 17日星期日 ?進(jìn)程的掛起狀態(tài) 三個基本狀態(tài)提供構(gòu)造進(jìn)程活動和模型的系統(tǒng)方法 ，指導(dǎo)操作系統(tǒng)設(shè)計與實現(xiàn) ，但不充分（ 2點） ?一方面 ，處理機、內(nèi)存等系統(tǒng)硬件資源的利用率得不到充分發(fā)揮 ?另一方面 ，處在活動空間進(jìn)程可能由于某原因暫時靜止不處于活動，但也不從系統(tǒng)中徹底退出 這就導(dǎo)致三種狀態(tài)模型擴充，引入掛起狀態(tài) 進(jìn)程狀態(tài)及其轉(zhuǎn)換 174。 ? 靜止阻塞 → 活動阻塞 ；這種情況較少發(fā)生。但運行進(jìn)程執(zhí)行完，發(fā)現(xiàn)靜止阻塞隊列存在優(yōu)先級較高者時 ? 活動就緒 →靜止就緒 ；通常，操作系統(tǒng)傾向掛起阻塞態(tài)進(jìn)程。 新建 → 靜止就緒； 創(chuàng)建一個新進(jìn)程可以進(jìn)入靜止就緒隊列。這樣使以后新進(jìn)程由于主存空間不足而無法進(jìn)入，這時就使用新建 → 靜止就緒 。但如表 進(jìn)程終止事件，如果 父進(jìn)程終止，或被創(chuàng)建它的進(jìn)程終止 ，則一個進(jìn)程可以在 任何狀態(tài)下終止而進(jìn)入完成狀態(tài) 靜止就緒 → 活動就緒； 若主存中沒有就緒進(jìn)程，一般操作系統(tǒng)需要調(diào)入一個進(jìn)程。 下一步 下一步下一步下一步下一步下一步? 174。 NOTE BOOK Operating System 第 3 章 47 2022年 4月 17日星期日 進(jìn)程控制 操作系統(tǒng)控制結(jié)構(gòu) 進(jìn)程創(chuàng)建與終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 進(jìn)程間的關(guān)系 174。 NOTE BOOK Operating System 第 3 章 49 2022年 4月 17日星期日 ?控制結(jié)構(gòu) 4 種資源管理表： ?內(nèi)存表 ——跟蹤或 記錄主存和輔存以及存儲管理的所有信息 ?I/O表 ——操作系統(tǒng)利用 I/O表來管理系統(tǒng)內(nèi)的 I/O設(shè)備和通道 ?文件表 ——記錄了進(jìn)程所擁有的文件的屬性，包括文件在輔存中的位置、當(dāng)前狀態(tài)等 ?進(jìn)程表 ——維護(hù)和管理系統(tǒng)中各個進(jìn)程， 依據(jù)圖 操作系統(tǒng)控制結(jié)構(gòu) 在實際控制和管理中，這四種表是可以相互交叉引用的 174。 NOTE BOOK Operating System 第 3 章 51 2022年 4月 17日星期日 操作系統(tǒng)控制結(jié)構(gòu) ?處理機的執(zhí)行模式 ? 內(nèi)核模式 （或核心態(tài) /系統(tǒng)態(tài) /管態(tài)） ? 用戶模式 （用戶態(tài) /算態(tài) /目態(tài)） 執(zhí)行模式？為什么 ？ ——兩種考慮： ?確定控制、管理的角色 ——OS核心程序 例：中斷是系統(tǒng)的靈魂， OS當(dāng)然要掌握靈魂，在多用戶多任務(wù)系統(tǒng)中，用戶無權(quán)利用中斷！ —通過模式 ?訪問的系統(tǒng)資源、執(zhí)行的指令集有所不同 ?內(nèi)核模式可以訪問全部系統(tǒng)資源，執(zhí)行指令集中所有指令 ?用戶模式只能訪問 OS分配的私有空間、執(zhí)行非特權(quán)指令 174。 NOTE BOOK Operating System 第 3 章 53 2022年 4月 17日星期日 操作系統(tǒng)控制結(jié)構(gòu) ?操作系統(tǒng)內(nèi)核 內(nèi)核應(yīng)當(dāng)包括： ?進(jìn)程管理 ?內(nèi)存管理 ?IO管理 與硬件有關(guān)的部分一定放入內(nèi)核中，包括 3部分： ?中斷處理 ?IO驅(qū)動程序 ?進(jìn)程調(diào)度與控制用原語等 內(nèi)核 界面 用戶 接口 內(nèi)核分為： ?強內(nèi)核 ?微內(nèi)核 /弱內(nèi)核 174。 NOTE BOOK Operating System 第 3 章 55 2022年 4月 17日星期日 操作系統(tǒng)控制結(jié)構(gòu) ?操作系統(tǒng)內(nèi)核 內(nèi)核中有些功能由 原語 操作實現(xiàn) — 原子操作 所謂原子操作就是不可分割的操作，要么不做，要么全做 ；原語可分為兩類： ?一類是機器指令級的 ?另一類是功能級的 ——作為原語的程序段不允許并發(fā)執(zhí)行（禁止被中斷?。? 通常把 進(jìn)程控制用程序段做成原語 ——創(chuàng)建原語、信號量操作原語等 174。 NOTE BOOK Operating System 第 3 章 57 2022年 4月 17日星期日 進(jìn)程創(chuàng)建與終止 ?進(jìn)程創(chuàng)建 由系統(tǒng)調(diào)用，或創(chuàng)建原語創(chuàng)建進(jìn)程過程（ 4點）： ?給新進(jìn)程分配（產(chǎn)生）一個唯一進(jìn)程標(biāo)識號PID，從系統(tǒng)空閑的 PCB結(jié)構(gòu)中摘出一個 PCB