Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

241

используется как контрольный. Размещение контрольного сектора

"скользящее", как показано на рисунке 7.5. Контрольный сектор содержит

результат операции XOR между содержимым секторов с тем же адресом

всех остальных дисков. При потере информации на одном из дисков эта

информация может быть восстановлена путем выполнения XOR между

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

Рисунок 7.5 Технология RAID 5

Промышленное применение в настоящее время имеют технологии

RAID 0, 1 и 5.

Резервное копирование и даже аппаратная избыточность позволяют

уменьшить потери, но не избежать их полностью. В предыдущей главе мы

упоминали о том, что все современные файловые системы используют

кеширование дискового ввода-вывода, а, следовательно, в них возникает

ситуация отложенной или ленивой записи (lazy write), когда данные, уже

записанные процессом в файл, на самом деле находятся в буферной

оперативной памяти. При сбое системы такие данные могут быть

потеряны. Наиболее опасно то, что отложенной записи подвергаются не

только данные, но и метаданные файловой системы: дескрипторы дисков и

файлов, каталоги и т.п. При потере изменений в метаданных

недоступными могут стать все данные на диске. Поэтому в тех ФС, к

целостности которых предъявляются высокие требования, ведется

протоколирование операций над метаданными – запись информации по

повторению или откату операции над метаданными в файл протокола (log)

242

или журнала (journal). При сбое системы восстановление или откат

операций производится по журналу. Поскольку журнал также

подвергается отложенной записи, периодически производится фиксация

контрольной точки – принудительная запись журнала на диск. При сбое

системы, таким образом, гарантируется восстановление до последней

контрольной точки.

Причиной нарушения целостности может являться одновременный

доступ к файлу двух и более процессов. Для предотвращения таких

нарушений ОС накладывает "замки" (lock) на файлы: замок разделяемого

доступа для файла, открытого для чтения, и замок монопольного доступа

для файла, открытого для записи. Замок может входить в дескриптор

открытого файла. Если новый замок конфликтует с замком, наложенным

ранее начавшейся операцией, то новая операция должна быть

заблокирована. Обычно ОС не поддерживает сложного управления

синхронизацией операций, ограничиваясь замками файлов. Наиболее часто

в ОС применяется так называемая двухфазная дисциплина, требующая,

чтобы замок на файл накладывался при его открытии и снимался при его

закрытии. Замыкаться могут не только файлы, но и целые диски или

каталоги или наоборот – отдельные записи или байты файла. Задача

обеспечения синхронизации является частным случаем задачи взаимного

исключения, подробно рассматриваемой в главе 8.

Большинство ОС обеспечивает только разделение доступа к каждому

отдельному файлу и восстановление целостности метаданных ФС,

перепоручая управление сложными транзакциями и целостностью

пользовательских данных промежуточному программному обеспечению –

менеджерам транзакций (IBM CICS, MS Transaction Server и др.) и

системам управления базами данных (Oracle, IBM DB2 и др.). В

распоряжении процессов должны быть средства API для формирования

структуры транзакций – системные вызовы или обращения к тому

243

программному пакету, в среде которого функционирует процесс.

Примером такого средства могут быть предложения языка SQL: COMMIT

(совершить) и ROLLBACK (откат).

7.9. Загружаемая файловая система

Задачи переносимости программного обеспечения, в том числе и

системного, и функционирования программных изделий в среде

распределенной обработки данных включают в себя требования к

обеспечению единого пользовательского интерфейса различных ФС.

Вытекающим отсюда следствием может быть совместное использование в

одной операционной среде томов данных, обслуживаемых различными

файловыми системами.

Иерархическая структура ФС дает возможность провести в иерархии

уровней некоторую разграничительную линию, выше которой будут

располагаться абстрактная ФС – структуры данных и алгоритмы, общие

для любых ФС, а ниже – конкретная ФС со специфическими структурами

и алгоритмами. Наиболее вероятно эта граница может проходить в базовой

ФС, связывающей логическое представление файла с его физическим

представлением. Такой подход был впервые применен в ОС Unix в связи с

концепцией сетевых файловых систем. Проведение разграничительной

линии на уровне базовой ФС вызывает расщепление дескриптора

открытого файла на две части. Первая часть имеет общий для всех файлов

формат и содержит общие для всех файлов поля, обработка которых не

зависит от конкретной ФС. Это могут быть поля типа файла, размера,

временные отметки и другие данные. Вторая часть – частный дескриптор –

для конкретной ФС. В ней содержится план размещения файла, сведения

об организации и т.д. Общая таблица томов в ядре указывает для каждого

244

тома тип конкретной ФС, управляющей этим томом. Для каждого типа

конкретной ФС ядро хранит таблицу операций – таблицу входных точек

процедур, выполняющих для данной ФС стандартные функции (open,

close, read и т.д.). При обращении к ФС абстрактная ФС, выполнив

общие операции, определяет том и тип конкретной ФС на этом томе,

выбирает соответствующую конкретной ФС таблицу входных точек и

вызывает требуемую процедуру для конкретной ФС.

В системах с многоуровневыми драйверами драйвер ФС является

одним из уровней, которые проходят данные на пути от процесса к

устройству. При этом драйвер ФС не зависит не только от верхнего уровня

– абстрактной ФС, но и от нижнего уровня – аппаратных драйверов.

Если конкретная ФС удовлетворяет спецификациям, диктуемым

общей ФС, то конкретная ФС может быть загружаемой – включаемой в

ядро при установке тома, управляемого конкретной ФС.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Поясните различие между виртуальным и физическим файлом.

2. Охарактеризуйте основные компоненты иерархической модели

файловой системы. Какие преимущества дает иерархическая модель?

3. В чем различие между байториентированными и

записеориентированными файлами? Назовите достоинства и недостатки

той и другой модели.

4. В чем отличие логической структуры каталогов в MD DOS –

Windows – OS/2 от структуры каталогов в Unix?

5. В чем достоинства и недостатки отделения дескриптора файла от

элемента каталога?

245

6. Какую информацию о файле должен содержать его дескриптор,

хранимый в файловой системе? Какую информацию должен содержать

дескриптор открытого файла?

7. В чем сходство и различие каталогов и файлов (на логическом и на

физическом уровнях)?

8. В чем сходство и различие алиасов и косвенных файлов?

9. Обязательно ли закрытие файла при завершении открывшего его

процесса? Обязательна ли запись данных файла на диск при закрытии

файла?

10. В чем отличие смежного размещения файлов в современных

файловых системах от смежного размещения файлов в старых файловых

системах?

11. Какими методами может быть обеспечено преимущественно

смежное размещение файла на внешней памяти?

12. В чем отличие целостности файловой системы от целостности

данных? Какую целостность, и какими методами обеспечивают

современные файловые системы?

Глава 8. Параллельное выполнение процессов

8.1. Постановка проблемы

Параллельными называются процессы, в которых "интервалы

времени выполнения перекрываются за счет использования разных

ресурсов одной и той же вычислительной системы или за счет

перераспределения одного и того же набора ресурсов."[8] При

рассмотрении параллельности мы несколько расширим (только в пределах

этой главы) понятие процесса: будем понимать под процессом любую

246

последовательность действий. Процесс у нас имеет строго

последовательную структуру, он выполняется операция за операцией,

команда за командой. Но в один и тот же момент времени в системе могут

выполняться несколько таких последовательностей. Такое расширение

понимания процесса позволит нам включить в рассмотрение и такие

последовательности действий, которые формально процессами не

являются: отдельные нити одного процесса, модули ядра ОС, обработчики

прерываний, процессы на внешних устройствах и т.д. С концептуальной

точки зрения не имеет значения, является ли одновременность выполнения

реальной (достигаемой за счет аппаратного распараллеливания) или

виртуальной (достигаемой за счет разделения времени), хотя это различие,

как мы увидим ниже, может сказываться на механизмах реализации.

Процессы, которые мы рассматриваем в этой главе, являются слабо

связанными. Это означает, что за исключением достаточно редких

моментов явной связи процессы выполняются независимо друг от друга.

Взаимная независимость процессов запрещает нам при решении задач

управления параллельным выполнением делать какие-либо предположения

о соотношении скоростей выполнения процессов. За счет

перераспределения ресурсов эти скорости вообще не могут считаться

постоянными. Единственным оправданным предположением в этом

отношении может быть предположение о наихудшем (наименее удобном

для нас) соотношении скоростей.

Поскольку параллельные процессы разделяют ресурсы

вычислительной системы, задачи управления параллельным выполнением

есть задачи управления ресурсами. Как и в случае монопольно

используемых ресурсов, методы решения этих задач составляют широкий

спектр от самых консервативных (требующих значительного снижения

уровня мультипрограммирования) до самых либеральных (допускающих

параллельное выполнение большого числа процессов).

247

Основной задачей управления параллельным выполнением является

задача взаимного исключения (mutual exclusion, сокращенно – mutex): два

процесса не могут выполнять одновременный доступ к разделяемым

ресурсам. Обратим внимание на то обстоятельство, что взаимное

исключение обеспечивается уже на аппаратном уровне. Если процессор

одновременно получает два запроса, то он выполняет их последовательно

по тем или иным правилам арбитража. Каждая процессорная команда

обладает свойством атомарности: она или выполняется полностью, или

вообще не выполняется. Так же атомарно каждое обращение к памяти.

Арбитражные свойства аппаратуры являются основой для построения

более сложных механизмов взаимного исключения.

Последовательность операций в процессе, которая выполняет такую

единицу работы (транзакцию) с разделяемым ресурсом, во время которой

никакой другой процесс не должен иметь доступа к этому ресурсу,

составляет критическую секцию. Чтобы процесс мог обеспечить

безопасность выполнения своей критической секции, в его распоряжении

должны быть средства ("скобки критической секции") которыми он эту

критическую секцию обозначит и защитит. Назовем эти скобки csBegin

и csEnd и посвятим дальнейшее рассмотрение взаимного исключения

механизмам реализации этих скобок. Для доказательства правильности

каждой реализации для нее необходимо показать следующее:

• в любой момент времени не более, чем один процесс может

находиться в своей критической секции;

• решение о том, какому процессу первому надлежит войти в

критическую секцию, не может откладываться до бесконечности;

• остановка процесса вне своей критической секции не влияет на

другие процессы.

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

выполнения процесса до наступления некоторого внешнего по отношению к

248

нему события – такая задача называется задачей синхронизации. Если

рассматривать события как ресурсы (потребляемые), то задача

синхронизации является частным случаем задачи взаимного исключения.

Как частный случай, она допускает частные решения.

Типичным примером задачи синхронизации является обеспечение

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

представлен на рисунке 8.1. Граф синхронизации задает порядок

выполнения действий. В программной реализации мы можем представлять

действия A, B, ..., I как отдельные процессы и выполнять явную

синхронизацию или использовать неявную синхронизацию, представляя в

виде процессов тройки ABC, DEF, GIH или ADG, BEH, CFI, и вводить

явные точки синхронизации внутри процессов.

Более сложные задачи синхронизации, такие как "читатели–

писатели" и "производители–потребители" мы рассмотрим отдельно ниже.

Рисунок 8.1 Пример графа синхронизации

8.2. Взаимное исключение запретом прерываний

Большинство компьютерных архитектур предусматривают в составе

своей системы команд команды запрета прерываний (иногда –

селективного запрета). В микропроцессорах Intel-Pentium, например,

такими командами являются CLI (запретить прерывания) и STI

(разрешить прерывания). Такие команды и могут составить "скобки

критической секции": запрет прерываний при входе в критическую секцию

249

и разрешение – при выходе из нее. Поскольку вытеснение процесса

возможно только по прерыванию, процесс, находящийся в критической

секции, не может быть прерван. Этот метод, однако, обладает большим

числом недостатков:

• пока процесс находится в критической секции, не могут быть обработаны

никакие внешние события, в том числе и события, требующие обработки в

реальном времени;

• исключаются не только конфликтующие критические секции,

которые могут обращаться к разделяемым данным, но и все

другие процессы вообще; дисциплина, таким образом, является

весьма консервативной;

• процесс, находящийся внутри критической секции, не может

перейти в ожидание (кроме занятого ожидания), так как механизм

ожидания обеспечивается прерываниями;

• программист должен быть весьма внимателен к тому, чтобы все

возможные варианты выхода из критической секции

обеспечивались разрешением прерываний;

• вложение критических секций невозможно;

• обеспечение критической секции запретом прерываний

базируется на аппаратной атомарности команд, оно неприменимо

в мультипроцессорных системах с реальной параллельностью, так

как программа, выполняющаяся на одном процессоре, не может

запретить прерывания другого процессора.

8.3. Взаимное исключение через общие переменные

Следующая группа решений базируется на непрерываемости памяти.

Представляя эти алгоритмы, мы в основном следуем первоисточнику [11]

250

и приводим в качестве примеров как правильные, так и неправильные или

неудачные варианты решений.

Почти все примеры мы даем для двух процессов с номерами 0 и 1, их

нетрудно обобщить на произвольное число процессов.

Вариант 1: общая переменная исключения.

Введем булевскую переменную mutEx, которая должна получать

значение true (1), если вхождение в критическую секцию запрещено, или

false (0), если вхождение разрешено. Попытка организовать "скобки

критической секции" представлена следующим программным кодом:

static char mutEx = 0;

void csBegin ( void ) {

while ( mutEx );

mutEx = 1;

}

void csEnd ( void ) {

mutEx = 0;

}

При вхождении в функцию csBegin процесс попадает в цикл

ожидания (строка 3), в котором находится до тех пор, пока состояние

переменной исключения не разрешит ему войти в критическую секцию.

Выйдя из этого цикла, процесс устанавливает эту переменную в 1,

запрещая тем самым другим процессам входить в их критические секции.

Процесс, который выполнялся в критической секции, при выходе из

последней сбрасывает переменную исключения в 0, разрешая этим другим

процессам входить в их критические секции.