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

Обновлено: 07.07.2024

Длина имени файла зависит от ОС, может быть от 8 (MS-DOS) до 255 (Windows, LINUX) символов.

ОС могут различать прописные и строчные символы. Например, WINDOWS и windows для MS-DOS одно и тоже, но для UNIX это разные файлы.

Во многих ОС имя файла состоит из двух частей, разделенных точкой, например windows.exe. Часть после точки называют расширением файла. По нему система различает тип файла.

У MS-DOS расширение составляет 3 символа. По нему система различает тип файла, а также можно его исполнять или нет.

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

2.1.2 Структура файла

Три основные структуры файлов:

Последовательность байтов - ОС не интересуется содержимым файла, она видит только байты. Основное преимущество такой системы, это гибкость использования. Используются в Windows и UNIX.

Последовательность записей - записей фиксированной длины (например, перфокарта), считываются последовательно. Сейчас не используются.

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

Три типа структур файла.

2.1.3 Типы файлов

Основные типы файлов:

Регулярные - содержат информацию пользователя. Используются в Windows и UNIX.

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

Символьные - для моделирования ввода-вывода. Используются только в UNIX.

Блочные - для моделирования дисков. Используются только в UNIX.

Основные типы регулярных файлов:

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

Двоичные файлы - остальные файлы (не ASCII). Как правило, имеют внутреннею структуру.

Основные типы двоичных файлов:

Исполняемые - программы, их может обрабатывать сама операционная система, хотя они записаны в виде последовательности байт.

Неисполняемые - все остальные.

Примеры исполняемого и не исполняемого файла

«Магическое число» - идентифицирующее файл как исполняющий.

2.1.4 Доступ к файлам

Основные виды доступа к файлам:

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

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

2.1.5 Атрибуты файла

Основные атрибуты файла:

Защита - кто, и каким образом может получить доступ к файлу (пользователи, группы, чтение/запись). Используются в Windows и UNIX.

Пароль - пароль к файлу

Создатель - кто создал файл

Владелец - текущий владелец файла

Флаг "только чтение" - 0 - для чтения/записи, 1 - только для чтения. Используются в Windows.

Флаг "скрытый" - 0 - виден, 1 - невиден в перечне файлов каталога (по умолчанию). Используются в Windows.

Флаг "системный" - 0 - нормальный, 1 - системный. Используются в Windows.

Флаг "архивный" - готов или нет для архивации (не путать сжатием). Используются в Windows.

Флаг "сжатый" - файл сжимается (подобие zip архивов). Используются в Windows.

Флаг "шифрованный" - используется алгоритм шифрования. Если кто-то попытается прочесть файл, не имеющий на это прав, он не сможет его прочесть. Используются в Windows.

Флаг ASCII/двоичный - 0 - ASCII, 1 - двоичный

Флаг произвольного доступа - 0 - только последовательный, 1 - произвольный доступ

Флаг "временный" - 0 - нормальный, 1 - для удаления файла по окончании работы процесса

Флаг блокировки - блокировка доступа к файлу. Если он занят для редактирования.

Время создания - дата и время создания. Используются UNIX.

Время последнего доступа - дата и время последнего доступа

Время последнего изменения - дата и время последнего изменения. Используются в Windows и UNIX.

Текущий размер - размер файла. Используются в Windows и UNIX.

2.1.6 Операции с файлами

Основные системные вызовы для работы с файлами:

Create - создание файла без данных.

Delete - удаление файла.

Open - открытие файла.

Close - закрытие файла.

Read - чтение из файла, с текущей позиции файла.

Write - запись в файл, в текущею позицию файла.

Append - добавление в конец файла.

Seek - устанавливает файловый указатель в определенную позицию в файле.

Get attributes - получение атрибутов файла.

Set attributes - установить атрибутов файла.

Rename - переименование файла.

2.1.7 Файлы, отображаемые на адресное пространство памяти

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

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

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

Пример копирования файла через отображение в памяти.

Создается сегмент для файла 1

Файл отображается в памяти

Создается сегмент для файла 2

Сегмент 1 копируется в сегмент 2

Сегмент 2 сохраняется на диске

Недостатки этого метода:

Тяжело определить длину выходного файла

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

Файл может оказаться большим, больше сегмента или виртуального пространства.

2.2 Каталоги

2.2.1 Одноуровневые каталоговые системы

В этой системе все файлы содержатся в одном каталоге.

Однокаталоговая система, содержащая четыре файла, файлов А два, но разных владельцев

Возможность быстро найти файл, не надо лазить по каталогам

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

2.2.2 Двухуровневые каталоговые системы

Для каждого пользователя создается свой собственный каталог.

Двухуровневая каталоговая система

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

Эту проблему можно решить созданием системного каталога, с общим доступом.

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

2.2.3 Иерархические каталоговые системы

Каждый пользователь может создавать столько каталогов, сколько ему нужно.

Иерархическая каталоговая система

Почти все современные универсальные ОС, организованы таким образом. Специализированным ОС это может быть не нужным.

2.2.4 Имя пути

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

Два основных метода указания файла:

абсолютное имя пути - указывает путь от корневого каталога, например:
- для Windows \usr\ast\mailbox
- для UNIX /usr/ast/mailbox
- для MULTICS >usr>ast>mailbox

относительное имя пути - путь указывается от текущего каталога (рабочего каталога), например:
- если текущий каталог /usr/, то абсолютный путь /usr/ast/mailbox перепишется в ast/mailbox
- если текущий каталог /usr/ast/, то абсолютный путь /usr/ast/mailbox перепишется в mailbox
- если текущий каталог /var/log/, то абсолютный путь /usr/ast/mailbox перепишется в ../../usr/ast/mailbox

./ - означает текущий каталог

../ - означает родительский каталог

2.2.5 Операции с каталогами

Основные системные вызовы для работы с каталогами:

Create - создать каталог

Delete - удалить каталог

OpenDir - закрыть каталог

CloseDir - закрыть каталог

ReadDir - прочитать следующий элемент открытого каталога

Rename - переименование каталога

Link - создание жесткой ссылки, позволяет файлу присутствовать сразу в нескольких каталогах.

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

Суть проблемы

Я уверен, на компьютере каждого человека, читающего этот топик, наверняка есть хоть один из следующих каталогов: soft, разобрать, временно, всякая всячина, trash, интересное. Обычно в папке софт находится несколько тысяч архивов и экзешников с говорящими названиями «setup.exe» или «589346.zip»; папка «Мои документы» засрана кучей файлов, многие из которых вообще к документам не относятся, а файлы из каталога «Разобрать» так и остаются не разобранными…
При этом, когда у нас возникает потребность отыскать «тот самый дистрибутив visual studio, который я скачивал пару месяцев назад», то гораздо проще за несколько секунд найти ссылку на установщик в гугле, чем долго и тщетно пытаться искать его на своем компьютере. Стандартные утилиты поиска так же не спасают, т.к. для бинарных файлов они могут ориентироваться только на название файла, да жалкую горстку дополнительных атрибутов.

Хочу заметить, что данная проблема в юзабилити файловых систем вовсе не является надуманной: достаточно вглянуть на этот топик, вызвавший достаточно бурное обсуждение.
Также можно ознакомиться с соответствующей главой из книги «Алан Купер об интерфейсе. Основы проектирования взаимодействия».

Варианты решения

Хорошо, но если такую простую и удобную идею до сих пор не внедрили производители операционных систем, то куда же смотрят разработчики сторонних приложений?!
Я полагал, что существует как минимум несколько альтернатив, позволяющих создавать базу данных, на основе тегирования файлов, ведь это так просто для реализации!
К моему разочарованию я обнаружил, что подсуетились лишь программисты под Mac OS: 7 File Tagging Applications for OS X (разумеется, почти все они платные).
Ни для windows, и, тем более, ни для Linux ничего подобного я не нашел. Хотя, возможно, я просто плохо искал — в таком случае очень прошу указать в комментариях ссылки на такой софт.

