Файл: Учебнометодическое пособие Томск 2016 2 удк 004. 451(075. 8) Ббк 32. 973. 2018. 2я73 к 754 Рецензенты.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 348
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
193 зависимости от типа ОС. Кроме того, заметим, что название fat является со- бирательным, объединяющим три реальных ФС: fat12,fat16и fat32.
7.2.2 Физическое размещение информации на носителе
Оценки реальной ФС по критериям производительности, надежности, а также используемости ВП в значительной степени зависят от физического размещения информации, используемого в данной системе. Так как наиболее распространенными носителями ВП являются магнитные диски, то далее будет рассмотрено размещение информации на этих носителях. В данном подпара- графе рассмотрим общие свойства таких носителей, а далее рассмотрим влия- ние этих свойств на реальную ФС.
Упрощенное представление магнитного диска приведено на рисунке 7.3.
Этот диск состоит из одной, двух или большего числа металлических или стек- лянных пластин, вращающихся вокруг общей оси. Одна или обе поверхности каждой пластины покрыты тонким однородным слоем магнитного материала.
Подобная поверхность пластины условно разделена на тонкие кольца, называе- мые дорожками. Все дорожки на каждой пластине пронумерованы, причем до- рожка 0 находится около внешнего края пластины. Все дорожки диска, имею- щие одинаковый номер, принадлежат одному цилиндру, номер которого определяется номерами входящих в него дорожек. Например, цилиндр 0 объ- единяет дорожки с номерами 0 (рис. 7.3).
Рис. 7.3 Упрощенное представление магнитного диска
194
Для чтения (записи) информации с пластины (на пластину) используется один или несколько элементов, называемых головками. Количество головок за- висит от используемого варианта конструкции дисковода. В первом из этих ва- риантов каждую поверхность пластины обслуживает единственная головка, ко- торая может перемещаться по радиусу диска дискретными шагами. При этом каждый шаг соответствует одной дорожке пластины. После того как головка
«зависнет» над требуемой пластиной, она может выполнять информационный обмен с этой дорожкой. Так как все головки диска связаны жестко в единую
«гребенку», то при установке одной из головок на требуемую дорожку все остальные головки «зависнут» над дорожками этого же цилиндра. Следствием этого является то, что переход между дорожками одного цилиндра не требует каких-либо механических перемещений головок. Для такого перехода доста- точно лишь выполнить электронное переключение головок. Другой вариант конструкции дисковода предполагает, что каждую дорожку поверхности пла- стины обслуживает своя отдельная головка. В этом случае никакого перемеще- ния головок не производится, так как для выбора требуемой дорожки достаточ- но лишь электронно включить требуемую головку.
Что касается информационного обмена с дорожкой, то он производится следующим образом. Во-первых, заметим, что магнитная поверхность дорожки состоит из маленьких фрагментов, называемых магнитными доменами.
Во время движения дорожки мимо головки (вследствие вращения диска) маг- нитное поле головки может повлиять на полярность того домена, который находится в данный момент времени рядом с головкой. Благодаря этому маг- нитный домен может использоваться для записи одного бита информации.
При этом одна полярность домена кодирует 0, а другая – 1. Во время чтения информации с диска, наоборот, полярность текущего домена влияет на магнит- ное поле головки. Это состояние магнитного поля считывается в электронную цепь и распознается ею как 0 или 1. Несмотря на то что длины дорожек на пла- стине разные, все они содержат одинаковое количество доменов, кодирующих биты.
Поверхность пластины, как и любой круг, можно разделить на угловые секторы (рис. 7.3). Возьмем размер углового сектора таким, чтобы он «выре- зал» из каждой дорожки на поверхности пластины дугу, содержащую 512 бит.
Эта дуга дорожки называется сектором. Как видно из рисунка 7.3, один угло- вой сектор «вырезает» секторы одинаковой длины (измерение в битах) не толь- ко на одной поверхности одной пластины, но и на всех поверхностях всех пла-
195 стин. Разбиение дорожки диска на секторы производится во время низкоуровне-
вого форматирования диска. Во время этого форматирования начало каждого сектора помечается специальной последовательностью битов. Кроме того, для каждого сектора записывается его номер.
С точки зрения ОС сектор является минимальной единицей информаци- онного обмена между диском и ОП. Для выполнения такого обмена каждый сектор задается своим адресом:
(номер цилиндра; номер поверхности; номер сектора).
Среднее время чтения (записи) одного сектора T
c
можно найти по форму- ле:
c
v
r
d
T
T
T
T
, где T
d
– среднее время установки головки на требуемую дорожку. Типичное значение этого времени для современных дисков составляет от 5 до 10 мс;
T
v
– среднее время вращения диска до достижения требуемого сектора. Не- трудно заметить, что это время выполнения диском половины своего оборота, которое в свою очередь определяется скоростью вращения диска: T
v
= 1/2n, где n – скорость вращения диска (об/с). Гибкие маг- нитные диски имеют скорость вращения 5–10 об/с, а жесткие –
9–170 об/с. Например, при скорости вращения 170 об/с среднее время вращения диска до достижения требуемого сектора составляет при- мерно 3 мс;
T
r
– время непосредственного считывания (записи) одного сектора. Так как это время поворота диска на заданный угловой сектор, то его можно определить по формуле:
1/
r
T
n L
, где L – число секторов на дорожке. Например, если диск имеет на каждой дорожке
320 секторов, а его скорость вращения n = 170 об/с, то для него
1 / 170 320 0,018 мс
r
T
Приведенные формулы могут быть использованы для приблизительной оценки производительности различных реальных ФС. Но при этом надо учесть, что в качестве единицы информационного обмена с диском любая реальная ФС использует не сектор, а более крупную величину – блок. Блок – часть дорожки диска, состоящая из одного или нескольких секторов. Длина блока для каждой информационной части реальной ФС является величиной фиксированной и равняется размеру сектора диска, умноженному на степень двойки:
196 512 байт
N,где N = 1, 2, 4, ... . Заметим, что блок в MS-DOSи Windows назы- вается кластером. В отличие от сектора имя блока не связано с его физическим размещением на диске, а представляет собой порядковый номер в пределах данной информационной части реальной ФС. Блок является той единицей про- странства ВП, которая используется ОС при распределении этого пространства между файлами.
После того как проведено разбиение диска на разделы (если это требует- ся), для каждого раздела производится свое отдельное высокоуровневое фор-
матирование. Во время этого форматирования в разделе размещаются управ- ляющие структуры той реальной ФС, одна из информационных частей которой будет размещаться в данном разделе. При этом среди прочей управляющей ин- формации записывается размер блока, выбранный для данного раздела. Заме- тим, что размеры блоков разных разделов диска могут быть разными.
Допустим, что размер блока составляет 4 K (8 секторов). С учетом того что секторы одного блока расположены последовательно на одной и той же до- рожке, для приведенных выше численных параметров среднее время чтения
(записи) одного блока составит T
b
:
8 10 мс + 3 мс + 8 0,018 мс = 13,144 мс
v
r
b
d
T
T
T
T
Очень часто требуется считать (записать) не один блок файла, а целую последовательность таких блоков. В этом случае затраты на обработку каждого блока приведенного выше среднего времени приведут к очень большому сум- марному времени на обработку данного файла. Например, пусть требуется счи- тать 1 000 блоков файла. Если эти блоки разбросаны (в результате распределе- ния ВП файлу) по всему разделу, то общее время чтения будет очень велико:
1 1 000 1 000 13,144 мс
13,144 с
b
T
T
Для увеличения производительности реальной ФС необходимо локализо- вать размещение блоков файла на диске так, чтобы они находились если не в пределах одного цилиндра, то в пределах близких цилиндров. Например, если все 1 000 блоков нашего файла расположены на 4 дорожках одного и того же цилиндра, то среднее время их чтения или записи составит:
2 4
1000 8 10 мс + 4 3 мс 1000 8 0,018 мс 0,116 с.
v
r
d
T
T
T
T
Полученное время чтения файла T
2
меньше времени T
1 соответствующего чтения при произвольном размещении блоков на диске почти в 80 раз. Времена
T
1
и T
2
соответствуют крайним случаям размещения блоков файла на диске.
197
Первый из этих случаев имеет место при реализации наиболее простых алго- ритмов динамического распределения ВП между файлами. Второй случай воз- можен только при статическом распределении.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1 ... 15 16 17 18 19 20 21 22 23
Статическое распределение ВП – вся память назначается
файлу при его создании.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
В этом случае нетрудно обеспечить размещение блоков небольшого фай- ла на одном цилиндре, а большого – на нескольких соседних цилиндрах. Очень большим недостатком статического распределения является очень низкая ис- пользуемость ВП для многих типов файлов. Причиной этого является необхо- димость одновременного выделения такой памяти файлу, значительная часть которой не понадобится для размещения данных файла в ближайшем будущем.
Другая значительная часть выделенной ВП, возможно, вообще останется невос- требованной, так как для многих файлов нельзя заранее точно предсказать их длину. С учетом данного недостатка статическое распределение дисковой па- мяти в настоящее время используется лишь для cd-дисков, так как длины фай- лов, размещаемых на таких дисках, заранее точно известны.
Что касается магнитных дисков, то размещаемые на них реальные ФС ис- пользуют только динамическое распределение ВП между файлами. При таком распределении блоки ВП назначаются файлу не при его создании, а в процессе его эксплуатации: если при получении от виртуальной ФС указания выполнить запись в файл некоторого числа байтов, реальная ФС обнаружила, что для за- писи этих байтов не хватает места на ранее выделенных файлу блоках, то эта реальная ФС (программная часть) выделяет этому файлу новый блок диска.
Простейшие алгоритмы динамического распределения не учитывают ранее проведенного назначения блоков диска файлу, динамически выдавая ему любой свободный блок раздела диска. Такие алгоритмы реализованы, например, в ре- альных ФС s5fsи fat. Эти реальные ФС обладают хорошей используемо- стью ВП (для распределения пригоден любой свободный блок раздела), но весьма низкой производительностью.
Гораздо лучшую производительность имеет реальная ФС ffs. Для этой системы характерно то, что при высокоуровневом форматировании раздел дис- ка, занимаемый этой системой, делится на несколько групп цилиндров. Группа
цилиндров – несколько соседних цилиндров (см. рис. 7.3). В начале этой группы находится управляющая информация, в том числе дисковые блоки управления
198 файлами – inode. При создании файла его inode помещается в одну из групп цилиндров. При выборе этой группы используются соображения:
1) если создается не каталог, а файл данных, то желательно поместить inode файла в ту группу цилиндров, куда ранее был помещен роди- тельский каталог. Это позволяет повысить производительность реаль- ной ФС при обслуживании многих программ, выполняющих обработ- ку файлов из одного каталога;
2) если создается каталог, то его inode желательно поместить в группу цилиндров, отличную от группы цилиндров, в которой находится ро- дительский каталог. Это позволяет улучшить равномерность распре- деления данных по диску.
Если при выполнении очередной операции записи в файл ему требуется выделить новый блок памяти, то этот блок выбирается, по возможности, из той же группы цилиндров, где находится inode файла. Это позволяет сократить не только время перехода между блоками данных, но и время перехода от inode файла к его блокам данных.
Если раздел диска, занимаемый системой ffs, включает всего одну группу цилиндров, то эта система не обладает лучшей производительностью по сравнению с s5fs. При наличии нескольких групп цилиндров система ffs имеет достаточно хорошую производительность лишь при ограниченной ис- пользуемости ВП (не более 90%). При более высокой степени загрузки диска распределение свободных блоков фактически производится случайным обра- зом, то есть без соблюдения перечисленных выше рекомендаций.
В заключение данного подпараграфа рассмотрим вопрос о выборе разме- ра блока (кластера) с точки зрения производительности реальной ФС и прису- щей ей используемости ВП. С учетом того что содержимое блока всегда нахо- дится на одной дорожке (или в одном цилиндре), увеличение размера блока приводит к увеличению производительности системы, так как при одних и тех же накладных расходах времени (T
d
+ T
v
) удается выполнить больший инфор- мационный обмен между ОП и диском. Но с другой стороны, увеличение раз- мера блока в системах s5fsи fat приводит к существенному снижению ис- пользуемости ВП, так как в этих системах блок является минимальной единицей распределяемой ВП. И поэтому даже очень небольшому файлу выде- ляется целый блок диска. В результате при наличии большого числа таких фай- лов в системе значительный объем дисковой памяти фактически не использует-
199 ся. Во-вторых, каждому файлу, занимающему более одного блока, в среднем соответствует половина неиспользуемого дискового блока, в котором находят- ся последние байты файла.
Для того чтобы обеспечить хорошую используемость ВП при использо- вании блоков большого размера, в реальной ФС ffs применяется фрагмента-
ция блоков – логическое разбиение блока на два, четыре, восемь или более фрагментов одинаковой длины. При этом минимально допустимый размер фрагмента определяется размером сектора (512 байт). В результате такой фраг- ментации единицей распределения ВП становится фрагмент. Что касается бло- ка, то он по-прежнему остается единицей информационного обмена между дис- ком и ОП.
7.2.3 Каталоги
Напомним (см. п. 2.2), что каталог представляет собой служебный файл, содержащий сведения о других файлах, в том числе, возможно, и о других ка- талогах. Благодаря наличию каталогов все физические файлы, принадлежащие одной и той же информационной части реальной файловой системы, оказыва- ются логически связанными в единую информационную структуру в виде дере- ва. Одна логическая запись (элемент) каталога содержит сведения об одном до- чернем файле или каталоге.
Система s5fs. В реальной файловой системе s5fs одна логическая за- пись каталога содержит минимум информации о дочернем файле (каталоге):
1) номер inode файла (2 байта). Этот номер представляет собой уни- кальное имя файла в пределах конкретной информационной части ре- альной ФС. Нулевой номер inode обозначает удаленный файл. По- этому при удалении файла реальная ФС (программная часть) заменяет номер его inode на 0;
2) простое имя файла (14 байтов). Первый элемент каталога содержит имя «.», обозначающее сам этот каталог. Второй элемент каталога со- держит имя «..», обозначающее родительский каталог по отношению к рассматриваемому каталогу.
Длины этих полей логической записи каталога определяют две характе- ристики всей реальной ФС:
1) предельное число файлов: 2 16
– 1 = 65 536 – 1 = 65 535;
2) предельная длина имени файла – 14 символов.
200
Система ffs. Для преодоления второго ограничения реальная файловая системаffs использует следующую структуру каталога:
1) номер inode файла (2 байта);
2) длина (в байтах) поля, содержащего простое имя файла (2 байта);
3) длина (в байтах) простого имени файла (2 байта);
4) простое имя файла (поле имеет переменную длину до 255 байтов).
Данное поле дополняется нулями до 4-байтной границы.
При удалении файла вся логическая запись каталога, соответствующая удаляемому файлу, подсоединяется к концу поля с именем файла в предыдущей логической записи этого же каталога. При этом корректируется длина этого по- ля.
Что касается ограничения на предельное число файлов, то оно легко пре- одолевается удлинением того поля элемента каталога, которое отводится под номер inode. Удлинение этого поля всего на один бит увеличивает предельное число файлов в два раза. В системе ffs такое увеличение не делается.
Система fat. В отличие от файловых систем s5fs и ffs, каталоги ко- торых содержат минимум информации о дочерних файлах, каждый элемент ка- талога в системе fatфактически содержит дескриптор (блок управления) до- чернего файла. Перечислим поля 32-байтного элемента каталога в системе fat12:
1) простое имя файла (11 байт, из которых 3 байта отводятся под расши- рение имени);
2) флаги атрибутов файла (1 байт). Например, бит 0 – файл «только для чтения» (данный файл нельзя открыть для записи), бит 4 – файл явля- ется каталогом;
3) свободное поле (10 байт);
4) время создания или последнего изменения (2 байта);
5) дата создания или последней модификации (2 байта);
6) номер начального блока (кластера) файла (2 байта);
7) размер файла (4 байта).
Как видно из данного перечня полей каталога, предельная длина имени файла вfat12(и в fat16) всего 11 символов, из которых 8 символов – пре- дельная длина собственно имени файла, а 3 символа – предельная длина рас- ширения имени файла. Для преодоления этого ограничения в реальной ФС fat32каждому файлу соответствуют несколько 32-байтовых записей каталога.