Журнал LinuxFormat - перейти на главную

LXF163:Erlang: Программируем синхронизацию

Материал из Linuxformat
Перейти к: навигация, поиск


Erlang Опи­сы­ва­ет­ся сле­дую­щей фор­му­лой: функ­цио­наль­ный язык + про­цес­сы


Erlang: Программируем синхронизацию

Ан­д­рей Уша­ков рас­смат­ри­ва­ет ор­га­ни­за­цию ра­бо­ты мно­го­за­дач­ных при­ло­же­ний. Без взаи­мо­дей­ст­вия тут не обой­тись...

(thumbnail)
Наш эксперт Ан­д­рей Уша­ков ак­тив­но при­бли­жа­ет тот день, когда функ­цио­наль­ные язы­ки ста­нут мейн­ст­ри­мом.

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

Пер­вый и, по­жа­луй, глав­ный во­прос, тре­бую­щий от­ве­та – что та­кое син­хрониза­ция ме­ж­ду за­да­ча­ми и за­чем она нуж­на. Син­хрониза­ция ме­ж­ду за­да­ча­ми – это все­го лишь взаи­мо­дей­ст­вие ме­ж­ду за­да­ча­ми в мно­го­за­дач­ной сре­де при по­мо­щи тех или иных средств. А вот за­чем оно нуж­но, уже ин­те­реснее. Крайне ред­ко уда­ет­ся раз­де­лить од­ну боль­шую за­да­чу на несколь­ко аб­со­лют­но неза­ви­си­мых за­дач, спо­соб­ных вы­пол­нять­ся па­рал­лель­но. Чаще одни за­да­чи долж­ны до­ж­дать­ся за­вер­шения дру­гих, пре­ж­де чем на­чать или про­дол­жить свою ра­бо­ту. При­ме­р та­кой си­туа­ции – про­бле­мы ви­да “map-reduce”. Для ре­шения по­доб­ных про­блем сна­ча­ла вы­пол­ня­ют­ся за­да­чи “map”, об­ра­ба­ты­ваю­щие вход­ные дан­ные, а затем за­да­чи “reduce”, ко­то­рые аг­ре­ги­ру­ют (или свер­ты­ва­ют) по­лу­чен­ные на пре­ды­ду­щем ша­ге дан­ные в некое ре­зуль­ти­рую­щее зна­чение.

В боль­шин­ст­ве слу­ча­ев за­да­чи об­ра­бот­ки хо­ро­шо под­да­ют­ся пе­ре­но­су в мно­го­за­дач­ную сре­ду, тогда как за­да­чи сверт­ки – го­раз­до ху­же (хо­тя мож­но при по­мо­щи несколь­ких за­дач про­из­ве­сти про­ме­жу­точ­ную сверт­ку, а за­тем при по­мо­щи од­ной за­да­чи вы­полнить окон­ча­тель­ную сверт­ку для по­лу­чения ито­го­во­го ре­зуль­та­та). Оче­вид­но, что за­да­чи сверт­ки долж­ны вы­пол­нять­ся толь­ко по за­вер­шении всех или части за­дач по об­ра­бот­ке. Ана­ло­гич­но, ес­ли мы ис­поль­зу­ем про­ме­жу­точ­ную сверт­ку, то за­да­ча по оконча­тель­ной сверт­ке долж­на вы­пол­нять­ся толь­ко по за­вер­шении за­дач про­ме­жу­точ­ной сверт­ки дан­ных. Вот при­мер про­бле­мы, ре­шае­мой при по­мо­щи под­хо­да “map-reduce”: пусть нас ин­те­ре­су­ет час­то­та ис­поль­зо­вания слов в боль­шом тек­сте. Тогда при по­мо­щи за­дач об­ра­бот­ки мы мог­ли бы по­счи­тать час­то­ту ис­поль­зо­вания слов в ка­ж­дом па­ра­гра­фе (и эти за­да­чи бу­дут хо­ро­шо ра­бо­тать па­рал­лель­но), по­сле че­го при по­мо­щи за­да­чи сверт­ки по­лу­чить ито­го­вый ре­зуль­тат.

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

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

Рас­смот­рим при­мер на язы­ке C, ил­лю­ст­ри­рую­щий дан­ную про­бле­му. Пусть у нас есть гло­баль­ная пе­ре­мен­ная X, доступ к ко­то­рой име­ют несколь­ко за­дач, и сле­дую­щий про­стой блок ко­да, из­ме­няю­щий на­ши дан­ные (гло­баль­ную пе­ре­мен­ную X): {X *= 3;}. Для понимания про­блем, возникаю­щих при вы­полнении это­го бло­ка ко­да, да­вай­те опустим­ся на уро­вень ниже и рас­смот­рим один из его ана­ло­гов на язы­ке ас­семб­лер (для про­цес­со­ров x86):

imul eax, [X], 3

mov dword ptr [X], eax

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

Но вернем­ся к на­ше­му при­ме­ру: пред­по­ло­жим, что две за­да­чи од­но­вре­мен­но вы­пол­ня­ют этот блок ко­да (на­при­мер, на раз­ных яд­рах про­цес­со­ра), и рас­смот­рим один из воз­мож­ных ва­ри­ан­тов од­но­вре­мен­но­го вы­полнения. Для оп­ре­де­лен­но­сти, пусть зна­чение пе­ре­мен­ной X до вы­полнения это­го бло­ка ко­да бы­ло 3. На пер­вом ша­ге обе за­да­чи на­чи­на­ют вы­полнение это­го бло­ка ко­да (вхо­дят в него). На сле­дую­щем ша­ге обе за­да­чи вы­пол­ня­ют ин­ст­рук­цию imul: в ре­зуль­та­те для обе­их за­дач зна­чение ре­ги­ст­ра eax ста­но­вит­ся 9. На сле­дую­щем ша­ге обе за­да­чи со­хра­ня­ют свои зна­чения ре­ги­ст­ра eax в ячей­ку па­мя­ти, свя­зан­ной с пе­ре­мен­ной X; в ре­зуль­та­те пе­ре­мен­ная X по­лу­ча­ет зна­чение 9. И на по­следнем ша­ге обе за­да­чи за­кан­чи­ва­ют вы­полнение это­го бло­ка ко­да (вы­хо­дят из него). Ес­ли бы две эти за­да­чи вы­пол­ня­ли этот блок ко­да по­сле­до­ва­тель­но, пе­ре­мен­ная X по­лу­чи­ла бы зна­чение 27, а в на­шем при­ме­ре пе­ре­мен­ная X по­лу­чи­ла зна­чение 9.

В этом при­ме­ре мы по­ка­за­ли про­бле­му, из­вест­ную как со­стя­зание (гонка) за ре­сур­сы. Дру­гая из­вест­ная про­бле­ма, свя­зан­ная с од­но­вре­мен­ным из­менением дан­ных – по­вре­ж­дение дан­ных. Обыч­но дан­ные по­вре­ж­да­ют­ся, когда несколь­ко за­дач од­но­вре­мен­но об­нов­ля­ют слож­ные струк­ту­ры дан­ных, доступ к ко­то­рым не ато­ма­рен на уровне про­цес­со­ра. На­при­мер, на плат­фор­ме x86 та­кой струк­ту­рой дан­ных бу­дут 64-бит­ные це­лые чис­ла. По­сле та­ко­го об­нов­ления в по­доб­ной струк­ту­ре мо­гут со­дер­жать­ся дан­ные всех про­цес­сов, про­из­во­див­ших об­нов­ление, и, со­от­вет­ст­вен­но, са­ма струк­ту­ра со­дер­жит дан­ные, ко­то­рые в ней не поя­ви­лись бы, ес­ли бы все про­цес­сы об­нов­ля­ли ее по­сле­до­ва­тель­но. Возника­ет вполне ло­гич­ный во­прос: что на­до де­лать, что­бы по­доб­ных си­туа­ций не возника­ло? От­вет вполне оче­ви­ден: ес­ли несколь­ко про­цес­сов од­но­вре­мен­но об­ра­ща­ют­ся к неко­то­рым дан­ным, при­чем неко­то­рые из этих про­цес­сов из­ме­ня­ют об­щие дан­ные, то для досту­па к этим дан­ным необ­хо­ди­мо ис­поль­зо­вать сред­ст­ва син­хрониза­ции.

Ре­ен­те­ра­бель­ность бло­ки­ро­вок

Ре­ен­те­ра­бель­ность – это воз­мож­ность по­втор­но­го ис­поль­зо­вания ка­ко­го-ли­бо объ­ек­та или вы­зо­ва функ­ции в мо­мент, когда дан­ный объ­ект ис­поль­зу­ет­ся или функ­ция вы­зва­на. В слу­чае объ­ек­тов бло­ки­ров­ки это оз­на­ча­ет, мо­жет ли од­на и та же сто­ро­на «за­хва­тить» объ­ект бло­ки­ров­ки несколь­ко раз. Ес­ли да, то та­кой объ­ект бло­ки­ров­ки яв­ля­ет­ся ре­ен­те­ра­бель­ным (при этом, ес­ли мы N раз «за­хва­ти­ли» объ­ект бло­ки­ров­ки, его необ­хо­ди­мо «осво­бо­дить» так­же N раз); ес­ли же нет – нере­ен­те­ра­бель­ным (при по­пыт­ках «за­хва­тить» та­кой объ­ект бло­ки­ров­ки несколь­ко раз мы в ито­ге по­лу­чим са­мо­бло­ки­ров­ку). Бло­ки­ров­ки, под­дер­жи­вае­мые мо­ду­лем global, яв­ля­ют­ся ре­ен­те­ра­бель­ны­ми.

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

