隨機(jī)性生產(chǎn)者消費(fèi)者問題并行算法及仿真應(yīng)用

魯向前 謝垂益 霍 英

1(韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 廣東 韶關(guān) 512005)2(韶關(guān)學(xué)院信息科學(xué)與工程學(xué)院 廣東 韶關(guān) 512005)3(密蘇里州立大學(xué)計(jì)算機(jī)科學(xué)系 美國(guó) 密蘇里州 斯普林菲爾德 65897)

0 引 言

社會(huì)、經(jīng)濟(jì)、交通、能源、軍事、計(jì)算機(jī)技術(shù)等領(lǐng)域廣泛存在著多主體對(duì)多個(gè)資源的隨機(jī)的和受同步互斥等規(guī)則約束的生產(chǎn)和消費(fèi)現(xiàn)象。例如城市中所有可出租的房屋或共享單車或出租車都是資源，其出租和退租是對(duì)資源的消費(fèi)和生產(chǎn)。又如城市中能提供的工作崗位是資源，而工作崗位的離職和入職分別是對(duì)資源的生產(chǎn)和消費(fèi)。再如小區(qū)周圍的公共停車位是資源，而車位的占用和空出分別是對(duì)資源的消費(fèi)和生產(chǎn)，也如醫(yī)院住院系統(tǒng)中，床位是資源，病人住院時(shí)病人是資源(床位)的消費(fèi)者，而醫(yī)生治愈病人時(shí)醫(yī)生是資源的生產(chǎn)者。伴隨資源數(shù)量、資源供需雙方數(shù)量的變化，可能會(huì)引起社會(huì)、經(jīng)濟(jì)、能源甚至軍事事件的突變。這類現(xiàn)象過程中，主體對(duì)資源的使用具有并發(fā)性、隨機(jī)性和同步互斥約束性，還具有演化性、突變性等特性，并具有復(fù)雜系統(tǒng)[1]的許多屬性。

劉曉平等[2]對(duì)復(fù)雜系統(tǒng)的各種仿真方法做了較為全面的分析，指出仿真理論、技術(shù)和方法作為一種新的認(rèn)識(shí)改造客觀世界的重要手段，應(yīng)用于復(fù)雜系統(tǒng)研究具有非常重要的意義。復(fù)雜系統(tǒng)由于其病態(tài)結(jié)構(gòu)或機(jī)理復(fù)雜，在沒有完全認(rèn)識(shí)到其內(nèi)部機(jī)理之前無(wú)法通過建立系統(tǒng)的原始量到系統(tǒng)屬性的函數(shù)關(guān)系，無(wú)法建立完全精確的模型，已有的基于解析模型的傳統(tǒng)建模方式并不能很好地刻畫復(fù)雜系統(tǒng)，傳統(tǒng)的數(shù)學(xué)方法對(duì)復(fù)雜系統(tǒng)現(xiàn)象的描述和分析能力有限[3]。因?yàn)榕抨?duì)論中關(guān)于隨機(jī)變量服從某一統(tǒng)計(jì)分布的假設(shè)在現(xiàn)實(shí)世界中不一定得到滿足等原因，因此采用排隊(duì)論等運(yùn)籌學(xué)方法來理解等待時(shí)間時(shí)空模式的涌現(xiàn)機(jī)理不太合適[4]。

從仿真應(yīng)用上來說，本文前面提出的現(xiàn)象及本文后面提出的算法可以隸屬于人工社會(huì)仿真ACP (Artificial Society，Computational Experiments Parallel Execution)范疇。人工社會(huì)仿真是研究社會(huì)科學(xué)的有效手段[5]，在當(dāng)前計(jì)算機(jī)與仿真技術(shù)條件下，ACP方法已經(jīng)成為一種研究人工社會(huì)這類復(fù)雜系統(tǒng)的重要方法[6]。邱曉剛[7]等對(duì)社會(huì)中的突發(fā)事件應(yīng)急處理的角度對(duì)ACP方法進(jìn)行了深入研究，但是，人工社會(huì)仿真擁有廣闊的應(yīng)用天地，從其他角度探索人工社會(huì)仿真及研究其社會(huì)現(xiàn)象內(nèi)在機(jī)理和重要特征對(duì)豐富人工社會(huì)仿真具有重要意義。

1 相關(guān)工作

基于Multi-Agent System(MAS)[8]的理論和技術(shù)為復(fù)雜系統(tǒng)建模與仿真實(shí)現(xiàn)提供了一個(gè)嶄新的途徑，該方法吸取了分布式人工智能和人工生命理論，適于建立非線性的復(fù)雜系統(tǒng)仿真。然而，MAS環(huán)境中眾多的Agent對(duì)象在分布環(huán)境中運(yùn)行，Agent的復(fù)雜行為需要在分布的環(huán)境中合成和復(fù)用，Agent需要不斷的協(xié)同和通信，由于分布式環(huán)境中各行為主體的異步執(zhí)行和同步需求，其同步的實(shí)現(xiàn)代價(jià)是昂貴的。雖然美國(guó)國(guó)防部提出的高層體系結(jié)構(gòu)HLA給出了較好的解決辦法，它通過聯(lián)邦及聯(lián)邦成員的管理，能夠有效地實(shí)現(xiàn)聯(lián)邦成員間的通信及同步，但是對(duì)于內(nèi)部的聯(lián)邦成員的復(fù)雜行為并未提供較多的支持[9]。由于分布式環(huán)境天然的本質(zhì)特性，其仿真系統(tǒng)的同步、開發(fā)、調(diào)試、部署、運(yùn)行并不容易。

分布式仿真環(huán)境中，為每個(gè)主體分配一個(gè)計(jì)算機(jī)節(jié)點(diǎn)是不現(xiàn)實(shí)的。因此，歸根結(jié)底，一個(gè)單一的計(jì)算機(jī)節(jié)點(diǎn)需要仿真多個(gè)主體。然而，對(duì)于單處理機(jī)計(jì)算機(jī)系統(tǒng)來說，許多主體都在單一處理機(jī)上仿真運(yùn)行明顯存在效率問題，而且它還與現(xiàn)實(shí)系統(tǒng)中的多主體并行現(xiàn)象不一致，仿真效果是值得懷疑的。多核CPU的出現(xiàn)和快速發(fā)展以及操作系統(tǒng)和編譯器對(duì)多核CPU的支持，使我們能夠在多核單一計(jì)算機(jī)環(huán)境中完成以前需要在分布式環(huán)境中才能完成的仿真，這使得系統(tǒng)開發(fā)、調(diào)試、部署等更加高效和容易，仿真的同步可靠性將會(huì)更加容易驗(yàn)證，仿真效率將會(huì)更高。

多核環(huán)境下軟件開發(fā)的核心是多線程開發(fā)[10]，多線程并發(fā)程序可以提高硬件系統(tǒng)的運(yùn)行效率[11]。然而，并發(fā)執(zhí)行的多個(gè)線程通過共享內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行通信和同步，隨著內(nèi)核數(shù)量的增多，程序?qū)蚕碣Y源訪問的沖突加劇，大量并發(fā)運(yùn)行的線程交替地修改數(shù)據(jù)，產(chǎn)生不可預(yù)期的結(jié)果，因而面臨嚴(yán)峻挑戰(zhàn)[10]。多線程并發(fā)程序往往存在同步及互斥約束關(guān)系，如果同步互斥約束關(guān)系十分復(fù)雜，則算法正確性容易出錯(cuò)，設(shè)計(jì)應(yīng)用程序時(shí)要考慮資源要求和潛在沖突，實(shí)現(xiàn)上難于掌握。

生產(chǎn)者消費(fèi)者PC(Producer-Consumer)問題是操作系統(tǒng)中關(guān)于多線程(進(jìn)程)并發(fā)程序中同步與互斥的綜合運(yùn)用的一個(gè)經(jīng)典模型。傳統(tǒng)PC模型是用于研究基于單處理機(jī)平臺(tái)下操作系統(tǒng)中的并發(fā)問題，很少考慮并行計(jì)算。在傳統(tǒng)模型中，所有生產(chǎn)者和消費(fèi)者進(jìn)程都是按FIFO(First Input First Output)且異步方式執(zhí)行，他們之間必須保持邏輯上的同步，既不允許消費(fèi)者進(jìn)程到一個(gè)空的緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品[12]。文獻(xiàn)[13]根據(jù)生產(chǎn)者、消費(fèi)者以及緩沖區(qū)的數(shù)量，把生產(chǎn)者-消費(fèi)者問題分成了8種情況進(jìn)行討論。文獻(xiàn)[14-15]提出了兩種解決方案:(1)對(duì)所有生產(chǎn)者、消費(fèi)者設(shè)置單一互斥信號(hào)量實(shí)現(xiàn)所有生產(chǎn)者和CT對(duì)隊(duì)列的互斥訪問;(2)對(duì)生產(chǎn)者線程群和消費(fèi)者線程群各設(shè)置一個(gè)互斥信號(hào)量對(duì)隊(duì)列的互斥訪問。本文把第一種模型簡(jiǎn)稱為單互斥FIFO隊(duì)列緩沖區(qū)模型SMLQB(Single Mutex Loop Queue Buffer)，把第二種模型簡(jiǎn)稱為雙互斥FIFO隊(duì)列緩沖區(qū)模型DMLQB(Double Mutexes Loop Queue Buffer)。這兩種方案在現(xiàn)有實(shí)現(xiàn)中比較具有代表性和傳統(tǒng)性，雖然他們都能夠完成PC問題的模擬求解，但在多處理機(jī)平臺(tái)下，不能充分利用多處理機(jī)的計(jì)算資源，運(yùn)行效率低下。

另外，傳統(tǒng)的PC模型的FIFO隊(duì)列模型在用于規(guī)劃良好、行為規(guī)范的現(xiàn)實(shí)情景仿真非常合適。然而，現(xiàn)實(shí)中的生產(chǎn)者與消費(fèi)者對(duì)資源的使用并非完全按照隊(duì)列機(jī)制運(yùn)轉(zhuǎn)。相反，許多情形下生產(chǎn)者和消費(fèi)者對(duì)資源使用表現(xiàn)出隨機(jī)性，因此，用傳統(tǒng)的PC模型進(jìn)行仿真時(shí)并不符合真實(shí)世界的許多隨機(jī)現(xiàn)象。本文對(duì)該模型給予了改進(jìn)，充分利用多處理機(jī)平臺(tái)的優(yōu)勢(shì)，使其能應(yīng)用于具有同步和互斥約束關(guān)系的多主體隨機(jī)資源生產(chǎn)消費(fèi)的模型仿真。它具有多個(gè)同步互斥對(duì)象、隨機(jī)緩沖區(qū)使用、高度并發(fā)的特征(為與前文提到的兩種模型區(qū)分，把改進(jìn)后的模型簡(jiǎn)稱為隨機(jī)性生產(chǎn)者消費(fèi)者問題并行RPCP)算法。最后把算法用于復(fù)雜系統(tǒng)的資源定位次數(shù)突變性仿真，從數(shù)量上獲得資源定位碰撞次數(shù)的突變臨界點(diǎn)，對(duì)現(xiàn)實(shí)系統(tǒng)的參數(shù)配置或供需突變預(yù)測(cè)具有指導(dǎo)意義。

2 RPCP算法設(shè)計(jì)

文中用到的參數(shù)或原語(yǔ)定義如表1所示。

表1 參數(shù)和原語(yǔ)定義

續(xù)表1

RPCP算法問題模型定義為：生產(chǎn)者線程集合PTs={PTk|(k=1,2,…,PN)}，消費(fèi)者線程集合CTs={CTk|(k=1,2,…,CN)}，所有線程并發(fā)執(zhí)行，緩沖區(qū)集合{Bk|(k=1,2,…,BN)}。模型要求:(1) 要盡可能地使所有PT和CT最大程度并發(fā)并且本質(zhì)上能最大程度地并行執(zhí)行，各線程的執(zhí)行順序完全由操作系統(tǒng)調(diào)度決定;(2)每個(gè)線程生產(chǎn)或消費(fèi)資源的緩沖區(qū)號(hào)是隨機(jī)的;(3)所有線程對(duì)每個(gè)緩沖區(qū)的操作必須是互斥的;(4)每個(gè)緩沖區(qū)必須在PT生產(chǎn)資源操作全部完成后才能由CT進(jìn)行消費(fèi)資源操作，是一種同步關(guān)系;(5)每個(gè)緩沖區(qū)必須在CT消費(fèi)資源操作全部完成后才能由PT進(jìn)行生產(chǎn)資源操作，也是一種同步關(guān)系。

RPCP算法的主要策略有:

(1) 把選擇緩沖區(qū)號(hào)與實(shí)際緩沖區(qū)操作分成兩階段完成，分別進(jìn)行各自的同步和互斥并發(fā)控制，減小并發(fā)粒度，提高并發(fā)度并同時(shí)提高并行度。

(2) 為了實(shí)現(xiàn)上述策略，為每一個(gè)緩沖區(qū)設(shè)置兩個(gè)狀態(tài)標(biāo)志：緩沖區(qū)滿標(biāo)志f_F和緩沖區(qū)空標(biāo)志e_F，這是實(shí)現(xiàn)細(xì)粒度RPCP算法的關(guān)鍵。

(3) 為每一個(gè)緩沖區(qū)號(hào)設(shè)置互斥對(duì)象g_m。

(4) PTs中的每一個(gè)PT互斥地選擇空緩沖區(qū)號(hào)，CTs中的每一個(gè)CT互斥地選擇滿緩沖區(qū)號(hào)。

(5) 所有已選定空緩沖區(qū)號(hào)的PT可以并發(fā)地對(duì)各自的緩沖區(qū)進(jìn)行生產(chǎn)操作，任何一個(gè)PT在完成生產(chǎn)后，都應(yīng)向CTs發(fā)出同步信號(hào)。

(6) 所有已選定滿緩沖區(qū)號(hào)的CT可以并發(fā)地對(duì)各自的緩沖區(qū)進(jìn)行消費(fèi)操作，任何一個(gè)CT在完成消費(fèi)后，都應(yīng)向PTs發(fā)出同步信號(hào)。

(7) 對(duì)某個(gè)特定的緩沖區(qū)，PT的生產(chǎn)操作和CT的消費(fèi)操作全局互斥。

PTs算法如算法1所示，CTs算法如算法2所示。

算法1生產(chǎn)者線程群函數(shù)算法

1. void Producer(){

2. While (true){

3. P(g_sE);

4. P(g_mP);

5. j=LoopSafeLocateEmptyBuffer();

6. P(g_m[j]);

7. e_F[j]=false;

8. VM(g_mP);

9. Produce(j);

10. f_F[j]=true;

11. VM(g_m[j]);

12. VS(g_sF);

13. if (p_cn++==ON) break;

14. }}

算法2消費(fèi)者線程群函數(shù)算法

1. void Consumer(){

2. While (true){

3. P(m_c_cn);

4. c_cn=Count();

5. if (c_cn>PN*ON)break;

6. VM(m_c_cn);

7. P(g_sF);

8. P(g_mC);

9. j=LoopSafeLocateFullBuffer();

10. P(g_m[j]);

11. f_F[j]=false;

12. VM(g_mC);

13. Consume(j);

14. e_F[j]=true;

15. VM(g_m[j]);

16. VS(g_sE);

17. }}

3 實(shí)驗(yàn)結(jié)果分析和討論

3.1 并發(fā)正確性驗(yàn)證

復(fù)雜同步關(guān)系的多線程程序不但設(shè)計(jì)難度大，而且也不易調(diào)試，多線程并發(fā)正確性是算法可用性的前提。多線程并發(fā)正確性包括同步正確性、互斥正確性、無(wú)死鎖正確性、無(wú)饑餓正確性、線程退出正確性及應(yīng)用邏輯正確性等。

多核處理器并行程序的確定性重放[17]是實(shí)現(xiàn)并行程序調(diào)試的有效手段，但由于多核架構(gòu)下存在共享訪存不同步問題，并行程序確定性重放的研究和實(shí)現(xiàn)依然面臨多方面的挑戰(zhàn)。文獻(xiàn)[18]使用了一種形式化的方法來描述和證明并行算法的正確性。對(duì)于少量局部范圍內(nèi)的同步對(duì)象，使用該方法進(jìn)行證明是可行的，但對(duì)于大量的復(fù)雜的并行系統(tǒng)，其證明過程本身將會(huì)變得難以描述。

對(duì)于某種特定的并發(fā)問題的調(diào)試，往往使用特殊的調(diào)試方法更為有效。學(xué)術(shù)界和工業(yè)界廣泛使用實(shí)驗(yàn)方法觀察并發(fā)系統(tǒng)的結(jié)果來驗(yàn)證算法的正確性。因此一個(gè)易于調(diào)試易于觀察并發(fā)過程和判斷同步互斥結(jié)果正確性的實(shí)驗(yàn)輸出控制方法非常重要。傳統(tǒng)上，對(duì)于多線程程序的輸出驗(yàn)證，有多種方案可供選擇，例如:(1)編寫控制臺(tái)程序進(jìn)行輸出，如文獻(xiàn)[15];(2)所有線程的輸出都顯示在同一個(gè)窗體中，如文獻(xiàn)[19-20];(3)各線程各自使用基于共享主線程窗口內(nèi)的多個(gè)子窗口進(jìn)行輸出。這些方案都有一個(gè)共同的缺點(diǎn):多個(gè)線程共用一個(gè)輸出區(qū)域或者共用一個(gè)消息循環(huán)，本質(zhì)上是“并發(fā)執(zhí)行，串行輸出”的耦合輸出方式，會(huì)影響并發(fā)性觀察和正確性判斷。

本文使用一種新的驗(yàn)證方法，把RPCP算法移植到GUI環(huán)境中，給每個(gè)PT和每個(gè)CT都創(chuàng)建自己獨(dú)立的輸出窗口，每個(gè)窗口使用獨(dú)立的窗口過程函數(shù)，并使用適當(dāng)?shù)男锌刂萍夹g(shù)和動(dòng)態(tài)交互控制技術(shù)，各自完全無(wú)耦合的顯示結(jié)果。

算法的無(wú)死鎖正確性、無(wú)饑餓正確性、線程退出正確性容易判斷。下面主要對(duì)同步正確性、互斥正確性作簡(jiǎn)要論述。PTk對(duì)應(yīng)的窗口標(biāo)記為PW={PWk|k=1,2,…,PN}，CTk對(duì)應(yīng)的窗口標(biāo)記為CW={CWk|k=1，2，…，CN}。設(shè)線程k(窗口k)在t時(shí)刻的輸出行號(hào)表示為L(zhǎng)(wk,t)，其對(duì)應(yīng)的調(diào)試輸出信息表示為元組(BL,SL)(BL表示線程正在操作的緩沖區(qū)號(hào),SL表示緩沖區(qū)的操作動(dòng)態(tài)信息)，對(duì)于任意t1>t2有L(wk,t1)> (wk,t2)。對(duì)于?(i,t)，比較L(wi,t)和L(wj,t)(j=1,2，…，PN+CN,i≠j)的元組(B1,S1)和(B2,S2)，如果有B1=B2，則存在互斥錯(cuò)誤。對(duì)于?(i,t1,t2)，比較L(wi,t1)和L(wj,t2)(j=1,2，…，CN,i≠j,t1B1，則能保證PT序?qū)T的同步正確性，把此表述稍作調(diào)整不難判斷CT對(duì)PT的同步正確性。

在驗(yàn)證過程中，在任意時(shí)刻t，用戶可以暫?；蚶^續(xù)所有線程的運(yùn)行，觀察線程并發(fā)執(zhí)行的當(dāng)前狀態(tài)。各線程窗口的輸出時(shí)序與系統(tǒng)內(nèi)部的計(jì)算過程完全精準(zhǔn)對(duì)應(yīng)，沒有任何輸出耦合，便于隨時(shí)觀察和驗(yàn)證結(jié)果的正確性。此驗(yàn)證方法十分簡(jiǎn)便，反復(fù)驗(yàn)證結(jié)果證明算法是穩(wěn)定和正確的。

3.2 隨機(jī)性分析

本算法的應(yīng)用邏輯正確性主要表現(xiàn)為隨機(jī)性是否正確。隨機(jī)性是普遍存在的現(xiàn)象，是算法應(yīng)用于復(fù)雜系統(tǒng)隨機(jī)性仿真的基石。多線程的隨機(jī)數(shù)產(chǎn)生與單線程隨機(jī)數(shù)產(chǎn)生原理上并不相同，本文使用了線程安全的隨機(jī)數(shù)產(chǎn)生方法實(shí)現(xiàn)隨機(jī)數(shù)產(chǎn)生的正確性。

首先對(duì)PT操作的緩沖區(qū)號(hào)的隨機(jī)性進(jìn)行分析。測(cè)試任務(wù)PN×CN×BN參數(shù)為24×35×18，測(cè)試10次。對(duì)每次實(shí)驗(yàn)中每個(gè)緩沖區(qū)號(hào)被PT群選中的次數(shù)進(jìn)行累加，得到統(tǒng)計(jì)數(shù)據(jù)，相應(yīng)的折線圖如圖1所示。 從統(tǒng)計(jì)結(jié)果看，各緩沖區(qū)編號(hào)被PT選中操作的次數(shù)是均衡的。

