Paul G. Spirakis

Excerpt from On the Shadow Cpu Approximation for Modelling Priority Scheduling in Computer Systems 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. Although this range is very rich and adequate for modelling many realistic features of a computer 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 research 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 many 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. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.

On the Shadow Cpu Approximation for Modelling Priority Scheduling in Computer Systems (Classic Reprint)

Fernando Orejas

Jan van Leeuwen

This book constitutes the refereed proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP 2001, held in Crete, Greece in July 2001. four invited papers were carefully reviewed and selected from a total of 208 submissions. complexity, algorithm analysis, approximation and optimization, complexity, concurrency, efficient data structures, graph algorithms, language theory, codes and automata, model checking and protocol analysis, networks and routing, reasoning and verification, scheduling, secure computation, specification and deduction, and structural complexity.

28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings

Automata, Languages and Programming

Maria Serna

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings

Algorithms and Complexity

Excerpt from On the Shadow Cpu Approximation for Modelling Priority Scheduling in Computer Systems We shall use a model proposed by [sevc, 77] that contains very little of the complexity of an actual system but still reflects the intrinsic difficulty of analytically approaching priority scheduling. ﬂue queuing network is a closed cyclic uetggtg_of two servers: a cpu and an i/o server. There are just two cystomer classes, with class 1 having pre-emptive priority over class -the cpu, while all scheduling is fcfs at the i/o. That L(jiept-rlazl processor will be devoted to class 1 whenever a class 1_job; is, availahle for service. Within each class jobs are served irpyfcejsiggdetﬂ'og-ixhe average service times at the i/o are the same (x3) ffxyboghggiasse§ hut the average cpu service times (bemeen i/o -t-=for the two classes (xi for class i, i Jobs always teturn to the cpu after being served at the i/o. We assume, for simplicity, that the service time distribution of the i/o is exponential (of rate u3 X51) and the cpu service for class 1 is exponential (rate 1 Xfl). For class 2 the same holds, when the cpu service time distribution is conditional to the event of absence of class 1 jobs from the cpu. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.

Paul G. Spirakis

About

Books

Join the club