3.10 Dividing the Program into Tasks

3.10 Dividing the Program into Tasks

When considering dividing your program into multiple tasks, you are introducing concurrency into your program. In a single processor environment, concurrency is implemented with multitasking . This accomplished by process switching. Each process executes for a short interval, then the processor is given to another process. This occurs so quickly that it gives the illusion that the processes are executing simultaneously . In a multiprocessor environment, processes belonging to a single program can all be assigned to the same processor or different processors. If the processes are assigned to different processors, then the processes will execute in parallel.

Two levels for concurrent processing within an application or system are the process level and the thread level. Concurrent processing on the thread level is called multithreading, which will be discussed in the next chapter. The key to dividing your program into concurrent tasks is identifying where concurrency occurs, and where you can take advantage of it. Sometimes concurrency is not absolutely necessary. Your program may have a concurrency interpretation yet serially execute just fine. The concurrency might benefit your program with increased speed and less complexity. Some programs have natural parallelism, while others are naturally sequential by nature. Some programs have dual interpretations.

When decomposing your program into functions or objects, the top-down approach is used to break down the program into functions and the bottom-up approach is used to break down the program into objects. Once this is done, it is necessary to determine which functions or objects are best served as separate programs or subprograms while others will be executed by threads. These subprograms will be executed by the operating system as processes. The separate or processes perform the tasks you have designated them to do.

A program separated into tasks can execute simultaneously in three ways:

1. Divide the program into a main task that creates a number of subtasks .

2. Divide the program into a set of separate binaries.

3. Divide the program into several types of tasks in which each task type is responsible for creating only certain tasks as needed.

These approaches are depicted in Figure 3-13.

Figure 3-13. Approaches that can be used to divide a program up into separate tasks.

For example, a rendering program can use these approaches. Rendering describes the process of going from a database representation of a 3D object to a shaded 2D projection on a view surface (computer screen). The image is represented as shaded polygons that exact the form of the object. The stages of the render process are shown in Figure 3-14. It can be broken down into separate tasks:

Figure 3-14. The stages of the render process.

1. Set up the data structure for polygon mesh models.

2. Apply linear transformations.

3. Cull back- facing polygons.

4. Perform rasterization.

5. Apply hidden surface removal algorithm.

6. Shade the individual pixels.

The first task is representing the object as an array of polygons in which each vertex in the polygon uses 3D world coordinates. The second task is applying linear transformations to the polygon mesh model. These transformations are used to position objects into a scene and to create the view point or view surface (what is seen by the observer from the view point they are observing the scene or object). The third task is culling back-facing surfaces of the objects in the scene. This means lines generated from the back portion of objects not visible from the view point are removed. This is also called back-face elimination . The fourth task is converting the vertex-based model to a set of pixel coordinates. The fifth task is removing any hidden surfaces. If there are objects interacting in the seen, objects behind others, for example, these surfaces are removed. The sixth task is shading the surfaces.

Each task is saved separately and compiled into standalone executable files. Task1 , Task2 , and Task3 are executed sequentially and Task4 , Task5 , and Task6 are executed simultaneously. In Example 3.5, approach 1 is used to execute our rendering program.

Example 3.5 Using approach 1 to create processes.

 #include <spawn.h> #include <stdlib.h> #include <stdio.h> #include <sys/wait.h> #include <errno.h> #include <unistd.h> int main(void) {    posix_spawnattr_t Attr;    posix_spawn_file_actions_t FileActions;    char *const argv4[] = {"Task4",...,NULL};    char *const argv5[] = {"Task5",...,NULL};    char *const argv6[] = {"Task6",...,NULL};    pid_t Pid;    int stat;    //...    // execute first 3 tasks synchronously    system("Task1 ...");    system("Task2 ...");    system("Task3 ...");    // initialize structures    posix_spawnattr_init(&Attr);    posix_spawn_file_actions_init(&FileActions);    // execute last 3 tasks asynchronously    posix_spawn(&Pid,"Task4",&FileActions,&Attr,argv4,NULL);    posix_spawn(&Pid,"Task5",&FileActions,&Attr,argv5,NULL);    posix_spawn(&Pid,"Task6",&FileActions,&Attr,argv6,NULL);    // like a good parent, wait for all your children    wait (&stat);    wait (&stat);    wait (&stat);    return(0); } 

In Example 3.5, from main() Task1 , Task2 , and Task3 are executed using the system() function. Each of these tasks is performed synchronously to the parent process. Task4 , Task5 , and Task6 are performed asynchronously to the parent process using posix_spawn() functions. The ellipse (...) is used to indicate whatever files the tasks require. Parent process calls three wait() functions. Each waits for one of the Task4 , Task5 , and Task6 to terminate.

Using approach 2, the rendering program can be launched from a shell script. The advantage of using a shell script is all of the shell commands and operators can be used. For our render program, the & and && metacharacters are used to manage the execution of the task:

 Task1 ... && Task2 ... && Task3 Task4 ... & Task5 ... & Task6 

