Boost logo

Boost :

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2002-05-25 12:11:31


"William E. Kempf" wrote:
[...]
> However,
> there are issues of performance that may be important enough to add the
> samaphore back.

----
<thp_at_[hidden]> wrote in message news:aclefi$ovm$2_at_glue.ucr.edu...
> In comp.programming.threads Slava M. Usov <stripit.slough_at_[hidden]> wrote:
[...]
> : I cannot agree more.
>
> Cool!!  ;-)
I do not argue with the obvious.
[...]
> Basically, a semaphore IS a special monitor.  It needs a lock to
> protect its data from concurrent access.  That lock is almost always
> of low-level (e.g., a spinlock or locking based on blockage of
> interrupts and other CPUs).  If we use the same kind of mutex with
> conditions, we get the same overhead, i.e., the same number of context
> switches, for signalling.
No. In win32, semaphores are kernel mode objects. There is one single KM
transition to increment semaphore count, and there is one single KM
transition to wait on semaphore. All locking/signaling is done by the
scheduler efficiently, i.e., there are no context switches between signaling
and unlocking. Contrast that with a monitor:
Thread A that waits on the monitor:
1. KM transition to acquire the lock [may be avoided if there is no
contention]
2. KM transition to release the lock [may be avoided if there is no
contention]
3. KM transition to wait [may be avoided if the semaphore > 0]
4. A context switch [may be avoided if the signaler has higher priority]
5. KM transition to acquire the lock [may be avoided ... ] and a context
switch which is an inversion of the switch at the previous step [may be
avoided]
6. KM transition to release the lock [may be avoided ... ]
Thread B that signals the monitor:
1. KM transition to acquire the lock [may be avoided if there is no
contention]
2. KM transition to signal [may be avoided in certain cases]
3. Two context switches [may be avoided if the signaler has higher priority]
4. KM transition to release the lock [may be avoided ... ]
There is another context switch which is present in the "win32 semaphore"
case. So we have two unnecessary context switches plus lots of KM
transitions which are not free. Granted, many of the KM transitions may be
avoided and there is non-zero probability both the signaler and the signalee
may pass the monitor without a single KM transition and without a single
context switch, while in win32 two KM transitions are mandatory. But it is
best that the programmer decide which of these two will suit his needs
better on per-case basis. I do not believe in one-size-fits-all type of
thing here.
Finally, all of this is moot when threads are user mode threads, which is
_the_ real win-win case provided there is some kernel support for that. That
does not apply to win32, though, which is a pity.
[...]
> : Even in that case there are still situations when you do not want to
> : serialize.
>
> Right.  We use conditions and mutexes to build more complex schedulers,
> e.g., R/W locks.
I wanted to mention R/W locks specifically, because it makes zero sense to
serialize wait-exit for readers. When the code guarded by a R/W lock
executes extremely fast, such R-wait-serialized lock degrades to a mere
critical section [mutex].
S
-----
< Forward Inline >
-------- Original Message --------
Message-ID: <3CEFC4B5.272F0DC6_at_[hidden]>
Date: Sat, 25 May 2002 19:07:01 +0200
From: Alexander Terekhov <terekhov_at_[hidden]>
Reply-To: terekhov_at_[hidden]
Newsgroups: comp.os.ms-windows.programmer.win32,comp.programming.threads,microsoft.public.win32.programmer.kernel
Subject: Re: The implementation of condition variables in pthreads-win32
References: <40726f20.0203260300.529bf1f3_at_[hidden]>   <3CE0C501.BEA63E94_at_[hidden]> <eEk4KY3#BHA.2336_at_tkmsftngp05> <3CE18E0C.F9EE7261_at_[hidden]> <u15b7m$#BHA.2520_at_tkmsftngp05> <3CE26636.2069C71B_at_[hidden]> <ueMYocM$BHA.1980_at_tkmsftngp04> <3CE3A44F.1ECC7192_at_[hidden]> <eRV52fN$BHA.2552_at_tkmsftngp05> <3CE3BA03.D126A7B2_at_[hidden]> <eebs#Na$BHA.1848_at_tkmsftngp05> <acisk3$qd$1_at_[hidden]> <OA8BPJoACHA.940_at_tkmsftngp05> <acko81$hec$3_at_[hidden]> <uLwSKjxACHA.2164_at_tkmsftngp04> <aclefi$ovm$2_at_[hidden]> <enHbwzzACHA.2200_at_tkmsftngp02>
"Slava M. Usov" wrote:
[...]
> No. In win32, semaphores are kernel mode objects. 
Yes. In win32, almost 'everybody and his dog' *IS* kernel 
mode object (yeah, and with 'security' silliness attached 
to it) -- mostly *brain-damaged* stuff, really >>Period<<
[snip silly 'KM/context switch may be avoided everywhere']
http://www.opengroup.org/onlinepubs/007904975/functions/pthread_cond_wait.html
"....
 Performance of Mutexes and Condition Variables
 Mutexes are expected to be locked only for a few 
 instructions. This practice is almost automatically 
 enforced by the desire of programmers to avoid long 
 serial regions of execution (which would reduce total 
 effective parallelism).
 When using mutexes and condition variables, one tries 
 to ensure that the usual case is to lock the mutex, 
 access shared data, and unlock the mutex. Waiting on 
 a condition variable should be a relatively rare situation. 
 For example, when implementing a read-write lock, code 
 that acquires a read-lock typically needs only to increment 
 the count of readers (under mutual-exclusion) and return. 
 The calling thread would actually wait on the condition 
 variable only when there is already an active writer. So 
 the efficiency of a synchronization operation is bounded 
 by the cost of mutex lock/unlock and not by condition wait. 
 Note that in the usual case there is no context switch.
 This is not to say that the efficiency of condition waiting 
 is unimportant. Since there needs to be at least one context 
 switch per Ada rendezvous, the efficiency of waiting on a 
 condition variable is important. The cost of waiting on a 
 condition variable should be little more than the minimal 
 cost for a context switch plus the time to unlock and lock 
 the mutex.
 ...."
> I wanted to mention R/W locks specifically, ....
Oh! I wanna 'mention R/W locks specifically' too:
A) http://www.opengroup.org/onlinepubs/007904975/xrat/xsh_chap02.html#tag_03_02_09_26
"....
 Although read-write locks can be implemented with mutexes 
 and condition variables, such implementations are significantly 
 less efficient than is possible. Therefore, this synchronization 
 primitive is included in IEEE Std 1003.1-2001 for the purpose 
 of allowing more efficient implementations in multi-processor 
 systems.
 ...."
B) *BRAIN-DAMAGED* (buggy too) MS-stuff:
 http://sources.redhat.com/ml/pthreads-win32/2001/msg00158.html
 (silly/buggy MSDN articles ["rwlock" including], I mean)
C) MS-Events 'showcase':
 http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/synchro_3t6b.asp
 (enjoy yet another "rwlock")
D) my own, humble, 'tackle' on this:
 http://groups.google.com/groups?selm=3B166244.F923B993%40web.de
 (semas/sort-of-mutex-MISUSE; no need for read/write pref.policy, though)
Any 'comments' (3/4 flames is OK, but, please, not MORE than 3/4) 
w.r.t. A) and B) and C) and D) are GREATLY APPRECIATED.... Slava, 
from you [your comments and/or annotations, etc.] TOO! ;-) ;-) ;-)
regards,
alexander.

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk