Due date: Tuesday, December 7, 2004.

Ex. 1 Dependency Graph Problem
Download the following files:
gsemaphore.h
gsemaphore.cc
graph.h
graph.cc
main.cc
Makefile
graph.txt
The last file contains the graph in the example bellow.

In this homework we are going to simulate an application where the threads must execute their tasks based on a dependency graph. For example, if we have the following graph:

then the thread P3 must wait for the threads P1, P2, and P6 to finish their task to be able to start theirs. After P3 finishes it's task, it must signal the threads P5 and P7 that are waiting on it to begin their own tasks.

We'll be using a general semaphore for this problem. The semaphore is based on a variable that has non-negative values. The semaphore is manipulated by two functions, Test_and_inc which increments the value of the variable only when the value is equal to 0. The second function, Dec, decrements the value of the variable without testing it.

Each thread will have its own semaphore that is initialized with a value equal to the number of incoming edges for that vertex. The thread calls the Test_and_inc function before executing their task, then calls the function Dec for all the semaphores of the threads in its adjacency list (all the threads waiting for it). Thus, when all the threads on which a threads depends on have decreased it's semaphore, the value of the semaphore is 0 and the thread can start executing its task.

a. Implement the function Test_and_inc in the file gsemaphore.cc.

b. Implement the function Count_incoming in the graph class. For this function, you must count all the occurrences of a vertex in the adjacency list of any other vertex.

c. Complete the implementation of the function Thread. This function starts by counting the number of incoming edges for the vertex associated with the current thread and initializing the semaphore using that value. After calling the function Test_and_inc, it executes its task. You have to add after this, a loop in which the threads scans the adjacency list for the vertex and calls the function Dec for the semaphore of every vertex found in the list.