Parallel Programming in C for the Transputer
© D. Thiébaut, 1995



5-3 Unsynchronized execution of multitasks: ProcRun

We have seen that ProcPar and ProcParList exhibit a high level of atomicity in that neither one will return to its caller until all the tasks that were launched have completed. In some situations, however, we may want to launch tasks but still continue with the computation. A good example is the creation of background tasks that receive messages from channels and route them on to other nodes. Such tasks should be started as soon as the Node becomes an active player in the computation, and should remain active relaying messages until the computation ends. Clearly, using ProcPar or ProcParList in that case would force us to artificially break the logical sequence of the main program (or some other function) into several separate blocks or functions.


ProcRun

The alternative is to call ProcRun, or one of its derived functions, ProcRunHigh, or ProcRunLow.

void ProcRun(Process *)
void ProcRunHigh(Process *)
void ProcRunLow(Process *)

We will look at ProcRunHigh and ProcRunLow in a later section, when we deal with task priority. For right now let's concentrate on ProcRun.

It differs mainly from the ProcPar function in that it is unsynchronized: The execution of the new task launched by ProcRun is not synchronized to the execution of the task that called ProcRun. With ProcPar, the caller has to wait for all the tasks launched to complete. With ProcRun, the caller continues and executes the code following ProcRun.

Let's investigate how ProcRun works with a new example. We will modify multi_1.c and launch Task1 and Task2 with ProcRun instead of ProcPar. 

main(void)
{
     Process *Task1P, *Task2P;
     char string[] = "This is the test string Task1 is working on...";
     int  FibNumber = 64;
     int  Task1Flag = 0, Task2Flag = 0;

     /*--- allocate storage for the processes ---*/
     Task1P = ProcAlloc(Task1, WS_SIZE, 2, string, &Task1Flag);
     Task2P = ProcAlloc(Task2, WS_SIZE, 2, &FibNumber, &Task2Flag);

     /*--- verify that storage could be allocated ---*/
     if ((Task1P==NULL) || (Task2P==NULL))
     {
          printf("Error allocating processes\n");
          exit(1);
     }

     /*--- start the two tasks ---*/
     ProcRun(Task2P);
     ProcRun(Task1P);

     printf("Tasks done\nTask1's result: %s\nTask2's result: %d\n\n",
          string, FibNumber);

     ProcFree(Task1P);
     ProcFree(Task2P);
     exit(0);
}

