taken = false: notTaken.signal ():

class Philosopher : public ZThread::Runnable { Chopsticks left: Chopsticks right: int id:

int ponderFactor:

ZThread::CountedPtr<Display> display: int randSleepTimeC) {

if(ponderFactor == 0) return 0:

return rand()/(RAND MAX/ponderFactor) * 250:

void outputCstd::string s) { std::ostringstream os: OS *this s std::endl: display->output(os):

public:

PhilosopherCChopstickS 1. ChopstickS r.

ZThread;:CountedPtr<Display>S disp, int ident,int ponder)

: left(l). r1ght(r), id(ident). ponderFactor(ponder).

display(disp) {} virtual void run() {

try {

while(!ZThread::Thread::interruptedO) { outputCthinking ):

ZThread::Thread::sleep(randSleepTime()):

Философ голоден

output( grabbing right ):

right.takeO:

output( grabbing left );

left.takeO:

output( eating ):

ZThread::Thread::sleep(randSleepTime()):

right.drop();

left.dropO:

} catch(ZThread::Synchronization ExceptionS e) { output(e.what()):

friend std::ostreamS

operator (std::ostreamS os. const Philosophers p) { return os Philosopher p.id:

#endif DININGPHILOSOPHERSJ /:-

Два философа (объекты Philosopher) не могут взять (takeO) палочку (объект Chopstick) одновременно, поскольку функция take() синхронизируется при помощи мутекса. Кроме того, если палочка уже находится у кого-то другого, философ ожидает ее освобождения вызовом функции drop() (причем этот вызов тоже должен синхронизироваться для предотвращения ситуации гонок и обеспечения видимости изменений в многопроцессорных системах).

Ha момент написания книги поддержка многопоточности в проекте Cygwin (www.cygwin.com) изменялась и совершенствовалась, но нам так и не удалось наблюдать взаимную блокировку в текушей версии Cygwin. С другой стороны, в системе Linux профамма довольно быстро выходила па взаимную блокировку.

Каждый объект Philosopher содержит ссылки на два объекта Chopstick (левая и правая палочки). Через эти ссылки он пытается взять палочки. Объект Philosopher одну часть времени думает, а другую - ест, и это обстоятельство отражено в функции main(). Нетрудно заметить, что если философы будут слишком мало думать, то при попытках поесть у них возникнет конкуренция за палочки, и взаимная блокировка случится гораздо быстрее. Чтобы вам было удобнее экспериментировать, переменная ponderFactor определяет отношение между затратами времени на размышления и еду. Малые значения ponderFactor повышают вероятность взаимной блокировки.

В функции Philosopher::run() все объекты Philosopher непрерывно думают и едят. Объект Philosopher думает в течение случайного промежутка времени, после чего пытается функцией take() взять правую (right) и левую (left) палочки. Далее он ест в течение случайного промежутка времени, и весь процесс повторяется заново. Вывод на консоль синхронизируется, о чем рассказывалось ранее в этой главе.

Задача обедающих философов доказывает, что даже правильно работающая (на первый взгляд) программа может быть подвержена взаимным блокировкам. Чтобы вы могли убедиться в этом, аргумент командной строки изменяет долю времени, затрачиваемую философом на размышления. Если философов много или они тратят большую часть времени на раздумья, возможно, вы никогда не столкнетесь с взаимной блокировкой, хотя ее теоретическая возможность остается. Если аргумент командной строки равен нулю, взаимная блокировка обычно возникает довольно быстро:

: Cll:DeadlockingDiningPhilosophers.cpp {RunByHand}

Обедающие философы и взаимная блокировка.

{L} ZThread

#include <ctime>

#1nclude Dini ngPhi1osophers.h

#include Zthread/ThreadedExecutor.h

using namespace ZThread:

using namespace std:

int main(int argc, char* argv[]) { srand(time(0)): Раскрутка генератора случайных чисел int ponder = argc > 1 ? atoi(argv[l]) : 5: cout Press <ENTER> to quit endl: enum { SZ = 5 }: try {

CountedPtr<Display> d(new Display): ThreadedExecutor executor: Chopstick c[SZ]: for(int i = 0: i < SZ: i++) { executor.execute( new Philosopher(c[i]. c[(i+l) % SZ]. d. i,ponder)):

cin.getO:

executor. interruptO: executor.waitO: } catch(Synchronization Exception& e) { cerr e.whatO endl:

} /:-

Объектам Chopstick не нужны внутренние идентификаторы, они идентифицируются своей позицией в массиве с. Каждому объекту Philosopher при конструировании назначается ссылка на левый и правый объекты Chopstick; это те самые столовые принадлежности, без которых философ не может есть. Каждый объект Philosopher, кроме последнего, инициализируется размещением между следующей парой объектов Chopstick. Последнему объекту Philosopher в правой ссылке назначается нулевой объект Chopstick, и круг замыкается (последний философ сидит рядом с первым, а нулевая палочка лежит между ними). При таком расположении в какой-то момент может возникнуть ситуация, когда все философы попытаются начать есть и будут ждать, пока их сосед положит палочку. В программе происходит взаимная блокировка.

Если программные потоки (философы) тратят на другие задачи (на размышления) больше времени, чем на еду, вероятность одновременного доступа к общим ресурсам (палочкам) существенно снижается. При ненулевом значении ponderFactor вы даже можете убедить себя, что программа не содержит ошибок, хотя на самом деле это не так.

Чтобы решить проблему, вы должны понять, что взаимная блокировка возникает при одновременном выполнении четырех условий.

Взаимное ис1спючение. По крайней мере, один ресурс, требующийся потокам, должен исключать одновременный доступ. В нашем примере каждая палочка одновременно может использоваться только одним философом.

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

Ресурс не может быть принудительно отнят у процесса. Освобождение ресурсов происходит только естественным образом. Философы - народ вежливый, они не отбирают палочки у своих коллег.

Возможно циклическое ожидание, когда процесс ожидает освобождения ресурса, удерживаемого другим процессом, который в свою очередь ожидает освобождения ресурса, удерживаемого третьим процессом и т. д., а п-й процесс ожидает доступности ресурса, удерживаемого первым процессом, то есть круг замыкается. В примере DeadlockingDiningPhilosophers.cpp циклическое ожидание возникает из-за того, что каждый философ сначала пытается взять правую, а потом - левую палочку.

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