  Multi-threaded programs have traditionally fallen into one of two domains:
cooperative and competitive. These two domains have traditionally remained
mostly disjoint, with cooperative threading used for increasing throughput in
compute-intensive applications such as scientific workloads and cooperative
threading used for increasing responsiveness in interactive applications such
as GUIs and games. As multicore hardware becomes increasingly mainstream, there
is a need for bridging these two disjoint worlds, because many applications mix
interaction and computation and would benefit from both cooperative and
competitive threading.
  In this paper, we present techniques for programming and reasoning about
parallel interactive applications that can use both cooperative and competitive
threading. Our techniques enable the programmer to write rich parallel
interactive programs by creating and synchronizing with threads as needed, and
by assigning threads user-defined and partially ordered priorities. To ensure
important responsiveness properties, we present a modal type system analogous
to S4 modal logic that precludes low-priority threads from delaying
high-priority threads, thereby statically preventing a crucial set of
priority-inversion bugs. We then present a cost model that allows reasoning
about responsiveness and completion time of well-typed programs. The cost model
extends the traditional work-span model for cooperative threading to account
for competitive scheduling decisions needed to ensure responsiveness. Finally,
we show that our proposed techniques are realistic by implementing them as an
extension to the Standard ML language.
