Queueing analysis of a canonical model of real-time multiprocessors

Multiprocessors are beginning to be regarded increasingly favorably as candidates for controllers in critical real-time control applications such as aircraft. Their considerable tolerance of component failures together with their great potential for high throughput are contributory factors. In this paper, we present first a logical classification of multiprocessor structures with control applications in mind. We point out that one important subclass has hitherto been neglected by the analysts. This is a class of systems with a common memory, minimal interprocessor communication and perfect processor symmetry. The performance characteristic of the greatest importance in real-time applications is the response time distribution. Indeed, we have shown in a separate paper [2] how it is possible to characterize rigorously and objectively the performance of a real-time multiprocessor given the application and the multiprocessor response time distribution and component failure characteristics. We therefore present here a computation of the response time distribution for a canonical model of real-time multiprocessor. To do so, we approximate the multiprocessor by a blocking model and present a means for efficient analysis. Two separate models are derived: one created from the system's point of view, and the other from the point of view of an incoming task. The former model is analyzed along largely conventional lines. For the latter model, an artificial server is used, and the system is transformed into a queueing network.