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

5.3.5. Производительность файловой системы

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

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

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

Когда требуется загрузить блок в заполненный до предела кэш, какой-либо другой блок должен быть из него удален (и записан на диск, если он был модифицирован в кэше). Эта ситуация очень похожа на страничную организацию памяти, и к ней применимы все обычные алгоритмы замены, описанные в главе 4, такие как FIFO (First in First Out - первым прибыл - первым обслужен), вторая попытка и LRU (Least Recently Used - с наиболее давним использованием). Одно приятное отличие кэширования от страничной организации памяти состоит в том, что обращения к кэшу производятся относительно нечасто, что позволяет хранить все блоки в точном LRU-порядке с однонаправленными списками.

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

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

L Насколько велика вероятность того, что данный блок скоро снова понадобится?

2. Важен ли данный блок для непротиворечивости файловой системы?

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

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

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

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

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

кэша количество обращений ввода/вывода к диску больше, чем при применении обычного кэша. Чтобы лучше понять разницу в этих двух подходах, представьте себе программу, сохраняющую блок размером в 1 Кбайт по одному символу. Система UNIX будет собирать все символы в кэше и записывать этот блок на диск каждые 30 с, или когда блок будет удален из кэша. Система MS-DOS будет обращаться к диску для каждого символа. Конечно, в большинстве программ применяется внутренняя буферизация, поэтому обычно они обращаются к системному вызову write не с одним символом, а с целыми строками или большими единицами данных.

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

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

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

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