Операционные системы

Указания

• Задание выполняется в одном (любом) из двух вариантах: при помощи интерфейса Windows API либо POSIX.

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

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

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

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

3. Каждый из n потоков должен генерировать заданное количество псевдослучайных чисел от 0 до 1000, каждое из которых он должен помещать в конец дека, но только если такого числа там ещё нет. Синхронизацию доступа к деку необходимо выполнять при помощи блокировок чтения/записи. Проверку числа на принадлежность деку необходимо выполнить в блокировке на чтение. Далее если число не обнаружено, выполнить блокировку на запись и перед добавлением числа вновь проверить его на принадлежность деку.

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

5. Дан массив вещественных чисел, содержащий y₀, y₁, ..., y_N — значения некоторой функции в точках x₀, x₀ + h, x₀ + 2 h, ... (задано h, значение x₀ не важно). Вычислить приближённые значения производной функции в этих точках по формулам:

   y'₀ = (y₁ - y₀) / h,
   y'_N = (y_N - y_N-1) / h,
   y'_i = (y_i+1 - y_i-1) / (2 h). Разделить работу между n потоками. Значения производной необходимо записывать в тот же массив, который изначально хранит значения y_k. Второй массив не использовать. Каждый поток должен сначала вычислить значения во внутренних точках своего отрезка, затем — в граничных. Для этого нужно считать значения, находящиеся слева и справа от отрезка, затем записать результаты в граничные точки текущего отрезка. Доступ разных потоков к граничным точкам необходимо упорядочить при помощи одного глобального барьера (более сложный вариант: для каждой границы использовать отдельный барьер).

6. Каждый из n потоков должен генерировать заданное количество псевдослучайных чисел от 0 до 9, при этом увеличивая элемент целочисленного массива с индексом, равным сгенерированному числу. Доступ к каждому элементу массива осуществляется при помощи отдельного мьютекса. По окончании проверить, что сумма элементов массива равна общему количеству сгенерированных чисел.

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