Те­перь рас­смот­рим, ка­кие сред­ст­ва для син­хрониза­ции за­дач у нас есть. Не бу­дем сей­час го­во­рить о кон­крет­ных сред­ст­вах; зай­мем­ся сред­ст­ва­ми для син­хрониза­ции за­дач в об­щем.

Су­ще­ст­ву­ют два клас­са средств син­хрониза­ции: это сред­ст­ва, ко­то­рые мо­гут при­во­дить к бло­ки­ров­кам за­дач (син­хрониза­ция с бло­ки­ров­ка­ми) и сред­ст­ва, ко­то­рые к бло­ки­ров­кам за­дач не при­во­дят (небло­ки­рую­щая син­хрониза­ция). Ра­бо­та средств син­хрониза­ции с бло­ки­ров­ка­ми осно­ва­на на спе­ци­аль­ном объ­ек­те, на­зы­вае­мом бло­ки­ров­кой. Объ­ект, пред­став­ляю­щий бло­ки­ров­ку, об­ла­да­ет несколь­ки­ми (минимум дву­мя) со­стояния­ми, и его по­ве­дение ме­ня­ет­ся в за­ви­си­мо­сти от то­го, в ка­ком со­стоянии он на­хо­дит­ся. В про­стей­шем слу­чае та­кой объ­ект име­ет два со­стояния; на­при­мер, для мью­тек­са это «сво­бо­ден» и «за­нят».

Когда объ­ект бло­ки­ров­ки на­хо­дит­ся в сво­бод­ном со­стоянии, лю­бая за­да­ча мо­жет «за­хва­тить» его (при по­мо­щи функ­ции из API); при этом объ­ект бло­ки­ров­ки пе­рей­дет в за­ня­тое со­стояние. Когда ка­кая-то дру­гая за­да­ча по­пы­та­ет­ся «за­хва­тить» объ­ект бло­ки­ров­ки, на­хо­дя­щий­ся в за­ня­том со­стоянии, вы­полнение этой за­да­чи бу­дет за­бло­ки­ро­ва­но (и она пе­рей­дет в со­стояние ожи­дания) до тех пор, по­ка объ­ект бло­ки­ров­ки не пе­рей­дет в сво­бод­ное со­стояние. Когда за­да­ча, вла­дею­щая объ­ек­том бло­ки­ров­ки, «осво­бо­дит» его (при по­мо­щи функ­ции из API), лю­бая дру­гая за­да­ча, ожи­даю­щая осво­бо­ж­дения это­го объ­ек­та бло­ки­ров­ки, мо­жет «за­хва­тить» его. Обыч­но при этом со всех за­дач снима­ет­ся бло­ки­ров­ка, по­сле че­го ка­кая-то од­на из за­дач «за­хва­ты­ва­ет» объ­ект бло­ки­ров­ки, а все осталь­ные за­да­чи бло­ки­ру­ют­ся (при по­пыт­ке «за­хва­тить» этот объ­ект бло­ки­ров­ки). В бо­лее слож­ных слу­ча­ях и по­ве­дение объ­ек­та бло­ки­ров­ки бу­дет бо­лее слож­ным: объ­ект бло­ки­ров­ки мо­жет раз­ре­шать «за­хва­ты­вать» се­бя несколь­ким за­да­чам (на­при­мер, когда объ­ект бло­ки­ров­ки пред­став­ля­ет со­бой се­ма­фор или бло­ки­ров­ку чтения-за­пи­си), мо­жет применять­ся для сиг­на­ли­за­ции о неко­то­ром со­бы­тии (услов­ные пе­ре­мен­ные в POSIX, объ­ек­ты яд­ра, со­бы­тие в WIN32 API) и т. д.

Ра­бо­та средств небло­ки­рую­щей син­хрониза­ции осно­ва­на на та­ких сред­ст­вах, как ато­мар­ные опе­ра­ции и спе­ци­аль­ные ме­ханиз­мы бло­ки­ров­ки. Эти спе­ци­аль­ные ме­ханиз­мы бло­ки­ров­ки не бло­ки­ру­ют за­да­чу (не пе­ре­во­дят ее в со­стояние ожи­дания), ес­ли объ­ект бло­ки­ров­ки не мо­жет быть «за­хва­чен» дан­ной за­да­чей. Вме­сто это­го за­да­ча в бес­конеч­ном цик­ле про­ве­ря­ет, не осво­бо­дил­ся ли этот объ­ект бло­ки­ров­ки (т. н. спин-бло­ки­ров­ка). Ато­мар­ная опе­ра­ция – это опе­ра­ция, ко­то­рая вы­полняется ато­мар­но на про­цес­со­ре, т. е. вы­полнение за­да­чи мо­жет быть пре­рва­но ли­бо до, ли­бо по­сле та­кой опе­ра­ции. К по­доб­ным опе­ра­ци­ям от­но­сят­ся ин­кре­мент, дек­ре­мент, сравнение с об­ме­ном (CAS) и др. Наи­бо­лее зна­чи­мая из ато­мар­ных опе­ра­ций – опе­ра­ция сравнения с об­ме­ном, ко­то­рая ато­мар­но про­ве­ря­ет зна­чение пе­ре­мен­ной с неко­то­рым за­дан­ным зна­чением и при несов­па­дении уста­нав­ли­ва­ет зна­чение пе­ре­мен­ной в за­дан­ное.

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

Пер­вая и наи­бо­лее оче­вид­ная пла­та за ис­поль­зо­вание средств син­хрониза­ции – усложнение ис­ход­но­го ко­да при­ло­жения (по сравнению с ва­ри­ан­том без ис­поль­зо­вания средств син­хро­низа­ции или од­но­за­дач­ным ва­ри­ан­том). Бо­лее то­го, при­ло­жение, раз­ра­бо­тан­ное с ис­поль­зо­ванием средств небло­ки­рую­щей син­хрониза­ции, обыч­но име­ет бо­лее слож­ную струк­ту­ру по сравнению с ана­ло­гич­ным при­ло­жением, раз­ра­бо­тан­ным с ис­поль­зо­ванием средств син­хрониза­ции с бло­ки­ров­ка­ми. Ис­поль­зо­вание этих средств при­во­дит к снижению про­из­во­ди­тель­но­сти (вре­ме­на­ми зна­чи­тель­но­му) в си­туа­ции мно­го­за­дач­но­сти на од­ном мно­го­ядер­ном или мно­го­про­цес­сор­ном ком­пь­ю­те­ре (обыч­но это за­тра­ги­ва­ет мно­го­за­дач­ность на осно­ве по­то­ков). Свя­за­но это с тем, что при бло­ки­ро­вании за­да­чи она пе­ре­хо­дит в со­стояние ожи­дания, в ре­зуль­та­те че­го оста­ток про­цес­сор­но­го вре­мени пе­ре­дается дру­гой за­да­че; при этом про­ис­хо­дит пе­ре­клю­чение кон­тек­ста за­да­чи, яв­ляю­щее­ся доста­точ­но ре­сур­со­ем­кой за­да­чей. Ес­ли пе­ре­клю­чение кон­тек­ста про­ис­хо­дит доста­точ­но час­то, мо­жет по­лу­чить­ся так, что при­ло­жение боль­ше вре­мени тра­тит на пе­ре­клю­чение кон­тек­ста, чем на вы­полнение сво­их за­дач.

Со сред­ст­ва­ми син­хрониза­ции с бло­ки­ров­ка­ми свя­за­на так­же та­кая боль­шая про­бле­ма, как вза­им­ные бло­ки­ров­ки за­дач. В про­стей­шем слу­чае вза­им­ные бло­ки­ров­ки за­дач по­лу­ча­ют­ся сле­дую­щим об­ра­зом. Пусть у нас есть два ре­сур­са – A и B, доступ к ко­то­рым за­щи­ща­ет­ся при по­мо­щи средств син­хрониза­ции с бло­ки­ров­ка­ми. Пред­по­ло­жим, что у нас есть две за­да­чи, ко­то­рые хо­тят безо­пас­но ра­бо­тать как с ре­сур­сом A, так и с ре­сур­сом B, при этом пер­вая за­да­ча сна­ча­ла пы­та­ет­ся «за­хва­тить» бло­ки­ров­ку, свя­зан­ную с ре­сур­сом A, а по­том с ре­сур­сом B, а вто­рая за­да­ча – на­обо­рот. При од­но­вре­мен­ном вы­полнении этих за­дач воз­мож­на та­кая си­туа­ция, когда пер­вая за­да­ча «за­хва­ти­ла» бло­ки­ров­ку, свя­зан­ную с ре­сур­сом A, и ожи­да­ет бло­ки­ров­ку, свя­зан­ную с ре­сур­сом B, тогда как вто­рая за­да­ча «за­хва­ти­ла» бло­ки­ров­ку, свя­зан­ную с ре­сур­сом B, и ожи­да­ет бло­ки­ров­ку, свя­зан­ную с ре­сур­сом A. Такое ожи­дание бу­дет веч­ным. Как мы го­во­ри­ли вы­ше, сред­ст­ва син­хрониза­ции – это сред­ст­ва взаи­мо­дей­ст­вия ме­ж­ду про­цес­са­ми, и ес­ли раз­ные за­да­чи «за­хва­ты­ва­ют» одни и те же бло­ки­ров­ки в раз­ном по­ряд­ке, это оз­на­ча­ет, что ка­кие-то из за­дач на­ру­ша­ют про­то­кол взаи­мо­дей­ст­вия ме­ж­ду за­да­ча­ми.

