UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The design of a verifiable operating system kernel Lockhart, Thomas Wayne 1979

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

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

Item Metadata

Download

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

Full Text

THE DESIGN OF A VERIFIABLE OPERATING SYSTEM KERNEL by THOMAS WAYNE LOCKHART P.Eng., B r i t i s h Columbia, 1975 B.S., Massachusetts I n s t i t u t e o f Technology, 1972 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES Department o f Computer Science We accept t h i s t h e s i s as conforming to the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA November 1979 © Thomas Wayne Lockhart, 1979 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e 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 the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . It i s u n d e r s t o o d tha 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 not 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 . Department o f COMPUTER SCIENCE The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date 16 November 1979 A b s t r a c t The d e s i g n and i m p l e m e n t a t i o n o f an o p e r a t i n g system k e r n e l i s d e s c r i b e d and j u s t i f i e d . The k e r n e l implements p r o c e s s e s and p r i m i t i v e o p e r a t i o n s on p r o c e s s e s . A v a r i e t y o f o p e r a t i n g systems can be implemented by p r o c e s s e s e x e c u t i n g i n the environment the k e r n e l p r o v i d e s . P r o c e s s e s communicate v i a messages. S e v e r a l f a c i l i t i e s found i n o t h e r k e r n e l s , such as memory management and d e v i c e h a n d l i n g , a re not i n c l u d e d . I n s t e a d , the k e r n e l p r o v i d e s o p e r a t i o n s t h a t a l l o w t h e s e s e r v i c e s t o be implemented by p r o c e s s e s . The ease o f r e a s o n i n g about ( i . e . the v e r i f i a b i l i t y o f ) both the k e r n e l and the systems i t s u p p o r t s i s o f p r i m a r y c o n c e r n . The k e r n e l ' s v e r i f i a b i l i t y i s enhanced because: i t has been kept as s m a l l as r e a s o n a b l e ; a l l k e r n e l o p e r a t i o n s a re i n d i v i s i b l e ; the s e m a n t i c s o f the k e r n e l o p e r a t i o n s are s i m p l e ; and, the k e r n e l does not depend upon any p r o c e s s e s f o r i t s c o r r e c t o p e r a t i o n . The v e r i f i a b i l i t y o f systems the k e r n e l s u p p o r t s i s enhanced because they can be m o d u l a r i z e d such t h a t each module can be v e r i f i e d i n d i v i d u a l l y . T h i s i s p o s s i b l e because the k e r n e l e l i m i n a t e s many p r o c e s s i n t e r d e p e n d e n c i e s . An i m p l e m e n t a t i o n o f the k e r n e l t h a t s u p p o r t s a m u l t i - p r o c e s s t e s t system l e n d s e m p i r i c a l s u p p o r t t o the d e s i g n . A l t h o u g h a complete o p e r a t i n g system has not y e t been c o n s t r u c t e d or v e r i f i e d , the r e s u l t s t o date are p r o m i s i n g . 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 v Acknowledgement v i 1 I n t r o d u c t i o n 1 1.1 O b j e c t i v e 1 1.2 S t r a t e g y 2 1.3 K e r n e l D e f i n i t i o n 6 1.4 Background 7 1.5 Summary 11 2 E x e c u t i o n Environment P r o v i d e d 13 2.1 I n t e r p r o c e s s Communication 15 2.2 P r o c e s s Management 19 2.3 Device M a n i p u l a t i o n 23 2.4 Summary 26 3 J u s t i f i c a t i o n o f the Environment 29 3.1 Design C r i t e r i a 29 3.2 I n t e r p r o c e s s Communication 33 3.2.1 Messages 33 3.2.2 Other Communication Mechanisms 38 3.3 P r o c e s s Management 40 3.3.1 System I n i t i a l i z a t i o n 41 3.3.2 P r o c e s s C r e a t i o n 42 3.3.3 P r o c e s s o r S c h e d u l i n g 43 3.3.4 P r o t e c t i o n / S e c u r i t y C o n t r o l . . 44 3.3.5 Memory Management 46 i i i 3.3.6 P r o c e s s D e s t r u c t i o n 47 3.3.7 E x c e p t i o n H a n d l i n g 50 3.3.8 Summary 53 3.4 Device A b s t r a c t i o n 54 3.4.1 G e n e r a l Purpose O p e r a t i o n s 57 3.4.2 Timing D e v i c e s . . . . , 59 3.4.3 C h a r a c t e r D e v i c e s 60 3.4.4 B l o c k D e v i c e s 62 3.4.5 Summary 64 3.5 Chapter Summary 64 4 Implementation o f the K e r n e l 66 4.1 Overview 66 4.1.1 The Zed Language 69 4.1.2 The Host P r o c e s s o r 71 4.2 D e s c r i p t i o n 74 4.2.1 The K e r n e l Data S t r u c t u r e s 74 4.2.2 The K e r n e l F u n c t i o n s 80 4.2.3 S y n c h r o n i z a t i o n S t a t e s 84 4.3 Test System 86 4.4 Summary 87 5 C o n c l u s i o n s 90 5.1 C o n c l u s i o n s 90 5.2 S u g g e s t i o n s f o r F u t u r e Research 95 Re f e r e n c e s 98 i v L i s t of Figures Figure 1: Typical system dependency graph 4 Figure 2: The basic structure of the kernel 67 Figure 3: Synchronization state diagram 85 v Acknowledgement I w i s h t o thank the pe o p l e w i t h o u t whom t h i s t h e s i s would not have been w r i t t e n . Much c r e d i t b e l o ngs t o my s u p e r v i s o r , Dr. D a v i d C h e r i t o n , f o r s u g g e s t i n g the t o p i c , many l i v e l y and p r o d u c t i v e arguments, and much c o n s t r u c t i v e c r i t i c i s m . Many i d e a s , i n c l u d i n g s u s c e p t i b i l i t i e s , a r o s e out o f d i s c u s s i o n s w i t h Steve D e e r i n g , and the r e s t o f the c o f f e e c l u b t o o ! Thanks are due t o Dr. Sam Chanson and John Demco f o r r e a d i n g and commenting on the p e n u l t i m a t e d r a f t . Thanks are a l s o due f o r the f i n a n c i a l s u p p o r t o f NSERC ( f o r m e r l y NRC) and my f a t h e r , Dr. H. B. L o c k h a r t , w i t h o u t which I would have been w o r k i n g f o r a l i v i n g , not w r i t i n g t h i s t h e s i s . F i n a l l y , I would l i k e t o acknowledge my w i f e , M i c h e l e L o c k h a r t , f o r her i n s p i r a t i o n when I was d r y , and f o r her mora l s u p p o r t (and o c c a s i o n a l t h r e a t s ) when I needed them. D e s p i t e the h e l p o f these p e o p l e , the r e s p o n s i b i l i t y f o r the i n e v i t a b l e m i s t a k e s i s mine. v i 1 Chapter 1 I n t r o d u c t i o n T h i s t h e s i s d e s c r i b e s the d e s i g n and i m p l e m e n t a t i o n o f an o p e r a t i n g system k e r n e l . The k e r n e l extends the base machine a r c h i t e c t u r e t o p r o v i d e an environment s u i t a b l e f o r s u p p o r t i n g message-based, m u l t i - p r o c e s s s t r u c t u r e d o p e r a t i n g systems. Chapter 2 d e s c r i b e s the k e r n e l o p e r a t i o n s i n d e t a i l and c h a p t e r 3 j u s t i f i e s t h e i r s e l e c t i o n . Some i n t e r e s t i n g a s p e c t s o f the i m p l e m e n t a t i o n are g i v e n i n c h a p t e r 4, and c h a p t e r 5 p r e s e n t s our c o n c l u s i o n s and s u g g e s t i o n s f o r f u t u r e r e s e a r c h . 1.1 O b j e c t i v e The o b j e c t i v e o f t h i s work i s t o e x p l o r e t e c h n i q u e s f o r b u i l d i n g v e r i f i a b l e o p e r a t i n g systems. A c e n t r a l i d e a i s t h a t o f s t r u c t u r i n g systems as a k e r n e l and a s e t o f c o o p e r a t i n g p r o c e s s e s , a l l o f which can be v e r i f i e d i n d e p e n d e n t l y . V e r i f i c a t i o n i n v o l v e s i n c r e a s i n g c o n f i d e n c e i n system p r o p e r t i e s , through u n d e r s t a n d i n g and c o n v i n c i n g arguments. T h i s r e s e a r c h does not e x p l o r e v e r i f i c a t i o n t e c h n i q u e s , but r a t h e r how t o s t r u c t u r e o p e r a t i n g systems so t h a t e x i s t i n g v e r i f i c a t i o n t e c h n i q u e s can be a p p l i e d t o them. Most o p e r a t i n g systems are so l a r g e and c o n v o l u t e d they are i m p o s s i b l e t o v e r i f y . C o n f i d e n c e i n t h e s e systems i s u s u a l l y based on o p e r a t i o n a l e x p e r i e n c e and t e s t i n g , not u n d e r s t a n d i n g . Advantages o f v e r i f i a b l e d e s i g n i n c l u d e : m a i n t a i n a b i l i t y , r o b u s t n e s s o f s o f t w a r e , and s e c u r i t y as w e l l as i n c r e a s e d c o n f i d e n c e i n the system. In a d d i t i o n t o b e i n g v e r i f i a b l e , o t h e r p r o p e r t i e s are o f 2 i n t e r e s t . The systems s h o u l d be a b l e t o meet r e a l - t i m e c r i t e r i a f o r r e s p o n d i n g t o e x t e r n a l e v e nts w i t h i n a c o n s t a n t maximum tim e . T h e i r d e s i g n s s h o u l d be machine-independent f o r p o r t a b i l i t y . A l e v e l o f f u n c t i o n a l i t y s i m i l a r t o UNIX, Thoth or o t h e r advanced o p e r a t i n g systems must be p o s s i b l e . And f i n a l l y , t hey must be implementable w i t h s u f f i c i e n t e f f i c i e n c y t o be u s e f u l . The d i f f i c u l t i e s o f u n d e r s t a n d i n g an o p e r a t i n g system came t o the a u t h o r ' s a t t e n t i o n when s t u d y i n g the k e r n e l o f the Thoth system. Even though Thoth i s h i g h l y modular i n n a t u r e , the c o r r e c t o p e r a t i o n o f i t s k e r n e l depends upon the c o r r e c t o p e r a t i o n o f the system p r o c e s s e s , which i n t u r n depends upon the k e r n e l . Thus u n d e r s t a n d i n g Thoth's k e r n e l r e q u i r e s u n d e r s t a n d i n g c o n s i d e r a b l y more than j u s t the k e r n e l . I n h i s Ph.D. t h e s i s , C h e r i t o n [1979a] d i s c u s s e d the problem t h i s c i r c u l a r i t y causes f o r the v e r i f i c a t i o n o f Thoth. S o l v i n g t h i s problem was the o r i g i n a l o b j e c t i v e o f t h i s work. T h i s was e xtended, however, when i t was d i s c o v e r e d t h a t c a r e f u l k e r n e l d e s i g n would not o n l y make the k e r n e l independent o f the system p r o c e s s e s , but would a l s o a l l o w the system p r o c e s s e s t o be d e s i g n e d so they c o u l d be v e r i f i e d i n d i v i d u a l l y . 1.2 S t r a t e g y " D i v i d e and conquer" i s the b a s i c s t r a t e g y f o r making the system v e r i f i a b l e . I f the system i s s t r u c t u r e d as a number o f s m a l l modules t h a t can be c o n s i d e r e d i n d i v i d u a l l y , i t s v e r i f i a b i l i t y i s g r e a t l y enhanced. The r e q u i r e d independence can 3 be demonstrated w i t h a dependency graph. The dependency graph o f a system i n c l u d e s a node f o r each module, and d i r e c t e d a r c s from each node t o the modules i t depends on f o r i t s c o r r e c t o p e r a t i o n . I f t h i s d i g r a p h i s a c y c l i c , then t h e r e are no c i r c u l a r d e p endencies. Thus, the c o r r e c t n e s s o f each module can be demonstrated i n d e p e n d e n t l y by assuming the c o r r e c t n e s s o f a l l modules i t depends on. When a l l modules are v e r i f i e d , the system has been v e r i f i e d . The o n l y g l o b a l p r o p e r t y t h a t needs t o be demonstrated i s t h a t the dependency graph i s a c y c l i c . T h i s a c y c l i c dependency n o t i o n i s f i r s t a t t r i b u t e d t o D i j k s t r a [1968b]. P r o c e s s e s p l u s the k e r n e l c o n s t i t u t e the modules o f the systems the k e r n e l s u p p o r t s . Independent modules cannot share an address space, thus the k e r n e l must have i t s own address space and i t must a l l o w the p r o c e s s e s t o have d i s t i n c t a d d r ess spaces as w e l l . O c c a s i o n a l l y i t i s advantageous f o r c l o s e l y c o o p e r a t i n g p r o c e s s e s t o share an address space, however they then c o n s t i t u t e a s i n g l e module. F i g u r e 1 shows the dependency graph o f a t y p i c a l system the k e r n e l c o u l d s u p p o r t . 4 KERNEL (Note 2) Note 1 - A l l p r o c e s s e s depend upon the memory p r o p r i e t o r . Note 2 - A l l p r o c e s s e s depend upon the k e r n e l . FIGURE 1: TYPICAL SYSTEM DEPENDENCY GRAPH 5 The c r i t e r i a t h a t g u i d e d the d e s i g n o f the k e r n e l are based upon t h i s b a s i c s t r a t e g y , p l u s the s t r a t e g i e s o f k e e p i n g the k e r n e l s m a l l and s i m p l e . Two s e t s o f c r i t e r i a were employed, as the k e r n e l d e s i g n i n v o l v e s two a c t i v i t i e s : d e s i g n i n g the environment p r o v i d e d by the k e r n e l ; and, implementing t h i s e nvironment. These c r i t e r i a are d i s c u s s e d i n d e t a i l i n c h a p t e r 3, however they are summarized here t o c l a r i f y our s t r a t e g y and o b j e c t i v e s . The c r i t e r i a t h a t g u i d e d the d e s i g n o f the environment i n c l u d e : 1. The k e r n e l s h o u l d a l l o w the systems i t s u p p o r t s t o be m o d u l a r i z e d w i t h an a c y c l i c dependency graph. 2. The k e r n e l s h o u l d not p r o v i d e f a c i l i t i e s t h a t can be p r o v i d e d e f f i c i e n t l y by a p r o c e s s . 3. The k e r n e l o p e r a t i o n s s h o u l d have s i m p l e w e l l d e f i n e d s e m a n t i c s . 4. I t must be p o s s i b l e t o implement the environment w i t h i n the i m p l e m e n t a t i o n c r i t e r i a . The c r i t e r i a t h a t g u i d e d the i m p l e m e n t a t i o n o f the k e r n e l i n c l u d e : 1. The k e r n e l o p e r a t i o n s s h o u l d be i n d i v i s i b l e . 2. The maximum time f o r the k e r n e l t o respond t o e x t e r n a l e v e n t s s h o u l d be s m a l l and bounded by a c o n s t a n t . 3. The d e s i g n s h o u l d be machine independent. 4. The i m p l e m e n t a t i o n s h o u l d be e f f i c i e n t . Only the f i r s t o f these i m p l e m e n t a t i o n c r i t e r i a i s m o t i v a t e d by v e r i f i a b i l i t y , the o t h e r s r e f l e c t a d d i t i o n a l d e s i r e d system p r o p e r t i e s . 6 1.3 K e r n e l D e f i n i t i o n S e v e r a l d e f i n i t i o n s o f o p e r a t i n g system k e r n e l s are found i n the l i t e r a t u r e . "The k e r n e l i s a p r i m i t i v e monitor that implements o b j e c t s and i n d i v i s i b l e o p e r a t i o n s on these o b j e c t s as an exten s i o n o f the b a s i c machine a r c h i t e c t u r e . " [ C h e r i t o n 1979a](Thoth). "The k e r n e l i s the onl y program i n DEMOS which executes i n monitor mode so th a t memory p r o t e c t i o n between tasks can be enf o r c e d . " [ C l i f f o r d & Montague, 1978](DEMOS). "The lowest l a y e r , the k e r n e l , p r o v i d e s b a s i c s e r v i c e s such as i n t e r p r o c e s s communication, process d i s p a t c h i n g and t r a p and i n t e r r u p t h a n d l i n g . " [Lycklama & Bayer, 1978](MERT). " E s s e n t i a l l y the monitor i s a software e x t e n s i o n o f the hardware s t r u c t u r e , which makes the RC4000 more a t t r a c t i v e f o r multiprogramming." [Brinch Hansen, 1969] (RC4000). "A s e c u r i t y k e r n e l i s a s m a l l , i s o l a t e d p a r t of the o p e r a t i n g system, b u i l t at the lowest l e v e l , which i s g e n e r a l l y intended to c o n t a i n a l l the s e c u r i t y enforcement code. " [Popek & K l i n e , 1977](UCLA-VM). "The k e r n e l that i s r e f e r r e d to here i s d e f i n e d as a l l programs that implement or a f f e c t access c o n t r o l of any kind, d i s c r e t i o n a r y or n o n - d i s c r e t i o n a r y . " [Schroeder e t . a l . , 1 9 7 7 ] ( M u l t i c s ) . In t h i s t h e s i s , the k e r n e l i s d e f i n e d as the l o w e s t l e v e l o f s o f t w a r e . I t i s independent o f a l l o t h e r s o f t w a r e , and implements m u l t i p l e p r o c e s s e s by a b s t r a c t i n g the hardware i n t e r r u p t and p r o t e c t i o n mechanisms. T h i s i s a s y n t h e s i s o f the co n c e p t s o f a multi-programming k e r n e l or n u c l e u s , and a s e c u r i t y k e r n e l . I t does not " c o n t a i n a l l the s e c u r i t y enforcement code", but i t does c o n t a i n the l o w e s t l e v e l o f t h i s code. The k e r n e l has complete c o n t r o l o f the s e c u r i t y f e a t u r e s 7 of the hardware, access to the d e v i c e s ( i n c l u d i n g the f i l e support d e v i c e s ) , and the memory. The k e r n e l can be thought of as a p r i m i t i v e o p e r a t i n g system, p r o v i d i n g a s e t of l o w - l e v e l , p r i m i t i v e "system c a l l s " that can then be used to implement a f u l l o p e r a t i n g system. More s p e c i f i c a l l y , the k e r n e l p r o v i d e s : 1. many inexpensive d e t e r m i n i s t i c processes; 2. i n t e r p r o c e s s communication v i a s m a l l synchronous messages, and a data t r a n s f e r f a c i l i t y . 3. o p e r a t i o n s f o r process management, which i n c l u d e s : dynamic process c r e a t i o n and d e s t r u c t i o n , f l e x i b l e processor s c h e d u l i n g , memory management, and e x c e p t i o n h a n d l i n g ; 4. a simple system i n i t i a l i z a t i o n mechanism; 5. d e v i c e a b s t r a c t i o n , i n c l u d i n g : l i m i t e d access, c o n t r o l l e d DMA, and b u f f e r i n g f o r e f f i c i e n t h a n d l i n g of r a p i d i n t e r r u p t s . The k e r n e l does not provide memory management, a f i l e system, or h i g h - l e v e l a b s t r a c t i o n of d e v i c e s . I t does however, as mentioned above, provide o p e r a t i o n s so that these f a c i l i t i e s can be p r o v i d e d by system pro c e s s e s . For example, the k e r n e l p r o v i d e s o p e r a t i o n s f o r changing processes' address spaces and e x e c u t i o n p r i o r i t i e s , but i t i s up to the system processes to implement swapping, or some other memory management scheme. 1.4 Background T h i s work extends p r e v i o u s r e s e a r c h done on the RC4000, UNIX, M u l t i c s , UCLA-VM, MERT, DEMOS, and Thoth o p e r a t i n g systems. 8 The RC4000 system [ B r i n c h Hansen 1969, 1970] i n t r o d u c e d the i d e a o f s t r u c t u r i n g an o p e r a t i n g system as a k e r n e l (or n u c l e u s ) which implements p r o c e s s e s and messages, p l u s a s e t o f system p r o c e s s e s . Our con c e r n f o r v e r i f i a b i l i t y l e a d t o a number o f d i f f e r e n c e s from the RC4000 k e r n e l . For example, our k e r n e l a b s t r a c t s d e v i c e s v i a r e s t r i c t e d k e r n e l o p e r a t i o n s , w h i l e the RC4000 system p r o v i d e d e x t e r n a l (pseudo) p r o c e s s e s . I t a l s o p r o v i d e d dynamic b u f f e r i n g o f messages, w i t h the p o s s i b i l i t y f o r one p r o c e s s t o send many messages c o n c u r r e n t l y , whereas our message-passing i s t o t a l l y synchronous. The k e r n e l o f the UNIX system [ R i t c h i e & Thompson, 1974] i s s i m i l a r t o our s i n t h a t : i t extends the f a c i l i t i e s o f the h o s t p r o c e s s o r t o p r o v i d e a m u l t i - p r o c e s s environment; i t i s the o n l y s o f t w a r e t o run i n p r i v i l e g e d mode and thus have f u l l c o n t r o l o f the hardware; i t o n l y depends on the hardware f o r i t s c o r r e c t o p e r a t i o n ; and i t has a s e p a r a t e address space. However, i t d i f f e r s i n t h a t i t implements most o f the UNIX environment, i n c l u d i n g the f i l e system, I/O system, and memory management, which c o n s t i t u t e s most o f what i s t y p i c a l l y c o n s i d e r e d t o be an o p e r a t i n g system. These d i f f e r e n c e s are due p r i m a r i l y t o our d e s i r e t o b u i l d a s m a l l k e r n e l t h a t s u p p o r t s a s e t o f system p r o c e s s e s , w h i l e UNIX uses a v e r y d i f f e r e n t s t r u c t u r i n g t e c h n i q u e . The o b j e c t i v e o f the M u l t i c s k e r n e l d e s i g n p r o j e c t [Schroeder e t . a l . , 1977], t o p r o v i d e v e r i f i a b l e s e c u r i t y o f an o p e r a t i n g system, was s i m i l a r t o o u r s . The b a s i c s t a t e g y was the same as w e l l . They emphasized the a c y c l i c dependency n o t i o n and 9 attemp t e d t o remove unn e c e s s a r y f u n c t i o n s from the k e r n e l . M u l t i c s i s n o t , however, a message-based m u l t i p r o c e s s s t r u c t u r e d system. A l s o , the k e r n e l t o which they r e f e r i s a s e c u r i t y k e r n e l , n o t s p e c i f i c a l l y a multiprogramming k e r n e l as o u r s i s , and thu s i t implements more o f the f u n c t i o n s o f the system. The s c a l e o f t h e i r system i s much l a r g e r than ours as w e l l . The UCLA-VM system [Popek & K l i n e , 1977] i s s i m i l a r t o ours i n t h a t i t i s p r i m a r i l y concerned w i t h v e r i f i a b i l i t y . I t i s a l s o s t r u c t u r e d as a k e r n e l (or l e v e l s o f k e r n e l s ) p l u s a s e t o f p r o c e s s e s . The k e r n e l s even have s i m i l a r p r o p e r t i e s , such a s : be i n g the l o w e s t l e v e l o f s o f t w a r e i n the system; b e i n g the o n l y " p r i v i l e g e d mode" s o f t w a r e ; h a v i n g address spaces d i s t i n c t from a l l p r o c e s s e s ; b e i n g s m a l l ; and h a v i n g i n d i v i s i b l e o p e r a t i o n s . These s i m i l a r i t i e s r e f l e c t our s i m i l a r c o n c e r n s , but are overshadowed by the d i f f e r e n c e s . The e n v i r o n m e n t s , or a b s t r a c t machines, p r o v i d e d by the two k e r n e l s a re v e r y d i f f e r e n t . The UCLA-VM k e r n e l i n c l u d e s " s e c u r i t y o b j e c t s " and i s p r i m a r i l y c oncerned w i t h c o n t r o l l i n g a c c e s s t o the s e o b j e c t s . I t does not p r o v i d e g e n e r a l purpose i n t e r p r o c e s s communication f a c i l i t i e s . Because o f t h i s , i t i s u n s u i t a b l e f o r s u p p o r t i n g systems w i t h d i f f e r e n t system p r o c e s s s t r u c t u r e s . T h i s i s q u i t e d i f f e r e n t than our k e r n e l which makes no assumptions about the system p r o c e s s s t r u c t u r e . F i n a l l y , t h e y make no attempt t o e x p l o i t the a c y c l i c dependency n o t i o n . MERT [Lycklama & B a y e r , 1978] c o n t a i n s a k e r n e l somewhat s i m i l a r t o o u r s . I t i s s t r u c t u r e d as f o u r l a y e r s : a k e r n e l , k e r n e l p r o c e s s e s , s u p e r v i s o r p r o c e s s e s , and user p r o c e s s e s . 10 "A r i c h s e t o f i n t e r - p r o c e s s communication mechanisms i n c l u d i n g messages, e v e n t s ( s o f t w a r e i n t e r r u p t s ) , s h a r e d memory, i n t e r - p r o c e s s t r a p s , p r o c e s s p o r t s , and f i l e s a l l o w a p p l i c a t i o n s t o be implemented as s e v e r a l i n d ependent, c o o p e r a t i n g p r o c e s s e s " . [Lycklama & Baye r , 1978] On the s u r f a c e , the s t r a t e g y o f the MERT d e s i g n e r s i s v e r y s i m i l a r t o o u r s . The b a s i c s t r u c t u r e i s the same: a k e r n e l s u p p o r t i n g a s e t o f system p r o c e s s e s . However, t h e i r r e s e a r c h o b j e c t i v e s were q u i t e d i f f e r e n t . For example, our c r i t e r i o n o f v e r i f i a b i l i t y made t h e i r d i v e r s e s e t o f i n t e r p r o c e s s communication p r i m i t i v e s u n a c c e p t a b l e . They c o n s i d e r e d the p r o t e c t i o n / e f f i c i e n c y t r a d e o f f , and opted f o r e f f i c i e n c y . As our p r i m a r y c o n c e r n i s v e r i f i a b i l i t y , we opted f o r p r o t e c t i o n and have attempted t o f i n d ways t o be e f f i c i e n t d e s p i t e the p r o t e c t i o n . DEMOS [ C l i f f o r d & Montague, 1978] i s a k e r n e l / p r o c e s s s t r u c t u r e d system concerned w i t h s e c u r i t y . I t s k e r n e l i s s i m i l a r t o ours i n t h a t i t implements p r o c e s s e s and message-passing. A l s o , i t has i t s own address space, which i s d i s t i n c t from t h a t o f most p r o c e s s e s . The major d i f f e r e n c e i s c o m p l e x i t y . I t s l i n k - b a s e d message-passing [ B a s k e t t e t . a l . , 1977], which i n c l u d e s dynamic message b u f f e r i n g , i s much more complex than our scheme. A l s o , DEMOS does not e x p l o i t the a c y c l i c dependency n o t i o n , nor are i t s k e r n e l o p e r a t i o n s i n d i v i s i b l e . Thoth [ C h e r i t o n , 1979a, 1979c] demonstrated the f e a s i b i l i t y o f a s e t o f p r i m i t i v e s f o r s t r u c t u r i n g an o p e r a t i n g system as a s e t o f c o o p e r a t i n g d e t e r m i n i s t i c p r o c e s s e s . S e v e r a l o f thes e p r i m i t i v e s , i n p a r t i c u l a r the i n t e r p r o c e s s communication 11 p r i m i t i v e s , were adopted by our k e r n e l . Thoth*s " k e r n e l " , which implements these p r i m i t i v e s , i s not s e p a r a t e d from the system p r o c e s s e s . I t sha r e s a common address space w i t h the system p r o c e s s e s , some o f which even have r e s p o n s i b i l i t y f o r m a i n t a i n i n g some k e r n e l d a t a s t r u c t u r e s . T h i s l a c k o f independence i s the main d i f f e r e n c e between i t and our k e r n e l . A s i g n i f i c a n t i m p l i c a t i o n o f t h i s i s t h a t our k e r n e l must p r o v i d e p r o c e s s management and d e v i c e m a n i p u l a t i o n o p e r a t i o n s , which are not r e q u i r e d o f the Thoth k e r n e l . In summary, the b a s i c k e r n e l / p r o c e s s s t r u c t u r e which we propose i s not new. What i s new i s our e x p l o i t a t i o n o f the a c y c l i c dependency n o t i o n , i n a message-based m u l t i - p r o c e s s e nvironment, t o a c h i e v e v e r i f i a b i l i t y . 1.5 Summary The o b j e c t i v e o f t h i s r e s e a r c h i s t o e x p l o r e t e c h n i q u e s f o r b u i l d i n g v e r i f i a b l e o p e r a t i n g systems. In p a r t i c u l a r , the s t r u c t u r e o f a k e r n e l p l u s a s e t o f system p r o c e s s e s i s e x p l o r e d . The i n t e r d e p e n d e n c i e s o f system modules are reduced so the system can have an a c y c l i c dependency g r a p h , which i m p l i e s t h a t each module can be v e r i f i e d i n d i v i d u a l l y . The k e r n e l i s d e f i n e d t o be the l o w e s t l e v e l o f s o f t w a r e . I t extends the f a c i l i t i e s o f the hardware t o p r o v i d e an e x e c u t i o n environment i n c l u d i n g m u l t i p l e p r o c e s s e s . Most s i m i l a r systems have not had v e r i f i a b i l i t y as a p r i m a r y d e s i g n c o n s t r a i n t . The main c o n t r i b u t i o n o f t h i s r e s e a r c h i s the d e m o n s t r a t i o n t h a t s t r i c t r u l e s o f i n t e r - m o d u l e dependencies can be e n f o r c e d 12 without impacting e f f i c i e n c y severely. Although "breaking the rules" may be the most obvious method of improving the e f f i c i e n c y of a mechanism, when forced to look, an e f f i c i e n t but legitimate technique can usually be found. 13 Chapter 2 E x e c u t i o n Environment P r o v i d e d The e x e c u t i o n environment implemented by the k e r n e l c o n s i s t s o f a s e t o f p r o c e s s e s , a s e t o f d e v i c e s , and o p e r a t i o n s f o r i n t e r p r o c e s s communication, p r o c e s s management, and d e v i c e m a n i p u l a t i o n . A message-based i n t e r p r o c e s s communication scheme i s used, i n c l u d i n g o p e r a t i o n s f o r " r e a d i n g , w r i t i n g , and s y n c h r o n o u s l y exchanging message b u f f e r s . T h i s scheme i s augmented by a d a t a move o p e r a t i o n . The p r o c e s s management o p e r a t i o n s can be used by a u t h o r i z e d p r o c e s s e s t o : c r e a t e and d e s t r o y p r o c e s s e s ; c o n t r o l p r o c e s s a t t r i b u t e s ; and handle e x c e p t i o n s . A u t h o r i z e d p r o c e s s e s use the d e v i c e m a n i p u l a t i o n o p e r a t i o n s t o c o n t r o l , communicate, and s y n c h r o n i z e w i t h t i m i n g , c h a r a c t e r , and b l o c k d e v i c e s . A p r o c e s s d e t e r m i n i s t i c a l l y e x e c u t e s a s u b s e t o f the h o s t machine's i n s t r u c t i o n s e t enhanced w i t h the k e r n e l o p e r a t i o n s . The a t t r i b u t e s o f a p r o c e s s i n c l u d e : 1. i d - an unique i d e n t i f i e r used t o r e f e r t o the p r o c e s s . I d ' s have two f i e l d s , an i n d e x number, and a c y c l e number. Index numbers are used f o r e f f i c i e n t a c c e s s t o p e r - p r o c e s s d a t a , because they are unique f o r a l l e x i s t e n t p r o c e s s e s . Zero i s a s p e c i a l i n v a l i d i d , used as an e r r o r i n d i c a t i o n and t o i n d i c a t e an u n s p e c i f i c p r o c e s s f o r some o p e r a t i o n s ; 2. machine s t a t e - a copy o f the h o s t p r o c e s s o r ' s r e g i s t e r s used by the p r o c e s s . T h i s i s a machine-dependent p r o p e r t y . For example, f o r the TI990, a machine s t a t e i n c l u d e s t h r e e r e g i s t e r s : the s t a t u s r e g i s t e r , ST; the program c o u n t e r , PC; 14 and the workspace p o i n t e r , WP; 3. map - a s p e c i f i c a t i o n o f the main memory a c c e s s i b l e t o the p r o c e s s , ( i t s address s p a c e ) . T h i s i s a machine-dependent p r o p e r t y , w h i c h , f o r the TI990, i s a 6-word v e c t o r s p e c i f y i n g the base and l i m i t o f each o f t h r e e memory segments; 4. p r i o r i t y - an i n t e g e r used t o determine the p r i o r i t y w i t h which the p r o c e s s i s a l l o c a t e d the p r o c e s s o r ; 5. s t a t u s - i n d i c a t i n g the c a p a b i l i t i e s ( f o r r e s t r i c t e d k e r n e l o p e r a t i o n s and d e v i c e a c c e s s ) and s u s c e p t i b i l i t i e s ( t o p r o c e s s management o p e r a t i o n s ) p o s s e s s e d by the p r o c e s s ; 6. v i o l a t i o n - an i n d i c a t i o n o f the n a t u r e o f the l a s t e x c e p t i o n caused by the p r o c e s s . The k e r n e l a l l o c a t e s the p r o c e s s o r t o ( d i s p a t c h e s ) the p r o c e s s w i t h the h i g h e s t p r i o r i t y t h a t has been ready f o r the l o n g e s t t i m e . A p r o c e s s ' s p r i o r i t y i s a l s o used t o d e t e r m i n e i t s i n t e r r u p t a b i l i t y on machines t h a t have s e l e c t i v e i n t e r r u p t masks. The h i g h e r a p r o c e s s ' s p r i o r i t y , the l e s s i n t e r r u p t a b l e i t i s . The k e r n e l p r o v i d e s a p r o t e c t i o n scheme based on c a p a b i l i t i e s f o r e x e c u t i n g r e s t r i c t e d o p e r a t i o n s , and a c c e s s i n g d e v i c e s . A s s o c i a t e d w i t h each r e s t r i c t e d o p e r a t i o n and w i t h each d e v i c e (or group o f d e v i c e s ) i s a c a p a b i l i t y . The s t a t u s o f a p r o c e s s i n d i c a t e s what o p e r a t i o n s and d e v i c e s i t p o s s e s s e s the c a p a b i l i t y t o use. I t a l s o i n d i c a t e s the s u s c e p t i b i l i t i e s o f the p r o c e s s , which determine which p r o c e s s management o p e r a t i o n s may a f f e c t i t . S u s c e p t i b i l i t i e s are used t o p r e v e n t the system p r o c e s s e s from depending on each o t h e r f o r t h e i r c o r r e c t 15 operation. Some exceptional conditions are detected by the kernel. When a process causes one of these error s i t u a t i o n s , (e.g. by attempting to access data outside of i t s address space), i t is arrested, which means that i t i s coerced by the kernel into sending to an exception handling process. This exception handler w i l l then decide what to do about the exception, which could include restarting the offending process. Only conditions that are not expected to occur under normal circumstances res u l t in being arrested. Less serious exceptions, such as replying to a non-existent process, r e s u l t in an error indication being returned by the kernel operation. The kernel abstracts the devices of the system only to the degree necessary to allow system processes to e f f i c i e n t l y and safely access them. Devices are c l a s s i f i e d into three types: timing, character, and block. Operations are supplied for manipulating each of these types of devices. In addition, general-purpose operations allow d i r e c t access to the control registers of most devices. The following sections describe the kernel operations in d e t a i l . 2.1 Interprocess Communication Processes synchronize and exchange small amounts of data with each other v i a messages. Each process has one message buffer, which i s a small (8-word) vector in the kernel's address space. 16 P r o c e s s e s r e a d , w r i t e , and s y n c h r o n o u s l y exchange t h e i r message b u f f e r s w i t h o t h e r p r o c e s s e s u s i n g the f o l l o w i n g o p e r a t i o n s . .Write_msg( msg ) c o p i e s the v e c t o r a t msg i n the i n v o k e r ' s address space t o i t s message b u f f e r . An e x c e p t i o n o c c u r s i f the v e c t o r s p e c i f i e d i s not i n the i n v o k e r ' s address space. s e n d e r _ i d = .Read_msg( msg ) c o p i e s the i n v o k e r ' s message b u f f e r t o msg i n i t s a d dress space, r e t u r n i n g the i d o f the p r o c e s s t h a t s e n t (or r e p l i e d to) the message. An e x c e p t i o n o c c u r s i f the s p e c i f i e d v e c t o r i s not i n the i n v o k e r ' s address space. .Send_msg( r e c e i v e r _ i d ) b l o c k s the i n v o k e r u n t i l i t s message b u f f e r has been r e c e i v e d by the s p e c i f i e d r e c e i v e r , forwarded z e r o or more t i m e s , and r e p l i e d t o . The i n v o k e r a w a i t s a r e p l y . The r e p l i e r ' s i d i s r e t u r n e d by the .Read_msg o p e r a t i o n , d e s c r i b e d above. An e x c e p t i o n i s caused i f r e c e i v e r _ i d i s i n v a l i d . ,Await_msg( s e n d e r _ i d ) b l o c k s the i n v o k e r u n t i l a message i s r e c e i v e d from the s p e c i f i e d s e n d e r , u n l e s s the message has a l r e a d y been s e n t , i n which case i t i s r e c e i v e d i m m e d i a t e l y . I f i d i s z e r o , the sender i s u n s p e c i f i e d , and the e a r l i e s t message s e n t t o the i n v o k i n g p r o c e s s i s r e c e i v e d . The sender can be d e t e r m i n e d w i t h the .Read_msg o p e r a t i o n d e s c r i b e d above. An e x c e p t i o n o c c u r s i f s e n d e r _ i d i s an i n v a l i d i d o t h e r than z e r o . s e n d e r _ i d = .Receive_msg( s e n d e r _ i d ) 17 i s the same as .Await_msg e x c e p t t h a t i n s t e a d o f b l o c k i n g , i t r e t u r n s z e r o i f the message has not been s e n t , o t h e r w i s e i t r e t u r n s the sender's i d . I f s e n d e r _ i d i s i n v a l i d , an e r r o r i n d i c a t i o n i s r e t u r n e d . ok = .Reply_msg( s e n d e r _ i d ) u n b l o c k s the p r o c e s s s p e c i f i e d by s e n d e r _ i d a f t e r exchanging message b u f f e r s w i t h i t . An e r r o r i n d i c a t i o n i s r e t u r n e d i f i d i s not v a l i d . An e x c e p t i o n i s caused i f the p r o c e s s s p e c i f i e d by s e n d e r _ i d i s not a w a i t i n g a r e p l y from the i n v o k e r . ok = .Forward_msg( s e n d e r _ i d , r e c e i v e r _ i d ) causes the p r o c e s s s p e c i f i e d by s e n d e r _ i d t o send the i n v o k e r ' s message b u f f e r t o the r e c e i v e r s p e c i f i e d by r e c e i v e r _ i d . The r e c e i v e r r e c e i v e s the i n v o k e r ' s message b u f f e r as i f i t had been sent by the sender. The i n v o k e r does not b l o c k . I f e i t h e r s e n d e r _ i d or r e c e i v e r _ i d are i n v a l i d , an e r r o r i n d i c a t i o n i s r e t u r n e d . I f the sender i s not a w a i t i n g a r e p l y from the i n v o k e r , an e x c e p t i o n o c c u r s . A p r o c e s s can f o r w a r d a message t o i t s e l f , which has the e f f e c t o f p u t t i n g the message t o the end o f i t s incoming message queue. ok = .Move( n_words, s r c _ i d , s r c , d s t _ i d , d s t ) moves a v e c t o r o f n_words from s r c i n the address space o f the so u r c e p r o c e s s s p e c i f i e d by s r c _ i d , t o d s t i n the d e s t i n a t i o n p r o c e s s ' s ( d s t _ i d ) address space. Both p r o c e s s e s must have e l i g i b l e p r i o r i t i e s , i n d i c a t i n g they are i n memory. I f e i t h e r i d i s i n v a l i d , o r e i t h e r p r o c e s s has an i n e l i g i b l e p r i o r i t y , an e r r o r i n d i c a t i o n i s r e t u r n e d . Both p r o c e s s e s must be a w a i t i n g r e p l y from the i n v o k e r or be the i n v o k e r , o t h e r w i s e an e x c e p t i o n 1 8 o c c u r s . An e x c e p t i o n a l s o o c c u r s i f e i t h e r v e c t o r s p e c i f i e d i s not i n i t s r e s p e c t i v e address space. An example o f a t y p i c a l i n t e r a c t i o n may c l a r i f y how these o p e r a t i o n s are used. Assume t h e r e are two p r o c e s s e s : a p r o p r i e t o r p r o c e s s t h a t performs s e r v i c e i n response t o r e q u e s t s ; and a r e q u e s t o r p r o c e s s t h a t r e q u i r e s the p r o p r i e t o r ' s s e r v i c e s . The s t a n d a r d form o f a p r o p r i e t o r p r o c e s s i s : • P r o p r i e t o r ( ) \ I n i t i a l i z a t i o n , r e p e a t •Await_msg( 0 ) ; \ From any p r o c e s s . \ P r o p r i e t o r may be b l o c k e d h e r e . r e q u e s t o r = .Read_msg( r e q u e s t ) ; \ Performs the r e q u e s t e d s e r v i c e . \ T h i s might i n v o l v e moving d a t a t o or \ from the r e q u e s t o r u s i n g .Move. \ B u i l d s the r e p l y . •Write_msg( r e p l y ); •Reply_msg( r e q u e s t o r ); } 1 The r e q u e s t o r r e q u e s t s s e r v i c e from the p r o p r i e t o r by: b u i l d i n g the r e q u e s t , w r i t i n g i t i n t o i t s message b u f f e r ( w i t h .Write_msg), and s e n d i n g i t t o the p r o p r i e t o r . Sending b l o c k s the r e q u e s t o r u n t i l i t s r e q u e s t has been s e r v i c e d and r e p l i e d t o . When the r e q u e s t o r resumes e x e c u t i o n , i t reads the r e p l y from i t s b u f f e r ( w i t h .Read_msg), and p r o c e e d s . 19 2.2 P r o c e s s Management The k e r n e l p r o v i d e s o p e r a t i o n s t h a t a u t h o r i z e d p r o c e s s e s can use t o : c r e a t e and d e s t r o y p r o c e s s e s , c o n t r o l the c a p a b i l i t i e s o f p r o c e s s e s , s c h e d u l e the p r o c e s s o r , manage main memory, and han d l e e x c e p t i o n a l c o n d i t i o n s . These r e s t r i c t e d o p e r a t i o n s may o n l y be in v o k e d by a p r o c e s s whose s t a t u s i n d i c a t e s t h a t i t has the c a p a b i l i t y f o r the o p e r a t i o n . The f i r s t p r o c e s s i s c r e a t e d by the k e r n e l when the system i s s t a r t e d . I t has a l l c a p a b i l i t i e s , the h i g h e s t p r i o r i t y , and the maximum address space ( d i s j o i n t from the k e r n e l ' s address s p a c e ) . A l l o t h e r p r o c e s s e s are descendants o f t h i s r o o t p r o c e s s which has the r e s p o n s i b i l i t y t o complete the i n i t i a l i z a t i o n o f the system, i n c l u d i n g the c r e a t i o n o f the r e s t o f the system p r o c e s s e s . new_id = . C r e a t e _ p r o c e s s ( ) c r e a t e s a p r o c e s s r e t u r n i n g i t s i d , u n l e s s the maximum number o f p r o c e s s e s a l r e a d y e x i s t , i n which case i t r e t u r n s z e r o . The c r e a t e d p r o c e s s has no memory, no s t a t u s , an i n e l i g i b l e p r i o r i t y , and a n u l l machine s t a t e . I t i s a w a i t i n g a r e p l y from the i n v o k e r . ok = . S e t _ p r i o r i t y ( OF i d , TO p r i o r i t y ) s e t s the p r i o r i t y o f the s p e c i f i e d p r o c e s s . P r i o r i t i e s o f a p r o c e s s are used by the k e r n e l t o a l l o c a t e the p r o c e s s o r . P r i o r i t i e s range from z e r o , the h i g h e s t , t o a s m a l l p o s i t i v e c o n s t a n t ( c u r r e n t l y 1 6 ) , which i s the l o w e s t e l i g i b l e l e v e l . There i s a l s o an i n e l i g i b l e l e v e l , i n d i c a t e d by any l a r g e r 20 p r i o r i t y , from which processes are not dispatched. p r i o r i t y = .Get_priority( OF id ) returns the p r i o r i t y of the specified process. ok = .Set_status( OF i d , FROM status ) sets the status of the specified process from the vector specified by status. The status of a process indicates: what r e s t r i c t e d operations i t is capable of performing; what process management operations i t i s susceptible to; and, which devices i t can access. ok = .Get_status( OF i d , INTO status ) copies the status of the specified process to the vector spe c i f i e d by status. ok = .Set_map( OF i d , FROM map ) sets the machine-dependent address map of the spec i f i e d process from the vector at map i n the invoker's address space. The map specified i s checked by the kernel to ensure that i t does not overlap with the kernel or the device control r e g i s t e r s . If i t does, the map i s not changed, and an error indication i s returned. An error indication i s also returned i f the spec i f i e d process's status indicates that i t s map cannot be changed ( i . e . i t i s not susceptible to .Set_map). ok = .Get_map( OF i d , INTO map ) copies the address map of the specified process to the vector at map in the invoker's address space. ok = .Set_machine_state( OF i d , FROM state ) 21 s e t s the machine s t a t e o f the s p e c i f i e d p r o c e s s from the s p e c i f i e d v e c t o r . The k e r n e l ensures t h a t the new s t a t e cannot v i o l a t e the k e r n e l (e.g. f o r the TI990, the s t a t u s r e g i s t e r , ST, i n d i c a t e s n o n - p r i v i l e g e d mode and user map). I f i d i s i n v a l i d , or i f the p r o c e s s i s not s u s c e p t i b l e , an e r r o r i n d i c a t i o n i s r e t u r n e d . An e x c e p t i o n o c c u r s i f the s p e c i f i e d p r o c e s s i s not a w a i t i n g a r e p l y from the i n v o k e r . ok = . G e t _ m a c h i n e _ s t a t e ( OF i d , INTO s t a t e ) c o p i e s the machine s t a t e o f the s p e c i f i e d p r o c e s s t o the s p e c i f i e d v e c t o r . An e r r o r i n d i c a t i o n i s r e t u r n e d i f i d i s i n v a l i d . ok = . S e t _ v i o l a t i o n ( OF i d , TO v i o l a t i o n ) s e t s the v i o l a t i o n i n d i c a t i o n o f the s p e c i f i e d p r o c e s s . An e r r o r i n d i c a t i o n i s r e t u r n e d i f i d i s i n v a l i d . An e x c e p t i o n o c c u r s i f the s p e c i f i e d p r o c e s s i s not a w a i t i n g a r e p l y from the i n v o k e r . Note t h a t t h i s o p e r a t i o n does not cause an e x c e p t i o n t o o ccur f o r the s p e c i f i e d p r o c e s s , i t m e r e l y changes the v i o l a t i o n i n d i c a t i o n . v i o l a t i o n = . G e t _ v i o l a t i o n ( OF i d ) r e t u r n s the v i o l a t i o n i n d i c a t i o n o f the s p e c i f i e d p r o c e s s . An e r r o r i n d i c a t i o n i s r e t u r n e d i f i d i s i n v a l i d . ok = . D e s t r o y _ p r o c e s s ( i d ) d e s t r o y s the s p e c i f i e d p r o c e s s by: i n v a l i d a t i n g i t s i d , r e l e a s i n g i t s kernel-managed r e s o u r c e s , c l e a r i n g i t s message b u f f e r , and c a u s i n g an e x c e p t i o n f o r a l l p r o c e s s e s b l o c k e d on i t , by p u t t i n g them i n the pending a r r e s t l i s t (see 22 . N e x t _ v i o l a t o r b e l o w ) . An e r r o r i n d i c a t i o n i s r e t u r n e d i f the s p e c i f i e d p r o c e s s i s not d e s t r o y a b l e , as i n d i c a t e d by i t s s t a t u s . i d = . N e x t _ v i o l a t o r ( ) r e t u r n s the i d o f the next p r o c e s s i n the pending a r r e s t l i s t ( p r o c e s s e s t h a t had been b l o c k e d on a d e s t r o y e d p r o c e s s ) . The p r o c e s s s p e c i f i e d by i d i s caused t o a w a i t a r e p l y from the i n v o k e r . I f the pending a r r e s t l i s t i s empty, z e r o i s r e t u r n e d . W i t h o u t i n t e n d i n g t o l i m i t the f l e x i b i l i t y o f the system d e s i g n e r , i t i s e n v i s a g e d t h a t the c a p a b i l i t y f o r each r e s t r i c t e d o p e r a t i o n w i l l be l i m i t e d t o a few p r o c e s s e s . For example, the . C r e a t e _ p r o c e s s , . D e s t r o y _ p r o c e s s , and . N e x t _ v i o l a t o r o p e r a t i o n s would be used e x c l u s i v e l y by a "p r o c e s s p r o p r i e t o r " p r o c e s s , (and the r o o t p r o c e s s ) . A l l o t h e r p r o c e s s e s would send r e q u e s t s t o the p r o c e s s p r o p r i e t o r t o c r e a t e or d e s t r o y p r o c e s s e s . .Set_map would be used by a "memory manager" p r o c e s s , and . S e t _ p r i o r i t y by a " s c h e d u l e r " p r o c e s s . . S e t _ s t a t u s i s such a p o w e r f u l o p e r a t i o n , t h a t i t s use s h o u l d be r e s t r i c t e d t o the r o o t p r o c e s s w h i l e i t i s s e t t i n g up the system p r o c e s s e s . . S e t _ m a c h i n e _ s t a t e and . S e t _ v i o l a t i o n a re c o n s i d e r a b l y l e s s p o w e r f u l o p e r a t i o n s , as the a f f e c t e d p r o c e s s must be a w a i t i n g a r e p l y from the i n v o k e r . Thus more system p r o c e s s e s might use them. For example, p r o p r i e t o r p r o c e s s e s c o u l d a r r e s t a f a u l t y r e q u e s t o r by s e t t i n g i t s v i o l a t i o n i n d i c a t i o n , and f o r w a r d i n g i t t o the e x c e p t i o n h a n d l e r . The query f u n c t i o n s , such as . G e t _ m a c h i n e _ s t a t e , are even l e s s c r i t i c a l , as they do not a f f e c t the c o r r e c t o p e r a t i o n o f 23 p r o c e s s e s . 2.3 D e v i c e M a n i p u l a t i o n The d e v i c e s a b s t r a c t e d by the k e r n e l are c l a s s i f i e d i n t o t h r e e broad t y p e s : t i m i n g , c h a r a c t e r , and b l o c k d e v i c e s . R e a l - t i m e c l o c k s and t i m e r s are examples o f t i m i n g d e v i c e s . T e r m i n a l s are c h a r a c t e r d e v i c e s and d i s k s are b l o c k d e v i c e s . In a d d i t i o n t o the s p e c i f i c o p e r a t i o n s f o r these t y p e s o f d e v i c e s , t h e r e are g e n e r a l purpose d e v i c e o p e r a t i o n s . Each d e v i c e has a c a p a b i l i t y a s s o c i a t e d w i t h i t which a p r o c e s s must po s s e s s t o use the o p e r a t i o n s t o m a n i p u l a t e the d e v i c e . The p a r t i c u l a r c h a r a c t e r i s t i c s and c o n f i g u r a t i o n o f d e v i c e s i n the system are m a i n t a i n e d i n a d e v i c e d e s c r i p t o r t a b l e i n the k e r n e l ' s address space. G e n e r a l Purpose O p e r a t i o n s Most d e v i c e s have c o n t r o l r e g i s t e r s . Most have the a b i l i t y t o i n t e r r u p t the p r o c e s s o r t o s i g n a l an e v e n t . The k e r n e l p r o v i d e s g e n e r a l purpose o p e r a t i o n s f o r r e a d i n g and w r i t i n g d e v i c e r e g i s t e r s , and f o r s y n c h r o n i z i n g w i t h d e v i c e e v e n t s . These l o w - l e v e l o p e r a t i o n s do not determine the a c t i o n s o f the d e v i c e , s i m p l y the e f f e c t upon i t s r e g i s t e r s . These o p e r a t i o n s cannot be used t o c o n t r o l d e v i c e s t h a t can a f f e c t the k e r n e l , ( i . e . unmapped d i r e c t memory a c c e s s , DMA, d e v i c e s ) . count = . A w a i t _ e v e n t ( FROM d e v i c e ) r e t u r n s a count o f the number o f times the d e v i c e has i n t e r r u p t e d s i n c e i t was l a s t a w a i t e d . I f the d e v i c e has not 24 i n t e r r u p t e d y e t , the i n v o k e r b l o c k s u n t i l i t does and then r e t u r n s z e r o t o i n d i c a t e t h a t no i n t e r r u p t s were m i s s e d . The i n v o k e r i s l o c k e d i n memory ( i . e . i t s map i s not s e t t a b l e ) w h i l e i t i s b l o c k e d . The i n v o k e r i s a r r e s t e d i f a p r o c e s s i s a l r e a d y a w a i t i n g the d e v i c e . . W r i t e _ b i t s ( n, THRU m, OF d e v i c e , WITH v a l u e ) pu t s the m-n+1 low-order b i t s o f v a l u e i n t o the n-th through m-th, b i t s o f the d e v i c e ' s c o n t r o l r e g i s t e r . v a l u e = . R e a d _ b i t s ( n, THRU m, OF d e v i c e ) r e t u r n s the n-th through m-th b i t s o f the d e v i c e ' s c o n t r o l r e g i s t e r i n the low-order b i t s o f v a l u e . Timing Devices The k e r n e l m a i n t a i n s a r e a l - t i m e c l o c k i n a t h r e e word time v e c t o r . The f i r s t word i n d i c a t e s the number o f c l i c k s s i n c e the l a s t second w h i l e the o t h e r two words i n d i c a t e the e l a p s e d time i n seconds. The s i z e o f a c l i c k i s a machine dependent parameter e q u i v a l e n t t o the r e s o l u t i o n p o s s i b l e w i t h the p a r t i c u l a r hardware c l o c k , (1/120 second f o r the TI990/10). . W r i t e _ r e a l t i m e ( t ime_vec ) c o p i e s the t h r e e word v e c t o r a t time_vec i n the i n v o k e r ' s address space t o the k e r n e l ' s time v e c t o r , t h u s s e t t i n g the c l o c k . I f the number o f c l i c k s s p e c i f i e d i s g r e a t e r than or e q u a l t o the number o f c l i c k s per second minus one, the next c l i c k w i l l i ncrement the seconds by one and s e t the c l i c k s t o z e r o . 25 . R e a d _ r e a l t i m e ( time_vec ) c o p i e s the k e r n e l ' s time v e c t o r t o time_vec i n the i n v o k e r ' s address space. . W r i t e _ t i m e r ( c l i c k s ) s e t s a k e r n e l - m a i n t a i n e d t i m e r t o c l i c k s which may be r e s e t w h i l e r u n n i n g . The t i m e r i n t e r r u p t s a f t e r the s p e c i f i e d number o f c l i c k s . A p r o c e s s uses the g e n e r a l purpose .Await_event o p e r a t i o n d e s c r i b e d above t o w a i t f o r the t i m e r t o e x p i r e . C h a r a c t e r D e v i c e s The k e r n e l a b s t r a c t s c h a r a c t e r d e v i c e s , such as t e r m i n a l s , by b u f f e r i n g the c h a r a c t e r s exchanged w i t h t h e s e d e v i c e s . These o p e r a t i o n s b l o c k on a p p r o p r i a t e b u f f e r c o n d i t i o n s . . W r i t e _ c h a r a c t e r ( c, TO d e v i c e ) pu t s the c h a r a c t e r , c, i n t o the d e v i c e ' s b u f f e r . I f the b u f f e r i s f u l l , the i n v o k e r b l o c k s u n t i l i t i s empty. The i n v o k e r i s l o c k e d i n memory w h i l e i t i s b l o c k e d . I f a p r o c e s s i s a l r e a d y b l o c k e d because the d e v i c e ' s b u f f e r was f u l l , the i n v o k e r i s a r r e s t e d . c = . R e a d _ c h a r a c t e r ( FROM d e v i c e ) r e t u r n s the nex t c h a r a c t e r from the d e v i c e ' s b u f f e r . I f the b u f f e r i s empty, the i n v o k e r b l o c k s u n t i l a c h a r a c t e r a r r i v e s . The h i g h o r d e r byte o f the r e t u r n e d v a l u e i s a count o f the number o f c h a r a c t e r s missed s i n c e the l a s t c h a r a c t e r was r e t u r n e d . The i n v o k e r i s l o c k e d i n memory w h i l e i t i s b l o c k e d . I f a p r o c e s s i s a l r e a d y b l o c k e d because the d e v i c e ' s b u f f e r i s empty, the i n v o k e r i s a r r e s t e d . 26 Other f e a t u r e s o f c h a r a c t e r d e v i c e s , such as baud r a t e and p a r i t y s e l e c t i o n a re not e x p l i c i t l y p r o v i d e d f o r . The g e n e r a l purpose o p e r a t i o n s d e s c r i b e d above a r e used t o c o n t r o l the d e v i c e ' s s p e c i a l f e a t u r e s . B l o c k D e v i c e s B l o c k d e v i c e s a re not a b s t r a c t e d by the k e r n e l , e x c e p t f o r r e s t r i c t i n g t h e i r use, and i n t e r p r e t i n g a l l a d d r e s s e s r e l a t i v e t o a p r o c e s s . Thus the a c t i o n s the d e v i c e s t a k e as a r e s u l t o f these o p e r a t i o n s i s e n t i r e l y d e v i c e - d e p e n d e n t . ok = . W r i t e _ r e g s ( OF d e v i c e , FROM r e g s , WITH i d ) w r i t e s the d e v i c e ' s c o n t r o l r e g i s t e r s w i t h the c o n t e n t s o f the v e c t o r regs i n the i n v o k e r ' s address space. A l l a d d r e s s e s s p e c i f i e d by the r e g i s t e r s a re r e l a t i v e t o the s p e c i f i e d p r o c e s s . The k e r n e l t r a n s l a t e s them i f n e c e s s a r y . The s p e c i f i e d p r o c e s s i s l o c k e d i n memory w h i l e DMA i s i n p r o g r e s s w i t h i t . i d = .Read_regs( OF d e v i c e , INTO regs ) c o p i e s the c o n t e n t s o f the d e v i c e ' s r e g i s t e r s i n t o the v e c t o r a t regs i n the i n v o k e r ' s address space. I t a l s o r e t u r n s the i d s p e c i f i e d by the l a s t . W r i t e _ r e g s o f t h i s d e v i c e . P r o c e s s e s use the g e n e r a l purpose .Await_event o p e r a t i o n , d e s c r i b e d above, t o s y n c h r o n i z e w i t h b l o c k d e v i c e s . 2 . 4 Summary The e x e c u t i o n environment implemented by the k e r n e l extends and a b s t r a c t s the environment p r o v i d e d by the hardware. 27 Processes and devices are the basic kernel objects. The set of operations allow for interprocess communication, process management, and device manipulation. Processes are execution instances of programs that d e t e r m i n i s t i c a l l y execute a subset of the host processor's instruction set plus the kernel operations. They are referred to by unique id's, and their attributes include: machine states, maps, p r i o r i t i e s , statuses ( c a p a b i l i t i e s and s u s c e p t i b i l i t i e s ) , and v i o l a t i o n indications. Devices are c l a s s i f i e d into three types: timing, character, and block devices. Interprocess communication i s v i a small synchronous messages, augmented with a data move operation. Processes read, write, send, await, reply, and forward message buffers. Senders await r e p l i e s . Authorized processes manage processes. They create, destroy, and manipulate the attributes of processes. Processes must possess the c a p a b i l i t y ' for a process management operation to execute i t . Access to devices is provided by general purpose operations as well as operations for each type of device. Only processes with the c a p a b i l i t y for a device manipulate i t . Generally, the operations only specify the ef f e c t upon the device's control r e g i s t e r s , not the action of the device. The kernel objects and operations provided allow the structuring of the system as a small self-contained v e r i f i a b l e kernel plus a set of system processes which can be independently 28 v e r i f i e d . E l a b o r a t i o n on t h i s c l a i m and the r a t i o n a l e behind t h i s d e sign are provided i n the next chapter. 29 Chapter 3 J u s t i f i c a t i o n of the Environment This chapter presents and discusses the design c r i t e r i a that were used, and then j u s t i f i e s the design of the environment in terms of them. 3.1 Design C r i t e r i a The objective of this work i s to explore techniques for building v e r i f i a b l e operating systems. Cheriton [1979b] has suggested that the following c h a r a c t e r i s t i c s make operating systems d i f f i c u l t to v e r i f y : 1. large siz e , 2. complexity, 3. concurrent execution, 4. dynamic behavior, and 5. asynchronous events. The kernel/system-process structure i s d i r e c t l y aimed at reducing the d i f f i c u l t i e s r esulting from these c h a r a c t e r i s t i c s . Two d i s t i n c t design a c t i v i t i e s are associated with the kernel component of the system: the design of the environment i t provides; and the design of i t s implementation. Different c r i t e r i a are required for each a c t i v i t y , although they are related. The environment must be suitable for supporting a set of v e r i f i a b l e system processes, while the implementation must i t s e l f be v e r i f i a b l e . The following c r i t e r i a guided the design of the environment the kernel provides. 30 1. The k e r n e l s h o u l d a l l o w t h e systems i t s u p p o r t s t o be m o d u l a r i z e d w i t h an a c y c l i c dependency graph. M o d u l a r i z a t i o n i s a p o w e r f u l t o o l f o r a c h i e v i n g v e r i f i a b i l i t y . I f the modules e x h i b i t an a c y c l i c dependency g r a p h , the v e r i f i a b i l i t y o f the system i s f u r t h e r enhanced, because the c o r r e c t n e s s o f each module can be c o n s i d e r e d s e p a r a t e l y . A d i r e c t consequence o f t h i s c r i t e r i o n i s t h a t the k e r n e l must be independent o f a l l p r o c e s s e s . I t must r e s i d e i n a s e p a r a t e i n v i o l a t e address space. I t must not even r e l y on the e x i s t e n c e o f any p r o c e s s e s (e.g. f o r e x c e p t i o n h a n d l i n g ) . 2. The k e r n e l s h o u l d not p r o v i d e f a c i l i t i e s t h a t can be p r o v i d e d e f f i c i e n t l y by a p r o c e s s . In t h i s way, the s i z e o f the k e r n e l i s kept as s m a l l as r e a s o n a b l e . However, t h i s c r i t e r i o n must not be t a k e n t o the extreme. O f t e n , f e a t u r e s can be p r o v i d e d by the k e r n e l w i t h d r a m a t i c i n c r e a s e s i n e f f i c i e n c y and o n l y t r i v i a l i n c r e a s e s i n c o m p l e x i t y o f the k e r n e l . An example o f t h i s i s c o u n t i n g c l o c k i n t e r r u p t s . 3. The k e r n e l o p e r a t i o n s s h o u l d have s i m p l e , w e l l - d e f i n e d s e m a n t i c s . T h i s i s an o b v i o u s p o i n t , but i t i s v e r y i m p o r t a n t both from the p o i n t o f view o f d e v e l o p i n g the system p r o c e s s e s c o r r e c t l y and v e r i f y i n g the k e r n e l . S p e c i a l c ases are o f t e n the s o u r c e o f program f a i l u r e s . 4. I t must be p o s s i b l e t o implement the environment w i t h i n the i m p l e m e n t a t i o n c r i t e r i a . T h i s c r i t e r i o n r e f l e c t s the r e l a t i o n s h i p between the d e s i g n o f 31 the environment and i t s implementation. I t has often been necessary to consider how the environment could be implemented in order to allow i t s sele c t i o n . The following c r i t e r i a guided the design of the implementation of the kernel. 1. The kernel operations should be i n d i v i s i b l e . This r e s t r i c t i o n s i m p l i f i e s the demonstration that the i n t e g r i t y of the kernel data structures i s maintained despite the occurrence of an interrupt. In fact i t s i m p l i f i e s the kernel in general because i t implies that a l l kernel operations execute sequentially and d e t e r m i n i s t i c a l l y . Thus, sequential program proving techniques can be used. A consequence of this c r i t e r i o n i s that the interrupts must be t o t a l l y disabled during kernel operations. 2. The maximum time for the kernel to respond to external events should be small and bounded by a constant. This i s the real-time constraint. I t i s necessary because a general purpose operating system must be able to respond to real world events such as synchronous communication l i n e interrupts. Also i t i s desirable that the kernel be able to support real-time applications such as process c o n t r o l . A consequence of this c r i t e r i o n i s that the time for which the interrupts are disabled must be bounded by a constant. The previous c r i t e r i o n required the interrupts to be f u l l y disabled during kernel operations. Combining these implies that the maximum execution time for a kernel operation must be bounded by a constant. 32 3. The d e s i g n s h o u l d be machine independent. I t i s not the o b j e c t i v e o f t h i s work t o d e v e l o p s o f t w a r e f o r a p a r t i c u l a r machine, but r a t h e r t o i n v e s t i g a t e s t r u c t u r e s t h a t are g e n e r a l l y u s e f u l f o r a l a r g e c l a s s o f machines. Thus, the d e s i g n o f the environment and the i m p l e m e n t a t i o n s h o u l d not be governed by s p e c i f i c f e a t u r e s o f any one machine. However, a broad c l a s s o f the machines o f i n t e r e s t p r o v i d e s i m i l a r f e a t u r e s , and these can and s h o u l d be t a k e n i n t o c o n s i d e r a t i o n . 4 . The i m p l e m e n t a t i o n s h o u l d be e f f i c i e n t . The system s h o u l d be e f f i c i e n t i n o r d e r t o be p r a c t i c a l , but d e c r e a s e s i n e f f i c i e n c y t o improve v e r i f i a b i l i t y a re i n c u r r e d . Where e f f i c i e n c y i s o f c o n c e r n , i t i s u s u a l l y time and not space e f f i c i e n c y , because o f the d e s i r e t o p r o v i d e r e a l - t i m e r e s p o n s e . In a d d i t i o n t o the p r e c e d i n g c r i t e r i a , the i m p l e m e n t a t i o n s h o u l d adhere t o good programming p r a c t i c e s . I n p a r t i c u l a r , i t s h o u l d use s t r u c t u r e d c o n t r o l c o n s t r u c t s , use m e a n i n g f u l i d e n t i f i e r s , and be w e l l commented and documented. To t h i s end a h i g h - l e v e l language i s used almost e x c l u s i v e l y . These c r i t e r i a enhance the v e r i f i a b i l i t y o f both the system and the k e r n e l , by r e d u c i n g the s i z e o f the v e r i f i c a t i o n u n i t s , e n s u r i n g t h a t each u n i t e x e c u t e s s e q u e n t i a l l y and d e t e r m i n i s t i c a l l y , and s i m p l i f y i n g the s e m a n t i c s o f the u n i t s . Systems a d h e r i n g t o these c r i t e r i a w i l l be u s e a b l e , c o n v e n i e n t , and p o r t a b l e . 33 3.2 I n t e r p r o c e s s Communication The k e r n e l ' s synchronous f i x e d - s i z e messages e n a b l e p r o c e s s e s t o s y n c h r o n i z e and pass c o n t r o l i n f o r m a t i o n w i t h o u t becoming m u t u a l l y dependent. L a r g e r and v a r i a b l e amounts o f d a t a are handled w i t h the d a t a move o p e r a t i o n . F a v o r a b l e e x p e r i e n c e w i t h Thoth's s i m i l a r p r i m i t i v e s i n d i c a t e s t h a t t h i s scheme i s r e a s o n a b l e . 3.2.1 Messages The send, a w a i t , and r e p l y message p r i m i t i v e s are s u f f i c i e n t f o r p r o c e s s s y n c h r o n i z a t i o n . C h e r i t o n [1979a] has shown they are a t l e a s t as p o w e r f u l as D i j k s t r a ' s g e n e r a l semaphores [1968a]. Each p r o c e s s has o n l y one message b u f f e r so the k e r n e l cannot d e a d l o c k on message b u f f e r space. I f a dynamic a l l o c a t i o n scheme i s used, the k e r n e l c o u l d run out o f b u f f e r s and be unable t o s u p p o r t any f u r t h e r messages. T h i s problem i s a v o i d e d by u s i n g a s t a t i c scheme, o f which one message per p r o c e s s i s the s i m p l e s t . P r o c e s s e s can o n l y use one b u f f e r anyway, because senders w a i t f o r r e p l i e s , and thus have at most one message i n t r a n s i t a t a t i m e . Messages are f i x e d - s i z e because: they can be implemented e a s i l y ; t hey can be s t a t i c a l l y a l l o c a t e d t o a v o i d the d e a d l o c k problem; and, they can e a s i l y s i m u l a t e v a r i a b l e - s i z e messages ( i n c o m b i n a t i o n w i t h .Move). S t a t i c a l l y a l l o c a t e d v a r i a b l e - s i z e messages reduce t o f i x e d - s i z e messages o f the l a r g e s t s i z e . The c o s t o f exchanging messages does not v a r y w i t h t h e i r s i z e , 34 because o n l y p o i n t e r s a re exchanged. V a r i a b l e - s i z e messages would p e r m i t a c c e s s i n g v a r i a b l e amounts o f the message b u f f e r . T h i s can be e a s i l y p r o v i d e d w i t h f i x e d - s i z e messages as w e l l , but i t s u s e f u l n e s s i s d o u b t f u l u n l e s s messages are l a r g e . Messages are s m a l l so t h a t the c o s t per p r o c e s s i s s m a l l and many p r o c e s s e s can be p r o v i d e d . Messages are i n t e n d e d f o r c o n t r o l i n f o r m a t i o n and s m a l l amounts o f d a t a . The .Move o p e r a t i o n i s f o r l a r g e r or v a r i a b l e amounts o f d a t a . The c u r r e n t 8-word s i z e was s e l e c t e d because i t worked w e l l f o r Thoth. Most messages do not use a l l 8 words, so a r e d u c t i o n might be d e s i r a b l e , but b u f f e r space has not been s c a r c e enough t o m o t i v a t e t h i s . R e p l i e s a l l o w the system t o be s t r u c t u r e d w i t h an a c y c l i c dependency graph. The send (and a w a i t r e p l y ) , a w a i t (from any p r o c e s s ) , and r e p l y sequence a l l o w s a p r o p r i e t o r (or manager) p r o c e s s t o a c c e p t and s e r v i c e r e q u e s t s w i t h o u t depending upon i t s r e q u e s t o r s . A r e p l y i n g p r o c e s s does not b l o c k because the sender i s a w a i t i n g the r e p l y ( u n l e s s i t has been d e s t r o y e d ) . Thus, a p r o p r i e t o r can r e t u r n i n f o r m a t i o n t o , and s y n c h r o n i z e w i t h , a r e q u e s t o r w i t h o u t depending on i t . The n o n - b l o c k i n g r e c e i v e a l l o w s p r o c e s s e s t o be independent w i t h r e s p e c t t o t i m i n g c r i t e r i a . I f a p r o c e s s must respond w i t h i n a s p e c i f i e d t i m e , i t cannot a w a i t a message w i t h o u t depending on some p r o c e s s t o send t o i t w i t h i n t h a t t i m e . For example, a d e v i c e p r o p r i e t o r t h a t must s e r v i c e p e r i o d i c i n t e r r u p t s , as w e l l as a w a i t and s e r v i c e r e q u e s t s , has t h i s p roblem. I f i t b l o c k s a w a i t i n g a r e q u e s t , i t i s depending on 35 some p r o c e s s t o send t o i t b e f o r e the n e x t i n t e r r u p t . I f i t r e c e i v e s w i t h o u t b l o c k i n g , i t can s e r v i c e the r e q u e s t , i f any, and o n l y b l o c k f o r the i n t e r r u p t . I t need not depend on any r e q u e s t o r s . There are o t h e r s o l u t i o n s t o t h i s problem. A t i m e r p r o c e s s can send back w i t h i n a s p e c i f i e d t i m e . T h i s mechanism works w e l l f o r slow r a t e s , but r e q u i r e s an e x t r a p r o c e s s and two more p r o c e s s s w i t c h e s per i n t e r r u p t than the n o n - b l o c k i n g r e c e i v e . Or, the n o n - b l o c k i n g and b l o c k i n g r e c e i v e s c o u l d be g e n e r a l i z e d i n t o a r e c e i v e w i t h a v a r i a b l e t i m e o u t , from z e r o t o i n f i n i t y . But i t i s not c l e a r how t o implement t h i s w i t h o u t s e v e r e l y c o m p l i c a t i n g the k e r n e l . F i n a l l y , s t r i c t t i m i n g r e q u i r e m e n t s c o u l d be met by the k e r n e l i t s e l f , which has i n f a c t , been done f o r t i m i n g and c h a r a c t e r d e v i c e s . Forward was i n c l u d e d because i t i s c o n v e n i e n t t o r e d i r e c t messages w i t h o u t becoming dependent upon and c o m p l i c a t i n g the new r e c e i v e r . T h i s a b i l i t y a l s o p e r m i t s a p r o c e s s t o r e d i r e c t a message t o i t s e l f , thus i g n o r i n g a r e q u e s t and moving i t t o the end o f i t s incoming message queue. The s p e c i f i c r e c e i v e o p e r a t i o n , which i s u s e f u l when p r o c e s s e s are c l o s e l y c o o p e r a t i n g , c o u l d be g e n e r a l i z e d t o r e c e i v e from s e t s o f p r o c e s s e s . W ith t h i s o p e r a t i o n , a p r o c e s s c o u l d r e c e i v e from o n l y the p r o c e s s e s i t was c o o p e r a t i n g w i t h , w h i l e i g n o r i n g o t h e r p r o c e s s e s . A l t h o u g h t h i s o p e r a t i o n would be u s e f u l , i t i s not i n c l u d e d because i t i s not n e c e s s a r y . I t can be s i m u l a t e d u s i n g f o r w a r d and r e c e i v e u n s p e c i f i c . A l s o , i t i s not c l e a r how t o implement r e c e i v i n g from a r b i t r a r y s u b s e t s o f 36 p r o c e s s e s i n c o n s t a n t t i m e . Reading and w r i t i n g the message b u f f e r w i t h o p e r a t i o n s d i s t i n c t from send, r e c e i v e and r e p l y a l l o w the l a t t e r o p e r a t i o n s t o be i n d i v i s i b l e . P r e v i o u s v e r s i o n s o f these o p e r a t i o n s b l o c k e d b e f o r e moving the message b u f f e r , which v i o l a t e s the i n d i v i s i b i l i t y c r i t e r i o n . T h i s argument a p p l i e s o n l y t o r e a d i n g the b u f f e r . W r i t i n g need o n l y o c c u r b e f o r e sends and r e p l i e s , t h u s i t c o u l d be i n t e g r a t e d w i t h them. The s e p a r a t e w r i t e b u f f e r o p e r a t i o n was i n c l u d e d f o r the sake o f symmetry and because i t reduces the average time t o respond t o e x t e r n a l e v e n t s . The i n d i v i s i b i l i t y c r i t e r i o n a l s o i m p l i e s t h a t v a l u e s cannot be r e t u r n e d from the b l o c k i n g send and a w a i t o p e r a t i o n s . T h i s i s because the r e t u r n v a l u e i s not known when the i n v o k e r b l o c k s and the u n b l o c k e r cannot r e t u r n the v a l u e because the r e c i p i e n t (the sender or a w a i t e r ) might not be i n memory a t the t i m e . Thus, the r e t u r n would have t o o c c u r a f t e r the b l o c k i n g p r o c e s s had been d i s p a t c h e d , making the o p e r a t i o n d i v i s i b l e . P r o c e s s e s t h a t use the communication p r i m i t i v e s i n c o r r e c t l y are a r r e s t e d f o r t h r e e r e a s o n s . F i r s t , i t e l i m i n a t e s the need f o r the i n v o k e r t o check f o r e r r o r i n d i c a t i o n s . Because the k e r n e l does th e s e checks t o p r o t e c t i t s e l f , i t can e a s i l y a r r e s t o f f e n d i n g p r o c e s s e s . Second, i t ensures t h a t f a u l t y p r o c e s s e s are d e a l t w i t h . The i n v o k e r may not check f o r e r r o r i n d i c a t i o n s , e i t h e r out o f n e g l e c t , or because i t i s out o f c o n t r o l . T h i r d , a r r e s t i n g these p r o c e s s e s g i v e s the system d e s i g n e r more f l e x i b i l i t y , not l e s s . A r r e s t e d p r o c e s s e s are e a s i l y r e s t a r t e d 3 7 by an e x c e p t i o n h a n d l i n g p r o c e s s . But i f the k e r n e l i g n o r e s t h e s e e r r o r s , the system has no a l t e r n a t i v e s . The k e r n e l does not a r r e s t p r o c e s s e s f o r e r r o r s t h a t can a r i s e i n normal o p e r a t i o n o f the p r o c e s s . For example, r e p l y i n g t o a r e q u e s t o r t h a t has been d e s t r o y e d does not cause an e x c e p t i o n . The same i s t r u e f o r both the forwardee and the i n t e n d e d r e c e i v e r s p e c i f i e d i n a f o r w a r d o p e r a t i o n . P r o c e s s e s i n v o k i n g the message o p e r a t i o n s are a r r e s t e d under the f o l l o w i n g c o n d i t i o n s : 1. s e n d i n g t o , or a w a i t i n g from a p r o c e s s w i t h an i n v a l i d i d , 2. f o r w a r d i n g or r e p l y i n g t o an e x i s t e n t p r o c e s s not a w a i t i n g r e p l y from the i n v o k e r , or 3 . s p e c i f y i n g a v e c t o r t o read or w r i t e t h a t i s not i n the i n v o k e r ' s address space. The l a t t e r two cases are c l e a r l y i n d i c a t i v e o f f a u l t y s i t u a t i o n s , but the f i r s t i s c o n t r o v e r s i a l . B l o c k i n g on a n o n - e x i s t e n t p r o c e s s i s c o n s i d e r e d an e r r o r because the i n v o k e r i s a t t e m p t i n g t o become dependent upon a n o n - e x i s t e n t p r o c e s s . The i n v o k e r most l i k e l y can not f u n c t i o n c o r r e c t l y w i t h o u t i t . One e x c e p t i o n t o t h i s i s a " v u l t u r e " p r o c e s s t h a t a w a i t s a message from a p r o c e s s t h a t does not send t o i t , s o l e l y t o m o n i t o r i t s d e s t r u c t i o n . T h i s c o n s t r u c t , a l t h o u g h e x p e n s i v e , c o u l d be u s e f u l f o r r e s o u r c e r e c l a m a t i o n . None the l e s s , the a r r e s t a l t e r n a t i v e was s e l e c t e d because i t i s more f l e x i b l e . A l s o o n l y minor changes t o the k e r n e l and the p r o c e s s e s would be r e q u i r e d t o r e v e r t t o the n o n - a r r e s t a l t e r n a t i v e . In summary, the message-passing scheme implemented by the 38 kernel allows processes to synchronize and communicate with each other without becoming mutually dependent. It i s easy to understand, convenient to use, simple and e f f i c i e n t to implement, and cannot deadlock. 3.2.2 Other Communication Mechanisms The data move operation provides e f f i c i e n t communication of large amounts of data. It also allows v a r i a b l e - s i z e data to be handled naturally, rather than packaged into messages. Its use i s r e s t r i c t e d to transfers of data between processes awaiting reply from the invoker so other processes do not depend on the mover; i t s requestors already do. Also, there are no synchronization problems, because at most one of the processes involved, the invoker, can execute. F u l l read/write access to the requestor's address space may seem excessive, but i s convenient for debuggers, exception handlers, and other monitoring processes. This f u n c t i o n a l i t y could be provided by a system process using .Set_map to give i t s e l f access to the data to be moved. The kernel provides .Move though for several reasons: 1. i t i s easier, more elegant, and faster for the kernel to do i t , 2. i t prevents that part of the system from becoming a bottleneck, and 3. i t gives low-level processes this f a c i l i t y . To prevent a mover from being arrested when i t attempts to move data to or from a swapped process, the kernel should ensure that the processes are in memory, returning an error indication i f 39 they a re n o t . A minor problem w i t h the s e m a n t i c s o f t h i s o p e r a t i o n , i s t h a t the b e s t the k e r n e l can do i s t o check t h a t the p r o c e s s e s have e l i g i b l e p r i o r i t i e s . They c o u l d , however, be swapped and have e l i g i b l e p r i o r i t i e s but t h i s i s u n l i k e l y . Words r a t h e r than b y t e s are moved, because t h i s i s s i m p l e r . I f i t i s d e s i r e d t o move an odd number o f b y t e s , t h i s can be s i m u l a t e d by the i n v o k i n g p r o c e s s , s a v i n g k e r n e l c o m p l e x i t y . The maximum number o f words t h a t can be moved i s l i m i t e d so t h a t the maximum d i s a b l e time i s bounded. P i p e s , f i r s t i n t r o d u c e d by UNIX, are a c o n v e n i e n t mechanism f o r i n t e r p r o c e s s communication and s y n c h r o n i z a t i o n . They can be thought o f as one-byte b u f f e r e d messages, or as shared temporary f i l e s w i t h the reader s y n c h r o n i z e d t o be behind the w r i t e r . P i p e s can be s i m u l a t e d w i t h the k e r n e l ' s message scheme. Because they a re thought o f as f i l e s (and thus p a r t o f the I/O s y s t e m ) , they are l o g i c a l l y a t a h i g h e r l e v e l than the k e r n e l . For these r e a s o n s , p i p e s were not i n c l u d e d . A p o t e n t i a l l y a t t r a c t i v e a l t e r n a t i v e t o s m a l l , f i x e d - s i z e messages i s t o use segments o f a p r o c e s s ' s a d dress space r a t h e r than message b u f f e r s i n the k e r n e l ' s a d dress space. T h i s i s i m p r a c t i c a l w i t h most mapping hardware, and a b s t r a c t i n g the mapping hardware more than i t a l r e a d y i s would c o m p l i c a t e the k e r n e l . S h a r i n g memory segments i s another t e c h n i q u e f o r i n t e r p r o c e s s communication. As the k e r n e l does not de t e r m i n e memory a l l o c a t i o n s t r a t e g y (except f o r p r o t e c t i n g the k e r n e l ' s memory), i t n e i t h e r p r o v i d e s nor d i s a l l o w s memory s h a r i n g . The system may 40 implement this i f desired. Processes that share segments they can modify become interdependent for their correct operation. In summary, of the non-message communication mechanisms considered, only a data move operation was included. It e f f i c i e n t l y a l l e v i a t e s the inconvenience of handling large or variable amounts of data with small fixed-size messages. The other schemes considered, pipes and shared memory, were considered to high-level to include in the kernel. 3 . 3 Process Management Process management involves: 1. i n i t i a l i z i n g the system processes, 2. creating and destroying processes, 3. managing main memory, 4. scheduling the processor, 5. c o n t r o l l i n g protection and security, and 6. handling exceptional conditions. It i s desirable for system processes to implement as much of these management functions as i s reasonable so that the kernel i s small. Processes cannot d i r e c t l y access the kernel to implement these features without the kernel depending on theses processes. Providing process management operations rather than a c c e s s i b i l i t y , allows the kernel to be independent of the system processes, even though they do much of the process management. Some of these operations are so powerful they can be used to prevent other processes from working c o r r e c t l y . Thus their use must be r e s t r i c t e d . A process must have the c a p a b i l i t y for one 41 of these operations (indicated by i t s status) to be authorized to execute i t . Unauthorized processes invoking these operations are arrested, and thus prevented from executing unless the exception handling process restarts them. This section argues that these operations are simple and e f f i c i e n t , but s t i l l allow f l e x i b l e system design. 3.3.1 System I n i t i a l i z a t i o n The kernel f i r s t i n i t i a l i z e s i t s own data structures, and then creates one process to i n i t i a l i z e the system. Giving the r e s p o n s i b i l i t y to i n i t i a l i z e the rest of the system to a process eliminates the need to change the kernel whenever the process structure of the system changes. Thus the kernel i s independent of the system process structure. One "root process" i s also easier to i n i t i a l i z e than multiple system processes. A table driven root process has been written that enables a process to be added to (or deleted from) the i n i t i a l i z a t i o n procedure simply by changing a table and recompiling this small process. Other i n i t i a l i z a t i o n schemes are also possible. One disadvantage of the root process scheme i s that the •Set_status operation would not be necessary i f the kernel created a l l processes that had special authorization. However, because .Set_status i s t r i v i a l to implement, the root process i n i t i a l i z a t i o n scheme i s preferable. 42 3.3.2 Process Creation •Create_process allocates and i n i t i a l i z e s the kernel data structures required for a new process. This operation i s r e s t r i c t e d so that a system process can: prevent excessive consumption of process descriptors, which can c r i p p l e a system; and, ensure that processes are destroyed when their usefulness has ended. An interesting c o r o l l a r y of this is that the kernel is not required to maintain a process descendant hierarchy. These hierarchies, indicating the creator and descendants of every process, are usually found in systems with unrestricted create operations. Their primary function seems to be to f a c i l i t a t e the destruction of a process's descendants when i t i s destroyed. The attributes of a new process are always i n i t i a l i z e d to the same values, so that separate processes can manage these attributes without depending upon a l l creators. I f , for example, a creator could determine a r b i t r a r y i n i t i a l p r i o r i t i e s , i t could disrupt the processor a l l o c a t i o n strategy implemented by a scheduler process. A new process i s created awaiting a reply from i t s creator, so that i t may be i n i t i a l i z e d and passed arguments. Thus the kernel need not provide this usually machine-dependent feature. A new process may be forwarded by i t s creator to a t h i r d process (such as the requestor of the creation) to i n i t i a l i z e . This could be desirable to eliminate a bottleneck i f only one process has the c a p a b i l i t y for .Create_process. 43 3.3.3 Processor Scheduling The m u l t i - l e v e l p r i o r i t y and dispatching strategy used by the kernel i s both capable of responding to real-time events and f l e x i b l e enough for time-sharing applications. This i s possible because there are two levels of dispatching. A micro dispatching strategy, implemented e n t i r e l y by the kernel, allows dispatching decisions to be made quickly without the intervention of a process. And, the .Set_priority operation allows a scheduler process to implement an a r b i t r a r y macro dispatching strategy. The kernel takes advantage of the hardware interrupt masking mechanism so that the time to dispatch the highest p r i o r i t y process in response to an interrupt only depends upon the kernel and i s bounded by a constant. The process with the most stringent response requirement can be assigned the highest p r i o r i t y and thus have a guaranteed maximum response time. As long as this process executes in constant time, other processes can have guaranteed response times as well. If interrupts were not maskable, the response times would depend on a l l the interrupt rates. The a b i l i t y to dynamically change process p r i o r i t i e s with .Se t _ p r i o r i t y gives a scheduler process the power to implement almost any gross (macro) dispatching strategy desired. For example, the processor may be equitably shared among a number of processes by p e r i o d i c a l l y cycling their p r i o r i t i e s , each process getting equal time at each l e v e l . The number of p r i o r i t y l e v e l s i s fixed so that both the bounded disable time and i n d i v i s i b i l i t y c r i t e r i a can be met. 44 For a process to be swappable, or use v i r t u a l memory, i t must be suspendable. That i s , i t must be possible to prevent i t s execution, even i f i t i s ready. For t h i s reason, the kernel provides an i n e l i g i b l e p r i o r i t y l e v e l from which processes are never dispatched. Even without the i n e l i g i b l e l e v e l , processes could be suspended by setting their p r i o r i t i e s lower than an " i d l e " process that never blocks. However, the id l e process scheme causes extra process switching, and uses resources such as a process descriptor and memory; while the i n e l i g i b l e p r i o r i t y l e v e l i s easy to implement. 3.3 . 4 Protection/Security Control The c a p a b i l i t i e s of a process determine which r e s t r i c t e d kernel operations i t can use, and which devices i t can access. Its s u s c e p t i b i l i t i e s determine the process management operations that a f f e c t i t . C o l l e c t i v e l y , the c a p a b i l i t i e s and s u s c e p t i b i l i t i e s of a process constitute i t s status. Process statuses can be modified by the r e s t r i c t e d .Set_status operation. This mechanism allows the implementation of a protected operating system and eliminates many system module dependencies that would otherwise occur. Two kinds of dependencies arise from the kernel operations themselves. Some operations can prevent the correct operation of the processes they operate on. For example, the .Set_map operation can be used to disrupt a process simply by setting i t s map i n c o r r e c t l y . This i s the f i r s t , d i r e c t kind of dependency. The second i s i n d i r e c t . If two processes, p and q, can both set 45 maps, and p must s e t maps t o f u n c t i o n c o r r e c t l y , then p depends upon q, because q can change what p has done. The c a p a b i l i t y mechanism can be used t o e l i m i n a t e most o f these dependencies by c o n t r o l l i n g which r e s t r i c t e d o p e r a t i o n s , i f any, a p r o c e s s can use. However, t h i s mechanism a l o n e i s not s u f f i c i e n t t o s t r u c t u r e the system w i t h an a c y c l i c dependency graph. C o n s i d e r two system p r o c e s s e s , p and q, where p r e q u i r e s q s e r v i c e s , and thus p depends on q. I f p can d e s t r o y q, then q depends upon p, and they are m u t u a l l y dependent. The s u s c e p t i b i l i t y mechanism can be used t o e l i m i n a t e t h i s s o u r c e o f dependency by d e t e r m i n i n g what o p e r a t i o n s can be performed on a p r o c e s s . I n the above example, q's s t a t u s c o u l d i n d i c a t e t h a t i t was not d e s t r o y a b l e (by any p r o c e s s ) , which e l i m i n a t e s the c y c l e . Another approach t o t h i s problem i s t o a l l o w o n l y one p r o c e s s t o e xecute a l l o p e r a t i o n s t h a t can cause d i r e c t d e p e n d e n c i e s . T h i s i s u n a c c e p t a b l e f o r two r e a s o n s : t h i s "super" p r o c e s s would be a b o t t l e n e c k ; and i t i s not a v e r y modular way t o c o n s t r u c t a system. A s i m p l e p r i v i l e g e d - m o d e scheme, t h a t r e s t r i c t s the e x e c u t i o n o f a su b s e t o f the o p e r a t i o n s t o a s u b s e t o f the p r o c e s s e s , e l i m i n a t e s dependence (from t h i s source) upon n o n - p r i v i l e g e d p r o c e s s e s . T h i s mechanism i s p r o v i d e d by the hardware o f many systems, and seems t o be s u f f i c i e n t t o p r o t e c t the system from u s e r s . I t does not however e l i m i n a t e the mutual dependence o f system p r o c e s s e s . 46 3 . 3 . 5 Memory Management The c a p a b i l i t y t o s e t memory maps a l l o w s a p r o c e s s t o c o n t r o l the use o f n o n - k e r n e l memory. P r o c e s s e s can be g i v e n a c c e s s t o any ar e a s o f n o n - k e r n e l memory, s u b j e c t o n l y t o the l i m i t a t i o n s o f the mapping hardware. Thus, s e p a r a t e address spaces f o r each p r o c e s s , shared segments, teams ( p r o c e s s e s s h a r i n g the same address s p a c e ) , or any o t h e r scheme can be p r o v i d e d . The .Set_map o p e r a t i o n a l l o w s the f u l l f u n c t i o n a l i t y o f the mapping hardware, w i t h the e x c e p t i o n t h a t no p r o c e s s i s a l l o w e d t o a c c e s s the k e r n e l ' s memory. T h i s l o w - l e v e l o p e r a t i o n i s s i m p l e t o implement and g i v e s the system d e s i g n e r c o n s i d e r a b l e f l e x i b i l i t y . Because address spaces are not changed v e r y o f t e n , a p r o c e s s can e f f i c i e n t l y manage main memory. The .Get_map o p e r a t i o n i s not n e c e s s a r y , but i s i n c l u d e d because i t i s s i m p l e t o implement and e l i m i n a t e s the need f o r a (memory manager) p r o c e s s t o m a i n t a i n a copy o f each p r o c e s s ' s map. The k e r n e l must ensure t h a t d i r e c t memory a c c e s s , DMA, (by d e v i c e s such as d i s k c o n t r o l l e r s ) , cannot a c c e s s k e r n e l memory or any d e v i c e c o n t r o l r e g i s t e r s . I f DMA i s not mapped, but can ac c e s s a l l o f memory, the k e r n e l s i m u l a t e s mapped DMA by t r a n s l a t i n g a l l r e q u e s t s r e l a t i v e t o a s p e c i f i e d p r o c e s s ' s map. T h i s i s f a i r l y s i m p l e t o do, and i s a l s o c o n v e n i e n t f o r the p r o c e s s e s i n i t i a t i n g DMA. In t h i s way, they do not have t o be aware o f the memory a c t u a l l y b e i n g used by the p r o c e s s e s i n v o l v e d i n the DMA. 47 A problem e x i s t s i f the memory o f a p r o c e s s i n v o l v e d i n a DMA t r a n s f e r i s r e a l l o c a t e d b e f o r e the t r a n s f e r i s f i n i s h e d . The DMA t r a n s f e r w i l l c o n t i n u e i n t o the r e a l l o c a t e d memory. Thus the k e r n e l m o n i t o r s a l l DMA a c t i v i t y , and s e t s the s u s c e p t i b i l i t i e s o f a l l p r o c e s s e s i n v o l v e d , so t h e i r maps cannot be changed u n t i l the DMA has f i n i s h e d . T h i s i s not n e c e s s a r y f o r the k e r n e l ' s independence, but i t e l i m i n a t e s the dependence o f a memory manager on p r o c e s s e s c o n t r o l l i n g DMA. 3.3.6 P r o c e s s D e s t r u c t i o n D e s t r o y i n g a p r o c e s s i n v o l v e s two b a s i c a c t i v i t i e s . The r e s o u r c e s a l l o c a t e d t o i t must be r e c l a i m e d , and the p r o c e s s e s b l o c k e d a t t e m p t i n g t o communicate w i t h i t must be d e a l t w i t h . T h i s i s much more d i f f i c u l t than p r o c e s s c r e a t i o n because the p r o c e s s must be e x t r a c t e d from i t s e nvironment, which may a f f e c t a l a r g e number o f p r o c e s s e s . The . D e s t r o y _ p r o c e s s o p e r a t i o n r e c l a i m s the kernel-managed r e s o u r c e s , which c o n s i s t p r i m a r i l y o f a p r o c e s s d e s c r i p t o r . I t does not r e c l a i m any process-managed r e s o u r c e s because o f the independence c r i t e r i o n . T h i s i n t u r n i m p l i e s t h a t d e s t r u c t i o n must be a r e s t r i c t e d o p e r a t i o n , so the system p r o c e s s e s can ensure t h a t the r e s o u r c e s they manage are r e c l a i m e d . Moreover, i n d i s c r i m i n a t e d e s t r u c t i o n has t o be p r e v e n t e d . Because d e s t r u c t i o n i s r e s t r i c t e d , the system can c o n t r o l i t . Two n e c e s s a r y r e s t r i c t i o n s are imposed by the k e r n e l . Some p r o c e s s e s are not d e s t r o y a b l e , as i n d i c a t e d by t h e i r s u s c e p t i b i l i t i e s . T h i s e n a b l e s the e l i m i n a t i o n o f the dependency l o o p s t h a t r e s u l t 48 i f a p r o c e s s can d e s t r o y the p r o c e s s e s i t depends upon. P r o c e s s e s not s u s c e p t i b l e t o map changes are a l s o not d e s t r o y a b l e . T h i s l a s t r e s t r i c t i o n e nsures t h a t a d e s t r o y e d p r o c e s s ' s memory cannot be r e a l l o c a t e d w h i l e DMA i s i n p r o g r e s s w i t h i t . The second a c t i v i t y , d e a l i n g w i t h the p r o c e s s e s b l o c k e d on the d e s t r o y e d p r o c e s s , i s the most d i f f i c u l t and c o n t r o v e r s i a l , because t h e r e can be a r b i t r a r i l y many such p r o c e s s e s . Both what s h o u l d happen t o these "abandoned" p r o c e s s e s and how t o a c c o m p l i s h the d e s i r e d f u n c t i o n a l i t y a r e i n t e r e s t i n g i s s u e s . There seem t o be two c h o i c e s o f what t o do: a r r e s t the p r o c e s s e s or r e t u r n an e r r o r i n d i c a t i o n t o them. The k e r n e l implements the f i r s t o f these a l t e r n a t i v e s , because i t i s more f l e x i b l e i n a d d i t i o n t o b e i n g e a s i e r t o implement. When p r o c e s s e s a re a r r e s t e d , they are stopped and a system p r o c e s s g a i n s c o n t r o l over them. I t can then r e s t a r t the o f f e n d e r s w i t h an e r r o r i n d i c a t i o n , thus subsuming the o t h e r a l t e r n a t i v e , or i t can d e s t r o y the o f f e n d e r s , ask an o p e r a t o r what t o do, or do v i r t u a l l y a n y t h i n g e l s e d e s i r e d . T h i s method i s easy f o r the k e r n e l t o p r o v i d e because i t a l r e a d y i n c l u d e s the n e c e s s a r y machinery f o r d e a l i n g w i t h o t h e r e x c e p t i o n s . A d i s a d v a n t a g e o f the a r r e s t a l t e r n a t i v e i s t h a t e x c e p t i o n h a n d l i n g i s more c o m p l i c a t e d because o f the a d d i t i o n a l type o f e x c e p t i o n . A l s o , we have no p r i o r e x p e r i e n c e w i t h the a r r e s t t e c h n i q u e , whereas the d i r e c t e r r o r r e t u r n a l t e r n a t i v e has been used s u c c e s s f u l l y i n T h o t h. The problem w i t h implementing e i t h e r a l t e r n a t i v e , i s t h a t 49 t h e r e i s an a r b i t r a r y number o f p r o c e s s e s i n v o l v e d . Thus they cannot be handled i n d i v i d u a l l y i n a s i n g l e k e r n e l o p e r a t i o n w i t h o u t v i o l a t i n g the bounded d i s a b l e time c r i t e r i o n . Four s o l u t i o n s were c o n s i d e r e d , t h r e e o f which r e q u i r e m a i n t a i n i n g a l i s t o f the p r o c e s s e s b l o c k e d on each p r o c e s s . The s o l u t i o n used appends the l i s t s o f senders and a w a i t e r s o f the d e s t r o y e d p r o c e s s t o a s p e c i a l k e r n e l - m a i n t a i n e d l i s t . The . N e x t _ v i o l a t o r o p e r a t i o n i s used t o remove p r o c e s s e s from t h i s l i s t and g a i n c o n t r o l over them by c a u s i n g them t o a w a i t a r e p l y from the p r o c e s s i n v o k i n g . N e x t _ v i o l a t o r . The advantages o f t h i s s o l u t i o n are t h a t d e s t r u c t i o n i s completed i n one i n d i v i s i b l e o p e r a t i o n , and i t can be implemented c l e a n l y . A d i s a d v a n t a g e i s t h a t i t r e q u i r e s m u l t i p l e i n v o c a t i o n s o f . N e x t _ v i o l a t o r t o c l e a n up a f t e r a p r o c e s s i s d e s t r o y e d . The second s o l u t i o n i s t o append the l i s t s o f b l o c k e d p r o c e s s e s (senders and a w a i t e r s ) onto the incoming message queue o f the e x c e p t i o n - h a n d l i n g p r o c e s s , e f f e c t i v e l y s i m u l a t i n g a mass send o p e r a t i o n . T h i s t e c h n i q u e has many advantages. I t i s one s t e p , does not r e q u i r e the . N e x t _ v i o l a t o r o p e r a t i o n or a s p e c i a l l i s t , and r e s u l t s i n immediate d e s t r u c t i o n . However, i t cannot be implemented c l e a n l y i n c o n s t a n t t i m e . I t r e q u i r e s messages t o be r e c e i v e d from p r o c e s s e s t h a t are not i n the s e n d i n g s t a t e (as i n d i c a t e d by t h e i r p r o c e s s d e s c r i p t o r s ) . I f a b e t t e r way o f t h i n k i n g about t h i s l a s t d i f f i c u l t y can be foun d , t h i s would be the b e s t a l t e r n a t i v e , as i t i s the s i m p l e s t and most e f f i c i e n t . The t h i r d s o l u t i o n i s t o make d e s t r u c t i o n a m u l t i - s t e p o p e r a t i o n , w i t h o n l y a bounded number o f b l o c k e r s d e a l t w i t h on 50 each o p e r a t i o n . A l t h o u g h t h i s can be implemented c l e a n l y , i t r e q u i r e s m u l t i p l e s t e p s , and d e s t r u c t i o n would not be immediate, i m p l y i n g a p r o c e s s c o u l d be p a r t i a l l y d e s t r o y e d . The s o l u t i o n which does not r e q u i r e m a i n t a i n i n g a l i s t o f p r o c e s s e s a w a i t i n g each p r o c e s s e s , i s t o s i m p l y d e s t r o y p r o c e s s e s , and a f t e r each d e s t r u c t i o n (or p e r i o d i c a l l y ) r e p e a t e d l y use a s p e c i a l o p e r a t i o n t o check e v e r y p r o c e s s , a r r e s t i n g any t h a t a re b l o c k e d on a n o n - e x i s t e n t p r o c e s s . T h i s i s v e r y i n e f f i c i e n t i f t h e r e are many p r o c e s s e s . 3.3.7 E x c e p t i o n H a n d l i n g E x c e p t i o n s a re u n u s u a l or f a u l t y c o n d i t i o n s i n d i c a t i n g t h a t e x e c u t i o n s h o u l d not proceed n o r m a l l y . The k e r n e l e n c o u n t e r s a number o f such c o n d i t i o n s . The hardware g e n e r a t e s an i n t e r r u p t when e x c e p t i o n s such as memory e r r o r s , i l l e g a l i n s t r u c t i o n s , and a d d r e s s i n g e r r o r s o c c u r . A l s o , the k e r n e l checks arguments, c a p a b i l i t i e s , and s u s c e p t i b i l i t i e s f o r e x c e p t i o n s . Some o f these s i t u a t i o n s are always the f a u l t o f the p r o c e s s i n c u r r i n g the e x c e p t i o n , w h i l e o t h e r s a re n o t . The f i r s t group i n c l u d e s such s i t u a t i o n s as e x e c u t i n g i l l e g a l machine i n s t r u c t i o n s , a d d r e s s i n g o u t s i d e o f an' address space, i n v o k i n g k e r n e l o p e r a t i o n s w i t h o u t the c a p a b i l i t y t o do so, u s i n g bad arguments t o k e r n e l o p e r a t i o n s , r e p l y i n g t o a p r o c e s s not a w a i t i n g a r e p l y , e t c . The second group i n c l u d e s r e p l y i n g t o a r e q u e s t o r t h a t has been d e s t r o y e d , s e t t i n g a p r o p e r t y o f a d e s t r o y e d p r o c e s s , c r e a t i n g a p r o c e s s when t h e r e are no more p r o c e s s d e s c r i p t o r s , e t c . The k e r n e l uses two d i f f e r e n t mechanisms t o handle t h e s e two 51 c a s e s . When an e x c e p t i o n i s c l e a r l y the f a u l t o f the i n c u r r i n g p r o c e s s , i t i s a r r e s t e d . T h i s means i t i s c o e r c e d i n t o s e n d i n g t o an e x c e p t i o n - h a n d l i n g p r o c e s s , which i s then i n a p o s i t i o n t o i n v e s t i g a t e the e x c e p t i o n and determine what a c t i o n t o t a k e . The l e s s s e r i o u s e x c e p t i o n s are d e a l t w i t h by r e t u r n i n g an e r r o r i n d i c a t i o n , and l e t t i n g the i n c u r r i n g p r o c e s s d e t e r m i n e what t o do about i t . The a r r e s t mechanism g i v e s the system c o n s i d e r a b l e f l e x i b i l i t y f o r h a n d l i n g e x c e p t i o n s . I t i s a l s o f a i r l y s i m p l e t o implement by t a k i n g advantage o f the message-passing mechanism. A minor d i s a d v a n t a g e o f t h i s scheme i s t h a t i t r e q u i r e s t h a t the system i n c l u d e an e x c e p t i o n - h a n d l i n g p r o c e s s , which l i m i t s the f l e x i b i l i t y o f the system d e s i g n e r . However, t h i s i s not s i g n i f i c a n t because most systems would i n c l u d e such a p r o c e s s . Four p r o c e s s management o p e r a t i o n s are p r o v i d e d t o f a c i l i t a t e e x c e p t i o n h a n d l i n g (and d e b u g g i n g ) . The .Get_machine_state o p e r a t i o n i s i n c l u d e d so t h a t an e x c e p t i o n - h a n d l i n g p r o c e s s can d e t e r m i n e where i n an o f f e n d e r ' s address space t o move a r e t u r n v a l u e . I t i s a l s o u s e f u l f o r a debugger t o know the machine s t a t e o f the p r o c e s s b e i n g debugged. , S e t _ m a c h i n e _ s t a t e a l l o w s a debugger t o t r a n s f e r c o n t r o l , i n the p r o c e s s b e i n g debugged, i n response t o a debugging command. Because the . S e t _ m a c h i n e _ s t a t e o p e r a t i o n can be used t o make p r o c e s s e s n o n - d e t e r m i n i s t i c (by changing t h e i r program c o u n t e r s ) , i t use s h o u l d be r e s t r i c t e d . In f a c t , i t might be p r e f e r a b l e t o not p r o v i d e i t a t a l l , which would r e q u i r e the i n i t i a l i z a t i o n o f p r o c e s s e s machine s t a t e s as p a r t o f the c r e a t i o n o p e r a t i o n . 52 The k e r n e l s e t s the v i o l a t i o n i n d i c a t i o n o f an a r r e s t e d p r o c e s s , i n d i c a t i n g the e x c e p t i o n d e t e c t e d . The . G e t _ v i o l a t i o n o p e r a t i o n i s used by the e x c e p t i o n h a n d l e r t o g e t t h i s i n f o r m a t i o n . I n s t e a d , the message s e n t t o the e x c e p t i o n h a n d l e r c o u l d c o n t a i n the v i o l a t i o n i n d i c a t i o n , but then i n f o r m a t i o n would be l o s t , and the o f f e n d i n g p r o c e s s c o u l d not be r e s t a r t e d . • S e t _ v i o l a t i o n was i n c l u d e d f o r symmetry, but c o u l d a l s o be used by p r o p r i e t o r p r o c e s s e s so t h a t e x c e p t i o n s they d e t e c t e d were handl e d i n the same way as k e r n e l - d e t e c t e d e x c e p t i o n s . That i s , when a p r o p r i e t o r d e t e c t e d an e x c e p t i o n , i t c o u l d s e t the o f f e n d e r ' s v i o l a t i o n i n d i c a t i o n w i t h . S e t _ v i o l a t i o n and f o r w a r d the o f f e n d e r t o the e x c e p t i o n h a n d l e r . The l e s s s e r i o u s e x c e p t i o n s do not r e s u l t i n a r r e s t s t o a v o i d problems such as the e x c e p t i o n h a n d l e r i n c u r r i n g an e x c e p t i o n , or p r o c e s s e s t h a t the e x c e p t i o n h a n d l e r depends upon i n c u r r i n g e x c e p t i o n s . Three a l t e r n a t i v e mechanisms f o r d e a l i n g w i t h e x c e p t i o n s were r e j e c t e d . P r o c e s s e s i n c u r r i n g e x c e p t i o n s c o u l d be d e s t r o y e d , but t h i s would make i t d i f f i c u l t t o d e t e r m i n e what happened. E x c e p t i o n s c o u l d be i g n o r e d ( i . e . the k e r n e l o p e r a t i o n s c o u l d r e t u r n i m m e d i a t e l y upon d e t e c t i n g an e x c e p t i o n ) , but then e r r o r s would be hard t o d e t e c t . S i g n a l s , or s o f t w a r e i n t e r r u p t s , c o u l d be used t o t r a n s f e r c o n t r o l t o a s p e c i a l s e c t i o n o f the p r o c e s s ' s code, but t h i s v i o l a t e s the n o t i o n o f a p r o c e s s e x e c u t i n g d e t e r m i n i s t i c a l l y . A r r e s t i n g i s implemented by c o e r c i n g messages t o a p a r t i c u l a r e x c e p t i o n - h a n d l i n g p r o c e s s . T h i s t e c h n i q u e was s e l e c t e d i n f a v o r 53 o f two a l t e r n a t i v e s because i t seemed the s i m p l e s t and most s t r a i g h t f o r w a r d . Rather than one c e n t r a l e x c e p t i o n h a n d l e r , i t might be p r e f e r a b l e t o s p e c i f y an e x c e p t i o n - h a n d l i n g p r o c e s s f o r each p r o c e s s , because o f dependency problems w i t h the one h a n d l e r scheme. The o t h e r mechanism does not employ c o e r c e d messages a t a l l , r a t h e r a s p e c i a l l i s t i s used t o h o l d a l l a r r e s t e d p r o c e s s e s , and an a d d i t i o n a l o p e r a t i o n i s used t o s y n c h r o n i z e w i t h and remove o f f e n d e r s from the l i s t . The i s s u e s o f e x c e p t i o n h a n d l i n g are d i f f i c u l t and deserve more a t t e n t i o n than we have been a b l e t o g i v e them. 3.3.8 Summary P r o c e s s management i n v o l v e s : i n i t i a l i z i n g the system; c r e a t i n g and d e s t r o y i n g p r o c e s s e s ; managing memory; s c h e d u l i n g the p r o c e s s o r ; c o n t r o l l i n g s e c u r i t y ; and h a n d l i n g e x c e p t i o n a l c o n d i t i o n s . The k e r n e l p r o v i d e s the p r o c e s s management o p e r a t i o n s so t h a t system p r o c e s s e s can p e r f o r m much o f t h i s t a s k . The k e r n e l c r e a t e s one r o o t p r o c e s s which then i n i t i a l i z e s the system p r o c e s s e s , because t h i s i s s i m p l e r f o r the k e r n e l than c r e a t i n g a l l o f the system p r o c e s s e s , and a l l o w s the k e r n e l t o be independent o f the system p r o c e s s s t r u c t u r e . P r o c e s s c r e a t i o n does not i n t e r f e r e w i t h o t h e r management f u n c t i o n s . Two s c h e d u l i n g mechanisms p r o v i d e speed and f l e x i b i l i t y . The k e r n e l ' s m i c r o d i s p a t c h i n g s t r a t e g y i s s e l f - c o n t a i n e d and t h u s f a s t , whereas the dynamic p r i o r i t y mechanism a l l o w s a p r o c e s s t o implement any macro s c h e d u l i n g s t r a t e g y d e s i r e d . The c a p a b i l i t y / s u s c e p t i b i l i t y mechanism not o n l y p r o t e c t s the system 54 p r o c e s s e s from user p r o c e s s e s , but a l s o from each o t h e r . Both are e s s e n t i a l f o r an a c y c l i c dependency s t r u c t u r e . Memory i s a b s t r a c t e d v e r y l i t t l e , because t h i s i s s i m p l e t o implement, and i t g i v e s the system d e s i g n e r g r e a t f l e x i b i l i t y . P r o c e s s d e s t r u c t i o n i s d i f f i c u l t because o f the p o t e n t i a l l y unbounded number o f p r o c e s s e s t h a t are a f f e c t e d . I t i s handled i n c o n s t a n t time by moving l i s t s o f p r o c e s s e s . P r o c e s s e s i n c u r r i n g e x c e p t i o n s ( f a u l t s ) are a r r e s t e d . That i s , they are c o e r c e d i n t o s e n d i n g t o an e x c e p t i o n - h a n d l i n g p r o c e s s which then d e t e r m i n e s what t o do about them, because t h i s i s the most f l e x i b l e o p t i o n . 3 . 4 D e v i c e A b s t r a c t i o n The k e r n e l d e s i g n e x p l o r e s two a l t e r n a t i v e approaches t o d e v i c e a b s t r a c t i o n . The f i r s t r e q u i r e s the k e r n e l t o do as l i t t l e as p o s s i b l e , by p r o v i d i n g o p e r a t i o n s f o r a c c e s s i n g d e v i c e r e g i s t e r s . The second p r o v i d e s c o n v e n i e n t y e t s i m p l e h i g h e r - l e v e l a b s t r a c t i o n s o f the d e v i c e s . The k e r n e l must at l e a s t : ensure t h a t d e v i c e s cannot compromise the k e r n e l ; r e s t r i c t a c c e s s t o d e v i c e s on a p e r - d e v i c e b a s i s ; and d i s a b l e (and/or acknowledge) i n t e r r u p t s t h a t are not b e i n g a w a i t e d by a p r o c e s s . One way d e v i c e s can compromise the k e r n e l i s v i a d i r e c t memory a c c e s s , DMA. I f a d e v i c e can a c c e s s a l l o f memory because i t s DMA i s not mapped, a p r o c e s s c o n t r o l l i n g the d e v i c e c o u l d a c c e s s the k e r n e l ' s memory, which v i o l a t e s the independence c r i t e r i o n . The use o f d e v i c e s must be r e s t r i c t e d on a p e r - d e v i c e b a s i s t o e l i m i n a t e the i n d i r e c t dependencies t h a t would r e s u l t i f two p r o c e s s e s c o u l d 55 a c c e s s the same d e v i c e . The k e r n e l must be a b l e t o d i s a b l e (and/or acknowledge) i n t e r r u p t s , so t h a t i f an i n t e r r u p t i s m i s s e d , the k e r n e l can p r e v e n t the system from g o i n g i n t o a t i g h t l o o p , r e s p o n d i n g r e p e a t e d l y t o the same i n t e r r u p t . The main advantage o f the k e r n e l a b s t r a c t i n g d e v i c e s as l i t t l e as p o s s i b l e i s t h a t the k e r n e l can be independent o f the d e v i c e c o n f i g u r a t i o n o f a p a r t i c u l a r system, and a l s o independent o f the p a r t i c u l a r d e v i c e i n t e r f a c e s . Thus none, or o n l y a s m a l l amount, o f the k e r n e l code would be d e v i c e - d e p e n d e n t . The environment p r o v i d e d by the k e r n e l would, however, be v e r y d e v i c e - d e p e n d e n t . B u t , t h i s would a l l o w most o f the d e vice-dependent code t o be c o n t a i n e d i n a few s m a l l " i n t e r f a c e " p r o p r i e t o r s which would implement i n t e r f a c e - i n d e p e n d e n t a b s t r a c t i o n s o f the d e v i c e s , used by the d e v i c e p r o p r i e t o r s . Once the k e r n e l i s v e r i f i e d , i t would be advantageous not t o modify i t a t a l l . Even r e c o m p i l a t i o n i s u n d e s i r a b l e , as c o m p i l e r s have a tendency t o e v o l v e . A l t h o u g h s i m p l e , new d e v i c e d r i v e r s c o u l d be i n c o r r e c t l y added t o the k e r n e l by p e o p l e u n f a m i l i a r w i t h i t . Another advantage i s t h a t the k e r n e l would be s m a l l e r i f i t d i d not i n c l u d e the code t o m a n i p u l a t e d e v i c e i n t e r f a c e s . The p r i m a r y d i s a d v a n t a g e o f t h i s scheme i s i n e f f i c i e n c y . A c t u a l l y i t s e f f i c i e n c y depends on the hardware mechanisms f o r m a n i p u l a t i n g d e v i c e s . The hardware c o u l d be d e s i g n e d so t h e r e would be no l o s s o f e f f i c i e n c y w i t h t h i s scheme. I t c o u l d r e s t r i c t a c c e s s t o each d e v i c e s e p a r a t e l y , ensure t h a t d e v i c e s c o u l d not compromise the k e r n e l (by mapping DMA), and p r o v i d e a 5 6 s t a n d a r d mechanism f o r d i s a b l i n g (and/or acknowledging) i n t e r r u p t s . But because c u r r e n t hardware does not have the s e f e a t u r e s , a l l d e v i c e m a n i p u l a t i o n has t o go through the k e r n e l t o o b t a i n the r e q u i r e d f u n c t i o n a l i t y . T h i s r e s u l t s i n a l l the overhead o f k e r n e l c a l l s f o r each d e v i c e o p e r a t i o n . I f these o p e r a t i o n s are too l o w - l e v e l , the overhead i s c o n s i d e r a b l e . The second approach t o d e v i c e a b s t r a c t i o n , t o p r o v i d e a c o n v e n i e n t y e t s i m p l e a b s t r a c t i o n o f each d e v i c e t y p e , i s more c o n v e n i e n t f o r the o p e r a t i n g system. I f the k e r n e l does a l l o f the l o w - l e v e l m a n i p u l a t i o n o f the d e v i c e i n t e r f a c e s , the system p r o c e s s e s do not have t o . T h i s approach i s a l s o s l i g h t l y more e f f i c i e n t because the o p e r a t i o n s are h i g h e r - l e v e l . That i s , o n l y one k e r n e l c a l l i s r e q u i r e d f o r each l o g i c a l t r a n s a c t i o n . A l s o , i t i s p o s s i b l e w i t h t h i s scheme t o p r o v i d e v e r y h i g h - l e v e l a b s t r a c t i o n s , w i t h l a r g e i n c r e a s e s i n e f f i c i e n c y . For example, c h a r a c t e r - o r i e n t e d d e v i c e s r e q u i r e s e r v i c e f o r each c h a r a c t e r , but they c o u l d be a b s t r a c t e d t o appear t o be DMA d e v i c e s . The major d i s a d v a n t a g e o f t h i s approach i s t h a t the k e r n e l would c o n t a i n a s i g n i f i c a n t amount o f d e v i c e - d e p e n d e n t code, and f u r t h e r t h a t the k e r n e l would have t o be m o d i f i e d whenever the c o n f i g u r a t i o n o f d e v i c e s i n the system changed. A l t h o u g h the k e r n e l has been d e s i g n e d t o p r o v i d e e i t h e r approach t o d e v i c e a b s t r a c t i o n , i n s u f f i c i e n t e x p e r i e n c e has been o b t a i n e d t o determine which i s p r e f e r a b l e . D e v i c e s a r e c l a s s i f i e d i n t o t h r e e broad t y p e s ( t i m i n g , c h a r a c t e r , and b l o c k ) on the b a s i s o f the mechanism used t o communicate w i t h them. Timing d e v i c e s t y p i c a l l y have no d a t a , or 5 7 o n l y a s m a l l f i x e d amount o f d a t a , a s s o c i a t e d w i t h them. C h a r a c t e r d e v i c e s l o g i c a l l y h a n d l e d a t a a c h a r a c t e r or word a t a t i m e , a t a r e l a t i v e l y slow r a t e . B l o c k d e v i c e s o f t e n have h i g h t r a n s f e r r a t e s w i t h the d a t a b y p a s s i n g the p r o c e s s o r , g o i n g d i r e c t l y t o or from memory. T h i s o p e r a t i v e c l a s s i f i c a t i o n o f d e v i c e s i s u s e f u l because a l l d e v i c e s i n a c l a s s can be m a n i p u l a t e d w i t h the same k e r n e l o p e r a t i o n s . 3 . 4 . 1 G e n e r a l Purpose O p e r a t i o n s The most common and i m p o r t a n t g e n e r a l purpose o p e r a t i o n p r o v i d e d i s . A w a i t _ e v e n t , which i s used t o s y n c h r o n i z e w i t h t i m i n g and b l o c k d e v i c e s . I t c o u l d a l s o be used t o s y n c h r o n i z e w i t h s t r a n g e c o n d i t i o n s o c c u r r i n g on c h a r a c t e r d e v i c e s . The most c o n t r o v e r s i a l a s p e c t o f t h i s o p e r a t i o n i s t h a t i t r e t u r n s i m m e d i a t e l y ( i . e . does not b l o c k ) i f an i n t e r r u p t has o c c u r r e d s i n c e the l a s t time i t was a w a i t e d . T h i s i s however the d e s i r e d e f f e c t i n a l l missed i n t e r r u p t s i t u a t i o n s we have e n c o u n t e r e d . A few examples i l l u s t r a t e t h i s p o i n t . F i r s t , c o n s i d e r a t i m e r t h a t causes an event when i t e x p i r e s . I f a p r o c e s s a w a i t s the event a f t e r i t o c c u r s , i t c o u l d w a i t f o r e v e r i f .Await_event d i d not r e t u r n i m m e d i a t e l y . The same i s t r u e f o r a d i s k h a n d l e r i f the a c t i o n i t s t a r t e d completes b e f o r e i t i s a w a i t e d . Even d e v i c e s t h a t r e p e a t e d l y i n t e r r u p t because o f r e a l w o r l d e v e n t s r a t h e r than i n response t o i n t e r n a l r e q u e s t s (e.g. i n p u t from a communications i n t e r f a c e ) , work b e t t e r w i t h an immediate r e t u r n . I f an i n t e r r u p t has been m i s s e d , the c h a r a c t e r may s t i l l be r e c o v e r a b l e from the i n t e r f a c e ' s b u f f e r . But i f the nex t i n t e r r u p t i s a w a i t e d , the c h a r a c t e r i s guaranteed t o be l o s t . I n 58 most i n s t a n c e s the immediate r e t u r n does not even c o m p l i c a t e the a w a i t e r , as i t h a n d l e s missed e v e n t s the same way as normal e v e n t s . Of c o u r s e , h a n d l e r s o f d e v i c e s f o r which missed i n t e r r u p t s are i m p o r t a n t have t o t e s t t h i s c o n d i t i o n , but they have t o do something s p e c i a l anyway. R e t u r n i n g a count o f the number o f m i s s e d i n t e r r u p t s i s o f q u e s t i o n a b l e u s e f u l n e s s as few s i t u a t i o n s r e q u i r e thus i n f o r m a t i o n . However i t i s j u s t as easy t o p r o v i d e as the missed i n d i c a t i o n t h a t i s n e c e s s a r y f o r some d e v i c e s . A l s o , i f the k e r n e l d i s a b l e s missed i n t e r r u p t s , the count can o n l y be z e r o or one. I t must acknowledge, not d i s a b l e , the i n t e r r u p t i f the count i s t o be s i g n i f i c a n t . Each l o g i c a l d e v i c e has a t most one event a s s o c i a t e d w i t h i t . T h i s s i m p l i f i e s the s e m a n t i c s o f the .Await_event o p e r a t i o n . I f i t i s n e c e s s a r y t o use .Await_event t o i n d e p e n d e n t l y s y c h r o n i z e w i t h more than one type o f i n t e r r u p t from a s i n g l e p h y s i c a l d e v i c e , i t must be c o n f i g u r e d as more than one l o g i c a l d e v i c e , and the k e r n e l s e p a r a t e s the e v e n t s . Communication i n t e r f a c e s are the most common case o f a d e v i c e c a u s i n g m u l t i p l e t y p e s o f i n t e r r u p t s (e.g. r e a d r e q u e s t and w r i t e r e q u e s t ) , but t h e s e do not need t o be c o n f i g u r e d as two l o g i c a l d e v i c e s because they are s y n c h r o n i z e d w i t h by u s i n g the . R e a d _ c h a r a c t e r and . W r i t e _ c h a r a c t e r o p e r a t i o n s , not the . A w a i t _ e v e n t o p e r a t i o n . I f two or more p h y s i c a l d e v i c e s share an i n t e r r u p t l e v e l , the k e r n e l s e p a r a t e s these i n t o d i s t i n c t l o g i c a l e v e n t s , d e s p i t e the f a c t t h a t a p r o c e s s c o u l d p e r f o r m t h i s f u n c t i o n . That i s , each i n t e r r u p t l e v e l c o u l d be a s s o c i a t e d w i t h a l o g i c a l event (and 59 t h u s a l o g i c a l d e v i c e ) and a p r o c e s s c o u l d a w a i t i t . T h i s p r o c e s s would then p o l l the d e v i c e s connected t o the l e v e l t o d e t e r m i n e which had i n t e r r u p t e d and pass t h i s i n f o r m a t i o n t o the p r o p r i e t o r p r o c e s s a s s o c i a t e d w i t h the d e v i c e . T h i s was not done because i t would cause an e x t r a p r o c e s s s w i t c h f o r each i n t e r r u p t on a shared l e v e l . The d e v i c e c o n t r o l o p e r a t i o n s , . W r i t e _ b i t s and . R e a d _ b i t s , p r o v i d e d i r e c t a c c e s s t o d e v i c e c o n t r o l r e g i s t e r s . A l t h o u g h these o p e r a t i o n s are n e i t h e r a e s t h e t i c a l l y p l e a s i n g nor e f f i c i e n t , t hey a l l o w the f u l l power o f a d e v i c e t o be used by the system p r o c e s s e s w h i l e the k e r n e l o n l y needs t o know how t o a c c e s s i t s r e g i s t e r s , not how i t works. These o p e r a t i o n s are p a r t i c u l a r l y u s e f u l f o r c o n t r o l l i n g "programmable" i n t e r f a c e s t h a t a l l o w numerous a s p e c t s o f the d e v i c e t o be changed under s o f t w a r e c o n t r o l . Thus the k e r n e l does not need t o p r o v i d e o p e r a t i o n s t o s e t t r a n s m i s s i o n r a t e s , the number o f s t o p b i t s , synch c h a r a c t e r s , or o t h e r u n u s u a l f e a t u r e s o f an i n t e r f a c e . A d i s a d v a n t a g e o f these o p e r a t i o n s i s t h a t they c o u l d be v e r y d i f f i c u l t t o implement on hardware t h a t has s t r a n g e t i m i n g c o n s i d e r a t i o n s a s s o c i a t e d w i t h a c c e s s i n g d e v i c e r e g i s t e r s . The a u t h o r , however, i s not aware o f any such c o n s i d e r a t i o n s , o t h e r than r e q u i r e m e n t s f o r minimum d e l a y s . 3 . 4.2 Timing D e v i c e s The k e r n e l extends the f u n c t i o n a l i t y o f the c l o c k hardware, which (on the TI990/10 and many o t h e r m i n i c o m p u t e r s ) p r o v i d e s an i n t e r r u p t a t p e r i o d i c i n t e r v a l s (120 Hz on the T I ) . The k e r n e l 60 m a i n t a i n s the time and p r o v i d e s a v a r i a b l e t i m e r s e r v i c e . T h i s has been done f o r t h r e e r e a s o n s . F i r s t , i t i s more e f f i c i e n t f o r the k e r n e l t o p r o c e s s the hardware i n t e r r u p t s because i t does not i n c u r the overhead o f a p r o c e s s s w i t c h on each hardware i n t e r r u p t . Second, i t a l l o w s a c l e a n e r system p r o c e s s s t r u c t u r e f o r the c l o c k . T h i r d , r e a l - t i m e c l o c k hardware on some machines p r o v i d e s t h i s l e v e l o f f u n c t i o n a l i t y . Because the k e r n e l a b s t r a c t i o n i s h i g h enough t o e x p l o i t t h i s hardware, the d e s i g n i s more p o r t a b l e . That i s , o n l y the k e r n e l has t o be m o d i f i e d t o make use o f t h i s more s o p h i s t i c a t e d r e a l - t i m e c l o c k hardware. The p r i m a r y d i s a d v a n t a g e o f t h i s scheme i s t h a t i t r e q u i r e s the k e r n e l t o be more c o m p l i c a t e d . The amount o f code r e q u i r e d t o implement t h i s f u n c t i o n a l i t y i s s m a l l however, and the s i g n i f i c a n t g a i n s i n e f f i c i e n c y seem worth the e x t r a c o m p l e x i t y . The time i s r e p r e s e n t e d as a l a r g e p r e c i s i o n b i n a r y number o f seconds p l u s c l i c k s , because t h i s i s s i m p l e r and more e f f i c i e n t f o r the s o f t w a r e t o d e a l w i t h than J u l i a n t i m e . T h i s i s s i m p l e r f o r a l l s o f t w a r e t h a t d e a l s w i t h t i m e , not j u s t the k e r n e l . The program environment l i b r a r y i n c l u d e s r o u t i n e s t o c o n v e r t from the b i n a r y r e p r e s e n t a t i o n t o the J u l i a n and v i c e v e r s a . 3 . 4.3 C h a r a c t e r D e v i c e s The k e r n e l p r o v i d e s e f f i c i e n t machine-independent o p e r a t i o n s f o r communicating w i t h c h a r a c t e r d e v i c e s . The s p e c i f i c d e t a i l s o f a c c e s s i n g the d e v i c e i n t e r f a c e s are h a n d l e d by the k e r n e l . T h i s has the advantage o f a l l o w i n g p r o c e s s e s t h a t use the d e v i c e s t o be i n t e r f a c e - i n d e p e n d e n t , a l l o w i n g the system 61 processes to be more portable. However, i t also results in a less portable kernel. Because giving characters to and getting characters from the interfaces are common operations, a high-level abstraction seems reasonable. Other less common operations, such as setting the rate of a communication l i n e , or determining error conditions are not included. These operations tend to be highly i n t e r f a c e - s p e c i f i c , and occur so seldomly that kernel operations s p e c i f i c a l l y for these device operations seem u n j u s t i f i e d . The l e s s - e f f i c i e n t general-purpose operations for manipulating device interfaces give the system the a b i l i t y to use these more esoteric features of the hardware. Output data i s buffered by the kernel to increase e f f i c i e n c y . By providing buffers, the amount of process switching a r i s i n g from outputting characters i s reduced. Because outputting characters i s a very frequent operation, i t s e f f i c i e n c y i s of concern. Input data i s much less frequent, and i s buffered simply to make the synchronization code simpler. These operations synchronize on f u l l (output) and empty (input) buffers, because this is more convenient for the device-handling processes, and is not d i f f i c u l t to implement. The alternative of asynchronous get and put operations, that return indications that the process should wait before attempting further communication, would be s l i g h t l y easier to implement, but would also be far less convenient to use, as well as less e f f i c i e n t . The asynchronous scheme would also require the use of a separate synchronization operation (e.g. .Await_event). 62 B l o c k communication o p e r a t i o n s are an i n t e r e s t i n g a l t e r n a t i v e t o t hese c h a r a c t e r - o r i e n t e d o p e r a t i o n s . S i m u l a t e d DMA o p e r a t i o n s would be both c o n v e n i e n t and e f f i c i e n t , p a r t i c u l a r l y f o r o u t p u t t i n g l a r g e q u a n t i t i e s o f d a t a , as when l i s t i n g f i l e s . These o p e r a t i o n s would even be e a s i e r t o implement than the b u f f e r e d c h a r a c t e r o p e r a t i o n s , e i t h e r by the k e r n e l or d i r e c t l y by the d e v i c e i n t e r f a c e . For example, a b l o c k o u t p u t o p e r a t i o n c o u l d s p e c i f y the number and l o c a t i o n o f the c h a r a c t e r s t o be o u t p u t . The k e r n e l would copy these c h a r a c t e r s i n t o a b u f f e r i n i t s a d d r ess space, and s i g n a l an event when they had been o u t p u t . S i m i l a r l y , the k e r n e l c o u l d p l a c e a l l i n p u t c h a r a c t e r s i n t o a b u f f e r i n i t s a d dress space, s i g n a l i n g an event on each c h a r a c t e r a r r i v a l , and when a p r o c e s s wanted the c h a r a c t e r s i t would i n v o k e an o p e r a t i o n t o copy them i n t o i t s a d d r e s s space. T h i s scheme would make "type ahead" t r i v i a l t o implement. I t would not even be n e c e s s a r y f o r the k e r n e l t o keep b u f f e r s i f i t a c c e s s e d b u f f e r s i n the p r o p r i e t o r ' s address space whenever i t s e r v i c e d the i n t e r f a c e . These o p e r a t i o n s were not i n c l u d e d p r i m a r i l y due t o a l a c k o f t i m e , and because the c h a r a c t e r o p e r a t i o n s were more f a m i l i a r . 3 . 4 . 4 B l o c k D e v i c e s B l o c k d e v i c e s communicate d a t a v i a d i r e c t memory a c c e s s , DMA. As p r e v i o u s l y s t a t e d , i f DMA i s not mapped, the k e r n e l must c o n t r o l i t d i r e c t l y . I f i t i s mapped, the k e r n e l must c o n t r o l i t v i a the mapping hardware. The . W r i t e _ r e g s and .Read_regs o p e r a t i o n s a l l o w t h i s c o n t r o l . A l l a d d r e s s e s are i n t e r p r e t e d r e l a t i v e t o a p r o c e s s ' s address space, which g u a r a n t e e s t h a t the DMA cannot e f f e c t the k e r n e l because a l l p r o c e s s address spaces are d i s t i n c t from the k e r n e l ' s address space. An a l t e r n a t i v e t o t r a n s l a t i n g a d d r e s s e s r e l a t i v e t o a p r o c e s s ' s a d d r e s s space i s to g i v e each DMA d e v i c e i t s own address space, or a t l e a s t i t s own map. T h i s would however r e q u i r e some mechanism f o r s p e c i f y i n g t h i s map. .Set_map c o u l d not be used f o r t h i s w i t h o u t c o m p l i c a t i n g i t s s e m a n t i c s . The mechanism p r o v i d e d i s easy t o implement whether the h o s t machine maps DMA or n o t . In f a c t , i t a l l o w s the system p r o c e s s e s t o be o b l i v i o u s as t o whether or not i t i s mapped. C o n t r o l o f the a c t u a l d e v i c e p a r a m e t e r s , such as b l o c k a d d r e s s e s , a re not a b s t r a c t e d f o r two r e a s o n s . I t i s un n e c e s s a r y f o r the k e r n e l t o do, and s i m p l i f i e s the k e r n e l t o e x c l u d e i t . I t a l s o a l l o w s the system more f l e x i b i l i t y as t o how l o g i c a l b l o c k a d d r e s s e s , or even l o g i c a l d e v i c e s , map onto p h y s i c a l b l o c k a d d r e s s e s . These o p e r a t i o n s are asynchronous f o r i n c r e a s e d f l e x i b i l i t y . O f t e n one c o n t r o l l e r i s used t o i n t e r f a c e t o s e v e r a l d e v i c e s . I n thes e s i t u a t i o n s i t i s not uncommon f o r the c o n t r o l l e r s t o a l l o w the d e v i c e s t o be c o n t r o l l e d a s y n c h r o n o u s l y . An example i s c o n c u r r e n t s e e k i n g o f d i s k d r i v e s on a common c o n t r o l l e r . I t i s s t i l l s t r a i g h t f o r w a r d f o r a d e v i c e h a n d l e r t o s y n c h r o n i z e w i t h the d e v i c e by a w a i t i n g i t s c o m p l e t i o n i m m e d i a t e l y a f t e r r e q u e s t i n g the o p e r a t i o n . 64 3.4.5 Summary Two approaches t o d e v i c e a b s t r a c t i o n a re c o n s i d e r e d . The f i r s t i s f o r the k e r n e l t o remain as d e v i c e - i n d e p e n d e n t as p o s s i b l e . T h i s would r e s u l t i n a more p o r t a b l e k e r n e l t h a t i s i n s e n s i t i v e t o d e v i c e c o n f i g u r a t i o n changes. I t would a l s o a l l o w d e v i c e dependencies t o be l o c a l i z e d i n a few " i n t e r f a c e " p r o p r i e t o r p r o c e s s e s . U n f o r t u n a t e l y , t h i s approach c o u l d be p a i n f u l l y i n e f f i c i e n t . The second approach c l a s s i f i e s d e v i c e s i n t o t h r e e t y p e s ( t i m i n g , c h a r a c t e r , and b l o c k ) and p r o v i d e s s i m p l e y e t c o n v e n i e n t o p e r a t i o n s f o r m a n i p u l a t i n g each c l a s s o f d e v i c e s . T h i s would a l l o w the system p r o c e s s e s t o be more p o r t a b l e and would a l s o be more e f f i c i e n t than the f i r s t approach. I t would however make the k e r n e l l a r g e r and d e v i c e - and c o n f i g u r a t i o n - d e p e n d e n t . I n s u f f i c i e n t e x p e r i e n c e w i t h t h e s e approaches has been o b t a i n e d t o dete r m i n e which i s p r e f e r a b l e . 3.5 Chapter Summary The message-based i n t e r p r o c e s s communication mechanism was s e l e c t e d because: i t i s s i m p l e and e f f i c i e n t ; i t a l l o w s p r o p r i e t o r p r o c e s s e s t o be independent o f t h e i r r e q u e s t o r s ; and the o p e r a t i o n s can be i n d i v i s i b l e . The o t h e r communication mechanisms c o n s i d e r e d (except a d a t a move o p e r a t i o n ) were c o n s i d e r e d too h i g h l e v e l t o i n c l u d e i n the k e r n e l . The p r o c e s s management o p e r a t i o n s a l l o w the k e r n e l t o be s m a l l but s t i l l independent o f the system p r o c e s s e s . Because o f 65 the power of these operations, a protection scheme of c a p a b i l i t i e s and s u s c e p t i b i l i t i e s for these operations i s necessary to prevent c y c l i c dependencies among the system processes. The design of the device abstraction i s complicated by c o n f l i c t i n g design c r i t e r i a . General purpose device operations reduce the device-dependency and complexity of the kernel as well as reduce the number of kernel operations. Higher-level, spe c i a l device operations provide greater e f f i c i e n c y and simplify the associated device handling processes. This chapter has attempted to j u s t i f y the design of the kernel in terms of the design c r i t e r i a . Empirical support for the kernel i s provided by i t s implementation, which i s described in the next chapter. 66 Chapter 4 Implementation of the Kernel 4.1 Overview The implementation of the kernel consists of a c o l l e c t i o n of function and data modules written in Zed [Cheriton & Steeves, 1979d] plus a few TI990/10 assembler modules. The major data structures include process descriptors (PD's), device descriptors (DDs), and ready queues. The kernel functions that act upon these data structures can be c l a s s i f i e d into six types: 1. operation functions that correspond one-to-one with the kernel operations; 2. interface functions that pass control from processes to the kernel; 3. interrupt functions that execute in response to interrupts; 4. support functions that provide general low-level services such as l i s t manipulation, and process state changes; 5. i n i t i a l i z a t i o n functions that set up the kernel data structures; and, 6. debugger functions. Figure 2 depicts the basic structure of the kernel functions. PROCESSES KERNEL DEBUGGER FUNCTIONS K INITIALIZATION FUNCTIONS kernel c a l l INTERFACE FUNCTIONS OPERATION FUNCTIONS SUPPORT FUNCTIONS * INTERRUPT FUNCTIONS If HARDWARE halt button interrupts FIGURE 2: THE BASIC STRUCTURE OF THE KERNEL 68 The k e r n e l i s the onl y module that executes i n p r i v i l e g e d mode. Thus i t has e x c l u s i v e c o n t r o l over the memory mapping hardware, the d e v i c e s , and the machine's p r i v i l e g e d mode. There are three ways to enter the k e r n e l : k e r n e l c a l l s , i n t e r r u p t s , and the p r o c e s s o r ' s h a l t button. Processes make k e r n e l c a l l s , d e v i c e s i n t e r r u p t , and the f r o n t panel h a l t button t r a n s f e r s c o n t r o l to the ROM debugger/loader. The k e r n e l r e t u r n s c o n t r o l by resuming execution o f the h i g h e s t p r i o r i t y ready p r o c e s s . The process a c t i v e when the k e r n e l was entered i s returned to unless a higher p r i o r i t y process was re a d i e d d u r i n g the execution of the k e r n e l , i n which case i t i s d i s p a t c h e d . The k e r n e l executes each o p e r a t i o n i n d i v i s i b l y and d e t e r m i n i s t i c a l l y , because a l l i n t e r r u p t s are d i s a b l e d while i n k e r n e l mode, with two ex c e p t i o n s . The power-up i n t e r r u p t cannot be d i s a b l e d on the TI990/10, but i t should never occur while the system i s o p e r a t i n g . I f there are no processes ready f o r ex e c u t i o n , the k e r n e l enters an i d l e s t a t e and turns on the i n t e r r u p t s . In t h i s s t a t e however, i t does noth i n g . I t i s not yet c l e a r how t h i s w i l l complicate the v e r i f i c a t i o n o f the k e r n e l . The k e r n e l has been kept as smal l as reasonable. The c u r r e n t implementation c o n t a i n s 71 f u n c t i o n modules and approximately 2500 l i n e s of source code (of which about 20-30% are b l a n k ) . Twenty four of the f u n c t i o n modules are machine dependent, and only 8 of these are assembler language. The compiled k e r n e l r e q u i r e s l e s s the 8K bytes of code space and IK + (62 * the number of processes) bytes of data space. The symbolic debugger 69 r e q u i r e s an a d d i t i o n a l 8K bytes. These numbers are o n l y intended to g i v e the reader some idea of the s i z e of the k e r n e l . Timing i n f o r m a t i o n , such as the maximum d i s a b l e time and average exe c u t i o n times of important f u n c t i o n s ( i . e . Send, Receive, and R e p l y ) , i s not c u r r e n t l y a v a i l a b l e , however i t i s expected that these are s l i g h t l y g r e a t e r than Thoth's [ C h e r i t o n e t . a l . , 1979c. The remainder of t h i s s e c t i o n p r o v i d e s a b r i e f i n t r o d u c t i o n to the Zed language and the TI990/10 p r o c e s s o r . The f o l l o w i n g s e c t i o n d e s c r i b e s the k e r n e l data s t r u c t u r e s and f u n c t i o n s , while the l a s t s e c t i o n d e s c r i b e s the m u l t i - p r o c e s s t e s t system that was implemented. 4.1.1 The Zed Language Most of the k e r n e l i s w r i t t e n i n a machine-oriented h i g h - l e v e l language, Zed, which i s s i m i l a r to UNIX's language C. Both are descendants of the language BCPL. A c t u a l l y Zed i s i n t e r m e d i a t e - l e v e l because i t supports o n l y word-oriented data types, and has no I/O i n s t r u c t i o n s . However, i t does i n c l u d e the standard s t r u c t u r e d programming c o n t r o l c o n s t r u c t s . Unstructured c o n t r o l (e.g. goto) was not used, d e s p i t e the l o w - l e v e l nature of the k e r n e l . The r a t h e r r i c h set of word o p e r a t o r s i n c l u d e s : i n t e g e r a r i t h m e t i c , b i t w i s e l o g i c a l , p o i n t e r , comparison, boolean and assignment o p e r a t o r s . P o i n t e r s are used e x t e n s i v e l y , but no other data s t r u c t u r e s are supported by Zed. A t e x t u a l s u b s t i t u t i o n mechanism i s used to parameterize most of the k e r n e l ' s c o n s t a n t s . M a n i f e s t c o n s t a n t s , which are 70 s y n t a c t i c a l l y s i m i l a r t o upper case i d e n t i f i e r s , a r e d e f i n e d t o have s t r i n g v a l u e s , which are s u b s t i t u t e d i n t o the s o u r c e d u r i n g the f i r s t phase o f c o m p i l a t i o n . In a d d i t i o n t o d e f i n i n g c o n s t a n t s , m a n i f e s t s have been used as p r e p o s i t i o n a l comments. Thus m a n i f e s t s such as OF, IN, FOR, e t c . are n o i s e words i g n o r e d by the c o m p i l e r . They g i v e semantic case c l u e s f o r the arguments t o a f u n c t i o n . For example, .Move( n_words, FROM p t r l , TO p t r 2 ) i s e q u i v a l e n t t o , •Move( n_words, p t r l , p t r 2 ) but h o p e f u l l y i s c l e a r e r . These m a n i f e s t comments appear t o be more h e l p f u l a t the p o i n t o f f u n c t i o n i n v o c a t i o n than the p o i n t o f d e f i n i t i o n . They have been i n c l u d e d p r i m a r i l y as an e x periment i n s t y l e . Zed has an "escape t o asssembly language" f e a t u r e t h a t was used i n the k e r n e l t o execute s p e c i a l machine i n s t r u c t i o n s f o r I/O and c o n t r o l p u r p o s e s . T h i s f e a t u r e g r e a t l y reduces the amount o f assembler language r e q u i r e d , p e r m i t t i n g the use o f f u n c t i o n s w i t h Zed c o n t r o l s t r u c t u r e s and the f u l l power o f the machine. The e f f e c t o f t h i s would be l e s s s i g n i f i c a n t f o r machines, l i k e the PDP-11, t h a t do not have many s p e c i a l i n s t r u c t i o n s . A macro f e a t u r e , s i m i l a r t o t h a t o f the C language, would s i g n i f i c a n t l y improve the e f f i c i e n c y o f the i m p l e m e n t a t i o n w i t h o u t a f f e c t i n g i t s u n d e r s t a n d a b i l i t y . T h i s would be an e x t e n s i o n o f the m a n i f e s t f a c i l i t y , t h a t s u b s t i t u t e d arguments i n t o the t e x t u a l e x p a n s i o n o f a m a n i f e s t (macro). T h i s would be 71 useful, as many functions are very simple, but make the code more readable. 4.1.2 The Host Processor This subsection b r i e f l y describes the Texas Instruments [1976] TI990/10 processor that was used for the test implementation. It concludes with a discussion of the hardware features e s s e n t i a l to the kernel design. The TI990/10 processor i s a byte-addressed 16-bit minicomputer. Its processor state consists of three r e g i s t e r s : a status r e g i s t e r , ST; a program counter, PC; and a workspace pointer, WP. WP points to a memory resident array of 16 general purpose r e g i s t e r s . PC indicates the location of the next i n s t r u c t i o n . ST includes condition codes, a p r i v i l e g e d mode f l a g , a map select f l a g , and an interrupt mask. This small processor state, with memory resident general purpose re g i s t e r s , results in fast context switching. The processor executes in either p r i v i l e g e d or non-privileged mode, as indicated by the mode select b i t of the ST re g i s t e r . Privileged mode i s required to: 1. execute the clock control (ckon, ckof), i d l e , long distance (Ids, ldd), load interrupt mask ( l i m i ) , load map f i l e (lmf), and I/O reset (rset) instructions; 2. access devices connected to the upper portion of the Communications Register Unit, CRU, which includes a l l of the "i n t e r n a l " devices; and 3. change the mode, map, and interrupt mask in the ST r e g i s t e r . 72 Once n o n - p r i v i l e g e d , the mode can o n l y be changed by an i n t e r r u p t , t r a p , or the f r o n t p a n e l h a l t b u t t o n . D e v i c e i n t e r f a c e s a r e o f two t y p e s . Slow d e v i c e s a re connected v i a the Communications R e g i s t e r U n i t , CRU, which can be thought o f as a 4096 b i t r e g i s t e r , w i t h s p e c i f i c b i t s a s s i g n e d t o each d e v i c e . S p e c i a l I/O i n s t r u c t i o n s a c c e s s t h i s r e g i s t e r , e i t h e r one b i t a t a t i m e , or i n groups o f up t o 16 b i t s . The upper p o r t i o n o f the CRU ( b i t a d d r e s s e s >=$E00) can o n l y be a c c e s s e d i n p r i v i l e g e d mode, thus d e v i c e a c c e s s can be r e s t r i c t e d . F a s t d e v i c e s , p a r t i c u l a r l y those employing D i r e c t Memory A c c e s s , DMA, are connected t o the main memory bus and are ac c e s s e d by r e f e r e n c i n g a s p e c i f i c group o f a d d r e s s e s c a l l e d the P e r i p h e r a l C o n t r o l Space, PCS. Access t o the PCS can o n l y be r e s t r i c t e d w h i l e the p r o c e s s o r i s u s i n g mapl. These f a s t d e v i c e s can a c c e s s a l l o f main memory (even the PCS) because t h e i r DMA i s not mapped. D e v i c e s i n t e r r u p t the p r o c e s s o r on one o f 16 l e v e l s . On an i n t e r r u p t , the PC and WP r e g i s t e r s a r e l o a d e d from a s p e c i f i c two word v e c t o r i n low memory, the o l d machine s t a t e i s saved i n the new workspace, p r i v i l e g e d mode and mapO a r e s e l e c t e d , and the i n t e r r u p t mask i s s e t t o p r e v e n t i n t e r r u p t s from the i n t e r r u p t i n g and a l l lower l e v e l s . The TI990/10 i n s t r u c t i o n s e t i n c l u d e s 16 t r a p i n s t r u c t i o n s . These are s i m i l a r t o i n t e r r u p t s , i n t h a t t hey cause c o n t e x t s w i t c h e s as d i c t a t e d by a v e c t o r i n low memory, and s e l e c t 73 p r i v i l e g e d mode and mapO. The p r o c e s s o r ' s 1 6 - b i t b y te a d d r e s s e s a re mapped i n t o the 2 0 - b i t word a d d r e s s e s o f the main memory bus. The mapping u n i t c o n t a i n s t h r e e s e t s o f map r e g i s t e r s : mapO, mapl, and map2. Each map uses 6 words t o s p e c i f y the l i m i t and base o f each o f t h r e e v a r i a b l e s i z e segments. When the mapping f e a t u r e i s e n a b l e d , the p r o c e s s o r maps a l l add r e s s e s w i t h e i t h e r mapO or mapl, as s p e c i f i e d by the map s e l e c t b i t i n the ST r e g i s t e r . Map2 i s not a g e n e r a l purpose map, but i s used e x c l u s i v e l y by the l o n g d i s t a n c e i n s t r u c t i o n s . Maps can be lo a d e d by a s i n g l e p r i v i l e g e d i n s t r u c t i o n , l m f . When mapO i s s e l e c t e d , h i g h a d d r e s s e s are always mapped t o the PCS and t o a ROM which c o n t a i n s a s i m p l e d e b u g g e r / l o a d e r . MapO i s s e l e c t e d by i n t e r r u p t s , t r a p s , and the f r o n t p a n e l h a l t b u t t o n . The hardware f e a t u r e s e s s e n t i a l t o the k e r n e l d e s i g n a re memory mapping and p r i v i l e g e d mode ( i n c l u d i n g t r a p s ) . They are n e c e s s a r y f o r the k e r n e l t o guarantee i t s own i n t e g r i t y . I t i s the o n l y s o f t w a r e i n the system t h a t e x e c u t e s i n p r i v i l e g e d mode and mapO. Thus i t r e t a i n s e x c l u s i v e c o n t r o l o f the mapping hardware, d e v i c e s ( i n c l u d i n g i n t e r r u p t s ) , and p r i v i l e g e d mode ( i n c l u d i n g t r a p s ) . Some o t h e r f e a t u r e s , w h i l e not s t r i c t l y n e c e s s a r y , do enhance the k e r n e l ' s e f f i c i e n c y . These i n c l u d e the r a p i d c o n t e x t s w i t c h i n g a l l o w e d by the memory r e s i d e n t r e g i s t e r s and l o a d map f i l e i n s t r u c t i o n s , and the improved r e a l - t i m e c h a r a c t e r i s t i c s a l l o w e d by i n t e r r u p t masking. The workspace a r c h i t e c t u r e i s a l s o s u i t a b l e f o r s u p p o r t i n g s t a c k o r i e n t e d l a n g u a g e s , such as Zed. 74 The k e r n e l c o u l d however, be p o r t e d t o machines w i t h o u t t h e s e f e a t u r e s w i t h no s t r u c t u r a l changes. 4.2 D e s c r i p t i o n T h i s s e c t i o n d e s c r i b e s the major k e r n e l d a t a s t r u c t u r e s , and each o f the c l a s s e s o f k e r n e l f u n c t i o n s . I t a l s o i n c l u d e s a d i s c u s s i o n o f p r o c e s s s y n c h r o n i z a t i o n s t a t e s . 4.2.1 The K e r n e l Data S t r u c t u r e s The k e r n e l d a t a s t r u c t u r e s a c c e s s i b l e t o a l l k e r n e l f u n c t i o n s i n c l u d e : p r o c e s s d e s c r i p t o r s , d e v i c e d e s c r i p t o r s , ready queues, . A c t i v e , the f r e e PD l i s t , the "To Be A b o r t e d " l i s t , and some m i s c e l l a n e o u s o t h e r s . Each o f these i s d e s c r i b e d below. P r o c e s s D e s c r i p t o r s Much o f the i m p l e m e n t a t i o n o f p r o c e s s e s i n v o l v e s the p r o c e s s d e s c r i p t o r s (PD's). These v e c t o r s are d e f i n e d by the t e m p l a t e .PROCESS_DESCRIPTOR, w i t h the f o l l o w i n g f i e l d s : 1. .ID - a one-word i d e n t i f i c a t i o n code f o r the p r o c e s s . Each i d maps t o a s p e c i f i c p r o c e s s d e s c r i p t o r , v i a i t s inde x f i e l d . An i d i s o n l y v a l i d i f i t i s e q u a l t o the .ID f i e l d o f the PD i t maps t o . An i d can be i n v a l i d f o r one o f t h r e e r e a s o n s . The .ID f i e l d o f the PD i t maps t o i s ones-complemented, i n d i c a t i n g the PD i s c u r r e n t l y unused. The c y c l e number i s i n c o r r e c t , i n d i c a t i n g the i d r e f e r s t o a p r o c e s s t h a t has been d e s t r o y e d a l r e a d y or not y e t c r e a t e d . Or, i t maps t o the f i r s t PD, i n d i c a t i n g t h a t no PD i s a l l o c a t e d f o r t h a t i d . The l a t t e r 7 5 mechanism has not been implemented, and would r e q u i r e some m o d i f i c a t i o n o f the i n i t i a l i z a t i o n o f PD's. I t would however, p e r m i t the a l l o c a t i o n o f space f o r a n o n - i n t e g r a l power o f two number o f PD's. 2 . .PRIORITY - an i n t e g e r from 0 t o the number o f e l i g i b l e p r i o r i t y l e v e l s p l u s one, t h a t d e t e r m i n e s which ready queue the p r o c e s s e n t e r s when i t i s r e a d i e d . Thus the p r i o r i t y o f a p r o c e s s d e t e r m i n e s when i t i s d i s p a t c h e d . 3. .STATE - a word i n d i c a t i n g the s y n c h r o n i z a t i o n s t a t e o f the p r o c e s s . E v e r y p r o c e s s i s i n one o f the s t a t e s : .READY - ready f o r e x e c u t i o n , i . e . not b l o c k e d , .SENDING - b l o c k e d a w a i t i n g i t s message t o be r e c e i v e d , .AWAIT_REPLY - b l o c k e d a w a i t i n g a r e p l y , .AWAIT_MSG - b l o c k e d a w a i t i n g a message t o be s e n t t o i t , or .AWAIT_EVENT - b l o c k e d a w a i t i n g a d e v i c e e v e n t . The low o r d e r b i t s o f the .STATE f i e l d c o n t a i n an i n d e x which i n d i c a t e s the p r o c e s s c u r r e n t l y b e i n g (or l a s t ) s y n c h r o n i z e d w i t h . See the next s u b s e c t i o n f o r a d i s c u s s i o n o f the s y n c h r o n i z a t i o n s t a t e t r a n s i t i o n s . 4. .F, and 5 . .B - p o i n t e r s t h a t d o u b l y l i n k the p r o c e s s i n t o a l i s t or queue. .F p o i n t s t o the PD o f the p r o c e s s c l o s e r t o the t a i l o f the l i s t ( f o r w a r d ) , w h i l e .B p o i n t s t o the PD o f the p r o c e s s c l o s e r t o the head (backward). Each p r o c e s s i s i n a t most one l i s t as d e t e r m i n e d by i t s s t a t e . P o i n t e r s are not d o u b l y - l i n k e d t o f a c i l i t a t e b i d i r e c t i o n a l s e a r c h i n g , but r a t h e r so t h a t the 76 time t o remove known elements from a l i s t i s bounded by a c o n s t a n t . 6. .VIOLATION - a word c o n t a i n i n g a numeric code f o r the e x c e p t i o n which caused the p r o c e s s t o be a r r e s t e d . E x c e p t i o n s are i n d i c a t e d i n t h i s s e p a r a t e f i e l d r a t h e r than i n the message b u f f e r so t h a t no i n f o r m a t i o n i s l o s t from the b u f f e r . 7. .STATUS - a two-word s u b v e c t o r r e p r e s e n t i n g the c a p a b i l i t i e s and s u s c e p t i b i l i t i e s o f the p r o c e s s . Each b i t o f the f i r s t word r e p r e s e n t s the c a p a b i l i t y t o e xecute a r e s t r i c t e d o p e r a t i o n or the s u s c e p t i b i l i t y t o a r e s t r i c t e d o p e r a t i o n . Each b i t o f the second word r e p r e s e n t s the c a p a b i l i t y t o a c c e s s a d e v i c e . The s i z e o f t h i s f i e l d can be a d j u s t e d t o accommodate the number o f r e s t r i c t e d o p e r a t i o n s and d e v i c e s i n the system. 8. .MESSAGE_POINTER - a p o i n t e r t o the 8-word message b u f f e r o f the p r o c e s s , which i s exchanged by the communication o p e r a t i o n s . T h i s i n d i r e c t i o n e l i m i n a t e s the need t o move messages between k e r n e l b u f f e r s . 9. .INITIAL_MESSAGE_BUFFER - an 8-word s u b v e c t o r , which i s the i n i t i a l message b u f f e r o f t h i s p r o c e s s . Because message b u f f e r s are exchanged however, t h i s i s u s u a l l y not the b u f f e r o f t h i s p r o c e s s . Message b u f f e r space i s a l l o c a t e d i n t h i s way because i t i s e a s i e r t o i n i t i a l i z e and i t e l i m i n a t e s a v e c t o r o f message b u f f e r p o i n t e r s t h a t would o n l y be used d u r i n g the i n i t i a l i z a t i o n p r o c e d u r e . 10. .SENDERS - a l i s t header, or two-word s u b v e c t o r c o n s i s t i n g o f p o i n t e r s t o the head and t a i l o f a d o u b l y - l i n k e d 77 l i s t of processes c u r r e n t l y blocked w a i t i n g to send to t h i s p r o c e s s . T h i s l i s t f a c i l i t a t e s implementation of u n s p e c i f i c r e c e i v e s and process d e s t r u c t i o n . 11. .AWAITERS - a l i s t o f the processes c u r r e n t l y awaiting e i t h e r a r e p l y or message from t h i s p r o c e s s . T h i s l i s t f a c i l i t a t e s immediate and complete process d e s t r u c t i o n . That i s , i t allows a l l of the awaiters of destroyed process to be handled as a group. 12. .MACHINE_STATE - a subvector s u f f i c i e n t to s t o r e the processor s t a t e ( i . e . r e g i s t e r s ) of the p r o c e s s . T h i s i n f o r m a t i o n i s loaded i n t o the processor whenever t h i s process i s d i s p a t c h e d . When a process r e l i n q u i s h e s the processor or i s preempted, the r e g i s t e r s are saved here. 13. .MAP - a subvector s p e c i f y i n g the address space of the p r o c e s s . The s i z e and format of maps i s machine dependent. For the TI they are s i x words, s p e c i f y i n g the l i m i t and base f o r each of three segments. The map of a process i s loaded i n t o the mapping hardware whenever i t i s d i s p a t c h e d . Because of the p o t e n t i a l l y l a r g e number of processes (256-1024), the s i z e of process d e s c r i p t o r s (30 words i n c l u d i n g message b u f f e r s ) has been kept to a minimum. Device D e s c r i p t o r s Device d e s c r i p t o r s c o n t a i n the i n f o r m a t i o n the k e r n e l r e q u i r e s about each d e v i c e . When a device i s added to the system, an e n t r y d e s c r i b i n g i t must be added to the k e r n e l . 78 D e v i c e codes map t o d e v i c e d e s c r i p t o r s v i a an index v e c t o r , . P o i n t e r _ t o _ d d . The t e m p l a t e .DEVICE_DESCRIPTOR d e f i n e s the f o l l o w i n g f i e l d s : 1. .DEVICE_CODE - a p o s i t i v e i n t e g e r , l e s s than the number o f d e v i c e s . D e v i c e codes are used by p r o c e s s e s t o r e f e r t o d e v i c e s , and by the k e r n e l t o d e t e r m i n e the d e v i c e d e s c r i p t o r . The m a n i f e s t s d e f i n i n g the d e v i c e codes are i n c l u d e d i n both the k e r n e l and s t a n d a r d p r o c e s s e n v i r o n m e n t s . 2. .ABILITY_FOR - a mask i n d i c a t i n g the s t a t u s b i t c o r r e s p o n d i n g t o the c a p a b i l i t y f o r the d e v i c e 3. .INTERFACE_TYPE - d e t e r m i n e s the method used- t o a c c e s s the d e v i c e ' s c o n t r o l r e g i s t e r s . For the T I , t h i s f i e l d i n d i c a t e s i f the d e v i c e i s a CRU or PCS d e v i c e . 4. .INTERFACE_ADDRESS - i n d i c a t e s the s p e c i f i c l o c a t i o n o f t h i s d e v i c e ' s r e g i s t e r s ( i . e . the CRU base a d d r e s s , or the PCS a d d r e s s ) . 5. .HANDLER - i n d i c a t e s the p r o c e s s ( i f any) a w a i t i n g an event from the d e v i c e . There are a l s o a d d i t i o n a l f i e l d s t h a t are used f o r s p e c i f i c d e v i c e t y p e s . Ready Queues For each p r i o r i t y l e v e l t h e r e i s an e n t r y i n the .Ready_queue v e c t o r , t h a t p o i n t s t o a l i s t o f ready p r o c e s s e s w i t h t h a t p r i o r i t y . T h i s s t r u c t u r e i s searc h e d by .Block whenever a p r o c e s s b l o c k s , which happens when a p r o c e s s sends a message, a w a i t s a message, or a w a i t s an e v e n t . The p e n u l t i m a t e ready queue never has any p r o c e s s e s i n i t , r a t h e r i t i s i n i t i a l i z e d so as t o s t o p the s e a r c h i n .Block b e f o r e i t g e t s t o the i n e l i g i b l e l e v e l . Thus p r o c e s s e s are never d i s p a t c h e d from the i n e l i g i b l e l e v e l . T h i s n e v e r - e m p t y - l e v e l t r i c k moves the c o m p l e t i o n t e s t out o f the s e a r c h l o o p i n the .Block f u n c t i o n . . A c t i v e . A c t i v e i s a p o i n t e r t o the PD o f the a c t i v e p r o c e s s . I t i s an i m p l i c i t argument t o many o f the k e r n e l o p e r a t i o n s . For example, .Send_msg( i d ) sends a message from the a c t i v e p r o c e s s t o the p r o c e s s s p e c i f i e d by i d . I t i s a l s o used t o check c a p a b i l i t i e s f o r r e s t r i c t e d o p e r a t i o n s , and t o i n d i c a t e where t o save the p r o c e s s o r ' s r e g i s t e r s when a p r o c e s s i s preempted, and l o s e s the p r o c e s s o r . . A c t i v e i s a c t u a l l y an e x t e n s i o n o f the p r o c e s s o r s t a t e , as i t must be changed whenever a p r o c e s s i s d i s p a t c h e d . When the k e r n e l i s i n the i d l e s t a t e ( i . e . t h e r e a r e no p r o c e s s e s t o d i s p a t c h ) , i t p o i n t s t o the f i r s t PD, which i s o t h e r w i s e unused. T h i s l a s t t r i c k , a l l o w s the . D i s p a t c h r o u t i n e t o always save the machine r e g i s t e r s , even i f t h e r e i s no a c t i v e p r o c e s s , which saves a t e s t . F r e e PD L i s t The f r e e PD l i s t c o n t a i n s a l l u n a l l o c a t e d PD's. I n i t i a l l y a l l PD's, e x c e p t the f i r s t p r o c e s s ' s , are on t h i s l i s t . When a p r o c e s s i s c r e a t e d i t i s a l l o c a t e d a PD from t h i s l i s t , and when i t i s d e s t r o y e d i t s PD i s r e t u r n e d t o t h i s l i s t . C u r r e n t l y , f r e e PD's are r e a l l o c a t e d on a " f i r s t come f i r s t s e r v e d " b a s i s . I f the r e c y c l i n g o f i d ' s was o f c o n c e r n , t h i s l i s t c o u l d be o r d e r e d 80 by c y c l e number, thus s t a l l i n g the r e c y c l i n g . "To Be A b o r t e d " L i s t When a p r o c e s s i s d e s t r o y e d , the p r o c e s s e s b l o c k e d on i t are added t o t h i s l i s t . They are removed from i t by the . N e x t _ v i o l a t o r o p e r a t i o n . A l l p r o c e s s e s i n t h i s l i s t a r e i n one of the s t a t e s : .SENDING, .AWAIT_REPLY, or .AWAIT_MSG. M i s c e l l a n e o u s . K e r n e l _ e n t r i e s i s a t a b l e o f k e r n e l e n t r y p o i n t s used by the i n t e r f a c e f u n c t i o n s . The k e r n e l has i t s own s t a c k which i s d i s t i n c t from the s t a c k s o f a l l p r o c e s s e s . . I n t e r r u p t _ m a s k i s a t a b l e used t o a s s o c i a t e p r i o r i t y l e v e l s w i t h i n t e r r u p t masks. When a p r o c e s s i s a c t i v e , i t s p r i o r i t y l e v e l d e t e r m i n e s the p r o c e s s o r i n t e r r u p t mask. Other e x t e r n a l s used as p a r t o f the d e v i c e i m p l e m e n t a t i o n i n c l u d e : the k e r n e l - m a i n t a i n e d time v e c t o r and t i m e r c o u n t , t e r m i n a l o u t p u t b u f f e r s , a s p u r i o u s i n t e r r u p t c o u n t , and a copy o f the f r o n t p a n e l d i s p l a y r e g i s t e r . The number o f 1024-byte b l o c k s o f main memory i s m a i n t a i n e d i n .Mem_size. 4.2.2 The K e r n e l F u n c t i o n s As d e p i c t e d i n f i g u r e 2, t h e r e a re s i x groups o f k e r n e l f u n c t i o n modules: the o p e r a t i o n , i n t e r f a c e , i n t e r r u p t , i n i t i a l i z a t i o n , s u p p o r t , and debugger f u n c t i o n s . Each o f these groups i s b r i e f l y d e s c r i b e d . The O p e r a t i o n F u n c t i o n s 81 Each o p e r a t i o n f u n c t i o n implements the l o g i c o f one k e r n e l o p e r a t i o n . As w i t h the o p e r a t i o n s , these f u n c t i o n s c l a s s i f y i n t o i n t e r p r o c e s s communication, p r o c e s s management, and d e v i c e a b s t r a c t i o n g roups. I n t e r p r o c e s s communication i s based upon the s y n c h r o n i z a t i o n s t a t e s d e s c r i b e d i n s e c t i o n 4.2.3. P r o c e s s management i n v o l v e s a c c e s s i n g d a t a i n the PD's, and m a n i p u l a t i n g p r o c e s s l i s t s . The d e v i c e a b s t r a c t i o n f u n c t i o n s are somewhat more c o m p l i c a t e d , r e q u i r i n g i n t e r a c t i o n w i t h the i n t e r r u p t f u n c t i o n s . The c h a r a c t e r - o r i e n t e d f u n c t i o n s i n p a r t i c u l a r , share b u f f e r s w i t h the i n t e r r u p t f u n c t i o n s . The o p e r a t i o n f u n c t i o n s o n l y c a l l s u p p o r t f u n c t i o n s . The I n t e r f a c e F u n c t i o n s The i n t e r f a c e f u n c t i o n s pass c o n t r o l from the i n v o k i n g p r o c e s s t o the d e s i r e d o p e r a t i o n f u n c t i o n . There are t h r e e groups o f i n t e r f a c e f u n c t i o n s . The c o s m e t i c f u n c t i o n s p r o v i d e u s e f u l c o m b i n a t i o n s o f k e r n e l o p e r a t i o n s . They are a l s o used t o i n s u l a t e p r o c e s s e s from changes i n the o p e r a t i o n s . The dummy k e r n e l f u n c t i o n s are used t o s e t u p the arguments t o the k e r n e l o p e r a t i o n s and execute the t r a p i n s t r u c t i o n s t h a t pass c o n t r o l t o the k e r n e l . Both o f these groups o f f u n c t i o n s a c t u a l l y r e s i d e i n each p r o c e s s ' s address space. That i s , t h e y are l i n k e d i n w i t h the code f o r each p r o c e s s . Thus they are not r e a l l y p a r t o f the k e r n e l a t a l l . They are i n c l u d e d however, because they are v e r y c l o s e l y r e l a t e d t o i t . The t h i r d group, the t r a p f u n c t i o n s are i n the k e r n e l ' s address space. When a t r a p i n s t r u c t i o n i s e x e c u t e d , the p r o c e s s o r passes c o n t r o l t o a t r a p f u n c t i o n through the t r a p (or xop) v e c t o r . I t then moves the arguments 82 from the p r o c e s s ' s s t a c k t o the k e r n e l ' s s t a c k and branches through the k e r n e l e n t r y t a b l e t o the a p p r o p r i a t e o p e r a t i o n f u n c t i o n . C u r r e n t l y o n l y one o f the TT990/10's 16 t r a p s i s used because t h i s i s the most p o r t a b l e d e s i g n . The overhead f o r common o p e r a t i o n s c o u l d be reduced however, i f they used i n d i v i d u a l t r a p s . The I n t e r r u p t F u n c t i o n s The i n t e r r u p t f u n c t i o n s i n c l u d e : an assembler module ( . I n t e r r u p t _ r o u t i n e s ) t h a t s p e c i f i e s the i n t e r r u p t v e c t o r s ; the r o u t i n e s t h a t are i n v o k e d on each i n t e r r u p t ; and s u p p o r t r o u t i n e s t h a t are s p e c i f i c t o i n t e r r u p t h a n d l i n g . The . I n t e r r u p t _ r o u t i n e s module t u r n s o f f the i n t e r r u p t s c o m p l e t e l y , and t r a n s f e r s c o n t r o l t o the f u n c t i o n f o r the s p e c i f i c i n t e r r u p t . Whenever a new i n t e r r u p t i s added, the v e c t o r must be changed. Because the . I n t e r r u p t _ r o u t i n e s module t u r n s o f f i n t e r r u p t s , the o t h e r f u n c t i o n s can be w r i t t e n i n Zed, and some a r e , but o f t e n assembler i s more r e a s o n a b l e because o f the need t o use s p e c i a l machine i n s t r u c t i o n s . The f u n c t i o n f o r each i n t e r r u p t depends g r e a t l y on the d e v i c e t h a t causes the i n t e r r u p t . That i s , t h e s e f u n c t i o n s are v e r y d e v i c e - (and i n t e r f a c e - ) dependent. The c l o c k i n t e r r u p t f u n c t i o n ( . R T C _ i n t e r r u p t ) keeps a count o f the i n t e r r u p t s i n the k e r n e l ' s three-word time v e c t o r (.Time_vec), m a i n t a i n s the t i m e r (.Timer) and d i s p a t c h e s the p r o c e s s a w a i t i n g the t i m e r when i t e x p i r e s . The c h a r a c t e r d e v i c e i n t e r r u p t f u n c t i o n s are by f a r the most c o m p l i c a t e d . They have t o d e t e r m i n e the n a t u r e o f the i n t e r r u p t (read r e q u e s t , w r i t e r e q u e s t , or o t h e r ) , move the c h a r a c t e r 83 between the i n t e r f a c e and the k e r n e l ' s d e v i c e b u f f e r s , and d i s p a t c h a w a i t i n g p r o c e s s e s under the c o r r e c t c o n d i t i o n s . The f u n c t i o n s t h a t respond t o i n t e r n a l i n t e r r u p t s , which o c c u r as a r e s u l t o f e r r o r s or power f a i l u r e s , a r e a l s o h i g h l y machine dependent. When a new d e v i c e i s added t o the system the i n t e r r u p t v e c t o r has t o be changed. I f a new d e v i c e r e q u i r e s a s p e c i a l i n t e r r u p t f u n c t i o n , i t has t o be w r i t t e n and added t o the k e r n e l . To d a t e , s p e c i a l i n t e r r u p t f u n c t i o n s have been w r i t t e n f o r : the r e a l time c l o c k , and two typ e s o f t e r m i n a l i n t e r f a c e s (EIA and CIM). The Support F u n c t i o n s The s u p p o r t f u n c t i o n s i n c l u d e common k e r n e l d a t a s t r u c t u r e o p e r a t i o n s such a s : m a n i p u l a t i n g d o u b l y l i n k e d l i s t s , c h a nging the s t a t e o f a p r o c e s s , d i s p a t c h i n g a p r o c e s s , e t c . These are o f t e n used t o make the c a l l i n g f u n c t i o n s c l e a r e r . The e f f i c i e n c y o f the k e r n e l c o u l d be i n c r e a s e d by i n c o r p o r a t i n g some o f these f u n c t i o n s d i r e c t l y i n t o the c a l l e r s . The I n i t i a l i z a t i o n F u n c t i o n s The i n i t i a l i z a t i o n f u n c t i o n s a re used t o se t u p the k e r n e l d a t a s t r u c t u r e s , and c r e a t e the f i r s t p r o c e s s . They assume t h a t c o m p i l e r i n i t i a l i z a t i o n s are c o r r e c t . T h i s i s r e a s o n a b l e f o r the c u r r e n t s i t u a t i o n where the k e r n e l i s r e l o a d e d from d i s k b e f o r e i t i s s t a r t e d . I f however, the k e r n e l was r e s i d e n t i n ROM and d i d not have t o be r e l o a d e d , the c o m p i l e r i n i t i a l i z a t i o n o f changeable v a r i a b l e s c o u l d not be t r u s t e d . Thus, i f the k e r n e l was put i n t o ROM, the i n i t i a l i z a t i o n f u n c t i o n s would have t o be 84 m o d i f i e d . T h i s would not r e q u i r e major r e s t r u c t u r i n g , however. The Debugger F u n c t i o n s There are two d i f f e r e n t s e t s o f debugger f u n c t i o n s . The f i r s t i s the ROM d e b u g g e r / l o a d e r , which i s used t o l o a d the k e r n e l and p r o v i d e s a b s o l u t e debugging f a c i l i t i e s s i m i l a r t o those p r o v i d e d by most minicomputer f r o n t p a n e l s . These are c o n s i d e r e d p a r t o f the k e r n e l because they execute i n p r i v i l e g e d mode, use mapO, and the r e s t o f the k e r n e l depends on them, a t l e a s t t o g e t g o i n g . They are r e a l l y q u i t e s e p a r a t e as they are not l i n k e d or loa d e d w i t h the r e s t o f the k e r n e l . The second type o f debugger f u n c t i o n s c o n s t i t u t e a s y m b o l i c debugger t h a t may o p t i o n a l l y be loade d w i t h the k e r n e l . T h i s debugger i s u s e f u l f o r k e r n e l development. 4.2.3 S y n c h r o n i z a t i o n S t a t e s The s y n c h r o n i z a t i o n s t a t e o f a p r o c e s s i n d i c a t e s i f i t i s ready t o e x e c u t e , or b l o c k e d w a i t i n g t o s y n c h r o n i z e w i t h another p r o c e s s or a d e v i c e . E v e r y p r o c e s s i s i n one o f the f i v e s t a t e s : 1. .READY - ready f o r e x e c u t i o n , i . e . not b l o c k e d ; 2. .SENDING - b l o c k e d a w a i t i n g i t s message t o be r e c e i v e d ; 3. .AWAIT_REPLY - b l o c k e d a w a i t i n g a r e p l y ; 4. .AWAIT_MSG - b l o c k e d a w a i t i n g a message t o be s e n t t o i t ; 5. .AWAIT_EVENT - b l o c k e d a w a i t i n g a d e v i c e t o s i g n a l an ev e n t . P r o c e s s s y n c h r o n i z a t i o n i s based upon these s t a t e s . That i s , the communication o p e r a t i o n s are implemented by c a u s i n g changes i n the s y n c h r o n i z a t i o n s t a t e s o f the p r o c e s s e s i n v o l v e d . F i g u r e 3 shows the s t a t e t r a n s i t i o n s and i n d i c a t e s which o p e r a t i o n s cause 85 them. FIGURE 13*. SYNCHRONIZATION STATE DIAGRAM Each p r o c e s s can be i n one l i s t o f p r o c e s s e s , as d i c t a t e d by i t s s y n c h r o n i z a t i o n s t a t e . These l i s t s , and the c o n d i t i o n s f o r a p r o c e s s t o be i n the l i s t a r e : 1. .Ready_queue - c o r r e s p o n d i n g t o the p r o c e s s ' s .PRIORITY, i f i n the .READY s t a t e . 2. .SENDERS - l i s t a s s o c i a t e d w i t h the p r o c e s s b e i n g s e n t t o , i f i n the .SENDING s t a t e . 3. .AWAITERS - o f the p r o c e s s b e i n g a w a i t e d , i f i n the .AWAIT REPLY or .AWAIT MSG s t a t e s . (A p r o c e s s a w a i t i n g any 86 message i s i n the .AWAITERS l i s t o f the f i r s t pd.) 4. No l i s t - i f i n the .AWAIT_EVENT s t a t e . 5. . F r e e _ p d _ l i s t - i f the pd i s not b e i n g used. 6 . . T o _ b e _ a r r e s t e d _ l i s t - i f the p r o c e s s i t was b l o c k e d on has been d e s t r o y e d . The s t a t e o f the p r o c e s s i s i r r e l e v a n t t o membership i n e i t h e r o f these l a s t two l i s t s . The s u p p o r t f u n c t i o n , . S e t _ s t a t e , not o n l y changes a p r o c e s s ' s s t a t e , but a l s o i t s l i s t membership. 4.3 T e s t System S e v e r a l s i m p l e systems have been w r i t t e n t o t e s t the k e r n e l . The most comprehensive i n c l u d e s f o u r p r o c e s s e s r e s i d i n g i n t h r e e d i s t i n c t address s p a c e s . The r o o t p r o c e s s , c r e a t e d by the k e r n e l , c r e a t e s and i n i t i a l i z e s the o t h e r p r o c e s s e s . I t i s d r i v e n by the . R e s i d e n t _ p r o c e s s _ t a b l e i n i t s address space. A l l o f the p r o c e s s e s i t c r e a t e s are assumed t o be i n memory when i t g e t s c o n t r o l . The c l o c k p r o p r i e t o r and i t s event n o t i f i e r share an address space. These two p r o c e s s e s p r o v i d e the complete t i m i n g f a c i l i t i e s f o r a g e n e r a l purpose system such as Thoth. The u s e r _ a g e n t i s a dummy p r o c e s s , i n t h a t i t o n l y g i v e s the "u s e r " the a b i l i t y t o send messages. I t does not p r o v i d e a n i c e user i n t e r f a c e . T h i s f a c i l i t y i s u s e f u l t o t e s t the message-passing o p e r a t i o n s and t o send r e q u e s t s t o p r o p r i e t o r p r o c e s s e s . 87 The t e s t system i s d e f i c i e n t i n a number o f a r e a s . The most prominent o f these i s t h a t t h e r e a re no f a c i l i t i e s f o r u s i n g the d i s k d r i v e s . I n f a c t , the k e r n e l o p e r a t i o n s f o r d i s k I/O have not even been w r i t t e n . The o t h e r d e v i c e o p e r a t i o n s have undergone i n s u f f i c i e n t t e s t i n g . The t e s t system does not i n c l u d e any f a c i l i t i e s f o r c r e a t i n g p r o c e s s e s , or memory management, a l t h o u g h t h e s e o p e r a t i o n s are used by the r o o t p r o c e s s . P r o c e s s d e s t r u c t i o n has a l s o not been t e s t e d . 4 . 4 Summary The i m p l e m e n t a t i o n o f the k e r n e l c o n s i s t s o f a s e t o f f u n c t i o n and d a t a modules, most o f which were w r i t t e n i n the i n t e r m e d i a t e - l e v e l language Zed, which i s s i m i l a r t o the C language. Only s t r u c t u r e d c o n t r o l c o n s t r u c t s were used, d e s p i t e the l o w - l e v e l n a t u r e o f the k e r n e l . Zed's "escape t o assembler language" f e a t u r e s i g n i f i c a n t l y reduced the number o f assembler modules r e q u i r e d . A macro f a c i l i t y , s i m i l a r t o C's, would have improved e f f i c i e n c y w i t h o u t l o s s o f p e r s p i c u i t y . A Texas I n s t r u m e n t s TI990/10 1 6 - b i t minicomputer was used f o r the t e s t i m p l e m e n t a t i o n . I t s memory mapping hardware and p r i v i l e g e d mode ( i n c l u d i n g t r a p mechanism) were e s s e n t i a l f o r the k e r n e l t o guarantee i t s own i n t e g r i t y . The p r o c e s s o r ' s workspace r e g i s t e r a r c h i t e c t u r e , w i t h memory r e s i d e n t g e n e r a l r e g i s t e r s , a l l o w e d r a p i d c o n t e x t s w i t c h i n g w h i c h , a l t h o u g h not e s s e n t i a l , d i d improve the e f f i c i e n c y o f the d e s i g n . S i n g l e i n s t r u c t i o n s f o r l o a d i n g address maps a l s o c o n t r i b u t e d t o the r a p i d c o n t e x t s w i t c h i n g . 88 The major k e r n e l d a t a s t r u c t u r e s i n c l u d e : p r o c e s s d e s c r i p t o r s , which r e p r e s e n t the a t t r i b u t e s o f (and o t h e r i n f o r m a t i o n about) p r o c e s s e s ; d e v i c e d e s c r i p t o r s , which c o n t a i n the i n f o r m a t i o n about the c o n f i g u r a t i o n o f d e v i c e s n e c e s s a r y f o r the k e r n e l t o a c c e s s the d e v i c e s ; and, the ready queues, which are l i s t s o f ready p r o c e s s e s (one l i s t per p r i o r i t y l e v e l ) . The k e r n e l f u n c t i o n s c l a s s i f y i n t o the f o l l o w i n g s i x gro u p s : the o p e r a t i o n f u n c t i o n s , which c o r r e s p o n d on a one-to-one b a s i s w i t h the k e r n e l o p e r a t i o n s ; the i n t e r f a c e f u n c t i o n s , which pass c o n t r o l from p r o c e s s e s t o the o p e r a t i o n f u n c t i o n s ; the i n t e r r u p t f u n c t i o n s , which a re in v o k e d i n response t o hardware i n t e r r u p t s ; the s u p p o r t f u n c t i o n s , which p r o v i d e l o w - l e v e l o p e r a t i o n s (such as l i s t m a n i p u l a t i o n ) t o the o t h e r k e r n e l f u n c t i o n s ; the i n i t i a l i z a t i o n f u n c t i o n s , which i n i t i a l i z e the k e r n e l d a t a s t r u c t u r e s and the f i r s t p r o c e s s ; and the debugger f u n c t i o n s , which i n c l u d e a l o w - l e v e l ROM-resident d e b u g g e r / l o a d e r and a s y m b o l i c debugger which may be o p t i o n a l l y l i n k e d i n t o the k e r n e l . The i m p l e m e n t a t i o n o f i n t e r p r o c e s s communication i s based upon the s y n c h r o n i z a t i o n s t a t e s o f p r o c e s s e s . Each p r o c e s s i s i n one o f the f o l l o w i n g f i v e s t a t e s : .READY, i f i t i s ready f o r e x e c u t i o n , i . e . not b l o c k e d ; .SENDING, i f i t i s b l o c k e d w a i t i n g f o r i t s message t o be r e c e i v e d ; .AWAIT_REPLY, i f i t i s b l o c k e d a w a i t i n g a r e p l y ; .AWAIT_MSG, i f i t i s a w a i t i n g a message t o be s e n t t o i t ; o r , .AWAIT_EVENT, i f i t i s b l o c k e d a w a i t i n g a d e v i c e e v e n t . 8 9 The p o s s i b l e t r a n s i t i o n s , and t h e i r c a u s e s , a r e shown i n the s y n c h r o n i z a t i o n s t a t e d iagram, f i g u r e 3. These s t a t e s a l s o i n d i c a t e which p r o c e s s l i s t a p r o c e s s i s i n . For example, p r o c e s s e s i n the ready s t a t e are i n one o f the ready queues. A complete o p e r a t i n g system has not y e t been implemented, but a t e s t system has been deve l o p e d f o r e x p e r i m e n t a t i o n . T h i s system c o n s i s t s o f f o u r p r o c e s s e s r e s i d i n g i n t h r e e d i f f e r e n t a ddress s p a c e s . I t has been used t o t e s t the i n t e r p r o c e s s communication and most o f the p r o c e s s management o p e r a t i o n s . P r o c e s s d e s t r u c t i o n has not been t e s t e d . Some o f the d e v i c e o p e r a t i o n s have been t e s t e d , a l t h o u g h o n l y i n a d e q u a t e l y . The k e r n e l has been implemented t o a degree s u f f i c i e n t t o i n d i c a t e the v i a b i l i t y o f many o f the t e c h n i q u e s , however i t r e q u i r e s more work b e f o r e i t w i l l be u s e a b l e . 90 Chapter 5 C o n c l u s i o n s T h i s t h e s i s has e x p l o r e d t e c h n i q u e s f o r d e s i g n i n g v e r i f i a b l e o p e r a t i n g systems. I t i s based on the e x p e r i e n c e o f d e s i g n i n g and implementing a multiprogramming k e r n e l i n t e n d e d t o p r o v i d e a f o u n d a t i o n f o r message-based, m u l t i p r o c e s s - s t r u c t u r e d o p e r a t i n g systems. P a r t i c u l a r emphasis has been p l a c e d on r e d u c i n g the i n t e r d e p e n d e n c i e s o f system components, i n an e f f o r t t o improve v e r i f i a b i l i t y . To a s i g n i f i c a n t degree, t h i s e f f o r t has been s u c c e s s f u l . The f o l l o w i n g s e c t i o n expands upon t h i s c o n c l u s i o n and draws a t t e n t i o n t o s i g n i f i c a n t a s p e c t s o f t h i s r e s e a r c h . The c h a p t e r ends w i t h a d i s c u s s i o n o f a number o f a r e a s t h a t c o u l d b e n e f i t from f u r t h e r e x p l o r a t i o n . 5.1 C o n c l u s i o n s Three u n u s u a l f e a t u r e s o f the k e r n e l improve the v e r i f i a b i l i t y o f both the k e r n e l and the systems i t s u p p o r t s . 1. The system p r o c e s s e s can be d e s i g n e d t o e x h i b i t a c y c l i c d e p e n d e n c i e s , and hence be i n d i v i d u a l l y v e r i f i a b l e . 2. The k e r n e l does not depend upon any p r o c e s s e s f o r i t s c o r r e c t o p e r a t i o n , hence i t can a l s o be v e r i f i e d i n d e p e n d e n t l y . 3. The k e r n e l o p e r a t i o n s are i n d i v i s i b l e , t h u s the k e r n e l e x e c u t e s s e q u e n t i a l l y and d e t e r m i n i s t i c a l l y , a l l o w i n g the use o f s t a n d a r d program p r o v i n g t e c h n i q u e s f o r i t s v e r i f i c a t i o n . Two f e a t u r e s o f the environment were i n s t r u m e n t a l i n a l l o w i n g 91 systems t o e x h i b i t a c y c l i c dependency g r a p h s . Senders a w a i t r e p l i e s , thus p r o p r i e t o r p r o c e s s e s need not depend upon t h e i r r e q u e s t o r s . V e r y few i n t e r p r o c e s s communication mechanisms have t h i s p r o p e r t y . S e c o n d l y , the c a p a b i l i t y / s u s c e p t i b i l i t y p r o t e c t i o n scheme e l i m i n a t e s system p r o c e s s i n t e r d e p e n d e n c i e s which a s i m p l e " p r i v i l e g e d - m o d e " scheme cannot. I n d i v i d u a l c a p a b i l i t i e s f o r p r o c e s s management and d e v i c e m a n i p u l a t i o n o p e r a t i o n s must be p r o v i d e d on a p e r - p r o c e s s b a s i s t o e l i m i n a t e i n d i r e c t d e p e n d e n c i e s . A new mechanism, which we c a l l s u s c e p t i b i l i t i e s , was n e c e s s a r y t o make i t p o s s i b l e t o p r e v e n t p o w e r f u l system p r o c e s s e s from d i s r u p t i n g each o t h e r . D i r e c t memory a c c e s s (DMA) by d e v i c e s i s another p o t e n t i a l s o u r c e o f i n t e r p r o c e s s d e p e n d e n c i e s . Because o f t h i s , the k e r n e l m o n i t o r s a l l DMA a c t i v i t y and l o c k s the i n v o l v e d p r o c e s s i n t o memory. T h i s k i n d o f dependency i s not v e r y w e l l u n d e r s t o o d , and the k e r n e l may have t o be m o d i f i e d s l i g h t l y t o reduce i t s e f f e c t . T h i s s h o u l d be d e l a y e d u n t i l the memory management component o f the system i s d e s i g n e d , and the e f f e c t s are more f u l l y u n d e r s t o o d . The p r o c e s s management o p e r a t i o n s are the key t o the independence o f the k e r n e l . They a l l o w p r o c e s s e s t o p e r f o r m most o f the p r o c e s s management f u n c t i o n s , w i t h o u t the k e r n e l l o s i n g i t s independence. D e v i c e m a n i p u l a t i o n o p e r a t i o n s were a l s o n e c e s s a r y t o ensure t h a t d e v i c e s cannot a f f e c t the k e r n e l (e.g. v i a DMA). Two f e a t u r e s o f the hardware n e c e s s a r y t o a c h i e v e the independence o f the k e r n e l i n c l u d e : memory mapping hardware, t o 92 p r o t e c t address s p a c e s ; and p r i v i l e g e d mode, i n c l u d i n g a t r a p mechanism, t o p e r m i t c o n t r o l l e d use o f d e v i c e s and the mapping hardware. These f a c i l i t i e s a r e , however, a v a i l a b l e on any machine t h a t s u p p o r t s a p r o t e c t e d o p e r a t i n g system. I f p r i v i l e g e d mode i s the o n l y way t o r e s t r i c t a c c e s s t o d e v i c e s , the k e r n e l must a b s t r a c t a l l d e v i c e s , because i t i s the o n l y s o f t w a r e t h a t e x e c u t e s i n p r i v i l e g e d mode. C a r e f u l c o n s i d e r a t i o n o f the s e m a n t i c s o f the k e r n e l o p e r a t i o n s was r e q u i r e d t o ensure t h a t they c o u l d be implemented t o be i n d i v i s i b l e w i t h e x e c u t i o n times bounded by a c o n s t a n t . P r o c e s s d e s t r u c t i o n was the most d i f f i c u l t o p e r a t i o n t o do t h i s f o r , as i t i n v o l v e s an a r b i t r a r y number o f p r o c e s s e s on each d e s t r u c t i o n . Because o f t h i s , the k e r n e l m a i n t a i n s l i s t s o f the p r o c e s s e s b l o c k e d on each p r o c e s s . A l t h o u g h somewhat e x p e n s i v e , t h i s a l l o w s p r o c e s s d e s t r u c t i o n t o be i n d i v i s i b l e . The s e p a r a t i o n o f d a t a movement and s y n c h r o n i z a t i o n by the p r o c e s s communication o p e r a t i o n s i s a l s o m o t i v a t e d by the i n d i v i s i b i l i t y c r i t e r i o n . Some o f the i m p o r t a n t c o n c l u s i o n s from the j u s t i f i c a t i o n i n c h a p t e r 3 w a r r a n t r e p e a t i n g h e r e . The i n t e r p r o c e s s communication p r i m i t i v e s were s e l e c t e d f o r a number o f r e a s o n s . They are s u f f i c i e n t t o s o l v e the "mutual e x c l u s i o n " problem. They are easy t o un d e r s t a n d and c o n v e n i e n t t o use. They a l l o w the system t o be s t r u c t u r e d w i t h an a c y c l i c dependency graph. And, they a re e f f i c i e n t . The r e s t r i c t i o n o f the p r o c e s s c r e a t i o n and d e s t r u c t i o n o p e r a t i o n s e l i m i n a t e s the n e c e s s i t y f o r the k e r n e l t o m a i n t a i n a r e c o r d o f the c r e a t o r and descendants o f each p r o c e s s . Most s i m i l a r k e r n e l s have m a i n t a i n e d such a p r o c e s s h i e r a r c h y . I t i s not n e c e s s a r y f o r the k e r n e l t o p r o v i d e a h i g h - l e v e l a b s t r a c t i o n o f memory. A memory manager p r o c e s s can a b s t r a c t memory w i t h the k e r n e l o p e r a t i o n f o r s e t t i n g p r o c e s s address maps. Thus memory management by the k e r n e l reduces t o the r e l a t i v e l y s i m p l e t a s k o f c h e c k i n g p r o c e s s maps as they are s e t , t o ensure they do not o v e r l a p w i t h the k e r n e l . The k e r n e l ' s two p r o c e s s o r a l l o c a t i o n mechanisms p r o v i d e both f a s t and f l e x i b l e s c h e d u l i n g . The m i c r o d i s p a t c h i n g s t r a t e g y , implemented e n t i r e l y by the k e r n e l , a l l o w s the time f o r d e t e r m i n a t i o n o f the p r o c e s s t o d i s p a t c h t o be bounded by a c o n s t a n t . The . S e t _ p r i o r i t y o p e r a t i o n a l l o w s a s c h e d u l e r p r o c e s s t o implement any macro a l l o c a t i o n s t r a t e g y d e s i r e d . The a r r e s t mechanism used by the k e r n e l t o ha n d l e e x c e p t i o n s a l l o w s the system c o n s i d e r a b l e f l e x i b i l i t y . D e s p i t e t h i s , however, e x c e p t i o n h a n d l i n g i s a weak a r e a o f the k e r n e l d e s i g n . I t does not seem t o f i t n i c e l y w i t h the r e s t o f the d e s i g n , nor are a l l e x c e p t i o n s handled c o n s i s t e n t l y . T h i s a r e a d e s e r v e s f u r t h e r i n v e s t i g a t i o n . D e v ice a b s t r a c t i o n i s a d i f f i c u l t and p o o r l y u n d e r s t o o d a r e a o f machine and system d e s i g n . We found i t n e c e s s a r y t o e x p l o r e two approaches t o i t . The f i r s t i s t o p r o v i d e g e n e r a l - p u r p o s e d e v i c e o p e r a t i o n s i n o r d e r t o reduce the k e r n e l ' s dependence upon d e v i c e i n t e r f a c e s and c o n f i g u r a t i o n . These g e n e r a l - p u r p o s e 94 o p e r a t i o n s s p e c i f y the e f f e c t upon the d e v i c e ' s c o n t r o l r e g i s t e r s , not the a c t i o n o f the d e v i c e . The second approach i s t o p r o v i d e s p e c i a l o p e r a t i o n s f o r each o f t h r e e g e n e r i c c l a s s e s o f d e v i c e s ( t i m i n g , c h a r a c t e r , and b l o c k ) . T h i s i s a much h i g h e r l e v e l o f a b s t r a c t i o n . The k e r n e l extends the hardware t i m i n g f a c i l i t i e s from a s i m p l e p e r i o d i c i n t e r r u p t , t o a time v e c t o r r e p r e s e n t i n g the c u r r e n t time and a s e t t a b l e t i m e r . T h i s a l l o w s a more e f f i c i e n t and e l e g a n t i m p l e m e n t a t i o n o f the t i m i n g f a c i l i t i e s which the system p r o v i d e s . T h i s i s an example o f a minor i n c r e a s e i n k e r n e l c o m p l e x i t y s i g n i f i c a n t l y i m p r o v i n g the e f f i c i e n c y and e l e g a n c e o f the systems i t s u p p o r t s . C h a r a c t e r d e v i c e s cause most o f the d e v i c e dependency problems the system d e s i g n e r f a c e s . I n t e r f a c e d e t a i l s v a r y w i d e l y , even among d e v i c e s from a s i n g l e m a n u f a c t u r e r . Systems tend t o c o n t a i n a number o f t h e s e d e v i c e s and they are r e c o n f i g u r e d o f t e n . A s i g n f i c a n t p r o p o r t i o n o f the p r o c e s s o r time i s spent s e r v i c i n g them, because they are h e a v i l y used. These a s p e c t s put c o n f l i c t i n g p r e s s u r e s on the system d e s i g n e r . The v a r i a t i o n i n i n t e r f a c e d e t a i l s (and even f u n c t i o n a l i t y ) c o u p l e d w i t h the d e s i r e f o r a s t a b l e k e r n e l w i t h s i m p l e s e m a n t i c s i n d i c a t e s t h a t t h e s e d e t a i l s s h o u l d be h a n d l e d by p r o c e s s e s . B u t , t h i s i s l e s s e f f i c i e n t , which i s s i g n i f i c a n t because o f heavy use. We have compromised. The k e r n e l p r o v i d e s e f f i c i e n t , d e v i c e - i n d e p e n d e n t o p e r a t i o n s f o r r e a d i n g and w r i t i n g c h a r a c t e r s , but o n l y g e n e r a l purpose o p e r a t i o n s f o r m a n i p u l a t i n g the more e s o t e r i c f e a t u r e s o f the d e v i c e s . L i k e a l l compromises, 95 t h i s one i s not p a r t i c u l a r l y s a t i s f y i n g . The s e m a n t i c s o f the b l o c k d e v i c e o p e r a t i o n s have been s p e c i f i e d , b e a r i n g i n mind the dependency problems a s s o c i a t e d w i t h d i r e c t memory ac c e s s (DMA). To date they have been n e i t h e r implemented nor t e s t e d , but t h e r e does not appear t o be any problem d o i n g so. Much work remains t o a c h i e v e the u l t i m a t e g o a l o f a v e r i f i e d f u l l - f u n c t i o n o p e r a t i n g system. However, the independent k e r n e l / s y s t e m - p r o c e s s approach seems s u f f i c i e n t l y p r o m i s i n g t o e x p l o r e f u r t h e r . 5 . 2 S u g g e s t i o n s f o r F u t u r e Research Three immediate e x t e n s i o n s t o t h i s r e s e a r c h i n c l u d e : v e r i f i c a t i o n o f the k e r n e l ; c o n s t r u c t i o n o f a s e t o f system p r o c e s s e s which implement a complete o p e r a t i n g system; and, v e r i f i c a t i o n o f these system p r o c e s s e s . These e x t e n s i o n s would s u b s t a n t i a t e our c l a i m s t h a t the k e r n e l i s v e r i f i a b l e and s u i t a b l e f o r s u p p o r t i n g v e r i f i a b l e o p e r a t i n g systems. They would a l s o be i n t e r e s t i n g e x p e r i m e n t s i n t h e i r own r i g h t , as they would r e s u l t i n a complete v e r i f i e d o p e r a t i n g system. I n a d d i t i o n t o these e x t e n s i o n s , t h r e e a r e a s o f the k e r n e l d e s i g n w a r r a n t f u r t h e r i n v e s t i g a t i o n . These are e x c e p t i o n h a n d l i n g , d e v i c e a b s t r a c t i o n , and memory management. The i s s u e s o f e x c e p t i o n h a n d l i n g need t o be c o n s i d e r e d from a more g l o b a l p o i n t o f view than we have adopted. What k i n d s o f e x c e p t i o n s o c c u r ? What are r e a s o n a b l e a c t i o n s f o r the system t o 96 t a k e when they do o c c u r ? Once these q u e s t i o n s a re answered, i t w i l l be more o b v i o u s what e x c e p t i o n h a n d l i n g s u p p o r t the k e r n e l s h o u l d p r o v i d e . The k e r n e l ' s a b s t r a c t i o n o f d e v i c e s i s ad hoc. The problem i s to d e t e r m i n e what l e v e l o f d e v i c e a b s t r a c t i o n the k e r n e l s h o u l d p r o v i d e , g i v e n v e r i f i a b i l i t y , c o n f i g u r a b i l i t y , p o r t a b i l i t y , and e f f i c i e n c y c o n s i d e r a t i o n s . Improved hardware f a c i l i t i e s t h a t can be a b s t r a c t e d s i m p l y and e a s i l y would be i n t e r e s t i n g t o e x p l o r e . For example, mapping DMA and e n f o r c i n g s t a n d a r d mechanisms f o r i n t e r r u p t h a n d l i n g would h e l p c o n s i d e r a b l y . The k e r n e l ' s a b s t r a c t i o n o f memory i s s u f f i c i e n t , but needs t o be reworked i n the c o n t e x t o f a h i g h e r - l e v e l memory a b s t r a c t i o n . T h i s would l e a d t o k e r n e l f a c i l i t i e s more s u i t a b l e f o r the d e s i r e d a b s t r a c t i o n . I n t h i s way, i t might even be p o s s i b l e f o r the k e r n e l t o p r o v i d e a machine-independent a b s t r a c t i o n o f memory. T h i s approach c o u l d a l s o p o i n t t o b e t t e r d e s i g n s f o r memory management hardware. I t would be i n t e r e s t i n g t o e x p l o r e t o what e x t e n t the k e r n e l c o u l d be m i c r o - c o d e d , and what e f f i c i e n c y g a i n s c o u l d be made. A l s o o f i n t e r e s t would be i n v e s t i g a t i o n o f machine a r c h i t e c t u r e s t h a t had b u i l t - i n knowledge o f m u l t i p l e p r o c e s s e s . That i s , the machine c o u l d i n c l u d e s p e c i a l r e g i s t e r s i n d i c a t i n g the a c t i v e p r o c e s s and/or i m p o r t a n t a t t r i b u t e s o f the a c t i v e p r o c e s s . A p o t e n t i a l l y a t t r a c t i v e r e s e a r c h d i r e c t i o n , i s the e x p l o r a t i o n o f the k e r n e l as a mechanism f o r c o o r d i n a t i n g m u l t i p l e p r o c e s s o r s . The b a s i c i d e a here i s f o r m u l t i p l e "closely coupled" (same memory) processors to share the kernel with a hardware lock. That i s , there would be only one copy of the kernel code and data structures which would be shared by a l l of the processors, only one of which could be in kernel mode at a time. In thi s way i t might be possible for the kernel to be the only software aware of how many processors were in the system. In conclusion, i t seems that there are many interesting issues to pursue in the area of v e r i f i a b l e operating system design. The kernel/system-process approach s t i l l appears f r u i t f u l . There i s much work to be done before we have systems that are proven to function c o r r e c t l y , never f a i l , and always do what i s expected of them. 98 References B a s k e t t , F., Howard, J.H. and Montague, J.T. Task communication i n DEMOS. Proc. 6th Symp. on Operating System P r i n c i p l e s , A.CM., New York7~T977. B r i n c h Hansen, P. RC4000 Software Multiprogramming System. A/S Regnecentralen, Copenhagen, A p r i l 1969. . The nucleus o f a multiprogramming system. Comm. A.CM. TJ7 4 ( A p r i l 1970). C h e r i t o n , D.R. M u l t i - p r o c e s s s t r u c t u r i n g and the Thoth o p e r a t i n g system. T e c h n i c a l Report 79-5, U n i v e r s i t y o f B r i t i s h Columbia, Vancouver, 1979a. (based on Ph.D. t h e s i s U n i v e r s i t y of Waterloo, 1978). . Designing an o p e r a t i n g system to be v e r i f i a b l e . T e c h n i c a l Report 79-9, U n i v e r s i t y o f B r i t i s h Columbia, 1979b. C h e r i t o n , D.R., Malcolm, M.A., Melen, L.S. and Sager, G.R. Thoth, a p o r t a b l e r e a l - t i m e o p e r a t i n g system. Comm. A.CM. 22, 1 (Jan. 1979c). C h e r i t o n , D.R., and Steeves, P.J. The Zed r e f e r e n c e manual. T e c h n i c a l Manual 79-2, U n i v e r s i t y o f B r i t i s h Columbia, 1979d. C l i f f o r d , J . , and Montague, J . DEMOS k e r n e l f u n c t i o n a l d e s c r i p t i o n . Los Alamos S c i e n t i f i c L a b oratory, 1978. D i j k s t r a , E.W. Co-operating s e q u e n t i a l p r o c e s s e s . In Programming  Languages, F. Genuys, Ed., Academic P r e s s , New York, 1968a. . The s t r u c t u r e of the "THE" multiprogramming system. Comm. A.CM. 11, 5 (May 1968b) . Lycklama, H., and Bayer, D.L. The MERT o p e r a t i n g system. The  B e l l System T e c h n i c a l J o u r n a l , 57, 6 (July-August 1978). Popek, G.J., and K l i n e , C.S. A v e r i f i a b l e p r o t e c t i o n system. Proc. 6th Symp. on Operating System P r i n c i p l e s , A.CM., New York, T977. R i t c h i e , D.M. and Thompson, K. The UNIX timesharing system. Comm. A.CM. 17, 7 (Ju l y 1974). Schroeder, M.D., C l a r k , D.D., and S a l t z e r , J.H. The M u l t i c s k e r n e l design p r o j e c t . Proc. 6th Symp. on Operating System  P r i n c i p l e s , A.CM., New York, 1977. Texas Instruments Incorporated. 990 Computer Family Systems Handbook. No. 945250-9701, A u s t i n , Texas 1976. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items