Abstract
We propose a concurrency reasoning framework for imperative programs,
based on the Owicki-Gries (OG) foundational shared-variable
concurrency method. Our framework combines the approaches of
Hoare-Parallel, a formalisation of OG in Isabelle/HOL for a simple
while-language, and Simpl, a generic imperative language embedded in
Isabelle/HOL, allowing formal reasoning on C programs. We define the
Complx language, extending the syntax and semantics of Simpl with
support for parallel composition and synchronisation. We additionally
define an OG logic, which we prove sound w.r.t. the semantics, and a
verification condition generator, both supporting involved low-level
imperative constructs such as function calls and abrupt termination.
We illustrate our framework on an example that features exceptions,
guards and function calls. We aim to then target concurrent operating
systems, such as the interruptible eChronos embedded operating system
for which we already have a model-level OG proof using Hoare-Parallel.
License
History
- January 13, 2017
- Improve VCG for nested parallels and sequential sections (revision 30739dbc3dcb)
Topics
- Computer science/Programming languages/Logics
- Computer science/Programming languages/Language definitions
Session Complx
- Language
- SmallStep
- OG_Annotations
- OG_Hoare
- SeqCatch_decomp
- OG_Soundness
- Cache_Tactics
- OG_Tactics
- OG_Syntax
- Examples
- SumArr