Not all companies share this luxury. For small companies with lower volumes, the cost savings instead come from the ability to react quickly to new requirements and make products easy to maintain. How many times have you seen a key engineer so swamped with supporting older products that he can no longer work on next-generation products? This is a classic symptom of a small company in trouble.

Since small companies have to spread their resources among several development fronts, it becomes important to create systems with flatter learning curves. While the rogue engineer might find it more fun to use clever design tricks, his value to the company will be higher if he keeps his designs simple and maintainable.

The Problem

I once worked at a small company with only a dozen employees, half of whom were involved with administration and customer support. That left six people to design and manufacture our products.

Our company produced industrial equipment used in the harsh environment of food-processing plants. The equipment had to withstand extreme high and low temperatures, as well as a rigorous daily wash-down routine. Our customers placed high demands on the equipment, as any downtime on the line translated directly into lost profits.

One other limitation we faced—one that is often overlooked—was the sophistication level of our own staff. Only the two project leaders had engineering degrees. The rest of us were trained in basic programming skills. We were simply not equipped to handle advanced concepts such as real-time system design, deadline analysis, or priority inversions. Consequently, we needed to keep our designs straightforward, so that little time would be spent in later development and maintenance.

Hardware and Software Environments

Our company chose to implement its industrial controllers using commercial off-the-shelf PC motherboards and a simple DOS software environment.

Early in our development, we considered using either Linux or Windows instead of DOS. But each had its shortcomings. Linux was perceived as unsupported—we would have to write some device drivers ourselves. Windows was also rejected; its shortcoming was its tendency to need user attention in exceptional situations. Our controller needed to run without user intervention. In the end, MS-DOS provided a good balance between reliability and simplicity.

We did not consider using a real-time operating system because no one on staff had familiarity with the concepts of real-time systems, nor did our application actually require real-time control. Considering our time and budget limitations, it would have been unreasonable to commit to training our current (and future) staff to this higher level of sophistication. The company was better off designing products that novice programmers could produce and maintain.

A New Requirement

The first generation of our industrial control equipment was immediately successful. Using off-the-shelf motherboards and the DOS-based software, we were able to develop our first release very quickly. Soon, we were installing equipment in food-processing plants all over North America. Our equipment did its job reliably, and communicated to the outside world through its serial ports. Everything looked great.

With a successful product under our belt, we wanted to follow up with a second-generation system. We got a new requirement from our marketing/sales/president (remember, in a small company, everyone wears many hats). The new product requirement was to network these devices together via Ethernet. One of us was going to have to figure out how to integrate TCP/IP into the control system. As it turned out, that person was me.