Добавление/редактирование тегов к файлам и папкам прямо из контекстного меню файлового менеджера (Nautilus)
Интерфейс для поиска и просмотра файлов по указанным тегам
Отслеживание изменений в именах и расположении (что, в общем, одно и то же) файлов

Существующие средства

Решив прощупать почву для первого этапа, т.е. добавление своих элементов в контекстное меню программы Nautilus, я наткнулся на один open-source проект, который частично реализует мою идею — это "tags-tabs extension".
Честно говоря, слово «проект» слабо подходит для одного полуработающего .py исходника на 7 кб, и не имеющего никакой документации.
tags-tabs — это расширение для Nautilus, использующее библиотеку «python-nautilus». Оно добавляет в контекстное меню свой пункт, что позволяет назначать файлам теги и выполнять базовый поиск.
В теории, чтобы все заработало, необходимо поместить этот файл в директории

/.nautilus/extensions/python и дать ему права на исполнение. На практике, в моей Ubuntu 8.10 этот скрипт вызывает крэш приложения, при вызове меню. Говорят, что в ранних версиях убунты все работает нормально.

Также нельзя не упомянуть замечательный проект dhtfs.
DHTFS также проповедует идеологию ФС, основанной на тегах, написан на python и имеет даже краткую пользовательскую документацию! Но есть один минус — это cli-приложение.

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

Создание двоичных файлов с помощью функции fopen отличается от создания текстовых файлов только указанием режима обмена – "rb" (двоичный для чтения), "rb+" (двоичный для чтения и записи), "wb" (двоичный для записи), "wb+" (двоичный для записи и чтения):

Обычно для обмена с двоичными файлами используются функции fread и fwrite :

buf – указатель типа void* на начало буфера в оперативной памяти, из которого информация переписывается в файл;
size_rec – размер передаваемой порции в байтах;
n_rec – количество порций, которое должно быть записано в файл;
f1 – указатель на блок управления файлом;
c_w – количество порций, которое фактически записалось в файл.

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

c_r – количество порций, которое фактически прочиталось из файла;
buf – указатель типа void* на начало буфера в оперативной памяти, в который информация считывается из файла.

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

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

f1 – указатель на блок управления файлом;
delta – величина смещения в байтах, на которую следует переместить указатель файла;
pos – позиция, от которой производится смещение указателя (0 или SEEK_SET – от начала файла, 1 или SEEK_CUR – от текущей позиции, 2 или SEEK_END – от конца файла)

Кроме набора функций fopen /fclose, fread /fwrite > для работы с двоичными файлами в библиотеке BC предусмотрены и другие средства – _dos_open /__dos_close, _dos_read /_dos_write, _create /_close, _read /_write . Однако знакомство со всеми возможностями этой библиотеки в рамках настоящего курса не предусмотрено.

Пример 2. Рассмотрим программу, которая создает двоичный файл для записи с именем c_bin и записывает в него 4*10 порций данных в машинном формате (строки, целые и вещественные числа). После записи данных файл закрывается и вновь открывается для чтения. Для демонстрации прямого доступа к данным информация из файла считывается в обратном порядке – с конца. Контроль записываемой и считываемой информации обеспечивается дублированием данных на экране дисплея.

Использованные в этом примере операторы:

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

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

10.1.3. Структурированные файлы

Структурированный файл является частным случаем двоичного файла, в котором в качестве порции обмена выступает структура языка C, являющаяся точным аналогом записи в Паскале. По сравнению с предыдущим примером использование записей позволяет сократить количество обращений к функциям fread /fwrite , т.к. в одном обращении участвуют все поля записи.

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

Пример 3. Приведенная ниже программа является модификацией предыдущего примера. Единственное ее отличие состоит в использовании структуры (записи) b , состоящей из символьного ( b.s , 5 байт, включая нулевой байт – признак конца строки), целочисленного ( b.n , 2 байта в BC и 4 байта в BCB) и вещественного ( b.r , 4 байта) полей.

Результат работы этой программы ничем не отличается от предыдущего примера.

Модуль 8. Управление данными

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

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

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

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

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

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

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

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

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

Индексно-последовательный.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также: