Robert John Morton
My Programs
Family Finances
HTML word-counter
HTTP server
Web Browser
ROBOS
Neural Networks
Introduction
Multi-Layer Perceptron
Summation Function
Transfer Function
Complete Neuron
An MLP Program
Training The MPL
Applications
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 and 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 input messages 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.
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 any one of a small (finite) number of discrete states. Hence the term Finite-State. For example, an instance of a 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, performs 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.
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 ID {
int machine_state; // Current machine-state
...
...
...
...
...
} I[16]; // Declare array of 16 instances of struct ID
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 ID *hInst = (struct ID *)malloc(sizeof(struct ID));
Part 2: A prototyped declaration of the message processing functions corresponding to its possible machine-states:
int MPF00100(void *pd_in) { // State 0
.....
.....
.....
.....
}
int MPF00101(void *pd_in) { // State 1
.....
.....
.....
.....
}
int MPF00102(void *pd_in) { // State 2
.....
.....
.....
.....
}
int MPF00103(void *pd_in) { // State 3
.....
.....
.....
.....
}
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 MQE{ // structure of a message queue entry
void(*pa)(void *); // pointer to message procesing function
void *pd; // pointer to input message
} MQ[256]; // declare array of 256 of these structures
*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. The 256 possible elements of the array M[] each contains pointers pa and pd to functions and data buffers.
Further pointers to individual elements of MQ[] 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 — i.e. 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 — i.e. 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 MQE structures and are defined as follows:
struct MQE *ps, *pf, *pt;
The structure definitions and declarations for the message queue and its associated pointers are as follows.
void Init(void *); // prototype for the initialisation function
#include <stddef.h> // For NULL pointer definition
struct MQE { // DEFINE A MESSAGE QUEUE ENTRY
void(*pa)(void *); // pointer to message processor function
void *pd; // pointer to message data
} /*
DECLARE CYCLIC MESSAGE QUEUE to hold up to 256 possible messages
| Place in its first element a message instructing
| | the application to initialise itself.
| | Init function has no associated message
| | | */
MQ[256] = { {Init, NULL} };
struct MQE // Queue management pointers to Message Queue Entries:
*pt = MQ + 255, // last element of queue array
*ps = MQ, // next message to be processed
*pf = MQ + 1; // where to put next new message
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) // advance pointer to next message in queue
ps = MQ; // If pointer now beyond last entry in MQ[]
} // set pointer back to beginning of MQ[].
}
}
/* points to handler function for type of message pointed to by 'd'
| content of what is defined as follows ...
| | pointer to a particular instance of a structure of type MQE
| | | Member 'pa' of the above structure-instance which points
| | | | to the required message handler function.
| | | |
a = *(ps->pa); // get pointer to required message handler function.
This is the content of the member 'pa' of the instance
of the structure type MQE pointed to by 'ps'.
The brackets in the above statement are unnecessary but have been put
there to indicate standard operator precedence.
pointer to base address of character array containing received message
| pointer to a particular instance of a structure of type MQE within MQ
| | member 'pd' of the above structure-instance
| | |
d = ps->pd; // get the pointer to the base of the character array
containing the message to be processed, which is equal to
the member 'pd' of the instance of the structure type MQE
pointed to by 'ps' */
/* THE MESSAGE ENTRY FUNCTION [puts a new message on the queue]
points to the required message handler function
| points to the message data
| | */
int PutMsg(void(*pa)(void *), void *pd) {
struct MQE
*p = pf; // temporary pointer to first free entry in MQ[]
if(++p > pt) // if incrementing p makes it overshoot top of MQ[]
p = MQ; // circle it back round to the first element of MQ[]
/* Provided that incrementing 'pf' [p is now pf + 1] will not make it
coincident with 'ps' [the first occupied entry on the queue] then
there must still be space on the queue for a new entry. */
if(p != ps) { // if there is still room on queue...
pf->pa = pa; // store pointer to required message handler function
pf->pd = pd; // store 'data' [message] pointer
pf = p; // advance to next free entry
return(0); // means 'Message stored OK'
}
return(1); // the queue was full so couldn't store message
}
The function prototype int Init(void *); is necessary to define the pointer Init — the address of the function which performs the application's initialisation tasks.
struct MQE{ // structure of a messahe queue entry
void(*pa)(void *); // pointer to message procesing function
void *pd; // pointer to input message
} M[256]; // declare array of 256 of these structures
The struct MQE definition specifies that each entry in the message queue consists of:
a pointer to a void function whose single input parameter is a pointer-to-void. The function pointed to is the message processing function which performs the 'action' required by the particular message.
a pointer-to-void data-type. This actually points to the message's data upon which the 'action' is to be performed. The data-type pointed to in any particular instance will of course depend on the nature of the message.
The operation of these pointers is perhaps clarified by the following illustration:
The structure definition for one element of the message queue includes the declaration MQ[256] which allocates storage for the actual message queue in the form of an array of message queue entries.
The = {Init, 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 Init() function to initialise the application. Read Init()'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 (MQ + 1) of the message queue array.
Three pointers are provided to facilitate processing of the queue within this 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 MQ,
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 integer 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 section 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.
main()
main() first checks to see if there are any messages in the message queue. An empty queue is indicated by the pointers ps and pf coinciding (see the 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 handler function whose name is synonymous with the action specified in the message, and passing to it a 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 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 = MQ resets ps to point to the first element of the message queue array (i.e. it has wrapped round back to the beginning of the array).
The program then loops back to the beginning of the while loop.
PutMsg()
PutMsg() is an integer-returning [because it is called by all MFMs] function that takes two input parameters:
(void) data-type
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 GM *)malloc(sizeof(struct GM));
where GM is the generic name for the structure defining the particular type of 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:
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.
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.
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 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:
int PutMsg(void( *)(void *), void *);
void _interrupt 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.
.......
} *msg; // pointer to such a message type
// Provided there's enough free memory for the new message...
if((msg = (struct msg *)malloc(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.
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.
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.
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( *pa)(void *), // default focus for this input
char *pb, // pointer to bottom of buffer
char *pt, // pointer to top of buffer
char *ps, // pointer to start of data
char *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.
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 *)malloc((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 *)malloc((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
} // on 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 malloc() or the like.
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 depending on the ramifications of the 'C' to Assembler calling conventions to resolve 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.
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.
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:
MPF00000
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
The general form of an MFM message processing function is as follows:
int MPF00000(void *pd_in) {
int inst; // MFM Data-Instance Number
void *pa_out, // Output message's action
*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 *)malloc((size_t)out_msg_len);
PROCESS THE INPUT MESSAGE
UPDATE THE INSTANCE DATA
BUILD THE OUTPUT MESSAGE
pa_out = MPF?????; // Output message's action
free(*pd_in); // Free old msg's storage
}
int Result = PutMsg(pa_out, pd_out);
}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 these are generally known as clients. Ed], servers, monitors, controllers and services.
These usually appear only in observation and telemetry applications.
These usually appear only in process control and tactical navigation applications.