list :: empty () многопоточное поведение?

9

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

Это нормально, если вызов list::empty()100% времени неправильный. Я только хочу , чтобы избежать сбоя или нарушений одновременно list::push()и list::pop()вызовов.

Могу ли я предположить, что VC ++ и Gnu GCC только иногда empty()ошибаются и ничего хуже?

if(list.empty() == false){ // unprotected by mutex, okay if incorrect sometimes
    mutex.lock();
    if(list.empty() == false){ // check again while locked to be certain
         element = list.back();
         list.pop_back();
    }
    mutex.unlock();
}
Энн Куинн
источник
1
Нет, ты не можешь предположить это. Вы можете использовать параллельный контейнер, такой как VC concurrent_queue
Panagiotis Kanavos
2
@Fureeish Это должен быть ответ. Я бы добавил, что std::list::sizeэто гарантирует постоянную сложность по времени, что в основном означает, что размер (количество узлов) необходимо хранить в отдельной переменной; давайте назовем это size_. std::list::emptyзатем, вероятно, возвращает что-то как size_ == 0, и одновременное чтение и запись size_вызовут гонку данных, следовательно, UB.
Даниэль Лангр
@DanielLangr Как измеряется «постоянное время»? Это один вызов функции или полная программа?
любопытный парень
1
@curiousguy: DanielLangr ответил на ваш вопрос «независимо от количества узлов списка», то есть точное определение O (1) означает, что каждый вызов выполняется менее чем за некоторое постоянное время, независимо от количества элементов. en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions Другой вариант (до C ++ 11) будет линейным = O (n), что означает, что размер должен будет учитывать элементы (связанный список), что будет еще хуже для параллелизм (более очевидная гонка данных, чем неатомарное чтение / запись на счетчике).
Фирда
1
@curiousguy: Если взять твой собственный пример с dV, сложность времени такая же, как и в математике. Все эти вещи определяются либо рекурсивно, либо в форме «существует C, такой что f (N) <C для каждого N» - то есть определение O (1) (для данного / каждого HW существует постоянная C, такая что алгоритм заканчивается в C-time меньше времени на любом входе). Амортизированный означает в среднем , что означает, что для обработки некоторых входных данных может потребоваться больше времени (например, требуется повторное хеширование / перераспределение), но в среднем оно остается постоянным (с учетом всех возможных входных данных).
Фирда

Ответы:

10

Это нормально, если вызов list::empty()100% времени неправильный.

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

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

NathanOliver
источник
Личные перспективы, вызов list::empty()является действием чтения , которое не имеет ничего общего сrace-condition
Ngọc Khánh Nguyễn
3
@ NgọcKhánhNguyễn Если они добавляют элементы в список, это, безусловно, вызывает гонку данных, когда вы пишете и читаете размер одновременно.
Натан Оливер
6
@ NgọcKhánhNguyễn Это неверно. Условие гонки - read-writeили write-write. Если вы не верите мне, прочитайте стандартный раздел о гонках данных
NathanOliver
1
@ NgọcKhánhNguyễn: Поскольку ни запись, ни чтение не гарантированно являются атомарными, поэтому они могут выполняться одновременно, поэтому чтение может привести к совершенно неправильным результатам (так называемое чтение с разрывом). Представьте, что запись изменяется от 0x00FF до 0x0100 в 8-битном MCU с прямым порядком байтов, начиная с перезаписи низкого 0xFF до 0x00, и теперь чтение получает именно этот ноль, читая оба байта (запись замедлена или приостановлена), запись продолжается путем обновления старшего байта до 0x01, но поток чтения уже получил неправильное значение (ни 0x00FF, ни 0x0100, а неожиданное 0x0000).
Фирда
1
@ NgọcKhánhNguyễn Это может быть на некоторых архитектурах, но виртуальная машина C ++ не дает такой гарантии. Даже если бы ваше оборудование имело место, для компилятора было бы законно оптимизировать код таким образом, чтобы вы никогда не увидели изменения, поскольку, если нет синхронизации потоков, он может предположить, что он работает только в одном потоке, и оптимизировать соответствующим образом.
Натан Оливер
6

Существует чтение и запись (скорее всего, для sizeчлена std::list, если мы предположим, что он назван так), которые не синхронизированы друг с другом . Представьте, что один поток вызывает empty()(в вашем внешнем if()), в то время как другой поток входит во внутренний if()и выполняет pop_back(). Затем вы читаете переменную, которая, возможно, изменяется. Это неопределенное поведение.

Fureeish
источник
2

В качестве примера того, как все может пойти не так:

Достаточно умный компилятор мог видеть, что mutex.lock()не может изменить list.empty()возвращаемое значение и, таким образом, полностью пропустить внутреннюю ifпроверку, что в конечном итоге привело к появлению pop_backв списке, в котором последний элемент был удален после первого if.

Почему это может сделать это? Синхронизация отсутствует list.empty(), поэтому, если бы она была изменена одновременно, это привело бы к гонке данных. Стандарт гласит, что в программах не должно быть гонок данных, поэтому компилятор примет это как должное (в противном случае он может почти не выполнять оптимизацию). Следовательно, он может предполагать однопоточный подход к несинхронизированным list.empty()и делать вывод, что он должен оставаться постоянным.

Это только одна из нескольких оптимизаций (или поведения оборудования), которые могут сломать ваш код.

Макс Лангоф
источник
Текущие компиляторы даже не хотят оптимизировать a.load()+a.load()...
curiousguy
1
@curiousguy Как бы это оптимизировать? Вы запрашиваете полную последовательную согласованность там, так что вы получите это ...
Макс Лангхоф
@MaxLanghof Вы не думаете, что оптимизация к a.load()*2очевидна? Даже a.load(rel)+b.load(rel)-a.load(rel)не оптимизирован в любом случае. Ничего. Почему вы ожидаете, что блокировки (которые по сути имеют последовательность seq) будут более оптимизированы?
любопытный парень
@curiousguy Потому что порядок памяти неатомарных обращений (здесь до и после блокировки) и атомарности совершенно разные? Я не ожидаю, что блокировка будет оптимизирована «больше», я ожидаю, что несинхронизированный доступ будет оптимизирован больше, чем последовательный согласованный доступ. Наличие замка не имеет значения для моей точки зрения. И нет, компилятор не может оптимизируют a.load() + a.load()к 2 * a.load(). Не стесняйтесь задавать вопрос об этом, если вы хотите узнать больше.
Макс
@MaxLanghof Я понятия не имею, что вы даже пытаетесь сказать. Замки по существу последовательно последовательны. Почему реализация пытается выполнять оптимизацию для одних потоковых примитивов (блокировок), а не для других (атомарных)? Ожидаете ли вы, что неатомные обращения будут оптимизированы для использования атомных операций?
любопытный парень