Here is a patch which adds a timeout feature to the locking operations
provided by Python. This feature is added at two levels:
- the C API level, with a new function PyThread_acquire_lock_timed()
- the Python level, with an optional `timeout` argument to the acquire()
method of Lock and RLock objects (it also helps simplify the wait()
function of Condition objects)

The timeout duration is expressed in microseconds at the C API level,
and in seconds at the Python API level. There is also a new Python-level
constant, `_thread.TIMEOUT_MAX`, indicating the max allowable timeout
value (values above this raise an OverflowError).

At the C level, the max timeout is PY_TIMEOUT_MAX (in microseconds). The
caller should check the value him/herself.

The patch contains both a POSIX implementation and a Windows
implementation. It still lacks docs.

This patch adds some docs and comments. It also adds the feature in the
non-semaphore path of thread_pthread.h, which I had forgotten to address.

I don't object strongly, but since locks are "supposed" to be held for 
short amounts of time, a timeout shouldn't be that useful, and when 
people really need it they can put it together with a condition 
variable. Timeouts also interact poorly with condition variables: you 
can time out the initial acquire, but if you wait on a condition there's 
no place to put the timeout on the reacquire.

Given that it's hard to pick a timeout in most cases anyway, I think 
it'd be a much bigger win to figure out thread interruption. (Yes, I 
know that's hard, and that I promised to do it a long while ago and 
never got around to it.)

That said, I have no objections at all to adding an internal timeout 
ability for use by Condition.wait, and if you're still enthusiastic 
about adding the timeout given the above argument, I won't block you.

> Timeouts also interact poorly with condition variables: you 
> can time out the initial acquire, but if you wait on a condition there's 
> no place to put the timeout on the reacquire.

I don't see how it's an objection. If you have a condition variable you
just use the cv's timeout feature, don't you? I guess there are already
tons of combinations which don't make sense anyway.

> Given that it's hard to pick a timeout in most cases anyway, I think 
> it'd be a much bigger win to figure out thread interruption. (Yes, I 
> know that's hard, and that I promised to do it a long while ago and 
> never got around to it.)

What do you mean by thread interruption? Cancellation?

> That said, I have no objections at all to adding an internal timeout 
> ability for use by Condition.wait, and if you're still enthusiastic 
> about adding the timeout given the above argument, I won't block you.

Well, it's pretty basic functionality provided by the underlying OS
APIs, which is why I think it would be good to expose it. I remember
being annoyed by its absence, but it was a long time ago and I don't
remember which problem I was trying to solve.

(and it's safer than thread cancellation ;-))

>> Timeouts also interact poorly with condition variables: you
>> can time out the initial acquire, but if you wait on a condition there's
>> no place to put the timeout on the reacquire.
>
> I don't see how it's an objection. If you have a condition variable you
> just use the cv's timeout feature, don't you? I guess there are already
> tons of combinations which don't make sense anyway.

The cv's timeout stops waiting for the cv to be notified, but then it
just calls acquire() with no timeout.

>> Given that it's hard to pick a timeout in most cases anyway, I think
>> it'd be a much bigger win to figure out thread interruption. (Yes, I
>> know that's hard, and that I promised to do it a long while ago and
>> never got around to it.)
>
> What do you mean by thread interruption? Cancellation?

Yes, sorry, I was using the Java term, which isn't particularly accurate.

>> That said, I have no objections at all to adding an internal timeout
>> ability for use by Condition.wait, and if you're still enthusiastic
>> about adding the timeout given the above argument, I won't block you.
>
> Well, it's pretty basic functionality provided by the underlying OS
> APIs, which is why I think it would be good to expose it. I remember
> being annoyed by its absence, but it was a long time ago and I don't
> remember which problem I was trying to solve.

Fair enough.

Updated patch against py3k.

Updated patch against newest py3k.

> diff -r 8089902215a5 Doc/library/_thread.rst
> --- a/Doc/library/_thread.rst   Fri Jan 08 18:54:23 2010 +0100
> +++ b/Doc/library/_thread.rst   Fri Jan 08 20:33:54 2010 +0100
> @@ -103,18 +103,29 @@ It defines the following constant and fu
>    Availability: Windows, systems with POSIX threads.
>
>
> +.. data:: TIMEOUT_MAX

Above here, it says, "It defines the following constant and
functions:", which should be updated to "constants" now that there are
2.

> +
> +   The maximum value allowed for the *timeout* parameter of
> +   :meth:`Lock.acquire`. Specifiying a timeout greater than this value will
> +   raise an :exc:`OverflowError`.

Do we want to document what this value is likely to be? Or guarantee
that it's at least 2000?

I believe we can support arbitrary values here, subject to floating
point rounding errors, by calling lock-with-timeout in a loop. I'm not
sure whether that's a good idea, but it fits better with python's
arbitrary-precision ints.

> +
> +
>  Lock objects have the following methods:
>
>
> -.. method:: lock.acquire([waitflag])
> +.. method:: lock.acquire(waitflag=1, timeout=-1)
>
>    Without the optional argument, this method acquires the lock
> unconditionally, if

Since there are now 2 optional arguments, this needs to be updated.

>    necessary waiting until it is released by another thread (only one
> thread at a
>    time can acquire a lock --- that's their reason for existence).
> If the integer
>    *waitflag* argument is present, the action depends on its value:
> if it is zero,
>    the lock is only acquired if it can be acquired immediately without waiting,
> -   while if it is nonzero, the lock is acquired unconditionally as before.  The
> -   return value is ``True`` if the lock is acquired successfully,
> ``False`` if not.
> +   while if it is nonzero, the lock is acquired unconditionally as before.
> +   If the floating-point *timeout* argument is present and positive, it
> +   specifies the maximum wait time in seconds before returning.

You might mention that "lock.acquire(timeout=0)" is equivalent to
"lock.acquire(waitflag=0)", and that a missing or negative timeout
causes an unbounded wait.

> +
> +   The return value is ``True`` if the lock is acquired successfully,
> +   ``False`` if not.
>
>
>  .. method:: lock.release()
> diff -r 8089902215a5 Doc/library/threading.rst
> --- a/Doc/library/threading.rst Fri Jan 08 18:54:23 2010 +0100
> +++ b/Doc/library/threading.rst Fri Jan 08 20:33:54 2010 +0100
> @@ -155,6 +155,16 @@ This module defines the following functi
>    Availability: Windows, systems with POSIX threads.
>
>
> +This module also defines the following constant:
> +
> +.. data:: TIMEOUT_MAX
> +
> +   The maximum value allowed for the *timeout* parameter of blocking functions
> +   (:meth:`Lock.acquire`, :meth:`RLock.acquire`, :meth:`Condition.wait`, etc.).
> +   Specifiying a timeout greater than this value will raise an
> +   :exc:`OverflowError`.
> +
> +
>  Detailed interfaces for the objects are documented below.
>
>  The design of this module is loosely based on Java's threading model. However,
> @@ -349,7 +359,7 @@ and may vary across implementations.
>  All methods are executed atomically.
>
>
> -.. method:: Lock.acquire(blocking=True)
> +.. method:: Lock.acquire(blocking=True, timeout=-1)
>
>    Acquire a lock, blocking or non-blocking.
>
> @@ -363,6 +373,13 @@ All methods are executed atomically.
>    without an argument would block, return false immediately; otherwise, do the
>    same thing as when called without arguments, and return true.
>
> +   When invoked with the floating-point *timeout* argument set to a positive
> +   value, block for at most the number of seconds specified by *timeout*
> +   and as long as the lock cannot be acquired.

s/and as long as the lock cannot be acquired./and return False if the
lock couldn't be acquired by then./ ?  Also consider an equivalent
comment about timeout<=0 as I suggested for _thread.

> +
> +   The return value is ``True`` if the lock is acquired successfully,
> +   ``False`` if not.
> +
>
>  .. method:: Lock.release()
>
> @@ -396,7 +413,7 @@ pair) resets the lock to unlocked and al
>  :meth:`acquire` to proceed.
>
>
> -.. method:: RLock.acquire(blocking=True)
> +.. method:: RLock.acquire(blocking=True, timeout=-1)
>
>    Acquire a lock, blocking or non-blocking.
>
> @@ -415,6 +432,11 @@ pair) resets the lock to unlocked and al
>    without an argument would block, return false immediately; otherwise, do the
>    same thing as when called without arguments, and return true.
>
> +   When invoked with the floating-point *timeout* argument set to a positive
> +   value, block for at most the number of seconds specified by *timeout*
> +   and as long as the lock cannot be acquired.  Return true if the lock has
> +   been acquired, false if the timeout has elapsed.

``True`` and ``False``? And same comment as for Lock.acquire.

