Дисклаймер. Из принципа не буду исправлять замеченные опечатки, пока мне не напишут про них коммент.
Задания практикума «Многопоточное программирование»
1.
Создание нити
Напишите программу, которая создает нить. Используйте атрибуты по умолчанию. Родительская и вновь созданная нити должны распечатать десять строк текста.
2.
Ожидание нити
Модифицируйте программу упр. 1 так, чтобы вывод родительской нити производился после завершения дочерней. Используйте pthread_join.
3.
Параметры нити
Напишите программу, которая создает четыре нити, исполняющие одну и ту же функцию. Эта функция должна распечатать последовательность текстовых строк, переданных как параметр. Каждая из созданных нитей должна распечатать различные последовательности строк.
4.
Принудительное завершение нити
Дочерняя нить должна распечатывать текст на экран. Через две секунды после создания дочерней нити, родительская нить должна прервать ее вызовом функции pthread_cancel.
5.
Обработка завершения нити
Модифицируйте программу упр. 4 так, чтобы дочерняя нить перед завершением распечатывала сообщение об этом. Используйте pthread_cleanup_push.
6.
Многопоточный cp -R
Реализуйте многопоточную программу рекурсивного копирования дерева подкаталогов, функциональный аналог команды cp(1) с ключом -R. Программа должна принимать два параметра – полное путевое имя корневого каталога исходного дерева и полное путевое имя целевого дерева. Программа должна обходить исходное дерево каталогов при помощи opendir(3C)/readdir_r(3С) и определять тип каждого найденного файла при помощи stat(2). Для определения размера буфера для readdir_r используйте pathconf(2) (sizeof (struct dirent) + pathconf(directory)+1).
Для каждого подкаталога должен создаваться одноименный каталог в целевом дереве и запускаться отдельная нить, обходящая этот подкаталог. Для каждого регулярного файла должна запускаться нить, копирующая этот файл в одноименный файл целевого дерева при помощи open(2)/read(2)/write(2). Файлы других типов (символические связи, именованные трубы и др.) следует игнорировать.
При копировании больших деревьев каталогов возможны проблемы с исчерпанием лимита открытых файлов. Очень важно закрывать дескрипторы обработанных файлов и каталогов при помощи close(2)/closedir(3C). Тем не менее, для очень больших деревьев этого может оказаться недостаточно. Допускается обход этой проблемы при помощи холостого цикла с ожиданием (если open(2) или readdir(3C) завершается с ошибкой EMFILE, то допускается сделать sleep(3C) и повторить попытку открытия через некоторое время).
Обратите также внимание, что значения дескрипторов открытых файлов могут переиспользоваться, т.е. в разные моменты времени один и тот же дескриптор может указывать на разные файлы. Чтобы избежать связанных с этим проблем, избегайте передачи дескрипторов между нитями. Вся работа с дескриптором от создания до закрытия должна происходить в одной нити.
7.
Многопоточный cp -R – усовершенствование
Модифицируйте решение предыдущего упражнения так, чтобы даты модификации, права доступа и, если это возможно, идентификаторы владельца и группы каждого скопированного файла и каталога совпадали с аналогичными параметрами оригинала. Обратите внимание, что установка даты модификации каталога должна происходить только после того, как завершено копирование всех его файлов и подкаталогов. Используйте pthread_join(3С) для синхронизации, utime(2)/chmod(2)/chgrp(2) для установки атрибутов файла.
8.
Многопоточный cp -R – аккуратный выход
Модифицируйте решение предыдущего упражнения так, чтобы при нажатии Ctrl-C (при получении сигнала SIGINT) процесс копирования завершался. При этом все файлы, копирование которых уже началось, должны быть докопированы до конца, но копирование новых файлов и подкаталогов начинать не следует. Повторное нажатие Ctrl-C не должно иметь никакого эффекта. Рекомендация – используйте глобальную переменную, значение которой проверяется всеми нитями, копирующими каталоги.
9.
Многопоточный cp -R – быстрый аккуратный выход
Модифицируйте решение предыдущего упражнения так, чтобы при нажатии Ctrl-\ (при получении сигнала SIGQUIT) процесс копирования завершался как можно скорее. При этом все файлы, копирование которых не завершено, и все пустые каталоги должны быть удалены.
Используйте unlink(2) для удаления файлов и rmdir(2) для удаления каталогов. Обратите внимание, что попытка удаления каталога должна производиться только после того, как все нити, занятые копированием файлов в этом каталоге, завершат работу. Используйте pthread_join(3C).
10.
Синхронизированный вывод
Модифицируйте программу упр. 1 так, чтобы вывод родительской и дочерней нитей был синхронизован: сначала родительская нить выводила первую строку, затем дочерняя, затем родительская вторую строку и т.д. Используйте мутексы. Запрещается использовать явные (sched_yeld) и неявные (sleep и т.д.) передачи управления между нитями и ожидание в цикле.
11.
Синхронизированный вывод 2
Докажите, что задача 10 не может быть решена с использованием двух мутексов (без использования других средств синхронизации).
12.
Синхронизированный вывод 3
Решите задачу 10 с использованием условной переменной и минимально необходимого количества мутексов.
13.
Синхронизированный вывод 4
Решите задачу 10 с использованием двух семафоров-счетчиков
14.
Синхронизированный вывод 5
Если вы решили задачи 11 и 13, объясните, почему ваше доказательство неприменимо к семафорам-счетчикам.
15.
Синхронизированный доступ к списку
Родительская нить программы должна считывать вводимые пользователем строки и помещать их в начало связанного списка. Строки длиннее 80 символов можно разрезать на несколько строк. При вводе пустой строки программа должна выдавать текущее состояние списка. Дочерняя нить пробуждается каждые пять секунд и сортирует список в лексикографическом порядке (используйте пузырьковую сортировку). Все операции над списком должны синхронизоваться при помощи мутекса.
16.
Синхронизированный доступ к списку 2
Переделайте программу упр. 15 так, чтобы с каждой записью (а также с заголовком списка) был связан свой собственный мутекс.
Примечание: при перестановке записей списка, необходимой при реализации пузырьковой сортировки, необходимо блокировать мутексы трех записей.
Примечание 2: чтобы избежать мертвых блокировок, мутексы записей, более близких к началу списка, всегда захватывайте раньше.
Примечание 3: преподаватель может потребовать, чтобы программа включала две или более сортирующие нити, а также потребовать изменить интервал между сортировками.
17.
Синхронизированный доступ к списку 3
Модифицируйте программу упр. 16 так, чтобы дочерняя нить засыпала на одну секунду между исполнениями каждого шага сортировки (между перестановками записей в списке). При этом можно будет наблюдать процесс сортировки по шагам.
18.
Использование блокировки чтения-записи
Модифицируйте программу упр. 11 так, чтобы вместо мутекса использовалась блокировка чтения-записи.
19.
Использование блокировки чтения-записи 2
Модифицируйте аналогичным образом программу упр. 17
20.
Обработка сигнала
Модифицируйте программу упр. 16 так, чтобы при нажатии °C (при получении сигнала SIGINT) список сортировался в обратном направлении.
21.
Производственная линия
Разработайте имитатор производственной линии, изготавливающей винтики (widget). Винтик собирается из детали C и модуля, который, в свою очередь, состоит из деталей A и B. Для изготовления детали A требуется 1 секунда, В – две секунды, С – три секунды. Задержку изготовления деталей имитируйте при помощи sleep. Используйте семафоры-счетчики.
22.
Производитель-потребитель
Реализуйте кольцевой буфер на десять строк, которым может использоваться для обмена данными между двумя или большим количеством нитей. Реализация буфера должна поддерживать функции
Допускается реализация на C++ с заменой mymsginit и mymsgdestroy на конструктор и деструктор, а операций get и put на соответствующие методы.
mymsgput принимает в качестве параметра ASCIIZ строку символов, обрезает ее до 80 символов (если это необходимо) и помещает ее в буфер. Если буфер заполнен, mymsgput блокируется. Функция возвращает количество переданных символов.
mymsgget возвращает первую запись из буфера, обрезая ее до размера пользовательского буфера (если это необходимо). В любом случае, запись извлекается из буфера полностью. Если буфер пуст, mymsgget блокируется. Функция возвращает количество прочитанных символов.
mymsgdestroy должна приводить к разблокированию ожидающих операций get и put. При этом функции get и put должны возвращать 0.
Необходимо продемонстрировать работу буфера с двумя производителями и двумя потребителями.
Для синхронизации доступа к буферу используйте семафоры-счетчики.
23.
Производитель-потребитель 2
Реализуйте задачу 22 с использованием условных переменных и минимально необходимого числа мутексов.
24.
Потоковый буфер
Реализуйте трубу в виде кольцевого буфера объемом 10240 байт. Реализация должна поддерживать функции
Допускается реализация на C++ с заменой init и destroy на конструктор и деструктор, а send и receive на методы.
Функция send получает в качестве параметра ASCIIZ строку неограниченной длины и пытается поместить ее в буфер. Если в буфере недостаточно места, send блокируется. При освобождении части буфера, send копирует часть строки и т.д., пока вся строка не будет передана или труба не будет уничтожена. Новые операции send не начнутся до тех пор, пока не завершатся все предыдущие операции send. Функция возвращает количество переданных байт.
Операция recv копирует из буфера bufsize-1 байт. Если данных в буфере недостаточно, операция блокируется до тех пор, пока не будут получены все данные или пока труба не будет уничтожена.
Необходимо продемонстрировать передачу данных объемом более 10240 байт через буфер. Для синхронизации доступа используйте условные переменные и минимально необходимое количество мутексов.
25.
Многопоточный сервер
Реализуйте сервер, который принимает TCP соединения и транслирует их. Сервер должен получать из командной строки следующие параметры:
- Номер порта P, на котором следует слушать.
- Имя или IP-адрес узла N, на который следует транслировать соединения.
- Номер порта P', на который следует транслировать соединения.
Сервер принимает все входящие запросы на установление соединения на порт P. Для каждого такого соединения он открывает соединение с портом P' на сервере N. Затем он транслирует все данные, получаемые от клиента, серверу N, а все данные, получаемые от сервера N – клиенту. Если сервер N или клиент разрывают соединение, наш сервер также должен разорвать соединение. Если сервер N отказывает в установлении соединения, следует разорвать клиентское соединение.
Сервер должен обеспечивать трансляцию 510 соединений при лимите количества открытых файлов на процесс 1024. Сервер не должен быть многопоточным и никогда не должен блокироваться. Не следует использовать неблокирующиеся сокеты. Следует использовать select или poll.
26.
псевдомногопоточный HTTP-клиент
Реализуйте простой HTTP-клиент. Он принимает один параметр командной строки – URL. Клиент делает запрос по указанному URL и выдает тело ответа на терминал как текст (т.е. если в ответе HTML, то распечатывает его исходный текст без форматирования). Вывод производится по мере того, как данные поступают из HTTP-соединения. Когда будет выведено более экрана (более 25 строк) данных, клиент должен продолжить прием данных, но должен остановить вывод и выдать приглашение Press space to scroll down.
При нажатии пользователем клиент должен вывести следующий экран данных. Для одновременного считывания данных с терминала и из сетевого соединения используйте системный вызов select.
27.
псевдомногопоточный HTTP-клиент 2
Реализуте задачу упр. 26, используя системные вызовы aioread и aiowait.
28.
Многопоточный HTTP-клиент
Реализуйте задачу упр. 26, используя две нити, одну для считывания данных из сетевого соединения, другую для взаимодействия с пользователем.
29.
Псевдомногопоточный кэширующий прокси
Реализуйте простой кэширующий HTTP-proxy с кэшем в оперативной памяти.
Прокси должен быть реализован как один процесс и один поток, использующий для одновременной работы с несколькими сетевыми соединениями системный вызов select или poll. Прокси должен обеспечивать одновременную работу нескольких клиентов (один клиент не должен ждать завершения запроса или этапа обработки запроса другого клиента).
30.
Многопоточный кэширующий прокси
Реализовать задачу 29, создавая для каждого входящего HTTP-соединения свою нить. При невозможности создать поток допускается блокировать входящие соединения или возвращать ошибку.
31.
Многопоточный кэширующий прокси с рабочими потоками
Реализовать задачу 29, используя рабочие потоки (worked threads). При запуске прокси должен принимать параметр, целое число, указывающее размер пула потоков. Прокси должен запустить указанное число нитей. Необходимо обеспечить одновременную обработку количества запросов, превосходящего количество нитей в пуле; блокировка входящих соединений недопустима. Разумеется, при этом каждая из нитей в разные моменты времени будет вынуждена обрабатывать разные соединения. Для управления соединениями используйте select или poll.
Known Issues
