РЕАЛИЗАЦИЯ ФАЙЛОВОЙ СИСТЕМЫ С ДИНАМИЧЕСКИМ РАСПОЛОЖЕНИЕМ ТАБЛИЦЫ РАЗМЕЩЕНИЙ ФАЙЛОВ

Всероссийский форум научной молодежи «Шаг в будущее»

РЕАЛИЗАЦИЯ ФАЙЛОВОЙ СИСТЕМЫ С ДИНАМИЧЕСКИМ РАСПОЛОЖЕНИЕМ ТАБЛИЦЫ РАЗМЕЩЕНИЙ ФАЙЛОВ

Россия, Самарская область, город Самара

Автор  Чернышев Владислав Анатольевич

МАОУ Самарский медико-технический лицей, 11 класс

Научный руководитель Сметанников Андрей Леонидович,

кандидат педагогических наук,  учитель информатики  

МАОУ Самарский медико-технический лицей

2014г.

Введение.

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

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

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

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

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

Задачи:

-Анализ существующих файловых систем.

-Выбор технических средств реализации проекта.

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

-Реализовать приложение, позволяющее работать с данной файловой системой.

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

Новизна работы.

В ходе исследования реализована модель файловой системы и разработано программное средство управления ей.

Практическая значимость.

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

Содержание работы по разделам.

1.Анализ современных файловых систем и выбор технических средств реализации.

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

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

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

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

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

Впоследствии был выбран язык С++, как язык, позволяющий писать приложения приемлемой скорости работы с приемлемыми временными затратами, в качестве среды программирования была определена Visual Studio, обеспечивающая комфортность и производительность работы. Функционал для работы с внешними устройствами на низком уровне предоставляла библиотека libusb-win32.

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

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

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

Можно выделить 3 различных этапа развития данного проекта.

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

Рисунок 2.1- структура сектора в разработанной файловой системе.

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

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

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

Рисунок 2.2- структура файловых записей в составе однонаправленного списка.

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

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

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

Сначала в теории, а затем и на практике в файловую систему была внедрена поддержка динамического размера кластера. Как известно, чем больше размер кластера, тем быстрее происходят файловые операкции, однако, тем меньше эффективность использования памяти устройства. Чем меньше размер кластера, тем меньше скорость файловых операций, однако, тем выше эффективность использования памяти. Идея использования динамического размера кластера позволяет совместить плюсы обоих вариантов, совершенно избавившись от их минусов. Также, на данном этапе файловой системе было дано название- RaCFiS (Random Cluster File System, файловая система с произвольным кластером).  

Рисунок 2.3- структура файловой системы второго этапа.

В структуре второго этапа можно выделить 3 области- список интервалов памяти (LoMI, list of memory intervals), список заголовков файлов, фрагменты данных файлов.

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

Рисунок 2.4- схема работы со списком интервалов памяти.

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

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

Рисунок 2.5- строение заголовка файла

В ходе второго этапа работы были выявлены следующие недостатки файловой системы:

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

-Максимальный размер имени в 256 символов является недостаточно большим.

-Использование списка интервалов памяти требует резервирования 1/64 объема памяти всего устройства, что является неприемлемо большим значением.

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

К третьему этапу работы структура файловой изменилась до неузнаваемости. В структуре было выделено 4 особые области- адреса заголовков файлов (FHA, Files headers addresses), список сортировки файлов (FSL, File sorting list), заголовки файлов (FH, Files headers), и, собственно, фрагменты данных файлов (Data).

Рисунок 2.6- строение файловой системы на третьем этапе

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

Рисунок 2.7- строение блоков FHA и FSL

Блок FSL также представляет собой набор блоков служебной информации (размер каждого блока- 64КБ), хранящий информацию о порядке возрастания имен файлов. Знать порядок сортировки необходимо для применения алгоритма бинарного поиска файла по имени.

Рисунок 2.8- схема работы с FSL

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

Рисунок 2.9- строение файлового заголовка

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

На данный момент, версия файловой системы третьего этапа является последней.

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

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

На данный момент успешно реализованы следующие функции:

-Функция открытия носителя.

-Функция форматирования носителя.

-Функция записи файлов на носитель.

-Функция чтения файлов с носителя.

-Функция переименования файлов.

-Функция удаления файлов.

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

Функция открытия. В начале происходит получения доступа к устройству. Программа, получив доступ к устройству, считывает основную информацию о нем. Затем- читает в оперативную память блоки FHA и FSL. Также в оперативной памяти создается вспомогательная структура, в которую номера файлов из FSL помещаются в порядке возрастания имен. Время выполнения данной операции и требования к оперативной памяти зависят от количества файлов, хранящихся на носителе. Что касается времени выполнения, то оно сопоставимо со временем чтения (n div 8191)*65536*2 байт за (n div 8191)*2 запросов, где n- количество файлов. Что касается памяти, то требования к ней сопоставимы с 32*n байт, где n-количество файлов.    

Функция форматирования. На устройство записываются пустые блоки FHA и FSL, каждый размером по 64КБ, а также информация о свободной памяти устройства, помещенная в заголовок системного файла. После выполнения этих операций устройство готово к работе. Время выполнения сопоставимо со временем записи 65536*2+512 байт за 3 запроса.

Функция записи файлов на носитель. Изначально, программа получает доступ к файлу для копирования и считывает необходимую информацию о нем. В случае, если размер файла свободной памяти больше размера файла для копирования, то происходит операция выделения памяти для заголовка файла- адрес первого фрагмента файла свободной памяти увеличивается на размер сектора в байтах (512 Б), или же становится равным адресу второго фрагмента. Затем необходимо произвести изменения в структурах FHA и FSL. В первую свободную ячейку FHA заносится адрес выделенной под заголовок памяти. Затем выполняется поиск (по алгоритму бинарного поиска) имени копируемого файла среди уже существующих файлов. Определяется положение файла в отсортированном списке, вносятся изменения в FSL. Формируется файловый заголовок. Если необходимо, выделяется память для длинного имени файла. Выделяется память для самого файла. Происходит чередующееся чтение данных из копируемого файла в буфер и запись данных буфера на носитель. Время выполнение данной функций складывается из двух основных операций- поиску места, которое данный файл должен занять в FSL (что происходит в лучшем случае за время чтения 512*log n байт за log n запросов, а в худшем- за чтение (512+65536)*log n байт за log n*2 запросов), а также времени записи данных файла на носитель (что в лучшем случае сопоставимо с временем записи n байт за n div 65536 запросов, а в худшем случае- с временем записи n байт за n div 512 запросов).    

Заключение.

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

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

Однако, на достигнутых результатах работа над проектом остановлена не была. В ближайшем времени планируется:

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

-Реализация возможности шифрования данных устройства с открытым ключом

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

-

Список использованных источников.

Интернет-ресурсы:

1. http://msdn.microsoft.com
2. http://ru.wikipedia.org
3. http://delphi.com/
4. Johannes Erdfelt. Libusb Developers Guide. Режим доступа:

http://libusb.sourceforge.net/doc/ (дата обращения 07.09.2013)