Short paper: PRP: Priority Rollback Protocol - A PIP extension for mixed criticality systems

Priority inheritance protocol (PIP) is an important protocol to prevent unbounded priority inversion of threads which contend on shared resources. Recently, there has been a renewed interest in reducing the latency and increasing predictability for high priority threads that acquire contended resources from low priority threads. In this paper we present an extension to PIP called Priority Rollback Protocol, which allows high priority threads to rollback low priority threads, thereby freeing contended resources. PRP leverages recent advances in software transactional memory (STM) to facilitate efficient and predictable reversion of low priority threads. We present two versions of the PRP algorithm and compare and contrast their tradeoffs. PRP is geared toward mixed criticality systems, specifically for providing tight and predictable bounds for direct communication between processes. Since PRP is an extension of PIP, systems can seamlessly leverage both PIP and PRP locks.