Конкурентне структуре података

С Википедије, слободне енциклопедије

У рачунарству,конкурентна структура података је посебан начин складиштења и организовања података ради приступа од стране више рачунарских нити (или процеса) на рачунару.

Историјски посматрано,такве структуре података су коришћене на једно-процесорским машинама са оперативним системима који су подржавали више рачунарских нити (или процеса). Израз конкурентност је осликавао мултиплексирање/преплитање операција нити над подацима од стране оперативног система,иако процесор није издао две операције које су приступале подацима истовремено.

Данас,пошто је више-процесорска архитектура рачунара која обезбеђује паралелност постала доминантна рачунарска платформа (кроз ширење више-језгарних процесора),израз више означава структуре података којима се може приступати од стране више нити које заправо могу приступати подацима истовремено зато што се извршавају на различитим процесорима који комуницирају међусобно. Конкурентна структура података (понекад такође називана и дељена структура података) обично се сматра да борави у апстрактном окружењу за складиштење названим дељена меморија,иако ова меморија може бити физички реализована као било „густо повезана“ или дистрибуирана колекција модула за складиштење.

Основни принципи[уреди | уреди извор]

Конкурентне структуре података,намењене за употребу у паралелним или дистрибуираним рачунарским окружењима,разликују се од „секвенцијалних“ структура података,намењених за употребу у једно-процесорским машинама,на неколико начина. Пре свега,у секвенцијалном окружењу прецизирају се особине структуре података и провере да ли су оне правилно спроведене,обезбеђујући својства заштите. У конкурентном окружењу,спецификација такође мора да опише својства животности које реализација мора да обезбеди. Својства безбедности обично наводе да се нешто лоше никада неће догодити,док својства животности наводе да ће се нешто добро стално дешавати. Ова својства могу бити изражена,на пример,коришћењем Линеарно Темпоралне Логике.

Тип животносних захтева тежи да дефинише структуру података. Позиви метода могу бити блокирајући и не-блокирајући. Структуре података нису ограничене на неки тип и могу дозволити комбинације где неки позиви метода јесу блокирајући и не-блокирајући (примери могу бити пронађени у библиотеци софтвера Јава конкурентности).

Безбедносна својства конкурентних структура података морају да задрже њихово понашање обзиром на велики број могућих преплитања метода позваних од стране различитих нити. Веома је интиутивно прецизирати како се апстрактне структуре података понашају при секвенцијалним подешавањима у којима нема преплитања. Сходно томе,многи устаљени приступи за тврђење безбедносних својстава конкурентних структура података (као што су серијализација,линеаризација,секвенцијална доследност и доследност мировања[1]) прецизирају својства структура секвенцијално,и пресликавају конкурентна извршавања у колекцију секвенцијалних.

Да би се гарантовала безбедносна и животносна својства,конкурентне структуре података често (мада не увек) морају да дозволе нитима да постигну консензус као резултатима њихових истовремених захтева за приступом и мењањем података. Како би подржале такав споразум,конкурентне структуре података се имплементирају користећи специјалне примитивне операције синхронизовања (видети синхронизовање примитивама) доступне на модерним више-процесорским машинама које дозвољавају вишеструким нитима да постигну консензус. Овај консензус може бити постигнут у блокирајућем маниру коришћењем катанаца,или без катанаца,у том случају је не-блокирајући. Постоји широко теоријско тело о дизајну конкурентних структура података (видети референце).

Дизајн и имплементација[уреди | уреди извор]

Конкурентне структуре података су далеко теже за дизајнирање и проверавање њихове ваљаности за разлику од њихових секвенцијалних колега.

Главни извор додатних потешкоћа је конкурентност,погоршано чињеницом да се нити морају посматрати као комплетно асихроне:подложне су присвајањима од стране оперативног система,грешкама у страници,прекидима,и тако даље.

На данашњим машинама,распоред процесора и меморије,распоред података у меморији,оптерећење комуникација разних елемената више-процесорске архитектуре утичу на ефикасност. Осим тога,постоји тензија између коректности и перформанси:алгоритамска унапређења перформанси често отежавају могућност дизајнирања и проверавања исправне имплементације структуре података.

Кључна мера за перформансе је скалабилност,заробљена убрзањем имплементације. Убрзање је мера о томе колико ефикасно програм искоришћава машину на којој се извршава. На машини са П процесора,убрзање је однос времена извршавања структуре на једном процесору и времена извршавања на Т процесора. Идеално,желели би смо линеарно убрзање:желели би смо да достигнемо убрзање од П када користимо П процесора. Структуре података чије убрзање расте са П се зову скалабилним. Граница до које се могу скалирати перформансе конкурентних структура података је описана формулом познатом као Амдалов закон и њене префињеније верзија познате као Густафсонов закон.

Кључни проблем у перформансама конкурентних структура података је ниво меморијског загушења:вишак у саобраћају ка и од меморије,као резултат тога што више нити покушава конкурентно да приступи истој локацији у меморији. Овај проблем је највише изражен код блокирајућих имплементација у којима катанци контолишу приступ меморији. У циљу стицања катанца,нит мора више пута покушати да модификујете ту локацију у меморији. На више-процесору са кохерентношћу кеша (такав у коме процесори имају локалне кешеве који су ажурирани од стране хардвера како би били доследни са последње сачуваним вредностима) ово се огледа у дугим временима чекања за сваки покушај да се измени локација,и погоршано је додатним меморијским саобраћајем повезаним са неуспешним покушајима да се стекне катанац.

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ Mark Moir and Nir Shavit (2007). „Concurrent Data Structures”. Ур.: Dinesh Metha and Sartaj Sahni. 'Handbook of Data Structures and Applications' (1st изд.). Chapman and Hall/CRC Press. стр. 47—14—47—30.  Спољашња веза у |chapter= (помоћ)

Додатна литература[уреди | уреди извор]

  • Nancy Lynch "Distributed Computing"
  • Hagit Attiya and Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"
  • Doug Lea, "Concurrent Programming in Java: Design Principles and Patterns"
  • Maurice Herlihy and Nir Shavit, "The Art of Multiprocessor Programming"
  • Mattson, Sanders, and Massingil "Patterns for Parallel Programming"

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Конкурентне_структуре_података&oldid=26903155”