Как реализовать свой собственный механизм блокировки - PullRequest
Новая
       5

Как реализовать свой собственный механизм блокировки

5 голосов
/ 29 сентября 2011

Для назначения (это для параллелизма, если вам интересно) - я должен реализовать свой собственный замок

(более конкретно: TaS, TTas и Array-Lock, как описано в «Искусстве многопроцессорного программирования»)

Есть несколько тестовых схем ввода-вывода, которые я попробовал в сети (очень плохо, что они занимают довольно много времени).

Ваша программа должна считать 9-значные числа, которые проходят определенный тест

(это называется elfproef на голландском языке, я не знаю английскую эквивалентность, извините).

Иногда я получаю немного другое число, что говорит о том, что моя блокировка не работает 100% правильно .

Я реализовал блокировки следующим образом: 

interface Lock
{
    void Lock();
    void Unlock();
}

class TaSLock : Lock
{
    AtomicBool state = new AtomicBool(false);

    void Lock.Lock()
    { while (state.getAndSet(true)); }

    void Lock.Unlock()
    { state.getAndSet(false); }
}

AtomicBool реализован с integer, потому что класс Interlocked не имеет операций для Boolean переменных. Это не оптимально с точки зрения использования памяти, но не имеет (или не должно) иметь значение для скорости. 

class AtomicBool
{
    int value;
    static int True = 1, False = -1;

    public AtomicBool(bool value)
    {
        if (value) this.value = True;
        else this.value = False;
    }

    public void set(bool newValue)
    {
        if (newValue) Interlocked.Exchange(ref value, True);
        else Interlocked.Exchange(ref value, False);
    }

    public bool getAndSet(bool newValue)
    {
        int oldValue;
        if (newValue) oldValue = Interlocked.Exchange(ref value, True);
        else oldValue = Interlocked.Exchange(ref value, False);
        return (oldValue == True);
    }

    public bool get()
    {
        return (Interlocked.Add(ref value, 0) == 1);
    }
}

Теперь в параллельной части, которую я только что использовал: 

theLock.Lock();
counter++;
theLock.Unlock();

Но каждый раз я получаю немного разные результаты.

Есть ли что-то очевидное, что я делаю не так?

1 Ответ

9 голосов
/ 29 сентября 2011

Ганс прав. Ваш атомный логический метод get-and-set, похоже, верен - на самом деле, он мне кажется несколько перегруженным. Кроме того, блокировка выглядит как правильная , поскольку вы создали потенциально крайне неэффективную «спин-блокировку». (То есть все ожидающие потоки просто сидят в узком цикле и спрашивают: «Могу ли я пойти еще? Могу ли я пойти еще?» Вместо того, чтобы идти спать, пока не наступит их очередь.)

Что не правильно, так это то, что ваша блокировка не дает никакой гарантии, что любые два потока, которые оба имеют представление "counter", имеют последовательное представление "counter". Два потока могут быть на разных процессорах, и эти разные процессоры могут иметь разные копии счетчика в своих кешах. Кэшированные копии будут обновляться и только изредка записываться обратно в основную память, тем самым эффективно «теряя» некоторые увеличения.

Реальная реализация блокировки в C # обеспечивает наложение полного барьера памяти, так что чтение и запись не могут перемещаться «вперед и назад во времени» через забор. Это дает подсказку процессорам, что им не нужно быть настолько умными, чтобы так агрессивно кэшировать «счетчик».

...