В общем о семафорах! см.билет№32
Рассмотренный выше вариант взаимодействия поставщика и потребителя не накладывал никаких ограничений на последовательность заполнения/опустошения ячеек буфера. В ряде случаев для получения нужного результата последовательность заполнения буферных ячеек данными и последовательность излечения информации из буфера является важной. Справиться с поставленной проблемой помогает кольцевой буфер, который используется как многоэлементный коммуникационный буфер.
Рассмотрим задачу о кольцевом буфере более подробно. Предположим, что есть два процесса: процесс-поставщик, который помещает сообщения в разделяемый буфер, и процесс-потребитель, извлекающий сообщения из буфера. Буфер содержит очередь уже помещенных, но еще не извлеченных сообщений. Представим буфер массивом buf[n], n>1. Пусть переменная первый_для_чтения является индексом первого сообщения очереди, а переменная первый_для_заполнения – индексом первой пустой ячейки после сообщения в конце очереди (рис.3).
Для того, чтобы значения переменных первый_для_заполнения и первый_для_чтения всегда были в интервале от 0 до n-1, при их очередном вычислении используется операция «деление по модулю(взятие остатка)».
При таком представлении буфера процесс-производитель помещает в него сообщение в ячейку с индексом первый_для_заполнения, а затем определяется индекс следующей ячейки, подлежащей
заполнению:
Buf[первый_для_заполнения]=Cообщение;
первый_для_заполнения = (первый_для_заполнения+1) % n
Аналогично процесс-потребитель извлекает информацию их ячейки буфера с индексом
первый_для_чтения, а затем определяется индекс следующей ячейки, из которой будет считываться
информация:
Данные = Buf[первый_для_чтения];
первый_для_чтения = (первый_для_чтения) % n
Таким образом, решение задачи можно записать так:
Buf[n] /* массив из n элементов */
Первый_для_чтения=0; Первый_для_заполнения=0;
/* семафоры, хранящие число пустых и заполненных ячеек буфера */
Пустой=n; Полный=0;
Process Поставщик {
While(true) {
…..
создать Сообщение;
/* поместить созданную информацию в буфер */
P(Пустой);
Buf[первый_для_заполнения]=Cообщение;
первый_для_заполнения = (первый_для_заполнения+1) % n;
V(Полный);
}}
Process Потребитель {
While(true) {
/* извлечь информацию из буфера */
P(Полный);
Данные = Buf[первый_для_чтения];
первый_для_чтения = (первый_для_чтения) % n
V(Пустой);
}}
Представленное решение справедливо в том случае, когда есть только один процесс-производитель и
один процесс-потребитель. Предположим, что есть несколько процессов-производителей. Тогда при
наличии хотя бы двух свободных ячеек кольцевого буфера два процесса могли бы выполнить
операцию помещения информации в буфер. Однако, каждый из них попытался бы поместить данные в
одну и ту же ячейку буфера с индексом первый_для_заполнения. Аналогично, при наличии нескольких
процессов-потребителей по крайней мере два из них могут одновременно выполнить операцию чтения
информации из буфера, получив одно и то же сообщение.
Следовательно, фрагменты кода, связанные с помещением данных в буфер, являются критическими
секциями для процессов-производителей, связанные с извлечением данных из буфера, являются
критическими секциями для процессов-потребителей. Для окончательного решения воспользуемся
рассмотренным ранее решением задачи критической секции.
Законченное решение приведено ниже:
Buf[n] /* массив из n элементов */
Первый_для_чтения=0; Первый_для_заполнения=0;
/* семафоры, хранящие число пустых и заполненных ячеек буфера */
Пустой=n; Полный=0;
/* двоичные семафоры для организации взаимного исключения */
S_Поставщик=1; S_Потребитель=1;
Process Поставщик {
While(true) {
создать Сообщение;
/* поместить созданную информацию в буфер */
P(Пустой);
P(S_Поставщик);
Buf[первый_для_заполнения]=Cообщение;
первый_для_заполнения = (первый_для_заполнения+1) % n;
V(S_Поставщик);
V(Полный);
}}
Process Потребитель {
While(true) {
/* извлечь информацию из буфера */
P(Полный);
P(S_Потребитель);
Данные = Buf[первый_для_чтения];
первый_для_чтения = (первый_для_чтения) % n
V(S_Потребитель);
V(Пустой);
}}
