Главная страница  Межпроцессное взаимодействие (состязание) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 [ 165 ] 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

64 байта <

16 бит л

- Время доступа

- Время модификации

- Время изменения состояния

Режим

Число ссылок

Размер файла

- Зона О

- Зона 1

- Зона 2

- Зона 3

- Зона 4

- Зона 5

- Зона 6

- Косвенная зона

- Косвенная зона второго уровня

- Не используется

Тип файла и биты rwx Записи в директориях для этого файла Идентифицирует владельца файла Группа владельца

Количество байт в файле

Время измеряется в секундах с 1 января 1970 года

Номера семи первых зон

Используются для файлов, занимающих больше семи зон

Можно использовать для косвенных зон третьего уровня вложенности

Рис. 5.2в. Структура i-узла в MINIX

5.6.5. Кэш блоков

Для повышения производительности файловой системы в MINIX применяется кэширование блоков. Кэш реализован в виде массива буферов, каждый из которых состоит из заголовка, содержащего указатели, счетчики и флаги, и тела - области памяти для хранения одного блока. Все неиспользуемые буферы связаны друг с другом в двунаправленный список, отсортированный от недавно использованных (MRU) к последним использованным (LRU). Это изображено на рис. 5.27.

С целью быстрого извлечения из кэша нужного блока применяется цепочечный хеш. Все буферы, имеющие одинаковое хеш-значение k, сцеплены в однонаправленный список, на который ссылается запись k хеш-таблицы. Сделано так



по той причине, что применяемая хеш-функция просто извлекает п младших битов из номера блока, и хеш-значения могут совпадать. Каждый буфер принадлежит одной из цепочек. Конечно, сразу после загрузки MINIX все буферы свободны, поэтому все они находятся в одной цепочке, на которую ссылается нулевой элемент хеш-таблицы. Все остальные элементы таблицы в это время содержат нулевые указатели. Но после того, как система начнет работу, буферы будут исключаться из нулевой цепочки и будут формироваться новые цепочки.

Хеш-таблица Фронт (LRU)

Тыл (MRU)


Рис. 5.27. Связный список кэша блоков

Если файловой системе необходим блок, она вызывает функцию get block. Эта функция вычисляет хеш-код блока и ищет его в соответствующем списке. При вызове get block ей передается как номер блока, так и номер устройства, и при поиске оба эти параметра сравниваются с соответствующими полями буферов из цепочки. Если нужный блок найден, увеличивается на единицу значение счетчика в его заголовке и возвращается указатель на него. Если затребованный буфер в кэше не обнаруживается, выбирается первый из LRU-списка; он гарантированно не используется, и содержащийся в нем блок может быть удален из оперативной памяти.

Когда удаляемый из памяти блок выбран, проверяется один из флагов в его заголовке, означающий, что блок был модифицирован после считывания. Если флаг установлен, блок записывается на диск. Затем с диска считывается нужный блок, для этого отправляется сообщение задаче диска. До тех пор пока запрошенный блок не будет прочитан, файловая система приостанавливается, а после этого возвращает указатель на прочитанный блок.

По окончании работы запросившей блок процедуры, чтобы освободить блок, она вызывает другую процедуру, put block. Обычно блок используется сразу после выделения и затем освобождается, но так как сушествует возможность того, что перед освобождением блока будут сделаны дополнительные запросы, функция put bbck сначала уменьшает на единицу счетчик использования и помещает блок обратно в LRU-список в том и только том случае, если счетчик достиг нуля. Если он имеет ненулевое значение, блок не освобождается.

Один из аргументов put block описывает, к какому классу принадлежит освобождаемый блок (то есть г-узлы, каталоги, данные). В зависимости от этого значения принимаются два ключевых решения.



1. Поместить блок в начало или в конец LRU-списка.

2. Записать блок на диск немедленно (если он был модифицирован).

Блоки, которые с малой вероятностью скоро потребуются, например суперблоки, помещаются в начало списка, поэтому, когда в следующий раз потребуется свободный буфер, он будет взят из начала. Все остальные блоки присоединяются в конец списка, в полном соответствии с идеей сортировки по частоте использования.

Модифицированный блок не записывается до тех пор, пока не произойдет одно из двух следующих событий.

1. Блок достиг начала LRU-списка и изгоняется из памяти.

2. Выполнен системный вызов sync.

Вызов sync не перебирает элементы LRU-списка. Вместо этого он обрабатывает массив буферов и записывает модифицированные буферы на диск даже в том случае, если они еще используются.

Тем не менее есть одно исключение. Модифицированный суперблок записывается на диск немедленно. В старой версии MINIX суперблок модифицировался при монтировании системы, поэтому, чтобы уменьшить вероятность повреждения файловой системы по причине неожиданного сбоя, он сохранялся без промедления. Сейчас суперблок не модифицируется, и код, отвечающий за его срочную запись, является анахронизмом. В стандартной конфигурации никакие другие блоки не записываются сразу. Но это поведение можно изменить, варьируя значение параметра ROBUST в файле конфигурации системы, include/minix/config.h. С его помощью можно сделать так, чтобы файловая система помечала г-узлы, каталоги, блоки косвенной адресации и блоки битовых карт как записываемые незамедлительно. Это должно сделать файловую систему более устойчивой, но ценой устойчивости является потеря производительности. Не совсем ясно и то, насколько это эффективно. Сбой питания, произошедший, когда еще не все блоки записаны на диск, вызовет головную боль, будь то блоки с данными или г-узлами.

Заметьте, что флаг в заголовке, означающий, что блок был модифицирован, устанавливается процедурой в файловой системе, которая его запросила и использует. Процедуры get block и put block занимаются только манипуляциями с однонаправленными списками. Они не имеют представления о том, какой процедуре файловой системы какой блок нужен и зачем.

5.6.6. Каталоги и пути

Другой важной составляющей файловой системы является система управления каталогами и путями. Многие системные вызовы, такие как open, в качестве аргумента принимают имя файла. Но в действительности нужен номер г-узла этого файла, поэтому файловая система должна просмотреть дерево каталогов и найти нужный г-узел.

В MINIX каталог состоит из файла, содержащего 16-байтовые записи. Первые два байта из шестнадцати формируют 16-битный номер г-узла, а оставшиеся 14 образуют имя файла. Это соответствует традиционной структуре каталога.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 [ 165 ] 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

© 2000 - 2018 ULTRASONEX-AMFODENT.RU.
Копирование материалов разрешено исключительно при условии цититирования.