Потребитель/Производитель с порядком и ограничением на потребляемые товары

Я думаю, Ганс прав: если у вас уже есть потокобезопасный SortedSet (который реализует IProducerConsumerCollection, поэтому его можно использовать в BlockingCollection), то все, что вам нужно, это положить в коллекцию только файлы, которые можно обработать прямо сейчас. Если вы закончите работу над файлом, который сделает другой файл доступным для обработки, добавьте этот файл в коллекцию в этот момент, а не раньше.

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

EDIT (для тех, кто не любит читать документацию, но кто любит...)

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

    static void Main(string[] args)
    {
        BufferBlock<string> source = new BufferBlock<string>();
        var cancellation = new CancellationTokenSource();
        LinkConsumer(source, "A", cancellation.Token);
        LinkConsumer(source, "B", cancellation.Token);
        LinkConsumer(source, "C", cancellation.Token);

        // Link an action that will process source values that are not processed by other 
        source.LinkTo(new ActionBlock<string>((s) => Console.WriteLine("Default action")));

        while (cancellation.IsCancellationRequested == false)
        {
            ConsoleKey key = Console.ReadKey(true).Key;
            switch (key)
            {
                case ConsoleKey.Escape:
                    cancellation.Cancel();
                    break;
                default:
                    Console.WriteLine("Posted value {0} on thread {1}.", key, Thread.CurrentThread.ManagedThreadId);
                    source.Post(key.ToString());
                    break;
            }
        }

        source.Complete();
        Console.WriteLine("Done.");
        Console.ReadLine();
    }

    private static void LinkConsumer(ISourceBlock<string> source, string prefix, CancellationToken token)
    {
        // Link a consumer that will buffer and process all input of the specified prefix
        var consumer = new ActionBlock<string>(new Action<string>(Process), new ExecutionDataflowBlockOptions() { MaxDegreeOfParallelism = 1, SingleProducerConstrained = true, CancellationToken = token, TaskScheduler = TaskScheduler.Default });
        var linkDisposable = source.LinkTo(consumer, (p) => p == prefix);

        // Dispose the link (remove the link) when cancellation is requested.
        token.Register(linkDisposable.Dispose);
    }

    private static void Process(string arg)
    {
        Console.WriteLine("Processed value {0} in thread {1}", arg, Thread.CurrentThread.ManagedThreadId);

        // Simulate work
        Thread.Sleep(500);
    }