Programs: ROBOS

A multi-tasking multi-processing message-driven real-time operating system and building frame for specialised PC-based applications. Topics: introduction, the message-driven finite-state machine, the message exchange, messages, input/output services, message processing functions, applications.


Robos is a development code name. It stands for Rob's Operating System. Robos runs as an application on a normal host operating system. It is a very compact operating system which is closely linked with the applications it runs.

All Robos applications - and a good proportion of Robos itself - are made up of software objects of a kind known as message-driven finite-state machines [MFMs]. Each MFM runs as an independent task. Robos currently makes provision for running up to 255 such tasks at once.

The kernel of Robos is a message exchange which provides an orderly channel through which MFMs pass messages between each other. Some MFMs perform general services, some perform applications-related services. Others perform the input/output services needed to allow applications to accept messages from, and send messages to, the external world.

An MFM comprises a set of data instances and a set of message processing functions [MPFs]. On receiving a valid message from the central Message Exchange, an MPF updates the appropriate data instance and then puts an appropriate output message on the Message Exchange's message queue.

Each data instance is designed as a logical machine which can at any given time be in any one of a small finite number of complex logical states. While in a given state, such a machine may receive a message of any one of a prescribed number of valid types. Such a message may simply supply data, trigger a change-of-state, or both.

Robos, and each of its applications is developed as a formal set of source files. The Robos message exchange, input/output services and internal MFMs are kept as an object library. Each application MFM is then developed as a separate file-set. It is then compiled and linked with Robos as an overlay object or compiled as a "class" file to be linked dynamically at run-time.

NOTE: Robos was conceived during the mid-eighties and written in the early nineties. Today's object-oriented programmers may recognise the Robos 'MFM' as a special case of what has become known nowadays as a class, and its data instances as objects of that class. Similarly, MPFs may be recognised as what now would be know as the class's constructors and methods.

The Message-Driven Finite-State Machine

An MFM comprises one or more identical data sets, each of which is serviced by a common group of message processing functions. Each such data set alone is known as an 'instance' of the MFM. The adjacent diagram shows an example of a 4-state 3-instance MFM. At any given time, an MFM 'instance' can only be in one of a small (finite) number of discrete 'states'. Hence the term Finite-State in its name. For example, an instance of a typical 3-state MFM could, at any given time, be in its initialisation state, its main state or its termination state.

The particular processing which is required to be done when an MFM instance is in a given state is performed by a corresponding message processing function [MPF]. Thus, each MFM state has an associated 'C' function which does the processing required when an instance of the MFM is in that state.

A message processing function receives a message, does some processing on it, updates the MFM's instance data, and then outputs the results as another message. A ROBOS-based application is therefore driven entirely by messages, which are continually received into and dispatched from a single central message queue. Thus, at the heart of Robos, there is a message queue and a message dispatcher function which together form a central Message Exchange.

Generic Structure of an MFM

MFMs are written one MFM per source file. An MFM source file contains the following parts:

Part 1: A definition of the structure of its instance data followed by a declaration of storage for all its data instances:

struct instance_data {
  int machine_state;          //Current machine-state
} instances[16];              //Declare 16 instances

If, for a particular application, the maximum number of data instances is unknown or fluid, storage can be allocated dynamically as and when required. This would be done by a call similar to the following:

struct instance_data _far 
  *hInst = (struct instance_data _far *)
           _fmalloc(sizeof(struct instance_data));

Part 2: A prototyped declaration of the message processing functions corresponding to its possible machine-states:

