The Working Set Size Distribution for the Markov Chain Model of Program Behavior

The history of modelling of the address sequences generated by computer programs (often termed "program behavior") follows a familiar pattern: the better a hypothetical model fits experimental evidence, the less amenable it is for calculation. In this paper programs that generate successiv...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1982-08, Vol.11 (3), p.453-466
Main Authors: Hofri, M., Tzelnic, P.
Format: Article
Language:English
Subjects:
Markov analysis
Optimization techniques
Random variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The history of modelling of the address sequences generated by computer programs (often termed "program behavior") follows a familiar pattern: the better a hypothetical model fits experimental evidence, the less amenable it is for calculation. In this paper programs that generate successive page references that can be described by a first order Markov chain are considered. We produce a closed form expression for the distribution and usable expressions for the first moments of the steady state size of their working set of pages. These expressions are also specialized for the independent reference model and the Easton model. Only standard Markov chain theory is used.
ISSN:0097-5397
1095-7111
DOI:10.1137/0211036