автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Программные механизмы повышения отказостойкости распределенных систем

•г о ~~ 1 э, 3-■ 0 ' л 15 "

Академ ¡я наук УкраТни 1нститут к!бернетики 1мен1 В. М. Глушкова

На правах рукопису

ГОСТ1ЛОВА Св1тлана Валентишвна

УДК 681.324

ПРОГРАЛ\Н1 МЕХАН13МИ ПЩВИЩЕННЯ В1ДМОВОСТ1ЙКОСТ1 РОЗПОД1ЛЕНИХ СИСТЕМ

05.13.11—математичне и програмне забезпечення обчислю-вальних машин, комплекав, систем 1 мереж

Автореферат дисертац1'1 на здобуття ученого ступеня кандидата техт'чних наук

КиТв 1992

Робота виконана в 1нститут1 юбернетики ¡меш В. М. Глуш-кова АН Украши.

Науковий кершник: доктор техшчиих наук, професор

Н1КШН А. I.

Офщшш опоненти: доктор техшчних наук ПАРАСЮК I. М.,

кандидат техшчних наук ФУРС1Н Г. I.

Прсшдне шдпрнемство: КиГвський псштехшчнни ¡нститут.

Захнст вибудеться «г^^»—--19^$. о год.

на засмданш спещал!зованоТ учено! ради Д 016.45.01 при 1нститут1 юбернетики ¡меш В. М. Глушкова АН УкраТни за адресою:

252207 Юпв 207, просп. Акаде\пка Глушкова, „40.

3 диеертащею можна ознайомитися у науково-техн!чному арх1в1 ¡нституту.

Автореферат розгсланин

Учений секретар спец1ал1зовано1 учено! ради

СИНЯВСЬКИИ В. Ф.

&\галша характеристика" роботи.

АКТУАЛЬШСТЬ ТЕМИ. РозподЦан! системи (PC) обробки дагая, що функщопують у меренному серо.човиц! надають можлго1сть використовувати п-/ро;«а спектр 1нформац1йшд i. обчислювальних послуг, мають б!льш високу над! £н i сть I продуктавн1сть < можливиа паралэл!зи сбробки), а такой наближують до користувача pisui тип i комп'1сггор1в. Вэщодэвно народався i розвиваеться иауковий нзпрятогс, псз'язапкз з розробкою технолог 12 розпод!лэноI обробгси дашпс. 1снуе рдц проблэм, що вшикли при cnpoöl досягга указаниг потенцлшяг ггзрэваг PC i пов'яззних з ускладдэшяя махан!зн1п кзрувапня розпод1лэними двцэятрал1зованкми ¡нформаЩйшяи продосаш. При цьому особливу роль в!д!грас створеяня мохая1зм1в, до забезгочуватимутъ В1дновост1гк1сть PC.

В дан in робот! в I д".оео ст1гк1 сть означав здатн1сть розпод!лвноI системи збор!гати cuco гграпопдатаi сть, а такса цШстнЮТь 1нфоряацП, нр '¿находиться в рсзпод1хвч1х базах даних (РЕД), при в!даов1 деяко! п!дмнолатк ксшояент1в. В1дмовост1йзс1сть - vo та наобх1даа влгстив!сть. без íticoI практично иеиомивэ гаранту юти допусткгз! окспдузташпн! харзкгориатихи PC.

Поз'язан1 з данкм напряиком тооротитн1 пробЛзки були розглядут! у публ1кац1ях в!тчеззяшк та заруб!жких автор!в, таких, як Лешорт Л., rapcia-Uo^ina Г., Pothí Дх., Вальтер . Б., Морген С., 31нов'ев Е.В., Кал1н!чзкко Л.A., Híkítíh A.I-. та 1нш1. Нэ зваааоти на досить валику к1льх1сть публ1кац!я та отримшЦ Ictothí результата в дан!а галуз1, кео5х!ди1 шдальш1 теоретичн! досл1дшпля i прзкгичн! розв'язаннл багатьох питань. Вир1пэнню дэяютх з них присвячена дана робота.

МЕТА ДЙСЕРТАЩЯН01 РОБОТИ - дослшкзння i розвиток иодвлвя M0X3HÍ3M13 забеэпзченЕЯ "Мдаовост12ксст! PC в уновэх пора-тельпого знконання транзакхяа, ■ а такси резробка на основ! отримаяих рззульгат!в злгор}ггм!в, що у сухупност! рэзл1зують збэражзяня цШсяое-п Í ТфЗНЭЗДотпоеггi ГБД.

Поставлэа1 так! окремi задач!:

- узагальниги мехенгзми габездачення в1даозост!йкост1 PC в умовэх пзрзлэлького вкковання трзнзакц1а;

- побудузагги та обгрунтувати даяк1 нов1 влгоритаи збэрожэння 1 в!дгвороння ц1л!сност1 РБД у вкладку в!дмов вузл!в KopQHi для р!сних ■ практично важливих припущэнь в1дносно умов робота PC, як1 б в1дпов1дали сучасиому piBHOBi над1£ност! тэхн1чних компонентов PC;

■ - розробиги програмниа пакэт моделшаЕня систем управл1ння транзакц1ями (СУТ), якии би забвзшчував знаходяення найб1льш важливих кртгерПв якост1 такого . управл!ння.

НАУКОВЛ' НОВИЗНА. У дасорггац1ин1й робот! розвинвн1 та узагальнен1 кэхапТзми забездачення в!дж)бост!йкост! PC I на ц1£ ochobI розроблениа ц!лиа ряд алгоритм 1 в. Новини с:

