Предположим, что у нас есть одна очередь независимых друг от друга задач (T1, T2,..., Tn). И есть пул рабочих потоков {w(1), ..., w(k)}. Каждый рабочий поток берет первую задачу из очереди, выполняет ее, после чего берет новую первую задачу и т.д. Если задач в очереди нет, рабочий поток засыпает. Когда в очередь добавляется новая задача и есть спящие рабочие потоки, один из них нужно разбудить.
Вроде все просто. Но есть нюанс...
Допустим, что очередь задач пуста. В нее попадает задача Ti. Просыпается какой-то поток w(j), берет ее и начинает выполнять. Очередь пуста. В процессе выполнения задачи Ti в очередь ставится новая задача T(i+1). В очереди появляется задача, значит какую-то из спящих нитей нужно разбудить. Правильно?
А вот правильно ли это или нет, зависит от того, как долго еще Ti будет работать на w(j). Если это время меньше или сравнимо со временем, необходимым на пробуждение какой-то другой рабочей нити w(g), то не нужно никого будить. Путь w(j) продолжит обслуживать Ti, после чего она спокойно возьмет T(i+1) из очереди с единственной задачей.
Это окажется гораздо дешевле, чем если будет разбужена w(g), она полезет в очередь, возьмет оттуда заявку. А где в это же время в эту же очередь полезет и w(j), которая только что завершила обработку Ti.
А вот если Ti еще долго будет работать после генерации T(i+1), тогда, действительно, имеет смысл разбудить w(g) и отдать T(i+1) ей.
Собственно, вопрос в том, как при постановке заявки T(i+1) в пустую очередь понять, имеет ли смысл кого-нибудь будить или нет. При том, что задача Ti в общем случае ничего про это сказать не может.
Такое ощущение, что лучше чуток подождать, прежде чем будить кого-нибудь. Мол, если заявка T(i+1) тяжелая, то небольшая задержка перед началом ее обработки погоды не сделает. А вот выгоду от того, что за T(i+1) возьмется та же самая рабочая нить вполне можно получить.
Осталось только понять, что означает это самое "чуток подождать". Ведь работает сейчас только w(j), а остальные все спят... "Чуток подождать" будет означать что-то вроде "выбрать w(g) и разбудить ее через какое-то время". Только вот про примитив "разбутить чужую нить через какое-то время" я пока не слышал :) Либо же остальные рабочие нити должны спать не постоянно, а "чутким сном", регулярно просыпаясь и проверяя рабочую очередь на непустоту...
Комментариев нет:
Отправить комментарий