Вопросы на собеседовании про многопоточность - О работе

Здравствуйте, shrecher, Вы писали:

S>Простой вопрос: поддержка целостности объекта через счетчик ссылок как в COM-t. Написать методы AddRef, Release.

Обычно приводят что-то такое:

void CReferenceCounter::AddRef( void ) {
  ::IntrlockedIncrement( &m_nReferences );
}

void CReferenceCounter::Release( void ) {
  if( !::IntrlockedDecrement( &m_nReferences ) ) {
  delete this;
  }
}

Либо синхронизируют через критическую секцию. А мне вот интересно, тут безопасно разве удалять объект? Если бы синхронизировали критической секцией, она бы была мембером класса, как удалить объект? Выйти из нее — а может в это время другой поток addRef сделает, а потом текущий, думая что счетчик 0, уничтожит. Не выходить из нее тоже нельзя.
Да и тут примерно такая ситуация вроде может быть — зашли в аddRef, в это время другой поток декрементировал и стер объект, и тут мы дошли в первом поток до вызова IntrlockedIncrement(). Может так быть?

Здравствуйте, ArtK, Вы писали:

AK>1. Проблема обедающих философов.
AK>2. Проблема читателей и писателей.
AK>3. Проблема спящего брадобрея.

А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

Здравствуйте, Ulitka, Вы писали:

U>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

Это реализуется железом — контролером доступа к памяти, программист с этим не соприкасается.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, Ulitka, Вы писали:

U>>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

S>Это реализуется железом — контролером доступа к памяти, программист с этим не соприкасается.

Ох еще как соприкасается, только, к сожалению, очень мало об этом знает.

Здравствуйте, Ulitka, Вы писали:

U>Ох еще как соприкасается, только, к сожалению, очень мало об этом знает.

Например? А то может мы о разном говорим.

Здравствуйте, Aleksey_NN, Вы писали:

Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Либо синхронизируют через критическую секцию. А мне вот интересно, тут безопасно разве удалять объект? Если бы

мне тоже интересно, как можно додуматься удалять объект в его методе

Здравствуйте, BulatZiganshin, Вы писали:

A_N>>Либо синхронизируют через критическую секцию. А мне вот интересно, тут безопасно разве удалять объект? Если бы

BZ>мне тоже интересно, как можно додуматься удалять объект в его методе

А где еще удалять COM-объект?

Здравствуйте, Ulitka, Вы писали:

U>Здравствуйте, sysenter, Вы писали:

S>>Здравствуйте, Ulitka, Вы писали:

U>>>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

S>>Это реализуется железом — контролером доступа к памяти, программист с этим не соприкасается.

U>Ох еще как соприкасается, только, к сожалению, очень мало об этом знает.

Поясните пожалуйста, если на потоке ставить мьютекс, то как с другого CPU читаются "грязные" данные ?

Здравствуйте, Lloyd, Вы писали:

BZ>>мне тоже интересно, как можно додуматься удалять объект в его методе

L>А где еще удалять COM-объект?

в глобальной процедуре или в его владельце

Здравствуйте, BulatZiganshin, Вы писали:

L>>А где еще удалять COM-объект?

BZ>в глобальной процедуре или в его владельце

Я COM как бы не зря выделил.

Здравствуйте, andy., Вы писали:

A>Поясните пожалуйста, если на потоке ставить мьютекс, то как с другого CPU читаются "грязные" данные ?

Тут понимаете про потоки не сказано ни слова, только про процессоры. На разных процессорах могут исполняться разные потоки равно, как разные потоки могут исполняться на одном и том же процессоре. Акцент был сделать именно на процессорах, а аппаратные кеши процессоров синхронизируются аппаратно, можно только принудительно делать flush или отключать использование кэша с помощью флага CD у регистра cr0, можно с помощью флага NM у cr0 включая сквозную запись в память. Что автор имел ввиду непонятно, никакого контроля над тем, как CPU договариваются между собой нет.

Здравствуйте, sysenter, Вы писали:

S>Это реализуется железом — контролером доступа к памяти, программист с этим не соприкасается.

Реализуется-то железом. А тормозит-то потом софт.

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Всем привет.

A_N>Предстоит важное собеседование, там сказали любят спрашивать различные вопросы про многопоточность под Win и давать разные задачки на эту тему.
A_N>А ктонить может подбросить задач и вопросов с собеседований про это все? Есть какие-либо "стандартные" задачи на это дело (ну как про круглые люки)?
A_N>Для примера: на первом собеседовании меня пока попросили написать синхронизированную очередь.

Join-calculus, pi-calculus, CSP, STM, non-blocking IO без каллбеков и прочей содомии, nested data parallelism, модель акторов, temporal logic of actions и пр. Если начнут с умным видом прашивать про мьютексы/сигналы/эвенты — вставай и уходи.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, andy., Вы писали:

A>>Поясните пожалуйста, если на потоке ставить мьютекс, то как с другого CPU читаются "грязные" данные ?

S> Что автор имел ввиду непонятно, никакого контроля над тем, как CPU договариваются между собой нет.

вероятно, имелась ввиду ситуация, когда ЦП1 пишет в память, находящейся в кэше ЦП2. контроль на самом деле есть. не хочешь, чтобы возникала такая ситуация -- не вызывай ее.

рассмотрим список в котором добавление/удаление элементов осуществляется редко, а вот изменение элементов -- часто и с разных ЦП. очевидно, что вынос ссылок в отдельную область памяти существенно ускорит работу со списком.

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Предстоит важное собеседование, там сказали любят спрашивать различные вопросы про многопоточность под Win и давать разные задачки на эту тему.

Да вроде Рихтера перечитать, освежить и достаточно.

A_N>А ктонить может подбросить задач и вопросов с собеседований про это все? Есть какие-либо "стандартные" задачи на это дело (ну как про круглые люки)?
A_N>Для примера: на первом собеседовании меня пока попросили написать синхронизированную очередь.

Меня просили как-то написать ридер-райтер лок при условии, что в наличии есть только такой объект синхронизации, который можно или захватить или освободить. Узнать, захвачен ли объект, нельзя. Вроде правильно вспомни.

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Здравствуйте, shrecher, Вы писали:

S>>Простой вопрос: поддержка целостности объекта через счетчик ссылок как в COM-t. Написать методы AddRef, Release.

A_N>Обычно приводят что-то такое:

Верно.
Здесь можно продолжить: Почему написано "!::IntrlockedDecrement( &m_nReferences )", а не

void CReferenceCounter::Release( void ) 
  {

  !::IntrlockedDecrement( &m_nReferences ) 
  if( !m_nReferences )
  {
     delete this;
  }
}

В чем отличие и проблемы?

S>В чем отличие и проблемы?

Главная проблема — в том, что не скомилируется

(забыта ";", та, что должна дать sequence point и кучу проблем с этим).

Но строго говоря, Bulat прав — удалять объект сам себя из собственного же метода (даже если это Release) по-хорошему не должен. Можно придумать примеры, где это будет стрелять (но они, все ж, будут слегка экзотичны).

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Здравствуйте, shrecher, Вы писали:

S>>Простой вопрос: поддержка целостности объекта через счетчик ссылок как в COM-t. Написать методы AddRef, Release.

A_N>Обычно приводят что-то такое:

A_N>

A_N>void CReferenceCounter::AddRef( void ) {
A_N>  ::IntrlockedIncrement( &m_nReferences );
A_N>}

A_N>void CReferenceCounter::Release( void ) {
A_N>  if( !::IntrlockedDecrement( &m_nReferences ) ) {
A_N>  delete this;
A_N>  }
A_N>}
A_N>

A_N>Либо синхронизируют через критическую секцию. А мне вот интересно, тут безопасно разве удалять объект? Если бы синхронизировали критической секцией, она бы была мембером класса, как удалить объект? Выйти из нее — а может в это время другой поток addRef сделает, а потом текущий, думая что счетчик 0, уничтожит. Не выходить из нее тоже нельзя.
A_N>Да и тут примерно такая ситуация вроде может быть — зашли в аddRef, в это время другой поток декрементировал и стер объект, и тут мы дошли в первом поток до вызова IntrlockedIncrement(). Может так быть?

Здесь все просто, всего лишь нужно задуматься "а кто может делать AddRef" ?

Ответ : тот кто имеет "валидный" интерфейс/хэндл, то есть пока этот хэндл валидный,
объект не будет удален даже вызовом Release() из другого потока.
Т.е. объект будет удален при вызове Release() у последнего "валидного" хэндла.

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

ПМ>Join-calculus, pi-calculus, CSP, STM, non-blocking IO без каллбеков и прочей содомии, nested data parallelism, модель акторов, temporal logic of actions и пр. Если начнут с умным видом прашивать про мьютексы/сигналы/эвенты — вставай и уходи.

Заинтриговали. Теперь, если нетрудно, разъясните, что вы тут написали. Я, кроме как про non-blocking IO, других терминов особо не встречал в обычной работе, за исключением разработки кодогенераторов (в т.ч. JIT, там действительно нужны некоторые добавочные знания, которые, я так понимаю, вы обозвали умными терминами nested data parallelism и temporal logic of actions — притом для конкретных железок).

В большинстве случаев, когда я вижу такие "заумные" термины, я прошу объяснить, в чем их суть. Если автор это в состоянии сделать, и получается простое и понятное определение — значит, автор понимает, о чем говорит, но, что называется, "понтуется" принадлежностью к какой-то "элитной" группировке программистов (что не во всех коллективах любят).
Если, соответственно, не в состоянии — значит, автор вообще что-то где-то краем уха слышал, но по факту не разбирается.

В любом случае, применение необщеупотребимых терминов сродни тяжелому codestyle. Вроде бы и "умно" смотрится, но читать тяжело, и что автор хотел сказать, не всегда с первого раза понятно.

Здравствуйте, SkyDance, Вы писали:

S>>В чем отличие и проблемы?

SD>Главная проблема — в том, что не скомилируется

Ой!

SD>Но строго говоря, Bulat прав — удалять объект сам себя из собственного же метода (даже если это Release) по-хорошему не должен. Можно придумать примеры, где это будет стрелять (но они, все ж, будут слегка экзотичны).

Дело не в этом если Release вызван параллельно из 2х или более потоков, то первый поток сделает уменьшение "m_nReferences", а другие будут видеть 0 в m_nReferences и сделают double delete. В случае "if IntrlockedDecrement(&m_nReferences ) == 0 )" такая проблема не возникает, т.к. используется локальный результат вычисления, а не общий член m_nReferences

По поводу "удалять объект сам себя из собственного же метода" это спорно, т.к. техника refcount используется очень часто (как сопутствующий вопрос с интервью "где используется?") и если аккуратно написано, то очень хорошо работает

Здравствуйте, andy., Вы писали:

A>Здравствуйте, IID, Вы писали:

IID>>Здравствуйте, Aleksey_NN, Вы писали:

IID>>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

A>У вас в проекте много "ручных" семафоров, если не секрет конечно ?

Ну вот, начинается. Рассуждения в ключе "если не используется то я знать не обязан". Ручных семафоров, разумеется, нет. Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

Здравствуйте, SkyDance, Вы писали:

SD> Можно придумать примеры, где это будет стрелять (но они, все ж, будут слегка экзотичны).
Придумайте, стало интересно.

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

S>Дело не в этом если Release вызван параллельно из 2х или более потоков, то первый поток сделает уменьшение "m_nReferences", а другие будут видеть 0 в m_nReferences и сделают double delete. В случае "if IntrlockedDecrement(&m_nReferences ) == 0 )" такая проблема не возникает, т.к. используется локальный результат вычисления, а не общий член m_nReferences

оооот тут широкое поле для беседы. Например, можно потеоретизировать на тему volatile и ума современных компиляторов (кодогенераторов). В частности, один мне известный генератор (чисто для унутренного применения, вряд ли вы о нем слышали) для volatile-переменных сам генерирует префик lock для x86 (или соответствующую инструкцию для высших процессоров), эффективным образом повторяя interlocked-операции. Учитывая, что оптимизатор в общем случае свернет всю конструкцию, в ассемблере получим что-нибудь вида

lock sub ax, 1   ; или вариант для высших x86
jnz function_exit
call delete_this ; тут, конечно, будет не так, но это для иллюстрации
function_exit:

S>По поводу "удалять объект сам себя из собственного же метода" это спорно, т.к. техника refcount используется очень часто (как сопутствующий вопрос с интервью "где используется?") и если аккуратно написано, то очень хорошо работает

Так-то оно так, но я могу привести экзотические случаи, когда это будет работать плохо. Но это реально придирки.

Здравствуйте, Aleksey_NN, Вы писали:

A_N>Предстоит важное собеседование, там сказали любят спрашивать различные вопросы про многопоточность под Win и давать разные задачки на эту тему.
A_N>А ктонить может подбросить задач и вопросов с собеседований про это все? Есть какие-либо "стандартные" задачи на это дело (ну как про круглые люки)?

http://rsdn.ru/forum/java/3622844.aspx — с уклоном в Java, но есть и общие для всех ЯП вопросы

С такой логикой Вас тоже нельзя ни к чему допускать, кроме того , что вы знаете на данный момент.
Все когда-то в первый раз.
За месяц вполне можно все эти "трюки" с многопоточностью усвоить. Надо просто на первых порах следить за кодом новичка.

Здравствуйте, SkyDance, Вы писали:

SD>lock sub ax, 1 ; или вариант для высших x86

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, HolyNick, Вы писали:

HN>С такой логикой Вас тоже нельзя ни к чему допускать, кроме того , что вы знаете на данный момент.
HN>Все когда-то в первый раз.
HN>За месяц вполне можно все эти "трюки" с многопоточностью усвоить. Надо просто на первых порах следить за кодом новичка.

А с такой логикой надо брать вообще всех подряд

>А с такой логикой надо брать вообще всех подряд

Практика показывает, что некоторых обучить нельзя\очень сложно.

>В нашем случае необходимо было знание многопоточности сразу, без обучения. Это во-первых. А во-вторых, если кандидат декларирует знание многопоточности и валится на такой задачке — о чём вообще может идти речь ?

Согласен, если есть конкретные требования, тут уж ничего не поделаешь.
Просто обидно, когда чувствуешь, что "могешь" скорее всего, а опыта поднабраться негде.

Здравствуйте, HolyNick, Вы писали:

>>А с такой логикой надо брать вообще всех подряд

HN>Практика показывает, что некоторых обучить нельзя\очень сложно.

Ага, именно так. Но ты всё равно предлагаешь этим заниматься.

>>В нашем случае необходимо было знание многопоточности сразу, без обучения. Это во-первых. А во-вторых, если кандидат декларирует знание многопоточности и валится на такой задачке — о чём вообще может идти речь ?

HN>Согласен, если есть конкретные требования, тут уж ничего не поделаешь.
HN>Просто обидно, когда чувствуешь, что "могешь" скорее всего, а опыта поднабраться негде.

Более того, "скорее всего" означает кучу говнокода, который на первый взгляд корректен, а на самом деле содержит кучу багов. А в многопоточном окружении ловить race condtition-ы то ещё "удовольствие". Опыта поднабраться всегда есть где =) Самостоятельные проекты, изучение текущего продукта, написанного более опытными товарищами, изучение стороннего открытого кода. Только для этого надо тратить время и силы, а особо ленивые уповают что их возьмут и так, а там авось как-нибудь научатся, да что-нибудь напишут, а другие пусть исправляют.

В ключе моего примера с семафором достаточно иметь базовые знания о примитивах синхронизации, да нормальную логику. Ну и аккуратность. Чтобы учесть все варианты поведения кода. Никаких супер-скиллов не нужно. Если кандидат не в состоянии решить такую задачу то и учить его бесполезно. Пусть базу подтягивает.

Много ты самостоятельных проектов ведешь?

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Здравствуйте, Aleksey_NN, Вы писали:

A_N>>Всем привет.

A_N>>Предстоит важное собеседование, там сказали любят спрашивать различные вопросы про многопоточность под Win и давать разные задачки на эту тему.
A_N>>А ктонить может подбросить задач и вопросов с собеседований про это все? Есть какие-либо "стандартные" задачи на это дело (ну как про круглые люки)?
A_N>>Для примера: на первом собеседовании меня пока попросили написать синхронизированную очередь.

