PTHREADS-WIN32
==============

Pthreads-win32 is free software, distributed under the GNU Lesser
General Public License (LGPL). See the file 'COPYING.LIB' for terms
and conditions. Also see the file 'COPYING' for information
specific to pthreads-win32, copyrights and the LGPL.


What is it?
-----------

Pthreads-win32 is an Open Source Software implementation of the
Threads component of the POSIX 1003.1c 1995 Standard (or later)
for Microsoft's Win32 environment. Some functions from POSIX
1003.1b are also supported including semaphores. Other related
functions include the set of read-write lock functions. The
library also supports some of the functionality of the Open
Group's Single Unix specification, version 2, namely mutex types,
plus some common and pthreads-win32 specific non-portable
routines (see README.NONPORTABLE).

See the file "ANNOUNCE" for more information including standards
conformance details and the list of supported and unsupported
routines.


Prerequisites
-------------
MSVC or GNU C (MinGW32 MSys development kit)
	To build from source.

QueueUserAPCEx by Panagiotis E. Hadjidoukas
	To support any thread cancelation in C++ library builds or
	to support cancelation of blocked threads in any build.
	This library is not required otherwise.

	For true async cancelation of threads (including blocked threads).
	This is a DLL and Windows driver that provides pre-emptive APC
	by forcing threads into an alertable state when the APC is queued.
	Both the DLL and driver are provided with the pthreads-win32.exe
	self-unpacking ZIP, and on the pthreads-win32 FTP site  (in source
	and pre-built forms). Currently this is a separate LGPL package to
	pthreads-win32. See the README in the QueueUserAPCEx folder for
	installation instructions.

	Pthreads-win32 will automatically detect if the QueueUserAPCEx DLL
	QuserEx.DLL is available and whether the driver AlertDrv.sys is
	loaded. If it is not available, pthreads-win32 will simulate async
	cancelation, which means that it can async cancel only threads that
	are runnable. The simulated async cancellation cannot cancel blocked
	threads.

        [FOR SECURITY] To be found Quserex.dll MUST be installed in the
	Windows System Folder. This is not an unreasonable constraint given a
	driver must also be installed and loaded at system startup.


Library naming
--------------

Because the library is being built using various exception
handling schemes and compilers - and because the library
may not work reliably if these are mixed in an application,
each different version of the library has it's own name.

Note 1: the incompatibility is really between EH implementations
of the different compilers. It should be possible to use the
standard C version from either compiler with C++ applications
built with a different compiler. If you use an EH version of
the library, then you must use the same compiler for the
application. This is another complication and dependency that
can be avoided by using only the standard C library version.

Note 2: if you use a standard C pthread*.dll with a C++
application, then any functions that you define that are
intended to be called via pthread_cleanup_push() must be
__cdecl.

Note 3: the intention was to also name either the VC or GC
version (it should be arbitrary) as pthread.dll, including
pthread.lib and libpthread.a as appropriate. This is no longer
likely to happen.

Note 4: the compatibility number was added so that applications
can differentiate between binary incompatible versions of the
libs and dlls.

In general:
	pthread[VG]{SE,CE,C}[c].dll
	pthread[VG]{SE,CE,C}[c].lib

where:
	[VG] indicates the compiler
	V	- MS VC, or
	G	- GNU C

	{SE,CE,C} indicates the exception handling scheme
	SE	- Structured EH, or
	CE	- C++ EH, or
	C	- no exceptions - uses setjmp/longjmp

	c	- DLL compatibility number indicating ABI and API
		  compatibility with applications built against
		  a snapshot with the same compatibility number.
		  See 'Version numbering' below.

The name may also be suffixed by a 'd' to indicate a debugging version
of the library. E.g. pthreadVC2d.lib. Debugging versions contain
additional information for debugging (symbols etc) and are often not
optimised in any way (compiled with optimisation turned off).

Examples:
	pthreadVSE.dll	(MSVC/SEH)
	pthreadGCE.dll	(GNUC/C++ EH)
	pthreadGC.dll	(GNUC/not dependent on exceptions)
	pthreadVC1.dll	(MSVC/not dependent on exceptions - not binary
			compatible with pthreadVC.dll)
	pthreadVC2.dll	(MSVC/not dependent on exceptions - not binary
			compatible with pthreadVC1.dll or pthreadVC.dll)

The GNU library archive file names have correspondingly changed to:

	libpthreadGCEc.a
	libpthreadGCc.a


Versioning numbering
--------------------

Version numbering is separate from the snapshot dating system, and
is the canonical version identification system embedded within the
DLL using the Microsoft version resource system. The versioning
system chosen follows the GNU Libtool system. See
http://www.gnu.org/software/libtool/manual.html section 6.2.

See the resource file 'version.rc'.

Microsoft version numbers use 4 integers:

	0.0.0.0

Pthreads-win32 uses the first 3 following the Libtool convention.
The fourth is commonly used for the build number, but will be reserved
for future use.

	current.revision.age.0

The numbers are changed as follows:

1. If the library source code has changed at all since the last update,
   then increment revision (`c:r:a' becomes `c:r+1:a').
2. If any interfaces have been added, removed, or changed since the last
   update, increment current, and set revision to 0.
3. If any interfaces have been added since the last public release, then
   increment age.
4. If any interfaces have been removed or changed since the last public
   release, then set age to 0.


DLL compatibility numbering is an attempt to ensure that applications
always load a compatible pthreads-win32 DLL by using a DLL naming system
that is consistent with the version numbering system. It also allows
older and newer DLLs to coexist in the same filesystem so that older
applications can continue to be used. For pre .NET Windows systems,
this inevitably requires incompatible versions of the same DLLs to have
different names.

Pthreads-win32 has adopted the Cygwin convention of appending a single
integer number to the DLL name. The number used is based on the library
version number and is computed as 'current' - 'age'.

(See http://home.att.net/~perlspinr/libversioning.html for a nicely
detailed explanation.)

Using this method, DLL name/s will only change when the DLL's
backwards compatibility changes. Note that the addition of new
'interfaces' will not of itself change the DLL's compatibility for older
applications.


Which of the several dll versions to use?
-----------------------------------------
or,
---
What are all these pthread*.dll and pthread*.lib files?
-------------------------------------------------------

Simple, use either pthreadGCv.* if you use GCC, or pthreadVCv.* if you
use MSVC - where 'v' is the DLL versioning (compatibility) number.

Otherwise, you need to choose carefully and know WHY.

The most important choice you need to make is whether to use a
version that uses exceptions internally, or not. There are versions
of the library that use exceptions as part of the thread
cancelation and exit implementation. The default version uses
setjmp/longjmp.

There is some contension amongst POSIX threads experts as
to how POSIX threads cancelation and exit should work
with languages that use exceptions, e.g. C++ and even C
(Microsoft's Structured Exceptions).

The issue is: should cancelation of a thread in, say,
a C++ application cause object destructors and C++ exception
handlers to be invoked as the stack unwinds during thread
exit, or not?

There seems to be more opinion in favour of using the
standard C version of the library (no EH) with C++ applications
for the reason that this appears to be the assumption commercial
pthreads implementations make. Therefore, if you use an EH version
of pthreads-win32 then you may be under the illusion that
your application will be portable, when in fact it is likely to
behave differently when linked with other pthreads libraries.

Now you may be asking: then why have you kept the EH versions of
the library?

There are a couple of reasons:
- there is division amongst the experts and so the code may
  be needed in the future. Yes, it's in the repository and we
  can get it out anytime in the future, but it would be difficult
  to find.
- pthreads-win32 is one of the few implementations, and possibly
  the only freely available one, that has EH versions. It may be
  useful to people who want to play with or study application
  behaviour under these conditions.

Notes:

[If you use either pthreadVCE or pthreadGCE]

1. [See also the discussion in the FAQ file - Q2, Q4, and Q5]

If your application contains catch(...) blocks in your POSIX
threads then you will need to replace the "catch(...)" with the macro
"PtW32Catch", eg.

	#ifdef PtW32Catch
		PtW32Catch {
			...
		}
	#else
		catch(...) {
			...
		}
	#endif

Otherwise neither pthreads cancelation nor pthread_exit() will work
reliably when using versions of the library that use C++ exceptions
for cancelation and thread exit.

This is due to what is believed to be a C++ compliance error in VC++
whereby you may not have multiple handlers for the same exception in
the same try/catch block. GNU G++ doesn't have this restriction.


Other name changes
------------------

All snapshots prior to and including snapshot 2000-08-13
used "_pthread_" as the prefix to library internal
functions, and "_PTHREAD_" to many library internal
macros. These have now been changed to "ptw32_" and "PTW32_"
respectively so as to not conflict with the ANSI standard's
reservation of identifiers beginning with "_" and "__" for
use by compiler implementations only.

If you have written any applications and you are linking
statically with the pthreads-win32 library then you may have
included a call to _pthread_processInitialize. You will
now have to change that to ptw32_processInitialize.


Cleanup code default style
--------------------------

Previously, if not defined, the cleanup style was determined automatically
from the compiler used, and one of the following was defined accordingly:

	__CLEANUP_SEH	MSVC only
	__CLEANUP_CXX	C++, including MSVC++, GNU G++
	__CLEANUP_C	C, including GNU GCC, not MSVC

These defines determine the style of cleanup (see pthread.h) and,
most importantly, the way that cancelation and thread exit (via
pthread_exit) is performed (see the routine ptw32_throw()).

In short, the exceptions versions of the library throw an exception
when a thread is canceled, or exits via pthread_exit(). This exception is
caught by a handler in the thread startup routine, so that the
the correct stack unwinding occurs regardless of where the thread
is when it's canceled or exits via pthread_exit().

In this snapshot, unless the build explicitly defines (e.g. via a
compiler option) __CLEANUP_SEH, __CLEANUP_CXX, or __CLEANUP_C, then
the build NOW always defaults to __CLEANUP_C style cleanup. This style
uses setjmp/longjmp in the cancelation and pthread_exit implementations,
and therefore won't do stack unwinding even when linked to applications
that have it (e.g. C++ apps). This is for consistency with most/all
commercial Unix POSIX threads implementations.

Although it was not clearly documented before, it is still necessary to
build your application using the same __CLEANUP_* define as was
used for the version of the library that you link with, so that the
correct parts of pthread.h are included. That is, the possible
defines require the following library versions:

	__CLEANUP_SEH	pthreadVSE.dll
	__CLEANUP_CXX	pthreadVCE.dll or pthreadGCE.dll
	__CLEANUP_C	pthreadVC.dll or pthreadGC.dll

It is recommended that you let pthread.h use it's default __CLEANUP_C
for both library and application builds. That is, don't define any of
the above, and then link with pthreadVC.lib (MSVC or MSVC++) and
libpthreadGC.a (MinGW GCC or G++). The reason is explained below, but
another reason is that the prebuilt pthreadVCE.dll is currently broken.
Versions built with MSVC++ later than version 6 may not be broken, but I
can't verify this yet.

WHY ARE WE MAKING THE DEFAULT STYLE LESS EXCEPTION-FRIENDLY?
Because no commercial Unix POSIX threads implementation allows you to
choose to have stack unwinding. Therefore, providing it in pthread-win32
as a default is dangerous. We still provide the choice but unless
you consciously choose to do otherwise, your pthreads applications will
now run or crash in similar ways irrespective of the pthreads platform
you use. Or at least this is the hope.


Building under VC++ using C++ EH, Structured EH, or just C
----------------------------------------------------------

From the source directory run nmake without any arguments to list
help information. E.g.

$ nmake

Microsoft (R) Program Maintenance Utility   Version 6.00.8168.0
Copyright (C) Microsoft Corp 1988-1998. All rights reserved.

Run one of the following command lines:
nmake clean VCE (to build the MSVC dll with C++ exception handling)
nmake clean VSE (to build the MSVC dll with structured exception handling)
nmake clean VC (to build the MSVC dll with C cleanup code)
nmake clean VCE-inlined (to build the MSVC inlined dll with C++ exception handling)
nmake clean VSE-inlined (to build the MSVC inlined dll with structured exception handling)
nmake clean VC-inlined (to build the MSVC inlined dll with C cleanup code)
nmake clean VC-static (to build the MSVC static lib with C cleanup code)
nmake clean VCE-debug (to build the debug MSVC dll with C++ exception handling)
nmake clean VSE-debug (to build the debug MSVC dll with structured exception handling)
nmake clean VC-debug (to build the debug MSVC dll with C cleanup code)
nmake clean VCE-inlined-debug (to build the debug MSVC inlined dll with C++ exception handling)
nmake clean VSE-inlined-debug (to build the debug MSVC inlined dll with structured exception handling)
nmake clean VC-inlined-debug (to build the debug MSVC inlined dll with C cleanup code)
nmake clean VC-static-debug (to build the debug MSVC static lib with C cleanup code)


The pre-built dlls are normally built using the *-inlined targets.

You can run the testsuite by changing to the "tests" directory and
running nmake. E.g.:

$ cd tests
$ nmake

Microsoft (R) Program Maintenance Utility   Version 6.00.8168.0
Copyright (C) Microsoft Corp 1988-1998. All rights reserved.

Run one of the following command lines:
nmake clean VC (to test using VC dll with VC (no EH) applications)
nmake clean VCX (to test using VC dll with VC++ (EH) applications)
nmake clean VCE (to test using the VCE dll with VC++ EH applications)
nmake clean VSE (to test using VSE dll with VC (SEH) applications)
nmake clean VC-bench (to benchtest using VC dll with C bench app)
nmake clean VCX-bench (to benchtest using VC dll with C++ bench app)
nmake clean VCE-bench (to benchtest using VCE dll with C++ bench app)
nmake clean VSE-bench (to benchtest using VSE dll with SEH bench app)
nmake clean VC-static (to test using VC static lib with VC (no EH) applications)


Building under Mingw32
----------------------

The dll can be built easily with recent versions of Mingw32.
(The distributed versions are built using Mingw32 and MsysDTK
from www.mingw32.org.)

From the source directory, run make for help information. E.g.:

$ make
Run one of the following command lines:
make clean GC            (to build the GNU C dll with C cleanup code)
make clean GCE           (to build the GNU C dll with C++ exception handling)
make clean GC-inlined    (to build the GNU C inlined dll with C cleanup code)
make clean GCE-inlined   (to build the GNU C inlined dll with C++ exception handling)
make clean GC-static     (to build the GNU C inlined static lib with C cleanup code)
make clean GC-debug      (to build the GNU C debug dll with C cleanup code)
make clean GCE-debug     (to build the GNU C debug dll with C++ exception handling)
make clean GC-inlined-debug    (to build the GNU C inlined debug dll with C cleanup code)
make clean GCE-inlined-debug   (to build the GNU C inlined debug dll with C++ exception handling)
make clean GC-static-debug     (to build the GNU C inlined static debug lib with C cleanup code)


The pre-built dlls are normally built using the *-inlined targets.

You can run the testsuite by changing to the "tests" directory and
running make for help information. E.g.:

$ cd tests
$ make
Run one of the following command lines:
make clean GC    (to test using GC dll with C (no EH) applications)
make clean GCX   (to test using GC dll with C++ (EH) applications)
make clean GCE   (to test using GCE dll with C++ (EH) applications)
make clean GC-bench       (to benchtest using GNU C dll with C cleanup code)
make clean GCE-bench   (to benchtest using GNU C dll with C++ exception handling)
make clean GC-static   (to test using GC static lib with C (no EH) applications)


Building under Linux using the Mingw32 cross development tools
--------------------------------------------------------------

You can build the library without leaving Linux by using the Mingw32 cross
development toolchain. See http://www.libsdl.org/extras/win32/cross/ for
tools and info. The GNUmakefile contains some support for this, for example:

make CROSS=i386-mingw32msvc- clean GC-inlined

will build pthreadGCn.dll and libpthreadGCn.a (n=version#), provided your
cross-tools/bin directory is in your PATH (or use the cross-make.sh script
at the URL above).


Building the library as a statically linkable library
-----------------------------------------------------

General: PTW32_STATIC_LIB must be defined for both the library build and the
application build. The makefiles supplied and used by the following 'make'
command lines will define this for you.

MSVC (creates pthreadVCn.lib as a static link lib):

nmake clean VC-static


MinGW32 (creates libpthreadGCn.a as a static link lib):

make clean GC-static


Define PTW32_STATIC_LIB when building your application. Also, your
application must call a two non-portable routines to initialise the
some state on startup and cleanup before exit. One other routine needs
to be called to cleanup after any Win32 threads have called POSIX API
routines. See README.NONPORTABLE or the html reference manual pages for
details on these routines:

BOOL pthread_win32_process_attach_np (void);
BOOL pthread_win32_process_detach_np (void);
BOOL pthread_win32_thread_attach_np (void); // Currently a no-op
BOOL pthread_win32_thread_detach_np (void);


The tests makefiles have the same targets but only check that the
static library is statically linkable. They don't run the full
testsuite. To run the full testsuite, build the dlls and run the
dll test targets.


Building the library under Cygwin
---------------------------------

Cygwin is implementing it's own POSIX threads routines and these
will be the ones to use if you develop using Cygwin.


Ready to run binaries
---------------------

For convenience, the following ready-to-run files can be downloaded
from the FTP site (see under "Availability" below):

	pthread.h
	semaphore.h
	sched.h
	pthreadVC.dll	- built with MSVC compiler using C setjmp/longjmp
	pthreadVC.lib
	pthreadVCE.dll	- built with MSVC++ compiler using C++ EH
	pthreadVCE.lib
	pthreadVSE.dll	- built with MSVC compiler using SEH
	pthreadVSE.lib
	pthreadGC.dll	- built with Mingw32 GCC
	libpthreadGC.a	- derived from pthreadGC.dll
	pthreadGCE.dll	- built with Mingw32 G++
	libpthreadGCE.a	- derived from pthreadGCE.dll

As of August 2003 pthreads-win32 pthreadG* versions are built and tested
using the MinGW + MsysDTK environment current as of that date or later.
The following file MAY be needed for older MinGW environments.

	gcc.dll 	- needed to build and run applications that use
			  pthreadGCE.dll.


Building applications with GNU compilers
----------------------------------------

If you're using pthreadGC.dll:

With the three header files, pthreadGC.dll and libpthreadGC.a in the
same directory as your application myapp.c, you could compile, link
and run myapp.c under Mingw32 as follows:

	gcc -o myapp.exe myapp.c -I. -L. -lpthreadGC
	myapp

Or put pthreadGC.dll in an appropriate directory in your PATH,
put libpthreadGC.a in your system lib directory, and
put the three header files in your system include directory,
then use:

	gcc -o myapp.exe myapp.c -lpthreadGC
	myapp


If you're using pthreadGCE.dll:

With the three header files, pthreadGCE.dll, gcc.dll and libpthreadGCE.a
in the same directory as your application myapp.c, you could compile,
link and run myapp.c under Mingw32 as follows:

	gcc -x c++ -o myapp.exe myapp.c -I. -L. -lpthreadGCE
	myapp

Or put pthreadGCE.dll and gcc.dll in an appropriate directory in
your PATH, put libpthreadGCE.a in your system lib directory, and
put the three header files in your system include directory,
then use:

	gcc -x c++ -o myapp.exe myapp.c -lpthreadGCE
	myapp


Availability
------------

The complete source code in either unbundled, self-extracting
Zip file, or tar/gzipped format can be found at:

	ftp://sources.redhat.com/pub/pthreads-win32

The pre-built DLL, export libraries and matching pthread.h can
be found at:

	ftp://sources.redhat.com/pub/pthreads-win32/dll-latest

Home page:

	http://sources.redhat.com/pthreads-win32/


Mailing list
------------

There is a mailing list for discussing pthreads on Win32.
To join, send email to:

	pthreads-win32-subscribe@sources.redhat.com

Unsubscribe by sending mail to:

	pthreads-win32-unsubscribe@sources.redhat.com


Acknowledgements
----------------

See the ANNOUNCE file for acknowledgements.
See the 'CONTRIBUTORS' file for the list of contributors.

As much as possible, the ChangeLog file attributes
contributions and patches that have been incorporated
in the library to the individuals responsible.

Finally, thanks to all those who work on and contribute to the
POSIX and Single Unix Specification standards. The maturity of an
industry can be measured by it's open standards.

----
Ross Johnson
<rpj@callisto.canberra.edu.au>

In ptw32_InterlockedCompareExchange.c, I've added a section for
Borland's compiler; it's identical to that for the MS compiler except
that it uses /* ... */ comments instead of ; comments.

[RPJ: need to define HAVE_TASM32 in config.h to use the above.]


The other file is a makefile suitable for use with Borland's compiler
(run "make -fBmakefile" in the directory).  It builds a single version
of the library, pthreadBC.dll and the corresponding pthreadBC.lib
import library, which is comparable to the pthreadVC version; I can't
personally see any demand for the versions that include structured or
C++ exception cancellation handling so I haven't attempted to build
those versions of the library.  (I imagine a static version might be
of use to some, but we can't legally use that on my commercial
projects so I can't try that out, unfortunately.)

[RPJ: Added tests\Bmakefile as well.]

Borland C++ doesn't define the ENOSYS constant used by pthreads-win32;
rather than make more extensive patches to the pthreads-win32 source I
have a mostly-arbitrary constant for it in the makefile.  However this
doesn't make it visible to the application using the library, so if
anyone actually wants to use this constant in their apps (why?)
someone might like to make a seperate NEED_BCC_something define to add
this stuff.

The makefile also #defines EDEADLK as EDEADLOCK, _timeb as timeb, and
_ftime as ftime, to deal with the minor differences between the two
RTLs' naming conventions, and sets the compiler flags as required to
get a normal compile of the library.

[RPJ: Moved errno values and _timeb etc to pthread.h, so apps will also
use them.]

(While I'm on the subject, the reason Borland users should recompile
the library, rather than using the impdef/implib technique suggested
previously on the mailing list, is that a) the errno constants are
different, so the results returned by the pthread_* functions can be
meaningless, and b) the errno variable/pseudo-variable itself is
different in the MS & BCC runtimes, so you can't access the
pthreadVC's errno from a Borland C++-compiled host application
correctly - I imagine there are other potential problems from the RTL
mismatch too.)

[RPJ: Make sure you use the same RTL in both dll and application builds.
The dll and tests Bmakefiles use cw32mti.lib. Having some trouble with
memory read exceptions running the test suite using BCC55.]

Best regards,
Will

--
Will Bryant
Systems Architect, eCOSM Limited
Cell +64 21 655 443, office +64 3 365 4176
http://www.ecosm.com/

README.CV -- Condition Variables
--------------------------------

The original implementation of condition variables in
pthreads-win32 was based on a discussion paper:

"Strategies for Implementing POSIX Condition Variables
on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

The changes suggested below were made on Feb 6 2001. This
file is included in the package for the benefit of anyone
interested in understanding the pthreads-win32 implementation
of condition variables and the (sometimes subtle) issues that
it attempts to resolve.

Thanks go to the individuals whose names appear throughout
the following text.

Ross Johnson

--------------------------------------------------------------------

fyi.. (more detailed problem description/demos + possible fix/patch)

regards,
alexander.


Alexander Terekhov
31.01.2001 17:43

To:   ace-bugs@cs.wustl.edu
cc:
From: Alexander Terekhov/Germany/IBM@IBMDE
Subject:  Implementation of POSIX CVs: spur.wakeups/lost
      signals/deadlocks/unfairness



    ACE VERSION:

        5.1.12 (pthread-win32 snapshot 2000-12-29)

    HOST MACHINE and OPERATING SYSTEM:

        IBM IntelliStation Z Pro, 2 x XEON 1GHz, Win2K

    TARGET MACHINE and OPERATING SYSTEM, if different from HOST:
    COMPILER NAME AND VERSION (AND PATCHLEVEL):

        Microsoft Visual C++ 6.0

    AREA/CLASS/EXAMPLE AFFECTED:

        Implementation of POSIX condition variables - OS.cpp/.h

    DOES THE PROBLEM AFFECT:

        EXECUTION? YES!

    SYNOPSIS:

        a) spurious wakeups (minor problem)
        b) lost signals
        c) broadcast deadlock
        d) unfairness (minor problem)

    DESCRIPTION:

        Please see attached copy of discussion thread
        from comp.programming.threads for more details on
        some reported problems. (i've also posted a "fyi"
        message to ace-users a week or two ago but
        unfortunately did not get any response so far).

        It seems that current implementation suffers from
        two essential problems:

        1) cond.waiters_count does not accurately reflect
           number of waiters blocked on semaphore - w/o
           proper synchronisation that could result (in the
           time window when counter is not accurate)
           in spurious wakeups organised by subsequent
           _signals  and _broadcasts.

        2) Always having (with no e.g. copy_and_clear/..)
           the same queue in use (semaphore+counter)
           neither signal nor broadcast provide 'atomic'
           behaviour with respect to other threads/subsequent
           calls to signal/broadcast/wait.

        Each problem and combination of both could produce
        various nasty things:

        a) spurious wakeups (minor problem)

             it is possible that waiter(s) which was already
             unblocked even so is still counted as blocked
             waiter. signal and broadcast will release
             semaphore which will produce a spurious wakeup
             for a 'real' waiter coming later.

        b) lost signals

             signalling thread ends up consuming its own
             signal. please see demo/discussion below.

        c) broadcast deadlock

             last_waiter processing code does not correctly
             handle the case with multiple threads
             waiting for the end of broadcast.
             please see demo/discussion below.

        d) unfairness (minor problem)

             without SignalObjectAndWait some waiter(s)
             may end up consuming broadcasted signals
             multiple times (spurious wakeups) because waiter
             thread(s) can be preempted before they call
             semaphore wait (but after count++ and mtx.unlock).

    REPEAT BY:

        See below... run problem demos programs (tennis.cpp and
        tennisb.cpp) number of times concurrently (on multiprocessor)
        and in multiple sessions or just add a couple of "Sleep"s
        as described in the attached copy of discussion thread
        from comp.programming.threads

    SAMPLE FIX/WORKAROUND:

        See attached patch to pthread-win32.. well, I can not
        claim that it is completely bug free but at least my
        test and tests provided by pthreads-win32 seem to work.
        Perhaps that will help.

        regards,
        alexander.


>> Forum: comp.programming.threads
>> Thread: pthread_cond_* implementation questions
.
.
.
David Schwartz <davids@webmaster.com> wrote:

> terekhov@my-deja.com wrote:
>
>> BTW, could you please also share your view on other perceived
>> "problems" such as nested broadcast deadlock, spurious wakeups
>> and (the latest one) lost signals??
>
>I'm not sure what you mean. The standard allows an implementation
>to do almost whatever it likes. In fact, you could implement
>pthread_cond_wait by releasing the mutex, sleeping a random
>amount of time, and then reacquiring the mutex. Of course,
>this would be a pretty poor implementation, but any code that
>didn't work under that implementation wouldn't be strictly
>compliant.

The implementation you suggested is indeed correct
one (yes, now I see it :). However it requires from
signal/broadcast nothing more than to "{ return 0; }"
That is not the case for pthread-win32 and ACE
implementations. I do think that these implementations
(basically the same implementation) have some serious
problems with wait/signal/broadcast calls. I am looking
for help to clarify whether these problems are real
or not. I think that I can demonstrate what I mean
using one or two small sample programs.
.
.
.
==========
tennis.cpp
==========

#include "ace/Synch.h"
#include "ace/Thread.h"

enum GAME_STATE {

  START_GAME,
  PLAYER_A,     // Player A playes the ball
  PLAYER_B,     // Player B playes the ball
  GAME_OVER,
  ONE_PLAYER_GONE,
  BOTH_PLAYERS_GONE

};

enum GAME_STATE             eGameState;
ACE_Mutex*                  pmtxGameStateLock;
ACE_Condition< ACE_Mutex >* pcndGameStateChange;

void*
  playerA(
    void* pParm
  )
{

  // For access to game state variable
  pmtxGameStateLock->acquire();

  // Play loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    cout << endl << "PLAYER-A" << endl;

    // Now its PLAYER-B's turn
    eGameState = PLAYER_B;

    // Signal to PLAYER-B that now it is his turn
    pcndGameStateChange->signal();

    // Wait until PLAYER-B finishes playing the ball
    do {

      pcndGameStateChange->wait();

      if ( PLAYER_B == eGameState )
        cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl;

    } while ( PLAYER_B == eGameState );

  }

  // PLAYER-A gone
  eGameState = (GAME_STATE)(eGameState+1);
  cout << endl << "PLAYER-A GONE" << endl;

  // No more access to state variable needed
  pmtxGameStateLock->release();

  // Signal PLAYER-A gone event
  pcndGameStateChange->broadcast();

  return 0;

}

void*
  playerB(
    void* pParm
  )
{

  // For access to game state variable
  pmtxGameStateLock->acquire();

  // Play loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    cout << endl << "PLAYER-B" << endl;

    // Now its PLAYER-A's turn
    eGameState = PLAYER_A;

    // Signal to PLAYER-A that now it is his turn
    pcndGameStateChange->signal();

    // Wait until PLAYER-A finishes playing the ball
    do {

      pcndGameStateChange->wait();

      if ( PLAYER_A == eGameState )
        cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl;

    } while ( PLAYER_A == eGameState );

  }

  // PLAYER-B gone
  eGameState = (GAME_STATE)(eGameState+1);
  cout << endl << "PLAYER-B GONE" << endl;

  // No more access to state variable needed
  pmtxGameStateLock->release();

  // Signal PLAYER-B gone event
  pcndGameStateChange->broadcast();

  return 0;

}


int
main (int, ACE_TCHAR *[])
{

  pmtxGameStateLock   = new ACE_Mutex();
  pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock
);

  // Set initial state
  eGameState = START_GAME;

  // Create players
  ACE_Thread::spawn( playerA );
  ACE_Thread::spawn( playerB );

  // Give them 5 sec. to play
  Sleep( 5000 );//sleep( 5 );

  // Set game over state
  pmtxGameStateLock->acquire();
  eGameState = GAME_OVER;

  // Let them know
  pcndGameStateChange->broadcast();

  // Wait for players to stop
  do {

    pcndGameStateChange->wait();

  } while ( eGameState < BOTH_PLAYERS_GONE );

  // Cleanup
  cout << endl << "GAME OVER" << endl;
  pmtxGameStateLock->release();
  delete pcndGameStateChange;
  delete pmtxGameStateLock;

  return 0;

}

===========
tennisb.cpp
===========
#include "ace/Synch.h"
#include "ace/Thread.h"

enum GAME_STATE {

  START_GAME,
  PLAYER_A,     // Player A playes the ball
  PLAYER_B,     // Player B playes the ball
  GAME_OVER,
  ONE_PLAYER_GONE,
  BOTH_PLAYERS_GONE

};

enum GAME_STATE             eGameState;
ACE_Mutex*                  pmtxGameStateLock;
ACE_Condition< ACE_Mutex >* pcndGameStateChange;

void*
  playerA(
    void* pParm
  )
{

  // For access to game state variable
  pmtxGameStateLock->acquire();

  // Play loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    cout << endl << "PLAYER-A" << endl;

    // Now its PLAYER-B's turn
    eGameState = PLAYER_B;

    // Signal to PLAYER-B that now it is his turn
    pcndGameStateChange->broadcast();

    // Wait until PLAYER-B finishes playing the ball
    do {

      pcndGameStateChange->wait();

      if ( PLAYER_B == eGameState )
        cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl;

    } while ( PLAYER_B == eGameState );

  }

  // PLAYER-A gone
  eGameState = (GAME_STATE)(eGameState+1);
  cout << endl << "PLAYER-A GONE" << endl;

  // No more access to state variable needed
  pmtxGameStateLock->release();

  // Signal PLAYER-A gone event
  pcndGameStateChange->broadcast();

  return 0;

}

void*
  playerB(
    void* pParm
  )
{

  // For access to game state variable
  pmtxGameStateLock->acquire();

  // Play loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    cout << endl << "PLAYER-B" << endl;

    // Now its PLAYER-A's turn
    eGameState = PLAYER_A;

    // Signal to PLAYER-A that now it is his turn
    pcndGameStateChange->broadcast();

    // Wait until PLAYER-A finishes playing the ball
    do {

      pcndGameStateChange->wait();

      if ( PLAYER_A == eGameState )
        cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl;

    } while ( PLAYER_A == eGameState );

  }

  // PLAYER-B gone
  eGameState = (GAME_STATE)(eGameState+1);
  cout << endl << "PLAYER-B GONE" << endl;

  // No more access to state variable needed
  pmtxGameStateLock->release();

  // Signal PLAYER-B gone event
  pcndGameStateChange->broadcast();

  return 0;

}


int
main (int, ACE_TCHAR *[])
{

  pmtxGameStateLock   = new ACE_Mutex();
  pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock
);

  // Set initial state
  eGameState = START_GAME;

  // Create players
  ACE_Thread::spawn( playerA );
  ACE_Thread::spawn( playerB );

  // Give them 5 sec. to play
  Sleep( 5000 );//sleep( 5 );

  // Make some noise
  pmtxGameStateLock->acquire();
  cout << endl << "---Noise ON..." << endl;
  pmtxGameStateLock->release();
  for ( int i = 0; i < 100000; i++ )
    pcndGameStateChange->broadcast();
  cout << endl << "---Noise OFF" << endl;

  // Set game over state
  pmtxGameStateLock->acquire();
  eGameState = GAME_OVER;
  cout << endl << "---Stopping the game..." << endl;

  // Let them know
  pcndGameStateChange->broadcast();

  // Wait for players to stop
  do {

    pcndGameStateChange->wait();

  } while ( eGameState < BOTH_PLAYERS_GONE );

  // Cleanup
  cout << endl << "GAME OVER" << endl;
  pmtxGameStateLock->release();
  delete pcndGameStateChange;
  delete pmtxGameStateLock;

  return 0;

}
.
.
.
David Schwartz <davids@webmaster.com> wrote:
>> > It's compliant
>>
>> That is really good.
>
>> Tomorrow (I have to go urgently now) I will try to
>> demonstrate the lost-signal "problem" of current
>> pthread-win32 and ACE-(variant w/o SingleObjectAndWait)
>> implementations: players start suddenly drop their balls :-)
>> (with no change in source code).
>
>Signals aren't lost, they're going to the main thread,
>which isn't coded correctly to handle them. Try this:
>
>  // Wait for players to stop
>  do {
>
>    pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock );
>printf("Main thread stole a signal\n");
>
>  } while ( eGameState < BOTH_PLAYERS_GONE );
>
>I bet everytime you thing a signal is lost, you'll see that printf.
>The signal isn't lost, it was stolen by another thread.

well, you can probably loose your bet.. it was indeed stolen
by "another" thread but not the one you seem to think of.

I think that what actually happens is the following:

H:\SA\UXX\pt\PTHREADS\TESTS>tennis3.exe

PLAYER-A

PLAYER-B

----PLAYER-B: SPURIOUS WAKEUP!!!

PLAYER-A GONE

PLAYER-B GONE

GAME OVER

H:\SA\UXX\pt\PTHREADS\TESTS>

here you can see that PLAYER-B after playing his first
ball (which came via signal from PLAYER-A) just dropped
it down. What happened is that his signal to player A
was consumed as spurious wakeup by himself (player B).

The implementation has a problem:

================
waiting threads:
================

{ /** Critical Section

  inc cond.waiters_count

}

  /*
  /* Atomic only if using Win32 SignalObjectAndWait
  /*
  cond.mtx.release

  /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX,
  /***      GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE
  /***      ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL!

  cond.sem.wait

Player-A after playing game's initial ball went into
wait (called _wait) but was pre-empted before reaching
wait semaphore. He was counted as waiter but was not
actually waiting/blocked yet.

===============
signal threads:
===============

{ /** Critical Section

  waiters_count = cond.waiters_count

}

  if ( waiters_count != 0 )

    sem.post 1

  endif

Player-B after he received signal/ball from Player A
called _signal. The _signal did see that there was
one waiter blocked on the condition (Player-A) and
released the semaphore.. (but it did not unblock
Player-A because he was not actually blocked).
Player-B thread continued its execution, called _wait,
was counted as second waiter BUT was allowed to slip
through opened semaphore gate (which was opened for
Player-B) and received his own signal. Player B remained
blocked followed by Player A. Deadlock happened which
lasted until main thread came in and said game over.

It seems to me that the implementation fails to
correctly implement the following statement
from specification:

http://www.opengroup.org/
onlinepubs/007908799/xsh/pthread_cond_wait.html

"These functions atomically release mutex and cause
the calling thread to block on the condition variable
cond; atomically here means "atomically with respect
to access by another thread to the mutex and then the
condition variable". That is, if another thread is
able to acquire the mutex after the about-to-block
thread has released it, then a subsequent call to
pthread_cond_signal() or pthread_cond_broadcast()
in that thread behaves as if it were issued after
the about-to-block thread has blocked."

Question: Am I right?

(I produced the program output above by simply
adding ?Sleep( 1 )?:

================
waiting threads:
================

{ /** Critical Section

  inc cond.waiters_count

}

  /*
  /* Atomic only if using Win32 SignalObjectAndWait
  /*
  cond.mtx.release

Sleep( 1 ); // Win32

  /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX,
  /***      GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE
  /***      ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL!

  cond.sem.wait

to the source code of pthread-win32 implementation:

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


  /*
  * We keep the lock held just long enough to increment the count of
  * waiters by one (above).
  * Note that we can't keep it held across the
  * call to sem_wait since that will deadlock other calls
  * to pthread_cond_signal
  */
  cleanup_args.mutexPtr = mutex;
  cleanup_args.cv = cv;
  cleanup_args.resultPtr = &result;

  pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *)
&cleanup_args);

  if ((result = pthread_mutex_unlock (mutex)) == 0)
    {((result
Sleep( 1 ); // @AT

      /*
      * Wait to be awakened by
      *              pthread_cond_signal, or
      *              pthread_cond_broadcast, or
      *              a timeout
      *
      * Note:
      *      ptw32_sem_timedwait is a cancelation point,
      *      hence providing the
      *      mechanism for making pthread_cond_wait a cancelation
      *      point. We use the cleanup mechanism to ensure we
      *      re-lock the mutex and decrement the waiters count
      *      if we are canceled.
      */
      if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1)         {
          result = errno;
        }
    }

  pthread_cleanup_pop (1);  /* Always cleanup */


BTW, on my system (2 CPUs) I can manage to get
signals lost even without any source code modification
if I run the tennis program many times in different
shell sessions.
.
.
.
David Schwartz <davids@webmaster.com> wrote:
>terekhov@my-deja.com wrote:
>
>> well, it might be that the program is in fact buggy.
>> but you did not show me any bug.
>
>You're right. I was close but not dead on. I was correct, however,
>that the code is buggy because it uses 'pthread_cond_signal' even
>though not any thread waiting on the condition variable can do the
>job. I was wrong in which thread could be waiting on the cv but
>unable to do the job.

Okay, lets change 'pthread_cond_signal' to 'pthread_cond_broadcast'
but also add some noise from main() right before declaring the game
to be over (I need it in order to demonstrate another problem of
pthread-win32/ACE implementations - broadcast deadlock)...
.
.
.
It is my understanding of POSIX conditions,
that on correct implementation added noise
in form of unnecessary broadcasts from main,
should not break the tennis program. The
only 'side effect' of added noise on correct
implementation would be 'spurious wakeups' of
players (in fact they are not spurious,
players just see them as spurious) unblocked,
not by another player but by main before
another player had a chance to acquire the
mutex and change the game state variable:
.
.
.

PLAYER-B

PLAYER-A

---Noise ON...

PLAYER-B

PLAYER-A

.
.
.

PLAYER-B

PLAYER-A

----PLAYER-A: SPURIOUS WAKEUP!!!

PLAYER-B

PLAYER-A

---Noise OFF

PLAYER-B

---Stopping the game...

PLAYER-A GONE

PLAYER-B GONE

GAME OVER

H:\SA\UXX\pt\PTHREADS\TESTS>

On pthread-win32/ACE implementations the
program could stall:

.
.
.

PLAYER-A

PLAYER-B

PLAYER-A

PLAYER-B

PLAYER-A

PLAYER-B

PLAYER-A

PLAYER-B

---Noise ON...

PLAYER-A

---Noise OFF
^C
H:\SA\UXX\pt\PTHREADS\TESTS>


The implementation has problems:

================
waiting threads:
================

{ /** Critical Section

  inc cond.waiters_count

}

  /*
  /* Atomic only if using Win32 SignalObjectAndWait
  /*
  cond.mtx.release
  cond.sem.wait

  /*** ^^-- WAITER CAN BE PREEMPTED AFTER BEING UNBLOCKED...

{ /** Critical Section

  dec cond.waiters_count

  /*** ^^- ...AND BEFORE DECREMENTING THE COUNT (1)

  last_waiter = ( cond.was_broadcast &&
                    cond.waiters_count == 0 )

  if ( last_waiter )

    cond.was_broadcast = FALSE

  endif

}

  if ( last_waiter )

    /*
    /* Atomic only if using Win32 SignalObjectAndWait
    /*
    cond.auto_reset_event_or_sem.post /* Event for Win32
    cond.mtx.acquire

  /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (2)

  /*** ^^-- NESTED BROADCASTS RESULT IN A DEADLOCK


  else

    cond.mtx.acquire

  /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (3)

  endif


==================
broadcast threads:
==================

{ /** Critical Section

  waiters_count = cond.waiters_count

  if ( waiters_count != 0 )

    cond.was_broadcast = TRUE

  endif

}

if ( waiters_count != 0 )

  cond.sem.post waiters_count

  /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1)

  cond.auto_reset_event_or_sem.wait /* Event for Win32

  /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY
                HAPPEN TO GO INTO WAIT WHILE PREVIOUS
                BROADCAST IS STILL IN PROGRESS/WAITING

endif

a) cond.waiters_count does not accurately reflect
number of waiters blocked on semaphore - that could
result (in the time window when counter is not accurate)
in spurios wakeups organised by subsequent _signals
and _broadcasts. From standard compliance point of view
that is OK but that could be a real problem from
performance/efficiency point of view.

b) If subsequent broadcast happen to go into wait on
cond.auto_reset_event_or_sem before previous
broadcast was unblocked from cond.auto_reset_event_or_sem
by its last waiter, one of two blocked threads will
remain blocked because last_waiter processing code
fails to unblock both threads.

In the situation with tennisb.c the Player-B was put
in a deadlock by noise (broadcast) coming from main
thread. And since Player-B holds the game state
mutex when it calls broadcast, the whole program
stalled: Player-A was deadlocked on mutex and
main thread after finishing with producing the noise
was deadlocked on mutex too (needed to declare the
game over)

(I produced the program output above by simply
adding ?Sleep( 1 )?:

==================
broadcast threads:
==================

{ /** Critical Section

  waiters_count = cond.waiters_count

  if ( waiters_count != 0 )

    cond.was_broadcast = TRUE

  endif

}

if ( waiters_count != 0 )

Sleep( 1 ); //Win32

  cond.sem.post waiters_count

  /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1)

  cond.auto_reset_event_or_sem.wait /* Event for Win32

  /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY
                HAPPEN TO GO INTO WAIT WHILE PREVIOUS
                BROADCAST IS STILL IN PROGRESS/WAITING

endif

to the source code of pthread-win32 implementation:

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

  if (wereWaiters)
    {(wereWaiters)sroot=pthreads-win32eb.cgi/pthreads/Yem...m
      /*
      * Wake up all waiters
      */

Sleep( 1 ); //@AT

#ifdef NEED_SEM

      result = (ptw32_increase_semaphore( &cv->sema, cv->waiters )
                 ? 0
                : EINVAL);

#else /* NEED_SEM */

      result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL )
                 ? 0
                : EINVAL);

#endif /* NEED_SEM */

    }

  (void) pthread_mutex_unlock(&(cv->waitersLock));

  if (wereWaiters && result == 0)
    {(wereWaiters
      /*
       * Wait for all the awakened threads to acquire their part of
       * the counting semaphore
       */

      if (WaitForSingleObject (cv->waitersDone, INFINITE)
          == WAIT_OBJECT_0)
        {
          result = 0;
        }
      else
        {
          result = EINVAL;
        }

    }

  return (result);

}

BTW, on my system (2 CPUs) I can manage to get
the program stalled even without any source code
modification if I run the tennisb program many
times in different shell sessions.

===================
pthread-win32 patch
===================
struct pthread_cond_t_ {
  long            nWaitersBlocked;   /* Number of threads blocked
*/
  long            nWaitersUnblocked; /* Number of threads unblocked
*/
  long            nWaitersToUnblock; /* Number of threads to unblock
*/
  sem_t           semBlockQueue;     /* Queue up threads waiting for the
*/
                                     /*   condition to become signalled
*/
  sem_t           semBlockLock;      /* Semaphore that guards access to
*/
                                     /* | waiters blocked count/block queue
*/
                                     /* +-> Mandatory Sync.LEVEL-1
*/
  pthread_mutex_t mtxUnblockLock;    /* Mutex that guards access to
*/
                                     /* | waiters (to)unblock(ed) counts
*/
                                     /* +-> Optional* Sync.LEVEL-2
*/
};                                   /* Opt*) for _timedwait and
cancellation*/

