Browse Prior Art Database

COMPUTING SYSTEM SIMULATION USING MARKOV PROCESSES

IP.com Disclosure Number: IPCOM000128451D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

Maletz, Mark C.: AUTHOR [+3]

Abstract

Models of computing systems involving fixed system resources and probabilistically specified user state transition behavior must account for interactions between the system users and the system states that result from resource limitations. This is normally accomplished by the introduction of queues for the system states. Because of the probabilistic definition of user behavior, queue transition probabilities must usually be determined by a simulation of the computing system. This paper develops a new technique for simulating computing systems where the hardware configuration is specified by a processor/state service matrix and is fixed throughout the simulation, and user state transition behavior is specified using a basic state transition probabilities matrix satisfying the requirements for a Markov process.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COMPUTING SYSTEM SIMULATION USING MARKOV PROCESSES

Mark C. Maletz

CRL-TR-12-83

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1

APRIL 1983

Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

ABSTRACT

Models of computing systems involving fixed system resources and probabilistically specified user state transition behavior must account for interactions between the system users and the system states that result from resource limitations. This is normally accomplished by the introduction of queues for the system states. Because of the probabilistic definition of user behavior, queue transition probabilities must usually be determined by a simulation of the computing system. This paper develops a new technique for simulating computing systems where the hardware configuration is specified by a processor/state service matrix and is fixed throughout the simulation, and user state transition behavior is specified using a basic state transition probabilities matrix satisfying the requirements for a Markov process.

INTRODUCTION

Computing system models employing a Markov methodology partition the computing system resources into a set of states which may be occupied by user tasks. No user task may occupy more than one state at any given time, and every user task must occupy some state at all times
(i.e., the states form a true partition). User task state transition behavior is specified using a Markov basic state transition probabilities matrix (STPM). This matrix specifies the probabilities that a user task will move from its current state to every other state in the system. Implicit in the use of Markov processes is the assumption that a state will be available when a user task attempts to move to that state. This assumption is not generally satisfied by state sets that correspond to processing activity undertaken by a user task. The problem is that user tasks are not always involved in processing, but rather, must occasionally await processing on queues for system states. These queues may be added to the state set and be used to produce an extended STPM which includes the newly created queue states.

Construction of an extended STPM requires the derivation of queue entry transition probabilities (the probabilities of moving from the original states to the queue states) and the queue maintenance transition probabilities (the probabilities of remaining in and of leaving a queue at

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

University of Michigan Computing Research Laboratory Page 1 Apr 01, 1983

Page 2 of 9

COMPUTING SYSTEM SIMULATION USING MARKOV PROCESSES

the end of the current time step). These queue-related transition probabilities may be calculated from performance statistics for existing systems...