并发程序（共4篇）
并发程序 篇1
0引言
如果将程序内部的语句(或程序段)之间设计成并发执行,则可以加快程序的运行速度,提高资源的利用率。程序并发度越高,系统的性能就越好,用户越满意。但是,程序内部的语句(或程序段)之间并不都是可以并发执行的,有些语句之间有严格的先后关系,因而在设计并发程序时,必须严格保证这些先后关系的正确性,否则程序运行时就会出错。找出程序里语句(或程序段)之间所有的先后关系,成为了并发程序设计的关键。然而,不借助于一定的辅助方法,只在程序里查找语句(或程序段)之间的先后关系,不直观、不形象,而且容易出错。
优先图PG是一种描述顶点间先后关系的有向无圈图。优先图常用于描述具有先后约束关系的工程问题[1]。实际上,优先图也可以用来辅助并发程序设计,利用优先图描述并发程序内语句之间的先后关系,将使得并发程序的设计变得更加直观、简便、不易出错。利用优先图辅助并发程序设计的一般步骤是:原程序→优先图(化简)→并发程序。即根据原程序内部语句间存在的先后制约关系,将其描绘成优先图,化简优先图,再将优先图转换为并发程序。
1语句之间的先后关系
程序里语句(或程序段)之间,常常存在着一些先后制约关系。例如:变量要先赋值、后读取,这样,针对同一变量的赋值语句与读变量语句(或程序段)之间就存在先后关系;函数、过程或子程序要先定义、后调用,那么,定义函数的程序段与调用该函数的语句(或程序段)之间也存在着先后关系;还有程序流程图中有许多其它先后关系,等等。尽管语句(或程序段)之间的先后关系有许多种,但都可以用如下方法来判定:
对于程序里的两个语句(或程序段)Si和Sj,如果存在“只有当Si执行完以后,才能执行Sj”的制约关系,则称Si和Sj之间存在着先后关系[2]。这就是判断程序里两个语句(或程序段)之间是否有先后关系的依据。
一个程序里,存在着先后关系的语句(程序段)往往不只一对,对于较复杂的大程序,可能有许多具有先后关系的语句(或程序段)。必须把这些先后关系全都找出来,才能设计出正确的并发程序。如果在查找程序中语句之间的先后关系时,不采用一个较好的方法来描述,当先后关系很多、很复杂时,就很容易遗漏一些、或者将一些先后关系弄错。
2优先图概况
优先图是由顶点集合V和有向边集合A组成的有向无圈图D=(V,A),从顶点Vi指向顶点Vj的有向边表示:只有当Vi完成后,才能执行Vj[2]。
优先图无圈 (no cycle),也一定无环(no loop)[3]。图1(a)所示的有向图含有向圈<V2,V3,V4,V2>,该有向圈表示:只有V2完成以后才能执行V3,只有V3完成以后才能执行V4,只有V4完成以后才能执行V2,这是自相矛盾的先后关系,因而不是优先图;图1(b)所示的有向图中含有自环<V3,V3>,该环表示:只有V3完成后才能执行V3,明显地自相矛盾,因而也不是优先图。图2(a)和(b)所示的有向图无圈无环,因而是优先图,其中图2(a)所示优先图表示的先后关系是:只有当V1完成以后才能执行V2,只有当V2完成以后才能执行V3,只有当V2和V3都完成以后,才能执行V4。
定义1 起点与终点。在优先图中,与有向边的尾部相连的顶点叫起点,与有向边的箭头相连的顶点叫终点。
3用优先图描述程序内先后关系
优先图非常适合描述程序内语句(或程序段)之间的先后关系:用优先图中的顶点代表程序里的语句(或程序段),用连接顶点的有向边表示语句(或程序段)之间的先后关系,图中的有向边表示只有当起点语句执行完以后,才能执行终点语句;当有多条有向边指向同一个顶点(终点)时,即表示:只有与该终点相连的所有有向边的起点语句都执行完以后,才能执行该终点语句。我们来看一个简单实例。
例1 对于图3(a)所示的一段程序,每条语句前已加上标记(V1、V2、V3和V4)。将每一条语句用一个圆形顶点表示,顶点名称即为该语句的标记名称,得到优先图的顶点集(如图3(b)所示)。
对于每两条语句间是否存在优先关系,只看它们之间是否存在“只有当Si执行完以后,才能执行Sj”的关系即可。不难看出:只有当赋值语句“a=1;”(对应于图3(b)中的V1顶点)和“b=2;”(对应于图3(b)中的V2顶点)都执行完以后,才能执行运算语句“c=a+b;”(对应于图3(b)中的V3顶点),因而顶点V1与V3有先后关系、顶点V2与V3也有先后关系。在图3(b)中,应该以顶点V1和V2为起点,分别画一条有向边到达终点V3。同理,只有当顶点V1、V2和V3相应的语句都执行完以后,才能执行顶点V4对应的语句(write(c);),应该以V1、V2和V3为起点,分别画一条有向边到达终点V4。从而得到如图3(c)所示的优先图。
上述实例推而广之,得到将程序描绘成优先图的方法如下:
Step1 将程序中每个语句(或程序段)加上标记,并给所有的标记命不同的名字(如V1、V2、V3……),转step2;
Step2 将每一条语句(或程序段)在优先图中用一个圆形顶点表示,顶点名称为该语句(或程序段)的标记名称,得到优先图的顶点集,转step3;
Step3 观察优先图中的两个顶点,分析它们对应的两个语句(或程序段)之间是否存在“只有当Si执行完以后,才能执行Sj”的先后关系,转step4;
Step4 若存在先后关系,则从先执行语句相应的顶点(起点),画一条有向边到达后执行语句相应的顶点(终点),然后转step5;若无先后关系,则直接转step5;
Step5 如果优先图中任何两个顶点之间的关系都已分析完毕,即所有的先后关系都已找出,并在优先图中画出了相应的有向边,则优先图完成。否则,转step3。
使用该方法,可以将图3(a) 所示的程序段转换为如图3(c)所示的优先图。该方法既可以将一个完整的程序转换为优先图,也可以将一段程序转换为优先图。
从上例可以看出,采用优先图来描述程序里语句之间的先后关系,很形象、很直观,而且结构完整、清晰,便于分析、不易出错、不易遗漏。
4优先图转换为并发程序
设计并发程序,就是尽可能多地让程序里的语句(或程序段)并发执行。并发程序设计的基本方法就是:首先将程序内所有语句(或程序段)全部设置成可并发执行,然后采用信号量和P、V操作原语把语句(或程序段)间所有的先后关系都控制好[2]。
将原始程序描绘成优先图以后,顶点之间的所有先后关系就非常明确地表现出来了,接下来就要把优先图转换为并发程序。
将优先图转换为并发程序,只要按照如下五步操作即可:
Step1 为优先图中的每一条有向边定义一个信号量,并给所有的信号量赋初始值0,转Step2;
Step2 预设所有顶点对应的语句(或程序段)都可以并发执行,将这些语句(或程序段)并列书写在同一并发语句(如parbegin……parend)内,转Step3;
Step3 考虑优先图中的一条有向边,在与之相连接的起点语句的后面,加一个V操作,起唤醒作用;在与之相连接的终点语句前面,加一个对应的P操作,起等待作用;然后,转Step4;
Step4 重复step3的操作,直至将所有的有向边全部转换成P、V操作对。然后,转Step5;
Step5 将每一个顶点语句,以及附加在它前面的所有P操作、附加在它后面的所有V操作,用一个复合词(如begin……end)前后组合,形成一个复合语句。
转换完毕。
采用该算法转换成的并发程序,除了有先后关系的语句(或程序段)不可并发外,其余语句都是可以并发执行的。
按照该算法,将图3(c)所示的优先图可以转换成如下并发程序:
var g,h,i,j,k: semaphores;
(initial value of all semaphores is 0)
begin
parbegin
begin a=1; V(g);V(h); end;
begin b=2; V(i);V(j); end;
begin P(g);P(i); c=a+b; V(k); end;
begin P(h);P(j);P(k); write(c); end;
parend;
end;
在该并发程序中语句“a=1;”与“b=2;”是并发执行的。
5优先图的化简与并发程序的简化
有些优先图是可以化简的,例如图4(a)所示的优先图就可以化简为图4(b)。
证明:图4(a)中有三条有向边<V1,V4>、<V3,V4>和<V2,V4>指向同一个顶点V4,说明只有当V1、V3和V2都完成以后,才能执行V4。然而,从图示先后关系中可以看出:当V3完成时,V1和V2早已完成。因此,指向V4的2条有向边<V1,V4>和<V2,V4>是多余的,可以省略掉。于是,图4(a)所示优先图可以化简为图4(b)所示。证毕。
同理,图4(c)所示优先图中的有向边<V2,V4>也可以化简掉,化简为图4(d)所示优先图。
将图3(c)(即图4(a))所示的优先图化简为图4(b)以后,对应的并发程序变为:
var g,h,i: semaphores;
(initial value of all semaphores is 0)
begin
parbegin
begin a=1; V(g); end;
begin b=2; V(h); end;
begin P(g);P(h); c=a+b; V(i); end;
begin P(i); write(c); end;
parend;
end;
通过前后两个并发程序对比,可看出:优先图化简后,并发程序的复杂性降低了。信号量由化简前的5个(g,h,i,j,k)减少为化简后的3个(g,k,i),P、V操作也由原来的5对减少为3对。可见,通过化简优先图,可以降低相应并发程序的并发控制复杂性。需要注意的是,化简优先图以后,并没有改变程序的并发性质。图3(c)对应的并发程序中,只有“a+1;”与“b+2;”可并发执行;化简为图4(b)以后,依然只有“a+1;”与“b+2;”是可并发执行的。
6结束语
并发程序设计的关键在于找出程序里语句(或程序段)之间所有的先后制约关系,使用优先图辅助并发程序设计,能够简明地显示这些先后关系,便于快速、准确地找出程序里全部的先后关系,为并发程序的设计带来极大的方便。本文论述了优先图辅助并发程序设计的过程:原程序→优先图(化简)→并发程序,阐述了将程序描绘成优先图的方法和将优先图转换为并发程序的步骤。同时,发现有些优先图可以化简,化简以后,相应的并发程序的并发控制复杂度降低了。关于优先图的化简算法,将在下一步工作中研究。
参考文献
[1]刘翔,姜双斌.基于PG图的空间信息服务链建模方法[J].重庆:后勤工程学院学报,2005,2.
[2]邹鹏,罗宇,王广芳等.操作系统原理[M].第二版.长沙:国防科技大学出版社,1995.
[3]徐俊明.图论及其应用[M].合肥:中国科技大学出版社,1998.
并发程序 篇2
关键词：多线程程序,原子性错误,线程序列的不确定,模型检测
0 引 言
现代软件中广泛地使用多线程技术,但这种技术容易引发并发错误,比如死锁、数据竞争、原子性错误等。多线程程序分析的难点在于程序运行时的线程序列不确定。同样的输入会有不同的结果,因此分析多线程程序要考虑到所有可能的线程序列。
原子性特征对于并发程序很重要,若某线程对某共享对象的连续迁移序列具备原子性,意味着它不允许别的线程在该序列中间对该对象进行读或写。违反了原子性而导致程序出错,就属于原子性错误。这种错误已经出现在Apache、MySQL等著名软件中[1]。图1是原子性错误的例子。foo程序的输入是num的值,计算10与num的和后,把结果输出到foo.out文件里。其中,存储num的内存以指针的方式被两个线程共享访问。对于输入是“./foo 5”期待输出是15的测试用例,运行时会出现这种情况:主线程运行到pthread_create执行后换foo_free线程运行,等到foo_free线程结束后主线程再接着运行。由于num被foo_free线程修改为0,最后输出结果是10,与预期结果15不符,测试出错。注意到:代码第10行和第12行对num的写操作和读操作,构成了主线程的一对原子性迁移。其他线程在该原子性迁移对之间对num做写操作,从而引起了原子性错误。
但并不是所有违反原子性的情况都会导致出错。发生在程序正确运行时的违反原子性的情况,称之为良性违反原子性。图2阐述了良性违反原子性的例子。当线程2把flag置为false后,进入循环,该循环直到线程1把flag置为true时才跳出。整个过程中线程1第2行代码的写操作发生在线程2第2行代码的连续的读操作之间,违反了线程2第2行代码的读操作的原子性,但是这样的线程运行序列符合程序员的意图,属于良性违反原子性的情况。在分析多线程程序的原子性时,要从违反原子性的执行序列中区分会导致程序出错的情况,否则会造成大量的错误误报。
为了对多线程程序做原子性错误检测,本文做了以下贡献:
1) 提出了原子性错误检测方法MC-AVIO。该方法首次将动态模型检测运用于多线程程序的原子性错误检测中。之前的原子性错误检测方法,都是基于静态程序分析,不能很好地解决多线程程序线程序列不确定的问题。本文用动态模型检测列举出多线程程序运行时所有可能的执行序列并做相应检测。
2) 实现了原子性错误检测工具AtomFinder,并在多组开源软件上评估了AtomFinder的原子性错误检测效果。这些程序分成两部分,一部分来自于inspect[2]基准程序库的正确程序,另一部分是对它们注入变异后的程序。AtomFinder都能发现注入的变异,并对正确程序没有产生误报。
1 背 景
模型检测作为一种重要的自动验证技术,可分为两类。第一类方法通过静态分析提取抽象模型 [3,4],第二类方法在程序执行时中动态搜索状态空间[5,6]。
为了解决并发程序模型检测的状态空间爆炸问题,在静态分析中引入了偏序规约技术,该技术使用稳定集和睡眠集对状态空间的搜索做剪枝[7],但静态分析得到的信息不准确,导致剪枝效果不佳。
C Flanagan和P Godefroid提出了动态偏序规约算法DPOR(Dynamic Partial-Order Reduction)[8]。该算法通过搜集运行时的信息,精确地计算代码间的依赖关系,进而实现了有效的剪枝。之后Yu Yang基于该算法实现的工具Inspect[3]可检测数据竞争、死锁等,但不支持原子性错误的检测。
2 方 法
本文提出的MC-AVIO方法从违反原子性的执行序列中识别出会导致程序出错的执行序列。MC-AVIO方法包括两个阶段:训练阶段和分析阶段,如图3所示。
MC-AVIO在训练阶段提取原子性迁移对。训练时运行目标程序的测试用例,当测试结果与预期相符时训练正确,这时提取原子性迁移对。每个迁移对是同一线程对同一变量的两次连续访问,期间没有其他线程对该变量的访问。MC-AVIO通过提取的原子性迁移对来学习程序员的编程意图,比如目标程序在正确运行时哪些代码段需要保持原子性,哪些代码段不需要保持原子性。原子性迁移对的原子性特征在程序正确运行时必须保证,如果不保证,就会违背程序员的意图,导致程序出错。然而良性违反原子性的迁移对也发生在程序正确运行时,程序员允许它们违反原子性,因此这些迁移对不会出现在原子性迁移对里。
MC-AVIO在分析阶段用模型检测方法检查程序员的意图是否在所有可能的线程执行序列上都满足。这些执行序列由DPOR算法计算得到。由于模型检测具备完备性,MC-AVIO能考虑到所有可能的执行序列,因此只要有一条执行序列违反了程序员的意图,就会被检查出来。
2.1 训练阶段
第1步 运行待测程序,若运行成功,则记下Set′all和Set′bv。Set′all是在本次训练中被访问到的读写共享对象的迁移对集合。Set′bv是Set′all中违反了原子性特征的迁移对集合。由于此次运行成功,Set′bv违反原子性的情况属于良性。训练时,随机运行待测程序。换句话说,线程运行的次序,完全由计算机CPU决定。
第2步 多次执行第1步,持续更新Setall和Setbv,直到二者持续Count次更新不再变化后,将Setall减去Setbv,得到Setatom。Setall是整个训练过程被访问到的读写共享对象的迁移对集合。Setbv是Setall中违反了原子性特征的迁移对集合,属于良性违反原子性。每次执行第2步,会得到该次训练的Set′all和Set′bv,将它们分别添加到Setall和Setbv里。最后得到的Setatom是原子性迁移对集合,将用于分析阶段的原子性错误检查。
以foo程序为例,用输入为“./foo 5”期待输出为15的测试用例训练时,会出现如图4、图5所示的2种情况。显然,在训练阶段结束后,Setall为{(10,12},Setbv为{},Setatom为{(10,12)}。
2.2 分析阶段
第1步 用DPOR算法算出待测程序还未运行过的一条线程执行序列,并用调度器控制待测程序按照该序列运行,同时通过分析迁移序列的原子性信息,来检查程序是否存在原子性错误。具体来说,如果某个迁移对pair在这条执行序列中违反了原子性,而它又在训练阶段结束后得到的原子性迁移集合Setatom中出现,则认为这条执行序列会导致程序产生原子性错误,因为Setatom中迁移对的原子性特征在程序正确运行时必须保证。在这里,程序的输入可以与训练阶段所用的测试用例不同,另外不检查程序的输出。
第2步 不断重复第1步,直到所有线程运行序列都被运行一次后,结束分析阶段。如果之前没有报出原子性错误,则认为该程序没有原子性错误。
以foo程序为例,假定分析阶段的输入是“./foo 0”。在这种情况下,DPOR算法得到的线程运行序列有2条,如表1所示。需要注意的是,不管程序按哪条线程序列运行,输出都是“10”。不过在分析阶段,不考虑程序的输出,只检查迁移序列的原子性信息。由于在第2次分析时,发现有一个违反原子性的pair∈Setatom,于是报告一个原子性错误。
3 实 现
AtomFinder的实现框架如图6所示。它由注入器和调度器组成。为了让调度器能控制并发程序的运行,注入器向并发程序的可见操作前注入插桩代码。当程序运行到注入位置时,插桩代码会向调度器发送一个描述该可见操作的socket请求,之后就一直等待调度器的回应,即线程处于悬挂状态。调度器收到多个线程的socket请求后,根据DPOR算法决定哪个线程先执行,对于先执行的线程,它立即发送同意运行的一个socket回应。当线程接到回应后就结束悬挂状态,继续执行。本文用Pin[9]实现注入代码。Pin提供了动态注入二进制程序的相关API。
交互框架中的可见操作拦截器实现了对可见操作的识别。这些可见操作是影响多线程程序交互和最终输出结果的操作,包括:
1) 对共享内存的读或写。
2) 与线程有关的操作,比如线程的产生、注销。
3) 与同步原语有关的操作,比如互斥锁的获取和释放,条件变量的等待和激发。
4 实 验
本文使用AtomFinder分别对5组开源软件程序做原子性错误检测。每组程序由正确的源程序,以及对它们注入并发错误变异的程序构成。这5个程序是Inspect基准程序库的子集。注入的变异包括SPCR变异(分离关键域)、EAN变异(移除原子性调用)[10]。这两种变异都会导致程序出现原子性错误。
实验结果如表2所示。AtomFinder的错误发现率为100%,并都能给出引发错误的线程执行序列。同时对于未注入错误前的正确程序,没有产生误报。
5 相关工作
对原子性迁移对的训练:早先的原子性错误检测算法需要程序员手动标上同步点[11],导致检测的人工代价大。之后工具Atomizer[12]采用锁集合算法和一些启发式方法自动识别具备原子性的程序代码块,解决了检测人工代价大的问题,但受锁集合理论的限制,识别准确度不高。相比较前面的方法,MC-AVIO通过测试用例的训练,得到程序的原子性迁移对,进而理解程序员的意图,再用这些迁移对做检测,检测准确度更高。
对并发程序的线程执行序列不确定性的处理:AVIO方法[13]和工具CTrigger[14]都采用了和本文类似的训练方法得到程序的原子性信息。但是在分析阶段,AVIO方法通过随机运行程序来检测错误,有些程序执行序列不会被考虑到。CTrigger基于并发错误经常发生在小概率的线程序列上的假设,进入分析阶段后,对程序注入sleep函数让程序尽可能地先按小概率的线程序列去运行,但这种方式不能完全控制程序的运行。本文实现的AtomFinder工具,使用DPOR算法得到所有线程序列,并用调度器控制程序按某条线程序列去运行,在处理并发程序的线程序列不确定性这一点上,保证了分析的完备性。
6 结 语
MC-AVIO方法用动态模型检测解决了并发程序分析面临的线程序列不确定问题,用训练提取原子性迁移对的方法从违反原子性的情况中识别出会导致程序出错的线程序列。最后的实验结果表明,基于MC-AVIO方法实现的AtomFinder工具对于原子性错误的检测是有效的。
但目前AtomFinder有一个不足,它将所有的内存操作都当作对可见内存的访问,虽然不影响检测正确性,但让调度器接受了许多无关的信息,导致检测效率较低。如果能基于静态分析找出多个线程通过指针访问的共享内存,只对它们做分析,检测效率将有明显提高。
并发程序 篇3
关键词：网络系统设计,程序设计,复杂性
网络系统设计中的程序设计并发复杂性问题是由于现今网络系统的性能和设计理念等多种因素所共同导致的, 因此只有在做好前期分析工作的前提下, 才能够促进网络系统设计中的程序设计并发复杂性得到有效的遏制。
1 网络程序并发性与复杂性简析
网络程序并发性与复杂性是由多方面引起的, 以下从环境差距过于明显、设计理念的限制、驱动模式有待优化等方面出发, 对于网络程序并发性与复杂性进行了分析。
1.1 环境差距过于明显
网络程序并发性与复杂性主要是因为单机环境和网络环境差距过于明显所导致的。大家都知道随着近年来高质量网络程序的不断开发, 之前传统程序设计过程中存在的许多问题都被暴露出来。在这一过程中可以发现网络环境与单机环境之间的巨大差异性成为影响程序开发设计的关键。其次, 并发性问题的存在实际上成为了网络程序设计发展的重要限制瓶颈, 因此, 如何能够对于并发性问题进行有效的解决, 成为了摆在程序设计人员面前的要点。与此同时, 环境差距过于明显还意味着混合性并发模型发展时间短和实际应用少的缺陷也会暴露出来, 因此其对于并发性问题的解决效果还需要进一步的观察。
1.2 设计理念的限制
网络程序并发性与复杂性的存在也跟之前的设计理念被软硬件功能限制有着密切的联系。通常来说网络程序的并发性问题的表现形式通常会以分布性、异构性、异步性和访问延误等形式表现出来。因此工作人员在将问题整合成一个整体后就会发现, 并发性问题变得极其难以解决。其次, 设计理念上的限制还会使得网络程序设计的整体效率受到非常大的影响。
1.3 驱动模式有待优化
网络程序并发性与复杂性和驱动模式有着千丝万缕的联系。由于网络并发任务处理方法实际上可以根据语义将其分为反应式和前摄式两种。在反应式模型中应用程序必须通过接收到相应的事件通知, 然后才能够在此基础上能够更加具有针对性的发出具体的操作指令, 在这一过程中如果操作的结果是错误的, 则工作人员可以从函数的返回值中即时获知。其次, 驱动模式有待优化还指的是操作的错误情况通常会作为完成事件的参数, 传递给应用程序如果需要同时发出多个相似的并发操作, 则需要在发出操作指令时, 增加一个标识参数, 从而能够在此基础上对于并发操作进行更加细致的区分。
2 网络程序并发性与复杂性问题应对
网络程序并发性与复杂性问题的应对应当从许多方面出发, 以下从优化多线程模型、协调程序运作顺序、开发新型并发模型等方面出发, 对于网络程序并发性与复杂性问题的应对进行了分析。
2.1 优化多线程模型
网络程序并发性与复杂性问题应对的第一步是合理优化多线程模型。工作人员在优化多线程模型的过程中首先应当根据多线程并发模型多线程并发模型的线程调度来对其进行分别的分析。其次, 工作人员在优化多线程模型的过程中应当确保线程的运行状况与应用层的控制无关, 在这一过程中CPU是由调度器来进行控制的, 并且调度器对于线程的调度是强制性的。与此同时, 工作人员在优化多线程模型的过程中应当合理的实现CPU控制权的强制转移, 从而能够在此基础上有效的规避因为上一个线程没有处理好当前线程所需要的各种数据, 引发数据竞争, 严重的甚因此, 在对线程协作复杂或者并发性高的任务进行处理, 最终可以减少系统出现崩溃的概率。
2.2 协调程序运作顺序
网络程序并发性与复杂性问题应对的关键是协调程序运作顺序。工作人员在协调程序运作顺利的过程中首先应当理解到与抢占式调度相比CPU的控制权具有更强的优先度, 因此这意味着只有在当前线程放弃数据处理后实际上才会将CPU的控制权转移到其他线程。其次, 作人员在协调程序运作顺利的过程中还应当确保应用程序的线程操作必须经过系统调用, 在这一过程中由于线程代码的移植具有很高的难度, 因此实际上非常严重的影响了其普遍适应性, 所以只有通过合理的协调才能够确保其运作顺序的合理优化。
2.3 开发新型并发模型
网络程序并发性与复杂性问题应对离不开新型并发模型的开发与利用。工作人员在开发新型并发模型的过程中应当优先对于混合性并发模型进行应用。其次, 工作人员在开发新型并发模型的过程中首先应当理解到无论是事件驱动模型还是多线程并发模型实际上都具有各自的优点和不足, 因此这导致了其在实际应用中始终存在一定的局限性。对因此设计人员在开发新型并发模型的过程中应当勇于打破常规合理的将这两种模型融合在一起, 最终能够期待形成全新的并发模型, 最终能够促进程序设计合理性的有效提升。
3 结束语
在网络程序的设计过程中并发性问题实际上是一个难以进行规避的复杂问题。因此工作人员在认清当前的技术条件下应当通过有效的提升网络程序的并发处理能力, 并且在此基础上并发模型的性能进行完善, 才能够促进网络程序设计效率的有效提升。
参考文献
[1]李慧霸, 田甜, 彭宇行, 等.网络程序设计中的并发复杂性[J].软件学报, 2011 (1) :132-148.
[2]高伟, 张学红.关于网络程序设计中的并发复杂性研究[J].网络安全技术与应用, 2014 (12) :49-51.
[3]潘珂, 田勇.网络程序设计中的并发复杂性研析[J].科技致富向导, 2014 (27) :84-85.
并发程序 篇4
Grand Central Dispatch (GCD)是苹果公司开发的一个多核编程的解决方法。该方法的需要在i OS4.0以上的版本中使用。
Dispatch Queues、Dispatch Source和Operation Queue是i OS中的多线程编程中通常使用的三种方法,开发过程通过使用它们可以提高应用的并发性。因为它们都能“自动地”解决在什么时间、何种系统可用资源条件下建立及维护线程的支持工作。同时,向程序员隐藏了线程这个名称,并以工作队列这样抽象的对象,使得并发程序更加方便实现。其中Dispatch Queues和Dispatch Source两种方法是基于GCD的。下面依次介绍三种方法的使用特点及技巧。
1 Dispatch Queue的使用
Dispatch Queue作为对象,接受任务,将任务以先进先出的顺序执行。并且它还有着编程简单、能够提供线程池的管理、节约内存空间的使用、不trap内核、无死锁、在顺序的队列中比直接加锁同步的执行速度快等一系列的优点。
Dispatch Queue可以并发执行任务,也能够串行执行任务。并发任务只要是在队列中的工作,都会被陆续地扔在各个Thread中去执行,它们之间相互独立,不需要等待其中一个结束了,再由队列扔出一个新的任务到Thread上去执行,而且是同时在各个Thread中各自执行。串行任务则意味着在这个队列中的各种操作,需要“一个一个”地按顺序进行执行,下一个任务需要等待上一个任务执行结束后,才会进入执行。
1.1 Dispatch Queue中队列的三种分类
Dispatch Queue中队列的队列分为顺序队列、并发队列和Main dispatch queue三种。
所谓顺序队列即是在一个queue中,每次仅1 个任务在执行。
并发队列即是在一个queue中,每次多于1个任务在执行,而这个多的数量由queue自己决定,它是根据相应的系统资源来决定的,资源多则数量多,资源少则数量少。
main dispatch queue,它是一个顺序的队列,它在main thread上执行,程序员也可以称main thread为”程序同步关键点“。
1.2 某些关键的“优点”
1)如果通过线程编程,其中2个线程上的task,都去访问共享资源。通过使用lock来进行线程的同步,额外的会造成相应的内核中断。而相应的,对于Dispatch Queue而言,可以使用顺序的queue来进行处理,从而提高效率。
2)多个Dispatch Queue的之间是并发的执行的,若是顺序的话,单个Dispatch Queue之内是顺序的。
3)Dispatch Queue会根据系统状况来选择create thread的数目,不会无限制扩张。
1.3 block的问题
1)block看上去像函数指针,其实它是一个基本的数据结构对象,由编译器建立和管理。
2)block可以访问其父作用域上的变量,如果不加__block,则是把这个变量拷贝到block自身的堆内存空间上。
3)block不要去使用父作用域上的指针变量,这些指针指向的对象的生命周期是由caller来决定的。也就是说,block不要引用一个野指针。
4)queue会copy一个block到其中,当block执行完毕,它会做release的处理。
1.4 queue需要release的问题
全局的queue,不需要retain和release。 自己create的queue,需要release。
1.5 queue的自身的context的设定
每一个queue都可以设定用户自定义的context数据,可以通过调用dispatch_set_context(queue,contextdata)设置context数据,通过dispatch_set_finalizer_f来设定怎样释放其对应queue的contextdata的函数指针。
1.6 dispatch group
dispatch group是一个lock的方法,可以lock一个或一系列task完成的条件,使得后续代码要等待某task执行完毕后,再继续执行。
1.7 线程安全
1)对于Dispatch Queue自身来说,线程是安全的。
2)不要在同一个queue中,调用dispatch_sync函数,如果这样调用,将会出现死锁的现象。例如:在a中同步调用b,结果b的block一直等待a的资源,而b不执行完毕,a是没办法继续向下执行
2 Dispatch Source的使用
Dispatch Source是GCD的一部分,是用于事件响应的队列。用于监听系统push上来的timer、signal以及各种event,一旦发生,立即把关联的block对象扔到Dispatch Queue上执行。
2.1 创建Dispatch Source
需要创建事件源和Dispatch Source本身。事件源是处理事件所需要的native数据结构,例如基于描述符的Dispatch Source,你需要打开描述符;基于进程的事件,你需要获得目标程序的进程ID。
然后可以如下创建相应的Dispatch Source:
使用dispatch_source_create函数创建Dispatch Source
配置Dispatch Source:
为Dispatch Source设置一个事件处理器
对于定时器源,使用dispatch_source_set_timer函数设置定时器信息
为Dispatch Source赋予一个取消处理器(可选)调用dispatch_resume函数开始处理事件由于Dispatch Source必须进行额外的配置才能被使用,dispatch_source_create函数返回的Dispatch Source将处于挂起状态。此时Dispatch Source会接收事件,但是不会进行处理。这时候你可以安装事件处理器,并执行额外的配置。
2.2 编写和安装一个事件处理器
需要定义一个事件处理器来处理事件,可以是函数或block对象,并使用dispatch_source_set_event_handler或dispatch_source_set_event_handler_f安装事件处理器。事件到达时,Dispatch Source会提交你的事件处理器到指定的Dispatch Queue,由queue执行事件处理器。
事件处理器的代码负责处理所有到达的事件。如果事件处理器已经在queue中并等待处理已经到达的事件,如果此时又来了一个新事件,Dispatch Source会合并这两个事件。事件处理器通常只能看到最新事件的信息,不过某些类型的Dispatch Source也能获得已经发生以及合并的事件信息。
如果事件处理器已经开始执行,一个或多个新事件到达,Dispatch Source会保留这些事件,直到前面的事件处理器完成执行。然后以新事件再次提交处理器到queue。
函数事件处理器有一个context指针指向Dispatch Source对象,没有返回值。Block事件处理器没有参数,也没有返回值。
3 Operation Queue的使用
Operation Queue的实现机制,是使用NSOperation Queue和NSOperation来完成的。
通常,Operation Queue中的执行对象是NSOperation类的子类的对象(NSOperation类是抽象的)。
相对于Dispatch Queue的FIFO而言,这里的顺序,依赖于NSOperation之间的依赖性来选择执行顺序的。因而它是按照一定顺序来执行的,并且是并发抛出的。
4 结论
4.1 使用并发、多线程几种情况
1)把任务进行分解,如果子任务之间的行为是相互独立的,那么可以确认在子任务之间可以是多线程执行的。
2)如果子任务之间相互存在依赖关系。例如:下一个子任务的输出必须通过上一个子任务的输入来获取,则最好不用并发异步。
3)独立的子任务确认后,就根据顺序还是并发的需求,塞入相应的group就好。
4)对于operation object而言,如果要设计成顺序执行的情况,就必须要设置任务之间的依赖,如果用block,就在Dispatch Queue中设置顺序即可,其他默认并发。
4.2 提高多线程编程效率的技巧:
1)尽量不要让共享资源lock住线程的并发。尽量使用线程的局部value来代替共享资源。变成可重入。
2)禁止使用lock。如果并发需要lock来同步,那么尽量使用serial queue来进行队列的方式来设计软件架构。但是注意,如果i OS的一些回调函数,或者通知函数,打回来时就是开启新线程,那么就要考虑对new Thread进行加入lock了。但是这是自己没法控制的时候,这样做的,如果代码部分是可以自己控制的,则尽量禁止使用lock机制,或者信号量。如果同时建立1k个operation对象,然后提交到operation queue中,那么会引起不断的内存换页。
摘要：如今移动设备已经进入了多核心CPU时代,并且随着时间的推移,CPU的核心数只会增加不会减少。作为软件开发者需要尽可能地提高应用的并发性,充分利用多核心CPU的性能。i OS是由苹果公司开发的移动操作系统,在i OS开发中,主要通过Dispatch Queues、Dispatch Sources和Operation Queues来提高应用的并发性。该文对针对这三种工具的使用方法及技巧进行了研究,总结出提高多线程编程的效率的方法。
关键词：iOS,并发程序,多线程
参考文献
[1]Rob Napier,Mugunth Kumar.i OS编程实战[M].美团移动,译.北京:人民邮电出版社,2014.
[2]关东升.i OS开发指南:从零基础到App Store上架[M].2版.北京:人民邮电出版社,2014.
[3]Kazuki Sakamoto,Tomohiko Furumoto.Objective-C高级编程i OS与OS X多线程和内存管理[M].黎华,译.北京:人民邮电出版社,2013.