Konkurentne strukture podataka

S Vikipedije, slobodne enciklopedije

U računarstvu,konkurentna struktura podataka je poseban način skladištenja i organizovanja podataka radi pristupa od strane više računarskih niti (ili procesa) na računaru.

Istorijski posmatrano,takve strukture podataka su korišćene na jedno-procesorskim mašinama sa operativnim sistemima koji su podržavali više računarskih niti (ili procesa). Izraz konkurentnost je oslikavao multipleksiranje/preplitanje operacija niti nad podacima od strane operativnog sistema,iako procesor nije izdao dve operacije koje su pristupale podacima istovremeno.

Danas,pošto je više-procesorska arhitektura računara koja obezbeđuje paralelnost postala dominantna računarska platforma (kroz širenje više-jezgarnih procesora),izraz više označava strukture podataka kojima se može pristupati od strane više niti koje zapravo mogu pristupati podacima istovremeno zato što se izvršavaju na različitim procesorima koji komuniciraju međusobno. Konkurentna struktura podataka (ponekad takođe nazivana i deljena struktura podataka) obično se smatra da boravi u apstraktnom okruženju za skladištenje nazvanim deljena memorija,iako ova memorija može biti fizički realizovana kao bilo „gusto povezana“ ili distribuirana kolekcija modula za skladištenje.

Osnovni principi[uredi | uredi izvor]

Konkurentne strukture podataka,namenjene za upotrebu u paralelnim ili distribuiranim računarskim okruženjima,razlikuju se od „sekvencijalnih“ struktura podataka,namenjenih za upotrebu u jedno-procesorskim mašinama,na nekoliko načina. Pre svega,u sekvencijalnom okruženju preciziraju se osobine strukture podataka i provere da li su one pravilno sprovedene,obezbeđujući svojstva zaštite. U konkurentnom okruženju,specifikacija takođe mora da opiše svojstva životnosti koje realizacija mora da obezbedi. Svojstva bezbednosti obično navode da se nešto loše nikada neće dogoditi,dok svojstva životnosti navode da će se nešto dobro stalno dešavati. Ova svojstva mogu biti izražena,na primer,korišćenjem Linearno Temporalne Logike.

Tip životnosnih zahteva teži da definiše strukturu podataka. Pozivi metoda mogu biti blokirajući i ne-blokirajući. Strukture podataka nisu ograničene na neki tip i mogu dozvoliti kombinacije gde neki pozivi metoda jesu blokirajući i ne-blokirajući (primeri mogu biti pronađeni u biblioteci softvera Java konkurentnosti).

Bezbednosna svojstva konkurentnih struktura podataka moraju da zadrže njihovo ponašanje obzirom na veliki broj mogućih preplitanja metoda pozvanih od strane različitih niti. Veoma je intiutivno precizirati kako se apstraktne strukture podataka ponašaju pri sekvencijalnim podešavanjima u kojima nema preplitanja. Shodno tome,mnogi ustaljeni pristupi za tvrđenje bezbednosnih svojstava konkurentnih struktura podataka (kao što su serijalizacija,linearizacija,sekvencijalna doslednost i doslednost mirovanja[1]) preciziraju svojstva struktura sekvencijalno,i preslikavaju konkurentna izvršavanja u kolekciju sekvencijalnih.

Da bi se garantovala bezbednosna i životnosna svojstva,konkurentne strukture podataka često (mada ne uvek) moraju da dozvole nitima da postignu konsenzus kao rezultatima njihovih istovremenih zahteva za pristupom i menjanjem podataka. Kako bi podržale takav sporazum,konkurentne strukture podataka se implementiraju koristeći specijalne primitivne operacije sinhronizovanja (videti sinhronizovanje primitivama) dostupne na modernim više-procesorskim mašinama koje dozvoljavaju višestrukim nitima da postignu konsenzus. Ovaj konsenzus može biti postignut u blokirajućem maniru korišćenjem katanaca,ili bez katanaca,u tom slučaju je ne-blokirajući. Postoji široko teorijsko telo o dizajnu konkurentnih struktura podataka (videti reference).

Dizajn i implementacija[uredi | uredi izvor]

Konkurentne strukture podataka su daleko teže za dizajniranje i proveravanje njihove valjanosti za razliku od njihovih sekvencijalnih kolega.

Glavni izvor dodatnih poteškoća je konkurentnost,pogoršano činjenicom da se niti moraju posmatrati kao kompletno asihrone:podložne su prisvajanjima od strane operativnog sistema,greškama u stranici,prekidima,i tako dalje.

Na današnjim mašinama,raspored procesora i memorije,raspored podataka u memoriji,opterećenje komunikacija raznih elemenata više-procesorske arhitekture utiču na efikasnost. Osim toga,postoji tenzija između korektnosti i performansi:algoritamska unapređenja performansi često otežavaju mogućnost dizajniranja i proveravanja ispravne implementacije strukture podataka.

Ključna mera za performanse je skalabilnost,zarobljena ubrzanjem implementacije. Ubrzanje je mera o tome koliko efikasno program iskorišćava mašinu na kojoj se izvršava. Na mašini sa P procesora,ubrzanje je odnos vremena izvršavanja strukture na jednom procesoru i vremena izvršavanja na T procesora. Idealno,želeli bi smo linearno ubrzanje:želeli bi smo da dostignemo ubrzanje od P kada koristimo P procesora. Strukture podataka čije ubrzanje raste sa P se zovu skalabilnim. Granica do koje se mogu skalirati performanse konkurentnih struktura podataka je opisana formulom poznatom kao Amdalov zakon i njene prefinjenije verzija poznate kao Gustafsonov zakon.

Ključni problem u performansama konkurentnih struktura podataka je nivo memorijskog zagušenja:višak u saobraćaju ka i od memorije,kao rezultat toga što više niti pokušava konkurentno da pristupi istoj lokaciji u memoriji. Ovaj problem je najviše izražen kod blokirajućih implementacija u kojima katanci kontolišu pristup memoriji. U cilju sticanja katanca,nit mora više puta pokušati da modifikujete tu lokaciju u memoriji. Na više-procesoru sa koherentnošću keša (takav u kome procesori imaju lokalne keševe koji su ažurirani od strane hardvera kako bi bili dosledni sa poslednje sačuvanim vrednostima) ovo se ogleda u dugim vremenima čekanja za svaki pokušaj da se izmeni lokacija,i pogoršano je dodatnim memorijskim saobraćajem povezanim sa neuspešnim pokušajima da se stekne katanac.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ Mark Moir and Nir Shavit (2007). „Concurrent Data Structures”. Ur.: Dinesh Metha and Sartaj Sahni. 'Handbook of Data Structures and Applications' (1st izd.). Chapman and Hall/CRC Press. str. 47—14—47—30.  Spoljašnja veza u |chapter= (pomoć)

Dodatna literatura[uredi | uredi izvor]

  • 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"

Spoljašnje veze[uredi | uredi izvor]

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