В рамках данного курса:
- Создать свой репозиторий c задачей на https://github.com.
- Получится Ваш первый открытый проект, который можно показывать будущему работодателю, что характеризует Вас, как специалиста.
- Тесты
- Отладка багов
- Доказательство работоспособности решения
- Подумать, чем отличаются следующие виды описаний и для чего нужны:
- комментарии,
- readme (цель проекта, решаемая задача),
- getting-started (шаги установки/развёртывания, метод и способ использования в своём коде),
- список зависимостей,
- документация
- Документация
- Если скачать программу doxygen.nl и выбрать папку с вашим правильно оформленным кодом, то doxygen автоматически сверстает документацию в формат html/doc/pdf и др.
- Правила оформления комментариев в коде для получения документации
- Пример такой сгенерированной документации на сайте Данный справочник по функциям и методам удобно читать (лишён ненужных подробностей в отличие от кода) и может быть показан пользователям Вашего проекта
Класс ThreadPool – пул потоков, шаблонный класс, параметризованный функтором (функция с состоянием, задача на исполнение), генерирует в конструкторе нужное количество потоков, согласно аргументу n_threads, в деструкторе дожидается окончания выполнения всех текущих задач (запрет на получение новых задач), имеет:
- метод «запросить задачу на выполнение» и передать её на выполнение любому свободному потоку, результат выполнения функции-задачи потока будет возвращён адресату, давшему задачу, через callback-функцию аргумент;
- метод «получить число свободных потоков»;
- метод «прервать выполнение потока по номеру»;
- метод «получить статистику выполненных задач» (простой потоков, загруженность потоков, ошибки при выполнении задач, число выполненных разных типов задач);
- метод «отдать задачу первому освободившемуся потоку».
Класс ThreadPool – очередь задач с приоритетами, шаблонный класс, параметризованный парой функтор (задача) и целочисленный приоритет. Чем меньше приоритет задачи, тем раньше задача должна оказаться в этой очереди. Перед тем, как поток начинает выполнять задачу, он забирает её из головы очереди. Добавлять новые задачи можно только в конец очереди, очередь сама решает, исходя из её контента, где будет размещена задача. Когда задач нет – потоки засыпают.
Написать симулятор ThreadPool и TasksQueue, обеспечивающих в совокупности оптимальный режим загрузки потоков задачами. Вести учёт времени простоя потока, только при наличии незабранных задач из очереди. Количество потоков, с которыми создаётся пул подаётся, число приоритетов и max длина очереди – аргументы командной строки.
Написать пул потоков и протестировать его на разнородных задачах: чтения файлов, записи файлов, сна потока, … и пр. разных по времени и потребляемым ресурсам. Для тестов понадобится отдельный поток, добавляющий случайно выбранные задачи, из пула возможных задач в конец очереди.
Есть M текстовых файлов (вилок на столе). N потоков (философов), каждый из них, хочет писать и читать в 2 файла выбранных случайно из M доступных. Поток хочет писать и читать случайные данные (кушать вилками спагетти) попеременно: сначала записывая в 1й файл в случайное место случайное число, затем читая из 1го файла из случайного места число и записывая то число и ещё одно новое случайное число во 2й файл, а затем, наоборот, вычитывая из 2го файла из случайного места число, добавляя к нему новое случайное число и дописывая их обратно в 1й выбранный файл. Таких итераций поток делает случайное число <10. Затем он закрывает свои файлы и выбирает случайно новые 2 файла для работы.
Время от времени (решая случайно) поток(философ) не выходит на очередную итерацию, а предпочитает заснуть на случайное число секунд(«пофилософствовать»).
При этом все потоки (философы) разделяют между собой общий случайный генератор (стол), 1 на всех, обращаясь к нему (придумать эффективный интерфейс).
N (2 >= N >= 20) и M (4 >= M >= 100) задаются при старте программы через параметры командной строки.
Задача написать симулятор работы потоков (обеда философов), так чтобы время простоя каждого потока было минимальным. Вести учёт времени простоя потока. Найти алгоритм, который позволит философам организовать доступ к вилкам так, чтобы каждый мог насытиться, и никто не умер с голоду.
Есть M файлов (табло с билетами). Есть N и K конкурирующих потоков(пассажиров и пилотов) хотят читать и обновлять одни и те же данные. Пилоты публикуют новые полёты, число свободных мест, время отлёта (счёт времени идёт на микросекунды), в один (выбранный случайно) файл (табло). Файлы(табло) отсортированы по времени. Пассажиры выбирают (случайно) файл(табло) резервируют за собой и всеми своими друзьями (взятых случайно) число место и улетают. После прилёта резервируют снова иной полёт. В момент отлёта самолёта запись о полёте из файла(табло) кем-то также удаляется.
N (2 >= N <= 200), K (2 >= K <= 20) и M (1 >= M >= 10) задаются при старте программы через параметры командной строки.
Несколько потоков могут читать данные одновременно, но только 1 поток может писать данные в 1 файл (обновлять табло билетов). Вести учёт времени простоя потока. Задача – как спланировать работу такой системы?
Каждый новый разряд кодирует очередная цифра из ряда Фибоначчи (кроме первой единицы). Эта система обладает свойством недопустимой последовательности (в ней не может быть подряд 2х единиц, почему?).
Кодирование: в новое битовое представление числа в начале записать лидирующую единицу, затем найти максимальное число из ряда Фибоначчи содержащееся в кодируемом числе (индекс этого числа – это длина нового битового представления исходного числа). Ставим эту единицу в новое битовое представление кодируемого числа (за имеющейся). Вычитаем из кодируемого это число Фибоначчи и, снова ищем максимальное число из ряда содержащееся в полученном остатке. Запишем столько нулей в битовое представление числа, сколько индексов ряда пропущено и затем запишем единицу. Будем повторять итерацию, пока искомое число не станет равным нулю. В конце запишем новое битовое представление в файл от конца к началу. Перейдём к следующему числу (2 единицы в конце будут отделять числа).
Имя файла, и тип операции(арх или деарх) – параметры командной строки.
Написать архиватор и деархиватор. Протестировать работу архиватора на случайно сгенерированных бинарных файлах, состоящих из целых чисел. Размер заархивированного файла должен быть всегда меньше файла исходного и однозначно деархивироваться до файла, совпадающего с исходным.
5. Реализация архивации данных в виде последовательности целых чисел кодом VarByte (составная часть библиотеки google protobuf).
Кодирование происходит с гранулярностью в 1 байт. Признак окончания очередного закодированного числа – это первый (знаковый) бит s байта, если s=1, конец числа. Если число <=127, кодируем его 1м байтом. Иначе сохраняем число в несколько байт, каждый из которых хранит очередной остаток от деления кодируемого числа на 128.
Имя файла, и тип операции(арх или деарх) – параметры командной строки.
Написать архиватор и деархиватор. Протестировать работу архиватора на случайно сгенерированных бинарных файлах, состоящих из целых чисел. Размер заархивированного файла должен быть всегда меньше файла исходного и однозначно деархивироваться до файла, совпадающего с исходным.
Данный метод сжимает числа с помощью выбора такого значения k, чтобы значение b=2^k было наиболее близко к среднему значению последовательности кодируемых чисел. Каждое целое n представляется q=[(n–1)/b], сохранённое в унарном коде используя q+1 битов (лидирующее число единиц = q и нулевой бит, который отделает 2 части кода) и остаток r=(n–1)(mod b), сохранённый в бинарном коде используя k битов. Рассмотрим среднее кодируемых чисел mean. Округлим mean до ближайшей степени 2 в меньшую сторону, получим b. Каждое число n будем представлять, как объединение двух кодовых частей, часть в унарном коде [(n–1)/b] и часть в бинарном коде (n–1)(mod b).
Пример RiceEncoding:
Последовательность: 34, 178, 291, 453
Промежутки: 34, 144, 113, 162
Среднее: mean = (34 + 144 + 113 + 162) / 4 = 113,33
Округляем: b = 64 (6 бит)
Число Разложение Кодирование
34 64 * 0 + ( 34-1) & 63 0 100001
144 64 * 2 + (144-1) & 63 110 001111
113 64 * 1 + (113-1) & 63 10 110000
162 64 * 2 + (162-1) & 63 110 100001
Имя файла, и тип операции(арх или деарх) – параметры командной строки.
Написать архиватор и деархиватор. Протестировать работу архиватора на случайно сгенерированных бинарных файлах, состоящих из целых чисел. Размер заархивированного файла должен быть всегда меньше файла исходного и однозначно деархивироваться до файла, совпадающего с исходным.
Машинное слово – 32 бита. Разбиваем его на нужные промежутки, в которые записываем числа в бинарном коде, а то на какие промежутки разбили – записываем в отдельных контрольных битах этого слова.
Кодирование: разобьём слово на 2 части, 4 бита под управление и 28 битов под данные
1. 1 28-ми битное число
2. 2 14-ти битных чисел
3. 3 9-ти битных чисел
4. 4 7-ми битных чисел
5. 5 5-ти битных чисел
6. 7 4-х битных чисел
7. 9 3-х битных чисел
8. 14 2-х битных чисел
9. 28 1-но битных чисел
В 4 бита запишем схему. Ещё бывают исключения – числа большие 2^28.
Имя файла, и тип операции (арх или деарх) – параметры командной строки.
Написать архиватор и деархиватор. Протестировать работу архиватора на случайно сгенерированных бинарных файлах, состоящих из целых чисел. Размер заархивированного файла должен быть всегда меньше файла исходного и однозначно деархивироваться до файла, совпадающего с исходным.
В представлении не все числа имеют одинаковую битность.
Кодирование: имеет 16 способов записи, использующие все 28 битов данных.
1. 1 28-ми битное число
2. 2 14-ти битных чисел
3. 3 { 10, 9, 9 }-битных чисел
4. 4 7-х битных чисел
5. 5 { 5, 5, 6, 6, 6 }-битных чисел
6. 5 { 6, 6, 6, 5, 5 }-битных чисел
7. 6 { 4, 4, 5, 5, 5, 5 }-битных чисел
8. 6 { 5, 5, 5, 5, 4, 4 }-битных чисел
9. 7 4-х битных чисел
10. 8 { 3, 4, 4, 4, 4, 3, 3, 3 }-битных чисел
11. 9 { 4, 3, 3, 3, 3, 3, 3, 3, 3 }-битных чисел
12. 14 2-х битных чисел
13. 21 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2 }-битных чисел
14. 21 { 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1 }-битных чисел
15. 21 { 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }-битных чисел
16. 28 1-битных чисел
Весь алгоритм также эффективно может быть выполнен с помощью switch условия и фиксированных битовых масок для каждого перехода.
Имя файла, и тип операции (арх или деарх) – параметры командной строки.
Написать архиватор и деархиватор. Протестировать работу архиватора на случайно сгенерированных бинарных файлах, состоящих из целых чисел. Размер заархивированного файла должен быть всегда меньше файла исходного и однозначно деархивироваться до файла, совпадающего с исходным.
Имеем: 1 фирму проката class Allocator, выдающую товары class CleverPtr во временное пользование для N клиентов.
enum Errors { FreeNotAllocated, AllocNoEnoughMemory, AllocNeedDefrag };
class CleverPtr { void* data{}; public: void* get() const; };
class Allocator {
public:
struct BusyBlockDesc { int offset, size, frequency; }; // при каждом обращении через CleverPtr к памяти считать их общее число, чтобы понимать, насколько блок востребован с такими характеристиками
struct BlockDesc { int offset, size; }
Allocator(int full_size);
list<BusyBlockDesc> busy_blocks() const; // блоки памяти с активным CleverPtr
list<BlockDesc> free_blocks() const; // все блоки свободной памяти
list<BlockDesc> hang_blocks() const; // блоки без активного CleverPtr, но явно неосвобождённые
map</*size*/int, /* frequency*/int> stats() const; // статистика востребованности
CleaverPtr alloc(int size); // выделить новый блок
void free(CleverPtr&); // освободить блок, но только если больше нет ссылающихся CleverPtr на него
void realloc(CleverPtr&, int new_size); // увеличить объём памяти в блоке, по возможности расширить
void free_hang_blocks(); // освободить блоки, на которых уже не ссылается ни 1 CleverPtr
void defrag(); // объединение всех свободных блоков в один непрерывный, с изменением адресов внутри некоторых активных CleverPtr
};
Клиент приходит в прокат и берёт во временное пользование товар (alloc) с заданными характеристиками (size). Когда товар перестаёт быть нужен клиенту, то он: либо приходит и лично сдаёт его (free) в прокат обратно, либо отправляет товар назад по почте (удаляет свою переменную CleverPtr). Кроме того, клиент может прийти в прокат за обновлением характеристик товара (realloc), при чём он хочет сохранить свои данные внутри товара. Заведующий прокатом раз в сутки может сходить на почту (free_hang_blocks), чтобы забрать пришедшие к тому моменту товары. Рассеянный клиент может прийти без товара, с намерением сдать обратно в прокат (FreeNotAllocated). Товары могут закончиться (AllocNoEnoughMemory). Товары с заданной характеристикой могут закончиться (AllocNeedDefrag), в этом случае заведующий может устроить инвентаризацию запасов (defrag), чтобы продолжить свою продуктивную работу. Заведующий довольно ленивый (сложность работы должна быть меньше линейной по числу имеющихся блоков! поскольку известно положение всех не выданных товаров) и не будет перебирать все товары понапрасну. При инвентаризации заведующий будет стараться располагать товары, пользующиеся максимальным спросом ближе к кассе (часто использующиеся блоки, размещать в начале общей области памяти), поскольку вероятно они дольше находятся на руках клиентов и лишний раз их не тревожить.
Для инвентаризации () и пере-выдачи - НЕЛЬЗЯ ИСПОЛЬЗОВАТЬ ДОПОЛНИТЕЛЬНУЮ ПАМЯТЬ! для товаров. ВСЁ должно храниться в объёме, в рамках однажды выделенного заданного размера!
Написать тест со случайным поведением клиентов.
Запуск из командной строки со следующими параметрами
./program -f/--full_size <объём_памяти> -n/--num_clients <число клиентов> -e/--events <общее число событий – длина теста> -p/--print_status <раз в p событий печатать полную статистику фирмы> -v/--verbose -h/--help
verbose – печатать события, происходящие в тесте
help – печать инструкции по запуску приложения
Написать простой рекурсивный http-загрузчик текста web-страниц.
Запуск:
./WGet
-u/--url <string> – http-адрес загружаемой web- страницы
-r/--recursive <uint> – загружать ли страницы по ссылкам, найденным на загружаемой странице, и с какой предельной глубиной заходить по этим ссылкам
-t/--tries <uint> – число попыток скачать страницу до выдачи ошибки
-n/--no-parent – загружать страницы не выше по иерархии заданной
-s/--savedir <path> – путь до папки, где сохранять html-страницы
-v –verbose – печатать в stdout подробно производимые операции, без этого флага печатать только ошибки
-h/--help – показать, как использовать программу, выдать аргументы консоли
Проверять статус коды ответов серверов -- 200 (500, 301)
Пример, как можно тестировать
nc -q 3 yandex.ru 80 < GET.txt