Бло­ки­ров­ки на пе­ре­кры­ваю­щих­ся под­мно­же­ст­вах уз­лов

Функ­ции global:set_lock/1,2,3 и global:del_lock/1,2 по­зво­ля­ют «за­хва­ты­вать» и «осво­бо­ж­дать» бло­ки­ров­ки, за­дан­ные иден­ти­фи­ка­то­ром на мно­же­ст­ве уз­лов, оп­ре­де­ляе­мых поль­зо­ва­те­лем. Иден­ти­фи­ка­тор бло­ки­ров­ки – это па­ра, со­стоя­щая из иден­ти­фи­ка­то­ра ре­сур­са и иден­ти­фи­ка­то­ра сто­ро­ны, за­пра­ши­ваю­щей бло­ки­ров­ку (в ка­че­­ст­ве иден­ти­фи­ка­то­ров мо­гут вы­сту­пать лю­бые объ­ек­ты язы­ка Erlang). Мо­жет встать во­прос: а что бу­дет, ес­ли по­пы­тать­ся за­хва­тить один и тот же ре­сурс дву­мя раз­ны­ми сто­ро­на­ми на двух раз­ных, но пе­ре­кры­ваю­щих­ся под­мно­же­ст­вах уз­лов? На­при­мер, мы де­ла­ем вы­зов global:set_lock({res_id, side_id1}, [‘n1@stdstring’, ‘n2@stdstring’], 0), ко­то­рый воз­вра­ща­ет true. Что в та­ком слу­чае вернет вы­зов global:set_lock({res_id, side_id2}, [‘n2@stdstring’, ‘n3@stdstring’], 0)? Ес­ли бы мы за­пра­ши­ва­ли бло­ки­ров­ку {res_id, side_id2} толь­ко на уз­ле n3@stdstring, мы, оче­вид­но, ее «за­хва­ти­ли» бы (и вы­зов вер­нул бы true). Од­на­ко мы за­про­си­ли бло­ки­ров­ку на уз­лах ‘n2@stdstring’ и ‘n3@stdstring’; а з­на­чит, бло­ки­ров­ки толь­ко на уз­ле ‘n3@stdstring’ нам не доста­точ­но. Бло­ки­ров­ку {res_id, side_id2} на уз­ле ‘n2@stdstring’ «за­хва­тить» нельзя (она «за­хва­че­на» дру­гой сто­ро­ной). Со­от­вет­ст­вен­но, нельзя за­хва­тить эту бло­ки­ров­ку и на уз­лах ‘n2@stdstring’ и ‘n3@stdstring’. Тогда вто­рой вы­зов global:set_lock/3 вернет false.

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

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

Ис­поль­зуе­мая в язы­ке Erlang мо­дель мно­го­за­дач­но­сти бы­ла вве­де­на не толь­ко для уп­ро­щения раз­ра­бот­ки мно­го­за­дач­ных при­ло­жений, но и для ре­шения ря­да про­блем, вызванных ис­поль­зо­ванием по­то­ков в ка­че­­ст­ве за­дач. По­нят­но, что при та­ком под­хо­де у нас не бу­дет та­ких про­блем, как гон­ка за ре­сур­сы, или про­блем, свя­зан­ных с небло­ки­рую­щей син­хрониза­ци­ей. Ос­та­ет­ся, по­жа­луй, один во­прос: воз­мож­на ли вза­им­ная бло­ки­ров­ка за­дач в язы­ке Erlang? Мы уже го­во­ри­ли, что вза­им­ная бло­ки­ров­ка за­дач про­яв­ля­ет­ся тогда, когда на­ру­ша­ет­ся про­то­кол взаи­мо­дей­ст­вия ме­ж­ду за­да­ча­ми (по­ря­док «за­хва­та» бло­ки­ро­вок). У нас бло­ки­ро­вок нет, но мы по­про­бу­ем реа­ли­зо­вать вза­им­ную бло­ки­ров­ку за­дач, ис­поль­зуя тот же прин­цип: од­на из за­дач бу­дет на­ру­шать уста­нов­лен­ный про­то­кол взаи­мо­дей­ст­вия.

У чи­та­те­лей мо­жет возник­нуть за­ко­но­мер­ный во­прос: а за­чем нам пы­тать­ся реа­ли­зо­вать вза­им­ную бло­ки­ров­ку за­дач? От­вет оче­ви­ден: зная, как это по­лу­ча­ет­ся, мы, на­вер­ное, бу­дем из­бе­гать та­кой си­туа­ции. Да­вай­те при­сту­пим к реа­ли­за­ции: пусть пер­вая за­да­ча по­сы­ла­ет со­об­щение a вто­рой за­да­че и ожи­да­ет его же в от­вет, по­сле че­го по­сы­ла­ет со­об­щение b и ожи­да­ет его же в от­вет. А вто­рая за­да­ча де­ла­ет все на­обо­рот: ожи­да­ет со­об­щение b и по­сы­ла­ет его же об­рат­но, по­сле че­го ожи­да­ет со­об­щение a и по­сы­ла­ет его об­рат­но. Вот при­мер, реа­ли­зую­щий это по­ве­дение:

fun1() ->

receive

{init, Process2} -> io:format(“init message ~n”, [])

end,

io:format(«process 1, send message a ~n», []),

Process2 ! {self(), a},

receive

{Process2, a} -> io:format(«a message on process 1 ~n», [])

end,

io:format(«process 1, send message b ~n», []),

Process2 ! {self(), b},

receive

{Process2, b} -> io:format(«b message on process 1 ~n», [])

end.

fun2() ->

receive

{Process1, b} -> io:format(«b message on process 2 ~n», [])

end,

io:format(«process 2, send message b ~n», []),

Process1 ! {self(), b},

receive

{Process1, a} -> io:format(«a message on process 2 ~n», [])

end,

io:format(«process 2, send message a ~n», []),

Process1 ! {self(), a}.

Ес­те­ст­вен­но, что функ­ции fun1/0 и fun2/0 экс­пор­ти­ру­ют­ся из неко­то­ро­го мо­ду­ля, на­при­мер, из мо­ду­ля interlock_ex. Так как функ­ции бу­дут основ­ны­ми те­ла­ми двух неза­ви­си­мых про­цес­сов, то пер­вый про­цесс дол­жен как-то уз­нать об иден­ти­фи­ка­то­ре вто­ро­го про­цес­са: для это­го пер­вый про­цесс по­сле его соз­дания ожи­да­ет со­об­щение ви­да {init, Pid2}, где Pid2 – иден­ти­фи­ка­тор вто­ро­го про­цес­са. Те­перь да­вай­те за­пустим наш при­мер и по­смот­рим на ре­зуль­ти­рую­щий вы­вод (из функ­ций fun1/0 и fun2/0). Для это­го за­пуска­ем сре­ду вы­полнения Erlang, по­сле че­го соз­да­ем оба про­цес­са: Pid1 = spawn(fun interlock_ex:fun1/0) и Pid2 = spawn(fun interlock_ex:fun2/0) (ес­те­ст­вен­но, что мо­дуль interlock_ex дол­жен уже быть от­ком­пи­ли­ро­ван). И, на­конец, оста­лось толь­ко со­об­щить пер­во­му про­цес­су о вто­ром, по­слав ему со­об­щение {init, Pid2}: Pid1!{init, Pid2}.

В ре­зуль­та­те в кон­со­ли сре­ды вы­полнения Erlang мы по­лу­чим со­об­щения “init message” и “process 1, send message a” (сре­ди со­об­щений бу­дет так­же ре­зуль­тат вы­чис­ления вы­ра­жения Pid1!{init, Pid2}). Вид­но, что вме­сто пол­но­го цик­ла об­ме­на со­об­щения­ми все за­кон­чи­лось на ста­дии от­прав­ления со­об­щения a пер­вым про­цес­сом вто­ро­му, т. е. на­ли­цо вза­им­ная бло­ки­ров­ка ме­ж­ду эти­ми дву­мя про­цес­са­ми. А ее при­чи­ной яв­ля­ет­ся на­ру­шение про­то­ко­ла взаи­мо­дей­ст­вия ме­ж­ду про­цес­са­ми вто­рым про­цес­сом.

Как уже не раз го­во­ри­лось, вве­дение в язык Erlang мно­го­за­дач­но­сти на осно­ве про­цес­сов Erlang (ко­то­рые ра­бо­та­ют изо­ли­ро­ван­но друг от дру­га, пускай и в пре­де­лах од­ной сре­ды вре­мени вы­полнения), да и са­ма функ­цио­наль­ная при­ро­да язы­ка из­бав­ля­ет нас от та­ких про­блем мно­го­за­дач­но­сти, как гон­ка за ре­сур­сы и по­вре­ж­дение дан­ных. Это спра­вед­ли­во, по­ка мы ра­бо­та­ем с ре­сур­са­ми и дан­ны­ми, внут­ренними от­но­си­тель­но сре­ды вы­полнения Erlang; на­при­мер, объ­ек­ты язы­ка Erlang яв­ля­ют­ся та­ки­ми ре­сур­са­ми. Но стоит на­чать ра­бо­тать с внешними от­но­си­тель­но сре­ды вре­мени вы­полнения Erlang ре­сур­са­ми (на­при­мер, с фай­ла­ми), все пе­ре­чис­лен­ные вы­ше про­бле­мы воз­вра­ща­ют­ся. Дей­ст­ви­тель­но, по­про­буй­те в двух за­да­чах от­крыть один и тот же файл на запись и за­пи­сать ту­да од­ну и ту же пор­цию дан­ных од­но­вре­мен­но; с боль­шой до­лей ве­ро­ят­но­сти вы уви­ди­те, что дан­ные бу­дут пе­ре­ме­ша­ны. По­это­му, как толь­ко мы на­чи­на­ем ра­бо­тать с внешними ре­сур­са­ми, пе­ред на­ми вста­ют во­про­сы о за­щи­те этих ре­сур­сов от од­но­вре­мен­но­го досту­па со сто­ро­ны несколь­ких за­дач (кроме слу­чая, когда все за­да­чи ниче­го не из­ме­ня­ют в дан­ных из внешнего ре­сур­са). Да­вай­те под­роб­нее по­го­во­рим о том, как ре­ша­ют­ся по­доб­ные про­бле­мы.

