Основные условия

Что должен знать каждый инженер о Частотно-Монотонной диспетчеризации: Учебник

(https://qnxclub.net/files/articles/rms/rms.html)

Аннотация: Данная статья представляет основные положения теории частотно-монотонной диспетчеризации для тех, кто не имеет сложившегося представления о ней. В статье представлены, и освещены примерами, основные теоремы и их расширения, включая синхронизацию потоков и не периодические события. Также в статье приводятся недостатки и критика указанного подхода. Приведенная ниже статья была сокращена в соответствии требований журнала Real-Time Magazine. Полный текст статьи можно получить в IEEE Computer Society Pres.

Автор: J.Zalewski, профессор, Department of Computer Science, Embry-Riddle Aeronaotical University.

Перевод: Елена Горошко.

1995 IEEE. ßeprinted, with Permission, from Advanced Multiprocessor Bus Architectures,

edited by Zalewski, IEEE Computer Society Press.

Real-Time Magazine - 95/1 p 6-24.

Введение

Теория частотно-монотонного анализа (ЧМА) появилась в контексте диспетчеризации задач в системе, где конечное количество периодических задач совместно использует единственный процессор. Теория ЧМА обеспечивает правила по которым происходит анализ, действительно ли данные задачи могут быть диспетчируемы согласно их характеристикам синхронизации. Естественно, что ситуация, в которой множественные аппаратные модули совместно используют монтажную шину, логически весьма подобна ситуации, в которой множественные задачи выполняются на одиночном процессоре. Запросы и от задач (потоков) и от модулей, должны быть диспетчируемы, чтобы получить доступ к ресурсу, за который они конкурируют: монтажной шине или процессору, соответственно.

Таким образом, общие результаты частотно-монотонного анализа, полученные для многозадачного режима на однопроцессорной вычислительной системе, являются одинаково применимыми к монтажной шине системы – если сделаны соответствующие замены условий. В этой статье обсуждаются принципы ЧМ диспетчеризации для множества задач, выполняющихся на одиночном процессоре, предполагая, что результаты могут быть применены и для монтажной шины системы. В статье делается акцент на основополагающие понятия и концепциях, исходя из предположения что читатель не имеет сложившегося представления о ЧМА.

Основные условия

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

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

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

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

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

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

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

В связи с вытеснением на основании приоритетов для увеличения реактивности системы, необходимо ответить на несколько вопросов. Например, если самый высокоприоритетный модуль может гарантировано получить доступ к шине в любое время, даже будучи способным вытеснить модуль, в настоящее время использующий шину прежде, чем его транзакция будет закончена – возникает немедленный вопрос о справедливости и голодании: Как мы вообще можем гарантировать, что модули самого низкого приоритета будут когда-либо получать доступ к шине? Относительно своевременности, возникает другой вопрос: Если есть много одновременных действий, как мы можем гарантировать, что все из них закончены вовремя? Если не все они могут закончиться своевременно, то кто сможет, и кто не сможет? Другими словами, есть потребность иметь метод количественного анализа поведения каждого модуля в терминах использования ресурса, за который тот конкурирует.

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

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

- могут ли задачи выполниться в их критические сроки обслуживания (deadlines)?

Stoyenko [2] дал первую формулировку проблемы, которая соответствует этим двум вопросам в терминах диспетчируемости (schedulability), которая является свойством набора задач, и гарантирует, что задачи все будут выполнены в срок их критического обслуживания. На языке модулей процессора, совместно использующих монтажную шину, набор запросов шины, сделанных этими модулями является диспетчируемым (schedulable), если запросы гарантированно получают доступ к шине и заканчивают транзакции вовремя (Определение "вовремя" предопределено для каждого модуля).

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