Yes, I synchronized removeFirst but I missed to synchronized unstartedRunnables.add.

TLDR;

If I run the removeFirst, there is a small chance that add adds a new element asynchroniously. We have two arrays having differrent sizes. That is why the ArrayIndexOutOfBoundsException is thrown. In order to solve the problem, I need to synchronize the unstartedRunnables.add call.

A good improvement suggestion however came from @rzwitserloot in order to not synchonize against the this-object.