I looked into MS-DOS TCP/IP libraries and ran across WatTCP (http://www.wattcp.com/), developed by Erick Engelke. Within a few minutes, I was able to write a simple program that opened a socket, sent some data to another machine, and waited for a reply. The program was basically structured as a loop, continuously polling the Ethernet stack through the function tcp_tick(); see Listing One.

The WatTCP library needs to be tickled every so often to get its work done. In my simple proof-of-concept example, I could just sit in a loop, calling tcp_tick(). However, I soon found out that this simple polling requirement would affect our industrial control software in big ways.

The Need for Multitasking

With WatTCP in hand, I began integrating the library into the controller's software. I simply initialized the library and started listening on a socket. If a message came in, I read it and sent back a response. The only thing I had to do was make sure the software tickled the TCP library (by calling tcp_tick()) from time to time. Consequently, I started sprinkling tcp_tick() statements throughout the code. My first instinct was to piggyback the TCP/IP tickling onto some other frequently called functions, such as the keyboard poller. But I kept finding places where the software would go off and do something for a minute or so, forgetting to tickle the TCP stack. For instance, when printing or reading through a data file, the system might go a few seconds without tickling the TCP stack. That meant I could not respond to commands coming in over the network until the printing or disk access was finished.

Something else that was becoming a concern was the intermixing of software modules. At first, it was not too bad. But it started to get messy as I added tcp_tick() calls in odd little places. I worried that the next programmer would not know where to put them—and where not to put them.

So we had noticeable delays in response and ugly source code. I needed a way to separate the Ethernet interface into a thread of its own. But how could I run multiple threads and still hang on to the easy-to-program MS-DOS environment?

Scheduling, Tasks, and Threads

To give the appearance that two threads are running concurrently, a multitasking operating system executes small pieces of each thread, rapidly switching back and forth. Besides the convenience of being able to monitor something in the background, a multitasking environment brings with it an inherent efficiency. Since all programs must wait for something at some time or another, it often makes sense to use this waiting time to do some other task. Obviously, MS-DOS was not going to do this for me, since it is a single-task operating system. If I wanted to run multiple threads in my own program, I needed to break my existing code into bite-sized pieces and execute these pieces in an alternating sequence. This would give the appearance of several things going on at once.

Figure 1 illustrates a single program running three logical threads of execution by breaking the threads into chained pieces, which I call "tasks." These tasks are like items on a to-do list: When a task is executed, the last thing it does is add another task to this to-do list. The resulting chain is a thread, which can do useful work independent of other threads in the system.

The software to implement these three threads is straightforward. In the starting condition, the main program spawns three tasks—one to update the clock display (CLK), one to monitor the Ethernet port (ETH), and one to respond to user input (UI). Each of these tasks does its job quickly with no waiting, then spawns a child task to continue the job later. The chains of tasks are collectively viewed as a thread of execution. Listing Two illustrates one such implementation.

A scheduler (available electronically; see "Resource Center," page 5) keeps track of what tasks need to be run, and in what order they should run. Each task runs to completion without being interrupted; that is, the system is nonpreemptive. Therefore, each function needs to be short so others are not kept waiting for too long. For this reason, this method is sometimes called "cooperative multitasking." Many high-profile systems—Windows 3.1 and early versions of Mac OS, for instance—used cooperative multitasking.

After dividing the program into small tasks, you are free to let the scheduler handle the timing and order of execution. That way, you can concentrate on the single thread of execution you are interested in. For example, to change the clock so that it also shows seconds, the interval at which the CLOCK_TASK is scheduled could be reduced from one minute to one second. The rest of the system would remain the same. There would be no reason to change the Ethernet task or the user interface task.

Since you focus attention on one thread at a time, you produce less buggy code because you aren't confused by all of the intermixed functionality.

How it Works

So how does this scheduler work? You know that you can break the code into small tasks, which are chained together into threads of execution. You have a scheduler that keeps a list of tasks, much like a to-do list. Tasks are added to the list as the need arises, and they are deleted as the tasks are completed.

Inside of the scheduler, a handful of module variables keep track of the tasks to be run. The main one is the task list—an array of structures that holds information about which tasks to run and when to run them. Each entry in the list contains basic information about one task, including:

• A flag indicating that this entry is in use.

• A pointer to a function to execute.

• Time to wait before running.

• Interval information for recurring tasks.

Listing Three is the declaration of the task list. The only feature of the scheduler's data structures that is not obvious is the use of function pointers. The structure in Listing Three contains a pointer called FunctionPtr that points to a function that takes no parameters and returns nothing. Although function pointers may look funny in their declarations, their uses are fairly straightforward. As a refresher, a simple example is shown below:

// declare the function and pointer

int my_function(void);

int (*my_pointer)(void);

int my_integer;

// aim the pointer at the function

my_pointer=my_function;

// call the function using the pointer

my_integer=my_pointer();

A key component of the scheduling system is the system timer. In the task list data structure just presented, the StartTime attribute delays the running of a task until sometime in the future. This feature is used to schedule repetitive tasks at certain intervals. The scheduler uses a Now() function to get the current time (in milliseconds) to see if tasks are ready to run. Now() is a home-brewed function built around the DOS timer interrupt, which occurs every 55 milliseconds. The source code for my timer (TIMER.C) is available electronically. As you'll see, this timer brings with it some subtle behavior traits that you should be aware of. It provides a good facility for coarse timing control, but should not be used to control a real-time application.

Under the Hood

The scheduler module has three functions that you can use to schedule tasks. You can schedule a task to be run in the future, remove a task from the task list, and see if a certain task is currently scheduled to be run. These functions are listed in Listing Four. These function prototypes provide the basic building blocks to create a multithreaded application.

There are functions that act as interfaces to the scheduler, and you can set up tasks to run periodically or one at a time.

• ScheduleTask() adds a task to the task list. It starts at the current task number and goes backward through the list looking for a free slot. If it gets to the beginning of the task list, it wraps around to the end. The reason for this odd search order is to prevent starvation, a condition where one thread of execution is given a disproportionate amount of processor time.

• UnScheduleTask() performs a necessary clean-up task. It kills a currently scheduled task. It searches through the task list and removes the specified function from the list. If it finds a matching task in the list, it simply sets its InUse to False. Because the scheduler has no knowledge of what that particular task was doing, it is your responsibility to make sure that any killed threads are properly cleaned up (files closed, resources freed, and so on).

• TaskIsScheduled() is used to query the task list and see if a certain function is scheduled to run. Its operation is obvious: looping through the array of tasks, returning True if the specified function appears in the list, and if its corresponding InUse flag is True.

In addition to these functions, which are meant to be used by all threads, the scheduler also has three administrative functions that should be called only in special circumstances; see Listing Five.

• InitializeScheduler() initializes the scheduler by looping through the task list and setting the InUse flags to False.

• RunOneTask() digs through the task list and finds a task that is ready to run. Once it decides which task needs to be run next, it does some clean-up of the task list. If the task is periodic (if Type equals REPEAT), then this function takes care of rescheduling the task for its next run. Otherwise (if Type equals ONCE), it frees one slot in the task list. The final (and most important) job that it does is to call the function and wait for it to return. This scheduler is a bit strange in that it marks items off of its to-do list before actually completing them. This is intentional, so the slots in the task list will be free for the running task to use if necessary.

• ShutdownScheduler() sets a flag that tells the scheduler not to run any more tasks. It finishes the task that it is currently executing; any subsequent calls to RunOneTask() result in a return code of SCHEDULER_SHUTDOWN.

Converting Existing Programs

To convert existing programs to the new structure, the first thing you need to do is add the main program loop to the application. I added mine into main() (available electronically) like this:

while( RunOneTask()!=

SCHEDULER_SHUTDOWN ) {

// Do not put anything inside this loop

}

The whole program revolves around repeated calls to RunOneTask(). If there is a task that needs running, it runs, then RunOneTask() returns SCHEDULER_DID_ SOMETHING. If there are no tasks that are ready to run, it simply returns SCHEDULER_NOTHING_RUN.

When the program is ready to end, a call is made to ShutdownScheduler(), which sets a special flag in the scheduler module. This lets the current function complete gracefully and prevents any more tasks from being executed. Instead, further calls to RunOneTask() simply return the value SCHEDULER_SHUTDOWN. The main loop checks for this special value and ends its main program loop.

An Example of the Changes

The preEthernet version of our software had been written as a stack of functions; that is, when users entered a menu on the control station, the software would enter a function. The program would remain in a busy loop until the user pressed a key. Depending on which key users pressed, a different function would be called. If the key was EXIT, then the software returned from the original menu function.

However, the new multithreaded structure dictated that all functions be short and that they should run to completion. So now, the menu functions had to be broken up into smaller bits. Listing Six(a) is the code for the main menu presented in the old style, while Listing Six(b) is in the new style. A comparison of these two functions demonstrates the different method of calling. A simple call to MainMenu() has now been broken into two parts—one to MainMenu() and several calls to MainMenuLoop(). The first function does all of the one-time initialization of that menu, such as drawing the menu on the screen. The second function is the loop that waits for keyboard input.

While the old function would call WaitForKeyPress(), the new one cannot afford to wait. It must be short enough to give other tasks a chance to run. So the new function must instead call its nonblocking counterpart, which I call "PollForKeyPress()."

A Smaller Stack

The change from the old menu structure to the new one carries with it some memory savings. The multithreaded system uses a much smaller stack than the original system. Imagine a menu structure where the user has to go through several menus before he gets to his desired function. With each menu that he enters, the old system would push the function addresses and local variables onto the stack. When the user is finished, he would pop-pop-pop back out to main(), and then exit. The new structure calls the separate menu functions sequentially, with no stack history.

User Interface: Hyperlink Instead of Push/Pop

One side effect of changing to the new code structure is the flexibility to design user menus as state machines. Menus in the traditional system were structured as trees. Users would enter menus and then back out of them in the reverse order. In the new multithreaded system, the menu navigation can be structured in a more flexible way.

For example, if you wanted a special button that exits all menus and returns to the main start-up screen, it would be tedious to implement in the old system. The calling structure of the old program required going out the same way you came in. However, since the new UI is built around chaining (rather than stacking), the exit button is trivial to implement. There is no memory of previous function calls in the program's stack.

Queuing Policies and Starvation

The scheduler uses a first-in/first-out (FIFO) policy to determine which task to run next. This can be seen by inspecting ScheduleTask(), which adds tasks to the task list; and RunOneTask(), where the runtime task selection is done. The interaction of these two functions is what characterizes our scheduling algorithm.

Before releasing our industrial control product, we experimented with different scheduling policies—some of the experiments unintentional. For example, the first time we tested the system, ScheduleTask() was written so that new tasks were added to the next available slot in the list. RunOneTask() would also pick a task to run using the same method. This resulted in a last-in/first-out scheduling policy, and caused starvation of some tasks. In our case, one thread would take over most of the processor's time, while other threads would barely get a chance to run.

This early starvation problem has been fixed. Tasks are now added to the back of the list and pulled from the front of the list. This combination results in a first-in/first-out scheduling policy. In practice, this FIFO method works well and there is a good balance among all running threads.

Benefits of Cooperative Scheduling

Since each task is a function that runs to completion, you conveniently avoid some of the pitfalls of preemptive systems. Specifically, shared resources can be more easily managed because all functions are atomic.

For example, if I have a shared resource like a printer, a preemptive operating system must provide sophisticated mechanisms for mutual exclusion. Otherwise, two threads might end up using the same device, resulting in a garbled print-out.

However, with the nonpreemptive scheduler described here, mutual exclusion is much easier to achieve because all tasks are atomic. That is, they are run to completion without being interrupted by another task. This means that resource locking can be done with simple flags.

You can control access to your printer using a variable called PrinterInUse. Before printing, you read the variable to see if someone else is using the printer. If not, you can set the variable to True and start using the printer. This method works in our system because the individual tasks that make up this thread are atomic. There is no chance for the task to be interrupted between the checking of the flag and the setting of the flag to True. That is, there is no chance that some other thread could break in line between the checking and the setting of the flag. In a preemptive environment, a much more complex system has to be used to lock resources.

Timer Side Effects

Since the DOS timer interrupt occurs every 55 milliseconds, the scheduler has a granularity of 55 milliseconds. Recall that the main program runs in a loop, repeatedly calling RunOneTask(). Thus, from the scheduler's point of view, the clock looks like this: 0, 0, 0, 0, 55, 55, 55, 110, 110, 165, 165, 165, 220, 275, 275, 275, 275, 330, ... The clock's jerkiness is due to the varying times that it takes for tasks to execute.

This also means that you can only schedule tasks to run at multiples of 55 ms. If you scheduled a task to run every 10 ms, then the RunOneTask() function would keep looking at the clock waiting for 10 ms to pass. Due to the granularity of the system clock, the task would only get run after the minimum time of 55 ms.

Of course, tasks can be scheduled to run at 0 ms intervals—they will be run every time the scheduler works its way through the task list.

Latency in Task Scheduling

A more subtle feature of this scheduling system is that when a task's time has come, it may still have to wait for other ready tasks to complete. So, if 10 tasks all become ready at the same time, they will still have to be executed according to their order in the task list. Since there are no priorities, this system does not have a deterministic way of selecting which task to run first. Therefore, this system cannot be considered real time, and each task may experience considerable latency.

Accumulation of Latencies

Making matters worse, repeating tasks can accumulate latencies. You might schedule a repeating task to happen once per second. However, it would be naive to assume that this task would run exactly 86,400 times per day. If one task were delayed 55 ms, then all subsequent tasks would also be delayed. The time would not be made up elsewhere. In fact, these lines in RunOneTask() guarantee that these latencies accumulate:

case REPEAT:

// reschedule this task to run again later

StartTime=Now()+Interval;

break;

Thus, this system should not be used in real-time applications.

Suitability

For our industrial application, these limitations did not cause concern. Because we were only polling for input from the keyboard, serial ports, and Ethernet port, there were no hard timing deadlines. We did not care if we polled the Ethernet port 10 times per second or 100 times per second. As long as the system was responsive, we were okay. If we had been controlling a moving object or some other timing-critical application, we would need to use a real-time operating system. We found this scheduler to be suitable for our DOS-based application. However, its utility can be realized in other environments, such as embedded microcontrollers that run without an operating system at all.

Conclusion

It is important to design systems that do not require a significant investment in training. A toolbox of simple utilities, like the scheduler presented here, provides a way to create multiple execution threads in a single program, and does this with a minimal learning curve. This solution is quick to implement, requires no special training in theory of operation, and avoids some common problems found in more advanced systems.

DDJ

Listing One

#include "wattcp.h"
#define TELNET_PORT 23
#define BUFFER_SIZE 256
int main(int argc, char ** argv) {
   tcp_Socket far Socket;
   tcp_Socket * SocketPtr;
   char Buffer[BUFFER_SIZE+1];
   int bytes;
   sock_init();
   SocketPtr=&Socket;
   // tell tcp to listen for a connection on TELNET port (23)
   // this call does not block...
   tcp_listen(SocketPtr,TELNET_PORT,0L,0,NULL,0);
   // wait for a connection
   while(!sock_established(SocketPtr)) {
      tcp_tick(NULL);
   }
   // a connection was made... send a string to the caller
   sock_mode(SocketPtr,TCP_MODE_ASCII);
   sock_puts(SocketPtr,"hello\r\n");
   // read what the caller is sending to us and print it out
   // only end when the caller disconnects
   while(tcp_tick(SocketPtr)) {
      if(sock_dataready(SocketPtr)) {
         StringFromSocket(Buffer,BUFFER_SIZE);
         bytes=sock_gets(SocketPtr,Buffer,BUFFER_SIZE);
         Buffer[bytes]=0;
         printf("received: %s", Buffer);
      }
   }
   printf("socket closed\n");
}

Back to Article

Listing Two

START{
   schedule CLOCK_TASK immediately
   schedule ETHERNET_TASK immediately
   schedule USER_INTERFACE_TASK immediately
   do forever
      let the "scheduler" pick a task to run
}