Всё для Учёбы — студенческий файлообменник
1 монета
doc

Лекция «Файловая подсистема» по Операционным системам (Иванько А. Ф.)

Файловая подсистема служит для того, чтобы предоставлять пользовательским и системным процессам удобный доступ к внешним запоминающим устройствам. Задачами файловой подсистемы является долговременное и надежное хранение информации на внешних носителях и организация совместного использования информации различными программами. Файловая подсистема – это совокупность всех файлов на диске; наборы структур данных, используемых для управления файлами; совокупность программных средств, предоставляющих операции над файлами.

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

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

Файловая система позволяет одинаковым образом обращаться к различным устройствам, работающим по различным принципам. Так, если у винчестера, компакт-диска и дискеты имеются секторы и дорожки, то виртуальный диск или диск на основе флэш-памяти физически устроены совершенно по-другому.

Выделяют несколько видов файлов.

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

2. Каталоги – специально оформленные файл, содержащие в себе информацию о других файлах. Различные ОС группируют файлы по различным признакам. Большинство ОС группируют файлы так, как этого требуют пользователь или программы. В один каталог складываются файлы, логически связанные между собой, например, относящиеся к одной программе или связанные с одним проектом. Если все файлы складывать в одном месте, то в них сложно будет разобраться, тогда как создав некоторую логическую структуру из каталогов мы тем самым создаем индекс файлов, позволяющий нам лучше в них ориентироваться. Однако ОС, ориентированные на работу с карманными компьютерами чаще группирую файлы по предназначению. То есть по запросам пользователя выдаются, например, все текстовые документы или изображения определенного формата, все исполняемые модули и так далее. Реально эти файлы могут храниться точно так же, как они хранятся в обычных ОС, и группируются только при отображении. При этом пользователь получает возможность группировать файлы различных форматов по логическим признакам. Так, например, можно собрать воедино файлы электронных таблиц, презентацию и текстовый документ, имеющие отношение к одному выступлению. Подобный подход удобен при работе с небольшим количеством текущих файлов, однако при создании файлового архива не может быть использован.

3. Специальные файлы – используются для доступа к устройствам. Так, например, под операционной системой Unix всем последовательным устройствам сопоставлен файл с определенным именем. При этом информация, поступающая в файл, не записывается на дисковый носитель, а подается драйверу устройства. И наоборот, при чтении из файла берется информация, отдаваемая драйвером устройства. Под MS-DOS тоже существовали (и продолжают существовать под ОС Windows) специальные файлы, например, устройство nul. Вся информация, поступающая на данное устройство, не подается дальше никуда и само устройство может использоваться, например, для проверки качества записи информации на носитель путем копирования файлов в устройство nul. Наиболее распространенным файлом является консоль. Чтение из файла консоли эмулирует ввод с клавиатуры, а запись в консоль – вывод на экран.

Каждый файл характеризуется своим именем и набором атрибутов. Имя – это символьная строка, которая позволяет идентифицировать данный файл. При этом разделяют короткое и полное имя файла. Короткое имя идентифицирует файл в каталоге. В файловой системе FAT16, разработанной для ОС MS-DOS имя файла состояло из двух частей: собственно имени файла (8 символов) и расширения (3 символа). В более современных версиях файловых систем это ограничение снято, однако, на размер имени файла все равно накладываются определенные ограничения (сейчас общая длина имени файла может достигать 255 символов). В одном каталоге может быть только один файл с данным именем. При этом файловая система может хранить как регистрозависимые, так и регистронезависимые имена, то есть будет или не будет различать написание имени файла большими и маленькими буквами. Так под ОС Windows невозможно создать файлы с именами TheFile.txt и thefile.txt в одном каталоге, тогда как в Unix это возможно. Полное имя – это короткое имя, к которому приписан полный путь к данному файлу. Полный путь включает в себя имена всех директорий, которые необходимо пройти для того, чтобы дойти до этого файла. Кроме того, полное имя может содержать имя носителя или имя компьютера, на котором он содержится. Так, например, в операционной системе Windows возможным является следующее полное имя: \\server1\c:\dir1\dir11\file.doc, которое говорит, что файл хранится на компьютере с именем server1 на логическом диске C: в каталоге dir1, который содержит в себе каталог dir11, короткое имя файла – file.doc.

Иерархическая организация, положенная в основу древовидной структуры файловой системы современных ОС, не предусматривает выражения отношений, в которых потомки связываются более чем с одним предком. Такая негибкость частично устраняется возможностью реализации связывания файлов или организации линков (link).

Ядро позволяет пользователю связывать каталоги, упрощая написание программ, требующих пересечения дерева файловой системы. Часто имеет смысл хранить под разными именами одну и ту же команду (выполняемый файл). Например, выполняемый файл традиционного текстового редактора ОС Unix vi обычно может вызываться под именами ex, edit, vi, view и vedit файловой системы. Соединение между директорией и разделяемым файлом называется "связью" или "ссылкой" (link). Дерево файловой системы превращается в циклический граф.

Это удобно, но создает ряд дополнительных проблем.

Простейший способ реализовать связывание файла - просто дублировать информацию о нем в обеих директориях. При этом, однако, может возникнуть проблема совместимости в случае, если владельцы этих директорий попытаются независимо друг от друга изменить содержимое файла. Например, в ОС CP/M запись в директории о файле непосредственно содержит адреса дисковых блоков. Поэтому копии тех же дисковых адресов должны быть сделаны и в другой директории, куда файл линкуется. Если один из пользователей что-то добавляет к файлу, новые блоки будут перечислены только у него в директории и не будут "видны" другому пользователю.

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

Альтернативное решение - создание нового файла, который содержит путь к связываемому файлу. Такой подход называется символической линковкой (soft или symbolic link). При этом в соответствующем каталоге создается элемент, в котором имени связи сопоставляется некоторое имя файла (этот файл даже не обязан существовать к моменту создания символической связи). Для символической связи может создаваться отдельный индексный узел и даже заводиться отдельный блок данных для хранения потенциально длинного имени файла.

Каждый из этих методов имеет свои минусы. В случае жесткой связи возникает необходимость поддержки счетчика ссылок на файл для корректной реализации операции удаления файла. Например, в Unix такой счетчик является одним из атрибутов, хранящихся в индексном узле. Удаление файла одним из пользователей уменьшает количество ссылок на файл на 1. Реальное удаление файла происходит, когда число ссылок на файл становится равным 0.

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

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

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

Еще одним достоинством абстрагирования от физических носителей при помощи файловой системы является то, что процесс может "не знать" на каком носителе находятся его данные. Так, например, в ОС Unix строится единая файловая система для всех устройств. И если часть устройств (такие как компакт-диски или дискеты) вписываются в нее в известные каталоги, то другие могут быть расположены в произвольных местах (вплоть до того, что один файл может начинаться на одном носителе, а заканчиваться на другом). В ОС Windows вводится понятие логического диска. Логический диск может быть присвоен как внешнему запоминающемуся устройству в целом (например, компакт-диску или дискете), либо его фрагменту. Последние версии Windows позволяют объединить в один логический диск фрагменты нескольких физических.

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

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

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

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

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

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

 Удаление файла и освобождение занимаемого им дискового пространства.

 Открытие файла. Перед использованием файла процесс должен его открыть. Цель данного системного вызова - разрешить системе проанализировать атрибуты файла и проверить права доступа к нему, а также считать в оперативную память список адресов блоков файла для быстрого доступа к его данным. Открытие файла является процедурой создания дескриптора или управляющего блока файла. Дескриптор (описатель) файла хранит всю информацию о нем. Иногда, в соответствии с парадигмой, принятой в языках программирования, под дескриптором понимается альтернативное имя файла или указатель на описание файла в таблице открытых файлов, используемый при последующей работе с файлом.

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

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

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

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

 Другие операции, например переименование файла, получение атрибутов файла и т. д.

