IV Международная студенческая научная конференция Студенческий научный форум - 2012

Существует два основных способа построения диспетчеров задач в многопроцессорных системах: с разделением времени и разделением пространства [1]. Первый предполагает использование глобальной очереди готовых к обработке задач, второй - локальной очереди для каждого процессорного узла.

В диспетчерах с разделением времени существует явление перезагрузки кэш-памяти связанное с переключением задач, когда прерванная задача с высокой вероятностью может быть направлена для продолжения обслуживания в другой процессорный узел. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности многопроцессорной системы [1]. Однако модель с разделением времени балансирует загрузку процессоров, обеспечивая тем самым высокую степень параллелизма.

В диспетчерах с разделением пространства у каждого процессора имеется своя очередь задач, причем диспетчер взаимодействует только с одним процессором и его функция ограничивается выборкой очередной задачи и назначения её освободившемуся процессору. При прерываниях по истечении кванта (переключениях контекста) задача остается в той же очереди, в которой она находилась ранее. Таким образом, в вычислительной системе действует одновременно n планировщиков, в результате чего задачи выбираются из очередей бесконфликтно, поступают в процессоры параллельно, что создает условия для повышения производительности. Балансировка загрузки процессоров слабая, что приводит к «перекосу» в системе, когда часть процессоров может простаивать.

При проектировании новых многопроцессорных систем необходимо определить эффективность возможностей реализации. Одним из основных таких критериев является производительность. Для оценки потерь производительности в процессе диспетчеризации рассмотрены аналитические модели n-процессорных систем с алгоритмами планирования процессов по стратегии разделения времени (рис. 1, а) и разделения пространства (рис. 1, б). Модели представлены в виде разомкнутых стохастических сетей массового обслуживания (СМО). В модели с разделением времени заявка (задача), поступающая извне (источника S₀), или после переключения контекста, может быть назначена в любой процессор (ЦП), поэтому представляется  в виде многоканальной СМО (S₁). Так как в этом случае создается единственная (глобальная) очередь задач, которая является общим ресурсом для всех запрашивающих очередную задачу процессоров, то модель механизма доступа к этому ресурсу (диспетчеризации) представлена одноканальной СМО (S₂).

Модель с разделением пространства состоит из n одноканальных СМО (S₁,...,S_n). Каждая такая СМО моделирует обслуживание в процессорном узле, в состав которого входит ЦП и диспетчер. Источник S₀ моделирует потоки заявок ₀ (задач, поступающих от пользователей), и поглощает обслуженные заявки (выдача результата пользователю). Будем считать, что потоки заявок ₀ являются простейшими, а время обслуживания заявок v_i в каждом процессоре распределено по экспоненциальному закону [2].

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

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

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

В диспетчерах с разделением пространства время работы определяется выражением

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

Список литературы

1. Таненбаум Э. Современные операционные системы. Э.Таненбаум. 2-е издание, СПБ: Питер, 2002. - 1040 с.
2. Бикташев Р.А. и др. Разработка метода анализа архитектур вычислительных систем с использованием моделирования. Сборник трудов «Модернизация системы управления качеством образовательного процесса в высшей школе». - Пенза: Изд-во Пенз. гос. технол. акад.,2007 с.102-110.