пользователей: 21251
предметов: 10459
вопросов: 177801
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Семафоры и семафорные примитивы. Задача «производители-потребители» с использованием кольцевого буфера.

В общем о семафорах! см.билет№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(Пустой);

}


15.06.2014; 14:46
хиты: 219
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь