Объединение записей в блоки и буферизация

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

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

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

 

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

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

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

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

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

Управление файлами

5.4.1. Понятие файлового способа хранения данных
и файловой системы

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

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

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

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

Файловая система – система управления данными с файловым способом хранения.

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

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

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

- каждый пользователь может иметь контролируемый доступ к файлам других пользователей;

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

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

- каждый пользователь должен иметь возможность пересылать данные между файлами;

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

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

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

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

- средства реализации методов доступа к файлу и к его составным элементам;

- средства распределения внешней памяти для хранения файлов, а также ее освобождения по мере уничтожения файлов;

- средства учета расположения файлов и их составных элементов.

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

 

 

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

Организация файлов

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

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

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

Последовательная организация файла предполагает создание на диске последовательного файла.

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

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

 

 

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

- один физический блок под одну логическую запись;

- несколько физических блоков под одну логическую запись;

- один физический блок под несколько логических записей.

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

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

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

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

Непрерывная организация файла предполагает создание на диске непрерывного файла.

Непрерывный файл – файл на носителе, состоящий из ряда физических блоков, которые все расположены в одной сплошной области дискового пространства.

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

Доступ к записям непрерывного файла достаточно прост. Если обозначить через r – номер записи, l – длину записи и L – длину блока, то номер b блока, где находится запись, вычисляется по формуле

b=l*r/L.

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

Обновление записи r совершается очень просто – она просто перекрывается новыми данными. При этом происходит обращение к нужному количеству физических блоков.

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

Сегментированная организация файла предполагает создание сегментированного файла.

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

Сегментированный файл называют также индексным файлом.

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

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

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

Организация хранения файлов

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

Каталог (Catalog) – справочник файлов и каталогов с ссылками на их расположение.

Справочник (Directory) – таблица идентификаторов и ссылок к соответствующим элементам данных.

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

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

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

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

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

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

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

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

Для эффективного управления файлами требуется также несколько блоков структурированных данных, главным из которых является блок управления файлом (БУФ), называемый также дескриптором файла.

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

Операции над файлами

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

Общие операции над файлами можно разделить на три группы:

- операции над файлами как над единым целым;

- операции для обмена данными между файлом и программой, инициирующей обмен;

- служебные операции.

К первой группе относятся следующие файловые операции: открытие файла; закрытие файла; копирование файла; объединение файлов; перемещение файла; удаление файла.

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

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

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

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

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

Ко второй группе относятся следующие операции над файлами: чтение составных элементов файла; запись составных элементов файла.

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

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

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

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

Файловая система