Эта идея пришла мне в голову очень давно и даже где-то была мной описана. Триггер к тому, чтобы её описать сегодня — обсуждение сетевых драйверов Линукса в комментариях к Анатомии драйвера.
Сформулирую проблему, описанную там, как я её понимаю: сетевой драйвер Линукса работает в отдельной нити, которая читает принятые пакеты из устройства и синхронно их обрабатывает. Прогоняет через роутинг, файрволл и, если пакет не нам, отправляет его в исходящий интерфейс.
Понятно, что некоторые пакеты обслуживаются быстро, а иные могут потребовать много времени. В такой ситуации хотелось бы иметь механизм, который динамически порождает обслуживающие нити по мере необходимости, и механизм достаточно дешёвый в ситуации, когда лишние нити не нужны.
То есть хотелось бы такого вызова функции, который при необходимости можно конвертировать в старт нити. Но по цене вызова функции, если нить реально не оказалась нужна.
Мне эта идея пришла когда я рассматривал совершенно фантастические модели для Фантом, включая акторную модель с запуском нити вообще на любой вызов функции/метода. Саму модель я отбросил, а вот идея lazy threads осталась и до сих пор кажется интересной.
Как это.
Предположим, что мы запускаем функцию void worker( packet ), которая должна что-то молча свершить. Нас не интересует код возврата (или он отдаётся нам асинхронно), и мы бы хотели выполнить функцию в рамках нашей нити, если она короткая, и в рамках отдельной, если длинная.
Понятие «длинная» здесь открыто, но разумно было бы для него применить простую точку оценки — если мы уложились в собственный квант планирования — функция короткая. Если в течение жизни функции случился preemption и у нас забирали процессор — длинная.
Для этого запустим её через прокси lazy_thread( worker, packet ), который выполняет очень простую операцию — фиксирует ссылку на стек в момент перед вызовом функции worker в специальной очереди lazy_threads_queue, и заменяет стек на новый:
push( lazy_threads_queue, arch_get_stack_pointer() );
arch_set_stack_pointer(allocate_stack())
Если worker вернулся, то отменим эту операцию:
tmp = arch_get_stack_pointer()
arch_set_stack_pointer( pop( lazy_threads_queue ) );
deallocate_stack(tmp)
И продолжим как ни в чём не бывало. Всё обошлось нам в пару строк кода.
Если же прошло значительное время, а worker всё ещё работает, произведём простую операцию — в точке смены стека выполним раздвоение нитей постфактум: сделаем вид, что внутри lazy_thread() произошло полноценное создание нити: скопируем свойства старой нити в новую, адрес возврата на новом стеке (который мы выделили в lazy_thread) переставим так, чтобы он указывал на функцию thread_exit(void), а в старой нити указатель следующей инструкции установим на точку выхода из функции lazy_thread.
Теперь старая нить продолжает работу, а новая исполнит начатое, и уничтожится там, где она в оригинальном сценарии вернулась бы из lazy_thread.
То есть: фактическое решение о запуске нити для обработки определённого запроса произошло уже после того, как мы начали его выполнять и смогли оценить фактическую тяжесть этого запроса. Можно наложить на точку принятия решения о запуске ленивой нити дополнительные ограничения — например, средний load average за 15 сек меньше 1.5/процессор. Если он выше — распараллеливание вряд ли поможет, мы больше потратим ресурсов на старты бессмысленных нитей.
В современном мире, когда обычное дело — 4 процессора в карманной машине и 16 в настольной, явно нужны механизмы, которые помогают коду адаптироваться к нагрузочной способности аппаратуры. Может быть — так?
Комментарии (47)
timapple
29.04.2016 14:50>> Если же прошло значительное время, а worker всё ещё работает, произведём простую операцию
Поясните пожалуйста, кто и когда это делает, если поток выполнения сейчас внутри worker'а?
KyHTEP
29.04.2016 14:50А не могли бы вы придумать несколько сценариев применения данного подхода?
Меня озадачивает самый плохой случай, когда кванта хватает впритык, и поток вызывающий по сути тратит время на функцию, которая могла бы быть в потоке сразу. Плюс мы же не знаем в каком моменте кванта мы вызвали лейзи тред. Т.е. мы можем вызвать и в конце своей порции и в начале.
Я сходу не смог придумать случай, когда это востребовано. Сразу скажу, что думал в контексте геймдева. В прикладных вещах, мне кажется, проблем особых не стоит, и, если уж, например, понадобился быстрый отклик от интерфейса, то все решается по принципу: есть гуй тред, а есть тред расчетов.
dzavalishin
29.04.2016 15:45В самом начале описано: рантайм балансировка числа тредов для обработки запросов. Например, запросов на маршрутизацию пакетов.
KyHTEP
30.04.2016 11:37+1Честно говоря не понял, почему одни пакеты могут «настолько» дольше обрабатываться, чем другие на уровне драйвера. А можете еще найти вариантов для прикладников, а не для драйвера, если не вас не затруднит?
PS: А как быть с временем ожидания выхода из функции? Т.е. вызвавший функцию поток спит или нет, пока выполняется запущенная нить?
результат нас может не интересовать, но может интересовать последовательность выполнения фунцкийdzavalishin
30.04.2016 15:29http сервер. запустивший спит, пока это функция и не спит, когда она нить. это надо рассматривать семантически как запуск нити, который в удачном случае оптимизируется в вызов функции.
KyHTEP
01.05.2016 07:34Я понимаю, как работает ваша идея. Я не понимаю применения в сравнении с другими методами.
Как это можно использовать в http-сервере мне тоже не понятно.
Есть сервер, туда идут запросы, они парсятся, результат отдается.
Мы делаем либо на нескольких потоках с примитивами синхронизации, либо плодим кучу потоков на каждый запрос и там выполняем все последовательно.
Ну даже предположить, что вы говорите о варианте «плодить кучу потоков» и, если запрос быстро выполнился, то поток не запускается, то вам все равно надо использовать синхронизацию для ситуации, когда поток запустится, что рождает дополнительную головную боль и именно это я хочу сказать. Вместо двух вариантов, последовательного и параллельного, мы получаем третий последовательно-параллельный.
Одно дело, когда вы точно знаете, что вам надо синхронизироваться, это одна парадигма, и другое дело, когда вы не знаете как дело пойдет, и придется учитывать оба варианта сразу.
Прикладных задач, где это будет лучше я не вижу, поэтому просил примеры, чтобы лучше понять вашу идею.
В общем, я вижу что задаю уже третий вопрос, ответа не увидел ни на один, извините за назойливость, больше тревожить не буду )dzavalishin
01.05.2016 13:26Замнём для ясности. У меня тоже нет какой-то сногсшибательной картины, которая бы явила абсолютную ясность. Разве что данный механизм проще в применении, чем тредпул, и является его заменой.
Duduka
01.05.2016 14:30+1Может я и слепой, но в статье я не увидел ничего иного, кроме описания событийно-ориентированного программирования, с очередным костылем. Поток событий порождает, с разной интенсивностью, поток исполнителей, существующих в едином контексте, что приводит к необходимости все синхронизировать, я правильно понял? Если правильно, то видится, что в очередной раз «создаются проблемы, и героически решаются». 1) Единый контекст, если нет ограничения наложенных транзакциями, то почему каждой нити не отдать свое псевдо-устройство? (т.е. перенести момент управления устройством на момент синхронизации псевдо устройства и реального) 2) За синхронизацию и разделение контекста не отвечают мониторы(акторы); состояния можно выпилить из нитей отдав их акторам, не блокируя сразу весь контекст для сложного драйвера, но огрести все проблемы множественной блокировки; в решении «Global Lock» получаем бессмысленность разделения на потоки, в решении «обмен сообщениями», получаем задержки и расходы на очередь.
Т.е. требование «одно устройство — одно состояние» делает бессмысленным многозадачность для управления им, каким бы «толстым» оно не было.
lorc
29.04.2016 16:12Что будет если мы передали указатель на локальную переменную куда-то?
Точнее, понятно, что ничего хорошего не будет. И я пока не могу придумать, как решить эту проблему.dzavalishin
29.04.2016 18:04В обычной программе указатель на локальную переменную тоже за пределы функции выпускать нельзя. (Можно, но пока она не вернулась.) Ничего нового.
lorc
29.04.2016 18:19+1Вот именно, что можно пока она не вернулась. Давайте рассмотрим простой пример:
void print_value(int *value){
printf(«Value: %d», *p);
}
void worker(packet)
{
int bytes_count = ...;
print_value(&bytes_count); // И тут у нас происходит создание нового потока, весь стек копируется в новый поток
// в print_value придет указатель который указывает на значение в «старом» стеке где может быть уже всё что угодно.
}
Беда в том, что даже если копировать в новый поток вызывающую функцию (ту, что вызвала worker()), то это тоже не поможет, потому что у той функции есть свои локальные переменные, которые она могла кому-то отдать.dzavalishin
29.04.2016 22:34стек не копируется, обратите внимание.
lorc
30.04.2016 01:02Ааа, да, действительно. Я пропустил этот момент. Тогда да, всё будет работать. Главное, не передавать ссылка на локальные переменные в worker()
lorc
29.04.2016 18:56А ещё проблему с setjmp/longjmp предвижу я. Радует только то, что они никому не нужны.
qw1
29.04.2016 18:07Это только для сценариев, когда результат функции не важен? Таких очень мало.
Тот же worker(packet) должен сам позаботиться об уничтожении пакета? Т.е. packet (и вообще, любые данные для worker) нельзя создать на стеке вызывающей ф-ции.
И я думаю, затраты на синхронизацию сожрут потенциальный профит. Поскольку мы не знаем, закончится обработка в том же треде, или в другом, придётся писать максимально блокировочно. Например, могут быть хитро заточенные аллокаторы, которые оптимизируют случай, когда malloc и free сделаны в одном потоке, здесь они просядут.dzavalishin
29.04.2016 22:36Если задача может быть решена без потоков, то зачем решать её с потоками, не так ли?
qw1
30.04.2016 00:58Вот именно, Ваш подход заставляет писать «с потоками». А именно, параметр packet аллоцировать так, как будто он передаётся во владение другому потоку, а это ещё расходы. Обычный подход с пулом потоков гарантирует, что packet будет обработан в текущем потоке, данные можно выделять на стеке, синхронизация не нужна для тех ресурсов, которые мы группировать в потоке пула.
dzavalishin
30.04.2016 15:31мой подход позволяет избегать создания потока в определённых случаях. в остальном он уместен только если при его отсутствии потоки всё равно потребовались бы.
qw1
30.04.2016 20:38То есть, этот подход — эволюция принципа рождения потока на запрос. А этот принцип на нагрузках показал себя не очень (при условии, что надо обслуживать тысячи запросов в секунду).
MacIn
29.04.2016 19:04Понятно, что некоторые пакеты обслуживаются быстро, а иные могут потребовать много времени. В такой ситуации хотелось бы иметь механизм, который динамически порождает обслуживающие нити по мере необходимости, и механизм достаточно дешёвый в ситуации, когда лишние нити не нужны
Или просто механизм вида DPC в NT. Может быть, обслуживаемый пулом.lorc
29.04.2016 20:41Аналогом DPC в линуксе являются workers + worker threads в качестве пула. Да и подобная штука есть наверное в любой ОС. Другое дело, что это довольно дорого, потому что надо переключать контексты. Автор поста хотел сделать более легковесный вариант, но беда в том, что дизайн языка не сильно расположен к таким штукам.
MacIn
29.04.2016 20:58что это довольно дорого, потому что надо переключать контексты
Это зависит от реализации.lorc
29.04.2016 21:26Ну я честно говоря плохо разбираюсь в ядрах NT. Не расскажете как это работает?
dzavalishin
29.04.2016 22:48Не знаю конкретной схемы в NT, но я эту идею реализовал в Фантоме именно как самобалансирующийся тред пул: желающие ставят в очередь функции на асинхронное исполнение, система исполняет их из пула тредов, и если весь пул занят — порождает для него ещё один тред.
dzavalishin
29.04.2016 22:40DPC тоже не бесплатный. Хотя и дешевле треда. Тут любопытно именно то свойство, что решение о формировании треда (или исполнении в рамках тред пула, кстати — что и есть DPC) принимается позже точки потенциального порождения этого треда.
Shamov
29.04.2016 22:41+1По-моему, идея тупиковая. Проблема в том, что если я знаю, что моя функция может быть выполнена параллельно, то я должен быть готов к худшему случаю и написать эту функцию так, как будто она всегда будет выполняться параллельно. Мне нужно будет защитить мьютексами всё, к чему она прикасается. Соответственно, в том случае, когда функция будет исполняться синхронно, она будет делать кучу лишней работы. Если уж делать что-то подобное, то функций должно быть две. Одна для параллельного выполнения, другая — для синхронного. Но тогда нельзя будет начать выполнять функцию синхронно, а затем продолжить параллельно. И значит в этом вообще нет никакого смысла. В общем, я думаю, что это нигде не реализовано неслучайно. Просто нет запроса на такой функционал. Никто не рискнёт доверить системе самой решать, выполнить функцию параллельно или нет.
dzavalishin
29.04.2016 22:42Это не всегда так. Приведённый пример — исполнение запросов — как раз не предполагает никаких мьютексов. Каждый вызов — новый отдельный запрос. Нитям нечего делить.
Shamov
29.04.2016 22:53+1Если так, то да. Но это какой-то сферический конь в вакууме. Когда запросам нечего делить, они не имеют побочных эффектов и ничего не возвращают обратно в вызывающую программу, то такие запросы можно ещё лучше соптимизировать — вообще не исполнять. Для вызывающей программы ситуация будет неотличима от очень эффективного исполнения.
dzavalishin
30.04.2016 15:32обслуживание read-only веб запроса.
Shamov
30.04.2016 16:02+1Если только для статических данных. Динамические данные могут измениться в процессе при параллельном исполнении. Следовательно, доступ к ним нужно защищать. Но в любом случае для таких специальных задач лучше сразу сделать пул потоков нужного размера и, потратив время на создание потоков лишь один раз, гарантированно обслуживать запросы параллельно, не рассчитывая на милость системы, которая может запустит исполнение параллельно, а может и нет.
dzavalishin
30.04.2016 16:51Может быть и лучше. Вполне допускаю. Но обоснования — не увидел.
Shamov
30.04.2016 17:17А как можно обосновать столь очевидную вещь? Если какая-то задача лучше решается параллельным исполнением, то очевидно, что наилучшим решением будет сознательно организованная параллельная обработка, полностью исключающая последовательное исполнение. Или это не очевидно?
dzavalishin
30.04.2016 17:38Нет. Последовательное дешевле, если фактическая нагрузка позволяет.
Shamov
30.04.2016 17:43За счёт чего оно дешевле, если при параллельной обработке нет расходов на создание потоков, и нет общих данных, доступ к которым нужно синхронизировать?
dzavalishin
01.05.2016 00:08Точка выдачи задания синхронизирована.
Shamov
01.05.2016 09:09В том случае, когда обработка может быть выполнена параллельно по решению системы, выдача задания тоже должна быть синхронизирована.
qw1
30.04.2016 20:40Так оппонент и предлагает создать потоков по числу ядер и на каждом потоке работать строго последовательно, крутить цикл обработки запросов.
nikitadanilov
30.04.2016 00:36В Солярисе так (были?) реализованы interrupt threads. Там прерывания обрабатывлись не поверх стека текущего треда, как в традиционном Юниксе, а в специальных пре-аллоцированных тредах. Но вначале, при возникновении прерывания, такой тред не был полноценным, и не был видем планировщику. Только если interrupt thread блокировался, например, на мьютексе, он отлеплялся от ядерного треда, который он прервал, и становился полноценным.
dzavalishin
30.04.2016 15:34О как интересно! Отличная схема. Особенно при учёте того, что переключение юзер-ядро всё равно переключает стек, и никаких новых накладных расходов не видно. Единственное — что делать с аппаратурой контроллера прерываний. Если обслуживание прерывания полетело в нить, то оно длинное и нужно бы открыть прерывания и разблокировать контроллер прерываний.
nikitadanilov
30.04.2016 15:47Да. Плюс в прерывании можно использовать все обычные синхронизационные примитивы, и нет нужды разбивать обработку на top-half vs. bottom-half. Но Сан в конце концов отказался, кажется, от этой схемы, не помню почему.
dzavalishin
30.04.2016 16:53Конечно! Плюсы очевидны. Мало того, такая схема позволяет вообще загнать обработчик в managed code. Спасибо Вам за этот кейз, у меня в копилке небанальных штук его не было. Интересно бы узнать, почему отказались.
nikitadanilov
30.04.2016 19:39А может быть и не отказались. Сейчас посмотрел Solaris Internals, в v10 еще были. В Солярисе, вообще (было) много интересных вещей с многопоточностью: N:M треды с scheduler activations по Андерсону et at., треды, которые могли прыгать между адресными пространствами (doors).
youROCK
В рантайме языка го происходит нечто похожее: когда в какой-то горутине происходит блокирующийся системный вызов, то все остальные горутины (аналог треда в го) мигрируют на новый ОС тред. То есть, переносят еще не запустившийся код, а не тот код, который в данный момент исполняется.
12sd
Да, но стоит отметить, что это при GOMAXPROCS>1.
Иначе все горутины мультиплексируются на один системный поток.
Например, в GopherJS (Golang -> Javascript компилятор и набор библиотек).
youROCK
Блокирующиеся системные вызовы (или вызовы C-кода) будут создавать новый тред вне зависимости от настройки GOMAXPROCS. Настройка GOMAXPROCS определяет лишь количество тредов, которым будет передано управление для чисто go-кода.