A lock that times out but doesn't poll

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Antoon Pardon

    A lock that times out but doesn't poll

    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

    #2
    Re: A lock that times out but doesn't poll

    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.


    Comment

    • Jive

      #3
      Re: A lock that times out but doesn't poll

      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" <apardon@forel. vub.ac.be> wrote in message
      news:slrncq5vvl .61m.apardon@rc pc42.vub.ac.be. ..[color=blue]
      > 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()[/color]


      Comment

      • Jive

        #4
        Re: A lock that times out but doesn't poll

        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.


        Comment

        • Antoon Pardon

          #5
          Re: A lock that times out but doesn't poll

          Op 2004-11-25, Jive schreef <someone@micros oft.com>:[color=blue]
          > 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.[/color]

          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

          Comment

          • Antoon Pardon

            #6
            Re: A lock that times out but doesn't poll

            Op 2004-11-25, Jive schreef <someone@micros oft.com>:[color=blue]
            > 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.[/color]

            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.

            [color=blue]
            > 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.[/color]

            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.
            [color=blue]
            > 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.[/color]

            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

            Comment

            • David Bolen

              #7
              Re: A lock that times out but doesn't poll

              "Jive" <someone@micros oft.com> writes:
              [color=blue]
              > I did find the MS-Windows timed lock extension though.[/color]

              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

              Comment

              • Jive

                #8
                Re: A lock that times out but doesn't poll


                "Antoon Pardon" <apardon@forel. vub.ac.be> wrote in message
                news:slrncqdtc0 .61m.apardon@rc pc42.vub.ac.be. ..[color=blue]
                >
                > 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.[/color]

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


                Comment

                • Jive

                  #9
                  Re: A lock that times out but doesn't poll


                  "David Bolen" <db3l@fitlinxx. com> wrote in message
                  news:uis7sxu95. fsf@fitlinxx.co m...[color=blue]
                  > "Jive" <someone@micros oft.com> writes:
                  >[color=green]
                  > > I did find the MS-Windows timed lock extension though.[/color]
                  >
                  > 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[/color]

                  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.
                  [color=blue]
                  > 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.[/color]

                  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.


                  Comment

                  • Peter Hansen

                    #10
                    Re: A lock that times out but doesn't poll

                    Jive wrote:[color=blue]
                    > 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.[/color]

                    "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....)
                    [color=blue]
                    > 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.[/color]

                    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

                    Comment

                    • Jive

                      #11
                      Re: A lock that times out but doesn't poll


                      "Peter Hansen" <peter@engcorp. com> wrote in message
                      news:cocmon$k3c $1@utornnr1pp.g rouptelecom.net ...[color=blue]
                      > 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.[/color]

                      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]
                      [color=blue]
                      > The bar for putting things in the main distribution should be
                      > very, very high.[/color]

                      Agreed. IMHO the bar was not set high enough for the current threading
                      module.
                      [color=blue]
                      > One of the conditions for doing that should
                      > probably be that the code is fairly widely used and widely
                      > required.[/color]

                      Why? If the existing code could be better, why not improve it?
                      [color=blue]
                      >
                      > 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,[/color]

                      Oh, there will be no bugs.
                      [color=blue]
                      > and basically do some of the work that
                      > *should* be done before anything gets into the main Python distro...
                      >[/color]

                      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



                      Comment

                      • Jive

                        #12
                        Re: A lock that times out but doesn't poll

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



                        Comment

                        • Peter Hansen

                          #13
                          Re: A lock that times out but doesn't poll

                          Jive wrote:[color=blue]
                          > [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.[/color]

                          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.
                          [color=blue][color=green]
                          >>One of the conditions for doing that should
                          >>probably be that the code is fairly widely used and widely
                          >>required.[/color]
                          >
                          > Why? If the existing code could be better, why not improve it?[/color]

                          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." ;-)
                          [color=blue][color=green]
                          >>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,[/color]
                          >
                          > Oh, there will be no bugs.[/color]

                          ?? 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

                          Comment

                          • Jive

                            #14
                            Re: A lock that times out but doesn't poll


                            "Peter Hansen" <peter@engcorp. com> wrote in message
                            news:coe5l8$6l1 $1@utornnr1pp.g rouptelecom.net ...[color=blue]
                            > Jive wrote:[color=green]
                            > > Oh, there will be no bugs.[/color]
                            >
                            > ?? What kind of a statement is that?[/color]

                            Humorous? Imagine Carl Spackler in Caddy Shack saying, "Oh, there will be
                            no money."
                            [color=blue]
                            > Seriously, why are you so confident about that? Even if
                            > the code were trivial, we're talking *threads* here...
                            >[/color]

                            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?




                            Comment

                            • Cameron Laird

                              #15
                              Re: A lock that times out but doesn't poll

                              In article <yzKqd.5915789$ 6p.948699@news. easynews.com>,
                              Jive <someone@micros oft.com> wrote:

                              Comment

                              Working...