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

H>XP. Проц AMD. Что-то у них с lock? Я правда использовал cmpxchg без него
H>- потому, что для однопроцессорной машины он смысла не имеет. А 15% -
H>это в основном алгоритмическая разница — при этом обращений к ядру
H>практически не происходило. Можно сказать, что при этом реализация
H>работала в режиме lock-free. Не думаю, что другая операционка или проц
H>смогли бы замедлить это время, по отношению к любой другой lock-free
H>реализации. Худшее время, когда блокировки происходят постоянно, я тоже
H>написал — разница в два раза — тут я могу поверить во влияние проца и
H>операционки.


Они на AMD, редиски, сделали, что в однопроцессорной конфигурации у них LOCK префикс игнорируется. По крайней мере на write-back памяти.
Поэтому получается, что тяжёлая interlocked операция получается лёгкой. А на Intel процессоре ты получишь следующую картину. Допустим операция вставки в очередь в твоей реализации, которую ты запостил в первом посте, будет занимать 10 тактов — там только несколько манипуляций с указателями. А очередь использующая Interlocked будет — 110 тактов = 10 вставить в очередь + 100 тактов LOCK CMPXCHG....

remark wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Теперь понятно, что ты имел в виду. Что сделаешь — я редко занимаюсь
> H>этим, и не всегда понимаю терминологию.
>
>
> Обычно спин-мьютекс это очередь, которая основана на периодическом
> опросе. Есть спин с активным ожиданием, это когда простой цикл, и есть
> спин с пассивным ожиданием, это когда sleep(0). Но тем не менее это всё
> спин, т.к. оба варианта периодически опрашивают состояние, что бы понять
> когда им действовать.

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

>
> H> Если конкуренция не очень
> H>высока, можно предположить такой, достаточно очевидный вариант (fair,
> H>время разблокирования пропорционально кол-ву ожидающих потоков):
>
>
> К сожалению, это *почти* работающий вариант...
> Тут есть гонка между выходящим потоком и одновременно входящим потоком.
> Т.е. выходящий поток может решить, что ещё никакой поток не пытался
> войти, т.е. ему не надо нотифицировать семафор, и в то же время
> одновременно входящий поток может решить, что мьютекс ещё занят и
> заблокироваться на семафоре. Как результат он "повиснет" на
> неопределённое время...

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

>
> з.ы. вот это можно cоптимизировать:
>
> /* we'd better not to have high concurrency on this mutex */
> while(p->next != o)
> p = p->next;
>
>
>
> В lock-free алгоритмах есть такой трюк как "prev hint". Линк next
> является как бы основным, а линк prev вспомогательным. При этом prev не
> обязан быть 100% правильным, но он является правильным в большинстве
> случаев. Это позволяет в большинстве случаев и использовать prev, а если
> он всё таки не правильный, то иметь какой-то запасной вариант. Вот
> пример модификации. За 100% не ручаюсь, но идея такая:

Понятно, спасибо. Можно и так сделать. Можно совместить оба подхода —
проверять хинт, и при сканировании дополнительно восстанавливать список.

Вот что получилось:

class Mutex
{
public:
    Mutex();
    ~Mutex() {}

    void lock();
    void unlock();

    static void attach_thread();
private:
    enum State { UNCERTAIN, WAITING, RUN };

    struct mqitem
    {
        Mutex * waiting;

        volatile struct mqitem * next;
        struct mqitem * prior;
        State state;
        HANDLE hwait;
    } e;

    static _declspec(thread) mqitem * thread_item;
};

_declspec(thread) Mutex::mqitem * Mutex::thread_item = NULL;

void Mutex::attach_thread()
{
    if (thread_item == NULL) {
        thread_item = new mqitem;
        thread_item->hwait = CreateSemaphore(NULL, 0, LONG_MAX, NULL);
    }
}

Mutex::Mutex()
{
    e.next = NULL;
    e.state = RUN;
    e.waiting = NULL;
}

