【文章內(nèi)容簡(jiǎn)介】 再使用，這種現(xiàn)象稱為進(jìn)程的互斥。也就是說(shuō)，不允許兩個(gè)以上的共享同一臨界資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。 第 2 章 進(jìn) 程 管 理 進(jìn)程互斥執(zhí)行應(yīng)遵循一定的原則 (P8889)： (1) 空閑讓進(jìn) (2) 忙則等待 (3) 有限等待 (4) 讓權(quán)等待 第 2 章 進(jìn) 程 管 理 整型信號(hào)量和簡(jiǎn)單的 P、 V操作 整型信號(hào)量是一個(gè)與資源的物理實(shí)體個(gè)數(shù)有關(guān)的整型變量，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作 (Atomic Operation) ： wait(S)和 signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直被分別稱為 P、 V操作。 wait和 signal操作可分別描述為： wait(S): while S≤0 do noop S∶ =S1。消耗一個(gè)資源 signal(S): S∶ =S+1。釋放一個(gè)資源 第 2 章 進(jìn) 程 管 理 用整型信號(hào)量和簡(jiǎn)單的 P、 V操作實(shí)現(xiàn)進(jìn)程互斥： Pa： Pb： wait(s) wait(s) S1 S2 signal(s) signal(s) …… …… S1 、 S2分別是進(jìn)程 Pa、 Pb中的臨界區(qū)。 第 2 章 進(jìn) 程 管 理 4. 記錄型信號(hào)量和對(duì)應(yīng)的 P、 V操作 在整型信號(hào)量機(jī)制中的 wait操作 ， 只要是信號(hào)量 S≤0， 就會(huì)不斷地測(cè)試 。 因此 ， 該機(jī)制并未遵循 “ 讓權(quán)等待 ” 的準(zhǔn)則 ， 而是使進(jìn)程處于 “ 忙等 ” 的狀態(tài) 。 記錄型信號(hào)量機(jī)制 ， 則是一種不存在 “ 忙等 ” 現(xiàn)象的進(jìn)程同步機(jī)制 。 但在采取了 “ 讓權(quán)等待 ” 的策略后 ，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一臨界資源的情況 ， 需要組織等待隊(duì)列 。 第 2 章 進(jìn) 程 管 理 于是引進(jìn)記錄型信號(hào)量 ，描述為： type semaphore=record value:integer。 L:list of process。 end 第 2 章 進(jìn) 程 管 理 整型分量： 是一個(gè)與資源的物理實(shí)體個(gè)數(shù)有關(guān)的整型變量，當(dāng)其值 0時(shí)，代表供并發(fā)進(jìn)程使用的某種資源的數(shù)量；當(dāng)其值 ≤ 0時(shí)，其絕對(duì)值代表目前等待該類(lèi)資源的阻塞隊(duì)列的長(zhǎng)度。 指針型分量： 指向該類(lèi)資源阻塞隊(duì)列的頭結(jié)點(diǎn)。 第 2 章 進(jìn) 程 管 理 當(dāng)信號(hào)量是記錄型數(shù)據(jù)時(shí)， P、 V操作被描述為： procedure wait(S) var S: semaphore。 begin ∶ =。 if ＜ 0 then block()；阻塞 end procedure signal(S) var S: semaphore。 begin ∶ =+1。 if ≤0 then wakeup()； 喚醒 end 第 2 章 進(jìn) 程 管 理 AND型信號(hào)量和對(duì)應(yīng)的 P、 V操作 多個(gè)進(jìn)程共享多個(gè)資源時(shí)用記錄型信號(hào)量和P、 V操作實(shí)現(xiàn)進(jìn)程的互斥，會(huì)出現(xiàn) 死鎖問(wèn)題 。 于是引進(jìn) AND型信號(hào)量，和與其對(duì)應(yīng)的 P、 V操作。 第 2 章 進(jìn) 程 管 理 AND機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源 ， 一次性全部地分配給進(jìn)程 ， 待進(jìn)程使用完后再一起釋放 。只要尚有一個(gè)資源未能分配給進(jìn)程 ， 其它所有可能為之分配的資源 ， 也不分配給他 。 亦即 ， 對(duì)若干個(gè)臨界資源的分配 ， 采取原子操作方式：要么全部分配到進(jìn)程 ， 要么一個(gè)也不分配 。 由死鎖理論可知 ， 這樣就可避免上述死鎖情況的發(fā)生 。 第 2 章 進(jìn) 程 管 理 對(duì)應(yīng)的 P、 V操作定義如下： Swait(S1, S2, …, Sn) if S1≥1 and … and Sn≥1 then for i∶ =1 to n do Si∶ =Si1。 endfor else place the process in the waiting queue associated with the first Si found with Si＜ 1, and set the program count of this process to the beginning of Swait operation endif 第 2 章 進(jìn) 程 管 理 Ssignal(S1, S2, …, Sn) for i∶ =1 to n do Si=Si+1。 Remove all the process waiting in the queue associated with Si into the ready queue. endfor。 第 2 章 進(jìn) 程 管 理 信號(hào)量集和對(duì)應(yīng)的 P、 V操作 信號(hào)量集機(jī)制的基本思想是：一次分配 若干類(lèi) 資源；每類(lèi)資源一次 分配一批 (而不是一個(gè) )；當(dāng)某類(lèi)資源的空閑數(shù)量少于 下限 時(shí)，不分配該類(lèi)資源。 第 2 章 進(jìn) 程 管 理 信號(hào)量集下的 P、 V操作： Swait(S1, t1, d1, …, Sn, tn, dn) 。t下限、 d一次分配的數(shù)量 if Si≥t1 and … and Sn≥tn then for i∶ =1 to n do Si∶ =Sidi。 endfor else Place the executing process in the waiting queue of the first Si with Si＜ ti and set its program counter to the beginning of the Swait Operation. endif 第 2 章 進(jìn) 程 管 理 signal(S1, d1, …, Sn, dn) for i∶ =1 to n do Si∶ =Si+di。 Remove all the process waiting in the queue associated with Si into the ready queue endfor。 第 2 章 進(jìn) 程 管 理 用不同類(lèi)型的信號(hào)量和其對(duì)應(yīng)的 P、 V操作實(shí)現(xiàn)進(jìn)程的互斥，形式是完全一樣，只是 P、V操作的意義不同。 Pa： Pb： wait(s) wait(s) S1 S2 signal(s) signal(s) …… …… S1 、 S2分別是進(jìn)程 Pa、 Pb中的訪問(wèn)資源 S的臨界區(qū)。 第 2 章 進(jìn) 程 管 理 三、進(jìn)程的同步 引例： A進(jìn)程向緩沖區(qū) buf中放數(shù)據(jù)、 B進(jìn)程從 buf中取數(shù)據(jù)打印。 A進(jìn)程： do while buf ≠ 空 { }。 計(jì)算，得到一個(gè)結(jié)果； buf? 一個(gè)結(jié)果； …… 第 2 章 進(jìn) 程 管 理 B進(jìn)程： do while buf = 空 { }。 取出 buf中的數(shù)據(jù)，打??； 清空 buf； …… 進(jìn)程 A和進(jìn)程 B是兩個(gè)并發(fā)執(zhí)行的、相互合作的進(jìn)程。 第 2 章 進(jìn) 程 管 理 進(jìn)程同步 如果引例中的進(jìn)程 A、 B并發(fā)執(zhí)行時(shí)不進(jìn)行任何控制，會(huì)造成 CPU資源的極大浪費(fèi)。 進(jìn)程同步：異步環(huán)境下的一組并發(fā)進(jìn)程，由于需要互發(fā)消息，相互合作，相互等待，從而相互制約彼此的執(zhí)行速度，要以一定的速度向前推進(jìn)。 第 2 章 進(jìn) 程 管 理 用信號(hào)量和 P、 V操作來(lái)實(shí)現(xiàn)進(jìn)程同步 用前面介紹過(guò)的信號(hào)量和 P、 V操作也可以實(shí)現(xiàn)進(jìn)程的同步控制。 對(duì)于引例，我們引入兩個(gè)信號(hào)量 s1和 s2。s1=1，表示緩沖區(qū)為空，可以放數(shù)據(jù)，s1=0，表示緩沖區(qū)里放滿了數(shù)據(jù)； s2=1，表示緩沖區(qū)內(nèi)有數(shù)據(jù)供打印， s2=0，表示緩沖區(qū)里沒(méi)有數(shù)據(jù)供打印。 第 2 章 進(jìn) 程 管 理 進(jìn)程同步的實(shí)現(xiàn) Pa： Pb： 計(jì)算； wait(s2) wait(s1) 從緩沖區(qū)取數(shù)據(jù)； 向緩沖區(qū)中放數(shù)據(jù)； signal(s1) signal(s2) 打印數(shù)據(jù)； 第 2 章 進(jìn) 程 管 理 在這里，我們可以將 P操作看成消耗一個(gè)資源，將 V操作看成生產(chǎn)一個(gè)資源；進(jìn)程 Pa看作信號(hào) s1的消耗者，信號(hào) s2的產(chǎn)生者。反之，將進(jìn)程 Pa看作信號(hào) s1的消耗者，信號(hào) s2的產(chǎn)生者。產(chǎn)生者和消耗者并發(fā)執(zhí)行，通過(guò)信號(hào)量交換信息，可以合作完成任務(wù)。 第 2 章 進(jìn) 程 管 理 四、 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系 圖 210 前趨圖舉例 S4S5S3S1S6S2第 2 章 進(jìn) 程 管 理 Var a,b,c,d,e,f,g。 semaphore∶ =0,0,0,0,0,0,0。 begin parbegin begin S1。 signal(a)。 signal(b)。 end。 begin wait(a)。 S2。 signal(c)。 signal(d)。 end。 begin wait(b)。 S3。 signal(e)。 end。 begin wait(c)。 S4。 signal(f)。 end。 begin wait(d)。 S5。 signal(g)。 end。 begin wait(e)。 wait(f)。 wait(g)。 S6。 end。 parend end 第 2 章 進(jìn) 程 管 理 私有信號(hào)量和共有信號(hào)量 在實(shí)現(xiàn)進(jìn)程 互斥 時(shí)使用的信號(hào)量，標(biāo)志著對(duì)并發(fā)執(zhí)行的一組進(jìn)程使用臨界資源的制約，這樣的信號(hào)量稱為 公有 信號(hào)量； 在實(shí)現(xiàn)進(jìn)程 同步 時(shí)使用的信號(hào)量，使得生產(chǎn)進(jìn)程和消耗進(jìn)程之間能交換信息，不影響并發(fā)執(zhí)行的其他進(jìn)程。這樣的信號(hào)量稱為 私有 信號(hào)量。 第 2 章 進(jìn) 程 管 理 第 四 節(jié) 經(jīng)典 的進(jìn)程同步問(wèn)題 第 2 章 進(jìn) 程 管 理 一、生產(chǎn)者 消費(fèi)者問(wèn)題 問(wèn)題的描述：在計(jì)算機(jī)系統(tǒng)中每個(gè)進(jìn)程都在申請(qǐng)使用、釋放各種不同類(lèi)型的資源。我們把 申請(qǐng)使用 某類(lèi)資源的進(jìn)程，稱為這類(lèi)資源的 消費(fèi)者 ，把產(chǎn)生或釋放 某類(lèi)資源的進(jìn)程，稱為這類(lèi)資源的 生產(chǎn)者 。例如，在輸入時(shí)，輸入進(jìn)程是數(shù)據(jù)的生產(chǎn)者，計(jì)算進(jìn)程是數(shù)據(jù)的消費(fèi)者；而在輸出時(shí)，則計(jì)算進(jìn)程是數(shù)據(jù)的生產(chǎn)者，而打印進(jìn)程是數(shù)據(jù)的消費(fèi)者。 (對(duì)于硬件資源和數(shù)據(jù)資源，意義略有不同。 )該問(wèn)題有很大的代表性及實(shí)用價(jià)值。 第 2 章 進(jìn) 程 管 理 解決生產(chǎn)者 —消費(fèi)者問(wèn)題的方法 例如，有一個(gè)大小為 n的公共緩沖區(qū)，生產(chǎn)者進(jìn)程向其中存入數(shù)據(jù)，消費(fèi)者進(jìn)程從其中取數(shù)據(jù)去打印。 同步的問(wèn)題描述為 ： (1) 消費(fèi)者要取數(shù)據(jù)，緩沖區(qū)