A lock that times out but doesn't poll

[Antoon Pardon]

The queue and condition class allow threads to wait only a limited
time. However this currently is implemented by a polling loop.

Now for those who like to avoid polling I have here a Tlock
class that allows for a timeout but doesn't use polling.

All comments are welcome.
----------------------- Tlock.py -------------------------------

import threading

class TimeOut(Excepti on):
pass

class Tlock:

def __init__(self):

self.mutex = threading.Lock( )
self.lktab = [threading.Lock( )]
def acquire(self, timeout=None):

class SC:
pass
def break_lock(sc, mutex, tab):

mutex.acquire()
try:
try:
i = tab.index(sc.pl , 1)
del tab[i]
sc.broken = True
sc.pl.release()
sc.pl.release()
except ValueError:
pass
finally:
mutex.release()
self.mutex.acqu ire()
sc=SC()
sc.ll = threading.Lock( )
sc.ll.acquire()
self.lktab.appe nd(sc.ll)
sc.pl = self.lktab[-2]
sc.broken = False
if len(self.lktab) > 2 and timeout is not None:
tm = threading.Timer (timeout, break_lock,
args=[sc, self.mutex, self.lktab])
tm.start()
else:
tm = None
self.mutex.rele ase()
sc.pl.acquire()
if sc.broken:
raise TimeOut, "lock timed out"
else:
if tm is not None:
tm.cancel()
def release(self):

self.mutex.acqu ire()
self.lktab[0].release()
del self.lktab[0]
self.lktab[0].release()
self.mutex.rele ase()
if __name__ == "__main__":

from time import sleep
from random import randint

T = Tlock()

def thrd(Id):

for _ in xrange(100):
try:
print "Trying %d" % Id
T.acquire(randi nt(0,6))
print "Entering %d" % Id
sleep(randint(0 ,6))
print "Leaving %d" % Id
T.release()
except TimeOut, ErrId:
print "Failed %d" % Id
sleep(randint(0 ,6))
for i in xrange(5):
th = threading.Threa d(target=thrd, args=(i,))
th.start()

[Jive]

Ironic, isn't it? The whole idea of a condition variable is to avoid
sleeping and polling. The polling soaks up CPU cycles, and the sleeping
introduces latency that might not be acceptable for a given application.

I presented two versions of sleepless timed condition variables in this NG a
year or two ago. They hooted me down like an English kuneegut.

One version used an alarm clock thread. From a very quick glance at your
code, I presume that's what you've done. The other used a C coded timed
lock, something that's not in standard Python. Why, I wonder? I can't
imagine there are many platforms where you can't implement such a thing. I
showed a C extension for MS Windows.

I made my Python module a drop-in replacement for the current threading
module, BTW. I am uncomfortable with the existing package not only because
it uses polling, ("the evil from which we flee"), but also because it's so
convoluted. Reading it, I have a hard time proving to myself that it's
correct. If the package I posted is still on the net somewhere, take a look
at it and see just how simple it can be.

Now they will taunt me a second time.

[Jive]

Okay, I've got a comment: How about some comments? Maybe it's just me, but
I find the code a little hard to comprehend.

What's up with this?

Exception in thread Thread-456:
Traceback (most recent call last):
File "C:\Python23\li b\threading.py" , line 436, in __bootstrap
self.run()
File "C:\Python23\li b\threading.py" , line 544, in run
self.function(* self.args, **self.kwargs)
File "C:\Python23\Sc ripts\foo.py", line 29, in break_lock
sc.pl.release()
error: release unlocked lock

That crops up occasionally.

It's been a while, but as I recall, the tricky bit in implementing timed
locks with an alarm clock thread is seeing to it that threads that don't
time out waiting on a timed lock do not leave zombie alarm clock threads
running. If you are not careful, they could proliferate and eat up system
resources.
"Antoon Pardon" <ap*****@forel. vub.ac.be> wrote in message
news:sl******** ************@rc pc42.vub.ac.be. ..

The queue and condition class allow threads to wait only a limited
time. However this currently is implemented by a polling loop.

Now for those who like to avoid polling I have here a Tlock
class that allows for a timeout but doesn't use polling.

All comments are welcome.
----------------------- Tlock.py -------------------------------

import threading

class TimeOut(Excepti on):
pass

class Tlock:

def __init__(self):

self.mutex = threading.Lock( )
self.lktab = [threading.Lock( )]
def acquire(self, timeout=None):

class SC:
pass
def break_lock(sc, mutex, tab):

mutex.acquire()
try:
try:
i = tab.index(sc.pl , 1)
del tab[i]
sc.broken = True
sc.pl.release()
sc.pl.release()
except ValueError:
pass
finally:
mutex.release()
self.mutex.acqu ire()
sc=SC()
sc.ll = threading.Lock( )
sc.ll.acquire()
self.lktab.appe nd(sc.ll)
sc.pl = self.lktab[-2]
sc.broken = False
if len(self.lktab) > 2 and timeout is not None:
tm = threading.Timer (timeout, break_lock,
args=[sc, self.mutex, self.lktab])
tm.start()
else:
tm = None
self.mutex.rele ase()
sc.pl.acquire()
if sc.broken:
raise TimeOut, "lock timed out"
else:
if tm is not None:
tm.cancel()
def release(self):

self.mutex.acqu ire()
self.lktab[0].release()
del self.lktab[0]
self.lktab[0].release()
self.mutex.rele ase()
if __name__ == "__main__":

from time import sleep
from random import randint

T = Tlock()

def thrd(Id):

for _ in xrange(100):
try:
print "Trying %d" % Id
T.acquire(randi nt(0,6))
print "Entering %d" % Id
sleep(randint(0 ,6))
print "Leaving %d" % Id
T.release()
except TimeOut, ErrId:
print "Failed %d" % Id
sleep(randint(0 ,6))
for i in xrange(5):
th = threading.Threa d(target=thrd, args=(i,))
th.start()

[Jive]

I just took a look at Timer in threading.py. Correct me if I'm wrong, but
it appears that the
timer always stays around for the programmed interval, even if cancel() is
called on it. If that's the
case, it's hard for me to see how it could be used to implement a useful
timed lock. The typical scenario
is for a thread to obtain a lock fairly quickly when things are functioning
properly, but to wait on it with
a long timeout in case some resource dries up -- like a socket connection
breaks. In that scenario,
a thread that repeatedly waits on a timed lock will generate new Timer
threads faster than they will die off.

How can you use cancel() for anything? In a time-sliced environment,
won't there
always be a race condition?

Once again, I have reservations about threading.py. I do realtime
programming in my day job, so
I see bush-whackers behind every rhododendron. Why, the stories I could
tell. They would
make a grown man sick Heck, they would make a sick man groan.

I looked for my pure Python version of timed locks, but I couldn't find it.
I'm wondering if I found
problems with *it* and deleted it.

I did find the MS-Windows timed lock extension though.

[Antoon Pardon]

Op 2004-11-25, Jive schreef <so*****@micros oft.com>:

I just took a look at Timer in threading.py. Correct me if I'm wrong, but
it appears that the
timer always stays around for the programmed interval, even if cancel() is
called on it. If that's the
case, it's hard for me to see how it could be used to implement a useful
timed lock. The typical scenario
is for a thread to obtain a lock fairly quickly when things are functioning
properly, but to wait on it with
a long timeout in case some resource dries up -- like a socket connection
breaks. In that scenario,
a thread that repeatedly waits on a timed lock will generate new Timer
threads faster than they will die off.

Only at the beginning, after the mean timeout Timer threads should die
out as fast as new are created. But that may be too much.

But is is worst. I found out that in order to wait the specific time
the Timer class uses a polling loop until the specified time is expired.

--
Antoon Pardon

[Antoon Pardon]

Op 2004-11-25, Jive schreef <so*****@micros oft.com>:

Okay, I've got a comment: How about some comments? Maybe it's just me, but
I find the code a little hard to comprehend.
The basic algorithm is that you have a list of simple locks that is
treated mostly like a queue. A tread that aquires the Tlock, first
allocates a new lock that is appened to the list and aquired, then
the next to last lock is aquired too.

A thread that releases the lock, releases the first lock and
deletes it from the table and then release the new first
lock.
A thread that specifies a timeout on the release, starts a timer
thread. This timer thread will look if the lock is in the table
and if so releases it and removes it from the table. It also
marks the lock is broken.

What's up with this?

Exception in thread Thread-456:
Traceback (most recent call last):
File "C:\Python23\li b\threading.py" , line 436, in __bootstrap
self.run()
File "C:\Python23\li b\threading.py" , line 544, in run
self.function(* self.args, **self.kwargs)
File "C:\Python23\Sc ripts\foo.py", line 29, in break_lock
sc.pl.release()
error: release unlocked lock

That crops up occasionally.
There are two solutions for that.

1) Just remove line 29, it is not needed but I entered it for
"estetical" concerns.

2) Use semaphores in the table. That means changing the Lock
to a Semaphore on lines 11 and 38.
It's been a while, but as I recall, the tricky bit in implementing timed
locks with an alarm clock thread is seeing to it that threads that don't
time out waiting on a timed lock do not leave zombie alarm clock threads
running. If you are not careful, they could proliferate and eat up system
resources.

What do you mean with a Zombie? The clock thread will remain for as long
as the timeout, which may be longer then needed but then they disappear,
so there won't be any real zombies.
But I expect some of the python comunity are laughing at me now, because
I have discoverd that the Timer class is implemented by a Condition
variable that is waited upon with a timeout. And this timeout is
implemented by a polling loop.
--
Antoon Pardon

[David Bolen]

"Jive" <so*****@micros oft.com> writes:

I did find the MS-Windows timed lock extension though.

That's pretty much what I use when I need them (at least under
Windows). For example, in a recent application I had a serious need
for low latency events and minimizing CPU while blocked. Switching
from the threading.Event to a Win32 event object was a big win on both
fronts, and are pretty drop-in in terms of functionality. I imagine
there is something similar in pthreads, but have not had the need
there yet.

Probably the best way to support this sort of thing in Python itself
is with OS-specific blocks for cases which are easy to do and fall
back to the current implementation in others. But as has been posted
here before, that needs someone to make, test and then propose the
changes.

-- David

[Jive]

"Antoon Pardon" <ap*****@forel. vub.ac.be> wrote in message
news:sl******** ************@rc pc42.vub.ac.be. ..

What do you mean with a Zombie? The clock thread will remain for as long
as the timeout, which may be longer then needed but then they disappear,
so there won't be any real zombies.

Whether you call them zombies or not, they can multiply like crazy and fll
up system memory.

[Jive]

"David Bolen" <db**@fitlinxx. com> wrote in message
news:ui******** ***@fitlinxx.co m...

"Jive" <so*****@micros oft.com> writes:

I did find the MS-Windows timed lock extension though.
That's pretty much what I use when I need them (at least under
Windows). For example, in a recent application I had a serious need
for low latency events and minimizing CPU while blocked. Switching
from the threading.Event to a Win32 event object was a big win on both
fronts, and are pretty drop-in in terms of functionality. I imagine
there is something similar in pthreads, but have not had the need
there yet.

Probably the best way to support this sort of thing in Python itself
is with OS-specific blocks for cases which are easy to do and fall
back to the current implementation in others. But as has been posted
here before, that needs someone to make, test and then propose the
changes.

-- David

Ah ha! You understand. I live and breath this stuff. You too?

Here is a common example from my line of work: You set a piece of machinery
into motion. If everything is operating normally, it will reach a certain
point and interrupt a light beam. You must react to that event instantly.
However, if it has not interrupted the beam after some longer time, you must
wake up because something is wrong.
Probably the best way to support this sort of thing in Python itself
is with OS-specific blocks for cases which are easy to do and fall
back to the current implementation in others. But as has been posted
here before, that needs someone to make, test and then propose the
changes.

I would ammend that to read, "fall back on an improvement of the current
implementation, " but otherwise I agree.

A year ago I volunteered (on this group) to do the general work, and the
specific module for Windoze. I was told, "Just post your cute little code
to some free software repository somewhere." At least that's the way I felt
at the time. Of course, no one here knows "Jive" from Adam. There is a
tendency on the net to assume anyone you don't recognise is a clueless
newbie, and everything they post is naive blather. I've been cruising and
using the newsgroups under one name or another since the mid 80's.

So where was I before I went off into old fart mode? Oh yeah. It really
should go into the main Python distribution.

[Peter Hansen]

Jive wrote:

Here is a common example from my line of work: You set a piece of machinery
into motion. If everything is operating normally, it will reach a certain
point and interrupt a light beam. You must react to that event instantly.
"Instantly" is of course impossible, even with a language
faster than Python. You probably have some specific maximum
latency in mind. And maybe this is a hard realtime system
and maybe it's not.

Python, of course, is unsuitable for many hard realtime systems,
and if you're using Windows you are probably on the wrong platform
in the first place. (Just on Friday we were doing a little bit
of latency measurement in a similar situation. 97 times out of
100 the Python code on a fast WinXP machine was taking less than
the required 0.35 seconds to respond and finish its processing.
Once it took 0.37 seconds, once it took 0.85 seconds, and once
it took just over 1.0 seconds. Windows....)
A year ago I volunteered (on this group) to do the general work, and the
specific module for Windoze. I was told, "Just post your cute little code
to some free software repository somewhere." At least that's the way I felt
at the time. Of course, no one here knows "Jive" from Adam. There is a
tendency on the net to assume anyone you don't recognise is a clueless
newbie, and everything they post is naive blather. I've been cruising and
using the newsgroups under one name or another since the mid 80's.

So where was I before I went off into old fart mode? Oh yeah. It really
should go into the main Python distribution.

The bar for putting things in the main distribution should be
very, very high. One of the conditions for doing that should
probably be that the code is fairly widely used and widely
required. It's not apparent that this is yet the case.

Why not post it to an appropriate "recipe" page in the fledgling
Agile Control Forum site instead? (http://www.engcorp.com/acf)
That way others who *do* work in the machine control field will
have an early chance to try out your code, experiment, maybe
even improve it, fix bugs, and basically do some of the work that
*should* be done before anything gets into the main Python distro...

-Peter