основанная на futex 4-байтная блокировка одного записывающего устройства / нескольких читателей - PullRequest
Новая
       34

основанная на futex 4-байтная блокировка одного записывающего устройства / нескольких читателей

2 голосов
/ 19 октября 2010

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

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

1 Ответ

0 голосов
/ 25 июля 2016

Вы найдете мою реализацию на https://gist.github.com/smokku/653c469d695d60be4fe8170630ba8205

Идея состоит в том, что может быть только один поток, принимающий блокировку для записи (значение futex 0), блокировка может быть открыта (значение futex 1) или может быть много потоков чтения (значения futex больше 1).Поэтому значения ниже 1 (есть только один) блокируют как читателей, так и пишущих на futex, а значения выше 1 блокируют только писателей.Разблокирование потока вызывает один из ожидающих потоков, но вы должны быть осторожны, чтобы не использовать читателей, которые активируются только потоком писателя. 

#define cpu_relax() __builtin_ia32_pause()
#define cmpxchg(P, O, N) __sync_val_compare_and_swap((P), (O), (N))

static unsigned _lock = 1; // read-write lock futex
const static unsigned _lock_open = 1;
const static unsigned _lock_wlocked = 0;

static void _unlock()
{
    unsigned current, wanted;
    do {
        current = _lock;
        if (current == _lock_open) return;
        if (current == _lock_wlocked) {
            wanted = _lock_open;
        } else {
            wanted = current - 1;
        }
    } while (cmpxchg(&_lock, current, wanted) != current);
    syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
}

static void _rlock()
{
    unsigned current;
    while ((current = _lock) == _lock_wlocked || cmpxchg(&_lock, current, current + 1) != current) {
        while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) {
            cpu_relax();
            if (_lock >= _lock_open) break;
        }
        // will be able to acquire rlock no matter what unlock woke us
    }
}

static void _wlock()
{
    unsigned current;
    while ((current = cmpxchg(&_lock, _lock_open, _lock_wlocked)) != _lock_open) {
        while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) {
            cpu_relax();
            if (_lock == _lock_open) break;
        }
        if (_lock != _lock_open) {
            // in rlock - won't be able to acquire lock - wake someone else
            syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
        }
    }
}
...