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

"Что мы можем описать?
Увы! Это всегда лишь то, что начинает увядать и портиться".
Ницше "По ту сторону добра и зла".

Оглавление.

Постановка задачи.
Работы с большой оперативной памятью при 16-разрядной адресации.

§1 Постановка задачи.

Статья навеяна многократным изучением книги Д. Кнута "Исскуство программирования для ЭВМ" [1] и личным опытом аммировании алгоритмов, требующих большого объема оперативной памяти. Описанные в [1] методы выделения "наиболее подходящего", "первого подходящего" и "системы близнецов", а также методы освобождения оперативной памяти в настоящее время относятся скорее к операционным системам (ОС) чем к средствам разработки приложений (СРП), что отмечено в конце главы 2.5 II тома [1] самим низации эффективного использования в одной из задач 1 Гбайта оперативной памяти уже в эпоху Windows 95/98/NT/2000. Это обусловило желание высказаться по поводу работы с оперативной памятью в части касающейся СРП. Размер доступной для программы оперативной памяти зависит от разрядности вычислительного устройства, разрядности поддерживаемой ОС и СРП, на которых происходит компиляция или интерпретация алгоритма. Обычно, сначала появляются вычислители с большей разрядностью, затем для них делаются ОС и СРП. В середине 90 г.г. это были 16 и 32-разрядные процессоры, ОС и СРП. Новое тысячилетие, по-видимому, будет эрой 64-разрядных вычислительных средств. Если x0,x1,…,xn-1,xn - адрес идентификатора в программе, где xiО{0,1}, то максимально возможный адрес 2n+1. Для 16-разрядных приложений (n=15) это число составляет 65536, для 32-разрядных приложений 4294967296 (» 4 Гбайта), для 64-разрядных приложений 1,844674407371*10+19. Обычно на эти ограничения в адресации накладываются дополнительные ограничения присущие ОС и СРП. Например, в ОС Windows 95/98/NT/2000 реальный размер максимальной адресации меньше, так как часть доступной оперативной памяти забирает ОС для своих нужд. И ещё СРП позволяют создавать приложения, как правило, с фиксированной разрядностью в смысле адресации. Управление оперативной памятью всегда было актуальной задачей, так как она является одним из дорогостоящих ресурсов предоставляемых вычислительными устройствами. В таблице показана динамика цен оперативной памяти в зависимости от размера для двух фирм в августе 2000 года.

Название фирмы	Серийный номер (part number)	Объём ОП	Цена в долларах США
Kingston Technology	KTH6521/64	32 Мбайта	168
Kingston Technology	KTH6521/64	64 Мбайта	143
Kingston Technology	KTH6521/128	128 Мбайта	269
Kingston Technology	KTH6521/256	256 Мбайта	521
Kingston Technology	KTH6742/512	512 Мбайта	1220
HP	D6522A	64 Mбайт	126
HP	D6523A	128 Mбайт	239
HP	D6743A	256 Mбайт	479
HP	D6742A	512 Mбайт	2643

Тенденция очевидна, за исключением схемы с номером KTH6521/64, из-за большого спроса на оперативную память в 64 Мбайт. Перед тем как приступить к основному повествованию оговорюсь, что далее речь будет идти о структурах данных состоящих из однотипных элементов. Это линейные списки [1] и массивы.

§2 Работы с большой оперативной памятью при 16-разрядной адресации.

Во времена, когда 640 килобайт (conventional memory или обычная память, или основной памятью) была пределом доступной для программистов оперативной памятью, приходилось бороться за десятки "лишних" килобайт, придумывая драйверы, позволяющие выйти за пределы возможностей 16-разрядных приложений и ограничений ОС. Например, стандарты EMS (expanded memory), которая продавалась на отдельной плате со своим процессором, и XMS (extended memory), которая была организована так же, как и основная. В настоящий момент интерес к таким драйверам снизился в связи с появлением процессоров, ОС и СРП с большей разрядностью, но для иллюстрации идей и методов представляется интересным рассмотреть и этот случай управления оперативной памятью. В ОС DOS (disc operation system) оперативная память распределялась следующим образом:

0-640Kбайт - обычная (conventional) память;

640Kбайт-1024Kбайт - старшая (upper) память (UMB);

1024Kбайт-1088Kбайт - верхняя (high) память (HMS);

1088Кбайт и выше - дополнительная (extended) память (XMS);

на отдельной плате - расширенная (expanded) память (EMS). Предположим на Вашем компьютере 2 Мбайта оперативной памяти. К 640 Кбайтам можно адресоваться непосредственно из программы, причём размер одного блока, т.е. максимальная длина оперативной памяти для переменной (идентификатора массива) не должна превышать 65519. ОС брала память для своих нужд также из 640 Кбайт. Видите ли, первоначально (при создании DOS) предполагалось, что максимальный объём требуемой оперативной памяти не превысит 1 Мбайт. Память от 640К до 1М (upper memory, старшая память, но ее нередко называют верхней памятью) была занята чем попало - и видеобуфером экрана, и областями специально для компьютера PS/2, и так далее. В дальнейшем функциональное назначение верхней памяти расширилось, в неё стали записывать резидентные программы в целях экономии основной памяти. Теперь представим, что перед нами стоит задача написать систему управления базой данных, размер записи которой составляет 1 Кбайт, а количество записей может составить несколько тысяч. Причём, для быстроты работы программы все или большая часть записей должны находиться в оперативной памяти. Понятно, что без дополнительных ухищрений в DOS такая задача решена быть не может, т.к. в ОС нет ресурса - оперативной памяти размером в несколько Мбайт с прямой адресацией. Но физически такая память есть. Надо только обойти ограничение, заложенное в ОС, чтобы заставить программу работать быстрее при выполнении операций чтения и записи в оперативную память. Обычно это делается при помощи организации связи между небольшим окном памяти с прямой адресацией, куда можно обратиться с помощью быстрых команд ОС, и большим окном верхней памяти, куда можно обратиться с помощью медленных команд ОС, но всё же более быстрых чем команды чтения/записи на долговременные носители данных. Можно долго рассказывать, как это сделать на уровне команд DOS, а можно воспользоваться библиотекой, например Object Profetional Copyright © фирмы TurboPower Software 1987-1992 и обсудить проблему на более высоком уровне. Что мы и сделаем. Для иллюстрации идей, рассматриваемых в данной статье, будет использовать язык Pascal с его реализацией в виде Borland Pascal 7.0 и Delphi 1/2/3/4/5 Copyright © фирмы Borland International, а позднее фирмы Inprise Corporation 1983-1999г.г. Выбор данных СРП обусловлен тем, что это были одни из первых средств в нашей стране, которые поддерживали объектно-ориентированное программирование (ООП) и динамически развивались. Надеюсь у заинтересованных лиц не вызовет затруднений перевести тексты на другой язык программирования, каждый из которых является канонической формой представления алгоритма, в случае необходимости. В фрагментах программ многоточием отмечены пропущенные для краткости операторы. Жирный шрифт - ключевые слова языка. В библиотеке Object Profetional (программирование на Borland Pascal 7.0) имеется объект OpArray наследуемый от AbstractArray, позволяющий управлять памятью при помощи больших двумерных массивов.

OpArray = object(AbstractArray) constructor Init(Rows, Cols : Word; ElementSize : Word; FileName : String; HeapToUse : LongInt; ArrayOptions: Byte; var Priority : AutoPriority); .... end; Объект поддерживает размещение данных в памяти с прямой адресацией, размещение данных в "верхней" памяти и временных наборах данных на долговременных носителях. Для унификации методов доступа к данным и обработки ошибок, возможно создание дополнительного объекта.

PAsciizStringArray = ^TAsciizStringArray; TAsciizStringArray = object(TObject) ... constructor Init(Rows, Cols, Element : Word; FileName: String; HeapToUse: LongInt); procedure InsertQ(var Item: Asciiz); ... end; var OA: OpArray; ... constructor TAsciizStringArray.Init(Rows, Cols, Element : Word; FileName: String; HeapToUse: LongInt ); const ArrayOptions : Word = LDeleteFile + LRangeCheck; MyDefaultPriority:AutoPriority=(LXmsArray,LRamArray,LEMSArray, LVirtualArray); {массив может располагаться в ОП с прямой адресацией (LRamArray), в "верхней" ОП (LXMSArray и LEMSArray) и во временных наборах данных (LVirtualArray)} ... var E: Word; begin XmsAvailable := TRUE; OA.Init(Rows, Cols, Element, FileName, HeapToUse, ArrayOptions, MyDefaultPriority); Count := 0; E := OA.ErrorA; if E <> 0 then ErrorM(E, Count); {обработка ошибок} OA.ClearA(ItemDefault, ExactInit); {предварительная очистка массива} E := OA.ErrorA; if E <> 0 then ErrorM(E, Count); {обработка ошибок} ... end; procedure TAsciizStringArray.InsertQ(var Item: Asciiz); var E: Word; begin OA.SetA(count, 0, Item); {метод вставки, наследуемый от AbstractArray } E := OA.ErrorA; if E <> 0 then ErrorM(E, count); Inc(Count); end; ... Для использования объекта надо описать его и запросить ресурс в оперативной памяти.

... PS: PAsciizStringArray; AS: Asciiz; ... PS := New(PAsciizStringArray, Init(MaxSize, 1, SizeOf(S), 'kadr.wrk', MaxAvail div 2 )); ... PS^.InsertQ(AS); {вставка новой строки в динамический массив} ... Попутно отметим, что в объекте TAsciizStringArray могут быть решены также вопросы отсева дубликатов, поиска, сортировки и другие, выходящие за рамки тематики статьи. Также обратите внимание на размер запрашиваемой памяти с прямой адресацией - параметр HeapToUse, который равен половине доступной памяти (через функцию MaxAvail). Это необходимо предусматривать, т.к. возможны явные или неявные запросы на свободную память из других мест Вашей программы или из программ работающих параллельно с Вашей и требующей памяти, для избежания коллизий. Программа, фрагменты текста которой приведены выше, будет работать в DOS или как эмулируемое DOS приложение в последующих ОС Windows фирмы Microsft. В поддиректории "XMS в DOS" можно найти исходные тексты системы "Кадры", при программировании которой использовался вышеописанный механизм хранения данных.

Содержание раздела