Jump to content
    

Две задачи на одном стеке.

Не знаю - в какой раздел задать сей вопрос. Отсутствует на нашем форум раздел чисто по программированию. Да, что-то есть в разделе "Для начинающих". Но вопрос - явно не уровня начинающих.

 

Дано:

Есть 2-е процедуры (или назовём их - задачи, но не в смысле "задачи ОС", а в смысле - "2 независимых процесса обработки данных"), которые должны взаимодействовать между собой (одна готовит и передаёт данные другой). Но выполняются они на МК, имеющем ограниченные ресурсы (ограниченный объём ОЗУ). Обе - достаточно сложные и объёмные. Содержащие множество вызовов функций, с довольно большой и слабо предсказуемой глубиной использования стека. И непредсказуемым временем исполнения (зависит от скорости реакции удалённого устройства и т.п.)

Один из возможных сценариев работы: Одна процедура-задача генерирует большой файл в потоковом режиме. Т.е. - не сохраняя его куда-то в ОЗУ, а передавая другой процедуре-задаче по-байтно или небольшими порциями (небольшая буферизация). Вторая процедура-задача передаёт этот файл по некоему протоколу через какой-то интерфейс. Со всеми ожиданиями отклика удалённой стороны, повторами и т.п. Тоже - довольно сложная и развесистая задача. Если бы какая-то из задач была простой, но её нетрудно было бы реализовать в виде машины состояний, вызываемой из второй задачи через callback-и. Но, так как обе довольно большие, то реализация через callback-и будет сложной до монстроидальности и нечитаемости кода (хотя возможна конечно).

На системе без сильных ограничений по ОЗУ (на ПК; или МК с SDRAM; ...) проще всего было бы оформить эти две процедуры-задачи в две задачи ОС: одна пишет данные в небольшой буфер (несколько байт), когда он заполнится - пинает 2-ю задачу "данные готовы" и встаёт на ожидание готовности (пинка) от неё; 2-я задача передаёт эту порцию данных, закончив передачу - пинает 1-ю задачу "данные обработаны" и встаёт на ожидание новой порции данных (пинка от 1-й). Но работаем на МК. Завести две задачи ОС, отдав каждой по приличному стеку с большим запасом? Жаба душит. Так как процесс этот выполняется редко, и бОльшую часть времени работы устройства эта память (стеки) будет просто болтаться без дела. Хотелось бы чтобы обе эти 2 процедуры-задачи можно было оформить в простом виде - кодом, передающим/принимающим данные к/от другой процедуры-задачи в блокирующем режиме. Упрощённо-схематично:

void ProcedureTask1()
{
  Data data;
  for (;;) {
     data.Fill();
     data.PutToTask2();
  }
}

void ProcedureTask2()
{
  Data data;
  for (;;) {
     data.GetFromTask1();
     data.SendToRemote();
  }
}

В таком удобочитаемом виде. Это общий принцип. PutToTask2() и GetFromTask1() - блокирующие.

Только в реальности вызов data.PutToTask2() в 1-й задаче не один, а их множество внутри data.Fill() и вложенных в неё на разных глубинах функциях. На очень больших глубинах. Аналогично и data.GetFromTask1() во 2-й задаче. Потому - соединить их простым способом проблематично.

 

Хочется чтобы обе задачи работали на одном стеке, с одним общим резервом объёма для него. Но нужно будет переключаться то на одну, то на другую. Тогда увеличивающийся стек одной задачи, потрёт стек 2-й. Получается - имеем такую структуру стека (на момент переключения со 2-й процедуры-задачи на 1-ю):

SP + NS2 + NS1:
   стек 1-й процедуры-задачи
SP + NS2:
   стек 2-й процедуры-задачи
SP + 0:
   резерв пространства стека

Для переключения нужно: сохранить контекст процедуры-задачи2 на текущий стек; поменять стеки местами; восстановить контекст из нового стека и вернуться в процедуру-задачу1. Потом - обратно. И так много раз.

Размеры стеков NS1 и NS2 - текущие размеры стеков процедур-задач. Постоянно меняются (при каждом новом переключении процедур-задач). Но очевидно - кратны и выровнены на границу 64 бит.

 

Вопросы:

  1. Как наиболее быстро поменять содержимое стеков (массивов 64-битных слов) местами? Без использования промежуточного буфера. Или с очень маленьким буфером. При условии, что: SP, NS1, NS2 - переменные; (SP + NS2 + NS1) - константа. NS1 может быть больше, меньше или равен NS2. Алгоритм?? 
  2. Кто-нибудь реализовывал что-то подобное?

Share this post


Link to post
Share on other sites

Попробуйте простейшие Stack-lesss C coroutines или Protothreads. Они на одном принципе сделаны, второй вариант использую в МК. Стек общий, переключение между "задачами" есть.

 

