Well, okay. Your requirements have become reasonably clear, although the design choices lead to some doubts here. As usual, there are alternative ways to accomplish the task. I tried to keep this as simple as possible and not reinvent sendmail or somesuch.

#! /usr/bin/perl

use strict;
use warnings;

use File::Temp;
use Fcntl qw( :flock );

myturn();
mywork();
exit();

sub diag { warn "$$: @_\n" }

sub mywork {
    diag "WORKING... @ARGV";
    sleep 1;
}

sub myturn {
    (my $wait, our $lk) = queueup("/tmp/foolock");
    diag "waiting on lock";
    flock($wait, LOCK_EX) or die;
    diag "obtained the lock!";
}

sub queueup {
    my $lkfile = shift;
    my ($prev, $own);

    # release this once done with our unit work
    $own = File::Temp->new( UNLINK => 0 );
    flock($own, LOCK_EX) or die;
    diag "create and lock $own";

    # protect lockfile ops with another lock...
    open(my $op, "+>", "$lkfile.lk") or die;
    flock($op, LOCK_EX) or die;

    diag "take previous $lkfile";
    open($prev, "+>", $lkfile) or die;
    diag "rename $own to $lkfile";
    rename("$own", $lkfile) or die;

    #flock($op, LOCK_UN) or die;

    return ($prev, $own);
}
[download]

As you can see, a chain of per-process locks is used, but just two lockfiles are kept around on /tmp. All in all, I'm somewhat unsure about the robustness of this approach.