Как и в случае с файлами, система обязана обеспечить пользователя набором операций, необходимых для работы с директориями, реализованных через системные вызовы. Несмотря на то что директории - это файлы, логика работы с ними отличается от логики работы с обычными файлами и определяется природой этих объектов, предназначенных для поддержки структуры файлового архива. Совокупность системных вызовов для управления директориями зависит от особенностей конкретной ОС. Напомним, что операции над каталогами являются прерогативой ОС, то есть пользователь не может, например, выполнить запись в каталог начиная с текущей позиции. Рассмотрим в качестве примера некоторые системные вызовы, необходимые для работы с каталогами.

 Создание директории. Вновь созданная директория включает записи с именами '.' и '..', однако считается пустой.

 Удаление директории. Удалена может быть только пустая директория.

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

 Закрытие директории после ее чтения для освобождения места во внутренних системных таблицах.

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

 Получение списка файлов в каталоге.

 Переименование. Имена директорий можно менять, как и имена файлов.

 Создание файла. При создании нового файла необходимо добавить в каталог соответствующий элемент.

 Удаление файла. Удаление из каталога соответствующего элемента. Если удаляемый файл присутствует только в одной директории, то он вообще удаляется из файловой системы, в противном случае система ограничивается только удалением специфицируемой записи.

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

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

Выделение непрерывной последовательностью блоков

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

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

Непрерывное выделение используется в ОС IBM/CMS, в ОС RSX-11 (для выполняемых файлов) и в ряде других.

Этот способ распространен мало, и вот почему. В процессе эксплуатации диск представляет собой некоторую совокупность свободных и занятых фрагментов. Не всегда имеется подходящий по размеру свободный фрагмент для нового файла. Проблема непрерывного расположения может рассматриваться как частный случай более общей проблемы выделения блока нужного размера из списка свободных блоков. Типовыми решениями этой задачи являются стратегии первого подходящего, наиболее подходящего и наименее подходящего (сравните с проблемой выделения памяти в методе с динамическим распределением). Как и в случае выделения нужного объема оперативной памяти в схеме с динамическими разделами, метод страдает от внешней фрагментации, в большей или меньшей степени, в зависимости от размера диска и среднего размера файла.

Кроме того, непрерывное распределение внешней памяти неприменимо до тех пор, пока неизвестен максимальный размер файла. Иногда размер выходного файла оценить легко (при копировании). Чаще, однако, это трудно сделать, особенно в тех случаях, когда размер файла меняется. Если места не хватило, то пользовательская программа может быть приостановлена с учетом выделения дополнительного места для файла при последующем рестарте. Некоторые ОС используют модифицированный вариант непрерывного выделения - основные блоки файла + резервные блоки. Однако с выделением блоков из резерва возникают те же проблемы, так как приходится решать задачу выделения непрерывной последовательности блоков диска теперь уже из совокупности резервных блоков.

Единственным приемлемым решением перечисленных проблем является периодическое уплотнение содержимого внешней памяти, или "сборка мусора", цель которой состоит в объединении свободных участков в один большой блок. Но это дорогостоящая операция, которую невозможно осуществлять слишком часто.

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

Связный список

Внешняя фрагментация - основная проблема рассмотренного выше метода - может быть устранена за счет представления файла в виде связного списка блоков диска. Запись в директории содержит указатель на первый и последний блоки файла (иногда в качестве варианта используется специальный знак конца файла - EOF). Каждый блок содержит указатель на следующий блок.

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

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

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

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

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

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

Таблица отображения файлов

Одним из вариантов предыдущего способа является хранение указателей не в дисковых блоках, а в индексной таблице в памяти, которая называется таблицей отображения файлов (FAT - file allocation table). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)

По-прежнему существенно, что запись в директории содержит только ссылку на первый блок. Далее при помощи таблицы FAT можно локализовать блоки файла независимо от его размера. В тех строках таблицы, которые соответствуют последним блокам файлов, обычно записывается некоторое граничное значение, например EOF.

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

Индексные узлы

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

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

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

Данную схему используют файловые системы Unix (а также файловые системы HPFS, NTFS и др.). Такой подход позволяет при фиксированном, относительно небольшом размере индексного узла поддерживать работу с файлами, размер которых может меняться от нескольких байтов до нескольких гигабайтов. Существенно, что для маленьких файлов используется только прямая адресация, обеспечивающая максимальную производительность.

Кэширование

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

Аккуратная реализация кэширования требует решения нескольких проблем.

Во-первых, емкость буфера кэша ограничена. Когда блок должен быть загружен в заполненный буфер кэша, возникает проблема замещения блоков, то есть отдельные блоки должны быть удалены из него. Здесь работают те же стратегии и те же FIFO, Second Chance и LRU-алгоритмы замещения, что и при выталкивании страниц памяти.

Структура блочного кэша

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

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

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

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

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

Оптимальное размещение информации на диске

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

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

Опережающее чтение

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

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

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

В 1988 году был принят Международный стандарт ISO 9660, описывающий файловые системы для CD-ROM. Одно из назначений этого стандарта заключалось в том, чтобы любой CD-ROM мог быть прочитан на любом компьютере, независимо от используемых байтового порядка и операционной системы. Как следствие, на файловую систему были наложены определенные ограничения, которые должны были позволить читать эти диски даже самым слабым из использовавшихся тогда операционных систем (таким как MS-DOS).

У CD-ROM нет концентрических цилиндров, как у магнитных дисков. Вместо этого они содержат непрерывную спираль, на которой последовательно размещены все биты (хотя поиск поперек спирали также возможен). Биты вдоль спирали разделены на логические блоки (также называемые логическими секторами) по 2352 байт. Некоторые из этих байтов используются для преамбул, коррекции ошибок и других накладных расходов. Полезная нагрузка в каждом блоке составляет 2048 байт. Аудиодиски содержат специальные разделительные участки между композициями, а также специальные заголовки и концевики для каждой фонограммы, не используемые в CD-ROM, содержащих другие данные. Часто позиция блока в спирали указывается в минутах и секундах. Она может быть преобразована в линейный номер блока, так как каждая секунда содержит 75 блоков.

Сами CD-ROM также могут быть разделены на отдельные логические тома (разделы). Однако ниже будет обсуждаться стандарт ISO 9660 для одного CD-ROM, не разделенного на тома.

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

Основной описатель тома также содержит имена трех файлов, в которых могут храниться краткий обзор, уведомление об авторских правах и библиографическая информация соответственно. Кроме того, в этом блоке также содержатся определенные ключевые числа, включающие размер логического блока (как правило, 2048, однако в определенных случаях могут использоваться блоки большего размера, например 4096, 8192 и других степеней двух), количество блоков на CD-ROM, а также дата создания и дата окончания срока службы диска. Наконец, основной описатель тома также содержит описатель корневого каталога, что позволяет найти этот каталог на CD-ROM (то есть определить номер блока, содержащего начало каталога). Начиная с этого каталога, можно определить местонахождение всей остальной файловой системы.

