Учебно-методическое пособие рекомендовано учебно-методическим советом Международного университета природы, общества и человека (стр. 3 из 11)

2. Дана последовательность символов С = {с0…сn–1} и символ b. Создать многопоточное приложение для определения количество вхождений символа b в строку C. Количество потоков является входным параметром программы, количество символов в строке может быть не кратно количеству потоков.

3. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска суммы Σai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

4. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска произведения чисел a0*а1*…*an–1. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

5. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска максимального ai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

6. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска минимального ai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

7. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска всех ai, являющихся простыми числами. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

8. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска всех ai, являющихся квадратами, любого натурального числа.

9. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для вычисления выражения a0-а1+a2-а3+a4-а5+...

10. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска суммы Σai, где ai – четные числа.

11. Изготовление знаменитого самурайского меча – катаны происходит в три этапа. Сначала младший ученик мастера выковывает заготовку будущего меча. Затем старший ученик мастера закаливает меч в трех водах – кипящей, студеной и теплой. И в конце мастер собственноручно изготавливает рукоять меча и наносит узоры. Требуется создать многопоточное приложение, в котором мастер и его ученики представлены разными потоками. Изготовление меча представить в виде разных арифметических операций над глобальной переменной.

12. Командиру N-ской ВЧ полковнику Кузнецову требуется перемножить два секретных числа. Полковник Кузнецов вызывает дежурного по части лейтенанта Смирнова и требует в течение получаса предоставить ему ответ. Лейтенант Смирнов будит старшего по караулу сержанта Петрова и приказывает ему в 15 минут предоставить ответ. Сержант Петров вызывает к себе рядового Иванова, бывшего студента, и поручает ему ответственное задание по определению произведения. Рядовой Иванов успешно справляется с поставленной задачей и ответ по цепочке передается полковнику Кузнецову. Требуется создать многопоточное приложение, в котором все военнослужащие от полковника до рядового моделируются потоками одного вида.

13. Даны результаты сдачи экзамена по курсу «Параллельные и распределённые вычисления» по группам. Требуется создать многопоточное приложение, вычисляющее средний балл. Потоки должны осуществлять вычисления параллельно по группам. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество групп может быть не кратно количеству потоков.

14. Охранное агентство разработало новую систему управления электронными замками. Для открытия двери клиент обязан произнести произвольную фразу из 25 слов. В этой фразе должно встречаться заранее оговоренное слово, причем только один раз. Требуется создать многопоточное приложение, управляющее замком. Потоки должны осуществлять сравнение параллельно по словам.

15. Среди студентов нашего университета проведен опрос с целью определения процента студентов, знающих точную формулировку правила Буравчика. В результате собраны данные о количестве знатоков на каждом направлении по группам. Известно, что всего в филиале обучается 500 студентов. Требуется создать многопоточное приложение для определения процента знающих правило Буравчика студентов. Потоки должны осуществлять поиск количества знатоков по факультету. Искомый процент определяет главный поток. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество направлений может быть не кратно количеству потоков.

16. Руководство заготовительной компании «Рога и Копыта» проводит соревнование по заготовке рогов среди своих региональных отделений. Все данные по результатам заготовки рогов (заготовитель, его результат) хранятся в общей базе данных по отделениям. Требуется создать многопоточное приложение для поиска лучшего заготовителя. Потоки должны осуществлять поиск победителя параллельно по отделениям. Главный поток определит победителя. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество отделений может быть не кратно количеству потоков.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №2. СИНХРОНИЗАЦИЯ ПОТОКОВ В ОС WINDOWS

Цель работы

Изучить работу с критическими секциями. Научиться выделять «проблемные» фрагменты алгоритма и защищать их с помощью критических секций.

Порядок выполнения практических заданий

Рассмотреть представленные примеры, и разработать приложения на их основе.

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

Реализовать алгоритм с применением функций WinAPI и протестировать его на нескольких примерах.

Литературные источники

1. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учётом специфики 64-разрядной версии Windows/ Рихтер Дж. — СПб.:Питер, 2001. — 752с.

2. Эндрюс Г.Р. Основы многопоточного, параллельного и распределённого программирования/ Эндрюс Г.Р. — М.: «Вильямс», 2003. — 512с.

3. Хованский Е.П. “Лабораторные работы по курсу Параллельные и распределённые вычисления” /

4.Гергель В.П. Теория и практика параллельных вычислений /Гергель В.П. — М.: ИНТУИР.РУ Интернет-Университет Информационных Технологий, 2007.

Теоретическая часть

Критические секции

Критическая секция (critical section) (рис.2.1) — это небольшой участок кода, требующий монопольного доступа к каким-то общим данным. Она позволяет сделать так, чтобы единовременно только один поток получал доступ к определенному ресурсу. Естественно, система может в любой момент вытеснить Ваш поток и подключить к процессору другой, но ни один из потоков, которым нужен занятый Вами ресурс, не получит процессорное время до тех пор, пока Ваш поток не выйдет за границы критической секции.

Ниже приведён фрагмент кода, который демонстрирует, что может произойти без критической секции:

const int MAX_TIMES = 1000,

int g_nIndex - 0,

DWORD g_dwTimes[MAX_TIMES];

DWORD WINAPI FirstThread(PVOID pvParam)

{

while (g_nIndex < MAX_TIMES)
{

g_dwTimes[g__nIndex] = GetTickCount();
g_nIndex++;

}

return(0),
}

DWORD WINAPI SecondThread(PVOID pvParam)
{

while Cg_nIndex < MAX_TIMES)
{

g_nIndex++;

g_dwTimes[g_nIndex - 1] = GetTickCount();
}

return(0);
}

Здесь предполагается, что функции обоих потоков дают одинаковый результат, хоть они и закодированы с небольшими различиями. Если бы исполнялась только функция FirstThread, она заполнила бы массив g_dwTimes набором чисел с возрастающими значениями. Это верно и в отношении SecondThread - если бы она тоже исполнялась независимо. В идеале обе функции даже при одновременном выполнении должны бы по-прежнему заполнять массив тем же набором чисел. Но в нашем коде возникает проблема: масив g_dwTimes не будет заполнен, как надо, потому что функции обоих потоков одновременно обращаются к одним и тем же глобальным переменным. Вот как это может произойти.

Допустим, мы только что начали исполнение обоих потоков в системе с одним процессором. Первым включился в работу второй поток, т.e. функция SecondThread (что вполне вероятно), и только она успела увеличить счетчик g_nIndex 1, как система вытеснила ее поток и перешла к исполнению FtrstThread Та заносит в g_dwTimes[1] показания системного времени, и процессор вновь переключается на исполнение второго потока. SecondThread теперь присваивает элементу g_dwTtmes[1 - 1] новые показания системного времени. Поскольку эта операция выполняется позже, новые показания, естественно, выше, чем записанные в элемент g_dwTimes[1]фyнк цией FirstThread. Отметьте также, что сначала заполняется первый элемент массива и только потом нулевой. Таким образом, данные в массиве оказываются ошибочными.

Пример приведённый выше в значительной степени надуман, но прост. Рассмотрим пример с управлением связанным списком объектов. Если доступ к связанному списку не синхронизирован, один поток может добавить элемент в список в тот момент, когда другой поток пытается найти в нём какой-то элемент. Ситуация станет еще более угрожающей, если оба потока одновременно добавят в список новые элементы. Так что, используя критические секции, можно и нужно координировать доступ потоков к структурам данных.