UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The application of optimal stochastic control theory to adaptive performance control of computer systems Lo, Nyuk Leong 1980

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1980_A6_7 L06.pdf [ 3.82MB ]
Metadata
JSON: 831-1.0051803.json
JSON-LD: 831-1.0051803-ld.json
RDF/XML (Pretty): 831-1.0051803-rdf.xml
RDF/JSON: 831-1.0051803-rdf.json
Turtle: 831-1.0051803-turtle.txt
N-Triples: 831-1.0051803-rdf-ntriples.txt
Original Record: 831-1.0051803-source.json
Full Text
831-1.0051803-fulltext.txt
Citation
831-1.0051803.ris

Full Text

THE APPLICATION OF OPTIMAL STOCHASTIC CONTROL THEORY TO ADAPTIVE PERFORMANCE CONTROL OF COMPUTER SYSTEMS © * LO, NYUK LEONG B.Sc.,Nanyang U n i v e r s i t y , 1 9 7 5 Diploma o f Computing S c i e n c e , U n i v e r s i t y o f Glasgow, 1977 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES ( Department o f Computer S c i e n c e ) We accept t h i s t h e s i s as conforming to the r e q u i r e d s t a n d a r d . THE UNIVERSITY OF June , (c) Lo, Nyuk BRITISH COLUMBIA 1980 Leong, 1980 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of t h e r e q u i r e m e n t s f o r a n a d v a n c e d d e g r e e a t t h e U n i v e r s i t y of B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e for r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n for e x t e n s i v e c o p y i n g of t h i s t h e s i s for s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head of my D e p a r t m e n t or by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 w e s b r o o k P l a c e V a n c o u v e r , C a n a d a V6T 1W5 D E - 6 B P 75-51 1 E i i ABSTRACT T h i s t h e s i s a p p l i e s o p t i m a l s t o c h a s t i c c o n t r o l t h e o r y , a well-known e n g i n e e r i n g t e c h n i q u e , to a d a p t i v e performance c o n t r o l o f computer systems. The major advantages o f u s i n g the t h e o r y to a d a p t i v e performance c o n t r o l o f computer systems a r e : a) the p o l i c y so o b t a i n e d can be shown m a t h e m a t i c a l l y to g i v e o p t i m a l performance, b) the p o l i c y i s dynamic i n the sense t h a t c o n t r o l d e c i s i o n s are made based on the c u r r e n t system s t a t e thus o p t i m i z i n g performance a t a l l t i m e , c) once a s t o c h a s t i c model of a system has been developed i t can be used to d e t e r m i n e o p t i m a l p o l i c i e s p e r t a i n i n g to d i f f e r e n t c r i t e r i a s i m p l y by u s i n g d i f f e r e n t o b j e c t i v e f u n c t i o n s i n the model. The a p p l i c a t i o n i s e x e m p l i f i e d by u s i n g the t h e o r y t o compute the o p t i m a l a d m i s s i o n p o l i c y f o r a combined b a t c h - i n t e r a c t i v e system w i t h p a g i n g . A m a t h e m a t i c a l model of the system was developed and the t h e o r y a p p l i e d to compute the o p t i m a l a d m i s s i o n p o l i c y . The p o l i c y d e t e r m i n e s the number o f b a t c h and i n t e r a c t i v e j o b s t h a t s h o u l d be a c t i v a t e d at each system s t a t e . The s o l u t i o n i s shown to e x h i b i t the f o l l o w i n g p r o p e r t i e s : i ) I t maximizes the t o t a l system t h r o u g h p u t . i i ) I t g i v e s good mean response time to i n t e r a c t i v e j o b s . i i i ) I t g u a r a n t e e s a minimium l e v e l o f b a t c h t h r o u g h p u t . The improvement i n t o t a l system throughput compared to the case when j o b s a re a u t o m a t i c a l l y a d m i t t e d on a r r i v a l i s s u b s t a n t i a l . The improvement i s most d r a m a t i c when the workload i s heavy. i v TABLE OF CONTENTS A b s t r a c t i i Tab l e o f c o n t e n t s i v L i s t of t a b l e s v L i s t of f i g u r e s v i Acknowledgements v i i CHAPTER I . INTRODUCTION 1 1.1 The Need f o r A d a p t i v e Performance O p t i m i z a t i o n . 1 1.2 Survey o f Performance C o n t r o l A l g o r i t h m s . 2 1.3 M o t i v a t i o n and Goal 8 CHAPTER I I . OPTIMAL STOCHASTIC CONTROL 9 2.1 The B a s i c Problem 9 2.2 C o n d i t i o n s f o r the E x i s t e n c e o f S t a t i o n a r y Optimal P o l i c y 12 2.2.1 F i n i t e Mean Passage Time C o n d i t i o n 12 2.2.2 Weak A c c e s s i b i l i t y C o n d i t i o n 13 2.3 P o l i c y Improvement A l g o r i t h m 15 CHAPTER I I I . MODEL DESCRIPTION 17 3.1 Model D e s c r i p t i o n 18 3.2 The Memory Loop as a C l o s e d C e n t r a l - s e r v e r Network. 21 3.2.1 Computation o f G (n) 25 3.3 F o r m u l a t i o n o f the Optimal C o n t r o l Problem .... 31 CHAPTER IV. INTERPRETING THE RESULTS 35 4.1 The e f f e c t s o f the Weight w on Performance .... 36 4.2 The Optimal A d m i s s i o n P o l i c y 39 CHAPTER V. CONCLUSIONS 42 REFERENCES 78 V LIST OF TABLES Table (4.1) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 65 Table (4.2) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 66 Table (4.3) Optimal a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 66 Table (4.4) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 67 Table (4.5) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 67 Table (4.6) Optimal a d m i s s i o n p o l i c y w i t h cpuT=0.3, cpuB=0.3 68 Table (4.7) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.5, cpuB=0.2 68 Table (4.8) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.5, cpuB=0.3 69 Table (4.9) Opt i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.5, cpuB=0.4 69 Table (4.10) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.5, cpuB=0.5 70 Table (4.11) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.5, cpuB=0.6 70 Table (4.12) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.2, cpuB=0.2 71 Table,(4.13) O p t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.2, cpuB=0.5 71 Table (4.14) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.4, cpuB=0.3 72 Table (4.15) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.6, cpuB=0.2 72 Table (4.16) O p t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.6, cpuB=0.6 73 Table (4.17) Op t i m a l a d m i s s i o n p o l i c y w i t h cpuT=0.6, cpuB=l.1 73 Table (4.18) CPU u t i l i z a t i o n s 74 Table (4.19) C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o the o p t i m a l p o l i c i e s under d i f f e r e n t w orkload c o n d i t i o n s 75 Table (4.20) C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o the o p t i m a l p o l i c i e s under d i f f e r e n t w orkload c o n d i t i o n s : 76 Table (4.21) C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y to the o p t i m a l p o l i c i e s under d i f f e r e n t w o r k load c o n d i t i o n s 76 Table (4.22) C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o the o p t i m a l p o l i c i e s under d i f f e r e n t w o r k load c o n d i t i o n s 77 Table (4.23) C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y to the o p t i m a l p o l i c i e s under d i f f e r e n t w orkload c o n d i t i o n s 77 v i LIST OF FIGURES F i g u r e 3.1 The System Model 20 F i g u r e 3.2 The L i f e t i m e F u n c t i o n 22 F i g u r e 3.3 the Memory Loop Subnetwork 23 F i g u r e 3.4 31 F i g u r e 4.0 Legend f o r F i g u r e s 4.1(a) to 4.9(a) and F i g u r e s 4.1(b) to4.9(b) 45 F i g . 4.1(a) Mean response times vs w cpuT=0.3, cpuB=0.3 46 F i g . 4.1(b) T h r o u g h t p u t s vs w cpuT=0.3, cpuB=0.3 47 F i g . 4.2(a) Mean response times vs w cpuT=0.3, cpuB=0.5 48 F i g . 4.2(b) T h r o u g h t p u t s vs w cpuT=0.3, cpuB=0.5 49 F i g . 4.3(a) Mean response times vs w cpuT=0.3, cpuB=0.7 50 F i g . 4.3(b) Thro u g h t p u t s vs w cpuT=0.3, cpuB=0.7 51 F i g . 4.4(a) Mean response times vs w cpuT=0.5, cpuB=0.3 52 F i g . 4.4(b) T h r o u g h t p u t s vs w cpuT=0.5, cpuB=0.3 53 F i g . 4.5(a) Mean response times vs w cpuT=0.5, cpuB=0.5 54 F i g . 4.5(b) T h r o u g h t p u t s vs w cpuT=0.5, cpuB=0.5 55 F i g . 4.6(a) Mean response times vs w cpuT=0.5, cpuB=0.7 . 56 F i g . 4.6(b) T h r o u g h t p u t s vs w cpuT=0.5, cpuB=0.7 57 F i g . 4.7(a) Mean response times vs w cpuT=0.7, cpuB=0.3 58 F i g . 4.7(b) Thro u g h t p u t s vs w cpuT=0.7, cpuB=0.3 59 F i g . 4.8(a) Mean response times vs w cpuT=0.7, cpuB=0.5 60 F i g . 4.8(b) T h r o u g h t p u t s vs w cpuT=0.7, cpuB=0.5 61 F i g . 4.9(a) Mean response times vs w cpuT=0.7, cpuB=0.7 62 F i g . 4.9(b) T h r o u g h t p u t s vs w cpuT=0.7, cpuB=0.7 63 F i g . 4.10 Mean i n t e r a c t i v e response times vs no. o f t e r m i n a l s 64 v i i ACKNOWLEDGEMENTS I s i n c e r e l y thank my s u p e r v i s o r Dr. s. Chanson f o r b i s s u p e r v i s i o n and c a r e f u l r e a d i n g of t h i s t h e s i s . The f i n a n c i a l s u p p o r t from the Dept. o f Computer S c i e n c e i s v e r y much a p p r e c i a t e d . Thanks a l s o go to F l o r a Chee f o r her t y p i n g of t h i s t h e s i s . 1 CHAPTER I . INTRODUCTION 1.1 The Need f o r A d a p t i v e Performance O p t i m i z a t i o n . The performance o f a computer system w i t h a s p e c i f i c s e t o f hardware c h a r a c t e r i s t i c s and c o n f i g u r a t i o n depends m a i n l y on the r e s o u r c e management p o l i c i e s o f the o p e r a t i n g system , the workload r u n n i n g on the system, and the i n t e r a c t i o n s between the two. For a g i v e n workload r u n n i n g on a computer system t h e r e e x i s t s a s e t o f r e s o u r c e management p o l i c i e s (or v a l u e s o f system v a r i a b l e s ) which w i l l o p t i m i z e some performance index (or i n d i c e s ) of the system. O f t e n , however, p o l i c i e s t h a t work b e s t under c e r t a i n workload cannot cope s u c c e s s f u l l y w i t h o t h e r d i f f e r e n t workload c o n d i t i o n s . S i n c e the workload v a r i e s w i t h t i m e , i t appears t h a t a p o l i c y c a p a b l e o f m o d i f y i n g i t s .ehaviour i n response to workload changes can o f f e r the best average performance. In a paging environment, i f the j o b c h a r a c t e r i s t i c s do not change, i t can be shown t h a t t h e r e i s an o p t i m a l degree o f multiprogramming which maximizes the system throughput and m i n i m i z e s the mean response time [1,2,13,14,28]. I f the degree o f multiprogramming i s much h i g h e r than t h i s , a phenomenon known as " t h r a s h i n g " o f t e n o c c u r s due to the e x c e s s i v e paging a c t i v i t i e s g e n e r a t e d by i n s u f f i c i e n t memory a l l o c a t i o n f o r each j o b . As a r e s u l t , t h r oughput drops and the response time i n c r e a s e s 2 d r a s t i c a l l y . I t i s v e r y d e s i r a b l e to o p e r a t e the system at the o p t i m a l degree o f m u l t i p r o g r a m m i n g . . U n f o r t u n a t e l y , the system workload i s not s t a t i c , i t v a r i e s w i t h t i m e . T h i s may, f o r example, be caused by u s e r s s u b m i t t i n g new programs i n t o the system or programs undergoing d i f f e r e n t phases o f e x e c u t i o n . T h e r e f o r e i t i s c l e a r t h a t t h e r e i s no s i n g l e v a l u e o f the degree o f multiprogramming which w i l l o p t i m i z e system performance a t a l l t i m e s . I n s t e a d , the c o n t r o l p a r a m e t e r ( s ) has to be recomputed as the workload changes and hence the need f o r a d a p t i v e performance o p t i m i z a t i o n or c o n t r o l . 1.2 Survey of Performance C o n t r o l A l g o r i t h m s The a d a p t i v e performance c o n t r o l a l g o r i t h m s t y p i c a l l y work i n one o f two ways. One o f these i s to a d j u s t the v a l u e s o f system v a r i a b l e s or management p o l i c y parameters such as the CPU quantum t i m e , the I/O b u f f e r s i z e , the r e s i d e n t s e t s i z e and the p r i o r i t y l e v e l o f j o b s , e t c . The o t h e r i s to r e g u l a t e the system l o a d to p r e v e n t the system or any component of the system from s a t u r a t i o n , ( e . g . , by r e g u l a t i n g the degree o f m u l t i p r o g r a m m i n g , the multiprogramming job mix, the b r a n c h i n g p r o b a b i l i t i e s t o each d e v i c e , e t c . ) The f o l l o w i n g i s a s u r v e y o f some of the c o n t r o l a l g o r i t h m s t h a t have been proposed. Bunt and Hume [ 7 ] proposed an a d a p t i v e p r o c e s s o r s c h e d u l i n g scheme based on j o b a r r i v a l p a t t e r n and the 3 approximated s e r v i c e demand d i s t r i b u t i o n . The a l g o r i t h m i s s i m i l a r t o K l e i n r o c k ' s " s e l f i s h - r o u n d - r o b i n " a l g o r i t h m and i s p r i o r i t y - d r i v e n w i t h a parameter B/X. X i s the l i n e a r r a t e a t which j o b s g a i n p r i o r i t y w i t h time w h i l e a w a i t i n g s e r v i c e and B i s the l i n e a r r a t e a t which j o b s g a i n p r i o r i t y w i t h time w h i l e r e c e i v i n g s e r v i c e . Jobs i n the multiprogramming s e t are served i n a round- r o b i n f a s h i o n u n t i l one o f the j o b s c o m p l e t e s , or the p r i o r i t y o f a w a i t i n g j o b grows to exceed t h a t o f a s e r v i c i n g j o b , a t which p o i n t the s e r v i c i n g j o b i s preempted and r e p l a c e d i n s e r v i c e by the w a i t i n g j o b . T h i s a l g o r i t h m adapts i t s e l f t o the workload changes by a d j u s t i n g the r a t e B a c c o r d i n g to the j o b a r r i v a l r a t e and the c u r r e n t e s t i m a t e d c o e f f i c i e n t o f v a r i a t i o n o f the s e r v i c e time d i s t r i b u t i o n . B i s decrea s e d by a f i x e d q u a n t i t y c on each j o b a r r i v a l and i s i n c r e a s e d by the same amount when a j o b i s completed. When the c u r r e n t e s t i m a t e d c o e f f i c i e n t o f v a r i a t i o n o f the s e r v i c e time d i s t r i b u t i o n i s l e s s than 1 , B i s decrea s e d by an amount d and i s i n c r e a s e d by d when the e s t i m a t i o n i s l a r g e r than 1. The major drawback o f t h i s a l g o r i t h m i s t h a t t h e r e i s no s i m p l e way to choose the amount by which B i s to be i n c r e a s e d or d e c r e a s e d . Badel , Gelenbe, L e r o u d i e r , P o t i e r [1] p r e s e n t e d an a d a p t i v e c o n t r o l scheme to o p t i m i z e the performance o f a t i m e - s h a r i n g system. At each j o b a r r i v a l , c o m p l e t i o n or a t pred e t e r m i n e d p o i n t s i n t i m e , an o p t i m a l degree o f m u l t i p r o g r a m m i n g , n 0 , i s e s t i m a t e d from the weighted sum of the observed u t i l i z a t i o n s o f the system p r o c e s s o r s . I f the c u r r e n t 4 degree o f multiprogramming n, i s l e s s than n Q , then i t i s i n c r e a s e d by 1; o t h e r w i s e n remains unchanged. An a l g o r i t h m which e s t i m a t e s n Q i s a l s o g i v e n . The major weakness of t h i s scheme i s t h a t n D i s c a l c u l a t e d f o l l o w i n g a h e u r i s t i c approach which cannot be proved to be o p t i m a l . B r i c e and Browne [6 ] proposed an i n t e g r a t e d - f e e d b a c k -d r i v e n s c h e d u l i n g a l g o r i t h m . T h i s a l g o r i t h m f i r s t computes the p r e d i c t e d I/O b e h a v i o u r f o r each a c t i v e p r o c e s s u s i n g an e x p o n e n t i a l smoothing f o r m u l a . Two p r o c e s s e s , one g e n e r a t i n g output d a t a and the o t h e r r e q u e s t i n g i n p u t , each w i t h the l a r g e s t p r e d i c t e d I/O b e h a v i o u r per u n i t o f CPU t i m e , a re f l a g g e d as p r i v i l e g e d . These p r o c e s s e s a re g i v e n e x t r a CPU quantum, e x t r a b u f f e r memory, and e x t r a I/O d e v i c e r e s o u r c e s . There i s no s y s t e m a t i c way to det e r m i n e how much e x t r a r e s o u r c e s s h o u l d be g i v e n t o the p r i v i l e g e d p r o c e s s e s . K r i t z i n g e r , K r z e s i n s k i and T e u n i s s e n [ 24 ] des i g n e d a r e f e r e n c e model parameter a d a p t i v e (R-MPA) c o n t r o l system to o p t i m i z e the performance o f a Univac 1110 t i m e - s h a r i n g computer system. The b a s i c c o n t r o l machanism a p p l i e s a m o d i f i e d m u t i p l e feedback queuing s c h e d u l i n g a l g o r i t h m (FB N) to the CPU as w e l l as t o memory r e s i d e n t time s c h e d u l i n g s . The c o n t r o l parameters - CPU quantum l e n g t h and memory r e s i d e n t quantum l e n g t h f o r each l e v e l of queues - are observed to have a s e n s i t i v e e f f e c t on system performance. Denning, Kahn, L e r o u d i e r , P o t i e r and S u r i [ 13 ] proposed t h r e e h e u r i s t i c approaches to o p t i m a l l o a d c o n t r o l i n 5 m u l t i p r o g rammed computer systems w i t h paged v i r t u a l memory. They a r e the Knee c r i t e r i o n , the L=S c r i t e r i o n and the 50% c r i t e r i o n . Under the Knee c r i t e r i o n , the mean r e s i d e n t s e t s i z e o f each program i s to be kept near the knee o f t h a t program's l i f e t i m e v e r s u s space f u n t i o n ( thus a l l o w i n g the degree o f multiprogramming to be d e t e r m i n e d ) . The l i f e t i m e f u n c t i o n G(x) of a g i v e n program under a g i v e n memory p o l i c y s p e c i f i e s the mean v i r t u a l t i me between s u c c e s s i v e page f a u l t s when the g i v e n program's r e s i d e n t s e t s i z e averages x pages. The knee o f the l i f e t i m e f u n c t i o n i s the p o i n t beyond which the c u r v e tends to f l a t t e n o u t . I t i s d e f i n e d g e o m e t r i c a l l y as the h i g h e s t p o i n t tengency between a r a y from the o r i g i n and the c u r v e . The i n t u i t i o n o f t h i s c r i t e r i o n i s t h a t o p e r a t i n g the system at the knee tends to m i n i m i z e the component o f memory space-time p r o d u c t due to p a g i n g . S i n c e the speed o f I/O d e v i c e s and the v i r t u a l I/O r e q u e s t r a t e s o f a program are independent o f the r e s i d e n t s e t s i z e , t h i s a l s o tends t o m i n i m i z e the t o t a l memory space-time per j o b . I t has been shown t h a t t h roughput i s maximized i f the memory space-time per job i s mini m i z e d [ 8 , 1 3 ] , Under the L=S c r i t e r i o n , the degree o f multiprogramming n or j o b mix i s c o n t r o l l e d so t h a t the system l i f e t i m e L(n) does not f a l l below the v a l u e cS, where c i s a c o n s t a n t not much l a r g e r than 1 and S i s the page swap t i m e . The r a t i o n a l e behind t h i s c r i t e r i o n i s t h a t s i n c e the system throughput i s bounded by 6 two curves, BQ! (arj i s the CPU e x i t i n g rate and I i s a constant between 0 and 1), and anL(n)/S, the maximum throughput should be c l o s e to the p o i n t of i n t e r s e c t i o n of these two curves, i . e . , L(n)=IS. Under the 50% c r i t e r i o n , the system load i s r e g u l a t e d (e.g., by c o n t r o l l i n g the degree of multiprogramming or job mix) so that the u t i l i z a t i o n of the paging device i s about (50+d)% , where d i s a constant l e s s than 10. The reasoning behind t h i s r u l e i s that when the u t i l i z a t i o n of a simple e x p o n e n t i a l s e r v e r i s 50%, the mean queue length i s 1, which corresponds to the onset of s i g n i f i c a n t queueing. Since t h r a s h i n g i s c h a r a c t e r i z e d by e x c e s s i v e queuing at the paging d e v i c e , i t i s p l a u s i b l e that the optimal throughput i s achieved j u s t before any s i g n i f i c a n t queue appears t h e r e . Gelenbe, Kurinckx and M i t r a n i [ 19 ] proposed a c o n t r o l a l g o r i t h m based on two main p r i n c i p l e s : — T h e degree of multiprogramming must be r e g u l a t e d on the b a s i s of g l o b a l system behaviour rather than on i n d i v i d u a l process behaviour. — I t must be d i s c r i m i n a t o r y a g a i n s t programs which introduce u n d e s i r a b l e p e r t u r b a t i o n s on systems performance, such as a l a r g e number of p a g e - f a u l t s . The proposed c o n t r o l p o l i c y , which i s c a l l e d r a t e c o n t r o l  p o l i c y (RPC), e l i m i n a t e s processes i f t h e i r number of p a g e - f a u l t s exceed M, where M i s a parameter of the RCP. These e l i m i n a t e d processes are brought back to the multiprogramming 7 s e t a t a r a t e p r o p o r t i o n a l to the system throughput r a t e . The d i s a d v a n t a g e o f the p o l i c y i s t h a t i t i s d i f f i c u l t to choose a s u i t a b l e v a l u e f o r M. H i n e , M i t r a n i and Tsur [ 22 ] s t u d i e d two a l g o r i t h m s to c o n t r o l the expected response times o f d i f f e r e n t c l a s s e s o f j o b s i n a paging system by a l l o c a t i n g d i f f e r e n t f r a c t i o n o f memory to each c l a s s w h i l e m a x i m i z i n g the CPU u t i l i z a t i o n . A h e u r i s t i c approach was used to d e t e r m i n e the number of j o b s from each c l a s s t h a t s h o u l d be a c t i v a t e d to maximize the CPU u t i l i z a t i o n . The approach g i v e s good but not n e c e s s a r y o p t i m a l s o l u t i o n . From t h i s s u r v e y , one w i l l n o t i c e t h a t a l t h o u g h a number of a d a p t i v e performance c o n t r o l and o p t i m i z a t i o n a l g o r i t h m s have been proposed and they do improve performance i n some ways, they have two common major weaknesses. One o f them i s t h a t t h e y do not p r o v i d e a s y s t e m a t i c way o f d e t e r m i n i n g the o p t i m a l v a l u e s f o r some of the parameters ( e . g . , the amount by which B s h o u l d be i n c r e a s e d or d e c r e a s e d i n Bunt's a l g o r i t h m ; the amount o f e x t r a r e s o u r c e s t o be g i v e n to the p r i v i l e g e d p r o c e s s e s i n B r i c e ' s scheme; the o p t i m a l CPU and memory r e s i d e n t , quanta f o r each l e v e l of queues i n K r i t z i n g e r ' s p r o p o s a l ; the M i n Gelenbe's RCP p o l i c y ) . The o t h e r weakness i s t h a t these a l g o r i t h m s are not based on a m a t h e m a t i c a l model. B e s i d e s not be i n g a b l e to be proved o p t i m a l (or even near o p t i m a l ) , the r e l a t i o n s h i p s among the system workload and performance parameters are not e a s i l y d e s c r i b a b l e . The r o b u s t n e s s o f the p o l i c y i s a l s o d i f f i c u l t t o be d e t e r m i n e d . 8 1.3 M o t i v a t i o n and G o a l S i n c e most o f the e x i s t i n g a d a p t i v e performance c o n t r o l and o p t i m i z a t i o n a l g o r i t h m s have the weaknesses mentioned i n the above s e c t i o n , i t i s v e r y d e s i r a b l e t o have an a l g o r i t h m or an approach to d e r i v e a l g o r i t h m s based on some m a t h e m a t i c a l model and o p t i m i z a t i o n t e c h n i q u e s . In t h i s t h e s i s we a p p l y some o f the r e s u l t s and t e c h n i q u e s i n o p t i m a l s t o c h a s t i c c o n t r o l t h e o r y t o a d a p t i v e performance c o n t r o l and o p t i m i z a t i o n o f computer systems. The computer system or subsystem i s f i r s t f o r m u l a t e d as an o p t i m a l s t o c h a s t i c problem. The p o l i c y improvement method d e s c r i b e d i n s e c t i o n 2.3 i s then used to compute the o p t i m a l c o n t r o l p o l i c y f o r the system. The p o l i c y thus o b t a i n e d i s dynamic i n the sense t h a t c o n t r o l d e c i s i o n s a r e made based on the c u r r e n t s t a t e o f the system. 9 CHAPTER I I . OPTIMAL STOCHASTIC CONTROL In t h i s c h a p t e r , we r e v i e w some r e s u l t s and t e c h n i q u e s from the t h e o r y o f o p t i m a l s t o c h a s t i c c o n t r o l . We s h a l l c o n c e n t r a t e on markov d e c i s i o n p r o c e s s e s and those r e s u l t s r e l e v e n t to t h i s t h e s i s . The reader i s r e f e r r e d to [ 4 ] f o r a more thorough t r e a t m e n t . 2 , 1 T h e B a s i c Problem. Let S ={1, n} denote the s t a t e space o f a system. To each s t a t e i £ S and each c o n t r o l u i n the f i n i t e c o n t r o l space C t h e r e c o r r e s p o n d s a s e t o f t r a n s i t i o n p r o b a b i l i t i e s P i j ( u ) , j = l , •-n, where p j j denotes the p r o b a b i l i t y t h a t the next s t a t e w i l l be j g i v e n t h a t the c u r r e n t s t a t e i s i and c o n t r o l u i s a p p l i e d . Each time the system i s i n s t a t e i £ S and c o n t r o l u i s a p p l i e d , an expected c o s t g ( i , u ) i s i n c u r r e d . The o b j e c t i v e i s t o m i n i m i z e over a l l a d m i s s i b l e p o l i c i e s «ff = {UQ, U J , ....} w i t h u k:S->C, u k(i)£U(i), V i £§, the averge c o s t per s t a g e N - l J i r ( x 0 ) = l i m (1/N) E { y g [ x k f u k ( x k ) ] } , (2.1) N — >oo k=0 f o r any g i v e n i n i t i a l s t a t e XQ£S. Where x k i s the s t a t e o f the system at time k, U k ( x k ) i s the c o n t r o l a t time k c o n d i t i o n i n g on x k and U ( i ) i s t h e s e t o f a l l p o s s i b l e c o n t r o l s f o r s t a t e i . G iven any s t a t i o n a r y a d m i s s i b l e p o l i c y *ff={u, u, }. 10 Let us denote by P u the t r a n s i t i o n p r o b a b i l i t y m a t r i x h a v i n g elements P i j ( u ( i ) ) : Eu = P l l ( u ( l ) ) P l n ( u ( l ) ) p n l (u(n) ) p n n ( u ( n ) ) By the d e f i n i t i o n o f P i j , we have P i j ( u ( i ) ) 2 : 0 , V i , j , 2 P i n ( u ( i ) ) = 1 , V i j = l Let us now c o n s i d e r the v a l u e of the c o s t f u n c t i o n J*ff(xo) of ( 2 . 1 ) . We may use the n o t a t i o n : J-Ff(i) = J u ( i ) , i = 1, n f o r s t a t i o n a r y p o l i c i e s ir={u, U , }. Denote £u= J u ( D i J u ( 2 ) g d r u ( l ) ) g(2, u(2)) g ( n , u(n)) With t h i s n o t a t i o n i t i s easy t o see t h a t N-1 J u = l i m ( l / N ) y P U G U N — >oo k=0 (2.2) where pjj ( P u r a i s e d to the k t h power) i s the k - step t r a n s i t i o n p r o b a b i l i t i e s c o r r e s p o n d i n g to a s t a t i o n a r y p o l i c y ir={u, u, }. The f o l l o w i n g r e s u l t shows t h a t J u i s w e l l d e f i n e . 11 LEMMA 1. For any rixn s t o c h a s t i c m a t r i x P, i . e . , a m a t r i x w i t h n element p j j s a t i s f y i n g p j j > 0 , i , j =1, ...n, Z P i j = 1, i = l f ...n, we have N-1 l i m (1/N) J P k = P* N — >co k=0 where P* i s a s t o c h a s t i c m a t r i x w i t h the f o l l o w i n g p r o p e r t i e s : (a) P* = PP* = P*P = P*P* (b) U"£+£*) i s an i n v e r s i b l e m a t r i x , where I_ i s an i d e n t i t y matr i x . D enoting N-1 P* = l i m (1/N) y lu ( 2 - 3 ) N — XX> k=0 and u s i n g Lemma 1, we have from (2.2) £u = P^ uGu (2. A) Thus f o r ev e r y a d m i s s i b l e s t a t i o n a r y p o l i c y the c o r r e s p o n d i n g average c o s t per sta g e i s w e l l d e f i n e d and c o n v e n i e n t l y c h a r a c t e r i z e d by e q u a t i o n (2.4). C o n s i d e r a l s o the v e c t o r "u = (I-Pu+ift)"1(I-£u)Gu, where the i n v e r s e above e x i s t by p a r t (b) of Lemma 1. We have (I-£u+P"u")!iu = (I-Pu)Gu- ...(2.5) M u l t i p l y i n g both s i d e s by P u and u s i n g p a r t (a) of Lemma 1, we obta i n PJHu = 0 (2.6) Using (2.6) and (2.4) we may r e w r i t e (2.5) as 12 J u + H u = G U+P U.H U (2.7) T h i s e q u a t i o n i s s a t i s f i e d by e v e r y a d m i s s i b e s t a t i o n a r y p o l i c y T f = { u , u , . . . } . 2.2 C o n d i t i o n s For The E x i s t e n c e Of S t a t i o n a r y Optimal P o l i c y . As a r e s u l t o f the p r e c e d i n g d i s c u s s i o n , we have t h a t a s s o c i a t e d w i t h e v e r y a d m i s s i b l e s t a t i o n a r y p o l i c y i f = {u, u, . . . . } , t h e r e i s a v e c t o r o f average c o s t per s t a g e J u d e f i n e d by (2.3) and (2.4) which s t a t i s f i e s the f u n c t i o n a l e q u a t i o n (2.7) . We s h a l l s t a t e the c o n d i t i o n s under which an o p t i m a l s t a t i o n a r y p o l i c y Tf*={u* , u* , } e x i s t s such t h a t J u ( i ) < J u ( i ) V u , i = l , n and the o p t i m a l c o s t v e c t o r J u has the form J u = tfe where i s a s c a l a r and e i s the u n i t v e c t o r on R n. The c o s t v e c t o r J u = t2fe c o r r e s p o n d i n g to the case where the o p t i m a l c o s t J«Tf(xn), i s independent o f the i n i t i a l s t a t e X Q . 2.2.1 F i n i t e Mean Passage Time C o n d i t i o n . For any two s t a t e s i , j , £s, l e t us denote by k j j ( u ) the s m a l l e s t index k f o r which x k = j when xn=i and the s t a t i o n a r y p o l i c y nr={u, u, } i s used. Then, we have k i j ( u ) = i n f { K | x k = j , x 0 = i , x m ?j f o r l<m<K} We c a l l k _ i ( u ) the f i r s t passage time from i to j a s s o c i a t e d 13 w i t h u. For each i , j and u, k i j ( u ) may be viewed as a random v a r i a b l e t a k i n g p o s i t i v e i n t e g e r v a l u e s or the v a l u e +00 w i t h p r o b a b i l i t i e s q i j = P ( k i j ( u ) = k ) = p ( x k = j , x m 7 * j , 1 <m <k |x 0 = i , i f ) , 0 0 k p(k i i(u)=oo) = 1 - 1 q i j . k = l D e f i n e the mean f i r s t passage time E { k j j ( u ) } a s s o c i a t e d w i t h u by E { k i j ( u ) } =1 00 K 1 k c 3 i j k=l 400 00 K i f z q i j =1 k = l o t h e r w i se 2.2.2 Weak A c c e s s i b i 1 i t y C o n d i t i o n . For any two s t a t e s i , j £ S t h e r e e x i s t s an a d m i s s i b l e s t a t i o n a r y p o l i c y i f = {u, u, } and an i n t e g e r m such t h a t p ^ j ( u ) = p ( x m = j I x 0 = i , i f)>0. THEOREM Suppose t h a t t h e r e e x i s t s a s t a t e t £ S such t h a t f o r e v e r y a d m i s s i b l e s t a t i o n a r y p o l i c y i r = {u, u, } and eve r y s t a t e i E S, E { k j t ( u ) } < 00, or under the weak a c c e s s i b i l i t y c o n d i t i o n then t h e r e e x i s t s a c o n s t a n t and a f u n c t i o n h:S—>R such t h a t 14 n gf+h(i) = min { g ( i , u ) + T P i j ( u ) h ( j ) } , i = l, . . .n ...(2.8) u£U(i) j = l Futhermore, the o p t i m a l v a l u e o f the c o s t f u n c t i o n J f f ( i ) of (2.1) i s e q u a l to (jf f o r e v e r y i = l n, i . e . , 4 = i n f J * r f ( i ) , i = l , ....n. ir In a d d i t i o n , i f u * ( i ) a t t a i n s the minimum i n the r i g h t - h a n d s i d e of (2.8) f o r ev e r y i = l , ....n, then the s t a t i o n a r y p o l i c y «ir* = {u*, u*, ....} i s o p t i m a l [ 4 ] . C o r o l l a r y 1. Let T T = { U , u, ....} be an a d m i s s i b l e s t a t i o n a r y p o l i c y and assume ^ t h a t t h e r e e x i s t s a s t a t e t £S such t h a t E { k j t ( u ) } < oo f o r a l l i £S. Then t h e r e e x i s t s a c o n s t a n t tfu and a f u n c t i o n h u:S—>R such t h a t J u ^ ) = < * U ' I = 1 ' N -Futhermore, n tfu+hu(i) = g ( i , u ( i ) ) + J p j A ( u ( i ) ) h u ( j ) , i = l , 2, ..n, j = l (2.9) E q u a t i o n (2.9) r e p r e s e n t s a system of n l i n e a r e q u a t i o n s w i t h (n+1) unknowns - the s c a l a r s h u ( l ) , h u ( 2 ) , h u ( n ) . We may add one a d d i t i o n a l e q u a t i o n to t h i s system by r e q u i r i n g t h a t h u ( t ) = 0. (2.10) I t has been shown t h a t a unique s o l u t i o n e x i s t s f o r t h i s system [ 4 ] . 1 5 2.3 P o l i c y Improvement A l g o r i t h m In the p r e v i o u s s e c t i o n we s t a t e d the c o n d i t i o n s under which an o p t i m a l s t a t i o n a r y p o l i c y e x i s t s . In t h i s s e c t i o n we d e s c r i b e an a l g o r i t h m c a l l e d the p o l i c y improvement a l g o r i t h m which can be used to s o l v e the average c o s t problem. T h i s a l g o r i t h m can be proved to y i e l d the o p t i m a l p o l i c y . G i ven a s t a t i o n a r y p o l i c y one o b t a i n s an improved p o l i c y by means o f a m i n i m i z a t i o n p r o c e s s u n t i l no f u r t h e r improvement i s p o s s i b l e . We s h a l l assume t h a t t h e r e e x i s t s a s t a t e t £S such t h a t f o r e v e r y a d m i s s i b l e s t a t i o n a r y p o l i c y if = {u, u, . . . . } , the mean f i r s t passage time f o r s t a t e t , E { k j t ( u ) } i s f i n i t e . Let i r k = { u k , u k....} be an a d m i s s i b l e s t a t i o n a r y p o l i c y o b t a i n e d a t the k t h i t e r a t i o n o f the a l g o r i t h m . We determine the average c o s t per s t a t e 0"u c o r r e s p o n d i n g to i f k by s o l v i n g the system o f (n+1) e q u a t i o n s : n i * u K + h j c i i ) = g ( i , u k ( i ) ) + T P i i ( u k ( i ) ) hJC( j ) , i = l, ..n ...(2.11) j = l hJC(t) = 0 . (2.12) S u b s e q u e n t l y , we f i n d a p o l i c y i r k + - ^ = { u k + l , u k + l , } Where u k +-'-(i) i s such t h a t n g ( i , u k + 1 ( i ) ) + J P i i ( u k + l ( i ) ) h U K ( j ) j = l n = min { g ( i , u)+ 2 P i j (u) h j ^ j ) }, i = i , n (2.13) u£U(i) j = l 16 The average cost per stage cCuK+| for the ( k + l ) t n i t e r a t i o n is obtained by solving the system of equations: n < 2 f U *M + h uK+i(i) = g ( i , u k + l (i) ) + T P i n ( u k + 1 (i) )huk+l (j) , i=l,..n j = l h U * M ( t ) = 0 . It can be shown that <zCuK-H < j 2 f u l<. The i t e r a t i o n is repeated u n t i l (^ J^ u*"*' ) * s 0 (° r * n practice, less than some a r b i t r a r i l y small constant). The policy i f k + l = {u k +*, u k + l , } is optimal. 17 CHAPTER I I I . MODEL DESCRIPTION Jobs i n a computer system are o f t e n c l a s s i f i e d i n t o s e v e r a l c a t e g o r i e s such as t e r m i n a l j o b s , database t r a n s a c t i o n s , s m a l l s t u d e n t b a t c h j o b s , p r o d u c t i o n j o b s e t c . . U s u a l l y , d i f f e r e n t q u a l i t y o f s e r v i c e i s g i v e n to j o b s i n d i f f e r e n t c l a s s e s r e f l e c t i n g the importance p l a c e d on them. T h i s i s o f t e n a c c o m p l i s h e d by a s s i g n i n g d i f f e r e n t p r i o r i t i e s and r e g u l a t i n g the r e s o u r c e a l l o c a t i o n d i f f e r e n t l y f o r d i f f e r e n t c l a s s e s o f j o b s . Hine [22] c o n s i d e r e d the use o f memory a l l o c a t i o n to c o n t r o l the expected response t i m e . Landwehr[25] proposed a l o a d c o n t r o l scheme i n combined b a t c h - i n t e r a c t i v e systems which m a i n t a i n s good response f o r i n t e r a c t i v e j o b s w h i l e the b a t c h throughput i s guaranteed to exceed some minimum l e v e l . Under the scheme, the a d m i s s i o n o f a b a t c h j o b i n t o the multiprogramming s e t i s a f u n c t i o n o f the queue l e n g t h o f i n t e r a c t i v e j o b s and the number o f i n t e r a c t i v e j o b s t h a t have been s e r v e d s i n c e the l a s t a d m i s s i o n o f a b a t c h j o b . These a l g o r i t h m s w h i l e meeting the requirement o f g i v i n g d i f f e r e n t q u a l i t y o f s e r v i c e to d i f f e r e n t j o b c l a s s do not n e c e s s a r i l y g uarantee o p t i m a l performance. Here we c o n s i d e r a s i m p l e l o a d c o n t r o l a l g o r i t h m f o r a combined b a t c h - i n t e r a c t i v e system which g i v e s good mean response time t o i n t e r a c t i v e j o b s and a l s o maximizes t o t a l system throughput r a t e . The c o n t r o l i s to r e g u l a t e the number of j o b s 18 i n each c l a s s t o be a c t i v a t e d a t each o f the d i f f e r e n t s t a t e s o f the system. The system s t a t e i s d e f i n e d as a v e c t o r (N l ,N2/ N t) where Nj = number o f c l a s s i j o b s i n the system and t = t o t a l number o f j o b c l a s s e s . For s i m p l i c i t y , we s h a l l c o n s i d e r o n l y two c l a s s e s o f j o b s batch and i n t e r a c t i v e . 3.1 Model D e s c r i p t i o n . The system be i n g m odelled c o n s i s t s o f N t e r m i n a l s , a cpu w i t h Y pages o f main memory, a paging drum and a f i l e d i s k ( s e e F i g u r e 3.1). The i n t e r a c t i v e user t h i n k time i s assumed to be an e x p o n e n t i a l l y d i s t r i b u t e d random v a r i a b l e w i t h mean The a r r i v a l r a t e o f i n t e r a c t i v e j o b s i s thus c ^ T , where c i s the number o f t e r m i n a l s i n the " t h i n k " s t a t e . The i n t e r a r r i v a l time of b a t c h j o b s i s a l s o assumed to be an e x p o n e n t i a l l y d i s t r i b u t e d random v a r i a b l e w i t h mean l/s^g. The cpu s e r v i c e r e q u i r e m e n t s f o r both i n t e r a c t i v e and bat c h j o b s a re assumed to be e x p o n e n t i a l l y d i s t r i b u t e d . At any moment i n t i m e , a j o b i n the system i s e i t h e r b l o c k e d , i . e . , w a i t i n g i n the memory queue a s s o c i a t e d w i t h i t s c l a s s , or i t i s a c t i v e , i . e . , o c c u p y i n g a c e r t a i n amount o f memory and c i r c u l a t i n g among the cpu, the paging drum, and the f i l e d i s k ( c a l l e d the memory l o o p ) . The b e h a v i o u r o f the system i s c o n t r o l l e d by an a d m i s s i o n 19 p o l i c y tf. I f t h e r e a re i n t e r a c t i v e and N2 batch j o b s i n the system ( i n c l u d i n g those w a i t i n g i n memory queues and those i n the memory loop) , i f d e t e r m i n e s n__ and T12, the number o f i n t e r a c t i v e and b a t c h j o b s r e s p e c t i v e l y , to be a d m i t t e d i n t o the memory l o o p . Now we want t o seek an o p t i m a l a d m i s s i o n p o l i c y nr* such t h a t the mean weighted sum o f the number o f j o b s i n each c l a s s i n the system E(w*N__ +N2) per u n i t time i s m i n i m i z e d . I t i s shown i n s e c t i o n 3.3 t h a t m i n i m i z i n g the above o b j e c t i v e f u n c t i o n i s e q u i v a l e n t to m a x i m i z i n g the t o t a l system throughput w h i l e g i v i n g good mean response time to i n t e r a t i v e j o b s (w r e f l e c t s the importance o f the i n t e r a c t i v e j o b r e l a t i v e to the batc h j o b and i s n o m a l l y g r e a t e r than 1 ) . Let T__(ni,n2) and T2(nj,n2) be the throughput r a t e s o f the i n t e r a c t i v e and b a t c h j o b s when t h e r e a re n j i n t e r a c t i v e and n2 batch j o b s i n the memory l o o p r e s p e c t i v e l y . Let the s t a t e o f the system be d e f i n e d by the s t a t e v e c t o r ( N i , N 2 ) , then the system can be t r e a t e d as a t w o - d i m e n s i o n a l b i r t h and death p r o c e s s . Our problem o f s e e k i n g an o p t i m a l a d m i s s i o n p o l i c y becomes the one o f f i n d i n g a mapping of (N__,N2)to ( n _ _ f i . e . , Tf*:(N2,N2) >(nj,n2) such t h a t N - l z = l i m ( l / N ) E { J g ( x k ) } N — >co k = 0 i s minmum, where x k=(Ni,N2) i s the s t a t e o f the system at time k and g ( x k ) i s (w*N_i + N2) • T h i s problem f i t s i n t o the framework o f the b a s i c problem 20 of o p t i m a l s t o c h a s t i c c o n t r o l and hence can be s o l v e d by u s i n g the r e s u l t s and t e c h n i q u e s d e s c r i b e d i n Chapter I I . We f i r s t proceed t o s o l v e T i ( n i , n 2 ) and T 2 ( n i , n 2 ) , then we f o r m u l a t e an o p t i m a l s t o c h a s t i c c o n t r o l problem and f i n a l l y , the p o l i c y inprovement method i s used to determine the o p t i m a l a d m i s s i o n p o l i c y . > ' ( N - N 1 ) ^ T H. T 1 ( n 1 , n 2 ) I i > • '. CPU -Q-, >• DRUM DISK -«—CH T 2 ( n 1 , n 2 ) j Memory Loop i F i g u r e 3.1 The System Model Because o f the b l o c k i n g which o c c u r s when a job cannot be a l l o c a t e d memory, the model does not f i t i n t o the s t r u c t u r e o f the g e n e r a l queueing networks [ 3 , 2 7 ] . An approximate s o l u t i o n i s o b t a i n e d by u s i n g the d e c o m p o s i t i o n t e c h n i q u e f i r s t proposed by C o u r t o i s [ 1 1 ] . T h i s t e c h n i q u e c o n s i s t s o f h i e r a c b i c a l l y decomposing a network i n t o n ested ( s u b ) n e t w o r k s . S t e a d y - s t a t e s o l u t i o n s f o r the subnetworks a r e f i r s t d e r i v e d as i f they were independent c l o s e d queueing networks ( w i t h o u t any i n t e r a c t i o n w i t h the s u r r o u n d i n g n e t w o r k s ) . These r e s u l t s a r e then used to 21 s o l v e the e n c l o s i n g network. In the case where the r a t e o f s t a t e - t r a n s i t i o n w i t h i n the subnetworks g r e a t l y exceed the r a t e of s t a t e - t r a n s i t i o n among the subnetworks, the approximate s o l u t i o n w i l l be v e r y c l o s e to the e x a c t s o l u t i o n . In our model, the r a t e o f s t a t e change caused by t r a n s i t i o n s among the d e v i c e s w i t h i n the memory l o o p i s much h i g h e r than the r a t e o f s t a t e change caused by the a d m i s s i o n or d e p a r t u r e o f j o b s from the memory l o o p . I t i s t h e r e f o r e j u s t i f i e d to use the d e c o m p o s i t i o n t e c h n i q u e t o s o l v e our model. We now s o l v e the memory l o o p as a c l o s e d c e n t r a l - s e r v e r network w i t h n__ i n t e r a c t i v e and r\2 batch j o b s . 3.2 The Memory Loop As A C l o s e d C e n t r a l - S e r v e r Network. Let l / u i r be the random v a r i a b l e r e p r e s e n t i n g the u n i n t e r r u p t e d cpu time r e q u e s t s o f c l a s s r j o b s ( r = l , 2 f o r i n t e r a c t i v e and b a t c h j o b s r e s p e c t i v e l y ) . Jobs be i n g served by the cpu can be i n t e r r u p t e d by page f a u l t s , f i l e d i s k r e q u e s t s or job c o m p l e t i o n i n t e r r u p t s . I f we assume t h a t these t h r e e c l a s s e s o f ev e n t s a re independent, we can s e t 1/U2 r = min {1/E r,1/D r,1/C r }, r = l , 2 , where 1/E r and 1/D r are the random v a r i a b l e s g i v i n g the amount o f v i r t u a l time between two s u c c e s s i v e p a g e - f a u l t s and f i l e d i s k r e q u e s t s r e s p e c t i v e l y . 1/C r i s the random v a r i a b l e r e p r e s e n t i n g the cpu s e r v i c e r e q u i r e m e n t which i s assumed to be e x p o n e n t i a l l y d i s t r i b u t e d w i t h mean l / c r . The d i s t r i b u t i o n o f 1/D r i s a l s o assumed to be e x p o n e n t i a l w i t h mean l / d r , r = l , 2 , and t h a t the d i s t r i b u t i o n o f 22 f i l e d i s k r e q u e s t s i n v i r t u a l time i s independent o f the memory a l l o c a t i o n . The paging b e h a v i o u r o f a c l a s s r j ob e x e c u t i n g w i t h p pages o f main memory a l l o c a t i o n i s modelled by a l i f e t i m e f u n c t i o n which d e t e r m i n e s the expected v i r t u a l time between two s u c e s s i v e page f a u l t s , L r ( p ) , as a f u n c t i o n o f the memory a l l o c a t i o n . Here, we adopt the l i f e t i m e f u n c t i o n proposed by C h a m b e r l i n e t . a l . [ 10 ] shown i n F i g u r e 3.2. ...(3.1) where b r i s the expected v i r t u a l i n t e r p a g e - f a u l t time when a jo b i s a l l o c a t e d a r pages o f memory, and a r i s the number of pages t h a t p r o v i d e s the j o b w i t h h a l f o f i t s l o n g e s t p o s s i b l e 1 i f e t ime. Because 1/E r, 1/D r, and 1/C r are drawn from e x p o n e n t i a l d i s t r i b u t i o n s , the random v a r i a b l e l / u _ _ r w i l l a l s o be e x p o n e n t i a l l y d i s t r i b u t e d . Hence the cpu e x i t r a t e i s g i v e n by u l r = d r + c r + 1/L r(p) ...(3.2) 23 The memory l o o p i s c o n s i d e r e d as a c l o s e d c e n t r a l - s e r v e r model w i t h n i i n t e r a c t i v e and r\2 batch j o b s . There a re t h r e e s e r v i c e s t a t i o n s - the c p u ( s e r v e r 1)', the drum ( s e r v e r 2) and the d i s k ( s e r v e r 3 ) . We assume t h a t the mean drum and d i s k s e r v i c e r a t e s ( U 2 and U3 r e s p e c t i v e l y ) are the same f o r a l l c l a s s e s o f j o b s . The t r a n s i t i o n p r o b a b i l i t i e s q i j ( r ) of g o i n g from s e r v e r i to s e r v e r j f o r a j o b i n c l a s s r , are g i v e n by: q 1 2 ( r ) = l / ( u l r . L r ( p r ) ) , * q 1 3 ( r ) = d r / u l r , 331< r) = q21 (r) = 1 . . CPU DRUM DISK - C M v — F i g u r e 3.3 The Memory Loop Subnetwork The s t a t e o f the model i s d e s c r i b e d i n terms o f the number o f jo b s o f each c l a s s a t each s e r v e r . Let us denote by k j r the number o f c l a s s r j o b s a t s e r v e r i , i= 1, 2, 3, r = l , 2 . T h e r e f o r e 3 k i = Z k i r * s t n e t o t a l number o f jo b s a t s e r v e r i , a •'•-> 3 Z k i r = n r and T k i = n] + n2 = n r-l i - l A c c o r d i n g to B a s k e t t e t . a l . [ 3 ] , the s t a t i o n a r y p r o b a b i l i t y of s t a t e K = ( k ^ i , k j 2 t k 2 1 > k 2 2 * k31> k32) ^ s g i v e n by the pro d u c t form i n e q u a t i o n ( 3 . 3 ) . T h i s assumes t h a t the s e r v i c e d i s c i p l i n e 24 of the cpu, f o r which the s e r v i c e r a t e u^j- i s c l a s s - d e p e n d e n t , i s p r o c e s s o r s h a r i n g . 1 2 ( x n ) k i r ( x 2 r ) k 2 r p n < £ ) = k l ! k 2 ! k 3 ! TT { . G(n) r = l k l r ! k 2 r ! ( x 3 r ) k3r k 3 r ! (3.3) The X i r ' s a r e a s o l u t i o n o f the t r a n s i t i o n e q u a t i o n s 3 Z <3i j U) u i r x i r = u j r . x j r i = l J j= 1,2,3 r = l , 2 (3.4) G(n) i s the n o r m a l i z i n g c o n s t a n t which n o r m a l i z e s the sum of a l l p r o b a b i l i t i e s t o 1, n i s the v e c t o r ( n - [ , n 2 ) . In our model the homogeneous s o l u t i o n o f (3.3) i s easy to f i n d : x l r = 1 q 1 2 ( r ) . u l r  u 2 x 2 r = U 2 . L r ( p r ) x 3 r = q i 3 (r) . u i r d u 3 r u 3 (3.5) E q u a t i o n (3.3) can be w r i t t e n as P n ( K ) = P n ( k l l / k 1 2 ' k 2 1 ' k 2 2 ' k 3 1 ' k 3 2 ) 1 2 1 1 1 = — - . k l ! k 2 ! k 3 ! TT{ . ( e n ( r ) / u 2 ) k 2 r . ( d r / u 3 ) k 3 ^ ) } G(n) r = l k i r , k 2 r ! ~ k 3 r ! (3.6) 25 where e n ( r ) i s the mean page f a u l t r a t e o f the c l a s s r j o b s when t h e r e a re n j o b s i n the memory l o o p . 1 e n (r) = (3.7) L r ( s n ( r ) ) . where s n ( r ) i s the mean number o f pages o f memory a l l o c a t e d to c l a s s r j o b s when the l o a d o f the model i s n and L r ( . ) i s the l i f e t i m e f u n c t i o n o f c l a s s r j o b s . There are many f a c t o r s which i n f l u e n c e the v a l u e o f s n ( r ) (e.g., page replacement a l g o r i t h m , program l o c a l i t y , speed of the paging d e v i c e e t c . ) . U n f o r t u n a t e l y , t h e y have not been s t u d i e d s y s t e m a t i c a l l y , and the v a l u e of s n ( r ) i s g e n e r a l l y not a v a i l a b l e e x cept f o r the case when the memory i s e q u a l l y p a r t i t i o n e d among a l l the j o b s . In our model, the e q u i p a r t i t i o n scheme i s used, and hence s n ( r ) i s g i v e n by : Y s n ( r ) = , r = l , 2 (3.8) n 1 + n 2 where Y i s the t o t a l memory c a p a c i t y . 3.2.1 Computation Of G (n) We now t u r n our a t t e n t i o n t o the method of computing the n o r m a l i z i n g c o n s t a n t G ( n ) . E q u a t i o n (3.3) i s r e w r i t t e n i n the f o l l o w i n g e q u i v a l e n t form: 26 1 M k n k i 2 ( k . i i + k i 2 ) ! P n ( K ) = TT{(xii) . ( x i 2 ) • } (3.9) G(n) i = l kill . k i 2 ! Where M i s the number o f s e r v e r s i n the network. In our model M i s e q u a l t o t h r e e . S i n c e G(n) i s d e f i n e d so t h a t a l l the P n ( K ) sum to one, i t f o l l o w s t h a t M k n k i 2 ( k i l + k 1 2 ) I G(n) = 1 TT{(x i :L) . ( x i 2 ) • } (3.10) K£s(n,M) i = l k i l ! - k i 2 ! M where s(n,M) = { ( k 1 1 , k 1 2 , kMl' kM2) I I k i r = n r ' r = l r 2 , i = l and k j r 1 0 V r} Note t h a t the sui (nj+M-lN /h 2+M-l\ M-l J V M-l / at_ he summation i n e q u a t i o n (3.10) i s taken over a l l p o s s i b l e system s t a t e s ( k _ Q , k i 2 , k M l ' k M 2 ) * I t would be e x t r e m e l y e x p e n s i v e t o compute G(n) d i r e c t l y from (3.10). An e f f i c i e n t way o f computing G(n) i s n e c e s s a r y . Our approach i s l a r g e l y based on Buzen [ 9 ] . De f i n e an a u x i l i a r y f u n c t i o n m k n k i 2 ( k i l + k i 2 ) ! g(n_L,n2,m) = 7 TT { ( X J I ) . ( X J 2 ) . } K£s(n l fn 2,m) i = l kj_11 . k i 2> (3.11) 27 Note t h a t G (n) i n (3.10) i s eq u a l to g(ni,n2,M) w i t h n = ( n j , n 2 ) . Observe t h a t the system s t a t e s K £s(ni,n2/m) can be grouped i n t o s e v e r a l groups by the number o f j o b s from one p a r t i c u l a r c l a s s p r e s e n t i n one p a r t i c u l a r s e r v e r . Grouping by the number o f c l a s s 1 j o b s p r e s e n t i n s e r v e r m, we have g ( n l / n 2 ' m ) =  n l Z ( z P=0 K£s(n^-p,n2,m) & k m l=p m k n k i 2 TT (x i i ) . ( X J 2 ) i = l ( k i l + k i 2 ) ! k n i . k i 2 ! g r o u p i n g f u r t h e r by the number o f c l a s s 2 jo b s p r e s e n t i n s e r v e r m we have g(ni,n2,m) = n l n 2 m k i l k i 2 ( k i ! + k i 2 ) ! Z Z { Z TT ( x n ) . ( x i 2 ) . } P=0 q=0 K£s(ni-p,n 2-q,m) i = l k i l ! - k i 2 ! & k m l = p , k m 2 = q (3.12) N o t i c e t h a t K£s(n 1-p,n 2-q,m) & k m l = P ' k m 2 = g m k i 2 k i 2 ( k i i + k i 2 ) ! TT { ( x n ) . ( x i 2 ) • } i = l k i l ! - k i 2 ! i s summed over a l l the s t a t e s which have the same numbers (p and q r e s p e c t i v e l y ) of c l a s s 1 and c l a s s 2 jo b s i n s e r v e r m Hence 28 m k n k i 2 ( k i l + k i 2 ) ! Z TT { ( x n ) . ( x i 2 ) . } K£s(ni-p,n 2-q,m) i = l k i 1 i • k i 2 !  & kml=P' km2 =q (p+q) ! p q m-l k n k i 2 Z { ( x m l ) (x m 2 ) TT { ( x n ) . ( x i 2 ) .Ti}} K£s(ni-p,n 2-q,m) p!q! i = l &k m l=p,k m 2=q (p+q) I p q m-l k n k i 2 = ( x m l ) (x m 2 ) Z T T { ( x i ; i ) ( x i 2 ) . T i } p!q! K£s (n_[-p. n 2-q,m-l) i = l (3.13) ( k i l + k i 2 ) ! where T i = k i l ' k i 2 ' By d e f i n i t i o n o f the f u n c t i o n g m-l kil k i 2 ( k i l + k i 2 ) l Z ( TT { ( x u ) . ( x i 2 ) . }} K£s(n2-p,n 2-q,m-l) i = l k i l ! - k i 2 ! = g (n]_-p, n 2 - q , m-l) (3.14) Now combining e q u a t i o n s ( 3 . 1 2 ) , (3.13) and (3.14) we o b t a i n , f o r m>l, n l n 2 (P+<3) I P q g ( n l f n 2 , m ) = T Z l ( x mi ) • ( x m 2 ).g(n!-p,n 2-q,m-l)}.(3.15) p=0 q=0 p'q! A l s o observe t h a t , 29 n i ri2 (ni+n2) ! g ( n i f n 2 * l ) = Un) ' -(*12) • (3.16) n i l - n 2 ! The r e c u r s i v e r e l a t i o n s h i p s p e c i f i e d i n (3.15) t o g e t h e r w i t h the i n i t i a l c o n d i t i o n s g i v e n i n (3.16) c o m p l e t e l y d e f i n e the a l g o r i t h m f o r computing g(n__,n2fm) and hence G (N) . The t o t a l u t i l i z a t i o n o f s e r v e r m w i t h l o a d n i n the ne t w o r k , u n ( m ) , i s g i v e n by u n(m) = J P n ( K ) ~ K£s(ni,n 2,m) ~ &k m l>0.k m 2>0 However i t i s e a s i e r t o compute the t o t a l i d l e time o f t h a t s e r v e r f i r s t and o b t a i n the u t i l i z a t i o n by s u b t r a c t i n g i t from 1. The t o t a l i d l e time o f the s e r v e r m i s g i v e n by I n(m) = I P n ( K ) K£s (n] ,n2,m) *" &k m l=0,k m 2=0 1 k m l km2 ( k m l + k m 2 M y { ( X m l ) . ( x m 2 ) • - F i } g(n 1,n 2,m) K£s(n,m) k m l ! - k m 2 ! & k m l = 0 ' k m 2 = 0 = 1 y F i g(n l fn2,m) K£s(n,m-1) g ( n l f n 2 , m - l ) 9 ( n l / n 2 ' m ) where m-1 k n k i 2 ( k n + K i 2 ) l F i = TT { ( x i i ) . ( x i 2 ) • }. i = l k i l ! k i 2 ! Hence u n(m) = l-In(m) g ( n 1 , n 2 , m - l ) = !_ . (3.17) g ( n i , n 2 f m ) The p a r t i a l u t i l i z a t i o n o f s e r v e r m f o r c l a s s r j o b s , u n(m,r) g i v e n by kmr u n ( m f r ) = 2 p n ( K ) - -K£s(n,m) ~ k m l + k m 2 &k m r>0 1 n l kmr y ( y H i . ) g(ni,n 2,m) p=l K£s(nj-p,n 2,m) k m l + k m 2 & kml=P where m kil k i 2 ( k i l + k i 2 ) ! Hi = TT { ( X i i ) . ( x i 2 ) . } . i = l k i l ! k i 2 ! F o l l o w i n g the same procedure f o r d e r i v i n g G(n) we g e t 31 1 n j n 2 p (P+q)! u n(m,r) = J 7 { . g ( n 1 / n 2 f m ) p=l q=0 p+q p!q! p q ( x m l ) . ( x m 2 ) .g(n 1-p,n2-q,m-l)} (3.18) The throughput r a t e o f c l a s s r j o b s i n the memory l o o p T r ( n i , n 2 ) can now be computed from e q u a t i o n s (3 .18 ) , (3 .16 ) , (3 .15) , (3 . 8 ): and ( 3 . 5 ) . 3.3 F o r m u l a t i o n of The Op t i m a l C o n t r o l Problem ( n ^ , n 2 ) A g g r e g a t e S e r v e r T 2 ( n 1 , n 2 ) F i g u r e 3.4 The System Model w i t h the memory l o o p r e p l a c e d by an aggregate s e r v e r 32 We r e p l a c e the memory l o o p by a s i n g l e aggregate s e r v e r ( F i g u r e 3.4). The s e r v i c e r a t e o f t h i s s e r v e r f o r c l a s s r j o b s i s T r ( n i , n 2 ) / where T r ( n i , n 2 ) i s the throughput r a t e o f c l a s s r j o b s through the memory l o o p when t h e r e are n^ c l a s s 1 and n2 c l a s s 2 j o b s i n s i d e the l o o p . The s t a t e v e c t o r o f the whole system (Ni,N2) can be t r e a t e d as a two d i m e n s i o n a l b i r t h and death p r o c e s s . In a s m a l l time i n t e r v a l h, the t r a n s i t i o n p r o b a b i l i t y , P i ^ C n ) ' ° f g o i n g from s t a t e _ i t o s t a t e j _ , when the l o a d o f the memory l o o p i s n ( i . e . , w i t h n^ c l a s s 1 and n 2 c l a s s 2 j o b s i n the memory l o o p ) , i s g i v e n by: S*Eh, f o r j_=(N l fN2), j = ( N l f N 2 + l ) , N 2 < m2-l (N-N2)^ Th, f o r j.= ( N 1 , N 2 ) , _j=(Ni+l,N 2) P i -5 (n) = T i ( n ) h , f or i= ( N 2 ,N 2) , j= (N x-1 ,N 2) , nj>0 T 2 ( n ) h , f o r J.= ( N l f N 2 ) , j = ( N l f N 2 - l ) , N 2>0 --(sum o f the above f o u r cases) f o r _i= j 0, o t h e r w i s e (3.18) where m2 i s the maximum number o f c l a s s 2 jo b s a l l o w e d i n the system + . R e c a l l t h a t the b e h a v i o u r o f the system i s c o n t r o l l e d by an a d m i s s i o n p o l i c y I f t h e r e a re Nj c l a s s 1 and N 2 c l a s s 2 j o b s i n the system, i f d e t e r m i n e s n^ and n2, the numbers o f c l a s s 1 and c l a s s 2 j o b s r e s p e c t i v e l y , to be a d m i t t e d i n t o the memory l o o p . We seek an o p t i m a l a d m i s s i o n p o l i c y T T* such t h a t the mean weighted sum o f the number o f j o b s i n each c l a s s i n the system E(w*Ni+N 2) per u n i t time i s m i n i m i z e d . I f w i s one, then L i t t l e ' s law can be used to show t h a t i f * w i l l maximize the + m2 i s s e t a t some f i n i t e q u a n t i t y f o r c o m p u t a t i o n a l e f f i c i e n c y o n l y . Otherwise t h e r e w i l l be i n f i n i t e number o f system s t a t e s . 33 system throughput r a t e . I f t he c o n t r o l d e c i s i o n i s made each time a j o b a r r i v e s or d e p a r t s from the system, the system s t a t e v e c t o r (N_[,N2) can be d e s c r i b e d by a two d i m e n s i o n a l semi-Markov d e c i s i o n p r o c e s s . The s e t o f p o s s i b l e c o n t r o l f o r each s t a t e j.= (N;_,N2), i s {n=(n__,n2), 0 < n i < N^, 0 < n2 < N2K I t i s easy to see t h a t the t r a n s i t i o n p r o b a b i l i t y , P i j (n) .of g o i n g from s t a t e _ i t o s t a t e _j when c o n t r o l n i s a p p l i e d i s the same as those g i v e n i n (3.18) . The problem o f f i n d i n g an o p t i m a l a d m i s s i o n p o l i c y i s f o r m u l a t e d as a m i n i m i z a t i o n problem of average c o s t per u n i t time over a l l a d m i s s i b l e p o l i c i e s N - l k min { Jif= l i m (1/N) 7 Pifgif } N — >oo k=0 where Prf i s the t r a n s i t i o n p r o b a b i l i t y m a t r i x h a v i n g element P i j , and g(0,0) g d , 0 ) g(N},N 2)=w*Ni+N2 gif = I gd,i) g ( N 2 , N 2 ) g(N,m2) w r e f l e c t s the importance o f the i n t e r a c t i v e j o b r e l a t i v e t o the ba t c h j o b and i s n o r m a l l y g r e a t e r than 1. Note t h a t f o r the case w=l,the average t o t a l number o f j o b s i n the system i s mi n i m i z e d which i s e q u i v a l e n t t o m a x i m i z i n g the t o t a l system 34 t h r o u g h p u t . The o p t i m a l a d m i s s i o n p o l i c y i s s o l v e d by the p o l i c y improvement method d e s c r i b e d i n Chapter I I . 35 CHAPTER IV. INTERPRETING THE RESULTS In t h i s c h a p t e r , we a n a l y z e the performance o f the o p t i m a l a d m i s s i o n p o l i c y o b t a i n e d i n Chapter I I I u s i n g the p o l i c y improvement method d e s c r i b e d i n Chapter I I . Our major performance i n d i c e s a r e the mean response times and throughput r a t e s f o r each c l a s s o f j o b s . The performance i n d i c e s o f a g i v e n a d m i s s i o n p o l i c y , if={u,u, } can be computed by u s i n g an a p p r o p r i a t e g f u n c t i o n i n e q u a t i o n ( 2 . 1 1 ) . To compute the mean response t i m e , R_[, f o r i n t e r a c t i v e j o b s , we f i r s t compute the mean number o f i n t e r a c t i v e j o b s Z] i n the system by u s i n g g ( i ,u ( i ) ) =N]_ i n e q u a t i o n (2.11) and then a p p l y L i t t l e ' s f o r m u l a t o o b t a i n : Z l R l = (4.1) ^ T ( N 1 - Z 1 ) S i m i l a r l y , the mean tu r n a r o u n d time f o r b a t c h j o b s i s g i v e n by: z 2 R 2 = (4.2) where Z 2 i s the mean number o f b a t c h j o b s i n the system and i s computed by u s i n g g ( i , u ( i ) ) = N 2 i n e q u a t i o n ( 2 . 1 1 ) . The mean throughput r a t e s f o r i n t e r a c t i v e and b a t c h j o b s a re computed by 36 u s i n g g'( i ,u ( i ) ) =T] (ni ,n 2) and g ( i ,u ( i ) ) =T 2 (ni ,n 2) r e s p e c t i v e l y . T r ( n i , n 2 ) , r = 1,2, i s the throughput o f c l a s s r j o b s through the memory l o o p ( F i g u r e 3.1) when the c o n t r o l u ( i ) = ( n i , n 2 ) i s a p p l i e d . The co m p u t a t i o n o f T r ( n i , n 2 ) i s d e s c r i b e d i n s e c t i o n 2 of Chapter I I I . A.1 The E f f e c t s o f the Weight w on Performance S i n c e the o p t i m a l a d m i s s i o n p o l i c y m i n i m i z e s the mean weighted sum of the number o f j o b s i n each c l a s s i n the system, the e f f e c t s o f w on the performance i n d i c e s d e s e r v e e x a m i n a t i o n . F i g u r e s 4.1(a) through 4.9(a) are a s e r i e s o f p l o t s o f the mean response times f o r each c l a s s o f j o b s c o r r e s p o n d i n g to the o p t i m a l a d m i s s i o n p o l i c i e s v e r s u s the weight (w) under d i f f e r e n t w orkload c o n d i t i o n s . The mean response times f o r each c l a s s o f jo b s w i t h o u t c o n t r o l and the lower-bound mean response time f o r i n t e r a c t i v e j o b s ( i . e . , when the b a t c h stream i s absent and the o p t i m a l c o n t r o l i s a p p l i e d ) are a l s o p l o t t e d on each o f these g r a p h s . F i g u r e s 4 . 1 ( b ) — 4 . 9 ( b ) are a s e r i e s o f p l o t s o f throughput f o r each c l a s s o f j o b s w i t h and w i t h o u t c o n t r o l ; and t o t a l system throughput w i t h c o n t r o l v e r s u s weight w. The d i f f e r e n t w orkload c o n d i t i o n s a r e s i m u l a t e d by v a r y i n g the cpu re q u i r e m e n t s f o r each c l a s s o f j o b s s y s t e m a t i c a l l y over a range of v a l u e s and keeping the o t h e r workload parameters c o n s t a n t . T h i s i s j u s t i f i e d on the ground t h a t changing the o t h e r 37 parameter v a l u e s has the same o v e r a l l e f f e c t o f a f f e c t i n g the r e s i d e n c e times o f j o b s i n the system. These f i g u r e s show t h a t the o p t i m a l a d m i s s i o n p o l i c y improves the mean response times and t h r o u g h p u t s f o r each c l a s s of j o b s c o n s i d e r a b l y over those w i t h no c o n t r o l . The e x a c t improvements depend on the workload of the system. G e n e r a l l y , the h e a v i e r the workload the g r e a t e r the improvements. When the system l o a d i s l i g h t the improvement i s o n l y m a r g i n a l . T h i s l e a d s t o the l o g i c a l c o n c l u s i o n t h a t t h e r e i s no need to c o n t r o l the system i f the expected workload i s l i g h t . From the f i g u r e s , the f o l l o w i n g i n t e r e s t i n g e f f e c t s o f w on the performance i n d i c e s a re o b s e r v e d : A) An i n c r e a s e d v a l u e o f w i n c r e a s e s the i n t e r a c t i v e t h roughput and d e c r e a s e s the b a t c h t h r o u g h p u t . I t a l s o d e c r e a s e s the mean i n t e r a c t i v e response time and i n c r e a s e s the ba t c h t u r n - a r o u n d t i m e . In o t h e r words, the l a r g e r the v a l u e o f w the b e t t e r the q u a l i t y o f s e r v i c e i s g i v e n to the i n t e r a c t i v e j o b s . B) When w exceeds a c e r t a i n v a l u e , the r a t e s o f change o f the v a l u e s o f the performance i n d i c e s w i t h r e s p e c t to w decrease as w i n c r e a s e s and become i n s i g n i f i c a n t f o r l a r g e w. T h i s i s an i m p o r t a n t p r o p e r t y because i t i m p l i e s t h a t the b a t c h throughput w i l l not c o n t i n u e to drop as w i n c r e a s e s but i s guaranteed to exceed some minimum l e v e l . C) The t o t a l system throughput does not v a r y a p p r e c i a b l y as w v a r i e s . R e c a l l t h a t when w=l, the o p t i m a l a d m i s s i o n p o l i c y 38 m i n i m i z e s the t o t a l number o f j o b s i n the system which i s e q u i v a l e n t t o m a x i m i z i n g the t o t a l system t h r o u g h p u t . T h i s p r o p e r t y i m p l i e s t h a t the o p t i m a l a d m i s s i o n p o l i c y always produces maximum or near-maximum t o t a l system throughput r e g a r d l e s s o f the v a l u e o f the weight choosen. D) The mean i n t e r a c t i v e response time becomes v e r y c l o s e t o the lower-bound when w exceeds some v a l u e ( d e n o t e d by w*). The v a l u e o f w* depends on the r e l a t i v e l o a d s o f i n t e r a c t i v e and b a t c h j o b s . The h e a v i e r the i n t e r a c t i v e l o a d r e l a t i v e to the ba t c h l o a d the g r e a t e r the v a l u e o f w*. T h i s p r o p e r t y s u g g e s t s t h a t we can choose a s u i t a b l y l a r g e v a l u e o f w such t h a t the mean i n t e r a c t i v e response time i s a c c e p t a b l y low (say w i t h i n 10 p e r c e n t o f the lower bound). From the above o b s e r v a t i o n s , we can see t h a t an o p t i m a l a d m i s s i o n p o l i c y can be o b t a i n e d by c h o o s i n g a s u i t a b l e v a l u e o f w w h i c h , 1) g i v e s good response to the i n t e r a c t i v e j o b s , 2) maximizes the t o t a l system t h r o u g h p u t , 3) g u a r a n t e e s a minimum batch t h r o u g h p u t . S i n c e the o p t i m a l a d m i s s i o n p o l i c y improves the mean i n t e r a c t i v e response time c o n s i d e r a b l y over t h a t w i t h no c o n t r o l ( e s p e c i a l l y when the l o a d i s heavy) we expect t h a t w i t h the o p t i m a l a d m i s s i o n p o l i c y the system can s u p p o r t more t e r m i n a l s . To v e r i f y t h i s we p l o t the i n t e r a c t i v e response times ( w i t h and w i t h o u t c o n t r o l ) v e r s u s the number o f t e r m i n a l s ( F i g u r e 4.10). I t shows t h a t the s a t u r a t i o n p o i n t ( a c c o r d i n g to K l e i n r o c k ' s 39 d e f i n i t i o n + [ 23 ]) w i t h c o n t r o l (6) i s v e r y much l a r g e r than the s a t u r a t i o n p o i n t w i t h no c o n t r o l ( 3 ) . ^ * 2 , T n e O p t i m a l A d m i s s i o n P o l i c y T a b l e s (4.1) through (4.17) show a s e r i e s o f o p t i m a l a d m i s s i o n p o l i c i e s o b t a i n e d by the p o l i c y improvement method. I t i s v e r y o b v i o u s t h a t the weight (w) of the o b j e c t i v e f u n c t i o n a f f e c t s the o p t i m a l a d m i s s i o n p o l i c i e s . For a g i v e n s e t o f parameter v a l u e s , d i f f e r e n t w e i g h t s i n the o b j e c t i v e f u n c t i o n r e s u l t i n d i f f e r e n t o p t i m a l a d m i s s i o n p o l i c i e s . T a b l e s (4.1) to (4.6) are the p o l i c i e s o b t a i n e d by u s i n g d i f f e r e n t w e i g h t s ( r a n g i n g from 1 to 3.5) and keeping the o t h e r parameters unchanged. The o t h e r parameter v a l u e s used a r e : ^^=0.05, <2f B=0.1, Y=60 pages, N=6, m2=5, b T=0.018, b B=0.012, c B=10, c T=20, T I 0=20, B I 0=10, F s=30, p s=80, cpuT=0.3, cpuB=0.3. Where 1/j^T =mean t e r m i n a l " t h i n k " time efg =mean b a t c h a r r i v a l r a t e Y = t o t a l memory s i z e N =number o f t e r m i n a l s m2 =maximun number o f b a t c h j o b s t o be c o n s i d e r e d b>p,bg,cip,cg =parameter o f the l i f e t i m e f u n c t i o n s f o r bat c h and t e r m i n a l j o b s TjQ =mean i n t e r a c t i v e I/O r e q u e s t r a t e BjQ =mean b a t c h I/O r e q u e s t e r a t e + d e f i n e d as the i n t e r s e c t i o n o f the mean n o r m a l i z e d response time c u r v e asymptote and the h o r i z o n a l l i n e c o r r e s p o n d i n g to the mean response time when t h e r e i s o n l y one t e r m i n a l . 40 P s = mean paging r a t e F s =mean I/O s e r v i c e r a t e cpuT =mean i n t e r a c t i v e cpu s e r v i c e r a t e cpuB =mean b a t c h cpu s e r v i c e r a t e As e x p e c ted these t a b l e s show t h a t the l a r g e r the weight used i n the o b j e c t i v e f u n c t i o n the h i g h e r the p r i o r i t y g i v e n to the i n t e r a t i v e j o b s . T h i s i s r e f l e c t e d by the f a c t t h a t a t some of the system s t a t e s the p o l i c y w i t h the l a r g e r weight admits more i n t e r a c t i v e j o b s i n t o the memory l o o p than those by p o l i c i e s w i t h a s m a l l e r w e i g h t . The p o l i c i e s i n t a b l e s ( 4 . 7 ) — ( 4 . 1 1 ) , have the same s e t o f parameter v a l u e s and weight except f o r cpuB, the mean b a t c h cpu s e r v i c e r a t e , which v a r i e s from 0.2 to 0.6. V a r y i n g cpuB and keep i n g the o t h e r parameters c o n s t a n t s i m u l a t e s d i f f e r e n t r e l a t i v e l o a d s between i n t e r a c t i v e and bat c h j o b s . These t a b l e s show t h a t the l i g h t e r the l o a d of one c l a s s o f j o b s r e l a t i v e to the o t h e r the b e t t e r s e r v i c e i t w i l l r e c e i v e . For example, as cpuB i n c r e a s e s (hence the b a t c h l o a d d e c r e a s e s ) the o p t i m a l p o l i c y a dmits more b a t c h and l e s s i n t e r a c t i v e j o b s i n t o the memory l o o p a t the same system s t a t e s . T a b l e s ( 4 . 1 2 ) — ( 4 . 1 7 ) a r e - t h e o p t i m a l a d m i s s i o n p o l i c i e s f o r d i f f e r e n t w o r k l o a d s which g i v e mean i n t e r a c t i v e response time c l o s e t o the lower bound. By comparing these p o l i c i e s i t i s observed t h a t t h e y a r e v e r y s i m i l a r to one another and a l l e x h i b i t a s i m i l a r p a t t e r n . Very o f t e n , when the number o f i n t e r a c t i v e j o b s i n the system exceeds some number (3 i n our 41 n u m e r i c a l example) the p o l i c i e s w i l l admit o n l y t h a t number o f i n t e r a c t i v e j o b s i n t o the memory l o o p r e g a r d l e s s o f how many ba t c h and i n t e r a c t i v e j o b s t h e r e are i n the system. From t a b l e (4.18) i t i s observed t h a t t h a t number i s equal to the number o f i n t e r a c t i v e j o b s which produces the h i g h e s t p a r t i a l i n t e r a c t i v e cpu u t i l i z a t i o n . I t i s observed t h a t the o p t i m a l a d m i s s i o n p o l i c i e s f o r work l o a d s t h a t g i v e mean i n t e r a c t i v e response times c l o s e t o the lower bounds a r e v e r y s i m i l a r to each o t h e r . One would t h e r e f o r e e x p e c t t h a t a p o l i c y t h a t produces o p t i m a l performance f o r a g i v e n w o rkload to g i v e c l o s e t o o p t i m a l performance f o r a range o f workload c o n d i t i o n s ( e s p e c i a l l y when w i s l a r g e ) . I f i t i s a c t u a l l y the case then t h i s p r o p e r t y i m p l i e s t h a t i n p r a c t i c e we o n l y need to implement one s t a n d a r d p o l i c y f o r a range o f workload i n s t e a d o f one f o r each workload c o n d i t i o n . (Note: the s t a n d a r d p o l i c y i s dynamic i n the sense t h a t d e c i s i o n s a re made based on the c u r r e n t s t a t e o f the s y s t e m ) . We choose the p o l i c y i n t a b l e 4.14, which g i v e s o p t i m a l performance a t cpuT=0.4, cpuB=0.3; as the s t a n d a r d p o l i c y i n our example. The performances o f t h i s p o l i c y f o r d i f f e r e n t w o r k l o a d s a r e computed and compared w i t h the o p t i m a l v a l u e s (see T a b l e s 4 . 1 9 — 4 . 2 3 ) . I t i s observed t h a t the performances a r e q u i t e c l o s e t o the o p t i m a l performances i n a l l c a s e s . 42 CHAPTER V. CONCLUSIONS We proposed to a p p l y some o f the r e s u l t s and t e c h n i q u e s i n o p t i m a l s t o c h a s t i c c o n t r o l t h e o r y to a d p a t i v e performance c o n t r o l and o p t i m i z a t i o n o f computer systems. We e x e m p l i f i e d the a p p l i c a t i o n by a p p l y i n g the t h e o r y t o compute the o p t i m a l a d m i s s i o n p o l i c y which d e t e r m i n e s the o p t i m a l number o f j o b s from each c l a s s t h a t s h o u l d be a d m i t t e d depending on the c u r r e n t s t a t e o f the system f o r a combined b a t c h - i n t e r a c t i v e system. The o b j e c t i v e i s t o m i n i m i z e the mean weighted sum of the number of j o b s i n each c l a s s i n the system, E(w*Nl+N2), per u n i t t i m e . A m a t h e m a t i c a l model o f the system was developed and the t h e o r y a p p l i e d to compute the o p t i m a l a d m i s s i o n p o l i c y . The p o l i c y thus o b t a i n e d was shown to e x h i b i t the f o l l o w i n g p r o p e r t i e s : A) I t g i v e s good mean response time f o r i n t e r a c t i v e j o b s ( c l o s e t o the lower bounds i f s u f f i c i e n t l y l a r g e weight w i s choosen.) B) I t maximizes the t o t a l system t h r o u g h p u t . C) I t g u a r a n t e e s some minimun l e v e l o f b a t c h t h r o u g h p u t . D) A p o l i c y t h a t produces an o p t i m a l performance f o r a g i v e n w o rkload p r o v i d e s n e a r - o p t i m a l performance f o r a range o f d i f f e r e n t w o r kload c o n d i t i o n s , e s p e c i a l l y when w i s l a r g e . E) The q u a l i t y o f s e r v i c e g i v e n t o each c l a s s o f j o b s can be e a ' s i l y c o n t r o l l e d by c h o o s i n g some s u i t a b l e weight w. The major advantages o f a p p l y i n g the o p t i m a l s t o c h a s t i c 43 c o n t r o l t h e o r y t o a d a p t i v e performance c o n t r o l and o p t i m i z a t i o n of computer systems a r e : (1) the c o n t r o l p o l i c y so o b t a i n e d can be m a t h e m a t i c a l l y proved to g i v e o p t i m a l performance, (2) the c o n t r o l p o l i c y i s dynamic i n the sense t h a t c o n t r o l d e c i s i o n s a r e made based on the c u r r e n t system s t a t e , (3) once a s t o c h a s t i c model of a system has been developed i t can be used to determine o p t i m a l p o l i c i e s p e r t a i n i n g to d i f f e r e n t c r i t e r i a s i m p l y by u s i n g d i f f e r e n t o b j e c t i v e f u n c t i o n s i n the model. Weaknesses n e v e r t h e l e s s e x i s t . B e s i d e s the c o m p u t a t i o n a l i n e f f i c i e n c y when the number of system s t a t e s i s large" 1", the major weakness i s t h a t t h i s approach b a s i c a l l y produces n u m e r i c a l r e s u l t s . I t does not g i v e e x p l i c i t r e l a t i o n s h i p between the o p t i m a l p o l i c y and the parameters o f the system which i s v e r y d e s i r a b l e . T h i s i s i n h e r e n t i n the approach. The f o l l o w i n g are some s u g g e s t i o n s f o r f u t u r e r e s e a r c h which can be c o n s i d e r e d as e x t e n s i o n s t o t h i s work. The s t a t e o f the system i s d e f i n e d by the number of j o b s i n each c l a s s i n the system . T h i s t r a d i t i o n a l d e f i n i t i o n o f system s t a t e i s adopted because o f i t s s i m p l i c i t y . However the number o f j o b s i n the system does not d e s c r i b e the c o n g e s t i o n s of the system p r e c i s e l y s i n c e j o b s u s u a l l y have w i d e l y d i f f e r e n t r e s o u r c e demand c h a r a c t e r i s t i c s . T h e r e f o r e , the c o n t r o l p o l i c i e s o b t a i n e d by u s i n g the numbers of j o b as the system + T h i s i s not a s e r i o u s problem s i n c e the c o m p u t a t i o n o f the o p t i m a l p o l i c y needs t o be done o n l y once and does not have to be done i n r e a l t i m e . 44 s t a t e may not be as e f f e c t i v e as those based on some o t h e r q u a n t i t i e s which r e f l e c t the c o n g e s t i o n s o f the system more d i r e c t l y ( e . g . , r e s o u r c e u t i l i z a t i o n s , queue l e n g t h s , r e s o u r c e s e r i v c e r e q u e s t r a t e s , e t c . ) . I t i s l o g i c a l to extend t h i s work a l o n g the d i r e c t i o n o f d e f i n i n g the system s t a t e by those q u a n t i t i e s which l i n k more d i r e c t l y to the c o n g e s t i o n s or r e s o u r c e demands o f the system. More work must be done c o n c e r n i n g the a c t u a l i m p l e m e n t a t i o n . For example, the problems of ease o f i m p l e m e n t a t i o n , s t a b i l i t y , and time l a g s o f the c o n t r o l p o l i c y s h o u l d be taken i n t o c o n s i d e r a t i o n i n f u t u r e work. These problems may be d e a l t w i t h by u s i n g some o t h e r t e c h n i q u e s a v a i l a b l e i n o p t i m a l s t o c h a s t i c c o n t r o l t h e o r y . The overhead i n t r o d u c e d by the c o n t r o l p o l i c y s h o u l d a l s o be c a r e f u l l y s t u d i e d and taken i n t o c o n s i d e r a t i o n i n the o b j e c t i v e func i o n . F i n a l l y , the t h e o r y may be used to s t u d y o t h e r a s p e c t s o f he computing system i n c l u d i n g memory management and computer network f l o w c o n t r o l . FIGURES 4 . 1 ( a ) t o 4 . 9 ( a ) : _ N _ : Mean i n t e r a c t i v e r e s p o n s e t i m e (No c o n t r o l ) _ * _ : " " " " ( w i t h c o n t r o l ) _ B _ : Mean b a t c h r e s p o n s e t i m e (No c o n t r o l ) - + - : " " " " ( w i t h c o n t r o l ) : Lower bound o f m e a n i n t e r a t i v e r e s p o n s e t i m e F i g u r e s 4 . 1 ( b ) t o 4 . 9 ( b ) : : T o t a l s y s t e m t h r o u g h t r a t e s ( j o b s / s ) - * - i n t e r a c t i v e t h r o u g h p u t r a t e ( w i t h c o n t r o l ) _ I _ : " " " (No c o n t r o l ) - + - : B a t c h t h r o u h g p u t r a t e ( w i t h c o n t r o l ) B : " " " (NO c o n t r o l ) F i g . 4 . 0 L e g e n d f o r F i g u r e s 4 . 1 ( a ) t o 4 . 9 ( a ) a n d F i g u r e s 4 . 1 ( b ) t o 4 . 9 ( b ) 46 Q Sh N U N U H N a a 1 1 1 1 I 0.0 I.D 3.0 3.D 4.0 5.D WEIGHT c p u T = 0 . 3 , c p u B = 0 . 3 tfT=0.Q5, 0 B = O . l , M=60, N=6, m2 = 5 , b T = 0 . 0 1 8 b B = 0 . 0 1 2 , c B = 1 0 , c T = 2 0 , T I Q = 2 0 , B j 0 = 1 0 , F s = 3 0 , P s = 8 0 47 ca' oo a Q ID 3 Q_ X X a i O.D — I — 1.0 —1 1— Z.D ,3.0 WEIGHT 4.0 3.D cpuT = 0 . 3 , c p u B = 0 . 3 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 48 a a #1 in UJ ^ M M M M N q 3 R B B 3 jt ± t , 1 1 1 1 O.S l .D 2.0 3.D 4.0 5.D WEIGHT fid, H. c p u T = 0 . 3 , c p u B = 0 . 5 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 49 01 fib Jf-.Z(h) c p u T = 0 . 3 , cpuB = 0 . 5 F o r o t h e r p a r a m e t e r v a l u e s , . s e e F i g . 4 . 1 ( a ) 50 Q Pi UJ in N N N H ^ N R R R B 3 5 ± * * + 1 r— 1 1 1 0.0 l .D 2.0 3.D 4.0 5.D WEIGHT fl(jA.3(CL) c p u T = . 0 . 3 , c p u B = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 51 cn a a ZD Q_ X (_3 cca X en a a' a * * M * * * * p p ff n p 1 — 1 1 1 1 0.0 I.D 2.0 3.D 4 .0 2.0 WEIGHT H6). 4.3<L) c p u T = 0 . 3 , cpuB = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4.1(a) 52 a 1 j.o c p u T = 0 . 5 , cpuB = 0 . 3 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 53 cn a 03 a Q 3 Q_ X LO §34 ceo X 0.0 J I 1 I ] 1 3 i B - 1 — I.D Z.D 3 .0 WEIGHT 4.0 3.0 Tib. t.H(k>) c p u T = 0 . 5 , cpuB = 0 . 3 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 54 c p u T = 0.5, c p u B = 0.5 . F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 55 cn d' 03 d' d ZD CL X LO CCQ X J ] I p » B_ 0.0 1-0 I T Z.D 3.0 WEIGHT A.O 5.D hi6. *k£(L) c p u T = 0 . 5 , cpuB = 0 . 5 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 56 CO cn' 03 ad' m yr ID CO in 03 bl bl y H N N B 3 B B 3 B T ~ l 1 0.0 l.D —I ? 1 1 2.0 3.0 4.0 5.0 WEIGHT c p u T = 0 . 5 , cpuB = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 57 X era x a * * ¥ ¥ ¥ * fi ^ fi B B y 1 1 1 1 1 0.0 1.0 2.0 3.0 4.0 3.0 WEIGHT fid- *h6tt>) c p u T = 0 . 5 , c p u B = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g 4 . 1 ( a ) 58 q C/I Q US a oa' O.o t.o 2.0 _ 3.0 WEJGHT c p u T = 0 . 7 , c p u B = 0 . 3 i — 4.0 S.D F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g , 4 . 1 ( a ) 59 cn ca' oa r-d' co Z3 CL X c t a ^ X I N a' 0.0 J * * * J I I I I I ft—JB 1 3 B _p - 1 — l . D —I 1— 2.0 3.0 WEIGHT 4.0 c p u T = 0 . 7 , cpuB = 0 . 3 3.0 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 60 Q4 10 en' o •<n" UJ U3 tri R R /B B B B -I— l.D —I 1 1 1 2.0 3.0 4.0 5.0 WEIGHT 0.0 c p u T = 0 . 7 , c p u B = 0 . 5 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 61 ZJ Q_ X L3 tt.a X d d 0.0 i d f c d f HI W—SI B B ft 1.0 i 1— 2.0 3.0 WEIGHT — i — 4.0 ~1 3.0 PIG. +.8(t>) c p u T = 0 . 7 , cpuB = 0 . 5 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 62 oa io' to to UJ UJ Er.. a. in in' o.o - 1 — 1.0 —I 1— 2.0 3.0 "WEIGHT —i— 4.0 —I 3.0 H6f. 4.1 (CL) c p u T = 0 . 7 , cpuB = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g 4.2 ( a ) 63 cn ca" oo d ' ca' 10 a " 3 a. x ID C t a X a I N d ¥ * ¥ —i 1 1 1 1 1.0 2.0 3.0 4.0 3.0 WEIGHT 0.0 c p u T = 0 . 7 , cpuB = 0 . 7 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) y : Mo c o n t r o l • * - - * : w i t h c o n t r o l p r - 1 I 3 . 0 6 . 0 9 . 0 1 2 . 0 NO. OF J N T E R R C T I V E J O B F I G . 4 . 1 0 c p u T = 0 . 3 , c p u B = 0 . 3 F o r o t h e r p a r a m e t e r v a l u e s , s e e F i g . 4 . 1 ( a ) 65 In t a b l e s (4.1) to ( 4 . 1 7 ) , e n t r y ( I , J ) c o r r e s p o n d s to the system s t a t e w i t h J - l batch and I - l i n t e r a c t i v e j o b s . The t u p l e (x,y) r e p r e s e n t s the c o n t r o l d e c i s i o n (Admits x i n t e r a c t i v e and y b a t c h j o b s i n t o the memory l o o p . ) . A l l the t a b l e s have the f o l l o w i n g parameter v a l u e s : jrfT = 0.05, jrfB = 0.1, Y = 60, N = 6, m2 = 5, b T=0.018, b B =0.012, c B = 10, c T = 20, T I 0 = 20, B I 0 = 10, F s = 30, P s = 80. Mean i n t e r a c t i v e response time w i t h o u t c o n t r o l = 66.97 Mean b a t c h t u r n around time w i t h o u t c o n t r o l = 33.32 Throughput o f i n t e r a c t i v e j o b w i t h o u t c o n t r o l = 0.0690 Throughput o f b a t c h j o b w i t h o u t c o n t r o l = 0.0669 WEIGHT =1.0 Opti m a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (0,2) (0,3) (0,4) (0,4) (2,0) (2,1) (0,2) (0,3) (0,4) (0,4) (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) ***************************************** Mean i n t e r a c t i v e response time = 29.35 Mean b a t c h t u r n around time = 10.72 Throughput r a t e o f i n t e r a c t i v e j o b = 0.1216 Throughput r a t e o f b a t c h j o b = 0.0990 Tab l e (4.1) Optimal A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 66 WEIGHT =1.5 Optim a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (0,3) (0,4) (0,4) (2,0) (2,1) (1,2) (0,3) (0,4) (0,4) I (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) ***************************************** T a b l e (4.2) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 WEIGHT =2.0 Opt i m a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (0,3) (0,4) (1,3) (2,0) (2,1) (1,2) (0,3) (0,4) (1,3) I (3,0) (2,1) (1,2) (0,3) (0,4) (1,3) (4,0) (2,1) (1,2) (0,3) (0,4) (1,3) (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) (3,0) (2,1) (1,2) (0,3) (0,4) (1,3) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 27.56 = 11.83 = 0.1262 = 0.0988 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 27.50 = 11.91 = 0.1263 = 0.0986 Ta b l e (4.3) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 67 WEIGHT = 2.5 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (0,3) (0,4) (1,2) (2,0) (2,1) (1,2) (0,3) (0,4) (2,0) I (3,0) (2,1) (1,2) (1,3) (0,4) (3,0) (3,0) (2,1) (1,2) (1,3) (1,3) (3,0) (3,0) (2,1) (1,2) (1,3) (1,3) (3,0) (3,0) (2,1) (1,2) (1,3) (1,3) (3,0) ***************************************** Table (4.4) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 WEIGHT =3.0 Optim a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (1,3) (1,2) (2,0) (2,1) (2,2) (1,3) (2,1) (2,0) I (3,0) (2,1) (2,2) (2,2) (3,0) (3,0) (3,0) (2,1) (2,2) (3,0) (3,0) (3,0) (3,0) (2,1) (2,2) (3,0) (3,0) (3,0) (3,0) (2,1) (2,2) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 22.95 = 17.88 = 0.1397 = 0.0844 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 16.96 = 30.07 = 0.1623 = 0.0609 Ta b l e (4.5) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 68 WEIGHT =3.5 Optim a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (1,2) (1,1) (2,0) (2,1) (2,2) (2,1) (2,1) (2,0) I (3,0) (2,1) (3,0) (3,0) (3,0) (3,0) (3,0) (3,1) (3,0) (3,0) (3,0) (3,0) (3,0) (3,1) (3,0) (3,0) (3,0) (3,0) (3,0) (3,1) (3,0) (3,0) (3,0) (3,0) ***************************************** T a b l e (4.6) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.3, cpuB=0.3 WEIGHT =2.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,2) (1,2) (1,1) (2,0) (2,1) (2,1) (2,1) (2,0) (2,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 14.82 = 36.48 = 0.1723 = 0.0485 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 7.55 = 34.92 = 0.2178 = 0.0598 Tab l e (4.7) Optimal A d m i s s i o n P o l i c y w i t h cpuT=0.5, cpuB=0.2 69 WEIGHT = 2.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (1,3) (1,2) (2,0) (2,1) (2,2) (2,2) (2,1) (2,0) I (3,0) (3,1) (2,2) (3,0) (3,0) (3,0) (3,0) (3,1) (2,2) (3,0) (3,0) (3,0) (3,0) (3,1) (2,2) (3,0) (3,0) (3,0) (3,0) (2,1) (2,2) (3,0) (3,0) (3,0) ***************************************** T a b l e (4.8) Optimal A d m i s s i o n P o l i c y w i t h cpuT=0.5, cpuB=0.3 WEIGHT =2.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (0,4) (1,2) (2,0) (2,1) (2,2) (1,3) (1,3) (2,0) I (3,0) (3,1) (2,2) (1,3) (1,3) (3,0) (3,0) (3,1) (2,2) (1,3) (2,2) (3,0) (3,0) (2,1) (2,2) (1,3) (2,2) (3,0) (3,0) (2,1) (2,2) (1,3) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b = 8.80 = 21.00 = 0.2083 = 0.0841 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b 9. 65 10.66 0.2023 0.0965 T a b l e (4.9) Opt i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.5, cpuB=0.4 70 WEIGHT = 2.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (0,4) (1,3) (2,0) (2,1) (2,2) (1,3) (0,4) (2,1) I (3,0) (3,1) (2,2) (1,3) (0,4) (3,0) (3,0) (2,1) (2,2) (1,3) (0,4) (3,0) (3,0) (2,1) (1,2) (0,3) (0,4) (3,0) (3,0) (2,1) (1,2) (1,3) (0,4) (2,2) ***************************************** T a b l e (4.10) Op t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.5, cpuB=0.5 WEIGHT = 2.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (0,4) (1,3) (2,0) (2,1) (2,2) (1,3) (0,4) (0,4) I (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) (3,0) (2,1) (1,2) (1,3) (0,4) (0,4) (3,0) (2,1) (1,2) (1,3) (0,4) (1,3) (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b 9. 02 7. 25 0.2067 0.0992 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b 8.55 5. 36 0.2101 0.0999 T a b l e (4.11) O p t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.5, cpuB=0.6 71 WEIGHT =3.5 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,2) (1,2) ' (1,0) (2,0) (2,1) (2,1) (2,0) (2,0) (2,0) I (3,0) (3,1) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time = 23.84 Mean b a t c h t u r n around time = 48.66 Throughput r a t e o f i n t e r a c t i v e j o b = 0.1369 Throughput r a t e o f b a t c h j o b = 0.0068 Lower bound o f i n t e r a c t i v e response time = 23.68 Tab l e (4.12) Op t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.2, cpuB=0.2 WEIGHT = 9.0 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,2) (1,2) (1,1) (2,0) (2,1) (2,1) (2,1) (2,1) (2,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time = 24.53 Mean b a t c h t u r n around time = 41.58 Throughput r a t e o f i n t e r a c t i v e j o b = 0.1347 Throughput r a t e o f b a t c h j o b = 0.0303 Lower bound o f i n t e r a c t i v e response time = 23.68 Ta b l e (4.13) Op t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.2, cpuB=0.5 72 WEIGHT =3.5 Optim a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (1,2) (1,1) (2,0) (2,1) (2,1) (2,1) (2,0) (2,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** T a b l e (4.14) Optimal A d m i s s i o n P o l i c y w i t h cpuT=0.4, cpuB=0.3 WEIGHT =3.5 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,2) (1,1) (1,0) (2,0) (2,0) (2,0) (2,0) (2,0) (2,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ° (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b Lower bound o f i n t e r a c t i v e response time = 9.96 = 30.91 = 0.2002 = 0.0653 = 8.64 Mean i n t e r a c t i v e response time Mean b a t c h t u r n around time Throughput r a t e o f i n t e r a c t i v e j o b Throughput r a t e o f b a t c h j o b Lower bound o f i n t e r a c t i v e response time = 5.42 = 34.61 = 0.2360 = 0.0596 = 4.93 Ta b l e (4.15) Op t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.6, cpuB=0.2 73 WEIGHT =3.5 Optimal p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,2) (1,3) (1,3) (1,2) (2,0) (2,1) (2,1) (2,1) (2,1) (2,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time = 5.73 Mean b a t c h t u r n around time = 8.75 Throughput r a t e o f i n t e r a c t i v e j o b = 0.2332 Throughput r a t e o f b a t c h j o b = 0.0978 Lower bound o f i n t e r a c t i v e response time = 4.93 Ta b l e (4.16) Op t i m a l A d m i s s i o n P o l i c y w i t h cpuT=0.6, cpuB=0.6 WEIGHT =9.0 Optim a l p o l i c y i s * * * * * * * * * * * * * * * * * * * * * j * * * * * * * * * * * * * * * * * (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) (1,0) (1,1) (1,1) (1,2) (1,1) (1,1) (2,0) (2,0) (2,0) (2,0) (2,0) (2,0) I (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) (3,0) ***************************************** Mean i n t e r a c t i v e response time = 5.17 Mean b a t c h t u r n around time = 6.97 Throughput r a t e o f i n t e r a c t i v e j o b = 0.2383 Throughput r a t e o f b a t c h j o b = 0.0984 Lower bound o f i n t e r a c t i v e response time = 4.93 Ta b l e (4.17) Optimal A d m i s s i o n P o l i c y w i t h cpuT=0.6, c p u B = l . l 74 0 1 2 3 4 5 0 0. 0 0. 0 0. 0 0. 0 0. 0 0. 0 0. 0 0. 5352 0. 7495 0. 8386 0. 8689 0. 8640 1 0. 4872 0. 3379 0. 24 54 0. 1824 0. 1359 0. 0993 0. 0 0. 3832 0. 5703 0. 6624 0. 6986 0. 6924 2 0. 6779 0. 4946 0. 3671 0. 2711 0. 1956 0. 1225 0. 0 0. 2917 0. 4496 0. 5298 0. 5553 0. 5048 3 0. 7483 0. 5544 0. 4059 0. 2894 0. 1799 0. 1243 0. 0 0. 2292 0. 3573 0. 4175 0. 4013 0. 3803 4 0. 7449 0. 5404 0. 3810 0. 2356 0. 1633 0. 1090 0. 0 0. 1008 0 . 2790 0. 2994 0. 3024 0. 2752 5 0. 6750 0. 4711 0. 2900 0. 2017 0. 1352 0. 1218 0. 0 0. 1399 0. 1987 0. 2257 0. 2193 0. 2479 6 0. 5599 0. 3436 0. 2396 0. 1611 0. 1453 0. 0937 0. 0 0. 0990 0. 1498 0. 1638 0. 1977 0. 1716 Table 4.18 CPU u t i l i z a t i o n U>p(ni,n2) , e n t r y (ni,n2) U B ( n l r n 2 ) c o r r e s p o n d s to t h e r e a re n j i n t e r a c t i v e and n 2 b a t c h j o b s i n the memory l o o p . Y=60 b T=0.018 b B=0.012 c T=20 c B=10 F s=30 P s=80 75 TW = i n t e r a c t i v e response time w i t h o u t c o n t r o l TO = " " " w i t h o p t i m a l c o n t r o l TS = " " " w i t h s u b o p t i m a l c o n t r o l PW = t o t a l t hroughput w i t h o u t c o n t r o l PO = " " w i t h o p t i m a l c o n t r o l PS = " " w i t h s u b o p t i m a l c o n t r o l BO = ba t c h throughput w i t h o p t i m a l c o n t r o l BS = " " w i t h s u b o p t i m a l c o n t r o l cpuT=0.2 cpuB| 0.1 |0.2 I 0.3 | 0.4 | 0.5 | 0.6 TW I 24 3 I 192 135 93 68 .9 55 .4 TO I 23. 6 I 23.6 23. 7 23 .8 24 .5 26 . 6 TS I 24.3 I 24.4 24.5 24 . 5 24 . 6 24 .8 PW I 0.043 I 0.0695 0.099 0. 129 0. 153 0. 171 PO I 0.141 I 0.143 0.146 0. 150 1 o. 165 0. 185 PS I 0.141 I o.l47 0.154 0. 160 1 o. 165 0. 180 BO I 0.003 I 0.0054 0.0087 1 0. 0134 1 o. 0303 0. 057 BS I 0.006 I 0.0127 0.0193 0. 0254 1 o. 0306 1 0. 051 T a b l e 4.19 C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o o p t i m a l p o l i c i e s under d i f f e r e n t w o r k l o a d s 76 cpuT=0.3 cpuB | 0.1 0.2 0 .3 0 .4 0 .5 0 . 6 TW | 147.6 106.9 67 . 0 43 . 5 31 .8 25 .8 TO | 13.1 13.4 14 .8 19 .8 19 . 4 25 .8 TS | 14.0 14. 2 14 . 3 14 . 3 14 . 3 14 . 2 PW | 0.0578 0.0926 0. 136 0. 177 0. 217 0. 226 PO | 0.190 0. 201 0. 221 0. 243 0. 253 0. 257 1 PS | 0.191 0.205 I o. 219 0. 230 0. 238 1 o. 244 1 BO | 0.0085 I 0.0204 1 o. 0485 I o. 0894 1 o. 0997 1 o. 099 1 BS | 0.0149 | 0.0308 1 o. 0448 1 o. 0556 1 o. 0634 1 o. 069 Table 4.20 C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o o p t i m a l p o l i c i e s under d i f f e r e n t w o rkloads cpuT=0.4 cpuB | 0.1 0 .2 0 .3 0 .4 0 .5 0 .6 TW | 100. 5 66 . 1 37 .9 24 . 2 17 m 9 14 .9 .TO I 8.6 8. 9 10 . 0 10 . 3 11 .8 11 . 5 TS | 9.6 9. 9 10 .0 10 . 0 9. 8 9. 7 PW | 0.0737 0. 120 0. 177 0. 224 0. 252 0. 269 PO | 0. 225 0. 242 0. 266 0. 279 0. 284 0. 289 PS | 0. 226 1 o. 248 0. 265 0. 277 0. 284 1 o. 289 BO | 0.0152 1 o. 0354 1 o. 0653 0. 0807 0. 095 1 o. 099 1 BS | 0.0238 1 o. 0475 1 o. 0653 1 o. 0763 1 o. 0828 1 o. 0869 Table 4.21 C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o o p t i m a l p o l i c i e s under d i f f e r e n t w o r k l o a d s 77 cpuT=0.5 CpuB | 0.1 0.2 0.3 0 .4 0.5 0.6 TW I 72.8 43.6 23.7 15 . 2 11.6 9.9 TO | 6.3 6.7 7.6 7. 6 7.4 7.3 TS | 7.4 7.6 7.6 7. 5 7.3 7.2 PW | 0. 091 I 0.150 0. 217 0. 262 ! 0.287 0. 298 PO | 0. 250 I 0.273 0.295 0. 306 I 0.312 0.315 PS | 0. 250 I 0.277 0.295 1 o. 305 I 0.311 0.314 BO | 0.0221 I 0.0491 I 0.077 1 o. 089 I 0.0937 1 0.095 BS | 0.0314 | 0.0602 I 0.0780 1 o. 0871 I 0.0917 I 0.0942 Table 4.22 C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o o p t i m a l p o l i c i e s under d i f f e r e n t w o r k l o a d s cpuT=0.6 cpuB | 0.1 0.2 0.3 0.4 0.5 0.6 TW | 54.8 30.3 16.1 10.6 8.7 7.3 TO | 4.9 5.4 5.6 5.9 5.8 5.7 TS | 6.0 6.2 6.1 6.0 5.8 5.7 PW | 0.109 0.180 0.250 0.290 0.308 0.318 PO | 0. 268 0.296 0.313 0.324 0.328 0.330 PS | 0. 268 0.298 0.315 1 0.323 ! 0.328 0.330 BO | 0.0280 0.0596 0.0788 I 0.0923 [ 0.0963 0.098 BS | 0.0375 I 0.0690 I 0.0854 I 0.0924 I 0.0956 I 0.097 Table 4.23 C o m p a r i s i o n o f the performance o f the s t a n d a r d a d m i s s i o n p o l i c y t o o p t i m a l p o l i c i e s under d i f f e r e n t w o r k l o a d s 78 REFERENCE [1] M. B a d e l , E. Gelenbe, J . L e r o u d i e r , D. P o t i e r , " A d a p t i v e o p t i m i z a t i o n o f a T i m e s h a r i n g System's Performance," P r o c . IEEE 63, 1975, 958-965. [2] M. B a d e l , J . L e r o u d i e s , " A d a p t i v e multiprogramming Systems can e x i s t , " Performance o f Computer I n s t a l l a t i o n s , D. F e r r a r i ( e d . ) , N o r t h - h o l l a n d , 1978, 115-135. [3] F. B a s k e t t , K. Chandy, R. Muntz, J . Polaius-Gomez, " OPen, C l o s e d , and Mixed Networks o f Queues w i t h d i f f e r e n t c l a s s e s o f customers," J . ACM, 1975, 248-260. [4] D. P. B e r t r e k a s , Dynamic Programming and S t o c h a s t i c C o n t r o l , New York: Academic P r e s s , 1976. [5] H. Brandwajn, J . Hernandez, "A s t u d y o f a Mechanism f o r C o n t r o l l i n g Multiprogrammed Memory i n an I n t e r a c t i v e Systems," Performance o f Computer Systems, M. A r a t o , A. Butr i m e n k o , E. Gelenbe ( e d s . ) , N o r t h - H o l l a n d , 1979, 487-500. [6] R. S. B r i c e , J . Browne, "Feedback Couple Resource A l l o c a t i o n P o l i c i e s i n the Mu l t i p r o g r a m m i n g -M u l t i p r o c e s s o r Computer Systems," Comm. ACM 21,8 (August 1978), 678-686. [7] R. Bunt, J . Hume, " A d a p t i v e P r o c e s s o r S c h e d u l i n g Based on A p p r o x i m a t i n g Demand D i s t r i b u t i o n , " INFOR, V o l . 15,no. 2, June 1977, 135-147. [8] J . P. Buzen, "Fundamental O p e r a t i o n a l Laws o f Computer System Performance," A c t a I n f o r m a t i c a 7, 1976, 167-182. [9] J . P. Buzen, " C o m p u t a t i o n a l A l g o r i t h m s f o r C l o s e d Queueing Networks w i t h E x p o n e n t i a l S e r v e r s , " Comm. ACM 16,9 (Sept. 1973), 527-531. 79 [10] D. C h a m b e r l i n , S. F u l l e r , L. L i u , "An A n a l y s i s o f page a l l o c a t i o n s t r a t e g i e s f o r V i r t u a l Memory Systems," IBM J . Res. Develop., V o l . 17, 1973, 404-412. [11] P. C o u r t o i s , " D e c o m p o s a b a l i t y , I n s t a b i l i t y and S a t u r a t i o n i n Multiprogramming Systems," Comm. ACM 18, 7 ( J u l y 1975), 371-377. [12] P. C o u r t o i s , D e c o m p o s i b i l i t y - Queueing and Computer System A p p l i c a t i o n s , New York: Academic P r e s s , 1977. [13] P. J . Denning, K. C. Kahn, J . L e r o u d i e r , D. P o t i e r , R. S u r i , "OPtimal M u l t i p r o g r a m m i n g , " Acta I n f o r m a t i c a , V o l . 7,no. 2, 1976, 197-216. [14] P. J . Denning, " T h r a s h i n g : I t s causes and p r e v e n t i o n , " P r o c . AFIPS 1968 FJCC 33,915-922. [15] P. J . Denning, "Working s e t s p a s t and p r e s e n t , " IEEE T rans. On Software E n g i n e e r i n g , V o l . SE-6, N o . l , 1980, 64-84. [16] p. J . Denning, S. Graham, "Multiprogrammed Memory Management," P r o c . IEEE 63, 1975, 924-939. [17] D. F e r r a r i , Computer Systems Performance  E v a l u a t i o n , Englewood C l i f f s , N J : P r e n t i c e - H a l l , 1978. [18] E. Gelenbe, R.R. Muntz, " P r o b a b i l i s t i c Models o f Computer Systems - P a r t I - (Exact R e s u l t s ) , " Acta I n f o r m a t i c a 7, 1976. [19] E. Gelenbe, A. K u r i n c k x , I . M i t r a n i , "The r a t e c o n t r o l p o l i c y f o r V i r t u a l Memory Management," O P e r a t i n g Systems: Theory and P r a c t i c e , D. L a n c i a u x ( e d . ) , N o r t h - H a l l a n d , 1979, 247-264. [20] E. Gelenbe, A. K u r i n c k x , "Random I n j e c t i o n C o n t r o l of Multiprogramming i n V i r t u a l Memory," IEEE T r a n s . On Software E n g i n e e r i n g 4, 1978, 2-17. 80 [21] G. S. Graham, P.J. Denning, "ON the r e l a t i v e C o n t r o l l a b i l i t y of memory p o l i c i e s , " Computer Performance, K. Chandy, and M. R e i s e r ( e d s . ) , N o r t h - H a l l a n d , 1977, 411-428. [22] J . H. Hine, I . M i t r a n i , S. T s u r , "The c o n t r o l o f Response Times i n M u l t i - c l a s s Systems by Memory A l l o c a t i o n , " Comm. ACM 22,7 ( J u l y 1979), 415-423. [23] L. K l e i n r o c k , " C e r t a i n a n a l y t i c r e s u l t s f o r tim e s h a r e d p r o c e s s o r s , " P r o c . I F I P Congress 68, N o r t h - H o l l a n d 1968, 838-845. [24] P. S. K r i t z i n g e r , A. E. K r z e s i n s k i , P. T e u n i s s e n , "Design of a C o n t r o l System f o r a t i m e s h a r i n g Computer System," Performance o f Computer I n s t a l l a t i o n s , D. F e r r a r i ( e d . ) , N o r t h - H o l l a n d , 1978, 103-114. [25] C. E. Landwehr, "An endogenous p r i o r i t y model f o r Load C o n t r o l i n combined B a t c h - I n t e r a c t i v e Computer Systems," Acta I N f o r m a t i c a , V o l . 7 no.2 ,1976, 153-166. [26] A. L. Schoute, "Comparison o f G l o b a l Memory Management S t r a t e g i e s i n V i r t u a l Memory Systems w i t h two c l a s s e s o f P r o c e s s e s , " M o d e l l i n g and Performance E v a l u a t i o n o f Computer Systems, E. Gelenbe, ed. N o r t h - H o l l a n d , 1976 389-414. [27] M. R e i s e r , H. K o b a y a s h i , "Queueing Networks w i t h M i l t ' i p l e C l o s e d C h a i n s : Theory and Co m p u t a t i o n a l A l g o r i t h m s , " IBM J . Res. Develop. 19,3 (may 1975), 283-294. [28] J . R o d r i g u e z - R o s e l l , J . P. Dupuy, "The d e s i g n , Implementation , and e v a l u a t i o n o f a Working s e t d i s p a t c h e r , " Comm. ACM 17,1973, 247-253. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051803/manifest

Comment

Related Items