【正文】 的同步 一般來說， 信號(hào)量初值為 0， 兩個(gè)進(jìn)程之間的同步模型如下： 進(jìn)程 P1 進(jìn)程 P2 L1： P(S) L2： V(S) 第三章 進(jìn)程管理 例 1 用信號(hào)量實(shí)現(xiàn)司機(jī)和售票員的同步 。 生產(chǎn)者 — 消費(fèi)者進(jìn)程描述如下： 第三章 進(jìn)程管理 第三章 進(jìn)程管理 生產(chǎn)者和消費(fèi)者可按如下方式并發(fā)執(zhí)行： begin B: array［ 0 cobegin process producer i(i=1, 2, ……, m) begin L1: produce a product。 P(S)。 用一個(gè)變量 rc表示當(dāng)前正在讀的讀者個(gè)數(shù) ， 當(dāng)進(jìn)程可以去讀或讀結(jié)束后都要改變 rc的值 ， 因此 rc又成為若干讀進(jìn)程的共享變量 ， 它們必須互斥地修改 rc。 if rc=1 then P(S)。 coend。 cobegin process Reader i(i=1, 2, …, n) begin P(S)。 V(S) end。 信箱頭是信箱的描述部分；信箱體由若干格子組成 ， 其中每一格子可存放一個(gè)信件 。 接收原語的執(zhí)行過程是：根據(jù) receive原語中的第一個(gè)參數(shù)信箱名 ， 找到相應(yīng)的信箱 ， 若信箱中有信件 ， 則取出一封信放入按第二個(gè)參數(shù)給出的地址中 。 (3) 逐次請(qǐng)求 。 假定 m=4, n=4, i=2， 當(dāng)每個(gè)進(jìn)程首先輪流要求 1 單位 ， 那么第一次請(qǐng)求就把存儲(chǔ)器分配完了 ， 而第二次請(qǐng)求時(shí) ， 各進(jìn)程都進(jìn)入阻塞狀態(tài) ， 結(jié)果這四個(gè)進(jìn)程誰也不能向前推進(jìn) ， 而形成死鎖 (圖 (a)) 。 第三章 進(jìn)程管理 圖 信息傳送引起的死鎖 P1S2P3S1P2S3第三章 進(jìn)程管理 設(shè)進(jìn)程 P1 產(chǎn)生信息 S1， 而要求從 P3 接收信息 S3；進(jìn)程P2 產(chǎn)生信息 S2， 而要求從 P1 接收信息 S1。 P3: 請(qǐng)求 S2, 釋放 S3。 P(Si+1 )。 process P5 begin L5: thinking。 putdown r 1。 (4) 檢測(cè)和解除。 假設(shè)系統(tǒng)有四類資源：磁帶驅(qū)動(dòng)器 、 繪圖儀 、 打印機(jī)和卡片穿孔機(jī) 。我們把進(jìn)程 Pi在單個(gè)操作下，系統(tǒng)由 S狀態(tài)可能過渡到的狀態(tài)的集合表示為 Pi(S)。 * i 第三章 進(jìn)程管理 (5) 如果在狀態(tài) S有一個(gè)死鎖進(jìn)程 ， 則 S稱為死鎖狀態(tài) 。 第三章 進(jìn)程管理 (2) 凡是屬于 E中的一個(gè)邊 e∈ E， 都連接 π中的一個(gè)結(jié)點(diǎn)和 ρ中的一個(gè)結(jié)點(diǎn) 。 此時(shí)可能出現(xiàn)兩種結(jié)局：一是剩下若干進(jìn)程 ， 它們?nèi)蕴幱谧枞麪顟B(tài)；二是系統(tǒng)中的全部進(jìn)程都運(yùn)行到了終點(diǎn) 。 于是 ， 某進(jìn)程所占有的資源的釋放過程又可喚醒某些以前處于阻塞狀態(tài)的進(jìn)程 ，從而使被喚醒的進(jìn)程又可得到它所需要的全部資源 。 在圖 中 ， ρ={R1, R2}, π={A, B}, N={R1, R2}∪ {A, B}。 例如圖 中 P2在狀態(tài) U是死鎖的 ， 因?yàn)?P2 無論在狀態(tài)U還是在狀態(tài) V都是阻塞的 。 第三章 進(jìn)程管理 圖 SUTV22 21111第三章 進(jìn)程管理 (2) 系統(tǒng)由一種狀態(tài) S演變?yōu)榱硪环N狀態(tài) T， 是由于某個(gè)進(jìn)程 Pi對(duì)資源實(shí)施了請(qǐng)求 、 獲得或釋放的單個(gè)操作的結(jié)果 。 這一要求如下表所示 ，并假定只有當(dāng)滿足了最大需求量后才能釋放所占用的全部資源 。 (2) 預(yù)防策略。 eating。 V(S i+1 )。 P(Si)。 第三章 進(jìn)程管理 P1: 請(qǐng)求 S3, 釋放 S1。 另一類資源是消耗性資源 ， 也叫做臨時(shí)性資源 ， 記以 CR， 這類資源由一進(jìn)程產(chǎn)生而被另一進(jìn)程消耗掉 ， 只能使用短暫的時(shí)間 。 P1 P2 P3 P4RP1 P2 P3R( a )( b )圖 存儲(chǔ)器共享的死鎖 第三章 進(jìn)程管理 假定系統(tǒng)中有 m個(gè)單位的存儲(chǔ)器 ， 它為 n個(gè)進(jìn)程所共享 。 end 第三章 進(jìn)程管理 死 鎖 死鎖的起因和產(chǎn)生死鎖的必要條件 圖 兩個(gè)進(jìn)程死鎖的典型例子 進(jìn)程 P1要求資源 A進(jìn)程 P2要求資源 B要求資源 A（阻塞）AB要求資源 B（阻塞）第三章 進(jìn)程管理 圖 進(jìn)程 A、 B對(duì)資源的請(qǐng)求和釋放 請(qǐng)求打印機(jī)請(qǐng)求讀卡機(jī)釋放打印機(jī)釋放讀卡機(jī)請(qǐng)求讀卡機(jī)請(qǐng)求打印機(jī)釋放打卡機(jī)釋放讀卡機(jī)Br1Br4Br2Br3Ar1Ar4Ar2Ar3進(jìn)程A進(jìn)程B打印機(jī)讀卡機(jī)第三章 進(jìn)程管理 R1R2A B圖 進(jìn)程死鎖的環(huán)路表示 第三章 進(jìn)程管理 2. 產(chǎn)生死鎖的必要條件 (1) 互斥控制 。 同樣 ， 調(diào)用 receive原語時(shí) ， 也要給出參數(shù)：信箱名和信件取出后的存放地址 。 此外在 PCB 消息隊(duì)列隊(duì)首指針： mq 消息隊(duì)列互斥信號(hào)量： mutex 消息隊(duì)列資源信號(hào)量： Sn 第三章 進(jìn)程管理 圖 消息緩沖通訊 進(jìn)程 A發(fā)送區(qū)s e n d ( B , a )進(jìn)程 B接收區(qū)mqm u t e xsms e n d e r : As i z e : 5T e x t ： H e l l on e x t : 0第一消息緩沖區(qū)P C B （ B ）as e n d e r : As i z e : 5t e x t : H e l l or e c e i v e ( b )s e n d e r : As i z e : 5t e x t : H e l l o第三章 進(jìn)程管理 2. 信箱用于存放信件 ， 而信件是一進(jìn)程發(fā)送給另一進(jìn)程的消息 。 Write file F。 S∶ =1。 Write file F。 第三章 進(jìn)程管理 cobegin process Reader i(i=1, 2, …, m) begin P(Sr)。 end。 第三章 進(jìn)程管理 go to L1 end。 S n∶ =n。 為此 ， 我們利用兩個(gè)私用信號(hào)量 S1和 S2， 其初值均為 0， 信號(hào)量 S1表示緩沖區(qū)是否有卡片信息 ， 信號(hào)量 S2表示緩沖區(qū)信息是否被取走 。 coend。 設(shè)P1， P2， …， Pn表示各售票處的處理進(jìn)程 ， R1, R2, …, Rn表示各進(jìn)程執(zhí)行時(shí)所用的工作單元 。 R2∶ =count。 cobegin process p1 R1: register。 設(shè) S為兩進(jìn)程互斥的公用信號(hào)量 ， 初值賦予 1， 表明該臨界資源未被占用 。 ② 若 S0， 則調(diào)用 V(S) ③ 若 S≤0， 從等待信號(hào)量 S的阻塞隊(duì)列中喚醒頭一個(gè)進(jìn)程 ， 然后調(diào)用 V(S)的進(jìn)程繼續(xù)運(yùn)行 。 交通管理人員利用信號(hào)燈的顏色 (紅 、 綠 )實(shí)現(xiàn)交通管理 。 第三章 進(jìn)程管理 在有些系統(tǒng)中 ， 上述的加鎖 、 開鎖操作可用機(jī)器硬件指令完成 。 換句話說 ， 它們不應(yīng)相互等待而致使誰都不能進(jìn)入 。 其中， R1 和 R2 是處理機(jī)的兩個(gè)通用寄存器。 第三章 進(jìn)程管理 圖 司機(jī)和售票員的同步 正常行車開 車到站停車售票開車門關(guān)車門司機(jī) 售票員第三章 進(jìn)程管理 又如 ， 有用戶作業(yè)程序 ， Z=func 1(x)*func 2(y) 其中 func 1(x)， func 2(y)均是一個(gè)復(fù)雜函數(shù) ， 為了加快本題的計(jì)算速度 ， 可用兩個(gè)進(jìn)程 P P2 各計(jì)算一個(gè)函數(shù) 。 (2) 描述處理機(jī)狀態(tài)的一組寄存器內(nèi)容 。 第三章 進(jìn)程管理 WindowsNT中的進(jìn)程和線程 1. Windows NT (1) 一個(gè)可執(zhí)行的程序 ， 它定義了初始代碼和數(shù)據(jù) 。 在具有多線程機(jī)制的操作系統(tǒng)中 ， 處理機(jī)調(diào)度的基本單位不是進(jìn)程而是線程 。 在一個(gè)多道程序并發(fā)執(zhí)行的系統(tǒng)中 ， 一個(gè)作業(yè)就是獨(dú)立于其它作業(yè)的工作單位 。 在這種方式中 ， 每一輪開始時(shí) ， 系統(tǒng)便根據(jù)就緒隊(duì)列中已有的進(jìn)程數(shù) ， 計(jì)算一次 q值 ， 然后進(jìn)行輪轉(zhuǎn) 。 這對(duì)于短作業(yè) ，對(duì)于 I/O操作多的作業(yè)都很不利 。 進(jìn)程調(diào)度算法基本分為兩大類： 優(yōu)先數(shù)法和時(shí)間片輪轉(zhuǎn)法， 第三章 進(jìn)程管理 4. 進(jìn)程隊(duì)列的組織 P C B P C B P C B P C B P C B P C B P C B( a )運(yùn)行隊(duì)列 P C B0就緒隊(duì)列P C B P C B P C B0阻塞隊(duì)列 1P C B P C B P C B0阻塞隊(duì)列 2P C B P C B0( b )圖 3.8 PCB的組織方式 第三章 進(jìn)程管理 常用的進(jìn)程調(diào)度算法 1. 靜態(tài)優(yōu)先級(jí)法 (1) 按進(jìn)程類型確定。 (5) 分配給該進(jìn)程運(yùn)行的時(shí)間片已用完。 (2) 確定調(diào)度算法 ， 決定把處理機(jī)分配給哪個(gè)進(jìn)程和分配多長(zhǎng)時(shí)間 。 他把操作系統(tǒng)中指揮各個(gè)進(jìn)程的工作比作一個(gè)交通警察 ， 而把各個(gè)進(jìn)程比作車輛 。 因此 ， 撤消原語應(yīng)采用第二種方式 。 第三章 進(jìn)程管理 (3) 阻塞原語和喚醒原語 。若狀態(tài)為 “ 運(yùn)行 ” ，則中斷處理機(jī)，把 CPU狀態(tài)保存在 PCB中，停止運(yùn)行該進(jìn)程；若狀態(tài)為活躍阻塞，則改為靜止阻塞； 若狀態(tài)為活躍就緒，則改為靜止就緒；若狀態(tài)為運(yùn)行，則從活躍就緒隊(duì)列中按某種算法選一進(jìn)程投入運(yùn)行。 第三章 進(jìn)程管理 創(chuàng)建原語的功能是用來創(chuàng)建子進(jìn)程 。 第三章 進(jìn)程管理 2. 操作系統(tǒng)的內(nèi)核是操作系統(tǒng)中最接近裸機(jī)的部分 。 (5) 進(jìn)程現(xiàn)場(chǎng)保護(hù)區(qū)。 (5) 一個(gè)進(jìn)程是由偽處理機(jī)執(zhí)行的一個(gè)程序 ()。 第三章 進(jìn)程管理 假設(shè)在開始某個(gè)循環(huán)之前 ， count的值為 n， 則在完成一個(gè)循環(huán)后 ， 對(duì)上述三個(gè)執(zhí)行序列打印機(jī)打印的 count值和執(zhí)行后的 count值如下表所示： 執(zhí)行序列 (1) (2) (3) 打印的值 n+1 n n 執(zhí)行后的值 0 1 0 第三章 進(jìn)程管理 2. 程序和機(jī)器執(zhí)行程序的活動(dòng)是兩個(gè)概念 。 (1) count∶ =count+1。報(bào)告者定時(shí)地將觀察者的計(jì)數(shù)值打印出來 ， 然后將計(jì)數(shù)器重新清 “ 0”。 所謂資源共享是指系統(tǒng)中的硬件資源和軟件資源不再為單個(gè)用戶程序所獨(dú)占 ， 而由幾道用戶程序共同使用 。 第三章 進(jìn)程管理 程序的并發(fā)執(zhí)行和資源共享 1. 程序的并發(fā)執(zhí)行 圖 程序段并發(fā)執(zhí)行的有向圖 I1I2I3I4C1C2C3C4P1P2P3P4