The Analysis of Computer Systems Using Markov Reward Processes
Matthew R. Smith, S K Trivedi, F V Nicola · 1987
Numerous applications in the area of computer system analysis can be effectively studied with Markov reward models. These models describe the behavior of the system with a continuous-time Markov chain, where a reward rate is associated with each state. A common interpretation of the reward rates in a computer system context is computational capacity, or a related performance measure. The distribution of accumulated reward or time-averaged over a finite time interval may be determined from the solution of the appropriate Markov reward model. We illustrate the diversity of areas where Markov reward models may be used with four examples chosen from quite different application domains. The four examples are the combined evaluation of performance and reliability of multiprocessor systems, the analysis of task completion time in a failure-prone environment, the response time distribution in a queueing system with a processor sharing discipline, and the distribution of time-averaged queue length for an M/M/1 queue. We present a polynomial time numerical algorithm used to compute the distribution of accumulated reward for the examples we set forth.