Sounds like you want to just use Thread::Queue objects inside a Thread::Queue, dequeue from the parent, then work on the child. A potential problem with this is that you can't modify the child queue in place (except by peeking) and would potentially have to keep a reference to it separate from the parent queue.
in reply to Re^2: How to create a two dimensional queue in Perl
in thread How to create a two dimensional queue in Perl
Alternatively you could use an actual state machine implementation from CPAN.