на самом деле http://c2.com/cgi/wiki?DeadLock, спасибо за идею. но там упоминаются только те самые два способа, которые я и сам придумал (GiantLock, OrderedLocking). я что ли гений, или где?
Дело в том, что писать программы со сложными алгоритмами locking - очень нехорошо. Это даже хуже, чем широкое использование design patterns. Насколько я понимаю, консенсус примерно такой: если нужны сложные стратегии locking, то у вас уже имеются большие проблемы с факторизацией кода.
Впрочем, это проповеди в пользу бедных. Возможно, проблема действительно требует сложной стратегии locking. Можете саму проблему сформулировать? Мне любопытно.
проблема такая: сходил на джоб интервью, а меня там спрашивают: какие вы применяете методологии для предотвращения дедлоков? а я: фиг знает, пишу просто аккуратно. а им не понравилось. я, правда, потом там смог выдавить что-то про ordered locking, но осадочек остался.
Я склоняюсь к тому, что это был "тест на живость ума" а-ля Воннегут.
Может, речь шла о чем-то вроде баз данных и имелось в виду нечто вроде "читатели не блокируют писателей", оптимистичное locking, пессимистичное и так далее. Но это тема довольно узкая.
Может, речь шла о lock-free алгоритмах и структурах данных (почитайте, кстати, это интересно). Начать можно с чего-нибудь вроде http://c2.com/cgi/wiki?BetterQueue - от этого, думаю, любой интервьюер в осадок выпадет =)
Может, можно было заикнуться об использовании message passing concurrency вместо shared state concurrency.
нет, речь шла совершенно конкретно о предотвращении дедлоков в сишарпном винформовском коде. но ответ от меня ожидали не сишарпно-специфичный, а именно что-то типа GiantLock DP.
Может, речь шла о lock-free алгоритмах
нет, речь шла о дедлоках :-)
Может, можно было заикнуться
нет, речь шла конкретно о дедлоках, а не о синхронизации вообще. я-то как раз начал свой ответ издалека, но меня довольно быстро прервали и спросили "а ты ваще знаешь, что такое дедлок?". там всё жёстко, wall street всё-таки.
дошли руки прочитать про BetterQueue. нич-чего не понимаю. какой в ж[опу] FAIL? я правильно вставляю правильный объект в правильную очередь и вдруг получаю FAIL? суровый design pattern. или я должен
Я не автор этого pattern, но мне думается, что Вы не вполне правы.
Рассуждая по Вашей логике, можно заключить, например, что асинхронный ввод-вывод вообще нахрен не нужен. Что пусть все используют блокирующийся send на socket и полминуты ждут ответа, как миленькие.
Если использовать locks, то при жесткой конкуренции и при отсутствии fairness guarantees у Вас вообще нет уверенности, что вставка объекта в очередь когда-либо завершится. Мне думается, что возвращение FAIL может быть в чем-то предпочтительнее, нет?
Можно, конечно, везде писать цикл. Можно не писать, а, например, поделать что-нибудь другое некоторое время. В другие очереди попробовать что-нибудь повставлять. Да мало ли что.
если нет дедлоков (с чего весь разговор и начался), то использование конструкции
lock(queue){queue.add(myObj)}
гарантирует, что вставка завершится. асинхронные же сокеты вряд ли могут служить тут хоть какой-нибудь аналогией, поскольку там и цели другие, и принципы работы, и вообще всё. из моей логики, заключающейся в том, что вставка валидного объекта в валидную очередь, возвращающая FAIL - это хуёвый дизайн, ненужность асинхронного ввода-вывода никак не следует.
далее, lock() процессор не ест, так что "поделать что-нибудь другое" могут остальные треды. а наш занят тем, что в очередь вставляет. вы представляете себе, насколько это решение с FAIL усложняет код, пользующийся такой "очередью"?
Locking - очень медленная операция. Ее хочется избежать. Насколько я понимаю ограничения этой задачки - systems programming как-никак, тормозить нельзя - malloc тоже хочется по мере возможности избегать. Если malloc запрещен вообще, то волей-неволей иногда придется возвращать FAIL.
Если очень хочется, можно попробовать сейчас придумать вариант получше. Граничные условия:
1) по минимуму malloc 2) нет locking 3) не возвращается FAIL на put 4) более-менее линейное расположение данных в памяти
У меня что-то пока не очень получается. Впрочем, я вообще не слишком умный.
ну, malloc надо просто делать каждый раз жаднее в два раза. а линейное - это уж как memory manager даст. я вообще на сишарпе пишу, так что никаких маллоков :-)
Эта идея сразу приходит. Маллок маллоком, но как предлагается данные на новое место двигать, не используя lock? А если он используется в put, то в get мы будем уже вынуждены его использовать.
У меня вопрос off-topic. Скажите, а Вы на C# пишете потому что нравится или потому что corporate policy? Если "нравится", то почему? Если corporate policy, то почему? Это не flamebait, сам я ничо рекламировать не хочу, просто интересно.
нравится. отличия от С++ и Дельфи очевидны (хотя я могу остановиться на них поподробнее, если вам интересно). почему не на джаве - объяснить труднее, но к джаве у меня стойкое отвращение. не к джаве как языку, собственно, а к тому, что вокруг. ни одной IDE приемлемой для джавы я не видел (хотя вот IDEA-ю хвалят, но теперь уж поздно на неё смотреть). да и вообще... куча мелочей в джаве раздражает, а те же мелочи в дотнете сделаны по уму, и это приятно.
Хочется представить себе, какая будет экосистема вокруг CLR лет через пять. Самому мне в это, надеюсь, лезть не придется, а посмотреть со стороны интересно.
оно улучшается стремительным домкратом, куда быстрее, чем джава. новая Visual Studio - это просто песня. они даже украли у меня пару архитектурных решений и захардкодили их :-)
Я смотрю не с точки зрения разработки - я слышал, там действительно рай для разработчика. Я пытаюсь смотреть с точки зрения экосистемы. Меня слегка пугает идея "платформы .Net".
Например, если я пишу сервлеты на Java, то я могу выбирать из кучи серверов (многие из которых open source), соответствующих спецификации Servlet.
А Майкрософт, похоже, меньше делает упор на "спецификации" и больше на "реализацию" - мне предлагается доверять их реализациям и принимать на веру обещания насчет обратной совместимости.
JDBC - это сановская спецификация на драйверы. Не реализация.
J2EE - это спецификация. У нее есть, например, open source реализация JBoss.
Аналогично - JMX, Servlets/JSP и так далее. Есть не-сановские компиляторы Java. Есть не-сановские IDE. Есть не-сановские библиотеки, которые стали де-факто стандартом - например, log4j.
Модель Sun: выпустить spec и reference implementation. Модель Microsoft - выпустить реализацию, которая сама по себе является spec.
сановская модель хороша только в теории. на практике получается, что спецификации описывают не всё и мы имеем, например, implementation-specific deployment descriptors, что делает процесс перехода, например, с JBOSS на Weblogic невыносимо болезненным. спецификация сервлетов - это вообще просто набор интерфейсов, дотнет в этом плане ничем не хуже. ну и, наконец, девелоперу с майкрософтовскими продуктами работать в основном удобно, а с продуктами open source в основном неудобно. чтобы понять, почему, достаточно задуматься над силами, движущими майкрософтовским девелопером и опенсорсным девелопером.
тьфу, опять повёлся на дискуссию о победе разума над здравым смыслом.
Очередь с одним писателем - это типичный случай. Более того, когда писатель один и читатель один - это тоже типичный случай, внутри первого типичного случая.
Конечно, если о скорости не беспокоиться, можно на уровне системы реализовать (например) process pipe, которая будет лочиться на каждое чтение/запись. Тогда эти локи и будут ограничивающим фактором для
Rewriting get() to be safe for multiaccess. We need to isolate getPoint and update it successfully. This implies we need to synchronize the get() function on getPoint, and synchronize the put() function on putPoint. They should not both synchronize on the same monitor, as this may result in processes missing a relevant notify.
Imho на deadlock просто в отладчике аттачишься, останавливаешься и смотришь. Системы блокировок это для слабых духом, ибо deadlock это просто фигня. Race страшнее т.к. хрен найдешь. Меня недавно спрашивали "а как ты выцепляещь Race Condition". Первое, что я ответил было "Стресс тест". Следующий вопрос "ну ладно, а еще? Есть тулзы какие?" Я сказал "Intel Thread Checker" после чего мне сказали "отлично. хватит!", и я даже не успел сказать что я думаю об этой тулзе...
Это не мне. Это Eric Raymond - The Art of UNIX Programming, там много ругательств на ОО вообще и design methodologies в частности. Причем ругательства IMHO вполне обоснованные.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2005-01-14 07:22 am (UTC)и дальше по ссылкам
(no subject)
Date: 2005-01-14 02:32 pm (UTC)(no subject)
Date: 2005-01-14 02:58 pm (UTC)Дело в том, что писать программы со сложными алгоритмами locking - очень нехорошо. Это даже хуже, чем широкое использование design patterns. Насколько я понимаю, консенсус примерно такой: если нужны сложные стратегии locking, то у вас уже имеются большие проблемы с факторизацией кода.
Впрочем, это проповеди в пользу бедных. Возможно, проблема действительно требует сложной стратегии locking. Можете саму проблему сформулировать? Мне любопытно.
(no subject)
Date: 2005-01-14 04:55 pm (UTC)(no subject)
Date: 2005-01-14 09:02 pm (UTC)Может, речь шла о чем-то вроде баз данных и имелось в виду нечто вроде "читатели не блокируют писателей", оптимистичное locking, пессимистичное и так далее. Но это тема довольно узкая.
Может, речь шла о lock-free алгоритмах и структурах данных (почитайте, кстати, это интересно). Начать можно с чего-нибудь вроде http://c2.com/cgi/wiki?BetterQueue - от этого, думаю, любой интервьюер в осадок выпадет =)
Может, можно было заикнуться об использовании message passing concurrency вместо shared state concurrency.
Правда, это все как-то не вполне в тему...
(no subject)
Date: 2005-01-14 09:30 pm (UTC)нет, речь шла совершенно конкретно о предотвращении дедлоков в сишарпном винформовском коде. но ответ от меня ожидали не сишарпно-специфичный, а именно что-то типа GiantLock DP.
Может, речь шла о lock-free алгоритмах
нет, речь шла о дедлоках :-)
Может, можно было заикнуться
нет, речь шла конкретно о дедлоках, а не о синхронизации вообще. я-то как раз начал свой ответ издалека, но меня довольно быстро прервали и спросили "а ты ваще знаешь, что такое дедлок?". там всё жёстко, wall street всё-таки.
(no subject)
Date: 2005-01-14 09:42 pm (UTC)http://www2.cs.uregina.ca/~hamilton/courses/330/notes/synchro/deadlock-ex.html
(no subject)
Date: 2005-01-17 07:54 am (UTC)(no subject)
Date: 2005-01-18 12:00 pm (UTC)Рассуждая по Вашей логике, можно заключить, например, что асинхронный ввод-вывод вообще нахрен не нужен. Что пусть все используют блокирующийся send на socket и полминуты ждут ответа, как миленькие.
Если использовать locks, то при жесткой конкуренции и при отсутствии fairness guarantees у Вас вообще нет уверенности, что вставка объекта в очередь когда-либо завершится. Мне думается, что возвращение FAIL может быть в чем-то предпочтительнее, нет?
Можно, конечно, везде писать цикл. Можно не писать, а, например, поделать что-нибудь другое некоторое время. В другие очереди попробовать что-нибудь повставлять. Да мало ли что.
(no subject)
Date: 2005-01-18 12:23 pm (UTC)lock(queue){queue.add(myObj)}гарантирует, что вставка завершится. асинхронные же сокеты вряд ли могут служить тут хоть какой-нибудь аналогией, поскольку там и цели другие, и принципы работы, и вообще всё. из моей логики, заключающейся в том, что вставка валидного объекта в валидную очередь, возвращающая FAIL - это хуёвый дизайн, ненужность асинхронного ввода-вывода никак не следует.далее, lock() процессор не ест, так что "поделать что-нибудь другое" могут остальные треды. а наш занят тем, что в очередь вставляет. вы представляете себе, насколько это решение с FAIL усложняет код, пользующийся такой "очередью"?
(no subject)
Date: 2005-01-18 12:40 pm (UTC)Если очень хочется, можно попробовать сейчас придумать вариант получше. Граничные условия:
1) по минимуму malloc
2) нет locking
3) не возвращается FAIL на put
4) более-менее линейное расположение данных в памяти
У меня что-то пока не очень получается. Впрочем, я вообще не слишком умный.
(no subject)
Date: 2005-01-18 01:12 pm (UTC)(no subject)
Date: 2005-01-18 01:16 pm (UTC)(no subject)
Date: 2005-01-18 01:33 pm (UTC)(no subject)
Date: 2005-01-18 02:01 pm (UTC)(no subject)
Date: 2005-01-19 01:24 am (UTC)(no subject)
Date: 2005-01-19 05:47 am (UTC)(no subject)
Date: 2005-01-19 12:36 pm (UTC)(no subject)
Date: 2005-01-19 01:41 pm (UTC)(no subject)
Date: 2005-01-19 02:17 pm (UTC)Например, если я пишу сервлеты на Java, то я могу выбирать из кучи серверов (многие из которых open source), соответствующих спецификации Servlet.
А Майкрософт, похоже, меньше делает упор на "спецификации" и больше на "реализацию" - мне предлагается доверять их реализациям и принимать на веру обещания насчет обратной совместимости.
Аналогичная ситуация с JDBC и так далее.
(no subject)
Date: 2005-01-20 07:44 am (UTC)(no subject)
Date: 2005-01-20 11:23 am (UTC)J2EE - это спецификация. У нее есть, например, open source реализация JBoss.
Аналогично - JMX, Servlets/JSP и так далее. Есть не-сановские компиляторы Java. Есть не-сановские IDE. Есть не-сановские библиотеки, которые стали де-факто стандартом - например, log4j.
Модель Sun: выпустить spec и reference implementation. Модель Microsoft - выпустить реализацию, которая сама по себе является spec.
(no subject)
Date: 2005-01-20 11:47 am (UTC)сановская модель хороша только в теории. на практике получается, что спецификации описывают не всё и мы имеем, например, implementation-specific deployment descriptors, что делает процесс перехода, например, с JBOSS на Weblogic невыносимо болезненным. спецификация сервлетов - это вообще просто набор интерфейсов, дотнет в этом плане ничем не хуже. ну и, наконец, девелоперу с майкрософтовскими продуктами работать в основном удобно, а с продуктами open source в основном неудобно. чтобы понять, почему, достаточно задуматься над силами, движущими майкрософтовским девелопером и опенсорсным девелопером.
тьфу, опять повёлся на дискуссию о победе разума над здравым смыслом.
(no subject)
Date: 2005-01-20 03:48 pm (UTC)(no subject)
Date: 2005-01-18 12:50 pm (UTC)гарантирует, что вставка завершится.
Зато при Вашем подходе писатель может заставить читателя голодать вечно. Понимаю, что nitpick, но все же =))
(no subject)
Date: 2005-01-18 01:07 pm (UTC)при внимательном перечтении статьи обнаружилось, что это вообще будет работать для только одного писателя и только одного читателя. неинтересно.
(no subject)
Date: 2005-01-18 01:15 pm (UTC)Очередь с одним писателем - это типичный случай. Более того, когда писатель один и читатель один - это тоже типичный случай, внутри первого типичного случая.
Конечно, если о скорости не беспокоиться, можно на уровне системы реализовать (например) process pipe, которая будет лочиться на каждое чтение/запись. Тогда эти локи и будут ограничивающим фактором для
ls -l | grep "ляля" | more
или тому подобной фигни...
Впрочем, на вкус и цвет товарищей нет =)
(no subject)
Date: 2005-01-18 01:25 pm (UTC)(no subject)
Date: 2005-01-18 01:27 pm (UTC)Rewriting get() to be safe for multiaccess. We need to isolate getPoint and update it successfully. This implies we need to synchronize the get() function on getPoint, and synchronize the put() function on putPoint. They should not both synchronize on the same monitor, as this may result in processes missing a relevant notify.
(no subject)
Date: 2005-01-18 12:34 pm (UTC)(no subject)
Date: 2005-01-14 09:26 pm (UTC)Меня недавно спрашивали "а как ты выцепляещь Race Condition". Первое, что я ответил было "Стресс тест". Следующий вопрос "ну ладно, а еще? Есть тулзы какие?" Я сказал "Intel Thread Checker" после чего мне сказали "отлично. хватит!", и я даже не успел сказать что я думаю об этой тулзе...
(no subject)
Date: 2005-01-14 09:35 pm (UTC)(no subject)
Date: 2005-01-14 09:39 pm (UTC)я, кстати, забыл вам 5 за эту фразу поставить :-)
(no subject)
Date: 2005-01-14 09:46 pm (UTC)