Справедливый критический раздел (Linux)

Question

В многопоточном приложении Linux я использую мьютекс для критических секций.Это работает очень хорошо, за исключением вопроса справедливости.Может случиться так, что поток, покидающий критическую секцию и возвращающийся сразу же, не дает никакой другой возможности.Например,

while(true)
{
    critsect.enter();
    ... do calculations ...
    ... maybe call a blocking operation so we sleep ...
    critsect.leave();
}

может остановить любой другой поток для входа в тот же критический раздел.Mutexe несправедливы.

Есть ли решение сделать справедливый критический раздел?Я думал о добавлении очереди, чтобы критические секции выполнялись в порядке их «прибытия».В качестве альтернативы, по крайней мере, счетчик может выполнить pthread_yield () после разблокировки, если другие потоки ожидают.

Есть ли рекомендуемая практика для такого рода требований?

Answer 1

Вы можете построить FIFO «блокировку билетов» поверх мьютексов pthreads, по следующим направлениям:

#include <pthread.h>

typedef struct ticket_lock {
    pthread_cond_t cond;
    pthread_mutex_t mutex;
    unsigned long queue_head, queue_tail;
} ticket_lock_t;

#define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }

void ticket_lock(ticket_lock_t *ticket)
{
    unsigned long queue_me;

    pthread_mutex_lock(&ticket->mutex);
    queue_me = ticket->queue_tail++;
    while (queue_me != ticket->queue_head)
    {
        pthread_cond_wait(&ticket->cond, &ticket->mutex);
    }
    pthread_mutex_unlock(&ticket->mutex);
}

void ticket_unlock(ticket_lock_t *ticket)
{
    pthread_mutex_lock(&ticket->mutex);
    ticket->queue_head++;
    pthread_cond_broadcast(&ticket->cond);
    pthread_mutex_unlock(&ticket->mutex);
}

При такой схеме схема не поддерживает мьютекс низкого уровня pthreads, пока поток находится вкритическая секция, защищенная тикетом, позволяющая другим потокам присоединяться к очереди.

Answer 2

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

Так что яЯ бы посоветовал вам попытаться реструктурировать код, чтобы он не блокировал критические разделы в течение продолжительного времени.Либо с использованием другого подхода в целом (часто рекомендуется передавать объекты через очередь сообщений, потому что это легко сделать правильно), либо, по крайней мере, делая большую часть вычислений для локальных переменных, не удерживая блокировку, а затем просто применяя блокировку для сохранения результатов.Если блокировка удерживается в течение более коротких периодов времени, потоки будут тратить меньше времени на ее ожидание, что, как правило, повышает производительность и делает беспристрастность беспроблемной.Вы также можете попытаться увеличить степень детализации блокировки (блокировать меньшие объекты отдельно), что также уменьшит конкуренцию.

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

Answer 3

ИМХО вы можете использовать FIFO SCHEDULER в Linux и изменить приоритет потоков:

thread_func() {
    ... 
    pthread_t t_id = pthread_self();
    struct sched_param prio_zero, prio_one;
    prio_zero.sched_priority = sched_get_priority_min(SCHED_FIFO);
    prio_one.sched_priority = sched_get_priority_min(SCHED_FIFO) + 1;
    phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
    ...
    while(true)
    {
        ... Doing something before
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_one);
        critsect.enter();
        ... do calculations ...
        ... maybe call a blocking operation so we sleep ...
        critsect.leave();
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
        ... Do something after
    }
}

Answer 4

ОК, как на счет этого:

while(true)
{
    sema.wait;
    critsect.enter();
    sema.post;
    ... do calculations ...
    ... maybe call a blocking operation so we sleep ...
    critsect.leave();
}

Init. количество семафоров равно 1. Пусть другие потоки также ждут семафор, прежде чем пытаться получить CS и сигнализировать об этом, когда это будет сделано. Если поток «вычисления» получает sema, он может добраться до CS и заблокировать его. Оказавшись внутри замка, но перед длинным парашютом, сигнализируется sema, и тогда еще один поток может достигнуть CS, но не попасть внутрь него. Когда поток «вычисления» выходит из блокировки, он не может зацикливаться и снова блокировать его из-за sema. Счетчик равен нулю, поэтому другой поток получает блокировку. Поток «вычисления» должен ждать в sema до тех пор, пока другой поток, который вошел в систему, не завершит свой доступ и не выдаст сигнал sema.

Таким образом, другой поток может «зарезервировать» доступ к данным, даже если он еще не может их получить.

Rgds, Martin

Answer 5

Если ваша претензия верна (у меня нет времени на чтение, и кажется, что вы исследовали ее до публикации вопроса), я предлагаю

 sleep(0);

явно датьмежду критическими секциями.

while(true)
{
    critsect.enter();
    ... do calculations ...
    ... maybe call a blocking operation so we sleep ...
    critsect.leave();
    sleep(0);
}