Какой-либо единственный производитель единственного потребителя блокирует бесплатную реализацию очереди в C?
Это короткий и простой пример, который я только что использовал:
Если:
fp = open("file.txt", "w")
Тогда:
fp.write(line.replace('is', 'now'))
// "This is me" becomes "This now me"
Не:
line.replace('is', 'now')
fp.write(line)
// "This is me" not changed while writing
8 ответов
Если вы беспокоитесь о производительности, добавление malloc () в микс не поможет. И если вас не беспокоит производительность, почему бы просто не контролировать доступ к очереди через мьютекс. Вы действительно измерили производительность такой реализации? Мне кажется, вы идете по знакомому пути преждевременной оптимизации.
Алгоритм, который вы показываете, работает, потому что, хотя два потока совместно используют ресурс (то есть очередь), они совместно используют его совершенно определенным образом. Поскольку только один поток когда-либо изменяет заголовочный индекс очереди (производитель), и только один поток каждый изменяет конечный индекс (потребитель, конечно), вы не можете получить несогласованное состояние общего объекта. Также важно, чтобы производитель поместил фактические данные в перед обновлением главного индекса, и чтобы потребитель прочитал данные, которые он хочет , прежде чем обновит хвостовой индекс.
Это работает как как и b / c массив довольно статичен; оба потока могут рассчитывать на хранилище для находящихся там элементов. Вероятно, вы не сможете полностью заменить массив, но вы можете изменить то, для чего этот массив используется.
Т.е. вместо хранения данных в массиве используйте его для хранения указателей на данные. Затем вы можете malloc () и free () элементы данных, передавая на них ссылки (указатели) между вашими потоками через массив.
Кроме того, posix поддерживает чтение наносекундных часов, хотя фактическая точность зависит от системы. Вы можете прочитать эти часы с высоким разрешением до и после и просто вычесть.
Я думаю, что распределитель может быть проблемой с производительностью. Вы можете попробовать использовать настраиваемый многопоточный распределитель памяти, который использует связанный список для обслуживания освобожденных блоков. Если ваши блоки не (почти) одинакового размера, вы можете реализовать «распределитель системной памяти Buddy», это очень быстро. Вам необходимо синхронизировать вашу очередь (кольцевой буфер) с мьютексом.
Чтобы избежать слишком большой синхронизации, вы можете попробовать записать / прочитать несколько значений в / из очереди при каждом доступе.
Если вы все еще хотите использовать, алгоритмы без блокировки, то вы должны использовать предварительно выделенные данные или использовать распределитель без блокировки. Существует статья о свободном от блокировок распределителе «Масштабируемое распределение динамической памяти без блокировок» и реализации Streamflow
Перед тем, как начать работу с блокировками, посмотрите: Круговой буфер без блокировок
Я работал с довольно простой реализацией очереди, отвечающей большинству ваших критериев. Он использовал статический пул байтов максимального размера, а затем мы реализовали в нем сообщения. Был указатель головы, который будет перемещать один процесс, и указатель хвоста, который будет перемещать другой процесс.
Блокировки по-прежнему требовались, но мы использовали двухпроцессорный алгоритм Петерсона , который довольно легкий поскольку он не связан с системными вызовами. Блокировка требуется только для очень маленькой, хорошо ограниченной области: максимум несколько циклов ЦП, поэтому вы никогда не блокируете надолго.
Я помню, как несколько лет назад видел одну, которая выглядела интересной, хотя сейчас я не могу ее найти. :( Предлагаемая реализация без блокировки требовала использования примитива CAS , хотя даже реализация блокировки (если вы не хотели использовать примитив CAS) имела довольно хорошие характеристики производительности --- блокировки только не позволяли нескольким читателям или нескольким производителям попадать в очередь одновременно, производитель по-прежнему никогда не гонялся с потребителем.
Я действительно помню, что фундаментальная концепция очереди заключалась в создании связного списка, в котором всегда был один дополнительный «пустой» узел. Этот дополнительный узел означал, что указатели заголовка и хвоста списка всегда будут ссылаться на одни и те же данные, только когда список пуст. Хотел бы я найти эту статью, я не оправдываю алгоритм в своих объяснениях ...
Ага!
Я нашел человека, который переписал алгоритм без остатка статьи . Это может быть полезной отправной точкой.
Этот дополнительный узел означал, что указатели заголовка и хвоста списка всегда будут ссылаться на одни и те же данные, только когда список пуст. Хотел бы я найти эту статью, я не оправдываю алгоритм в своих объяснениях ...Ага!
Я нашел человека, который переписал алгоритм без остатка статьи . Это может быть полезной отправной точкой.
Этот дополнительный узел означал, что указатели заголовка и хвоста списка всегда будут ссылаться на одни и те же данные, только когда список пуст. Хотел бы я найти эту статью, я не оправдываю алгоритм в своих объяснениях ...Ага!
Я нашел человека, который переписал алгоритм без остатка статьи . Это может быть полезной отправной точкой.
Да.
Существует несколько безблокирующих очередей с несколькими считывателями и несколькими записывающими устройствами.
Я реализовал одну, написанную Майклом и Скоттом, из их статьи 1996 года.
Я (после некоторого дополнительного тестирования) выпущу небольшую библиотеку структур данных без блокировок (на языке C), которая будет включать эту очередь.
Добавление malloc убьет любой прирост производительности, и структура, основанная на блокировке, будет такой же эффективной. Это так, потому что malloc требует своего рода блокировку CAS через кучу и, следовательно, некоторые формы malloc имеют свою собственную блокировку, так что Вы можете быть заблокированы в Менеджере Памяти.
Чтобы использовать malloc, вам нужно будет предварительно выделить все узлы и управлять ими с помощью другой очереди....
Обратите внимание, что можно сделать некий расширяемый массив, который нужно заблокировать, если он был расширен.
Также, когда блокировка свободна на процессоре, они помещают блокировку памяти и блокируют память на время выполнения команды и часто останавливают конвейер.