ПМ>Join-calculus, pi-calculus, CSP, STM, non-blocking IO без каллбеков и прочей содомии, nested data parallelism, модель акторов, temporal logic of actions и пр. Если начнут с умным видом прашивать про мьютексы/сигналы/эвенты — вставай и уходи.

А что, кстати, плохого в вопросах про мьютексы/сигналы/ивенты. Разве эти примитивы не надо знать в первую очередь ?

Здравствуйте, andy., Вы писали:

A>А что, кстати, плохого в вопросах про мьютексы/сигналы/ивенты. Разве эти примитивы не надо знать в первую очередь ?

Обычно при разработке на плюсах используют boost, как давно boost знаком с виндовыми Event?

Здравствуйте, HolyNick, Вы писали:

HN>Много ты самостоятельных проектов ведешь?

Не пойму какое это имеет отношение к обсуждению.

Самостоятельных — в свободное время ? Сейчас один. Кернел-мод. Раньше несколько юзерлендных было, писал чисто для фана. Даже профит кое-какой приносили.

Имеет, т.к заниматься чем-то более менее серьезным в нерабочее время проблематично(время немного, да 24 часа за компом сидеть маразм). Книги почитать, что-то мелкое написать — да, еще можно.

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

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, andy., Вы писали:

A>>А что, кстати, плохого в вопросах про мьютексы/сигналы/ивенты. Разве эти примитивы не надо знать в первую очередь ?

S>Обычно при разработке на плюсах используют boost, как давно boost знаком с виндовыми Event?

http://www.boost.org/doc/libs/1_46_1/doc/html/thread/synchronization.html#thread.synchronization.condvar_ref

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, andy., Вы писали:

A>>Здравствуйте, IID, Вы писали:

IID>>>Здравствуйте, Aleksey_NN, Вы писали:

IID>>>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

A>>У вас в проекте много "ручных" семафоров, если не секрет конечно ?

IID>Ну вот, начинается. Рассуждения в ключе "если не используется то я знать не обязан". Ручных семафоров, разумеется, нет. Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

А если кандидат пишет под линукс и не знает что в далёком виндовс есть семафоры? Сразу в утиль?

Здравствуйте, XuMuK, Вы писали:

XMK>http://www.boost.org/doc/libs/1_46_1/doc/html/thread/synchronization.html#thread.synchronization.condvar_ref

Conditional var не равнозначно event, не хранит состояние — ручной/авто сброс. В целом это платформозависимые мелочи, готов согласиться с предложенным вариантом.

Здравствуйте, XuMuK, Вы писали:

XMK>А если кандидат пишет под линукс и не знает что в далёком виндовс есть семафоры? Сразу в утиль?

В Linux Posix и IPC семофоры есть же

Здравствуйте, HolyNick, Вы писали:

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

Думаешь это кого-нибудь интересует ? Есть кандидат А, который не поленился изучить технологию Х. И есть кандидат Б, которому всё некогда и лениво. Работодателю плевать на причины, по которому Б не знает Х. Пусть Б ноет дальше. Или идёт учить Х в институт (смешно, ага).

Здравствуйте, XuMuK, Вы писали:

XMK>А если кандидат пишет под линукс и не знает что в далёком виндовс есть семафоры? Сразу в утиль?

А причём тут вообще ОС ? Семафоры базовая концепция примитивов синхронизации. В линуксе есть в том числе (Posix semaphores). Таки да, в твоей постановке: не знает что такое семафоры — сразу в утиль

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, XuMuK, Вы писали:

XMK>>А если кандидат пишет под линукс и не знает что в далёком виндовс есть семафоры? Сразу в утиль?

IID>А причём тут вообще ОС ? Семафоры базовая концепция примитивов синхронизации. В линуксе есть в том числе (Posix semaphores). Таки да, в твоей постановке: не знает что такое семафоры — сразу в утиль

О, и правда =) Я как-то за все годы пользовался либо pthread'ом либо бустом, а о семафорах читал года 4 назад, во время подготовки к очередному собеседованию (где они не понадобились), и кроме того что это базовый примитив синхронизации ничего не вспомнил, вот и удивился. А винда к тому, что там семафорами наверное приходится пользоваться, в отличии от. Ну значит меня в утиль, договорились =)

Здравствуйте, IID, Вы писали:

IID>А с такой логикой надо брать вообще всех подряд

Ведь всё можно усвоить и всему обучить. Нафиг-нафиг. В нашем случае необходимо было знание многопоточности сразу, без обучения. Это во-первых. А во-вторых, если кандидат декларирует знание многопоточности и валится на такой задачке — о чём вообще может идти речь ?

Мой личный опыт показывает, что лучше взять полного лопуха в многопоточности, чем специалиста по lock-free очередям, наколенным семафорам и прочими обедающими философами. От последних вреда на два десятичных порядка больше.

Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, IID, Вы писали:

IID>>А с такой логикой надо брать вообще всех подряд

Ведь всё можно усвоить и всему обучить. Нафиг-нафиг. В нашем случае необходимо было знание многопоточности сразу, без обучения. Это во-первых. А во-вторых, если кандидат декларирует знание многопоточности и валится на такой задачке — о чём вообще может идти речь ?

L>Мой личный опыт показывает, что лучше взять полного лопуха в многопоточности, чем специалиста по lock-free очередям, наколенным семафорам и прочими обедающими философами.

А у тебя кроме чёрного и белого ещё цвета есть ?

Здравствуйте, XuMuK, Вы писали:

XMK>А винда к тому, что там семафорами наверное приходится пользоваться, в отличии от.

Опять винда, эка тебе она покоя не даёт.

Повторяю, я вообще ОС не упоминал.

XMK>Я как-то за все годы пользовался либо pthread'ом либо бустом, а о семафорах читал года 4 назад, во время подготовки к очередному собеседованию (где они не понадобились)

Ну если чего-то не знаешь, то и использовать это не будешь. Логично ?

А если серъёзно — не знать что такое семафор это ещё не фатально (хотя и тревожный сигнал). Но вот если тебе объясняют как он работает, а ты не можешь его реализовать — то всё плохо.

Здравствуйте, XuMuK, Вы писали:

XMK>Здравствуйте, IID, Вы писали:

IID>>Здравствуйте, XuMuK, Вы писали:

XMK>>>А если кандидат пишет под линукс и не знает что в далёком виндовс есть семафоры? Сразу в утиль?

IID>>А причём тут вообще ОС ? Семафоры базовая концепция примитивов синхронизации. В линуксе есть в том числе (Posix semaphores). Таки да, в твоей постановке: не знает что такое семафоры — сразу в утиль

XMK>О, и правда =) Я как-то за все годы пользовался либо pthread'ом либо бустом, а о семафорах читал года 4 назад, во время подготовки к очередному собеседованию (где они не понадобились), и кроме того что это базовый примитив синхронизации ничего не вспомнил, вот и удивился. А винда к тому, что там семафорами наверное приходится пользоваться, в отличии от. Ну значит меня в утиль, договорились =)

В винде внутри процесса можно CriticalSection использовать, а между процессами Messaging, разве нет ?

Здравствуйте, IID, Вы писали:

IID>Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

Интересно, что ж вы там такое напедалить умудрились, что теперь без знания ручного семафора людей на проект брать опасно.

... << RSDN@Home 1.2.0 alpha 4 rev. 1138>>

Здравствуйте, мыщъх, Вы писали:

М>вероятно, имелась ввиду ситуация, когда ЦП1 пишет в память, находящейся в кэше ЦП2. контроль на самом деле есть. не хочешь, чтобы возникала такая ситуация -- не вызывай ее.

М>рассмотрим список в котором добавление/удаление элементов осуществляется редко, а вот изменение элементов -- часто и с разных ЦП. очевидно, что вынос ссылок в отдельную область памяти существенно ускорит работу со списком.

Угу. Я бы был рад услышать про MESI, про store buffers, read/write memory barriers, prefetching etc. Много о чем поговорить можно. Но это так, мысли вслух

Здравствуйте, Ulitka, Вы писали:

U>Здравствуйте, мыщъх, Вы писали:

М>>вероятно, имелась ввиду ситуация, когда ЦП1 пишет в память, находящейся в кэше ЦП2. контроль на самом деле есть. не хочешь, чтобы возникала такая ситуация -- не вызывай ее.

М>>рассмотрим список в котором добавление/удаление элементов осуществляется редко, а вот изменение элементов -- часто и с разных ЦП. очевидно, что вынос ссылок в отдельную область памяти существенно ускорит работу со списком.

U>Угу. Я бы был рад услышать про MESI,
кстати, да. понимание протокола позволяет оптимизировать программы. во всяком случае не будет ситуации, когда два и более ЦП "молотят" одну область памяти и оба туда интенсивно читают/пишут. стоимость одного обращения к ячейке памяти резко возрастает и дешевле вырубить остальные ЦП на фиг, чем так параллелить задачу.

U> про store buffers,
это сильно системно-зависимо и в общем случае трудно сказать какая последовательность операций чтения/записи/чтения окажется оптимальной. иногда лишнее чтение перед записью ускоряет работу, иногда -- тормозит. абстрактно я бы не рискнул оптимизировать без конкретных тестов, хотя "холостое" чтение пред записью скорее не помешает, чем навредит.

U> prefetching etc. Много о чем поговорить можно.
U> Но это так, мысли вслух

ИМХО лучший способ избежать багов -- это отказаться от работы с разделяемыми данными. в большинстве случаев это вполне возможно. а если работа с разделяемыми данными необходима, то вводить поток-посредник. например, у нас есть список, который мы хотим модифицировать из разных потоков. если потоки модифицируют его напрямую -- нужна синхронизация. если же список модифицирует только один поток, а остальные потоки к нему обращатся с запросами, причем запросы ставятся в раздельные очереди (по одной на каждый поток), то в этом случае разделяемых данных нет. ну то есть они, конечно, есть, но исключительно в схеме поток_агент <==> поток_с_запросом, но тут синхронизация тривиальная.

Здравствуйте, Ulitka, Вы писали:

U>>>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

Прикладному программисту это по-барабану.

Здравствуйте, Коваленко Дмитрий, Вы писали:

КД>Здравствуйте, Ulitka, Вы писали:

U>>>>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

КД>Прикладному программисту это по-барабану.

Почитайте ответы уважаемого Мыщъх, он привел кучу примеров, почему прикладному программисту как раз не по барабану. Есть все шансы, что Ваша многопоточная программу будет лучше работать на single CPU будет работать лучше и быстрее. В общем, Вы не прошли собеседование многопоточному программированию.

Здравствуйте, мыщъх, Вы писали:

мыщъх, не могу не согласиться. Но как мало людей об этом знают... Хотя все горазды писать многопоточные приложения — кругом одни писатели.

Здравствуйте, Ulitka, Вы писали:

U>Здравствуйте, мыщъх, Вы писали:

U> мыщъх, не могу не согласиться. Но как мало людей об этом знают...
я тоже этим удручаюсь. и еще удручаюсь тем, что стремятся параллелить на самом низком уровне, хотя классический контрпример -- написать компилятор, поддерживающий N ЦП очень сложно (если вообще возможно), но легко заставить make пускать компилятор на разных ЦП. и... никаких проблем работы с разделяемыми данными, синхронизаций и т.д. и т.п.

U> Хотя все горазды писать многопоточные приложения — кругом одни писатели.
в том-то и дело. до сих пор не могу понять откуда такая любовь к сценариям -- один поток заталкивает элементы в объект, а другой их оттуда выпихивает. вроде бы ясно, что кто заталкивает, тот и выпихивать должен, а остальные всего лишь собщать ему, что данный элемент в очереди на выпих.

у меня вот программа на 10K+ строк многопоточная и многоцпшная. только она об этом не знает, т.к. в момент иницилизации экземпляра "движка" функция init возвращает handle, в котором есть указатель на память, в которой расположены все необходимые данные, настройки и промежуточные результаты. грубо говоря, каждый экземпляр ведет себя так, как будто он тут один, а если им нужно взаимодействовать -- на это есть API. и хотя API у меня тупое (там данные копируются из локального хранилища одного потока в локальное хранилище другого), это все же быстрее, чем средства синхронизации, размазанные по всей программе.

Здравствуйте, Ulitka, Вы писали:

U>Угу. Я бы был рад услышать про MESI, про store buffers, read/write memory barriers, prefetching etc. Много о чем поговорить можно. Но это так, мысли вслух

Главное — не увлекаться. А то опять появится релизация memcpy, которая падает при копировании во write-only memory

Здравствуйте, SkyDance, Вы писали:

SD>Заинтриговали. Теперь, если нетрудно, разъясните, что вы тут написали.

Всё гуглится по названиям.

Аббревиатуры:
CSP — Communicating Sequential Processes
STM — Software Transactional Memory

Теперь всё точно гуглится.

SD>В любом случае, применение необщеупотребимых терминов сродни тяжелому codestyle.

Терминология стандартная.

Здравствуйте, andy., Вы писали:

A>А что, кстати, плохого в вопросах про мьютексы/сигналы/ивенты. Разве эти примитивы не надо знать в первую очередь ?

Когда вы в последний раз реализовывали мьютекс/сигнал/эвент?

Тут товарищь писал, что большая часть собеседуемых не может нормально написать семафор, так оно и есть, и заниматься написанием семафоров вместо решения прикладных задач — это все равно что в жопу долбиться. Чтобы не долбиться в жопу, любой нормальный инженер разработает методы автоматизации рутинных задач, часть из которых я перечислил, а если он продолжает стойко преодолевать надуманные трудности — то он, скорее всего, не инженер, а педераст. Общения с педерастами следует избегать, они ведь и нормального человека зашкварить могут, поэтому как только речь заходит о реализации семафора (о которой, кстати, можно прочитать в википедии, поэтому само по себе это знание особой ценности не представляет) следует сразу уходить с собеседования, ибо нормальному пацану в петушиной хате западло работать.

U>мыщъх, не могу не согласиться. Но как мало людей об этом знают... Хотя все горазды писать многопоточные приложения — кругом одни писатели.

Имхо кругом одни "читатели," if you know what I mean.

IID>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

Абсолютно идиотская задача которая ничего не демонстрирует кроме как неадекватности ее спрашивающего.

A>>У вас в проекте много "ручных" семафоров, если не секрет конечно ?

IID>Ну вот, начинается. Рассуждения в ключе "если не используется то я знать не обязан". Ручных семафоров, разумеется, нет. Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

Реализовать семафор в кернел моде намного проще и понятнее этого изврата который ты хочешь увидеть в юзер моде при помощи других примитивов.

ЗЫ. Ты такой умный! Тебе череп мозг не жмет? (с)

IID>>Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

MP>Интересно, что ж вы там такое напедалить умудрились, что теперь без знания ручного семафора людей на проект брать опасно.

Сто процентов что что-нибудь да напедалили в этом стиле. Не семафор так что-то другое. Возможно даже все.

HN>>Согласен, если есть конкретные требования, тут уж ничего не поделаешь.
HN>>Просто обидно, когда чувствуешь, что "могешь" скорее всего, а опыта поднабраться негде.

IID>Более того, "скорее всего" означает кучу говнокода, который на первый взгляд корректен,

Этот твой user-space semaphore и есть самый что ни на есть гавнистый говнокод, как бы аккуратно его не написали. А ты даже и не понимаешь этого.

IID>а на самом деле содержит кучу багов. А в многопоточном окружении ловить race condtition-ы то ещё "удовольствие". Опыта поднабраться всегда есть где =) Самостоятельные проекты, изучение текущего продукта, написанного более опытными товарищами, изучение стороннего открытого кода. Только для этого надо тратить время и силы, а особо ленивые уповают что их возьмут и так, а там авось как-нибудь научатся, да что-нибудь напишут, а другие пусть исправляют.

Да ничего такого в этой многопоточности и синхронизации нет и зачастую она не нужна. Нужно просто понимать что такое потоки, как происходит их переключение, проблемы с ними связанные и примитивы синхронизации. Ну и иметь голову на плечах. А на интервью всего не спросить.