Корневой каталог и все остальные каталоги могут содержать переменное количество записей, в последней из которых установлен специальный бит, помечающий эту запись как последнюю. Сами каталоговые записи также могут иметь переменную длину. Каждая запись содержит от 10 до 12 полей, некоторые из них содержат текст формата ASCII, а другие являются числовыми двоичными полями. Двоичные поля кодируются дважды, один раз в формате, используемом в процессорах типа Pentium (сначала младшие байты, затем старшие), и один раз в формате, используемом в процессоре SPARC (сначала старшие байты, затем младшие).

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

Поле Flags (флаги) содержит несколько различных управляющих битов, один из которых позволяет скрывать запись при отображении каталога (свойство, взятое из MS-DOS), другой разрешает использование расширенных атрибутов, а третий помечает последнюю запись в каталоге. Следующее поле описывает особенности чередования частей файла на диске. Это свойство не используется в простейшей версии стандарта ISO 9660, поэтому оно не будет обсуждаться в данной книге.

Еще одно поле указывает местоположение файла на CD-ROM. Стандарт допускает возможность расположения файла на другом CD-ROM набора. Таким образом, можно создать на одном CD-ROM главный каталог, содержащий все файлы всех остальных CD-ROM набора.

Поле, отмеченное на рис. символом L, содержит длину имени файла в байтах. За ним следует само имя файла, состоящее из базового имени (base name на рисунке), точки, расширения, точки с запятой и версии файла в двоичном формате (один или два байта). В базовом имени и расширении могут использоваться прописные символы, цифры от 0 до 9 и символ подчеркивания. Все остальные символы запрещены, чтобы гарантировать, что каждый компьютер сможет работать со всеми файлами на диске. Базовое имя может быть длиной до восьми символов; расширение - до трех символов. Такой выбор был продиктован необходимостью совместимости с системой MS-DOS. Имя файла может встречаться несколько раз, но с различными номерами версий.

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

Стандартом ISO 9660 определены так называемые три уровня. На уровне 1 применяются самые жесткие ограничения. Имена файлов ограничиваются уже описанной выше схемой 8 + 3, а имена каталогов могут состоять из восьми символов и не могут иметь расширений. Кроме того, уровень 1 требует, чтобы все файлы были непрерывными. Использование этого уровня обеспечивает совместимость CD-ROM с самым широким спектром систем.

Уровень 2 ослабляет ограничение на длину имени. Он позволяет файлам и каталогам иметь имена до 31 символа, но из того же набора символов.

На уровне 3 используются те же ограничения имен, что и на уровне 2, но ослабляется жесткость требования непрерывности файлов. На этом уровне файл может состоять из нескольких разделов, каждый из которых представляет собой непрерывную последовательность блоков. Одна и та же последовательность блоков может несколько раз встречаться в одном файле и даже входить в несколько различных файлов. Такая организация файловой системы позволяет экономить место на диске.

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

Как было показано, стандарт ISO 9660 содержит много различных ограничений. Вскоре после выхода этого стандарта пользователи из UNIX-сообщества начали работу над его расширением, чтобы файловая система UNIX могла быть представлена на CD-ROM. Эти расширения получили название Рок-Ридж (Rock Ridge).

Расширение использует поле System use, чтобы CD-ROM формата Рок-Ридж мог читаться на любом компьютере. Все остальные поля соответствуют требованиям стандарта ISO 9660. Система, не знакомая с расширениями Рок-Ридж, просто игнорирует их и видит нормальный CD-ROM.

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

1. РХ - Атрибуты POSIX.

2. PN - Старший и младший номера устройств.

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

4. NM - Альтернативное имя.

5. CL - Расположение дочернего узла.

6. PL - Расположение дочернего узла.

7. RE - Перераспределение.

8. TF - Временные штампы.

Поле РХ содержит стандартные биты разрешений rwxrwxrwx системы UNIX для владельца, группы и всех остальных. Оно также содержит остальные биты слова состояния, такие как SETUID, SETGID и т. п.

Чтобы необработанные устройства могли быть представлены на CD-ROM, вводится поле PN. Оно содержит старший и младший номера устройств, ассоциированных с файлом. Таким образом, содержимое каталога /dev может быть записано на CD-ROM и позднее правильно воссоздано на другой системе.

Поле SL используется для символьных связей. Оно позволяет файлу из одной файловой системы ссылаться на файл из другой файловой системы.

Вероятно, наиболее важным является поле NM. С его помощью можно указать для файла второе имя. Этого имени не касаются ограничения стандарта ISO 9660, что позволяет указывать произвольные имена файлов системы UNIX на CD-ROM.

Следующие три поля используются вместе, чтобы обойти ограничения стандарта ISO 9660 на глубину вложенности каталогов. С их помощью можно указать, куда в дереве иерархии должен быть перемещен тот или иной каталог.

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

Расширения Joliet

Сообщество UNIX было не единственной группой, которой требовалось расширение стандарта ISO 9660. Корпорация Microsoft также пришла к выводу, что стандарт ISO 9660 содержит слишком много ограничений (хотя большинство ограничений было вызвано в первую очередь требованием совместимости с файловой системой MS-DOS фирмы Microsoft). Поэтому корпорация Microsoft разработала некоторые расширения, названные Joliet. Они должны были позволить копировать на CD-ROM-диск и восстанавливать с него файловую систему Windows подобно тому, как расширения Рок-Ридж позволяли работать с файловой системой UNIX. Теоретически все программы, работающие в операционной системе Windows и использующие CD-ROM, включая программы записи на CD-R, поддерживают расширение Joliet.

Основными расширениями, содержащимися в Joliet, являются:

1. Длинные имена файлов.

2. Набор символов Unicode.

3. Глубина вложенности каталогов, превышающая восемь уровней.

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

Первое расширение позволяет использовать имена файлов длиной до 64 символов. Второе расширение разрешает использовать для имен файлов символы Unicode. Поскольку символы Unicode занимают два байта, максимальное имя файла в расширении Joliet занимает 128 байт.

Как и Рок-Ридж, расширение Joliet устраняет ограничение на глубину вложенности каталогов. Каталоги могут вкладываться друг в друга на любую требуемую глубину. Наконец, у имен каталогов могут быть расширения. Неясно, почему было включено такое расширение стандарта, поскольку каталоги в файловой системе Windows практически никогда не используют расширений, но, возможно, однажды они потребуются.

Файловая система MS-DOS

Файловая система MS-DOS во многом напоминает файловую систему СР/М, включая использование имен файлов, состоящих из 8 + 3 символов верхнего регистра. В первой версии системы (MS-DOS 1.0) был даже всего один каталог, как и в СР/М. Однако, начиная с MS-DOS 2.0, функциональность файловой системы значительно расширилась. Самым серьезным улучшением явился переход на иерархическую файловую систему, в которой каталоги могли вкладываться друг в друга на произвольную глубину. Это означало, что корневой каталог (размер которого по-прежнему был ограничен) мог содержать подкаталоги, которые, в свою очередь, также могли содержать подкаталоги и т. д. до бесконечности. Связи, принятые в UNIX, не допускались, поэтому файловая система представляла собой дерево, начинавшееся в корневом каталоге. Однако в отличие от СР/М, в MS-DOS нет концепции различных пользователей. Соответственно, любой вошедший в систему пользователь получает доступ сразу ко всем файлам.

Хотя каталоги в файловой системе MS-DOS переменного размера, используемые каталоговые записи, как и в СР/М, имеют фиксированный размер 32 байт. Формат описателя файла системы MS-DOS показан на рисунке ниже. В нем содержится имя файла, его атрибуты, дата и время создания, номер начального блока и точный размер файла. Имена файлов короче 8 + 3 символов выравниваются по левому краю полей и дополняются пробелами, каждое поле отдельно. Поле Attributes (атрибуты) представляет собой новое поле, содержащее биты, указывающие, что для файла разрешено только чтение, что файл должен быть заархивирован, что файл является системным или скрытым. Запись в файл, для которого разрешено только чтение, не разрешается. Таким образом осуществляется защита файлов от случайной записи или удаления. Бит archived (архивный) не устанавливается и не проверяется операционной системой MS-DOS. Он зарезервирован в описателе для архивирующих программ уровня пользователя, сбрасывающих этот бит при создании резервной копии файла, в то время как программы, модифицирующие файл, должны устанавливать этот бит. Таким образом архивирующая программа может определить, какие файлы подлежат архивации. Бит hidden (скрытый файл) позволяет избежать отображения файла в перечне файлов каталога. Основное его назначение заключается в том, чтобы скрыть от неопытных пользователей файлы, назначение которых им неизвестно. Наконец, бит system (системный) также скры- скрывает файлы и защищает их от случайного удаления командой del. Этот бит установлен у основных компонентов системы MS-DOS.

Рис. Формат каталоговой записи в системе MS-DOS

Каталоговая запись также содержит дату и время создания или последнего изменения файла. Время хранится с точностью 2 с, так как для него отведено 2-байтовое поле, способное содержать всего 65 536 уникальных значений, а в сутках 86 400 с. Поле времени разбивается на подполя секунд (5 бит), минут (6 бит) и часов (5 бит). 16-разрядное поле даты также разбивается па три подполя: день (5 бит), месяц (4 бит) и год - 1980 (7 бит). При 7 двоичных разрядах для хранения года и 1980 в качестве точки отсчета максимальное значение года, которое можно выразить таким способом, - это 2107-й. Таким образом, файловая система MS-DOS имеет встроенную проблему 2108 года.

В отличие от файловой системы СР/М, не хранящей точного размера файла, система MS-DOS хранит точный размер. Поскольку для размера файла используется 32-разрядное число, в теории файлы могут быть размером до 4 Гбайт. Однако другие пределы (описываемые ниже) ограничивают максимальный размер файла размером 2 Гбайт или меньше.

Другое отличие системы MS-DOS от СР/М состоит в том, что дисковые адреса файлов не хранятся прямо в их описателях, возможно, поскольку разработчики системы понимали, что большие жесткие диски однажды появятся в мире MS-DOS. Вместо этого файловая система MS-DOS хранит номера блоков файла в специальной таблице размещения файлов, в оперативной памяти. В каталоговой записи хранится номер первого блока файла. Этот номер используется в качестве индекса для 64 К элементов FAT-таблицы, хранящейся в оперативной памяти. Все блоки файла могут быть найдены, если проследовать по цепочке элементов таблицы. Принцип действия FAT-таблицы проиллюстрирован на рис. 6.11.

В зависимости от количества блоков на диске в системе MS-DOS применяется три версии файловой системы FAT: FAT-12, FAT-16 и FAT-32. В действительности FAT-32 является неверным названием, так как используются только 28 младших битов дискового адреса. Ее следовало бы назвать FAT-28, но степени двух звучат гораздо приятнее.

Во всех файловых системах FAT размер блока диска в байтах может быть установлен равным некоторому числу, кратному 512, с наборами разрешенных размеров блоков, различными для каждого варианта FAT. В первой версии системы MS-DOS использовалась FAT-12 с 512-байтовыми блоками, что позволяло создавать дисковые разделы размером до 212 х 512 байт (на самом деле только 4086 х 512 байт, так как 10 дисковых адресов использовались как специальные маркеры - конец файла, дефектный блок и т. д.). При этом максимальный размер дискового раздела мог составлять 2 Мбайт, а в оперативной памяти FAT-таблица занимала 4096 элементов по два байта каждый. Кроме того, обработка 12-разрядных адресов была довольно медленной.

Такая система неплохо работала на гибких дисках, но с появлением жестких дисков появились проблемы. Корпорация Microsoft попыталась решить проблему, разрешив использовать дисковые блоки (кластеры) размером 1, 2 и 4 Кбайт. Это позволило сохранить структуру и размер таблицы FAT-12 и увеличить размер дискового раздела до 16 Мбайт.

Так как система MS-DOS поддерживала до четырех дисковых разделов на диске, новая файловая система FAT-12 могла работать с дисками емкостью до 64 Мбайт. Для поддержки винчестеров большего размера нужно было предпринимать что-то еще. В результате была разработана файловая система FAT-16, с 16-разрядными дисковыми указателями. Дополнительно было разрешено использовать кластеры размеров 8, 16 и 32 Кбайт. Теперь таблица FAT-16 постоянно занимала 128 Кбайт оперативной памяти, но с ростом размеров памяти компьютеров она получила широкое применение и быстро вытеснила файловую систему FAT-12. Максимальный размер дискового раздела, поддерживаемый системой FAT-16, равен 2 Гбайт (64 К элементов по 32 Кбайт каждый), а максимальный размер диска - 8 Гбайт, то есть четыре раздела по 2 Гбайт каждый.

С выходом второй версии операционной системы Windows 95 была представлена файловая система FAT-32 со своими 28-разрядными адресами. При этом версия системы MS-DOS, лежащая в основе Windows 95, была адаптирована для поддержки FAT-32. Теоретически в этой системе разделы могли быть по 228 х 215 байт, но фактически размер разделов ограничен 2 Тбайт, так как внутренне система учитывает размеры разделов в 512-байтовых секторах с помощью 32-разрядных чисел, а 232 х 29 байт равно 2 Тбайт. Максимальный размер раздела для всех трех типов FAT и различных размеров кластеров показан в таблице. Пустым элементам таблицы соответствуют запрещенные комбинации.

Таблица Максимальный размер раздела для различных размеров кластеров

________________________________________

Размер кластера, Кбайт FAT-12, Мбайт FAT-16, Мбайт FAT-32, Тбайт

________________________________________

0,5 2 1 4

2 8 128

4 16 256 1

8 512 2 16 1024 2

32 2048 2 ________________________________________

