Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Организация дискового пространства. Управление внешней памятью


 

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

При работе с блоками фиксированного размера большое значение имеет размер блока. В некоторых системах (например, UNIX) размер блока может быть задан при форматировании. При небольшом размере блока каждый файл будет содержать много блоков. Так как чтение блока осуществляется с задержками на поиск и вращение головок, то файл будет читаться медленно. Большие блоки обеспечивают более высокую скорость обмена с диском, но вследствие внутренней фрагментации (каждый файл занимает целое число блоков и в среднем половина последнего блока пропадает) снижается процент полезного дискового пространства. Исследования, проведенные в области размера блоков файла, показали, что оптимальный размер блока составляет: 512 байт, 1 Кбайт, 2 Кбайта.

После выбора размера блока следует выбрать метод учета свободных и занятых блоков. В современных операционных системах наибольшее распространение получили два метода.

Метод 1: учет при помощи организации битового вектора (массива или бит карты, bit map, bit vector). Каждый блок представлен одним битом, принимающим значение 0 – занят или 1 – свободен. В оперативной памяти возможно хранение одного блока, если организовано обращение к диску за другим блоком, когда текущий блок переполняется. Выделяемые файлу блоки располагаются близко друг к другу, в результате чего для доступа к файлу затрачивается меньше времени на перемещение блока головок. Главное преимущество этого подхода – проста и эффективность при нахождении первого свободного блока или n последовательных блоков на диске. Метод используется в Apple Macintosh, многие компьютеры, например, семейств Intel и Motorola имеют инструкции манипулирования битами, которые могут быть использованы для этой цели. Данный метод эффективен, если битовый вектор помещается в памяти целиком, что возможно только для небольших дисков. Например, диск размером 4 Гбайт с блоками по 4 Кбайт нуждается в таблице размером 128 Кбайт для управления свободными блоками. Если битовый вектор становится большим, то для ускорения поиска в нем его разбивают на регионы и организуют структуры данных, содержащие сведения о количестве свободных блоков для каждого региона.



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

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

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

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

 
 

 

В самом общем случае права доступа могут быть описаны матрицей прав доступа, в которой столбцы соответствуют всем файлам системы, строки – всем пользователям, в ячейках указываются разрешенные операции (рис. 4.16.). В некоторых системах пользователи разделяются на отдельные категории. Для всех пользователей одной категории определяются единые права доступа. Например, в системе UNIX все пользователи подразделяются на три категории: владелец файла, член его группы и все остальные. Различают два основных подхода к определению прав доступа:

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

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

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

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

 
 

 

Функционирование файловой системы определяется многоуровневой моделью (рис. 4.17.), в которой каждый уровень предоставляет интерфейс (набор функций) вышележащему уровню, а для выполнения своей работы использует интерфейс (обращается с набором запросов) нижележащего уровня. Задачей первого уровня является определение по символьному имени файла его уникального имени. В файловых системах, в которых каждый файл может иметь только одно символьное имя (например, MS-DOS), этот уровень отсутствует, так как символьное имя, присвоенное файлу пользователем, является одновременно уникальным и может использоваться операционной системой. В других файловых системах, в которых один и тот же файл может иметь несколько символьных имен, просматривается цепочка каталогов для определения уникального имени файла. Например, в UNIX, уникальным именем файла является номер его индексного дескриптора.

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

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

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

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

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

 

<== предыдущая лекция | следующая лекция ==>
Реализация директорий. Совместно используемые файлы | Надежность файловой системы. Управление плохими блоками

Дата добавления: 2014-01-03; Просмотров: 1400; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.