Vi introducerar begreppet k-FIFO kö som kan dequeue element ur FIFO ordning upp till en konstant k ≥ 0. Att hämta det äldsta elementet från kön kan kräva upp till k + 1 dequeue-operationer (begränsad rättvisa), som kan returnera element som inte är yngre än k + 1 äldsta element i kön (begränsad ålder) eller ingenting även om det finns element i kön. En k-FIFO kö är svältfri för ändlig k där k + 1 är vad vi kallar den värsta semantiska avvikelsen (WCSD) av kön från en vanlig FIFO kö. WCSD begränsar den faktiska semantiska avvikelsen (ASD) för en k-FIFO-kö från en vanlig FIFO-kö när den tillämpas på en given arbetsbelastning. Intuitivt, ASD håller reda på antalet dequeue operationer som krävs för att returnera äldsta element och åldern av dequeued element. Vi visar att ett antal befintliga samtidiga algoritmer implementerar k-FIFO köer vars WCSD bestäms av konfigurerbara konstanter oberoende av all arbetsbelastning. Vi introducerar sedan så kallade Scal köer, som implementerar k-FIFO köer med generellt större, arbetsbelastningsberoende samt obundna WCSD. Eftersom ASD inte kan erhållas utan oöverkomliga overheads har vi utvecklat ett verktyg som beräknar lägre gränser på ASD från tidsstämplade körningar. Våra mikro- och makrobenchmarks på en toppmodern 40-kärnig multiprocessor maskin visar att Scal köer, som en omedelbar följd av deras svagare WCSD, överträffar och skala befintliga implementationer på bekostnad av måttligt ökade lägre gränser på ASD.
REF föreslår en ungefärlig samtidig FIFO-kö med den avslappnade begränsningen i ordning på elementen och härleda probabilistisk bunden på mängden avvikelse av denna ungefärliga kö från en perfekt FIFO- kö.
Performance , Scalability , and Semantics of Concurrent FIFO Queues ?
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}