- нодиф1кованиа WT - протокол ф!ксац11 транзакцП для N вузл1в у ранках модзл1 слукби в1дмовост1акост1. цо зКЗрана в едину 1срарх1чну систему;

- неблохуючиа WT*- протокол трьохфазно! ф1ксац11, , ст!Яяиа до дов1лышх множинних в!даов вузл!в;

- модаф1кований кехан1зм управл!ния зарезврвованшш данигш в рамках 1срарх1чно1 ыодел1 слу^йи в1даовост10кост1;

узагальноння алгоритму "мовэнталъного зн1мку" глобального стану ¡горев!, за Лампортом, на основ! "пэрофарбування" вузл!в;

- иодаЛ кован! протокола фориування контролших точок в РБД, що скорочують час простою PC;

- алгориш вори1>!кац11 глобального плану викоиання субтраязакхЦй в!дносно кого сер!ал1зуемост1 при мзтод! блокування.

ПРАКТИЧНА ЩШПСТЬ РОБОТИ полягае у розробц1 програмно! оболонки для моделювання СУТ, для доел!даоння динам1ки практично важливих процос!в 1 ситуаЩа при управл!нн! паралэл!змом транзакц1& ! виявлэнню важливих критер! !в якост! такого кврування.

АПРОБАЩЯ. OchobhI результата дисортащйно! робота допов!дались 1 обговорювались на 3-а ВсесоюзнШ конфврвнцП "Живуч!сть 1 реконф!гуращя iпформацi£ао-обчислювальних i квруючих систем" (м.Севастополь, 1891р.); семинарах науково! рада АН Укра!ни з проблема " КЮернетика"; Конфоренцп молодих учеши 1 споц1ал1ст1в 1н-ту Мборнатики ¡м.

В.М.Глушкова АН УРСР (м. Ки1в, 1988р.); 0-а Всосоюзл1й копфоренци "Обчислксаяья! мэряя! гсоиутацП пакет)в" ( и. Рига, 19833.}

ПУБЛКАЦ11. За теисз дасертзцП опуйлИсозано 4 нзукоя! робота.

СТРУКТУРА ТА ОБСЯГ РОБОТИ.

Дж»ртац!яна робота склпдаеться 1з вступу, чотигьох роздШв, висновку, списку д1тератури 1 додатку. Робота вшсладзна на 123 сторгяках капипописпого тексту, и1сппъ 27 наюнк1в. Б1блЮгрзф1я складаеться 3 ~ 98 наакенувань.

3MICT РОБОТИ.

У Еступ! обгрунтсвуеться актуален ¡сть тега i фориулюиться коякрвтн1 задачi досл1даэння.

У горному розд1д1 списан! сучасг.1 зспэкти розвигау тз застосуванкя сбчжхяавальних норе:х 1 в гв'язку з c« noBi задач1 управл1ння в PC, дан! визиачзння основних понять, коротки» опгяд Шдход1в до побудрвз* мэхзи!гм!в гзбозтчення в1даовост!йкост1 PC, що дозволяють эберзгтл ксждивЮТь користувэння иеп при наявпост1 в!даоз техп)чних гбо прогргмних sacodiß. 1Ьобх1дно б;дэпзчите, га шсгззн1 К9хан1эмя розиод1лзн! на ECix р.'пяях сдуяб i протокол1в нодол! ВОС-МОС, причоку на приклтдцому р!ая1 вопи, в своо черту, нсжуть бута подан! окремок iерзрхi-т::оя нодалаэ. Сгиз на ц1я модел1 1 и компонентах зссеродаен! доол1дшякя, г;о • з1дображен1 в робот!. Езсготвеня того та lnaoro шхзтг1-гму зэбозшчвння в!даоБост1йкост1 FC заложить rat в1д характеру в1даони твгяJ ион компонента иэрвя!, тзк i П1Д фззи обробки окремих паралххлъно працкючгас тргнзакц1й, ягсдх 1 статно торхиулася в!,-?гава. В cyicyiEtocrl мвхзн!з?щ повили! ьаЗоашчоти д&еют» квидаз т'лълятп в!,2?50би, забозпзчетн yeninse ЗЭБврЕЗНЛЯ тих трзЕзакц1а, ЙХ! ксхуть бути "врятован.1 , в1дк1Т тяг трапзакШя, як! "орятован!" бута аэ иояуть, 1 забездачоння подальоо! робота в умовах в1дйови. ОСНОБН! ГфОбЛЗМИ ПрП ЦЬОМУ - ПОбуДСВЗ СИСТЭМИ КОНТрОЛЬНЕХ точек РЦД, згбвзшчгэння сер!ал1зусмост! глобального шгну Екконання субтранзакц1й, узпщязка робота з зарззэрвованми данями. Ватр-лэi аяьн!сть роза'язэпвя данкх пробам зуков.*зяа

прицусрнняк, до управл!ння мережами 1 ЕБД, яке на сьогодн!шн1 е - загзльнопраяняпм, доцэнтрал1зоваЕв. В к1нц1 розд1лу формулкоться конкротн! задач1.

