Every day of our lives we spend all of our conscious moments engaged in a wide variety of activities, from the complex to the mundane. Sometimes these activities can be routine, such as eating, driving, or performing repetitive tasks at work. Other times, they can be activities with which we are less familiar, either because we have never done them before, or simply because we have not yet mastered them. Altogether, these activities fully occupy our lives, both physically and mentally, for even when we are not physically active, our minds are engaged in the activity of conscious thought. And, despite their variety, all of these activities have one thing in common -- they require following processes.

A process is nothing more than a sequence of steps that, when followed in order, completes an activity or some subset thereof. Without processes to serve as guides, we would be unable to function in any capacity, because we would be unable to determine what to do next. And, although we often do not actively think about the processes we follow, particularly routine ones, we still follow them intuitively. This concept is important to understand, because it allows for the development of automation technology. Throughout history, inventors have been able to examine the processes which people follow and devise machinery which, by following roughly the same processes, accomplishes the same goals, without requiring the same level of human exertion. These automated time- and labor-saving devices range from the simple, such as the loom, which eliminates much of the tedium of weaving cloth, to the complex, such as the automated telephone switch, which can do the job of many human telephone operators in a fraction of the time.

In the past few decades, a new class of automated machinery has come about, utilizing sophisticated electronic circuitry to follow complex processes that would be impossible for mechanical contraptions. This class of machinery primarily encompasses the computer, which is perhaps the ultimate automation device. Because the computer is programmable, it can be configured to follow a vast array of different processes, and complete a wide variety of tasks. And, even though some processes from human life are beyond its capabilities, it can still be used to automate portions of these processes. Thus, today the computer plays either a primary or supporting role in many different processes in which we are involved.

Of course, life is not quite as straightforward as simply following processes. Because there is only a limited amount of space in the world, it is quite possible for the processes that various people are following to conflict with each other. If these conflicts are not solved gracefully, the involved processes may never be completed, so coordination procedures are necessary. Generally, there are five types of coordination that people are concerned with:

Sometimes several people can be using the same resource for their own purposes, and changes they make to the resource can leave it in a different state depending on who made the last change. The next person who wishes to use the resource can then no longer be guaranteed to find it in a particular state. For example, if three people share the use of a car, and it is agreed that one person will drive to the store to buy groceries and another (at a different time) will fill up the gas tank, both while the third person is away, depending on the order in which the first two carry out their chores the third may find either a full tank or a partially spent tank. This problem is known as a race condition, because the outcome varies depending on who "wins" the race.

There are many resources in the world which can only be used by one person or group at a time. For example, an airplane seat can be sold only to one person per flight, because multiple people cannot share it. Similarly, on a single-lane bridge, only cars going in one direction can pass at a time without causing a collision. This is known as exclusive use. Usually people can ensure exclusive use through the use of a communication or signalling system. In the former example, a system of reservation records can alert an airline employee that a seat has already been sold before another sale is made. In the latter example, traffic signals (and laws about obeying the traffic signals) can bring order to the situation.

Whenever there is a need to enforce serial access to a resource (such as with exclusive use), there is always a chance that more than one person will show up at the same time wanting to use it. For example, in a traffic intersection, it is possible for several cars to arrive at once, all seeking to pass through. There has to be some means of determining who gets to go first -- this process is known as arbitration. Sometimes arbitration can be accomplished by mechanisms such as traffic signals, but other times (such as at a four-way stop) a decision must be made on the basis of who arrived first. Unfortunately, this isn't always clear, and making a decision can take an indefinite amount of time when there is no obvious victor from the start. This situation is known as arbitration failure, and often the only solution is to wait for someone to finally make a decision.

Sometimes the processes in which people are engaged are dependent upon other processes being completed first, possibly by other people. For example, on an automobile assembly line, it is necessary for the body to be constructed before the doors can be added on. Attempting to add the doors first would be pointless, because there would be nowhere to attach them. Thus, if there is no body ready to have doors added, the process for adding doors has to be suspended until the process for creating the next body is complete. This is known as synchronization.

Obviously, there are many cases where people have to wait for other people to do something. Synchronization, arbitration and exclusive use all require this. However, if everyone in such a situation is waiting for someone else to do something first, then no one will ever be able to do anything. For example, traffic gridlock can occur when someone is attempting to turn at an intersection, which is blocked because someone else is attempting to turn at the next intersection, which is also blocked because a third person is attempting to turn at a third intersection, which is blocked because of a fourth person attempting to turn at a fourth intersection, which is blocked because of the first person attempting to turn at the first intersection. In this case, none of the four people will ever turn, because in order for any of them to turn, one of the other three must turn first to clear up some intersections. When discussing processes, this situation is known as deadlock, because all of the involved processes are effectively dead because of locks they have on resources. Usually someone in such a situation will eventually notice and abort the process, allowing normal flow to resume, and often warning signs can even be spotted ahead of time to avoid deadlock in the first place.

Each of these five coordination problems can be solved, in time, by people who encounter them in the course of following processes, largely by relying on past experience and reason. However, computers and other automated machinery have neither past experience nor reason to rely upon for answers. If they are to coordinate processes successfully, the procedures for coordination must be just as automated as the processes themselves. It turns out that foolproof, automated coordination mechanisms can be very difficult to implement, because things that the human brain can reduce to "obvious" are not necessarily so in actuality. Given the vast number of computer programs that run concurrently in the world today, crafting reliable coordination schemes for all of them would be a nearly impossible task. Yet, we cannot risk the corruption of valuable data that would occur by ignoring these five problems.

Fortunately, over the years various computer scientists have studied these problems extensively, and out of all this research has come a handful of great ideas, which can be implemented in a standard, straightforward manner to ensure proper coordination in computer systems. These ideas are great because they allow most programmers to go about their business without becoming mired in the details of coordination on a minute scale. They are also great because they provide solutions that will always work to problems that will always exist. They are basic, powerful, and timeless.

Next section: Races and Exclusive Use