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

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

способен диск. Таким образом, непрерывные файлы легко реализуются и обладают высокой производительностью.

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

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

Списки

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

Файл А

Физический 4 блок

БпокО файла

Блок 1 файла

Блок 2 файла

БлокЗ файла

Блок 4 файла

Файл В

БлокО файла

Блок 1 файла

Блок 2 файла

Блок 3 файла

Физический блок

Рис. 5.6. Размещение файла в виде связного списка блоков диска

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

С другой стороны, хотя последовательный доступ к такому файлу несложен, произвольный доступ будет довольно медленным. Чтобы получить доступ к бло-



ку п, операционная система должна сначала прочитать первые п-1 блоков по очереди. Очевидно, такая схема оказывается очень медленной.

Список с индексацией

Оба недостатка предыдущей схемы организации файлов в виде списков могут быть устранены, если указатели на следующие блоки хранить не прямо в блоках, а в отдельной таблице, загружаемой в память. На рис. 5.7 показан внешний вид такой таблицы для файлов с рис. 5.6. На обоих рисунках показаны два файла. Файл А занимает блоки диска 4, 7, 2, 10 и 12, а файл В - блоки 6, 3, 11 и 14. С помощью таблицы мы можем начать с блока 4 и следовать по цепочке до конца файла. Те же действия применимы для второго файла, если начать с блока 6. Обе цепочки завершаются специальным маркером (например, 1), не являющимся допустимым номером блока. Такая таблица, загружаемая в оперативную память, называется FAT (File Allocation Table - таблица размещения файлов).

Физический блок

<- Файл А начинается здесь

- Файл В начинается здесь

4- Неиспользуемый блок

Рис. 5.7. Таблица размещения файлов

При такой организации все блоки доступны для данных. Кроме того, значительно упрощается произвольный доступ. Хотя для обращения к какому-либо блоку файла все равно понадобится проследовать по цепочке по всем ссылкам вплоть до требуемого блока, в данном случае вся цепочка ссылок уже хранится в памяти и ее прохождение не требует дополнительных дисковых операций. Как и в предыдущем случае, в каталоге достаточно хранить один целый индекс (номер начального блока файла) для обеспечения доступа ко всем частям файла.



Основной недостаток этого метода состоит в том, что вся таблица должна постоянно находиться в памяти. Для 500-мегабайтового диска с блоками размером 1 Кбайт потребовалась бы таблица из 500 ООО записей, по одной для каждого из 500 ООО блоков диска. Каждая запись должна состоять как минимум из трех байтов. Для ускорения поиска размер записей должен быть увеличен до 4 байт. Таким образом, резидентная таблица будет занимать 1,5 или 2 Мбайт оперативной памяти. Таблица, конечно, может быть размещена в виртуальной памяти, но и в этом случае ее размер оказывается чрезмерно большим, к тому же постоянная выгрузка таблицы на диск и загрузка ее с диска существенно снизят производительность файловых операций.

1-узлы

Последний метод отслеживания принадлежности блоков диска файлам заключается в связывании с каждым файлом структуры данных, называемой i-узлом (index node - индекс-узел), содержащей атрибуты файла и адреса блоков файла. Простой пример f-узла показан на рис. 5.8. При наличии г-узла можно найти все блоки файла. Большое преимущество такой схемы перед хранящейся в памяти таблицей из списков состоит в том, что каждый конкретный г-узел должен находиться в памяти только тогда, когда соответствующий ему файл открыт. Если каждый г-узел занимает п байтов, а одновременно открыть можно k файлов, для массива г-узлов потребуется в памяти всего kn байтов.

1-узел

Однократный косвенный блок

Адреса блоков данных


Рис. 5.8. Пример i-узла



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.
Копирование материалов разрешено исключительно при условии цититирования.