close

Вход

Забыли?

вход по аккаунту

?

Kychin

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Н. В. Кучин, А. Ю. Молчанов
ОСНОВЫ ОРГАНИЗАЦИИ
МУЛЬТИПРОГРАММНЫХ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Учебное пособие
Санкт-Петербург
2017
УДК 004.451
ББК 32.97 - 018.2
К88
Рецензенты:
доктор технических наук, профессор В. А. Шпенст;
кандидат технических наук, доцент С. А. Якушенко
Утверждено
редакционно-издательским советом университета
в качестве текста лекций
Кучин, Н. В,
К88 Основы организации мультипрограммных вычислительных систем: учеб. пособие / Н. В. Кучин, А. Ю. Молчанов.
СПб.: ГУАП, 2017. – 103 с.
ISBN 978-5-8088-1177-5
Содержатся сведения по организации мультипрограммных вычислительных систем. Показывается, что мультипрограммный режим
работы возможен на основе использования операционных систем, обеспечивающих выполнение множества параллельных вычислительных
процессов. Рассматриваются вопросы назначения отдельных компонентов операционных систем, их архитектура и возможные варианты
реализации. Значительное внимание уделено рассмотрению вопросов,
характерных для мультипрограммных вычислительных систем – синхронизации параллельных процессов, методам борьбы с тупиковыми
ситуациями и средствам аппаратной поддержки функционирования
операционных систем.
Учебное пособие предназначено для студентов, обучающихся по направлению «Информатика и вычислительная техника».
УДК 004.451
ББК 32.97 - 018.2
ISBN 978-5-8088-1177-5
©
©
Кучин Н. В, Молчанов А. Ю., 2017
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2017
1. ОСНОВНЫЕ ПОНЯТИЯ И АРХИТЕКТУРА
ОПЕРАЦИОННЫХ СИСТЕМ
1.1. Обзор развития операционных систем
Операционные системы (ОС), как основной и необходимый компонент программного обеспечения современных вычислительных
систем, появились значительно позднее первых компьютеров. Их
необходимость была определена в процессе развития и эволюции
вычислительной техники. Кратко рассмотрим этот процесс, начиная с первых вычислительных систем.
Системы, ориентированные на использование перфокарт. Пользователь ЭВМ, используя специальное устройство, готовил свою задачу в виде колоды перфокарт, на которой размещал код программы и
исходные данные к ней. Затем, в отведенное для него время, используя устройство считывания с перфокарт и пульт управления, вводил
код программы в оперативную память (ОП) ЭВМ и запускал задачу
на выполнение. Далее, манипулируя клавишами пульта управления, останавливал и перезапускал свою программу по мере надобности. После получения результатов пользователь покидал машинный
зал. Такая схема работы на ЭВМ имела следующие свойства:
– в каждый момент рабочего времени ЭВМ использовалась для
выполнения только одной пользовательской (прикладной) программы, т. е. реализовывался однопрограммный режим работы;
– управление вычислениями осуществлялось вручную, т. е. отсутствовала автоматизация управления;
– пропускная способность вычислительной системы была крайне низкой.
Пропускная способность вычислительной системы определяется количеством выполненых задач в единицу времени. Низкая пропускная
способность таких систем связана с тем, что значительная часть общего
времени решения задачи тратилась на выполнение операций ввода / вывода, а процессор, как основной ресурс вычислительной системы, в это
время простаивал и не выполнял никакой полезной работы. Поэтому
для повышения эффективности использования вычислительных систем
необходимо было сократить время, которое тратилось на ввод / вывод.
Системы, ориентированные на магнитные ленты (МЛ). Пользователь перед выходом на ЭВМ переносил свои данные и код программы на МЛ. Вычислительная система снабжалась накопителями
на магнитной ленте (НМЛ), которые представляли устройства ввода-вывода с более высоким быстродействием. Схема работы в таких
3
системах мало отличалась от систем с перфокартами. Разница заключалась лишь в том, что информация считывалась в оперативную
память ЭВМ и записывалась из нее с большей скоростью. Как и раньше, реализовывался однопрограммный режим работы, а управление
вычислениями осуществлялось вручную. Пропускная способность
системы оставалась низкой, хотя и несколько выше, чем в системах
с перфокартами. Следующим этапом развития вычислительных систем стали системы пакетной обработки данных.
Системы пакетной обработки данных. Оператор создавал пакет
заданий, последовательно записывая их на МЛ. Задания отделялись
друг от друга специальными маркерами. После составления пакета и
установки его на НМЛ оператор, используя пульт управления, запускал пакет на выполнение. Для того чтобы пакет заданий мог последовательно выполняться на ЭВМ, в ее памяти должна храниться специальная программа – монитор пакетной обработки. Такой монитор
отслеживал момент окончания выполнения очередного задания и загружал в ОП следующее задание. Кроме того, монитор фиксировал
время выполнения каждого задания и реагировал на ряд нештатных
ситуаций (попытка деления на ноль, зацикливание и т. п.). По своему назначению монитор пакетной обработки являлся управляющей
программой, а по способу реализации – системной. Можно сказать,
что такой монитор являлся простейшей ОП.
Характерной особенностью систем пакетной обработки является
автоматизация управления вычислениями (функционирование монитора). Но эффективность работы оставалось весьма низкой из-за
однопрограммного режима выполнения задач и значительных простоев процессора. Очевидно, для того чтобы повысить эффективность функционирования вычислительной системы, необходимо
минимизировать простои процессора. Поэтому следующим этапом
стал этап создания мультипрограммных вычислительных систем.
Именно на этом этапе появились полноценные ОП.
Мультипрограммные вычислительные системы. Для минимизации простоев процессора необходимо выполнить три условия:
– необходим механизм разделения процессора (процессорного времени) между выполняемыми программами;
– в ОП необходимо одновременно хранить коды нескольких программ;
– необходимо обеспечить одновременную работу устройств ввода-вывода и центрального процессора.
Реализация этих условий значительно усложнила вычислительные системы. Если говорить об аппаратной части (hardware), то в со4
ставе компьютеров появились специальные устройства – каналы
(контроллеры, микроконтроллеры). Эти устройства предназначены
для управления обменом между ОП и соответствующими устройствами ввода-вывода. Они могут функционировать определенное время независимо и асинхронно относительно центрального процессора,
что способствует выполнению третьего условия. Но для обеспечения всех трех условий, определяющих мультипрограммный режим
работы вычислительной системы, изменений в аппаратной части
было недостаточно. Необходимо было создать комплекс системных
программных средств, которые бы распределяли процессор между
пользовательскими программами (диспетчер задач), выделяли бы
области памяти для хранения кодов нескольких программ одновременно (планировщик памяти ), осуществляли планирование операций ввода-вывода (супервизор ввода-вывода), координировали бы параллельную работу различных устройств из состава системы (механизм прерываний) и т. д. Кроме того, на данном этапе эволюции вычислительных систем очень важным требованием стало требование
минимизации возможности непосредственного доступа к ресурсам
вычислительной системы со стороны пользовательских программ и
пользователей. Реализация такого требования значительно повышает надежность функционирования вычислительной системы. Другими словами системные программы должны обеспечивать интерфейс
между пользовательскими программами с одной стороны и аппаратурой – с другой. Комплекс системных программных средств, позволяющий обеспечивать указанные требования, составляет основу
современных ОС. С появлением локальных и глобальных вычислительных сетей появились сетевые ОС.
Вычислительные системы на основе сетей. Сетевые ОС отличаются от ОС для локальных компьютеров тем, что в их составе существуют механизмы, обеспечивающие доступ к удаленным (сетевым) ресурсам. Сетевую ОС можно представить как совокупность
служб, каждая из которых позволяет выполнять определенный
набор функций с конкретным типом ресурса (файловая служба, почтовая служба и т. д. ). Каждая служба разделяется на клиентскую
и серверную части. Клиентская часть по требованию создает запрос
к удаленному ресурсу, а серверная часть выделяет удаленный ресурс с учетом прав доступа. В составе сетевой ОС также имеется
транспортная подсистема, позволяющая передавать информацию
между различными узлами сети. Функционирование транспортной
подсистемы опирается на совокупность протоколов более низкого
уровня. Все современные версии ОС являются сетевыми.
5
1.2. Назначение и функции операционной системы
Операционная система – это комплекс взаимосвязанных системных программных модулей и соответствующих таблиц, предназначенных для эффективного (в некотором смысле) распределения ресурсов
вычислительной системы во время выполнения пользовательских программ, а также для организации интерфейса между пользователями и
прикладными программами с одной стороны и аппаратурой с другой.
Интерфейс между пользователями и аппаратурой поддерживается на основе использования и реализации в составе ОС командного
языка запросов. В настоящее время такой язык имеет форму графических оболочек.
Интерфейс между пользовательскими программами (приложениями) и аппаратурой обеспечивается с помощью функций из состава интерфейса прикладного программирования – API (Application
Programming Interface).
Перечислим основные функции ОС как распределителя ресурсов:
– распределение процессора (процессорного времени) между активными процессами (задачами) и потоками вычислительной системы – диспетчеризация задач;
– организация оперативной памяти для осуществления мультипрограммного режима (организация виртуальной памяти, защита
различных областей памяти от несанкционированного доступа);
– организация ввода-вывода (планирование ввода-вывода, управление микроконтроллерами и внешними устройствами, организация
файлов и каталогов на магнитных дисках);
– организация механизма прерываний как основного средства координации функционирования различных компонент вычислительной системы;
– синхронизация доступа со стороны процессов (задач) к общим
(разделяемым) ресурсам системы;
– защита данных и администрирование (организация процедуры
логического доступа в систему, определение прав доступа при обращении к ресурсам системы, аудит системы, резервирование ресурсов);
– организация доступа к удаленным ресурсам в вычислительных сетях.
1.3. Понятие процесса, граф состояний процесса
Для понимания принципов функционирования современных ОС
необходимо определить понятия: процесса (задачи), потока, ресурса и прерываний.
6
Понятие процесс (задача) является одним из основных при рассмотрении ОС. Процесс (задача) – это некоторый комплекс действий,
связанный с выполнением отдельной программы в вычислительной
системе. Процесс одновременно является носителем данных и выполняет операции, связанные с их обработкой. Процесс может находиться в одном из четырех состояний – бездействия, готовности, выполнения (счета), ожидания (блокировки).
В состоянии бездействия процесс не потребляет (не использует)
никаких ресурсов вычислительной системы, кроме ресурса, необходимого для хранения описания процесса в некоторой форме.
В состоянии готовности процессу выделяются все необходимые
ресурсы или могут быть выделены в любой момент по требованию,
кроме процессора.
В состоянии выполнения процессу выделяется процессор (процессорное время), т. е. выполняются команды соответствующей программы.
В состоянии ожидания процесс ждет необходимый ему ресурс,
ранее выделенный некоторому другому процессу, или наступления
некоторого события.
Во время своего развития процессы могут многократно переходить из
одного состояния в другое. Такие переходы осуществляются в соответствии с графом переходов (рис. 1), где Б – состояние бездействия; Г – состояние готовности; В – состояние выполнения; О – состояние ожидания.
Переход из одного состояния в другое может инициироваться
пользователем, приложением или ОС, но контроль за такими переходами всегда осуществляет ОС. Это связано с тем, что любой переход предполагает выделение процессу конкретных ресурсов или освобождение ресурсов, а это является прерогативой ОС.
Состояния готовности, выполнения и ожидания являются активными состояниями, так как в этих состояниях процессы потребляют
ресурсы вычислительной системы и конкурируют за них. Состояние
бездействия, с этой точки зрения, считается пассивным состоянием.
Часто, в рамках конкретного процесса, можно выделить несколько подпроцессов (потоков), причем такие потоки могут выполняться
Б
В
Г
О
Рис. 1
7
параллельно относительно друг друга. Принципиальное различие
между процессами и потоками (threads) состоит в том, что разные
процессы имеют высокую степень обособленности друг от друга в отличие от потоков конкретного процесса. Высокая степень обособленности разных процессов выражается в том, что каждому процессу
выделяется свое адресное пространство, файлы, окна, семафоры и
другие ресурсы. Такая обособленность нужна, чтобы защитить процессы друг от друга и снизить конкуренцию за общие ресурсы. Потоки конкретного процесса не имеют собственных ресурсов, при своем
развитии они используют ресурсы, выделенные их процессу, кроме
ресурса процессорного времени. Граф переходов для потоков имеет
такой же вид, как и граф переходов для процессов.
1.4. Классификация процессов
Для более полного понимания сущности процессов рассмотрим
их классификацию по ряду классификационных признаков.
Временные ограничения. В соответствии с этим признаком процессы разделяются на процессы реального времени, интерактивные
процессы и пакетные процессы (фоновые).
Процессы реального времени – это процессы, требующие своего
полного выполнения к некоторому моменту времени. Другими словами, такие процессы должны выполняться в вычислительной системе как можно скорее, так как по своей сути они являются управляющими процессами, вырабатывающими управляющее воздействие на некоторый объект.
Интерактивные процессы – это процессы, время выполнения
которых должно укладываться в определенный интервал времени.
Интерактивные процессы характерны для многопользовательских
вычислительных систем, где сущность процесса состоит в выполнении некоторой функции по запросу пользователя.
К выполнению пакетных (фоновых) процессов временные требования не предъявляются.
Генеалогический признак. В вычислительной системе процессы могут требовать порождения (активизации) других процессов. Процесс, задающий такое требование, называется порождающим (родительским),
а создаваемый по требованию процесс – порожденным (дочерним).
Динамический признак. Два процесса относительно друг друга
будут считаться параллельными, если интервалы их существования пересекаются во времени. В противном случае процессы относительно друг друга будут считаться последовательными.
8
Интервалом существования процесса будем называть интервал
времени между моментом активизации процесса (переход из состояния бездействия в одно из активных состояний) и моментом его
окончания.
Принадлежность к центральному процессору. Внутренние процессы связаны с выполнение команд соответствующей программы
на процессоре. Внешние процессы – это процессы, которые развиваются на других устройствах вычислительной системы (устройства
ввода-вывода, микроконтроллеры). Внешние процессы могут развиваться асинхронно и независимо относительно работы центрального процессора.
Принадлежность к ОС. Системные процессы – это процессы,
связанные с выполнением модулей из состава ОС. Пользовательские (прикладные) процессы – это процессы, связанные с выполнением пользовательских программ и приложений.
Признак связности. Процессы называются взаимосвязанными,
если между ними существуют функциональные, управляющие, информационные или временные связи. В противном случае процессы
будут считаться изолированными.
Взаимосвязанные параллельные процессы называют взаимодействующими. Такие процессы выполняют некоторую общую работу,
используя, при этом, общие (разделяемые) ресурсы. Параллельные
процессы, которые используют общие ресурсы, не выполняя общей
работы в системе, называются конкурирующими.
1.5. Ресурсы вычислительных систем, их классификация
С точки зрения вычислительных систем, ресурсом является
средство вычислительной системы, которое может быть выделено
процессу (задаче) на определенный период времени для его успешного развития и выполнения.
Для более отчетливого понимания сущности ресурсов необходимо их определять в соответствии с различными классификационными признаками. Рассмотрим некоторые из них.
Реальность существования. В соответствии с этим классификационным признаком все ресурсы вычислительной системы можно
разделить на физические и виртуальные.
Физический ресурс – это ресурс, который реально существует
и имеет конкретные характеристики. Виртуальный (мнимый) ресурс представляет собой некоторую модель, в основе которой лежит
соответствующий физический ресурс. Как модель, виртуальный
9
ресурс, реализуется в некоторой программно-аппаратной форме,
и в этом смысле он существует. Виртуальный ресурс может иметь
свойства и характеристики, значительно отличающиеся от свойств
и характеристик соответствующего физического ресурса. Примером такого отличия является разница в характеристиках и в возможностях виртуальной и физической памяти компьютера.
Форма реализации. В соответствии с этим признаком ресурсы
разделяются на аппаратные (твердые) и мягкие (остальные). К мягким ресурсам относятся, прежде всего, программные ресурсы.
К аппаратным ресурсам относятся процессор, оперативная память,
магнитные диски и другие устройства ввода/вывода, а к программным – библиотечные модули, драйверы, компиляторы и т. д.
Время существования. Ресурс, существующий в системе до момента порождения процесса и доступный для использования на
всем интервале существования процесса, называется постоянным.
Временной ресурс может появляться и исчезать в системе динамически в течение интервала существования процесса. К временным
ресурсам относятся различного рода сигналы, включая сигналы
прерываний, а также различные сообщения, которыми процессы
обмениваются между собой.
Структура. Ресурс называется простым, если не содержит составных элементов и рассматривается при распределении процессам как единое целое. Составной ресурс характеризуется некоторой структурой, т. е. имеет в своем составе некоторые однотипные
элементы, обладающие одинаковыми характеристиками. Простые
ресурсы могут находиться только в двух состояниях – «занят»,
«свободен», а для составных ресурсов характерны три состояния –
«занят», «свободен», «частично занят». Примером простого ресурса,
с точки зрения операционных систем, является процессор, а составного – оперативная память.
Возможность восстанавливаемости. Ресурс называется воспроизводимым (системным), если после его использования некоторым
процессом, он может быть использован другим процессом. Потребляемый ресурс – это ресурс, который после своего использования
некоторым процессом, исчезает из системы. К потребляемым ресурсам, прежде всего, относятся сигналы и сообщения.
1.6. Прерывания и порядок их обработки
Механизм прерываний является основным координирующим
механизмом в вычислительной системе, так как с его помощью
10
решается задача параллельного функционирования различных
устройств системы и корректного реагирования на особые события,
которые в ней могут происходить. Прерывание – это принудительная передача управления от выполняемой программы к системе (а
через нее к специальной программе обработки прерывания – обработчику прерывания), происходящая при возникновении определенного события. Основная идея прерываний – реализация асинхронного режима работы и распараллеливание работы отдельных
устройств вычислительной системы.
Все виды прерываний можно разделить на внутренние и внешние прерывания. Внутренние прерывания определяются событиями, связанными с работой центрального процессора (попытка деления на ноль, переполнение разрядной сетки, попытка сформировать
неправильный адрес в оперативной памяти и т. п.). Внешние прерывания связаны с работой таймера и других устройств ввода/вывода.
Внешние прерывания носят асинхронный характер по отношению
к работе центрального процессора.
С другой стороны, все виды прерываний можно разделять на аппаратные и программные. Программные прерывания по своей форме представляют собой программное обращение к необходимому обработчику прерываний. Все множество обработчиков прерываний
являются резидентными модулями из состава ОС.
Порядок обработки прерываний идентичен для различных архитектур вычислительных систем и состоит в следующем:
1. Прежде всего выполняется до конца текущая команда прерываемой программы.
2. Устанавливается факт прерывания и определяется его тип.
3. Запоминается состояние прерываемого процесса (сохраняется
контекст задачи), т. е. сохраняется на момент прерывания в определенном месте памяти содержимое регистров процессора (прежде
всего счетчика команд).
4. Передается управление обработчику прерываний. Для этого
в счетчик команд заносится начальный адрес обработчика прерываний,
а в соответствующие регистры – информация о данном обработчике.
5. При необходимости сохраняется дополнительная информация
о прерываемой программе.
6. Обработка прерывания, т. е. выполнение команд обработчика
прерывания.
7. Восстановление информации о раннее прерванном процессе
(этап, обратный этапу 5) и возврат в прерванную программу.
Этапы 1–4 реализуются аппаратно, а шаги 5–7 – программно.
11
Сигналы, вызывающие прерывания, могут возникать в различных
устройствах вычислительной системы, более того, они могут возникать одновременно. Поэтому возникает задача определения очередности обработки прерываний. Данная задача решается на основе разных
приоритетов для различных типов прерываний. Приоритеты различных типов прерываний, в порядке их уменьшения, определяются следующим образом:
– прерывания от средств контроля процессора (наивысший приоритет);
– прерывания системного таймера;
– прерывания от магнитных дисков;
– прерывания сетевого оборудования;
– прерывания от терминалов;
– программные прерывания.
Учет приоритетов может быть встроен в технические средства, а
также определяться ОС, т. е. очередность обработки прерываний осуществляется аппаратно-программным путем. Кроме того, в составе
современных вычислительных систем есть средства, позволяющие
проигнорировать сигналы прерываний или отложить их обработку (маскирование прерываний). Наличие таких средств позволяет управлять очередностью обработки прерываний в соответствии
с различными правилами (дисциплины обслуживания прерываний).
Рассмотрим наиболее характерные из них:
– с относительными приоритетами, т. е. обслуживание не прерывается даже при наличии запросов с более высокими приоритетами; после окончания обслуживания данного запроса обслуживается запрос с наивысшим приоритетом;
– с абсолютным приоритетом, т. е. всегда обслуживается запрос с наивысшим приоритетом;
– по принципу стека, или, как говорят по дисциплине LCFS (last
come first served – последним пришел – первым обслужен), т. е. запросы с более низким приоритетом могут прерывать обработку запросов с более высоким приоритетом.
Последние две дисциплины предполагают возможность прерывания работы обработчиков прерываний, т. е. в этих случаях обработка прерываний носит многоуровневый характер.
В состав ОС входит специальная компонента – супервизор прерываний (диспетчер прерываний), которая реализует некоторую дисциплину обслуживания прерываний. Такой супервизор использует
специальные программно-аппаратные механизмы включения, отключения и маскирования прерываний.
12
1.7. Архитектура операционной системы
Современные ОС имеют модульную структуру, которая позволяет увеличивать их возможности развития, расширения и переноса
на новые платформы. Единой архитектуры ОС не существует, но существуют универсальные подходы к структуированию ОС. Модули
ОС разделяются на две группы: ядро ОС и вспомогательные модули.
Модули ядра ОС выполняют основные функции по распределению ресурсов в вычислительной системе. Они используются часто и
должны работать как можно быстрее. Поэтому такие модули оформляются как резидентные (резидентные модули – это модули, коды
которых постоянно находятся в ОП). Следовательно, при загрузке
системы ядро ОС всегда помещается в специально выделенную область оперативной памяти.
Вспомогательные модули ОС выполняют функции, не требующие
частого использования (сжатие, архивирование, копирование и т. п.).
Они оформляются как дискрезидентные модули (дискрезидентные
модули – это модули, которые постоянно хранятся во внешней памяти и загружаются в ОП только на время своего выполнения).
Модули, входящие в состав ОС, можно классифицировать по
кратности использования. Однократно используемые модули – это
модули, которые могут быть правильно выполнены только один
раз, так как при своем выполнении они «портят» свою собственную
память. Примером такого модуля является абсолютный загрузчик
системы. Модули многократного применения (повторно используемые модули) могут быть, в свою очередь, непривилегированными,
привилегированными и реентерабельными.
Непривилегированные программные модули – это модули, которые могут быть прерваны во время своей работы, причем, промежуточные результаты их работы не сохраняются.
Привилегированные программные модули не могут быть прерваны во время своего выполнения, т. е. они работают при отключенной
системе прерываний. Такие модули, начав работать, выполняются до
конца.
Реентерабельные программные модули допускают повторное
многократное прерывание своего выполнения и повторный их запуск, причем при каждом таком прерывании происходит запоминание промежуточных результатов в некоторой специально отведенной для этого области памяти. Такие модули обычно состоят из трех
секций. Первая секция предназначена для выделения памяти под
промежуточные результаты выполнения. Вторая секция представ13
ляет собой непосредственный код программного модуля. Третья
секция – это секция освобождения памяти, которая использовалась
для хранения промежуточных результатов. Первая и третья секции
работают как привилегированные секции, а вторая – как непривилегированная. Примерами реентерабельных модулей является ряд
драйверов из состава ОС.
Также в составе ОС существуют повторно входимые модули. Такие модули допускают свое многократное параллельное использование, но их нельзя прерывать. Повторно входимые модули состоят из привилегированных секций, каждая из которых имеет свою
собственную точку входа (начальный адрес). После выполнения
очередной такой секции управление может быть передано системой
другой секции того же модуля или повторно той же самой секции.
Привилегированный режим. Ни одно приложение при своем
функционировании не должно иметь возможности без контроля со
стороны ОС получать ресурсы вычислительной системы. Поэтому
ОС должна иметь полномочия (привилегии) по распределению ресурсов. Обеспечение таких привилегий для ОС осуществляется за счет
средств аппаратной поддержки, которые поддерживают два режима работы вычислительной системы – пользовательский и привилегированный (режим ядра). Поскольку ядро ОС выполняет основные ее функции, именно оно должно работать в привилегированном
режиме. В пользовательском режиме работают пользовательские
программы и некоторые дискрезидентные утилиты из состава ОС.
В пользовательском режиме запрещается выполнение некоторых инструкций (команд), связанных с распределением ресурсов вычислительной системы (переключение процессора, управление вводом/выводом, механизмы распределения и защиты памяти и т. д.). Переход
из пользовательского режима в привилегированный инициируется
соответствующим системным вызовом из состава API, а осуществляПользовательский
режим
Пользовательский
режим
Режим ядра
t
t1
t2
Рис. 2
14
ется аппаратными средствами. Наличие привилегированного режима функционирования вычислительной системы повышает ее устойчивость и надежность, так как распределение ресурсов происходит
под жестким контролем ОС. С другой стороны, наличие привилегированного режима несколько снижает производительность системы,
что видно из рис. 2.
Потеря производительности связана с тем, что на переход из пользовательского режима в привилегированный и обратно тратится
определенное время (интервалы t1 и t2). Чем больше в пользовательской программе системных вызовов, тем больше таких переходов.
1. 8. Структура ядра операционной системы
Ядро ОС представляет собой сложный многофункциональный
комплекс, состоящий из большого числа различных, взаимосвязанных модулей. Поэтому структура ядра ОС носит многослойный характер, где каждый слой реализует функции определенного типа.
С некоторой долей условности можно выделить пять основных слоев.
Средства аппаратной поддержки ОС. Часть функций ОС может
выполняться аппаратными средствами. Поэтому такие средства
можно считать частью ОС. Они связаны с организацией вычислительных процессов (средства поддержки привилегированного режима, система прерываний, средства переключений контекстов процессов, средства защиты памяти и т. п.).
Машинно-зависимые компоненты ОС. Этот слой образуют программные модули, в которых отражается специфика аппаратной
платформы компьютера. В идеале этот слой должен полностью
экранировать вышележащие слои ядра от особенностей аппаратуры. Это позволяет разрабатывать вышележащие слои ядра на основе машинно-независимых модулей, существующих в единственном
экземпляре для всех типов аппаратных платформ.
Базовые механизмы ядра. Этот слой выполняет наиболее примитивные операции ядра (программное переключение контекстов процессов, диспетчеризация прерываний, перемещение страниц из памяти на диск и обратно и т. п.). Эти модули не принимают решений
о распределении ресурсов – они только отрабатывают принятые «наверху решения».
Менеджеры ресурсов. Этот слой состоит из мощных функциональных модулей, реализующих стратегические задачи по управлению
основными ресурсами вычислительной системы. Обычно на данном
слое работают менеджеры (диспетчеры) процессов, ввода-вывода,
15
файловой системы и ОП. Каждый из менеджеров ведет учет свободных и используемых ресурсов определенного типа и планирует их
распределение в соответствии с запросами приложений. Внутри слоя
менеджеров существуют тесные взаимосвязи, отражающие тот факт,
что для выполнения процессу требуется доступ к нескольким ресурсам – процессору, оперативной памяти, возможно, к внешней памяти
или устройству ввода-вывода.
Интерфейс системных вызовов. Этот слой является самым верхним слоем ядра и взаимодействует непосредственно с приложениями и системными утилитами, образуя прикладной программный
интерфейс ОС – API. Системные вызовы, в свою очередь, обращаются к менеджерам ресурсов, причем для выполнения одного системного вызова, возможно, необходимо несколько таких обращений.
Такое разбиение ядра ОС на слои является достаточно условным.
В реальной системе количество слоев и распределение функций
между ними может быть иным. Выбор числа слоев является ответственным и трудным делом: увеличение числа слоев ведет к некоторому замедлению работы ядра за счет дополнительных накладных
расходов на межслойное взаимодействие, а уменьшение числа слоев
ухудшает расширяемость и логичность системы.
1. 9. Микроядерная архитектура операционной системы
Микроядерная архитектура является альтернативой классического способа построения ОС. Суть микроядерной архитектуры состоит в следующем. В привилегированном режиме остается работать только небольшая часть ОС, называемая микроядром. Микроядро защищено от остальных частей ОС и приложений. В состав
микроядра обычно входят машинно-зависимые модули, а также
модули, выполняющие базовые функции ядра по управлению процессами, обработке прерываний, управлению виртуальной памятью, пересылке сообщений и управлению устройствами ввода-вывода, связанные с загрузкой или чтением регистров устройств. Набор
функций микроядра обычно соответствует функциям слоя базовых
механизмов обычного ядра. Такие функции невозможно, как правило, выполнить в пространстве приложений.
Все остальные более высокоуровневые функции ядра оформляются в виде приложений, работающих в пользовательском режиме. По своему назначению такие приложения предназначены для
выполнения запросов других приложений (создание процесса, выделение памяти, проверка прав доступа к ресурсу и т. п.). Именно
16
поэтому менеджеры ресурсов, вынесенные в пользовательский режим, называются серверами ОС, то есть модулями, основным назначением которых является обслуживание запросов локальных
приложений и других модулей ОС. Очевидно, что для реализации
микроядерной архитектуры необходимым условием является наличие в ОС удобного и эффективного способа вызова процедур одного
процесса из другого. Поддержка такого механизма и является одной из задач микроядра.
Схематично механизм обращения к функциям ОС, оформленным в виде серверов, выглядит следующим образом. Клиент (приложение или другой компонент ОС) запрашивает выполнение
некоторой функции у соответствующего сервера, посылая ему
сообщение. Непосредственная передача сообщений между приложениями невозможна, так как их адресные пространства изолированы друг от друга. Микроядро, выполняющееся в привилегированном режиме, имеет доступ к адресным пространствам
каждого из приложений и поэтому может работать в качестве
посредника. Микроядро сначала передает сообщение, содержащее имя и параметры вызываемой процедуры нужному серверу,
затем сервер выполняет запрошенную операцию, после чего микроядро возвращает результаты клиенту с помощью другого сообщения. Таким образом, работа микроядерной ОС соответствует
известной модели клиент – сервер, в которой роль транспортных
средств выполняет микроядро.
Преимущества микроядерной архитектуры определяются следующими свойствами:
– высокая степень переносимости, которая обусловлена тем, что
весь машинно-независимый код изолирован в микроядре, поэтому
для переноса системы на новый процессор требуется меньше изменений;
– высокая степень расширяемости, так как добавление новых
функций и изменение существующих значительно упрощается изза того, что все модификации можно оформлять и реализовывать
в пользовательском режиме;
– повышенная надежность ОС, так как все серверы выполняются
в своих адресных пространствах, изолированных друг от друга, и, кроме того, серверы не имеют непосредственного доступа к аппаратуре.
Недостатком микроядерной архитектуры ОС является более низкая производительность. Это связано с тем, что при выполнении
запроса клиента необходимо, по крайней мере, дважды переходить
в привилегированный режим (см. рис. 3). Увеличение числа пере17
Пользовательский режим
приложение
Пользовательский режим
сервер ресурса
Режим
ядра
Режим
ядра
t1
Пользовательский режим
приложение
t2
t3
t4
Рис. 3
ходов из пользовательского режима в привилегированный режим
и обратно, влечет за собой дополнительные временные затраты на
выполнение запросов к ОС.
Выводы
1. Полноценные ОС появляются на этапе создания первых мультипрограммных вычислительных систем как необходимые средства для взаимосвязанных сложных решений по распределению и
перераспределению различных ресурсов вычислительных систем.
2. Мультипрограммные вычислительные системы обеспечивают
параллельное развитие и выполнение процессов в рамках вычислительной системы.
3. При изучении различных ОС основными терминами являются
термины, связанные с понятиями «процесс» и «ресурс».
4. Механизм прерываний, как один из основных механизмов в составе ОС, является необходимым для координации всего множества
вычислений.
5. Наиболее важной частью ОС является его ядро, в котором содержится код самых важных и часто используемых внутренних
сервисов системы.
6. Ядро ОС всегда является резидентным (постоянно хранится в ОП на
время сеанса работы) и функционирует в привилегированном режиме.
7. Ядро ОС обладает внутренней структурой и может иметь различную архитектуру.
Контрольные вопросы
1. В каких вычислительных системах впервые появились системные программы?
18
2. Какова основная цель мультипрограммных вычислительных
систем?
3. Что означает фраза «процесс находится в активном состоянии»?
4. В каком состоянии процесс ждет доступа к процессору?
5. Какой из указанных типов ресурсов можно считать потребляемым: файл, память, переменная, сигнал, процессор?
6. В чем принципиальная разница между внешними и внутренними прерываниями?
7. Что значит сохранить состояние прерываемой программы?
8. Какая дисциплина обслуживания прерываний не требует выполнения прерываний самих обработчиков прерываний?
9. Какие программные модули из состава ОС не войдут в состав
ядра?
10. Каким образом осуществляется переход из пользовательского режима в привилегированный?
11. При микроядерной архитектуре ОС какая характеристика
вычислительных систем ухудшается?
19
2. ПЛАНИРОВАНИЕ И ДИСПЕТЧЕРИЗАЦИЯ
ЗАДАЧ И ПРОЦЕССОВ
2.1. Планирование и диспетчеризация процессов.
Дескрипторы задач
Планирование процессов (задач) – это определение очередности
получения ресурсов вычислительной системы для процессов при их
активизации. Планирование процесса связано с его переводом из состояния бездействия в состояние готовности. Такой перевод осуществляется однократно на интервале существования процесса.
Диспетчеризация процессов (задач) – это определение очередности получения процессора для процессов (задач), находящихся
в состоянии готовности, с целью их выполнения. Диспетчеризация
процесса связана с его переводом из состояния готовности в состояние выполнения (счета). Диспетчеризация для конкретного процесса может выполняться многократно, т. е. процесс может несколько
раз переходить из состояния готовности в состояние выполнения и
обратно на интервале своего существования. Поскольку в каждый
такт процессорного времени могут выполняться команды только одной задачи, диспетчеризация предполагает создание и модификацию
очереди готовых к выполнению задач (процессов). Элементами такой
очереди (как и других очередей в вычислительной системе) на «физическом уровне» являются дескрипторы задач.
Дескриптор задачи – это специальная информационная структура, в которой хранятся характеристики задачи, необходимые
для целей управления со стороны ОС. Первоначально дескриптор
задачи формируется на этапе ее трансляции. Перед выполнением
задачи такой дескриптор загружается в ОП совместно с ее кодом
и данными. Информация о задаче, которая хранится в дескрипторе, разделяется на несколько групп, и часть ее динамически
изменяется на интервале существования задачи. Рассмотрим эти
группы:
– информация по идентификации задачи (имя задачи, тип задачи);
– информация о ресурсах, которые необходимы задаче для ее выполнения, и о ресурсах, которые используются в настоящее время
(идентификаторы необходимых внешних устройств);
– информация о текущем состоянии задачи (содержимое некоторых регистров процессора);
– информация о родственных связях задачи (имена родительского процесса и процессов-предков);
20
– информация, необходимая для целей планирования и диспетчеризации (адресные ссылки на соседние дескрипторы, находящиеся в той же очереди, приоритет задачи, ссылки на объекты синхронизации).
Обычно дескриптор задачи имеет размер порядка нескольких десятков машинных слов. Есть два основных способа размещения дескрипторов в ОП. Первый, более ранний, состоит в том, что ОС выделяет в системной области памяти специальный раздел под таблицу
дескрипторов. Такая таблица имеет фиксированный размер и фиксированный начальный адрес. Такой способ прост с точки зрения управления и сложности реализации, но имеет существенный недостаток –
ограничение параллелизма в вычислительной системе. Причиной этого недостатка является ограниченный размер таблицы дескрипторов.
Второй способ, более современный, состоит в том, что ОС выделяет подходящую свободную область ОП под очередной загружаемый дескриптор задачи. Методологически такой способ не ограничивает параллелизм функционирования вычислительной системы.
2.2. Дисциплины диспетчеризации
Дисциплина диспетчеризации – это некоторое основное правило,
реализующее очередность предоставления (выделения) процессора
(процессорного времени) готовым к выполнению задачам (процессам). Любая конкретная дисциплина диспетчеризации выполняет
две взаимосвязанные функции – выделение процессорного времени
конкретной задаче (процессу), и создание и модификация очереди
готовых к выполнению задач (обслуживание очереди). Дисциплина
диспетчеризации реализуется специальной компонентой ОС – диспетчером (диспетчером задач). Рассмотрим наиболее важные дисциплины диспетчеризации.
1. FCFS (first come – first served – первым пришел – первым обслужен) – прежде процессор получает ту задачу, которая раньше
перешла в состояние готовности. Данная дисциплина проста в реализации, равноправна по отношению, как к «длинным » так и к «коротким» процессам, среднее время пребывания в очереди готовности
весьма значительное.
2. SJN (shortest job next – следующий с кратчайшим заданием) –
прежде процессор получает ту задачу, которая имеет минимальное
заказное время обслуживания. Данная дисциплина требует, чтобы
для каждой задачи была известна оценка потребности в машинном
времени, значение которой задается как параметр задачи. Такая
21
дисциплина более сложна в реализации по сравнению с FCFS, она
дискриминационна по отношению к «длинным процессам», среднее
время пребывания в очереди готовности меньше чем для FCFS. SJN
имеет существенный недостаток. Задачи, которые были временно
заблокированы (например, ожидали завершения ввода / вывода),
в результате попадут в конец очереди готовности, даже если для их
выполнения требуется небольшое процессорное время.
3. SRT (shortest remaining time) – раньше процессор получает
ту задачу, которая имеет меньше всего времени для своего завершения. Это время определяется как разность между заказанным
временем обслуживания и тем процессорным временем, которое задача уже получила. SRT свободна от недостатка, характерного для
SJN. SRT сложна в реализации и дискриминационна по отношению
к «длинным» процессам.
Рассмотренные дисциплины диспетчеризации являются невытесняющими, в отличие от вытесняющих дисциплин, которые будут описаны далее. Вытесняющей дисциплиной диспетчеризации
будем называть такую дисциплину, которая предполагает возможное прерывание выполнения текущей задачи с целью предоставления процессора другой готовой к выполнению задаче. Рассмотрим
некоторые основные вытесняющие дисциплины диспетчеризации:
4. RR (round robin) – циклическая (карусельная) дисциплина.
Диспетчер выделяет готовой к выполнению задаче некоторый квант
процессорного времени (интервал мультиплексирования). Если задача не успевает выполниться в течение этого кванта, диспетчер переводит ее обратно в конец очереди готовности и выделяет следующий
квант процессорного времени для другой готовой задачи. Данная
дисциплина является дискриминационной по отношению к длинным процессам. Ее удобно использовать в многопользовательских
вычислительных системах, где требуется обслуживать большое число запросов, поступающих с различных рабочих станций системы.
5. Дисциплины на основе абсолютных приоритетов задач. Каждая задача имеет приоритет, выраженный конкретным значением,
который не меняется на всем интервале существования задачи. Прежде процессор будет получать ту готовую задачу, которая в данный
момент имеет максимальный приоритет по отношению к другим готовым задачам. Данная дисциплина характерна для систем реального времени, она дискриминационна по отношению к длинным процессам и не дает гарантий обслуживания для таких процессов.
6. Дисциплины на основе динамических приоритетов задач.
Для каждой задачи задается начальное значение приоритета, кото22
рое затем изменяется во времени. Таким образом, приоритет задачи есть функция времени. Конкретный вид таких функций может
быть разный, но общая их направленность состоит в том, что чем
дольше задача находится в очереди готовности, тем выше становится ее приоритет. Это позволяет гарантировать обслуживание как
«коротких», так и «длинных» процессов.
7. Дисциплины с несколькими очередями. Диспетчер поддерживает несколько очередей, готовых к выполнению задач. Каждая очередь обслуживается по своей дисциплине. Такой диспетчер сложен
в реализации, так как в его составе должен быть дополнительный
механизм переключения с одной очереди готовности на другую.
Более простой способ реализации диспетчера (статический) предполагает, что задача, попав в некоторую очередь готовности, там и
остается до своего полного выполнения. Более сложным способом
реализации (динамическим) является способ, при котором задача
может переходить из одной очереди готовности в другую на интервале своего существования.
2. 3. Дисциплины планирования
Планирование – это определение очередности выделения ресурсов системы задачам (процессам), которые хотят активизироваться
и начать свое выполнение. Планирование связано с работой совокупности менеджеров ресурсов ОС (планировщик памяти, супервизор ввода/вывода, файловая система и т. д.).
Наиболее естественной дисциплиной планирования является
FCFS. Содержательный смысл этой дисциплины, в данном случае,
состоит в следующем: необходимые ресурсы, прежде всего, выделяются той задаче, для которой раньше появилось требование активизации.
Другой возможной дисциплиной планирования является SJN.
Эта дисциплина предполагает предпочтительное выделение необходимых ресурсов задаче с наименьшей оценкой времени ее выполнения по сравнению с соответствующими оценками других задач.
Выводы
1. Диспетчеризация для конкретного вычислительного процесса
может производиться многократно, а планирование является однократным действием на время существования такого процесса в вычислительной системе.
23
2. Планирование и диспетчеризация связана с организацией очередей активных процессов к различным ресурсам вычислительной
системы. Такие очереди создаются и поддерживаются ОС.
3. На физическом уровне элементами очередей являются дескрипторы задач (процессов).
4. Конкретную дисциплину диспетчеризации реализует диспетчер задач, как одна из основных компонент ОС.
5. При диспетчеризации происходит распределение и перераспределение процессора, как одного из основных ресурсов системы,
между множеством активных процессов (задач).
Контрольные вопросы
1. Какая дисциплина диспетчеризации будет оптимальной, если
необходимо обеспечить равный доступ к выполнению задач со всех
рабочих мест во многотерминальной ВС – LFCS, RR, SRT, SJN?
2. В чем состоит основное отличие между невытесняющими и
вытесняющими дисциплинами диспетчеризации?
3. Как понимать «дискриминацию» по отношению к «длинным
процессам»?
4. Что такое «гарантии обслуживания» и как они достигаются
при диспетчеризации?
24
3. УПРАВЛЕНИЕ ОПЕРАТИВНОЙ ПАМЯТЬЮ
Оперативная память является важнейшим ресурсом любой вычислительной системы. Она состоит из фиксированного числа ячеек,
предназначенных для хранения кодов программ и данных. Команды
программы могут выполняться на процессоре, если их коды и операнды предварительно загружены в ОП. Некоторая часть ОП всегда
отводится для хранения ядра ОС, которое обычно загружается по
младшим адресам памяти. Большая часть ОП используется для хранения пользовательских программ и данных. Проблема управления
ОП со стороны ОС сводится к решению двух взаимосвязанных задач:
– эффективное (в некотором смысле) распределение ОП между
несколькими активными задачами с целью обеспечения мультипрограммного режима;
– защита памяти от несанкционированного доступа, т. е. контроль и запрет попыток адресации к «чужим» или запрещенным
областям памяти.
Для понимания способов организации ОП необходимо знать методы отображения символьных имен переменных, которыми пользуются программисты, в конкретные физические адреса ячеек ОП.
3.1. Пространства и отображения,
виртуальное адресное пространство
Программист при написании программы определяет необходимые ему переменные с помощью символьных (логических) имен.
Другими словами, он задает некоторое подмножество переменных,
используя логическое адресное
пространство. Это пространство
Логические
ограничено правилами синтаксиимена
са конкретного языка программиСистема программирования
рования. Логические имена переменных можно интерпретировать
Виртуальные
как символьные адреса. Задача
адреса
вычислительной системы, для
Операционная система
того чтобы программа была выполнена, состоит в отображении
Физические
этих адресов в конкретные физиадреса
ческие адреса. Такое отображение, в общем случае, осуществляРис. 4
ется в два этапа (см. рис. 4).
25
Первый этап реализует система программирования (транслятор),
на котором логические имена переменных преобразуются в виртуальные адреса. Конкретный вид таких адресов зависит от архитектуры вычислительной системы, конкретного транслятора и ряда
других факторов. Совокупность возможных виртуальных адресов
образует виртуальное адресное пространство.
Второй этап реализуется ОС совместно с аппаратурой. На этом
этапе виртуальные адреса отображаются в физические адреса ОП.
Конкретные значения физических адресов зависят от размера физической памяти, а в совокупности определяют физическое адресное
пространство.
При изучении данного вопроса необходимо выделить четыре возможных варианта отображения.
При первом варианте предполагается, что виртуальное адресное
пространство тождественно физическому адресному пространству.
Поэтому система программирования полностью реализует отображение логических имен в физические адреса. Этот случай характерен для отображения так называемых «абсолютных программ».
В командах таких программ в явном виде указываются их физические адреса и физические адреса операндов. Задача ОС сводится
к обычной загрузке в память по указанным адресам.
Второй вариант предполагает эквивалентность пространства логических имен и виртуального адресного пространства. В этом случае задача отображения целиком лежит на ОС. Такая ОС носит специфический характер и называется интерпретатором. Интерпретатор последовательно транслирует в машинный код и выполняет текущие операторы программы. При этом он создает свои внутренние
таблицы, в которых определяется соответствие между логическими
именами переменных и физическими адресами.
При третьем варианте отображение осуществляется в два этапа.
При этом конкретному виртуальному адресу жестко соответствует
конкретный физический адрес. Отображение осуществляется до
начала выполнения задачи, т. е. код задачи не меняет своего местоположения в памяти на все время ее выполнения.
При четвертом варианте отображение также осуществляется
в два этапа, причем конкретному виртуальному адресу могут соответствовать несколько физических адресов. Это означает, что
физические адреса определяются на этапе выполнения задачи, а
ее код может менять свое местоположение в ОП. Этот вариант соответствует различным способам организации виртуальной памяти.
26
3.2. Распределение разделами
Та часть ОП, которая предназначена для хранения пользовательских задач и приложений, распределяется на несколько разделов.
Каждый раздел предназначен для единовременного хранения кода
и данных одной задачи. Загружаемой в ОП логической единицей
является задача. Число разделов может быть различным в разные
моменты работы вычислительной системы, но экспериментально
доказано, что для того чтобы процессор был загружен на 90%, необходимо иметь в ОП 4–5 задач. Число задач, одновременно загруженных в ОП, называется коэффициентом мультипрограммирования.
Существует несколько стратегий (дисциплин) распределения памяти разделами. Рассмотрим основные дисциплины.
Распределение фиксированными разделами. Распределение ОП
на разделы производится на этапе конфигурации вычислительной
системы. Каждый раздел имеет фиксированный начальный адрес
и фиксированный размер. Заданное распределение не может изменяться во время работы вычислительной системы вплоть до новой
ее конфигурации. Такая дисциплина распределения памяти имеет
очевидный недостаток – значительные области памяти оказываются
неиспользованными (фрагментация памяти). Причиной высокого
уровня фрагментации памяти является несоответствие размеров выделенных разделов и размеров кодов загружаемых задач (см. рис. 5).
kernel
Task1
part 1
Task2
part 2
Task3
part 3
Task4
part 4
Рис. 5
27
Затемненные области на рис. 5 показывают незаполненные полезным кодом участки памяти. Единственным достоинством такой
дисциплины распределения памяти является простота управления
со стороны ОС. Для снижения уровня фрагментации памяти используется распределение разделами с подвижными границами.
Распределение разделами с подвижными границами. Основная
идея данной дисциплины распределения заключается в том, что
в памяти выделяется раздел, размер которого равен размеру очередной загружаемой задачи. Следовательно, такое выделение возможно только во время работы вычислительной системы. Поэтому
в составе ОС необходимо иметь некоторое средство, позволяющее
оперативно предоставлять память под загружаемые задачи. Такое
средство будем называть планировщиком памяти.
Планировщик памяти входит в состав ядра ОС. Он создает и
поддерживает в своей собственной памяти список свободных областей. Элементы такого списка состоят из двух полей. В первом поле
хранится значение начального адреса свободной области памяти, а
во втором – значение размера этой области. Просматривая список,
планировщик определяет свободную область памяти, подходящую
по размеру для очередной загружаемой задачи, после чего производится непосредственная загрузка кода задачи в память. После
каждой загрузки планировщик модифицирует (корректирует) вышеуказанный список. Просмотр списка с целью определения подходящей свободной области памяти может осуществляться двумя
способами – «первый подходящий» или «наиболее подходящий».
Первый способ предполагает поиск любой свободной области памяти, размер которой не меньше размера кода загружаемой задачи. Второй способ предполагает поиск свободной области памяти,
размер которой наиболее близок размеру кода загружаемой задачи
и при этом не меньше, чем размер этого кода. При первом способе
требуется просматривать, в среднем, половину списка, а при втором – весь список. Кроме того, планировщик реализует функцию
освобождения памяти после выполнения очередной задачи, модифицируя список свободных областей памяти.
При данной дисциплине распределения памяти уровень фрагментации и коэффициент мультипрограммирования могут значительно изменяться во времени, что показано на рис. 6.
В момент τ1 в памяти находятся коды четырех задач. В момент
τ2 закончилось выполнение задачи task2, и планировщик освободил память, достаточную для загрузки задачи task5 (момент τ3).
В момент τ4 закончилось выполнение задачи task3, планировщик
28
kernel
Task1
kernel
Task1
kernel
Task1
Task5
Task2
Task3
Task3
Task3
Task4
Task4
Task4
τ1
τ2
τ3
kernel
Task1
kernel
Task1
kernel
Task1
Task5
Task5
Task5
Task6
Task7
Task4
τ4
τ5
τ6
Рис. 6
освободил память, но размеры свободных областей недостаточны
по размеру для загрузки задачи task6. Поэтому очередная загрузка произойдет только после выполнения task4 и соответствующего
освобождения памяти (момент τ5). При этом размер свободной области памяти оказался достаточным для загрузки кодов сразу двух
задач – task6 и task7 (момент τ6).
Данная дисциплина распределения является средством локальной оптимизации, так как оптимизируется местоположение в памяти для конкретной задачи, но не распределение всей памяти в целом.
Распределение подвижными разделами. Для оптимизации распределения всей памяти в целом и уменьшения уровня фрагментации
можно использовать метод смещения (сдвига) по адресам кодов загруженных задач с целью получения непрерывных областей памяти, размеры которых будут достаточны для загрузки новых задач (рис. 7).
В момент τ1 в памяти имеется две свободные области, но ни одна
из них недостаточна по размеру, чтобы загрузить следующую зада29
kernel
Task1
kernel
Task1
kernel
Task1
Task5
Task5
Task5
Task4
Task4
Task4
τ1
Task6
τ2
τ3
Рис. 7
чу. Планировщик делает смещение кода задачи task4, образуя одну,
большую по размеру, непрерывную свободную область памяти (момент τ2). Поэтому появляется возможность загрузить следующую
задачу task6 (момент τ3).
Смещение в памяти кода задачи, которое выполняет планировщик, должно быть согласовано по времени с окончанием операции
ввода / вывода для этой задачи (в данном случае – task4). Если такое
согласование отсутствует, то результаты ввода-вывода могут записаться на «старое» место в памяти, и задача будет разрушена. С другой стороны, такое согласование противоречит принципам мультипрограммирования, в соответствии с которыми внешние устройства
должны работать независимо и асинхронно относительно центрального процессора. Поэтому данная дисциплина распределения разделами не нашла практического применения.
3.3. Сегментная организация памяти
Сегментная организация памяти – это один из способов организации виртуальной памяти. Транслятор подготавливает задачу
в виде совокупности сегментов в общем случае разного размера. Эти
сегменты хранятся во внешней памяти. Адресация внутри сегментов носит непрерывный характер. Виртуальные адреса после трансляции имеют вид – (s,d), где s – виртуальный номер сегмента, а d –
смещение относительно начала сегмента. Предполагается, что в общем случае, при первоначальной загрузке сегментов задачи в ОП,
не все из них могут попасть в нее, и часть сегментов задачи может
остаться во внешней памяти. Отображение виртуальных адресов
30
Регистр начального адреса
таблицы дескрипторов
сегментов текущей
выполняемой задачи
Таблица дескрипторов
сегментов
S
D
Сегмент
+
Pr
A
R
+
Рис. 8
в физические происходит на этапе выполнения задачи и имеет вид
(см. рис. 8).
При загрузке задачи в ОП, ОС совместно с аппаратурой создает
в памяти таблицу дескрипторов сегментов задачи. Первоначально
дескрипторы сегментов задачи создаются на этапе ее трансляции.
Каждый дескриптор имеет поля, содержимое которых может изменяться во время выполнения задачи. На рис. 8 показаны некоторые
из них: Pr – битовый признак присутствия-отсутствия сегментов в ОП
(0 – сегмент отсутствует в памяти, 1 – сегмент присутствует в памяти);
A – начальный адрес сегмента; R – размер сегмента.
В специальном регистре процессора хранится значение начального адреса таблицы дескрипторов сегментов выполняемой задачи.
При переключении на выполнение новой задачи ОС меняет содержимое этого регистра. Отображение виртуальных адресов в физические адреса производится в два этапа. На первом этапе определяется
адрес конкретного дескриптора в таблице путем сложения начального адреса таблицы, хранящегося в регистре, и значения S. Если сегмент отсутствует в памяти (pr = 0), то генерируется соответствующее
прерывание и вызывается программа подкачки сегмента (свопинг).
На втором этапе определяется значение физического адреса путем
сложения значений A и I. Перед выполнением этой операции выполняется проверка условия I <= R. Если это условие выполняется (физический адрес определяется корректно и не выходит за адресуемый
31
сегмент), то определение физического адреса внутри страницы разрешается. В противном случае генерируется соответствующее прерывание, и адресация к странице откладывается.
Рассмотрим свойства сегментной организации памяти. Вопервых необходимо отметить, что загружаемым в память объектом является сегмент некоторой задачи, а не ее код целиком. Кроме
того, при данной организации памяти обеспечивается автоматическое перекрытие сегментов в памяти (на место в памяти, где хранился некоторый сегмент, возможна загрузка нового необходимого
сегмента). Уровень фрагментации памяти может быть достаточно
высоким. Это связано с тем, что при перекрытии сегментов в памяти могут образовываться значительные по размеру незаполненные
области памяти из-за разных размеров сегментов.
3.4. Страничная организация памяти
Страничная организация памяти – это еще один из способов организации виртуальной памяти. Транслятор подготавливает задачу в виде совокупности виртуальных страниц одинакового размера. Эти страницы хранятся во внешней памяти. Адресация внутри
страниц носит непрерывный характер. Виртуальные адреса после
трансляции имеют вид – (p, i), где p – виртуальный номер страницы, а i – смещение относительно начала страницы. Предполагается,
что в общем случае, при первоначальной загрузке страниц задачи
в ОП, не все из них могут попасть в нее, и часть страниц задачи может остаться во внешней памяти. Физическая память рассматривается как совокупность физических страниц того же размера, как и
размер виртуальных страниц. Отображение виртуальных адресов
в физические происходит на этапе выполнения задачи (см. рис. 9).
При загрузке задачи в ОП ОС, совместно с аппаратурой, создает в памяти таблицу дескрипторов страниц задачи. Первоначально
дескрипторы страниц задачи создаются на этапе ее трансляции.
Каждый дескриптор имеет поля, содержимое которых может изменяться во время выполнения задачи. Некоторые из них показаны на
рис. 9: Pr – битовый признак присутствия-отсутствия страниц в ОП
(0 – сегмент отсутствует в памяти, 1 – сегмент присутствует в памяти); F – физический номер страницы.
В специальном регистре процессора хранится значение начального
адреса таблицы дескрипторов страниц выполняемой задачи. При переключении на выполнение новой задачи ОС меняет содержимое этого
регистра. Отображение виртуальных адресов в физические адреса
32
Регистр начального адреса
таблицы страниц текущей
выполняемой задачи
P
I
Страница
Таблица дескрипторов
страниц
+
Pr
F
//
Рис. 9
производится в два этапа. На первом этапе определяется адрес конкретного дескриптора в таблице путем сложения начального адреса
таблицы, хранящегося в регистре, и значения P. Если страница отсутствует в памяти (pr = 0), то генерируется соответствующее прерывание
и вызывается программа подкачки страницы (свопинг). На втором
этапе определяется значение физического адреса внутри страницы путем реализации операции приписывания (//). Данная операция может
быть представлена в виде F × L + I, где L – размер страницы. Поскольку
умножение выполняется медленно, значение L выбирается кратным
степени двойки. В этом случае умножение заменяется на быструю операцию «сдвиг влево» на число разрядов, равное степени двойки.
Рассмотрим свойства страничной организации памяти. Прежде
всего необходимо отметить, что загружаемым в память объектом
является страница некоторой задачи, а не ее код целиком. Кроме
того, при данной организации памяти обеспечивается автоматическое перекрытие страниц в памяти (на место в памяти, где находилась некоторая страница, возможна загрузка новой необходимой
страницы). Уровень фрагментации памяти при страничной организации значительно ниже, чем при сегментной организации памяти.
Но для страничной организации памяти характерна внутренняя
фрагментация. Внутренняя фрагментация памяти образуется изза незаполненности последней страницы кода задачи. В среднем,
33
последняя страница задачи не заполнена полезным кодом на 50%.
Поэтому важным вопросом является выбор значения размера страниц. Выбор размера страниц основывается на двух противоречивых
соображениях. Чем больше размер страницы, тем выше уровень
внутренней фрагментации. С другой стороны, если размер страницы делать небольшим, увеличивается интенсивность свопинга, что
может значительно увеличить время выполнения отдельных задач
и понизить эффективность работы вычислительной системы в целом. Поэтому размеры страниц выбираются в пределах:
8
2=
<
L=
<
12
2 áàéò.
3.5. Свопинг. Стратегии свопинга
Свопинг (swapping) – это необходимый механизм при организации
виртуальной памяти, так как с его помощью реализуется автоматическое перекрытие страниц или сегментов в ОП. Своппинг состоит из
двух процедур – процедуры подкачки страниц (сегментов) из внешней
памяти в оперативную, и процедуры откачки страниц (сегментов) из
ОП во внешнюю. Для этого ОС выделяет специальную область внешней памяти, где могут храниться временно откачанные страницы или
сегменты задач. Существуют различные стратегии (дисциплины) подкачки и откачки, которые требуют специального рассмотрения.
Стратегии подкачки. Принципиально могут рассматриваться
только два метода подкачки необходимых страниц (сегментов) – это
опережающая подкачка и подкачка по требованию.
Опережающая подкачка основывается на том, что поведение программ при их выполнении можно предсказать. Следовательно, можно
заранее определить – какие страницы или сегменты задачи необходимо сразу загрузить в ОП. В действительности поведение программ
в подавляющем большинстве случаев непредсказуемо. Поэтому идея
опережающей подкачки не нашла практического воплощения.
Подкачка по требованию состоит в загрузке необходимой страницы (сегмента), когда к данной странице произошло фактическое
обращение. Данная стратегия реализуется относительно просто, но
при этом она способствует увеличению интенсивности свопинга,
что является недостатком стратегии.
Стратегии откачки (вытеснения). Откачка страниц необходима, когда в ОП отсутствуют свободные физические страницы. В этом
случае необходимо выбрать занятую физическую страницу для ее откачки во внешнюю память. Существует доказанное положение: что
34
прежде всего необходимо откачивать такую страницу, следующее
обращение к которой будет нескоро. На основе данного положения
были реализованы различные стратегии откачки, отличающиеся
друг от друга сложностью реализации и показателями качества.
Случайная откачка предполагает случайный выбор страницы
для откачки. Данная стратегия проста в реализации, но плохо согласуется с указанным положением. При случайной откачке слишком часто будут откачиваться нужные страницы.
FIFO – «первым подкачан – первым откачан». При данной стратегии прежде всего откачивается та страница, которая дольше
остальных находится в оперативной памяти. Если обращения к памяти носят последовательный характер, то откачиваемая страница
становится ненужной на достаточно длительный период времени.
Тем не менее при такой стратегии часто удаляются нужные страницы. Основным достоинством FIFO является простота реализации,
так как планировщику памяти достаточно следить за очередью физических страниц, упорядоченных по времени подкачки.
LRU (least recently used) – определяет факт давности использования страниц, т. е. прежде всего откачивается та страница, к которой
не было обращений в течение некоторого интервала времени. Данная
стратегия дает хорошие результаты, но сложна в реализации. Сложность реализации объясняется тем, что ОС совместно с аппаратурой
должна создавать и оперативно изменять список страниц, к которым
не было обращений в течение некоторого заданного интервала времени.
LFU (least frequently used) – определяет факт частоты использования страниц, т. е. прежде всего откачивается та страница, к которой было меньше всего обращений за заданный интервал времени.
Планировщик, однако, не должен учитывать страницы, которые
были подкачаны в память только что. Иначе такие страницы станут первыми кандидатами на откачку. Данная стратегия также достаточно сложна в реализации, но дает хорошее качество с точки
зрения ранее указанного положения.
Механизм свопинга необходим при организации виртуальной
памяти, но так как при своей реализации он требует значительного
времени (обмен с внешней памятью) желательно минимизировать
его использование.
3.6. Сегментно-страничная организация памяти
При сегментно-страничной организации памяти транслятор
подготавливает задачу как совокупность виртуальных сегментов,
35
в общем случае, разной длины. Каждый виртуальный сегмент состоит из целого числа виртуальных страниц одинакового размера.
Виртуальные адреса представляют собой тройки типа (s, p, i), где
s – задает виртуальный номер сегмента; p – виртуальный номер
страницы внутри сегмента; i – смещение относительно начала
страницы. Физическая память представляется как совокупность
физических страниц той же длины, что и виртуальные, поэтому
загружаемой в память единицей является страница. При загрузке
очередной задачи в ОП операционная система совместно с аппаратурой заводит в памяти таблицу дескрипторов сегментов задачи,
а для каждого такого сегмента – таблицу дескрипторов страниц.
При активизации задачи в специальный регистр процессора заносится начальный адрес соответствующей таблицы дескрипторов
сегментов. Другими словами, в этом регистре всегда находится
значение адреса таблицы дескрипторов сегментов той задачи, которая выполняется в данный момент времени. Схема отображения
виртуальных адресов в физические адреса во время выполнения
программы представлена на рис. 10.
Регистр таблицы
дескрипторов сегментов
текущей выполняемой
задачи
S
+
+
Таблица
дескрипторов
сегментов задачи
A
L
//
Таблица
дескрипторов
страниц
сегмента
Pr
Рис. 10
36
I
P
F
Страница
Здесь А – начальный адрес таблицы деY
X
скрипторов страниц сегмента с виртуальным номером S; L – размер сегмента в страниKey
цах; Pr – признак присутствия / отсутствия
страницы в памяти; F – физический номер
страницы. Отображение виртуальных адресов в физические адреса производится в три
этапа – обращение к соответствующей таблице дескрипторов сегментов с целью
Рис. 11
определение нужного дескриптора сегмента, обращение к таблице дескрипторов страниц для определения необходимого дескриптора страницы и обращение к соответствующей
физической странице путем выполнения операции приписывания.
Такая схема отображения реализуется недостаточно быстро, поэтому
используется дополнительный механизм отображения – ассоциативная (кэш) память.
Ассоциативная память – это память, выборка из которой осуществляется по значению некоторого подаваемого на вход ключа, а
не по адресу, как это делается обычно. Каждая ячейка такой памяти состоит из двух полей – поля аргумента (X) и поля функции (Y).
При ее использовании параллельно на вход всех ячеек посылается
значение ключа (Key). Если значение ключа совпадает со значением
аргумента, на выходные шины памяти выдается значение функции
(см. рис. 11).
Если использовать ассоциативную память как дополнительный
механизм применительно к сегментно-страничной организации памяти, то в качестве аргумента и функции имеет смысл использовать
следующие соотношения:
X = (S, P), Y = F.
В этом случае пара (S, P) однозначно определяет виртуальную
страницу в сегменте, а F задает номер соответствующей физической
страницы.
Для того чтобы понять, как механизм ассоциативной памяти дополняет основную схему отображения виртуальных адресов в физические адреса, представим следующую ситуацию. Производится
первое обращение к некоторой странице. В этом случае срабатывает
основная схема определения физического адреса. Но одновременно
в ячейку ассоциативной памяти занесутся соответствующие значения аргумента и функции. Вероятность того, что следующее обращение будет к той же самой странице очень велика. И, если это так,
37
то при следующем обращении сработает механизм ассоциативной
памяти, определится значение F, затем быстро реализуется операция приписывания и определится значение физического адреса.
Пока будут происходить обращения к данной странице, будет срабатывать быстрый механизм ассоциативной памяти. При обращении к новой странице, аргумент и функция которой не прописаны
в ассоциативной памяти, будет срабатывать основная схема определения физического адреса внутри страницы.
Ассоциативная память имеет относительно небольшой размер,
поэтому возможна ситуация, когда в памяти нет незаполненных
ячеек, а произошло обращение к новой странице. В этом случае необходимо решать задачу замещения ячеек ассоциативной памяти.
Данная задача решается на основе использования дисциплины замещения LFU, то есть выбирается для замещения та ячейка памяти, в которой хранится информация (значения аргумента и функции) о странице с наименьшей частотой обращения за некоторый
период времени.
Выводы
1. При мультипрограммном режиме функция распределения ОП
между активными задачами взаимосвязана с функцией ее защиты
от несанкционированного обращения.
2. Задачу распределения оперативной памяти можно трактовать
как задачу отображения символьного кода задачи на некотором
языке программирования на физические адреса памяти.
3. Для дисциплин распределения памяти разделами предполагается, что код задачи после трансляции представляет собой единый
блок, а физические адреса команд и операндов задачи определяются до начала ее выполнения и остаются постоянными на все время
выполнения.
4. Современными методами организации ОП являются методы,
основанные на использовании виртуальной памяти, где код программы состоит из нескольких компонент (сегменты, страницы),
а исполнительный адрес определяется во время выполнения программы.
5. Организация виртуальной памяти возможна только при использовании свопинга, как необходимого механизма подкачки-откачки страниц или сегментов, с целью выполнения активных задач.
6. Основную работу по распределению ОП выполняет планировщик памяти – важнейшая компонента ОС.
38
7. Функционирование планировщика памяти тесно взаимосвязано с работой процессора, в частности, при организации сегментно-страничного метода организации ОП. В этом случае активно используется кэш-память процессора с целью ускорения определения
исполнительных адресов команд и операндов.
Контрольные вопросы
1. Что такое коэффициент мультипрограммирования?
2. Какая стратегия распределения разделами является оптимальной с точки зрения минимизации уровня фрагментации?
3. Как используется виртуальный номер сегмента при отображении виртуальных адресов в физические?
4. Какая величина хранится в специальном регистре процессора
при отображении виртуальных страниц в физические?
5. Что является загружаемым в память объектом при сегментностраничной организации памяти?
6. Какие значения должны содержать поле аргумента и поле
функции в ячейке кэш-памяти, как дополнительный механизм сегментно-страничной организации памяти?
39
4. МЕТОДЫ СИНХРОНИЗАЦИИ
ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ
4.1. Проблемы синхронизации параллельных процессов
Функционирование мультипрограммной вычислительной системы характерно тем, что в ее среде одновременно развиваются
несколько параллельных процессов. В своем развитии параллельные процессы часто используют одни и те же ресурсы системы, т. е.
разделяют их. Часть таких разделяемых ресурсов требуют только
последовательного использования со стороны процессов, т. е. в каждый момент времени только один процесс может использовать разделяемый ресурс. Такие ресурсы называются критическими. Для
того чтобы обеспечить последовательное использование критических ресурсов необходимо синхронизировать доступ к ним.
Задача синхронизации в общем случае состоит в следующем.
Если несколько процессов хотят пользоваться критическим ресурсом в режиме разделения, им следует синхронизировать свои действия таким образом, чтобы такой ресурс всегда находился в распоряжении не более чем одного из них. Если один процесс пользуется
в данный момент критическим ресурсом, то все остальные процессы, которым нужен этот ресурс, должны получить отказ в доступе
и ждать, пока он не освободится. Если в системе не предусмотрена
защита от одновременного доступа процессов к критическим ресурсам, в ней могут возникать ошибки, которые трудно обнаружить и
исправить. Основной причиной возникновения таких ошибок является то, что процессы развиваются с разными скоростями, причем эти скорости самим процессам неподвластны и неизвестны друг
другу. Рассмотрим несколько примеров, как отсутствие синхронизации при доступе к критическим ресурсам влияет на результаты
выполнения процессов.
Пусть два конкурирующих процесса Р1 и Р2 асинхронно увеличивают значение общей переменной Х, предварительно считывая ее
значение в свои локальные области памяти R1 и R2.
Р1: (1) R1:=X; (2) R1:=R1+1; (3) X:=R1;
P2: (4) R2:=X; (5) R2:=R2+1; (6) X:=R2;
Поскольку процессы Р1 и Р2 могут иметь различные скорости
выполнения, то может иметь место любая последовательность выполнения операций во времени. Например, если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы
40
одна из операций 4–6, то значение переменной Х будет не (Х + 2),
а (Х + 1). Если предположить, что процессы Р1 и Р2 осуществляли продажу билетов, и переменная Х фиксировала количество уже
проданных билетов, то в результате некорректного взаимодействия
было бы продано несколько билетов на одно и то же место.
В качестве второго примера приведем пару процессов, которые
изменяют различные поля записей служащих какого-либо предприятия. Процесс АДРЕС изменяет домашний адрес служащего, а
процесс СТАТУС – его должность и зарплату. Каждый процесс копирует всю запись в свою рабочую область памяти. Пусть каждый
процесс должен обработать запись ИВАНОВ. Предположим, что
после того как процесс АДРЕС скопировал запись ИВАНОВ в свою
рабочую область, но до того, как он записал скорректированную запись обратно, процесс СТАТУС скорректировал первоначальную запись ИВАНОВ в свою рабочую область. Изменения, выполненные
тем из процессов, который первым запишет скорректированную запись назад в файл СЛУЖАЩИЕ, будут потеряны и, возможно, никто не будет знать об этом.
Чтобы предотвратить некорректное исполнение конкурирующих
процессов вследствие нерегламентированного доступа к разделяемым
переменным, необходимо ввести такое понятие как взаимное исключение, которое не позволит двум или более процессам параллельно обращаться к разделяемым переменным. Кроме реализации в ОС средств,
организующих взаимное исключение, в ней должны быть средства,
синхронизирующие работу взаимодействующих процессов. Использование таких средств позволит взаимодействующим процессам корректно обмениваться данными, чтобы правильно выполнялась их общая
работа. Типичным примером взаимодействующих процессов, использующих разделяемые ресурсы, является задача ПОСТАВЩИК – ПОТРЕБИТЕЛЬ. Решение данной задачи будет рассмотрено далее.
Таким образом, при организации различного рода взаимодействующих процессов необходимо решать проблему корректного
доступа к общим переменным, которые идентифицируют критические ресурсы с программной точки зрения. Те места в программах,
в которых происходит обращение к критическим ресурсам, называются критическими интервалами или критическими секциями
(critical section). Решение этой проблемы заключается в организации такого доступа к критическому ресурсу, когда только одному
процессу разрешается входить в свою критическую секцию.
Когда какой-либо процесс находится в своем критическом интервале, другие процессы могут продолжать свое выполнение, но без входа
41
в свои критические секции. Взаимное исключение необходимо только в том случае, когда процессы обращаются к разделяемым, общим
данным. Если же процессы выполняют операции, которые не приводят к конфликтным ситуациям, они должны иметь возможность выполняться параллельно. Когда процесс выходит из своего критического интервала, то одному из остальных процессов, ожидающих входа
в свои критические секции, должно быть разрешено продолжить выполнение, т. е. разрешено войти в свой критический интервал.
Задача взаимного исключения может быть сформулирована следующим образом:
– в любой момент времени только один процесс должен находиться в своей критической секции;
– ни один процесс не должен находиться в своей критической секции бесконечно долго;
– ни один процесс не должен бесконечно долго ждать входа в свою
критическую секцию.
Процесс, находящийся вне своей критической секции, не должен блокировать выполнение других процессов, ожидающих входа в свои критические интервалы. Если два процесса одновременно
хотят войти в свои критические интервалы, то принятие решения о
том, кто из них должен это сделать, не должно бесконечно откладываться. Если процесс, находящийся в своем критическом интервале, завершается естественным или аварийным путем, режим взаимоисключения должен временно отменяться для того, чтобы один
из других процессов смог войти в свою критическую секцию.
Для решения проблемы синхронизации параллельных процессов было предложено множество различных подходов, которые стали основой для программно-аппаратных средств из состава современных ОС.
4.2. Синхронизация параллельных процессов
с помощью команды «Проверка и установка»
Команда «Проверка и установка» входит в состав системы команд компьютеров, имеющих различные архитектуры. Данная
команда имеет аббревиатуру TS или TAS (test and set) и имеет два
операнда. При выполнении команды последовательно реализуются два действия: сначала значение второго операнда присваивается
первому операнду, а затем второй операнд устанавливается в единицу. Команда TS является неделимой операцией, т. е. ее выполнение
не может быть прервано. Рассмотрим решение задачи взаимного ис42
ключения с помощью команды TS на примере двух параллельных
процессов. Описание решения приводится в нотации языка параллельный Pascal.
Var common, local1, local2;
Begin
Common:=0;
Parbegin
P1: while true do
Begin
…
local1:=1;
while local1=1 do TS(local1, common);
CS1;
Common:=0;
…
End;
And
P2: while true do
Begin
…
local2:=1;
while local2=1 do TS(local2, common);
CS2;
Common:=0;
…
End;
Parend
End.
Ключевые слова parbegin и parend означают, что между ними
имеется описание параллельных процессов. Ключевое слово and означает связку между описаниями конкретных параллельных процессов. Бесконечный цикл while true do означает, что процесс выполняется неопределенное время.
Переменная common является общей для процессов Р1 и Р2. Ее
первоначальное значение равно нулю. Предположим, что первым
начнет выполняться процесс Р1. Перед тем как войти в свою критическую секцию (CS1), он установит свою переменную local1 в единицу и войдет в цикл while. Этот цикл Р1 выполнит один раз, так как
начальное значение common равнялось нулю. При выполнении цикла common установится в единицу (см. действия команды TS). Затем
43
Р1 войдет в свой критический интервал (CS1). Если в этот момент
управление получит Р2 и захочет войти в свой критический интервал (CS2), то он сначала установит свою переменную local2 в единицу, а затем войдет в цикл while и зациклится здесь (см. действия
команды TS). Если через некоторое время управление получит Р1 и
выполнит свой критический интервал до конца, а также установит
common в ноль, процесс Р2 при получении управления сможет войти в свой критический интервал. Другими словами, пока один из
процессов находится в своем критическом интервале, другой процесс не может войти в свой критический интервал, т. е. задача взаимного исключения решается.
Основным недостатком предложенного решения является эффект «активного ожидания». Активное ожидание проявляется
в том, что процессы, выполняя цикл while (ожидая разрешения на
вход в свой критический интервал), впустую потребляют процессорное время.
4.3. Семафорные примитивы Дейкстры
Семафор – это переменная специального типа, над которой определены две операции – закрытие семафора (P) и открытие семафора
(V). Обобщенный смысл операции Р состоит в декрементации числового поля семафора и в проверке значения этого поля семафора. Если
это значение оказывается меньше некоторой величины (чаще всего
нуля), процесс, вызвавший данную операцию, блокируется и помещается в очередь к семафору.В противном случае процесс продолжает свое выполнение. Операция V связана с инкрементацией числового поля семафора. При этом, если выполняется некоторое условие,
один из ранее заблокированных процессов деблокируется, т. е. покидает очередь к семафору и переходит в состояние готовности. Обычно
семафор логически связывается с некоторым критическим ресурсом.
Поэтому заблокированные процессы, находящиеся в очереди к семафору, косвенно ожидают доступа к критическому ресурсу.
Операции P и V являются неделимыми операциями, т. е. их выполнение не может прерываться. Действия по блокированию и деблокированию процессов реализуют модули из состава ядра ОС.
Допустимыми значениями числовых полей семафоров являются
целые числа. Различают два вида семафоров – числовые и двоичные. Числовые семафоры – это семафоры, числовые поля которых
могут принимать любые целые значения в некотором заданном диапазоне. Двоичные семафоры – это семафоры, числовые поля кото44
рых могут принимать только два значения: единица и ноль. Существуют различные реализации семафорных примитивов. Они отличаются друг от друга по различным параметрам (тип семафоров,
диапазон изменения значений числовых полей семафоров, логика
операций, дисциплина выбора процесса при его деблокировании и
т. д.). Рассмотрим некоторые алгоритмы работы семафорных примитивов. Сначала представим вариант алгоритма реализации операций P и V для числовых семафоров:
P(S):
V(S):
S:=S-1;
If S<0 then <заблокировать процесс, и поместить
его в очередь к семафору>
S:=S+1;
If S<=0 then <деблокировать один из ранее заблокированных
процессов>
Алгоритм работы семафорных примитивов P и V для двоичных
семафоров может выглядеть следующим образом:
P(S):
V(S):
if S=1 then begin S:=0; L:=0 end
Else
Begin
L:=L+1;
<заблокировать процесс>;
End;
if (S=0) and (L>0) then
Begin
<деблокировать один из процессов>;
L:=L-1;
End;
If L=0 then S:=1;
Здесь L – длина очереди заблокированных процессов.
Решение задачи взаимного исключения с помощью семафорных
примитивов для двух параллельных процессов можно представить
следующим образом:
Var s: semaphor;
Begin s:=1;
Parbegin
P1: while true do begin
… P(s); CS1; V(s); …
45
end;
and
P2: while true do begin
… P(s); CS2; V(s); …
end;
parend
end.
Предположим, что первым начнет выполняться процесс Р1. Прежде чем войти в свой критический интервал (CS1), он вызовет операцию P(s). После ее выполнения значение числового поля семафора станет равным нулю, но Р1 войдет в свой критический интервал.
Если в этот момент процесс Р2 получит управление и захочет войти
в свой критический интервал (CS2), он сначала вызовет выполнение
операции P(s) и заблокируется по семафору s. Если через некоторое время процесс Р1 опять получит управление и выполнит свой
критический интервал до конца, а также вызовет операцию V(s),
процесс Р2 деблокируется и сможет войти в свой критический интервал. Задача взаимного исключения будет решена, так как только один из двух процессов будет находиться в своем критическом
интервале.
Использование семафорных примитивов для решения задач синхронизации имеет значительное достоинство: в случае блокировки
процессы попадают в состояние пассивного ожидания, не требуя использования процессорного времени.
4.4. Задача «Поставщик – Потребитель»
Взаимодействуют два процесса – Поставщик и Потребитель.
Поставщик создает сообщения и записывает их в пул буферов (для
каждого сообщения свой буфер). Потребитель считывает сообщения
из пула буферов для дальнейшего анализа и обработки. Параллельные действия по записи в пул и чтению из него запрещены. Пул буферов имеет конечную размерность. Поэтому оба процесса должны
корректно изменять число свободных и занятых буферов в пуле,
как при записи очередного сообщения, так и при его считывании из
пула. Решение данной задачи, основанное на использовании семафорных примитивов, представлено далее:
Const N=100;
Var
S, SS, SN: semaphore;
46
Begin
S:=1; SS:=0; SN:=N;
Parbegin
Поставщик:
while true do begin
… { генерация собщения}
P(SN); P(S);
… {запись сообщения}
V(SS); V(S);
End;
And
Потребитель: while true do begin
P(SS); P(S);
…{ чтение сообщения}
V(SN);
V(S);
… {обработка сообщения}
End;
Parend
End.
Здесь N – число буферов в пуле; S – двоичный семафор, используемый для регулирования доступа к пулу буферов, как при записи,
так и при считывании; SS и SN – числовые семафоры, используемые
как счетчики числа занятых и свободных буферов в пуле соответственно.
Для того чтобы понять представленное решение рассмотрим несколько возможных ситуаций развития взаимодействующих процессов.
Пусть пул буферов частично занят (числовые поля SS и SN имеют
целые положительные значения), и управление получает Поставщик. Он создаст новое сообщение, последовательно выполнит P(SN)
и P(S) и начнет запись. Если в этот момент управление получит Потребитель, то он выполнит P(SS), затем P(S) и здесь заблокируется
по семафору S. Потребитель сможет деблокироваться только после
того, как Поставщик закончит запись и выполнит операцию V(S).
Другими словами, пока очередная запись в пул не закончена чтение
из пула невозможно, и наоборот.
Пусть пул буферов пуст, а управление получил Потребитель. Он
выполнит операцию P(SS) и тут же заблокируется по семафору SS
(числовое поле семафора SS к этому моменту равнялось нулю). Другими словами, чтение из пула запрещено, если он не содержит сообщений.
47
Пусть пул буферов полностью заполнен сообщениями, а управление получил Поставщик. Он выполнит операцию P(SN) и заблокируется по семафору SN (значение числового поля семафора SN к этому моменту будет равняться нулю). Другими словами, запись в пул
запрещается, если он полностью заполнен сообщениями.
4.5. Задача «Читатели – Писатели»
Некоторая база данных используется двумя типами параллельных процессов – Читателями и Писателями. Читатели считывают
информацию из базы данных, а Писатели модифицируют содержимое базы данных. Модификация содержимого базы данных должна
выполняться в монопольном режиме, т. е. если некоторый Писатель
получил доступ к базе, то остальные Писатели и Читатели должны
ждать до тех пор, пока этот Писатель закончит свои действия с базой
данных. Читатели относительно друг друга могут считывать информацию из базы параллельно, но при этом любая запись в базу должна
быть запрещена. Далее представлено решение данной задачи, основанное на использовании семафорных примитивов.
Var S, W : semaphore;
count_r: integer;
Procedure Reader;
Begin
P(S); count_r:=count_r+1;
If count_r=1 then P(W);
V(S);
Read_DB;
P(S); count_r:=count_r-1;
If count_r=0 then V(W);
V(S);
End;
Procedure Writer;
Begin
P(W); write_DB; V(W);
End;
Begin
S:=1; W:=1; count_r:=0;
End.
При доступе к базе данных Читатели используют процедуру
Reader, а Писатели процедуру Writer. Здесь W – двоичный сема48
фор, используемый для регулирования доступа к базе; S – двоичный семафор, используемый для корректного доступа к переменной
count_r; count_r – счетчик параллельно выполняемых Читателей.
Монопольность записи в базу обеспечивается следующим образом. Предположим, что для некоторого Писателя осуществляется
запись в базу (write_DB), и в этот момент управление получит другой Писатель. Для него, при выполнении процедуры Writer, сначала выполнится оператор P(W), и этот Писатель заблокируется по
семафору W. Следующие Писатели будут также блокироваться по
семафору W. Если же в этот момент управление получит Читатель,
то для него последовательно выполнятся операции P(S), инкрементация счетчика читателей и по условию (count_r = 1) операция P(W)
(см. процедуру Reader). Здесь Читатель заблокируется по семафору
W. Следующие Читатели будут блокироваться по семафору S.
Обеспечение параллельности чтения с одновременным запретом
на запись в базу можно представить следующим образом. Предположим, некоторый Читатель занимается чтением из базы (read_DB), и
в этот момент управление получает новый Читатель. Он также сможет выполнять свои действия по чтению содержимого базы данных
(см. текст процедуры Reader). Если же в этот момент управление
получит Писатель, то для него выполнится операция P(W), и Писатель заблокируется по семафору W, так как для первого Читателя
операция P(W) уже выполнялась. Модификация содержимого базы
данных сможет возобновиться только после того, когда закончит
чтение последний из параллельно выполняемых Читателей (см. условие count_r = 0 в процедуре Reader). Для того чтобы обновление
базы данных происходило быстрее, Писатели имеют более высокий
приоритет по сравнению с Читателями, т. е. при выполнении операции V(W), прежде всего, деблокируются Писатели.
Тем не менее при интенсивном потоке запросов на чтение, обновление базы данных может значительно задерживаться во времени,
что является недостатком представленного решения задачи. Рассмотрим решение, свободное от указанного недостатка.
Var S, W, R : semaphore;
count_r: integer;
Procedure Reader;
Begin
P(R); P(S); counr_r:=counr+1;
If count_r=1 then P(W);
V(S); V(R);
49
read_DB;
P(S); countr:=count_r-1;
If count-r=0 then V(W);
V(S);
End;
Procedure Writer;
Begin
P(R); P(W); write_DB; V(W); V(R);
End;
Begin
S:=1; W:=1; R:=1; count_r:=0;
End.
Для данного решения характерно использование еще одного двоичного семафора R. Предположим, что N Читателей занимаются
чтением содержимого базы данных, т. е. каждый из них находится
в некоторой точке вычислений комплекса действий, определенных
как read_DB. В этот момент управление получает Писатель, и для
него начинает выполняться процедура Writer. Сначала выполнится
операция P(R), а затем P(W), и Писатель заблокируется по семафору
W, так как первый из Читателей уже выполнял эту операцию. Если
далее управление получит N+1-й Читатель, то для него выполнится
операция P(R), и он заблокируется по семафору R. После того как
первые N Читателей закончат чтение, последний из них выполнит
операцию V(W), и ранее заблокированный Писатель деблокируется
и сможет модифицировать содержимое базы данных. Другими словами, с помощью семафора R временно блокируется поток запросов
на чтение, что способствует ускорению обновления содержимого
базы данных.
4.6. Задача с ожиданием
Содержательная постановка задачи состоит в следующем. Для
того чтобы первый процесс Р1 смог выполнить свою работу целиком,
он должен передать управление второму процессу Р2 и дождаться
его окончания. Решение такой задачи с помощью семафорных примитивов может выглядеть следующим образом:
Var S: semaphore;
Begin
S:=0;
50
Parbegin
P1:
…
And
P2:
Parend
End.
…
Exec(P2);
P(S);
…
V(S);
При решении используется двоичный семафор S, причем, начальное значение числового поля этого семафора равняется нулю.
После того как Р1 выполнит часть своих действий, он инициирует
запуск процесса Р2 с помощью директивы Exec. Если Р1 далее продолжит свое выполнение, то после реализации операции P(S), он заблокируется по семафору S. Р1 сможет деблокироваться и продолжить свое выполнение только после того, как Р2 выполнит все свои
действия и операцию V(S).
4.7. Почтовые ящики
Почтовые ящики относятся к высокоуровневым средствам организации взаимодействий между параллельными процессами. Почтовые ящики предназначены для хранения и передачи сообщений
между взаимодействующими процессами. Для хранения посланного, но еще не полученного сообщения, необходимо выделить некоторый буфер в памяти, он будет исполнять роль почтового ящика.
Если процесс Р1 хочет общаться с процессом Р2, то Р1 просит ОС образовать почтовый ящик, который свяжет эти два процесса так, чтобы
они могли передавать друг другу сообщения. Для того чтобы послать
процессу Р2 какое-то сообщение, процесс Р1 просто помещает это сообщение в почтовый ящик, откуда процесс Р2 может его взять в любое
время. При использовании почтового ящика процесс Р2 в конце концов обязательно получит сообщение, когда обратится за ним.
Если объем передаваемых данных велик, то эффективнее не передавать их непосредственно, а отправлять в почтовый ящик сообщение, информирующее процесс «получатель» о том, где их можно
найти (адресная ссылка).
Почтовый ящик может быть связан только с парой процессов (отправитель и получатель), а может быть связан и с большим числом
51
процессов. Почтовый ящик, связанный только с процессом «получатель», облегчает посылку сообщений от нескольких процессов
в фиксированный пункт назначения. Если почтовый ящик не связан
с конкретными процессами, то сообщение должно содержать идентификаторы отправителя и получателя.
Почтовый ящик – это информационная структура, поддерживаемая ОС. Она состоит из головного элемента (заголовка), в котором находится информация о характеристиках почтового ящика, и
из нескольких буферов (гнезд), в которые помещаются сообщения.
Размер каждого гнезда и количество гнезд обычно задаются при образовании почтового ящика.
Правила работы почтовых ящиков могут быть разные в зависимости от их сложности. В простейшем случае сообщения передаются
только в одном направлении. Процесс Р1 может посылать сообщения
до тех пор, пока имеются свободные гнезда. Если все гнезда заполнены, то процесс Р1 вынужден ждать, когда хотя бы одно из гнезд
освободится. Аналогично, процесс Р2 может получать сообщения до
тех пор, пока имеются заполненные гнезда. Если сообщений нет в почтовом ящике, Р2 будет ждать их появлений. Такие почтовые ящики
называются однонаправленными. Реализацией однонаправленного
почтового ящика является решение задачи «Поставщик – Потребитель».
Двунаправленный почтовый ящик, связанный с парой процессов, используется для подтверждения сообщений. Если используется
множество гнезд, то каждое из них может хранить либо сообщение,
либо подтверждение (ответ). Чтобы гарантировать передачу подтверждений, когда все гнезда заняты, подтверждение на сообщение
помещается в то же гнездо, которое использовалось для хранения сообщения, и оно уже не используется для хранения другого сообщения до тех пор, пока подтверждение не будет получено. Из-за того, что
некоторые процессы не забрали свои сообщения, связь может быть
приостановлена. Если каждое сообщение снабдить пометкой времени
появления в почтовом ящике, то системная управляющая процедура
может уничтожать старые сообщения и освобождать гнезда. Процессы могут быть также остановлены в связи с тем, что другие процессы
не смогли послать им сообщения или подтверждения. Если время поступления сообщений в почтовый ящик регистрируется, то управляющая процедура может периодически посылать процессам пустые
сообщения или подтверждения, чтобы они не ждали слишком долго.
При реализации почтовых ящиков используются низкоуровневые средства, например – семафорные примитивы и т. п.
52
Рассмотрим интерфейс операций с двунаправленным почтовым
ящиком, которые могут использовать процессы при своем взаимодействии:
1. Send_message (receiver, message, buffer) – посылка сообщения
(message) получателю (receiver) через почтовый ящик (buffer). Процесс, выдавший данную операцию, продолжает свое выполнение.
2. Wait_message (sender, message, buffer) – процесс, выдавший
данную операцию ждет до тех пор, пока в почтовом ящике не появится сообщение от отправителя (sender) и не перепишется в собственную память получателя (message).
3. Send_answer (result, answer, buffer) – записывает ответ (answer)
в тот буфер, в который было записано сообщение.
4. Wait_answer (result, answer, buffer) – блокирует процесс, выдавший данную операцию, до тех пор, пока в почтовом ящике не появится
ответ и не перепишется в собственную память процесса (answer). Значение переменной result определяет, каков ответ: от процесса «получатель» или пустой от ОС.
Совокупность представленных операций с двунаправленным почтовым ящиком позволяет организовать различные варианты взаимодействия двух или более процессов. Почтовые ящики удобны
для обмена сообщениями, но их затруднительно использовать для
решения задачи взаимоисключения при доступе к критическим ресурсам.
4.8. Мониторы Хоара
Монитор – это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причем в каждый момент времени им
может пользоваться только один процесс. Монитор можно представить как комнату, от которой есть только один ключ. Если какой-то
процесс намеревается воспользоваться этой комнатой и ключ находится снаружи, то этот процесс может отпереть комнату, войти
в нее и воспользоваться одной из процедур монитора. Если ключа
снаружи нет, то процессу придется ждать, пока тот, кто пользуется комнатой в данный момент, не выйдет из нее и не отдаст ключ.
Кроме того, никому не разрешается в комнате оставаться навсегда.
Рассмотрим, например, некоторый ресурс, который выделяет соответствующий планировщик. Каждый раз, когда процесс желает
получить этот ресурс, он должен обратиться к планировщику. Процедуру «планировщик» разделяют все процессы, и каждый из них
53
может обратиться к планировщику в любой момент. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура «планировщик» представляет собой пример
монитора.
Таким образом, монитор – это механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для динамического распределения конкретного общего ресурса или группы общих ресурсов. Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору,
который либо предоставит доступ, либо откажет в нем. Вход в монитор находится под жестким контролем – здесь осуществляется
взаимоисключение процессов, так как в каждый момент времени
только один процесс может пользоваться монитором. Процессам,
которые хотят войти в монитор, когда он уже занят, приходится
ждать, причем режимом ожидания управляет сам монитор. При
отказе в доступе монитор блокирует обратившийся к нему процесс
и определяет условие, по которому процесс ждет. Проверка условия выполняется самим монитором, который и деблокирует ожидающий процесс.
Внутренние переменные монитора могут быть либо глобальными (используемыми всеми процедурами монитора), либо локальными (используемыми только в своих процедурах). Обращение к этим переменным возможно только изнутри монитора. При
первом обращении к монитору инициализируются начальные
значения переменных. При последующих обращениях используются те значения переменных, которые остались от предыдущего
обращения.
Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, эта процедура монитора выдает команду WAIT с указанием условия ожидания.
В этом случае процесс, переводящийся в режим ожидания, будет
ждать момента, когда необходимый ресурс освободится. Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе. В этом случае монитор выдает
команду извещения (сигнализации) SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и войти в монитор.
Если монитор сигнализирует о возвращении ресурса, и в это время
нет процессов, ожидающих такого ресурса, то он вносится в список
свободных ресурсов.
Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ресурса, со временем его получит, считается, что ожидаю54
щий процесс имеет более высокий приоритет, чем новый процесс,
пытающийся войти в монитор.
Рассмотрим пример монитора для выделения одного ресурса.
Monitor resourse;
Condition free;
(* условие - свободный*)
Var busy: Boolean;
Procedure Request; (* запрос*)
Begin
If busy then WAIT (free);
Busy := true;
Выдать ресурс;
End;
Procedure Release; (* освобождение*)
Begin
Взять ресурс;
Busy := false;
SIGNAL (free);
End;
Begin
Busy := false;
End.
Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам Request и Release.
Если процесс обращается к процедуре Request в тот момент, когда
ресурс используется, значение переменной busy будет true и Request
выполнит операцию WAIT(free). Эта операция заблокирует обратившийся процесс, и он будет помещен в конец очереди процессов, ожидающих доступ к монитору. Когда процесс, использующий ресурс, обратится к процедуре Release, операция монитора SIGNAL деблокирует
процесс, находящийся в начале очереди, не позволяя исполняться никакой другой процедуре внутри того же монитора. Этот деблокированный процесс готов возобновить выполнение процедуры Request.
Использование монитора в качестве средства синхронизации и
связи освобождает процессы от необходимости явно разделять между собою ресурсы, так как доступ к разделяемым переменным всегда ограничен телом монитора. Поскольку мониторы входят в состав
ядра ОС, то разделяемые переменные становятся системными переменными. Этот факт автоматически исключает критические интервалы, так как в каждый момент монитором может пользоваться
только один процесс.
55
Использование мониторов имеет ряд преимуществ по сравнению
с низкоуровневыми средствами:
– локализация разделяемых переменных внутри тела монитора
позволяет избавиться от малопонятных программных конструкций
в синхронизируемых процессах;
– мониторы дают возможность процессам совместно использовать программные модули, представляющие критические секции
(если несколько процессов совместно и одинаково используют некоторый разделяемый ресурс, то в составе монитора достаточно иметь
одну копию соответствующей процедуры работы с этим ресурсом).
Выводы
1. При мультипрограммировании в вычислительной системе проблема синхронизации доступа к общим разделяемым ресурсам является проблемой, требующей обязательного решения с точки зрения
корректного выполнения всего множества активных процессов. Поэтому в составе ОС должны быть средства для решения подобных задач.
2. При использовании низкоуровневых средств из состава ОС
можно решать разнообразные задачи синхронизации, когда используются общие разделяемые ресурсы. Но в этом случае программисту приходиться самому определять состав критических ресурсов и
программный код критических интервалов.
3. При использовании высокоуровневых средств синхронизации
отпадает необходимость программирования критических интервалов, что упрощает программирование, но несколько снижает производительность соответствующих программных модулей.
Контрольные вопросы
1. В чем разница между конкурирующими и взаимодествующими параллельными процессами?
2. Что означают понятия – критический ресурс и критическая
секция (критический интервал)?
3. Какой недостаток имеет метод синхронизации параллельных
процессов с помощью команды «Проверка и установка»?
4. Какие критические ресурсы фигурируют в задаче «Поставщик –
Потребитель»?
5. Какой основной недостаток первого решения задачи «Читатели – Писатели» и как этот недостаток устраняется во втором способе решения данной задачи?
56
6. Зачем в операциях с почтовыми ящиками используется механизм тайм-аута?
7. Какие возможности предоставляет использование мониторов
при решении задач синхронизации?
57
5. ПОНЯТИЕ ТУПИКА И МЕТОДЫ БОРЬБЫ С ТУПИКАМИ
В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
5.1. Понятие тупика, примеры тупиков,
условия существования тупиков
При параллельном выполнении процессов в вычислительной системе могут возникать ситуации, при которых два или более процесса все
время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов
не может продолжить свое выполнение и освободить в конечном итоге
ресурс, необходимый другому процессу. Такая ситуация называется
тупиком или клинчем. Говорят, что в мультипрограммной системе
процесс находится в состоянии тупика, если он ждет событие, которое
никогда не произойдет. Тупики чаще всего возникают из-за конкуренции параллельных процессов за ресурсы вычислительной системы, но
иногда к тупикам приводят ошибки в программировании.
При рассмотрении проблемы тупиков целесообразно понятие
ресурсов вычислительной системы обобщить и разделить их все на
два класса – повторно используемые или системные ресурсы (SR –
System Resource) и потребляемые или расходуемые ресурсы (CR –
Consumable Resource).
Системный ресурс (SR) есть конечное множество единиц со следующими свойствами:
– число единиц ресурса постоянно;
– каждая единица ресурса или доступна, или распределена одному и только одному процессу;
– процесс может освободить единицу ресурса, только, если он раньше получил эту единицу, т. е. никакой процесс не может оказывать
какого-либо влияния ни на один ресурс, если он ему не принадлежит.
Примерами таких ресурсов являются компоненты аппаратуры
(оперативная память, внешняя память, внешние устройства, процессор), а также программные и информационные компоненты
(файлы, таблицы, переменные и т. п.).
Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях:
– число доступных единиц некоторого ресурса типа CR изменяется, по мере того как приобретаются и освобождаются отдельные
его элементы выполняемыми процессами, а также число единиц ресурса является потенциально неограниченным;
58
– процесс типа «Производитель» увеличивает число единиц ресурса, освобождая одну или более единиц;
– процесс типа «Потребитель» уменьшает число единиц ресурса,
сначала запрашивая, а затем приобретая одну или более единиц.
Примерами таких ресурсов являются синхронизирующие сигналы, сигналы прерываний, сообщения, которыми обмениваются процессы.
Рассмотрим несколько примеров образования тупиков.
Пример тупика на ресурсах типа CR
Пусть три процесса Пр1, Пр2, Пр3 вырабатывают сообщения М1,
М2, М3 по кольцевой схеме. Процесс Пр1 является потребителем сообщения М3, процесс Пр2 должен получить сообщение М1, а Пр3 –
М2. Таким образом, каждый из процессов одновременно является и
«Поставщиком », и «Потребителем», и вместе они образуют кольцевую схему передачи сообщений друг другу. Если связь между процессами устанавливается в следующем порядке:
Прi :
send_message (Прk, Mi, Пяk);
Wait_message ( Прj, Mj, Пяi);
(где i = 1, 2, 3 k = 2, 3, 1 j = 3, 1, 2), то никаких сложностей при взаимодействии процессов не возникает, и тупика не будет. Однако перестановка этих двух операций местами приводит к тупику:
Пр1:
wait_message(Пр3, М3, Пя1);
Send_message(Пр2, М1, Пя2);
Пр2:
wait_message(Пр1, М1, Пя2);
Send_message(Пр3, М2, Пя3);
Пр3:
wait_message(Пр2, М2, Пя3);
Send_message(Пр1, М3, Пя1);
В самом деле, ни один из процессов не сможет послать сообщение
до тех пор, пока сам его не получит, а это событие никогда не произойдет, поскольку ни один процесс не может этого сделать.
Пример тупика на ресурсах типа CR и SR
Пусть некоторый процесс Пр1 должен обменяться сообщениями
с процессом Пр2 и каждый из них запрашивает некоторый ресурс
R, причем Пр1 требует три единицы этого ресурса для своего выпол59
нения, а Пр2 – две единицы и только на время обработки сообщения. Всего же у системы имеется только четыре единицы ресурса R.
Запрос на ресурс R можно реализовать через процедуру монитора
Request (R, N) – запрос N единиц ресурса R, и Release (R, N) – освобождение N единиц ресурса R. Обмен сообщениями производится
через почтовый ящик Пя. Фрагменты программ процессов Пр1 и
Пр2 будут выглядеть следующим образом:
Пр1:
Пр2:
…
Request (R,3);
…
send_message (Пр2, сообщение, Пя);
wait_answer (ответ, Пя);
…
Release (R, 3);
…
…
Wait_message ( Пр1, сообщение, Пя);
Request (R, 2);
Обработка сообщения;
Release (R, 2);
Send_answer (ответ, Пя);
…
Эти два процесса всегда будут попадать в тупик. Процесс Пр2,
если будет выполняться первым, сначала ожидает сообщение от
Пр1, после чего будет заблокирован при запросе ресурса R, часть
единиц которого уже будет отдана Пр1. Процесс Пр1, завладев тремя единицами ресурса R, будет заблокирован на ожидании ответа
от Пр2, которого никогда не получит, так как для этого Пр2 нужно
получить две единицы ресурса R, что невозможно. Тупика можно
избежать лишь при условии, что на время ожидания ответа от Пр2
процесс Пр1 будет отдавать хотя бы одну единицу ресурса R, которым он владеет.
Пример тупика на ресурсах типа SR
Предположим, что существуют два процесса Пр1 и Пр2, разделяющих два ресурса типа SR: R1 и R2. Пусть взаимное исключение
доступа к этим ресурсам реализуется с помощью двоичных семафоров S1 и S2 соответственно. Начальные значения семафоров равны
60
единице. Процессы Пр1 и Пр2 обращаются к ресурсам следующим
образом:
Пр1:
…
Пр2:
1: P(S2);
…
2: P(S1);
…
3: V(S1);
…
4: V(S2);
…
…
5: P(S1);
…
6: P(S2);
…
7: V(S1);
…
8: V(S2);
…
Здесь несущественные детали с точки зрения доступа к ресурсам опущены. Оба семафора первоначально установлены в единицу.
Пространство возможных вычислений приводится на рис. 12.
Горизонтальная ось задает выполнение Пр1, а вертикальная Пр2.
Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1–4 процесса Пр1. Аналогично, горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5–8 процесса Пр2. ТочПР2
8
I
7
W
6
U
H
Y
Z
5
X
II
1
2
3
4
ПР1
Рис. 12
61
ка на плоскости определяет состояние вычислений в некоторый момент
времени. Так, точка W соответствует ситуации, при которой Пр1 начал
выполнение, но не достиг оператора 1, а Пр2 выполнил операторы 5 и 6,
но не достиг оператора 7. По мере выполнения процессов точка может
двигаться горизонтально вправо, если выполняется Пр1, и вертикально вверх, если выполняется Пр2. Горизонтальные и вертикальные линии делят пространство вычислений на 25 прямоугольников (клеток),
каждый из которых задает определенное состояние вычислений. Заштрихованные состояния являются недостижимыми из-за взаимного
исключения Пр1 и Пр2 при доступе к ресурсам R1 и R2.
Рассмотрим последовательность выполнения 1–2–5–3–6–7–8, представленную траекторией I. Когда Пр2 запрашивает R1 (оператор 5), R1
недоступен (семафор S1 закрыт). Поэтому Пр2 заблокирован в точке
Х. Как только Пр1 достигнет оператора 3, Пр2 деблокируется по R1.
Аналогично, в точке Y Пр2 будет заблокирован при попытке доступа
к R2 (оператор 6). Как только Пр1 достигнет оператора 4, Пр2 деблокируется по R2. Данная последовательность выполнения процессов не
приведет к тупиковой ситуации, так как оба процесса рано или поздно
получат доступ к ресурсам и смогут нормально завершиться.
Если же, например, выполняется последовательность 1–5–2–6, то
Пр1 заблокируется в точке Z при выполнении оператора 2, а Пр2 заблокируется в точке H при выполнении оператора 6. При этом Пр1 будет
ждать, когда Пр2 выполнит оператор 7, а Пр2 будет ждать, когда Пр1
выполнит оператор 4. Оба процесса попадут в тупик и не смогут закончить свое выполнение. При этом все ресурсы, которые получил Пр1,
будут недоступны для Пр2 и наоборот. Тупик будет неизбежным, если
выполнение процессов зашло в состояние U. Такое состояние называется опасным состоянием, а точка H является точкой тупика.
Для того чтобы возник тупик, необходимо, чтобы одновременно
выполнялись четыре условия:
– взаимного исключения, при котором процессы осуществляют
монопольный доступ к ресурсам;
– ожидания, при котором процесс, запросивший ресурс, ждет до
тех пор, пока его запрос не будет удовлетворен, при этом удерживая
ранее полученные ресурсы;
– отсутствия перераспределения, при котором ресурсы нельзя
отобрать у процесса, если они уже ему выделены;
– кругового ожидания, при котором существует замкнутая цепь
процессов, каждый из которых ждет ресурс, удерживаемый его
предшественником в цепи.
Все эти четыре условия выполняются в точке H – точке тупика.
62
5.2. Методы борьбы с тупиками
Борьба с тупиковыми ситуациями основывается на одной из трех
стратегий:
– предотвращение тупика;
– обход тупика;
– обнаружение тупика с последующим восстановлением работоспособности системы.
Предотвращение тупика
Предотвращение тупика основывается на предположении о
его чрезвычайно высокой стоимости, поэтому лучше потратить до­
полнительные ресурсы системы, чтобы исключить вероятность его
возникновения при любых обстоятельствах. Предотвращение можно
рассматривать как запрет существования опасных состояний. Поэтому дисциплина, предотвращающая тупик, должна гарантировать,
что какое-либо из четырех условий, необходимых для его наступ­
ления, не может возникнуть.
Условие взаимного исключения можно подавить путем разре­шения
неограниченного разделения ресурсов. Это удобно для пов­торно входимых программ и ряда драйверов, но совершенно неприемлемо к совместно используемым переменным в критических интервалах.
Условие ожидания можно подавить, предварительно выделяя ресурсы. При этом процесс может начать исполнение, только по­лучив
все необходимые ресурсы заранее. Следовательно, общее число затребованных параллельными процессами ресурсов должно быть не
больше возможностей системы. Поэтому предварительное выделение
может привести к снижению эффективности работы вы­числительной
системы в целом. Необходимо также отметить, что предварительное
выделение зачастую невозможно, так как необхо­димые ресурсы становятся известны процессу только после начала исполнения.
Условие отсутствия перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы. Для этого в ОС должен быть
предусмотрен механизм запоминания состояния процесса с целью последующего восстанов­ления. Перераспределение процессора реализуется достаточно легко, в то время как перераспределение
устройств ввода-вывода крайне нежелательно.
Условие кругового ожидания можно исключить, предотвращая
образование цепи. Это обеспечивается иерархическим выделением
ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, за63
требовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Процесс может освободить
ресурсы на данном уровне только после освобождения всех ре­сурсов
на всех более высоких уровнях. После того как процесс получил, а
потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне. Пусть имеются про­цессы Пр1 и Пр2,
которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на более высоком уровне иерархии. Когда Пр1 захватил R1,
Пр2 не может захватить R2, так как доступ к нему проходит через
доступ к R1, который уже захвачен Пр1. Таким образом, создание
замкнутой цепи исключается. Иерархи­ческое выделение ресурсов
часто не дает никакого выигрыша, ес­ли порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом слу­чае ресурсы будут использоваться
крайне неэффективно.
Обход тупика
Обход тупика можно интерпретировать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условий не
исключено, то вход в опасное состояние можно предотвратить, при
наличии у системы информации о последовательности запросов,
связанных с каждым параллельным процессом. Доказано, что если
вычисления находятся в любом неопасном состояния, то суще­ствует
по крайней мере одна последовательность состояний, кото­рая обходит опасное. Следовательно, достаточно проверить, не приведет ли
выделение затребованного ресурса сразу же к опасно­му состоянию.
Если да, то запрос отклоняется. Если нет, его можно выполнить.
Определение того, является ли состояние опас­ным или нет, требует анализа последующих запросов процессов. Часто бывает так, что
последовательность запросов, связанных с каждым процессом, неизвестна заранее. Но если заранее известен общий запрос на ресурсы каждого типа, то выделение ресурсов можно контролировать.
В этом случае необходимо для каждого тре­бования, в предположении, что оно удовлетворено, определить, существует ли среди общих запросов от всех процессов некоторая последовательность требований, которая может привести к опасно­му состоянию. Данный
подход является примером контролируемого выделения ресурса.
Классическое решение этой задачи известно как алгоритм банкира Дейкстры . Основным накладным расходом стратегии обхода
тупика с помощью контролируемого выделения ресурса яв­ляется
64
время выполнения алгоритма, так как он выполняется при каждом запросе. Причем алгоритм работает наиболее медленно, когда
система близка к тупику. Необходимо отметить, что обход тупика
неприменим при отсутствии информации о требованиях про­цессов
на ресурсы.
Распознавание тупика
Распознавание тупика основано на анализе модели распреде­
ления ресурсов. Один из алгоритмов использует информацию о состоянии системы, содержащуюся в двух таблицах: таблице текущего распределения (назначения) peсурсов RATBL и таблице заблокированных процессов PWTBL (для каждого вида ресурса может быть
свой список заблокированных процессов). При каждом запросе на
получение или освобождение ресурсов содержимое этих таблиц мо­
дифицируется, а при запросе на ранее выделенный ресурс анализируется в соответствии со следующим алгоритмом:
1. Запрос от процесса Y на занятый ресурс I.
2. Поместить номер ресурса I в PWTBI. в строке с номером процесса Y.
3. Использовать I в качестве смещения в RATBL, чтобы найти номер процесса К, который владеет ресурсом.
4. Использовать К в качестве смещения в PWTBL.
5. Проверить, ждет ли процесс К освобождения какого-либо ресурса I’. Если нет, то перейти к пункту 6, в противном случае – к пункту 7.
6. Перевести Y в состояние ожидания и выйти из алгоритма.
7. Использовать I′ в качестве смещения в RATBL, чтобы найти
номер блокирующего его процесса К′.
8. Проверить К′ = Y? Если да, то перейти к пункту 9, в про­тивном
случае – к пункту 11.
9. Проверить, вся ли таблица PWI′BL просмотрена. Если да, то
переход к пункту 6, в противном случае – к пункту 10.
10. Присвоение К := К′ и переход к пункту 4.
11. Вывод о наличии тупика.
12. Конец aлгоритма.
Для иллюстрации описанного алгоритма распознавания ту­пика
рассмотрим следующую последовательность событий:
1. Пр1 занимает ресурс R1.
2. Пр2 занимает ресурс R3.
3. ПрЗ занимает ресурс R2.
4. Пр2 занимает ресурс R4.
65
5. Пр1 занимает ресурс R5.
В результате RATBL принимает вид:
Ресурсы
1
2
3
4
5
Процессы
1
3
2
2
1
6. Пусть Пр1 пытается занять R3, поэтому в соответствии с описанным алгоритмом – Y = 1, I = 3, К = 2, процесс K не ждет никакого
ресурса I′, поэтому Пр1 блокируется по R3.
7. Далее пусть Пр2 пытается занять R2; Y = 2, I = 2, К = 3, процесс
К не ждет никакого ресурса, поэтому Пр2 блокируется по R2.
8. И, наконец, пусть Пр3 пытается получить R5; Y = 3, I = 5, К = 1,
I′ = 3, К′ = 2, К′ не равен Y, поэтому берем К = 2, I′ = 2, K′ = 3. В этом
случае К′ = Y, т. е. тупик определен. Таблица PWTBL имеет следующий вид:
Процесс
1
2
3
Ресурс
3
2
5
Равенство Y = K′ означает, что существует замкнутая цепь взаимоисключающих и ожидающих процессов, т. е. выполняются все
четыре условия существования тупика.
Распознавание тупика требует дальнейшего восстановления.
Восстановление можно интерпретировать как запрет постоянного
пребывания в опасном состоянии. Существуют следующие методы
восстановления:
– принудительный перезапуск системы, характеризующийсяпотерей информации о всех процессах, существовавших до перезапуска в системе;
– принудительное завершение только тех процессов, которые находились в тупике;
– принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызовом алгоритма распоз­
навания после каждого завершения процесса вплоть до исчезновения тупика;
66
– перезапуск процессов, находящихся в тупике, с некоторой
контрольной точки, т. е. из состояния, предшествовавшего запросу
на ресурс;
– перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.
Основные издержки восстановления составляют потери време­
ни на повторные вычисления, которые могут оказаться весьма существенными. К сожалению, в ряде случаев восстановление может
стать невозможным: например, исходные данные, поступившие
с каких-либо датчиков, могут уже измениться, а предыдущие значения будут безвозвратно потеряны.
Выводы
1. Взаимная конкуренция со стороны параллельных процессов
и ошибки в программировании могут приводить вычисления к «тупику» и, как следствие, – к «зависанию» вычислительной системы.
2. Образование тупика возможно при попытке доступа, как к «системным», так и «потребляемым» ресурсам вычислительной системы.
3. Тупик становится неизбежным, если одновременно действуют
четыре условия существования тупика.
4. Предотвращение и обход, как стратегии борьбы с тупиками,
оказались несостоятельными, так как их использование невозможно
при доступе к ряду необходимых ресурсов из состава вычислительной системы или резко снижает производительность вычислений.
5. Распознавание тупика с последующим восстановлением работоспособности системы является реально используемой стратегией
борьбы с тупиками, но имеет ряд недостатков, связанных с необходимостью повторных вычислений.
Контрольные вопросы
1. Условие взаимного исключения при тупике можно подавить,
если разрешить неограниченное разделение всех видов ресурсов со
стороны параллельных процессов. Какой ресурс нельзя неограниченно разделять: процессор, винчестер, переменные, драйвера?
2. Почему введение и поддержка иерархии ресурсов при подавлении условия «кругового ожидания» оказались неэффективными,
как метод предотвращения тупика?
3. Почему алгоритм «Банкира» не нашел практического применения?
67
4. В какой момент должен начинать работать алгоритм распознавания тупика?
5. Какую информацию о процессах и ресурсах определяет алгоритм распознавания тупика?
6. Перечислите методы восстановления работоспособности системы после распознавания тупика.
68
6. ЗАДАЧИ ОПЕРАЦИОННОЙ СИСТЕМЫ
ПО УПРАВЛЕНИЮ ФАЙЛАМИ И УСТРОЙСТВАМИ
Организация параллельной работы
устройств ввода-вывода и процессора
Каждое устройство ввода-вывода снабжено специализированным
блоком управления – контроллером. Контроллер взаимодействует
с драйвером – системным программным модулем, предназначенным
для управления устройством ввода-вывода. Контроллер периодически принимает от драйвера данные, или выдает ему порции данных, а также принимает от драйвера управляющие команды, которые определяют действия с данными. Под управлением контроллера
внешнее устройство может некоторое время выполнять свои операции автономно, не требуя внимания со стороны центрального процессора. Это время зависит от многих факторов – объема передаваемой
информации, степени интеллектуальности соответствующего контроллера, быстродействия устройства ввода-вывода и т. д.
Процессы, происходящие в контроллерах, протекают между выдачами управляющих команд независимо от ОС. От подсистемы ввода-вывода требуется спланировать в реальном масштабе времени (в
котором работают внешние устройства) запуск и приостановку большого числа разнообразных драйверов, обеспечив приемлемое время
реакции каждого драйвера на независимые события, происходящие
при работе внешних устройств и соответствующих драйверов. С другой стороны, необходимо минимизировать загрузку процессора задачами ввода-вывода, оставив как можно больше процессорного времени на выполнение пользовательских потоков. Данная задача обычно
решается на основе многоуровневой приоритетной схемы обслуживания по прерываниям. Для обеспечения приемлемого уровня реакции
все драйверы( или части драйверов) распределяются по нескольким
приоритетным уровням в соответствии с требованиями ко времени
реакции и временем использования процессора. Для реализации такой схемы обычно используется диспетчер прерываний.
Согласование скоростей обмена и кэширование данных
При обмене данными всегда возникает задача согласования скорости.
В подсистеме ввода-вывода для согласования скоростей обмена широко используется буферизация данных в ОП. В систе69
мах, где обеспечение высокой скорости ввода-вывода является
первоочередной задачей (управление в реальном времени, услуги
сетевой файловой службы), большая часть ОП отводится не под
коды прикладных программ, а под буферизацию данных. Однако разница между скоростью работы внутренних процессов и
скоростью работы внешних устройств может оказаться весьма
значительной, и ОП, отведенной под буфер, может просто не хватить. В этом случае в качестве буфера используется специальный
дисковый файл – спул-файл. Например, с помощью спул-файла
осуществляется организация вывода данных на принтер (объем
выводимой информации может превышать несколько десятков
мегабайт). Также в настоящее время в качестве буфера активно
используется собственная память внешних устройств (контроллеры графических станций), что значительно ускоряет вывод
графики на экран мониторов.
Буферизация данных позволяет также сократить количество
операций ввода-вывода, что повышает скорость ввода-вывода.
Разделение устройств и данных между процессами
Устройства ввода-вывода могут предоставляться процессам, как
в монопольное, так и в совместное (разделяемое) использование. При
этом ОС должна обеспечивать контроль доступа к устройствам ввода-вывода. Такой контроль осуществляется путем проверки прав
доступа пользователя или группы пользователей, от имени которых действует процесс, на выполнение той или иной операции над
внешним устройством. Например, определенной группе пользователей разрешено захватывать последовательный порт в монопольное
владение, а другой группе – нет.
Оперативная система может контролировать доступ не только к устройству в целом, но и к отдельным порциям данных,
хранимых или отображаемых этим устройством. Диск является типичным примером устройства, для которого необходимо
контролировать доступ не к устройству в целом, а к отдельным
каталогам и файлам. При выводе на графический дисплей отдельные окна экрана также представляют собой ресурсы, к которым необходимо обеспечить тот или иной вид доступа со стороны
выполняемых в системе процессов. Для каждого файла и каталога можно задать индивидуальные права доступа, а для их совместного использования необходимо задать режим разделения
устройства в целом.
70
Одно и то же устройство в разные периоды времени работы вычислительной системы может использоваться как в разделяемом,
так и в монопольном режиме. Оперативная система должна предоставлять эти устройства в обоих режимах, осуществляя отслеживание процедур захвата и освобождения монопольно используемых
устройств, а в случае совместного использования оптимизируя последовательность операций ввода-вывода для различных процессов
в целях повышения общей производительности (пример – оптимизация затрат времени на перемещения головок диска).
При разделении устройства между процессами может возникнуть необходимость в разграничении порций данных двух процессов друг от друга. Обычно такая потребность возникает при использовании так называемых последовательных устройств, данные
в которых не адресуются (пример – принтер). Для таких устройств
система организует очередь заданий на вывод, причем каждое задание представляет порцию данных, которую нельзя разрывать. Для
хранения очереди заданий используется спул-файл, который одновременно согласует скорости работы принтера и ОП и позволяет разбить данные на логические порции. Поскольку спул-файл находится на разделяемом устройстве (диск) прямого доступа, то процессы
могут параллельно выполнять ввод на принтер, помещая данные
в свой раздел спул-файла.
Обеспечение удобного логического интерфейса
между устройствами и остальной частью системы
Разнообразие устройств ввода-вывода делают актуальной функцию по созданию унифицированного интерфейса между этими
устройствами и приложениями. В качестве основы такого интерфейса выступает файловая модель устройств ввода-вывода, когда
любое устройство рассматривается прикладным программистом
как набор байт, с которым можно работать с помощью унифицированных системных вызовов (read, write и т. п.), задавая имя устройства и смещение от начала последовательности байт.
Привлекательность модели файла-устройства состоит в ее простоте и унифицированности для устройств любого типа. Однако
при программировании операций ввода-вывода для некоторых
устройств такая модель является слишком «бедной». Поэтому файловая модель используется только в качестве базиса, над которым
подсистема ввода-вывода строит более содержательную модель (например – вывод графической информации).
71
Поддержка широкого спектра драйверов
и простота включения нового драйвера в систему
Достоинством подсистемы ввода-вывода любой универсальной
ОС является наличие разнообразного набора драйверов для наиболее популярных периферийных устройств.
Чтобы ОС не испытывала недостатка в драйверах, необходимо
наличие четкого, удобного и открытого интерфейса между драйверами и другими компонентами ОС. Открытость интерфейса драйверов, т. е. доступность их описания для независимых разработчиков
ПО, является необходимым условием успешного развития ОС.
Драйвер, с одной стороны, взаимодействует с модулями ядра ОС,
а с другой – с контроллерами внешних устройств. Поэтому существует два типа интерфейсов: <ядро-драйвер> и <драйвер-устройство>.
Интерфейс <ядро-драйвер> должен быть стандартизирован в любом
случае, а интерфейс <драйвер-устройство> имеет смысл стандартизировать тогда, когда подсистема ввода-вывода не разрешает драйверу
непосредственно взаимодействовать с аппаратурой контроллера, а выполняет эти операции самостоятельно. В этом случае драйвер становится независимым от аппаратной платформы. Подсистема ввода-вывода может поддерживать несколько различных типов интерфейсов.
Динамическая загрузка и выгрузка драйверов
Современные ОС должны иметь в своем составе механизм, позволяющий осуществлять динамическую загрузку и выгрузку драйверов. Такая возможность позволяет оперативно изменять набор
необходимых драйверов в системе, а также экономить системную
область памяти в случае выгрузки драйвера, необходимость в котором отпала по тем или иным причинам.
При изменении состава драйверов отсутствие такой возможности требует повторной компиляции ядра ОС, что значительно усложняет модификацию ОС.
Поддержка нескольких файловых систем
Популярность файловой системы часто приводит к ее миграции
из «родной» ОС в другие ОС, – например, файловая система FAT появилась персонально в MS-DOS, но затем была реализована в OS/2,
семействе MS Windows и многих реализациях UNIX. Ввиду этого
поддержка нескольких популярных файловых систем со стороны
72
подсистемы ввода-вывода также очень важна. Архитектура подсистемы ввода-вывода должна достаточно просто включать в свой состав новые типы файловых систем, без необходимости изменения ее
кода. Для этого в ОС имеется специальный слой программного обеспечения, отвечающий за решение данной задачи.
Поддержка синхронных и асинхронных операций ввода-вывода
Операция ввода-вывода может выполняться по отношению
к программному модулю, запросившему эту операцию в синхронном или асинхронном режиме. Синхронный режим означает, что
программный модуль приостанавливает свою работу до тех пор,
пока операция ввода-вывода не будет завершена, а при асинхронном режиме программный модуль продолжает выполняться одновременно с операцией ввода-вывода. Операция ввода-вывода может
быть инициирована как пользовательским так системным процессом. Подсистема ввода-вывода должна предоставлять возможности
выполнения как синхронных, так и асинхронных операций вводавывода. Системные вызовы ввода-вывода обычно оформляются как
синхронные процедуры, так как пользовательские процессы должны дождаться результатов выполнения операций ввода-вывода для
своего дальнейшего корректного развития. Внутренние вызовы
операций ввода-вывода из модулей ядра ОС обычно выполняются
в виде асинхронных процедур, так как кодам ядра нужна свобода
в выборе дальнейшего поведения после запроса ввода-вывода.
Выводы
1. Организация параллельной работы всего множества внешних
устройств вычислительной системы обеспечивается ОС при тесном
взаимодействии с соответствующими микроконтроллерами внешних устройств. Планирование такого взаимодействия реализуется
супервизором ввода-вывода или диспетчером прерываний на основе
некоторой приоритетной схемы, отображающей разную значимость
(приоритет) различных внешних устройств.
2. Согласование разных скоростей обмена между процессором и
внешними устройствами реализуется в использовании различных
методов кэширования и буферизации.
3. Операционная система должна обеспечивать доступ к различным внешним устройствам, как в монопольном режиме, так и в режиме разделения.
73
4. Базовой моделью представления внешних устройств является файловая модель. Остальные способы представления являются
надстройкой над базовой моделью.
5. Возможность оперативного включения новых драйверов в ОС
без перепрограммирования его ядра значительно повышает привлекательность использования такой системы.
6. Поддержка как синхронных, так и асинхронных операций
ввода/вывода со стороны ОС позволяет эффективно управлять различными процессами ввода-вывода во время вычислений.
Контрольные вопросы
1. От каких факторов зависит время автономной работы внешнего устройства и его микроконтроллера?
2. Какие методы кэширования используются при согласовании
скоростей обмена данными?
3. Как реализуется задача разграничения порций данных разных процессов?
4. Какие привлекательные свойства файловой модели имеются
для представления внешних устройств?
5. Почему операции ввода-вывода из состава API оформляются
как синхронные функции или процедуры?
74
7. АППАРАТНЫЕ СРЕДСТВА ПОДДЕРЖКИ
ОПЕРАЦИОННОЙ СИСТЕМЫ
НА ПРИМЕРЕ СЕМЕЙСТВА ПРОЦЕССОРОВ I80X86
Процессоры семейства i80х86, начиная с процессора 80386,
способны работать в двух режимах: в режиме реальных адресов
(реальный режим) и в режиме защищенной памяти (защищенный режим). В составе этого процессора имеются различные блоки и устройства, осуществляющие поддержку функционирования ОС.
Основным режимом работы процессора является защищенный
режим, при котором обеспечивается многозадачность, специальный механизм защиты памяти, сегментная или сегментно-страничная организация памяти, кэширование страниц и данных.
В защищенном режиме используется 32-разрядная адресная
шина, поэтому адресуемая физическая память имеет размер 4гб.
Дальнейшее изложение материала будет ориентировано на объяснение механизмов функционирования, характерных для защищенного режима.
В реальном режиме процессор выполняет шестнадцатиразрядные инструкции (команды) и адресует 1 Мб памяти.
7.1. Регистры процессора i80x86
Набор основных функциональных регистров процессора,
в первую очередь, направлен на реализацию основных возможностей защищенного режима (многозадачность, защита памяти
и т. д.), а их содержимое определяется текущей выполняемой задачей.
Регистры общего назначения
Восемь 32-разрядных регистров общего назначения предназначены для хранения данных и адресов и имеют имена EAX,
EBX, ECX, EDX, ESI, EDI, EBP, ESP. Они поддерживают работу с данными разрядностью 1, 8, 16, 32, и 64 бита (см. рис. 13).
Младшие 16 разрядов этих регистров доступны отдельно при использовании имен AX, BX, CX, DX, SI, DI, BP, SP. При операциях с байтами можно обращаться к старшим и младшим байтам
регистров AX, BX, CX, DX. В этом случае старшие байты будут
иметь имена – AH, BH, CH, DH, а младшие – AL, BL, CL, DL.
75
31
16 15
AH
BH
CH
DH
AX
BX
CX
DX
SI
DI
BP
SP
0
AL
BL
CL
DL
Рис. 13
Программный доступ к отдельным байтам повышает возможности программирования.
Регистры сегментов (селекторы)
С помощью этих шести 16-разрядных регистров обеспечивается обращение к текущему сегменту задачи, а в защищенном режиме эти регистры называются селекторами. Кроме того, для целей ускорения определения адресов внутри сегментов, с каждым из селекторов связан невидимый 8-байтовый регистр, назначение которого будет рассмотрено далее.
CS – хранит указатель на дескриптор кодового сегмента в одной
из таблиц дескрипторов сегментов (GDT или LDT); SS – хранит указатель на дескриптор сегмента стека в одной из таблиц дескрипторов сегментов; DS, ES, FS, GS – хранят указатели на дескрипторы
сегментов данных в одной из таблиц дескрипторов сегментов.
Структура селекторов показана на рис. 14,
15
3
Index
2 1
0
TI
RPL
Рис. 14
где Index – индекс (номер) дескриптора в таблице дескрипторов сегмента; TI – тип таблицы (если TI = 0, то GDT, если TI = 1, то LDT);
RPL – значение уровня привилегий запроса (от 0 до 3).
Указатели инструкций
EIP – указатель команд, содержит относительный 32-разрядный
адрес текущей инструкции, т. е. смещение относительно базового
адреса кодового сегмента. Его содержимое является программно
недоступным.
76
EFLAGS – 32-разрядный регистр флагов, содержит признаки результата выполнения текущей команды, используется при обработке исключений и маскируемых прерываний, при определении последовательности вызываемых задач, при управлении вводом-выводом и рядом других процедур. В дальнейшем описание содержимого отдельных полей и битов этого регистра будет осуществляться по
мере необходимости.
Управляющие 32-разрядные регистры
CR0 – его содержимое определяет признаки работы процессора
(признак режима, вкл / выкл сегментно-страничной организации
памяти, выполнение команд с плавающей точкой и т. д.). Нас будет,
прежде всего, интересовать содержимое младшего бита этого регистра (PE – protect enable). При PE = 0 процессор функционирует в реальном режиме, а при PE = 1 процессор переходит в защищенный
режим.
CR1 – не используется (в резерве).
CR2 – для хранения линейного виртуального адреса, вызвавшего страничный отказ. Страничный отказ связан с отсутствием страницы в ОП в момент адресации к ней.
CR3 – физический адрес таблицы разделов текущей выполняемой задачи, используемой при сегментно-страничной организации
памяти.
CR4 – признаки, разрешающие работу архитектурных расширений (возможность использования страниц размером в 4 Мб).
Регистры системных адресов
GDTR – 48-разрядный регистр, значение которого определяют
характеристики GDT (Global Descriptor Table) – глобальной таблицы дескрипторов сегментов.
IDTR – 48-разрядный регистр, значение которого определяют характеристики IDT (Interrupt Descriptor Table) – таблицы дескрипторов прерываний. Структуры этих регистров идентичны и показаны
на рис. 15.
16 15
47
Адрес GDT
Адрес IDT
0
Размер GDT
Размер IDT
Рис. 15
77
TR – 16-разрядный указатель на
дескриптор специального сегмента
(TSS), входящего GDT. В сегменте TSS
(Task State Segment) хранится конРис. 16
текст текущей выполняемой задачи.
LDTR – 16-разрядный указатель
на дескриптор в GDT, в котором, в свою очередь, хранится адрес
LDT (Local Descriptor Table) – локальной таблицы дескрипторов текущей выполняемой задачи. Структуры этих регистров идентичны
и показаны на рис. 16. Кроме того с этими регистрами связаны «невидимые» 8-байтовые регистры, используемые для ускорения процесса адресации и переключения задач.
Регистры отладки (DR0, …, DR7) и регистры тестирования
(TR3, …, TR7), используемые для проверки корректности работы
внутренних блоков процессора, не являются средствами непосредственной аппаратной поддержки функционирования ОС и подробно
рассматриваться не будут.
15
0
Указатель на дескриптор TSS
Указатель на LDT
7.2. Дескрипторы сегментов и виртуальное адресное пространство
При сегментной организации памяти виртуальное адресное пространство определяется всем множеством сегментов. Код и данные
задачи представляют некоторое множество сегментов. Загружаемым в память объектом является сегмент задачи. Каждый сегмент
имеет свой описатель – дескриптор сегмента, в котором хранятся
параметры конкретного сегмента. Значения некоторых параметров
сегмента могут меняться за период выполнения задачи. Структура
такого 8-байтового дескриптора показана на рис. 17.
Из рис. 17 видно, что значение размера сегмента сосредоточено в нулевом, первом и, частично, в шестом байте дескриптора. Значение начального ( базового) 32-разрядного адреса сегмента в памяти распределено
между вторым, третьим, четвертым и седьмым байтах дескриптора.
3 байт
2 байт
База (биты 0–15)
P DPL Тип сегмента База (биты 16–23)
Размер
и признаки
(биты 16–19)
доступа
4 байт
6 байт
5 байт
(права доступа)
Рис. 17
78
0 байт
Размер сегмента (биты 0–15)
База (биты 24–31) G D 0 X
7 байт
1 байт
Шестой байт дескриптора состоит из нескольких полей, а именно:
– битовое поле G (7-й бит) задает значение признака измерения
размера сегмента (если G = 0, то в байтах, если G = 1,то в страницах);
– битовое поле D (6-й бит ) задает значение признака размерности
слов, входящих в сегмент (если D = 0, то 16-битные слова, если D = 1,
то 32-битные слова).
5-й бит всегда принимает нулевое значение, 4-й бит может принимать любое значение (Х).
Биты с нулевого по третий используются для хранения старших
разрядов значения размера сегмента.
Особую и очень важную роль играет содержимое 5-го байта –
байта «прав доступа» (см. рис. 18).
Битовое поле P (7-й бит) задает значение признака присутствия /
отсутствия сегмента в памяти (если P = 1, то сегмент в памяти).
Поле DPL (Descriptor Privilege Level), состоящее из 2 бит (5-й и
6-й биты) задает значение уровня привилегий сегмента, его значение может изменяться от 0 до 3. Значение DPL необходимо при проверке прав доступа к сегменту.
Остальные пять битов в байте прав доступа используются для определения типа сегмента (данные, стек, код, системный сегмент) и способ использования сегмента (читать, писать, выполнять, только читать и т. д.).
Если четвертый бит S = 0, то такие дескрипторы будут называться системными и являться описателями системных или специальных сегментов (TSS). При S = 1 дескрипторы являются описателями
кодовых сегментов, сегментов данных или стека задачи.
Если третий бит Е = 1, то это дескриптор кодового сегмента, для
которого:
– Поле С = 1 (2-й бит) означает, что соответствующий кодовый
сегмент является «подчиненным», а при C = 0 – «неподчиненным».
Понятие подчиненности сегмента будет рассмотрено далее.
7
6
P
7
5
DPL
6
P
7
5
DPL
6
P
5
DPL
4
S=0
3
4
S =1
3
4
S=1
3
E=0
2
1
0
1
0
A
1
0
A
Тип
Е=1
2
С
R
2
ED
W
Рис. 18
79
– Поле R = 1 (1-й бит) разрешает считывание кодового сегмента,
а при R = 0 такое считывание не разрешается.
– Поле A (бит обращения) (0-й бит) устанавливается в единицу
при обращении к сегменту. Для невостребованных сегментов значение этого поля будет равняться нулю. Значение поля A используется при реализации механизма свопинга.
Если третий бит E = 0, то речь идет о дескрипторах сегментов
данных и стека. Такие сегменты имеют следующие характерные
признаки:
– Поле ED (2-й бит) определяет размещение сегмента относительно его базового адреса. При ED = 0, данные в сегменте размещаются
в направлении возрастания адресов до границы, определяемой размером сегмента. При ED = 1 данные в сегменте располагаются в направлении уменьшения адресов, что характерно для сегментов стека.
– Поле W (1-й бит) используется для сегментов данных. При W = 1
разрешается модификация содержимого сегмента (разрешение на запись), при W = 0 разрешается только считывание данных.
– Поле А (0-й бит) имеет то же назначение, что и соответствующее поле в дескрипторе кодового сегмента.
При загрузке задач в ОП дескрипторы сегментов каждой загружаемой задачи объединяются в соответствующие таблицы. Микропроцессор использует три типа таблиц дескрипторов:
– GDT – глобальная таблица дескрипторов;
– LDT – локальная таблица дескрипторов;
– IDT – таблица дескрипторов прерываний.
В GDT содержатся:
– дескрипторы сегментов ОС;
– дескрипторы сегментов TSS пользовательских задач;
– специальные дескрипторы (шлюзы), используемые при переключении задач и межзадачного взаимодействия;
– дескрипторы сегментов с указанием на локальные таблицы дескрипторов сегментов пользовательских задач.
Таблица GDT хранится в памяти в одном экземпляре и объединяет в себе дескрипторы сегментов, определяющих общее виртуальное адресное пространство.
В LDT объединяются дескрипторы сегментов конкретной пользовательской задачи. Такие сегменты в совокупности определяют локальное виртуальное пространство конкретной задачи. Количество
в памяти локальных таблиц определяется числом активных задач.
Максимальное число дескрипторов, находящихся в одной таблице –
213, следовательно, максимальный размер таблицы – 213 × 23 = 64 Кб.
80
Селектор
Смещение (EIP)
Index TI = 0 RPL
EIP
Сегмент
GDT
+
GDTR
+
База
Размер
Рис. 19
Определение линейного исполнительного адреса при сегментной организации памяти выполняется во время выполнения программы. Доступ к сегменту возможен только при соблюдении соответствующих прав доступа, которые будут рассмотрены далее.
Схема получения линейного адреса, в случае, когда дескриптор
адресуемого сегмента находится в глобальной таблице дескрипторов GDT (в селекторе поле TI = 0), выглядит следующим образом (рис. 19).
Линейный адрес определяется в два этапа. На первом этапе определяется местоположение дескриптора сегмента в таблице GDT путем сложения содержимого поля Index селектора и регистра процессора GDTR. На втором этапе базовый адрес сегмента, извлекаемый из соответствующего дескриптора, складывается со значением
регистра EIP, что дает значение линейного адреса. При сегментной
организации памяти линейный адрес рассматривается как физический адрес внутри адресуемого сегмента, не требующий дальнейших преобразований.
В случае, когда дескриптор адресуемого сегмента находится в локальной таблице дескрипторов LDT, определение линейного адреса
производится в три этапа (рис. 20). На первом этапе определяется
местоположение специального дескриптора из состава GDT, в котором хранится значение базового адреса LDT. Это осуществляется
81
Смещение
Селектор
Index TI = RPL
=1
EIP
GDTR
GDT
+
+
База
Сегмент
LDT
База
+
LDTR
Рис. 20
путем сложения значений GDTR и LDTR. На втором этапе определяется местоположение дескриптора из состава LDT путем сложения базового адреса LDT и значения поля Index селектора. На третьем этапе непосредственно определяется линейный адрес путем
сложения базового адреса сегмента и значения EIP.
При обращении к сегменту, который в данный момент отсутствует в оперативной памяти (в байте прав доступа дескриптора признак
P = 0), вызывается соответствующее прерывание, обработка которого заключается в вызове процедуры подкачки сегмента из внешней
памяти.
Поскольку линейный адрес определяется во время выполнения
программы, необходимо чтобы это осуществлялось как можно быстрее. Поэтому с каждым из селекторов связан «невидимый» (скрытый) 8-байтовый регистр, в котором хранится дескриптор текущего
адресуемого сегмента. Наличие такого регистра позволяет непосредственно через него адресоваться к сегменту, минуя обращения
к таблицам, если это повторные обращения к данному сегменту.
Содержимое этих регистров будет меняться только в случае обращения к новому сегменту. Использование таких «невидимых» регистров значительно ускоряет процесс определения линейных адресов сегментов и является специальным средством кэширования дескрипторов сегментов.
82
7.3. Защита данных при сегментной организации памяти
Для защиты информации, хранящейся в сегментах памяти, используется система привилегий, которая регулирует доступ к тому
или иному сегменту в зависимости от уровня его защищенности и
степени важности (привилегированности) запроса. В процессоре
i80х86 установлены четыре уровня привилегий (рис. 21).
0 – ядро ОС (максимальная защищенность); 1 – утилиты операционной системы; 2 – служебные программы; 3 – пользовательские
программы.
Правила доступа к сегментам основываются на сравнении следующих значений:
RPL – запрашиваемый уровень привилегий (задается битами 0
и 1 селектора);
CPL – текущий уровень привилегий выполняемого кода (хранится в селекторе кода CS),т. е. CPL = RPL селектора кода;
EPL – max (CPL,RPL) – эффективный уровень привилегий;
DPL – действительный уровень привилегий сегмента (задается
в 5-м байте прав доступа дескриптора сегмента, биты 5 и 6). Наиболее защищенный сегмент имеет значение DPL = 0, а наименее защищенный DPL = 3.
Доступ к сегментам данных разрешается, если EPL<=DPL. Это
означает, что доступ к сегменту данных возможен как из собственной программы, так и из программного сегмента, имеющего более
высокий уровень привилегий. Нарушение этого правила вызывает
соответствующее прерывание, и доступ к сегменту откладывается.
Доступ к сегментам стека разрешается, если DPL = RPL (в селекторе SS) = CPL. Это означает, что доступ к сегменту стека возможен
только из программного сегмента,
имеющего тот же уровень привилегий, что и сегмент стека. Кроме того
3
доступ к сегменту стека будет разре2
шен, если значение признака W в бай1
0
те прав доступа дескриптора сегмента
будет равно единице. В противном
случае произойдет прерывание и в доступе к сегменту стека будет отказано.
Доступ к сегментам кода определяется в зависимости от типа кодового
сегмента, к которому идет обращение.
Кодовые сегменты могут быть подчиРис. 21
83
Селектор CS
EIP
GDT или LDT
Сегмент
Дескриптор
+
База Размер
База
DPL С
Рис. 22
ненными или неподчиненными. Подчиненный сегмент хранит код
вызываемого программного модуля, вызов к которому имеется в некотором основном программном модуле. Такой вызов может осуществляться с помощью команд CALL, RET, INT, IRET. Подчиненный
сегмент идентифицируется битом С = 1 в байте прав доступа дескриптора сегмента. Правило доступа к подчиненному сегменту определяется как DPL>= CPL, т. е. к подчиненному сегменту могут обращаться программы,имеющие такой же или более высокий уровень
привилегий. Схема обращения к подчиненному сегменту выглядит
следующим образом (см. рис. 22).
Значение поля Index селектора определяет местоположение дескриптора в одной из таблиц дескрипторов. Значение базового адреса сегмента, извлекаемое из дескриптора, складывается с содержимым EIP и определяет значение линейного адреса внутри подчиненного кодового сегмента.
Доступ к неподчиненным сегментам (С = 0) обычно связан с доступом к более привилегированным сегментам, в частности к кодовым сегментам из состава ядра ОС. Такой доступ осуществляется с помощью специальных дескрипторов, называемых шлюзами
(вентилями). Шлюзы содержат указатели на обычные дескрипторы
сегментов, находящиеся в той же таблице дескрипторов. Структура
шлюза представлена на рис. 23.
84
3 байт
2 байт
Относительный адрес (биты 0–15)
Относительный адрес (биты 16–31)
7 байт
0 байт
1 байт
Селектор
6 байт
WC
(биты 0–4)
4 байт
0 0 0
Р DPL
5 байт
(права доступа)
Рис. 23
В байтах 2 и 3 дескриптора шлюза содержится значение селектора вызываемого сегмента программы, а байты 0, 1, 6, 7 задают
относительный адрес процедуры, к которой идет обращение (точка
входа в программу внутри сегмента). Байт прав доступа шлюза показан на рис. 24.
Поле T (3-й бит) задает конкретный тип процессора и определяет
особенности формирования линейного адреса для различных типов
процессора.
Поле WC, состоящее из пяти бит, в четвертом байте указывает
количество параметров, которые переносятся из стека текущей программы в стек новой программы, к которой произошло обращение.
Число переносимых параметров из старого стека в новый стек может составлять от 0 до 31.
Правило доступа к неподчиненным сегментам определяется как CPL <= DPL шлюза. При использовании шлюзов задачи
с меньшим уровнем привилегий могут вызывать более привилегированные задачи. Схема обращения к неподчиненному сегменту
показана на рис. 25.
Из этой схемы видно, что значение поля селектора шлюза используется для определения дескриптора сегмента адресуемой
новой программы (процедуры). Сложение относительного адреса,
извлекаемого из соответствующего поля шлюза, и базового адреса
сегмента, извлекаемого из дескриптора сегмента новой программы,
дает значение начального адреса новой программы (процедуры) относительно начала сегмента. Значение регистра EIP в формировании линейного адреса не используется.
7
6
P
5
DPL
4
0
3
T
2
1
1
0
0
0
Рис. 24
85
Index
EIP
TI RPL
GDT или LDT
Селектор
Сегмент
Смещение
+
Дескриптор
База
Рис. 25
В защищенном режиме работы процессора i80х86 модули, входящие в ядро ОС и имеющие высший уровень привилегий, могут
содержать в своем коде привилегированные команды. К таким командам относятся:
– команды для работы с управляющими регистрами CRn, а также для загрузки системных адресов GDTR, LDTR, IDTR, и TR;
– команда останова процессора HALT;
– команды запрета/разрешения маскируемых прерываний CLI/
SLI;
– команды ввода-вывода IN, INS, OUT, OUTS.
Первые две группы команд могут выполняться только при самом
высшем уровне привилегий кода, то есть при CPL=0. Для двух последних групп команд их выполнение будет разрешаться, если CPL
<= IOPL, где IOPL – значение уровня привилегий ввода-вывода.
7.4. Сегментно-страничная организация памяти
Признаком сегментно-страничной организации памяти является значение PG = 1 (31 бит в регистре CR0). В этом случае линейный адрес, получаемый при сегментной организации памяти, считается виртуальным и требует своего дальнейшего преобразования
с целью определения исполнительного физического адреса внутри
страницы.
86
Сегмент разбивается на отдельные разделы, максимальное число
которых для одного сегмента может достигать 210, а каждый раздел
может состоять из 210 страниц. Размер каждой страницы – 212 байт.
Поэтому линейный адрес рассматривается как элемент, состоящий из
трех полей: table – младшие 10 бит указателя на дескриптор текущей
используемой таблицы страниц, page – младшие 10 бит указателя на
дескриптор текущей используемой страницы, byte – младшие 12 бит
исполнительного адреса внутри страницы. Физическая память рассматривается как множество физических страниц, имеющих размер
в 4 Кб, причем границы физических страниц жестко фиксированы.
Процессор для каждого адресуемого сегмента создает в памяти
каталог разделов, а для каждого каталога таблицу страниц. Элементами, как каталога разделов, так и таблицы страниц являются
4-байтные дескрипторы. Регистр CR3 используется для хранения
значения старших 20 байт начального адреса каталога разделов текущего адресуемого сегмента. Схема получения исполнительного
адреса выглядит следующим образом (см. рис. 26).
Исполнительный адрес внутри страницы определяется за три обращения к памяти – к каталогу разделов, к таблице страниц и непосредственно к самой странице. Адреса внутри таблиц и исполнительный адрес определяются путем логического сложения старших
бит базовых адресов (12–31), хранящихся в CR3 и в дескрипторах, и
соответствующих полей исполнительного адреса.
31
table
page
22 21
Каталог
разделов
+
Дескриптор
таблицы
страниц
12
byte
11
Страница
Таблица
страниц
+
Дескриптор
страницы
0
+
CR3 (31–12 б)
Рис. 26
87
12
31
Базовый адрес
11–9
8–7
6
5
Резерв
0
D
A
4
3
2
1
PCD PWT U/S R/W
0
P
Рис. 27
Дескрипторы таблицы страниц и дескрипторы страниц имеют
идентичную структуру, показанную на рис. 27.
P – бит присутствия, если P = 1, то таблица страниц или сама
страница находится в памяти. Если же P = 0, то обращение к соответствующему разделу или странице запрещено и попытка их использования вызовет соответствующее прерывание;
R/W – определяет права доступа к странице со стороны программ пользователя (уровень привилегий равен трем);
U/S – определяет возможность доступа к странице, если U/S = 0 доступ запрещается, если U/S = 1 и R/W = 1 разрешается чтение и запись;
PWT – определяет метод обновления внешней кэш-памяти, при
PWT = 1 – сквозная запись (одновременное обновление основной и
кэш-памяти), при PWT = 0 – обратная запись;
PCD – разрешение-запрет кэширования во внутренней памяти
процессора, при PCD = 1 запрещается загрузка страницы во внутреннюю кэш-память;
A – автоматически устанавливается в 1 при обращении к данной
таблице страниц или странице;
D – признак модификации страницы, если D = 1 – в страницу
осуществлялась запись. Для указателей таблиц страниц, значение
бита D является неопределенным.
Биты A и D используются ОС, поддерживающей виртуальную
память, для определения в ОП разделов и страниц, которые подлежат замене и откачке во внешнюю память (механизм свопинга).
Проверку и сброс этих битов осуществляет ОС.
Биты 9–11 дескриптора зарезервированы для ОС, которая может
использовать их для своих потребностей. Например, в этих битах
может размещаться информация о времени последнего обращения
к разделу или странице. Такая информация может использоваться
для определения разделов и страниц, подлежащих замене в ОП при
реализации механизма свопинга.
Сегментно-страничная организация памяти требует дополнительных затрат для преобразования линейного адреса в физи88
ческий исполнительный адрес внутри страницы, причем эти затраты могут быть весьма значительными и отрицательно влиять
на производительность вычислительной системы. Существенное
сокращение времени преобразования адресов достигается путем
использования специального устройства в составе процессора –
буфера ассоциативной трансляции (TLB – Translation Look aside
Buffer).
7.5. Буфер ассоциативной трансляции и кэширование памяти
Буфер ассоциативной трансляции (TLB) является памятью с ассоциативной выборкой.
TLB состоит из 8 наборов (рис. 28). В каждый набор входят – четыре семнадцатиразрядных тега, логика обслуживания и четыре
регистра для хранения дескрипторов страниц. Логика обслужива31
Тег
15 14 Индекс 12 11
Набор № 0
Теги
Смещение
0
Дескрипторы страниц
v0
L0
b0
v1 L1
b1
v2 L2
b2
v3
L3
Набор № 7
Рис. 28
89
ния базируется на трех битах обращения (b0, b1, b2) и четырех битах
действительности (v0, v1, v2, v3).
При использовании TLB линейный адрес рассматривается как совокупность трех полей – поле тега (ключа), поле индекса и поле, в котором хранится значение смещения относительно начала страницы.
При обращении к TLB ассоциативная процедура поиска состоит
в следующем:
– значение индекса в соответствующем поле линейного адреса
определяет номер набора в TLB;
– параллельное сравнение значения ключа (в линейном адресе)
со значениями тегов в наборе и, в случае равенства, последующее
определение наличия дескриптора в регистре хранения (соответствующее значение бита действительности должно быть установлено в единицу).
В случае «кэш-попадания» происходит сложение старших битов,
хранящихся в дескрипторе, со смещением в линейном адресе, что
дает значение исполнительного адреса внутри страницы.
В случае «кэш-промаха» реализуется многоступенчатая процедура определения исполнительного адреса (рис. 28). Одновременно происходит запись в соответствующий набор TLB значения дескриптора
адресуемой страницы, с установкой одного из битов действительности
в единицу. Это необходимо для последующих обращений к данной
странице. Запись дескриптора страницы осуществляется в первую
свободную строку набора. Если же все строки заняты, то запись осуществляется в строку, к которой дольше всего не обращались, а старое
значение дескриптора считается на данный момент «ненужным».
Биты обращения используются при реализации замещения «ненужных» дескрипторов страниц. Такое замещение производится в соответствии с упрощенной дисциплиной PseudoLRU (Pseudo
Least Recently Used). Установка же значений битов обращений b0,
b1, b2 осуществляется по специальному алгоритму в зависимости
от значений строк набора L0, L1, L2, L3 и сводится к следующему:
1. Проверка– последнее обращение было к паре L0, L1? Если да,
то b0 = 1, если нет b0 = 0.
2. При b0 = 1 проверка – последнее обращение к L0? Если да, то
b1 = 1, если нет b1 = 0, конец.
3. При b0 = 0 проверка – последнее обращение к L2? Если да, то
b2 = 1, если нет b2 = 0, конец.
Данная процедура не всегда приводит к выбору строки, к которой
дольше всех не было обращения. Но в большинстве случаев этот алгоритм дает результат, совпадающий с оптимальным результатом.
90
В TLB кэшируются дескрипторы страниц, количество которых
может достигать 32-х. Следовательно, объем кэшируемой с помощью TLB памяти составляет 32 × 4 Кб = 128 Кб. При использовании
TLB количество «кэш-попаданий» достигает 98%, что значительно
ускоряет получение исполнительного адреса.
Кроме того, в составе процессора i80х86 имеется кэш-память
первого уровня, в которой кэшируются данные. Эта память организована аналогично TLB и позволяет кэшировать объем до 16 Кбайт.
В такой кэш-памяти единицей хранения является байт данных. Обновление данных в кэше происходит блоками по 16 байт. В случае
использования кэш-памяти первого уровня уже известный физический адрес рассматривается как совокупность трех полей – младшие 4 бита как смещение в блоке, следующие 8 бит как индекс,
указывающий на номер набора, а старшие биты как значение тега
(ключа), указывающее на номер блока. Для хранения блоков данных в кэше отводятся строки, имеющие объем 16 байт. Структура
кэш-памяти первого уровня представлена на рис. 29.
Так же как и TLB, выбор строки в наборе осуществляется на основе анализа битов действительности v0, v1, v2, v4 и битов обращения
b0, b1, b2 по алгоритму PseudoLRU. Блок данных заносится в строку кэш-памяти вместе с тегом, а бит действительности устанавливается в 1. При возникновении запроса на чтение из основной памяти
сначала делается попытка найти данные к кэш-памяти. По индексу,
извлеченному из адреса запроса, определяется номер набора, в котором могут быть искомые данные. Затем для строк из данного набора, содержимое которых действительно (биты действительности
установлены в 1), выполняется ассоциативный поиск путем сравнения старших разрядов адреса со значениями тегов набора. При совпадении этих значений (кэш-попадание) из соответствующей строки извлекается байт, смещение которого относительно начала строки определяется значением поля смещения в задаваемом адресе.
Для согласования данных в кэш-памяти первого уровня используется метод сквозной записи, т. е. при возникновении запроса на запись обновляется, как содержимое соответствующей ячейки основной памяти, так ее копии в кэш-памяти, если она там находится. При
кэш-промахе запрос на запись не вызывает обновления кэш-памяти.
При обработке запроса к основной памяти могут использоваться
разные виды кэш-памяти. Прежде всего, будет сделана попытка использования невидимого регистра при соответствующем селекторе
с целью получения дескриптора адресуемого сегмента. Затем будет
использоваться буфер ассоциативной трансляции TLB, в котором
91
31
Тег
12
11
Индекс
Набор № 0
Теги
b0
4
3 Смещение 0
Блок данных
v0
v1
b1
v2
v3
b2
Набор № 256
Рис. 29
кэшируются дескрипторы страниц. Использование TLB позволяет
достичь очень высокого процента кэш-попаданий. Далее, при известном физическом адресе, искомый операнд может быть обнаружен в кэш-памяти первого уровня.
7.6. Многозадачность. Переключение задач
При переключении задач используются специальные сегменты –
TSS (Task State Segment). Сегменты TSS поддерживаются процессором i80х86 в защищенном режиме и создаются в ОП при ее активизации. По своему функциональному назначению сегмент TSS
представляет собой описатель контекста задачи. Дескриптор, указывающий на TSS, всегда находится в GDT. Структура TSS показана на рис 30.
92
Битовая карта ввода-вывода (БККВ)
Дополнительная информация ОС
Относительный адрес БККВ
0…0
Селектор LDT
0…0
0…0
GS
FS
0…0
0…0
DS
0…0
SS
0…0
CS
ES
Селектор LDT
EDI
ESI
| T
EBP
ESP
EBX
EDX
ECD
EAX
EFLAGS
EIP
CR3
0 ... 0
SS уровня 2
ESP2
SS уровня 1
0 ... 0
ESP1
0 ... 0
SS уровня 0
ESP0
Селектор TSS возврата
0 ... 0
Рис. 30
Сегмент TSS имеет фиксированные поля, отведенные для хранения содержимого регистров процессора, как универсальных, так и
некоторых управляющих (например, CR3).
Для доступа задачи к портам ввода-вывода процессор использует в защищенном режиме поле IOPL (Input / Output Privilege Level)
в своем регистре EFLAGS и карту битовых полей доступа к портам
в сегменте TSS. Чтобы выполнять команды ввода-вывода значение
текущего CPL не выше, чем уровень привилегий операций ввода-вывода, задаваемый значением поля IOPL в регистре флагов EFLAGS,
т. е. CPL<= IOPL. Если же это условие не соблюдается, то возможность доступа к порту с конкретным адресом определяется значени93
ем соответствующего бита в карте ввода-вывода сегмента TSS (карта
состоит из 8Кбайт для описания доступа к 65536 портам), – значение 0 разрешает операцию ввода-вывода с данным номером порта.
Кроме того сегмент TSS может включать дополнительную информацию, необходимую для работы задачи и зависящую от конкретной ОС.
Поле селектора возврата в составе TSS используется для хранения значения CS ранее выполняемой задачи. Контекст задачи представляет собой набор значений регистров процессора, необходимых
для начала выполнения задачи. БКВВ – битовая карта ввода-вывода, используется для указания внешних устройств, необходимых
для выполнения задачи.
Переключение задач осуществляется с помощью ассемблерной
команды CALL с указанием пары значений CS:EIP. Порядок переключения задач следующий:
1. Сохраняются значения всех рабочих регистров процессора
в текущем сегменте TSS. Для этого используется регистр TR, указывающий на дескриптор TSS в составе GDT.
2. Происходит обращение к TSS новой задачи по следующей схеме (см. рис. 31).
3. В TR загружается новое значение, соответствующее значению
CS или значению поля селектора в шлюзе.
4. Из нового TSS в регистр LDTR переносится значение селектора
таблицы LDT в таблице GDT задачи.
CALL CS: EIP
LDT
GDT
Шлюз
Дескриптор
TSS
Селектор
Адрес Граница
Рис. 31
94
TSS
5. В регистры процессора загружаются соответствующие значения из соответствующих полей TSS новой задачи.
6. В поле селектора возврата нового TSS загружается значение
CS старой задачи.
7. Начало выполнения новой задачи.
Из сказанного следует, что переключение задач является довольно сложной процедурой. Поэтому при ее реализации активно
используются невидимые регистры при селекторах, что позволяет
ускорить процесс переключения задач.
7.7. Обработка прерываний
При обработке прерываний в защищенном режиме используется
таблица IDT (Interrupt Descriptor Table), поддерживаемая процессором i80х86. Составляющими элементами IDT являются 8-байтовые
дескрипторы обработчиков прерываний, которые по своей структуре представляют собой шлюзы и называются коммутаторами.
В регистре IDTR хранится начальный адрес IDT, а номер прерывания, который указывается в соответствующих запросах при обращении к обработчикам прерываний, показывает местоположение
коммутатора в IDT относительно начального адреса.
Коммутаторы могут быть 3 типов:
1. Коммутатор прерываний (interrupt gate).
2. Коммутатор перехвата (trap gate).
3. Коммутатор задачи (task gate).
Первые два типа коммутаторов вызывают переход на выполнение соответствующих сегментов кода, принадлежащих виртуальному адресному пространству текущего вычислительного процесса. Другими словами, обработка прерываний при использовании
этих коммутаторов осуществляется под контролем текущей задачи
и смены контекста не происходит. Обращение к сегменту кода, содержащего обработчик прерывания, в этом случае производится по
следующей схеме (см. рис. 32).
По номеру прерывания ищется соответствующий коммутатор из
IDT. Далее определяется тип прерывания путем анализа содержимого байта прав доступа коммутатора.
Если его тип соответствует коммутатору interrupt gate или trap
gate, то выполняются следующие действия.
В стек на уровне привилегий текущего сегмента кода помещаются:
1. Значения SS и SP, если уровень привилегий в коммутаторе
выше уровня привилегий ранее исполнявшегося кода.
95
№ прерывания
+
IDT
GDT
Коммутатор
прерывания
Дескриптор
сегмента
Селек- Сметор щение
Адрес Граница
+
Сегмент
с кодом
обработчика
прерываний
IDTR
Рис. 32
2. Значение регистра флагов EFLAGS.
3. Значения регистров CS и EIP.
Отличие в использовании коммутаторов прерываний и коммутаторов перехвата состоит в том, что при использовании первых запрещается обработка новых прерываний на период обработки текущего прерывания (устанавливается флаг IF = 0 в регистре EFLAGS).
Использование коммутаторов задачи вызывает переключение
процессора на новую задачу, представляющую собой обработчик прерываний. При этом происходит смена контекста задачи. Обращение
к новой задаче производится по следующей схеме (см. рис. 33):
Последовательность действий в этом случае следующая:
1. Сохраняются все рабочие регистры процессора в текущем сегменте
TSS, базовый адрес которого берется из «невидимого» регистра при TR.
2. Текущая задача отмечается как занятая.
3. По селектору из Task Gate выбирается новый TSS (поле селектора помещается в регистр TR) и загружается контекст новой задачи. Загрузка контекста новой задачи означает загрузку значений
LDTR, EFLAGS, восемь регистров общего назначения, EIP и шесть
сегментных регистров (селекторов).
4. Устанавливается бит NT (next task).
96
№ прерывания
+
IDT
GDT
Коммутатор
задачи
Дескриптор
TSS
Селектор
TSS
Адрес
IDTR
Рис. 33
5. В поле обратной связи TSS помещается значение селектора
прерванной задачи.
6. Значения CS:EIP, взятые из нового TSS, позволяют определить
и выполнить первую команду обработчика прерываний.
Достоинством использования коммутаторов task gate является
то, что сохраняются значения всех регистров процессора при обращении к обработчику прерываний. Тогда как при использовании
коммутаторов типа interrupt gate и trap gate сохраняется содержимое только регистров EFLAGS, CS, EIP.
Использование коммутаторов задачи task gate при обработке
прерываний связано с большими временными затратами. Поэтому
при создании соответствующих программ программисты стараются использовать обработчики прерываний, выполняемые в контексте исполняемой задачи без переключения на новую задачу.
Выводы
1. Процессоры i80х86, начиная с процессора 80486, обладают
развитыми средствами, необходимыми для функционирования ОС,
поддерживающих мультипрограммный режим:
– сегментный и сегментно-страничный механизм виртуальной
памяти;
97
– средства защиты сегментов кодов и данных на основе четырех
уровней привилегий;
– набор привилегированных команд, используемых только в системных модулях;
– встроенная кэш-память, используемая на различных этапах
определения исполнительных адресов кода и данных;
– механизм переключения задач с сохранением их контекста;
– система обработки прерываний, позволяющая обрабатывать
прерывания различных типов (interrupt gate, trap gate, task gate).
2. Процессор поддерживает два типа таблиц: глобальную таблицу дескрипторов GDT, в которой хранятся значения параметров системных сегментов и разделяемых сегментов пользовательских задач, и локальные таблицы дескрипторов LDT, каждая из которых
содержит дескрипторы сегментов отдельной задачи.
3. Каждый сегмент виртуального адресного пространства описывается дескриптором, который содержит базовый адрес, размер
сегмента, а также ряд признаков, в том числе уровень привилегий
сегмента DPL, определяющий права доступа к нему.
4. При сегментном режиме работы виртуальное адресное пространство состоит из 16 Кбайт сегментов по 4 Гбайт каждый – всего
64 Тбайт, а при сегментно-страничном режиме работы все сегменты
отображаются в общем диапазоне адресов 4 Гбайт.
5. Процессор поддерживает несколько способов обращения к сегментам кода в зависимости от типа таких сегментов (подчиненные,
неподчиненные), а также содержит средства переключения задач
с сохранением контекстов этих задач.
6. В процессоре активно используются механизмы кэширования, позволяющие значительно ускорить выполнение задач, а также смену задач при их переключении: кэширование дескрипторов
сегментов в скрытых регистрах процессора, кэширование дескрипторов страниц в буфере ассоциативной трансляции TLB, кэширование данных и команд в кэш-памяти первого уровня.
7. Процессор предоставляет широкие возможности для организации обработки прерываний различного типа в защищенном режиме
на основе использования таблицы прерываний IDT. При этом прерывания могут являться как внутренними (исключения), так и внешними (от устройств ввода-вывода), а также программными прерываниями, обработка которых инициируется с помощью команды INT.
8. Объем машинно-зависимых модулей из состава ядра ОС должен быть как можно меньше, что упрощает их перенос на различные аппаратные платформы.
98
Контрольные вопросы
1. Содержимое каких регистров процессора i80х86 в защищенном
режиме указывает на дескрипторы сегментов? Как эти регистры называются?
2. Какое назначение имеют регистры процессора LDTR и TR?
3. Опишите структуру дескриптора сегмента. Что такое байт прав
доступа в дескрипторе сегмента? Объясните содержимое отдельных
полей байта прав доступа.
4. Как определяется максимальное число дескрипторов в таблице и ее максимальный размер в байтах?
5. Чем отличаются механизм доступа к дескрипторам сегментов из
GDT от механизма доступа к дескрипторам сегментов, входящих в LDT?
6. Для чего нужны невидимые (скрытые) 8-байтовые регистры
при селекторах?
7. Что означает понятие – линейный адрес? В каком случае этот
адрес является конечным физическим адресом, а в каком случае он
рассматривается как виртуальный адрес и требуется его дальнейшее преобразование?
8. Объясните понятие «уровень привилегий», какие значения
может принимать уровень привилегий в процессоре i80х86?
9. Что такое текущий и эффективный уровень привилегий?
10. Объясните правила доступа к сегментам данных и стека на
основе уровней привилегий.
11. Что такое подчиненный и неподчиненный кодовые сегменты?
Что такое «шлюз» и какова его структура? Чем отличаются механизмы доступа к подчиненным и неподчиненным кодовым сегментам на основе уровней привилегий?
12. Какие новые таблицы поддерживает процессор i80х86 при
сегментно-страничной организации оперативной памяти?
13. Как определяется исполнительный адрес при сегментно-страничной организации памяти и какой недостаток у этого механизма?
14. Какова цель использования буфера ассоциативной трансляции TLB?
15. Какие объекты кэшируются с помощью TLB и чему равен
максимальный кэшируемый объем памяти?
16. Сколько уровней встроенной кэш-памяти имеет процессор i80х86?
17. Объясните назначение сегмента TSS? Что такое контекст задачи?
18. В чем состоит механизм переключения задач?
19. Как называются дескрипторы, входящие в таблицу IDT, и каков их тип?
99
20. Какие прерывания вызывают выполнение обработчика, входящего в виртуальное адресное пространство текущей задачи?
21. Какие прерывания вызывают переключение процессора на
выполнение программы обработки новой задачи?
100
Библиографический список
1. Гордеев А. В. Операционные системы: учебник. СПб.:Питер, 2004.
416 с.
2. Гордеев А. В., Молчанов А. Ю. Системное программное обеспечение: учебник. СПб.: Питер, 2002. 736 с.
3. Олифер Н. А., Олифер В. Г. Сетевые операционные системы:
учебн. СПб.: Питер, 2001. 544 с.
4. Соловьев Г. Н., Никитин В. Д. Операционные системы ЭВМ:
учеб. пособие. М.: Высшая школа, 1989. 255 с.
5. Иртегов Д. В. Введение в операционные системы. Разработка
и реализация. 2-е изд. СПб., 2007 г.
6. Востриков А. А., Кучин Н. В. Основы организации операционных систем: учеб.-метод. пособие. СПб.: ГУАП, 2011. 72 с.
7. Кучин Н. В. Аппаратные средства поддержки операционных
систем: метод. пособие. СПб.: ГУАП, 2015. 43 с.
101
СОДЕРЖАНИЕ
1. ОСНОВНЫЕ ПОНЯТИЯ И АРХИТЕКТУРА
ОПЕРАЦИОННЫХ СИСТЕМ.....................................................
1.1. Обзор развития операционных систем............................. 1.2. Назначение и функции операционной системы................. 1.3. Понятие процесса, граф состояний процесса.................... 1.4. Классификация процессов............................................. 1.5. Ресурсы вычислительных систем, их классификация........ 1.6. Прерывания и порядок их обработки.............................. 1.7. Архитектура операционной системы............................... 1. 8. Структура ядра операционной системы.......................... 1. 9. Микроядерная архитектура операционной системы......... Выводы............................................................................. Контрольные вопросы......................................................... 2. ПЛАНИРОВАНИЕ И ДИСПЕТЧЕРИЗАЦИЯ ЗАДАЧ
И ПРОЦЕССОВ........................................................................
2.1. Планирование и диспетчеризация процессов.
Дескрипторы задач...................................................... 2.2. Дисциплины диспетчеризации....................................... 2. 3. Дисциплины планирования.......................................... Выводы............................................................................. Контрольные вопросы......................................................... 3. УПРАВЛЕНИЕ ОПЕРАЦИОННОЙ ПАМЯТЬЮ........................
3.1. Пространства и отображения, виртуальное адресное
пространство.............................................................. 3.2. Распределение разделами.............................................. 3.3. Сегментная организация памяти.................................... 3.4. Страничная организация памяти.................................... 3.5. Свопинг. Стратегии свопинга......................................... 3.6 Сегментно-страничная организация памяти...................... Выводы............................................................................. Контрольные вопросы......................................................... 4. МЕТОДЫ СИНХРОНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ
ПРОЦЕССОВ...........................................................................
4.1. Проблемы синхронизации параллельных процессов.......... 4.2. Синхронизация параллельных процессов с помощью
команды «Проверка и установка».................................. 4.3. Семафорные примитивы Дейкстры................................. 4.4. Задача «Поставщик – Потребитель»............................... 4.5. Задача «Читатели – Писатели»...................................... 4.6. Задача с ожиданием...................................................... 4.7. Почтовые ящики.......................................................... 4.8. Мониторы Хоара.......................................................... Выводы............................................................................. Контрольные вопросы......................................................... 102
3
3
6
6
8
9
10
13
15
16
18
18
20
20
21
23
23
24
25
25
27
30
32
34
35
38
39
40
40
42
44
46
48
50
51
53
56
56
5. ПОНЯТИЕ ТУПИКА И МЕТОДЫ БОРЬБЫ С ТУПИКАМИ
В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.........................................
5.1. Понятие тупика, примеры тупиков, условия
существования тупиков................................................ 5.2. Методы борьбы с тупиками............................................ Выводы............................................................................. Контрольные вопросы......................................................... 58
63
67
67
6. ЗАДАЧИ ОПЕРАЦИОННОЙ СИСИТЕМЫ ПО УПРАВЛЕНИЮ
ФАЙЛАМИ И УСТРОЙСТВАМИ................................................
Выводы............................................................................. Контрольные вопросы......................................................... 69
73
74
58
7. АППАРАТНЫЕ СРЕДСТВА ПОДДЕРЖКИ ОПЕРАЦИОННОЙ
СИСТЕМЫ НА ПРИМЕРЕ СЕМЕЙСТВА ПРОЦЕССОРОВ I80X86......
7.1. Регистры процессора i80x86.......................................... 7.2. Дескрипторы сегментов и виртуальное адресное
пространство.............................................................. 7.3. Защита данных при сегментной организации памяти........ 7.4. Сегментно-страничная организация памяти..................... 7.5. Буфер ассоциативной трансляции и кэширование памяти...
7.6. Многозадачность. Переключение задач........................... 7.7. Обработка прерываний.................................................. Выводы............................................................................. Контрольные вопросы......................................................... 78
83
86
89
92
95
97
99
Библиографический список.......................................................
101
75
75
103
Учебное издание
Кучин Николай Валентинович
Молчанов Алексей Юрьевич
ОСНОВЫ ОРГАНИЗАЦИИ
МУЛЬТИПРОГРАММНЫХ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Учебное пособие
Редактор В. П. Зуева
Компьютерная верстка В. Н. Костиной
Сдано в набор 17.03.17. Подписано к печати 18.04.17. Формат 60 × 84 1/16.
Усл. печ. л. 6,0. Уч.-изд. л. 6,5.
Тираж 50 экз. Заказ № 152.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
10
Размер файла
1 985 Кб
Теги
kychin
1/--страниц
Пожаловаться на содержимое документа