Repository navigation
Fix emulated lock to be 'fair' #52657
Description
| BPO | 8410 |
|---|---|
| Nosy | @loewis, @ronaldoussoren, @pitrou, @kristjanvalur, @navytux |
| Files |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = <Date 2014-04-04.11:57:36.004>
created_at = <Date 2010-04-15.20:00:44.904>
labels = ['OS-mac', 'interpreter-core', 'type-bug']
title = "Fix emulated lock to be 'fair'"
updated_at = <Date 2019-09-11.16:42:28.070>
user = 'https://github.com/kristjanvalur'bugs.python.org fields:
activity = <Date 2019-09-11.16:42:28.070>
actor = 'navytux'
assignee = 'none'
closed = True
closed_date = <Date 2014-04-04.11:57:36.004>
closer = 'kristjan.jonsson'
components = ['Interpreter Core', 'macOS']
creation = <Date 2010-04-15.20:00:44.904>
creator = 'kristjan.jonsson'
dependencies = []
files = ['16933']
hgrepos = []
issue_num = 8410
keywords = ['patch', 'needs review']
message_count = 15.0
messages = ['103247', '103249', '103271', '103313', '103532', '103536', '103574', '103580', '103582', '103820', '111360', '215512', '351831', '351947', '351973']
nosy_count = 7.0
nosy_names = ['loewis', 'ronaldoussoren', 'pitrou', 'kristjan.jonsson', 'dabeaz', 'ysj.ray', 'navytux']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue8410'
versions = ['Python 3.2']
Activity
kristjanvalur commentedon Apr 15, 2010
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 bpo-8299, where this has been discussed at length.
loewis commentedon Apr 15, 2010
Why do you think condition variables don't provide fairness?
pitrou commentedon Apr 15, 2010
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.
kristjanvalur commentedon Apr 16, 2010
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 [email protected]"
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.
If the lock were based on a semaphore, the events would be different:
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 bpo-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 bpo-8299, if you don't trust the condition variable's own internal mechanism to treat its waiting threads fairly.
ronaldoussoren commentedon Apr 18, 2010
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":
kristjanvalur commentedon Apr 18, 2010
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.
kristjanvalur commentedon Apr 19, 2010
Also, _POSIX_SEMAPHORES must be defined to be greater than 200112L. If it isn't, then it isn't supported.
ysjray commentedon Apr 19, 2010
Hi,
krisvale:
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!
kristjanvalur commentedon Apr 19, 2010
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.
dabeaz commentedon Apr 21, 2010
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 bpo-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.
ronaldoussoren commentedon Jul 23, 2010
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.
kristjanvalur commentedon Apr 4, 2014
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.
navytux commentedon Sep 11, 2019
At least condition variable signalling has to be moved to be done under mutex for correctness: https://bugs.python.org/issue38106.
kristjanvalur commentedon Sep 11, 2019
super, good catch!
navytux commentedon Sep 11, 2019
Thanks for feedback.