5.1 Coordinating Order of Execution

Let's say we have three threads executing concurrently labeled thread A, thread B, and thread C. All three threads are involved in list processing. The list is to be sorted and searched and the results displayed. Each thread is assigned a task; thread A is to display the results of the search, thread B is to sort the list, and thread C is to search the list. First, the list has to be sorted then multiple concurrent searches can occur on the list. The results of the searches are then displayed. If these threads' tasks are not synchronized properly, thread A may attempt to display results not yet generated that violates the postcondition of the process. The precondition in the list must be sorted prior to searching. If searches start before the list is sorted, the search may generate the wrong results. The three threads require task synchronization. Task synchronization enforces preconditions and postconditions of logical processes. Figure 5-1 shows a UML activity diagram for this process.

Figure 5-1. Activity diagram for sorting, searching, and displaying the contents of a list.

The thread B's sort must occur first, then forking to the multiple searches spawned by thread C takes place. The threads are then joined and thread A displays the results.

5.1.1 Relationships between Synchronized Tasks

There are four basic synchronization relationships between any two threads in a single process or between any two processes within a single application: start-to-start (SS), finish-to-start (FS), start-to-finish (SF), and finish-to-finish (FF). These four basic relationships characterize the coordination of work between threads and processes. Figure 5-2 shows activity diagrams for each synchronization relationship.

Figure 5-2. The synchronization relationships that can exist between tasks A and B.

5.1.2 Start-to-Start (SS) Relationship

In a start-to-start synchronization relationship, one task cannot start until another task starts. One task may start before the other but never after. For example, let's say we have a program that implements an avatar. The avatar is a computer-generated talking head. The avatar provides a kind of personality for the software. The program that implements the avatar has several threads. Here, we will focus on thread A, which controls the animation of the mouth and thread B, which controls the sound or voice. We want to give the illusion that the sound and mouth animation are synchronized. Ideally, they should execute at the same precise moment. If multiple processors are involved, both threads may start simultaneously . The threads have a start-to-start relationship. Because of timing conditions, it is allowed that thread A start slightly before thread B (not much before for illusion's sake) but thread B cannot start before thread A. The voice has to wait for the animation. It is not desirable to hear a voice before the mouth animates (unless it is simulating voice dubbing).

5.1.3 Finish-to-Start (FS) Relationship

In a finish-to-start synchronization relationship, task A cannot finish until task B starts. This type of relationship is common with parent “child processes. The parent process cannot complete execution of some operation until it spawns a child process or it receives a communication from the child process that it has started its operation. The child process continues to execute once it has signaled the parent or supplied the needed information. The parent process is then free to complete its operation.

5.1.4 Start-to-Finish Relationship

A start-to-finish synchronization relationship is the reverse of the finish-to-start relationship. In a start-to-finish synchronization relationship, one task cannot start until another task finishes. Task A cannot start execution until task B finishes executing or completes a certain operation. If process A is reading from a pipe connected to process B, process B must first write to the pipe before process A reads from it. Process B must at least complete one operation, writing a single element to the pipe before process A starts. The producer-consumer threads in Chapter 4 are another example of a finish-to-start relationship. The sort-search threads in Figure 5-1 also demonstrate this relationship. The sort thread had to complete its work before the search threads were to search the list. In all these cases, one thread or process has to complete an operation before another thread or process attempts to execute its operation. Unless this work is coordinated, the goal of the process, thread, or application would fail or give inaccurate results.

The finish-to-start relationship usually suggests there is an information dependency between the tasks. With information dependency, interthread or interprocess communication is required from one or more tasks in order for a thread or process to operate correctly. The search would produce incorrect results unless the sort was performed. The consumer thread would have no files to process unless the producer thread produced the files to be searched.

5.1.5 Finish-to-Finish Relationship

In a finish-to-finish synchronization relationship, one task cannot finish until another task finishes. Task A cannot finish until task B finishes. This again can describe the relationship between parent and child processes discussed in Chapter 3. The parent process must wait until all its child processes have terminated before it is allowed to terminate. If the parent process terminates before its child processes, those terminated child processes become zombied. Parent processes should not finish (exit the system in this case) until all its child processes have finished executing. The parent process achieves this by either calling a wait() function for each of its child processes, or waiting for a mutex or condition variable that can be broadcast by child threads. Another example of a finish-to-finish relationship is the boss “worker model. The boss thread's job is to delegate work to the worker threads. It would be undesirable for the boss thread to terminate before the worker threads. New requests to the system would not be processed , existing threads would have no work to perform, and no new threads would be created. If the boss thread is the primary thread and it terminates, the process would terminate along with all the worker threads. In a peer-to-peer model, if thread A dynamically allocates an object passed to thread B and thread A terminates, the object is destroyed along with thread A. If this is done before thread B has had a chance to use it, a segmentation fault or data access violation will occur. In order to prevent these kinds of errors with threads, termination of threads is synchronized by using the pthread_join() function. A call to this function causes the calling thread to wait on the target thread until it finishes. This creates finish-to-finish synchronization.