2.2 Multi-threaded Qu-Prolog

Our first major extension in the early 1990s was to make a Qu-Prolog process multi-threaded, with each thread having a different atom name evaluating a different Qu-Prolog query, but sharing and accessing the same static and dynamic relation definitions. The multi-threading was added to extend the interactive theorem proving application to allow the spawning a threads to construct proofs of straightforward lemmas whilst the main interactive theorem proving activity continued.

Co-ordination of the activity of the separate threads was initially achieved by atomic updates of the shared Belief Store of dynamic relation facts, with some threads waiting for an update by another thread.

We then added inter-thread communication via messages. Each thread had one linked message buffer into which messages sent to the thread were put. The messages were ordered by time of arrival with the most recent being the last message. The receiving thread periodically ’pattern match reads’ and optionally removes a message term from its message buffer using message read primitives. It could search the buffer looking for a message that matches a given pattern, or is from a specific thread, or both. If there was no message that satisfied the given constraints the reading thread suspended, with an optional timeout on the suspension, until a message satisfying the constraints was received

The threads were time-shared by a run-time scheduler with each thread being given a 2 millisecond evaluation slot. The slot of a thread Th is automatically extended to complete an atomic call sequence, say one that needs to do several updates to one or more dynamic relations. The slot is shortened if the Th thread suspends waiting for a particular message to arrive, or for one or more other threads to update the dynamic relations so that some suspended query succeeds.

When the application of the multi-threaded Qu-Prolog is an agent application, each thread is an agent sub-task and the dynamic relations defined solely by facts comprise the agent’s Belief Store. Task co-ordination is achieved either by inter-thread communication, or by atomic updates of the Belief Store, used as a shared blackboard.