圖1 每個(gè)緩沖區(qū)號(hào)被PT群選中的總次數(shù)

再考察CT群中每個(gè)CT所消費(fèi)的緩沖區(qū)個(gè)數(shù)，仍然以10組測(cè)試數(shù)據(jù)進(jìn)行累加，統(tǒng)計(jì)出每個(gè)線程編號(hào)所消費(fèi)的緩沖區(qū)總個(gè)數(shù)，相應(yīng)的折線圖如圖2所示。從總體上來看，各CT所消費(fèi)的緩沖區(qū)個(gè)數(shù)都相對(duì)一致，說明各CT的負(fù)載是均衡的。

圖2 每個(gè)CT消費(fèi)的緩沖區(qū)個(gè)數(shù)總和

3.3 并行度分析

為了比較三種算法在執(zhí)行性能上的差異，在不同參數(shù)配置的機(jī)器上進(jìn)行不同任務(wù)參數(shù)的實(shí)驗(yàn)，每臺(tái)機(jī)器每個(gè)任務(wù)的每種算法均運(yùn)行10次，測(cè)試每次運(yùn)行的耗時(shí)，統(tǒng)計(jì)每臺(tái)機(jī)器每種算法的10次運(yùn)行耗時(shí)的平均值。為避免循環(huán)級(jí)任務(wù)并行[16]的編譯優(yōu)化而影響測(cè)試時(shí)間的準(zhǔn)確性，每次測(cè)試是獨(dú)立進(jìn)行而非在同一進(jìn)程中循環(huán)測(cè)試。

定義:加速比A1=t(SMLQB)/t(DMLQB);加速比A2= t(DMLQB)/t(RPCP)，其中t()表示算法運(yùn)行消耗時(shí)間。實(shí)驗(yàn)結(jié)果數(shù)據(jù)如表2所示，其中任務(wù)編號(hào)1～3的任務(wù)參數(shù)PN×CN×BN的值分別取24×24×24、100×24×24、24×24×5000。

表2 并行度實(shí)驗(yàn)結(jié)果

表2中理想加速比是指在不考慮CPU被操作系統(tǒng)及其他應(yīng)用程序占用而導(dǎo)致性能損耗的情形下所得到的三種算法性能對(duì)比。

從表2中的實(shí)驗(yàn)結(jié)果可以看出，實(shí)驗(yàn)結(jié)果的加速比很好地?cái)M合了理想加速比，說明RPCP算法并行執(zhí)行的線程數(shù)與CPU核數(shù)基本相同，在多處理機(jī)平臺(tái)上其并行度遠(yuǎn)高于傳統(tǒng)的算法。

4 資源定位碰撞次數(shù)的涌現(xiàn)性仿真

在RPCP算法的步驟j=LoopSafeLocate**()中，線程以線程安全的循環(huán)測(cè)試方式隨機(jī)選擇一個(gè)空/滿的緩沖區(qū)編號(hào)j，以定位符合同步和互斥條件的可用資源號(hào)。我們把線程從開始新一輪生產(chǎn)/消費(fèi)到成功定位到一個(gè)可用資源號(hào)所經(jīng)過的循環(huán)次數(shù)定義為資源定位碰撞次數(shù)lct。從仿真意義上來說，lct可以代表真實(shí)世界中如石油需求國(guó)從市場(chǎng)成功獲取石油的時(shí)間代價(jià)，也可代表如求職者從求職開始到求職成功過程中求職失敗的碰壁次數(shù)，也可對(duì)應(yīng)于出租車乘客從開始尋找出租車到成功乘坐出租車所嘗試的招租次數(shù)。從本質(zhì)上來說，lct的大小反映了主體獲取資源的代價(jià)、系統(tǒng)資源的利用率或客戶獲取資滿意度，如果資源配置過多，會(huì)造成資源的浪費(fèi)，配置過少，客戶在定位可用資源的時(shí)間花銷增多，滿意度會(huì)降低。

此處定義時(shí)間因子tf為:tf=tp/tc，tp表示生產(chǎn)者從獲取一個(gè)緩沖區(qū)號(hào)開始到成功完成一個(gè)產(chǎn)品的生產(chǎn)所耗費(fèi)的時(shí)間，tc表示消費(fèi)者從獲取了一個(gè)緩沖區(qū)號(hào)開始到成功完成一個(gè)產(chǎn)品的消費(fèi)所經(jīng)歷的時(shí)間。另外，為使研究著重于系統(tǒng)整體性能，lct是基于平均意義下的值。

