Битовые карты блоков и фрагментов
Состояние выделения блоков и фрагментов определяется по битовым картам. В действительности информация о каждом блоке UFS хранится в двух битовых картах: битовой карте фрагментов и битовой карте блоков.
Учтите, что эти битовые карты хранят информацию в формате, обратном тому, который обычно используется на практике: их биты устанавливаются в 1 для свободных объектов, и сбрасываются в 0 для выделенных объектов.Начнем с битовой карты фрагментов. Для каждой группы цилиндров ведется битовая карта фрагментов, которая хранится в дескрипторе группы. Смещение битовой карты в байтах задается в дескрипторе, а ее размер определяется по количеству фрагментов в группе. Чтобы найти бит, представляющий конкретный фрагмент, следует определить его адрес относительно начала группы цилиндров вычитанием адреса первого фрагмента в группе. Скажем, если фрагмент является 50-м в группе, его состояние выделения хранится в 50-м бите, то есть втором бите байта 6.
В рассмотренной ранее файловой системе UFS1 дескриптор группы располагался в блоке 24, а битовая карта фрагментов хранилась со смещением 504 байта. Чтобы просмотреть ее содержимое, следует запустить dcat с параметром 8 для просмотра всех 8 фрагментов блока: dcat -f openbsd openbsd.dd 24 | xxd [...]
0000496: 0000 0000 0000 0000 0000 0000 0000 0000
0000512: 0000 0000 0000 0000 0000 0000 0000 0000
0000528: 0000 0000 0000 0000 0000 fOfe 0000 0000
0000544: 0000 0000 ffff ffff OOff 0000 0000 0000
0000560: 0000 0000 0000 0000 0000 0000 0000 0000
0000576: 0000 0000 0000 0000 0000 0000 0000 0000
[...]
Байт 504 является первым байтом в битовой карте фрагментов. Он равен 0; это означает, что первые 8 фрагментов выделены. Свободные фрагменты отсутствуют вплоть до байта 538, который является байтом 34 битовой карты. Старшие бита этого байта равны 1, то есть фрагменты 276-279 свободны.
Данные относятся к первой группе, поэтому эти номера соответствуют их фактическим адресам; в противном случае к ним пришлось бы прибавить начальный адрес группы. Обратите внимание: эти четыре свободных фрагмента не представляют полный блок, поскольку каждый блок состоит из восьми фрагментов. В данном случае первые 4 фрагмента блока выделены, а последние 4 — нет.Байты 548-551 описывают серию из 32 смежных невыделенных фрагментов. Байт 548 соответствует байту 44 битовой карты, поэтому первый бит относится к фрагменту 352.
Битовая карта фрагментов малоэффективна при выделении отдельных блоков или больших групп смежных блоков, поэтому наряду с ней существует битовая карта блоков. Она дублирует информацию, находящуюся в битовой карте фрагментов, но каждый бит в ней обозначает целый блок, поэтому адресация блоков должна производиться иначе. Блоки нумеруются последовательными числами — например, если один блок состоит из 8 фрагментов, вместо блоков 0, 8, 16, 24 и т. д. будут использоваться номера 0,1, 2,3 и т. д. Чтобы вычислить адрес блока, достаточно разделить адрес фрагмента на количество фрагментов в блоке. Если соответствующий бит равен 1, блок свободен для выделения.
Как было показано ранее, в системе UFS1 битовая карта блоков хранится в дескрипторе группы со смещением 1540: dcat -f openbsd openbsd.dd 24 8 | xxd [...]
0001536: 0100 0000 0000 0000 OOfO 0200 0000 0000
0001552: 0000 0000 0000 0000 0000 0000 cOff ffff
0001568: ffff ffff ffff ffff ffff ffff ffff ffff
[...]
Мы видим, что байт 1540 равен 0, после чего установленные биты появляются только в байте 1545, в котором установлены 4 старших бита. Этот байт является 5-м байтом битовой карты; его биты соответствуют относительным блокам 40-47, а биты относительных блоков 44-47 установлены равными 1. Преобразовав эти адреса в адреса фрагментов, мы получим фрагменты 352-383, которые мы видели в битовой карте фрагментов как набор свободных смежных фрагментов.
Еще по теме Битовые карты блоков и фрагментов:
- Битовая карта блоков
- М.И. Дарвин ФРАГМЕНТ
- Под редакцией Г. АЛЕКСАНДРОВА. Античная философия (Фрагменты и свидетельства), 1940
- Применение нейропсихологического подхода в дефектологической практике*13* А.Л. Битова
- УСТАВ ОРГАНИЗАЦИИ АМЕРИКАНСКИХ ГОСУДАРСТВ, 1967 г. Фрагменты (на английском языке) CHARTER OF THE ORGANIZATION OF AMERICAN STATES
- Глава 25 ГЕОМОРФОЛОГИЧЕСКИЕ КАРТЫ
- 21.1. ПЛАСТИКОВЫЕ КАРТЫ
- Овердрафт счета банковской карты.
- Устав «Клубной карты»
- ГЕОГРАФИЧЕСКИЕ КАРТЫ
- Ревизия финансовых отчетов «Клубной карты»
- Встреча «Клубной карты» с Kroger
- Команда «Клубной карты»: снова вместе
- Пластиковые карты, телефоны и бланки
- Эффект «Клубной карты»
- Значение «Клубной карты» для нового предприятия
- Оценка преимуществ «Клубной карты»
- Карты истории