int
pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr)
  int result = EAGAIN;
  pthread_cond_t cv = NULL;

  if (cond == NULL)
    {(cond
      return EINVAL;
    }

  if ((attr != NULL && *attr != NULL) &&
      ((*attr)->pshared == PTHREAD_PROCESS_SHARED))
    {
      /*
       * Creating condition variable that can be shared between
       * processes.
       */
      result = ENOSYS;

      goto FAIL0;
    }

  cv = (pthread_cond_t) calloc (1, sizeof (*cv));

  if (cv == NULL)
    {(cv
      result = ENOMEM;
      goto FAIL0;
    }

  cv->nWaitersBlocked   = 0;
  cv->nWaitersUnblocked = 0;
  cv->nWaitersToUnblock = 0;

  if (sem_init (&(cv->semBlockLock), 0, 1) != 0)
    {(sem_init
      goto FAIL0;
    }

  if (sem_init (&(cv->semBlockQueue), 0, 0) != 0)
    {(sem_init
      goto FAIL1;
    }

  if (pthread_mutex_init (&(cv->mtxUnblockLock), 0) != 0)
    {(pthread_mutex_init
      goto FAIL2;
    }


  result = 0;

  goto DONE;

  /*
   * -------------
   * Failed...
   * -------------
   */
FAIL2:
  (void) sem_destroy (&(cv->semBlockQueue));

FAIL1:
  (void) sem_destroy (&(cv->semBlockLock));

FAIL0:
DONE:
  *cond = cv;

  return (result);

}                               /* pthread_cond_init */

int
pthread_cond_destroy (pthread_cond_t * cond)
{
  int result = 0;
  pthread_cond_t cv;

  /*
   * Assuming any race condition here is harmless.
   */
  if (cond == NULL
      || *cond == NULL)
    {
      return EINVAL;
    }

  if (*cond != (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
    {(*cond
      cv = *cond;

      /*
       * Synchronize access to waiters blocked count (LEVEL-1)
       */
      if (sem_wait(&(cv->semBlockLock)) != 0)
        {(sem_wait(&(cv->semBlockLock))
          return errno;
        }

      /*
       * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2)
       */
      if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
        {((result
          (void) sem_post(&(cv->semBlockLock));
          return result;
        }

      /*
       * Check whether cv is still busy (still has waiters blocked)
       */
      if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0)
        {(cv->nWaitersBlocked
          (void) sem_post(&(cv->semBlockLock));
          (void) pthread_mutex_unlock(&(cv->mtxUnblockLock));
          return EBUSY;
        }

      /*
       * Now it is safe to destroy
       */
      (void) sem_destroy (&(cv->semBlockLock));
      (void) sem_destroy (&(cv->semBlockQueue));
      (void) pthread_mutex_unlock (&(cv->mtxUnblockLock));
      (void) pthread_mutex_destroy (&(cv->mtxUnblockLock));

      free(cv);
      *cond = NULL;
    }
  else
    {
      /*
       * See notes in ptw32_cond_check_need_init() above also.
       */
      EnterCriticalSection(&ptw32_cond_test_init_lock);

      /*
       * Check again.
       */
      if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
        {(*cond
          /*
           * This is all we need to do to destroy a statically
           * initialised cond that has not yet been used (initialised).
           * If we get to here, another thread
           * waiting to initialise this cond will get an EINVAL.
           */
          *cond = NULL;
        }
      else
        {
          /*
           * The cv has been initialised while we were waiting
           * so assume it's in use.
           */
          result = EBUSY;
        }

      LeaveCriticalSection(&ptw32_cond_test_init_lock);
    }

  return (result);
}

/*
 * Arguments for cond_wait_cleanup, since we can only pass a
 * single void * to it.
 */
typedef struct {
  pthread_mutex_t * mutexPtr;
  pthread_cond_t cv;
  int * resultPtr;
} ptw32_cond_wait_cleanup_args_t;

static void
ptw32_cond_wait_cleanup(void * args)
{
  ptw32_cond_wait_cleanup_args_t * cleanup_args =
(ptw32_cond_wait_cleanup_args_t *) args;
  pthread_cond_t cv = cleanup_args->cv;
  int * resultPtr = cleanup_args->resultPtr;
  int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s)
*/
  int result;

  /*
   * Whether we got here as a result of signal/broadcast or because of
   * timeout on wait or thread cancellation we indicate that we are no
   * longer waiting. The waiter is responsible for adjusting waiters
   * (to)unblock(ed) counts (protected by unblock lock).
   * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation.
   */
  if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
    {((result
      *resultPtr = result;
      return;
    }

  cv->nWaitersUnblocked++;

  eLastSignal = (cv->nWaitersToUnblock == 0) ?
                   -1 : (--cv->nWaitersToUnblock == 0);

  /*
   * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed
   */
  if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0)
    {((result
      *resultPtr = result;
      return;
    }

  /*
   * If last signal...
   */
  if (eLastSignal == 1)
    {(eLastSignal
     /*
      * ...it means that we have end of 'atomic' signal/broadcast
      */
      if (sem_post(&(cv->semBlockLock)) != 0)
        {(sem_post(&(cv->semBlockLock))
          *resultPtr = errno;
          return;
        }
    }
  /*
   * If not last signal and not timed out/cancelled wait w/o signal...
   */
  else if (eLastSignal == 0)
    {
     /*
      * ...it means that next waiter can go through semaphore
      */
      if (sem_post(&(cv->semBlockQueue)) != 0)
        {(sem_post(&(cv->semBlockQueue))
          *resultPtr = errno;
          return;
        }
    }

  /*
   * XSH: Upon successful return, the mutex has been locked and is owned
   * by the calling thread
   */
  if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0)
    {((result
      *resultPtr = result;
    }

}                               /* ptw32_cond_wait_cleanup */

static int
ptw32_cond_timedwait (pthread_cond_t * cond,
                      pthread_mutex_t * mutex,
                      const struct timespec *abstime)
{
  int result = 0;
  pthread_cond_t cv;
  ptw32_cond_wait_cleanup_args_t cleanup_args;

  if (cond == NULL || *cond == NULL)
    {(cond
      return EINVAL;
    }

  /*
   * We do a quick check to see if we need to do more work
   * to initialise a static condition variable. We check
   * again inside the guarded section of ptw32_cond_check_need_init()
   * to avoid race conditions.
   */
  if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
    {(*cond
      result = ptw32_cond_check_need_init(cond);
    }

  if (result != 0 && result != EBUSY)
    {(result
      return result;
    }

  cv = *cond;

  /*
   * Synchronize access to waiters blocked count (LEVEL-1)
   */
  if (sem_wait(&(cv->semBlockLock)) != 0)
    {(sem_wait(&(cv->semBlockLock))
      return errno;
    }

  cv->nWaitersBlocked++;

  /*
   * Thats it. Counted means waiting, no more access needed
   */
  if (sem_post(&(cv->semBlockLock)) != 0)
    {(sem_post(&(cv->semBlockLock))
      return errno;
    }

  /*
   * Setup this waiter cleanup handler
   */
  cleanup_args.mutexPtr = mutex;
  cleanup_args.cv = cv;
  cleanup_args.resultPtr = &result;

  pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args);

  /*
   * Now we can release 'mutex' and...
   */
  if ((result = pthread_mutex_unlock (mutex)) == 0)
    {((result

      /*
       * ...wait to be awakened by
       *              pthread_cond_signal, or
       *              pthread_cond_broadcast, or
       *              timeout, or
       *              thread cancellation
       *
       * Note:
       *
       *      ptw32_sem_timedwait is a cancellation point,
       *      hence providing the mechanism for making
       *      pthread_cond_wait a cancellation point.
       *      We use the cleanup mechanism to ensure we
       *      re-lock the mutex and adjust (to)unblock(ed) waiters
       *      counts if we are cancelled, timed out or signalled.
       */
      if (ptw32_sem_timedwait (&(cv->semBlockQueue), abstime) != 0)
        {(ptw32_sem_timedwait
          result = errno;
        }
    }

  /*
   * Always cleanup
   */
  pthread_cleanup_pop (1);


  /*
   * "result" can be modified by the cleanup handler.
   */
  return (result);

}                               /* ptw32_cond_timedwait */


static int
ptw32_cond_unblock (pthread_cond_t * cond,
                    int unblockAll)
{
  int result;
  pthread_cond_t cv;

  if (cond == NULL || *cond == NULL)
    {(cond
      return EINVAL;
    }

  cv = *cond;

  /*
   * No-op if the CV is static and hasn't been initialised yet.
   * Assuming that any race condition is harmless.
   */
  if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
    {(cv
      return 0;
    }

  /*
   * Synchronize access to waiters blocked count (LEVEL-1)
   */
  if (sem_wait(&(cv->semBlockLock)) != 0)
    {(sem_wait(&(cv->semBlockLock))
      return errno;
    }

  /*
   * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2)
   * This sync.level supports _timedwait and cancellation
   */
  if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
    {((result
      return result;
    }

  /*
   * Adjust waiters blocked and unblocked counts (collect garbage)
   */
  if (cv->nWaitersUnblocked != 0)
    {(cv->nWaitersUnblocked
      cv->nWaitersBlocked  -= cv->nWaitersUnblocked;
      cv->nWaitersUnblocked = 0;
    }

  /*
   * If (after adjustment) there are still some waiters blocked counted...
   */
  if ( cv->nWaitersBlocked > 0)
    {(
      /*
       * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked
       * LEVEL-1 access is left disabled until last signal/unblock
completes
       */
      cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1;

      /*
       * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed
       * This sync.level supports _timedwait and cancellation
       */
      if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0)
        {((result
          return result;
        }


      /*
       * Now, with LEVEL-2 lock released let first waiter go through
semaphore
       */
      if (sem_post(&(cv->semBlockQueue)) != 0)
        {(sem_post(&(cv->semBlockQueue))
          return errno;
        }
    }
  /*
   * No waiter blocked - no more LEVEL-1 access to blocked count needed...
   */
  else if (sem_post(&(cv->semBlockLock)) != 0)
    {
      return errno;
    }
  /*
   * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed
too
   * This sync.level supports _timedwait and cancellation
   */
  else
    {
      result = pthread_mutex_unlock(&(cv->mtxUnblockLock));
    }

  return(result);

}                               /* ptw32_cond_unblock */

int
pthread_cond_wait (pthread_cond_t * cond,
                   pthread_mutex_t * mutex)
{
  /* The NULL abstime arg means INFINITE waiting. */
  return(ptw32_cond_timedwait(cond, mutex, NULL));
}                               /* pthread_cond_wait */


int
pthread_cond_timedwait (pthread_cond_t * cond,
                        pthread_mutex_t * mutex,
                        const struct timespec *abstime)
{
  if (abstime == NULL)
    {(abstime
      return EINVAL;
    }

  return(ptw32_cond_timedwait(cond, mutex, abstime));
}                               /* pthread_cond_timedwait */


int
pthread_cond_signal (pthread_cond_t * cond)
{
  /* The '0'(FALSE) unblockAll arg means unblock ONE waiter. */
  return(ptw32_cond_unblock(cond, 0));
}                               /* pthread_cond_signal */

int
pthread_cond_broadcast (pthread_cond_t * cond)
{
  /* The '1'(TRUE) unblockAll arg means unblock ALL waiters. */
  return(ptw32_cond_unblock(cond, 1));
}                               /* pthread_cond_broadcast */




TEREKHOV@de.ibm.com on 17.01.2001 01:00:57

Please respond to TEREKHOV@de.ibm.com

To:   pthreads-win32@sourceware.cygnus.com
cc:   schmidt@uci.edu
Subject:  win32 conditions: sem+counter+event = broadcast_deadlock +
      spur.wakeup/unfairness/incorrectness ??







Hi,

Problem 1: broadcast_deadlock

It seems that current implementation does not provide "atomic"
broadcasts. That may lead to "nested" broadcasts... and it seems
that nested case is not handled correctly -> producing a broadcast
DEADLOCK as a result.

Scenario:

N (>1) waiting threads W1..N are blocked (in _wait) on condition's
semaphore.

Thread B1 calls pthread_cond_broadcast, which results in "releasing" N
W threads via incrementing semaphore counter by N (stored in
cv->waiters) BUT cv->waiters counter does not change!! The caller
thread B1 remains blocked on cv->waitersDone event (auto-reset!!) BUT
condition is not protected from starting another broadcast (when called
on another thread) while still waiting for the "old" broadcast to
complete on thread B1.

M (>=0, <N) W threads are fast enough to go thru their _wait call and
decrement cv->waiters counter.

L (N-M) "late" waiter W threads are a) still blocked/not returned from
their semaphore wait call or b) were preempted after sem_wait but before
lock( &cv->waitersLock ) or c) are blocked on cv->waitersLock.

cv->waiters is still > 0 (= L).

Another thread B2 (or some W thread from M group) calls
pthread_cond_broadcast and gains access to counter... neither a) nor b)
prevent thread B2 in pthread_cond_broadcast from gaining access to
counter and starting another broadcast ( for c) - it depends on
cv->waitersLock scheduling rules: FIFO=OK, PRTY=PROBLEM,... )

That call to pthread_cond_broadcast (on thread B2) will result in
incrementing semaphore by cv->waiters (=L) which is INCORRECT (all
W1..N were in fact already released by thread B1) and waiting on
_auto-reset_ event cv->waitersDone which is DEADLY WRONG (produces a
deadlock)...

All late W1..L threads now have a chance to complete their _wait call.
Last W_L thread sets an auto-reselt event cv->waitersDone which will
release either B1 or B2 leaving one of B threads in a deadlock.

Problem 2: spur.wakeup/unfairness/incorrectness

It seems that:

a) because of the same problem with counter which does not reflect the
actual number of NOT RELEASED waiters, the signal call may increment
a semaphore counter w/o having a waiter blocked on it. That will result
in (best case) spurious wake ups - performance degradation due to
unnecessary context switches and predicate re-checks and (in worth case)
unfairness/incorrectness problem - see b)

b) neither signal nor broadcast prevent other threads - "new waiters"
(and in the case of signal, the caller thread as well) from going into
_wait and overtaking "old" waiters (already released but still not returned
from sem_wait on condition's semaphore). Win semaphore just [API DOC]:
"Maintains a count between zero and some maximum value, limiting the number
of threads that are simultaneously accessing a shared resource." Calling
ReleaseSemaphore does not imply (at least not documented) that on return
from ReleaseSemaphore all waiters will in fact become released (returned
from their Wait... call) and/or that new waiters calling Wait... afterwards
will become less importance. It is NOT documented to be an atomic release
of
waiters... And even if it would be there is still a problem with a thread
being preempted after Wait on semaphore and before Wait on cv->waitersLock
and scheduling rules for cv->waitersLock itself
(??WaitForMultipleObjects??)
That may result in unfairness/incorrectness problem as described
for SetEvent impl. in "Strategies for Implementing POSIX Condition
Variables
on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

Unfairness -- The semantics of the POSIX pthread_cond_broadcast function is
to wake up all threads currently blocked in wait calls on the condition
variable. The awakened threads then compete for the external_mutex. To
ensure
fairness, all of these threads should be released from their
pthread_cond_wait calls and allowed to recheck their condition expressions
before other threads can successfully complete a wait on the condition
variable.

Unfortunately, the SetEvent implementation above does not guarantee that
all
threads sleeping on the condition variable when cond_broadcast is called
will
acquire the external_mutex and check their condition expressions. Although
the Pthreads specification does not mandate this degree of fairness, the
lack of fairness can cause starvation.

To illustrate the unfairness problem, imagine there are 2 threads, C1 and
C2,
that are blocked in pthread_cond_wait on condition variable not_empty_ that
is guarding a thread-safe message queue. Another thread, P1 then places two
messages onto the queue and calls pthread_cond_broadcast. If C1 returns
from
pthread_cond_wait, dequeues and processes the message, and immediately
waits
again then it and only it may end up acquiring both messages. Thus, C2 will
never get a chance to dequeue a message and run.

The following illustrates the sequence of events:

1.   Thread C1 attempts to dequeue and waits on CV non_empty_
2.   Thread C2 attempts to dequeue and waits on CV non_empty_
3.   Thread P1 enqueues 2 messages and broadcasts to CV not_empty_
4.   Thread P1 exits
5.   Thread C1 wakes up from CV not_empty_, dequeues a message and runs
6.   Thread C1 waits again on CV not_empty_, immediately dequeues the 2nd
        message and runs
7.   Thread C1 exits
8.   Thread C2 is the only thread left and blocks forever since
        not_empty_ will never be signaled

Depending on the algorithm being implemented, this lack of fairness may
yield
concurrent programs that have subtle bugs. Of course, application
developers
should not rely on the fairness semantics of pthread_cond_broadcast.
However,
there are many cases where fair implementations of condition variables can
simplify application code.

Incorrectness -- A variation on the unfairness problem described above
occurs
when a third consumer thread, C3, is allowed to slip through even though it
was not waiting on condition variable not_empty_ when a broadcast occurred.

To illustrate this, we will use the same scenario as above: 2 threads, C1
and
C2, are blocked dequeuing messages from the message queue. Another thread,
P1
then places two messages onto the queue and calls pthread_cond_broadcast.
C1
returns from pthread_cond_wait, dequeues and processes the message. At this
time, C3 acquires the external_mutex, calls pthread_cond_wait and waits on
the events in WaitForMultipleObjects. Since C2 has not had a chance to run
yet, the BROADCAST event is still signaled. C3 then returns from
WaitForMultipleObjects, and dequeues and processes the message in the
queue.
Thus, C2 will never get a chance to dequeue a message and run.

The following illustrates the sequence of events:

1.   Thread C1 attempts to dequeue and waits on CV non_empty_
2.   Thread C2 attempts to dequeue and waits on CV non_empty_
3.   Thread P1 enqueues 2 messages and broadcasts to CV not_empty_
4.   Thread P1 exits
5.   Thread C1 wakes up from CV not_empty_, dequeues a message and runs
6.   Thread C1 exits
7.   Thread C3 waits on CV not_empty_, immediately dequeues the 2nd
        message and runs
8.   Thread C3 exits
9.   Thread C2 is the only thread left and blocks forever since
        not_empty_ will never be signaled

In the above case, a thread that was not waiting on the condition variable
when a broadcast occurred was allowed to proceed. This leads to incorrect
semantics for a condition variable.


COMMENTS???

regards,
alexander.

-----------------------------------------------------------------------------

Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_*
     implementation questions
Date: Wed, 21 Feb 2001 11:54:47 +0100
From: TEREKHOV@de.ibm.com
To: lthomas@arbitrade.com
CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
     Nanbor Wang <nanbor@cs.wustl.edu>

Hi Louis,

generation number 8..

had some time to revisit timeouts/spurious wakeup problem..
found some bugs (in 7.b/c/d) and something to improve
(7a - using IPC semaphores but it should speedup Win32
version as well).

regards,
alexander.

---------- Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
given:
semBlockLock - bin.semaphore
semBlockQueue - semaphore
mtxExternal - mutex or CS
mtxUnblockLock - mutex or CS
nWaitersGone - int
nWaitersBlocked - int
nWaitersToUnblock - int

wait( timeout ) {

  [auto: register int result          ]     // error checking omitted
  [auto: register int nSignalsWasLeft ]
  [auto: register int nWaitersWasGone ]

  sem_wait( semBlockLock );
  nWaitersBlocked++;
  sem_post( semBlockLock );

  unlock( mtxExternal );
  bTimedOut = sem_wait( semBlockQueue,timeout );

  lock( mtxUnblockLock );
  if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
    if ( bTimeout ) {                       // timeout (or canceled)
      if ( 0 != nWaitersBlocked ) {
        nWaitersBlocked--;
      }
      else {
        nWaitersGone++;                     // count spurious wakeups
      }
    }
    if ( 0 == --nWaitersToUnblock ) {
      if ( 0 != nWaitersBlocked ) {
        sem_post( semBlockLock );           // open the gate
        nSignalsWasLeft = 0;                // do not open the gate below
again
      }
      else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
        nWaitersGone = 0;
      }
    }
  }
  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
semaphore :-)
    sem_wait( semBlockLock );
    nWaitersBlocked -= nWaitersGone;        // something is going on here -
test of timeouts? :-)
    sem_post( semBlockLock );
    nWaitersGone = 0;
  }
  unlock( mtxUnblockLock );

  if ( 1 == nSignalsWasLeft ) {
    if ( 0 != nWaitersWasGone ) {
      // sem_adjust( -nWaitersWasGone );
      while ( nWaitersWasGone-- ) {
        sem_wait( semBlockLock );          // better now than spurious
later
      }
    }
    sem_post( semBlockLock );              // open the gate
  }

  lock( mtxExternal );

  return ( bTimedOut ) ? ETIMEOUT : 0;
}

signal(bAll) {

  [auto: register int result         ]
  [auto: register int nSignalsToIssue]

  lock( mtxUnblockLock );

  if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
    if ( 0 == nWaitersBlocked ) { // NO-OP
      return unlock( mtxUnblockLock );
    }
    if (bAll) {
      nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nSignalsToIssue = 1;
      nWaitersToUnblock++;
      nWaitersBlocked--;
    }
  }
  else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
    sem_wait( semBlockLock ); // close the gate
    if ( 0 != nWaitersGone ) {
      nWaitersBlocked -= nWaitersGone;
      nWaitersGone = 0;
    }
    if (bAll) {
      nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nSignalsToIssue = nWaitersToUnblock = 1;
      nWaitersBlocked--;
    }
  }
  else { // NO-OP
    return unlock( mtxUnblockLock );
  }

  unlock( mtxUnblockLock );
  sem_post( semBlockQueue,nSignalsToIssue );
  return result;
}

---------- Algorithm 8b / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE
------
given:
semBlockLock - bin.semaphore
semBlockQueue - bin.semaphore
mtxExternal - mutex or CS
mtxUnblockLock - mutex or CS
nWaitersGone - int
nWaitersBlocked - int
nWaitersToUnblock - int

wait( timeout ) {

  [auto: register int result          ]     // error checking omitted
  [auto: register int nWaitersWasGone ]
  [auto: register int nSignalsWasLeft ]

  sem_wait( semBlockLock );
  nWaitersBlocked++;
  sem_post( semBlockLock );

  unlock( mtxExternal );
  bTimedOut = sem_wait( semBlockQueue,timeout );

  lock( mtxUnblockLock );
  if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
    if ( bTimeout ) {                       // timeout (or canceled)
      if ( 0 != nWaitersBlocked ) {
        nWaitersBlocked--;
        nSignalsWasLeft = 0;                // do not unblock next waiter
below (already unblocked)
      }
      else {
        nWaitersGone = 1;                   // spurious wakeup pending!!
      }
    }
    if ( 0 == --nWaitersToUnblock &&
      if ( 0 != nWaitersBlocked ) {
        sem_post( semBlockLock );           // open the gate
        nSignalsWasLeft = 0;                // do not open the gate below
again
      }
      else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
        nWaitersGone = 0;
      }
    }
  }
  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
semaphore :-)
    sem_wait( semBlockLock );
    nWaitersBlocked -= nWaitersGone;        // something is going on here -
test of timeouts? :-)
    sem_post( semBlockLock );
    nWaitersGone = 0;
  }
  unlock( mtxUnblockLock );

  if ( 1 == nSignalsWasLeft ) {
    if ( 0 != nWaitersWasGone ) {
      // sem_adjust( -1 );
      sem_wait( semBlockQueue );           // better now than spurious
later
    }
    sem_post( semBlockLock );              // open the gate
  }
  else if ( 0 != nSignalsWasLeft ) {
    sem_post( semBlockQueue );             // unblock next waiter
  }

  lock( mtxExternal );

  return ( bTimedOut ) ? ETIMEOUT : 0;
}

signal(bAll) {

  [auto: register int result ]

  lock( mtxUnblockLock );

  if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
    if ( 0 == nWaitersBlocked ) { // NO-OP
      return unlock( mtxUnblockLock );
    }
    if (bAll) {
      nWaitersToUnblock += nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nWaitersToUnblock++;
      nWaitersBlocked--;
    }
    unlock( mtxUnblockLock );
  }
  else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
    sem_wait( semBlockLock ); // close the gate
    if ( 0 != nWaitersGone ) {
      nWaitersBlocked -= nWaitersGone;
      nWaitersGone = 0;
    }
    if (bAll) {
      nWaitersToUnblock = nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nWaitersToUnblock = 1;
      nWaitersBlocked--;
    }
    unlock( mtxUnblockLock );
    sem_post( semBlockQueue );
  }
  else { // NO-OP
    unlock( mtxUnblockLock );
  }

  return result;
}

---------- Algorithm 8c / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE
---------
given:
hevBlockLock - auto-reset event
hevBlockQueue - auto-reset event
mtxExternal - mutex or CS
mtxUnblockLock - mutex or CS
nWaitersGone - int
nWaitersBlocked - int
nWaitersToUnblock - int

wait( timeout ) {

  [auto: register int result          ]     // error checking omitted
  [auto: register int nSignalsWasLeft ]
  [auto: register int nWaitersWasGone ]

  wait( hevBlockLock,INFINITE );
  nWaitersBlocked++;
  set_event( hevBlockLock );

  unlock( mtxExternal );
  bTimedOut = wait( hevBlockQueue,timeout );

  lock( mtxUnblockLock );
  if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
    if ( bTimeout ) {                       // timeout (or canceled)
      if ( 0 != nWaitersBlocked ) {
        nWaitersBlocked--;
        nSignalsWasLeft = 0;                // do not unblock next waiter
below (already unblocked)
      }
      else {
        nWaitersGone = 1;                   // spurious wakeup pending!!
      }
    }
    if ( 0 == --nWaitersToUnblock )
      if ( 0 != nWaitersBlocked ) {
        set_event( hevBlockLock );          // open the gate
        nSignalsWasLeft = 0;                // do not open the gate below
again
      }
      else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
        nWaitersGone = 0;
      }
    }
  }
  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
event :-)
    wait( hevBlockLock,INFINITE );
    nWaitersBlocked -= nWaitersGone;        // something is going on here -
test of timeouts? :-)
    set_event( hevBlockLock );
    nWaitersGone = 0;
  }
  unlock( mtxUnblockLock );

  if ( 1 == nSignalsWasLeft ) {
    if ( 0 != nWaitersWasGone ) {
      reset_event( hevBlockQueue );         // better now than spurious
later
    }
    set_event( hevBlockLock );              // open the gate
  }
  else if ( 0 != nSignalsWasLeft ) {
    set_event( hevBlockQueue );             // unblock next waiter
  }

  lock( mtxExternal );

  return ( bTimedOut ) ? ETIMEOUT : 0;
}

signal(bAll) {

  [auto: register int result ]

  lock( mtxUnblockLock );

  if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
    if ( 0 == nWaitersBlocked ) { // NO-OP
      return unlock( mtxUnblockLock );
    }
    if (bAll) {
      nWaitersToUnblock += nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nWaitersToUnblock++;
      nWaitersBlocked--;
    }
    unlock( mtxUnblockLock );
  }
  else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
    wait( hevBlockLock,INFINITE ); // close the gate
    if ( 0 != nWaitersGone ) {
      nWaitersBlocked -= nWaitersGone;
      nWaitersGone = 0;
    }
    if (bAll) {
      nWaitersToUnblock = nWaitersBlocked;
      nWaitersBlocked = 0;
    }
    else {
      nWaitersToUnblock = 1;
      nWaitersBlocked--;
    }
    unlock( mtxUnblockLock );
    set_event( hevBlockQueue );
  }
  else { // NO-OP
    unlock( mtxUnblockLock );
  }

  return result;
}

---------- Algorithm 8d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
given:
hevBlockLock - auto-reset event
hevBlockQueueS - auto-reset event  // for signals
hevBlockQueueB - manual-reset even // for broadcasts
mtxExternal - mutex or CS
mtxUnblockLock - mutex or CS
eBroadcast - int                   // 0: no broadcast, 1: broadcast, 2:
broadcast after signal(s)
nWaitersGone - int
nWaitersBlocked - int
nWaitersToUnblock - int

wait( timeout ) {

  [auto: register int result          ]     // error checking omitted
  [auto: register int eWasBroadcast   ]
  [auto: register int nSignalsWasLeft ]
  [auto: register int nWaitersWasGone ]

  wait( hevBlockLock,INFINITE );
  nWaitersBlocked++;
  set_event( hevBlockLock );

  unlock( mtxExternal );
  bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE );

  lock( mtxUnblockLock );
  if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
    if ( bTimeout ) {                       // timeout (or canceled)
      if ( 0 != nWaitersBlocked ) {
        nWaitersBlocked--;
        nSignalsWasLeft = 0;                // do not unblock next waiter
below (already unblocked)
      }
      else if ( 1 != eBroadcast ) {
        nWaitersGone = 1;
      }
    }
    if ( 0 == --nWaitersToUnblock ) {
      if ( 0 != nWaitersBlocked ) {
        set_event( hevBlockLock );           // open the gate
        nSignalsWasLeft = 0;                 // do not open the gate below
again
      }
      else {
        if ( 0 != (eWasBroadcast = eBroadcast) ) {
          eBroadcast = 0;
        }
        if ( 0 != (nWaitersWasGone = nWaitersGone ) {
          nWaitersGone = 0;
        }
      }
    }
    else if ( 0 != eBroadcast ) {
      nSignalsWasLeft = 0;                  // do not unblock next waiter
below (already unblocked)
    }
  }
  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
event :-)
    wait( hevBlockLock,INFINITE );
    nWaitersBlocked -= nWaitersGone;        // something is going on here -
test of timeouts? :-)
    set_event( hevBlockLock );
    nWaitersGone = 0;
  }
  unlock( mtxUnblockLock );

  if ( 1 == nSignalsWasLeft ) {
    if ( 0 != eWasBroadcast ) {
      reset_event( hevBlockQueueB );
    }
    if ( 0 != nWaitersWasGone ) {
      reset_event( hevBlockQueueS );        // better now than spurious
later
    }
    set_event( hevBlockLock );              // open the gate
  }
  else if ( 0 != nSignalsWasLeft ) {
    set_event( hevBlockQueueS );            // unblock next waiter
  }

  lock( mtxExternal );

  return ( bTimedOut ) ? ETIMEOUT : 0;
}

