Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A state-dependent policy for computer system load regulation Wong, William Chun Mun 1984

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

Item Metadata

Download

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

Full Text

A S T A T E - D E P E N D E N T P O L I C Y FOR COMPUTER SYSTEM LOAD REGULATION by W I L L I A M CHUN MUN WONG B . S c , T h e 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 , 1982 A T H E S I S SUBMITTED I N P A R T I A L F U L F I L M E N T OF THE REQUIREMENTS FOR T H E DEGREE OF MASTER OF S C I E N C E i n THE F A C U L T Y OF GRADUTE S T U D I E S ( D E P A R T M E N T OF COMPUTER S C I E N C E ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE U N I V E R S I T Y OF B R I T I S H COLUMBIA May 1984 © W i l l i a m Chun Mun Wong , 1984 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 o f t h e r e q u i r e m e n t s f o r an 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 o f 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 f o r 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 f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r 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 h e a d o f my d e p a r t m e n t o r b y h i s o r h e r 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 o r p u b l i c a t i o n o f 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 o f Computer Science  T h e 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 1956 Main M a l l V a n c o u v e r , C a n a d a V6T 1Y3 i i A b s t r a c t One o f t h e p r i n c i p a l i d e a s b e h i n d m u l t i p r o g r a m m i n g i s t o make more e f f e c t i v e u se o f t h e s y s t e m r e s o u r c e s . H o w e v e r , i n o r d e r t o a v o i d e x c e s s i v e i n t e r a c t i o n s among t h e c o m p e t i n g j o b s , w h i c h w i l l r e s u l t i n g e n e r a l d e g r a d a t i o n o f s y s t e m p e r f o r m a n c e , t h e number a n d c o m p o s i t i o n o f j o b s i n t h e m u l t i p r o g r a m m i n g s e t s h o u l d be c a r e f u l l y c o n t r o l l e d . T h i s i s t h e f u n c t i o n o f t h e l o a d - c o n t r o l p o l i c y . A g o o d l o a d - c o n t r o l p o l i c y s h o u l d be a d a p t i v e t o work l o a d v a r i a t i o n . A l o a d - c o n t r o l p o l i c y b a s e d on a m a t h e m a t i c a l m o d e l h a s many a d v a n t a g e s i n c l u d i n g : 1) T h e e f f e c t on p e r f o r m a n c e due t o s y s t e m a n d / o r work l o a d c h a n g e s c a n be r e a d i l y a n a l y z e d . 2) I t i s e a s y t o a d o p t d i f f e r e n t o p t i m i z a t i o n c r i t e r i a by c h o o s i n g s u i t a b l e o b j e c t i v e f u n c t i o n s . 3) T h e l o a d - c o n t r o l p o l i c y i s a d a p t i v e i f t h e o b j e c t i v e f u n c t i o n i s c h o s e n t o be a f u n c t i o n o f t h e s t a t e o f t h e s y s t e m . I n [ 1 1 ] , C h a n s o n a n d L o d e s c r i b e d an a d a p t i v e l o a d - c o n t r o l p o l i c y b a s e d on s t o c h a s t i c c o n t r o l t h e o r y . The c o m p u t e r s y s t e m i s m o d e l l e d a s a q u e u e i n g n e t w o r k w i t h two c l a s s e s o f j o b s -b a t c h a n d i n t e r a c t i v e . T h e p o l i c y d e t e r m i n e s t h e number o f j o b s o f e a c h t y p e t o be a c t i v a t e d f o r e x e c u t i o n a t e a c h s y s t e m s t a t e w h i c h i s d e f i n e d t o be t h e t o t a l number o f j o b s o f e a c h c l a s s i n t h e s y s t e m ( t h o s e e x e c u t i n g p l u s t h o s e w a i t i n g t o be a c t i v a t e d ) . T h e o b j e c t i v e i s t o m i n i m i z e a w e i g h t e d sum o f t h e number o f j o b s i n t h e s y s t e m . I t was shown t h a t t h e mean r e s p o n s e t i m e a n d t h r o u g h p u t r a t e o f t h e s y s t e m i m p r o v e s i g n i f i c a n t l y o v e r t h o s e i n t h e c a s e o f no l o a d c o n t r o l . T h i s t h e s i s e x t e n d s t h e r e s u l t s i n [ 1 1 ] . T h e m o d e l i s g e n e r a l i z e d t o " S " c l a s s e s o f j o b s i n s t e a d o f t w o . T h e s y s t e m s t a t e i s a l s o r e f i n e d by t a k i n g i n t o c o n s i d e r a t i o n o f t h e j o b s w a i t i n g t o be a c t i v a t e d a s w e l l a s t h o s e t h a t a r e e x e c u t i n g . T h i s e l i m i n a t e s t h e p o s s i b i l i t y t h a t t h e c o m p u t e d number o f j o b s t o be a c t i v a t e d i n a c l a s s i s l e s s t h a n t h e number o f e x e c u t i n g j o b s i n t h a t c l a s s . I t i s a l s o shown t h a t t h i s p o l i c y p e r f o r m s b e t t e r t h a n t h e one d e s c r i b e d i n [11] a t t h e e x p e n s e o f h i g h e r c o m p u t a t i o n a l o v e r h e a d . i v T a b l e o f C o n t e n t s A b s t r a c t i i T a b l e o f C o n t e n t s i v L i s t o f T a b l e s v L i s t o f F i g u r e s . v i A c k n o w l e d g e m e n t s v i i C H A P T E R I . INTRODUCTION 1 1.1 T h e Need F o r G o o d A d a p t i v e L o a d C o n t r o l P o l i c y 1 1.2 S u r v e y Of A d a p t i v e P e r f o r m a n c e I m p r o v e m e n t P o l i c i e s . 1 1.3 M o t i v a t i o n A n d G o a l 5 CHAPTER I I . OPTIMAL S T O C H A S T I C CONTROL THEORY 7 2.1 T h e B a s i c P r o b l e m 7 2 . 2 C o n d i t i o n F o r The E x i s t e n c e Of O p t i m a l S t a t i o n a r y P o l i c y 9 2 . 2 . 1 F i n i t e Mean P a s s a g e T i m e C o n d i t i o n 9 2 . 2 . 2 Weak A c c e s s a b i 1 i t y C o n d i t i o n 10 2 . 2 . 3 E x i s t e n c e R e s u l t 1.1 2 . 3 P o l i c y I t e r a t i o n A l g o r i t h m 12 2 . 4 C o m p u t a t i o n a l C o s t 15 CHAPTER I I I . THE SYSTEM D E S C R I P T I O N 17 3.1 M o d e l D e s c r i p t i o n 17 3 . 2 T h e 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 N e t w o r k . . 20 3 . 3 F o r m u l a t i o n Of T h e O p t i m a l C o n t r o l P r o b l e m 34 3 . 4 C o m p u t a t i o n a l C o s t 37 3 . 4 . 1 C o m p u t a t i o n a l T i m e 37 3 . 4 . 2 Memory R e q u i r e m e n t 40 CHAPTER I V . I N T E R P R E T I N G THE R E S U L T S 41 4 .1 T h e E f f e c t s Of W o r k l o a d 43 4 . 2 T h e E f f e c t Of T h e W e i g h t 44 4 . 3 T h e D o m a i n Of T h e P o l i c y 45 4 . 4 T h e E r r o r In The S o l u t i o n 45 CHAPTER V . CONCLUSION 4 6 B I B L I O G R A P H Y 81 V L i s t o f T a b l e s T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e T a b l e 4 . 0 ) C p u u t i l i z a t i o n 48 4 . 1 . 1 ) S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t 4 . 2 . 1 4 . 2 . 2 4 . 3 . 1 4 . 3 . 2 4 . 4 . 1 4 . 4 . 2 4 . 5 . 1 4 . 5 . 2 4 . 6 . 1 4 . 6 . 2 4 . 7 . 1 4 . 7 . 2 4 . 8 . 1 4 . 8 . 2 l o a d c o n t r o l w i t h c p u T = 0 . 3 , c p u B = 0 . 3 50 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 3 , c p u B = 0 . 3 , W=1 . . 5 1 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 3 , c p u B = 0 . 3 , W=2 , . 5 2 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 3 , c p u B = 0 . 3 , W=3 . . 5 3 A d m i s s i o n p o l i c y w i t h c p u T = 0 „ 3 , c p u B = 0 . 3 , W=5 . . 5 4 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 3 , c p u B = 0 . 3 , W=5f) . 5 5 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 3 , c p u B = 0 . 7 56 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 3 , c p u B = 0 . 7 , W=1 . . 5 7 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 5 , c p u B = 0 . 3 . 5 8 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 5 , c p u B = 0 . 3 , W=1 . . 5 9 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 5 f c p u B = 0 . 2 . . . . . . . 6 0 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 5 , c p u B = 0 . 2 , W=1 . . 6 1 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 5 , c p u B = 0 . 4 . . . . . . . 6 2 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 5 , c p u B = 0 . 4 , W= 1 . . 6 3 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 5 r c p u B = 0 . 5 . . . . . . . 6 4 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 5 , c p u B = 0 . 5 , W=1 . . 6 5 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t , r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 2 , c p u B = 0 . 2 . . . . . . . 6 6 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 2 , c p u B = 0 . 2 , W=1 . . 6 7 S y s t e m r e s p o n s e t i m e a n d t h r o u g h p u t r a t e w i t h o u t l o a d c o n t r o l w i t h c p u T = 0 . 2 , c p u B = 0 . 5 68 A d m i s s i o n p o l i c y w i t h c p u T = 0 . 2 , c p u B = 0 . 5 , W=1 . . 6 9 v i L i s t o f F i g u r e s F i g u r e 4 . 1 . 1 T h r o u g h p u t r a t e v e r s u s W f o r c p u T = 0 . 3 , c p u B - 0 . 3 , 71 F i g u r e 4 . 1 . 2 R e s p o n s e t i m e v e r s u s W f o r c p u T = 0 . 3 , c p u B = 0 . 3 , 72 F i g u r e 4 . 2 . 1 T h r o u g h p u t r a t e v e r s u s W f o r c p u T = 0 . 3 , c p u B = 0 . 7 , 73 F i g u r e 4 . 2 . 2 R e s p o n s e t i m e v e r s u s W f o r c p u T = 0 . 3 , c p u B = 0 . 7 , 74 F i g u r e 4 . 3 . 1 T h r o u g h p u t r a t e v e r s u s W f o r c p u T = 0 . 5 , c p u B = 0 . 3 , 75 F i g u r e 4 . 3 . 2 R e s p o n s e t i m e v e r s u s W f o r c p u T = 0 . 5 , c p u B = 0 . 3 , 76 F i g u r e 4 . 4 . 1 T h r o u g h p u t r a t e v e r s u s W f o r c p u T = 0 . 2 , c p u B = 0 . 2 , 77 F i g u r e 4 . 4 . 2 R e s p o n s e t i m e v e r s u s W f o r c p u T = 0 . 2 , c p u B = 0 . 2 , 78 F i g u r e 4 . 5 . 1 T h r o u g h p u t r a t e v e r s u s c p u T = c p u B 79 F i g u r e 4 . 5 . 2 R e s p o n s e t i m e v e r s u s c p u T = c p u B 80 v i i A c k n o w l e d g e m e n t s I s i n c e r e l y t h a n k my s u p e r v i s o r D r . S . Cha.nson f o r h i s s u p e r v i s i o n a n d c a r e f u l r e a d i n g o f t h e t h e s i s . I a l s o s i n c e r e l y t h a n k D r . M . L . P u t e r m a n f o r h i s comments a n d c a r e f u l r e a d i n g o f t h e t h e s i s . T h e f i n a n c i a l s u p p o r t f r o m t h e D e p a r t m e n t o f C o m p u t e r S c i e n c e i s a l s o a p p r e c i a t e d . 1 CHAPTER I . INTRODUCTION 1.1 T h e N e e d f o r G o o d A d a p t i v e L o a d C o n t r o l P o l i c y L o a d c o n t r o l i s i m p o r t a n t i n m u l t i p r o g r a m m e d p a g i n g s y s t e m s s i n c e i f t h e d e g r e e o f m u l t i p r o g r a m m i n g i s t o o h i g h , ' t h r a s h i n g ' w i l l o c c u r . T h e e x c e s s i v e p a g i n g a c t i v i t i e s a r e u s u a l l y c a u s e d b y 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 t h e j o b s . A s a r e s u l t , t h r o u g h p u t r a t e w i l l d e c r e a s e a n d r e s p o n s e t i m e w i l l g r e a t l y i n c r e a s e . I t h a s b e e n shown t h a t an o p t i m a l d e g r e e • o f m u l t i p r o g r a m m i n g e x i s t s w h i c h m a x i m i z e s t h e s y s t e m t h r o u g h p u t i n a p a g i n g e n v i r o n m e n t i f t h e work l o a d d o e s n o t c h a n g e [ 1 , 2 , 1 6 , 1 7 ] , H o w e v e r , i n r e a l i t y , t h e work l o a d o f t h e s y s t e m i s n o t s t a t i c due t o t h e d y n a m i c r e s o u r c e demands o f j o b s a n d t h e i r n o n - u n i f o r m s t o c h a s t i c a r r i v a l s . T h e r e f o r e , an a d a p t i v e c o n t r o l p o l i c y i s n e e d e d w h i c h c h a n g e s w i t h t h e work l o a d t o o p t i m i z e p e r f o r m a n c e . 1.2 S u r v e y o f A d a p t i v e P e r f o r m a n c e I m p r o v e m e n t P o l i c i e s B u n t a n d Hume [ 7 ] p r o p o s e d an a d a p t i v e p r o c s s s o r s c h e d u l i n g s cheme b a s e d on j o b a r r i v a l p a t t e r n a n d t h e e s t i m a t e d s e r v i c e demand d i s t r i b u t i o n . T h e a l g o r i t h m i s s i m i l a r t o " S e l f i s h R o u n d R o b i n " a n d i s p r i o r i t y - d r i v e n w i t h a p a r a m e t e r B / X . A w a i t i n g j o b s g a i n p r i o r i t y a t t h e r a t e X a n d s e r v i c i n g j o b s g a i n p r i o r i t y a t t h e r a t e B . S e r v i c i n g j o b s a r e s e r v e d i n a r o u n d r o b i n f a s h i o n u n t i l a j o b i s c o m p l e t e d , o r t h e p r i o r i t y o f a w a i t i n g j o b e x c e e d s t h a t o f a s e r v i c i n g j o b . A t t h a t p o i n t , t h e s e r v i c i n g j o b i s p r e e m p t e d by t h e w a i t i n g j o b . T h i s a l g o r i t h m 2 a d a p t s i t s e l f t o t h e work l o a d c h a n g e s by a d j u s t i n g t h e r a t e B a c c o r d i n g t o t h e j o b a r r i v a l r a t e a n d t h e e s t i m a t e d c o e f f i c i e n t o f t h e v a r i a n c e o f t h e s e r v i c e t i m e d i s t r i b u t i o n . B i s d e c r e a s e d o r i n c r e a s e d by a f i x e d c o n s t a n t c on e a c h j o b a r r i v a l o r j o b c o m p l e t i o n r e s p e c t i v e l y . A p r o b l e m i s t h a t t h e r e i s no s y s t e m a t i c way o f c h o o s i n g t h e v a l u e o f c . B a d e l , G e l e n b e , 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 a n a d a p t i v e c o n t r o l scheme t o o p t i m i z e t h e p e r f o r m a n c e o f a t i m e - s h a r i n g s y s t e m . A t e a c h j o b a r r i v a l , c o m p l e t i o n o r a t p r e d e t e r m i n e d t i m e , an o p t i m a l d e g r e e o f m u l t i p r o g r a m m i n g n n , i s e s t i m a t e d f r o m t h e w e i g h t e d sum o f t h e u t i l i z a t i o n s o f t h e s y s t e m p r o c e s s o r s . I f t h e d e g r e e o f m u l t i p r o g r a m m i n g n i s l e s s t h a n n ^ , n i s i n c r e a s e d by o n e ; o t h e r w i s e i t r e m a i n s u n c h a n g e d . An a l g o r i t h m - i s a l s o g i v e n i n [ l ] b a s e d on a h e u r i s t i c a p p r o a c h . I n [ 1 7 ] , D e n n i n g , K h a n , L e r o u d i e r , P o t i e r a n d S u r i p r o p o s e d t h r e e h e u r i s t i c a p p r o a c h e s t o o p t i m a l l o a d c o n t r o l i n m u l t i p r o g r a m m e d c o m p u t e r s y s t e m s w i t h p a g e d v i r t u a l m e m o r y . T h e s e a r e t h e Knee c r i t e r i o n , t h e L=S c r i t e r i o n a n d t h e 50% c r i t e r i o n . U n d e r t h e Knee c r i t e r i o n , t h e mean r e s i d e n t memory s i z e o f e a c h p r o g r a m i s t o be k e p t n e a r t h e knee o f t h a t p r o g r a m ' s l i f e t i m e v e r s u s s p a c e f u n c t i o n a l l o w i n g t h e d e g r e e o f m u l t i p r o g r a m m i n g t o be d e t e r m i n e d . T h e l i f e t i m e f u n c t i o n L ( y ) o f a g i v e n p r o g r a m u n d e r a g i v e n memory management p o l i c y s p e c i f i e s t h e mean v i r t u a l t i m e b e t w e e n s u c c e s s i v e p a g e f a u l t s when y p a g e s o f memory a r e a l l o c a t e d t o i t . T h e knee o f t h e l i f e t i m e f u n c t i o n i s t h e p o i n t b e y o n d w h i c h t h e c u r v e f l a t t e n s o u t o r 3 more p r e c i s e l y , i t i s t h e h i g h e s t p o i n t o f t a n g e n c y b e t w e e n a r a y f r o m t h e o r i g i n a n d t h e c u r v e . T h e r a t i o n a l e 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 t h e s y s t e m a t t h e knee t e n d s t o m i n i m i z e t h e c o m p o n e n t s o f memory s p a c e - t i m e p r o d u c t due t o p a g i n g . S i n c e t h e s p e e d o f t h e I / O d e v i c e s a n d t h e v i r t u a l I / O r e q u e s t r a t e o f a p r o g r a m a r e i n d e p e n d e n t o f t h e r e s i d e n t memory s i z e , t h i s a l s o t e n d s t o m i n i m i z e t h e t o t a l memory s p a c e - t i m e p r o d u c t p e r j o b . I t h a s b e e n shown i n [ 9 , 1 7 ] t h a t t h r o u g h p u t r a t e i s m a x i m i z e d i f t h e memory s p a c e - t i m e p r o d u c t i s m i n i m i z e d . U n d e r t h e L=S c r i t e r i o n , t h e d e g r e e o f m u l t i p r o g r a m m i n g n i s c o n t r o l l e d so t h a t t h e s y s t e m l i f e t i m e L ( n ) d o e s n o t f a l l b e l o w t h e v a l u e S, w h e r e S i s t h e p a g e swap s e r v i c e t i m e . S i n c e t h e s y s t e m t h r o u g h p u t r a t e i s b o u n d e d by two c u r v e s , a g i (aQ i s t h e CPU e x i t i n g r a t e a n d i i s a c o n s t a n t b e t w e e n 0 a n d 1) a n d a p L ( n ) / S , t h e maximum t h r o u g h p u t r a t e s h o u l d be c l o s e t o t h e p o i n t o f i n t e r s e c t i o n o f t h e s e two c u r v e s w h i c h i m p l i e s L ( n ) = i S . F o r s i m p l i c i t y , i f we l e t i e q u a l t o o n e , we g e t t h e L=S c r i t e r i o n . U n d e r t h e 50% c r i t e r i o n , ^ t h e s y s t e m l o a d i s r e g u l a t e d by c o n t r o l l i n g t h e d e g r e e o f m u l t i p r o g r a m m i n g s o t h a t t h e u t i l i z a t i o n o f t h e p a g i n g d e v i c e i s c l o s e t o 50%. T h e r e a s o n i n g i s t h a t when t h e u t i l i z a t i o n o f a s i m p l e e x p o n e n t i a l s e r v e r i s 50%, t h e mean number o f j o b s i n t h e s y s t e m i s o n e . S i n c e 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 q u e u i n g a t t h e p a g i n g d e v i c e , i t i s p l a u s i b l e t h a t t h e o p t i m a l t h r o u g h p u t r a t e i s a c h i e v e d j u s t b e f o r e a n y s i g n i f i c a n t q u e u i n g o c c u r s . 4 H i n e , M i t r a n i a n d T s u r i n [ 2 1 ] s t u d i e d two a l g o r i t h m s t o c o n t r o l t h e e x p e c t e d r e s p o n s e t i m e s 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 p a g i n g s y s t e m s 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 t o d i f f e r e n t c l a s s e s o f j o b s w h i l e m a x i m i z i n g t h e CPU u t i l i z a t i o n . A h e u i s t i c a p p r o a c h was u s e d t o d e t e r m i n e t h e number o f j o b s f r o m e a c h 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 t o m a x i m i z e t h e CPU u t i l i z a t i o n . M o s t l o a d c o n t r o l a l g o r i t h m s a r e b a s e d on h e u r i s t i c a p p r o a c h e s w h i c h h a v e two m a j o r w e a k n e s s e s . T h e f i r s t i s t h a t t h e r e i s g e n e r a l l y no s y s t e m a t i c way o f d e t e r m i n i n g t h e o p t i m a l v a l u e s o f t h e p a r a m e t e r s i n t h e a l g o r i t h m . T h e o t h e r i s t h a t i t i s v e r y d i f f i c u l t t o show t h a t t h e y a r e o p t i m a l o r e v e n c l o s e t o o p t i m a l s i n c e t h e y a r e n o t b a s e d on a m a t h e m a t i c a l m o d e l . A l s o , t h e r o b u s t n e s s o f t h e a l g o r i t h m i s d i f f i c u l t t o be d e t e r m i n e d . I n [ 1 2 ] , C h a n s o n a n d S i n h a p r o p o s e d a l o a d c o n t r o l p o l i c y w h i c h i s b a s e d on m a t h e m a t i c a l m o d e l i n g f o r a m u l t i - c l a s s s y s t e m . T h e c o n t r o l p o l i c y i s an a d a p t i v e one a n d i s b a s e d on p r o j e c t e d work l o a d p a r a m e t e r s . T h e p o l i c y i s a p p l i e d a t f i x e d i n t e r v a l s . Work l o a d p a r a m e t e r v a l u e s a r e c o l l e c t e d a t e a c h i n t e r v a l a n d u s e d t o e s t i m a t e t h e v a l u e s i n t h e n e x t i n t e r v a l . The. c o n t r o l d e c i s i o n i s e x p r e s s e d a s an o p t i m i z a t i o n p r o b l e m f o r m u l a t e d a s a s i n g l e s t a g e n o n l i n e a r p r o g r a m m i n g p r o b l e m w i t h t h e number o f j o b s o f e a c h c l a s s i n t h e s y s t e m b e i n g t h e p r o b l e m v a r i a b l e s . T h e o b j e c t i v e i s c h o s e n t o be t h e w e i g h t e d sum o f t h e mean r e s p o n s e t i m e s i n c e w i t h t h e a s s u m p t i o n s a b o v e , i t c a n be e x p r e s s e d a s a f u n c t i o n o f t h e v a r i a b l e s . T h e p r o b l e m i s t h e n s o l v e d by t h e l a g r a n g i a n m u l t i p l i e r m e t h o d . T h e a c t u a l c o n t r o l 5 p o l i c y i s t o m a i n t a i n t h e number o f a c t i v a t e d j o b s o f e a c h c l a s s i n e a c h i n t e r v a l t o be a s c l o s e t o t h e c o m p u t e d o p t i m a l v a l u e s a s p o s s i b l e . T h e m a i n d i s a d v a n t a g e o f t h e scheme i s t h a t m e a s u r e m e n t o f w o r k l o a d p a r a m e t e r s a n d t h e c o m p u t a t i o n o f t h e c o n t r o l p o l i c y m u s t be d o n e a t e a c h i n t e r v a l i n r e a l t i m e . T h e c o m p u t a t i o n c a n be c o n s i d e r a b l e i f t h e e r r o r i n e s t i m a t i n g t h e work l o a d p a r a m e t e r s i s t o be s m a l l . In e i t h e r c a s e , s i n c e t h e e s t i m a t e d v a l u e s a r e n o t a l w a y s c o r r e c t , i t i s p o s s i b l e f o r t h e c o m p u t e d number o f j o b s i n a c l a s s t o be a c t i v a t e d t o e x c e e d t h e number o f j o b s i n t h e c l a s s t h a t i s a v a i l a b l e . T h u s t h e p r e d i c t e d p e r f o r m a n c e u s u a l l y f o r m s an u p p e r b o u n d i n a c t u a l p r a c t i c e . 1.3 M o t i v a t i o n a n d G o a l S i n c e m o s t o f t h e e x i s t i n g a d a p t i v e l o a d c o n t r o l a l g o r i t h m s h a v e t h e w e a k n e s s e s m e n t i o n e d i n t h e a b o v e s e c t i o n , i t i s d e s i r a b l e t o h a v e an a l g o r i t h m w h i c h i s b a s e d on m a t h e m a t i c a l m o d e l i n g w i t h m i n i m a l o v e r h e a d d u r i n g a p p l i c a t i o n . I n [ 2 9 ] , L o a p p l i e d some o f t h e r e s u l t s a n d 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 o e r y t o o b t a i n an a d a p t i v e l o a d c o n t r o l p o l i c y w h i c h i s b a s e d on a m a t h e m a t i c a l m o d e l . T h e c o m p u t e r s y s t e m i s m o d e l l e d a s a q u e u e i n g m o d e l a n d t h e l o a d c o n t r o l i s m o d e l l e d a s an o p t i m a l s t o c h a s t i c p r o b l e m . The c o n t r o l p o l i c y i s a f u n c t i o n o f t h e c u r r e n t s t a t e o f t h e s y s t e m . O n l y t h e s t a t e o f t h e s y s t e m ( u s u a l l y s i m p l y a s t h e number o f j o b s o f e a c h c l a s s i n t h e s y s t e m ) h a s t o be d e t e r m i n e d . A t a b l e l o o k - u p p r o d u c e s t h e d e s i r e d c o n t r o l f o r t h a t s t a t e . T h u s t h e 6 a p p l i c a t i o n o v e r h e a d i s n e g l i g i b l e . I n t h i s t h e s i s , we w i l l e x t e n d t h e r e s u l t s i n [ 2 9 ] t o g i v e a m o r e g e n e r a l a p p r o a c h a n d i m p r o v e t h e p e r f o r m a n c e by s p e c i f y i n g t h e s t a t e s o f t h e s y s t e m i n more d e t a i l . 7 CHAPTER I I . OPTIMAL S T O C H A S T I C CONTROL THEORY In t h i s c h a p t e r , we w i l l r e v i e w t h e a r e a s i n s t o c h a s t i c c o n t r o l t h e o r y i n [ 4 ] t h a t a r e r e l e v a n t t o t h i s t h e s i s . 2.1 The p r o b l e m k L e t S d e n o t e t h e s t a t e s p a c e o f a s y s t e m a n d l e t U ( i ) k d e n o t e t h e c o n t r o l s p a c e f o r s t a t e i a t s t a g e k . A l s o l e t u ( i ) d e n o t e t h e c o n t r o l a p p l i e d a t s y s t e m s t a t e i a n d s t a g e k w i t h k . k i e S a n d u ( i ) e U ( i ) . A p o l i c y i f i s a s e q u e n c e o f c o n t r o l s 1 2 {u , u , . . . . } a p p l i e d f o r t h e s u c c e s s i v e s t a g e s r e s p e c t i v e l y . We w i l l o n l y c o n s i d e r • s t a t i o n a r y a d m i s s i o n p o l i c i e s w i t h t h e f o l l o w i n g p r o p e r t i e s : ( 1 ) u k ( i ) = u ( i ) V i , k (2) U k ( i ) = U ( i ) V i , k L e t P ^ j ( u ( i ) ) , V i , j d e n o t e t h e t r a n s i t i o n p r o b a b i l i t i e s f r o m s t a t e i t o s t a t e j when c o n t r o l u ( i ) i s a p p l i e d . L e t g ( i , u ( i ) ) be t h e c o s t when c o n t r o l u ( i ) i s a p p l i e d a t s t a t e i . The o b j e c t i v e i s t o m i n i m i z e t h e a v e r a g e c o s t p e r s t a g e o v e r a l l s t a t i o n a r y a d m i s s i o n p o l i c i e s n. F o r s i m p l i c i t y , we w i l l u s e u t o d e n o t e t h e s t a t i o n a r y p o l i c y {u , u , . . . }. The l o n g r u n a v e r a g e c o s t o f p o l i c y u i s d e f i n e d t o be N - 1 J = l i m (1 / N ) E { L g (X , , u ( X , ))} (2.1) U N - - > ° ° K=0 K K where i s t h e s t a t e o f t h e s y s t e m a t s t a g e k . G i v e n a n y s t a t i o n a r y p o l i c y u , l e t us d e n o t e t h e 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 a s f o l l o w : p = u P n ( u ( D ) P l n ( u ( D ) P n 1 ( u ( n ) ) . P n n ( u ( n ) ) w h e r e P . . ( u ( i ) ) > 0, V i , j , J j = 1 3 Z P . . ( u ( i ) ) = 1, V i a n d n i s t h e number o f e l e m e n t s i n S . D e n o t e J = —u J u(1) J » < 2 > J (n) u a n d G = —u g ( i , u ( U ) g ( 2 , u ( 2 ) ) g ( n , u ( n ) ) N - l . t h e n , J = l i m ( 1 / N ) I P . G u N ~ > » k = 0 u u ( 2 . 2 ) w h e r e P y i s t h e k - s t e p 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 c o r r e s p o n d i n g t o t h e p o l i c y u . T h e o r e m 1 F o r a n y nxn s t o c h a s t i c m a t r i x P , ( P . . > 0 V i , j a n d Z P . . = 1 V i ) , we h a v e 3 = 1 1 3 9 N-1 . * l i m ( 1 / N ) L P = P N — > ° ° k=1 * 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 t h e f o l l o w i n g p r o p e r t i e s : * * * * * (a) P = P P = P P = P P * -1 (b) ( I - P + P ) e x i s t s where I i s t h e i d e n t i t y m a t r i x . L e t * N - 1 k P = l i m ( 1 / N ) L P „ ( 2 . 3 ) u N - - > » k=0 U U s i n g t h e o r e m 1, a n d e q u a t i o n ( 2 . 2 ) J = P * G ( 2 . 4 ) —u u—u T h u s , 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 , t h e c o r r e s p o n d i n g a v e r a g e c o s t J_u i s w e l l d e f i n e d by e q u a t i o n ( 2 . 4 ) . -D e f i n e ^ u = ( I - p u + P u r 1 ( l - p ! X ( I~ Pu+ E\X = ( l " P u ^ u • • ( 2 ' 5 ) M u l t i p l y i n g b o t h s i d e s by P u a n d u s i n g p a r t (a) o f t h e o r e m 1, we g e t P * H = 0 ( 2 . 6 ) u—u U s i n g e q u a t i o n s ( 2 . 4 ) a n d ( 2 . 6 ) , we c a n r e w r i t e ( 2 . 5 ) a s J + H = G + P H , V u ( 2 . 7 ) —u —u - u u - u ' 2 . 2 C o n d i t i o n f o r t h e e x i s t e n c e o f o p t i m a l s t a t i o n a r y p o l i c y 2 . 2 . 1 F i n i t e Mean P a s s a g e T i m e C o n d i t i o n D e f i n e t o be t h e s y s t e m s t a t e a t s t a g e k . F o r any two 10 s t a t e s i , j e S , l e t us d e n o t e by k ^ ( u ( i ) ) t h e s m a l l e s t i n d e x k f o r w h i c h X ^ = j when XQ = i , a n d t h e s t a t i o n a r y p o l i c y u i s u s e d . T h e n we h a v e k . j ( u ( i ) ) = i n f { k | X Q = i , X k = j , X m # j f o r 1<m<k } w h e r e k ^ j ( u ( i ) ) i s t h e f i r s t p a s s a g e t i m e f r o m s t a t e i t o s t a t e j w i t h c o n t r o l u ( i ) . F o r e a c h i , j a n d u ( i ) , k ^ ( u ( i ) ) may be v i e w e d a s a r andom v a r i a b l e t a k i n g p o s i t i v e v a l u e s o r t h e v a l u e i n f i n i t y w i t h p r o b a b i l i t i e s P ( k . . ( i ) = k) = q * . m k P ( k , . ( i ) = ° ° ) = 1 - Z q ? . 1 3 k=1 1 3 Now d e f i n e t h e e x p e c t e d f i r s t p a s s a g e t i m e E { k ^ j ( u ( i ) ) } a s s o c i a t e d w i t h u by E { k . j ( u ( i ) ) } = 2.2.2 Weak A c c e s s a b i 1 i t y C o n d i t i o n F o r a n y two s t a t e s i , j e S , t h e r e e x i s t s a s t a t i o n a r y p o l i c y 7r a n d an i n t e g e r m s u c h t h a t P i j = P ( X m = J I X Q = i , TT) > 0 t h a t i s , a n y s t a t e c a n be r e a c h e d f r o m a n y o t h e r s t a t e i n f i n i t e t i m e f o r some c o n t r o l p o l i c y . 0 0 If 0 0 v Z kq? . i f Z q ? . = 1 k=1 1 3 k=1 1 3 0 0 o t h e r w i s e . 11 2 . 2 . 3 E x i s t e n c e R e s u l t A s a r e s u l t o f s e c t i o n 2 . 1 , we h a v e an a v e r a g e c o s t v e c t o r J_u a s s o c i a t e d w i t h e v e r y c o n t r o l u d e f i n e d by e q u a t i o n ( 2 . 3 ) a n d ( 2 . 4 ) w h i c h w i l l s a t i s f y t h e f u n c t i o n a l e q u a t i o n ( 2 . 7 ) . W i t h t h e weak a c c e s s a b i 1 i t y c o n d i t i o n s a t i s f i e d , t h e o p t i m a l s t a t i o n a r y p o l i c y u * s a t i s f i e s t h e f o l l o w i n g : The c o s t v e c t o r J = <pe c o r r e s p o n d s t o t h e c a s e w h e r e t h e o p t i m a l c o s t i s i n d e p e n d e n t ' o f t h e i n i t i a l s t a t e . T h e o r e m 2 S u p p o s e t h a t t h e r e e x i s t s a r e f e r e n c e s t a t e t e S s u c h 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 u a n d e v e r y s t a t e i e S , E { k ^ t ( u ( i ) ) } < » o r t h e weak a c c e s s i b i l i t y c o n d i t i o n i s s a t i s f i e d , t h e n t h e r e e x i s t s a c o n s t a n t <f> a n d a f u n c t i o n h : S ~ - > R s u c h t h a t J ( i ) < J ( i ) - u * - u V u , i = <£e where 0 i s a s c a l a r n 0 + h ( i ) = min ( g ( i , u ( i ) ) + Z p . . ( u ( i ) ) h ( j ) } , i=1 u ( i ) e U ( i ) j=1 3  , . • • , ( 2 . 8 ) F u r t h e r m o r e , t h e o p t i m a l v a l u e J o f ( 2 . 1 ) i s e q u a l t o <j> V i w i t h <p = i n f J u u In a d d i t i o n , i f u * ( i ) a t t a i n s t h e minimum 0 f o r e v e r y s t a t e i , 1 2 t h e s t a t i o n a r y p o l i c y IT* = { u * , . . . } i s o p t i m a l . C o r o l l a r y 1. L e t 0 be an s t a t i o n a r y a d m i s s i o n p o l i c y a n d s u p p o s e t h e r e e x i s t s a s t a t e t e S s u c h t h a t E { k ^ t ( . u ( i ) ) } < ° ° , V i e S . T h e n t h e r e e x i s t s a c o n s t a n t 0 a n d a f u n c t i o n h u : S --> R s u c h t h a t J u ( i ) = 0 U, V i F u r t h e r m o r e , n 0 +h ( i ) = g ( i , u ( i ) ) + Z P . . (u ( i ) ) h ( j ) , V i u u j=1 1 3 u ( 2 . 9 ) E q u a t i o n ( 2 . 9 ) r e p r e s e n t s a s y s t e m o f n l i n e a r e q u a t i o n s w i t h (n+1) unknowns - t h e s c a l a r s 0^, h u ( 1 ) , h u ( 2 ) , h u ( n ) . By a d d i n g one more c o n s t r a i n t h ( t ) = 0 ( 2 . 1 0 ) w h e r e t i s t h e r e f e r e n c e s t a t e d e f i n e d i n T h e o r e m 2 . I t h a s b e e n shown i n [ 4 ] t h a t a u n i q u e s o l u t i o n e x i s t s f o r t h i s s y s t e m . 2 . 3 P o l i c y i t e r a t i o n a l g o r i t h m I n t h e p r e v i o u s s e c t i o n s , we d i s c u s s t h e n a t u r e o f t h e p r o b l e m a n d t h e c o n d i t i o n s i n w h i c h 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 . I n t h i s s e c t i o n , we w i l l d i s c u s s an a l g o r i t h m c a l l e d p o l i c y i t e r a t i o n w h i c h s o l v e s t h e e x p e c t e d a v e r a g e c o s t p r o b l e m . T h e b a s i s o f t h e a l g o r i t h m i s t o f i n d a new p o l i c y i n t h e s t t h (k+1) i t e r a t i o n f r o m t h e p o l i c y i n t h e k i t e r a t i o n s u c h t h a t J < J _ u ( k - H ) - u k T h e a l g o r i t h m w i l l a s sume t h e c o n d i t i o n s f o r t h e e x i s t e n c e t h e o p t i m a l p o l i c y s t a t e d i n T h e o r e m 2 . 1 4 T h e P o l i c y I t e r a t i o n A l g o r i t h m S t e p (1) : L e t k = 0 , c h o o s e an a r b i t r a r y a d m i s s i b l e p o l i c y U Q . S t e p (2) : Compute 0 , h ( i ) , i = 1 , . . . , n by s o l v i n g t h e s y s t e m u k u k n <PU + h ( i ) = g ( i , u k ( i ) ) + L P . . ( u . ( i ) ) h ( j ) , i = 1 , . . . , n k k j = 1 k • ( 2 . 1 1 ) h ( t ) = 0 . ( 2 . 1 2 ) u k w h e r e t i s t h e r e f e r e n c e s t a t e d e f i n e d i n t h e o r e m 2 . S t e p (3) : F i n d u k + 1 by , n -min { g ( i , u ( i ) ) + I P . . ( u ( i ) ) h ( j ) } ( 2 . 1 3 ) u ( i ) e U ( i ) j=1 1 3 U k n = g ( i , u R + 1 ( i ) ) + L P . j ( u k + 1 ( i ) ) h u ( j ) , i=1 n ] = 1 k S t e p (4) : I f u k = u k + 1 or <p - <t> < e k k+i u k u k + 1 t h e n s t o p , u A = u k e l s e go t o S t e p (2) I t c a n be shown t h a t 0 < 0 a n d t h e i t e r a t i o n c o n v e r g e s u k+1 u k t o . 15 2 . 4 C o m p u t a t i o n a l c o s t L e t N be t h e t o t a l number o f s y s t e m s t a t e s . L e t | U ( i ) | be t h e number o f d i s t i n c t c o n t r o l s f o r s t a t e i . T h e o v e r h e a d c o s t c o n s i s t s o f two p a r t s : c p u t i m e r e q u i r e m e n t a n d memory s p a c e r e q u i r e m e n t . We w i l l f i r s t c o n s i d e r t h e t i m e r e q u i r e m e n t . C o m p a r i s o n s , a d d i t i o n s a n d s u b s t r a c t i o n s w i l l be g r o u p e d t o g e t h e r a n d a b b r e v a t e d by " C A S " . We w i l l o n l y c o u n t t h e number o f m u l t i p l i c a t i o n s , d i v i s i o n s a n d C A S . L e t us as sume t h a t t h e o p e r a t i o n a l c o u n t o f g ( i , u ( i ) ) f o r a l l s t a t e i be b o u n d e d by K1 number o f m u l t i p l i c a t i o n s , K2 number o f d i v i s i o n s a n d K3 number o f C A S . I n p r a c t i c e , t h e number o f i t e r a t i o n s n e e d e d f o r t h e a l g o r i t h m t o c o n v e r g e i s u s u a l l y l e s s t h a n t e n . T i m e r e q u i r e m e n t : I n s t e p (2) ,- f o r e v e r y s t a t e i , f o r m i n g t h e s y s t e m o f e q u a t i o n s r e q u i r e s N(N+K1) m u l t i p l i c a t i o n s , no d i v i s i o n a n d N(K3+N+1) C A S . S o l v i n g t h e l i n e a r s y s t e m o f e q u a t i o n o f N+1 unknown by G a u s s E l i m i n a t i o n w i t h p a r t i a l p i v o t i n g r e q u i r e s 0 ( ( N + l ) 3 / 3 ) m u l t i p l i c a t i o n s , 0 ( ( N + 1 ) 2 / 2 ) d i v i s i o n s a n d 0 ( ( N + 1 ) 3 / 3 ) C A S . I n s t e p ( 3 ) , t h e m i n i m i z a t i o n i s o v e r a l l a d m i s s i b l e c o n t r o l u ( i ) e U ( i ) f o r a l l t h e s t a t e i . ' N o t e t h e number o f d i s t i n c t c o n t r o l i s l e s s t h a n o r e q u a l t o N ( t h e t o t a l number o f s y s t e m s s t a t e s ) . T h e r e a r e N m u l t i p l i c a t i o n s , (N+1) CAS a n d one c o m p u t a t i o n o f g ( i , u ( i ) ) f o r e a c h d i s t i n c t ( i , u ) p a i r w h i c h g i v e s a t o t a l o f N . I l | U ( i ) | . (N+K1 ) < N 2 ( N + K 1 ) m u l t i p l i c a t i o n s i 16 N . n | U ( i ) | . K 2 < N 2 K 2 d i v i s i o n s , i N . n | U ( i ) | . ( N + K 3 + 1 ) < N 2 ( N + 1 + K 3 ) C A S . i " I n s t e p ( 4 ) , t h e r e a r e no m u l t i p l i c a t i o n s a n d d i v i s i o n s . C h e c k i n g f o r c o n v e r g e n c e r e q u i r e s 0 (N+2) C A S . A s a r e s u l t , t h e t o t a l number o f m u l t i p l i c a t i o n s p e r i t e r a t i o n i s 0 ( N ( N + K 1 ) ) + 0 ( N 3 / 3 ) + 0 ( N 2 ( N + K 1 ) ) = 0 ( 4 N 3 / 3 ) + 0 ( N 2 ) + 0 ( N . K 1 ) + 0 ( N 2 . K 1 ) = 0 ( 4 N 3 / 3 ) + 0 ( K 1 . N 2 ) . T h e t o t a l number o f d i v i s i o n s p e r i t e r a t i o n i s 0 ( ( N + 1 ) 2 / 2 ) + 0 ( N 2 K 2 ) = 0 ( N 2 . ( K 2 + 1 / 2 ) . T h e t o t a l number o f C A S . p e r i t e r a t i o n i s 0 ( N ( N + K 3 ) ) + 0 ( N 3 / 3 ) + 0 ( N 2 ( N + K 3 ) ) = 0 ( 4 N 3 / 3 ) + 0 ( K 3 . N 2 ) . Now we w i l l c o n s i d e r t h e memory s p a c e r e q u i r e m e n t . Memory r e q u i r e m e n t : T h e m a j o r memory r e q u i r e m e n t i s t o s t o r e t h e m a t r i x o f t h e 2 2 l i n e a r s y s t e m o f e q u a t i o n s w h i c h r e q u i r e s 0 ( ( N + 1 ) ) —> 0 ( N ) w o r d s . T o s t o r e t h e c o n t r o l p o l i c y , o n l y 0 ( N ) w o r d s a r e r e q u i r e d . N o t e t h a t i t may be p o s s i b l e t o s o l v e t h e p r o b l e m more e f f i c i e n t l y by u s i n g t h e m o d i f i e d p o l i c y i t e r a t i o n a l g o r i t h m w i t h a c t i o n e l i m i n a t i o n f 3 1 ] . 17 CHAPTER I I I . THE SYSTEM D E S C R I P T I O N J o b s i n a c o m p u t e r s y s t e m a r e 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 g r o u p s s u c h a s t e r m i n a l j o b s , b a t c h 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 r e q u i r e d f o r e a c h c l a s s o f j o b s . T h e j o b s i n d i f f e r e n t c l a s s e s a r e g i v e n d i f f e r e n t p r i o r i t i e s a n d a r e t r e a t e d d i f f e r e n t l y . H e r e , we w i l l c o n s i d e r t h e m o d e l p r o p o s e d i n [ 2 9 ] w h i c h c o n s i s t s o f o n l y two c l a s s e s o f j o b s a n d a s i m p l e l o a d c o n t r o l . T h e c o n t r o l i s t o r e g u l a t e t h e number o f j o b s o f e a c h c l a s s t o be a c t i v a t e d f o r e a c h s t a t e o f t h e s y s t e m i n o r d e r t o g i v e g o o d t h r o u g h p u t r a t e a n d r e s p o n s e t i m e . L e t N^ be t h e t o t a l number o f c l a s s i j o b s i n t h e s y s t e m . L e t n^ be t h e number o f a c t i v a t e d c l a s s i j o b s i n t h e s y s t e m . 3 . 1 M o d e l D e s c r i p t i o n T h e s y s t e m m o d e l c o n s i s t s o f N t e r m i n a l s , a c p u w i t h Y p a g e s o f m a i n memory , a p a g i n g d r u m a n d 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 u s e r " t h i n k " t i m e i s a s s u m e d t o be r a n d o m l y d i s t r i b u t e d w i t h mean 1/0 T- T h e 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 t h u s c 0 T w h e r e c i s t h e number o f t e r m i n a l s i n t h e " t h i n k " s t a t e . T h e i n t e r a r r i v a l t i m e o f b a t c h j o b s i s r a n d o m l y d i s t r i b u t e d w i t h mean T / ^ g * T n e C P U s e r v i c e r e q u i r e m e n t o f a l l t h e c l a s s e s o f j o b s a r e a s s u m e d t 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 . A t any moment , a j o b i n t h e s y s t e m i s e i t h e r a c t i v e , o c c u p y i n g a c e r t a i n amount o f memory i n s i d e t h e memory l o o p o r i s n o n - a c t i v e , w a i t i n g t o be a d m i t t e d i n t o t h e memory l o o p . 18 The a d m i s s i o n o f j o b s i n t o t h e memory l o o p i s c o n t r o l l e d by a l o a d c o n t r o l p o l i c y it. T h e s t a t e o f t h e s y s t e m c a n be a p p r o x i m a t e d by t h e v e c t o r (N ,N, , ) w h i c h c o n t a i n s t h e t o t a l number o f e a c h c l a s s o f j o b s i n t h e s y s t e m o r t h e more p r e c i s e s t a t e ( N 1 , N 2 , n 1 , n 2 ) w h i c h a l s o c o n t a i n s t h e number o f j o b s o f e a c h c l a s s i n t h e memory l o o p . Now we want an a d m i s s i o n p o l i c y % w h i c h w i l l m a x i m i z e t h r o u g h p u t r a t e a n d m i n i m i z e r e s p o n s e t i m e . A s i m p l e c r i t e r i o n i s t o m i n i m i z e W * N + H 2 , . ( 3 . 0 ) t h e w e i g h t e d sum o f t h e number o f j o b s o f e a c h c l a s s i n t h e s y s t e m where W i s t h e w e i g h t r e f l e c t i n g t h e d e s i r e d p r i o r i t y o f c l a s s one j o b s o v e r c l a s s two j o b s . T h e r a t i o n a l e o f c h o o s i n g ( 3 . 0 ) i s b r i e f l y g i v e n b e l o w . F o r a s y s t e m i n e q u i l i b r i u m , t h e t h r o u g h p u t r a t e o f j o b s i n a n y c l a s s must e q u a l t o t h e a r r i v a l r a t e o f t h e j o b s i n t h a t c l a s s . The mean a r r i v a l r a t e o f b a t c h j o b s i s a s s u m e d t o be c o n s t a n t . T h e r e f o r e m i n i m i z i n g N 2 w i l l m i n i m i z e t h e mean r e s p o n s e t i m e o f b a t c h j o b s . A l s o , t h e mean 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 p r o p o r t i o n a l t o ( N - N ^ . T h e r e f o r e m i n i m i z i n g N^ w i l l m a x i m i z e t h e t h r o u g h p u t r a t e a n d m i n i m i z e t h e r e s p o n s e t i m e o f i n t e r a c t i v e j o b s . We a s sume n^ = 0 V i a t t h e p r e v i o u s s t a g e w h e n e v e r t h e c o n t r o l p o l i c y i s a p p l i e d . I f we c h o o s e t o r e p r e s e n t t h e s t a t e by t h e v e c t o r (N , N 2 ) , t h e c o n t r o l s p a c e U ( ( N r N 2 ) ) = { ( n r n 2 ) | n 1 < N 1 & n 2 < N 2 }. L e t X, be t h e s y s t e m s t a t e a t s t a g e k 19 T h e p r o b l e m : N-1 min l i m ( 1 / N ) E { L g ( X . ) } N - - > o o k = Q w i t h g ( X . ) = W*N +N. where X, ( N 1 , N 2 ) f i t s i n t o t h e b a s i c f r a m e w o r k 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 p r o b l e m d e s c r i b e d i n c h a p t e r I I . T h e r e f o r e , i t c a n be s o l v e d by t h e t e c h n i q u e s d e s c r i b e d i n c h a p t e r I I . N t e r m i n a l s ( N - N , ) Memory Queues 'B I DRUM f DISK -<• A T l ( n l ' n 2 ) T 2 ( n 1 , n 2 ) Memory Loop (n^n,,) F i g u r e 3.1 T h e S y s t e m M o d e l In t h e m o d e l , c l a s s 1 j o b s c o r r e s p o n d t o i n t e r a c t i v e j o b s a n d c l a s s 2 j o b s c o r r e s p o n d t o b a t c h j o b s . T h e drum i s u s e d f o r p a g i n g a n d t h e d i s k i s f o r f i l e I / O . L e t T ( n 1 , n 2 ) d e n o t e t h e t h r o u g h p u t r a t e f o r c l a s s r j o b s when t h e r e a r e n 1 i n t e r a c t i v e j o b s a n d n 2 b a t c h j o b s i n t h e memory l o o p . F i r s t , i t i s n e c e s s a r y t o c o m p u t e T ^ n ^ n . ^ ) a n d T ^ n ^ n ^ . B e c a u s e o f t h e b l o c k i n g o f j o b s by t h e c o n t r o l p o l i c y a n d t h e 20 n o n - e x p o n e n t i a l j o b a r r i v a l d i s t r i b u t i o n , t h e model d o e s n o t f i t i n t o t h e q u e u i n g network m o d e l s i n [ 3 , 3 2 ] . An a p p r o x i m a t e s o l u t i o n i s o b t a i n e d by u s i n g t h e d e c o m p o s i t i o n t e c h n i q u e s f i r s t p r o p o s e d by C o u r t o i s f 1 3 ] . T h e s e t e c h n i q u e s c o n s i s t o f h i e r a r c h i c a l l y d e c o m p o s i n g a n e t w o r k i n t o n e s t e d 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 t h e s u b n e t w o r k a r e f i r s t d e r i v e d a s i f t h e y were i n d e p e n d e n t c l o s e d q u e u i n g n e t w o r k s ( w i t h o u t any i n t e r a c t i o n s w i t h t h e s u r r o u n d i n g n e t w o r k ) . T h e s e r e s u l t s a r e t h e n u s e d t o s o l v e t h e e n c l o s i n g n e t w o r k . The a p p r o x i m a t e s o l u t i o n w i l l be c l o s e t o t h e e x a c t s o l u t i o n i n w h i c h t h e r a t e of i n t e r a c t i o n s w i t h i n t h e s u b n e t w o r k s g r e a t l y e x c e e d s t h e r a t e o f i n t e r a c t i o n s among t h e s u b n e t w o r k s , In o u r m o d e l , t h e r a t e o f s t a t e c h a n g e s w i t h i n t h e memory l o o p among t h e d e v i c e s i s much h i g h e r t h a n t h a t o f a d m i s s i o n a n d d e p a r t u r e o f j o b s i n t o and f r o m t h e memory l o o p . T h e r e f o r e , i t i s j u s t i f i e d t o u s e d e c o m p o s i t i o n t e c h n i q u e s t o s o l v e o u r model by f i r s t c o n s i d e r i n g t h e memory l o o p a s a c l o s e d c e n t r a l - s e r v e r n e t w o r k w i t h n^ i n t e r a c t i v e a n d b a t c h j o b s . 3.2 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 L e t d e n o t e t h e e x i t r a t e o f c l a s s j j o b s f r o m s e r v e r i . L e t 1 / M i r ^ e t n e mean o f t h e random d i s t r i b u t i o n r e p r e s e n t i n g t h e u n i n t e r r u p t e d c p u t i m e s e r v i c e o f c l a s s r j o b s . J o b s b e i n g s e r v e d by t h e c p u c a n 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 o r j o b c o m p l e t i o n i n t e r r u p t s . L e t 1/E be t h e mean o f an e x p o n e n t i a l d i s t r i b u t i o n o f t h e 21 amount o f v i r t u a l t i m e b e t w e e n page f a u l t s f o r a c l a s s r j o b . L e t 1 / ° r D e the mean o f a n e x p o n e n t i a l d i s t r i b u t i o n o f t h e amount o f v i r t u a l t i m e b e t w e e n two d i s k r e q u e s t s f o r a c l a s s r j o b a n d i t i s a s s u m e d t o be i n d e p e n d e n t o f memory a l l o c a t i o n . L e t 1/C be t h e mean o f a n e x p o n e n t i a l d i s t r i b u t i o n o f t h e t o t a l c p u t i m e r e q u i r e m e n t o f a c l a s s r j o b . I f we assume t h e s e t h r e e e v e n t s a r e i n d e p e n d e n t , we g e t 1/M 1 r = m i n { 1 / E r , i / D r , 1 / C r ) The p a g i n g b e h a v i o u r o f a c l a s s r j o b e x e c u t i n g w i t h y p a g e s o f m a i n memory a l l o c a t i o n i s m o d e l l e d by a l i f e t i m e f u n c t i o n L r ( y ) w h i c h d e t e r m i n e s t h e e x p e c t e d v i r t u a l t i m e b e t w e e n two s u c c e s s i v e page f a u l t s . L r ( y ) i s a f u n c t i o n o f t h e number o f p a g e s a l l o c a t e d t o a p r o c e s s . H e r e , we a d o p t t h e l i f e t i m e f u n c t i o n p r o p o s e d by C h a m b e r l i n [ 1 0 ] shown i n F i g u r e 3.2. 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 L r(y) = 2b 1+(a r/y) (3.1 ) b^ i s t h e e x p e c t e d v i r t u a l i n t e r p a g e - f a u l t t i m e when a c l a s s r 22 j o b i s a l l o c a t e d p a g e s o f memory , a n d a r i s t h e number o f p a g e s t h a t p r o v i d e s t h e 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 l i f e t i m e . S i n c e 1 / E ^ , 1 / D r , a n d a r e f r o m e x p o n e n t i a l d i s t r i b u t i o n , t h e d i s t r i b u t i o n w i l l a l s o be ' . 1 r e x p o n e n t i a l l y d i s t r i b u t e d . H e n c e t h e c p u e x i t r a t e u^r i s g i v e n by M 1 r = D r + C r + 1 / L r ( y ) (3.2) T h e memory l o o p i s now c o n s i d e r e d a s a c l o s e d c e n t r a l - s e r v e r m o d e l . We a s sume t h a t t h e mean d r u m a n d d i s k s e r v i c e r a t e ( A ^ J r e s p e c t i v e l y ) a r e t h e same f o r a l l t h e c l a s s e s o f j o b s . T h e t r a n s i t i o n p r o b a b i l i t i e s q ^ ( r ) o f g o i n g f r o m s e r v e r i t o s e r v e r j f o r a j o b i n c l a s s r a r e g i v e n b y : q 1 2 ( r ) = l / U l r . L r ( y r ) ) q n ( r ) = D r / M 1 r q 2 1 ( r ) = q 3 1 ( r ) = 1 ( 3 . 3 ) C o n s i d e r t h e t r a n s i t i o n b a l a n c e e q u a t i o n s : 3 E q . . ( r ) . / i . x . = u . x . , j = 1 , 2 , 3 r=1 i j i r i r * } r j r ' J ' '  1,2 ( 3 . 4 ) 23 I n o u r m o d e l , t h e h o m o g e n o u s s o l u t i o n o f ( 3 . 4 ) i s : 1 r ' 2 r '3r = 1 q 1 2 ( r ) . / £ 1 r q l 3 ( r ) . M 1 M 2 . L r ( y r ) D Now l e t us c o n s i d e r a g e n e r a l c e n t r a l s e r v e r m o d e l w i t h s j o b c l a s s e s a n d M s e r v e r s . L e t be t h e number o f c l a s s r j o b s a t s e r v e r i . L e t n be t h e t o t a l number o f j o b s i n t h e m o d e l . L e t n be t h e v e c t o r ( n ^ n 2 , . . . . , n g ) L e t n^ be t h e t o t a l number o f j o b s i n s e r v e r i . L e t k^ be t h e t o t a l number o f c l a s s i j o b s i n t h e m o d e l , s k . = I k . 1 r=1 i r T h e s t a t e o f t h e m o d e l i s d e s c r i b e d by t h e number o f j o b s o f e a c h c l a s s a t e a c h s e r v e r . We w i l l d e r i v e t h e u t i l i z a t i o n e q u a t i o n s f o r t h i s m o d e l . N o t e t h a t n = Z n . i = 1 ' M = Z k : i=1 ' L e t S n ( r ) be t h e mean number o f p a g e s o f memory a l l o c a t e d t o a c l a s s r j o b when t h e s y s t e m s t a t e i s n a n d L r ( . ) i s t h e 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 . T h e r e a r e many f a c t o r s w h i c h i n f l u e n c e t h e v a l u e o f S n ( r ) 24 s u c h a s p a g e r e p l a c e m e n t a l g o r i t h m , s p e e d o f p a g i n g d e v i c e , p r o g r a m , l o c a l i t y , e t c . U n f o r t u n a t e l y , t h e y h a v e n o t b e e n s t u d i e d s y s t e m a t i c a l l y , a n d t h e v a l u e o f ^ n ( r ) i s g e n e r a l l y n o t a v a i l a b l e e x c e p t f o r t h e c a s e when 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 t h e j o b s . We w i l l u s e e q u i p a r t i t i o n a s s u m p t i o n i n t h e m o d e l . H e n c e Y S n ( r ) = — , ( 3 . 6 ) — s Z n-i=1 1 w h e r e Y i s t h e t o t a l memory c a p a c i t y . L e t e n ( r ) be t h e mean p a g e f a u l t r a t e o f t h e c l a s s r j o b s when t h e s y s t e m s t a t e i s n . 1 e ( r ) = ~ V S n ( r ) ) A c c o r d i n g t o B a s k e t t [ 3 ] , t h e s t a t i o n a r y p r o b a b i l i t y o f s t a t e K ( s , m ) = { k ^ , . . . , k ^ s , k 2 .j , . . . , k 2 s , , k m 1 , . . . , k m s ) i . e . , t h e p r o b a b i l i t y t h a t t h e s y s t e m i s i n s t a t e K ( s , m ) a t a n y t i m e i s g i v e n by e q u a t i o n ( 3 . 7 ) . T h i s a s s u m e s t h a t t h e s e r v i c e d i s c i p l i n e o f t h e c p u , w i t h j o b c l a s s d e p e n d e n t s e r v i c e r a t e M l r , i s p r o c e s s o r s h a r i n g . k . 1 s M ( x . ) i r P ( K ( s , M ) ) = n n { k . ! — 1 £ } ( 3 . 7 ) • - G ( n ) r=1 i=1 1 k i r ! G ( n ) i s t h e n o r m a l i z i n g c o n s t a n t w h i c h n o r m a l i z e d t h e sum o f a l l p r o b a b i l i t i e s t o 1. 25 3 . 2 . 1 C o m p u t a t i o n o f G ( n ) L e t S ( n , m ) = { ( k 1 i r . . . , k 1 s , k 2 1 , . . . , k 2 s , ' k m 1 " - " k m s ) m Z k . = n , a n d k . > 0 V r } i = 1 r S i n c e G ( n ) i s d e f i n e d so t h a t Z P ( K ( s , M ) ) = 1, i t • K ( s , M ) ^ " -f o l l o w s t h a t G ( n ) = M s k . n {"[ n (x. ) i r s [ z r=1 k . ] ! i r K ( s , M ) e S ( n , M ) i=1 r=1 i r n k . ! r=1 i r ( 3 . 8 ) N o t e t h a t t h e s u m m a t i o n i n ( 3 . 8 ) i s t a k e n o v e r a l l n +M- 1 M-1 n 2 +M-1 M-1 n +M-1 s M-1 p o s s i b l e s y s t e m s t a t e s K . I t w o u l d be e x t r e m e l y e x p e n s i v e t o c o m p u t e G ( n ) d i r e c t l y f r o m ( 3 . 8 ) . An e f f i c i e n t way o f c o m p u t i n g G ( n ) i s n e c e s s a r y a n d o u r a p p r o a c h i s b a s e d on B u z e n [ 8 ] . D e f i n e an a u x i l i a r y f u n c t i o n [ 2 k . ] ! g ( n , m ) = m s k . r=1 z n {[ n ( x . ) i r ] . K ( s , m ) e S ( n , m ) i=1 r=1 s i r n k . ! • r=1 i r ( 3 . 9 ) N o t e t h a t G ( n ) i n e q u a t i o n ( 3 . 8 ) i s e q u a l t o g ( n , m ) w i t h m 26 b e i n g e q u a l t o M ( t h e number o f s e r v e r s i n t h e n e t w o r k ) . O b s e r v e t h a t t h e s y s t e m s t a t e s K(s,rn) eS(n,m) c a n be g r o u p e d i n t o s e v e r a l g r o u p s by t h e number o f j o b s f r o m e a c h 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 . G r o u p i n g by t h e 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 i n a n e t w o r k w i t h m s e r v e r s , we have g(n,m) = [ Z k. ]! n m s k. r=1 I 1 { Z n [ n ( x . ) i r ] . - - } p = 0 K ( s , m ) e S ( n -p , n « , . . . , i=1 r=1 s 1 I I k. ! n s,m) and k j n 1 = p 1 r=1 i r G r o u p i n g f o r a l l c l a s s e s i n s e r v e r m i n a network w i t h m s e r v e r s , we h a v e g(n,m) = [ i k ] i n n m s k. r=1 Z 1 ... Z s { Z n [ n (x. ) i r ] . } P 1 = 0 P s = 0 I S ^ s ' m ^ e S ( n 1 - p l , i=1 r=1 1 s ,n o-p e,m) n k ; ^ ! (3.10) and'k s.=ps.' V j r=1 i r Now d e f i n e 2 = (P,' P 2 ' •••'» P s^ -m = ( km1' km2' * * * ' k m s ) [ Z k. j ! r=1 i r T . = S n k. ! r = i i r 27 s k . F i * n , <*ir» r= 1 S u b s t i t u t e F . , T . , p , k i n t o ( 3 . 1 0 ) , we g e t l I FC —m 3 n n m g ( n , m ) = Z 1 . . . Z s { Z n [ F . . T . ] } p 1 = 0 p s = 0 £ ( s ' m ) eS(n-p_,m) i = 1 1 N o t i c e t h a t a n d k m = jD ( 3 . 1 1 ) m 2 n { F . . T . } ( 3 . 1 2 ) K ( s , m ) e S ( n 1 ~ p 1 , . . . , n - p ,m) i=1 a n d k m j - P j V j I s summed o v e r a l l t h e s t a t e s w h i c h h a v e t h e same n u m b e r s p^ o f c l a s s j j o b s i n s e r v e r m i n a n e t w o r k w i t h m s e r v e r s . [ i P r l ! r= 1 s p m-1 • z { [ n ( x _ . ) r] . [ n F . . T . ] } K ( s , m ) e S ( n - g , m ) s r=1 m j i . 1 a n d k = p IT p ' [ i P r ] ! r=1 s p_ m-1 n (x ) r z n { F . . T . } s r=1 m r K ( s , m - 1 ) e S ( n - 2 , m - 1 ) i = l 1 1 n P < r=1 ( 3 . 1 3 ) By t h e d e f i n i t i o n o f g ( n , m ) r=1 s p = — [ n (x ) r ] . g (n-p_ ,m-1) s r=1 n p ! r=1 ( 3 . 1 4 ) 28 By c o m b i n i n g e q u a t i o n s ( 3 . 1 4 ) , ( 3 . 1 2 ) a n d ( 3 . 1 1 ) , we o b t a i n [ 2 p ]! g ( n , m ) = Z 1 . . . Z s { [ II ( x ) r ] P l = 0 p =0 s r=1 m r n p ! r=1 . g ( n ] - p 1 , n 2 ~ p 2 , . . . , n s ~ p s , m - 1 ) } . . . . . ( 3 . 1 5 ) O b s e r v e f r o m ( 3 . 9 ) t h a t g ( n , 0 ) = 1 s [ Z n ] ! s n ^ i=1 g ( n , D = [ n (x ) r ] . ( 3 . 1 6 ) r= 1 s Z n ! i = 1 r T h e 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 . 1 5 ) a n d t h e i n i t i a l c o n d i t i o n ( 3 . 1 6 ) c o m p l e t e l y d e f i n e t h e a l g o r i t h m f o r c o m p u t i n g g ( n , m ) a n d h e n c e G ( n ) w h i c h i s e q u a l t o g ( n , m ) when m i s t h e number o f s e r v e r s i n t h e n e t w o r k c o n s i d e r e d . Now we d e f i n e t h r e e a d d i t i o n a l t e r m s : S z ( n , m ) = { ( k n , . . . , k 1 s , , k ( 2 - l ) , 1 ' - - " k ( Z - 1 ) , s ' K ( z + 1 ) , 1 ' - - - ' k ( 2 + l ) , s ' . , ' K ( m + 1 ) , 1 ' * * * ' K ( m + 1 ) , s i m+1 I Z k . =n , & k. > 0 , V r , 1 r = 1 i r r ' i r ' ' r * z ( 3 . 1 7 ) 29 [ I k i r]! m+1 s k. r=1 g ( n , m ) = Z U {[ n ( x . ) i r ] . } K ( s , m ) e S ( n , m ) i=1 r=1 s z i * z n k. ! r=1 ( 3 . 1 8 ) a n d , s [ Z k. ] ! s k. r-1 i r H i = [ n ( x . ) i r ] . — ( 3 . 1 9 ) r=1 s n k. ! r-1 i r R e p l a c e m by m-1 a n d s u b s t i t u t e s H . i n t o t h e ( 3 . 1 8 ) , we g e t m I i g ( n , m - 1 ) = Z TI H. K ( s , m - 1 ) e S ( n , m - 1 ) i=1 1  2 i * z I f z i s e q u a l t o m, we h a v e g z ( n _ , m - l ) == g ( n , m - l ) . S i n c e r e l a b e l i n g w i l l n o t c h a n g e t h e f u n c t i o n G ( n ) , c o m b i n i n g t h e a b o v e o b s e r v a t i o n w i t h ( 3 . 1 5 ) a n d ( 3 . 1 8 ) we g e t [ Z p ]< n n r=1 s p G ( n ) = g ( n , M ) = Z 1 . . . Z s { [ n (x ) r ] p =0 p =0 s r=1 s n p ! r=1 r ( 3 . 2 0 ) . g 2 ( n 1 - p 1 , n 2 - p 2 , . . . , n s - p s , M - l ) } z < M F o l l o w i n g s i m i l i a r d e r v i a t i o n a s t h a t o f g ( n , m ) s k i p p i n g a l l r e f e r e n c e t o t h e i n d e x z . 30 we g e t g 2 ( n , m ) [ 2 p i ! n n r=1 s p z . . . z s { [ n ( x m r ) r ] p =0 p =0 s r=1 m r n P ! r=1 • 9 2 ( n 1 - p 1 , n 2 ~ p 2 , . . . , n s - p s , m - 1 ) } , m < z [ 2 p i ! n n r=1 s p Z 1 . . . Z s { [ n ( x , + n ) r ] p , = 0 p = 0 s r-1 ( m + l ) ' r n p ! r=1 • g z ( n 1 _ P v n 2 - p 2 , . . . , n s - p s , m - 1 )} , m > z ( 3 . 2 1 ) 9 z ( n , l ) = s n [ n ( x l r ) r ] r= 1 s n [ n ( x , r ) r ] r = l s [ £ n ] ! i=1 s Z n ! i = 1 [ Z n ] ! i = 1 Z n ! i = l z > 1 z = 1 ( 3 . 2 2 ) U t i l i z a t i o n o f s e r v e r s T h e t o t a l u t i l i z a t i o n o f s e r v e r z i n a n e t w o r k w i t h M s e r v e r s w i t h l o a d n i n t h e n e t w o r k , u ( M ) , i s g i v e n b y : z f n 31 u (M) = L P ( K ( s , M ) ) K ( s , M ) e S ( n , M ) - ~ & k > 0 V r z r H o w e v e r , i t i s e a s i e r t o c o m p u t e t h e t o t a l i d l e t i m e a n d s u b s t r a c t i n g i t f r o m 1 t o g e t t h e u t i l i z a t i o n o f t h e s e r v e r . T h e t o t a l i d l e t i m e o f s e r v e r z i n a n e t w o r k w i t h M s e r v e r s i s g i v e n b y : I (M) = Z P ( K ( s , M ) ) Z ' - K ( s , M ) e S ( n , M ) ^ a n d k =0 V r z r 1 s k = L .{[ II ( x 7 ) z r ] . g ( n , M - U } G ( n ) K ( s , M ) e S ( n , M ) r=1 z r z a n d k =0 z r g z ( n , M - 1 ) G ( n ) w i t h u (M) = 1 - 1 (M) z , n z , n T h e p a r t i a l u t i l i z a t i o n u ( M , r ) o f s e r v e r z f o r c l a s s r j o b s w i t h M s e r v e r s i n t h e n e t w o r k i s g i v e n by k u n ( M , r ) = L P ( K ( s , M ) ) . z ^ — Z ' - K ( s , M ) e S ( n , M ) - s k >0 Z L k r=1 z r 32 i n M k = Z z { Z n T. . F . . — = £ — } G ( n ) p=1 K ( s , M ) e $ z ( n 1 , i=1 s • • • ' " ( z - O ' r Z , k z r n z " p ' n ( z + l ) ' r = 1 . . . , n 7 a n d k =p z 1 ^ F o l l o w i n g t h e same p r o c e d u r e f o r d e r i v i n g g (n ,m) we o b t a i n t h e 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 z , j o b c l a s s r , w i t h M s e r v e r s i n t h e n e t w o r k , d e n o t e d by u z n ( m , r ) w i t h m e q u a l s t o M , w h i c h c a n be c o m p u t e d f r o m e q u a t i o n s ( 3 . 2 3 ) , ( 3 . 2 2 ) a n d ( 3 . 2 1 ) , 1 n , n , n n , , n u ( m , r ) = Z . . . Z Z Z . . . Z Z ' ° - G ( n ) P l = 0 p z _ 1 = 0 p z =1 p z + 1 = 0 p s = 0 [ £ P j ! P z r=1 s p { ^ n { x } r ] . g ( n - e , m - 1 ) } s s r=1 2 p r 1 1 P r ! r=1 r=1 ( 3 . 2 3 ) F o r a n y p j i n t h e s u m m a t i o n , i f j i s n o t b e t w e e n 1 a n d s , n . d e l e t e t h e e n t i r e s u m m a t i o n Z J f r o m e q u a t i o n ( 3 . 2 3 ) . T h i s c o m p l e t e s t h e s o l u t i o n o f t h e g e n e r a l m o d e l . I n o u r e x a m p l e , s i s two a n d M i s t h r e e . T h u s , t h e 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 1 f o r c l a s s 2 j o b s i s 33 u 1 , n ( 3 ' 2 ) 1 n i n 2 P 1 ( P ! + P 2 ) ! Z' { G ( n ) p 1 = 0 p 2 =1 ( P 1 + P 2 ) P ! ! P 2 [ ( x n ) P l . ( x 1 2 ) P 2 ] . g z ( n - p , 2 ) } ( 3 . 2 4 ) T h e t h r o u g h p u t r a t e o f c l a s s r j o b s i n o u r m o d e l f o r n 1 i n t e r a c t i v e a n d n 2 b a t c h j o b s i n t h e memory l o o p i s g i v e n b y : 3 T (n) = u ( 3 , r ) * n * (1 - Z q .) r 1 ' £ 1 r j = 2 1 3 ( 3 . 2 5 ) U s i n g e q u a t i o n s ( 3 . 2 ) a n d ( 3 . 3 ) , we g e t L r ( y ) " D r - 1 L r ( y ) . M l r L r . ( y ) ( C r + D r + 1 / L r ( y ) - D r ) - 1 L r ( y ) . M 1 r L £ ( y ) . c E c£__ L r ( y ) . M 1 r M l r S u b s t i t u t e i n t o ( 3 . 2 5 ) , t h e t h r o u g h p u t r a t e i s T f ( n ) = u 1 n ( 3 , r ) * C r ( 3 . 2 6 ) 34 3 . 3 F o r m u l a t i o n o f t h e o p t i m a l c o n t r o l p r o b l e m N t e r m i n a l s r i f-4 _ > 4 T ] [ ( n 1 , n 2 ) a g c r r e g a t e s e r v e r , SYSTEM (N 1 # N 2 ) T 2 ( n r n 2 ) F i g u r e 3 . 3 T h e s y s t e m m o d e l w i t h t h e memory l o o p r e p l a c e d by a n a g g r e g a t e s e r v e r We r e p l a c e t h e memory l o o p by a s i n g l e a g g r e g a t e s e r v e r ( F i g u r e 3 . 3 ) w i t h t h r o u g h p u t r a t e o f c l a s s r j o b s e q u a l t o T r ^ n 1 ' n 2 ^ ^ o r t * i e s y s t e m s t a t e ( n ^ n ^ , r = 1 , 2 . I n a s m a l l e n o u g h t i m e i n t e r v a l h , we c a n a s s u m e no s i m u l t a n e o u s e v e n t s . L e t t h e v e c t o r s d e n o t e s y s t e m s t a t e s . L e t t h e v e c t o r u ( i ) • = ( u ^ U j ) be t h e c o n t r o l f o r s t a t e i. T h e v a l u e u ^ i s t h e n u m b e r o f c l a s s j j o b s t h a t s h o u l d be i n memory i n t h e n e x t i n t e r v a l . L e t p j [ j ^ u ( i j ) d e n o t e t h e t r a n s i t i o n p r o b a b i l i t i e s g o i n g f r o m s t a t e i_ t o s t a t e j when c o n t r o l u(_i) i s a p p l i e d . L e t N be t h e number o f t e r m i n a l s . L e t m2 be t h e maximum number o f c l a s s 2 j o b s a l l o w e d i n t h e s y s t e m . 35 C a s e (1) C o n t r o l (a ) I n t h i s s c h e m e , t h e s y s t e m s t a t e i s d e f i n e d by t h e t o t a l number o f j o b s i n e a c h c l a s s i n t h e s y s t e m , i . e . , S y s t e m s t a t e i s N = ( N ^ N , ^ ) a n d C o n t r o l s p a c e i s U ( N ) = ( u | u - N }. T h e r e f e r e n c e s t a t e t d e f i n e d i n t h e o r e m 2 i s (N,m2) w h i c h c a n be r e a c h e d f r o m a n y o t h e r s t a t e s f o r a n y c o n t r o l u. <PBh, f o r i = ( N r N 2 ) , j = ( N r N 2 + l ) , N 2<m2 ( N - N ^ ^ h , f o r i = ( N . 1 , N 2 ) , 2=(N 1 + 1 , N 2 ) , T ^ u j h , f o r j. = ( N 1 , N 2 ) , j = ( N l - 1 , N 2 ) , N ^ O T 2 ( u ) h , f o r i = ( N 1 , N 2 ) , j = (U ] , N 2 ~ 1 ) ,- N 2 > 0 1 - sum o f a b o v e f o r i = j 0 o t h e r w i s e ( 3 . 2 7 ) C a s e (2) C o n t r o l (b) S y s t e m s t a t e i s [ N | n ] = ( N 1 , N 2 , n 1 , n 2 ) . I n t h i s s c h e m e , t h e s y s t e m s t a t e i s d e f i n e d by t h e t o t a l number o f j o b s i n e a c h c l a s s a s w e l l a s t h e number o f j o b s i n e a c h c l a s s i n t h e memory l o o p , i . e . , C o n t r o l s p a c e i s U ( [ N | n ] ) = { u | n < u < N }. T h e r e f e r e n c e s t a t e t d e f i n e d i n t h e o r e m 2 i s ( N , m 2 , 0 , 0 ) . 36 P i . ( u ) -0 B h , f o r i_= 1= ( N - N 1 )<ATh, f o r i_= 1= T 1 ( u ) h , T 2 ' ( u ) h , f o r i_= i = f o r i = i = N , , N 0 , n , , n 0 ) , N 1 - sum o f a b o v e 0 , N 2 + 1 , n , n 2 ) , N 0 < m2 ' N 2 ' n l , n 2 * ' + 1 , N 2 , n 1 , n 2 ) / N 2 , n 1 ,r>2) , - 1 , N 2 , n 1 - 1 , n 2 ) , N n i ; n 2 ) , , N 2 - 1 , n 1 , n 2 - 1 ) f o r i_=j o t h e r w i se n > 0 n 2 > 0 ( 3 . 2 8 ) R e c a l l t h a t we want t o f i n d an o p t i m a l s t a t i o n a r y p o l i c y w h i c h c o n t r o l s t h e number o f j o b s t o be a d m i t t e d i n t o t h e memory l o o p s u c h t h a t t h e mean w e i g h t e d sum o f t h e number o f j o b s o f e a c h c l a s s i n t h e s y s t e m i s m i n i m i z e d . T h e p r o b l e m 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 p r o c e s s on t h e a v e r a g e c o s t c r i t e r i o n . T h a t i s N-1 m i n J = m i n l i m ( 1 / N ) Z P G N - - > ° ° k = 0 where P^ i s t h e 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 e l e m e n t s P . . ( u ) d e f i n e d i n e q u a t i o n s ( 3 . 2 7 ) and ( 3 . 2 8 ) f o r t h e two i n -d i f f e r e n t c a s e s a n d g ( 0 , 0 , u 1 , u 2 ) g ( N , m 2 , u 1 , u 2 ) g ( N , , N 2 , u 1 , u 2 ) = W * N 1 + N 2 t h e w e i g h t W, w h i c h i s n o r m a l l y g r e a t e r t h a n o n e , r e f l e c t s t h e 37 i m p o r t a n c e o f i n t e r a c t i v e j o b s r e l a t i v e t o t h a t o f b a t c h j o b s . N o t e t h a t f o r w=1, t h e a v e r a g e number o f j o b s i n t h e s y s t e m i s m i n i m i z e d . By c h o o s i n g a p p r o p r i a t e g ( _ i , u ( _ i ) ) , o t h e r p e r f o r m a n c e i n d i c e s c a n be o p t i m i z e d . T h e p r o b l e m c a n t h e n be s o l v e d by t h e p o l i c y i t e r a t i o n a l g o r i t h m d e s c r i b e d i n C h a p t e r I I . 3 . 4 C o m p u t a t i o n a l C o s t f o r c o n t r o l p o l i c i e s (a) a n d (b) T h e o v e r h e a d c o s t c o n s i s t s o f c o m p u t a t i o n a l t i m e i n number o f m u l t i p l i c a t i o n s , d i v i s i o n s a n d C A S ( C o m p a r s i o n s , a d d i t i o n s , s u b s t r a c t i o n s ) a n d t h e memory r e q u i r e d t o c o m p u t e t h e c o n t r o l p o l i c y . We w i l l c o n s i d e r c o m p u t a t i o n a l t i m e f i r s t . N o t e t h a t w i t h o u r c h o i c e o f g ( i , u ( i ) ) i n c o n t r o l s (a ) a n d ( b ) , t h e c o m p u t a t i o n o f t h e g ( i , u ( i ) ) f u n c t i o n r e q u i r e s o n l y one m u l t i p l i c a t i o n a n d C A S . < 3 . 4 . 1 C o m p u t a t i o n a l T i m e (1) I n c o m p u t i n g p ^ j ( u ( i ) ) I n c o m p u t i n g P ^ j ( u ( i ) ) f o r a n y i , j , u ( i ) r e q u i r e s o n l y one m u l t i p l i c a t i o n . T h e number o f m u l t i p l i c a t i o n s i s p r o p o r t i o n a l 4 t i m e s t h a t o f t h e number o f p o s s i b l e s t a t e s s i n c e a t a n y g i v e n s t a t e , o n l y f o u r o t h e r s t a t e s c a n be r e a c h e d f r o m a n y s t a t e i n one s t e p . T h e p o s s i b l e s t a t e s a r e : { ( N 1 , N 2 , n 1 , n 2 ) | Nj<N, N 2 <m2, n ^ N ^ n 2 ~ N 2 * T h e t o t a l number o f s t a t e s i s t h e number o f e n t r i e s i n t h e f o l l o w i n g s u m m a t i o n . 38 N N1 m2 N2 Z Z Z Z N1=0 n1=0 N2=0 n2=0 C o n s i d e r t h e (N , n ) p a i r , when N1=0, n1=0 when N1 = 1, n1=0 , 1 1 e n t r y 2 e n t r i e s when N1=N, n1=0 N (N+1) e n t r i e s U s i n g t h e f o r m u l a , 1 + 2 + . . . . + n = ( n + l ) n / 2 , we f i n d t h a t t h e t o t a l number o f s t a t e s i s I t r e q u i r e s o n e m u l t i p l i c a t i o n , no d i v i s i o n a n d a t most one CAS t o c o m p u t e t h e P ^ j f o r a n y i , j g i v e n t h e t h r o u g h p u t r a t e o f a n y c l a s s j o b s f o r a n y s y s t e m s t a t e . T h e m a j o r c o m p u t a t i o n a l t i m e c o s t i s t h e 0 ( ( N + 1 ) x ( m 2 + 1 ) x ( N + 2 ) x ( m 2 + 2 ) ) m u l t i p l i c a t i o n s 2 ==> 0( (N+m2) ) m u l t i p l i c a t i o n s , (2 ) I n c o m p u t i n g t h r o u g h p u t r a t e I t i s o n l y n e c e s s a r y t o c o m p u t e t h e p a r t i a l u t i l i z a t i o n o f t h e c p u o n l y . L e t S be t h e t o t a l number o f s t a t e s w h i c h i s e q u a l t o ( N + 1 ) x ( m 2 + 1 ) . (a ) q . . a n d x i s a f u n c t i o n o f n +n~ w h i c h r e q u i r e s a t mr 1 2 ^ mos t o n e d i v i s i o n . T h e r e f o r e , i t r e q u i r e s 0(N+m2) d i v i s i o n s . (b ) F r o m e q u a t i o n s ( 3 . 2 2 ) a n d ( 3 . 2 1 ) , c o m p u t i n g q^(m,r) r e q u i r e s 0 ( S . S / 4 ) m u l t i p l i c a t i o n s a n d C A S . T h i s a s s u m e s a l l t h e ( N + ! ) ( N + 2 ) / 2 x (m2+1) (m2+2) /2 ( 3 . 2 9 ) 39 f a c t o r i a l a n d t h e power o f t h e x ' s a r e c o m p u t e d o n c e o n l y . 3 2 O t h e r w i s e , we g e t O ( S ) m u l t i p l i c a t i o n s a n d 0 ( S / 4 ) C A S . F r o m e q u a t i o n ( 3 . 2 4 ) , t h e r e a r e a n o t h e r 0 ( S . S / 4 ) o p e r a t i o n s . T h e m a j o r c o m p u t a t i o n a l t i m e c o s t i n c o m p u t i n g t h e c p u u t i l i z a t i o n i s t h e r e f o r e 0 ( S / 4 + S . S / 4 ) = 0 ( S 2 / 4 ) = 0 ( ( N x m 2 ) 2 / 4 ) m u l t i p l i c a t i o n s a n d C A S . N o t e t h a t t h e a b o v e c o s t i s t h e same f o r c o n t r o l s (a ) a n d ( b ) . (3) I n p o l i c y i t e r a t i o n a l g o r i t h m F o r t h e two d i f f e r e n t c o n t r o l p o l i c i e s . C a s e (1 ) C o n t r o l (a ) w i t h s y s t e m s t a t e N a n d g ( [ N | n ] , u ( [ N | n ] ) ) = W * N 1 + N 2 L e t S Q be t h e t o t a l number o f p o s s i b l e s t a t e s w h i c h i s e q u a l t o t h e p r o d u c t , o f t h e number o f s t a t e s o f e a c h j o b c l a s s f o r a l l t h e j o b c l a s s e s . T h e r e f o r e , S = i s e q u a l t o (N+1)x (m2+1) . F r o m s e c t i o n 2 . 4 w i t h K 1 = 1 , K 2 = 0 , K 3 = 1 , t h e c o m p u t a t i o n a l o v e r h e a d i s 0 ( 4 S 3 / 3 ) = 0 ( 4 ( N x m 2 ) 3 / 3 ) m u l t i p l i c a t i o n s a n d C A S . a T h i s i s l a r g e r t h a n t h a t o f c o m p u t i n g t h e t h r o u g h p u t r a t e a n d t h e P ^ j ( u ( i ) ) . T h e r e f o r e , t h e o v e r a l l o v e r h e a d i s 3 0 ( 4 ( N x m 2 ) / 3 ) m u l t i p l i c a t i o n s a n d C A S . C a s e (2) C o n t r o l (b) w i t h s y s t e m s t a t e [ N | n ] a n d g ( [ N | n ] , u ( [ N | n ] ) ) = W * N ] + N 2 L e t S^ be t h e t o t a l number o f s y s t e m s t a t e s . F r o m ( 3 . 2 7 ) , i t i s e q u a l t o 4 0 [ (N+1) x (m2+1) x (N+2) x ( m 2 + 2 ) ] / 4 . F r o m s e c t i o n 2 . 4 w i t h K 1 = 1 , K 2 = 0 , K 3 = 1 , t h e m a j o r c o m p u t a t i o n a l o v e r h e a d i s 0 ( 4 S 3 / 3 ) = 0 ( ( N x m 2 ) 6 / ( 3 x 4 5 ) ) m u l t i p l i c a t i o n s a n d C A S . I n t h i s c a s e , t h e m a j o r i t y o f c o m p u t a t i o n a l t i m e c o s t i s a l s o i n t h e p o l i c y i t e r a t i o n a l g o r i t h m . T h e r e f o r e , t h e o v e r a l l o v e r h e a d i s 0 ( N x m 2 ) 6 / ( 3 x 4 5 ) ) m u l t i p l i c a t i o n s a n d C A S . 3 . 4 . 2 Memory R e q u i r e m e n t F o r b o t h c o n t r o l ( a ) a n d c o n t r o l ( b ) , t h e l a r g e s t memory r e q u i r e m n t i s s t e p (2) o f t h e p o l i c y i t e r a t i o n a l g o r t i h m i n a t h e m a t r i x o f s i z e ( S a + 1 ) a n d (S^+1) r e s p e c t i v e l y i s f o r m e d . T h e r e f o r e , t h e memory r e q u i r e m e n t o f c o n t r o l ( a ) a n d (b) a r e 2 2 0 ( S ) a n d 0 ( S , ) w o r d s r e s p e c t i v e l y . 41 CHAPTER I V . I N T E R P R E T I N G THE R E S U L T S I n t h i s c h a p t e r , we w i l l d i s c u s s t h e r e s u l t s o b t a i n e d i n c h a p t e r I I I . We c a n c o m p u t e t h e o p t i m a l p o l i c y u s i n g t h e e q u a t i o n s i n c h a p t e r s I I a n d I I I . T h e p a r a m e t e r s i n t h e m o d e l a r e : 1 / 0 T = mean t e r m i n a l " t h i n k " t i m e 1 / 0 D = mean b a t c h i n t e r a r r i v a l t i m 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 = maximum 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 a T , b T , a B , a B = p a r a m e t e r s o f t h e l i f e t i m e f u n c t i o n f o r i n t e r a c t i v e a n d b a t c h j o b s ( D f f o r r = 1 ,2 ) • = mean i n t e r a c t i v e a n d b a t c h I / O r e q u e s t r a t e s r e s p e c t i v e l y = mean p a g i n g s e r v i c e r a t e ^2 = mean I / O s e r v i c e r a t e ( c p u T , c p u B ) = ( C r f o r r = 1 , 2 ) = mean t o t a l i n t e r a c t i v e a n d b a t c h c p u s e r v i c e r a t e s O n l y t h e e f f e c t s o f t h e p a r a m e t e r s c p u T and c p u B ( r e p r e s e n t i n g v a r i a t i o n i n p r o g r a m c h a r a c t e r i s t i c s ) w i l l be s t u d i e d h e r e . A l l t h e o t h e r p a r a m e t e r s a r e k e p t c o n s t a n t . The c o n t r o l p o l i c i e s (a ) a n d (b) i n t h e t a b l e s a r e o b t a i n e d u s i n g t h e two p o l i c y i t e r a t i o n a l g o r i t h m s w i t h t h e s t a t e s b e i n g N a n d 42 [ N | n ] r e s p e c t i v e l y . T h e t h r o u g h p u t r a t e a n d r e s p o n s e t i m e a r e o b t a i n e d f r o m a s i m u l a t o r o f t h e m o d e l . T h e c o n t r o l p o l i c i e s a r e f u n c t i o n s o f t h e w e i g h t a n d t h e p a r a m e t e r s o f t h e m o d e l s p e c i f i e d a b o v e . T h e c o n f i d e n c e i n t e r v a l s i n t h e t a b l e s a r e a t 95% l e v e l a n d t h e y a r e o b t a i n e d f r o m t h e s i m u l a t o r u s i n g t h e t - d i s t r i b u t i o n w i t h s a m p l e s i z e n = l O . T h e o u t p u t o f t h e s i m u l a t o r i s v e r y s e n s i t i v e t c s m a l l v a r i a t i o n i n t h e e x a c t s e q u e n c i n g o f t h e j o b s a r r i v a l s a n d t h e i r c p u t i m e r e q u i r e m e n t s . T h i s i s c a u s e d by t h e i n h e r e n t i l l - c o n d i t i o n i n g o f t h e s i m u l a t i o n p r o b l e m . I n o r d e r t o o b t a i n more a c c u r a t e r e s u l t , more i n d e p e n d e n t r u n s a r e n e e d e d . A l t h o u g h t h e v a r i a t i o n s a t c o n f i d e n c e l e v e l 95% o b t a i n e d f o r n=1U a r e q u i t e l a r g e , t h e mean v a l u e s o f t h e p e r f o r m a n c e i n d e x w i t h c o n t r o l (b) i s g e n e r a l l y b e t t e r t h a n t h a t w i t h c o n t r o l ( a ) . H o w e v e r , f r o m t h e t h e o r e t i c a l o v e r h e a d a n a l y s i s , t h e o v e r h e a d i n c p u t i m e and memory r e q u i r e m e n t i n c o n t r o l (b) i s a b o u t s q u a r e o f t h a t i n c o n t r o l ( a ) . I t i s p o s s i b l e t o c o m p u t e t h e e x p e c t e d v a l u e o f t h e p e r f o r m a n c e i n d e x a n a l y t i c a l l y f o r c o n t r o l (b ) f r o m t h e p o l i c y * i t e r a t i o n a l g o r i t h m . T h e v a l u e o f t h e p e r f o r m a n c e i n d e x J^. c a n be o b t a i n e d f r o m t h e a l g o r i t h m . D i f f e r e n t p e r f o r m a n c e i n d i c e s c a n be o b t a i n e d by c h o o s i n g t h e a p p r o p r i a t e f u n c t i o n g ( i , u ( i ) ) . F o r e x a m p l e : w i t h g ( i , u ( i ) ) = N , * t h e v a l u e J = </> i s t h e mean number o f c l a s s r ir v u * j o b s i n t h e s y s t e m . 43 4 .1 T h e E f f e c t s o f W o r k l o a d F i g u r e ( 4 . 5 . 1 ) a n d f i g u r e ( 4 . 5 . 2 ) a r e g r a p h s o f t h r o u g h p u t r a t e a n d r e s p o n s e t i m e v e r s u s t h e work l o a d c p u T w h i c h i.s e q u a l t o c p u B . T h e o t h e r p a r a m e t e r s a r e f i x e d as s p e c i f i e d i n p a g e 4 9 . I n t a b l e s ( 4 . 2 . 1 ) t o ( 4 . 8 . 2 ) , t h e c o n t r o l p o l i c i e s , t h r o u g h p u t r a t e , r e s p o n s e t i m e , a n d c o m p u t a t i o n a l t i m e a r e l i s t e d f o r v a r i o u s v a l u e s o f c p u T a n d c p u B . T h e mean r e s p o n s e t i m e a n d t h r o u g h p u t r a t e o f a c l a s s r j o b i s u s u a l l y b e t t e r t h a n t h o s e o f a c l a s s z j o b w i t h t h e same w e i g h t i f i t s l o a d i s l i g h t e r t h a n t h a t o f c l a s s z . T h e j o b s w i t h s m a l l e r c p u t i m e r e q u i r e m e n t w i l l n o r m a l l y h a v e b e t t e r t h o r u g h p u t r a t e i n j o b s p e r s e c o n d t h a n t h a t w i t h l a r g e r c p u t i m e r e q u i r e m e n t s . When t h e t o t a l work l o a d i s l i g h t , i . e . , c p u T a n d c p u B l a r g e , t h e p e r f o r m a n c e o f t h e s y s t e m i s a l m o s t t h e same f o r t h e c a s e s w i t h no c o n t r o l p o l i c y , c o n t r o l ( a ) a n d c o n t r o l ( b ) . T h i s i s t o be e x p e c t e d s i n c e c o n t r o l i s n o t n e c e s s a r y when t h e work l o a d i s n o t h e a v y e n o u g h t o s a t u r a t e t h e s y s t e m . T h e s i m u l a t e d r e s u l t f o r c o n t r o l (a ) were b a s e d on an a p p r o x i m a t i o n o f t h e m o d e l w h i c h w i l l c a u s e u n n e c e s s a r y d e l a y i n a d m i t t i n g j o b s b e c a u s e j o b s a r e a d m i t t e d o n l y when t h e r e a r e no j o b s i n t h e memory l o o p . T h e r e f o r e , i n t h e c a s e o f v e r y l i g h t l o a d , t h e s y s t e m p e r f o r m a n c e w i t h no c o n t r o l i s a c t u a l l y b e t t e r t h a n t h a t w i t h c o n t r o l ( a ) . T h e s y s t e m p e r f o r m a n c e u n d e r c o n t r o l (b) i s u s u a l l y b e t t e r t h a n t h e o t h e r two c a s e s . T h e d i f f e r e n c e i n p e r f o r m a n c e b e t w e e n t h e c a s e s i n c r e a s e s w i t h work l o a d . 44 4 . 2 T h e E f f e c t o f t h e W e i g h t I n f i g u r e s ( 4 . 1 . 1 ) t o ( 4 . 4 . 2 ) , t h e t h r o u g h p u t r a t e a n d r e s p o n s e t i m e f o r some v a l u e s o f c p u T a n d c p u B v e r s u s t h e w e i g h t a r e p l o t t e d . T h e c p u u t i l i z a t i o n s f o r d i f f e r e n t number o f i n t e r a c t i v e a n d b a t c h j o b s i n t h e memory l o o p a r e l i s t e d i n t a b l e ( 4 . 0 ) . N o t e t h a t i t i s i n d e p e n d e n t o f t h e a r r i v a l r a t e s a n d t h e c p u t i m e s e r v i c e r e q u i r e m e n t s . The c o n t r o l p o l i c i e s f o r v a r i o u s w e i g h t s w i t h c p u T a n d c p u B b e i n g e q u a l t o 0 . 3 a r e l i s t e d i n t a b l e s ( 4 . 1 . 2 ) t o ( 4 . 1 . 6 ) . A s e x p e c t e d , when t h e w e i g h t i n c r e a s e s , a h i g h e r p r i o r i t y i s g i v e n t o i n t e r a c t i v e j o b s . T h i s i s r e f l e c t e d i n t h e c o n t r o l p o l i c y i n w h i c h f o r some s t a t e s , more i n t e r a c t i v e j o b s a r e a d m i t t e d . A s a r e s u l t , t h e p e r f o r m a n c e o f t h e i n t e r a c t i v e j o b s i m p r o v e s a t t h e e x p e n s e o f t h e b a t c h j o b s when t h e w e i g h t i n c r e a s e s . When t h e work l o a d d e c r e a s e s , t h e e f f e c t s o f t h e w e i g h t a l s o d e c r e a s e s f o r b o t h c a s e s . C o n t r o l (b) i s more s e n s i t i v e t o t h e i n c r e a s e i n w e i g h t t h a n c o n t r o l ( a ) . T h i s i s p r o b a b l y c a u s e d by t h e f a c t t h a t t h e c o n t r o l p o l i c y i s a p p l i e d more o f t e n . T h e t h r o u g h p u t r a t e a n d r e s p o n s e t i m e a p p r o a c h c e r t a i n l i m i t i n g v a l u e s a s t h e w e i g h t a p p r o a c h e s i n f i n i t y . I n t h e c a s e o f c p u T = c p u B = 0 . 3 , a n y w e i g h t g r e a t e r t h a n f i v e w i l l g i v e s i m i l a r r e s u l t s . A l s o n o t e t h a t t h e b e h a v i o u r o f t h e s y s t e m u n d e r b o t h c o n t r o l (a) a n d c o n t r o l (b) a r e l e s s r e g u l a r when t h e d i f f e r e n c e b e t w e e n c p u B a n d c p u T becomes l a r g e . 45 4 . 3 T h e D o m a i n o f t h e P o l i c y T h e p o l i c i e s i n t h e t a b l e s a r e f u n c t i o n s o f a l l t h e p a r a m e t e r s i n t h e m o d e l . Among t h e m , o n l y t h e a r r i v a l r a t e , t h e c p u t i m e r e q u i r e m e n t a n d t h e I / O r e q u e s t r a t e , a r e j o b r e l a t e d . T o e n s u r e t h a t t h e c o n t r o l p o l i c y i s v a l i d , we c a n m o n i t o r t h e i n p u t p a r a m e t e r s o v e r a f i x e d p e r i o d o f t i m e a n d r e c o m p u t e t h e c o n t r o l p o l i c y i f t h e y a r e v e r y d i f f e r e n t f r o m t h e e x p e c t e d v a l u e s . A s i m p l y way i s t o m o n i t o r t h e v a l u e o f * 3 7 r * = E { g ( i , u ( i ) ) } . I n t h i s c a s e , i t i s t h e w e i g h t e d sum o f t h e mean number o f i n t e r a c t i v e a n d b a t c h j o b s . I f i t i s o u t s i d e a c e r t a i n K l e v e l c o n f i d e n c e i n t e r v a l o v e r a t i m e p e r i o d T , t h e c o n t r o l p o l i c y s h o u l d be r e c o m p u t e d . 4 . 4 T h e E r r o r i n t h e S o l u t i o n A l t h o u g h t h e o v e r h e a d i n t h e c o n t r o l (b) c a s e i s t o o h i g h t o be p r a c t i c a l , t h e i m p r o v e m e n t o f t h e c o n t r o l (b) o v e r t h a t o f t h e c o n t r o l (a ) c a n be u s e d a s an e s t i m a t e o f t h e e r r o r f r o m t h e o p t i m u m f o r c o n t r o l (a) i f we a s s u m e t h a t t h e e r r o r i n c o n t r o l (b) i s r e l a t i v e l y s m a l l c o m p a r e d t o t h a t i n c o n t r o l ( a ) . An a n a l y t i c a l e r r o r a n a l y s i s f o r t h e c o n t r o l ( a ) i s e x t r e m e l y d i f f i c u l t i f n o t i m p o s s i b l e due t o t h e m o d e l a p p r o x i m a t i o n . F r o m t h e n u m e r i c a l r e s u l t s i n t h e t a b l e s a n d f i g u r e s , we f i n d t h a t t h e d i f f e r e n c e b e t w e e n c o n t r o l ( a ) a n d c o n t r o l (b ) i s l a r g e r a s t h e l o a d i n c r e a s e s ( f i g u r e s ( 4 . 5 . 1 ) a n d ( 4 . 5 . 2 ) ) . T h e o t h e r s o u r c e o f e r r o r i n c o n t r o l s (a ) a n d (b.) i s f r o m t h e d e c o m p o s i t i o n o f t h e n e t w o r k w h i c h i s a s s u m e d t o be s m a l l a n d w i l l be i g n o r e d h e r e . 4 6 CHAPTER V . CONCLUSION I n [ 2 9 ] , L o p r o p o s e d t h e c o n t r o l p o l i c i e s w h i c h i s b a s e d on m a t h e m a t i c a l m o d e l i n g a n d c o n t r o l t h e o r y . T h e c o n t r o l p o l i c y i s d y n a m i c a n d i s a f u n c t i o n o f t h e s y s t e m s t a t e . I t i s shown i n [ 2 9 ] t h a t t h e c o n t r o l p o l i c y w i l l g i v e g o o d t o t a l p e r f o r m a n c e a n d g u a r a n t e e a maximum b a t c h r e s p o n s e t i m e . I n t h i s t h e s i s , we h a v e made a few e x t e n t i o n s t o [ 2 9 ] . The s t a t e s p a c e o f t h e p r o b l e m i s e x t e n d e d t o g i v e a more p r e c i s e r e p r e s e n t a t i o n o f t h e m o d e l r e s u l t i n g i n c o n t r o l (b) i n s t e a d o f t h e c o n t r o l (a) i n [ 2 9 ] . T h e c o m p u t a t i o n a l o v e r h e a d f o r b o t h c a s e s i s e s t i m a t e d . I t i s t o o l a r g e t o be p r a c t i c a l f o r t h e c o n t r o l (b) c a s e b u t i t i s a c c e p t a b l e f o r t h e c o n t r o l (a ) c a s e . A l s o , u s i n g t h e r e s u l t f r o m t h e c o n t r o l (b) c a s e , we f i n d t h a t t h e e r r o r i n t h e c o n t r o l ( a ) c a s e i s s m a l l . H o w e v e r , i t i n c r e a s e s when t h e l o a d i n c r e a s e s . B o t h c o n t r o l p o l i c i e s w i l l g i v e g o o d t h r o u g h p u t r a t e a n d r e s p o n s e t i m e . By a d j u s t i n g t h e w e i g h t , we c a n g e t a r e a s o n a b l e s e r v i c e f o r a l l c l a s s e s o f j o b s . By c h o o s i n g t h e a p p r o p r i a t e g ( i , u ( i ) ) , d i f f e r e n t p e r f o r m a n c e i n d i c e s c a n be s t u d i e d . I n f a c t , t h e c o s t f o r l o a d c o n t r o l c a n a l s o be i n c l u d e d i n t h e g ( i , u ( i ) ) f u n c t i o n . A l l t h e g ( i , u ( i ) ) f u n c t i o n s p r o p o s e d s o f a r a r e f u n c t i o n s o f t h e s t a t e a t t h e n e x t t i m e i n t e r v a l o n l y . We c a n c h o o s e g ( i , u ( i ) ) so t h a t i t i s a f u n c t i o n o f t h e c u r r e n t s t a t e a n d t h e c o n t r o l u s e d . F o r e x a m p l e , g ( N 1 , N 2 , n 1 , n 2 ) = W * ( N ^ u ( 1 ) - n ] ) + ( N 2 + u ( 2 ) - n 2 ) Some o f t h e p o s s i b l e a r e a s o f f u r t h e r s t u d i e s a r e l i s t e d b e l o w 4 7 ( 1 ) T h e c h o i c e o f t h e w e i g h t : A p r o b l e m i s t h e c h o i c e o f t h e w e i g h t i n o r d e r t o g i v e r e a s o n a b l e s e r v i c e t o a l l c l a s s e s o f j o b s a s a f u n c t i o n o f t h e s y s t e m a n d j o b p a r a m e t e r s . (2) T h e c h o i c e o f g ( i , u ( i ) ) A n o t h e r p r o b l e m i s t h e c h o i c e o f t h e a p p r o p r i a t e p e r f o r m a n c e i n d i c e s a n d t h e a p p r o p r i a t e c o s t f a c t o r w h i c h w i l l g i v e a g o o d r e p r e s e n t a t i o n o f t h e r e a l s y s t e m . 48 I n t a b l e ( 4 . 0 ) , t h e p a r t i a l C p u u t i l i z a t i o n s o f i n t e r a c t i v e a n d b a t c h j o b s f o r a n y ( n ^ n ^ a r e l i s t e d . T h e p a r t i a l C p u u t i l i z a t i o n o f c l a s s i j o b s i s t h e f r a c t i o n o f n o n - i d l e t i m e o f t h e C p u t h a t i s d e v o t e d t o c l a s s i j o b s . T h e f i r s t e n t r y i s t h e u t i l i z a t i o n o f i n t e r a c t i v e j o b s a n d s e c o n d e n t r y i s t h e u t i l i z a t i o n o f b a t c h j o b s . n . 3 4 5 6 0 0 0 0 .5351 0 0 . 7 4 5 2 0 0 . 8 2 6 4 0 0 . 8 4 2 9 0 0 . 8 0 7 5 0 . 4 8 7 2 0 0 . 3 3 9 8 0 . 3 7 3 2 0 . 2 4 9 2 0 . 5 4 6 5 0 . 1 8 6 3 0 . 6 1 7 9 0 . 1357 0 . 6 1 4 0 0 . 0 8 9 0 0 . 5 2 9 8 0 . 6 6 5 7 0 0 . 4 8 5 3 0 .2721 0 . 3 5 6 9 0 . 4 0 1 9 0 . 2 5 0 3 0 . 4 3 3 4 0 . 1 5 3 9 0 . 3 7 7 4 0 .0511 0 . 1 7 6 2 0 . 7 0 9 6 0 0 . 5 1 0 8 0 . 1 9 5 8 0 . 3 4 2 4 0 . 2 6 9 4 0 . 1 9 7 2 0 . 2 4 9 6 0 . 0 5 9 7 0 . 1 1 4 3 0 . 0 3 6 7 0 . 1 0 8 3 0 . 6 4 7 9 0 0 . 4 1 2 6 0 . 1 2 4 7 0 . 2 2 3 8 0 .1461 0 . 0 6 3 3 0 . 0 7 0 6 0 . 0 4 4 2 0 . 0 7 9 7 0 . 0 1 7 9 0 . 0 4 3 9 0 . 4 6 3 4 0 0 . 2 3 8 5 0 . 0 6 4 2 0 . 0 6 4 4 0 . 0 3 9 4 0 . 0 5 0 6 0 . 0 5 5 5 0 . 0 2 0 7 0 . 0 3 2 7 0 . 0 9 0 9 0 . 1 9 2 3 0 . 2 4 5 7 0 0 . 0 6 4 2 0 . 0 1 6 7 0 . 0 5 6 2 0 . 0 3 4 6 0 . 0 2 3 2 0 . 0 2 2 9 0 . 1 1 0 6 0 .1561 0 . 0 0 6 0 0 . 0 1 0 4 T a b l e ( 4 . 0 ) C p u u t i l i z a t i o n f o r a l l n 1 i n t e r a c t i v e j o b s a n d n 2 b a t c h j o b s 4 9 I n t a b l e s 4 . 1 . 1 t o 4 . 8 . 2 , t h e i n d e x o f t h e t a b l e s s t a r t s f r o m z e r o i n s t e a d o f o n e . F o r t h e c a s e o f c o n t r o l ( a ) , t h e c o n t r o l p o l i c y i s . t h e ( p r p j ) p a i r i n t h e e n t r i e s 1 + 1, J+1 f o r t h e s t a t e N ^ I a n d N 2 = J . T h e c o n t r o l i s a p p l i e d when t h e r e a r e no j o b s i n t h e memory l o o p ( n 1 = n 2 = 0 ) . I n t h e c a s e o f c o n t r o l ( b ) , t h e i n d e x ( i , j ) b l o c k o f t h e t a b l e g i v e s t h e v a l u e o f N 1 , N 2 w h i l e t h e i n d e x w i t h i n a b l o c k g i v e s t h e v a l u e o f n1 a n d n 2 . T h e f i r s t d i g i t o f t h e two d i g i t s c o d e i s t h e number o f i n t e r a c t i v e j o b s w h i c h s h o u l d be i n memory i n t h e n e x t i n t e r v a l a n d t h e s e c o n d d i g i t i s t h e number o f b a t c h w h i c h s h o u l d be i n memory i n t h e n e x t i n t e r v a l . E x a m p l e : T h e c o n t r o l i n t h e s q u a r e i s f o r t h e s y s t e m s t a t e w i t h N 1 = 4 , N 2 = 3 ' n i = 2 a n d n 2 = 1 " T h e v a l u e ' 2 2 ' i s t h e d e s i r e d n 1 , n 2 f o r t h e n e x t i n t e r v a l . T h e r e f o r e , t h e a c t u a l c o n t r o l i s t o a d m i t one more b a t c h j o b . A l l t h e t a b l e s h a v e t h e f o l l l o w i n g p a r a m e t e r v a l u e s : 0 M = 0 . 0 5 , (pn = 0 . 1 , Y = 6 0 , N = 6 , m2 = 5 , b m = 0 . 0 1 8 , b B = 0 . 0 1 2 , a B = 10, a T = 2 0 , D 1 = 2 0 , D 2 = 10 , n2 = 8 0 , n3 = 3 0 . " I t a " i s t h e a b b r e v a t i o n f o r " 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 i s i n j o b s p e r s e c o n d s . . R e s p o n s e t i m e i s i n s e c o n d s . c p u T a n d c p u B a r e t h e c p u t i m e s e r v i c e r a t e s f o r i n t e r a c t i v e a n d b a t c h j o b s r e s p e c t i v e l y . 50 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0 . 0 8 4 ± 0 . 0 3 4 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 4 0 . 7 5 7 ± 1 7 . 5 9 7 Mean b a t c h j o b t h r o u g h p u t r a t e = 0 . 0 6 3 ± 0 . 0 1 8 Mean b a t c h j o b r e s p o n s e t i m e = 3 5 . 1 0 2 ± 1 7 . 1 1 5 T a b l e ( 4 . 1 . 1 ) W i t h o u t c o n t r o l w i t h c p u T = 0 . 3 , c p u B = 0 . 3 51 C o n t r o l p o l i c y ( a) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1) (0,2) (2,1) (0,2) (0,3) (0 ,'4) (0,4) 2 (2,0) (0,3) (0,4) (0,4) 3 (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) 4 (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) 5 (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) 6 (3,0) (2,1) (0,2) (0,3) (0,4) (0,4) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : ' * Q * * * } * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * £ * * * * * * * * * * * * * * 5 * * * * * * * * 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 12 12 12 13 13 13 13 13 1 3 13 13 1 4 1 2 1 2 12 13 1 4 15 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 12 12 1 3 13 13 13 1 3 13 1 3 1 3 1 4 1 2 1 2 12 13 1 4 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 23 25 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 13 13 13 13 13 13 13 13 1 4 1 2 1 2 12 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 23 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 1 3 13 13 1 3 1 3 13 1 3 1 3 1 4 12 12 12 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 13 13 13 1 3 13 13 13 1 3 1 4 1 2 1 2 12 13 14 1 5 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 13 13 13 13 13 13 13 13 1 4 12 12 12 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 X = N X = [N|n] Mean I t a . j o b t h r o u g h p u t r a t e = 0. 130 ± 0.037 0. 1 38 + 0.037 Mean I t a . j o b r e s p o n s e t i m e = 22 .10 ± 10.433 19 .257 + 6.651 Mean B a t c h j o b t h r o u g h p u t r a t e = 0. 096 ± 0.028 0. 101 + 0.027 Mean B a t c h j o b r e s p o n s e t i m e = 12 .319 ± 3.893 10 .067 + 3.235 Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.711 54. 170 T a b l e (4.1.2) C o n t r o l p o l i c y w i t h Weight=1, cpuT=0.3, cpuB=0.3 52 C o n t r o l p o l i c y (a ) w i t h s y s t e m s t a t e X = N : J 0 1 2 3 4 5 0 ( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 1 ( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 2 ( 2 , 0 ) ( 2 , 1 ) ( 1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 3 ( 3 , 0 ) ( 2 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 4 ( 3 , 0 ) ( 2 , 1 ) ( 1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 5 ( 3 , 0 ) ( 2 , 1 ) ( 1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 6 ( 3 , 0 ) ( 2 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N j n ] : 1 t 0 * * * i ** **** 2*** ***** 3** * * * *******£****** ******** 5******** 0 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 1 10 1 1 1 1 12 1 2 1 2 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 1 2 1 2 12 13 1 3 13 13 1 3 13 1 3 1 3 1 4 1 2 12 12 13 14 15 2 20 1 1 1 1 12 1 2 12 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 13 13 13 1 3 1 3 13 13 13 1 4 1 2 1 2 12 13 14 15 20 21 21 22 22 22 21 21 22 23 21 21 22 23 24 20 21 22 23 24 25 3 20 21 21 1 2 1 2 12 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 21 21 12 1 2 1 2 13 13 13 13 1 3 13 13 13 1 4 1 2 12 12 13 14 15 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 30 21 22 23 24 25 30 31 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 4 20 21 21 12 12 12 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 21 21 12 12 1 2 13 1 3 13 13 1 3 13 1 3 13 1 4 1 2 12 12 13 14 15 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 30 21 22 23 24 25 30 31 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 5 20 21 21 12 12 12 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 21 21 12 1 2 1 2 13 1 3 13 1 3 1 3 13 13 13 1 4 30 1 2 12 13 14 15 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 30 21 22 23 24 25 30 31 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 6 20 21 21- 12 1 2 12 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 21 21 12 1 2 12 13 13 13 1 3 1 3 13 1 3 13 14 30 1 2 12 13 14 15 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 30 21 22 23 24 25 30 31 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 C o n t r o l ( a) C o n t r o l (b) Mean I t a . j o b t h r o u g h p u t r a t e = 0 . 1 33 + 0 . 056 0 . 145 + 0 . 040 Mean I t a . j o b r e s p o n s e t ime = 19 . 9 9 9 + 6 . 41 1 18 . 2 8 6 ± 6 . 323 Mean B a t c h j o b t h r o u g h p u t r a t e = 0 . 095 + 0 . 027 0 . 092 + 0 . 023 Mean B a t c h j o b r e s p o n s e t ime = 1 3 . 944 + 4 . 328 9 . 873 + 2 . 616 C p u t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y 0 . 6 5 8 5 4 . 1 7 0 T a b l e ( 4 . 1 . 3 ) C o n t r o l p o l i c y w i t h W e i g h t = 2 , c p u T = 0 . 3 , c p u B = 0 . 3 53 C o n t r o l p o l i c y (a) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 (0,0) (0,1 ) (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1) (2,1 ) (1,2) (1,3) (1,2) (1,1) (2,0) 2 (2,0) (1,2) (1,2) (2,1) 3 (3,0) (2,1 ) (1,2) (2,1) (3,0) (3,0) 4 (3,0) (2,1 ) (1,2) (3,0) (3,0) (3,0) 5 (3,0) (2,1 ) ( 1,2) (3,0) (3,0) (3,0) 6 (3,0) (2,0) (1 ,2) (3,0) (3,0) (3,0) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : * * ] * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * £ * * * * * * 00 01 01 02 02 02 03 03 03 03 03 03 03 03 04 02 02 02 03 04 05 10 1 1 1 1 12 12 12 03 03 03 03 1 1 1 1 12 03 04 10 1 1 1 2 13 04 05 10 1 1 1 1 1 2 12 12 12 12 12 1 3 1 1 1 1 12 13 14 10 1 1 12 13 14 15 20 21 21 12 1 2 12 20 21 12 03 20 21 12 03 04 20 21 22 13 04 05 20 21 21 1 2 1 2 12 20 21 12 13 20 21 12 13 14 20 21 22 13 14 15 20 21 21 21 21 22 20 21 22 23 20 21 22 23 24 20 21 22 23 24 25 30 21 21 1 2 12 1 2 30 21 12 03 30 21 12 03 04 30 21 22 13 04 05 30 21 21 12 12 1 2 30 21 1 2 13 30 21 12 13 1 4 30 21 22 1 3 1 4 15 30 21 21 21 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 30 21 21 12 1 2 12 30 21 12 03 30 21 12 03 04 30 21 22 13 04 05 30 21 21 12 12 1 2 30 21 12 13 30 21 12 13 14 30 21 22 13 14 15 30 21 21 21 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 30 21 21 30 1 2 1 2 30 21 12 03 30 21 12 03 04 30 21 22 1 3 04 05 30 21 21 30 12 12 30 21 1 2 13 30 21 12 13 1 4 30 21 22 1 3 14 15 30 21 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 30 21 21 30 12 12 30 21 12 03 30 21 12 03 04 30 21 12 13 04 05 30 21 21 30 12 1 2 30 21 12 13 30 21 12 13 14 30 21 12 13 14 15 30 21 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 Mean I t a . j o b t h r o u g h p u t r a t e = Mean I t a . j o b r e s p o n s e t i m e = Mean B a t c h j o b t h r o u g h p u t r a t e = Mean B a t c h j o b r e s p o n s e t i m e = Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = C o n t r o l (a) 0. 145 8.08 0.083 20.65 0.04 5.78 0.022 7.453 0.645 C o n t r o l (b) 0.156 ± 0.043 15.43 0.088 23.04 5.098 0.025 10.89 74.836 T a b l e (4.1.4) C o n t r o l p o l i c y w i t h Weight=3, cpuT=0.3, cpuB=0.3 54 C o n t r o l p o l i c y ( a ) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 1 2 3 4 5 6 ( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) (0,1 ) ( 1 , 1 ) ( 2 , 1 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 0 , 2 ) ( 1 , 2 ) ( 2 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 0 , 3 ) ( 1 , 2 ) ( 2 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 0 , 4 ) ( 1 , 1 ) ( 2 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 0 , 4 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) C o n t r o l p o l i c y ( b) w i t h s y s t e m s t a t e X = [N_|n] : f j * * * ] * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * £ * * * * * * * * * * * * * * 5 * * * * * * * * 00 01 01 02 02 02 01 01 02 03 01 01 02 03 04 01 01 02 03 04 05 10 1 1 1 1 1 1 1 1 12 10 1 1 12 1 3 10 1 1 12 1 3 04 10 1 1 12 13 04 05 10 1 1 1 1 1 1 1 1 12 10 1 1 12 1 3 10 1 1 1 2 1 3 14 10 1 1 12 13 1 4 15 20 20 21 20 21 1 2 20 21 1 2 1 3 20 21 1 2 13 04 20 21 22 13 04 05 20 20 21 20 21 1 2 20 21 12 1 3 20 21 1 2 1 3 14 20 21 22 13 1 4 1 5 20 20 21 20 21 22 20 21 22 23 20 21 22 23 24 20 21 22 23 24 25 30 30 21 30 21 12 30 21 12 13 30 21 12 13 04 30 21 22 13 04 05 30 30 21 30 21 1 2 30 21 12 1 3 30 21 12 13 14 30 21 22 13 14 1 5 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 30 30 21 30 21 12 30 21 1 2 1 3 30 21 12 13 04 •30 21 22 13 04 05 30 30 21 30 21 12 30 21 12 13 30 21 12 13 1 4 30 21 22 13 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 '33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 30 30 21 30 21 12 30 21 12 1 3 30 21 12 1 3 04 30 21 22 1 3 04 05 30 30 21 30 21 1 2 30 21 12 1 3 30 21 12 13 14 30 21 22 13 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 30 30 21 30 21 12 30 21 12 03 30 21 12 13 04 30 21 12 13 04 05 30 30 21 30 21 12 30 21 12 13 30 21 12 13 14 30 21 12 13 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 C o n t r o l ( a ) Mean I t a . j o b t h r o u g h p u t r a t e = 0.157 ± 0.044 Mean I t a . j o b r e s p o n s e t i m e = 14.331 ± 4.264 Mean B a t c h j o b t h r o u g h p u t r a t e = 0.071 ± 0.026 Mean B a t c h j o b r e s p o n s e t i m e = 31.505 ± 16.064 Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.646 C o n t r o l 0. 178 10.647 0.070 31.410 (b) 0.045 2.8 0.019 13.22 69.045 T a b l e ( 4 . 1 . 5 ) C o n t r o l p o l i c y w i t h W e i g h t = 5 , c p u T = 0 . 3 , cpuB=0.3 55 C o n t r o l p o l i c y ( a ) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 ( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 1 ( 1 , 0 ) ( 1 , 0 ) ( 1 , 0 ) ( 1 , 0 ) ( 1 , 0 ) ( 1 , 0 ) 2 - ( 2 , 0 ) ( 2 , 0 ) ( 2 , 0 ) ( 2 , 0 ) ( 2 , 0 ) ( 2 , 0 ) 3 ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) 4 ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) 5 ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) 6 ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) ( 3 , 0 ) C o n t r o l p o l i c y ( b) w i t h s y s t e m s t a t e X = [ N | n ] : :Q* * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * * 5 * * * * * * * * 0 00 01 01 01 01 02 01 01 02 03 01 01 02 03 04 01 01 02 03 04 05 1 1 0 10 1 1 10 1 1 1 2 10 1 1 1 2 13 10 1 1 12 1 3 04 10 1 1 1 2 1 3 04 05 10 10 1 1 10 1 1 1 2 10 1 1 1 2 13 10 1 1 12 1 3 1 4 10 1 1 12 13 1 4 15 2 20 20 21 20 21 22 20 21 22 13 20 21 22 13 04 20 21 22 1 3 04 05 20 20 21 20 21 22 20 21 22 13 20 21 22 13 1 4 20 21 22 1 3 14 15 20 20 21 -20 21 22 20 21 22 23 20 21 22 23 24 20 21 22 23 24 25 3 30 30 21 30 21 22 30 21 22 13 30 21 22 1 3 04 30 21 22 13 04 05 30 30 21 30 21 22 30 21 22 13 30 21 22 13 1 4 30 21 22 1 3 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 4 30 30 21 30 21 22 30 21 22 13 30 21 22 13 04 30 21 22 13 04 05 30 30 21 30 21 22 30 21 22 13 30 21 22 13 14 30 21 22 13 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 5 30 30 21 30 21 22 30 21 22 1 3 30 21 22 13 04 30 21 22 1 3 04 05 30 30 21 30 21 22 30 21 22 13 30 21 22 13 14 30 21 22 13 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 6 30 30 21 30 21 1 2 30 21 12 13 30 21 12 13 04 30 21 22 13 04 05 30 30 21 30 21 12 30 21 12 13 30 21 12 13 14 30 21 22 1 3 14 15 30 30 21 30 21 22 30 21 22 23 30 21 22 23 24 30 21 22 23 24 25 30 30 31 30 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 Mean I t a . j o b t h r o u g h p u t r a t e = Mean I t a . j o b r e s p o n s e t i m e = Mean B a t c h j o b t h r o u g h p u t r a t e = Mean B a t c h j o b r e s p o n s e t i m e = Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = C o n t r o l ( a ) 0. 150 ± 0.041 + 15.45 0.067 42.53 4.185 0.02 22.77 0.646 C o n t r o l 0.176 ± 10.67 0.058 49.48 + + + (b) 0.046 2.821 0.017 23.43 65.982 T a b l e ( 4 . 1 . 6 ) C o n t r o l p o l i c y w i t h W e i g h t = 5 0 , c p u T = 0 . 3 , cpuB=0.3 56 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0 . 1 4 6 ± 0 . 0 4 2 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 1 7 . 0 0 6 ± 6 . 7 9 8 Mean b a t c h j o b t h r o u g h p u t r a t e = 0 . 0 9 6 ± 0 . 0 2 6 Mean b a t c h j o b r e s p o n s e t i m e = 8 .211 ± 3 , 4 2 0 T a b l e ( 4 . 2 . 1 ) W i t h o u t c o n t r o l w i t h c p u T = 0 . 3 , c p u B = 0 . 7 57 C o n t r o l p o l i c y (a) w i t h s y s t e m s t a t e X = N : J 0 1 2 3 4 5 0 (0,0) ( o , r » (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1 1 (0,2) (0,3) (0,4) (0,4) 2 (2,0) (1,1 > (0,2) (0,3) (0,4) (0,4) 3 (3,0) (1,1 > (0,2) (0,3) (0,4) (0,4) 4 (3,0) (1,1, 1 (0,2) (0,3) (0,4) (0,4) 5 (3,0) (1,1 > (0,2) (0,3) (0,4) (0,4) 6 (3,0) (1,1 1 (0,2) (0,3) (0,4) (0,4) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e , X = [ N | n ] : * Q * * * • ) * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * 0 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 1 10 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 1 2 12 1 2 1 3 1 3 13 1 3 1 3 1 3 13 13 14 13 13 13 13 14 1 5 2 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 1 2 1 3 13 13 13 13 1 3 1 3 13 14 1 3 13 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 3 20 1 1 11 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 12 1 2 13 1 3 1 3 1 3 1 3 13 13 13 1 4 13 13 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 4 20 1 1 1 1 •02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 1 2 1 2 13 13 1 3 1 3 1 3 13 1 3 13 14 13 1 3 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 5 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 1 3 13 1 3 13 1 3 13 13 1 4 13 13 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 6 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 12 1 2 1 3 1 3 13 1 3 13 13 1 3 13 14 13 1 3 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 64 64 60 61 62 64 64 65 Mean I t a . j o b t h r o u g h p u t r a t e = Mean I t a . j o b r e s p o n s e t i m e = Mean B a t c h j o b t h r o u g h p u t r a t e = 0.094 Mean B a t c h j o b r e s p o n s e t i m e = 8.475 Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.574 C o n t r o l (a) 0.160 ± 0.04 15.003 ± 4.148 ± 0.027 ± 2.272 C o n t r o l 0.171 ± 11.334 ± 0.095 ± 3.342 ± (b) 0.04 3.473 0.026 1 .049 42.306 T a b l e (4.2.2) C o n t r o l p o l i c y w i t h Weight=1, cpuT=0.3, cpuB=0.7 58 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0 . 1 4 3 ± 0 . 0 4 5 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 1 3 . 9 6 2 ± 5 . 7 4 3 Mean b a t c h j o b t h r o u g h p u t r a t e = 0 . 0 8 1 ± 0 . 0 2 3 Mean b a t c h j o b r e s p o n s e t i m e = 1 7 . 2 1 2 ± 7 . 9 1 0 T a b l e ( 4 . 3 . 1 ) W i t h o u t c o n t r o l w i t h c p u T = 0 . 5 , c p u B = 0 . 3 59 C o n t r o l p o l i c y ( a ) w i t h s y s t e m s t a t e X = N: J 0 1 2 .3 4 5 0 (0,0) (0,1 ) (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1) (2,1 ) ( 1,2) (0,3) (0,4) (0,4) 2 (2,0) (1,2) (0,3) (0,4) (0,4) 3 (3,0) (2,1 ) (1,2) (0,3) (0,4) (0,4) 4 (3,0) (2,1 ) (1,2) (0,3) (0,4) (0,4) 5 (3,0) (2,1 ) ( 1,2) (0,3) (0,4) (0,4) 6 (3,0) (2,1 ) (1,2) (0,3) (0,4) (0,4) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : : g * * * ] * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * £ * * * * * * 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 0 1 1 1 1 1 1 1 1 02 02 02 12 12 12 03 1 3 03 1 3 03 13 03 13 04 13 04 1 3 04 04 04 13 13 14 04 04 04 04 04 05 12 12 12 13 14 15 20 20 20 1 1 1 1 21 1 1 1 1 21 02 02 02 12 12 12 22 22 22 03 1 3 21 03 13 21 03 13 22 03 13 23 04 04 13 13 21 21 04 04 04 13 13 14 22 23 24 04 04 12 12 21 21 04 04 12 13 22 23 04 1 4 24 05 15 25 30 30 30 30 1 1 1 1 21 31 1 1 1 1 21 31 02 02 02 12 12 12 22 22 22 30 31 32 03 13 21 30 03 13 21 31 03 03 13 13 22 23 32 33 04 04 13 13 21 21 30 31 04 04 04 13 13 14 22 23 24 32 33 34 04 04 12 12 21 21 30 31 04 04 12 13 2-2 23 32 33 04 05 14 15 24 25 34 35 30 30 30 30 40 1 1 1 1 21 31 40 1 1 1.1 21 31 41 02 02 02 12 12 12 22 22 22 30 31 32 40 41 42 03 03 13 13 22 22 30 31 40 41 03 03 13 13 22 23 32 33 42 43 04 1 3 21 30 40 04 13 21 31 41 04 04 04 13 13 14 22 23 24 32 33 34 42 43 44 04 12 21 30 40 04 12 21 31 41 04 04 12 13 22 23 32 33 42 43 04 05 14 15 24 25 34 35 44 45 30 30 30 30 40 50 1 1 1 1 21 31 40 50 1 1 1 1 21 31 41 51 02 02 02 12 12 12 22 22 22 30 31 32 40 41 50 51 42 52 03 03 13 13 22 22 30 31 40 41 50 51 03 03 13 13 22 23 32 33 42 43 52 53 04 13 21 30 40 50 04 13 21 31 41 51 04 04 04 13 13 14 22 23 24 32 33 34 42 43 44 52 53 54 04 04 12 12 21 21 30 31 40 41 50 51 04 04 12 13 22 23 32 33 42 43 52 53 04 05 14 15 24 25 34 35 44 45 54 55 30 30 30 30 40 50 60 1 1 1 1 21 31 40 50 60 1 1 1 1 21 31 41 51 61 02 02 02 12 12 12 22 22 22 30 31 32 40 41 50 51 60 61 42 52 62 03 03 13 13 22 22 30 31 40 41 50 51 60 61 03 03 13 13 22 23 32 33 42 43 52 53 62 63 04 04 13 13 21 21 30 31 40 41 50 51 60 61 04 04 04 13 13 14 22 23 24 32 33 34 42 43 44 52 53 54 62 63 64 04 04 12 12 21 21 30 31 40 41 50 51 60 61 04 04 12 13 22 23 32 33 42 43 52 53 62 63 04 05 14 15 24 25 34 35 44 45 54 55 64 65 Mean I t a . j o b t h r o u g h p u t r a t e = Mean I t a . j o b r e s p o n s e t i m e = Mean B a t c h j o b t h r o u g h p u t r a t e = Mean B a t c h j o b r e s p o n s e t i m e .= Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y C o n t r o l (a) 0. 174 11.490 0.094 10.228 0.044 3.234 0.026 2.874 0.642 C o n t r o l 0 . 1 8 9 ± 8.388 ± 0.100 ± 8.138 ± 52.967 (b) 0.049 2.667 0.027 2.322 T a b l e (4.3.2) C o n t r o l p o l i c y w i t h Weight=1, cpuT=0.5, cpuB=0.3 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0 . 1 2 3 ± 0 . 0 3 7 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 2 2 . 9 1 9 ± 1 0 . 7 4 2 Mean b a t c h j o b t h r o u g h p u t r a t e = 0 . 0 5 9 ± 0 . 0 1 7 Mean b a t c h j o b r e s p o n s e t i m e = 3 6 . 2 8 2 ± 1 1 . 9 4 2 T a b l e ( 4 . 4 . 1 ) W i t h o u t c o n t r o l w i t h c p u T = 0 . 5 , c p u B = 0 . 2 61 C o n t r o l p o l i c y ( a ) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 ( 0 , 0 ) (0,1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 1 ( 1 , 0 ) ( 1 , 1 ) (1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 1 , 2 ) 2 ( 2 , 0 ) ( 2 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 2 , 0 ) 3 ( 3 , 0 ) ( 2 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 3 , 0 ) 4 ( 3 , 0 ) ( 2 , 1 ) (1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 3 , 0 ) 5 ( 3 , 0 ) (2,1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 3 , 0 ) 6 ( 3 , 0 ) ( 2 , 1 ) ( 1 , 2 ) ( 0 , 3 ) ( 2 , 1 ) ( 3 , 0 ) C o n t r o l p o l i c y ( b ) w i t h s y s t e m s t a t e X = [ N | n ] : * 0 * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * * 5 * * * * * * * * 00 01 01 02 02 02 03 03 03 03 03 03 03 03 04 02 02 02 03 04 05 10 10 1 1 1 1 1 1 1 1 12 1 2 12 12 1 2 1 2 03 1 3 03 1 3 03 13 03 1 3 03 12 03 1 2 03 1 2 03 1 3 04 1 4 1 1 1 1 11 12 11 12 1 3 1 3 04 1 4 05 1 5 20 20 20 21 21 21 21 21 21 12 1 2 21 12 12 21 12 12 22 03 12 21 03 1 2 21 03 03 12 13 22 23 21 21 21 21 21 21 12 03 04 12 13 14 22 23 24 20 21 22 20 21 22 20 21 22 1 3 1 3 23 04 1 4 24 05 15 25 30 30 30 30 21 21 21 30 21 21 21 31 12 12 21 30 1 2 12 21 31 1 2 1 2 22 32 03 03 12 12 21 21 30 31 03 03 12 13 22 23 32 33 30 21 30 21 30 21 30 31 12 03 04 12 13 14 22 23 24 32 33 34 30 21 22 30 21 22 30 21 22 30 31 32 13 04 05 13 14 15 23 24 25 33 34 35 30 30 30 30 40 21 21 21 30 40 21 21 21 31 41 12 12 21 30 40 12 12 21 31 41 1 2 12 22 32 42 03 1 2 21 30 40 03 1 2 21 31 41 03 03 12 13 22 23 32 33 42 43 30 21 30 21 30 21 30 31 40 41 12 03 04 12 13 14 22 23 24 32 33 34 42 43 44 30 21 22 30 21 22 30' 21 22 30 31 32 40 41 42 13 04 05 13 14 15 23 24 25 33 34 35 43 44 45 30 30 30 30 40 50 21 21 21 30 40 50 21 21 21 31 41 51 12 12 21 30 40 50 12 12 21 31 41 51 1 2 12 22 32 42 52 03 12 21 30 40 50 03 1 2 21 31 41 51 03 03 12 13 22 23 32 33 42 43 52 53 30 21 30 21 30 21 30 31 40 41 50 51 12 03 04 12 13 14 22 23 24 32 33 34 42 43 44 52 53 54 30 21 22 30 21 22 30 21 22 30 31 32 40 41 42 50 51 52 13 04 05 13 14 15 23 24 25 33 34 35 43 44 45 53 54 55 30 30 30 30 40 50 60 21 21 21 30 40 50 60 21 21 21 31 41 51 61 12 12 21 30 40 50 60 12 12 21 31 41 51 61 12 12 22 32 42 52 62 03 12 21 30 40 50 60 03 12 21 31 41 51 61 03 '03 12 13 22 23 32 33 42 43 52 53 62 63 30 21 30 21 30 21 30 31 40 41 50 51 60 61 12 03 04 12 13 14 22 23 24 32 33 34 42 43 44 52 53 54 62 63 64 30 21 22 30 21 22 30 21 22 30 31 32 40 41 42 50 51 52 60 61 62 13 04 05 13 14 15 23 24 25 33 34 35 43 44 45 53 54 55 63 64 65 Mean I t a . j o b t h r o u g h p u t r a t e = 0 . 1 2 4 ± Mean I t a . j o b r e s p o n s e t i m e = 27.027 ± Mean B a t c h j o b t h r o u g h p u t r a t e = 0.086 ± Mean B a t c h j o b r e s p o n s e t i m e = 19.216 ± Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.710 C o n t r o l ( a ) 0.047 14.54 0.024 7.098 C o n t r o l 0.183 ± 9.893 ± 0.086 ± 15.924 ± 58.999 (b) 0.047 3.685 0.022 4.655 T a b l e ( 4 . 4 . 2 ) C o n t r o l p o l i c y w i t h W e i g h t = 1 , cpuT=0.5, cpuB=0.2 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0 . 0 8 4 ± 0 . 0 3 4 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 4 0 . 7 5 7 ± 1 7 . 5 9 7 Mean b a t c h j o b t h r o u g h p u t r a t e = 0 . 0 6 3 ± 0 . 0 1 8 Mean b a t c h j o b r e s p o n s e t i m e = 3 5 . 1 0 2 ± 1 7 . 1 1 5 T a b l e ( 4 . 5 . 1 ) W i t h o u t c o n t r o l w i t h c p u T = 0 . 5 , c p u B = 0 . 4 63 C o n t r o l p o l i c y ( a ) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 ( 0 , 0 ) (0,1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 1 ( 1 , 0 ) ( 1 , 1 ) (2,1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 2 ( 2 , 0 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 3 ( 3 , 0 ) (2,1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 4 ( 3 , 0 ) ( 2 , 1 ) (1 ,2) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 5 ( 3 , 0 ) (2,1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 6 ( 3 , 0 ) (2,1 ) ( 1 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) C o n t r o l p o l i c y ( b) w i t h s y s t e m s t a t e X = [ N | n ] : *o* ** \ ** * * * *2* * * ***** 3***** * * * * * * *4 * * * * * * ******** 5****** * * 0 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 1 10 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 1 2 1 2 1 2 1 3 13 13 1 3 1 3 13 1 3 13 1 4 1 2 1 2 12 1 3 14 15 2 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 12 12 1 3 1 3 1 3 1 3 1 3 13 1 3 13 1 4 1 2 1 2 12 1 3 14 15 20 2 1 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 3 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 12 1 2 1 2 1 3 13 13 1 3 1 3 1 3 1 3 13 1 4 1 2 12 12 13 1 4 1 5 30 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 4 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 1 2 1 2 1 2 1 3 1 3 1 3 13 13 1 3 1 3 13 1 4 1 2 1 2 12 1 3 14 1 5 30 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 '40 41 42 43 44 45 5 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 1 2 1 2 1 2 1 3 13 1 3 1 3 1 3 1 3 1 3 1 3 1 4 1 2 1 2 12 1 3 1 4 1 5 30 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 4 1 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 6 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 1 2 12 1 2 13 13 1 3 13 1 3 1 3 13 13 1 4 12 12 12 13 14 15 30 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 30 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 C o n t r o l ( a ) C o n t r o l ( b ) Mean I t a . j o b t h r o u g h p u t r a t e — 0. 1 92 + 0. 05 0. 204 + 0.051 Mean I t a . j o b r e s p o n s e t i m e 10 .903 ± 4. 487 7. 459 + 2.393 Mean B a t c h j o t t h r o u g h p u t r a t e = 0. 102 + 0. 03 0. 093' + 0.024 Mean B a t c h j o t r e s p o n s e t ime 9. 317 + 3. 398 6. 039 + 1 .825 Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y 0.572 55.450 T a b l e ( 4 . 5 . 2 ) C o n t r o l p o l i c y w i t h W e i g h t = 1 , c p u T = 0 . 5 , cpuB=0.4 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0.208 ± 0.053 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 6.8507 ± 3.208 Mean b a t c h j o b t h r o u g h p u t r a t e = 0.086 ± 0.022 Mean b a t c h j o b r e s p o n s e t i m e = 6.170 ± 3.730 T a b l e ( 4 . 6 . 1 ) W i t h o u t c o n t r o l w i t h cpuT=0.5, cpuB=0.5 65 C o n t r o l p o l i c y (a) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 (0,0) (0,1 ) (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1) (2,1) (1,2) (0,3) (0,4) (0,4) 2 (2,0) (1,2) (0,3) (0,4) (0,4) 3 (3,0) (2,1 ) (1,2) (0,3) (0,4) (0,4) 4 (3,0) (2,1 ) (1,2) (0,3) (0,4) (0,4) 5 (3,0) (2,1) ( 1 ,2) (0,3) (0,4) (0,4) 6 (3,0) (2,1) (1,2) (0,3) (0,4) (0,4) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : *0* ****2*** * * * * * 3 * * * * * * * * * * * * * 5 * * * * * * * * 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 1 0 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 12 1 2 1 2 1 3 1 3 13 1 3 1 3 1 3 13 13 14 1 3 1 3 1 3 13 1 4 1 5 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 1 2 1 3 1 3 1 3 1 3 1 3 1 3 13 1 3 14 13 1 3 1 3 13 1 4 1 5 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 12 1 2 1 2 1 3 1 3 1 3 1 3 13 1 3 13 13 1 4 13 1 3 1 3 13 1 4 15 30 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 12 1 2 1 2 1 3 13 1 3 1 3 13 1 3 1 3 1 3 1 4 1 3 13 1 3 13 1 4 15 30 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 12 1 2 1 2 1 3 1 3 1 3 1 3 1 3 13 13 1 3 1 4 1 3 1 3 1 3 1 3 1 4 1 5 30 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 30 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 30 1 1 1 1 12 12 1 2 1 3 13 13 1 3 13 1 3 13 1 3 14 13 1 3 1 3 13 14 1 5 30 21 21 22 22 22 22 22 22 23 22 22 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 64 64 60 61 62 64 64 65 C o n t r o l (a) Mean I t a . j o b t h r o u g h p u t r a t e = 0 . 1 9 5 ± Mean I t a . j o b r e s p o n s e t i m e = 9.795 ± Mean B a t c h j o b t h r o u g h p u t r a t e = 0.106 ± Mean B a t c h j o b r e s p o n s e t i m e = 7.636 ± Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.579 0.05 3.649 0.028 2.507 C o n t r o l 0.210 ± 6.497 ± 0.095 ± 4.732 ± (b) 0.055 2.071 0.029 1 .242 73.129 T a b l e (4.6.2) C o n t r o l p o l i c y w i t h Weight=1 , cpuT=0.5, cpuB=0.5 66 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0.036 ± 0.013 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 58.475 ± 24.203 Mean b a t c h j o b t h r o u g h p u t r a t e = 0.039 ± 0.015 Mean b a t c h j o b r e s p o n s e t i m e = 60.569 ± 23.708 T a b l e ( 4 . 7 . 1 ) W i t h o u t c o n t r o l w i t h cpuT=0.2, cpuB=0.2 67 C o n t r o l p o l i c y (a) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 ( 0 , 0 ) ( 0 , 1 ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 1 ( 1 , 0 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 2 ( 2 , 0 ) (1,11 ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) I 3 ( 3 , 0 ) ( 1 , 1 ! ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 4 ( 3 , 0 ) d , r ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 5 ( 3 , 0 ) ( 1 , 1 ] > ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) 6 ( 3 , 0 ) o,i: ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 4 ) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : :Q* * * ] * * * * **2*** * * * * * 3 * * * * * * * * * * * * * 5 * * * * * * * * 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 12 12 12 13 1 3 1 3 1 3 1 3 1 3 1 3 13 14 1 2 1 2 1 2 13 1 4 15 20 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 13 1 3 13 13 1 3 1 3 13 13 14 1 2 12 1 2 1 3 1 4 1 5 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 20 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 1 3 1 3 13 1 3 13 1 3 13 14 1 2 1 2 12 1 3 1 4 1 5 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 20 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 1 2 1 3 1 3 13 1 3 1 3 1 3 13 13 14 1 2 1 2 1 2 1 3 1 4 1 5 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 4 1 42 43 44 45 20 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 1 3 1 3 1 3 1 3 1 3 1 3 13 14 1 2 1 2 12 1 3 1 4 1 5 20 21 21 22 22 22 22 22 22 23 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 20 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 13 13 13 13 13 13 13 13 14 1 2 12 1 2 13 14 15 20 21 21 22 22 22 22 22 22 2 3 21 21 22 23 24 21 21 22 23 24 25 30 31 31 31 31 32 31 31 32 33 30 31 32 33 34 30 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 63 64 60 61 62 63 64 65 C o n t r o l (a) Mean I t a . j o b t h r o u g h p u t r a t e = 0.064 ± 0.02 Mean I t a . j o b r e s p o n s e t i m e = Mean B a t c h j o b t h r o u g h p u t r a t e = Mean B a t c h j o b r e s p o n s e t i m e Cpu t i m e i n 'seconds u s e d i n c o m p u t i n g P o l i c y = 0.573 57.447 ± 26.473 0.084 ± 0.024 22.519 ± 6.952 C o n t r o l 0.078 ± 45.829 ± 0.096 ± 14.497 ± (b) 0.029 17.97 0.026 4. 134 68.209 T a b l e (4.7.2) C o n t r o l p o l i c y w i t h Weight=1, cpuT=0.2, cpuB=0.2 68 Mean i n t e r a c t i v e j o b t h r o u g h p u t r a t e = 0.066 ± 0.027 Mean i n t e r a c t i v e j o b r e s p o n s e t i m e = 38.969 ± 13.887 Mean b a t c h j o b t h r o u g h p u t r a t e = 0.088 ± 0.024 Mean b a t c h j o b r e s p o n s e t i m e = 19.728 ± 7.920 T a b l e ( 4 . 8 . 1 ) W i t h o u t c o n t r o l w i t h c puT=0.2, cpuB=0.5 69 C o n t r o l p o l i c y (a) w i t h s y s t e m s t a t e X = N: J 0 1 2 3 4 5 0 (0,0) (0,1) (0,2) (0,3) (0,4) (0,4) 1 (1,0) (1,1) (0,2) (0,3) (0,4) (0,4) 2 (2,0) (1,1) (0,2) (0,3) (0,4) (0,4) 3 (3,0) (1,1) (0,2) (0,3) (0,4) (0,4) 4 (3,0) (1,1) (0,2) (0,3) (0,4) (0,4) 5 (3,0) (1,1) (0,2) (0,3) (0,4) (0,4) 6 (3,0) (1,1) (0,2) (0,3) (0,4) (0,4) C o n t r o l p o l i c y (b) w i t h s y s t e m s t a t e X = [ N | n ] : :Q* * * • ) * * * * * * 2 * * * * * * * * 3 * * * * * * * * * * * * 4 * * * * * * 00 01 01 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 10 1 1 11 12 1 2 12 13 1 3 13 1 3 1 3 1 3 13 13 1 4 1 3 13 13 13 14 1 5 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 13 1 3 13 13 13 13 13 1 4 1 3 1 3 13 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 1 2 12 12 13 1 3 13 13 1 3 1 3 13 13 1 4 1 3 1 3 1 3 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 12 12 1 3 1 3 13 13 13 1 3 13 1 3 1 4 13 1 3 1 3 13 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 4 1 3 1 3 1 3 1 3 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 20 1 1 1 1 02 02 02 03 03 03 03 04 04 04 04 04 04 04 04 04 04 05 20 1 1 1 1 12 1 2 12 1 3 1 3 1 3 13 13 13 13 13 1 4 13 1 3 13 1 3 14 15 20 21 21 22 22 22 22 22 22 23 22 22 22 23 24 22 22 22 23 24 25 30 31 31 31 31 32 31 31 32 33 31 31 32 33 34 31 31 32 33 34 35 40 40 41 40 41 42 40 41 42 43 40 41 42 43 44 40 41 42 43 44 45 50 50 51 50 51 52 50 51 52 53 50 51 52 53 54 50 51 52 53 54 55 60 60 61 60 61 62 60 61 62 63 60 61 62 64 64 60 61 62 64 64 65 C o n t r o l (a) Mean I t a . j o b t h r o u g h p u t r a t e = 0.124 Mean I t a . j o b r e s p o n s e t i m e = 29.322 Mean B a t c h j o b t h r o u g h p u t r a t e = 0.096 Mean B a t c h j o b r e s p o n s e t i m e = 12.470 Cpu t i m e i n s e c o n d s u s e d i n c o m p u t i n g P o l i c y = 0.573 0.038 12.513 0.027 4.534 C o n t r o l (b) 0.134 ± 0.035 21 . 102 ± 6.592 0.099 ± 0.028 5.723 ± 1.704 52.248 T a b l e (4.8,2) C o n t r o l p o l i c y w i t h Weight=1, cpuT=0.2, cpuB=0.5 70 I n t h e f o l l o w i n g g r a p h s : B I * o + x b a t c h j o b s w i t h o u t l o a d c o n t r o l I n t e r a c t i v e j o b s w i t h o u t l o a d c o n t r o l I n t e r a c t i v e j o b s w i t h c o n t r o l (a ) B a t c h j o b s w i t h c o n t r o l ( a ) I n t e r a c t i v e j o b s w i t h c o n t r o l (b) B a t c h j o b s w i t h c o n t r o l (b ) C o n t r o l ( a ) i s t h e c a s e w i t h s y s t e m s t a t e d e n o t e d by [N] a n d g ( N , u ( N ) ) = W * N 1 + N 2 C o n t r o l (b) i s t h e c a s e w i t h s y s t e m s t a t e d e n o t e d by [ N | n ] a n d g(-[N | n ] , u ( [ N | n ] ) ) = W * N 1 + N 2 T h r o u g h p u t r a t e i s i n j o b s / s e c o n d . R e s p o n s e t i m e i s i n s e c o n d s . I n a l l t h e f o l l o w i n g g r a p h s , t h e s y s t e m p a r a m e t e r s a r e g i v e n t h e f o l l o w i n g v a l u e s : 4>T = 0 . 0 5 , 0 f i = 0 . 1 , Y = 6 0 , N = 6 , m2 = 5 , b T = 0 . 0 1 8 , b B = 0 . 0 1 2 , a g = 10 , a T = 2 0 , D 1 = 2 0 , D 2 = 10 , M 2 = 8 0 , M 3 = 3 0 . .20 .18 16 4-1 4 .12 T h r o u g h p u t R a t e . 1 .08 4-,06 4-04 4-02 j , — j j_ 1.0 2.0 3.0 4.0 5.0 WEIGHT F i g . 4.2.1 c p u T = 0.3, c p u B = 0.7 18 + 16 + i j j -14 + 12 4-10 4-R e s p o n s e T i m e 8 &©>r—B B- -B--e 6 + 2 i 1.0 2 . 0 3 . 0 4 . 0 5 . 0 WEIGHT F i g . 4 . 2 . 2 c p u T = 0 . 3 , c p u B = 0 . 7 . 2 4 + c p u T , c p u B F i g . 4 . 5 . 1 70 + c p u T , c p u B F i g . 4.5.2 81 B I B L I O G R A P H Y [ I ] B a d e l , M . , G e l e n b e , E . , L e r o u d i e r , J . a n d P o t i e r , . D . , " 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 S y s t e m ' s P e r f o r m a n c e " , P r o c . I E E E , V o l . 6 3 , p p 9 5 8 - 9 6 5 , 1 9 7 5 . [ 2 ] B a d e l , J . a n d L e r o u d i e r , J . , " A d a p t i v e M u l t i p r o g r a m m i n g S y s t e m s Can E x i s t " , P e r f o r m a n c e o f C o m p u t e r I n s t a l l a t i o n , F e r r a r i , D . ( e d . ) , N o r t h - H o l l a n d , p p 1 1 5 - 1 3 5 , 1978 . [ 3 ] B a s k e t t , F . , C h a n d y , K . , M u n t z , R . a n d P o l a i u s - G i m e z , J . , " O p e n , C l o s e d , a n d M i x e d N e t w o r k s o f Queues w i t h D i f f e r e n t C l a s s o f C u s t o m e r s " , J . A C M , V o l . 2 2 , N o . 2 , p p 2 4 8 - 2 6 0 , A p r i l 1 9 7 5 . [ 4 ] B e r t s e k a s , D . , D y n a m i c P r o g r a m m i n g a n d S t o c h a s t i c C o n t r o l , A c a d e m i c P r e s s , 1 9 7 6 . [ 5 ] B r a n d w a j n , H . a n d H e r n a n d e z , J . , " A S t u d y o f a M e c h a n i s m f o r C o n t r o l l i n g M u l t i p r o g r a m m i n g Memory i n a n I n t e r a c t i v e S y s t e m s " , P e r f o r m a n c e o f C o m p u t e r S y s t e m s , A r a t o , M . , B u t r i m e n k o , A . a n d G e l e n b e , E . ( e d . ) , N o r t h - H o l l a n d , p p 4 8 7 - 5 0 0 , 1979 . [ 6 ] B r i c e , R . S . a n d Browne J . , " F e e d b a c k C o u p l e R e s o u r c e A l l o c a t i o n P o l i c i e s i n t h e M u l t i p r o g r a m m i n g C o m p u t e r S y s t e m s " , Comm. ACM 2 1 , 8 , p p 6 7 8 - 6 8 6 , A u g . 1978 . [ 7 ] B u n t , R . a n d Hume, J . , " 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 B a s e d 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, N o . 2 , p p 1 3 5 - 1 4 7 , J u n e 1 9 7 7 . [ 8 ] B u z e n , J . , " 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 Queue. in N e t w o r k s w i t h E x p o n e n t i a l S e r v e r s " , Comm. A C M , V o l . 16 N o . 9 , p p 5 2 7 - 5 3 1 , S e p t . 1 9 7 3 . [ 9 ] B u z e n , J . P . , " F u n d a m e n t a l O p e r a t i o n a l Laws o f C o m p u t e r S y s t e m p e r f o r m a n c e " , A c t a I n f o r m a t i c a 7 , p p 1 6 7 - 1 8 2 , 1 9 7 6 . [ 1 0 ] C h a m b e r l i n , D . , F u l l e r , S . a n d L i u , L . , " 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 S y s t e m s " , IBM J . , R e s . D e v e l o p . , V o l . 17 , p p 4 0 4 - 4 1 2 , 1 9 7 3 . [ I I ] C h a n s o n , S a m u e l T . , a n d L o , R a y m o n d , " T h e A p p l i c a t i o n 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 T h e o r y i n C o m p u t e r S y s t e m L o a d R e g u l a t i o n " , T e c h . R e p . 8 1 - 5 , D e p t . o f C o m p u t e r S c i e n c e , . U . B . C . , J u n e 1981 . [12 ] C h a n s o n , S a m u e l T . , a n d S i n h a , P r e m , S . , " O p t i m a l M a c r o -S c h e d u l i n g " , T e c h . R e p . 8 1 - 1 1 , D e p t . o f C o m p u t e r S c i e n c e , U . B . C . , A u g . 1981 . 82 [ 1 3 ] C o u r t o i s , P., D e c o m p o s a b i l i t y - Q u e u e i n q a n d Co m p u t e r S y s t e m A p p l i c a t i o n s , Academic- P r e s s , 1977. [ 1 4 ] C o u r t o i s , P., " D e c o m p o s a b i l i t y , I n s t a b i l i t i e s a n d S a t u r a t i o n i n M u l t i p r o g r a m m i n g S y s t e m s " , Comm. ACM, V o l . 18, pp 3 7 1 - 3 7 7 , J u l y 1975. [ 1 5 ] C o u r t o i s , P., "On t h e N e a r - C o m p l e t e - d e c o m p o s a b i l i t y o f N e t w o r k s o f Queues a n d o f S t o c h a s t i c M o d e l s o f M u l t i p r o g r a m m i n g C o m p u t e r S y s t e m s " , S c i . R e p., CMU-C72-11, C a r n e g i e - M e l l o n U n i v e r s i t y , Nov. 1971. [ 1 6 ] D e n n i n g , P., " T h r a s h i n g : i t s c a u s e s a n d p r e v e n t i o n " , P r o c . A F I P S , V o l . 3 3 , pp 197-216, 1976. [ 1 7 ] D e n n i n g , P., K a h n , K . C., L e r o u d i e r , J . , P o t i e r , R. a n d S u r i , R., " O p t i m a l M u l t i p r o g r a m m i n g " , A c t a I n f o r m a t i c a , V o l . 7, No. 2, pp 197-216, 1976. [ 1 8 ] F e r r a r i , D., C o m p u t e r S y s t e m s P e r f o r m a n c e E v a l u a t i o n , E n g l e w o o d C l i f f s , N J : P r e n t i c e - H a l l , 1978. [ 1 9 ] G e l e n b e , E., a n d M u n t z , R. R., " P r o b a b i l i s t i c M o d e l s o f Comp u t e r S y s t e m s - P a r t I - ( E x a c t R e s u l t s ) " , A c t a i n f o r m a t i c a 7, 1976. [ 2 0 ] G o r d o n , W. J . , a n d N e w e l l , G. F., " C l o s e d Q u e u e i n g S y s t e m w i t h E x p o n e n t i a l S e r v e r s " , O p e r . R e s . 15, pp 2 5 4 - 2 6 5 , 1967. [ 2 1 ] H i n e , J . H., M i t r a n i , . ! . , a n d ' T s u r , M. S., "The C o n t r o l o f R e s p o n s e T i m e s i n M u l t i - c l a s s S y s t e m s by Memory A l l o c a t i o n " , Comm. ACM 2 2 , 7 , pp 4 1 5 - 4 2 3 , J u l y 1979. [ 2 2 ] J a c k s o n , J . R., " J o b s h o p - l i k e Q u e u e i n g S y s t e m s " , Man. S c i . 9,1, p p 131-142, O c t . 1963. [ 2 3 ] K a r l i n , S. a n d T a y l o r , H. M., F i r s t C o u r s e i n S t o c h a s t i c  P r o c e s s e s , A c a d e m i c p r e s s , 1975. [ 2 4 ] K l e i n r o c k , L., " 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 T i m 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 S C o n g r e s s 6 8 , pp 8 3 8 - 8 4 5 , 1968. [ 2 5 ] K r i t z i n g e r , P., K r z e s i n s k i , A., a n d T e u n i s s e n , P., " D e s i g n o f a C o n t r o l S y s t e m f o r a T i m e s h a r i n g C o m p u t e r S y s t e m " , P e r f . 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 , pp 103-144, 1978. [ 2 6 ] K u s h n e r , H. J . , I n t r o d u c t i o n t o S t o c h a s t i c C o n t r o l , New Y o r k , H o l t , R e i n h a r t a n d W i n s t o n , 1973. [ 2 7 ] L a n d w e h r , C. E., "An E n d o g e n o u s P r i o r i t y M o d e l f o r L o a d C o n t r o l i n C o m b i n e d B a t c h - I n t e r a c t i v e C o m p u t e r S y s t e m s " , A c t a I n f o r m a t i c a , V o l * 7, No. 2, pp 15 3 - 1 6 6 , 1977. 83 [28] L a u e s e n , S., " J o b S c h e d u l i n g G u a r a n t e e i n g R e a s o n a b l e T u r n a r o u n d Time", A c t a I n f o r m a t i c a 2, pp 1-11, 1973. [29] L o , Raymond, "The A p p l i c a t i o n 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 T h e o r y t o A d a p t i v e P e r f o r m a n c e C o n t r o l o f Computer S y s t e m s " , M. S c . T h e s i s , D e p t . o f Computer S c i e n c e , U.B.C., J u n e 1980. [30] M e n d e n h a l l , W. , a n d S c h e a f f e r , R. L.', M a t h e m a t i c a l  S t a t i s t i c s w i t h A p p l i c a t i o n s , D uxbury P r e s s , N o r t h S c i t u a t e M a s s a c h u s e t t s , 1973. [31] P u t e r m a n , M. L., a n d S h i n , M. C , " A c t i o n E l i m i n a t i o n P r o c e d u r e s f o r M o d i f i e d P o l i c y I t e r a t i o n A l g o r i t h m s " , O p e r . Res., V o l . 30, No. 2, pp 301-318, M a r c h - A p r i l 1982. [32] R e i s e r , M. and K o b a y a s h i , H., " Q u e u e i n g N e t w o r k s w i t h M u l t i p l e C l o s e d C h a i n s : T h e o r y a n d C o m p u t a t i o n a l A l g o r i t h m s " , IBM J . Res. D e v e l o p . 19,3, pp 283-294, May 1975. [33] Simon, H. A. and Ando, A., " A g g r e g a t i o n o f V a r i a b l e s i n ' Dynamic S y s t e m s " , E c o n o m e t r i c a 29,2, pp 111-138, A p r i l 1961 . 

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}]}"
                            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-0051895/manifest

Comment

Related Items