Yesterday we talked about interrupts, lightweight threads and multi tasking. There are lots of related issues that you'd explore in a course on computer architecture and assembly language programming. For example, we haven't talked about how functions or subroutines are handled at the machine level. There are machine instructions that allow a program to jump to a subroutine by saving the program counter (and possibly other registers) to a special part of memory called a stack reserved for this purpose. Every time you jump to (or call) a subroutine you "push" the program counter onto the top of the stack and when you return from a subroutine call you "pop" off the top item on the stack and restore the program counter to where you left off before calling the subroutine. With a little care, this works if you call one subroutine in the midst of executing another. You can "nest" subroutine calls as deep as you like or at least as deep as you've set aside stack space in memory to store the necessary register contents. Stacks are also used to keep track of the values of arguments and local variables when calling functions or when the operating system has to perform some routine tasks when in the midst of running one of your programs. Stacks and various types of queues, e.g., of the first in first out (FIFO) and last in first out (LIFO) varieties, are additional examples of data structures that are used frequently in designing algorithms. I think I'll write about stacks and subroutine calls tomorrow.

Today, I thought we'd take a somewhat more detailed looks at multi tasking and lightweight threads for applications in robotics. Consider the following extension of the problem that we looked at on Friday. On Friday, I defined a program that would drive a little robot to seek and drive toward a light. Now we'd like to modify that program so that the robot isn't so single minded (or single threaded in this case). Specifically, we'd like the robot to watch out for collisions by detecting when its front bumper switch is depressed when in comes in contact with a wall or someone's foot. Note that this requires the robot to do two things at once, like chewing gum and watching television. We're going to consider two different methods for managing this feat but we'll start with a little more background on the C programming language.

In C, every program must have a function called main which is called when the program is started. This function is required to take a set of formal parameters (which we'll ignore here) and return an integer value (which we'll also ignore here). The main procedure is run in a separate process and any child processes that it spawns are children of that process. The C function execi creates a new process (a lightweight thread) in which it calls the function that appears as it's first argument; execi returns a handle for the process that the parent process can use to kill the process when it's done what it was created for.

