Страница:
дисковые блоки к тому же могут быть переназначены другим файлам. Чтобы очис-
тить файловую систему программой fsck, потребовались бы большие усилия. Од-
нако, если система сначала переписала индекс на диск, а потом дала сбой,
пользователь не заметит каких-либо искажений в файловой системе после пере-
загрузки. Информационные блоки, ранее принадлежавшие файлу, станут недоступ-
ны для системы, но каких-нибудь явных изменений при этом пользователи не
увидят. Программе fsck так же было бы проще забрать назад освободившиеся
после удаления связи дисковые блоки, нежели производить очистку, необходимую
в первом из рассматриваемых случаев.
Поводов для конкуренции при выполнении системной функции unlink очень
много, особенно при удалении имен каталогов. Команда rmdir удаляет каталог,
убедившись предварительно в том, что в каталоге отсутствуют файлы (она счи-
тывает каталог и проверяет значения индексов во всех записях каталога на ра-
венство нулю). Но так как команда rmdir запускается на пользовательском
уровне, действия по проверке содержимого каталога и удаления каталога выпол-
няются не так уж просто; система должна переключать контекст между выполне-
нием функций read и unlink. Однако, после того, как команда rmdir обнаружи-
ла, что каталог пуст, другой процесс может предпринять попытку создать файл
в каталоге функцией creat. Избежать этого пользователи могут только путем
использования механизма захвата файла и записи. Тем не менее, раз процесс
приступил к выполнению функции unlink, никакой другой процесс не может обра-
титься к файлу с удаляемой связью, поскольку индексы родительского каталога
и файла заблокированы.
Обратимся еще раз к алгоритму функции link и посмотрим, каким образом
система снимает с индекса блокировку до завершения выполнения функции. Если
бы другой процесс удалил связь файла пока его индекс свободен, он бы тем са-
мым только уменьшил значение счетчика связей; так как значение счетчика свя-
зей было увеличено перед удалением связи, это значение останется положитель-
ным. Следовательно, файл не может быть удален и система работает надежно.
Эта ситуация аналогична той, когда функция unlink вызывается сразу после за-
вершения выполнения функции link.
Другой повод для конкуренции имеет место в том случае, когда один про-
цесс преобразует имя пути поиска файла в индекс файла по алгоритму namei, а
другой процесс удаляет каталог, имя которого входит в путь поиска. Допустим,
процесс A делает разбор имени "a/ b/c/d" и приостанавливается во время полу-
чения индекса для файла "c". Он может приостановиться при попытке заблокиро-
вать индекс или при попытке обратиться к дисковому блоку, где этот индекс
хранится (см. алгоритмы iget и bread). Если процессу B нужно удлить связь
для каталога с именем "c", он может приостановиться по той же самой причине,
что и процесс A. Пусть ядро впоследствии решит возобновить процесс B раньше
процесса A. Прежде чем процесс A продолжит свое выполнение, процесс B завер-
шится, удалив связь каталога "c" и его содержимое по этой связи. Позднее,
процесс A попытается обратиться к несуществующему индексу, который уже был
удален. Алгоритм namei, проверяющий в первую очередь неравенство значения
счетчика связей нулю, сообщит об ошибке.
Такой проверки, однако, не всегда достаточно, поскольку можно предполо-
жить, что какой-нибудь другой процесс создаст в любом месте файловой системы
новый каталог и получит тот индекс, который ранее использовался для "c".
126
Процесс A будет заблуждаться, думая, что он обратился к нужному индексу (см.
Рисунок 5.32). Как бы то ни было, система сохраняет свою целостность; самое
худшее, что может произойти, это обращение не к тому файлу - с возможным на-
Процесс A Процесс B Процесс C
+------------------------------------------------------------
| - Удаляется связь фай- -
| - ла с именем "с" -
| - -
| - Обнаруживает, что -
| - индекс файла "c" -
| - заблокирован -
| - Приостанавливает -
| - выполнение -
| - - -
| Просматривает ка- - -
| талог "b" в поис- - -
| ках имени "c" - -
| Получает номер ин- - -
| декса для "c" - -
| Обнаруживает, что - -
| индекс файла "c" - -
| заблокирован - -
| Приостанавливает - -
| выполнение - -
| - - -
| - Возобновляет выпол- -
| - нение, индекс "c" -
| - свободен -
| - Удаляет связь с име- -
| - нем "c", прежний ин- -
| - декс освобождается, -
| - если число связей =0 -
| - - -
| - - Назначает индекс
| - - новому файлу "n"
| - - Случайно назнача-
| - - ет ему индекс, ра-
| - - нее принадлежавший
| - - "c"
| - -
| - - В конечном итоге
| - - снимает блокировку
| - - с индекса "n"
| - -
| Возобновляет выпол- -
| нение, прежний ин- -
| декс "c" (теперь -
| "n") свободен -
| Получает индекс "n" -
| Просматривает ка- -
| талог "n" в поис- -
| ках имени "d" -
v
Время
Рисунок 5.32. Соперничество процессов за индекс при выполне-
нии функции unlink
127
+------------------------------------------------------------+
| #include |
| #include |
| #include |
| |
| main(argc,argv) |
| int argc; |
| char *argv[]; |
| { |
| int fd; |
| char buf[1024]; |
| struct stat statbuf; |
| |
| if (argc != 2) /* нужен параметр */ |
| exit(); |
| fd = open(argv[1],O_RDONLY); |
| if (fd == -1) /* open завершилась |
| неудачно */ |
| exit(); |
| if (unlink(argv[1]) == -1) /* удалить связь с только |
| что открытым файлом */ |
| exit(); |
| if (stat(argv[1],&statbuf) == -1) /* узнать состоя- |
| ние файла по имени */ |
| printf("stat %s завершилась неудачно\n",argv[1]);|
| /* как и следовало бы */ |
| else |
| printf("stat %s завершилась успешно!\n",argv[1]);|
| if (fstat(fd,&statbuf) == -1) /* узнать состояние |
| файла по идентификатору */ |
| printf("fstat %s сработала неудачно!\n",argv[1]);|
| else |
| printf("fstat %s завершилась успешно\n",argv[1]);|
| /* как и следовало бы */ |
| while (read(fd,buf,sizeof(buf)) > 0) /* чтение откры- |
| того файла с удаленной связью */ |
| printf("%1024s",buf); /* вывод на печать поля |
| размером 1 Кбайт */ |
| } |
+------------------------------------------------------------+
Рисунок 5.33. Удаление связи с открытым файлом
рушением защиты - но соперничества такого рода на практике довольно редки.
Процесс может удалить связь файла в то время, как другому процессу нуж-
но, чтобы файл оставался открытым. (Даже процесс, удаляющий связь, может
быть процессом, выполнившим это открытие). Поскольку ядро снимает с индекса
блокировку по окончании выполнения функции open, функция unlink завершится
успешно. Ядро будет выполнять алгоритм unlink точно так же, как если бы файл
не был открыт, и удалит из каталога запись о файле. Теперь по имени удален-
ной связи к файлу не сможет обратиться никакой другой процесс. Однако, так
как системная функция open увеличила значение счетчика ссылок в индексе, яд-
ро не очищает содержимое файла при выполнении алгоритма iput перед заверше-
нием функции unlink. Поэтому процесс, открывший файл, может производить над
файлом все обычные действия по его дескриптору, включая чтение из файла и
запись в файл. Но когда процесс закрывает файл, значение счетчика ссылок в
алгоритме iput становится равным 0, и ядро очищает содержимое файла. Короче
говоря, процесс, открывший файл, продолжает работу так, как если бы функция
128
unlink не выполнялась, а unlink, в свою очередь, работает так, как если бы
файл не был открыт. Другие системные функции также могут продолжать выпол-
няться в процессе, открывшем файл.
В приведенном на Рисунке 5.33 примере процесс открывает файл, указанный
в качестве параметра, и затем удаляет связь только что открытого файла. Фун-
кция stat завершится неудачно, поскольку первоначальное имя после unlink
больше не указывает на файл (предпо-
лагается, что тем временем никакой другой процесс не создал файл с тем же
именем), но функция fstat завершится успешно, так как она выбирает индекс по
дескриптору файла. Процесс выполняет цикл, считывая на каждом шаге по 1024
байта и пересылая файл в стандартный вывод. Когда при чтении будет обнаружен
конец файла, процесс завершает работу: после завершения процесса файл перес-
тает существовать. Процессы часто создают временные файлы и сразу же удаляют
связь с ними; они могут продолжать ввод-вывод в эти файлы, но имена файлов
больше не появляются в иерархии каталогов. Если процесс по какой-либо причи-
не завершается аварийно, он не оставляет от временных файлов никакого следа.
Уайнбергером было введено понятие "тип файловой системы" для объяснения
механизма работы принадлежавшей ему сетевой файловой системы (см. краткое
описание этого механизма в [Killian 84]) и в позднейшей версии системы V
поддерживаются основополагающие принципы его схемы. Наличие типа файловой
системы дает ядру возможность поддерживать одновременно множество файловых
систем, таких как сетевые файловые системы (глава 13) или даже файловые сис-
темы из других операционных систем. Процессы пользуются для обращения к фай-
лам обычными функциями системы UNIX, а ядро устанавливает соответствие между
общим набором файловых операций и операциями, специфичными для каждого типа
файловой системы.
Операции файловой Общие индексы Индекс файловой
системы системы версии V
+---------------+ +------+ +-------+
Версия V | open | +-----+- -+-------->| |
| close | | +------+ +-------+
| read | | +---+- -+---+ | |
| write |<---+ | +------+ | +-------+
| - |<-----|---+- -+---|---->| |
| - | | +------+ | +-------+
| - | | | | | | - |
| - | | +------+ | | - |
+---------------+ | | | | | - |
Удаленная | ropen | | +------+ | +-------+
система | rclose | | | - | |
| rread | | | - | | Индекс удален-
| rwrite |<-----+ | - | | ной системы
| - | | - | | +-------+
| - | | - | | | |
| - | | - | | +-------+
| - | | - | +---->| |
+---------------+ | - | +-------+
| - | | - | | |
| - | | - | +-------+
| - | | - | | |
| - | | - | +-------+
| - | | - | | - |
+---------------+ +------+ +-------+
Рисунок 5.34. Индексы для файловых систем различных типов
129
Индекс выступает интерфейсом между абстрактной файловой системой и от-
дельной файловой системой. Общая копия индекса в памяти содержит информацию,
не зависящую от отдельной файловой системы, а также указатель на частный ин-
декс файловой системы, который уже содержит информацию, специфичную для нее.
Частный индекс файловой системы содержит такую информацию, как права доступа
и расположение блоков, а общий индекс содержит номер устройства, номер ин-
декса на диске, тип файла, размер, информацию о владельце и счетчик ссылок.
Другая частная информация, описывающая отдельную файловую систему, содержит-
ся в суперблоке и структуре каталогов. На Рисунке 5.34 изображены таблица
общих индексов в памяти и две таблицы частных индексов отдельных файловых
систем, одна для структур файловой системы версии V, а другая для индекса
удаленной (сетевой) системы. Предполагается, что последний индекс содержит
достаточно информации для того, чтобы идентифицировать файл, находящийся в
удаленной системе. У файловой системы может отсутствовать структура, подоб-
ная индексу; но исходный текст программ отдельной файловой системы позволяет
создать объектный код, удовлетворяющий семантическим требованиям файловой
системы UNIX и назначающий свой "индекс", который соответствует общему ин-
дексу, назначаемому ядром.
Файловая система каждого типа имеет некую структуру, в которой хранятся
адреса функций, реализующих абстрактные действия. Когда ядру нужно обратить-
ся к файлу, оно вызывает косвенную функцию в зависимости от типа файловой
системы и абстрактного действия (см. Рисунок 5.34). Примерами абстрактных
действий являются: открытие и закрытие файла, чтение и запись данных, возв-
ращение индекса для компоненты имени файла (подобно namei и iget), освобож-
дение индекса (подобно iput), коррекция индекса, проверка прав доступа, ус-
тановка атрибутов файла (прав доступа к нему), а также монтирование и демон-
тирование файловых систем. В главе 13 будет проиллюстрировано использование
системных абстракций при рассмотрении распределенной файловой системы.
Ядро поддерживает целостность системы в своей обычной работе. Тем не ме-
нее, такие чрезвычайные обстоятельства, как отказ питания, могут привести к
фатальному сбою системы, в результате которого содержимое системы утрачивает
свою согласованность: большинство данных в файловой системе доступно для ис-
пользования, но некоторая несогласованность между ними имеет место. Команда
fsck проверяет согласованность данных и в случае необходимости вносит в фай-
ловую систему исправления. Она обращается к файловой системе через блочный
или строковый интерфейс (глава 10) в обход традиционных методов доступа к
файлам. В этом разделе рассматриваются некоторые примеры противоречивости
данных, которая обнаруживается командой fsck.
Дисковый блок может принадлежать более чем одному индексу или списку
свободных блоков. Когда файловая система открывается в первый раз, все дис-
ковые блоки находятся в списке свободных блоков. Когда дисковый блок выбира-
ется для использования, ядро удаляет его номер из списка свободных блоков и
назначает блок индексу. Ядро не может переназначить дисковый блок другому
индексу до тех пор, пока блок не будет возвращен в список свободных блоков.
Таким образом, дисковый блок может либо находиться в списке свободных бло-
ков, либо быть назначенным одному из индексов. Рассмотрим различные ситуа-
ции, могущие иметь место при освобождении ядром дискового блока, принадле-
жавшего файлу, с возвращением номера блока в суперблок, находящийся в памя-
ти, и при выделении дискового блока новому файлу. Если ядро записывало на
диск индекс и блоки нового файла, но перед внесением изменений в индекс
прежнего файла на диске произошел сбой, оба индекса будут адресовать к одно-
130
му и тому же номеру дискового блока. Подобным же образом, если ядро перепи-
сывало на диск суперблок и его списки свободных ресурсов и перед переписью
старого индекса случился сбой, дисковый блок появится одновременно и в спис-
ке свободных блоков, и в старом индексе.
Если блок отсутствует как в списке свободных блоков, так и в файле, фай-
ловая система является несогласованной, ибо, как уже говорилось выше, все
блоки обязаны где-нибудь присутствовать. Такая ситуация могла бы произойти,
если бы блок был удален из файла и помещен в список свободных блоков в су-
перблоке. Если производилась запись прежнего файла на диск и система дала
сбой перед записью суперблока, блок будет отсутствовать во всех списках,
хранящихся на диске.
Индекс может иметь счетчик связей с ненулевым значением при том, что его
номер отсутствует во всех каталогах файловой системы. Все файлы, за исключе-
нием каналов (непоименованных), должны присутствовать в древовидной структу-
ре файловой системы. Если система дала сбой после создания канала или обыч-
ного файла, но перед созданием соответствующей этому каналу или файлу точки
входа в каталог, индекс будет иметь в поле счетчика связей установленное
значение, пусть даже он явно не присутствует в файловой системе. Еще одна
проблема может возникнуть, если с помощью функции unlink была удалена связь
каталога без проверки удаления из каталога всех содержащихся в нем связей с
отдельными файлами.
Если формат индекса неверен (например, если значение поля типа файла не
определено), значит где-то имеется ошибка. Это может произойти, если адми-
нистратор смонтировал файловую систему, которая отформатирована неправильно.
Ядро обращается к тем дисковым блокам, которые, как кажется ядру, содержат
индексы, но в действительности оказывается, что они содержат данные.
Если номер индекса присутствует в записи каталога, но сам индекс свобо-
ден, файловая система является несогласованной, поскольку номер индекса в
записи каталога должен быть номером назначенного индекса. Это могло бы прои-
зойти, если бы ядро, создавая новый файл и записывая на диск новую точку
входа в каталог, не успела бы скопировать на диск индекс файла из-за сбоя.
Также это может случиться, если процесс, удаляя связь файла с каталогом, за-
пишет освободившийся индекс на диск, но не успеет откорректировать каталог
из-за сбоя. Возникновение подобных ситуаций можно предотвратить, копируя на
диск результаты работы в надлежащем порядке.
Если число свободных блоков или свободных индексов, записанное в суперб-
локе, не совпадает с их количеством на диске, файловая система так же явля-
ется несогласованной. Итоговая информация в суперблоке всегда должна соот-
ветствовать информации о текущем состоянии файловой системы.
Этой главой завершается первая часть книги, посвященная рассмотрению
особенностей файловой системы. Глава познакомила пользователя с тремя табли-
цами, принадлежащими ядру: таблицей пользовательских дескрипторов файла,
системной таблицей файлов и таблицей монтирования. В ней рассмотрены алго-
ритмы выполнения системных функций, имеющих отношение к файловой системе, и
взаимодействие между этими функциями. Исследованы некоторые абстрактные
свойства файловой системы, позволяющие системе UNIX поддерживать файловые
системы различных типов. Наконец, описан механизм выполнения команды fsck,
контролирующей целостность и согласованность данных в файловой системе.
1. Рассмотрим программу, приведенную на Рисунке 5.35. Какое значение воз-
вращает каждая операция read и что при этом содержится в буфере ? Опи-
131
шите, что происходит в ядре во время выполнения каждого вызова read.
2. Вновь вернемся к программе на Рисунке 5.35 и предположим, что оператор
lseek(fd,9000L,0); стоит перед первым обращением к функции read. Что
ищет процесс и что при этом происходит в ядре ?
3. Процесс может открыть файл для работы в режиме добавления записей в
конец файла, при этом имеется в виду, что каждая операция записи рас-
полагает данные по адресу смещения, указывающего текущий конец файла.
Таким образом, два процесса могут открыть файл для работы в режиме до-
бавления записей в конец файла и вводить данные, не опасаясь затереть
записи друг другу. Что произойдет, если процесс откроет файл в режиме
добавления в конец, а записывающую головку установит на начало файла ?
4. Библиотека стандартных подпрограмм ввода-вывода повышает эффективность
выполнения пользователем операций чтения и записи благодаря буфериза-
ции данных в библиотеке и сохранению большого количества модулей обра-
щения к операционной системе, необходимых пользователю. Как бы вы реа-
лизовали библиотечные функции fread и fwrite ? Что должны делать биб-
лиотечные функции fopen и fclose ?
+------------------------------------------------------------+
| #include |
| main() |
| { |
| int fd; |
| char buf[1024]; |
| fd = creat("junk",0666); |
| lseek(fd,2000L,2); /* ищется байт с номером 2000 */ |
| write(fd,"hello",5); |
| close(fd); |
| |
| fd = open("junk",O_RDONLY); |
| read(fd,buf,1024); /* читает нули */ |
| read(fd,buf,1024); /* считывает нечто, отличное от 0 */|
| read(fd,buf,1024); |
| } |
+------------------------------------------------------------+
Рисунок 5.35. Считывание нулей и конца файла
5. Если процесс читает данные из файла последовательно, ядро запоминает
значение блока, прочитанного с продвижением, в индексе, хранящемся в
памяти. Что произойдет, если несколько процессов будут одновременно
вести последовательное считывание данных из одного и того же файла ?
+---------------------------------------------------------+
| #include |
| main() |
| { |
| int fd; |
| char buf[256]; |
| |
| fd = open("/etc/passwd",O_RDONLY); |
| if (read(fd,buf,1024) < 0) |
| printf("чтение завершается неудачно\n"); |
| } |
+---------------------------------------------------------+
Рисунок 5.36. Чтение большой порции данных в маленький буфер
132
6. Рассмотрим программу, приведенную на Рисунке 5.36. Что произойдет в
результате выполнения программы ? Обоснуйте ответ. Что произошло бы,
если бы объявление массива buf было вставлено между объявлениями двух
других массивов размером 1024 элемента каждый ? Каким образом ядро ус-
танавливает, что прочитанная порция данных слишком велика для буфера ?
*7. В файловой системе BSD разрешается фрагментировать последний блок фай-
ла в соответствии со следующими правилами:
* Свободные фрагменты отслеживаются в структурах, подобных суперблоку;
* Ядро не поддерживает пул ранее выделенных свободных фрагментов, а
разбивает на фрагменты в случае необходимости свободный блок;
* Ядро может назначать фрагменты блока только для последнего блока в
файле;
* Если блок разбит на несколько фрагментов, ядро может назначить их
различным файлам;
* Количество фрагментов в блоке не должно превышать величину, фиксиро-
ванную для данной файловой системы;
* Ядро назначает фрагменты во время выполнения системной функции
write.
Разработайте алгоритм, присоединяющий к файлу фрагменты блока. Какие
изменения должны быть сделаны в индексе, чтобы позволить использование
фрагментов ? Какие преимущества с системной точки зрения предоставляет
использование фрагментов для тех файлов, которые используют блоки кос-
венной адресации ? Не выгоднее ли было бы назначать фрагменты во время
выполнения функции close вместо того, чтобы назначать их при выполне-
нии функции write ?
*8. Вернемся к обсуждению, начатому в главе 4 и касающемуся расположения
данных в индексе файла. Для того случая, когда индекс имеет размер
дискового блока, разработайте алгоритм, по которому остаток данных
файла переписывается в индексный блок, если помещается туда. Сравните
этот метод с методом, предложенным для решения предыдущей проблемы.
*9. В версии V системы функция fcntl используется для реализации механизма
захвата файла и записи и имеет следующий формат: fcntl(fd,cmd,arg);
где fd - дескриптор файла, cmd - тип блокирующей операции, а в arg
указываются различные параметры, такие как тип блокировки (записи или
чтения) и смещения в байтах (см. приложение). К блокирующим операциям
относятся
* Проверка наличия блокировок, принадлежащих другим процессам, с не-
медленным возвратом управления в случае обнаружения таких блокиро-
вок,
* Установка блокировки и приостанов до успешного завершения,
* Установка блокировки с немедленным возвратом управления в случае не-
удачи.
Ядро автоматически снимает блокировки, установленные процессом, при
закрытии файла. Опишите работу алгоритма, реализующего захват файла и
записи. Если блокировки являются обязательными, другим процессам сле-
дует запретить доступ к файлу. Какие изменения следует сделать в опе-
рациях чтения и записи ?
*10. Если процесс приостановил свою работу в ожидании снятия с файла блоки-
ровки, возникает опасность взаимной блокировки: процесс A может забло-
кировать файл "one" и попытаться заблокировать файл "two", а процесс B
может заблокировать файл "two" и попытаться заблокировать файл "one".
Оба процесса перейдут в состояние, при котором они не смогут продол-
жить свою работу. Расширьте алгоритм решения предыдущей проблемы таким
образом, чтобы ядро могло обнаруживать ситуации взаимной блокировки и
прерывать выполнение системных функций. Следует ли поручать обнаруже-
ние взаимных блокировок ядру ?
11. До существования специальной системной функции захвата файла пользова-
тить файловую систему программой fsck, потребовались бы большие усилия. Од-
нако, если система сначала переписала индекс на диск, а потом дала сбой,
пользователь не заметит каких-либо искажений в файловой системе после пере-
загрузки. Информационные блоки, ранее принадлежавшие файлу, станут недоступ-
ны для системы, но каких-нибудь явных изменений при этом пользователи не
увидят. Программе fsck так же было бы проще забрать назад освободившиеся
после удаления связи дисковые блоки, нежели производить очистку, необходимую
в первом из рассматриваемых случаев.
Поводов для конкуренции при выполнении системной функции unlink очень
много, особенно при удалении имен каталогов. Команда rmdir удаляет каталог,
убедившись предварительно в том, что в каталоге отсутствуют файлы (она счи-
тывает каталог и проверяет значения индексов во всех записях каталога на ра-
венство нулю). Но так как команда rmdir запускается на пользовательском
уровне, действия по проверке содержимого каталога и удаления каталога выпол-
няются не так уж просто; система должна переключать контекст между выполне-
нием функций read и unlink. Однако, после того, как команда rmdir обнаружи-
ла, что каталог пуст, другой процесс может предпринять попытку создать файл
в каталоге функцией creat. Избежать этого пользователи могут только путем
использования механизма захвата файла и записи. Тем не менее, раз процесс
приступил к выполнению функции unlink, никакой другой процесс не может обра-
титься к файлу с удаляемой связью, поскольку индексы родительского каталога
и файла заблокированы.
Обратимся еще раз к алгоритму функции link и посмотрим, каким образом
система снимает с индекса блокировку до завершения выполнения функции. Если
бы другой процесс удалил связь файла пока его индекс свободен, он бы тем са-
мым только уменьшил значение счетчика связей; так как значение счетчика свя-
зей было увеличено перед удалением связи, это значение останется положитель-
ным. Следовательно, файл не может быть удален и система работает надежно.
Эта ситуация аналогична той, когда функция unlink вызывается сразу после за-
вершения выполнения функции link.
Другой повод для конкуренции имеет место в том случае, когда один про-
цесс преобразует имя пути поиска файла в индекс файла по алгоритму namei, а
другой процесс удаляет каталог, имя которого входит в путь поиска. Допустим,
процесс A делает разбор имени "a/ b/c/d" и приостанавливается во время полу-
чения индекса для файла "c". Он может приостановиться при попытке заблокиро-
вать индекс или при попытке обратиться к дисковому блоку, где этот индекс
хранится (см. алгоритмы iget и bread). Если процессу B нужно удлить связь
для каталога с именем "c", он может приостановиться по той же самой причине,
что и процесс A. Пусть ядро впоследствии решит возобновить процесс B раньше
процесса A. Прежде чем процесс A продолжит свое выполнение, процесс B завер-
шится, удалив связь каталога "c" и его содержимое по этой связи. Позднее,
процесс A попытается обратиться к несуществующему индексу, который уже был
удален. Алгоритм namei, проверяющий в первую очередь неравенство значения
счетчика связей нулю, сообщит об ошибке.
Такой проверки, однако, не всегда достаточно, поскольку можно предполо-
жить, что какой-нибудь другой процесс создаст в любом месте файловой системы
новый каталог и получит тот индекс, который ранее использовался для "c".
126
Процесс A будет заблуждаться, думая, что он обратился к нужному индексу (см.
Рисунок 5.32). Как бы то ни было, система сохраняет свою целостность; самое
худшее, что может произойти, это обращение не к тому файлу - с возможным на-
Процесс A Процесс B Процесс C
+------------------------------------------------------------
| - Удаляется связь фай- -
| - ла с именем "с" -
| - -
| - Обнаруживает, что -
| - индекс файла "c" -
| - заблокирован -
| - Приостанавливает -
| - выполнение -
| - - -
| Просматривает ка- - -
| талог "b" в поис- - -
| ках имени "c" - -
| Получает номер ин- - -
| декса для "c" - -
| Обнаруживает, что - -
| индекс файла "c" - -
| заблокирован - -
| Приостанавливает - -
| выполнение - -
| - - -
| - Возобновляет выпол- -
| - нение, индекс "c" -
| - свободен -
| - Удаляет связь с име- -
| - нем "c", прежний ин- -
| - декс освобождается, -
| - если число связей =0 -
| - - -
| - - Назначает индекс
| - - новому файлу "n"
| - - Случайно назнача-
| - - ет ему индекс, ра-
| - - нее принадлежавший
| - - "c"
| - -
| - - В конечном итоге
| - - снимает блокировку
| - - с индекса "n"
| - -
| Возобновляет выпол- -
| нение, прежний ин- -
| декс "c" (теперь -
| "n") свободен -
| Получает индекс "n" -
| Просматривает ка- -
| талог "n" в поис- -
| ках имени "d" -
v
Время
Рисунок 5.32. Соперничество процессов за индекс при выполне-
нии функции unlink
127
+------------------------------------------------------------+
| #include
| #include
| #include
| |
| main(argc,argv) |
| int argc; |
| char *argv[]; |
| { |
| int fd; |
| char buf[1024]; |
| struct stat statbuf; |
| |
| if (argc != 2) /* нужен параметр */ |
| exit(); |
| fd = open(argv[1],O_RDONLY); |
| if (fd == -1) /* open завершилась |
| неудачно */ |
| exit(); |
| if (unlink(argv[1]) == -1) /* удалить связь с только |
| что открытым файлом */ |
| exit(); |
| if (stat(argv[1],&statbuf) == -1) /* узнать состоя- |
| ние файла по имени */ |
| printf("stat %s завершилась неудачно\n",argv[1]);|
| /* как и следовало бы */ |
| else |
| printf("stat %s завершилась успешно!\n",argv[1]);|
| if (fstat(fd,&statbuf) == -1) /* узнать состояние |
| файла по идентификатору */ |
| printf("fstat %s сработала неудачно!\n",argv[1]);|
| else |
| printf("fstat %s завершилась успешно\n",argv[1]);|
| /* как и следовало бы */ |
| while (read(fd,buf,sizeof(buf)) > 0) /* чтение откры- |
| того файла с удаленной связью */ |
| printf("%1024s",buf); /* вывод на печать поля |
| размером 1 Кбайт */ |
| } |
+------------------------------------------------------------+
Рисунок 5.33. Удаление связи с открытым файлом
рушением защиты - но соперничества такого рода на практике довольно редки.
Процесс может удалить связь файла в то время, как другому процессу нуж-
но, чтобы файл оставался открытым. (Даже процесс, удаляющий связь, может
быть процессом, выполнившим это открытие). Поскольку ядро снимает с индекса
блокировку по окончании выполнения функции open, функция unlink завершится
успешно. Ядро будет выполнять алгоритм unlink точно так же, как если бы файл
не был открыт, и удалит из каталога запись о файле. Теперь по имени удален-
ной связи к файлу не сможет обратиться никакой другой процесс. Однако, так
как системная функция open увеличила значение счетчика ссылок в индексе, яд-
ро не очищает содержимое файла при выполнении алгоритма iput перед заверше-
нием функции unlink. Поэтому процесс, открывший файл, может производить над
файлом все обычные действия по его дескриптору, включая чтение из файла и
запись в файл. Но когда процесс закрывает файл, значение счетчика ссылок в
алгоритме iput становится равным 0, и ядро очищает содержимое файла. Короче
говоря, процесс, открывший файл, продолжает работу так, как если бы функция
128
unlink не выполнялась, а unlink, в свою очередь, работает так, как если бы
файл не был открыт. Другие системные функции также могут продолжать выпол-
няться в процессе, открывшем файл.
В приведенном на Рисунке 5.33 примере процесс открывает файл, указанный
в качестве параметра, и затем удаляет связь только что открытого файла. Фун-
кция stat завершится неудачно, поскольку первоначальное имя после unlink
больше не указывает на файл (предпо-
лагается, что тем временем никакой другой процесс не создал файл с тем же
именем), но функция fstat завершится успешно, так как она выбирает индекс по
дескриптору файла. Процесс выполняет цикл, считывая на каждом шаге по 1024
байта и пересылая файл в стандартный вывод. Когда при чтении будет обнаружен
конец файла, процесс завершает работу: после завершения процесса файл перес-
тает существовать. Процессы часто создают временные файлы и сразу же удаляют
связь с ними; они могут продолжать ввод-вывод в эти файлы, но имена файлов
больше не появляются в иерархии каталогов. Если процесс по какой-либо причи-
не завершается аварийно, он не оставляет от временных файлов никакого следа.
Уайнбергером было введено понятие "тип файловой системы" для объяснения
механизма работы принадлежавшей ему сетевой файловой системы (см. краткое
описание этого механизма в [Killian 84]) и в позднейшей версии системы V
поддерживаются основополагающие принципы его схемы. Наличие типа файловой
системы дает ядру возможность поддерживать одновременно множество файловых
систем, таких как сетевые файловые системы (глава 13) или даже файловые сис-
темы из других операционных систем. Процессы пользуются для обращения к фай-
лам обычными функциями системы UNIX, а ядро устанавливает соответствие между
общим набором файловых операций и операциями, специфичными для каждого типа
файловой системы.
Операции файловой Общие индексы Индекс файловой
системы системы версии V
+---------------+ +------+ +-------+
Версия V | open | +-----+- -+-------->| |
| close | | +------+ +-------+
| read | | +---+- -+---+ | |
| write |<---+ | +------+ | +-------+
| - |<-----|---+- -+---|---->| |
| - | | +------+ | +-------+
| - | | | | | | - |
| - | | +------+ | | - |
+---------------+ | | | | | - |
Удаленная | ropen | | +------+ | +-------+
система | rclose | | | - | |
| rread | | | - | | Индекс удален-
| rwrite |<-----+ | - | | ной системы
| - | | - | | +-------+
| - | | - | | | |
| - | | - | | +-------+
| - | | - | +---->| |
+---------------+ | - | +-------+
| - | | - | | |
| - | | - | +-------+
| - | | - | | |
| - | | - | +-------+
| - | | - | | - |
+---------------+ +------+ +-------+
Рисунок 5.34. Индексы для файловых систем различных типов
129
Индекс выступает интерфейсом между абстрактной файловой системой и от-
дельной файловой системой. Общая копия индекса в памяти содержит информацию,
не зависящую от отдельной файловой системы, а также указатель на частный ин-
декс файловой системы, который уже содержит информацию, специфичную для нее.
Частный индекс файловой системы содержит такую информацию, как права доступа
и расположение блоков, а общий индекс содержит номер устройства, номер ин-
декса на диске, тип файла, размер, информацию о владельце и счетчик ссылок.
Другая частная информация, описывающая отдельную файловую систему, содержит-
ся в суперблоке и структуре каталогов. На Рисунке 5.34 изображены таблица
общих индексов в памяти и две таблицы частных индексов отдельных файловых
систем, одна для структур файловой системы версии V, а другая для индекса
удаленной (сетевой) системы. Предполагается, что последний индекс содержит
достаточно информации для того, чтобы идентифицировать файл, находящийся в
удаленной системе. У файловой системы может отсутствовать структура, подоб-
ная индексу; но исходный текст программ отдельной файловой системы позволяет
создать объектный код, удовлетворяющий семантическим требованиям файловой
системы UNIX и назначающий свой "индекс", который соответствует общему ин-
дексу, назначаемому ядром.
Файловая система каждого типа имеет некую структуру, в которой хранятся
адреса функций, реализующих абстрактные действия. Когда ядру нужно обратить-
ся к файлу, оно вызывает косвенную функцию в зависимости от типа файловой
системы и абстрактного действия (см. Рисунок 5.34). Примерами абстрактных
действий являются: открытие и закрытие файла, чтение и запись данных, возв-
ращение индекса для компоненты имени файла (подобно namei и iget), освобож-
дение индекса (подобно iput), коррекция индекса, проверка прав доступа, ус-
тановка атрибутов файла (прав доступа к нему), а также монтирование и демон-
тирование файловых систем. В главе 13 будет проиллюстрировано использование
системных абстракций при рассмотрении распределенной файловой системы.
Ядро поддерживает целостность системы в своей обычной работе. Тем не ме-
нее, такие чрезвычайные обстоятельства, как отказ питания, могут привести к
фатальному сбою системы, в результате которого содержимое системы утрачивает
свою согласованность: большинство данных в файловой системе доступно для ис-
пользования, но некоторая несогласованность между ними имеет место. Команда
fsck проверяет согласованность данных и в случае необходимости вносит в фай-
ловую систему исправления. Она обращается к файловой системе через блочный
или строковый интерфейс (глава 10) в обход традиционных методов доступа к
файлам. В этом разделе рассматриваются некоторые примеры противоречивости
данных, которая обнаруживается командой fsck.
Дисковый блок может принадлежать более чем одному индексу или списку
свободных блоков. Когда файловая система открывается в первый раз, все дис-
ковые блоки находятся в списке свободных блоков. Когда дисковый блок выбира-
ется для использования, ядро удаляет его номер из списка свободных блоков и
назначает блок индексу. Ядро не может переназначить дисковый блок другому
индексу до тех пор, пока блок не будет возвращен в список свободных блоков.
Таким образом, дисковый блок может либо находиться в списке свободных бло-
ков, либо быть назначенным одному из индексов. Рассмотрим различные ситуа-
ции, могущие иметь место при освобождении ядром дискового блока, принадле-
жавшего файлу, с возвращением номера блока в суперблок, находящийся в памя-
ти, и при выделении дискового блока новому файлу. Если ядро записывало на
диск индекс и блоки нового файла, но перед внесением изменений в индекс
прежнего файла на диске произошел сбой, оба индекса будут адресовать к одно-
130
му и тому же номеру дискового блока. Подобным же образом, если ядро перепи-
сывало на диск суперблок и его списки свободных ресурсов и перед переписью
старого индекса случился сбой, дисковый блок появится одновременно и в спис-
ке свободных блоков, и в старом индексе.
Если блок отсутствует как в списке свободных блоков, так и в файле, фай-
ловая система является несогласованной, ибо, как уже говорилось выше, все
блоки обязаны где-нибудь присутствовать. Такая ситуация могла бы произойти,
если бы блок был удален из файла и помещен в список свободных блоков в су-
перблоке. Если производилась запись прежнего файла на диск и система дала
сбой перед записью суперблока, блок будет отсутствовать во всех списках,
хранящихся на диске.
Индекс может иметь счетчик связей с ненулевым значением при том, что его
номер отсутствует во всех каталогах файловой системы. Все файлы, за исключе-
нием каналов (непоименованных), должны присутствовать в древовидной структу-
ре файловой системы. Если система дала сбой после создания канала или обыч-
ного файла, но перед созданием соответствующей этому каналу или файлу точки
входа в каталог, индекс будет иметь в поле счетчика связей установленное
значение, пусть даже он явно не присутствует в файловой системе. Еще одна
проблема может возникнуть, если с помощью функции unlink была удалена связь
каталога без проверки удаления из каталога всех содержащихся в нем связей с
отдельными файлами.
Если формат индекса неверен (например, если значение поля типа файла не
определено), значит где-то имеется ошибка. Это может произойти, если адми-
нистратор смонтировал файловую систему, которая отформатирована неправильно.
Ядро обращается к тем дисковым блокам, которые, как кажется ядру, содержат
индексы, но в действительности оказывается, что они содержат данные.
Если номер индекса присутствует в записи каталога, но сам индекс свобо-
ден, файловая система является несогласованной, поскольку номер индекса в
записи каталога должен быть номером назначенного индекса. Это могло бы прои-
зойти, если бы ядро, создавая новый файл и записывая на диск новую точку
входа в каталог, не успела бы скопировать на диск индекс файла из-за сбоя.
Также это может случиться, если процесс, удаляя связь файла с каталогом, за-
пишет освободившийся индекс на диск, но не успеет откорректировать каталог
из-за сбоя. Возникновение подобных ситуаций можно предотвратить, копируя на
диск результаты работы в надлежащем порядке.
Если число свободных блоков или свободных индексов, записанное в суперб-
локе, не совпадает с их количеством на диске, файловая система так же явля-
ется несогласованной. Итоговая информация в суперблоке всегда должна соот-
ветствовать информации о текущем состоянии файловой системы.
Этой главой завершается первая часть книги, посвященная рассмотрению
особенностей файловой системы. Глава познакомила пользователя с тремя табли-
цами, принадлежащими ядру: таблицей пользовательских дескрипторов файла,
системной таблицей файлов и таблицей монтирования. В ней рассмотрены алго-
ритмы выполнения системных функций, имеющих отношение к файловой системе, и
взаимодействие между этими функциями. Исследованы некоторые абстрактные
свойства файловой системы, позволяющие системе UNIX поддерживать файловые
системы различных типов. Наконец, описан механизм выполнения команды fsck,
контролирующей целостность и согласованность данных в файловой системе.
1. Рассмотрим программу, приведенную на Рисунке 5.35. Какое значение воз-
вращает каждая операция read и что при этом содержится в буфере ? Опи-
131
шите, что происходит в ядре во время выполнения каждого вызова read.
2. Вновь вернемся к программе на Рисунке 5.35 и предположим, что оператор
lseek(fd,9000L,0); стоит перед первым обращением к функции read. Что
ищет процесс и что при этом происходит в ядре ?
3. Процесс может открыть файл для работы в режиме добавления записей в
конец файла, при этом имеется в виду, что каждая операция записи рас-
полагает данные по адресу смещения, указывающего текущий конец файла.
Таким образом, два процесса могут открыть файл для работы в режиме до-
бавления записей в конец файла и вводить данные, не опасаясь затереть
записи друг другу. Что произойдет, если процесс откроет файл в режиме
добавления в конец, а записывающую головку установит на начало файла ?
4. Библиотека стандартных подпрограмм ввода-вывода повышает эффективность
выполнения пользователем операций чтения и записи благодаря буфериза-
ции данных в библиотеке и сохранению большого количества модулей обра-
щения к операционной системе, необходимых пользователю. Как бы вы реа-
лизовали библиотечные функции fread и fwrite ? Что должны делать биб-
лиотечные функции fopen и fclose ?
+------------------------------------------------------------+
| #include
| main() |
| { |
| int fd; |
| char buf[1024]; |
| fd = creat("junk",0666); |
| lseek(fd,2000L,2); /* ищется байт с номером 2000 */ |
| write(fd,"hello",5); |
| close(fd); |
| |
| fd = open("junk",O_RDONLY); |
| read(fd,buf,1024); /* читает нули */ |
| read(fd,buf,1024); /* считывает нечто, отличное от 0 */|
| read(fd,buf,1024); |
| } |
+------------------------------------------------------------+
Рисунок 5.35. Считывание нулей и конца файла
5. Если процесс читает данные из файла последовательно, ядро запоминает
значение блока, прочитанного с продвижением, в индексе, хранящемся в
памяти. Что произойдет, если несколько процессов будут одновременно
вести последовательное считывание данных из одного и того же файла ?
+---------------------------------------------------------+
| #include
| main() |
| { |
| int fd; |
| char buf[256]; |
| |
| fd = open("/etc/passwd",O_RDONLY); |
| if (read(fd,buf,1024) < 0) |
| printf("чтение завершается неудачно\n"); |
| } |
+---------------------------------------------------------+
Рисунок 5.36. Чтение большой порции данных в маленький буфер
132
6. Рассмотрим программу, приведенную на Рисунке 5.36. Что произойдет в
результате выполнения программы ? Обоснуйте ответ. Что произошло бы,
если бы объявление массива buf было вставлено между объявлениями двух
других массивов размером 1024 элемента каждый ? Каким образом ядро ус-
танавливает, что прочитанная порция данных слишком велика для буфера ?
*7. В файловой системе BSD разрешается фрагментировать последний блок фай-
ла в соответствии со следующими правилами:
* Свободные фрагменты отслеживаются в структурах, подобных суперблоку;
* Ядро не поддерживает пул ранее выделенных свободных фрагментов, а
разбивает на фрагменты в случае необходимости свободный блок;
* Ядро может назначать фрагменты блока только для последнего блока в
файле;
* Если блок разбит на несколько фрагментов, ядро может назначить их
различным файлам;
* Количество фрагментов в блоке не должно превышать величину, фиксиро-
ванную для данной файловой системы;
* Ядро назначает фрагменты во время выполнения системной функции
write.
Разработайте алгоритм, присоединяющий к файлу фрагменты блока. Какие
изменения должны быть сделаны в индексе, чтобы позволить использование
фрагментов ? Какие преимущества с системной точки зрения предоставляет
использование фрагментов для тех файлов, которые используют блоки кос-
венной адресации ? Не выгоднее ли было бы назначать фрагменты во время
выполнения функции close вместо того, чтобы назначать их при выполне-
нии функции write ?
*8. Вернемся к обсуждению, начатому в главе 4 и касающемуся расположения
данных в индексе файла. Для того случая, когда индекс имеет размер
дискового блока, разработайте алгоритм, по которому остаток данных
файла переписывается в индексный блок, если помещается туда. Сравните
этот метод с методом, предложенным для решения предыдущей проблемы.
*9. В версии V системы функция fcntl используется для реализации механизма
захвата файла и записи и имеет следующий формат: fcntl(fd,cmd,arg);
где fd - дескриптор файла, cmd - тип блокирующей операции, а в arg
указываются различные параметры, такие как тип блокировки (записи или
чтения) и смещения в байтах (см. приложение). К блокирующим операциям
относятся
* Проверка наличия блокировок, принадлежащих другим процессам, с не-
медленным возвратом управления в случае обнаружения таких блокиро-
вок,
* Установка блокировки и приостанов до успешного завершения,
* Установка блокировки с немедленным возвратом управления в случае не-
удачи.
Ядро автоматически снимает блокировки, установленные процессом, при
закрытии файла. Опишите работу алгоритма, реализующего захват файла и
записи. Если блокировки являются обязательными, другим процессам сле-
дует запретить доступ к файлу. Какие изменения следует сделать в опе-
рациях чтения и записи ?
*10. Если процесс приостановил свою работу в ожидании снятия с файла блоки-
ровки, возникает опасность взаимной блокировки: процесс A может забло-
кировать файл "one" и попытаться заблокировать файл "two", а процесс B
может заблокировать файл "two" и попытаться заблокировать файл "one".
Оба процесса перейдут в состояние, при котором они не смогут продол-
жить свою работу. Расширьте алгоритм решения предыдущей проблемы таким
образом, чтобы ядро могло обнаруживать ситуации взаимной блокировки и
прерывать выполнение системных функций. Следует ли поручать обнаруже-
ние взаимных блокировок ядру ?
11. До существования специальной системной функции захвата файла пользова-