Примитивы синхронизации в языках программирования
8.10. Примитивы синхронизации в языках программирования
До сих пор мы рассматривали методы, которые обеспечивают и взаимное исключение, и синхронизацию. Целый ряд прикладных задач, однако, требует только синхронизации без взаимного исключения. Отказ от последнего, если это не мешает решению задачи, всегда оправдан, так как взаимное исключение усложняет решение может снижать уровень мультипрограммирования.
Один из возможных примитивов, обеспечивающих синхронизацию без взаимного исключения, называется счетчиком событий. Счетчик событий - тип данных, представляемый неуменьшающимся целым числом с начальным значением 0. Его значение в любой момент времени - число событий определенного типа, произошедших от некоторой точки начала отсчета. Над этим типом данных возможны следующие операции:
- advance(E) - увеличение значения счетчика событий E на 1, атомарная операция;
- eread(E) - возвращает текущее значение счетчика E, эта операция не взаимоисключающая с advance, так что к моменту, когда значение попадет в читающий его процесс, текущее значение счетчика может быть уже изменено;
- await(E,value) - ждать - ожидание (блокировка процесса), пока значение счетчика E не станет большим или равным value.
Существенно, что из перечисленных операций только advance является взаимоисключающей, остальные могут выполняться параллельно друг с другом и с advance.
Вот как решается с помощью счетчиков событий задача для одного производителя и одного потребителя: 1 typedef unsigned int eventcounter; /* тип данных - счетчик событий */ 2 static eventcounter inCnt = 0, outCnt = 0; /* счетчики для чтения и записи */ 3 static portion buffer [BUFSIZE]; /* буфер */ 4 /*== процесс-потребитель ==*/ 5 void consumer ( void ) { 6 int portNum; /* номер порции */ 7 portion work; /* рабочая область порции */ 8 /* цикл потребления */ 9 for ( portNum = 1; ; portNum++ ) { 10 /* ожидание доступности порции по номеру */ 11 await (inCnt, portNum); 12 /* выборка из буфера */ 13 memcpy (&work, buffer + portNum % BSIZE, sizeof(portion) ); 14 /* продвижение счетчика записи */ 15 advance (outCnt); 16 < обработка порции в work > 17 } 18 } 19 /*== процесс-производитель ==*/ 20 void producer ( void ) { 21 int portNum; /* номер порции */ 22 portion work; /* рабочая область для порции */ 23 /* цикл производства */ 24 for ( portNum = 1; ; portNum++ ) { 25 < производство порции в work > 26 /* ожидание доступности порции по номеру */ 27 await (outCnt, portNum - BSIZE); 28 /* запись в буфер */ 29 memcpy (buffer + portNum % BSIZE, &work, sizeof(portion) ); 30 /* продвижение счетчика чтения */ 31 advance (inCnt); 32 } 33 }
Как мы уже отмечали выше, производитель и потребитель работают с разными секциями буфера, и взаимное исключение для них не требуется. Процессы - производитель и потребитель - могут перекрываться в любых своих фазах, кроме операций advance (строки 15 и 31). Переменные inCnt и outCnt являются счетчиками событий - производства порции и потребления порции соответственно. Кроме того, каждый процесс хранит в собственной локальной переменной portNum - номер порции, с которой ему предстоит работать (счет начинается с 1). Потребитель ждет, пока счетчик производств не достигнет номера очередной его порции, затем выбирает порцию из буфера и увеличивает счетчик потреблений. Производитель работает симметрично. Обратите внимание на второй параметр операции await в производителе (строка 27). Он задается таким, чтобы обеспечить отсутствие ожидания при наличии хотя бы одной свободной секции в буфере.
Другой механизм синхронизации носит название секвенсоров (sequencer). Буквальный перевод этого слова - "упорядочиватель" - так называются средства, которые выстраивают неупорядоченные события в определенном порядке. Как и счетчик событий, секвенсор представляется целым числом, над которым выполняется единственная операция: ticket. Операция ticket(S) возвращает текущее значение секвенсора и увеличивает его на 1. Операция является атомарной. Начальное значение секвенсора - 0.
Имея в своем распоряжении секвенсоры мы можем так записать решение задачи производителей-потребителей для произвольного числа процессов: 1 /* типы данных - счетчик событий и секвенсор */ 2 typedef unsigned int eventcounter; 3 typedef unsigned int sequencer; 4 static eventcounter inCnt = 0, outCnt = 0; /* счетчики для чтения и записи */ 5 /* секвенсоры для чтения и записи */ 6 static sequencer inSeq = 0, outSeq = 0; 7 static portion buffer [BUFSIZE]; /* буфер */ 8 /*== процесс-производитель ==*/ 9 void producer ( void ) { 10 int portNum; /* номер порции */ 11 portion work; /* рабочая область для порции */ 12 /* цикл производства */ 13 while (1) { 14 < производство порции в work > 15 /* получение "билета" на запись порции */ 16 portNum = ticket (inSeq); 17 /* ожидание номера порции */ 18 await (inCnt, portNum); 19 /* ожидание свободного места в буфере */ 20 await (outCnt, portNum - BSIZE+1); 21 /* запись в буфер */ 22 memcpy (buffer + portNum % BSIZE, &work, sizeof(portion) ); 23 /* продвижение счетчика чтения */ 24 advance (inCnt); 25 } 26 } 27 /*= процесс-потребитель =*/ 28 void consumer ( void ) { 29 int portNum; /* номер порции */ 30 portion work; /* рабочая область для порции */ 31 /* цикл потребления */ 32 while (1) { 33 /* получение "билета" на выборку порции */ 34 portNum = ticket (outSeq); 35 /* ожидание номера порции */ 36 await (outCnt, portNum); 37 /* ожидание появления в буфере */ 38 await (inCnt, portNum+1); 39 /* выборка порции */ 40 memcpy (&work, buffer + portNum % BSIZE, sizeof(portion) ); 41 /* продвижение счетчика записи */ 42 advance (outCnt); 43 < обработка порции в work > 44 } 45 }
Каждый производитель получает "билет" со своим номером в очереди на запись в буфер (строка 16). Затем он ожидает, когда до него дойдет очередь (строка 18), ожидает освобождения места в буфере (строка 20), записывает информацию (строки 22, 23) и наращивает счетчик производств (строка 24). Увеличение счетчика событий inCnt является сигналом к разблокированию как для потребителя, получившего "билет" на выборку этой порции и ожидающего в строке 36, так и для производителя, получившего "билет" на запись следующей порции и ожидающего в строке 20. Полученный процессом "билет" определяет и адрес в буфере той секции, с которой будет работать процесс. Хотя каждый процесс работает со своей секцией в буфере, одновременный доступ к буферу однотипных процессов исключается ожиданием в строке 18 или 36. Если разрешить одновременный доступ к буферу двух, например, производителей, то процесс, получивший "билет" на запись порции в n-ю секцию буфера может закончить запись раньше, чем процесс, пишущий порцию в n-1-ю секцию, даже если последний начал запись раньше. Процесс, закончивший запись, увеличит счетчик inCnt и выйдет из ожидания потребитель, имеющий билет на n-1-ю секцию, запись в которую еще не закончена.