У другому роздШ систематизовано ряд кехашзм1в забезгочення в1даовост12кост1, що були запропоновап1 в р1зяих цубл!кац1ях, 1 запропонована 1х едина icpapxi4Ha модель. ' При цьому ввд1лязоться т! фази функц1онування мэхан1зм!в на вс1х р1впях lcpapxll, як1 пов'язан! з • еооох1дц1стю досягнення узгодаення д1й в децонтралi зованих PC. 1акэ узгодаення (англ. nteractive cons»tency>, зведоне Лзмпортом в ранг одн1е! з парадигм PC, 1 е основою для розробки р1зшп: конкретних алгоршн1в у рамках зазначених иэхан1за1в.

Будзмо • називати гошшюю пропв деяко! вэсправност! (в1даови) компоненту системи, якиа <2иксуеться 1шпши И компонентами. йшон1ном тврн1ну "помолка" можна вважати . торм!н "нерегулярна сигуац1я". В1даова одного 1 того ж техн1чного компоненту Ей! коке бути причиною- р1зних нерегулярних ситуац1а. Так, наприклад, нвсправнЮть процэсора мои» проявится у тому, що дана ЕОМ пэрестано реагувати на пов1домлещш 1нших ЕОМ мерен! ( мовчазниа вуэол), 1 в тому, що ЕОМ в!дпов1дае на пов!дсмлэння, ало видас хкбну 1нформац1ю. Ми припускаемо, що при в1дмов1 ЕОМ у дрякому вузл1 корояi даниа вузол не видае 1ншим ЕОМ н1яко1 ¡нформацП до моменту свого в1дновлання. В л1тератур1 ця властав1сть в1даови характеризусться, звичаяно, як властив1сть "fail stop".

Припускаеться, що мережа, на основi яко! побудована PC, забозшчуе так1 характеристики, як бозпомилкова передача пов1домлонь м1и будь-якюш двома справнши вузлами та гаранты 1х отримання по черз! в1дправжння. Службу в1дмовост1йкост1 зображуско як таку, що мае чотири р1вня.

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

В1ртуальне к1лыр утворюеться таким чином. Вузли мереж!

нукэрувться П0СЛ1Д0ВНЕ£И НЗТУраЛЪЕКЯИ ЧЕСЛЗМИ u.Nb Ця нукэрэц1я i визначйв Ki-лыгэву впорядковаи! иъ вуаг1э шрст! вПдяо з в1дасшяикм сл1дувэпвя: к <- Ck^Omod M. При шлсонанн! дгного в1дноЕвнля вуяол <к+0 будэи лаггазтк старшим, а вузол к- колщеи а ц1й пар! ( туг i ятага 1мэнуватимэмо вузсл яого яс;.таром у Б1ртуальксчу :с1лып ). ВХДЗНЗЧИМО, ЩО НОМОрЧ ПрИСЗОКХГЬОК ПуЗДЗИ ДОП1ЛЬИО, МС1ШП30. з урахуванням прагматичшх шркувань, наприялад, гетод-тг« я правила: два вуз.га з пос-йдовнкки некзргкн но пгжтал! о'ути западго далвта ро эталонал1 одая 1Пд одаого зз к1льк!ств прон1жниг трзвзипжх вуол1в. Отривану зг1дчо з вездзноп Kljsbi^sro» Епорядкован1стя мпгжязу' вузл1в йудеко нзз:-азп*; Б1ртуальЕ:к :г1льцэм.

Базовиа протекал р!пля в1ртузлълого к1лы5Я скгадаеться з' дзох оу0протокол1в CONTROL i aViíGE.

Субпротокол COHTRCL. Бузол к з1дпрзвлйе го п'ргуалълежу к1лы«> "иг>*-вэз1д0яя9ння зузду (;<*-1У ' ЮТтэрвалытиа

тактар на гор i од Tsenoer, цэ в1до£53 ус!и вуз-гаы мт-рий. Кожнэ "|*»"-поа1до.члзЕ2Я тз тгкяасов.у м1тку, /сз БЁдаовЬтае rnpei í табляц1 про стан e^jüü, ет дозводяе вузлок кор<эгуваггн oriol до стрнязкия гдено! узгодюноГ

Doncií. Коля вузая Сх+В crrpzwyc -позi-.пдзняя, в1к шикая )нт0рзальЕШ таггюр пз пор í од Тсемтrol- камакаэ-яо допустямкг дар i од м1з надаодрэщятгк дзет "up"-еяз]дочл?яь: Tcontrol = Теёюп* + Lmax - Lî-bn. да Lmax - магкаиальнив чао. гародзч i шв1;и;«иэяня м1а дт>сиа будь-нигзхи вуаззми, Lí-n" -aiHiaaaBM час гаредзп!.

ЯкщЧ ново "ир"-пов1дв:гл?ппя на надияию в!д вузлз к протягш цього 1нтерзалу часу, то тзакэр Tcóntrol спрацьоЕуе. Зузаг к ВЕгягастъся кздэстугоим, i Тя)ц1гэться субпротокол CílAHS-I. лкяз короктус таСлЩО стаяiв (STATE-TABLE), № мi стать 1£фориац1ю про 1 sal вузли.

Лругкй piBOEL. 23323MD pi sirsы WATCH-CAyVÍT. WATCH-'-^',KÏ3

оргзз1зуе сл ■ даувззгя за стяноя .,юя1М.-г,,'х ьузл!п, задание ирюслздЕИ« npoi!pc;;:î, i "дсгязз1дзс" про будь~ях1 с.ч!тт стгэд дгному прикладному iipoipcy. Г!ри цьо w? WATCH-a¿yE33, щиродао, спирасться на !Ефораац!о, отриазну э!д в1ргг/алг>Ег.го к1льг'л. i' роэд1л1 эапропоаовзз! î обгрузтоваэ!

в

вкршалън1 правила виЗору ново! ворсi I STATE-TABLE кошка вузлоа. Запропоновзниа алгоритм виЗору нових вере!а STATE-TABLE га снования на такому прицукзнн1: у вс1х вузлах зааходеться годанники, показания яких но ножуть в1др1знятися один в!д одного 61лыео н!ж на е. одиниць часу.

V i,k ( ti - tk ) з

дэ ti, tk -показания годкнник1в вузла i i вузла к.

Пров1вш шрау фазу субпротокола CHANGE - фазу вбору пэдостатньо! 1нфорыацП, координатор (вузол к) поы1чае ворсId поточниа часом свого вузла, тобто: PTS - tk.

Шхаа в доякиа вузол к посл1довно пришпли дв1 iстогно р!зн1 Bopci i STATE-TABLE з ф1вичники тимчасовими м1ткаии PTS 1 PTS' i вэхая PTS >PTS, тод1:

I) ягацо р1з1шця Шы циш тимчасовиыи и 1 псами зэдовольняе шр1вн1сть

¿5 - PTS' - PTS £ 2( Lmax - Lnin),

то приамасться варс1я STATE-TABLE, позначена PTS";

2) якцо neplbhictb eo виконуеться, то необх1дно повторно викопання субпротоколу CHANGE;

3) якщо пришили ДБ1 одааков1 взрс11, аяэ з р1знмми поточнк.и м1 пса ии, то во pel я приамаеться 1 позначасться mltkob PTS'.

Трвт1й р1вонь являс собою кохан1зы управл1ння ф1ксац1ею транзакции, шбудованиа за класичним протоколом двохфазно! ф1ксац11 ( 2РС - протокол). BiH використовуе сорв1с WATCH-слуяйи як з боку вузла-координатора (ТМ). так 1 з боку вузла-виконавця (DM). Кокай з них зворггаеться до WATCH-служби для елдкуваыпя за зм1пою стану вузл1в, цо боруть участь у виконзтП транзакцП. Завдяки МАТСН-слу>йб1 як вузол-коорципатор, так 1 вузли-виконавц1 можуть у процэс! обребки тракзакц! i роагувати на в1дмови. Тобто в 2РС-протокол1 шрадЗачена поводlinca ТМ i DM на випадок зяаходаенля в1дйов WATCH-службою.

У роботi запропоновакиз WT-протокол для й-вузл!в, який дозволяе скоротити к1льк1сть видашэс пов1дснлань 1 стан i в вузл1в порiвкянно з протоколом Вальтера, kic*3 буэ узягий за основу досл1дмэння . Так, ка пэра is фаз! робот.! протокола вузол-винонавепь при ноиоазквсот! пиконання субтраяэакц1 i сам ануляс II, пороходигь в стап OACXOUT 1 Btvac пов i домлэнля "в". У друг is фзз1 протокола вводиться додатковиа стан чэкзнпя вузл!в-вккопавц1в WAIT, лра жому в!д5увзсться узгодяэЕзя 1х лодалсих д]а. Вводиться додатковиа огоратор з кетоз розмежузання ноэктмыуз: станШ DMi шсля ф!ксацП збо апулювзння субтранзакц1й. Цай протокол поряд з указано» горевзгси- несгПккиа при мнсипшагсс в!дновах DM або при одно^асШЯ Di^raBi ТМ 1 DM- У гв'язку з цкч протону сться ноблокувчна WT' -протокол, (ггргс«ззи2 на бзз1 ViT-протокола способом введэння додаткового пов1домлэння "wacк", яка нздслгаеться координатором ТМ У cranl готсвяост! до ф1ксзцП СОЖ1Т Шсля стриианвя пов ¡дог«.'ля "дек" в!д yclx вузл!в-виконавц1в, 1 скороченням дзяпиг блттзьпнх за пм 1 стоя стан!в вузл!в. У роЗот! оп -;сгн1 вс1 ?:с.ч-т,'.в! пэрэходи глобального стану при виконзшп у/Т'-щ.-отохола 1 сх5груптсвз.»1э короктн!сть остзяньсго.

Четвертая р!вонь - р!вянь рэзорвовают даннх, призпачоннкн якого е упрзвл1Еал розарняик! данюет. Заувазяко, '¿р в npoqsci кзруванзя вузли, як! ¡¿ЮТлть 1дззтичну 1Ефорнац1я, сл1д-^тоть за за 1 вами стан Id одой одного тэкоз ва дрпокого» WATCH-cxysia. У роздШ ззпропояавания ¡годиф1яоезт:а алгорэтп, суть якого полягас у такому. Для кожного ззре.тпрвоз-'зяего 1?4«рмтЛйного об'есту одна с коп!а оголоауеться ockcbho?j (prshary сору). 'Шелл вм!ни oceoehol коли список np02SU»hjdc 5м1н (IL) надсялзсться до вугШв 1з вторизш^ыя кои1яал ( пра цьоиу п!дгрзнзакц!я знахсдкться у стан) DO}. Остзкя! rosininl в1дпраштпт п1дшэр5?!?.1шя про вкхоиэння д!а, еязяяних в IL. В протигакюиу випгдку { яздо заф1ксоеана в1дмос.э зузлэ !з Бторинноо коп!сп) вуаол з основной icon!ся залам'irrcsye IL У стзб!л1л1а пам'.тП з котов б!дьа п!зпьс! гсго дастгвхи Н9ДССЯЖ20ИУ вузлу 1з вторивноа коп! ею, зшеликзе сл!дк7ванкя за в!дноазэлняы в узла ("\vu") ! ышеуа в!дпов!дага запке в

тэЗл.щю UPDATE-TABLE. Цэй запис к Ютить в с об! ношр вузла, цо визков з лад, 1зкзз1епик на IL. нокер взрсП. п;о повинен бута зберояиним. Шсля цих ман1пуляц1й стан п1дгранзакц1й у вузл! з шраишшаз коп1са зн1ьюзться на READY. Як т1льки вузол 1з вторияною коп 1 сю пэрвходить у стан lip, в1н п0в1д0?1ляз ношр своз! Eopcl I ochobhie КОПИ i BCi BTpa40Hi IL будуть сому гарвдан!. Про в1д:.ову вузла з основною коп!ею вс1 вуали доскгь пвидао д!знахггься в!д у/АТСН-служби. -Шдангаяша вузл1в, як1 sOopiraxrrb вторинн1 коп11, маркирован! як AC1UEL, зд1йснюе mtfip ново! основно! копП, но чокают в1дяоалэкня зазнзченого вузла. Шсля в1дновлэння коли2н1Е вузол основно! коп1I в1дправляе пшрокоыовнкй (сород оло;4знт1в зазначоно1 п1дмноимни) запит про то, дэ тешр з5эр!гаеться основна коп!я, просить над!слати Сому IL 1 пзчинао функцЮнувати уао як вузол, 1цо збвр1гас вторинну коп!». Для обгрунтування корохтЕОсгп цього мзхан!зму . налзаопъ зробити два зауважонпя. По-терсэ, вс1 вузли i3 вторинноа Koniea макггь оды.у 1 ту сану вэрс1ю 1Ефорыац1йного об'екту ( цэ гарантуе марк1ровка ACTUEL). По-друге, тут ве розглядзсться ножлив1сть ФрагкэнтацП Kaposi. Цэ обмежоння на дужо сильно, тоиу z,o у сучасних кэроаах городЗачахггься зарезврвовая1 марпрутк.

Тротт розд!л присвячвний пройгэм1. форнування юзнтрольних точок (CP) в РБД дяя коордкнацИ в!дкат1в локальнкх баз дазшх. Основою для розв'язаяня ц1е! проблэии е 1доя вкзначегня глобального стану PC еляхом 11 "мокэнталъного зп!мку" ( SSS- snaps»ют state). Коротко описаний Лэмшртои SS-алгориты псхгягас у тошу, що на часовиг в1сях, цо ф1ксуетъ подП, як! Екникаэтъ у продасах, проводиться пзрер!з. При цьоку, якцо позначати обиан поз1домлэшшш м1к процзсами стр!лка.\?м, то стр1лки повинн1 пврзтинати цэа шреказ т!хыси зл!ва направо.

Конкретно 83-алгор;гпя пэрадЗачае, цо сшчатку ycl вузла "пофзрОоваи!" в один ксшр ( напршслад. 61ЛИ2 ). Пот1М 1н1ц1кзчка вузол i виконуе процодуру bmihh кольору (procedure color- . сяАмог), цо складаеться з чотарьох стутои1в:

трофэрбуьати вузол i в червоняа кол^р CcolorCD-red);

записать стан вузла Si в стайiльну пам'ять; по yclx випдних каналах в1дправихи попэрэджувальпе пов!домлення v/u;

записати ycl над 1 сланi у вузол 6Ш пов!до:ллоняя по ycix вх1дштх каналах з моменту пофарбування вузла у червспий кол1р до мокэпту надаодкення погорсдаувальтос пов1домлбннь (Wu) по Bcix вх1дши каналах, ятй засв^дчують про те, щр вс1 в1дпоз1дн1 вузли вже горофарбувалкся у чорвониа кол1р 1 записали CBifl стан у стаб1льну пам'ять.

Взшта j—х вузл!в мереш, до отримали поперэдаувальне пов!домлення Wu в!д 1пщ1 агора i, пор!внююггь CBia кол!р i па випадок його розб1жност1 а кольором псперзякувалыюги пов1домлепня вюсояують вжэсписану процедуру colcr . chance .

Шсля того, язе кежон вузол виконав процедуру color.change, в!н продов;«ус роботу в чорвоному ГЮр10Д1 . При 1н1ц1ал1зац1ï наступного моментального зн1мку знову в^дЗувасться шрефарбування вузл1в 1 пов1домлопь в1д них у 61 лил кол1р. За значимо, що кол1р вузла 1 його пов!домлэкня но носе зм1стопного навантаження. Кол1р використовусться в даному випа,цку т1лыш для моментального зц 1 мху стану вузл!в як своер1дно! м!тки, яка ио::«э розмежогувати гюрюди (етапи) запису стану PC у процэс1 П безгарервно! робота.

В роздШ проБЭдано досл1даоння корекгност1 SS-алгоритму. Обгрунтовухлься так1 тзерджоння:

черговв шрофарбування ззк!нчуеться за ск 1 нчонниа час; якщо в процэсi шрефарбування один або докiлька вузл]в по CBOia IninlaTiîBl викликаять одаоямвнния процэс, то ij) но зм1юое результату SS-алгоритму;

якщо в черговому процве! шрефарбування один або двк1лька вузл1в по CBOïa 1н1циатив1 вигсличуть протиложниа процэс пэрефарбування ( наступниа, на ïx думку, за черговим), го цэ не .порошкодить зак1нченни чоргоаого процэсу.

Дал1 розглядасться дана процедура на приклад! морож1 з чотирьох вуз.л!в i проводиться пор1Вняльний анал!з SS-алгорнгму з алгоритмом ф1ксацп глобального стану в СУТ. SSS можна розглядати як глобальну коптрольну точку (GCP) PC. Одаак використання SSS як GCP пор.уиуе можлигисть В1дкату

т!лыш у в1даовлон1а частин1 РС, якдо при цьому зб9р1гасться цШсния стан РЕД. Кр1м того, створоння 6СР штробуе ¡коротко I синхрон ЮацП процэс!в в РС ая да зупинки вс!е! системи (що моей бута недопу стадам в системах рэальпого часу).

