Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • harvard-cite-them-right
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency Framework and Trade-offs
Högskolan i Borås, Institutionen Handels- och IT-högskolan. (CSL@BS)
2014 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport’s systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We describe a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.

Ort, förlag, år, upplaga, sidor
Lunds Tekniska Högskola , 2014.
Nyckelord [sv]
Datavetenskap
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:hb:diva-7244Lokalt ID: 2320/14383OAI: oai:DiVA.org:hb-7244DiVA, id: diva2:887955
Konferens
MCC14: Seventh Swedish Workshop on Multicore Computing, Lund, Sweden, 27-28 November, 2014
Tillgänglig från: 2015-12-22 Skapad: 2015-12-22 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Gidenstam, Anders

Sök vidare i DiVA

Av författaren/redaktören
Gidenstam, Anders
Av organisationen
Institutionen Handels- och IT-högskolan
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 821 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • harvard-cite-them-right
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf