Performance bounds for concurrent software with rendezvous

Synchronous message-passing communication, or rendezvous, occurring between software tasks can have a significant effect on system performance. The rendezvous style of communication is coming into wider use in programming languages and operating systems for parallel and distributed environments. Understanding the performance implications of this style of inter-task communication is becoming a matter of practical importance. The dual nature of a task which acts both like a customer as well as a server, makes the performance analysis of rendezvous-based multitasking systems quite different from the analysis of the other queueing systems with known results. This research focuses on rendezvous-based systems in which the execution behavior of the software has a nondeterministic component of a very general nature which may for example be the manifestation of a data dependent behavior. Based on a model called the Stochastic Rendezvous Network the computation of bounds on task throughputs for multitasking systems characterized by rendezvous style communication is presented. Although the behavior of tasks is called stochastic, it is very general and the results are valid for general distributions of computation times and the number of messages generated by tasks. The inter-relationship among task throughputs, however, makes it difficult to extract the bounds in closed analytic form. The notion of a feasible throughput region which encloses the set of feasible tasks throughputs and captures the inter-relationship among the behavior of tasks is introduced. Variations of this basic bounding approach that are useful in the context of different types of multitasking systems are considered in the article. For example, a novel technique based on interval arithmetic is proposed for the computation of numerical values for the bounds. The applicability of the bounds and their tightness are analyzed through case studies. Issues such as the inter-relationship between the software architecture and system performance, and the effect of processor contention on the performance bounds are discussed.