Lazy threads: опциональный параллелизм

    Статья-гипотеза. Описанное нигде не было реализовано, хотя, в принципе, ничто не мешает запилить такое в Фантоме.

    Эта идея пришла мне в голову очень давно и даже где-то была мной описана. Триггер к тому, чтобы её описать сегодня — обсуждение сетевых драйверов Линукса в комментариях к Анатомии драйвера.

    Сформулирую проблему, описанную там, как я её понимаю: сетевой драйвер Линукса работает в отдельной нити, которая читает принятые пакеты из устройства и синхронно их обрабатывает. Прогоняет через роутинг, файрволл и, если пакет не нам, отправляет его в исходящий интерфейс.

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

    То есть хотелось бы такого вызова функции, который при необходимости можно конвертировать в старт нити. Но по цене вызова функции, если нить реально не оказалась нужна.

    Мне эта идея пришла когда я рассматривал совершенно фантастические модели для Фантом, включая акторную модель с запуском нити вообще на любой вызов функции/метода. Саму модель я отбросил, а вот идея 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 в настольной, явно нужны механизмы, которые помогают коду адаптироваться к нагрузочной способности аппаратуры. Может быть — так?

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 707 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 48

      0
      В рантайме языка го происходит нечто похожее: когда в какой-то горутине происходит блокирующийся системный вызов, то все остальные горутины (аналог треда в го) мигрируют на новый ОС тред. То есть, переносят еще не запустившийся код, а не тот код, который в данный момент исполняется.
        0
        Да, но стоит отметить, что это при GOMAXPROCS>1.
        Иначе все горутины мультиплексируются на один системный поток.
        Например, в GopherJS (Golang -> Javascript компилятор и набор библиотек).
          0
          Блокирующиеся системные вызовы (или вызовы C-кода) будут создавать новый тред вне зависимости от настройки GOMAXPROCS. Настройка GOMAXPROCS определяет лишь количество тредов, которым будет передано управление для чисто go-кода.
        0
        >> Если же прошло значительное время, а worker всё ещё работает, произведём простую операцию
        Поясните пожалуйста, кто и когда это делает, если поток выполнения сейчас внутри worker'а?
          0
          ядро, подсистема переключения потоков.
          0
          А не могли бы вы придумать несколько сценариев применения данного подхода?

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

          Я сходу не смог придумать случай, когда это востребовано. Сразу скажу, что думал в контексте геймдева. В прикладных вещах, мне кажется, проблем особых не стоит, и, если уж, например, понадобился быстрый отклик от интерфейса, то все решается по принципу: есть гуй тред, а есть тред расчетов.
            0
            В самом начале описано: рантайм балансировка числа тредов для обработки запросов. Например, запросов на маршрутизацию пакетов.
              +1
              Честно говоря не понял, почему одни пакеты могут «настолько» дольше обрабатываться, чем другие на уровне драйвера. А можете еще найти вариантов для прикладников, а не для драйвера, если не вас не затруднит?

              PS: А как быть с временем ожидания выхода из функции? Т.е. вызвавший функцию поток спит или нет, пока выполняется запущенная нить?
              результат нас может не интересовать, но может интересовать последовательность выполнения фунцкий
                0
                http сервер. запустивший спит, пока это функция и не спит, когда она нить. это надо рассматривать семантически как запуск нити, который в удачном случае оптимизируется в вызов функции.
                  0
                  Я понимаю, как работает ваша идея. Я не понимаю применения в сравнении с другими методами.

                  Как это можно использовать в http-сервере мне тоже не понятно.

                  Есть сервер, туда идут запросы, они парсятся, результат отдается.
                  Мы делаем либо на нескольких потоках с примитивами синхронизации, либо плодим кучу потоков на каждый запрос и там выполняем все последовательно.

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

                  Одно дело, когда вы точно знаете, что вам надо синхронизироваться, это одна парадигма, и другое дело, когда вы не знаете как дело пойдет, и придется учитывать оба варианта сразу.
                  Прикладных задач, где это будет лучше я не вижу, поэтому просил примеры, чтобы лучше понять вашу идею.

                  В общем, я вижу что задаю уже третий вопрос, ответа не увидел ни на один, извините за назойливость, больше тревожить не буду )
                    0
                    Замнём для ясности. У меня тоже нет какой-то сногсшибательной картины, которая бы явила абсолютную ясность. Разве что данный механизм проще в применении, чем тредпул, и является его заменой.
                      +1
                      Может я и слепой, но в статье я не увидел ничего иного, кроме описания событийно-ориентированного программирования, с очередным костылем. Поток событий порождает, с разной интенсивностью, поток исполнителей, существующих в едином контексте, что приводит к необходимости все синхронизировать, я правильно понял? Если правильно, то видится, что в очередной раз «создаются проблемы, и героически решаются». 1) Единый контекст, если нет ограничения наложенных транзакциями, то почему каждой нити не отдать свое псевдо-устройство? (т.е. перенести момент управления устройством на момент синхронизации псевдо устройства и реального) 2) За синхронизацию и разделение контекста не отвечают мониторы(акторы); состояния можно выпилить из нитей отдав их акторам, не блокируя сразу весь контекст для сложного драйвера, но огрести все проблемы множественной блокировки; в решении «Global Lock» получаем бессмысленность разделения на потоки, в решении «обмен сообщениями», получаем задержки и расходы на очередь.
                      Т.е. требование «одно устройство — одно состояние» делает бессмысленным многозадачность для управления им, каким бы «толстым» оно не было.
              0
              Что будет если мы передали указатель на локальную переменную куда-то?
              Точнее, понятно, что ничего хорошего не будет. И я пока не могу придумать, как решить эту проблему.
                0
                В обычной программе указатель на локальную переменную тоже за пределы функции выпускать нельзя. (Можно, но пока она не вернулась.) Ничего нового.
                  +1
                  Вот именно, что можно пока она не вернулась. Давайте рассмотрим простой пример:

                  void print_value(int *value){
                  printf(«Value: %d», *p);
                  }

                  void worker(packet)
                  {
                  int bytes_count = ...;
                  print_value(&bytes_count); // И тут у нас происходит создание нового потока, весь стек копируется в новый поток
                  // в print_value придет указатель который указывает на значение в «старом» стеке где может быть уже всё что угодно.
                  }

                  Беда в том, что даже если копировать в новый поток вызывающую функцию (ту, что вызвала worker()), то это тоже не поможет, потому что у той функции есть свои локальные переменные, которые она могла кому-то отдать.
                    0
                    стек не копируется, обратите внимание.
                      0
                      Ааа, да, действительно. Я пропустил этот момент. Тогда да, всё будет работать. Главное, не передавать ссылка на локальные переменные в worker()
                    0
                    А ещё проблему с setjmp/longjmp предвижу я. Радует только то, что они никому не нужны.
                  0
                  Это только для сценариев, когда результат функции не важен? Таких очень мало.
                  Тот же worker(packet) должен сам позаботиться об уничтожении пакета? Т.е. packet (и вообще, любые данные для worker) нельзя создать на стеке вызывающей ф-ции.

                  И я думаю, затраты на синхронизацию сожрут потенциальный профит. Поскольку мы не знаем, закончится обработка в том же треде, или в другом, придётся писать максимально блокировочно. Например, могут быть хитро заточенные аллокаторы, которые оптимизируют случай, когда malloc и free сделаны в одном потоке, здесь они просядут.
                    0
                    Если задача может быть решена без потоков, то зачем решать её с потоками, не так ли?
                      0
                      Вот именно, Ваш подход заставляет писать «с потоками». А именно, параметр packet аллоцировать так, как будто он передаётся во владение другому потоку, а это ещё расходы. Обычный подход с пулом потоков гарантирует, что packet будет обработан в текущем потоке, данные можно выделять на стеке, синхронизация не нужна для тех ресурсов, которые мы группировать в потоке пула.
                        0
                        мой подход позволяет избегать создания потока в определённых случаях. в остальном он уместен только если при его отсутствии потоки всё равно потребовались бы.
                          0
                          То есть, этот подход — эволюция принципа рождения потока на запрос. А этот принцип на нагрузках показал себя не очень (при условии, что надо обслуживать тысячи запросов в секунду).
                    0
                    Понятно, что некоторые пакеты обслуживаются быстро, а иные могут потребовать много времени. В такой ситуации хотелось бы иметь механизм, который динамически порождает обслуживающие нити по мере необходимости, и механизм достаточно дешёвый в ситуации, когда лишние нити не нужны

                    Или просто механизм вида DPC в NT. Может быть, обслуживаемый пулом.
                      0
                      Аналогом DPC в линуксе являются workers + worker threads в качестве пула. Да и подобная штука есть наверное в любой ОС. Другое дело, что это довольно дорого, потому что надо переключать контексты. Автор поста хотел сделать более легковесный вариант, но беда в том, что дизайн языка не сильно расположен к таким штукам.
                        0
                        что это довольно дорого, потому что надо переключать контексты

                        Это зависит от реализации.
                          0
                          Ну я честно говоря плохо разбираюсь в ядрах NT. Не расскажете как это работает?
                            0
                            Не знаю конкретной схемы в NT, но я эту идею реализовал в Фантоме именно как самобалансирующийся тред пул: желающие ставят в очередь функции на асинхронное исполнение, система исполняет их из пула тредов, и если весь пул занят — порождает для него ещё один тред.
                        0
                        DPC тоже не бесплатный. Хотя и дешевле треда. Тут любопытно именно то свойство, что решение о формировании треда (или исполнении в рамках тред пула, кстати — что и есть DPC) принимается позже точки потенциального порождения этого треда.
                        0
                        del
                          +1
                          По-моему, идея тупиковая. Проблема в том, что если я знаю, что моя функция может быть выполнена параллельно, то я должен быть готов к худшему случаю и написать эту функцию так, как будто она всегда будет выполняться параллельно. Мне нужно будет защитить мьютексами всё, к чему она прикасается. Соответственно, в том случае, когда функция будет исполняться синхронно, она будет делать кучу лишней работы. Если уж делать что-то подобное, то функций должно быть две. Одна для параллельного выполнения, другая — для синхронного. Но тогда нельзя будет начать выполнять функцию синхронно, а затем продолжить параллельно. И значит в этом вообще нет никакого смысла. В общем, я думаю, что это нигде не реализовано неслучайно. Просто нет запроса на такой функционал. Никто не рискнёт доверить системе самой решать, выполнить функцию параллельно или нет.
                            0
                            Это не всегда так. Приведённый пример — исполнение запросов — как раз не предполагает никаких мьютексов. Каждый вызов — новый отдельный запрос. Нитям нечего делить.
                              +1
                              Если так, то да. Но это какой-то сферический конь в вакууме. Когда запросам нечего делить, они не имеют побочных эффектов и ничего не возвращают обратно в вызывающую программу, то такие запросы можно ещё лучше соптимизировать — вообще не исполнять. Для вызывающей программы ситуация будет неотличима от очень эффективного исполнения.
                                0
                                обслуживание read-only веб запроса.
                                  +1
                                  Если только для статических данных. Динамические данные могут измениться в процессе при параллельном исполнении. Следовательно, доступ к ним нужно защищать. Но в любом случае для таких специальных задач лучше сразу сделать пул потоков нужного размера и, потратив время на создание потоков лишь один раз, гарантированно обслуживать запросы параллельно, не рассчитывая на милость системы, которая может запустит исполнение параллельно, а может и нет.
                                    0
                                    Может быть и лучше. Вполне допускаю. Но обоснования — не увидел.
                                      0
                                      А как можно обосновать столь очевидную вещь? Если какая-то задача лучше решается параллельным исполнением, то очевидно, что наилучшим решением будет сознательно организованная параллельная обработка, полностью исключающая последовательное исполнение. Или это не очевидно?
                                        0
                                        Нет. Последовательное дешевле, если фактическая нагрузка позволяет.
                                          0
                                          За счёт чего оно дешевле, если при параллельной обработке нет расходов на создание потоков, и нет общих данных, доступ к которым нужно синхронизировать?
                                            0
                                            Точка выдачи задания синхронизирована.
                                              0
                                              В том случае, когда обработка может быть выполнена параллельно по решению системы, выдача задания тоже должна быть синхронизирована.
                                            0
                                            Так оппонент и предлагает создать потоков по числу ядер и на каждом потоке работать строго последовательно, крутить цикл обработки запросов.
                              0
                              В Солярисе так (были?) реализованы interrupt threads. Там прерывания обрабатывлись не поверх стека текущего треда, как в традиционном Юниксе, а в специальных пре-аллоцированных тредах. Но вначале, при возникновении прерывания, такой тред не был полноценным, и не был видем планировщику. Только если interrupt thread блокировался, например, на мьютексе, он отлеплялся от ядерного треда, который он прервал, и становился полноценным.
                                0
                                О как интересно! Отличная схема. Особенно при учёте того, что переключение юзер-ядро всё равно переключает стек, и никаких новых накладных расходов не видно. Единственное — что делать с аппаратурой контроллера прерываний. Если обслуживание прерывания полетело в нить, то оно длинное и нужно бы открыть прерывания и разблокировать контроллер прерываний.
                                  0
                                  Да. Плюс в прерывании можно использовать все обычные синхронизационные примитивы, и нет нужды разбивать обработку на top-half vs. bottom-half. Но Сан в конце концов отказался, кажется, от этой схемы, не помню почему.
                                    0
                                    Конечно! Плюсы очевидны. Мало того, такая схема позволяет вообще загнать обработчик в managed code. Спасибо Вам за этот кейз, у меня в копилке небанальных штук его не было. Интересно бы узнать, почему отказались.
                                      0
                                      А может быть и не отказались. Сейчас посмотрел Solaris Internals, в v10 еще были. В Солярисе, вообще (было) много интересных вещей с многопоточностью: N:M треды с scheduler activations по Андерсону et at., треды, которые могли прыгать между адресными пространствами (doors).
                                0
                                В Continuation Passing C (руководство) реализуются зелёные потоки с возможностью миграции на выделенные обычные и обратно:

                                cpc_detach, cpc_attach The cpc_detach statement detaches the current continuation; the following statements are executed in a dedicated native thread. The opposite operation is performed by cpc_attach, which causes the current continuation to be scheduled by the CPC scheduler.
                                The cpc_detach and cpc_attach statements can only appear in cpc context.

                                cpc_detached, cpc_attached The body of a cpc_detached statement is run detached: an implicit cpc_detach is executed upon entering the body, and a cpc_attach is executed upon exiting. The cpc_attached construct is dual: a cpc_attach is executed upon entry, and a cpc_detach is executed upon exit

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое