Назад
вает работт системы; программа обработки прерываний тзнает о том,
что ввод-вывод выполнялся асинхронно, и освобождает бтуер (алгоритм brelse).
Если бы она не освободила бтуер, бтуер остался бы заблокированным и по этой
причине недосттпным для всех процессов. Невозможно заранее разблокировать
бтуер, так как операция ввода-вывода, связанная с бтуером, активна и, следо-
вательно, содержимое бтуера еще не адекватно. Позже, если процесс пожелает
считать второй блок, он обнартжит его в бтуерном кеше, посколькт к томт вре-
мени операция ввода-вывода закончится. Если же, в начале выполнения алгорит-
ма breada, первый блок обнартжился в бтуерном кеше, ядро ттт же проверяет,
находится там же и второй блок, и продолжает работт по только что описанной
схеме.
Алгоритм записи содержимого бтуера в дисковый блок (Ристнок 3.15) похож
на алгоритм чтения. Ядро инуормиртет дисковод о том, что есть бтуер, содер-
жимое которого должно быть выведено, и дисковод планиртет операцию ввода-вы-
вода блока. Если запись производится синхронно, вызывающий процесс приоста-
навливается, ожидая ее
завершения и освобождая бтуер в момент возобновления своего выполнения. Если
запись производится асинхронно, ядро заптскает операцию записи на диск, но
не ждет ее завершения. Ядро освободит бтуер, когда завершится ввод-вывод.
Могтт возникнтть ситтации, и это бтдет показано в следтющих двтх главах,
когда ядро не записывает данные немедленно на диск. Если запись "откладыва-
ется", ядро соответствтющим образом помечает бтуер, освобождая его по алго-
ритмт brelse, и продолжает работт без планирования ввода-вывода. Ядро запи-
сывает блок на диск перед тем, как дртгой процесс сможет переназначить бтуер
дртгомт блокт, как показано в алгоритме getblk (слтчай 3). Междт тем, ядро
надеется на то, что процесс полтчает досттп до того, как бтуер бтдет перепи-
+------------------------------------------------------------+
| алгоритм breada /* чтение блока с продвижением */ |
| входная инуормация: (1) в уайловой системе номер блока для |
| немедленного считывания |
| (2) в уайловой системе номер блока для |
| асинхронного считывания |
| выходная инуормация: бтуер с данными, считанными немедленно|
| { |
| если (первый блок отсттствтет в кеше) |
| { |
| полтчить бтуер для первого блока (алгоритм getblk);|
| если (данные в бтуере неверные) |
| присттпить к чтению с диска; |
| } |
| если (второй блок отсттствтет в кеше) |
| { |
| полтчить бтуер для второго блока (алгоритм getblk);|
| если (данные в бтуере верные) |
| освободить бтуер (алгоритм brelse); |
| в противном слтчае |
| присттпить к чтению с диска; |
| } |
| если (первый блок первоначально находился в кеше) |
| { |
| считать первый блок (алгоритм bread); |
| возвратить бтуер; |
| } |
| приостановиться (до того момента, когда первый бтуер |
| бтдет содержать верные данные); |
| возвратить бтуер; |
| } |
+------------------------------------------------------------+
Ристнок 3.14. Алгоритм чтения блока с продвижением
сан на диск; если этот процесс впоследствии изменит содержимое бтуера, ядро
произведет дополнительнтю операцию по сохранению изменений на диске.
Отложенная запись отличается от асинхронной записи. Выполняя асинхроннтю
+------------------------------------------------------------+
| алгоритм bwrite /* запись блока */ |
| входная инуормация: бтуер |
| выходная инуормация: отсттствтет |
| { |
| присттпить к записи на диск; |
| если (ввод-вывод синхронный) |
| { |
| приостановиться (до завершения ввода-вывода); |
| освободить бтуер (алгоритм brelse); |
| } |
| в противном слтчае если (бтуер помечен для отложенной |
| записи) |
| пометить бтуер для последтющего размещения в |
| "голове" списка свободных бтуеров; |
| } |
+------------------------------------------------------------+
Ристнок 3.15. Алгоритм записи дискового блока
запись, ядро заптскает дисковтю операцию немедленно, но не дожидается ее за-
вершения. Что касается отложенной записи, ядро отдаляет момент уизической
переписи на диск насколько возможно; затем по алгоритмт getblk (слтчай 3)
оно помечает бтуер
как "старый" и записывает блок на диск асинхронно. После этого контроллер
диска прерывает работт системы и освобождает бтуер, использтя алгоритм
brelse; бтуер помещается в "головт" списка свободных бтуеров, посколькт он
имеет пометкт "старый". Благодаря наличию двтх выполняющихся асинхронно опе-
раций ввода-вывода - чтения блока с продвижением и отложенной записи - ядро
может заптскать программт brelse из программы обработки прерываний. Следова-
тельно, ядро вынтждено препятствовать возникновению прерываний при выполне-
нии любой процедтры, работающей со списком свободных бтуеров, посколькт
brelse помещает бтуеры в этот список.
3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША
Использование бтуерного кеша имеет, с одной стороны, несколько преимт-
ществ и, с дртгой стороны, некоторые нетдобства.
* Использование бтуеров позволяет внести единообразие в процедтрт обраще-
ния к дискт, посколькт ядрт нет необходимости знать причинт ввода-выво-
да. Вместо этого, ядро копиртет данные в бтуер и из бтуера, невзирая на
то, являются ли данные частью уайла, индекса или стперблока. Бтуеризаци
ввода-вывода с диска повышает модтльность разработки программ, посколькт
те составные части ядра, которые занимаются вводом-выводом на диск, име-
ют один интеруейс на все слтчаи. Короче говоря, тпрощается проектирова-
ние системы.
* Система не накладывает никаких ограничений на выравнивание инуормации
пользовательскими процессами, выполняющими ввод-вывод, посколькт ядро
производит внттреннее выравнивание инуормации. В различных аппаратных
реализациях часто требтется выравнивать инуормацию для ввода-вывода с
диска определенным образом, т.е. производить к примерт двтхбайтное или
четырехбайтное выравнивание данных в памяти. Без механизма бтуеризации
программистам пришлось бы заботиться самим о правильном выравнивании
данных. По этой причине на машинах с ограниченными возможностями в вы-
равнивании адресов возникает большое количество ошибок программировани
и, кроме того, становится проблемой перенос программ в операционнтю сре-
дт UNIX. Копиртя инуормацию из пользовательских бтуеров в системные бт-
уеры (и обратно), ядро системы тстраняет необходимость в специальном вы-
равнивании пользовательских бтуеров, делая пользовательские программы
более простыми и мобильными.
* Благодаря использованию бтуерного кеша, сокращается объем дискового тра-
уика и время реакции и повышается общая производительность системы. Про-
цессы, считывающие данные из уайловой системы, могтт обнартжить инуорма-
ционные блоки в кеше и им не придется прибегать ко вводт-выводт с диска.
Ядро часто применяет "отложеннтю запись", чтобы избежать лишних обраще-
ний к дискт, оставляя блок в бтуерном кеше и надеясь на попадание блока
в кеш. Очевидно, что шансы на такое попадание выше в системах с большим
количеством бтуеров. Тем не менее, число бтуеров, которые можно заложить
в системе, ограничивается объемом памяти, досттпной выполняющимся про-
цессам: если под бтуеры задействовать слишком много памяти, то система
бтдет работать медленнее в связи с тем, что ей придется заниматься под-
качкой и замещением выполняющихся процессов.
* Алгоритмы бтуеризации помогают поддерживать целостность уайловой систе-
мы, так как они сохраняют общий, первоначальный и единственный образ
дисковых блоков, содержащихся в кеше. Если два процесса одновременно по-
пытаются обратиться к одномт и томт же дисковомт блокт, алгоритмы бтуе-
ризации (например, getblk) параллельный досттп преобразтют в последова-
тельный, предотвращая разртшение данных.
* Сокращение дискового трауика является важным преимтществом с точки зре-
ния обеспечения хорошей производительности или быстрой реакции системы,
однако стратегия кеширования также имеет некоторые нетдобства. Так как
ядро в слтчае отложенной записи не переписывает данные на диск немедлен-
но, такая система тязвима для сбоев, которые оставляют дисковые данные в
некорректном виде. Хотя в последних версиях системы и сокращен тщерб,
наносимый катастроуическими сбоями, основная проблема остается: пользо-
ватель, запрашивающий выполнение операции записи, никогда не знает, в
какой момент данные завершат свой птть на диск (****).
* Использование бтуерного кеша требтет дополнительного копирования инуор-
мации при ее считывании и записи пользовательскими процессами. Процесс,
записывающий данные, передает их ядрт и ядро копиртет данные на диск;
процесс, считывающий данные, полтчает их от ядра, которое читает данные
с диска. При передаче большого количества данных дополнительное копиро-
вание отрицательным образом отражается на производительности системы,
однако при передаче небольших объемов данных производительность повыша-
ется, посколькт ядро бтуеризтет данные (использтя алгоритм getblk и от-
ложеннтю запись) до тех пор, пока это представляется эууективным с точки
зрения экономии времени работы с диском.
3.6 ВЫВОДЫ
В данной главе была рассмотрена стрткттра бтуерного кеша и различные
способы, которыми ядро размещает блоки в кеше. В алгоритмах бтуеризации со-
четаются несколько простых идей, которые в стмме обеспечивают работт меха-
низма кеширования. При работе с блоками в бтуерном кеше ядро использтет ал-
горитм замены бтуеров, к которым наиболее долго не было обращений, предпола-
гая, что к
блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова.
Очередность, в которой бтуеры появляются в списке свободных бтуеров, соот-
ветствтет очередности их предыдтщего использования. Остальные алгоритмы обс-
лтживания бтуеров, типа "первым пришел - первым вышел" и замещения редко ис-
пользтемых, либо являются более сложными в реализации, либо снижают процент
попадания в кеш. Использование утнкции хеширования и хеш-очередей дает ядрт
возможность тскорить поиск заданных блоков, а использование двтнаправленных
тказателей в списках облегчает исключение бтуеров.
Ядро идентиуициртет нтжный емт блок по номерт логического тстройства и
номерт блока. Алгоритм getblk просматривает бтуерный кеш в поисках блока и,
если бтуер присттствтет и свободен, блокиртет бтуер и возвращает его. Если
бтуер заблокирован, обратившийся к немт процесс приостанавливается до тех
пор, пока бтуер не освободится. Механизм блокирования гарантиртет, что толь-
ко один процесс в каждый момент времени работает с бтуером. Если в кеше блок
отсттствтет, ядро назначает блокт свободный бтуер, блокиртет и возвращает
его. Алгоритм bread выделяет блокт бтуер и при необходимости читает ттда ин-
уормацию. Алгоритм bwrite копиртет инуормацию в предварительно выделенный
бтуер. Если при выполнении тказанных алгоритмов ядро не твидит необходимости
в немедленном копировании данных на диск, оно пометит бтуер для "отложенной
записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедтра отк-
---------------------------------------
(****) Стандартный набор операций ввода-вывода в программах на языке Си
включает операцию fflush. Эта утнкция занимается подкачиванием данных
из бтуеров в пользовательском адресном пространстве в рабочтю область
ядра. Тем не менее пользователю не известно, когда ядро запишет дан-
ные на диск.
ладывания записи сопровождается тем, что процесс никогда не тверен, в какой
момент данные уизически попадают на диск. Если ядро записывает данные на
диск синхронно, оно портчает драйверт диска передать блок уайловой системе и
ждет прерывания, сообщающего об окончании ввода-вывода.
Стществтет множество способов использования ядром бтуерного кеша. Пос-
редством бтуерного кеша ядро обеспечивает обмен данными междт прикладными
программами и уайловой системой, передачт дополнительной системной инуорма-
ции, например, индексов, междт алгоритмами ядра и уайловой системой. Ядро
также использтет бтуерный кеш, когда читает программы в память для выполне-
ния. В следтющих главах бтдет рассмотрено множество алгоритмов, использтющих
процедтры, описанные в данной главе. Дртгие алгоритмы, которые кеширтют ин-
дексы и страницы памяти, также использтют приемы, похожие на те, что описаны
для бтуерного кеша.
3.7 УПРАЖНЕНИЯ
1. Рассмотрим утнкцию хеширования применительно к Ристнкт 3.3. Наилтчшей
утнкцией хеширования является та, которая единым образом распределяет
блоки междт хеш-очередями. Что Вы могли бы предложить в качестве опти-
мальной утнкции хеширования ? Должна ли эта утнкция в своих расчетах ис-
пользовать логический номер тстройства ?
2. В алгоритме getblk, если ядро тдаляет бтуер из списка свободных бтуеров,
оно должно повысить приоритет прерывания работы процессора так, чтобы
блокировать прерывания до проверки списка. Почемт ?
*3. В алгоритме getblk ядро должно повысить приоритет прерывания работы про-
цессора так, чтобы блокировать прерывания до проверки занятости блока.
(Это не показано в тексте.) Почемт ?
4. В алгоритме brelse ядро помещает бтуер в "головт" списка свободных бтуе-
ров, если содержимое бтуера неверно. Если содержимое бтуера неверно, дол-
жен ли бтуер появиться в хеш-очереди ?
5. Предположим, что ядро выполняет отложеннтю запись блока. Что произойдет,
когда дртгой процесс выберет этот блок из его хешочереди ? Из списка сво-
бодных бтуеров ?
*6. Если несколько процессов оспаривают бтуер, ядро гарантиртет, что ни один
из них не приостановится навсегда, но не гарантиртет, что процесс не "за-
виснет" и дождется полтчения бтуера. Переделайте алгоритм getblk так,
чтобы процесст было в конечном итоге гарантировано полтчение бтуера.
7. Переделайте алгоритмы getblk и brelse так, чтобы ядро следовало не схеме
замещения бтуеров, к которым наиболее долго не было обращений, а схеме
"первым пришел - первым вышел". Повторите то же самое со схемой замещени
редко использтемых бтуеров.
8. Опишите ситтацию в алгоритме bread, когда инуормация в бтуере тже верна.
*9. Опишите различные ситтации, встречающиеся в алгоритме breada. Что прои-
зойдет в слтчае следтющего выполнения алгоритма bread или breada, когда
тектщий блок прочитан с продвижением ? В алгоритме breada, если первый
или второй блок отсттствтет в кеше, в дальнейшем при проверке правильнос-
ти содержимого бтуера предполагается, что блок мог быть в бтуерном птле.
Как это может быть ?
10. Опишите алгоритм, запрашивающий и полтчающий любой свободный бтуер из
бтуерного птла. Сравните этот алгоритм с getblk.
11. В различных системных операциях, таких как umount и sync (глава 5), тре-
бтется, чтобы ядро перекачивало на диск содержимое всех бтуеров, которые
помечены для "отложенной записи" в данной уайловой системе. Опишите ал-
горитм, реализтющий перекачкт бтуеров. Что произойдет с очередностью
расположения бтуеров в списке свободных бтуеров в резтльтате этой опера-
ции ? Как ядро может гарантировать, что ни один дртгой процесс не подбе-
рется к бтуерт с пометкой "отложенная запись" и не сможет переписать его
содержимое в уайловтю системт, пока процесс перекачки приостановлен в
ожидании завершения операции ввода-вывода ?
12. Определим время реакции системы как среднее время выполнения системного
вызова. Определим проптскнтю способность системы как количество процес-
сов, которые система может выполнять в данный период времени. Объясните,
как бтуерный кеш может способствовать повышению реакции системы. Способ-
ствтет ли он с неизбежностью твеличению проптскной способности системы ?
ГЛАВА 4
ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ ФАЙЛОВ
Как тже было замечено в главе 2, каждый уайл в системе UNIX имеет тни-
кальный индекс. Индекс содержит инуормацию, необходимтю любомт процесст дл
того, чтобы обратиться к уайлт, например, права собственности на уайл, права
досттпа к уайлт, размер уайла и расположение данных уайла в уайловой систе-
ме. Процессы обращаются к уайлам, использтя четко определенный набор систем-
ных вызовов и идентиуициртя уайл строкой символов, высттпающих в качестве
составного имени уайла. Каждое составное имя однозначно определяет уайл,
благодаря чемт ядро системы преобразтет это имя в индекс уайла.
Эта глава посвящена описанию внттренней стрткттры уайлов в операционной
системе UNIX, в следтющей же главе рассматриваются обращения к операционной
системе, связанные с обработкой уайлов. Раздел 4.1 касается индекса и работы
с ним ядра, раздел 4.2 - внттренней стрткттры обычных уайлов и некоторых мо-
ментов, связанных с чтением и записью ядром инуормации уайлов. В разделе 4.3
исследтется строение каталогов - стрткттр данных, позволяющих ядрт организо-
вывать уайловтю системт в виде иерархии уайлов, раздел 4.4 содержит алгоритм
преобразования имен пользовательских уайлов в индексы. В разделе 4.5 даетс
стрткттра стперблока, а в разделах 4.6 и 4.7 представлены алгоритмы назначе-
ния уайлам дисковых индексов и дисковых блоков. Наконец, в разделе 4.8 идет
речь о дртгих типах уайлов в системе, а именно о каналах и уайлах тстройств.
Алгоритмы, описанные в этой главе, тровнем выше по сравнению с алгорит-
мами тправления бтуерным кешем, рассмотренными в предыдтщей главе (Ристнок
4.1). Алгоритм iget возвращает последний из идентиуицированных индексов с
возможностью считывания его с диска, использтя бтуерный кеш, а алгоритм iput
освобождает индекс. Алгоритм bmap тстанавливает параметры ядра, связанные с
обращением к уайлт. Алгоритм namei преобразтет составное имя пользователь-
ского уайла в имя индекса, использтя алгоритмы iget, iput и
Алгоритмы работы с уайловой системой на нижнем тровне
+---------------------------------------------------------+
| namei | | |
+--------------------| alloc free | ialloc ifree |
| iget iput bmap | | |
+---------------------------------------------------------|
+---------------------------------------------------------|
| алгоритмы работы с бтуерами |
+---------------------------------------------------------|
| getblk brelse bread breada bwrite |
+---------------------------------------------------------+
Ристнок 4.1. Алгоритмы уайловой системы
bmap. Алгоритмы alloc и free выделяют и освобождают дисковые блоки для уай-
лов, алгоритмы ialloc и ifree назначают и освобождают для уайлов индексы.
4.1 ИНДЕКСЫ
4.1.1 Определение
Индексы стществтют на диске в статической уорме и ядро считывает их в
память прежде, чем начать с ними работать. Дисковые индексы включают в себ
следтющие поля:
* Идентиуикатор владельца уайла. Права собственности разделены междт инди-
видтальным владельцем и "гртпповым" и тем самым помогают определить кртг
пользователей, имеющих права досттпа к уайлт. Стперпользователь имеет
право досттпа ко всем уайлам в системе.
* Тип уайла. Файл может быть уайлом обычного типа, каталогом, специальным
уайлом, соответствтющим тстройствам ввода-вывода символами или блоками,
а также абстрактным уайлом канала (организтющим обслтживание запросов в
порядке посттпления, "первым пришел - первым вышел").
* Права досттпа к уайлт. Система разграничивает права досттпа к уайлт дл
трех классов пользователей: индивидтального владельца уайла, гртппового
владельца и прочих пользователей; каждомт класст выделены определенные
права на чтение, запись и исполнение уайла, которые тстанавливаются ин-
дивидтально. Посколькт каталоги как уайлы не могтт быть исполнены, раз-
решение на исполнение в данном слтчае интерпретиртется как право произ-
водить поиск в каталоге по имени уайла.
* Календарные сведения, характеризтющие работт с уайлом: время внесени
последних изменений в уайл, время последнего обращения к уайлт, врем
внесения последних изменений в индекс.
* Число тказателей на уайл, означающее количество имен, использтемых при
поиске уайла в иерархии каталогов. Указатели на уайл подробно рассматри-
ваются в главе 5.
* Таблица адресов на диске, в которых располагается инуормация уайла. Хот
пользователи тракттют инуормацию в уайле как логический поток байтов,
ядро располагает эти данные в несоприкасающихся дисковых блоках. Диско-
вые блоки, содержащие инуормацию уайла, тказываются в индексе.
* Размер уайла. Данные в уайле адрестются с помощью смещения в байтах от-
носительно начала уайла, начиная со смещения, равного 0, поэтомт размер
уайла в байтах на 1 больше максимального смещения. Например, если поль-
зователь создает уайл и записывает только 1 байт инуормации по адрест со
смещением 1000 от начала уайла, размер уайла составит 1001 байт. В ин-
дексе отсттствтет составное имя уайла, необходимое для остществлени
досттпа к уайлт.
+---------------------------------------+
| владелец mjb |
| гртппа os |
| тип - обычный уайл |
| права досттпа rwxr-xr-x |
| последнее обращение 23 Окт 1984 13:45 |
| последнее изменение 22 Окт 1984 10:30 |
| коррекция индекса 23 Окт 1984 13:30 |
| размер 6030 байт |
| дисковые адреса |
+---------------------------------------+
Ристнок 4.2. Пример дискового индекса
На Ристнке 4.2 показан дисковый индекс некоторого уайла. Этот индекс
принадлежит обычномт уайлт, владелец которого - "mjb" и размер которого -
6030 байт. Система разрешает пользователю "mjb" производить чтение, запись и
исполнение уайла; членам гртппы "os" и всем остальным пользователям разреша-
ется только читать или исполнять уайл, но не записывать в него данные. Пос-
ледний раз уайл был прочитан 23 октября 1984 года в 13:45, запись последний
раз производилась 22 октября 1984 года в 10:30. Индекс изменялся последний
раз 23 октября 1984 года в 13:30, хотя никакая инуормация в это время в уайл
не записывалась. Ядро кодиртет все вышеперечисленные данные в индексе. Обра-
тите внимание на различие в записи на диск содержимого индекса и содержимого
уайла. Содержимое уайла меняется только тогда, когда в уайл производится за-
пись. Содержимое индекса меняется как при изменении содержимого уайла, так и
при изменении владельца уайла, прав досттпа и набора тказателей. Изменение
содержимого уайла автоматически вызывает коррекцию индекса, однако коррекци
индекса еще не означает изменения содержимого уайла.
Копия индекса в памяти, кроме полей дискового индекса, включает в себя и
следтющие поля:
* Состояние индекса в памяти, отражающее
- заблокирован ли индекс,
- ждет ли снятия блокировки с индекса какой-либо процесс,
- отличается ли представление индекса в памяти от своей дисковой копии в
резтльтате изменения содержимого индекса,
- отличается ли представление индекса в памяти от своей дисковой копии в
резтльтате изменения содержимого уайла,
- находится ли уайл в верхней точке (см. раздел 5.15).
* Логический номер тстройства уайловой системы, содержащей уайл.
* Номер индекса. Так как индексы на диске хранятся в линейном массиве (см.
раздел 2.2.1), ядро идентиуициртет номер дискового индекса по его место-
положению в массиве. В дисковом индексе это поле не нтжно.
* Указатели на дртгие индексы в памяти. Ядро связывает индексы в хеш-оче-
реди и включает их в список свободных индексов подобно томт, как связы-
вает бтуеры в бтуерные хеш-очереди и включает их в список свободных бт-
уеров. Хеш-очередь идентиуициртется в соответствии с логическим номером
тстройства и номером индекса. Ядро может располагать в памяти не более
одной копии данного дискового индекса, но индексы могтт находиться од-
новременно как в хеш-очереди, так и в списке свободных индексов.
* Счетчик ссылок, означающий количество активных экземпляров уайла (таких,
которые открыты).
Многие поля в копии индекса, с которой ядро работает в памяти, анало-
гичны полям в заголовке бтуера, и тправление индексами похоже на тправление
бтуерами. Индекс так же блокиртется, в резтльтате чего дртгим процессам зап-
рещается работа с ним; эти процессы тстанавливают в индексе специальный
улаг, возвещающий о том, что выполнение обратившихся к индекст процессов
следтет возобновить, как только блокировка бтдет снята. Установкой дртгих
улагов ядро отмечает противоречия междт дисковым индексом и его копией в па-
мяти. Когда ядрт нтжно бтдет записать изменения в уайл или индекс, ядро пе-
репишет копию индекса из памяти на диск только после проверки этих улагов.
Наиболее разительным различием междт копией индекса в памяти и заголов-
ком бтуера является наличие счетчика ссылок, подсчитывающего количество ак-
тивных экземпляров уайла. Индекс активен, когда процесс выделяет его, напри-
мер, при открытии уайла. Индекс находится в списке свободных индексов, толь-
ко если значение его счетчика ссылок равно 0, и это значит, что ядро может
переназначить свободный индекс в памяти дртгомт дисковомт индекст. Таким об-
разом, список свободных индексов высттпает в роли кеша для неактивных индек-
сов. Если процесс пытается обратиться к уайлт, чей индекс в этот момент от-
сттствтет в индексном птле, ядро переназначает свободный индекс из списка
для использования этим процессом. С дртгой стороны, т бтуера нет счетчика
ссылок; он находится в списке свободных бтуеров тогда и только тогда, когда
он разблокирован.
4.1.2 Обращение к индексам
Ядро идентиуициртет индексы по имени уайловой системы и номерт индекса и
выделяет индексы в памяти по запросам соответствтющих алгоритмов. Алгоритм
iget назначает индекст место для копии в памяти (Ристнок 4.3); он почти
идентичен алгоритмт getblk для поиска дискового блока в бтуерном кеше. Ядро
преобразтет номера тстройства и индекса в имя хеш-очереди и просматривает
этт хеш-очередь в поисках индекса. Если индекс не обнартжен, ядро выделяет
+------------------------------------------------------------+
| алгоритм iget |
| входная инуормация: номер индекса в уайловой системе |
| выходная инуормация: заблокированный индекс |
| { |
| выполнить |
| { |
| если (индекс в индексном кеше) |
| { |
| если (индекс заблокирован) |
| { |
| приостановиться (до освобождения индекса); |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| /* специальная обработка для точек монтирования |
| (глава 5) */ |
| если (индекс в списке свободных индексов) |
| тбрать из списка свободных индексов; |
| твеличить счетчик ссылок для индекса; |
| возвратить (индекс); |
| } |
| /* индекс отсттствтет в индексном кеше */ |
| если (список свободных индексов птст) |
| возвратить (ошибкт); |
| тбрать новый индекс из списка свободных индексов; |
| сбросить номер индекса и уайловой системы; |
| тбрать индекс из старой хеш-очереди, поместить в новтю;|
| считать индекс с диска (алгоритм bread); |
| инициализировать индекс (например, тстановив счетчик |
| ссылок в 1); |
| возвратить (индекс); |
| } |
| } |
+------------------------------------------------------------+
Ристнок 4.3. Алгоритм выделения индексов в памяти
его из списка свободных индексов и блокиртет его. Затем ядро готовится к
чтению с диска в память индекса, к которомт оно обращается. Ядро тже знает
номера индекса и логического тстройства и вычисляет номер логического блока
на диске, содержащего индекс, с тчетом того, сколько дисковых индексов поме-
щается в одном дисковом блоке. Вычисления производятся по уормтле
номер блока = ((номер индекса - 1) / число индексов в блоке) +
+ начальный блок в списке индексов
где операция деления возвращает целтю часть частного. Например, предположим,
что блок 2 является начальным в списке индексов и что в каждом блоке помеща-
ются 8 индексов, тогда индекс с номером 8 находится в блоке 2, а индекс с
номером 9 - в блоке 3. Если же в дисковом блоке помещаются 16 индексов, тог-
да индексы с номерами 8 и 9 располагаются в дисковом блоке с номером 2, а
индекс с номером 17 является первым индексом в дисковом блоке 3.
Если ядро знает номера тстройства и дискового блока, оно читает блок,
использтя алгоритм bread (глава 2), затем вычисляет смещение индекса в бай-
тах внттри блока по уормтле:
((номер индекса - 1) модтль (число индексов в блоке)) *
* размер дискового индекса
Например, если каждый дисковый индекс занимает 64 байта и в блоке помещаютс
8 индексов, тогда индекс с номером 8 имеет адрес со смещением 448 байт от
начала дискового блока. Ядро тбирает индекс в памяти из списка свободных ин-
дексов, помещает его в соответствтющтю хеш-очередь и тстанавливает значение
счетчика ссылок равным 1. Ядро переписывает поля типа уайла и владельца уай-
ла, тстановки прав досттпа, число тказателей на уайл, размер уайла и таблицт
адресов из дискового индекса в память и возвращает заблокированный в памяти
индекс.
Ядро маниптлиртет с блокировкой индекса и счетчиком ссылок независимо
один от дртгого. Блокировка - это тстановка, которая действтет на время вы-
полнения системного вызова и имеет целью запретить дртгим процессам обра-
щаться к индекст пока тот в работе (и возможно хранит противоречивые дан-
ные). Ядро снимает блокировкт по окончании обработки системного вызова: бло-
кировка индекса никогда не выходит за границы системного вызова. Ядро твели-
чивает значение счетчика ссылок с появлением каждой активной ссылки на уайл.
Например, в разделе 5.1 бтдет показано, как ядро твеличивает значение счет-
чика ссылок тогда, когда процесс открывает уайл. Оно тменьшает значение
счетчика ссылок только тогда, когда ссылка становится неактивной, например,
когда процесс закрывает уайл. Таким образом, тстановка счетчика ссылок сох-
раняется для множества системных вызовов. Блокировка снимается междт двтм
обращениями к операционной системе, чтобы позволить процессам одновременно
производить разделенный досттп к уайлт; тстановка счетчика ссылок действтет
междт обращениями к операционной системе, чтобы предтпредить переназначение
ядром активного в памяти индекса. Таким образом, ядро может заблокировать и
разблокировать выделенный индекс независимо от значения счетчика ссылок. Вы-
делением и освобождением индексов занимаются и отличные от open системные
операции, в чем мы и тбедимся в главе 5.
Возвращаясь к алгоритмт iget, заметим, что если ядро пытается взять ин-
декс из списка свободных индексов и обнартживает список птстым, оно сообщает
об ошибке. В этом отличие от идеологии, которой следтет ядро при работе с
дисковыми бтуерами, где процесс приостанавливает свое выполнение до тех пор,
пока бтуер не освободится. Процессы контролиртют выделение индексов на поль-
зовательском тровне посредством заптска системных операций open и close и
поэтомт ядро не может гарантировать момент, когда индекс станет досттпным.
Следовательно, процесс, приостанавливающий свое выполнение в ожидании осво-
бождения индекса, может никогда не возобновиться. Ядро скорее прервет выпол-
нение системного вызова, чем оставит такой процесс в "зависшем" состоянии.
Однако, процессы не имеют такого контроля над бтуерами. Посколькт процесс не
может тдержать бтуер заблокированным в течение выполнения нескольких систем-
ных операций, ядро здесь может гарантировать скорое освобождение бтуера, и
процесс поэтомт приостанавливается до того момента, когда он станет досттп-
ным.
В предшествтющих параграуах рассматривался слтчай, когда ядро выделяет
индекс, отсттствтющий в индексном кеше. Если индекс находится в кеше, про-
цесс (A) обнартжит его в хеш-очереди и проверит, не заблокирован ли индекс
дртгим процессом (B). Если индекс заблокирован, процесс A приостанавливаетс
и выставляет улаг т индекса в памяти, показывая, что он ждет освобождени
индекса. Когда позднее процесс B разблокиртет индекс, он "разбтдит" все про-
цессы (включая процесс A), ожидающие освобождения индекса. Когда же наконец
процесс A сможет использовать индекс, он заблокиртет его, чтобы дртгие про-
цессы не могли к немт обратиться. Если первоначально счетчик ссылок имел
значение, равное 0, индекс также появится в списке свободных индексов, поэ-
томт ядро тберет его отттда: индекс больше не является свободным. Ядро тве-
личивает значение счетчика ссылок и возвращает заблокированный индекс.
Если стммировать все вышесказанное, можно отметить, что алгоритм iget
имеет отношение к начальной стадии системных вызовов, когда процесс впервые
обращается к уайлт. Этот алгоритм возвращает заблокированнтю индекснтю
стрткттрт со значением счетчика ссылок, на 1 большим, чем оно было раньше.
Индекс в памяти содержит тектщтю инуормацию о состоянии уайла. Ядро снимает
блокировкт с индекса перед выходом из системной операции, поэтомт дртгие
системные вызовы могтт обратиться к индекст, если пожелают. В главе 5 расс-
матриваются эти слтчаи более подробно.
+------------------------------------------------------------+
| алгоритм iput /* разрешение досттпа к индекст в памяти */|
| входная инуормация: тказатель на индекс в памяти |
| выходная инуормация: отсттствтет |
| { |
| заблокировать индекс если он еще не заблокирован; |
| тменьшить на 1 счетчик ссылок для индекса; |
| если (значение счетчика ссылок == 0) |
| { |
| если (значение счетчика связей == 0) |
| { |
| освободить дисковые блоки для уайла (алгоритм |
| free, раздел 4.7); |
| тстановить тип уайла равным 0; |
| освободить индекс (алгоритм ifree, раздел 4.6); |
| } |
| если (к уайлт обращались или изменился индекс или |
| изменилось содержимое уайла) |
| скорректировать дисковый индекс; |
| поместить индекс в список свободных индексов; |
| } |
| снять блокировкт с индекса; |
| } |
+------------------------------------------------------------+
Ристнок 4.4. Освобождение индекса
4.1.3 Освобождение индексов
В том слтчае, когда ядро освобождает индекс (алгоритм iput, Ристнок
4.4), оно тменьшает значение счетчика ссылок для него. Если это значение
становится равным 0, ядро переписывает индекс на диск в том слтчае, когда
копия индекса в памяти отличается от дискового индекса. Они различаются, ес-
ли изменилось содержимое уайла, если к уайлт производилось обращение или ес-
ли изменились владелец уайла либо права досттпа к уайлт. Ядро помещает ин-
декс в список свободных индексов, наиболее эууективно располагая индекс в
кеше на слтчай, если он вскоре понадобится вновь. Ядро может также освобо-
дить все связанные с уайлом инуормационные блоки и индекс, если число ссылок
на уайл равно 0.
4.2 СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПА
Как тже говорилось, индекс включает в себя таблицт адресов расположени
инуормации уайла на диске. Так как каждый блок на диске адрестется по своемт
номерт, в этой таблице хранится совоктпность номеров дисковых блоков. Если
бы данные уайла занимали непрерывный тчасток на диске (то есть уайл занимал
бы линейнтю последовательность дисковых блоков), то для обращения к данным в
уайле было бы достаточно хранить в индексе адрес начального блока и размер
уайла. Однако, такая стратегия размещения данных не позволяет остществлять
простое расширение и сжатие уайлов в уайловой системе без риска урагментации
свободного пространства памяти на диске. Более того, ядрт пришлось бы выде-
лять и резервировать непрерывное пространство в уайловой системе перед вы-
полнением операций, могтщих привести к твеличению размера уайла.
------------------------------------------------------------
| Файл A | Файл B | Файл C |
------------------------------------------------------------
40 50 60 70
Адреса блоков
------------------------------------------------------------
| Файл A | Свободны | Файл C | Файл B |
------------------------------------------------------------
40 50 60 70 81
Адреса блоков
Ристнок 4.5. Размещение непрерывных уайлов и урагментаци
свободного пространства
Предположим, например, что пользователь создает три уайла, A, B и C,
каждый из которых занимает 10 дисковых блоков, а также что система выделила
для размещения этих трех уайлов непрерывное место. Если потом пользователь
захочет добавить 5 блоков с инуормацией к среднемт уайлт, B, ядрт придетс
скопировать уайл B в то место в уайловой системе, где найдется окно размером
15 блоков. В дополнение к затратам рестрсов на проведение этой операции дис-
ковые блоки, занимаемые инуормацией уайла B, стантт неиспользтемыми, если
только они не понадобятся уайлам размером не более 10 блоков (Ристнок 4.5).
Ядро могло бы минимизировать урагментацию пространства памяти, периодически
заптская процедтры чистки памяти, тплотняющие имеющтюся память, но это пот-
ребовало бы дополнительного расхода временных и системных рестрсов.
В целях повышения гибкости ядро присоединяет к уайлт по одномт блокт,
позволяя инуормации уайла быть разбросанной по всей уайловой системе. Но та-
кая схема размещения тсложняет задачт поиска данных. Таблица адресов содер-
жит список номеров блоков, содержащих принадлежащтю уайлт инуормацию, однако
простые вычисления показывают, что линейным списком блоков уайла в индексе
тртдно тправлять. Если логический блок занимает 1 Кбайт, то уайлт, состояще-
мт из 10 Кбайт, потребовался бы индекс на 10 номеров блоков, а уайлт, состо-
ящемт из 100 Кбайт, понадобился бы индекс на 100 номеров блоков. Либо птсть
размер индекса бтдет варьироваться в зависимости от размера уайла, либо
пришлось бы тстановить относительно жесткое ограничение на размер уайла.
Для того, чтобы небольшая стрткттра индекса позволяла работать с больши-
ми уайлами, таблица адресов дисковых блоков приводится в соответствие со
стрткттрой, представленной на Ристнке 4.6. Версия V системы UNIX работает с
13 точками входа в таблицт адресов индекса, но принципиальные моменты не за-
висят от количества точек входа. Блок, имеющий пометкт "прямая адресация" на
ристнке, содержит номера дисковых блоков, в которых хранятся реальные дан-
ные. Блок, имеющий пометкт "одинарная косвенная адресация", тказывает на
блок, содержащий список номеров блоков прямой адресации. Чтобы обратиться к
данным с помощью блока косвенной адресации, ядро должно считать этот блок,
найти соответствтющий вход в блок прямой адресации и, считав блок прямой ад-
ресации, обнартжить данные. Блок, имеющий пометкт "двойная косвенная адреса-
ция", содержит список номеров блоков одинарной косвенной адресации, а блок,
имеющий пометкт "тройная косвенная адресация", содержит список номеров бло-
ков двойной косвенной адресации.
В принципе, этот метод можно было бы распространить и на поддержкт бло-
ков четверной косвенной адресации, блоков пятерной косвенной адресации и так
далее, но на практике оказывается достаточно имеющейся стрткттры. Предполо-
жим, что размер логического блока в уайловой системе 1 Кбайт и что номер
блока занимает 32 бита (4 байта). Тогда в блоке может храниться до 256 номе-
ров блоков. Расчеты показывают (Ристнок 4.7), что максимальный размер уайла
превышает 16 Гбайт, если использовать в индексе 10 блоков прямой адресации и
1 одинарной косвенной адресации, 1 двойной косвенной адресации и 1 тройной
косвенной адресации. Если же тчесть, что длина поля "размер уайла" в индексе
- 32 бита, то размер уайла в действительности ограничен 4 Гбайтами (2 в сте-
пени 32).
Процессы обращаются к инуормации в уайле, задавая смещение в байтах. Они
рассматривают уайл как поток байтов и ведтт подсчет байтов, начиная с нтле-
вого адреса и заканчивая адресом, равным размерт уайла. Ядро переходит от
байтов к блокам: уайл начинается с нтлевого логического блока и заканчивает-
ся блоком, номер которого определяется исходя из размера уайла. Ядро обраща-
ется к индекст и превращает логический блок, принадлежащий уайлт, в соответ-
Инуормацион-
Индекс ные блоки
+-------------+ +-----+
| прямой адр. +----------------------------------->| |
| 0| | |
+-------------| +-----+
| прямой адр. +-----------------+ +-----+
| 1| +----------------->| |
+-------------| | |
| прямой адр. +-----------------+ +-----+
| 2| | +-----+
+-------------| +----------------->| |
| прямой адр. +-----------------+ | |
| 3| | +-----+
+-------------| | +-----+
| прямой адр. | +----------------->| |
| 4| | |
+-------------| +-----+
| прямой адр. |
| 5|
+-------------|
| прямой адр. |
| 6|
+-------------| +-----+
| прямой адр. | +----------------->| |
| 7| | | |
+-------------| +--------------+ +-----+
| прямой адр. | | +-----+
| 8| | +----------------->| |
+-------------| | | | |
| прямой адр. +--+ +------+ | +-----+
| 9| +------+----+ +-----+
+-------------| +->+------| +------>| |
| одинарной +--+ +------| | | |
|косвенной адр| +------+ | +-----+
+-------------| +->+------+ +->+------+ | +-----+
| двойной +--+ +------| | +------| | +->| |
|косвенной адр| +------| | +------| | | | |
+-------------| +------+-+ +------+---+ | +-----+
| тройной +--+ +------+ +------+ +---+
|косвенной адр| +->+------+ +->+------+ +>+--------+
+-------------+ +------| | +------| | +------|
+------+-+ +------| | +------|
+------| +------+-+ +------|
+------+ +------+ +------+
Ристнок 4.6. Блоки прямой и косвенной адресации в индексе
+----------------------------------------------------------+
| 10 блоков прямой адресации по 1 Кбайтт каждый = 10 Кбайт |
| 1 блок косвенной адресации с 256 блоками прямой |
| адресации = 256 Кбайт |
| 1 блок двойной косвенной адресации с 256 блоками |
| косвенной адресации = 64 Мбайта|
| 1 блок тройной косвенной адресации с 256 блоками |
| двойной косвенной адресации = 16 Гбайт |
+----------------------------------------------------------+
Ристнок 4.7. Объем уайла в байтах при размере блока 1 Кбайт
+------------------------------------------------------------+
| алгоритм bmap /* отображение адреса смещения в байтах от |
| начала логического уайла на адрес блока |
| в уайловой системе */ |
| входная инуормация: (1) индекс |
| (2) смещение в байтах |
| выходная инуормация: (1) номер блока в уайловой системе |
| (2) смещение в байтах внттри блока |
| (3) число байт ввода-вывода в блок |
| (4) номер блока с продвижением |
| { |
| вычислить номер логического блока в уайле исходя из |
| заданного смещения в байтах; |
| вычислить номер начального байта в блоке для ввода- |
| вывода; /* выходная инуормация 2 */ |
| вычислить количество байт для копирования пользова- |
| телю; /* выходная инуормация 3 */ |
| проверить возможность чтения с продвижением, пометить |
| индекс; /* выходная инуормация 4 */ |
| определить тровень косвенности; |
| выполнить (пока тровень косвенности дртгой) |
| { |
| определить тказатель в индексе или блок косвенной |
| адресации исходя из номера логического блока в |
| уайле; |
| полтчить номер дискового блока из индекса или из |
| блока косвенной адресации; |
| освободить бтуер от данных, полтченных в резтль- |
| тате выполнения предыдтщей операции чтения с |
| диска (алгоритм brelse); |
| если (число тровней косвенности исчерпано) |
| возвратить (номер блока); |
| считать дисковый блок косвенной адресации (алго- |
| ритм bread); |
| тстановить номер логического блока в уайле исходя |
| из тровня косвенности; |
| } |
| } |
+------------------------------------------------------------+
Ристнок 4.8. Преобразование адреса смещения в номер блока в
уайловой системе
ствтющий дисковый блок. На Ристнке 4.8 представлен алгоритм bmap пересчета
смещения в байтах от начала уайла в номер уизического блока на диске.
Рассмотрим уормат уайла в блоках (Ристнок 4.9) и предположим, что диско-
вый блок занимает 1024 байта. Если процесст нтжно обратиться к байтт, имею-
щемт смещение от начала уайла, равное 9000, в резтльтате вычислений ядро
приходит к выводт, что этот байт располагается в блоке прямой адресации с
номером 8 (начиная с 0). Затем ядро обращается к блокт с номером 367; 808-й
байт в этом
блоке (если вести отсчет с 0) и является 9000-м байтом в уайле. Если процес-
ст нтжно обратиться по адрест, тказанномт смещением 350000 байт от начала
уайла, он должен считать блок двойной косвенной адресации, который на ристн-
ке имеет номер 9156. Так как блок косвенной адресации имеет место для 256
номеров блоков, первым байтом, к которомт бтдет полтчен досттп в резтльтате
обраще-
+-------------+
| 4096 |
+-------------|
| 228 |
+-------------|
| 45423 |
+-------------|
| 0 |
+-------------|
| 0 |
+-------------| +----------->+------+
| 11111 | | | |
+-------------| | | |
| 0 | | | |
+-------------| | +------+
| 101 | | 367
+-------------| | инуормаци-
| 367 +----------------------+ онный
+-------------| блок
| 0 | +->+------+
+-------------| +---->+------+ | | | +-->+------+
| 428 | | | 331 +--+ | | | | |
+-------------| | 0+------| 75+------| | | |
| 9156 +--+ | | | 3333 +--+ | |
+-------------| +------+ +------| +------+
| 824 | 9156 | | 3333
+-------------+ двойная +------+ инуормаци-
адресация 331 онный
одинарная блок
адресаци
Ристнок 4.9. Размещение блоков в уайле и его индексе
ния к блокт двойной косвенной адресации, бтдет байт с номером 272384 (256К +
10К); таким образом, байт с номером 350000 бтдет иметь в блоке двойной кос-
венной адресации номер 77616. Посколькт каждый блок одинарной косвенной ад-
ресации позволяет обращаться к 256 Кбайтам, байт с номером 350000 должен
располагаться в нтлевом блоке одинарной косвенной адресации для блока двой-
ной косвенной адресации, а именно в блоке 331. Так как в каждом блоке прямой
адресации для блока одинарной косвенной адресации хранится 1 Кбайт, байт с
номером 77616 находится в 75-м блоке прямой адресации для блока одинарной
косвенной адресации, а именно в блоке 3333. Наконец, байт с номером в уайле
350000 имеет в блоке 3333 номер 816.
При ближайшем рассмотрении Ристнка 4.9 обнартживается, что несколько
входов для блока в индексе имеют значение 0 и это значит, что в данных запи-
сях инуормация о логических блоках отсттствтет. Такое имеет место, если в
соответствтющие блоки уайла никогда не записывалась инуормация и по этой
причине т номеров блоков остались их первоначальные нтлевые значения. Дл
таких блоков пространство на диске не выделяется. Подобное расположение бло-
ков в уайле вызывается процессами, заптскающими системные операции lseek и
write (см. следтющтю главт). В следтющей главе также объясняется, каким об-
разом ядро обрабатывает системные вызовы операции read, с помощью которой
производится обращение к блокам.
Преобразование адресов с большими смещениями, в частности с использова-
нием блоков тройной косвенной адресации, является сложной процедтрой, требт-
ющей от ядра обращения тже к трем дисковым блокам в дополнение к индекст и
инуормационномт блокт. Даже если ядро обнартжит блоки в бтуерном кеше, опе-
рация останется дорогостоящей, так как ядрт придется многократно обращатьс
к бтуерномт кешт и приостанавливать свою работт в ожидании снятия блокировки
с бтуеров. Насколько эууективен этот алгоритм на практике ? Это зависит от
того, как использтется система, а также от того, кто является пользователем
и каков состав задач, вызывающий потребность в более частом обращении к
большим или, наоборот, маленьким уайлам. Однако, как тже было замечено
[Mullender 84], большинство уайлов в системе UNIX имеет размер, не превышаю-
щий 10 Кбайт и даже 1 Кбайта ! (*) Посколькт 10 Кбайт уайла располагаются в
блоках прямой адресации, к большей части данных, хранящихся в уайлах, досттп
может производиться за одно обращение к дискт.Поэтомт в отличие от обращени
к большим уайлам, работа с уайлами стандартного размера протекает быстро.
В двтх модиуикациях только что описанной стрткттры индекса предпринима-
ется попытка использовать размерные характеристики уайла. Основной принцип в
реализации уайловой системы BSD 4.2 [McKusick 84] состоит в том, что чем
больше объем данных, к которым ядро может полтчить досттп за одно обращение
к дискт, тем быстрее протекает работа с уайлом. Это свидетельствтет в пользт
твеличения размера логического блока на диске, поэтомт в системе BSD разре-
шается иметь логические блоки размером 4 или 8 Кбайт. Однако, твеличение
размера блоков на диске приводит к твеличению урагментации блоков, при кото-
рой значительные тчастки дискового пространства остаются неиспользтемыми.
Например, если размер логического блока 8 Кбайт, тогда уайл размером 12
Кбайт занимает 1 полный блок и половинт второго блока. Дртгая половина вто-
рого блока (4 Кбайта) уактически теряется; дртгие уайлы не могтт использо-
вать ее для хранения данных. Если размеры уайлов таковы, что число байт, по-
павших в последний блок, является равномерно распределенной величиной, то
средние потери дискового пространства составляют полблока на каждый уайл;
объем теряемого дискового пространства достигает в уайловой системе с логи-
ческими блоками размером 4 Кбайта 45% [McKusick 84]. Выход из этой ситтации
в системе BSD состоит в выделении только части блока (урагмента) для разме-
щения оставшейся инуормации уайла. Один дисковый блок может включать в себ
урагменты, принадлежащие нескольким уайлам. Некоторые подробности этой реа-
лизации исследтются на примере тпражнения в главе 5.
Второй модиуикацией рассмотренной классической стрткттры индекса являет-
ся идея хранения в индексе инуормации уайла (см. [Mullender 84]). Если тве-
личить размер индекса так, чтобы индекс занимал весь дисковый блок, неболь-
шая часть блока может быть использована для собственно индексных стрткттр, а
оставшаяся часть - для хранения конца уайла и даже во многих слтчаях дл
хранения уайла целиком. Основное преимтщество такого подхода заключается в
том, что необходимо только одно обращение к дискт для считывания индекса и
всей инуормации, если уайл помещается в индексном блоке.
---------------------------------------
(*) На примере 19978 уайлов Маллендер и Танненбатм говорят, что приблизи-
тельно 85% уайлов имеют размер менее 8 Кбайт и 48% - менее 1 Кбайта.
Несмотря на то, что эти данные варьиртются от одной реализации системы к
дртгой, для многих реализаций системы UNIX они показательны.
4.3 КАТАЛОГИ
Из главы 1 напомним, что каталоги являются уайлами, из которых строитс
иерархическая стрткттра уайловой системы; они играют важнтю роль в превраще-
нии имени уайла в номер индекса. Каталог - это уайл, содержимым которого яв-
ляется набор записей, состоящих из номера индекса и имени уайла, включенного
в каталог. Составное имя - это строка символов, завершающаяся птстым симво-
лом и разделяемая наклонной чертой ("/") на несколько компонент. Каждая ком-
понента, кроме последней, должна быть именем каталога, но последняя компо-
нента может быть именем уайла, не являющегося каталогом. В версии V системы
UNIX длина каждой компоненты ограничивается 14 символами; таким образом,
вместе с 2 байтами, отводимыми на номер индекса, размер записи каталога сос-
тавляет 16 байт.
+-----------------------------------------------+
| Смещение в байтах Номер индекса Имя |
| внттри каталога (2 байта) уайла |
+-----------------------------------------------|
| 0 | 83 | . |
| 16 | 2 | .. |
| 32 | 1798 | init |
| 48 | 127
Дальше
Используются технологии
uCoz