void Mutex::lock()
{
    mqitem * p, * h;

    assert( thread_item != NULL );
    p = thread_item;
    p->prior = &e;

    do {
        h = (mqitem *)e.next;
        p->next = h;
        p->state = UNCERTAIN;
        p->waiting = this;
    } while( _CAS_PTR((PVOID*)&e.next, (PVOID)h, (PVOID)p) != h );

    /* hint the previous item. And you'd better not to release the other
thread's
     * descriptor ;-)
     */
    if (h)
        h->prior = h;

    while (p->next != NULL) {
        p->state = WAITING;
        WaitForSingleObject(p->hwait, INFINITE);
    }
    p->state = RUN;
}

void Mutex::unlock()
{
    mqitem * o = thread_item;
    mqitem * p;
    BOOL rescan;

    /* check the hint */
    p = o->prior;
    if (p->next != o) {
        /* Scan the whole list, updating the hints 'prior' as well. */
        p = &e;
        while(p->next != o) {
            p->next->prior = p;
            p = (mqitem *)p->next;
        }
    }

    /* we might have to rescan the queue if no waiters yet */
    rescan = (e.next == thread_item);

    /* release the mutex */
    p->next = NULL;

    /* Now to prevent race conditions we have to rescan the list to see
     * if any other thread has appeared since we released the lock in
     * the previous line.
     * Note that we have to deal with two threads only.
     */

    if (rescan) {
    /* we could have updated 'prior' hints here, should we? */
        for(p = &e; p->next != NULL; p = (mqitem *)p->next)
            ;
    }

    if (p->waiting == this) {
        /* spin until thread decided about it's state.
         * Removing this would just cause spurious wakeups.
         */
        while (p->state == UNCERTAIN)
            ;

        if (p->state != RUN)
            ReleaseSemaphore(p->hwait, 1, NULL);
    }
}

remark wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>XP. Проц AMD. Что-то у них с lock? Я правда использовал cmpxchg без него
> H>- потому, что для однопроцессорной машины он смысла не имеет. А 15% -
> H>это в основном алгоритмическая разница — при этом обращений к ядру
> H>практически не происходило. Можно сказать, что при этом реализация
> H>работала в режиме lock-free. Не думаю, что другая операционка или проц
> H>смогли бы замедлить это время, по отношению к любой другой lock-free
> H>реализации. Худшее время, когда блокировки происходят постоянно, я тоже
> H>написал — разница в два раза — тут я могу поверить во влияние проца и
> H>операционки.
>
>
> Они на AMD, редиски, сделали, что в однопроцессорной конфигурации у них
> LOCK префикс игнорируется. По крайней мере на write-back памяти.
> Поэтому получается, что тяжёлая interlocked операция получается лёгкой.
> А на Intel процессоре ты получишь следующую картину. Допустим операция
> вставки в очередь в твоей реализации, которую ты запостил в первом
> посте, будет занимать 10 тактов — там только несколько манипуляций с
> указателями. А очередь использующая Interlocked будет — 110 тактов = 10
> вставить в очередь + 100 тактов LOCK CMPXCHG....
>

Так я и думал. Чтобы покопаться с зависимостями от SMP (предположив, что
XP идет в SMP и UNP конфигурациях, как и NT4 и w2k), написал CAS в виде
ассемблерной вставки и заметил, что нет разницы между наличием и
отсутствием LOCK. Значит, это только у AMD... Будем знать.
Это, кстати, было одной из причин, почему я специально отмечал
однопроцессорную машину.

hexis wrote:
>
> Вот что получилось:
>

Есть неоптимальность — первый поток оканчивает rescan в unlock() и
вытесняется; второй поток блокирует (без ожидания), разблокирует; третий
поток блокирует; второй запрашивает блокировку; первый просыпается и
будит второй поток. Который, правда, тут-же вернется в состояние
ожидания. Лечится заменой waiting с указателя на объект, на указатель на
поток (несбрасываемый дубликат поля next) и обработкой его в unlock.
Кстати, мне непонятно, насколько все это интересно — выкладывать
следующие версии или нет?

hexis wrote:
>
> Вот что получилось:
>

Есть неоптимальность — первый поток оканчивает rescan в unlock() и
вытесняется; второй поток блокирует (без ожидания), разблокирует; третий
поток блокирует; второй запрашивает блокировку; первый просыпается и
будит второй поток. Который, правда, тут-же вернется в состояние
ожидания. Лечится заменой waiting с указателя на объект, на указатель на
поток (несбрасываемый дубликат поля next) и обработкой его в unlock.
Кстати, мне непонятно, насколько все это интересно — выкладывать
следующие версии или нет?

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

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


Это уже лучше. *Теоретически* это рабочий алгоритм.
Самое интересное начнётся, когда мы переложим его в практическую плоскость. А именно вот тут нужен барьер памяти:



H> /* release the mutex */
p->>next = NULL;

#StoreLoad memory barrier

H> /* Now to prevent race conditions we have to rescan the list to see
H> * if any other thread has appeared since we released the lock in
H> * the previous line.
H> * Note that we have to deal with two threads only.
H> */

H> if (rescan) {
H> /* we could have updated 'prior' hints here, should we? */
H> for(p = &e; p->next != NULL; p = (mqitem *)p->next)
H> ;
H> }


#StoreLoad это самый дорогой тип барьера памяти. В частности на x86 для его реализации надо использовать mfence инструкцию. Сколько она занимает времени? Делаем ставки! Правильно 100 тактов, столько же сколько и инструкиция с префиксом LOCK, т.к. по большому счёту это одно и то же просто в другой форме.
Хотя в принципе есть мнения, что mfence более дружествен к SMP/multicore системам, чем LOCK, несмотря на то, что занимает столько же времени. Хотя у меня уверенности нет...

Обычно LOCK и MFENCE взаимозаменяемы. Вот например алгоритм мьютекса Петерсона:
http://en.wikipedia.org/wiki/Peterson's_algorithm
Он использует на *входе* в мьютекс MFENCE вместо LOCK.

Поэтому более правильно ставить задачу как "without atomic rmw operations or heavy memory barriers".

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

H>hexis wrote:
>>
>> Вот что получилось:
>>

H>Есть неоптимальность — первый поток оканчивает rescan в unlock() и
H>вытесняется; второй поток блокирует (без ожидания), разблокирует; третий
H>поток блокирует; второй запрашивает блокировку; первый просыпается и
H>будит второй поток. Который, правда, тут-же вернется в состояние
H>ожидания. Лечится заменой waiting с указателя на объект, на указатель на
H>поток (несбрасываемый дубликат поля next) и обработкой его в unlock.


В принципе имхо небольшая вероятность spurious wakeups не страшна, если при этом общий случай мы делаем значительно быстрее. Под значительно быстрее понимается, например, меньшее кол-во атомарных RMW операций или тяжёлых барьеров памяти.


H>Кстати, мне непонятно, насколько все это интересно — выкладывать
H>следующие версии или нет?


Мне лично очень интересно. Выкладывай.
Я сам частьенько занимаюсь выдумыванием всяких кастомных примитивов синхронизации и выкладываю на comp.programming.threads:

asymmetric rw_mutex:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6

rw_mutex with costless read_lock/unlock:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1348064e4838e871

MPSC FIFO Queue w/o atomic_rmw/membars:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/844d08c4eeb5c5d5

MPMC Unbounded FIFO Queue w/ 1 CAS/Operation:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/bf2261a78b4d3188

lock-free node allocator for fifo-queues:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/378a35b21ae2b42e

Lock-free proxy algorithm:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6cfe6b1a6926680d

Ну и так далее. К сожалению на c.p.t обычно к таким вопросам имеют интерес 1,5 человека, которых я могу назвать по именам. На Intel Threading Forum и на RSDN, к сожалению, никто...

