|
Данные
В «суперблоке» содержатся ключевые параметры файловой
системы и считывается в память при загрузке компьютера или при первом обращении
к ФС. Информация, хранящаяся в суперблоке, включает число, позволяющее
различать системные файлы, количество блоков в ФС, а также ключевую
административную информацию. Его структуру можно увидеть в таблице 1.1.
Таблица 1.1
|
Название поля
|
Размер в байтах
|
Описание
|
|
fs_name
|
3
|
Название файловой системы
|
|
fs_size
|
2
|
Размер файловой системы
|
|
block_size
|
2
|
Размер блока данных
|
|
free_ block
_count
|
2
|
Количество свободных блоков
|
|
free_inode_count
|
2
|
Количество свободных i
-узлов
|
Следом располагается информация о свободных блоках
файловой системы в виде битового массива. Битовая карта представляет собой
массив, каждый элемент которого соответствует состоянию блока данных раздела.
Далее i-узлы, которые представляют собой массив
структур данных (по одной структуре на файл), содержащих всю информацию о
файлах.
В таблице 1.2 показана структура i-узла, с помощью
которых происходит размещение файлов на диске. Они содержатся в массиве i-узлов
и каждому файлу соответствует один элемент этого массива. I-узел содержит
информацию о файле, его атрибуты, но не содержит данных и имени файла.
Последнее, а также номер i-узла файла находятся в специальных файлах -
каталогах.
На логическом уровне каталог представляет собой
таблицу, каждый элемент которого имеет размер 16 байт. Первые 14 байта хранят
имя файла, последние 2 - его номер i-узла.
Данные о пользователях находятся в служебном файле,
который находится в корневом каталоге. Он представляет собой структуру из пяти
полей: первое - флаг: администратор или обычный пользователь (1 байт), второе -
идентификатор пользователя (1 байт), третье - индекс аватары пользователя (1
байт), четвертое - имя пользователя (14 байт), и пятое - хэш-значения пароля
(32 байт).
Таблица 1.2
|
Название поля
|
Размер в байтах
|
Описание
|
|
is_free
|
1
|
Состояние i -узла
|
|
f_size
|
2
|
Размер файла
|
|
rights
|
1
|
Права доступа к файлу
|
|
uid
|
1
|
Идентификатор владельца
|
|
is_dir
|
1
|
Флаг : файл или каталог
|
|
create_time
|
8
|
Время создания файла
|
|
last_mod_time
|
8
|
Время последней модификации
|
|
addr[1..10]
|
20
|
Указатели на блоки данных
файла
|
Права доступа к файлам представляются как целое число,
принимает значения от 0 до 5 в зависимости от установленных прав. Эта
зависимость представлена в таблице 1.3.
Таблица 1.3
|
Права
|
Значения числа
|
|
Для владельца файла
|
Для других пользователей
|
|
|
r
|
-
|
0
|
|
r
|
r
|
1
|
|
r
|
w
|
2
|
|
w
|
-
|
|
w
|
r
|
4
|
|
w
|
w
|
5
|
После i-узлов следует корневой каталог, содержащий
вершину дерева ФС. Остальное место дискового раздела занимают все остальные
файлы и каталоги.
Для определения того, какой блок какому файлу
принадлежит, в проектируемой операционной системе применяется метод
последовательных блоков.
Этот метод является простейшей схемой выделения файлам
определенных блоков на диске. Это система, в которой файлы представляют собой
непрерывные наборы соседних блоков диска. Тогда на диске, состоящем из блоков
по 1 Кбайт, файл размером в 50 Кбайт будет занимать 50 последовательных блоков.
Схематично он представлен на рисунке 1.2
Рисунок 1.2 - Метод последовательных блоков
Преимущества такого метода состоят в том, что его
легко реализовать, так как системе, чтобы определить какие блоки принадлежат
тому или иному файлу, нужно следить всего лишь за двумя числами: номером
первого блока файла и числом блоков в файле.
Производительность высока, так как весь файл может
быть прочитан с диска за одну операцию. Требуется только одна операция поиска
(для первого блока). После этого более не нужно искать цилиндры и тратить время
на ожидания вращения диска, поэтому данные могут считываться с максимальной
скоростью, на которую способен диск.
Недостаток: со временем диск становится
фрагментированным.
Создание иерархической организации данных является
решением проблемы одинаковых имен файлов, созданных различными пользователями.
При этом имена файлов, созданных одним пользователем, не конфликтуют с именами
файлов другого пользователя.
Благодаря многоуровневой иерархии исчезают конфликты
имен файлов между различными пользователями и ее достаточно для пользователей с
большим числом файлов. Возможность создавать произвольное количество
подкаталогов является мощным структурирующим инструментом, позволяющим
пользователям организовать свою работу. Схема многоуровневой иерархии
представлена на рисунке 1.3
Рисунок 1.3 - Структура многоуровневой ФС
Системные вызовы для работы с каталогами:
Create - создание каталога.
Delete - удаление каталога.
Opendir - открытие каталога.
Closedir - закрытие каталога.
Readdir - чтение следующего элемента
открытого каталога.
Rename - переименование каталога.
Link - установление связей.
Unlink - удаление ссылки на файл из
каталога.
Флаг «Только чтение»- 0 -для чтения/записи; 1- только
чтение
Флаг «Скрытый» - 0 - нормальный, 1 - не отображать в
перечне файлов каталога
Флаг «Системный»0 - нормальный; 1- системный
Флаг «Архивный»-0 - заархивирован; 1 - требуется
архивация
Флаг ASCII/двоичный -0 - ASCII; 1- двоичный
Флаг произвольного доступа -0 - только последовательный доступ; 1
- произвольный доступ
Флаг «временный»-0 - нормальный, 1- для удаления файла
по окончании процесса
Флаги блокировки-0 - неблокированный; отличный от
нуля для блокированного
1.2 Виртуальные страницы
Учитывая, что проектируемая операционная система
мультипрограммная, позволяющая реализовать выполнение нескольких программ
одновременно, исключительную важность приобретает вопрос организации обмена
информацией между внешней и оперативной памятью. В системах с распределением
оперативной памяти в последней может находиться одновременно несколько целевых
программ или их частей. При этом не надо производить обмен каждый раз, когда
обработка целевой программы заканчивается, так как другие целевые программы или
их части уже находятся в памяти и готовы к обработке.
Распределением памяти называется процесс размещения
информации (блоков данных или команд) в запоминающем устройстве различных
уровней для наиболее эффективного использования всей ёмкости памяти,
рациональной организации вычислительного процесса и сокращения времени решения
задачи. При работе в режиме мультипрограммирования статическое распределение
памяти оказывается практически нереализуемым, так как программист не может
заранее предусмотреть всех возможных ситуаций, возникающих при решении
одновременно нескольких задач. Поэтому распределение памяти должно выполняться
в самой ЭВМ автоматически в процессе исполнения программ. Такой метод
называется динамическим распределением памяти. При этом во избежание случайного
вторжения программой одной задачи в области памяти, занятые информацией,
относящейся к другой задаче, предусматривается защита памяти, благодаря которой
при попытке обращения к запрещенным блокам памяти происходит автоматическое
прерывание программы. При динамическом распределении памяти внутренний обмен
информацией между оперативной и внешней памятью удаётся организовать так, что
пользователь (программист) как бы имеет в своём распоряжении одну оперативную
память очень большой ёмкости, ограниченной только разрядностью адреса в
команде. На самом деле эта память - виртуальная (кажущаяся), так как в любой
данный момент времени только небольшая часть информации, содержащейся в
виртуальной памяти, физически находится в оперативном запоминающем устройстве.
Одной из схем адресации памяти компьютера, при которой
память запущенной программы реализуется однородным массивом, в то время как в
действительности операционная система выделяет память блоками в различных видах
памяти, включая кратковременную (оперативную) и долговременную (жесткие диски,
твердотельные накопители) является виртуальная память.
Внутри операционной системы обычно отводится пул
свободной памяти, предназначенный для текущих нужд различных системных
процессов. Этот пул поддерживает временные системные буферы, очереди и блоки
управления процессами. Так как операционная система обычно работает с реальными
адресами, этот пул представляет собой непрерывный сегмент, динамически
распределяемый между различными системными процессами.
Концепция динамического распределения памяти состоит в
выборе соответствующей стратегии размещения. Распределение представляет собой
принятие решения о том, в каком месте памяти должна располагаться программа,
чтобы минимизировать неиспользуемое адресное пространство и гарантировать
одновременное размещение в памяти заданного числа пользователей. Разумеется,
чем больше задач, «готовых выполняться», будет размещено в памяти, тем больше
вероятность наиболее эффективного использования системных ресурсов.
Определяя стратегию размещения, мы рассматриваем
память как упорядоченное пространство из m слов. Запросы на размещение или
освобождение блоков памяти будут постоянно стремиться нарушить эту
упорядоченность. В этом случае конфигурация памяти будет напоминать шахматную
доску с пустыми участками, чередующимися с распределенными блоками. Такая конфигурация
меняется во времени в зависимости от объемов памяти, указываемых в запросах.
Эффективное распределение памяти предполагает минимизацию размера и количества
пустых участков памяти.
Для стратегий размещений выработано правило «Правило
50%». Оно предполагает, что система находится в равновесии, если запросы на
распределение и освобождение сбалансированы между собой в течение заданного
короткого промежутка времени. Иначе говоря, в системе из m слов с
распределенными n сегментами будет
примерно h пустых участков, где h равно n /2. Это следует из того факта, что
для данного сегмента пространство, примыкающее к его правому краю, будет пустим
в течение половины данного интервала времени и занятым сегментом в течение
другой половины. Вероятность существования пустого участка есть р = 1/2;
например, число сегментов, имеющих пустоту по своему правому краю, есть np =
n/2 = h.
Результат применения этого правила вполне очевиден.
Для сокращения времени работы алгоритма размещения мы должны сознательно
смириться с присутствием в памяти пустых участков большой величины. Это
увеличивает объем неиспользуемой памяти. Однако было рассчитано, что при
сильном варьировании размеров пустых участков доля объем неиспользуемой памяти
может быть уменьшена до 10%.
a) Алгоритм оптимального размещения.
Этот алгоритм пытается удовлетворить запрос, выделяя
свободный участок минимально возможного размера. Создается и поддерживается
список свободных участков, упорядоченный по их размерам. Менеджер памяти при
получении запроса на свободное пространство просматривает список, подыскивая
участок с минимальной величиной ОСТАТОК, вычисляемой следующим образом:
РАЗМЕР-УЧАСТКА - ТРЕБУЕМЬІЙ-РАЗМЕР -* ОСТАТОК
Здесь ОСТАТОК - это свободное пространство, остающееся
после удовлетворения запроса. Идея алгоритма - минимизировать объем свободного
пространства, остающегося после каждого распределения. В системах,
осуществляющих деление свободных участков на части, ОСТАТОК сравнивается с
некоторой пороговой величиной для принятия решения: производить такое
разделение или нет.
б)
Похожие работы на - Проектирование гипотетической операционной системы
|