Since getting and freeing nodes are two of the most frequently used operations, we cannot allow locking of global lists to prevent more than one process from simultaneously updating the lists. Therefore, each process maintains its own lists of available nodes. The nodes are in shared memory, however, and data built with those nodes are passed between various processes. The following problem arises. Suppose process Pa builds more than its share of clauses, and process Pb frees more than its share of clauses. Then Pa must keep allocating memory from the operating system, while Pb's lists of available nodes grow.
Our preliminary experiments with ROO showed that this was a severe problem when one of the processes spent most of its time executing Task B--when freeing clauses, that process would collect all of the nodes allocated by the other processes while building inferred clauses in Task A. Our solution is (1) to have Task A stamp all inferred clauses with the ID of the process executing Task A (with the ``owner'' of the clause); (2) to have Task B, rather than deallocate a clause, place it in an area accessible to the owner of the clause; and (3) to have a process reclaim and deallocate its clauses when it is convenient to do so (for example, at the beginning of Task A). If ROO applications arise in which memory balance is a problem when managing nodes used in the construction of indices, then the same technique can be used in there as well.
A second solution is to have each process monitor the sizes of its lists of available nodes and to have it give up any large lists to a global area. We have not experimented with the second solution.