Listing 5-2: Replacing ProcPar by two ProcRun (this code won't work!).

What do you think of the program above? We have kept almost every line of code of multi_1.c in creating multi_2.c, except that the call to ProcPar has been replaced by two calls to ProcRun, one to start Task1, and the other to start Task2. But will it work?

Let's analyze it. When the first ProcRun is called, it adds Task1 to the list of active but waiting tasks. Depending on when the current quantum expires, the main program may or may not have time to execute the second ProcRun. Let's assume that the quantum had just started, and the main program not only has time to execute the second call to ProcRun, but also continues and executes the printf statement... But the results of Task1 and Task2 aren't ready yet!

The above program will not work! The reason is that because we have removed the synchronization implemented as part of ProcPar, we have lost the (implied) knowledge of when Task1 and Task2 are done. In this example, the synchronization was needed. Since we lost it by using ProcRun, we must reinstate it somehow. Flags are good candidates for this type of application.

Using flags to synchronize tasks

The solution is simple. Both Task1 and Task2 will maintain individual flags. As long as the task is not done with its computation, it will maintain its flag false. A true flag will therefore indicate that the result can be used. Since the flags are set by only one task and checked by another one (the main program) we do not need more sophistication than using integer or char variables for the flags. We'll see later on that in some cases when flags are modifiable by several tasks, we'll have to use more powerful flags than simple variables: semaphores.

main(void)
{
     Process *Task1P, *Task2P;
     char string[] = "This is the test string Task1 is working on...";
     int  FibNumber = 64;

     int  Task1Done = 0, Task2Done = 0;


     /*--- allocate storage for the processes ---*/
     Task1P = ProcAlloc(Task1, WS_SIZE, 2, string, &Task1Done);
     Task2P = ProcAlloc(Task2, WS_SIZE, 2, &FibNumber, &Task2Done);

     /*--- verify that storage could be allocated ---*/
     if ((Task1P==NULL) || (Task2P==NULL))
     {
          printf("Error allocating processes\n");
          exit(1);
     }

     /*--- start the two tasks ---*/
     ProcRun(Task2P);
     ProcRun(Task1P);


     while ((Task1Done==0) && (Task2Done==0))
          /* wait */;

     if (Task1Done)
          printf("Task1 finished first\n");
     else
          printf("Task2 finished first\n");



     while ((!Task1Done) ||(!Task2Done))
          /* wait */;


     printf("Both tasks done\nTask1's result: %s\nTask2's result: %d\n\n",
          string, FibNumber);
     ProcFree(Task1P);
     ProcFree(Task2P);
     exit(0);
}

/* -------------------------------------------------------------------- */
/* TASK1                                                                */
/* Transforms characters in "string" to uppercase                       */
/* -------------------------------------------------------------------- */
void Task1(Process *p, char *string, int *Task1Done)
{
	...

     *Task1Done = 1;

}

/* -------------------------------------------------------------------- */
/* TASK2                                                                */
/* Computes the xth fibonacci number                                    */
/* -------------------------------------------------------------------- */
void Task2(Process *p, int *x, int *Task2Done)
{
	...
     *Task2Done = 1;
}

Listing 5-3: Listing of multi_2.c. ProcPar replaced by ProcRun. Synchronization now implemented through the use of flags.

EXERCISES

 
5-1

The example programs that we have used in this chapter make use of the parallel tasks only once during the execution of the program. Many times it is necessary to run a task, or group of tasks several times during the program, with different sets of parameters. In such cases, the function ProcParam comes in handy.

void ProcParam(Process *, p1,...)

ProcParam takes a Process pointer initialized by ProcAlloc, along with a new list of parameters. This list should be similar to the list passed to ProcAlloc, in allocation size and number of parameters. For example, assume that we want to use Task2 twice in a program, to compute the 13th and 27th terms of the Fibonacci series. The following code segment shows how this could be done.

Process *Task2P;
int	   a=13, b=27;
...
Task2P = ProcAlloc(Task2, WS_SIZE, 1, &a);
...
ProcPar(Task2P,0);
...
ProcParam(Task2P,&b);
...
ProcPar(Task2P,0);

Rewrite multi_1.c so that it runs Task1 and Task2 on three sets of data. The first set of data is the original string and value of FibNumber. The second and third sets are strings and numbers of your choice, different from the set that precedes them. Use different character arrays for the three strings, string1, string2, and string3.

.


 
 
5-2
Write a program that measures the multiprogramming time-slice, or quantum. The program should print the value of the quantum, in milliseconds, and then stop by returning control to DOS.

Hints: A task can read the value of its associated timer through a call to the function Time() (note the uppercase T), which returns an integer number of ticks. Time is defined in conc.h. Each tick represents an interval of 64 ms[1 ]. If you write a non-multitasked loop that keeps on reading the value of the timer, you will find that the same value of the counter is read several times in a row, and every so often the value increases by 1, indicating that a new 64 ms interval has started. Using this knowledge, you can write a program that measures the quantum. Also, you should know that the first quantum experienced by a program just loaded in a transputer isnever a full quantum.


 
 
5-3
Adapt the prime-finding program of Chapter 4 to multitasking. In particular, your program should run on only one transputer, the root, and should rely on two multitasked processes to compute and print the primes. The first task will compute the primes and store them in an array as they are found. The second task will keep on checking the array, and will print each prime number found in the array. You are free to chose the implementation of the array shared by the two tasks.

Make sure that the program exits gracefully, and that only one task is doing printf statements, while the other computes the primes. To make the program more efficient, have the print module deschedule itself if it finds the array empty (check the ProcReschedule function described int he LS C documentation!)


 




[Previous] [HOME] [NEXT]