Пример приоритетного правила
5.1. Пример приоритетного правила
В ¬4.3 мы использовали общий семафор для организации взаимодействия производителя и потребителя через ограниченный буфер. Предложенное решение легко обобщается на большее число производителей и (или) потребителей; оно применимо в случае, когда "порция" на буфере является к тому же и удобной единицей информации, т. е. когда можно считать, что все порции одинакового размера.
В настоящей задаче мы рассмотрим производителей, которые выдают порции различного размера, и предположим, что размер каждой из этих порций выражается в некоторых единицах. Потребители опять будут обрабатывать последовательные порции из буфера, а потому должны уметь обрабатывать порции, размер которых заранее не задан. Максимальный размер порции пусть будет, однако, известен.
Итак, размер порции задается в единицах информации; предполагаем также, что в единицах информации определяется и максимальная емкость буфера. Тогда вопрос о том, можно ли разместить на буфере очередную выработанную порцию, зависит от размера этой порции. Требования осуществимости операций "добавление порции к буферу" и "взятие порции из буфера" означают, что размер буфера не меньше размера максимальной порции.
Наш буфер ограничен, и поэтому может оказаться, что производитель должен ждать, пока он сможет поместить в буфер созданную порцию. При порциях фиксированного размера это случалось только тогда, когда буфер был полон; теперь это может происходить из-за того, что имеющегося на буфере свободного места недостаточно для размещения данной порции.
Кроме того, если имеется более одного производителя и какой-то из них ждет из-за отсутствия достаточного места на буфере, то другие производители вполне могут продолжать работу и достигнуть точки, когда они желают выдать выработанную порцию. Предлагаемая порция от нового производителя также может быть слишком велика, но она может быть и достаточно мала, чтобы поместиться на свободном месте буфера. Мы наложим на искомое решение требование, до некоторой степени произвольное, о том, что производитель, предлагающий большую порцию, получает приоритет над производителем, предлагающим меньшую порцию. (Когда два или больше производителей предлагают порции одинакового размера, нам безразлично, кто добавит порцию к буферу.)
Если какой-то производитель находится в состоянии ожидания, потому что его порцию нельзя разместить на буфере, то никакой другой производитель не сможет добавить свою порцию к буферу впредь до момента появления дополнительного свободного места: во-первых, другой производитель не сможет сделать это у если его порция больше (так как ее негде поместить); во-вторых, - ему не разрешено это делать, если его порция меньше, так как тогда он имеет более низкий приоритет и должен уступить буфер предыдущему запросу.
Рассмотрим момент, когда буфер полностью заполнен, и три производителя ожидают возможности добавить порции размером 1, 2 и 3 соответственно. Если теперь потребитель обработает порцию в пять единиц, то правило приоритетов будет означать, что получат возможность продолжать работу производители с порциями в 3 и 2 единицы, а не производитель с порцией в 1 единицу. Но это не означает, что в данном случае порция в 3 единицы будет действительно выдана раньше порции в 2 единицы.
Сейчас мы попытаемся ввести так называемые "переменные состояния" для различных элементов системы, с помощью которых мы сможем описывать состояния системы в любой момент времени.
Для каждого производителя вводим переменную с именем "желание"; эта переменная будет обозначать число единиц буфера, необходимых для размещения порции, которая не могла быть добавлена к буферу. Так как значение этой переменной всегда есть положительное число, мы можем придать соотношению "желание = 0" тот смысл, что у данного производителя нет неудовлетворенного требования на добавление порции. Кроме того, для каждого производителя введем двоичный "семафор производителя".
Для буфера мы вводим двоичный семафор "работбуф" - работа с буфером, который предназначается для взаимного исключения действий с буфером в широком смысле (т. е. не только добавление и взятие порций из буфера, но также проверка и модификация связанных с буфером переменных состояния).
Далее, мы нуждаемся в механизме сигнализации потребителям о появлении следующей порции.Как только в буфер добавлена новая порция, она может быть обработана; и поскольку нам безразлично, какой из потребителей возьмет ее, то для этого можно воспользоваться общим семафором "число порций в буфере". (Отметим, что он указывает число порций, а не число заполненных единиц информации в буфере.)
Об освобождении областей буфера необходимо сообщать производителям, но возможные последствия освобождения областей буфера вызывают более сложные решения, и нельзя ожидать, что общий семафор будет здесь подходящим средством. Попробуем ввести для этих целей целочисленную переменную состояния "число свободных единиц буфера". Отметим, что эта переменная отсчитывает единицы информации, а не порции.
