基于petrinet分析并發(fā)控制

1、基于petri網(wǎng)分析并發(fā)控制劉云峰,2012年7月5日1.簡(jiǎn)介petri網(wǎng)是用來(lái)分析并發(fā)行為的一種形式模型。舉例來(lái)說(shuō)，一個(gè)進(jìn)程創(chuàng)建兩個(gè)線(xiàn)程，然后等 待它們結(jié)束，如下圖：figure 1：開(kāi)始進(jìn)程t2:創(chuàng)建;t3:合并;t1和t0為各自線(xiàn)程的操作。p5為起始控制點(diǎn)，其中的黑點(diǎn)兒為token,表示擁有控制權(quán)。經(jīng)過(guò)t2以后，p5失去控制 權(quán)，p0與p3獲得控制權(quán)，如下圖。figure 2：創(chuàng)建線(xiàn)程如此運(yùn)行,最后token到達(dá)p6,進(jìn)程結(jié)束,見(jiàn)figure 3。注意p4和p2都有token時(shí)，t3 才能激活。這個(gè)圖里邊，所有的p的token都不超過(guò)1,是有界的，這代表一種介理性。figure 3：線(xiàn)程

2、合并與進(jìn)程終結(jié)值得一提的是，如果是一個(gè)進(jìn)程fork出兩個(gè)進(jìn)程，這個(gè)圖依然冇效。在設(shè)計(jì)過(guò)程中，對(duì)并行過(guò)程建立petri網(wǎng)模型，比較容易驗(yàn)證所期望的性質(zhì)。以下對(duì)兒種 同步控制方法和并行設(shè)計(jì)模式進(jìn)行分析。2.同步控制方法互斥鎖figure4：臨界資源訪問(wèn)to和t1兩個(gè)操作訪問(wèn)了臨界資源，為了保證互斥性，引入了 p5,同時(shí)又需耍保證對(duì)方進(jìn) 入,需要在t2和t3釋放tokeno這個(gè)方案可以保證p2和p4不同時(shí)包含token,或者說(shuō) to和t1隨機(jī)互斥發(fā)生。爭(zhēng)實(shí)上，這個(gè)p5就是互斥鎖的模型。在程序中，p5的出邊實(shí)現(xiàn)為to和t1 z前的加鎖操 作，p5的入邊實(shí)現(xiàn)為t2和t3 z后的解鎖操作。此時(shí)p5中tok

3、en的個(gè)數(shù)，解禪為資源量。讀寫(xiě)鎖讀寫(xiě)鎖指的是讀鎖和寫(xiě)鎖，除了讀與讀可并行以外，其它組合都只能互斥完成。這里用權(quán) 重為2的變換t4、t5表示“寫(xiě)”操作。這個(gè)模型里，所有的p有界。而且除了 p2和p4 可以同時(shí)有token,其它組合只能是p2, p4, p8, p9單獨(dú)有token0此時(shí)p5的2出邊實(shí)現(xiàn)為加寫(xiě)鎖操作，1出邊實(shí)現(xiàn)為加讀鎖操作，所有入邊都實(shí)現(xiàn)為解鎖 操作。figures：讀寫(xiě)鎖模型條件變量條件變量在petri網(wǎng)中不需要顯式地表達(dá)，因?yàn)槊總€(gè)變換都自動(dòng)判斷在p中的前提條件。單入多出的變換：發(fā)送/廣播信號(hào)，需耍下一級(jí)變換等待多入單出的變換：等待多入多出的變換：視悄況而定3.并行設(shè)計(jì)模式最簡(jiǎn)單

4、的并行行為是模塊z間沒(méi)有數(shù)據(jù)交互，基本不需要驗(yàn)證。下而講述的是有數(shù)據(jù)交互 并行行為 生產(chǎn)者消費(fèi)者這種行為中，消費(fèi)者是依賴(lài)于生產(chǎn)者的，有一種實(shí)現(xiàn)方案見(jiàn)figure 6ofigure 6：生產(chǎn)者消費(fèi)者設(shè)計(jì)1t4為生產(chǎn)過(guò)程，t2為消費(fèi)過(guò)程。兩個(gè)過(guò)程的連接關(guān)系保證了先后次序。然而這種方式p1 和p2不滿(mǎn)足有界性，比如可能有無(wú)限個(gè)token累積在p1,在現(xiàn)實(shí)中表現(xiàn)為生產(chǎn)的產(chǎn)品未 及時(shí)消費(fèi)，產(chǎn)生庫(kù)存溢出。此時(shí)要改變?cè)O(shè)計(jì)，用p2 （消費(fèi)完畢）作為生產(chǎn)的條件，可以保證p的有界性，見(jiàn)figure 7。系統(tǒng)實(shí)現(xiàn)的時(shí)候，p1和p2解釋為兩個(gè)條件變量，生產(chǎn)者等待在p2±,執(zhí)行完畢之后發(fā) 信號(hào)給p1;消費(fèi)者等待在p2上，執(zhí)行完畢z后發(fā)信號(hào)給p2。系統(tǒng)啟動(dòng)時(shí)，發(fā)送信號(hào)給 p2o值得注童的是，對(duì)于多個(gè)生產(chǎn)者-消費(fèi)者的情況，程序的結(jié)構(gòu)不發(fā)生變化，只是條件 變量的等待/喚醒條件發(fā)生變化。figure 7：生產(chǎn)者消費(fèi)者設(shè)計(jì)2流水線(xiàn)模式流水線(xiàn)是多級(jí)的生產(chǎn)者消費(fèi)者模式老板工人模式英實(shí)figure 1就是這種模式，創(chuàng)建者為老板，被創(chuàng)