Такая файловая система называется ориентированный ациклический граф (DAG, Directed Acyclic Graph).

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

Есть два решения этой проблемы:

1. Использование i-узлов, в каталогах хранится только указатель на i-узел. Такие ссылки называются жесткими ссылками.

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

10.6.1 Жесткие ссылки

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

Поэтому в этом случае при удалении файла i-узел лучше не удалять.

Файл будет удален только после того, как счетчик будет равен 0.

Иллюстрация проблемы, которая может возникнуть

10.6.2 Символьные ссылки

Удаление файла не влияет на ссылку, просто по ссылке будет не возможно найти файл (путь будет не верен).

Удаление ссылки тоже никак не скажется на файле.

Но возникают накладные расходы, чтобы получить доступ к i-узлу, должны быть проделаны следующие шаги:

• Прочитать файл-ссылку (содержащий путь)

• Пройти по всему этому путь, открывая каталог за каталогом

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

10.7.1 Размер блока

Если принято решение хранить файл в блоках, то возникает вопрос о размере этих блоков.

Есть две крайности:

• Большие блоки - например, 1Мбайт, то файл даже 1 байт займет целый блок в 1Мбайт.

• Маленькие блоки - чтение файла состоящего из большого числа блоков будет медленным.

Скорости чтения/записи и эффективность использования диска,
в системе с файла одинакового размера 2 Кбайта.

В UNIX системах размер блока фиксирован, и, как правило, равен от 1Кбайта до 4Кбайт.

В MS-DOS размер блока может быть от 512 до 32 Кбайт в зависимости от размера диска, поэтому FAT16 использовать на дисках больше 500 Мбайт не эффективно.

В NTFS размер блока фиксирован (от 512байт до 64 Кбайт), как правило, равен примерно 2Кбайтам (от 512байт до 64 Кбайт).

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

Основные два способа учета свободных блоков :

• Связной список блоков диска, в каждом блоке содержится номеров свободных блоков столько, сколько вмешается в блок. Часто для списка резервируется нужное число блоков в начале диска.
  Недостатки:
  - Требует больше места на диске, если номер блока 32-разрядный, требуется 32бита для номера
  - Излишние операции ввода/вывода, т.к. в памяти не хранятся все блоки, а, например, только один блок

• Битовый массив (бит-карта) - для каждого блока требуется один бит.

---

Основные два способа учета свободных блоков

10.7.3 Дисковые квоты

Чтобы ограничить пользователя, существует механизм квот.

Два вида лимитов:

• Жесткие - превышены быть не могут

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

Наиболее распространенные квоты:

• Объем использования диска

• Количество файлов

• Количество открытых файлов

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

10.8.1 Резервное копирование

Случаи, для которых необходимо резервное копирование:

• Аварийные ситуации, приводящие к потере данных на диске

• Случайное удаление или программная порча файлов

Основные принципы создания резервных копий:

• Создавать несколько копий - ежедневные, еженедельные, ежемесячные, ежеквартальные.

• Как правило, необходимо сохранять не весь диск, а толь выборочные каталоги.

• Применять инкрементные резервные копии - сохраняются только измененные файлы

• Сжимать резервные копии для экономии места

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

• Хранить резервные копии в защищенном месте, не доступном для посторонних.

Существует две стратегии:

• Физическая архивация - поблочное копирование диска (копируются блоки, а не файлы)

Недостатки:

- копирование пустых блоков

- проблемы с дефектными блоками

- не возможно применять инкрементное копирование

- не возможно копировать отдельные каталоги и файлы

Преимущества:

- высокая скорость копирования

- простота реализации

• Логическая архивация - работает с файлами и каталогами. Применяется чаще физической.

10.8.2 Непротиворечивость файловой системы

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

В большинстве файловых систем есть специальная программа, проверяющая непротиворечивость системы.В UNIX - fsck.В Windows - scandisk.

Если произошел сбой, то во время загрузки они проверяют файловую систему (если файловая система журналируемая, такая проверка не требуется).

Журналируемая файловая система - операции выполняются в виде транзакций, если транзакция не завершена, то во время загрузки происходит откат в системе назад.

Два типа проверки на непротиворечивость системы:

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

2. проверка файлов - в первую очередь проверяется каталоговая структура. Файл может оказаться; либо в нескольких каталогах, либо не в одном каталоге (уменьшается место на диске).

---

10.11 Производительность файловой системы

Так как дисковая память достаточно медленная. Приходится использовать методы повышающие производительность.

10.11.1 Кэширование

Блочный кэш (буферный кэш) - набор блоков хранящиеся в памяти, но логически принадлежащие диску.

Перехватываются все запросы чтения к диску, и проверяется наличие требуемых блоков в кэше.

Ситуация схожа со страничной организацией памяти, можно применять те же алгоритмы.

Нужно чтобы измененные блоки периодически записывались на диск. В UNIX это выполняет демон update (вызывая системный вызов sync). В MS-DOS модифицированные блоки сразу записываются на диск (сквозное кэширование).

10.11.2 Опережающее чтение блока

Если файлы считываются последовательно, и когда получен к-блок, можно считать блок к+1 (если его нет в памяти). Что увеличивает быстродействие.

10.11.3 Снижение времени перемещения блока головок

Если записывать, наиболее часто запрашиваемые файлы, рядом (соседние сектора или дорожки), то перемещение головок будет меньше

В случае использования i-узлов если они расположены в начале диска, то быстродействие будет уменьшено, т.к. сначала головка считает i-узел (в начале диска), а потом будет считывать данные (где-то на диске). Если располагать i-узлы поближе к данным, то можно увеличить скорость доступа.

Лекция 11. Примеры файловых систем

11.1 Файловой системы CD-дисков

11.1.1 Файловая система ISO 9660

Более подробная информация - http://ru.wikipedia.org/wiki/ISO_9660 Стандарт принят в 1988 г.

По стандарту диски могут быть разбиты на логические разделы, но мы будем рассматривать диски с одним разделом.

Как вы знаете блоки записываются последовательно; по спирали; сектора по 2352 байта.

Порядок записи информации:

1. Каждый CD-ROM начинается с 16 блоков (неопределенных ISO 9660), эта область может быть использована для размещения загрузчика ОС или для других целей.

2. Дальше один блок основного описателя тома - хранит общую информацию о CD-ROM, в нее входит:

• идентификатор системы (32байта)

• идентификатор тома (32байта)

• идентификатор издателя (128байт)

• идентификатор лица, подготовившего данные (128байт)

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

• ключевые слова: размер логического блока (как правило, 2048, но могут быть 4096, 8192 и т.д.); количество блоков; дата создания; дата окончания срока службы диска.

• описатель корневого каталога (номер блока содержащего каталог).

3. Могут быть дополнительные описатели тома, подобные основному.

Каталоговая запись стандарта ISO 9660.

Каталоговая запись стандарта ISO 9660.

Расположение файла - номер начального блока, т.к. блоки располагаются последовательно.

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

Имя файла - 8 символов, 3 символа расширения (из-за совместимости с MS-DOS). Имя файла может встречаться несколько раз, но с разными номерами версий.

---

Sys - поле System use (используется различными ОС для своих расширений )

Порядок каталоговых записей:

1. Описатель самого каталога (аналог ".")

2. Ссылка на родительский каталог (аналог "..")

3. Остальные записи (записи файлов) в алфавитном порядке

Количество каталоговых записей не ограничено, но ограничено количество вложенности каталогов - 8.

В стандарте ISO 9660 определены три уровня ограничений:

1. - имена файлов = 8-3

- имена каталогов 8 символов, каталоги без расширений

- глубина вложенности каталогов ограничена восемью

- файлы должны быть непрерывными

2. имена файлов и каталогов до 31 символа

3. - имена файлов и каталогов до 31 символа

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

11.1.2 Рок-ридж расширения для UNIX

Это расширение было создано, чтобы файловая система UNIX была представлена на CD-ROM.

Для этого используется поле System use.

Расширения содержат следующие поля:

1. PX - атрибуты POSIX (стандартные биты rwxrwxrwx, (чтение, запись, запуск) (владелец, группа, все) )

2. PN - старший и младший номер устройств (чтобы можно было записать каталог /dev, который содержит устройства)

3. SL - символьная связь

4. NM - альтернативное имя, позволяет использовать произвольные имена, без ограничений

5. CL - расположение дочернего узла (чтобы обойти ограничение на вложенность каталогов)

6. PL - расположение дочернего узла (чтобы обойти ограничение на вложенность каталогов)

7. RE - перераспределение (чтобы обойти ограничение на вложенность каталогов)

8. TF - временные штампы (время создания, последнее изменение , последний доступ)

11.1.3 Joliet расширения для Windows

Это расширение было создано, чтобы файловая система ОС Windows 95 была представлена на CD-ROM.

Для этого используется поле System use.

Расширения содержат следующие поля:

1. Длинные имена файлов (до 64 символов)

2. Набор символов Unicode (поддержка различных языков)

3. Преодоление ограничений на вложенность каталогов

