どのログ出力ライブラリの話をしているかは知らないが
キューで実装されているならログ順序は保証されるだろうに
もしくはスレッドセーフでないライブラリを複数スレッドから触っているか