Вроде все уже выше описал.
Я делаю не взять строку с удалением, а получаю кол-во строк, потом прохожу от 0 до N строк, после взятия N строки создаю лок файл, типа Run/1.lock, Run/2.lock и тп, следующий потом берет следующую строку, проверяет есть ли файл лока, есть есть, берет следующую и т.д. с последним потоком файлы лока затираются (ну либо после каждого прохода стирается свой).