Секретные протоколы к задачам практикума "Многопоточное программирование"

Информация для преподавателей

Студентам не показывать!

Задачи 10-11

Задача 11 рассматривается как бонус за понимание решения задачи 10.

При приеме задания 10 надо иметь в виду, что решение на двух мутексах (pthread_mutex_lock(&a); print; pthread_mutex_unlock(&b);) работает как под линуксом, так и под солярисом. Однако оно некорректно, т.к. по спецификациям POSIX нельзя снимать мутекс, который ты не лочил. (надо попробовать, что будет, если пометить оба мутекса рекурсивными). Такое можно делать только на семафорах-счетчиках.

Идея доказательства, что на двух мутексах это сделать невозможно, принадлежит Алексею Семенову. Смысл такой. Ситуация, когда одна из нитей не держит ни одного из мутексов, недопустима, т.к. вторая сможет печатать сообщения подряд. Из этого следует, что недопустима также ситуация, когда одна из нитей держит оба мутекса (тогда другая должна их оба освободить). Рассмотрим ситуацию, когда одна нить держит мутекс a, другая мутекс b. Нам надо перейти в ситуацию, когда первая нить держит b, вторая a. Сделать это, не переходя через состояние, когда либо одна нить держит оба мутекса, либо она не держит ни одного, невозможно.

По этой же причине нельзя корректно (без дополнительного хотя бы целочисленного флага и холостого цикла, или без sleep/yield) войти в основной цикл программы на трех мутексах: ведь дочерняя нить стартует, не держа ни одного мутекса. Т.е. либо следует разрешить программе студента стартовать с последовательности непрерывных печатей родительской нити, либо разрешить использовать yield, но студент должен доказать необходимость этого. Такое доказательство, на самом деле, составляет больше половны доказательства задачи 11.

На семафоры-счетчики это доказательство не распространяется, т.к. на счетчиках нет понятия "держания" семафора, и первая нить запросто может отобрать у второй семафор b (на чем и основано решение с двумя семафорами). К этому можно докопаться, если студент решил задачи 10 и 11, и сдает задачу 13.

Группа задач "кэширующий прокси"

Главная проблема при приемке этих задач - переиспользование кода между студентами. Предлагаемая стратегия борьбы с этим: решения, принимаемые первыми, тестируются не на все необходимые тесткейзы. Затем, когда вы видите, что студент сдает чужой код, вы проверяете тесткейз, который не проверяли в первый раз. Нередко оказывается необходимо не только разобраться в чужом коде, но и пересмотреть архитектуру.

Предлагаемая последовательность тесткейзов:

1. Параллельная работа. Прокси должен обеспечивать параллельную работу двух соединений. Проверяется открытием двух текстов с lib.ru; они скачиваются несколько минут; при этом наблюдаемая задержка при открытии www.nsu.ru из кэша не должна изменяться (т.е. сессия www.nsu.ru не должна ждать событий в сессиях lib.ru). Это относится ко всем реализациям, в том числе и на селекте. Допускается задержка при обработке некэшированных запросов DNS.
   Разрыв соединений. При закрытии окна браузера с недокачанной страницей (подойдет тот же lib.ru), прокси не должен падать.
   Нормальное скачивание страниц с картинками (передается как HTML, так и двоичные данные, с корректной передачей всех полей заголовка).
2. Поддержка редиректов. Т.е. их, разумеется, не следует кэшировать, но следует передавать браузеру.
   Проверить из links. Он по умолчанию говорит HTTP 0.9, если прокси отказывается принимать соединение, студент должен понять, в чем дело. В настройках links можно сказать говорить HTTP 1.0.
3. Кэширование. Две сессии, качающие один и тот же длинный документ, должны обновляться одновременно или с задержкой не более секунды. Разрыв одной из этих сессий не должен приводить к срыву докачки во второй сессии.
   Необходимо также проверить, что кэшированная страница повторно не скачивается, а берется из кэша.
4. У прокси, которые проходят тесткейз 3, можно попросить переделать докачку закрытых сессий на их обрыв или наоборот (см. официальные требования).
   Добиться осмысленного поведения при открытии URL, сессия с которыми была оборвана.
5. Стресс-тестирование. Две-три сессии wget --mirror на www.nsu.ru, missphoto.nsu.ru и несколько "долгоиграющих" интерактивных сессий. Загрузка процессора не должна превышать 10-12%, прокси должен скачивать весь www.nsu.ru и весь missphoto.nsu.ru и не падать по квоте процессорного времени. Если квота исчерпывается, это подозрение на скрытый холостой цикл. Впрочем, высокая загрузка процессора может быть обусловлена линейным поиском по индексу URL. Посоветуйте переделать на STL map.
   Прокси с пулом потоков должен быть способен поддерживать больше одновременных соединений, чем у него потоков в пуле, поэтому нуждается в более интенсивном стресс-тестировании, чем однопоточная и простая многопоточная реализации.
   При стресс-тестировании допускается работа без очистки кэша (по крайней мере в прошлом году весь missphoto.nsu.ru влезал в своп ftp.ccfit.nsu.ru) и умеренные утечки памяти.
   Внимание! для стресс-тестирования лучше всего использовать /tmp, но не забывайте его потом чистить!!!!
6. Асинхронные запросы DNS. Можно применять против тех, кто много выпендривается - они этого не проходили, надо искать самому по документации.
7. Сквозное соединение. wget --mirror debian.nsu.ru. Там лежат ISO image по 600 мегабайт, под такое ему памяти не дадут никогда, даже при чистом /tmp. Разумеется, кэшировать такие штуки не следует, но скачивать их надо уметь. Часто требуется полный пересмотр архитектуры.
8. Очистка кэша. Стресс-тестирование при забитом /tmp (на солярисе он расположен в memfs) либо квота оперативной памяти, либо просто следить по top'у, чтобы не вылезало, скажем, за 15 или 30 мегабайт. В этих условиях прокси должен обеспечить скачивание всего www.nsu.ru и missphoto.nsu.ru.
   Изощренное издевательство: забить /tmp и с наивным видом спросить, а что изменилось-то? Куда вся память делась?
   Внимание! не забывайте потом чистить /tmp!!!!
9. Утечка памяти. После того, как кэш начал очищаться, объем памяти расти не должен - в этом смысле предпочтительно просто следить за объемом памяти по top.
   Человек, который способен найти утечку памяти в чужом многопоточном коде (а они там практически всегда есть), на мой взгляд, заслуживает положительной оценки.