Операционные системы. Управление ресурсами

         

Физическая структура файлов


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

Несколько принципиально важных положений являются общими для любых способов управления дисковой памятью.

  1. Дисковая память состоит из блоков, являющихся единицами распределения дискового пространства (например, секторов). Каждый блок имеет уникальный номер (адрес), его идентифицирующий. В каждый блок может быть записана любая информация достаточно сложной структуры, в том числе, и содержащая ссылки на другие блоки.
  2. Каждый физический диск описывается дескриптором диска, который содержит информацию о количестве и размере блоков на диске и о свободном пространстве на диске. Дисковый дескриптор записывается на известное заранее место на диске (чаще всего - в первый блок).
  3. Каждый файл в составе своего дескриптора имеет план своего размещения (layuot) на физическом пространстве диска.
  4. Информация, записываемая на диск, может быть избыточной для обеспечения возможности ее восстановления при сбоях.
  5. Дисковое пространство распределяется блоками фиксированной длины. Даже в тех дисковых архитектурах, которые допускают чтение/запись блоками переменной длины, размер единицы распределения, как правило, все равно фиксирован, например, дорожка. Возможно объединение в единицу распределения нескольких смежных блоков, такой прием носит название кластеризации (clastering), а порции распределения, состоящие из нескольких блоков, называются кластерами.
    Кластеризация может быть как симметричной - с заранее установленным размером кластера, так и асимметричной - с размером кластера, выбираемым для каждого распределения.
  6. Поиск на диске управляющих структур ФС и свободных блоков может оказаться слишком времяемким. Поэтому те управляющие структуры, обращение к которым происходит наиболее часто, обычно копируются в оперативную память. Это создает дополнительные проблемы, связанные с надежностью функционирования ОС. При крахе системы изменения в управляющих структурах могут не быть перенесены из кеша на внешнюю память. Специальные системные процессы ОС обычно обеспечивают периодическое сохранение управляющих структур на внешней памяти.


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

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


Во-вторых, такое распределение требует, чтобы необходимый размер дискового пространства указывался при создании файла - эта информация не всегда может быть предоставлена пользователем, создающим файл. В-третьих, расширение файла за пределы установленного размера невозможно - для файлов с длительным сроком существования эта проблема может стать критической. Перечисленные недостатки могут быть не радикально преодолены, но несколько сглажены, если допустить, чтобы файл занимал не один, а несколько участков дискового пространства. При создании такого файла задаются требования к размеру первичного и вторичного распределения. Файлу выделяется непрерывный участок памяти в соответствии с первичным размером. Если далее оказывается, что файл не помещается в первичный участок, ему выделяется дополнительный участок (экстент - extent), размер которого задается требованием ко вторичному распределению. Экстент занимает непрерывную область на диске, но необязательно смежную с первичным участком. Затем может быть выделен второй экстент и т.д. План файла в его дескрипторе в этом случае представляется массивом пар "начальный адрес - длина", каждый элемент которого соответствует одному экстенту. Размер этого массива в дескрипторе ограничивает допустимое число экстентов.

Очевидно, что смежное распределение является негибким. Это в первую очередь послужило причиной полного отказа от него в ОС Unix и в MS DOS. Однако, в связи с увеличением объемов дисковых накопителей вопросы повышения эффективности обмена приобретают все большее значение и локализация файлов является хорошим средством повышения этой эффективности. В последнее время наметилась тенденция к размещению файлов в смежных областях диска, пусть даже и в рамках несмежной модели распределения (см., например описание ФС HPFS, NTFS, Veritas, JFS в Части II).

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



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


  • списки блоков;
  • карта размещения;
  • списки указателей на блоки.


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



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

Метод списков указателей на блоки предполагает, наличие для каждого файла перечня номеров блоков, ему распределенных. Этот перечень записывается в отдельный блок, специально выделяемый для этой цели, а файловый дескриптор содержит указатель на этот блок. Если в блоке не хватает места для всего перечня, то последний в нем номер адресует блок, содержащий продолжение перечня и т.д. При применении этого метода "в чистом виде" список блоков, как всякий линейный список, может обрабатываться только последовательно, поэтому доступ в блокам файла, имеющим большие виртуальные номера может быть значительно замедлен. Поэтому на практике применяются различные модификации этого метода. Классическим примером такого подхода является ФС s5 первых версий ОС Unix.



Учет дискового пространства, выделенного файлу (план размещения), ведется в s5 следующим образом. Как показали исследования, на любом носителе всегда есть большое число файлов, объем которых не превышает 1 Кбайт. Для таких файлов нет никакой необходимости выделять отдельные блоки для размещения плана, а тем более - увязывать эти блоки в какие-либо списки. Поэтому непосредственно в файловом дескрипторе содержится массив из 10 номеров первых блоков файла. При размере блока 512 байт первые 5 Кбайт файла адресуются непосредственно из файлового дескриптора. Одиннадцатый элемент этого массива содержит адрес блока, в котором записано еще 128 номеров следующих блоков файла. Таким образом, доступ к следующим 64 Кбайтам файла производится путем косвенной адресации из дескриптора через этот блок адресов. Двенадцатый элемент содержит адрес блока, в котором записано еще 128 номеров блоков, каждый из которых адресует еще 128 блоков данных файла - это обеспечивает доступ к следующим 8 Мбайтам путем двухуровневой косвенной адресации. Наконец, тринадцатый элемент массива в дескрипторе обеспечивает доступ через трехуровневую косвенную адресацию еще к 2 Гбайтам файла. Структура плана размещения показана на Рисунке 7.4.



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

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


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

Списки свободных блоков организуются точно так же, как и списки блоков, принадлежащих файлу. Дескриптор диска содержит указатель на начало списка свободных блоков. Последовательная природа списка не оказывает влияния на эффективность его обработки, так как список свободных блоков может обрабатываться по дисциплине LIFO - выборка блока происходит из начала списка, и новый свободный блок также добавляется в начало списка. Изящный пример работы со свободными блоками показывает та же ФС s5, пример относится к категории "ленивых политик", свойственных этой ОС Unix.

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




Содержание раздела