IID>В ключе моего примера с семафором достаточно иметь базовые знания о примитивах синхронизации, да нормальную логику. Ну и аккуратность. Чтобы учесть все варианты поведения кода. Никаких супер-скиллов не нужно. Если кандидат не в состоянии решить такую задачу то и учить его бесполезно. Пусть базу подтягивает.

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

SD>>lock sub ax, 1 ; или вариант для высших x86
CC>

Это была иллюстрация. Не надо понимать буквально. Если мы хотим углубиться в изучение конкретных реализаций — можно продолжить обсуждение lock CMPXCHG (один из возможных методов, AFAIK, в Windows сделано так), вспомнить про cli/sti (ЕМНИП, в Linux c поддержкой многопроцессорности прерывания локального процессора запрещаются при работе в режиме ядра), потрещать о еще одной реализации Solaris/Linux (где вообще нет decrement — есть только add, к счастью, signed, — в итоге тот же boost пользует очень даже платформо-зависимый __sync_fetch_and_add).
Но прямого отношения к теме всё это не имеет — а подавляющее большинство программистов вообще никогда не полезет в конкретную реализацию atomic_* функций. Даже если это ядерный программист. Поэтому начальной иллюстрации более чем достаточно.
Вот если бы начали барьеры обсуждать (к этому уже пришли, я смотрю, ближе к концу ветки), еще было бы понятен ваш сарказм.

M>Придумайте, стало интересно.

Есть набор очевидных проблем (перечислены здесь: http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.15). Самое важное — надо внимательно следить, чтобы объект ненароком не был на стеке или еще где-то в странном месте. Например, размещен placement new — очень частый случай для мелких COM-объектов, в больших количествах создаваемых какой-нибудь homebrew IClassFactory — какие-нибудь "обёрточные" объекты, которые быстрее из пула доставать, чем постоянно создавать/уничтожать.

Кстати, подумалось, что есть хороший вопрос на внимательность для собеседования:

class RefCountable
{
  Mutex m;
  int ref_counter;
  void Release()
  {
    m.lock();
    --ref_counter;
    if (ref_counter == 0) delete this;
    m.unlock();
  }

Требуется исправить код (сразу предупрежу, я не компилировал и не проверял синтаксическую правильность — это код для иллюстрации).

ПМ>Теперь всё точно гуглится.

Как я и ожидал, вы ничего не объяснили. Даже кратко. Даже парой слов. Из чего можно сделать вывод: либо вы "читали много умных книжек", либо у вас очень мало свободного времени (но этот вариант кажется менее вероятным — иначе зачем бы вы писали на форуме туманные сообщения).

Здравствуйте, SkyDance, Вы писали:
SD>Самое важное — надо внимательно следить, чтобы объект ненароком не был на стеке или еще где-то в странном месте.
Создавать СОМ обьекты на стеке

Вообщето их принято фабрикой создавать, и согласовать размещение обьекта с фабрикой не является проблемой.

Здравствуйте, Ulitka, Вы писали:

U>>>>>А я бы попросил объяснить как CPUs между собой договариваются, кто и какие данные модифицирует, и как гарантируется то, что другие CPU не прочитают "грязные" данные. Вполне себе интересная тема.

КД>>Прикладному программисту это по-барабану.

U>Почитайте ответы уважаемого Мыщъх, он привел кучу примеров, почему прикладному программисту как раз не по барабану. Есть все шансы, что Ваша многопоточная программу будет лучше работать на single CPU будет работать лучше и быстрее.

Я уже давно положил на примеры, меня интересуют законченные решения. Как они там внутри сделаны, меня начинает интересовать только если они начинают выносить мне моск

Впрочем да, встречал программистов, которые создавая код на VBScript рассуждают об ассемблере. Или, что ближе к теме топика, не в состоянии раскрутить причину AV в коде (сервера RDBMS) вида

assert(ptr!=NULL);
(*ptr)=0; //AV, потому что ptr таки оказался равным NULL

при этом размышляя — неужто это бага в процессоре AMD?

Всегда старался не опускаться до первого и не допускать второе в принципе. По этому лично мне — оно действительно по барабану. Понимания базовых принципов, которые не привязаны к железу, мне вполне хватает, чтобы полностью загрузить свой квад.

U>В общем, Вы не прошли собеседование многопоточному программированию.
В таких вещах самым лучшим будет демонстрация собственных произведений по теме. У меня такое есть. И самое краткое, что я мог бы сказать про него, что расстояние от CreateThread до промышленного решения (которое не страшно выпускать в дикую природу), управляющего потоками, в моем случае составило сотню килобайт исходного кода на C++. Прикладной код, где эти потоки потом работают — на порядок больше и сложнее. А то, где оно все целиком эксплуатируется — это вообще тихий ужос

Здравствуйте, BulatZiganshin, Вы писали:

A_N>>Либо синхронизируют через критическую секцию. А мне вот интересно, тут безопасно разве удалять объект? Если бы

BZ>мне тоже интересно, как можно додуматься удалять объект в его методе

Для этого нужно иметь реально мега крутое сознание

Помнится, в 97 году я чуть не рехнулся когда пытался до него самостоятельно додуматься. Ниасилил.

Чуть позже прочитал про него в книжке "Основы COM". К сожалению, моск к этому моменту уже был необратимо поврежден

На текущий момент, лично по мне, "delete this" — это одно из немногих обоснованных, явных использований оператора delete. В методе декремента счетчика ссылок на объект

---
Да, кстати, а объекты со счетчиками ссылок — это единственные кандидаты на роль совместно используемых ресурсов в многопоточной программе. Опять же — моё скромное мнение. Правда, нужно знать базовые правила управления такими объектами

Здравствуйте, Ulitka, Вы писали:

U>Ох еще как соприкасается, только, к сожалению, очень мало об этом знает.

Проблема не в знаниях, а в доступном времени. Разработчик для создаваемой фичи может осуществить только конечный набор мероприятий. Он должен подумать и тысячи разных вещах: проверок результатов API, синхронизация, unit test-ы, документация и еще много чего. Поэтому знания и действия должны быть четко приоритизированны. Если прикладной программист начнет еще размышлять над тем как там железо осуществляет доступ к ячейкам памяти или какой алгоритм заложен в ЦПУ, то он не успеет сделать что-то более важное, к примеру, написать хороший комментарий в код. Не надо требовать от разработчика не профильными знаниями, он о них может почитать в журналах для самообразования.

Я не думаю, что это кого-то интересует.

N_>Создавать СОМ обьекты на стеке

Вообщето их принято фабрикой создавать, и согласовать размещение обьекта с фабрикой не является проблемой.

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

Стек — это уже было в рамках обсуждения delete this; а не про конкретно СОМ-объекты.

Здравствуйте, мыщъх, Вы писали:

М>в том-то и дело. до сих пор не могу понять откуда такая любовь к сценариям -- один поток заталкивает элементы в объект, а другой их оттуда выпихивает. вроде бы ясно, что кто заталкивает, тот и выпихивать должен, а остальные всего лишь собщать ему, что данный элемент в очереди на выпих.

Интересно, а как преобразовать задачу Producer-consumer, чтобы избежать ситуации "один поток заталкивает элементы в объект, а другой их оттуда выпихивает"? (Естественно, помимо отказа от многопоточности вообще)

Здравствуйте, SkyDance, Вы писали:

M>>Придумайте, стало интересно.

SD>Есть набор очевидных проблем (перечислены здесь: http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.15). Самое важное — надо внимательно следить, чтобы объект ненароком не был на стеке или еще где-то в странном месте. Например, размещен placement new — очень частый случай для мелких COM-объектов, в больших количествах создаваемых какой-нибудь homebrew IClassFactory — какие-нибудь "обёрточные" объекты, которые быстрее из пула доставать, чем постоянно создавать/уничтожать.

Спасибо, это конечно не интересно. Я думал что то другое.

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, IID, Вы писали:

IID>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

Честно сказать, не понял чем эта задача хуже "8 гномиков встали раком" либо переверните однонаправленный список или любая другая задача ни о чем. Даже удивительно что народ столько возмущается, неужели написание такой простой херотени доставляет какие-то трудности?

Здравствуйте, SkyDance, Вы писали:

N_>>Создавать СОМ обьекты на стеке

Вообщето их принято фабрикой создавать, и согласовать размещение обьекта с фабрикой не является проблемой.

SD>При чем тут стек?
SD>Я же написал там про реализацию IClassFactory с применением пула готовых объектов (чтобы сэкономить на выделении памяти и инициализации).

SD>Стек — это уже было в рамках обсуждения delete this; а не про конкретно СОМ-объекты.
в СОМе фабрика и сам класс поставляются вместе, и создавать обьект как-то иначе, чем через его собственную фабрику нельзя. А обьекту со свой фабрикой договориться о том как правильно удаляться не является проблемой

Здравствуйте, Коваленко Дмитрий, Вы писали:

КД>Потоки работающие в рамках DLL. Засады, решения...

А можете перечислить? А то с этим я редко работал. Знаю только про однопоточность DllMain — что потоки, запущенные в ней, будут приостановлены до конца инициализации длл-ки, т.е. в дллмайн нет смысла ждать каких-то эвентов от рабочих потоков, повиснем

Здравствуйте, Aleksey_NN, Вы писали:

КД>>Потоки работающие в рамках DLL. Засады, решения...

A_N>А можете перечислить? А то с этим я редко работал. Знаю только про однопоточность DllMain — что потоки, запущенные в ней, будут приостановлены до конца инициализации длл-ки, т.е. в дллмайн нет смысла ждать каких-то эвентов от рабочих потоков, повиснем

Про DllMain — это понятно. В ней нельзя запускать/останавливать и прочие операции с потоками. Это в Рихтере описано.

Мне больше нравится другое — борьба с выгрузкой DLL, которая содержит активные потоки.

На текущий момент у меня работает схема — есть рабочие потоки и есть поток супервизора.

поток супервизора
— блокирует DLL в памяти (вызывает LoadLibrary)
— проверяет состояние всех рабочих потоков (они регистрируются в глобальном списке)

если рабочий поток стал неактивным, то поток супервизор удаляет его из списка

как только список опустошился, поток супервизора завершает работу через вызов FreeLibraryAndExitThread

это позволяет избежать всяких специальных экспортируемых функций DLL типа ShutdownServer, которые в случае COM-сервера в DLL бессмысленны.

Вообщем, здесь ключевой вещью является FreeLibraryAndExitThread. Кстати, тоже есть в Рихтере.

----
Поскольку DLL, это как правило — COM сервер, то я эксплуатирую еще одно правило: как только уничтожается последний COM-объект, я завершаю все рабочие потоки. Точнее уничтожаю пул потоков. Супервизор сам завершит свою работу. Я вообще не очень сильно исследовал этот момент, решил не рисковать и завершать всю активность внутрях своего модуля

----
Кстати говоря, я не уверен, но по-моему дело обстоит именно так — DLL-ные модули которые будут работать в произвольной многопоточной среде следует линковать только с MT-DLL стандартной библиотеки. Статика может спровоцировать всякие нехорошие проблемы.

Я вообще всегда юзаю только MT-DLL рантайма, независимо от типа проекта. Чисто на всякий случай

Здравствуйте, IID, Вы писали:

IID>А у тебя кроме чёрного и белого ещё цвета есть ?

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

Здравствуйте, IID, Вы писали:

IID>А у тебя кроме чёрного и белого ещё цвета есть ?

Здравствуйте, Madruel, Вы писали:

M>Здравствуйте, мыщъх, Вы писали:

М>>в том-то и дело. до сих пор не могу понять откуда такая любовь к сценариям -- один поток заталкивает элементы в объект, а другой их оттуда выпихивает. вроде бы ясно, что кто заталкивает, тот и выпихивать должен, а остальные всего лишь собщать ему, что данный элемент в очереди на выпих.

M>Интересно, а как преобразовать задачу Producer-consumer, чтобы избежать ситуации "один поток заталкивает элементы в объект, а другой их оттуда выпихивает"? (Естественно, помимо отказа от многопоточности вообще)

через API ес-но. писал же. есть поток-агент, работающий с данными, нужными остальным потокам. эти потоки обращаются к данным не напрямую, а через агента. потоки вызывают API агента в случайное время, и в это время происходит модификация очередей каждого потока на обращение к агенту. очереди находятся в локальной памяти потоков (не TLS, а просто буфер). поток-агент к ним обращается только при вызове его API, что обеспечивает прозрачную синхронизацию. главнй минус этой схеме -- памяти требуется больше. главный плюс -- системно-независимо, т.к. не используются объекты синхронизации, а потому работает и на ANSI C.

On 25.05.2011 0:38, BulatZiganshin wrote:
> мне тоже интересно, как можно додуматься удалять объект в его методе

Почему же нет-то ? Если больше не будет доступа к данным этого объекта
в этом методе, и ссылок на объект больше нет — можно удалять.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Здравствуйте, andy., Вы писали:

A>>А что, кстати, плохого в вопросах про мьютексы/сигналы/ивенты. Разве эти примитивы не надо знать в первую очередь ?

ПМ>Когда вы в последний раз реализовывали мьютекс/сигнал/эвент?

ПМ>Тут товарищь писал, что большая часть собеседуемых не может нормально написать семафор, так оно и есть, и заниматься написанием семафоров вместо решения прикладных задач — это все равно что в жопу долбиться. Чтобы не долбиться в жопу, любой нормальный инженер разработает методы автоматизации рутинных задач, часть из которых я перечислил, а если он продолжает стойко преодолевать надуманные трудности — то он, скорее всего, не инженер, а педераст. Общения с педерастами следует избегать, они ведь и нормального человека зашкварить могут, поэтому как только речь заходит о реализации семафора (о которой, кстати, можно прочитать в википедии, поэтому само по себе это знание особой ценности не представляет) следует сразу уходить с собеседования, ибо нормальному пацану в петушиной хате западло работать.

Смешно. А если тебе на собеседовании предложат написать процедурку умножения целых чисел, используя только сложение и сдвиг, ты их тоже педерастами обзовешь? Или ты и на собеседованиях только нетленку ваяешь?

Здравствуйте, Олег К., Вы писали:

HN>>>Согласен, если есть конкретные требования, тут уж ничего не поделаешь.
HN>>>Просто обидно, когда чувствуешь, что "могешь" скорее всего, а опыта поднабраться негде.

IID>>Более того, "скорее всего" означает кучу говнокода, который на первый взгляд корректен,

ОК>Этот твой user-space semaphore и есть самый что ни на есть гавнистый говнокод, как бы аккуратно его не написали. А ты даже и не понимаешь этого.

Это задача на собеседовании, а не production код. Ты хочешь мне доказать, что если человек не может сделать семафор, то он разбирается в многопоточности, или что ? Насчёт говнистости тоже вопрос открыт. Может твоя реализация и будет "говнистым говном" (с) твой, но можно написать так, что по накладным расходам будет не сильно отличаться от штатного.

IID>>а на самом деле содержит кучу багов. А в многопоточном окружении ловить race condtition-ы то ещё "удовольствие". Опыта поднабраться всегда есть где =) Самостоятельные проекты, изучение текущего продукта, написанного более опытными товарищами, изучение стороннего открытого кода. Только для этого надо тратить время и силы, а особо ленивые уповают что их возьмут и так, а там авось как-нибудь научатся, да что-нибудь напишут, а другие пусть исправляют.

ОК>Да ничего такого в этой многопоточности и синхронизации нет и зачастую она не нужна.
Ты не прав. Есть разные неочевидные на первый взгляд вещи. А про нужность вообще бред. Если тебе/твоей конторе не нужна — отучайся говорить за всех.

ОК>Нужно просто понимать что такое потоки, как происходит их переключение, проблемы с ними связанные и примитивы синхронизации. Ну и иметь голову на плечах.
Вау! Спасибо кэп. А теперь вопрос: если всё перечисленное имеется — какова сложность выполнения задачи на собеседовании ? Верно, никакой сложности. Задача тривиальная.

ОК>А на интервью всего не спросить.
Логично. Но это же не значит что теперь и спрашивать не надо.

IID>>В ключе моего примера с семафором достаточно иметь базовые знания о примитивах синхронизации, да нормальную логику. Ну и аккуратность. Чтобы учесть все варианты поведения кода. Никаких супер-скиллов не нужно. Если кандидат не в состоянии решить такую задачу то и учить его бесполезно. Пусть базу подтягивает.

ОК>Повторюсь опять. Тебе череп на мозг не давит?
Попаболь detected. Что же так тебя зацепило ?

ОК>Ты тут разглагольствуешь о какой-то базе однако уже в котором посту забыл упомянуть еще одно важное и надуманное условие задачи.
Это какое я условие забыл упомянуть ?

ОК>Также и на интервью, скорее всего.

О, попёрли фантазии.

Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, IID, Вы писали:

IID>>А у тебя кроме чёрного и белого ещё цвета есть ?

Если нужен человек, разбирающися в многопоточности — надо брать человека, разбирающегося в многопоточности. Это не значит что нужен мега-гуру, но и абсолютно не шаращяего тоже брать не нужно. Интересно, почему такой баттхёрт от примитивной задачки ?

L>Твой светофор — это не примитивная задача, а кусок бессмысленного говнокода.

Мой семафор это отличный индикатор. Проверено неоднократно. Чем лучше кандидат справлялся с ним, тем меньше потом багов с потокам было у него в коде. А половина тех кто сливали и на другие вопросы ответить толком не могли.

L>Чтобы разбираться в многопоточности, нужно:
L>1. Знать, зачем, когда и почему необходимо иметь много потоков.
L>2. Знать, какие грабли из этого отрастают как их избегать.

Если не можешь осилить семафор, то п2 сфейлен.

L>Все.
L>Ниасилившие эти две проблемы занмаются конструированием велосипедов.

Да причём тут велосипед. Ты читать умеешь ? Зто задача для собеседования. А не код в production. Я понимаю, что подменять понятия это излюбленный на RSDN приём, но не до такой же степени.

Здравствуйте, IID, Вы писали:

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

Может представите свою реализацию где накладные расходы будут не сильно отличаться от ядерного семафора?

Здравствуйте, andy., Вы писали:

A>В винде внутри процесса можно CriticalSection использовать, а между процессами Messaging, разве нет ?

Между процессами можно использовать любые объекты ядра, имеющие описатель в User land и поддерживающие синхронизацию: Synchronization Objects. Второй процесс получит их либо открыв по имени, либо в результате дупликации описателей процессом-владельцем.

Здравствуйте, Олег К., Вы писали:

IID>>>Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

MP>>Интересно, что ж вы там такое напедалить умудрились, что теперь без знания ручного семафора людей на проект брать опасно.

ОК>Сто процентов что что-нибудь да напедалили в этом стиле. Не семафор так что-то другое. Возможно даже все.

Вот и экстрасенсы подтянулись. Испытывающие баттхёрт от того, что считают задачку на написание самопального семафора за гранью знаний спеца по многопоточному программированию, которым сами, безусловно, являются

Здравствуйте, Олег К., Вы писали:

A>>>У вас в проекте много "ручных" семафоров, если не секрет конечно ?

IID>>Ну вот, начинается. Рассуждения в ключе "если не используется то я знать не обязан". Ручных семафоров, разумеется, нет. Но если человек не может написать сам семафор, делает логические ошибки, ошибки синхронизации, или даже не знает что такое семафор — то в многопоточном программировании он лопух полный, и его за километр нельзя подпускать к таким проектам.

ОК>Реализовать семафор в кернел моде намного проще и понятнее этого изврата который ты хочешь увидеть в юзер моде при помощи других примитивов.

Да что вы такое говорите! Много вы семафоров в кернелмоде реализовали ? Как предполагается делать семафор в кернелмоде без других объектов синхронизации ? Расскажите, очень интересно послушать. Особенно в ключе "намного проще и понятнее".

ОК>ЗЫ. Ты такой умный! Тебе череп мозг не жмет? (с)

Написать вручную семафор это уже признак великого ума ? Я бы по другому сказал: средний уровень знаний стремительно деградирует, раз такая примитивная задача вызывает столько ненависти от ущемлённых.

Здравствуйте, kaa.python, Вы писали:

KP>Здравствуйте, IID, Вы писали:

IID>>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

KP>Честно сказать, не понял чем эта задача хуже "8 гномиков встали раком" либо переверните однонаправленный список или любая другая задача ни о чем. Даже удивительно что народ столько возмущается, неужели написание такой простой херотени доставляет какие-то трудности?

Я сам в шоке (ц)

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

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

S>Может представите свою реализацию где накладные расходы будут не сильно отличаться от ядерного семафора?

Да легко. Но сначала хотел бы увидеть вот эту реализацию "в ядре" от мега-гуру Олег К. Дадим ему шанс блеснуть. А потом я свой скромный вариант выложу.

Здравствуйте, IID, Вы писали:

IID>Да что вы такое говорите! Много вы семафоров в кернелмоде реализовали ? Как предполагается делать семафор в кернелмоде без других объектов синхронизации ? Расскажите, очень интересно послушать. Особенно в ключе "намного проще и понятнее".

Расскажу, в ядре Linux семафоры реализованы через спинлоки и отключение прерываний, спинлок это просто цикл.
Сразу видно "специалиста" по ядерным примитивам синхронизации.

Здравствуйте, IID, Вы писали:

IID>Да легко. Но сначала хотел бы увидеть вот эту реализацию "в ядре" от мега-гуру Олег К. Дадим ему шанс блеснуть. А потом я свой скромный вариант выложу.

Тут я вам помогу, пример семафора из Linux
Ждем вашу реализацию для сравнения.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Да легко. Но сначала хотел бы увидеть вот эту реализацию "в ядре" от мега-гуру Олег К. Дадим ему шанс блеснуть. А потом я свой скромный вариант выложу.

S>Тут я вам помогу, пример семафора из Linux
S>Ждем вашу реализацию для сравнения.

Это совсем не то, что требовалось. Речь была о полноценном синхрообъекте, на ожидании которого тред уснёт, не отжирая ресурсы. Ты показывешь случай, когда приоритет исполнения выше чем у планировщика, и ничего не остаётся кроме как крутиться в цикле. Вместо нормального ожидания на синхрообъекте тут поджигание ядера процессора. Покажи-ка мне лучше ядерную реализацию вот этого: http://cristi.indefero.net/p/uClibc-cristi/source/tree/30cb4b5cd2e3e6da7603d34b5d0c4dd21ed26bff/libpthread/nptl/sysdeps/unix/sysv/linux/sem_wait.c

Кстати, отключать прерывания — что за убогость ? В NT спинлоки прекрасно крутятся не запрещая прерываний.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Да что вы такое говорите! Много вы семафоров в кернелмоде реализовали ? Как предполагается делать семафор в кернелмоде без других объектов синхронизации ? Расскажите, очень интересно послушать. Особенно в ключе "намного проще и понятнее".

S>Расскажу, в ядре Linux семафоры реализованы через спинлоки и отключение прерываний, спинлок это просто цикл.
Фигню ты несёшь. pthread-ные семафоры реализованы совершенно не так.

S>Сразу видно "специалиста" по ядерным примитивам синхронизации.
Ох уж мне эти экстрасенсы. Покажи-ка мне нормальную ядерную реализацию, взаимодествующую с планировщиком.

Здравствуйте, IID, Вы писали:

IID>либо в результате дупликации описателей процессом-владельцем.

Дополню для строгости. Можно и самостоятельно сдуплицировать описатели из процесса-владельца, если открыть его с соответствующими правами. Но тогда надо знать какой(-ие) именно описатель(-ели) дуплицировать. Например знать его числовое значение.

Здравствуйте, IID, Вы писали:

IID>Это совсем не то, что требовалось. Речь была о полноценном синхрообъекте, на ожидании которого тред уснёт, не отжирая ресурсы. Ты показывешь случай, когда приоритет исполнения выше чем у планировщика, и ничего не остаётся кроме как крутиться в цикле. Вместо нормального ожидания на синхрообъекте тут поджигание ядера процессора.

Это реализация семафора в кернел мод. На то, чтобы объект уснул требуется затратить существенное время, если делать так как предлагаете вы в случае попытки захвата семафора если он будет занят, но освободиться через миллисекунду потребуется затратить машинное время на сохранение регистров потока и другой необходимой информации, а потом пробудить поток и снова восстановить его контекст. Так же нет гарантии, что проснётся именно этот поток.
Всё это потребует гигантского машинного времени, на порядок большего чем со спинлоками. В винде, если мне не изменяет память, семафоры так же реализованы через спинлоки в том числе и только если виндовый семафор не освобождается в течении 400 циклов поток засыпает.

IID>Покажи-ка мне лучше ядерную реализацию вот этого: http://cristi.indefero.net/p/uClibc-cristi/source/tree/30cb4b5cd2e3e6da7603d34b5d0c4dd21ed26bff/libpthread/nptl/sysdeps/unix/sysv/linux/sem_wait.c

Это реализация Posix семафора в юзер мод через фьютекс в кернел мод.
В винде нету фьютексов, а предлагаемые вами мьютексы потребуют накладных рассходов при переключение в кернел мод и обратно.

IID>Кстати, отключать прерывания — что за убогость ? В NT спинлоки прекрасно крутятся не запрещая прерываний.

В Linux отключаются soft прерывания, hard не блокируются.

Хотите подискутировать об архитектуре современных операционных систем? Для начала покажите вашу обещанную реализацию семафора через мьютекс с накладными рассходами близкими к кернел мод.

Здравствуйте, IID, Вы писали:

IID>Фигню ты несёшь. pthread-ные семафоры реализованы совершенно не так.

Ну, я же говорю, что сразу видно "специалиста". Posix семафоры в Linux реализованы в юзер мод через фьютексы из кренел мод.

IID>Покажи-ка мне нормальную ядерную реализацию, взаимодествующую с планировщиком.

На собеседованиях вы так же сразу на "ты", "Фигню ты несёшь", "Покажи-ка мне"?

Если вы не знаете, как реализовано в ядре переключение процессов не позорьтесь. Вы про кванты времени, вытеснение, pit, hpet, acpi таймер или что там у вас в висте, про tsc слышали? Семафор не должен никак взаимодействовать с планировщиком, то что вы говорите это глупость.

Как тестовый вопрос задание про semaphore на тему многопоточность очень даже хорошо. По крайней мере придется вспомнить что такое Event, как обновлять lock-счетчик. Видно как мысли кандидат. Кода в пределах 100-200 строк, которые можно даже на доске писать, и не скажешь, что используют кандидата, чтобы писать продакшен код.

Здравствуйте, sysenter, Вы писали:

S>Семафор не должен никак взаимодействовать с планировщиком, то что вы говорите это глупость.

В том смысле, что он может переключить текущий поток выполнения и на этом всё.

Здравствуйте, rfq, Вы писали:

rfq>Смешно. А если тебе на собеседовании предложат написать процедурку умножения целых чисел, используя только сложение и сдвиг, ты их тоже педерастами обзовешь? Или ты и на собеседованиях только нетленку ваяешь?

Если предложат это в качестве теста на IQ, то ок. Кстати, я не знаю алгоритма, мне придётся его придумать.

S>В винде нету фьютексов, а предлагаемые вами мьютексы потребуют накладных рассходов при переключение в кернел мод и обратно.

