os-course/lab/vtld

Базовый трек. Лабораторная работа 1

Вариант: cpu-dedup ema-replace-str

Часть 3. Анализ системы и мониторинг

Разработайте параметризируемую программу-нагрузчик, которая будет однопоточно нагружать подсистему ввода-вывода (IO). Она должна принимать на вход следующие параметры:

• rw: read/write - режим нагрузки: чтение или запись;
• block_size: <number> - размер блока в байтах, с которым производится чтение/запись;
• block_count: <number> - количество блоков;
• file: <path string> - имя файла, с которым происходит работа;
• range: <number>-<number> - границы в пределах файла, в которые должны осуществляться запись/чтение, значение по умолчанию, 0-0, означает, что доступен весь файл;
• direct: on/off - открывать файл с опцией O_DIRECT (в обход кэшей ОС) или нет;
• type: sequence/random - режим выбора следующего блока для записи/чтения последовательно или случайно;

Разработайте комплекс программ-нагрузчиков согласно выданному варианту. Каждый нагрузчик должен принимать параметр, который определяет количество повторений для алгоритма, указанного в задании, а также другие вспомогательные параметры. Варианты программ рассчитаны так, чтобы по-разному нагружать вычислительную подсистему (CPU) и подсистему ввода-вывода (IO) - это необходимо учитывать при их реализации. Разработанные программы необходимо скомпилировать без дополнительных опций оптимизации компилятора.

Проведите исследование поведения ОС во время исполнения разработанных программ-нагрузчиков по следующему плану:

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

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

3. Определите количество одновременно запущенных процессов с программой-нагрузчиком, которое эффективно нагружает все ядра процессора в вашей системе. Как распределяются показатели времени USER%, SYS%, WAIT%, а также полное время выполнения нагрузчика, какое количество переключений контекста (вынужденных и невынужденных) происходит при этом? Подумайте над тем, как вы определяете эффективность.

4. Увеличьте количество нагрузчиков вдвое, втрое, вчетверо. Как изменились исследуемые показатели? Почему?

5. Объедините программы-нагрузчики в одну, реализованную при помощи потоков выполнения, чтобы один нагрузчик эффективно нагружал все ядра вашей системы. Как изменились показатели времени для того же объема вычислений? Запустите одну, две, три таких программы. Как изменились исследуемые показатели? Почему?

6. Скомпилируйте программу-нугрузчик с опцией агрессивной оптимизации. Как изменились исследуемые показатели? На сколько сократилось реальное время исполнения программы нагрузчика? Почему?

В процессе защиты вашей работы преподаватель будет просить вас запустить программу-нагрузчик с различными комбинациями параметров и просить объяснить результат.

Требования к реализации

1. Программа (комплекс программ) должна быть реализован на языке C.

2. Дочерние процессы должны быть созданы через указанные в варианте системные вызовы операционной системы, с обеспечением корректного запуска и завершения процессов. Запрещено использовать высокоуровневые абстракции над системными вызовами. Необходимо использовать, процедуры libc.

Требования к отчету и защите

Отчет должен содержать:

1. Титульный лист с указанием номера и названия ЛР, вашего ФИО, ФИО преподавателя практики, номера вашей группы, варианта ЛР.

2. Текст задания в соответствии с вариантом.

3. Листинг исходного кода всех программ, написанных в рамках данной ЛР.

4. Предположения о свойствах программ-нагрузчиков

5. Результаты измерений и метрик программ-нагрузчиков, полученных инструментами мониторинга. Должно быть описано, какие утилиты запускались, с какими параметрами и их вывод.

6. Сравнительный анализ ожидаемых и фактических значений исследованных показателей.

7. Заключение.

Студент должен быть готов:

1. Продемонстрировать работоспособность Shell и предоставить исходный код.

2. Воспроизвести ход работы по исследованию поведения ОС и продемонстрировать схожие результаты работы программ-нагрузчиков.

3. Ответить на вопросы по реализации программ и контрольные вопросы.

Описание вариантов

Нагрузчик вычислительной подсистемы (группа cpu):

• cpu-factorize: Разложение числа на простые множители. Задаваемое число должно являться произведением нескольких больших простых чисел.

• cpu-sort: Любая сортировка массива чисел за N*log(N) и любая за N**2. Алгоритм должен быть реализован самим студентом, а не взят из стандартной библиотеки.

• cpu-short-path: Поиск кратчайшего пути в графе. Граф генерируется в момент запуска или записан в исходный код.

• cpu-linreg: Построение модели линейной регрессии для последовательности случайных чисел. Количество чисел и диапозон значений задаются параметром.

• cpu-dedup: Дедупликация элементов в массиве. Массив генерируется на основе случайных чисел. Размер массива задаётся параметром.

• cpu-mat-mul: Перемножение матриц. Размер матриц задаётся параметром, а элементы матриц генерируются на основе случайных чисел.

• cpu-calc-md5: Подсчитать хеш md5 для текста полученного конкатенацией фрагментов текста выбранных с помощью генератора случайных чисел.

• cpu-calc-crc: Посчитать контрольную сумму crc для текста полученного конкатенацией фрагментов текста выбранных с помощью генератора случайных чисел.

Нагрузчик, работающий с внешней памятью (группа ema):

• ema-replace-int: Поиск элемента в массиве чисел во внешней памяти и замена значения на другое. Файл для поиска значения генерируется в произвольном формате, размер задаётся через параметр.

• ema-replace-str: Поиск подстроки в тексте во внешней памяти и замена на другую строку того же размера. Файл для поиска значения генерируется в произвольном формате, размер задаётся через параметр.

• ema-sort-int: Сортировка массива чисел во внешней памяти. Весь массив не может быть загружен в память, поэтому сортировка происходит частями.

• ema-traverse-graph: Обход k-регулярного направленного графа, сериализованного в файл, и выполнение модифицирующей операции над определенной вершиной графа. Поиск вершины происходит по хранимому в ней значению, возможно с ограничением глубины поиска. Формат хранения: вершина (struct Node) определяется её отступом от начала файла (id=index*(sizeof struct Node)), в вершине хранится одно значение типа фиксированного размера и k номеров вершин, в которые из неё можно попасть; в файле вершины хранятся последовательно с выравниванием соответствующим размеру структуры. Тип значения, хранимого в вершине, и значение k подбираются таким образом, чтобы с учетом выравнивания не было неиспользуемой памяти. При генерации графа случайно задается значение, хранимое в вершине и номера соседних вершин, отдельным параметром генератора задется шанс получения номера соседней вершины больше или меньше номера данной вершины (соседняя вершина раньше или позже).

• ema-join-*: Необходимо реализовать алгоритм equi-join для объединения таблиц в файлах. На вход подаются два файла, результат их объединения пишется в новый файл. В первой строке файла содержится количество строчек в файле. В каждой последующей строчке входного файла содержится два значения, разделенных пробелами: численный идентификатор и строка без пробелов фиксированного размера 8 байт. Строка является валидным английским словом. Таблицы необходимо объединять по идентификатору.

  По варианту выдается стратегия джоина:

  • ema-join-nl: Nested Loop Join
  • ema-join-hash: Hash Join Join
  • ema-join-sm: Sort + Merge Join

  Количество строк входных таблиц включают все комбинации пар значений: 5, 10, 100, 1000, 10000."