Многопоточная обработка - нужен совет

[Jtt]

Доброго времени суток! Пишу небольшое консольное приложение, и у меня возникли некоторые вопросы. Надеюсь, кто-нибудь мне поможет

Суть приложения в следующем. Нужно организовать многопоточное сжатие файла большого размера (превышающего размер RAM. Т.е. размер файла 10-15ГБ). И использовать нужно .NET версии не выше 3.5 (соответственно никаких классов Task, Parallel и т.д.)

Я решил в этом деле применить шаблон поставщик/потребитель. Создаю несколько рабочих потоков, по одному на каждое ядро процессора (или число потоков следует выбирать иначе?). Основной поток считывает входной файл по блокам, и раздает их рабочим потокам, которые возвращают сжатые блоки для записи. На словах все достаточно просто. Но при реализации возникли следующие вопросы.

1. Как правильно реализовать очередь из блоков? Это может быть одна очередь, либо же отдельная очередь на каждый поток (лично я считаю последний вариант более оптимальным).
2. На блоки какого размера следует разбивать файл? Хотя этот вопрос не очень насущный, потому как это легко можно определить тестами.
3. Нумерация блоков. Так как в сжатый файл блоки нужно поместить в том же порядке, в котором они были считаны их исходного файла, то их необходимо нумеровать. Хорошо. Записали пронумерованные блоки в очередь (или в очереди), откуда их будет извлекать записывающий поток. Тут-то и проблема. Учитывая, что запись и так самое узкое место, записывающему потоку еще придется выискивать нужные блоки для организации правильного порядка записи. А если какой-то из блоков запоздает, то совсем плохая картина получается. И, собственно, сам вопрос: Как быть?
4. И, пожалуй, самый трудный вопрос. Как правильно организовать подачу этих самых блоков? Чтобы очередь на запись не переполнялась, а очередь на сжатие никогда не оставалась пустой.
5. И, наконец, как нужно выбирать размер памяти, отведенный приложению? Как это делаю нормальные программисты? Или без зазрения совести занимать всю свободную?

[Akeloya]

1. Как правильно реализовать очередь из блоков? Это может быть одна очередь, либо же отдельная очередь на каждый поток (лично я считаю последний вариант более оптимальным).

Речь не об оптимальности, а о том как будет реализовано распараллеливание программы. Одна очередь - распараллеливание с общей памятью, разные очереди - раздельная память. Всё зависит от того, как вы реализуете распараллеливание алгоритма сжатия, но в рамках одного компьютера - память всё равно будет одна, разве что доступ из разных потоков нужно организовывать.

2. На блоки какого размера следует разбивать файл? Хотя этот вопрос не очень насущный, потому как это легко можно определить тестами.

а с какими блоками работает единовременно алгоритм?

3. Нумерация блоков. Так как в сжатый файл блоки нужно поместить в том же порядке, в котором они были считаны их исходного файла, то их необходимо нумеровать. Хорошо. Записали пронумерованные блоки в очередь (или в очереди), откуда их будет извлекать записывающий поток. Тут-то и проблема. Учитывая, что запись и так самое узкое место, записывающему потоку еще придется выискивать нужные блоки для организации правильного порядка записи. А если какой-то из блоков запоздает, то совсем плохая картина получается. И, собственно, сам вопрос: Как быть?

Входные блоки одинакового размера? Выходные блоки одинакового размера? - тогда вычисляйте смещением. А, если, входные блоки одинакового размера, а выходные нет - тогда вы потеряете время на перестановках включением при записи блока в файл, так как даже не думайте, что потоки у вас будут без синхронизации выполняться синхронно на разных ядрах, а это значит, что возможно выход двух коротких блоков с одного потока (первый и N-й, для понимания трагедии), в то время как с остальных выйдет по одному большому блоку и как итог, первый и последний блок в серии будут записаны подряд, а остальные придется вставлять с помощью перестановки включением.
Соответственно, вам придется синхронизовать потоки в данном случае, что приведет к тому, что какие-то потоки будут простаивать, если хотя бы один задержится с выполнением по любой причине (тот же таск менеджер ему время выделил меньше, чем остальным из-за чего он завершился позже остальных).

4. И, пожалуй, самый трудный вопрос. Как правильно организовать подачу этих самых блоков? Чтобы очередь на запись не переполнялась, а очередь на сжатие никогда не оставалась пустой.
5. И, наконец, как нужно выбирать размер памяти, отведенный приложению? Как это делаю нормальные программисты? Или без зазрения совести занимать всю свободную?

А вы для кого и зачем пишите программу? Для себя - сами решайте, для приоритетного сжатия файла - занимайте всю свободную. Для эффективного сжатия файла? Тогда вычисляйте эффективную память, т.е. ту, которая необходима для непрерывной работы алгоритма.

А вообще, я вам рекомендую подумать над тем, насколько медленнее операция ввода-вывода одного блока данных, по сравнению со сжатием этого же блока в ОЗУ?
Чтение блоков у вас всё равно будет последовательное, т.е. каждый поток будет ждать пока для него не будет считан блок и затем только выполняться, затем он будет ждать пока этот блок не будет записан на (в худжем случае) тот же диск и опять будет ждать считывания данных и всё у вас заглохнет именно на диске.
Хотите ускорить процесс сжатия - купите SSD

В общем, распараллеливание реализуют для вычислений данных, уже находящихся в памяти и распараллеливают именно большие вычисления - матрицы, циклы.
Сжатие - процесс поточный и связан на 100% с операцией ввода-вывода.