22/1/95 Things I've added previous to uploading this are marked with a ###. This is public domain. Not even freeware. Do with it whatever you will. I'd like to know if somebody does touch it up (so to speak), however. This is a slightly updated version of a *very* old document. Bits that are now misleading are marked *WIBBLE* with notes like [foo]- mcy More notes at the bottom... Overview ======== The kernel is capble of pre-emptively multi-tasking with up to 16 processes. This limit is hardwired into the source but not the design, so more would technically be possible. A mechanism for passing messages between processes is included. There are functions to allocate and de-allocate pieces of memory in 512 byte blocks. Kernel routines are entered via the trap instruction. A non-kernel library system is implemented essentially as a macro system, but also so that those functions that don't require to be running in the kernel (which locks it to other tasks) aren't. System calls ============ Functions marked with X are not yet implimented. Functions 0 to 5 can be emulated by funtion 11. Arguments are passed by pushing them onto the stack and then executing a trap instuction. # Name Function Args Returns (in r0) 0 hear_con Accept messages from --- --- X the console 1 hear_term Accept messages from --- --- X the terminal 2 hear_clock Accept messages from --- --- X the clock 3 hear_trans Accept messages from --- --- X the transmission line 4 hear_IPC Accept messages from --- --- X other processes 5 say_IPC Send a message to type,data, --- other processes cookie 6 sleep Go to sleep new status --- 7 clear_msg Clears all messages --- --- for process 10 read_msg Reads a message --- pointer to msg 11 set_ptab Write to word to your data,entry --- process table entry 12 read_ptab Reads an entry from entry data your process table 13 start Launches a new process addr,stack size child pid envronf 14 stop Kills a process pid --- 15 non_kernel Returns the address of --- addr the non-kernel library routines 16 free_cookie Unregesters a cookie cookie# --- X for re-use 17 mem_req Request a piece of size/256 addr/NULL memory. [should be even] 20 mem_free Frees a piece of addr --- memory reserved by mem_req. 21 make_cookie Generates a new unique --- cookie magic number. 22 find_msg_ Searches the msg list type msg/NULL type for a specific message type. 23 find_msg_ Searches the msg list cookie msg/NULL cookie for messages with a specific cookie. 24 find_msg_ Searches the msg list type,cookie msg/NULL both for messages with a (or the other specific types and way around!) cookie. Message types *WIBBLE* ============= [basicly still this method, but all the bits have changed meaning to include block/file IO and stuff] This is a bit significant mask used when sending/receiving messages. Only those messages with a mask that matches a bit set in the processes table entry (+10) are actually sent to that process. Bit Octal Name 0 1 con_in - messages from the console i.s.r. 1 2 con_out - messages to the console output i.s.r. 2 4 term_in 3 10 term_out 4 20 clock_tick - messages whenever the clock interrupts 5 40 trans_in - transmission line 6 100 trans_out 7 200 IPC - process to process messaging. 8... not used ### Okay basically what's happened if this. All the channels but one are used by deviceio internals. One is left over for general inter- process communications. The cookie table feature should be used to filter out unwanted messages. The cookie table feature works like this: each running process has a cookie table in its environment block. Only messages with a cookie that matches one in the table are put onto that processes message list. Hence fuctions 22,23 and 24 for pulling out message of a specific type. It's important not to leave too many unread messages hanging about though. Cookies with messages *WIBBLE* ===================== [Also much the same in theory,, but more most message types use the cookies] A message consists of 4 16bit words 0 - Message type mask (see above) 2 - Message data 4 - [kernel use only] Pointer to next message 6 - Message cookie The cookie is currently used only with IPC messages. It states the type of message, in the context of the recieving/transmitting tasks. It allows processes to identify messages when recieving from more than one source. Each process also has a cookie list. A pointer to this is stored in the process table (+16). It is a zero terminated list of 16 bit cookies. Only if the message cookie matches something in this list will the process recieve the message. Cookie 0 goes to all IPC receptive processes. Several cookies are reserved. Fresh cookies can be obtained from the system call new_cookie (16 octal, not yet implimented :-) ### oh yes it is! Reserved cookies: 1 - messages to the console_device 2 - messages from the console_device 3 - messages to the terminal_device 4 - messages from the terminal_device Process status *WIBBLE* ============== [after some scheduler/switcher streamlining this is now utter tosh] At any time a process may have value 0 to 4: 0 - This process is dead, the slot is available 1 - Processes is asleep until it recieves a message (or >1) 2 - Process was pre-empted. It did not sleep on it's own. 3 - Process has low-level IO pending. It will be woken up as soon as possible 4 - The process is being altered by the kernel. It's slot should not be touched. Non-kernel library ================== There are a selection of completely re-entrant routines that are available to processes without entering the kernel proper i.e. the register values are not changed and the context is not switched on entry. They are intended to make programs short by providing commonly used function. A pointer to a jump table can be obtained from system call 15 (octal). 0 - LIB_write Writes the character in r0 to stream in r1. 1 - LIB_read Reads a character from stream in r1 result->r0. 2 - LIB_hex_output Display the contents of r0 as a hex number on stream r1. 3 - LIB_string_output Display string pointed to by r0 on stream r1. 4 - LIB_string_input Reads a CR terminated string from stream r1 to memory pointed to by r0. No range checking is performed. 5 - LIB_clear_cookies Clears the cookie table. Note this doesn't actually free the cookies; it just removes them from the list. 6 - LIB_add_cookie Puts a cookie (in r0) in the processes cookie list. Note: doesn't generate a cookie, merely add to the list. 7 - LIB_remove_cookie Removes a cookie (in r0) from the process' list. A less extreme from of 5. 10 - LIB_open_file Open the filename pointed to by r0. A file handle is returned in r0. Note: this is *very*very* heavily tied to the file system emulator. 11 - LIB_close_file Closes a file associated with handle in r0. Device processes *WIBBLE* ================ [changed slightly with the introduction of block IO and remote (ish) terminals] There are terminal and console device processes. These send IPC messages with reserved cookies whenever they receive messages from the i.s.rs. When they recieve IPC messages with to_x reserved cookies, they output the message data to the hardware. The clock has an interrupt service routine that sends clock_tick messages, so time based pre-emption is implimented when the clock in turned on at the panel, however there is no process-level support for it (yet). Priority, status, the scheduler *WIBBLE* =============================== [this is now completely untrue] Each process has a status (most significant) and a priority (least significant) that the scheduler uses to decide which process will be the next to run. In order: Status Name Reason 3 IO pending User input is delt with quickly 1 msg pending Messages are clear away quickly with msgs 2 pre-empted CPU bound processes are done eventually with msgs 2 pre-empted without msgs 1 msg pending There is nothing else to do at this point without msgs Whenever there is more than one process with the required status and message/no messages, the one with the highest priority is run. When a task is switched out (for whatever reason) its priority is decremented, until it reachs zero, when it is reloaded from the priority reload field in the process table (+14 octal). Priorities of around 16 seem to work well for device processes. For user programs, lower values should be used for processes that often become CPU bound, and higher ones for messaging tasks which enter the kernel lots (where they are switched out, and their priority decremented). ### okay, the basic ideas are much the same, but for the purposes of optimisation something like this happens: When a new processes is given the CPU, a counter is set, which under normal conditions will cause a switch when it reaches zero. The process table is not re-evaluation under the counter reaches zero (saves time). If something significant happens (i.e. blockIO arrives) then the counter is forced to 1. It will then be decremented to zero on the way out of the interrupt and thus initiate an immediate switch, probably to the blockIO device, seeing as the interrupt service routene will have push its priority up. The process table *WIBBLE* ================= [only slightly reliable] It looks like this (it has 16 entries) 0 : Pointer to stack (where registers are stored on switch) 2 : Process status 4 : Message pointer (start of linked list) 6 : Top of stack (used for mem_free when process is stopped) 8 : Message type mask 12 : Priority countdown 14 : Priority reload 16 : Pointer to IPC cookie list The user programs *WIBBLE* ================= [not a grain of truth in here] At the moment there are two user programs (started at boot time, near label "boot:"). One allocated some memory, frees some of it, and displays the addresses of these blocks on the terminal, then busy loops with a "br .". The other waits for a key to be pressed on the terminal, then dumps the whole process table to the terminal in hex. This goes very slowly. The second user program busy looping in the background doesn't help, and possibly the priorities are wrong. It is even possible that the kernel is grossly inefficient. ### Added last of all: This has been replaced by a kind of proto-shell that will dump the process table "P ", the memory list "M " and run files by filename " return" The mechanism for loading object code does no relocation, so you're code will have to be position independent. This could do with improving, probably by adding a LIB_loadcode function to the library. ---- Extra things ============ Since this was originally written the OS has gained a file system emulator, more LIB_ functions, a different scheduler algorithm, something approaching a proto-shell and generally more fastness. Many specific details have changed. If anybody is still interested then I get dig out the scribbled notes I made at the time as these constitute the nearest thing to correct information. The file system emulator is braindead. I threw it together in about three days before the end of term i.e. when I ceased to have access to the machine. I got it to the point where one can type a filename and have it executed on the LSI (after pulling the file across the transmission line from the Sun). It expects, as it stands, a console physically attached to the LSI and a Sun on the other end of a serial line where the demons (there're in the archive too) deal with parsing of packets, retrieval of file and so forth. The C source for the Sun was written even more quickly and more nastily than the LSI code. You have been warned. I don't normally write code this badly. Honest. ### The best way to find out what's going on is to look at the source. If you do have any queries then feel free to mail me. I have some extra more up-to-date notes on paper. ### There are one or two example programs including the usual "Hello world" one. This uses the stdout mechanism and is runable from the proto- shell. It should work on an terminal attached to the system, provided it's environment has been correctly set up (you'll need to add a environment block somewhere is the source to say where your terminal is). Adding a new physical terminal will also require you to add a new set of definitions and space as line 419 (I've got the source in the other window!) Terminals on the transmission line will send packets to the termt device driver (it deals with single character only packets and passes them on to termx, which is where characters from the physical terminal go straight to, from the isrs). Other blocks from the blockio driver go to the fake file system (the first half of it which deals with opening new files). read calls use the second part of the filesystem which deals (badly) with buffering and file pointers. Problems ======== There are some problems with the design of this: All kernel, user data and code shares a common 64Kb address space. The design of the kernel would allow splitting across different banks provided: i)messages are actually copied to local addresses before the pointers are given to user processes, ii) the memory manager is told about having separate maps for each process, iii) erm... Actually this'd be quite alot of work wouldn't it? Processes cannot be blocked on the basis of having sent too many messages. Buffer high and low water marks would have to be dealt with via handshaking. The message space can easily become full if processes refuse to read some messages. The transmission-line device drivers send ACKs, but the UNIX end doesn't handle them properly, and the ACK packets themselves don't say what is being acknowledged. Priority levels and the like are quite hard to tune.