KERNEL DEVICE MANAGEMENT USING A HIGH LEVEL I/O PROTOCOL by FREDERICK DIXON SAMPLE .Sc., The U n i v e r s i t y of B r i t i s h Columbia, 198 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES THE DEPARTMENT OF COMPUTER SCIENCE We accept t h i s t h e s i s as conforming to the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l 1984 (cT) F r e d e r i c k Dixon Sample, 1984 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y a v a i l a b l e for reference and study. I further agree that permission for extensive copying of t h i s thesis f o r scholarly purposes may be granted by the head of my department or by h i s or her representatives. I t i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of (^.ovwpuiAer OCAd / V C C The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Abstract T h i s t h e s i s examines t h e a d v a n t a g e s and d i s a d v a n t a g e s o f u s i n g a h i g h l e v e l I/O p r o t o c o l f o r d e v i c e management. I t c o v e r s t h e i m p l e m e n t a t i o n o f t h i s f o r m o f d e v i c e management as an a d d i t i o n t o t h e V e r e x o p e r a t i n g s y s t e m , t h e p r o b l e m s e n c o u n t e r e d , and t h e i r s o l u t i o n s . T a b l e Of C o n t e n t s A b s t r a c t i i T a b l e o f C o n t e n t s i i i L i s t o f . F i g u r e s v Acknowledgements 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 s . . . 1 1.2 M o t i v a t i o n . . . 2 2. R e s e a r c h B a c k g r o u n d 5 2.1 I n t e r p r o c e s s C o m m u n i c a t i o n . . . 5 2.2 I n p u t / O u t p u t P r o t o c o l s 7 2.3 V e r e x D e v i c e Management. . . 8 2.4 U n i x D e v i c e Management 9 3. D e s i g n 12 3.1 D e s i g n C r i t e r i a 12 3.2 E n v i r o n m e n t 14 3.3 D e s i g n 15 3.3.1 S e r v i c e s 15 3.3.1.1 D e v i c e C r e a t i o n . . 15 3.3.1.2 D e v i c e Removal 17 3.3.1.3 P r o t e c t i o n 17 3.3.2 I n t e r f a c e 19 3.3.2.1 C o m m u n i c a t i o n 19 3.3.2.2 I/O P r o t o c o l 22 3.3.3 I n t e r n a l D e s i g n . 22 3.3.3.1 D a t a S t r u c t u r e s 23 s 3.3.3.2 R e q u e s t D r i v e n R o u t i n e s 24 i i i 3.3.3.3 I n t e r r u p t D r i v e n Routines 25 3.3.3.4 U t i l i t y Routines 25 4. Environment 28 4.1 Verex Process Management & Communication . . 28 4.2 The Verex I/O P r o t o c o l 30 4.3 Verex I/O Serv e r s 33 5. Implementation 35 6. R e s u l t s 38 7. C o n c l u s i o n s 40 Appendix 1. K e r n e l Device Implementation G u i d e l i n e . . 41 Appendix 2. Example Device D r i v e r 49 B i b l i o g r a p h y 55 i v L i s t of F i g u r e s 2.1 Uniform Access P r o t o c o l 8 3.1 Process Device Communication 21 A l . l Device S t a t e V e c t o r 43 v Acknowledgements I w o u l d l i k e t o thank t h e many p e o p l e who c o n t r i b u t e d i n one way o r a n o t h e r t o t h i s t h e s i s : D r . D a v i d C h e r i t o n , who p r o p o s e d t h e o r i g i n a l i d e a and s u p e r v i s e d much o f t h e i m p l e m e n t a t i o n o f t h e work; t h e o t h e r g r a d u a t e s t u d e n t s w o r k i n g w i t h V e r e x , who gave a d v i c e and i d e a s ; G e r a l d N e u f e l d , who s u p e r v i s e d t h e w r i t i n g and was v e r y p a t i e n t ; and my f a m i l y and f r i e n d s , who p r o v i d e d e n c o u r a g e m e n t . v i 1 C h a p t e r 1 I n t r o d u c t i o n The s u b j e c t o f t h i s t h e s i s i s t h e i n v e s t i g a t i o n o f t h e a d v a n t a g e s and d i s a d v a n t a g e s o f managing d e v i c e c o m m u n i c a t i o n u s i n g a h i g h l e v e l d a t a c o m m u n i c a t i o n p r o t o c o l , w i t h i n t h e k e r n e l o f a message b a s e d o p e r a t i n g s y s t e m . Of p a r t i c u l a r c o n c e r n a r e t h e e f f e c t s on o p e r a t i n g s y s t e m p o r t a b i l i t y , f l e x i b i l i t y , and e f f i c i e n c y . The r e s e a r c h work i n v o l v e d i n t h i s t h e s i s i n c l u d e s t h e d e s i g n and i m p l e m e n t a t i o n o f d e v i c e h a n d l i n g r o u t i n e s u s i n g t h i s m o d e l . T h i s r e s e a r c h was done i n c o n j u n c t i o n w i t h r e l a t e d r e s e a r c h i n t o d a t a c o m m u n i c a t i o n p r o t o c o l s a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a D e p a r t m e n t o f Computer S c i e n c e . A p r o t o c o l o f s u f f i c i e n t power and f l e x i b i l i t y t o h a n d l e a wide v a r i e t y o f i n p u t and o u t p u t t a s k s was d e v e l o p e d , and a s u b r o u t i n e p a c k a g e was w r i t t e n t o p r o v i d e c o n v e n i e n t a c c e s s t o i n p u t and o u t p u t s e r v i c e s t h a t c o n f o r m e d t o t h e p r o t o c o l [10]. 1.1 O b j e c t i v e s The aim o f t h i s t h e s i s i s t o examine t h e p o s s i b i l i t y o f u s i n g a h i g h l e v e l I/O i n t e r f a c e f o r c o m m u n i c a t i n g w i t h p e r i p h e r a l d e v i c e s . The e x p e c t e d a d v a n t a g e s o f t h i s a p p r o a c h t o d e v i c e h a n d l i n g a r e dynamic r e c o n f i g u r a b i l i t y , more 2 e f f i c i e n t c o m m u n i c a t i o n w i t h d e v i c e s , and t h e c o n f i n e m e n t o f p r i v i l e g e d I/O i n s t r u c t i o n s t o t h e k e r n e l . A l s o , more o f t h e m a c h i n e d e p e n d a n c y i n t h e s y s t e m i s c o n f i n e d t o t h e k e r n e l . A p o s s i b l e p r o b l e m i s t h e i n c r e a s e i n t h e amount o f code t h a t i s c o n t a i n e d i n t h e k e r n e l . D e t e r m i n i n g t h e s e v e r i t y o f t h i s p r o b l e m i s one o f t h e o b j e c t i v e s o f t h i s r e s e a r c h . A n o t h e r o b j e c t i v e o f t h i s t h e s i s i s t o d e s c r i b e t h e i m p l e m e n t a t i o n o f t h i s f o r m o f d e v i c e management as an a d d i t i o n t o V e r e x [ 1 ] , and t o r e p o r t on t h e p r o b l e m s e n c o u n t e r e d and t h e i r s o l u t i o n s . 1.2 M o t i v a t i o n One o f t h e p r i m e m o t i v a t i o n s f o r u s i n g an I/O p r o t o c o l i s t h e improvement o f d e v i c e management. C u r r e n t schemes a r e u n s t r u c t u r e d and o f t e n i n e f f i c i e n t . The i n e f f i c i e n c y o f t h e s e schemes c a n s e v e r e l y l i m i t r e a l t i m e a p p l i c a t i o n s due t o t h e i n a b i l i t y t o g u a r a n t e e t h a t i n t e r r u p t s w i l l be s e r v i c e d w i t h i n a c e r t a i n t i m e i n t e r v a l . I m p l e m e n t i n g t h e p r o t o c o l a t t h e k e r n e l l e v e l r a t h e r t h a n h a v i n g a d e v i c e h a n d l e r p r o c e s s e n a b l e s d i r e c t c o m m u n i c a t i o n between u s e r p r o c e s s e s and d e v i c e s , t h u s r e d u c i n g t h e message p a s s i n g o v e r h e a d . The I/O p r o t o c o l message t o t h e d e v i c e , as i t i s i n t e r c e p t e d i n t h e k e r n e l , i s r e c e i v e d i m m e d i a t e l y , e l i m i n a t i n g t h e p r o c e s s s w i t c h i n g o v e r h e a d t h a t w o u l d o t h e r w i s e be r e q u i r e d t o s e n d a message and r e c e i v e a r e p l y . 3 Verex device handling, l a r g e l y inherited from Thoth [4], involves awakening a process to handle most interrupts. This i s co s t l y , so costly i n fact that the maximum rate that a terminal can send characters to the cpu without any characters being missed i s only 1200 baud. Many modern i n t e l l i g e n t terminals can transmit programmed strings or screen readouts to the cpu, usually at the same rate as characters are received from the cpu. To take advantage of this f a c i l i t y on Verex, currently the terminals must be set to a rate of 1200 baud, a severe l i m i t a t i o n on their performance. The Verex I/O protocol reads and writes in blocks, enabling a kernel implementation of thi s protocol to buffer characters. Hence a kernel l e v e l implementation of this protocol need not awaken a process for each interrupt. As the blocks can vary in s i z e , the block I/O allows single character I/O as well. V e r i f i a b i l i t y i s one of the objectives of Verex. On many machines, I/O operations are p r i v i l e g e d . Limiting the code which must run in p r i v i l e g e d mode to the kernel improves the v e r i f i a b i l i t y of the operating system, as the amount of damage that can be caused by a malfunctioning process i s much less i f i t i s not running in p r i v i l e g e d mode. In p a r t i c u l a r , devices that access memory d i r e c t l y can overwrite kernel code, so the kernel must supervise a l l such devices to ensure i t s i n t e g r i t y . The o r i g i n a l work done on v e r i f i a b i l i t y with Verex aimed to exclude I/O operations from the kernel, so that the kernel would not have to be r e - v e r i f i e d each time a device handler was added to the 4 system. Supervision of d i r e c t memory access transfers requires knowledge of device function, hence excluding device dependancy from the kernel i s impossible. Confining I/O operations to kernel code i s also the major step i n i s o l a t i n g the kernel from the rest of the operating system, which currently runs in the same address space as the kernel. Above the kernel l e v e l , the kernel device management system appears as a server process. This i s in accord with th e o r e t i c a l models which regard devices as external processes [ 6 ] . The kernel device management system extends Verex interprocess communication to these external processes. 5 Chapter 2 Research Background Although device management software forms an important part of a l l operating systems, l i t t l e has been written about i t s design. Perhaps this i s due to the hardware dependant nature of device software. Brinch Hansen [ 6 ] referred to devices as "hardware processes", yet l i t t l e work has been done in extending interprocess communication to devices. 2.1 Interprocess Communication Interprocess communication has increased s t e a d i l y in sophistication with the development of modern operating systems. Early operating systems provided very l i t t l e in the way of communication between processes, as a l l but the lowest l e v e l system code was r e s t r i c t e d to one process per program. As the idea of multiple processes per program became more popular, the methods of interprocess communication increased in power to meet the demand. Interprocess communication serves two main purposes, data transmission and synchronization. The simplest form of data transmission is through the use of shared memory. Use of shared memory must be coupled with a method of synchronization, to avoid c r i t i c a l section problems. Semaphores [11], are the most basic form of synchronization. Message passing provides both synchronization and data 6 transmission. Shared memory requires the processes sharing memory have overlapping address spaces, which often incurs either protection d i f f i c u l t i e s or high computational overheads. The simplest method i s to have the processes run i n the same address space, but t h i s l i m i t s a l l communicating processes to one address space, and leaves each process dependant on the correct behavior of a l l other processes. Less dangerous methods either incur large computational overheads or require s p e c i a l hardware [4]. The use of message passing for interprocess communication has been growing as new operating systems are developed. Message passing i s a set of primitives for the exchange of packets of data, c a l l e d messages, between processes. Message passing schemes can be divided into two categories: synchronous and asynchronous. Asynchronous message passing allows a process to proceed with execution after sending a message, whereas synchronous message passing requires the sender to wait u n t i l the receiver of the message has received i t and sent a reply. The advantage of synchronous message passing i s i t s simpler implementation, as message buffers need not be dynamically allocated in the kernel, resulting in greater r e l i a b i l i t y , since there i s no danger of running out of message buffers [4]. Its disadvantage i s the reduction of concurrency. However, concurrency can be achieved by the creation of more processes. 7 Verex message passin g uses s m a l l , f i x e d l e n g t h messages which are passed synchronously. The message p a s s i n g p r i m i t i v e s c o n s i s t of a r o u t i n e to send a message, a r o u t i n e to r e c e i v e a message, and a r o u t i n e to r e p l y to a message. A process sending a message b l o c k s u n t i l t h a t message has been r e p l i e d t o , or the process sent to no longer e x i s t s . A process may check to see i f a message has a r r i v e d f o r i t , or i t may block u n t i l a message a r r i v e s . A process may await a message from a p a r t i c u l a r p r o c e s s , or from any p r o c e s s . The r e p l y p r i m i t i v e passes a message to a process that has sent to the r e p l y i n g p r o c e s s , and unblocks the sending p r o c e s s . 2.2 Input/Output P r o t o c o l s Input/Output p r o t o c o l s are the s u b j e c t of much re s e a r c h c u r r e n t l y with the g r e a t expansion of the use of computers f o r communication. Standard p r o t o c o l s i n c r e a s e the p o r t a b i l i t y and f l e x i b i l i t y o f the programs using them, as t h e i r range of p o s s i b l e a p p l i c a t i o n i s i n c r e a s e d . Madnick [12] d e t a i l s the advantages of having a uniform p r e s e n t a t i o n of a f i l e system. H i s arguments are e a s i l y extended to p r o v i d i n g a uniform i n t e r f a c e to a l l types of input and output. Most modern o p e r a t i n g systems p r o v i d e a uniform f i l e / d e v i c e a b s t r a c t i o n at the top l e v e l . 8 Application Program Standard I/O Access protocol V V V V Pipes Disk F i l e s Devices Other Services Figure 2.1 — Uniform Access Protocol Cheriton [10] has developed a universal f i l e access protocol using message passing. This protocol i s based on the client/server model, where a c l i e n t process makes I/O requests to a server process which manages the p a r t i c u l a r f i l e abstraction. As a l l servers coinmunicate using the same protocol, programs using the protocol can be used with a wide variety of f i l e / d e v i c e abstractions. 2.3 Verex Device Management The device management philosophy i n the o r i g i n a l Verex i s to keep the code in the kernel to a minimum, and have processes handle the majority of the work. Hence the device management interface to the kernel i s low l e v e l . 9 The k e r n e l p r o v i d e s one d e v i c e i n t e r f a c e f u n c t i o n , . A w a i t _ i n t e r r u p t . A process uses t h i s k e r n e l o p e r a t i o n to await an i n t e r r u p t at a p a r t i c u l a r i n t e r r u p t l e v e l . When an i n t e r r u p t occurs at that l e v e l , the i n t e r r u p t r o u t i n e f o r that i n t e r r u p t l e v e l i s invoked, some c a l c u l a t i o n s are performed, and the process awaiting the i n t e r r u p t i s unblocked. A process i s not n e c e s s a r i l y unblocked each time an i n t e r r u p t i s r e c e i v e d . In t h i s manner, i n t e r r u p t s that request simple a c t i o n can be handled by the i n t e r r u p t r o u t i n e . A f t e r awaiting an i n t e r r u p t and being unblocked, the handler process then d e a l s d i r e c t l y with the hardware. Response to frequent i n t e r r u p t s i s hampered by the l i m i t e d r a t e at which processes can be unblocked and run. T h i s problem i s avoided by p u t t i n g code i n t o the i n t e r r u p t r o u t i n e s to b u f f e r incoming data, and adding k e r n e l o p e r a t i o n s to read the d a t a . The problem with t h i s method i s that each f a s t d e v i c e r e q u i r e s i t s own d e v i c e input/output k e r n e l o p e r a t i o n s . 2.4 Unix Device Management Unix d i v i d e s d e v i c e s i n t o two c l a s s e s , block and c h a r a c t e r . Block d e v i c e s must be random access , and must use 512 byte b l o c k s . Character d e v i c e s are d e v i c e s t h a t do not f i t i n t o the "block" c l a s s . Devices are i d e n t i f i e d by a s i x t e e n b i t number, which i d e n t i f i e s the d e v i c e d r i v e r , and the p a r t i c u l a r d e v i c e handled by t h a t d r i v e r [ 5 ] . 10 Device d r i v e r software c o n s i s t s of the d e v i c e ' s i n t e r r u p t r o u t i n e , and i n t e r f a c e procedures. Device d r i v e r r o u t i n e s are accessed by using the upper e i g h t b i t s of the dev i c e i d e n t i f i e r to index a t a b l e of de v i c e f u n c t i o n s . Character and block type d e v i c e s use separate t a b l e s . Every device has an open and a c l o s e f u n c t i o n . Character d e v i c e s each have i n a d d i t i o n a read r o u t i n e , a w r i t e r o u t i n e , and a s p e c i a l f u n c t i o n r o u t i n e . Block d e v i c e s have a " s t r a t e g y " r o u t i n e which perform read, w r i t e , and c o n t r o l f u n c t i o n s i n a manner a p p r o p r i a t e to the d e v i c e . Communication between the i n t e r r u p t - d r i v e n p a r t and the procedure c a l l e d p a r t of the d e v i c e d r i v e r uses common v a r i a b l e s , f l a g s , and queues. S y n c h r o n i z a t i o n i s accomplished through the use of i n t e r r u p t p r i o r i t y l e v e l s , and the use of sleep and wakeup r o u t i n e s which allow the procedure to cause the c a l l i n g process to block u n t i l i t i s unblocked by the i n t e r r u p t r o u t i n e . Unix maintains a p o o l of b u f f e r s and s u p p l i e s software f o r t h e i r management. These b u f f e r s are used by the block type d e v i c e s to keep c o p i e s of f r e q u e n t l y used b l o c k s i n memory. A l l block type d e v i c e s have chains of b u f f e r s that are managed by the b u f f e r management r o u t i n e s . Many r o u t i n e s are p r o v i d e d to implement the d i f f e r e n t ways i n which b u f f e r e d i n p u t and output can be done. Each b u f f e r c o n t a i n s i n f o r m a t i o n on i t s s t a t u s and the i n f o r m a t i o n i t c o n t a i n s . Unix a l s o c o n t a i n s some p r o v i s i o n s f o r t r a n s f e r s d i r e c t l y from d e v i c e s i n t o a users address space with 11 non-standard block siz e s . These devices are set up to be character devices which have their own buffers. A user program c a l l s standard functions to perform I/O. These functions access the system f i l e table, which, among other information, contains the o f f s e t into the f i l e at which the next I/O w i l l take place, and a pointer to the f i l e ' s inode. The inode contains the device i d e n t i f i e r , which i s then used to access the appropriate device driver routine. Unix device management provides many of the features desired in device management systems, but i s limited by several problems. The device access protocol i s f a i r l y uniform across a l l devices; a l l devices appear as f i l e s to the users, even to the point of having a p a r t i c u l a r location within the f i l e system structure. The f i l e access protocol is quite l i m i t e d , however, which means that some control functions are d i f f i c u l t to make available at the application l e v e l . The lack of suitable interprocess communication forces device handlers to be within the kernel of the operating system, which causes the kernel to grow quite large. The device handling structure within the kernel i s quite r e s t r i c t i v e , which can cause d i f f i c u l t i e s in writing device drivers for devices which do not match Unix's idea of how devices should behave. 12 Chapter 3 Design 3.1 Design C r i t e r i a The aim of t h i s r e s e a r c h i s to examine the use of h i g h - l e v e l p r o t o c o l s f o r d e v i c e management, hence the primary d e s i g n o b j e c t i v e i s to c r e a t e a d e v i c e management system which communicates with processes using a h i g h - l e v e l I/O p r o t o c o l . Devices should appear to be f i l e s implemented by a standard I/O s e r v e r , so t h a t a d e v i c e can be used i n t e r c h a n g a b l y with another type of " f i l e " . Another design aim i s to p r o v i d e a s t r u c t u r e d method of implementing a d e v i c e d r i v e r , so that adding a new device i s a simpler p r o c e s s . The de v i c e implementor should not be r e q u i r e d to be an expert on the o p e r a t i n g system i n g e n e r a l . T h i s enhances the p o r t a b i l i t y of the o p e r a t i n g system, as p o r t i n g to a new machine r e q u i r e s new de v i c e d r i v e r s to be w r i t t e n . The d e v i c e i n t e r f a c e s should l o s e l i t t l e of the f l e x i b i l i t y p r o v i d e d by l o w - l e v e l i n t e r f a c e s . The implementation of a de v i c e d r i v e r f o r an unusual d e v i c e should not r e q u i r e the implementor to w r i t e complicated code to o u t w i t , or "program around", the de v i c e management system. T h i s r e q u i r e s that the I/O p r o t o c o l chosen be s u f f i c i e n t l y f l e x i b l e to accomodate wi d e l y v a r y i n g types of 13 i n p u t , output, and c o n t r o l i n f o r m a t i o n . For example, i n the o r i g i n a l Verex o p e r a t i n g system, the simple p r i m i t i v e s f o r dev i c e management were inadequate to c o n t r o l network i n t e r f a c e s , f o r c i n g the implementors to add k e r n e l o p e r a t i o n s to communicate with them. Real time response and e f f i c i e n c y should not be l o s t i n a c h i e v i n g the above aims. An i n e f f i c i e n t d e v i c e management system i s not l i k e l y to be used, e s p e c i a l l y i f i t cannot g i v e adequate response to the i n t e r r u p t s of the d e v i c e s i t manages. For example, device managment schemes which i n v o l v e s c h e d u l i n g a process to s e r v i c e an i n t e r r u p t , a time consuming o p e r a t i o n , cannot s e r v i c e high frequency i n t e r r u p t s . Many o p e r a t i n g systems r e q u i r e e i t h e r r e g e n e r a t i o n or r e c o m p i l a t i o n when the hardware c o n f i g u r a t i o n of the system i s changed. Hardware c o n f i g u r a t i o n , as i t i s used here, d e f i n e s the type of de v i c e s and i n t e r f a c e s connected to the computer, and t h e i r arrangement i n I/O address space. T h i s device management system w i l l attempt to e l i m i n a t e the n e c e s s i t y of r e c o m p i l a t i o n or r e g e n e r a t i o n . Changing the hardware c o n f i g u r a t i o n w i l l o n l y r e q u i r e e d i t i n g a setup f i l e , as long as no de v i c e f o r which d e v i c e d r i v e r s do not e x i s t are added. T h i s c o n t r i b u t e s to the r e l i a b i l i t y of the system, as compilers change with time, and there i s no guarantee t h a t a recompiled v e r s i o n of a system w i l l behave c o r r e c t l y [2]. M o d i f i c a t i o n of a setup f i l e i s a l s o a much si m p l e r , f a s t e r , process than r e c o m p i l a t i o n . T h i s method of 4 14 reconfiguration also saves disc space in some circumstances, as operating systems which require recompilation to change hardware configuration require that a separate core image of the system be kept on f i l e for each d i f f e r e n t hardware configuration in which the system may be run. An example of this i s Data General's MRDOS operating system, where the number and type of each device i s spec i f i e d to a system configuration program, which generates a core image which w i l l only run with the given hardware configuration. Some classes of devices have a number of d i f f e r e n t modes in which they can operate, which require d i f f e r e n t interface and interrupt routines. An example of thi s i s some terminal/network interfaces which can operate synchronously or asynchronously. I t i s advantageous not to need to reboot when a change of mode i s desired. This "dynamic r e c o n f i g u r a b i l i t y " i s c l o s e l y related to the "regeneration-free" reconfiguration described above. 3.2 Environment The device management system described here i s designed to work with kernel based multi-process operating systems with message based interprocess communication. The reason for t h i s r e s t r i c t i o n i s that a major element in the design is the extension of interprocess communication to devices. Systems with primitive interprocess communication would gain l i t t l e i n having i t extended to devices. The system i s p a r t i c u l a r l y aimed at those systems that use a message based 15 I/O p r o t o c o l of the c l i e n t and server type, as they have subroutines designed to take advantage of high l e v e l communication with devices. Some aspects may be t r a n s f e r r a b l e to other types of operating systems. 3.3 Design The design of the device management system i s broken i n t o three p a r t s : the s e r v i c e s provided by the system, the i n t e r f a c e between processes and the system, and the i n t e r n a l f u n c t i o n of the system. 3.3.1 Se r v i c e s The p r o t o c o l used d e f i n e s , to a c e r t a i n extent, the nature of the s e r v i c e s provided by the device management system. Most p r o t o c o l s , however, allow a f a i r degree of f l e x i b l i t y i n the exact operations performed by requests. The d e s i r e d behavior of the system has been defined above i n the design c r i t e r i a . This s e c t i o n w i l l d e t a i l the f u n c t i o n a l i t y r e q uired to achieve the d e s i r e d behavior. 3.3.1.1 Device C r e a t i o n In order to achieve a k e r n e l that i s independant of the hardware c o n f i g u r a t i o n of i t s host computer, a l l hardware c o n f i g u r a t i o n dependant information must be removed from the 16 kernel. Devices, therefore must be i n i t i a l i z e d and activated by requests from processes. In general, these device creation requests w i l l come from the system processes that use the p a r t i c u l a r devices, for example, the f i l e server w i l l issue the device creation requests for i t s disk drives and other devices. As no hardware configuration dependant information i s contained in the kernel, the relevant information must be contained in the device creation request. This information w i l l consist of such things as interrupt vector addresses, device control register addresses, and other information about devices which change with hardware configuration. The exact nature of the information w i l l depend on the hardware I/O structure of the host computer. Device i n i t i a l i z a t i o n and a c t i v a t i o n i s a device dependant operation. To allow the necessary f l e x i b i l i t y to implement a wide range of device types, each type of device should have i t s own device creation routine. Selection of the appropriate routine when a device i s created must depend on an indica t i o n of device type in the creation request. A simple protocol i s required to map device types onto i d e n t i f i e r s , which can be implemented as a set of constants shared by the source code of the device management system and the source code of' the system processes using the devices. 17 3.3.1.2 D e v i c e Removal Dynamic r e c o n f i g u r a b i l i t y r e q u i r e s a method o f r e l e a s i n g d e v i c e s so t h a t t h e i r mode o f o p e r a t i o n c a n be c h a n g e d . When a d e v i c e i s r e l e a s e d , t h e d e v i c e management s y s t e m r e l e a s e s i t s d a t a s t r u c t u r e s and r e s e r v e d h ardware (see P r o t e c t i o n , b e l o w ) , and t e r m i n a t e s p e n d i n g I/O on t h e r e l e a s e d d e v i c e . The d e v i c e r e m o v a l w i l l n o t a l w a y s be prompted by a r e q u e s t f r o m a p r o c e s s , as a p r o c e s s may be d e s t r o y e d o r a b o r t , i n w h i c h c a s e any d e v i c e s i t owns s h o u l d be removed. T h i s i m p l i e s t h a t t h e d e v i c e management s y s t e m must d e t e c t p r o c e s s d e s t r u c t i o n . P r o c e s s d e s t r u c t i o n d e t e c t i o n c a n t a k e t h e f o r m o f p e r i o d i c c h e c k i n g f o r e x i s t a n c e , o r n o t i f i c a t i o n upon d e s t r u c t i o n . N o t i f i c a t i o n upon d e s t r u c t i o n i s more d i f f i c u l t t o i m p l e m e n t , b u t i s more r e l i a b l e as t h e d e v i c e i s removed as t h e p r o c e s s i s d e s t r o y e d , n o t sometime l a t e r . B e c a u s e o f i t s g r e a t e r r e l i a b l i t y , t h e n o t i f i c a t i o n method was c h o s e n f o r i m p l e m e n t a t i o n . 3.3.1.3 P r o t e c t i o n One o f t h e b a s i c a s s u m p t i o n s when d e s i g n i n g k e r n e l s o f t w a r e i s t h a t p r o c e s s e s a r e i n h e r e n t l y u n r e l i a b l e , and p o s s i b l y m a l i c i o u s . F o r t h i s r e a s o n , m a n i p u l a t i o n o f d e v i c e s must be s u b j e c t e d t o c h e c k s and r e s t r i c t i o n s . One a r e a t h a t must be p r o t e c t e d i s i n t e r r u p t v e c t o r 18 l o c a t i o n s . I f a device i s c r e a t e d with the same i n t e r r u p t v e c t o r l o c a t i o n as a d e v i c e t h a t i s a l r e a d y a c t i v e , the new i n t e r r u p t r o u t i n e would end up s e r v i c i n g i n t e r r u p t s from both the o l d d e v i c e and the new d e v i c e . T h i s would l i k e l y cause c o n f u s i o n , hence the v e c t o r l o c a t i o n s must be checked at d e v i ce c r e a t i o n time. Some d e v i c e s , such as d i s c d r i v e s , c o n t a i n p r e c i o u s i n f o r m a t i o n , and should not be a c c e s s i b l e to user p r o c e s s e s , whereas other forms of d e v i c e s , such as t e r m i n a l i n t e r f a c e s , are l e s s s e n s i t i v e . When a c r e a t i o n request i s r e c e i v e d f o r a s e n s i t i v e d e v i c e , the type of the process sending the request should be checked. The request should be r e j e c t e d i f the process does not meet some s e c u r i t y c r i t e r i o n , such as being a system p r o c e s s . S i m i l a r l y , some d e v i c e s are i n s e n s i t i v e to read and w r i t e r e q u e s t s , hence read and w r i t e requests can be allowed from any p r o c e s s . More s e n s i t i v e d e v i c e s , however, should check each read and/or w r i t e request to ensure t h a t i t comes from an a c c e p t a b l e p r o c e s s . The most u s e f u l acceptance c r i t e r i o n f o r s e n s i t i v e d e v i c e s i s that the request comes from the same process who c r e a t e d the d e v i c e . 19 3.3.2 I n t e r f a c e 3.3.2.1 Communication A b a s i c component of the d e v i c e management system i s a means of communication between processes and d e v i c e software v i a messages. To m a i n t a i n c o m p a t i b i l i t y with I/O l i b r a r y r o u t i n e s , d e v i c e communication must appear e x a c t l y the same as i n t e r p r o c e s s communication. T h i s r e q u i r e s t h a t the k e r n e l p r i m i t i v e s implementing message p a s s i n g must d e t e c t messages that are intended f o r d e v i c e s and pass them to the a p p r o p r i a t e code. The method used to determine i f a message i s intended f o r a d e vice or a process cannot depend on the contents of the message, as message contents should be u n r e s t r i c t e d . T h i s leaves the process i d e n t i f i e r of the process to which the message i s sent as the o n l y source of i n f o r m a t i o n to d i s c e r n the proper d e s t i n a t i o n of a message. T h e r e f o r e one or more process i d e n t i f i e r s must be r e s e r v e d f o r d e v i c e communication. There are a number of ways i n which process i d e n t i f i e r s c o u l d be used to i n d i c a t e t h a t a message i s intended f o r a d e v i c e . The primary f a c t o r i n f l u e n c i n g the s e l e c t i o n of a p a r t i c u l a r method i s the amount of overhead added to the message p a s s i n g , as message based o p e r a t i n g systems g e n e r a l l y have a high volume of message t r a f f i c [10]. 20 The s i m p l e s t p o s s i b l e method i s t o r e s e r v e one u n i q u e p r o c e s s i d e n t i f i e r t o i n d i c a t e d e v i c e c o m m u n i c a t i o n . T h i s has t h e a d v a n t a g e o f b e i n g e a s y and e f f i c i e n t t o d e t e c t , r e q u i r i n g o n l y a s i n g l e c o m p a r i s o n . A d i s a d v a n t a g e o f t h i s method i s t h a t i t e l i m i n a t e s any p o s s i b i l i t y o f u s i n g i n f o r m a t i o n i n t h e p r o c e s s i d e n t i f i e r f o r o t h e r p u r p o s e s s u c h as d e v i c e c l a s s s e l e c t i o n . T h i s d i s a d v a n t a g e i s m i n i m i z e d by t h e f a c t t h a t I/O p r o t o c o l s use f i e l d s i n t h e message t o i d e n t i f y a p a r t i c u l a r o b j e c t . Two l e v e l s y s t e m s , w h i c h s e l e c t b o t h on t h e p r o c e s s i d e n t i f i e r and t h e o b j e c t i d e n t i f i e r i n t h e message, a r e i m p o s s i b l e w i t h t h i s scheme. A n o t h e r p o s s i b l e method i s t o r e s e r v e a g r o u p o r r a n g e o f i d e n t i f i e r s . The p a r t i c u l a r i d e n t i f i e r i n t h e g r o u p c a n t h e n be u s e d t o g i v e some i n f o r m a t i o n a b o u t t h e d e v i c e . T h i s a l l o w s g r e a t e r f l e x i b i l i t y i n d e v i c e s p e c i f i c a t i o n , b u t i n c u r s a s m a l l p e r f o r m a n c e p e n a l t y , and i s more c o m p l i c a t e d . The s i n g l e r e s e r v e d i d method was c h o s e n f o r i m p l e m e n t a t i o n , b e c a u s e o f e f f i c i e n c y and s i m p l i c i t y c o n s i d e r a t i o n s . The two l e v e l s e l e c t i o n p o s s i b l e u s i n g a r a n g e o f r e s e r v e d p r o c e s s i d e n t i f i e r s g i v e s a w i d e r r a n g e o f d e v i c e s e l e c t i o n , b u t r e q u i r e s more code and t a k e s more t i m e . The o b j e c t i d e n t i f i c a t i o n f i e l d i n t h e message seems t o g i v e s u f f i c i e n t d e v i c e s p e c i f i c a t i o n r a n g e . 21 Processes Process # 2 K e r n e l — > — > REPLY Message Sending Routine Message Forwarding Routine Message Reply Routine REPLY — > Device Management System F i g u r e 3.1 — Process Device Communication Once a message has been i d e n t i f i e d as being intended f o r a d e v i c e , the a p p r o p r i a t e d e v i c e h a n d l i n g code must be s e l e c t e d . The s e l e c t i o n of code depends on the type of d e v i c e being addressed, and the s e r v i c e being requested. 22 3.3.2.2 I/O P r o t o c o l The r e m a i n d e r o f t h e i n t e r f a c e i s l a r g e l y d e f i n e d by t h e I/O p r o t o c o l c h o s e n . E x t e n s i o n s w i l l p r o b a b l y be r e q u i r e d t o t h e p r o t o c o l f o r t h e s p e c i f i c a t i o n o f t h e h a r d w a r e i n f o r m a t i o n i n t h e d e v i c e c r e a t i o n r e q u e s t . 3.3.3 I n t e r n a l D e s i g n A d e v i c e d r i v e r c a n be s e p a r a t e d i n t o two d i s t i n c t p a r t s : i n t e r r u p t d r i v e n and r e q u e s t d r i v e n . R o u t i n e s i n t h e r e q u e s t d r i v e n s e c t i o n a r e e x e c u t e d i n r e s p o n s e t o an I/O p r o t o c o l r e q u e s t f r o m a p r o c e s s , w h i l e i n t e r r u p t d r i v e n r o u t i n e s a r e e x e c u t e d i n r e s p o n s e t o an i n t e r r u p t f r o m a d e v i c e . C o m m u n i c a t i o n between t h e two s e c t i o n s must be t h r o u g h t h e use o f s h a r e d d a t a s t r u c t u r e s , as message p a s s i n g and p r o c e s s s y n c h r o n i z a t i o n do n o t e x i s t below t h e k e r n e l l e v e l . F o r example, i n r e s p o n s e t o a r e a d r e q u e s t , t h e r e q u e s t d r i v e n s e c t i o n o f a d e v i c e d r i v e r m i g h t c h e c k a b u f f e r f o r d a t a , and b l o c k t h e r e q u e s t i n g p r o c e s s i f t h e r e was none. I n r e p o n s e t o an i n c o m i n g d a t a i n t e r r u p t , t h e i n t e r r u p t d r i v e n s e c t i o n c h e c k s t h e s h a r e d d a t a s t r u c t u r e t o see i f a p r o c e s s i s b l o c k e d w a i t i n g f o r i n p u t , and u n b l o c k s i t i f t h e r e i s , o t h e r w i s e b u f f e r i n g t h e d a t a . 23 3.3.3.1 Data S t r u c t u r e s In choosing the form of data s t r u c t u r e s used, one trades o f f f l e x i b i l i t y a g a i n s t overhead. The more f l e x i b l e memory management schemes have a high space overhead, and an even higher e x e c u t i o n time overhead. At the k e r n e l l e v e l , i t i s important to minimize overhead, so the more complicated methods must be r e j e c t e d . S t a t i c a l l o c a t i o n has no overhead, but r u l e s out dynamic r e c o n f i g u r a t i o n . A s u i t a b l e compromise between these two extremes i s dynamic a l l o c a t i o n of memory i n p i e c e s of a few f i x e d s i z e s . A data s t r u c t u r e i s r e q u i r e d to d e s c r i b e the d e v i c e to the device management system, and to s t o r e d e v i c e dependant i n f o r m a t i o n . T h i s data s t r u c t u r e i s used to s e l e c t the a p p r o p r i a t e device dependant code to s e r v i c e I/O requests f o r the d e v i c e . Access to t h i s data s t r u c t u r e should be f a s t , as i t must be accessed f o r every d e v i c e request: T h i s suggests the use of a t a b l e of p o i n t e r s to d e v i c e s t a t e v e c t o r s , with the f i l e i d e n t i f i e r of the d e v i c e used to s e l e c t the element of the t a b l e . A simple indexing scheme i s u n d e s i r a b l e , a s i t allows p o s s i b l e c o n f u s i o n between a d e v i c e r e c e n t l y removed, and a new one t h a t has been c r e a t e d with the same index. T h i s problem can be avoided by using the low order b i t s of the f i l e i d e n t i f i e r as an index, and the high order b i t s as a sequence number. The time r e q u i r e d f o r the sequence number to r e c y c l e makes c o n f u s i o n u n l i k e l y . C e r t a i n requests i n I/O p r o t o c o l s can be s e r v i c e d with 24 l i t t l e r e f e r e n c e to device s p e c i f i c i n f o r m a t i o n . These requests do not r e q u i r e d e v i c e s p e c i f i c r o u t i n e s , but can be handled by g e n e r a l r o u t i n e with a l i t t l e d e v i c e s p e c i f i c i n f o r m a t i o n from the de v i c e s t a t e v e c t o r . Space must be a l l o c a t e d i n the s t a t e v e c t o r f o r the needed i n f o r m a t i o n . The d e c i s i o n of which requests to implement i n t h i s f a s h i o n i s based on o p t i m i z a t i o n of memory requirements. The d e v i c e s t a t e v e c t o r must a l s o c o n t a i n space f o r device s p e c i f i c i n f o r m a t i o n s t o r a g e . As the amount of needed storage v a r i e s from d e v i c e to d e v i c e , and the s t a t e v e c t o r s i z e i s f i x e d , d e c i d i n g how much " e x t r a " space to leave i s a problem. The best s o l u t i o n i s one t h a t minimizes the memory space used, which can be determined e x p e r i m e n t a l l y . More than one s t a t e v e c t o r can be a l l o c a t e d f o r those d e v i c e s which r e q u i r e more storage than i s allowed i n a s i n g l e s t a t e v e c t o r . 3.3.3.2 Request D r i v e n Routines As mentioned above, some requests r e q u i r e l i t t l e i n the way of d e v i c e s p e c i f i c i n f o r m a t i o n to be s e r v i c e d . These mainly take the form of simple querys and parameter changes. F l e x i b i l i t y c o n s i d e r a t i o n s r e q u i r e the use of device s p e c i f i c code to implement some I/O r e q u e s t s . These r o u t i n e s are accessed through the de v i c e s t a t e v e c t o r , which c o n t a i n s t h e i r addresses. The requests are l i k e l y to r e q u i r e d e v i c e s p e c i f i c code are those which perform the more complicated 25 f u n c t i o n s , i . e . data communication and d e v i c e c o n t r o l . To ensure f l e x i b i l i t y i t i s b e t t e r to e r r on the s i d e of too many device s p e c i f i c r o u t i n e s . The overhead of a l l o w i n g a r o u t i n e to be device s p e c i f i c i s o n l y one address i n the device s t a t e v e c t o r , and a s m a l l time overhead to access the d e s c r i p t o r and the address of the r o u t i n e . Devices t h a t have s i m i l a r requirements can share the same request s e r v i c e code. 3.3.3.3 I n t e r r u p t D r i v e n Routines Very few r e s t r i c t i o n s should be p l a c e d on the way i n which i n t e r r u p t r o u t i n e s are w r i t t e n , as they must d e a l with widely v a r y i n g kinds of hardware, i n as e f f i c i e n t a manner as p o s s i b l e . The o n l y s t r u c t u r e imposed i s t h a t of communications, that the i n t e r r u p t d r i v e n r o u t i n e s communicate with the request d r i v e n r o u t i n e s through the shared memory of the d e v i c e s t a t e v e c t o r s and b u f f e r s . 3.3.3.4 U t i l i t y Routines To make the de v i c e management system easy f o r the implementor, a wide range of u t i l i t y r o u t i n e s should be pr o v i d e d . Use of u t i l i t y r o u t i n e s a l s o i n c r e a s e s the r e l i a b i l i t y o f the de v i c e d r i v e r s , as o b j e c t s are handled i n a s t a n d a r d i z e d , t e s t e d f a s h i o n . Memory management i s one area i n which u t i l i t y r o u t i n e s 26 are important. Routines should be provided for the al l o c a t i o n and freeing of device descriptors and buffers. I n i t i a l i z a t i o n of standard f i e l d s in the device descriptor i s another useful u t i l i t y . Routines should be provided to manage such " b u i l t i n " data structures as interrupt vectors, minimizing the machine dependant data that the implementer must learn. Many devices share common properties, which allow the use of common routines for c o n t r o l l i n g them. For example, most of the software used to map terminal interfaces onto the I/O protocol i s common to a l l terminals interfaces, regardless of the hardware protocols used. The common parts should be provided as u t i l i t y routines and documented, to minimize the work of implementing a driver for a new type of terminal interface. Another class of u t i l i t y routines that should be provided i s no-operation (NOP) routines. These routines are used to f i l l s l o t s for device dependant request service routines, when the p a r t i c u l a r service i s impossible or meaningless for a device. For example, performing a read operation on a printer interface i s , in general, meaningless. In thi s case, the s l o t for read request service would be f i l l e d with a pointer to a routine that merely returns a reply that indicates that the device i s not readable. Processes that communicate with devices usually must be synchronized in some fashion with the interrupts from the 27 devices. Routines must be provided to block a process and rest a r t i t after an event. These routines usually exist in some form or other in any multiprocessing kernel, and often may be used without modification when a device management subsystem i s added. 28 Chapter 4 Environment 4.1 Verex Process Management & Communication Verex i s a message based o p e r a t i n g system. Operations f o r process c r e a t i o n , and i n t e r p r o c e s s communication are prov i d e d by the Verex k e r n e l . The k e r n e l a l s o p r o v i d e s p r i m i t i v e process s c h e d u l i n g . The two o p e r a t i o n s used f o r process c r e a t i o n are: new_process_id = .Create_process() which a l l o c a t e s a process d e s c r i p t o r and r e t u r n s i t s i d ; and . I n i t _ p r o c e s s ( i d , s t a c k _ s i z e , ... ) which i n i t i a l i z e s the process d e s c r i p t o r and schedules i t to be run. I n t e r p r o c e s s communication uses s m a l l , f i x e d s i z e message b u f f e r s , which r e s i d e i n s i d e the k e r n e l . 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 to read and w r i t e the message b u f f e r s from the process" address space. The b a s i c communication o p e r a t i o n s p r o v i d e d are: r e c e i v e r _ i d = .Send_msg( i d ) which sends a message to a process whose i d i s g i v e n as a parameter, and awaits a r e p l y ; 29 s e n d e r _ i d = .Receive_msg( [id] ) which r e c e i v e s a message from the s p e c i f i e d p r o c e s s , or any process i f no i d i s g i v e n , i f a message has been sent the i d of the sending process i s r e t u r n e d , otherwise an i n d i c a t i o n t h a t no message has been sent i s returned; .Await_msg( i d ) which waits f o r a message to be sent to the i n v o k i n g process from the process s p e c i f i e d , or any process i f none i s s p e c i f i e d , and then r e t u r n s the i d of the sending process; .Reply_msg( i d ) which r e p l i e s to the sender s p e c i f i e d ; and .Forward_msg( from_id, t o _ i d ) which passes a message to the process s p e c i f i e d by the parameter " t o _ i d " , as i f i t was sent by the process s p e c i f i e d by the parameter "from_id". Message p a s s i n g i s synchronous, as a sender must wait u n t i l h i s message has been r e c e i v e d and r e p l i e d to before proceeding. The o n l y asynchronous event p o s s i b l e i s process d e s t r u c t i o n : .Destroy( i d ) which d e s t r o y s the process s p e c i f i e d by i d , i f i t has the same user as the invoking p r o c e s s , or the user of the invoking process i s the system user. 30 The kernel process scheduling maintains multiple p r i o r i t i z e d queues of processes, and ensures that the highest p r i o r i t y ready process i s always running. A process being added to a queue of a given p r i o r i t y l e v e l i s added at the end, creating round-robin scheduling for process at the same l e v e l . Higher l e v e l scheduling i s done external to the kernel, through modification of process p r i o r i t y . At the kernel l e v e l , the routines .Block, .Unblock, and .Block_and_unblock are used to remove and add processes to the ready queues. These routines are accessible to the device management software to schedule processes waiting for I/O. 4.2 The Verex I/O Protocol The Verex I/O protocol i s designed to provide standard interaction with a wide variety of data storage and communication f a c i l i t i e s . The protocol i s object based and connectionless, using the client-server communication model. A l l services using the protocol are mapped onto a standard view of a " f i l e " . A standard f i l e i s made up of "blocks" which may vary in length. Each block has associated with i t a number that defines i t s l o g i c a l p o s i t i o n . The way in which the data i s divided into blocks i s not defined by the I/O protocol, and can be selected to match the c h a r a c t e r i s t i c s of the service. Operations provided by the I/O protocol are executed on 31 " i n s t a n c e s " o f f i l e s . A f i l e i n s t a n c e i s a c u r r e n t l y a c t i v e e n t i t y , i d e n t i f i e d by t h e i d e n t i t y o f i t s s e r v e r p r o c e s s , and a f i l e i n s t a n c e i d e n t i f i e r p r o v i d e d by t h e s e r v e r . The m a i n d i s t i n c t i o n between f i l e s and f i l e i n s t a n c e s i s t h a t i n s t a n c e s a r e d y n a m i c , e x i s t i n g o n l y f o r t h e d u r a t i o n o f some a c t i v i t y , whereas f i l e s may e x i s t t h r o u g h many i n s t a n t i a t i o n s . To a l l o w t h e use o f w i d e l y d i f f e r i n g I/O f a c i l i t i e s , t h e p r o t o c o l d e f i n e s s t a n d a r d d e s c r i p t i o n s o f f i l e a t t r i b u t e s . T h i s a l l o w s t h e c l i e n t t o t r e a t a f i l e i n s t a n c e i n a manner a p p r o p r i a t e t o i t s t y p e . T h e s e a t t r i b u t e s d e f i n e t h e l i m i t a t i o n s on t h e o p e r a t i o n s t h a t c a n be e x e c u t e d on t h e f i l e . F o r i n s t a n c e , t h e WRITEABLE a t t r i b u t e d e f i n e s w hether a f i l e c a n be w r i t t e n t o , and c a n be u s e d t o implement w r i t e p r o t e c t i o n on f i l e s . The message as p r o v i d e d by t h e i n t e r p r o c e s s c o m m u n i c a t i o n p r i m i t i v e s i s t h e b a s i c u n i t o f t h e p r o t o c o l . The t y p e o f r e q u e s t i s s p e c i f i e d by t h e ,REQ_CODE f i e l d o f t h e message. T h i s s e m a n t i c s o f t h e r e s t o f t h e message i s d e f i n e d a c c o r d i n g t o t h e t y p e o f r e q u e s t . The r e q u e s t c o d e s d e f i n e d by t h e I/O p r o t o c o l a r e : .CREATE_INSTANCE, .RELEASE_INSTANCE, .QUERY_INSTANCE, .READ_INSTANCE, .WRITE_INSTANCE, and .SET_INSTANCE_OWNER. The r e p l y message f r o m t h e s e r e q u e s t s has a s t a n d a r d .REPLY_CODE c o m p l e t e d , o r i t s r e a s o n f o r f a i l u r e . The .CREATE_INSTANCE r e q u e s t c r e a t e s an i n s t a n c e o f a f i l e and r e t u r n s an i n s t a n c e i d e n t i f i e r and t h e f i l e ' s a t t r i b u t e s . The nature of the i n s t a n c e c r e a t e d depends on se r v e r dependant i n f o r m a t i o n used to s p e c i f y the f i l e d e s i r e d , and a standard "usage mode" which d e f i n e s the manner i n which the f i l e i s to be used. The .RELEASE_INSTANCE request informs the s e r v e r that a c l i e n t i s f i n i s h e d with a f i l e i n s t a n c e . The s e r v e r then performs whatever cleanup o p e r a t i o n i s a s s o c i a t e d with the r e l e a s e of the f i l e i n s t a n c e . A f i e l d i n the r e l e a s e request s p e c i f i e s the " r e l e a s e mode" of the i n s t a n c e . Use of t h i s i n f o r m a t i o n i s server dependant, and i s u s u a l l y used to i n d i c a t e whether or not permanent data should be updated. The .QUERY_INSTANCE request r e t u r n s the same i n f o r m a t i o n as the .CREATE_INSTANCE request, without c r e a t i n g a new i n s t a n c e . The f i l e i n s t a n c e q u e r i e d i s s p e c i f i e d by the f i l e s i n s t a n c e i d e n t i f i e r . The .READ_INSTANCE and .WRITE_INSTANCE requests are used f o r data t r a n s f e r between the c l i e n t and the f i l e i n s t a n c e . The block number, the number of bytes to be t r a n s f e r r e d and the l o c a t i o n of the data are s p e c i f i e d by f i e l d s the request message. The .SET_INSTANCE_OWNER request changes the owner of the s p e c i f i e d f i l e i n s t a n c e to a new owner s p e c i f i e d by a f i e l d i n the request message. T h i s allows i n s t a n c e ownership to be t r a n s f e r r e d from one process to another. T h i s i s necessary as some s e r v e r s allow c e r t a i n o p e r a t i o n s on an i n s t a n c e to be executed o n l y by the i n s t a n c e ' s owner. 33 Two a d d i t i o n a l requests used by some s e r v e r s are the .CONTROL and .QUERY r e q u e s t s , which are used to request o p e r a t i o n s and server i n f o r m a t i o n not pr o v i d e d f o r by the standard I/O p r o n o t c o l . For example, the f i l e s e r v e r uses these requests to perform such o p e r a t i o n s as t r a c k f o r m a t t i n g , and the t e r m i n a l server to r e t u r n i n f o r m a t i o n about t e r m i n a l c h a r a c t e r i s t i c s . For a more complete d e s c r i p t i o n , the reader i s r e f e r r e d to C h e r i t o n [10]. 4.3 Verex I/O Se r v e r s Through the use of a s t a n d a r d i z e d p r o t o c o l s , the Verex o p e r a t i n g system has evolved to the p o i n t where a l l o p e r a t i n g system s e r v i c e s , a s i d e from the b a s i c few pr o v i d e d by the k e r n e l , are p r o v i d e d by server p r o c e s s e s . T h i s has r e s u l t e d i n a h i g h l y modular system, which i s e a s i l y r e c o n f i g u r e d to s u i t i t s purpose, as the s e l e c t i o n of s e r v e r s invoked when the system i s s t a r t e d can be v a r i e d simply by m o d i f i c a t i o n of a setup f i l e . The use of the I/O p r o t o c o l has l e d to the c r e a t i o n of many I/O s e r v e r s which use i t to i n t e r a c t i n a standard f a s h i o n . As a l l s e r v e r s use the I/O p r o t o c o l , the type of f i l e being used i s t r a n s p a r e n t to the a p p l i c a t i o n , a s i d e from s p e c i a l c o n t r o l f u n c t i o n s p o s s i b l e on some d e v i c e s . The p r o t o c o l has been s u c c e s s f u l l y a p p l i e d to communication with f i l e s e r v e r s , l o c a l and long haul networks, t e r m i n a l s , i n t e r - u s e r m a i l , and p i p e s . 34 A name server i s used to relate the symbolic name of a service to the process id of the server process. This provides great f l e x i b i l i t y in the redir e c t i o n of the output from programs. For example, the output from the editor can be sent d i r e c t l y to the mail server, allowing the convenient composition of mail messages with a v i s u a l editor, without the use of an intermediate storage f i l e . 35 C h a p t e r 5 I m p l e m e n t a t i o n T h i s c h a p t e r w i l l d i s c u s s t h e i m p l e m e n t a t i o n o f t h e i d e a s d i s c u s s e d i n t h e p r e v i o u s c h a p t e r s , as a p a r t o f t h e V e r e x o p e r a t i n g s y s t e m r u n n i n g on t h e T e x a s I n s t r u m e n t s T I 9 9 0 / 1 0 . D e v i c e d e p e n d a n t c o d e w i l l be d i s c u s s e d i n t h e a p p e n d i c e s . A g u i d e l i n e f o r d e v i c e i m p l e m e n t a t i o n w i l l be f o u n d A p p e n d i x A and an example d e v i c e d r i v e r i n A p p e n d i x B. I n o r d e r t o implement k e r n e l d e v i c e s , c h a n g e s must be made t o t h e o r i g i n a l k e r n e l code f o r p r o c e s s c r e a t i o n and d e l e t i o n , and message p a s s i n g . P r o c e s s c r e a t i o n must be c h a n g e d t o i n s u r e t h a t t h e s p e c i a l DEVICE_SERVER i d i s n o t g i v e n t o a p r o c e s s . The p r o c e s s d e s t r u c t i o n r o u t i n e i s a l t e r e d so t h a t a d e v i c e b e i n g w r i t t e n o r r e a d by a p r o c e s s t o be d e s t r o y e d i s r e t u r n e d t o an i d l e s t a t e . The message p a s s i n g r o u t i n e s must be a l t e r e d t o r o u t e messages s e n t o r f o r w a r d e d t o t h e DEVICE_SERVER t o t h e d e v i c e s e r v e r r o u t i n e . A l s o , code must be added t o t h e s y s t e m i n i t i a l i z a t i o n t o s e t up k e r n e l d e v i c e d a t a s t r u c t u r e s . The b a s i c k e r n e l d e v i c e d a t a s t r u c t u r e s a r e : a t a b l e o f d e v i c e s t a t e d e s c r i p t o r s ; a b u f f e r p o o l ; and a t a b l e o f t h e d e v i c e c r e a t i o n f u n c t i o n s f o r d i f f e r e n t d e v i c e c l a s s e s . The n e c e s s a r y r o u t i n e s f o r h a n d l i n g t h e s e d a t a s t r u c t u r e s a r e : d e v i c e d e s c r i p t o r a l l o c a t i o n / r e l e a s e r o u t i n e s ; a r o u t i n e f o r mapping f r o m d e v i c e i d s t o d e s c r i p t o r a d d r e s s e s ; b u f f e r p o o l management r o u t i n e s ; and a r o u t i n e t o c a l l t h e d e v i c e 36 c r e a t i o n r o u t i n e a p p r o p r i a t e g i v e n i t s d e v i c e c l a s s . The d e v i c e d e s c r i p t o r c o n t a i n s d e v i c e i n d e p e n d a n t i n f o r m a t i o n as w e l l as s p a c e f o r d e v i c e d e p e n d a n t i n f o r m a t i o n . The d e v i c e i n d e p e n d a n t r o u t i n e i n c l u d e s : p o i n t e r s t o t h e code t o be e x e c u t e d f o r r e a d , w r i t e , c o n t r o l , and r e l e a s e r e q u e s t s ; p o i n t e r s t o cod e t o r e s t a r t t h e d e v i c e a f t e r power f a i l u r e ; i n f o r m a t i o n a b o u t t h e d e v i c e , s u c h as i t s b l o c k s i z e ; and i n f o r m a t i o n a b o u t t h e p r o c e s s e s u s i n g t h e d e v i c e . The d e v i c e d e s c r i p t o r a l l o c a t i o n / r e l e a s e r o u t i n e s were k e p t s i m p l e t o m i n i m i z e c o d e . As d e v i c e c r e a t i o n and d e l e t i o n a r e r a r e e v e n t s , t h e r o u t i n e s need n o t be p a r t i c u l a r l y f a s t . The a l l o c a t i o n a l g o r i t h m u s e d i s a s i m p l e s e q u e n t i a l s e a r c h t h r o u g h t h e d e v i c e d e s c r i p t o r t a b l e f o r an unused d e s c r i p t o r . I f no unused d e s c r i p t o r i s f o u n d , an a t t e m p t i s made t o c l e a n up r e s o u r c e s a l l o c a t e d t o d e v i c e s whose owner p r o c e s s e s no l o n g e r e x i s t . The c e n t r a l r o u t i n e t o t h e d e v i c e s e r v e r code i s S e n d _ d e v i c e , w h i c h i n t e r p r e t s t h e k e r n e l d e v i c e r e q u e s t i n a manner s i m i l a r t o a s t a n d a r d s e r v e r . The m a j o r d i f f e r e n c e i s t h a t t h e s e n d i n g p r o c e s s i s n o t r e p l i e d t o , b u t i s e i t h e r b l o c k e d o r r e t u r n e d t o d e p e n d i n g on t h e d e v i c e and t h e r e q u e s t . I f t h e r e q u e s t i s f o r w a r d e d , t h e s e n d i n g r o u t i n e i s u n b l o c k e d u n l e s s t h e r e p l y code i s .NO_REPLY, and t h e f o r w a r d e r i s a l w a y s r e t u r n e d t o , whereas i f t h e r e q u e s t i s n o t f o r w a r d e d , t h e s e n d e r i s r e t u r n e d t o u n l e s s t h e r e p l y code i s .NO REPLY, i n w h i c h c a s e i t i s b l o c k e d . 37 Send_device c a l l s the routine appropriate to the .REQUEST_CODE of the message. Device requests conform to the Verex I/O protocol, and are i d e n t i c a l to standard server requests, except in the case of the .CREATEINSTANCE request, where additional information must be s p e c i f i e d . The information required are: the service type, which s p e c i f i e s the p a r t i c u l a r hardware device and how i t i s to be used; and hardware location information, which in the case of the TI/990 consists of the interrupt l e v e l and CRU address. The service type i s used as an index into a table of functions to select the appropriate device c r e a t i o n / i n i t i a l i z a t i o n routine. 38 Chapter 6 R e s u l t s The implementation of the d e v i c e managment system as a p a r t of the Verex o p e r a t i n g system has proceeded to the p o i n t where i t can be used as p a r t of a p r o d u c t i o n system. A v e r s i o n of the system i n c o r p o r a t i n g the d e v i c e management system has been i n everyday use f o r four months, and has proved to be very r e l i a b l e . Not a l l d e v i c e s have had t h e i r d e v i c e d r i v e r s m o d i f i e d to work with the new system, so c u r r e n t systems use a combination where some de v i c e s are handled using the new system, and o t h e r s s t i l l use the o l d . Devices are being converted to the new system as programmer time p e r m i t s . The system commonly i n use uses the d e v i c e management system to d r i v e a l l t e r m i n a l and p r i n t e r i n t e r f a c e s , l e a v i n g o n l y the d i s c c o n t r o l l e r i n t e r f a c e and the x.25 network i n t e r f a c e unconverted. Response to i n t e r r u p t s has been, as p r e d i c t e d , g r e a t l y improved. The t e r m i n a l s i n t e r f a c e s can now send c h a r a c t e r s to the cpu at 19200 baud, w h i l e dropping o n l y the o c c a s i o n a l c h a r a c t e r . The reason f o r the c h a r a c t e r s dropping i s not due to the d e v i c e management system, but to the f a c t t h a t Verex d i s a b l e s a l l i n t e r r u p t s when executing k e r n e l code. A p o s s i b l e f u t u r e p r o j e c t i s to modify Verex so t h a t k e r n e l code can run with i n t e r r u p t s enabled. No c h a r a c t e r s are missed at 9600 baud. The maximum r a t e of output to t e r m i n a l s 39 has decreased by about ten p e r c e n t . T h i s i s due to the s m a l l output b u f f e r s i z e . T h i s can be cured by e n l a r g i n g the output b u f f e r s i z e , and w i l l be done when time p e r m i t s . As the t e r m i n a l i n t e r f a c e s are now managed by the device management system, the h i g h - l e v e l t e r m i n a l server has been removed from the system address space. T h i s has r e s u l t e d i n a twenty percent decrease i n the s i z e of the system, which i s a g r e a t advantage as the address space l i m i t a t i o n of the machine was beginning to make system expansion d i f f i c u l t . Removal of the t e r m i n a l s e r v e r from the system address space has allowed i t much more room f o r expansion. The high l e v e l i n t e r f a c e p r o v i d e d by the d e v i c e s e r v e r has f a c i l i t a t e d the a d d i t i o n of new f e a t u r e s to the t e r m i n a l s e r v e r , through the use of c o n t r o l r e q u e s t s . 40 C h a p t e r 7 C o n c l u s i o n s The i m p l e m e n t a t i o n o f t h e d e v i c e management s y s t e m as a p a r t o f t h e V e r e x o p e r a t i n g s y s t e m has d e m o n s t r a t e d t h e f e a s a b i l i t y and m e r i t o f c o m m u n i c a t i n g w i t h d e v i c e s u s i n g a h i g h - l e v e l I/O p r o t o c o l . D e v i c e d r i v e r s were w r i t t e n f o r a number o f d i f f e r e n t d e v i c e t y p e s , p r o v i n g t h e f l e x i b i l i t y o f t h e method. The e x t e n s i b i l i t y o f t h e i d e a s has y e t t o be p r o v e n , as V e r e x i s t h e o n l y o p e r a t i n g s y s t e m i n w h i c h t h e y have been i m p l e m e n t e d . I t i s c l e a r t h a t t h i s f o r m o f d e v i c e management c o u l d be a p p l i e d t o s i m i l a r o p e r a t i n g s y s t e m s s u c h as T h o t h , b u t w hether o p e r a t i n g s y s t e m s w i t h p r i m i t i v e i n t e r p r o c e s s c o m m u n i c a t i o n c a n b e n e f i t f r o m i t r e m a i n s an open q u e s t i o n . As i s u s u a l l y t h e c a s e i n i m p l e m e n t a t i o n , u n f o r s e e n p r o b l e m s were e n c o u n t e r e d , r e q u i r i n g m o d i f i c a t i o n o f some o f t h e o r i g i n a l i d e a s . I t i s l i k e l y t h a t d e v i c e s e x i s t f o r w h i c h a d e v i c e d r i v e r w o u l d be d i f f i c u l t t o implement w i t h t h i s s y s t e m . F o r t u n a t e l y , t h e i m p l e m e n t a t i o n i s e a s y t o m o d i f y . 41 Appendix 1 Ke r n e l Device Implementation G u i d e l i n e T h i s appendix g i v e s a step by step g u i d e l i n e f o r adding a d e v i c e d r i v e r to the Verex o p e r a t i n g system k e r n e l . F a m i l i a r i t y with the Verex I/O p r o t o c o l and knowledge of how to compile and boot a new system i s r e q u i r e d of the implementor. Other knowledge about the system and the k e r n e l should be unnecessary. A d e v i c e d r i v e r i n t h i s system c o n s i s t s l o g i c a l l y of two p a r t s ; the i n t e r r u p t d r i v e n r o u t i n e s and the request d r i v e n r o u t i n e s , which communicate through the shared device s t a t e d e s c r i p t o r ( s ) and o p t i o n a l l y through shared b u f f e r s . Request S e r v i c e Routines When a request i s sent to the de v i c e server pseudo-process, the a p p r o p r i a t e r o u t i n e i s c a l l e d to s e r v i c e that request. A l l request s e r v i c e r o u t i n e s are subrouti n e s w r i t t e n i n the Zed language, with parameters as d e s c r i b e d below. Some re q u e s t s , such as .QUERY_INSTANCE are de v i c e independant and are handled by de v i c e independant code. The de v i c e dependant request s e r v i c e r o u t i n e s are i d e n t i f i e d i n the d e v i c e ' s d e s c r i p t o r . The e x c e p t i o n to t h i s p a t t e r n i s the r o u t i n e which responds t o the .CREATE_INSTANCE request, which occurs before the de v i c e d e s c r i p t o r i s a l l o c a t e d . T h i s r o u t i n e uses 42 the SERVICE_TYPE f i e l d of the creation request as an index into a s t a t i c array of device creation routines. When a new device i s added, the assembler module Create_function, i s modified and re-assembled. This module s p e c i f i e s the array of device creation functions, and an external variable, Max_service_type, which indicates the length of the array. The name of the device creation function of the new device is added to the end of the array, and Max_service_type i s increased by one. Note that a code for a device class can be excluded from the system by commenting out i t s entry in the Cr e a t e f u n c t i o n table and replacing i t with a zero word. This w i l l cause the routine Create_device to return a reply code of .ILLEGAL_REQ to a device creation request for that device c l a s s . The device creation routine i s c a l l e d with two parameters: a pointer to the requesting message, and a pointer to the process descriptor (PD) of the requesting process. Its function i s to allocate and i n i t i a l i z e a l l data structures used by the device. This w i l l include at least one device descriptor, and possibly buffers provided by the buffer support routines. The device descriptor i s allocated by the routine Alloc_device, and freed by the routine Free_device. The values of the f i e l d s in the descriptor are i n i t i a l l y undefined and must be set by the device creation routine. Buffers are allocated by the routine A l l o c b u f f e r , and freed by the routine Free_buffer. The buffers have a fixed size of 80 bytes. 43 A d e v i c e d e s c r i p t o r i s d e f i n e d by t h e Zed t e m p l a t e : t e m p l a t e DEVICE STATE word REGISTERO; \ RO : i n i n t e r r u p t word REGISTER1, \ RI REGISTER2, \ R2 REGISTER3, \ R3 REGISTER4, \ R4 REGISTER5, \ R5 REGISTER6, \ R6 REGISTER7, \ R7 REGISTER8, \ R8 REGISTER9, \ R9 REGISTER10, \ RIO REGISTER11, \ R l l REGISTER12; \ R12 word RETURN WP[]; \ R13 ( r e s e r v e d ) u n s i g n e d RETURN P C [ ] ( ) , \ R14 ( r e s e r v e d ) RETURN ST; \ R15 ( r e s e r v e d ) u n s i g n e d READ_FUNCTION[](), WRITE_FUNCTION [] () , CONTROL_FUNCTION [] () , RESTART_FUNCTION[](), RELEASE_FUNCTION [] () , READ_CLEAR_FUNCTION[](), WRITE_CLEAR_FUNCTION [] () , F I L E _ T Y P E , \ f o r r e s p o n e s t o IN_BLOCK_SIZE, \ .QUERY_INSTANCE r e q u e s t s OUT_BLOCK_SIZE, WRITER_ID, READER_ID, USED, DEVICE_OWNER, F I L L E R : [ 2 ] ; } The "FUNCTION" f i e l d s a r e i n i t i a l i z e d t o p o i n t t o t h e a p p r o p r i a t e code t o s e r v i c e t h e r e q u e s t . The f i e l d s F I L E _ T Y P E , IN_BLOCK_SIZE and OUT_BLOCK_SIZE must be i n i t i a l i z e d i n a c c o r d a n c e w i t h t h e V e r e x I/O p r o t o c o l s p e c i f i c a t i o n s f o r t h e .QUERY_INSTANCE r e q u e s t t o work p r o p e r l y f o r t h e d e v i c e . The f i e l d USED i s u s e d by t h e d e v i c e d e s c r i p t o r management r o u t i n e s and must n o t be 44 a l t e r e d . The f i e l d s READER_ID and WRITER_ID may be u s e d f o r k e e p i n g t r a c k o f t h e i d s o f p r o c e s s e s r e a d i n g and w r i t i n g t h e d e v i c e . The f i e l d F I L L E R i s t h r e e words o f u n c o m m i t t e d s p a c e w h i c h may be u s e d as t h e i m p l e m e n t o r d e s i r e s . The d e v i c e c r e a t i o n r o u t i n e must a l s o i n i t i a l i z e t h e i n t e r r u p t v e c t o r , and i n i t i a l i z e t h e d e v i c e h a r d w a r e . The i n t e r r u p t v e c t o r i s i n i t i a l i z e d w i t h t h e r o u t i n e A d d _ d e v i c e w h i c h t a k e s t h e d e v i c e d e s c r i p t o r , t h e i n t e r r u p t r o u t i n e , and t h e i n t e r r u p t l e v e l as p a r a m e t e r s . The d e v i c e d e p e n d a n t r e q u e s t s e r v i c e r o u t i n e s h a n d l e t h e .READ_INSTANCE, ,WRITE_INSTANCE, .CONTROL, and .RELEASE_INSTANCE r e q u e s t s . The a p p r o p r i a t e f i e l d s i n t h e d e v i c e d e s c r i p t o r a r e i n i t i a l i z e d t o p o i n t t o t h e s e r o u t i n e s a t d e v i c e c r e a t i o n t i m e . The r o u t i n e s s e r v i c i n g t h e s e r e q u e s t s a r e c a l l e d w i t h t h r e e p a r a m e t e r s : a p o i n t e r t o t h e r e q u e s t message, a p o i n t e r t o t h e d e v i c e d e s c r i p t o r , and a p o i n t e r t o t h e PD o f t h e r e q u e s t i n g p r o c e s s . A l s o n e e ded a r e a RESTART_FUNCTION, a READ_CLEAR_FUNCTION, and a WRITE_CLEAR_FUNCTION. The r e s t a r t f u n c t i o n i s c a l l e d when t h e d e v i c e i s c r e a t e d , t o i n i t i a l i z e i t s h a r d w a r e , and a f t e r power f a i l u r e t o r e s t a r t t h e d e v i c e . The r e a d / w r i t e c l e a r f u n c t i o n s a r e u s e d t o n o t i f y t h e d e v i c e d r i v e r t h a t a p r o c e s s r e a d i n g o r w r i t i n g i t has been d e s t r o y e d . T h e s e r o u t i n e s a r e c a l l e d w i t h t h e d e v i c e d e s c r i p t o r as a p a r a m e t e r . S t a n d a r d r o u t i n e s f o r some o f t h e s e f u n c t i o n s a r e p r o v i d e d a s u t i l i t y r o u t i n e s a t t h e k e r n e l l e v e l . 45 The path of communication with the device i s through i t s read, write, and control functions. Data transfer to and from the device usually occurs after a device interrupts. The data can be stored in a buffer while awaiting the interrupt. The exact data transfer method i s l e f t up to the implementor. The control function can be used for special hardware functions, such as disk track formatting. Control functions are device s p e c i f i c , hence their d e f i n i t i o n i s l e f t to the implementor. U t i l i t y Routines Here i s a detailed description of the u t i l i t y routines available: Add_device D e f i n i t i o n : Add_device( i n t e r r u p t _ l e v e l , r o u t i n e [ ] ( ) , word device[] ) Description: Add_device i n i t i a l i z e s the interrupt vector so that the routine pointed to by routine w i l l be c a l l e d with the workspace pointer pointing to device when an interrupt a the speci f i e d l e v e l occurrs. The parameter i n t e r r u p t _ l e v e l the machine handles. A l l o c d e v i c e D e f i n i t i o n : unsigned Alloc_device() Description: Alloc_device returns the number of a free device descriptor, which i s used as an index into the external table Device_table. If no device descriptors are available, .MAX UNSIGNED i s returned. 46 A l l o c _ b u f f e r D e f i n i t i o n : word A l l o c _ b u f f er () [] D e s c r i p t i o n : A l l o c _ b u f f e r r e t u r n s a p o i n t e r to a f r e e b u f f e r , 80 bytes i n l e n g t h . I f there are no f r e e b u f f e r s , .NULL i s re t u r n e d . F r e e _ b u f f e r D e f i n i t i o n : F r e e _ b u f f e r ( word b u f f e r [ ] ) D e s c r i p t i o n : F r e e _ b u f f e r f r e e s the b u f f e r passed to i t . Not_readable D e f i n i t i o n : unsigned Not_readable( word r e q [ ] , word d e v i c e [ ] , word sender[] ) D e s c r i p t i o n : A dummy r o u t i n e to r e t u r n .NOT_READABLE to a .READ_INSTANCE request . N o t w r i t e a b l e D e f i n i t i o n : unsigned N o t _ w r i t e a b l e ( word r e q [ ] , word d e v i c e f ] , word sender[] ) D e s c r i p t i o n : A dummy r o u t i n e to r e t u r n .NOT_WRITEABLE to a ,WRITE_INSTANCE request. I l l e g a l _ r e q D e f i n i t i o n : unsigned I l l e g a l _ r e q ( word r e q [ ] , word d e v i c e f ] , word sender[] ) D e s c r i p t i o n : A dummy r o u t i n e to r e t u r n .ILLEGAL_REQ to a .READ INSTANCE request . 47 I n t e r r u p t R o u t i n e s T h i s s e c t i o n i s machi n e d e p e n d a n t . The method d e s c r i b e d h e r e i s f o r t h e T I 9 9 0 . The i n t e r r u p t r o u t i n e f o r a d e v i c e i s c a l l e d whenever an i n t e r r u p t i s r e c e i v e d f r o m t h a t d e v i c e . On t h e T I , t h e cod e f o r an i n t e r r u p t r o u t i n e i s c a l l e d u s i n g a s i m u l a t i o n o f a "blwp" i n s t r u c t i o n u s i n g an o f f s e t i n t o t h e i n t e r r u p t v e c t o r . The w o r k s p a c e p o i n t e r t h a t i s l o a d e d i n t h e i n s t r u c t i o n p o i n t s t o t h e d e v i c e d e s c r i p t o r f o r t h a t d e v i c e , hence t h e d e v i c e s t a t e d e s c r i p t o r c o n t a i n s t h e r e g i s t e r s e t f o r t h e i n t e r r u p t r o u t i n e . T h i s e n a b l e s f a s t , e a s y a c c e s s t o t h e d e v i c e d e s c r i p t o r when an i n t e r r u p t o c c u r s . T o a c c e s s t h e p a r t o f t h e d e v i c e d e s c r i p t o r t h a t i s n o t i n t h e r e g i s t e r s e t , t h e "stwp" i n s t r u c t i o n c a n be u s e d t o l o a d t h e w o r k s p a c e p o i n t e r i n t o a r e g i s t e r , f o r use as a base a d d r e s s f o r i n d e x i n g . The p r i m a r y u t i l i t y r o u t i n e u s e d by i n t e r r u p t r o u t i n e s i s a c c e s s e d t h r o u g h t h e e x t e r n a l e n t r y . S t a r t _ h a n d l e r _ e n t r y . T h i s r o u t i n e i s u s e d t o u n b l o c k a p r o c e s s , and i s c a l l e d w i t h t h e b r a n c h i n s t r u c t i o n , i . e . : b . S t a r t _ h a n d l e r _ e n t r y \ u n b l o c k w a i t i n g p r o c e s s The c a l l i n g r o u t i n e s h o u l d have a p o i n t e r t o t h e PD o f t h e p r o c e s s t o u n b l o c k i n r e g i s t e r 9. To r e t u r n f r o m an i n t e r r u p t when a p r o c e s s i s n o t u n b l o c k e d , use t h e "rtw p " i n s t r u c t i o n . The use o f t h e v a r i o u s r e g i s t e r s i s l e f t up t o t h e i m p l e m e n t o r . The r o u t i n e . S t a r t _ h a n d l e r _ e n t r y u s e s r e g i s t e r s 48 7, 8, and 11, hence they are usable only for temporary storage. Registers 13, 14, and 15 are used to store the return address, workspace pointer, and status, and cannot be used for data. 49 A p p e n d i x 2 Example D e v i c e D r i v e r T h i s a p p e n d i x c o n t a i n s t h e s o u r c e c o d e f o r a s i m p l e E I A t e r m i n a l i n t e r f a c e . I t i s i n t e n d e d t o be u s e d as an example t o c l a r i f y t h e d e v i c e i m p l e m e n t a t i o n g u i d e l i n e . An e x p l a n a t i o n o f t h e f u n c t i o n o f e a c h r o u t i n e i s i n c l u d e d b e f o r e t h e r o u t i n e s c o d e . t e m p l a t e E I A STATE { word u n s i g n e d u n s i g n e d word u n s i g n e d u n s i g n e d word u n s i g n e d u n s i g n e d EIA_READER[] ; IN_BUF{}, IN_BUF END{}, IN_PTRT] OUT_PTR OUT BUF OUT_BUF_END{}; \ R6 \ R7 \ R8 \ RO i n i n t e r r u p t r e g i s t e r s \ RI \ R2 \ R3 \ R4 \ R5 REGISTER7, REGISTER8, REGISTER9; \ R9 EIA_WRITER[] ; \ RIO REGISTER11; \ R l l CRU_BASE; \ R12 RETURN_WP[]; \ R13 RETURN PC [] () , \ R14 RETURN ST; \ R15 READ_FUNCTION [] () , WRITE_FUNCTION[](), CONTROL_FUNCTION [] () , RESTART_FUNCTION [] () , RELEASE_FUNCTION [] () , READ_CLEAR_FUNCTION[](), WRITE_CLEAR_FUNCTION[](), F I L E _ T Y P E , IN_BLOCK_SIZE, OUT_BLOCK_SIZE, WRITER_ID, READER_ID, USED, DEVICE_OWNER, DROPPED, SPURIOUS; \ f o r r e s p o n e s t o \ .QUERY_INSTANCE \ r e q u e s t s 50 T h i s i s the template which d e f i n e s the dev i c e dependant f i e l d s i n the EIA dev i c e d e s c r i p t o r . E i a _ c r e a t e ( word req[] , word senderf] ) template EIA_STATE, CREATE_DEVICE_REQUEST, .CREATE_INSTANCE_REPLY, .PD; ex t r n E i a _ r e a d ( ) , E i a _ w r i t e ( ) , N o t _ r e a d a b l e ( ) , E i a _ i n t e r r u p t , N o t _ w r i t e a b l e ( ) , E i a _ r e s t a r t ( ) , I l l e g a l _ r e q () , D e v i c e _ t a b l e [] [] , Mux r e a d _ c l e a r ( ) , Mux_write_clear () , Mux_release(); word devTce[]; unsigned device_id; i f ( ( d e v i c e _ i d = A l l o c _ d e v i c e ( ) ) == .MAX_UNSIGNED ) r e t u r n ( ,NO_MEMORY ); device = D e v i c e _ t a b l e [ d e v i c e _ i d ] ; DEVICE_OWNER[device] = .ID[sender]; READ_FUNCTION[device] = ( .FILE_MODE[req] & .READ ) ? &Eia_read : &Not_readable; WRITE_FUNCTION[device] = ( .FILE_MODE[req] & .CREATE ) ? &Eia_write : &Not_writeable; READ_CLEAR_FUNCTION[device] = &Mux_read c l e a r ; WRITE_CLEAR_FUNCTION [device] = &Mux_wr i"Ee_clear; CONTROL_FUNCTION[device] = & I l l e g a l _ r e q ; RELEASE_FUNCTION[device] = &Mux_release; RESTART FUNCTION[device] = &Eia r e s t a r t ; IN_PTR[ elev i c e ] = OUT_PTR[deviceT = IN_BUF [device] = A l l o c _ b u f f er () ; IN_BUF_END[device] = IN_BUF[device] + BUFFER_SIZE - pun( u n s i g n e d f ] , 1 ); EIA_READER[device] = EIA_WRITER[device] = 0; CRU_BASE[device] = HARDWARE_LOCATION[req]; Add_device( INTERRUPT_LEVEL[req], & E i a _ i n t e r r u p t , d e v i c e ); E i a _ r e s t a r t ( d e v i c e ); ,FILE_SERVER[req] = DEVICE_SERVER; .FILE_ID[req] = d e v i c e _ i d ; FILE_TYPE [device] = .FILE_TYPE [req] = TERMINAL__TYPE; IN_BLOCK_SIZE[device] = OUT_BLOCK_SIZE[device] = .FILE_BLOCK_SIZE[req] = 4 * .BYTES_PER_WORD; DROPPED[device] = SPURIOUS[device] = .FILE_LAST_BYTES[req] = ,FILE_LAST_BLOCK[req] = ,FILE_NEXT_BLOCK[req] = 0; re t u r n ( .OK ); T h i s r o u t i n e i s c a l l e d when a c r e a t e i n s t a n c e request i s r e c e i v e d f o r an E I A t e r m i n a l i n t e r f a c e s h a r e s s e v e r a l d e v i c e A x i s m u l t i p l e x o r (mux) t e r m i n a l E i a _ r e s t a r t ( d e v i c e [ ] ) \ I n i t i a l i z e an e i a t e m i n a l { t e m p l a t e EIA_STATE; u n s i g n e d b a s e , chan; 51 i n t e r f a c e . N o t e t h a t t h e E I A d e p e n d a n t r o u t i n e s w i t h t h e i n t e r f a c e . » i n t e r f a c e . b ase = C R U _ B A S E [ d e v i c e ] ; c o d e ( .MOV., " r l 2 " , b a s e ) ; c o d e ( .SBO., EIA_DTR ) ; c o d e ( .SBO., EIA_RTS ) ; c o d e ( .SBO., E I A ENABLE ); T h i s r o u t i n e i n i t i a l i z e s t h e E I A h a r d w a r e . I t i s c a l l e d when t h e d e v i c e i s c r e a t e d , and when t h e s y s t e m r e c o v e r s a f t e r a power f a i l u r e . 52 E i a _ w r i t e ( word r e q [ ] , word d e v i c e [ ] , word s e n d e r f ] ) t e m p l a t e E I A_STATE, .IO_REPLY, .IO_REQUEST, .PD; u n s i g n e d base, p{}, c o u n t ; i f ( E I A _ W R I T E R [ d e v i c e ] ) r e t u r n ( .BUSY ) ; p = &.IO_BUF[req]; c o u n t = . I O _ B U F _ L E N [ r e q ] ; base = C R U _ B A S E [ d e v i c e ] ; c o d e ( .MOV., , , r l 2 " , b a s e ) ; code ( .TB., EIA_XMTING ) ; \ T e s t i f t r a n s m i s s i o n i n p r o g r e s s c o d e ( .JEQ., s e t u p ) ; o u t p u t c h a r : coHe( .LDCR., 8, " r i a G " ); — c o u n t ; s e t u p : i f ( c o u n t ) { .REPLY_CODE[req] = .OK; WRI T E R _ I D [ d e v i c e ] = .ID[ EI A _ W R I T E R [ d e v i c e ] = s e n d e r ] ; O U T _ B U F [ d e v i c e ] = p; OUT_BUF_END[device] = p + pun( u n s i g n e d [ ] , c o u n t ); . S T A T E [ s e n d e r ] = WRITING_DEVICE; .BLOCKED_ON[sender] = pun( u n s i g n e d , d e v i c e ); r e t u r n ( ,NO_REPLY ) ; e l s e r e t u r n ( .OK ); T h i s r o u t i n e i s c a l l e d i n r e s p o n s e t o a .WRITE_INSTANCE r e q u e s t on an E I A i n t e r f a c e . 53 E i a _ r e a d ( word r e q [ ] , word d e v i c e [ ] , word s e n d e r [ ] ) t e m p l a t e E I A_STATE, .IO_REPLY, .IO_REQUEST / .PD; i f | O U T _ P T R [ d e v i c e ] == I N _ P T R [ d e v i c e ] ) i f ( E I A _ R E A D E R [ d e v i c e ] ) r e t u r n ( .BUSY ) ; R E A D E R _ I D [ d e v i c e ] = .ID[ E I A _ R E A D E R [ d e v i c e ] = s e n d e r ] ; . S T A T E [ s e n d e r ] = READING_DEVICE; .BLOCKED_ON[sender] = pun( u n s i g n e d , d e v i c e ); ^ r e t u r n ( ,NO_REPLY ); R e a d _ c i r c u l a r ( r e q , d e v i c e ) ; r e t u r n ( .OK ); T h i s r o u t i n e i s c a l l e d i n r e s p o n s e t o a .READINSTANCE r e q u e s t on an E I A i n t e r f a c e . u n s i g n e d M u x _ r e l e a s e ( word r e q [ ] , word d e v i c e [ ] , word s e n d e r [ ] ) t e m p l a t e MUX_CHAN_STATE; U S E D [ d e v i c e ] = .FALSE; F r e e _ b u f f e r ( I N _ B U F [ d e v i c e ] ); r e t u r n ( .OK ); } A s i m p l e r o u t i n e t o r e l e a s e s t o r a g e when d e v i c e i s removed, i n r e s p o n s e t o a .RELEASE_INSTANCE r e q u e s t . M u x _ r e a d _ c l e a r ( d e v i c e ) t e m p l a t e MUX_CHAN_STATE; MUX_READER[device] = 0; C a l l e d when a p r o c e s s r e a d i n g an E I A i n t e r f a c e i s d e s t r o y e d t o i n f o r m t h e d e v i c e h a n d l e r . 5 4 Mux w r i t e c l e a r ( d e v i ce ) r template MUX_CHAN_STATE; MUX_WRITER[device] = 0; C a l l e d when a process w r i t i n g an EIA i n t e r f a c e i s destroyed to inform the de v i c e handler. 55 B i b l i o g r a p h y 1. C h e r i t o n , D. R. D e s i g n i n g an O p e r a t i n g S y s t e m t o be V e r i f i a b l e . T e c h n i c a l R e p o r t 79-9, 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 , V a n c o u v e r , 1979. 2. L o c k h a r t , T. W. The D e s i g n o f A V e r i f i a b l e O p e r a t i n g S y s t e m K e r n e l . T e c h n i c a l R e p o r t 79-15, 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 , V a n c o u v e r , 1979. ( b a s e d on M.Sc. t h e s i s 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 , 1 9 7 9 ) . 3. C h e r i t o n , D. R. V e r e x S e r v e r s . T e c h n i c a l R e p o r t 8 1 - ? ? , 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 , V a n c o u v e r , 1981. v 4. 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 t h e T h o t h o p e r a t i n g s y s t e m . T e c h n i c a l R e p o r t 79-5, 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 , V a n c o u v e r , 1979. ( b a s e d on Ph.D. t h e s i s U n i v e r s i t y o f W a t e r l o o , 1 9 7 8 ) . 5. R i t c h i e , D e n n i s M. The UNIX I/O S y s t e m . B e l l L a b o r a t o r i e s , 1975 6. B r i n c h H a n s e n , P. The n u c l e u s o f a m u l t i p r o g r a m m i n g s y s t e m . C o m m u n i c a t i o n s o f t h e A.C.M. 13, 4 ( A p r i l 1970) . 7. F a l k , G i l b e r t . The S t r u c t u r e and F u n c t i o n o f Network P r o t o c o l s . Computer C o m m u n i c a t i o n s Wushow Chou, e d . P r e n t i c e - H a l l , I n c . , 1983. 8. R i t c h i e , The UNIX T i m e _ S h a r i n g S y s t e m C o m m u n i c a t i o n s o f t h e A.C.M. 17, 7 ( J u l y , 1 9 7 4 ) . 9. D e e r i n g , S t e p h e n E . M u l t i - P r o c e s s S t r u c t u r i n g o f X.25 S o f t w a r e . T e c h n i c a l R e p o r t 82-11, 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 , V a n c o u v e r , 1982. 10. C h e r i t o n , D. R. D i s t r i b u t e d I/O u s i n g an O b j e c t - b a s e d P r o t o c o l . T e c h n i c a l R e p o r t 81-1, 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 , V a n c o u v e r , 1981. 11. D i j k s t r a , E . W. The S t r u c t u r e o f t h e "THE" M u l t i p r o g r a m m i n g S y s t e m . C o m m u n i c a t i o n s o f t h e A.C.M. 11, 5 (May 1 9 6 8 ) . 12. M a d n i c k , S t u a r t E . D e s i g n S t r a t e g i e s f o r F i l e S y s t e m s . P r o j e c t MAC, TR 78, M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , M a s s a c h u s e t t s , 1980.