Модель внешних вычислений

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

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

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: