starvation in pthread_once?

starvation in pthread_once?

[Gottlob Frege]

I'm concerned about the Sleep(0) in pthread_once:

  if (!once_control->done)
    {
      if (InterlockedIncrement (&(once_control->started)) == 0)
        {
          /*
           * First thread to increment the started variable
           */
          (*init_routine) ();
          once_control->done = PTW32_TRUE;

        }
      else
        {
          /*
           * Block until other thread finishes executing the onceRoutine
           */
          while (!(once_control->done))
            {
              /*
               * The following gives up CPU cycles without pausing
               * unnecessarily
               */
              Sleep (0);
            }
        }
    }

IIRC, Sleep(0) does not relinquish time slices to lower priority
threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
priority thread is first in, followed closely by a higher priority
one, the higher priority thread will spin on Sleep(0) *forever*
because the lower, first thread will never get a chance to set done.

So even Sleep(10) should be good enough.  In theory, there could be
enough higher priority threads in the system that the first thread
still doesn't get in (ever?!), but unlikely.  And that would probably
mean a general design flaw of the calling code, not pthread_once.

?

Re: starvation in pthread_once?

[Ross Johnson]

On Thu, 2005-03-03 at 04:32 -0500, Gottlob Frege wrote:
> I'm concerned about the Sleep(0) in pthread_once:
> 

Thanks. It looks like this routine needs to be redesigned.

Regards.
Ross

>   if (!once_control->done)
>     {
>       if (InterlockedIncrement (&(once_control->started)) == 0)
>         {
>           /*
>            * First thread to increment the started variable
>            */
>           (*init_routine) ();
>           once_control->done = PTW32_TRUE;
> 
>         }
>       else
>         {
>           /*
>            * Block until other thread finishes executing the onceRoutine
>            */
>           while (!(once_control->done))
>             {
>               /*
>                * The following gives up CPU cycles without pausing
>                * unnecessarily
>                */
>               Sleep (0);
>             }
>         }
>     }
> 
> IIRC, Sleep(0) does not relinquish time slices to lower priority
> threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
> priority thread is first in, followed closely by a higher priority
> one, the higher priority thread will spin on Sleep(0) *forever*
> because the lower, first thread will never get a chance to set done.
> 
> So even Sleep(10) should be good enough.  In theory, there could be
> enough higher priority threads in the system that the first thread
> still doesn't get in (ever?!), but unlikely.  And that would probably
> mean a general design flaw of the calling code, not pthread_once.
> 
> ?
> 

Re: starvation in pthread_once?

[Ross Johnson]

All,

I've redesigned pthread_once() and will shortly drop it into CVS and a
new snapshot. Please take a look over the code below and let me know of
any problems or improvements you find. The rationale is explained in the
comments.

This new version passes a new test I've added to the test suite that
exercises the routine much more intensively than previously (although it
doesn't play around with thread priorities yet).

Thanks.
Ross

  /*
   * Use a single global cond+mutex to manage access to all once_control objects.
   * Unlike a global mutex on it's own, the global cond+mutex allows faster
   * once_controls to overtake slower ones. Spurious wakeups can occur, but
   * can be tolerated.
   *
   * To maintain a separate mutex for each once_control object requires either
   * cleaning up the mutex (difficult to synchronise reliably), or leaving it
   * around forever. Since we can't make assumptions about how an application might
   * employ once_t objects, the later is considered to be unacceptable.
   *
   * Since this is being introduced as a bug fix, the global cond+mtx also avoids
   * a change in the ABI, maintaining backwards compatibility.
   *
   * The mutex should be an ERRORCHECK type to be sure we will never, in the event
   * we're cancelled before we get the lock, unlock the mutex when it's held by
   * another thread (possible with NORMAL/DEFAULT mutexes because they don't check
   * ownership).
   */

  if (!once_control->done)
    {
      if (InterlockedExchange((LPLONG) &once_control->started, (LONG) 0) == -1)
	{
	  (*init_routine) ();

	  /*
	   * Holding the mutex during the broadcast prevents threads being left
	   * behind waiting.
	   */
	  pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
	  (void) pthread_mutex_lock(&ptw32_once_control.mtx);
	  once_control->done = PTW32_TRUE;
	  (void) pthread_cond_broadcast(&ptw32_once_control.cond);
	  pthread_cleanup_pop(1);
	}
      else
	{
	  pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
	  (void) pthread_mutex_lock(&ptw32_once_control.mtx);
	  while (!once_control->done)
	    {
	      (void) pthread_cond_wait(&ptw32_once_control.cond, &ptw32_once_control.mtx);
	    }
	  pthread_cleanup_pop(1);
	}
    }


On Sat, 2005-03-05 at 10:18 +1100, Ross Johnson wrote:
> On Thu, 2005-03-03 at 04:32 -0500, Gottlob Frege wrote:
> > I'm concerned about the Sleep(0) in pthread_once:
> > 
> 
> Thanks. It looks like this routine needs to be redesigned.
> 
> Regards.
> Ross
> 
> >   if (!once_control->done)
> >     {
> >       if (InterlockedIncrement (&(once_control->started)) == 0)
> >         {
> >           /*
> >            * First thread to increment the started variable
> >            */
> >           (*init_routine) ();
> >           once_control->done = PTW32_TRUE;
> > 
> >         }
> >       else
> >         {
> >           /*
> >            * Block until other thread finishes executing the onceRoutine
> >            */
> >           while (!(once_control->done))
> >             {
> >               /*
> >                * The following gives up CPU cycles without pausing
> >                * unnecessarily
> >                */
> >               Sleep (0);
> >             }
> >         }
> >     }
> > 
> > IIRC, Sleep(0) does not relinquish time slices to lower priority
> > threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
> > priority thread is first in, followed closely by a higher priority
> > one, the higher priority thread will spin on Sleep(0) *forever*
> > because the lower, first thread will never get a chance to set done.
> > 
> > So even Sleep(10) should be good enough.  In theory, there could be
> > enough higher priority threads in the system that the first thread
> > still doesn't get in (ever?!), but unlikely.  And that would probably
> > mean a general design flaw of the calling code, not pthread_once.
> > 
> > ?
> > 

Re: starvation in pthread_once?

[Gottlob Frege]

I was thinking of something like this: (haven't compiled it yet or anything...)

	if (flag.initted)  // quick and easy check
	{
		return;
	}

	if (!AtomicExchange(&flag.entry, true)) // no one was in before us?
	{
		if (func)
		{
			func();
		}

		AtomicExchange(&initted, true);  // needs release type memory barrier

		// we didn't create the event.
		// it is only there if there is someone waiting
		if (AtomicRead(&flag.event))
		{
			SetEvent(flag.event);
		}
	}
	else
	{
		// wait for init.
		// while waiting, create an event to wait on

		AtomicIncrement(&flag.eventUsers); // mark that we have committed to
creating an event

		if (!AtomicRead(&flag.event))
		{
			tmpEvent = CreateEvent(true, false); // manual reset (ie will never be reset)
			if (AtomicCompareExchange(&flag.event, 0, tmpEvent) == 0)  //
release memory barrier
			{
				// wasn't set, is now
			}
			else
			{
				// someone snuck in
				// get rid of our attempt
				CloseHandle(tmpEvent);
			}
		}

		// check initted again in case the initting thread has finished
		// and left before seeing that there was an event to trigger.
		// (Now that the event IS created, if init gets finished AFTER this,
		//  then the event handle is guaranteed to be seen and triggered).
		//
		// Note also, that our first 'quick and easy' init check did NOT use
atomic read;
		// this atomic read here ensures that initted is properly seen by
the CPU cache.
		// And once seen as 'true' it will always stay true, so no need to
worry about the cache anymore.
		// (Thus the first 'quick and easy' check might 'falsely' fail, but
it gets corrected here.

		if (!AtomicRead(&flag.initted))  // needs acquire type memory barrier
		{
			WaitEvent(flag.event);   // acquire type memory barrier
		}

		// last one out shut off the lights:
		if (AtomicDecrement(&flag.eventUsers) == 0) // we were last
		{
			HANDLE tmpEvent = AtomicExchange(&flag.event, (HANDLE)-1);
			if (tmpEvent && tmpEvent != (HANDLE)-1);
			{
				CloseHandle(tmpEvent);
			}
		}
	}



On Tue, 08 Mar 2005 13:22:01 +1100, Ross Johnson
<ross.johnson@homemail.com.au> wrote:
> All,
> 
> I've redesigned pthread_once() and will shortly drop it into CVS and a
> new snapshot. Please take a look over the code below and let me know of
> any problems or improvements you find. The rationale is explained in the
> comments.
> 
> This new version passes a new test I've added to the test suite that
> exercises the routine much more intensively than previously (although it
> doesn't play around with thread priorities yet).
> 
> Thanks.
> Ross
> 
>  /*
>   * Use a single global cond+mutex to manage access to all once_control objects.
>   * Unlike a global mutex on it's own, the global cond+mutex allows faster
>   * once_controls to overtake slower ones. Spurious wakeups can occur, but
>   * can be tolerated.
>   *
>   * To maintain a separate mutex for each once_control object requires either
>   * cleaning up the mutex (difficult to synchronise reliably), or leaving it
>   * around forever. Since we can't make assumptions about how an application might
>   * employ once_t objects, the later is considered to be unacceptable.
>   *
>   * Since this is being introduced as a bug fix, the global cond+mtx also avoids
>   * a change in the ABI, maintaining backwards compatibility.
>   *
>   * The mutex should be an ERRORCHECK type to be sure we will never, in the event
>   * we're cancelled before we get the lock, unlock the mutex when it's held by
>   * another thread (possible with NORMAL/DEFAULT mutexes because they don't check
>   * ownership).
>   */
> 
>  if (!once_control->done)
>    {
>      if (InterlockedExchange((LPLONG) &once_control->started, (LONG) 0) == -1)
>        {
>          (*init_routine) ();
> 
>          /*
>           * Holding the mutex during the broadcast prevents threads being left
>           * behind waiting.
>           */
>          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
>          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
>          once_control->done = PTW32_TRUE;
>          (void) pthread_cond_broadcast(&ptw32_once_control.cond);
>          pthread_cleanup_pop(1);
>        }
>      else
>        {
>          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
>          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
>          while (!once_control->done)
>            {
>              (void) pthread_cond_wait(&ptw32_once_control.cond, &ptw32_once_control.mtx);
>            }
>          pthread_cleanup_pop(1);
>        }
>    }
> 
> On Sat, 2005-03-05 at 10:18 +1100, Ross Johnson wrote:
> > On Thu, 2005-03-03 at 04:32 -0500, Gottlob Frege wrote:
> > > I'm concerned about the Sleep(0) in pthread_once:
> > >
> >
> > Thanks. It looks like this routine needs to be redesigned.
> >
> > Regards.
> > Ross
> >
> > >   if (!once_control->done)
> > >     {
> > >       if (InterlockedIncrement (&(once_control->started)) == 0)
> > >         {
> > >           /*
> > >            * First thread to increment the started variable
> > >            */
> > >           (*init_routine) ();
> > >           once_control->done = PTW32_TRUE;
> > >
> > >         }
> > >       else
> > >         {
> > >           /*
> > >            * Block until other thread finishes executing the onceRoutine
> > >            */
> > >           while (!(once_control->done))
> > >             {
> > >               /*
> > >                * The following gives up CPU cycles without pausing
> > >                * unnecessarily
> > >                */
> > >               Sleep (0);
> > >             }
> > >         }
> > >     }
> > >
> > > IIRC, Sleep(0) does not relinquish time slices to lower priority
> > > threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
> > > priority thread is first in, followed closely by a higher priority
> > > one, the higher priority thread will spin on Sleep(0) *forever*
> > > because the lower, first thread will never get a chance to set done.
> > >
> > > So even Sleep(10) should be good enough.  In theory, there could be
> > > enough higher priority threads in the system that the first thread
> > > still doesn't get in (ever?!), but unlikely.  And that would probably
> > > mean a general design flaw of the calling code, not pthread_once.
> > >
> > > ?
> > >
> 
>

Re: starvation in pthread_once?

[Ross Johnson]

On Mon, 2005-03-07 at 22:00 -0500, Gottlob Frege wrote:
> I was thinking of something like this: (haven't compiled it yet or anything...)
> 

This is definitely the more interesting solution. A slight downside is
the ABI change (pthread_once_t and PTHREAD_ONCE_INIT). So this is what
I'd like to do:-

- because of the ABI change, I will put out a new snapshot today
containing the version I posted earlier (no ABI change and fixes the
starvation problem) plus the other bug fix (handle leak fix).

- after that, include the version below in CVS after testing it, ready
for the next snapshot, which will have a new dll name (pthreadVC2.dll
etc.) and compatibility version number.

- generate another [new] snapshot in a few days if no complications or
other issues arise in the meantime.

One other thing:- since pthread_once() is being redesigned, I'm also
looking at the latest SUS3 spec and trying to decide what the following
paragraph means for threads that are already waiting:-

"The pthread_once() function is not a cancelation point. However, if
init_routine is a cancelation point and is canceled, the effect on
once_control shall be as if pthread_once() was never called."

Should one or more waiting threads get woken up and made to re-compete
to run the init routine? That's the only sensible (maybe even obvious)
thing to do AFAIKS.

Ross

> 	if (flag.initted)  // quick and easy check
> 	{
> 		return;
> 	}
> 
> 	if (!AtomicExchange(&flag.entry, true)) // no one was in before us?
> 	{
> 		if (func)
> 		{
> 			func();
> 		}
> 
> 		AtomicExchange(&initted, true);  // needs release type memory barrier
> 
> 		// we didn't create the event.
> 		// it is only there if there is someone waiting
> 		if (AtomicRead(&flag.event))
> 		{
> 			SetEvent(flag.event);
> 		}
> 	}
> 	else
> 	{
> 		// wait for init.
> 		// while waiting, create an event to wait on
> 
> 		AtomicIncrement(&flag.eventUsers); // mark that we have committed to
> creating an event
> 
> 		if (!AtomicRead(&flag.event))
> 		{
> 			tmpEvent = CreateEvent(true, false); // manual reset (ie will never be reset)
> 			if (AtomicCompareExchange(&flag.event, 0, tmpEvent) == 0)  //
> release memory barrier
> 			{
> 				// wasn't set, is now
> 			}
> 			else
> 			{
> 				// someone snuck in
> 				// get rid of our attempt
> 				CloseHandle(tmpEvent);
> 			}
> 		}
> 
> 		// check initted again in case the initting thread has finished
> 		// and left before seeing that there was an event to trigger.
> 		// (Now that the event IS created, if init gets finished AFTER this,
> 		//  then the event handle is guaranteed to be seen and triggered).
> 		//
> 		// Note also, that our first 'quick and easy' init check did NOT use
> atomic read;
> 		// this atomic read here ensures that initted is properly seen by
> the CPU cache.
> 		// And once seen as 'true' it will always stay true, so no need to
> worry about the cache anymore.
> 		// (Thus the first 'quick and easy' check might 'falsely' fail, but
> it gets corrected here.
> 
> 		if (!AtomicRead(&flag.initted))  // needs acquire type memory barrier
> 		{
> 			WaitEvent(flag.event);   // acquire type memory barrier
> 		}
> 
> 		// last one out shut off the lights:
> 		if (AtomicDecrement(&flag.eventUsers) == 0) // we were last
> 		{
> 			HANDLE tmpEvent = AtomicExchange(&flag.event, (HANDLE)-1);
> 			if (tmpEvent && tmpEvent != (HANDLE)-1);
> 			{
> 				CloseHandle(tmpEvent);
> 			}
> 		}
> 	}
> 
> 
> 
> On Tue, 08 Mar 2005 13:22:01 +1100, Ross Johnson
> <ross.johnson@homemail.com.au> wrote:
> > All,
> > 
> > I've redesigned pthread_once() and will shortly drop it into CVS and a
> > new snapshot. Please take a look over the code below and let me know of
> > any problems or improvements you find. The rationale is explained in the
> > comments.
> > 
> > This new version passes a new test I've added to the test suite that
> > exercises the routine much more intensively than previously (although it
> > doesn't play around with thread priorities yet).
> > 
> > Thanks.
> > Ross
> > 
> >  /*
> >   * Use a single global cond+mutex to manage access to all once_control objects.
> >   * Unlike a global mutex on it's own, the global cond+mutex allows faster
> >   * once_controls to overtake slower ones. Spurious wakeups can occur, but
> >   * can be tolerated.
> >   *
> >   * To maintain a separate mutex for each once_control object requires either
> >   * cleaning up the mutex (difficult to synchronise reliably), or leaving it
> >   * around forever. Since we can't make assumptions about how an application might
> >   * employ once_t objects, the later is considered to be unacceptable.
> >   *
> >   * Since this is being introduced as a bug fix, the global cond+mtx also avoids
> >   * a change in the ABI, maintaining backwards compatibility.
> >   *
> >   * The mutex should be an ERRORCHECK type to be sure we will never, in the event
> >   * we're cancelled before we get the lock, unlock the mutex when it's held by
> >   * another thread (possible with NORMAL/DEFAULT mutexes because they don't check
> >   * ownership).
> >   */
> > 
> >  if (!once_control->done)
> >    {
> >      if (InterlockedExchange((LPLONG) &once_control->started, (LONG) 0) == -1)
> >        {
> >          (*init_routine) ();
> > 
> >          /*
> >           * Holding the mutex during the broadcast prevents threads being left
> >           * behind waiting.
> >           */
> >          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
> >          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
> >          once_control->done = PTW32_TRUE;
> >          (void) pthread_cond_broadcast(&ptw32_once_control.cond);
> >          pthread_cleanup_pop(1);
> >        }
> >      else
> >        {
> >          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
> >          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
> >          while (!once_control->done)
> >            {
> >              (void) pthread_cond_wait(&ptw32_once_control.cond, &ptw32_once_control.mtx);
> >            }
> >          pthread_cleanup_pop(1);
> >        }
> >    }
> > 
> > On Sat, 2005-03-05 at 10:18 +1100, Ross Johnson wrote:
> > > On Thu, 2005-03-03 at 04:32 -0500, Gottlob Frege wrote:
> > > > I'm concerned about the Sleep(0) in pthread_once:
> > > >
> > >
> > > Thanks. It looks like this routine needs to be redesigned.
> > >
> > > Regards.
> > > Ross
> > >
> > > >   if (!once_control->done)
> > > >     {
> > > >       if (InterlockedIncrement (&(once_control->started)) == 0)
> > > >         {
> > > >           /*
> > > >            * First thread to increment the started variable
> > > >            */
> > > >           (*init_routine) ();
> > > >           once_control->done = PTW32_TRUE;
> > > >
> > > >         }
> > > >       else
> > > >         {
> > > >           /*
> > > >            * Block until other thread finishes executing the onceRoutine
> > > >            */
> > > >           while (!(once_control->done))
> > > >             {
> > > >               /*
> > > >                * The following gives up CPU cycles without pausing
> > > >                * unnecessarily
> > > >                */
> > > >               Sleep (0);
> > > >             }
> > > >         }
> > > >     }
> > > >
> > > > IIRC, Sleep(0) does not relinquish time slices to lower priority
> > > > threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
> > > > priority thread is first in, followed closely by a higher priority
> > > > one, the higher priority thread will spin on Sleep(0) *forever*
> > > > because the lower, first thread will never get a chance to set done.
> > > >
> > > > So even Sleep(10) should be good enough.  In theory, there could be
> > > > enough higher priority threads in the system that the first thread
> > > > still doesn't get in (ever?!), but unlikely.  And that would probably
> > > > mean a general design flaw of the calling code, not pthread_once.
> > > >
> > > > ?
> > > >
> > 
> >
> 

Re: starvation in pthread_once?

[Alexander Terekhov]

[... pthread_once() and cancelation ...]

> Should one or more waiting threads get woken up and made to
> re-compete to run the init routine?

Yes. As for the rest, what you need here is DCSI-TLS or DCSI-MBR
(acquire/release memory barriers are needed on both Itanic and
XBOX NEXT... and, apart from hardware memory model, compiler
shall respect acquire/release semantics on IA-32 as well). For
serialization simply use a named mutex associated with address
of control variable and process id (to minimize contention).

DCSI-TLS: (__declspec(thread) for control variable; DLL issues
aside for a moment)

  if (!once_control) {
    named_mutex::guard guard(&once_control);
    if (!once_control) {
      <init>
      once_control = true;
    }
  }

DCSI-MBR: (atomic<> for control variable)

  if (!once_control.load(msync::acq)) {
    named_mutex::guard guard(&once_control);
    if (!once_control.load(msync::none)) {
      <init>
      once_control.store(true, msync::rel);
    }
  }

regards,
alexander.

Re: starvation in pthread_once?

[Alexander Terekhov]

> DCSI-TLS: (__declspec(thread) for control variable; DLL issues
> aside for a moment)
>
>   if (!once_control) {
>     named_mutex::guard guard(&once_control);
>     if (!once_control) {
>       <init>
>       once_control = true;
>     }
>   }

Sorry, I meant:

  if (!once_control) {
    named_mutex::guard guard(&once_control);
    if (!once_control2) {
      <init>
      once_control2 = true;
    }
    once_control = true;
  }

where once_control2 is a non-TLS flag.

regards,
alexander.

Re: starvation in pthread_once?

[Alexander Terekhov]

Grrr. Bad day.

  if (!once_control) {
    named_mutex::guard guard(&once_control2);
    if (!once_control2) {
      <init>
      once_control2 = true;
    }
    once_control = true;
  }

regards,
alexander.


Alexander Terekhov/Germany/IBM@IBMDE@sources.redhat.com on 03/08/2005
10:55:53 AM

Sent by:    pthreads-win32-owner@sources.redhat.com


To:    Ross Johnson <rpj@callisto.canberra.edu.au>
cc:    Pthreads-Win32 list <pthreads-win32@sources.redhat.com>
Subject:    Re: starvation in pthread_once?



> DCSI-TLS: (__declspec(thread) for control variable; DLL issues
> aside for a moment)
>
>   if (!once_control) {
>     named_mutex::guard guard(&once_control);
>     if (!once_control) {
>       <init>
>       once_control = true;
>     }
>   }

Sorry, I meant:

  if (!once_control) {
    named_mutex::guard guard(&once_control);
    if (!once_control2) {
      <init>
      once_control2 = true;
    }
    once_control = true;
  }

where once_control2 is a non-TLS flag.

regards,
alexander.

Re: starvation in pthread_once?

[Gottlob Frege]

Do you think it is worth avoiding the named_mutex in favor of a event
only created on contention (my version)? (I do, obviously).

I'm guessing that for typical usage, contention will be low.  And, in
my own code, I'm considering making statically initialized mutexes (or
CSes) by using a call_once in their constructor.  It would just seem
like overkill if all my mutexes needed a mutex to init themselves.


On Tue, 8 Mar 2005 10:58:23 +0100, Alexander Terekhov
<TEREKHOV@de.ibm.com> wrote:
> 
> Grrr. Bad day.
> 
>  if (!once_control) {
>    named_mutex::guard guard(&once_control2);
>    if (!once_control2) {
>      <init>
>      once_control2 = true;
>    }
>    once_control = true;
>  }
> 
> regards,
> alexander.
> 
> Alexander Terekhov/Germany/IBM@IBMDE@sources.redhat.com on 03/08/2005
> 10:55:53 AM
> 
> Sent by:    pthreads-win32-owner@sources.redhat.com
> 
> To:    Ross Johnson <rpj@callisto.canberra.edu.au>
> cc:    Pthreads-Win32 list <pthreads-win32@sources.redhat.com>
> Subject:    Re: starvation in pthread_once?
> 
> 
> > DCSI-TLS: (__declspec(thread) for control variable; DLL issues
> > aside for a moment)
> >
> >   if (!once_control) {
> >     named_mutex::guard guard(&once_control);
> >     if (!once_control) {
> >       <init>
> >       once_control = true;
> >     }
> >   }
> 
> Sorry, I meant:
> 
>  if (!once_control) {
>    named_mutex::guard guard(&once_control);
>    if (!once_control2) {
>      <init>
>      once_control2 = true;
>    }
>    once_control = true;
>  }
> 
> where once_control2 is a non-TLS flag.
> 
> regards,
> alexander.
> 
>

Re: starvation in pthread_once?

[Alexander Terekhov]

> It would just seem like overkill if all my mutexes needed a
> mutex to init themselves.

With CAS (InterlockedCompareExchange), you can use lockless
DCCI (not DCSI) on slow path to initialize event handle/ptr.

http://www.google.de/groups?selm=421F44B2.F931491D%40web.de

regards,
alexander.

Re: starvation in pthread_once?

[Gottlob Frege]

On Tue, 8 Mar 2005 18:14:22 +0100, Alexander Terekhov
<TEREKHOV@de.ibm.com> wrote:
> 
> > It would just seem like overkill if all my mutexes needed a
> > mutex to init themselves.
> 
> With CAS (InterlockedCompareExchange), you can use lockless
> DCCI (not DCSI) on slow path to initialize event handle/ptr.
> 
> http://www.google.de/groups?selm=421F44B2.F931491D%40web.de
> 
> regards,
> alexander.
> 

Yes, I remember that conversion.  I've improved my stuff because of it
no doubt.  But in those examples, the slow path was still taken by the
first thread (IIRC - it was because your lock starts out == 0 ie
contention.)  Whereas my version (above, in this thread) avoids the
event creation entirely if there is no contention while initting (ie
first one in does the init, but doesn't create event - only triggers the event
if it finds one there when initting is done).

I'd like to hear your opinion - yours in particular, actually (or
wrath - particularly wrath if necessary.  If there is a problem I need
someone to tell me - threading code is not reliable because of
testing, but because of peer review).

Re: starvation in pthread_once?

[Ross Johnson]

On Tue, 2005-03-08 at 11:11 -0500, Gottlob Frege wrote:
> Do you think it is worth avoiding the named_mutex in favor of a event
> only created on contention (my version)? (I do, obviously).
> 

I agree.

Win32 mutexes are VERY slow, even for uncontended lock operations - that
is, about 50 times slower than a CriticalSection. I would guess that a
named mutex is even slower again. A CS is about the same speed as an
interlocked operation if it doesn't block.

I also think that generating the [guaranteed unique] name is a
complication that should be avoided if possible.

News:
I've dropped a new version of pthread_once into CVS (bumping the
library's version from 1 to 2, and dll's name to indicate an ABI
change). It's based on the code that Gottlob posted earlier:-
http://sources.redhat.com/ml/pthreads-win32/2005/msg00029.html

This code works fine without cancellation, but with it included, the
design's efficiency had to be downgraded a little. Threads waiting on a
cancelled initter thread must be woken to compete again to run the
init_routine. I couldn't find any way to manage the repeated
creation/reuse/closure of the event properly without a global CS, but at
least these sections are very short where it matters most.

See:-
http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/pthread_once.c?
rev=1.10&content-type=text/x-cvsweb-markup&cvsroot=pthreads-win32

Crucially, the event is still a per once_control object that is released
on successful return from pthread_once.

I plan on releasing one more pthread*1.dll snapshot to include
init_routine cancellability based on the global cond+mutex used in the
last snapshot, then a pthread*2.dll snapshot using the above code. (DLL
names change only when their ABI compatibility is affected).

Thanks.
Ross

> I'm guessing that for typical usage, contention will be low.  And, in
> my own code, I'm considering making statically initialized mutexes (or
> CSes) by using a call_once in their constructor.  It would just seem
> like overkill if all my mutexes needed a mutex to init themselves.
> 
> 
> On Tue, 8 Mar 2005 10:58:23 +0100, Alexander Terekhov
> <TEREKHOV@de.ibm.com> wrote:
> > 
> > Grrr. Bad day.
> > 
> >  if (!once_control) {
> >    named_mutex::guard guard(&once_control2);
> >    if (!once_control2) {
> >      <init>
> >      once_control2 = true;
> >    }
> >    once_control = true;
> >  }
> > 
> > regards,
> > alexander.
> > 
> > Alexander Terekhov/Germany/IBM@IBMDE@sources.redhat.com on 03/08/2005
> > 10:55:53 AM
> > 
> > Sent by:    pthreads-win32-owner@sources.redhat.com
> > 
> > To:    Ross Johnson <rpj@callisto.canberra.edu.au>
> > cc:    Pthreads-Win32 list <pthreads-win32@sources.redhat.com>
> > Subject:    Re: starvation in pthread_once?
> > 
> > 
> > > DCSI-TLS: (__declspec(thread) for control variable; DLL issues
> > > aside for a moment)
> > >
> > >   if (!once_control) {
> > >     named_mutex::guard guard(&once_control);
> > >     if (!once_control) {
> > >       <init>
> > >       once_control = true;
> > >     }
> > >   }
> > 
> > Sorry, I meant:
> > 
> >  if (!once_control) {
> >    named_mutex::guard guard(&once_control);
> >    if (!once_control2) {
> >      <init>
> >      once_control2 = true;
> >    }
> >    once_control = true;
> >  }
> > 
> > where once_control2 is a non-TLS flag.
> > 
> > regards,
> > alexander.
> > 
> >
> 

Re: starvation in pthread_once?

[Gottlob Frege]

Blast from the past - whatever happened to changing call_once() to not
create the named mutex when it wasn't needed?


On Tue, Mar 22, 2005 at 1:26 PM, Gottlob Frege <gottlobfrege@gmail.com> wrote:
> If it comes down to it, I might vote for daisy-chaining over
> busy-looping (assuming the busy-looping is endless).  Remember, this
> all started because the original implementation was polling/sleeping
> on 'initted' - and if the busy-looping thread is high-priority, then
> we are locked forever...
>
>
> On Tue, 22 Mar 2005 15:14:07 +1100, Ross Johnson
> <rpj@callisto.canberra.edu.au> wrote:
>> On Mon, 2005-03-21 at 11:07 -0500, Gottlob Frege wrote:
>>
>> > So, it doesn't seem to be getting any easier!  *Almost* to the point
>> > where a big named mutex becomes tempting - there is a lot to be said
>> > for simplicity.  However, my/the goal is still to at least minimize
>> > the non-contention simple init case...
>>
>> I'm less and less tempted to use a named mutex. Perhaps there's a
>> standard technique, but AFAICS it's impossible to guarantee that the
>> name is unique across the system (and all Windows variants).
>>
>> And I agree, minimum overhead for the uncontended case is the top
>> priority (after correct behaviour). I'm not concerned at all about speed
>> in the cancellation case.
>>
>> > And the event is still an auto-reset, although I no longer think it
>> > really matters - I really haven't had the tenacity to think this stuff
>> > through.  If it doesn't matter, manual-reset would be better, I think
>> > - I don't like having 1 thread relying on another thread waking it up,
>> > - for cases where the thread is killed, or strange thread priorities,
>> > etc.
>>
>> It all looks to me like it will work. I don't recall, in the version
>> that's in pthreads-win32 now, why I included eventUsers (++/--) in what
>> you have as the __lock() sections. Maybe to save additional Atomic calls
>> (bus locks). But now I realise [in that version - not yours] that waking
>> threads can block unnecessarily when leaving the wait section.
>>
>> It probably doesn't matter if cancel_event is auto or manual. I think
>> there will be at most one thread waiting on it. And, for 'event', like
>> you I'm uncomfortable with daisy-chaining SetEvent() calls.
>>
>> The only problem with the alternative of using a manual-reset event is
>> that some thread/s may busy-loop for a bit until an explicit reset
>> occurs. It seems untidy, but it's probably more robust than daisy-
>> chained SetEvents given the issues you've identified above.
>>
>> So I'm tempted to leave both events as manual-reset events. I'm also
>> guessing that this busy-looping will be extremely rare - perhaps only
>> when a new thread sneaks in to become initter, then suspends just inside
>> while the first waiter is waking and heading back to the loop start.
>>
>> I'll run your design and let you know the results.
>>
>> Thanks.
>> Ross
>>
>>
>

Re: starvation in pthread_once?

[Ross Johnson]

Hi Gottlob,

Vladimir Kliatchko reimplemented pthread_once to use his 
implementation of MCS (Mellor-Crummey/Scott) locks.

 From ptw32_MCS_lock.c:-

 * About MCS locks:
 *
 * MCS locks are queue-based locks, where the queue nodes are local to the
 * thread. The 'lock' is nothing more than a global pointer that points to
 * the last node in the queue, or is NULL if the queue is empty.
 * 
 * Originally designed for use as spin locks requiring no kernel resources
 * for synchronisation or blocking, the implementation below has adapted
 * the MCS spin lock for use as a general mutex that will suspend threads
 * when there is lock contention.
 *
 * Because the queue nodes are thread-local, most of the memory read/write
 * operations required to add or remove nodes from the queue do not trigger
 * cache-coherence updates.
 *
 * Like 'named' mutexes, MCS locks consume system resources transiently -
 * they are able to acquire and free resources automatically - but MCS
 * locks do not require any unique 'name' to identify the lock to all
 * threads using it.



Gottlob Frege wrote:
> Blast from the past - whatever happened to changing call_once() to not
> create the named mutex when it wasn't needed?
>
>
> On Tue, Mar 22, 2005 at 1:26 PM, Gottlob Frege <gottlobfrege@gmail.com> wrote:
>   
>> If it comes down to it, I might vote for daisy-chaining over
>> busy-looping (assuming the busy-looping is endless).  Remember, this
>> all started because the original implementation was polling/sleeping
>> on 'initted' - and if the busy-looping thread is high-priority, then
>> we are locked forever...
>>
>>
>> On Tue, 22 Mar 2005 15:14:07 +1100, Ross Johnson
>> <rpj@callisto.canberra.edu.au> wrote:
>>     
>>> On Mon, 2005-03-21 at 11:07 -0500, Gottlob Frege wrote:
>>>
>>>       
>>>> So, it doesn't seem to be getting any easier!  *Almost* to the point
>>>> where a big named mutex becomes tempting - there is a lot to be said
>>>> for simplicity.  However, my/the goal is still to at least minimize
>>>> the non-contention simple init case...
>>>>         
>>> I'm less and less tempted to use a named mutex. Perhaps there's a
>>> standard technique, but AFAICS it's impossible to guarantee that the
>>> name is unique across the system (and all Windows variants).
>>>
>>> And I agree, minimum overhead for the uncontended case is the top
>>> priority (after correct behaviour). I'm not concerned at all about speed
>>> in the cancellation case.
>>>
>>>       
>>>> And the event is still an auto-reset, although I no longer think it
>>>> really matters - I really haven't had the tenacity to think this stuff
>>>> through.  If it doesn't matter, manual-reset would be better, I think
>>>> - I don't like having 1 thread relying on another thread waking it up,
>>>> - for cases where the thread is killed, or strange thread priorities,
>>>> etc.
>>>>         
>>> It all looks to me like it will work. I don't recall, in the version
>>> that's in pthreads-win32 now, why I included eventUsers (++/--) in what
>>> you have as the __lock() sections. Maybe to save additional Atomic calls
>>> (bus locks). But now I realise [in that version - not yours] that waking
>>> threads can block unnecessarily when leaving the wait section.
>>>
>>> It probably doesn't matter if cancel_event is auto or manual. I think
>>> there will be at most one thread waiting on it. And, for 'event', like
>>> you I'm uncomfortable with daisy-chaining SetEvent() calls.
>>>
>>> The only problem with the alternative of using a manual-reset event is
>>> that some thread/s may busy-loop for a bit until an explicit reset
>>> occurs. It seems untidy, but it's probably more robust than daisy-
>>> chained SetEvents given the issues you've identified above.
>>>
>>> So I'm tempted to leave both events as manual-reset events. I'm also
>>> guessing that this busy-looping will be extremely rare - perhaps only
>>> when a new thread sneaks in to become initter, then suspends just inside
>>> while the first waiter is waking and heading back to the loop start.
>>>
>>> I'll run your design and let you know the results.
>>>
>>> Thanks.
>>> Ross
>>>
>>>
>>>       

Re: starvation in pthread_once?

[Gottlob Frege]

By the way, I was thinking that the first flag.initted check didn't
need to be atomic because an inaccurate read of false isn't a problem
(it is not - it gets handled later).  But an out of order read of true
would mean that the data set by the init func() might not really be
visible yet.

So you need if (AtomicRead(flag.initted).

Or TLS like Alexander shows.  Under Windows, a __declspec(thread) is
pretty fast.


On Mon, 7 Mar 2005 22:00:14 -0500, Gottlob Frege <gottlobfrege@gmail.com> wrote:
> I was thinking of something like this: (haven't compiled it yet or anything...)
> 
>        if (flag.initted)  // quick and easy check
>        {
>                return;
>        }
> 
>        if (!AtomicExchange(&flag.entry, true)) // no one was in before us?
>        {
>                if (func)
>                {
>                        func();
>                }
> 
>                AtomicExchange(&initted, true);  // needs release type memory barrier
> 
>                // we didn't create the event.
>                // it is only there if there is someone waiting
>                if (AtomicRead(&flag.event))
>                {
>                        SetEvent(flag.event);
>                }
>        }
>        else
>        {
>                // wait for init.
>                // while waiting, create an event to wait on
> 
>                AtomicIncrement(&flag.eventUsers); // mark that we have committed to
> creating an event
> 
>                if (!AtomicRead(&flag.event))
>                {
>                        tmpEvent = CreateEvent(true, false); // manual reset (ie will never be reset)
>                        if (AtomicCompareExchange(&flag.event, 0, tmpEvent) == 0)  //
> release memory barrier
>                        {
>                                // wasn't set, is now
>                        }
>                        else
>                        {
>                                // someone snuck in
>                                // get rid of our attempt
>                                CloseHandle(tmpEvent);
>                        }
>                }
> 
>                // check initted again in case the initting thread has finished
>                // and left before seeing that there was an event to trigger.
>                // (Now that the event IS created, if init gets finished AFTER this,
>                //  then the event handle is guaranteed to be seen and triggered).
>                //
>                // Note also, that our first 'quick and easy' init check did NOT use
> atomic read;
>                // this atomic read here ensures that initted is properly seen by
> the CPU cache.
>                // And once seen as 'true' it will always stay true, so no need to
> worry about the cache anymore.
>                // (Thus the first 'quick and easy' check might 'falsely' fail, but
> it gets corrected here.
> 
>                if (!AtomicRead(&flag.initted))  // needs acquire type memory barrier
>                {
>                        WaitEvent(flag.event);   // acquire type memory barrier
>                }
> 
>                // last one out shut off the lights:
>                if (AtomicDecrement(&flag.eventUsers) == 0) // we were last
>                {
>                        HANDLE tmpEvent = AtomicExchange(&flag.event, (HANDLE)-1);
>                        if (tmpEvent && tmpEvent != (HANDLE)-1);
>                        {
>                                CloseHandle(tmpEvent);
>                        }
>                }
>        }
> 
> On Tue, 08 Mar 2005 13:22:01 +1100, Ross Johnson
> <ross.johnson@homemail.com.au> wrote:
> > All,
> >
> > I've redesigned pthread_once() and will shortly drop it into CVS and a
> > new snapshot. Please take a look over the code below and let me know of
> > any problems or improvements you find. The rationale is explained in the
> > comments.
> >
> > This new version passes a new test I've added to the test suite that
> > exercises the routine much more intensively than previously (although it
> > doesn't play around with thread priorities yet).
> >
> > Thanks.
> > Ross
> >
> >  /*
> >   * Use a single global cond+mutex to manage access to all once_control objects.
> >   * Unlike a global mutex on it's own, the global cond+mutex allows faster
> >   * once_controls to overtake slower ones. Spurious wakeups can occur, but
> >   * can be tolerated.
> >   *
> >   * To maintain a separate mutex for each once_control object requires either
> >   * cleaning up the mutex (difficult to synchronise reliably), or leaving it
> >   * around forever. Since we can't make assumptions about how an application might
> >   * employ once_t objects, the later is considered to be unacceptable.
> >   *
> >   * Since this is being introduced as a bug fix, the global cond+mtx also avoids
> >   * a change in the ABI, maintaining backwards compatibility.
> >   *
> >   * The mutex should be an ERRORCHECK type to be sure we will never, in the event
> >   * we're cancelled before we get the lock, unlock the mutex when it's held by
> >   * another thread (possible with NORMAL/DEFAULT mutexes because they don't check
> >   * ownership).
> >   */
> >
> >  if (!once_control->done)
> >    {
> >      if (InterlockedExchange((LPLONG) &once_control->started, (LONG) 0) == -1)
> >        {
> >          (*init_routine) ();
> >
> >          /*
> >           * Holding the mutex during the broadcast prevents threads being left
> >           * behind waiting.
> >           */
> >          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
> >          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
> >          once_control->done = PTW32_TRUE;
> >          (void) pthread_cond_broadcast(&ptw32_once_control.cond);
> >          pthread_cleanup_pop(1);
> >        }
> >      else
> >        {
> >          pthread_cleanup_push(pthread_mutex_unlock, (void *) &ptw32_once_control.mtx);
> >          (void) pthread_mutex_lock(&ptw32_once_control.mtx);
> >          while (!once_control->done)
> >            {
> >              (void) pthread_cond_wait(&ptw32_once_control.cond, &ptw32_once_control.mtx);
> >            }
> >          pthread_cleanup_pop(1);
> >        }
> >    }
> >
> > On Sat, 2005-03-05 at 10:18 +1100, Ross Johnson wrote:
> > > On Thu, 2005-03-03 at 04:32 -0500, Gottlob Frege wrote:
> > > > I'm concerned about the Sleep(0) in pthread_once:
> > > >
> > >
> > > Thanks. It looks like this routine needs to be redesigned.
> > >
> > > Regards.
> > > Ross
> > >
> > > >   if (!once_control->done)
> > > >     {
> > > >       if (InterlockedIncrement (&(once_control->started)) == 0)
> > > >         {
> > > >           /*
> > > >            * First thread to increment the started variable
> > > >            */
> > > >           (*init_routine) ();
> > > >           once_control->done = PTW32_TRUE;
> > > >
> > > >         }
> > > >       else
> > > >         {
> > > >           /*
> > > >            * Block until other thread finishes executing the onceRoutine
> > > >            */
> > > >           while (!(once_control->done))
> > > >             {
> > > >               /*
> > > >                * The following gives up CPU cycles without pausing
> > > >                * unnecessarily
> > > >                */
> > > >               Sleep (0);
> > > >             }
> > > >         }
> > > >     }
> > > >
> > > > IIRC, Sleep(0) does not relinquish time slices to lower priority
> > > > threads.  (Sleep(n) for n != 0 does, but 0 does not).  So, if a lower
> > > > priority thread is first in, followed closely by a higher priority
> > > > one, the higher priority thread will spin on Sleep(0) *forever*
> > > > because the lower, first thread will never get a chance to set done.
> > > >
> > > > So even Sleep(10) should be good enough.  In theory, there could be
> > > > enough higher priority threads in the system that the first thread
> > > > still doesn't get in (ever?!), but unlikely.  And that would probably
> > > > mean a general design flaw of the calling code, not pthread_once.
> > > >
> > > > ?
> > > >
> >
> >
>