Способы доступа и организации файлов. Распределение файлов на диске
Способы доступа и организации файлов С точки зрения внутренней структуры (логической организации) файл - это совокупность одно-типных записей, каждая из которых информирует о свойствах одного объекта. Записи могут быть фиксированной длины, переменной длины или неопределенной длины. Записи переменной длины в своем составе содержат длину записи, а неопределенной длины – специальный символ конца записи. При этом каждая запись может иметь идентификатор, представляющий собой ключ, который может быть сложным и состоять из нескольких полей. Существует три способа доступа к данным, расположенным во внешней памяти: 1. Физически последовательный по порядку размещения записи в файле. 2. Логически последовательный в соответствии с упорядочением по значению ключей. Для выполнения упорядочения создается специальный индексный файл, в соответствии с которым записи представляются для обработки. 3. Прямой - непосредственно по ключу или физическому адресу записи. Для организации доступа записи должны быть определенным образом расположены и взаимо-связаны во внешней памяти. Есть несколько способов логической организации памяти. Последовательный Записи располагаются в физическом порядке и обеспечивают доступ в физической последова-тельности. Таким образом, для обработки записи с номером N+1 необходимо последовательно обра-титься к записям с номером 1, 2,….,N. Это универсальный способ организации файла периферийного устройства. Используется так же для организации входного/выходного потока. Индексно-последовательный. Записи располагаются в логической последовательности в соответствии со значением ключей записи. Физически записи располагаются в различных местах файла. Логическая последовательность файла фиксируется в специальной таблице индексов, в которой значение ключей связывается с физи-ческим адресом записи. При такой организации доступ к записям осуществляется логически последо-вательно в порядке возрастания или убывания значения ключа или по значению ключа. Индексный Место записи в файле, ее физический адрес, определяется алгоритмом преобразования для клю-ча. Доступ к записям возможен только прямой. Алгоритм преобразования ключа называется хеширо-ванием. Ключ, использующий алгоритм хеширования, преобразуется в номер записи. Прямой. Это организация, при которой осуществляется прямой доступ по порядковому номеру записи или по физическому адресу. Библиотечный Организация, в которой файл состоит из последовательных подфайлов (разделов), первый из которых является оглавлением и содержит имена и адреса остальных подфайлов. При такой организации осуществляется комбинированныйдоступ: индексный прямой к разделу и последовательный в разделах. Определить права доступа к файлу - значит определить для каждого пользователя набор опера-ций, которые он может применить к данному файлу. В разных файловых системах может быть опре-делен свой список дифференцируемых операций доступа. Этот список может включать следующие операции: • создание файла; • уничтожение файла; • открытие файла; • закрытие файла; • чтение файла; • запись в файл; • дополнение файла; • поиск в файле; • получение атрибутов файла; • установление новых значений атрибутов; • переименование; • выполнение файла; • чтение каталога; • и другие операции с файлами и каталогами. В самом общем случае права доступа могут быть описаны матрицей прав доступа, в которой столбцы соответствуют всем файлам системы, строки - всем пользователям, а на пересечении строк и столбцов указываются разрешенные операции. В некоторых системах пользователи могут быть раз-делены на отдельные категории. Для всех пользователей одной категории определяются единые права доступа. Например, в системе UNIX все пользователи подразделяются на три категории: владельца файла, членов его группы и всех остальных. Различают два основных подхода к определению прав доступа: • избирательный доступ, когда для каждого файла и каждого пользователя сам владелец может определить допустимые операции; • мандатный подход, когда система наделяет пользователя определенными правами по отношению к каждому разделяемому ресурсу (в данном случае файлу) в зависимости от того, к какой группе пользователь отнесен. Управление внешней памятью Физически том дисковой памяти - это отдельный носитель внешней памяти, представляющий собой совокупность блоков данных. Блок - это единица физической передачи данных (единица обме-на данных с устройством). Запись - это единица ввода/вывода программы. Блок может содержать не-сколько логических записей, что минимизирует число операций ввода/вывода (рис.1).
Рисунок 1. Коэффициент блокирования 7 Физически файл - это совокупность выделенных блоков памяти (область внешней памяти). Су-ществует два вида организации накопителей на магнитном диске: 1.Трековый, в котором весь диск подразделяется на треки (дорожки) фиксированной длины, на которых размещаются блоки переменного размера. Адресом блока является тройка: • номер цилиндра; • номер трека; • номер блока. Единицей выделения памяти является трек или цилиндр. Цилиндр представляет собой область памяти, образованную всеми дорожками, доступными на магнитных поверхностях без перемещения магнитных головок. 2.Секторный, в котором диск разбивается на блоки фиксированного размера, обычно кратного 256 байтам. Адресом блока является его порядковый номер на носителе. Работа с дисковой памятью включает в себя 4 основные процедуры: 1. Инициализация тома (форматирование). 2. Выделение и освобождение памяти файлу. 3. Уплотнение внешней памяти (дефрагментация). 4. Копирование, восстановление томов для обеспечения целостности. Инициализация тома состоит из: • форматирования диска на дорожки (сектора); • определения сбойных участков диска; • присвоения метки тому; • создания оглавления тома; • записи ОС, если это необходимо. Способы распределения памяти на диске Выделение и освобождение места для файлов на томе аналогично стратегии размещения ОП. 1. Непрерывное распределение памяти, когда файлу выделяется непрерывный участок па-мяти. Для задания адреса файла в этом случае достаточно указать только номер началь-ного блока. Достоинство этого метода - простота. Очевидный недостаток - проблема расширения файла и фрагментация. Уплотнение или дефрагментация используется для восстановления памяти. 2. Секторное или блочное распределение, когда файлу выделяется логически связанные блоки, физически размещенные в любом месте. При таком способе в начале каждого блока содержится указатель на следующий блок. В этом случае адрес файла также мо-жет быть задан одним числом - номером первого блока. В отличие от предыдущего способа, каждый блок может быть присоединен в цепочку какого-либо файла и, следо-вательно, фрагментация отсутствует. Файл может изменяться во время своего сущест-вования, наращивая число блоков. Недостатком является сложность реализации досту-па к произвольно заданному месту файла: для того чтобы прочитать пятый по порядку блок файла, необходимо последовательно прочитать четыре первых блока, прослеживая цепочку номеров блоков. Популярным способом, используемым, например, в файловой системе 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. В некоторых файловых системах запросы к внешним устройствам, в которых адресация осуще-ствляется блоками (диски, ленты), перехватываются промежуточным программным слоем-подсистемой буферизации. Подсистема буферизации представляет собой буферный пул, распола-гающийся в оперативной памяти, и комплекс программ, управляющих этим пулом и позволяющий выполнять опережающее считывание блоков файла при последовательном доступе. Каждый буфер пула имеет размер, равный одному блоку. При поступлении запроса на чтение некоторого блока под-система буферизации просматривает свой буферный пул и, если находит требуемый блок, то копиру-ет его в буфер запрашивающего процесса. Операция ввода-вывода считается выполненной, хотя фи-зического обмена с устройством не происходило. Очевиден выигрыш во времени доступа к файлу. Если же нужный блок в буферном пуле отсутствует, то он считывается с устройства и одновременно с передачей запрашивающему процессу копируется в один из буферов подсистемы буферизации. При отсутствии свободного буфера на диск вытесняется наименее используемая информация. Таким образом, подсистема буферизации работает по принципу кэш-памяти. Кроме того, буферизация позволяет одновременно обрабатывать программой текущий блок и читать/писать в другие буфера следующий блок.
