Inferring Synchronization Under Limited Observability

Free registration required

Executive Summary

This paper addresses the problem of automatically inferring synchronization for concurrent programs. Given a program and a specification, the paper infers synchronization that avoids all interleavings violating the specification, but permits as many valid interleavings as possible. The paper lets the user specify an upper bound on the cost of synchronization, which may limit the observability - what observations on program state can be made by the synchronization code. It presents an algorithm that infers, under certain conditions, the maximally permissive synchronization for a given cost. The paper implemented a prototype of the approach and applied it to infer synchronization in a number of small programs.

  • Format: PDF
  • Size: 240.8 KB