Наи­бо­лее лег­кий, про­стой и оче­вид­ный под­ход (он же и наи­бо­лее близ­кий к Erlang-way) к ре­шению дан­ной про­бле­мы – ис­поль­зо­вание сер­вис-ори­ен­ти­ро­ван­ной ар­хи­тек­ту­ры (СОА). Дей­ст­ви­тель­но, ес­ли у нас есть внешний ре­сурс (на­при­мер, файл), то да­вай­те осу­ще­ст­в­лять к нему доступ не на­пря­мую, а че­рез неко­то­рый сер­вис, взаи­мо­дей­ст­вуя с ним при по­мо­щи от­сыл­ки за­про­сов и по­лу­чения от­ве­тов. Вполне ло­гич­но, что та­ким сер­ви­сом бу­дет про­цесс язы­ка Erlang, а за­про­са­ми и от­ве­та­ми бу­дут со­об­щения (т. е. лю­бые объ­ек­ты язы­ка). Тогда доступ к внешнему ре­сур­су бу­дет осу­ще­ст­в­лять толь­ко этот сер­вис­ный про­цесс, и ника­ких про­блем с од­но­вре­мен­ным досту­пом к ре­сур­су не возникнет. Ес­ли же в раз­ных час­тях про­грам­мы необ­хо­ди­мо об­ра­щать­ся к несколь­ким раз­ным фай­лам, то вполне ло­гич­но, что в та­ком слу­чае мы мо­жем соз­дать несколь­ко эк­зем­п­ля­ров сер­висов: по од­но­му на ка­ж­дый файл, с ко­то­рым необ­хо­ди­мо ра­бо­тать.

Описанный под­ход, при всех его досто­ин­ст­вах, не ли­шен и недостат­ков. Допустим, мы соз­да­ли сер­ви­сы для ра­бо­ты с внешними ре­сур­са­ми (на­при­мер, фай­лом), но сей­час на­м тре­бу­ется об­ме­н дан­ны­ми ме­ж­ду дву­мя внешними ре­сур­са­ми. Ес­ли мы мо­жем про­чи­тать все необ­хо­ди­мые дан­ные с ре­сур­са ис­точника за один раз, то обыч­но ника­ких про­блем нет: сер­ви­сы досту­па к ре­сур­сам обес­пе­чи­ва­ют ато­мар­ность чтения и за­пи­си, а необ­хо­ди­мость в ато­мар­но­сти опе­ра­ции об­ме­на дан­ны­ми (чтения-за­пи­си) бы­ва­ет не так уж час­то. Од­на­ко ес­ли нель­зя про­чи­тать все дан­ные с ре­сур­са ис­точника, или есть необ­хо­ди­мость в ато­мар­но­сти опе­ра­ции об­ме­на, необ­хо­ди­мо что-то де­лать во из­бе­жание про­блем. Пер­вое, что при­хо­дит на ум, это сде­лать ана­лог бло­ки­ро­вок: спе­ци­аль­ную па­ру со­об­щений, пе­ре­во­дя­щую сер­вис для досту­па к внешнему ре­сур­су в мо­но­поль­ный ре­жим ра­бо­ты и об­рат­но. К сча­стью, де­лать это­го для ка­ж­до­го сер­ви­са не на­до: мо­дуль global пре­достав­ля­ет средства реа­ли­зации та­кой функ­цио­наль­ности. Для ра­бо­ты с та­ки­ми бло­ки­ров­ка­ми ис­поль­зу­ет­ся по­ня­тие «иден­ти­фи­ка­тор бло­ки­ров­ки» – это кор­теж из двух эле­мен­тов: иден­ти­фи­ка­то­ра ре­сур­са и иден­ти­фи­ка­то­ра сто­ро­ны, за­пра­ши­ваю­щей бло­ки­ров­ку. В ка­че­­ст­ве та­ких иден­ти­фи­ка­то­ров мо­гут вы­сту­пать лю­бые объ­ек­ты язы­ка Erlang (су­ще­ст­ву­ет доста­точ­но неболь­шой спи­сок ато­мов, ко­то­рые не ре­ко­мен­ду­ет­ся ис­поль­зо­вать в ка­че­­ст­ве иден­ти­фи­ка­то­ров ре­сур­сов).

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

