Операционные системы. Управление ресурсами

         

"Производители-потребители"


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

Решение достигается при помощи единственного общего семафора, играющего роль счетчика числа порций в буфере (здесь и далее мы предполагаем структуру семафора, определенную в предыдущем разделе):

1 static semaphore *portCnt = { 0, 0, NULL }; 2 static ... buffer ...; 3 /* процесс-производитель */ 4 void producer ( void ) { 5 while (1) { 6 < производство порции > 7 < добавление порции в буфер > 8 V(portCnt); 9 } 10 } 11 /* процесс-потребитель */ 12 void consumer ( void ) { 13 while (1) { 14 P(portCnt) 15 < выборка порции из буфера > 16 < обработка порции > 17 } 18 }

Исходное значение семафора portCnt - 0. Производитель каждую итерацию своего цикла заканчивает V-операцией, увеличивающей значение счетчика. Потребитель каждую свою итерацию начинает P-операцией. Если буфер пуст, то потребитель задержится в своей P-операции до появления в буфере очередной порции. Таким образом, если потребитель работает быстрее производителя, он будет время от времени простаивать, если производитель работает быстрее - в буфере будут накапливаться порции.

В реальных задачах такого рода буфер всегда имеет некоторую конечную емкость. Если производитель работает быстрее, то при заполнении буфера он должен приостанавливаться, ожидая освобождения места в буфере.
Это легко обеспечить, введя новый семафор freeCnt, выполняющий роль счетчика свободных мест в буфере:

1 static semaphore *portCnt = { 0, 0, NULL }, 2 *freeCnt = { BSIZE, 0, NULL }, 3 static ... buffer [BSIZE]; 4 /* процесс-производитель */ 5 void producer ( void ) { 6 while (1) { 7 < производство порции > 8 P(freeCnt); 9 < добавление порции в буфер > 10 V(portCnt); 11 } 12 } 13 /* процесс-потребитель */ 14 void consumer ( void ) { 15 while (1) { 16 P(portCnt) 17 < выборка порции из буфера > 18 V(freeCnt); 19 < обработка порции > 20 } 21 }

Попытаемся теперь обобщить решение для произвольного числа производителей и потребителей. Но в таком обобщении мы сталкиваемся с еще одной существенной особенностью. В вышеприведенных решениях мы допускали одновременное выполнение операций <добавление порции в буфер> и <выборка порции из буфера> . Очевидно, что при любой организации буфера производитель и потребитель могут одновременно работать только с разными порциями информации. Иначе обстоит дело с многочисленными производителями и потребителями. Два производителя могут попытаться одновременно добавить порцию в буфер и выбрать для этого одно и то же место в буфере. Аналогично, два потребителя могут попытаться выбрать из буфера одну и ту же порцию. В следующем примере мы для наглядности представляем буфер в виде кольцевой очереди с элементами (порциями) одинакового размера:

1 typedef ... portion; /* порция информации */ 2 static portion buffer [BSIZE]; 3 static int wIndex = 0, rIndex = 0; 4 static semaphore *portCnt = { 0, 0, NULL }, 5 *freeCnt = { BSIZE, 0, NULL }, 6 *rAccess = { 1, 0, NULL }, 7 *wAccess = { 1, 0, NULL }; 8 /* имеется NP аналогичных процессов-производителей */ 9 void producer ( void ) { 10 portion work; 11 while (1) { 12 < производство порции в work > 13 P(wAccess); 14 P(freeCnt); 15 /* добавление порции в буфер */ 16 memcpy(buffer+wIndex,&work, sizeof(portion) ); 17 if ( ++wIndex == BSIZE ) w_index = 0; 18 V(portCnt); 19 V(wAccess); 20 } 21 } 22 /* имеется NC аналогичных процессов-потребителей */ 23 void consumer ( void ) { 24 portion work; 25 while (1) { 26 P(rAccess); 27 P(portCnt) 28 /* выборка порции из буфера */ 29 memcpy(&work, buffer+rIndex, sizeof(portion) ); 30 if ( ++rIndex == BSIZE ) rIndex = 0; 31 V(freeCnt); 32 V(rAaccess); 33 < обработка порции в work> 34 } 35 }

Мы оформляем обращения к буферу как критические секции, защищая их семафорами rAccess и wAccess. Поскольку конфликтовать (пытаться работать с одной и той же порцией в буфере) могут только однотипные процессы, мы рассматриваем буфер как два ресурса: ресурс для чтения и ресурс для записи и каждый такой ресурс защищается своим семафором. Таким образом запрещается одновременный доступ к буферу двух производителей или двух потребителей, но разрешается одновременный доступ одного производителя и одного потребителя.




Содержание раздела