5.1. Размещение и организация

адресации данных в памяти ЭВМ

Понятия основной и внешней памяти

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

Для хранения данных ЭВМ имеет ячейки памяти, которые характеризуются длиной, т.е. числом бит информации, которые можно поместить в нее. В совре­менных ЭВМ элементарная ячейка памяти, как правило, имеет длину один байт, позволяющую разместить 8 бит информации.

В ЭВМ выделяют основную и внешнюю память.

Основная память, в свою очередь, состоит из оперативного запоминающего устройства (ОЗУ) и постоянного запоминающего устройства (ПЗУ). В совре­менных ПЭВМ основная память размещается на материнской плате.

Данные перед их обработкой и программы перед исполнением помещают­ся в ОЗУ. Такая память используется для временного хранения, ее содержимое может меняться в процессе работы ЭВМ и не сохраняется при выключении питания. ПЗУ содержит данные и программы, которые в процессе работы не меняются и сохраняются при выключении питания.

В современных ЭВМ может быть несколько типов ОЗУ и ПЗУ, различа­ющихся скоростью выполнения операций чтения (записи) в ячейке памяти и функциональным назначением (кэш-память, стековая память, BIOS и др.).

Внешняя память представляет собой дополнительные, подключаемые к ЭВМ устройства. Классическим примером такой памяти является жесткий диск (винчестер). Он используется для долговременного хранения больших массивов данных и программ, которые на нем могут перезаписываться и сохра­няться при выключении питания ЭВМ.

Основную память ЭВМ условно можно представить в виде некоторой ленты, разделенной по длине на клетки, каждой из которых сопоставлена определенная ячейка памяти. При этом каждой клетке (ячейке) соответствует адрес, определя­ющий ее место на ленте. Первая ячейка имеет адрес 0, вторая - 1, третья - 2 и т.д. Аппаратурная часть ЭВМ имеет специальные устройства, которые позволяют,

258

зная адрес ячейки, занести в нее необходимые данные или прочитать ее содержи­мое. Адрес формируется специальной электронной схемой, выход которой назы­вают шиной адреса. В первых персональных ЭВМ (IBM PC AT) этой шиной формировался 20-разрядный адрес. В современных ПЭВМ адрес задается кодом в 32 и более разрядов. Очевидно, что n-разрядный адрес позволяет работать с памятью не менее 2" байт.

С целью увеличения адресного пространства в ЭВМ применяют сегмен­тирование памяти. При этом основная память разделяется на части-сегменты, а адрес задается двумя числами: первое - номер сегмента, второе - место ячейки памяти в сегменте. Возможна также сегментно-страничная схема распределения памяти. В этом случае в сегментах выделяются более мелкие части, называемые страницами, и тогда для указания места ячейки памяти надо задать три числа, которые определяют сегмент, страницу и место ячейки в странице.

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

Адресация ячеек памяти

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

При работе с массивом, представляющим собой последовательность ячеек с данными, для выбора необходимой ячейки используется адресация с указани­ем смещения (рис. 5.1). Например, если R задает адрес начала массива (адрес первой его ячейки) и надо прочитать 5-ю ячейку массива, то программист ука­жет адрес R+4.

Рис. 5.1. Адресация в одномерном массиве

Очень часто данные удобно обрабатывать, считая, что они представлены в памяти ЭВМ в виде двухмерной структуры - таблицы или матрицы (хотя, как отмечалось выше, с точки зрения адресации основная память - это одномерная структура, в которой ячейки памяти следуют одна за другой).

259

Предположим, что таблица содержит 4 строки и 4 столбца, причем значения эле­ментов строк располагаются в ячейках памяти ЭВМ последовательно друг за дру­гом, как показано на рис. 5.2. Зная структуру размещения данных в памяти, нетруд­но вычислить место любого элемента таблицы. Это можно сделать по формуле

A = r+[n(i-l) + (k-l)],

где г - адрес начала таблицы;

п - число элементов в строке (число столбцов);

ink- номера строки и столбца, на пересечении которых находится нужный элемент.

Так, на рис. 5.2 адрес элемента на пересечении 3-й строки и 3-го столбца равен: А = г+[4(3-1) + (3-1)] = г+10. г+10

Адреса

Рис. 5.2. Размещение табличной структуры в памяти ЭВМ

Практически все алгоритмические языки высокого уровня позволяют про­граммисту работать с одномерными и двухмерными структурами. Для выбора необходимого элемента указываются имя массива данных и порядковый номер элемента (при одномерном массиве) либо номера строки и столбца, на пересече­нии которых находится элемент (при двухмерном массиве). Выполняя програм­му, ЭВМ сама вычисляет фактический адрес заданного элемента.

Адрес - некоторое число, которое может храниться, как и любое другое чис­ло, в ячейке памяти ЭВМ. Ячейку с адресом принято называть указателем. Фак­тически это ссылки на место расположения данных в памяти ЭВМ.

Количество данных и размерность соответствующих массивов могут меняться в ходе решения задачи. При этом возможно, что данные приходится размещать блоками в разных местах памяти ЭВМ. Тогда для указания их адре­сов используется система указателей (рис. 5.3). Указатель (ячейка) с адресом следующего блока обычно размещается в конце предыдущего блока данных. На рис. 5.3 адреса начала блоков обозначены символами А,, А₂, А₃. Указатель конца данных обычно представляет собой особое число, которое не может быть адресом (например, число «-!»).

Ячейки памяти

Рис. 53. Использование указателей для хранения данных

260

Адресация при хранении древовидных структур данных

Используемая система указателей существенно зависит от того, какую надо организовать модель представления данных в памяти ЭВМ. Очень часто информация о предметной области представляется в виде древовидной структуры, которой часто описывают, например, линейные системы управле­ния, схемы поиска неисправностей, различные классификаторы и др. Древовид­ные структуры представления информации - главная особенность иерархичес­ких баз данных.

Древовидная структура имеет вид направленного графа, вершинам которо­го сопоставляется некоторый объект (или список объектов), а связям - отношения между объекта­ми. Один из графов древовидной структуры при­веден на рис. 5.4. Он может описывать, например, структуру управления некоторого предприятия: А - р /ководитель; В и D - заместители руководи­теля по направлениям; С, Е и F - функциональные отделы, подчиненные заместителям.

Вершина, с которой начинается дерево, называется корневой, или корнем дерева. Каждая вершина, включая корневую, порождает ряд вершин, которые располагают ниже. С другими вершинами каждая из них может иметь несколько связей (ветвей) . Порожденные вершины называют дочерними вершинами, или потомками. Порождающая вершина называется родительской, или предком. В древовидной структуре каждая дочерняя вершина непосредственно соединена только с одной родительской. На рис. 5.4 родительская вершина В имеет одну дочернюю - С, а родительская вершина D имеет две дочерние - Е и F.

Ячейки с общим	Адрес описания		Адрес описания
описанием объекта	дочерней вершины 1		дочерней вершины N

Рис. 5.5. Структура машинного описания вершины дерева

В памяти ЭВМ вершину древовидной структуры можно представить из N+1 компонент, где N - число дочерних вершин (рис. 5.5). Первая компонента обычно представляет собой группу ячеек памяти с общим описа­нием объекта,

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

Организацию данных в памяти ЭВМ для дерева на рис. 5.4 иллюстрирует рис. 5.6. В рассматриваемом примере предполагается, что каждая вершина может иметь не более двух дочерних вершин. Поэтому в конце данных, описывающих объект, сопоставленный вершине, имеются две ячейки - указатели мест описа­ний дочерних вершин. Адрес для данных i-й вершины обозначен как А₍. Если дочерних вершин нет или имеется только одна, то значения свободных указате­лей принимаются равными «О».

261

Указатель корневой вершины данных

Следует иметь в виду, что для хранения числа, как правило, отводится слово ЭВМ, состоящее из нескольких байт (обычно 2 или 4). Это надо учитывать при вычислении адресов расположения данных.

Применение указателей - очень распространенный прием при обработке данных на ЭВМ. Возможны системы указателей, при которых задается как нача­ло, так и конец блока данных; место самих указателей может изменяться в про­цессе обработки и т.д.