Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Program and job-stream characteristics in the michigan terminal system Bowler, Kenneth Haydn 1972

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

Item Metadata

Download

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

Full Text

PROGRAM AND JOB-STREAM CHARACTERISTICS IN THE MICHIGAN TERMINAL SYSTEM by KENNETH H. BOWLER B. Eng., Carleton U n i v e r s i t y , 1969 A t h e s i s submitted i n p a r t i a l f u l f i l m e n t of the requirements f o r the degree of MASTER OF SCIENCE i n the Department of COMPUTER SCIENCE We accept t h i s t h e s i s as conforming to the r e q u i r e d standard. THE UNIVERSITY OF BRITISH COLUMBIA J u l y , 1972 In present ing th is thes is in p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the Un ive rs i t y of B r i t i s h Columbia, I agree that the L i b r a r y sha l l make i t f r e e l y a v a i l a b l e for reference and study. I fu r ther agree that permission for extensive copying o f th is t h e s i s fo r s c h o l a r l y purposes may be granted by the Head of my Department or by h is representa t ives . It is understood that copying or p u b l i c a t i o n o f th is t h e s i s f o r f i n a n c i a l gain sha l l not be allowed without my wr i t ten permiss ion . Department The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada i ABSTRACT There has been l i t t l e p u b l i s h e d about the c h a r a c t e r i s t i c s of computer jobs running on modern tim e - s h a r i n g computer systems, due l a r g e l y to the l a c k of a p p r o p r i a t e programs and equipment necessary to measure the parameters i n v o l v e d . In t h i s t h e s i s , measures are presented f o r some of the important c h a r a c t e r i s t i c s of jobs. The Data C o l l e c t i o n F a c i l i t y , which i s part of the Michigan Terminal System, was used to t h i s end. The Michigan Terminal System i s a time-sharing o p e r a t i n g system f o r the IBM 360/67 computer, and supports batch and t e r m i n a l users s i m u l t a n e o u s l y . Chapter 1 g i v e s an o u t l i n e of the problem, and other work which has been done i n t h i s l i n e . I t a l s o c o n t a i n s a reasonably d e t a i l e d d e s c r i p t i o n of the Michigan Terminal System. In Chapter 2, measurements of requested CPU s e r v i c e , CPU s e r v i c e obtained, system and user response times, I/O delays, and page wai t i n g times are g i v e n . Chapter 3 o u t l i n e s the s t o r a g e requirements of jobs, and g i v e s a model which w i l l generate p r o f i l e s of s t o r a g e r e q u i r e d by jobs over t h e i r running times, which are very s i m i l a r to p r o f i l e s observed f o r a c t u a l jobs. Some d i s c u s s i o n of the r e s u l t s i s given i n chapter 4, and a l s o a simple model of the system i s shown which might be used i n a s i m u l a t i o n study employing measurements taken i n t h i s study. i i TABLE OF CONTENTS Chapter 1 - I n t r o d u c t i o n 1 1.1 Preamble 1 1.2 D e s c r i p t i o n of the Michigan Terminal System 6 1.3 Problem Area 18 Chapter 2 - Some Basic C h a r a c t e r i s t i c s 21 2.1 fieguests f o r CPU Se r v i c e 21 2.2 CPU Se r v i c e Obtained 25 2.3 I/O Delays 27 2.4 Page Waiting Times 32 2.5 Other Parameters of I n t e r e s t 34 Chapter 3 - Storage Requirements 4 1 3.1 Preamble 4 1 3.2 Observed Storage Requirements 42 3.3 A Model f o r Program Storage Requirements 44 Chapter 4 - Summary and Discussion 50 4.1 Summary and Discussion 50 4.2 A Simple Model of MTS f o r Simulation 51 4.3 Concluding Remarks 57 Bib l i o g r a p h y 58 Appendix A - The Data C o l l e c t i o n F a c i l i t y 63 Appendix B - F i t t i n g Weibull and Hyper-exponential D i s t r i b u t i o n s 65 Appendix C - The Data 68 Appendix D - Storage P r o f i l e s 71 Appendix E - The Computing System 85 i l l LIST OF TABLES 2.1 Job stream c h a r a c t e r i s t i c s UO 3.1 Comparison of observed p r o f i l e s , and those generated by the model U9 C.1 MTS data 69 C.2 Frequency of STAT items 70 LIST OF FIGURES 1. 1 Flowchart of storage scheduling 15 1. 2 Flow of tasks i n MTS 20 2. 1 Requested CPU i n t e r v a l s ( i n t e r a c t i v e ) 23 2. 2 Requested CPU i n t e r v a l s (batch) 23 2. 3 Processor time between i n t e r a c t i o n s 24 2. 4 Ac t u a l CPU i n t e r v a l s (tape 1) 26 2. 5 Ac t u a l CPU i n t e r v a l s (tape 2) 26 2. 6 I/O delays (batch) 28 2. 7 I/O delays ( i n t e r a c t i v e ) 28 2. 8 User response time 31 2. 9 System wri t e time ( i n t e r a c t i v e ) 31 2, 1 Page waiting times (tape 1) 34 2, 11 Page waiting times (tape 2) 35 2, 12 Page waiting times generated by the model 35 2. 13 System response time 36 2. 14 Ready i n t e r v a l s (tape 1) 38 2. 15 Ready i n t e r v a l s (tape 2) 38 3. 1 T y p i c a l storage p r o f i l e 43 3. 2 D i s t r i b u t i o n s f o r storage p r o f i l e model (grp D 45 3. 3 D i s t r i b u t i o n s f o r storage p r o f i l e model (grp 2) 46 3. 4 Flowchart f o r storage p r o f i l e model 48 a . 1 Flowchart f o r a model of MTS 54 D. 1 through D.8 Observed p r o f i l e s (group!) 71- 74 D. 9 through D.20 Observed p r o f i l e s (group 2) 75- 80 D. 21 through D.24 Generated p r o f i l e s (group D 81- 82 D. 25 through D.28 Generated p r o f i l e s (group 2) 83- 84 V ACKNOWLEDGMENT I w i s h t o e x p r e s s my t h a n k s t o Dr. D.A.R. S e e l e y f o r h i s h e l p f u l a s s i s t a n c e d u r i n g t h e p r e p a r a t i o n o f t h i s t h e s i s , a n d t o t h e N a t i o n a l R e s e a r c h C o u n c i l o f Ca n a d a , and t h e D e p a r t m e n t o f Computer S c i e n c e f o r p r o v i d i n g f i n a n c i a l a s s i s t a n c e d u r i n g t h e c o u r s e o f my s t u d i e s . I w i s h a l s o t o t h a n k my w i f e , J o a n , who p r o v i d e d much e n c o u r a g e m e n t , and s p e n t many h o u r s k e y p u n c h i n g and p r o o f - r e a d i n g f o r t h e p r e p a r a t i o n o f t h i s work. CHAFTEB 1 INTRODUCTION 1.1 Preamble In the p a s t , program behavior and the c h a r a c t e r i s t i c s of the job mix running on a computer system were r e l a t i v e l y easy t h i n g s to observe. The machines were slow, and u s u a l l y ran as s i n g l e thread batch systems, so that one program was processed to completion before another was allowed on the system. I t was p o s s i b l e on the e a r l y machines to time the p e r i o d s of p r o c e s s o r a c t i v i t y and waits f o r I/O with a stop watch s i n c e there was no o v e r l a p of p r o c e s s i n g and I/O, and the times of the events were of the order of seconds. On f a s t e r machines the measurements s t i l l c o u l d have been e a s i l y made using some s o r t of hardware device to do the measuring. With the advent of multiprogramming, measurements of program behavior became much more d i f f i c u l t . Hardware devices c o u l d s t i l l measure e a s i l y the p r o c e s s i n g and I/O i n t e r v a l s on the system, but, as s t a t e d by Drummond [ 1 9 ] , data dependent c h a r a c t e r i s t i c s such as job i d e n t i f i c a t i o n , data set i d e n t i f i c a t i o n , and the o r i g i n s of r e g u e s t s are not r e a d i l y a v a i l a b l e . In e f f e c t , what these d e v i c e s measure i s system behavior and not program behavior. The c h a r a c t e r i s t i c s of s i n g l e jobs can be determined using a hardware d e v i c e by running the jobs alone on the system one at a time, as was done by Cheng [ 1 2 ] . T h i s method i s t e d i o u s , and t i e s up the system f o r long p e r i o d s of time, which makes i t i m p r a c t i c a l t o use i n a busy environment. Other c o m p l i c a t i o n s f o r measurement a l s o a r i s e . Not a l l the I/O i s a s s o c i a t e d with the jobs that are running. In an e f f o r t to improve the u t i l i z a t i o n of various resources of the 2 system, jobs can not be allowed to t i e up c e r t a i n d e v i c e s f o r long p e r i o d s of time. (In p a r t i c u l a r c a r d readers and p r i n t e r s ) . I f a job i s allowed to possess a p r i n t e r , i t w i l l t i e i t up f o r the d u r a t i o n of i t s running time on the system, (since the output f o r one job must be kept together) even though i t p r i n t s o n l y a few l i n e s . Other jobs r e q u i r i n g the p r i n t e r can not be dispatched. The s o l u t i o n i s to have the job write i t s output to a f i l e on d i s k (or t a p e ) , and a f t e r i t i s f i n i s h e d have the system take care of the p r i n t i n g . S i m i l a r l y c a r d input i s read i n t o a d i s k f i l e , and the job can read the f i l e as i t progresses without t y i n g up the card reader f o r long p e r i o d s . So we have the system, as well as the jobs running, doing I/O. Time-sharing adds the a d d i t i o n a l c o m p l i c a t i o n t h a t a job running on a GPU does not need t o i n i t i a t e an I/O o p e r a t i o n to l o s e c o n t r o l of i t s CPU. On a m u l t i p r o c e s s i n g system more than one job can be running on the system at once and the task of a s s o c i a t i n g events with the job i n v o l v e d i s a very complex one f o r an e x t e r n a l hardware de v i c e , (A good d e s c r i p t i o n of the type of i n f o r m a t i o n gathered by a hardware d e v i c e may be found i n [ 7 ] ) . For a software d e v i c e , t h i s task i s much simpler, and v a r i o u s such d e v i c e s (see [ 3 , 4 7 ] f o r examples) have been w r i t t e n f o r some computer systems. Software d e v i c e s have such i n f o r m a t i o n , as job i d e n t i f i c a t i o n and the s t a t i s t i c s t h a t the system keeps about the j o b s , e a s i l y a v a i l a b l e to them (the device may be the part of the system t h a t c o l l e c t s these s t a t i s t i c s ) , but r e q u i r e f o r t h e i r o p e r a t i o n some part of the system's r e s o u r c e s . T h i s f a c t i m p l i e s that they can a f f e c t the measurements that they are 3 t a k i n g , a n d t h i s must a l w a y s be c o n s i d e r e d when u s i n g s u c h a d e v i c e . Two t y p e s o f s o f t w a r e measurement t e c h n i q u e s have emerged i n r e c e n t y e a r s . One a p p r o a c h i s a s a m p l i n g [ 1 9 , 4 7 , 4 8 ] f o r m o f measurement i n w h i c h v a r i o u s s t a t i s t i c s k e p t a b o u t t h e j o b s a r e s a m p l e d p e r i o d i c a l l y and t h e r e s u l t s r e c o r d e d . (CPU t i m e , I/O r e g u e s t s , p a g e r e a d s e t c . ) I t i s e a s y t o s e e t h a t a w e l l d e v i s e d p r o g r a m t o do t h i s s a m p l i n g w i l l n o t a f f e c t t h e m e a s u r e m e n t s t h a t i t t a k e s , a s l o n g as i t d o e s n o t s a m p l e t o o f r e q u e n t l y . I t m i g h t use o n l y a few m i l l i s e c o n d s o f CPU t i m e e v e r y f ew s e c o n d s , b u t t h e r e i s a c o n s i d e r a b l e l o s s o f d e t a i l e d i n f o r m a t i o n u s i n g t h i s t e c h n i g u e . Mean t i m e s f o r e v e n t s may be o b t a i n e d , b u t i n f o r m a t i o n a b o u t d i s t r i b u t i o n s o f e v e n t t i m e s , and t h e s e q u e n c e s o f e v e n t s [ 1 9 , 4 0 ] w i l l be l o s t . The s e c o n d t y p e o f d e v i c e (program) m o n i t o r s c o n t i n u o u s l y , and e v e r y i m p o r t a n t e v e n t h a p p e n i n g i n t h e s y s t e m c a n be r e c o r d e d . (See [ 3 , 3 9 ] f o r e x a m p l e s . ) I n o r d e r t h a t t h i s t e c h n i q u e d o e s n o t c o m p l e t e l y o v e r w h e l m t h e m e a s u r e m e n t s t h a t i t i s t a k i n g , i t must be a p a r t o f t h e s u p e r v i s o r p r o g r a m o f t h e s y s t e m , s i n c e t h e i n f o r m a t i o n i s e a s i l y a v a i l a b l e a t t h i s l e v e l , and may be o b t a i n e d a t s m a l l e x p e n s e . ft p r o g r a m t o do t h i s t y p e o f m o n i t o r i n g , e x t e r n a l t o t h e s u p e r v i s o r , would v i r t u a l l y h a v e t o i n t e r p r e t e v e r y a c t i o n t h a t t h e s u p e r v i s o r t a k e s , t o s e e i f some i n f o r m a t i o n n e e d s s a v i n g . S u c h i n t e r p r e t a t i o n w o u l d c a u s e c o n s i d e r a b l e d e g r a d a t i o n o f s y s t e m p e r f o r m a n c e , b e c a u s e o f t h e p r o c e s s o r t i m e n e c c e s s a r y t o a c c o m p l i s h i t . T h i s makes t h i s t e c h n i g u e much more d i f f i c u l t t o i m p l e m e n t t h a n t h a t o f 4 sampling. The disadvantage of the continuous monitoring technique i s that enormous q u a n t i t i e s of raw data are produced, and the c o s t of reducing these data can be qu i t e l a r g e . The sampling method on the other hand, produces manageable q u a n t i t i e s of s p e c i f i c data which are more e a s i l y reduced. L i t t l e data has been published on the c h a r a c t e r i s t i c s of jobs i n a t i m e - s h a r i n g environment, other than t h e i r behavior with r e s p e c t t o paging, and paging s t r a t e g i e s . Brawn and Gustavson [ 8 ] measured the e f f e c t of r e s t r i c t i n g r e a l memory s i z e on the running time of v a r i o u s programs, and they, as well as H a t f i e l d [ 2 6 ] , s t u d i e d the e f f e c t of r e s t r u c t u r i n g programs to l o c a l i z e t h e i r memory r e f e r e n c e s , on the amount of paging r e g u i r e d . Coffman and V a r i a n [13] were i n t e r e s t e d i n the times between i n t e r - p a g e r e f e r e n c e s (as were Fine e t a l [ 2 2 ] ) , and a l s o page r e s i d e n c e times i n main memory. U n f o r t u n a t e l y t h e i r study was done using u n r e a l i s t i c r e s t r i c t i o n s on core s i z e . F r e i b e r g s [23] has measured the times taken between c a l l s t o the s u p e r v i s o r program f o r s e r v i c e s , f o r a few types of programs (a FOBTRAH compiler, a l i s t p r o c e s s i n g program, e t c . ) , and has measured a d i s t r i b u t i o n f o r the maximum memory requirements of jobs on M c G i l l ' s IBM 7044. Scherr [45] and Schwetman and DeLine [44] have measured d i s t r i b u t i o n s f o r user response time (think time) and system response time f o r two d i f f e r e n t systems. Scherr as w e l l has obtained a d i s t r i b u t i o n f o r the amount of pr o c e s s o r time demanded by tasks between i n t e r a c t i o n s on P r o j e c t MAC 'S CTSS system. Baskett e t a l [ 5 ] have measured a d i s t r i b u t i o n f o r d i s k I/O de l a y s . 5 The problem of page t r a n s f e r times has been w e l l covered i n the l i t e r a t u r e [14,39], but i n the Michigan Terminal System (MTS), which i s the o p e r a t i n g system f o r the U n i v e r s i t y of B r i t i s h Columbia's IBM 360/67 computer, a l a r g e p o r t i o n of the page f a u l t s do not r e q u i r e page t r a n s f e r s from the drum. These f a u l t s r e s u l t from the f i r s t r e f e r e n c e to a new page. MTS does not a l l o c a t e any r e a l page to a job u n t i l a f t e r t h at page has been r e f e r e n c e d . The f i r s t r e f e r e n c e to a, new page causes a page f a u l t which can be d e a l t with by immediately a l l o c a t i n g an a v a i l a b l e r e a l page, and no drum t r a n s f e r occurs. (See s e c t i o n 2.4.) Parameters l i k e the t o t a l processor time r e q u i r e d by jobs, and job i n t e r - a r r i v a l times are h i g h l y s i t u a t i o n dependent, but can be e a s i l y obtained i f the system keeps any accounting s t a t i s t i c s . Although models have been proposed f o r the r e a l core reguirements of computer jobs, notably Denning»s [ 1 6 ] , almost nothing e x i s t s concerning jobs* v i r t u a l memory reguirements. By v i r t u a l memory requirements, we mean the t o t a l i nstantaneous s t o r a g e reguirements, which i s a dynamic q u a n t i t y i n most time-s h a r i n g systems. Lehman and Hosenfeld [31] have modelled the dynamic g u a l i t y of storage demands to some extent by breaking t h e i r model of a job i n t o job s t e p s , and g i v i n g each job step" a d i f f e r e n t memory requirement. T h i s i s s t i l l not a complete enough model, however, s i n c e the storage requirement of a job i n a time-sharing environment t h a t a l l o w s dynamic program l o a d i n g and storage a l l o c a t i o n , may vary c o n s i d e r a b l y over a s i n g l e job 6 s t e p . E m p i r i c a l measurements of program storage reguirements over t h e i r running times, and models of these requirements are needed f o r a more thorough understanding of program behavior, and f o r s i m u l a t i o n s t u d i e s . 1.2 D e s c r i p t i o n Of The Michigan Terminal System T h i s d e s c r i p t i o n i s taken i n l a r g e p a r t from M. T. Alexander's paper "Time-sharing s u p e r v i s o r programs." [ 2 ] 1.2.1 The Michigan Terminal System jMTS)_ MTS i s a general purpose t i m e - s h a r i n g system designed f o r the IBM 360/67 computer, and w i l l support up to f o u r p r o c e s s o r s running i n p a r a l l e l . The term MTS i s used t o r e f e r to both the o p e r a t i n g system as a whole, and to a r e - e n t r a n t job program i n the s u p e r v i s o r program, UMMPS, which g i v e s the user the c a p a b i l i t y to run programs and to manipulate f i l e s from remote t e r m i n a l s or from batch. MTS p r o v i d e s : 1) An easy to use command language to cause the running and monitoring of programs and to crea t e , destroy and otherwise manipulate f i l e s . and f o r other communication with the system. 7 2) Two types of f i l e s , s e q u e n t i a l and l i n e f i l e s . L ine f i l e s may be accessed randomly by l i n e number, but s e q u e n t i a l f i l e s can only be accessed s e q u e n t i a l l y . Line f i l e s r e s i d e on disk while s e q u e n t i a l f i l e s may e i t h e r be on di s k or d a t a c e l l . 3) A dynamic program loader which a l l o w s a program to load another during execution. 4) Extensive subroutine l i b r a r i e s and the c a p a b i l i t y to load programs s e l e c t i v e l y from e i t h e r user defined or system l i b r a r i e s to reso l v e undefined e x t e r n a l symbol references i n a loaded object module. 5) Many language processors such as FORTRAN, PL/1, APL, ALGOL, WATFIV etc. Together MTS and UMMPS form an easy to use but powerful time sharing system. \jt2.±2. U n i v e r s i t y Of Michigan Mult iprogrammi ng Supervisor JUMM PS J. The UMMPS supervisor i s a time-sharing s u p e r v i s o r f o r IBS 360/67 supporting up to four processors. I t c o n s i s t s of a set of subroutines f o r processing i n t e r r u p t s , and i s only entered by i n t e r r u p t , e i t h e r hardware, or i n t e r n a l such as c a l l s to the super v i s o r (the 360 SVC i n s t r u c t i o n ) , and the various program 8 i n t e r r u p t s . A l l in terrupts are processed as c lose to completion as poss ib le , and a queue i s maintained for a l l those things that must be postponed. When there i s nothing more to be done at the moment, the supervisor gives contro l to a ready task (if any). DMMPS runs with in terrupts disabled, which means that i t cannot i t s e l f be in terrupted , and also with the re locat ion mechanism turned of f . I t also allows some tasks to ran with re loca t ion turned of f which permits them to reference any r e a l core l o c a t i o n . This a b i l i t y i s r e s t r i c t e d to s p e c i a l tasks such as the Paging Drum Processor (PDP) and tasks c o n t r o l l i n g unit record equipment, which need to be able to reference a l l of main memory. User tasks cannot be given this power, s ince the re loca t ion hardware i s used to provide in ter - task pro tec t ion . J.-2 ..3 Processor Scheduling UMMPS maintains only one CPD queue which a l l the processors scan looking for ava i lab le work. Tasks i n the system can be in one of four states as far as the supervisor i s concerned. 1) Sunning 2) Ready 3) Waiting 4) Page wait A l l tasks which are running or ready and some waiting tasks are on the processor queue, and when the queue i s being scanned, the f i r s t ready task found i s given a processor. A task which uses up i t s time s l i c e (100ms) i s given a new one and placed on 9 t h e b o t t o m o f t h e queue (b u t a h e a d o f any w a i t i n g t a s k s w h i c h a r e on t h e q u e u e ) . T h i s i s t h e o n l y t i m e t h a t a t a s k i s g i v e n a new t i m e s l i c e , A t a s k w h i c h i n i t i a t e s an I/O r e q u e s t o r r e q u e s t s a page n o t i n main s t o r a g e i s n o t r e p l a c e d on t h e p r o c e s s o r q u e u e , b u t when i t becomes r e a d y i t i s a d d e d t o t h e t o p o f t h e queue. Whenever a t a s k i s added t o t h e p r o c e s s o r queue f o r any r e a s o n , i t i s a d d e d t o t h e t o p o f t h e q u e u e . T h i s g i v e s v e r y q u i c k s e r v i c e t o i n t e r r u p t s , and a l l o w s t a s k s w h i c h a r e a c q u i r i n g r e a l s t o r a g e t o do so q u i c k l y . I t i s p o s s i b l e f o r a t a s k t o w a i t f o r some b i t s i n a b y t e i n v i r t u a l s t o r a g e t o become a l l z e r o . T h i s i s u s e d t o a l l o w d i f f e r e n t t a s k s t o c o m m u n i c a t e , and a l s o t o a l l o w t a s k s t o w a i t f o r a s y n c h r o n o u s i n t e r r u p t s . I n t h e l a t t e r c a s e , t h e i n t e r r u p t h a n d l e r s e t s t h e b i t s . When a t a s k w a i t s f o r a b y t e t h a t i s n o t i n i t s p r i v a t e v i r t u a l memory, t h e t a s k r e m a i n s on t h e CPU queue and t h e b y t e i s t e s t e d e a c h t i m e t h e t a s k i s t h e n e x t t o be g i v e n a p r o c e s s o r . I f t h e b i t s a r e z e r o , t h e t a s k g e t s a p r o c e s s o r , i f n o t t h e n e x t t a s k i s e x a m i n e d . The CPU q u e u e i s r e - o r d e r e d s o t h a t a l l s u c h w a i t i n g t a s k s f o l l o w any r e a d y t a s k i n t h e g u e u e . I f t h e b y t e i s i n t h e t a s k s own v i r t u a l s t o r a g e , t h e t a s k i s removed f r o m t h e p r o c e s s o r q u e u e , s i n c e some i n t e r r u p t must o c c u r t o a l l o w t h e b i t s t o be c h a n g e d . The f a c t t h a t a t a s k t h a t q u i t s w a i t i n g i s p l a c e d a t t h e t o p o f t h e p r o c e s s o r queue g i v e s v e r y f a s t s e r v i c e t o i n t e r r u p t s and a l l o w s o r d i n a r y t a s k s t o c o n t r o l I/O e g u i p m e n t . F o r e x a m p l e , t h e PDP i s n o t t r e a t e d s p e c i a l l y as f a r a s s c h e d u l i n g i s c o n c e r n e d , b u t i t c a n e a s i l y keep up w i t h t h e drum 10 i n t e r r u p t s , and such tasks can be given very l a r g e time s l i c e s which w i l l prevent them from being f o r c e d to the end of the processor gueue. In an e f f o r t to prevent too many tasks from competing f o r main storage, UMMPS has a mechanism f o r making c e r t a i n t a s k s p r i v i l e g e d or n o n - p r i v i l e g e d . There are t h e r e f o r e , three c l a s s e s of tasks i n UMMPS: 1) N e u t r a l 2) P r i v i l e g e d 3) N o n - p r i v i l e g e d The term p r i v i l e g e d a p p l i e s only to the amount of processor time t h a t a task g e t s , and the amount of paging that i t i s allowed t o do. When a task i s f i r s t added t o the pro c e s s o r queue, i t i s c l a s s e d n e u t r a l , but i f i t attempts to accumulate more than a c e r t a i n t h r e s h o l d of pages, a d e c i s i o n i s made. I f there are fewer than the maximum allowed number of p r i v i l e g e d tasks, i t i s made p r i v i l e g e d , and i s g i v e n a time s l i c e equal 4*K*U, where K i s the number of a d d i t i o n a l p r i v i l e g e d tasks allowed at th a t poi n t i n time, and U i s the b a s i c time s l i c e . The t o t a l number of p r i v i l e g e d t a s k s allowed i s 7 f o r 1 core box, 12 f o r 2 core boxes, 15 f o r 3 core boxes, 22 f o r 4 core boxes, and 30 f o r more than 4. The d e c i s i o n t h r e s h o l d i s i n i t i a l l y s e t to about 30 pages. (This mechanism i s c u r r e n t l y i n the process of r e v i s i o n . Further i n f o r m a t i o n may be obtained from the U n i v e r s i t y of Michigan Computing C e n t e r ) . The d e c i s i o n t h r e s h o l d f o r the next task i s then lowered, and t h i s one i s allowed t o o b t a i n as many 11 r e a l pages as i t wants. I f there are alre a d y the maximum number of p r i v i l e g e d t a s k s when the d e c i s i o n p o i n t i s reached, the task i s made n o n - p r i v i l e g e d , which removes that task t e m p o r a r i l y from c o n t e n t i o n f o r the CPU's and main storage. A p r i v i l e g e d task remains p r i v i l e g e d u n t i l i t uses up i t s extended time s l i c e or ent e r s the wait s t a t e (except page-wait). At t h i s p o i n t i t i s made n e u t r a l and the d e c i s i o n t h r e s h o l d i s r a i s e d , a l l o w i n g a n o n - p r i v i l e g e d task, i f any, to be made p r i v i l e g e d . Non-p r i v i l e g e d t a s k s are never made n e u t r a l without f i r s t becoming p r i v i l e g e d . Two gueues are a l s o maintained f o r each task, a task CPU queue and a task wait queue. The task CPU queue i s used t o keep t r a c k of m u l t i p l e l e v e l s of execution. Each e n t r y under the top one r e p r e s e n t s a subtask which has been i n t e r r u p t e d but may l a t e r be resumed. Some I/O i n t e r r u p t s cause a new e n t r y t o be added to the top of the CPU queue, and a f t e r t h e i r p r o c e s s i n g the next lower l e v e l resumes p r o c e s s i n g . A wait e n t r y i s maintained i n the wait gueue f o r each l e v e l of the CPU queue at which a wait i s o u t s t a n d i n g . The end of a wait a t any l e v e l can be recorded by removing the wait gueue e n t r y at t h a t l e v e l . S u p e r v i s o r r o u t i n e s e x i s t to remove a l l e n t r i e s from the task CPU gueue but the top one or to remove the top e n t r y . An example of the above i s i l l u s t r a t e d by the f o l l o w i n g s i t u a t i o n . A user i s running a program a t a t e r m i n a l and e n t e r s an a t t e n t i o n i n t e r r u p t . T h i s f o r c e s the saving of s t a t u s a t the i n i t i a l CPU queue l e v e l and a new en t r y t o be added to the top. He may now enter commands at the t e r m i n a l , then he can enter a 12 command to r e s t a r t the program (remove the top e n t r y ) , or he can e l e c t to run another program, which causes the previous e n t r y or e n t r i e s to be removed. As.2j.ii Storage S c h e d u l i n g In MTS, v i r t u a l memory i s implemented u s i n g drum storage d e v i c e s (IBM 2301»s). These drums have 200 t r a c k s and are capable of s t o r i n g 4.5 pages per tr a c k . In order to o b t a i n the best u t i l i z a t i o n of the drums, they are arranged with 100 l o g i c a l t r a c k s having 9 pages each. Two r e v o l u t i o n s of the r e a l drum are needed f o r one r e v o l u t i o n of the l o g i c a l drum. The 9 s l o t s around the circumference of a l o g i c a l t r a c k are c a l l e d s e c t o r s . The task of v i r t u a l memory management i n MTS i s d i v i d e d between UMMPS and a s p e c i a l job c a l l e d the Paging Drum Processor (PDP). The PDP takes care of the a c t u a l reading and w r i t i n g of pages to and from main memory, while i t i s the r e s p o n s i b i l i t y of the s u p e r v i s o r to decide which pages need moving, UMMPS and the PDP communicate v i a Page C o n t r o l Blocks (PCB*s) and there e x i s t s one PCB f o r each v i r t u a l page. Each PCB c o n t a i n s a l l the in f o r m a t i o n concerning the s t a t u s of i t s page, and may be l i n k e d at any time on one of f o u r queues: D Page In Queue (PIQ) co n t a i n s page requests t h a t PDP has not yet the PCB's f o r a l l s t a r t e d r e a d i n g 13 i n . 2) Page In Complete Queue (PICQ) c o n t a i n s the PCB's of a l l pages that the PDP has read or a new page f o r which reading was unnecessary but of which the s u p e r v i s o r has not been n o t i f i e d y e t . 3) Page Out Queue (POQ) c o n t a i n s PCB's f o r a l l pages i n main storage that can be removed. 4) Release Page Queue (RPQ) c o n t a i n s PCB's f o r a l l pages which have been r e l e a s e d by the tasks t h a t own them, but which the PDP has not r e l e a s e d yet (the PDP must be n o t i f i e d so the drum space can be released) . A l l pages t h a t are read i n are immediately placed on the POQ at the top. When the PDP requests some pages to be w r i t t e n , the s u p e r v i s o r checks the amount of f r e e space a v a i l a b l e and i f i t i s s u f f i c i e n t (about 20% of main memory), no pages are given t o the PDP. Otherwise the s u p e r v i s o r s t a r t s scanning the POQ f o r a page t o be w r i t t e n out. I f the page under c o n s i d e r a t i o n i n the scan has been r e f e r e n c e d s i n c e the l a s t scan, the r e f e r e n c e b i t i s r e s e t and the PCB w i l l be placed on the bottom of the POQ. I f the page was not r e f e r e n c e d i t i s given to the PDP f o r w r i t i n g out. T h i s process continues u n t i l enough pages are found f o r the PDP., 14 When a page i s requested by a task, the s u p e r v i s o r places the PCB on the bottom of PIQ and i f the PDP i s not already running, i t i s s t a r t e d . The PDP places the PCB on one of nine s e c t o r queues, corresponding t o the s e c t o r t h a t the page occupies on the l o g i c a l drum, and then requests pages t o be w r i t t e n from the s u p e r v i s o r t o f i l l any of the nine s e c t o r gueues which are empty. I f any of these pages to be wr i t t e n have not been changed s i n c e l a s t w r i t i n g , the s u p e r v i s o r w i l l be n o t i f i e d that the main storage f o r that page i s f r e e and another page i s requested f o r w r i t i n g . When a l l s e c t o r queues are f i l l e d as much as p o s s i b l e , a channel program t o do the readi n g and w r i t i n g i s c o n s t r u c t e d by the PDP and executed. The PDP w i l l then p l a c e the PCB's f o r the pages read on the PICQ and n o t i f y the s u p e r v i s o r that main storage f o r the pages w r i t t e n i s f r e e . The s u p e r v i s o r takes PCB's from the PICQ and pla c e s them on the POQ at the top and r e s t a r t s the tasks i n v o l v e d . The PDP handles the job of c o n s t r u c t i n g new channel programs i n p a r a l l e l with p r o c e s s i n g o l d ones so that the process of readi n g and w r i t i n g i s continuous. Figure 1.1 Flowchart cf storage scheduling 16 Figure 1.1 (b) Flowchart of storage scheduling 17 J * . 2 , 5 General Flow of tasks in MTS at the Univers i ty of B r i t i s h Columbia i s depicted i n f i g , 1 .2 . Both processors scan the s ingle gueue looking for work, and the f i r s t ready task encountered i s given a CPU. A task which i s running on a CPU can subsequently stop for any of the fol lowing reasons: 1) I t requests some I/O 2) It stops to wait for some byte to be set to zero 3) It references a page not i n main storage 4) I t exhausts i t s t ime- s l i c e 5) It i s pre-empted Tasks which are waiting for an i n t e r r u p t to occur, to s i g n a l the end of an I/O operat ion, or the completion of a page transfer are not on the processor gueue, but immediately se ize one of the CPU's when the in terrupt occurs, pre-empting a task that i s current ly running. The pre-empted task i s placed on the top of the queue, and i s the next to receive service provided that another task i s not pre-empted in the i n t e r i m . There are no spec ia l p r i o r i t i e s assigned to any tasks in MTS, so that a l l tasks compete on an equal basis for system resources. Most of the occurrences of stoppages i n processing for the second reason above have to do with terminal I/O for in t erac t ive tasks . In t h i s study, the time that the device support routine (DSB) for the terminal i s entered to get an input l i n e or to write an output l i n e , i s taken as the s tar t of the terminal I/O 18 o p e r a t i o n . The time that an e x i t i s made from the DSR i s taken as the f i n i s h of t h a t o p e r a t i o n , and a l l processor a c t i v i t y f o r that task between i s ignored. In e f f e c t , the en t r y of the DSR i s taken as the beginning of a wait I/O o p e r a t i o n f o r the t e r m i n a l , and the e x i t from the DSR i s taken as the completion of t h a t wait. When a task r e l e a s e s a v i r t u a l memory page, the PDP i s s t a r t e d by the s u p e r v i s o r ( i f i t i s not al r e a d y running) i n order to n o t i f y i t t h a t the drum space may now be used f o r other page w r i t e o p e r a t i o n s . I f the PDP was not running, i t w i l l pre-empt the task t h a t r e l e a s e d the page f o r the time taken t o modify the a p p r o p r i a t e t a b l e s . 1.3 Problem Area T h i s study uses the Data C o l l e c t i o n F a c i l i t y c a l l e d the DCF (continuous monitoring type) a v a i l a b l e i n the MTS o p e r a t i n g system to study the c h a r a c t e r i s t i c s of a t y p i c a l u n i v e r s i t y job stream, the purpose being to allow the pr o d u c t i o n of an accurate model of the job stream f o r s i m u l a t i o n . I t has been p o s s i b l e to measure the times taken f o r many of the events o c c u r i n g i n the system, i n p a r t i c u l a r : 1) The amount of processor time requested by a task when i t o b t a i n s a CPU 2) The amount of processor time that i t a c t u a l l y gets 19 3) The w a i t i n g t i m e s f o r I/O, and pages 4) The i n t e r a r r i v a l t i m e s f o r j o b s i n t o t h e s y s t e m 5) The t o t a l p r o c e s s o r time used by j o b s 6) The s t o r a g e r e g u i r e m e n t s o f j o b s Some s y s t e m d e p e n d e n t c h a r a c t e r i s t i c s (CPtJ t i m e r e q u i r e d t o p r o c e s s i n t e r r u p t s ) have been removed as f a r a s p o s s i b l e from t h e measure o f CPU s e r v i c e r e q u i r e d by j o b s , so t h a t t h i s measure s h o u l d be a p p l i c a b l e on o t h e r s y s t e m s . D a t a was c o l l e c t e d f o r t h e s t u d y on two m a g n e t i c t a p e s , c a l l e d t a p e 1 and t a p e 2, The d a t a on t a p e 1 was c o l l e c t e d on a S a t u r d a y a f t e r n o o n , and r e p r e s e n t s a t i m e o f l i g h t l o a d on t h e s y s t e m , w h i l e t h e d a t a f o r t a p e 2 was c o l l e c t e d on a F r i d a y a f t e r n o o n , which i s a t i m e o f m o d e r a t e l y heavy l o a d . T o g e t h e r t h e t a p e s c o n t a i n d a t a f o r a b o u t 300 j o b s . co •CJ a o o CO I o EH P r o c e s s o r Queue C O CE Job A r r i v a l s A j o b e n t e r i n g the square marked P i m m e d i a t e l y s e i z e s a CPU, p r e -empting the j o b a l r e a d y r u n n i n g i f the CPU was busy* .WAIT I/O) - ^ A P T -1/0^ _ ^ {PAGE WAIT) F i g u r e l . l Flow o f t a s k s i n MTS 21 CHAPTER 2- SOME BASIC CHARACTERISTICS 2s.l Requests For CPU- Se r v i c e In the past, i t has teen d i f f i c u l t to obtain measurements of the time that computer jobs run between successive I/O operations, because of the la c k of appropriate monitoring devices and programs (see [31,33]), but with the development of t o o l s l i k e the DCF i n MTS [ 3 , Appendix A], such measurements may now be r e a d i l y obtained. The amount of processor time that a job requests from the termination of one I/O operation u n t i l the s t a r t of the next, w i l l be c a l l e d a requested CPU i n t e r v a l . Many s i m u l a t i o n s t u d i e s have assumed that the d i s t r i b u t i o n of these i n t e r v a l s i s exponential [33,34,46], or hyper-exponential [ 2 1 ] , since the use of these d i s t r i b u t i o n s a llows easy generation of random samples, and a n a l y t i c methods e x i s t f o r studying systems governed by them. Measurements of requested CPU i n t e r v a l s i n t h i s study show considerably more v a r i a b i l i t y than they would i f they were e x p o n e n t i a l l y d i s t r i b u t e d , and even a hyper-exponential d i s t r i b u t i o n does not provide a cl o s e f i t to the observed d i s t r i b u t i o n s . Requested CPU i n t e r v a l s f o r batch jobs had a mean of 23.6 ms and a standard d e v i a t i o n of 73.6, while i n t e r a c t i v e tasks had a mean of 17.0 ms with a standard d e v i a t i o n of 76.4. A Weibull d i s t r i b u t i o n provided the c l o s e s t f i t f o r the observed i n t e r v a l s f o r batch jobs, and a hyper-exponential d i s t r i b u t i o n f o r those of the i n t e r a c t i v e jobs. (See f i g s . 2.1, and 2.2). The Kolmogorov-Smirnov goodness of f i t t e s t i s 22 used throughout, and gave maximum d e v i a t i o n s f o r the observed values from the f i t t i n g curve of 0.1673 f o r batch jobs, and 0.0802 f o r i n t e r a c t i v e jobs. The p r o b a b i l i t y of f i n d i n g a d e v i a t i o n as l a r g e as 0.0200 (batch) or 0.0119 ( i n t e r a c t i v e ) f o r samples t h i s l a r g e i s l e s s than 1% i f the f i t i s t o be cons i d e r e d good. T h i s value w i l l be r e f e r r e d t o i n f u t u r e as KS (.01) . The Weibull d i s t r i b u t i o n i s u s e f u l f o r f i t t i n g sample d i s t r i b u t i o n s of t h i s type (with the a p p r o p r i a t e c h o i c e of parameters), s i n c e one can o b t a i n a d i s t r i b u t i o n with more very l a r g e v a l u es, and more very s m a l l values than with a hyper-e x p o n e n t i a l d i s t r i b u t i o n having the same mean and standard d e v i a t i o n . The problem with using the Weibull d i s t r i b u t i o n , however, comes i n choosing the parameters. (See Appendix B f o r d e t a i l s ) . The CPU time reguested by i n t e r a c t i v e jobs between t e r m i n a l I/O o p e r a t i o n s i s l a r g e r than the requested CP0 i n t e r v a l s on the average s i n c e s e v e r a l i n s t a n c e s o f d i s k or tape I/O may occur between s u c c e s s i v e t e r m i n a l o p e r a t i o n s . The mean observed time was 58.6 ms with a standard d e v i a t i o n of 669, and a Weibull d i s t r i b u t i o n gave the c l o s e s t f i t with a maximum d e v i a t i o n of 0.0942. (KS (.01) =0.0211) (see f i g . 2.3) The Weibull d i s t r i b u t i o n f i t t e d by the method d e s c r i b e d i n Appendix B had a mean of 27 ms, and a standard d e v i a t i o n of 48 which are much l e s s than the observed values f o r the mean and standard d e v i a t i o n , however, the observed d i s t r i b u t i o n had a few very l a r g e sample val u e s (as gre a t as 30 seconds of CPU time), which 20.0 . 60.0 TINE 20.0 120.0 150.0 Figure 2.1 Requested CPU i n t e r v a l s (interactive) V .0 30.0 60.0 . 20.0 120.0 T I M E Figure 2.2 Requested CPU i n t e r v a l s (batch) 150.0 made the mean and standard d e v i a t i o n l a r g e . Such lar g e samples are very r a r e . Scherr [43] found a s i m i l a r shaped d i s t r i b u t i o n f o r these times, with a mean of 0.88 seconds f o r jobs run on an IBM 7094 running CTSS. Q TIME Figure 2.3 Processor time between i n t e r a c t i o n s 25 2-2 CPU S e r v i c e Obtained The amount of time that a job a c t u a l l y gets on a processor i n one shot, c a l l e d an a c t u a l CPU i n t e r v a l * . i - s c o n s i d e r a b l y l e s s than i t r e q u e s t s , s i n c e the maximum time that a job may hold a CPU i s l i m i t e d by i t s time s l i c e , and a job has a high p r o b a b i l i t y of being pre-empted i f there are more than a few other jobs i n the system. Means f o r the CPU s e r v i c e obtained ( a c t u a l CPU i n t e r v a l s were 14.3 ms f o r jobs on tape 1, and 8.9 ms f o r jobs on tape 2 with standard d e v i a t i o n s of 42.5 and 14.9 r e s p e c t i v e l y . The average a c t u a l CPU i n t e r v a l s on tape 1 r e p r e s e n t about 80% of the requested i n t e r v a l s , while those on tape 2 r e p r e s e n t only about 45%. The reason f o r t h i s d i f f e r e n c e i s t h a t tape 2 r e c o r d s a c t i v i t y a t a b u s i e r time than tape 1, and jobs are pre-empted more f r e q u e n t l y when the system i s busy. A hyper-exponential d i s t r i b u t i o n p r o v i d e s the c l o s e s t f i t f o r these v a l u e s , and the observed data show a maximum d e v i a t i o n of 0.0900 (KS (.01)=0.0111) from the f i t t i n g curve f o r tape 1, and a maximum d e v i a t i o n of 0.027 f o r tape 2. (See f i g s . 2.4 and 2.5). 26 Figure' 2.5 . Actual.CPU intervals (tape 2) 27 .2.J I/O Delays In MTS, the pro c e s s i n g of a job i s not overlapped with i t s own I/O, and as a r e s u l t , the job must remain i d l e d u r i n g these times. Most of the I/O a c t i v i t y of MTS jobs i s f o r disk o p e r a t i o n s , with some f o r tape I/O. For i n t e r a c t i v e jobs, some of the I/O i s a l s o f o r the t e r m i n a l on which the job i s run. The d i s t r i b u t i o n s of I/O delays f o r both i n t e r a c t i v e and batch t a s k s (excluding the de l a y s f o r the t e r m i n a l i t s e l f ) are q u i t e s i m i l a r , ( f i g s . 2.6, and 2.7) and a l s o ressemble c l o s e l y the d i s t r i b u t i o n f o r d i s k I/O delays measured by Baskett et a l [ 5 ] f o r the U n i v e r s i t y of Texas' CDC 6600 system. The peaks are c l o s e to the same p o i n t ( 35 ms), and the shapes of the d i s t r i b u t i o n s are s i m i l a r . The reason f o r the d i f f e r e n c e i n means f o r the batch and i n t e r a c t i v e tasks i s probably due t o the f a c t t h a t much more d i s k arm movement i s r e q u i r e d f o r the i n t e r a c t i v e t a s k s , s i n c e f a i r l y long p e r i o d s can be spent w a i t i n g f o r t e r m i n a l responses during which time the arm can be r e p o s i t i o n e d by another t a s k . The peak observed i n f i g , 2.3 at 80 ms i s due to s e v e r a l jobs i n the sample doing tape I/O. 80ms i s the time taken to t r a n s f e r a tape record one page i n l e n g t h , and t h i s i s a very common s i z e used i n the MTS system. Most disk o p e r a t i o n s take between 25 and 75 ms (from P i n k e r t o n [ 3 9 ] ) , with those r e q u i r i n g arm movements t a k i n g l o n g e r . Although these d i s t r i b u t i o n s look E r l a n g i a n , the standard o . o a o . o . i s o . o 2^0.0 320.0 4 0 0 . 0 T I M E Figure 2 .7 I/O delays (interactive) 29 d e v i a t i o n s are g r e a t e r than the means. For batch t a s k s , the observed mean was 38 ms with a standard d e v i a t i o n of 67, and f o r i n t e r a c t i v e t a s k s , the mean was 123 ms with a standard d e v i a t i o n of 986. The dotted l i n e s i n f i g s . 2.6 and 2.7 show the Weibull d e n s i t y f u n c t i o n g i v i n g the c l o s e s t f i t a c c o r d i n g to the Kolmogorov-Smirnov goodness of f i t t e s t . Greater values of (causing the peak t o be s h i f t e d r i g h t ) y i e l d e d l a r g e r d e v i a t i o n s from the cummulative d i s t r i b u t i o n than the curves p l o t t e d . The term "U§§r Response Time^ r e f e r s to the time that i t takes a user at an i n t e r a c t i v e t e r m i n a l to frame h i s response and to type i t i n . I t i s measured from the time t h a t the system s t a r t s w a i t i n g f o r some a c t i o n from the user, u n t i l the user e n t e r s a c a r r i a g e r e t u r n or other end of l i n e s i g n a l i n d i c a t i n g t h a t he has f i n i s h e d h i s response. Scherr [43] c a l l s these times "Think Times". The d i s t r i b u t i o n of user response times f o r i n t e r a c t i v e t a s k s w i l l vary from system t o system, depending on the type of response r e g u i r e d , the dev i c e s used, and the s o p h i s t i c a t i o n of the users. Scherr found the mean user response time t o be 35 seconds f o r users of the CTSS sytem, but f o r MTS users the mean i s c l o s e r to 11 seconds with a standard d e v i a t i o n of 16. The d i s t r i b u t i o n of these times was s i m i l a r i n shape to th a t observed by Scherr, i f one removes the program generated responses from h i s o b s e r v a t i o n s . I t i s a l s o s i m i l a r t o the d i s t r i b u t i o n observed by Schwetman and DeLine [ 4 4 ] f o r the RESPOND system. A Weibull d i s t r i b u t i o n again showed the c l o s e s t f i t ( f i g . 30 2.8) and the observed data d i s p l a y e d a maximum d e v i a t i o n of 0.0655 from i t with KS (. 0 1) =0 .05. The d i s t r i b u t i o n i n the f i g u r e may be seen to have two l a r g e peaks. The f i r s t corresponds t o quick responses r e q u i r i n g l i t t l e thought on the part of the user, and a l s o l i t t l e t y p i n g . Such responses are g u i t e common i n MTS with the user e n t e r i n g a n u l l l i n e , or one with only a few c h a r a c t e r s i n r e p l y to some query on the part of the system. The second peak r e p r e s e n t s those responses r e g u i r i n g some thought, or c o n s i d e r a b l e t y p i n g , or both. The number of responses f a l l i n g i n t o the f i r s t category ( l e s s than 5 seconds) i s roughly 35% of the t o t a l . The system responds by ty p i n g a r e p l y which takes an average of 0.65 seconds ( f i g . 2.9) and writes about f i v e times as many l i n e s as the user i n p u t s . The peaks i n the d i s t r i b u t i o n correspond to d i f f e r e n t d e v i c e s . F i g u r e 2.9 System w r i t e t i m e s ( i n t e r a c t i v e ) 32 2J± Page Waiting Times The d i s t r i b u t i o n of page waiting times i s divided into several types of events i n MTS, depending on the reason for the page f a u l t that generated the request, and the status of the page involved. The p o s s i b i l i t i e s are outlined below: 1) Page f a u l t was for the f i r s t reference to a new page, which can be allocated nearly immediately. 2) Page f a u l t was for the f i r s t reference to a new page, but core space can be allocated only aft e r f i r s t writing out another page to provide space. 3) Page f a u l t was for a page exis t i n g on the drum, which must be brought into core. 4) Page f a u l t was for a page existing on the drum, but i t can only be brought into core after f i r s t writing out another page. 5) Page f a u l t was for a page that s t i l l exists in core, although a page out operation was in progress for that page. The page out operation can be cancelled, and the page w i l l become available immediately. Since MTS t r i e s to keep about 20% of the available core space empty to allow guick service to page reads, situations of 33 type 2, or 4 above occur o n l y r a r e l y . In a d d i t i o n to the f i v e types of events above, the s u p e r v i s o r may decide to make a task n o n - p r i v i l e g e d (see sec. 1,2.3) i f i t attempts to o b t a i n more than a c e r t a i n t h r e s h o l d of r e a l pages. The job must then wait f o r some other p r i v i l e g e d job t o leave t h a t s t a t u s before i t can be made p r i v i l e g e d , and have i t s page request s e r v i c e d . T h i s has the e f f e c t of making some page waits very l o n g . Events of t h i s type are e a s i l y separated from the r e s t by the l a r g e d i f f e r e n c e i n magnitude. Because of the v a r i o u s types of events making up the d i s t r i b u t i o n of page w a i t i n g times, no one f u n c t i o n can be made to f i t the observed data very c l o s e l y . I f one breaks the d i s t r i b u t i o n i n t o part corresponding to the events of d i f f e r e n t t y pes, however, a reasonable f i t can be obtained. (See f i g s . 2.10, 2.11, and f i g . 2.12). In t h i s case, the d i s t r i b u t i o n was broken i n t o two p a r t s , the f i r s t corresponding to events of types 1, and 5 above, and the second to events of type 3. An e x p o n e n t i a l d i s t r i b u t i o n with a mean of 1ms was used to f i t the d i s t r i b u t i o n of events of types 1, and 5, and an E r l a n g d i s t r i b u t i o n with a mean of 22 ms and 6 channels was used t o f i t the events of type 3. T h i s g i v e s a f a i r f i t to the observed data, which shows a maximum d e v i a t i o n of 0.1453 with KS (.01)=0.0591. The p r o b a b i l i t y d e n s i t y f u n c t i o n f o r the r e s u l t i n g d i s t r i b u t i o n i s seen i n f i g . 2. 12. 34 04 O >-CD 0.0 50.D 100-O 150-0 200.0 250.0 T I M E F i g u r e 2.10 Page w a i t i n g times (tape 1) 2.5 Other Parameters Of I n t e r e s t 2*5.. 1- System Response- Time System response time i s d e f i n e d as the time that i t takes the system to s t a r t to type a response, a f t e r a user has entered h i s c a r r i a g e r e t u r n s i g n a l at an i n t e r a c t i v e t e r m i n a l . T h i s g u a n t i t y i s of i n t e r e s t , as i t i s o f t e n used as a c r i t e r i o n f o r judging the performance of t i m e - s h a r i n g systems. The d i s t r i b u t i o n observed had a mean of 0.42 seconds, with a standard d e v i a t i o n of 2. (see f i g . 2.13) The median was only 35 1Q0.Q T I M E 150.0 200.0 250.0 Figure 2.11 Page waiting times (tape 2) 36 30 ms. a Weibull d i s t r i b u t i o n gave the c l o s e s t f i t , and the observed values showed a maximum d e v i a t i o n of 0 .070 from i t , with KS (.01)=0.05. The d i s t r i b u t i o n i s s i m i l a r i n shape t o the one o b t a i n e d by Scherr [ 4 3 ] , although the mean i s an order of observed by Schwetman and DeLine [ 4 4 ] f o r the RESPOND system, although the mean time i s s i m i l a r i n t h i s i n s t a n c e . The RESPOND system seems t o make almost no very quick responses. Looking at the d i s t r i b u t i o n of proc e s s o r time r e q u i r e d between i n t e r a c t i o n s , one would expect very quick responses s i n c e so l i t t l e time i s used i n most cases ( l e s s than 55 ms), and the mean time f o r d i s k o p e r a t i o n s i f they are r e q u i r e d i s sm a l l ( l e s s than 100 ms). magnitude l e s s . I t i s q u i t e d i f f e r e n t i n shape to the one o 50.0 75.0 )0O0 \?S.O 0.0 25.0 Tine t x IO 1 ) F i g u r e 2 .13 System reponse time 37 2.5.2 Ready I n t e r v a l s Beady i n t e r v a l s are def i n e d as the i n t e r v a l s of time that t a s k s which could be running on a CPU spend w a i t i n g on the processor gueue. These i n c l u d e tasks which have used up t h e i r t i m e - s l i c e s and are placed on the bottom of the gueue, and ta s k s which have been pre-empted and are placed on the top. The mean value f o r ready i n t e r v a l s i s very s m a l l s i n c e a l a r g e p o r t i o n of the i n t e r v a l s r epresent pre-empted tasks w a i t i n g f o r some i n t e r r u p t to be processed, and so w i l l o b t a i n CPU s e r v i c e again i n a r e l a t i v e l y s h o r t time, s i n c e most i n t e r r u p t s are processed i n 200 - 300 us. I t i s a l s o u n l i k e l y (at UBC) t h a t many ta s k s w i l l be stacked i n such a manner that each i s waiting f o r the prev i o u s task t o f i n i s h p r o c e s s i n g some i n t e r r u p t . P r o c e s s i n g of i n t e r r u p t s has been removed from the d i s t r i b u t i o n of a c t u a l CPU i n t e r v a l s , so the mean of the a c t u a l i n t e r v a l s i s l a r g e r than i t would be i f these were i n c l u d e d . I t i s f o r t h i s reason t h a t the mean of the ready i n t e r v a l s i s so s m a l l compared t o the mean of the a c t u a l CPU i n t e r v a l s . (See f i g s . 2.14 and 2.15 f o r d i s t r i b u t i o n s of ready i n t e r v a l s ) . 2.5.3 I n t e r - A r r i v a l Times The i n t e r - a r r i v a l times of jobs to the system i s the time between s u c c e s s i v e "SIGNON's", not the time between submissions of jobs to the HASP gueue. For t e r m i n a l j o b s , the act of s i g n i n g on puts the job immediately i n t o the system, but f o r batch jobs the case i s d i f f e r e n t . Batch jobs are enqueued by HASP, and ordered a c c o r d i n g t o an assigned p r i o r i t y which i s ° 1 I m C O i I i i 60.0 SO.O F i g u r e 2 .1h Ready i n t e r v a l s (tape 1) C O 0.0 20.0 T I M E SO.O 80.0 F i g u r e 2.15. Ready i n t e r v a l s .(tape 2) 39 c a l c u l a t e d from the user's estimates of CPU time, and pages of output r e q u i r e d f o r the job. Jobs are released from the gueue f o r execution at a r a t e that i s dependent on the system load. Only two batch jobs are permitted i f there are many t e r m i n a l users signed on. The time that a batch job a c t u a l l y leaves the gueue and s t a r t s executing i s deemed i t s a r r i v a l time. The i n t e r - a r r i v a l times f o r t e r m i n a l jobs were found 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 as expected, and the same was found to be true f o r batch jobs. The mean i n t e r - a r r i v a l time f o r batch jobs was 40 seconds, and was 94 seconds f o r the t e r m i n a l jobs. More accurate values f o r i n t e r - a r r i v a l times could be obtained by examining the system accounting records. T o t a l Processor- Time Processing time r e g u i r e d by jobs i s the t o t a l amount of CPU time reguired t o complete the job. This q u a n t i t y was found to be hyper-exponentially d i s t r i b u t e d with a mean of 16 seconds, and a standard d e v i a t i o n of 28, based on a sample of 136 jobs drawn from the data tapes. Again more accurate values could be obtained by examining the accounting s t a t i s t i c s s ince a much l a r g e r sample could be used. UO Tape • 1 1 Tape 2 Terminal Batch | j Terminal J Batch Requested CPU int e r v a l s 18 .1 ms (87.6) 2U.1 ms ( 319^ lh.9 ms ' . ( U6 . U ) ' 2 3 . 2 ms ' ( 2 1 3 ) Actual CPU Intervals 12.9 ms ( 3 7 . 6 ) 19.U ms (60.1) . 6 . 0 ms | (1U.1) 1 0 . 1 ms (16.1) I/O Delays 1 5 0 . 2 ms ( 1 2 0 3 ) 30.1 ms ( 3 1 . 9 ) 1 76.1 ms ( 3 8 1 ) U2.2 ms (82 .3 ) User Response 1 0 . h sec (lh.9) • | 12.1 sec j (17.7) System Write O.hli sec ( 1 . 9 0 ) | 0 . 5 7 sec ( 1 . 6 7 ) System Response 0.39 sec (2 . 0 1 ) ' •0.U7 sec • (2 . 1 U ) . CPU Time Between Interactions 59-9 ms (719) 55 .8 ms ( 5 3 5 ) Page Waits 22.5 ms (22 .0 ) 22.2 ms (22 .U) . j 25.7 ms (20.7) 2U.1 ms (15.U) Ready Intervals 3.7 ms (11.4) • 3-9 ms (li t . 8) ' • 6 .U ms ' (15.U) • 7 . 0 ms (17 .5) No. Concurrent Tasks 1~2 j — 1 9 2 - 3 I n t e r - a r r i v a l Times 9 U sec <*> | U 0 sec (111) Bracketted numbers are standard deviations. Table 2.1 Job stream cha r a c t e r i s t i c s 41 CHAPTER 3 STORAGE REQUIREMENTS 3*. I Preamble In a time-sharing environment, there i s u s u a l l y i n s u f f i c i e n t core storage a v a i l a b l e to allow a l l users to have t h e i r f u l l a l l o t m e n t of s t o r a g e i n core s i m u l t a n e o u s l y . Schemes of v i r t u a l memory management have been developed [1,3,15,17,18] which t r y to g i v e each user only as much core as he needs at the moment, while the remainder of h i s a l l o t t e d memory space r e s i d e s on some secondary storage device such as a drum. The memory i s normally grouped i n t o b l o c k s c a l l e d pages, which are the u n i t s of storage t r a n s f e r r e d between core storage and the drum. A page i s brought i n t o core memory when a r e f e r e n c e i s made to i t , and pages t h a t are i n core f o r a long time, or have not been r e f e r e n c e d i n a long time, are placed on the drum to make more core storage a v a i l a b l e . Even with the l a r g e amounts of v i r t u a l storage that e x i s t i n such systems, each user cannot simply be a l l o c a t e d as much storage space as he might p o s s i b l y r e g u i r e , and be allowed to keep a l l t h i s space f o r the d u r a t i o n of h i s time on the system. In t h i s i n s t a n c e , most of the storage would be unused at any moment and poor u t i l i z a t i o n of the hardware would r e s u l t . In a d d i t i o n , a r e s t r i c t i o n would have to be placed on the number of simultaneous users which would depend on the t o t a l amount of storage a v a i l a b l e . To overcome t h i s problem, methods of dynamic storage a l l o c a t i o n have been d e v i s e d that allow jobs to a c q u i r e s t o r a g e as they need i t , and to r e l e a s e t h a t storage as soon as the need disappears. T h i s process i s t r a n s p a r e n t to the user i n most 42 cases, so that when he runs a program, the c o r r e c t amount of storage i s a u t o m a t i c a l l y acquired, and then released when the program terminates. Most systems provide the user with the c a p a b i l i t y of w r i t i n g programs that acquire storage during execution (see [ 2 5 ] ) , e i t h e r to load a d d i t i o n a l program modules, or to increase the s i z e of data areas, and t h i s storage may be re t a i n e d or released as the program w r i t e r sees f i t u n t i l the program terminates. Since the storage requirement of jobs i s a dynamic gu a n t i t y , any s i m u l a t i o n which s t u d i e s the u t i l i z a t i o n of v i r t u a l memory, must incorporate a model f o r the storage demands of jobs. Most s t u d i e s , however, have concerned themselves with paging behavior (such as times between inter-page references, and sequences of references, e t c . See [1,13,22]), and r e a l core requirements f o r e f f i c i e n t running [8,16,29], rather than the v a r i a b i l i t y of storage reguirements with time, s i n c e the concern was mostly the f e a s i b i l i t y of paging algorithms, and paging machines i n general. Lehman and Rosenfeld [31] broke t h e i r model of a job i n t o job steps, g i v i n g each step a d i f f e r e n t storage allotment. This comes c l o s e s t to modelling the v a r i a b l e nature of storage requirements. Denning [16] developed a model fo r the r e a l core demands of computer jobs, which he c a l l s the working set model. 3,2 Observed Program Storage Requirements a storage p r o f i l e i s a p l o t of the storage reguirements of 4 3 a j o b o v e r i t s r u n n i n g t i m e ( S e e r i g . , 3 . 1 , a n a A p p e n d i x D f o r e x a m p l e s ) . A n u m b e r o f t h e s e p r o f i l e s w e r e c o l l e c t e d , a n d ' d e s c r i p t i v e p a r a m e t e r s f o r e a c h w e r e m e a s u r e d . 'The t i m e s c a l e was n o r m a l i z e d t o make a l l t h e p r o f i l e s t h e same l e n g t h f o r c o m p a r i s o n - p u r p o s e s . T h e p a r a m e t e r s m e a s u r e d w e r e t h e j t a x i m u m number 0£ p a q e s , the icaan number o f p a g e s , the number o f d i s t i n c t humps (a hump i s a n a r e a o f t h e p r o f i l e w h e r e t h e n u m b e r , o f p a q e s p o s s e s s e d e x c e e d s a n a r b i t r a r y s m a l l l i m i t , 15 p a g e s i n t h i s c a s e ) , t h e w i d t h o f t h e l a r g e s t hump, t h e n u m b e r o f c h a n g e s i n s t o r a g e r e q u i r e m e n t , t h e a v e r a g e s i z e o f t h e s e c h a n q e s a s a p e r c e n t o f t h e maximum n u m b e r o f p a g e s , , a n d t h e s i z e o f t h e maximum i n c r e a s e a n d d e c r e a s e i n s t o r a g e r e q u i r e m e n t a s a p e r c e n t o f t h e maximum n u m b e r o f p a y e s . CO ; CD o e Cd 0.0 o O J w S max width---! i V T r hump 1 hump 2 i . 1 ; ™ 0.2 .0.4 0.6 Normalized Time 0.8 JI i T 1.0 F i g u r e 3.1 - T y p i c a l s t o r a g e p r o f i l e w i t h m e a s u r e d p a r a m e t e r s . U s i n g t h e p a r a m e t e r s m e a s u r e d f o r e a c h p r o f i l e a s a v e c t o r d e f i n i n g t h e p o s i t i o n o f t h e p r o f i l e i n a n e i g h t d i m e n s i o n a l E u c l i d i a n s p a c e ( e i g h t ' p a r a m e t e r s ) , a n d d o i n g some c l u s t e r 44 a n a l y s i s [45] the p r o f i l e s were found to f a l l i n t o two c l u s t e r s . P r o f i l e s from the f i r s t group showed l a r g e maximum sto r a g e requirements, and u s u a l l y had one l a r g e hump c o v e r i n g most of the running time. The average maximum number of pages f o r t h i s group was 70 pages, and the average s i z e of change i n storage reguirement was 6.5 pages. (See f i g s . D.1 through D.8.) P r o f i l e s from the second group had an average maximum number of pages of 23, and the average s i z e of change was 4.1 pages. Most of the p r o f i l e s i n t h i s group show a g r e a t amount of f l u c t u a t i o n i n the storage possessed (see f i g s . D. 9 through D.20). about 50% of the batch jobs examined had storage p r o f i l e s f a l l i n g i n t o the f i r s t group, while only 25% of the i n t e r a c t i v e jobs had s i m i l a r requirements. At the U n i v e r s i t y of B r i t i s h Columbia, the MTS user i s charged f o r storage used during i n a c t i v e p e r i o d s when he i s signed on at an i n t e r a c t i v e t e r m i n a l , but not i f h i s job i s run from batch. T h i s makes programs with l a r g e s t o r a g e requirements c o s t l y to run i n t e r a c t i v e l y , and probably accounts f o r the lower p r o p o r t i o n of i n t e r a c t i v e jobs having p r o f i l e s i n the f i r s t group. 3.3 A Model Tor Program Storage Requirements Since i t would be d e s i r a b l e to generate storage reguirement p r o f i l e s f o r computer jobs f o r s i m u l a t i o n purposes, a model was developed to do t h i s . The model used i s very simple i n p r i n c i p l e , but seems to generate p r o f i l e s q u i t e s i m i l a r t o the ones observed (see Appendix D, and Table 3 . 1 ) . 45 a) 10 20 30 ko Percent of maximum number of pages Increases, i n storage allotment b) 10 20 30 kO 50 Percent of maximum number of pages Decreases i n storage allotment -r 10 20 30 ko Percent of normalized time 50 c) Time storage allotment remained s t a t i c Figure 3.2 Dis t r i b u t i o n s f o r storage p r o f i l e model (grp 1) o c .j O r-i -p OCX). a fe vO. 0) a > •H • P J " . c3 • H 3 a CM. a • o a) 10 20 30 '1*0 , 50 Percent of maximum number of pages Increases i n storage allotment b) 10 20 30 ko 50 Percent of maximum number of pages Decreases i n storage allotment 10 20 30 kO Percent of normalized time 50 c) Time storage allotment remained s t a t i c Figure 3.3 Dist r i b u t i o n s f o r storage p r o f i l e model (grp 2) 47 A s e t of d i s t r i b u t i o n s was determined f o r the s i z e s of i n c r e a s e s and decreases i n the amount of storage possessed f o r each category (see f i g s . 3.2 and 3.3), and a l s o a d i s t r i b u t i o n f o r the l e n g t h s of time t h a t the number of pages remained s t a t i c . C o n d i t i o n a l p r o b a b i l i t i e s f o r the d i r e c t i o n of the next change i n the number of pages (up or down), given the d i r e c t i o n of the l a s t change, were measured from the observed storage p r o f i l e s . By drawing random numbers from the above d i s t r i b u t i o n s , and f o r c i n g an i n c r e a s e to the maximum storage s i z e a t some p o i n t , i t i s p o s s i b l e to generate very reasonable storage p r o f i l e s . A comparison i s found i n Table 3.1 I t i s p o s s i b l e that a much more e l a b o r a t e model co u l d be devised, but because of the extreme v a r i a b i l i t y of jobs run on t h i s system, i t i s u n l i k e l y t h a t much b e t t e r p r o f i l e s c o u l d be obta ined. A f l o w c h a r t d e s c r i b i n g the model appears i n f i g u r e 3.4. M8 Determine i f p r o f i l e i s c l a s s ] o r ? Stop Determine the s i z e O J increase Determine point to forc e climb to tfaxirau:?: I Determine point of d e c l i n e i n storage demand •Determine time to- the next change Set # of pages equal, * i to minimum Determine the s i z e of s decrease Determine time to the; N^next change: Figure 3.U- Flowchart of storage p r o f i l e model Maximum Mean tf tf humps Max % Max % tf o f Maximum Mean % tf pages pages x 10 i n c r e a s e d e c r e a s e changes w i d t h change Group 1 23.17 1 0 . 5 9 14 . 1 7 2 8 . 9 5 4 9 . 9 2 2 1 . 0 0 17.42 1 7 . 6 1 Observed Group 2 7 0 . 4 3 42 . 8 4 11 .43 3 5 . 5 5 5 5 . 7 3 25.14 7 4 . 0 0 9 .27 Group 1 23 .17 11 .72 1 5 . 0 0 3 2 . 3 1 6 1 . 6 6 1 7 . 0 9 2 1 . 5 0 1 8 . 6 6 Generated Group 2 7 0 . 4 3 34.42 1 0 . 9 1 36.22 5 7 . 2 5 2 6 . 8 8 6 9 . 3 1 10 . 7 3 T a b l e 3*1 Comparison o f observed p r o f i l e s , and t h o s e g e n e r a t e d by the model. 50 CHAPTER-U SUMMARY AND DISCUSSION ii-s.1 Summary And Discussion I t was found i n s e c t i o n 2.1 that the requested CPU i n t e r v a l s f o r batch jobs were about 30% longer on the average than those f o r i n t e r a c t i v e jobs, and that these i n t e r v a l s have standard d e v i a t i o n s about four times as large as t h e i r means. E i t h e r a hyper-exponential or a W e i b u l l d i s t r i b u t i o n can be used as a model f o r the i n t e r v a l s , with the hyper-exponential d i s t r i b u t i o n being the e a s i e s t to use, as i t i s much e a s i e r to generate parameters that g i v e the d e s i r e d mean and variance. The r e l a t i o n s h i p between the d i s t r i b u t i o n parameters, and the mean and variance f o r the Weibull d i s t r i b u t i o n i s very complex, (see Appendix B) and no s t r a i g h t forward s o l u t i o n e x i s t s to determine the parameters from them. The processor time r e q u i r e d by i n t e r a c t i v e t a s k s , i s broken up i n t o reguested CPU i n t e r v a l s , with disk or tape I/O operations terminating a l l but the l a s t of these i n t e r v a l s , which i s terminated by a te r m i n a l I/O operation. The Weibull d i s t r i b u t i o n g i v e s the c l o s e s t f i t according to the Kolmogorov-Smirnov goodness of f i t t e s t , has a mean and standard d e v i a t i o n much l e s s than those observed due to a few very large values i n the observed d i s t r i b u t i o n . A s h i f t e d Weibull d i s t r i b u t i o n (one with the 2f parameter greater than zero) provides a f a i r l y good f i t to the observed d i s t r i b u t i o n of user response times, but f o r the d i s t r i b u t i o n of times that i t takes the system to write l i n e s no d i s t r i b u t i o n f u n c t i o n was found to provide a reasonable f i t . I t would probably be a good idea to break t h i s d i s t r i b u t i o n up according 51 to the various types of devices i n v o l v e d , and to determine a d i s t r i b u t i o n of w r i t e times f o r each one. A Weibull d i s t r i b u t i o n with a s h i f t can be used to model disk I/O del a y s , but the f i t obtained i s not a good one. The d i s t r i b u t i o n of page waiting times f o r the MTS system, i s best broken up i n t o two cat e g o r i e s i f one wants to generate page t r a n s f e r delays with a d i s t r i b u t i o n s i m i l a r to the ones observed. An exponential d i s t r i b u t i o n models the delays that do not require a t r a n s f e r of a page from the drum, and the t r a d i t i o n a l Erlang d i s t r i b u t i o n can be used to model those delays that do. D i s t r i b u t i o n s of system response time, and a c t u a l CPU i n t e r v a l s can be used to check the accuracy of s i m u l a t i o n models t e s t e d . In the area of program storage requirements, more work might be p r o f i t a b l e . For s i m u l a t i o n models, the r e l a t i o n s h i p between v i r t u a l storage allotment and the amount of r e a l core needed would be u s e f u l , as w e l l as r e l a t i o n s h i p s between amount of r e a l core, the number of simultaneous users, and the amount of paging done. The model developed i n s e c t i o n 3.3 f o r v i r t u a l storage requirements of jobs i s only a beginning i n t h i s d i r e c t i o n . H.2 A Simple Model Of MTS For Simulation The f o l l o w i n g simple s i m u l a t i o n model of MTS could be used to employ some of the measures taken i n t h i s study. The model 52 keeps three l i s t s o u t l i n e d below: 1) Job L i s t Each entry on the job l i s t c o n t a i n s a l l the informati o n concerning a p a r t i c u l a r job running on the simulated system, and i n c l u d e s these f i e l d s : TC maximum CPU time f o r the job TE current t o t a l CPU time f o r the job TR time remaining i n the c u r r e n t reguest f o r CPU s e r v i c e TRTS time remaining i n the t i m e - s l i c e NB the reason the job w i l l stop at the end of the curren t requested CPU i n t e r v a l Various other f i e l d s can be used to keep track of s t a t i s t i c s of i n t e r e s t such as the cu r r e n t number of r e a l pages, the cumulative wait time, e t c . 2) CPU Queue This l i s t i s l i n k e d with the f i r s t entry p o i n t i n g to the next, e t c . Each entry contains only a pointer to the job l i s t , and the l i n k to the next ent r y , with the p o s i t i o n of the entry i n d i c a t i n g the p o s i t i o n of the corresponding job i n the simulated CPU gueue. 53 3) Event L i s t This l i s t i s a l s o l i n k e d , and ordered according to the times of the events represented. Events i n t h i s l i s t w i l l cause the pre-emption of a job that i s running on a CPU i f any job i s running at the time of the event. Each entry contains a p o i n t e r to the job l i s t i n d i c a t i n g the job a s s o c i a t e d with the event, an i n d i c a t i o n of the event type, and a l i n k to the next entry i n the l i s t . In a d d i t i o n the model keeps the current time T. A flowchart of the model appears i n f i g . 4 . 1 . The value i i n d i c a t e s the job c u r r e n t l y i n possession of a CPU. (note: the model i s shown f o r o n l y one CPU since others are i d e n t i c a l ) Tr i s the running time before stopping f o r the job c u r r e n t l y on the CPU, and Tn i s the time of the next event from the event l i s t . Tev i s the time c a l c u l a t e d f o r an event to occur. 5* T i l Tev p o i n t e r to job l i s t ( c u r r e n t job) .current time running time before s t o p p i n g f o r job i time of next, event time c a l c u l a t e d f o r an event t o occur St? V? S'Generate i n i t i a l : j; parameters f o r [ a l l jobs i n the jj system a t the j s t a r t I Order a l l the | I jobs on the I CPU queue iOB LIST TC TRTS NB maximum CPU time c u r r e n t t o t a l CPU time time remaining .in c u r r e n t r e q uest f o r s e r v i c e time remaining i n time--s l i c e reason job w i l l stop a t the end of the c u r r e n t request i-. job if j o f . t h e job | on the top of the aueue f I Generate time I of next a r r i v a l ! f o r the event l i s t La-i X T r min (TRj_, TRTS ± ] F i g u r e ^ . I Flowchart f o r a model of MTS (see over) i I Job s t o p s f o r i / 0 o r a page • f a u l t Figure A . l (b) Flowchart f o r a' model of MTS -'(see over) .^y- THj_-TRTS j_ T RTSi new t i m e - s l i c e ? i m e - s l i c e runs out TRTS-? <- TRTS-i J O D 1 pre-em -(Tn-T). TR^-.-TRi -(Tn-T) TE .•'<*• TE l •(Ti Put job i on the bottom o f the CPU queue ® Put j o b i on the t o p o f the CPU queue job # from n e x t event Generate j o b parameters F i g u r e -l+.l '(c) F l o w c h a r t f o r a model'-of'MTS 57 i L i i Concluding Remarks Information on the workloads of computing systems becomes i n c r e a s i n g l y d i f f i c u l t t o o b t a i n as the systems become more complex. New t o o l s must c o n s t a n t l y be developed to overcome t h i s problem, as a good understanding of the behavior of programs i s necessary f o r one to design new o p e r a t i n g systems, or modify o l d ones, with the idea of producing a system t h a t makes good use of the hardware a v a i l a b l e (to minimize waste) , and a l s o g i v e s s a t i s f a c t o r y performance t o users . Basing an oper a t i n g system design on f a u l t y assumptions about the c h a r a c t e r i s t i c s of programs, i s bound to be a h i t and miss a f f a i r . The purpose of t h i s study has been to measure some of the important c h a r a c t e r i s t i c s of programs at the U n i v e r s i t y of B r i t i s h Columbia. The Data C o l l e c t i o n F a c i l i t y w r i t t e n by Dr. T. B. P i n k e r t o n f o r the MTS o p e r a t i n g system has proven to be a v a l u a b l e t o o l to t h i s end. BIBLIOGRAPHY 58 Aho, A. V., Denning, P. J . , Ullman, J . D., " P r i n c i p l e s of Optimal Page Replacement", J o u r n a l of the ACM, v o l . 18, 1 (Jan 1971). Alexander, M. T., "Time-Sharing S u p e r v i s o r Programs", U n i v e r s i t y of Michigan Computing Cetner Memorandum (May 1969). Alexander, M. T., & K. M., "Data C o l l e c t i o n F a c i l i t y and Data A n a l y s i s Program f o r MTS", U n i v e r s i t y of Michigan Computing Center Memorandum #M200 (Nov 1971) . Bard, Y., "Performance C r i t e r i a f o r a Time-Sharing System", IBM S y s t . J o u r n a l , v o l . 10, 3 (1971). Baskett, F., Browne, J . , Raike, w., "The Management of a M u l t i - L e v e l Non-Paged Memory System", Proc. Of AFIPS 1970 SJCC, v o l . 36. B e r r e t t o n i , N. J . , " P r a c t i c a l A p p l i c a t i o n s of the Weibull D i s t r i b u t i o n " , I n d u s t r i a l Q u a l i t y C o n t r o l , v o l . 21, 2 (Aug 196U). Bonner, A. J . , "Using System Monitor Output to Improve Performance", IBM Syst. J o u r n a l , v o l . 8, 4 (1969). Brawn, B., Gustavson, F., "Program Behavior i n a Paging Environment", Proc. Of AFIPS 1968 FJCC, v o l . 33. Bryan, G. E. , "20,000 Hours at the Console: A S t a t i s t i c a l Summary", Proc. Of AFIPS 1967 FJCC, v o l . 31. Campbell, D. J . , Hef f n e r , W. J. , "Measurement A n a l y s i s of Large Operating Systems During System Development", Proc. Of AFIPS 1968 FJCC, v o l . 33, part 1. C a n t r e l l , H. 8., E l l i s o n , A. L. , "Multiprogamming System Performance Measurement and A n a l y s i s " , Proc. Of AFIPS 1968 SJCC, v o l . 32. Cheng, P. S., "Trace Driven System Modeling", IBM Sy s t . J o u r n a l , v o l . 8, 4 (1969). 59 13 Coffman, E. G, , Varian, L. C. , "Further Experimental Data on the Behavior of Programs i n a Paging Environment", Communications of the ACM, v o l . 11, 7 (July 1968). 14 Coffman, E. G., " A n a l y s i s of a Drum Input/Output Queue Under Scheduled Operation i n a Paged Computer System", Journal of the ACM, v o l . 16, 1 (Jan 1969). 15 Daley, R. , Dennis, J . B., " V i r t u a l Memory, Process, and Sharing i n MU1TICS", Communications of the ACM, v o l . 11, 5 (May 1968). 16 Denning, P. J . , "The Working Set Model f o r Program Behavior", Communications of the ACM, v o l . 11, 5 (May 1968). 17 Denning, P. J . , " V i r t u a l Memory", Computing Surveys, v o l . 2, 3 (Sept 1970). 18 Dennis, J . B., "Segmentation and Design of Multiprogramming Computing Systems", J o u r n a l of the ACM, vol.12, 4 (Oct 1965). 19 Drummond, M. E. J r . , "A Pe r s p e c t i v e on System Performance", IBM Syst. J o u r n a l , v o l 8, 4 (1969). 20 E s t r i n , G., K l e i n r o c k , L., "Measures, Models, and Measurements f o r Time-Shared Computer Systems", Proc. Of the ACM 22 N a t i o n a l Conference (1967). 21 F i f e , D. W., "An Optimization Model f o r Time-Sharing", Proc. Of AFIPS 1966 SJCC, v o l . 28. 22 F i n e , G. H., Jackson, C. W., Mclsaac, P. v . , "Dynamic Behavior of Programs Under Paging", Proc. Of the ACM 21 N a t i o n a l Conference (1966). 23 F r e i b e r g s , I. F., "The Dynamic Behavior of Programs", Proc. Of AFIPS 1968 FJCC, v o l . 33. 60 24 Fuchs, E., Jackson, P. E., "Estimates of D i s t r i b u t i o n s of Random V a r i a b l e s f o r C e r t a i n Computer Commumnications T r a f f i c Models", Communications of the ACM, v o l . 13, 12 (Dec 1970). 25 Gordon, G., System S i m u l a t i o n ^ P r e n t i c e - H a l l , Englewood C l i f f s , New Jersey, 1969. 26 H a t f i e l d , D., Gerald, J . , "Program R e s t r u c t u r i n g Techniques i n V i r t u a l Memory", IBM Syst. J o u r n a l , v o l . 10, 3 (1971). 27 K i l b u r n , T., Edwards, D., Lanigan, M., Sumner, F., "One L e v e l Storage Systems", IEEE Trans. On Elec. Computers, v o l . 11, 2 (Apr 1962). 28 K l e i n r o c k , L., Coffman, E. G., " D i s t r i b u t i o n of Atta i n e d S e r v i c e i n Time-Shared Systems", Jour. Comput. Syst. S c i . , v o l . 1 (1967). 29 Kuehner, C. J . , R a n d e l l , B., "Demand Paging i n Pers p e c t i v e " , Proc. Of AFIPS 1968 FJCC, v o l . 33. 30 Lauer, H., "Bulk Core i n a 360/67 Time-Sharing System", Proc. Of AFIPS 1967 FJCC, v o l . 31. 31 Lehman, M., Rosenfeld, J . , "Performance of a Simulated Multiprogramming System", Proc. Of AFIPS 1968 FJCC, v o l . 33, part 2. 32 MacDougall, M. H., "Simulation of an ECS-Based Operating System", Proc. Of AFIPS 1967 SJCC, v o l . 30. 33 MacDougall, M. H., "Computer System Simulation: An I n t r o d u c t i o n " , Computing Surveys, v o l . 2, 3 (Sept 1970). 34 McKinney, J. M., " A n a l y t i c a l Time-Sharing Models", Computing Surveys, v o l . 1, 2 (June 1969). 35 Nakamura, G., "A Feedback Queueing Model f o r an I n t e r a c t i v e Computer System", Proc. Of AFIPS 1971 FJCC, v o l . 39. 61 36 N i e l s e n , N. R., "The Simulation of Time-Sharing Systems", Communications of the ACM, v o l . 10, 7 (July 1968) . 37 O'Neil, R. W. , "Experience Using a Time-Shared Multiprogrammed System With Dynamic Address Rel o c a t i o n Hardware", Proc. Of AFIPS 1967 SJCC, v o l . 30. 38 Oppenheimer, G., Weizer, N., "Resource Management f o r a Medium Scale Time-Sharing Operating System", Communications of the ACM, v o l 11, 5 (May 1968). 39 P i n k e r t o n , T. B., "Program Behavior and C o n t r o l i n V i r t u a l Storage Computer Systems", U n i v e r s i t y of Michigan Tech. Rep. #4, CONCOMP P r o j e c t . 40 P i n k e r t o n , T. B., "Performance Monitoring i n a Time-Sharing System", Communications of the ACM, v o l . 12, 11 (Nov 1969). 41 R u i z - P a l a , E., A v i l a - B e l o s o , C., Hines, W. W., Waitincj-i i n e . Models, Reinhold P u b l i s h i n g Co., New York, 1967. 42 Scherr, A. L., "Time-Sharing Measurement", Datamation, v o l . 12, 4 (Apr 1966). 43 Scherr, A. E., A n a l y s i s of Time-Shared Computer Systems, MIT P r e s s , Cambridge, Mass., 1967. 44 Schwetman, H. D. , DeLine, J. R. , "An Operational A n a l y s i s of a Remote Console System", Proc. Of AFIPS 1969 SJCC, v o l . 34. 45 Sebestyen, G. S., Decision-Making Processes i n Pattern B.6co3nition x Macmillan, New York, 1962. 46 Shemer, J . E., Heying, D.W., "Performance Modeling and E m p i r i c a l Measurement i n a System f o r Batch and Time-Sharing Users", Proc. Of AFIPS 1969 FJCC, v o l . 35. 47 Stanley, W. I . , "Measurement of System Operational S t a t i s t i c s " , IBM Syst. J o u r n a l , v o l . 8, 4 (1969). 62 von Maydell, U. M., Gatha, A. K., "Analysing the Performance of the CP/67 Time Sharing System", INFOR, v o l . 9, 3 (Nov 1971). Z e s g l e r , J . R., Time-Sharing Data Processing Systems^ P r e n t i c e - H a l l , Englewood C l i f f s , New Jersey, 1967. 63 APPENDIX A THE DATA COLLECTION FACILITY The DCF c o n s i s t s of two UMMPS jobs c a l l e d STAT and STATSW and of supervisor subroutine which i s invoked from various points i n the s u p e r v i s o r , and which may a l s o be invoked by a SVC. The STAT job manages a r i n g of b u f f e r s which i t w r i t e s onto a tape when f u l l . The STATSW job i s r e s p o n s i b l e f o r s e t t i n g and r e s e t t i n g a word of switches i n each entry i n the job t a b l e , which i n d i c a t e whether or not data i s to be c o l l e c t e d f o r that job, and what items are to be c o l l e c t e d f o r i t i f data i s to be c o l l e c t e d . The supervisor subroutine i s r e s p o n s i b l e f o r p l a c i n g the items i n the b u f f e r s . Each item c o n s i s t s of a two word p r e f i x c o n t a i n i n g the item type, item length, ID of job to which the item a p p l i e s , an i n d i c a t i o n of which CPU the item occurred on, and the time of the event, followed by from zero to s i x words of s p e c i f i c i n f o r m a t i o n about the event. The presence of such a f a c i l i t y i n a system, must cause some degradation i n performance, but the amount i n t h i s case i s s m a l l . Roughly 10 us of CPU time i s r e q u i r e d every_ time the s u p e r v i s o r i s entered to see i f the DCF i s c u r r e n t l y a c t i v e . I f i t i s , the b u f f e r entry subroutine can place each item i n t o a b u f f e r at a cost of about 65 us each. In a d d i t i o n , the SVC c a l l from a job program to save an item requires about 330 us of CPU time, but only about 10% of items are c o l l e c t e d i n t h i s manner. My measurements have shown that on a f a i r l y busy day, with the DCF o p e r a t i n g , roughly 0.6% of the CPU time i s used by the STAT job, and about 4% of the CPU time by b u f f e r entry subroutine and SVC c a l l to enter data i n b u f f e r s . The DCF a l s o uses roughly 3% 64 of the r e a l core a v a i l a b l e to users. I t i s p o s s i b l e f o r no bu f f e r to be a v a i l a b l e when an item i s to be entered. In t h i s case, a count i s kept of a l l items missed u n t i l a b u f f e r becomes a v a i l a b l e and a s p e c i a l item i n d i c a t i n g t h i s number i s i n s e r t e d as the f i r s t item of the new b u f f e r . This s i t u a t i o n , however, occurs only r a r e l y . The data c o l l e c t i o n f a c i l i t y i n MTS i s c u r r e n t l y the most f l e x i b l e and d e t a i l e d a v a i l a b l e . 65 APPENDIX B FITTING WEIBULL AND HYPER-EXPONENTIAL DISTRIBUTIONS THE WEIBULL DISTRIBUTION The Weibull d i s t r i b u t i o n has the gen e r a l form F{x) = i- e-<K*-y> b where X i s a s h i f t parameter which i s normally e g u a l t o zero when one i s i n t e r e s t e d i n time dependent v a r i a b l e s . T h i s g i v e s us the f o l l o w i n g form f o r the W e i b u l l d i s t r i b u t i o n F(t) = l-e"*** The mean of t h i s d i s t r i b u t i o n i s giv e n by and the v a r i a n c e by <*2*{ f(2/S+1)-r 2(/S+D } where ot = 1/a, /3 - 1/b In order to o b t a i n e s t i m a t e s of the parameters a and b we may apply the f o l l o w i n g t r a n s f o r m a t i o n 1-F(t) = e"*r l n ( 1 - F (t)) = - a t b l n ( 1 / ( 1 - F { t ) ) ) = a t b l n (In ( 1 / ( 1 - F (t) ) )) = l n a + b In t which r e s u l t s i n a l i n e a r equation i n the v a r i a b l e s l n (ln ( 1 / ( 1 - F (t)) ) and l n t . The slope of t h i s l i n e i s b r and the i n t e r c e p t i s l n a. We can f i n d two p o i n t s on t h i s l i n e by s e t t i n g each of the v a r i a b l e s to zero i n t u r n . (1) l n t = 0 when t = 1 Some s u i t a b l e s c a l i n g f a c t o r can be a p p l i e d t o the time v a r i a b l e t o get a value of t = 1 near to the maximum time f o r which data was c o l l e c t e d and not grouped i n an overflow c l a s s . E v a l u a t i n g l n (ln ( 1 / ( 1 - F ( t ) ) ) ) at t h i s p o i n t g i v e s a value f o r l n a. 66 (2) ln ( l n { 1 / ( 1 - F . ( t ) ) ) ) = 0 when 1/(1-F(t)) = e or F (t) = 0. 6321 from the sample d i s t r i b u t i o n , f i n d a value T such that F (T) = 0. 6321. The parameter b may now be c a l c u l a t e d from b = -In a/In T. An i n v e r s e f u n c t i o n e x i s t s f o r the Weibull d i s t r i b u t i o n , and i s derived as f o l l o w s : P (x<t) = 1-e" a t b 1-p = e-** In p = - a t b t b = ln[ d / p ) 0 1 ] In t = /Q l n ( l n [ (1/p)*] In t = l n ( l n [ ( 1 / p ) * ] ) * t = [ <*ln{1/p) ] * THE HIPER-EXPONENTIAL DISTHIBUTION A hyper-exponential d i s t r i b u t i o n may be represented by the general form F(t) = + (1-s)e - 2('-s)^" t' The mean of t h i s d i s t r i b u t i o n i s given by 1/Ar and the variance by Cr2 = [ (1-2s+2s2)/(2s-2s2) ](1 / A ) 2 Given the mean and variance of a sample d i s t r i b u t i o n , we may c a l c u l a t e a value f o r the parameter s as f o l l o w s : l e t k = a 2 A? 67 k = ( 1 - 2 s + 2 s 2 ) / ( 2 s - 2 s 2 ) t h i s y i e l d s s = (2k+2-2 ( k2-1)' A)/(Uk+4) w h i c h h a s a s o l u t i o n a s l o n g a s k>1, w h i c h must be t r u e f o r t h e h y p e r - e x p o n e n t i a l d i s t r i b u t i o n s i n c e t h e v a r i a n c e i s g r e a t e r t h a n t h e s g u a r e o f t h e mean. 68 APPENDIX C MTS DATA Data was c o l l e c t e d f o r t h i s study on two occasions, f i r s t on June 19, 1971, and secondly on November 11, 1971. The f i r s t data tape (tape 1) r e p r e s e n t s a l i g h t load on the system, with only about 7 i n t e r a c t i v e jobs, and 2 batch jobs running s i m u l t a n e o u s l y . The second data tape (tape 2) was c o l l e c t e d to observe the system under h e a v i e r l o a d . During the time that c o l l e c t i o n took p l a c e , about 19 i n t e r a c t i v e j o b s , and 2 to 3 batch jobs were running s i m u l t a n e o u s l y , The number of batch jobs i s r e s t r i c t e d a t times of heavy usage by i n t e r a c t i v e j o bs t o prevent the system from g e t t i n g bogged down. As can be seen i n Table C.1, even under the heavier l o a d c o n d i t i o n , the CPU's are i d l e 48% of the time. The u t i l i z a t i o n of the CPU's at The U n i v e r s i t y of B r i t i s h Columbia's computing c e n t r e approaches 100% during the midnight hours, when most of the l a r g e batch jobs are run. I t i s i n t e r e s t i n g to note that the DCF uses c o n s i d e r a b l y more of the system's res o u r c e s (Table C.1) than P i n k e r t o n has i n d i c a t e d i n e i t h e r [ 3 1 ] , or [ 3 2 ] . The times were c a l c u l a t e d u s i n g h i s formula of 65 us f o r the c o l l e c t i o n of 90% of the items, and 330 us f o r the remainder. The times f o r the b u f f e r managing subroutine (STAT) were measured d i r e c t l y from the data tapes. A frequency d i s t r i b u t i o n of the items on the tapes may be found i n Table C.2, and a comprehensive d e s c r i p t i o n of the items i n [ 3 ] . Tape 1 . Tape 2 Date 19-6-71 12-11-71 Start Time 15:25 14;03 Durration 95 min No. of Items 753389 ' 2749238 GJVU' s Idle 83.6% 48.4% CPU Time f o r DC? 4 .0% 4.8% data c o l l e c t i o n 5.5% 4.2% STAT job (buffers) 0.5% 0.6% CPU Time f o r PDP 2.9% , 6.6% Total CPU Time f o r Non-user Tasks 12.3% 16.8% Table C l MTS Data STAT ITEM • j* on' TAPIS 1 /V on TAPE 2 OVERFLOW 0 3 '•DATii I 1 ADTOTOP. • 35U53 , 2 0 1 6 5 1 POPvi • 320U1 • 130960 WAYT 91326 • 29*311; UNWAYT ob656 •' ' 297U75 QUiiUS '• 3U9U12 - ' 1187322 STATSW .'. 3 U 9 . • • • _ ; 397 PAG IKSTK , $Qhb ' 3QO69 PAGINiX) 'N SOht ' . 36872 PAGOUTST •••• . " ' 5552 •• U2132 PAGOUTDN. , 5U76 • 1^689 P A G R E C L M ' * ' 8276 30210 G3TVKPAG . ' 9196- 32658 WEVMPAG •• 9u67 32760' SYNCHRON ' . 91 95 VMP^GES 12695 . iSubk WAITrOH • 1790 _ 20u6 UNLOAD- 212 595 LOAD. ., 211 .•• . . 63u F R E S S P A C 2956.9 •. .' v . ' 96088 G E T S P A C S 28951' ' . 95287. DSP.IX ' ' ' ,17183 , 69336 DSROUT 1716U • ; .69330 G T A L S 753389. 27U9238 Table G.2 . Frequency of STAT items. APPENDIX !) SYGkAwS FftOyTLBS 7 / o U3 CO CXvr a. 0.0 0.2 0 .4 0.5 0.8 1.0' 03 a CO LU<=> a . a ' 0..0 0.2 • 0.4 Figure ' D.u 0.0 0.0 1 .0 H CD D.O o CD D cn o CD 2 0 . D _ J P f i G E S 4 0 . 0 CO.O 80.0 _ J D.D C.J CD O to **1 CD o vn o o cn o co 2 0 . . D I 1 1 - , P A G E S 4 0 . 0 60.0 _ J •si 75 cn C D g , CL a a ' 0.0 0.2 ST 0.4 Figure D . 9 hr^ H 0.5 0.8 "1 1.0 a a _j can cn C-Dq. CL. a . CM ILnn a ' •JI—a. 0.0 0.2 LJL 0 .4 0.5 0.8 1.0 Figure D.10 Ul CM a a' 0.0 "L SL 0.2 0.4 .0.6 Figure D . l l 0.8 1.0 03 CO CL. a . CM C J 0.0. 0.2 • 0.4 0.5 Figure D.12 0.8 1 A I Figure D .13 o o _ CO o . ID 01 Li _ i , Q CL. a a _ j n • 1 n n q a 1 : I I I I Q ; 0 Q . 2 3.4 0 . 5 • 0 . 8 Figure . D.ii; 78 LO CO c n v Q-a a ' 0.0 , j . . — j — , 1 . 0.2 0.4 0.6 0.8 1.0 Figure 2 . 1 5 co (£3 CO U J Q C C v CL. OJ a ' 0,0 J i or A—-T. 0-2 0.4 • 0.6 0.8 1.0 figure D.16 0.0 o CD O K3 o o cn o co . P A G E S 20.0 40.0 i i 60.D _ J 80.0 _ J D.O o o CD F o CD o 20.0 P A G E S •40.0 G0.D _ J : 1 <0 D.O 20.0 _ J _ P A G E S 40. o i CO.D _ J 80.0 o o cn o co D.O o CD o o cn o CO 20.0 _ l P A G E S 40.0 l _ CO .0.0 0.2 0 .4 0.6 o .a Figure D.21 -TL. 0.0 .0.2 T T 0.4 0.6 Fisruro D..22 . o.a A 0.0 T T 0.2 0.4 0.5 ' Figure D.25 . o.a O.D o o . to >0 3C-. CT) 20. D P R G E S 40.0 BD.D o • CD 1=> 8D.0 _ L CD D.D • * to t cn . CO 20.0 _ J P R G E S 40.0 BD.D _J_. - j ] co -F APPENDIX E THE COHPUTI'HG S 1ST EH 85 The c o n f i g u r a t i o n of the 360/67 computing system at the U n i v e r s i t y of B r i t i s h Columbia during the time of t h i s study was as f o l l o w s : processors drum storage u n i t s 1) 2 2067 2) 2 2301 3) a 2365-2 4) 2 2860-2 5) 2 2870 6) 2 2314 7) 1 2321 8) assorted 8-drive d i s k u n i t s data c e l l u n i t s , i n t e r a c t i v e t e r m i n a l s , and the associated c o n t r o l eguipment. The two processors run i n f u l l duplex mode, 

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-0051195/manifest

Comment

Related Items