Н.А. Беляков, Б.Е. Винтайкин
12
итератору и взять очередную атомарную часть задачи. Если же флаг
будет снят до того, как закончатся очередные вычисления функции
(10), то вычислительный поток не заметит, что его опрашивал плани-
ровщик. Если у очередного просматриваемого потока работы оста-
лось меньше, чем у найденного ранее «максимально загруженного»
потока, то флаг блокировки в этом очередном потоке снимается и
планировщик просматривает следующий поток. Если у очередного
просматриваемого потока работы осталось больше, то с потока, ко-
торый считался максимально загруженным до этого, снимается флаг
блокировки, и этот поток извещается, что он может продолжать ра-
боту. Очередной просматриваемый поток теперь считается макси-
мально загруженным – планировщик, не снимая с него флага блоки-
ровки, переходит к следующему потоку из набора и т. д., пока не бу-
дут просмотрены все потоки в наборе потоков.
5. Работа максимально загруженного потока делится планиров-
щиком поровну с помощью операции
split
итератора, и половина от-
дается завершившемуся ранее потоку, инициировавшему весь этот
процесс планирования, а половина остается у найденного потока.
6. Планировщик запускает на счет завершившийся ранее поток и
снимает флаг блокирования с найденного максимально загруженного
потока, извещая его при необходимости, что он может продолжать
работу.
7. «Максимально загруженный» поток может быть и не найден во
всем множестве потоков, если у каждого выполняющегося потока
осталось атомарных частей задачи меньше некоторого заданного ми-
нимума (например, меньше двух). В этом случае планировщик ниче-
го не делает, он ожидает завершения всех потоков.
На рис. 1 приведена упрощенная блок-схема алгоритма планиро-
вания (процесс планирования последовательный и выполняется в од-
ном потоке – потоке планировщика, поэтому его алгоритм можно
изобразить на блок-схеме), где i_max – индекс максимально загру-
женного потока в наборе потоков; r_max – оставшаяся работа (число
оставшихся значений параметров у максимально загруженного пото-
ка); r_max0 – некоторая минимальная порция параметров, при которой
деления не происходит (в пределе – атомарная порция); i_finished –
индекс завершившегося потока, инициировавшего процедуру плани-
рования (планировщик легко может его узнать); iter_lock(i) – функ-
ция блокировки итератора потока i; iter_unlock(i) – функция разбло-
кировки итератора потока i; remaining(i) – функция определения
оставшейся работы потока i; ir – оставшаяся работа у потока i;
threadsCount – число потоков в наборе; iter_split(i) – функция разбие-
ния итератора потока i пополам, возвращающая splitted_iter – итера-
тор, содержащий в себе половину значений итератора потока i (число
значений итератора в потоке i уменьшается соответственно);
iter_set(i, iter) – функция установки итератора iter в поток i.
