Задача на многопроцессорное программирование в c?

Question

[antonidas37]

Всем, привет, стоит задача найти самую длинную последовательность обернутую в боковые скобочки - "< " и ">".

То есть если в массиве символов лежат последовательности <a> и <bbb>, то ответ будет <bbb>.

Как можно решить данную задачу делая fork процессов? Может есть какие-то материалы, которые помогут с этим разобраться.

Comments

[Денис Загаевский]

Можно, конечно, придумать для решения этой задачи какой-то аналог машины Гольдберга на форках, но зачем?

[res2001]

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

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

Для варианта с форком все примерно так же, только надо продумать как передать новому процессу его диапазон и как возвратить результат основному процессу.

Удачи!

[rPman]

и никто не спросил, могут ли цепочки < > пересекаться, типа <aa<bb>aa> ?

Answer 1

[Wataru]

Я так понял, надо распараллелить? Посмотрите на OpenMP - работает в С/C++. Параллеленье очень просто делается - вставляете какие-то директивы в код, ключи компиляции и все работает.

Как решать задачу паралелльно: Разбейте всю строку на N (количество потоков) частей и каждый поток отдельно для каждой части найдет ответ внутри нее. А также две велечины: Самый последний символ '<', самый первый симовл '<' и вообще, есть ли они в этом куске.

Потом непараллельная часть, которая выберет лучшый ответ из N кусоков, а также проверит, какой есть самый длинный ответ распределенный по кускам. Для этого у вас все есть - вы знаете в каждом куске какой символ может быть началом <...> идущий в следующие куски и какой может быть концом. Надо еще рассмотреть случай, что в данном куске последний < левее первого > - тогда из этого куска отрезок <...> торчать не может. Иначе смотрите, где может левее начаться отрезок. Это все реализуется одним циклом на N итераций. Надо хранить последний символ < в предыдущих кусках, который пока не закрыт. Или закрываете текущим куском и сравниваете с ответом, или обрываете его (если кусок начинается с <) или продолжаете отрезок в следующий кусок.