Производительность файловой системы
Доступ к диску производится значительно медленнее, чем к оперативной памяти, поэтому во многих файловых системах применяются различные методы оптимизации, увеличивающие производительность.
Метод 1: кэширование. В некоторых файловых системах, в которых адресация осуществляется блоками, запросы к внешним устройствам перехватываются промежуточным программным слоем – подсистемой буферизации (буферным кэшем, блочным кэшем; франц. cacher – скрывать). Подсистема буферизации представляет собой буферный кэш, располагающийся в оперативной памяти, и комплекс управляющих программ. В данном контексте кэш представляет собой набор блоков, логически принадлежащих диску, но хранящихся в оперативной памяти по соображениям производительности. При поступлении запроса на чтение некоторого блока подсистема буферизации просматривает свой буферный кэш, если находит требуемый блок, то копирует его в буфер запрашивающего процесса. Операция ввода-вывода считается выполненной, хотя физического обмена с устройством не происходило. Если же нужный блок в буферном кэше отсутствует, то он считывается с диска и одновременно с передачей запрашивающему процессу копируется в один из буферов подсистемы буферизации. При отсутствии свободного буфера на диск вытесняется наименее используемая информация. Таким образом, подсистема буферизации работает по принципу кэш-памяти.
Поскольку в кэше хранится большое количество блоков, то необходим способ быстрого определения наличия или отсутствия требуемого блока. Обычно для этого используется хэширование номера устройства и дискового адреса (номера блока) и поиск результата в хэш-таблице. Все блоки с одинаковыми хэш-кодами связываются вместе в связный список. Когда требуется загрузить блок в заполненный кэш, то другой блок должен быть удален и помещен на диск. С этой целью используются алгоритмы замещения FIFO (First in First Out – первым пришел – первым обслужен) и LRU (Least Recently Used – с наиболее давним использованием, то есть выгружается из оперативной памяти блок, который не использовался дольше всего).
Замещение блоков должно осуществляется с учетом их важности для файловой системы. Поэтому блоки подразделяются на категории: блоки индексных узлов, блоки косвенной адресации, блоки директорий, блоки данных и пр. Категория блоков, которая возможно не потребуется в ближайшее время, помещается в начало списка LRU, чтобы занимаемые ими буферы могли вскоре освободиться. Категория блоков, вероятность повторного использования которых высока, помещаются в конец списка LRU, что позволяет им остаться в кэше более долгое время.
В связи с тем, что долгое хранение в кэше блоков с данными является нежелательным из-за вероятности потери данных в случае сбоя в работе системы, используются методы принудительного сохранения модифицированных блоков на диске. В UNIX имеется системный вызов sync, который записываться на диск модифицированные блоки. При загрузке операционной системы запускается фоновый процесс (демон) update, работа которого заключается в периодическом (через каждые 30 секунд) обращении к вызову sync. В системе MS DOS и Windows каждый модифицированный блок записывается на диск сразу. Кэш, в котором модифицированные блоки записываются на диск немедленно, называется сквозным кэшем или кэшем со сквозной записью.
Метод 2: опережающее чтение блока. Метод заключается в получении блоков диска в кэш прежде, чем они потребуются. Многие файлы считываются последовательно, поэтому при получении файловой системой запроса на чтение блока n и его выполнения, она проверяет, есть ли в кэше следующий блок n+1. При его отсутствии файловая система считывает блок в кэш, учитывая возможность его использования в будущем. При обращении к блокам в случайном порядке данный метод не используется. Чтобы определить, следует ли его использовать, файловая система должна вести учет доступа к блокам каждого открытого файла. Например, для каждого открытого файла назначается бит, который означает режим последовательного доступа, который при перемещении указателя в файле сбрасывается. Если к файлу снова будут обращаться с запросами последовательного чтения, то бит повторно устанавливается. Таким образом, файловая система определяет, следует ли ей выполнять операции опережающего чтения или нет.
Метод 3: снижение времени перемещения блока головок. Уменьшение затрат времени на перемещение блока головок достигается помещением блоков, к которым высока вероятность доступа в течение короткого интервала времени, на одном цилиндре близко друг к другу. При записи выходного файла файловая система резервирует место для чтения таких блоков за одну операцию. Если свободные блоки учитываются в битовом массиве, а битовый массив помещается в оперативной памяти, то легко выбрать свободный блок как можно ближе к предыдущему блоку.
В случае, когда свободные блоки хранятся в списке, часть которого находится в оперативной памяти, а часть на диске, выполняется кластеризация блоков таким образом, чтобы учитывать место на диске не в блоках, а в группах последовательных блоков. Если сектор состоит из 512 байт, система может использовать блоки размером в 1 Кбайт (2 сектора), но выделять пространство на диске в единицах по 2 блока (4 сектора).
Другой фактор, снижающий производительность файловых систем, связан с тем, что при использовании i-узлов требуется два обращения к диску вместо одного: одно для i-узла и одно для блока данных. Обычно все i-узлы располагаются в начале диска. Среднее расстояние между i-узлом и его блоками составляет около половины количества цилиндров, поэтому при доступе к файлу требуется значительное перемещение блока головок.
Один из способов увеличения производительности состоит в помещении i-узлов в середину диска для уменьшения среднего расстояния перемещения блоков головок в два раза. Другая идея заключается в разбиении диска на группы цилиндров, причем каждая группа имеет свои i-узлы, блоки и списки свободных блоков. При создании нового файла выбирается любой i-узел и предпринимается попытка найти блок в той же группе цилиндров, что и i-узел. Если эта попытка заканчивается неудачей, используется блок в соседней группе цилиндров.
Метод 4: журнализация. Метод заключается в использовании диска как журнала. Периодически буферизированные в памяти блоки, которые должны быть записаны, собираются вместе в единый сегмент, который записывается на диск одним непрерывным блоком в конец журнала. Записываемый сегмент может содержать i-узлы, блоки каталогов и блоки данных, перемешанные друг с другом. В начале каждого сегмента создается оглавление. Если средний размер сегмента составляет 1 Мбайт, то используется почти вся пропускная способность диска.
При такой организации i-узлы имеют ту же структуру, что и в UNIX, но расположены в разных частях журнала. Для нахождения i-узла создается массив i-узлов, индексированный по i-номерам. Элемент i- массива указывает на i-узел на диске. Массив хранится на диске, но также содержится в кэше, поэтому часто используемые части массива постоянно находятся в оперативной памяти. Таким образом, все операции записи буферизируются в оперативной памяти, и периодически данные из буфера записываются на диск в виде единых сегментов в конец журнала. Чтобы открыть файл, используется массив, позволяющий обнаружить i-узел в файле. При обнаружении i-узла определяются номера блоков файла, расположенных в сегментах журнала.
Так как диски имеют ограниченный размер, то существует вероятность, что журнал займет весь диск. Однако многие сегменты могут содержать ненужные блоки. Для решения проблемы повторного использования блоков в старых сегментах создается чистящий поток, занимающийся постоянным сканированием журнала с целью сделать его более компактным. Чистящий поток считывает содержание первого сегмента журнала, чтобы определить, какие i-узлы и файлы находятся в нем. Затем он проверяет текущий массив i-узлов и определяет, используются ли блоки файлов. Если нет, то эта информация отбрасывается, а использующиеся i-узлы и блоки считываются в память, чтобы записать их в следующий сегмент. Исходный сегмент помечается как свободный, поэтому журнал может использовать его для новых данных. Таким образом, чистящий процесс, двигаясь по журналу, удаляет старые сегменты с диска и помещает ценную информацию в память для перезаписи в следующий сегмент. В результате диск представляет собой большой кольцевой буфер, в котором пишущий поток добавляет новые сегменты с одного конца, а чистящий процесс удаляет старые сегменты с другого.