Помимо поддержки дисков большего размера, файловая система FAT-32 обладает двумя другими преимуществами перед системой FAT-16. Во-первых, 8-гигабайтный диск, использующий FAT-32, может состоять из всего одного раздела. Другое преимущество заключается в том, что для дискового раздела заданного размера могут использоваться блоки меньшего размера. Например, для 2-гигабайтного дискового раздела система FAT-16 должна пользоваться 32-килобайтными блоками, в противном случае при наличии всего 64 К доступных дисковых адресов она не смогла бы покрыть весь раздел. В то же время система FAT-32 для такого же дискового раздела может использовать, например, блоки размером 4 Кбайт. Преимущество блоков меньшего размера заключается в том, что длина большинства файлов менее 32 Кбайт. При размере блока в 32 Кбайт даже 10-байтовый файл будет занимать на диске 32 Кбайт. Если средний размер файлов, скажем, равен 8 Кбайт, тогда при использовании 32-килобайтных блоков около 3/4 дискового пространства будет теряться, то есть эффективность использования диска будет низкой. При 8-килобайтных файлах и 4-килобайтных блоках потерь дискового пространства не будет, но платой за это будет то, что для хранения таблицы FAT потребуется значительно больше оперативной памяти. При 4-килобайтных блоках 2-гигабайтный раздел будет состоять из 512 К блоков, поэтому таблица FAT должна состоять из 512 К элементов (занимая 2 Мбайт ОЗУ).

Файловая система MS-DOS использует FAT для учета свободных блоков. Любой незанятый блок помечается специальным кодом. Когда системе MS-DOS требуется новый блок на диске, она ищет этот код в таблице FAT. Таким образом, битовый массив или список свободных блоков не нужны.

Файловая система Windows 98

Для того чтобы позволить пользователям работать с длинными именами файлов, можно было просто разработать новую структуру каталога. Недостаток такого подхода состоит в том, что если бы корпорация Microsoft сделала это, пользователи, переходящие с Windows 3 на Windows 95 или Windows 98, не смогли бы иметь доступ ко всем своим файлам одновременно из обеих систем. В корпорации Microsoft было принято политическое решение о том, что файлы, созданные в системе Windows 98, должны быть также доступны из Windows 3. В результате была разработана система поддержки длинных имен, обладавшая обратной совместимостью со старой системой имен 8 + 3, применявшейся в MS-DOS. Поскольку такие требования обратной совместимости нередки в компьютерной промышленности, стоит детально ознакомиться с тем, как корпорация Microsoft выполнила эту задачу.

Итак, каталоговая структура системы Windows 98 должна была обладать обратной совместимостью со структурой каталогов MS-DOS. Как уже было показано, эта структура представляет собой просто список 32-байтовых описателей. Такой формат был заимствован у файловой системы СР/М (написанной для процессора Intel 8080), что демонстрирует, насколько долго устаревшие структуры могут существовать в компьютерном мире.

Однако в 32-байтовом описателе файла оставались незадействованными 10, что и было использовано. Это изменение не имеет никакого отношения к длинным именам, но используется в Windows 98, поэтому стоит обратить на него внимание.

Рис. Формат каталоговой записи в системе MS-DOS

Изменение каталоговой записи состоит в добавлении пяти новых полей на место неиспользовавшихся 10 байт. Поле NT предназначено для совместимости с Windows NT и обеспечивает отображение имени файла в правильном регистре. Поле Sec решает проблему невозможности хранения времени суток в 16-битовом поле с точностью до секунды. Восемь дополнительных разрядов позволяют хранить поле Creation time (время создания) с точностью до 10 мс. Еще одно новое поле Last access (дата последнего доступа) хранит дату последнего доступа к файлу. Наконец, переход на файловую систему FAT-32 означает, что номера блоков теперь 32-разрядные, поэтому для хранения старших разрядов номера начального блока файла требуются дополнительные 16 бит.

Выбранное решение для представления длинных имен файлов, обладающему обратной совместимостью с MS-DOS заключается в назначении каждому файлу двух имен: (потенциально) длинного имени файла (в формате Unicode, для совместимости с Windows NT) и имени формата 8 + 3 для совместимости с MS-DOS. Доступ к файлам может быть получен по любому имени. Когда создается файл, имя которого не удовлетворяет правилам MS-DOS (8 символов для имени и 3 символа для расширения, ограниченный набор символов, отсутствие пробелов и т. д.), Windows 98 создает дополнительное имя формата MS-DOS в соответствии с определенным алгоритмом. Берутся первые шесть символов имени, преобразуются при необходимости в верхний регистр ASCII, после чего к ним добавляется суффикс -1. Если такое имя уже есть, то используется суффикс -2 и т. д. Кроме того, удаляются пробелы и лишние точки, а определенные символы преобразуются в символы подчеркивания.

Имя формата MS-DOS хранится в каталоге прямо в описателе. Если у файла есть также длинное имя, оно хранится в одной или нескольких каталоговых записях, предшествующих описателю файла с именем в формате MS-DOS. Каждая такая запись содержит до 13 символов формата Unicode. Элементы имени хранятся в обратном порядке, начинаясь сразу перед описателем файла в формате MS-DOS и последующими фрагментами перед ним. Формат каждого фрагмента длинного имени показан на рисунке ниже.

Рис. Формат каталоговой записи с фрагментом длинного имени файла в Windows 98

Для фрагмента длинного имени поле Attributes содержит значение 0x0F, что соответствует невозможной комбинации атрибутов для описателя файла в MS-DOS. Старые программы, написанные для работы в MS-DOS, читая каталог, просто игнорируют такие описатели как неверные. Порядок фрагментов имени учитывается в первом байте каталоговой записи. Последний фрагмент имени отмечается добавлением к порядковому номеру числа 64. Поскольку для порядкового номера используется всего 6 бит, теоретически максимальная длина имени файла может составить 63 х 13 = 819 символов. На практике она ограничена 260 символами по историческим причинам.

Каждый фрагмент длинного имени содержит поле Checksum (контрольная сумма) во избежание следующей проблемы. Сначала программа, работающая в системе Windows 98, создает файл с длинным именем. Затем компьютер перезагружается в MS-DOS или Windows 3. После этого старая программа, удаляя файл, удаляет из каталога имя формата MS-DOS, но оставляет в нем предшествующее ему длинное имя (так как ей ничего не известно о длинных именах). Наконец, какая-то программа создает новый файл, используя освободившееся место в каталоге. К этому моменту мы имеем верную последовательность фрагментов длинного имени, предшествующую описателю файла формата MS-DOS, который не имеет к ней никакого отношения. Поле Checksum позволяет системе Windows 98 обнаружить такую ситуацию. Конечно, поскольку для поля Checksum используется всего один байт, есть один шанс из 256, что Windows 98 не заметит подмены.

Каталоговая структура обладает некоторой избыточностью, позволяющей обнаруживать проблемы, вызванные вмешательством старых программ, написанных для работы в Windows 3. Порядковый номер в начале каждого фрагмента длинного имени не так уж и нужен, так как бит 0x40 помечает первый фрагмент, но он обеспечивает дополнительную избыточность. Реализация файловой системы FAT-32 концептуально близка к реализации файловой системы FAT-16. Однако вместо массива из 65 536 элементов в ней используется столько, сколько нужно, чтобы покрыть весь раздел диска. Если диск содержит миллион блоков, то и таблица будет состоять из миллиона элементов. Для экономии памяти система Windows 98 не хранит их все сразу в памяти, а использует окно, накладываемое на таблицу.

Файловая система UNIX V7

Даже в ранних версиях системы UNIX применялась довольно сложная многопользовательская файловая система, так как в основе этой системы лежала операционная система MULTICS. Ниже будет рассмотрена файловая система V7, разработанная для компьютера PDP-11, сделавшего систему UNIX знаменитой.

Файловая система представляет собой дерево, начинающееся в корневом каталоге, с добавлением связей, формирующих направленный ациклический граф. Имена файлов могут содержать до 14 символов, включающих в себя любые символы ASCII, кроме косой черты (использовавшейся в качестве разделителя компонентов пути) и символа NUL (использовавшегося для дополнения имен короче 14 символов). Символ NUL обозначается байтом 0.

Каталог UNIX содержит по одной записи для каждого файла этого каталога. Каждая каталоговая запись максимально проста, так как в системе UNIX используется схема i-узлов (см. рис. 6.12). Каталоговая запись состоит всего из двух полей: имени файла (14 байт) и номера i-узла для этого файла (2 байт), как показано на рис. 6.33. Эти параметры ограничивают количество файлов в файловой системе числом 64 К.

Рис. Каталоговая запись файловой системы UNIX V7

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

Для учета дисковых блоков файла используется обобщение схемы, позволяющее работать с очень большими файлами. Первые 10 дисковых адресов хранятся в самом i-узле. Таким образом, для небольших файлов вся необходимая информация содержится прямо в i-узле, считываемом с диска при открытии файла. Для файлов большего размера один из адресов в i-узле представляет собой адрес блока диска, называемого одинарным косвенным блоком. Этот блок содержит дополнительные дисковые адреса. Если и этого недостаточно, используется другой адрес в i-узле, называемый двойным косвенным блоком, и содержащий адрес блока, в котором хранятся адреса однократных косвенных блоков. Если и этого мало, используется тройной косвенный блок. Полная схема показана на рис. 6.34.

Виртуальная файловая система

Одна операционная система может быть вынуждена работать сразу с несколькими версиями файловых систем. Так, например, компьютер под управлением Unix должен работать как с V7 и ее более современными реализациями, так и с DOS- и Windows-разделами, находящимися на том же диске (при условии возможности загрузки нескольких ОС) или, например, на дискете или CD-ROM. В связи с этим под Unix вводится понятие виртуальной файловой системы (VFS). Нечто подобное существует и под другими ОС. В конечном счете, пользователю и пользовательским приложениям все равно, файловая система какого типа хранит их файлы. Основная задача – получить к ним доступ по единому интерфейсу. В связи с этим все файловые системы сводятся в единую виртуальную систему, за обращение к фрагментам которой отвечают самостоятельные драйвера. Приложения обращаются к VFS. А она принимает решение к какому из драйверов необходимо обратиться.

Драйверы

Как это уже отмечалось в предыдущих лекциях, драйверы служат для предоставления стандартного интерфейса к разнообразному оборудованию, работа с которым, в общем случае, не стандартизована. Считается, что драйвер работает с некоторым устройством, осуществляющим ввод и/или вывод информации. В общем случае это неверно. Во-первых, физически устройство может отсутствовать, а работа будет вестись с некоторым виртуальным устройством. Так работает, например, драйвер печати в файл в формате pdf. Во-вторых, устройство может не осуществлять ввода/вывода. Примером может служить драйвер таймера. Однако таймер может воспринимать команды, что на некотором уровне абстракции можно принять за вывод команд во внешнее устройство. Кстати, сам по себе таймер не является внешним устройством. Однако сама абстракция является достаточно удобной для того, чтобы отказаться от подробностей рассматривать все устройства как внешние и способные на ввод и/или вывод. Так, например, в Windows вводится понятие HAL (hardware abstract layer) – абстрактный (виртуальный) уровень аппаратного обеспечения. На этом уровне находятся некоторые «идеальные» (как в смысле Платона (иными словами виртуальные), так и в смысле поведения) аппаратные устройства, обладающие стандартным интерфейсом. С одной стороны, HAL умеет принимать команды и данные от пользовательских процессов и отдавать им данные. С другой стороны, данный уровень обеспечивается конкретными драйверами, умеющими работать с конкретными устройствами. Задачами HAL является обеспечение работы с виртуальными устройствами: ввод нового устройства в систему, обеспечение интерфейса к этому устройству, учет устройств и т.д.

Все системные вызовы, связанные с осуществлением операций ввода-вывода, можно разбить на три группы по способам реализации взаимодействия процесса и устройства ввода-вывода.

 К первой, наиболее привычной для большинства программистов группе относятся блокирующиеся системные вызовы. Как следует из самого названия, применение такого вызова приводит к блокировке инициировавшего его процесса, т. е. процесс переводится операционной системой из состояния исполнение в состояние ожидание. Завершив выполнение всех операций ввода-вывода, предписанных системным вызовом, операционная система переводит процесс из состояния ожидание в состояние готовность. После того как процесс будет снова выбран для исполнения, в нем произойдет окончательный возврат из системного вызова. Типичным для применения такого системного вызова является случай, когда процессу необходимо получить от устройства строго определенное количество данных, без которых он не может выполнять работу далее.

 Ко второй группе относятся неблокирующиеся системные вызовы. Их название не совсем точно отражает суть дела. В простейшем случае процесс, применивший неблокирующийся вызов, не переводится в состояние ожидание вообще. Системный вызов возвращается немедленно, выполнив предписанные ему операции ввода-вывода полностью, частично или не выполнив совсем, в зависимости от текущей ситуации (состояния устройства, наличия данных и т. д.). В более сложных ситуациях процесс может блокироваться, но условием его разблокирования является завершение всех необходимых операций или окончание некоторого промежутка времени. Типичным случаем применения неблокирующегося системного вызова может являться периодическая проверка на поступление информации с клавиатуры при выполнении трудоемких расчетов.

 К третьей группе относятся асинхронные системные вызовы. Процесс, использовавший асинхронный системный вызов, никогда в нем не блокируется. Системный вызов инициирует выполнение необходимых операций ввода-вывода и немедленно возвращается, после чего процесс продолжает свою регулярную деятельность. Об окончании завершения операции ввода-вывода операционная система впоследствии информирует процесс изменением значений некоторых переменных, передачей ему сигнала или сообщения или каким-либо иным способом. Необходимо четко понимать разницу между неблокирующимися и асинхронными вызовами. Неблокирующийся системный вызов для выполнения операции read вернется немедленно, но может прочитать запрошенное количество байтов, меньшее количество или вообще ничего. Асинхронный системный вызов для этой операции также вернется немедленно, но требуемое количество байтов рано или поздно будет прочитано в полном объеме.

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

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

В некоторых операционных системах вместо использования spooling для устранения race condition применяется механизм монопольного захвата устройств процессами. Если устройство свободно, то один из процессов может получить его в монопольное распоряжение. При этом все другие процессы при попытке осуществления операций над этим устройством будут либо блокированы (переведены в состояние ожидание), либо получат информацию о невозможности выполнения операции до тех пор, пока процесс, захвативший устройство, не завершится или явно не сообщит операционной системе о своем отказе от его использования.

Обеспечение spooling и механизма захвата устройств является прерогативой базовой подсистемы ввода-вывода.

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

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

Задача планирования использования устройства обычно возлагается на базовую подсистему ввода-вывода, однако для некоторых устройств лучшие алгоритмы планирования могут быть тесно связаны с деталями их внутреннего функционирования. В таких случаях операция планирования переносится внутрь драйвера соответствующего устройства, так как эти детали скрыты от базовой подсистемы. Для этого в интерфейс драйвера добавляется еще одна специальная функция, которая осуществляет выбор очередного запроса, – функция strategy.

Вычислительные сети

Принято говорить о локальных вычислительных сетях (LAN – Local Area Network) и глобальных вычислительных сетях (WAN – Wide Area Network). Строгого определения этим понятиям обычно не дается, а принадлежность сети к тому или иному типу часто определяется взаимным расположением вычислительных комплексов, объединенных в сеть. Так, например, в большинстве работ к локальным сетям относят сети, состоящие из компьютеров одной организации, размещенные в пределах одного или нескольких зданий, а к глобальным сетям – сети, охватывающие все компьютеры в нескольких городах и более. Зачастую вводится дополнительный термин для описания сетей промежуточного масштаба – муниципальных или городских вычислительных сетей (MAN – Metropolitan Area Network) – сетей, объединяющих компьютеры различных организаций в пределах одного города или одного городского района. Также вводится понятие CAN – campus area network –сеть университетского городка, то есть сеть объединяющая достаточно большое количество компактно расположенных зданий. Таким образом, упрощенно можно рассматривать глобальные сети как сети, состоящие из локальных и муниципальных сетей. А муниципальные сети, в свою очередь, могут состоять из нескольких локальных сетей. На самом деле деление сетей на локальные, глобальные и муниципальные обычно связано не столько с местоположением и принадлежностью вычислительных систем, соединенных сетью, сколько с различными подходами, применяемыми для решения поставленных вопросов в рамках той или иной сети, – с различными используемыми протоколами.

Многоуровневая модель построения сетевых вычислительных систем

Даже беглого взгляда на перечень проблем, связанных с логической организацией взаимодействия удаленных процессов, достаточно, чтобы понять, что построение сетевых средств связи – задача более сложная, чем реализация локальных средств связи. Поэтому обычно задачу создания таких средств решают по частям, применяя уже неоднократно упоминавшийся нами "слоеный", или многоуровневый, подход.

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

На самом верхнем уровне находятся пользовательские процессы, которые инициируют обмен данными. Количество и функции промежуточных уровней варьируются от одной системы к другой. Вернемся к нашей аналогии с пересылкой почтовых отправлений между людьми, проживающими в разных городах, правда, с порядком их пересылки несколько отличным от привычного житейского порядка. Рассмотрим в качестве пользовательских процессов руководителей различных организаций, желающих обменяться письмами. Руководитель (пользовательский процесс) готовит текст письма (данные) для пересылки в другую организацию. Затем он отдает его своему секретарю (совершает системный вызов – обращение к нижележащему уровню), сообщая, кому и куда должно быть направлено письмо. Секретарь снимает с него копию и выясняет адрес организации. Далее идет обращение к нижестоящему уровню, допустим, письмо направляется в канцелярию. Здесь оно регистрируется (ему присваивается порядковый номер), один экземпляр запечатывается в конверт, на котором указывается, кому и куда адресовано письмо, впечатывается адрес отправителя. Копия остается в канцелярии, а конверт отправляется на почту (переход на следующий уровень). На почте наклеиваются марки и делаются другие служебные пометки, определяется способ доставки корреспонденции и т. д. Наконец, поездом, самолетом или курьером (физический уровень!) письмо следует в другой город, в котором все уровни проходятся в обратном порядке. Пользовательский уровень (руководитель) после подготовки исходных данных и инициации процесса взаимодействия далее судьбой почтового отправления не занимается. Все остальное (включая, быть может, проверку его доставки и посылку копии в случае утери) выполняют нижележащие уровни.

Заметим, что на каждом уровне взаимодействия в городе отправителя исходные данные (текст письма) обрастают дополнительной служебной информацией. Соответствующие уровни почтовой службы в городе получателя должны уметь понимать эту служебную информацию. Таким образом, для одинаковых уровней в различных городах необходимо следование специальным соглашениям – поддержка определенных горизонтальных протоколов.

Точно так же в сетевых вычислительных системах все их одинаковые уровни, лежащие выше физического, виртуально обмениваются данными посредством горизонтальных протоколов. Наличие такой виртуальной связи означает, что уровень N компьютера 2 должен получить ту же самую информацию, которая была отправлена уровнем N компьютера 1. Хотя в реальности эта информация должна была сначала дойти сверху вниз до уровня 1 компьютера 1, затем передана уровню 1 компьютера 2 и только после этого доставлена снизу вверх уровню N этого компьютера.

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

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

Эталоном многоуровневой схемы построения сетевых средств связи считается семиуровневая модель открытого взаимодействия систем (Open System Interconnection – OSI), предложенная Международной организацией Стандартов (International Standard Organization – ISO) и получившая сокращенное наименование OSI/ISO.

Давайте очень кратко опишем, какие функции выполняют различные уровни модели OSI/ISO:

 Уровень 1 – физический. Этот уровень связан с работой hardware. На нем определяются физические аспекты передачи информации по линиям связи, такие как: напряжения, частоты, природа передающей среды, способ передачи двоичной информации по физическому носителю, вплоть до размеров и формы используемых разъемов. В компьютерах за поддержку физического уровня обычно отвечает сетевой адаптер.

 Уровень 2 – канальный. Этот уровень отвечает за передачу данных по физическому уровню без искажений между непосредственно связанными узлами сети. На нем формируются физические пакеты данных для реальной доставки по физическому уровню. Протоколы канального уровня реализуются совместно сетевыми адаптерами и их драйверами (понятие драйвера рассматривалось в лекции 13).

 Уровень 3 – сетевой. Сетевой уровень несет ответственность за доставку информации от узла-отправителя к узлу-получателю. На этом уровне частично решаются вопросы адресации, осуществляется выбор маршрутов следования пакетов данных, решаются вопросы стыковки сетей, а также управление скоростью передачи информации для предотвращения перегрузок в сети.

 Уровень 4 – транспортный. Регламентирует передачу данных между удаленными процессами. Обеспечивает доставку информации вышележащим уровнем с необходимой степенью надежности, компенсируя, быть может, ненадежность нижележащих уровней, связанную с искажением и потерей данных или доставкой пакетов в неправильном порядке. Наряду с сетевым уровнем может управлять скоростью передачи данных и частично решать проблемы адресации.

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

 Уровень 6 – уровень представления данных. Отвечает за форму представления данных, перекодирует текстовую и графическую информацию из одного формата в другой, обеспечивает ее сжатие и распаковку, шифрование и декодирование.

 Уровень 7 – прикладной. Служит для организации интерфейса между пользователем и сетью. На этом уровне реализуются такие сервисы, как удаленная передача данных, удаленный терминальный доступ, почтовая служба и работа во Всемирной паутине (Web-браузеры).

Рис. Семиуровневая эталонная модель OSI/ISO

Надо отметить, что к приведенной эталонной модели большинство практиков относится без излишнего пиетета. Эта модель не предвосхитила появления различных семейств протоколов, таких как, например, семейство протоколов TCP/IP, а наоборот, была создана под их влиянием. Ее не следует рассматривать как готовый оптимальный чертеж для создания любого сетевого средства связи. Наличие некоторой функции на определенном уровне не гарантирует, что это ее наилучшее место, некоторые функции (например, коррекция ошибок) дублируются на нескольких уровнях, да и само деление на 7 уровней носит отчасти произвольный характер. Хотя в конце концов были созданы работающие реализации этой модели, но наиболее распространенные семейства протоколов лишь до некоторой степени согласуются с ней. Ценность предложенной эталонной модели заключается в том, что она показывает направление, в котором должны двигаться разработчики новых вычислительных сетей.

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

