Richard F. Man is a compiler writer at DEC, a part time "gradual" student at Tufts University, and father of Ariane Man-Willrich: the cutest baby girl in the world. If you are interested in this project or subsumption architecture in general, write to him at P.O. Box 6, North Chelmsford, MA 01863.
Subsumption architecture, created at the MIT Mobile Robot Lab by Professor Rodney Brooks as a control system for autonomous robots, decomposes the control program in terms of task-achieving layers. Starting from the lowest layer, the robot's capabilities are increased by additions of higher and higher layers of competence, with each higher level subsuming and incorporating capabilities of the lower layers by modifying lower layers' behavior. The resulting control system provides more robustness, buildability, testability, and adaptability than traditional systems.
A major characteristic of a subsumption architecture implementation is the ability to write concurrent asynchronous executing modules with certain communication capabilities. Since autonomous robots have their own embedded processors and C has many advantages in programming embedded systems, I decided to augment C with a subsumption architecture library. In this library, the multithreading executive provides the ability to write concurrent executing modules and the message manager implements the communication mechanisms.
This subsumption language contains features similar to MIT's first generation FSM-based subsumption language, plus some features from the Behavior Language. I hope to add more Behavior Language features as time goes on. Most of these functions are written in standard C, with some target hardware specific functions in assembly. All target-specific functions are isolated into their own modules and can be replaced easily when switching environments.
Although the library was created for the purpose of writing subsumption architecture-based robot control software, it may also be used to write simulation software that runs on PCs or workstations. To date, I have tested the library in PC DOS and Sun 3 UNIX environments, and on a Motorola MC68HC11 EVB evaluation board with 16K of RAM. (My own mobile robot project, which uses the HC11 EVB as the main controller, is mentioned briefly at the end of this article.)
Overview Of The Multithreading Executive
With the multithreading library, a single program may contain multiple executing threads, each being an execution instantiation of a function in the program. The executive's scheduler, operating independently of the host OS scheduler, controls which thread to run at a given time.Figure 1 lists the executive functions included in the library; Figure 2, the message manager functions. (Because the code has been commented and is provided in the listings, I will not give a detailed explanation of each of the functions; instead, I will outline the way the system works.)
The function ExecInit() initializes the system. A program must call it before it calls any other functions in this library.
ExecCreateThread() creates the context for a thread but does not execute it. A program calls this function with the address of a thread function, its required stack size, and two pointersized initial arguments. ExecCreateThread() may be called anytime, including in another concurrently running thread as well as multiple times within the same thread function. (Such thread functions should obey the usual rules of reentrancy, e.g., by using automatic variables instead of global variables.) The first argument to this function specifies the thread type: this will be used when more features are incorporated from the Behavior Language.
After a user program creates all the initial threads, it must call the function ExecStart() to start the scheduler. Once started, the scheduler never returns control to the original caller but will pass control to runnable threads in a round-robin manner.
This executive supports only the cooperative style of multitasking — that is, a thread only gives up control back to the executive when it explicitly calls a particular library function. Although in theory not as suitable as preemptive multitasking for real time programming, the use of subsumption architecture makes this mostly a non-issue. (Both of Brooks's subsumption languages use cooperative multitasking as well.)
A thread typically executes some initialization code and then calls the MsgGetMsg() function to get a message. MsgGetMsg() immediately calls the thread-switching function ExecSwitch(), which gives execution control to the next runnable thread. After receiving control, a thread should call MsgGetMsg() again within a "reasonable" time to ensure that other threads have a chance to run. Thus the call to MsgGetMsg() is usually done in a non-terminating while loop. If a thread function ever returns, its resources are reclaimed and it will not be executed again.
As an example, consider the following program that creates two threads:
void thread(void) { MsgWatchTimer (0); while (MsgGetMsg()) printf("I am alive, thread %d\n", ExecGetThreadID()); } int main() { ExecInit(); ExecCreateThread (NORMAL_PROC, thread, 10000, 0, 0); ExecCreateThread (NORMAL_PROC, thread, 10000, 0, 0); ExecStart (); }When run, the program prints the following output:
I am alive, thread 0 I am alive, thread 1 I am alive, thread 0 I am alive, thread 1 I am alive, thread 0 (etc...)There are three types of messages: timer, port, and semaphore. A thread notifies the message manager of what types of messages it wants to receive by using the MsgWatchTimer(), MsgWatchPort(), or MsgWatchSemaphore() functions. All of these functions return a unique message identifier. When a message arrives, the message manager places the receiving thread at the end of a queue of runnable threads and stores the message identifier in the queue entry; it then calls the scheduler function ExecSwitch. Upon receiving control, the scheduler takes the first thread off the runnable queue thread and gives control to it. From a thread's point of view, it calls the MsgGetMsg() function and the library function returns with a message identifier.This event-driven style of cooperative multitasking is similar to those used by other cooperative multitasking OSs such as MS Windows v3.0 and the Apple MacIntosh Multi-Finder. I have thus chosen the name MsgGetMsg() deliberately to be close to the names of the corresponding functions in these OSs.
The simplest message to watch for is the timer message. To do this, a thread calls the function MsgWatchTimer() with the time delay factor. The thread will then be runnable after the specified time has elapsed since it was last run. In this implementation, the unit for time delay factor is proportional to the number of threads currently watching for timer messages. (I may change the time delay factor to a constant time unit later, to match the corresponding concept in Brooks's languages.)
Threads communicate through a "port" message. A port variable can be any C variable, although it is best to use a local variable for re-entrancy reasons. To allow other threads to identify a port variable, a thread must associate a unique identifier with it. Port variables serve as the input/output "register" interface of a thread, and their corresponding identifiers serve as their "name" interface. An ASCII string serves as a good unique identifier for a port variable (or a semaphore, see below). For efficiency reasons, a program must convert the string to a unique index value and use it in place of the ASCII string. (This library contains the function StringToAtom() for this purpose. It returns the same unique index value for two ASCII strings if and only if they are identical.)
A program informs the message manager of the binding between a port variable and a port identifier by using the MsgWatchPort () or MsgOpenPort () function. All other message manager functions only use port identifiers.
A port variable may be unidirectional or bidirectional. A thread sets a port variable for reading by calling the function MsgWatchPort () with a port identifier and the address of its corresponding port variable. When another thread indirectly writes to that port variable, the message manager notes the arrival of this message to this thread and takes the appropriate action.
A thread sets a port for writing by calling the function MsgConnectPorts () with an output port identifier and an input port identifier (the destination port) in another thread. Multiple input port variables (up to a system-defined limit) may be connected to a single output port. When using MsgConnectPorts (), no actual output port variable is required. Alternatively, a thread can set a port for writing by calling the function MsgOpenPort () with a port identifier and the address of a port variable. Here, it is assumed that other threads will connect their input port variable(s) to this output port. A lower layer of competence uses the MsgOpenPort () function to provide feedback values for the higher layers.
A thread writes to a port by calling the function MsgWritePort () with the output port identifier and the value it is writing. This function updates the value of the output variable (if it was registered via MsgOpenPort ()) and finds all threads with input port variables connected to this output port (by MsgConnectPorts ()). It then updates these input port registers and places the threads on the runnable queue.
A thread calls MsgSuppressPorts () with an output port identifier and the identifier of an output port (usually in another thread) to be suppressed. The semantic of this function is that whenever the thread writes to the output port (the first argument to the MsgSuppressPorts () function) via MsgWritePort(), all the input ports attached to the suppressed port (the second argument) will receive this value for a system-defined period. Any other writes during this period is ignored and will not get passed to the attached ports.
A thread calls MsgInhibitPorts() with an output port identifier and the identifier of an input port to be inhibited. Whenever the thread writes to the output port with MsgWritePort(), the inhibited input port will receive this value (for a system-defined period) instead of from the output port that it may be connected to.
A thread also may read the current value of any output port variable by calling MsgPeekPort() with the port identifier of an output port variable.
Note that the system does not care if you specify the same port identifier (i.e., same ASCII string) for two different port variables. The result is undefined. MsgConnectPorts() may also be called anywhere, including in functions that are lexically far from the threads whose variables are involved in the call. However, since this practice obscures the interface between the threads, it is not recommended. As a programming style, I use ASCII strings in the form of either thread_function_name.in.digit (e.g., alphaPos.in.2) , or thread_function_name.out.digit, where "in" and "out" signify an input or output register respectively.
A thread may wait for a semaphore by calling the function MsgWatchSemaphore() with a unique identifier. The second argument to the function specifies whether the thread is watching for the clearing of or the setting of the semaphore. A semaphore is set and cleared via the functions MsgSetSemaphore() and MsgClearSemaphore() respectively.
Implementation Of The Multithreading Executive
There is almost enough machinery in standard C to write all the functions in the multithreading executive. The standard library functions setjmp() and longjmp(), which implement non-local gotos, are enough to implement the thread-switching function ExecSwitch(). These functions work in the following ways: when setjmp() is called with a jump buffer, it returns immediately with the value 0. Later, if the function longjmp() is called with that same jump buffer, then execution returns to where the setjmp() is called; this time as if setjmp() returns with the second argument to longjmp() as its value. If the second argument of longjmp() is 0, then setjmp() returns a value of 1.The internal function ExecSwitch() first checks for possible stack overflow, then records the current thread's execution context via a call to setjmp(). It then calls another internal function, execRunNewThread(), which takes the first thread off the runnable queue and switches back to that thread via a call to longjmp(). The execution continues in this new thread as if its call to setjmp() inside ExecSwitch() has just returned again with a message identifier. ExecSwitch() then returns to MsgGetMsg() which in turn returns the message identifier to the thread that calls it.
One concern with these functions is that setjmp() and longjmp() do not address the issue of setting up the initial stack pointer for each thread. In theory, longjmp() should not be called if the function that originally calls setjmp() has already exited since the stack context may no longer be valid. Some C-and C++-based multithreading executives deliberately ignore this constraint so that the stack space for all the threads is allocated on the stack of the running program. This technique, however, makes thread stack allocation tricky and obscure. Under this scheme a program may be forced to create all the possible threads at once, because the alternative of allowing a program to create a thread anytime is difficult to implement.
I chose a different approach to allocate thread stack space. The ExecCreateThread() function allocates stack space for a thread dynamically via the standard C function calloc() and stores the address of the returned value in the thread's context. When calling a thread function for the first time, the scheduler function ExecSwitch() changes the stack pointer so that the new thread will use the correct stack pointer. This is only done at the initial call to a thread since normal thread-switching uses the functions setjmp() and longjmp() to save and restore execution context, including the stack pointer.
Since there is no portable way of changing stack pointers in C, it is done using a small assembly routine. I wrote a prototype C routine that does everything except modify the stack pointer, then compiled it to assembly. I then modified the assembly file to handle stack switching for a particular machine environment. This compile/modify technique makes it relatively easy to port this part of the system to different environments.
I did encounter one problem with this approach. The library in the HC11 cross compiler that I am using assumes that if a stack address is lower in value than a heap address, then the heap must have overrun the stack. This would be true in normal cases since the heap is allocated upwards from the bottom of a free data segment and the stack is allocated downward from the top of the same data segment. It is not true here because the "stack" is really another heap item, so I had to write a very simple-minded linear stack allocator to circumvent this problem.
About The Listings
Listing 1 contains the multithreading executive. Listing 2 (sans the servo interface code) is the control software for a simple six-legged walking robot.The Listing 2 code is based on the description of a simple walking algorithm for Genghis in [4]. Notice that there is no routine that is consciously doing any walking — the closest it comes is that the highest layer function, TripodGait(), alternately raises its legs in a tripod gait.
This code is intended to control the movement of a six-legged "ladybug" robot (for which the hardware is being built by Donald Doughty). The robot's brain is an MC68HC11 EVB, chosen because it contains many features that are useful for embedded work, such as a serial and parallel interface, some A/D converters, and several timers on one chip. The EVB emulates all the features of the CPU while providing a ROM monitor, 16K of user RAM space and an RS-232 port. The monitor and the RS-232 port allow programs to be developed on the host, typically on an IBM PC, and executed on the EVB. The EVB interfaces 12 Futuba servos — two per leg — through a custom-designed interface board. One servo moves the leg back and forth and the other moves it up and down. (As of this writing, the hardware for the project, which is part of my master's thesis, is not yet finished and the code is incomplete; if you are interested in the project, you may contact me at the address given in my bio.)
Bibliography
[1] "Achieving Artificial Intelligence Through Building Robots," Rodney A. Brooks, MIT AI Memo 899, May 1986.[2] "A Robust Layered Control System For a Mobile Robot," Rodney A. Brooks, MIT AI Memo 864, September 1985.
[3] "The Behavior Language; User's Guide," Rodney A. Brooks, MIT AI Memo 1227, April 1990.
[4] "A Robot That Walks; Emergent Behaviors from a Carefully Evolved Network," MIT AI Memo 1091, February 1989.
Listings — All code in this listing copyright (c) by Richard F. Man 1991. All rights reserved.
Sidebar: "Subsumption Architecture: Moving Robots In The Real World"