If first thread signals, but gets interrupted before it can loop back to re-lock the variable and reenter the wait

If that's the problem (and I can't see what else it could be), then all you have to do is change

    while (1) {
        lock ($baton);
        cond_wait ($baton) until $baton == $id;
        ...
        cond_broadcast ($baton);
    }
[download]

to

    lock ($baton);
    while (1) {
        cond_wait ($baton) until $baton == $id;
        ...
        cond_broadcast ($baton);
    }
[download]

While you should do that change, I don't think that's the problem. The only time where missing the signal would cause a problem is if it's sent between the time $baton == $id is checked and the time cond_wait blocks. The purpose of locking $baton is to create the mutual exclusion that should prevent this from happening.

The problem might be that your system's implementation of cond_wait isn't atomic (while it should be), allowing a signal to come in after cond_wait unlocks $baton, but before cond_wait starts waiting.

You could give yourself a safety net by using cond_timedwait — cond_wait with a timeout — to check $baton periodically.

Update: Did some repharsing and added the second last paragraph.