1625914892-87304ba273974eff372da046ba2bc5da (843828), страница 4
Текст из файла (страница 4)
Минусом данной схемы может быть необходимость хранения в па мяти этой довольно большой таблицы.13) Как организуется хранение файлов методом «индексные узлы»?Наиболее распространенный метод выделения файлу блоков диска - связать с каждым файлом небольшую таблицу, называемую индексным узлом (i-node), которая перечисляет атрибутыи дисковые адреса блоков файла. Запись в директории, относящаяся к файлу, содержит адрес индексного блока. По мере заполнения файла указатели на блоки диска в индексном узле принимают осмысленные значения.Индексирование поддерживает прямой доступ к файлу, без ущерба от внешней фрагментации.
Индексированное размещение широко распространено и поддерживает как последовательный, так и прямой доступ к файлу.Обычно применяется комбинация одноуровневого и многоуровневых индексов. Первые несколько адресов блоков файла хранятся непосредственно в индексном узле, таким образом, длямаленьких файлов индексный узел хранит всю необходимую информацию об адресах блоковдиска. Для больших файлов один из адресов индексного узла указывает на блок косвенной адресации. Данный блок содержит адреса дополнительных блоков диска.
Если этого недостаточно,используется блок двойной косвенной адресации, который содержит адреса блоков косвеннойадресации. Если и этого не хватает, используется блок тройной косвенной адресации.Данную схему используют файловые системы Unix (а также файловые системы HPFS, NTFSи др.). Такой подход позволяет при фиксированном, относительно небольшом размере индексного узла поддерживать работу с файлами, размер которых может меняться от нескольких байтовдо нескольких гигабайтов. Существенно, что для маленьких файлов используется только прямаяадресация, обеспечивающая максимальную производительность.14) Методы управления свободным дисковым пространством «Битовый вектор», «Связныйсписок».Часто список свободных блоков диска реализован в виде битового вектора (bit map или bitvector).
Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимостиот того, занят он или свободен. Hапример, 00111100111100011000001 ... .Главное преимущество этого подхода состоит в том, что он относительно прост и эффективенпри нахождении первого свободного блока или n последовательных блоков на диске. Многиекомпьютеры имеют инструкции манипулирования битами, которые могут использоваться дляэтой цели. Hапример, компьютеры семейств Intel и Motorola имеют инструкции, при помощи которых можно легко локализовать первый единичный бит в слове.Другой подход - связать в список все свободные блоки, размещая указатель на первый свободный блок в специально отведенном месте диска, попутно кэшируя в памяти эту информацию.Подобная схема не всегда эффективна.
Для трассирования списка нужно выполнить много обращений к диску. Однако, к счастью, нам необходим, как правило, только первый свободныйблок.Иногда прибегают к модификации подхода связного списка, организуя хранение адресов n свободных блоков в первом свободном блоке. Первые n-1 этих блоков действительно используются.Последний блок содержит адреса других n блоков и т. д.15) Как реализуется представление директорий в файловых системах?Директория или каталог - это файл, имеющий вид таблицы и хранящий список входящих в негофайлов или каталогов.
Основная задача файлов-директорий - поддержка иерархической древовидной структуры файловой системы. Запись в директории имеет определенный для данной ОСформат, зачастую неизвестныйпользователю, поэтому блокиданных файла-директории заполняются не через операции записи,а при помощи специальных системных вызовов (например, создание файла).Для доступа к файлу ОС использует путь, сообщенный пользователем. Запись в директории связывает имя файла или имя поддиректории с блоками данных на диске. В зависимости от способавыделения файлу блоков диска эта ссылка может быть номером первого блока или номером индексного узла. В любом случае обеспечивается связь символьного имени файла с данными надиске.Когда система открывает файл, она ищет его имя в директории. Затем из записи в директорииили из структуры, на которую запись в директории указывает, извлекаются атрибуты и адресаблоков файла на диске.
Эта информация помещается в системную таблицу в главной памяти. Всепоследующие ссылки на данный файл используют эту информацию. Атрибуты файла можнохранить непосредственно в записи в директории, как показано на рисунке. Однако для организации совместного доступа к файлам удобнее хранить атрибуты в индексном узле, как это делаетсяв Unix.16) Как организовано хранение файлов в ОС MS-DOS.17) Как организовано хранение файлов в ОС Unix.Структура директории проста. Каждая запись содержит имя файла и номер его индексного узла.Вся остальная информация о файле (тип, размер, время модификации, владелец и т. д.
и номерадисковых блоков) находится в индексном узле.18) Описать процедуру монтирования файловых систем.Функция mount (монтировать) связывает файловую систему из указанного раздела на диске ссуществующей иерархией файловых систем. Функция mount, таким образом, дает пользователямвозможность обращаться к данным в дисковом разделе как к файловой системе, а не как к последовательности дисковых блоков.Процедура монтирования состоит в следующем.
Пользователь сообщает ОС имя устройства иместо в файловой структуре (имя пустого каталога), куда нужно присоединить файловую систему (точка монтирования). Затем ОС должна убедиться, что устройство содержит действительнуюфайловую систему ожидаемого формата с суперблоком, списком индексов и корневым индексом.19) Что такое жесткое связывание файлов (hard link)?Соединение между директорией и разделяемым файлом называется "связью" или "ссылкой"(link). Дерево файловой системы превращается в циклический граф.Это удобно, но создает ряд дополнительных проблем.Простейший способ реализовать связывание файла - просто дублировать информацию о нем вобеих директориях.
При этом, однако, может возникнуть проблема совместимости в случае, есливладельцы этих директорий попытаются независимо друг от друга изменить содержимое файла.Например, в ОС CP/M запись в директории о файле непосредственно содержит адреса дисковыхблоков. Поэтому копии тех же дисковых адресов должны быть сделаны и в другой директории,куда файл линкуется.
Если один из пользователей что-то добавляет к файлу, новые блоки будутперечислены только у него в директории и не будут "видны" другому пользователю.Проблема такого рода может быть решена двумя способами. Первый из них - так называемаяжесткая связь (hard link). Если блоки данных файла перечислены не в директории, а в небольшой структуре данных (например, в индексном узле), связанной собственно с файлом, то второйпользователь может связаться непосредственно с этой, уже существующей структурой.20) Что такое символическое связывание файлов (symbolic link)?Альтернативное решение - создание нового файла, который содержит путь к связываемомуфайлу.
Такой подход называется символической линковкой (soft или symbolic link). При этом всоответствующем каталоге создается элемент, в котором имени связи сопоставляется некотороеимя файла (этот файл даже не обязан существовать к моменту создания символической связи).Для символической связи может создаваться отдельный индексный узел и даже заводиться отдельный блок данных для хранения потенциально длинного имени файла.Каждый из этих методов имеет свои минусы. В случае жесткой связи возникает необходимость поддержки счетчика ссылок на файл для корректной реализации операции удаленияфайла.
Например, в Unix такой счетчик является одним из атрибутов, хранящихся в индексномузле. Удаление файла одним из пользователей уменьшает количество ссылок на файл на 1. Реальное удаление файла происходит, когда число ссылок на файл становится равным 0.В случае символической линковки такая проблема не возникает, так как только реальныйвладелец имеет ссылку на индексный узел файла. Если собственник удаляет файл, то он разрушается, и попытки других пользователей работать с ним закончатся провалом. Удаление символического линка на файл никак не влияет. Проблема организации символической связи - потенциальное снижение скорости доступа к файлу.
Файл символического линка хранит путь к файлу,содержащий список вложенных директорий, для прохождения по которому необходимо осуществить несколько обращений к диску.Символический линк имеет то преимущество, что он может использоваться для организацииудобного доступа к файлам удаленных компьютеров, если, например, добавить к пути сетевойадрес удаленной машины.21) Перечислить основные методы повышения надежности файловой системы. Своевременное дублирование информацииКонтроль целостности системыПорядок выполнения операцийЖурнализацияПроверка целостности файловой системы при помощи утилитУправление "плохими" блоками22) Перечислить основные методы повышения производительности файловой системы.Поскольку обращение к диску - операция относительно медленная, минимизация количества таких обращений – ключевая задача всех алгоритмов, работающих с внешней памятью. Кэширование разумной стратегии размещения информации дефрагментацию диска23) Описать алгоритм вытеснения из кэша SecondChance.Например, алгоритм Second-Chance - модификация алгоритма FIFO, которая позволяет избежатьпотери часто используемых страниц с помощью анализа флага обращений (бита ссылки) для самой старой страницы.
Если флаг установлен, то страница не выталкивается, а ее флаг сбрасывается, и страница переносится в конец очереди. Если первоначально флаги обращений были установлены для всех страниц (на все страницы ссылались), алгоритм Second-Chance превращается валгоритм FIFO.24) Описать алгоритм вытеснения из кэша LRU.Least Recently Used (LRU): в первую очередь,вытесняется неиспользованный дольше всех. Этоталгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольнонакладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться.Общая реализация этого метода требует сохранения "бита возраста" для строк кэша и за счетэтого происходит отслеживание наименее использованных строк (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
