For a detailed description of the problem see The Dining philosophers problem on Wikipedia .
We implemented the model in the following way:
The forks are global variables, which can be locked, or unlocked with the VLOCK or the VUNLOCK Statements in StEAM. The philosophers are represented as a C++ class, whose task is to lock and unlock variables. The main method initializes the given number of philosophers as threads.
You can download the code as a .tar.gz file from here
You can also download the igcc compiled binary from here.
All experiments are conducted on AMD dual-processor Opteron machine with 4GB RAM, 4GB swap and a 3 Tera bytes hard disk made available through NFS.
To show the improvements in performance by using the externalization implemented in StEAM-XXL we have run the test cases with all three methods available in StEAM.
This graph describes the internal memory usage for finding the deadlock. For the experiments the most blocked heuristic was used. As we see, we were able to find a deadlock in an instance for 300 philosophers. This number can be increased by setting the capacity of the cache to a smaller number, trading space for time this way.
One might think that externalizing takes time. Not so with our algorithm. As we see in the next graph, the duration to find a deadlock is nearly the same in all three cases.
The graph shows that the time to find a deadlock is nearly the same in all three cases.
We present a graph, which shows us the expanded states for an instance of 150 philosophers. We choose 150 philosophers because this is the only instance solved by all the methods.
In all three cases the expansion rate remained linear. This implies that externalizing the states to disk does not slow down the performance of the search algorithm.
The last graph shown here will be the usage of internal memory while expanding the states.
In this graph we see that the memory usage for externalization is not only very low, but also remained nearly constant.
StEAM is able to find a deadlock in very large instances of the model. Also the algorithm for externalization does not slowdown the searching process, the experiments show that externalizing a software, does not mean trading time for space. If the algorithm fits well with the problem, it can be very effective.