Зг1дао з розшвсюдаэпим п1дходои, процэси форнують СР шзадэино о дал в!д одаого 1 запзм'ятовуять 1х у стаб1лън1а гам'ят!. У випадку в!дмош процэси повинп1 зпаати шеупзрочву ннояашу контрольнкх точок сэред сформованих. Система в1даоаляс 1 ростартус в1д ц!е! мноккни контрольных точок.

Цзй П1дх1д як головцу ваду к ¡стать в с об! пебвзпзку "ефзкгу дом!во". В роздШ запропонован1 два ахгоритыи простановки СР. як! не п!ддяг<ялъ вплшу "ефекгу дом ¡но" I на горедЗачаэть просто» РС, а такш так!, цо змэнщуоть ( пор ¡вняли о з Б1доашЕа ) к1льк!сть транзакц1а, як1 в1дкочу»ться.

Пэрикг алгоритм полягае у простздовц! Еозаюхшкх автономии* тютасових 1 посПаних СР. Алгоритм допускас, цо в пам'яг1 кожного вузла вбер!гасться контрольна точка сР1. Сукупв!сть СР в!да1ражас ввдэзазначоцу Евсупэрвчливу мнояазку СР. Алгортгги вюшае так! крокк:

1. Коюан процэс о саиост1йно ставить • додзткову кмггрольну точку АСР2 т!льки зз уаовп, що в!д иоменту створоння останньо! контрольно! ТОЧКИ СР1 да створэпня ново! койтрольно! точки СР2 було в1д1 слано поз!доалвння м 1нсс!гу процэсу р. При цьому перед ютшлм в1даравлониш ПрОЦЭС о горэв1ряе пов!домлвння и на в!рог!да!сть ( наприклад, сдац!альнкм тостувашшм ).

2. До отрицания тдозоркопня "аск" про кадходаэння тв!домл0иня м процэс о н!яких оазрац!а Ее веда ( просПК ).

3. При отригшш! п!дгверкэння "дсх" процэс о зашсус додлткову контрольну точку АСР2 в стаб1льну пам'ять як посгпвну контрольау точку СР2 ! видучае пошродшэ контрольну точку СР1 -

4. Процзс р, ккие отрииаэ гюв1дозь£оння н, зразу а Формуе контрольну точку СР2, в!дправляз ШдгвордаэЕшя "ас*" 1 видучае СР1.

Припустило. що вузол о в1дзм0виз до 0тркмап2я п1дгвердаення "аск", тод1 вгавнониа у прав!'льпост1 пов1домлэння м ( див.п.1 алгоритму ) В1К повортасться до додзтково! контрольно! точки АСР2, в!дн03лю€ться 1 чокае п!дгвердаення "аск". Прицустимо, що вузол р в!даовш до в!дправлэння п1дтвордкоштя "аск". Ход1 в!п повортасться до контрольно 1" точки СР2, в!дновлюсться ! в1дпрэвляс п!дгвордкення "аск". Якщо ж р в!даотата п!сля в!доравдоння п!дгвордаоння "аск". то тн повертасться до СР2 1 в!дяовлюеться без повторного в!дправленпя "аск".

Для випадку одночасно! з1даови процэс!в о ! р при в!дправлвнн! 1 призом! пов1домл0ешя м можлисе поручения ц1л1сност! системи. Це очевидно на приклад1, коли проще о в1дмовиа п!сля в!дправлояня пов 1 домлшгая м, алэ до створоння АСР2, а процэс р в1дмовив до отрицания пов!домлэння м. Процос о п1сля в!дновлення в1д контрольно! точки СР1 в друге в1дправигь пов1домлення м, а процэс р теля в!днсвлэння в!д СР1 прийме старе 1 ново пов!домлення з короли. Тому вводами обмеження: припустимо, що одночасна вдаова вузла, якиа в1д!слав пов1домлоння, ! вузла, якиа отримав пов1домлення, не нош в!дбутися. Правомочн!сть введаного обможэнпя обгрунтовусться анал1зом достить просто! марк!всько! кодэл1.

Таким чином, алгоритм, що дае несупэрочния стан РО, забезпечус, по-шрие, в1дсутн1сть "ефекту домшо", по-друго. малу загальну довжину высоту.

Пропонусться так© коордановане формування СР в ГС з древовидною тополог!ею. Така тополог 1 я морени зв'язку часто зустр1часться в 1срарх1чнкх регшнальних 1/або галузових системах. Вважасмо, що !н1ц!аторсм форнування СР с рентралыгоя (в:гдия за 1ерарх1сю вузол) - кор1нь В1ртуального дорова (УТ). Запит на форнування СР в!н в1дправляс пльки множин! безпос9родпьо л! дпорядковлких йому за 1срарх1ся вузл1з; т1, в свою чергу, - шшжилам шдпорядкованих бозпосередньо !м 1 т.д. Опт, еломентараим актом протоколу являсться протокол ( 1 < - > н ) М1ж одним стзрг/м вузле^ I н п1дпорядковлнкми аому вузлами 01льш низького р|вия.

Запропоновано мода!) 1 кования двостугановия алгоритм фор;1упзтш контрольно! точки (230СР). розроблон! вкризалы! 1

правила, що забазпачуюгсъ тормШацш i малиа час рсботи алгоритму:

1. 1шц1атор о проподус вс1м вузлам pi сформувате глобзлъну коытрольау точку ( ~chpr(ti)"). При цьому указуеться но;.юр останзього пов1доилоныя, отриманого о в!д pi. Вузли гн иожуть висловати 1нЩ1атору свою згоду або шзгоду в зал?яшост! в1д того, сп!ападее чи ni вомэр остаянього в!дпрзвл9вого ники поа!домлзння з покором, указании в 3ararri 1н1ц!атюру, а також салзаагаст! в1д в!дпов1д! шмчо л!даорадкованнх вузл!ь. Для цього вузли pi, юрод гш як дата свою в!даов!дь ( "уев" або "по" ), повияя1 запросит Шдаорздкован! ¡к вузли-вжсонавц!. I т!лъки ягацо останн1 в!доов1даэть 1м "yes", то до 1н!ц1атора о надходагь та сама в1даов1дь "yea". У протижшюыу вкладку до о надходшгь "по".

2. 1н1ц1атор о розсилае свое р1Еияня про формувашш контрольно! точки ("tafee-chp"), якщо воi вузли над! слали "yea", i в!даову е!д формувашш кмпрольяа! точки ("undo-chp"}, fisqo хоча б один вузол над!слав "по", ßap вузал - виконавець мав нэлульовиа кс^ор у валет! !е!Щагора, тобто обм1нювався nos i доилоншмк, то в1н Еаколус ваи!р Шщатора. firara вузол-шконавэць ига нульошЕ аошр у залит! iHiyiaropa, tcöto ва ойНешввся пов 1 як ими в иодаим з вузл!в, то в1а lraopys nasáp !н!ц!гторэ. Заувакзаю, цэ-з нокэнту надгодвэЕНЛ азпкту В1Д 1н1ц!аторз q до комзнту кадкодання р!шбнпя 1н!ц!аторз о процзск р m о6и!еяоться Ш8 i доылэкняыи.

Кошгаго разу, кола вузол в!даовл5, VT пов1дч&лие про цз вс1 вузли сисггеки. Тод1: яьхд в!деовигь 1в1ц!зтор о кз будь-якоиу кроц! ахгсртгму, то вс! вузла р-- будуть чекгтк ЙОГО Б1ДПОВЛЭНКЯ. Пкш.0 В1даОХИ!В вузол ri шрод тса, як BiWEBlcTK "уев" або "по", то iniiíióTop о будэ про цз ИОВ1ДОМЛЗНШ i приагэ- р!Шп!ШЯ "ur.do-chp". 10Д1 Ei'ЗОЛ pi Hiczí? сеого в!даозлэнкя шзхаоз д!знзткся про прийаягэ р1Еопня б!д Ш1ц!атира або Ieœx £>уак1в pj. Ягадр а вузол pi В!ДМЗВКВ П!СЛШ В1ДГЕ5В1Д1 "уев" sóо ".-ve", то п!сля свого В1дпаалэння в1в коже сашэст!Ьяо прианяги р1ыэняя про "undo-chp", 71 ЛЫС! ЯКЩО ЙОГО Б1ДП031ДЬ 6УДЭ "по". у

протидешному вкладку нообИдно д1знатася про прийняге р1Ш0НИЯ в1д !нших вузл!в.

В1дзначимо, якцо СР !н1ц!кжггь одночзсно два вузли мэре:«! то, щоб уникнути тупиково! ситуац! I, другиа запот повинен отримати в!дмову. Таким чином, зПдно з запропонованим алгоритмом, кожниа вузол РС будуе одну тост1гну конгрольну точ1су за умови об?л!ну пов1домлэнлями, м!н1м1зугочи при цьому витрати на пам'ять 1 забезгочуючи несупэречниа стан даних 1 налу сунарну довжину в1дкоту.

В четвертому розд!л1 поставлена задача створоння набору засоб!в ( фунгаЦональна оболонка ) до систэми СИМПАС для Шдтркмання опису та моделювання в динам1ц! б]льшост1 практично важливих процас1в 1 ситуац!я в системах управляя транзакц1ями I знаходаання значень кригерПв якост1 такого управл!ння ( Додаток I до дасорггац! Г).

В основу розробки були покладан1 так! принципи:

1. Моделованню п!длягаклъ т1льки процэси, як1 управляться протоколами ворхн!х р!вн1в. Характеристики ж протокол!в р1вн!в 2-4 ( 1 конф!гурацП тохн!чних засоб1в ) задаться як початков! параметри на основ! ексшртних оц!нок.

2. Оболонка повинна п!дгримувати вс! наяб1льи розповсюдаен1 метода управления паралел1змом транзакц!я л дозволяти знаходаги ! оц1нювати м1ру д1! р!зноман!тних фактор1в 1 параметр!в системи, а такой тупикових ситуэц1й на ефективн!сть робота системи.

3. Оболонка повинна п!дгримувати проектування в1дмовост!йхо1 системи 1 несугаречШсть даних систем на баз! алгоритм!в ф!ксэц!I транзакц!а ! алгоритм!в побудови контрольное точок для в!даовлэння систэми п!сля в!дмов.

Зазначег! функцИ ! !х в^аставост! реал!зуються такими модулями: мг дуль виЗору поточно! под1!, модуль гонерац!! транзакц1й, модуль визначення необх1дних ОМ-вузл1в, модуль визначення необх!дно! гранули. модуль обл!ку часу розповсюдхиння пов!домлень в)д ТМ до ОМ, модуль вор;<$1кзц! I транзакщя перед постановкою в чергу до гранул, модуль забезшчвння в1дмовост!якост1, модуль ф!ксац!1 транзакц1я.

В процэс! розробки оболонки були проведан! додатков1

доол1дюэнзя дая рэал1зац!1 алгоритм!в горев1рки глобального плану виконанню субтрапзакщй щодо йога свр1ал1зуекост1 (така пэрав1рка здШсюкггься методами, цо в!дносяться до класу "ошим 1 стачних"). Суть дрсл1даення полягае в тому, що готрапивши у доякиг ОМ, заявка на виконання субтрзнзакц1й не одрэзу татрашшв в чоргу до Езобх1дпо1 гранули, а поизрэдньо проходить в©риф1кац1ю зг!дао з алгоротмоя " зростаичого л1су".

