CPU burst 37 страница

А л г о р и т м б у л о ч н о й (Bakery algorithm)

А л г о р и т м П е т е р с о н а д а е т н а м р е ш е н и е з а д а ч и к о р р е к т н о й о р г а н и з а ц и и в з а и м о д е й с т в и я д в у х п р о ц е с с о в. Д а в а й т е р а с с м о т р и м т е п е р ь с о о т в е т с т в у ю щ и й а л г о р и т м д л я n в з а и м о д е й с т в у ю щ и х п р о ц е с с о в, к о т о р ы й п о л у ч и л н а з в а н и е а л г о р и т м б у л о ч н о й, х о т я п р и м е н и т е л ь н о к н а ш и м у с л о в и я м е г о с л е д о в а л о б ы с к о р е е н а з в а т ь а л г о р и т м р е г и с т р а т у р ы в п о л и к л и н и к е. О с н о в н а я е г о и д е я в ы г л я д и т т а к. К а ж д ы й в н о в ь п р и б ы -

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

shared enum {false, true} choosing[n]; shared int number[n];

И з н а ч а л ь н о э л е м е н т ы э т и х м а с с и в о в и н и ц и и р у ю т с я з н а ч е н и я м и false и 0 с о о т в е т с т в е н н о. В в е д е м с л е -д у ю щ и е о б о з н а ч е н и я

(a, b) < (c, d), е с л и a < c

и л и е с л и a == c и b < d

max(a₀, a₁,...., a_n) – э т о ч и с л о k т а к о е, ч т о k > = a_i д л я в с е х i = 0,..., n

С т р у к т у р а п р о ц е с с а P_i д л я а л г о р и т м а б у л о ч н о й п р и в е д е н а н и ж е

while (some condition) { choosing[i] = true;

number[i] = max(number[0],..., number[n-1]) + 1;

choosing[i] = false; for(j = 0; j < n; j++){

while(choosing[j]);

while(number[j]! = 0 & & (number[j], j) < (number[i], i));

}

critical section number[i] = 0;

remainder section

}

Д о к а з а т е л ь с т в о т о г о, ч т о э т о т а л г о р и т м у д о в л е т в о р я е т у с л о в и я м 1 – 5, в ы п о л н и т е с а м о с т о я т е л ь н о в к а ч е -с т в е у п р а ж н е н и я.

А п п а р а т н а я п о д д е р ж к а в з а и м о и с к л ю ч е н и й

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

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

К о м а н д а Test-and-Set (п р о в е р и т ь и п р и с в о и т ь 1)

О в ы п о л н е н и и к о м а н д ы Test-and-Set, о с у щ е с т в л я ю щ е й п р о в е р к у з н а ч е н и я л о г и ч е с к о й п е р е м е н н о й с о д -н о в р е м е н н о й у с т а н о в к о й е е з н а ч е н и я в 1, м о ж н о д у м а т ь к а к о в ы п о л н е н и и ф у н к ц и и

int Test_and_Set (int *target){ int tmp = *target;

*target = 1; return tmp;

}

С и с п о л ь з о в а н и е м э т о й а т о м а р н о й к о м а н д ы м ы м о ж е м м о д и ф и ц и р о в а т ь н а ш а л г о р и т м д л я п е р е м е н н о й -з а м к а, т а к ч т о б ы о н о б е с п е ч и в а л в з а и м о и с к л ю ч е н и я

shared int lock = 0;

while (some condition) { while(Test_and_Set(& lock));

critical section lock = 0;

remainder section

}

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

К о м а н д а Swap (о б м е н я т ь з н а ч е н и я)

В ы п о л н е н и е к о м а н д ы Swap, о б м е н и в а ю щ е й д в а з н а ч е н и я, н а х о д я щ и х с я в п а м я т и, м о ж н о п р о и л л ю с т р и -р о в а т ь с л е д у ю щ е й ф у н к ц и е й:

void Swap (int *a, int *b){ int tmp = *a;

*a = *b; *b = tmp;

}

П р и м е н я я а т о м а р н у ю к о м а н д у Swap, м ы м о ж е м р е а л и з о в а т ь п р е д ы д у щ и й а л г о р и т м, в в е д я д о п о л н и т е л ь -н у ю л о г и ч е с к у ю п е р е м е н н у ю key, л о к а л ь н у ю д л я к а ж д о г о п р о ц е с с а:

shared int lock = 0; int key;

while (some condition) { key = 1;

do Swap(& lock, & key); while (key);

critical section lock = 0;

remainder section

}

З а к л ю ч е н и е

П о с л е д о в а т е л ь н о е в ы п о л н е н и е н е к о т о р ы х д е й с т в и й, н а п р а в л е н н ы х н а д о с т и ж е н и е о п р е д е л е н н о й ц е л и, н а з ы в а е т с я а к т и в н о с т ь ю. А к т и в н о с т и с о с т о я т и з а т о м а р н ы х о п е р а ц и й, в ы п о л н я е м ы х н е р а з р ы в н о, к а к е д и н и ч н о е ц е л о е. П р и и с п о л н е н и и н е с к о л ь к и х а к т и в н о с т е й в п с е в д о п а р а л л е л ь н о м р е ж и м е а т о м а р н ы е о п е р а ц и и р а з л и ч н ы х а к т и в н о с т е й м о г у т п е р е м е ш и в а т ь с я м е ж д у с о б о й с с о б л ю д е н и е м п о р я д к а с л е д о в а -н и я в н у т р и а к т и в н о с т е й. Э т о я в л е н и е п о л у ч и л о н а з в а н и е interleaving (ч е р е д о в а н и е). Е с л и р е з у л ь т а т ы в ы -п о л н е н и я н е с к о л ь к и х а к т и в н о с т е й н е з а в и с я т о т в а р и а н т а ч е р е д о в а н и я, т о т а к о й н а б о р а к т и в н о с т е й н а з ы -в а е т с я д е т е р м и н и р о в а н н ы м. В п р о т и в н о м с л у ч а е о н н о с и т н а з в а н и е н е д е т е р м и н и р о в а н н о г о. С у щ е с т в у е т д о с т а т о ч н о е у с л о в и е Б е р н с т а й н а д л я о п р е д е л е н и я д е т е р м и н и р о в а н н о с т и н а б о р а а к т и в н о с т е й, н о о н о н а -к л а д ы в а е т о ч е н ь ж е с т к и е о г р а н и ч е н и я н а н а б о р, т р е б у я п р а к т и ч е с к и н е в з а и м о д е й с т в у ю щ и х а к т и в н о -с т е й. П р о н е д е т е р м и н и р о в а н н ы й н а б о р а к т и в н о с т е й г о в о р я т, ч т о о н и м е е т race condition (у с л о в и е г о н к и, с о с т я з а н и я). У с т р а н е н и е race condition в о з м о ж н о п р и о г р а н и ч е н и и д о п у с т и м ы х в а р и а н т о в ч е р е д о в а н и й а т о м а р н ы х о п е р а ц и й с п о м о щ ь ю с и н х р о н и з а ц и и п о в е д е н и я а к т и в н о с т е й. У ч а с т к и а к т и в н о с т е й, в ы п о л н е -н и е к о т о р ы х м о ж е т п р и в е с т и к race condition, н а з ы в а ю т к р и т и ч е с к и м и у ч а с т к а м и. Н е о б х о д и м ы м у с л о в и -е м д л я у с т р а н е н и я race condition я в л я е т с я о р г а н и з а ц и я в з а и м о и с к л ю ч е н и я н а к р и т и ч е с к и х у ч а с т к а х: в н у т р и с о о т в е т с т в у ю щ и х к р и т и ч е с к и х у ч а с т к о в н е м о ж е т о д н о в р е м е н н о н а х о д и т ь с я б о л е е о д н о й а к т и в -н о с т и.

Д л я э ф ф е к т и в н ы х п р о г р а м м н ы х а л г о р и т м о в у с т р а н е н и я race condition п о м и м о у с л о в и я в з а и м о и с к л ю ч е -н и я т р е б у е т с я в ы п о л н е н и е с л е д у ю щ и х у с л о в и й: а л г о р и т м ы н е и с п о л ь з у ю т с п е ц и а л ь н ы х к о м а н д п р о ц е с -

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