Диссертация (1148255), страница 20
Текст из файла (страница 20)
— ISBN: 0521899435.42. Steen, M. v. Distributed Systems (3rd Edition) [Text] / Maarten van Steen,Andrew S. Tanenbaum. — [S. l.] : CreateSpace Independent Publishing Platform, 2017. — ISBN: 1543057381.43. Steinke, R. C. A unified theory of shared memory consistency [Text] /Robert C Steinke, Gary J Nutt // Journal of the ACM (JACM). — 2004.
—Vol. 51, no. 5. — P. 800–849.44. Stumm, M. Algorithms implementing distributed shared memory [Text] /M. Stumm, S. Zhou // Computer. — 1990. — May. — Vol. 23, no. 5. — P. 54–64.45. Stumm, M. Fault tolerant distributed shared memory algorithms [Text] /M. Stumm, Songnian Zhou // Proceedings of the Second IEEE Symposiumon Parallel and Distributed Processing 1990. — [S.
l. : s. n.], 1990. — Dec. —P. 719–724.46. Tanenbaum, A. S. Distributed operating systems [Text] / Andrew S Tanenbaum. — [S. l.] : Pearson, 1994. — ISBN: 0132199084.47. Treadmarks: Distributed shared memory on standard workstations and operating systems.
[Text] / Peter J Keleher, Alan L Cox, Sandhya Dwarkadas,Willy Zwaenepoel // USENIX Winter. — Vol. 1994. — [S. l. : s. n.], 1994. —P. 23–36.48. TreadMarks: shared memory computing on networks of workstations [Text] /C. Amza, A. L. Cox, S. Dwarkadas [et al.] // Computer. — 1996.
— Feb. —Vol. 29, no. 2. — P. 18–28.49. View-based consistency and false sharing effect in distributed shared memory[Text] / Zhiyi Huang, Chengzheng Sun, M Purvis, Stephen Cranefield // ACMSIGOPS Operating Systems Review. — 2001. — Vol. 35, no. 2. — P. 51–60.50. VODCA: View-oriented, distributed, cluster-based approach to parallel computing [Text] / Z.
Huang, W. Chen, M. Purvis, W. Zheng // Cluster Comput-122ing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposiumon. — Vol. 2. — [S. l. : s. n.], 2006. — May. — P. 15–15.51. Voronoi coverage of nonconvex environments with a group of networked robots[Text] / Andreas Breitenmoser, Mac Schwager, JeanClaude Metzger [et al.] //In processing of the IEEE International Conference on Robotics and Automation (ICRA). — Anchorage, Alaska, USA : [s. n.], 2010. — P. 4982–4989.52.
Wooldridge, M. An Introduction to MultiAgent Systems - Second Edition[Text] / M. Wooldridge. — [S. l.] : Wiley, 2009. — ISBN: 0470519460.53. Yu, X. Tardis: Time traveling coherence algorithm for distributed sharedmemory [Text] / X. Yu, S. Devadas // 2015 International Conference onParallel Architecture and Compilation (PACT). — [S. l. : s. n.], 2015. —Oct.
— P. 227–240.123Список иллюстративного материалаРисунок 1.1 Концепция доски объявлений . . . . . . . . . . . . . . . .17Рисунок 1.2 Концепция мультипроцессорной системы с общей памятью 18Рисунок 1.3 Система с общей памятью и шиной данных . . . . . . . .19Рисунок 1.4 Концепция мультикомпьютерной системы с распределённой памятью . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .20Рисунок 1.5 Модель строгой консистентности . . . . . . . . . . . . . .25Рисунок 1.6 Модель последовательной консистентности . . . . . . . .27Рисунок 1.7 Ситуация, недопустимая в модели последовательной консистентности . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .27Рисунок 1.8 Алгоритм с центральным сервером . . . . . . . . . . . .36Рисунок 1.9 Отказоустойчивый алгоритм с центральным сервером . .36Рисунок 1.10 Алгоритм миграции данных . . . . . . . . . . . . . . . .37Рисунок 1.11 Операция записи в алгоритме репликации по чтению . .39Рисунок 1.12 Операция записи в алгоритме полной репликации . . . .41Рисунок 2.1 Модель расширенной консистентности по выходу . . .
.62Рисунок 2.2 Схема возможных изменений ролей узла в МАКС DSM .64Рисунок 2.3 Алгоритм смены роли узлом в МАКС DSM . . . . . . . .64Рисунок 2.4 Операция записи в МАКС DSM . . . . . . . . . . . . . .65Рисунок 2.5 Типы и направления сообщений в МАКС DSM . . . . .
.68Рисунок 3.1 Пример программы с использованием МАКС DSM . . .73Рисунок 3.2 МАКС DSM в составе функционирующего узла МАС . .87Рисунок 3.3 Основные классы МАКС DSM в нотации UML . . . . . .89Рисунок 3.4 МАКС DSM программа «счётчик» . . . . . . . . . . . . .91Рисунок 3.5 МАКС DSM программа «цветной счётчик» . . . .
. . . .94Рисунок 3.6 «Сырая» скорость канала . . . . . . . . . . . . . . . . . .97Рисунок 3.7 Cкорость с контролем целостности данных . . . . . . . .98124Рисунок 3.8 Cкорость с гарантированной доставкой . . . . . . . . . . 100Рисунок 3.9 Cкорость DSM уровня . .
. . . . . . . . . . . . . . . . . . 102Рисунок 3.10 Cкорость DSM уровня (масштаб 10 секунд) . . . . . . . . 103Рисунок 3.11 Cкорость DSM уровня (2–5 узлов) . . . . . . . . . . . . . 104Рисунок 3.12 Cкорость уровня гарантированной доставки (2–5 узлов)105Рисунок 3.13 Cкорость DSM уровня (2–16 узлов) . . . . . .
. . . . . . 107125Список таблицТаблица 1.1 Известные DSM решения . . . . . . . . . . . . . . . . . .48Таблица 2.1 Роли узлов в МАКС DSM . . . . . . . . . . . . . . . . . .63Таблица 3.1 Операции прикладного интерфейса МАКС DSM . . . . .75Таблица 3.2 Внутренние сообщения МАКС DSM . . . . . . . . . . . .79126Приложение А. Результаты измеренийВ данном приложении в виде таблицы представлены исходные (числовые)данные произведённых измерений. Информация может быть использована дляуточнения графиков представленных в главе 4, а также визуализации данныхв альтернативном виде.Расшифровка названий колонок приведена ниже.
При этом суффикс «-b»означает «байт в секунду» (от англ. bytes), «-p» – «пакетов в секунду» (от англ.packets).– b – Количество байт в одном пакете данных.– r – «Сырая» скорость канала (от англ. raw).– c – Скорость для протокола с контролем целостности данных (от англ.check).– g – Скорость для протокола с гарантированной доставкой (от англ.guarantee).– d – Скорость DSM уровня для режима эксклюзивного доступа (от англ.DSM).Так как в использующихся протоколах размер пакета представлен однимбайтом, максимально возможный размер пакета – 255 байт.
Соответственно,количество строк в таблице ограничено именно этим числом. Каждый новыйуровень стека протоколов (за исключением уровня с контролем целостности, см.примечание в разделе замеров данного уровня в главе 4), добавляет несколькобайт служебной информации к каждому пакету исходных, «пользовательских»данных. Гарантированная доставка – дополнительно 9 байт, DSM – ещё 17 байт.В связи с этим, замеры для каждого более высокого уровня стека протоколовпрекращаются на размере пакета, меньшего на соответствующее количествобайт.127br-bc-bc-pg-bg-pd-bd-pd-b10d-p1011,7961,5251,525333333292929429423,5262,9821,491672336582958329235,1994,4011,4671,008336872986128746,8065,7601,4401,348337112281,13928558,3607,0751,4151,685337140281,42428569,8668,3401,3901,854309168281,709285711,3199,5691,3671,995285196281,993285812,72110,7521,3442,312289224282,278285914,08111,9071,3232,601289252282,5632851015,40613,0001,3003,010301280282,8482851116,66314,0361,2763,410310308283,1322851217,91214,9401,2453,720310336283,3902821319,11215,9121,2244,056312364283,6132781420,27316,8701,2054,340310392283,8912781521,38917,7901,1864,650310420284,1692781622,52018,6241,1644,944309448284,4472781723,57319,4481,1444,573269476284,7632801824,60320,1421,1194,842269504285,0432801925,62320,9761,1045,111269532285,2802782026,59321,6401,0825,360268540275,4672732127,53422,3861,0665,649269567275,7412732228,45222,9241,0425,830265594276,0142732329,35523,6901,0306,187269621276,2872732430,25124,2401,0106,552273648276,5612732531,14924,7009886,625265675276,8342732631,89418,9547296,916266702277,1072732732,75019,4137197,263269729277,3812732833,54019,7687067,532269756277,6542732934,27820,4747067,801269783277,9272733035,04920,9106977,590253810278,2012733135,77421,2046847,781251837278,4742733236,56721,7286797,584237864278,6022693323,09021,9786667,821237891278,7952673423,57322,7466698,058237918279,0622673524,15023,1006608,295237945279,3282673624,61923,4366518,388233972279,5952673725,16123,8286448,769237999279,8612673825,62323,9786318,8542331,0262710,128267128br-bc-bc-pg-bg-pd-bd-pd-b10d-p103926,13324,4536279,2822381,0532710,3952674026,59324,5606149,2402311,0402610,3882604127,07025,1746149,6352351,0662610,7412624227,61025,2846029,4502251,1342711,1942674328,01925,8006009,6752251,1612711,4612674428,53425,7845869,9002251,1442611,6272644528,95326,37058610,2602281,1702611,6862604629,44226,26657110,9942391,1962611,9462604729,82926,79057011,1392371,2222612,2062604830,25126,73655711,3762371,2482612,2472554930,75327,39155911,0252251,2742612,5022555031,14927,60055211,4002281,3002612,7572555131,52927,84654612,0872371,3262613,0122555231,99628,23654312,4282391,3522613,2672555332,34727,45451812,5612371,3782613,5222555432,75028,24252312,7982371,4042613,7772555533,18027,72050413,1452391,4302614,0322555633,55828,56051013,2722371,4562614,2882555733,92528,78550513,3952351,4252514,4132535834,39625,28843613,7462371,3342313,4772325934,73825,66543513,7472331,4162414,3812446035,06625,98043313,5002251,5002514,7612466135,50726,04742713,7252251,5252515,1462486235,90226,41242613,9502251,5502515,2532466336,19226,46042014,1752251,5122415,3562446436,56726,81641914,4002251,5362415,3082396528,25026,78041212,4151911,5602415,5472396628,55327,06041012,7381931,5842415,7872396728,84927,06840412,6631891,6082416,0262396829,13927,40440313,1241931,6322416,2652396929,39327,18639413,3171931,6562416,5042397029,75727,72039613,4401921,6802416,7432397130,02727,61938913,7031931,7042417,3062447230,28928,08039013,8961931,7282417,5502447330,63827,95938314,0891931,7522417,7932447430,92527,60237314,2821931,7762418,0372447531,16828,12537514,4751931,8002418,2812447631,40327,81636614,6681931,8242418,525244129br-bc-bc-pg-bg-pd-bd-pd-b10d-p107731,73128,25936714,0911831,9252519,1192487831,99628,08036014,4301851,9502519,3682487932,31428,51936114,4571831,9752519,6162488032,57028,32035414,6401832,0002519,8642488132,76928,75535514,9041842,0252520,1122488233,07028,53634815,0061832,0502520,3612488333,30727,97133714,8571792,0752520,6092488433,65328,64434115,1201802,1002520,8572488533,82328,30533315,3851812,1252521,4932538634,16028,98233716,2541892,1502521,1582468734,43428,18832416,7911932,0882421,2062448834,64427,72031516,9841932,1122421,2492418934,84928,48032017,1771932,1362421,2882399035,17226,82029817,3701932,1602421,5272399135,42126,66329317,5631932,1842421,7662399235,60928,06030517,7561932,2082422,0052399335,92027,99330117,8561922,2322422,2452399436,09726,79028518,1421932,2562422,4842399536,40126,69528117,5751852,2802422,7232399636,56728,51229716,9921772,3042422,9622399730,55027,16028016,0051652,3282423,6432449830,75326,95027515,2881562,3522423,8872449930,95328,80929116,0381622,3762424,13124410031,14928,70028716,5001652,4002424,37524410131,36327,57327316,4631632,4242424,61824410231,57527,33626816,7281642,4482424,86224410331,78729,35528516,6861622,4722425,10624410431,99629,32828217,1601652,3922324,40223510532,20528,35027015,8551512,5202424,87623710632,41228,30226716,5361562,5442425,35423910732,61830,38828416,7991572,4612325,10623510832,82330,34828117,7121642,4842324,84823010933,02729,32126917,6581622,5072325,07923011033,22929,26026618,0401642,5302325,30923011133,43031,41328317,9821622,5532325,03322611233,63031,36028017,1361532,5762325,25822611333,72830,28426817,7411572,5992325,48422611433,92530,32426617,8981572,6222325,710226130br-bc-bc-pg-bg-pd-bd-pd-b10d-p1011534,12132,31528117,4801522,6452325,93522611634,31632,36427918,2121572,6682326,16122611734,51031,23926718,3691572,6912326,38622611834,70231,27026517,7001502,7142326,61222611934,89431,29726317,9691512,7372326,83722612035,08433,36027818,8401572,7602327,06322612135,27432,30726718,9971572,7832327,28822612235,35929,89024519,6421612,6842226,95822112335,54631,48825620,2951652,7062227,17922112435,73130,75224820,0881622,7282227,40022112535,91630,75024620,5001642,7502227,33621912636,10030,87024520,4121622,7722227,84222112736,28230,86124320,9551652,7942228,06322112836,46432,51225418,0481412,8162228,28422112931,77031,73424618,0601402,8382228,50522113031,93831,85024517,8101372,8602228,72622113132,10531,83324317,9471373,0132329,54322613232,27131,94424218,6121413,0362329,76922613332,43631,92024018,7531412,9262229,69122313432,60033,63425118,8941412,9482229,60922113532,76432,94024417,9551332,9702229,83022113632,92732,91224219,1761412,9922230,05122113733,08932,74323919,3171413,0142230,27222113833,25032,84423819,4581413,0362230,49322113933,33032,80423619,4601403,0582230,71422114033,49034,58024719,7401413,0802230,93522114133,64934,54524519,8811413,1022231,15622114233,80734,64824419,7381393,1242231,37722114333,96433,89123720,0201403,1462231,59822114434,12033,84023520,3041413,1682231,49121914534,27634,07523520,4451413,1902231,37921614634,43134,16423420,0021373,2122231,59621614734,58534,25123320,1391373,2342231,81221614834,73935,07623720,2761373,2562232,02921614934,89235,16423620,4131373,2782232,24521615035,04435,10023420,5501373,3002232,46221615135,19535,18323320,6871373,3222232,67821615235,34635,26423220,8241373,3442232,894216131br-bc-bc-pg-bg-pd-bd-pd-b10d-p1015335,49636,87324118,0541183,2132132,41421215435,64534,18822220,0201303,2342132,62621215535,79433,48021621,2351373,2552132,83721215635,94233,54021521,0601353,2762133,04921215736,08933,59821421,1951353,2972133,26121215836,23633,65421321,9621393,3182133,47321215936,38233,86721322,2601403,3392133,68521216036,52733,92021219,6801233,3602133,89721216132,58933,97121119,3201203,3812134,10821216232,72535,31621819,4401203,4022134,32021216332,86035,37121719,5601203,4232134,53221216432,99535,58821720,5001253,4442134,74421216531,15234,81521119,9651213,4652134,95621216633,26434,86021020,0861213,4862135,16821216733,46435,07021020,2071213,5072134,99921016833,53035,11220921,0001253,5282134,44320516933,66335,15220821,1251253,5492134,64820517033,79536,55021520,9101233,5702134,85320517133,92636,59421421,3751253,5912135,05820517234,05735,94820919,7801153,6122135,26320517334,18736,15720921,4521243,6332135,46820517434,31736,01820721,7501253,4802034,88120017534,44636,05020621,8751253,5002035,08120017634,57536,08020522,0001253,5202035,28220017734,51536,10820421,7711233,7172136,28920517834,83136,31220420,8261173,7382136,49420517934,95837,76921122,3751253,7592136,69920518035,08537,80021022,5001253,6002036,49420318135,21237,82920922,2631233,6202036,28420018235,26937,12820421,6581193,6402036,48420018335,39437,14920322,1431213,6602036,68520018435,51937,35220317,664963,6802036,88520018535,64337,37020220,1651093,7002037,08620018635,76735,15418921,2041143,7202036,86319818735,89035,34318922,6271213,7402037,06119818836,01335,34418821,0561123,7602037,25919818936,13535,53218822,4911193,7802037,45719819036,25735,53018716,910893,8002037,655198132br-bc-bc-pg-bg-pd-bd-pd-b10d-p1019136,37935,52618621,9651153,6291936,98319419236,50035,71218621,1201103,6481937,17719419333,21635,70518521,4231113,6671937,37119419433,33135,69618421,5341113,6861937,56419419533,44535,88018420,6701063,7051937,75819419633,55935,86818319,208983,7241937,95119419733,67336,64218620,8821063,7431938,14519419833,72936,63018520,9881063,7621938,33919419933,89936,81518522,4871133,7811938,53219420033,95436,80018421,2001063,8001938,27019120134,06636,78318320,1001003,8191938,46219120234,17736,96618320,4021013,8381938,65319120334,28836,94618221,7211073,8571938,84419120434,39937,12818218,156893,8761939,03619120534,51037,10518122,7551113,8951939,22719120634,62037,08018022,8661113,9141939,41919120734,72938,50218623,3911133,9331939,61019120834,83938,68818623,2961123,9521940,27519420934,94838,45618422,9901103,9711940,46919421035,05638,01018123,5201123,9901940,66219421135,16537,98018023,8431134,0091940,85619421235,27238,16018023,9561134,0281941,05019421335,38038,12717923,6431114,0471941,24319421435,48738,30617923,5401104,0661940,94919121535,59438,27017824,0801124,0851940,65118921635,70038,23217723,7601104,1041940,84018921735,80638,40917723,6531094,1231941,02918921835,91236,40616722,6721044,1421941,21818921936,01836,35416623,8711094,1611941,40718922036,12336,52016621,780994,1801941,59618922136,22736,46516524,0891094,1991941,78518922236,33236,63016523,0881044,2181941,97418922336,43636,57216422,3001004,2371942,16418922436,53936,51216322,176994,2561942,86319122533,63037,80016822,5001004,2751943,05419122633,72937,96816822,8261014,2941943,24619122733,82838,13616822,9271014,3131942,92018922833,92738,07616722,572994,3321943,109189133br-bc-bc-pg-bg-pd-bd-pd-b10d-p1022934,02537,55616423,1291014,3511943,29818923034,12337,72016423,23010123134,22037,65316322,1769623234,31837,81616322,2729623334,41537,74616221,2039123434,51137,90816223,63410123534,60837,83516122,5609623634,70437,99616122,8929723734,80038,15716122,7529623834,89538,08016023,0869723934,99138,24016024,13910124035,08639,36016424,24010124135,12939,52416423,3779724235,22439,68816423,4749724335,36939,60916323,5719724435,41239,04016024,64410124535,50539,20016024,74510124635,59939,11415924,84610124735,69239,27315924835,78439,18415824935,87739,34215825035,96937,25014925136,06137,39914925236,15337,29614825336,24437,44414825436,33637,59214825536,42837,740148.