Основы операционных систем 120 Символический линк имеет то преимущество, что он может использоваться для организации удобного доступа к файлам удаленных компьютеров, если, например, добавить к пути сетевой адрес удаленной машины. Циклический граф - структура более гибкая, нежели простое дерево, но работа с ней требует большой аккуратности. Поскольку теперь к файлу существует несколько путей, программа поиска файла может найти его на диске несколько раз. Простейшее практическое решение данной проблемы - ограничить число директорий при поиске. Полное устранение циклов при поиске - довольно трудоемкая процедура, выполняемая специальными утилитами и связанная с многократной трассировкой директорий файловой системы. Кооперация процессов при работе с файлами Когда различные пользователи работают вместе над проектом, они часто нуждаются в разделении фай- лов. Разделяемый файл - разделяемый ресурс. Как и в случае любого совместно используемого ресурса, про- цессы должны синхронизировать доступ к совместно используемым файлам, каталогам, чтобы избежать тупиковых ситуаций, дискриминации отдельных процессов и снижения производительности системы. Например, если несколько пользователей одновременно редактируют какой-либо файл и не принято спе- циальных мер, то результат будет непредсказуем и зависит от того, в каком порядке осуществлялись за- писи в файл. Между двумя операциями read одного процесса другой процесс может модифицировать данные, что для многих приложений неприемлемо. Простейшее решение данной проблемы - предоста- вить возможность одному из процессов захватить файл, то есть блокировать доступ к разделяемому фай- лу других процессов на все время, пока файл остается открытым для данного процесса. Однако это было бы недостаточно гибко и не соответствовало бы характеру поставленной задачи. Рассмотрим вначале грубый подход, то есть временный захват пользовательским процессом файла или записи (части файла между указанными позициями). Системный вызов, позволяющий установить и проверить блокировки на файл, является неотъемлемым атрибутом современных многопользовательских ОС. В принципе, было бы логично связать синхрониза- цию доступа к файлу как к единому целому с системным вызовом open (т. е., например, открытие файла в режиме записи или обновления могло бы означать его монопольную блокировку соответствующим про- цессом, а открытие в режиме чтения - совместную блокировку). Так поступают во многих операционных системах (начиная с ОС Multics). В ОС Unix это не так, что имеет исторические причины. В первой версии системы Unix, разработанной Томпсоном и Ричи, механизм захвата файла отсутствовал. Применялся очень простой подход к обеспечению параллельного (от нескольких процессов) доступа к файлам: система позволяла любому числу процессов одновременно открывать один и тот же файл в лю- бом режиме (чтения, записи или обновления) и не предпринимала никаких синхронизационных дейст- вий. Вся ответственность за корректность совместной обработки файла ложилась на использующие его процессы, и система даже не предоставляла каких-либо особых средств для синхронизации доступа про- цессов к файлу. Однако впоследствии для того, чтобы повысить привлекательность системы для коммер- ческих пользователей, работающих с базами данных, в версию V системы были включены механизмы захвата файла и записи, базирующиеся на системном вызове fcntl. Допускается два варианта синхронизации: с ожиданием, когда требование блокировки может привести к откладыванию процесса до того момента, когда это требование может быть удовлетворено, и без ожида- ния, когда процесс немедленно оповещается об удовлетворении требования блокировки или о невозмож- ности ее удовлетворения в данный момент. Установленные блокировки относятся только к тому процессу, который их установил, и не наследуются процессами-потомками этого процесса. Более того, даже если некоторый процесс пользуется синхрони- зационными возможностями системного вызова fcntl, другие процессы по-прежнему могут работать с Основы операционных систем 121 тем файлом без всякой синхронизации. Другими словами, это дело группы процессов, совместно исполь- зующих файл, - договориться о способе синхронизации параллельного доступа. Более тонкий подход заключается в прозрачной для пользователя блокировке отдельных структур ядра, отвечающих за работу с файлами части пользовательских данных. Например, в ОС Unix во время сис- темного вызова, осуществляющего ту или иную операцию с файлом, как правило, происходит блокиро- вание индексного узла, содержащего адреса блоков данных файла. Может показаться, что организация блокировок или запрета более чем одному процессу работать с файлом во время выполнения системного вызова является излишней, так как в подавляющем большинстве случаев выполнение системных вызовов и так не прерывается, то есть ядро работает в условиях невытесняющей многозадачности. Однако в дан- ном случае это не совсем так. Операции чтения и записи занимают продолжительное время и лишь ини- циируются центральным процессором, а осуществляются по независимым каналам, поэтому установка блокировок на время системного вызова является необходимой гарантией атомарности операций чтения и записи. На практике оказывается достаточным заблокировать один из буферов кэша диска, в заголовке которого ведется список процессов, ожидающих освобождения данного буфера. Таким образом, в соот- ветствии с семантикой Unix изменения, сделанные одним пользователем, немедленно становятся "вид- ны" другому пользователю, который держит данный файл открытым одновременно с первым. Примеры разрешения коллизий и тупиковых ситуаций Логика работы системы в сложных ситуациях может проиллюстрировать особенности организации мультидоступа. Рассмотрим в качестве примера образование потенциального тупика при создании связи (link), когда разрешен совместный доступ к файлу [Bach, 1986]. Два процесса, выполняющие одновременно следующие функции: процесс A: link("a/b/c/d","e/f/g"); процесс B: link("e/f","a/b/c/d/ee"); могут зайти в тупик. Предположим, что процесс A обнаружил индекс файла "a/b/c/d" в тот самый мо- мент, когда процесс B обнаружил индекс файла "e/f". Фраза "в тот же самый момент" означает, что сис- темой достигнуто состояние, при котором каждый процесс получил искомый индекс. Когда же теперь процесс A попытается получить индекс файла "e/f", он приостановит свое выполнение до тех пор, пока индекс файла "f" не освободится. В то же время процесс B пытается получить индекс каталога "a/b/c/d" и приостанавливается в ожидании освобождения индекса файла "d". Процесс A будет удерживать заблоки- рованным индекс, нужный процессу B, а процесс B, в свою очередь, будет удерживать заблокированным индекс, необходимый процессу A. Для предотвращения этого классического примера взаимной блокировки в файловой системе принято, чтобы ядро освобождало индекс исходного файла после увеличения значения счетчика связей. Тогда, по- скольку первый из ресурсов (индекс) свободен при обращении к следующему ресурсу, взаимной блоки- ровки не происходит. Поводов для нежелательной конкуренции между процессами много, особенно при удалении имен ката- логов. Предположим, что один процесс пытается найти данные файла по его полному символическому имени, последовательно проходя компонент за компонентом, а другой процесс удаляет каталог, имя ко- торого входит в путь поиска. Допустим, процесс A делает разбор имени "a/b/c/d" и приостанавливается во время получения индексного узла для файла "c". Он может приостановиться при попытке заблокиро- вать индексный узел или при попытке обратиться к дисковому блоку, где этот индексный узел хранится. Если процессу B нужно удалить связь для каталога с именем "c", он может приостановиться по той же самой причине, что и процесс A. Пусть ядро впоследствии решит возобновить процесс B раньше процес- са A. Прежде чем процесс A продолжит свое выполнение, процесс B завершится, удалив связь каталога "c" и его содержимое по этой связи. Позднее процесс A попытается обратиться к несуществующему ин- дексному узлу, который уже был удален. Алгоритм поиска файла, проверяющий в первую очередь нера- венство значения счетчика связей> нулю, должен сообщить об ошибке. Основы операционных систем 122 Можно привести и другие примеры, которые демонстрируют необходимость тщательного проектирова- ния файловой системы для ее последующей надежной работы. Hадежность файловой системы Жизнь полна неприятных неожиданностей, а разрушение файловой системы зачастую более опасно, чем разрушение компьютера. Поэтому файловые системы должны разрабатываться с учетом подобной воз- можности. Помимо очевидных решений, например своевременное дублирование информации (backup), файловые системы современных ОС содержат специальные средства для поддержки собственной со- вместимости. Целостность файловой системы Важный аспект надежной работы файловой системы - контроль ее целостности. В результате файловых операций блоки диска могут считываться в память, модифицироваться и затем записываться на диск. Причем многие файловые операции затрагивают сразу несколько объектов файловой системы. Напри- мер, копирование файла предполагает выделение ему блоков диска, формирование индексного узла, из- менение содержимого каталога и т. д. В течение короткого периода времени между этими шагами ин- формация в файловой системе оказывается несогласованной. И если вследствие непредсказуемой остановки системы на диске будут сохранены изменения только для части этих объектов (нарушена атомарность файловой операции), файловая система на диске может быть оставлена в несовместимом состоянии. В результате могут возникнуть нарушения логики работы с дан- ными, например появиться "потерянные" блоки диска, которые не принадлежат ни одному файлу и в то же время помечены как занятые, или, наоборот, блоки, помеченные как свободные, но в то же время за- нятые (на них есть ссылка в индексном узле) или другие нарушения. В современных ОС предусмотрены меры, которые позволяют свести к минимуму ущерб от порчи файло- вой системы и затем полностью или частично восстановить ее целостность. Порядок выполнения операций Очевидно, что для правильного функционирования файловой системы значимость отдельных данных не- равноценна. Искажение содержимого пользовательских файлов не приводит к серьезным (с точки зрения целостности файловой системы) последствиям, тогда как несоответствия в файлах, содержащих управ- ляющую информацию (директории, индексные узлы, суперблок и т. п.), могут быть катастрофическими. Поэтому должен быть тщательно продуман порядок выполнения операций со структурами данных фай- ловой системы. Рассмотрим пример создания жесткой связи для файла [Робачевский, 1999]. Для этого файловой системе необходимо выполнить следующие операции: • создать новую запись в каталоге, указывающую на индексный узел файла; • увеличить счетчик связей в индексном узле. Если аварийный останов произошел между 1-й и 2-й операциями, то в каталогах файловой системы бу- дут существовать два имени файла, адресующих индексный узел со значением счетчика связей, равному

