Алгоритмы диспетчирезации.

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

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

1. Проблему разделения процессорного времени между задачами.

2. Проблема планирования очередности выполнения задач с целью избежание конфликта за обладание системными ресурсами.

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

1. Предоставление каждому процессу справедливой доли процессорного времени.

2. Баланс нагрузки, то есть поддержание равномерной занятости всех частей системы.

3. Принудительное выполнение политики планирования и контроль за ее исполнение в системе.

Методы планирования мультипрограммных систем.

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

• Возвращается в очередь готовых процессов.

• Выходит из системы.

• Направляется в очередь заблокированных процессов.

Алгоритм планирования для такой системы состоит в:

1. Выборе процесса из совокупности готовых процессов.

2. Способе вычисления кванта времени для этого процесса.

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

Лекция номер 10.

Продолжение темы диспетчирезаии.

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

1. Хорошая загружаемость ресурсов.

2. Малое время простоя.

3. Разумная время ожидания для заданий пользователя.

4. Высокая пропускная способность.

Не всегда существенное улучшение одной из характеристик приводит к нужному результату как так очень часто рассматриваемые характеристики взаимосвязанны.

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

Существует три основных класса алгоритмов планирования:

1. Планирование по наивысшему приоритету.

2. Круговорот.

3. Планирование с обратной связью.

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

Рассмотрим эти классы:

Планирование по наивысшему приоритету. Метод состоит в том что процессор предоставляется тому процессу, который имеет наивысший приоритет, такой процесс в системе помечается флагом "highest priority level". Дальнейшие дествия зависят от вида системы: применяется в ней вытеснения или нет. Если вытеснения не применяется, то процесс получивший данный флаг получает процессор сразу после того как его освободит предыдущий процесс. Если в системе применяется вытеснеие то при появлении в системе высоко приоритетного процесса, выполнение текущего процесса прерывается и процессор отдается вновь прибывшему процессу, дальнейшие действия зависят от алгоритма принятого в конкретной системе. Возможные варианты:

1. Если в системе не появилось более высоко приоритетного процесса, процессор после завершения работы будет отдан тому процессу выполнение которого было прервана.

2. Планировщик производит пересчет динамического приоритета и по новому выстраивает очередь.

3. Если в системе имеется несколько прервавших выполнения процессов

Круговорот:

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

К минусам относятся достаточно долгое время ожидания для больших задач. У протого круговоррота для выбора кванта времени есть два варианта, q делается очень большим, в этом случае фактически режим первый пришел первый обслужен, квант времени очень маленький, третий вариант это оптимальный выбор.

Разновидности круговоротов:

1. Круговорот со смещением. Каждому процессу предоставляется квант времени величина которого зависит от внешнего приоритета процессора.

2. "эгоистический круговорот" при этом процесс входя в систему намеренно ожидает когда его приоритет возрастет и после этого в круговороте отправляется сразу на исполнение.

3. Круговорот использования очередей. Wqewqw

Не нашли, что искали? Воспользуйтесь поиском по сайту: