[issue8410] Fix emulated lock to be 'fair'

[Kirill Smelkov]

Kirill Smelkov  added the comment:

Thanks for feedback.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson  added the comment:

super, good catch!

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kirill Smelkov]

Kirill Smelkov  added the comment:

At least condition variable signalling has to be moved to be done under mutex 
for correctness: https://bugs.python.org/issue38106.

--
nosy: +navytux

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson added the comment:

Closing this issue.
It is largely superseded.  For our Python 2.7 branches, we have a custom GIL 
lock which can have different inherent semantics from the common Lock.  In 
particular, we can implement a fair PyGIL_Handoff() function to be used to 
yield the GIL to a waiting thread.

--
status: open - closed

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Changes by Kristján Valur Jónsson krist...@ccpgames.com:


--
resolution:  - rejected

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Ronald Oussoren]

Changes by Ronald Oussoren ronaldousso...@mac.com:


--
assignee: ronaldoussoren - 

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Ronald Oussoren]

Ronald Oussoren ronaldousso...@mac.com added the comment:

It turns out that posix semaphores aren't supported on OSX.

The patch doesn't apply cleanly anymore, and that is not just because of 
whitespace issues (the patch contains tabs while the tree no longer does).  

The chunk that affects 'PyThread_acquire_lock_timed' doesn't apply even with 
'patch -l' (which ignores whitespace).

I'll try to update the patch, but I'm not that well versed in pthread so that 
might take a while.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[David Beazley]

David Beazley d...@dabeaz.com added the comment:

I know that multicore processors are all the rage right now, but one thing that 
concerns me about this patch is its effect on single-core systems.  If you 
apply this on a single-CPU, are threads just going to sit there and thrash as 
they rapidly context switch? (Something that does not occur now).

Also, I've done a few experiments and on a single-core Windows-XP machine, the 
GIL does not appear to have any kind of fairness to it (as previously claimed 
here).   Yet, if I run the same experiments on a dual-core PC, the GIL is 
suddenly fair.  So, somewhere in that lock implementation, it seems to adapt to 
the environment.  Do we have to try an emulate that behavior in Unix?   If so, 
how do you do it without it turning into a huge coding mess? 

I'll just mention that the extra context-switching introduced by fair-locking 
has a rather pronounced effect on performance that should be considered even on 
multicore.  I posted some benchmarks in Issue 8299 for Linux and OS-X.  In 
those benchmarks, the introduction of fair GIL locking makes CPU-bound threads 
run about 2-5 times slower than before on Linux and OS-X.

--
nosy: +dabeaz

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson krist...@ccpgames.com added the comment:

Also, _POSIX_SEMAPHORES must be defined to be greater than 200112L.  If it 
isn't, then it isn't supported.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Ray.Allen]

Ray.Allen ysj@gmail.com added the comment:

Hi, 

krisvale:
 Since the exact mechanics seem to be unclair to many, let me just step you 
 through the series of events.
 1) A has the lock, B is waiting for it.  the bit is set.
 2) A releases the lock:  Clears the bit, signals the condition variable.
 3) A tries to immediately reacquire the lock.  Sees the bit cleared, sets it, 
 and claims the lock.
 4) B wakes up from the condition variable.  Sees the bit set and goes back 
 to sleep.  It has lost the race to A.

I don't quite understand the four steps you explained. After the time of step 
2, B is going to waken up and acquire the lock, and at the same time A returns 
from release function and is going to reacquire the lock. Who is scheduled 
first after A signals the condition variable is not predictable. So why does A 
always acquire the lock?

Thanks!

--
nosy: +ysj.ray

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson krist...@ccpgames.com added the comment:

In 2), B is indeed signaled and the OS makes it runnable.  But it doesn´t run 
immediately. A is still running.  There is no need for A to stop running until 
it runs out of timeslice.  Meanwhile the OS has to put B on a separate core 
(which makes this problem more significant on multicore), putting it at the end 
of the runnable queue where it has to percolate to the top for it to actually 
start execution some time later.

In effect, B has has to 'race' with A (and any other threads) to get the lock 
and since A is already running, it is likely to win the race.

Having threads 'race' to get synchronization primitives is a valid technique to 
reduce lock convoying problems, but it also can cause thread starvation, and is 
not approppriate when you want to ensure fair use of the resource.  To ensure 
fairness, lock handoff must be used.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Ronald Oussoren]

Ronald Oussoren ronaldousso...@mac.com added the comment:

W.r.t. This appears to be the case on Mac OS X: OSX 10.4 and later seem to 
support posix semaphores, the program below prints yes:

#include unistd.h

int main()
{
#ifdef _POSIX_SEMAPHORES
printf(yes\n);
#else
printf(no\n);
#endif
}

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson krist...@ccpgames.com added the comment:

Is it possible that unistd.h isn't included by Python on mac builds? perhaps 
the config script is broken and HAVE_UNISTD_H doesn't get defined.  I'll have a 
look at the generated pyconfig.h file on my colleague's machine tomorrow.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

Kristján Valur Jónsson krist...@ccpgames.com added the comment:

Martin, it isn't the condition variable which is unfair, but how the 
constructed locking apparatus is unfair that is the problem.  This lock is 
written by a Tim, whom I assume to be Tim Peters.  I quote his comment:  
In general, if the bit can be acquired instantly, it is, else the pair is used 
to block the thread until the bit is cleared. 9 May 1994 t...@ksr.com

Herein lies the problem.  This is the behaviour of greedy or unfair 
mutexes, not that of fair semaphores.  The lock is made 'free' and the just 
signaled thread has to _race_ to acquire it.

Since the exact mechanics seem to be unclair to many, let me just step you 
through the series of events.
1) A has the lock, B is waiting for it.  the bit is set.
2) A releases the lock:  Clears the bit, signals the condition variable.
3) A tries to immediately reacquire the lock.  Sees the bit cleared, sets it, 
and claims the lock.
4) B wakes up from the condition variable.  Sees the bit set and goes back to 
sleep.  It has lost the race to A.

If the lock were based on a semaphore, the events would be different:
1) A has the semaphore, B is waiting for it, sem.value == 0
2) A releases (signals) the semaphore.  B is made runnable. sem.value stays at 0
3) A tries to immediately reacquire the lock.  Finds the sem.value at 0 and 
blocks.
4) B wakes up and executes, now the owner of the lock. sem.value stays at 0.

This particular patch implements the latter behaviour by explicitly entering a 
handoff period.  If you want, I can submit a different patch which emulates a 
semaphore perfectly.  perhaps that is easier to understand, since semaphores 
are very familiar to people.

The key difference between Tim's lock is that the semaphore hands off 
ownership to a particular waiting thread.  The semaphore doesn't enter a state 
of free so that thread have to race to lock it.  It is this race which is 
unfair and which the just-releasing lock almost always wins.

If you are asking why would we want an unfair lock, then?, see issue 8299 
where I point out some links that discuss unfair locks and their role in 
combating lock convoys.


Antoine, if we have A, B, and C, all competing for the lock, at any one point, 
only one of the three has the lock.  Say, A.  The others are waiting on the 
condition variable.
Condition variables are generally implemented in a fair manner, so that all 
threads that wait on it are woken up in a roughly FIFO manner.  If not 
exactly, then at least in the long run.  All of the threads have to enter the 
condition variable's wait queue to acquire the lock.  Because of this, the lock 
is handed off to the threads in roughly the same order that they enter the 
condition variable´s wait state.

If, in your example, C is waiting on the condition variable, then A and B, 
whenever they give up the lock, they will hand it off a single thread which is 
woken up, typcally the one at the head of the condition variable's internal 
queue.  If the condition variable is implemented properly, there is no way that 
A and B can just flip-flop without C never being the thread to be woken up next.

As so often, the proof is in the pudding.  Try your ccprof.py script with the 
do_yield turned off.
You can also implement an explicitly FIFO condition variable, as I did in issue 
8299, if you don't trust the condition variable's own internal mechanism to 
treat its waiting threads fairly.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Kristján Valur Jónsson]

New submission from Kristján Valur Jónsson krist...@ccpgames.com:

On pthreads plaforms, if the posix_sem functions aren't available (when 
_POSIX_SEMAPHORES isn't defined), the python lock is implemented with a mutex 
and a condition variable.  This appears to be the case on Mac OS X, for example.
The problem is that this lock does not provide fairness to threads trying to 
acquire it.  This makes it a very poor candidate to implement the GIL, which is 
a lock that is held all the time, and all the threads are in constant 
competition to claim.
Other implementations of the python lock, such as the posix_sem based ones 
(linux) and Event based (MS Windows) provide fairness through that underlying 
synchronization primitive.

This patch fixes the emulated semaphore by making all competing threads wait 
their turn in the condition variable, thus enjoying whatever fairness that 
primitive provides.

I've not tested this patch for compilation since I don't have access to a mac 
to do that.  But the mechanism has been tested successfully on windows.

See also issue 8299, where this has been discussed at length.

--
assignee: ronaldoussoren
components: Interpreter Core, Macintosh
files: pthread_lock.patch
keywords: needs review, patch, patch
messages: 103247
nosy: krisvale, ronaldoussoren
severity: normal
status: open
title: Fix emulated lock to be 'fair'
versions: Python 2.7
Added file: http://bugs.python.org/file16933/pthread_lock.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Martin v . Löwis]

Martin v. Löwis mar...@v.loewis.de added the comment:

 On pthreads plaforms, if the posix_sem functions aren't available
 (when _POSIX_SEMAPHORES isn't defined), the python lock is
 implemented with a mutex and a condition variable.  This appears to
 be the case on Mac OS X, for example. The problem is that this lock
 does not provide fairness to threads trying to acquire it. 

Why do you think condition variables don't provide fairness?

--
nosy: +loewis

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8410] Fix emulated lock to be 'fair'

[Antoine Pitrou]

Antoine Pitrou pit...@free.fr added the comment:

I don't understand why you claim your patched version is fair. As far as I can 
tell, if you have three threads A, B and C all routinely trying to take this 
lock, your implementation can perfectly well bounce between A and B without 
ever giving the lock to C.

--
nosy: +pitrou
priority:  - normal
type:  - behavior
versions: +Python 3.2 -Python 2.7

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8410
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com