c # učinkovita varnostna vrsta niti ConcurrentQueue

C Efficient Thread Safety Queue Concurrentqueue

Enqueue, Dequeue, IsEmpty, Pridobite število elementov v čakalni vrsti (Count).

Najprej notranja struktura ConcurrentQueue:

1. Načelo izvajanja

Kot vsi vemo, obstajata dve izvedbi običajnih čakalnih vrst, ki niso varne za nit:

1. Krožna vrsta, izvedena z uporabo nizov.

2. Čakalne vrste, izvedene z uporabo povezanih seznamov.

Najprej si oglejte prednosti in slabosti obeh načinov:

Izvajanje skupne čakalne vrste v .Net Farmework uporablja prvo metodo. Pomanjkljivost je, da se bo razširitev izvedla, ko bo prostor čakalne vrste nezadosten. Glavna izvedba razširitve je odpreti novo matriko z izvirno dolžino 2-krat in nato kopirati podatke v prvotni matriki. V novem polju ne bo manjše porabe pomnilnika pri razširitvi in ​​vpliva na zmogljivost v sočasnem okolju ni mogoče podcenjevati. Ko pokličete konstruktor Queue, lahko določite velikost privzetega prostora. Vendar je količina podatkov v običajnih okoliščinah nepredvidljiva. Če izberete veliko, bo škoda prostora. Če izberete majhno, bodo za kopiranje pomnilnika režijski stroški, po razširitvi pa morate čakalno vrsto razširiti. Poklicana je metoda TrimToSize () za povrnitev neizkoriščenega pomnilniškega prostora.

Druga izvedba povezanega seznama odpravlja problem zapravljenega prostora, vendar povečuje pritisk GC. Ko je vrsta vnesena, se dodeli novo vozlišče. Ko je vrsta izpraznjena, je vozlišče zavrženo. Za veliko število postopkov odstranjevanja iz vrst ta izvedba ni zelo učinkovita.

ConcurrentQueue združuje zgornji dve izvedbi koncept segmentiranega pomnilnika (kot je prikazano na zgornji sliki), ko podpira več niti in izdaja ekipe v ekipo. ConcurrentQueue dodeli pomnilnik v enotah segmentov, en segment. Notranji vsebuje matriko s privzeto dolžino 32 in kazalcem za izvedbo naslednjega segmenta. Kazalec glave in repa kaže na začetni in končni del. Ta struktura je nekoliko podobna upravljanju segmenta operacijskega sistema in pomnilnika strani. Strategija upravljanja). Ta način dodeljevanja pomnilnika ne samo zmanjša pritisk GC, ampak tudi klicatelj ne uporablja metode TrimToSize () za prikaz pomnilnika. (Ko je določen segment pomnilnika prazen, bo GC povrnil segment pomnilnika).

2. Segmentirajte notranjo strukturo

Dejansko je delovanje ConcurrentQueue pravzaprav delovanje segmenta.

Segment lahko povzame naslednjo strukturo podatkov:

Glavne metode znotraj segmenta:

Notranjost segmenta je enakovredna običajni čakalni vrsti, ki jo izvaja matrika, le da se atomska operacija uporablja za preprečevanje večkontektnega problema s konkurenco za operacije čakanja in odvajanja, tehnika, kot je naključna koncesija, pa se livelock, izvedbeni mehanizem in ConcurrentStack pa se ne razlikujeta veliko. Podrobnosti izvedbe številnih poskusov so zelo jasne v komentarjih vira. Tu ni nobene razlage več.

Drugič, delovanje ekipe

Kot je prikazano na zgornji sliki, se operacija čakalne vrste izvaja v končnem segmentu. Ko podatki ne uspejo v segmentu, bo najprej izvedel operacijo vračanja in nato poskusil znova, dokler ne uspe. Razlog za neuspeh tukaj (tail.Append (item) vrne false Samo eden je ta, da kadar prostor v segmentu ni dovolj, se dodeli nov segment in elementi, ki vstopijo v segment, v tem času ne bodo uspeli.

Tretjič, timsko delovanje

Kot je prikazano na zgornji sliki, ko ekipa odpove, vrne false, namesto da bi se previjala kot ekipa. Ker je razlog za neuspeh ekipe ta, da ko so vsi elementi v čakalni vrsti prazni, je ekipa zasnovana tako, da vrne bool. Funkcija vrednosti.

Četrtič, ugotovite, ali je prazen (IsEmpty)

Splošna presoja je zapletenost O (1). Obstajajo tri glavne situacije:

1. Glavno vozlišče (segment) ni nič in vrne false

2. Glavno vozlišče je prazno, naslednje vozlišče pa je prazno, da vrne true

3. Glavno vozlišče je prazno, naslednje vozlišče pa ni prazno in vrne false. To pomeni, da se vrsta širi, zato počakajte, da razširitev znova zaključi sodbo.

Pet, dobite število elementov v čakalni vrsti (Count)

Poiščite nizek položaj vozlišča glave in visok položaj vozlišča repa. Ker je indeks trenutnega segmenta v čakalni vrsti zapisan v vsakem segmentu, je enostavno najti število elementov v celotni čakalni vrsti.

Tako kot pri ConcurrentStack tudi uradna Microsoftova dokumentacija in komentarji kažejo, da za presojo, ali je vrsta prazna ali ne, uporablja atribut IsEmpty namesto štetja Count == 0. Razlog je v tem, da GetHeadTailPositions išče položaj vozlišč glave in repa v postopek vključevanja in odprave velike količine podatkov. Zamudne operacije za neprekinjeno zanko za določanje položaja vozlišč glave in repa, zato določite, ali je vrsta prazna, ali uporabite atribut IsEmpty.