рава доступа и расположение блоков, а общий индекс содержит номер устройства, номер ин- декса на диске, тип файла, размер, информацию о владельце и счетчик ссылок. Другая частная информация, описывающая отдельную файловую систему, содержит- ся в суперблоке и структуре каталогов. На Рисунке 5.34 изображены таблица общих индексов в памяти и две таблицы частных индексов отдельных файловых систем, одна для структур файловой системы версии V, а другая для индекса удаленной (сетевой) системы. Предполагается, что последний индекс содержит достаточно информации для того, чтобы идентифицировать файл, находящийся в удаленной системе. У файловой системы может отсутствовать структура, подоб- ная индексу; но исходный текст программ отдельной файловой системы позволяет создать объектный код, удовлетворяющий семантическим требованиям файловой системы UNIX и назначающий свой "индекс", который соответствует общему ин- дексу, назначаемому ядром. Файловая система каждого типа имеет некую структуру, в которой хранятся адреса функций, реализующих абстрактные действия. Когда ядру нужно обратить- ся к файлу, оно вызывает косвенную функцию в зависимости от типа файловой системы и абстрактного действия (см. Рисунок 5.34). Примерами абстрактных действий являются: открытие и закрытие файла, чтение и запись данных, возв- ращение индекса для компоненты имени файла (подобно namei и iget), освобож- дение индекса (подобно iput), коррекция индекса, проверка прав доступа, ус- тановка атрибутов файла (прав доступа к нему), а также монтирование и демон- тирование файловых систем. В главе 13 будет проиллюстрировано использование системных абстракций при рассмотрении распределенной файловой системы. 5.18 СОПРОВОЖДЕНИЕ ФАЙЛОВОЙ СИСТЕМЫ Ядро поддерживает целостность системы в своей обычной работе. Тем не ме- нее, такие чрезвычайные обстоятельства, как отказ питания, могут привести к фатальному сбою системы, в результате которого содержимое системы утрачивает свою согласованность: большинство данных в файловой системе доступно для ис- пользования, но некоторая несогласованность между ними имеет место. Команда fsck проверяет согласованность данных и в случае необходимости вносит в фай- ловую систему исправления. Она обращается к файловой системе через блочный или строковый интерфейс (глава 10) в обход традиционных методов доступа к файлам. В этом разделе рассматриваются некоторые примеры противоречивости данных, которая обнаруживается командой fsck. Дисковый блок может принадлежать более чем одному индексу или списку свободных блоков. Когда файловая система открывается в первый раз, все дис- ковые блоки находятся в списке свободных блоков. Когда дисковый блок выбира- ется для использования, ядро удаляет его номер из списка свободных блоков и назначает блок индексу. Ядро не может переназначить дисковый блок другому индексу до тех пор, пока блок не будет возвращен в список свободных блоков. Таким образом, дисковый блок может либо находиться в списке свободных бло- ков, либо быть назначенным одному из индексов. Рассмотрим различные ситуа- ции, могущие иметь место при освобождении ядром дискового блока, принадле- жавшего файлу, с возвращением номера блока в суперблок, находящийся в памя- ти, и при выделении дискового блока новому файлу. Если ядро записывало на диск индекс и блоки нового файла, но перед внесением изменений в индекс прежнего файла на диске произошел сбой, оба индекса будут адресовать к одно- 130 му и тому же номеру дискового блока. Подобным же образом, если ядро перепи- сывало на диск суперблок и его списки свободных ресурсов и перед переписью старого индекса случился сбой, дисковый блок появится одновременно и в спис- ке свободных блоков, и в старом индексе. Если блок отсутствует как в списке свободных блоков, так и в файле, фай- ловая система является несогласованной, ибо, как уже говорилось выше, все блоки обязаны где-нибудь присутствовать. Такая ситуация могла бы произойти, если бы блок был удален из файла и помещен в список свободных блоков в су- перблоке. Если производилась запись прежнего файла на диск и система дала сбой перед записью суперблока, блок будет отсутствовать во всех списках, хранящихся на диске. Индекс может иметь счетчик связей с ненулевым значением при том, что его номер отсутствует во всех каталогах файловой системы. Все файлы, за исключе- нием каналов (непоименованных), должны присутствовать в древовидной структу- ре файловой системы. Если система дала сбой после создания канала или обыч- ного файла, но перед созданием соответствующей этому каналу или файлу точки входа в каталог, индекс будет иметь в поле счетчика связей установленное значение, пусть даже он явно не присутствует в файловой системе. Еще одна проблема может возникнуть, если с помощью функции unlink была удалена связь каталога без проверки удаления из каталога всех содержащихся в нем связей с отдельными файлами. Если формат индекса неверен (например, если значение поля типа файла не определено), значит где-то имеется ошибка. Это может произойти, если адми- нистратор смонтировал файловую систему, которая отформатирована неправильно. Ядро обращается к тем дисковым блокам, которые, как кажется ядру, содержат индексы, но в действительности оказывается, что они содержат данные. Если номер индекса присутствует в записи каталога, но сам индекс свобо- ден, файловая система является несогласованной, поскольку номер индекса в записи каталога должен быть номером назначенного индекса. Это могло бы прои- зойти, если бы ядро, создавая новый файл и записывая на диск новую точку входа в каталог, не успела бы скопировать на диск индекс файла из-за сбоя. Также это может случиться, если процесс, удаляя связь файла с каталогом, за- пишет освободившийся индекс на диск, но не успеет откорректировать каталог из-за сбоя. Возникновение подобных ситуаций можно предотвратить, копируя на диск результаты работы в надлежащем порядке. Если число свободных блоков или свободных индексов, записанное в суперб- локе, не совпадает с их количеством на диске, файловая система так же явля- ется несогласованной. Итоговая информация в суперблоке всегда должна соот- ветствовать информации о текущем состоянии файловой системы. 5.19 ВЫВОДЫ Этой главой завершается первая часть книги, посвященная рассмотрению особенностей файловой системы. Глава познакомила пользователя с тремя табли- цами, принадлежащими ядру: таблицей пользовательских дескрипторов файла, системной таблицей файлов и таблицей монтирования. В ней рассмотрены алго- ритмы выполнения системных функций, имеющих отношение к файловой системе, и взаимодействие между этими функциями. Исследованы некоторые абстрактные свойства файловой системы, позволяющие системе UNIX поддерживать файловые системы различных типов. Наконец, описан механизм выполнения команды fsck, контролирующей целостность и согласованность данных в файловой системе. 5.20 УПРАЖНЕНИЯ 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. До существования специальной системной функции захвата файла пользова- телям приходилось прибегать к услугам параллельно действующих процес- 133 сов для реализации механизма захвата путем вызова системных функций, выполняющих элементарные действия. Какие из системных функций, описан- ных в этой главе, могли бы использоваться ? Какие опасности подстере- гают при использовании этих методов ? 12. Ричи заявлял (см. [Ritchie 81]), что захвата файла недостаточно для того, чтобы предотвратить путаницу, вызываемую такими программами, как редакторы, которые создают копию файла при редактировании и переписы- вают первоначальный файл по окончании работы. Объясните, что он имел в виду, и прокомментируйте. 13. Рассмотрим еще один способ блокировки файлов, предотвращающий разруши- тельные последствия корректировки. Предположим, что в индексе содер- жится новая установка прав доступа, позволяющая только одному процессу в текущий момент открывать файл для записи и нескольким процессам отк- рывать файл для чтения. Опишите реализацию этого способа. +----------------------------------------------------------+ | main(argc,argv) | | int argc; | | char *argv[]; | | { | | if (argc != 2) | | { | | printf("введите: команда имя каталога\n"); | | exit(); | | } | | | | /* права доступа к каталогу: запись, чтение и ис- | | полнение разрешены для всех */ | | /* только суперпользователь может делать следую- | | щее */ | | if (mknod(argv[1],040777,0) == -1) | | printf("mknod завершилась неудачно\n"); | | } | +----------------------------------------------------------+ Рисунок 5.37. Каталог, создание которого не завершено *14. Рассмотрим программу (Рисунок 5.37), которая создает каталог с невер- ным форматом (в каталоге отсутствуют записи с именами "." и ".."). Попробуйте, находясь в этом каталоге, выполнить несколько команд, та- ких как ls -l, ls -ld, или cd. Что произойдет при этом ? 15. Напишите программу, которая выводит для файлов, имена которых указаны в качестве параметров, информацию о владельце, типе файла, правах дос- тупа и времени доступа. Если файл (параметр) является каталогом, прог- рамма должна читать записи из каталога и выводить вышеуказанную инфор- мацию для всех файлов в каталоге. 16. Предположим, что у пользователя есть разрешение на чтение из каталога, но нет разрешения на исполнение. Что произойдет, если каталог исполь- зовать в качестве параметра команды ls, заданной с опцией "-i" ? Что будет, если указана опция "-l" ? Поясните свои ответы. Ответьте на вопрос, сформулированный для случая, когда есть разрешение на исполне- ние, но нет разрешения на чтение из каталога. 17. Сравните права доступа, которые должны быть у процесса для выполнения следующих действий, и прокомментируйте: * Для создания нового файла требуется разрешение на запись в каталог. * Для "создания" существующего файла требуется разрешение на запись в файл. * Для удаления связи файла с каталогом требуется разрешение на запись 134 в каталог, а не в файл. *18. Напишите программу, которая навещает все каталоги, начиная с текущего. Как она должна управлять циклами в иерархии каталогов ? 19. Выполните программу, приведенную на Рисунке 5.38, и объясните, что при этом происходит в ядре. (Намек: выполните команду pwd, когда программа закончится). 20. Напишите программу, которая заменяет корневой каталог указанным ката- логом, и исследуйте дерево каталогов, доступное для этой программы. 21. Почему процесс не может отменить предыдущий вызов функции chroot ? Из- мените конкретную реализацию процесса таким образом, чтобы он мог ме- нять текущее значение корня на предыдущее. Какие у этой возможности преимущества и неудобства ? 22. Рассмотрим простой пример канала (Рисунок 5.19), когда процесс записы- вает в канал строку "hello" и затем считывает +----------------------------------------------------------+ | main(argc,argv) | | int argc; | | char *argv[]; | | { | | if (argc != 2) | | { | | printf("нужен 1 аргумент - имя каталога\n"); | | exit(); | | } | | | | if (chdir(argv[1]) == -1) | | printf("%s файл не является каталогом\n",argv[1]);| | } | +----------------------------------------------------------+ Рисунок 5.38. Пример программы с использованием функции chdir ее. Что произошло бы, если бы массив для записи данных в канал имел размер 1024 байта вместо 6 (а объем считываемых за одну операцию дан- ных оставался равным 6) ? Что произойдет, если порядок вызова функций read и write в программе изменить, поменяв функции местами ? 23. Что произойдет при выполнении программы, иллюстрирующей использование поименованных каналов (Рисунок 5.19), если функция mknod обнаружит, что канал с таким именем уже существует ? Как этот момент реализуется ядром ? Что произошло бы, если бы вместо подразумеваемых в тексте программы одного считывающего и одного записывающего процессов связь между собой через канал попытались установить несколько считывающих и записывающих процессов ? Как в этом случае гарантировалась бы связь одного считывающего процесса с одним записывающим процессом ? 24. Открывая поименованный канал для чтения, процесс приостанавливается до тех пор, пока еще один процесс не откроет канал для записи. Почему ? Не мог бы процесс успешно пройти функцию open, продолжить работу до того момента, когда им будет предпринята попытка чтения данных из ка- нала, и приостановиться при выполнении функции read ? 25. Как бы вы реализовали алгоритм выполнения системной функции dup2 (из версии 7), вызываемой следующим образом: dup2(oldfd,newfd); где oldfd - файловый дескриптор, который дублируется дескриптором newfd ? Что произошло бы, если бы дескриптор newfd уже принадлежал от- крытому файлу? *26. Какие последствия имело бы решение ядра позволить двум процессам од- новременно смонтировать одну и ту же файловую систему в двух точках монтирования ? 135 27. Предположим, что один процесс меняет свой текущий каталог на каталог "/mnt/a/b/c", после чего другой процесс в каталоге "/mnt" монтирует файловую систему. Завершится ли функция mount успешно ? Что произой- дет, если первый процесс выполнит команду pwd ? Ядро не позволит функ- ции mount успешно завершиться, если значение счетчика ссылок в индексе каталога "/mnt" превышает 1. Прокомментируйте этот момент. 28. При исполнении алгоритма пересечения точки монтирования по имени ".." в маршруте поиска файла ядро проверяет выполнение трех условий, свя- занных с точкой монтирования: что номер обнаруженного индекса совпада- ет с номером корневого индекса, что рабочий индекс является корнем файловой системы и что имя компоненты маршрута поиска - "..". Почему необходимо проверять выполнение всех трех условий ? Докажите, что про- верки любых двух условий недостаточно для того, чтобы разрешить про- цессу пересечь точку монтирования. 29. Если пользователь монтирует файловую систему только для чтения, ядро устанавливает соответствующий флаг в суперблоке. Как ядро может восп- репятствовать выполнению операций записи в функциях write, creat, link, unlink, chown и chmod ? Какого рода информацию записывают в фай- ловую систему все перечисленные функции ? *30. Предположим, что один процесс пытается демонтировать файловую систему, в то время как другой процесс пытается создать в файловой системе но- вый файл. Только одна из функций umount и creat выполнится успешно. Подробно рассмотрите возникшую конкуренцию. *31. Когда функция umount проверяет отсутствие в файловой системе активных файлов, возникает одна проблема, связанная с тем, что корневой индекс файловой системы, назначаемый при выполнении функции mount с помощью алгоритма iget, имеет счетчик ссылок с положительным значением. Как функция umount сможет убедиться в отсутствии активных файлов и отчи- таться перед корнем файловой системы ? Рассмотрите два случая: * функция umount освобождает корневой индекс по алгоритму iput перед проверкой активных индексов. (Как функции вернуть этот индекс обрат- но, если будут обнаружены активные файлы ?) * функция umount проверяет отсутствие активных файлов до того, как ос- вободить корневой индекс, и разрешая корневому индексу оставаться активным. (Насколько активным может быть корневой индекс ?) 32. Обратите внимание на то, что при выполнении команды ls -ld количество связей с каталогом никогда не равно 1. Почему ? 33. Как работает команда mkdir (создать новый каталог) ? (Наводящий воп- рос: какие номера по завершении выполнения команды имеют индексы для файлов "." и ".." ?) *34. Понятие "символические связи" имеет отношение к возможности указания с помощью функции link связей между файлами, принадлежащими к различным файловым системам. С файлом символической связи ассоциирован указатель нового типа; содержимым файла является имя пути поиска того файла, с которым он связан. Опишите реализацию символических связей. *35. Что произойдет, если процесс вызовет функцию unlink("."); Каким будет текущий каталог процесса ? Предполагается, что процесс об- ладает правами суперпользователя. 36. Разработайте системную функцию, которая усекает существующий файл до произвольных размеров, указанных в качестве аргумента, и опишите ее работу. Реализуйте системную функцию, которая позволяла бы пользовате- лю удалять сегмент файла, расположенный между двумя адресами, заданны- ми в виде смещений, и сжимать файл. Напишите программу, которая не вы- зывала бы эти функции, но обладала бы теми же функциональными возмож- ностями. 37. Опишите все условия, при которых счетчик ссылок в индексе может превы- шать значение 1. 38. Затрагивая тему абстрактных обращений к файловым системам, ответьте на вопрос: следует ли файловой системе каждого типа иметь личную операцию блокирования, вызываемую из общей программы, или же достаточно общей операции блокирования ? 136