Функция InitializeCriticalSectionAndSpinCount (http://msdn.microsoft.com/en-us/library/ms683476(v=VS.85).aspx) является весьма неплохим аналогом futex'ов. Внутренности и дополнительные грабли описаны тут: http://msdn.microsoft.com/en-us/magazine/cc164040.aspx

Это я к чему, к тому, что Critical Section в Windows не требует всяких там "накладных расходов" и для многих применений вполне себе заменяет futex.

Здравствуйте, IID, Вы писали:

L>>Твой светофор — это не примитивная задача, а кусок бессмысленного говнокода.

IID>Мой семафор это отличный индикатор. Проверено неоднократно. Чем лучше кандидат справлялся с ним, тем меньше потом багов с потокам было у него в коде. А половина тех кто сливали и на другие вопросы ответить толком не могли.

Код в студию тогда.

L>>Чтобы разбираться в многопоточности, нужно:
L>>1. Знать, зачем, когда и почему необходимо иметь много потоков.
L>>2. Знать, какие грабли из этого отрастают как их избегать.

IID>Если не можешь осилить семафор, то п2 сфейлен.

Ты либо чего-то не договариваешь, либо сам в MT-вопросах плаваешь конкретно.

L>>Все.
L>>Ниасилившие эти две проблемы занмаются конструированием велосипедов.

IID>Да причём тут велосипед. Ты читать умеешь ? Зто задача для собеседования. А не код в production.

При том, что это велосипед.

Вам сотрудник нужен код в продакшен писать или задачи для собесебований решать? Или, как тут уже неоднократно предположили, у вас продакшен из велосипедов и состоит?

Здравствуйте, IID, Вы писали:

L>>От последних вреда на два десятичных порядка больше.
IID>Не уловил мысль. Давай, развивай.

От полного лопуха в многопоточности вреда либо не будет совсем, так как или будет делать как старшие сказали или будет просто следовать общему стилю, либо его косяки будут очевидны и сразу бросаться в глаза. Не могу представить code review, которое пропустит TerminateThread, например.

А вот от "гуру" многопоточности того и жди подвоха. То Scope Guard по религиозным причинам отказываются заюзать, то начинают проектирование с изобретения lock-free контейнеров (ага, еще до выяснения, будет ли многопоточность вообще и если будет, нужен ли будет доступ к контейнерам из разных потоков), то придумают супер-мьютексы с возможностью обхода, когда очень надо, то просто накосячат пул потоков там, где можно и нужно было бы обойтись одним потоком.

Следует отметить, что в изобретаемых lock-free конейнерах, понятное дело, совместимость с STL в велосипедных контейнерах не рассматривается как необходимость, зато предоставляется некий интерфейс, с которым остальная команда потом имеет группенсекас перед релизом. И конечно, гуры не утруждают себя написанием юнит-тестов для своих шыдевров (еще чего, ценное время гуру на такую ерунду расходовать).

В одном чудном месте меня попросили написать реализацию семафора через мьютекс

Здравствуйте, SkyDance, Вы писали:

SD>Функция InitializeCriticalSectionAndSpinCount (http://msdn.microsoft.com/en-us/library/ms683476(v=VS.85).aspx) является весьма неплохим аналогом futex'ов. Внутренности и дополнительные грабли описаны тут: http://msdn.microsoft.com/en-us/magazine/cc164040.aspx

В случае футексов переход в кернел мод происходит только в случае конфликтов, в случае InitializeCriticalSectionAndSpinCount переход в кернел мод с последующем засыпанием потока происходит если не удалось за время отведённое спинлоку захватить блокировку, правильно? Значит и реализация не совсем будет соответствовать. Но я не буду спорить на тему какое ядро ОС лучше.

Поскольку IID обругал использование спинлоков он явно не вкурсе про InitializeCriticalSectionAndSpinCount, а значит свой семафор будет реализовывать через мьютекс, что уже говорить о его "высоком профессиональном" уровне.

SD>Это я к чему, к тому, что Critical Section в Windows не требует всяких там "накладных расходов" и для многих применений вполне себе заменяет futex.

Осталось только получить код от IID который он что-то не спешит показать.

Здравствуйте, s.ts, Вы писали:

ST>В одном чудном месте меня попросили написать реализацию семафора через мьютекс

И как, вы справились, как делали? Что сказал просивший про код?

Здравствуйте, Паблик Морозов, Вы писали:

A_N>>Предстоит важное собеседование, там сказали любят спрашивать различные вопросы про многопоточность под Win и давать разные задачки на эту тему.
A_N>>А ктонить может подбросить задач и вопросов с собеседований про это все? Есть какие-либо "стандартные" задачи на это дело (ну как про круглые люки)?
A_N>>Для примера: на первом собеседовании меня пока попросили написать синхронизированную очередь.

ПМ>Join-calculus, pi-calculus, CSP, STM, non-blocking IO без каллбеков и прочей содомии, nested data parallelism, модель акторов, temporal logic of actions и пр. Если начнут с умным видом прашивать про мьютексы/сигналы/эвенты — вставай и уходи.

Хороший наброс, годный

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, Aleksey_NN, Вы писали:

IID>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

Стало любопытно. Итого — десять минут на реализацию, плюс еще минут пятнадцать на
визуальную проверку, плюс минут двадцать пять на написание и прогон тестового сценария в
большом диапазоне потоков и входных значений. При этом кода всего сотня строчек, не больше.

P.S. Гуру по многопоточности себя не считаю. Просто удивляюсь реакции.

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Если предложат это в качестве теста на IQ, то ок. Кстати, я не знаю алгоритма, мне придётся его придумать.

http://ru.musorosvalka.wikia.com/wiki/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%81%D1%82%D0%BE%D0%BB%D0%B1%D0%B8%D0%BA

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Это совсем не то, что требовалось. Речь была о полноценном синхрообъекте, на ожидании которого тред уснёт, не отжирая ресурсы. Ты показывешь случай, когда приоритет исполнения выше чем у планировщика, и ничего не остаётся кроме как крутиться в цикле. Вместо нормального ожидания на синхрообъекте тут поджигание ядера процессора.

S>Это реализация семафора в кернел мод. На то, чтобы объект уснул требуется затратить существенное время, если делать так как предлагаете вы в случае попытки захвата семафора если он будет занят, но освободиться через миллисекунду потребуется затратить машинное время на сохранение регистров потока и другой необходимой информации, а потом пробудить поток и снова восстановить его контекст. Так же нет гарантии, что проснётся именно этот поток.
S>Всё это потребует гигантского машинного времени, на порядок большего чем со спинлоками. В винде, если мне не изменяет память, семафоры так же реализованы через спинлоки в том числе и только если виндовый семафор не освобождается в течении 400 циклов поток засыпает.

IID>>Покажи-ка мне лучше ядерную реализацию вот этого: http://cristi.indefero.net/p/uClibc-cristi/source/tree/30cb4b5cd2e3e6da7603d34b5d0c4dd21ed26bff/libpthread/nptl/sysdeps/unix/sysv/linux/sem_wait.c

S>Это реализация Posix семафора в юзер мод через фьютекс в кернел мод.
S>В винде нету фьютексов, а предлагаемые вами мьютексы потребуют накладных рассходов при переключение в кернел мод и обратно.

Есть критические секции. И таки интересно, где это я предлагал мьютексы ?

IID>>Кстати, отключать прерывания — что за убогость ? В NT спинлоки прекрасно крутятся не запрещая прерываний.

S>В Linux отключаются soft прерывания, hard не блокируются.

Ясно. Если это так, то это практически аналог IRQL==DISPATCH_LEVEL.

S>Хотите подискутировать об архитектуре современных операционных систем? Для начала покажите вашу обещанную реализацию семафора через мьютекс с накладными рассходами близкими к кернел мод.


#pragma once

//
// Наивная версия захвата/освобождения.
// Максимально прозрачная.
//
class Semaphore
{
protected:
    HANDLE m_hEvent;
    volatile LONG m_lLockCount;
    LONG m_lMaxCount;    

public:
    Semaphore();
    ~Semaphore();

    bool Init(
        LONG lMaxCount
        );
    void Close();

    bool Acquire(
        DWORD dwTimeout = INFINITE
        );
    void Release();
};

Semaphore::Semaphore()
    : m_hEvent(NULL)
    , m_lLockCount(0)
    , m_lMaxCount(0)
{
}

Semaphore::~Semaphore()
{
    Close();
}

bool Semaphore::Init(
    LONG lMaxCount
    )
{
    ASSERT(!m_hEvent);
    ASSERT(lMaxCount > 0);

    if (lMaxCount <= 0)
        return false;

    m_lMaxCount = lMaxCount;

    m_hEvent = CreateEvent(NULL, FALSE, FALSE, NULL);
    return !!m_hEvent;
}

void Semaphore::Close()
{
    if (m_hEvent)
    {
        ASSERT(!m_lLockCount);
        CloseHandle(m_hEvent);
        m_hEvent = NULL;
    }
}

bool Semaphore::Acquire(
    DWORD dwTimeout /*= INFINITE */
    )
{
    ASSERT( m_hEvent );
    if (InterlockedIncrement(&m_lLockCount) <= m_lMaxCount)
        return true;

    if (WAIT_OBJECT_0 == WaitForSingleObject(m_hEvent, dwTimeout))
        return true;

    Release();
    return false;
}

void Semaphore::Release()
{
    if (InterlockedDecrement(&m_lLockCount) >= m_lMaxCount)
        return;

    SetEvent(m_hEvent);
}

//
// Версия захвата/освобождения, минимизирующая переключение в KM.
//
class SemaphoreSMP : public Semaphore
{
    LONG m_lWaitersCount;

public:
    SemaphoreSMP() : m_lWaitersCount(0) {}

    bool Acquire(
        DWORD dwTimeout = INFINITE
        );
    void Release();
};

bool SemaphoreSMP::Acquire(
    DWORD dwTimeout /*= INFINITE */
    )
{
    ASSERT( m_hEvent );
    if (InterlockedIncrement(&m_lLockCount) <= m_lMaxCount)
        return true;

    int iSemSpinCount = 300;
    for(int i = 0; i < iSemSpinCount; i++)
    {
        if (InterlockedCompareExchange(&m_lLockCount, m_lMaxCount, m_lMaxCount) == m_lMaxCount)
            return true;
    }

    InterlockedIncrement(&m_lWaitersCount);
    DWORD dwWaitResult = WaitForSingleObject(m_hEvent, dwTimeout);
    if (WAIT_OBJECT_0 == dwWaitResult)
        return true;

    InterlockedDecrement(&m_lWaitersCount);
    InterlockedDecrement(&m_lLockCount);
    return false;
}

void SemaphoreSMP::Release()
{
    if (InterlockedDecrement(&m_lLockCount) >= m_lMaxCount)
        return;

    if (InterlockedDecrement(&m_lWaitersCount) >= 0)
    {
        SetEvent(m_hEvent);
    } else {
        InterlockedIncrement(&m_lWaitersCount);
    }
}

Здравствуйте, IID, Вы писали:

IID>Есть критические секции. И таки интересно, где это я предлагал мьютексы ?

Критические секции которые позволяют или бесконечно ждать или попробовать tryentercriticalsection.
Ты высказал недовольство спинлоками, а в приведённом тобой коде крутиться цикл в 300 итераций и критические секции ты не используешь.
Непонятно это.

Про мьютексы, события и т.д. ты упомянул в своём первом сообщении. Впрочем это было всего лишь упоминание примитивов синхронизации.

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

Здравствуйте, rfq, Вы писали:

rfq>Здравствуйте, Паблик Морозов, Вы писали:

ПМ>>Если предложат это в качестве теста на IQ, то ок. Кстати, я не знаю алгоритма, мне придётся его придумать.

rfq>http://ru.musorosvalka.wikia.com/wiki/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%81%D1%82%D0%BE%D0%BB%D0%B1%D0%B8%D0%BA

Ага, или так: http://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm

Так что там есть над чем подумать, если конечно в голове осталось что-нибудь кроме мьютексов.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Да что вы такое говорите! Много вы семафоров в кернелмоде реализовали ? Как предполагается делать семафор в кернелмоде без других объектов синхронизации ? Расскажите, очень интересно послушать. Особенно в ключе "намного проще и понятнее".

S>Расскажу, в ядре Linux семафоры реализованы через спинлоки и отключение прерываний, спинлок это просто цикл.
S>Сразу видно "специалиста" по ядерным примитивам синхронизации.

Не, ну вообще говоря на мой взгляд семафор на одних спинлоках и asm cli не реализовать, нужно еще добавиться
в waitqueue, сменить состояние и вызвать функцию перепланировщика. Иначе как заблокироваться-то. В режиме ядра то многозадачность не вытесняющая.
Прерывания от PIT по кванту времени правда тоже вызывают schedule, но насколько я помню если проц. застрял в kernel mode
то туда и вернется.

PS:

Только не говорите, что я несу чушь — я этого не вынесу!

Здравствуйте, gangof4, Вы писали:

G>Иначе как заблокироваться-то. В режиме ядра то многозадачность не вытесняющая.

У меня была уверенность, что ядро полностью вытесняемое включая и кернел мод, нужно будет перепроверить.

G>Прерывания от PIT по кванту времени правда тоже вызывают schedule, но насколько я помню если проц. застрял в kernel mode

Что-то как-то сомнительно.

Здравствуйте, sysenter, Вы писали:

S>У меня была уверенность, что ядро полностью вытесняемое включая и кернел мод, нужно будет перепроверить.

Полностью вытесняемое.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

S>Критические секции которые позволяют или бесконечно ждать или попробовать tryentercriticalsection.
S>Ты высказал недовольство спинлоками, а в приведённом тобой коде крутиться цикл в 300 итераций и критические секции ты не используешь.
S>Непонятно это.

Недовольство ядерными спинлоками. Юзермодные спинлоки прекрасно вытесняются, в отличие от.

Здравствуйте, sysenter, Вы писали:

S>Про код, бегло посмотрел, работать похоже будет. Только не вижу производительности близкой к ядерной, как минимум четыре переключения контекста будет. Свой интерес я удовлетворил.

Переключения контекста будут не всегда, а только если не удалось захватить владение сразу. Будет не более одного переключения при захвате, и не более одного при освобождении. Как ты 4 насчитал ? Туда-обратно что ли считаешь ?

А теперь возьмём ядерный семафор. В Win будет строго переключение контекста и захвате и при освобождении. Про позикс не скажу, ты показывай, а мы посмотрим.

Здравствуйте, IID, Вы писали:

IID>Недовольство ядерными спинлоками. Юзермодные спинлоки прекрасно вытесняются, в отличие от.

Ядерные тоже вполне себе вытесняются. Вот кусок из реализации спинлока:

void __lockfunc __raw_##op##_lock(locktype##_t *lock)            \
{                                    \
    for (;;) {                            \
        preempt_disable();                    \
        if (likely(do_raw_##op##_trylock(lock)))        \
            break;                        \
        preempt_enable();                    \
                                    \
        if (!(lock)->break_lock)                \
            (lock)->break_lock = 1;                \
        while (!raw_##op##_can_lock(lock) && (lock)->break_lock)\
            arch_##op##_relax(&lock->raw_lock);        \
    }                                \
    (lock)->break_lock = 0;                        \
}

Только выделенное не вытесняется, остальная часть цикла спокойна может быть вытеснена.

Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, IID, Вы писали:

L>>>Твой светофор — это не примитивная задача, а кусок бессмысленного говнокода.

IID>>Мой семафор это отличный индикатор. Проверено неоднократно. Чем лучше кандидат справлялся с ним, тем меньше потом багов с потокам было у него в коде. А половина тех кто сливали и на другие вопросы ответить толком не могли.

L>Код в студию тогда.

Интересный манёвр. Ты требуешь от меня решения моей же задачи. Чтобы доказать мне что задача плохая ? Я правильно понимаю твоё требование ?

L>>>Чтобы разбираться в многопоточности, нужно:
L>>>1. Знать, зачем, когда и почему необходимо иметь много потоков.
L>>>2. Знать, какие грабли из этого отрастают как их избегать.

IID>>Если не можешь осилить семафор, то п2 сфейлен.

L>Ты либо чего-то не договариваешь, либо сам в MT-вопросах плаваешь конкретно.

Ты точно адекватен ? Реплики как будто сгенерированы ботом.

L>>>Все.
L>>>Ниасилившие эти две проблемы занмаются конструированием велосипедов.

IID>>Да причём тут велосипед. Ты читать умеешь ? Зто задача для собеседования. А не код в production.

L>При том, что это велосипед.

Задам вопрос, уже звучавший в этой ветке: а ты на собеседованиях только нетленки ваяешь ?

L>Вам сотрудник нужен код в продакшен писать или задачи для собесебований решать? Или, как тут уже неоднократно предположили, у вас продакшен из велосипедов и состоит?

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

Здравствуйте, sysenter, Вы писали:

S>У меня была уверенность, что ядро полностью вытесняемое включая и кернел мод, нужно будет перепроверить.

В NT так и есть. В буханке очень не уверен, слишком она костыльная.

Здравствуйте, IID, Вы писали:

IID>Как ты 4 насчитал ? Туда-обратно что ли считаешь ?

Именно так и считаю, разве это не соответствует тому, что происходит? А раз именно так и происходит — контекст сохраняется, выполняется вход в кернел мод, работа, восстанавливается контекст, выход в юзер спейс. Почему я должен считать иначе?

IID>А теперь возьмём ядерный семафор. В Win будет строго переключение контекста и захвате и при освобождении. Про позикс не скажу, ты показывай, а мы посмотрим.

Posix это юзерспейс библиотека основанная на ядерных фьютексах. Я же приводил код симафора из ядра.

Здравствуйте, IID, Вы писали:

IID>В NT так и есть. В буханке очень не уверен, слишком она костыльная.

Что еcть буханка?

Здравствуйте, sysenter, Вы писали:

S>

S>        if (likely(do_raw_##op##_trylock(lock)))        \
S>            break;                        \
S>

Разверни внутренности вот этих вызовов. Нет сорцов буханки под рукой, а гуглить лень.

Поясню свою мысль про спинлоки. В Win ядерные спинлоки, как примитив синхронизации, юзаются на уровне софтовых прерываний >= уровню планировщика (DISPATCH_LEVEL). Соответственно, на этом уровне объектами синхронизаии пользоваться нельзя. Т.к. поток никогда не будет перепланирован. Единственное, что может прервать код, захвативший спинлок, это прерывание не ниже аппаратного. Поэтому, увидев ожидание внутри спинлока я логично предположил, что вместо ожидания с помощью планировщика имеет место быть тупой цикл.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, gangof4, Вы писали:

G>>Иначе как заблокироваться-то. В режиме ядра то многозадачность не вытесняющая.

S>У меня была уверенность, что ядро полностью вытесняемое включая и кернел мод, нужно будет перепроверить.

Я говорю про Linux..Цитирую O'Reilly Undestanding Linux Kernel:

11.2.1 Nonpreemptability of Processes in Kernel Mode
As already pointed out, the Linux kernel is not preemptive, that is, a running process cannot
be preempted (replaced by a higher-priority process) while it remains in Kernel Mode. In
particular, the following assertions always hold in Linux:
• No process running in Kernel Mode may be replaced by another process, except when
the former voluntarily relinquishes control of the CPU.[1]
[1] Of course, all context switches are performed in Kernel Mode. However, a context switch may occur only when the current process is going to
return in User Mode.
• Interrupt or exception handling can interrupt a process running in Kernel Mode;
however, when the interrupt handler terminates, the kernel control path of the process
is resumed.
• A kernel control path performing interrupt or exception handling can be interrupted
only by another control path performing interrupt or exception handling.

G>>Прерывания от PIT по кванту времени правда тоже вызывают schedule, но насколько я помню если проц. застрял в kernel mode

S>Что-то как-то сомнительно.

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

Здравствуйте, IID, Вы писали:

IID>Разверни внутренности вот этих вызовов. Нет сорцов буханки под рукой, а гуглить лень.

Сводиться к вызову

# define arch_spin_trylock(lock)    ({ (void)(lock); 1; })

где lock есть что-то архитектурно зависимое типа ассемблерного префикса lock из x86, дальше ковырять лень.

IID>Поясню свою мысль про спинлоки. В Win ядерные спинлоки, как примитив синхронизации, юзаются на уровне софтовых прерываний >= уровню планировщика (DISPATCH_LEVEL). Соответственно, на этом уровне объектами синхронизаии пользоваться нельзя. Т.к. поток никогда не будет перепланирован. Единственное, что может прервать код, захвативший спинлок, это прерывание не ниже аппаратного. Поэтому, увидев ожидание внутри спинлока я логично предположил, что вместо ожидания с помощью планировщика имеет место быть тупой цикл.

Имеет место тупой цикл, который может быть вытеснен в определённой точке.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Как ты 4 насчитал ? Туда-обратно что ли считаешь ?

S>Именно так и считаю, разве это не соответствует тому, что происходит? А раз именно так и происходит — контекст сохраняется, выполняется вход в кернел мод, работа, восстанавливается контекст, выход в юзер спейс. Почему я должен считать иначе?

Потому что так не принято. Считаются накладные расходы на ядерный вызов. Это сразу и туда, и обратно. Считать их как отдельные сущности не имеет смысла как минимум потому что они не равны друг другу по вычислительным затратам.

IID>>А теперь возьмём ядерный семафор. В Win будет строго переключение контекста и захвате и при освобождении. Про позикс не скажу, ты показывай, а мы посмотрим.

S>Posix это юзерспейс библиотека основанная на ядерных фьютексах. Я же приводил код симафора из ядра.

Сколько будет переключений в KM на каждый лок и анлок ? ты бы лучше юзермодный код привёл, чтобы сравнить затраты на переключение.

Здравствуйте, sysenter, Вы писали:

S>Что еcть буханка?

Здравствуйте, gangof4, Вы писали:

G>Вот как..Ну во всяком случае если драйвер линуха в кернел моде зациклить, то ничего уже не работает.
G>Если я что-то не так понимаю буду рад услышать.

Буханка, такая буханка

Я тоже помню потоки ругани про однозадачное буханочное ядро от знакомого рисёчера.

Здравствуйте, sysenter, Вы писали:

S>Про код, бегло посмотрел, работать похоже будет.

Внимание, вопрос. Неужели набросать нечто подобое составляет хоть малейшую сложность для человека, декларирующего знание многопоточности ?

Здравствуйте, gangof4, Вы писали:

G>Я говорю про Linux..Цитирую O'Reilly Undestanding Linux Kernel:

Это про какую версию ядра 2.6 или 2.4? Книгу какого года издания читаете?
Ядро Linux вытесняемое и потоки ядра также могут вытеснены, это 100% информация.

G>Вот как..Ну во всяком случае если драйвер линуха в кернел моде зациклить, то ничего уже не работает.

Драйвера в линухе архитектурно делятся на нижнюю и верхнюю половины, нижняя половина не может быть вытеснена и она минимально по размеру выполняемого кода. А вот верхняя половина драйвера может быть вытеснена, если это специально не запрещено.

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, gangof4, Вы писали:

G>>Вот как..Ну во всяком случае если драйвер линуха в кернел моде зациклить, то ничего уже не работает.
G>>Если я что-то не так понимаю буду рад услышать.

IID>Буханка, такая буханка

Я тоже помню потоки ругани про однозадачное буханочное ядро от знакомого рисёчера.

Ну вообще с невытесняемым ядром на мой взгляд трудности некоторые отпадают..Однако для SMP уже конечно
все не так хорошо.

Здравствуйте, IID, Вы писали:

Происки завистников)

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, gangof4, Вы писали:

G>>Я говорю про Linux..Цитирую O'Reilly Undestanding Linux Kernel:

S>Это про какую версию ядра 2.6 или 2.4? Книгу какого года издания читаете?
S>Ядро Linux вытесняемое и потоки ядра также могут вытеснены, это 100% информация.

Каюсь, ядро 2.4. А что 2.6 вытесняемое? Дайте ссылку что-ли..

G>>Вот как..Ну во всяком случае если драйвер линуха в кернел моде зациклить, то ничего уже не работает.

S>Драйвера в линухе архитектурно делятся на нижнюю и верхнюю половины, нижняя половина не может быть вытеснена и она минимально по размеру выполняемого кода. А вот верхняя половина драйвера может быть вытеснена, если это специально не запрещено.

Как я безнадежно отстал от жизни..А верхняя и нижняя это как?

Здравствуйте, IID, Вы писали:

IID>Потому что так не принято. Считаются накладные расходы на ядерный вызов. Это сразу и туда, и обратно. Считать их как отдельные сущности не имеет смысла как минимум потому что они не равны друг другу по вычислительным затратам.

В литературе объясняется полностью весь процесс от вызова обёртки ядерного вызова, последующего вызова функции врапера которая из таблицы номеров системных вызовов извлекает адрес в кернел моде, сохранения контекста, перехода на обработчик ядерного вызова и восстановления контекста после выполнения работы. Так вот расходы на сохранение и восстановление контекста одинаковы, а время работы врапера и поиск адреса в таблице системных вызовов не настолько велико, чтобы вход в кернел мод был хотя бы в два раза дороже выхода. И заметь у меня было написано _4 переключения контекста_, а не 4 обработки ядерного вызова.

IID>Сколько будет переключений в KM на каждый лок и анлок ? ты бы лучше юзермодный код привёл, чтобы сравнить затраты на переключение.

Будет нисколько, в КМ переключение происходит только для разрешения конфликта, а так лок/анлок происходит в юзерспейс через расшареную память где атомарно происходит изменение счётчика. Мне ковырять код glibc не интересно, от этого никакой пользы не будет по сравнению с кодом ядра.

Здравствуйте, IID, Вы писали:

IID>Внимание, вопрос. Неужели набросать нечто подобое составляет хоть малейшую сложность для человека, декларирующего знание многопоточности ?

Ну, не составляет, вопрос то был в том, что реализовать в юзер мод семафор с производительностью близкой к КМ не реально. Что вы удачно и подтвердили.

Здравствуйте, gangof4, Вы писали:

G>Каюсь, ядро 2.4. А что 2.6 вытесняемое? Дайте ссылку что-ли..

В той же самой книге только 3-е издание за 2005 год откройте главу 7 про планирование процессов.

G>Как я безнадежно отстал от жизни..А верхняя и нижняя это как?

Это архитектурное разделение драйвера на приём данных и их обработку.
Нижняя половина отрабатывает сразу, как поступает прерывание от устройства. Нижняя половина не может быть вытеснена. К нижней половине предъявляются требования минимального по размеру кода и минимального времени исполнения, назначение сводиться к заполнению какой либо структуры и завершению работы.
Верхняя половина уже планируется на выполнение, она обрабатывает сохранённые нижней половиной данные и может быть вытеснена в процессе обработки.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, gangof4, Вы писали:

G>>Каюсь, ядро 2.4. А что 2.6 вытесняемое? Дайте ссылку что-ли..

S>В той же самой книге только 3-е издание за 2005 год откройте главу 7 про планирование процессов.

Уже нашел. Да, так оно и есть еще изменения в планировщике и тд.

G>>Как я безнадежно отстал от жизни..А верхняя и нижняя это как?

S>Это архитектурное разделение драйвера на приём данных и их обработку.
S>Нижняя половина отрабатывает сразу, как поступает прерывание от устройства. Нижняя половина не может быть вытеснена. К нижней половине предъявляются требования минимального по размеру кода и минимального времени исполнения, назначение сводиться к заполнению какой либо структуры и завершению работы.
S>Верхняя половина уже планируется на выполнение, она обрабатывает сохранённые нижней половиной данные и может быть вытеснена в процессе обработки.

Ну то что в прерывании нельзя вытеснить это понятно, так всегда и было. Дальше идут bottomhalf, tasklet и тд.
Преемственность я как понимаю запрещается в спинлоках. Однако я думаю все это не должно влиять на реализацию
семафора.

Сколько всего нового можно подчерпнуть на рсдн!

Здравствуйте, gangof4, Вы писали:

G>Преемственность я как понимаю запрещается в спинлоках. Однако я думаю все это не должно влиять на реализацию
G>семафора.

Судя по коду который я привёл IID выше, в спинлоках в цикле попытка залочить обрамлена отключением/включением вытеснения т.е. спинлок похоже может быть вытеснен в определённой точке, сразу после включения вытеснения.

Пожалуйста, уважайте коллег и не допускайте излишнего цитирования. Для неуважающих напомню, что есть правила форума и ресурса + санкции за несоблюдение оных. Модератор

G>Сколько всего нового можно подчерпнуть на рсдн!

Однако надо помнить что одно прерывание, всегда может быть прервано другим прерыванием.

Здравствуйте, gangof4, Вы писали:

G>Однако надо помнить что одно прерывание, всегда может быть прервано другим прерыванием.

Soft прерывание может быть вытеснено, но не hard. Собственно для софт прерываний нижняя половина и не используется, а всякие тасклеты и т.п

Здравствуйте, Polonius, Вы писали:

P>Все это значит, чтобы передать "валидный" хэндл в другой поток, нужно сначала сделать ему AddRef()
P>и только потом передавать в др поток (тогда можно считать, что в новом потоке "валидный" хэндл).
Нельзя, нужно дождаться чтобы и другой поток сделал AddRef.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Потому что так не принято. Считаются накладные расходы на ядерный вызов. Это сразу и туда, и обратно. Считать их как отдельные сущности не имеет смысла как минимум потому что они не равны друг другу по вычислительным затратам.

S>В литературе объясняется полностью весь процесс от вызова обёртки ядерного вызова, последующего вызова функции врапера которая из таблицы номеров системных вызовов извлекает адрес в кернел моде, сохранения контекста, перехода на обработчик ядерного вызова и восстановления контекста после выполнения работы. Так вот расходы на сохранение и восстановление контекста одинаковы, а время работы врапера и поиск адреса в таблице системных вызовов не настолько велико, чтобы вход в кернел мод был хотя бы в два раза дороже выхода. И заметь у меня было написано _4 переключения контекста_, а не 4 обработки ядерного вызова.

А кроме этого есть, например, валидация параметров, переданных системному вызову. При этом все параметры, переданные по указателю, копируются в память ядра. Чтобы работа с ними из супервизоровского кода была безопасной.

IID>>Сколько будет переключений в KM на каждый лок и анлок ? ты бы лучше юзермодный код привёл, чтобы сравнить затраты на переключение.

S>Будет нисколько,

Этого просто не может быть. Чтобы уснуть потоку придётся перейти в кернел-мод.

S>в КМ переключение происходит только для разрешения конфликта, а так лок/анлок происходит в юзерспейс через расшареную память где атомарно происходит изменение счётчика.

Пока синхронизация сводится только к изменению счётчика даже наивный вариант не требует перехода в режим ядра. Что насчёт предельных значений ?

S>Мне ковырять код glibc не интересно, от этого никакой пользы не будет по сравнению с кодом ядра.

Очень зря. Иначе бы ты сам убедился что переход в режим ядра будет.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, IID, Вы писали:

IID>>Внимание, вопрос. Неужели набросать нечто подобое составляет хоть малейшую сложность для человека, декларирующего знание многопоточности ?

S>Ну, не составляет,

Замечательно. Значит ты вменяем, в отличие от кучи здесь отметившихся.

S>вопрос то был в том, что реализовать в юзер мод семафор с производительностью близкой к КМ не реально. Что вы удачно и подтвердили.

Реально

Про затраты на системные вызовы мы говорим выше, давай не распыляться по треду.

Здравствуйте, IID, Вы писали:

IID>А кроме этого есть, например, валидация параметров, переданных системному вызову. При этом все параметры, переданные по указателю, копируются в память ядра. Чтобы работа с ними из супервизоровского кода была безопасной.

На счёт параметры переданные по указателю копируются память ядра не уверен, скорее всего в линухе это не так.

IID>Этого просто не может быть. Чтобы уснуть потоку придётся перейти в кернел-мод.

Ну, это беспорно.

IID>Пока синхронизация сводится только к изменению счётчика даже наивный вариант не требует перехода в режим ядра. Что насчёт предельных значений ?

Нужно смотреть код.

IID>Очень зря. Иначе бы ты сам убедился что переход в режим ядра будет.

Glibc весит не меньше ядра, в такой куче кода один раз копался, там всё не очень очевидно. Больше не хочу.

Ты бы хоть почитал о семафорах перед тем как постить сюда неработающего уродца.

Чтобы не быть голословным, вот пример кода на котором твой семафор завалится:

Semaphore sem;  // Создадим семафор, счетчик равен нулю

sem.Init(100);  // Проинициализируем, максимальное значение счетчика может быть 100

// Попробуем захватить наш семафор...

sem.Acquire();  // А тут уже проблема. Счетчик у нас все еще ноль, семафор
                // находится в несигнальном состоянии, acquire() должна заблокироваться,
                // но у тебя она увеличит счетчик на единицу и вернется...

В общем логика у тебя вся неправильная и семафор не работает. В Semaphore::Acquire() нужно уменьшать счетчик и в Semaphore::Release() увеличивать, а не наоборот как это сделано у тебя. И сравнения чтобы определить в сигнальном состоянии семафор или нет нужно делать относительно нуля а не относительно максимального значения.

Ну и еще, ты даешь возможность задать семафору максимальное значение. Однако ты не даешь возможности задать начальное значение счетчика, что вообще-то поважнее максимального значения. Ну и переменную m_lLockCount лучше бы назвать как-нибудь m_lInstanceCount т.к. семафор ведет счет instances какого-нибудь ресурса а не локов. Но это так, мелочи уже.

IID>


IID>#pragma once

IID>//
IID>// Наивная версия захвата/освобождения.
IID>// Максимально прозрачная.
IID>//
IID>class Semaphore
IID>{
IID>protected:
IID>    HANDLE m_hEvent;
IID>    volatile LONG m_lLockCount;
IID>    LONG m_lMaxCount;    

IID>public:
IID>    Semaphore();
IID>    ~Semaphore();

IID>    bool Init(
IID>        LONG lMaxCount
IID>        );
IID>    void Close();

IID>    bool Acquire(
IID>        DWORD dwTimeout = INFINITE
IID>        );
IID>    void Release();
IID>};

IID>Semaphore::Semaphore()
IID>    : m_hEvent(NULL)
IID>    , m_lLockCount(0)
IID>    , m_lMaxCount(0)
IID>{
IID>}

IID>Semaphore::~Semaphore()
IID>{
IID>    Close();
IID>}

IID>bool Semaphore::Init(
IID>    LONG lMaxCount
IID>    )
IID>{
IID>    ASSERT(!m_hEvent);
IID>    ASSERT(lMaxCount > 0);

IID>    if (lMaxCount <= 0)
IID>        return false;

IID>    m_lMaxCount = lMaxCount;

IID>    m_hEvent = CreateEvent(NULL, FALSE, FALSE, NULL);
IID>    return !!m_hEvent;
IID>}

IID>void Semaphore::Close()
IID>{
IID>    if (m_hEvent)
IID>    {
IID>        ASSERT(!m_lLockCount);
IID>        CloseHandle(m_hEvent);
IID>        m_hEvent = NULL;
IID>    }
IID>}

IID>bool Semaphore::Acquire(
IID>    DWORD dwTimeout /*= INFINITE */
IID>    )
IID>{
IID>    ASSERT( m_hEvent );
IID>    if (InterlockedIncrement(&m_lLockCount) <= m_lMaxCount)
IID>        return true;

IID>    if (WAIT_OBJECT_0 == WaitForSingleObject(m_hEvent, dwTimeout))
IID>        return true;

IID>    Release();
IID>    return false;
IID>}

IID>void Semaphore::Release()
IID>{
IID>    if (InterlockedDecrement(&m_lLockCount) >= m_lMaxCount)
IID>        return;

IID>    SetEvent(m_hEvent);
IID>}

IID>//
IID>// Версия захвата/освобождения, минимизирующая переключение в KM.
IID>//
IID>class SemaphoreSMP : public Semaphore
IID>{
IID>    LONG m_lWaitersCount;

IID>public:
IID>    SemaphoreSMP() : m_lWaitersCount(0) {}

IID>    bool Acquire(
IID>        DWORD dwTimeout = INFINITE
IID>        );
IID>    void Release();
IID>};

IID>bool SemaphoreSMP::Acquire(
IID>    DWORD dwTimeout /*= INFINITE */
IID>    )
IID>{
IID>    ASSERT( m_hEvent );
IID>    if (InterlockedIncrement(&m_lLockCount) <= m_lMaxCount)
IID>        return true;

IID>    int iSemSpinCount = 300;
IID>    for(int i = 0; i < iSemSpinCount; i++)
IID>    {
IID>        if (InterlockedCompareExchange(&m_lLockCount, m_lMaxCount, m_lMaxCount) == m_lMaxCount)
IID>            return true;
IID>    }

IID>    InterlockedIncrement(&m_lWaitersCount);
IID>    DWORD dwWaitResult = WaitForSingleObject(m_hEvent, dwTimeout);
IID>    if (WAIT_OBJECT_0 == dwWaitResult)
IID>        return true;

IID>    InterlockedDecrement(&m_lWaitersCount);
IID>    InterlockedDecrement(&m_lLockCount);
IID>    return false;
IID>}

IID>void SemaphoreSMP::Release()
IID>{
IID>    if (InterlockedDecrement(&m_lLockCount) >= m_lMaxCount)
IID>        return;

IID>    if (InterlockedDecrement(&m_lWaitersCount) >= 0)
IID>    {
IID>        SetEvent(m_hEvent);
IID>    } else {
IID>        InterlockedIncrement(&m_lWaitersCount);
IID>    }
IID>}

IID>

S>>Про код, бегло посмотрел, работать похоже будет.

Код абсолютно нерабочий.

IID>Внимание, вопрос. Неужели набросать нечто подобое составляет хоть малейшую сложность для человека, декларирующего знание многопоточности ?

Вот смотри. У тебя было время почитать документацию, посидеть над кодом. И то ты привел здесь абсолютно неправильный код. Что уж говорить о собеседующихся которые находятся в более стрессовом состоянии? Зато понтов-то

IID>>>Более того, "скорее всего" означает кучу говнокода, который на первый взгляд корректен,

ОК>>Этот твой user-space semaphore и есть самый что ни на есть гавнистый говнокод, как бы аккуратно его не написали. А ты даже и не понимаешь этого.

S>Как тестовый вопрос задание про semaphore на тему многопоточность очень даже хорошо. По крайней мере придется вспомнить что такое Event, как обновлять lock-счетчик. Видно как мысли кандидат. Кода в пределах 100-200 строк, которые можно даже на доске писать, и не скажешь, что используют кандидата, чтобы писать продакшен код.

Возможно но не для тех 50-ти минут личного интервью когда надо поговорить о проектах, спросить знания технологий и рассказать о работе.

И на данный момент чувак толкавший это в качестве "задачки для интервью" сам ее же и завалил хотя у самого было время посидеть над ней.

IID>>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

KP>Честно сказать, не понял чем эта задача хуже "8 гномиков встали раком"

Это идиотизм.

KP>либо переверните однонаправленный список или любая другая задача ни о чем.

А вот это я считаю нормально. Сам бы давать не стал но и нос от нее не ворочал. У развернуть списка хотя бы есть практическая ценность. Другое дело что в реальном коде ее писать не будут т.к. уже есть имплементации, но вот делать семафор в юзер спейсе — у нее нет никакой практической ценности.

KP>Даже удивительно что народ столько возмущается, неужели написание такой простой херотени доставляет какие-то трудности?

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

ПМ>Когда вы в последний раз реализовывали мьютекс/сигнал/эвент?

ПМ>Тут товарищь писал, что большая часть собеседуемых не может нормально написать семафор,

Жжошь, чувак!

ST>В одном чудном месте меня попросили написать реализацию семафора через мьютекс

+100 но не потому что считаю что нужно давать такие задачи на интервью, а потому что вижу что человек понимает идиотизм данной задачи.

Здравствуйте, Олег К., Вы писали:

ОК>+100 но не потому что считаю что нужно давать такие задачи на интервью, а потому что вижу что человек понимает идиотизм данной задачи.

Задача на самом деле интересная, я бы добавил к задаче ещё и вопросы про то почему не стоит реализовывать семафор в юзерспейс, какие накладные расходы будут.
Идиотизм, как вы говорите, в самом принципе реализовывать семафор в юзерспейс через примитивы синхронизации ядра. И задача не для собеседования где хотят проверить владение многопоточностью, а как разминка для ума очень даже не плоха.

ST>>В одном чудном месте меня попросили написать реализацию семафора через мьютекс

Тех кто дает именно эту задачу надо избивать бейсбольными битами.

S>И как, вы справились, как делали? Что сказал просивший про код?

По вопросу можно оценить уровень спрашивающего и если он дает такое гуано на интервью, то как специалист он ничто.

Я вообще вначале думал IID имел в виду именно эту задачу когда ответил ему, но потом оказалось что у него требования к задаче послабее (любые примитивы синхронизации).

В общем s.ts привел пример задачи, но условие привел не до конца. Нужно реализовать семафор используя только built-in типы и только mutex-ы. Это первая часть условия. Вторую часть я пока не буду говорить. Попробуй для начала сделать как обычный спинлок. Это просто. Затем уже как настоящий семафор который не потребляет CPU time. Это уже сложнее и для этого нужна вторая часть условия которая вообще сделает задачу еще более абсурдной.

P.S. Вторую часть не говорю пока что потому что к ней надо "прийти" в ходе интервью.
P.P.S. Подчеркну что я категорических против таких задач но к ним надо быть готовым т.к. дураков везде много а они, как говорится, изобретательны.

Здравствуйте, sysenter, Вы писали:

S>Происки завистников)

Особенно в свете этого. Так, что на спинлоки из Linux бочку катить не нужно))
ядро Linux на 1024 процессоров спокойно параллелится, а винда только на 256.

S>Задача на самом деле интересная,

Ты просто не знаешь условия до конца.

S>я бы добавил к задаче ещё и вопросы про то почему не стоит реализовывать семафор в юзерспейс, какие накладные расходы будут.

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

S>Идиотизм, как вы говорите, в самом принципе реализовывать семафор в юзерспейс через примитивы синхронизации ядра.

Ну так и решение задачи ведь и основывается на этом самом принципе. Потому и решение и сама задача являются идиотскими. Не так ее решать надо! Лучше поговорить как это сделано в ядре.

S>И задача не для собеседования где хотят проверить владение многопоточностью, а как разминка для ума очень даже не плоха.

Думаю что именно плоха и ее именно доводят до абсурда. Если человек просто понимает что происходит в ядре когда поток ждет на семафоре и когда семафор отпускается — то это уже достаточные знания. Они же хотят именно рабочий код с надуманным условием (вторая часть условия о котором я тут говорю)!

Здравствуйте, Олег К., Вы писали:

KP>>Честно сказать, не понял чем эта задача хуже "8 гномиков встали раком"
ОК>Это идиотизм.

Я придерживаюсь несколько другой позиции. Главное на собеседовании это точка для начала общения. Пусть это будет задача на логику, пусть это будет задача ан алгоритмы, пусть это будет задача на многопоточность, пусть это будет задача на сети. Общаться только по выполненным проектам, зачастую, может быть недостаточным, потому и надо с чего-то начать.

KP>>либо переверните однонаправленный список или любая другая задача ни о чем.
ОК>А вот это я считаю нормально. Сам бы давать не стал но и нос от нее не ворочал. У развернуть списка хотя бы есть практическая ценность. Другое дело что в реальном коде ее писать не будут т.к. уже есть имплементации, но вот делать семафор в юзер спейсе — у нее нет никакой практической ценности.

Да вот бог его знает насчет практической ценности. По мне так она нулевая, так, не более чем повод "по-трындеть".

KP>>Даже удивительно что народ столько возмущается, неужели написание такой простой херотени доставляет какие-то трудности?
ОК>Ну, данный товарищ сам же ее и завалил, хотя у него было время над ней посидеть. Так что не все так просто, особенно учитывая последнии тенденции на интервью. Плюс не забывай что интервью могут проводить полнейшие дурачки которые доведут любую здравую идею до абсурда.

Честно скажу. С "полнейшими дурачками, которые доведут любую здравую идею до абсурда" я за последние несколько лет на собеседованиях не сталкивался не разу (если говорить не о манагерах, а о людях проводящих технические собеседованя; причем, все не адекватные манагеры, с которыми я сталкивался, были не из РФ, но русские).

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, gangof4, Вы писали:

G>>Однако надо помнить что одно прерывание, всегда может быть прервано другим прерыванием.

S>Soft прерывание может быть вытеснено, но не hard. Собственно для софт прерываний нижняя половина и не используется, а всякие тасклеты и т.п

Я чего-то не совсем понимаю, про что вы говорите. Когда происходит любое прерывание сперва вызывается обработчик ядра, потом последовательно
обработчики всех драйверов которые висят на этом прерывании(которые вызвали request_irq), во время исполнения этого прерывание может быть
прервано прерыванием с более высоким приоритетом(если только не запретить все прерывания в обработчике, хотя на SMP это не поможет).
Более того если драйвер часто должен сам убрать флаг прерывания у девайса, выставившего его(если только это его прерывание, ведь
на одном могут несколько сидеть) иначе прерывание будет вызываться постоянно.
То что исполняется в тасклетах, это вообще не в прерывании устройства не исполняется, а выполняется после, если больше не возникло прерываний.
То есть softirq несмотря на название прерыванием вообще не является, это deferred interrupt handling, который происходит в очереди уже не в контексте
прерывания.
Вообще когда я слышу термин Software Interrupt, мне видятся всякие int 3 в коде, то есть прерывания источником которых служит программа, а не железо.

Здравствуйте, gangof4, Вы писали:

S>>Soft прерывание может быть вытеснено, но не hard. Собственно для софт прерываний нижняя половина и не используется, а всякие тасклеты и т.п
G>Я чего-то не совсем понимаю

Hard это аппаратные прерывания, у каждого проца свой стек таких прерываний и они хранятся в hardirq_stack
Soft это функции отложного выполнения (softirq, тасклеты), у каждого проца свой стек таких прерываний и они хранятся в softirq_stack

Обработчик Hard прерывания А может быть прерван другим обработчиком Hard прерывания Б, но не вытеснен т.е. произойдёт вложение одного обработчика прерывания в другой. После отработки обработчика прерывания Б возобновит работу прерванный обработчик А. В случае вытеснения решение о передаче выполнения принял бы шедулер.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, gangof4, Вы писали:

S>>>Soft прерывание может быть вытеснено, но не hard. Собственно для софт прерываний нижняя половина и не используется, а всякие тасклеты и т.п
G>>Я чего-то не совсем понимаю

S>Hard это аппаратные прерывания, у каждого проца свой стек таких прерываний и они хранятся в hardirq_stack
S>Soft это функции отложного выполнения (softirq, тасклеты), у каждого проца свой стек таких прерываний и они хранятся в softirq_stack

S>Обработчик Hard прерывания А может быть прерван другим обработчиком Hard прерывания Б, но не вытеснен т.е. произойдёт вложение одного обработчика прерывания в другой. После отработки обработчика прерывания Б возобновит работу прерванный обработчик А. В случае вытеснения решение о передаче выполнения принял бы шедулер.

Согласен, только я это вообще говоря и сказал вначале: один обработчик может быть прерван другим. Но не вытеснен.
Вообще так cooperative scheduling работает, если была задача, она прерывается обработчиком прерывания, и даже если он
сигналит задаче с более высоким приоритетом, то все равно сперва возобновит работу прерванная, а уж потом когда она отдаст
управление, та которая с более высоким приоритетом.

Здравствуйте, gangof4, Вы писали:

G>Согласен, только я это вообще говоря и сказал вначале: один обработчик может быть прерван другим. Но не вытеснен.

Вы сказали — Однако надо помнить что одно прерывание, всегда может быть прервано другим прерыванием..
На счёт — Но не вытеснен, это я вас дополнил раньше — Soft прерывание может быть вытеснено, но не hard.

Здравствуйте, Олег К., Вы писали:

IID>>>Я любил давать кандидатам задачку на реализацию семафора "вручную". При условии что остальные объекты синхронизации (ивенты, мьютексы и т.д.) у них есть. Казалось бы, но результат удивлял. Мало кто мог реализовать сразу и без ошибок. Многие не могли найти ошибку и/или исправить, когда на неё показывал пальцем.

O>>Стало любопытно. Итого — десять минут на реализацию, плюс еще минут пятнадцать на
O>>визуальную проверку, плюс минут двадцать пять на написание и прогон тестового сценария в
O>>большом диапазоне потоков и входных значений. При этом кода всего сотня строчек, не больше.

O>>P.S. Гуру по многопоточности себя не считаю. Просто удивляюсь реакции.

ОК>Очередная распальцовка?

Не иначе.
Уж больно я крутой мэн, раз такую задачу осилил.

Здравствуйте, Олег К., Вы писали:

ОК>Возможно но не для тех 50-ти минут личного интервью когда надо поговорить о проектах, спросить знания технологий и рассказать о работе.

Если интервью идет 50 минут, то это не серьезно. Компания собирается получить самый важный ее ресурс — человека. Экономить время интервью — глупость. Нормально, когда интервью идет день, в несколько сессий и проводится разными людьми.

Расспросить о знаниях и проделанной работе это обязательно. В принципе, это уже должно быть в CV и выявлено на телефонном скрининге.

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

Здравствуйте, shrecher, Вы писали:

S>Нормально, когда интервью идет день, в несколько сессий и проводится разными людьми.

Это трынцед какой-то, бежать от таких компаний нужно.

S>Можно спросить про "гору Фудзи", это провокационный вопрос чтобы посмотреть как человек реагирует на стресс.

Это про, как сдвинуть гору Фудзи? Человек может подумать, что здесь работают клинические идиоты, встать и спокойно уйти. И будет прав.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, shrecher, Вы писали:

S>>Нормально, когда интервью идет день, в несколько сессий и проводится разными людьми.

Вообще-то к крупных компания так и интервьюируют. По гугли "Interview at Microsoft"

http://en.wikipedia.org/wiki/Microsoft_interview

The interview day usually comprises meeting with about three to five different employees within Microsoft. A typical schedule might include two interviews in the morning, one lunch interview, and two interviews in the afternoon. The lunch interview can take place in one of Microsoft's various in-house cafeterias or in a restaurant off-campus. In most cases the candidate will interview with two different product teams within a single product group or two entirely different product groups

S>Это трынцед какой-то, бежать от таких компаний нужно.
Тебе и не светит работать в серьезных компаниях.

Здравствуйте, sysenter, Вы писали:

S>Про код, бегло посмотрел, работать похоже будет.

Похоже, не будет. Положим, хотим сделать бинарный семафор, инициализировав предел счетчика 1. Тогда первая нить сделает acquire, увеличив счетчик до 1, и продолжит работу. Вторая нить, получив управление, вызовет acquire, увеличит счетчик до 2 и встанет ждать. Первая нить сделает release, уменьшив счетчик до 1, и не просигналит event, в результате чего вторая нить останется ждать вместо того, чтобы быть просигналенной. Это при беглом просмотре.

Здравствуйте, A.Lokotkov, Вы писали:

AL>Здравствуйте, sysenter, Вы писали:

S>>Про код, бегло посмотрел, работать похоже будет.

AL>Похоже, не будет. Положим, хотим сделать бинарный семафор, инициализировав предел счетчика 1. Тогда первая нить сделает acquire, увеличив счетчик до 1, и продолжит работу. Вторая нить, получив управление, вызовет acquire, увеличит счетчик до 2 и встанет ждать. Первая нить сделает release, уменьшив счетчик до 1, и не просигналит event, в результате чего вторая нить останется ждать вместо того, чтобы быть просигналенной. Это при беглом просмотре.

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

ОК>>Возможно но не для тех 50-ти минут личного интервью когда надо поговорить о проектах, спросить знания технологий и рассказать о работе.

S>Если интервью идет 50 минут, то это не серьезно. Компания собирается получить самый важный ее ресурс — человека. Экономить время интервью — глупость. Нормально, когда интервью идет день, в несколько сессий и проводится разными людьми.

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

S>Расспросить о знаниях и проделанной работе это обязательно. В принципе, это уже должно быть в CV и выявлено на телефонном скрининге.

S>Многие люди с упоением рассказывают о себе, поют как соловьи. Тут как говориться доверяй, но проверяй. Если чел крут, то решить задачку про семафоры для него в пределах часа. Можно спросить про "гору Фудзи", это провокационный вопрос чтобы посмотреть как человек реагирует на стресс.

Это вообще какой-то идиотизм спрашивать про гору Фудзи. Особенно когда этим занимаются какие-то "Рога и Копыта."

S>Вообще-то к крупных компания так и интервьюируют. По гугли "Interview at Microsoft"

Вообще-то сам Майкрософт отошел уже от таких задач как про гору Фудзи. Так что...

Но ладно. Ради Майкрософта я, к примеру, готов потерпеть задачи про гору Фудзи, но когда это дают какие-то "Рога и Копыта"

S>>Это трынцед какой-то, бежать от таких компаний нужно.

S>Тебе и не светит работать в серьезных компаниях.

O>Не иначе.
O>Уж больно я крутой мэн, раз такую задачу осилил.

Ну это ты так думаешь что осилил. IID вон тоже так думал, однако показал полное непонимание как работают семафоры.

И прошу тебя, не надо мне сюда ставить очередной самопальный семафор.

Здравствуйте, Олег К., Вы писали:

ОК>если человека не особо прижимают жизненые обстоятельства, то он пошлет таких в том или ином виде.

Ну и хорошо, что пошлет, значит кандидат несильно мотивирован здесь работать. Лучше не взять нужного кандидата, чем взять не нужного.

ОК>Это вообще какой-то идиотизм спрашивать про гору Фудзи. Особенно когда этим занимаются какие-то "Рога и Копыта."

А чем "Рога и Копыта" (маленькая компания) хуже чем крупная? Если деньги те же, то и качество персонала тоже

Здравствуйте, shrecher, Вы писали:

S>Здравствуйте, sysenter, Вы писали:

S>>Здравствуйте, shrecher, Вы писали:

S>>>Нормально, когда интервью идет день, в несколько сессий и проводится разными людьми.

S>Вообще-то к крупных компания так и интервьюируют. По гугли "Interview at Microsoft"

S>http://en.wikipedia.org/wiki/Microsoft_interview

S>

S>The interview day usually comprises meeting with about three to five different employees within Microsoft. A typical schedule might include two interviews in the morning, one lunch interview, and two interviews in the afternoon. The lunch interview can take place in one of Microsoft's various in-house cafeterias or in a restaurant off-campus. In most cases the candidate will interview with two different product teams within a single product group or two entirely different product groups

S>>Это трынцед какой-то, бежать от таких компаний нужно.
S>Тебе и не светит работать в серьезных компаниях.

MS давно не спрашивает про Фудзи)

Здравствуйте, andy., Вы писали:

A>MS давно не спрашивает про Фудзи)

Читать умеешь? "это провокационный вопрос чтобы посмотреть как человек реагирует на стресс." Можно спросить, что вы будете делать если вас заберут инопланетяне?.

Смысл таких вопросов просто что человек делает в не привычной для него ситуации.

Здравствуйте, Олег К., Вы писали:

O>>Не иначе.
O>>Уж больно я крутой мэн, раз такую задачу осилил.

ОК>Ну это ты так думаешь что осилил. IID вон тоже так думал, однако показал полное непонимание как работают семафоры.

С чувством юмора вообще все в порядке ? Или мне надо было поставить какой-нибудь смайлик ?

ОК>И прошу тебя, не надо мне сюда ставить очередной самопальный семафор.

Изволь объяснить, за что минусы поставил.
Мне, вообще-то, по барабану, но все-таки интересно, с чем именно ты вот в этой цитате не согласен:

>okman:
Тут тонкость еще в том, что SetEvent (освобождение) может быть вызвана двумя или более покидающими
семафор потоками в очень короткий промежуток времени. При этом велик риск того, что войдет только
один поток-новичок. Если семафор рассчитан на одновременное обслуживание нескольких потоков,
то при высокой конкуренции вполне вероятна ситуация, при которой он будет большую часть времени
захвачен только одним-двумя.

S>Это про какую версию ядра 2.6 или 2.4? Книгу какого года издания читаете?
S>Ядро Linux вытесняемое и потоки ядра также могут вытеснены, это 100% информация.

По-человечески вытесняемое оно становится только с RT_PREEMPT patch. Это отдельное ядро, и у SuSE (Novell) оно вообще идет как отдельный Add-On продукт к своему SLES'у. Код ядра там достаточно сильно изменен (патч большой), как раз в тех местах, где синхронизация. В силу специфики моей нынешней работы там приходится периодически копаться (нам нужен soft realtime, а без вытеснения ядра это невозможно в принципе).

Но, боюсь, "очень далеки они от народа", такие варианты линукса (а уж как на этих ядрах плохо работают KDE, Eclipse и gdb — вообще песня, которая стоном зовется).

Здравствуйте, SkyDance, Вы писали:

SD>По-человечески вытесняемое оно становится только с RT_PREEMPT patch. Это отдельное ядро, и у SuSE (Novell) оно вообще идет как отдельный Add-On продукт к своему SLES'у. Код ядра там достаточно сильно изменен (патч большой), как раз в тех местах, где синхронизация. В силу специфики моей нынешней работы там приходится периодически копаться (нам нужен soft realtime, а без вытеснения ядра это невозможно в принципе).

Вообще-то Linux, что называется из коробки удовлетворяет требованиям soft realtime, а патч про который вы говорите нужен для реализации hard realtime в ядре. Здесь.

S>Вообще-то Linux, что называется из коробки удовлетворяет требованиям soft realtime, а патч про который вы говорите нужен для реализации hard realtime в ядре. Здесь.

Терминами мы можем играть сколько угодно (есть разброд и шатания в области того, что считать soft realtime — но то, что в mainstream kernel, очень странный soft RT, разброс setitimer'а влёгкую составляет микросекунды — проверено многократно).
Но вот факт: вытеснение ядра без этого патча очень, что называется, ограничено.
hard realtime не достигается даже с этим патчем (увы), хотя с нужными железками от IBM для несерьезного применения (т.е. не АЭС) уже катит (в частности, для "начинающих" финансовых товарищей, которые еще не пилят свои чипы).

В любом случае, я писал немножко о другом: слухи о вытесняемости ядра Linux (давайте не путать всякий около-ядерный хлам в виде bottom half'ов разных драйверов с собственно ядром) слегка преувеличены.

Здравствуйте, SkyDance, Вы писали:

SD>Терминами мы можем играть сколько угодно (есть разброд и шатания в области того, что считать soft realtime — но то, что в mainstream kernel, очень странный soft RT, разброс setitimer'а влёгкую составляет микросекунды — проверено многократно).

Это как раз и есть софт риалтайм, вообще погрешность равна HZ*0.5 т.е. при HZ = 1000 имеет погрешность до 1.5 миллисекунд.

SD>Но вот факт: вытеснение ядра без этого патча очень, что называется, ограничено.

А можно по конкретнее где именно ограничено, чтобы я в исходниках посмотрел?

Здравствуйте, SkyDance, Вы писали:

Может
SD>Кстати, подумалось, что есть хороший вопрос на внимательность для собеседования:
SD>

SD>class RefCountable
SD>{
SD>  Mutex m;
SD>  int ref_counter;
SD>  void Release()
SD>  {
SD>    m.lock();
SD>    --ref_counter;
SD>    if (ref_counter == 0) delete this;
SD>    m.unlock();
SD>  }
SD>

SD>Требуется исправить код (сразу предупрежу, я не компилировал и не проверял синтаксическую правильность — это код для иллюстрации).

Может так:

class RefCountable
{
  struct auto_lock
    { 
     Mutex &mRef;
     auto_lock(Mutex &m) : mRef(m) { mRef.lock(); }
     ~auto_lock() { mRef.unlock(); }
    }

  Mutex m;
  int ref_counter;
  int increment()
  {
   auto_lock al(m);
   return ++ref_counter;
  }
  int decrement()
  {
   auto_lock al(m);
   return --ref_counter;
  }

  void Release()
  {
   if (!decrement()) delete this;
  }

Здравствуйте, Олег К., Вы писали:
ОК>Реализовать семафор в кернел моде намного проще и понятнее этого изврата который ты хочешь увидеть в юзер моде при помощи других примитивов.
Модельный семафор от IID будет примерно таким же, как честный кернелмодовский; только последний — это ~ спинлок, счетчик и очередь, а для первого — нужно будет на замену подобрать юзермодные примитивы синхронизации.

Здравствуйте, Олег К., Вы писали:
ОК>В общем логика у тебя вся неправильная и семафор не работает. В Semaphore::Acquire() нужно уменьшать счетчик и в Semaphore::Release() увеличивать, а не наоборот как это сделано у тебя.
Неконструктивненько. Прям как в анекдоте. Горло у кружки запаяно и дна нет.

Дело было так...

Что, спрашивают, приходилось делать про многопоточность.
Ну, я вспомнил, что пришлось как-то сделать семафор на спинлоках, т.к. стандартный тормозил — не подходил под задачу.
Ну и отлично, говорят. Давайте тогда напишите нам на бумажке семафор с помощью, ну, к примеру, мьютексов.
Уверены, говорю, м.быть лучше через спин-локи какие-нибудь ?

Нет, говорят, давай через мьютексы.
Объясняю, что через мьютекс не получится, т.к. его нельзя разлочить из другого потока.
А семафор — можно, потому одно через другое не выражается.
С точки зрения использования это и есть большая разница между "семафором со счетчиком 1" и "мьютексом".
Будет неопределенное поведение (линукс или венда) или определенная ошибка (.net какой-нибудь).
Чувак завис.
Странные, мол, вещи говорите.
А как же, спрашивает, у нас-то это работает ?

В итоге выяснилось, что у них там всего 2 потока.
А в 2-х потоках, понятно, не может быть ситуации разлочки мьютекса из другого треда.
Ну, чисто логически. Если там диаграмму состояний нарисовать или код написать, то сразу это дело ясно.

Я к чему.
Вот такие у людей семафоры понаписаны, кторые только в 2-х потоках работают.
При чем, явно, там кто-то написал его, назвал семафором.
А мужики-то [коллеги] и не знают. И не заглянув в реализацию так и не узнают что там за семафор, пока не начнет все это их дело падать раз в 3 месяца с дребезгом по непонятной причине.
Что интересно, эти же люди спрашивают на собеседованиях.
Не удивлюсь, если и статьи на эту тему пишут, аль книжки.
Ну или влюбимом бложеге отжигают — это уж как минимум.
Жесть, в общем.

Здравствуйте, sysenter, Вы писали:

S>Здравствуйте, s.ts, Вы писали:

ST>>В одном чудном месте меня попросили написать реализацию семафора через мьютекс

S>И как, вы справились, как делали? Что сказал просивший про код?

Здравствуйте, sysenter, Вы писали:

S>Задача на самом деле интересная, я бы добавил к задаче ещё и вопросы про то почему не стоит реализовывать семафор в юзерспейс, какие накладные расходы будут.
S>Идиотизм, как вы говорите, в самом принципе реализовывать семафор в юзерспейс через примитивы синхронизации ядра. И задача не для собеседования где хотят проверить владение многопоточностью, а как разминка для ума очень даже не плоха.

Как на такие вопросы можно ответить правильно если что стоит за "примитивами синхронизации ядра" или как работает планировщик никто в деталях, кроме MS, не знает? Все что пишут в книжках — общие слова, но не код. Исходный код был бы единственной точной инфой, а так все это "second hands".

Какой смысл вообще задавать такие вопросы где решение и ответ неоднозначны?

Здравствуйте, shrecher, Вы писали:

S>Как на такие вопросы можно ответить правильно если что стоит за "примитивами синхронизации ядра" или как работает планировщик никто в деталях, кроме MS, не знает? Все что пишут в книжках — общие слова, но не код. Исходный код был бы единственной точной инфой, а так все это "second hands".

Есть исходный код NT и возможно в том исходном коде, что гуляет по сети от w2k тоже есть реализация семафора. Да и потом, зачем на винде сосредотачиваться?

ST>Что, спрашивают, приходилось делать про многопоточность.
ST>Ну, я вспомнил, что пришлось как-то сделать семафор на спинлоках, т.к. стандартный тормозил — не подходил под задачу.

Жесть.

ST>Ну и отлично, говорят. Давайте тогда напишите нам на бумажке семафор с помощью, ну, к примеру, мьютексов.
ST>Уверены, говорю, м.быть лучше через спин-локи какие-нибудь ?

ST>Нет, говорят, давай через мьютексы.
ST>Объясняю, что через мьютекс не получится, т.к. его нельзя разлочить из другого потока.
ST>А семафор — можно, потому одно через другое не выражается.
ST>С точки зрения использования это и есть большая разница между "семафором со счетчиком 1" и "мьютексом".

+1.

ST>Будет неопределенное поведение (линукс или венда) или определенная ошибка (.net какой-нибудь).
ST>Чувак завис.
ST>Странные, мол, вещи говорите.

Ага, бывают такие дурачки.

ST>А как же, спрашивает, у нас-то это работает ?

ST>В итоге выяснилось, что у них там всего 2 потока.
ST>А в 2-х потоках, понятно, не может быть ситуации разлочки мьютекса из другого треда.
ST>Ну, чисто логически. Если там диаграмму состояний нарисовать или код написать, то сразу это дело ясно.

Ну а вообще хоть с ним(и) поговорить можно было? А то все что у меня были на предложение воспользоваться компилятором и/или проверить в MSDN Library уходили в отказ. Говорили что типа сам можешь после интервью проверить свои знания.

Ну и какой вообще результат этого интервью был?

ST>Я к чему.
ST>Вот такие у людей семафоры понаписаны, кторые только в 2-х потоках работают.
ST>При чем, явно, там кто-то написал его, назвал семафором.
ST>А мужики-то [коллеги] и не знают. И не заглянув в реализацию так и не узнают что там за семафор, пока не начнет все это их дело падать раз в 3 месяца с дребезгом по непонятной причине.
ST>Что интересно, эти же люди спрашивают на собеседованиях.
ST>Не удивлюсь, если и статьи на эту тему пишут, аль книжки.
ST>Ну или влюбимом бложеге отжигают — это уж как минимум.
ST>Жесть, в общем.

Действительно жесть. И таких ой как много бывает на интервью. И дело даже не в многопоточности.

S>>Задача на самом деле интересная, я бы добавил к задаче ещё и вопросы про то почему не стоит реализовывать семафор в юзерспейс, какие накладные расходы будут.
S>>Идиотизм, как вы говорите, в самом принципе реализовывать семафор в юзерспейс через примитивы синхронизации ядра. И задача не для собеседования где хотят проверить владение многопоточностью, а как разминка для ума очень даже не плоха.

S>Как на такие вопросы можно ответить правильно если что стоит за "примитивами синхронизации ядра" или как работает планировщик никто в деталях, кроме MS, не знает? Все что пишут в книжках — общие слова, но не код. Исходный код был бы единственной точной инфой, а так все это "second hands".

Вообще-то нормальные интервьюеры спрашивают о понятиях, а они везде одинаковы.

S>Какой смысл вообще задавать такие вопросы где решение и ответ неоднозначны?

	От:	Aleksey_NN
	Дата:	24.05.11 18:54
	Оценка:

	От:	shrecher
	Дата:	24.05.11 19:04
	Оценка:

От:	andy.	__
Дата:	24.05.11 19:14
Оценка:

	От:	ArtK
	Дата:	24.05.11 19:19
	Оценка:	1 (1)

	От:	Aleksey_NN
	Дата:	24.05.11 19:24
	Оценка:

От:	Ulitka	http://lazarenko.me
Дата:	24.05.11 19:27
Оценка:

	От:	BulatZiganshin
	Дата:	24.05.11 20:38
	Оценка:	-2

	От:	Паблик Морозов
	Дата:	24.05.11 22:04
	Оценка:	-5

От:	мыщъх	http://nezumi-lab.org
Дата:	25.05.11 02:03
Оценка:	12 (1) +1

От:	_FRED_	@ViIvanov
Дата:	25.05.11 04:29
Оценка:

	От:	Polonius
	Дата:	25.05.11 06:26
	Оценка:	3 (1) +3

От:	Donz	http://donz-ru.livejournal.com
Дата:	25.05.11 07:53
Оценка:

	От:	landerhigh
	Дата:	25.05.11 14:17
	Оценка:	6 (1) +3

	От:	MescalitoPeyot
	Дата:	25.05.11 16:13
	Оценка:	1 (1) +3

От:	Коваленко Дмитрий	http://www.ibprovider.com
Дата:	25.05.11 19:05
Оценка:

	От:	Олег К.
	Дата:	25.05.11 23:23
	Оценка:	1 (1) +1 -2

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	26.05.11 08:21
Оценка:	5 (2)

	От:	Тот кто сидит в пруду
	Дата:	27.05.11 07:08
	Оценка:

От:	okman	https://searchinform.ru/
Дата:	27.05.11 08:16
Оценка:	-1

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	30.05.11 11:36
Оценка:

От:	Valery A. Boronin	linkedin.com/in/boronin
Дата:	12.06.11 21:26
Оценка: