随机性生产者消费者问题并行算法及仿真应用

2018-05-22鲁向前谢垂益

计算机应用与软件 2018年5期

鲁向前谢垂益霍英

1(韶关学院数学与统计学院广东韶关 512005)2(韶关学院信息科学与工程学院广东韶关 512005)3(密苏里州立大学计算机科学系美国密苏里州斯普林菲尔德 65897)

0 引言

社会、经济、交通、能源、军事、计算机技术等领域广泛存在着多主体对多个资源的随机的和受同步互斥等规则约束的生产和消费现象。例如城市中所有可出租的房屋或共享单车或出租车都是资源，其出租和退租是对资源的消费和生产。又如城市中能提供的工作岗位是资源，而工作岗位的离职和入职分别是对资源的生产和消费。再如小区周围的公共停车位是资源，而车位的占用和空出分别是对资源的消费和生产，也如医院住院系统中，床位是资源，病人住院时病人是资源(床位)的消费者，而医生治愈病人时医生是资源的生产者。伴随资源数量、资源供需双方数量的变化，可能会引起社会、经济、能源甚至军事事件的突变。这类现象过程中，主体对资源的使用具有并发性、随机性和同步互斥约束性，还具有演化性、突变性等特性，并具有复杂系统[1]的许多属性。

刘晓平等[2]对复杂系统的各种仿真方法做了较为全面的分析，指出仿真理论、技术和方法作为一种新的认识改造客观世界的重要手段，应用于复杂系统研究具有非常重要的意义。复杂系统由于其病态结构或机理复杂，在没有完全认识到其内部机理之前无法通过建立系统的原始量到系统属性的函数关系，无法建立完全精确的模型，已有的基于解析模型的传统建模方式并不能很好地刻画复杂系统，传统的数学方法对复杂系统现象的描述和分析能力有限[3]。因为排队论中关于随机变量服从某一统计分布的假设在现实世界中不一定得到满足等原因，因此采用排队论等运筹学方法来理解等待时间时空模式的涌现机理不太合适[4]。

从仿真应用上来说，本文前面提出的现象及本文后面提出的算法可以隶属于人工社会仿真ACP (Artificial Society，Computational Experiments Parallel Execution)范畴。人工社会仿真是研究社会科学的有效手段[5]，在当前计算机与仿真技术条件下，ACP方法已经成为一种研究人工社会这类复杂系统的重要方法[6]。邱晓刚[7]等对社会中的突发事件应急处理的角度对ACP方法进行了深入研究，但是，人工社会仿真拥有广阔的应用天地，从其他角度探索人工社会仿真及研究其社会现象内在机理和重要特征对丰富人工社会仿真具有重要意义。

1 相关工作

基于Multi-Agent System(MAS)[8]的理论和技术为复杂系统建模与仿真实现提供了一个崭新的途径，该方法吸取了分布式人工智能和人工生命理论，适于建立非线性的复杂系统仿真。然而，MAS环境中众多的Agent对象在分布环境中运行，Agent的复杂行为需要在分布的环境中合成和复用，Agent需要不断的协同和通信，由于分布式环境中各行为主体的异步执行和同步需求，其同步的实现代价是昂贵的。虽然美国国防部提出的高层体系结构HLA给出了较好的解决办法，它通过联邦及联邦成员的管理，能够有效地实现联邦成员间的通信及同步，但是对于内部的联邦成员的复杂行为并未提供较多的支持[9]。由于分布式环境天然的本质特性，其仿真系统的同步、开发、调试、部署、运行并不容易。

分布式仿真环境中，为每个主体分配一个计算机节点是不现实的。因此，归根结底，一个单一的计算机节点需要仿真多个主体。然而，对于单处理机计算机系统来说，许多主体都在单一处理机上仿真运行明显存在效率问题，而且它还与现实系统中的多主体并行现象不一致，仿真效果是值得怀疑的。多核CPU的出现和快速发展以及操作系统和编译器对多核CPU的支持，使我们能够在多核单一计算机环境中完成以前需要在分布式环境中才能完成的仿真，这使得系统开发、调试、部署等更加高效和容易，仿真的同步可靠性将会更加容易验证，仿真效率将会更高。

多核环境下软件开发的核心是多线程开发[10]，多线程并发程序可以提高硬件系统的运行效率[11]。然而，并发执行的多个线程通过共享内存中的数据结构来进行通信和同步，随着内核数量的增多，程序对共享资源访问的冲突加剧，大量并发运行的线程交替地修改数据，产生不可预期的结果，因而面临严峻挑战[10]。多线程并发程序往往存在同步及互斥约束关系，如果同步互斥约束关系十分复杂，则算法正确性容易出错，设计应用程序时要考虑资源要求和潜在冲突，实现上难于掌握。

生产者消费者PC(Producer-Consumer)问题是操作系统中关于多线程(进程)并发程序中同步与互斥的综合运用的一个经典模型。传统PC模型是用于研究基于单处理机平台下操作系统中的并发问题，很少考虑并行计算。在传统模型中，所有生产者和消费者进程都是按FIFO(First Input First Output)且异步方式执行，他们之间必须保持逻辑上的同步，既不允许消费者进程到一个空的缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品[12]。文献[13]根据生产者、消费者以及缓冲区的数量，把生产者-消费者问题分成了8种情况进行讨论。文献[14-15]提出了两种解决方案:(1)对所有生产者、消费者设置单一互斥信号量实现所有生产者和CT对队列的互斥访问;(2)对生产者线程群和消费者线程群各设置一个互斥信号量对队列的互斥访问。本文把第一种模型简称为单互斥FIFO队列缓冲区模型SMLQB(Single Mutex Loop Queue Buffer)，把第二种模型简称为双互斥FIFO队列缓冲区模型DMLQB(Double Mutexes Loop Queue Buffer)。这两种方案在现有实现中比较具有代表性和传统性，虽然他们都能够完成PC问题的模拟求解，但在多处理机平台下，不能充分利用多处理机的计算资源，运行效率低下。

另外，传统的PC模型的FIFO队列模型在用于规划良好、行为规范的现实情景仿真非常合适。然而，现实中的生产者与消费者对资源的使用并非完全按照队列机制运转。相反，许多情形下生产者和消费者对资源使用表现出随机性，因此，用传统的PC模型进行仿真时并不符合真实世界的许多随机现象。本文对该模型给予了改进，充分利用多处理机平台的优势，使其能应用于具有同步和互斥约束关系的多主体随机资源生产消费的模型仿真。它具有多个同步互斥对象、随机缓冲区使用、高度并发的特征(为与前文提到的两种模型区分，把改进后的模型简称为随机性生产者消费者问题并行RPCP)算法。最后把算法用于复杂系统的资源定位次数突变性仿真，从数量上获得资源定位碰撞次数的突变临界点，对现实系统的参数配置或供需突变预测具有指导意义。

2 RPCP算法设计

文中用到的参数或原语定义如表1所示。

表1 参数和原语定义

续表1

RPCP算法问题模型定义为：生产者线程集合PTs={PTk|(k=1,2,…,PN)}，消费者线程集合CTs={CTk|(k=1,2,…,CN)}，所有线程并发执行，缓冲区集合{Bk|(k=1,2,…,BN)}。模型要求:(1) 要尽可能地使所有PT和CT最大程度并发并且本质上能最大程度地并行执行，各线程的执行顺序完全由操作系统调度决定;(2)每个线程生产或消费资源的缓冲区号是随机的;(3)所有线程对每个缓冲区的操作必须是互斥的;(4)每个缓冲区必须在PT生产资源操作全部完成后才能由CT进行消费资源操作，是一种同步关系;(5)每个缓冲区必须在CT消费资源操作全部完成后才能由PT进行生产资源操作，也是一种同步关系。

RPCP算法的主要策略有:

