ных блоков в суперблоке;   |
    |    если (из списка удален последний блок)                  |
    |    {                                                       |
    |        заблокировать суперблок;                            |
    |        прочитать блок, только что взЯтый из списка свобод- |
    |         ных (алгоритм bread);                              |
    |        скопировать номера блоков, хранЯщиесЯ в данном бло- |
    |         ке, в суперблок;                                   |
    |        освободить блочный буфер (алгоритм brelse);         |
    |        снЯть блокировку с суперблока;                      |
    |        возобновить выполнение процессов (после снЯтиЯ бло- |
    |         кировки с суперблока);                             |
    |    }                                                       |
    |    получить буфер длЯ блока, удаленного из списка (алго-   |
    |     ритм getblk);                                          |
    |    обнулить содержимое буфера;                             |
    |    уменьшить общее число свободных блоков;                 |
    |    пометить суперблок как "измененный";                    |
    |    возвратить буфер;                                       |
    | }                                                          |
    +------------------------------------------------------------+


           ђисунок 4.19. Ђлгоритм выделениЯ дискового блока


                                     81


4.20(г)  показан  заполненный список в суперблоке и следующий свЯзной блок с
номером 211.
    Ђлгоритмы назначениЯ и освобождениЯ индексов и дисковых блоков  сходЯтсЯ
в том, что Ядро использует суперблок в качестве кеша, хранЯщего указатели на
свободные ресурсы - номера блоков и номера индексов. Ћно поддерживает список
номеров  блоков  с  указателЯми,  такой, что каждый номер свободного блока в
файловой системе поЯвлЯетсЯ в некотором элементе списка, но Ядро не  поддер-
живает такого списка длЯ свободных индексов. ’ому есть три причины.
1.  џдро устанавливает, свободен ли индекс или нет, проверЯЯ: если поле типа
   файла очищено, индекс свободен. џдро не нуждаетсЯ в другом механизме опи-
   саниЯ свободных индексов. ’ем не менее, оно не может определить, свободен
   ли блок или нет, только взглЯнув на него. џдро не может уловить  различиЯ
   между  маской,  показывающей,  что блок свободен, и информацией, случайно
   имеющей сходную маску. ‘ледовательно, Ядро нуждаетсЯ во внешнем механизме
   идентификации свободных блоков, в качестве него в традиционных реализаци-
   Ях системы используетсЯ список с указателЯми.
2. ‘ама конструкциЯ дисковых блоков наводит на мысль об использовании  спис-
   ков с указателЯми: в дисковом блоке легко разместить большие списки номе-
   ров свободных блоков. Ќо индексы не имеют подходЯщего места длЯ массового
   хранениЯ списков номеров свободных индексов.
