Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
go ahead... be a heretic
 
PerlMonks  

Boolean Thread::Semaphore ?

by chrestomanci (Priest)
on Feb 08, 2012 at 12:02 UTC ( #952465=perlquestion: print w/ replies, xml ) Need Help??
chrestomanci has asked for the wisdom of the Perl Monks concerning the following question:

Greetings wise brothers.

I am working on a multi threaded perl script (using a Thread_pool design pattern), where I have one thread building a queue of work to be done, and a number of worker threads pulling items of work from the queue.

In order to keep the queue size sensible, and the workers fully employed, I am using a Thread::Semaphore to control the work finding thread. If the queue becomes full then the work finding thread calls down() on the semaphore to block untill it is signaled to resume. If a worker thread finds the queue to be less than half full it calls up() on the semaphore to wake up the work finding thread to keep the queue of work full.

My problem is that Thread::Semaphore stores an integer (equal to the number of up() calls less the number of down() calls), and not a boolean value. I have a large number or worker threads and they can make lots of up() calls driving the value in the semaphore to a large number, so that it takes a lot of down() calls before the semaphore blocks.

What I would like is a semaphore that contains a boolean 1 or 0 value, so that any number of up() calls will not increase the value beyond 1, and every call to down() will always block untill another thread calls up.

Is there a way of using Thread::Semaphore in this way, or an alternative semaphore module that can be used for this purpose?

Comment on Boolean Thread::Semaphore ?
Re: Boolean Thread::Semaphore ?
by Corion (Pope) on Feb 08, 2012 at 12:04 UTC

    Why not use a Thread::Queue to distribute the work to your worker threads? The workers will block when the queue is empty and get woken up when there is work to be done.

      I am doing that, the work finding thread is putting the work it finds into a Thread::Queue object.

      The reason I want to use a semaphore as well is because the work finder runs much faster than the workers, but is quite expensive in terms of resource consumption.

      If there was not a mechanism to pause the work finder when there is enough work in the queue, it would build a queue of millions of items and waste a lot of memory and other resources in the process.

Re: Boolean Thread::Semaphore ?
by BrowserUk (Pope) on Feb 08, 2012 at 12:14 UTC
    Is there a way of using Thread::Semaphore in this way, or an alternative semaphore module that can be used for this purpose?

    You don't want a semaphore.

    The simplest mechanism is:

    wbile( my $workitem = sourceOfWork() ) { sleep 1 while $Q->pending > MAXQ; $Q->enqueue( $workitem ); }

    If you are concerned that the queue might empty during that 1 second, use Time::HiRes::usleep().

    If you really insist on not polling the queuesize, then use a condition vatiable:

    my $cond :shared; ... wbile( my $workitem = sourceOfWork() ) { cond_wait( $cond ); $Q->enqueue( $workitem ); } ## somewhere else ... ... cond_signal( $cond ) if $Q->pending < MAXQ; ...

    But really, the latter involves more work and is less effective.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    The start of some sanity?

      You don't want a semaphore.

      The simplest mechanism is:

      while( my $workitem = sourceOfWork() ) { sleep 1 while $Q->pending > MAXQ; $Q->enqueue( $workitem ); }

      Thanks, that looks to be a much more sensible approach compared with what I was doing with semaphores.

      That should teach me to read algorithoms online that are intened for other languages or problem domains where near realtime responses are required.

        The best way (aka not polling) would be that the worker thread will stop itself if the queue is full, and will be restarted by a client thread by a signal.

        take a look at thread signalling chapter in threads documentation

Re: Boolean Thread::Semaphore ?
by sundialsvc4 (Monsignor) on Feb 08, 2012 at 21:52 UTC

    I agree with BrowserUK’s sentiment that a simple polling loop (with a substantial sleep() delay between each iteration, and an appropriately long or short interval) is the simplest approach in this case.   If, in actual practice, a simple poll keeps the work-to-do list reasonably full most of the time, “you’re done.”   If the feeder process “wastes” a few dozen microseconds every thousand, and in the process it avoids a more complicated timing mechanism ... so what ... it’s a “waste” that you can afford.   Even if, every now and then, “the well runs dry,” but the total waste is not a significant delay to the business operation that it supports ... you can afford the simplicity.

Re: Boolean Thread::Semaphore ?
by Anonymous Monk on Feb 09, 2012 at 14:40 UTC
    While others have commented on alternative methods to the overarching problem, I wanted to address the specific question of a 'boolean' semaphore. One 'brain-dead' simple approach would be to sub-class Thread::Semaphore such that the ->up() operation sets the semaphore to 1 rather than incrementing it.
    package Thread::Semaphore::Boolean; use threads::shared; use parent 'Thread::Semaphore'; # Create a new 'boolean' semaphore sub new { my $class = shift; return $class->SUPER::new(1); } # Set semaphore's count to 1 sub up { my $sema = shift; lock($$sema); $$sema = 1; cond_broadcast($$sema); } 1;
    Again, this is 'brain-dead' in that elementary uses of ->down() and ->up() will work, whereas other 'fancy' operations may break (e.g., $sema->down(2) would 'hang' because the 'boolean' semaphore would never be greater than 1).

      Thanks, that is a good solution, though as you say, not very robust.

      I think a robust implementation would be a good idea, so with that in mind I have emailed the author of Thread::Semaphore about adding the feature, either via a subclass as you suggest, or by adding the feature to the existing core module.

      Don't worry, whatever code I submit will robust and be properly tested to avoid the bugs you suggest.

      This is a very bad idea.

      A counting semaphore is fundamentally the wrong mechanism(*) for watermarking a queue; so futzing with the API of a counting semaphore to allow it to be used (badly) for this purpose is just all kinds of wrong.

      (*)In brief, A counting semaphore is designed for controlling concurrent access to a resource that is limited but has multiple instantiations.

      A queue, even a pre-limited queue, does not fit this criteria.

      1. a queue can only be accessed by one user (reader or writer) at a time, regardless of how much is does or can contain.
      2. the availability of a queues resources is not determined by the actions of competing consumers -- the reason d'etre of the counting semaphore -- but rather by the actions of the producer.

        They are very different animals.

      3. Having the consumer(s) of a queue effectively control the producer(s) for that queue, requires multi-way synchronisation, and defeats the primary purpose of the queue: that of acting as a flexible buffer between producers and consumers to avoid the need for and problems associated with such synchronisation.

        Those problems include:

        Consumers and producers can become 'step-locked'.

        The flow falls into a pattern of the consumer(s) all wasting many time-slices (and expensive context switches) waiting for the producer(s). Then alternately, the producer(s) all waste time-slices waiting for the consumer(s). The flow becomes lock-stepped wasting many context switches between each forward step.

        The very purpose of queues is to alleviate this problem by acting as a flexible buffer removing the need for synchronisation.

      See 940030 for a little more discussion.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      The start of some sanity?

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://952465]
Approved by Ratazong
Front-paged by MidLifeXis
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (11)
As of 2014-04-17 19:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (454 votes), past polls