remark wrote:
>
> Поэтому более правильно ставить задачу как "without atomic rmw
> operations or heavy memory barriers".
>

Ну тогда я выскажу следующую мысль — в заданных условиях, идеальное
решение невозможно. Обоснование такое. Рассмотрим упрощенную модель
работы mutex в приложении к двум потокам:

lock()
{
    /* barrier */
    if (!free) {
        wait = true;
        Wait();
    }
    free = false;
}

unlock()
{
    free = true;
    /* barrier */
    if (wait) {
        wait = false;
        Signal();
    }
}

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

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

Передачу информации в одну сторону можно реализовать на практике одним
из следующих способов:

1) отсутствие барьера в lock(), приведет к тому, что в результате
несколько потоков могут одновременно получить блокировку. Очевидно, что
при этом требуется проверка конфликта в unlock и откат изменений
выполненных в конфликтной ситуации. То есть схема эквивалентна, так
называемой, оптимистической блокировке. Но не эквивалентна классической
трактовке понятия мьютекса. Так, что вряд ли стоит разрабатывать эту
тему в рамках вопроса о мьютексе, хотя сама по себе она достаточно
интересна.

2) отсутствие барьера у unlock() приведет к тому, что проверка в
unlock() предиката (wait) может дать ложные результаты. Что будет
приводить к подвисанию потоков в lock(). Возможные пути решения
проблемы, пришедшие мне в голову, можно просуммировать следующим образом:

2.1) Wait не должен быть блокирующимся. Требуется, как минимум вторая
проверка, после истечения времени барьера. Это возможно двумя путями —
полное отсутствие Wait и Signal (вариант spin lock-а) или
Wait(TIMEOUT)+Wait(INFINITE). Таймаут равен времени записи в память плюс
1. Достаточно практично было бы обрабатывать опрос с таймаутом при
помощи spin опроса, но без дополнительного барьера.

2.2) Wait должен знать об ожидании на предикате. Что приводит к мысли о
futex. К сожалению — трудно уговорить производителя ОС включить в API
новый предикат.

2.3) Wait должен получать гарантированное оповещение. Для этого при
unlock() должен всегда вызываться Signal(). Вариация на тему обычного
mutex из OS, что, в данном случае, не имеет особого смысла.

2.4) Наличие помощника/посредника. unlock() может сигналить, если он
точно знает, что другая нитка ждет. И запрашивать проверку состояния по
истечении времени барьера у посредника, если предикат wait оказался
ложным. В идеале этот посредник — планировщик OS, но на практике это
может быть выделенный поток.

Перенос кода из lock() в unlock() невозможен без изменения семантики.
Но можно перенести код из unlock() в lock():

lock()
{
    /* barrier */
    if (wait > 0 && free) {
        wait++;
        Signal();
        Wait();
        wait--;
    } else if (!free) {
        wait++;
        Wait();
        wait--;
    }
    free = false;
}

unlock()
{
    /* no-barrier */
    if (wait > 0)
        Signal();
    free = true;
}

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

Примерно так. Я пока не вижу других способов решения вопроса. Из
приведенного, на мой взгляд есть два практичных решения — futex и
ожидание с таймаутом.

Соответственно, код будет выглядеть наподобие следующего (нетестированно):

struct mutex
{
    long requested;  /* количество запросов на блокировки */
    long granted;    /* количество выданных блокировок    */
    long sent;       /* количество посланных сигналов     */
    long got;        /* количество полученных сигналов    */
};

void
init(mutex * m)
{
    m->granted = 0;
    m->requested = 0;
    m->sent = 0;
    m->got  = 0;
}

void
lock(mutex * m)
{
    long mine;
    int  j;

    /* InterlockedIncrement включает в себя барьер */
    mine = InterlockedIncrement(&m->requested) - 1L;
    while (m->granted != mine) {
        for(j = 0; j < WAIT_COUNT; j++) {
            if (m->granted == mine)
                return;
        }
        Wait(m, INFINITE);
    m->got++;
    }
}