3. Џользователи имеют склонность чаще расходовать дисковые блоки, нежели ин-
   дексы,  поэтому кажущеесЯ запаздывание в работе при просмотре диска в по-
   исках свободных индексов не ЯвлЯетсЯ таким критическим, как если  бы  оно
   имело место при поисках свободных дисковых блоков.

          список в суперблоке
         +-----+-----+-----+-----+---------------------+
         | 109 | 106 | 103 | 100 | ------------------- |
         +--+--+-----+-----+-----+---------------------+
      +-----+
      |  109
      |  +-----+-----+-----+-----+---------------+-----+
      +->| 211 | 208 | 205 | 202 | ------------- | 112 |
         +-----+-----+-----+-----+---------------+-----+

         (а) ЏервоначальнаЯ конфигурациЯ

          список в суперблоке
         +-----+-----+---------------------------------+
         | 109 | 949 | ------------------------------- |
         +--+--+-----+---------------------------------+
      +-----+
      |  109
      |  +-----+-----+-----+-----+---------------+-----+
      +->| 211 | 208 | 205 | 202 | ------------- | 112 |
         +-----+-----+-----+-----+---------------+-----+
         (б) Џосле освобождениЯ блока с номером 949

          список в суперблоке
         +-----+-----+-----+-----+---------------------+
         | 109 | 106 | 103 | 100 | ------------------- |
         +--+--+-----+-----+-----+---------------------+
      +-----+
      |  109
      |  +-----+-----+-----+-----+---------------+-----+
      +->| 211 | 208 | 205 | 202 | ------------- | 112 |
         +-----+-----+-----+-----+---------------+-----+
         (в) Џосле назначениЯ блока с номером 949

                                     82


          список в суперблоке
         +-----+-----+-----+-----+---------------+-----+
         | 211 | 208 | 205 | 202 | ------------- | 112 |
         +--+--+-----+-----+-----+---------------+-----+
      +-----+
      |  211
      |  +-----+-----+-----+-----+---------------+-----+
      +->| 344 | 341 | 338 | 335 | ------------- | 243 |
         +-----+-----+-----+-----+---------------+-----+

         (г) Ќовое заполнение списка в суперблоке после
             назначениЯ блока с номером 109

    ђисунок 4.20. ‡апрашивание и освобождение дисковых блоков


        4.8 „ђ“ѓ€… ’€Џ› ”Ђ‰‹Ћ‚

    ‚  системе UNIX поддерживаютсЯ и два других типа файлов: каналы и специ-
альные   файлы.   Љанал,   иногда    называемый    fifo    (сокращенно    от
"first-in-first-out" - "первым пришел - первым вышел" - поскольку обслужива-
ет запросы в порЯдке поступлениЯ), отличаетсЯ от обычного файла тем, что со-
держит  временные  данные: информациЯ, однажды считаннаЯ из канала, не может
быть прочитана вновь. Љроме того, информациЯ читаетсЯ в том порЯдке, в кото-
ром она была записана в канале, и система не допускает никаких отклонений от
данного порЯдка. ‘пособ хранениЯ Ядром информации в канале не отличаетсЯ  от
способа  ее хранениЯ в обычном файле, за исключением того, что здесь исполь-
зуютсЯ только блоки прЯмой, а не косвенной, адресации. Љонкретное  представ-
ление о каналах можно будет получить в следующей главе.
    Џоследним  типом файлов в системе UNIX ЯвлЯютсЯ специальные файлы, к ко-
торым относЯтсЯ специальные файлы устройств ввода-вывода блоками и специаль-
ные файлы устройств посимвольного ввода-вывода. Ћба подтипа обозначают  уст-
ройства,  и  поэтому индексы таких файлов не свЯзаны ни с какой информацией.
‚место этого индекс содержит два номера - старший и младший номера устройст-
ва. ‘тарший номер устройства указывает его тип, например, терминал или диск,
а младший номер устройства - числовой  код,  идентифицирующий  устройство  в
группе однородных устройств. Ѓолее подробно специальные файлы устройств рас-
сматриваютсЯ в главе 10.


        4.9 ‚›‚Ћ„›


    €ндекс  представлЯет собой структуру данных, в которой описываютсЯ атри-
буты файла, в том числе расположение информации файла на  диске.  ‘уществует
две разновидности индекса: копиЯ на диске, в которой хранитсЯ информациЯ ин-
декса, пока файл находитсЯ в работе, и копиЯ в памЯти, где хранитсЯ информа-
циЯ об активных файлах. Ђлгоритмы ialloc и ifree управлЯют назначением файлу
дискового  индекса во времЯ выполнениЯ системных операций creat, mknod, pipe
и unlink (см. следующую главу), а алгоритмы iget и iput управлЯют выделением
индексов в памЯти в момент обращениЯ процесса к файлу. Ђлгоритм bmap опреде-
лЯет местонахождение дисковых блоков, принадлежащих файлу, используЯ предва-
рительно заданное смещение в байтах от начала файла.  Љаталоги  представлЯют
собой файлы, которые устанавливают соответствие между компонентами имен фай-
лов и номерами индексов. Ђлгоритм namei преобразует имена файлов, с которыми
работают  процессы, в идентификаторы индексов, с которыми работает Ядро. Ќа-
конец, Ядро управлЯет назначением файлу новых дисковых блоков, используЯ ал-
горитмы alloc и free.

                                     83

    ‘труктуры данных, рассмотренные в настоЯщей главе, состоЯт из  свЯзанных
списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с
рассмотренными  структурами  данных, достаточно просты. ‘ложности поЯвлЯютсЯ
тогда, когда возникает конкуренциЯ,  вызываемаЯ  взаимодействием  алгоритмов
между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте.
’ем  не  менее,  алгоритмы не настолько детально разработаны и могут служить
иллюстрацией простоты конструкции системы.
    ‚ышеописанные структуры и алгоритмы работают внутри Ядра и невидимы  длЯ
пользователЯ.  ‘ точки зрениЯ общей архитектуры системы (ђисунок 2.1), алго-
ритмы, рассмотренные в данной главе, имеют отношение к нижней половине  под-
системы  управлениЯ  файлами.  ‘ледующаЯ глава посвЯщена разбору обращений к
операционной системе, обеспечивающих функционирование пользовательского  ин-
терфейса,  и описанию верхней половины подсистемы управлениЯ файлами, из ко-
торой вызываетсЯ выполнение рассмотренных здесь алгоритмов.

8. ‚ версии V системы UNIX разрешаетсЯ использовать не более 14 символов  на
   каждую  компоненту имени пути поиска. Ђлгоритм namei отсекает лишние сим-
   волы в компоненте. —то нужно сделать в файловой системе и в соответствую-
   щих алгоритмах, чтобы стали допустимыми имена компонент произвольной дли-
   ны ?
9. Џредположим, что пользователь имеет закрытую версию системы UNIX,  причем
   он  внес  в нее такие изменениЯ, что имЯ компоненты теперь может состоЯть
   из 30 символов; закрытаЯ версиЯ системы обеспечивает тот же способ хране-
   ниЯ записей каталогов, как и стандартнаЯ операционнаЯ система, за  исклю-
   чением  того,  что  записи каталогов имеют длину 32 байта вместо 16. …сли
   пользователь смонтирует закрытую файловую систему в стандартной  операци-
   онной  среде,  что произойдет во времЯ работы алгоритма namei, когда про-
   цесс обратитсЯ к файлу ?
*10. ђассмотрим работу алгоритма namei по преобразованию имени пути поиска в
   идентификатор индекса. ‚ течение всего просмотра Ядро проверЯет соответс-
   твие текущего рабочего индекса индексу каталога. Њожет ли другой  процесс
   удалить  (unlink) каталог ? Љаким образом Ядро предупреждает такие дейст-
   виЯ ? ‚ следующей главе мы вернемсЯ к этой проблеме.
*11. ђазработайте структуру каталога, повышающую эффективность  поиска  имен
   файлов  без  использованиЯ  линейного просмотра. ђассмотрите два способа:
   хеширование и n-арные деревьЯ.
*12. ђазработайте алгоритм сокращениЯ количества просмотров каталога в поис-
   ках имени файла, используЯ запоминание часто употреблЯемых имен.
*13. ‚ идеальном случае в файловой системе не должно быть свободных индексов
   с номерами, меньшими, чем номер "запомненного" индекса, используемый  ал-
   горитмом ialloc. Љак случаетсЯ, что это утверждение бывает ложным ?
14.  ‘уперблок  ЯвлЯетсЯ  дисковым  блоком и содержит кроме списка свободных
   блоков и другую информацию, как показано в данной главе.  Џоэтому  список
   свободных блоков в суперблоке не может содержать больше номеров свободных
   блоков,  чем  может поместитьсЯ в одном дисковом блоке в свЯзанном списке
   свободных дисковых блоков. Љакое число номеров свободных блоков  было  бы
   оптимальным длЯ хранениЯ в одном блоке из свЯзанного списка ?


                                     84