Задача об обедающих философах

В предыдущем разделе было показано, как использовать семафоры для решения задачи критической секции. В этом и следующем разделах на основе этого решения строится реали­зация выборочного взаимного исключения для двух классических задач: об обедающих фило­софах и о читателях и писателях. Решение задачи об обедающих философах иллюстрирует реализацию взаимного исключения между процессами, конкурирующими за доступ к пере­секающимся множествам разделяемых переменных, а читателей и писателей — реализацию комбинации параллельного и исключительного доступа к разделяемым переменным. В уп­ражнениях есть дополнительные задачи выборочного взаимного исключения.

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

4.1) Задача об обедающих философах. Пять философов сидят возле круглого стола. Они про­водят жизнь, чередуя приемы пищи и размышления. В центре стола находится большое блюдо спагетти. Спагетти длинные и запутанные, философам тяжело управляться с ни­ми, поэтому каждый из них, чтобы съесть порцию, должен пользоваться двумя вилками. К несчастью, философам дали всего пять вилок. Между каждой парой философов лежит одна вилка, поэтому они договорились, что каждый будет пользоваться только теми вил­ками, которые лежат рядом с ним (слева и справа). Задача — написать программу, моде­лирующую поведение философов. Программа должна избегать неудачной (и в итоге ро­ковой) ситуации, в которой все философы голодны, но ни один из них не может взять обе вилки — например, когда каждый из них держит по одной вилке и не хочет отдавать ее.

Задача проиллюстрирована на рис. 4.1. Ясно, что два сидящих рядом философа не могут есть одновременно. Кроме того, раз вилок всего пять, одновременно могут есть не более, чем двое философов.

Предположим, что периоды раздумий и приемов пищи различны — для их имитации в программе можно использовать генератор случайных чисел. Проимитируем поведение фи­лософов следующим образом.
140                                               Часть 1. Программирование с разделяемыми переменными
process Philosopher[i  =  0  to 4]   { while   (true)   { поразмыслить; взять вилки; поесть -, отдать вилки; } }
Для решения задачи нужно запрограммировать операции "взять вилки" и "отдать (освободить) вилки". Вилки являются разделяемым ресурсом, поэтому сосредоточимся на их взятии и освобождении. (Можно решать эту задачу, отслеживая, едят ли философы; см. уп­ражнения в конце главы.)
Каждая вилка похожа на блокировку критической секции: в любой момент времени вла­деть ею может только один философ. Следовательно, вилки можно представить массивом се­мафоров, инициализированных значением 1. Взятие вилки имитируется операцией Р для со­ответствующего семафора, а освобождение — операцией V.
Процессы, по существу, идентичны, поэтому естественно предполагать, что они выпол­няют одинаковые действия. Например, каждый процесс может сначала взять левую вилку, потому правую. Однако это может привести ко взаимной блокировке процессов. Например, если все философы возьмут свои левые вилки, то они навсегда останутся в ожидании воз-.. можности взять правую вилку.
Необходимое условие взаимной блокировки — возможность кругового ожидания, т.е. когда один процесс ждет ресурс, занятый вторым процессом, который ждет ресурс, занятый третьим, и так далее до некоторого процесса, ожидающего ресурс, занятый первым процес­сом. Таким образом, чтобы избежать взаимной блокировки, достаточно обеспечить невоз­можность возникновения кругового ожидания. Для этого можно заставить один из процес­сов, скажем, Philosopher [4], сначала взять правую вилку. Это решение показано в лис­тинге 4.6. Возможен также вариант решения, в котором философы с четным номером берут вилки в одном порядке, а с нечетным — в другом.



Глава 4 Семафоры                                                                                                                         141


