

Hello fellow monks,

I'm trying to implement a FIFO non-blocking queue in a project I'm working on. What I want to do is create a queue for a pdf document to be generated. The reason I need the queue is that in the tests I've done if too many people request a pdf to be generated it bogs the server down so much only one or two people get theirs generated. The database its generated from has over a million records and some of the requested pdfs are huge. So I need to put users in line if more than one at a time requests a pdf.

What I have so far is the ability to place a user in queue and check where they are and the average time people have waited in line. The problem I'm having is figuring out how to make it non-blocking if someone decides to abandon their position in line. Currently the way I have it if someone abandons their position it will block everyone else from moving on and getting their job done.

I've never had to implement something like this before so i would appreciate any pointers on how to create something like this. I do realise that I need to have some sort of way of telling if that user who is waiting in line is still there without making the others wait unreasonably long. I was thinking of using a timestamp that updates every time a user checks their position in line.

Thanks for your help,

  • Comment on How would you implement a FIFO non-blocking queue?

Replies are listed 'Best First'.
Re: How would you implement a FIFO non-blocking queue?
by tilly (Archbishop) on Feb 25, 2006 at 04:15 UTC
    I think you're overengineering the problem.

    The simplest thing to do is eliminate the queue. Just say that when you try to create a PDF, it sees if one is being created, and if it is it just retries later. Eventually you get through. Simple, dumb, and in my experience almost always sufficient.

    If you want to get fancier, have a simple job table. When you ask for a PDF, it adds a record saying that person X wants PDF Y. A process is sitting there creating PDFs, which are placed in a temporary area for a bit, then cleaned up. At any time through a simple query you can see where someone is in line. If the person doesn't pick it up in time, they lose and have to resubmit the request. (With some cleverness you can do quite a bit with a surprisingly simple job system...)

    The next simplest is to modify the job table to allow people to cancel jobs. Again, the default is that work gets done, but people can remove their job from the queue.

    After that you can modify it to say that any job that is not updated regularly to say that you're still waiting is considered cancelled. And there you have it.

    BTW while you're optimizing this, note that while you might not be able to create 500 PDFs at once, you'll probably be able to create 5 at once faster than 5 sequentially. So introduce some naive parallelism by having 5 workers trying to take jobs. That will improve throughput, and will also keep one person with a large job from blocking everyone else until their job is done.

      I wish I could double-++ this!

      About the only thing I'd add would be a way to cancel an in-progress job (not simply remove one from the waiting-to-be-processed queue).

      Come to think of it, I wish *life* had an "oops, I didn't mean to do *that*" button....

      -- WARNING: You are logged into reality as root.
by GrandFather (Saint) on Feb 25, 2006 at 09:27 UTC

    The following may help. Note that this hasn't been tested beyond the sample code given so the handling for data in addition to the ID had not been checked.

    use warnings; use strict; package Fifo; sub new { my $self = []; return bless $self; } sub push { my $self = shift; my $id = shift; if (@_) { push @$self, [$id, \@_]; } else { push @$self, $id; } return scalar @$self; } sub pull { my $self = shift; return shift @$self; } sub remove { my $self = shift; my $id = shift; for (reverse 0..$#$self) { my $item = $self->[$_]; my $itemId = ref $item ? $item->[0] : $item; splice @$self, $_, 1 if $itemId eq $id } } 1; package main; my $fifo = Fifo->new; $fifo->push ('First person'); $fifo->push ('Second person'); $fifo->push ('Third person'); $fifo->remove ('Second person'); print "$_\n" while defined ($_ = $fifo->pull);


    First person Third person

    DWIM is Perl's answer to Gödel
by InfiniteSilence (Curate) on Feb 24, 2006 at 23:56 UTC
    Call me crazy, but I think you are going about this the wrong way. Two things immediately came to mind while I was reading your post. They were:
    • Why don't you just buy a faster/bigger server?
    • Why don't you try some in-memory caching with your webserver?
    Okay, neither of those solutions involves code, but if performance is your problem this is the route I would go first.

    Celebrate Intellectual Diversity

      Both are great questions.

      Why don't you just buy a faster/bigger server?

      I have no control over the hardware what so ever. So it's not up to me to get a new server.


      Good idea but not practical as the PDF is created on the fly depending upon the search done by the user. Also we don't want the information cached anywhere for security purposes.

      Good ideas though.