Задание 7 (индивидуальное): синхронизация потоков

Указания

  • Необходимо выполнить задание в двух вариантах: при помощи интерфейсов Windows API и POSIX.
  • Необходимо реализовать задание в последовательном и многопоточном варианте, результаты сравнить между собой.

  1. Задача "эволюция". Дано двумерное поле клеток, каждая из которых либо содержит организм (1), либо пуста (0). Каждая клетка проверяет состояние своих соседей (их 8) и изменяет своё по правилам:

    1. Живая клетка, вокруг которой < 2 живых клеток, умирает от одиночества.
    2. Живая клетка, вокруг которой есть 2 или 3 живых клеток, выживает.
    3. Живая клетка, вокруг которой > 3 живых клеток, умирает от перенаселения.
    4. Пустая клетка, рядом с которой равно 3 живых соседа, оживает.

    Реализовать заданное количество шагов моделирования при помощи n потоков. Каждый поток должен вычислить значения в заданной ему полосе матрицы. На каждом шаге результат моделирования необходимо записывать в новую матрицу. По окончании очередного шага необходимо скопировать содержимое новой матрицы в исходную (как вариант можно использовать указатели, чтобы избежать копирования). Синхронизацию шагов между потоками необходимо выполнить при помощи барьера.

  2. Выполнить чтение слов заданного текстового файла в дек из строк. Далее в каждом из n потоков необходимо обработать часть строк, обновляя информацию в частотном словаре (количество вхождений каждого слова в текст). При добавлении нового слова доступ к словарю необходимо синхронизировать при помощи общего мьютекса. Увеличение счётчика одного слова необходимо синхронизировать при помощи отдельного мьютекса для данного счётчика.

  3. Реализовать параллельный алгоритм быстрой сортировки методом портфеля задач.

  4. Реализовать параллельный алгоритм сортировки слиянием методом портфеля задач.

  5. Реализовать поиск решения уравнения f(x) = 0, где x ∈ [a, b], f — непрерывная на отрезке [a, b] и принимающая на его концах разные по знаку значения, с точностью ε > 0, при помощи n потоков. Вначале до запуска потоков очередь отрезков должна хранить набор из n равных по длине частей отрезка [a, b]. Поток должен забирать первый в очереди отрезок и проверять, принимает ли функция на его концах разные по знаку значения. Если нет, то поток забирает следующий отрезок из очереди. Если да и длина отрезка меньше ε, его середина возвращается в качестве ответа. Иначе поток делит отрезок на n равных частей, помещает их в конец очереди и забирает оттуда следующий отрезок. Доступ к очереди необходимо синхронизировать при помощи мьютекса и условной переменной.

  6. Дан массив вещественных чисел, содержащий y0, y1, ..., yN — значения некоторой функции в точках x0, x0 + h, x0 + 2 h, ... (задано h, значение x0 не важно). Вычислить приближённые значения производной функции в этих точках по формулам:

    y'0 = (y1 - y0) / h,
    y'N = (yN - yN-1) / h,
    y'i = (yi+1 - yi-1) / (2 h).

    Разделить работу между n потоками. Значения производной необходимо записывать в тот же массив, который изначально хранит значения yk. Второй массив не использовать. Каждый поток должен сначала вычислить значения во внутренних точках своего отрезка, затем — в граничных. Для этого нужно считать значения, находящиеся слева и справа от отрезка, затем записать результаты в граничные точки текущего отрезка. Доступ разных потоков к граничным точкам необходимо упорядочить при помощи отдельного барьера для каждой границы.

  7. Нахождение определённого интеграла по схеме адаптивной квадратуры методом портфеля задач. В качестве задачи выделяется вычисление площади криволинейной трапеции по формуле Симпсона на отрезке [a, b]. Данная задача порождает две подзадачи: вычисление площадей криволинейных трапеций на отрезках [a, m] и [m, b], где m — середина отрезка [a, b]. Если сумма площадей двух трапеций приближённо равна площади большой трапеции (с точностью ε > 0), то точность аппроксимации на отрезке [a, b] считается достигнутой. Иначе процедура рекурсивно повторяется для отрезков [a, m] и [m, b].

  8. Дана матрица целых чисел, представляющая некоторое изображение. Получить по ней другую матрицу тех же размеров, представляющую размытый N раз вариант исходного изображения. На каждом шаге размытия каждый элемент новой матрицы должен быть получен как среднее арифметическое значений элемента старой с теми же координатами и соседних с ним элементов (координаты которых отличаются от текущего не более, чем на 1). Разделить работу между n потоками. Каждый поток должен вычислить значения в заданной ему полосе матрицы. По окончании очередного шага необходимо скопировать содержимое новой матрицы в исходную. Синхронизацию шагов между потоками необходимо выполнить при помощи барьера.

  9. Задан массив A вещественных значений размера n, а также вещественный отрезок [a, b] и натуральное число m. Определить, сколько элементов массива A принадлежат полуинтервалам [a, a + h), [a + h, a + 2 h), ... [a + (m - 1) h, b), где h = (b - a) / m. Счётчик для каждого полуинтервала защитить отдельным мьютексом.

  10. Задача умножения разрежённых матриц методом портфеля задач. Для разрежённых матриц хранится информация об их ненулевых элементах (например, в отображении из координат в значение). Одна задача в портфеле представляет собой нахождение строки результирующей матрицы с заданным номером.

  11. Выполнить циклический сдвиг на один элемент вправо/вниз всех строк и столбцов заданной матрицы. Каждый из потоков должен обрабатывать свой диапазон столбцов. Необходимо выполнить следующие действия в каждом потоке:

    1. выполнить циклический сдвиг внутри каждого столбца;
    2. сдвинуть вправо все столбцы, перемещаемые в пределах того же диапазона;
    3. сдвинуть вправо (в начало матрицы) все граничные столбцы — по согласованию с соседними потоками (при помощи мьютекса, связанного с данным столбцом).
  12. Реализовать решение задачи об n ферзях, преобразовав рекурсивный алгоритм к параллельному с использованием портфеля задач.

  13. Дана матрица целых чисел, представляющая некоторое изображение. Получить по ней другую матрицу тех же размеров, представляющую размытый N раз вариант исходного изображения. На каждом шаге размытия каждый элемент новой матрицы должен быть получен как разность текущего с минимальным среди соседних с ним элементов (координаты которых отличаются от текущего не более, чем на 1). Разделить работу между n потоками. Каждый поток должен вычислить значения в заданной ему полосе матрицы. По окончании очередного шага необходимо скопировать содержимое новой матрицы в исходную. Синхронизацию шагов между потоками необходимо выполнить при помощи барьера.