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

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

В каждом каталоге есть записи с именами . и которые добавляются при создании каталога. Записи . соответствует г-узел самого каталога, а ссылается на г-узел каталога верхнего уровня. Таким образом, если дано имя файла ../dick/prog.с, система найдет в текущем каталоге, получит г-узел родительского и будет искать в нем dick. Для обработки таких имен не применяется никаких специальных алгоритмов. С точки зрения системы каталогов, это обычные ASCII-строки, ничем не отличающиеся от прочих имен.

5.3.3. Организация дискового пространства

Обычно файлы хранятся на диске, поэтому организация дискового пространства является основной заботой разработчиков файловой системы. Для хранения файла из п байтов возможны две стратегии: выделение на диске п последовательных байтов или разбиение файла на несколько непрерывных блоков. Та же дилемма присутствует в системах управления памяти, где имеется выбор между чистой сегментацией и страничной организацией памяти.

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

Размер блока

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

Если выбрать большую единицу хранения, такую как цилиндр, это будет означать, что любой файл, даже состоящий из одного байта, займет как минимум целый цилиндр. Опыт показал, что средний размер файла в системе UNIX около 1 Кбайт, поэтому при выделении каждому файлу 32-килобайтового блока будет расходоваться понапрасну 31/32 или 97 % общего дискового пространства [90].

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

Например, представьте себе диск с 131 072 байтами (128 Кбайт) на дорожку, периодом вращения 8,33 мс и средним временем поиска 10 мс. При этом время.



требующееся для чтения блока из k байтов, будет равно сумме времени поиска, ожидании поворота и времени переноса данных:

10 + 4,165 + {k/ШШ) X 8,33.

Жирная кривая на рис. 5.13 показывает зависимость скорости передачи данных от размера блока. Если мы предположим, что файлы в основном имеют размер 1 Кбайт (медианный размер), то прерывистая линия на рис. 5.13 отразит эффективность задействования дискового пространства. Плохие новости в том, что эффективное использование места на диске (блок меньще 2 Кбайт) сопряжено с низкой пропускной способностью, и наоборот.

Поэтому обычно выбирается компромиссное рещение, и размер блока делается равным 512 байт, 1 Кбайт или 2 Кбайт. Если сектор диска имеет размер 512 байт, а блока - 1 Кбайт, то файловая система всегда будет считывать или записывать два последовательных сектора, рассматривая их как единый, неделимый элемент. Какое бы решение ни было принято, его необходимо периодически пересматривать, так как по мере развития технологий пользователи, получив больше ресурсов, начинают требовать еще больше. Один из системных администраторов сообщил нам, что средний размер файлов в университетской системе медленно возрастал год за годом и к 1997 году достиг 12 Кбайт для студентов и 15 Кбайт для факультета.

1-узел 6 содержит данные

Корневой каталог о каталоге /usr

Блок 132 содержит каталог 132

1-узел 26 содержит

о каталоге /usr/ast

Блок 40S содержит каталог /usr/ast

Размер Времена

dick

ел1<

Режимный код Размер Времена

grants

boolts

mbox

minix

В результате

поиска элемента usr получаем нуэел 6

Bi-узлеб указывается, что /usr находится в блоке 132

Запись/usr/ast ссылается на 1-узел 26

В i-узле 26 указывается, что /usr/ast находится в блоке 406

Запись /usr/ast/ml x ссылается на 1-узвл 60

Рис. 5.13. Зависимость скорости чтения/записи данных диска (жирная линия, левая шкала) и эффективности использования дискового пространства (штриховая линия, правая шкала) от размера блоков. Все файлы по 2 Кбайт

Учет свободных блоков

После того как мы выбрали размер блоков, следует определиться, как учитывать свободные и занятые блоки. Широкое распространение получили два метода, представленные на рис. 5.14. Первый метод - не что иное, как использование списка блоков диска. При этом в каждом блоке списка содержится столько номеров свободных блоков, сколько может поместиться в один блок. При размере блока, равном 1 Кбайт, и 32-разрядных номерах блоков каждый блок списка свободных блоков может содержать номера 255 свободных блоков. (Одно 32-разрядное слово



нужно для указателя на следующий блок списка.) Для 16-гигабайтового диска потребуется список свободных блоков, состоящий из 16 794 блоков, чтобы охватить все 2 дисковых блока. Часто для списка резервируется нужное число блоков в начале диска.

Блоки диска 16, 17, 18

1-килобайтный блок диска может содержать 256 32-разрядных номеров блока

1001101101101100

0110110111110111

1010110110110110

0110110110111011

1110111011101111

1101101010001111

0000111011010111

г 48

1011101101101111

1100100011101111

г

S

i я

i S

0111011101110111

1101111101110111

Битовый массив

Рис. 5.14. a - хранение информации о свободных блоках в виде списка; б - битовый

массив

Другой метод учета свободного дискового пространства заключается в хранении этой информации в виде битового массива (битовой карты). Здесь на каждый блок приходится всего по одному биту вместо 32. Свободные блоки обозначаются в массиве единицами, а занятые - нулями (или наоборот). 16-гигабайтовый диск состоит из 2 килобайтовых блоков, таким образом, для него требуется массив размером 2 бит, то есть 2048 блоков, что меньше, чем потребовалось бы для организации списка. Схема на основе списка более эффективна только тогда, когда диск практически полон.

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



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