无界无等待通用构造的研究

来源 :天津大学 | 被引量 : 0次 | 上传用户:typxh123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在研究并发计算的过程中,可以将研究的系统分为三种模型:k-有界并发模型,有界并发模型和无界并发模型。研究表明随着并发性的增强,无等待可解的问题规模越来越小。收集,快照以及重命名等问题已经被证明在无界并发模型下是可解的,通用构造问题在无界并发模型下是否可解是一个急需回答的问题。通用构造是一种能将任意对象的顺序实现转化为可线性化的并发实现的一般性原理,无等待通用构造算法要求这种转化的过程具有无等待性。在有界并发模型下,已经有许多优秀的通用构造算法,这些算法证明了有界并发模型下通用构造算法的存在性,然而关于“无界并发模型下,通用构造算法是否存在”这一问题,已有的研究都没有给出答案。针对这一情况,本文提出了无界无等待通用构造算法,从而证明了通用构造的问题在无界并发模型下是可解的。论文在研究了所有已有的通用构造算法基础上,做出了以下工作:1)设计出了第一个无界并发模型下的通用构造算法。算法是基于帮助机制的,为了保证无界并发模型下进程间的帮助能够终止,算法中引入了新的排队方法,并且利用了无界并发模型中有限时间内系统中活跃的进程数有限的特性。2)从理论上证明了算法的正确性,本文主要证明了算法的无等待性和可线性化性。本文的工作是理论性的研究,意义在于证明了无界并发模型下通用构造的存在性,在附录部分给出了算法的一个模拟程序。另外,本文提出的算法在设计帮助机制时引入的排队技术是一种新颖的思想。
其他文献
股权众筹是一种面向社会大众投资者,基于互联网渠道的新型融资模式。近年来,国内外在政策支持下,股权众筹快速发展。本文研究目的在于分析什么样的驱动因素,促使社会大众投资
“新常态”下,我国财政收入增速下降、经济增长放缓、国债规模节节攀升。维持中央财政可持续、预防财政风险对我国的经济安全具有重要意义。财政可持续性问题的提出最早可追
背景:炎症反应在蛛网膜下腔出血(S AH)后早期脑损伤(EBI)中起重要作用。T细胞免疫球蛋白和粘蛋白分子-3(Tim-3)是适应性和先天免疫反应的关键调节因子,并已被确定在某些炎症
随着科学技术的发展和理论研究的深入,人们对于现实世界的认知愈加成熟,所考虑和研究的实际控制系统也越来越复杂。鉴于微分方程不再适用于描述具有不确定性和不连续性的实际
磁悬浮由于无接触而避免了物体之间的摩擦和磨损,设备的使用寿命大大延长,省去了复杂的润滑系统,改善了设备的运行条件,因而在交通、机械、冶金、材料等各个方面有着广阔的应
相传很久以前,望儿山下的小渔村一位学子赴京赶考,不幸途中船沉人亡。母亲不知道儿子葬身大海的消息,每天登山眺望,等待远行的儿子归来。日复一日,年复一 According to lege
本课题主要目的是开发一个冠心病医师培训系统,系统以典型的、真实的临床病例为基础,利用计算机技术模拟医师在临床实践中对疾病的诊断、治疗过程,可训练医师对冠心病病因、
三维微纳结构因其在光电子、通讯以及传感器等领域的诸多优异性能,受到了越来越多的关注。目前,三维微纳结构的加工方法包括聚焦离子束/电子束诱导的化学气相沉积、电子束/光
数值水池下的矢量场可视化是科学计算可视化领域中一个热门方向。它将海洋科研实验计算产生的矢量场数据转化为可以观察的图形、图像,使人们通过图像解释海洋流场中存在的科
当前我们所处的社会正在经历着第四次工业革命,驱动着这一全新的技术革命的基础是数据。数据已经变得和水、电、土地、空气、森林、草原、矿藏等资源一样,成为了当今社会的一