signal(bAll) {

  [auto: register int    result        ]
  [auto: register HANDLE hevBlockQueue ]

  lock( mtxUnblockLock );

  if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
    if ( 0 == nWaitersBlocked ) { // NO-OP
      return unlock( mtxUnblockLock );
    }
    if (bAll) {
      nWaitersToUnblock += nWaitersBlocked;
      nWaitersBlocked = 0;
      eBroadcast = 2;
      hevBlockQueue = hevBlockQueueB;
    }
    else {
      nWaitersToUnblock++;
      nWaitersBlocked--;
      return unlock( mtxUnblockLock );
    }
  }
  else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
    wait( hevBlockLock,INFINITE ); // close the gate
    if ( 0 != nWaitersGone ) {
      nWaitersBlocked -= nWaitersGone;
      nWaitersGone = 0;
    }
    if (bAll) {
      nWaitersToUnblock = nWaitersBlocked;
      nWaitersBlocked = 0;
      eBroadcast = 1;
      hevBlockQueue = hevBlockQueueB;
    }
    else {
      nWaitersToUnblock = 1;
      nWaitersBlocked--;
      hevBlockQueue = hevBlockQueueS;
    }
  }
  else { // NO-OP
    return unlock( mtxUnblockLock );
  }

  unlock( mtxUnblockLock );
  set_event( hevBlockQueue );
  return result;
}
---------------------- Forwarded by Alexander Terekhov/Germany/IBM on
02/21/2001 09:13 AM ---------------------------

Alexander Terekhov
02/20/2001 04:33 PM

To:   Louis Thomas <lthomas@arbitrade.com>
cc:

From: Alexander Terekhov/Germany/IBM@IBMDE
Subject:  RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
      n questions
Importance:    Normal

>Sorry, gotta take a break and work on something else for a while.
>Real work
>calls, unfortunately. I'll get back to you in two or three days.

ok. no problem. here is some more stuff for pauses you might have
in between :)

---------- Algorithm 7d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
given:
hevBlockLock - auto-reset event
hevBlockQueueS - auto-reset event  // for signals
hevBlockQueueB - manual-reset even // for broadcasts
mtxExternal - mutex or CS
mtxUnblockLock - mutex or CS
bBroadcast - int
nWaitersGone - int
nWaitersBlocked - int
nWaitersToUnblock - int

wait( timeout ) {

  [auto: register int result          ]     // error checking omitted
  [auto: register int bWasBroadcast   ]
  [auto: register int nSignalsWasLeft ]

  wait( hevBlockLock,INFINITE );
  nWaitersBlocked++;
  set_event( hevBlockLock );

  unlock( mtxExternal );
  bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE );

  lock( mtxUnblockLock );
  if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
    if ( bTimeout ) {                       // timeout (or canceled)
      if ( 0 != nWaitersBlocked ) {
        nWaitersBlocked--;
        nSignalsWasLeft = 0;                // do not unblock next waiter
below (already unblocked)
      }
      else if ( !bBroadcast ) {
        wait( hevBlockQueueS,INFINITE );    // better now than spurious
later
      }
    }
    if ( 0 == --nWaitersToUnblock ) {
      if ( 0 != nWaitersBlocked ) {
        if ( bBroadcast ) {
          reset_event( hevBlockQueueB );
          bBroadcast = false;
        }
        set_event( hevBlockLock );           // open the gate
        nSignalsWasLeft = 0;                 // do not open the gate below
again
      }
      else if ( false != (bWasBroadcast = bBroadcast) ) {
        bBroadcast = false;
      }
    }
    else {
      bWasBroadcast = bBroadcast;
    }
  }
  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
event :-)
    wait( hevBlockLock,INFINITE );
    nWaitersBlocked -= nWaitersGone;        // something is going on here -
test of timeouts? :-)
    set_event( hevBlockLock );
    nWaitersGone = 0;
  }
  unlock( mtxUnblockLock );

  if ( 1 == nSignalsWasLeft ) {
    if ( bWasBroadcast ) {
      reset_event( hevBlockQueueB );
    }
    set_event( hevBlockLock );              // open the gate
  }
  else if ( 0 != nSignalsWasLeft && !bWasBroadcast ) {
    set_event( hevBlockQueueS );            // unblock next waiter
  }

  lock( mtxExternal );

  return ( bTimedOut ) ? ETIMEOUT : 0;
}

signal(bAll) {

  [auto: register int    result        ]
  [auto: register HANDLE hevBlockQueue ]

  lock( mtxUnblockLock );

  if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
    if ( 0 == nWaitersBlocked ) { // NO-OP
      return unlock( mtxUnblockLock );
    }
    if (bAll) {
      nWaitersToUnblock += nWaitersBlocked;
      nWaitersBlocked = 0;
      bBroadcast = true;
      hevBlockQueue = hevBlockQueueB;
    }
    else {
      nWaitersToUnblock++;
      nWaitersBlocked--;
      return unlock( mtxUnblockLock );
    }
  }
  else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
    wait( hevBlockLock,INFINITE ); // close the gate
    if ( 0 != nWaitersGone ) {
      nWaitersBlocked -= nWaitersGone;
      nWaitersGone = 0;
    }
    if (bAll) {
      nWaitersToUnblock = nWaitersBlocked;
      nWaitersBlocked = 0;
      bBroadcast = true;
      hevBlockQueue = hevBlockQueueB;
    }
    else {
      nWaitersToUnblock = 1;
      nWaitersBlocked--;
      hevBlockQueue = hevBlockQueueS;
    }
  }
  else { // NO-OP
    return unlock( mtxUnblockLock );
  }

  unlock( mtxUnblockLock );
  set_event( hevBlockQueue );
  return result;
}


----------------------------------------------------------------------------

Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
     n questions
Date: Mon, 26 Feb 2001 22:20:12 -0600
From: Louis Thomas <lthomas@arbitrade.com>
To: "'TEREKHOV@de.ibm.com'" <TEREKHOV@de.ibm.com>
CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
     Nanbor Wang
     <nanbor@cs.wustl.edu>

Sorry all. Busy week.

> this insures the fairness
> which POSIX does not (e.g. two subsequent broadcasts - the gate does
insure
> that first wave waiters will start the race for the mutex before waiters
> from the second wave - Linux pthreads process/unblock both waves
> concurrently...)

I'm not sure how we are any more fair about this than Linux. We certainly
don't guarantee that the threads released by the first broadcast will get
the external mutex before the threads of the second wave. In fact, it is
possible that those threads will never get the external mutex if there is
enough contention for it.