(1) 把选择缓冲区号与实际缓冲区操作分成两阶段完成，分别进行各自的同步和互斥并发控制，减小并发粒度，提高并发度并同时提高并行度。

(2) 为了实现上述策略，为每一个缓冲区设置两个状态标志：缓冲区满标志f_F和缓冲区空标志e_F，这是实现细粒度RPCP算法的关键。

(3) 为每一个缓冲区号设置互斥对象g_m。

(4) PTs中的每一个PT互斥地选择空缓冲区号，CTs中的每一个CT互斥地选择满缓冲区号。

(5) 所有已选定空缓冲区号的PT可以并发地对各自的缓冲区进行生产操作，任何一个PT在完成生产后，都应向CTs发出同步信号。

(6) 所有已选定满缓冲区号的CT可以并发地对各自的缓冲区进行消费操作，任何一个CT在完成消费后，都应向PTs发出同步信号。

(7) 对某个特定的缓冲区，PT的生产操作和CT的消费操作全局互斥。

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

算法1生产者线程群函数算法

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消费者线程群函数算法

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 实验结果分析和讨论

3.1 并发正确性验证

复杂同步关系的多线程程序不但设计难度大，而且也不易调试，多线程并发正确性是算法可用性的前提。多线程并发正确性包括同步正确性、互斥正确性、无死锁正确性、无饥饿正确性、线程退出正确性及应用逻辑正确性等。

多核处理器并行程序的确定性重放[17]是实现并行程序调试的有效手段，但由于多核架构下存在共享访存不同步问题，并行程序确定性重放的研究和实现依然面临多方面的挑战。文献[18]使用了一种形式化的方法来描述和证明并行算法的正确性。对于少量局部范围内的同步对象，使用该方法进行证明是可行的，但对于大量的复杂的并行系统，其证明过程本身将会变得难以描述。

对于某种特定的并发问题的调试，往往使用特殊的调试方法更为有效。学术界和工业界广泛使用实验方法观察并发系统的结果来验证算法的正确性。因此一个易于调试易于观察并发过程和判断同步互斥结果正确性的实验输出控制方法非常重要。传统上，对于多线程程序的输出验证，有多种方案可供选择，例如:(1)编写控制台程序进行输出，如文献[15];(2)所有线程的输出都显示在同一个窗体中，如文献[19-20];(3)各线程各自使用基于共享主线程窗口内的多个子窗口进行输出。这些方案都有一个共同的缺点:多个线程共用一个输出区域或者共用一个消息循环，本质上是“并发执行，串行输出”的耦合输出方式，会影响并发性观察和正确性判断。

本文使用一种新的验证方法，把RPCP算法移植到GUI环境中，给每个PT和每个CT都创建自己独立的输出窗口，每个窗口使用独立的窗口过程函数，并使用适当的行控制技术和动态交互控制技术，各自完全无耦合的显示结果。