По­сле это­го неболь­шо­го об­зо­ра взглянем на на­ших ге­ро­ев. Для «за­хва­та» бло­ки­ров­ки у нас есть сле­дую­щие три функ­ции: global:set_lock(Id), global:set_lock(Id, Nodes) и global:set_lock(Id, Nodes, Retries). Функ­ция global:set_lock/3 пы­та­ет­ся уста­но­вить бло­ки­ров­ку с иден­ти­фи­ка­то­ром Id, об­ласть дей­ст­вия ко­то­рой рас­про­стра­ня­ет­ся на уз­лы Nodes, с ко­ли­че­­ст­вом по­пы­ток уста­но­вить бло­ки­ров­ку Retries. В ка­че­­ст­ве зна­чения для чис­ла по­пы­ток уста­но­вить бло­ки­ров­ку мож­но пе­ре­дать лю­бое неот­ри­ца­тель­ное чис­ло или атом infinity. Функ­ция global:set_lock/3 бу­дет пы­тать­ся «за­хва­тить» бло­ки­ров­ку не бо­лее Retries раз, впа­дая на неко­то­рое вре­мя в сон в слу­чае неудач­ной по­пыт­ки
Бло­ки­ров­ки: Уп­ро­щен­ный сце­на­рий

Обыч­но ра­бо­та с бло­ки­ров­ка­ми ре­сур­сов вы­гля­дит так: мы «за­хва­ты­ва­ем» бло­ки­ров­ку, вы­пол­ня­ем некую функ­цию (или по­сле­до­ва­тель­ность дей­ст­вий, сво­ди­мую в некую функ­цию), по­сле че­го «осво­бо­ж­да­ем» бло­ки­ров­ку. Конеч­но, мы мо­жем не смочь «за­хва­тить» бло­ки­ров­ку: тогда дальней­ших дей­ст­вий не пред­ви­дит­ся. Что­бы уп­ро­стить этот сце­на­рий, в мо­ду­ле global оп­ре­де­ле­ны функ­ции global:trans/2,3,4. Функ­ция global:trans(Id, Fun, Nodes, Retries) пы­та­ет­ся за­хва­тить бло­ки­ров­ку с иден­ти­фи­ка­то­ром Id на уз­лах Nodes Retries раз. Ес­ли «за­хват» осу­ще­ст­в­лен, вы­пол­ня­ет­ся функ­ция Fun, бло­ки­ров­ка «осво­бо­ж­да­ет­ся» и воз­вра­ща­ет­ся ре­зуль­тат вы­полнения функ­ции Fun. Ес­ли «за­хва­тить» бло­ки­ров­ку не уда­лось, воз­вра­ща­ет­ся атом aborted.

(ес­ли зна­чением Retries яв­ля­ет­ся атом infinity, то функ­ция global:set_lock/3 бу­дет вы­пол­нять­ся, по­ка не «за­хва­тит» бло­ки­ров­ку). Эта функ­ция вернет атом true, ес­ли бло­ки­ров­ка бы­ла «за­хва­че­на», и false – в про­тив­ном слу­чае. Функ­ция global:set_lock/2 эк­ви­ва­лент­на функ­ции global:set_lock/3 со зна­чением Retries, рав­ным ато­му infinity. Функ­ция global:set_lock/1 эк­ви­ва­лент­на функ­ции global:set_lock/2, толь­ко бло­ки­ров­ка оп­ре­де­ля­ет­ся на всех уз­лах. Для осво­бо­ж­дения бло­ки­ров­ки слу­жат сле­дую­щие две функ­ции: global:del_lock(Id) и global:del_lock(Id, Nodes). Функ­ция global:del_lock/2 по­зво­ля­ет осво­бо­дить бло­ки­ров­ку, за­дан­ную иден­ти­фи­ка­то­ром Id, на уз­лах Nodes, а функ­ция global:del_lock/1 де­ла­ет то же са­мое на всех уз­лах.

Се­го­дня мы по­зна­ко­ми­лись по­бли­же с та­ким яв­лением, как син­хрониза­ция за­дач (и с ее реа­ли­за­ци­ей в язы­ке Erlang). Мы уви­де­ли, что ниче­го страш­но­го в син­хрониза­ции нет: доста­точ­но быть ак­ку­рат­ным и со­блю­дать при­ня­тые про­то­ко­лы взаи­мо­дей­ст­вия ме­ж­ду за­да­ча­ми. А в сле­дую­щем но­ме­ре мы начнем прак­ти­кум, по­свя­щен­ный соз­данию мно­го­за­дач­ных при­ло­жений. |

Персональные инструменты
купить
подписаться
Яндекс.Метрика