Browse Prior Art Database

On The Shadow CPU Approximation For Modellinq~Priority Scheduling In Computer Systems

IP.com Disclosure Number: IPCOM000128167D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Paul G. Spirakis: AUTHOR [+3]

Abstract

A sound performance evaluation methodology is essential to the design and use of computer systems. Among performance evaluation methods, queuing network models have been widely recognized as cost and time effective tools, capable. of predicting ability and necessary complements of simulations. Algorithms for efficiently estimating the throughput, response time and other measures of performance have been devised for a broad range of queuing network models. Althoug h this range is very rich and adequate for modelling many realistic features of a corrputer system, nevertheless it has major limitations. An important one is the inability to model pre-emptive priority scheduling disciplines. Although exact closed-form solutions for such network models are open reseach problems, several approximation techniques have been proposed. An important one was Sevcik's [Sevc, 77) "shadow CPU" technique, which admits a product form solution and gives performance bounds which are quite tight in may circumstances. In this paper, we extend the shadow CPU model to an optimal approximation of the priority model, within the restrictions of the product form. We propose a computationally efficient sub-optimal approximation technique which gives tighter performance bounds compared to the original shadow CPU technique. We also investigate the limitations of such shadow server-product form techniques for modelling priorities.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On The Shadow CPU Approximation For Modellinq~Priority Scheduling In Computer Systems

by

Paul G. Spirakis

January 1983

Tech, Cal-ReporiP.R. 55

This work was supported in part by the NSF Grant NSF-MC579-21024 and the ONR Contract N00014-80-C-0674.

ABSTRACT

A sound performance evaluation methodology is essential to the design and use of computer systems. Among performance evaluation methods, queuing network models have been widely recognized as cost and time effective tools, capable. of predicting ability and necessary complements of simulations. Algorithms for efficiently estimating the throughput, response time and other measures of performance have been devised for a broad range of queuing network models. Althoug h this range is very rich and adequate for modelling many realistic features of a corrputer system, nevertheless it has major limitations. An important one is the inability to model pre-emptive priority scheduling disciplines. Although exact closed-form solutions for such network models are open reseach problems, several approximation techniques have been proposed. An important one was Sevcik's [Sevc, 77) "shadow CPU" technique, which admits a product form solution and gives performance bounds which are quite tight in may circumstances. In this paper, we extend the shadow CPU model to an optimal approximation of the priority model, within the restrictions of the product form. We propose a computationally efficient sub-optimal approximation technique which gives tighter performance bounds compared to the original shadow CPU technique. We also investigate the limitations of such shadow server-product form techniques for modelling priorities. -3-

1. Introduction

With the advancement of technology, computer systems have become exceedingly complex and performance evaluation can no longer be done on an informal basis. In addition, detailed simulation of complex systems is very expensive. Fortunately, analytic models based on queuing networks have been shown in several cases to provide predictive ability comparable to that of extensive simulations, yet more efficient and cost-effective ([Giam, 761, [Rose, 761). In addition, a lot of approximation techniques have been devised to model situations for which closed-form computationally efficient solutions are not known. (See, for example, (Koba, 741, (Gele, 75], [Re, Ko, 741, (Sa,Ch, 751, [Sh,Bu, 771, [Reis, 811, etc.)

In the past few years, the early work on analysis of queuing

networks (see (Jack, 631, (Go,Ne, 671, [Klei, 751, (Klei, 761,

Northwestern University Page 1 Dec 31, 1983

Page 2 of 10

On The Shadow CPU Approximation For Modellinq~Priority Scheduling In Computer Systems

[Ba,Mu, 731) has beea substantially extended. Buzen ([Buze, 73]) presented a very efficient computational method for deriving performance measures from closed queuing networks with exponential servers and a single customer class ("product fo...