Initialization

To run a program using Tabard the user only needs to include the Tabard library file and then start his program from init/0. An example of such program follows:

:- include('lib').

% Master
init:-
pm2_is_master,!,
system(hostname),
write_loop.

% Slaves
init:-
system(hostname),
read_loop.

read_loop:-
mutex_lock,
pl_thread_get_msg(Termo),
write(Termo), nl,
read_loop.

write_loop:-
pl_thread_send_msg(vid(3,0,_,_), a(gnu)),
pl_thread_send_msg(vid(2,0,_,_), b(software)),
pl_thread_send_msg(vid(1,0,_,_), c(is)),
write_loop.


Message-Queues: no read() before write() (mutex)

Since the SYS V message-queues were not longer being used and since I thought it would be better, everything related to clone(2) has been removed in favor of pthreads. That means Tabard works solely on top of pthreads, with a C thread listener and a Prolog thread on each node. That will make Tabard more portable and eventually work transparently when Linux switches from LinuxThreads to Native Posix Thread Library (NPTL) more elegant.

One thing that needs to be guaranteed in the message-queues is that no read() is made before write(). For that a pthread mutex is used in the following way:

1) mutex is inicializated and a lock is made.

2) Someone sends a message. The listener thread receives it, writes it to the message-queue and an unlock is made.

3) Since an unlock has been made, the Prolog thread will now acquire the lock and retrieve the message from the queue. Finally, a lock is made and we go back to step 1.

Threads in Linux

When we talk about threads in Linux we’re talking about one of two things:

1) LinuxThreads – an implementation of the Posix 1003.1c (discussion saying they aren’t really POSIX) thread package for Linux, now obsolete and being replaced by a library called NPTL (Native POSIX Thread Library). Unlike other implementations of Posix threads for Linux, LinuxThreads provides kernel-level threads: threads are created with the new clone() system call and all scheduling is done in the kernel. The main strength of this approach is that it can take full advantage of multiprocessors. It also results in a simpler, more robust thread library, especially w.r.t. blocking system calls.

2) Native POSIX Thread Library (NPTL)

• Threads use and exist within these process resources, yet are able to be scheduled by the operating system and run as independent entities largely because they duplicate only the bare essential resources that enable them to exist as executable code.
• This independent flow of control is accomplished because a thread maintains its own:

  * Stack pointer
  * Registers
  * Scheduling properties (such as policy or priority)
  * Set of pending and blocked signals
  * Thread specific data.

• So, in summary, in the UNIX environment a thread:

  * Exists within a process and uses the process resources
  * Has its own independent flow of control as long as its parent process exists and the OS supports it
  * Duplicates only the essential resources it needs to be independently schedulable
  * May share the process resources with other threads that act equally independently (and dependently)
  * Dies if the parent process dies – or something similar
  * Is “lightweight” because most of the overhead has already been accomplished through the creation of its process.

• Because threads within the same process share resources:

  * Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads.
  * Two pointers having the same value point to the same data.
  * Reading and writing to the same memory locations is possible, and therefore requires explicit synchronization by the programmer.

GNU Prolog and POSIX Threads

I was trying to play with gprolog+pthreads to run multiple Prolog engines. As Daniel Diaz explains, it doesn’t seem possible:

