Some more remarks:
- COND_TIMED_WAIT macro modifies timeout_result when pthread_cond_timewait expires. But timeout_result is not an int pointer, just an int. So it is never updated, and as a result, bfs_check_depleted is never set after a thread has waited for the current running thread to schedule it in vain (in _bfs_timed_wait).
- the scheduling function bfs_find_task returns the first task that has an expired deadline. since an expired deadline probably means that the scheduler hasn't run for a while, it might be worth it to look for the thread with the oldest deadline and serve it first, instead of stopping at the first one
- calls to COND_WAIT/COND_TIMED_WAIT should be run in loops checking for the predicate, since it might be false even after these call return (spurious wakeups, etc):
"In general, whenever a condition wait returns, the thread has to re-evaluate the predicate associated with the condition wait to determine whether it can safely proceed, should wait again, or should declare a timeout. A return from the wait does not imply that the associated predicate is either true or false. 

It is thus recommended that a condition wait be enclosed in the equivalent of a "while loop" that checks the predicate."