Быстрый подсчет семафора в Windows?

Question

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

if (AtomicDecremenIfPositive(_counter) > 0) return; // Uncontended
AtomicAdd(&_waiters, 1);
do
{
    if (syscall(SYS_futex, &_counter, FUTEX_WAIT_PRIVATE, 0, nullptr, nullptr, 0) == -1) // Sleep
    {
        AtomicAdd(&_waiters, -1);
        throw std::runtime_error("Failed to wait for futex");
    }
}
while (AtomicDecrementIfPositive(_counter) <= 0);
AtomicAdd(&_waiters, -1);

и сообщение:

AtomicAdd(&_counter, 1);
if (Load(_waiters) > 0 && syscall(SYS_futex, &_counter, FUTEX_WAKE_PRIVATE, 1, nullptr, nullptr, 0) == -1) throw std::runtime_error("Failed to wake futex"); // Wake one

Сначала я подумал, что для Windows нужно просто использовать NtWaitForKeyedEvent (). Проблема в том, что это не прямая подстановка, поскольку она не проверяет атомарно значение в _counter перед входом в ядро, и поэтому может пропустить пробуждение из NtReleaseKeyedEvent (). Хуже того, тогда NtReleaseKeyedEvent () заблокируется. Какое лучшее решение?

Answer 1

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

Answer 2

Я думаю, что-то вроде этого должно работать:

// bottom 16 bits: post count
// top 16 bits: wait count
struct Semaphore { unsigned val; }

wait(struct Semaphore *s)
{
retry:
    do
        old = s->val;
        if old had posts (bottom 16 bits != 0)
            new = old - 1
            wait = false
        else
            new = old + 65536
            wait = true
    until successful CAS of &s->val from old to new

    if wait == true
        wait on keyed event
        goto retry;
}

post(struct Semaphore *s)
{
    do
        old = s->val;
        if old had waiters (top 16 bits != 0)
            // perhaps new = old - 65536 and remove the "goto retry" above?
            // not sure, but this is safer...
            new = old - 65536 + 1
            release = true
        else
            new = old + 1
            release = false
    until successful CAS of &s->val from old to new

    if release == true
        release keyed event
}

edit : но я не уверен, что это вам сильно поможет.Ваш пул потоков обычно должен быть достаточно большим, чтобы поток всегда был готов обработать ваш запрос.Это означает, что не только ожидания, но и сообщения будут всегда идти по медленному пути и идти к ядру.Таким образом, подсчет семафоров, вероятно, является единственным примитивом, когда вам не важен быстрый путь только для пространства пользователя.Сток Win32 семафоров должен быть достаточно хорош.Тем не менее, я счастлив, что оказался неправ!

Answer 3

Я голосую за вашу первую идею, например, критическую секцию и переменную условия. Критическая секция достаточно быстра и использует блокированную операцию, прежде чем перейти в спящий режим. Или вы можете поэкспериментировать с SRWLocks вместо критического раздела. Переменные условий (и SRWLocks) очень быстрые - их единственная проблема в том, что в XP нет условий, но, возможно, вам не нужно указывать эту платформу.

Answer 4

Qt имеет все виды вещей, таких как QMutex, QSemaphore, которые реализованы в духе, подобном тому, что вы представили в своем вопросе.

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