Synchronization

[Prime95]

The new multi-threaded carry code must make sure that blocks are processed in order. Before entering the carry code each thread calls a routine that does this:

/* Wait until the next normalization block to process is the block */
/* that this thread is working on. */

        for ( ; ; ) {
                gwmutex_lock (&gwdata->thread_lock);
                if (gwdata->pass1_norm_block == asm_data->this_block) break;
                gwmutex_unlock (&gwdata->thread_lock);
                gwevent_wait (&gwdata->pass1_norm_event, 0);
        }

/* We're entering the normalization code.  Reset pass1_norm_event so */
/* that other threads wait for us to finish with the normalization code */
/* before they can continnue */

        gwevent_reset (&gwdata->pass1_norm_event);
        gwmutex_unlock (&gwdata->thread_lock);

The mutex ensures only one thread at a time accesses the common data structure. The gwevent_wait uses Windows manual reset events. I'm fairly certain there is a Linux pthreads equivalent.

The above makes sure that only the thread processing pass1_norm_block enters the carry code. When the thread is done with the carry code it bumps pass1_norm_block and signals the pass1_norm_event.

Here is my worry: Suppose we'll do block 2 next (pass1_norm_block is 2) and the threads processing blocks 2 and 3 are waiting to enter the carry code (this_block = 2 and 3). The thread processing block 1 finishes and signals the event. The OS happens to be running some other jobs and has only one CPU for prime95 right now. The OS randomly decides to schedule the this_block = 3 thread. The thread sees it's not time for it to enter the carry code and waits again. The event however is still in the signalled state and the OS could keep the this_block = 3 thread running in a CPU bound loop. The CPU bound loop ends only when the OS happens to schedule the this_block = 2 thread.

Synchronization programming has always given me a headache. Is there a better way to implement this? Will the OS (Windows, Linux, FreeBSD, etc.) guarantee that it won't go into a cpu bound loop above?

[retina]

Originally Posted by Prime95

Here is my worry: Suppose we'll do block 2 next (pass1_norm_block is 2) and the threads processing blocks 2 and 3 are waiting to enter the carry code (this_block = 2 and 3). The thread processing block 1 finishes and signals the event. The OS happens to be running some other jobs and has only one CPU for prime95 right now. The OS randomly decides to schedule the this_block = 3 thread. The thread sees it's not time for it to enter the carry code and waits again. The event however is still in the signalled state and the OS could keep the this_block = 3 thread running in a CPU bound loop. The CPU bound loop ends only when the OS happens to schedule the this_block = 2 thread.

Synchronization programming has always given me a headache. Is there a better way to implement this? Will the OS (Windows, Linux, FreeBSD, etc.) guarantee that it won't go into a cpu bound loop above?

In my experience with locks (under win32 only) if a thread locks a mutex (or critical section) - checks something - then unocks and sleeps, I found that the scheduler will try to find another thread in the same process to run during the allocated time slice. I suspect this would solve the particular worry you show above. Hoever I don't know how LINUX (or other OSes) do their thing in this case.

PS: I think you are using only one process. If that is so then using a mutex under win32 is a little less efficient than a critical section lock.

[Prime95]

Thanks retina. I've reimplemented the gwmutex_* routines with critical sections. I added a Sleep (0) to the wait loop, though I'm hoping someone comes up with a superior solution. In Linux, the sleep(0) is not guaranteed to yield to other waiting threads, though it seems the current kernel does.

[ColdFury]

I've reimplemented the gwmutex_* routines with critical sections

Instead of rolling your own synchronization primitives, just use pthreads. Its available on both Win32 and Linux, and they have solved all this stuff already.

http://sourceware.org/pthreads-win32/

[retina]

In Win32 there is always the fiber (CreateFiber) option also. More cumbersome, but it makes it possible to fully control the execution of threads as you please. Although, once again, LINUX may not support it.

[ColdFury]

Although, once again, LINUX may not support it.

Its a Win32 API, so definitely not.

Using pthreads is really the best solution. You get automatic portability and its very efficient. You don't have to worry about busy-waiting because the implementation will handle locks in the most efficient way for the platform. For instance, on Linux, pthreads uses the futex system call to provide very fast locks.

In fact, user-level mutexes never should have to busy-wait at all, and the kernel should make sure of this, provided the mutex is implemented correctly.