Лабы

Правила

  1. Крайний срок сдачи всех л.р. - 15 декабря (пятница).
  2. Больше двух л.р. (или заданий другого типа) за одну неделю не принимается.
  3. По прошествии двух недель 1 и одного дня от "старта" л.р. макс. балл за нее снижается на 2 (но дальше остается постоянным).
  4. Чтобы иметь возможность получить полный балл за лабу, надо в течение этих двух недель сделать ее на 30-50%.
  5. За лабораторную работу - 7 баллов (всего 7 штук), за индивидуальное задание - 11 баллов (1 штука).

Л.р.1 Многопоточность

Задание 1

Закодить пример программы, моделирующей транзакции в банке, из 2-го тома Хорстманна без блокировок. Показать, что программа действительно работает неправильно, объяснить почему и как это исправить.

Задание 2

Реализовать многопоточную программу с якобы "тяжелыми вычислениями". В качестве "тяжелых вычислений" производить вычисление числа Пи с помощью ряда Лейбница: 4*(1-1/3+1/5-1/7+1/9-...). Примечание: этот ряд очень плохо сходится, поэтому чтобы достичь более-менее приличной точности, надо очень долго считать.

Программа предоставляет пользователю (в консоли) меню следующего вида:

  1. Продолжить вычисления.
  2. Приостановить вычисления.
  3. Посмотреть текущий результат.
  4. Узнать суммарное время, затраченное на вычисления.
  5. Выход.
Собственно вычисление ряда выполняет отдельный поток (в бесконечном цикле). Главный поток может его приостановить (для этого нужно заставить вычислительный поток выполнить вызов wait()), продолжить (notify()), показать текущий достигнутый результат вычислений (собственно, число Пи, но пока не очень точное). При приостановке загруженность процессора (в "диспетчере задач") должна падать  до небольшого значения около 0, при продолжении - возрастать до 100%. Когда вычисления приостановлены, операция "посмотреть текущий результат" при многократном ее выполнении должна показывать одно и то же (потому что текущее значение Пи не меняется); во время вычислений - соответственно - при каждом повторном просмотре Пи должно становиться все точнее и точнее.

Операция "узнать суммарное время" - показывает сколько секунд проработал вычислительный поток. Т.е., когда он "спит" в режиме паузы - эта величина не меняется; когда работает - увеличивается со скоростью "одна секунда в секунду".

На что обратить внимание:
  • Разберитесь, какому классу принадлежат методы wait() и notify() и какой именно поток они приостанавливают/пробуждают. Что такое notifyAll()?
  • Что такое  synchronized, какую проблему оно решает. Помните, что бывают synchronized-методы и synchronized-секции. (примечание: IllegalThreadStateException - это не искомая проблема, это ее следствие).
  • Зачем у synchronized-блока есть параметр-объект? ("synchronized(объект){код}")
  • Как правильно останавливать потоки. Метод join().
  • Литература - Шилдт и Хорстманн Т2.

Вопросы

  1. Какие есть два способа создать поток?
  2. Что делает метод join? Приведите пример его использования.
  3. В каких ситуациях необходимо использовать synchronized-блоки (или методы)? Привести пример.
  4. Имеется synchronized-метод. Как переписать его с использованием synchronized-блока(ов) так, чтобы метод работал так же, как и до этого, но в его объявлении не было слова synchronized?
  5. Почему методы wait и notify являются членами класса Object? (а не Thread)
  6. Приведите пример, когда вызов notifyAll() пробуждает не все спящие в данный момент потоки.

Инд.з.№1 (многопоточность)

Общие замечания:
  1. Когда речь идет о некоторых независимо действующих сущностях (людях, "клиентах", самолетах) - имеется в виду, что каждый из них представлен отдельным потоком. При этом все потоки могут либо запускаться одновременно - и затем многократно повторять свои запросы к ресурсам, либо создаваться заново с некоторой периодичностью, выполнять свой запрос и завершаться (выбирайте, как вам больше нравится).
  2. Когда написано что что-то "периодически происходит" - это значит, что надо сделать sleep() на некоторое случайное количество миллисекунд, затем сделать необходимое действие, затем повторить все сначала. Занятие ресурса на некоторое время (печать на принтере, уборка стола, посадка самолета и т.п.) тоже моделируется операцией sleep() на некоторое случайное или фиксированное количество миллисекунд.
  3. Все действия, происходящие в системе, документируйте выводом на экран: "клиент №1 пришел", "клиент №1 заселился в номер 2", "клиент №1 в ожидании", "самолет 5 освободил полосу 3" и т.п. К каждому сообщению добавьте удобно читаемую временнУю метку (в миллисекундах) - чтоб была понятна динамика происходивших событий.
  4. Не запускайте систему в бесконечный цикл: дайте ей поработать столько, чтобы примерно 1 или 0.5 экрана заполнились сообщениями, после чего завершите моделирование. Затем проверьте по сообщениям на экране, все ли правильно происходило в системе во время моделирования.
  5. Используйте ООП: выделяйте классы и операции с ними. Соотнесите свой дизайн с "чеклистом по ООП".
  6. Везде, где это необходимо, обеспечивайте взаимное исключение (т.е. исключайте состояния "гонок" потоков) (для этого обычно применяется synchronized).
  7. Не используйте готовые реализации конкурентных коллекций, атомарных переменных, барьеров и т.п. из стандартной библиотеки. Для этого у вас еще будет время.
Варианты:
(для выбора своего варианта используйте формулу: вариант = abs("Иванов".hashCode())%8+1 (вместо Иванова подставить свою фамилию, написанную на русском языке с большой буквы)) Объясните, как и почему работает эта формула.
  1. В сети имеются 2 принтера и N "клиентов", которым периодически требуется что-то напечатать. Когда эта необходимость возникает, клиент ждет, пока освободится любой из принтеров, после чего занимает его на некоторое время (пока идет печать), затем освобождает его, а через некоторое время опять ищет свободный принтер...
  2. В супермаркете имеются 2 полки с товарами (на одной товары одного типа, на другой - другого). В магазин периодически заходят клиенты, которым надо купить N товаров 1-го типа и M товаров 2-го типа (N и M для разных клиентов разные). Если на полках имеется достаточно количество нужных товаров - клиент их забирает и уходит, если нет - сначала ждет, пока они появятся. Пополнение полок товарами обеспечивают сотрудники магазина. Они тоже подходят к полкам в случайные моменты времени, неся в левой руке N товаров 1-го типа и M товаров 2-го типа (N и M для разных сотрудников разные). Если на полках имеется достаточно свободного места - сотрудник оставляет на них товары и уходит (чтобы потом вернуться опять), если места не хватает - сотрудник ждет у полки, пока клиенты освободят ему место. Как вы уже догадались, полки имеют ограниченную вместимость.
  3. В офисе имеется N рабочих столов, M сотрудников и K уборщиц. Изначально все столы чистые и не заняты. В случайные моменты времени приходят сотрудники, выбирают чистый стол и некоторое время за ним работают (если чистых столов нет - ждут, пока они появятся). После того, как за столом поработал сотрудник, стол считается грязным и требует уборки. Уборщицы непрерывно ищут "грязные" столы и убирают на них (уборка требует некоторого времени).
  4. В аэропорту имеется N взлетно-посадочных полос. Периодически прилетают самолеты, ждут, пока освободится полоса и садятся на нее (после посадки полоса опять свободна). Процесс посадки занимает некоторое время.
  5. В гостинице имеется N одноместных номеров. Периодически приходят клиенты, занимают номер (или ждут освобождения номера, если все номера заняты), живут в нем некоторое время, освобождают номер.
  6. Имеется 1 поток-отправитель и N потоков-получателей. Отправитель периодически добавляет в некоторую очередь сообщения, получатели пытаются забрать сообщения из этой очереди - но сообщение не удаляется из нее, пока его не "прочитают" все получатели.
  7. Имеется автоматизированный пункт проката велосипедов на N мест. Периодически приходят люди, чтобы взять велосипед. Если свободного велосипеда нет - ждут, пока он появится, забирают его на некоторое время, потом возвращают. Также могут приезжать люди с других пунктов проката и оставлять свои велосипеды на этом (или ждать, пока появится свободное место, если велосипед поставить некуда).
  8. Промоделируйте аналогично тому, как это описано в вариантах 1-7 задачу об обедающих философах (описание легко найти в Интернете).

Л.р.№2 Ввод-вывод

Задание 1 (3 балла)

Используя текстовый файл со списком фильмов (скачать, потом распаковать), написать программу, позволяющую удобно редактировать этот список и осуществлять в нем удобный поиск (год, жанр). Обычно такие программы читают файл в ОЗУ при запуске и перезаписывают все его содержимое (если были изменения) при завершении.
Подсказка: из текстовых файлов лучше всего читает Scanner. Чтобы научить его воспринимать запятую как разделитель полей - см. официальную справку на этот класс (в ней описывается специальный метод для этого).


Задание 2 (3 балла)

Используя класс DataInputStream, прочитать заголовок первого (и единственного) файла из movies.zip. Вывести на экран полученную информацию:
  1. Необходимую для распаковки версию архиватора.
  2. Имя файла в архиве.
  3. Дату и время его изменения (опционально).
  4. Его "сжатый" и "несжатый" размер.
Формат заголовка см. https://en.wikipedia.org/wiki/Zip_(file_format)#File_headers (Local header).
Для более подробной информации: https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.html и .ZIP File Format Specification
Примечание: если для "числовых" полей - вроде размера файла - использовать readInt()/intShort() - считанное число интерпретируется как big-endian (MSB first). Однако, в zip-файле оно хранится как little-endian (LSB first). Для конвертации одного в другое можно использовать Integer.reverseBytes() (или Short.reverseBytes()).

Задание 3 (1 балл)

Повторить задание 1, только вместо текстового файла использовать сериализацию (объектов вашего класса "фильм").

Бонус №1 (+5 баллов)

Скачать файл с оценками к фильмам (ratings.zip). Написать программу, аналогичную "заданию1" - но с показом рейтинга каждого фильма (посчитать среднее арифметическое всех его оценок) и возможностью смотреть и редактировать список оценок к каждому фильму. Для хранения данных использовать бинарные файлы (класс RandomAccessFile). Чтобы программа без "тормозов" справлялась с полу-гигабайтным файлом с оценками - не грузите его весь в ОЗУ, а производите все изменения на месте (сразу в файле) - с помощью операции seek().
Comments