Добавлен: 29.10.2018
Просмотров: 48113
Скачиваний: 190
4.4. Управление файловой системой и ее оптимизация
341
сектора (за исключением твердотельного диска), поэтому чтение файла, состоящего
из множества небольших блоков, будет медленным.
В качестве примера рассмотрим диск, у которого на каждой дорожке размещается по
1 Мбайт данных. На ожидание подхода нужного сектора затрачивается 8,33 мс, а сред-
нее время позиционирования блока головок составляет 5 мс. Время в миллисекундах,
затрачиваемое на чтение блока из k байт, складывается из суммы затрат времени на по-
зиционирование блока головок, ожидание подхода нужного сектора и перенос данных:
5 + 4,165 + (k/1 000 000) · 8,33.
Пунктирная кривая на рис. 4.17 показывает зависимость скорости передачи данных
такого диска от размера блока. Для вычисления эффективности использования дис-
кового пространства нужно сделать предположение о среднем размере файла. В целях
упрощения предположим, что все файлы имеют размер 4 Кбайт. Хотя это число не-
сколько превышает объем данных, определенный в VU, у студентов, возможно, боль-
ше файлов небольшого размера, чем в корпоративном центре хранения и обработки
данных, так что в целом это может быть наилучшим предположением. Сплошная
кривая на рис. 4.17 показывает зависимость эффективности использования дискового
пространства от размера блока.
Рис. 4.17. Пунктирная кривая (по шкале слева) показывает скорость передачи данных с диска,
сплошная кривая (по правой шкале) показывает эффективность использования
дискового пространства. Все файлы имеют размер 4 Кбайт
Эти две кривые можно понимать следующим образом. Время доступа к блоку полно-
стью зависит от времени позиционирования блока головок и ожидания подхода под
головки нужного сектора. Таким образом, если затраты на доступ к блоку задаются на
уровне 9 мс, то чем больше данных извлекается, тем лучше. Поэтому с ростом размера
блока скорость передачи данных возрастает практически линейно (до тех пор, пока
перенос данных не займет столько времени, что его уже нужно будет брать в расчет).
Теперь рассмотрим эффективность использования дискового пространства. Потери
при использовании файлов размером 4 Кбайт и блоков размером 1, 2 или 4 Кбайт
практически отсутствуют. При блоках по 8 Кбайт и файлах по 4 Кбайт эффективность
использования дискового пространства падает до 50 %, а при блоках по 16 Кбайт — до
25 %. В реальности точно попадают в кратность размера дисковых блоков всего не-
сколько файлов, поэтому потери пространства в последнем блоке файла бывают всегда.
342
Глава 4. Файловые системы
Кривые показывают, что производительность и эффективность использования дис-
кового пространства по своей сути конфликтуют. Небольшие размеры блоков вредят
производительности, но благоприятствуют эффективности использования дискового
пространства. В представленных данных найти какой-либо разумный компромисс не-
возможно. Размер, находящийся поблизости от пересечения двух кривых, составляет
64 Кбайт, но скорость передачи данных в этой точке составляет всего лишь 6,6 Мбайт/с,
а эффективность использования дискового пространства находится на отметке, близкой
к 7 %. Ни то ни другое нельзя считать приемлемым результатом. Исторически сложилось
так, что в файловых системах выбор падал на диапазон размеров от 1 до 4 Кбайт, но при
наличии дисков, чья емкость сегодня превышает 1 Тбайт, может быть лучше увеличить
размер блоков до 64 Кбайт и смириться с потерями дискового пространства. Вряд ли
дисковое пространство когда-либо будет в дефиците.
В рамках эксперимента по поиску существенных различий между использованием
файлов в Windows NT и в UNIX Вогельс провел измерения, используя файлы, с ко-
торыми работают в Корнелльском университете (Vogels, 1999). Он заметил, что в NT
файлы используются более сложным образом, чем в UNIX. Он написал следующее:
«Набор в Блокноте нескольких символов с последующим сохранением в файле приво-
дит к 26 системным вызовам, включая 3 неудачные попытки открытия файла, 1 пере-
писывание файла и 4 дополнительные последовательности его открытия и закрытия».
При этом Вогельс проводил исследования с файлами усредненного размера (опре-
деленного на практике). Для чтения брались файлы размером 1 Кбайт, для записи —
2,3 Кбайт, для чтения и записи — 4,2 Кбайт. Если принять в расчет различные техноло-
гии измерения набора данных и то, что заканчивается 2014 год, эти результаты вполне
совместимы с результатами, полученными в VU.
Отслеживание свободных блоков
После выбора размера блока возникает следующий вопрос: как отслеживать свободные
блоки? На рис. 4.18 показаны два метода, нашедшие широкое применение. Первый
метод состоит в использовании связанного списка дисковых блоков, при этом в каж-
дом блоке списка содержится столько номеров свободных дисковых блоков, сколько
в него может поместиться. При блоках размером 1 Кбайт и 32-разрядном номере
дискового блока каждый блок может хранить в списке свободных блоков номера 255
блоков. (Одно слово необходимо под указатель на следующий блок.) Рассмотрим диск
емкостью 1 Тбайт, имеющий около 1 млрд дисковых блоков. Для хранения всех этих
адресов по 255 на блок необходимо около 4 млн блоков. Как правило, для хранения
списка свободных блоков используются сами свободные блоки, поэтому его хранение
обходится практически бесплатно.
Другая технология управления свободным дисковым пространством использует бито-
вый массив. Для диска, имеющего n блоков, требуется битовый массив, состоящий из
n битов. Свободные блоки представлены в массиве в виде единиц, а распределенные —
в виде нулей (или наоборот). В нашем примере с диском размером 1 Тбайт массиву
необходимо иметь 1 млрд битов, для хранения которых требуется около 130 000 бло-
ков размером 1 Кбайт каждый. Неудивительно, что битовый массив требует меньше
пространства на диске, поскольку в нем используется по одному биту на блок, а не по
32 бита, как в модели, использующей связанный список. Только если диск почти за-
полнен (то есть имеет всего несколько свободных блоков), для системы со связанными
списками требуется меньше блоков, чем для битового массива.
4.4. Управление файловой системой и ее оптимизация
343
Рис. 4.18. Хранение сведений о свободных блоках: а — в связанном списке;
б — в битовом массиве
Если свободные блоки выстраиваются в длинные непрерывные последовательности
блоков, система, использующая список свободных блоков, может быть модифициро-
вана на отслеживание последовательности блоков, а не отдельных блоков. С каждым
блоком, дающим номер последовательных свободных блоков, может быть связан 8-,
16- или 32-разрядный счетчик. В идеале в основном пустой диск может быть пред-
ставлен двумя числами: адресом первого свободного блока, за которым следует счетчик
свободных блоков. Но если диск становится слишком фрагментированным, отслежи-
вание последовательностей менее эффективно, чем отслеживание отдельных блоков,
поскольку при этом должен храниться не только адрес, но и счетчик.
Это иллюстрирует проблему, с которой довольно часто сталкиваются разработчики
операционных систем. Для решения проблемы можно применить несколько структур
данных и алгоритмов, но для выбора наилучших из них требуются сведения, которых
разработчики не имеют и не будут иметь до тех пор, пока система не будет развернута
и испытана временем. И даже тогда сведения могут быть недоступными. К примеру,
наши собственные замеры размеров файлов в VU, данные веб-сайта и данные Кор-
нелльского университета — это всего лишь четыре выборки. Так как это лучше, чем
ничего, мы склонны считать, что они характерны и для домашних компьютеров, кор-
поративных машин, компьютеров госучреждений и других вычислительных систем.
Затратив определенные усилия, мы могли бы получить несколько выборок для других
категорий компьютеров, но даже тогда их было бы глупо экстраполировать на все
компью теры исследованной категории.
344
Глава 4. Файловые системы
Ненадолго возвращаясь к методу, использующему список свободных блоков, следует
заметить, что в оперативной памяти нужно хранить только один блок указателей. При
создании файла необходимые для него блоки берутся из блока указателей. Когда он бу-
дет исчерпан, с диска считывается новый блок указателей. Точно так же при удалении
файла его блоки освобождаются и добавляются к блоку указателей, который находится
в оперативной памяти. Когда этот блок заполняется, он записывается на диск.
При определенных обстоятельствах этот метод приводит к выполнению излишних дис-
ковых операций ввода-вывода. Рассмотрим ситуацию, показанную на рис. 4.19, а, где
находящийся в оперативной памяти блок указателей имеет свободное место только для
двух записей. Если освобождается файл, состоящий из трех блоков, блок указателей
переполняется и должен быть записан на диск, что приводит к ситуации, показанной на
рис. 4.19, б. Если теперь записывается файл из трех блоков, опять должен быть считан
полный блок указателей, возвращающий нас к ситуации, изображенной на рис. 4.19, а.
Если только что записанный файл из трех блоков был временным файлом, то при его
освобождении требуется еще одна запись на диск, чтобы сбросить на него обратно
полный блок указателей. Короче говоря, когда блок указателей почти пуст, ряд вре-
менных файлов с кратким циклом использования может стать причиной выполнения
множества дисковых операций ввода-вывода.
Альтернативный подход, позволяющий избежать большинства операций ввода-вывода,
состоит в разделении полного блока указателей на две части. Тогда при освобождении
трех блоков вместо перехода от ситуации, изображенной на рис. 4.19, а, к ситуации,
проиллюстрированной на рис. 4.19, б, мы переходим от ситуации, показанной на
рис. 4.19, а, к ситуации, которую видим на рис. 4.19, в. Теперь система может справиться
с серией временных файлов без каких-либо операций дискового ввода-вывода. Если
блок в памяти заполняется, он записывается на диск, а с диска считывается полузапол-
ненный блок. Идея здесь в том, чтобы хранить большинство блоков указателей на диске
полными (и тем самым свести к минимуму использование диска), а в памяти хранить
полупустой блок, чтобы он мог обслуживать как создание файла, так и его удаление без
дисковых операций ввода-вывода для обращения к списку свободных блоков.
При использовании битового массива можно также содержать в памяти только один
блок, обращаясь к диску за другим блоком только при полном заполнении или опусто-
Рис. 4.19. Три ситуации: а — почти заполненный блок указателей на свободные дисковые блоки,
находящийся в памяти, и три блока указателей на диске; б — результат освобождения файла
из трех блоков; в — альтернативная стратегия обработки трех свободных блоков. Закрашены
указатели на свободные дисковые блоки
4.4. Управление файловой системой и ее оптимизация
345
шении хранящегося в памяти блока. Дополнительное преимущество такого подхода
состоит в том, что при осуществлении всех распределений из одного блока битового
массива дисковые блоки будут находиться близко друг к другу, сводя к минимуму пере-
мещения блока головок. Поскольку битовый массив относится к структурам данных
с фиксированным размером, если ядро частично разбито на страницы, битовая карта
может размещаться в виртуальной памяти и иметь страницы, загружаемые по мере
надобности.
Дисковые квоты
Чтобы не дать пользователям возможности захватывать слишком большие области дис-
кового пространства, многопользовательские операционные системы часто предоставля-
ют механизм навязывания дисковых квот. Замысел заключается в том, чтобы системный
администратор назначал каждому пользователю максимальную долю файлов и блоков,
а операционная система гарантировала невозможность превышения этих квот. Далее
будет описан типичный механизм реализации этого замысла.
Когда пользователь открывает файл, определяется местоположение атрибутов
и дисковых адресов и они помещаются в таблицу открытых файлов, находящуюся
в оперативной памяти. В числе атрибутов имеется запись, сообщающая о том, кто
является владельцем файла. Любое увеличение размера файла будет засчитано
в квоту владельца.
Во второй таблице содержится запись квоты для каждого пользователя, являющегося
владельцем какого-либо из открытых в данный момент файлов, даже если этот файл
был открыт кем-нибудь другим. Эта таблица показана на рис. 4.20. Она представляет
собой извлечение из имеющегося на диске файла квот, касающееся тех пользователей,
чьи файлы открыты в настоящее время. Когда все файлы закрыты, записи сбрасывается
обратно в файл квот.
Рис. 4.20. Квоты отслеживаются для каждого пользователя в таблице квот