A Cooperative Approach to Two-Phase Waiting

Competitive analysis is traditionally used to bound the worst-case performance of two-phase waiting, a common algorithm in multiprocessor environments. Despite the popularity of competitive algorithms, we observe that their assumptions are not valid in closed systems in which processes can influence their future waiting times. By evaluating implicit coscheduling on time-shared, communicating processes in a distributed system, we show that spin-time should instead be calculated with cooperative methods. Rather than reacting to a fixed stream of adversarial waiting times, our cooperative algorithm minimizes future waiting times by keeping processes that belong to the same parallel job coordinated across machines.

Another common assumption in two-phase waiting is that the penalty of blocking is a fixed amount, equal to the cost of a context-switch performed by the operating system scheduler. However, in implicit coscheduling, the penalty of blocking is dynamic, related to the number of arriving messages. To handle this complication, we leverage conditional two-phase waiting, a generalization in which spin-time may be altered, depending upon events that occur while the process is waiting. Through simulations, we show that our algorithm performs within 35% of ideal on a range of workloads, and significantly better than two-phase waiting with a fixed spin-time.