Здравствуйте, Maxim S. Shatskih, Вы писали:
>>языку[/url] утверждается, что он предотвращает возможность дэдлоков.
MSS>Правильно написанная реализация мутекса предотвращает возможность дедлоков.
MSS>Кстати, дедлок вообще не есть проблема, при соблюдении парочки простейших правил.
Можно пример? И реализации mutex'а, u парочки простейших правил. Как мне кажется, дедлоки -- это достаточно фундаментальная проблема связанная с особым взглядом (парадигмой) на синхронизацию потоков, а именно через mutex'ы, семафоры и прочее.
Здравствуйте, Курилка, Вы писали:
К>Хотелось обратить внимание на E, который написан в результате работы над диссертацией(защищаться в мае будет ). Сам ещё не очень хорошо разобрался с тонкостями предлагаемого конвейерного механизма, но в драфте учебника по языку утверждается, что он предотвращает возможность дэдлоков.
Здравствуйте, Курилка, Вы писали:
К>Хотелось обратить внимание на E, который написан в результате работы над диссертацией(защищаться в мае будет ). Сам ещё не очень хорошо разобрался с тонкостями предлагаемого конвейерного механизма, но в драфте учебника по языку утверждается, что он предотвращает возможность дэдлоков.
И ничего удивительного, ведь для взаимодействия процессов они используют асинхронное взаимодействие, обозванное Promise-ами и закомуфлированное за специальным синтаксическим сахаром.
Кстати, не понятно, зачем им потребовалось новый язык создавать (для Ph.D что ли?), при существовании-то Erlang-а? Более того, асинхронное взаимодействие можно и в существующие языки добавлять (которые изначально таких возможностей не содержали). Скажем, в виде фреймворка
Здравствуйте, dshe, Вы писали:
D>Можно пример? И реализации mutex'а, u парочки простейших правил.
Дейстрой описаны еще лет сорок назад. Суть идеи в том, что все ресурсы, занимаемые потоком, должны иметь жесткую иерархию, и при занятии "нижележащиз" ресурсов уже должны быть заняты все "вышележащие". Соответственно, мьютексы реализуются так, что каждый поток помнит "уровень" последнего занятого ресурса, и при попытке занять "вышележащий" ресурс получает по рукам. Разумеется, это приводит к расходу ресурсов, зато гарантирует от дедлоков.
Грубо и с ходу оно выглядит так. Это иллюстрация, не обессудьте, не совсем точная и упрощенная.
В TLS заводится поле — "голова списка мутексов, захваченных данной нитью".
В мутексе заводится поле Next, и поле "указатель на TLS нити-владельца".
Перед захватом мутекса смотрится, кто именно им владеет, и обходится дерево по этим указателям. Если в дереве обнаруживается цикл (т.е. если оно на самом деле не дерево) — то возникает exception, который возвращается callerу — или как код ошибки, или через try/catch — механизмы реализации exceptions тут не важны.
Я сам такое делал году в 2000. Прекрасно работает. Причем годится как инструментация кода — если ОСовские мутексы обернуты в макросы типа OSLock и OSUnlock, то можно просто подставить .H файл с инструментированными мутексами, и поймать все дедлоки.
>, u парочки простейших правил.
1) Установить отношение "больше-меньше" между всеми мутексами в системе. И — никогда не захватывать "больший" мутекс, если уже держим "меньший".
2) Не делать "сложных" вызовов наружу, удерживая мутекс. "Сложный" — это тот вызов, который способен позвать callback в твоем же коде той же нитью, что позвали сам "сложный" вызов. Также "сложным" является любой вызов, который может приостановить поток на неизвестное время — blocking в юниксной терминологии.
Все. Правило 2 еще и scalability повышает. А если затянуть гайки с правилом 2, обозвав "сложным" вообще любой вызов, имеющий нетривиальное время исполнения — то повышение scalability будет заметным.
В идеале под мутексом можно звать только операции где-то в экран-полтора Сишного кода — снятие или "положение" объекта в контейнер, атомарное изменение сразу нескольких полей состояния объекта, reference counting и прочее такое.
Скажем, открывать дисковый файл из-под мутекса — уже ИМХО грязновато (хотя допустимо), а читать из сокета, удерживая мутекс — это просто баг и misdesign этого куска кода.
Я даже знаю, как такой misdesign рефакторится — к совокупности возможных состояний объекта добавляется состояние "в процессе чтения", чтение делается:
Obj->State = OBJ_ST_READ_PENDING;
OSUnlock(&MutexWhoGuardsObj);
read(Obj->Socket...);
OSLock(&MutexWhoGuardsObj); Obj->State = OBJ_ST_READ_DONE;
Если есть еще и эвент, ассоциированный со сменой состояния — то еще надо вниз этого кода добавить вызов — просигналить этот эвент.
Именно таким образом в Windows обрабатывается collided page fault, когда сразу несколько нитей споткнулись об одну и ту же отсутствующую страницу.
Еще про правило 2. Для упрощения следования этому правилу в ОС бывают примитивы типа "отдать-мутекс-и-тут-же-атомарно-ждать", типа condvars в юниксе и SignalObjectAndWait в виндах. Сделаны они для того, чтобы не ждать под мутексом.
>Как мне кажется, дедлоки -- это достаточно фундаментальная проблема связанная с особым >взглядом (парадигмой) на синхронизацию потоков, а именно через mutex'ы, семафоры и >прочее.
Ага. Только эта фундаментальная проблема решается тупо и в лоб.
Реальной проблемой дедлоки становятся в вещах типа файловых систем Windows, когда твой код зовется окружающей средой _уже под локом_, и ты еще не совсем понял, под каким именно локом и когда, а документация по этому поводу путаная или отсутствует.
Хотелось обратить внимание на E, который написан в результате работы над диссертацией(защищаться в мае будет ). Сам ещё не очень хорошо разобрался с тонкостями предлагаемого конвейерного механизма, но в драфте учебника по языку утверждается, что он предотвращает возможность дэдлоков.
ГВ>А по-другому не получится. Семафор — простейший объект синхронизации. А дедлоки — следствие беспорядка в использовании семафоров.
Да, да, да. А дальше вспоминается, что у нас говорил проф. Преображенский про разруху короче, все эти "языки программирования без дедлоков" напоминают идею большого мочеулавливателя вокруг унитаза
Здравствуйте, Maxim S. Shatskih, Вы писали:
>>получает по рукам. Разумеется, это приводит к расходу ресурсов, зато гарантирует от дедлоков.
MSS>Это можно делать "в голове" без расхода ресурсов. Реально "в металле" это имеет смысл делать ИМХО только в инструментации кода.
Ну так и контроль типов можно делать в голове, и границы массовом там же отслеживать, однако все эти ошибки приводили и приводят к глюкам, иногда крайне трудноуловимым. Поэтому стоит потратить несколько часов на реализацию механизма, который будет потом спасать годами
Здравствуйте, eao197, Вы писали:
E>Кстати, не понятно, зачем им потребовалось новый язык создавать (для Ph.D что ли?), при существовании-то Erlang-а?
Возможно. Одно дело промышленный язык, другое дело исследовательский. Его проще менять, плюс компилятор/ВМ можно писать на том, что знаеш, а не на том, что выбрали авторы исходной системы.
E>Более того, асинхронное взаимодействие можно и в существующие языки добавлять (которые изначально таких возможностей не содержали).
Как я помню, основная фича там не асинхронность, а capability-based security.
Здравствуйте, dshe, Вы писали:
>>>языку[/url] утверждается, что он предотвращает возможность дэдлоков. MSS>>Правильно написанная реализация мутекса предотвращает возможность дедлоков. MSS>>Кстати, дедлок вообще не есть проблема, при соблюдении парочки простейших правил. D>Можно пример? И реализации mutex'а, u парочки простейших правил. Как мне кажется, дедлоки -- это достаточно фундаментальная проблема связанная с особым взглядом (парадигмой) на синхронизацию потоков, а именно через mutex'ы, семафоры и прочее.
А по-другому не получится. Семафор — простейший объект синхронизации. А дедлоки — следствие беспорядка в использовании семафоров. Есть алгоритмы планирования захвата ресурсов и можно пользовтаься подходом, о котором по-соседству говорит Евгений.
PS.:Тема парадигмы не раскрыта!
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Maxim S. Shatskih, Вы писали:
>>языку[/url] утверждается, что он предотвращает возможность дэдлоков.
MSS>Правильно написанная реализация мутекса предотвращает возможность дедлоков.
MSS>Кстати, дедлок вообще не есть проблема, при соблюдении парочки простейших правил.
Вопрос в том, как эти правила принудительно применять (e.g. против Гашиш Кумаров, хотя все мы человеки )
Здравствуйте, Maxim S. Shatskih, Вы писали:
>>языку[/url] утверждается, что он предотвращает возможность дэдлоков.
MSS>Правильно написанная реализация мутекса предотвращает возможность дедлоков.
MSS>Кстати, дедлок вообще не есть проблема, при соблюдении парочки простейших правил.
Хотелось бы прочитать эти правила , а если еще и компактно сформулированные ...
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Скажем, открывать дисковый файл из-под мутекса — уже ИМХО грязновато (хотя допустимо), а читать из сокета, удерживая мутекс — это просто баг и misdesign этого куска кода.
Файл не файл, но в kernel-mode мультимедии иногда и пересылку сотен килобайт данных вместе с преобразованием форматов, например, делать приходится не только под мутексом, а еще и под спинлоком на повышенном приоритете И никуда не денешься, если в реальном времени данные пересылаются между несколькими потоками, каждый из которых может в произвольный момент захотеть сменить себе формат, остановиться/перезапуститься, а то и вообще закрыться.
MSS>Реальной проблемой дедлоки становятся в вещах типа файловых систем Windows, когда твой код зовется окружающей средой _уже под локом_, и ты еще не совсем понял, под каким именно локом и когда, а документация по этому поводу путаная или отсутствует.
Такая же фигня имеет место в мультимедийных user-mode драйверах, для которых в целях связи с основными потоками предусмотрены callback'и. Драйверу без служебного потока не обойтись, и винда служебный поток заводит, и взаимодействие между ними иногда получается такое, что никакой логики не хватает — просто тупо лезешь дизассемблировать или эксперименты ставить
ЕМ>Файл не файл, но в kernel-mode мультимедии иногда и пересылку сотен килобайт данных вместе с преобразованием форматов, например, делать приходится не только под мутексом, а еще и под спинлоком на повышенном приоритете
Пересылка под спинлоком???? это еще зачем?
Захочет сменить формат? ну пожалуйста, со следующего пакета, а этот пакет будет в старом формате.
Не, правда, не понятно, зачем гонять математику кодека под спинлоком, а тем более работать под спинлоком с сетью.
ЕМ>Такая же фигня имеет место в мультимедийных user-mode драйверах, для которых в целях связи с основными потоками предусмотрены callback'и.
Там вроде документировано было что-то, но маловнятно.
Короче, callback из WINMM зовется — служебной нитью, созданной WINMMовским драйвером, и эта же служебная нить и зовет DeviceIoControl, который шлет пакет в ядро. Это мы выяснили путем исследований. Это приводит к ограничениям, вот они уже документированы.
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Пересылка под спинлоком???? это еще зачем?
Затем, что атомарно нужно обработать несколько потоков данных внутри DPC. А в каждый из потоков в любой момент может поступить запрос на изменение режима работы.
MSS>Захочет сменить формат? ну пожалуйста, со следующего пакета, а этот пакет будет в старом формате.
Форматы самих данных — это полбеды. От формата потока зависит размер внутренних буферов, интервал времени обработки и еще энное количество параметров.
MSS>Не, правда, не понятно, зачем гонять математику кодека под спинлоком
Если бы это был кодек с синхронным управлением — совершенно незачем. А это минипортовый аудио-драйвер, к примеру. Который в любой момент времени может быть позван с другого процессора, ибо ограничений на это нет никаких.
Там со спинлоками еще более забавная ситуация, я ее как-то описывал в соседнем форуме: есть метод IPortWavePci::GetMapping, с помощью которого минипортовый драйвер получает у портового описатель очередного фрагмента данных. Еще с конца 90-х, когда появился этот интерфейс, MS предупреждает, что метод нельзя звать при захваченном спинлоке. А он по сути своей такой, что не может корректно работать без внешней синхронизации. MS ссылается на пример из DDK (драйвер AC'97), в котором перед вызовом этого метода спинлок освобождается, однако в реальном драйвере, что в системе, этого не делается — и понятно, иначе на многопроцессорной машине все взвиснет на фиг. А самое смешное — что рекомендацию за все это время отнюдь не убрали
MSS>а тем более работать под спинлоком с сетью.
Это было бы проблематично прежде всего по причине необходимости ожидания события
ЕМ>>Такая же фигня имеет место в мультимедийных user-mode драйверах, для которых в целях связи с основными потоками предусмотрены callback'и.
MSS>Короче, callback из WINMM зовется — служебной нитью, созданной WINMMовским драйвером, и эта же служебная нить и зовет DeviceIoControl, который шлет пакет в ядро. Это мы выяснили путем исследований. Это приводит к ограничениям, вот они уже документированы.
Только им мало кто следует В итоге имеем рекомендации для процесса Win32, а в рекомендациях для драйвера не имеем ничего, поэтому делаем, как правильно — и получаем дедлоки. Выясняем путем исследований, материмся, переделываем
Здравствуйте, Maxim S. Shatskih, Вы писали:
D>>Можно пример? И реализации mutex'а
MSS>В TLS заводится поле — "голова списка мутексов, захваченных данной нитью".
MSS>В мутексе заводится поле Next, и поле "указатель на TLS нити-владельца".
MSS>Перед захватом мутекса смотрится, кто именно им владеет, и обходится дерево по этим указателям. Если в дереве обнаруживается цикл (т.е. если оно на самом деле не дерево) — то возникает exception, который возвращается callerу — или как код ошибки, или через try/catch — механизмы реализации exceptions тут не важны.
MSS>Я сам такое делал году в 2000. Прекрасно работает. Причем годится как инструментация кода — если ОСовские мутексы обернуты в макросы типа OSLock и OSUnlock, то можно просто подставить .H файл с инструментированными мутексами, и поймать все дедлоки.
А можно еще использовать timeout'ы. Это не так красиво, как приведенное тобой решение, но тоже вполне рабочее. Или даже вообще единственный mutex.
Тем не менее, обнаружить дедлок и разрешить его -- это конечно хорошо. Но это не решает проблему. Дедлоки никуда не деваются -- они просто, может быть, приносят меньше вреда. К слову, что делать если дедлок был обнаружен и возникло исключение? Самое лучшее, что мне приходит в голову, это откатить изменения и разлочить ресурсы до определенного уровня (до какого?) и начать операцию заново. Но как мне кажется, откат измененений -- не всегда тривиальная задача.
И еще, дедлок может возникать не только при использовании mutex'ов. Впрочем, это уже зависит от того, как опредляется понятие дедлока. Если допустить, что дедлок может возникать при синхронизации потоков не только mutex'ами, а и любыми другими механизмами синхронизации, то приведенное решение не универсально (и не может быть универсального решения). В частности, с семафорами дедлоки не обнаруживаются (просто потому, что залочить его может один поток, а разлочить другой, может быть даже тот, который еще и не запущен)
>>, u парочки простейших правил.
MSS>1) Установить отношение "больше-меньше" между всеми мутексами в системе. И — никогда не захватывать "больший" мутекс, если уже держим "меньший". MSS>2) Не делать "сложных" вызовов наружу, удерживая мутекс. "Сложный" — это тот вызов, который способен позвать callback в твоем же коде той же нитью, что позвали сам "сложный" вызов. Также "сложным" является любой вызов, который может приостановить поток на неизвестное время — blocking в юниксной терминологии.
На мой взгляд, у этих правил есть небольшой недостаток -- им трудно следовать в больших, сложных и динамичных системах. Дело в то, что всех мютексов в системе можеть быть очень-очень много и их упорядочивание можеть стать весьма сложной задачей (с учетем того, что неоптимальное упорядочивание чревато существенной потерей производительности). Кроме того, сложная система может быть собрана из многих модулей, разработанных различными разработчиками, независимо друг от друга, которые используют mutex'ы для своих внутренних нужд (т.е. как недокументируемые детали реализации).
Далее, делая такой банальный вызов (виртуального метода):
A a = ...
a.method();
практически никогда нельзя быть уверенным, что он "прост". Он можеть быть простым в классе A, и в потомках B, C, D... Но можеть быть в какой-то новой версии какой-то библиотеки появится потомок Z, в котором method() окажется "сложным". А это создает дополнительные сложности при программировании. Кстати, насколько я понимаю, компилятор не в состоянии обнаружить нарушения правила 2, а для человека, удержание всех вызовов в системе в голове, опять же, может стать непосильной задачей.
dshe,
D>Тем не менее, обнаружить дедлок и разрешить его -- это конечно хорошо. Но это не решает проблему. Дедлоки никуда не деваются -- они просто, может быть, приносят меньше вреда. К слову, что делать если дедлок был обнаружен и возникло исключение?
Скажи пожалуйста, о каком исключении идёт речь?
D>На мой взгляд, у этих правил есть небольшой недостаток -- им трудно следовать в больших, сложных и динамичных системах. Дело в то, что всех мютексов в системе можеть быть очень-очень много и их упорядочивание можеть стать весьма сложной задачей (с учетем того, что неоптимальное упорядочивание чревато существенной потерей производительности). Кроме того, сложная система может быть собрана из многих модулей, разработанных различными разработчиками, независимо друг от друга, которые используют mutex'ы для своих внутренних нужд (т.е. как недокументируемые детали реализации).
Да, и кроме того в соответствующем примере в главе Distributed Computing Алиса просит Боба, потом Алиса просит Кэрол, а Кэрол обращается опять к Бобу. Иерархии нет, но при этом всё разруливается без проблем.
К слову, асинхронные сообщения — гораздо более общий и более гибкий ключ для решения проблемы дедлоков.
D>Тем не менее, обнаружить дедлок и разрешить его -- это конечно хорошо. Но это не решает >проблему. Дедлоки никуда не деваются
Правильно написанный код вообще не создает дедлоков.
>возникать при синхронизации потоков не только mutex'ами, а и любыми другими механизмами >синхронизации,
В рамках нашей дискуссии слово mutex есть синоним слова lock и означает любой примитив синхронизации — хоть ERESOURCE, хоть "synchronized" в яве.
>частности, с семафорами дедлоки не обнаруживаются (просто потому, что залочить его может >один поток, а разлочить другой, может быть даже тот, который еще и не запущен)
За 7 с лишним лет системного программирования ни разу не возникала нужда в семафоре почему-то
D>На мой взгляд, у этих правил есть небольшой недостаток -- им трудно следовать в >больших, сложных и динамичных системах. Дело в то, что всех мютексов в системе можеть >быть очень-очень много
Не больше, чем классов объектов и структурных паттернов.
>независимо друг от друга, которые используют mutex'ы для своих внутренних нужд (т.е. как >недокументируемые детали реализации).
По башке бить. интерфейсы, которые выставлены наружу для широкой публики, не должны зваться под локом. Коллбэки и визиторы тоже не должны зваться под локом. Есть ну-очень очень хочется — то тогда надо документировать.
Что под каким локом зовется, надо документировать точно так же, как и параметры вызова.
D>Далее, делая такой банальный вызов (виртуального метода): D>
D>A a = ...
D>a.method();
D>
D>практически никогда нельзя быть уверенным, что он "прост".
А нефиг перекрываемый виртуальный метод под локом звать. Но если уж совсем никак — то в документации на него описать — "зовется под локом".
>человека, удержание всех вызовов в системе в голове
По умолчанию все зовется при отсутствии удерживаемых локов под локом можно звать только мелкие статические функции, тут же в этом файле, наружу не видные никак.
Если же нужно звать другуе компоненту — неважно, визитора ли, коллбэк ли, или просто другой объект — под локом — то об этом должна быть написана обязательная для ознакомления документация. Такие случаи надо сводить к минимуму.
Lazy Cjow Rhrr, Вы писали:
D>Тем не менее, обнаружить дедлок и разрешить его -- это конечно хорошо. Но это не решает проблему. Дедлоки никуда не деваются -- они просто, может быть, приносят меньше вреда. К слову, что делать если дедлок был обнаружен и возникло исключение?
LCR>Скажи пожалуйста, о каком исключении идёт речь?
Всё, допёрло (исключение при обнаружении цикла в дереве мьютексов).
Здравствуйте, Maxim S. Shatskih, Вы писали:
D>>Тем не менее, обнаружить дедлок и разрешить его -- это конечно хорошо. Но это не решает >>проблему. Дедлоки никуда не деваются
MSS>Правильно написанный код вообще не создает дедлоков.
Абсолютно согласен. Только хитрая реализация mutex'ов не делает этот код более правильным.
>>возникать при синхронизации потоков не только mutex'ами, а и любыми другими механизмами >>синхронизации,
MSS>В рамках нашей дискуссии слово mutex есть синоним слова lock и означает любой примитив синхронизации — хоть ERESOURCE, хоть "synchronized" в яве.
Понятно. На мой взгляд под синхронизацией потоков следует понимать не только защиту данных от одновременного доступа к ним, но и оповещение одного потока другим о каком-то событии. Например, когда один поток ожидает готовности данных, подготавливаемыми для него другими потоками. Здесь только локами не обойтись. И зависание потока на условной переменной, которую никто никогда не дергнет, я также склонен называть дедлоком.
>>частности, с семафорами дедлоки не обнаруживаются (просто потому, что залочить его может >>один поток, а разлочить другой, может быть даже тот, который еще и не запущен)
MSS>За 7 с лишним лет системного программирования ни разу не возникала нужда в семафоре почему-то
Здравствуйте, Andrei N.Sobchuck, Вы писали:
ANS>Возможно. Одно дело промышленный язык, другое дело исследовательский. Его проще менять, плюс компилятор/ВМ можно писать на том, что знаеш, а не на том, что выбрали авторы исходной системы.
Если речь идет только об исследовательском проекте -- тогда понятно.
E>>Более того, асинхронное взаимодействие можно и в существующие языки добавлять (которые изначально таких возможностей не содержали).
ANS>Как я помню, основная фича там не асинхронность, а capability-based security.
Об этом уже времени не было читать
Да и тема топика предполагала обсуждение только дедлоков
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
D>Понятно. На мой взгляд под синхронизацией потоков следует понимать не только защиту данных от одновременного доступа к ним, но и оповещение одного потока другим о каком-то событии.
Да. Согласен.
>Например, когда один поток ожидает готовности данных, подготавливаемыми для него другими потоками. Здесь только локами не обойтись. И зависание потока на условной переменной, которую никто никогда не дергнет, я также склонен называть дедлоком.
Конечно. Очень часто такое бывает от неправильного сочетания ожидания и мутекса. Ожидание под мутексом, например.
Инструментировать код, чтобы этого не было, невозможно (blocking может быть очень много кто, read(), например), но выработать правила, предотвращающие это — можно.
D>Ok. Как насчет condvar или event?
Event, конечно. Condvar лично мне кажется противоестественным. Грубо говоря, светофор или красный, или зеленый. А светофор, который может мигнуть зеленым так, что только ныне стоящие машины это увидят и тронутся (а те, кто приехал позже на долю секунды, уже остановятся) — какое-то извращение.
Нелогичный это объект. На коленке сляпанный и хреновый. Единственный с него толк — экономия kernel memory. Все. Неактуально сейчас.
И нет никакого функционала, никакого поведенческого паттерна, который можно было бы реализовать на condvarах и нельзя на эвентах.
Кстати, в ядре линукса я кондваров не видел, а вот эвенты вполне даже есть — wait queues.
E>Кстати, не понятно, зачем им потребовалось новый язык создавать (для Ph.D что ли?), при существовании-то Erlang-а? Более того, асинхронное
Один нюанс. Для создания языка, который гарантирует отсутствие дедлоков на уровне синтаксиса, придется завести ключевое (или атрибут) слово blocking, разрешить помечать им функции и пометить целую кучу функций стандартной библиотеки — типа recv(), например — этим словом.
Иначе это все игрушки. Запросто можно дедлокнуться в recv(), если позвать его из-под мутекса.
Здравствуйте, Maxim S. Shatskih, Вы писали:
D>>Ok. Как насчет condvar или event?
MSS>Event, конечно. Condvar лично мне кажется противоестественным. Грубо говоря, светофор или красный, или зеленый. А светофор, который может мигнуть зеленым так, что только ныне стоящие машины это увидят и тронутся (а те, кто приехал позже на долю секунды, уже остановятся) — какое-то извращение.
MSS>Нелогичный это объект. На коленке сляпанный и хреновый.
Полагаю, что ты просто не нашел ему адекватной аналогии.
Представь стадион и бегунов, которые должны пробежать вокруг него ровно один круг. Изначально бегуны стоят на старте и ждут выстрела стартового пистолета. После выстрела (pthread_condvar_broadcast, PulseEvent, java.lang.Object.notifyAll) бегуны (потоки) пробегают круг и останавливаются на стартовой позиции. Если же стартовый пистолет заменить семафором и в момент старта включить зеленый свет на некоторое время и потом вернуть красный, то существует риск того, что одни бегуны успеют пробежать несколько кругов (до того как семафор станет красным), в то время как другие не успеют тронуться с места.
D>Представь стадион и бегунов, которые должны пробежать вокруг него ровно один круг.
Часто такой паттерн бывает? я имею в виду "ровно один круг"?
>кругов (до того как семафор станет красным), в то время как другие не успеют тронуться с >места.
Чаще встречается иной паттерн. Не бегуна, а курьера. Курьер получает свой груз — и мчится доставлять. Потом возвращается, получает следующий груз и вперед.
Это один из двух главнейших паттернов в многонитевом программировании. Второй — "туалетная кабинка", ну или рамка досмотра в аэропорту. Туда нельзя входить вдвоем. Следущий должен дождаться, когда предыдущий окончит свои дела. Это мутекс.
Дальше. Грузы хранятся в ожидании курьеров у стартовой линии. Когда грузы есть — горит зеленый, бери груз и беги. Когда нет — горит красный. Стой, ожидая груза.
Ну и как тут поможет стартовый пистолет? а если груз пришел, а курьеров на стартовой линии — нуль? из пистолета палить? а тогда курьер придет, а выстрел уже отгремел, и курьер замер навсегда. Еще раз из пистолета палить? а кто это будет делать, и как?
Здравствуйте, Maxim S. Shatskih, Вы писали:
D>>Представь стадион и бегунов, которые должны пробежать вокруг него ровно один круг.
MSS>Часто такой паттерн бывает? я имею в виду "ровно один круг"?
Ну, бывает раз есть. Такая вещь как monitor (mutex + condvar) встроена в платформы .NET и Java.
MSS>Чаще встречается иной паттерн. Не бегуна, а курьера. Курьер получает свой груз — и мчится доставлять. Потом возвращается, получает следующий груз и вперед.
MSS>Это один из двух главнейших паттернов в многонитевом программировании. Второй — "туалетная кабинка", ну или рамка досмотра в аэропорту. Туда нельзя входить вдвоем. Следущий должен дождаться, когда предыдущий окончит свои дела. Это мутекс.
MSS>Дальше. Грузы хранятся в ожидании курьеров у стартовой линии. Когда грузы есть — горит зеленый, бери груз и беги. Когда нет — горит красный. Стой, ожидая груза.
MSS>Ну и как тут поможет стартовый пистолет? а если груз пришел, а курьеров на стартовой линии — нуль? из пистолета палить? а тогда курьер придет, а выстрел уже отгремел, и курьер замер навсегда. Еще раз из пистолета палить? а кто это будет делать, и как?
Ну во-первых, по-моему, это совершенно естественно, что одни задачи хорошо решаются одними средствами, а другие -- другими. Поэтому, если что-то не решается или решается плохо одним средством (condvar'ом, например) или такие задачи встречаются редко -- это не повод он него отказываться. Ведь могут быть задачи, которые именно этим средством будут решаться лучше, чем любыми другими.
Во-вторых, что касается приведенной задачи про курьера, то по-моему, она прекрасно решается condvar'ом.
Курьер возвращается за грузом, он входит в критическую секцию и проверяет есть ли груз, который необходимо отнести. Если есть, то он его берет, выходит из критической секции и относит куда нужно. Если же груза нет, то он засыпает (освобождая на время сна критическую секцию, которую он занял). Когда выходит грузчик и выносит груз для курьера, он заходит в критическую секцию, ставит груз и будит одного (или всех) спящих курьеров (пистолетом или еще как), выходит из критической секции и идет за другим грузом. Если спящих курьеров нет, то он просто выходит. Проснувшиеся курьеры обратно занимают критическую секцию, проверяют наличие груза, берут его и уносят (освободив напоследок критическую секцию).
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Перед захватом мутекса смотрится, кто именно им владеет, и обходится дерево по этим указателям. Если в дереве обнаруживается цикл (т.е. если оно на самом деле не дерево) — то возникает exception, который возвращается callerу — или как код ошибки, или через try/catch — механизмы реализации exceptions тут не важны.
Глупые мутексы в дедлоке приводят к зависанию, а умные — к отказу от обслуживания. Это, конечно, лучше, но ненамного.
Представь себе: один поток такой
lock(mutex1);
...
while(!ok)
{
try
{
...
lock(mutex2); ... unlock(mutex2); // где-то в недрах есть охраняемый код
...
// мы во что бы то ни стало хотим пройти контрольный пункт
ok = true;
}
catch(...) {}
}
...
unlock(mutex1);
а второй — примерно симметричный ему. И они будут долбиться в DoS пока не надоест.
С глупыми мутексами тот же эффект можно получить, указывая таймауты.
). Сам ещё не очень хорошо разобрался с тонкостями предлагаемого конвейерного механизма, но в драфте учебника по языку утверждается, что он предотвращает возможность дэдлоков.
)
В итоге имеем рекомендации для процесса Win32, а в рекомендациях для драйвера не имеем ничего, поэтому делаем, как правильно — и получаем дедлоки. Выясняем путем исследований, материмся, переделываем 
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Перекуём баги на фичи!