4. Имена каталогов с расширениями

11.1.4 Romeo расширения для Windows

Стандарт Romeo предоставляет другую возможность записи файлов с длинными именами на компакт-диск. Длина имени может составлять 128 символов, однако использование кодировки Unicode не предусмотрено. Альтернативные имена в этом стандарте не создаются, поэтому программы MS-DOS не смогут прочитать файлы с такого диска.

Вы можете выбрать стандарт Romeo только в том случае, если диск предназначен для чтения приложениями Windows 95 и Windows NT.

11.1.5 HFS расширения для Macintosh

Иерархическая файловая система компьютеров Macintosh, не совместима ни с какими другими файловыми системами и называется Hierarchical File System (HFS).

11.1.6 Файловая система UDF (Universal Disk Format)

Более подробная информация - http://ru.wikipedia.org/wiki/Universal_Disk_Format

Изначально созданная для DVD, с версии 1.50 добавили поддержку CD-RW и CD-R.

Сейчас последняя версия 2.60. Официальную информацию (и спецификацию) можно получить на сервере www.osta.org - сервер Optical Storage Technology Association.

---

Эта файловая система позволяет дописывать диски, а также поддерживает большие размеры файлов и длинные имена файлов.

11.2 Файловая система CP/M

CP/M (Control Program for Microcomputers) - операционная система, предшественник MS-DOS.

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

Имена файлов - 8+3 символов верхнего регистра.

После каждой перезагрузки рассчитывается битовый массив занятых и свободных блоков. Массив находится постоянно в памяти (для 180Кбайтного диска 23 байта массива). После завершения работы, он не записывается на диск.

Каталоговая запись CP/M

Видно, что максимальный размер файла 16Кбайт (16*1Кбайт).

Для файлов размером от 16 до 32 Кбайт можно использовать две записи. Для до 48 Кбайт три записи и т.д.

Порядковый номер записи хранится в поле экстент.

Код пользователя - каждый пользователь мог работать только со своими файлами.

Порядок чтения файлов:

1. Файл открывается системным вызовом open

2. Читается каталоговая запись, из которой получает информацию о всех блоках.

3. Вызывается системный вызов read

11.2 Файловая система MS-DOS (FAT-12,16,32)

В первых версиях был только один каталог (MS-DOS 1.0).

С версии MS-DOS 2.0 применили иерархическую структуру.

Каталоговые записи, фиксированны по 32 байта.

Имена файлов - 8+3 символов верхнего регистра.

Порядок чтения файлов:

1. Файл открывается системным вызовом open, которому указывается путь к файлу (может быть абсолютным и относительным).

2. Файловая система открывает каталоги (согласно пути), считывает последний каталог в память.

3. Ищет описатель файла.

4. Читается дескриптор файла, из которого получает информацию о всех блоках.

5. Вызывается системный вызов read

Каталоговая запись MS-DOS, обратите внимание на пустые 10 байт,

они будут задействованы в Windows 98

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

Поле время (16 разрядов) разбивается на три подполя:

1. секунды - 5бит (2^5=32 поэтому хранятся с точностью до 2-х секунд)

2. минуты - 6бит

3. часы - 5бит

Поле даты (16 разрядов) разбивается на три подполя:

1. день - 5бит

2. месяц - 4бита

3. год - 7бит (начинается с 1980г, т.е. максимальный 2107г.)

Теоретически размер файлов может быть до 4Гбайт (32 разряда).

Все блоки файла в записи не хранятся, а только первый блок. Этот номер используется в качестве индекса для 64К (для FAT-16) элементов FAT-таблицы, хранящейся в оперативной памяти.

В зависимости от количества блоков на диске в системе MS-DOS применяется три версии файловой системы FAT:

1. FAT-12

2. FAT-16

3. FAT-32 - для адреса используются только 28 бит, поэтому правильнее назвать FAT-28

Размер блока (кластера) должен быть кратным 512 байт.

11.2.1 FAT-12

В первой версии MS-DOS использовалась FAT-12 с 512 байтовыми блоками, поэтому максимальный размер раздела мог достигать 2Мбайта (2^12*512байта).

---

Смотрите также файлы

• Лекция 5. Процессы и потоки (нити). Взаимодействие процессов.doc

• Лекция 4. ОСНОВНЫЕ КОНЦЕПЦИИ ТЕОРИИ ОС.doc

• Лекция 1.doc

• Лекция 3. АРХИТЕКТУРА ОПЕРАЦИОННОЙ СИСТЕМЫ.doc

• Лекция 6. Планирование процессов.doc