4.4. Задача о читателях и писателях
Задача о читателях и писателях — это еще одна классическая задача синхронизации. Как и задачу об обедающих философах, ее часто используют для сравнения механизмов синхро­низации. Она также весьма важна для практического применения.
(4.2) Задача о читателях и писателях. Базу данных разделяют два типа процессов — читатели и писатели Читатели выполняют транзакции, которые просматривают записи базы данных, а транзакции писателей и просматривают, и изменяют записи. Предполагает­ся, что вначале база данных находится в непротиворечивом состоянии (т.е. отношения между данными имеют .смысл). Каждая отдельная транзакция переводит базу данных из одного непротиворечивого состояния в другое. Для предотвращения взаимного влияния транзакций процесс-писатель должен иметь исключительный доступ к базе данных Если к базе данных не обращается ни один из процессов-писателей, то вы­полнять транзакции могут одновременно сколько угодно читателей.
Приведенное выше определение касается разделяемой базы данных, но ею может быть файл, связанный список, таблица и т.д
Задача о читателях и писателях — это еще один пример выборочного взаимного исключения. В задаче об обедающих философах пары процессов конкурировали за доступ к вилкам. Здесь за доступ к базе данных соревнуются классы процессов. Процессы-читатели конкурируют с писа­телями, а отдельные процессы-писатели — между собой. Задача о читателях и писателях — это также пример задачи общей условной синхронизации: процессы-читатели должны ждать, пока к базе данных имеет доступ хотя бы один процесс-писатель; процессы-писатели должны ждать, пока к базе данных имеют доступ процессы-читатели или другой процесс-писатель.
В этом разделе представлены два различных решения задачи о читателях и писателях. В первом она рассматривается как задача взаимного исключения.


Это решение является ко­ротким, и его легко реализовать. Однако в нем читатели получают преимущество перед писа­телями (почему— сказано ниже), и его трудно модифицировать, например, для достижения справедливости. Во втором решении задача рассматривается как задача условной синхрони­зации Это решение длиннее, оно кажется более сложным, но на самом деле его тоже легко реализовать. Более того, оно без труда изменяется для того, чтобы реализовать для читателей и писателей различные стратегии планирования. Важнее то, что во втором решении пред­ставлен мощный метод программирования, который называется передачей эстафеты и при­меним для решения любой задачи условной синхронизации.
4.4.1. Задача о читателях и писателях как задача исключения
Процессам-писателям нужен взаимоисключающий доступ к базе данных. Доступ процессов-читателей как группы также должен быть взаимоисключающим по отношению к любому процес­су-писателю. Полезный для любой задачи избирательного взаимного исключения подход — внача­ле ввести дополнительные ограничения, реализовав больше исключений, чем требуется, а затем ослабить ограничения. Представим задачу как частный случай задачи критической секции. Оче­видное дополнительное ограничение — обеспечить исключительный доступ к базе данных каждо­му читателю и писателю. Пусть переменная rw — это семафор взаимного исключения с начальным значением 1. В результате получим решение с дополнительным ограничением (листинг 4.7).
Рассмотрим, как ослабить ограничения в программе листинга 4.7, чтобы процессы-читатели могли работать параллельно. Читатели как группа должны блокировать работу писателей, но только первый читатель должен захватить блокировку взаимного исключения путем, выполнив операцию р (rw). Остальные читатели могут сразу обращаться к базе данных. Аналогично чита­тель, заканчивая работу, должен снимать блокировку, только если является последним активным процессом-читателем. Эти замечания приводят к решению, представленному в листинге 4.8.



Глава 4. Семафоры                                                                                                                         143
вычитание и проверка значения переменной пг в протоколе выхода должны выполняться не­делимым образом, поэтому протокол выхода тоже заключен в угловые скобки.
Для уточнения схемы решения в листинге 4.8 до полного решения, использующего сема­форы, нужно просто реализовать неделимые действия с помощью семафоров. Каждое дейст­вие является критической секцией, а реализация критических секций представлена в лис­тинге 4.1. Пусть mutexR— семафор, обеспечивающий взаимное исключение процессов-читателей в законченном решении задачи о читателях и писателях (листинг 4.9). Отметим, что mutexR инициализируется значением 1, начало каждого неделимого действия реализо­вано операцией Р (mutexR), а конец — операцией V (mutexR).

