- •Семафоры. Синхронизация процессов при помощи семафоров.
- •Организация параллелизма с помощью монитора. Кольцевой буфер.
- •Проблемы тупиков. Бесконечное откладывание и старение процессов.
- •Концепция ресурсов. Четыре необходимых условия возникновения тупика. Стратегия предотвращения тупиков.
- •Графы распределения ресурсов. Простая тупиковая ситуация
- •6.9.2 Приведение графов распределения ресурсов
- •Алгоритмы обнаружения тупиков. Редукция графа распределения ресурсов.
- •Организация памяти. Стратегии управления памятью. Связное и несвязное распределение памяти.
- •Мультипрограммные системы. Разделы памяти фиксированного и переменного размеров. Свопинг в мультипрограммировании.
- •Концепция виртуальной памяти. Пространство виртуальных адресов.
- •Многоуровневая организация виртуальной памяти. Поблочное отображение. Страницы и сегменты.
- •Системы с комбинированной странично-сегментной организацией. Таблица процессов и преобразование адресов.
- •Стратегии вталкивания и размещения страниц.
- •Стратегия выталкивания страниц. Понятия рабочего множества и трешинга.
- •Подкачка страниц по запросу и с упреждением.
- •Управление процессорами. Планирование загрузки процессоров. Цели планирования.
- •11.2 Цели планирования
- •Планирование с переключением и без переключения. Интервальный таймер.
- •Приоритеты. Планирование по сроку завершения.
- •Планирование по принципу fifo. Размер кванта.
- •Планирование по принципам sjf, srt и hrn.
- •Многоуровневые очереди с обратными связями.
- •Требования, предъявляемые к операционной системе. Многозадачность и ее виды.
Организация параллелизма с помощью монитора. Кольцевой буфер.
Мониторы
Монитор — механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для обеспечения доступа к неразделяемым ресурсам.
В простейшем случае монитор состоит из мьютекса и набора процедур, взаимодействующих с общим ресурсом.
Монитор – это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, прич¨м в каждый момент времени им может пользоваться только один процесс. Монитор можно представить как комнату, от которой есть только один ключ. Если какой-то процесс намеревается воспользоваться этой комнатой и ключ находится снаружи, то этот процесс может отпереть комнату, войти в не¨ и воспользоваться одной из процедур монитора. Если ключа снаружи нет, то процессу придется ждать, пока тот, кто пользуется комнатой в данный момент, не выйдет из не¨ и не отдаст ключ. Кроме того, никому не разрешается в комнате оставаться навсегда.
Рассмотрим, например, некоторый ресурс, который выделяет соответствующий планировщик. Каждый раз, когда процесс желает получить этот ресурс, он должен обратиться к планировщику. Процедуру планировщик разделяют все процессы, и каждый из них может обратиться к планировщику в любой момент. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура планировщик представляет собой пример монитора.
Таким образом, монитор – это механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для динамического распределения конкретного общего ресурса или группы общих ресурсов. Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору, который либо предоставит доступ, либо откажет в н¨м. Вход в монитор находится под ж¨стким контролем – здесь осуществляется взаимоисключение процессов, так как в каждый момент времени только один процесс может пользоваться монитором. Процессам, которые хотят войти в монитор, когда он уже занят, приходится ждать, прич¨м режимом ожидания управляет сам монитор. При отказе в доступе монитор блокирует обратившийся к нему процесс и определяет условие, по которому процесс жд¨т. Проверка условия выполняется самим монитором, который и деблокирует ожидающий процесс.
Внутренние переменные монитора могут быть либо глобальными (используемыми всеми процедурами монитора), либо локальными (используемыми только в своих процедурах). Обращение к этим переменным возможно только изнутри монитора. При первом обращении к монитору инициализируются начальные значения переменных. При последующих обращениях используются те значения переменных, которые остались от предыдущего обращения.
Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, эта процедура монитора выда¨т команду WAIT с указанием условия ожидания. В этом случае, процесс, переводящийся в режим ожидания, будет ждать момента, когда необходимый ресурс освободится. Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе. В этом случае монитор выда¨т команду извещения (сигнализации) SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и войти в монитор. Если монитор сигнализирует о возвращении ресурса, и в это время нет процессов, ожидающих такого ресурса, то он вносится в список свободных ресурсов.
Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ресурса, со временем его получит, считается, что ожидающий процесс имеет более высокий приоритет, чем новый процесс, пытающийся войти в монитор.
Рассмотрим пример монитора для выделения одного ресурса.
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.
Использование монитора в качестве средства синхронизации и связи освобождает процессы от необходимости явно разделять между собою ресурсы, так как доступ к разделяемым переменным всегда ограничен телом монитора. Поскольку мониторы входят в состав ядра ОС, то разделяемые переменные становятся системными переменными. Этот факт автоматически исключает критические интервалы, так как в каждый момент монитором может пользоваться только один процесс.
Использование мониторов имеет ряд преимуществ по сравнению с низкоуровневыми средствами:
- локализация разделяемых переменных внутри тела монитора позволяет избавиться от малопонятных программных конструкций в синхронизируемых процессах;
- мониторы дают возможность процессам совместно использовать программные модули, представляющие критические секции (если несколько процессов совместно и одинаково используют некоторый разделяемый ресурс, то в составе монитора достаточно иметь одну копию соответствующей процедуры работы с этим ресурсом).
Кольцевой буфер
Применение кольцевого буфера (ring buffer) - обычный прием, когда нужно организовать поток данных между асинхронными по отношению друг к другу процессами - например, между получением данных по каналу связи и обработкой этих данных в программе. Кольцевой буфер является упрощенным аналогом очереди (queue), которая применяется в многозадачных операционных системах (Windows, Linux, FreeRTOS и многих других) для организации безопасного (thread-safe) обмена данных между потоками (синхронизации).
Кольцевой буфер может использоваться не только на прием, но и на передачу - например, если нужно быстро подготовленные где-то данные постепенно передавать с течением времени. Кольцевой буфер удобен прежде всего тем, что очень просто производить заполнение буфера, проверку наличия данных в буфере и выборку данных из буфера, при этом не нужно особенно беспокоиться о выходе данных за границу буфера, переполнении памяти и т. п. Кольцевой буфер позволяет корректно обмениваться данными между обработчиком прерывания и основной программой.
Кольцевой буфер является разновидностью буфера FIFO, First Input First Output (первый зашел - первый вышел). Принцип кольцевого буфера довольно прост - в памяти выделяется непрерывный блок размером обычно равным степени двойки (назовем его buffer), и два индекса (idxIN и idxOUT) - один индекс указывает на место для записи в буфер (idxIN), другой - на место чтения из буфера. Размер буфера, равный степени двойки, выбирается для того, чтобы удобно было манипулировать индексами, указывающими на данные буфера, с помощью инкремента/декремента и наложения маски (это будет понятно далее). Индекс - это обычное число, равное адресу ячейки буфера. Например, на ячейку buffer[0] указывает индекс, равный нулю. Количество бит индекса как раз равно степени двойки размера буфера. Максимально удобны буфера размером 256 байт - в этом случае в качестве индекса можно применить 1 байт, и маску при операциях с указателями уже накладывать не надо. Код получается в этом случае максимально быстрый и компактный. На рисунке показан принцип работы кольцевого буфера на примере буфера в 16 байт (желтым показаны еще не обработанные данные буфера):
Вот так, например, выделяется буфер:
#define BUF_SIZE 16 //размер буфера обязательно равен степени двойки!
#define BUF_MASK (BUF_SIZE-1)
u8 idxIN, idxOUT;
char buffer [BUF_SIZE];
При помещения значения value в буфер используется индекс idxIN. Это делается так:
buffer[idxIN++] = value;
idxIN &= BUF_MASK;
Значение константы BUF_MASK равно размеру буфера минус 1 (при условии, что размер буфера равен степени двойки). При таком принципе работы с индексом происходит автоматический переход на начало буфера, как только мы достигли его конца.
Операция выборки из буфера происходит похожим образом, только используется индекс idxOUT:
value = buffer[idxOUT++];
idxOUT &= BUF_MASK;
Теперь становится понятным, почему при размере буфера 256 байт и байтовом индексе не нужна операция наложения маски - переход в ноль индекса при достижении конца буфера происходит автоматически.
Проверка на наличие данных в буфере происходит очень просто - если idxIN не равен idxOUT, то в буфере есть данные, в противном случае данных в буфере нет. Индекс idxOUT как-бы постоянно догоняет индекс idxIN при работе с данными буфера. Если догнал - значит, считывать из буфера больше нечего.
if (idxIN != idxOUT)
{
//данные есть, обрабатываем их
...
}
Сбросить данные буфера (т. е. удалить их оттуда) тоже очень просто - для этого в idxOUT записывают значение idxIN:
idxOUT = idxIN;
Иногда бывает необходимо знать, что не только данные в буфере есть, а еще нужно знать сколько именно байт данных в буфере. Для этого используется довольно простая процедура:
u8 idxDiff (u8 idxIN, u8 idxOUT)
{
if (idxIN >= idxOUT)
return (idxIN - idxOUT);
else
return ((BUF_SIZE - idxOUT) + idxIN);