Обработка массива данных в несколько потоков

Имеется большой массив данных, который обрабатывается несколькими потоками одновременно (сами элементы массива не изменяются, а лишь читаются). Необходимо реализовать функционал, который позволяет равномерно распределить работу: у каждого потока в любой момент времени есть 1 обрабатываемый элемент, завершив работу с этим элементом, вызывается метод GetItem(), который запрашивает следующий элемент. Как идея: создать внутренний словарь где ключом будет идентификатор потока, а значением - позиция обрабатываемого элемента. При вызове метода GetItem() осуществляется потокобезопасный поиск номера элемента, который может быть следующим (номер на единицу больше наибольшего из номеров, обрабатываемых в настоящий момент, либо наименьший номер находящий между соседними отсортированными по возрастанию номерами с разницей больше 1). Так же следует избежать копирования самого массива - необходимо лишь вытаскивать в нужный момент элемент с определённым номером.

Просто разделить весь массив на несколько равных по размеру сегментов и скормить соответствующему количеству потоков не подходит, так как время обработки каждого элемента может сильно отличаться, и в то время как один поток завершит обработку, другие будут простаивать.

UPD: Работа всех потоков может быть прервана и тогда важно сохранить номера обрабатываемых элементов, чтобы в следующий раз можно было с них же начать.