Алгоритм в листинге 4.9 реализует решение задачи с преимуществом читателей. Если не­который процесс-читатель обращается к базе данных, а другой читатель и писатель достигают протоколов входа, то новый читатель получает преимущество перед писателем. Следователь­но, это решение не является справедливым, поскольку бесконечный поток процессов-читателей может постоянно блокировать доступ писателей к базе данных. Чтобы получить спра­ведливое решение, программу в листинге 4.9 изменить весьма сложно (см. историческую справ­ку), но далее будет разработано другое решение, которое легко преобразуется к справедливому.
4.4.2. Решение задачи о читателях и писателях с использованием условной синхронизации
Задача о читателях и писателях рассматривалась с точки зрения взаимного исключения. Целью было гарантировать, что писатели исключают друг друга, а читатели как класс — писа­телей. Решение (см. листинг 4.9) получено было в результате объединения решений для двух
144                                               Часть 1 Программирование с разделяемыми переменными
задач критической секции: одно — для доступа к базе данных читателей и писателей, другое — для доступа читателей к переменной пг.


Построим другое решение поставленной задачи, начав с более простого определения не­обходимой синхронизации. В этом решении будет представлен общий метод программирова­ния, который называется передачей эстафеты и использует разделенные двоичные семафоры как для исключения, так и для сигнализации приостановленным процессам. Метод передачи эстафеты можно применить для реализации любых операторов типа await и, таким образом, для реализации произвольной условной синхронизации. Этот метод можно также использовать для точного управления порядком, в котором возобновляются приостановленные процессы.
В соответствии с определением (4.2) процессы-читатели просматривают базу данных, а процессы-писатели и читают, и изменяют ее. Для сохранения непротиворечивости (целостности) базы данных писателям необходим исключительный доступ, но процессы-читатели могут работать параллельно в любом количестве. Простой способ описания такой синхронизации состоит в подсчете процессов каждого типа, которые обращаются к базе дан­ных, и ограничении значений счетчиков. Например, пусть пг и nw — переменные с неотри­цательными целыми значениями, хранящие соответственно число процессов-читателей и процессов-писателей, получивших доступ к базе данных. Нужно избегать плохих состоя­ний, в которых значения обеих переменных положительны или значение nw больше 1:
BAD:    (nr >  0  л nw >  0)   v nw >  1
Дополняющее множество хороших состояний описывается отрицанием приведенного выше предиката, упрощенным до такого выражения:
RW:   (пг ==  0 v nw ==  0)   л nw <=  1
Первая часть формулы определяет, что читатели и писатели не могут получать доступ к базе данных одновременно. Вторая часть говорит, что не может быть больше одного активного писателя. В со­ответствии с этим описанием задачи схема основной части процесса-читателя выглядит так.
(пг  =  пг+1;) читать базу данных; (пг  =  пг-1;) Соответствующая схема процесса-писателя такова.
(nw =  nw+1;} записать в базу данных;


(nw = nw-1;}
Чтобы уточнить эти схемы до крупномодульного решения, нужно защитить операции присваивания разделяемым переменным, гарантируя тем самым, что предикат RWявляется глобальным инвариантом. В процессах-читателях для этого необходимо защитить увеличение nr условием (nw == 0), поскольку при увеличении переменной nr значением nw должен быть 0. В процессах-писателях необходимо соблюдение условия (пг == 0 and nw == 0), поскольку при увеличении nw желательно нулевое значение как пг, так и nw. Однако в защи­те операций вычитания нет необходимости, поскольку никогда не нужно задерживать про­цесс, освобождающий ресурс. После вставки необходимых для защиты условий получим крупномодульное решение, показанное в листинге 4.10.
Листинг 4.10. Крупномодульное решение задачи о читателях и писателях"1
int nr = 0, nw = 0;
##RW: (nr == 0 v nw == 0) л nw <= 1
process Reader[i = 1 to M] { while (true) {
(await (nw ==0) nr = nr+1;)

4.4.3. Метод передачи эстафеты
Иногда операторы await можно реализовать путем прямого использования семафоров или других элементарных операций, но в общем случае это невозможно. Рассмотрим два ус­ловия защиты операторов await в листинге 4.10. Эти условия перекрываются: условие защи­ты в протоколе входа писателя требует, чтобы и nw, и пг равнялись 0, а в протоколе входа чи­тателя — чтобы nw была равна 0. Ни один семафор не может различить эти условия, поэтому для реализации таких операторов await, как указанный здесь, нужен общий метод. Пред­ставленный здесь метод называется передачей эстафеты (появление названия объяснено ни­же). Этот метод достаточно мощен, чтобы реализовать любой оператор await.
В листинге 4.10 присутствуют четыре неделимых оператора. Первые два (в процессах чи­тателя и писателя) имеют вид:
(await   (В)   S;}
Как обычно, В обозначает логическое выражение, as— список операторов. Последние два неделимых оператора в обоих процессах имеют вид:
<S;>
Как было сказано в разделе 2.4, в первой форме может быть представлена любая условная синхронизация, а вторая форма является просто ее сокращением для частного случая, когда значение условия В неизменно и истинно.


Следовательно, если знать, как с помощью сема­ форов реализуются операторы await, можно решить любую задачу условной синхронизации.
Для реализации операторов await из листинга4.10 можно использовать разделенные двоичные семафоры. Пусть е — двоичный семафор с начальным значением 1. Он будет при­меняться для управления входом (entry) в любое неделимое действие.
С каждым условием защиты в свяжем один семафор и один счетчик с нулевыми началь­ными значениями. Семафор будем использовать для приостановки процесса до момента, когда условие защиты станет истинным. В счетчике будет храниться число приостановленных процессов. В программе (см. листинг 4.10) есть два разных условия защиты, по одному в про­токолах входа писателей и читателей, поэтому нужны два семафора и два счетчика. Пусть г — семафор, связанный с условием защиты в процессе-читателе, a dr — соответствующий ему счетчик приостановленных процессов-читателей. Аналогично пусть с условием защиты в процессе-писателе связаны семафор w и счетчик приостановленных процессов-писателей dw. Вначале нет ожидающих читателей и писателей, поэтому значения г, dr, w и dw равны 0.
Использование трех семафоров (е, г и w) и двух счетчиков (dr и dw) описано в листинге 4.11. Комментарии поясняют, как реализованы крупномодульные неделимые действия из листин­га 4.10. Для выхода из неделимых действий использован следующий код, помеченный SIGNAL.

Глава 4 Семафоры                                                                                                                         147 •
Три семафора в листинге 4.11 образуют разделенный двоичный семафор, поскольку в лю­бой момент времени только один из них может иметь значение 1, а все выполняемые ветви начинаются операциями Р и заканчиваются операциями V. Следовательно, операторы между каждой парой Р и V выполняются со взаимным исключением. Инвариант синхронизации RW является истинным в начале работы программы и перед каждой операцией V, так что он ис­тинен, если один из семафоров имеет значение 1.


Кроме того, при выполнении защищенного оператора истинно его условие защиты В, поскольку его проверил /либо сам процесс и обна­ружил, что оно истинно, либо семафор, который сигнализировал о продолжении приоста­новленного процесса, если только в истинно. Наконец, рассматриваемое преобразование ко­да не приводит ко взаимной блокировке, поскольку семафор задержки получает сигнал, толь­ко если некоторый процесс находится в состоянии ожидания или должен в него перейти. (Процесс может увеличить счетчик ожидающих процессов и выполнить операцию V(e), но не может выполнить операцию Р для семафора задержки.)
Описанный метод программирования называется передачей эстафеты из-за способа вы­работки сигналов семафорами. Когда процесс выполняется внутри критической секции, счи­тается, что он получил эстафету, которая подтверждает его право на выполнение. Передача эстафеты происходит, когда процесс доходит до фрагмента программы SIGNAL. Если некото­рый процесс ожидает условия, которое теперь стало истинным, эстафета передается одному из таких процессов, который в свою очередь выполняет критическую секцию и передает эс­тафету следующему процессу. Если ни один из процессов не ожидает условия, которое стало истинным, эстафета передается следующему процессу, который впервые пытается войти в критическую секцию, т.е. следующему процессу, выполняющему Р (е).
В листинге 4.11, как и в общем случае, многие экземпляры кода SIGNAL можно упростить или опустить. В процессе-читателе, например, перед выполнением первого экземпляра кода SIGNAL, т.е. в конце протокола входа процесса-читателя, пг больше нуля и nw равна нулю. Это значит, что фрагмент программы SIGNAL можно упростить:

Перед вторым экземпляром кода SIGNAL в процессах-читателях обе переменные nw и dr равны нулю В процессах-писателях пг равна нулю и nw больше нуля перед кодом SIGNAL в конце прото­кола входа писателя Наконец, обе переменные nw и пг равны нулю перед последним экземпляром кода SIGNAL процесса-писателя.


С помощью этих закономерностей упростим сигнальные про­токолы и получим окончательное решение, использующее передачу эстафеты (листинг 4.12).
В этом варианте программы, если в момент завершения работы писателя несколько про­цессов-читателей отложены и один продолжает работу, то остальные возобновятся последо­вательно. Первый читатель увеличит пг и возобновит работу второго приостановленного процесса-читателя, который тоже увеличит nг и запустит третий процесс, и так далее. Эста­фета передается от одного приостановленного процесса другому до тех пор, пока все они не возобновятся, т.е. значение переменной пг не станет равным 0. Последний оператор if про­цесса-писателя в листинге 4.12 сначала проверяет, есть ли приостановленные читатели, затем — есть ли приостановленные писатели. Порядок этих проверок можно свободно изме­нять, поскольку, если есть приостановленные процессы обоих типов, то после завершения протокола выхода писателя сигнал может получить любой из них.
4.4.4. Другие стратегии планирования
Решение задачи о читателях и писателях в листинге 4.12, конечно, длиннее, чем решение 4.8. Однако оно основано на многократном применении простого принципа — всегда передавать эс­тафету взаимного исключения только одному процессу. Оба решения дают преимущество чита-

Глава 4. Семафоры                                                                                                                         149
Для выполнения второго условия изменим порядок первых двух ветвей оператора if процес­сов-писателей:

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


При условии, что справедливы сами операции с семафорами, можно обеспечить справед­ливый доступ к базе данных, изменив программу 4.12.'Например, когда в состоянии ожида­ния находятся и читатели и писатели, можно запускать их по очереди. Для этого нужно:
•    если ожидает писатель, приостанавливать работу нового читателя;
•    если ожидает читатель, приостанавливать работу нового писателя;
•    когда заканчивает работу читатель, запускать один ожидающий процесс-писатель (если он есть);
•    когда заканчивает работу писатель, запускать все ожидающие процессы-читатели (если они есть); иначе запускать один ожидающий процесс-писатель (если он есть).
Можно приостанавливать работу новых читателей и писателей, как показано выше. (Программа в листинге 4.12 удовлетворяет двум последним требованиям.) И здесь структура решения не изменяется.
Метод передачи эстафеты можно применить, чтобы управление порядком, в котором процессы используют ресурсы, сделать более мелкомодульным. Это демонстрируется в сле­дующем разделе. Единственное, чем мы не можем управлять — это порядок запуска процес­сов, остановленных на входном семафоре, но это зависит от реализации семафоров.

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

---

---