void
unlock(mutex * m)
{
    if (m->requested != ++m->granted && m->sent == m->got) {
    m->sent++;
        Signal(m);
    }
}

Вероятность spurious wakeup при такой технике значительно повышена (тем
ниже, чем ближе WAIT_COUNT к времени исполнения FENCE (задержку, кстати,
можно калибровать на старте). Соответственно, предпочтительно
использовать бинарный семафор или Event. Или же можно подсчитывать
соотношение посланных и полученных сигналов (на тех-же условиях).

Возможно не совсем в тему вопрос, но вот искал аналог InterlockedIncrement для Линукса.
Наткнулся вот на такой пример (см. второй ответ).
Насколько это будет работоспособно? Платформа х86.

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

HK>Возможно не совсем в тему вопрос, но вот искал аналог InterlockedIncrement для Линукса.
HK>Наткнулся вот на такой пример (см. второй ответ).
HK>Насколько это будет работоспособно? Платформа х86.


В принципе похоже. Это асм под gcc компилятор. Так же можешь поглядеть в библиотеках типа boost или ACE (Atomic_Op.cpp).

А вообще смотри здесь:
Built-in functions for atomic memory access
В gcc просто есть встроенные функции типа __sync_fetch_and_add() и __sync_val_compare_and_swap() — так что изобретать ничего не надо...

remark wrote:
>
> Здравствуйте, HaronK, Вы писали:
>
> HK>Возможно не совсем в тему вопрос, но вот искал аналог
> InterlockedIncrement для Линукса.
> HK>Наткнулся вот на такой пример
> <http://www.verycoder.com/programmers-archive/16/developer-tech-c++-160558.shtm&gt;
> (см. второй ответ).
> HK>Насколько это будет работоспособно? Платформа х86.
>
>
> В принципе похоже. Это асм под gcc компилятор. Так же можешь поглядеть в
> библиотеках типа boost или ACE (Atomic_Op.cpp).

Да, похоже на правду. Можно еще взять из asm/atomic.h

> А вообще смотри здесь:
> Built-in functions for atomic memory access
> <http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html#Atomic-Builtins&gt;
> В gcc просто есть встроенные функции типа __sync_fetch_and_add() и
> __sync_val_compare_and_swap() — так что изобретать ничего не надо...

Интересно, а как gcc учитывает SMP/UNP конфигурации ядра? И учитывает ли?

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

R>В принципе похоже. Это асм под gcc компилятор. Так же можешь поглядеть в библиотеках типа boost или ACE (Atomic_Op.cpp).

R>А вообще смотри здесь:
R>Built-in functions for atomic memory access
R>В gcc просто есть встроенные функции типа __sync_fetch_and_add() и __sync_val_compare_and_swap() — так что изобретать ничего не надо...

Спасибо, гляну.

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

H>remark wrote:
>>
>> Поэтому более правильно ставить задачу как "without atomic rmw
>> operations or heavy memory barriers".
>>

H>Ну тогда я выскажу следующую мысль — в заданных условиях, идеальное
H>решение невозможно.Обоснование такое. Рассмотрим упрощенную модель
H>работы mutex в приложении к двум потокам:


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

Если интересно, то можешь поглядеть следующие ссылки:
Relaxed-Locks
Это описание лока, который используется в SUN JVM. С описанием некоторых интересных деталей, типа directed-handoff vs competitive handoff, futile wakeup throttling.

Quickly Reacquirable Locks
Тут используется collocation technique. Правда фактически это замена StoreLoad барьеру памяти. Но на SPARC архитектуре StoreLoad дешевле, чем атомарные RMW операции, а эта collocation technique видимо ещё дешевле. Плохие новости состоят в том, что на x86 это работать не будет... т.е. всё равно нужен будет явный StoreLoad барьер...

Seqlock
Это уникальный лок. Он позволяет захватывать/освобождать блокировку на чтение вообще без каких-либо тяжёлых операций. Но правда подходит только для *чистого* чтения.

Asymmetric Dekker Synchronization
Это аналог моего asymmetric_rw_mutex. Идея та же — переносим всю тяжесть с блокировки на чтение на блокировку на запись.

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


H>Видно, что здесь информация передается в две стороны — от блокирующего
H>потока к разблокирующему и обратно. Из чего следует, что, для того,
H>чтобы тот процедура отработала правильно, требуется наличие барьеров.
H>Собственно проблема возникает из-за необходимости синхронизировать
H>состояние двух примитивов — самой блокировки и объекта ожидания.


Круто всё разложил по полочкам
Про передачу информации в две стороны — хорошая аналогия, точнее не аналогия, а способ анализировать алгоритм.
По поводу синхронизации 2 примитивов не согласен. Фактически тут надо синхронизировать 1 примитив — само слово блокировки, а объект ожидания является вспомогательным, т.к. он "не теряющий". Анализируя слово блокировки, разблокирующему потоку достаточно только понять, надо ему сигналить объект ожидания или нет. А когда именно он это сделает по отношению к ожидающему — не важно, хоть до того, как ожидающий заблокируется, хоть после.
Проблема в том, что без атомарной RMW в операции выхода не получается синхронизировать даже один примитив.



H>Соответственно, можно рассмотреть такие способы преодоления проблемы -
H>передача информации только в одну сторону и попытки избежать барьеров
H>путем переноса операций.

H>Передачу информации в одну сторону можно реализовать на практике одним
H>из следующих способов:

H>1) отсутствие барьера в lock(), приведет к тому, что в результате
H>несколько потоков могут одновременно получить блокировку. Очевидно, что
H>при этом требуется проверка конфликта в unlock и откат изменений
H>выполненных в конфликтной ситуации. То есть схема эквивалентна, так
H>называемой, оптимистической блокировке. Но не эквивалентна классической
H>трактовке понятия мьютекса. Так, что вряд ли стоит разрабатывать эту
H>тему в рамках вопроса о мьютексе, хотя сама по себе она достаточно
H>интересна.


Да, идея интересная. Это называется транзакционная память. Можешь гуглить по словам STM, HTM, HyTM.
Модель предоставляемая пользователю, конечно, принципиально отличается от мьютекса — надо делать ретрай, нельзя делать ничего, что было бы нельзя "откатить" и т.д.



H>2) отсутствие барьера у unlock() приведет к тому, что проверка в
H>unlock() предиката (wait) может дать ложные результаты. Что будет
H>приводить к подвисанию потоков в lock(). Возможные пути решения
H>проблемы, пришедшие мне в голову, можно просуммировать следующим образом:

H>2.1) Wait не должен быть блокирующимся. Требуется, как минимум вторая
H>проверка, после истечения времени барьера. Это возможно двумя путями -
H>полное отсутствие Wait и Signal (вариант spin lock-а) или
H>Wait(TIMEOUT)+Wait(INFINITE). Таймаут равен времени записи в память плюс
H>1. Достаточно практично было бы обрабатывать опрос с таймаутом при
H>помощи spin опроса, но без дополнительного барьера.


Я думал над этим. Ничего хорошего/практического не придумывается.
Во-первых, не понятно как определять этот TIMEOUT. Очевидно, что он сильно архитектурно зависим. Возможно он зависит от текущей загрузки системы...
А брать "заведомо достаточный" интервал, типа 10 мкс. получается бессмысленно. Ждать столько в активном спине дорого. Блокироваться лишний раз — так это мы так только сделаем операцию дороже...



H>2.2) Wait должен знать об ожидании на предикате. Что приводит к мысли о
H>futex. К сожалению — трудно уговорить производителя ОС включить в API
H>новый предикат.


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



H>2.3) Wait должен получать гарантированное оповещение. Для этого при
H>unlock() должен всегда вызываться Signal(). Вариация на тему обычного
H>mutex из OS, что, в данном случае, не имеет особого смысла.

Да.

H>2.4) Наличие помощника/посредника. unlock() может сигналить, если он
H>точно знает, что другая нитка ждет. И запрашивать проверку состояния по
H>истечении времени барьера у посредника, если предикат wait оказался
H>ложным. В идеале этот посредник — планировщик OS, но на практике это
H>может быть выделенный поток.


Опять же это что-то типа фьютекса получается.
И встаёт вопрос — в какова будет цена периодически проверять *все* критические секции в программе... И какой выбрать период...


H>Перенос кода из lock() в unlock() невозможен без изменения семантики.
H>Но можно перенести код из unlock() в lock():

H>

H>lock()
H>{
H>    /* barrier */
H>    if (wait > 0 && free) {
H>        wait++;
H>        Signal();
H>        Wait();
H>        wait--;
H>    } else if (!free) {
H>        wait++;
H>        Wait();
H>        wait--;
H>    }
H>    free = false;
H>}

H>unlock()
H>{
H>    /* no-barrier */
H>    if (wait > 0)
H>        Signal();
H>    free = true;
H>}
H>

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


Я сейчас разрабатываю event-driven систему. Такая система интересна тем, что можно гарантировать, что все потоки периодически совершают некоторую нужную активность. И в принципе я применяю похожий трюк. С небольшой вероятностью какой-то поток может что-то "пропустить", но тогда, допустим, каждые 10 событий я проверяю, а не пропустил ли кто чего.
В event-driven системе это становится затруднительнее, т.к. пользовательский поток нельзя заставить периодически выполнять некоторую активность...



H>Примерно так. Я пока не вижу других способов решения вопроса. Из
H>приведенного, на мой взгляд есть два практичных решения — futex и
H>ожидание с таймаутом.

H>Соответственно, код будет выглядеть наподобие следующего (нетестированно):

H>

H>struct mutex
H>{
H>    long requested;  /* количество запросов на блокировки */
H>    long granted;    /* количество выданных блокировок    */
H>    long sent;       /* количество посланных сигналов     */
H>    long got;        /* количество полученных сигналов    */
H>};

H>void
H>init(mutex * m)
H>{
    m->>granted = 0;
    m->>requested = 0;
    m->>sent = 0;
    m->>got  = 0;
H>}

H>void
H>lock(mutex * m)
H>{
H>    long mine;
H>    int  j;

H>    /* InterlockedIncrement включает в себя барьер */
H>    mine = InterlockedIncrement(&m->requested) - 1L;
H>    while (m->granted != mine) {
H>        for(j = 0; j < WAIT_COUNT; j++) {
H>            if (m->granted == mine)
H>                return;
H>        }
H>        Wait(m, INFINITE);
    m->>got++;
H>    }
H>}

H>void
H>unlock(mutex * m)
H>{
H>    if (m->requested != ++m->granted && m->sent == m->got) {
    m->>sent++;
H>        Signal(m);
H>    }
H>}
H>

H>Вероятность spurious wakeup при такой технике значительно повышена (тем
H>ниже, чем ближе WAIT_COUNT к времени исполнения FENCE (задержку, кстати,
H>можно калибровать на старте). Соответственно, предпочтительно
H>использовать бинарный семафор или Event. Или же можно подсчитывать
H>соотношение посланных и полученных сигналов (на тех-же условиях).


Хммм... Надо будет подумать над этим. Это что-то типа алгоритма билета, модифицированного для использования так же и блокировки — оригинальный алгоритм билета использует только спин-ожид ание.
Единственное, что сразу приходит — честные мьютексы, конечно, без сильной нужны применять накладно — т.к. они обычно очень плохо себя ведут в реальных условиях. Самое неприятное, что у них есть — handoff ownership проблема. Подробгее смотри здесь:
http://www.accu.org/index.php/journals/1324