Библиотека Интернет Индустрии I2R.ru

Предисловие.

Технологии <ускользающих> входят в число низкоуровневых методологий Оморфо программирования. С недавнего времени, автор использовал данный подход при использовании памяти. Результаты оказались превосходными, и поэтому он приводит несколько слов о принципах реализации ускользающей памяти в этой небольшой статье.

Внимание! В этой статье не рассматривается вариант с многопоточной организацией доступа, дабы не делать статью очень длинной и скучной.

Проблемы с временной памятью.

При написании программ под Win32 постоянно сталкиваешься с тем, что тому нужно 256b, то тому дай 512b. Различные функции требуют множество небольших областей памяти, для всевозможных операций. При этом требования к скорости исполнения данных функций обычно минимальны (особенно если они связаны с GUI), или наоборот максимальны. При этом, как правило, память нужна им ненадолго, и её не должно быть много. Если вы загляните во все книги и учебники, то без сомнения найдёте там, либо динамическое выделение памяти силами Win32, либо выделение её в стеке. Но если вы знакомы с ужасной проблемой дефрагментации, борьбе с которой я мог бы посвятить и книгу, то сразу бы отказались от мысли выделить несколько байт, ради какой- нибудь там процедуры. Стек - классика, от которой не стоит отказываться, и которая для некоторых случаев есть единственно верным решением, только обращаться к этой памяти не так легко, через тяжеловесный ebp-xxh.

Но есть и другой, на первый взгляд самый очевидный метод, и несколько неприятный - память фантом, чем-то похожая на блок COMMON, чем-то на что-то ещё.

<Классическая> реализация ускользающих.

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

Первой попыткой автора применить этот принцип, была обработка строковых данных и их форматирование, конвертирование число-строка, и наоборот. Поэтому автор называет приведённую ниже реализацию <классической>, и, между прочим, наиболее лёгкой.

Пусть у вас есть функция A, которой требуется 256b для хранения полного имени файла. Путь есть функция B, которой требуется 256b для форматирования строки. Функция форматирования F, вызываемая функцией B, занимает относительно много времени. Путь есть буфер Buff размером 256b.

В том случае, если вы организуете буфер просто как общую память, то уже не сможете, вызывать из функции A функцию B. Даже если вы и не собираетесь этого делать, функции B придётся каждый раз вызывать функцию F для форматирования, хотя очень возможно, что данные подлежащие форматированию с последнего момента не изменились, и что можно было бы воспользоваться когда-то отформатированными данными в буфере. (Такой метод называется отложенными вычислениями) В этом случае удобно воспользоваться ускользающей памятью.

Данные, записанные в ускользающую память, могут быть разрушены в любой момент, то есть память как бы исчезает, независимо от функций её использующих. Именно по этому она и называется <ускользающей>. Но её легко вызвать заново, и при этом быть уверенным, что это не вызывает никакой дефрагментации, и что где-нибудь, эта память будет выделена.

Таким образом, функция B, осуществляет попытку обратиться к блоку памяти, в том случае, если память была с последнего момента разрушена, функция B, вызывает функцию форматирования F, и снова использует выделенный диапазон. Данные в буфере не будут разрушены пока кто-нибудь не вызовет функцию A.

Вот так всё предельно просто.

Классификация ускользающей памяти.

Теоретическое определение ускользающих.

Ускользающим называется такой формальный объект, подверженный влиянию, или управлению несколькими независимыми системами; либо сам осуществляющий своё управление, независящие от всех или некоторых внешних связей.

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

Ускользающую память удобно классифицировать по следующим признакам:

1. По месту размещения.
   • статическая;
   • динамическая;
   • стековая;
2. По способу виду адресации.
   • фиксированная;
   • свободная;
3. По виду доступа. (<не для слабонервных ?!>)
   • поточная;
   • асинхронная;
4. По скорости получения.
   • безразличная;
   • умеренная;
   • немедленная;

Данная классификация не полная, можно определить свои критерии оценки памяти, влияющие на выбор алгоритмов реализации.

Комментарии.

По виду адресации:

Здесь идёт речь о двух вариантах обращения к памяти, через фиксированный адрес, или через полученный указатель. Как правило, первый способ используется кодом, требующим высокой скорости выполнения. В этом случае доступ к памяти осуществляется как к переменной.

Менеджер ускользающей памяти.

Например, одна и та же функция прорисовки использует небольшой буфер, для создания градиента в формате DIB перед окончательным выводом на экран. Эта функция прорисовки одна для нескольких окон. В этом случае можно хранить в статической переменной последнее окно, потребовавшее прорисовку, и если сам градиент не изменил формы, использовать старый буфер. В данном случае, сама функция прорисовки и является менеджером ускользающей памяти (здесь это лучше назвать отложенными вычислениями), однако несложно построить небольшой API для использования его в вашей программе. При этом заключить в него не только управление ускользающей памятью, но и памятью вообще. Такая надстройка над Win32 вовсе не снизит скорость исполнения, а вовсе наоборот, повысит эффективность использования ресурсов системы в вашем приложении, да и обеспечит некоторую переносимость на будущее.

Создание общей системы управления ускользающей памятью, позволяет, во- первых, использовать её как обычную динамическую, следить за ресурсами системы, выделять память большими блоками фиксированной длинны по надобности, и таким образом избегать дефрагментации.

Привязка к объектам.

Все функции по работе с ускользающей памятью, так или иначе, привязываются к объекту, представляющему собой описание памяти, заказанной у менеджера. Хендл, который используется этими функциями, должен быть указателем на структуру описывающей такую заказанную память. В сущности, этот объект представляет собой абстракцию простой статической памяти, а в действительности никакой памяти может и не быть. Вот его структура:

ESCMEM _$OBJ	struct
	state		dd	?	; Поле состояния\описания.
	pescm		dd	?	; Указатель на структуру ускользающей памяти.
	pointer		dd	?	; Указатель на саму память.
	pexdata	dd	?	; Указатель на расширенные данные объекта:. и т.д.
ESCMEM _$OBJ	ends

Поле pescm содержит указатель на структуру, описывающий блок последнего (!!!) полученного ресурса памяти, так же как и поле pexdata. Поле state описывает настройки и характеристики объекта и имеет следующий формат:

Бит 0: Флаг занятости памяти (указывает на то, что она в принципе занята) fbusy. Бит 1: Флаг использования памяти. fstate Бит 2-5: Флаги приоритета памяти P0 - P3. Бит 6-7: На ваше усмотрение (зарезервировано). Бит 8-15: Тип используемой памяти (изменяемая размер, и т.д.). Бит 16-23: Какие-нибудь флаги: Бит 24-31: Число занимаемых блоков памяти (один блок, как правило, 256 байт)

Флаг сброса занятости не имеет для данной структуры большого веса, и предназначен для описания в структурах описывающих саму память. Следующие поля будут рассмотрены ниже.

Описание самой памяти осуществляется системой векторных потоков, то есть несколькими массивами.

Первый массив (как правило, массив байт, но можно и битовый массив, если скорость не так важна.) как раз является массивом полей state в вышеописанной структуре. Теперь роль нулевого бита является одной из основных, и мы плавно переходим в следующую главу.

Алгоритм поиска свободного блока памяти, и приоритеты сброса.

Физически блок ускользающей памяти содержится как один непрерывный. Его состав, описывается массивом байт полей типа state. Главной задачей этого массива следить, какой блок памяти свободен, а какой нет. Чтобы облегчить задачу можно поделить всю память на блоки по 256 байт, и сказать, что каждый элемент данного массива описывает один такой блок памяти. При выделении памяти занятые участки будут помечаться флагом fbusy, а участки c которыми сейчас идёт работа - флагом fstate. Но существует ещё один интересный нюанс, связанный с применением <приоритетов сброса>. При помощи приоритета сброса можно указать, какую память следует занимать первой, а какую последней. Существует несколько способов как достичь такого эффекта с наименьшими затратами по времени, первый способ заключается на деление общего банка памяти на несколько зон, три или четыре (как правило три). При этом более высший приоритет хранить в более высшей зоне. Второй, как вы видите это битовые флаги. Для разметки приоритета используются биты 2-5 байта state. В сущности, эти два способа употребляются одновременно. Приоритет назначается флагами, так как легче (быстрее) вести сравнение, то есть проверка приоритета сводится к проверке маской битов, какой- нибудь битовой командой, что эффективнее, нежели командами группы вычитания.

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

Для этой цели служит ещё один массив, на этот раз массив структур из двух DWORD.

ESCMEM _$DATA	struct
	size		dd	?	; Размер общего выделенного блока.
	pobj		dd	?	; Указатель на объект, которому принадлежит этот ; 
блок(и).
ESCMEM _$DATA	ends

Количество элементов этого массива в точности равно количеству элементов в массиве байт, и равно общему числу блоков памяти.

Алгоритм поиска свободного блока состоит в том, чтобы обнаружить свободный блок этого приоритета или ниже, в крайнем случае, выше, и при том, чтобы по возможности не уничтожать уже существующие занятые блоки. Однако мы должны решить, что значит свободный блок. Первый случай это сброшенный флаг fbusy, тогда блок действительно свободен. Второй случай это установленный fbusy, но сброшенный fstate, будем называть эту память: свободная память второго рода. Тривиально данный алгоритм представляет собой элементарный цикл перебора байт в первом массиве в поиске свободного элемента. При этом поиск ведётся по двум флагам, сначала по флагу fbusy, а потом по флагу fstate. С первым флагом всё просто: если он сброшен, то память свободна, если же нет, то вся роль переходит ко второму флагу, при этом если он установлен, то о занятии памяти не может быть и речи, а если сброшен - означает как бы условие <желательно не занимать>. Далее приведен алгоритм поиска в так называемом <почти полном> варианте, читателю не следует пока в него углубляться, просто прочесть.

Первый этап состоит из поиска свободного пространства блоков, достаточных для заказанного размера памяти, которая может занимать не один блок. При этом блоки естественно не должны прерываться. В случае если элемент со свободным флагом fbusy найден:

1. следует проверить статус сброса данного блока, если статус сброса равен запрашиваемому, то следующий пункт, иначе искать дальше.
2. если запрашиваемая область памяти, более чем один блок, следует проверить, свободен ли следующий блок (fbusy = 0), если нет запомнить как вариант на худший случай, и продолжить поиск.
3. если пункты 1 и 2 удовлетворены занять блок.

В том случае, если свободный блок не был найден среди блоков равного уровня сброса, следует занять:

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

Следует отметить, что все вышеприведенные пункты должны вести так же с параллельным поиском более подходящего варианта на тот случай, если блока со свободным флагом fbusy так и не будет найдено. В этом случае более подходящим считается:

1. Наибольшее непрерывное пространство блоков со свободным fbusy, которого не хватает для покрытия заказа, но далее которых следующие блоки имеют свободный флаг fstate.
2. В случае невыполнения условия пункта 1, следует занять любой непрерывный блок, в области данного приоритета, из блоков с установленным флагом fbusy, но сброшенным флагом fstate.

В случае если вся память окажется занятой попытаться взять свободную память из более высоких приоритетов, но только со свободным флагом fbusy. И, в конце концов, если всё занято, прибегнуть к динамическому выделению памяти средствами операционной системы.

Этот алгоритм можно как упрощать, так и усложнить. Здесь приведен его почти полный вариант. Одним из дополнений к этому алгоритму можно включить процедуру дефрагментации, которая перераспределит блоки так, чтоб образовалось требуемое свободное пространство. Ясно одно, что в зависимости от <напряжения> пространства блоков памяти, этот алгоритм выполняется относительно долго. Конечно, есть несколько методов, как ускорить его и сделать более умнее. Например, следить за наличием свободных блоков fbusy = 0, и если таковых нет, заранее можно пропустить несколько пунктов с вышепредставленного алгоритма. Далее мы рассмотрим усовершенствования более подробно. Но важно понять следующее, то, что память можно выделять быстрее, но неэффективно для других, или очень медленно, но максимально эффективно. Чем и следует воспользоваться!

Теперь весь алгоритм мы повторим, графически моделируя ситуации, как говорится, обыграем его.

Пусть у нас есть два приоритета сброса и следующие свободные блоки памяти: 256b

Пусть кто-то заказал блок в 256b в высшем приоритете, а потом, ещё следующие 256, и ещё, но уже последние 512b.

На рисунке одним цветом показаны несколько блоков выделенные как один регион. И разными цветами, как разные регионы. Синий цвет каёмки означает установленный флаг fstate, отсутствие каёмки, означает сброс этого флага. Пусть следующее состояние таково:

Как мы видим первый блок высшего приоритета, сбросил флаг fstate, а второй блок совсем свободен, при этом второй блок нижнего приоритета имеет fstate = 0, а третий блок занят совсем fstate = 1.

Пусть нам следует выделить память в 512b высшего приоритета, тогда будет выбраны блоки 1 и 2 в зоне высших приоритетов, если же нам следует выделить 768 байт, то будут заняты: четвёртый блок из нижней зоны и два из высшей. При этом если потребуется занять блок в 256b при этом будет выделен, первый свободный блок в высшем уровне. А теперь такая картина:

Снова требуется выделить блоки 256, 512, 768 байт. В первом случае будет выделен первый блок с высшим приоритетом, но с fbusy = 1. Это важно!

Методы совершенствования поиска.

В действительности, как правило, существует три уровня приоритета сброса, а значит и три сегмента. При этом, как мы увидели, более высший приоритет может диффундировать в более нижний и иногда в более высший, если там нашлись блоки с fbusy = 0. Следует не просто говорить за методику совершенствования поиска, а за эффективность общей концепции выделения памяти. Первым шагом является направление поиска, для самого высшего приоритета, поиск следует производить с верху в низ, а для среднего и нижнего вверх. Другим механизмом ускорения поиска является <память последнего>. В этом случае менеджер держит индекс блока, за которым идут свободные, либо индекс последнего освобождённого блока. Вот в чём суть: В идеале считается, что блоки будут заниматься снизу вверх (и сверху вниз для высшего приоритета), поэтому можно хранить индекс блока, перед которым гарантированно все заняты. В том же случае, когда блоки будут освобождаться ставить этот указатель на них. Следует отметить, что, как правило, блоков памяти, в конце концов, не много, и поэтому ощутимой прибавки в скорости не получается, если не наоборот.

Без внимания осталась одна ситуация, а что происходит, если более высший приоритет разместился в зоне более низшего. В этом случае, выделенная память будет вытиснена (если fstate = 0) более низким приоритетом в том случае, если он не нашёл свободного блока в области более высших приоритетов т.е. блоков с fbusy = 0.

Заключение.

Нерассмотренными остались многие нюансы реализации, а так же асинхронная модель использования, использование ускользающей памяти в группах и т.д. В действительности приведённая архитектура менеджера, используется не только с ускользающей памятью, а так же: <буферами>, <временной памятью>. Однако эти темы уже следующих статей.