Предлагаемые программные проекты на C# построены по материалам курса по "Параллельным вычислениям". Проекты написаны по завершении работы над текстом курса и поэтому реализация может отличаться от той, что дана в тексте курса. В некоторых проектах появились методы, не описанные в тексте лекций. С другой стороны не все задачи, рассмотренные в ходе лекций, нашли отражение в предлагаемых проектах.
Проекты являются важным дополнительным материалом к курсу лекций. Размещение их на сайте преследует три цели:
Проекты, связанные единой тематикой, объединены в Решения (Solution):
Sum объединяет проекты по теме суммирования;Integral связано с задачей вычисления определенного интеграла;Sorting объединяет проекты, реализующие различные методы сортировки; TasksAndInstruments объединяет проекты, позволяющие анализировать проблемы гонки данных, клинча и способы преодоления этих проблем.Game15 исследует важную тему взаимодействия управляющего и управляемого процессов, работающих в разных потоках. Оно представляет реализацию известной игры 15 и обладает чертами полноценного приложения с развитым интерфейсом, меню, файлами и другими атрибутами реальных приложений. Задача вычисления суммы $$S=\sum_k a_k$$ является классической задачей математики и программирования. При рассмотрении параллельных вычислений ей уделяется большое внимание.
Решение Sum содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов вычисления суммы. Построенные проекты позволяют также оценить эффективность инструментальных средств, реализующих в программах на C# параллельные вычисления.
В проектах рассматриваются три варианта вычисления суммы, где $$a_k$$ это :
Анализируются три варианта параллельных алгоритмов вычисления суммы – пирамидальный, сегментный и шаговый. Рассматриваются также различные вариации инструментария, реализующего параллельные вычисления:
For класса Parallel;Thtead;Task.Проекты, включенные в Решение Sum, следует рассматривать как дополнение, полезное при изучении материалов главы 3 (раздел "Суммирование") и глав 4 -7 учебника "Параллельные вычисления и многопоточное программирование.
Решение Sum содержит 5 проектов. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibrarySum, представляющего динамическую библиотеку классов. Эта библиотека содержит три класса – Massiv, Infinite_Series, Function_Sum. Каждый из этих классов содержит методы , реализующие последовательные и параллельные алгоритмы для трех изучаемых проблем – суммирования элементов массива, сходящихся рядов и конечных сумм, элементы которых заданы значениями функций.
Четыре проекта, входящие в Решение Sum, являются интерфейсными проектами. Три из них – ConsoleMassive_Sum, ConsoleArcSin и ConsoleFunction_Sum реализуют консольный интерфейс. Каждый из этих трех проектов позволяет в консоли анализировать три изучаемые проблемы. Четвертый интерфейсный проект – WindowsFormSum представляет классическое Windows Form приложение с главной формой и тремя формами, спроектированными для анализа рассматриваемых проблем.
Начну с общих выводов, связанных с проблемой распараллеливания вычислений. Все задачи можно условно разделить на пять классов:
Что можно сказать о задаче суммирования? К какому из классов ее следует отнести? Начнем с задачи суммирования элементов массива. Прежде, чем дать ответ, рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательного и различных параллельных алгоритмов по нахождению суммы элементов массивов различного размера, хранящих элементы вещественного типа (double). Вот какие результаты получены на моем компьютере (64-х битный компьютер с 6 Гб оперативной памяти и 4-мя физическими ядрами) при запуске Windows проекта из Решения Sum:
(рис 9.1) Суммирование элементов массивов разного размера
Как можно видеть, все алгоритмы – последовательный и параллельные - прекрасно справляются с задачей. Время суммирования вплоть до массива, содержащего 10000000 -десять миллионов элементов, составляет менее 0,1 секунды. В такой ситуации параллельные алгоритмы не имеют преимущества перед последовательным алгоритмом. Так что задачу нахождения суммы элементов массива, также как нахождение максимального элемента и другие подобные ей задачи, следует отнести ко второму классу, где применение параллельных алгоритмов хотя и возможно, но нецелесообразно на компьютерах подобного класса.
Хочу обратить внимание на одну особенность, связанную с результатами экспериментов. Время, замеряемое в экспериментах, содержит погрешности. Этих погрешностей избежать нельзя, поскольку они связаны с тем, как работает таймер в многозадачной операционной системе. Квант времени составляет 0,015 секунды, а ошибка измерения может достигать нескольких квантов. Для сравнения приведу результаты вычисления суммы элементов массива в тех же условиях, что и на рис. 1, но для другого сеанса работы:
(рис 9.2) Суммирование элементов массива. Эксперимент 2
Как видите, результаты слегка отличаются от результатов первого эксперимента. Но замечу, что во всех случаях последовательный алгоритм выигрывает сотые доли секунды у любых параллельных алгоритмов на массиве из 10 миллионов элементов.
Приведу теперь результаты экспериментов для задачи суммирования бесконечного сходящегося ряда на примере вычисления значений функции Arcsin(x). Эта задача интересна еще и тем, что эффективный последовательный алгоритм использует рекуррентное соотношение для вычисления очередного члена суммы. При распараллеливании такого эффективного приема не существует. Рекуррентное соотношение хотя и можно построить для параллельного шагового алгоритма, но оно значительно сложнее в сравнении с последовательным вариантом. Учитывая еще, что последовательный алгоритм практически мгновенно решает эту задачу, то у параллельного алгоритма нет шансов выиграть, что и подтверждается результатами экспериментов:
(рис 9.3) Суммирование сходящегося ряда
Можно видеть, что как последовательный, так и параллельный алгоритм прекрасно справляются с задачей. Время многократного (10000 повторов) вычисления значения функции менее 0,1 секунды. Но опять-таки параллельный алгоритм не имеет преимущества перед последовательным алгоритмом. Так что и эту задачу следует отнести ко второму классу, где применение параллельных алгоритмов хотя и возможно, но нецелесообразно на компьютерах подобного класса.
Полагаю, что справедлива следующая гипотеза:
Задачи с линейной временной сложностью относятся ко второму классу.
Для того чтобы параллельные алгоритмы выигрывали у последовательных алгоритмов исходная задача должно иметь по крайней мере квадратичную сложность. Суммирование конечного ряда, где каждый член ряда требует вычисления значения функции с линейной сложностью $$O(n)$$, относится к подобным задачам, поскольку для вычисления суммы ряда необходимо вычислить n членов ряда. Подробное описание примера приведено в 7-й главе учебника в разделе, посвященном методу Parallel.For, а его реализация представлена в классе Function_Sum. Вот как выглядят результаты эксперимента:
(рис 9.4) Суммирование конечного ряда
Рассматриваемую нами задачу, имеющую квадратичную временную сложность $$O(n^2)$$ следует отнести к третьему классу задач, допускающих эффективное распараллеливание. В главе 7 подробно обсуждается алгоритм, позволяющий перейти от исходной частично распараллеливаемой задачи к практически полному распараллеливанию. Анализируя приведенные результаты можно видеть, что последовательному алгоритму понадобилось ощутимо заметное время на вычисления – более 5 секунд. В то же время все параллельные алгоритмы выигрывают у последовательного алгоритма, лучший из них выигрывает более чем в 4 раза, что согласуется с числом ядер компьютера. Лучшим параллельным алгоритмом является алгоритм, построенный с использованием метода Parallel.For. Но и методы, использующие непосредственно потоки и объекты класса Task ведут себя вполне достойно на этой задаче.
Можно сделать и более общий вывод. Для потенциально распараллеливаемых задач со сложностью $$O(n^2)$$ и выше следует искать эффективные параллельные алгоритмы, позволяющие ощутимо сократить время решения задачи. Поиск таких алгоритмов непростая задача. Эта тема будет обсуждаться и при рассмотрении других проектов, дополняющих и сопровождающих учебник "Параллельные вычисления и многопоточное программирование".
Задача вычисления интеграла $$S=\int^b_a f(x)dx$$ также относится к классическим задачам математики и программирования. При рассмотрении параллельных вычислений в учебном курсе она достаточно подробно обсуждается. Вычисление интеграла аналогично задаче суммирования, поскольку практически вычисление значения S сводится к вычислению суммы $$S=\sum_k f(x_k)delta_x$$.
Решение Integral содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов вычисления интеграла.
Решение Integral содержит 2 проекта. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibraryIntegral, представляющем динамическую библиотеку классов. Библиотека содержит один класс – Integral, включающий методы, реализующие последовательные и параллельные алгоритмы вычисления интеграла. Параллельный алгоритм построен на использовании инструментария Parallel.For.
Для распараллеливания используется стратегия сегментного алгоритма вычисления суммы. Интервал интегрирования разбивается на k сегментов, на каждом из которых для вычисления интеграла используется обычный последовательный алгоритм. Вычисление интегралов на отдельных сегментах ведется параллельно. Эта стратегия оказывается весьма эффективной, даже в том случае, когда вычисление интеграла на каждом сегменте ведется последовательно. Выигрыш по времени может достигать десятки раз при относительно небольшой потери точности. В учебном курсе поясняется причина такой эффективности. Подынтегральная функция на каждом участке ведет себя более гладко, в сравнении со всем интервалом интегрирования. По этой причине на каждом сегменте достаточно быстро достигается нужная точность вычислений.
Что касается последовательного метода вычисления интеграла на отрезке, то в классе Integral представлены два классических метода – более простой в реализации метод прямоугольников и более эффективный метод трапеций.
Интерфейсный проект – WindowsForm Integral представляет классическое Windows Form приложение, спроектированное для анализа двух проблем – анализа эффективности последовательного и параллельного алгоритма и анализа влияния числа сегментов на эффективность решения задачи.
Исследование ведется на примере подынтегральной функции, задающей гармонические колебания. Для интеграла от этой функции известно точное значение, что позволяет следить за точностью решения задачи. Интерфейс проекта позволяет легко менять параметры функции – амплитуду и частоту колебаний, также как и интервал интегрирования.
Рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательного и параллельного алгоритмов в зависимости от числа сегментов разбиения интервала интегрирования:
(рис 9.5) Сравнительный анализ эффективности последовательного и параллельного алгоритмов (метод прямоугольников)
Анализируя эти результаты можно видеть, что интегрирование с разбиением на сегменты дает существенный выигрыш по времени. В данном эксперименте время сокращается в 15 раз при делении на 64 сегмента с 14, 4 секунды до 0, 97 секунды. Это ускорение достигается только за счет разделения на сегменты. Требуемая точность вычислений 108 сохраняется.
Параллельный алгоритм выигрывает во всех случаях у последовательного алгоритма. За счет параллелизма достигается эффективное 4-х кратное ускорение, как и должно быть для компьютера с 4-мя ядрами.
Если вместо метода прямоугольников применять для вычисления интеграла значительно более эффективный метод трапеций, то при тех же данных последовательный алгоритм работает намного быстрее, поэтому и выиграть у него можно относительно немного. Вот каковы результаты эксперимента, когда в тех же условиях применяется более эффективный метод трапеций:
(рис 9.6) Сравнительный анализ эффективности последовательного и параллельного алгоритмов (метод трапеций)
Анализируя эти результаты, можно видеть, что в данном случае последовательный алгоритм без разбиения интервала интегрирования на сегменты прекрасно справляется с задачей, затрачивая на решение 0, 015 секунды. Хотя параллельные алгоритмы работают не хуже, но говорить о реальном повышении эффективности вряд ли стоит.
Подводя итоги, можно сказать, что задача вычисления интеграла относится к задачам второго и третьего типа в зависимости от сложности вычисления подынтегральной функции. Когда подынтегральная функция вычислительно простая, как в нашем примере, то фактически задача вычисления интеграла имеет линейную сложность и относится ко второму типу, когда распараллеливание возможно, но не имеет особого смысла ввиду эффективной работы последовательного алгоритма. Для сложной в вычислительном отношении функции задачу следует относить к третьему типу и применять параллельные алгоритмы с разбиением интервала интегрирования на сегменты. Применение метода прямоугольников по существу имитирует увеличение сложности вычисления функции, демонстрируя, каков эффект можно получить при распараллеливании этой задачи.
Решение Sorting содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов сортировки массивов. В проектах анализируются три алгоритма:
Первые две сортировки рассматриваются в учебном курсе. Сортировка Бэтчера, которая создавалась как сортировка, предназначенная для параллельного выполнения, в текст учебника не вошла. Одна из причин в том, что хотя алгоритм сортировки достаточно прост, но объяснение его корректности совсем не просто.
Решение Sorting содержит 3 проекта. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibrary Sorting, представляющем динамическую библиотеку классов. Библиотека содержит один класс – Sorting, включающий методы, реализующие последовательные и параллельные алгоритмы сортировки массива.
Для пузырьковой сортировки построен метод, реализующий последовательную классическую версию, и метод, реализующий параллельный вариант пузырьковой сортировки. Параллельный вариант реализует идею шагового алгоритма. Сортируемый массив разбивается на k групп, в каждую из которых включаются элементы, отстоящие на расстоянии k. Все группы сортируются параллельно, а затем выполняется последовательная операция слияния k-упорядоченных групп в единый массив.
Для быстрой сортировки наряду с последовательной версией рассматриваются два параллельных метода – один реализует идею шагового алгоритма, другой – реализует рекурсивный вариант сортировки с ограниченным распараллеливанием.
Для рекурсивного варианта с ограничением на параллелизм в зависимости от объема массива вызывается либо последовательная версия либо параллельная версия, использующая инструментарий параллельных задач (класс Task). Этот вариант в лекциях курса не рассматривался, хотя, как можно будет увидеть по результатам экспериментов, он наиболее эффективен при сортировке больших массивов.
Для сортировки Бэтчера построены две параллельные версии. Одна реализует алгоритм, описанный в третьем томе "Искусство программирования" - фундаментальном труде Дональда Кнута. Эта версия (у Кнута это явно не оговорено) корректно работает только тогда , когда размер массива N является степенью двойки. Вторая версия работает для массивов любого размера.
Два проекта WindowsFormsSorting и ConsoleSorting являются интерфейсным проектами. Первый удобен при проведении запланированных исследований, второй – при проведении экспериментов, проверки различных возникающих гипотез.
Рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательных и параллельных алгоритмов. Посмотрим, что может дать параллельный вариант пузырьковой сортировки в сравнении с его последовательным собратом:
(рис 9.7) Сравнительный анализ эффективности последовательного и параллельного алгоритмов пузырьковой сортировки
Результаты показывают, что параллельный вариант "пузырька" сортировки массива из 100 000 элементов при разбиении массива на 100 групп эффективнее по времени более чем в 100 раз, затрачивая на сортировку менее секунды, в то время, когда последовательный вариант затрачивает более полутора минут. Как видите, распараллеливание дает существенный эффект. Радость этого успеха слегка портит тот факт, что существует другой последовательный алгоритм, который сортирует этот массив еще быстрее. Можно видеть, что последовательный алгоритм быстрой сортировки справляется с задачей на порядок лучше параллельного пузырька, затрачивая на сортировку сотые доли секунды.
Главный вопрос, на какой хотелось получить ответ при изучении методов сортировки, можно ли предложить параллельный вариант сортировки, работающий быстрее последовательного варианта быстрой сортировки? В тексте лекций положительного ответа так и не было дано. Приведу результаты, показывающие, что параллельные методы сортировки могут работать быстрее последовательного метода:
(рис 9.8) Сравнительный анализ эффективности последовательного алгоритма и параллельных алгоритмов быстрой сортировки (2-х ядерный компьютер)
Как можно видеть, на массиве из 8 388 608 элементов обе параллельные версии быстрой сортировки работают существенно быстрее последовательного варианта быстрой сортировки. Лучший результат показывает рекурсивная версия с ограниченной параллельностью, в которой для массивов размера менее 100 000 элементов вызывается рекурсивная последовательная версия, а для массивов большего размера создаются две параллельно работающие задачи.
Размер массива в данном эксперименте может показаться на первый взгляд странным, но он выбран таковым для того, чтобы можно было использовать лучшую по эффективности версию сортировки Бэтчера, накладывающую ограничения на размер массива (в данном случае N = 223).
О сортировке Бэтчера следует сказать особо. В этом эксперименте она показала наихудший результат, затратив на порядок больше времени, чем последовательная версия. Эта сортировка построена на операциях "сравнение – обмен", рассматриваемых как единое целое. Вначале сравниваются пары элементов массива, после чего массив становится дву- упорядоченным. На следующем этапе новые пары сравниваются таким образом, что поволяют получить четырех-упорядоченный массив. Затем строятся восьмерки упорядоченности, пока массив не будет полностью упорядочен. Все операции "сравнение – обмен" можно выполнять параллельно. Теоретически ожидается, что сортировка Бэтчера, несмотря на сложность организации, при распараллеливании вычислений работает быстрее в сравнении с последовательными вариантами . Но практика не всегда совпадает с теорией.
Ситуация здесь примерно такая же, как и с пирамидальным алгоритмом суммирования. Теоретически, обладая сложностью порядка O(logN), пирамидальный алгоритм должен работать значительнее эффективнее по времени, чем последовательный алгоритм со сложностью O(N). Но на практике это не так, поскольку на малых N последовательный алгоритм обогнать практически невозможно и нецелесообразно, а для больших значений N накладные расходы на организацию параллелизма не только съедают весь выигрыш от распараллеливания вычислений, но и приводят к дополнительным существенным затратам. Вот и в алгоритме Бэтчера накладные расходы слишком велики, чтобы им стоило пользоваться для сортировки больших массивов в рассматриваемых усовиях.
Следует заметить, что данные по сортировке массива приведены по результатам экспериментов на 2-х ядерном 32-х разрядном компьютере. Вот как выглядят в тех же условиях результаты работы на 4-х ядерном 64-х битном компьютере:
(рис 9.9) Сравнительный анализ эффективности последовательного алгоритма и параллельных алгоритмов быстрой сортировки (4-х ядерный компьютер)
Как видите, с увеличением числа ядер параллельные алгоритмы улучшают свои показатели в сравнении с последовательным алгоритмом. Первый из параллельных алгоритмов показывает результаты вдвое лучше последовательного алгоритма, второй – более чем в три раза.
Подводя общие итоги сравнительного анализа методов сортировки, следует сказать, что для массивов сравнительно небольшого размера (до миллиона элементов) сортировка относится в нашей классификации к задачам второго класса, где существует эффективный последовательный алгоритм, делающий нерациональным применение параллельных вычислений. Однако современная тенденция состоит в том, что оперативная память может быть очень большой, позволяющая, например, вести в оперативной памяти работу с большими базами данных. В этом случае приходится сортировать массивы с сотнями миллионов элементов. В таких ситуациях параллельные версии сортировки эффективны. Как показывают наши исследования, эффективные параллельные версии сортировки существуют, так что задачу сортировки сверхбольших массивов следует отнести к задачам третьего класса.
В предыдущих проектах основной целью являлось поиск параллельных алгоритмов, которые по времени были бы эффективнее последовательного алгоритма. Параллельные алгоритмы предусматривали распараллеливание по данным, когда один и тот же метод параллельно применяется к различным непересекающимся подмножествам исходной совокупности данных.
Проекты в решении TasksAndInstruments другого типа. Здесь изначально предполагается, что задача решается с использованием параллельных вычислений, так что о сравнении с последовательным алгоритмом речь не идет. По нашей классификации такие задачи относятся к третьему типу – к классу задач, ориентированных на параллельные вычисления.
Для таких задач при параллельных вычислениях могут использоваться общие ресурсы, прежде всего, общие данные, что может приводить к возникновению таких проблем как гонка данных и клинч. В проектах, входящих в решение TasksAndInstruments, рассматриваются именно такие задачи. Все эти задачи подробно рассмотрены в главе 5 учебного курса, а предлагаемые проекты являются улучшенной модификацией проектов, описанных в этой главе.
Решение TasksAndInstruments содержит 4 проекта – три из них представляют библиотеки классов, а четвертый является интерфейсным Windows Forms проектом с главной формой, позволяющей выбрать для исследования одну из четырех рассматриваемых задач. Вот как выглядит главная форма:
(рис 9.10) Главная форма проекта WindowsFormsTasksAndInstruments
В проекте, реализующем эту задачу, моделируется ситуация, приводящая к гонке данных и ее последствиям. Содержательные классы для этой задачи включены в динамическую библиотеку классов – проект ClassLibraryTasksAndInstruments. Вот как выглядит результаты эксперимента, приводящего к гонке данных:
(рис 9.11) Моделирование ситуации "гонки данных"
Простейшим инструментом, позволяющим справиться с гонкой данных, является оператор lock языка C#. Проект демонстрирует безопасную параллельную работу с банковским счетом с использованием этого инструмента. Результаты эксперимента выглядят в этом случае так:
(рис 9.12) Безопасная параллельная работа с банковским счетом
В проекте, реализующем эту задачу, моделируется ситуация, приводящая к клинчу, и показано, как можно справиться с этой проблемой. Поскольку клинч приводит к зависанию компьютера, то убедительным доказательством возникновения этой ситуации является запуск проекта на собственном компьютере.
Как и в предыдущей задаче, содержательные классы включены в проект ClassLibraryTasksAndInstruments, а интерфейс проекта реализован в одной из форм проекта WindowsFormsTasksAndInstruments . Покажем, как выглядят результаты эксперимента, позволяющего справиться с ситуацией клинча:
(рис 9.13) Решение проблемы "клинча"
Блокировка является одним из важнейших механизмов параллельных вычислений, когда приходится работать с общими ресурсами. Существуют различные инструменты, позволяющие осуществлять нужный стиль блокировки в зависимости от возникающей ситуации. Инструмент, заданный классом ReaderWriterLockSlim позволяет реализовать мягкий метод блокировки, применимый в задачах, соответствующих известному образцу (паттерну) "Читатели и писатели".
В рассматриваемой задаче моделируется совместная работа по разработке программного проекта. Моделируется параллельная работа трех групп – разработчиков проекта, тестеров и программистов, играющих роль пользователей проекта. Программисты, представляющие "читателей", имеют одновременный доступ к очередной версии программного проекта, созданного разработчиками и редактируемой тестерами.
Содержательные классы, позволяющие построить модель решения задачи, помещены в проект ClassLibraryReadersWriters. Интерфейс реализован одной из форм проекта WindowsFormsTasksAndInstruments. В сравнении с проектом решения этой задачи, описанном в главе 5, изменению подвергся не только интерфейс, но и внесены некоторые поправки, улучшающие, по моему мнению, содержательную часть проекта. Вот как теперь выглядит интерфейс для пользователя, работающего с проектом:
(рис 9.14) Мягкие методы блокировки. Модель "Читатели и писатели"
Классическая задача параллельного программирования, предложенная Э. Дейкстрой, демонстрирует работу с общими ресурсами, приводящую к клинчу, если не предпринимать специальных мер по его предупреждению. В проекте используется инструмент блокировки, называемый семафором, реализованный классом FCL – Semaphore.
Содержательные классы, моделирующие обедающих философов, помещены в проект ClassLibraryFilosofDinner, а интерфейс реализован одной из форм интерфейсного проекта. По сравнению с описанием проекта в лекциях изменен интерфейс проекта. Он стал более удобным для проведения исследований. Вот результат некоторого эксперимента:
(рис 9.15) Обедающие философы
В данном эксперименте в отведенное для обеда время все пять философов успешно размышляли и все же успешно ели и остались сытыми. Введение жесткого правила, обеспечивающего "правильный" порядок взятия вилок обедающими философами, позволило не допустить возникновения ситуации клинча.
Существует класс задач, изначально предполагающих параллельное выполнение и работу с общими ресурсами. При программировании таких задач могут возникать серьезные проблемы, не имеющие аналогов в последовательном программировании. Из-за этих проблем результаты работы могут быть некорректными, в ряде ситуаций приложение может вообще "зависнуть". В проектах решения TaskAndInstruments рассматриваются задачи, где такие проблемы возникают и показано, как можно с ними справляться.
Данное решение содержит всего один проект – WindowsFormsGame15. Это большой проект, который упоминался, но не рассматривался в учебном курсе. Он является хорошей иллюстрацией всех положений, рассмотренных в последней лекции учебника, посвященной описанию взаимодействия двух процессов – управляющего и управляемого. Управляющий процесс реализуется интерфейсным классом, а управляемый процесс отдельным классом. Оба процесса работают в разных потоках. Управляемый процесс в ходе работы выводит значения наблюдаемых параметров в соответствующие элементы интерфейса. Пользователь, управляющий процессом, задает управляющие воздействия, влияющие на ход управляемого процесса.
В главе 8 подробно описаны два способа организации взаимодействия таких процессов – взаимодействие, основанное на взаимных ссылках, и взаимодействие, основанное на обмене событиями. Оба способа взаимодействия иллюстрировались специальными учебными проектами. Данное решение рассматривает более интересный проект, обладающий чертами настоящего полноценного приложения.
Проект представляет реализацию известной игры в 15, где требуется упорядочить случайную перестановку из 15 элементов на поле из 4 * 4 клеток.
Помимо решения основной задачи - организации взаимодействия двух процессов, работающих в разных потоках, проект демонстрирует:
Остановимся более подробно на организации взаимодействия двух процессов. Управляемый процесс, реализуемый классом Game15, в качестве наблюдаемых параметров выводит информацию о каждом сделанном компьютером ходе, и о числе упорядоченных элементов. Информация о сделанных компьютером ходах отображается в текстовом виде, в элементе управления ProgressBar и графически в игровом поле.
Какие действия, используя интерфейс проекта, может выполнять пользователь? Он может выбрать файл с заранее подготовленной конфигурацией исходной перестановки, получить новую случайную перестановку, может сохранить перестановку в файле. В ходе игры он может менять скорость визуального показа ходов, сделанных компьютером, он может остановить процесс игры, проанализировать запись ходов игры и при желании продолжить игру. Наконец он может заменить компьютер и сам выступить в роли игрока, соревнуясь с компьютером, стараясь для фиксированной перестановки упорядочить ее за меньшее число ходов, чем это делает компьютер.
Следует заметить, что обыграть компьютер в этом смысле не так уж трудно. Алгоритм, который я написал, близок к тому, как играет рядовой игрок. Он корректно работает, но не оптимизирован.
В интернете можно найти описание различных алгоритмов этой игры, более эффективных по числу ходов, требуемых для упорядочивания.
У программистов есть все возможности улучшения данного проекта. Конечно, наиболее интересно написание версии этого проекта, где взаимодействие основано на обмене событиями.
В данной версии взаимодействие основано на взаимных ссылках. Интерфейсный класс содержит ссылку и создает объект класса Game15. В интерфейсном классе создается дочерний поток, начинающий выполнять метод класса Game15, инициирующий игру. Класс Game15, в свою очередь, содержит ссылку на интерфейсный класс, что позволяет ему выводить наблюдаемый параметры в элементы интерфейса, используя безопасный метод Invoke для работы с элементами управления, представляющими общие ресурсы.
При организации взаимодействия, основанного на ссылках, как интерфейсный класс, так и управляемый класс должны быть классами одного проекта. Класс Game15 нельзя поместить в DLL, поскольку при работе в Dot Net, в частности при создании приложений на C#, запрещается создавать проекты, связанные циклическими ссылками ( проект А не может ссылаться на проект В, ссылающийся на проект А, что имело бы место в нашем случае, если класс Game15 поместить в другой проект - динамическую библиотеку классов).
В заключение приведу снимок экрана в процессе игры 15:
(рис 9.16) Прерывание пользователем процесса игры 15
Примеры проектов Вы можете скачать здесь.
Предлагаемые программные проекты на C# построены по материалам курса по "Параллельным вычислениям". Проекты написаны по завершении работы над текстом курса и поэтому реализация может отличаться от той, что дана в тексте курса. В некоторых проектах появились методы, не описанные в тексте лекций. С другой стороны не все задачи, рассмотренные в ходе лекций, нашли отражение в предлагаемых проектах.
Проекты являются важным дополнительным материалом к курсу лекций. Размещение их на сайте преследует три цели:
Проекты, связанные единой тематикой, объединены в Решения (Solution):
Sum объединяет проекты по теме суммирования;Integral связано с задачей вычисления определенного интеграла;Sorting объединяет проекты, реализующие различные методы сортировки; TasksAndInstruments объединяет проекты, позволяющие анализировать проблемы гонки данных, клинча и способы преодоления этих проблем.Game15 исследует важную тему взаимодействия управляющего и управляемого процессов, работающих в разных потоках. Оно представляет реализацию известной игры 15 и обладает чертами полноценного приложения с развитым интерфейсом, меню, файлами и другими атрибутами реальных приложений. Задача вычисления суммы $$S=\sum_k a_k$$ является классической задачей математики и программирования. При рассмотрении параллельных вычислений ей уделяется большое внимание.
Решение Sum содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов вычисления суммы. Построенные проекты позволяют также оценить эффективность инструментальных средств, реализующих в программах на C# параллельные вычисления.
В проектах рассматриваются три варианта вычисления суммы, где $$a_k$$ это :
Анализируются три варианта параллельных алгоритмов вычисления суммы – пирамидальный, сегментный и шаговый. Рассматриваются также различные вариации инструментария, реализующего параллельные вычисления:
For класса Parallel;Thtead;Task.Проекты, включенные в Решение Sum, следует рассматривать как дополнение, полезное при изучении материалов главы 3 (раздел "Суммирование") и глав 4 -7 учебника "Параллельные вычисления и многопоточное программирование.
Решение Sum содержит 5 проектов. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibrarySum, представляющего динамическую библиотеку классов. Эта библиотека содержит три класса – Massiv, Infinite_Series, Function_Sum. Каждый из этих классов содержит методы , реализующие последовательные и параллельные алгоритмы для трех изучаемых проблем – суммирования элементов массива, сходящихся рядов и конечных сумм, элементы которых заданы значениями функций.
Четыре проекта, входящие в Решение Sum, являются интерфейсными проектами. Три из них – ConsoleMassive_Sum, ConsoleArcSin и ConsoleFunction_Sum реализуют консольный интерфейс. Каждый из этих трех проектов позволяет в консоли анализировать три изучаемые проблемы. Четвертый интерфейсный проект – WindowsFormSum представляет классическое Windows Form приложение с главной формой и тремя формами, спроектированными для анализа рассматриваемых проблем.
Начну с общих выводов, связанных с проблемой распараллеливания вычислений. Все задачи можно условно разделить на пять классов:
Что можно сказать о задаче суммирования? К какому из классов ее следует отнести? Начнем с задачи суммирования элементов массива. Прежде, чем дать ответ, рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательного и различных параллельных алгоритмов по нахождению суммы элементов массивов различного размера, хранящих элементы вещественного типа (double). Вот какие результаты получены на моем компьютере (64-х битный компьютер с 6 Гб оперативной памяти и 4-мя физическими ядрами) при запуске Windows проекта из Решения Sum:
(рис 9.1) Суммирование элементов массивов разного размера
Как можно видеть, все алгоритмы – последовательный и параллельные - прекрасно справляются с задачей. Время суммирования вплоть до массива, содержащего 10000000 -десять миллионов элементов, составляет менее 0,1 секунды. В такой ситуации параллельные алгоритмы не имеют преимущества перед последовательным алгоритмом. Так что задачу нахождения суммы элементов массива, также как нахождение максимального элемента и другие подобные ей задачи, следует отнести ко второму классу, где применение параллельных алгоритмов хотя и возможно, но нецелесообразно на компьютерах подобного класса.
Хочу обратить внимание на одну особенность, связанную с результатами экспериментов. Время, замеряемое в экспериментах, содержит погрешности. Этих погрешностей избежать нельзя, поскольку они связаны с тем, как работает таймер в многозадачной операционной системе. Квант времени составляет 0,015 секунды, а ошибка измерения может достигать нескольких квантов. Для сравнения приведу результаты вычисления суммы элементов массива в тех же условиях, что и на рис. 1, но для другого сеанса работы:
(рис 9.2) Суммирование элементов массива. Эксперимент 2
Как видите, результаты слегка отличаются от результатов первого эксперимента. Но замечу, что во всех случаях последовательный алгоритм выигрывает сотые доли секунды у любых параллельных алгоритмов на массиве из 10 миллионов элементов.
Приведу теперь результаты экспериментов для задачи суммирования бесконечного сходящегося ряда на примере вычисления значений функции Arcsin(x). Эта задача интересна еще и тем, что эффективный последовательный алгоритм использует рекуррентное соотношение для вычисления очередного члена суммы. При распараллеливании такого эффективного приема не существует. Рекуррентное соотношение хотя и можно построить для параллельного шагового алгоритма, но оно значительно сложнее в сравнении с последовательным вариантом. Учитывая еще, что последовательный алгоритм практически мгновенно решает эту задачу, то у параллельного алгоритма нет шансов выиграть, что и подтверждается результатами экспериментов:
(рис 9.3) Суммирование сходящегося ряда
Можно видеть, что как последовательный, так и параллельный алгоритм прекрасно справляются с задачей. Время многократного (10000 повторов) вычисления значения функции менее 0,1 секунды. Но опять-таки параллельный алгоритм не имеет преимущества перед последовательным алгоритмом. Так что и эту задачу следует отнести ко второму классу, где применение параллельных алгоритмов хотя и возможно, но нецелесообразно на компьютерах подобного класса.
Полагаю, что справедлива следующая гипотеза:
Задачи с линейной временной сложностью относятся ко второму классу.
Для того чтобы параллельные алгоритмы выигрывали у последовательных алгоритмов исходная задача должно иметь по крайней мере квадратичную сложность. Суммирование конечного ряда, где каждый член ряда требует вычисления значения функции с линейной сложностью $$O(n)$$, относится к подобным задачам, поскольку для вычисления суммы ряда необходимо вычислить n членов ряда. Подробное описание примера приведено в 7-й главе учебника в разделе, посвященном методу Parallel.For, а его реализация представлена в классе Function_Sum. Вот как выглядят результаты эксперимента:
(рис 9.4) Суммирование конечного ряда
Рассматриваемую нами задачу, имеющую квадратичную временную сложность $$O(n^2)$$ следует отнести к третьему классу задач, допускающих эффективное распараллеливание. В главе 7 подробно обсуждается алгоритм, позволяющий перейти от исходной частично распараллеливаемой задачи к практически полному распараллеливанию. Анализируя приведенные результаты можно видеть, что последовательному алгоритму понадобилось ощутимо заметное время на вычисления – более 5 секунд. В то же время все параллельные алгоритмы выигрывают у последовательного алгоритма, лучший из них выигрывает более чем в 4 раза, что согласуется с числом ядер компьютера. Лучшим параллельным алгоритмом является алгоритм, построенный с использованием метода Parallel.For. Но и методы, использующие непосредственно потоки и объекты класса Task ведут себя вполне достойно на этой задаче.
Можно сделать и более общий вывод. Для потенциально распараллеливаемых задач со сложностью $$O(n^2)$$ и выше следует искать эффективные параллельные алгоритмы, позволяющие ощутимо сократить время решения задачи. Поиск таких алгоритмов непростая задача. Эта тема будет обсуждаться и при рассмотрении других проектов, дополняющих и сопровождающих учебник "Параллельные вычисления и многопоточное программирование".
Задача вычисления интеграла $$S=\int^b_a f(x)dx$$ также относится к классическим задачам математики и программирования. При рассмотрении параллельных вычислений в учебном курсе она достаточно подробно обсуждается. Вычисление интеграла аналогично задаче суммирования, поскольку практически вычисление значения S сводится к вычислению суммы $$S=\sum_k f(x_k)delta_x$$.
Решение Integral содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов вычисления интеграла.
Решение Integral содержит 2 проекта. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibraryIntegral, представляющем динамическую библиотеку классов. Библиотека содержит один класс – Integral, включающий методы, реализующие последовательные и параллельные алгоритмы вычисления интеграла. Параллельный алгоритм построен на использовании инструментария Parallel.For.
Для распараллеливания используется стратегия сегментного алгоритма вычисления суммы. Интервал интегрирования разбивается на k сегментов, на каждом из которых для вычисления интеграла используется обычный последовательный алгоритм. Вычисление интегралов на отдельных сегментах ведется параллельно. Эта стратегия оказывается весьма эффективной, даже в том случае, когда вычисление интеграла на каждом сегменте ведется последовательно. Выигрыш по времени может достигать десятки раз при относительно небольшой потери точности. В учебном курсе поясняется причина такой эффективности. Подынтегральная функция на каждом участке ведет себя более гладко, в сравнении со всем интервалом интегрирования. По этой причине на каждом сегменте достаточно быстро достигается нужная точность вычислений.
Что касается последовательного метода вычисления интеграла на отрезке, то в классе Integral представлены два классических метода – более простой в реализации метод прямоугольников и более эффективный метод трапеций.
Интерфейсный проект – WindowsForm Integral представляет классическое Windows Form приложение, спроектированное для анализа двух проблем – анализа эффективности последовательного и параллельного алгоритма и анализа влияния числа сегментов на эффективность решения задачи.
Исследование ведется на примере подынтегральной функции, задающей гармонические колебания. Для интеграла от этой функции известно точное значение, что позволяет следить за точностью решения задачи. Интерфейс проекта позволяет легко менять параметры функции – амплитуду и частоту колебаний, также как и интервал интегрирования.
Рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательного и параллельного алгоритмов в зависимости от числа сегментов разбиения интервала интегрирования:
(рис 9.5) Сравнительный анализ эффективности последовательного и параллельного алгоритмов (метод прямоугольников)
Анализируя эти результаты можно видеть, что интегрирование с разбиением на сегменты дает существенный выигрыш по времени. В данном эксперименте время сокращается в 15 раз при делении на 64 сегмента с 14, 4 секунды до 0, 97 секунды. Это ускорение достигается только за счет разделения на сегменты. Требуемая точность вычислений 108 сохраняется.
Параллельный алгоритм выигрывает во всех случаях у последовательного алгоритма. За счет параллелизма достигается эффективное 4-х кратное ускорение, как и должно быть для компьютера с 4-мя ядрами.
Если вместо метода прямоугольников применять для вычисления интеграла значительно более эффективный метод трапеций, то при тех же данных последовательный алгоритм работает намного быстрее, поэтому и выиграть у него можно относительно немного. Вот каковы результаты эксперимента, когда в тех же условиях применяется более эффективный метод трапеций:
(рис 9.6) Сравнительный анализ эффективности последовательного и параллельного алгоритмов (метод трапеций)
Анализируя эти результаты, можно видеть, что в данном случае последовательный алгоритм без разбиения интервала интегрирования на сегменты прекрасно справляется с задачей, затрачивая на решение 0, 015 секунды. Хотя параллельные алгоритмы работают не хуже, но говорить о реальном повышении эффективности вряд ли стоит.
Подводя итоги, можно сказать, что задача вычисления интеграла относится к задачам второго и третьего типа в зависимости от сложности вычисления подынтегральной функции. Когда подынтегральная функция вычислительно простая, как в нашем примере, то фактически задача вычисления интеграла имеет линейную сложность и относится ко второму типу, когда распараллеливание возможно, но не имеет особого смысла ввиду эффективной работы последовательного алгоритма. Для сложной в вычислительном отношении функции задачу следует относить к третьему типу и применять параллельные алгоритмы с разбиением интервала интегрирования на сегменты. Применение метода прямоугольников по существу имитирует увеличение сложности вычисления функции, демонстрируя, каков эффект можно получить при распараллеливании этой задачи.
Решение Sorting содержит проекты, позволяющие провести сравнительный анализ эффективности последовательных и параллельных алгоритмов сортировки массивов. В проектах анализируются три алгоритма:
Первые две сортировки рассматриваются в учебном курсе. Сортировка Бэтчера, которая создавалась как сортировка, предназначенная для параллельного выполнения, в текст учебника не вошла. Одна из причин в том, что хотя алгоритм сортировки достаточно прост, но объяснение его корректности совсем не просто.
Решение Sorting содержит 3 проекта. Следуя принципу разделения интерфейса и бизнес-логики, содержательная часть реализована в проекте ClassLibrary Sorting, представляющем динамическую библиотеку классов. Библиотека содержит один класс – Sorting, включающий методы, реализующие последовательные и параллельные алгоритмы сортировки массива.
Для пузырьковой сортировки построен метод, реализующий последовательную классическую версию, и метод, реализующий параллельный вариант пузырьковой сортировки. Параллельный вариант реализует идею шагового алгоритма. Сортируемый массив разбивается на k групп, в каждую из которых включаются элементы, отстоящие на расстоянии k. Все группы сортируются параллельно, а затем выполняется последовательная операция слияния k-упорядоченных групп в единый массив.
Для быстрой сортировки наряду с последовательной версией рассматриваются два параллельных метода – один реализует идею шагового алгоритма, другой – реализует рекурсивный вариант сортировки с ограниченным распараллеливанием.
Для рекурсивного варианта с ограничением на параллелизм в зависимости от объема массива вызывается либо последовательная версия либо параллельная версия, использующая инструментарий параллельных задач (класс Task). Этот вариант в лекциях курса не рассматривался, хотя, как можно будет увидеть по результатам экспериментов, он наиболее эффективен при сортировке больших массивов.
Для сортировки Бэтчера построены две параллельные версии. Одна реализует алгоритм, описанный в третьем томе "Искусство программирования" - фундаментальном труде Дональда Кнута. Эта версия (у Кнута это явно не оговорено) корректно работает только тогда , когда размер массива N является степенью двойки. Вторая версия работает для массивов любого размера.
Два проекта WindowsFormsSorting и ConsoleSorting являются интерфейсным проектами. Первый удобен при проведении запланированных исследований, второй – при проведении экспериментов, проверки различных возникающих гипотез.
Рассмотрим результаты экспериментов по анализу сравнительной эффективности последовательных и параллельных алгоритмов. Посмотрим, что может дать параллельный вариант пузырьковой сортировки в сравнении с его последовательным собратом:
(рис 9.7) Сравнительный анализ эффективности последовательного и параллельного алгоритмов пузырьковой сортировки
Результаты показывают, что параллельный вариант "пузырька" сортировки массива из 100 000 элементов при разбиении массива на 100 групп эффективнее по времени более чем в 100 раз, затрачивая на сортировку менее секунды, в то время, когда последовательный вариант затрачивает более полутора минут. Как видите, распараллеливание дает существенный эффект. Радость этого успеха слегка портит тот факт, что существует другой последовательный алгоритм, который сортирует этот массив еще быстрее. Можно видеть, что последовательный алгоритм быстрой сортировки справляется с задачей на порядок лучше параллельного пузырька, затрачивая на сортировку сотые доли секунды.
Главный вопрос, на какой хотелось получить ответ при изучении методов сортировки, можно ли предложить параллельный вариант сортировки, работающий быстрее последовательного варианта быстрой сортировки? В тексте лекций положительного ответа так и не было дано. Приведу результаты, показывающие, что параллельные методы сортировки могут работать быстрее последовательного метода:
(рис 9.8) Сравнительный анализ эффективности последовательного алгоритма и параллельных алгоритмов быстрой сортировки (2-х ядерный компьютер)
Как можно видеть, на массиве из 8 388 608 элементов обе параллельные версии быстрой сортировки работают существенно быстрее последовательного варианта быстрой сортировки. Лучший результат показывает рекурсивная версия с ограниченной параллельностью, в которой для массивов размера менее 100 000 элементов вызывается рекурсивная последовательная версия, а для массивов большего размера создаются две параллельно работающие задачи.
Размер массива в данном эксперименте может показаться на первый взгляд странным, но он выбран таковым для того, чтобы можно было использовать лучшую по эффективности версию сортировки Бэтчера, накладывающую ограничения на размер массива (в данном случае N = 223).
О сортировке Бэтчера следует сказать особо. В этом эксперименте она показала наихудший результат, затратив на порядок больше времени, чем последовательная версия. Эта сортировка построена на операциях "сравнение – обмен", рассматриваемых как единое целое. Вначале сравниваются пары элементов массива, после чего массив становится дву- упорядоченным. На следующем этапе новые пары сравниваются таким образом, что поволяют получить четырех-упорядоченный массив. Затем строятся восьмерки упорядоченности, пока массив не будет полностью упорядочен. Все операции "сравнение – обмен" можно выполнять параллельно. Теоретически ожидается, что сортировка Бэтчера, несмотря на сложность организации, при распараллеливании вычислений работает быстрее в сравнении с последовательными вариантами . Но практика не всегда совпадает с теорией.
Ситуация здесь примерно такая же, как и с пирамидальным алгоритмом суммирования. Теоретически, обладая сложностью порядка O(logN), пирамидальный алгоритм должен работать значительнее эффективнее по времени, чем последовательный алгоритм со сложностью O(N). Но на практике это не так, поскольку на малых N последовательный алгоритм обогнать практически невозможно и нецелесообразно, а для больших значений N накладные расходы на организацию параллелизма не только съедают весь выигрыш от распараллеливания вычислений, но и приводят к дополнительным существенным затратам. Вот и в алгоритме Бэтчера накладные расходы слишком велики, чтобы им стоило пользоваться для сортировки больших массивов в рассматриваемых усовиях.
Следует заметить, что данные по сортировке массива приведены по результатам экспериментов на 2-х ядерном 32-х разрядном компьютере. Вот как выглядят в тех же условиях результаты работы на 4-х ядерном 64-х битном компьютере:
(рис 9.9) Сравнительный анализ эффективности последовательного алгоритма и параллельных алгоритмов быстрой сортировки (4-х ядерный компьютер)
Как видите, с увеличением числа ядер параллельные алгоритмы улучшают свои показатели в сравнении с последовательным алгоритмом. Первый из параллельных алгоритмов показывает результаты вдвое лучше последовательного алгоритма, второй – более чем в три раза.
Подводя общие итоги сравнительного анализа методов сортировки, следует сказать, что для массивов сравнительно небольшого размера (до миллиона элементов) сортировка относится в нашей классификации к задачам второго класса, где существует эффективный последовательный алгоритм, делающий нерациональным применение параллельных вычислений. Однако современная тенденция состоит в том, что оперативная память может быть очень большой, позволяющая, например, вести в оперативной памяти работу с большими базами данных. В этом случае приходится сортировать массивы с сотнями миллионов элементов. В таких ситуациях параллельные версии сортировки эффективны. Как показывают наши исследования, эффективные параллельные версии сортировки существуют, так что задачу сортировки сверхбольших массивов следует отнести к задачам третьего класса.
В предыдущих проектах основной целью являлось поиск параллельных алгоритмов, которые по времени были бы эффективнее последовательного алгоритма. Параллельные алгоритмы предусматривали распараллеливание по данным, когда один и тот же метод параллельно применяется к различным непересекающимся подмножествам исходной совокупности данных.
Проекты в решении TasksAndInstruments другого типа. Здесь изначально предполагается, что задача решается с использованием параллельных вычислений, так что о сравнении с последовательным алгоритмом речь не идет. По нашей классификации такие задачи относятся к третьему типу – к классу задач, ориентированных на параллельные вычисления.
Для таких задач при параллельных вычислениях могут использоваться общие ресурсы, прежде всего, общие данные, что может приводить к возникновению таких проблем как гонка данных и клинч. В проектах, входящих в решение TasksAndInstruments, рассматриваются именно такие задачи. Все эти задачи подробно рассмотрены в главе 5 учебного курса, а предлагаемые проекты являются улучшенной модификацией проектов, описанных в этой главе.
Решение TasksAndInstruments содержит 4 проекта – три из них представляют библиотеки классов, а четвертый является интерфейсным Windows Forms проектом с главной формой, позволяющей выбрать для исследования одну из четырех рассматриваемых задач. Вот как выглядит главная форма:
(рис 9.10) Главная форма проекта WindowsFormsTasksAndInstruments
В проекте, реализующем эту задачу, моделируется ситуация, приводящая к гонке данных и ее последствиям. Содержательные классы для этой задачи включены в динамическую библиотеку классов – проект ClassLibraryTasksAndInstruments. Вот как выглядит результаты эксперимента, приводящего к гонке данных:
(рис 9.11) Моделирование ситуации "гонки данных"
Простейшим инструментом, позволяющим справиться с гонкой данных, является оператор lock языка C#. Проект демонстрирует безопасную параллельную работу с банковским счетом с использованием этого инструмента. Результаты эксперимента выглядят в этом случае так:
(рис 9.12) Безопасная параллельная работа с банковским счетом
В проекте, реализующем эту задачу, моделируется ситуация, приводящая к клинчу, и показано, как можно справиться с этой проблемой. Поскольку клинч приводит к зависанию компьютера, то убедительным доказательством возникновения этой ситуации является запуск проекта на собственном компьютере.
Как и в предыдущей задаче, содержательные классы включены в проект ClassLibraryTasksAndInstruments, а интерфейс проекта реализован в одной из форм проекта WindowsFormsTasksAndInstruments . Покажем, как выглядят результаты эксперимента, позволяющего справиться с ситуацией клинча:
(рис 9.13) Решение проблемы "клинча"
Блокировка является одним из важнейших механизмов параллельных вычислений, когда приходится работать с общими ресурсами. Существуют различные инструменты, позволяющие осуществлять нужный стиль блокировки в зависимости от возникающей ситуации. Инструмент, заданный классом ReaderWriterLockSlim позволяет реализовать мягкий метод блокировки, применимый в задачах, соответствующих известному образцу (паттерну) "Читатели и писатели".
В рассматриваемой задаче моделируется совместная работа по разработке программного проекта. Моделируется параллельная работа трех групп – разработчиков проекта, тестеров и программистов, играющих роль пользователей проекта. Программисты, представляющие "читателей", имеют одновременный доступ к очередной версии программного проекта, созданного разработчиками и редактируемой тестерами.
Содержательные классы, позволяющие построить модель решения задачи, помещены в проект ClassLibraryReadersWriters. Интерфейс реализован одной из форм проекта WindowsFormsTasksAndInstruments. В сравнении с проектом решения этой задачи, описанном в главе 5, изменению подвергся не только интерфейс, но и внесены некоторые поправки, улучшающие, по моему мнению, содержательную часть проекта. Вот как теперь выглядит интерфейс для пользователя, работающего с проектом:
(рис 9.14) Мягкие методы блокировки. Модель "Читатели и писатели"
Классическая задача параллельного программирования, предложенная Э. Дейкстрой, демонстрирует работу с общими ресурсами, приводящую к клинчу, если не предпринимать специальных мер по его предупреждению. В проекте используется инструмент блокировки, называемый семафором, реализованный классом FCL – Semaphore.
Содержательные классы, моделирующие обедающих философов, помещены в проект ClassLibraryFilosofDinner, а интерфейс реализован одной из форм интерфейсного проекта. По сравнению с описанием проекта в лекциях изменен интерфейс проекта. Он стал более удобным для проведения исследований. Вот результат некоторого эксперимента:
(рис 9.15) Обедающие философы
В данном эксперименте в отведенное для обеда время все пять философов успешно размышляли и все же успешно ели и остались сытыми. Введение жесткого правила, обеспечивающего "правильный" порядок взятия вилок обедающими философами, позволило не допустить возникновения ситуации клинча.
Существует класс задач, изначально предполагающих параллельное выполнение и работу с общими ресурсами. При программировании таких задач могут возникать серьезные проблемы, не имеющие аналогов в последовательном программировании. Из-за этих проблем результаты работы могут быть некорректными, в ряде ситуаций приложение может вообще "зависнуть". В проектах решения TaskAndInstruments рассматриваются задачи, где такие проблемы возникают и показано, как можно с ними справляться.
Данное решение содержит всего один проект – WindowsFormsGame15. Это большой проект, который упоминался, но не рассматривался в учебном курсе. Он является хорошей иллюстрацией всех положений, рассмотренных в последней лекции учебника, посвященной описанию взаимодействия двух процессов – управляющего и управляемого. Управляющий процесс реализуется интерфейсным классом, а управляемый процесс отдельным классом. Оба процесса работают в разных потоках. Управляемый процесс в ходе работы выводит значения наблюдаемых параметров в соответствующие элементы интерфейса. Пользователь, управляющий процессом, задает управляющие воздействия, влияющие на ход управляемого процесса.
В главе 8 подробно описаны два способа организации взаимодействия таких процессов – взаимодействие, основанное на взаимных ссылках, и взаимодействие, основанное на обмене событиями. Оба способа взаимодействия иллюстрировались специальными учебными проектами. Данное решение рассматривает более интересный проект, обладающий чертами настоящего полноценного приложения.
Проект представляет реализацию известной игры в 15, где требуется упорядочить случайную перестановку из 15 элементов на поле из 4 * 4 клеток.
Помимо решения основной задачи - организации взаимодействия двух процессов, работающих в разных потоках, проект демонстрирует:
Остановимся более подробно на организации взаимодействия двух процессов. Управляемый процесс, реализуемый классом Game15, в качестве наблюдаемых параметров выводит информацию о каждом сделанном компьютером ходе, и о числе упорядоченных элементов. Информация о сделанных компьютером ходах отображается в текстовом виде, в элементе управления ProgressBar и графически в игровом поле.
Какие действия, используя интерфейс проекта, может выполнять пользователь? Он может выбрать файл с заранее подготовленной конфигурацией исходной перестановки, получить новую случайную перестановку, может сохранить перестановку в файле. В ходе игры он может менять скорость визуального показа ходов, сделанных компьютером, он может остановить процесс игры, проанализировать запись ходов игры и при желании продолжить игру. Наконец он может заменить компьютер и сам выступить в роли игрока, соревнуясь с компьютером, стараясь для фиксированной перестановки упорядочить ее за меньшее число ходов, чем это делает компьютер.
Следует заметить, что обыграть компьютер в этом смысле не так уж трудно. Алгоритм, который я написал, близок к тому, как играет рядовой игрок. Он корректно работает, но не оптимизирован.
В интернете можно найти описание различных алгоритмов этой игры, более эффективных по числу ходов, требуемых для упорядочивания.
У программистов есть все возможности улучшения данного проекта. Конечно, наиболее интересно написание версии этого проекта, где взаимодействие основано на обмене событиями.
В данной версии взаимодействие основано на взаимных ссылках. Интерфейсный класс содержит ссылку и создает объект класса Game15. В интерфейсном классе создается дочерний поток, начинающий выполнять метод класса Game15, инициирующий игру. Класс Game15, в свою очередь, содержит ссылку на интерфейсный класс, что позволяет ему выводить наблюдаемый параметры в элементы интерфейса, используя безопасный метод Invoke для работы с элементами управления, представляющими общие ресурсы.
При организации взаимодействия, основанного на ссылках, как интерфейсный класс, так и управляемый класс должны быть классами одного проекта. Класс Game15 нельзя поместить в DLL, поскольку при работе в Dot Net, в частности при создании приложений на C#, запрещается создавать проекты, связанные циклическими ссылками ( проект А не может ссылаться на проект В, ссылающийся на проект А, что имело бы место в нашем случае, если класс Game15 поместить в другой проект - динамическую библиотеку классов).
В заключение приведу снимок экрана в процессе игры 15:
(рис 9.16) Прерывание пользователем процесса игры 15
Примеры проектов Вы можете скачать здесь.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.