Page 99 - 《软件学报》2021年第7期

石剑君 等:操作系统内核并发错误检测研究进展 2017

统崩溃等问题,造成巨大的经济损失.例如,从 1985 年~1987 年期间,导致多名患者丧生的 Therac-25 医疗事
[2]
[1]
故 、2003 年美国东北部地区的大停电事件 、2012 年 Facebook 公司的 IPO 故障造成的数亿美元的经济损
[3]
失等 .由于多线程并发执行的不确定性,并发错误产生的原因往往难以追踪,并发错误的检测和修复也比串行
[4]
程序错误更加困难 .
研究人员对并发错误进行了大量研究,提出了一些应对并发错误的措施,包括并发错误检测、并发错误避
免、并发错误预测和诊断等,本文仅关注并发错误检测相关的研究.目前,大部分针对并发错误检测的研究工作
主要集中在应用程序级 [515] .然而,操作系统内核作为软件栈中最底层的软件,一旦发生并发错误,将导致服务中
断、系统崩溃等更加严重的后果.由于操作系统内核中采用复杂的同步机制、各种软/硬件中断处理机制以及
错综复杂的线程调度机制,操作系统内核并发错误的研究变得更加困难.此外,操作系统内核的代码规模庞大,
尤其是开源操作系统内核,如 Linux 内核自 1991 年发布至今,由分布在全球各地的开发者共同开发和维护,且经
过了多个版本的迭代更新,如 Linux kernel v5.0 的代码量已经多达 2 600 多万行.复杂的代码结构和庞大的规模,
使得操作系统内核级并发错误检测的研究面临巨大的挑战.因此,很多用于应用程序级并发错误检测的方法,并
不能直接用于操作系统内核的并发错误检测.随着静态分析、动态分析、形式化验证等程序分析技术的发展,
研究人员提出了很多用于操作系统内核并发错误检测的方法.
本文对操作系统内核级并发错误检测相关的研究进行了广泛调研,首先在 IEEE、ACM、Web of Science、
Springer、Elsevier、DBLP、Google Scholar 和 CNKI 等论文数据库和搜索引擎中进行检索,检索采用的英文关
键字包括“kernel/os concurrency”“kernel/os deadlock”“kernel/os race”“kernel/os atomicity violation”和“kernel/os
order violation”等,然后对检索到的论文逐一进行筛选,去除掉那些与操作系统内核和并发错误检测不相关的研
究论文,并通过这些论文的相关工作部分对文献进行补充,最终得到与操作系统内核并发错误检测相关的研究
论文.图 1 展示了主要相关研究论文的分布情况,自 2003 年至今,关于操作系统内核的并发错误研究整体呈增长
趋势,尤其是 2016 年以来发表在 ASE、OSDI、SOSP、ATC、S&P 等顶级会议上的论文数目多达 12 篇.

Fig.1 Literature distribution of concurrency bug detection in OS kernels
图 1 操作系统内核并发错误检测研究相关文献分布情况
本文第 1 节介绍并发错误的基本类型、相关的并发错误检测算法和并发错误检测性能评价指标.第 2 节讨
论已存在的应用程序级并发错误检测方法无法直接用于操作系统内核的原因,以及操作系统内核中已有的并
发错误检测工具的局限性.第 3 节从形式化验证、静态分析、动态分析和静态与动态相结合 4 个方面分类阐述
近年来针对操作系统内核并发错误检测相关的研究方法,并从技术手段、检测效果和性能等方面对相关的代表
性研究工作进行系统总结和对比分析.第 4 节对操作系统内核并发错误检测研究面临的挑战进行探讨,并对该
领域未来可能的研究趋势进行展望.第 5 节总结全文.
1 并发错误简介

1.1 并发错误的基本类型

常见的并发错误包括死锁、数据竞争、原子性违例和顺序性违例等.下文以 Linux 内核中出现的并发错误