  A monitor is a widely-used concurrent programming abstraction that
encapsulates all shared state between threads. Monitors can be classified as
being either implicit or explicit depending on the primitives they provide.
Implicit monitors are much easier to program but typically not as efficient. To
address this gap, there has been recent research on automatically synthesizing
explicit-signal monitors from an implicit specification, but prior work does
not exploit all paralellization opportunities due to the use of a single lock
for the entire monitor. This paper presents a new technique for synthesizing
fine-grained explicit-synchronization protocols from implicit monitors. Our
method is based on two key innovations: First, we present a new static analysis
for inferring safe interleavings that allow violating mutual exclusion of
monitor operations without changing its semantics. Second, we use the results
of this static analysis to generate a MaxSAT instance whose models correspond
to correct-by-construction synchronization protocols. We have implemented our
approach in a tool called Cortado and evaluate it on monitors that contain
parallelization opportunities. Our evaluation shows that Cortado can synthesize
synchronization policies that are competitive with, or even better than,
expert-written ones on these benchmarks.