> +
>
>  .. method:: RLock.release()
>
> diff -r 8089902215a5 Include/pythread.h
> --- a/Include/pythread.h        Fri Jan 08 18:54:23 2010 +0100
> +++ b/Include/pythread.h        Fri Jan 08 20:33:54 2010 +0100
> @@ -23,6 +23,30 @@ PyAPI_FUNC(void) PyThread_free_lock(PyTh
>  PyAPI_FUNC(int) PyThread_acquire_lock(PyThread_type_lock, int);
>  #define WAIT_LOCK      1
>  #define NOWAIT_LOCK    0
> +
> +#if defined(HAVE_LONG_LONG)
> +#define PY_TIMEOUT_T PY_LONG_LONG
> +#define PY_TIMEOUT_MAX PY_LLONG_MAX

I think this deserves a comment that it's not the same as
_thread.TIMEOUT_MAX and why.

> +#else
> +#define PY_TIMEOUT_T long
> +#define PY_TIMEOUT_MAX LONG_MAX
> +#endif
> +
> +/* In the NT API, the timeout is a DWORD and is expressed in milliseconds */
> +#if defined (NT_THREADS) && (0xFFFFFFFFLL * 1000 < PY_TIMEOUT_MAX)
> +#undef PY_TIMEOUT_MAX
> +#define PY_TIMEOUT_MAX (0xFFFFFFFFLL * 1000)
> +#endif
> +
> +/* If microseconds == 0, the call is non-blocking: it returns immediately
> +   even when the lock can't be acquired.
> +   If microseconds > 0, the call waits up to the specified duration.
> +   If microseconds < 0, the call waits until success (or abnormal failure)
> +
> +   microseconds must be less than PY_TIMEOUT_MAX. Behaviour otherwise is
> +   undefined. */
> +PyAPI_FUNC(int) PyThread_acquire_lock_timed(PyThread_type_lock,
> +                                           PY_TIMEOUT_T microseconds);
>  PyAPI_FUNC(void) PyThread_release_lock(PyThread_type_lock);
>
>  PyAPI_FUNC(size_t) PyThread_get_stacksize(void);
> diff -r 8089902215a5 Lib/_dummy_thread.py
> --- a/Lib/_dummy_thread.py      Fri Jan 08 18:54:23 2010 +0100
> +++ b/Lib/_dummy_thread.py      Fri Jan 08 20:33:54 2010 +0100
> @@ -17,6 +17,10 @@ __all__ = ['error', 'start_new_thread',
>            'interrupt_main', 'LockType']
>
>  import traceback as _traceback
> +import time
> +
> +# A dummy value
> +TIMEOUT_MAX = 2**31

This should probably be the same as the typical value for _thread.TIMEOUT_MAX.

>  class error(Exception):
>     """Dummy implementation of _thread.error."""
> @@ -92,7 +96,7 @@ class LockType(object):
>     def __init__(self):
>         self.locked_status = False
>
> -    def acquire(self, waitflag=None):
> +    def acquire(self, waitflag=None, timeout=-1):
>         """Dummy implementation of acquire().
>
>         For blocking calls, self.locked_status is automatically set to
> @@ -111,6 +115,8 @@ class LockType(object):
>                 self.locked_status = True
>                 return True
>             else:
> +                if timeout > 0:
> +                    time.sleep(timeout)
>                 return False
>
>     __enter__ = acquire
> diff -r 8089902215a5 Lib/multiprocessing/pool.py
> --- a/Lib/multiprocessing/pool.py       Fri Jan 08 18:54:23 2010 +0100
> +++ b/Lib/multiprocessing/pool.py       Fri Jan 08 20:33:54 2010 +0100
> @@ -379,10 +379,10 @@ class Pool(object):
>                 p.terminate()
>
>         debug('joining task handler')
> -        task_handler.join(1e100)
> +        task_handler.join()

Why is this change here?  (Mostly curiosity)

>
>         debug('joining result handler')
> -        result_handler.join(1e100)
> +        task_handler.join()
>
>         if pool and hasattr(pool[0], 'terminate'):
>             debug('joining pool workers')
> diff -r 8089902215a5 Lib/test/lock_tests.py
> --- a/Lib/test/lock_tests.py    Fri Jan 08 18:54:23 2010 +0100
> +++ b/Lib/test/lock_tests.py    Fri Jan 08 20:33:54 2010 +0100
> @@ -4,7 +4,7 @@ Various tests for synchronization primit
>
>  import sys
>  import time
> -from _thread import start_new_thread, get_ident
> +from _thread import start_new_thread, get_ident, TIMEOUT_MAX
>  import threading
>  import unittest
>
> @@ -62,6 +62,14 @@ class BaseTestCase(unittest.TestCase):
>         support.threading_cleanup(*self._threads)
>         support.reap_children()
>
> +    def assertTimeout(self, actual, expected):
> +        # The waiting and/or time.time() can be imprecise, which
> +        # is why comparing to the expected value would sometimes fail
> +        # (especially under Windows).
> +        self.assertGreaterEqual(actual, expected * 0.6)
> +        # Test nothing insane happened
> +        self.assertLess(actual, expected * 10.0)
> +
>
>  class BaseLockTests(BaseTestCase):
>     """
> @@ -143,6 +151,31 @@ class BaseLockTests(BaseTestCase):
>         Bunch(f, 15).wait_for_finished()
>         self.assertEqual(n, len(threading.enumerate()))
>
> +    def test_timeout(self):
> +        lock = self.locktype()
> +        # Can't set timeout if not blocking

Please add this to the documentation.

> +        self.assertRaises(ValueError, lock.acquire, 0, 1)
> +        # Invalid timeout values
> +        self.assertRaises(ValueError, lock.acquire, timeout=-100)
> +        self.assertRaises(OverflowError, lock.acquire, timeout=1e100)
> +        self.assertRaises(OverflowError, lock.acquire, timeout=TIMEOUT_MAX + 1)
> +        # TIMEOUT_MAX is ok
> +        lock.acquire(timeout=TIMEOUT_MAX)
> +        lock.release()
> +        t1 = time.time()
> +        self.assertTrue(lock.acquire(timeout=5))
> +        t2 = time.time()
> +        self.assertLess(t2 - t1, 5)

This is just a sanity-check that a successful acquire finishes in a
sane amount of time, right? Please comment that.

> +        results = []
> +        def f():
> +            t1 = time.time()
> +            results.append(lock.acquire(timeout=0.5))
> +            t2 = time.time()
> +            results.append(t2 - t1)
> +        Bunch(f, 1).wait_for_finished()
> +        self.assertFalse(results[0])
> +        self.assertTimeout(results[1], 0.5)
> +
>
>  class LockTests(BaseLockTests):
>     """
> @@ -178,7 +211,7 @@ class LockTests(BaseLockTests):
>         b.wait_for_finished()
>         lock.acquire()
>         lock.release()
> -
> +
>
>  class RLockTests(BaseLockTests):
>     """
> @@ -284,14 +317,14 @@ class EventTests(BaseTestCase):
>         def f():
>             results1.append(evt.wait(0.0))
>             t1 = time.time()
> -            r = evt.wait(0.2)
> +            r = evt.wait(0.5)
>             t2 = time.time()
>             results2.append((r, t2 - t1))
>         Bunch(f, N).wait_for_finished()
>         self.assertEqual(results1, [False] * N)
>         for r, dt in results2:
>             self.assertFalse(r)
> -            self.assertTrue(dt >= 0.2, dt)
> +            self.assertTimeout(dt, 0.5)
>         # The event is set
>         results1 = []
>         results2 = []
> @@ -397,14 +430,14 @@ class ConditionTests(BaseTestCase):
>         def f():
>             cond.acquire()
>             t1 = time.time()
> -            cond.wait(0.2)
> +            cond.wait(0.5)
>             t2 = time.time()
>             cond.release()
>             results.append(t2 - t1)
>         Bunch(f, N).wait_for_finished()
>         self.assertEqual(len(results), 5)
>         for dt in results:
> -            self.assertTrue(dt >= 0.2, dt)
> +            self.assertTimeout(dt, 0.5)
>
>
>  class BaseSemaphoreTests(BaseTestCase):
> diff -r 8089902215a5 Lib/threading.py
> --- a/Lib/threading.py  Fri Jan 08 18:54:23 2010 +0100
> +++ b/Lib/threading.py  Fri Jan 08 20:33:54 2010 +0100
> @@ -31,6 +31,7 @@ try:
>     _CRLock = _thread.RLock
>  except AttributeError:
>     _CRLock = None
> +TIMEOUT_MAX = _thread.TIMEOUT_MAX
>  del _thread
>
>
> @@ -107,14 +108,14 @@ class _RLock(_Verbose):
>         return "<%s owner=%r count=%d>" % (
>                 self.__class__.__name__, owner, self._count)
>
> -    def acquire(self, blocking=True):
> +    def acquire(self, blocking=True, timeout=-1):
>         me = _get_ident()
>         if self._owner == me:
>             self._count = self._count + 1
>             if __debug__:
>                 self._note("%s.acquire(%s): recursive success", self, blocking)
>             return 1
> -        rc = self._block.acquire(blocking)
> +        rc = self._block.acquire(blocking, timeout)
>         if rc:
>             self._owner = me
>             self._count = 1
> @@ -234,22 +235,10 @@ class _Condition(_Verbose):
>                 if __debug__:
>                     self._note("%s.wait(): got it", self)
>             else:
> -                # Balancing act:  We can't afford a pure busy loop, so we
> -                # have to sleep; but if we sleep the whole timeout time,
> -                # we'll be unresponsive.  The scheme here sleeps very
> -                # little at first, longer as time goes on, but never longer
> -                # than 20 times per second (or the timeout time remaining).
> -                endtime = _time() + timeout
> -                delay = 0.0005 # 500 us -> initial delay of 1 ms
> -                while True:
> -                    gotit = waiter.acquire(0)
> -                    if gotit:
> -                        break
> -                    remaining = endtime - _time()
> -                    if remaining <= 0:
> -                        break
> -                    delay = min(delay * 2, remaining, .05)
> -                    _sleep(delay)
> +                if timeout > 0:
> +                    gotit = waiter.acquire(True, timeout)
> +                else:
> +                    gotit = waiter.acquire(False)
>                 if not gotit:
>                     if __debug__:
>                         self._note("%s.wait(%s): timed out", self, timeout)
> diff -r 8089902215a5 Modules/_threadmodule.c
> --- a/Modules/_threadmodule.c   Fri Jan 08 18:54:23 2010 +0100
> +++ b/Modules/_threadmodule.c   Fri Jan 08 20:33:54 2010 +0100
> @@ -39,18 +39,47 @@ lock_dealloc(lockobject *self)
>  }
>
>  static PyObject *
> -lock_PyThread_acquire_lock(lockobject *self, PyObject *args)
> +lock_PyThread_acquire_lock(lockobject *self, PyObject *args, PyObject *kwds)
>  {
> -       int i = 1;
> +       char *kwlist[] = {"blocking", "timeout", NULL};
> +       int blocking = 1;
> +       double timeout = -1;
> +       PY_TIMEOUT_T microseconds;
> +       int r;
>
> -       if (!PyArg_ParseTuple(args, "|i:acquire", &i))
> +       if (!PyArg_ParseTupleAndKeywords(args, kwds, "|id:acquire", kwlist,
> +                                        &blocking, &timeout))
>                return NULL;
>
> +       if (!blocking && timeout != -1) {
> +               PyErr_SetString(PyExc_ValueError, "can't specify a timeout "
> +                               "for a non-blocking call");
> +               return NULL;
> +       }
> +       if (timeout < 0 && timeout != -1) {
> +               PyErr_SetString(PyExc_ValueError, "timeout value must be "
> +                               "strictly positive");
> +               return NULL;
> +       }
> +       if (!blocking)
> +               microseconds = 0;
> +       else if (timeout == -1)
> +               microseconds = -1;
> +       else {
> +               timeout *= 1e6;
> +               if (timeout > PY_TIMEOUT_MAX) {

I believe it's possible for this comparison to return false, but for
the conversion to PY_TIMEOUT_T to still overflow:

$ cat test.c
#include <stdio.h>
#include <limits.h>

int main() {
  double d_ll_max = (double)LONG_LONG_MAX;
  if (d_ll_max > LONG_LONG_MAX)
   printf("Bigger\n");
  if (d_ll_max == LONG_LONG_MAX)
   printf("Equal\n");
  printf("%lld %lf %lld\n", LONG_LONG_MAX, d_ll_max, (long long)d_ll_max);
return 0;
}

$ ./test
Equal
9223372036854775807 9223372036854775808.000000 -9223372036854775808

Unfortunately, that overflowing cast back to long long is undefined
behavior, and I don't know how to check for that overflow before it
happens.

> +                       PyErr_SetString(PyExc_OverflowError,
> +                                       "timeout value is too large");
> +                       return NULL;
> +               }
> +               microseconds = (PY_TIMEOUT_T) timeout;
> +       }
> +
>        Py_BEGIN_ALLOW_THREADS
> -       i = PyThread_acquire_lock(self->lock_lock, i);
> +       r = PyThread_acquire_lock_timed(self->lock_lock, microseconds);
>        Py_END_ALLOW_THREADS
>
> -       return PyBool_FromLong((long)i);
> +       return PyBool_FromLong(r);
>  }
>
>  PyDoc_STRVAR(acquire_doc,
> @@ -105,9 +134,9 @@ Return whether the lock is in the locked
>
>  static PyMethodDef lock_methods[] = {
>        {"acquire_lock", (PyCFunction)lock_PyThread_acquire_lock,
> -        METH_VARARGS, acquire_doc},
> +        METH_VARARGS | METH_KEYWORDS, acquire_doc},
>        {"acquire",      (PyCFunction)lock_PyThread_acquire_lock,
> -        METH_VARARGS, acquire_doc},
> +        METH_VARARGS | METH_KEYWORDS, acquire_doc},
>        {"release_lock", (PyCFunction)lock_PyThread_release_lock,
>         METH_NOARGS, release_doc},
>        {"release",      (PyCFunction)lock_PyThread_release_lock,
> @@ -117,7 +146,7 @@ static PyMethodDef lock_methods[] = {
>        {"locked",       (PyCFunction)lock_locked_lock,
>         METH_NOARGS, locked_doc},
>        {"__enter__",    (PyCFunction)lock_PyThread_acquire_lock,
> -        METH_VARARGS, acquire_doc},
> +        METH_VARARGS | METH_KEYWORDS, acquire_doc},
>        {"__exit__",    (PyCFunction)lock_PyThread_release_lock,
>         METH_VARARGS, release_doc},
>        {NULL,           NULL}          /* sentinel */
> @@ -182,15 +211,41 @@ rlock_dealloc(rlockobject *self)
>  static PyObject *
>  rlock_acquire(rlockobject *self, PyObject *args, PyObject *kwds)
>  {
> -       char *kwlist[] = {"blocking", NULL};
> +       char *kwlist[] = {"blocking", "timeout", NULL};
>        int blocking = 1;
> +       double timeout = -1;
> +       PY_TIMEOUT_T microseconds;
>        long tid;
>        int r = 1;
>
> -       if (!PyArg_ParseTupleAndKeywords(args, kwds, "|i:acquire", kwlist,
> -                                        &blocking))
> +       if (!PyArg_ParseTupleAndKeywords(args, kwds, "|id:acquire", kwlist,
> +                                        &blocking, &timeout))
>                return NULL;
>
> +       if (!blocking && timeout != -1) {
> +               PyErr_SetString(PyExc_ValueError, "can't specify a timeout "
> +                               "for a non-blocking call");
> +               return NULL;
> +       }
> +       if (timeout < 0 && timeout != -1) {
> +               PyErr_SetString(PyExc_ValueError, "timeout value must be "
> +                               "strictly positive");
> +               return NULL;
> +       }
> +       if (!blocking)
> +               microseconds = 0;
> +       else if (timeout == -1)
> +               microseconds = -1;
> +       else {
> +               timeout *= 1e6;
> +               if (timeout > PY_TIMEOUT_MAX) {
> +                       PyErr_SetString(PyExc_OverflowError,
> +                                       "timeout value is too large");
> +                       return NULL;
> +               }
> +               microseconds = (PY_TIMEOUT_T) timeout;
> +       }
> +
>        tid = PyThread_get_thread_ident();
>        if (self->rlock_count > 0 && tid == self->rlock_owner) {
>                unsigned long count = self->rlock_count + 1;
> @@ -205,11 +260,11 @@ rlock_acquire(rlockobject *self, PyObjec
>
>        if (self->rlock_count > 0 ||
>            !PyThread_acquire_lock(self->rlock_lock, 0)) {
> -               if (!blocking) {
> +               if (microseconds == 0) {
>                        Py_RETURN_FALSE;
>                }
>                Py_BEGIN_ALLOW_THREADS
> -               r = PyThread_acquire_lock(self->rlock_lock, blocking);
> +               r = PyThread_acquire_lock_timed(self->rlock_lock, microseconds);
>                Py_END_ALLOW_THREADS
>        }
>        if (r) {
> @@ -1012,7 +1067,7 @@ static struct PyModuleDef threadmodule =
>  PyMODINIT_FUNC
>  PyInit__thread(void)
>  {
> -       PyObject *m, *d;
> +       PyObject *m, *d, *timeout_max;
>
>        /* Initialize types: */
>        if (PyType_Ready(&localtype) < 0)
> @@ -1027,6 +1082,12 @@ PyInit__thread(void)
>        if (m == NULL)
>                return NULL;
>
> +       timeout_max = PyFloat_FromDouble(PY_TIMEOUT_MAX / 1000000.);
> +       if (!timeout_max)
> +               return NULL;
> +       if (PyModule_AddObject(m, "TIMEOUT_MAX", timeout_max) < 0)
> +               return NULL;
> +
>        /* Add a symbolic constant */
>        d = PyModule_GetDict(m);
>        ThreadError = PyErr_NewException("_thread.error", NULL, NULL);
> diff -r 8089902215a5 Python/thread_nt.h
> --- a/Python/thread_nt.h        Fri Jan 08 18:54:23 2010 +0100
> +++ b/Python/thread_nt.h        Fri Jan 08 20:33:54 2010 +0100
> @@ -34,13 +34,13 @@ DeleteNonRecursiveMutex(PNRMUTEX mutex)
>  }
>
>  DWORD
> -EnterNonRecursiveMutex(PNRMUTEX mutex, BOOL wait)
> +EnterNonRecursiveMutex(PNRMUTEX mutex, DWORD milliseconds)
>  {
>        /* Assume that the thread waits successfully */
>        DWORD ret ;
>
>        /* InterlockedIncrement(&mutex->owned) == 0 means that no thread
> currently owns the mutex */
> -       if (!wait)
> +       if (!milliseconds)

Use ==0 now that this in a real integer?

>        {
>                if (InterlockedCompareExchange(&mutex->owned, 0, -1) != -1)
>                        return WAIT_TIMEOUT ;
> @@ -49,7 +49,7 @@ EnterNonRecursiveMutex(PNRMUTEX mutex, B
>        else
>                ret = InterlockedIncrement(&mutex->owned) ?
>                        /* Some thread owns the mutex, let's wait... */
> -                       WaitForSingleObject(mutex->hevent, INFINITE) : WAIT_OBJECT_0 ;
> +                       WaitForSingleObject(mutex->hevent, milliseconds) : WAIT_OBJECT_0 ;
>
>        mutex->thread_id = GetCurrentThreadId() ; /* We own it */
>        return ret ;
> @@ -249,17 +249,34 @@ PyThread_free_lock(PyThread_type_lock aL
>  * if the lock has already been acquired by this thread!
>  */
>  int
> +PyThread_acquire_lock_timed(PyThread_type_lock aLock, PY_TIMEOUT_T
> microseconds)
> +{
> +       int success ;
> +       PY_TIMEOUT_T milliseconds;
> +
> +       if (microseconds >= 0) {
> +               milliseconds = (microseconds + 999) / 1000;

Can (microseconds+999) overflow?

> +               if ((DWORD) milliseconds != milliseconds)
> +                       Py_FatalError("Timeout too large for a DWORD, "
> +                                      "please check PY_TIMEOUT_MAX");
> +       }
> +       else
> +               milliseconds = INFINITE;
> +
> +       dprintf(("%ld: PyThread_acquire_lock_timed(%p, %lld) called\n",
> +                PyThread_get_thread_ident(), aLock, microseconds));
> +
> +       success = aLock && EnterNonRecursiveMutex((PNRMUTEX) aLock, (DWORD)
> milliseconds) == WAIT_OBJECT_0 ;
> +
> +       dprintf(("%ld: PyThread_acquire_lock(%p, %lld) -> %d\n",
> +                PyThread_get_thread_ident(), aLock, microseconds, success));
> +
> +       return success;
> +}
> +int
>  PyThread_acquire_lock(PyThread_type_lock aLock, int waitflag)
>  {
> -       int success ;
> -
> -       dprintf(("%ld: PyThread_acquire_lock(%p, %d) called\n",
> PyThread_get_thread_ident(),aLock, waitflag));
> -
> -       success = aLock && EnterNonRecursiveMutex((PNRMUTEX) aLock,
> (waitflag ? INFINITE : 0)) == WAIT_OBJECT_0 ;
> -
> -       dprintf(("%ld: PyThread_acquire_lock(%p, %d) -> %d\n",
> PyThread_get_thread_ident(),aLock, waitflag, success));
> -
> -       return success;
> +       return PyThread_acquire_lock_timed(aLock, waitflag ? -1 : 0);
>  }
>
>  void
> diff -r 8089902215a5 Python/thread_pthread.h
> --- a/Python/thread_pthread.h   Fri Jan 08 18:54:23 2010 +0100
> +++ b/Python/thread_pthread.h   Fri Jan 08 20:33:54 2010 +0100
> @@ -83,6 +83,14 @@
>  #endif
>
>
> +/* We assume all modern POSIX systems have gettimeofday() */

Famous last words. ;)   (Not saying you should change anything)

> +#ifdef GETTIMEOFDAY_NO_TZ
> +#define GETTIMEOFDAY(ptv) gettimeofday(ptv)
> +#else
> +#define GETTIMEOFDAY(ptv) gettimeofday(ptv, (struct timezone *)NULL)
> +#endif
> +
> +
>  /* A pthread mutex isn't sufficient to model the Python lock type
>  * because, according to Draft 5 of the docs (P1003.4a/D5), both of the
>  * following are undefined:
> @@ -335,34 +343,61 @@ fix_status(int status)
>        return (status == -1) ? errno : status;
>  }
>
> -int
> -PyThread_acquire_lock(PyThread_type_lock lock, int waitflag)
> +int
> +PyThread_acquire_lock_timed(PyThread_type_lock lock, PY_TIMEOUT_T microseconds)
>  {
>        int success;
>        sem_t *thelock = (sem_t *)lock;
>        int status, error = 0;
> +       struct timeval tv;
> +       struct timespec ts;
>
> -       dprintf(("PyThread_acquire_lock(%p, %d) called\n", lock, waitflag));
> +       dprintf(("PyThread_acquire_lock_timed(%p, %lld) called\n",
> +                lock, microseconds));
>
> +       if (microseconds > 0) {
> +               GETTIMEOFDAY(&tv);
> +               tv.tv_usec += microseconds % 1000000;
> +               tv.tv_sec += microseconds / 1000000;
> +               tv.tv_sec += tv.tv_usec / 1000000;
> +               tv.tv_usec %= 1000000;
> +               ts.tv_sec = tv.tv_sec;
> +               ts.tv_nsec = tv.tv_usec * 1000;
> +       }
>        do {
> -               if (waitflag)
> +               if (microseconds > 0)
> +                       status = fix_status(sem_timedwait(thelock, &ts));
> +               else if (microseconds == 0)
> +                       status = fix_status(sem_trywait(thelock));
> +               else
>                        status = fix_status(sem_wait(thelock));
> -               else
> -                       status = fix_status(sem_trywait(thelock));
>        } while (status == EINTR); /* Retry if interrupted by a signal */
>
> -       if (waitflag) {
> +       if (microseconds > 0) {
> +               if (status != ETIMEDOUT)
> +                       CHECK_STATUS("sem_timedwait");
> +       }
> +       else if (microseconds == 0) {
> +               if (status != EAGAIN)
> +                       CHECK_STATUS("sem_trywait");
> +       }
> +       else {
>                CHECK_STATUS("sem_wait");
> -       } else if (status != EAGAIN) {
> -               CHECK_STATUS("sem_trywait");
>        }
>
>        success = (status == 0) ? 1 : 0;
>
> -       dprintf(("PyThread_acquire_lock(%p, %d) -> %d\n", lock, waitflag, success));
> +       dprintf(("PyThread_acquire_lock_timed(%p, %lld) -> %d\n",
> +                lock, microseconds, success));
>        return success;
>  }
>
> +int
> +PyThread_acquire_lock(PyThread_type_lock lock, int waitflag)
> +{
> +       return PyThread_acquire_lock_timed(lock, waitflag ? -1 : 0);
> +}
> +
>  void
>  PyThread_release_lock(PyThread_type_lock lock)
>  {
> @@ -430,40 +465,70 @@ PyThread_free_lock(PyThread_type_lock lo
>        free((void *)thelock);
>  }
>
> -int
> -PyThread_acquire_lock(PyThread_type_lock lock, int waitflag)
> +int
> +PyThread_acquire_lock_timed(PyThread_type_lock lock, PY_TIMEOUT_T microseconds)
>  {
>        int success;
>        pthread_lock *thelock = (pthread_lock *)lock;
>        int status, error = 0;
>
> -       dprintf(("PyThread_acquire_lock(%p, %d) called\n", lock, waitflag));
> +       dprintf(("PyThread_acquire_lock_timed(%p, %lld) called\n",
> +                lock, microseconds));
>
>        status = pthread_mutex_lock( &thelock->mut );
>        CHECK_STATUS("pthread_mutex_lock[1]");
>        success = thelock->locked == 0;
>
> -       if ( !success && waitflag ) {
> +       if (!success && microseconds != 0) {
> +               struct timeval tv;
> +               struct timespec ts;
> +               if (microseconds > 0) {
> +                       GETTIMEOFDAY(&tv);
> +                       tv.tv_usec += microseconds % 1000000;
> +                       tv.tv_sec += microseconds / 1000000;
> +                       tv.tv_sec += tv.tv_usec / 1000000;
> +                       tv.tv_usec %= 1000000;
> +                       ts.tv_sec = tv.tv_sec;
> +                       ts.tv_nsec = tv.tv_usec * 1000;

Pull this into a helper function so it's not duplicated between the
sem and mutex implementations?

> +               }
>                /* continue trying until we get the lock */
>
>                /* mut must be locked by me -- part of the condition
>                 * protocol */
> -               while ( thelock->locked ) {
> -                       status = pthread_cond_wait(&thelock->lock_released,
> -                                                  &thelock->mut);
> -                       CHECK_STATUS("pthread_cond_wait");
> +               while (thelock->locked) {
> +                       if (microseconds > 0) {
> +                               status = pthread_cond_timedwait(
> +                                       &thelock->lock_released,
> +                                       &thelock->mut, &ts);
> +                               if (status == ETIMEDOUT)
> +                                       break;
> +                               CHECK_STATUS("pthread_cond_timed_wait");
> +                       }
> +                       else {
> +                               status = pthread_cond_wait(
> +                                       &thelock->lock_released,
> +                                       &thelock->mut);
> +                               CHECK_STATUS("pthread_cond_wait");
> +                       }
>                }
> -               success = 1;
> +               success = (status == 0);
>        }
>        if (success) thelock->locked = 1;
>        status = pthread_mutex_unlock( &thelock->mut );
>        CHECK_STATUS("pthread_mutex_unlock[1]");
>
>        if (error) success = 0;
> -       dprintf(("PyThread_acquire_lock(%p, %d) -> %d\n", lock, waitflag, success));
> +       dprintf(("PyThread_acquire_lock_timed(%p, %lld) -> %d\n",
> +                lock, microseconds, success));
>        return success;
>  }
>
> +int
> +PyThread_acquire_lock(PyThread_type_lock lock, int waitflag)
> +{
> +       return PyThread_acquire_lock_timed(lock, waitflag ? -1 : 0);
> +}
> +
>  void
>  PyThread_release_lock(PyThread_type_lock lock)
>  {
>

Here is a new patch fixing most of your comments.

A couple of answers:

> I believe we can support arbitrary values here, subject to floating
> point rounding errors, by calling lock-with-timeout in a loop. I'm not
> sure whether that's a good idea, but it fits better with python's
> arbitrary-precision ints.

I'm a bit wary of this, because we can't test it properly.

> -        task_handler.join(1e100)
> +        task_handler.join()
> 
> Why is this change here?  (Mostly curiosity)

Because 1e100 would raise OverflowError :)

> +               if (timeout > PY_TIMEOUT_MAX) {
> 
> I believe it's possible for this comparison to return false, but for
> the conversion to PY_TIMEOUT_T to still overflow:

Ok, I've replaced it with the following which should be ok:

    if (timeout >= (double) PY_TIMEOUT_MAX) [...]

> +               milliseconds = (microseconds + 999) / 1000;
> 
> Can (microseconds+999) overflow?

Indeed it can (I sincerely hoped that nobody would care...).
I've replaced it with what might be a more appropriate construct.
Please note that behaviour is undefined when microseconds exceeds the max timeout, though (this is the low-level C API).

Updated patch against current py3k.
About the timeout limit, an useful point of comparison is select(), which doesn't try to loop either: it just throws OverflowError if the specified timeout value is too large to be represented in a timeval struct.

Thanks, looks good. Sorry for the delay.

Thank you! Checked in in r80071.

While you are at it, you might want to submit the patch from http://bugs.python.org/issue850728 as well.

It adds timeouts for semaphores. :)