Могу ли я переключить часть тестирования и модификации в семафор ожидания / сигнала? - PullRequest
Новая
       13

Могу ли я переключить часть тестирования и модификации в семафор ожидания / сигнала?

0 голосов
/ 30 апреля 2011

Классическая none-busy-waiting версия семафоров wait() и signal() реализована, как показано ниже.В этом варианте value может быть отрицательным. 

//primitive
wait(semaphore* S)
{
    S->value--;
    if (S->value < 0)
    {
        add this process to S->list;
        block();
    }
}

//primitive
signal(semaphore* S)
{
    S->value++;
    if (S->value <= 0)
    {
        remove a process P from S->list;
        wakeup(P);
    }
}

Вопрос : Правильна ли следующая версия?Здесь я сначала проверяю и изменяю значение.Здорово, если вы покажете мне сценарий, где он не работает. 

//primitive wait().
//If (S->value > 0), the whole function is atomic
//otherise, only if(){} section is atomic
wait(semaphore* S)
{
    if (S->value <= 0)
    {
        add this process to S->list;
        block();
    }
    // here I decrement the value after the previous test and possible blocking
    S->value--;
}

//similar to wait()
signal(semaphore* S)
{
    if (S->list is not empty)
    {
        remove a process P from S->list;
        wakeup(P);
    }
    // here I increment the value after the previous test and possible waking up
    S->value++;
}

Редактировать :

Моя мотивация - выяснить, могу ли я использовать этопоследняя версия для достижения взаимного исключения, без тупика, без голода.

1 Ответ

1 голос
/ 30 апреля 2011

Ваша модифицированная версия вводит условие гонки:

  • Поток A: if (S-> Value <0) // Value = 1 </li>
  • Поток B: if (S-> Value <0) // Value = 1 </li>
  • Тема A: S-> Value--; // Значение = 0
  • Тема B: S-> Значение--; // Значение = -1

Оба потока получили семафор count = 1. К сожалению. Обратите внимание, что есть еще одна проблема, даже если они не выгружаются (см. Ниже), но для полноты рассмотрим атомарность и работу реальных протоколов блокировки.

При работе с такими протоколами очень важно точно определить, какие атомарные примитивы вы используете. Атомарные примитивы таковы, что они, кажется, выполняются мгновенно, без чередования с какими-либо другими операциями. Вы не можете просто взять большую функцию и назвать ее атомарной; Вы должны сделать атомарным, используя другие атомарные примитивы.

Большинство процессоров предлагают примитив, называемый «атомарное сравнение и обмен». Я сокращу это cmpxchg с этого момента. Семантика выглядит так: 

bool cmpxchg(long *ptr, long old, long new) {
    if (*ptr == old) {
        *ptr = new;
        return true;
    } else {
        return false;
    }
}

cmpxchg не не реализовано с этим кодом. Он находится в аппаратном обеспечении процессора, но ведет себя примерно так, только атомарно.

Теперь давайте добавим к этому некоторые дополнительные полезные функции (построенные из других примитивов):

  • add_waitqueue (waitqueue) - устанавливает состояние нашего процесса в спящий режим и добавляет нас в очередь ожидания, но продолжает выполнение (ATOMIC)
  • schedule () - Переключать темы. Если мы находимся в спящем состоянии, мы не бежим снова, пока не пробудимся (БЛОКИРОВКА)
  • remove_waitqueue (waitqueue) - удаляет наш процесс из очереди ожидания, а затем устанавливает наше состояние в пробужденное, если оно еще не (ATOMIC)
  • memory_barrier () - гарантирует, что любые операции чтения / записи до этой точки фактически выполняются до этой точки , избегая проблем с упорядочением памяти (мы будем предполагать, что все другие элементарные примитивы поставляются со свободным барьером памяти , хотя это не всегда так) (CPU / COMPILER PRIMITIVE)

Вот как будет выглядеть типичная процедура получения семафора. Это немного сложнее, чем ваш пример, потому что я явно указал, какие атомарные операции я использую: 

void sem_down(sem *pSem)
{
    while (1) {
        long spec_count = pSem->count;
        read_memory_barrier(); // make sure spec_count doesn't start changing on us! pSem->count may keep changing though
        if (spec_count > 0)
        {
            if (cmpxchg(&pSem->count, spec_count, spec_count - 1)) // ATOMIC
                return; // got the semaphore without blocking
            else
                continue; // count is stale, try again
        } else { // semaphore count is zero
            add_waitqueue(pSem->wqueue); // ATOMIC
            // recheck the semaphore count, now that we're in the waitqueue - it may have changed
            if (pSem->count == 0) schedule(); // NOT ATOMIC
            remove_waitqueue(pSem->wqueue); // ATOMIC
            // loop around again to try to acquire the semaphore
        }
    }
}

Вы заметите, что фактический тест для ненулевого pSem->count в реальной функции semaphore_down выполняется cmpxchg. Вы не можете доверять любому другому чтению; значение может измениться сразу после прочтения значения. Мы просто не можем разделить проверку значения и изменение значения.

spec_count здесь спекулятивный . Это важно. По сути, я делаю предположение о том, каким будет счет. Это довольно хорошее предположение, но это предположение. cmpxchg потерпит неудачу, если мое предположение неверно, и в этот момент процедура должна пройти цикл и повторить попытку. Если я угадаю 0, то я либо проснусь (так как он перестанет быть нулевым, пока я нахожусь в очереди ожидания), либо я замечу, что это больше не ноль в тесте по расписанию.

Следует также отметить, что невозможно создать функцию, которая содержит атомарную операцию блокировки. Это бессмысленно. По определению атомарные функции, по-видимому, выполняются мгновенно, а не чередуются с чем-либо еще. Но блокирующая функция по определению ожидает, что произойдет что-то еще. Это противоречиво. Аналогично, ни одна атомарная операция не может быть «разделена» на блокирующую операцию, как в вашем примере.

Теперь, вы можете избавиться от многих из этих сложностей, объявив функцию не выгружаемой. Используя блокировки или другие методы, вы просто гарантируете, что одновременно выполняется только один поток (не включая блокировку) в коде семафора за раз. Но проблема все еще остается тогда. Начните со значения 0, где C дважды опустил семафор, затем:

  • Поток A: if (S-> Value <0) // Value = 0 </li>
  • Тема A: Блок ....
  • Поток B: if (S-> Value <0) // Value = 0 </li>
  • Тема B: Блок ....
  • Поток C: S-> Value ++ // value = 1
  • Тема C: пробуждение (A)
  • (поток C снова вызывает сигнал ())
  • Поток C: S-> Value ++ // value = 2
  • Тема C: пробуждение (B)
  • (Тема C вызывает wait ())
  • Поток C: if (S-> Value <= 0) // Value = 2 </li>
  • Поток C: S-> Value-- // Value = 1
  • // A и B были разбужены
  • Поток A: S-> Value-- // Value = 0
  • Поток B: S-> Value-- // Value = -1

Возможно, вы могли бы исправить это с помощью цикла, чтобы перепроверить S-> value - снова, предполагая, что вы находитесь на однопроцессорной машине, и ваш семафорный код выгружается. К сожалению, эти предположения ложны на всех настольных ОС:)

Для получения дополнительной информации о работе реальных протоколов блокировки, вас может заинтересовать статья " Fuss, Futexes и Furwocks: Быстрая блокировка на уровне пользователя в Linux "

...