关于线程上下文切换的验证研究
Certification of Thread Context Switching
-
摘要: 线程上下文切换是操作系统内核中实现多线程机制的核心代码。传统的程序验证理论与方法只关注用户级的多线程应用程序,并依赖线程切换机制的正确实现。表面上,线程上下文切换代码相对较少,其实现代码的正确性较易通过测试等手段来完成。但是当线程上下文切换代码与其它的操作系统内核代码(如线程调度器)结合在一起时,测试将难以保证线程上下文总被正确地切换,或总被切换到正确的线程。形式化程序验证方法的优势在于不仅可以保证线程切换代码的正确性,也能够保证线程总被正确地切换。
在近年来的一些系统软件的验证研究中,对于线程上下文切换程序验证的方法大致可以分为两类:第一类验证方法是采用单一的逻辑来同时验证线程上下文切换实现代码与内核线程代码,但该逻辑系统需要支持高阶代码指针推理,支持非直谓多态(Impredicative polymorphism)与递归谓词,从而导致代码规范异常复杂,难以理解且难以验证;第二类方法采用两个不同的逻辑来分别验证线程切换的实现代码与调用线程切换的代码,通过在两个不同的抽象层上验证来避免引入高阶代码指针推理与复杂的逻辑证明。但是这种隔离性导致了第二类方法只能验证某类具有特殊形式的线程上下文切换实现代码,而不能验证实际操作系统内核中的线程上下文切换代码。
本文分析了线程上下文切换的语义与验证难点所在。设计了一个轻量级的验证框架用以同时验证线程上下文切换以及内核线程。该验证框架虽然只有一套逻辑规则,但通过两个不同的线程切换规范为线程切换实现代码与内核线程代码构造了不同的抽象层次。该验证框架通过状态抽象的基本思想避免了两部分代码的过度隔离,从而能够验证实际操作系统内核中常见的线程上下文切换代码。
该验证框架的基本思想是将机器按照线程进行划分空间,然后通过状态抽象为各个空间之间建立联系。因为线程上下文切换操作涉及到两个线程的内存,因此必须从全局的视角来规范和验证。线程上下文切换的全局规范为:将当前的机器上下文保存到当前线程的控制块中,然后加载另一个线程控制块中的机器上下文。另外,每一个线程来执行上下文切换时,从线程的视角来看,线程切换并不影响线程本身的私有空间,只是共享内存发生了改变。这样就可以为其定义线程视角的局部规范:当前机器的上下文不发生变化,共享内存的变化满足某个不变式。在验证框架中,可以证明出:线程的全局规范蕴含其局部规范。然后通过逻辑推理规则,可以证明验证框架的可靠性。从而说明本文方法的正确性。
本文的验证框架已在证明辅助工具Coq中实现,并且验证了一个简单的例子来说明验证过程的直观性。并且本文与Zhao-Zhong Ni 等人采用的第一类方法进行验证切换的Coq代码进行了比较。从比较结果可以反映出:本文提出的验证框架在验证代码方面代价比较小,并具有良好的扩展性。但是本文的验证框架还未支持线程上下文的创建操作,这个是未来工作的方向。目前,在验证框架中有相当一部分的验证工作可以由工具来自动完成,从而提高程序验证的实用性,因此开发自动验证工具也是较具有吸引力的工作方向。
本文提出的轻量级验证框架没有复杂的逻辑规则,代码规范更能直观反映代码的语义,因此可以在此验证框架上加以扩充,使之支持验证更加实际的内核代码,例如线程创建、线程终止与线程同步等。本文提出的验证方法为系统软件验证研究提供了一个思路,利用空间划分与状态抽象的方法为代码定义不同的规范,从而使得整个验证过程具有良好的模块性。Abstract: With recent efforts to build foundational certified software systems, two different approaches have been proposed to certify thread context switching. One is to certify both threads and context switching in a single logic system, and the other certifies threads and context switching at different abstraction levels. The former requires heavyweight extensions in the logic system to support first-class code pointers and recursive specifications. Moreover, the specification for context switching is very complex. The latter supports simpler and more natural specifications, but it requires the contexts of threads to be abstracted away completely when threads are certified. As a result, the conventional implementation of context switching used in most systems needs to be revised to make the abstraction work. In this paper, we extend the second approach to certify the conventional implementation, where the clear abstraction for threads is unavailable since both threads and context switching hold pointers of thread contexts. To solve this problem, we allow the program specifications for threads to refer to pointers of thread contexts. Thread contexts are treated as opaque structures, whose contents are unspecified and should never be accessed by the code of threads. Therefore, the advantage of avoiding the direct support of first-class code pointers is still preserved in our method. Besides, our new approach is also more lightweight. Instead of using two different logics to certify threads and context switching, we employ only one program logic with two different specifications for the context switching. One is used to certify the implementation itself, and the more abstract one is used as an interface between threads and context switching at a higher abstraction level. The consistency between the two specifications are enforced by the global program invariant.