UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The design and implementation of the Cambridge ring protocols Wong, Julian Hong Pak 1984

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

Item Metadata

Download

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

Full Text

THE D E S I G N AND I M P L E M E N T A T I O N OF THE CAMBRIDGE RING PROTOCOLS by J U L I A N HONG PAR WONG B . S c , W a s h i n g t o n S t a t e U n i v e r s i t y , 1982 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF S C I E N C E i n THE F A C U L T Y OF GRADUATE S T U D I E S D e p a r t m e n t Of C o m p u t e r S c i e n c e We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE U N I V E R S I T Y OF B R I T I S H COLUMBIA May 1984 © J u l i a n Hong Pak Wong , 1984 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my d e p a r t m e n t o r b y h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t o f Computer Science  T h e U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 W e s b r o o k P l a c e V a n c o u v e r , C a n a d a V 6 T 1W5 D a t e 8/5/84 )E-6 (2 /79) i i A b s t r a c t P r o t o c o l i m p l e m e n t a t i o n i s c h a r a c t e r i z e d by v a r i o u s i s s u e s s u c h a s c o n c u r r e n c y , t i m e - c r i t i c a l r e s p o n s e s , a n d a s y n c h r o n o u s e v e n t s . S u c h i s s u e s w o u l d be e a s i e r t o r e s o l v e i f t h e u n d e r l y i n g o p e r a t i n g s y s t e m p r o v i d e s a h o s p i t a b l e e n v i r o n m e n t t h a t i n c l u d e an e f f i c i e n t i n t e r p r o c e s s c o m m u n i c a t i o n f a c i l i t y . M o s t o p e r a t i n g s y s t e m s , h o w e v e r , do n o t p r o v i d e s u c h an e n v i r o n m e n t . T h i s t h e s i s p r e s e n t s an i m p l e m e n t a t i o n a n d d i s c u s s e s what h a s b e e n l e a r n e d -in i m p l e m e n t i n g t h e B y t e S t r e a m a n d t h e B a s i c B l o c k p r o t o c o l s o f t h e C a m b r i d g e R i n g on a L S I 11 /23 c o m p u t e r r u n n i n g t h e U n i x . V 7 o p e r a t i n g s y s t e m . i i i T a b l e o f C o n t e n t s A b s t r a c t i i L i s t o f F i g u r e s y A c k n o w l e d g e m e n t v i C h a p t e r I INTRODUCTION 1 1.1 M o t i v a t i o n A n d O b j e c t i v e 1 1.2 T h e s i s O u t l i n e 3 C h a p t e r I I THE CAMBRIDGE RING AND ITS PROTOCOLS 4 2 .1 T h e C a m b r i d g e R i n g 4 2 . 2 O v e r v i e w Of The B a s i c B l o c k P r o t o c o l 8 2 . 2 . 1 I n t e r f a c e To T h e R i n g 9 2 . 2 . 2 Mode Of O p e r a t i o n 9 2 . 2 . 3 S h o r t c o m i n g s 10 2 . 2 . 4 The C a m b r i d g e BBP 12 2 . 3 O v e r v i e w Of T h e B y t e S t r e a m P r o t o c o l 14 2 . 3 . 1 F o r m a t Of P a c k e t 14 2 . 3 . 2 Mode Of O p e r a t i o n 15 2 . 3 . 3 BSP S t a t e T r a n s i t i o n - 16 2 . 3 . 4 I n i t i a l S t a t e 19 2 . 3 . 5 T i m e r s 19 C h a p t e r I I I I M P L E M E N T A T I O N ENVIRONMENT 20 3.1 I n t r o d u c t i o n 20 3 . 2 I n t e r p r o c e s s C o m m u n i c a t i o n I n UNIX 24 3 . 2 . 1 F o r k s A n d P i p e s 24 3 . 2 . 2 L o c k e d F i l e s A n d S i g n a l s 27 3 . 3 D e s i g n O v e r v i e w 29 3 . 3 . 1 M u l t i p l e x i n g Of U s e r s 29 3 . 3 . 2 U s e r I n t e r f a c e . . . 3 2 3 . 3 . 3 A d m i n i s t r a t i o n Of I P C 32 C h a p t e r I V B A S I C BLOCK PROTOCOL I M P L E M E N T A T I O N 34 4.1 E x i s t i n g BBP I m p l e m e n t a t i o n 34 4 . 2 A l g o r i t h m s 37 4 . 3 U n i x I / O 3 9 4 . 4 P e r f o r m a n c e Of BBP I m p l e m e n t a t i o n s 41 4 . 4 . 1 C o n v e n t i o n a l I / O 41 4 . 4 . 2 R e a d - A h e a d I / O 42 4 . 4 . 3 S i g n a l l i n g 42 4 . 4 . 4 M e a s u r e m e n t s 43 C h a p t e r V B Y T E STREAM PROTOCOL I M P L E M E N T A T I O N 4 5 5.1 S e r v e r R e p r e s e n t a t i o n 47 5 . 2 R e a d e r R e p r e s e n t a t i o n 51 5 . 3 P r o c e s s i n g R e q u e s t B B _ A R R I V E 53 i v 5 . 3 . 1 D a t a T r a n s a c t i o n s 55 5 . 3 . 2 F o r m a t Of B u f f e r • 57 5 . 4 T i m e r D e s i g n 57 5 . 4 . 1 G e n e r a l T i m e r 59 5 . 4 . 2 M u t u a l E x c l u s i o n Of S h a r e d Queue 61 5 . 4 . 3 G r a n u l a r i t y Of C l o c k 62 5 . 5 W r i t e r D e s i g n 62 C h a p t e r VI CONCLUSIONS 66 6.1 R e f l e c t i o n s On T h e I m p l e m e n t a t i o n s 66 6 . 2 S u g g e s t i o n s F o r P o s s i b l e I m p r o v e m e n t s 67 B I B L I O G R A P H Y 68 A P P E N D I X A - T A B U L A T I O N S OF PERFORMANCES OF BBP 70 V L i s t o f F i g u r e s 1. C a m b r i d g e R i n g LAN 4 2 . F o r m a t o f a M i n i p a c k e t 5 3 . T h e B a s i c B l o c k 8 4 . F o r m a t o f H e a d e r 9 5 . S t a t e T r a n s i t i o n D i a g r a m f o r t h e BSP 17 6 . O v e r a l l D e s i g n o f BSP a n d BBP 31 7 . M o d i f i e d B a s i c B l o c k 35 8 . I n t e r f a c e b l o c k b e t w e e n R i n g d r i v e r a n d BSP 36 9 . P e r f o r m a n c e s o f t h e i m p l e m e n t a t i o n s 44 10 . S e r v e r / C l i e n t M o d e l o f B S P - 46 11 . M a i n P r o c e d u r e o f S e r v e r . . . . . 4 8 •12. F o r m a t o f P I P E _ F R A M E 49 13 . F o r m a t o f S E R V E R _ S T A T E 50 14 . BSP D a t a S t r u c t u r e s 51 15 . R e p r e s e n t a t i o n o f R e a d e r 52 16 . D i a g r a m o f f u n c t i o n f r a m e _ a r r i v a l 53 17 . F o r m a t o f USER_NODE 54 18 . D i a g r a m o f f u n c t i o n d a t a _ f r a m e 56 19 . F o r m a t o f s t r u c t u r e t i m e n o d e 60 2 0 . R e p r e s e n t a t i o n o f T i m e r s 61 2 1 . R e p r e s e n t a t i o n o f W r i t e r 63 v i Ac k n o w l e d g e m e n t Many i n d i v i d u a l s c o n t r i b u t e d i n s p e c i a l ways t o t h e a c c o m p l i s h m e n t o f t h i s t h e s i s . I w o u l d l i k e t o t h a n k t h e f o l l o w i n g p e o p l e : • D r . Son V u o n g f o r h i s s u p e r v i s i o n a n d f i n a n c i a l s u p p o r t . • D r . S a m u e l C h a n s o n f o r h i s g u i d a n c e a n d f o r t h e r e a d i n g o f t h i s t h e s i s . • R. R a v i n d r a n f o r h i s h e l p f u l s u g g e s t i o n s a n d t h e c o m p l e t i o n o f t h e p e r f o r m a n c e m e a s u r e m e n t s o f t h e B B P . • L i n d a Chan a n d T a n Ghee H i n g f o r t h e i r f i n e e d i t i n g s k i l l s . • J e a n Wu a n d R o s a l y n L e e f o r t h e i r a s s i s t a n c e i n one way o r a n o t h e r . I am a l s o g r a t e f u l t o -the d e p a r t m e n t o f C o m p u t e r S c i e n c e f o r t h e f i n a n c i a l s u p p o r t g i v e n w h i l e p r e p a r i n g t h i s t h e s i s . A n d a s p e c i a l " T h a n k Y o u " t o G r a c e K i m f o r g i v i n g me e n c o u r a g e m e n t a n d T . L . C . d u r i n g t h e d i f f i c u l t t i m e s . 1 I . INTRODUCTION 1.1 M o t i v a t i o n A n d O b j e c t i v e C u r r e n t t r e n d s f a v o r i n g d e c e n t r a l i z a t i o n o f c o m p u t i n g power a n d r e s o u r c e s g a i n e d momentum on t h e a r r i v a l o f L o c a l A r e a N e t w o r k t e c h n o l o g y . A L o c a l A r e a N e t w o r k ( L A N ) , a s t h e name i m p l i e s , r e f e r s t o an i n t e r c o n n e c t i o n o f c o m p u t e r s o r d e v i c e s l o c a t e d i n a r e s t r i c t e d g e o g r a p h i c a l a r e a . I t p r o v i d e s an e f f e c t i v e a n d i n e x p e n s i v e f o r m o f d a t a c o m m u n i c a t i o n among t h e c o n s t i t u e n t c o m p u t e r s o r h o s t s a n d d e v i c e s l i n k e d t o i t . T h e h o s t s a n d d e v i c e s a r e s o m e t i m e s r e f e r r e d u n d e r t h e g e n e r i c name o f n o d e s . A L A N , l i k e a n y o t h e r d a t a c o m m u n i c a t i o n n e t w o r k , b a s i c a l l y c o n s i s t s o f : • T h e p h y s i c a l medium f o r t r a n s m i s s i o n , e . g . c a b l e s , t w i s t e d p a i r a n d f i b r e o p t i c s . • T h e p h y s i c a l c o n t r o l m e c h a n i s m f o r t h e u s e o f t h e p h y s i c a l medium f o r t r a n s m i s s i o n . • T h e h a r d w a r e i n t e r f a c e s t o t h e n o d e s u s i n g t h e p h y s i c a l m e d i u m . • T h e s o f t w a r e r e s i d i n g i n t h e n o d e s t o c o n t r o l t h e c o m m u n i c a t i o n p r o c e s s among n o d e s . T h i s s o f t w a r e i s c o m m o n l y known a s c o m m u n i c a t i o n p r o t o c o l s . P r o t o c o l s p r o v i d e a s e t o f r u l e s t o f a c i l i t a t e c o m m u n i c a t i o n among t h e v a r i e t y o f h o s t s a n d d e v i c e s i n t h e n e t w o r k u s i n g t h e u n d e r l y i n g p h y s i c a l medium t h a t i s s u s c e p t i b l e t o e r r o r s . T h e s e t o f p r o t o c o l s i m p l e m e n t e d i n e a c h n o d e c a n be 2 c o n c e i v e d as f u n c t i o n i n g a t d i f f e r e n t l a y e r s . E a c h l a y e r u t i l i z e s t h e s e r v i c e s o f t h e l a y e r b e l o w i t a n d p r o v i d e s t h e n e c e s s a r y s e r v i c e s f o r t h e l a y e r a b o v e t o f u n c t i o n . The l o w e s t l a y e r i n t e r a c t s d i r e c t l y w i t h t h e h a r d w a r e a n d t h e h i g h e s t l a y e r p r o v i d e s a t r a n s p a r e n t s e r v i c e t o t h e u s e r . T h i s l a y e r i n g c o n c e p t i s f o r m a l i z e d i n t h e ISO R e f e r e n c e M o d e l f o r Open S y s t e m s I n t e r c o n n e c t i o n [ 7 ] , T h e o b j e c t i v e o f t h i s t h e s i s i s t o d e s i g n a n d i m p l e m e n t t h e C a m b r i d g e R i n g B y t e S t r e a m a n d B a s i s B l o c k p r o t o c o l s [ 5 , 8 ] on a L S I 1 1 / 2 3 m a c h i n e r u n n i n g t h e U N I X . V 7 [ 1 3 , 1 4 ] o p e r a t i n g s y s t e m . T h e L S I 11 /23 m a c h i n e i s c o n n e c t e d t o a C a m b r i d g e R i n g L o c a l A r e a N e t w o r k [ 1 5 ] o f w h i c h t h e r e i s o n l y one o t h e r m a c h i n e c u r r e n t l y c o n n e c t e d , a TI 9 9 0 . T h e a b o v e m e n t i o n e d p r o t o c o l s t o g e t h e r p r o v i d e a c o m p a r a b l e t r a n s p o r t l a y e r s e r v i c e [ 7 ] t o t h i s h o s t P r o t o c o l i m p l e m e n t a t i o n i s c h a r a c t e r i z e d by t h e v a r i o u s i s s u e s o f c o n c u r r e n c y , t i m e - c r i t i c a l r e s p o n s e s , a s y n c h r o n o u s e v e n t s a n d r o b u s t r e c o v e r y f r o m e r r o r s . F e a t u r e s i n t h e u n d e r l y i n g o p e r a t i n g s y s t e m w h i c h w o u l d a i d t h e p r o g r a m m e r t r e m e n d o u s l y w o u l d i n c l u d e s h a r e d memory among r e l a t e d p r o c e s s e s , g o o d i n t e r p r o c e s s c o m m u n i c a t i o n , h i g h s p e e d I / O , a c c e s s c o n t r o l a n d s y n c h r o n i z a t i o n t o s h a r e d d a t a a n d t h e p r o v i s i o n o f t i m e r s . M o s t o f t h e p r o c e d u r e b a s e d o p e r a t i n g s y s t e m s , h o w e v e r , do n o t p r o v i d e s u c h f e a t u r e s a n d i f t h e y d o , i t i s n o t uncommon t o f i n d t h e f a c i l i t i e s awkward o r u n s u i t a b l e t o u s e . I n t h e c a s e o f t h e q u a s i s t a n d a r d UNIX o p e r a t i n g s y s t e m , i t s i n t e r p r o c e s s c o m m u n i c a t i o n ( I P C ) h a s e v e n b e e n 3 e x t e n d e d t o f a c i l i t a t e p r o t o c o l i m p l e m e n t a t i o n s [ 1 , 6 , 1 2 ] . T h i s a p p r o a c h i s u n d o u b t e d l y e f f e c t i v e a n d w o u l d r e p r e s e n t an e f f o r t o f a l a r g e r s c a l e where a c o r r e s p o n d i n g amount o f human a n d e c o n o m i c r e s o u r c e s i s r e q u i r e d . I n o u r c a s e , t h e a b o v e m e n t i o n e d p r o t o c o l s a r e s i m p l y i m p l e m e n t e d on t h e e x i s t i n g U N I X . V 7 s y s t e m a n d t h e f o l l o w i n g c h a p t e r s w i l l e n u m e r a t e t h e c o n s t r a i n t s o f t h e u n d e r l y i n g o p e r a t i n g s y s t e m on t h e f i n a l d e s i g n o f t h e r e s u l t i n g i m p l e m e n t a t i o n . 1.2 T h e s i s O u t l i n e C h a p t e r i i b e g i n s w i t h a b r i e f o v e r v i e w on t h e C a m b r i g e R i n g a n d i s f o l l o w e d by a b r i e f o v e r v i e w on t h e s e t o f p r o t o c o l s . C h a p t e r i i i d e s c r i b e s t h e UNIX i m p l e m e n t a t i o n e n v i r o n m e n t a n d i t s c o n s t r a i n t s on t h e o v e r a l l d e s i g n o f t h e s e t o f p r o t o c o l s . T h e d e t a i l s o f e a c h i m p l e m e n t a t i o n i s d e s c r i b e d i n c h a p t e r s i v a n d v . C h a p t e r v i c o n c l u d e s t h i s t h e s i s by p r e s e n t i n g t h e f i n a l p r o d u c t a n d by s u g g e s t i n g p o s s i b l e i m p r o v e m e n t s . S i n c e t h e i m p l e m e n t a t i o n i s c o d e d i n t h e s y s t e m l a n g u a g e C [ 9 ] , many o f t h e a l g o r i t h m s o r e x a m p l e s g i v e n i n t h e c h a p t e r s a r e a l s o i n C ; h o w e v e r , t h e y a r e s i m p l e e n o u g h t o be u n d e r s t o o d by a r e a d e r w i t h some p r o g r a m m i n g e x p e r i e n c e . 4 I I . THE CAMBRIDGE RING AND ITS PROTOCOLS T h i s c h a p t e r p r e s e n t s an o v e r v i e w o f t h e C a m b r i d g e R i n g [ 1 5 ] a n d i t s low l e v e l p r o t o c o l s , n a m e l y t h e B a s i c B l o c k a n d t h e B y t e S t r e a m p r o t o c o l s . T h i s o v e r v i e w i s a b a s i s f o r t h e d e s c r i p t i o n o f t h e i m p l e m e n t a t i o n s t h a t w i l l be d e s c r i b e d i n t h e l a t e r c h a p t e r s . 2 . 1 The C a m b r i d g e R i n g T h e C a m b r i d g e R i n g i s a s l o t t e d r i n g w i t h a raw d a t a r a t e o f 10 m e g a b i t s / s e c o n d ( w i t h c u r r e n t t w i s t e d p a i r t e c h n o l o g y ) . T h e d i a g r a m shown b e l o w i s a t y p i c a l L o c a l A r e a N e t w o r k (LAN) u s i n g t h e R i n g . F i g u r e 1 - C a m b r i d g e R i n g LAN 5 F o r a n y d e v i c e t h a t i s t o be a t t a c h e d t o t h e R i n g , a r e p e a t e r i s r e q u i r e d . E s s e n t i a l l y t h e t a s k o f t h e r e p e a t e r i s t o p r o v i d e s i g n a l r e g e n e r a t i o n a n d t o p a s s t h e d a t a t o t h e s t a t i o n . D a t a i s t r a n s m i t t e d r o u n d t h e R i n g i n m i n i p a c k e t s c o n t a i n e d i n t h e c i r c u l a t i n g s l o t s . As shown i n F i g . 2 , e a c h m i n i p a c k e t c o n s i s t s o f two d a t a b y t e s , a s o u r c e a d d r e s s b y t e , a d e s t i n a t i o n a d d r e s s b y t e , two r e s p o n s e b i t s a n d f o u r c o n t r o l b i t s . l e n g t h : 1 1 1 . 8 8 I i i i i I + - + - + - + — + — + d e s t i n a t i o n s o u r c e a d d r e s s a d d r e s s u s a g e m o n i t o r , f rame 1 6 2 1 - + - - + - + d a t a p a r i t y r e s p o n s e F i g u r e 2 - F o r m a t o f a M i n i p a c k e t D e f i n i t i o n o f t h e b i t s : • F r ame b i t i s s e t t o one i f t h i s were a h e a d e r p a c k e t . • M o n i t o r b i t i n d i c a t e s i f t h e p a c k e t h a d p a s s e d t h e m o n i t o r s t a t i o n . • U s a g e i n d i c a t e s i f t h e p a c k e t i s i n u s e . • R e s p o n s e c a n t a k e one o f f o u r v a l u e s a n d i n d i c a t e s t h e d e s t i n a t i o n s t a t i o n s r e s p o n s e . \ 6 00 accepted 01 busy 1 0 r e j e c t e d 1 1 ignored • P a r i t y i s used f o r d e t e c t i n g t r a n s m i s s i o n e r r o r s . Between the host and the r e p e a t e r comes the s t a t i o n . Each s t a t i o n has a source s e l e c t r e g i s t e r (SSR) which i s used to permit r e c e p t i o n from any source, from a nominated source or from no source. The s t a t i o n u n i t watches the b i t stream e m i t t e d by the re p e a t e r and d e t e c t s the framing of the m i n i p a c k e t s ; i t p r o v i d e s the mechanism f o r . r e c e i v i n g and t r a n s m i t t i n g of the m i n i p a c k e t s . When t r a n s m i t t i n g a mi n i p a c k e t , the s t a t i o n watches f o r an empty s l o t ; when one a r r i v e s , i t i s marked f u l l . The minipacket to be t r a n s m i t t e d i s then f i l l e d i n and sent away. E v e n t u a l l y , t h i s minipacket r e t u r n s to the sending s t a t i o n a f t e r being p r o c e s s e d at the d e s t i n a t i o n . The p o s s i b l e responses to the t r a n s m i t t e d minipacket are as f o l l o w s : 7 P a c k e t A c c e p t e d The d a t a a n d s o u r c e b y t e s h a v e b e e n c o p i e d i n t o t h e r e c e i v i n g s t a t i o n S t a t i o n B u s y T h e r e c e i v i n g s t a t i o n r e c e p t i o n r e g i s t e r was f u l l P a c k e t R e j e c t e d The S e l e c t i o n r e g i s t e r i n t h e r e c e i v i n g s t a t i o n h a d b e e n s e t t o e x c l u d e r e c e p t i o n f r o m t h i s s o u r c e E r r o r P a c k e t An e r r o r p a c k e t i s r e t u r n e d When a m i n i p a c k e t r e t u r n s t o t h e s e n d i n g s t a t i o n , i t i s a l w a y s m a r k e d as e m p t y a n d p a s s e d o n . T h i s i s an a n t i - h o g g i n g d e v i c e a n d e n s u r e s t h a t t h e b a n d w i d t h i s s h a r e d e q u a l l y among t h e s t a t i o n s . T h e m o n i t o r s t a t i o n i s a s p e c i a l m a i n t e n a n c e s t a t i o n w h i c h i s s e t up t o m o n i t o r t h e R i n g f o r o b s c u r e e r r o r s a n d o t h e r f u n c t i o n s n e c e s s a r y f o r a r e l i a b l e R i n g . T h e i n t e r f a c e b e t w e e n a h o s t a n d t h e R i n g i s p r o v i d e d by t h e a c c e s s c i r c u i t s . 8 2 . 2 O v e r v i e w Of T h e B a s i c B l o c k P r o t o c o l T h e B a s i c B l o c k P r o t o c o l (BBP) i s t h e l o w e s t l e v e l p r o t o c o l w h i c h i n t e r a c t s w i t h t h e H o s t h a r d w a r e i n t e r f a c e ( a c c e s s c i r c u i t s ) t o t h e R i n g . I t p r o v i d e s an u n r e l i a b l e d a t a g r a m s e r v i c e t o h i g h e r l e v e l s o f t w a r e . I n t h e ISO p r o t o c o l f r a m e w o r k , t h i s p r o t o c o l l a y e r i s c o n s i d e r e d a s t h e D a t a - L i n k l a y e r . T h e b a s i c u n i t ' o f t r a n s m i s s i o n o f d a t a i n t h e BBP i s t h e B a s i c B l o c k ; t h e f o r m a t o f w h i c h i s a s shown b e l o w . • A H e a d e r m i n i p a c k e t • A P o r t m i n i p a c k e t • 1 t o 1024 D a t a m i n i p a c k e t s • A C h e c k s u m m i n i p a c k e t + + + + + + + + | P o r t | | D a t a | - - | D a t a | | C h k s u m | + + + + + + + + <-- 1 t o 1024 --> F i g u r e 3 - The B a s i c B l o c k H h | H e a d e r | H I-T h e H e a d e r s i g n i f i e s t h e b e g i n n i n g o f a b a s i c b l o c k a n d c o n t a i n s t h e l e n g t h o f t h e D a t a m i n i p a c k e t s i n t h e b a s i c b l o c k . A t r a n s m i t t e r may s e n d up t o 1024 D a t a m i n i p a c k e t s . The f o r m a t o f t h e H e a d e r m i n i p a c k e t i s a s f o l l o w s : 9 + + + + | 1 0 0 1| TY | L E N G T H 4 2 b i t s b i t s 1 0 b i t s TY= t y p e o f b a s i c b l o c k . F i g u r e 4 F o r m a t o f H e a d e r T h e P o r t m i n i p a c k e t a l l o w s m u l t i p l e x i n g o f l o g i c a l c h a n n e l s w i t h i n a h o s t . The D a t a m i n i p a c k e t s c o n t a i n t h e a c t u a l m e s s a g e t o be t r a n s m i t t e d . T h e C h e c k s u m i s a 16 b i t sum o f t h e b a s i c b l o c k , c o m p u t e d m o d u l o 2 - 1 , w i t h e n d - a r o u n d c a r r y . 2 . 2 . 1 I n t e r f a c e T o T h e R i n g T h e r e a r e 2 t y p e s o f h a r d w a r e i n t e r f a c e s w h i c h a r e u s e d i n t h e R i n g . The f i r s t t y p e i s s i m p l e p r o g r a m m e d i n t e r r u p t i n t e r f a c e a n d t h e o t h e r i s a s o p h i s t i c a t e d DMA ( d i r e c t memory a c c e s s ) t y p e i n t e r f a c e . [3 ] T h e n o n - i n t e l l i g e n t p r o g r a m m e d i n t e r r r u p t i n t e r f a c e c u r r e n t l y e x i s t s b e t w e e n t h e R i n g a n d t h e L S I 1 1 / 2 3 . 2 . 2 . 2 Mode Of O p e r a t i o n F r o m a p r o g r a m m e r ' s p o i n t o f v i e w , t h e R i n g c a n be p e r c e i v e d a s a d a t a h i g h w a y [ 4 ] . On t r a n s m i s s i o n t h e BBP s o f t w a r e l o a d s t h e d e s t i n a t i o n a d d r e s s (8 b i t s ) a n d t h e d a t a (16 b i t s ) o n t o t h e i n t e r f a c e a n d s i g n a l s t h e i n t e r f a c e t o t r a n s m i t 1 0 t h i s m i n i p a c k e t . T h e m i n i p a c k e t t h e n g o e s r o u n d t h e R i n g ; a t t h e d e s t i n a t i o n i n t e r f a c e , t h e r e s p o n s e b i t s i n t h e m i n i p a c k e t a r e a l t e r e d t o r e c o r d t h e r e s u l t o f t h i s t r a n s m i s s i o n . On a r r i v a l a t t h e s e n d e r ' s i n t e r f a c e , t h e r e s u l t o f t h e t r a n s m i s s i o n i s t h e n p a s s e d t o t h e s o f t w a r e . T h e r e c e i v i n g p a r t o f t h e i n t e r f a c e c o n s i s t s o f a s o u r c e s e l e c t r e g i s t e r ( S S R ) , a r e c e i v e d a d d r e s s r e g i s t e r a n d a 16 b i t d a t a r e g i s t e r . T h e SSR a l l o w s t h e r e c e i v i n g i n t e r f a c e t o be e i t h e r one o f t h e f o l l o w i n g s t a t e s : • l i s t e n t o a l l s t a t i o n s • l i s t e n e x c l u s i v e l y t o 1 s t a t i o n • l i s t e n t o n o b o d y By s e t t i n g t h e c o n t e n t s o f t h e SSR, t h e BBP c o u l d d i s c r i m i n a t e a s t o w h i c h s t a t i o n i t w i s h e s t o c o m m u n i c a t e w i t h . T h e r e c e i v e d a d d r e s s r e g i s t e r c o n t a i n s t h e a d d r e s s o f t h e s t a t i o n w h i c h o r i g i n a t e d t h e t r a n s m i s s i o n . 2 . 2 . 3 S h o r t c o m i n g s I n a p r o g r a m m e d i n t e r r u p t i n t e r f a c e , an i n t e r r u p t i s g e n e r a t e d f o r e v e r y m i n i p a c k e t r e c e i v e d o r t r a n s m i t t e d . In a h i g h s p e e d R i n g , t h e r a t e a t w h i c h i n t e r r u p t s a r e g e n e r a t e d a t t h e i n t e r f a c e e x c e e d s t h e r a t e a t w h i c h most o p e r a t i n g s y s t e m s c a n p r o c e s s them [ 1 1 ] . T h e p r o b l e m i s a m p l i f i e d i f t h e CPU i s a l s o s l o w ( s e e F i g . 9 ) . A r a p i d s e n d e r s e n d i n g c o n t i n u o u s m a t e r i a l t o s u c h a s t a t i o n w i l l l i k e l y e x p e r i e n c e a c o n s i d e r a b l e amount o f ' b u s i e s ' 11 a n d w i l l h a v e t o r e t r y r e p e a t e d l y . C o n s e q u e n t l y , a t r a n s m i t t i n g h o s t w i l l n o t be a b l e t o e x p l o i t t h e h i g h s p e e d t r a n s m i s s i o n m e d i u m . To o b t a i n i d e a l p e r f o r m a n c e , i t i s n e c e s s a r y t o make a t r a n s m i s s i o n r e q u e s t t o t h e s t a t i o n w i t h i n a b o u t .3 .5 m i c r o s e c o n d s o f t h e r e t u r n o f t h e p r e v i o u s l y t r a n s m i t t e d p a c k e t . Few m a c h i n e s i f any c a n p r o c e s s a p r o g r a m i n t e r r u p t t h a t f a s t [ 1 1 ] . A n o t h e r p o t e n t i a l p r o b l e m w i t h u s i n g a p r o g r a m m e d i n t e r r u p t i n t e r f a c e i s t h a t i f t h e . l o w l e v e l p r o t o c o l i n t e r a c t i n g w i t h t h e h a r d w a r e i n t e r f a c e were s u f f i c i e n t l y c o m p l e x , t h e n t h e f r e q u e n c y o f i n t e r r u p t s , c o u p l e d w i t h t h e t i m e s p e n t i n h a n d l i n g t h e i n t e r r u p t s i n t h e p r o t o c o l w i l l more o r l e s s make t h e p r o c e s s o r u n a v a i l a b l e t o a l l o t h e r p r o c e s s e s i n t h e s y s t e m . 1 2 2 . 2 . 4 T h e C a m b r i d g e BBP T h e f o l l o w i n g d e s c r i b e s t h e C a m b r i d g e BBP [ 5 , 1 1 ] . R e c e p t i o n • S e t t h e S o u r c e S e l e c t R e g i s t e r ( SSR ) t o l i s t e n t o a n y b o d y . • Any m i n i p a c k e t t h a t a r r i v e s w h i c h d o e s n o t c o n f o r m t o a H e a d e r i s d i s c a r d e d . I f a H e a d e r a r r i v e s , l o c k t h i s s t a t i o n t o l i s t e n e x c l u s i v e l y t o t h e s e n d i n g s t a t i o n . • W a i t f o r t h e P o r t . On i t s a r r i v a l , d e t e r m i n e w h e t h e r t h e p o r t r e c e i v e d i s - a c t i v e on t h e h o s t s y s t e m . I f i t i s n o t , t h e P o r t i s r e j e c t e d a n d t h e SSR i s s e t t o R e j e c t f o r a s h o r t p e r i o d o f t i m e so a s t o i n f o r m t h e r e l e v a n t s o u r c e t o q u i t i t s i n t e n t i o n a b o u t s e n d i n g t h i s p a r t i c u l a r b a s i c b l o c k . • A c c e p t t h e D a t a m i n i p a c k e t s i f e v e r y t h i n g a b o v e went on • f i n e . • R e c e i v e t h e C h e c k s u m . I f t h e r e were no e r r o r s , r e l a y t h e b a s i c b l o c k t o h i g h e r l e v e l , o t h e r w i s e , r e p o r t t h e e r r o r s . T h e SSR i s t h e n r e s e t t o l i s t e n t o a n y b o d y . 1 3 T r a n s m i s s i o n • S e n d t h e H e a d e r . I f t h e r e s p o n s e f r o m t h e d e s t i n a t i o n s t a t i o n i s ' r e j e c t e d ' o r ' b u s y ' , t r y s e n d i n g t h e • H e a d e r a g a i n . • S e n d t h e P o r t . I f t h e r e s p o n s e i s b u s y , t r y a g a i n ; i f u n s e l e c t e d , g i v e u p . • S e n d t h e D a t a . R e t r y on b u s i e s ; i f u n s e l e c t e d , g i v e u p . • S e n d t h e C h e c k s u m u n d e r t h e same r u l e s a s i n s e n d i n g t h e D a t a . B o t h r e c e p t i o n a n d t r a n s m i s s i o n i n c l u d e t h e u se o f t h e T i m e o u t a n d R e t r y mechani sm-s . The T i m e o u t m e c h a n i s m i n v o l v e s t h e u s e o f a t i m e r a n d s e t t i n g i t t o a c o n s t a n t t i m e i n t e r v a l . On t h e e x p i r y o f t h a t i n t e r v a l , t h e c o r r e s p o n d i n g a c t i o n i s a b a n d o n e d . T h e R e t r y m e c h a n i s m s t i p u l a t e s t h e number o f r e p e a t e d a t t e m p t s a l l o w e d f o r an a c t i o n . 1 4 2 . 3 O v e r v i e w Of The B y t e S t r e a m P r o t o c o l T h e B y t e S t r e a m P r o t o c o l (BSP) i s t h e s o f t w a r e l a y e r a b o v e t h e BBP a n d p r o v i d e s t h e f o l l o w i n g s e r v i c e s t o o t h e r s o f t w a r e l a y e r s a b o v e i t : • E r r o r C o r r e c t i o n • F l o w C o n t r o l • L o s t P a c k e t D e t e c t i o n • D u p l i c a t e P a c k e t D e t e c t i o n C o u p l e d w i t h an I n i t i a l C o n n e c t i o n p r o t o c o l s p e c i f i c a t i o n w h i c h i s n o t p a r t o f t h e BSP s p e c i f i c a t i o n i t s e l f , b u t s u p p l e m e n t a r y t o i t , t h e BSP e s s e n t i a l l y p r o v i d e s a V i r t u a 1  C i r c u i t s e r v i c e . 2 . 3 . 1 F o r m a t Of P a c k e t D u r i n g t h e d a t a t r a n s a c t i o n p h a s e , t h a t i s i m m e d i a t e l y a f t e r an an I n i t i a l C o n n e c t i o n , o r a f t e r a r e s e t , t h e u n i t o f c o m m u n i c a t i o n i s a P a c k e t w h i c h c o n s i s t s o f : 1 5 • A R e c e p t i o n Command, r e f e r i n g t o t h e r e c e p t i o n o f d a t a . • A T r a n s m i s s i o n Command, r e f e r i n g . t o t h e t r a n s m i s s i o n o f d a t a . • The D a t a i t s e l f ( i f a n y ) . T o p r o v i d e f o r c o n t r o l i n f o r m a t i o n , w h i c h r e f e r s t o t h e BSP c o n n e c t i o n a s a w h o l e , t h e P a c k e t may j u s t c o n t a i n a c o n t r o l command. T h e two c o n t r o l commands R e s e t a n d C l o s e e n a b l e t h e c o n n e c t i o n t o be r e s e t due t o u n r e s o l v e d e r r o r s a s w e l l a s t o t e r m i n a t e a c o n n e c t i o n . P r o v i s i o n o f f l o w c o n t r o l i s t h r o u g h t h e u s e o f s e q u e n c e n u m b e r s i m b e d d e d i n t h e commands t h e m s e l v e s . In t h i s d e s c r i p t i o n , t h e . s e q u e n c e number i s d e n o t e d a s ' n ' i m m e d i a t e l y a f t e r t h e command-name ; e . g . DATA n . Two a d d i t i o n a l c o n t r o l commands a r i s i n g f r o m t h e I n i t i a l C o n n e c t i o n p r o t o c o l a r e OPEN a n d OPENACK ; h o w e v e r t h e p r o c e d u r e i n v o l v e d i n s e t t i n g up t h e c o n n e c t i o n i s i r r e l e v a n t h e r e . 2 . 3 . 2 Mode Of O p e r a t i o n T h e t r a n s a c t i o n s b e t w e e n two c o m m u n i c a t i n g p a r t i e s a l t e r n a t e b e t w e e n two p h a s e s . D u r i n g d a t a t r a n s f e r , i t i s i n a d a t a t r a n s a c t i o n p h a s e a n d d u r i n g t h e e x c h a n g e o f c o n t r o l i n f o r m a t i o n , i t i s i n a c o n t r o l t r a n s a c t i o n p h a s e . We s h a l l f i r s t d e s c r i b e t h e mode o f o p e r a t i o n d u r i n g t h e d a t a t r a n s a c t i o n p h a s e . When a t r a n s m i t t i n g h o s t h a s d a t a t o s e n d , a DATA n i s s e n t ; o t h e r w i s e i t s e n d s a NODATA n . When t h e r e c e i v i n g h o s t i s r e a d y t o r e c e i v e d a t a , i t s e n d s a RDY n ; o t h e r w i s e a NOTRDY n i s s e n t . B o t h r e c e p t i o n commands RDY n a n d NOTRDY n a c k n o w l e d g e 1 6 t h e p r e v i o u s DATA n - 1 r e c e i v e d f r o m t h e t r a n s m i t t i n g h o s t . T r a n s m i s s i o n o f a DATA n or a RDY n i n v o l v e s s e t t i n g a t i m e r a n d e x p e c t s an a c k n o w l e d g e m e n t b e f o r e t h e t i m e r e x p i r e s . B e c a u s e i t e x p e c t s an a c k n o w l e d g e m e n t , DATA n a n d RDY n a r e s o m e t i m e s r e f e r r e d t o a s e s s e n t i a l e l e m e n t s . By t h e same t o k e n , NODATA n a n d NOTRDY n a r e r e f e r r e d t o a s n o n - e s s e n t i a l e l e m e n t s a s t h e y do n o t e x p e c t an a c k n o w l e d g e m e n t i n r e p l y . When t h e t i m e r e x p i r e s o r t i m e o u t s , t h e e s s e n t i a l e l e m e n t i s s e n t a g a i n . T h e number o f r e p e a t e d a t t e m p t s o r r e t r i e s made b e f o r e t h e a t t e m p t i s g i v e n up i s i m p l e m e n t a t i o n d e p e n d e n t . 2 . 3 . 3 BSP S t a t e T r a n s i t i o n T h e c o n t r o l f l o w o f . t h e BSP w i t h t h e e x c e p t i o n o f t h e c o n t r o l commands i s e x p r e s s e d i n t h e f o l l o w i n g s t a t e t r a n s i t i o n d i a g r a m : >v F.VC lit fi <\\% Timeout Buffer ready State N . D A T A n . 1 / R D Y n D A T A n / R D Y n t | N O D A T A „ / N O T R D Y n + | Retransmit Empty/fi l l buffer Retransmit R D Y n / D A T A „ n+: = 1 R D Y „ / D A T A „ Buffer ready? E . yes: no: RDY„ N O T R D Y , , / D A T A n / N O D A T A , , I- fi N 1 I: I-Retry nsmil Protocol Protocol Transmit N O T R D Y , , / N O D A T A , , error error K D Y n / O A T A n N N - N E Protocol Bmply/t i l l buffer — — — error n+: = | J Buffer ready? 1 yes: no: B D Y ; N O T R D Y , , / D A T A , II / N O D A T A , , N 1 1 1 18 T h e r e a r e t h r e e s t a t e s a n d f i v e e v e n t s . S t a t e s E E x p e c t i n g an A c k n o w l e d g e m e n t . ( i . e . a DATA n o r RDY n was p r e v i o u s l y s e n t ) N A n o n - e s s e n t i a l e l e m e n t was s e n t . ( i . e . a NODATA n o r NOTRDY n was s e n t ) I I d l e s t a t e . A n o n - e s s e n t i a l e l e m e n t was r e c e i v e d i n r e p l y . (NOTRDY n-1 o r NODATA n was r e c e i v e d ) E v e n t s E _ r e p E _ e x p N _ e x p T i m e o u t B u f f e r R e a d y An e s s e n t i a l e l e m e n t w h i c h i s a r e p e t i t i o n o f an e a r l i e r e s s e n t i a l e l e m e n t i s r e c e i v e d ; i . e . a RDY n o r DATA n-1 ha s b e e n r e c e i v e d . An e s s e n t i a l e l e m e n t w i t h t h e e x p e c t e d s e q u e n c e number i s r e c e - i v e d ; i . e . a RDY n+1 o r DATA n . A n o n - e s s e n t i a l e l e m e n t w i t h t h e e x p e c t e d s e q u e n c e number i s r e c e i v e d ; i . e . a NOTRDY n+1 o r NODATa n . E x p i r y o f t i m e r w h i l e w a i t i n g f o r an a c k n o w l e d g e m e n t . A b i l i t y t o r e c e i v e more d a t a o r h a s d a t a t o s e n d . T h e two c o n t r o l commands R e s e t a n d C l o s e p e r t a i n t o . t h e B y t e S t r e a m c o n n e c t i o n a s a w h o l e . The e x c h a n g e o f t h e s e c o n t r o l commands c o n s t i t u t e t h e c o n t r o l t r a n s a c t i o n p h a s e . .When a R e s e t i s s e n t , a l l r e c e i v e d d a t a s h o u l d be i g n o r e d u n t i l a R e s e t i s r e c e i v e d i n r e p l y . An u n e x p e c t e d R e s e t r e c e i v e d e l i c i t s a R e s e t s e n t i n r e p l y . T h e C l o s e i s a n a l o g o u s t o t h e R e s e t . B o t h commands s e n t a s a r e q u e s t r a t h e r t h a n a r e p l y w o u l d e m p l o y t h e T i m e o u t a n d R e t r y m e c h a n i s m s t o e n s u r e t h a t t h e o t h e r h o s t h a s n o t a l r e a d y t e r m i n a t e d t h e c o n n e c t i o n a n d i s u n a v a i l a b l e t o r e p l y . 19 2 . 3 . 4 I n i t i a l S t a t e ' I n i t i a l l y a f t e r a c o n n e c t i o n i s made a n d a f t e r a R e s e t , t h e r e c e i v e r s s h o u l d be i n s t a t e N w i t h s e q u e n c e number 0 , a n d t h e t r a n s m i t t e r s h o u l d be i n s t a t e I w i t h s e q u e n c e number - 1 . As s o o n a s t h e r e c e i v e r h a s b u f f e r s p a c e f o r t h e f i r s t P a c k e t ( B u f f e r R e a d y E v e n t ) , i t w i l l s e n d a RDY 0 a n d go t o s t a t e E . T h e t r a n s m i t t e r r e g a r d s t h i s a s e v e n t E _ e x p , i n c r e m e n t s i t s s e q u e n c e number t o 0 a n d t r a n s m i t s e i t h e r DATA 0 o r NODATA 0 . 2 . 3 . 5 T i m e r s T h e r e a r e two t i m e r s , a N o r m a l t i m e r a n d an I d l e H a n d s h a k e t i m e r . T h e I d l e H a n d s h a k e "~ t i m e r i s i n v o k e d o n l y when t h e t r a n s a c t i o n i s i n s t a t e I . T h i s i s t o p r e v e n t a p e r p e t u a l w a i t f o r an E _ e x p e v e n t when t h e o t h e r h o s t i s no l o n g e r a v a i l a b l e a n d i s u n a b l e t o r e p l y . T h e N o r m a l t i m e r , a s t h e name i m p l i e s , i s i n v o k e d a t t i m e s o t h e r t h a n t h e I s t a t e a n d when an e s s e n t i a l e l e m e n t i s s e n t . T h e t i m e d u r a t i o n f o r t h e N o r m a l t i m e r i s i n t h e o r d e r o f one o r more s e c o n d s , a s o p p o s e d t o one m i n u t e f o r t h e I d l e H a n d s h a k e t i m e r . 20 I I I . I M P L E M E N T A T I O N ENVIRONMENT 3 . 1 I n t r o d u c t i o n One common i s s u e w h i c h a r i s e s i n p r o t o c o l i m p l e m e n t a t i o n s i s where t h e p r o t o c o l s h o u l d r e s i d e [ 2 ] , T h e p r o t o c o l may e i t h e r r e s i d e , i n t h e k e r n e l o f t h e o p e r a t i n g s y s t e m i t s e l f , i n a p r o c e s s p r o v i d e d by t h e o p e r a t i n g s y s t e m o r b o t h . T h e d e c i s i o n made w o u l d be s t r o n g l y i n f l u e n c e d by t h e m a c h i n e a r c h i t e c t u r e a n d t h e o p e r a t i n g s y s t e m d e s i g n . UNIX a s s u m e s two modes o f o p e r a t i o n : u s e r a n d k e r n e l m o d e s . T h e r e l a t i v e l y s m a l l r e s i d e n t UNIX k e r n e l i s a p r i v i l e d g e d a n d p r o t e c t e d s e c t i o n o f c o d e . D e s i g n e d t o be s i m p l i s t i c , i t p r o v i d e s t h e e s s e n t i a l s e r v i c e s o f p r o c e s s m a n a g e m e n t , c l o c k m a n a g e m e n t , i n t e r p r o c e s s c o m m u n i c a t i o n ( I P C ) a n d a g e n e r a l p u r p o s e i n p u t / o u t p u t m e c h a n i s m . T h e k e r n e l i n t e r a c t s d i r e c t l y w i t h t h e h a r d w a r e a n d p r o v i d e s t h e a b s t r a c t i o n a n d a d m i n i s t r a t i o n o f t h e h a r d w a r e r e s o u r c e s t o h i g h e r l a y e r s o f t w a r e a b o v e i t . D e v i c e d r i v e r s i n UNIX a r e e a s i l y a c c e s s e d t h r o u g h t h e UNIX I / O s y s t e m . T h e I / O s y s t e m u s e s t h e same c l e a n i n t e r f a c e o f t h e f i l e s y s t e m . T h e r e a r e o n l y two t y p e s o f f i l e s i n U N I X : O r d i n a r y f i l e s a n d S p e c i a l F i l e s . S p e c i a l f i l e s r e p r e s e n t d e v i c e s a n d a r e u s e d t o c o n t a i n t h e d e v i c e d r i v e r s . T h e B a s i c B l o c k P r o t o c o l (BBP) w h i c h i n t e r a c t s d i r e c t l y w i t h t h e R i n g h a r d w a r e i n t e r f a c e i s t h u s i m p l e m e n t e d a s ' a d e v i c e 2 1 d r i v e r u s i n g t h e f o l l o w i n g f i l e s y s t e m i n t e r f a c e : • Open • R e a d • W r i t e • C l o s e • I o c t l F o r p r o t o c o l e f f i c i e n c y r e a s o n s , i t w o u l d a l s o be d e s i r a b l e f o r t h e BSP t o r e s i d e i n t h e k e r n e l . H o w e v e r , t h e UNIX k e r n e l e n v i r o n m e n t p r o h i b i t s t h i s . T h e UNIX k e r n e l , b o t h by t h e d e s i g n a n d t h e p h y s i c a l l i m i t a t i o n s o f t h e L S I 11 / 23 ( a d d r e s s s p a c e o f 64K b y t e s ) , i s l i m i t e d t o t h e m o s t b a s i c o f f u n c t i o n s . The UNIX k e r n e l i n t h e L S I 11 / 2 3 m a c h i n e i n c o r p o r a t e s t h e o v e r l a y c o n c e p t . T h e mos t i m p o r t a n t a n d u n m o d i f i a b l e body o f c o d e a n d t h e d a t a a r e a s a r e a l w a y s r e s i d e n t i n memory ; t h e r e s t i s c o n t a i n e d i n o v e r l a y s o f s i z e 8K b y t e s e a c h . A t a n y one t i m e , t h e r e i s o n l y one o v e r l a y r e s i d i n g i n m e m o r y . In u s i n g o v e r l a y s , t h e o b j e c t i v e i s t o m i n i m i z e o v e r l a y s w a p p i n g by p l a c i n g r e l a t e d c o d e t o g e t h e r i n one o v e r l a y . C a l l i n g f o r s e r v i c e s w h i c h i s l o c a t e d i n o t h e r o v e r l a y s i n v o l v e s s w a p p i n g o f t h e c u r r e n t o v e r l a y w i t h t h e d e s i r e d one i n b a c k i n g s t o r e . Due t o i t s r e q u i r e m e n t f o r b u f f e r s o f s i z e 2K b y t e s e a c h , t h e BSP w o u l d n o t f i t i n t o t h e t i g h t l y c o n s t r a i n e d s p a c e l e f t i n t h e r e s e r v e d d a t a a r e a s o f t h e k e r n e l . A l t h o u g h one may r e d u c e t h e s i z e o f b u f f e r s t o a c c o m m o d a t e them i n t o t h e d a t a a r e a s o f t h e k e r n e l , t h e BSP t e x t w o u l d n e v e r t h e l e s s r e q u i r e a t l e a s t two o v e r l a y s ( u n l e s s we c o u l d r i d i c u l o u s l y p r e s u m e t h e BSP t o be o f 22 s i z e 8 K ) . T h u s t h e e x e c u t i o n o f t h e BSP i t s e l f i n v o l v e s s w a p p i n g . I f t h e BBP i s n o t p l a c e d i n " a n y o f t h e o v e r l a y s o c c u p i e d by t h e B S P , t h e n f r e q u e n t s w a p p i n g o f o v e r l a y s w i l l o c c u r s i n c e t h e BSP f r e q u e n t l y r e q u i r e s t h e s e r v i c e s o f t h e B B P . I n a d d i t i o n b o t h t h e BBP a n d t h e BSP r e q u i r e s e r v i c e s f r o m o t h e r k e r n e l r o u t i n e s , s u c h a s c o p y i n g o f d a t a f r o m k e r n e l t o u s e r s p a c e , c l o c k r o u t i n e s a n d p r o c e s s o r p r i o r i t y m a n i p u l a t i o n r o u t i n e s . C o n s e q u e n t l y , t h e r e w i l l be o v e r l a y s w a p p i n g ; t h e s w a p p i n g f r e q u e n c y , h o w e v e r , c o u l d be m i n i m i z e d by a c a r e f u l r e a r r a n g e m e n t o f t h e c o n t e n t s o f t h e o v e r l a y s . C o m m u n i c a t i o n p r o t o c o l s w h i c h a r e t i m e - c r i t i c a l i n n a t u r e may n o t f u n c t i o n c o r r e c t l y i f i t s p e r f o r m a n c e d e g r a d e s d r a m a t i c a l l y a s a r e s u l t o f t h e i n o r d i n a t e amount o f d i s k a c t i v i t i e s a r i s i n g f r o m s w a p p i n g . B e s i d e s t h e c o n s t r a i n t s , t h e r e a r e o t h e r d i s a v a n t a g e s i n i m p l e m e n t i n g t h e BSP i n t h e k e r n e l . One m a j o r d i s a d v a n t a g e i s t h a t s i n c e t h e k e r n e l i s a l a r g e b o d y o f c o d e , i t w o u l d t a k e a c o n s i d e r a b l e number of . a t t e m p t s t o r e c o m p i l e t h e o p e r a t i n g s y s t e m i n w h i c h t h e new k e r n e l c o d e i s t o be t e s t e d . F o r t h e L S I 11 /23 m a c h i n e , i t t o o k an a v e r a g e o f f i v e m i n u t e s t o s e t up a n d p e r f o r m a f i l e s y s t e m c h e c k . S e c o n d l y , t h e n a t u r e o f c o m p l e x i t y i n t h e r e s u l t i n g i m p l e m e n t a t i o n c o d e f o r t h e BSP r e n o u n c e s t h e v e r y p r i n c i p l e o f t h e UNIX k e r n e l d e s i g n o f s i m p l i c i t y . L a s t l y , t h e k e r n e l c o d e i s one l a r g e m o n o l i t h i c p i e c e o f c o d e w h i c h i s a f f e c t e d by t h e e r r o r s o f a n y c o m p o n e n t p a r t o f i t . T h e a b o v e d e t e r r e n t s more t h a n j u s t i f y t h e p l a c e m e n t o f t h e 23 BSP c o d e a t t h e u s e r l e v e l . However, p l a c i n g t h e code a t t h e u s e r l e v e l i m p l i e s t h a t p r o c e s s s c h e d u l i n g c a n be a s i g n i f i c a n t s o u r c e of r e a l t i m e d e l a y and t h e i n a d e q u a t e i n t e r p r o c e s s c o m m u n i c a t i o n (IPC) f a c i l i t y o f UNIX w o u l d h i n d e r t h e d e v e l o p m e n t a n d e f f i c i e n c y o f t h e p r o t o c o l . F o r e f f i c i e n c y r e a s o n s , i t w o u l d be i d e a l t o have t h e BSP r u n n i n g i m m e d i a t e l y a f t e r s y s t e m b o o t i n g . T h i s may be r e a l i z e d i n UNIX by making i t a daemon p r o c e s s , t h a t i s a p r o c e s s owned by t h e s y s t e m . T h i s i s d e s i r a b l e as b a s i c b l o c k s may a r r i v e f r o m o t h e r s t a t i o n s on t h e R i n g even t h o u g h t h e r e i s no a c t i v e p o r t c u r r e n t l y a v a i l a b l e . A n o t h e r a p p a r e n t e f f i c i e n c y i s t h a t any u s e r w i s h i n g t o u s e t h e n e t w o r k c a n a c c e s s t h e BSP s e r v i c e s w i t h o u t much d e l a y . I s t h i s c o n c e p t f e a s i b l e i n UNIX ? I t i s p o s s i b l e i n UNIX i f t h e MPX f i l e s a r e w o r k i n g c o r r e c t l y . MPX f i l e s a r e m u l t i p l e x e d f i l e s w h i c h e n a b l e 1 t o n number o f p r o c e s s e s t o communicate w i t h one a n o t h e r t h r o u g h .the owner o f t h e MPX f i l e . The owner o f t h e MPX f i l e h as t o p e r f o r m t h e n e c e s s a r y m u l t i p l e x i n g o f m e s s a g e s t o t h e v a r i o u s p r o c e s s e s . The c o m m u n i c a t i n g p r o c e s s e s need n o t be " r e l a t e d " ( s e e s e c t i o n on " F o r k s and P i p e s " ) i n o r d e r t o c o m m u n i c a t e . However MPX f i l e s a r e an e x p e r i m e n t a l p a r t o f t h e UNIX s y s t e m and i s n o t w o r k i n g as s p e c i f i e d i n t h e v e r s i o n t h a t we h a v e . The f a c t t h a t i n d e p e n d e n t o r n o n - r e l a t e d p r o c e s s e s c a n n o t communicate w i t h one a n o t h e r i n a s i m p l e and e f f i c i e n t - way d r a s t i c a l l y a f f e c t s t h e s t r u c t u r e o f t h e BSP. 24 3 .2 I n t e r p r o c e s s C o m m u n i c a t i o n In UNIX T h e n a t u r e o f c o m m u n i c a t i o n p r o t o c o l s d i c t a t e s a s t r u c t u r e o f c o o p e r a t i n g p r o c e s s e s w i t h a m a i n p r o c e s s a c t i n g a s a c o o r d i n a t o r o r S e r v e r . E a c h p r o c e s s p e r f o r m s a f u n c t i o n i n d e p e n d e n t l y a n d r e p o r t s t o t h e S e r v e r o f t h e c o m p l e t i o n o r a r r i v a l o f an e v e n t . We may t h i n k o f s u c h a m o d e l a s t h e i n t e r a c t i o n o f a S e r v e r p r o c e s s a n d a number o f C l i e n t o r W o r k e r p r o c e s s e s . T h e S e r v e r p r o c e s s e s r e q u e s t s / s e r v i c e s f r o m i t s C l i e n t / W o r k e r p r o c e s s e s ( s e e F i g . 1 0 ) . T h e u n d e r l y i n g m o t i v a t i o n f o r s u c h a m o d e l s t e m s f r o m t h e n e e d t o p r o m o t e e f f i c i e n c y t h r o u g h c o n c u r r e n c y . F o r e x a m p l e , we c o u l d h a v e t h e S e r v e r d e l e g a t e t h e t a s k s o f r e a d i n g a n d t r a n s m i t t i n g o f b a s i c b l o c k s t o two W o r k e r p r o c e s s e s s u c h t h a t t h e S e r v e r i s f r e e t o p e r f o r m o t h e r f u n c t i o n s . S u c h a m o d e l c l e a r l y r e f l e c t s t h e n a t u r e o f p r o t o c o l s w h i c h a r e c h a r a c t e r i z e d by i s s u e s s u c h a s a s y n c h r o n y , c o n c u r r e n c y a n d t i m e - c r i t i c a l r e s p o n s e s . We s h a l l now see how UNIX s u p p o r t s s u c h a r e q u i r e m e n t o f c o o p e r a t i n g p r o c e s s e s . 3 . 2 . 1 F o r k s A n d P i p e s C r e a t i n g a p r o c e s s i n UNIX i n v o l v e s m a k i n g a c o p y o f i t s e l f by i s s u i n g t h e s y s t e m c a l l f o r k . T h e new p r o c e s s i s d e n o t e d t h e c h i l d p r o c e s s a n d t h e c r e a t o r o f t h e new p r o c e s s , t h e p a r e n t . T h e r e i s an e x p l i c i t r e l a t i o n s h i p b e t w e e n p a r e n t a n d c h i l d , a n d t h i s i n f o r m a t i o n i s r e c o r d e d i n t o t h e s y s t e m t a b l e s . The c h i l d p r o c e s s h a s i t s own u n i q u e 16 b i t p r o c e s s - i d a n d i n h e r i t s f r o m t h e p a r e n t a l l t h e f i l e s t h a t were o p e n e d b e f o r e t h e f o r k . I t 25 has i t s own a d d r e s s s p a c e , i m p l y i n g i t s own d a t a a n d s t a c k a r e a s . T h e t e x t may be s h a r e d s i n c e t e x t a r e p l a c e d i n r e a d -o n l y s e g m e n t s . T h e s h a r e d o p e n e d f i l e s a r e t h e o n l y common l i n k t h r o u g h w h i c h t h e IPC i n UNIX i s f o u n d e d . The e x a m p l e b e l o w i l l u s t r a t e s t h e c r e a t i o n o f m u l t i p l e p r o c e s s e s . i f ( ( i d = f o r k O ) == -1 ) { p e r r o r ( ) ; r e t u r n ; } i f ( i d == 0 ) { / * c h i l d p r o c e s s ' s s e c t i o n o f c o d e * / } e l s e { / * p a r e n t p r o c e s s ' s s e c t i o n o f c o d e * / } T h e f o r k s y s t e m c a l l r e t u r n s -1 i f t h e r e was an e r r o r . T h e e r r o r c o u l d be c a u s e d by v a r i o u s r e a s o n s s u c h a s t h e d e p l e t i o n o f s y s t e m r e s o u r c e s o r t h e number o f p r o c e s s e s a c t i v e Binder t h i s u s e r e x c e e d s t h e maximum a l l o w e d . " p e r r o r " i s a l i b r a r y r o u t i n e w h i c h p r i n t s o u t t h e e r r o r m e s s a g e . T h e p r o c e s s - i d r e t u r n e d f r o m t h e f o r k w i t h i n t h e c h i l d p r o c e s s i s 0 a n d w i t h i n t h e p a r e n t p r o c e s s , t h e new c h i l d p r o c e s s - i d , w h i c h i s n e v e r z e r o . E x t r e m e c a r e s h o u l d be t a k e n a f t e r t h e f o r k s i n c e t h e r e t u r n o f t h e c a l l i s i n t h e same l o c a t i o n f o r b o t h t h e c h i l d a n d p a r e n t . T h i s i s b e c a u s e t h e c h i l d i s an e x a c t c o p y o f t h e p a r e n t . C o m m u n i c a t i o n b e t w e e n two p r o c e s s e s i s o f t e n d o n e t h r o u g h p i p e s . A p i p e i s a s p e c i a l k i n d o f f i l e t h a t p r o v i d e s a one way means o f c o m m u n i c a t i o n . One e n d o f t h e p i p e r e a d s a n d t h e o t h e r e n d w r i t e s . T o p r o v i d e a d i a l o g u e , two p i p e s a r e t h e r e f o r e n e e d e d . 26 An e x a m p l e : ma i n ( ) { i n t p i p [ 2 ] ; c h a r b u f l [ l 0 ] , * s t r i n g ; i f ( ( p i p e ( p i p ) ) == -1 ) { p e r r o r ( ) ; r e t u r n ; } i f ( ( i d = f o r k ( ) ) == -1 ) { p e r r o r ( ) ; r e t u r n ; } i f ( i d == 0 ) { / * c o d e f o r c h i l d * / c l o s e ( • p i p [ 1 ] ) ; / * c l o s e w r i t i n g e n d o f p i p e * / r e a d ( p i p [ 0 ] , b u f 1 , 1 0 ) ; e x i t ( ) ; } e l s e { / * c o d e f o r p a r e n t * / ~ c l o s e ( p i p [ 0 ] ) ; / * c l o s e r e a d i n g e n d o f p i p e * / s t r i n g = "Go Home ". ; w r i t e ( p i p [ 1 ] ,• s t r i n g , 10) ; } } T h e p i p e r o u t i n e r e q u i r e s a s p a r a m e t e r a two c o m p o n e n t i n t e g e r a r r a y . I t r e t u r n s t h e f i l e d e s c r i p t o r s f o r r e a d i n g a n d w r i t i n g i n t o t h e a r r a y i n r e s p e c t i v e l o c a t i o n s . F i l e d e s c r i p t o r s i n UNIX a r e i n t e g e r s u s e d t o i d e n t i f y f i l e s d u r i n g f i l e o p e r a t i o n s . I n t h e e x a m p l e a b o v e , t h e p r o c e s s r e a d i n g f r o m t h e p i p e h a s t o ' c l o s e t h e w r i t i n g e n d o f t h e p i p e ; s i m i l a r l y t h e p r o c e s s w r i t i n g t o t h e p i p e c l o s e s i t s r e a d i n g e n d . T h e c l o s i n g o f t h e w r i t i n g e n d i s m a n d a t o r y f o r t h e r e a d i n g p r o c e s s . T h i s i s b e c a u s e r e a d s a r e b l o c k e d u n t i l t h e r e i s s o m e t h i n g t o r e a d o r an e n d - o f - f i l e o c c u r s . N o t h a v i n g c l o s e d i t s own w r i t i n g e n d o f 27 t h e p i p e w o u l d c a u s e t h e r e a d t o be p e r p e t u a l l y b l o c k e d a s t h e e n d - o f - f i l e w i l l n e v e r be r e a d . P i p e s p r o v i d e f l o w c o n t r o l a n d a b u f f e r o f s i z e 4096 b y t e s f o r m e s s a g e s a r r a n g e d i n a F I F O q u e u e . W r i t i n g t o a p i p e w o u l d n o t be b l o c k e d u n l e s s t h e p i p e i s f u l l . T h e p i p e m e c h a n i s m may be e x t e n d e d t o p r o v i d e f o r many W o r k e r p r o c e s s e s t o c o m m u n i c a t e w i t h t h e S e r v e r p r o c e s s t h r o u g h a s i n g l e p i p e . T h e r e a d i n g e n d s o f t h e p i p e f o r a l l t h e W o r k e r p r o c e s s e s a r e c l o s e d w h i l e t h e w r i t i n g e n d o f t h e p i p e f o r t h e S e r v e r p r o c e s s i s c l o s e d . A d d i t i o n a l p i p e s may be p r o v i d e d t o d e s i g n a t e d W o r k e r p r o c e s s e s t o f a c i l i t a t e two way c o m m u n i c a t i o n w i t h t h e S e r v e r . S i n c e t h e p i p e q u e u e s t h e r e q u e s t s , m u l t i p l e e v e n t s i n h e r e n t i n p r o t o c o l i m p l e m e n t a t i o n c o u l d be r e a l i z e d i n a c h r o n o l o g i c a l f a s h i o n . 3 . 2 . 2 L o c k e d F i l e s A n d S i g n a l s O r d i n a r y f i l e s may a l s o be u s e d by p r o c e s s e s f o r i n t e r c o m m u n i c a t i o n . To p r o v i d e s y n c h r o n i z a t i o n when u s i n g f i l e s , " l o c k s " may be p l a c e d on f i l e s so a s t o e n s u r e m u t u a l e x c l u s i o n o f s h a r e d d a t a . A p r o c e s s w i s h i n g t o a c c e s s t h e s h a r e d f i l e w o u l d o n l y be a l l o w e d i f t h e f i l e i s " u n l o c k e d " . D u r i n g a c c e s s , t h e f i l e w o u l d a p p e a r l o c k e d t o a l l o t h e r p r o c e s s e s a t t e m p t i n g t o a c c e s s i t . T h e l a s t a v a i l a b l e means o f i n t e r p r o c e s s c o m m u n i c a t i o n i s t h r o u g h " s i g n a l s " . S i g n a l s a r e s o f t w a r e i n t e r r u p t s w h i c h c o u l d be u s e d t o i n f o r m a p r o c e s s t h a t an e v e n t h a s h a p p e n e d . The e v e n t i s r e p r e s e n t e d a s an a r b i t r a r y i n t e g e r , u s u a l l y p o s s e s s i n g 28 s i g n i f i c a n c e o n l y t o t h e c o m m u n i c a t i n g p a r t i e s c o n c e r n e d . S i g n a l s m a i n l y p r o v i d e s y n c h r o n i z a t i o n s i n c e i t c o u l d o n l y h o l d an i n t e g e r s i z e w o r t h o f i n f o r m a t i o n . A p r o c e s s u t i l i z i n g s i g n a l s must p r o v i d e a s i g n a l h a n d l i n g r o u t i n e . When a s i g n a l a r r i v e s , c o n t r o l i s p a s s e d t o t h i s s i g n a l h a n d l i n g r o u t i n e . I f no s u c h r o u t i n e e x i s t s , t h e p r o c e s s i s t e r m i n a t e d . The c o n c e p t i s s i m i l a r t o t h e i n t e r r u p t h a n d l i n g r o u t i n e s u s e d f o r I / O d e v i c e s . O c c a s i o n a l l y , s i g n a l s h a v e t h e u n d e s i r a b l e e f f e c t o f a b o r t i n g a p a r t i a l l y c o m p l e t e d s y s t e m c a l l " . T h u s , u s a g e o f s i g n a l s i n v o l v e s an i n c o r p o r a t i o n o f a c h e c k i n g m e c h a n i s m when s y s t e m c a l l s a r e u s e d . T h i s i s t o d e t e r m i n e w h e t h e r a f a i l u r e o f a s y s t e m c a l l i s g e n u i n e o r a c o n s e q u e n c e o f t h e s i g n a l a r r i v a l . 29 3 . 3 Design Overview The UNIX environment thus d i c t a t e s the fundamental d e s i g n s t r u c t u r e of the BSP. I t s in a d e q u a c i e s , b e s i d e s i t s impact on the p r o t o c o l e f f i c i e n c y , i s m a n i f e s t e d c h i e f l y i n the f o l l o w i n g a s p e c t s of the f i n a l d e s i g n : • M u l t i p l e x i n g of users • User I n t e r f a c e • A d m i n i s t r a t i o n of IPC Before we dwe l l on the ina d e q u a c i e s of UNIX, a b r i e f d e s c r i p t i o n on the BSP de s i g n i s a p p r o p r i a t e here. The f i n a l d e s i g n of the BSP i n v o l v e s two Cl i e n t / W o r k e r p r o c e s s e s , namely the. User and the Reader, i n t e r a c t i n g with the Server (see F i g . 6) . The User - - s y m b o l i z i n g the user-- p r o c e s s e s the requests from the user and the s e r v i c e s rendered from the Ser v e r . The Reader performs the r e l a y of the b a s i c b l o c k s read from the Ring d r i v e r to the S e r v e r . Although the t r a n s m i s s i o n of b a s i c b l o c k s may a l s o be performed by another Worker p r o c e s s , t h i s i s not done; we s h a l l see the j u s t i f i c a t i o n f o r t h i s i n chapter v. 3 . 3 . 1 M u l t i p l e x i n g Of Users The assignment of Port numbers to f a c i l i t a t e i d e n t i f i c a t i o n and m u l t i p l e x i n g of users has to be done at the k e r n e l l e v e l . T h i s n e c e s s i t y a r i s e s from the i n a b i l i t y of n o n - r e l a t e d p r o c e s s e s to communicate with one another. That i s to say the 30 p r o s p e c t of a s i n g l e S e r v e r p r o c e s s i n t e r a c t i n g w i t h one o r more i n d e p e n d e n t U s e r p r o c e s s e s i s n o t f e a s i b l e . E a c h u s e r t h e r e f o r e has i t s own BSP p r o c e s s . The a d m i n i s t r a t i o n o f p o r t s i s p r o v i d e d by means o f two s y s t e m ' c a l l s : • c r e a t p o r t ( ) • r e l p o r t O - c r e a t p o r t ( r e a d e r - i d ) r e t u r n s a p o r t n u m b e r , o t h e r w i s e i t r e t u r n s - 1 . T h e p a r a m e t e r p a s s e d i s t h e p r o c e s s - i d o f t h e R e a d e r . ' - r e l p o r t ( p o r t n o ) makes a v a i l a b l e t h e p o r t n o t o be r e u s e d . T o r e c o r d t h e a s s i g n m e n t o f p o r t s t o p r o c e s s e s a n d t o a d m i n i s t r a t e t h e a v a i l a b l e p o r t n u m b e r s , a s y s t e m t a b l e , p o r t - p r o c i d i s c r e a t e d . T h e p o r t n u m b e r s a n d t h e c o r r e s p o n d i n g p r o c e s s - i d s a r e u t i l i z e d by t h e BBP t o p a s s t h e a r r i v e d b a s i c b l o c k t o t h e a p p r o p r i a t e R e a d e r o f t h e BSP S e r v e r . When t h e R i n g d e v i c e d r i v e'r i s f i n a l l y c l o s e d , t h e e n t r i e s i n t h i s s y s t e m t a b l e a r e e r a s e d . T h e f i g u r e b e l o w g r a p h i c a l l y d e p i c t s t h e f i n a l d e s i g n o f t h e BSP a n d t h e u n d e r l y i n g B B P . 31 P r o c e s s - i ds i g u r e 6 - O v e r a l l D e s i g n o f BSP a n d BBP 32 3 . 3 . 2 U s e r I n t e r f a c e S i n c e u n r e l a t e d p r o c e s s e s may o n l y c o m m u n i c a t e t h r o u g h f i l e s , t h e i n t e r f a c e f o r u s e r s t o a c c e s s t h e s e r v i c e s o f BSP may be d o n e u s i n g a l o c k e d f i l e ; e n a b l i n g an a w k w a r d , s l o w a n d l i m i t e d means o f i n t e r a c t i o n . I t s l i m i t a t i o n s r e s t on t h e s y n c h r o n i z a t i o n a n d i d e n t i f i c a t i o n o f t h e r e a d s a n d w r i t e s f r o m b o t h t h e a c t u a l u s e r a n d t h e U s e r p r o c e s s . S e r v e r . T h i s i n t e r a c t i o n w i t h t h e u s e r i s n o t p a r t o f t h e BSP a n d i s c o n s e q u e n t l y a p r o t o c o l i t s e l f , u t i l i z i n g t h e s e r v i c e s o f t h e BSP a n d r e s i d e s i n a p r o c e s s owned by t h e BSP t h r o u g h a f o r k ( i . e . t h i s p r o t o c o l w i l l r e s i d e i n t h e U s e r p r o c e s s ) . W i t h s u c h a c o n s t r a i n t , t h e s e r v i c e ' s o f t h e C a m b r i d g e R i n g may o n l y be u t i l i z e d i n a s i m p l e f i l e t r a n s f e r s e r v i c e ; t h i s i s b e c a u s e o t h e r t y p e s o f s e r v i c e s may o n l y be r e a l i z e d i n more d i f f i c u l t w a y s . • 3 . 3 . 3 A d m i n i s t r a t i o n Of I P C T h e f i n a l d e s i g n i n v o l v i n g t h e S e r v e r i n t e r a c t i n g w i t h t h e U s e r a n d R e a d e r p r o c e s s e s i s r e a l i z e d t h r o u g h t h e u se o f a s i n g l e p i p e m u l t i p l e x i n g b o t h C l i e n t p r o c e s s e s . C a r e i s t a k e n t o e n s u r e t h a t t h e a p p r o p r i a t e e n d s o f t h e p i p e a r e c l o s e d a n d a m e s s a g e f o r m a t i s d e s i g n e d t o f a c i l i t a t e i d e n t i f i c a t i o n a n d m u l t i p l e x i n g o f t h e C l i e n t p r o c e s s e s . T h e mes sage i s made up o f a c o n t r o l ' p a r t a n d a d a t a p a r t . T h e c o n t r o l p a r t , a s t h e name i m p l i e s , c o n t a i n s i n f o r m a t i o n t h a t i d e n t i f i e s t h e p r o c e s s a s w e l l a s t h e t y p e o f r e q u e s t s . I f . t h e r e i s d a t a a t t a c h e d , t h e c o n t r o l p a r t a l s o c o n t a i n s t h e l e n g t h o f d a t a t o be r e a d i n . 33 T h e f o r m a t o f t h e b u f f e r u s e d b e t w e e n t h e BSP a n d t h e R i n g d e v i c e d r i v e r a n d t h e f o r m a t u s e d h e r e a r e u n a v o i d a b l y d i f f e r e n t . C o n s e q u e n t l y t h e r e i s c o p y i n g o f d a t a t o o v e r c o m e d i f f e r e n t f o r m a t s o f b u f f e r u s e d . 34 I V . B A S I C BLOCK PROTOCOL I M P L E M E N T A T I O N 4.1 E x i s t i n g BBP I m p l e m e n t a t i o n T h e r e i s an e x i s t i n g i m p l e m e n t a t i o n o f t h e BBP on a TI 9 9 0 . I t i s a s i m p l e i m p l e m e n t a t i o n w h i c h d e v i a t e s s l i g h t l y f r o m t h e s t a n d a r d BBP p r o p o s e d by C a m b r i d g e . To e n a b l e c o m m u n i c a t i o n w i t h t h i s B B P , t h e BBP i m p l e m e n t e d on t h e L S I 11/23 i s made c o m p a t i b l e . What i s d e s c r i b e d b e l o w may n o t f u l l y r e p r e s e n t t h e o r i g i n a l i m p l e m e n t o r ' s a r g u m e n t f o r t h e d e s i g n a n d i s p a r t i a l l y t h i s a u t h o r ' s a n a l y s i s f o r s u c h a d e s i g n . T h i s i s b e c a u s e f u l l d o c u m e n t a t i o n was n o t a v a i l a b l e . T h e m a j o r d e v i a t i o n s a n d t h e i r j u s t i f i c a t i o n s a r e : • T h e r e i s no m i n i p a c k e t f o r t h e P o r t . T h e p o r t number i s i m b e d d e d i n t o t h e H e a d e r p a c k e t . T h i s i s t o f u l l y u t i l i z e t h e v a c a n t s p a c e i n t h e H e a d e r p a c k e t , t o s i m p l i f y t h e BBP a l g o r i t h m a n d o v e r a l l t o i m p r o v e t h e t h r o u g h p u t . H e n c e f o r t h e r e c o g n i t i o n o f t h e H e a d e r , t h e two e x t r a c o n t r o l b i t s i n t h e 40 b i t m i n i p a c k e t i s s e t t o s i g n i f y t h a t t h e m i n i p a c k e t i s a H e a d e r . T h e l a y o u t o f t h e m o d i f i e d b a s i c b l o c k i s a s s h o w n . 35 + + + + + + + | t y p e 10 j l e n g t h | | d a t a | d a t a | | d a t a | d a t a | - | d a t a | + + + + + + + 4 11 8 8 8 8 8 b i t s b i t s b i t s b i t s b i t s b i t s b i t s t y p e = c l i e n t p r o t o c o l t y p e (0 - 15) 0 = R e s e r v e d 1 = V i r t u a l W i r e P r o t o c o l 2 = B y t e S t r e a m P r o t o c o l 3-14 = U n a s s i g n e d 15 = R e s e r v e d l e n g t h = d a t a l e n g t h - 1 (0 - 2047) b y t e s d a t a = c l i e n t ' s d a t a (1 - 2048) b y t e s F i g u r e 7 - M o d i f i e d B a s i c B l o c k • T h e C h e c k s u m i s n o t c a l c u l a t e d n o r s e n t ; t h i s i s j u s t i f i e d by t h e f a c t t h a t t h e r a t e o f c o r r u p t i o n o f b i t s i n t h e R i n g i s e x t r e m e l y l o w . R a t e s o f c o r r u p t i o n o f one b i t i n 1 0 1 ° o r one i n 1 0 1 1 a r e common. F u r t h e r m o r e , t h e c a l c u l a t i o n o f c h e c k s u m i s g e n e r a l l y known t o be a m a j o r u s a g e o f c r i t i c a l p r o c e s s o r t i m e d u r i n g t h e r e c e p t i o n a n d t r a n s m i s s i o n o f a b a s i c b l o c k . M e a s u r e m e n t s were c o n d u c t e d a n d t h e r e s u l t s were t h a t w i t h o u t t h e C h e c k s u m p a c k e t , t h e t h r o u g h p u t was i n c r e a s e d by a s much a s 10% p e r b a s i c b l o c k . T h e l a y o u t o f t h e b l o c k o f d a t a d e s c r i b i n g t h e i n t e r f a c e b e t w e e n t h e BBP a n d h i g h e r l e v e l s o f t w a r e i s a s s h o w n : 36 s t a t i o n | 00001 t y p e | d a t a | d a t a | 8 4 4 8 8 b i t s b i t s b i t s b i t s b i t s s t a t i o n = d e s t i n a t i o n / s o u r c e s t a t i o n a d d r e s s t y p e = c l i e n t p r o t o c o l t y p e d a t a = 1 - 2048 c l i e n t d a t a b y t e s F i g u r e 8 - I n t e r f a c e b l o c k b e t w e e n R i n g d r i v e r a n d BSP 37 4 . 2 A l g o r i t h m s To i l l u s t r a t e c l e a r l y t h e s t r u c t u r e o f t h e B B P , t h e f o l l o w i n g r e c e p t i o n a n d t r a n s m i s s i o n p r o t o c o l a l g o r i t h m s a r e l i s t e d b e l o w . R E C E P T I O N L O O P : S e t SSR t o 255 ( l i s t e n t o a n y b o d y ) I f HEADER a r r i v e s t h e n b e g i n LOCK on t o t h e t r a n s m i t t i n g s t a t i o n , s t a r t TIMER f o r b a s i c b l o c k . F o r I = 1 t o L e n g t h - b a s i c - b l o c k DO C o p y DATA i n t o i n t e r n a l b u f f e r . I n f o r m H i g h e r L e v e l & g o t o LOOP e n d e l s e b e g i n D i s c a r d m i n i p a c k e t . G o t o LOOP e n d T I M E O U T ; D i s c a r d w h a t e v e r t h a t h a s b e e n r e c e i v e d so f a r . G o t o L O O P . N O T E : When t h e TIMER e x p i r e s , t h e c l o c k w o u l d i n t e r r u p t a n d e x e c u t e t h e s t a t e m e n t s a f t e r l a b e l T I M E O U T . 38 TRANSMISSION S t a r t TIMER R E T R I E S = 0 L O O P 1 : T x m i t HEADER ( i n c l u d i n g i m b e d d e d PORT i n f o r m a t i o . C a s e R E S P O N S E : B U S Y , R E J E C T E D : I f R E T R I E S < M A X - H E A D E R - R E T R Y t h e n b e g i n R E T R I E S = R E T R I E S + 1 G o t o LOOP1 e n d e l s e r e t u r n (ERROR) IGNORED, E R R O R - P A C K E T : r e t u r n (ERROR) e n d C a s e FOR R e s t o f B a s i c B l o c k DO B E G I N RETRIES= 0 L O O P 2 : T x m i t DATA C a s e R E S P O N S E : B U S Y : I f R E T R I E S < M A X - D A T A - R E T R Y t h e n b e g i n R E T R I E S * R E T R I E S + 1 G o t o LOOP2 e n d e l s e r e t u r n (ERROR) R E J E C T E D , IGNORED, E R R O R - P A C K E T : r e t u r n ( E R R O R ) e n d C a s e END T I M E O U T : r e t u r n (ERROR) 39 4 . 3 U n i x I / O D e v i c e s r u n n i n g u n d e r t h e U n i x o p e r a t i n g s y s t e m a r e a l s o c o n s i d e r e d as f i l e s . T h e r e a r e e s s e n t i a l l y two t y p e s o f f i l e s i n U n i x , n a m e l y O r d i n a r y f i l e s a n d S p e c i a l f i l e s . F o r a d e v i c e c o n n e c t e d t o U n i x , a s p e c i a l f i l e f o r i t i s made . T h e s y s t e m c a l l s t h a t a p p l y t o O r d i n a r y f i l e s a l s o a p p l y t o S p e c i a l f i l e s . C o n s e q u e n t l y t h e R i n g d e v i c e d r i v e r i n o u r c a s e i s made i n v i s i b l e t o t h e u s e r : t h e r e a d e r s i m p l y r e a d s a n d w r i t e s t o / f r o m t h e R i n g a s i f i t were a c c e s s i n g a f i l e . T h e r e a r e two t y p e s o f S p e c i a l f i l e s w h i c h r e f l e c t t h e two m a j o r k i n d s o f I / O . T h e y a r e b l o c k a n d c h a r a c t e r . T h e b l o c k i n t e r f a c e i s s u i t a b l e f o r d e v i c e s l i k e d i s k s , t a p e s w h i c h c a n work w i t h a d d r e s s a b l e 512 b y t e ~ b l o c k s . T h o s e d e v i c e s t h a t do n o t b e l o n g t o t h i s c a t e g o r y f a l l i n t o t h e c h a r a c t e r d e v i c e c l a s s . T h e f o l l o w i n g s y s t e m c a l l s u s e d t o a c c e s s t h e f i l e s a r e : • f d - o p e n ( f i l e n a m e , f l a g ) • c l o s e ( f d ) • b y t e s - r e a d = r e a d ( f d , b u f f e r , n u m b y t e s ) • w r i t e ( f d , b u f f e r , n u m b y t e s ) • i o c t l ( f d , command, d a t a ) where f d = f i l e d e s c r i p t o r u s e d t o i d e n t i f y t h e f i l e . When a new d e v i c e d r i v e r i s t o be a d d e d o n t o t h e s y s t e m , 40 t he f o l l o w i n g has t o be done ; • The I n t e r r u p t V e c t o r t a b l e i n f i l e / s y s / c o n f / l . s has t o be m o d i f i e d t o e n a b l e ha rdware i n t e r r u p t s t o be t r a p p e d t o t h e a p p r o p r i a t e i n t e r r u p t r o u t i n e s . • The C h a r a c t e r D e v i c e T a b l e (cdevsw) i n f i l e / s y s / c o n f / c . c has t o be m o d i f i e d t o s p e c i f y t h e i n t e r f a c e r o u t i n e s p r e s e n t f o r t h e d e v i c e d r i v e r . • A S p e c i a l f i l e r e p r e s e n t i n g i t has t o be c r e a t e d i n t h e d i r e c t o r y / d e v . The d e v i c e d r i v e r i t s e l f s h o u l d c o n s i s t o f t h e f i v e r o u t i n e s w h i c h map o n t o t h e f i v e s t a n d a r d sys tem c a l l s used t o access a f i l e as m e n t i o n e d a b o v e . I n our R ing d e v i c e d r i v e r , t h e c o r r e s p o n d i n g r o u t i n e s a r e : • r i n g o p e n ( ) • r i n g c l o s e O • r i n g w r i t e ( ) • r i n g r e a d ( ) The i o c t l sys tem c a l l i s no t u s e d . I n a d d i t i o n t h e 2 c o r r e s p o n d i n g i n t e r r u p t h a n d l e r s f o r t h e R ing ha rdware i n t e r f a c e , r n r i n t O and r n x i n t O a r e p l a c e d i n t h i s d r i v e r . 41 4 . 4 P e r f o r m a n c e Of BBP I m p l e m e n t a t i o n s T h r e e d e s i g n s c h e m e s f o r t h e B B P , n a m e l y C o n v e n t i o n a l I / O , R e a d - A h e a d I / O a n d S i g n a l l i n g were i m p l e m e n t e d a n d t h e i r p e r f o r m a n c e s , i n t e r m s o f t h r o u g h p u t , were m e a s u r e d . T h e d i f f e r e n c e s i n t h e t h r e e d e s i g n s r e s t on t h e b u f f e r i n g o f d a t a a n d t h e r a t e a t w h i c h d a t a i s p a s s e d t o t h e u s e r f r o m t h e R i n g d e v i c e d r i v e r . A l t h o u g h t h e u se o f more t h a n one b u f f e r w o u l d s m o o t h o u t t h e p e a k s i n b a s i c b l o c k a r r i v a l s a n d i n c r e a s e t h e t h r o u g h p u t , t h e R i n g d e v i c e d r i v e r c u r r e n t l y h a s o n l y one b u f f e r f o r r e c e p t i o n . T h i s i s b e c a u s e o f t h e d e c i s i o n f o r p r o t o c o l s i m p l i c i t y a n d a l a c k o f a v a i l a b l e s p a c e i n t h e r e s e r v e d d a t a a r e a s o f t h e k e r n e l . ~ 4 . 4 . 1 C o n v e n t i o n a l I / O A p r o g r a m m e r new t o t h e i m p l e m e n t a t i o n o f a d e v i c e d r i v e r i n U n i x w o u l d n a t u r a l l y i m p l e m e n t t h e BBP a c c o r d i n g t o t h e i d e a t h a t l a y b e f o r e h i m i n t e r m s o f t h e R e a d s y s t e m c a l l . I n o r d e r t o r e c e i v e d a t a f r o m t h e R i n g , a u s e r w o u l d e x e c u t e a R e a d c a l l ; t h e R e a d c a l l g e t s b l o c k e d u n t i l t h e d a t a a r r i v e s f r o m t h e R i n g . T h i s d r i v e r h a s t h e u n d e s i r a b l e e f f e c t o f i g n o r i n g d a t a f r o m t h e R i n g u n t i l a f t e r a R e a d c a l l i s i s s u e d . M e a s u r e m e n t s were d o n e a n d t h e r e s u l t i n g t h r o u g h p u t r e l a t i v e t o t h e s p e e d o f t h e R i n g was s i g n i f i c a n t l y l o w . N e v e r t h l e s s , t h e o b j e c t i v e o f t h i s s i m p l e d r i v e r i m p l e m e n t a t i o n was t o f a m i l i a r i z e t h e p r o g r a m m e r w i t h t h e s p e e d d i s p a r i t y b e t w e e n t h e h i g h s p e e d R i n g a n d t h e s y s t e m a n d t o g e t s o m e t h i n g 42 w o r k i n g b e f o r e e m b a r k i n g on a somewhat more s o p h i s t i c a t e d d r i v e r " . T o a l l e v i a t e t h e p r o b l e m o f t h i s s p e e d d i s p a r i t y a n d t o p r o v i d e f o r d a t a f l o w , t h e o t h e r two s c h e m e s were t r i e d . 4 . 4 . 2 R e a d - A h e a d I / O In t h i s R e a d - A h e a d I / O s c h e m e , a n y d a t a t h a t a r r i v e s f r o m t h e R i n g i s a c c e p t e d u n l e s s t h e d r i v e r i n p u t b u f f e r i s f u l l . The i n p u t b u f f e r i s a l w a y s k e p t a s f u l l a s p o s s i b l e , so t h a t t h e r e i s d a t a p e n d i n g i n t h e d r i v e r w h e n e v e r a R e a d s y s t e m c a l l i s e x e c u t e d . A f t e r t h e R e a d c a l l , t h e i n p u t b u f f e r i s m a r k e d empty a n d i s a v a i l a b l e f o r u s e a g a i n . T h e m a j o r d r a w b a c k w i t h t h i s scheme i s t h a t t h e u s e r p r o c e s s d o e s n o t know when a n y d a t a h a s a r r i v e d f r o m t h e R i n g , h e n c e i t h a s t o e x e c u t e t h e R e a d i n an i n f i n i t e l o o p . E a c h R e a d s y s t e m c a l l e x e c u t e d h a s t o be p r o c e s s e d by t h e s y s t e m , i r r e s p e c t i v e o f w h e t h e r t h e r e i s p e n d i n g d a t a f r o m t h e R i n g ; c o n s e q u e n t l y t y i n g up t h e s y s t e m u n n e c e s s a r i l y when no d a t a i s c o m i n g f r o m t h e R i n g a t a l l . 4 . 4 . 3 S i g n a l l i n g T h i s scheme i s q u i t e s i m i l a r t o t h e R e a d - A h e a d I / O s c h e m e , e x c e p t t h a t t h i s t i m e t h e u s e r p r o c e s s knows when t o e x e c u t e t h e Read s y s t e m c a l l . E a c h t i m e t h e R i n g d e v i c e d r i v e r s u c c e s s f u l l y r e c e i v e s a b l o c k o f d a t a , i t s e n d s a s o f t w a r e i n t e r r u p t ( s i g n a l ) t o t h e u s e r p r o c e s s w h i c h o p e n e d t h i s d e v i c e d r i v e r . The s i g n a l i n t e r r u p t h a n d l i n g r o u t i n e o f t h e a f f e c t e d p r o c e s s w o u l d t h e n 43 e x e c u t e t h e R e a d c a l l t o o b t a i n t h e b a s i c b l o c k . H o w e v e r , t h e s i g n a l i n t e r r u p t h a n d l i n g r o u t i n e c a n o n l y be e x e c u t e d when t h e a f f e c t e d u s e r p r o c e s s i s a c t i v e . T h e m a j o r d r a w b a c k w i t h t h i s scheme i s t h a t t h e e f f e c t o f a s o f t w a r e i n t e r r u p t n e v e r t a k e s p l a c e i m m e d i a t e l y . I t may o c c u r a f t e r o n l y some s l i g h t d e l a y i f t h e a f f e c t e d p r o c e s s i s c u r r e n t l y r u n n i n g o r p o s s i b l y a f t e r a c o n s i d e r a b l e d e l a y i f t h e r e j e c t e d p r o c e s s i s s u s p e n d e d a n d h a s been s w a p p e d o u t . [ 1 0 ] 4 . 4 . 4 M e a s u r e m e n t s M e a s u r e m e n t s were c o n d u c t e d f o r t h e a b o v e t h r e e s c h e m e s t o d e t e r m i n e t h e i r r e l a t i v e p e r f o r m a n c e s ; t h i s i s a s shown i n F i g . 9 . T h e e x p e r i m e n t a l s e t u p c o n s i s t s o n l y o f t h e L S I 1 1 / 2 3 a c t i n g a s b o t h t r a n s m i t t e r a n d r e c e i v e r , i . e . , t h e R i n g o r i g i n a t e d a n d t e r m i n a t e d on t h e same m a c h i n e (a l o o p - b a c k m o d e ) . S i n c e t h e r e a d e r , a n d t r a n s m i t t e r a r e i n t h e same m a c h i n e , t h e r e e x i s t e d o n l y a p s e u d o f o r m o f a s y n c h r o n i s m . T h e r e s u l t s u s i n g a s i n g l e b u f f e r e a c h f o r r e c e p t i o n a n d t r a n s m i s s i o n were t a b u l a t e d ( s e e A p p e n d i x A ) . T h e g r a p h s i n F i g . 9 show t h e s u p e r i o r p e r f o r m a n c e . o f t h e R e a d - A h e a d I / O scheme o v e r t h e o t h e r two s c h e m e s . 44 i i r 1 1 ; r— - ° ' J 40.0 60.0 80.0 100.0 170 0 ' ] O BYTES PER BASIC BLOCK ( X 1 0 r ) F i g u r e 9 - P e r f o r m a n c e s o f t h e i m p l e m e n t a t i o n s 45 V . BYTE STREAM PROTOCOL IMPLEMENTATION T h i s c h a p t e r d e s c r i b e s t h e t r a n s l a t i o n o f t h e d e s c r i p t i o n o f t h e BSP i n t o a w o r k i n g i m p l e m e n t a t i o n o f i t . T h e BSP p r o g r a m i s w r i t t e n i n t h e h i g h l e v e l s y s t e m l a n g u a g e C . I n d e v e l o p i n g t h i s s y s t e m , t h e f o l l o w i n g c l a s s i c d e s i g n p r o c e s s was c l o s e l y a d h e r e d t o : • S p e c i f y t h e p r o b l e m • S p e c i f y t h e d a t a s t r u c t u r e s • D e f i n e f o r m a t o f d a t a s t r u c t u r e s • S p e c i f y t h e a l g o r i t h m s • S i m p l i f y a n d m o d u l a r i z e t h e p r o g r a m m o d u l e i n t o s m a l l e r m o d u l e s • R e p e a t f o r e a c h p r o g r a m m o d u l e T h e d e s i g n p r o c e s s i s i t e r a t i v e i n n a t u r e , t h a t i s e a c h s t e p may be r e p e a t e d t o r e f i n e t h e p r o c e s s . A s m e n t i o n e d e a r l i e r i n c h a p t e r i i i , t h e f i n a l c o n c e p t u a l d e s i g n o f t h e BSP i n v o l v e s t h e BSP S e r v e r i n t e r a c t i n g o n l y w i t h t h e U s e r a n d R e a d e r . M u l t i p l e i n s t a n c e s o f t h e BSP i s s u p p o r t e d by t h e BSP m u l t i p l e x o r i n t h e k e r n e l . The BSP m u l t i p l e x o r i s an a b s t r a c t e n t i t y a n d i s r e a l i z e d a s t h e i n t e r a c t i o n o f t h e two s y s t e m c a l l s : c r e a t p o r t a n d r e l p o r t , w i t h t h e BBP t h r o u g h t h e u se o f t h e p o r t - p r o c i d t a b l e ( s e e F i g . 6 ) . I n t h e f o l l o w i n g s e c t i o n s , we s h a l l c o n c e n t r a t e on t h e BSP i m p l e m e n t a t i o n r e s i d i n g a t t h e u s e r l e v e l o f t h e U n i x s y s t e m , a s 46 d e p i c t e d i n f i g . 1 0 . F i g u r e 1 0 - S e r v e r / C l i e n t M o d e l o f BSP In e s s e n c e , most o f t h e i m p l e m e n t a t i o n i s s t r a i g h t f o r w a r d , b u t two p r o g r a m m o d u l e s , n a m e l y t h e T i m e o u t m e c h a n i s m a n d t h e W r i t e r , whose f u n c t i o n ' i s t o t r a n s m i t b a s i c b l o c k s , c a u s e d t h e a u t h o r t o m u l l o v e r t h e i r d e s i g n s . I n t h e c a s e o f t h e T i m e o u t m e c h a n i s m , d i f f i c u l t i e s e m e r g e d f r o m t h e n e e d t o h a v e two t i m e r s e v o k e d c o n c u r r e n t l y ; one e a c h f o r r e c e p t i o n a n d t r a n s m i s s i o n . In t h e t r a n s m i s s i o n o f b a s i c b l o c k s , t h e i s s u e o f how t o i n t e g r a t e t h e W r i t e r a r i s e s : s h o u l d i t be p a r t o f t h e BSP S e r v e r o r a W o r k e r p r o c e s s i t s e l f . T o e n l i g h t e n a n d n o t t o b o r e t h e r e a d e r w i t h d e t a i l s , t h e 47 a p p r o a c h t a k e n t o p r e s e n t t h i s i m p l e m e n t a t i o n , i s t o d e s c r i b e o n l y t h e r e p r e s e n t a t i o n s o f t h e f o l l o w i n g c o n s t i t u e n t e l e m e n t s w h i c h e p i t o m i z e t h e BSP d e s i g n : • S e r v e r • R e a d e r • P r o c e s s i n g o f b a s i c b l o c k s • T i m e r • W r i t e r T h e s e r e p r e s e n t a t i o n s embody t h e p r o g r a m m o d u l e s a n d t h e d a t a s t r u c t u r e s t h a t a r e o p e r a t e d o n . 5.1 S e r v e r R e p r e s e n t a t i o n T h e S e r v e r i s t h e m a i n p r o c e s s w h i c h c o o r d i n a t e s t h e a c t i v i t i e s o f t h e R e a d e r a n d U s e r . I t p r o v i d e s a v i r t u a l c i r c u i t s e r v i c e t o t h e U s e r t h r o u g h t h e f o l l o w i n g r e q u e s t s t h a t c o r r e s p o n d t o t h e BSP commands : • REQ_OPEN • REQ_READ • REQ_WRITE • REQ_RESET • REQ CLOSE T h e REQ_READ a n d REQ_WRITE a r e c o m p a r a b l e t o t h e " B u f f e r R e a d y " e v e n t s i n t h e BSP s t a t e t r a n s i t i o n d i a g r a m . A l l t h e r e q u e s t s f r o m t h e U s e r a r e b l o c k e d p e n d i n g r e p l y f r o m t h e 48 S e r v e r . R e q u e s t s f r o m t h e R e a d e r t a k e t h e f o r m o f a n o t i f i c a t i o n o f a b a s i c b l o c k a r r i v a l , B B _ A R R I V E a n d an u n r e s o l v a b l e f a i l u r e , R E A D _ F A I L i n t h e R i n g d r i v e r ( B B P ) . T h e f o l l o w i n g f i g u r e b e l o w i l l u s t r a t e s t h e m a i n p r o c e d u r e o f t h e S e r v e r . ma i n () { USER_NODE * u _ n o d e , * g e t _ r e q u e s t ( ) ; i n t r e q u e s t ; i f •( ( i n i t _ s t a t i o n ( ) ) == ERROR ) r e t u r n ( E R R O R ) ; f o r ( ; ; ) { u_node= g e t _ r e q u e s t ( & r e q u e s t ) ; s w i t c h ( r e q u e s t ) { c a s e R E Q _ O P E N : o p e n _ r e q ( u _ n o d e ) ; b r e a k ; c a s e R E Q _ C L O S E : c l o s e _ r e q ( u _ n o d e ) ; b r e a k ; c a s e R E Q _ W R I T E : w r i t e _ r e q ( u _ n o d e ) ; b r e a k ; c a s e R E Q _ R E S E T : r e s e t _ r e q ( u _ n o d e ) ; b r e a k ; c a s e B B _ A R R I V E : f r a m e _ a r r i v a l ( u _ n o d e ) ; b r e a k ; c a s e R E A D _ F A I L : p _ e r r o r ( u _ n o d e - > u s e r _ n u m , R E A D _ F A I L ) ; e x i t ( E R R O R ) ; d e f a u l t : ' p _ e r r o r ( u _ n o d e - > u s e r _ n u m , B A D _ R E Q U E S T ) ; b r e a k ; } } } F i g u r e 11 - M a i n P r o c e d u r e o f S e r v e r T h e t a s k ' o f t h e S e r v e r i s t o i n i t i a l i z e t h e c o m m u n i c a t i o n l i n k a n d t h e n go i n t o an i n f i n i t e l o o p p r o c e s s i n g r e q u e s t s . T h e 49 i n i t i a l i z a t i o n i n v o l v e s c r e a t i n g t h e U s e r a n d R e a d e r p r o c e s s e s , s e t t i n g up t h e n e c e s s a r y p i p e s a n d i n i t i a l i z i n g t h e d a t a s t r u c t u r e s u s e d . R e q u e s t s a r e o b t a i n e d f r o m t h e m u l t i p l e x i n g p i p e by a c a l l t o t h e f u n c t i o n g e t r e q u e s t . T h e t a s k o f g e t _ r e q u e s t i s t o s i m p l y i d e n t i f y t h e t y p e a n d s o u r c e o f t h e r e q u e s t . M e s s a g e s i n t h e m u l t i p l e x i n g p i p e t a k e on a r e c o r d s t r u c t u r e o f t y p e P I P E FRAME a s shown b e l o w : t y p e d e f s t r u c t { i n t f r o m ; i n t r e q u e s t ; i n t c o u n t ; c h a r m e s g [ ] ; } P I P E _ F R A M E ; D e f i n i t i o n s : f r o m : s o u r c e o f r e q u e s t . r e q u e s t : r e q u e s t t y p e . c o u n t : s i z e o f d a t a . m e s g : b u f f e r f o r d a t a i f a n y . F i g u r e 12 - F o r m a t o f P I P E _ F R A M E E x c e p t f o r t h e p e r r o r f u n c t i o n p r o c e s s i n g f a t a l e r r o r s , t h e r e s t o f t h e f u n c t i o n s d e l e g a t e d t o p e r f o r m t h e i r a p p r o p r i a t e t a s k s r e q u i r e t h e p o i n t e r u node t o a c c e s s p e r t i n e n t i n f o r m a t i o n f o r i t s c o r r e c t f u n c t i o n i n g . T h e s t a t u s o f t h e BSP c o m m u n i c a t i o n l i n k i s m a i n t a i n e d i n t h r e e d a t a s t r u c t u r e s o f t y p e s SERVER S T A T E , USER NODE and t i m e n o d e . 50 F o r m a t : De f i n i t i o n s : t y p e d e f s t r u c t { i n t i d ; USER_NODE * u s r ; T I M E R P T R t i m e h e a d ; T I M E R P T R t i m e t a i l ; i n t u s e r _ i d ; i n t r e a d _ i d ; i n t b u s [ 2 ] ; i n t b b f d ; i n t s i g f l g ; p r o c e s s - i d o f S e r v e r . p o i n t e r t o U S E R _ N O D E . p o i n t e r t o f i r s t t i m e r node i n l i s t . p o i n t e r t o l a s t t i m e r n o d e i n l i s t . p r o c e s s - i d o f U s e r . p r o c e s s - i d o f R e a d e r . t h e m u l t i p l e x i n g p i p e . F i l e d e s c r i p t o r f o r R i n g d r i v e r . F l a g u s e d t o mark s i g n a l i n t e r r u p t . } SERVER S T A T E ; F i g u r e 13 - F o r m a t o f SERVER S T A T E T h e S E R V E R _ S T A T E a s shown a b o v e , c o n t a i n s g l o b a l i n f o r m a t i o n t h a t i d e n t i f i e s t h e C l i e n t p r o c e s s e s , t h e m u l t i p l e x i n g p i p e , t h e R i n g d r i v e r , a n d t h e p o i n t e r s t o t h e o t h e r two d a t a s t r u c t u r e s w h i c h c o n t a i n i n f o r m a t i o n t h a t r e f l e c t t h e a c t u a l s t a t e o f t h e c o m m u n i c a t i o n l i n k . An i n s t a n c e o f a BSP l i n k c o n t a i n s two b u f f e r s , one e a c h , f o r r e c e p t i o n a n d t r a n s m i s s i o n . T h e s e b u f f e r s a r e r e p r e s e n t e d i n t h e d a t a s t r u c t u r e B U F F E R , a n d a r e a c c e s s e d by p o i n t e r s i n t h e U S E R _ N O D E . T h e c o m p o s i t i o n o f t h e d a t a s t r u c t u r e s w i l l be e l a b o r a t e d on i n t h e r e l e v a n t s e c t i o n s . F o r t h e p r e s e n t , a s k e t c h on t h e v a r i o u s d a t a s t r u c t u r e s a n d t h e i r a c c e s s i b i l i t y f r o m t h e S E R V E R _ S T A T E i s d e p i c t e d o v e r l e a f . 5 1 SERVER STATE h e a d u s r t i m e h e a d *• t I m e t a t1 USER NODE BSP S t a t e T r a n s 1t i on I n f o r m a t \ o n r e c . b u f f e r * t x . b u f f e r *• \ \ \ \ t i menode BUFFER BUFFER F i g u r e 14 - BSP D a t a S t r u c t u r e s 5 . 2 R e a d e r R e p r e s e n t a t i o n T h e t a s k o f t h e R e a d e r i s t o r e a d i n t h e b a s i c b l o c k s a r r i v i n g f r o m t h e R i n g d r i v e r a n d r e l a y them t o t h e S e r v e r t o be p r o c e s s e d . I t c o n s i s t s o f two f u n c t i o n s , n a m e l y t h e s i g n a l h a n d l i n g r o u t i n e , s i g h a n d l r a n d t h e m a i n r o u t i n e , r e a d e r p r o c . T h e r e a d e r _ p r o c f u n c t i o n s i m p l y w a i t s f o r t h e s i g n a l t o a r r i v e f r o m t h e R i n g d r i v e r by e x e c u t i n g t h e p a u s e c a l l . The s y s t e m f u n c t i o n p a u s e e n a b l e s a p r o c e s s t o r e l i n q u i s h c o n t r o l o f t h e CPU a n d r e g a i n c o n t r o l w h e n e v e r a s i g n a l a r r i v e s . A r r i v a l 52 o f t h e s i g n a l c a u s e s t h e i n v o c a t i o n o f t h e s i g h a n d l r f u n c t i o n w h i c h t h e n r e a d s i n t h e b a s i c b l o c k o r t h e e r r o r m e s s a g e f r o m t h e R i n g d r i v e r . On h a v i n g s u c c e s s f u l l y r e a d i n t h e b a s i c b l o c k , t h e R e a d e r n o t i f i e s t h e S e r v e r by t h e BB A R R I V E r e q u e s t . I n t h e e v e n t o f a f a i l u r e , t h e READ F A I L r e q u e s t i s s e n t i n s t e a d . T h e f i g u r e b e l o w d e p i c t s t h e R e a d e r -and i l l u s t r a t e s t h e u s e o f t h e p a u s e a n d s i g n a l l i n g c o n c e p t s . s t a t i c P I P E _ F R A M E f r a m e ; s t a t i c i n t f d ; s t a t i c u n s i g n e d * i n t _ p t r ; s t a t i c i n t l e n , d o n e ; s i g h a n d l r ( s i g n ) / * s i g n a l h a n d l i n g r o u t i n e - * / s i g n a l ( s i g n , s i g h a n d l r ) ; / * r e s e t s i g n a l * / i f ( ( l e n = r e a d ( s e r v e r . b b f d , f r a m e . m e s g , S I Z E _ M A X _ B U F ) ) > 0 ) { / * r e l a y b a s i c b l o c k t o S e r v e r * / i n t _ p t r = f r a m e . m e s g ; s e t _ f r a m e ( & f r a m e , R E A D E R , i n t _ p t r - > l o b y t e & 0 3 7 7 , B B _ A R R I V E , l e n ) ; msg t o s e r v e r ( & f r a m e , ( C N T R L E N + f r a m e . c o u n t ) ) ; 1 " " i f ( l e n == ERROR ) { / * r e t u r n e r r o r mes sage t o S e r v e r * / s e t _ f r a m e ( & f r a m e , R E A D E R , 0 , R E A D _ F A I L , 0 ) ; m s g _ t o _ s e r v e r ( & f r a m e , C N T R L E N ) ; done= T R U E ; } } r e a d e r _ p r o c ( ) { done= F A L S E ; w h i l e ( Idone ) / * w h i l e n o t d o n e * / p a u s e ( ) ; / * r e l i n q u i s h c o n t r o l o f CPU * / } F i g u r e 15 - R e p r e s e n t a t i o n o f R e a d e r 53 5 . 3 P r o c e s s i n g R e q u e s t BB A R R I V E T h e e s s e n c e o f t h e BSP l i e s i n t h e p r o c e s s i n g o f t h e b a s i c b l o c k s a r r i v e d f r o m t h e R e a d e r . I t c o m p r i s e s a g r o u p o f r e l a t e d s e c o n d a r y f u n c t i o n s c o o r d i n a t e d by t h e p r i m a r y o r m a i n f u n c t i o n f r ame a r r i v a l a s shown i n F i g . 16 . The c o n t r o l f l o w o r a l g o r i t h m f o r a l l t h e s e c o n d a r y f u n c t i o n s i s b a s e d on t h e s t a t e t r a n s i t i o n o f t h e BSP a c c e s s i b l e f r o m t h e p o i n t e r u _ n o d e . The f o r m a t o f t h e s t r u c t u r e USER_NODE p o i n t e d t o by u _ n o d e i s shown i n F i g . 17 . To g i v e a s k e t c h on t h e p r o c e s s i n g o f b a s i c b l o c k s , t h e f o l l o w i n g s u b s e c t i o n d e s c r i b e s t h e p r o c e s s i n g o f d a t a t r a n s a c t i o n commands (a s o p p o s e d t o c o n t r o l c o m m a n d s ) . -f r a m e a r r i v a l ( u node ) USER_NODE * u n o d e ; B U F F E R * b u - f p t r ; b u f p t r = u _ n o d e - > r _ q u e ; s w i t c h ( b u f p t r - > f i r s t _ c m d ) { c a s e R E S E T COM: r e c _ r e s e t ( u b r e a k ; n o d e , b u f p t r ) ; c a s e C L O S E COM: r e c _ c l o s e ( u b r e a k ; n o d e , b u f p t r ) ; c a s e OPEN COM: r e c _ o p e n ( u _ n o d e , b u f p t r ) ; b r e a k ; c a s e OPENACK COM: o p e n a c k _ r e c ( u _ n o d e , b u f p t r ) ; b r e a k ; d e f a u l t : d a t a _ f r a m e ( u _ n o d e , b u f p t r ) ; b r e a k ; } } F i g u r e 16 - D i a g r a m o f f u n c t i o n f r a m e _ a r r i v a l 5 4 t y p e d e f s t r u c t unode { i n t u s e r _ n u m ; i n t r _ s t a t e , r _ s e q , r _ t r i e s , r _ m a x _ s i z e , r _ p o r t ; i n t x _ s t a t e , x _ s e q , x _ t r i e s , x _ m a x _ s i z e , x _ p o r t , x _ a d d r ; i n t r b u f s t a t ; i n t r e a d _ p e n d i n g ; i n t w r i t _ p e n d i n g ; i n t p r o c _ s t a t u s ; B U F F E R * r _ q u e , * x _ q u e ; } USER N O D E ; • u s e r _ n u m i s t h e p o r t n u m b e r . • r _ s t a t e i s t h e s t a t e o f t h e B S P , w h i c h c o u l d e i t h e r t a k e one o f t h e f o l l o w i n g s t a t e s : • r _ s e q i s t h e r e c e p t i o n s e q u e n c e n u m b e r . • r _ t r i e s i s a v a r i a b l e t o k e e p t r a c k o f t h e number o f a t t e m p t s made f o r an a c t i o n . • r _ m a x _ s i z e k e e p s t r a c k o f t h e s i z e o f t h e b u f f e r t o h o l d t h e b a s i c b l o c k f o r t h e U s e r . • x _ s t a t e , x _ s e q , x _ t r i e s a n d x _ m a x _ s i z e s i m i l a r l y a p p l i e s t o t h e t r a n s m i s s i o n . • x _ p o r t r e f e r s t o t h e d e s t i n a t i o n p o r t t h i s p o r t i s c o m m u n i c a t i n g w i t h . • x _ a d d r r e f e r s t o t h e d e s t i n a t i o n s t a t i o n a d d r e s s . • r b u f s t a t r e f e r s t o t h e s t a t u s o f t h e r e c e p t i o n b u f f e r ; d e n o t i n g w h e t h e r i t i s f i l l e d o r e m p t y . • r e a d _ p e n d i n g i s a b o o l e a n v a l u e d e n o t i n g w h e t h e r a R E A D _ R E Q was made by t h e U s e r . • w r i t _ p e n d i n g i s a b o o l e a n v a l u e d e n o t i n g w h e t h e r a W R I T E _ R E Q was made by t h e U s e r . F i g u r e 1 7 - F o r m a t o f USER_NODE D e s c r i p t i o n o f f i e l d s i n USER NODE a ) E b) N c ) I - E x p e c t i n g a c k n o w l e d g e m e n t - N o t e x p e c t i n g an a c k n o w l e d g e m e n t - I d l e S t a t e 55 • p r o c _ s t a t u s r e f e r s t o t h e s t a t u s o f t h e BSP d u r i n g t h e c o n t r o l t r a n s a c t i o n p h a s e o f t h e c o m m u n i c a t i o n . • * r _ q u e a n d * x _ q u e r e f e r t o t h e b u f f e r s u s e d t o c o n t a i n t h e b a s i c b l o c k s d u r i n g r e c e p t i o n a n d t r a n s m i s s i o n . 5 . 3 . 1 D a t a T r a n s a c t i o n s T h e f u n c t i o n d a t a f r ame p r o c e s s e s d a t a t r a n s a c t i o n commands a n d i t s mode o f o p e r a t i o n c o r r e s p o n d s t o a c t i v i t i e s o f t h e BSP s t a t e t r a n s i t i o n m o d e l . E s s e n t i a l l y t h e o p e r a t i o n i s t o p r o c e s s t h e commands i n t h e b a s i c b l o c k s t o r e d i n t h e r e c e p t i o n b u f f e r a n d u p d a t e t h e b a s i c b l o c k i n t h e t r a n s m i s s i o n b u f f e r . I f d a t a h a s a r r i v e d a n d t h e p r o c e s s i n g i s c o r r e c t , t h e d a t a ' i s t r a n s f e r r e d t o t h e U s e r , p r o v i d e d t h e r e q u e s t REQ_READ was p r e v i o u s l y s e n t ; o t h e r w i s e a f l a g i s s e t m a r k i n g t h e r e c e p t i o n b u f f e r a s f u l l — p r o v i d i n g m o n o - b u f f e r i n g - - . T h e mode o f o p e r a t i o n i s a s f o l l o w s : • I f t h e BSP s t a t u s i s i n t h e d a t a t r a n s a c t i o n p h a s e , t h e n c o n t i n u e , o t h e r w i s e r e t u r n . • I n i t i a l i z e t h e c o n t e n t s o f t h e b a s i c b l o c k i n t h e t r a n s m i s s i o n b u f f e r . • • P r o c e s s t h e r e c e p t i o n a n d t r a n s m i s s i o n commands by d e l e g a t i n g t h e t a s k s t o t h e s u b o r d i n a t e f u n c t i o n s . T h e v a l u e s s t o r e d i n t o s e n d l a n d t o s e n d 2 r e t u r n e d f r o m t h e r e s p e c t i v e c a l l s t o t h e f u n c t i o n s p r o c e s s i n g t h e r e c e p t i o n a n d t r a n s m i s s i o n commands s i g n i f y w h e t h e r t h e t r a n s m i s s i o n b u f f e r i s t o be s e n t o r an e r r o r h a s o c c u r r e d . • S e t t h e t i m e r a n d t r a n s m i t t h e b a s i c b l o c k s t o r e d i n t h e t r a n s m i s s i o n b u f f e r a c c o r d i n g t o t h e v a l u e s r e t u r n e d i n t o s e n d l a n d t o s e n d 2 . T h e a l g o r i t h m i s shown i n t h e f o l l o w i n g f i g u r e . 56 d a t a _ f r a m e ( u _ n o d e , b u f p t r ) USER_NODE * u _ n o d e ; B U F F E R * b u f p t r ; { i n t t o s e n d l , tosend2, t i m e o u t ( ) ; i f ( ! ( u _ n o d e - > p r o c _ s t a t u s & NORMALTX ) r e t u r n ; t o s e n d l = tosend2= F A L S E ; s e t _ s t a t i o n _ p o r t ( u _ n o d e , u _ n o d e - > x q u e ) ; s w i t c h ( g e t _ c m d ( b u f p t r - > f i r s t_cmd7& 0 3 6 0 ) { c a s e R D Y _ C O M : s t o p _ t i m e r ( u _ n o d e - > u s e r _ n u m , W ) ; t o s e n d l = r d y _ c m d ( u n o d e , b u f p t r ) ; b r e a k ; c a s e NOTRDY_COM: s t o p _ t i m e r ( u _ n o d e - > u s e r _ n u m , W ) ; t o s e n d 1= n o n r d y _ c m d ( u _ n o d e , b u f p t r ) ; b r e a k ; c a s e N U L L _ C O M : b r e a k ; d e f a u l t : p _ e r r o r ( u _ n o d e - > u s e r _ n u m , B A D _ C O M M A N D ) ; b r e a k ; } s w i t c h ( g e t _ c m d ( b u f p t r - > x m i t _ c m d ) & 0 3 6 0 ) { c a s e R D Y _ C O M : s t o p _ t i m e r ( u _ n o d e - > u s e r _ _ n u m , R ) ; tosend2= d a t a _ c m d ( u n o d e , b u f p t r ) ; b r e a k ; c a s e NOTRDY_COM: s t o p _ t i m e r ( u _ n o d e - > u s e r _ n u m , R ) ; tosend2= n o n d a t a _ c m d ( u _ n o d e , b u f p t r ) ; b r e a k ; c a s e N U L L _ C O M : b r e a k ; d e f a u l t : p _ e r r o r ( u _ n o d e - > u s e r _ n u m . , B A D _ C O M M A N D ) ; b r e a k ; } i f ( ( t o s e n d l != ERROR) && (tosend2 != ERROR)) { i f ( t o s e n d l ) s e t _ t i m e r ( u _ n o d e - > u s e r _ n u m , W , A L A R M _ T I M E , t i m e o u t ) ; i f ( tosend2 ) s e t _ t i m e r ( u _ n o d e - > u s e r _ n u m , R , A L A R M _ T I M E , t i m e o u t ) ; i f ( t o s e n d l j j tosend2 ) s e n d t o r i n g ( u n o d e ) ; 1 } F i g u r e 18 - D i a g r a m o f f u n c t i o n d a t a _ f r a m e 57 5 . 3 . 2 F o r m a t Of B u f f e r T h e r e a d e r w o u l d o f c o u r s e be r i g h t when he a s s u m e s t h a t t h e f o r m a t o f t h e BUFFER c o r r e s p o n d s t o t h e f o r m a t o f t h e b a s i c b l o c k . T h e f o r m a t , i n a d d i t i o n , maps o n t o t h e i n t e r f a c e b l o c k u s e d b e t w e e n t h e R i n g d r i v e r a n d t h e B S P . T h e f o r m a t i s - -as shown b e l o w . t y p e d e f s t r u c t b u f { i n t l e n _ o f _ b l k ; i n t m e s s a g e [ ] ; c h a r p t y p e , s t a t i o n ; c h a r r e c _ f l g , f i r s t _ c m d ; c h a r x m i t _ f l g , x m i t _ c m d ; c h a r m s g [ S I Z E _ M A X _ B U F ] ; } B U F F E R ; D e f i n i t i o n s : l e n _ o f _ b l k : l e n g t h o f i n t e r f a c e b l o c k t o be s e n t , m e s s a g e : a dummy; u s e d a s a m a s k . p t y p e : p r o t o c o l t y p e ( s e e i n t e r f a c e b l o c k i n B B P ) . s t a t i o n : d e s t i n a t i o n s t a t i o n a d d r e s s . T h e r e s t o f t h e d e f i n i t i o n s c o r r e s p o n d t o t h e f o r m a t o f t h e pac u s e d i n t h e B S P . N o t e : I n t h e L S I 11 /23 a r c h i t e c t u r e , t h e low o r d e r a n d h i g h o r d e r b y t e s a r e r e p r e s e n t e d i n t h e r e v e r s e d o r d e r . 5 . 4 T i m e r D e s i g n I t i s c h a r a c t e r i s t i c o f p r o t o c o l i m p l e m e n t a t i o n s t o i n c o r p o r a t e t h e T i m e o u t m e c h a n i s m a s a p r o c e s s w h i c h s l e e p s ( i . e . r e l i n q u i s h e s c o n t r o l o f t h e CPU) f o r t h e T i m e o u t i n t e r v a l a n d on a w a k e n i n g ( i . e . when t h e t i m e i n t e r v a l e x p i r e s ) , i n f o r m s t h e S e r v e r o f t h i s T i m e o u t e v e n t . T h e S e r v e r w o u l d t h e n i n v o k e t h e a p p r o p r i a t e f u n c t i o n , n a m e l y t h e T i m e o u t r o u t i n e , t o h a n d l e 58 t h i s e v e n t . T h e e a s e i n w h i c h t h i s c o u l d be d o n e d e p e n d s on t h e f a c i l i t i e s p r o v i d e d by t h e o p e r a t i n g s y s t e m . U n i x p r o v i d e s two f u n c t i o n s , n a m e l y t h e p a u s e a n d t h e a l a r m w h i c h e n a b l e a p r i m i t i v e f o r m o f t h e T i m e o u t m e c h a n i s m t o be r e a l i z e d . By i n v o k i n g t h e p a u s e f u n c t i o n , a p r o c e s s i s c a u s e d t o s l e e p a n d a c a l l t o t h e a l a r m f u n c t i o n w i t h a p a r a m e t e r s p e c i f y i n g t h e t i m e i n t e r v a l a l l o w s a p r o c e s s t o be i n t e r r u p t e d a f t e r t h e t i m e i n t e r v a l h a s e x p i r e d . T h i s a l a r m f e a t u r e e m p l o y s t h e c o n c e p t o f s i g n a l i n g as d e s c r i b e d p r e v i o u s l y . T h u s a s i m p l e t i m e r i s e a s i l y i m p l e m e n t e d by h a v i n g a p r o c e s s s e t t h e a l a r m b e f o r e s l e e p i n g . H o w e v e r , t h e a l a r m f e a t u r e o f U n i x d o e s n o t q u e u e c a l l s . T h e r e i s a t most one o u t s t a n d i n g a l a r m a n d a s u b s e q u e n t c a l l t o i t b e f o r e t h e e x p i r y o f t h e c u r r e n t a l a r m s u p e r s e d e s t h e c u r r e n t o n e . T h e BSP r e q u i r e m e n t f o r two t i m e r s a p p a r e n t l y i n v o l v e s two e x t r a p r o c e s s e s a c t i n g as t i m e r s . T h e i m p l i c a t i o n o f s u c h a t i m e r i m p l e m e n t a t i o n m a n i f e s t s i t s e l f i n t h e i n e f f i c i e n c y a n d a w k w a r d n e s s o f t h e S e r v e r / C l i e n t i n t e r a c t i o n . T h e b a s i s o f i t s a w k w a r d n e s s a n d i n e f f i c i e n c y s t e m s f r o m : • T h e i n c r e a s e i n t h e t o t a l number o f p r o c e s s e s r e q u i r e d f o r t h e S e r v e r t o m u l t i p l e x i n e v i t a b l y d e g r a d e i t s p e r f o r m a n c e . • D e t e r m i n a t i o n o f t h e i d e n t i t y o f t h e t i m e r s , i . e . , w h e t h e r i t i s f o r r e c e p t i o n o r t r a n s m i s s i o n . • A p i p e h a s t o be l i n k e d f r o m t h e S e r v e r t o e a c h t i m e r p r o c e s s t o p r o v i d e a two way c o m m u n i c a t i o n n e c e s s a r y f o r 59 t h e s e t t i n g a n d k i l l i n g , i . e . , r e v o c a t i o n , o f t h e t i m e r s . A p r o t o c o l h a s t o be e s t a b l i s h e d b e t w e e n t h e S e r v e r a n d t h e t i m e r p r o c e s s i n o r d e r t o d i s t i n g u i s h t h e t y p e o f r e q u e s t w a n t e d by t h e S e r v e r : t h e s e t t i n g a n d k i l l i n g o f t i m e r s . S e t t i n g a t i m e r i n v o l v e s h a v i n g t h e S e r v e r t r a n s m i t t h e T i m e o u t i n t e r v a l t o t h e t i m e r p r o c e s s . • A d d i t i o n a l i n f o r m a t i o n h a s t o be k e p t i n s t a t e t a b l e s t o a s c e r t a i n w h i c h T i m e o u t i n t e r v a l ha s e x p i r e d ( N o r m a l o r I d l e H a n d s h a k e ) a n d t h e a p p r o p r i a t e T i m e o u t r o u t i n e s t o be i n v o k e d . 5 . 4 . 1 G e n e r a l T i m e r T o o v e r c o m e s u c h i n a d e q u a c i e s a n d a w k w a r d n e s s , a g e n e r a l T i m e o u t m e c h a n i s m i s d e s i g n e d . I t o b v i a t e s t h e n e e d f o r two e x t r a t i m e r p r o c e s s e s a n d p r o v i d e s a c l e a n i n t e r f a c e f o r t h e s e t t i n g a n d s t o p p i n g o f t i m e r s . F u r t h e r m o r e , two o r more t i m e r s c a n be s e t w i t h o u t a n y s i g n i f i c a n t i n c r e a s e i n c o s t , i n t e r m s o f s p a c e a n d c o m p u t a t i o n r e q u i r e m e n t s . To s e t a t i m e r , t h e f u n c t i o n s e t t i m e r i s c a l l e d , p a s s i n g t o i t t h e T i m e o u t i n t e r v a l a n d t h e T i m e o u t r o u t i n e . In o r d e r t o d i s t i n g u i s h t h e i d e n t i t y o f t h e t i m e r , w h e t h e r i t i s f o r r e c e p t i o n o r t r a n s m i s s i o n , t h e p a r a m e t e r mode i s a l s o d e f i n e d . To k i l l a t i m e r , t h e f u n c t i o n s t o p t i m e r i s i n v o k e d , p a s s i n g t o i t t h e i d e n t i t y o f t h e t i m e r t o be k i l l e d . T h e p r i n c i p l e b e h i n d t h i s g e n e r a l T i m e o u t m e c h a n i s m l i e s i n 60 t h e u se o f a q u e u e o f t i m e r n o d e s , i . e . , a d a t a s t r u c t u r e o f t y p e t i m e n o d e , t o r e p r e s e n t t h e l i s t o f t i m e r s b e i n g s e t . T h i s q u e u e i s o r d e r e d a c c o r d i n g t o t h e e x p i r y t i m e o f e a c h t i m e r ( s e e F i g . 2 0 ) . T h e a l a r m f u n c t i o n i s t h e n i n v o k e d f o r t h e f i r s t node o f t h e q u e u e . On t h e e x p i r y o f t h e t i m e r , t h e f u n c t i o n a l r m h a n d l r i s i n v o k e d a n d i t s t a s k i s t o u p d a t e t h e q u e u e by r e m o v i n g t h e f i r s t n o d e ; c a l l t h e a p p r o p r i a t e T i m e o u t r o u t i n e a n d f i n a l l y i n v o k e t h e a l a r m a g a i n f o r t h e new f i r s t node i n t h e q u e u e ; p r o v i d e d t h e r e i s o n e . T h e e x p i r y t i m e f o r a t i m e r i s c o m p u t e d a s t h e sum o f t h e t i m e t h e t i m e r was i n v o k e d a n d t h e T i m e o u t i n t e r v a l . T h e i n f o r m a t i o n c o n t a i n e d i n t h e t i m e r node i n c l u d e s t h e i d e n t i t y o f t h e t i m e r , t h e T i m e o u t i n t e r v a l , a n d t h e T i m e o u t r o u t i n e . T h e f o r m a t o f t h e d a t a s t r u c t u r e t i m e n o d e i s a s . s h o w n b e l o w . s t r u c t t i m e n o d e { i n t u s e r n o ; i n t m o d e ; i n t i n t e r v a l ; l o n g i n t e x p i r y ; i n t ( * h a n d l r ) ( ) ; s t r u c t t i m e n o d e * n e x t ; } F i g u r e 19 - F o r m a t o f s t r u c t u r e t i m e n o d e D e f i n i t i o n s : u s e r n o : m o d e : i n t e r v a l : h a n d l r ( ) : n e x t : p o r t n u m b e r , d e f i n e s t y p e o f t i m e r , t i m e i n t e r v a l t o be s e t . a d d r e s s o f T i m e o u t r o u t i n e , p o i n t e r t o n e x t t i m e n o d e . 6 1 SERVER STATE t i m e h e a d t i m e t a i 1 - t i m e r n o d e s -F i g u r e 20 - R e p r e s e n t a t i o n o f T i m e r s 5 . 4 . 2 M u t u a l E x c l u s i o n O f S h a r e d Queue I n t e r r u p t s p r e c i p i t a t e d by t h e a l a r m s i g n a l a r r i v a l may c a u s e i n c o n s i s t e n c y i n t h e q u e u e i f b o t h t h e a l r m _ h a n d l r a n d t h e r o u t i n e b e i n g i n t e r r u p t e d u p d a t e t h e l i n k s o f t h e q u e u e . I n d i v i s i b i l i t y o f t h e u p d a t e o p e r a t i o n i s p r o v i d e d by a l w a y s k i l l i n g t h e c u r r e n t a l a r m , i f t h e r e were a n y , a n d r e s e t t i n g t h e a l a r m a g a i n o n c e t h e u p d a t i n g i s d o n e . 62 5.4 . 3 G r a n u l a r i t y Of C l o c k T h e g r a n u l a r i t y o r r e s o l u t i o n o f t h e c l o c k a v a i l a b l e t o p r o c e s s e s by t h e f u n c t i o n t i m e i s one s e c o n d a n d t h i s h a s an u n d e s i r a b l e i m p a c t on t h e f u n c t i o n i n g o f t h e T i m e o u t m e c h a n i s m . F i r s t , t h e r e c o m m e n d e d N o r m a l T i m e o u t i n t e r v a l o f one s e c o n d i s n o t f e a s i b l e a n d s e c o n d l y , i t w o u l d n o t be u n u s u a l t o f i n d t h e e x p i r y t i m e f o r t i m e r s s e t a t d i f f e r e n t t i m e s t o be t h e same, c a u s i n g T i m e o u t e v e n t s t o o c c u r i n s u c c e s s i o n . In b r i e f , t h e a c c u r a c y o f t h e T i m e o u t m e c h a n i s m c o u l d o n l y be a s p r e c i s e a s t h e r e s o l u t i o n o f t h e c l o c k . 5.5 W r i t e r D e s i g n T h e W r i t e r • i s a t e r m u s e d t o d e n o t e t h e f u n c t i o n w h i c h h a n d l e s t h e t r a n s m i s s i o n o f t h e b a s i c b l o c k . I t s s p e c i f i c t a s k i s t o e x e c u t e a w r i t e t o t h e R i n g d r i v e r a n d p r o c e s s t h e v a l u e r e t u r n e d f r o m t h e c a l l . E r r o r s r e s u l t i n g f r o m t h e w r i t e a r e s t o r e d i n t h e g l o b a l v a r i a b l e e r r n o by t h e s y s t e m . O n l y t h r e e e r r o r t y p e s f r o m t h e R i n g d r i v e r p e r m i t t h e w r i t e a t t e m p t t o be r e p e a t e d ( s e e F i g . 2 l ) ; t h e r e s t a r e u n r e s o l v a b l e a n d f o r c e s t h e S e r v e r t o a b a n d o n t h e c o m m u n i c a t i o n l i n k . T h e f u n c t i o n s e n d t o r i n g r e p r e s e n t i n g t h e W r i t e r i s a s shown b e l o w . 63 s e n d t o r i n g ( u _ n o d e ) USER NODE * u n o d e ; ; { BUFFER * b p t r ; i n t r e t r i e s , d o n e , l e n ; b p t r = u _ n o d e - > x _ q u e ; l e n = b p t r - > l e n _ o f _ b l k ; r e t r i e s * M A X _ T R I E S ; done= F A L S E ; do { i f ( ( w r i t e ( s e r v e r . b b f d , b p t r - > m e s s a g e , l e n ) ) == ERROR ) { / * To p r o c e s s t h e e r r o r m e s s a g e * / s w i t c h ( e r r n o ) { c a s e R E J E C T : c a s e IGNORED: c a s e B A D _ B L O C K : p _ e r r o r ( u _ n o d e - > u s e r _ n u m , e r r n o ) ; r e t u r n ( E R R O R ) ; i f ( ( — r e t r i e s ) < 0 ) { p _ e r r o r ( u _ n o d e - > u s e r _ n u m , e r r n o ) ; r e t u r n ( E R R O R ) ; } b r e a k ; p e r r o r ( " s e n d t o r i n g " ) ; r e t u r n ( E R R O R ) ; c a s e T X M I T E R R : c a s e T I M E O U T : c a s e COUNT O U T : d e f a u l t : } } w h i l e ( ! d o n e ) ; r e t u r n ( F A L S E ) ; } F i g u r e 21 - R e p r e s e n t a t i o n o f W r i t e r I t s h o u l d be c l e a r by now t h a t t h e W r i t e r d o e s n o t r e s i d e i n a p r o c e s s ; a c t i n g a s a s l a v e o r W o r k e r p r o c e s s t o t h e S e r v e r . The i s s u e o f w h e t h e r t h e W r i t e r s h o u l d be r e p r e s e n t e d as a W o r k e r p r o c e s s o r a s p a r t o f t h e S e r v e r i t s e l f i s i n f l u e n c e d by t h e c o n f l i c t i n g n e e d s o f o v e r c o m i n g t h e i n h e r e n t d e a d l o c k p r o b l e m a n d t h e d e s i r e f o r an e l e g a n t a n d c o n c e p t u a l l y e f f i c i e n t 64 d e s i g n i f t h e W o r k e r i s r e p r e s e n t e d a s an " i n d e p e n d e n t p r o c e s s . H a v i n g t h e W r i t e r a s a W o r k e r p r o c e s s r e q u i r e s a n o t h e r p i p e b e t w e e n i t a n d t h e S e r v e r t o f a c i l i t a t e a two way c o m m u n i c a t i o n . . T h i s p i p e w i l l be u s e d by t h e S e r v e r t o p a s s t h e b a s i c b l o c k f o r i t t o be t r a n s m i t t e d by t h e W r i t e r . On h a v i n g s u c c e s s f u l l y t r a n s m i t t e d a b a s i c b l o c k , t h e W r i t e r w o u l d i n f o r m t h e S e r v e r o f t h i s e v e n t t h r o u g h t h e m u l t i p l e x i n g p i p e . I f a t a n y t i m e b o t h p i p e s a r e f i l l e d a n d b o t h S e r v e r a n d W r i t e r a r e b l o c k e d t r y i n g t o w r i t e t o one a n o t h e r , t h e n t h e c l a s s i c a l d e a d l o c k p r o b l e m e n s u e s . T h e d e a d l o c k p r o b l e m c o u l d be o v e r c o m e w i t h a d d e d c o m p l e x i t y t o t h e d e s i g n o f t h e S e r v e r ; h o w e v e r t h e g o a l o f s i m p l i c i t y i s a d o p t e d h e r e by m a k i n g t h e W r i t e r p a r t o f t h e S e r v e r p r o c e s s . A l t h o u g h one may a r g u e t h a t t h e g a i n s i m p l i c i t i n t h e s i m p l i c i t y o f t h e S e r v e r d e s i g n d o e s n o t o f f s e t t h e e l e g a n c e a n d a p p a r e n t e f f i c i e n c y g a i n e d by h a v i n g t h e W r i t e r a s a W o r k e r p r o c e s s , we c o n t e n d h e r e t h a t t h e a p p a r e n t e f f i c i e n c y i s d e b a t a b l e u n l e s s p e r f o r m a n c e m e a s u r e m e n t s a r e a c t u a l l y c o n d u c t e d . I n c r e a s i n g t h e number o f C l i e n t p r o c e s s e s by one w o u l d i n c r e a s e t h e number o f i n s t a n c e s a W o r k e r p r o c e s s h a s t o w a i t f o r t h e u se o f t h e m u l t i p l e x i n g p i p e . T h i s i s b e c a u s e t h e b u f f e r s i z e f o r a p i p e i s o n l y 4096 b y t e s a n d t h e s i z e s o f t h e b a s i c b l o c k s t r a v e l l i n g w i t h i n t h e m u l t i p l e x i n g p i p e i s o f t e n 2048 b y t e s i n l e n g t h - - t h e d e f a u l t s i z e o f t h e b a s i c b l o c k - - a n d c o p y i n g o f b a s i c b l o c k s among t h e S e r v e r , R e a d e r , U s e r a n d t h e W r i t e r o c c u r s q u i t e f r e q u e n t l y . C o m p o u n d i n g t h i s d e t e r i o r a t i o n 65 i s t h a t p i p e s a r e e s s e n t i a l l y f i l e s a n d c o m m u n i c a t i o n u s i n g p i p e s a r e t h e r e f o r e i n h e r e n t l y s l o w . On t h e o t h e r h a n d , h a v i n g t h e W r i t e r a s p a r t o f t h e S e r v e r s i m p l y means t h a t t r a n s m i t t i n g t h e b a s i c b l o c k t o t h e R i n g d r i v e r i s d o n e d i r e c t l y a n d t h e S e r v e r i s b l o c k e d p e n d i n g t h e c o m p l e t i o n o f t h e s y s t e m c a l l w r i t e . T h e i n t e r v a l o f t i m e t h e S e r v e r i s s u s p e n d e d i s h i g h l y d e p e n d e n t on t h e s c h e d u l i n g p o l i c i e s o f t h e s y s t e m a n d n o t on t h e h i g h s p e e d R i n g h a r d w a r e i n t e r f a c e . T h e r e f o r e one may e x p e c t t h e p e r f o r m a n c e o f t h e BSP t o d e t e r i o r a t e when t h e r e a r e many u s e r s l o g g e d o n . 66 V I . CONCLUSIONS G i v e n t h e t i m e c o n s t r a i n t , an i n a d e q u a t e o p e r a t i n g s y s t e m , a s l o w L S I 11 /23 p r o c e s s o r , a n d t h e s i z e o f t h e p r o j e c t i t s e l f , a s i m p l e a n d " w o r k i n g " s y s t e m i s f i n a l l y a c h i e v e d . 6.1 R e f l e c t i o n s On T h e I m p l e m e n t a t i o n s T h e i m p l e m e n t a t i o n o f t h e BBP t o o k a p p r o x i m a t e l y t h r e e m o n t h s t o c o m p l e t e . Two m o n t h s were d e d i c a t e d t o t h e a c t u a l i m p l e m e n t a t i o n a n d one m o n t h t o t h e u n d e r s t a n d i n g o f t h e U n i x k e r n e l a n d o t h e r m i s c e l l a n e o u s d e t a i l s . T h e s e t h r e e m o n t h s s t a t e d , h o w e v e r s p a n n e d o v e r a f o u r m o n t h p e r i o d a s t h e L S I 11 /23 m a c h i n e was n o t a l w a y s a v a i l a b l e f o r s y s t e m d e v e l o p m e n t . The two m o n t h s o f a c t u a l i m p l e m e n t a t i o n t i m e c a n be a t t r i b u t e d t o t h e t e s t i n g p h a s e a n d t h e r e c o m p i l a t i o n t i m e , r a t h e r t h a n t h e a c t u a l c o d i n g . T h i s i s b e c a u s e t h e c o d e i s o n l y a b o u t 250 l i n e s i n l e n g t h . T h e f i n a l s i z e o f t h e BBP c o d e o c c u p i e s 5068 b y t e s ; d e c o m p o s e d i n t o 934 b y t e s f o r t h e t e x t s e g m e n t a n d 4134 b y t e s f o r t h e d a t a s e g m e n t . The BSP i m p l e m e n t a t i o n t o o k a b o u t t h r e e m o n t h s ; p r e s e n t l y , t h e t e s t i n g o f t h e p r o t o c o l i n t h e l o o p - b a c k f a s h i o n i n d i c a t e s i t i s w o r k i n g p r o p e r l y . T h i s t e s t i n g i s f a c i l i t a t e d by e x t e n d i n g t h e d e s i g n by h a v i n g two U s e r p r o c e s s e s i n s t e a d o f one i n t h e S e r v e r / C l i e n t m o d e l o f t h e BSP ( s e e f i g . 1 0 ) . T h e s i z e o f t h e BSP c o d e o c c u p i e s 16036 b y t e s , d e c o m p o s e d i n t o 13156 b y t e s o f t e x t a n d 2880 b y t e s o f d a t a . 67 D e s p i t e t h e i n a d e q u a c y o f t h e I P C o f U N I X , t h e c o d e f o r t h e BSP i s n e v e r t h e l e s s m o d u l a r a n d w e l l s t r u c t u r e d . I t w o u l d t h e r e f o r e be e a s i e r t o m a i n t a i n , a n d i n t h e f u t u r e , w o u l d a l l e v i a t e t h e t a s k o f m o d i f i c a t i o n s t o i m p r o v e o r d e b u g t h i s e v o l v i n g s o f t w a r e . N o t h i n g much was s a i d a b o u t t h e p e r f o r m a n c e o f t h e B S P . T h i s i s p a r t l y due t o a l a c k o f a s u i t a b l e c o n f i g u r a t i o n f o r t e s t i n g . H o w e v e r , c o p y i n g o f b a s i c b l o c k s among t h e S e r v e r , R e a d e r a n d t h e U s e r p r o c e s s e s v i a t h e m u l t i p l e x i n g p i p e u n d o u b t e d l y i n d i c a t e s t h e k i n d o f low p e r f o r m a n c e e x p e c t e d . 6 . 2 S u g g e s t i o n s F o r P o s s i b l e I m p r o v e m e n t s T h e r e c e n t t e s t i n g i n v o l v i n g b o t h t h e L S I 1 1 / 2 3 a n d t h e TI 990 on t h e n e t w o r k s u f f e r e d some t r i v i a l i n c o n s i s t e n c i e s w h i c h were n o t p r e v i o u s l y p e r c e i v e d . S u c h i n c o n s i s t e n c i e s must be i r o n e d o u t . I n a d d i t i o n , t h e BSP m u l t i p l e x o r ha s b e e n i m p l e m e n t e d b u t h a s y e t t o be i n t e g r a t e d w i t h t h e r e s t o f t h e c o d e . H o p e f u l l y , t h e s e a p p a r e n t l y m i n o r t a s k s c o u l d be e r a d i c a t e d w i t h o u t much d e l a y . F u r t h e r r i g o r o u s t e s t i n g o f t h e s e t o f p r o t o c o l s i n v o l v i n g a more c o m p r e h e n s i v e s e t o f s i m u l a t i o n s o f e r r o r s i s a l s o d e s i r a b l e t o p r o m o t e c o n f i d e n c e a n d f a i t h i n t h e u se o f t h i s e v o l v e d p r o d u c t . 68 B I B L I O G R A P H Y 1. B l a i r , G . S . e t a l , " A P r a c t i c a l E x t e n s i o n t o UNIX f o r I n t e r p r o c e s s C o m m u n i c a t i o n " , V o l . 13, 1982 , p p . 4 5 - 5 8 . 2 . C l a r k , D . D . , " M o d u l a r i t y a n d E f f i c i e n c y i n P r o t o c o l I m p l e m e n t a t i o n " , R F C : 8 1 7 , M I T L a b . f o r C o m p u t e r S c i e n c e , C o m p u t e r S y s t e m s a n d C o m m u n i c a t i o n s G r o u p , J u l y 1982 . 3 . C l a r k , D . D . e t a l , " A n I n t r o d u c t i o n t o L o c a l A r e a N e t w o r k s " , P r o c . I E E E , N o v . 1978 , p p . 1 4 9 7 - 1 5 1 7 . 4 . C o l l i n s o n , R . P . , " T h e C a m b r i d g e R i n g a n d U N I X " , S o f t w a r e -P r a c t i c e a n d E x p e r i e n c e , V o l . 12, 1982, p p . 2 4 - 3 9 . 5 . D a l l a s , I . N . , " T r a n s p o r t S e r v i c e B y t e S t r e a m P r o t o c o l " , R e p o r t N o . 1, R e v i s i o n 3 , UKC C o m p u t i n g L a b . , The U n i v e r s i t y o f C a n t e r b u r y , K e n t , C a n t e r b u r y , A u g u s t 1 9 8 1 . 6 . H a v e r t y , J . F . a n d R e t t b u r g , R . D . , " I n t e r p r o c e s s c o m m u n i c a t i o n f o r a s e r v e r i n U N I X " , P r o c . I E E E - C o m p u t e r S o c i e t y I n t e r n a t i o n a l C o n f . on C o m p u t e r C o m m u n i c a t i o n s N e t w o r k s , S e p t e m b e r 1978 , p p . 3 1 2 - 3 1 5 . 7 . I S O / T C 9 7 / S C 1 6 , " D a t a P r o c e s s i n g - O p e n S y s t e m s I n t e r c o n n e c t i o n - B a s i c R e f e r e n c e M o d e l " , D o c u m e n t N537 R e v i s e d , D e c e m b e r 1980 . 8 . J o h n s o n , M . A . , " R i n g b y t e s t r e a m p r o t o c o l s p e c i f i c a t i o n " , S y s t e m s R e s e a r c h G r o u p P a p e r , U n i v e r s i t y o f C a m b r i d g e C o m p u t i n g L a b o r a t o r y , A p r i l 1 9 8 0 . 9 . K e r n i g h a n , B . W . a n d R i t c h i e , D . M . , " T h e C P r o g r a m m i n g L a n g u a g e " , P r e n t i c e - H a l l , 1978 . 10. L i o n s , J . , " A C o m m e n t a r y on t h e UNIX o p e r a t i n g s y s t e m " , D e p t . o f C o m p u t e r S c i e n c e , U n i v e r s i t y o f New S o u t h W a l e s , 1 9 7 7 . 11 . N e e d h a m , R . M . a n d H e r b e r t , A . J . , " T h e C a m b r i d g e D i s t r i b u t e d C o m p u t i n g S y s t e m " , A d d i s o n - W e s l e y , 1982 , p p . 2 4 - 3 9 . 12. R a s h i d , R . F . , " A n i n t e r p r o c e s s c o m m u n i c a t i o n f a c i l i t y f o r U N I X " , T e c h n i c a l R e p o r t C M U - C S - 8 0 - 1 2 4 , D e p a r t m e n t o f C o m p u t e r S c i e n c e , C a r n e g i e - M e l l o n U n i v e r s i t y , P i t t s b u r g h , P A , r e v i s e d J u n e 1980 . 13 . R i t c h i e , D . M . a n d T h o m p s o n , K . , " T h e UNIX t i m e - s h a r i n g s y s t e m " , B e l l S y s . T e c h . J . , V o l . 5 7 , N o . 6 , J u l y 1978 , p p . 1 9 0 5 - 1 9 2 9 . 69 14. T h o m p s o n , K . , " U N I X t i m e - s h a r i n g s y s t e m : UNIX I m p l e m e n t a t i o n " , B e l l S y s . T e c h . J . , V o l . 5 7 , N o . 6 , J u l y 1978 , p p . 1 9 3 1 - 1 9 4 6 . 15 . W i l k e s , M . V . a n d W h e e l e r , D . J . , " T h e C a m b r i d g e D i g i t a l C o m m u n i c a t i o n R i n g " , P r o c . L o c a l A r e a C o m m u n i c a t i o n ' N e t w o r k S y m p o s i u m , M i t r e C o r p . , May 1979 . 70 A P P E N D I X A - T A B U L A T I O N S OF PERFORMANCES OF BBP i . C o n v e n t i o n I / O Number o f b y t e s t r a n s f f e r e d = 48075 b y t e s 1 C l o c k T i c k i n UNIX = 1/60 s e c . B y t e s p e r C l o c k W r i t e s W r i t e s T h r o u g h p u t B a s i c B l k . T i c k s i s s u e d s u c c e s s f u l b i t s / s e c . 25 7491 1942 1923 3080 100 1795 572 481 12855 300 1341 246 161 17208 500 1255 171 97 18387 700 1153 110 69 20013 1000 964 74 49 23937 1300 1049 51 37 21998 1500 1036 51 33 22274 i i . R e a d - A h e a d I / O B y t e s p e r B a s i c B l k C l o c k T i c k s W r i t e s i s s u e d Wr i t e s s u c c e s s f u l T h r o u g h p u t b i t s / s e c . 25 100 300 500 700 1 000 1 300 1 500 7503 1 1 1 7 640 483 492 497 579 800 1 931 484 1 62 97 69 49 37 33 1 923 481 161 97 69 49 37 33 3075 20659 36056 47776 46902 46431 39855 28845 71 i i i . S i g n a l l i n g Number o f b y t e s t r a n s f f e r e d = 17868 b y t e s 1 C l o c k T i c k i n UNIX = 1/60 s e c . B y t e s p e r C l o c k W r i t e s W r i t e s T h r o u g h p u t B a s i c B l k . T i c k s i s s u e d s u c c e s s f u l b i t s / s e c . 25 3450 719 715 2486 1 00 677 181 1 79 1 2669 200 507 92 90 16916 300 418 60 60 2051 8 500 365 36 36 23498 800 355 23 23 241 60 1 000 352 18 18 24365 1 300 397 1 4 1 4 21 604 1 500 352 1 2 1 2 24365 » 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items