Алгоритмы планирования работы вс в различных режимах
При организации вычислительного процесса в ВС необходимо каждой программе выделить определенную совокупность ресурсов – необходимый объём оперативной памяти и внешней памяти, требуемые устройства ввода – вывода, процессорное время и время каналов ввода – вывода и внешних запоминающих устройств. Из – за ограниченности ресурсов, которыми располагает ВС, все программы не могут быть одновременно обеспечены ими, так что параллельно во времени может выполняться лишь часть программы, обеспечиваемая ресурсами ВС. Поэтому программы в ВС выполняются в основном последовательно, одна за другой, и в каждый момент времени ВС может обрабатывать ограниченное число задач, возможно только одну задачу.
Различный порядок выполнения работ приводит к различным эффектам. Например, рассмотрим выполнение процессором трёх программ А, В, С, с трудоёмкостью 6, 3 и 1 единиц процессорного времени соответственно. Возможны шесть различных планов выполнения указанных программ, различающихся порядком запуска последних. На рис. 11.3 приведены временные диаграммы выполнения программ для двух планов: P1=A, B, C и P6=C, B, A.
Из рис. 11.3 видно, что выполнение работ в порядке P1 приводит к окончанию работ A, B, C в момент времени 6; 9; 10 соответственно, и средние времена ожидания w1 и пребывания u1 работ в системе в этом случае будут иметь значения
.
0
1 2 3 4 5 6 7 8 9 10 11 12
Р
1
А В С
Р6
С В А
Рис.11.3. Временные диаграммы выполнения программ
При выполнении работ в порядке С,В,А значения w6 и u6:
Таким образом, изменение плана выполнения работ существенно повлияло на среднее время пребывания работ в системе.
Рассмотрим теперь, как изменение последовательности работ, осуществляемое на нескольких устройствах, влияет на суммарное время их выполнения.
Пусть имеются программы А и В, каждая из которых выполняется на устройстве 1, а затем на устройстве 2 (рис. 11.4). Трудоёмкость работ А и В равна (2;8) и (6;3) соответственно, где первая и вторая составляющие вектора характеризуют число секунд работы первого и второго устройства, необходимых для выполнения программ. Если сначала запустить программу В, а затем программу А (рис.11.4 а), то суммарное время выполнения работ составит 17 с. При запуске программ в обратном порядке время выполнения программ уменьшается до 13 с (рис.11.4, б). Очевидно, что второй план более предпочтителен, так как обеспечивает минимум времени выполнения программ за счет высокой степени совмещения их во времени.
Рис.11.4. Временные диаграммы выполнения программ на нескольких устройствах
Рассмотренные примеры показывают, что порядок запуска программ существенно влияет на характеристики ВС. Следовательно, в ВС должны быть встроены средства, обеспечивающие такой порядок запуска программ, который соответствовал бы назначению системы, например, минимизировал бы время пребывания программ в системе или время обработки пакета программ.
Процесс определения порядка выполнения программ во времени называется планированием. Основная цель планирования состоит в том, чтобы путем лучшей организации работы ВС (а не за счет увеличения числа ЭВМ и процессоров или их замены на более производительные) повысить эффективность функционирования системы. Планирование производится, исходя из имеющихся в ВС ресурсов, потребностей программ в ресурсах, приоритетов программ и критерия, определяющего качество планов.
Различают два основных вида планирования работы систем: неоперативное (называемое так же статическим или предварительным) и оперативное (динамическое).
Неоперативное планирование осуществляется для выработки планов заполнения некоторых наборов задач применительно к типовым ситуациям функционирования ВС. Следовательно, неоперативное планирование производится заранее, не в динамике функционирования ВС. При этом для каждой типовой ситуации составляются планы выполнения соответствующих заданных наборов задач (ЗНЗ), реализация которых происходит в процессе функционирования ВС по мере возникновения определенных ситуаций. Неоперативное планирование целесообразно проводить только для специализированных ВС с ограниченным перечнем решаемых задач, для каждой из которых составлены машинные программы, известны потребности в ресурсах ВС, необходимых для решения задач, частоты их решения и т.д.
Наборы задач должны быть достаточно стабильными, а надобность в их выполнении должна возникать неоднократно. В противном случае не окупаются затраты, связанные с планированием работы системы.
Оперативное планирование проводится в динамике функционирования ВС непосредственно перед началом peaлизации, поступившей в систему к данному моменту времени группы задач. Составленный план обычно корректируется с каждым поступлением в систему новой задачи. Оперативное планирование осуществляется с учетом сложившейся к моменту принятия решения ситуации по свободным и занятым ресурсам системы, наличия очередей для задач каждого приоритета. Оперативное планирование осуществляется при наличии данных о времени, необходимом на выполнение каждой программы.
По качеству решения задачи планирования различают: методы, позволяющие получить строго оптимальный план в смысле выбранного критерия; методы, позволяющие получить субоптимальные планы, и методы, позволяющие получить приближенные планы.
Строго оптимальный план распределения программ можно получить с помощью применения таких математических методов, как методы целочисленного и динамического программирования, но эти методы требуют большого объема вычислений и могут применяться только в тех случаях, когда не накладываются жесткие ограничения на время планирования.
Метод составления субоптимального плана является более предпочтительным по сравнению с предыдущими методами по трудоемкости и необходимой емкости ЗУ. Недостаток его состоит в том, что не позволяет получить строго оптимального плана. Он лишь обеспечивает получение одного из возможных решений, приближающегося к оптимальному.
Методы получения приближенных решений характеризуются тем, что при их использовании хотя и не обеспечивается получение минимального времени решения ЗНЗ, но зато по своей трудоемкости они являются наиболее пригодными для практики.