[boost] Lightweight Mutex Code

From: Tyson Whitehead (twhitehe_at_[hidden])
Date: 2004-07-02 16:48:27

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I believe there is a mistake in the 'details/lwm_gcc.hpp' and 
'details/lwm_linux.hpp' (and possibly the other lightweight_mutex 
implementation as well -- I haven't looked at them).

In both of these files we have a counter (m_.a_) that is initialized to 1.  
The lock routine is implemented as follows:

while( !__exchange_and_add(&m_.a_, -1) ){
  __atomic_add(&m_.a_, 1);
  sched_yield();
}

The unlock as:
__atomic_add(&m_.a_, 1);

This works if there are only two contenders for the lock.  It can fail if 
there are three or more:

1-  Thread one takes the lock, putting the counter at 0.
2-  Thread two does the __exchange_and_add, fails the test, and then its time 
time slice expires before the __atomic_add, leaving the counter at -1.
3-  Thread three also takes the lock (because !-1 is false).

A simple solution is to initialize the counter to zero and replace the above 
lock by:

while( __exchange_and_add(&m_.a_, 1) ){
  __atomic_add(&m_.a_, -1);
  sched_yield();
}

and the unlock by:
__atomic_add(&m_.a_, -1);

This would result in:
1-  Thread one takes the lock, putting the counter at 1.
2-  Thread two does the __exchange_and_add, fails the test, and then its time 
slice expires before it can do the __atomic_add, leaving the counter at 2.
3-  Thread cannot take the the lock (because 2 is true).

- -T

- -- 
 Tyson Whitehead  (-twhitehe_at_[hidden] -- WSC-)
 Computer Engineer                        Dept. of Applied Mathematics,
 Graduate Student- Applied Mathematics    University of Western Ontario,
 GnuPG Key ID# 0x8A2AB5D8                 London, Ontario, Canada
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA5dgwRXbLmIoqtdgRAmbyAJ0aZFZvxn5MXeXyNqSAI63o9EqddQCfTK9p
wFAoBbQueoo9hLNhXJtit44=
=SPra
-----END PGP SIGNATURE-----