UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A model of the UNIX time-sharing system under disk saturation Brachman, Barry Jeffrey 1983

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

Item Metadata

Download

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

Full Text

A MODEL OF THE UNIX TIME-SHARING SYSTEM UNDER DISK SATURATION By B A R R Y J E F F R E Y B R A C H M A N B.Sc, The University of Regina, 1981 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September 1983 © Barry Jeffrey Brachman, 1983 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the 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 and study. I f u r t h e r agree 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 copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head o f my department or by h i s or her r e p r e s e n t a t i v e s . I t i s understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be allowed without my w r i t t e n p e r m i s s i o n . Department of Co^PuTER Sh/£7vc£~ The U n i v e r s i t y of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 DE-6 (3/81) ii A b s t r a c t A d e t e r m i n i s t i c m o d e l o f t he U N I X t i m e - s h a r i n g s y s t e m u n d e r d i s k s a t u r a t i o n is p r e s e n t e d a n d a p e r f o r m a n c e e x p e r i m e n t o n a P D P - 1 1 / 3 4 is c o n d u c t e d to e s t a b l i s h t he v a l i d i t y a n d a c c u r a c y o f t h e m o d e l . T h e bas i s o f t h e m o d e l is t h a t t h e r a t i o o f m e a n f i le s y s t e m access r a t e s b e t w e e n t w o d i f f e ren t s y s t e m s c a n p r o v i d e , u n d e r c e r t a i n c i r -c u m s t a n c e s , a u s e f u l p e r f o r m a n c e c o m p a r i s o n b e t w e e n t he t w o s y s t e m s . G i v e n seve ra l w o r k l o a d a n d s y s t e m p a r a m e t e r s as w e l l as t h e e l apsed t i m e t o p e r f o r m the w o r k l o a d , t h e m o d e l p r e d i c t s f r o m a s e c o n d set o f p a r a m e t e r s t he e l apsed t i m e t o p e r f o r m t h e s e c o n d w o r k l o a d . W o r k l o a d , h a r d w a r e , a n d i n t e r n a l s y s t e m p a r a m e t e r s are i d e n t i f i e d a n d too l s are c o n s t r u c t e d t o r e c o r d these p a r a m e t e r s . A c o n t r o l l e d e x p e r i m e n t , u s i n g a s y n t h e t i c w o r k l o a d , is t h e n c o n d u c t e d . T h e r e su l t s a re a n a l y z e d a n d t h e m o d e l is e v a l u a t e d . T h e m o d e l is e x t e n d e d i n r e sponse t o r e g u l a r i t i e s d i s c o v e r e d i n t h e m e a s u r e m e n t d a t a . S a m p l e a p p l i c a t i o n s o f t he m o d e l are g i v e n . T h e s u i t a b i l i t y o f t h e t oo l s d e v e l o p e d a n d t h e m e t h o d s used are d i s c u s s e d . iii Table Of Contents A b s t r a c t i i 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 v i i 1. I n t r o d u c t i o n 1 1.1 O v e r v i e w '. 1 1.2 B a s i c G o a l s , A p p r o a c h , M o t i v a t i o n 2 2. S y s t e m D e s c r i p t i o n 5 2.1 T h e H a r d w a r e 5 2.2 T h e O p e r a t i n g S y s t e m 5 2.2.1 P rocesses 6 2.2.2 T h e S c h e d u l i n g P rocess a n d S w a p p i n g 7 2.2.3 T h e B l o c k I/O S y s t e m 10 3. T h e M o d e l 12 3.1 R e l a t e d W o r k 13 3.2 I n i t i a l W o r k 16 3.3 T h e Ba s i c M o d e l 18 3.3.1 W o r k l o a d a n d H a r d w a r e P a r a m e t e r s 18 3.3.2 T h e C P U B o u n d C a s e 19 3.3.3 T h e B a s i c M o d e l 21 4. T h e E x p e r i m e n t 24 4.1 O v e r v i e w 24 4.2 T h e S y n t h e t i c W o r k l o a d 24 4.2.1 C o n s t r u c t i o n o f t he P r o t o t y p e P roces s 25 4.3 D e s c r i p t i o n o f t h e M e a s u r e m e n t T o o l s 26 4.4 D e s i g n o f t he E x p e r i m e n t 3 0 4.5 I m p l e m e n t a t i o n 3 3 5. R e s u l t s a n d A n a l y s i s 35 5.1 E x p e r i m e n t a l R e s u l t s 35 5.2 A n a l y s i s o f t he M o d e l 38 5.3 S o u r c e s o f E r r o r 42 5.4 A p p l i c a t i o n s 4 3 6. C o n c l u s i o n s 46 6.1 T h e M o d e l a n d V a l i d a t i o n 46 iv 6.2 T o o l s a n d M e t h o d 46 6.3 D o m a i n o f A p p l i c a b i l i t y 47 6.4 F u t u r e R e s e a r c h 48 B i b l i o g r a p h y 49 V List of Tables T a b l e I R L 0 1 C h a r a c t e r i s t i c s 5 T a b l e II E x p e r i m e n t a l F a c t o r s a n d L e v e l s 31 T a b l e III D i s t r i b u t i o n s o f C o m p u t e L o o p s 32 T a b l e I V M e a n S w a p T i m e s 35 T a b l e V M e a n B l o c k R e a d / W r i t e T i m e 35 T a b l e V I R e s u l t s o f t h e F a c t o r i a l E x p e r i m e n t 38 T a b l e V I I S u p p l e m e n t a r y E x p e r i m e n t a l R e s u l t s 38 T a b l e V I I I S t a n d a r d D e v i a t i o n i n t h e P r e d i c t i o n s 3 9 vi List of Figures F i g u r e 1 O u t p u t o f t h e M o d e l v s . M e a s u r e d V a l u e s 40 F i g u r e 2 E l a p s e d T i m e v s . PN 41 vii Acknowledgement I w o u l d l i k e t o t h a n k D r . S a m C h a n s o n f o r h i s ideas a n d g u i d a n c e , c a r e f u l r e a d -ings o f t h e thes i s , a n d financial s u p p o r t t h r o u g h r e sea r ch a s s i s t a n t s h i p s . I a l so t h a n k D r . S o n V u o n g f o r b o t h h i s s u g g e s t i o n s a n d h i s r e a d i n g s o f t h e d r a f t s . I a m g r a t e f u l t o t h e D e p a r t m e n t o f M e t a l l u r g i c a l E n g i n e e r i n g f o r g i v i n g m e u n l i m -i t e d access t o t h e i r c o m p u t e r f a c i l i t y a n d i t s r esources . F i n a l l y , I w i s h t o t h a n k m y f a m i l y a n d f r i e n d s f o r t h e i r s u p p o r t a n d e n c o u r a g e -m e n t d u r i n g m y r e s e a r c h . Chapter One: Introduction Page 1 1. Introduction 1.1 Overview Time-sharing systems have long been implemented using the memory management technique of process swapping. Swapping involves exchanging one or more processes loaded in main memory with one previously written to secondary storage. Normally an entire process is swapped out. The technique is commonly used on systems without vir-tual memory capabilities; the entire process often must be resident to be executed. Although the use of virtual storage has become widespread, many small and medium size time-sharing systems still use swapping. A primary task of computer system performance evaluation is to predict the perfor-mance of a computer system under a given workload. The improvement study is con-cerned with modifying an existing system to increase its performance or decrease its cost, or both. Upgrading and tuning are two types of improvement study. Upgrading is replacing or adding one or more hardware components, while tuning is adjusting the sys-tem parameters to adapt the system to its workload. This thesis concentrates on the predictive aspect of performance evaluation (See Dowdey et al. [12] for an example of such a study). Because performance is a subjective concept, a precisely defined descriptor called a performance index is used to represent a system's performance or some of its aspects. Objective measures of performance include throughput rate, response time, and tur-naround time. Performance analysis involves determining the values of performance indices for given values of the installation's parameters. The performance information required by a study may be obtained from the system itself or from a model of it. C h a p t e r O n e : I n t r o d u c t i o n Page 2 A n u m b e r o f m a j o r obs t ac l e s s t a n d b e t w e e n t h e a n a l y s t a n d b o t h t he d e v e l o p m e n t a n d e v a l u a t i o n o f a u s e f u l m o d e l . F i r s t , o p e r a t i n g s y s t e m s are l a rge a n d c o m p l i c a t e d p r o g r a m s , i n c o r p o r a t i n g v a r i o u s s t ra teg ies t o c o n t r o l r e source s h a r i n g . T h e y are g e n -e r a l l y n o t d e s i g n e d w i t h f u t u r e p e r f o r m a n c e s t u d i e s i n m i n d . E v e n t s w i t h i n t h e s y s t e m o c c u r a s y n c h r o n o u s l y . M a n y c o m p l i c a t e d , ad hoc m e t h o d s are o f t e n u s e d a n d t h e p e r f o r -m a n c e o f these m e t h o d s i n c o m b i n a t i o n a n d u n d e r d i v e r s e c o n d i t i o n s is o f t e n u n c l e a r [21]. A s e c o n d m a j o r d i f f i c u l t y i n t h e e v a l u a t i o n o f c o m p u t e r s y s t e m s is t h e l a c k o f a q u a n t i t a t i v e u n d e r s t a n d i n g o f t h e r e l a t i o n s h i p b e t w e e n w o r k l o a d a n d p e r f o r m a n c e . In p e r f o r m a n c e e v a l u a t i o n , t h e r ea l w o r k l o a d is c h a r a c t e r i z e d b y a w o r k l o a d m o d e l w h i c h is used t o d r i v e a m o d e l o f t he r e a l s y s t e m . T h e w o r k l o a d m o d e l spec i f ies t h e c h a r a c t e r i s -t i c s o f t h e r e sou r ce d e m a n d s p l a c e d o n t h e dev i ces b y p r o g r a m s . It is n o t a l w a y s c l ea r w h a t a s y s t e m ' s " t y p i c a l " w o r k l o a d is because t h e w o r k l o a d o f t e n c h a n g e s f r o m m i n u t e t o m i n u t e a n d f r o m d a y t o d a y . T h e a n a l y s t is s o m e t i m e s i n t e r e s t e d i n e v a l u a t i n g a s y s t e m ' s p e r f o r m a n c e u n d e r w o r k l o a d s d i f f e r i n g f r o m t h e " n o r m a l " w o r k l o a d ; e.g., t he p e r f o r m a n c e o f t h e s y s t e m u n d e r heav i e r t h a n u s u a l l o a d . C h a r a c t e r i z i n g a w o r k l o a d r equ i r es d e t e r m i n i n g w i t h e n o u g h d e t a i l w h i c h o f i ts m a n y aspec ts i n f l uence t h e s y s t e m ' s p e r f o r m a n c e a n d t h e n c r e a t i n g a w o r k l o a d m o d e l c o m p o s e d o f a set o f q u a n t i f i a b l e w o r k -l o a d p a r a m e t e r s . W h e n t h e p r o d u c t i o n w o r k l o a d c a n n o t be u s e d o r does n o t meet t h e s t u d y ' s needs , a s y n t h e t i c w o r k l o a d m u s t be c o n s t r u c t e d a n d v a l i d a t e d . S y n t h e t i c w o r k -l oads a re c o m p a c t a n d r e p r o d u c i b l e w h i l e g i v i n g t h e a n a l y s t m o r e c o n t r o l o v e r t he e x p e r -i m e n t . T h e s e a d v a n t a g e s are o f t e n a c h i e v e d a t t he cos t o f r e p r e s e n t a t i v e n e s s . 1.2 Basic Goals, Approach, and Motivation T h e bas i c g o a l o f t h i s r e s e a r c h is t o d i s c o v e r t he m a j o r r e l a t i o n s h i p s b e t w e e n swap-C h a p t e r O n e : I n t r o d u c t i o n P a g e 3 p i n g a c t i v i t y , h a r d w a r e c h a r a c t e r i s t i c s , w o r k l o a d c h a r a c t e r i s t i c s , a n d s y s t e m p e r f o r m a n c e u n d e r t h e V e r s i o n 6 U N I X 1 t i m e - s h a r i n g s y s t e m . A s i m p l e m o d e l o f t h e c o m p u t e r s y s -t e m is h y p o t h e s i z e d , t h e n a c o n t r o l l e d e x p e r i m e n t is c o n d u c t e d t o tes t t h e v a l i d i t y , a c c u -r a c y , a n d r a n g e o f t h e m o d e l . F i r s t , a m o d e l o f t h e s y s t e m is p o s t u l a t e d b a s e d o n m a j o r w o r k l o a d a n d p e r f o r -m a n c e p a r a m e t e r s o b t a i n e d f r o m e a r l i e r w o r k [13,38] as w e l l as f r o m o b s e r v a t i o n s o f t h e s y s t e m u n d e r l o a d . T o o l s t o m e a s u r e a n d e x t r a c t p e r t i n e n t w o r k l o a d , h a r d w a r e , a n d s y s t e m i n f o r m a t i o n are d e v e l o p e d . S e ve r a l s y n t h e t i c w o r k l o a d s a re c o n s t r u c t e d a n d a c o n t r o l l e d e x p e r i m e n t is c o n d u c t e d , v a r y i n g seve ra l w o r k l o a d p a r a m e t e r s . T h e r e su l t s are t h e n a n a l y z e d a n d c o m p a r e d t o t h e p e r f o r m a n c e p r e d i c t i o n s o b t a i n e d f r o m t h e m o d e l . O n c e t h e a c c u r a c y a n d d o m a i n o f v a l i d i t y o f t he m o d e l a re d e t e r m i n e d , t he effect a d i f f e r en t n u m b e r o f p rocesses , a d i f f e r en t m a i n m e m o r y s i ze , o r d i f f e r en t d i s k c h a r a c t e r i s t i c s w o u l d h a v e o n s y s t e m p e r f o r m a n c e c a n be e v a l u a t e d . S u c h i n f o r m a t i o n c o u l d be u s e f u l i n d e c i d i n g w h e t h e r t h e a d d i t i o n o f m o r e m a i n m e m o r y o r a d i s k s y s t e m u p g r a d e , f o r e x a m p l e , w o u l d be a m o r e cost-ef fect ive s o l u t i o n t o a p e r f o r m a n c e p r o b l e m . A p r i m a r y m o t i v a t i o n f o r t h i s p r o j e c t is t o a r r i v e a t a b e t t e r u n d e r s t a n d i n g o f h o w s w a p p i n g i n f l uences p e r f o r m a n c e . S o m e w o r k has been d o n e i n t h i s a r e a (see S e c t i o n 3.1), b u t m o s t r e s e a r c h o n m e m o r y m a n a g e m e n t t e c h n i q u e s i n a t i m e - s h a r i n g e n v i r o n -m e n t has been c o n c e r n e d w i t h p a g i n g s y s t e m s [9]. It is h o p e d t h a t b e t t e r i n s i g h t s i n t o s w a p p i n g m a y be u s e f u l i n c o m p a r i n g s w a p p i n g t o p a g i n g a n d p e r h a p s a n y s i m i l a r i t i e s m a y a l l o w s o m e o f t h e r e su l t s o b t a i n e d f r o m one s c h e m e t o be a p p l i e d t o t h e o t h e r . A l l e x p e r i m e n t a l w o r k w a s p e r f o r m e d o n a U N I X s y s t e m . T h e U N I X s y s t e m is a p o p u l a r s w a p p i n g s y s t e m 2 a n d is b e c o m i n g t he de facto s t a n d a r d f o r 16-bit c o m p u t e r s . 1 UNIX is a trademark of Bell Laboratories. 2 The Berkeley UNIX implementation uses paging. C h a p t e r O n e : I n t r o d u c t i o n Page 4 It is h o p e d t h a t t h e r e su l t s o f t h i s w o r k w i l l be use fu l t o U N I X i n s t a l l a t i o n s i n p a r t i c u l a r a n d p e r h a p s t o o t h e r s w a p p i n g s y s t e m s as w e l l . It is o b v i o u s t h a t s w a p p i n g i n i t se l f is n o t a " b a d " m e m o r y m a n a g e m e n t t e c h n i q u e . If s w a p p i n g t i m e a n d o v e r h e a d a re m a d e neg l i g i b l e ( say b y t h e i n t r o d u c t i o n o f a so l i d-s t a t e , D M A - b a s e d s w a p p i n g d e v i c e o r b y a b a n k s w i t c h i n g m e c h a n i s m ) , t h e n i t e f f ec t i ve l y becomes a p h y s i c a l add ress e x t e n s i o n m e c h a n i s m w h i l e n o t r e l i e v i n g t h e v i r -t u a l add ress l i m i t a t i o n s . 3 N o t e t h a t i f s w a p p i n g c o u l d be p e r f o r m e d " i n s t a n t l y " , t h e s y s -t e m w o u l d d o so a f t e r e a ch q u a n t u m e x p i r a t i o n o r w h e n e v e r a process b l o c k e d , w h i c h -ever c a m e f i r s t . A s w i l l be seen i n S e c t i o n 3.2.2, i f r e a s o n a b l e s c h e d u l i n g a s s u m p t i o n s are m a d e , C P U b o u n d w o r k l o a d s c a n execu te w i t h o u t s w a p p i n g s i g n i f i c a n t l y i m p a c t i n g p e r -f o r m a n c e . It is less a p p a r e n t h o w s w a p p i n g affects t h e p e r f o r m a n c e o f t h e sma l l- to-m e d i u m - s i z e d m a c h i n e s w h e r e d i s k a n d m e m o r y resources a re o f t e n a t a p r e m i u m a n d whe re p e r f o r m a n c e is o f t e n s ens i t i v e t o s m a l l changes i n t h e w o r k l o a d c h a r a c t e r i s t i c s . T h i s thes i s is c o n c e r n e d w i t h t h e a n a l y s i s o f s w a p p i n g o n these s m a l l s y s t e m s a n d t h e d e v e l o p m e n t o f a c o n c e p t u a l m o d e l w h i c h m a y be used t o e s t i m a t e p e r f o r m a n c e changes d u e t o v a r i o u s h a r d w a r e o r w o r k l o a d c h a n g e s . C h a p t e r 2 c o n t a i n s a d e s c r i p t i o n o f t h e h a r d w a r e a n d s o f t w a r e u s e d i n t h i s s t u d y . C h a p t e r 3 desc r i bes a m o d e l o f t h e s y s t e m w h i c h w i l l be e v a l u a t e d i n C h a p t e r 5. C h a p t e r 4 dea l s w i t h t h e d e s c r i p t i o n o f t h e w o r k l o a d a n d t h e e x p e r i m e n t a l m e t h o d . T h e r e su l t s o f t h e e x p e r i m e n t are d e t a i l e d i n C h a p t e r 5 a n d a n ana l y s i s is c o n d u c t e d . C o n -c l u s i o n s are p r e s e n t e d i n C h a p t e r 6. A bas i c u n d e r s t a n d i n g o f o p e r a t i n g s y s t e m s is a s s u m e d t h r o u g h o u t t h i s t h e s i s , a l t h o u g h p r i o r k n o w l e d g e o f U N I X is n o t necessa r y . 3 The same can be said about a solid-state paging device. Chapter Two: System Description Page 5 2. System Description 2.1 The Hardware T h e h o s t m a c h i n e f o r t h i s p r o j e c t is a D i g i t a l E q u i p m e n t C o r p o r a t i o n P D P - 1 1 / 3 4 A [27]. It has 6 4 K w o r d s (2 8-bit b y t e s p e r w o r d ) o f m a i n m e m o r y ( M S 1 1 - L B ) . M e m o r y m a y be e x p a n d e d t o t h e m a x i m u m o f 2 4 8 K b y t e s . S e c o n d a r y s to rage cons i s t s o f 2 R L 0 1 c a r t r i d g e d i s k d r i v e s w h i c h sha re a s ing le c o n t r o l l e r [28]. T h e P D P - 1 1 a l l o w s b o t h t h e C P U a n d d i s k c o n t r o l l e r s t o be s i m u l t a n e o u s l y a c t i v e ; i.e., d i s k I/O c a n be o v e r l a p p e d w i t h p r o c e s s i n g . A l t h o u g h t h e c o n t r o l l e r u sed p e r m i t s a r u d i m e n t a r y o v e r l a p p e d seek c a p a b i l i t y , t h i s w a s n o t u s e d . T h e c h a r a c t e r i s t i c s o f t h e R L 0 1 d i s k d r i v e are g i v e n i n T a b l e I. T h e s y s t e m has f o u r i n t e r a c t i v e t e r m i n a l s , t h ree o f w h i c h are c o n n e c t e d t o a D Z 1 1 se r i a l c o m m u n i c a t i o n s i n t e r f a c e . O t h e r p e r i p h e r a l s i n c l u d e a p l o t t e r , D U P l l s e r i a l c o n t r o l l e r , I E C 1 1 ( I E E E - 4 8 8 ) b u s c o n t r o l l e r , a n d a se r i a l l i ne t o t h e c a m p u s n e t w o r k . RL01 Characteristics Surfaces: 2 Tracks/Surface: 256 512-byte Blocks/Track: 20 Track-To-Track Seek: 15 msec. Ave. Latency Time: 12.5 msec. Ave. Seek Time: 55 msec. Ave. Access Time: 67.5 msec. Transfer Rate: 512.5K bytes/sec. (peak) 2.35 /xsec/byte (ave.) Table I 2.2 The Operating System Chapter Two: System Description Page ft T h e o p e r a t i n g s y s t e m i n use is a l o c a l l y m o d i f i e d v e r s i o n o f t h e S i x t h E d i t i o n U N I X , t h e ea r l i e s t d i s t r i b u t e d s y s t e m . O v e r v i e w s o f t h e s y s t e m c a n be f o u n d i n R i t c h i e a n d T h o m p s o n [31], w h i l e d e t a i l e d d e s c r i p t i o n s o f t h e i n t e r n a l s c a n be f o u n d i n [22] a n d [38]. M a n y o f t h e l o c a l m o d i f i c a t i o n s t o U N I X a re n o t s i g n i f i c a n t t o t h i s s t u d y ; t h o s e t h a t are w i l l be p r e s e n t e d s h o r t l y . F e w U N I X i n s t a l l a t i o n s r u n a c o p y o f U N I X t h a t has n o t b e e n a l t e r e d i n s o m e w a y a n d few h a v e t h e s a m e h a r d w a r e c o n f i g u r a t i o n . B e c a u s e U N I X s y s t e m s r u n p r i m a r i l y o n P D P - 1 1 m i n i c o m p u t e r s , t h e m a x i m u m n u m b e r o f users is u s u a l l y less t h a n 3 0 . T h e m a x i m u m process s ize is a l m o s t 6 4 K b y t e s o n t h e s m a l l e r m a c h i n e s a n d t w i c e t h a t o n P D P - l l s w i t h s e p a r a t e i n s t r u c t i o n a n d d a t a spaces . B e cause t h e r e are n o w s e v e r a l v e r s i o n s o f U N I X d i s t r i b u t e d b y B e l l L a b s , a n y n o n q u a l i f i e d r e f e r -ence t o U N I X i n t h i s p a p e r w i l l i m p l y t h e S i x t h E d i t i o n v e r s i o n . It is be l i e ved t h a t t h e o t h e r s w a p p i n g v e r s i o n s o f U N I X are s i m i l a r e n o u g h t o t h e V e r s i o n 6 s y s t e m t h a t m a n y o f t h e r e su l t s o f t h i s p r o j e c t a p p l y t o t h e m as w e l l , a l t h o u g h we do n o t h a v e access t o these s y s t e m s t o v e r i f y o u r be l i e f . T h e f o l l o w i n g sec t i ons p r o v i d e a b r i e f o v e r v i e w o f t hose areas o f U N I X a p p l i c a b l e t o t h i s t h e s i s . 2.2.1 Processes R i t c h i e a n d T h o m p s o n [31] de f i ne a n i m a g e t o be " a c o m p u t e r e x e c u t i o n e n v i r o n -m e n t " . T h e e n v i r o n m e n t i n c l u d e s a m e m o r y i m a g e , gene ra l r e g i s t e r v a l u e s , s t a t u s o f o p e n files, e t c . A p rocess is d e f i n e d t o be t h e e x e c u t i o n o f a n i m a g e . W h i l e t h e p roces so r is e x e c u t i n g o n b e h a l f o f a p rocess , t h e i m a g e m u s t r e s i de i n m a i n m e m o r y . D u r i n g t h e e x e c u t i o n o f o t h e r processes i t m a y be s w a p p e d - o u t t o s e c o n d a r y s to r age . T h e ex i s t ence o f a p rocess i m p l i e s a p p r o p r i a t e e n t r i e s i n t h e s y s t e m d a t a s t r u c t u r e s [22]. U N I X p e r -m i t s t he use r to i n i t i a t e a n u m b e r o f c o n c u r r e n t processes . T h i s p a r t i c u l a r f e a t u r e w a s Chapter Twoi System Description Page 7 u t i l i z e d b y t h e s y n t h e t i c w o r k l o a d , w h i c h is d e s c r i b e d i n S e c t i o n 4.2. T h e u s e r - m e m o r y p a r t o f a n i m a g e is d i v i d e d i n t o t h r ee l og i c a l s e g m e n t s : t e x t , d a t a , a n d s t a c k . G e n e r a l l y , a l l t h r e e s e g m e n t s a re c o n t i g u o u s i n m a i n m e m o r y . A s w a p p e d - o u t i m a g e is s t o r e d c o n t i g u o u s l y ( l og i c a l l y ) o n t h e s w a p p i n g dev i ce . It is p o s s i -b le t o s e p a r a t e t h e p r o g r a m c o d e a n d t o m a k e i t s h a r a b l e a m o n g a l l users . In t h i s case t h e r e a d - o n l y p r o g r a m t e x t need n e v e r be s w a p p e d - o u t . 2.2.2 P rocessor Schedul ing and S w a p p i n g S i n c e b o t h s c h e d u l i n g a n d s w a p p i n g are i m p o r t a n t t o t h i s w o r k t h e y w i l l be d i s -c u s s e d i n d e t a i l . T h e i n f o r m a t i o n is a s u m m a r y o f T h o m p s o n [38]. P r o c e s s s y n c h r o n i z a t i o n is a c c o m p l i s h e d b y h a v i n g p r o c e d u r e s w a i t f o r e v e n t s . E v e n t s a re , b y c o n v e n t i o n , addresses w i t h i n t h e k e r n e l o f t ab l e s a s soc i a t ed w i t h t hose e v e n t s . P rocesses a re s u s p e n d e d w h e n , f o r e x a m p l e , t h e y w a i t f o r t h e c o m p l e t i o n o f a n I/O r eques t o r w h e n t h e y r equ i r e a r e sou r ce w h i c h is ( t e m p o r a r i l y ) u n a v a i l a b l e . W h e n a n e v e n t o c c u r s , a n y processes w a i t i n g fo r t h e e v e n t are a w a k e n e d . A l t h o u g h t h i s m e t h o d is q u i t e s i m p l e , i t c a n l ead t o l a rge ine f f i c i enc ies . If, f o r e x a m p l e , a n u m b e r o f processes are w a i t i n g f o r t h e s a m e r e sou r ce t o b e c o m e a v a i l a b l e a n d a l l h a v e been s w a p p e d - o u t , t h e n w h e n t h e r e sou r ce b e c o m e s a v a i l a b l e a l l s u c h processes w i l l e v e n t u a l l y be s w a p p e d - i n . O n l y t h e first w a i t i n g process s w a p p e d - i n w i l l ge t t h e r e sou r ce a n d t h e r e m a i n d e r w i l l w a i t a g a i n , p o s s i b l y b e i n g s w a p p e d - o u t . T h e s y s t e m c a l l sleep, w h i c h s u s p e n d s t h e c a l l e r f o r t h e n u m b e r o f s e conds spec i f i ed b y t he a r g u m e n t , c a n be e spec i a l l y i ne f f i c i en t . S u p p o s e t h a t one p rocess o n a b u s y s y s t e m f r e q u e n t l y sleeps f o r a s h o r t p e r i o d a n d t h a t a s e c o n d process has i s sued a sleep c a l l w i t h a l a rge a r g u m e n t . E a c h t i m e t h e first p rocess a w a k e n s , t h e s e c o n d p r o -cess w i l l a l so a w a k e n , be s w a p p e d - i n , d e t e r m i n e t h a t i t s sleep has n o t y e t e x p i r e d , a n d Chapter Two: System Description Page 8 s u b s e q u e n t l y be s w a p p e d - o u t . Sleep has been r e p l a c e d i n newer v e r s i o n s o f U N I X b y a s u b r o u t i n e o f t h e s a m e n a m e a n d t w o new s y s t e m c a l l s , pause a n d a l a r m , w h i c h are m o r e e f f i c i en t . T h e s y s t e m keeps t r a c k o f a l a r m r eques ts f o r e a c h process so t h a t a p r o -cess a w a k e n i n g f r o m a s leep w i l l n o t d i s t u r b o t h e r processes w h i c h h a v e c a l l e d t h e sleep s u b r o u t i n e . A n i n t ege r p r i o r i t y is a s s o c i a t e d w i t h e a c h process . T h e p r i o r i t y o f a s y s t e m p r o -cess ( i .e., t h e s c h e d u l e r o r a user-process e x e c u t i n g w i t h i n t he k e r n e l ) is a ss igned b y t h e code w h i c h issues t h e w a i t o n a n e v e n t . T h e p r i o r i t y is r o u g h l y i n v e r s e l y p r o p o r t i o n a l t o t h e r e a c t i o n t i m e t h a t one w o u l d expec t f o r s u c h a n e v e n t . D i s k - r e l a t e d even t s h a v e h i g h p r i o r i t y , t e r m i n a l i n p u t o r o u t p u t h a v e low p r i o r i t y a n d t ime-o f-day e v e n t s h a v e v e r y l ow p r i o r i t y . T h o m p s o n [38] c l a i m s t h a t t h e d i f fe rence i n s y s t e m process p r i o r i t i e s has l i t t l e o r no p e r f o r m a n c e i m p a c t . A l l user-process p r i o r i t i e s are l o w e r t h a n t he l owes t s y s t e m p r i o r i t y . S i n c e h i g h - p r i o r i t y processes a re c h o s e n first b y t h e s c h e d u l e r , w a k i n g a n y s y s t e m process w i l l p r e e m p t a n y c u r r e n t l y r u n n i n g user-process . User-process p r i o r i -t ies a re a s s i gned b y a n a l g o r i t h m b a s e d o n t h e recen t r a t i o o f t h e a m o u n t o f c o m p u t e t i m e t o rea l t i m e i n t h e l as t r ea l t i m e u n i t a s s igned a l ow user p r i o r i t y . T h e s y s t e m -process r e v e r t i n g t o a user-process w i l l c o n t i n u e t o e n j o y t h e h i g h p r i o r i t y u n t i l i t m a k e s a s y s t e m c a l l , i n i t i a t e s a t r a p , o r u p o n t h e n e x t one-second c l o c k i n t e r r u p t , w h i c h e v e r o c c u r s first. T h e r e is n o t i m e q u a n t u m as s u c h , b u t i t w i l l g e n e r a l l y be a t m o s t one s e c o n d a n d l o o p i n g user processes w i l l be s c h e d u l e d r o u n d - r o b i n . T o s u p p o r t m o r e processes t h a n m a i n m e m o r y c a n s i m u l t a n e o u s l y c o n t a i n , U N I X u t i l i z e s t h e m e m o r y m a n a g e m e n t t e c h n i q u e k n o w n as s w a p p i n g [8]. A process w h i c h c a n n o t be e n t i r e l y l o a d e d i n t o m a i n m e m o r y res ides o n s e c o n d a r y s t o r age u n t i l i t c a n rep l a ce , o r be e x c h a n g e d w i t h o n e o r m o r e l o a d e d processes . T h e user d a t a s e g m e n t , t h e s y s t e m d a t a s e g m e n t a n d t h e t e x t s e g m e n t are s w a p p e d - i n a n d s w a p p e d - o u t as n e e d e d . Chapter Two: System Description Page 0 T h e user d a t a s e g m e n t a n d s y s t e m d a t a s e g m e n t are k e p t i n c o n t i g u o u s p r i m a r y m e m o r y t o r e d u c e s w a p p i n g l a t e n c y . A l l o c a t i o n o f b o t h m a i n m e m o r y a n d s w a p space is p e r f o r m e d b y t h e s a m e first-fit a l g o r i t h m . M e m o r y c o m p a c t i o n is n o t p e r f o r m e d so t h a t w h i l e t h e r e m a y be e n o u g h t o t a l f ree m e m o r y , t h e r e m a y n o t be e n o u g h c o n t i g u o u s m a i n m e m o r y t o l o a d a p rocess . T h i s a d d s t o t h e s w a p p i n g l o a d . W h e n a process g r o w s ( U N I X p e r m i t s a process t o d y n a m i c a l l y m o d i f y t h e s ize o f i t s d a t a area ) , a new p iece o f p r i m a r y m e m o r y is a l l o c a t e d . If t he r e is n o t e n o u g h p r i m a r y m e m o r y , t he s w a p p i n g m e c h a n i s m is u s e d a n d t he p rocess is e v e n t u a l l y s w a p p e d - i n w i t h i t s new s ize . T h e s w a p p i n g m e c h a n i s m m a y a lso be i n v o k e d w h e n a process " f o r k s " a c o p y o f i t se l f . T h e s c h e d u l e r is i m p l e m e n t e d as a k e r n e l p rocess . It e x a m i n e s t h e process t a b l e , l o o k i n g f o r t h e o l d e s t s w a p p e d - o u t p rocess w h i c h is r e a d y t o r u n . If t he r e is su f f i c i en t p r i m a r y m e m o r y , t h e process is s w a p p e d - i n a n d t h e s c h e d u l e r c o n t i n u e s t o l o o k f o r a p rocess t o s w a p - i n . If t h e r e is i n s u f f i c i e n t f ree m a i n m e m o r y , t h e s c h e d u l e r searches f o r a l o a d e d p rocess w h i c h is w a i t i n g f o r a " s l o w e v e n t " ( i .e. , a l o w - p r i o r i t y s y s t e m even t w h i c h t e n d s t o t a k e m u c h l o n g e r t h a n t h e e x e c u t i o n o f a s w a p , f o r e x a m p l e , t e r m i n a l I/O). I f s u c h a process does n o t e x i s t , t h e t i m e t h a t t h e s w a p p e d - o u t p rocess has been o n d i s k is c o m p a r e d t o a n i n t e g e r c o n s t a n t , s a y MINTIMEOUT. If t h e process has n o t been o u t a t leas t MINTIMEOUT s e conds , t h e s c h e d u l e r w a i t s . If t h e s w a p p e d - o u t p rocess sa t i s f ies t h i s c o n d i t i o n , a s e a r c h is c o n d u c t e d f o r t he o l d e s t r e s i d e n t p rocess . If t h i s p r o -cess has n o t b e e n l o a d e d f o r a t leas t MINTIMEIN s e c o n d s , t h e s c h e d u l e r w a i t s . 4 O t h e r -w i se t h i s o ldes t p rocess is s w a p p e d - o u t , i t s m e m o r y is f r eed , a n d t h e s c h e d u l e r goes b a c k to l o o k f o r a p rocess t o s w a p - i n . T h e s c h e d u l e r w a i t s f o r a s w a p - i n o r a s w a p - o u t t o c o m p l e t e . O n l y one s c h e d u l i n g 4 In the distribution system MINTIMEOUT = 3 seconds md MINTIMEIN=2 seconds. In this work both were 3 seconds. Chapter Two: System Description Page 10 s w a p c a n be s u b m i t t e d a t a t i m e . If t h e s w a p dev i c e is c o n n e c t e d t o t h e s a m e c o n t r o l l e r as a file s y s t e m d e v i c e , s w a p s are s e r v i c e d i n t h e s a m e m a n n e r as a n y o t h e r d i s k r eques t . T h o m p s o n [38] obse r ves t h a t i f t h e s w a p p i n g dev i c e is a lso u sed f o r file s to rage (as i t is o n m o s t s m a l l s y s t e m s ) , t h e s w a p p i n g t ra f f i c s eve re l y i m p a c t s t he file s y s t e m t r a f f i c . If t h e c a p a c i t y o f t he d r i v e is s m a l l , t h e s w a p a r e a is u s u a l l y p l a c e d o n t h e i nne r-mos t t r a c k s o f t h e d i s k , i n c r e a s i n g t h e seek t i m e i n v o l v e d i n a s w a p . 2.2.3 The Block I/O System T h e b l o c k I/O s y s t e m cons ide r s a d e v i c e t o h a v e a n u m b e r o f 512-byte m e m o r y b l o c k s . T h e s e dev i ces are accessed t h r o u g h a c o m m o n b u f f e r i n g m e c h a n i s m [29]. T h e s y s t e m m a i n t a i n s a n u m b e r o f 512-by te buf fers i n t h e k e r n e l add res s s p a c e , 5 e a c h a s s i g n e d a dev i c e n a m e a n d a d e v i c e a d d r e s s . T h i s bu f fe r p o o l c o n s t i t u t e s a d a t a cache f o r t h e b l o c k d e v i c e s . O n a r e a d r e q u e s t , t h e c a c h e is s ea r ched f o r t he d e s i r e d b l o c k . If t h e b l o c k is f o u n d , t h e d a t a a re m a d e a v a i l a b l e t o t h e r eques t e r w i t h o u t a n y p h y s i c a l I/O. If t h e b l o c k is n o t i n t h e c a c h e , t h e least r e c e n t l y u sed b l o c k i n t h e c a che is r e n a m e d , t h e a p p r o p r i a t e d e v i c e d r i v e r is c a l l e d t o fill u p t he r e n a m e d buf fe r , a n d t h e d a t a a re m a d e a v a i l a b l e . W r i t e r eques t s are h a n d l e d s i m i l a r l y ; h o w e v e r t h e w r i t e is p e r -f o r m e d b y m a r k i n g t he bu f f e r a n d p h y s i c a l I/O is d e f e r r e d u n t i l t h e bu f f e r is r e n a m e d . If less t h a n a c o m p l e t e b l o c k is b e i n g w r i t t e n , t he b l o c k m u s t be r e a d first. A user-p rocess , /etc/update, execu tes a s y s t e m c a l l e v e r y 30 s e conds w h i c h causes a l l d e l a y e d w r i t e o p e r a t i o n s t o be flushed f r o m the queues . W h e n p h y s i c a l I/O is r e q u i r e d , t he a p p r o p r i a t e dev i c e d r i v e r is c a l l e d t o l i n k t h e buf fe r i n t o i t s queue a n d t o execu te t h e r e a d o r w r i t e o p e r a t i o n . N o r m a l l y t h e U N I X On thia system, 20. Chapter Two: System Description Page 11 R L 0 1 dev i c e d r i v e r p e r f o r m s the r eques t s i n a first-come first-served m a n n e r . T h e s y s -t e m u n d e r s t u d y , h o w e v e r , w a s m o d i f i e d t o use t h e L O O K d i s k s c h e d u l i n g p o l i c y [36,37]. Chapter Three: The Model Page 12 3. The Model A m o d e l is a r e p r e s e n t a t i o n b u i l t t o s t u d y a s y s t e m a n d cons i s t s o f a c e r t a i n a m o u n t o f o r g a n i z e d i n f o r m a t i o n a b o u t i t . M o d e l s r e p r e s e n t i n g t h e s a m e s y s t e m m a y d i f fe r i n t h e i r p u r p o s e , s t a n d p o i n t , o r a m o u n t o f d e t a i l . A n a d v a n t a g e o f m o d e l i n g o v e r d i r e c t m e a s u r e m e n t is t h a t i t a l l ows t h e a n a l y s t t o o b t a i n r e su l t s w h e n t h e t a r g e t s y s t e m is n o t a v a i l a b l e ; i.e., i n t h e d e s i g n o f new c o m p u t e r s y s t e m s , i n i m p r o v e m e n t s t u d i e s w h e r e t h e effects o f new h a r d w a r e o r a r e c o n f i g u r e d s y s t e m are o f i n t e r e s t , o r w h e r e i t w o u l d be t o o c o s t l y o r i m p r a c t i c a l t o g i ve t h e a n a l y s t d i r e c t c o n t r o l . V e r b a l a n d s o m e w h a t . s u p e r f i c i a l m o d e l s o f a r e a l s y s t e m are c a l l e d c o n c e p t u a l m o d e l s . C o n c e p t u a l m o d e l s are t h e bas i s o f m e a s u r e m e n t t e c h n i q u e s a n d o f t w o m a j o r t y p e s o f m o d e l i n g t e c h n i q u e s : s i m u l a t i o n m e t h o d s a n d a n a l y t i c m e t h o d s . G r a h a m [15] g ives a b r i e f o v e r v i e w o f m o d e l i n g . A n a n a l y t i c m o d e l is c o m p o s e d o f m a t h e m a t i c a l r e l a -t i o n s h i p s w h i c h r e p r e s e n t t h e s y s t e m . A l t h o u g h m a n y s i m p l i f y i n g a s s u m p t i o n s m a y o f t e n be m a d e a b o u t t h e w o r k l o a d p a r a m e t e r s a n d t h e o p e r a t i n g s y s t e m ' s c h a r a c t e r i s -t i c s , a m o d e l c a n s t i l l p r o v i d e s a t i s f a c t o r y r e su l t s a t a c o m p a r a t i v e l y l ow cos t . Q u e u e i n g m o d e l s [14,19] a n d m o d e l s b a s e d o n o p e r a t i o n a l ana l y s i s [4,10] are t w o s u c h a n a l y t i c m e t h o d s . G r e n a n d e r a n d T s a o [16] asser t t h a t q u e u i n g m o d e l s a lone are i n su f f i c i en t t o s t u d y a n d e v a l u a t e c o m p u t i n g s y s t e m s , b u t t h a t t h e y he lp i n u n d e r s t a n d i n g t h e b e h a v i o u r o f t h e s y s t e m . A s i m u l a t i o n m o d e l r e p r o d u c e s t h e b e h a v i o u r i n t h e t i m e d o m a i n o f a s y s t e m a c c o r d i n g t o s o m e c o n v e n t i o n s w h i c h e s t a b l i s h a c o r r e s p o n d e n c e b e t w e e n v a r i o u s aspec ts o f t h e m o d e l a n d o f t h e s y s t e m [14]. S i m u l a t i o n is m o r e flexible b u t is a lso m o r e c o s t l y t h a n a n a l y t i c t e c h n i q u e s . S i m u l a t i o n m a y be used w h e n t h e a n a l y t i c e q u a t i o n s are i n s o -l u b l e o r a n a n a l y t i c d e s c r i p t i o n is u n c l e a r . It t o o suffers as t h e m o d e l g r o w s m o r e c o m -p l e x . It is o f t e n necessa ry t o v a l i d a t e t h e r e su l t s o f s i m u l a t i o n w i t h a n a l y t i c m e t h o d s o r Chapter Three: The Model Page 13 d i r e c t m e a s u r e m e n t because i t is d i f f i c u l t t o k n o w i f t he s i m u l a t i o n p r o g r a m i t se l f is c o r r e c t . T h e r e su l t s o f s i m u l a t i o n are n o t a l w a y s easy t o i n t e r p r e t w i t h r espec t t o cause a n d effect r e l a t i o n s h i p s b e t w e e n l o a d a n d s y s t e m p a r a m e t e r a n d p e r f o r m a n c e measu res , w h i l e c l o s e d - f o r m a n a l y t i c s o l u t i o n s o f t e n y i e l d s u c h i n s i g h t s [24]. H y b r i d s i m u l a t i o n uses a n a n a l y t i c m o d e l t o r ep l a ce p a r t o f t h e s y s t e m b e i n g m o d e l e d , s i m p l i f y i n g t he o v e r a l l s i m u l a t i o n . T h e d e v e l o p m e n t o f a m o d e l o f t e n p r o d u c e s i n s i g h t s w h i c h have g r e a t e r i m p l i c a -t i o n s t h a n t h e p e r f o r m a n c e s t u d y s ince i t r equ i res t h e a n a l y s t t o seek o u t a s i ng l e , u n i f i e d p i c t u r e o f w h a t m a y o f t e n a p p e a r c o m p l i c a t e d a n d i n c o n s i s t e n t . M o d e l s n o t o n l y p r o v i d e q u a n t i t a t i v e r e su l t s f r o m g i v e n v a l u e s o f p a r a m e t e r s , b u t a lso m a y p l a y a q u a l i -t a t i v e ro le b y d e v e l o p i n g t he a n a l y s t ' s i n t u i t i o n a b o u t a c t u a l s y s t e m s . A d r a w b a c k t o m o d e l i n g is t h e poss ib l e l a c k o f fidelity t o t h e m o d e l e d s y s t e m . A n y m o d e l m u s t be v a l i d a t e d be fo re i t c a n be used t o p r o d u c e t h e i n f o r m a t i o n n e e d e d fo r e v a l u a t i o n . T h e r e is n o b e t t e r w a y o f c o n f i r m i n g c o n f i d e n c e i n a m o d e l t h a n b y e x p e r i -m e n t a t i o n . O f cou r se m e a s u r e m e n t c a n n o t be used w h e n t h e m o d e l e d s y s t e m does n o t ex is t o r is n o t a v a i l a b l e . 3.1 Related Work M o s t m o d e l i n g a n d a n a l y s i s o f m e m o r y m a n a g e m e n t t e c h n i q u e s f o r t i m e - s h a r i n g s y s t e m s h a v e been d i r e c t e d t o w a r d s p a g i n g r a t h e r t h a n s w a p p i n g . M a n y s t u d i e s are c o n c e r n e d w i t h b a l a n c i n g on- l ine l o a d w i t h b a t c h l o a d ; i.e., t h e t r adeo f f b e t w e e n t u r -n a r o u n d t i m e a n d s y s t e m u t i l i z a t i o n . W o r k w h i c h is r e l a t e d t o s c h e d u l i n g m e t h o d s d e s i g n e d t o r e d u c e s w a p p i n g w i l l be m e n t i o n e d here a l o n g w i t h m o d e l i n g w o r k . S c h e r r [33] d e v e l o p e d one o f t h e first s w a p p i n g m o d e l s , c o n s t r u c t i n g a s i m p l e m o d e l o f t h e C o m p a t i b l e T i m e - S h a r i n g S y s t e m ( C T S S ) . T h i s e a r l y i n t e r a c t i v e s y s t e m used Chapter Three: The Model Page 14 s w a p p i n g a n d s u p p o r t e d o n l y a s ing le c o m p l e t e l y l o a d e d p rocess . A n i n t e r a c t i o n was d e s c r i b e d b y t h e a m o u n t o f p r o c e s s o r t i m e r e q u i r e d d u r i n g t h e i n t e r a c t i o n , i n c l u d i n g s y s -t e m o v e r h e a d a n d u n o v e r l a p p e d file s y s t e m access t i m e s , as w e l l as t h e p r o g r a m s ize . N o o v e r l a p p e d p r o c e s s i n g a n d c h a n n e l o p e r a t i o n w a s a l l o w e d . B o t h s i m u l a t i o n a n d c o n t i n u o u s - t i m e M a r k o v m o d e l s we re d e s c r i b e d . In t h e M a r k o v m o d e l , S c h e r r t o o k t h e m e a n p roces so r t i m e p e r i n t e r a c t i o n t o i n c l u d e t he necessa ry m e a n s w a p t i m e pe r i n t e r a c t i o n s ince t h e p roces so r w a s id le w h i l e s w a p p i n g . D i s t r i b u t i o n b a s e d c a l c u l a t i o n s we re used t o d e t e r m i n e b o t h s w a p p i n g a n d file access t i m e s i n t h e s i m u l a t i o n . T h e t h i n k t i m e d i s t r i b u t i o n a n d t h e C P U se r v i ce t i m e d i s t r i b u t i o n were a s s u m e d to be e x p o n e n -t i a l l y d i s t r i b u t e d . G i v e n t he n u m b e r o f a c t i v e users , t h e m e a n response t i m e p r e d i c t e d b y t h e a n a l y t i c m o d e l w a s a c c u r a t e w h e n c o m p a r e d t o t h e a c t u a l m e a s u r e m e n t d a t a . C o f f m a n [7] a n a l y z e s t i m e - s h a r i n g a l g o r i t h m s w h i c h are d e s i g n e d p r i m a r i l y t o r e d u c e s w a p p i n g . T h e o b s e r v a t i o n m a d e is t h a t t o r e d u c e o v e r h e a d , t h e t i m e q u a n t u m s h o u l d dec rease u n t i l a c e r t a i n p o i n t w i t h i n c r e a s i n g l o a d , t h e n inc rease t o r educe s w a p -p i n g . A m u l t i p l e q u a n t u m a l g o r i t h m is p r e s e n t e d . T h e a l g o r i t h m r e t a i n s t h e gene ra l s t r u c t u r e o f t he r o u n d - r o b i n d i s c i p l i n e a n d t he m u l t i p l e - l e v e l w a i t i n g t i m e d i s t r i b u t i o n s excep t u n d e r h e a v y l o a d w h e n i t a v o i d s s a t u r a t i o n c o n d i t i o n s b y i n c r e a s i n g t h e t ime-s l i ce . T h i s inc reases t h e e f f i c i ency o f s y s t e m o p e r a t i o n . B e r n s t e i n a n d S h a r p [2] p r o p o s e a p rocesso r s c h e d u l i n g a l g o r i t h m d e s i g n e d t o r educe s w a p p i n g . T h e y c l a i m i t is d e s i r a b l e t o i n c o r p o r a t e i n t o t h e s c h e d u l e r a s p e c i f i c a t i o n o f a m i n i m u m leve l o f a c c e p t a b l e se rv i ce f o r e a c h c lass o f p r o g r a m . S c h e d u l i n g a n d s w a p p i n g d e c i s i o n s are m a d e w i t h r espec t t o a f a m i l y o f p o l i c y f u n c t i o n s w h i c h spec i f y t h e l eve l o f se rv i ce t o be of fered t o v a r i o u s c lasses o f use rs . T h e y a lso s u g -gest t h a t u n d e r h e a v y l o a d b o t h t h e m i n i m u m m e m o r y res idence t i m e (MINTIMEIN) a n d the m i n i m u m t i m e s p e n t o u t o n d i s k (MINTIMEOUT) be i n c r ea sed b y a q u a n t i t y t h e y Chapter Three: The Model Page 15 t e r m t h e hy s t e r e s i s . H y s t e r e s i s c o u l d a lso be a d j u s t e d a c c o r d i n g t o t h e s ize o f a p rocess . In [20], K l e i n r o c k so l ves a q u e u e i n g m o d e l t o c a l c u l a t e t h e e x p e c t e d s w a p t i m e e x p e n d e d o n a l l c u s t o m e r s i n a s y s t e m o f queues . B o t h t i m e - s h a r e d s y s t e m s a n d p roces so r-sha red s y s t e m s are c o n s i d e r e d . P r o c e s s o r - s h a r e d s y s t e m s are t i m e - s h a r i n g s y s -t e m s i n w h i c h t h e q u a n t u m s ize is a l l o w e d t o a p p r o a c h zero . In o r d e r t o a p p l y t h e r e s u l t s , t h e e x p e c t e d w a i t i n queues c o n d i t i o n e d o n a se rv i ce r e q u i r e m e n t m u s t be k n o w n fo r t i m e - s h a r e d s y s t e m s w h i c h a c c o u n t f o r s w a p t i m e . N i e l s e n [26] s t u d i e s t h e ef fect iveness o f p r o g r a m r e l o c a t i o n , r o t a t i o n a l d e l a y m i n i m i -z a t i o n , a n d s w a p v o l u m e m i n i m i z a t i o n t e c h n i q u e s . N i e l s e n uses a set o f p r o t o t y p e s i n h is s i m u l a t i o n s w i t h e a c h j o b t y p e b a s e d o n seven d i s t r i b u t i o n s r e f l e c t i n g a j o b ' s r esource needs . T h e e f fec t i veness o f f a s t e r s w a p p i n g dev i ces is s h o w n t o d e p e n d u p o n t h e o v e r a l l b a l a n c e o f t h e s y s t e m . A s i m p l e m o d e l o f a m u l t i p r o g r a m m i n g s y s t e m is d e v e l o p e d b y T s u j i g a d o [39] a n d t h e C P U id l e t i m e d u e t o s w a p p i n g is a n a l y z e d . T h e r e l a t i o n s h i p b e t w e e n t h e n u m b e r o f c h a n n e l s u s e d f o r s w a p p i n g a n d t h e r a t e o f id le t i m e g e n e r a t e d i n t h e p roces so r is d e r i v e d . S h e m e r a n d H e y i n g [34] a n a l y t i c a l l y m o d e l a s w a p p i n g s y s t e m d e s i g n e d f o r b a t c h a n d t i m e - s h a r i n g users a n d c o m p a r e t h e r e su l t s w i t h e m p i r i c a l m e a s u r e m e n t s . T h e m o d e l p a r a m e t e r s are o b t a i n e d f r o m p e r f o r m a n c e s t a t i s t i c s a n d m e a n v a l u e s . T h e e x p e c t e d r esponse t o " t y p i c a l " i n t e r a c t i v e user d e m a n d s is p r e d i c t e d f r o m t h e n u m b e r o f c o n c u r r e n t use rs . E m p i r i c a l d a t a is u s e d t o s u b s t a n t i a t e t he v a l i d i t y o f t he a s s u m p t i o n s e m p l o y e d i n t h e m o d e l a n d t o d e t e r m i n e a n y c o r r e l a t i o n b e t w e e n m e a s u r e d p e r f o r m a n c e a n d t h e r e su l t s o f t h e m o d e l . A l i m i t i n g r esource m o d e l o f t he E X E C 8 t i m e - s h a r i n g s y s t e m is d e v e l o p e d b y S t r a u s s [35] u n d e r t h e a s s u m p t i o n o f s w a p p i n g s a t u r a t i o n . S w a p p i n g s a t u r a t i o n is t h e Chapter Three: The Model Page 16 i n i t i a t i n g o f one s w a p o p e r a t i o n as s o o n as t h e p r e v i o u s s w a p c o m p l e t e s . T h i s s i m p l e c o n c e p t u a l m o d e l p r e d i c t s t h e s t eady-s t a t e p e r f o r m a n c e f o r b o t h i n t e r a c t i v e a n d b a t c h users as a f u n c t i o n o f c o n f i g u r a t i o n a n d w o r k l o a d . M e a n v a l u e s o b t a i n e d f r o m d i r e c t m e a s u r e m e n t are t h e i n p u t s t o t h e m o d e l . T h e r esu l t s f r o m t h e m o d e l ag r eed w e l l w i t h m e a s u r e d p e r f o r m a n c e v a l u e s o u t s i d e t h e m o d e l ' s r a n g e , a l t h o u g h n o m e a s u r e m e n t s we re a v a i l a b l e t o v e r i f y t h e m o d e l u n d e r s w a p p i n g s a t u r a t i o n . C h e n [6] s t u d i e d a c l o s e d q u e u e i n g n e t w o r k w i t h s t a t e d e p e n d e n t r o u t i n g p r o b a b i l i -t ies f o r s w a p p i n g b a s e d s y s t e m s . T h e m o d e l p r e d i c t s m e a n s y s t e m response t i m e , a n d u t i l i z a t i o n a n d queue l e n g t h o f a n i n d i v i d u a l r e sou rce . T h e p r o b a b i l i t y t h a t a p r o g r a m m u s t be s w a p p e d - i n is e x p r e s s e d as a f a c t o r o f t he s y s t e m s t a t e a n d s y s t e m p a r a m e t e r s . A n a p p r o x i m a t e s o l u t i o n is o b t a i n e d f r o m a n i t e r a t i v e a l g o r i t h m u s i n g B u z e n ' s m e t h o d [3]. T h e r e su l t s o f t h e m o d e l a re c o m p a r e d w i t h b o t h t he c l a ss i ca l m o d e l a n d m e a s u r e -m e n t d a t a . 3.2 Initial Work A n i n i t i a l a t t e m p t a t u n d e r s t a n d i n g s w a p p i n g b e h a v i o u r w a s d i r e c t e d at i n v e s t i g a t -i n g t h e e f f i cacy o f a p e r f o r m a n c e p a r a m e t e r c a l l e d t h e m e a n t i m e b e t w e e n s w a p s ( M T B S ) . W e de f ine t h i s t o be t h e m e a n a m o u n t o f r e a l t i m e w h i c h e lapses b e t w e e n c o m p l e t e s w a p s . T h i s p a r a m e t e r is s u p p o s e d t o be a n a l o g o u s t o t h e m e a n t i m e b e t w e e n page f a u l t s o n a v i r t u a l m e m o r y s y s t e m [ l ] . A p r e d i c t i o n o f M T B S f r o m h a r d w a r e a n d w o r k l o a d p a r a m e t e r s w o u l d a l l ow s w a p p i n g ra tes t o be p r e d i c t e d f o r s i m u l a t i o n p u r -poses. T h e M T B S c o u l d a lso be u s e d b y a q u e u i n g n e t w o r k m o d e l t o o b t a i n e s t i m a t e s o f m e a n t h r o u g h p u t a n d r esponse t i m e . It c o u l d a lso p e r h a p s l e a d t o a l o a d c o n t r o l p o l i c y based o n t h e shape o f t he s w a p l i f e t i m e c u r v e , j u s t as t he p a g i n g l i f e t i m e c u r v e is u sed fo r s u c h p u r p o s e s o n a v i r t u a l m e m o r y s y s t e m [11]. A l t h o u g h s w a p p i n g is a s y s t e m - w i d e Chapter Three: The Model Page 17 a c t i v i t y w h i l e p a g i n g a c t i v i t y is a pe r p rocess c h a r a c t e r i s t i c , i t w a s s p e c u l a t e d t h a t the re are e n o u g h s i m i l a r i t i e s b e t w e e n t h e t w o t e c h n i q u e s t h a t s u c h a n i n v e s t i g a t i o n c o u l d p rove w o r t h w h i l e . A m a j o r d i f f e rence , h o w e v e r , is t h a t w h i l e a h i g h page f a u l t r a t e is n e v e r d e s i r a b l e , i t is n o t c l e a r t h a t a h i g h s w a p p i n g r a t e is u n d e s i r a b l e . A s l o n g as s w a p p i n g does n o t i n t e r f e r e w i t h o t h e r d i s k a c t i v i t i e s a n d t h e C P U id l e t i m e d u e t o s w a p p i n g is n e g l i g i b l e , t h e n s w a p p i n g m i g h t as w e l l be p e r f o r m e d as f r e q u e n t l y as necessa r y . I dea l l y , a p rocess s h o u l d be s w a p p e d - o u t w h e n i t n o l onge r needs t he C P U . A n o t h e r d i f f i c u l t y w i t h t h i s a p p r o a c h is t h a t t h e M T B S seems t o d e p e n d u p o n b o t h t h e t o t a l n u m b e r o f processes a n d t h e process s izes i n a c o m p l i c a t e d m a n n e r . A l t h o u g h s o m e e m p i r i c a l r e su l t s were s t u d i e d , i t d i d n o t a p p e a r t h a t r e s e a r c h a l o n g these l ines s h o u l d be c o n t i n u e d f o r t he r e a -sons n o t e d a b o v e . A s u b s e q u e n t e f for t e n t a i l e d a d e v e l o p m e n t o f a m o d e l w h i c h c o u l d e s t i m a t e t h e r a t i o o f t h r o u g h p u t w i t h s w a p p i n g o v e r h e a d t o t h e t h r o u g h p u t w i t h o u t s w a p p i n g over-h e a d , g i v e n t he r a t i o o f " m e m o r y q u a n t u m " r e q u i r e m e n t t o t h e m e a n one-way s w a p t i m e . T h e m e m o r y q u a n t u m is e q u i v a l e n t t o t he t i m e a p rocess should be l o a d e d i f t h e s y s t e m is n o t s w a p s a t u r a t e d . T h e m o d e l c o u l d also a c c o u n t f o r t he pe r cen t age o f t i m e d u r i n g t h e e x e c u t i o n o f a w o r k l o a d i n w h i c h t h e C P U is i d l e d u e t o s w a p p i n g . It m i g h t be a s s u m e d t h a t a " l a r g e " C P U i d l e t i m e d u e t o s w a p p i n g is u n d e s i r a b l e . T h i s id le t i m e , h o w e v e r , m a y o r m a y n o t be s i g n i f i c a n t , d e p e n d i n g u p o n t h e n a t u r e o f t h e w o r k l o a d . If m o s t processes a re I/O b o u n d , t h e n t h e C P U w i l l h ave a low u t i l i z a t i o n i n a n y case . If t he s y s t e m is e s sen t i a l l y c o m p u t e b o u n d , t h e id le t i m e is s i g n i f i c a n t t o s y s t e m t h r o u g h p u t s ince p r o d u c t i v e w o r k c o u l d p o t e n t i a l l y be p e r f o r m e d d u r i n g t h e s w a p . T h e A one-way swap is a swap-in or a swap-out. Chapter Three: The Model Page 18 d e t e r m i n a t i o n o f t h e m e m o r y q u a n t u m o n a n a c t u a l s y s t e m w a s f o u n d t o be d i f f i c u l t . B e cause o f these p r o b l e m s , t h e m o d e l w a s a b a n d o n e d . 3.3 The Basic Model T h i s s e c t i o n desc r i bes a s i m p l e d e t e r m i n i s t i c m o d e l o f a s w a p p i n g s y s t e m w h i c h is of use w h e n t h e w o r k l o a d f a l l s w i t h i n t h e r ange o f seve ra l w o r k l o a d a n d h a r d w a r e p a r a m e t e r s . T w o e x t r e m e cases w i l l be c o n s i d e r e d : t h e C P U b o u n d case a n d t h e h i g h l y i n t e r a c t i v e , d i s k I/O b o u n d case . T o s i m p l i f y t he m o d e l , w e w i l l a s s u m e t h a t t h e processes h a v e t h e s a m e C P U r e q u i r e m e n t s a n d process s i ze . 3.3.1 Workload and Hardware Parameters A n u m b e r o f w o r k l o a d p a r a m e t e r s w i l l be i n t r o d u c e d t o c h a r a c t e r i z e t h e w o r k l o a d i n q u a n t i t a t i v e t e r m s . S e v e r a l s i g n i f i c a n t h a r d w a r e c h a r a c t e r i s t i c s w i l l a lso be se l ec t ed a n d d e f i n e d . H a r d w a r e P a r a m e t e r s : 1. MM: the amount of main memory available to users in "clicks". Each click is a 64-byte block of primary memory (the minimum allocation size for PDP-11 memory management hardware). The value of MM excludes the size of the resident portions of the operating sys-tem. 2. Tswap: the mean length of time, exclusive of queuing delays, for a one-way swap. Tswap is defined to be the sum of the mean access time and the mean transfer time as a function of the size of the swap. Where an empirical result is available for this value it should, of course, be substituted for the theoretical value. When using a measured result for Tswap, it should be observed that the total number of processes also contributes to Tswap since longer seeks may be required. Chapter Three: The Model Page 19 3. Tbloct the mean time, exclusive of queuing delays, for one file system access (i.e., a 512-byte read or write). Workload Parameters: 4. PN: the number of active processes. A number of relatively idle system programs (/etc/update, /etc/Inlt, /bln/sh, the workload startup process, and the measurement process) will be excluded from this quantity. 5. PS: the swappable process size, in clicks. This value includes the user text and data seg-ments, the stack and the user's system data. 6. NL: the maximum number of simultaneously loaded processes. This is defined to be: 7. PC: the mean CPU requirement between I/O requests (i.e., the uniprogramming duration of a process' CPU burst). This value is not used by the basic model, but is used in the experi-ment to determine how PC influences the validity of the model. 8. Nswaps: the sum of the swap-ins and the swap-outs during a measurement period. 3.3.2 The C P U Bound Case The case when most or all of the workload is C P U bound will be briefly mentioned here. It is assumed that round-robin scheduling is used and that processes are usually swapped-out after receiving their quantum time, Q. To simplify the following discussion, it will be assumed that processes are all of equal size. If the time quantum is also assumed to be at least as large as the time to replace a loaded process with one from secondary storage and that there are always at least two processes loaded (NL > 1), then since all swapping can be overlapped with computation (except for Chapter Three: The Model Page 20 s c h e d u l i n g / s w a p p i n g code o v e r h e a d a n d D M A r e l a t e d m e m o r y c y c l e c o m p e t i t i o n ) , s w a p -p i n g w i l l h a v e v i r t u a l l y no i m p a c t o n p e r f o r m a n c e . ( N o t e t h a t r e sponse t i m e c a n p o s s i -b l y be d e c r e a s e d w i t h o u t d e g r a d i n g t h r o u g h p u t i f Q is r e d u c e d t o 2 * Tswap; i.e., i f t h e t ime-s l i ce is e q u a l t o t he t i m e t o r e a d y a s w a p p e d - o u t p rocess f o r e x e c u t i o n . A s Q decreases b e y o n d t h i s p o i n t , " t h r a s h i n g " w i l l o c c u r because t h e a m o u n t o f p r o d u c t i v e w o r k p e r f o r m e d b e t w e e n s w a p s decreases . ) T w o p r e d i c t i o n s based o n t he r o u n d - r o b i n s c h e d u l i n g a n d e q u a l p rocess s ize a s s u m p t i o n s m a y be m a d e a n d e x p e r i m e n t a l l y v e r i f i e d f o r t w o s y s t e m s , A a n d B, as f o l l o w s : 1. If TA is the runn ing t ime on system A of a fixed amount of work when no swapping is required or when a l l swapping is over lapped w i th computa t ion , then i f PN > 1 and NL=1, the t ime to complete the same amount of work on system B w i l l be TA + Tswap * Nswaps because no over lap is possible. The general case for arb i t rary Tswap, Q, N, and NL under a compute work load w i l l not be discussed here bu t the same reasoning may be appl ied to the general case. O n an actual system, Q wou ld normal ly be much longer than 2 * Tswap. 2. G i v e n PN > 2 compute bound processes of which NLA > 1 are s imultaneously loadable and Tswap < Q I 2, the t ime TA to complete a fixed amount of product ive work should be equal (wi th in error) to the t ime TB to complete the same work when 1 < NLB < NLA. T h i s impl ies tha t as long as there is sufficient memory to al low one process to execute wh i l e another is being swapped, swapping does not signif icantly impact system performance. It should take twice as long to complete double the amount of work (a l inear increase in execu-t ion t ime w i t h increasing PN). A d d i n g ex t ra memory to such a system w i l l not improve performance nor w i l l subst i tu t ing a faster swap device since the C P U is the bott leneck. Chapter Three: The Model Page 21 3.3.3 The Basic Model T h e m o d e l m a k e s seve ra l a s s u m p t i o n s a b o u t t h e c h a r a c t e r i s t i c s o f t h e w o r k l o a d , t h e o p e r a t i n g s y s t e m , a n d t h e h a r d w a r e . T h e w o r k l o a d is a s s u m e d t o be o f a h i g h l y i n t e r a c t i v e n a t u r e , g e n e r a t i n g m a n y file s y s t e m reques ts a n d w i t h r e l a t i v e l y s h o r t C P U d e m a n d s r e l a t i v e t o t he s w a p t i m e . T h e v o l u m e o f t h i s t y p e o f w o r k l o a d is f u r t h e r a s s u m e d t o be su f f i c i en t t o cause t h e s y s t e m t o a p p r o a c h s w a p p i n g s a t u r a t i o n , a l t h o u g h t h i s r e q u i r e m e n t w i l l be r e l a x e d l a t e r . It is a s s u m e d t h a t t h e s h a r e d s w a p p i n g / f i l e s y s -t e m c o n t r o l l e r b e c o m e s t h e l i m i t i n g r esource ( i .e., b o t t l e n e c k ) t o s y s t e m p e r f o r m a n c e . M a n y s i m p l e m o d e l s are b a s e d o n a l i m i t i n g r e sou r ce a s s u m p t i o n o f t h i s t y p e [35]. S u c h m o d e l s are c o n c e p t u a l l y a n d a n a l y t i c a l l y s i m p l e , b u t t h e i r use fu lness d e p e n d s o n t h e v a l i d i t y o f t h e o r i g i n a l r e s o u r c e a s s u m p t i o n . It is a s s u m e d t h a t r o u n d - r o b i n p roces so r s c h e d u l i n g w i l l be e m p l o y e d , t h a t o n l y one s c h e d u l e r i n i t i a t e d s w a p - i n o r s w a p - o u t c a n be q u e u e d a t a n y one t i m e , a n d t h a t s w a p reques ts are s e r v i c e d i n t h e s a m e m a n n e r as o r d i n a r y file s y s t e m reques ts . It is a lso a s s u m e d f o r t h e t i m e b e i n g t h a t a s i ng l e c o n t r o l l e r is s h a r e d b y t h e d i s k dev i ces i n v o l v e d (i.e., s w a p p i n g is n o t o v e r l a p p e d w i t h file s y s t e m t ra f f i c ) . S i n ce t h e d i s k s u b s y s t e m is a s s u m e d t o be t h e m a j o r b o t t l e n e c k , o t h e r p e r i p h e r a l dev i ces a re i g n o r e d b y t h e m o d e l . M a n y s m a l l t o m e d i u m s i z e d U N I X f a c i l i t i e s mee t these a s s u m p t i o n s . T h e h i g h l y i n t e r a c t i v e n a t u r e o f t h e w o r k l o a d (e .g . , e d i t i n g , g r a p h i c s , p l o t t i n g , file m a n i p u l a t i o n , c o m m u n i c a t i o n s , etc . ) a l l ows t he s w a p p i n g s a t u r a t i o n a s s u m p t i o n t o be m e t , because processes w a i t i n g f o r a s l ow ( r e l a t i v e to a d i s k ) dev i c e are u s u a l l y s w a p p e d - o u t . A l s o , g i v e n a s u f f i c i e n t l y l a rge w o r k l o a d o f t h i s t y p e , t h i n k t i m e s m a y be i g n o r e d because t h e n e x t i n t e r a c t i o n is o f t e n r e a d y w h e n the c u r r e n t one finishes. T h e bas i c c o n c e p t b e h i n d t h e m o d e l is t h a t t h e r a t i o o f t h e n u m b e r o f file s y s t e m reques ts ( i .e., u se fu l w o r k ) q u e u e d b e t w e e n s w a p reques ts ( o ve rhead ) , a d j u s t e d f o r I/O Chapter Three: The Model Page 2 2 t i m e s , g i ves a n a p p r o x i m a t i o n o f t he r a t i o o f t i m e s t o c o m p l e t e t h e s a m e a m o u n t o f use-f u l w o r k o r t h e s a m e n u m b e r o f i n t e r a c t i o n s . If m o r e f i le s y s t e m accesses c a n be pe r -f o r m e d b e t w e e n s w a p s t h e n m o r e p r o d u c t i v e w o r k is b e i n g d o n e pe r u n i t t i m e . T h e m o d e l a s sumes t h a t , o n ave rage , e a c h process has one file s y s t e m reques t i n t he d i s k queue . T h e bas i s f o r t h i s a s s u m p t i o n is t h a t w h e n t h e C P U r e q u i r e m e n t o f a process is s h o r t c o m p a r e d t o t h e t i m e t o execu t e a one-way s w a p , a new reques t w i l l be q u e u e d before t h e c u r r e n t s w a p - i n o r s w a p - o u t c o m p l e t e s . S i n ce t he w o r k l o a d is h i g h l y i n t e r a c -t i v e , as s o o n as a s w a p - i n o r s w a p - o u t c o m p l e t e s , a n o t h e r w i l l be q u e u e d . N o t e t h a t as NL dec reases , t h e s w a p p i n g r a t e s h o u l d inc rease u n t i l s w a p s a t u r a t i o n because t h e r e is less file s y s t e m t r a f f i c b e t w e e n s w a p s . T o i l l u s t r a t e a s i m p l e case , s u p p o s e t h a t i n c o n f i g u r a t i o n A t he r e are f o u r l o a d e d processes a n d t h a t i n c o n f i g u r a t i o n B t h e r e are e i gh t l o a d e d processes . A s s u m e t h a t i n e i t h e r c o n f i g u r a t i o n t h e t i m e t o s w a p a n d t h e t i m e t o p e r f o r m a file s y s t e m reques t are r e s p e c t i v e l y t h e s a m e . T h e n because B p e r f o r m s a b o u t t w i c e as m u c h use fu l w o r k b e t w e e n s w a p s as A, B w i l l t a k e less t i m e t o p e r f o r m t h e s a m e a m o u n t o f w o r k . T h e a n a l y t i c m o d e l i s : Rati = I± = N L a * N L b * T b l o c k B + N L a * T 8 w a P B ( s n a l°BA ~ TA~ NLA * NLB * TblockA + NLB * TswapA  1 ' ' whe re T is t he t i m e t o c o m p l e t e t h e w o r k l o a d . T h e m o d e l p r e d i c t s t h e t o t a l t i m e t o a c c o m p l i s h a g i v e n a m o u n t o f w o r k , once a m e a s u r e m e n t o f t h e s a m e t y p e o f w o r k l o a d u n d e r ( p o s s i b l y ) d i f f e ren t c o n d i t i o n s is k n o w n (PN is t h e s a m e i n b o t h cases) . F r o m t h i s v a l u e , t h e m e a n s y s t e m t h r o u g h p u t c a n be d e t e r m i n e d (X = C / T) a n d t h e m e a n r e sponse t i m e is R= T / C - Z [10], whe re C is Chapter Three: The Model Page 23 t h e n u m b e r o f c o m p l e t e d " i n t e r a c t i o n s " a n d Z is t h e m e a n t h i n k t i m e . F o r t he i n t e r a c -t i v e use r , r e sponse t i m e is u s u a l l y o f p r i m a r y c o n c e r n . H e l l e r m a n [17] sugges ts t h a t a b e t t e r p e r f o r m a n c e i n d i c a t o r t h a n r esponse t i m e is a s t a t i s t i c o n t h e r e sponse r e l a t i v e t o t he se rv i ce t i m e r e q u i r e d f o r t h e reques t ( s o m e t i m e s c a l l e d t h e " s t r e t c h f a c t o r " o r " d i l a -t i o n " ) . T h i s is d e f i n e d as t h e r a t i o o f r e sponse t o se rv i ce t i m e , o r i t s r e c i p r o c a l . T h e o u t p u t o f t he m o d e l , t h e r e l a t i v e c h a n g e i n e x e c u t i o n t i m e (per w o r k l o a d ) , is a n a l o g o u s t o t h e d i l a t i o n s t a t i s t i c (per p rocess ) . It is a s s u m e d t h a t d e c r e a s i n g t h e t i m e t o p e r f o r m a file s y s t e m access w i l l h a v e n o s i g n i f i c a n t effect o n t h e m e a n queue l e n g t h ; t h e d i s k c o n t r o l l e r w i l l s t i l l be t h e b o t t l e n e c k . N o t e t h a t t h e u t i l i z a t i o n o f t h e c o n t r o l l e r m u s t be h i g h (g rea te r t h a n a b o u t 8 0 p e r c e n t ) o n b o t h o f t h e s y s t e m s used i n E q u a t i o n 3.1. T h e p r i m a r y a d v a n t a g e s o f t h i s m o d e l o v e r p r e v i o u s m o d e l s are i t s s i m p l i c i t y a n d d e t e r m i n i s t i c n a t u r e . C h e n ' s m o d e l [6], f o r e x a m p l e , r equ i r es t h e m e a n n u m b e r o f d i s k I/O reques t s pe r i n t e r a c t i o n t o e s t i m a t e r o u t i n g f r equenc i es . T h e p r o b a b i l i t y o f a p r o -cess b e i n g s w a p p e d - i n o r s w a p p e d - o u t m u s t a lso be e s t i m a t e d . O t h e r m o d e l i n g w o r k is p r i m a r i l y c o n c e r n e d w i t h t h e b a l a n c i n g o f i n t e r a c t i v e l o a d a n d b a t c h l o a d t o i m p r o v e s y s t e m u t i l i z a t i o n . B e c a u s e t h e m o d e l d e v e l o p e d i n t h i s c h a p t e r is d e t e r m i n i s t i c , n e i t h e r p r o b a b i l i t i e s n o r a s e p a r a t e q u e u e i n g n e t w o r k s o l u t i o n s t ep is r e q u i r e d . T h e r e is a lso no need f o r a n y o f t h e a s s u m p t i o n s used i n t h e t h e o r y o f s t o c h a s t i c processes . T h e c o n c e p t s b e h i n d t he m o d e l are easy t o u n d e r s t a n d a n d t h e m o d e l is s i m p l e t o e v a l u a t e . S i n c e t h e m o d e l is b a s e d o n o p e r a t i o n a l q u a n t i t i e s , i t s a s s u m p t i o n s c a n be t e s t e d a n d v e r i f i e d . A w e a k n e s s o f t he m o d e l is t h a t i t re l ies u p o n t h e a s s u m p t i o n s o f d i s k s a t u r a t i o n a n d h i g h l y i n t e r a c t i v e w o r k l o a d . Chapter Four: The Experiment Page 24 4. T h e Exper iment 4.1 Overview In t h i s c h a p t e r , t h e e x p e r i m e n t c o n d u c t e d w i l l be d e s c r i b e d i n d e t a i l . H a v i n g d e c i d e d t o p e r f o r m a n e x p e r i m e n t t o e v a l u a t e t h e m o d e l , t h e first s t ep is t o d e s i g n t h e p a r a m e t e r s f o r a s y n t h e t i c w o r k l o a d a n d v a l i d a t e t h e w o r k l o a d . T o o l s are t h e n d e v e l o p e d t o m e a s u r e , e x t r a c t , a n d process t he s y s t e m d a t a . T h e d e s c r i p t i o n o f b o t h t h e s y s t e m m o d i f i c a t i o n s a n d t he m e a s u r e m e n t p r o g r a m are i n c l u d e d i n t h i s s e c t i o n . T h e d e s i g n a n d i m p l e m e n t a t i o n o f t h e e x p e r i m e n t are d i s c u s s e d . T h e o b j e c t i v e o f a n y e x p e r i m e n t a l i n v e s t i g a t i o n is t o l e a r n m o r e a b o u t t h e s y s t e m b e i n g i n v e s t i g a t e d ; i.e., to s t u d y t he effect o f v a r i a t i o n o f c e r t a i n f a c t o r s o r t h e r e l a t i o n b e t w e e n c e r t a i n f a c t o r s i n a s y s t e m . T h e m a j o r d i f f i c u l t y i n e v a l u a t i n g c o m p u t e r p e r f o r -m a n c e is t h e l a rge n u m b e r o f f a c t o r s i n t h e p r o b l e m u n d e r i n v e s t i g a t i o n . E x t r a n e o u s f a c t o r s w h i c h c a n n o t c o m p l e t e l y be c o n t r o l l e d i n f l u e n c e t h e o u t c o m e o f t h e e v a l u a t i o n . T h e u t i l i t y o f a n e x p e r i m e n t a l d e s i g n is t o e l i m i n a t e these f a c t o r s i f pos s i b l e , o r t o m i n i m i z e t h e i r effects b y a r r a n g i n g t h e e x p e r i m e n t so t h a t t h e effects m a y be e x p e c t e d t o c a n c e l a n d p a r t i a l l y c a n c e l e a c h o t h e r i n t h e a n a l y s i s o f t h e r e s u l t i n g e m p i r i c a l d a t a . E x p e r i m e n t a t i o n is a n i t e r a t i v e p rocess . A n i n i t i a l c o n j e c t u r e leads t o a d e s i g n , t h e d e s i g n l eads t o t h e e x p e r i m e n t , a n d t h e e x p e r i m e n t p r o v i d e s d a t a t h a t are a n a l y s e d be fo re f o r m i n g a new c o n j e c t u r e . 4.2 Synthetic W o r k l o a d and M o d e l Parameters W h e n m e a s u r i n g t h e p e r f o r m a n c e o f a s y s t e m , e i t h e r t he p r o d u c t i o n w o r k l o a d o r a n a r t i f i c i a l w o r k l o a d c a n be used t o d r i v e t h e s y s t e m . T h e p r o d u c t i o n w o r k l o a d , o r a seg -m e n t o f i t , has t he a d v a n t a g e o f b e i n g m o r e r e p r e s e n t a t i v e . B e cause , h o w e v e r , t h e Chapter Four: The Experiment Page 25 w o r k l o a d va r i e s w i t h t he t i m e o f d a y , t h e d a y o f the week , e tc . , t he q u e s t i o n o f a p a r t i c -u l a r m e a s u r e m e n t ' s r e p r e s e n t a t i v e n e s s m a y ar i se . A r t i f i c i a l w o r k l o a d s offer r e p r o d u c i b i l -i t y , flexibility, a n d are p o t e n t i a l l y m o r e c o m p a c t . T h e y are , h o w e v e r , m o r e expens i ve t o c o n s t r u c t , less r e p r e s e n t a t i v e , a n d r equ i r e a d e d i c a t e d s y s t e m t o r u n o n . In t h i s w o r k , t h e p r o d u c t i o n w o r k l o a d w a s n o t s u i t a b l e f o r d i r e c t m e a s u r e m e n t a l t h o u g h m o n t h l y c o m m a n d f r e q u e n c y d a t a sugges t ed t h e m o r e p o p u l a r c o m m a n d s . F o r t h e p u r p o s e s o f t h i s t hes i s , t h e s y n t h e t i c w o r k l o a d is t h e m o s t des i r ab l e cho i ce because a c o n t r o l l e d e n v i r o n m e n t is n e e d e d t o m a k e c o m p a r i s o n s b e t w e e n d i f f e r en t c o n f i g u r a t i o n s w i t h t h e s a m e w o r k l o a d . T h e c h a n g e s i n p e r f o r m a n c e w i t h c h a n g i n g w o r k l o a d c h a r a c -t e r i s t i c s are a l so o f g rea t i n t e r e s t . A p r o t o t y p e p r o g r a m w h i c h b e c a m e t h e bas is o f t h e s y n t h e t i c w o r k l o a d w a s t h e r e f o r e c o n s t r u c t e d . 4.2.1 Construction of the Prototype Process A p r o t o t y p e p rocess c o n s i s t s o f 200 " i n t e r a c t i o n s " , e a c h m a d e u p o f t h e f o l l o w i n g : 1. A Compute Loop - the duration of this computation is a command line argument to the pro-cess when it is invoked. 2. Disk I/O Operations - a number of reads, writes, and seeks are usually performed, although on occasion no operation will be performed. Note that because of the buffering strategy, physical I/O may be delayed or may not be required. 3. Pause - to simulate think time, the process is put into a low priority wait for a short time. This would normally cause the process to be swapped-out. This was implemented by setting an alarm clock signal and then issuing a read request which could not be satisfied. Chapter Four: The Experiment Page 26 4. T e r m i n a l O u t p u t - several 25-character-Iong strings are pr inted. The first character of the s t r ing identif ies the wr i t i ng process. A n interact ive work load usual ly involves a great deal of te rmina l input and output . Because te rmina l input is di f f icult to s imulate in a synthet ic work load , te rmina l output was used to cause add i t iona l process suspensions. When the ter-m ina l output buffer fills, the process is suspended at a pr ior i ty s l ight ly lower than the input pr ior i ty un t i l the characters have been sent to the te rmina l . 5. Process Size - there is a d u m m y array in the prototype process which can be stat ica l ly var ied to alter the size of the process. The process size includes the stack and system da ta segments. T h e a m o u n t o f c o m p u t a t i o n , d i s k I/O, a n d t e r m i n a l o u t p u t , as w e l l as t he d u r a t i o n o f t h e p a u s e are a l l d i s t r i b u t i o n d r i v e n . T h i s a d d s v a r i a b i l i t y t o t h e w o r k l o a d w h i l e k e e p i n g averages c o n s t a n t . In a d d i t i o n , t h e seed f o r t h e r a n d o m n u m b e r g e n e r a t o r a n d the file u s e d f o r I/O we re d i f f e ren t f o r e a c h p rocess . T o c rea te t h e s y n t h e t i c w o r k l o a d , t he p r o t o t y p e process w a s d u p l i c a t e d o n a non-sha rab l e bas i s t o g i ve t h e d e s i r e d n u m b e r o f processes . 4.3 Description of the Measurement Tools In o r d e r t o e x t r a c t d a t a o n t h e o p e r a t i o n o f a c o m p u t e r s y s t e m o v e r a p e r i o d o f t i m e , m e a s u r e m e n t m o n i t o r s are used t o r e c o r d t he va l ues o f c e r t a i n v a r i a b l e s c o n s i d e r e d t o be s i g n i f i c a n t f o r e v a l u a t i n g s y s t e m o p e r a t i o n . R o s e [32] d i scusses m e a s u r e m e n t p r o -cedures i n d e t a i l . M o n i t o r s use e i t h e r a n e v e n t t r a c e p o l i c y o r a s a m p l i n g p o l i c y a n d are i m p l e m e n t e d u s i n g h a r d w a r e , s o f t w a r e , o r b o t h . E v e n t t r a c e m o n i t o r s r e c o r d i n f o r m a -t i o n w h e n a p a r t i c u l a r e ven t o c c u r s w h i l e s a m p l i n g m o n i t o r s r e c o r d i n f o r m a t i o n at Chapter Four: The Experiment Page 27 spec i f i ed t i m e i n t e r v a l s . T h e e ven t t r a ce p o l i c y u s u a l l y o b t a i n s m o r e d e t a i l e d i n f o r m a -t i o n o v e r a s h o r t e r p e r i o d o f t i m e . D a t a a re w r i t t e n t o d i s k o r t a p e f o r s u b s e q u e n t use b y d a t a r e d u c t i o n s o f t w a r e . L a r g e a m o u n t s o f d a t a are o f t e n c o l l e c t e d i n t h e cou rse o f a m e a s u r e m e n t sess ion a n d i t is i m p o r t a n t t o i n s u r e t h a t t h e c o l l e c t i o n process does n o t i n t e r f e r e s i g n i f i c a n t l y w i t h t h e s y s t e m b e i n g o b s e r v e d . T h e s a m p l i n g p o l i c y i n i t i a t e s d a t a c o l l e c t i o n a c t i v i t i e s w h e n a r ea l - t ime c l o c k s i gna l s t h e e n d o f a n i n t e r v a l . T h e i n t e r v a l , o r t i m e b e t w e e n success i ve s a m p l i n g e v e n t s , is u s u a l l y c o n s t a n t . A less d e t a i l e d d e s c r i p t i o n o f t h e s y s t e m is o b t a i n e d o v e r a l onge r p e r i o d o f t i m e u s i n g s a m p l i n g . T h e r e a re t h r ee b a s i c i m p l e m e n t a t i o n s o f m e a s u r e m e n t m o n i t o r s , e a c h o f w h i c h m a y use e i t h e r e v e n t t r a c e o r s a m p l i n g po l i c i e s . H a r d w a r e m o n i t o r s are dev i ces a t t a c h e d t o t h e c o m p u t e r ' s c i r c u i t r y a t v a r i o u s p o i n t s t o e x a m i n e s t a t u s e s o r c o u n t e ven t s . T h e s e m o n i t o r s h a v e t h e a d v a n t a g e s o f p e r m i t t i n g h i g h e v e n t r a t es , m a k i n g p rec i se m e a s u r e -m e n t s , a n d n o t i n t e r f e r i n g w i t h t h e s y s t e m b e i n g m e a s u r e d . T h e y c a n n o t , h o w e v e r , r e vea l t h e causes b e h i n d even t s a n d t h e y l a c k s e l e c t i v i t y o f m e a s u r e m e n t . S o f t w a r e m o n i t o r s are m e a s u r e m e n t r o u t i n e s i n s e r t e d i n t o t h e s y s t e m s o f t w a r e t o r e c o r d e ven t s a n d s t a t u s e s . T h e y c a n g e n e r a l l y r e c o r d a n y i n f o r m a t i o n a v a i l a b l e t o t h e o p e r a t i n g s y s -t e m a n d offer a g r e a t d e a l o f f l e x i b i l i t y i n t h e s e l e c t i o n o f t h e m e a s u r e m e n t d a t a . B e c a u s e t h e y r equ i r e r e sou r ces , t h e y m a y i n t e r f e r e w i t h t h e s y s t e m o p e r a t i o n w h i c h is t o be m e a s u r e d . I f a s a m p l i n g p o l i c y is u s e d , t h e s a m p l i n g f r e q u e n c y has t o be l a rge e n o u g h t o p r o v i d e s t a t i s t i c a l l y g o o d r e su l t s , b u t m u s t n o t u n d u l y i n f l u e n c e t h e m e a s u r e -m e n t s . T h e h y b r i d i m p l e m e n t a t i o n c o m b i n e s h a r d w a r e a n d s o f t w a r e b u t has t he d i s a d -v a n t a g e o f r e q u i r i n g t h e m o n i t o r s o f t w a r e t o be ab l e t o c o m m u n i c a t e w i t h t h e e x t e r n a l h a r d w a r e m o n i t o r . A n u m b e r o f changes we r e m a d e t o t h e o p e r a t i n g s y s t e m t o c o n d u c t t h e e x p e r i -m e n t . W h e n t h e e x p e r i m e n t a l v e r s i o n o f U N I X is b o o t e d , i t a l l o w s t h e user t o spec i f y Chapter Four: The Experiment Page 28 t h e a m o u n t o f f ree user m e m o r y t o be m a d e a v a i l a b l e . T h i s a l l ows t h e p a r a m e t e r NL t o be c o n t r o l l e d b y a d j u s t i n g MM. T h e pause a n d alarm [18] s y s t e m ca l l s h a d p r e v i o u s l y been a d d e d t o t h e s y s t e m as w e l l as t h e V e r s i o n S e v e n sleep s u b r o u t i n e w h i c h uses these s y s t e m c a l l s . T h e user-process (/etc/update) w h i c h flushes t h e bu f fe r s y s t e m uses these new ca l l s t o a v o i d t h e ine f f i c i enc ies d e t a i l e d ea r l i e r c a u s e d b y t h e o r i g i n a l sleep s y s t e m c a l l . A m e a s u r e m e n t p r o g r a m c a l l e d iostat w a s w r i t t e n w h i c h is s i m i l a r t o t h e S e v e n t h E d i t i o n p r o g r a m o f t h e s a m e n a m e [18]. C o d e w a s a d d e d t o t h e k e r n e l w h i c h c o m b i n e d a n e v e n t t r a ce p o l i c y w i t h a s a m p l i n g p o l i c y . A l s o , /etc/update w a s m a d e i n t o a p u r e t e x t p r o g r a m so t h a t i t w o u l d n e v e r be s w a p p e d - o u t . T h e k e r n e l w a s m o d i f i e d t o s a m p l e s y s t e m s t a t e s a t e a c h c l o c k i n t e r r u p t (60 H z ) as we j l as t o r e c o r d v a r i o u s t r a n s a c t i o n s . T h e c l o c k i n t e r r u p t h a n d l e r w a s m o d i f i e d t o r e c o r d t h e s t a t u s o f e i t h e r d i s k d r i v e ( b u s y o r n o t b u s y ) a n d t h e s t a t e o f t h e C P U ( b u s y use r-mode , b u s y s y s t e m - m o d e , o r id le ) e a c h t i m e i t w a s c a l l e d . T h e d i s t r i b u t i o n o f d i s k c o n t r o l l e r q u e u e l e n g t h s w a s a l so m a i n -t a i n e d . W i t h i n t h e s e c t i o n o f t h e s y s t e m used t o m a n a g e t he b l o c k I/O buf fe rs , code w a s a d d e d t o c o u n t t h e n u m b e r o f c a che h i t s , t he n u m b e r o f r e a d s , r ead-aheads , a n d w r i t e s . T h e r o u t i n e t o set u p a s w a p w a s c h a n g e d t o c o u n t t he n u m b e r o f s w a p s a n d t h e n u m b e r o f co re c l i c k s w h i c h we re s w a p p e d . T h e d i s k d r i v e r w a s m o d i f i e d t o c o u n t t h e n u m b e r o f r eques t s d i r e c t e d t o e a c h d r i v e a n d t h e n u m b e r o f w o r d s t r a n s f e r r e d b y e a c h d r i v e . It was a l so r e s p o n s i b l e f o r m a r k i n g t he s t a t u s o f e i t h e r d r i v e f o r t h e p u r p o s e o f s a m p l i n g b y t h e c l o c k d r i v e r . T h e t o t a l n u m b e r o f seeks f o r e i t h e r d r i v e w a s m a i n -t a i n e d . T h e t e r m i n a l d r i v e r r e c o r d e d t h e n u m b e r o f c h a r a c t e r s r e a d a n d t h e n u m b e r p r i n t e d . A l l t h e d a t a were s t o r e d i n a c o n t i g u o u s d a t a s t r u c t u r e so t h a t t h e iostat user-process c o u l d access t h e m e a s i l y . T h i s p a r t i c u l a r i m p l e m e n t a t i o n o f p e r f o r m i n g m e a s u r e m e n t s w a s c h o s e n because o f i ts s i m p l i c i t y a n d because o f c o n s t r a i n t s i m p o s e d b y t he s y s t e m h a r d w a r e (o r l a c k Chapter Four: The Experiment Page 20 t he r eo f ) . M e a s u r e m e n t code c o u l d have been d e s i g n e d t o w r i t e d a t a t o s e c o n d a r y s t o r age , f o r e x a m p l e . T h i s w o u l d a l l ow m u c h m o r e d e t a i l e d i n f o r m a t i o n t o be e x t r a c t e d a n d s t u d i e d . S i n c e n e i t h e r a t a p e d r i v e n o r a n a d d i t i o n a l d i s k u n i t w a s a v a i l a b l e , s i m p l e o p e r a t i o n a l d a t a w o u l d h a v e t o suf f i ce . T h e i n t e r f e r ence t o t he s y s t e m c a u s e d b y w r i t i n g d a t a t o t he d i s k dev i ces b e i n g o b s e r v e d w a s d e e m e d t o be t o o l a rge . It w o u l d a l so inc rease c o m p l e x i t y a n d i n t r o d u c e a n o t h e r p o t e n t i a l sou r ce o f e r r o r . S o m e o f t h e q u a n t i t i e s r e c o r d e d are necessa r y t o d e r i v e p a r a m e t e r s f o r t he m o d e l ; o t h e r s ( s u c h as s y s t e m s t a t e d i s t r i b u t i o n ) we r e t h o u g h t t o be u s e f u l f o r t h e i n s i g h t s t h e y m i g h t g i ve i n t o t h e e x p e r i m e n t a l r e su l t s a n d fo r poss ib l e f u t u r e r e s e a r c h . T h e o u t p u t o f iostat c ons i s t s o f t h e n u m b e r o f d i s k r e a d s , r ead-aheads , cache h i t s , d i s k w r i t e s , t h e m e a n queue l e n g t h , a n d t h e d i s k queue l e n g t h d i s t r i b u t i o n . T h e t o t a l n u m b e r o f reques ts t o each d i s k a n d t h e t o t a l a m o u n t t r a n s f e r r e d t o a n d f r o m e a c h d i s k are p r i n t e d . T h e m e a n access t i m e , t h e m e a n t r a n s f e r t i m e , a n d t he m e a n n u m b e r o f b y t e s pe r r eques t are c a l c u l a t e d f r o m m e a s u r e m e n t d a t a a n d f r o m t h e m a n u f a c t u r e r ' s dev i c e s p e c i f i c a t i o n s . D i s k u t i l i z a t i o n a n d t h e t i m e t h e C P U s p e n d s w a i t i n g fo r I/O t o c o m p l e t e are p r i n t e d as w e l l as a s y s t em-s t a t e /d i sk-d r i v e-s t a t e m a t r i x . T h e use r m a y select v a r i o u s subse t s o f t h i s i n f o r m a t i o n . W h e n iostat is i n v o k e d , i t s i m p l y r eads t h e m e a s u r e m e n t d a t a f r o m k e r n e l space a n d no tes t h e c u r r e n t t i m e o f d a y . It t h e n s u s p e n d s i t se l f f o r a g i v e n a m o u n t o f t i m e u s i n g t h e sleep s u b r o u t i n e . W h e n i t a w a k e n s , i t c a l c u l a t e s t h e e l apsed t i m e , r e ads t h e d a t a a g a i n , a n d d i s p l a y s p e r f o r m a n c e p a r a m e t e r s b a s e d o n t h e d i f fe rence b e t w e e n t h e t w o sets o f d a t a a n d t h e r ea l t i m e w h i c h e l a p s e d b e t w e e n t h e r e a d i n g s . If iostat is i n t e r r u p t e d be fore t h e g i v e n t i m e p e r i o d exp i r e s , i t ignores t h e o r i g i n a l t i m e p e r i o d a n d uses t h e e l apsed t i m e t o t h e i n t e r r u p t . S i n ce t h e pause p u t s t h e process i n a low p r i o r i t y w a i t , iostat w i l l be s w a p p e d - o u t d u r i n g t h e m e a s u r e m e n t sess ion a n d t he r e fo r e w i l l n o t Chapter Foun The Experiment Page 30 i n t e r f e r e w i t h i t . T h e m e a s u r e m e n t s w i t h i n t h e k e r n e l cons i s t o f s i m p l e i n c r e m e n t s a n d a s s i g n m e n t s a n d w o u l d c o n t r i b u t e l i t t l e t o t he s y s t e m o v e r h e a d . T h e n o r m a l s y s t e m c l o c k is a c c u r a t e t o t h e neares t one s i x t i e t h o f a s e c o n d . A m o r e a c c u r a t e c l o c k is a v a i l a b l e w i t h i n t h e DUP11 s y n c h r o n o u s l i ne i n t e r f a c e . T h e m a i n t e n a n c e c l o c k i n t h i s i n t e r f a c e has a r e s o l u t i o n o f b e t w e e n one a n d t w o m i l l i s e c o n d s . A d e v i c e d r i v e r a n d a s y s t e m c a l l we r e a d d e d t o t h e k e r n e l i n a p r e l i m i n a r y e x p e r i m e n t t o a l l o w t h e m a i n t e n a n c e c l o c k t o be u s e d as a s t o p w a t c h . T h e c l o c k w a s c a l i b r a t e d u s i n g t h e s y s t e m c l o c k a n d t h e n t h e m a i n t e n a n c e c l o c k w a s u s e d t o d e v e l o p d i s t r i b u t i o n s f o r t h e v a r i o u s PC i n t e r v a l s . T h e code w a s o r i g i n a l l y w r i t t e n t o m a k e m o r e prec ise m e a s u r e m e n t s a n d t o pass d a t a b a c k t o a user-process . A m e c h a n i s m w a s d e v e l o p e d w h e r e b y p a r t o f m a i n m e m o r y c o u l d be r e se r v ed f o r c o l l e c t i o n o f d a t a . T h i s i m p l e -m e n t e d a s i m p l e , l ow i n t e r f e r ence t r a c e f a c i l i t y . 4.4 Design of the Experiment T h e w o r k l o a d a n d h a r d w a r e p a r a m e t e r s t h a t t h e bas i c m o d e l r equ i r es we re o u t l i n e d i n S e c t i o n 3.3.1. W h e n the r e are i n t e r a c t i o n s a m o n g t h e p a r a m e t e r s , i t is necessa r y t o use a f a c t o r i a l d e s i g n f o r t h e e x p e r i m e n t . In a f a c t o r i a l d e s i g n a l l v a l ues o f each p a r a m e -t e r m u s t be v a r i e d w i t h a l l v a l u e s o f t h e o t h e r p a r a m e t e r s . T h e m o d e l p a r a m e t e r s b e c o m e t h e f a c t o r s o f t h e e x p e r i m e n t ; i.e., t hose q u a n t i t i e s w h i c h a re e x p l i c i t l y v a r i e d . T h e d i f f e ren t v a l ues o f a f a c t o r w h i c h are used are t e r m e d t h e leve ls o f a f a c t o r . T h e in f l uences w h i c h are n o t o f i n t e r e s t a n d w h i c h m u s t be h e l d c o n s t a n t d u r i n g t he e x p e r i -m e n t are c a l l e d s e c o n d a r y f a c t o r s . T h i s s e c t i o n desc r ibes t h e leve ls c h o s e n f o r t h e f a c -t o r s a n d t h e r e a s o n i n g b e h i n d t h e i r c h o i c e . A c o m p l e t e f a c t o r i a l e x p e r i m e n t w a s f o l -l o w e d f o r t h e m a i n l eve l s , w h i l e s eve ra l i n d i v i d u a l e x p e r i m e n t s we re r u n w i t h d i f f e ren t leve ls i n o r d e r t o p r o b e f o r t h e p o i n t s w h e r e t he m o d e l b r e a k s d o w n . A l s o , s o m e c o m b i -Chapter Four: The Experiment Page 31 n a t i o n s o f l e v e l s / f a c t o r s we re n o t o f i n t e r e s t because n o s w a p p i n g w o u l d o c c u r ( i .e. , PN < NL). T h e f a c t o r s a n d leve ls are s u m m a r i z e d i n T a b l e II. Experimental Factors and Levels Factor Levels  MM 650, 1000, 1280 (clicks) PN 4, 5, 6, 8, 10, 12 (processes) PS 157, 314 (clicks) PC 12 (msec.) Table II S ince t h e n a t u r a l w o r k l o a d w a s n o t s u i t a b l e f o r t h e e x p e r i m e n t ' s w o r k l o a d o r f o r d e t e r m i n i n g r e a s o n a b l e leve ls f o r t h e f a c t o r s , r e su l t s f r o m a p r e v i o u s e x p e r i m e n t h e l p e d t o p r o v i d e s o m e r e a l i s t i c v a l u e s . D o w n i n g [13] m e a s u r e d t he p r o d u c t i o n w o r k l o a d o n a s i m i l a r l y c o n f i g u r e d U N I X s y s t e m . T h i s w o r k l o a d w a s h i g h l y i n t e r a c t i v e . T h e m e a n n u m b e r o f processes , t h e process s ize d i s t r i b u t i o n , a n d t h e d i s t r i b u t i o n o f u n i n t e r r u p t e d C P U i n t e r v a l s we r e d e t e r m i n e d . It w a s f o u n d t h a t o n a b u s y s y s t e m t h e r e we r e u s u a l l y a b o u t 2 r e a d y processes a n d f r o m 12 t o 14 b l o c k e d (i .e., w a i t i n g ) p rocesses . M o s t processes we r e s m a l l e r t h a n 200 c l i c k s (6K w o r d s ) w i t h u p t o 5 p e r c e n t o v e r 500 c l i c k s i n s ize . T h e m e a n u n i n t e r r u p t e d C P U i n t e r v a l o f t h a t p r o d u c t i o n w o r k l o a d w a s f o u n d t o be 12 m s e c . A l t h o u g h t h e PC findings we r e f r o m a d i f f e r e n t l y c o n f i g u r e d s y s t e m , t h e s a m e leve ls we re used i n t h i s w o r k s ince t h e y were f o u n d t o be less t h a n , c lose t o , a n d g rea t e r t h a n t h e one-way s w a p serv i ce t i m e s u s e d . T h e l eve l o f 12 msec , f o r t h e PC f a c t o r i n t he f a c t o r i a l e x p e r i m e n t w a s c h o s e n . S e v e r a l s u p p l e m e n t a r y r u n s w e r e m a d e w i t h l a rge r PC v a l u e s t o d e t e r m i n e w h e n t h e C P U d e m a n d s b e g i n t o v i o l a t e t h e m o d e l ' s w o r k l o a d a s s u m p t i o n s . T h e u n i n t e r r u p t e d Chapter Four: The Experiment Page 32 C P U r e q u i r e m e n t s we re i m p l e m e n t e d b y c a l l i n g a f u n c t i o n h a v i n g a fixed d e l a y seve ra l t i m e s b a s e d o n a d i s t r i b u t i o n . A l l PC d i s t r i b u t i o n s u s e d i n t he e x p e r i m e n t a re g i v e n i n T a b l e III. Distribution of Compute Loops (Percent of Occurrences) Number of Iterations PC (msec.) 5 20 200 5000 12 3 36 100 100 30 1 19 97 100 60 1 5 90 100 186 1 5 57 100 354 1 5 15 100 Tab le III T h e m a x i m u m leve l f o r m a i n m e m o r y is l i m i t e d b y t he m a x i m u m a m o u n t o f free m e m o r y a v a i l a b l e o n t h e s y s t e m . T h e l o w e r l eve l is based o n p r o v i d i n g j u s t e n o u g h m e m o r y so t h a t t w o o f t h e l a rge r processes c o u l d be s i m u l t a n e o u s l y l o a d e d . S e ve r a l r u n s were m a d e w i t h a process s ize o f o v e r 400 c l i c k s so t h a t s w a p t i m e s c o u l d be i n c r e a s e d . T h e d i s t r i b u t i o n f o r t h e d i s k a c t i v i t y w a s a d j u s t e d so t h a t t h e u t i l i z a t i o n o f t h e c o n t r o l l e r e x c e e d e d 90 p e r c e n t w h e n t he m a x i m u m leve l o f PN was u s e d . It c o u l d be a r g u e d t h a t t h e a m o u n t o f file s y s t e m t ra f f i c g e n e r a t e d ( a b o u t 6 b l o c k s r e a d / w r i t t e n p e r i n t e r a c t i o n ) w a s p e r h a p s g r e a t e r t h a n t h a t w h i c h w o u l d be e x p e c t e d f r o m a t y p i c a l i n t e r a c t i v e p roces s . F o r e x a m p l e , n o t h i n k t i m e s exceeded 3 s e conds . T h i s sac r i f i ce i n r e p r e s e n t a t i v e n e s s w a s necessa r y because t he r e w a s i n su f f i c i en t m a i n m e m o r y t o c rea te a h i g h u t i l i z a t i o n w h e n t h e l a rge r p rocess s izes we re r u n a n d because i t b e c a m e t o o d i f f i c u l t e x p e r i m e n t a l l y ( a n d t o o l e n g t h y ) t o use a leve l o f m o r e t h a n 12 p rocesses . M a n y C h a p t e r F o u r : T h e E x p e r i m e n t P a g e 33 s i m i l a r i n s t a l l a t i o n s r u n at t he m a x i m u m m a i n m e m o r y c a p a c i t y ( m o r e t h a n t w i c e t h e user m e m o r y a v a i l a b l e o n t h i s s y s t e m ) , n a t u r a l l y c r e a t i n g h i g h c o n t r o l l e r u t i l i z a t i o n . T h e i n t e r n a l s y s t e m p a r a m e t e r s , s u c h as t h e n u m b e r o f bu f fe rs , t h e s c h e d u l i n g c o n -s t a n t s , p r i o r i t i e s , e t c . , we r e h e l d c o n s t a n t t h r o u g h o u t t h e e x p e r i m e n t . T h e s w a p p i n g a n d file s y s t e m accesses we re d i r e c t e d t o sepa ra t e d i s k d r i v e s t o m a k e t h e m e a n t i m e t o p e r f o r m e i t h e r t y p e o f d i s k reques t easy t o d e t e r m i n e . It is c o m -m o n f o r a U N I X i n s t a l l a t i o n t o ass ign user files t o a d i f f e ren t d r i v e t h a n t h a t u sed fo r s w a p p i n g . It w o u l d n o t v i o l a t e a n y a s s u m p t i o n s m a d e b y t h e m o d e l i f t h i s we re n o t t h e case . A l l t e r m i n a l o u t p u t w a s sent t o t h e s a m e 9 6 0 0 - b a u d C R T t e r m i n a l . I d e a l l y , i t w o u l d be b e t t e r t o c o n t r o l NL a n d Tswap s e p a r a t e l y . T h i s w o u l d a l l o w r u n s t o be m a d e w h e r e a s l owe r d i s k c o u l d be s t u d i e d w i t h t h e s a m e n u m b e r o f l o a d e d processes . B e cause o f t h e i n t r o d u c t i o n o f t h e e x t r a f a c to r s a n d t h e e x t r a c o m p l e x i t y , t h i s e n h a n c e m e n t w a s n o t i m p l e m e n t e d . F u r t h e r con f i dence i n t he m o d e l w o u l d be o b t a i n e d b y c o n d u c t i n g a n a d d i t i o n a l e x p e r i m e n t o n a d i f f e r e n t l y c o n f i g u r e d U N I X s y s t e m . T h e i d e n t i c a l p rocess s ize o f each o f t he p r o t o t y p e s i s , o f cou r se , n o t r e a l i s t i c . T h i s s i m p l i f i c a t i o n m a d e t h e NL p a r a m e t e r easy t o c a l c u l a t e a n d Tswap eas ier t o m e a s u r e , r e d u c i n g t h e c o m p l e x i t y o f t he e x p e r i m e n t . C a l c u l a t i n g NL i n a n a c t u a l s y s t e m i n v o l v e s s c a n n i n g t h r o u g h t h e s y s t e m process t a b l e , w h e r e t he m e a n process s ize c a n a lso be d e t e r m i n e d f o r t h e c a l c u l a t i o n o f Tswap. 4.5 Implementation T h e i m p l e m e n t a t i o n o f t h i s e x p e r i m e n t i n v o l v e d c h a n g i n g t he o p e r a t i n g s y s t e m as d e s c r i b e d i n S e c t i o n 4 .3 , w r i t i n g t h e user-process m e a s u r e m e n t p r o g r a m , a n d c r e a t i n g t h e p r o t o t y p e processes . B e f o r e r u n n i n g t he e x p e r i m e n t , t he l e n g t h o f a sess ion h a d t o be d e t e r m i n e d . It is a s s u m e d t h a t t h e a c c u r a c y of t he v a l u e s g a t h e r e d w i t h i n t he s y s t e m Chapter Four: The Experiment Page 34 are e r g o d i c ; i.e., t h a t t h e a c c u r a c y o f t h e e s t i m a t i o n s increases as t he n u m b e r of o b s e r v a -t i o n s i n t he ser ies i nc reases . A s a m p l e w o r k l o a d was r u n seve ra l t i m e s u n t i l t h e n u m b e r o f i t e r a t i o n s w i t h i n e a c h p r o t o t y p e w a s e n o u g h t o m a k e e l apsed t i m e s f o r e a c h r u n r e a -s o n a b l y c lose . T h e v a l u e o f 200 i t e r a t i o n s p r o v i d e d e x p e r i m e n t a l r u n s n o t excess i ve l y l o n g a n d w i t h d i f fe rences o f less t h a n 5 p e r c e n t i n e l apsed t i m e b e t w e e n i d e n t i c a l w o r k -l o ads . T o r e d u c e t h e p o s s i b i l i t y o f i n t r o d u c i n g e r r o r , t o s i m p l i f y t h e i m p l e m e n t a t i o n , a n d t o m i n i m i z e poss ib l e v a r i a t i o n s i n t h e s t a r t - u p p r o c e d u r e , e a c h r u n w a s i n i t i a t e d b y a c o m m a n d file a n d a s p e c i a l s t a r t - u p p r o g r a m . T h e s t a r t - u p p r o g r a m s i m p l y r e a d f r o m t h e c o m m a n d file, i n v o k e d e a c h p r o t o t y p e process w i t h i t s a r g u m e n t s , a n d t h e n w a i t e d u n t i l t he l a s t p rocess c o m p l e t e d be fore d i s p l a y i n g t h e e l apsed t i m e . O n c e t h e w o r k l o a d h a d s t a b i l i z e d , t h e iostat p r o g r a m w a s i n v o k e d f r o m a s e c o n d t e r m i n a l . T h e s t a b i l i z a -t i o n c r i t e r i o n w a s t h e s a m e fo r e a c h w o r k l o a d . S i n c e e a c h process i d e n t i f i e d i t se l f w h e n i t p r i n t e d i t s t e r m i n a l o u t p u t , i t w a s poss ib l e t o t e l l w h e n e a c h o f t he processes h a d b e g u n t o execu te . A t t h i s p o i n t iostat w a s i n v o k e d . U p o n c o m p l e t i o n o f t he s t a r t u p p r o g r a m , iostat w a s m a n u a l l y i n t e r r u p t e d , c a u s i n g i t t o d i s p l a y t h e p e r f o r m a n c e d a t a a n d t h e n t e r m i n a t e . A f t e r a r u n w a s c o m p l e t e d , t h e s c r a t c h files were reset t o t h e i r o r i -g i n a l c o n t e n t s . Chapter Five: Results Page 35 5. Resul ts a n d A n a l y s i s T h e r e su l t s o f t he e x p e r i m e n t are p r e s e n t e d a n d t he a c c u r a c y a n d u t i l i t y o f t h e m o d e l are e x a m i n e d i n t h i s c h a p t e r . 5.1 E x p e r i m e n t a l Resul ts T h e m e a s u r e d a n d c a l c u l a t e d v a l u e s f o r s w a p t i m e s a n d b l o c k I/O t i m e s are g i v e n i n T a b l e I V a n d T a b l e V , r e s p e c t i v e l y . Mean Swap Times PS Measured Calculated (clicks) (msec.) (msec.) Min Max 157 50.7 91.1 118.6 314 69.8 114.7 129.7 425 93.7 146.4 161.4 470 106.5 153.2 168.2 Table IV Mean Block Read/Write Time (Tblock) Measured (msec.) Calculated (msec.) 39.8 ± 2 . 5 68.7 Table V T h e l a rge d i f f e rence b e t w e e n t h e m e a s u r e d b l o c k I/O t i m e s a n d t h e t i m e s o b t a i n e d f r o m t he m a n u f a c t u r e r ' s s p e c i f i c a t i o n s c a n be a t t r i b u t e d to t h e p h y s i c a l c loseness o f t h e Chapter Five: Results Page 36 s c r a t c h files u sed b y t h e p r o t o t y p e processes a n d t o t he L O O K d i s k s c h e d u l i n g a l go -r i t h m . T h e m e a s u r e d s w a p t i m e s a b o v e are a lso l o w e r t h a n t h e c a l c u l a t e d t i m e s d u e t o t h e l o c a l i t y o f t h e seeks . In f a c t t h e d i f fe rence b e t w e e n t h e m e a n m e a s u r e d v a l ues a n d t he m e a n c a l c u l a t e d v a l ues is a p p r o x i m a t e l y t he m e a n seek t i m e . T h e m e a s u r e d t i m e s are a p p r o x i m a t e because t h e y v a r y w i t h PN; as PN c h a n g e s , t h e n u m b e r o f t r a c k - t o - t r a c k seeks m a y c h a n g e . T h e m e a s u r e d v a l u e s a re used w h e n e v e r poss ib l e i n s u b s e q u e n t r e s u l t s . T h e r e su l t s o f t h e f a c t o r i a l p a r t o f t h e e x p e r i m e n t are p r e s e n t e d i n T a b l e V I . T h e m e a s u r e d v a l u e Qdisk is t h e m e a n queue l e n g t h at t he d i s k c o n t r o l l e r , i n c l u d i n g t he reques t c u r r e n t l y b e i n g s e r v i c e d . T h e e x p e r i m e n t a l e r r o r i n t h e m e a s u r e m e n t o f Qdisk w a s f o u n d t o be ±0 .1. Chapter Five: Results Page PS MM (clicks) PN Results of the Factorial Experiment PC = 12 msec. Arr s\ J' L », Controller NL Qdisk Nswaps ( % ) Elapsed Time (sees.) 157 650 12 4 4.8 3554 95 717 157 650 10 4 4.7 3016 95 613 157 650 8 4 4.6 1937 91 439 157 650 6 4 4.4 1202 88 358 157 650 5 4 3.4 660 78 315 157 1000 12 6 7.0 2336 96 637 157 1000 10 6 7.2 1889 94 530 157 1000 8 6 6.3 1031 89 423 157 1280 12 8 8.6 1833 95 623 157 1280 10 8 8.2 1477 93 521 157 1280 8 8 6.5 438 86 403 157 1280 6 6 3.9 5 77 311 157 1280 5 5 2.9 4 68 298 314 650 12 2 2.7 4095 96 1032 314 650 10 2 2.8 3590 95 838 314 650 8 2 2.7 2819 94 670 314 650 6 2 2.7 2027 91 510 314 650 5 2 2.6 1602 90 433 314 650 4 2 2.3 1064 81 353 314 1000 12 3 4.1 3815 96 920 314 1000 10 3 4.2 3262 97 761 314 1000 8 3 4.2 2500 95 613 314 1000 6 3 4.1 1630 92 453 314 1000 5 3 3.6 1119 86 387 314 1000 4 3 2.7 531 71 307 314 1280 12 4 4.7 3493 96 854 314 1280 10 4 4.8 2865 97 721 314 1280 8 4 4.3 2093 87 669 314 1280 6 4 4.5 1316 91 422 314 1280 5 4 3.9 691 82 346 314 1280 4 4 2.4 198 64 289 Table VI Chapter Five: Results Page 38 T a b l e V I I s h o w s t h e r e su l t s o f seve ra l r u n s whe re t he C P U i n t e r v a l was i n c r ea sed f r o m 12 msec . PC (msec.) PS MM (clicks) Supplementary Experimental Results ... ' Controller NL Qdtsk Nswaps Virion ( % ) Elapsed Time (sees.) 30 157 1280 12 8 8.2 1793 95 610 60 157 1280 12 8 8.1 2046 93 665 186 157 1280 12 8 6.1 2773 89 797 354 157 1280 12 8 3.8 3240 75 1025 354 157 1280 5 5 1.6 4 40 534 30 314 1280 12 4 4.7 3598 96 882 60 314 1280 12 4 4.6 3813 96 908 186 314 1280 12 4 3.7 3935 89 994 12 425 1280 12 3 3.8 4029 98 1045 30 425 1280 12 3 3.8 4031 98 1072 60 425 1280 12 3 3.6 4050 95 1095 186 425 1280 12 3 2.9 4053 86 1205 12 470 1280 12 2 2.9 3921 97 1047 186 157 650 12 4 3.4 4425 83 987 12 157/314 1280 12 ~5 5.7 2939 94 724 Tab le VI I O n e o f t h e s u p p l e m e n t a r y r u n s i n T a b l e V I I c o n s i s t e d o f 6 processes o f s ize 157 a n d 6 o f s ize 314 c l i c k s . T h e m e a n n u m b e r o f l o a d e d processes w a s e s t i m a t e d t o be 5. 5.2 Analysis of the Model F i g u r e 1 i l l u s t r a t e s t h e o u t p u t o f t h e m o d e l v e r sus m e a s u r e d va lues f o r s e ve r a l Chapter Five: Results Page 39 d i f f e r en t sets o f p a r a m e t e r s . T a b l e V I I I s h o w s t h e s t a n d a r d d e v i a t i o n u s i n g five o f t h e m e a s u r e m e n t s t o p r e d i c t a s i x t h . Standard Deviation in the Predictions Measured Elapsed Time Mean Prediction Standard Deviation (sees.) (sees.) (sees.) 623 ±31 .2 684.2 32.5 637 ±31 .9 680.6 30.0 717 ±35.9 735.1 38.3 854 ±42.7 787.3 30.0 920 ±46 .0 871.2 41.5 1032 ±51.6 1042.8 55.5 Table VIII T h e l i n e a r t r e n d i n e l a p s e d t i m e w i t h c h a n g i n g PN is n o t d i r e c t l y t a k e n i n t o a c c o u n t b y t h e m o d e l ; PN is a s s u m e d t o be c o n s t a n t f o r b o t h w o r k l o a d s used b y t h e m o d e l . In F i g u r e 2, a g r a p h is p l o t t e d o f e l a p s e d t i m e ve r sus PN. T h e l i n e a r i t y i n t h e e l apsed t i m e is d u e t o t h e s a t u r a t i o n o f t h e d i s k c o n t r o l l e r . T h e r e l a t i o n s h i p b e t w e e n t he b o t t l e n e c k d e v i c e a n d b o t h r e sponse t i m e a n d t h r o u g h p u t is d e r i v e d b y D e n n i n g a n d B u z e n [10]. T h e f a c t t h a t t h e l i n e a r i t y is o b s e r v e d a t t h e l owes t PN v a l u e s (PN = 4) sugges ts t h a t t h e c o n t r o l l e r is a p p r o a c h i n g s a t u r a t i o n e ven a t t h a t p o i n t . A s e c o n d e x t e n s i o n t o t h e m o d e l i n v o l v e s changes o f t h e PC p a r a m e t e r . A s PC i nc reases , t h e queue l e n g t h a t t h e d i s k c o n t r o l l e r decreases . T h i s o c c u r s because t h e r e is m o r e c o m p u t a t i o n d o n e b e t w e e n d i s k I/O reques t s a n d s ince PN is n o t c h a n g e d , t h e m e a n q u e u e l e n g t h m u s t dec rease . S i m i l a r l y , as PC decreases , t he queue l e n g t h m u s t inc rease ( up t o a p o i n t ) s i n ce reques ts are b e i n g a d d e d t o t h e queue a f t e r a s h o r t e r 7 The standard deviation was calculated using the mean of the predictions as the true mean and the predictions as the samples. Page 40 LEGEND 1100.0 -f- X P r e d i c t e d Value Q C o r r e c t Value X X 1000.0 o X X X 900.0 O X X o X X X X 300.0 X X X X X 700.0 X X X X X X 600.0 700.0 800.0 900.0 1000.0 Measured E l apsed Time (sees) 1100.0 F i gure 1 Page 41 F i gure 2 Chapter Five: Results Page 42 p e r i o d o f t i m e . T h e inc rease becomes m o s t s i g n i f i c a n t w h e n PC exceeds Tswap. It was d i s c o v e r e d t h a t t h e r a t i o o f queue l e n g t h s p r o v i d e s a g o o d a p p r o x i m a t i o n o f t h e r a t i o o f e l apsed t i m e s b e t w e e n t w o w o r k l o a d s w h i c h are t h e s a m e e x c e p t t h a t one has a la rge PC a n d t h e o t h e r a s m a l l PC. F o r e x a m p l e , d u r i n g t h e r u n ( 157 ,12 ,12 ,4 ) 8 t he m e a n queue l e n g t h w a s o b s e r v e d t o be 4.8 a n d t h e e l apsed t i m e w a s 717 se conds . D u r i n g a d i f f e r en t r u n (157 ,186 ,12 ,4 ) , t h e queue l e n g t h at t h e c o n t r o l l e r was 3.4 a n d t h e e l a p s e d t i m e w a s 987 se conds . T h e r a t i o 4.8 / 3.4 i s , w i t h i n e x p e r i m e n t a l e r r o r , 987 / 7 1 7 . T h e m e a n queue l e n g t h , h o w e v e r , m u s t be k n o w n f o r t h e w o r k l o a d w i t h t he l a rge r PC s ince t he r e a p p e a r s t o be no s i m p l e w a y t o p r e d i c t t h e c h a n g e i n queue l e n g t h w i t h a c h a n g e i n PC. T h e r e l a t i o n s h i p seems t o b r e a k d o w n i n t h e r u n w h e r e PC = 354 m s e c ; t h e p r e d i c t i o n f r o m t h i s d a t a g r e a t l y exceeds t h e m e a s u r e d e l a p s e d t i m e . P r e s u m a b l y t h i s is because t h e d i s k s a t u r a t i o n a s s u m p t i o n is v i o l a t e d o r p e r h a p s a n o t h e r f a c t o r w h i c h is n o t t a k e n i n t o a c c o u n t b y t h e m o d e l s t a r t s t o become i n f l u e n t i a l w h e n PC is s u f f i c i e n t l y l a rge . T h e m e a n q u e u e l e n g t h is i n f l u e n c e d b y b o t h t h e b u f f e r i n g m e c h a n i s m a n d b y /etc/update w h i c h flushes t h e buf fers p e r i o d i c a l l y . B e cause o f t h i s , t h e o b s e r v e d s w a p -p i n g r a t e does n o t agree w e l l w i t h t h e r a t e p r e d i c t e d b y t h e m o d e l . It a lso appea r s t o be d i f f i c u l t t o p r e d i c t w h a t t h e queue l e n g t h a t t h e c o n t r o l l e r w i l l be as PC is i n c r ea sed b e y o n d Tswap. T h i s w o u l d p r o b a b l y m a k e t h e m o d e l , as i t i s , o f l i t t l e use w h e n d e a l i n g w i t h c o m p i l i n g - t y p e w o r k l o a d s . 5.3 Sources of Error 8 The notation (PS,PC,PN,NL) will be nsed in the following discussion to describe the experimental parame-ters. Chapter Five: Results Page 43 T h e r e a re seve ra l p o t e n t i a l sources o f e r r o r i n t h e e x p e r i m e n t . D i f fe rences i n b o t h t he a l l o c a t i o n o f file space a n d s w a p space b e t w e e n r u n s i n t r o d u c e a c e r t a i n a m o u n t o f e r r o r . It is p o s s i b l e t h a t s o m e even t s w e r e m i s s e d because s a m p l i n g w a s done a t 6 0 H z . E r r o r s i n t h e m a n u f a c t u r e r ' s s p e c i f i c a t i o n s are a l so p o s s i b l e . A c e r t a i n a m o u n t o f h u m a n e r r o r is i n t r o d u c e d b y t h e need t o m a n u a l l y i n t e r r u p t t h e m e a s u r e m e n t p r o g r a m w h e n the w o r k l o a d finishes. T h e s e sources o f e r r o r p r o b a b l y a c c o u n t f o r t h e 5 pe r cen t fluctua-t i o n i n e l a p s e d t i m e m e n t i o n e d ea r l i e r . A few e x p e r i m e n t a l r u n s were r e d o n e seve ra l t i m e s w h e n t h e a c c u r a c y o f t h e first r u n w a s i n d o u b t . E i t h e r m e a n v a l u e s we r e used i n s u c h cases o r t h e q u e s t i o n a b l e r e s u l t w a s d i s c a r d e d . 5.4 Applications T h e f o l l o w i n g h y p o t h e t i c a l s i t u a t i o n s are p r e s e n t e d t o i n d i c a t e areas w h e r e t h e m o d e l a n d i t s e x t e n s i o n s m a y find a p p l i c a t i o n . I n e a c h e x a m p l e i t is a s s u m e d t h a t b o t h w o r k l o a d s are f a i r l y u n i f o r m a n d cons i s t m a i n l y o f i n t e r a c t i v e p r o g r a m s o r m a n y s h o r t p r o g r a m s w h i c h t e n d t o s a t u r a t e t h e d i s k c o n t r o l l e r . S u p p o s e t h e r e w a s a U N I X s y s t e m w h i c h h a d 1280 c l i c k s o f a v a i l a b l e m e m o r y , a n ave rage o f 10 user p rocesses , 4 o f w h i c h c o u l d , o n ave r age , be r e s i d e n t . A s s u m e t h a t Tblock is 0.05 s e c , Tswap is 0 .07 sec. a n d t h a t t h e t h i n k t i m e is n e g l i g i b l e . T h e i n s t a l l a -t i o n w o u l d l i k e t o e s t i m a t e t h e effect o f d o u b l i n g t he user m e m o r y o n m e a n response t i m e . S u b s t i t u t i n g i n t o E q u a t i o n 3 .1 , „ 8*4 *0.05 + 4 *0.07 Ratio = 8 *4 *0.05 + 8 *0.07 = 0.87 or a 13 p e r c e n t decrease i n e l apsed t i m e . Chapter Five: Results Page 44 A s i m i l a r m e t h o d c o u l d be f o l l o w e d t o d e t e r m i n e t he i n f l uence o f a c h a n g e i n Tblock a n d / o r Tswap. S u p p o s e t h e i n s t a l l a t i o n w o u l d l i k e t o e s t i m a t e t h e effect o f d e c r e a s i n g Tblock t o 0.04 sec. a n d Tswap t o 0.055 sec . S u b s t i t u t i n g i n t o E q u a t i o n 3.1, Ratio = 4 *4 *0.04 + 4 *0.055 4 *4 *0.05 + 4 * 0.070 = 0.80 or a 20 p e r c e n t dec rease i n e l a p s e d t i m e . S u p p o s e t h a t s w a p p i n g effects we re e l i m i n a t e d a l t o g e t h e r b y k e e p i n g a l l processes l o a d e d o r b y t he a d d i t i o n o f e x t r e m e l y fas t s w a p p i n g h a r d w a r e . F r o m E q u a t i o n 3.1, 10 *4 *0.05 + 4 *0.00 Ratio = 10 * 4 * 0.05 + 10 * 0.07 = 0.74 t h e m o d e l p r e d i c t s a 26 p e r c e n t decrease i n e l apsed t i m e . B e cause o f t h e s a t u r a t i o n a s s u m p t i o n , t h e inc rease o r dec rease i n e l a p s e d t i m e w i t h a c h a n g e i n PN m a y be a s s u m e d t o be l i n e a r ; e .g. , d o u b l i n g PN s h o u l d a p p r o x i m a t e l y d o u b l e t h e c o m p l e t i o n t i m e . I f Tblock w a s dec r ea sed t o 0.04 sec. a n d PN was i n c r ea sed b y 50 p e r c e n t , t h e n n 4 *4 *0.04 + 4 *0.07 15 Ratio = * — 4 *4 *0.05 + 4 *0.07 10 = 1.28 a n d so t h e e l apsed t i m e w o u l d be e x p e c t e d t o inc rease b y a b o u t 28 p e r c e n t . Chapter Five: Results Page 45 If t h e m e a n queue l e n g t h a t t h e c o n t r o l l e r is k n o w n o r c a n be e s t i m a t e d f o r a c h a n g e i n t h e C P U r e q u i r e m e n t s , t h e n t h e r a t i o o f q u e u e l eng ths c a n be used t o e s t i m a t e t he c h a n g e i n e l apsed t i m e . S u p p o s e , f o r e x a m p l e , t h a t t he i n s t a l l a t i o n w o u l d l i k e t o e s t i m a t e t h e effect o f d e c r e a s i n g Tswap t o 0.06 sec . w h i l e a t t h e s a m e t i m e i n c r e a s i n g PC f r o m 0.012 sec . t o 0.05 sec. a n d i n c r e a s i n g NL t o 6 b y t h e a d d i t i o n o f m e m o r y . T h e queue l e n g t h a t t h e d i s k c o n t r o l l e r i n t h e new c o n f i g u r a t i o n w i l l be e s t i m a t e d t o be NL + 1, s i n ce PC w i l l be less t h a n Tswap. T h e e x p e c t e d c h a n g e w o u l d be a p p r o x i m a t e l y : Ratio —- 4 *6 *0.05 + 4 *0.06 4 *6 *0.05 + 6 *0.07 = 0.63 Chapter Six: Conclusions Page 40 6. Conclusions 6.1 The Model and Validation A s i m p l e , d e t e r m i n i s t i c m o d e l o f a d i s k - s a t u r a t e d s w a p p i n g s y s t e m w a s d e v e l o p e d a n d v a l i d a t e d t h r o u g h a c o n t r o l l e d e x p e r i m e n t . T h e m o d e l w a s f o u n d t o p r o v i d e a g o o d a p p r o x i m a t i o n o f t h e r a t i o o f e l a p s e d t i m e s b e t w e e n t w o w o r k l o a d s w i t h d i f f e r i n g p a r a m -e te rs . A s p r e d i c t e d b y t h e o r y , t h e c h a n g e i n e l a p s e d t i m e w a s l i n ea r w i t h t h e c h a n g e i n t h e n u m b e r o f processes w h e n t h e d i s k c o n t r o l l e r a p p r o a c h e d s a t u r a t i o n . W h e n t h e C P U r e q u i r e m e n t s o f t h e processes we re i n c r e a s e d , w i t h i n l i m i t s , t h e r a t i o o f queue l e n g t h s a t t h e d i s k c o n t r o l l e r w a s f o u n d t o be a g o o d a p p r o x i m a t i o n o f t h e r a t i o b e t w e e n e l a p s e d t i m e s . O n l y one h a r d w a r e c o n f i g u r a t i o n w a s used t o k e e p t he s ize o f t h e e m p i r i c a l v a l i d a -t i o n r e a s o n a b l e . A s y n t h e t i c w o r k l o a d h a d t o be c r e a t e d because t h e n a t u r a l w o r k l o a d w a s u n s a t i s f a c t o r y f o r v a l i d a t i o n p u r p o s e s . S e ve r a l s a m p l e a p p l i c a t i o n s we r e d e s c r i b e d . A n i m p o r t a n t c h a r a c t e r i s t i c o f t h e m o d e l is t h a t s ince i t is d e t e r m i n i s t i c , t he r e is n o need t o d e t e r m i n e dev i c e r o u t i n g p r o b a b i l i t i e s . A l t h o u g h t h e m o d e l is s i m p l e , i t c a n be u s e d t o d e t e r m i n e t h e c h a n g e i n p e r f o r m a n c e w i t h changes i n t h e h a r d w a r e c o n f i g u r a t i o n . S i n ce t h e s ize o f m a i n m e m o r y is c o n s t a n t , t h e m e a n n u m b e r o f processes a n d t h e m e a n p rocess s ize c a n be d e t e r m i n e d f r o m o n l y one pass t h r o u g h t h e s y s t e m process t a b l e . T h e m e a n d i s k I/O t i m e s c a n be eas i l y m e a s u r e d f r o m w i t h i n t h e s y s t e m o r c a n be c a l -c u l a t e d u s i n g t h e m a n u f a c t u r e r ' s s p e c i f i c a t i o n s . 6.2 Tools and Method T h e d a t a m e a s u r e m e n t a n d e x t r a c t i o n too l s f o r t h e e x p e r i m e n t p r o v e d v e r y s a t i s -f a c t o r y f o r t h e n a t u r e o f t he i n f o r m a t i o n b e i n g c o l l e c t e d . T h e too l s are s t r a i g h t f o r w a r d Chapter Six: Conclusions Page 47 a n d because t h e y are w r i t t e n i n C , are q u i t e p o r t a b l e a n d eas i l y u n d e r s t o o d . T h e ove r -h e a d i n t r o d u c e d b y t h e too l s is n e g l i g i b l e . T h e f a c t o r i a l n a t u r e o f t h e e x p e r i m e n t , c h o s e n t o t e s t t h e m o d e l u n i f o r m l y , p r o v e d s a t i s f a c t o r y w h e n s u p p l e m e n t e d b y seve ra l a d d i t i o n a l r u n s . A s m e n t i o n e d a b o v e , t e s t i n g t h e m o d e l u n d e r v a r i o u s h a r d w a r e c o n f i g u r a t i o n s is d e s i r a b l e , b u t t u r n e d o u t t o be i m p r a c t i c a l . S i m i l a r l y , a d d i t i o n a l f a c t o r s w o u l d s i g n i f i c a n t l y inc rease t h e s ize o f t h e e x p e r i m e n t . 6.3 Domain of Applicability P e r h a p s t h e g rea tes t s i m p l i f i c a t i o n i n t h e e x p e r i m e n t was t he use o f a n h o m o g e n e -ous s y n t h e t i c w o r k l o a d . W h i l e t h i s does n o t re f lec t r e a l i t y , one e x p e r i m e n t w h e r e t h e process s izes we r e n o t i d e n t i c a l g a v e a r e s u l t c lose t o t h a t p r e d i c t e d b y t h e m o d e l (see the l as t e n t r y , T a b l e V I I ) . A l t h o u g h m o r e w o r k s h o u l d be d o n e o n t h i s , i t is f e l t t h a t t h e m o d e l w i l l c o n t i n u e t o be u s e f u l as l o n g as t he r e a re n o t la rge d i f fe rences i n t h e C P U r e q u i r e m e n t s o f t h e processes w h i c h m a k e u p t he w o r k l o a d . A d d i t i o n a l w o r k c o u l d i n v e s t i g a t e t h e effect p u r e , s h a r a b l e code has o n t h e a c c u r a c y o f t h e m o d e l . R e g a r d i n g w o r k l o a d , t h e d o m a i n is l i m i t e d t o h i g h l y i n t e r a c t i v e e n v i r o n m e n t s w h e r e C P U reques ts a re a l l m u c h less t h a n one s e c o n d ; i.e., w h e r e t h e w o r k l o a d cons i s t s m a i n l y o f e d i t i n g , file m a n i p u l a t i o n , a n d e x e c u t i o n o f p r o g r a m s w h i c h are e i t h e r s h o r t o r w h i c h i n t e r a c t w i t h t h e t e r m i n a l . O b v i o u s l y t h e m o d e l is r e s t r i c t e d t o s y s t e m s w h i c h e m p l o y s w a p p i n g . A n o t h e r d e p a r t u r e f r o m r e a l i t y is t h e absence o f t e r m i n a l i n p u t . T h i s w a s n o t c o n -s i d e r e d t o o s i g n i f i c a n t because a g o o d a p p r o x i m a t i o n u s i n g t e r m i n a l o u t p u t w a s u s e d . B e cause n e w e r v e r s i o n s o f U N I X use s i m i l a r s c h e d u l i n g a n d s w a p p i n g s t r a t eg i e s , t he m o d e l c o u l d be a p p l i e d t o t h e m as w e l l . T e s t i n g t h i s h y p o t h e s i s , h o w e v e r , w a s n o t Chapter Six: Conclusions Page 48 poss i b l e . 6.4 Future Research T h e r e s u l t s o f t h i s s t u d y c o u l d be used as a bas i s f o r r e sea r ch i n t o t he f o l l o w i n g : 1. A more general model, not relying on disk saturation, 2. Expanding the model to account for large PC values so that compiling-type workloads can be considered, 3. An examination of the differences in performance between swapping and paging on a small machine where the disk is the limiting resource, 4. Testing the model on a different hardware configuration, perhaps one with over-lapped file I/O and swapping capability, 5. Studying the effectiveness of a processor scheduling algorithm which attempts to balance the characteristics of the loaded processes to reduce the swapping load. Bibliography Page 4 0 1. BELADY, L.A., AND KUEHNER, C.J. Dynamic space-sharing in computer systems. Com-munications of the ACM 12, 5 (May 1969), 282-288. 2. BERNSTEIN, A.J., AND SHARP, J.C. A policy-driven scheduler for a time-sharing system. Communications of the ACM 14, 2 (February 1971), 74-78. 3. BUZEN, J. P. Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM 16, 9 (September 1973), 527-531. 4. BUZEN, J. P. Fundamental operational laws of computer system performance. Acta Infor-matica 7, 2 (1976), 167-282. 5. CHANDY, K. M., AND SAUER, C. H. Approximate methods for analyzing queueing network models of computer systems. Computing Surveys 10, 3 (September 1978), 281-317. 6. CHEN, P. P. Queueing network model of interactive computing systems. Proc. of the IEEE 68, 6 (June 1975), 954-957. 7. COFFMAN JR . , E. G. Analysis of two time-sharing algorithms designed for limited swap-ping. Journal of the ACM 15, 3 (July 1968), 341-353. 8. DEITEL, H. M. An Introduction to Operating Systems, Addison-Wesley, Reading, Mass., 1983. 9. DENNING, P. J. Virtual memory. Computing Surveys 2, 3 (September 1970), 153-289. 10. DENNING, P. J., AND BUZEN, J. P. The operational analysis of queueing network models. Computing Surveys 10, 3 (September 1978), 225-261. 11. DENNING, P. J., KAHN, K. C , LEROUDIER, J., POTIER, D., AND SURI, R. Optimal mul-tiprogramming. Acta Informatica 7, 2 (1976), 197-216. 12. DOWDY, L. W., AGRAWALA, A. K., GORDON, K. D., AND TRIPATHI, S. K. Computer per-formance predictions via analytic modeling—an experiment. Conference on Simulation, Measurement and Modeling of Computer Systems, August 1979, 13-28. Bibliography Page 50 13. DOWNING, R. A Performance Experiment on a UNIX System, M.Sc. Thesis , Un ivers i ty of Br i t i sh C o l u m b i a , 1979. 14. FERRARI, D. Computer Systems Performance Evaluation, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1978. 15. GRAHAM, G. S. Queueing network models of computer system performance. Computing Surveys 10,3 (September 1978), 219-224. 16. GRENANDER, U. , AND TSAO, R. F. Quant i t a t i ve methods for eva luat ing computer system performance: a review and proposals. In Statistical Computer Performance Evaluation, W . Freiberger (Ed.), Academic Press, N e w Y o r k , N.Y. , 1972, 3-24. 17. HELLERMAN, H. Discussion of session II. In Statistical Computer Performance Evaluation, W. Fre iberger (Ed.), Academic Press, N e w Y o r k , N.Y. , 1972, 99-200. 18. KERNIGHAN, B. W. , AND MclLROY, M . D. UNIX Programmer's Manual, Seventh E d i t i o n , V o l . 1, B e l l Labs , January 1979. 19. KlENZLE, M . G., AND SEVCIK, K. C. Survey of analytic queueing network models of com-puter systems. Conference on Simulation, Measurement and Modeling of Computer Sys-tems, August 1979, 113-229. 20. KLEINROCK, L. Swap-time considerations in time-shared systems. IEEE Transactions on Computers C-29, 6 (June 1970), 534-540. 21. LAZOWSKA, E. D. The benchmark ing , tun ing , and analyt ic model ing of V A X / V M S . Conference on Simulation, Measurement and Modeling of Computer Systems, Augus t 1979, 57-64. 22. LIONS, J. A Commentary on the UNIX Operating System, Un ivers i ty of New South Wales, 1977. 23. McKlNNEY, J. M. A survey of analytical time-sharing models. Computing Surveys 1, 2 (June 1969), 105-216. Bibliography Page 51 24. MUNTZ , R. R. Analytic modeling of interactive systems. Proc. of the IEEE 63, 6 (June 1975), 946-953. 25. MUNTZ, R. R. Queueing networks: a critique of the state of the art and directions for the future. Computing Surveys 10, 3 (September 1978), 353-359. 26. N l E L S O N , N . R. An analysis of some time-sharing techniques. Communications of the ACM 14, 2 (February 1971), 79-90. 27. PDP-11 Processor Handbook. Digital Equipment Corporation, 1981. 28. Peripherals Handbook. Digital Equipment Corporation, 1981. 29. RITCHIE , D. M. The UNIX I/O system. Bell Labs Internal Memorandum, 1974. 30. RITCHIE, D. M. A retrospective. Bell System Technical Journal, Part 2, July/August 1978, 1947-2969. 31. RITCHIE , D. M., AND THOMPSON , K. The U N K time-sharing system. Bell System Techni-cal Journal, Part 2, July/August 1978, 1905-2930. 32. ROSE , C. A. A measurement procedure for queueing network models of computer systems. Computing Surveys 10, 3 (September 1978), 263-280. 33. SCHERR, A. L. An analysis of time-shared computer systems, Research Monograph No. 36, The M.I.T. Press, Cambridge, Mass., 1967. 34. SHEMER, J. E., AND HEYING, D. W. Performance modeling and empirical measurements in a system designed for batch and time-sharing users. Proc. AFIPS 1969 FJCC, Vol. 35, AFfPS Press, Montvale, N.J., pp. 17-26. 35. STRAUSS, J. C. A simple thruput and response model of EXEC8 under swapping satura-tion. Proc. AFIPS 1971 FJCC, Vol. 39, AFfPS Press, Montvale, N.J., pp. 39-49. Bibliography Page 52 36. TEORY, T. J. Properties of disk scheduling policies in multiprogrammed computer sys-tems. Proc. AFIPS 1972 FJCC, Vol. 41, Part I, AFIPS Press, Montvale, N.J., pp. 1-21. 37. TEORY, T. J., AND PINKERTON, T. B. A comparative analysis of disk scheduling policies. Communications of the ACM 15, 3 (March 1972), 177-284. 38. THOMPSON, K. UNIX implementation. Bell System Technical Journal, Part 2, July/August 1978, 1931-2946. 39. TSUJIGADO, M. Multiprogramming, swapping and program residence priority in the F A C O M 230-60. Proc. AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N.J., pp. 223-228. 

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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051832/manifest

Comment

Related Items