顯然，lct的大小與PN、CN、BN、tf等有關(guān)。例如，在PN、CN及tf確定的情況下，BN過大，則PT的lct會(huì)很小，但CT的lct會(huì)很大，BN過小則會(huì)有相反的結(jié)果。由于系統(tǒng)具有多個(gè)主體行為并行且特殊的同步約束關(guān)系，使用概率模型無(wú)法對(duì)lct建立完全精確的模型，已有的基于傳統(tǒng)建模方式的解析模型并不能很好地刻畫復(fù)雜系統(tǒng)。因此，使用仿真的方法來捕獲與研究事物的演化規(guī)律，以達(dá)到對(duì)系統(tǒng)演化特性或其他特性的研究。圖3是在PN×CN×BN×tf參數(shù)值分別為X×64×64×1、X×32×64×1、X×64×32×1情形下PT群的lct仿真結(jié)果。圖4是在PN×CN×BN×tf參數(shù)值分別為X×64×64×0.5、X×64×64×1、X×64×64×2情形下PT群的lct仿真結(jié)果。CT群和PT群的仿真結(jié)果具有對(duì)稱性。

圖3 tf=1情形下不同任務(wù)組合的影響

圖4 X×64×64情形下不同時(shí)間因子的影響

從所有仿真結(jié)果看，lct具有明顯的突變臨界窄區(qū)間，在突變臨界窄區(qū)間左側(cè)，lct的變化非常緩慢，在突變臨界窄區(qū)間右側(cè)，lct的變化保持在一定的穩(wěn)定飽和狀態(tài)。這種臨界突變性與量變引起質(zhì)變的唯物辯證法的基本規(guī)律相一致，然而哲學(xué)上對(duì)量變引起質(zhì)變一般是進(jìn)行定性研究，即并不解決究竟要多大的量變才能引起質(zhì)變的問題。因此，我們可以在已知現(xiàn)實(shí)系統(tǒng)參數(shù)組合配置下先用RPCP算法進(jìn)行仿真實(shí)驗(yàn)，獲得突變臨界點(diǎn)，然后對(duì)現(xiàn)實(shí)系統(tǒng)的生產(chǎn)者群體、消費(fèi)者群體或資源數(shù)量等參數(shù)進(jìn)行控制，使lct保持在較低水平，從而提高資源利用率并能保持較高的客戶滿意度。因此從數(shù)量上捕獲到的仿真突變臨界點(diǎn)對(duì)于現(xiàn)實(shí)系統(tǒng)的參數(shù)配置或供需突變預(yù)測(cè)具有指導(dǎo)意義。

除此之外，RPCP算法還可以對(duì)其他參數(shù)組合或其他系統(tǒng)屬性進(jìn)行仿真，如系統(tǒng)穩(wěn)定性、lct最值、lct標(biāo)準(zhǔn)差以及資源定位平均時(shí)間等。

5 結(jié) 語(yǔ)

本文對(duì)傳統(tǒng)PC問題算法進(jìn)行改進(jìn)，使其能應(yīng)用于具有同步和互斥約束關(guān)系的多主體隨機(jī)資源訪問復(fù)雜系統(tǒng)離散事件仿真。在多處理機(jī)平臺(tái)上進(jìn)行仿真，仿真效率主要取決于處理機(jī)數(shù)量。經(jīng)實(shí)驗(yàn)驗(yàn)證，算法滿足隨機(jī)性、高并發(fā)性、同步和互斥正確性等特點(diǎn)。對(duì)RPCP算法的資源定位碰撞次數(shù)進(jìn)行了仿真實(shí)驗(yàn)，獲得了資源定位碰撞次數(shù)的突變臨界點(diǎn)，對(duì)現(xiàn)實(shí)系統(tǒng)的參數(shù)配置或生產(chǎn)/消費(fèi)引發(fā)突變的臨界點(diǎn)進(jìn)行預(yù)測(cè)具有指導(dǎo)意義。RPCP算法可以很容易泛化為其他任意特定時(shí)間同步互斥約束關(guān)系的并行主體隨機(jī)行為的任意參數(shù)的系統(tǒng)。

