Пересыхающие озера, описанные в примере к Работе N13, превращаются в россыпь луж, каждая из которых подпитывается умирающим родником. Стадо Слонов подходит к такой россыпи и разбредается по ней: каждый Слон выбирает себе свободную лужу и пьет из нее. Луж хватает на все стадо с избытком. Опустошив лужу, Слон переходит к следующей луже (незанятой и наполненной). Если таких луж нет, Слон ждет. Оставленная Слоном лужа тем временем наполняется.

В программной модели "россыпь луж" представлена массивом байтов pool, состоящим из 48 элементов. Каждый Слон представлен в программной модели отдельной нитью, в которой для каждого Слона выполняется одна и та же процедура - функция elephant8. Код этой процедуры моделирует поиск подходящей лужи и потребление воды. Еще одну нить с отличной от них процедурой выполнения составляет Ганеша - функция main. Код этой процедуры моделирует наполнение луж.

Массив pool доступен для всех нитей процесса, поэтому требуется синхронизация работы нитей при их доступе к этому массиву. Мы применяем комбинацию синхронизации данными с не вполне строгой реализацией монитора Хоара.

Синхронизация по данным состоит в том, что каждый элемент массива pool может принимать одно из трех значений, и эти значения индицируют его состояние:

• 0 - лужа пуста;
• 1 - лужа полна и свободна;
• -1 - лужа занята Слоном.

Нить, желающая выполнить какую-либо операцию над элементом массива, сначала проверяет его состояние и, если состояние элемента несовместимо с выполняемой операцией, выбирает для выполнения операции другой, подходящий элемент. Поиск подходящего элемента состоит в переборе элементов от того, который первоначально был выбран для выполнения операции в направлении увеличения индексов, с переходом в начало массива при достижении его конца.

Над элементами массива возможны операции трех видов:

• el_alloc - выделение: лужа "выделяется" Слону, эта операция изменяет значение соответствующего элемента из 1 в -1; если исходное значение элемента отлично от 1, элемент "не подходит" для выполнения операции;
• el_free - освобождение: лужа "опустошается" Слоном, эта операция изменяет значение соответствующего элемента из -1 в 0; если исходное значение элемента отлично от -1, элемент "не подходит" для выполнения операции; вариант "неподходящей" лужи, однако, не актуален, так как Слон может знать, какую лужу он освобождает;

  el_full - наполнение: лужа "наполняется" водой, эта операция изменяет значение соответствующего элемента из 0 в 1; если исходное значение элемента отлично от 0, элемент "не подходит" для выполнения операции.

Сами по себе операции, изменяющие состояние элемента массива не требуют много времени, поэтому они могут выполняться в режиме взаимного исключения. Все эти операции вынесены в отдельные процедуры. Эти процедуры вместе с самим массивом pool и составляют монитор: объединение ресурса и операций, работающих с ним. Все потоки выполняют изменения в массиве pool, только обращаясь к процедурам монитора. "Нестрогость" реализации монитора состоит в том, что его данные и коды не инкапсулированы в отдельном модуле и, в принципе, доступны для всех нитей напрямую (хотя последние и не пользуются этой доступностью).

Для обеспечения взаимного исключения процедур монитора потребуется исключающий семафор (назовем его mutex). Значение семафора 1 говорит о доступности монитора, значение 0 - о том, что монитор занят. Процедура монитора, таким образом, должна начинаться с операции P(mutex) и заканчиваться операцией V(mutex).

Однако, одного семафора оказывается недостаточно. Представим себе такую ситуацию: нить входит в процедуру el_alloc и выполняет операцию P(mutex), а затем пытается выполнить операцию выделения, но во всем массиве pool не находится элемента, "подходящего" для выполнения такой операции (все лужи либо пусты, либо заняты). Наша нить, таким образом, зациклится в опросе элементов массива pool, причем этот цикл будет бесконечным, так как состояние массива измениться не может. Нить, которая ответственна за наполнение луж, не сможет войти в монитор, так как вход в него заблокирован операцией P(mutex), выполненной нашей нитью.

Чтобы избежать такого тупика, мы вводим общий семафор count, выполняющий роль счетчика числа наполненных и свободных луж. Операция P(count) выполняется при выделении, операция V(count) при освобождении. Вход в операцию выделения, таким образом, защищается операцией P(count), т.е., нить может претендовать на выделение только в том случае, если есть подходящие для этого элементы массива. Если же таких элементов нет, то нить этой операцией переводится в ожидание еще до выполнения ею операции P(mutex) и, следовательно, она не успевает заблокировать вход в монитор.

Алгоритмы выполнения основных процедур модели, таким образом, следующие:

Процедура main моделирует поведение Ганеши:

1. Создание и инициализация необходимых семафоров. Заполнение массива pool значениями "1" (Слоны должны найти свой водопой уже наполненным.) Установка "будильника" на интервал 30 сек.
2. Порождение нитей-Слонов, для каждого Слона исходный индекс используемой им в настоящий момент лужи устанавливается -1.
3. Вхождение в цикл, в каждой итерации которого: выполняется задержка, соответствующая "набору" очередной порции; выполняется операция el_full.
4. Выход из цикла происходит после получения сигнала будильника. Все нити, не завершившие своего выполнения принудительно прекращаются.

Процедура elepfant8 моделирует поведение Слона:

1. Определение своей потребности.
2. Вхождение в цикл, в каждой итерации которого:
   • выполняется операция el_alloc - получение очередной лужи, этой процедуре передается индекс последней обработанной лужи;
   • индекс, который возвращает операция el_alloc запоминается как индекс обработанной последней лужи;
   • выполняется задержка, соответствующая "набору" очередной порции;
   • выполняется операция el_free - освобождение пустой лужи;
   • уменьшается на 1 потребность.
3. Выход из цикла происходит при полном удовлетворении своей потребности. Нить после этого завершается.

Процедура el_alloc является процедурой монитора и выполняется в контексте различных нитей-Слонов. В ней:

1. Выполняется операция P(count); если счетчик доступных луж - 0, нить, выполняющая процедуру, переводится в ожидание.
2. Выполняется операция P(mutex); если какая-либо другая нить в это время находится в мониторе, нить, выполняющая, процедуру переводится в ожидание.
3. Увеличивается на единицу индекс, полученный процедурой в качестве параметра (с учетом кольцевой обработки массива).
4. Если элемент массива по этому индексу "не подходит" для операции выделения, повторяются пп.3, 4.
5. В элемент массива pool по получившемуся индексу записывается -1.
6. Выполняется операция V(mutex).
7. Процедура возвращает получившийся индекс.

Процедура el_free является процедурой монитора и выполняется в контексте различных нитей-Слонов. В ней:

1. Выполняется операция P(mutex); если какая-либо другая нить в это время находится в мониторе, нить, выполняющая, процедуру переводится в ожидание.
2. В элемент массива pool по индексу - параметру процедуры записывается 0.
3. Выполняется операция V(mutex).

Процедура el_full является процедурой монитора и выполняется в контексте различных нити-Ганеши. В ней:

1. Выполняется операция P(mutex); если какая-либо другая нить в это время находится в мониторе, нить, выполняющая, процедуру переводится в ожидание.
2. Увеличивается на 1 индекс, полученный процедурой в качестве параметра.
3. Если элемент массива по этому индексу "не подходит" для операции заполнения, повторяются пп.2, 3.
4. В элемент массива pool по получившемуся индексу записывается -1.
5. Выполняется операция V(count).
6. Выполняется операция V(mutex).
7. Цикл пп. 2, 3 прерывается.
8. Если в цикле пп. 2, 3 сделан полный круг по массиву, цикл прерывается, индекс уменьшается на 1.
9. Процедура возвращает получившийся индекс.

Вся программная модель реализована в одном модуле - ganesha8.c:

Программный модуль (ganesha8.c ) .

В программе используються следующие вызовы:

• signal()
• pthread_mutex_init()
• sem_init()
• pthread_create()
• alarm()
• pthread_cancel()
• pthread_mutex_lock()
• sem_post()
• pthread_mutex_unlock()
• sem_wait()
• sem_getvalue()
• pthread_exit()
• pthread_joine()

Ниже приводится пример выполнения этой модели

