基于CSP的PSTM框架形式化分析与验证
发布时间：2021-11-07 06:58
并行编程技术由于其运算效率高且性能好的能力,一直是学术界和工业界的热点研究对象。作为其中一种解决方案的事务内存处理技术（Transactional Memory,TM）,采用以事务代替锁的方式,解决了其他传统解决方案中的种种问题。而在当前市场上,TM的应用还局限于传统的交易系统和服务行业。原因可归纳为（1）支持TM技术的多核设备没有得到普及,且当下流行的编程语言并不支持TM;（2）并非所有类型的应用程序都适用于TM类型的编程模型;（3）对TM技术应用并行性的评估系统不够完善。因此,将TM范式推广到更多的应用领域受到了阻碍。为解决这三种问题,PSTM（Python Software Transactional Memory）框架应运而生。本文从该框架的源代码出发,采用进程代数演算中的通信顺序进程（Commu-nicating Sequential Processes,CSP）方法对 PSTM 框架进行了深层次的形式化分析与建模。对PSTM框架中的通信过程与组件进行多角度的抽象与分析,包括建立多层次的请求事务模型,循环提供服务的PSTMAPI、PSTM-Server组...
【文章来源】：华东师范大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：87 页
【学位级别】：硕士
【部分图文】：
图２＿１：?ＰＳＴＭ框架??
证了事务请求通信的正确性和完整性。??２丄４功能演示??我们以一个最简单的例子说明ＰＳＴＭ框架实现的功能＾如图２．３所乱当前系??统字典中仅有一个项，元对（Ｍ，３０）ｓ现在．．，总共有七个请求事务想要对该项??进行更新，它们的键值均为１。其中，仅有前三个请求事务的版本和字典项的版本??匹配，因此Ｔ４至Ｔ７直接被系统忽略掉６假设Ｔ２的执行速度快于Ｔ１和Ｔ３，率先成??功执行了更新操作，则该字典项被更新为（１，１，７５），此时其版本值为１。因此，Ｔ１??和Ｔ３的版本不再和该字典项匹配，不能再执行更新操作，被系统中止掉。所以，在??这次并行执行请求的过程中，仅有Ｔ２成功执行了更新操作，将字典项从（１，０，３０）??更新为（１，１，７５）。其他的事务不再满足匹配条件，一次并行请求结東。??至此
的一个字典项。每个进程都对该字典项执行相同的操作，即将当前值取出，自加一??并提交。由于起到的效果和计数器的一般功能一致，且称之为共享计数器。??如图５．１所示，这个案例由ｉＶ个相同的事务进程并行组成，每个事务进程都??执行相同的事务函数所有的事务进程共享一个共享计数器变量，也就??是说，所有的事务进程都可以通过调用ＡＰＩ公共函数对该共享变量进行操作。该??案例主要执行两个函数，除了上述提到的事务函数ｔｅｎＦｎ（ｇ），还有一个即是主函??．数?ｍａｉｎ（）。??主进程（Ｔｈｅ?Ｍａｉｎ?Ｐｒｏｃｅｓｓ）执行主函数如Ｐｙｔｈｏｎ伪代码１所示。首??先，我们定义事务进程的个数＝?６。然后，创建一个队列ｇ，用于连接请求进程??和服务器端。创建一个事务请求主进程ｐｔｍ，用于做一些准备工作，即将共享计数??器添加到系统字典中并对其进行初始化。然后，便开始调用添加函数向系统字典中??添加以ｃｏｉｍｔｅｒ为关键字的字典项，此时该字典项的版本为０。该字典项即为共享??变量
【参考文献】：
期刊论文
[1]多核多线程技术综述[J]. 眭俊华,刘慧娜,王建鑫,秦庆旺. 计算机应用. 2013(S1)
[2]任务并行编程模型研究与进展[J]. 王蕾,崔慧敏,陈莉,冯晓兵. 软件学报. 2013(01)
[3]多核处理器并行编程模型的研究与设计[J]. 曹折波,李青. 计算机工程与设计. 2010(13)
[4]软件开发中的形式化方法[J]. 郑红军,张乃孝. 计算机科学. 1997(06)
本文编号：3481388
【文章来源】：华东师范大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：87 页
【学位级别】：硕士
【部分图文】：
图２＿１：?ＰＳＴＭ框架??
证了事务请求通信的正确性和完整性。??２丄４功能演示??我们以一个最简单的例子说明ＰＳＴＭ框架实现的功能＾如图２．３所乱当前系??统字典中仅有一个项，元对（Ｍ，３０）ｓ现在．．，总共有七个请求事务想要对该项??进行更新，它们的键值均为１。其中，仅有前三个请求事务的版本和字典项的版本??匹配，因此Ｔ４至Ｔ７直接被系统忽略掉６假设Ｔ２的执行速度快于Ｔ１和Ｔ３，率先成??功执行了更新操作，则该字典项被更新为（１，１，７５），此时其版本值为１。因此，Ｔ１??和Ｔ３的版本不再和该字典项匹配，不能再执行更新操作，被系统中止掉。所以，在??这次并行执行请求的过程中，仅有Ｔ２成功执行了更新操作，将字典项从（１，０，３０）??更新为（１，１，７５）。其他的事务不再满足匹配条件，一次并行请求结東。??至此
的一个字典项。每个进程都对该字典项执行相同的操作，即将当前值取出，自加一??并提交。由于起到的效果和计数器的一般功能一致，且称之为共享计数器。??如图５．１所示，这个案例由ｉＶ个相同的事务进程并行组成，每个事务进程都??执行相同的事务函数所有的事务进程共享一个共享计数器变量，也就??是说，所有的事务进程都可以通过调用ＡＰＩ公共函数对该共享变量进行操作。该??案例主要执行两个函数，除了上述提到的事务函数ｔｅｎＦｎ（ｇ），还有一个即是主函??．数?ｍａｉｎ（）。??主进程（Ｔｈｅ?Ｍａｉｎ?Ｐｒｏｃｅｓｓ）执行主函数如Ｐｙｔｈｏｎ伪代码１所示。首??先，我们定义事务进程的个数＝?６。然后，创建一个队列ｇ，用于连接请求进程??和服务器端。创建一个事务请求主进程ｐｔｍ，用于做一些准备工作，即将共享计数??器添加到系统字典中并对其进行初始化。然后，便开始调用添加函数向系统字典中??添加以ｃｏｉｍｔｅｒ为关键字的字典项，此时该字典项的版本为０。该字典项即为共享??变量
【参考文献】：
期刊论文
[1]多核多线程技术综述[J]. 眭俊华,刘慧娜,王建鑫,秦庆旺. 计算机应用. 2013(S1)
[2]任务并行编程模型研究与进展[J]. 王蕾,崔慧敏,陈莉,冯晓兵. 软件学报. 2013(01)
[3]多核处理器并行编程模型的研究与设计[J]. 曹折波,李青. 计算机工程与设计. 2010(13)
[4]软件开发中的形式化方法[J]. 郑红军,张乃孝. 计算机科学. 1997(06)
本文编号：3481388
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3481388.html
