Программирование систем реального времени

ПРОГРАММИРОВАНИЕ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ КУРС ЛЕКЦИЙ (Заочное отделение) 1. Определение операционной системы Операционная система в наибольшей степени определяет облик всей вычислительной системы в целом. ОС выполняет две функции: обеспечение пользователю-программисту удобств посредством прикладного интерфейса и повышение эффективности использования компьютера путем рационального управления его ресурсами. ОС как прикладной интерфейс. Использование большинства компьютеров на уровне машинного языка затруднительно, особенно это касается ввода-вывода. Например, для организации чтения блока данных с жесткого диска программист может использовать 16 различных команд, каждая из которых требует 13 параметров, таких как номер блока на диске, номер сектора на дорожке и т. п. Когда выполнение операции с диском завершается, контроллер возвращает 23 значения, отражающих наличие и типы ошибок, которые, очевидно, надо анализировать. Даже если не входить в курс реальных проблем программирования ввода-вывода, ясно, что среди программистов нашлось бы не много желающих непосредственно заниматься программированием этих операций. При работе с диском программисту-пользователю достаточно представлять его в виде некоторого набора файлов, каждый из которых имеет имя. Работа с файлом заключается в его открытии, выполнении чтения или записи, а затем в закрытии файла. Вопросы подобные таким, как следует ли при записи использовать усовершенствованную частотную модуляцию или в каком состоянии сейчас находится двигатель механизма перемещения считывающих головок, не должны волновать пользователя. Программа, которая скрывает от программиста все реалии аппаратуры и предоставляет возможность простого, удобного просмотра указанных файлов, чтения или записи - это, конечно, операционная система. Точно также, как ОС ограждает программистов от аппаратуры дискового накопителя и предоставляет ему простой файловый интерфейс, операционная система берет на себя все малоприятные дела, связанные с обработкой прерываний, управлением таймерами и оперативной памятью, а также другие низкоуровневые проблемы. В каждом случае та абстрактная, воображаемая машина, с которой, благодаря операционной системе, теперь может иметь дело пользователь, гораздо проще и удобнее в обращении, чем реальная аппаратура, лежащая в основе этой абстрактной машины. С этой точки зрения функцией ОС является предоставление пользователю некоторой расширенной или виртуальной машины, которую легче программировать и с которой легче работать, чем непосредственно с аппаратурой, составляющей реальную машину. ОС как система управления ресурсами Идея о том, что ОС прежде всего система, обеспечивающая удобный интерфейс пользователям, соответствует рассмотрению сверху вниз. Другой взгляд, снизу вверх, дает представление об ОС как о некотором механизме, управляющем всеми частями сложной системы. Современные вычислительные системы состоят из процессоров, памяти, таймеров, дисков, накопителей на магнитных лентах, сетевых коммуникационной аппаратуры, принтеров и других устройств. В соответствии со вторым подходом функцией ОС является распределение процессоров, памяти, устройств и данных между процессами, конкурирующими за эти ресурсы. ОС должна управлять всеми ресурсами вычислительной машины таким образом, чтобы обеспечить максимальную эффективность ее функционирования. Критерием эффективности может быть, например, пропускная способность или реактивность системы. Управление ресурсами включает решение двух общих, не зависящих от типа ресурса задач: • планирование ресурса - то есть определение, кому, когда, а для делимых ресурсов и в каком количестве, необходимо выделить данный ресурс; • отслеживание состояния ресурса - то есть поддержание оперативной информации о том, занят или не занят ресурс, а для делимых ресурсов - какое количество ресурса уже распределено, а какое свободно. Для решения этих общих задач управления ресурсами разные ОС используют различные алгоритмы, что в конечном счете и определяет их облик в целом, включая характеристики производительности, область применения и даже пользовательский интерфейс. Так, например, алгоритм управления процессором в значительной степени определяет, является ли ОС системой разделения времени, системой пакетной обработки или системой реального времени. Эволюция ОС Первый период (1945 -1955) Известно, что компьютер был изобретен английским математиком Чарльзом Бэбиджем в конце восемнадцатого века. Его "аналитическая машина" так и не смогла но-настоящему заработать, потому что технологии того времени не удовлетворяли требованиям по изготовлению деталей точной механики, которые были необходимы для вычислительной техники. Известно также, что этот компьютер не имел операционной системы. Некоторый прогресс в создании цифровых вычислительных машин произошел после второй мировой войны. В середине 40-х были созданы первые ламповые вычислительные устройства. В то время одна и та же группа людей участвовала и в проектировании, и в эксплуатации, и в программировании вычислительной машины. Это была скорее научно-исследовательская работа в области вычислительной техники, а не использование компьютеров в качестве инструмента решения каких-либо практических задач из других прикладных областей. Программирование осуществлялось исключительно на машинном языке. Об операционных системах не было и речи, все задачи организации вычислительного процесса решались вручную каждым программистом с пульта управления. Не было никакого другого системного программного обеспечения, кроме библиотек математических и служебных подпрограмм. Второй период (1955 - 1965) С середины 50-х годов начался новый период в развитии вычислительной техники, связанный с появлением новой технической базы - полупроводниковых элементов. Компьютеры второго поколения стали более надежными, теперь они смогли непрерывно работать настолько долго, чтобы на них можно было возложить выполнение действительно практически важных задач. Именно в этот период произошло разделение персонала на программистов и операторов, эксплуатационщиков и разработчиков вычислительных машин. В эти годы появились первые алгоритмические языки, а следовательно и первые системные программы - компиляторы. Стоимость процессорного времени возросла, что потребовало уменьшения непроизводительных затрат времени между запусками программ. Появились первые системы пакетной обработки, которые просто автоматизировали запуск одной программ за другой и тем самым увеличивали коэффициент загрузки процессора. Системы пакетной обработки явились прообразом современных операционных систем, они стали первыми системными программами, предназначенными для управления вычислительным процессом. Третий период (1965 - 1980) Следующий важный период развития вычислительных машин относится к 1965-1980 годам. В это время в технической базе произошел переход от отдельных полупроводниковых элементов типа транзисторов к интегральным микросхемам, что дало гораздо большие возможности новому, третьему поколению компьютеров. Для этого периода характерно также создание семейств программно-совместимых машин. Первым семейством программно-совместимых машин, построенных на интегральных микросхемах, явилась серия машин IBM/360. Построенное в начале 60-х годов это семейство значительно превосходило машины второго поколения по критерию цена/произ-водительность. Вскоре идея программно-совместимых машин стала общепризнанной. Программная совместимость требовала и совместимости операционных систем. Такие операционные системы должны были бы работать и на больших, и на малых вычислительных системах, с большим и с малым количеством разнообразной периферии, в коммерческой области и в области научных исследований. Операционные системы, построенные с намерением удовлетворить всем этим противоречивым требованиям, оказались чрезвычайно сложными "монстрами". Они состояли из многих миллионов ассемблерных строк, написанных тысячами программистов, и содержали тысячи ошибок, вызывающих нескончаемый поток исправлений. В каждой новой версии операционной системы исправлялись одни ошибки и вносились другие. Однако, несмотря на необозримые для того времени размеры и множество проблем, OS/360 и другие ей подобные операционные системы машин третьего поколения действительно удовлетворяли большинству требований потребителей. Важнейшим достижением ОС данного поколения явилась реализация мультипрограммирования. Мультипрограммирование - это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются несколько программ. Пока одна программа выполняет операцию ввода-вывода, процессор не простаивает, как это происходило при последовательном выполнении программ (однопрограммный режим), а выполняет другую программу (многопрограммный режим). При этом каждая программа загружается в свой участок оперативной памяти, называемый разделом. Наряду с мультипрограммной реализацией систем пакетной обработки появился новый тип ОС - системы разделения времени. Вариант мультипрограммирования, применяемый в системах разделения времени, нацелен на создание для каждого отдельного пользователя иллюзии единоличного использования вычислительной машины. Четвертый период (1980 - настоящее время) Следующий период в эволюции операционных систем связан с появлением больших интегральных схем (БИС). В эти годы произошло резкое возрастание степени интеграции и удешевление микросхем. Компьютер стал доступен отдельному человеку, и наступила эра персональных компьютеров. На рынке операционных систем доминировали две системы: MS-DOS и UNIX. Однопрограммная однопользовательская ОС MS-DOS широко использовалась для компьютеров, построенных на базе микропроцессоров Intel 8088, а затем 80286, 80386 и 80486. Мультипрограммная многопользовательская ОС UNIX доминировала в среде "не-интеловских" компьютеров, особенно построенных на базе высокопроизводительных RISC-процессоров. В середине 80-х стали бурно развиваться сети персональных компьютеров, работающие под управлением сетевых или распределенных ОС. В сетевых ОС пользователи должны быть осведомлены о наличии других компьютеров и должны делать логический вход в другой компьютер, чтобы воспользоваться его ресурсами, преимущественно файлами. Каждая машина в сети выполняет свою собственную локальную операционную систему, отличающуюся от ОС автономного компьютера наличием дополнительных средств, позволяющих компьютеру работать в сети. Сетевая ОС не имеет фундаментальных отличий от ОС однопроцессорного компьютера. Она обязательно содержит программную поддержку для сетевых интерфейсных устройств (драйвер сетевого адаптера), а также средства для удаленного входа в другие компьютеры сети и средства доступа к удаленным файлам, однако эти дополнения существенно не меняют структуру самой операционной системы. 1. Операционные системы реального времени. ОС общего назначения, особенно многопользовательские, ориентированы на оптимальное распределение ресурсов компьютера между пользователями и задачами (системы разделения времени), В операционных системах реального времени (ОСРВ), подобная задача отходит на второй план - все отступает перед главной задачей - успеть среагировать на события, происходящие на объекте. 1.1. Описание и общие требования к системам реального времени. Применение операционной системы реального времени всегда связано с аппаратурой, с объектом, с событиями, происходящими на объекте. Система реального времени, как аппаратно-программный комплекс, включает в себя датчики, регистрирующие события на объекте, модули ввода-вывода, преобразующие показания датчиков в цифровой вид, пригодный для обработки этих показаний на компьютере, и, наконец, компьютер с программой, реагирующей на события, происходящие на объекте. ОСРВ ориентирована на обработку внешних событий. Именно это приводит к коренным отличиям (по сравнению с ОС общего назначения) в структуре системы, в функциях ядра, в построении системы ввода-вывода. ОСРВ может быть похожа по пользовательскому интерфейсу на ОС общего назначения, однако устроена она совершенно иначе. Кроме того, применение ОСРВ всегда конкретно. Если ОС общего назначения обычно воспринимается пользователями (не разработчиками) как уже готовый набор приложений, то ОСРВ служит только инструментом для создания конкретного аппаратно - программного комплекса реального времени. И поэтому наиболее широкий класс пользователей ОСРВ - разработчики комплексов реального времени, люди проектирующие системы управления и сбора данных. Проектируя и разрабатывая конкретную систему реального времени, программист всегда знает точно, какие события могут произойти на объекте, знает критические сроки обслуживания каждого из этих событий. Существует несколько определений систем реального времени (ОСРВ) (real time operating systems (RTOS)). 1. Системой реального времени называется система, в которой успешность работы любой программы зависит не только от ее логической правильности, но от времени, за которое она получила результат. Если временные ограничения не удовлетворены, то фиксируется сбой в работе системы. Таким образом, временные ограничения должны быть гарантированно удовлетворены. Это требует от системы быть предсказуемой, т.е. вне зависимости от своего текущего состояния и загруженности выдавать нужный результат за требуемое время. При этом желательно, чтобы система обеспечивала как можно больший процент использования имеющихся ресурсов. Хорошим примером задачи, где требуется ОСРВ, является управление роботом, берущим деталь с ленты конвейера. Деталь движется, и робот имеет лишь маленькое временное окно, когда он может ее взять. Если он опоздает, то деталь уже не будет на нужном участке конвейера, и, следовательно, работа не будет сделана, несмотря на то, что робот находится в правильном месте. Если он позиционируется раньше, то деталь еще не успеет подъехать, и он заблокирует ей путь. Другим примером может быть самолет, находящийся на автопилоте. Сенсорные датчики должны постоянно передавать в управляющий компьютер результаты измерений. Если результат какого-либо измерения будет пропущен, то это может привести к недопустимому несоответствию между реальным состоянием систем самолета и информацией о нем в управляющей программе. Система реального времени (СРВ) - это аппаратно-программный комплекс, реагирующий в предсказуемые времена на непредсказуемый поток внешних событий. Это определение означает, что: • Система должна успеть отреагировать на событие, произошедшее на объекте, в течение времени, критического для этого события. Величина критического времени для каждого события определяется объектом и самим событием, и, естественно, может быть разной, но время реакции системы должно быть предсказано (вычислено) при создании системы. Отсутствие реакции в предсказанное время считается ошибкой для систем реального времени. • Система должна успевать реагировать на одновременно происходящие события. Даже если два или больше внешних событий происходят одновременно, система должна успеть среагировать на каждое из них в течение интервалов времени, критического для этих событий. Различают системы реального времени двух типов - системы жесткого реального времени и системы мягкого реального времени. Системы жесткого реального времени не допускают никаких задержек реакции системы ни при каких условиях, так как: • результаты могут оказаться бесполезны в случае опоздания, • может произойти катастрофа в случае задержки реакции, • стоимость опоздания может оказаться бесконечно велика. Примеры систем жесткого реального времени - бортовые системы управления, системы аварийной защиты, регистраторы аварийных событий. Системы мягкого реального времени характеризуются тем, что задержка реакции не критична, хотя и может привести к увеличению стоимости результатов и снижению производительности системы в целом. Основное отличие между системами жесткого и мягкого реального времени можно выразить так: система жесткого реального времени никогда не опоздает с реакцией на событие, система мягкого реального времени - не должна опаздывать с реакцией на событие. 1.2. Параметры ОСРВ 1.2.1. Время реакции системы Почти все производители систем реального времени приводят такой параметр, как время реакции системы на прерывание (внешнее событие, сигнал с датчика). События, происходящие на объекте, регистрируются датчиками, данные с датчиков передаются в модули ввода-вывода (интерфейсы) системы. Модули ввода-вывода, получив информацию от датчиков и преобразовав ее, генерируют запрос на прерывание в управляющем компьютере, подавая ему тем самым сигнал о том, что на объекте произошло событие. Получив сигнал от модуля ввода-вывода, система должна запустить программу обработки этого события. Интервал времени - от события на объекте и до выполнения первой инструкции в программе обработки этого события и является временем реакции системы на события. Приблизительное время реакции в зависимости от области применения ОСРВ может быть следующим: математическое моделирование управляющих процессов - несколько микросекунд радиолокация - несколько миллисекунд складской учет - несколько секунд торговые операции _ несколько минут управление производством _ несколько минут некоторые химические реакции - несколько часов Видно, что времена очень разнятся и накладывают различные требования на вычислительную установку, на которой работает ОСРВ. 1.2.2. Время переключения контекста В операционные системы реального времени заложен параллелизм, возможность одновременной обработки нескольких событий, поэтому все ОСРВ являются многозадачными. Контекст задачи это набор данных, задающих состояние процессора при выполнении задачи. Обычно совпадает с набором регистров, доступных для изменения прикладной задаче. При переключении задач (процессов) необходимо: 1. корректно остановить работающую задачу; для этого а) выполнить инструкции текущей задачи, уже загруженные в процессор, но еще не выполненные; б) сохранить в оперативной памяти регистры текущей задачи; 2. найти, подготовить и загрузить затребованную задачу; 3. запустить новую задачу, для этого а) восстановить из оперативной памяти регистры новой задачи (сохраненные ранее, если она до этого уже работала); б) загрузить в процессор инструкции новой задачи. Каждая из этих стадий вносит свой вклад в задержку при переключении контекста. Поскольку любое приложение реального времени должно обеспечить выдачу результата в заданное время, то эта задержка должна быть мала и известна. Это число также является одной из важнейших характеристик ОСРВ. 1.2.3. Размеры системы Для систем реального времени важным параметром является размер системы исполнения, а именно суммарный размер минимально необходимого для работы приложения системного набора (ядро, системные модули, драйверы и т. д.). Этот параметр является критичным для встраиваемых систем – где загрузка операционной системы происходит из ПЗУ микроконтроллера. Хотя, надо признать, что с течением времени значение этого параметра уменьшается, тем не менее, он остается важным и производители систем реального времени стремятся к тому, чтобы размеры ядра и обслуживающих модулей системы были невелики. 1.3. Особенности оборудования, на котором работают ОСРВ Вычислительные установки, на которых применяются ОСРВ, можно условно разделитьна три группы. 1. «Обычные» компьютеры. По логическому устройству совпадают с настольными системами. Аппаратное устройство несколько отличается. Для обеспечения минимального времени простоя в случае технической неполадки процессор, память и т.д. размещены на съемной плате, вставляемой в специальный разъем так называемой «пассивной» основной платы. В другие разъемы этой платы вставляются платы периферийных контроллеров и другое оборудование. Сам компьютер помещается в специальный корпус, обеспечивающий защиту от пыли и механических повреждений. В качестве мониторов часто используются жидкокристалические дисплеи, иногда с сенсочувствительным покрытием. Подобные вычислительные системы обычно не используются для непосредственного управления промышленным или иным оборудованием. Они в основном служат как терминалы для взаимодействия с промышленными компьютерами и встроенными контроллерами, для визуализации состояния оборудования и технологического процесса. На таких компьютерах в качестве операционных систем часто используются «обычные» операционные системы с дополнительными программными комплексами, адаптирующими их к требованиям «реального времени». 2. Промышленные компьютеры. Состоят из одной платы, на которой размещены: процессор, контроллер памяти, память 4-х видов: • ПЗУ, постоянное запоминающее устройство (ROM, read-only memory), где обычно размещена сама ОСРВ; типичная емкость _ 500Kb; • ОЗУ, оперативное запоминающее устройство (RAM, random access memory), куда загружается код и данные ОСРВ; обычно организована на базе динамической памяти (dynamic RAM, DRAM); типичная емкость _ 16Mb; • статическое ОЗУ (static RAM, SRAM) (то же, что и ОЗУ, но питается от имеющейся на плате батарейки), где размещаются критически важные данные, которые не должны пропадать при выключении питания; типичная емкость _ 2Mb; типичное время сохранения данных _ 5 лет; • флеш-память (flash RAM) (электрически программируемое ПЗУ), которое играет роль диска для ОСРВ; типичная емкость -- 4Mb; контроллеры периферийных устройств: SCSI (Small Computer System Interface), Ethernet, COM портов, параллельного порта, несколько программируемых таймеров. На плате находится также контроллер и разъем шины, через которую компьютер управляет внешними устройствами. В качестве шины в подавляющем большинстве случаев используется шина VME, которую в последнее время стала теснить шина Compact PCI. Плата помещается в специальный корпус (крейт), в котором разведены разъемы шины и установлен блок питания. Корпус обеспечивает надлежащий температурный режим, защиту от пыли и механических повреждений. В тот же корпус вставляются платы аналого-цифровых и/или цифро-аналоговых преобразователей (АЦП и/или ЦАП) analog to digital and/or digital to analog converters, ADC and/or DAC), через которые осуществляется ввод/вывод управляющей информации, платы управления электромоторами и т.п. В тот же корпус могут вставляться другие такие же (или иные) промышленные компьютеры, образуя многопроцессорную систему. Промышленные компьютеры используются для непосредственного управления промышленным или иным оборудованием. Они часто не имеют монитора и клавиатуры, и для взаимодействия с ними служат «обычные» компьютеры, соединенные с ними через какой либо последовательный интерфейс. 3. Встраиваемые системы. Устанавливаются внутрь оборудования, которым они управляют. Для крупного оборудования (например, самолет) могут по исполнению совпадать с промышленными компьютерами. Для оборудования поменьше могут представлять собой процессор с сопутствующими элементами, размещенный на одной плате с другими электронными компонентами этого оборудования. Для миниатюрного оборудования (например, мобильный телефон) процессор с сопутствующими элементами может быть частью одной из больших интегральных схем этого оборудования. В дальнейшем под компьютером для ОСРВ мы будем понимать промышленный компьютер. Отметим основные особенности ОСРВ, диктуемые необходимостью ее работы на промышленном компьютере. • Система часто должна работать на бездисковом компьютере и осуществлять начальную загрузку из ПЗУ. В силу этого: ◦ критически важным является размер системы; ◦ для экономии места в ПЗУ часть системы часто хранится в сжатом виде и загружается в ОЗУ по мере необходимости; ◦ система часто позволяет исполнять код как в ОЗУ, так и в ПЗУ; ◦ при наличии свободного места в ОЗУ система часто копирует себя из медленного ПЗУ в более быстрое ОЗУ; ◦ сама система компилируется, линкуется и превращается в загрузочный модуль на другом, «обычном» компьютере, связанном с промышленным компьютером через последовательный порт или Ethernet; это требует специального кроссплатформенного инструментария разработчика, поскольку типы процессоров и/или операционных систем на этих двух компьютерах не совпадают. • Система по возможности должна поддерживать как можно более широкий ряд процессоров, что дает возможность потребителю выбрать процессор подходящей мощности. • Система по возможности должна поддерживать как можно более широкий ряд специального оборудования (периферийные контроллеры, таймеры и т.д.), которые могут стоять на плате компьютера и платах, которыми он управляет через общую шину. • Очевидно, что для получения законченной системы управления не достаточно промышленного компьютера, АЦП и/или ЦАП платы, крейта и ОСРВ. Нужно еще написать программу, которая будет непосредственно управлять конкретным промышленным оборудованием. Для этого необходим (кроссплатформенный) инструментарий разработчика, цена которого может превосходить цену перечисленных выше компонент, вместе взятых. Правда, этот инструментарий нужен только разработчику, и полученная программа может работать на многих компьютерах. • Критически важным параметром для ОСРВ является время ее реакции на прерывания (которое складывается из аппаратного времени задержки и программных задержек), а также предсказуемость этого времени. Механизмы реального времени 1.3.1. Система приоритетов и алгоритмы диспетчеризации Базовыми инструментами разработки сценария работы системы являются система приоритетов процессов (задач) и алгоритмы планирования (диспетчеризации) ОСРВ. В многозадачных ОС общего назначения используются, как правило, различные модификации алгоритма круговой диспетчеризации, основанные на понятии непрерывного кванта времени ("time slice"), предоставляемого процессу для работы. Планировщик по истечении каждого кванта времени просматривает очередь активных процессов и принимает решение, кому передать управление, основываясь на приоритетах процессов (численных значениях, им присвоенных). Приоритеты могут быть фиксированными или меняться со временем - это зависит от алгоритмов планирования в данной ОС, но рано или поздно процессорное время получат все процессы в системе. Алгоритмы круговой диспетчеризации неприменимы в чистом виде в ОСРВ. Основной недостаток - непрерывный квант времени, в течение которого процессором владеет только один процесс. Планировщики же ОСРВ имеют возможность сменить процесс до истечения непрерывного кванта времени, если в этом возникла необходимость. ОСРВ отличаются богатством различных алгоритмов планирования: динамические, приоритетные, монотонные, адаптивные и пр., цель же всегда преследуется одна - предоставить инструмент, позволяющий в нужный момент времени исполнять именно тот процесс, который необходим. Рассмотрим их более подробно. Модель цифровой управляющей системы. При управлении, каким либо процессом ЭВМ должна решать совокупность задач. Программы П1…Пn хранятся в постоянной или оперативной памяти ЭВМ. Они инициируются в порядке, определяемом процессами, происходящими в управляемом объекте и в самой ЭВМ. Причина инициирования программы называется заявкой. Заявки генерируются на объекте и поступают в ЭВМ периодически или в произвольные, случайные моменты времени. При этом за короткий отрезок времени может поступить несколько заявок Z1…Zn, для обслуживания которых должны быть выполнены соответствующие программы П1…Пn. При наличии одного процессора эти программы могут быть выполнены только последовательно, в связи, с чем возникают очереди на обслуживание. Модель функционирования ЦУС Обработка заявок организуется по следующей схеме. (рисую) Заявки Z1…Zn поступают в устройство организации прерываний. При появлении заявки Zi устройство прерывания инициирует в процессоре операцию прерывания, в результате выполнения которой процессор переключается на выполнение программы приема и постановки заявок в очередь, называемой ДИСПЕТЧЕР1. Это Д1на рисунке. Д1 опознает тип поступившей заявки и ставит заявку в соответствующую очередь Oi на обслуживание. Очередь в физическом отношении состоит из совокупности ячеек оперативной памяти, в которых размещаются коды поступивших заявок. В каждый момент времени процессор может выполнять только одну программу. Процесс выбора заявки из множества заявок, ожидающих обслуживания, называется диспетчированием. Процедура Диспетчирования реализуется программой ДИСПЕТЧЕР2 – Д2 на рисунке. Эта программа анализирует состояния очередей O1…On, выбирает заявку Zk, имеющую преимущественное право на обслуживание, и инициирует соответствующую прикладную программу Пк. Считается, что в момент окончания работы программы обслуженная заявка покидает систему. По окончании программы Пк управление вновь передается Д2, который выбирает очередную заявку и инициирует соответствующую прикладную программу. Если очереди пусты, Д2 переключает процессор в состояние ожидания. Таким образом, обработка заявки проводится в два этапа: На первом этапе заявка принимается Д1 в систему и ставится в очередь, где ожидает обслуживания. На втором этапе заявка выбирается Д2, который организует обслуживание заявки, инициируя соответствующую прикладную программу. Программы Д1 и Д2 управляют порядком обработки заявок и относятся к классу управляющих программ. Д1 является короткой программой, для выполнения которой требуется несколько десятков операций процессора. Она инициируется устройством прерывания в момент поступления на его вход очередной заявки. Правило диспетчирования, на основе которого из очередей выбираются заявки на обслуживание, называется дисциплиной обслуживания. Заданная дисциплина обслуживания реализуется управляющей программой – Д2. Функционирование ЦУС можно рассматривать как совокупность трех процессов: 1) Поступление заявок на вход системы 2) Диспетчерование 3) Обслуживание заявок Поступившая заявка инициирует прерывание в системе, процессор приостанавливает выполнение текущих задач и начинает обработку прерывания: 1) Запуск диспетчера 1. В функции диспетчера 1 входит определение типа заявки и поставление ее в очередь обслуживания (Oj) в зависимости от типа пришедшей заявки. 2) Д1 передает управление Д2. Д2 в зависимости от типа диспечеризации выбирает наиболее приоритетную заявку из очереди и запускает приложение необходимое для обработки данной заявки 2.3 Потоки заявок. Совокупность событий, распределенных во времени, называется потоком заявок. Пример потока заявок показан на рис. 3.3. Пример потока заявок Здесь t1, t2, ... — моменты возникновения событий, порождающих заявки. Различают входящие и выходящие потоки заявок, которые поступают в систему и соответственно покидают ее. В общем случае поток заявок рассматривается как случайный процесс, задаваемый функцией распределения промежутков времени между моментами поступления двух соседних заявок. Важнейшая характеристика потока —его интенсивность , равная среднему числу заявок, поступающих в единицу времени. – среднее число заявок, пришедшее в единицу времени или Интенсивность поступивших заявок. N – число пришедших заявок t – интервал времени за который поступили заявки Величина , обратная интенсивности, определяет средний интервал времени между двумя последовательными заявками 2.4 Стационарные и нестационарные потоки заявок. Различают стационарныеи нестационарные потоки заявок. Стационарным потоком заявок – называется поток заявок, у которого вероятностные характеристики не зависят от времени. Нестационарным потоком заявок – называется поток заявок, у которого вероятностные характеристики зависят от времени. Характеристики ЦУС определяются наиболее просто для стационарного режима функционирования системы, предполагающего стационарность потоков заявок. По этой причине нестационарные потоки аппроксимируются на отдельных отрезках времени стационарными. Так, например, поток заявок от абонентов, поступающий в АТС, не может считаться стационарным в течение суток, поскольку интенсивность разговоров ночью значительно ниже, чем днем (рис. 3.4) Рисунок 3.4 . Из приведенного графика видно, что наибольшая интенсивность приходится на период от 9'до 18 ч, в пределах которого с некоторым приближением поток может рассматриваться как стационарный. Еще можно привести пример про факел ракеты. 2.5 Простейший поток заявок. Простейшим потоком заявок называется поток обладающий следующими свойствами: 1. Стационарность – вероятностные характеристики потока не зависят от времени. 2. Отсутствие последействия - поступления заявки не зависит от времени прихода предыдущей заявки. 3. Ординарность – в каждый момент времени в систему поступает не более одной заявки. При простейшем потоке заявки обнаруживают тенденцию к группировке, что создает более тяжелые условия при работе системы по сравнению с другими распределениями потоков заявок. Поэтому предположение о том, что на вход системы поступает простейший поток заявок, приводит к определению предельных значений характеристик качества обслуживания. Если реальный поток отличен от простейшего, то система будет функционировать не хуже, чем это следует из полученных оценок. Основные характеристики качества функционирования ЦУС. Одной из важнейших характеристик качества функционирования ЦУС является загрузка системы: Где интенсивность поступления заявок в систему; - интенсивность обслуживания заявок. Заменяя величиной , где есть средняя длительность обслуживания одной заявки, получаем . Значение определяет среднее число заявок, поступающих в систему за среднее время обслуживания одной заявки. Наряду с этим величина загрузки характеризует долю времени, в течении которого обслуживающий прибор занят обслуживанием заявок, и одновременно вероятность того, что в произвольный момент времени процессор не простаивает Поскольку загрузка определяет вероятность того, что система занята обслуживанием, т.е. работает, то вероятность простоя определяется значением называемым коэффициентом простоя. При этом предполагается, что, , что справедливо для всех реальных систем. Все время работы системы можно условно разбить на два интервала: интервал переходного режима работы системы от момента начала работы системы до момента входа в стационарный режим и интервал стационарного режима. Стационарным (установившимся) режимом называется такой режим работы, при котором вероятностные характеристики работы системы не зависят от времени. Условие существования стационарного режима определяется значением загрузки Если , т.е. интенсивность поступления заявок превышает интенсивность их обслуживания, то работа системы характеризуется неограниченным возрастанием длины очереди заявок перед обслуживающим устройством, т.е. не существует стационарного режима работы системы. Глава 3. Дисциплины обслуживания заявок. 3.1 Бесприоритетная дисциплина обслуживания. При бесприоритетной дисциплине обслуживания заявки разных типов не имеют заранее определенных привилегий на досрочное обслуживание. Это правило выполняется, если заявки на обслуживание выбираются: 1) в порядке поступления (первой обслуживается заявка, поступившая раньше других); 2) в порядке, обратном порядку поступления заявок (первой обслуживается заявка, поступившая позже других); 3) наугад, т. е. путем случайного выбора из очереди. Дисциплина обслуживания в порядке поступления называется FIFO1 (первый при), а дисциплина обслуживания в обратном порядке-LIFO2. Эти три бесприоритетных дисциплины характеризуются одинаковым средним временем ожидания заявок, но дисциплина FIFO минимизирует дисперсию времени ожидания, т. е. уменьшает разброс времени ожидания относительно среднего значения. По этой причине дисциплина FIFO используется наиболее часто. Бесприоритетчюе обслуживание заявок на основе дисциплины FIFO организуется в соответствии со следующим рисунком Бесприоритетная дисциплина обслуживания где Пр -процессор и О - очередь для заявок типа z1, ..., zn. Вновь поступившая заявка заносится в конец очереди. Заявки выбираются на обслуживание из начала очереди. Примером может служить очередь заданий печати для принтера. 3.2 Дисциплина обслуживания с относительными приоритетами заявок Если требуется, чтобы заявки некоторого типа имели меньшее время ожидания (время пребывания), чем заявки других типов, то необходимо первым предоставить преимущественное право на обслуживание, называемое приоритетом. Приоритеты заявок характеризуются целыми положительными числами 1, 2, 3, ..., причем наиболее высокому приоритету соответствует меньшее число. Если приоритеты учитываются только в момент выбора заявки на обслуживание, то их называют относительными. Относительность приоритета связана со следующим. В момент выбора сравниваются приоритеты заявок, находящихся в состоянии ожидания, и обслуживание предоставляется заявке .с наиболее высоким приоритетом, например – заявке с приоритетом 3. После этого выбранная заявка захватывает процессор. Если в процессе обслуживания этой заявки поступают заявки с более высокими приоритетами, например с приоритетами 1 и 2, процесс обслуживания заявки, имеющей приоритет 3, не прекращается, т. е. эта заявка, захватив процессор, оказывается наиболее приоритетной. Т.е. приоритет заявок относителен – он имеет место только при свободном процессоре. При использовании относительных приоритетов обработка заявок организуется по следующей схеме. Дисциплина обслуживания с относительными приоритетами Заявкам типа zl ..., zm присвоены относительные приоритеты i, ..., М соответственно. Заявка zр поступившая в систему, заносится в очередь Ор, в которой хранятся заявки приоритета р=1, ....М. В очереди Oр заявки упорядочены по времени поступления. Когда процессор Пp заканчивает ранее начатое обслуживание, то управление передается программе ДИС­ПЕТЧЕР. ДИСПЕТЧЕР выбирает на обслуживание заявку с наи­большим приоритетом — заявку zi, если очереди О1 ..., Оi-1 не со­держат заявок. Выбранная заявка захватывает процессор Пр на все время обслуживания. 3.3 Дисциплина обслуживания с абсолютными приоритетами В ряде случаев время ожидания заявок некоторых типов нужно уменьшить в такой степени, которая недостижима при использовании относительных приоритетов. Можно предполагать, что время ожидания значительно уменьшится, если при поступлении высокоприоритетной заявки обслуживание ранее поступившей заявки с низ­шим приоритетом прерывается и процессор тут же предоставляется для обслуживания высокоприоритетной заявки. Дисциплина обслуживания, при которой высокоприоритетная заявка прерывает обслуживание заявки с низким приоритетом, называется дисциплиной обслуживания с абсолютными приоритетами. При использовании абсолютных приоритетов обслуживание за­явок организуется следующей схеме Дисциплина обслуживания с абсолютными приоритетами 1 — заявка, ожидающая обслуживания; 2 — прерванная заявка. Для каждого потока заявок z1 ..., zм организуется очередь O1 ..., Ом, в которой заявки раз­мещаются в порядке поступления. Заявкам z1; ..., zm соответствуют абсолютные приоритеты 1, .... М. Если процессор Пр занят обслуживанием заявки zi и на вход, поступает заявка типа zj, то при i <=j заявка zj заносится в конец очереди Оj, а при i > j обслуживание заявки zi прерывается, заявка zi заносится в начало очереди Оi и ДИСПЕТЧЕР переключает прибор на обслуживание заявки zj. Обслуживание прерванных заявок может проводиться: 1) от начала; 2) от момента прерывания (дообслуживание). По возможности стремятся использовать второй способ – дообслуживание прерванных заявок. ОП – кривая относительного приоритета; АП – кривая абсолютного приоритета. Присваивание заявкам абсолютных приоритетов приводит к уменьшению времени ожидания заявок с высокими приоритетами, но одновременно с этим увеличивается время ожидания низкоприоритетных заявок 3.4 Дисциплина обслуживания со смешанными приоритетами. В некоторых системах необходимо выполнить жесткие ограниче­ния на время ожидания отдельных заявок, что требует присваивания. им абсолютных приоритетов: В результате этого время ожидания низкоприоритетных заявок может оказаться недопустимо большим, хотя отдельные заявки и имеют запас по времени ожидания. Чтобы выполнить ограничения по всем видам заявок, можно наряду с абсолютными приоритетами некоторым заявкам присвоить относительные приоритеты, а остальные заявки обслуживать без приоритетов. Такая дисциплина обслуживания называется смешанной. Пусть в систему поступает М типов заявок. Если заявки обслуживать без приоритетов (дисциплина FIFO), то для заявок типа 1, ..... М1 среднее время ожидания может оказаться недопустимо большим. Если перейти к дисциплине с относительными приоритетами (кривая ОП), то для заявок типа 1, ...,М1 положение исправляется, но времена, ожидания заявок с низкими приоритетами превышают предельно допустимые значения. Если заявкам типа 1, ..., М1 присвоить относительные приоритеты 1, ..... М1, а заявки типа М1+1,... М обслуживать без приоритетов, то среднее время ожидания соответствует кривой СП удовлетворяет заданным ограничениям. Случаи использования других смешанных дисциплин обслуживания иллюстрируются ниже.