11:38:26.754 - Начало работы 11:38:26.757 Слон Tandy потребность - 14, буфер - 0 11:38:26.758 Слон Aun потребность - 24, буфер - 1 11:38:26.759 Слон Assam потребность - 168, буфер - 2 11:38:26.760 Слон Maya потребность - 92, буфер - 3 11:38:26.761 Слон BakZap потребность - 101, буфер - 4   11:38:26.762 Слон Hao потребность - 51, буфер - 5 11:38:26.763 Слон Hathy потребность - 238, буфер - 6 11:38:26.763 Слон Kitty потребность - 45, буфер - 7 11:38:26.810 Слон BakZap потребность - 100, буфер - 8 11:38:26.820 Слон Assam потребность - 167, буфер - 9 11:38:26.820 Слон Hathy потребность - 237, буфер - 10 11:38:26.830 Заполнен буфер 2 11:38:26.830 Слон Maya потребность - 91, буфер - 11 11:38:26.850 Заполнен буфер 3 11:38:26.860 Слон BakZap потребность - 99, буфер - 12 11:38:26.880 Заполнен буфер 4 11:38:26.880 Слон Hathy потребность - 236, буфер - 13 11:38:26.890 Слон Assam потребность - 166, буфер - 14 11:38:26.900 Слон Maya потребность - 90, буфер - 15 11:38:26.910 Заполнен буфер 6 11:38:26.910 Слон BakZap потребность - 98, буфер - 16 11:38:26.920 Слон Hao потребность - 50, буфер - 6 11:38:26.930 Заполнен буфер 8 11:38:26.940 Слон Hathy потребность - 235, буфер - 17 11:38:26.960 Слон Assam потребность - 165, буфер - 18 11:38:26.960 Слон BakZap потребность - 97, буфер - 19 11:38:26.970 Слон Maya потребность - 89, буфер - 20 11:38:26.980 Слон Kitty потребность - 44, буфер - 8 11:38:27.000 Заполнен буфер 9 11:38:27.000 Слон Hathy потребность - 234, буфер - 21 11:38:27.010 Слон BakZap потребность - 96, буфер - 22 11:38:27.030 Слон Assam потребность - 164, буфер - 23 11:38:27.040 Слон Maya потребность - 88, буфер - 24 11:38:27.060 Слон BakZap потребность - 95, буфер - 25 11:38:27.060 Слон Hathy потребность - 233, буфер - 26 11:38:27.070 Заполнен буфер 10 11:38:27.080 Слон Hao потребность - 49, буфер - 9 11:38:27.100 Слон Assam потребность - 163, буфер - 27 11:38:27.110 Слон BakZap потребность - 94, буфер - 28 11:38:27.110 Слон Maya потребность - 87, буфер - 29 11:38:27.120 Заполнен буфер 11 11:38:27.120 Слон Hathy потребность - 232, буфер - 30 11:38:27.160 Слон BakZap потребность - 93, буфер - 31 11:38:27.170 Слон Assam потребность - 162, буфер - 32 11:38:27.180 Слон Maya потребность - 86, буфер - 33 11:38:27.180 Слон Hathy потребность - 231, буфер - 34 11:38:27.200 Заполнен буфер 12 11:38:27.200 Слон Kitty потребность - 43, буфер - 10 11:38:27.210 Слон BakZap потребность - 92, буфер - 35 11:38:27.240 Слон Assam потребность - 161, буфер - 36 11:38:27.240 Слон Hao потребность - 48, буфер - 11 11:38:27.240 Слон Hathy потребность - 230, буфер - 37 11:38:27.250 Заполнен буфер 13 11:38:27.250 Слон Maya потребность - 85, буфер - 38 11:38:27.260 Слон BakZap потребность - 91, буфер - 39 11:38:27.270 Слон Aun потребность - 23, буфер - 2 11:38:27.290 Заполнен буфер 14 11:38:27.300 Слон Hathy потребность - 229, буфер - 40 11:38:27.310 Слон Assam потребность - 160, буфер - 41 11:38:27.310 Слон BakZap потребность - 90, буфер - 42 11:38:27.320 Слон Maya потребность - 84, буфер - 43 11:38:27.360 Слон BakZap потребность - 89, буфер - 44 11:38:27.360 Слон Hathy потребность - 228, буфер - 45 11:38:27.370 Заполнен буфер 15 11:38:27.380 Слон Assam потребность - 159, буфер - 46 11:38:27.390 Слон Maya потребность - 83, буфер - 47 11:38:27.400 Слон Hao потребность - 47, буфер - 12 11:38:27.410 Заполнен буфер 16 11:38:27.410 Слон BakZap потребность - 88, буфер - 3 11:38:27.420 Слон Hathy потребность - 227, буфер - 4 11:38:27.420 Слон Kitty потребность - 42, буфер - 13 11:38:27.430 Слон Tandy потребность - 13, буфер - 14 11:38:27.450 Заполнен буфер 17 11:38:27.450 Слон Assam потребность - 158, буфер - 15 11:38:27.460 Слон BakZap потребность - 87, буфер - 16 11:38:27.460 Слон Maya потребность - 82, буфер - 17 11:38:27.510 Заполнен буфер 18 11:38:27.510 Слон Hathy потребность - 226, буфер - 18 11:38:27.550 Заполнен буфер 19 11:38:27.550 Слон BakZap потребность - 86, буфер - 19 11:38:27.620 Заполнен буфер 20 11:38:27.620 Слон Assam потребность - 157, буфер - 20 11:38:27.650 Заполнен буфер 21 11:38:27.650 Слон Maya потребность - 81, буфер - 21 11:38:27.730 Заполнен буфер 22 11:38:27.730 Слон Hao потребность - 46, буфер - 22 11:38:27.750 Заполнен буфер 23 11:38:27.750 Слон Hathy потребность - 225, буфер - 23 11:38:27.800 Заполнен буфер 24 11:38:27.800 Слон BakZap потребность - 85, буфер - 24 11:38:27.840 Заполнен буфер 25 11:38:27.840 Слон Kitty потребность - 41, буфер - 25 11:38:27.870 Заполнен буфер 26 11:38:27.870 Слон Assam потребность - 156, буфер - 26 11:38:27.900 Заполнен буфер 27 11:38:27.900 Слон Maya потребность - 80, буфер - 27 11:38:27.970 Заполнен буфер 28 11:38:27.970 Слон Aun потребность - 22, буфер - 28 11:38:27.990 Заполнен буфер 29 11:38:27.990 Слон Hathy потребность - 224, буфер - 29 11:38:28.050 Заполнен буфер 30 11:38:28.050 Слон BakZap потребность - 84, буфер - 30 11:38:28.070 Заполнен буфер 31 11:38:28.070 Слон Hao потребность - 45, буфер - 31 11:38:28.130 Заполнен буфер 32 11:38:28.130 Слон Assam потребность - 155, буфер - 32 11:38:28.170 Заполнен буфер 33 11:38:28.170 Слон Maya потребность - 79, буфер - 33 11:38:28.220 Заполнен буфер 34 11:38:28.220 Слон Hathy потребность - 223, буфер - 34 11:38:28.260 Заполнен буфер 35 11:38:28.260 Слон Kitty потребность - 40, буфер - 35 11:38:28.310 Заполнен буфер 36 11:38:28.310 Слон BakZap потребность - 83, буфер - 36 11:38:28.370 Заполнен буфер 37 11:38:28.370 Слон Tandy потребность - 12, буфер - 37 11:38:28.430 Заполнен буфер 38 11:38:28.430 Слон Assam потребность - 154, буфер - 38 11:38:28.490 Заполнен буфер 39 11:38:28.490 Слон Hao потребность - 44, буфер - 39 11:38:28.540 Заполнен буфер 40 11:38:28.540 Слон Maya потребность - 78, буфер - 40 11:38:28.590 Заполнен буфер 41 11:38:28.590 Слон Hathy потребность - 222, буфер - 41 11:38:28.610 Заполнен буфер 42 11:38:28.610 Слон BakZap потребность - 82, буфер - 42 11:38:28.660 Заполнен буфер 43 11:38:28.660 Слон Kitty потребность - 39, буфер - 43 11:38:28.740 Заполнен буфер 44 11:38:28.740 Слон Aun потребность - 21, буфер - 44 11:38:28.790 Заполнен буфер 45 11:38:28.790 Слон Assam потребность - 153, буфер - 45 11:38:28.830 Заполнен буфер 46 11:38:28.830 Слон Maya потребность - 77, буфер - 46 11:38:28.870 Заполнен буфер 47 11:38:28.870 Слон Hao потребность - 43, буфер - 47 11:38:28.950 Заполнен буфер 48 11:38:28.950 Слон Hathy потребность - 221, буфер - 48 11:38:29.030 Заполнен буфер 1 11:38:29.030 Слон BakZap потребность - 81, буфер - 1 11:38:29.100 Заполнен буфер 2 11:38:29.100 Слон Assam потребность - 152, буфер - 2 11:38:29.160 Заполнен буфер 3 11:38:29.160 Слон Kitty потребность - 38, буфер - 3 11:38:29.190 Заполнен буфер 4 11:38:29.190 Слон Maya потребность - 76, буфер - 4 11:38:29.250 Заполнен буфер 5 11:38:29.250 Слон Hathy потребность - 220, буфер - 5 11:38:39.820 Слон Tandy завершился 11:38:45.160 Слон Aun завершился 11:38:46.000 Слон Hao завершился 11:38:46.340 Слон Kitty завершился 11:38:50.270 Слон Maya завершился 11:38:51.030 Слон BakZap завершился 11:38:56.760 Слон Assam погиб 11:38:56.760 Слон Hathy погиб