МОДЕЛИ ОЧЕРЕДЕЙ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ И СЕТЯХ. CТРУКТУРА СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ.

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

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

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

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

Cтруктура системы массового обслуживания

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

Основные элементы системы массового обслуживания (СМО) показаны на рисунке.

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

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

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