实时操作系统中有限优先级反转的验证

摘要

实时操作系统常常运用优先级调度方案来进行抢占式调度.如果在这些操作系统中使用基于阻塞的同步原语则很容易产生无限优先级反转问题.历史上已经引入了多种不同的协议来避免产生这个问题.然而,这些协议往往非常复杂并且容易滋生错误.本文给出了一套系统的方案来定义这些协议并验证其能够保证有限优先级反转.本文首先给出有限优先级反转的形式化定义.然后介绍了验证框架,它可以用于验证不同的协议保证该性质.该框架可以支持协议抽象层面与具体实现层面的验证.本文已经成功的将该框架应用于验证POSIX标准中提供的优先级继承协议与优先级保护协议.并且,本文的所有工作都已在证明助手Coq中完成.