Существует два основных способа построения диспетчеров задач в многопроцессорных системах: с разделением времени и разделением пространства [1]. Первый предполагает использование глобальной очереди готовых к обработке задач, второй - локальной очереди для каждого процессорного узла.
В диспетчерах с разделением времени существует явление перезагрузки кэш-памяти связанное с переключением задач, когда прерванная задача с высокой вероятностью может быть направлена для продолжения обслуживания в другой процессорный узел. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности многопроцессорной системы [1]. Однако модель с разделением времени балансирует загрузку процессоров, обеспечивая тем самым высокую степень параллелизма.
В диспетчерах с разделением пространства у каждого процессора имеется своя очередь задач, причем диспетчер взаимодействует только с одним процессором и его функция ограничивается выборкой очередной задачи и назначения её освободившемуся процессору. При прерываниях по истечении кванта (переключениях контекста) задача остается в той же очереди, в которой она находилась ранее. Таким образом, в вычислительной системе действует одновременно n планировщиков, в результате чего задачи выбираются из очередей бесконфликтно, поступают в процессоры параллельно, что создает условия для повышения производительности. Балансировка загрузки процессоров слабая, что приводит к «перекосу» в системе, когда часть процессоров может простаивать.
При проектировании новых многопроцессорных систем необходимо определить эффективность возможностей реализации. Одним из основных таких критериев является производительность. Для оценки потерь производительности в процессе диспетчеризации рассмотрены аналитические модели n-процессорных систем с алгоритмами планирования процессов по стратегии разделения времени (рисунок, а) и разделения пространства (рисунок, б). Модели представлены в виде разомкнутых стохастических сетей массового обслуживания (СМО). В модели с разделением времени заявка (задача), поступающая извне (источника S0), или после переключения контекста, может быть назначена в любой процессор (ЦП), поэтому представляется в виде многоканальной СМО (S1). Так как в этом случае создается единственная (глобальная) очередь задач, которая является общим ресурсом для всех запрашивающих очередную задачу процессоров, то модель механизма доступа к этому ресурсу (диспетчеризации) представлена одноканальной СМО (S2).
Модель с разделением пространства состоит из n одноканальных СМО (S1,...,Sn). Каждая такая СМО моделирует обслуживание в процессорном узле, в состав которого входит ЦП и диспетчер. Источник S0 моделирует потоки заявок l0 (задач, поступающих от пользователей), и поглощает обслуженные заявки (выдача результата пользователю). Будем считать, что потоки заявок l0 являются простейшими, а время обслуживания заявок vi в каждом процессоре распределено по экспоненциальному закону [2].
При использовании стратегии разделения по времени вновь поступившая задача помещается в глобальную очередь (рисунок, а). Если имеется свободное место в очереди, то задача занимает его. Принятая на обслуживание задача находится в очереди до тех пор, пока не поступит на выполнение в один из процессоров. Если используется режим квантования, то незавершенная задача по окончании текущего кванта помещается в конец глобальной очереди, иначе результат выдается пользователю, а в очереди освобождается одно место. При завершении выполнения задачи диспетчер просматривает очередь, и если в ней имеются заявки на обслуживание, то назначается на выполнение задача, стоящая в голове списка. Если очередь пуста, свободные процессоры переходят в режим ожидания.
При использовании стратегии разделения в пространстве вновь поступившая задача помещается в очередь к одному из процессорных узлов (рисунок, б). Если имеется свободное место в одной из очередей, то задача занимает его. Принятая на обслуживание задача находится в локальной очереди до тех пор, пока не поступит на выполнение в процессор. Если используется режим квантования, то незавершенная задача по окончании текущего кванта помещается в конец той же очереди, где она находилась ранее, иначе результат выдается пользователю, а в локальной очереди освобождается одно место. При завершении выполнения задачи диспетчер просматривает локальную очередь. Если в ней имеются заявки на обслуживание, то назначается на выполнение задача, стоящая в голове списка. Если очередь пуста, процессор переходит в режим ожидания.
а
б
Схема аналитической модели n-процессорной системы с алгоритмами планирования процессов по стратегии разделения времени (а) и разделения пространства (б)
Считается, что приложения формируют простейшие потоки запросов, а времена обслуживания подчиняются экспоненциальному закону. Это распределение позволяет получить результаты заведомо хуже реальных значений, что в свою очередь позволит сделать оценку полученных результатов сверху. В диспетчерах с разделением времени время выполнения задачи определяется выражением
t = k(v + rω),
где ν - время обслуживания задачи процессором; ρ - вероятность перезагрузки кэш из-за возможного переназначения задачи, получающей дообслуживание после переключения контекста; ω - время перезагрузки кэш данными обслуживаемой задачи; k - среднее число квантов, требуемое для реализации задачи.
В диспетчерах с разделением пространства время работы определяется выражением
t = k(v + τ),
где τ - время переключения контекста диспетчером. Зная параметры моделей (ν, r, ω, τ) можно легко получить временные характеристики решаемых задач, например, загрузку процессоров, время ответа и др.
Список литературы
1. Таненбаум Э. Современные операционные системы. - 2-е изд. - СПб.: Питер, 2002. - 1040 с.
2. Бикташев Р.А. и др. Разработка метода анализа архитектур вычислительных систем с использованием моделирования // Модернизация системы управления качеством образовательного процесса в высшей школе: сборник трудов. - Пенза: Изд-во Пенз. гос. технол. акад., 2007. - С. 102-110.