Here, Task1 , Task2 , and Task3 are executing sequentially under the condition the previous task executed successfully by using the && metacharacter. Task4 , Task5 , and Task6 executed simultaneously using the & metacharacter. The UNIX/Linux environments use metacharacters to control the way commands are executed. These are some of the metacharacters that can be used to control execution of several commands:

&&	Commands separated by && tokens causes the next command to be executed only if the previous command executes successfully.
	Commands separated by tokens causes the next command to be executed only if the previous command fails to execute successfully.
;	Commands separated by ; tokens causes the next command to be executed next in the sequence.
&	Commands separated by & tokens causes all the commands to be executed simultaneously.

Using approach 3, the tasks are categorized. When decomposing a program, it is a good technique to see if there are categories of tasks present. For example, some tasks are concerned with the user interface, creating it, extracting input from it, sending it to output, and so on. Other tasks perform computations , manage data, and so on. This is a useful technique when designing a progam. It can also be used in implementing a program. In our render-program, we can group tasks into several categories:

• Tasks that perform linear transformations

  Viewing transformations

  Scene transformations

• Tasks that perform rasterization

  Line drawing

  Solid area filling

  Rasterizing polygons

• Tasks that perform surface removal

  Hidden surface

  Back-surface elimination

• Tasks that perform shading

  Pixel

  Scheme

Categorizing our tasks will allow our program to be more general. Processes only create other processes of a certain category of work as needed. For example, if our program is to render a single object and not a scene, then it would not be necessary to spawn a process that performs hidden surface removal; back-surface elimination may be sufficient. If the object is not to be shaded, then it would not be necessary to spawn a task that performs shading; only line drawing rasterization would be nesssary. A parent process or a shell script can be used to launch our program using approach 3. The parent can determine what type of rendering is necessary and pass that information to each of the dedicated processes so that they will know which processes to spawn. The information can also be redirected to each of the dedicated processes from the shell script. In Example 3.6, approach 3 is used.

Example 3.6 Using approach 3 to create processes. The tasks are launched from a parent process.

 #include <spawn.h> #include <stdlib.h> #include <stdio.h> #include <sys/wait.h> #include <errno.h> #include <unistd.h> int main(void) {    posix_spawnattr_t Attr;    posix_spawn_file_actions_t FileActions;    pid_t Pid;    int stat;    //...    system("Task1 ..."); //performed regardless of the type                           rendering used    // determine what type of rendering is needed, this can be    // obtained from the user or by performing some other type    // of analysis, communicate this to other tasks through    // arguments    char *const argv4[] = {"TaskType4",...,NULL};    char *const argv5[] = {"TaskType5",...,NULL};    char *const argv6[] = {"TaskType6",...,NULL};    system("TaskType2 ...");    system("TaskType3 ...");    // initialize structures    posix_spawnattr_init(&Attr);    posix_spawn_file_actions_init(&FileActions);    posix_spawn(&Pid,"TaskType4",&FileActions,&Attr,argv4,               NULL);     posix_spawn(&Pid,"TaskType5",&FileActions,&Attr,argv5,                 NULL);    if(Y){             posix_spawn(&Pid,"TaskType6",&FileActions,&Attr,                        argv6,NULL);    }    // like a good parent, wait for all your children    wait(&stat);    wait(&stat);    wait(&stat);    return(0); }   // Each TaskType will be similar //... int main(int argc, char *argv[]) {     int Rt;     //...   if(argv[1] == X){      // initialize structures      //...      posix_spawn(&Pid,"TaskTypeX",&FileActions,&Attr,...,                 NULL);    }    else{           // initialize structures           //...           posix_spawn(&Pid,"TaskTypeY",&FileActions,&Attr,                       ...,NULL);    }    wait(&stat);    exit(0); } 

In Example 3.6, each task type will determine what processes need to be spawned based on the information passed to it from the parent or shell script.

3.10.1 Processes Along Function and Object Lines

Processes can be spawned from functions called from main() , as in Example 3.7.

Example 3.7 The mainline which calls the function.

 int main(int argc, char *argv[]) {     //...     Rt = func1(X, Y, Z);     //... } // This is the function definition int func1(char *M, char *N, char *V) {    //...    char *const args[] = {"TaskX",M,N,V,NULL};    Pid = fork();    if(Pid == 0)    {        exec("TaskX",args);    }    if(Pid > 0)    {        //...    }    wait(&stat); } 

In Example 3.7 func1() is called with three arguments. These arguments are passed to the spawned process.

Processes can also be spawned from methods that belong to objects. The objects can be declared in any process, as in Example 3.8.

Example 3.8 A process declaring an object.

 //... my_object MyObject; //... // Class declaration and definition class my_object { public:      //...     int spawnProcess(int X);     //... }; int my_object::spawnProcess(int X) {    //...    // posix_spawn() or system()    //... } 

In Example 3.8, the object can create any number of processes from whatever method necessary.