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(Exception):
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
sc.broken = True
sc.pl.release()
sc.pl.release()
except ValueError:
pass
finally:
mutex.release()


self.mutex.acquire()
sc=SC()
sc.ll = threading.Lock()
sc.ll.acquire()
self.lktab.append(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.release()
sc.pl.acquire()
if sc.broken:
raise TimeOut, "lock timed out"
else:
if tm is not None:
tm.cancel()


def release(self):

self.mutex.acquire()
self.lktab[0].release()
del self.lktab[0]
self.lktab[0].release()
self.mutex.release()


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(randint(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.Thread(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\lib\threading.py", line 436, in __bootstrap
self.run()
File "C:\Python23\lib\threading.py", line 544, in run
self.function(*self.args, **self.kwargs)
File "C:\Python23\Scripts\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.

 

[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]

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\lib\threading.py", line 436, in __bootstrap
self.run()
File "C:\Python23\lib\threading.py", line 544, in run
self.function(*self.args, **self.kwargs)
File "C:\Python23\Scripts\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]

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.

 

[David Bolen]

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]

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]

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]

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

 

[Jive]

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.

Well, there is that. The platform I'm using is a realtime operating system,
but it has a Windoze lookalike
API for OS functions like threads, semaphores, critical sections, events,
and whatnot.

[OT]
I don't draw any distinction between "soft" and "hard" realtime. I've never
seen definitions for
those terms that I thought were useful. If some operations must be
performed within a certain time
window, to me that's realtime, neither hard, soft, smooth, lumpy, or just
right. A realtime operating
system has guaranteed latency. Depending on the application, it does not
necessarily have
to be fast. I have an application that runs fine on a realtime OS, but
fails eventually under MS Windows
running on a processor that's 3x as fast.
[/OT]

The bar for putting things in the main distribution should be
very, very high.

Agreed. IMHO the bar was not set high enough for the current threading
module.

One of the conditions for doing that should
probably be that the code is fairly widely used and widely
required.

Why? If the existing code could be better, why not improve it?

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,

Oh, there will be no bugs.

and basically do some of the work that
*should* be done before anything gets into the main Python distro...

I will give it a look. I had some spare time last year when I volunteered
the first
time. I don't have spare time now, and probably will not have before May at
the earliest..
If someone would like to take over the code, I would be happy to contribute
it and give
as much help as I can.

Jive

 

[Jive]

Dang. I forgot the line-wrap again. Sorry about that.

 

[Peter Hansen]

[OT]
I don't draw any distinction between "soft" and "hard" realtime.
> I've never seen definitions for those terms that I thought were
> useful.

The key difference is that one is a binary test, and the other
is not. As an article writing by Steve Furr of QNX Software
says, "soft real time is a property of the timeliness of a
computation where the value diminishes according to its tardiness"
(but does not drop away completely to zero).

One simple way to look at it is that for a hard realtime system,
a given operation must complete 100% of the time within its
required time constraints or the system is defective, while for
a soft realtime system that value can be less than 100% and the
system is still considered functional.

I doubt any of this is new to you, but I thought I'd throw it
out there just in case.

Why? If the existing code could be better, why not improve it?

I would guess the best answer to that is "how do we judge
that it's really better?" And I think the answer to _that_
question is "by getting enough people who are very knowledgeable
in that area to exercise it enough to be able to form an
opinion about it, independent of its sole author." ;-)

Oh, there will be no bugs.

?? What kind of a statement is that? I can think of only two
possibilities. Either you are being deliberately provocative,
or you have such an extensive set of unit tests for it that
you feel confident making what would otherwise be a reckless
statement. Or you are much less experienced than you sound.
_Three_ possibilities. The three possibilities are ...

Seriously, why are you so confident about that? Even if
the code were trivial, we're talking *threads* here...

-Peter

 

[Jive]

?? What kind of a statement is that?

Humorous? Imagine Carl Spackler in Caddy Shack saying, "Oh, there will be
no money."

Seriously, why are you so confident about that? Even if
the code were trivial, we're talking *threads* here...

Two reasons:

1) I just know I can do it. Argue with *that* logic!

B) Writing bug-free code is quite possible when the job is well-defined and
"from scratch."
It's when you have to modify a mess that it gets tricky.

I think a lot of programmers would be capable of writing bug-free code if
they just knew
it was possible and believed they could do it. My programmers submit very
few bugs.

I've made some bugs in my day, but the odds are with me on this one.

But enough about me... Read any good books lately?

 

[Cameron Laird]

.
.
.

B) Writing bug-free code is quite possible when the job is well-defined and
"from scratch."

.
.
.
? !? Who has "well-defined" jobs?