Информатика и программное обеспечение ПЭВМ (стр. 15 из 48)

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

Физический уровень хранения означает реализацию хранения информации на конкретных физических носителях.

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

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

Маркер (mark, marker) – метка на носителе информации, обозначающая начало или конец данных либо их части (блока).

В современных носителях информации используются маркеры:

- адреса (адресный маркер) – код или физическая метка на дорожке диска, указывающие на начало адреса сектора;

- группы – маркер, указывающий начало или конец группы данных;

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

- конца файла – метка, используемая для указания окончания считывания последней записи файла;

- ленты (ленточный маркер) – управляющая запись или физическая метка на магнитной ленте, обозначающая признак начала или конца блока данных или файла;

- сегмента – специальная метка, записываемая на магнитной ленте для отделения одного сегмента набора данных от другого.

Хранение информации в ЭВМ связано с процессом ее арифметической обработки и с принципами организации информационных массивов, поиска, обновления, представления информации и др.

Важным этапом автоматизированного этапа хранения является организация информационных массивов.

Массив (от англ. array) – упорядоченное множество данных.

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

С учетом этого рассматриваются следующие структуры организации информационных массивов: линейная, многомерная.

В свою очередь, линейная структура данных делится на строки, одномерные массивы, стеки, очереди, деки и др.

Строка – это представление данных в виде элементов, располагающихся по признаку непосредственного следования, т. е. по мере поступления данных в ЭВМ.

Одномерный массив – это представление данных, отдельные элементы которых имеют индексы, т. е. поставленные им в соответствие целые числа, рассматриваемые как номер элемента массива.

Индекс обеспечивает поиск и идентификацию элементов, а следовательно, и доступ к заданному элементу, что облегчает его поиск по сравнению с поиском в строке.

Идентификация – процесс отождествления объекта с одним из известных объектов.

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

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

Дека – структура организации данных, одновременно сочетающая рассмотренные виды.

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

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

Массивы по своей структуре близки к файлам и отличаются от последних двумя основными признаками:

- каждый элемент массива может быть явно обозначен, и к нему имеется прямой доступ;

- число элементов массива определяется при его описании.

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

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

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

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

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

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

Список включает имя и адрес поля данных. В памяти ЭВМ элементы списка физически разнесены, но связаны друг с другом логически за счет адресных ссылок.

Поле данных в зависимости от характера хранимой информации может быть выражено двоичным разрядом, словом фиксированной либо переменной длины, а также набором отдельных слов.

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

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

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

Рассмотренные списковые структуры информационных массивов имеют следующие особенности:

- высокую логическую простоту;

- относительно большое количество времени доступа, обусловленное адресным обращением к данным, при котором к каждому элементу списка необходимо иметь ссылку;

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

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

Рис. 1.17. Способы организации массивов информации в запоминающем устройстве ЭВТ

На физическом уровне любые записи информационного поля представляют в виде двоичных символов. Обращение к памяти большого объема требует большой длины адреса. Если память имеет емкость 2n слов, то для поиска таких слов потребуются n-разрядные адреса. В микропроцессорах восьмиразрядные слова дают возможность обращаться к 256 ячейкам памяти, что оказывается недостаточно для хранения информации в автоматизированных системах. Если непосредственно обращение к любой ячейке невозможно, переходят к страничной организации памяти.

В этом случае выбирают область памяти емкостью 2n слов и называют страницей, обращение к которой осуществляется командой, содержащей n-разрядное адресное поле. В микропроцессорах обычно используют страницы размером 256 слов.

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

С хранением информации связаны следующие понятия: носитель информации (память), внутренняя память, внешняя память, хранилище информации.