【正文】 produce an item in nextp。 in ?? (in+1) mod n。 end (nextp)。 nextc??buffer[out]。 consume the item in nextc。 ? 生產(chǎn) /消費(fèi)指針 in, out: integer ?? 0, 0。 buffer: array [0..n1] of item。 buffer[in] ?? nextp。 END。 out ?? (out+1) mod n。 BEGIN in ?? out ?? count ?? 0。 if then ()。 BEGIN if count=0 then ()。 count ?? count + 1。 PROCEDURE entry put(nextp: item)。 ? 條件變量設(shè)計(jì) ? notfull/notempty ? 針對(duì)每個(gè)條件變量 ? 設(shè)置進(jìn)程等待隊(duì)列 ? 設(shè)置同步操作原語(yǔ) wait與 signal 137 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 消費(fèi)者管程設(shè)計(jì) (待續(xù) ) TYPE producerconsumer = monitor。 end (nextc)。 signal(mutex)。 begin repeat wait(full)。 signal(full)。 wait(mutex)。 共享變量說(shuō)明 PROCEDURE entry P1（形參表）； 過(guò)程局部變量說(shuō)明 BEGIN 語(yǔ)句序列 END。 ?? 。 remove(, Bufferj)。 End。 wait()。 ?? 。 // 消息隊(duì)列互斥信號(hào)量 Semphore。 // 消息正文 Next。 end Receive(producer, nextc)。 signal(mutex)。 begin repeat wait(full)。 signal(full)。 wait(mutex)。 109 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 《 操作系統(tǒng)實(shí)踐 》 實(shí)驗(yàn) 3 ? 利 用 Windows下的 VC++或者 Linux下的 C或 C++編程模擬解決各種進(jìn)程同步問題： I. 生產(chǎn)者 消費(fèi)者問題；讀者優(yōu)先的讀者 寫者問題；寫者優(yōu)先的讀者 寫者問題；讀者數(shù)限定的讀者 寫者問題；哲學(xué)家就餐問題 II. 撰寫實(shí)驗(yàn)報(bào)告，闡述實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)?zāi)繕?biāo)、實(shí)驗(yàn)步驟、技術(shù)難點(diǎn)及解決方案、關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法流程、測(cè)試方案與過(guò)程及運(yùn)行效果、結(jié)論與體會(huì)等。 Perform write operation。 …… Perform read operation。 … 。 readerm。 begin parbegin reader1。 signal(wmutex)。 signal(rmutex)。 Perform read operation。 parend end 99 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 讀者子程序設(shè)計(jì) readeri: begin repeat wait(rmutex)。 … 。 readeri 。 ? 存在多個(gè)進(jìn)程共享一個(gè)數(shù)據(jù)對(duì)象 ? 只要求讀的進(jìn)程稱為讀者進(jìn)程 ? 擁有寫或修改要求的進(jìn)程稱為寫者進(jìn)程 ? 允許多個(gè)讀者進(jìn)程同時(shí)執(zhí)行讀操作 ? 任何寫者進(jìn)程的執(zhí)行具有排它性 ? 讀者 —寫者問題常用于測(cè)試新同步原語(yǔ) 97 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 讀者 ? 寫者程序信號(hào)量及變量設(shè)計(jì) ? 寫者進(jìn)程與其它進(jìn)程的互斥執(zhí)行 ? 寫互斥信號(hào)量 wmutex，初始值為 1 ? 讀者進(jìn)程之間的并發(fā)執(zhí)行 ? 讀者進(jìn)程計(jì)數(shù)變量 readercount，表示正在執(zhí)行的讀者進(jìn)程數(shù)量，其初始值為 0 ? 讀者進(jìn)程計(jì)數(shù)變量的互斥訪問 ? readercount對(duì)于多個(gè)讀者進(jìn)程而言是臨界資源，應(yīng)為之設(shè)置讀互斥信號(hào)量 rmutex，其初始值為 1 98 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 讀者－寫者主程序設(shè)計(jì) Var readercount: integer ?? 0。 Eat。 philosophyi 。 Think。 wait(chopstick[(i+1)mod 5])。 Ssignal(mutex, empty)。 until false。 Swait(empty, mutex)。 signal(empty)。 wait(mutex)。 signal(full)。 wait(mutex)。 consumer X。 consumer1。 …。 ? 輸入指針 in ? 指示下一個(gè)可以投放數(shù)據(jù)的緩沖區(qū) ? 初始值為 0；變化方式： in ?? (in+1) mod n ? 輸出指針 out ? 指示下一個(gè)可以獲取數(shù)據(jù)的緩沖區(qū) ? 初始值為 0；變化方式： out??(out+1) mod n ? nextp/nextc暫存每次要生產(chǎn)或消費(fèi)的數(shù)據(jù) 83 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者程序信號(hào)量設(shè)計(jì) ? 循環(huán)緩沖的互斥使用 ? 互斥信號(hào)量 mutex，初始值為 1 ? 資源信號(hào)量 ? empty 表示循環(huán)緩沖中的空緩沖區(qū)的數(shù)量，其初始值為 n ? full 表示循環(huán)緩沖中的滿緩沖區(qū)的數(shù)量，其初始值為 0 84 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者－消費(fèi)者主程序設(shè)計(jì) Var buffer: array [0..n1] of item。 ? 試闡述你對(duì)整型信號(hào)量機(jī)制與記錄型信號(hào)量機(jī)制的完整理解以及 AND型信號(hào)量機(jī)制與一般信號(hào)量集機(jī)制的基本思想。 S6。 end。 end。 end。 end。 begin wait(a)。 begin parbegin begin S1。 end process2: begin repeat wait(mutex)。 process2。 wakeupAllProcesses(si)。 } } if (in) { for i:=1 to n do si :=si－ di。 else blockProcessAndResetPC(sfirstless)。 ? 基于以上兩點(diǎn)可以對(duì) AND信號(hào)量機(jī)制進(jìn)行擴(kuò)充，形成一般化的“信號(hào)量集”機(jī)制。 end ？ 65 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 一般信號(hào)量集機(jī)制的引入 ? 記錄型信號(hào)量集機(jī)制中， wait(s)和 signal(s)操作僅能對(duì)信號(hào)量施以增 1和減 1的操作，即每次只能獲得或釋放一個(gè)單位的臨界資源。 } 64 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 Ssignal(s1, s2, … , s n)操作 procedure Ssignal(s1, s2, … , s n) Var s1, s2, … , s n : semphore。 end ？ for i:=1 to n do { if (si1) { block()。 wait(Dmutex)。 if ?0 then wakeup()。 begin := 1。 ? signal(s): s:=s+1。 Pj。注意，對(duì)于過(guò)于復(fù)雜的功能或你無(wú)法解決的細(xì)節(jié)可采用指定功能的函數(shù)模塊來(lái)替代。 ? 比較程序和進(jìn)程。 S2: b:=a5。 S1 S2 S3 5 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 6 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 程序順序執(zhí)行 ? 程序執(zhí)行過(guò)程中通常存在順序執(zhí)行問題 ? 構(gòu)成程序的若干個(gè)程序段之間 ? 組成程序段的多條語(yǔ)句之間 Ii Ci Pi S1: a:=x+y。 N:=0 ? 執(zhí)行結(jié)果分析 ? 先 A: 1, 1, 0 ? 中 A: 0, 1, 0 ? 后 A: 0, 0, 1 14 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 15 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的引入 ? 并發(fā) 、 共享及多道程序環(huán)境 ? 基于程序的概念已不能完整 、 有效地描述并發(fā)程序在內(nèi)存中的運(yùn)行狀態(tài) ? 必須建立并發(fā)程序的新的描述和控制機(jī)制 ? 基于程序段 、 數(shù)據(jù)段和進(jìn)程控制塊而引入進(jìn)程的概念以對(duì)應(yīng)程序的運(yùn)行過(guò)程 ? 進(jìn)程控制塊存放了進(jìn)程標(biāo)識(shí)符 、 進(jìn)程運(yùn)行的當(dāng)前狀態(tài) 、 程序和數(shù)據(jù)的地址以及關(guān)于該程序運(yùn)行時(shí)的 CPU環(huán)境信息 16 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的定義 ? 進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程 ， 亦即進(jìn)程實(shí)體的運(yùn)行過(guò)程 ? 進(jìn)程實(shí)體由程序段 、 數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成 ? 進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位 17 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的特征 ? 與程序的區(qū)別與聯(lián)系 ? 結(jié)構(gòu)特征 ? 程序段 、 數(shù)據(jù)段及進(jìn)程控制塊 ? 動(dòng)態(tài)性 ? 生命周期及 “ 執(zhí)行 ” 本質(zhì) ? 并發(fā)性 ? 共存于內(nèi)存 、 宏觀同時(shí)運(yùn)行 ? 獨(dú)立性 ? 調(diào)度 、 資源分配 、 運(yùn)行 ? 異步性 ? 推進(jìn)相互獨(dú)立 、 速度不可預(yù)知 18 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 19 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(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ā)生超時(shí)I/O請(qǐng)求或等待某事件20 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 引入掛起狀態(tài)的可能原因 ? 終端用戶的請(qǐng)求 ? 程序運(yùn)行期間發(fā)現(xiàn)可疑問題暫停進(jìn)程 ? 父進(jìn)程的請(qǐng)求 ? 考察、修改或協(xié)調(diào)子進(jìn)程 ? 操作系統(tǒng)的需要 ? 運(yùn)行中資源使用情況的檢查和記賬 ? 負(fù)載調(diào)節(jié)的需要 ? 負(fù)荷調(diào)節(jié)和保證實(shí)時(shí)系統(tǒng)正常運(yùn)行 21 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(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ā)生超時(shí)I/O請(qǐng)求或等待某事件阻 塞 掛 起 狀 態(tài)新 狀 態(tài)接納接納激活掛起激活掛 起I/O完成或事件發(fā)生掛 起22 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程的基本概念 前趨圖 程序順序執(zhí)行及特征 程序并發(fā)執(zhí)行及特征 進(jìn)程的特征和定義 進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換圖 23 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 作業(yè)題 ? 比較程序的順序執(zhí)行和并發(fā)執(zhí)行。在此基礎(chǔ)上，給出進(jìn)程的創(chuàng)建、終止、阻塞、喚醒、掛起與激活等函數(shù)原型及函數(shù)代碼。 end 主程序描述框架 begin parbegin Pi。 s:=s1。 end 物理意義 ？ 60 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 記錄型