“The functions Start_Prolog() and Stop_Prolog() shoud be called only once since Stop_Prolog does not free allocated stacks (will be done in a next version). Try to use Reset_Prolog() (which reset all Prolog stacks, but NOT dynamic predicates (thus asserted clauses remain after a Reset_Prolog).”

Joseph Benden also explains:

“This is what I am doing with success:

On Linux: I am using multiple process (a preforking) server, and after the accept and fork, then call Start_Prolog.

On Windows: I have the GNU Prolog wrapped into a DLL. On the DLL_PROCESS_ATATCH I call Start_Prolog. Then each thread waits on a master critical section before calling any prolog routines (inside the dll, on each call).

I do not believe GNU Prolog is thread-safe because it uses global memory space for its’ stacks. If you only ever read the memory, you should be safe, but writing is a different story. One could put mutex locks in the term reading and writing functions. But that would be a big project, and would slow the prolog down. GNU Prolog would have to use thread-local stacks, but that would require a re-write of the entire prolog, and would make multiple thread unable to access other threads stacks.

To get the same performance under windows as linux, load multiple instances of the DLL and marshal into them. “

The pthread library gets us two things (essentially) – a function to create threads, which you could pretty easily replace with clone(), and other functions to handle mutexes and conditions. If you replace pthread_create with clone you have a lot of work to do to implement the locking stuff… Of
course, if you’re willing to do this work, then more power to you.

Dining Philosophers Problem

Update: I have made available my Prolog implementation as this URL.

It’s time to start testing with real problems. The dining philosophers is a classic problem for this kind of testing since it involves thread/process concurrency and synchronization. It’s all around in the literature.

So, I’m now looking for a clean and elegant Prolog implementation of a solution to the dining philosophers problem. I’ve searched the web for something meaningful but since I wasn’t able to find anything in Prolog I’ve rolled out my own implementation.

There are several solutions proposed to solve the dining philosophers. The easiest one I found consisted of having each chopstick be a monitor (mutex), and each philosopher will attempt to pick up the chopstick on his left first, then right, then eat, then put down the right one, and then put down the left one.

This is prone to deadlock, although on this system you really won’t ever see it because of the granularity of timeslicing between threads. The only time that this solution is a problem is if a philosopher’s thread gets preempted between picking up the first and the second mutex. That doesn’t really ever happen here, so it looks like it works just fine.

I’ve tested with SWI-Prolog 5.2.13 multi-threaded.

Ditching SYS V Message Queues

The one-thread-per-VP prototype is basically finished. I’ve used one message-queue by thread and the PID to access it. I didn’t use any mutual exclusion mechanisms yet but I’ll probably need them if we decide to go this way because msgget(2) man page says there is currently no intrinsic way for a process to ensure exclusive access to a message queue.

Suggested improvements include the use of a shared-memory structure instead of the SYS V message queues. This will definitely include the use of user-level mutexes or SYS V semaphores and will be a lot simplier too. I’ve created a svn branch where I’ll ditch the use of them in favor of my own queues.

Plans to expand the cluster are in the way. I have to look for fun problems to use in testing.

Message Queue to communicate between processes in different machines

I was thinking about either it was possible to use a single SYS V message queue to communicate between processes that reside in different machines in a scenario where the queue (the ftok()’s file) resides in a NFS shared location. Message queues where made to use in local IPC but since all the machines have access to it on the filesystem it would make some sense if they could use it. According to my tests it is not possible. Although the file resides in a NFS shared location, remember that as far as you can tell there is no usable message queue on the other machines. Note: could we use a shared file to communicate?

Thread Communication

The API will be based on the existing SWI-Prolog’s Thread communication API, that uses message queues. This will allow communication between any two threads.

Local Communication (Two threads that reside on the same processing node)

Prolog threads can exchange data using dynamic predicates, database records, and other globally shared data. These provide no suitable means to wait for data or a condition as they can only be checked in an expensive polling loop. Message queues provide a means for threads to wait for data or conditions without using the CPU.

Each thread has a message-queue attached to it that is identified by the thread. Additional queues are created using message_queue_create/1.

Remote Communication (Two threads that reside on different processing nodes)

If one thread reside on node X and the second in node Y then:
- send msg to node Y via Madeleine.
- thread listener on node Y will proxy message to thread message queue.

I’ll be mainly using SYS V IPC, more precisely message queues and eventually semaphores.

Explicit message queues are designed with the worker-pool model in mind, where multiple threads wait on a single queue and pick up the first goal to execute. I don’t know if the user will need to protect the queue against concurrent access (two or more threads reading from the queue at the same time) or if the SYS V message queues will take care of that.

If it will involve protecting the queues, then the handling of user-level mutexes or semaphores might get handy. A mutex is a MUTual EXclusive device and the difference between a mutex and a semaphore (as my good friend Pedro told me) is that a mutex is only for mutual exclusion and semaphores can be used for more complicated stuff. For example, with a mutex protecting a resource, only one process at a time can access it. With semaphores (depending on the implementation, of course), you can have two, or three, or as much processes as you like accessing the resource at a time.

Clarify the notion of a node

Since PM2 adheres to the SPMD (Single Program Multiple Data) model, the user can write a single program text, a copy of which is launched by a specific load command on each processing node of the current configuration.

The nodes we are considering here are virtual: they only refer to Unix processes located on physical nodes. It looks like common sense pratice to exactly use one virtual node per physical node, so that the two notions just identify together. But nothing in PM2 requires such an identification. PM2 virtual nodes may be located at any physical nodes. The precise association is made by the pm2conf command. For instance, with this command we say 3 machines with 2 Unix processes (processing nodes) in each one:

$ pm2conf kx1 kx1 kx2 kx2 kx3 kx3


Notice this is especially fun because we can say the number of Unix processes we want by repeating the hostname. Since I’m using one Prolog thread per processing node, with Tabard I can also create more Prolog threads by invoking more than one node in each machine. Fun!

Kill threads

A running thread is identified by three things:
1) the cluster node in which the thread is running (abbrev. VP),
2) a local identifier which tells inside the node which thread we’re talking about (abbrev. ThreadId or Tid)
3) it’s PID.

Information about running threads is kept on the master node. This information consists on an array with the same size as the cluster configuration size (or number of cluster nodes) like this:

To kill a thread :

thread_kill(vid(VP, Tid)) calls pm2_thread_kill(VP, Tid)

pm2_thread_kill() looks at the array of running threads to get the PID and then signals the remote node if it’s a remote VP or kills the thread locally if it’s a local thread.