> e.g. i was thinking about implementation with a pool of
> N semaphores/counters [...]

I considered that too. The problem is as you mentioned in a). You really
need to assign threads to semaphores once you know how you want to wake them
up, not when they first begin waiting which is the only time you can assign
them.

> well, i am not quite sure that i've fully understood your scenario,

Hmm. Well, it think it's an important example, so I'll try again. First, we
have thread A which we KNOW is waiting on a condition. As soon as it becomes
unblocked for any reason, we will know because it will set a flag. Since the
flag is not set, we are 100% confident that thread A is waiting on the
condition. We have another thread, thread B, which has acquired the mutex
and is about to wait on the condition. Thus it is pretty clear that at any
point, either just A is waiting, or A and B are waiting. Now thread C comes
along. C is about to do a broadcast on the condition. A broadcast is
guaranteed to unblock all threads currently waiting on a condition, right?
Again, we said that either just A is waiting, or A and B are both waiting.
So, when C does its broadcast, depending upon whether B has started waiting
or not, thread C will unblock A or unblock A and B. Either way, C must
unblock A, right?

Now, you said anything that happens is correct so long as a) "a signal is
not lost between unlocking the mutex and waiting on the condition" and b) "a
thread must not steal a signal it sent", correct? Requirement b) is easy to
satisfy: in this scenario, thread C will never wait on the condition, so it
won't steal any signals.  Requirement a) is not hard either. The only way we
could fail to meet requirement a) in this scenario is if thread B was
started waiting but didn't wake up because a signal was lost. This will not
happen.

Now, here is what happens. Assume thread C beats thread B. Thread C looks to
see how many threads are waiting on the condition. Thread C sees just one
thread, thread A, waiting. It does a broadcast waking up just one thread
because just one thread is waiting. Next, before A can become unblocked,
thread B begins waiting. Now there are two threads waiting, but only one
will be unblocked. Suppose B wins. B will become unblocked. A will not
become unblocked, because C only unblocked one thread (sema_post cond, 1).
So at the end, B finishes and A remains blocked.

We have met both of your requirements, so by your rules, this is an
acceptable outcome. However, I think that the spec says this is an
unacceptable outcome! We know for certain that A was waiting and that C did
a broadcast, but A did not become unblocked! Yet, the spec says that a
broadcast wakes up all waiting threads. This did not happen. Do you agree
that this shows your rules are not strict enough?

> and what about N2? :) this one does allow almost everything.

Don't get me started about rule #2. I'll NEVER advocate an algorithm that
uses rule 2 as an excuse to suck!

> but it is done (decrement)under mutex protection - this is not a subject
> of a race condition.

You are correct. My mistake.

> i would remove "_bTimedOut=false".. after all, it was a real timeout..

I disagree. A thread that can't successfully retract its waiter status can't
really have timed out. If a thread can't return without executing extra code
to deal with the fact that someone tried to unblock it, I think it is a poor
idea to pretend we
didn't realize someone was trying to signal us. After all, a signal is more
important than a time out.

> when nSignaled != 0, it is possible to update nWaiters (--) and do not
> touch nGone

I realize this, but I was thinking that writing it the other ways saves
another if statement.

> adjust only if nGone != 0 and save one cache memory write - probably much
slower than 'if'

Hmm. You are probably right.

> well, in a strange (e.g. timeout test) program you may (theoretically)
> have an overflow of nWaiters/nGone counters (with waiters repeatedly
timing
> out and no signals at all).

Also true. Not only that, but you also have the possibility that one could
overflow the number of waiters as well! However, considering the limit you
have chosen for nWaitersGone, I suppose it is unlikely that anyone would be
able to get INT_MAX/2 threads waiting on a single condition. :)

Analysis of 8a:

It looks correct to me.

What are IPC semaphores?

In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
because nWaitersGone is never modified without holding mtxUnblockLock. You
are correct that there is a harmless race on nWaitersBlocked, which can
increase and make the condition become true just after we check it. If this
happens, we interpret it as the wait starting after the signal.

I like your optimization of this. You could improve Alg. 6 as follows:
---------- Algorithm 6b ----------
signal(bAll) {
  _nSig=0
  lock counters
  // this is safe because nWaiting can only be decremented by a thread that
  // owns counters and nGone can only be changed by a thread that owns
counters.
  if (nWaiting>nGone) {
    if (0==nSignaled) {
      sema_wait gate // close gate if not already closed
    }
    if (nGone>0) {
      nWaiting-=nGone
      nGone=0
    }
    _nSig=bAll?nWaiting:1
    nSignaled+=_nSig
    nWaiting-=_nSig
  }
  unlock counters
  if (0!=_nSig) {
    sema_post queue, _nSig
  }
}
---------- ---------- ----------
I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings
depending upon whether the gate is open or closed.

In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.

What have you gained by making the last thread to be signaled do the waits
for all the timed out threads, besides added complexity? It took me a long
time to figure out what your objective was with this, to realize you were
using nWaitersGone to mean two different things, and to verify that you
hadn't introduced any bug by doing this. Even now I'm not 100% sure.

What has all this playing about with nWaitersGone really gained us besides a
lot of complexity (it is much harder to verify that this solution is
correct), execution overhead (we now have a lot more if statements to
evaluate), and space overhead (more space for the extra code, and another
integer in our data)? We did manage to save a lock/unlock pair in an
uncommon case (when a time out occurs) at the above mentioned expenses in
the common cases.

As for 8b, c, and d, they look ok though I haven't studied them thoroughly.
What would you use them for?

    Later,
        -Louis! :)

-----------------------------------------------------------------------------

Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
     n questions
Date: Tue, 27 Feb 2001 15:51:28 +0100
From: TEREKHOV@de.ibm.com
To: Louis Thomas <lthomas@arbitrade.com>
CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
     Nanbor Wang <nanbor@cs.wustl.edu>

Hi Louis,

>> that first wave waiters will start the race for the mutex before waiters
>> from the second wave - Linux pthreads process/unblock both waves
>> concurrently...)
>
>I'm not sure how we are any more fair about this than Linux. We certainly
>don't guarantee that the threads released by the first broadcast will get
>the external mutex before the threads of the second wave. In fact, it is
>possible that those threads will never get the external mutex if there is
>enough contention for it.

correct. but gate is nevertheless more fair than Linux because of the
barrier it establishes between two races (1st and 2nd wave waiters) for
the mutex which under 'normal' circumstances (e.g. all threads of equal
priorities,..) will 'probably' result in fair behaviour with respect to
mutex ownership.

>> well, i am not quite sure that i've fully understood your scenario,
>
>Hmm. Well, it think it's an important example, so I'll try again. ...

ok. now i seem to understand this example. well, now it seems to me
that the only meaningful rule is just:

a) "a signal is not lost between unlocking the mutex and waiting on the
condition"

and that the rule

b) "a thread must not steal a signal it sent"

is not needed at all because a thread which violates b) also violates a).

i'll try to explain..

i think that the most important thing is how POSIX defines waiter's
visibility:

"if another thread is able to acquire the mutex after the about-to-block
thread
has released it, then a subsequent call to pthread_cond_signal() or
pthread_cond_broadcast() in that thread behaves as if it were issued after
the about-to-block thread has blocked. "

my understanding is the following:

1) there is no guarantees whatsoever with respect to whether
signal/broadcast
will actually unblock any 'waiter' if it is done w/o acquiring the mutex
first
(note that a thread may release it before signal/broadcast - it does not
matter).

2) it is guaranteed that waiters become 'visible' - eligible for unblock as
soon
as signalling thread acquires the mutex (but not before!!)

so..

>So, when C does its broadcast, depending upon whether B has started
waiting
>or not, thread C will unblock A or unblock A and B. Either way, C must
>unblock A, right?

right. but only if C did acquire the mutex prior to broadcast (it may
release it before broadcast as well).

implementation will violate waiters visibility rule (signal will become
lost)
if C will not unblock A.

>Now, here is what happens. Assume thread C beats thread B. Thread C looks
to
>see how many threads are waiting on the condition. Thread C sees just one
>thread, thread A, waiting. It does a broadcast waking up just one thread
>because just one thread is waiting. Next, before A can become unblocked,
>thread B begins waiting. Now there are two threads waiting, but only one
>will be unblocked. Suppose B wins. B will become unblocked. A will not
>become unblocked, because C only unblocked one thread (sema_post cond, 1).
>So at the end, B finishes and A remains blocked.

thread C did acquire the mutex ("Thread C sees just one thread, thread A,
waiting"). beginning from that moment it is guaranteed that subsequent
broadcast will unblock A. Otherwise we will have a lost signal with respect
to A. I do think that it does not matter whether the signal was physically
(completely) lost or was just stolen by another thread (B) - in both cases
it was simply lost with respect to A.

>..Do you agree that this shows your rules are not strict enough?

probably the opposite.. :-) i think that it shows that the only meaningful
rule is

a) "a signal is not lost between unlocking the mutex and waiting on the
condition"

with clarification of waiters visibility as defined by POSIX above.

>> i would remove "_bTimedOut=false".. after all, it was a real timeout..
>
>I disagree. A thread that can't successfully retract its waiter status
can't
>really have timed out. If a thread can't return without executing extra
code
>to deal with the fact that someone tried to unblock it, I think it is a
poor
>idea to pretend we
>didn't realize someone was trying to signal us. After all, a signal is
more
>important than a time out.

a) POSIX does allow timed out thread to consume a signal (cancelled is
not).
b) ETIMEDOUT status just says that: "The time specified by abstime to
pthread_cond_timedwait() has passed."
c) it seem to me that hiding timeouts would violate "The
pthread_cond_timedwait()
function is the same as pthread_cond_wait() except that an error is
returned if
the absolute time specified by abstime passes (that is, system time equals
or
exceeds abstime) before the condition cond is signaled or broadcasted"
because
the abs. time did really pass before cond was signaled (waiter was
released via semaphore). however, if it really matters, i could imaging
that we
can save an abs. time of signal/broadcast and compare it with timeout after
unblock to find out whether it was a 'real' timeout or not. absent this
check
i do think that hiding timeouts would result in technical violation of
specification.. but i think that this check is not important and we can
simply
trust timeout error code provided by wait since we are not trying to make
'hard' realtime implementation.

>What are IPC semaphores?

<sys/sem.h>
int   semctl(int, int, int, ...);
int   semget(key_t, int, int);
int   semop(int, struct sembuf *, size_t);

they support adjustment of semaphore counter (semvalue)
in one single call - imaging Win32 ReleaseSemaphore( hsem,-N )

>In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
>// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
>because nWaitersGone is never modified without holding mtxUnblockLock. You
>are correct that there is a harmless race on nWaitersBlocked, which can
>increase and make the condition become true just after we check it. If
this
>happens, we interpret it as the wait starting after the signal.

well, the reason why i've asked on comp.programming.threads whether this
race
condition is harmless or not is that in order to be harmless it should not
violate the waiters visibility rule (see above). Fortunately, we increment
the counter under protection of external mutex.. so that any (signalling)
thread which will acquire the mutex next, should see the updated counter
(in signal) according to POSIX memory visibility rules and mutexes
(memory barriers). But i am not so sure how it actually works on
Win32/INTEL
which does not explicitly define any memory visibility rules :(

>I like your optimization of this. You could improve Alg. 6 as follows:
>---------- Algorithm 6b ----------
>signal(bAll) {
>  _nSig=0
>  lock counters
>  // this is safe because nWaiting can only be decremented by a thread
that
>  // owns counters and nGone can only be changed by a thread that owns
>counters.
>  if (nWaiting>nGone) {
>    if (0==nSignaled) {
>      sema_wait gate // close gate if not already closed
>    }
>    if (nGone>0) {
>      nWaiting-=nGone
>      nGone=0
>    }
>    _nSig=bAll?nWaiting:1
>    nSignaled+=_nSig
>    nWaiting-=_nSig
>  }
>  unlock counters
>  if (0!=_nSig) {
>    sema_post queue, _nSig
>  }
>}
>---------- ---------- ----------
>I guess this wouldn't apply to Alg 8a because nWaitersGone changes
meanings
>depending upon whether the gate is open or closed.

agree.

>In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
>semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.

you are correct. my mistake.

>What have you gained by making the last thread to be signaled do the waits
>for all the timed out threads, besides added complexity? It took me a long
>time to figure out what your objective was with this, to realize you were
>using nWaitersGone to mean two different things, and to verify that you
>hadn't introduced any bug by doing this. Even now I'm not 100% sure.
>
>What has all this playing about with nWaitersGone really gained us besides
a
>lot of complexity (it is much harder to verify that this solution is
>correct), execution overhead (we now have a lot more if statements to
>evaluate), and space overhead (more space for the extra code, and another
>integer in our data)? We did manage to save a lock/unlock pair in an
>uncommon case (when a time out occurs) at the above mentioned expenses in
>the common cases.

well, please consider the following:

1) with multiple waiters unblocked (but some timed out) the trick with
counter
seem to ensure potentially higher level of concurrency by not delaying
most of unblocked waiters for semaphore cleanup - only the last one
will be delayed but all others would already contend/acquire/release
the external mutex - the critical section protected by mtxUnblockLock is
made smaller (increment + couple of IFs is faster than system/kernel call)
which i think is good in general. however, you are right, this is done
at expense of 'normal' waiters..

2) some semaphore APIs (e.g. POSIX IPC sems) do allow to adjust the
semaphore counter in one call => less system/kernel calls.. imagine:

if ( 1 == nSignalsWasLeft ) {
    if ( 0 != nWaitersWasGone ) {
      ReleaseSemaphore( semBlockQueue,-nWaitersWasGone );  // better now
than spurious later
    }
    sem_post( semBlockLock );              // open the gate
  }

3) even on win32 a single thread doing multiple cleanup calls (to wait)
will probably result in faster execution (because of processor caching)
than multiple threads each doing a single call to wait.

>As for 8b, c, and d, they look ok though I haven't studied them
thoroughly.
>What would you use them for?

8b) for semaphores which do not allow to unblock multiple waiters
in a single call to post/release (e.g. POSIX realtime semaphores -
<semaphore.h>)

8c/8d) for WinCE prior to 3.0 (WinCE 3.0 does have semaphores)

ok. so, which one is the 'final' algorithm(s) which we should use in
pthreads-win32??

regards,
alexander.

----------------------------------------------------------------------------

Louis Thomas <lthomas@arbitrade.com> on 02/27/2001 05:20:12 AM

Please respond to Louis Thomas <lthomas@arbitrade.com>

To:   Alexander Terekhov/Germany/IBM@IBMDE
cc:   rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, Nanbor Wang
      <nanbor@cs.wustl.edu>
Subject:  RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
      n questions

Sorry all. Busy week.

> this insures the fairness
> which POSIX does not (e.g. two subsequent broadcasts - the gate does
insure
> that first wave waiters will start the race for the mutex before waiters
> from the second wave - Linux pthreads process/unblock both waves
> concurrently...)

I'm not sure how we are any more fair about this than Linux. We certainly
don't guarantee that the threads released by the first broadcast will get
the external mutex before the threads of the second wave. In fact, it is
possible that those threads will never get the external mutex if there is
enough contention for it.

> e.g. i was thinking about implementation with a pool of
> N semaphores/counters [...]

I considered that too. The problem is as you mentioned in a). You really
need to assign threads to semaphores once you know how you want to wake
them
up, not when they first begin waiting which is the only time you can assign
them.

> well, i am not quite sure that i've fully understood your scenario,

Hmm. Well, it think it's an important example, so I'll try again. First, we
have thread A which we KNOW is waiting on a condition. As soon as it
becomes
unblocked for any reason, we will know because it will set a flag. Since
the
flag is not set, we are 100% confident that thread A is waiting on the
condition. We have another thread, thread B, which has acquired the mutex
and is about to wait on the condition. Thus it is pretty clear that at any
point, either just A is waiting, or A and B are waiting. Now thread C comes
along. C is about to do a broadcast on the condition. A broadcast is
guaranteed to unblock all threads currently waiting on a condition, right?
Again, we said that either just A is waiting, or A and B are both waiting.
So, when C does its broadcast, depending upon whether B has started waiting
or not, thread C will unblock A or unblock A and B. Either way, C must
unblock A, right?

Now, you said anything that happens is correct so long as a) "a signal is
not lost between unlocking the mutex and waiting on the condition" and b)
"a
thread must not steal a signal it sent", correct? Requirement b) is easy to
satisfy: in this scenario, thread C will never wait on the condition, so it
won't steal any signals.  Requirement a) is not hard either. The only way
we
could fail to meet requirement a) in this scenario is if thread B was
started waiting but didn't wake up because a signal was lost. This will not
happen.

Now, here is what happens. Assume thread C beats thread B. Thread C looks
to
see how many threads are waiting on the condition. Thread C sees just one
thread, thread A, waiting. It does a broadcast waking up just one thread
because just one thread is waiting. Next, before A can become unblocked,
thread B begins waiting. Now there are two threads waiting, but only one
will be unblocked. Suppose B wins. B will become unblocked. A will not
become unblocked, because C only unblocked one thread (sema_post cond, 1).
So at the end, B finishes and A remains blocked.

We have met both of your requirements, so by your rules, this is an
acceptable outcome. However, I think that the spec says this is an
unacceptable outcome! We know for certain that A was waiting and that C did
a broadcast, but A did not become unblocked! Yet, the spec says that a
broadcast wakes up all waiting threads. This did not happen. Do you agree
that this shows your rules are not strict enough?

> and what about N2? :) this one does allow almost everything.

Don't get me started about rule #2. I'll NEVER advocate an algorithm that
uses rule 2 as an excuse to suck!

> but it is done (decrement)under mutex protection - this is not a subject
> of a race condition.

You are correct. My mistake.

> i would remove "_bTimedOut=false".. after all, it was a real timeout..

I disagree. A thread that can't successfully retract its waiter status
can't
really have timed out. If a thread can't return without executing extra
code
to deal with the fact that someone tried to unblock it, I think it is a
poor
idea to pretend we
didn't realize someone was trying to signal us. After all, a signal is more
important than a time out.

> when nSignaled != 0, it is possible to update nWaiters (--) and do not
> touch nGone

I realize this, but I was thinking that writing it the other ways saves
another if statement.

> adjust only if nGone != 0 and save one cache memory write - probably much
slower than 'if'

Hmm. You are probably right.

> well, in a strange (e.g. timeout test) program you may (theoretically)
> have an overflow of nWaiters/nGone counters (with waiters repeatedly
timing
> out and no signals at all).

Also true. Not only that, but you also have the possibility that one could
overflow the number of waiters as well! However, considering the limit you
have chosen for nWaitersGone, I suppose it is unlikely that anyone would be
able to get INT_MAX/2 threads waiting on a single condition. :)

Analysis of 8a:

It looks correct to me.

What are IPC semaphores?

In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
because nWaitersGone is never modified without holding mtxUnblockLock. You
are correct that there is a harmless race on nWaitersBlocked, which can
increase and make the condition become true just after we check it. If this
happens, we interpret it as the wait starting after the signal.

I like your optimization of this. You could improve Alg. 6 as follows:
---------- Algorithm 6b ----------
signal(bAll) {
  _nSig=0
  lock counters
  // this is safe because nWaiting can only be decremented by a thread that
  // owns counters and nGone can only be changed by a thread that owns
counters.
  if (nWaiting>nGone) {
    if (0==nSignaled) {
      sema_wait gate // close gate if not already closed
    }
    if (nGone>0) {
      nWaiting-=nGone
      nGone=0
    }
    _nSig=bAll?nWaiting:1
    nSignaled+=_nSig
    nWaiting-=_nSig
  }
  unlock counters
  if (0!=_nSig) {
    sema_post queue, _nSig
  }
}
---------- ---------- ----------
I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings
depending upon whether the gate is open or closed.

In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.

What have you gained by making the last thread to be signaled do the waits
for all the timed out threads, besides added complexity? It took me a long
time to figure out what your objective was with this, to realize you were
using nWaitersGone to mean two different things, and to verify that you
hadn't introduced any bug by doing this. Even now I'm not 100% sure.

What has all this playing about with nWaitersGone really gained us besides
a
lot of complexity (it is much harder to verify that this solution is
correct), execution overhead (we now have a lot more if statements to
evaluate), and space overhead (more space for the extra code, and another
integer in our data)? We did manage to save a lock/unlock pair in an
uncommon case (when a time out occurs) at the above mentioned expenses in
the common cases.

As for 8b, c, and d, they look ok though I haven't studied them thoroughly.
What would you use them for?

    Later,
        -Louis! :)

This file documents non-portable functions and other issues.

Non-portable functions included in pthreads-win32
-------------------------------------------------

BOOL
pthread_win32_test_features_np(int mask)

	This routine allows an application to check which
	run-time auto-detected features are available within
	the library.

	The possible features are:

		PTW32_SYSTEM_INTERLOCKED_COMPARE_EXCHANGE
			Return TRUE if the native version of
			InterlockedCompareExchange() is being used.
			This feature is not meaningful in recent
			library versions as MSVC builds only support
			system implemented ICE. Note that all Mingw
			builds use inlined asm versions of all the
			Interlocked routines.
		PTW32_ALERTABLE_ASYNC_CANCEL
			Return TRUE is the QueueUserAPCEx package
			QUSEREX.DLL is available and the AlertDrv.sys
			driver is loaded into Windows, providing
			alertable (pre-emptive) asyncronous threads
			cancelation. If this feature returns FALSE
			then the default async cancel scheme is in
			use, which cannot cancel blocked threads.

	Features may be Or'ed into the mask parameter, in which case
	the routine returns TRUE if any of the Or'ed features would
	return TRUE. At this stage it doesn't make sense to Or features
	but it may some day.


void *
pthread_timechange_handler_np(void *)

        To improve tolerance against operator or time service
        initiated system clock changes.

        This routine can be called by an application when it
        receives a WM_TIMECHANGE message from the system. At
        present it broadcasts all condition variables so that
        waiting threads can wake up and re-evaluate their
        conditions and restart their timed waits if required.

        It has the same return type and argument type as a
        thread routine so that it may be called directly
        through pthread_create(), i.e. as a separate thread.

        Parameters

        Although a parameter must be supplied, it is ignored.
        The value NULL can be used.

        Return values

        It can return an error EAGAIN to indicate that not
        all condition variables were broadcast for some reason.
        Otherwise, 0 is returned.

        If run as a thread, the return value is returned
        through pthread_join().

        The return value should be cast to an integer.


HANDLE
pthread_getw32threadhandle_np(pthread_t thread);

	Returns the win32 thread handle that the POSIX
	thread "thread" is running as.

	Applications can use the win32 handle to set
	win32 specific attributes of the thread.

DWORD
pthread_getw32threadid_np (pthread_t thread)

	Returns the Windows native thread ID that the POSIX
	thread "thread" is running as.

        Only valid when the library is built where
        ! (defined(__MINGW64__) || defined(__MINGW32__)) || defined (__MSVCRT__) || defined (__DMC__)
        and otherwise returns 0.


int
pthread_mutexattr_setkind_np(pthread_mutexattr_t * attr, int kind)

int
pthread_mutexattr_getkind_np(pthread_mutexattr_t * attr, int *kind)

        These two routines are included for Linux compatibility
        and are direct equivalents to the standard routines
                pthread_mutexattr_settype
                pthread_mutexattr_gettype

        pthread_mutexattr_setkind_np accepts the following
        mutex kinds:
                PTHREAD_MUTEX_FAST_NP
                PTHREAD_MUTEX_ERRORCHECK_NP
                PTHREAD_MUTEX_RECURSIVE_NP

        These are really just equivalent to (respectively):
                PTHREAD_MUTEX_NORMAL
                PTHREAD_MUTEX_ERRORCHECK
                PTHREAD_MUTEX_RECURSIVE

int
pthread_delay_np (const struct timespec *interval);

        This routine causes a thread to delay execution for a specific period of time.
        This period ends at the current time plus the specified interval. The routine
        will not return before the end of the period is reached, but may return an
        arbitrary amount of time after the period has gone by. This can be due to
        system load, thread priorities, and system timer granularity.

        Specifying an interval of zero (0) seconds and zero (0) nanoseconds is
        allowed and can be used to force the thread to give up the processor or to
        deliver a pending cancelation request.

        This routine is a cancelation point.

        The timespec structure contains the following two fields:

                tv_sec is an integer number of seconds.
                tv_nsec is an integer number of nanoseconds.

        Return Values

        If an error condition occurs, this routine returns an integer value
        indicating the type of error. Possible return values are as follows:

        0          Successful completion.
        [EINVAL]   The value specified by interval is invalid.

int
pthread_num_processors_np (void)

        This routine (found on HPUX systems) returns the number of processors
        in the system. This implementation actually returns the number of
        processors available to the process, which can be a lower number
        than the system's number, depending on the process's affinity mask.

BOOL
pthread_win32_process_attach_np (void);

BOOL
pthread_win32_process_detach_np (void);

BOOL
pthread_win32_thread_attach_np (void);

BOOL
pthread_win32_thread_detach_np (void);

	These functions contain the code normally run via dllMain
	when the library is used as a dll but which need to be
	called explicitly by an application when the library
	is statically linked. As of version 2.9.0 of the library, static
	builds using either MSC or GCC will call pthread_win32_process_*
	automatically at application startup and exit respectively.

	Otherwise, you will need to call pthread_win32_process_attach_np()
	before you can call any pthread routines when statically linking.
	You should call pthread_win32_process_detach_np() before
	exiting your application to clean up.

	pthread_win32_thread_attach_np() is currently a no-op, but
	pthread_win32_thread_detach_np() is needed to clean up
	the implicit pthread handle that is allocated to a Win32 thread if
	it calls any pthreads routines. Call this routine when the
	Win32 thread exits.

	Threads created through pthread_create() do not	need to call
	pthread_win32_thread_detach_np().

	These functions invariably return TRUE except for
	pthread_win32_process_attach_np() which will return FALSE
	if pthreads-win32 initialisation fails.

int
pthreadCancelableWait (HANDLE waitHandle);

int
pthreadCancelableTimedWait (HANDLE waitHandle, DWORD timeout);

	These two functions provide hooks into the pthread_cancel
	mechanism that will allow you to wait on a Windows handle
	and make it a cancellation point. Both functions block
	until either the given w32 handle is signaled, or
	pthread_cancel has been called. It is implemented using
	WaitForMultipleObjects on 'waitHandle' and a manually
	reset w32 event used to implement pthread_cancel.


Non-portable issues
-------------------

Thread priority

	POSIX defines a single contiguous range of numbers that determine a
	thread's priority. Win32 defines priority classes and priority
	levels relative to these classes. Classes are simply priority base
	levels that the defined priority levels are relative to such that,
	changing a process's priority class will change the priority of all
	of it's threads, while the threads retain the same relativity to each
	other.

	A Win32 system defines a single contiguous monotonic range of values
	that define system priority levels, just like POSIX. However, Win32
	restricts individual threads to a subset of this range on a
	per-process basis.

	The following table shows the base priority levels for combinations
	of priority class and priority value in Win32.

	 Process Priority Class               Thread Priority Level
	 -----------------------------------------------------------------
	 1 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_IDLE
	 1 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_IDLE
	 1 NORMAL_PRIORITY_CLASS              THREAD_PRIORITY_IDLE
	 1 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_IDLE
	 1 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_IDLE
	 2 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_LOWEST
	 3 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_BELOW_NORMAL
	 4 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_NORMAL
	 4 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_LOWEST
	 5 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_ABOVE_NORMAL
	 5 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_BELOW_NORMAL
	 5 Background NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_LOWEST
	 6 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_HIGHEST
	 6 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_NORMAL
	 6 Background NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_BELOW_NORMAL
	 7 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_ABOVE_NORMAL
	 7 Background NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_NORMAL
	 7 Foreground NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_LOWEST
 	 8 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_HIGHEST
	 8 NORMAL_PRIORITY_CLASS              THREAD_PRIORITY_ABOVE_NORMAL
	 8 Foreground NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_BELOW_NORMAL
	 8 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_LOWEST
	 9 NORMAL_PRIORITY_CLASS              THREAD_PRIORITY_HIGHEST
	 9 Foreground NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_NORMAL
	 9 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_BELOW_NORMAL
	10 Foreground NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_ABOVE_NORMAL
	10 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_NORMAL
	11 Foreground NORMAL_PRIORITY_CLASS   THREAD_PRIORITY_HIGHEST
	11 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_ABOVE_NORMAL
	11 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_LOWEST
	12 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_HIGHEST
	12 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_BELOW_NORMAL
	13 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_NORMAL
	14 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_ABOVE_NORMAL
	15 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_HIGHEST
	15 HIGH_PRIORITY_CLASS                THREAD_PRIORITY_TIME_CRITICAL
	15 IDLE_PRIORITY_CLASS                THREAD_PRIORITY_TIME_CRITICAL
	15 BELOW_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_TIME_CRITICAL
	15 NORMAL_PRIORITY_CLASS              THREAD_PRIORITY_TIME_CRITICAL
	15 ABOVE_NORMAL_PRIORITY_CLASS        THREAD_PRIORITY_TIME_CRITICAL
	16 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_IDLE
	17 REALTIME_PRIORITY_CLASS            -7
	18 REALTIME_PRIORITY_CLASS            -6
	19 REALTIME_PRIORITY_CLASS            -5
	20 REALTIME_PRIORITY_CLASS            -4
	21 REALTIME_PRIORITY_CLASS            -3
	22 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_LOWEST
	23 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_BELOW_NORMAL
	24 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_NORMAL
	25 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_ABOVE_NORMAL
	26 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_HIGHEST
	27 REALTIME_PRIORITY_CLASS             3
	28 REALTIME_PRIORITY_CLASS             4
	29 REALTIME_PRIORITY_CLASS             5
	30 REALTIME_PRIORITY_CLASS             6
	31 REALTIME_PRIORITY_CLASS            THREAD_PRIORITY_TIME_CRITICAL

	Windows NT:  Values -7, -6, -5, -4, -3, 3, 4, 5, and 6 are not supported.


	As you can see, the real priority levels available to any individual
	Win32 thread are non-contiguous.

	An application using pthreads-win32 should not make assumptions about
	the numbers used to represent thread priority levels, except that they
	are monotonic between the values returned by sched_get_priority_min()
	and sched_get_priority_max(). E.g. Windows 95, 98, NT, 2000, XP make
	available a non-contiguous range of numbers between -15 and 15, while
	at least one version of WinCE (3.0) defines the minimum priority
	(THREAD_PRIORITY_LOWEST) as 5, and the maximum priority
	(THREAD_PRIORITY_HIGHEST) as 1.

	Internally, pthreads-win32 maps any priority levels between
	THREAD_PRIORITY_IDLE and THREAD_PRIORITY_LOWEST to THREAD_PRIORITY_LOWEST,
	or between THREAD_PRIORITY_TIME_CRITICAL and THREAD_PRIORITY_HIGHEST to
	THREAD_PRIORITY_HIGHEST. Currently, this also applies to
	REALTIME_PRIORITY_CLASSi even if levels -7, -6, -5, -4, -3, 3, 4, 5, and 6
	are supported.

	If it wishes, a Win32 application using pthreads-win32 can use the Win32
	defined priority macros THREAD_PRIORITY_IDLE through
	THREAD_PRIORITY_TIME_CRITICAL.


The opacity of the pthread_t datatype
-------------------------------------
and possible solutions for portable null/compare/hash, etc
----------------------------------------------------------

Because pthread_t is an opague datatype an implementation is permitted to define
pthread_t in any way it wishes. That includes defining some bits, if it is
scalar, or members, if it is an aggregate, to store information that may be
extra to the unique identifying value of the ID. As a result, pthread_t values
may not be directly comparable.

If you want your code to be portable you must adhere to the following contraints:

1) Don't assume it is a scalar data type, e.g. an integer or pointer value. There
are several other implementations where pthread_t is also a struct. See our FAQ
Question 11 for our reasons for defining pthread_t as a struct.

2) You must not compare them using relational or equality operators. You must use
the API function pthread_equal() to test for equality.

3) Never attempt to reference individual members.


The problem

Certain applications would like to be able to access only the 'pure' pthread_t
id values, primarily to use as keys into data structures to manage threads or
thread-related data, but this is not possible in a maximally portable and
standards compliant way for current POSIX threads implementations.

For implementations that define pthread_t as a scalar, programmers often employ
direct relational and equality operators on pthread_t. This code will break when
ported to an implementation that defines pthread_t as an aggregate type.

For implementations that define pthread_t as an aggregate, e.g. a struct,
programmers can use memcmp etc., but then face the prospect that the struct may
include alignment padding bytes or bits as well as extra implementation-specific
members that are not part of the unique identifying value.

[While this is not currently the case for pthreads-win32, opacity also
means that an implementation is free to change the definition, which should
generally only require that applications be recompiled and relinked, not
rewritten.]


Doesn't the compiler take care of padding?

The C89 and later standards only effectively guarrantee element-by-element
equivalence following an assignment or pass by value of a struct or union,
therefore undefined areas of any two otherwise equivalent pthread_t instances
can still compare differently, e.g. attempting to compare two such pthread_t
variables byte-by-byte, e.g. memcmp(&t1, &t2, sizeof(pthread_t) may give an
incorrect result. In practice I'm reasonably confident that compilers routinely
also copy the padding bytes, mainly because assignment of unions would be far
too complicated otherwise. But it just isn't guarranteed by the standard.

Illustration:

We have two thread IDs t1 and t2

pthread_t t1, t2;

In an application we create the threads and intend to store the thread IDs in an
ordered data structure (linked list, tree, etc) so we need to be able to compare
them in order to insert them initially and also to traverse.

Suppose pthread_t contains undefined padding bits and our compiler copies our
pthread_t [struct] element-by-element, then for the assignment:

pthread_t temp = t1;

temp and t1 will be equivalent and correct but a byte-for-byte comparison such as
memcmp(&temp, &t1, sizeof(pthread_t)) == 0 may not return true as we expect because
the undefined bits may not have the same values in the two variable instances.

Similarly if passing by value under the same conditions.

If, on the other hand, the undefined bits are at least constant through every
assignment and pass-by-value then the byte-for-byte comparison
memcmp(&temp, &t1, sizeof(pthread_t)) == 0 will always return the expected result.
How can we force the behaviour we need?


Solutions

Adding new functions to the standard API or as non-portable extentions is
the only reliable and portable way to provide the necessary operations.
Remember also that POSIX is not tied to the C language. The most common
functions that have been suggested are:

pthread_null()
pthread_compare()
pthread_hash()

A single more general purpose function could also be defined as a
basis for at least the last two of the above functions.

First we need to list the freedoms and constraints with restpect
to pthread_t so that we can be sure our solution is compatible with the
standard.

What is known or may be deduced from the standard:
1) pthread_t must be able to be passed by value, so it must be a single object.
2) from (1) it must be copyable so cannot embed thread-state information, locks
or other volatile objects required to manage the thread it associates with.
3) pthread_t may carry additional information, e.g. for debugging or to manage
itself.
4) there is an implicit requirement that the size of pthread_t is determinable
at compile-time and size-invariant, because it must be able to copy the object
(i.e. through assignment and pass-by-value). Such copies must be genuine
duplicates, not merely a copy of a pointer to a common instance such as
would be the case if pthread_t were defined as an array.


Suppose we define the following function:

/* This function shall return it's argument */
pthread_t* pthread_normalize(pthread_t* thread);

For scalar or aggregate pthread_t types this function would simply zero any bits
within the pthread_t that don't uniquely identify the thread, including padding,
such that client code can return consistent results from operations done on the
result. If the additional bits are a pointer to an associate structure then
this function would ensure that the memory used to store that associate
structure does not leak. After normalization the following compare would be
valid and repeatable:

memcmp(pthread_normalize(&t1),pthread_normalize(&t2),sizeof(pthread_t))

Note 1: such comparisons are intended merely to order and sort pthread_t values
and allow them to index various data structures. They are not intended to reveal
anything about the relationships between threads, like startup order.

Note 2: the normalized pthread_t is also a valid pthread_t that uniquely
identifies the same thread.

Advantages:
1) In most existing implementations this function would reduce to a no-op that
emits no additional instructions, i.e after in-lining or optimisation, or if
defined as a macro:
#define pthread_normalise(tptr) (tptr)

2) This single function allows an application to portably derive
application-level versions of any of the other required functions.

3) It is a generic function that could enable unanticipated uses.

Disadvantages:
1) Less efficient than dedicated compare or hash functions for implementations
that include significant extra non-id elements in pthread_t.

2) Still need to be concerned about padding if copying normalized pthread_t.
See the later section on defining pthread_t to neutralise padding issues.

Generally a pthread_t may need to be normalized every time it is used,
which could have a significant impact. However, this is a design decision
for the implementor in a competitive environment. An implementation is free
to define a pthread_t in a way that minimises or eliminates padding or
renders this function a no-op.

Hazards:
1) Pass-by-reference directly modifies 'thread' so the application must
synchronise access or ensure that the pointer refers to a copy. The alternative
of pass-by-value/return-by-value was considered but then this requires two copy
operations, disadvantaging implementations where this function is not a no-op
in terms of speed of execution. This function is intended to be used in high
frequency situations and needs to be efficient, or at least not unnecessarily
inefficient. The alternative also sits awkwardly with functions like memcmp.

2) [Non-compliant] code that uses relational and equality operators on
arithmetic or pointer style pthread_t types would need to be rewritten, but it
should be rewritten anyway.


C implementation of null/compare/hash functions using pthread_normalize():

/* In pthread.h */
pthread_t* pthread_normalize(pthread_t* thread);

/* In user code */
/* User-level bitclear function - clear bits in loc corresponding to mask */
void* bitclear (void* loc, void* mask, size_t count);

typedef unsigned int hash_t;

/* User-level hash function */
hash_t hash(void* ptr, size_t count);

/*
 * User-level pthr_null function - modifies the origin thread handle.
 * The concept of a null pthread_t is highly implementation dependent
 * and this design may be far from the mark. For example, in an
 * implementation "null" may mean setting a special value inside one
 * element of pthread_t to mean "INVALID". However, if that value was zero and
 * formed part of the id component then we may get away with this design.
 */
pthread_t* pthr_null(pthread_t* tp)
{
  /*
   * This should have the same effect as memset(tp, 0, sizeof(pthread_t))
   * We're just showing that we can do it.
   */
  void* p = (void*) pthread_normalize(tp);
  return (pthread_t*) bitclear(p, p, sizeof(pthread_t));
}

/*
 * Safe user-level pthr_compare function - modifies temporary thread handle copies
 */
int pthr_compare_safe(pthread_t thread1, pthread_t thread2)
{
  return memcmp(pthread_normalize(&thread1), pthread_normalize(&thread2), sizeof(pthread_t));
}

/*
 * Fast user-level pthr_compare function - modifies origin thread handles
 */
int pthr_compare_fast(pthread_t* thread1, pthread_t* thread2)
{
  return memcmp(pthread_normalize(&thread1), pthread_normalize(&thread2), sizeof(pthread_t));
}

/*
 * Safe user-level pthr_hash function - modifies temporary thread handle copy
 */
hash_t pthr_hash_safe(pthread_t thread)
{
  return hash((void *) pthread_normalize(&thread), sizeof(pthread_t));
}

/*
 * Fast user-level pthr_hash function - modifies origin thread handle
 */
hash_t pthr_hash_fast(pthread_t thread)
{
  return hash((void *) pthread_normalize(&thread), sizeof(pthread_t));
}

/* User-level bitclear function - modifies the origin array */
void* bitclear(void* loc, void* mask, size_t count)
{
  int i;
  for (i=0; i < count; i++) {
    (unsigned char) *loc++ &= ~((unsigned char) *mask++);
  }
}

/* Donald Knuth hash */
hash_t hash(void* str, size_t count)
{
   hash_t hash = (hash_t) count;
   unsigned int i = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
   }
   return hash;
}

/* Example of advantage point (3) - split a thread handle into its id and non-id values */
pthread_t id = thread, non-id = thread;
bitclear((void*) &non-id, (void*) pthread_normalize(&id), sizeof(pthread_t));


A pthread_t type change proposal to neutralise the effects of padding

Even if pthread_nornalize() is available, padding is still a problem because
the standard only garrantees element-by-element equivalence through
copy operations (assignment and pass-by-value). So padding bit values can
still change randomly after calls to pthread_normalize().

[I suspect that most compilers take the easy path and always byte-copy anyway,
partly because it becomes too complex to do (e.g. unions that contain sub-aggregates)
but also because programmers can easily design their aggregates to minimise and
often eliminate padding].

How can we eliminate the problem of padding bytes in structs? Could
defining pthread_t as a union rather than a struct provide a solution?

In fact, the Linux pthread.h defines most of it's pthread_*_t objects (but not
pthread_t itself) as unions, possibly for this and/or other reasons. We'll
borrow some element naming from there but the ideas themselves are well known
- the __align element used to force alignment of the union comes from K&R's
storage allocator example.

/* Essentially our current pthread_t renamed */
typedef struct {
  struct thread_state_t * __p;
  long __x; /* sequence counter */
} thread_id_t;

Ensuring that the last element in the above struct is a long ensures that the
overall struct size is a multiple of sizeof(long), so there should be no trailing
padding in this struct or the union we define below.
(Later we'll see that we can handle internal but not trailing padding.)

/* New pthread_t */
typedef union {
  char __size[sizeof(thread_id_t)]; /* array as the first element */
  thread_id_t __tid;
  long __align;  /* Ensure that the union starts on long boundary */
} pthread_t;

This guarrantees that, during an assignment or pass-by-value, the compiler copies
every byte in our thread_id_t because the compiler guarrantees that the __size
array, which we have ensured is the equal-largest element in the union, retains
equivalence.

This means that pthread_t values stored, assigned and passed by value will at least
carry the value of any undefined padding bytes along and therefore ensure that
those values remain consistent. Our comparisons will return consistent results and
our hashes of [zero initialised] pthread_t values will also return consistent
results.

We have also removed the need for a pthread_null() function; we can initialise
at declaration time or easily create our own const pthread_t to use in assignments
later:

const pthread_t null_tid = {0}; /* braces are required */

pthread_t t;
...
t = null_tid;


Note that we don't have to explicitly make use of the __size array at all. It's
there just to force the compiler behaviour we want.


Partial solutions without a pthread_normalize function


An application-level pthread_null and pthread_compare proposal
(and pthread_hash proposal by extention)

In order to deal with the problem of scalar/aggregate pthread_t type disparity in
portable code I suggest using an old-fashioned union, e.g.:

Contraints:
- there is no padding, or padding values are preserved through assignment and
  pass-by-value (see above);
- there are no extra non-id values in the pthread_t.


Example 1: A null initialiser for pthread_t variables...

typedef union {
    unsigned char b[sizeof(pthread_t)];
    pthread_t t;
} init_t;

const init_t initial = {0};

pthread_t tid = initial.t; /* init tid to all zeroes */


Example 2: A comparison function for pthread_t values

typedef union {
   unsigned char b[sizeof(pthread_t)];
   pthread_t t;
} pthcmp_t;

int pthcmp(pthread_t left, pthread_t right)
{
  /*
  * Compare two pthread handles in a way that imposes a repeatable but arbitrary
  * ordering on them.
  * I.e. given the same set of pthread_t handles the ordering should be the same
  * each time but the order has no particular meaning other than that. E.g.
  * the ordering does not imply the thread start sequence, or any other
  * relationship between threads.
  *
  * Return values are:
  * 1 : left is greater than right
  * 0 : left is equal to right
  * -1 : left is less than right
  */
  int i;
  pthcmp_t L, R;
  L.t = left;
  R.t = right;
  for (i = 0; i < sizeof(pthread_t); i++)
  {
    if (L.b[i] > R.b[i])
      return 1;
    else if (L.b[i] < R.b[i])
      return -1;
  }
  return 0;
}

It has been pointed out that the C99 standard allows for the possibility that
integer types also may include padding bits, which could invalidate the above
method. This addition to C99 was specifically included after it was pointed
out that there was one, presumably not particularly well known, architecture
that included a padding bit in it's 32 bit integer type. See section 6.2.6.2
of both the standard and the rationale, specifically the paragraph starting at
line 16 on page 43 of the rationale.


An aside

Certain compilers, e.g. gcc and one of the IBM compilers, include a feature
extention: provided the union contains a member of the same type as the
object then the object may be cast to the union itself.

We could use this feature to speed up the pthrcmp() function from example 2
above by casting rather than assigning the pthread_t arguments to the union, e.g.:

int pthcmp(pthread_t left, pthread_t right)
{
  /*
  * Compare two pthread handles in a way that imposes a repeatable but arbitrary
  * ordering on them.
  * I.e. given the same set of pthread_t handles the ordering should be the same
  * each time but the order has no particular meaning other than that. E.g.
  * the ordering does not imply the thread start sequence, or any other
  * relationship between threads.
  *
  * Return values are:
  * 1 : left is greater than right
  * 0 : left is equal to right
  * -1 : left is less than right
  */
  int i;
  for (i = 0; i < sizeof(pthread_t); i++)
  {
    if (((pthcmp_t)left).b[i] > ((pthcmp_t)right).b[i])
      return 1;
    else if (((pthcmp_t)left).b[i] < ((pthcmp_t)right).b[i])
      return -1;
  }
  return 0;
}


Result thus far

We can't remove undefined bits if they are there in pthread_t already, but we have
attempted to render them inert for comparison and hashing functions by making them
consistent through assignment, copy and pass-by-value.

Note: Hashing pthread_t values requires that all pthread_t variables be initialised
to the same value (usually all zeros) before being assigned a proper thread ID, i.e.
to ensure that any padding bits are zero, or at least the same value for all
pthread_t. Since all pthread_t values are generated by the library in the first
instance this need not be an application-level operation.


Conclusion

I've attempted to resolve the multiple issues of type opacity and the possible
presence of undefined bits and bytes in pthread_t values, which prevent
applications from comparing or hashing pthread handles.

Two complimentary partial solutions have been proposed, one an application-level
scheme to handle both scalar and aggregate pthread_t types equally, plus a
definition of pthread_t itself that neutralises padding bits and bytes by
coercing semantics out of the compiler to eliminate variations in the values of
padding bits.

I have not provided any solution to the problem of handling extra values embedded
in pthread_t, e.g. debugging or trap information that an implementation is entitled
to include. Therefore none of this replaces the portability and flexibility of API
functions but what functions are needed? The threads standard is unlikely to
include that can be implemented by a combination of existing features and more
generic functions (several references in the threads rationale suggest this.
Therefore I propose that the following function could replace the several functions
that have been suggested in conversations:

pthread_t * pthread_normalize(pthread_t * handle);

For most existing pthreads implementations this function, or macro, would reduce to
a no-op with zero call overhead.

Watcom compiler notes
=====================

Status
------
Not yet usable. Although the library builds under Watcom it
substantially fails the test suite.

There is a working Wmakefile for wmake for the library build.

invoke as any of:
wmake -f Wmakefile clean WC
wmake -f Wmakefile clean WC-inlined
wmake -f Wmakefile clean WCE
wmake -f Wmakefile clean WCE-inlined

These build pthreadWC.dll and pthreadWCE.dll.

There is a working Wmakefile for wmake for the test suite.

invoke as any of:
wmake -f Wmakefile clean WC
wmake -f Wmakefile clean WCX
wmake -f Wmakefile clean WCE
wmake -f Wmakefile clean WC-bench
wmake -f Wmakefile clean WCX-bench
wmake -f Wmakefile clean WCE-bench


Current known problems
----------------------

Library build:
The Watcom compiler uses a different default call convention to MS C or GNU C and so
applications are not compatible with pthreadVC.dll etc using pre 2003-10-14 versions
of pthread.h, sched.h, or semaphore.h. The cdecl attribute can be used on exposed
function prototypes to force compatibility with MS C built DLLs.

However, there appear to be other incompatibilities. Errno.h, for example, defines
different values for the standard C and POSIX errors to those defined by the MS C
errno.h. It may be that references to Watcom's threads compatible 'errno' do set
and return translated numbers consistently, but I have not verified this.

Watcom defines errno as a dereferenced pointer returned by the function
_get_errno_ptr(). This is similar to both the MS and GNU C environments for
multithreaded use. However, the Watcom version appears to have a number of problems:

- different threads return the same pointer value. Compare with the MS and GNU C
versions which correctly return different values (since each thread must maintain
a thread specific errno value).

- an errno value set within the DLL appears as zero in the application even though
both share the same thread.

Therefore applications built using the Watcom compiler may need to use
a Watcom built version of the library (pthreadWC.dll). If this is the case, then
the cdecl function attribute should not be required.

Application builds:
The test suite fails with the Watcom compiler.

Test semaphore1.c fails for pthreadWC.dll because errno returns 0 instead of EAGAIN.

WinCE port
----------
(See the file WinCE-PORT for a detailed explanation.)

Make sure you define "WINCE" amongst your compiler flags (eg. -DWINCE).
The config.h file will define all the necessary defines for you.