算法的无死锁正确性、无饥饿正确性、线程退出正确性容易判断。下面主要对同步正确性、互斥正确性作简要论述。PTk对应的窗口标记为PW={PWk|k=1,2,…,PN}，CTk对应的窗口标记为CW={CWk|k=1，2，…，CN}。设线程k(窗口k)在t时刻的输出行号表示为L(wk,t)，其对应的调试输出信息表示为元组(BL,SL)(BL表示线程正在操作的缓冲区号,SL表示缓冲区的操作动态信息)，对于任意t1>t2有L(wk,t1)> (wk,t2)。对于∀(i,t)，比较L(wi,t)和L(wj,t)(j=1,2，…，PN+CN,i≠j)的元组(B1,S1)和(B2,S2)，如果有B1=B2，则存在互斥错误。对于∀(i,t1,t2)，比较L(wi,t1)和L(wj,t2)(j=1,2，…，CN,i≠j,t1B1，则能保证PT序对CT的同步正确性，把此表述稍作调整不难判断CT对PT的同步正确性。

在验证过程中，在任意时刻t，用户可以暂停或继续所有线程的运行，观察线程并发执行的当前状态。各线程窗口的输出时序与系统内部的计算过程完全精准对应，没有任何输出耦合，便于随时观察和验证结果的正确性。此验证方法十分简便，反复验证结果证明算法是稳定和正确的。

3.2 随机性分析

本算法的应用逻辑正确性主要表现为随机性是否正确。随机性是普遍存在的现象，是算法应用于复杂系统随机性仿真的基石。多线程的随机数产生与单线程随机数产生原理上并不相同，本文使用了线程安全的随机数产生方法实现随机数产生的正确性。

首先对PT操作的缓冲区号的随机性进行分析。测试任务PN×CN×BN参数为24×35×18，测试10次。对每次实验中每个缓冲区号被PT群选中的次数进行累加，得到统计数据，相应的折线图如图1所示。从统计结果看，各缓冲区编号被PT选中操作的次数是均衡的。

图1 每个缓冲区号被PT群选中的总次数

再考察CT群中每个CT所消费的缓冲区个数，仍然以10组测试数据进行累加，统计出每个线程编号所消费的缓冲区总个数，相应的折线图如图2所示。从总体上来看，各CT所消费的缓冲区个数都相对一致，说明各CT的负载是均衡的。

图2 每个CT消费的缓冲区个数总和

3.3 并行度分析

为了比较三种算法在执行性能上的差异，在不同参数配置的机器上进行不同任务参数的实验，每台机器每个任务的每种算法均运行10次，测试每次运行的耗时，统计每台机器每种算法的10次运行耗时的平均值。为避免循环级任务并行[16]的编译优化而影响测试时间的准确性，每次测试是独立进行而非在同一进程中循环测试。

定义:加速比A1=t(SMLQB)/t(DMLQB);加速比A2= t(DMLQB)/t(RPCP)，其中t()表示算法运行消耗时间。实验结果数据如表2所示，其中任务编号1～3的任务参数PN×CN×BN的值分别取24×24×24、100×24×24、24×24×5000。

表2 并行度实验结果

表2中理想加速比是指在不考虑CPU被操作系统及其他应用程序占用而导致性能损耗的情形下所得到的三种算法性能对比。

从表2中的实验结果可以看出，实验结果的加速比很好地拟合了理想加速比，说明RPCP算法并行执行的线程数与CPU核数基本相同，在多处理机平台上其并行度远高于传统的算法。

4 资源定位碰撞次数的涌现性仿真

在RPCP算法的步骤j=LoopSafeLocate**()中，线程以线程安全的循环测试方式随机选择一个空/满的缓冲区编号j，以定位符合同步和互斥条件的可用资源号。我们把线程从开始新一轮生产/消费到成功定位到一个可用资源号所经过的循环次数定义为资源定位碰撞次数lct。从仿真意义上来说，lct可以代表真实世界中如石油需求国从市场成功获取石油的时间代价，也可代表如求职者从求职开始到求职成功过程中求职失败的碰壁次数，也可对应于出租车乘客从开始寻找出租车到成功乘坐出租车所尝试的招租次数。从本质上来说，lct的大小反映了主体获取资源的代价、系统资源的利用率或客户获取资满意度，如果资源配置过多，会造成资源的浪费，配置过少，客户在定位可用资源的时间花销增多，满意度会降低。

此处定义时间因子tf为:tf=tp/tc，tp表示生产者从获取一个缓冲区号开始到成功完成一个产品的生产所耗费的时间，tc表示消费者从获取了一个缓冲区号开始到成功完成一个产品的消费所经历的时间。另外，为使研究着重于系统整体性能，lct是基于平均意义下的值。

显然，lct的大小与PN、CN、BN、tf等有关。例如，在PN、CN及tf确定的情况下，BN过大，则PT的lct会很小，但CT的lct会很大，BN过小则会有相反的结果。由于系统具有多个主体行为并行且特殊的同步约束关系，使用概率模型无法对lct建立完全精确的模型，已有的基于传统建模方式的解析模型并不能很好地刻画复杂系统。因此，使用仿真的方法来捕获与研究事物的演化规律，以达到对系统演化特性或其他特性的研究。图3是在PN×CN×BN×tf参数值分别为X×64×64×1、X×32×64×1、X×64×32×1情形下PT群的lct仿真结果。图4是在PN×CN×BN×tf参数值分别为X×64×64×0.5、X×64×64×1、X×64×64×2情形下PT群的lct仿真结果。CT群和PT群的仿真结果具有对称性。

图3 tf=1情形下不同任务组合的影响

图4 X×64×64情形下不同时间因子的影响

从所有仿真结果看，lct具有明显的突变临界窄区间，在突变临界窄区间左侧，lct的变化非常缓慢，在突变临界窄区间右侧，lct的变化保持在一定的稳定饱和状态。这种临界突变性与量变引起质变的唯物辩证法的基本规律相一致，然而哲学上对量变引起质变一般是进行定性研究，即并不解决究竟要多大的量变才能引起质变的问题。因此，我们可以在已知现实系统参数组合配置下先用RPCP算法进行仿真实验，获得突变临界点，然后对现实系统的生产者群体、消费者群体或资源数量等参数进行控制，使lct保持在较低水平，从而提高资源利用率并能保持较高的客户满意度。因此从数量上捕获到的仿真突变临界点对于现实系统的参数配置或供需突变预测具有指导意义。

除此之外，RPCP算法还可以对其他参数组合或其他系统属性进行仿真，如系统稳定性、lct最值、lct标准差以及资源定位平均时间等。

5 结语

本文对传统PC问题算法进行改进，使其能应用于具有同步和互斥约束关系的多主体随机资源访问复杂系统离散事件仿真。在多处理机平台上进行仿真，仿真效率主要取决于处理机数量。经实验验证，算法满足随机性、高并发性、同步和互斥正确性等特点。对RPCP算法的资源定位碰撞次数进行了仿真实验，获得了资源定位碰撞次数的突变临界点，对现实系统的参数配置或生产/消费引发突变的临界点进行预测具有指导意义。RPCP算法可以很容易泛化为其他任意特定时间同步互斥约束关系的并行主体随机行为的任意参数的系统。

参考文献

[1] 梅可玉.论自组织临界性与复杂系统的演化行为[J]. 自然辩证法研究,2004,20(7):6-9,41.

[2] 刘晓平,唐益明,郑利平.复杂系统与复杂系统仿真研究综述[J].系统仿真学报,2008,20(23):6303-6315.

[3] 李昊,戴金海.基于Agent的建模与仿真支持下的复杂系统效能分析法[J].系统仿真学报,2008,20(15):3911-3914,3919.

[4] 陶丽,骆亮,张自力,等.基于Multi-Agent的手术等待时间时空模式建模与仿真[J].系统仿真学报,2017,29(5):979-987.

[5] 李祯,邱晓刚,郭刚,等.面向大规模人工社会的异构并行仿真引擎设计[J].系统仿真学报,2014,26(10):2285-2292.

[6] 宋智超,孟荣清,邱晓刚,等.面向应急管理的人工社会生成系统设计与实现[J].系统仿真学报,2014,26(10):2253-2257.

[7] 邱晓刚,孟荣清,陈彬,等.社会性突发事件平行应急管理方法研究[J].系统仿真学报,2014,26(10):2239-2246.

[8] 廖守亿,戴金海.基于多Agent的天战系统建模与仿真方法研究[J].计算机仿真,2003,20(1):18-21.

[9] 覃威宁,郑天舒,沈旭昆,等.基于Multi-Agent的实体建模与时间同步方法研究[J].系统仿真学报,2014,26(9):1933-1938.

[10] 眭俊华,刘慧娜,王建鑫.多核多线程技术综述[J]. 计算机应用,2013,33(S1):239-242,261.

[11] 何倩,孟祥武,陈俊亮.并发计算重复问题与控制方法[J].软件学报, 2011,22(10):2263-2278.