int _far MPF00100(void _far *pd_in) {     // State 0

int _far MPF00101(void _far *pd_in) {     // State 1

int _far MPF00102(void _far *pd_in) {     // State 2

int _far MPF00103(void _far *pd_in) {     // State 3

The Message Exchange

The Message Queue

Robos messages, as such, are not placed in the message queue. Instead, a message queue entry comprises just the two pointers, pa and pd. The action part of a message pointed to by pa is a message processing function which resides in its appropriate place in memory. The data part pointed to by pd resides in a portion of dynamically allocated memory which is freed once the message has been dealt with.

This regime makes the message queue compact and easy to handle. A message queue entry is thus defined in 'C' as follows:

struct msg_queue_entry {
  void(*pa)(void *);       //pointer to the appropriate MPF
  void *pd;                //pointer to the message data

*pa points to a void function whose single input parameter is a pointer to an as yet undetermined data type. *pd is a pointer-to-void. A 256-entry Message Queue is therefore declared as follows:

struct msg_queue_entry msg_queue[256];

The elements of the msg_queue[] array each contain pointers pa and pd to functions and data buffers. However, further pointers to the elements of the msg_queue[] array itself are needed in order to allow messages to be taken off and put on the message queue. Pointers ps and pf point to the start and finish of the message queue itself - ie the currently occupied part of the message queue array. In fact, to make the program simpler, pf actually points to the next free element after the current end of the queue - ie the place where the next new message entry should be placed. The pointer pt is a constant. It permanently points to the highest (last) element in the message queue array.

The following diagram illustrates how these pointers are used. The shading represents the currently occupied portion of the message queue array.

Note that a 256-entry message queue can hold only 255 messages. At least one element must be considered unoccupied. This is so that ps and pf coincide only when the queue is empty and not when it is full also.

The pointers ps, pf and pt are pointers to msg_queue_entry structures and are defined as follows:

struct msg_queue_entry *ps, *pf, *pt;

Message Queue Declaration

The structure definitions and declarations for the message queue and its associated pointers is as follows.

extern void _far Initialise(void _far *);

#include <stddef.h>            //For NULL pointer definition
struct msg_queue_entry {       //DEFINE A MESSAGE QUEUE ENTRY
  void(_far *pa)(void _far *); //to message processor
  void _far *pd;               //to message data
_near msg_queue[256] =         //DECLARE CYCLIC MESSAGE QUEUE
{                              //Place in its first element a
  {Initialise, NULL}           //message instructing the appli-
};                             //cation to initialise itself.

struct msg_queue_entry         //Queue management pointers to:
  _near *pt = msg_queue + 255, //last element of queue array
  _near *ps = msg_queue,       //next message to be processed
  _near *pf = msg_queue + 1;   //where to put next new message

Message Queue Processor

The function main() which expedites and then removes messages from the queue, and the function PutMsg() which puts new messages onto the queue are shown below.

int active = 1;                //main()'s 'on/off' switch

main() {                       //MESSAGE DISPATCHER FUNCTION
  while(active) {              //While 'active' not zeroed
    if(ps != pf) {             //Provided msg queue not empty,
      (*ps->pa)(ps->pd);       //call required msg processor
      if(++ps > pt)            //then advance pointer to next
        ps = msg_queue;        //message in queue ready for 
    }                          //the next pass.

int _far PutMsg (              //MESSAGE ENTRY FUNCTION
  void(_far *pa)(void _far *), //points to message action
  void _far *pd                //points to message data
) {
  struct msg_queue_entry _near *p = pf;   //temporary pointer
  if(++p > pt)
    p = msg_queue;             //Advance 'feeler' pointer
  if(p != ps) {                //If room on queue...
    pf->pa = pa;               //Store 'action' pointer
    pf->pd = pd;               //Store 'data' pointer
    pf = p;                    //Advance to next free entry
    return(0);                 //Means 'Message stored OK'
  return(1);                   //'Couldn't store message'

Explanation of Source Code

The prototype extern int _far Initialise(void _far *); is necessary to define the pointer Initialise - the address of the function which performs the application's initialisation tasks.

Define The Message Queue Entry

The struct msg_queue_entry definition specifies that each entry in the message queue consists of:

The operation of these pointers is perhaps clarified by the following illustration:

Declare The Message Queue Array

The structure definition for one element of the message queue includes the declaration msg_queue[256] which allocates storage for the actual message queue in the form of an array of message queue entries.

Initialise The Message Queue

The = {Initialise, NULL} then initialises the first element of the message queue array with the message that kicks off the program. This message is an instruction to the Initialise() function to initialise the application. Read Initialise()'s description to see what happens as a result.

Note that it is because this message is in the queue to start with that the pointer pf is initialised to point to the second element (msg_queue + 1) of the message queue array.

Message Queue Pointers

Three (_near) pointers are provided to facilitate processing of the queue within this (_near) array of message entries:

pt points to the last entry in the array of message entries. The first entry is pointed to by the array name msg_queue, ps points to the entry for the next message to be processed, pf points to the next vacant array element where the entry for the next new message should be placed in the queue.

The Main On/Off Switch

The global interger variable active is initialised to 1 so that the while(active) loop in main() cycles continually. The application is terminated by the Terminate() function in the Initialisation/Termination overlay setting active to zero. This switch is necessary since the message queue will be empty for considerable periods while the application is running, and something needs to keep main() cycling.

The Function main()

main() first checks to see if there are any messages in the message queue. An empty queue is indicated by the (_near) pointers ps and pf coinciding (see previous diagrams).

Assuming the queue is not empty, the pointer ps points to the next message to be expedited. A message is expedited by calling the message processing function whose name is synonymous with the action specified in the message, and passing to it a (_far) pointer to the data upon which that action is to be performed. This is done by the indirect function call (*ps->pa)(ps->pd);. This works as follows:

(*ps->pa) calls the function whose address is in the field pa of the message structure element pointed to by ps. Note that the -> takes precedence over the *.
(ps->pd) passes the pointer pd found in the structure element pointed to by ps.
++ps advances the pointer ps one message queue element further up the message queue array. Remember that a message queue element is a structure comprising two (_far) pointers.

If the result of doing the ++ps is that the pointer ps has been pushed beyond the final element pt of the message queue array, then ps = msg_queue resets ps to point to the first element of the message queue array (ie it has wrapped round back to the beginning of the array).

The program then loops back to the beginning of the while loop.

The Function PutMsg()

PutMsg() is an interger-returning _far (because it is called by all MFMs) function that takes two input parameters:

It is called by every message processor function in the program.

All message processor functions are called directly by main() as already described. Every message processor function receives a message, performs an action upon it, then outputs the results as another message. It assembles the data portion of its output message (if there is any) in a structure. It allocates space for this data string from the dynamic memory pool by executing the function call:

pd = (struct gen_msg _far *)_fmalloc(sizeof(struct gen_msg));

where gen_msg is the generic name for the structure defining the particular message concerned.

It then executes the function call int x = PutMsg(pa, pd); where pa represents the output message's 'action to be taken' and pd represents the data on which the action is to be taken. Specifically, pa is the address of the message processor which performs that particular action, pd is a pointer to the start of the dynamically allocated storage area containing the data.

As described earlier, there must always remain at least one empty place in the message queue. This is necessary in order to be able to distinguish between when the queue is full and when it is empty. Therefore, although we already know where to put the next new message entry, we must look ahead to see if there is a further empty place which will remain after we have added our new message entry.

To do this, PutMsg() first declares a temporary pointer to a message queue element, p which it initialises to point to the current position where the next new message should be put on the queue. We then increment it one place ahead and test to see if it does not coincide with the beginning of the queue.

If incrementing p puts it beyond the end of the message queue array, its value is wrapped around back to the beginning of the array.

If the pointers p and pf now coincide, it means that if we were to put another message on the queue, the message queue array would become absolutely full. There would be no remaining free element. This is not allowed.

It is only if p != pf that we can put the new message on the queue, otherwise we must ignore it and return a value 1 to the calling message processor function.

To put the new message on the message queue, we proceed as follows. Of the two pointers passed to us, we:

  1. put the first pointer into the 'action' field of the message queue element pointed to by pf. (pf has not been incremented yet.)

  2. put the second pointer into the 'data' field of that same message queue element.

Setting pf = p effectively advances pf to the next spare element in the message queue array ready for the next call. Since the message has been stored OK, a value of 0 is returned.


Message Formats

There are two main message formats: internal and external. The internal format is designed to maximise processing speed. Only internal messages are processed by MPFs. External messages - messages which have come in from other PC's on a network or com link - are converted to internal format. External systems cannot know the internal addresses of MPFs. Therefore, messages from outside must specify the 'action' as an action number instead of as a pointer to an MPF. The internal structure of a message is defined within the message processing function that handles it.

Structure of A Message

A message (in the context of ROBOS) is a request for something to be done - for an ACTION to be performed. It is a command or instruction.

An action is performed by a function. The name of an action may therefore be synonymous with the name of the function which performs the action. A function's name is in effect its address. A message's 'action' field therefore contains merely a pointer *pa to the function that carries out that particular action.

However, a message is more than just a request for something to be done. It is a request for something to be done to something - for a particular action to be performed on a specific piece of data. In addition to its action field, therefore, a message has a data field which contains the data on which the action is to be performed.

This data can vary in length (number of bytes). It is therefore accommodated in a dynamically allocated area of memory which is pointed to by a pointer *pd.


To be able to do their jobs, application MFMs need to communicate with the real world. ROBOS provides them with the means of doing this. To an application MFM, ROBOS is the real world. Furthermore it is a real world which can be communicated with by the sending and receiving of messages. And these messages are of a form and in the language familiar to MFMs.

To achieve this, ROBOS includes means of converting raw data from the real world into ROBOS-compatible internal messages. Naturally it also contains means of converting response messages back into the various forms expected at their real-world destinations. These means are called Input Handlers and Output Handlers.

Two Design Options

Two approaches to the design of these Handlers were considered.

The first approach was to write each Handler as a single interrupt-driven 'C' function of the form:

extern int _far PutMsg(void(_far *)(void _far *), void _far *);

void _interrupt _far xxIH(
  [CPU REGISTERS]                //The input data appears in
  ...............                //specified CPU registers when
  ...............                //the given interrupt occurs.
) {
  struct MSG {                   //input device's message format
    [FIELD]                      //Specify each field of the 
    .......                      //input message type concerned.
  } _far *msg;                   //ptr to such a message type

  //Provided there's enough free memory for the new message...
  if((msg = (struct msg _far *)_fmalloc(sizeof(struct msg)))
      != NULL) {
    msg->[FIELD] = [REGISTER];   //fill out each field
    ............ = ..........;   
    ............ = ..........;   
    PutMsg(xxMP, msg);           //put the message on 
  }                              //ROBOS's message queue

xx is the name of the outside source from which the input has come. Examples are Com1, Com2, Mouse, Keybd. xxIH is the name of the interrupt handler which grabs input from that source. xxMP is the name of the Message Processor MFM which deals with messages received from that source.

This approach is intellectually interesting. However it could be a bit dangerous. One can never be sure how a particular 'C' compiler deals with interrupts. It may suppress some and not others within the body of the function. Furthermore, the execution time for a function like the one above would be rather long for an interrupt handler. For these reasons, this approach was rejected.

The second approach is to write very simple Input and Output Handlers in the host machine's assembler language. Such a Handler would put and get one character at a time respectively to or from its associated memory buffer.

Under this option, Robos's input service would comprise a set of corresponding polling functions. Each of these would empty its associated input buffer on a regular cycle. Robos's output service would be different. It would comprise a set of special MFMs. Each of these would feed its associated output buffer with output data as and when such data were passed to it by a message from an application MFM.

Input Services

Interrupt Handlers

The diagram shows the get process. Whenever a character is presented at the input port, the Handler is activated by an interrupt. When this happens, the Handler places the said character into the position in the buffer currently pointed to by pf. The Handler then moves the pointer pf up the buffer one byte. It continues to do this each time it receives a new character from the input port. Eventually, if the buffer is not emptied in the meantime, it will become full.

This occurs when pf has been advanced so far that it has wrapped around via the beginning of the buffer area and progressed up until it is 1 byte before the start pointer ps. When this occurs, the Handler sends an alert of some kind to the data source in the outside world to tell it to stop sending any more characters for the moment. This would mean sounding a beep in the case of keyboard input or sending an Xoff signal in the case of a Com port.

Input Polling

Each Input Handler has an associated 'C' function called an Input Poller. This checks the buffer periodically to see if there is any input data there. If there is, the Poller grabs it and resets the pointer ps to coincide with pf. This releases the space in the buffer which that data had occupied. The space can therefore be used again by the Handler to hold more input data received from its port.

If ps is just one byte ahead of pf when the Poller grabs the data, it means that the buffer is full. Consequently, the Handler has already sent an Xoff signal to the outside source. In this case, the Poller nudges the Handler after it has grabbed the data and reset ps. This is to tell the Handler to send an Xon signal to the outside source so that the source will resume sending data.

Suitable interrupt handlers are already present in the base operating system under which ROBOS is running. Their input/output buffers can be accessed, and their appropriate pointer(s) reset safely via software interrupts. All that ROBOS needs to include are suitable input buffers and a polling routine to empty them regularly. Output is performed by special MFMs which accept messages for output and convert them to data streams suitable for each respective output sink. Because output MFMs are message-driven, they do not need to be in a polling loop.

Input Buffers

A set of buffers must be declared for each input source as follows. Such input sources include keyboard, mouse, modem, Ethernet card and any specialised input devices.

#define MaxImp 6       //number of input sources

int KbInSize = 16,     //default size of keyboard input buffer
    MsInSize = 32,     //default size of mouse input buffer
    PrInSize = 16,     //default size of printer response buffer
    MoInSize = 65536,  //default size of modem input buffer
    EtInSize = 65536,  //default size of Ethernet input buffer
    ADInSize = 65536;  //default size of A/D converter buffer

char KbIn[KbInSize],   //declare keyboard input buffer
     MsIn[MsInSize],   //declare mouse input buffer
     PrIn[PrInSize],   //declare printer input response buffer
     MoIn[MoInSize],   //declare modem input buffer
     EtIn[EtInSize],   //declare Ethernet input buffer
     ADIn[ADInSize];   //declare A to D converter input buffer

These will be global, and appear before main() in the source file. Naturally other input sources may be added as the particular application may demand. For instance, in some monitoring and control applications there could be literally hundreds of all manner of logic, scalar, synchro and resolver inputs. Next, an array of structures must be declared in which each structure contains the pointers necessary for dealing with one of the input buffers.

struct PollData {
  void(_far *pa)(void _far *),  //default focus for this input
  char _far *pb,                //pointer to bottom of buffer
  char _far *pt,                //pointer to top of buffer
  char _far *ps,                //pointer to start of data
  char _far *pf                 //pointer to first free byte
} PollDataArray[NumIns] = {
  {KbDflt, KbIn, KbIn + KbInSize, KbIn, KbIn},
  {MsDflt, MsIn, MsIn + MoInSize, MoIn, MoIn},
  {PrDflt, PrIn, PrIn + PrInSize, PrIn, PrIn},
  {MoDflt, MoIn, MoIn + MoInSize, MoIn, MoIn},
  {EtDflt, EtIn, EtIn + EtInSize, EtIn, EtIn},
  {ADDflt, ADIn, ADIn + ADInSize, ADIn, ADIn},

The above structure definition also holds a pointer to the default MFM to which each respective type of input message is directed. This is sometimes called the default focus for the respective input source.

Polling Routine

An input polling routine is now required to encapsulate each 'grab' of received data into a ROBOS style internal message. This features a for(){} loop in which each iteration deals with one of the input sources.

for(                        //for each input source...
  struct PollData *p = PollDataArray,
  struct PollData *P = PollDataArray + NumIns;
  p < P; p++) {
  char *ps = p->ps,         //points to start of input data
       *pf = p->pf,         //first free byte after end of data
       *q, *pd;             //points to new message data
  if(ps != pf) {            //if input data present in buffer
    if(pf > ps) {           //if data is contiguous in buffer
      pd = (char _far *)_fmalloc((size_t)(ps - pf));
      q = pd;
    } else {                //if data is wrapped round buffer
      char *pt = p->pt      //points to byte after end of buffer
           *pb = p->pb;     //points to first byte of buffer
      pd = (char _far *)_fmalloc((size_t)(pt - pb + pf - ps));
      q = pd;
      while(ps < pt)        //copy data in top part of buffer
        *q++ = *ps++;       //to first part of message
      ps = pb;              //wrap pointer to start of buffer
    while(ps < pf)          //copy contiguous data or data at
      *q++ = *ps++;         //bottom of buffer into message
    p->ps = ps;             //reset ps for interrupt handler
    PutMsg(p->pa, pd);      //put the message onto the stack

This polling routine must be executed regularly to check for input from all the input interrupt handlers. This is effected by placing it within the while(active) loop in main() as follows.

main() {                       //MESSAGE DISPATCHER FUNCTION
  while(active) {              //While 'active' not zeroed
    if(ps != pf) {             //Provided msg queue not empty,
      (*ps->pa)(ps->pd);       //call required msg processor
      if(++ps > pt)            //then advance pointer to next
        ps = msg_queue;        //message in queue ready for 
    for(...) {...}             //poll all input sources
    }                          //the next pass.

It may become tiresome to have to recompile in order to change the number and sizes of input buffers. To avoid this, the number and sizes can be supplied via an .ini file or by command line arguments. These can then be used to allocate buffer storage dynamically using _fmalloc() or the like.

Initialising The Handlers

Finally, it is necessary to inform each respective interrupt handler as to the whereabouts of its input buffer. This is done by a PollInit() function which is called from the main initialisation function (which is an MFM invoked by a message planted in the main message stack when the stack is declared).

PollInit() {
  struct PollData *p = PollDataArray,
  KbIni(&(p->pb), &(p->pt)); p++;
  MsIni(&(p->pb), &(p->pt)); p++;
  PrIni(&(p->pb), &(p->pt)); p++;
  MoIni(&(p->pb), &(p->pt)); p++;
  EtIni(&(p->pb), &(p->pt)); p++;
  ADIni(&(p->pb), &(p->pt));

The functions within PollInit(), namely KbIni() and its friends are assembler functions which are part of their respective interrupt handlers. That is, they are each in the same code segments as their corresponding interrupt handlers. Because of this, the calls to these functions may need a call qualifier like _Pascal depending on the ramifications of the 'C' to Assembler calling conventions. Irksome and irritating things like who puts what on the parameter stack first.

Of course, one may desire to replace the base operating system's indigenous handlers with other more suitable ones. In fact, the base operating system may not include handlers suitable for specialised input sources. The main initialisation function may therefore need to disconnect some or all of the base operating system's indigenous handlers and connect in their place both replacement handlers and additional handlers. Obviously this must be done before PollInit() can pass them the buffer addresses.

Message Processing Functions

Each MFM contains one or more Message Processing Functions [MPFs]. Each MPF may, in addition to processing a received message, invoke a change of state in the MFM of which it is part.

Naming Convention For MPFs

The name of a message processing function begins with the letters MPF. These are followed by 5 digits. The first 3 of these identify the MPF's parent MFM. The remaining 2 identify the parent MFM's state for which the MPF concerned does the processing. This is clarified below:

MPF        Stands for 'Message Processor Function'
   000     Identification Number of the MPF's parent MFM
      00   State of parent MFM for which the MPF concerned
           processes messages

Structure of an MPF

The general form of an MFM message processing function is as follows:

int _far MPF00000(void _far *pd_in) {
  int inst;                          //MFM Data-Instance Number
  void _far *pa_out,                 //Output message's action
       _far *pd_out;                 //Output message's data
  size_t  in_msg_len;                //length of input message
         out_msg_len;                //length of output message
  if(cannot_process_it_this_pass) {  //EXAMINE INPUT MESSAGE
    pa_out = MPF00000;               //Set new message entry to
    pd_out = pd_in;                  //point to old message.
  } else {
    pd_out = (void _far *)_fmalloc((size_t)out_msg_len);
    pa_out = MPF?????;               //Output message's action
    _ffree(*pd_in);                  //Free old msg's storage
  int Result = PutMsg(pa_out, pd_out);

Typical Applications

All applications that run on Robos are written as Message-driven Finite-state Machines [MFMs]. Each application runs as an independent task. Applications running concurrently can exchange information with each other by messages. This is true not only of applications running on the same computer, but is true also of applications running on different computers which are linked by network.

Robos applications fall into 5 general classes: interfaces [nowadays generally known as clients. Ed], servers, monitors, controllers and services.

These accept raw information from the outside world and present processed information to the outside world. Some interfaces exchange information with human beings. Others exchange information with both natural and artificial processes.

These are active repositories of both raw and processed information. They normally work without human attention. They accept messages requesting information and originate reply messages containing the information requested.

These are gatherers and organisers of specific information. They also normally work without human attention. They accept messages from interfaces bearing raw information from the outside world. They then process this information and send it on (again by message) to a server for storage.

These usually appear only in observation and telemetry applications.

These may accept information immediately from processes in the outside world via messages produced by interfaces. Alternatively they may receive it indirectly by making requests to servers for information left there by monitors. This information - by whatever route it comes - originates from processes (natural or artificial) in the outside world. Their function is to use this information to form appropriate responses to those processes in the outside world which it is their job to control.

These usually appear only in process control and tactical navigation applications.

These provide timing, communication and security services, plus general storage, processing and presentation functions for other applications.

© 1997 Robert John Morton