As usual, squint at the syntax and ignore the other arguments except to note that these arguments allow the programmer to tell the operating system to assign the newly-minted process a priority level and allocate a particular amount of stack space to handle subroutine and procedure calls (we'll have more to say about subroutines and the stack tomorrow). The seek_light function is exactly as we described it on Friday except that it's formal parameters and return type have been changed to meet the requirements for the execi function.

In this first implementation that combines seeking light and watching for collisions, the main function works by controlling a thread to seek light, killing it off when a collision is detected and it's time to take evasive action and creating the light seeking thread anew when the danger is past. Most of the time, main just sleeps waking up from time to time to check on the front bumper. I haven't bothered to define the take_evasive_action function but assume that it just backs up a random distance, turns a random angle and then sets off in a new direction (being able to perform random actions is quite useful in programming robots). Here's the code for the main and light_seek functions.

int main(int argc, char *argv[]) {
  /* declare a variable of type process identifer */
  pid_t seeker_thread ;
  /* start the light seeking thread */
  seeker_thread = execi(&seek_light, 0, 0, PRIORITY_NORMAL, DEFAULT_STACK_SIZE);
  /* loop forever watching for a collision */
  while (1) {
    if ( front_bumper > 1 ) {
      /* if you detect a collision then kill the seeker */
      kill(seeker_thread);
      /* take some appropriate evasive action */
      take_evasive_action() ;
      /* and then resume seeking the light */
      seeker_thread = execi(&seek_light, 0, 0, PRIORITY_NORMAL, DEFAULT_STACK_SIZE);
    } 
    /* otherwise put the parent thread to sleep and let the seeker do its thing */
    else sleep(1) ;
  }
}

int seek_light(int argc, char *argv[]) {
  int on = 100 ;
  int off = 0 ;
  while (1) {
    if (left_sensor > right_sensor) {
      right_motor = on ;
      left_motor = off ; 
    } 
    else {
      right_motor = off ;
      left_motor = on ; } 
  }
}

In the second implementation, I'm going to have the main program spawn two processes, one that seeks light and a second that watches for collisions. But we have a problem in this case because both the light seeking and the collision detection threads want to control the motors (collision detection indirectly by calling take_evasive_action when it senses that the switch attached to the front bumper has been depressed). This is actually quite a common situation in programming and occurs whenever you have a resource - could be a portion of protected memory or it could be a peripheral device - that only one program at a time can make use of.

Whenever you use an ATM to make a cash withdrawal, the ATM checks on your current balance and debits your account by the amount of the withdrawal before giving you the cash. Suppose this is the code that the ATM machine runs to perform the checks and debits.

if (withdrawal < balance) {
  balance = balance - withdrawal ;
  issue_cash(withdrawal) ;
}       

Now imagine that you and a confederate each go to separate ATMs and at exactly the same time you make withdrawals to the tune of $90 and let's say that your current balance is $100. What if the bank processed the statements for the two threads corresponding to your and your friends separate transactions as follows:

ATM 1: (withdrawal < balance) => 90 < 100
ATM 2: (withdrawal < balance) => 90 < 100
ATM 1: balance = balance - withdrawal => balance = 10
ATM 2: balance = balance - withdrawal => balance = -80

Voila, each of you get $90 in cash. Now you can't carry out this particular bit of petty larceny because the program that processes transactions wraps the code fragment above with pair of statements, the first of which requests exclusive control over the location in memory where your balance is stored and the second which relinquishes control when the code fragment has conducted its business. If ATM 1 executes its code fragment first, then ATM 2 will find its request denied and will be forced to sleep until ATM 1 has finished its business at which point ATM 2 will be woken up and allowed to complete its business. Of course in this scenario, whichever one of you is at ATM 2 will be disappointed.

You can find out more about mechanisms for synchronizing multiple threads of control by searching for information about "critical sections" and "semaphores" on the web. For our purposes, we can get by using the simple expedient of a global value so that the two threads vying for control of the motors can communicate with one another.

The next version of main starts two threads one for seeking light and one for detecting collisions. These two threads then run independently. We could just put main in an infinite loop but this would take up CPU cycles so instead we put it to sleep for how ever long we want robot to seek light and avoid obstacles and then kill off the threads when the times up and we want to terminiate the program. I've rewritten seek_light and put the bump detection code in a separate function called avoid_bumps. The functions seek_light and avoid_bumps communicate through the global variable, evasive_action_in_progress; in particular, seek_light goes to sleep if it sees that evasive_action_in_progress is 1.

int main(int argc, char *argv[])
{
  pid_t seeker_thread, bumper_thread ; 
  /* start the light seeking and collision detecting threads */
  seeker_thread = execi(&seek_light, 0, 0, PRIORITY_NORMAL, DEFAULT_STACK_SIZE);
  bumper_thread = execi(&avoid_bumps, 0, 0, PRIORITY_NORMAL, DEFAULT_STACK_SIZE);
  /* go to sleep for a couple of minutes */
  sleep(120);
  /* now kill the threads and halt */
  kill (seeker_thread);
  kill (bumper_thread);
  return 0;
}

int evasive_action_in_progress = 0 ;

int seek_light(int argc, char *argv[]) {
  int on = 100 ;
  int off = 0 ;
  while (1) {
    /* if there's an evasive action in progress go to sleep */
    if (evasive_action_in_progress == 1) 
      sleep(1) ; 
    /* otherwise seek the light */
    else if (left_sensor > right_sensor) {
      right_motor = on ;
      left_motor = off ; 
    } 
    else {
      right_motor = off ;
      left_motor = on ; } 
  }
}

int avoid_bumps(int argc, char *argv[]) {
  while (1) {
    if (front_bumper == 1) {
      /* if you detect a collision signal you want control of the motors */
      evasive_action_in_progress = 1
      /* take whatever evasive action seems appropriate */
      take_evasive_action() ;
      /* and then relinquish your control of the motors */
      evasive_action_in_progress = 0
    } 
    /* otherwise go to sleep for a while and let the seeker do its thing */
    else sleep(1) ;
  }
}

There's a bug in this implementation but one that you can fix pretty easily. I'm assuming that the function take_evasive_action takes some time to run, perhaps a couple of seconds to actually negotiate its evasive maneuvers. But note that it's possible that seek_light could still modify the motor control parameters, left_motor and right_motor, for perhaps a couple of milliseconds after take_evasive_action is called. Depending on how take_evasive_action is implemented this could cause problems. We could fix this by adding another global variable so that seek_light could notify avoid_bumps that it has seen that evasive_action_in_progress is set 1; avoid_bumps would wait until it receives this message before calling take_evasive_action. We could also use the C-language semaphore library which makes it much easier to implement this sort of communication and synchronization.

There are all sorts of clever solutions to this simple robot problem involving the use of multiple threads of control, semaphores, interrupt handling, the ability to make threads go to sleep or alter their priority. (By the way, the title for today's entry, "Do Robots Sleep?", owes a debt to Philip K. Dick's "Do Androids Dream of Electric Sheep?" which was adapting for the movies by Ridley Scott and appeared in theaters as "Blade Runner.") Solutions involving lots of threads can be pretty complicated especially running on tiny little computers with slow clocks and little memory. (The RCX microcomputer that comes with the Lego Mindstorms Robot Invention System is based on the Hitachi H8 family of micro controllers which have a top clock speed of 16MHz (million Hertz). The RCX comes with 32KB (thousand bytes) of memory. Compare this with modern PCs that typically have processors rated at 1GHz (thousand million Hertz) or more and come with 256MB (million bytes) or more.) If you have a slow processor running lots of processes, you'll probably find some of your processes starved for CPU cycles. In general, programs that involve lots of threads can be tricky to manage.

We're already seeing educational and entertainment robots with much faster CPUs and lots more memory; however, there is a tradeoff. It might seem that that you can never have too much memory or too fast a processor. Unfortunately fast clocks and memory cost in terms of the cost of the products and the power that they require. Even a little Lego robot can wear down its batteries in a matter of minutes if it's running its motors a lot or using its infrared port to communicate with another robot. Some of these robot implementation problems seem merely temporary inconveniences; after all, you might say, processors will get faster, batteries will last longer and everything will get cheaper. However, this rosy picture of the future is cold comfort when you're trying to get a robot to do something today.