Материал: 9
9 лекция.
Сложность можно определить или подсчетом количества флопов (элементарных операций) в зависимости от размерности задачи (обрабатываемых входных данных), или по ключевым признакам типичных сложностей.
Теперь знакомимся еще с одним методом оценки сложности по циклам.
Процесс перебора всех порядков, в которых можно вычислить рассматриваемое произведение n матриц, с целью минимизации числа операций имеет экспоненциальную сложность, что при больших n практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности О(n3).
Это заключение напрямую относится к тому примеру, который мы рассмотрели на прошлой лекции применительно к динамическому программированию.
После сдачи работы с сортировкой и еще одним алгоритмом (интегрирования, интерполяции или др.) вы должны оценить сложность каждого из алгоритмов и сопоставить теоретический вывод с оценкой времени работы метода.
Есть несколько функций для такого рода подсчета, одну из которых мы и рассмотрим.
Показатели сложности необходимо сопоставлять со временем выполнения методов, определение которого называется профилированием. Для
профилирования потоков можно использовать удобную API-функцию
GetThreadTimes:
BOOL GetThreadTimes(
HANDLE hThread, //дескриптор потока (определяется функцией GetCurrentThread)
FILETIME ftCreationTime, // время создания потока FILETIME ftExitTime, // время завершения потока
FILETIME ftKernelTime, // время работы потока в режиме ядра FILETIME ftUserTime); // время работы потока в режиме пользователя
Ну и пример использования этой функции. Порядок действий (пример):
1.Объявляем три переменные типа FILETIME: FILETIME ftKernelTime;
FILETIME ftUserTime; FILETIME ftDummy;
2.Объявляем три переменные типа _int64:
_int64 qwKernelTime, qwUserTime, qwTotalTime;
3. Вызываем функцию GetThreadTimes: GetThreadTimes(GetCurrentThread, &ftDummy, &ftDummy, &ftKernelTime, &ftUserTime);
4. Определяем время выполнения потока: qwKernelTime = FileTimeToQuadWord(&ftKernelTime); qwUserTime = FileTimeToQuadWord(&ftUserTime); qwTotalTime = qwKernelTime + qwUserTime;
printf("\n\nВремя выполнение первого потока: %lld", qwTotalTime)
------------------------------------------------------------------------------------------------------
Есть один тонкий момент. Если функция возвращает нули, то это значит, что методы работают слишком быстро. Это не проблема. Генерируете большой список в районе 2 тыс. строк, после чего засекаете время.
И еще: вы должны знать, какие функции выполняются в режиме ядра. У нас этой теме был посвящен целый параграф.
Безусловно надо знать, чем занимается ядро.
-------------------------------------------------------------------------------------------------------
Помимо оценки сложности и подсчета времени выполнения методов, необходимо оценить ресурсоемкость алгоритмических процессов, то есть каждого из методов.
Для этого надо знать простые понятия по памяти.
------------------------------------------------------------------------------------------------------
Оперативная память называется основной (физической) памятью (ОП) и представляет собой ограниченное фиксированное количество ячеек, каждая из которых имеет свой уникальный физический адрес. Эти адреса используются
процессором для обмена данными с ОП. Данные, которые не помещаются в ОП, располагаются во вторичной (внешней) памяти, роль которой обычно выполняет дисковое пространство. Время доступа ко вторичной памяти на несколько порядков превышает время доступа к оперативной памяти и требует активного содействия ОС. Система управления памятью ОС выполняет распределение ОП между задачами, а также передачу данных между основной и вторичной памятью.
-----------------------------------------
Системное программное обеспечение должно сопоставить каждое имя в пространстве имен программы с физической ячейкой памяти, то есть выполнить отображение пространства имен на физическую память. Если бы это отображение выполнялось напрямую на физические адреса, то возникли бы следующие проблемы:
—ограничение количества одновременно выполняемых задач;
—отсутствие механизма защиты адресного пространства одной задачи от адресного пространства другой задачи и от адресного пространства ядра;
—на этапе компиляции необходимо выделение отдельного пространства физических адресов для каждой задачи, к которому не должны обращаться другие задачи.
------------------------------------------------
Имя в пространстве имен программы - это идентификатор.
Практически все мне показывали таблицу идентификаторов с указанием его имени, типа и диапазона типа.
Прямая привязка идентификаторов к физическим адресам породила бы кучу проблем, которые описаны выше.
Это серьезные проблемы, которые непонятно как обходить.
Поэтому вводятся промежуточные виртуальные адреса, которые составляют виртуальное адресное пространство или виртуальную память. Виртуальная память делит физическую память на разделы и распределяет их между различными задачами. Поддерживаются разделы фиксированного размера (страницы) и переменного размера (сегменты).
Виртуальная память ограничивает задачу теми разделами, которые ей выделяются. Каждая задача выполняется в своем виртуальном адресном пространстве.
Привязка виртуальных адресов к физическим выполняется на аппаратном уровне с помощью устройства управления памятью MMU во время загрузки задачи в память. Виртуальная память может значительно превышать физическую за счет использования вторичной памяти, в которой могут сохраняться временно неиспользуемые данные.
------------------------------------------------
Напомню, что понятие виртуального адресного пространства вводилось в
разделе со сравнением процессов и потоков.
Там как раз говорилось, что у каждого процесса есть своя память, которая защищена от других процессов и которая называется виртуальным адресным пространством.
Виртуальное адресное пространство — это как раз пространство виртуальных адресов.
На этой схеме обозначено, что идентификаторы (логические имена) из пространства имен программы сопоставляются сначала с виртуальными адресами.
Это сопоставление выполняется системой программирования.
А потом уже виртуальные адреса сопоставляются с физическими адресами. Это сопоставление выполняется операционной системой на аппаратном уровне
спомощью устройства управления памятью (Memory Management Unit, MMU). Ну и вкратце рассмотрим работу с виртуальной памятью на уровне использования функции VirtualAlloc. Мы ее не будем использовать на практике, сразу говорю.
------------------------------------------------------------------------------------------------------
Виртуальное адресное пространство каждой задачи практически полностью свободно. Для использования какой-либо его части необходимо выделить в нем определенные регионы с помощью функции VirtualAlloc, то есть выполнить резервирование. При этом система выравнивает начало региона в соответствии
сгранулярностью выделения памяти, которая обычно составляет 64 Кб. Кроме того, система обеспечивает кратность размера региона размеру страницы. При этом система автоматически округляет запрашиваемый размер региона до большей кратной величины.
---------------------------------------------------------------------
Ключевые термины - это гранулярность и размер страницы.
Пример. Для процессоров Pentuim размер страницы составляет 4 Кб. Если задача попытается зарезервировать 10 Кб, то будет выделен регион размером 12 Кб.
Когда регион становится не нужен, его необходимо освободить вызовом функции VirtualFree. Для использования зарезервированного региона адресного пространства необходимо выделить физическую память и спроецировать ее на этот регион. Такая операция называется передачей физической памяти и выполняется с помощью функции VirtualAlloc.
----------------------------------------------------------------------
Из этого описания надо сделать вывод о том, что сначала надо зарезервировать участок памяти, чтобы потом этот участок был физически передан приложению.
Эта схема аналогична бронированию номера и фактической передаче номера при заселении.
То есть номер в гостинице надо сначала забронировать, а при заселении фактически в него заселиться.
Здесь такая же схема.
Ну и рассмотрим функцию VirtualAlloc.