The San threading engine

This is an introduction to the San threading engine, which is very much a work in progress.

The proposed San language is a dynamic data flow language. A simple way to understand the difference between procedural programs and data-flow programs is to look at the following flow chart fragment.

            _____     ______
           |     |    |     |
    ...--->|  A  |--->|  B  |--->...
           |_____|    |_____|
               Diagram 1.

If this fragment is from the flow chart of a procedural program it signifies that the program first executes block A and then block B. Procedural programs execute sequentially; the flow chart represents the flow of control. If, however, it is from the flow chart of a data flow program blocks A and B are executed concurrently. Data flow programs execute in parallel; the flow chart represents the flow of data. (Parallel in principle – actual implementations are necessarily messier.)

A data flow language is dynamic if blocks and their connections can be created and deleted during the course of execution. In other words, the data flow chart for the program is not fixed in advance; it change over time.

The San engine software is a preliminary implementation of the data flow engine to be used by a San language interpreter. Although it was created to be part of a San interpreter, it can be used as a stand alone C package. The San engine software is consistent with use in an implementation distributed across multiple processes and computers; however the current code is written for a single process environment.

The engine structure upper level is one or more common resource frames. A common resource frame (CRF) contains a tree of agents and resources used by the engine to maintain the agents.

    common resource frame
               |
               |--------> resources (e.g., free lists, storage pools)
               |
               |--------> tree of agents

An agent contains administrative data used by the engine, global data shared by the user mini threads, and optional initialization, autonomous source, and input response mini-threads.

             agent
               |              
               |--------> administrative data
               |--------> shared global data
               |--------> initialization mini thread
               |--------> autonomous source mini thread
               |--------> input response mini thread

In the San model an agent has 0 or more input ports and 0 or more output ports. Here is an example:

              __________________________________________
             |                                          |
             |   _______      ________     _______      |     ________
 _______     |  |      1|--->|1     1|--->|1     1|---->|--->|1       |
|       |    -->|1  A   |    |   B   |    |   C   |          |   D    |
|   S  1|------>|2      | |->|2      |    |      2|->|       |________|
|_______|       |_______| |  |_______|    |_______|  |
                          |__________________________| 
               Diagram 2.

Block S is a source, i.e., it autonomously produces output. Blocks A and B have two input ports and one output port whereas block C has one input port and two output ports. The output from port 1 in block C tees, i.e., it is sent both to block A and block D. Finally, block D is a sink, i.e., it has inputs but no outputs.

Within an agent there is a separate application supplied response function for each input port. (By default it is a no-op, i.e., an empty function.) An agent can also have application supplied source functions that execute autonomously.

The agents receive inputs and emit outputs; however they do not “know” where the inputs come from and where the outputs go. This information is contained in separate connection tables. Here is the connection table for the data flow chart (schematic) shown in diagram 2.

    From  To
    S 1   A 2
    A 1   B 1
    B 1   C 1
    C 1   A 1
    C 1   D 1
    C 2   B 2

The interface to the San engine is opaque. The API functions use handles to refer to objects managed by the engine. A handle universally needed by user code is the sigil, a structure that acts as a password. When user code is loaded, a sigil is passed to it. When the user code accesses the API it supplies the sigil as a password. The engine uses the sigil to validate the access.

There are two categories of entry points. The first category has the setup functions listed in table I. These functions are called in “main” to initialize the engine and to load the initial user code.

                  Table I - Setup functions
    san_ctl_create_crframe   Creates a common resource frame           
    san_ctl_get_master_sigil Gets sigil for the master agent           
    san_ctl_init_sysinfo     Initializes the system information struct 
    san_ctl_load_master      Loads initialization code for the master agent 
    san_ctl_scheduler        Handles scheduling of execution 'threads' 

The prototypes for the setup functions are in a separate include file, san_ctl.h, and are meant to only be used by main. Here is a sample main program:

int
main(int argc, char ** argv)
{
    CRFID          crfid;
    SIGIL          sigil;
    trace_init("san");
    sys   = san_ctl_init_sysinfo(argc,argv);
    crfid = san_ctl_create_crframe(sys);
    sigil  = san_ctl_get_master_sigil(crfid);
    san_ctl_load_master(sigil,load_master);
    san_ctl_scheduler(crfid);
    return EXIT_SUCCESS;
}

The first four functions are initialization routines. Trace_init initializes a calling sequence trace utility. San_ctl_init_sysinfo processes the command line options. The options currently available are:

OPTION       TYPE         DESCRIPTION
context      context      Default context
err          error file   Error file
log          output file  Log file
d            flag         Debug flag
ev           flag         Event log flag
def          flag         Use defaults flag
rpt          flag         Write a terminal report

The scheduler (san_ctl_scheduler) is the heart of the engine. The general idea is that user code elements emit data that is sent to other user code elements as specified by the connection tables. The scheduler takes care of moving data from emitters to receivers; it also schedules the activation of agent source functions and agent input response functions as needed.

Function san_ctl_load_master has two arguments, a sigil for the master agent, and a user defined function that loads and initializes the user application. The user defined function creates the initial agents and their connections. It also loads user application code into the agents. Here is a sample “load master” function:

void
load_master(SIGIL sigil,void * data)
{
    AGENT_R        master;
    AGENT_R        ag1;
    AGENT_R        ag2;
    AGENT_R        ag3;
    AGENT_R        ag4;
    AGENT_R        ag5;
    SIGIL          ag1_sigil;
    master = sigil.host;
    ag1 = san_create_child(sigil,0);
    ag2 = san_create_child(sigil,0);
    ag3 = san_create_child(sigil,0);
    ag4 = san_create_child(sigil,0);
    ag5 = san_create_child(sigil,0);
    san_connect(sigil,ag1,ag2,1,1);
    san_connect(sigil,ag2,ag3,1,1);
    san_connect(sigil,ag3,ag1,1,1);
    ag1_sigil = sigil;
    ag1_sigil.host = ag1;
    src = san_add_source(ag1_sigil,ag1,ag1_source);
    }
}

The mqajority of the application interface functions alter the schematic (the data flow structure) either by creating or deleting agents, by altering connections, or by altering user application code. There are three output functions, san_emit, san_event_logger, and san_rpt_agent. San_emit emits output from an agent output port. One of the program options is the ability to create an event log; the event logger writes messages to the event log. Finally, the agent reporter writes an agent report.

        Table II - engine/application interface routines
san_connect             Creates a pipe connection                   
san_create_child        Creates a child agent                       
san_create_sibling      Creates a sibling agent                     
san_delete_agent        Deletes an agent                            
san_delete_source       Deletes a source element                    
san_disconnect          Eliminates a pipe connection                
san_emit                Emits a data packet                         
san_event_logger        Logs an event in the event log              
san_get_agent_data      Gets user visible agent data                
san_get_child_no        Gets child ref for a given index            
san_get_source_no       Gets source ref for a given index           
san_load_init           Loads agent initialization code             
san_load_inport         Loads an execution function into an inport  
san_load_source         Adds a source element to an agent           
san_rpt_agent           Creates an agent report                     

This page was last updated February 26, 2009.