PRELIMINARY REPORT ON THE J A N O S OPERATING SYSTEM By J.N.E. Bos and N.T. Ferguson april 1984 ----------------------------------------------------------------------- This document has been written in English for the following reasons: - In the computerworld there are a lot of English (American) terms wich have a narrowly defined meaning. Normally these terms have no proper translation in Dutch - A Dutch document with English terms is difficult to read and the resulting language would be difficult to pronounce, as you would have to switch from dutch pronounciation to english and back. Furthermore we do not think it advisable to mix two languages as this could develop into a bad habit. - Anyone who knows enough about computers to be interested in this document may be assumed to be able to read english effordlessly, as virtually all literature on this subject is written in English. - English has become the standard language in the computerworld. Having had first-hand experience with incompatabilities we see no reason why we shouldn't write this in English. Note: Due to the limited processortime allocated to us this document was typed directly instead of being prepared on a wordprocessor. Typing mistakes may therefore occur. A list explaining the difficult tecnical terms can be found in appendix A. Aim. To build a multy-user multy-task operating system on a Z80. As no fast disks are available everything is held in memory. The system has been designed to be used with a slow external memory such as a taperecorder or a floppy disk. Underlying hardware. JANOS is being developed for two computersystems, the Ordinator computer at DJO Eindhoven and for the JEC 3.0 being built privately by J. Bos. The main hardware features of both systems are: - Z80 CPU (Normally at 4 MHz) - Interrupt controlled I/O. There is no polling at all. - A (programmable) timer interrupt. - An MMU (Memory Mapping Unit) extending the amount of addressable memory to 512 Kb (Kilobytes=1024 (2^10) bytes). The MMU works as follows: The highest 4 addressbits of the Z80 are used to address a small but very fast RAM. This RAM has 8 outputbits. One is used for writepro- tection and the 7 other for addressing memory. The resulting address- bus is 19 bits wide. The 12 lower addressbits of the Z80 form the lower addressbits of the addressbus and the MMU the other 7. ----------------------------------------------------------------------- By changeing the contents of this RAM through an I/O port it is possible to map any 4 Kb segment of the memory into one of the 16 positions in the CPU memory layout. Setting the writeprotectbit of a position makes it impossible to write into that segment of the memory. Other systems. The only other systems we looked at were UNIX and CANDE (B7700 at the THE). Looking at CANDE wasn't very helpful as this is a much larger system. The only thing we learned was how not to present system output to the terminal. UNIX was more interesting as it was designed for minicomputers. We took over the idea of popelines and extended this to graphs. (A graph is like a pipeline but instead of being onedimensional it is multidimensional. It turns out, however, that graphs are nearly impossible to type as a single string of characters. To be able to use graphcs probably requires a totally different shell.) Our main criticisms of UNIX are the chaotic use of controlcharacters in the shell and the extenseve administration it keeps with every file. Main problems - As everything is stored in memory a very large administration is necessary. (Most other systems keep most data on hard-disks.) The datastructure has to be so that administration is minimal but at the same time memory should not be wasted and access to the data has to be fast. (Administration is simple if memory is allocated in large chunks. This, on the other hand, uses a lot more memory than is necessary.) - Many ways of memoryorganisation require a packer. This is a program that scans through all the memory and rearanges the order of the data so that the unused memory comes together in large chunks. Packers are very difficult to test and if they make a mistake it normally is fatal to the system. As they have to scan through and move nearly all the mamory they take a long time to run. During this time the administration isn't correct so no program can run. Apart from being very irritating for the users (the packer may well require up to a minute of processortime) this makes fixed- speed I/O such as taperecorders and disk very difficult. - There are many different kind of things to store. (files, directo- ries, FIFO's for making pipelines, temporary buffers for I/O de- vices, program code, information about files, program and tasks, the administration itself etc. etc. The problem is to find a logical datastructure to store these and to limit the number of datatypes at the same time. - The system has to be careful about tasks reading from and writing to loose ends. (A loose end is a FIFO where there is no task on the other side.) To make it easy to detect extra administration is necessary. - The system has to make sure it doesn't lose a piece of memory. If it forgets that a certain piece is used or free this is a time- bomb wich will explode later on. This kind of errors are the most difficult to find as you have no idea when the fault occurred. ----------------------------------------------------------------------- We now come to our solution. We will bring it in three parts. An outline, then we will discuss the interaction of the different parts and finally we will look into the way the system stores it in memory. Outline. There are three basicly different things in the system. - The programs wich are run - The files and FIFO's wich hold the data for the programs. - The directory wich is used to find the programs and files in memory. Task When the user instructs the system to run a program the system starts up a task. A task is any machine-code program wich is being run. Several tasks can be run at the same time. Also several tasks can use the same programcode. Thus an editor wich is used by two users is only stored once in memory. For the user it looks as if all active tasks are run at the same time. In fact only one task is run at a time and after a certain time that task is stopped and the next task started. A task can be active or waiting. It is active if it isn't waiting and it is waiting when the task can't continue for one or another reason. (Lack of input for example) Tasks can have different prioritylevels. Only tasks of the highest priority level in wich there is an active task are run. If a task starts up another task this will be it's child. If a task is aborted or killed all it's children are killed too as the have lost their meaning. To communicate with JANOS a task can make systemcalls. This is the only way for a task to affect anything outside it's own memory. The only I/O a task has is through an UFI. (UFI's will be discussed later) A task also has a standard input and a standard output UFI. These are used for the main I/O and for pipelineing. For the task the UFI's it has access to are numbered 0,1,2 etc. For every number there is a read and a write UFI. UFI number 0 make up the standard in and out UFI. If a task needs more RAM it can ask for more. In this respect there are two classes of tasks. Approved tasks wich have been generated by a compiler or wich have been approved by the systemprogrammer. These tasks are garanteed not to write outside their allocated memory. These tasks get memory in small chunks. Unapproved tasks are all tasks wich have been written by an unapproved compiler or directly in machinecode. If these tasks need RAM they get a segment at a time and no other data is stored in that segment. Thus it won't harm the system if this task crashes. UFI UFI is the abbreviation of Universal File. Although an UFI isn't as universal any more as it was when we invented it we still kept the name. An UFI wich can be found in the directory is called a file. UFI's are used for datastorage and for buffering. They also make the FIFO's necessary for pipelining. An UFI has a read and a write task. The writetask is the only one allowed to write into the UFI. The read task is the only one allowed to read destructively from the UFI. (destructively means that after the data has been read by the task it is removed from the UFI.) ----------------------------------------------------------------------- The following things can be done with an UFI: - The write task can write appending to the end of the UFI. (The data that the write task writes is put at the end of the datablock already in the UFI. - The read task can read destructively from the beginning of the UFI. - The read task can set a pointer, the 'current' pointer anywhere in the UFI and read from it. The read task is the only one wich can affect this pointer. - Any task can read any byte from the UFI provided it can find the UFI. This way of access is relatively slow when the UFI is large. The size of an UFI is only limited by the size of the memory of the computer. To make a FIFO one task is made the write task of an UFI and another task is made the readtask of that UFI. If the writetask writes into the UFI and the readtask reads from it destructively the FIFO effect has been achieved. This makes it possible to use FIFO's with no sizelimit. A task can get access to an UFI in three ways. It can create the UFI itself. It can get the UFI from it's parent on startup of this task. It can find the UFI as a file in the directory. An UFI also has an owner. The owner is the task wich determines who is the readtask and who is the writetask. Also the owner can put the UFI in the directory and make it a file. In this way other tasks kan get access to the UFI even after the owner has been killed. Directory What we have been calling the directory until now is in fact a number of directories. A directory is a set of directoryentries. Any directoryentry can contain one of the following: - An UFI. The UFI and the directoryentry together form a file. - A program. This contains the code of a certain program. - A directory. There is one main directory called root. All other directories are subdirectories of another directory (possibly root). One UFI, program or directory can be represented by one or more directoryentries in one or more directoryentries. These directory- entries may have different levels in respect to the root. However, no directory may contain itself in any way. Every directoryentry has a name wich is unique in the directory con- taining this entry. The name is used to find a particular entry in a directory. ----------------------------------------------------------------------- We will now look into the system in more detail and see how all this is stored. The entire memory is divided up into cells. Each cell is 8 bytes long and has a startingaddress of the form 8xN where N is the cell- number. Cellnumbers range from 0-65535. (65535=2^16-1) It is defined that if there is RAM at address 0 the systemprogram of JANOS is loaded there. The reason for this is that a pointer to cell 0 is used to indicate an empty link. (meaning that the object the pointer is supposed to be pointing to doesn't exist) From now in the word 'link' will be used to indicate a pointer to a cell. The link contains the cellnumber. If it points to an object wich occupies more than one cell the link points to the first cell. Keeping the same order as before we will start with the tasks. Every task has a Task Information Block or TIB. All TIB's are linked in a linear list. (Every TIB has a link to the next TIB in the list.) In the list the TIB's are sorted from high to low priority. In every TIB there is a prioritybit. If this bit is set it indicates that this TIB is the last one in this priority- level. A lower prioritylevel follows. This system doesn't restrict the number of prioritylevels. When a task is started up it is given the same prioritylevel as it's parent or a lower one. The only thing a task can do with it's priority is to decrement it. A TIB contains: - A link to the next TIB in the TIBlist. - A link to the list of children of this task. All the children have a link to the next child of this task. This list is used to abort all children (and grandchildren and so on) of a task if the task is aborted. - A link to the next child of it's parent - A link to the parent of this task. This is necessary to make it possible for a task to wait for one of it's children to finish. - A link to the first piece of RAM used by this task. This link is meaningless if this task is unapproved. If it is approved every piece of RAM it uses has a link to the next piece. - The linklayout. This is a list of segments that are mapped into the CPU memory when this task is running. (This is equal to the contents of the MMU when the task is running) - A link to a directoryelement wichrepresents the programcode this tasks uses. This link is also used to give the task a name as every directoryelement has a name. - A pointer to the home directory. That is to say, a link to the directoryelement wich represents the home directory. THis home- directory is used to place files in containing error messages and such. - Pointer to the current directory. (=link to directoryelement repre- senting the current directory) This pointer can be changed by the task. The task uses it to find files wich are not in it's home- directory. - A pointer to the current directoryentry. This pointer points to a directoryelement in the current directory with wich the task wants to do something. - The status of the task. This contains among others: - A bit wich indicates if this task is waiting for something. ----------------------------------------------------------------------- - A bit wich indicates if this task is approved or not. - The bit wich indicates if a lower prioritylevel is following. - A bit to indicate if this task was interrupted during a systemcall. If this is so the restarting of the task is a litte bit different from normally. --------------- At this point a new cell starts. The reason for this is that the following cell is the first element of the UFIlist and it is easier if the startingaddress is standardised. An element of the UFIlist contains: - A link to the next element of the UFIlist. - A link to the UFI in wich data is written if the task uses this number to write to - A link tot the UFI from wich data is read if the task uses this number to read from - The status. This is not defined yet and not needed yet. It is reserved for later expansion. The first element of the UFIlist follows the TIB. This was done to decrement the number of links in the system and that way speed it up. The first element is number 0, the next 1 etc. etc. These numbers are used by the task to refer to the UFI's For every number there are two UFI's. One to read from and one to write to. Number 0 are the standard in and the standard out UFI's. The UFI's represented by one number may be the same. The UFI's are stored in the following way. Every UFI has a Ufi Controll Block or UCB. The data itself is stored in datablocks. An UCB contain: - A link to the TIB if it's owner. - A link to the TIB of it's read task. - A link to the TIB of it's write task. - The number of pointers or links wich point to this UCB. This number is kept updated all the time and if it is decremented to zero the UFI is killed.As noone knows where to find the UFI it isn't useful any more. - A link to the last datablock. This is the datablock in wich the last byte of the contents of the UFI is stored. - An index in that last datablock. This index tells the system what byte in the datablock is the last byte of the UFI. - An index in the first datablock of the UFI telling the system where to find the first byte of the UFI in that datablock. - A link to the datablock in wich the 'current' pointer is poining. - An index in that datablock to what byte the currentpointer is pointing. Following this UCB is the first datablock. It starts at the beginning of a new cell. It contains: - A link to the next datablock. - A number of bytes data. (normally 254) In the first datablock the first few bytes may not belong to the contents of the UFI. In the last datablock the last few bytes may not belong to the UFI. ----------------------------------------------------------------------- The contents of a directoryentry is as follows: - A link to the next directoryentry in this directory - A name - A link to the 'contents' of this directoryentry (An UFI, program or directory) - status containing among others: - The type of the contents of this directory. - The number of pointers to this directoryentry. This number is kept updated and if it decrements to zero the directoryentry is killed. If the Directoryentry contains a directory the link points to the forst directoryentry of that directory. A program is stored in the following way: - Status (Is this programcode approved or not) - number of links to this block. (One program may re represented by more than one directoryentry. If this number is decremented to zero the program is thrown away. - The amount of initial RAM the task needs - The length of the program - The programcode itself. All the free RAM is linked in a list. The smallest pieces are at the beginning of the list and the larger ones at the end. As these links are stored in free memory they do not occupy any memory wich the system might want to use. If a piece of memory comes free it is put in the list at it's proper place after it has been checked that it doesn't form a larger piece of free memory together with another piece already in the list. When a piece of memory is needed the first piece in the list is used wich is large enough. This ensures the optimum use of the memory. ----------------------------------------------------------------------- Appendix A. This appendix contains a list explainig some of the tecnical terms. They are arranged in order of appearance in this report. JANOS is the abbreviation of Jurjen and Niels Operating System. INTERRUPT is a way to force the CPU to service the hardware. POLLING is going around in a loop asking every device if the processor can do something for it. Very timeconsuming. ADDRESSBUS A number of lines in the computer used to address memory. SEGMENT any 4Kb piece of memory wich has a startingaddress of the form 4096xN where N is the segmentnumber. PIPELINE several tasks wich form a chain are called a pipeline. The output of the first task is the input of the second one and so on. FIFO abreviation of First In First Out. It is a buffer in wich the data wich was written into it first comes out first as opposed to FILO's (First In Last Out) SYSTEMCALL A subroutine wich is provided by the system. It performs certain tasks wich the task itself cannot do. ROOT The root directory. If you see the directorysystem as a tree this directory forms the roots of the tree.