Процэо шров1рк1{ викоркстовуе гобудову в кожному вузл! ТМ» дерева залэжностой, яке являе собою Шдграф о-графа. Право говорэти про те, цо Шдграфи у вс1х вузлах с деревами, дас нам врахуванкя одного з правил, зПдно якому, як т!льки дзяхз транззхц1я став причиною ¿творения цжлу на граф!-вона в1дгаэчусться.

Алгорэта Оудуе тракзитивн1 заяикання для дэрова в кожному вузл! ТМ>, в кксму в1д5уваеться раткф1кац!я ново! субтранзакцП ш вс1м г1лкам, як1 ваникавть в процэс1 росту дерева.

Заоеравння ново! г1лки ! дарова в щлому означая побудову вс!х трзнзигкшшх зашкань, щр гарагггус В1дсутн1сть цшш!в 1 можливЮТь ратиф!кацП ново! транзакц!I. •

Аягорига вважасться заваривши в дзох випадках:

- колк в одному !з вузл1в Т1>й знаадэниа хоч один 1$псл, 1 тод! виглад даров в 1ншег ТМ1 во в]д1грае значения;

- кола вс1 г!дки будуть эавэртен!, цикл но заагдзно, I елях ( проа1жн! стани ) до цього стану байдуикй.

Як ексшримэптальниа приклад 1штац1йного гдцзлпзаыня ТС була досл1даепа кодоль РСБД, розшд!лэна го п'ятк ОМ-вузлам. Кояний вузод вас ч!тко визкачапу частану дзнпх РСЕД з одаашши под!лоы на гранули (облает! блокування). Нокери Еэобх^дшк гранул задашься при гонерацП транзакц!I л ТМ. В екешрихэнт! викорксггозувалась РР-стратег!я срцео-аи роис-.о поперэдаьо! сб'кви блок!ровок. ; Приавпто, цо транзакц!я но зн!кае юдно! блох1ровкп до зак!Ечення свое! робота. Для знаходаення тупик!» використовувався мохая!зм обюшення розм!р1в черт до кожно! гранули. Для рэгулшання тривалост! виконаяня транзакц 15 використовувався шхан1зи тайм-аута. Таким чином, враховано вшив таких

факторов:

1) закон розпод!лу потоку транзакц!й;

2) закон розпод!лу часу обробки трзпзакцШ;

3) максимальна доажина черги до гранул;

4) к!льк1сть гранул в ОМ;

5) тривал1сть тайм-аута чекання готовност1 ОМи

6) системн1 параметра РСБД (зо1срема, затримки при шрэдач1).

Показники, за якими оц1непа ефоктквшсть робота ст.-ггеми:

1) продуктивн1сть систвми, тобто к1льк1сть транзакция, виконаних за час модэлювання;

2) процэнт втрат (невиконаних трэязакща), спричинеких тупиковими ситуащями або тайм-аутом.

Результата для кожного показника в1дображэн1 у вигляд1 граф1к1в, як функцН в!д числа гранул.

Основы1 висновки.

У дисертац1яв1й робот1 були отриман1 так! основн1 результата.

У теоретичному план1:

1) модиф!ковано ИТ-протокол фИссац! I транзакцП для н вузл1в в рамках модал! слунйи в1даовост!акост!, з1брапо! о едину 1ерарх1чпу систему;

2) запропоновано неблокуючиа ИТ'-протокол трьохфазно! ф1ксац11, стИВсий до дов1льшга множшших в1даов вузл1в;

3) модиф1 ковано механ1зм управл1ння зарезервовашда.и даними в рамках 1ерарх1чно1 модэл1 систоми в1дмовост1йкост1;

4) узагальнено 1 обгрунтовано алгоритм "моментального зн1мку" глобального стану мерой!, за Ломпортом, па основ1 шрефарбувашя вузл1в;

5) розроблен! протоколи формування контрольних точок в РС, в тому числ1 2 модиф1кованих алгоритмы, як! скорочуюггь час простою РС 1 к1льк!сть в!дкот!в транзакщй;

й) запропоновано алгоритм вери^кацП глобального плану виконання субтранзакфй щодо його сер1ал1зуемосгп при мотод1 блокування.

У практичному план i :

Розроблена програмна оболопка для модэлювання СУТ на баз1 систени СИМПАС, що п!дгриыуе анал1з динам!ки практично важливих процэс!в 1 ситуац1а в скотомах управл1ння транзакц!ями 1 забезшчуе знаходшння значень найб1льш важливих кршврПв якост! такого управл!ння.

Основа i полошоння дасертацП опусШковап! в таких роботах:

1. Никитин А.И.» Алкав A.A., Гостилова C.B. Глобальное непротиворечивое состояннз распределенных баз данных. -Киев, 1888. - 21с. - (Препр./ АН УССР. Ин-т кибернетики им. В.М.Глушкова; 88-48).

2. Никитин А.И., Гостилова C.B. Иерархия механизмов отказоустойчивости в распределенных системах// УСиМ. -1890.- N6. -0.84-93.

3. Никитин А.И., Гостилова C.B. Глобальное состоят» распродаланноп базы данных и глобальная контрольная точка// УСиМ. - 1991. -N8. -0.68-76.

4. Никитин А.И., Гостилова C.B. Контрольная точка в РЕД как мотод васстановлэния процэссов, происходящих в сетях// Тез. докл. 3-й Всвсоюз. конф. "Живучесть и реконфигурация икформационно-вычислкгельных и управляющих систои".-Севастополь, I99I.-C.I5.