В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 2
Текст из файла (страница 2)
Тогда найдём g(Q) из уравнения g(P ) + g(Q) = i. Поскольку C связна, мы сможем найтизначения g на всех вершинах C.Теперь становятся очевидными две вещи. Во-первых, ясно, зачем в графе не должно быть циклов. Действительно, если C — цикл, то в общем случае возникающая цепочка уравнений не будет совместна. Во-вторых, изпостроения функции g понятно, почему функция h не даст коллизий на словах из нашего множества и будетсовершенной.Пример 4.1. Построим h на множестве слов A, B, C, D. Опишем процедуру построения g, всё остальноеясно без всяких примеров.
Допустим, f1 и f2 сгенерированы так:f1f2A54B71C38D13В этом примере константа c выбрана, судя по числу 8 в таблице, не меньше 3, хотя сейчас нам это и не важно. В нашем графе будет 2 компонентысвязности.Теперь приступим к вычислению g. Рассмотрим первую компонентусвязности и положим g(5) = 0. Тогда g(5) + g(4) = 0, откуда g(4) = 0.
Далее, рассмотрим вторую компоненту связности и положим g(7) = 0. Тогда g(7) + g(1) = 1, следовательно, g(1) = 1. Далее, g(1) + g(3) = 2,следовательно, g(3) = 1. Наконец, g(3) + g(8) = 3, откуда g(8) = 2. Заметим, что значения h — это в точностиномера рёбер графа.Отметим плюсы и минусы. Алгоритм построения достаточно быстрый, причём самое медленное в нём —проверка графа на цикличность.
Из недостатков PHF важно отметить, что нам необходимо хранить весь списокслов, для которого мы строилиPHF. Всамом деле, если h есть PHF для множества M, где |M| = m, и длянекоторого x имеем h(x) ∈ 0, . . . , m − 1 , то это ещё не означает, что x ∈ M.A540BDC71381232. Файловые системыПри организации файловых систем всегда надо помнить, что диск по природе своей является блочнымустройством, а потому поиск кластера, чтение и запись — операции довольно долгие, и потому необходимо свестиих количество к минимуму.
При этом, естественно, приходится задействовать оперативную память, которойу нас всегда не так уж много. Следовательно, приходится выбирать между эффективностью и количествомиспользуемых ресурсов.Диск всегда содержит MBR (Master Boot Record), в которой собрана информация о всех разделах (Partitions)диска. MBR всегда занимает фиксированную на диске позицию, чтобы его не надо было искать. В каждомразделе диска может использоваться свой тип файловой системы. Например, один физический диск можетсодержать разделы FAT, NTFS, EXT, HPFS и т. д. Рассмотрим ФС FAT.2.1. Файловая система FATFAT (File Allocation Table) — таблица размещения файлов.
В этой файловой системе раздел делится на 4куска:••••Boot Record — загрузочная записьFAT — собственно таблица размещения файловDIR — корневой каталогDATA — область данных, хранящая файлыВ FAT файл фактически представляет собой однонаправленный список кластеров, разбитых на блоки (сектора). Пронумеруем все кластеры диска. Пусть их N штук. Тогда FAT будет содержать N ячеек.
Пусть кластеры сномерами k и m хранят два последовательных фрагмента файла. Тогда ячейка FAT с номером k будет содержатьчисло m. Таким образом, чтобы считать весь файл, нам надо узнать только номер первого кластера, занятогофайлом. Этот номер извлекается из записи в каталоге, о которой речь пойдёт ниже. Чтобы сигнализироватьо том, что кластер является последним в цепочке, в ячейку FAT с номером этого кластера записывается специальное зарезервированное значение.
Существует несколько типов зарезервированных значений. Перечислимих:5••••00..00FF..F7FF..F0FF..F8——-свободныедефектные кластерыFF..F6 — системныеFF..FF — последние в цепочкеРазрядность FAT — это количество бит, которое отводится под размер ячеек таблицы FAT. Здесь вездерасставлены многоточия, поскольку количество букв F зависит от разрядности ФС.
Существует 3 вида FAT,если классифицировать их по разрядности: FAT12 (используется на дискетах), FAT16 (DOS 6.22 и ниже) иFAT32 (DOS 7.0 и Windows 9x).Скажем пару слов о том, сколько примерно дискового пространства можно адресовать. Из принципов организации диска стало ясно, что файл всегда должен по факту занимать целое число кластеров. Это означает, чтодаже если кластер огромный (32 Кбайт), а файл маленький (1 байт), всё равно на него будет отведён целый кластер.
Оно и понятно, поскольку в противном случае нескольким файлам мог бы соответствовать один кластер,а это очень замедляло бы доступ и усложняло организацию. Следовательно, непомерно большие кластеры —это плохо. Кроме того, размер кластера должен делиться на размер дискового блока (сектора), который всегдасоставляет 512 байт. Опытным путём было установлено, что оптимальный размер кластера составляет от 2 до 8блоков: с одной стороны, это достаточно экономно, а с другой стороны, размер самой таблицы FAT при этом ещёне так велик. Подытожим сказанное.
Максимальный размер раздела равен 2D ∗ 29 ∗ BP C, где D — разрядностьФС, а BP C — количество блоков на кластер. Отсюда следует, что загрузить всю таблицу FAT в оперативнуюпамять нереально.Перейдём к правилам организации каталогов. Вся файловая структура в FAT является деревом с файламилистьями. Каталоги — это тоже файлы, у которых установлен специальный атрибут Directory (об атрибутахречь пойдёт ниже). Корень дерева называется корневым каталогом и располагается в фиксированной областидиска DIR. Содержимое файла-каталога несёт в себе информацию о всех файлах, расположенных в нём, ипредставляет собой несколько записей фиксированного размера, называемых элементами каталога (DirectoryEntry).
Для удобства организации, помимо обычных DirEntry, каждый каталог имеет ссылку на самого себя и народительский каталог. Такие ссылки обозначаются точкой и двумя точками соответственно. Опишем структуруполей DirEntry в FAT16.Количество байт8+3110222432НазначениеИмя + расширениеАтрибутыРезервВремяДатаНомер первого кластераРазмер в байтахИтогоАтрибуты файла — битовая маска, в которой из 8 бит используются только биты с 0-го по 5-й. Это, соответственно, флаги R (ReadOnly — только для чтения), H (Hidden — скрытый), S (System — системный), V (VolumeLabel — метка тома), D (Directory — каталог), A (Archive — архивный).
Назначение флага A в настоящее времяутратило смысл.С появлением Windows 95 возникла необходимость создавать файлы с длинными именами. Для этого былосоздано расширение FAT, называемое VFAT, в котором под файл с длинным именем отводится несколько последовательных DirEntry. При этом у них устанавливаются нереальные c точки зрения FAT атрибуты — число0xF.
В самом деле, файл не может быть одновременно меткой тома, скрытым, системным и только для чтения.Имя файла в этом случае хранится в кодировке, напоминающей UNICODE, т. е. на каждый символ отводится по2 байта. Оно хранится в неиспользуемых полях DirEntry. Элементы каталога, хранящие один файл с длиннымименем, расположены задом наперёд, и самый последний из них является «нормальным» с точки зрения FAT.При последовательном считывании элементов каталога проверяются их атрибуты, и, если замечен атрибут 0xF,то производится чтение DirEntry до тех пор, пока не попадётся DirEntry с нормальными атрибутами.
Далеепроизводится извлечение имени из элементов каталога.Поговорим о надёжности FAT и возможности восстановления файлов. Из соображений безопасности надиске хранится 2 идентичные копии FAT. При удалении файла почти никакой физической записи на дискне производится. Вместо этого в имени файла в его DirEntry прописывается число 0xE5 в первый символ. Этопризнак того, что файл удалён.
При этом FAT не претерпевает никаких изменений. Реальное освобождение ячеекFAT, занимаемых файлом, производится по мере надобности: при создании файла DOS просматривает текущийкаталог, находит в нём удалённые файлы и отводит их кластеры под новый файл, возвращая таким образом6«потерянное» дисковое пространство. Если FAT не разрушена, то файл ещё можно восстановить, если кластеры,им занимаемые, не были отведены под другой файл.
Действительно, если запись каталога не испорчена, мысможем извлечь номер первого кластера и восстановить файл, пробежавшись по FAT. Даже если DirEntryиспорчен, мы можем, просмотрев все каталоги, найти в FAT все цепочки кластеров, не принадлежащие никакимфайлам, и восстановить файл хотя бы фрагментарно.Из за невозможности загрузить в оперативную память всю таблицу FAT, эта ФС работает достаточно медленно. Что касается надёжности и возможности восстановления, то с этих точек зрения она достаточно хороша.Среди файловых систем, ещё более приспособленных к восстановлению удалённых файлов, известна только ФС,используемая в томах Novell NetWare. Она характерна тем, что там при удалении файла ему присваивается специальный атрибут Deleted, и файл с таким атрибутом исчезает с глаз пользователя. Физическое удаление такихфайлов производится системным администратором с помощью специальной команды PURGE.
До выполненияэтой операции восстановление файла возможно с гарантией 100%.2.2. Файловая система EXTВ UNIX понятие кластера фактически отсутствует, т. е. за единицу дискового пространства выбирается блок(сектор). Как и в FAT, раздел EXT делится на 4 куска: BOOT Record, SuperBlock, INodeArray, Data. Сразу скажем, что в UNIX под файлом понимается фактически любая сущность, с которой можно производить операцииввода-вывода. Например, мышь — символьное устройство, рассматриваемое как файл, доступный только длячтения в особом режиме.
Зачем так было сделано — вопрос философский, и его мы рассматривать не будем.Вторая особенность этой ФС заключается в том, что она изначально при разметке раздела подготавливаетсяна фиксированное число файлов. Считается, что из многолетнего опыта примерно понятно, сколько файловможет потребоваться для работы.Опишем куски, из которых состоит раздел. BOOT Record — загрузочная запись, SuperBlock — дескрипторраздела, содержащий всю информацию о структуре его ФС. Data — область данных, а INodeArray — массивэлементов типа INode, количество которых и есть то количество файлов, на которое размечена ФС.В UNIX файл может быть многоликим: на него может существовать несколько ссылок с различными именами.
Количество ссылок решает проблему разделения доступа: если кто-то удалил файл, количество ссылокна него уменьшается на 1. Когда оно становится равным 0, файл физически удаляется.Существует два типа EXT: EXT2 и EXT3. Мы будем описывать только EXT2. В ней INode — структураразмером 64 байта, содержащая поля:НазваниеFileTypeOwnerIDGroupIDRightsDateTimeLengthNumRefsBlockTableНазначениеТип файлаИдентификатор владельца файлаИдентификатор группы владельцевПрава доступа для пользователя, группы, и всех остальныхДата и времяДлина в байтахКоличество ссылок на файлТаблица блоковТип файла описывает его происхождение: это может быть символьное устройство, блочное устройство, обычный файл, или канал (Pipe).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
