Prolog

для 7 задач и 3 процессоров. Вверху показано предшествование задач и величины продолжительности их решения. Например, задача t₅  требует 20 квантов времени, причем ее выполнение может начаться только после того, как будет завершено решение трех других задач   t₁,  t₂  и  t₃.   Показано два корректных плана: оптимальный план с временем окончания  24  и субоптимальный - с временем окончания  33.  В данной задаче любой оптимальный план должен содержать время простоя.

Coffman/ Denning, Operating Systems Theory, © 1973, p.86. Приведено с разрешения Prentice-Hall, Englewood Cliffs, New Jersey.

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

состояния - это частично составленные планы;

преемник частичного плана получается включением в план еще одной задачи; другая возможность - оставить процессор, только что закончивший свою задачу, в состоянии простоя;

стартовая вершина - пустой план;

любой план, содержащий все задачи, - целевое состояние;

стоимость решения (подлежащая минимизации) -время окончания целевого плана;

стоимость перехода от одного частичного плана к другому равна К₂ - К₁  где  К₁,   К₂  -  времена окончания этих планов.

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

Теперь нам необходимо принять решение относительно представления проблемных ситуаций, т.е. частичных планов. Нам понадобится следующая информация:

(1)        список ждущих задач вместе с их временами выполнения;

(2)        текущая загрузка процессоров задачами.

Добавим также для удобства программирования

(3)        время окончания (частичного) плана, т.е. самое последнее время окончания задачи среди всех задач, приписанных процессорам.

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

        [ Задача1/Т1, Задача2/Т2, ... ]

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

        [ Задача/ВремяОкончания ]

В списке  m  таких пар, по одной на каждый процессор. Новая задача будет добавляться к плану в момент, когда закончится первая задача из этого списка. В связи с этим мы должны