Пустой элемент в ограниченном буфере на основе массива

Question

У меня классическая проблема производителя / потребителя. Код для производителя это:

#define BUFFER_SIZE 10
while (true) {
  /* Produce an item */
  while (( (in + 1) % BUFFER_SIZE)  == out)
  ;   /* do nothing -- no free buffers */
  buffer[in] = item;
  in = (in + 1) % BUFFER_SIZE;
}

И потребитель:

while (true) {
  while (in == out)
  ; // do nothing -- nothing to consume

  // remove an item from the buffer
  item = buffer[out];
  out = (out + 1) % BUFFER_SIZE;
  return item;
}

Это работает нормально, но проблема в том, что когда первые восемь элементов заполнены, а in=9 и out=0, производитель сидит там и не заполняет последний (девятый) элемент. Это также происходит, когда, скажем, in=4 и out=5. В любом случае один элемент остается пустым, и очередь кажется «заполненной», хотя один слот все еще пуст.

Я могу предложить несколько сложных проверок, но мне нужно знать, есть ли чистое решение для заполнения всей очереди. Я попытался увеличить сначала, а затем вставить item, но это также сталкивается с аналогичными проблемами. (Инициализация с -1 для in и out также не работает).

Answer 1

На уроке по разработке ОС в колледже у меня был адъюнкт-учитель, который утверждал, что невозможно иметь программное решение, которое могло бы использовать все N элементов в буфере. Я доказал, что он не прав с чем-то, что я решил назвать решением для гоночной трассы (вдохновленный тем, что мне нравится бегать по трассе).

На гоночной трассе вы не ограничены 400-метровой гонкой; гонка может состоять из более чем одного круга. Что случится, если два бегуна будут шеей и шеей в гонке? Как вы знаете, связаны ли они, или один бегун плеснул другого? Ответ прост: в гонке мы не контролируем позицию бегуна на трассе; мы отслеживаем расстояние, пройденное каждым бегуном. Таким образом, когда два бегуна являются шеей и шеей, мы можем различить между галстуком и когда один бегун имеет плескался другой.

Итак, наш алгоритм имеет массив из N элементов и управляет гонкой 2N. Мы не перезагружаем счетчик производителя / потребителя до нуля, пока они не закончат свою соответствующую гонку 2N. Мы не позволяем производителю опережать потребителя более чем на один круг, и мы не позволяем потребителю опережать производителя. На самом деле, нам нужно только отслеживать расстояние между производителем и потребителем.

Код выглядит следующим образом:

Item track[LAP];
int consIdx = 0;
int prodIdx = 0;

void consumer()
{ while(true)
  { int diff = abs(prodIdx - consIdx);
    if(0 < diff) //If the consumer isn't tied
    { track[consIdx%LAP] = null;
      prodIdx = (prodIdx + 1) % (2*LAP);
    }
  }
}

void producer()
{ while(true)
  { int diff = (prodIdx - consIdx);
    if(diff < LAP) //If prod hasn't lapped cons
    { track[prodIdx%LAP] = Item();      //Advance on the 1-lap track.
      prodIdx = (prodIdx + 1) % (2*LAP);//Advance in the 2-lap race.
    }
  }
}

Прошло много времени с тех пор, как я изначально решил проблему, так что, насколько я помню. Надеюсь, я не пропустил никаких ошибок. Надеюсь, это поможет!

Answer 2

См. Википедия по этой самой теме. Самыми простыми решениями являются:

• Всегда оставляйте один слот пустым: если in == out, то буфер пуст; если in == out - 1, буфер заполнен
• Заменить out на num_unread_items; выполнять простые математические операции для извлечения out из num_unread_items и in

... но есть и другие опции, связанные с подсчетом количества операций чтения и записи (либо в отдельных переменных, либо непосредственно в in и out); или отслеживание того, была ли последняя операция считыванием или записью в дополнение к текущим in и out, что позволяет устранять неоднозначность случаев с полным / пустым буфером.