Здравствуйте, 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 слышали? Семафор не должен никак взаимодействовать с планировщиком, то что вы говорите это глупость.

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

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

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

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


Как тестовый вопрос задание про 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 в велосипедных контейнерах не рассматривается как необходимость, зато предоставляется некий интерфейс, с которым остальная команда потом имеет группенсекас перед релизом. И конечно, гуры не утруждают себя написанием юнит-тестов для своих шыдевров (еще чего, ценное время гуру на такую ерунду расходовать).

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



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

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

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

Здравствуйте, 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

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