Лекция №8. Построение очереди процессов

План лекции.

1. Приоритеты процессов

2. Методы построения очереди

3. Механизмы синхронизации

4. Защита от инверсии приоритетов

Построитель очереди Kernel-а принимает решения когда:

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

• кончается отрезок времени для работающего процесса

• выгружается работающий процесс

1. Приоритеты процессов

В QNX каждому процессу присваивается приоритет. Построитель очереди выбирает следующий процесс для исполнения глядя на приоритеты присвоенные каждому готовому к исполнению процессу. (Готовым считается тот, который может пользоваться CPU). Запускается процесс с наивысшим приоритетом.

Очередь из 6-и процессов (A-F) готовых к исполнению. Все остальные процессы (G-Z) заблокированы. Сейчас исполняется процесс А. У процессов A, B и C - наивысший приоритет, поэтому они будут совместно использовать CPU, основываясь на алгоритме построения очереди действующего процесса.

Уровни приоритета начинаются с 0 (самый низкий) и заканчиваются 31 (самый высокий). Новому процессу по умолчанию присваивается приоритет его родителя. Для приложений запускаемых Shell он обычно равен 10.

Если вы хотите:	то используйте:
узнать приоритет процесса	функцию С getprio()
установить приоритет процесса	функцию С setprio()

2. Методы построения очереди

Для того чтобы соответствовать потребностям различных приложений, в QNX есть три метода:

• FIFO

• карусель

• адаптивное построение очереди

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

Запомните, что эти методы применимы, когда существуют два и более процессов с одинаковым приоритетом и готовые к исполнению (т.е. процессы напрямую конкурируют друг с другом). Если вдруг появляется процесс с более высоким приоритетом, то он обходит всех остальных.

В приведенном ниже примере три процесса с одинаковым приоритетом готовы к исполнению.

Если процесс А блокируется то будет выполняться процесс В.

A blocks B runs

Процесс А блокируется, процесс В исполняется

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

Если хотите:	то используйте:
Узнать метод процесса	функция С getscheduler()
Установить новый метод	функция С setscheduler()

FIFO

При построении очереди по методу FIFO процесс, выбранный для исполнения продолжает осуществляться до тех пор, пока он:

• добровольно не отдаст управление (т.е. заблокируется)

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

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

Карусельный метод

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

• добровольно не отдаст управление

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

• исчерпает отведенное ему время

Каждому процессу отводится квант времени. Как только оно кончается -- процесс вытесняется следующим процессом с таким же приоритетом и готовым к исполнению. Квант принят равным 100 миллисекунд.

За исключением лимита времени карусельный метод совпадает с методом FIFO.

Адаптивное построение очереди

В адаптивном методе процесс ведет себя следующим образом:

• Если процесс выработал свой квант времени (т.е. не заблокировался) то его приоритет уменьшается на единицу, если есть готовый к исполнению процесс такого же приоритета. Это называется разрушением приоритета.

• Если приоритет процесса совсем разрушен и процесс выпадает из очереди более чем на 1 секунду, то приоритет вырастает на единицу (приоритет не может вырасти больше своего исходного значения).

• Если процесс блокируется, то ему немедленно возвращается исходный приоритет.

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

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

Приоритет, задаваемый клиентом

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

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

Если клиент с низким приоритетом посылает сообщение серверу, то оно будет обрабатываться с более высоким приоритетом сервера. Косвенно это поднимает приоритет клиента, так как это его запрос запускает сервер. Обычно это не важно, если сервер занят недолго. Но если он занят на продолжительное время, то это может отрицательно влиять на другие процессы, приоритет которых выше чем у клиента, но ниже чем у сервера.

Чтобы решить эту проблему сервер может выбрать, чтобы его приоритет зависел от клиента, который послал сообщение. Когда сервер получает сообщение, его приоритет устанавливается равным приоритету клиента. Обратите внимание, что изменяется только приоритет, метод построения очереди остается прежним. Если в момент когда сервер работает приходит новое сообщение -- то приоритет сервера будет увеличен если приоритет нового клиента выше. То есть новое сообщение разгоняет сервер, позволяя ему быстрее разобраться с предыдущим сообщением. Если этого не делать, то у нового клиента за счет блокировки на "медленном" сервере будет понижаться приоритет.

Если вы выбрали чтобы приоритет сервера устанавливался клиентом, надо так же обеспечить, чтобы сообщения обрабатывались по приоритету, а не по времени поступления.

Для выбора приоритета задаваемого клиентом следует использовать функцию С qnx_pflags() следующим образом:

qnx_рflags (~0, _PPF_PRIORITY_FLOAT

| _PPF_PRIORITY_REC, 0, 0);

Механизмы синхронизации

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

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

Защита от инверсии приоритетов

Итак, проблема инверсии приоритетов оказалась настолько важной для ОСРВ, что реализацию в системе механизмов за­щиты от этой проблемы вынесли в отдельное функциональное требование к операционным системам реального времени [1]. Давайте разберемся, что это такое? Инверсия приоритетов воз­никает, когда два потока, высоко приоритетный (В) и низко­приоритетный (Н) разделяют некий общий ресурс (Р). Пред­положим, также что в системе присутствует третий поток, при­оритет которого находится между приоритетами Ви Н. Назовем его средним (С). Если поток В переходит в состояние готовно­сти, когда активен поток Я, и Я заблокировал ресурс Р, то поток В вытеснит поток Н, и Р останется заблокирован. Когда В понадобится ресурс Р, то он сам перейдет в заблокирован­ное состояние. Если в состоянии готовности находится только поток Н, то ничего страшного не произойдет, Н освободит заблокированный ресурс и будет вытеснен потоком В. Но если на момент блокирования потока В в состоянии готовности на­ходится поток С, приоритет которого выше чем у Я, то актив­ным станет именно он, а Н опять будет вытеснен, и получит управление только после того, как С закончит свою работу. Подобная задержка вполне может привести к тому, что кри­тическое время обслуживания потока В будет пропущено. Если В — это поток жесткого реального времени, то подобная ситу­ация недопустима.

Какие же механизмы защиты от этой проблемы используют разработчики операционных систем реального времени? Наи­более широко распространенный и проверенный механизм — это наследование приоритетов.

Суть этого метода заключается в наследовании низкбприо-ритетным потоком, захватившим ресурс, приоритета от высо­коприоритетного потока, которому этот ресурс нужен. В опи­санном примере это означает следующее. Если Н блокировал ресурс Р, который нужен В, то при блокировании В его при­оритет присваивается потоку Н, и, таким образом, он не мо­жет быть вытеснен потоком, с меньшим чем у В приоритетом. После того, как поток Н разблокирует ресурс Р, его приори­тет понижается до исходного значения и он вытесняется пото­ком В.

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

Другой, несколько менее распространенный метод, называ­ется Протокол Предельного Приоритета (Priority Ceiling Pro­tocol) [6].

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