Python threading (was: Re: global interpreter lock not working as it should)

[Bengt Richter]

On 05 Aug 2002 04:30:22 +0200, martin at v.loewis.de (Martin v. Loewis) wrote:

>bokr at oz.net (Bengt Richter) writes:
>
>> >> A mutex should result in a context switch every time there is a
>> >> release with a waiter present, since the releaser would reliably
>> >> fail to re-acquire.  Perhaps that is the way it works on BSD?
>> >> That might at least partly explain Jonathan's results.
>
>> >I doubt that. 
>> Why?
>
>Because the other threads waiting for the GIL do not block on a
>mutex. So mutex wait lists should not be relevant for this behaviour.
>
Ok, I see that the mutex itself is not used to accomplish mutual exclusion on
the interpreter. Actually, it appears that a single pthread mutex would have the same
kind of race problem, if there really is one (and doubt is waning but not non-existent ;-),
as in the current lock implementation ;-/

BTW, the win32 mutex is apparently different:

"The state of a mutex object is signaled when it is not owned by any thread.
 The creating thread can use the bInitialOwner flag to request immediate ownership
 of the mutex. Otherwise, a thread must use one of the wait functions to request ownership.
 When the mutex's state is signaled, one waiting thread is granted ownership, the mutex's
 state changes to nonsignaled, and the wait function returns. Only one thread can own
 a mutex at any given time. The owning thread uses the ReleaseMutex function to
 release its ownership. "

>> IOW, I don't think the new owner has to execute before it becomes owner
>> of the mutex, I think the OS hands it over as part of the release operation
>> if there is a waiter. Why would it be done otherwise?
>
>Because of this code in thread_pthread.h
Hm. I suppose the pthread_lock is supposed to be general purpose, not just for the GIL,
but ISTM (;-) you could easily add serial handover functionality if you wanted to use that
for the GIL. It might be useful for other things too.

Seems like you'd just need an int waiter_count in your pthread_lock struct, which would be
protected by the mutex along with locked etc, and then make acquire_lock and release_lock
keep track. Consistency would be guaranteed by the mutex. The added functionality would be
accessed through an alternate to PyThread_release_lock, e.g., PyThread_handover_lock.
It would be just like release_lock, except that it would not set thelock->locked = 0 if
there was a waiter. It _would_ of course set thelock->locked = 0 if there were _no_ waiters,
so that the lock could be acquired normally (by just getting past the mutex spin lock at the
next attempt).

Waiting on the cond variable lock_released would work as now. Notice that when the waiter gets
control, it owns the mutex and just assumes that thelock->locked is 0 and should  be set to 1.
This would just be redundant but harmless in a handover. (If a waiter died of unnatural causes,
the waiter_count would have to be kept consistent. I'm not sure of the ramifications of that).

In any case, it would mean that the handing-over thread could not reacquire the lock without
waiting, irrespective of priority. Maybe that is the rub. OTOH, the current thread _is_ trying
to give other threads a chance. Anyway, if the cond_wait is dequeued in priority order, then
it should have a minimum wait. And if you really wanted to, I think something could be done
to shorten the byte code countdown or otherwise sense there when a higher priority thread was waiting.

>
>	status = pthread_mutex_lock( &thelock->mut );
>	CHECK_STATUS("pthread_mutex_lock[1]");
>	success = thelock->locked == 0;
>	if (success) thelock->locked = 1;
>	status = pthread_mutex_unlock( &thelock->mut );
>	CHECK_STATUS("pthread_mutex_unlock[1]");
>
>	if ( !success && waitflag ) {
>		/* continue trying until we get the lock */
>
>		/* mut must be locked by me -- part of the condition
>		 * protocol */
>		status = pthread_mutex_lock( &thelock->mut );
>		CHECK_STATUS("pthread_mutex_lock[2]");
>		while ( thelock->locked ) {
>			status = pthread_cond_wait(&thelock->lock_released,
>						   &thelock->mut);
>			CHECK_STATUS("pthread_cond_wait");
>		}
>		thelock->locked = 1;
>		status = pthread_mutex_unlock( &thelock->mut );
>		CHECK_STATUS("pthread_mutex_unlock[2]");
>		success = 1;
>	}
>
>Nobody is blocking on the mutex; the other thread blocks on the
>condition variable instead. The first thread signals the condition
>variable, then tries to lock the mutex. If that succeeds, it will
Signaling the condition variable seems to use kill(th->p_pid, PTHREAD_SIG_RESTART)
to start a waiting thread. Does that affect scheduling order between it
and the releasing thread?

>reacquire the lock. The other thread will come out of the cond_wait,
>and find that the lock is still locked. It then will wait on the
>condition variable again (probably adding itself to the end of the
>condition's wait list).
If that's the way it is working (and then presumably depending on
the dynamic priority adjustments you mentioned), what do you think
of implementing PyThread_handover_lock and using that for the GIL?
>
>> OTOH, if there is a variable associated with the mutex that is
>> supposed to represent some state of the interpreter, and other
>> threads are reading this without synchronizing, then I can see a
>> possible (different) race.
>
>The ->locked field of the lock is protected by a mutex, so there is no
>danger of it getting inconsistent - it is just not clear who will lock
>it.
Ok. Not to be tiresome, but what about making it clear with
PyThread_handover_lock for the GIL ;-)

>
>> If a race condition is possible, I think the OS mutex implementation
>> is not good or more likely there's a bug in its use and/or simulation.
>
>The OS mutex implementation is not (directly) used. Only the cond_wait
>implementation (indirectly) tries to acquire the mutex.
My impression was that it requires the mutex to be locked when called,
and unlocks it itself so as to wait unlocked, and then re-locks it for
the waiter. I.e., inside pthread_cond_wait:
  ...
  pthread_mutex_unlock(mutex);
  suspend_with_cancellation(self);
  pthread_mutex_lock(mutex);
  ...

I guess the re-lock involves trying, though -- is that a tiny crack
for Murphy to sneak through?

Ah, I guess that's why there's that 'while' in PyThread_acquire_lock:
		...
		while ( thelock->locked ) {
			status = pthread_cond_wait(&thelock->lock_released,
						   &thelock->mut);
			CHECK_STATUS("pthread_cond_wait");
		}
		thelock->locked = 1;
		...

Hm...
	
>
>> Because mutex is not used after 2.2? But I thought 2.2 was the
>> 'business' edition.  If there's a race condition there, should it
>> not be looked into and fixed?
>
>There is no bug in the sense that inconsistency could occur. There is
>just no guarantee that locks are fair in Python.

Thanks for your pointers. BTW, the source for the linuxthreads (or whatever
pthread package is actually used) is (AFAICS) not included in the win32 python
distribution. Might this be a good idea for cross-platform documentation purposes?

Regards,
Bengt Richter