Модели организации прерываний

Рассмиотим три модели организации прерываний:

1. Использование «регистра прерываний»

2. Использование вектора прерываний

3. Использование регистра «слово состояние процессора»

[править]Использование «регистра прерываний»

Каждый разряд этого регистра отвечает за появление того или иного прерывания или группы прерываний (т.е. каким-то регистрам может соответствовать прерывание определенного типа, а в каком-то регистре возможна индикация о том, что есть еще один периферийный регистр прерываний, в котором появилось прерывание). Когда ОС получает управление, то специальными командами, которые доступны только ОС, она может прочесть регистр прерываний и определить причину прерывания, а после этого, в зависимости от причины, передать управление на ту или иную программу обработки прерывания.

[править]Использование вектора прерываний

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

[править]Использование регистра «слово состояние процессора»

Код прерывания аппаратно помещается в регистр «слово состояние процессора», после этого программа-обработчик прерывания, выбрав этот код, принимает решение о дальнейшей последовательности действий, которые необходимо осуществить для обработки прерывания, стоящего под этим кодом.

Семафо́р — объект, позволяющий войти в заданный участок кода не более чем n потокам. Определение введено Эдсгером Дейкстрой.
Семафоры используются при передаче данных через разделяемую память.

Семафор — это объект, с которым можно выполнить три операции.

init(n):счётчик := nenter():ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.leave():увеличить счётчик на единицу.

Применение семафоров

Вот некоторые из проблем, которые могут решать семафоры.

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

§ поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен одновременный доступ).

Следующий пример показывает, как наладить поочерёдный доступ к консоли.

semaphore.init(1);Поток 1:semaphore.enter();cout << "Состояние массива: ";for (int i=0; i<n; i++) cout << a[i] << ' ';cout << '\n';semaphore.leave();Поток 2:semaphore.enter();cout << "Нажато Esc.\n";semaphore.leave();

Этот код поможет предотвратить появление листинга наподобие

Состояние массива: 1 2 3 Нажато Esc.4 5 6

Проблемы семафоров

Во-первых, можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave().

Во-вторых, семафоры чреваты взаимной блокировкой потоков. В частности, опасен такой код:

Поток 1:semaphore1.enter();semaphore2.enter();...semaphore2.leave();semaphore1.leave();Поток 2:semaphore2.enter();semaphore1.enter();semaphore1.leave();semaphore2.leave();

Таблица 8.2. Сравнительные характеристики объектов синхронизации Windows

	CRITICAL_SECTION	Мьютекс	Семафор	Событие
Именованный защищаемый объект синхронизации	Нет	Да	Да	Да
Доступность из нескольких процессов	Нет	Да	Да	Да
Синхронизация	Вхождение	Ожидание	Ожидание	Ожидание
Освобождение	Выход	Мьютекс может быть освобожден или оставлен без контроля.	Освобождается любым потоком.	Функции SetEvent, PulseEvent.
Права владения	В каждый момент времени иметь права владельца может только один поток. Владеющий поток может осуществлять вхождение несколько раз, не блокируя свое выполнение.	В каждый момент времени иметь права владельца может только один поток. Владеющий поток может выполнять функцию ожидания несколько раз, не блокируя свое выполнение.	Понятие владения неприменимо. Доступ разрешен одновременно нескольким потокам, число которых ограничено максимальным значением счетчика.	Понятие владения неприменимо. Функции SetEvent и PulseEvent могут быть вызваны любым потоком.
Результат освобождения	Разрешается вхождение одного потока из числа ожидающих.	Вслед за последним освобождением права владения разрешается приобрести одному потоку из числа ожидающих.	Продолжать выполнение могут несколько потоков, число которых определяется текущим значением счетчика.	После вызова функций SetEvent или PulseEvent продолжать выполнение будет один или несколько ожидающих потоков.

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

В Windows существует три группы wait-функций:
1) single-object
К этой группе относится функция WaitForSingleObject(), которая приостанавливает поток до освобождения заданного объекта синхронизации.

DWORD WaitForSingleObject(
HANDLE hHandle,
DWORD dwMilliseconds
);

Параметр hHandle - это дескриптор объекта синхронизации.
Параметр dwMilliseconds указывает время, по истечении которого функция завершается, даже если объект синхронизации не освободился. В этом случае функция возвращает значение WAIT_TIMEOUT.

2) multiple-object
Функции этой группы позволяют потоку ждать освобождения или нескольких объектов синхронизации, или одного из них. К этой группе относится функция WaitForMultipleObjects().

DWORD WaitForMultipleObjects(
DWORD nCount,
const HANDLE* lpHandles,
BOOL bWaitAll,
DWORD dwMilliseconds
);

Параметр nCount указывает количество дескрипторов объектов, содержащихся в массиве, на который указывает параметр lpHandles. Максимально возможное число дескрипторов объектов равно константе MAXIMUM_WAIT_OBJECTS.
Параметр lpHandles - указатель на массив, в котором содержаться дескрипторы объектов синхронизации.
Параметр bWaitAll - если этот параметр равен TRUE, то функция возвращает управление потоку, когда освобождаются все объекты синхронизации, дескрипторы которых содержатся в массиве. Если параметр равен FALSE, то функция завершается при освобождении любого из объектов.
Параметр dwMilliseconds указывает время, по истечении которого функция завершается, даже если объект синхронизации не освободился. В этом случае функция возвращает значение WAIT_TIMEOUT.

3) сигнализирующие (alertable).

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

Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, дедлока, или клинча, если он ожидает неко­торого события, которое никогда не произойдет. Системная тупико­вая ситуация, или «зависание» системы — это ситуация, когда один или более процессов оказываются в состоянии тупика.

Сообщениями в Windows называются небольшие пакеты информации, которыми обмениваются ядро Windows с программами и программы друг с другом. Сообщение связано с некоторым событием и извещает адресат о его наступлении.

Структура сообщений

В модуле Windows сообщение описано следующим образом:

• type
• TMsg = packed record
• hWnd: HWND; // Дескриптор окна-получателя
• Message: UINT; // Код сообщения;
• WParam: WPARAM; // Уточняющий параметр
• LParam: LPARAM; // Уточняющий параметр
• Time: DWORD; // Время создания сообщения
• pt: TPoint; // Координаты указателя мыши в этот момент
• end;

Функции ОС по управлению памятью

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

Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипрограммной операционной системы. Особая роль памяти объясняется тем, что процессор может выполнять инструкции протравы только в том случае, если они находятся в памяти. Память распределяется как между модулями прикладных программ, так и между модулями самой операционной системы.

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

Функциями ОС по управлению памятью в мультипрограммной системе являются:

§ отслеживание свободной и занятой памяти;

§ выделение памяти процессам и освобождение памяти по завершении процессов;

§ вытеснение кодов и данных процессов из оперативной памяти на диск (полное или частичное), когда размеры основной памяти не достаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место;

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

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

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

Защита памяти — это еще одна важная задача операционной системы, которая состоит в том, чтобы не позволить выполняемому процессу записывать или читать данные из памяти, назначенной другому процессу. Эта функция, как правило, реализуется программными модулями ОС в тесном взаимодействии с аппаратными средствами.

Алгоритмы распределения памяти

Следует ли назначать каждому процессу одну непрерывную область физической памяти или можно выделять память «кусками»? Должны ли сегменты программы, загруженные в память, находиться на одном месте в течение всего периода выполнения процесса или можно ее время от времени сдвигать? Что делать, если сегменты программы не помещаются в имеющуюся память? Разные ОС по-разному отвечают на эти и другие базовые вопросы управления памятью. Далее будут рассмотрены наиболее общие подходы к распределению памяти, которые были характерны для разных периодов развития операционных систем. Некоторые из них сохранили актуальность и широко используются в современных ОС, другие же представляют в основном только познавательный интерес, хотя их и сегодня можно встретить в специализированных системах.

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

Рис. 5.7. Классификация методов распределения памяти

Кэш-память

Кэш-память, или просто кэш (cache), — это способ совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который за счет динамического копирования в «быстрое» ЗУ наиболее часто используемой информации из «медленного» ЗУ позволяет, с одной стороны, уменьшить среднее время доступа к данным, а с другой стороны, экономить более дорогую быстродействующую память.

Неотъемлемым свойством кэш-памяти является ее прозрачность для программ и пользователей. Система не требует никакой внешней информации об интенсивности использования данных; ни пользователи, ни программы не принимают никакого участия в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.

Кэш-памятью, или кэшем, часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств — «быстрое» ЗУ.

Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. «Медленное» ЗУ далее будем называть основной памятью, противопоставляя ее вспомогательной кэш-памяти.

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

Принцип действия кэш-памяти

Рассмотрим одну из возможных схем кэширования (рис. 5.25). Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя:

§ значение элемента данных;

§ адрес, который этот элемент данных имеет в основной памяти;

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

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

§ если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попадание (cache-hit), они считываются из нее и результат передается источнику запроса;

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

Рис. 5.25. Схема функционирования кэш-памяти

Интуитивно понятно, что эффективность кэширования зависит от вероятности попадания в кэш. Покажем это путем нахождения зависимости среднего времени доступа к основной памяти от вероятности кэш-попаданий. Пусть имеется основное запоминающее устройство со средним временем доступа к данным tl и кэш-память, имеющая время доступа t2, очевидно, что t2<tl. Пусть t — среднее время доступа к данным в системе с кэш-памятью, ар — вероятность кэш-попадания. По формуле полной вероятности имеем:

t - t₁(d - р) + t₂p - (t₂ -t₁)p + t₁

Среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в основное запоминающее устройство t1 при р=0 до среднего времени доступа непосредственно в кэш-память t2 при р=1. Отсюда видно, что использование кэш-памяти имеет смысл только при высокой вероятности кэш-попадания.

Вероятность обнаружения данных в кэше зависит от разных факторов, таких, например, как объем кэша, объем кэшируемой памяти, алгоритм замещения данных в кэше, особенности выполняемой программы, время ее работы, уровень мультипрограммирования и других особенностей вычислительного процесса. Тем не менее в большинстве реализаций кэш-памяти процент кэш-попаданий оказывается весьма высоким — свыше 90 %. Такое высокое значение вероятности нахождения данных в кэш-памяти объясняется наличием у данных объективных свойств: пространственной и временной локальности.

§ Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью произойдет в ближайшее время.

§ Пространственная локальность. Если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам.

Именно основываясь на свойстве временной локальности, данные, только что считанные из основной памяти, размещают в запоминающем устройстве быстрого доступа, предполагая, что скоро они опять понадобятся. Вначале работы системы, когда кэш-память еще пуста, почти каждый запрос к основной памяти выполняется «по полной программе»: просмотр кэша, констатация промаха, чтение данных из основной памяти, передача результата источнику запроса и копирование данных в кэш. Затем, по мере заполнения кэша, в полном соответствии со свойством временной локальности возрастает вероятность обращения к данным, которые уже были использованы на предыдущем этапе работы системы, то есть к данным, которые содержатся в кэше и могут быть считаны значительно быстрее, чем из основной памяти.

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

22 23

Система ввода/вывода

Система ввода/вывода исполнительной системы - это часть кода ОС, получающая запросы ввода/вывода от процессов пользовательского режима и передающая их, в преобразованном виде, устройствам ввода/вывода. Между сервисами пользовательского режима и аппаратурой ввода/вывода располагается несколько отдельных системных компонентов, включая законченные файловые системы, многочисленные драйверы устройств и драйверы сетевых транспортов.
Система ввода/вывода управляется пакетами запроса ввода/вывода (I/O Request Packet, IRP). Каждый запрос ввода/вывода представляется в виде пакета IRP во время его перехода от одной компоненты системы ввода/вывода к другой. IRP - это структура данных, управляющая обработкой операции ввода/вывода на каждой стадии ее выполнения.

В систему ввода/вывода входят следующие компоненты:

1. 1. Диспетчер ввода/вывода (I/O manager). Реализует средства ввода/вывода, не зависящие от типа устройства, и устанавливает модель для ввода/вывода исполнительной системы. Диспетчер ввода/вывода осуществляет создание, чтение, запись, установку и получение информации, и многие другие операции над файловыми объектами. Диспетчер ввода/вывода реализует асинхронную подсистему ввода/вывода, основанную на передаче пакетов запроса ввода/вывода (I/O Request Packet, IRP). Диспетчер ввода/ вывода также отвечает за поддержку и обеспечение операционной среды для драйверов.

2. 2. Файловые системы. Драйверы, принимающие запросы файлового ввода/вывода и транслирующие их в запросы, привязанные к конкретному устройству. Сюда же входят сетевые файловые системы, состоящие из двух компонентов: сетевого редиректора (network redirector), реализуемого как драйвер файловой системы и передающего удаленные запросы ввода/вывода на машины в сети, и сетевого сервера (network server), являющегося обычным драйвером, принимающим и обрабатывающим такие запросы.

3. 3. Сетевые драйверы, которые могут загружаться в ОС и рассматриваться как часть системы ввода/вывода.

4. 4. Драйверы устройств. Низкоуровневые драйверы, напрямую работающие с оборудованием.

Диспетчер ввода/вывода (I/O manager) определяет порядок, по которому запросы ввода/вывода доставляются драйверам. В обязанности диспетчера входит:

1. 1. Получение запроса на ввод/вывод и создание пакета IRP.

2. 2. Передача IRP соответствующему драйверу. Драйвер, получив IRP, выполняет указанную в нем операцию ввода/вывода, и, либо возвращает его диспетчеру ввода/ вывода для завершения обработки, либо передает другому драйверу для продолжения операции ввода/вывода.

3. 3. Сопровождение IRP по стеку драйверов.

4. 4. Завершение IRP по окончании операции ввода/вывода и возвращение результатов обработки инициатору запроса ввода/вывода.

5. 5. Также диспетчер ввода/вывода реализует общие процедуры, к которым обращаются драйверы во время обработки ввода/вывода, и предоставляет системные сервисы, позволяющие защищенным подсистемам реализовать свои API ввода/вывода.

Файловая система

Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами.

В широком смысле понятие "файловая система" включает:

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

Типы файлов

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

Обычные файлы в свою очередь подразделяются на текстовые и двоичные. Текстовые файлы состоят из строк символов, представленных в ASCII-коде. Это могут быть документы, исходные тексты программ и т.п. Текстовые файлы можно прочитать на экране и распечатать на принтере. Двоичные файлы не используют ASCII-коды, они часто имеют сложную внутреннюю структуру, например, объектный код программы или архивный файл. Все операционные системы должны уметь распознавать хотя бы один тип файлов - их собственные исполняемые файлы.

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

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

В разных файловых системах могут использоваться в качестве атрибутов разные характеристики, например:

• информация о разрешенном доступе,
• пароль для доступа к файлу,
• владелец файла,
• создатель файла,
• признак "только для чтения",
• признак "скрытый файл",
• признак "системный файл",
• признак "архивный файл",
• признак "двоичный/символьный",
• признак "временный" (удалить после завершения процесса),
• признак блокировки,
• длина записи,
• указатель на ключевое поле в записи,
• длина ключа,
• времена создания, последнего доступа и последнего изменения,
• текущий размер файла,
• максимальный размер файла.

Каталоги могут непосредственно содержать значения характеристик файлов, как это сделано в файловой системе MS-DOS, или ссылаться на таблицы, содержащие эти характеристики, как это реализовано в ОС UNIX (рисунок 2.31). Каталоги могут образовывать иерархическую структуру за счет того, что каталог более низкого уровня может входить в каталог более высокого уровня (рисунок 2.32).

Рис. 2.31. Структура каталогов: а - структура записи каталога MS-DOS (32 байта);
б - структура записи каталога ОС UNIX

Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть - если файл может входить сразу в несколько каталогов. В MS-DOS каталоги образуют древовидную структуру, а в UNIX'е - сетевую. Как и любой другой файл, каталог имеет символьное имя и однозначно идентифицируется составным именем, содержащим цепочку символьных имен всех каталогов, через которые проходит путь от корня до данного каталога.

Рис. 2.32. Логическая организация файловой системы
а - одноуровневая; б - иерархическая (дерево); в - иерархическая (сеть)