> Какой выбрать планировщик для последовательного чтения миллионов файлов в каталоге с подкаталогами, чтобы минимизировать перемещения головок?
Если ваше чтение происходит последовательно в один поток, планировщик ввода/вывода вам слабо поможет: ваша задача генерирует единственный запрос и блокируется до завершения его выполнения, планировщик же для какого-то видимого эффекта требует несколько запросов, которые он может переупорядочить/склеить.
По идее вам нужно сначала создать правильную нагрузку на файловую систему, например обходя каталоги и читая файлы в параллельных потоках или используя fadvise для управления чтением.
> buf = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
не похоже на последовательное чтение.
> Есть подозрение, что чтение файлов происходит не в том порядке, в котором они были записаны
превратите его в уверенность или опровергните с помощью, например, blktrace.