Пример выполнения лабораторной работы


Готовый проект с откомпилированным кодом вы можете скачать здесь:)

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

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

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

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

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

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

Сами по себе операции, изменяющие состояние элемента массива не требуют много времени, поэтому они могут выполняться в режиме взаимного исключения. Все эти операции вынесены в отдельные процедуры. Эти процедуры вместе с самим массивом 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. Вхождение в цикл, в каждой итерации которого:
  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 ) .

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

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

  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 погиб 


 

© life-prog.ru