Ограниченные буферы (производитель потребитель)

Question

В проблеме с общей буферной памятью почему в буфере одновременно может быть не более (n-1) элементов.

Где 'n' - размер буфера.

Спасибо!

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;
      consIdx = (consIdx + 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

Упс, вот исправление ошибки:

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

void consumer()
{ while(true)
  { int diff = prodIdx - consIdx;         //When prodIdx wraps to 0 before consIdx,
    diff = 0<=diff? diff: diff + (2*LAP); //think in 3 Laps until consIdx wraps to 0.
    if(0 < diff) //If the consumer isn't tied
    { track[consIdx%LAP] = null;
      consIdx = (consIdx + 1) % (2*LAP);
    }
  }
}

void producer()
{ while(true)
  { int diff = prodIdx - consIdx;
    diff = 0<=diff? diff: diff + (2*LAP);
    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 3

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

Однако вы, конечно, можете иметь реализации, в которых заполнены все n слотов.Вот как все-таки определяется проблема ограниченного буфера.