Детерминированные сети очередей

Рассмотрим систему, которая характеризуется наличием каналов прямого доступа в память со стороны накопителей на лентах (НМЛ) и дисках (НМД), а также со стороны терминалов объекта управления. Схема системы представлена на рис. 2.3.(а). Процессор  может запустить операции в каналах, освободившись для выполнения других задач. Каналы обеспечивают отработку операций управления в НМЛ и НМД, а также пересылку данных между ними и основной памятью. Запросы от терминалов объекта управления и обращения к ним со стороны системы обслуживаются каналом 4. Коэффициент мультипрограммирования в системе равен количеству терминалов объекта. Внутреннее управление системой реализуется аппаратными средствами (каналами, контроллерами дисков и т.п.) и программными средствами ОС. Одной из функций ОС является организация и отработка очередей к ресурсам системы. Очереди формируются к , каналам, каждому из НМД и НМЛ. Современные мультипрограммные ОС поддерживают одновременную обработку заданий путем разделения между ними системных ресурсов. При этом достигается максимальное совмещение прикладных задач пользователей при чередовании обработки на центральном процессоре и периферийных средствах.

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

На рис. 2.3 (б) изображена схема действия процесса, рассматриваемая с позиций проблемного программиста. Операции прикладной программы расположены в порядке их выполнения и включают: 1 – работа прикладной программы (счет 1); 2 – печать данных; 3 – обмен с НМД; 4 – работа прикладной программы (счет 2); 5 – выдача информации на объект управления. Макрокоманды запроса к печати, обмена с НМД и объектом управления интерпретируются управляющими программами ОС и инициируют работу соответствующих каналов. Эти операции пронумерованы следующими цифрами: 6 – выполнение программы управления печатью; 7 – выполнение программы управления НМД; 8 – управляющие действия на терминале объекта. Из рис. 2.3.(б) видно, что выполнение операций прикладной программы и ОС чередуется и в очереди к процессору размещаются запросы на обслуживание различного типа.

Рис. 2.3. (а) – функциональная схема системы; (б) – схема выполнения операций прикладной программы (процесса); (в) – сетевая модель процесса

Графическое представление путей движения процесса по узлам сети (очереди и ресурсы) рассмотрим на примере сети (рис. 2.3.(в)), построенной для отображения процесса (рис. 2.3. (б)). Сеть включает узлы ( - процессор,  - печать.  - НМД.  - терминал объекта), используемые процессом и очереди к ним за исключением узла , у которого очередь не возникает, так как число терминалов равно числу процессов в системе. Совокупность узлов и очередей соединена дугами, каждая из которых указывает возможные пути движения процессов. Процесс может занимать ресурс узла или находиться в очереди к нему. Если при переходе процесса между узлами сети происходит переход от операции  к операции , то у соответствующей дуги делается запись в виде . Поскольку рассматриваемый процесс создается по запросу от таймера, в модель введен нулевой узел , являющийся источником заявок. На дуге, соединяющей узлы  и  изображена запись , которая указывает на формирование начального значения атрибута-операции, которая становится равной 1. Обслужившись в узле  (этап счета 1), процесс создает запрос на печать, обращаясь к операции 6. Эта операция выполняется узлом , поэтому у дуги, соединяющей выход узла  и вход в очередь к нему, сделана запись . Эта запись указывает как дальнейший путь процесса после операции 1, так и новое значение его атрибута-операции. Если процесс по операции 6 обслужился в узле , то согласно схеме действий процесса (рис. 2.3. (б)) он должен уйти в узел . Формирование этой части маршрута процесса производится с помощью записи  у дуги между узлами  и . Аналогично делаются записи и у других дуг сети. Весь маршрут процесса можно представить последовательностью пар (узел, операция), указывающих на его состояния в динамике: (0, ), (, 1), (, 6), (, 2), (, 7), (, 3), (, 4), (, 8), (, 5), (,5), (, ). Первое и последнее состояние соответствует источнику и стоку модели.

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