參考文獻(xiàn)

[1] 梅可玉.論自組織臨界性與復(fù)雜系統(tǒng)的演化行為[J]. 自然辯證法研究,2004,20(7):6-9,41.

[2] 劉曉平,唐益明,鄭利平.復(fù)雜系統(tǒng)與復(fù)雜系統(tǒng)仿真研究綜述[J].系統(tǒng)仿真學(xué)報(bào),2008,20(23):6303-6315.

[3] 李昊,戴金海.基于Agent的建模與仿真支持下的復(fù)雜系統(tǒng)效能分析法[J].系統(tǒng)仿真學(xué)報(bào),2008,20(15):3911-3914,3919.

[4] 陶麗,駱亮,張自力,等.基于Multi-Agent的手術(shù)等待時(shí)間時(shí)空模式建模與仿真[J].系統(tǒng)仿真學(xué)報(bào),2017,29(5):979-987.

[5] 李禎,邱曉剛,郭剛,等.面向大規(guī)模人工社會(huì)的異構(gòu)并行仿真引擎設(shè)計(jì)[J].系統(tǒng)仿真學(xué)報(bào),2014,26(10):2285-2292.

[6] 宋智超,孟榮清,邱曉剛,等.面向應(yīng)急管理的人工社會(huì)生成系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].系統(tǒng)仿真學(xué)報(bào),2014,26(10):2253-2257.

[7] 邱曉剛,孟榮清,陳彬,等.社會(huì)性突發(fā)事件平行應(yīng)急管理方法研究[J].系統(tǒng)仿真學(xué)報(bào),2014,26(10):2239-2246.

[8] 廖守億,戴金海.基于多Agent的天戰(zhàn)系統(tǒng)建模與仿真方法研究[J].計(jì)算機(jī)仿真,2003,20(1):18-21.

[9] 覃威寧,鄭天舒,沈旭昆,等.基于Multi-Agent的實(shí)體建模與時(shí)間同步方法研究[J].系統(tǒng)仿真學(xué)報(bào),2014,26(9):1933-1938.

[10] 眭俊華,劉慧娜,王建鑫.多核多線程技術(shù)綜述[J]. 計(jì)算機(jī)應(yīng)用,2013,33(S1):239-242,261.

[11] 何倩,孟祥武,陳俊亮.并發(fā)計(jì)算重復(fù)問題與控制方法[J].軟件學(xué)報(bào), 2011,22(10):2263-2278.

[12] 湯小丹,梁紅兵,哲鳳屏,等.計(jì)算機(jī)操作系統(tǒng)[M].西安電子科技大學(xué)出版社,2014:49.

[13] 李曉宇.操作系統(tǒng)中并發(fā)進(jìn)程的生產(chǎn)者—消費(fèi)者問題的研究[J]. 許昌學(xué)院學(xué)報(bào),2013,32(2):52-56.

[14] 劉曉平,石慧,凌實(shí),等.基于信號(hào)量的生產(chǎn)者-消費(fèi)者問題設(shè)計(jì)與分析[J].合肥工業(yè)大學(xué)學(xué)報(bào),2008,22(5):84-88.

[15] 范容, 胡則輝. 兩種解決生產(chǎn)者—消費(fèi)者問題的Java實(shí)現(xiàn)模型[J]. 現(xiàn)代計(jì)算機(jī):專業(yè)版, 2006(6):100-103.

[16] 周維, 周可人, 欒鐘治,等. 基于共享內(nèi)存的多核時(shí)代數(shù)據(jù)結(jié)構(gòu)研究[J]. 軟件學(xué)報(bào), 2016, 27(4):1009-1025.

[17] 高嵐,王銳,錢德沛.多核處理器并行程序的確定性重放研究[J].軟件學(xué)報(bào),2013,24(6):1390-1402.

[18] Herlihy Mauice, Shavit Nir.多處理機(jī)編程的藝術(shù)[M].金海,胡侃,譯.北京:機(jī)械工業(yè)出版社,2009:13-20.

[19] 白戈力.生產(chǎn)者與消費(fèi)者問題在JAVA中的實(shí)現(xiàn)[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào),,2006,27(2):117-121.

[20] 彭民德. 基于Web的生產(chǎn)者-消費(fèi)者同步問題的實(shí)現(xiàn)技術(shù)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 42(22):50-51,58.