Это устаревшая версия заданий! Новая версия заданий доступна по адресу

http://swsoft.nsu.ru/WackoWiki/KursOperacionnyeSistemy/PraktikumPosixThreads/PthreadTasks

Задания практикума <Многопоточное программирование>


1. Создание нити

Напишите программу, которая создает нить. Используйте атрибуты по умолчанию. Родительская и вновь созданная нити должны распечатать десять строк текста. При использовании stdout выключите буферизацию (setvbuf).

2. Ожидание нити

Модифицируйте программу упр. 1 так, чтобы вывод родительской нити производился после завершения дочерней. Используйте pthread_join.

3. Атрибуты нити

Модифицируйте программу упр. 1 так, чтобы созданная нить распечатывала свои идентификатор нити и приоритет. Используйте pthread_self и pthread_getschedparam.

4. Параметры нити

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

5. Среда исполнения нити

Модифицируйте программу упр. 1 так, чтобы родительская и дочерняя нити распечатали адрес какой-либо локальной переменной. (используйте printf("%p", &i));. Убедитесь, что различные нити используют различные стеки.

6. Установка атрибутов нити

Создайте атрибуты нити. Установите приоритет нити и стек. Запустите нить с указанными атрибутами, распечатайте приоритет и указатель на локальную переменную. Убедитесь, что параметры соответствуют установленным.

7. Посылка и перехват сигнала

Родительская нить должна послать дочерней сигнал SIGINT. Дочерняя нить должна перехватить этот сигнал и распечатать пришедший сигнал и свой идентификатор нити.

8. Принудительное завершение нити

Дочерняя нить должна распечатывать текст на экран. Через две секунды после создания дочерней нити, родительская нить должна прервать ее вызовом функции pthread_cancel.

9. Обработка завершения нити

Модифицируйте программу упр. 8 так, чтобы дочерняя нить перед завершением распечатывала сообщение об этом. Используйте pthread_cleanup_push.

10. Синхронизированный вывод

Модифицируйте программу упр. 1 так, чтобы вывод родительской и дочерней нитей был синхронизован: сначала родительская нить выводила первую строку, затем дочерняя, затем родительская вторую строку и т.д. Используйте мутексы. Запрещается использовать явные (pthread_yeld) и неявные (sleep и т.д.) передачи управления между нитями и ожидание в цикле.

11. Синхронизированный вывод 2

Докажите, что задача 10 не может быть решена с использованием двух мутексов (без использования других средств синхронизации).

12. Синхронизированный вывод 3

Решите задачу 10 с использованием условной переменной и двух мутексов.

13. Синхронизированный вывод 4

Решите задачу 10 с использованием двух семафоров-счетчиков

14. Синхронизированный вывод 5

Если вы решили задачи 11 и 13, объясните, почему ваше доказательство неприменимо к семафорам-счетчикам.

15. Синхронизированный доступ к списку

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

16. Синхронизированный доступ к списку - усложнение

Переделайте программу упр. 15 так, чтобы с каждой записью (а также с заголовком списка) был связан свой собственный мутекс.

Примечание: при перестановке записей списка, необходимой при реализации пузырьковой сортировки, необходимо блокировать мутексы трех записей.

Примечание 2: чтобы избежать мертвых блокировок, мутексы записей, более близких к началу списка, всегда захватывайте раньше.

Примечание 3: преподаватель может потребовать, чтобы программа включала две или более сортирующие нити, а также потребовать изменить интервал между сортировками.

17. Синхронизированный доступ к списку - усложнение 2

Модифицируйте программу упр. 16 так, чтобы дочерняя нить засыпала на одну секунду между исполнениями каждого шага сортировки (между перестановками записей в списке). При этом можно будет наблюдать процесс сортировки по шагам.

18. Использование блокировки чтения-записи

Модифицируйте программу упр. 15 так, чтобы вместо мутекса использовалась блокировка чтения-записи.

19. Использование блокировки чтения-записи 2

Модифицируйте аналогичным образом программу упр. 16

20. Производственная линия

Разработайте имитатор производственной линии, изготавливающей винтики (widget). Винтик собирается из детали C и модуля, который, в свою очередь, состоит из деталей A и B. Для изготовления детали A требуется 1 секунда, В - две секунды, С - три секунды. Задержку изготовления деталей имитируйте при помощи sleep. Используйте семафоры-счетчики.

21. [псевдо]многопоточный HTTP-клиент

Реализуйте простой HTTP-клиент. Он принимает один параметр командной строки - URL. Клиент делает запрос по указанному URL и выдает тело ответа на терминал как текст (т.е. если в ответе HTML, то распечатывает его исходный текст без форматирования). Вывод производится по мере того, как данные поступают из HTTP-соединения. Когда будет выведено более экрана (более 25 строк) данных, клиент должен продолжить прием данных, но должен остановить вывод и выдать приглашение Press space to scroll down.

При нажатии пользователем клиент должен вывести следующий экран данных. Для одновременного считывания данных с терминала и из сетевого соединения используйте системный вызов select.

22. [псевдо]многопоточный HTTP-клиент - 2 вариант

Реализуте задачу упр. 22, используя системные вызовы aioread и aiowait.

23. Многопоточный HTTP-клиент

Реализуйте задачу упр. 21, используя две нити, одну для считывания данных из сетевого соединения, другую для взаимодействия с пользователем.

24. Псевдомногопоточный кэширующий прокси

Реализуйте простой кэширующий HTTP-proxy с кэшем в оперативной памяти. В качестве порта прокси используйте 8000+ваш UID. При поступлении HTTP-запроса ваш прокси должен попытаться найти точный URL запроса в индексе кэша. Если он будет обнаружен, возвратить содержимое соответствующего буфера кэша. При этом следует учесть, что буфер кэша может быть еще не считан до конца.

Если URL в индексе кэша не обнаружен, внести его в индекс кэша, запросить у указанного в URL сервера размер страницы и попытаться разместить буфер необходимого размера в оперативной памяти. Затем необходимо инициировать чтение страницы с сервера и ее сохранение в буфере вместе с заголовками HTTP. По мере того, как страница будет считываться, ее необходимо возвращать клиенту.

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

При невозможности разместить или расширить буфер (напр. из-за превышения квоты адресного пространства), необходимо удалить один или несколько буферов, которые дольше всего не использовались.

Индекс кэша следует реализовать как несортированный массив с линейным поиском в нем либо STL map. В индексе кэша следует хранить URL, время последнего обращения с точностью до секунд, указатель на буфер кэша, размер буфера и размер считанных к данному моменту данных.

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

25. Многопоточный кэширующий прокси

Реализовать задачу 24, создавая для каждого входящего HTTP-соединения свою нить. При невозможности создать поток допускается блокировать входящие соединения или возвращать ошибку.

26. Многопоточный кэширующий прокси с пулом потоков.

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

Уточнения к задачам группы "кэширующий прокси" - внимание, там предусмотрены бонусы!

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

Терминология

Собственно правила

Оценка за практикум выставляется на основе оценки за 4 семестр и количества задач, сданных в 5 семестре. Правила определения оценки таковы:

Оценка в 4 семестре - "отлично"

17 обычных задач + 2 задачи "proxy" = "отлично"
11 эффективных задач = "хорошо"
6 эффективных задач = "удовлетворительно"

Оценка в 4 семестре - "хорошо"

все задачи = "отлично"
11 эффективных задач = "хорошо"
6 эффективных задач = "удовлетворительно"

Оценка в 3 семестре - "удовлетворительно"

16 эффективных задач = "хорошо"
6 эффективных задач = "удовлетворительно"

По итогам практикума, студенты, получившие оценку 5, получают итоговую оценку 5 без сдачи экзамена ("автоматом"). Студенты, получившие за практикум оценку 4, обязаны сдавать экзамен и могут получить по результатам экзамена итоговую оценку от 2 до 5 включительно. Студенты, получившие за практикум оценку 3, обязаны сдавать экзамен и могут получить по результатам экзамена итоговую оценку от 2 до 4 включительно.

Студенты, не получившие оценки 3 за практикум, могут быть допущены к экзамену после собеседования и могут получить оценку не выше 3.

Требования к заданиям

Не допускается использование холостых циклов для синхронизации (если иное явно не оговорено заданием).

Трудновоспроизводимые "глюки" интерпретируются как ошибки соревнования. Обнаружив такое поведение, преподаватель обязан потребовать его устранения. Поскольку для трудновоспроизводимых ошибок безошибочный прогон и даже серия безошибочных прогонов программы не гарантирует отсутствия ошибки, студент должен не только устранить ошибку, но объяснить преподавателю ее причину. В том числе, при внесении исправлений в код программы, студент обязан объяснить, каким образом неисправленный код мог приводить к наблюдавшемуся поведению.

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

Это устаревшая версия заданий! Новая версия заданий доступна по адресу

http://swsoft.nsu.ru/WackoWiki/KursOperacionnyeSistemy/PraktikumPosixThreads/PthreadTasks