软件学报

作者：王超，吕毅，吴鹏，贾巧雯

单位：王超，西南大学 计算机与信息科学学院 软件研究与创新中心, 重庆 40071511,吕毅，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004902,吴鹏，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004903,贾巧雯，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;中国科学院大学, 北京 10004904

关键词：并发数据结构;可线性化;TSO内存模型;可判定性;易失通道机器

基金：国家自然科学基金(62002298,62072443);中央高校基本科研业务费专项资金(SWU019036);中国科学院对外合作重点项目(GJHZ1844)

TSO-to-TSO可线性化、TSO-to-SC可线性化和TSO可线性化是Total Store Order (TSO)内存模型下可线性化的3个变种.提出了k-限界TSO-to-TSO可线性化和k-限界TSO可线性化,考察了k-限界TSO-to-TSO可线性化、k-限界TSO-to-SC可线性化和k-限界TSO可线性化的验证问题.它们分别是这3种可线性化的限界版本,都使用k-扩展历史,这样的扩展历史对应的执行有着限界数目(不超过k个)的函数调用、函数返回、调用刷出和返回刷出动作.k-扩展历史对应执行中的写动作数目是不限界的,进而执行中使用的存储缓冲区的大小也是不限界的,对应的操作语义是无穷状态迁移系统,所以3个限界版本可线性化的验证问题是不平凡的.将定义在并发数据结构与顺序规约之间的k-限界TSO-to-TSO可线性化、k-限界TSO-to-SC可线性化和k-限界TSO可线性化的验证问题归约到k-扩展历史集合之间的TSO-to-TSO可线性化问题,从而以统一的方式验证了TSO内存模型下可线性化的3个限界版本.验证方法的关键步骤是判定一个并发数据结构是否有一个特定的k-扩展历史.证明了这个问题是可判定的,证明方法是将这一问题归约为已知可判定的易失通道机器的控制状态可达问题.本质上,这一归约将每一个函数调用或函数返回动作转化为写、刷出或cas(compare-and-swap)动作.在TSO-to-TSO可线性化的定义中,一个函数调用或函数返回动作会同时影响存储缓冲区和控制状态.为了模拟函数调用或函数返回动作对存储缓冲区的影响,在每个函数调用或函数返回动作之后立刻执行一个特定的写动作.这个写动作及其对应的刷出动作模拟了函数调用或函数返回动作对存储缓冲区的影响.引入观察者进程,为每个函数调用或函数返回动作“绑定”一个观察者进程的cas动作,以这种方式模拟了函数调用或函数返回动作对控制状态的影响.因此证明了TSO内存模型下可线性化的这3个限界版本都是可判定的,进而证明了在TSO内存模型下判定可线性化的这3个限界版本的复杂度都在递归函数的Fast-Growing层级Fωω中.通过证明已知对应复杂度的单通道简单通道机器的可达问题和TSO内存模型下可线性化的3个限界版本可以互相归约得到这个结论.

来源：2022年第8期

《软件学报》期刊编辑部

查看软件学报杂志2022年第8期