Какие фундаментальные способы организации файлов вы знаете

Тема 15. Способы доступа и организации файлов. Распределение файлов на диске

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

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

Существует три способа доступа к данным, расположенным во внешней памяти:

Физически последовательный по порядку размещения записи в файле.

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

Прямой — непосредственно по ключу или физическому адресу записи.

Для организации доступа записи должны быть определенным образом расположены и взаимосвязаны во внешней памяти. Есть несколько способов логической организации памяти.

Записи располагаются в физическом порядке и обеспечивают доступ в физической последовательности. Таким образом, для обработки записи с номером N+1 необходимо последовательно обратиться к записям с номером 1, 2,….,N. Это универсальный способ организации файла периферийного устройства. Используется так же для организации входного/выходного потока.

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

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

Это организация, при которой осуществляется прямой доступ по порядковому номеру записи или по физическому адресу.

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

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

создание файла;

уничтожение файла;

открытие файла;

закрытие файла;

чтение файла;

запись в файл;

дополнение файла;

поиск в файле;

получение атрибутов файла;

установление новых значений атрибутов;

переименование;

выполнение файла;

чтение каталога;

и другие операции с файлами и каталогами.

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

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

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

Физически том дисковой памяти — это отдельный носитель внешней памяти, представляющий собой совокупность блоков данных. Блок — это единица физической передачи данных (единица обмена данных с устройством). Запись — это единица ввода/вывода программы. Блок может содержать несколько логических записей, что минимизирует число операций ввода/вывода (рис.1).

Рисунок 1. Коэффициент блокирования 7

Физически файл — это совокупность выделенных блоков памяти (область внешней памяти). Существует два вида организации накопителей на магнитном диске:

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

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

2.Секторный, в котором диск разбивается на блоки фиксированного размера, обычно кратного 256 байтам. Адресом блока является его порядковый номер на носителе.

Работа с дисковой памятью включает в себя 4 основные процедуры:

Инициализация тома (форматирование).

Выделение и освобождение памяти файлу.

Уплотнение внешней памяти (дефрагментация).

Копирование, восстановление томов для обеспечения целостности.

форматирования диска на дорожки (сектора);

определения сбойных участков диска;

присвоения метки тому;

создания оглавления тома;

записи ОС, если это необходимо.

Выделение и освобождение места для файлов на томе аналогично стратегии размещения ОП.

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

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

Популярным способом, используемым, например, в файловой системе FAT операционной системы MS-DOS, является использование связанного списка индексов. С каждым блоком (кластером) связывается некоторый элемент — индекс. Индексы располагаются в отдельной области диска (в MS-DOS это таблица FAT). Если некоторый блок распределен файлу, то индекс этого блока содержит номер следующего блока данного файла. При этом для каждого файла в каталоге имеется поле, в котором отмечается номер начального индекса для кластера, входящего в файл. Последний индекс содержит специальный маркер конца файла. Такая физическая организация сохраняет все достоинства предыдущего способа и снимает отмеченный недостаток: для доступа к произвольному месту файла достаточно прочитать только блок индексов, отсчитать нужное количество блоков файла по цепочке и определить номер нужного блока.

В заключение рассмотрим задание физического расположения файла путем простого перечисления номеров блоков, занимаемых этим файлом. ОС UNIX использует вариант данного способа, позволяющий обеспечить фиксированную длину адреса независимо от размера файла. Для хранения адреса файла выделено 13 полей. Если размер файла меньше или равен 10 блокам, то номера этих блоков непосредственно перечислены в первых десяти полях адреса. Если размер файла больше 10 блоков, то следующее, 11-е поле содержит адрес блока, в котором могут быть расположены еще 128 номеров следующих блоков файла. Если файл больше, чем 10+128 блоков, то используется 12-е поле, в котором находится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номеров блоков данного файла. И, наконец, если файл больше 10+128+128(128, то используется последнее, 13-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего размер максимум: 10+ 128 + 128(128 + 128(128(128.

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

Источник

Способы организации файлов

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

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

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

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

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

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

Относительный уровень приоритета этих критериев зависит от приложений, которые будут работать с файлом. Например, если файл предназначен только для обработки в пакетном режиме, когда одновременно выбираются несколько записей, быстрый доступ для выборки одной записи заинтересует нас менее всего. Файл, сохраненный на CD-ROM, никогда не будет обновлен, поэтому вопрос легкости в обновлении не имеет смысла.

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

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

— Файл прямого доступа (хешированный).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник