Развитие теории планирования в реальном времени

Планирование периодических и апериодических задач. Планирование с синхронизацией задач

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

Протокол предельного приоритета [24] позволяет из­бежать тупиковой ситуации и гарантирует ограниченную инверсию приоритетов за счет того, что высокоприоритетная задача может блокироваться самое большее одной низкоприоритетной. Чтобы предотвратить задержку высокоприоритетных задач низкоприоритет­ными на долгое время, применяется коррекция приоритетов. Когда низкоприори­тетная задача t₁ оказывается в критической области, она в состоянии блокировать высокоприоритетные задачи, которым нужен тот же ресурс. Если это происходит, то приоритет t₁ повышается до максимального из приоритетов блокируемых за­дач. Цель состоит в том, чтобы ускорить выполнение низкоприоритетной задачи и сократить время ожидания для высокоприоритетных.

Предельный приоритет Р двоичного семафора S – максимум из приоритетов всех задач, которые могут занять данный семафор. Таким образом, низкоприори­тетная задача, захватившая S, способна повысить свой приоритет до Р в зависи­мости от того, какие задачи она блокирует.

Еще одна возможная проблема – это тупиковая ситуация (deadlock), которая возникает, когда двум задачам нужно захватить по два ресурса. Если каждая задача захватит по одному ресурсу, то ни одна не сможет завершиться, поскольку будет ждать, пока другая освободит ресурс. Протокол предельного приоритета справля­ется и с такой трудностью [24].

Теоремы о планировании методом монотонных частот необходимо обобщить на задачу об инверсии приоритетов.

Теорию планирования в реальном времени можно применить к множеству параллельных задач либо на этапе проектирования, либо уже после реализации всех задач. Поскольку во время проектирования для времени ЦП существуют только приблизительные оценки, нужно быть осторожнее и при разработке задач реального времени с жесткими временными ограничениями полагаться на песси­мистическую теорему о верхней границе коэффициента использования. Эта тео­рема дает верхнюю границу 0,69 в худшем случае, хотя теория планирования в ре­альном времени часто указывает более высокие значения. Если верхняя граница в худшем случае не может быть достигнута, придется изучить альтернативные решения. С точки зрения проектировщика-пессимиста, оценка верхней границы коэффициента выше 0,69 приемлема при условии, что использование сверх 0,69 целиком обусловлено низкоприоритетными задачами с мягкими временными огра­ничениями или задачами, которые могут исполняться не в реальном масштабе вре­мени. Для таких задач эпизодический пропуск срока выполнения не столь важен.

Дата добавления: 2014-01-07