Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"lock free"”.
-
Breaking serialization in lock-free multicore synchronization
… synchronization is increasingly performed in a lock-free manner using atomic instructions such as CAS or LL/SC. However, when many processors synchronize on the same variable, performance can still degrade significantly. Contending writes get serialized, creating a non-scalable condition. Past …
-
Finding linearization violations in lock-free concurrent data structures
Finding bugs in lock-free concurrent programs is hard. This is due in part to the difficulty of reasoning about the correctness of concurrent algorithms and the timing-sensitive nature of concurrent programs. One of the most widely used tools for reasoning about the correctness of concurrent …
-
Fast bug finding in lock-free data structures with CB-DPOR
… an algorithm for quickly finding bugs in lock-free data structures. CB-DPOR is a combination of the CHESS and DPOR model checking algorithms. CB-DPOR performs similar to the concurrently developed preemption-bounded BPOR algorithm. CODEX is a tool for finding bugs in lock-free data …
-
Xmalloc: a scalable lock-free dynamic memory allocator for many-core machines
… memory allocators such as atomic operation based lock-free algorithms, can be scalable with number of processors growing, but have poor scalability with the number of vector units in one SIMD processor growing. As a result, they are not truly scalable in many-core architecture. In this work, we …
-
Utility Accrual Real-Time Scheduling and Synchronization on Single and Multiprocessors: Models, Algorithms, and Tradeoffs
… Algorithm (DASA). However, they all use lock-based synchronization. To overcome shortcomings of lock-based (e.g., serialized object access, increased run-time overhead, deadlocks), we consider non-blocking synchronization including wait-free and lock-free synchronization. We present a …
-
A Wait-free Queue with Poly-logarithmic Worst-case Step Complexity
… work, we introduce a novel linearizable wait-free queue implementation. Linearizability and lock-freedom are standard requirements for designing shared data structures. To the best of our knowledge, all of the existing linearizable lock-free queues in the literature have a common problem in …
-
Real-Time Software Transactional Memory: Contention Managers, Time Bounds, and Implementations
Lock-based concurrency control suffers from programmability, scalability, and composability challenges. These challenges are exacerbated in emerging multicore architectures, on which improved software performance must be achieved by exposing greater concurrency. Transactional memory (TM) is an …
-
Utility Accrual Real-Time Scheduling: Models and Algorithms
… and analysis are extended with a class of lock-free and lock-based resource access protocols to satisfy mutual exclusion constraints. We show that satisfying utility lower bounds with lock-based resource access protocols does not imply doing so with the lock-free scheme, and vice versa. …
-
MergeArray and scalable, relaxed, concurrent, mergeable priority queues
… a linearizable and scalable priority queue with lock-free merge and insert and a relaxed, deadlock-free remove-min with expected worst-case rank-error of O(plogp) for p threads under common assumptions. I show experimental evidence that supports this rank-error estimate in practice as well as …
-
Design and Implementation of a Nonblocking Randomized Work Stealing Scheduler
This thesis presents FLCN (Free of Locks, Cilk is Now), a nonblocking work-stealing runtime scheduler that supports Cilk multithreaded programming. The existing OpenCilk runtime system uses lock-based synchronization and thus suffers from lock contention, does not provide progress guarantees, and …
-
Studying and Analysing Transactional Memory Using Interval Temporal Logic and AnaTempura
Transactional memory (TM) is a promising lock-free synchronisation technique which offers a high-level abstract parallel programming model for future chip multiprocessor (CMP) systems. Moreover, it adapts the well-established popular paradigm of transactions and thus provides a general and flexible …
-
Threaded WARPED : An Optimistic Parallel Discrete Event Simulator for Cluster of Multi-Core Machines
… atomic instructions are used to deploy lock-free data-structures and synchronization. With the addition of thread to WARPED the work also required adjustments and extensions to several of the subalgorithms of Time Warp. In particular, adjustments to the algorithm for computing Global …
-
Fast long lived renaming
… barriers, and memory reclamation schemes for lock-free data structures. In this thesis, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the LevelArray, has previously been used for hashing and one-shot (single-use) renaming. Our main …
-
Building A Scalable And High-Performance Key-Value Store System
… GET requests almost entirely. Combined with lock-free multithreaded data access, Hippos removes several performance bottlenecks both internal and external to the KV-store application.</p> <p>Hippos is prototyped as a Linux loadable kernel module and evaluated it against the ubiquitous …
-
Fast in-memory storage systems : two aspects
… is derived from a concurrent B+tree. It provides lock-free reads for good multi-core performance, which requires special care to avoid writes interfering with concurrent reads. To reduce time spent waiting for memory for workloads with long common key prefixes, Masstree arranges a set of B+trees …
-
MCFlow: Middleware for Mixed-Criticality Distributed Real-Time Systems
… (4) an event dispatching architecture that uses lock free algorithms where possible to reduce memory contention, CPU context switching, and priority inversion; and (5) empirical evaluations of MCFlow itself and of different mixed criticality scheduling approaches both with a single host and …
-
COMPLIANT END-EFFECTOR COUPLING FOR ROBOTIC ASSEMBLY
… the end-effector. The coupling has 6 degrees of freedom. The design of the coupling is based on a "Lock" & "Free" assembly idea. The coupling is locked and behaves like a stiff member during robot motion and is free (compliant) during constrained motion. It features an air bearing, a variable …
-
A scalable analysis framework for large-scale RDF data
… of hashing implementations using different lock-free strategies has been characterized through extensive experiments, thereby allowing system developers to make a more informed choice for the implementation of their high-performance analytical data processing systems. The second part of this …
-
Improving Operating System Security, Reliability, and Performance through Intra-Unikernel Isolation, Asynchronous Out-of-kernel IPC, and Advanced System Servers
… for microkernel OSs. Aoki incorporates non-blocking concurrency techniques to eliminate in-kernel blocking synchronization which causes performance challenges for state-of-the-art microkernels. Aoki's non-blocking (i.e., lock-free and wait-free) IPC design not only improves performance and …
-
The Design, Implementation, and Refinement of Wait-Free Algorithms and Containers
… of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation. In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel …