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

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

Данные во внешней памяти хранятся в виде файлов.

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

Рассмотрим магнитный диск. С диска читается (записывается) не один символ (байт), а сектор или блок данных размером обычно 512 байт. Время доступа к гибкому диску (FDD) - 200-500 мс, к жесткому (HDD) - до 10-12 мс. Размер сектора оговорен конструкцией диска и не зависит от проектировщика системы. Обмен дисковой памяти с оперативной происходит только целыми секторами. Поэтому оптимальные длины записей, при которых достигается минимальное время обмена, должны быть кратными длине сектора. Правда, выигрыш по сравнению с записями, пересекающими границу сектора, составляет всего 2-5%.

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

Во внешней памяти несколько смежных секторов (обычно 2 или 4, а вообще - до 16) образуют кластер. При создании файла ему отводится один кластер. Если информациявыходит за пределы кластера, файлу отводится новый кластер из числа свободных на диске. Он может быть несмежным с первым и связывается с ним в цепочку. Длина цепочки ограничивается только наличием свободных кластеров.

На диске выделяется место под таблицу размещения файлов (FAT - File Allocation Table), остальное пространство диска используется для размещения файлов. В таблице хранятся описания файлов и соответствующие им списки (цепочки) кластеров.

Доступ к файлу начинается с обращения к FAT и поиска имени файла, при успешном поиске становятся доступны кластеры файла в области размещения файлов. При записи на диск нового файла в FAT предоставляется очередная свободная строка, а в области размещения файлов - очередные свободные кластеры.

При удалении файла первый символ имени файла в FAT заменяется служебным символом (обычно знаком вопроса). В результате имя файла и занимаемые им кластеры становятся недоступными, однако содержимое кластера не уничтожается, пока на диск не записываются новые данные (в последнем случае возможна потеря содержимого этих кластеров). Это дает возможность восстановить файл (например, утилитой UNERASE из пакета Norton Utilites). Новый файл может занимать кластеры в разных местах диска (не сплошной участок) - фрагментация (сегментация) файла, что может привести к существенному замедлению работы с диском. Этот эффект можно устранить, выполнив дефрагментацию файлов на диске, например, утилитой SPEEDISK из того же пакета утилит.

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

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

2. Индексно-последовательный файл. Это последовательный файл, снабженный индексами. На диске для него выделяется три области:

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

б) индексная; в зависимости от размера первичной области могут создаваться один, два или три уровня индексов. Индекс первого уровня отмечает последовательную запись каждой дорожки диска. Индекс второго уровня - последнюю запись каждого цилиндра диска. Третий уровень используется, если файл индекса 2 уровня достаточно велик.

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

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

3. Индексно-произвольный файл. В индекс помещается информацияо ключе каждой записи. Записи файла при этом могут быть не упорядочены. Индекс формируется практически всегда как многоуровневый. Типичная организация соответствует понятию В-дерева. Нижний уровень образуют индексы со ссылкой на каждую запись основного массива, они разделены на страницы, и в конце каждой страницы оставляется резервная память. Последний индекс каждой страницы поступает на страницу предыдущего уровня В-дерева и т.д.

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

Рис. 18. В-дерево

Достоинство В-дерева - его простое расширение. При переполнении у какой-либо страницы половины ее содержимого индекс переходит в новую страницу, а на вышестоящем уровне появляется новый индекс.

4. Файл прямого доступа. Особенности прямого доступа: не требуется упорядоченность записей файла; наличие повторяющихся значений ключа недопустимо; значениям нескольких ключей может соответствовать один и тот же адрес. Прямой метод доступа обеспечивается многими языками программирования.

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

Вопросы для самоконтроля:

1. Какие информационные системы называются фактографическими?

2. В чем заключаются особенности фактографических информационных систем?

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

4. Дайте определение предметной области фактографических информационных систем?

5. Дайте определение понятиям «сущность», «связь».

6. Объясните содержание концептуальной модели фактографических информационных систем.

7. Изобразите графически основные модели данных фактографических информационных систем?

8. Как организовано хранение д анных во внешней памяти?

9. Как осуществляется обмен дисковой памяти с оперативной памятью.

10. Какие существуют методы доступа к файлам.

Дата добавления: 2014-01-20