1. Если теперь будет удалено одно из имен, это приведет к удалению файла как такового. Если же поря- док операций изменен и, как прежде, останов произошел между первой и второй операциями, файл будет иметь несуществующую жесткую связь, но существующая запись в каталоге будет правильной. Хотя это тоже является ошибкой, но ее последствия менее серьезны, чем в предыдущем случае. Журнализация Другим средством поддержки целостности является заимствованный из систем управления базами дан- ных прием, называемый журнализация (иногда употребляется термин "журналирование"). Последова- тельность действий с объектами во время файловой операции протоколируется, и если произошел оста- нов системы, то, имея в наличии протокол, можно осуществить откат системы назад в исходное целост- Основы операционных систем 123 ное состояние, в котором она пребывала до начала операции. Подобная избыточность может стоить до- рого, но она оправданна, так как в случае отказа позволяет реконструировать потерянные данные. Для отката необходимо, чтобы для каждой протоколируемой в журнале операции существовала обрат- ная. Например, для каталогов и реляционных СУБД это именно так. По этой причине, в отличие от СУБД, в файловых системах протоколируются не все изменения, а лишь изменения метаданных (индекс- ных узлов, записей в каталогах и др.). Изменения в данных пользователя в протокол не заносятся. Кроме того, если протоколировать изменения пользовательских данных, то этим будет нанесен серьезный ущерб производительности системы, поскольку кэширование потеряет смысл. Журнализация реализована в NTFS, Ext3FS, ReiserFS и других системах. Чтобы подчеркнуть сложность задачи, нужно отметить, что существуют не вполне очевидные проблемы, связанные с процедурой отка- та. Например, отмена одних изменений может затрагивать данные, уже использованные другими файло- выми операциями. Это означает, что такие операции также должны быть отменены. Данная проблема по- лучила название каскадного отката транзакций [Брукшир, 2001] Проверка целостности файловой системы при помощи утилит Если же нарушение все же произошло, то для устранения проблемы несовместимости можно прибегнуть к утилитам (fsck, chkdsk, scandisk и др.), которые проверяют целостность файловой системы. Они могут запускаться после загрузки или после сбоя и осуществляют многократное сканирование разнообразных структур данных файловой системы в поисках противоречий. Возможны также эвристические проверки. Hапример, нахождение индексного узла, номер которого пре- вышает их число на диске или поиск в пользовательских директориях файлов, принадлежащих супер- пользователю. К сожалению, приходится констатировать, что не существует никаких средств, гарантирующих абсо- лютную сохранность информации в файлах, и в тех ситуациях, когда целостность информации нужно гарантировать с высокой степенью надежности, прибегают к дорогостоящим процедурам дублирования. Управление "плохими" блоками Наличие дефектных блоков на диске - обычное дело. Внутри блока наряду с данными хранится кон- трольная сумма данных. Под "плохими" блоками обычно понимают блоки диска, для которых вычислен- ная контрольная сумма считываемых данных не совпадает с хранимой контрольной суммой. Дефектные блоки обычно появляются в процессе эксплуатации. Иногда они уже имеются при поставке вместе со списком, так как очень затруднительно для поставщиков сделать диск полностью свободным от дефек- тов. Рассмотрим два решения проблемы дефектных блоков - одно на уровне аппаратуры, другое на уров- не ядра ОС. Первый способ - хранить список плохих блоков в контроллере диска. Когда контроллер инициализирует- ся, он читает плохие блоки и замещает дефектный блок резервным, помечая отображение в списке пло- хих блоков. Все реальные запросы будут идти к резервному блоку. Следует иметь в виду, что при этом механизм подъемника (наиболее распространенный механизм обработки запросов к блокам диска) будет работать неэффективно. Дело в том, что существует стратегия очередности обработки запросов к диску (подробнее см. лекцию "ввод-вывод"). Стратегия диктует направление движения считывающей головки диска к нужному цилиндру. Обычно резервные блоки размещаются на внешних цилиндрах. Если плохой блок расположен на внутреннем цилиндре и контроллер осуществляет подстановку прозрачным образом, то кажущееся движение головки будет осуществляться к внутреннему цилиндру, а фактическое - к внеш- нему. Это является нарушением стратегии и, следовательно, минусом данной схемы. Решение на уровне ОС может быть следующим. Прежде всего, необходимо тщательно сконструировать файл, содержащий дефектные блоки. Тогда они изымаются из списка свободных блоков. Затем нужно каким-то образом скрыть этот файл от прикладных программ. Производительность файловой системы Основы операционных систем 124 Поскольку обращение к диску - операция относительно медленная, минимизация количества таких об- ращений - ключевая задача всех алгоритмов, работающих с внешней памятью. Наиболее типичная тех- ника повышения скорости работы с диском - кэширование. Кэширование Кэш диска представляет собой буфер в оперативной памяти, содержащий ряд блоков диска (см. рис. 12.12). Если имеется запрос на чтение/запись блока диска, то сначала производится проверка на предмет наличия этого блока в кэше. Если блок в кэше имеется, то запрос удовлетворяется из кэша, в противном случае запрошенный блок считывается в кэш с диска. Сокращение количества дисковых операций ока- зывается возможным вследствие присущего ОС свойства локальности (о свойстве локальности много го- ворилось в лекциях, посвященных описанию работы системы управления памятью). Аккуратная реализация кэширования требует решения нескольких проблем. Во-первых, емкость буфера кэша ограничена. Когда блок должен быть загружен в заполненный буфер кэша, возникает проблема замещения блоков, то есть отдельные блоки должны быть удалены из него. Здесь работают те же стратегии и те же FIFO, Second Chance и LRU-алгоритмы замещения, что и при вы- талкивании страниц памяти. Рис. 12.12. Структура блочного кэша Замещение блоков должно осуществляться с учетом их важности для файловой системы. Блоки должны быть разделены на категории, например: блоки индексных узлов, блоки косвенной адресации, блоки ди- ректорий, заполненные блоки данных и т. д., и в зависимости от принадлежности блока к той или иной категории можно применять к ним разную стратегию замещения. Во-вторых, поскольку кэширование использует механизм отложенной записи, при котором модифика- ция буфера не вызывает немедленной записи на диск, серьезной проблемой является "старение" инфор- мации в дисковых блоках, образы которых находятся в буферном кэше. Несвоевременная синхрониза- ция буфера кэша и диска может привести к очень нежелательным последствиям в случае отказов обору- дования или программного обеспечения. Поэтому стратегия и порядок отображения информации из кэша на диск должна быть тщательно продумана. Так, блоки, существенные для совместимости файловой системы (блоки индексных узлов, блоки косвен- ной адресации, блоки директорий), должны быть переписаны на диск немедленно, независимо от того, в какой части LRU-цепочки они находятся. Hеобходимо тщательно выбрать порядок такого переписыва- ния. В Unix имеется для этого вызов SYNC, который заставляет все модифицированные блоки записываться на диск немедленно. Для синхронизации содержимого кэша и диска периодически запускается фоновый процесс-демон. Кроме того, можно организовать синхронный режим работы с отдельными файлами, за- даваемый при открытии файла, когда все изменения в файле немедленно сохраняются на диске. Основы операционных систем 125 Наконец, проблема конкуренции процессов на доступ к блокам кэша решается ведением списков блоков, пребывающих в различных состояниях, и отметкой о состоянии блока в его дескрипторе. Например, блок может быть заблокирован, участвовать в операции ввода-вывода, а также иметь список процессов, ожи- дающих освобождения данного блока. Оптимальное размещение информации на диске Кэширование - не единственный способ увеличения производительности системы. Другая важная тех- ника - сокращение количества движений считывающей головки диска за счет разумной стратегии разме- щения информации. Например, массив индексных узлов в Unix стараются разместить на средних дорож- ках. Также имеет смысл размещать индексные узлы поблизости от блоков данных, на которые они ссы- лаются и т. д. Кроме того, рекомендуется периодически осуществлять дефрагментацию диска (сборку мусора), по- скольку в популярных методиках выделения дисковых блоков (за исключением, может быть, FAT) прин- цип локальности не работает, и последовательная обработка файла требует обращения к различным уча- сткам диска. Реализация некоторых операций над файлами В предыдущей лекции перечислены основные операции над файлами. В данном разделе будет описан порядок работы некоторых системных вызовов для работы с файловой системой, следуя главным обра- зом [Bach, 1986], с учетом совокупности введенных в данной лекции понятий. Системные вызовы, работающие с символическим именем файла Системные вызовы, связывающие pathname с дескриптором файла Это функции создания и открытия файла. Например, в ОС Unix fd = creat(pathname,modes); fd = open(pathname,flags,modes); Другие операции над файлами, такие как чтение, запись, позиционирование головок чтения-записи, вос- произведение дескриптора файла, установка параметров ввода-вывода, определение статуса файла и за- крытие файла, используют значение полученного дескриптора файла. Рассмотрим работу системного вызова open. Логическая файловая подсистема просматривает файловую систему в поисках файла по его имени. Она проверяет права на открытие файла и выделяет открываемому файлу запись в таблице файлов. Запись таблицы файлов содержит указатель на индексный узел открытого файла. Ядро выделяет запись в личной (закрытой) таблице в адресном пространстве процесса, выделенном процессу (таблица эта называется таблицей пользовательских дескрипторов открытых файлов) и запоминает указатель на данную запись. В роли указателя выступает дескриптор файла, возвращаемый пользователю. Запись в таблице пользова- тельских файлов указывает на запись в глобальной таблице файлов (см. рис. 12.13). Первые три пользовательских дескриптора (0, 1 и 2) именуются дескрипторами файлов стандартного ввода, стандартного вывода и стандартного файла ошибок. Процессы в системе Unix по договоренности используют дескриптор файла стандартного ввода при чтении вводимой информации, дескриптор файла стандартного вывода при записи выводимой информации и дескриптор стандартного файла ошибок для записи сообщений об ошибках. Основы операционных систем 126 Рис. 12.13. Структуры данных после открытия файлов Связывание файла Системная функция link связывает файл с новым именем в структуре каталогов файловой системы, соз- давая для существующего индекса новую запись в каталоге. Синтаксис вызова функции link: link(source file name, target file name); где source file name - существующее имя файла, а target file name - новое (дополнительное) имя, присваи- ваемое файлу после выполнения функции link. Сначала ОС определяет местонахождение индекса исходного файла и увеличивает значение счетчика связей в индексном узле. Затем ядро ищет файл с новым именем; если он существует, функция link за- вершается неудачно, и ядро восстанавливает прежнее значение счетчика связей, измененное ранее. В противном случае ядро находит в родительском каталоге свободную запись для файла с новым именем, записывает в нее новое имя и номер индекса исходного файла. Удаление файла В Unix системная функция unlink удаляет из каталога точку входа для файла. Синтаксис вызова функции unlink: unlink(pathname); Если удаляемое имя является последней связью файла с каким-либо каталогом, ядро в итоге освобождает все информационные блоки файла. Однако если у файла было несколько связей, он остается все еще дос- тупным под другими именами. Для того чтобы забрать дисковые блоки, ядро в цикле просматривает таблицу содержимого индексного узла, освобождая все блоки прямой адресации немедленно. Что касается блоков косвенной адресации, то ядро освобождает все блоки, появляющиеся на различных уровнях косвенности, рекурсивно, причем в первую очередь освобождаются блоки с меньшим уровнем. Системные вызовы, работающие с файловым дескриптором Основы операционных систем 127 Открытый файл может использоваться для чтения и записи последовательностей байтов. Для этого под- держиваются два системных вызова read и write, работающие с файловым дескриптором (или handle в терминологии Microsoft), полученным при ранее выполненных системных вызовах open или creat. Функции ввода-вывода из файла Системный вызов read выполняет чтение обычного файла number = read(fd,buffer,count); где fd - дескриптор файла, возвращаемый функцией open, buffer - адрес структуры данных в пользова- тельском процессе, где будут размещаться считанные данные в случае успешного завершения выполне- ния функции read, count - количество байтов, которые пользователю нужно прочитать, number - количе- ство фактически прочитанных байтов. Синтаксис вызова системной функции write (писать): number = write(fd,buffer,count); где переменные fd, buffer, count и number имеют тот же смысл, что и для вызова системной функции read. Алгоритм записи в обычный файл похож на алгоритм чтения из обычного файла. Однако если в файле отсутствует блок, соответствующий смещению в байтах до места, куда должна производиться запись, ядро выделяет блок и присваивает ему номер в соответствии с точным указанием места в таблице содер- жимого индексного узла. Обычное использование системных функций read и write обеспечивает последовательный доступ к фай- лу, однако процессы могут использовать вызов системной функции lseek для указания места в файле, где будет производиться ввод-вывод, и осуществления произвольного доступа к файлу. Синтаксис вызова системной функции: position = lseek(fd,offset,reference); где fd - дескриптор файла, идентифицирующий файл, offset - смещение в байтах, а reference указывает, является ли значение offset смещением от начала файла, смещением от текущей позиции ввода-вывода или смещением от конца файла. Возвращаемое значение, position, является смещением в байтах до места, где будет начинаться следующая операция чтения или записи. Современные архитектуры файловых систем Современные ОС предоставляют пользователю возможность работать сразу с несколькими файловыми системами (Linux работает с Ext2fs, FAT и др.). Файловая система в традиционном понимании становит- ся частью более общей многоуровневой структуры (см. рис. 12.14). На верхнем уровне располагается так называемый диспетчер файловых систем (например, в Windows 95 этот компонент называется installable filesystem manager). Он связывает запросы прикладной программы с конкретной файловой системой. Каждая файловая система (иногда говорят - драйвер файловой системы) на этапе инициализации регист- рируется у диспетчера, сообщая ему точки входа, для последующих обращений к данной файловой сис- теме. Та же идея поддержки нескольких файловых систем в рамках одной ОС может быть реализована по- другому, например исходя из концепции виртуальной файловой системы. Виртуальная файловая система (vfs) представляет собой независимый от реализации уровень и опирается на реальные файловые систе- мы (s5fs, ufs, FAT, NFS, FFS. Ext2fs ѕ). При этом возникают структуры данных виртуальной файловой системы типа виртуальных индексных узлов vnode, которые обобщают индексные узлы конкретных сис- тем. Основы операционных систем 128 Рис. 12.14. Архитектура современной файловой системы Заключение Реализация файловой системы связана с такими вопросами, как поддержка понятия логического блока диска, связывания имени файла и блоков его данных, проблемами разделения файлов и проблемами управления дискового пространства. Наиболее распространенные способы выделения дискового пространства: непрерывное выделение, орга- низация связного списка и система с индексными узлами. Файловая система часто реализуется в виде слоеной модульной структуры. Нижние слои имеют дело с оборудованием, а верхние - с символическими именами и логическими свойствами файлов. Директории могут быть организованы различными способами и могут хранить атрибуты файла и адреса блоков файлов, а иногда для этого предназначается специальная структура (индексные узлы). Проблемы надежности и производительности файловой системы - важнейшие аспекты ее дизайна