UPD: возможно вот из-за этого:

Цитата

Только в реальности вызов data.PutToTask2() в 1-й задаче не один, а их множество внутри data.Fill() и вложенных в неё на разных глубинах функциях. На очень больших глубинах.

предложенные мной варианты не подойдут. Точнее protothreads можно использовать, но все вызываемые функции, где нужно будет передавать управление другой "задаче" нужно будет оборачивать в прототреды. Иначе, мне кажется, на одном стеке такую задачу не решить.

Share this post


Link to post
Share on other sites

2 часа назад, arhiv6 сказал:

UPD: возможно вот из-за этого:

предложенные мной варианты не подойдут. Точнее protothreads можно использовать, но все вызываемые функции, где нужно будет передавать управление другой "задаче" нужно будет оборачивать в прототреды. Иначе, мне кажется, на одном стеке такую задачу не решить.

Если бы не это, я бы просто сделал одну из процедур-задач - вызываемой через callback-и из второй. И всё. Не усложняя.

Иначе - без копирования содержимого стека никак не обойтись. И если эти protothreads этого делать не умеют - значит не помогут.

Share this post


Link to post
Share on other sites

Из описанного просматривается кооперативная многозадачность. Варианта три:

  1. поискать готовые реализации, может попадётся подходящая;
  2. написать что-то своё (простенький планировщик, который по yiеld из задач будет передавать управление следующей (по очереди или по приоритету);
  3. использовать языковые средства -- например, в С++20 ввели механизм сопрограмм (coroutines), который по сути и есть организация кооперативной многозадачности средствами языка. Этот async в последнее время модная тема, почти одновременно стало появляться в очень разных языках (С++, Python). 

По поводу сопрограмм, чтобы понять, оно/не оно, нравится/не нравится можно начать с примера. Поначалу кажется немного пугающим, но немного вникнув, сложного на таком уровне там немного. Просто тема сама по себе несколько новая, требуются некоторые усилия на вникание (там есть ссылка на видос-лекцию, может помочь сориентироваться в теме). Цитата из коммента к статье:

Цитата

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

 

Share this post


Link to post
Share on other sites

5 минут назад, dxp сказал:

По поводу сопрограмм, чтобы понять, оно/не оно, нравится/не нравится можно начать с примера.

Вопрос не в "нравится"/"не нравится". Как бы оно ни было бы организовано, оно должно уметь перемещать содержимое стека. Это следует из самой природы стека и использования его процессором.

Оно умеет перемещать? нет? Умеет делать то, что я описал в вопросе N1?

Share this post


Link to post
Share on other sites

Я вот что-то не смог уловить суть. Нужно, чтобы 2 разных задачи использовали один и тот же физический кусок ОЗУ для своих стеков? Как это будет работать, если, например, задача 1 где-то в дебрях своих вложенных функций сменила контекст на задачу 2 (например, ожиданием семафора), 2 задача начала работать, возможно затерла этот блок памяти, поработала, отдала управление обратно - но стек задачи 1 уже будет запорот.

Share this post


Link to post
Share on other sites

Пришла мысль.... В структуре стека двух задач, контекст неактивной задачи можно хранить в самом низу стека:

SP + NS2: (конец (невключительный) стека)
   стек/контекст 2-й процедуры-задачи (активной)
SP:
   резерв пространства стека
STACK + NS1:   
   стек/контекст 1-й процедуры-задачи (неактивной)
STACK: (начало(низ) стека)

Тогда обмен содержимым становится быстрее. Так как в качестве промежуточного буфера выступает резерв пространства стека.  :yess:

9 минут назад, Arlleex сказал:

Я вот что-то не смог уловить суть. Нужно, чтобы 2 разных задачи использовали один и тот же физический кусок ОЗУ для своих стеков? Как это будет работать, если, например, задача 1 где-то в дебрях своих вложенных функций сменила контекст на задачу 2 (например, ожиданием семафора), 2 задача начала работать, возможно затерла этот блок памяти, поработала, отдала управление обратно - но стек задачи 1 уже будет запорот.

Я выше приводил стек 2-х задач:

4 часа назад, jcxz сказал:

Получается - имеем такую структуру стека (на момент переключения со 2-й процедуры-задачи на 1-ю):

SP + NS2 + NS1:
   стек 1-й процедуры-задачи
SP + NS2:
   стек 2-й процедуры-задачи
SP + 0:
   резерв пространства стека

Для переключения нужно: сохранить контекст процедуры-задачи2 на текущий стек; поменять стеки местами; восстановить контекст из нового стека и вернуться в процедуру-задачу1. Потом - обратно. И так много раз.

Т.е. - запустилась 1-я задача. Потом она из себя (через callback или подобным образом) запустила 2-ю задачу. 2-я задача заполнила буфер данных (или наоборот - опустошила) для первой задачи, и должна встать на ожидания его обработки 1-й задачей. Вот в этот момент структура стека такая, как показана выше. Теперь, чтобы снова активировать задачу1, не потеряв контекста 2-й задачи, и нужно обменять содержимое их стеков. А потом (при переключении задача1->задача2) нужно произвести обратный обмен.

Вопрос был главным образом об эффективной процедуре наиболее быстрого обмена местами содержимого контекстов 2-х задач. Чтобы из структуры выше получить:

SP + NS1 + NS2:
   стек 2-й процедуры-задачи
SP + NS1:
   стек 1-й процедуры-задачи
SP + 0:
   резерв пространства стека

Share this post


Link to post
Share on other sites

FreeRTOS позволяет создавать корутины в одном стеке.

Только это не рекомендуется делать в новых разработках, считается устаревшим.

Share this post


Link to post
Share on other sites

29 минут назад, dOb сказал:

FreeRTOS позволяет создавать корутины в одном стеке.

И какова будет структура хранения контекстов внутри этого стека? Покажите.

29 минут назад, dOb сказал:

Только это не рекомендуется делать в новых разработках, считается устаревшим.

Точно! Нынче модно для простой мигалки лампочками [censored] Cortex-M7 на 480МГц и мегабайтом ОЗУ. И весь его занять простым миганием.  :biggrin:

Share this post


Link to post
Share on other sites

5 часов назад, jcxz сказал:

Завести две задачи ОС, отдав каждой по приличному стеку с большим запасом? Жаба душит. Так как процесс этот выполняется редко, и бОльшую часть времени работы устройства эта память (стеки) будет просто болтаться без дела

а нельзя выделить на куче стек и саму задачу #1, после отправки очередь - прибить #1 и выделить на куче для #2 ?

Share this post


Link to post
Share on other sites

2 минуты назад, megajohn сказал:

а нельзя выделить на куче стек и саму задачу #1, после отправки очередь - прибить #1 и выделить на куче для #2 ?

Задачу #1 прибить нельзя, потому как она, заполнив один буфер (для передачи задаче #2), не закончила работу, а только прервалась до момента освобождения буфера. И должна продолжить работу с места предыдущей остановки. Прибив её (или контекст) теряем весь прогресс её работы.

Share this post


Link to post
Share on other sites

13 hours ago, jcxz said:

Одна процедура-задача генерирует большой файл в потоковом режиме. Т.е. - не сохраняя его куда-то в ОЗУ, а передавая другой процедуре-задаче по-байтно или небольшими порциями (небольшая буферизация). Вторая процедура-задача передаёт этот файл по некоему протоколу через какой-то интерфейс

Решение - кооперативная ОС.

ТСР стек на 8-битных МК передает файлы ( а там буферы совсем маленькие) сгенерированные на лету.

Или по FTP принимает файлы и пишет их во внешнюю память (или внутреннюю).

Обычная задача с кольцевым буфером в которой одна прога  заполняет буфер , а другая его выталкивает .

 

Share this post


Link to post
Share on other sites

51 минуту назад, smart_pic сказал:

Решение - кооперативная ОС.

когда я был маленьким не дорос но нормального переключения контекста, делал так, есть осн прога, это задача 1 (низкий уровень) и есть задача 2 (средний уровень), которая вызывается программным прерыванием, которое инициируется аппаратным прерыванием -  шедулером, при входе в него, прерывания разрешаются снова, но определенный квант времени работает задача 2, потом из нее идет выход и управление передается задаче 1, обычные прерывания (высокий уровень) от устройств тоже работают, и прерывают обе задачи, но т.к. обработка прерываний занимает очень небольшую часть времени, на работу задач 1 и 2 практически не сказывается. Минус такой схемы - задача 2 должна сама завершится, чтобы дать время задаче 1. Задача 1 работает постоянно, ее не надо завершать, как в случае кооперативной схемы. У меня использовалось так низкий уровень - ФС, сетевой стек, усб энумерация и низкоскоростные интерфейсы, средний - виртуальная машина, скоростные интерфейсы, и пр. ногодрыг, высокий - драйверы устройств на прерываниях. Для чего-то подобного было предостаточно. Шедулер позволял регулировать кол-во квантов времени отдаваемое 1 и 2 задаче, тактировался прерыванием таймера 10000 раз в сек, ну и выполнял еще функции счетчиков-задержек для всяких применений...

Edited by mantech

Share this post


Link to post
Share on other sites

10 часов назад, jcxz сказал:

И если эти protothreads этого делать не умеют - значит не помогут.

протонитки могут много. целая ОС на них навеорочана с блекджэком ..
https://github.com/contiki-ng/contiki-ng

И даже без этого наворота они прекрасно себя показывают в качестве процедур главного цыкла

Edited by AlexRayne

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...