Единое окно доступа к образовательным ресурсам

Операционные системы. Теория и практика: Учебное пособие

Голосов: 2

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
         На каждой стороне каждой пластины размечены тонкие концентри-
ческие кольца – дорожки (англ. traks), на которых хранятся данные. Ко-
личество дорожек зависит от типа диска. Нумерация дорожек начинает-
ся с 0 от внешнего края к центру диска. Когда диск вращается, элемент,
называемый головкой, считывает двоичные данные с магнитной дорож-
ки или записывает их на нее.
     Головка может позиционироваться над заданной дорожкой. Голов-
ки перемещаются над поверхностью диска дискретными шагами, каж-
дый шаг соответствует сдвигу на одну дорожку. Запись на диск осу-
ществляется благодаря способности головки изменять магнитные свой-
ства дорожки. В некоторых дисках вдоль каждой поверхности переме-
щается одна головка, а в других – имеется по головке на каждую дорож-
ку. В первом случае для поиска информации головка должна переме-
щаться по радиусу диска. Обычно все головки закреплены на едином
перемещающем механизме и двигаются синхронно. Поэтому, когда го-
ловка фиксируется на заданной дорожке одной поверхности, все осталь-
ные головки останавливаются над дорожками с такими же номерами. В
тех же случаях, когда на каждой дорожке имеется отдельная головка,
никакого перемещения головок с одной дорожки на другую не требует-
ся, за счет этого экономится время, затрачиваемое на поиск данных.
     Совокупность дорожек одного радиуса на всех поверхностях всех
пластин пакета называется цилиндром (англ. cylinder). Каждая дорожка
разбивается на фрагменты, называемые секторами (англ. sectors) или
блоками (англ. blocks). На первых жестких дисках все дорожки имели
равное число секторов, в которые можно максимально записать одно и
то же число байт. Сектор имел фиксированный для конкретной системы
размер, выражающийся степенью двойки. Учитывая, что дорожки раз-
ного радиуса имели одинаковое число секторов, плотность записи ста-
новилась тем выше, чем ближе дорожка к центру. Однако, современные
жесткие диски имеют постоянную плотность записи, поэтому на разных
дорожках располагается различное количество секторов.
     Сектор – наименьшая адресуемая единица обмена данными диско-
вого устройства с ОП. Для того чтобы контроллер мог найти на диске
нужный сектор, необходимо задать ему все составляющие адреса секто-
ра: номер цилиндра, номер поверхности и номер сектора. В связи с тем,
что прикладной программе в общем случае нужен не сектор, а некото-
рое количество байт, не обязательно кратное размеру сектора, то типич-
ный запрос включает чтение нескольких секторов, содержащих требуе-
мую информацию, и одного или двух секторов, содержащих наряду с
требуемыми избыточные данные (рис. 35).
     Операционная система при работе с диском использует, как прави-
ло, собственную единицу дискового пространства, называемую класте-
                                 121


ром. При создании файла место на диске ему выделяется кластерами.
Например, если файл имеет размер 2560 байт, а размер кластера в фай-
ловой системе определен в 1024 байта, то файлу будет выделено на дис-
ке 3 кластера.




        Избыточные данные

                                          Требуемые данные
    Рисунок 35 – Считывание избыточных данных при обмене с диском
     Дорожки и секторы создаются в результате выполнения процедуры
физического, или низкоуровневого форматирования диска, предше-
ствующей использованию диска. Для определения границ блоков на
диск записывается идентификационная информация. Низкоуровневый
формат диска не зависит от типа ОС, которая этот диск будет использо-
вать.
     Разметку диска под конкретный тип файловой системы выполняют
процедуры высокоуровневого, или логического, форматирования. При
высокоуровневом форматировании определяется размер кластера и на
диск записывается информация, необходимая для работы файловой си-
стемы, в том числе информация о доступном и неиспользуемом про-
странстве, о границах областей, отведенных под файлы и каталоги, ин-
формация о поврежденных областях.
     Жесткий диск может содержать до четырех основных разделов. Это
ограничение связано с характером организации данных на жестких дис-
ках IBM-совместимых компьютеров.
     В первом физическом секторе жесткого диска располагается голов-
ная запись загрузки и таблица разделов (табл. 1).
     Головная запись загрузки (англ. master boot record, MBR) – первая
часть данных на жестком диске. Она зарезервирована для программы
начальной загрузки BIOS (ROM Bootstrap routine), которая при загрузке
                                 122


с жесткого диска считывает и загружает в память первый физический
сектор на активном разделе диска, называемый загрузочным сектором
(англ. Boot Sector). Программа, расположенная в MBR, носит название вне-
системного загрузчика (Non-System Bootstrap, NSB).
     Каждая запись в таблице разделов (англ. partition table) содержит
начальную позицию и размер раздела на жестком диске, а также инфор-
мацию о том, первый сектор какого раздела содержит загрузочный сек-
тор.
                            Таблица 1. Структура таблицы разделов
         Размер (байт)                    Описание
              446                 Загрузочная запись (MBR)
              16                        Запись 1 раздела
              16                        Запись 2 раздела
              16                        Запись 3 раздела
              16                        Запись 4 раздела
               2                        Сигнатура 055AAh

     Можно сказать, что таблица разделов – одна из наиболее важных
структур данных на жестком диске. Если эта таблица повреждена, то не
только не будет загружаться ни одна из установленных на компьютере
ОС, но станут недоступными данные, расположенные в диске, особенно
если жесткий диск был разбит на несколько разделов.
     Последние два байта таблицы разделов имеют значение 055AAh, то
есть чередующиеся значения 0 и 1 в двоичном представлении данных.
Эта сигнатура выбрана для того, чтобы проверить работоспособность
всех линий передачи данных. Значение 055AAh, присвоенное последним
двум байтам, имеется во всех загрузочных секторах.
     Многие ОС позволяют создавать, так называемый, расширенный
(англ. extended) раздел, который по аналогии с разделами может разби-
ваться на несколько логических дисков (англ. logical disks). В этом
смысле термин «первичный» можно признать не совсем удачным пере-
водом слова «primary» – лучше было бы перевести «простейший», или
«примитивный». В этом случае становится понятным и логичным
термин «расширенный». Расширенный раздел содержит вторичную
запись MBR (англ. Secondary MBR, SMBR), в состав которой вместо
таблицы разделов входит аналогичная ей таблица логических дисков
(англ. Logical Disks Table, LDT). Таблица логических дисков описыва-
ет размещение и характеристики раздела, содержащего единственный
логический диск, а также может специфицировать следующую запись

                                  123


SMBR. Следовательно, если в расширенном разделе создано K логи-
ческих дисков, то он содержит K экземпляров SMBR, связанных в спи-
сок. Каждый элемент этого списка описывает соответствующий логи-
ческий диск и ссылается (кроме последнего) на следующий элемент
списка. Загрузчик NSB служит для поиска с помощью таблицы разде-
лов активного раздела, затем копирования в ОП компьютера систем-
ного загрузчика (англ. System Bootstrap, SB) из выбранного раздела и
передачи на него управления, что позволяет осуществить загрузку
ОС.
     Вслед за сектором MBR размещаются собственно сами разделы
(рис. 36). В процессе начальной загрузки сектора MBR, содержащего
таблицу разделов, работают программные модули BIOS. Начальная
загрузка считается выполненной корректно только в том случае, если
таблица разделов содержит допустимую информацию.
   Первичный раздел
                                                Master Boot Record
  Расширенный раздел
    Не использован                       Загрузочный сектор диска С:
    Не использован                                                       Первичный
                                                                         раздел DOS
    Главная таблица                                                       (диск С:)
        разделов
                                               Secondary Master Boot
                                                      Record
  Логический диск D:
                                         Загрузочный сектор диска D:
    Адрес таблицы
     для диска E:
    Не использован
                                                                         Расширенный
    Не использован                                                         раздел DOS
                                               Secondary Master Boot     с логическими
    Первая таблица                                    Record            дисками D: и E:
   логического диска
                                          Загрузочный сектор диска E:
  Логический диск E:
   0 – конец цепочки
    Не использован
    Не использован                        Нераспределенное дисковое
                                                пространство
    Вторая таб лица
   логического диска
                       Рисунок 36 – Разбиение диска на разделы

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

                                         124


внешней памяти и предоставить пользователю возможности для запо-
минания и выборки данных в ней.
    Для организации хранения информации на диске пользователь вна-
чале обычно выполняет его форматирование, выделяя на нем место для
структур данных, которые описывают состояние файловой системы в
целом. Затем создает нужную ему структуру каталогов (директорий),
которые по существу являются списками вложенных каталогов и соб-
ственно файлов. И, наконец, заполняет дисковое пространство файлами,
приписывая их тому или иному каталогу. Таким образом, ОС должна
предоставить в распоряжение пользователя совокупность сервисов, тра-
диционно реализованных через системные вызовы, которые обеспечи-
вают:
     создание файловой системы на диске;
     необходимые операции для работы с каталогами;
     необходимые операции для работы с файлами.
    Кроме того, файловые службы могут решать проблемы проверки и
сохранения целостности файловой системы, проблемы повышения про-
изводительности и ряд других.
    Прежде чем приступить к описанию работы отдельных файловых
операций, необходимо рассмотреть ключевые алгоритмы и структуры
данных, которые обеспечивают функционирование файловой системы.
    5.2.2   Функциональная схема организации файловой системы
    Система хранения данных на дисках может быть представлена в
виде функциональной схемы (рис. 37). Рассмотрим ее подробнее.
    Нижний уровень – оборудование. Это в первую очередь, магнит-
ные диски с подвижными головками, особенности физической органи-
зации которых рассмотрены в п. 5.1.
    Непосредственно с устройствами (дисками) взаимодействует часть
ОС, называемая системой ввода-вывода. Система ввода-вывода (она
состоит из драйверов устройств и обработчиков прерываний для пере-
дачи информации между памятью и дисковой системой) предоставляет
в распоряжение более высокоуровневого компонента ОС – файловой
системы используемое дисковое пространство в виде непрерывной по-
следовательности блоков фиксированного размера. Система ввода-
вывода имеет дело с физическими блоками диска, которые характери-
зуются адресом – номерами диска, цилиндра и сектора. Файловая си-
стема имеет дело с логическими блоками, каждый из которых имеет но-
мер (от 0 или 1 до N). Размер этих логических блоков файла совпадает
или кратен размеру физического блока диска и может быть задан рав-
ным размеру страницы виртуальной памяти, поддерживаемой аппарату-
рой компьютера совместно с ОС.
                                125


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



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




        Базисная подсистема управления файлами
 Алгоритмы выделения блоков диска и соответствующие структуры
 данны х
 Менеджер свободного пространства
 Системные вызовы, работающие с дескриптором файлов
 Таблицы открыты х файлов, индексных узлов и др.
 Монтирование файловы х систем
 Реализация разделяемы х файлов



                         Кэширование блоков диска                                Процессы ОС




            Логические блоки (от 1 до N)
            Разделы диска, логические диски



                               Система ввода-вывода
                               Драйверы устройств, обработчики прерываний



                 Оборудование
                 Контроллер диска. Физические блоки диска
                 (сектора, цилиндры, треки)


     Рисунок 37 – Функциональная схема организации файловой системы
    Информация на диске организована в виде иерархической древо-
видной структуры, состоящей из набора файлов, каждый из которых яв-

                                              126


ляется хранилищем данных пользователя, и каталогов или директорий,
которые необходимы для хранения информации о файлах системы.
     Взаимодействие прикладной программы с файлом происходит сле-
дующим образом. От прикладной программы к логической подсистеме
поступает запрос на открытие или создание файла. Логическая подси-
стема, используя структуру директорий, проверяет права доступа и вы-
зывает базовую подсистему для получения доступа к блокам файла. По-
сле этого файл считается открытым, содержится в таблице открытых
файлов, прикладная программа получает в свое распоряжение дескрип-
тор (в системах Microsoft – handle) этого файла. Дескриптор файла яв-
ляется ссылкой на файл в таблице открытых файлов и используется в
запросах прикладной программы на чтение-запись из этого файла. За-
пись в таблице открытых файлов указывает через систему кэширования
блоков диска на блоки данного файла. Если к моменту открытия файл
уже используется другим процессом, то есть содержится в таблице от-
крытых файлов, то после проверки прав доступа к файлу может быть
организован совместный доступ. При этом новому процессу также воз-
вращается дескриптор файла.
     Прежде чем рассмотреть структуру данных файловой системы на
диске следует рассмотреть алгоритмы выделения дискового простран-
ства и способы учета свободной и занятой дисковой памяти.
    5.2.3   Типовая структура файловой системы на диске
     Обзор способов работы с дисковым пространством дает общее
представление о совокупности служебных данных, необходимых для
описания файловой системы. Структуры данных типовой файловой си-
стемы, например Unix, на одном из разделов диска, может состоять из 4-
х основных частей (рис. 38).
    Суперблок     Структуры данных,   Массив индексных   Блоки диска данных
                    описывающие            узлов              файлов
                 свободное дисковое
                   пространство и
                свободные индексные
                        узлы
       Рисунок 38 – Пример структуры файловой системы на диске
    В начале раздела находится суперблок, содержащий общее описа-
ние файловой системы, например:
     тип файловой системы;
     размер файловой системы в блоках;
     размер массива индексных узлов;
     размер логического блока;
     и т.д.
                                      127


     В файловых системах современных ОС для повышения устойчиво-
сти поддерживается несколько копий суперблока. В некоторых версиях
ОС Unix суперблок включал также и структуры данных, управляющие
распределением дискового пространства, в результате чего суперблок
непрерывно подвергался модификации, что снижало надежность файло-
вой системы в целом. Выделение структур данных, описывающих дис-
ковое пространство, в отдельную часть является более правильным ре-
шением.
     Описанные структуры данных создаются на диске в результате его
форматирования специализированными утилитами ОС. Их наличие поз-
воляет обращаться к данным на диске как к файловой системе, а не как
к обычной последовательности блоков.
     Массив индексных узлов (англ. ilist) содержит список индексов,
соответствующих файлам данной файловой системы. Размер массива
индексных узлов определяется администратором при установке систе-
мы. Максимальное число файлов, которые могут быть созданы в файло-
вой системе, определяется числом доступных индексных узлов.
     В блоках данных хранятся реальные данные файлов. Размер логи-
ческого блока данных может задаваться при форматировании файловой
системы. Заполнение диска содержательной информацией предполагает
использование блоков хранения данных для файлов директорий и обыч-
ных файлов и имеет следствием модификацию массива индексных узлов
и данных, описывающих пространство диска. Отдельно взятый блок
данных может принадлежать одному и только одному файлу в файловой
системе.
    5.2.4   Способы выделения дискового пространства
    Ключевой вопрос реализации файловой системы – способ связыва-
ния файлов с блоками диска. В ОС используется несколько способов
выделения файлу дискового пространства, для каждого из которых све-
дения о локализации блоков данных файла можно извлечь из записи в
директории, соответствующей символьному имени файла.
    Выделение непрерывной последовательностью блоков. Про-
стейший способ – хранить каждый файл, как непрерывную последова-
тельность блоков диска. При непрерывном расположении файл харак-
теризуется адресом и длиной (в блоках). Файл, стартующий с блока b,
занимает затем блоки b + 1, b + 2, ... b + n – 1. Этот способ имеет два
преимущества:
     легкая реализация, так как выяснение местонахождения файла
сводится к вопросу, где находится первый блок;
     обеспечивает хорошую производительность, потому что целый
файл может быть считан за одну дисковую операцию.
                                  128


     Например, непрерывное выделение использовано в ОС IBM/CMS,
RSX-11 (для исполняемых файлов).
     Основная проблема, в связи с которой этот способ мало распро-
странен – трудности в поиске места для нового файла. В процессе экс-
плуатации диск представляет собой некоторую совокупность свобод-
ных и занятых фрагментов. Проблема непрерывного расположения мо-
жет рассматриваться как частный случай более общей проблемы выде-
ления n блоков из списка свободных фрагментов. Наиболее распро-
страненные стратегии решения этой проблемы – выбор первого подхо-
дящего по размеру блока (англ. first fit), наиболее подходящего, т.е. того,
при размещении в котором наиболее тесно (англ. best fit), и наименее
подходящего, т.е. выбирается наибольший блок (англ. worst fit).
     Способ характеризуется наличием существенной внешней фраг-
ментации (в большей или меньшей степени – в зависимости от размера
диска и среднего размера файла). Кроме того, непрерывное распределе-
ние внешней памяти не применимо до тех пор, пока не известен макси-
мальный размер файла. Иногда размер выходного файла оценить легко
(при копировании), но чаще – трудно. Если места не достаточно, то
пользовательская программа может быть приостановлена, предполагая
выделение дополнительного места для файла при последующем переза-
пуске. Некоторые ОС используют модифицированный вариант непре-
рывного выделения: «основные блоки файла» + «резервные блоки». Од-
нако с выделением блоков из резерва возникают те же проблемы, так
как возникает задача выделения непрерывной последовательности бло-
ков диска теперь уже из совокупности резервных блоков.
     Выделение связным списком. Метод распределения блоков в виде
связного списка решает основную проблему непрерывного выделения,
то есть устраняет внешнюю фрагментацию (рис. 39). Каждый файл –
связный список блоков диска. Запись в директории содержит указатель
на первый и последний блоки файла. Каждый блок содержит указатель
на следующий блок.
 Файл А                                                Файл В


   Блок 0        Блок 1     Блок 2          Блок 3         Блок 0   Блок 1   Блок 2

     4             7           2                12           6         3        11


                                     Адреса блоков диска

         Рисунок 39 – Хранение файлов в связных списках дисковых блоков
    Внешняя фрагментация для данного метода отсутствует. Любой
свободный блок может быть использован для удовлетворения запроса.
                                          129


Отметим, что нет необходимости декларировать размер файла в момент
создания и, поэтому, файл может неограниченно расти. Связное выделе-
ние имеет несколько существенных недостатков:
      при прямом доступе к файлу для поиска i-го блока нужно осу-
ществить несколько обращений к диску, последовательно считывая бло-
ки от 1 до i – 1, то есть выборка логически смежных записей, которые
занимают физически несмежные секторы, может требовать много вре-
мени;
      прямым следствием этого является низкая надежность – нали-
чие дефектного блока в списке приводит к потере информации в оста-
точной части файла и, потенциально, к потере дискового пространства
отведенного под этот файл;
      для указателя на следующий блок внутри блока нужно выделить
место размером, традиционно определяемым степенью двойки (многие
программы читают и записывают блоками по степеням двойки), кото-
рый перестает быть таковым, так как указатель отбирает несколько бай-
тов.
     В связи с вышеизложенным, метод связного списка обычно не ис-
пользуется в чистом виде.
     Распределение связным списком с использованием индекса.
Недостатки предыдущего способа могут быть устранены путем изъятия
указателя из каждого дискового блока и помещения его в индексную
таблицу в памяти, которая называется таблицей размещения файлов
(англ. file allocation table – FAT). Этой схемы придерживаются многие
ОС (MS-DOS, OS/2, MS Windows и др.).
     По-прежнему существенно, что запись в директории содержит
только ссылку на первый блок. Далее при помощи таблицы FAT можно
локализовать блоки файла независимо от его размера (значение равно
адресу следующего блока этого файла). В тех строках таблицы, которые
соответствуют последним блокам файлов, обычно записывается некото-
рое граничное значение, например EOF (рис. 40).
                           Номер
                           блоков
                           диска
                           1        0
                           2        10
                           3        11    Начало файла F2
                           4        0
                           5        EOF
                           6        2     Начало файла F1
                           7        EOF
                           8        0
                           9        0
                           10       7
                           11       5

 Рисунок 40 – Способ выделения памяти с использованием связного списка в
                                  ОП
                                      130



    
Яндекс цитирования Яндекс.Метрика