Надежность файловой системы.

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

1) Создание резервных копий. Может осуществляться на внешнем носителе (магнитный диск, магнитная лента), либо внутри файловой системы (FAT1, FAT2). Во втором случае используется дублирование и поддержание в актуальном состоянии данных и управляющих таблиц в режиме времени, близком к реальному. Пример: корзина для удаленных файлов. В этом случае необходимо определить, какие элементы файловой системы являются критическими в случае нештатной ситуации и с какой частотой осуществлять их актуализацию (обновление). Копии, как правило, создаются при завершении всех прикладных процессов (задач), поэтому частота снятия копий может определяться графиком их решения. В некоторых ОС возможно получать "образы" (слепок), как состояний файловой системы в определенный момент времени, так и содержимого реальной и виртуальной ОП. При возникновении нештатной ситуации возможна загрузка образа в ОП (текущее состояние вычислительного процесса) и на диск, соответствующий ему состояния файловой системы. В общем случае существует две основных стратегии создания резервных копий: физическая архивация и логическая архивация.

- Физическая архивация включает поблочное копирование на внешний носитель. Недостатки:

1. Хранение неиспользуемых блоков.

2. При восстановлении необходимо восстанавливать весь диск.

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

В общем случае можно выделить 3 состояния копий:

1. Дистрибутив. (Создан и передан для эксплуатации разработчикам. Как правило, находится на ленте или диске, защищенном от записи.)

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

3. Дубль. (Копия или архив текущего состояния файловой системы, подлежащая обновлению.)

2) Обеспечение непротиворечивости файловой системы.

Проблема возникает при сбое, при записи последних блоков в файловую систему (потеря кластеров, ссылок на кластеры). Как правило, в ОС существует инструментарий проверки непротиворечивости.

Существуют два основных метода проверки непротиворечивости:

- блоков (кластеров)

- каталогов.

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

Пример:

а) в случае непротиворечивости

б) пропавший блок

Блок 2 (кластер) не занят и не свободен - потерян.

в) один и тот же блок (кластер) находится в двух файлах

Блок 4 дважды появляется в разных файлах. При удалении будет и свободным, и занятым.

Инструментарий проверки должен скопировать содержимое блока 4 в свободный блок и выделить его файлу. Непротиворечивость каталогов проверяется путем сравнения счетчиков нахождения файлов в разных каталогах.

Пример: для файловой системы, построенной на i-nodes, для каждого файла в каждом каталоге инструментарий увеличивает на единицу счётчик использования файла. На выходе появляется список, индексированный по i-nodes, который сообщает, в скольких каталогах присутствует каждый файл. Далее сравнивается полученное значение со счётчиками связи, хранящимися в самих i-nodes. Указанные счётчики при создании файла имеют значение 1 и увеличиваются на 1 каждый раз, когда создается новая связь с данным файлом. В непротиворечивой файловой системе оба счётчика должны совпадать.

А - счетчик кол-ва каталогов, в котором присутствует файла.

В - счетчик связей i-nodes файла.

1. В>А.

При удалении файла из всех каталогов i-node не будет удален. Устранение: установить значение счётчика связей, равным числу каталогов.

2. А>В.

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

Производительность ФС.

Для уменьшения системных затрат применяются различные способы оптимизации файловой системы:

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

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

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

Файловая система CDR.

Описывается стандартом ISO-9660. Цель стандарта - создание файловой системы, которая могла бы прочитать в любой ОС.

Файловая система расположена на непрерывной спирали, начинающейся от середины диска. Биты вдоль спирали разделены на логические блоки по 2352 байта. Логический блок содержит управляющую информацию и непосредственно данные - 2048 байт. Каждый CD-ROM начинается с 16 блоков, не определяемых стандартом. 17ый блок - основной описатель тома: идентификатор системы (32 байта), идентификатор тома (32 байта), идентификатор издателя (128 байт), идентификатор лица, подготовившего данные (128 байт), место под имена трех файлов, в которых может хранится пользовательская информация. Управляющая информация: размер логического блока, количество блоков, дата окончания службы диска, номер блока-описателя корневого каталога. Каталоговые записи имеют переменную длину. Каждая запись каталога содержит 10-12 полей. Поля кодируются дважды: в формате Pentium (младшие биты, старшие биты) и в формате SPARC (старшие биты, младшие биты).

Формат записи каталога.

формат записи каталога
									7-15
							CD	L

1 – длина каталоговой записи (байт)

2 – длина записи настраиваемых атрибутов

3 – место расположения файла

4 – номер файла

5 - дата и время создания

6, 7 - см. стандарт

8 (CD) - чередование

9 (L) - длина имени файла в байтах

10 - имя файла

Файлы хранятся в виде непрерывной последовательности блоков, таким образом размещение файла на диске однозначно определяется начальным блоком и размером.

CD чередование. Определяет возможность расположения файла (продолжения) на другом CDR.

Сжатие видеоинформации.

Для всех систем сжатия требуется 2 алгоритма: для сжатия данных источника (компрессия) и декомпрессии данных у получателя. Алгоритмы имеют некоторую асимметрию, т.е. они не одинаковы:

1. Алгоритм сжатия (кодирования) может быть медленным, алгоритм декодирования должен быть быстрым.

2. Для видеоконференций кодирование должно происходить в режиме времени, близком к реальному.

3. При сжатии видеоинформации и её декодировании изображение может изменяться, т.е. иногда говорят, что декодирование происходит с потерями.

Одним из первых стандартов является jpeg (Joint Photographic Expert Group) - алгоритм сжатия неподвижных изображений. Каждая точка на экране (пиксел) представляется разложением на три цвета: Red, Green, Blue. При этом на Red отводится 8 бит, Green 8 бит и Blue 8 бит, т.е. 24х битовое RGB видеоизображение. Кодирование осуществляется по следующим этапам:

1. Подготовка блока.

Рассмотрим на основе изображения 640*480. Из значения RGB каждого пиксела выделяют: яркость и два значения цветности. Из них строятся матрицы (Y- яркость, I, Q - цветность). Значения I и Q усредняются по четырем пикселям, т.е. растр преобразуется в размер 240*320. 4 пикселя заменяются на 1. Сжатие является преобразованием с потерями, но человеческому глазу это не видно, т.к. ощущение цветности у человека меньше.

2. Матрица 320*240 преобразуется в матрицу 8*8 точек методом усреднения.

320/8*240/8=1200

Y 640/8*480/8

Общее количество блоков 4800+1200+1200=7200.

3. К каждому блоку применяется так называемое дискретное косинусное преобразование (ДКП). Получается 7200 коэффициентов ДКП.

4. Этап квантования. Коэффициенты ДКП подвергаются квантованию в соответствие с таблицей квантования. Если коэффициенты ДКП 7200, то на выходе квантованное ДКП. Квантование происходит делением коэффициентов ДКП на коэффициенты квантования. Получаем квантованные коэффициенты ДКП.

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

6. Элементы матрицы выстраиваются по следующей схеме: в случае повторения значения в ряд выстраивается их число и значения повторений.

7. Полученные значения чисел кодируется кодом Хаффмана. По следующей схеме: