двойная очередь - есть у этого паттерна название?
вопрос: этому есть какоенить название? есть ли упоминание в какойнить классической книжке?Сомневаюсь. Если я тебя правильно понял, то оно не будет работать.
Если я тебя правильно понял, то оно не будет работать.неправильно понял...
неправильно понял...Ну хорошо. Код где-то посмотреть можно?
Read Write Lock?
А использовать классическое FIFO не судьба?
А использовать классическое FIFO не судьба?что ты имеешь ввиду?
что такое по-твоему "классическое FIFO"
помойму это идея, а у идеи может быть несоклько реализаций
я говорю про 2 вполне конкретный реализации
Ну хорошо. Код где-то посмотреть можно?а что непонятного то?
func read {
if readQueue.size = 0 {
if(writeQueue.size = 0)
throw exception: queue is empty or wait for data
else switchQueues
}
return readQueue.head;
}
func write(obj) {
writeQueue.addTail(obj);
}
func switchQueues {
lock (readQueue, writeQueue);
readQueue ^= writeQueue ^= readQueue;
unlock(readQueue, writeQueue);
}
как-то так
ток я терь чото перестал порнимать как write и switchQueues засинкятся
Вопрос на засыпку: корректно ли будет работать следующий код на джаве, использующийся для лейзи инициализации, в малтитред енвайронментах?
class Config {
private IAmLazy lazy = null;
public IAmLazy getLazy {
if (lazy == null) {
synchronized(this) {
if (lazy == null)
lazy = new IAmLazy;
}
}
return lazy;
}
}
ток я терь чото перестал порнимать как write и switchQueues засинкятсяа я с самого начала не понимаю
потому и прошу кодток я терь чото перестал порнимать как write и switchQueues засинкятсяне вижу проблемы...
не вижу проблемы...раз не видишь, то ответь, пожалуйста, на
Вопрос на засыпкупричем тут этот вопрос?
и на какую такую он засыпку если он боянный?
причем тут этот вопрос?Ты подожди, дай 'у на него ответить. А то видишь, вон у него проблем нету.
и на какую такую он засыпку если он боянный?
//А вообще понятно при чем - если начать реализовывать твой паттерн на джаве, то у тебя будет все та же синхронизация. Все та же java memory model. Все те же грабли.
ну просто я про алгоритм спрашивал, а ты мне про джаву
паттерн его ж на любом языке можно реализовать
паттерн его ж на любом языке можно реализовать
Вопрос на засыпку: корректно ли будет работать следующий код на джаве, использующийся для лейзи инициализации, в малтитред енвайронментах?Мне кажется, что неработоспособность этого примера в каких то ситуациях - это большая проблема Java. Кстати, я на этот вопрос не ответил на одном из собеседований, настолько привык, что за нас обо всём подумали.
а зачем локи использовать?
есть же очереди на атомарных операциях
//хотя они и не без ограничений, конечно
есть же очереди на атомарных операциях
//хотя они и не без ограничений, конечно
я уж подумал, я чего-то в жизни не понимаю, а оказывается - в Java. но здесь о жизни
есть же очереди на атомарных операцияхУгу, они и в Java имеются. Не понятно, почему автор не хочет взять готовую реализацию.
есть же очереди на атомарных операцияха реализованы они часом не так, как автор не хочет?
Мне кажется, что неработоспособность этого примера в каких то ситуациях - это большая проблема Java. Кстати, я на этот вопрос не ответил на одном из собеседований, настолько привык, что за нас обо всём подумали.К сожалению, боюсь, слово java можно заменить на "любой оптимизирующий компилятор".
В си шарпе та же дребедень, и синтаксически такой же фикс через volatile.
В си++ то же самое и другой фикс через мемори барьеры.
<pick your favorite language here>
я уж подумал, я чего-то в жизни не понимаю, а оказывается - в Java. но здесь о жизникак раз я о жизни. а вы о сферических конях в вакууме.
как раз я о жизни. а вы о сферических конях в вакууме.ах, вот оно что, это в каждом языке своё...
а как это применится к описанному примеру?
насколько я знаю, чего-чего, а семафоров и мутексов в таких реализациях обычно нет, так как смысл теряется
правда есть барьеры памяти и атомарные операции процессора, но это в любом случае не медленнее
правда есть барьеры памяти и атомарные операции процессора, но это в любом случае не медленнее
К сожалению, боюсь, слово java можно заменить на "любой оптимизирующий компилятор".Оптимизации не портят этот пример, на x86 будет прекрасно работать. Этот пример портят многопроцессорные SPARK-и. Беда в том, что через volatile ты это не пофиксишь.
В си шарпе та же дребедень, и синтаксически такой же фикс через volatile.
Беда в том, что через volatile ты это не пофиксишь.Смотря где. В джаве since 1.5 - думаю пофиксю =)
а на x86_64 ?
Смотря где. В джаве since 1.5 - думаю пофиксю =)Ну с какой-то версии это типа не надо фиксить, они сами всё сделали. Но проблема была в том, что это не работало даже с volatile переменной. ИМХО, какой-то бред, этим должны заниматься не прикладники, а разработчики языка.
а на x86_64 ?Там была проблема только на многопроцессорных SPARK-ах.
Ну с какой-то версии это типа не надо фиксить, они сами всё сделали. Но проблема была в том, что это не работало даже с volatile переменной. ИМХО, какой-то бред, этим должны заниматься не прикладники, а разработчики языка.С какой это не надо? Имхо и сейчас, в 1.6_u10 надо.
До 1.5 - да, volatile не работало. В общем-то бред, согласен. Впрочем как и любая другая дыра в абстракции.
С какой это не надо? Имхо и сейчас, в 1.6_u10 надо.Да я не про volatile, я про проблему, которая возникала именно на многопоточных SPARK-ах. Она возникала даже с volatile. Почему-то собеседующий напирал на то, что я просто обязан был это где-то когда-то прочитать, если вообще интересовался многопоточными программами...
Да я не про volatile, я про проблему, которая возникала именно на многопоточных SPARK-ах. Она возникала даже с volatile. Почему-то собеседующий напирал на то, что я просто обязан был это где-то когда-то прочитать, если вообще интересовался многопоточными программами...Если честно, я не очень в курсе, что там конкретно возникало на многопоточных спарках =( Да и может там был баг в реализации jvm, может там была не джава 1.5, мало ли чего хотел тот собеседующий.
В своих измышлениях я ограничиваюсь спецификацией (jsl) =)
еще бывают очереди, в которых делается отдельный лок на хвост и отдельный лок на голову
они типа позволяют использовать несоклько потоков записывальщиков и несоклько потоков считывальщиков
про них такой же вопрос
http://www.python.org/doc/2.5.2/lib/QueueObjects.html
а я не про volatile, я про проблему, которая возникала именно на многопоточных SPARK-ах. Она возникала даже с volatile.а какая проблема возникала на спарках, не помнишь, может ссылки есть?
стало интересно, мне всегда казалось, что чтения/записи (по одному адресу во всяком случае) в память для процессорных типов упорядочиваются аппаратно контроллером памяти или где-то там (а Java'овские ссылки ,я так понимаю, должены представляться машинным словом)
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLo... похоже на нужное? я в яве не разбираюсь, но что касается сложностей в С++ - там всё верно написано
в середине там про Aplha ссылочка на обсуждение есть
в середине там про Aplha ссылочка на обсуждение есть
спасибо, кажется , именно то, что нужно (хоть я и чуть не сломал себе мозг )
)В си шарпе та же дребедень, и синтаксически такой же фикс через volatile.
Нет.
В шарпе любой синхронизационный примитив работает как memory barrier. То есть если ты пишешь lock, то компилятор никакие чтения/записи через него переносить не будет. Более того, у слова volatile в шарпе совершенно не тот смысл, что в плюсах, например: доступ к volatile полю считается использованием синхронизационного примитива, точка. То есть я могу написать
int a;
volatile int b;
...
a = 10;
b = 2;
return a;
и оптимизатор не выкинет второй доступ к а.
Там были какие-то ещё дополнительные тонкости, слегка менявшие модель между 1.0, 1.1, 2.0 и 3.0 фреймворками, но общая суть такова, кажется.
Беда в том, что через volatile ты это не пофиксишь.Может быть, это проблема компилятора?
Вот что я нашёл:
Microsoft CL 14.0.0 and later versions tighten the restrictions on the types of reordering that can occur around volatile variables. In these compilers, reads from volatile locations are treated as acquires and writes to volatile locations are treated as releases on hardware architectures that support these semantics.
чуть не сломал себе мозгСудя по объяснениям собеседующего там всё просто. После выхода из synchronized комитится кэш одного процессора, но только по адресу, где хранится значение переменной. Память, в которой создан объект, не комитится. В это время второй процессор проверяет память, куда закомичено значение переменной, видит что оно не null, и вызывает методы объекта, память которого ещё не закомичена.
ИМХО, бред какой-то.
Судя по объяснениям собеседующего там всё просто. После выхода из synchronized комитится кэш одного процессора, но только по адресу, где хранится значение переменной. Память, в которой создан объект, не комитится. В это время второй процессор проверяет память, куда закомичено значение переменной, видит что оно не null, и вызывает методы объекта, память которого ещё не закомичена.Не, The first reason it doesn't work - это точно другое. Фича там в том, что выхода из synchronized там еще нет, но ссылка на объект уже видна. Это классический reordering, описанный в http://java.sun.com/docs/books/jls/third_edition/html/memory... Единственное, что здесь не очевидно - это то, что создание объекта и вызов конструктора - две различных инструкции VM. Ну а дальше все просто. Есть инструкции
1. Выделение памяти.
2. Вызов конструктора.
3. Присваивание значения полю.
Вот если поменять 2 и 3-ю операции местами, и будет проблема, описанная в статье. Т.е. не только нет записи изменений, но и самих изменений в полях объекта вообще нет и конструктор не выполнен. А объект то уже есть и доступен. И как раз с 1.5 volatile для переменной спасает - он не дает перемещать инструкции, выполняющиеся до п. 3 после неё. Плюс ещё это синхронизация со всем последующими чтениями этой переменной (и только ей! Нет в Java Memory Model такого понятия, как main memory и commit в нее. Видимость изменений описывается только в рамках "синхронизации" на одном и том же "объекте" (synchronized на одном и том же объекте, либо чтение одного и того же volatile поля). В теории это может быть существенно на многопроцессорных машинах, когда при volatile write, например, кэш будет синхронизироваться не со всеми процессорами, а только с частью, на которых будут выполняться нити с соответствующими чтениями).
Фича там в том, что выхода из synchronized там еще нет, но ссылка на объект уже видна.Нет, это вовсе не причина того, что данный подход не работает даже с volatile на многопроцессорных SPARK-ах.
Нет в Java Memory Model такого понятия, как main memory и commit в нее.
Это в Java такого понятия нет. А на многопроцессорных SPARK-ах - есть.
Нет, это вовсе не причина того, что данный подход не работает даже с volatile на многопроцессорных SPARK-ах.Частично согласен. Если брать статью по ссылке http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering..., то мой комментарий к ней плохо относится и reordering там совсем не нужен. Тот пример прекрасно описывает работу модели памяти без volatile переменной (требующей синхронизации при чтении volatile). Уж не знаю, были ли баги в JVM (забытый барьер при чтении volatile но по спецификации 1.4 получается, что volatile помогать в doble checked locking и не должен был, даже при корректной реализации JVM. Там JVM могла коммитить только изменения данных в этой переменной, но не все предыдущие изменения. Т.е. читатель мог увидеть non-null значение переменной, но не увидеть изменений, сделанных в конструкторе. В принципе, этот эффект мог быть достижим как с использованием указанного мною переупорядочивания, так и без него (при возможности выполнения избирательного commit'а в main memory).
В спецификации 1.5 volatile уже должен был помогать на SPARC'ах и если не работал, это уже были ошибки реализации JVM.
Это в Java такого понятия нет. А на многопроцессорных SPARK-ах - есть.Здесь я был не прав
. Оказывается, было таки это понятие в JLS 2nd (Java 1.4, соответственно). В 1.5 такого понятия не стало. Но тогда многопроцессорные SPARK'и хорошо объясняют, откуда получалась соответствующая спецификация.Кстати, похоже, в 1.4 некоторые аспекты Memory Model были все-таки более логичны. Пример:
public class T {
static int val;
public static void main(String [] args) {
Thread t = new Thread(new Runnable {
public void run {
while (true) {
System.out.println(val);
}
}
})
t.setDaemon(false);
t.start;
for (val = 1; val < 10; val++) {}
}
}
В 1.4 с его memory model и глобальным порядком операций над общей памятью получалось, что программа может выводить только неубывающую последовательность чисел.
В 1.5. с его write observed и happens-before оно вроде бы может давать немонотонную последовательность! Может быть, для чистоты эксперимента, стоит считать, например, 100 чисел в массив и только после этого выводить (чтобы не было external action между чтениями). Я несколько раз искал соответствующее место в JLS, так и не нашёл. Похоже, что никаких особых ограничений на write observed кроме happens before ordership нет. Casuality requirement здесь, похоже, тоже не при чем... Там commit можно делать для одной операции чтения val во внутреннем цикле. Соответственно, на следующем этапе коммитов мы можем выбрать для только что закоммиченой операции произвольное записанное значение (Wi, write seen) для этого чтения (при коммите самой операции чтения она обязана была видеть 0).
В 1.5. с его write observed и happens-before оно вроде бы может давать немонотонную последовательность!что-то мне кажется, что ты этого jls'а переботал =)
на x86 будет прекрасно работать.разве на многопроцессорных x86 проблемы нет, такой же как на spark-ах?
ИМХО, бред какой-то.имхо не такой уж и бред для многопроцессорных систем (но хз, сколько это реально дает в производительности но писать под такие системы - это жесткач , нужно бл., все время быть на чеку и не забывать вставлять memoryBarrier'ы....
тут вот написали, что если бы доступы к volatile переменным не только не оптимизировались бы, но и окружались бы memoryBarrier'ами (или достаточно только после вставлять... то все было бы ок, имхо , если бы так сделали когда-нибудь в будущем (ну или еще одно ключевое слово введут было бы здорово, а то стандарты обновляют, всякую хню (имхо) типа strict_aliasing по умолчанию включают
на x86 нет такого тотально memory reordering'а , как на спарках, так что там все ок
на x86 нет такого тотально memory reordering'а , как на спарках, так что там все окесли синхронайз не вызывает memorybarrier, то проблемы будут, т.к. результат будет просто висеть в кэше одного процессора, а на другом проце успешно вызовется еще раз
"... В это время второй процессор проверяет память, куда закомичено значение переменной, видит что оно не null, и вызывает методы объекта" ----- второй процессор не входит еще в synchronized, а читает значение указателья - который уже не нул, заявка от первого процессора, что надо инвалидировать кэш для объекта (куда указатель теперь указывает) приходила и он на нее ответил (но физически кэш не очисил (-- x86 так не делают) - потому что на втором роцессоре не было memoty_barrier'а) и затем сразу успел прочитать из кэша (который еще не инвалидировался) старое значени объекта... как-то так.
После выхода из synchronized комитится кэш одного процессора, но только по адресу, где хранится значение переменной.а в честь чего будет закомитчено именно значение переменной, а не this?
заявка от первого процессора, что надо инвалидировать кэш для объектаа это из-за чего происходит? при любом обращении/изменении памяти?
эту цитату не надо было мне включать, на первом комитится все и, указатель и объект, но прикол в том , что второй процессор читает обновленное значение указатели и старое значение объекта из-за того, что ктуто там у себя все переупорядочил
насколько я понял, заявки должны рассылаться при испольнении memory_barierrа (он , понятное дело должен быть во входих и во выходах synchronized)
разве на многопроцессорных x86 проблемы нет, такой же как на spark-ах?В приведённом коде с volatile - нет.
В приведённом коде с volatile - нет.меня интересует тот код, который приведен (без всяких volatile)?
меня интересует тот код, который приведен (без всяких volatile)?Без всяких volatile тут и так все всё понимают. Интересным моментом были только SPARK-и.
тут вот написали, что если бы доступы к volatile переменным не только не оптимизировались бы, но и окружались бы memoryBarrier'ами (или достаточно только после вставлять... то все было бы ок, имхо , если бы так сделали когда-нибудь в будущем (ну или еще одно ключевое слово введут было бы здорово, а то стандарты обновляют, всякую хню (имхо) типа strict_aliasing по умолчанию включаютЯ уже цитировал текст, в котором утверждалось, что компилятор CL начиная с какой-то версии вставляет memoryBarrier-ы для volatile-ов. Интересно, как с этим у gcc.
Оставить комментарий
pitrik2
допустим есть 2 потока, один кладет в очередь, а другой из нее считывает, т.е. классич. FIFOпотока 2, значит нада синхронизировать
простейший вариант - лок всей очереди при каждом чтении/записи
но если очередь пустеет редко, то на локи тратится слишком много времени
поэтому можно завести 2 очереди
в одну класть, из другой считывать
если при считывании там не остается записей, то делается лок и очереди менются местами
вопрос: этому есть какоенить название? есть ли упоминание в какойнить классической книжке?
еще бывают очереди, в которых делается отдельный лок на хвост и отдельный лок на голову
они типа позволяют использовать несоклько потоков записывальщиков и несоклько потоков считывальщиков
про них такой же вопрос