Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 50
Текст из файла (страница 50)
Такой подходобеспечивает большую надежность файловой системы.193СуперблокРис. 116.4.2.4.1СуперблокСуперблокСтруктура файловой системы версии FFS BSD.Стратегии размещенияРабота системы основывается на трех концепциях. Первой концепцией являетсяоптимизация размещения каталога. При создании каталога система осуществляет поисккластера, наиболее свободного в данный момент с точки зрения использования индексныхдескрипторов, т.е.
ищутся кластеры, количество свободных индексных дескрипторов в которыхпревосходит некоторую среднюю величину, и среди найденных кластеров выбирается кластер снаименьшим количеством каталогов.Следующей стратегией является равномерность использования блоков данных. Вовремя создания файла он делится на несколько частей. Часть файла, которая имеланепосредственную адресацию из индексного дескриптора, по возможности размещается в том жекластере, что и индексный дескриптор.
Оставшиеся части файла делятся на равные порции,которые файловая система размещает в отдельных кластерах. Перечисленные стратегии призваныдля борьбы фрагментации файла по разделу: файл либо целиком размещается в одном кластере,либо он размещается в нескольких кластерах, но тогда в них размещаются достаточно большиефрагменты подряд идущих блоков.И, наконец,третья стратегияразмещения — технологическое размещениепоследовательных блоков файлов (4.2.4.1). Представим следующую ситуацию: пускайнеобходимо прочитать два последовательных блока с магнитного диска (будем считать, что этиблоки находятся на одной дорожке магнитного диска).
Это означает, что данная задача требуетдвух последовательных обращений к системным вызовам. Соответственно, между окончаниемфизического считывания первого блока и началом физического считывания второго блокапотратится некоторое время Δt на накладные расходы (в частности, вход и выход из системноговызова). Это время хоть и мало, но за данный промежуток диск успеет повернуться на угол ω*Δt(где ω — скорость вращения диска). Если следующий второй блок расположен на дискенепосредственно за первым, то за время Δt головка пропустит начало второго блока, и когда будетпредпринята попытка физически прочесть второй блок, то придется ожидать полного оборотадиска, что является относительно протяженным промежутком времени. Чтобы избежать подобныхнакладных расходов, связанных с необходимостью ожидать полного оборота диска, необходиморасположить второй блок с некоторым отступом от первого. В этом и заключаетсятехнологическое размещение блоков на диске.194Поверхность жесткого дискаtreadblock1ωblock1readblock2block2ΔtРис.
117.4.2.4.2ω*ΔtСтратегия размещения последовательных блоков файлов.Внутренняя организация блоковРазмер блока в файловой системе FFS может варьироваться в достаточно широкомдиапазоне: предельный размер блока — 64 Кбайт. Как отмечалось выше, проблема выбораоптимального размера блока достаточно сложна: и крупные блоки, и малоразмерные имеют своиплюсы и минусы, и от администратора системы требуются хорошие навыки, чтобы подобратьоптимальные для данной системы, решающей задачи конкретного типа, размеры блоков файловойсистемы.Создатели рассматриваемой файловой системы пошли по пути увеличения размера блока.За счет этого 1) уменьшается фрагментация файла по диску и 2) уменьшаются накладные расходыпри чтении подряд идущих данных файла (эффективнее считать за 1 раз большую порциюинформации, чем два раза считать по «половинке»). Но главным недостатком крупных блоков —большая степень внутренней фрагментации. Для борьбы с внутренней фрагментацией в системереализован еще один уровень структурной организации: каждый блок файловой системы поделенна фиксированное количество т.н.
фрагментов (обычно число фрагментов в блоке кратно степени2 — 2, 4, 8 и т.д.).Размещение файла по блокам файловой системы строится на основе следующей концепции(4.2.4.2). Начиная с первого и заканчивая предпоследним, эти блоки целиком заполненысодержимым данного файла. Соответственно, номера этих блоков хранятся среди атрибутовфайла. Последний блок выделен отдельно: помимо его номера в атрибутах файла хранятся иномера занятых в нем фрагментов, принадлежащих данному файлу. Информация о блоках ифрагментах могла быть представлена разными способами: например, двоичная маска, или женомер первого фрагмента в этом блоке, занятым данным файлом (количество фрагментов тогдаможно вычислить на основании длины файла в байтах), и т.д.Блоки01…Фрагменты01234567…Маска00000111…Рис.
118.NВнутренняя организация блоков (блоки выровнены по кратности).1954.2.4.3Выделение пространства для файлаРассмотрим алгоритм выделения пространства для файлов на следующем примере. Будемсчитать, что блок файловой системы поделен на 4 фрагмента. Пускай в системе хранятся файлыpetya.txt и vasya.txt (4.2.4.3), для которых в соответствующих индексных дескрипторах хранитсяинформация об их размерах и номеров блоков, принадлежащих файлам, в виде стартовыхфрагментов.
Соответственно, файл petya.txt расположен в нулевом блоке (стартовый фрагмент №00), первом (стартовый фрагмент № 04) и второго блока (начинающегося с 08 фрагмента). Еслиучесть длину файла (5120 байт), то получается, что во втором блоке этот файл занимает 08 и 09фрагменты. Файл vasya.txt расположен в третьем блоке (стартовый фрагмент № 12), четвертом(стартовый фрагмент № 16) и втором (стартовый фрагмент № 10), при этом во втором блоке файлупринадлежит только 10 фрагмент (т.к.
размер файла 4608 байт). Итак, очевидно, что даннаясистема нарушает концепцию файловой системы ветви System V, в которой каждый блок могпринадлежать только одному файлу; в FFS последний блок можно разделять между различнымифайлами.Дескриптор petya.txtID РазмерФрагмент1512000 04 08Дескриптор vasya.txtID РазмерФрагмент2460812 16 10Блоки данных, разделённые на фрагменты0120001020304050607080910311121341415161751819202122232223увеличился размер файла petya.txtДескриптор petya.txtID РазмерФрагмент1563200 04 20Дескриптор vasya.txtID РазмерФрагмент2460812 16 10Блоки данных, разделённые на фрагменты0120001Рис. 119.0203040506070809103111213414151617518192021Выделение пространства для файла.Если, например, размер файла petya.txt увеличивается на столько, что конец файла непомещается в 08 и 09 фрагментах, то система начинает поиск блока с тремя подряд идущимисвободными фрагментами.
(Соответственно, если размер файл увеличивается на большуювеличину, то сначала для него отводятся полностью свободные блоки, в которых файл занимаетвсе фрагменты, а для размещения последних фрагментов ищется блок с соответствующим числомподряд идущих свободных фрагментов.) Когда система находит такой блок, то происходитперемещение последних фрагментов файла petya.txt в этот блок.4.2.4.4Структура каталога FFSКаталог файловой системы FFS позволяет использовать имена файлов, длиной до 255символов (4.2.4.4). Каталог состоит из записей переменной длины, состоящих из блоков, размеромв 4 байта.
Начальная запись содержит номер индексного дескриптора, размер записи (т.е. ссылкана последний элемент записи) и длина имени файла, после этого следует дополненное до196кратности в 4 байта имя файла (максимальная длина имени файла — 255 символов). Работасистемы организована следующим образом: если происходит удаление файла из каталога, тоосвобождающееся пространство, занимаемое раньше записью данного файла, присоединяется кпредыдущей записи.
Это означает, что размер предыдущей записи увеличивается, но длинахранимого в ней имени не меняется (т.е. остается реальной). Удаление первой записи выражаетсяв обнулении номера индексного дескриптора в этой записи. Такая модель позволяет при удалениифайла практически не заботиться о высвобождаемом пространстве внутри файла-каталога:получаемые при удалении «дыры» ликвидируются не счет той же компрессии, а за счеттривиального «склеивания» с предыдущей записью.Каталогномер индексногодескриптораразмер записидлина имени файлаимя файла(до 255 символов)Рис. 120.Name1Name2Name3Name4Name5Size(Name1)Name1Name3RM Name2RM Name4…Size(Name1)Size(Name3)Name5…Структура каталога FFS BSD.Таким образом, система позволяет использовать имена файлов произвольной длины вплотьдо 255 символов, что достаточно удобно для пользователя.
Но такое преимущество оборачиваетсятем, что система несет накладные расходы как по использованию дискового пространства (вкаталогах присутствует внутренняя фрагментация), так и по времени (осуществление поиска всистемах с фиксированными размерами записей в большинстве случаев эффективнее, чем всистемах с переменными размерами записей).4.2.4.5Блокировка доступа к содержимому файлаОрганизация файловой системы ОС Unix позволяет открывать и работать с одним и тем жефайлом произвольному числу процессов. Более того, один и тот же файл может быть многократнооткрыт в рамках одного процесса.
При этом система поддерживает модель синхронизации работыс файлами. Для этого используется системный вызов fcntl() (данный системный вызовпредназначен вообще для организации управления работы с файлом), который можетобеспечивать блокировку как файла в целом, так и отдельных областей внутри файла (т.е. сделатькакую-то область файла недоступной для других процессов).
Различают два типа блокировок:исключающие и распределенные.Исключающая блокировка (exclusive lock) — это «жесткая» блокировка: если произошлатакая блокировка области, то любой другой процесс не сможет осуществить операции обмена сданной областью (в этом случае процесс будет либо приостановлен в ожидании разблокированияобласти, либо получит отказ в зависимости от установленного режима работы). Данный видблокировок является блокировкой с монополизацией, области с исключающими блокировкамипересекаться не могут.Альтернативой исключающей блокировке является распределенная блокировка (sharedlock), или «мягкая», рекомендательная блокировка.
Процесс может установить для областиблокировку этого типа, а другие процессы при работе могут на нее не обращать внимания, т.е. приустановленной блокировке все равно разрешены чтение и запись информации из блокированнойобласти. Для обеспечения корректной работы с файлом необходимо средство определенияустановки блокировки на той или иной области, для этого опять-таки используется системныйвызов fcntl(). Области с рекомендательными блокировками могут пересекаться.1975Управление оперативной памятьюБудем говорить о функциях управления оперативной памятью в контексте решенияследующих основных задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
