сряда, 14 януари 2009 г.

Задачата за обядващите философи

И тази задача е поставена и решена за първи път от Дейкстра чрез семафори и обща памет. Задачата се състои в следното. Пет философа седят около кръгла маса, като пред всеки от тях има чиния със спагети, а между всеки две чинии има само по една вилица. Животът на всеки философ представлява цикъл, в който той размишлява, в резултат на което огладнява и се опитва да вземе двете вилици около своята чиния. Ако успее известно време се храни, а след това връща вилиците. Задачата е да се напише програма, която да прави това, което се очаква от философа.

Решението на Дейкстра използва общ масив state[N], като всеки елемент описва състоянието на съответния философ. Възможните състояния са: мисли, гладен е (опитва се да вземе двете вилици) и храни се. Достъпа до общия масив се регулира от двоичен семафор mutex. Освен него се използва масив от семафори s[N], по един за всеки философ, по който той се блокира когато трябва да чака освобождаването на вилиците


#define N 5
#define TRUE 1
#define LEFT (i-1)%N /* номер на левия съсед на философ i */
#define RIGHT (i+1)%N /* номер на десния съсед на философ i */
#define THINKING 0 /* философът мисли */
#define HUNGRY 1 /* философът се опитва да вземе вилици */
#define EATING 2 /* философът се храни */
shared int state[N] ]={0,0,0,0,0};
semaphore mutex=1; /* за взаимно изключване на state[N] */
semaphore s[N]={0,0,0,0,0}; /* семафори, по един на философ */
philosopher(int i)
{
while(TRUE) {
think();
take_forks(i);
eat();
put_forks(i);
}
}
take_forks(int i)
{
P(mutex);
state[i] = HUNGRY;
test(i);
V(mutex);
P(s[i]);
}

put_forks(int i)
{
P(mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
V(mutex);
}
test(int i)
{
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING) {
state[i] = EATING;
V(s[i]);
}
}
При използването на обща памет и семафори за междупроцесни комуникации отговорността за правилното взаимодействие на процесите е на програмиста. Поради това този метод не е безопасен. Грешки в програмите могат да доведат до дедлок, състезание и други форми на непредсказуемо и невъзпроизводимо поведение.


Няма коментари:

Публикуване на коментар