Замена для очередей в RTOS

12

Для взаимодействия между задачами или для обмена данными между двумя задачами RTOS, мы используем очереди. Но проблема с очередями заключается в том, что они работают медленно ... Они копируют данные в буфер, затем в обработку Mutex и затем в передачу данных. Это раздражающе медленно, если вам приходится передавать большие данные. Другая проблема, если к одной и той же очереди обращаются несколько задач. Затем изображение выглядит следующим образом: - Сначала подождите, чтобы получить доступ к очереди, затем к внутренней обработке очереди Mutex, а затем к передаче данных.

Это увеличивает нагрузку на систему. Что может быть эффективной заменой очередей?

(Я полагаю, что этот вопрос не зависит от RTOS, которую мы используем. Большинство RTOS обрабатывают очереди только таким способом)

Swanand
источник
Что вы подразумеваете под очередью, доступ к которой осуществляется несколькими задачами? Вы имеете в виду отправку в очередь или чтение из очереди? Несколько задач должны иметь возможность отправлять сообщения в очередь с минимальными издержками. ОСРВ должна обрабатывать мьютексирование, чтобы сообщение было атомарной операцией. Для 99% задач у вас должен быть цикл, который ожидает очереди и обрабатывает сообщение. Очередь должна (обычно) читаться только одной задачей. Вам, вероятно, нужно посмотреть на свой дизайн и то, как вы используете очереди вместо их замены.
Эрик
@Erik: прости! Я использую механизм, который вы упомянули .... Я хотел сказать что-то еще, и я написал по-другому ... Я буду редактировать это! Спасибо за указание на ошибку! Я жду очереди доступа в моем коде!
Суонан,

Ответы:

7

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

Вы копируете данные в буфер в памяти, затем передаете указатель с элементами очереди или пытаетесь передать все данные в самих элементах очереди? Если вы не передаете указатели, вы получите увеличение производительности, вместо того чтобы пропустить один байт за раз через элементы очереди.

AngryEE
источник
2
Я собирался сказать то же самое. Если вы просто передаете указатели на данные в очередях, вы можете увеличить скорость, но убедитесь, что у вас нет двух потоков, пытающихся использовать и изменить данные.
Кортук
Как сказал @Kortuk, мне нужно "убедиться, что у вас нет двух потоков, пытающихся использовать и изменить данные" ... Что означает увеличение накладных расходов ... Я не хочу много обрабатывать! :(
Swanand
Так что нет такой замены для очередей ... Вместо очереди данных мне нужно использовать очередь указателей!
Swanand
1
@Swan, если вы спланируете свое приложение так, чтобы очереди были только однонаправленными (т. Е. Вы никогда не читали одну и ту же очередь в двух задачах) и обрабатывали данные, хранящиеся в указателе, сразу, а затем освобождали их, у вас не должно быть проблем с совместным использованием данных. Это увеличит накладные расходы, поскольку вам, возможно, придется создать несколько очередей для надежной передачи данных назад и вперед, но это стоимость ведения бизнеса в многозадачной среде.
AngryEE
7

Один из простых способов - поместить указатель на данные в очереди и использовать данные с помощью указателя.

Обратите внимание, что вы торгуете безопасностью для производительности таким образом, поскольку вы должны убедиться, что:

  1. буфер остается действительным, пока потребитель не использует данные
  2. кто-то освобождает буфер

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

Trygve Laugstøl
источник
6

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

Очередь без блокировки может быть построена следующим образом: выделить массив элементов, которые необходимо передать, а также два целых числа, называть их Head и Tail. Head - это индекс в массиве, куда будет добавлен следующий элемент. Хвост - это индекс в массиве, где следующий элемент доступен для удаления. Задача производителя читает H и T, чтобы определить, есть ли место для добавления элемента; записывает элемент в индекс H, затем обновляет H. Потребительские задачи считывают H и T, чтобы определить, есть ли доступные данные, считывают данные из индекса T, затем обновляют T. По сути, это кольцевой буфер, к которому получают доступ две задачи, и порядок операций (вставка, затем обновление H; удаление, затем обновление T) гарантирует, что повреждение данных не произойдет.

Если у вас есть ситуация с несколькими производителями и одним потребителем, или с одним производителем и несколькими потребителями, у вас фактически есть какое-то ограничение ресурсов, и для него нет ничего другого, кроме как использовать синхронизацию, поскольку ограничитель производительности с большей вероятностью быть одиноким производителем / потребителем, чем издержки ОС с механизмом блокировки.

Но если у вас есть несколько производителей и потребителей, стоит потратить время (в пространстве дизайна), чтобы увидеть, не можете ли вы получить более скоординированный механизм коммуникации; в таком случае сериализация всего через одну очередь определенно делает эффективность очереди центральным фактором, определяющим производительность.

JustJeff
источник
1
Я собирался +1 это, но вы ошиблись: очереди без блокировки можно реализовать для нескольких читателей и авторов, они просто более сложные. (посмотрите на статью Майкла + Скотта об очередях без блокировок google.com/search?q=michael%20scott%20queue )
Джейсон С
1
@ Jason S - требует ли бумага Скотта повторного входа для операций без вставки и удаления без блокировки? Если это так, если вы можете извлечь это и опубликовать, пожалуйста, сделайте это будет бесценным активом для многих. Читатель должен отметить, что в цитируемой статье используются специальные машинные инструкции, в то время как моя позиция в вышеприведенном посте не предполагала таких инструкций.
JustJeff
1
Да, стоимость алгоритмов без блокировок обычно зависит от CAS или эквивалентных инструкций. Но как в игру вступает повторный вход? Это имеет смысл для мьютексов + блокирующих структур, но не для операций со структурами данных.
Джейсон С
2

Можно получить эффективную работу в очереди с несколькими потребителями без блокировки для одного производителя, если сама очередь содержит элементы, которые достаточно малы, чтобы работать с исключающими загрузку хранилищем, сравнивать обмен или подобный примитив, и можно использовать зарезервированное значение или зарезервированные значения для пустых слотов очереди. При записи в очередь писатель выполняет обмен сравнениями, чтобы попытаться сохранить свои данные в следующем пустом слоте; если это не удается, писатель пытается следующий слот. Хотя очередь поддерживает указатель на следующий пустой слот, значение указателя является «рекомендательным». Обратите внимание, что если система использует сравнение-обмен, а не загрузку-исключение-хранилище, может возникнуть необходимость иметь «семейство» разных значений «пустого слота». В противном случае, если между временем записи найдется пустой слот очереди и попытается выполнить запись в него, другой писатель пишет слот, а читатель читает его, первый писатель неосознанно помещает свои данные в то место, где читатель их не увидит. Эта проблема не возникает в системах, которые используют исключение загрузки-хранилища, поскольку исключение хранилища обнаружит, что данные были записаны, даже если они были записаны обратно в старое значение.

Supercat
источник
1

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

ура !!

Sai
источник
1

Очереди не являются медленными по своей сути. Реализация их может быть.

Если вы слепо копируете данные и используете синхронную очередь, вы увидите снижение производительности.

Как указывали другие авторы, существуют альтернативы без блокировок. Случай одного производителя / одного потребителя прост; для множества производителей и потребителей алгоритм очереди без блокировки Майкла и Скотта (таковы их фамилии) является стандартом и используется в качестве основы для Java ConcurrentLinkedQueue .

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

Джейсон С
источник
Из статьи Майкла и Скотта: «это четкий алгоритм выбора для машин, которые предоставляют универсальный атомарный примитив (например, сравнивать и менять или загружать, связывать / хранить условно)». Хотя это может на самом деле не совсем блокировать поток, здесь есть форма синхронизации.
JustJeff
у вас есть точка; это может уменьшить требование параллелизма от исключительного доступа к барьеру памяти.
Джейсон С