Одноуровневые адреса

В небольших компьютерных сетях можно построить одноуровневую систему адресации. При таком подходе каждый процесс, желающий стать участником удаленного взаимодействия (при прямой адресации), и каждый объект, для такого взаимодействия предназначенный (при непрямой адресации), получают по мере необходимости собственные адреса (символьные или числовые), а сами вычислительные комплексы, объединенные в сеть, никаких самостоятельных адресов не имеют. Подобный метод требует довольно сложного протокола обеспечения уникальности адресов. Вычислительный комплекс, на котором запускается взаимодействующий процесс, должен запросить все компьютеры сети о возможности присвоения процессу некоторого адреса. Только после получения от них согласия процессу может быть назначен адрес. Поскольку процесс, посылающий данные другому процессу, не может знать, на каком компоненте сети находится процесс-адресат, передаваемая информация должна быть направлена всем компонентам сети (так называемое широковещательное сообщение – broadcast message), проанализирована ими и либо отброшена (если процесса-адресата на данном компьютере нет), либо доставлена по назначению. Так как все данные постоянно передаются от одного комплекса ко всем остальным, такую одноуровневую схему обычно применяют только в локальных сетях с прямой физической связью всех компьютеров между собой (например, в сети NetBIOS на базе Ethernet), но она является существенно менее эффективной, чем двухуровневая схема адресации.

Двухуровневые адреса

При двухуровневой адресации полный сетевой адрес процесса или промежуточного объекта для хранения данных складывается из двух частей – адреса вычислительного комплекса, на котором находится процесс или объект в сети (удаленного адреса), и адреса самого процесса или объекта на этом вычислительном комплексе (локального адреса). Уникальность полного адреса будет обеспечиваться уникальностью удаленного адреса для каждого компьютера в сети и уникальностью локальных адресов объектов на компьютере. Давайте подробнее рассмотрим проблемы, возникающие для каждого из компонентов полного адреса.

Удаленная адресация и разрешение адресов

Каждая машина в сети получает символьное, часто даже содержательное имя. Компьютер не разбирается в смысловом содержании символов, ему проще оперировать числами, желательно одного и того же формата, которые помещаются, например, в 4 байта или в 16 байт. Поэтому каждый компьютер в сети для удобства работы вычислительных систем получает числовой адрес. Возникает проблема отображения пространства символьных имен (или адресов) вычислительных комплексов в пространство их числовых адресов. Эта проблема получила наименование проблемы разрешения адресов.

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

В современной сетевой паутине этот подход является неприемлемым. Дело даже не в размерах подобного файла, а в частоте требуемых обновлений и в огромном количестве рассылок, что может полностью подорвать производительность сети. Проблема состоит в том, что добавление или удаление компонента сети требует внесения изменений в файлы на всех сетевых машинах. Второй метод разрешения адресов заключается в частичном распределении информации о соответствии символьных и числовых адресов по многим комплексам сети, так что каждый из этих комплексов содержит лишь часть полных данных. Он же определяет и правила построения символических имен компьютеров. Один из таких способов, используемый в Internet, получил английское наименование Domain Name Service или сокращенно DNS.

Организуем логически все компьютеры сети в некоторую древовидную структуру, напоминающую структуру директорий файловых систем, в которых отсутствует возможность организации жестких и мягких связей и нет пустых директорий. Будем рассматривать все компьютеры, входящие во Всемирную сеть, как область самого низкого ранга (аналог корневой директории в файловой системе) – ранга 0. Разобьем все множество компьютеров области на какое-то количество подобластей (domains). При этом некоторые подобласти будут состоять из одного компьютера, а некоторые – более чем из одного компьютера. Каждую подобласть будем рассматривать как область более высокого ранга. Присвоим подобластям собственные имена таким образом, чтобы в рамках разбиваемой области все они были уникальны. Повторим такое разбиение рекурсивно для каждой области более высокого ранга, которая состоит более чем из одного компьютера, несколько раз, пока при последнем разбиении в каждой подобласти не окажется ровно по одному компьютеру. Глубина рекурсии для различных областей одного ранга может быть разной, но обычно в целом ограничиваются 3 – 5 разбиениями, начиная от ранга 0.

В результате мы получим дерево, неименованной вершиной которого является область, объединяющая все компьютеры, входящие во Всемирную сеть, именованными терминальными узлами – отдельные компьютеры (точнее – подобласти, состоящие из отдельных компьютеров), а именованными нетерминальными узлами – области различных рангов. Используем полученную структуру для построения имен компьютеров, подобно тому как мы поступали при построении полных имен файлов в структуре директорий файловой системы. Только теперь, двигаясь от корневой вершины к терминальному узлу – отдельному компьютеру, будем вести запись имен подобластей справа налево и отделять имена друг от друга с помощью символа ".".

Допустим, некоторая подобласть, состоящая из одного компьютера, получила имя serv, она входит в подобласть, объединяющую все компьютеры некоторой лаборатории, с именем crec. Та, в свою очередь, входит в подобласть всех компьютеров Московского физико-технического института с именем mipt, которая включается в область ранга 1 всех компьютеров России с именем ru. Тогда имя рассматриваемого компьютера во Всемирной сети будет serv.crec.mipt.ru. Аналогичным образом можно именовать и подобласти, состоящие более чем из одного компьютера.

В каждой полученной именованной области, состоящей более чем из одного узла, выберем один из компьютеров и назначим его ответственным за эту область – сервером DNS. Сервер DNS знает числовые адреса серверов DNS для подобластей, входящих в его зону ответственности, или числовые адреса отдельных компьютеров, если такая подобласть включает в себя только один компьютер. Кроме того, он также знает числовой адрес сервера DNS, в зону ответственности которого входит рассматриваемая область (если это не область ранга 1), или числовые адреса всех серверов DNS ранга 1 (в противном случае). Отдельные компьютеры всегда знают числовые адреса серверов DNS, которые непосредственно за них отвечают.

Рассмотрим теперь, как процесс на компьютере serv.crec.mipt.ru может узнать числовой адрес компьютера ssp.brown.edu. Для этого он обращается к своему DNS-серверу, отвечающему за область crec.mipt.ru, и передает ему нужный адрес в символьном виде. Если этот DNS-сервер не может сразу представить необходимый числовой адрес, он передает запрос DNS-серверу, отвечающему за область mipt.ru. Если и тот не в силах самостоятельно справиться с проблемой, он перенаправляет запрос серверу DNS, отвечающему за область 1-го ранга ru. Этот сервер может обратиться к серверу DNS, обслуживающему область 1-го ранга edu, который, наконец, затребует информацию от сервера DNS области brown.edu, где должен быть нужный числовой адрес. Полученный числовой адрес по всей цепи серверов DNS в обратном порядке будет передан процессу, направившему запрос.

Рис. Пример разрешения имен с использованием DNS-серверов

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

Рассмотренный способ разрешения адресов позволяет легко добавлять компьютеры в сеть и исключать их из сети, так как для этого необходимо внести изменения только на DNS-сервере соответствующей области.

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

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

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

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

Показать полностью…
Похожие документы в приложении