Civil Rights
Movements, leaders, victories and the continuing fight for equality.
q2K BHP
Black History Portal
THE BHP WIRE —
HIDDEN TRUTHS
What's New!
Explore the people, places, events, achievements, struggles and stories that shaped our journey.
Movements, leaders, victories and the continuing fight for equality.
Innovation, patents, science, technology and world-changing contributions.
Pioneers, champions, Negro Leagues, records, activism and excellence.
Meet the people whose lives, choices and achievements shaped the journey.
Black towns, communities, institutions and places where history happened.
Moments that changed communities, movements, institutions and the nation.
Wilmington, North Carolina once had a thriving Black middle class and an elected interracial government. In 1898 white supremacists used violence to overthrow that government, kill Black residents and drive many others from the city.
MORE →Reflects the personal views, recollections, and perspective of the author, Mike Davis.
This is a personal recollection on the Move fire on May 13, 1985
 | This article needs more citations. (November 2009) |
In computer science, a concurrent data structure (also called shared data structure) is a data structure designed for access and modification by multiple computing threads (or processes or nodes) on a computer, for example concurrent queues, concurrent stacks etc. The concurrent data structure is typically considered to reside in an abstract storage environment known as shared memory, which may be physically implemented as either a tightly coupled or a distributed collection of storage modules.[1][2]
Concurrent data structures, intended for use in parallel or distributed computing environments, differ from "sequential" data structures, intended for use on a uni-processor machine, in several ways.[3] Most notably, in a sequential environment one specifies the data structure's properties and checks that they are implemented correctly, by providing safety properties. In a concurrent environment, the specification must also describe liveness properties which an implementation must provide. Safety properties usually state that something bad never happens, while liveness properties state that something good keeps happening. These properties can be expressed, for example, using linear temporal logic.
The type of liveness requirements tend to define the data structure. The method calls can be blocking or non-blocking. Data structures are not restricted to one type or the other, and can allow combinations where some method calls are blocking and others are non-blocking (examples can be found in the Java concurrency software library).
The safety properties of concurrent data structures must capture their behavior given the many possible interleavings of methods called by different threads. It is quite intuitive to specify how abstract data structures behave in a sequential setting in which there are no interleavings. Therefore, many mainstream approaches for arguing the safety properties of a concurrent data structure (such as serializability, linearizability, sequential consistency, and quiescent consistency[3]) specify the structures properties sequentially, and map its concurrent executions to a collection of sequential ones.
To guarantee the safety and liveness properties, concurrent data structures must typically (though not always) allow threads to reach consensus as to the results of their simultaneous data access and modification requests. To support such agreement, concurrent data structures are implemented using special primitive synchronization operations (see synchronization primitives) available on modern multiprocessor machines that allow multiple threads to reach consensus. This consensus can be achieved in a blocking manner by using locks, or without locks, in which case it is non-blocking. There is a wide body of theory on the design of concurrent data structures (see bibliographical references).
Concurrent data structures are significantly more difficult to design and to verify as being correct than their sequential counterparts.
The primary source of this additional difficulty is concurrency, exacerbated by the fact that threads must be thought of as being completely asynchronous: they are subject to operating system preemption, page faults, interrupts, and so on.
On today's machines, the layout of processors and memory, the layout of data in memory, the communication load on the various elements of the multiprocessor architecture all influence performance. Furthermore, there is a tension between correctness and performance: algorithmic enhancements that seek to improve performance often make it more difficult to design and verify a correct data structure implementation.[4]
A key measure for performance is scalability, captured by the speedup of the implementation. Speedup is a measure of how effectively the application is using the machine it is running on. On a machine with P processors, the speedup is the ratio of the structures execution time on a single processor to its execution time on P processors. Ideally, we want linear speedup: we would like to achieve a speedup of P when using P processors. Data structures whose speedup grows with P are called scalable. The extent to which one can scale the performance of a concurrent data structure is captured by a formula known as Amdahl's law and more refined versions of it such as Gustafson's law.
A key issue with the performance of concurrent data structures is the level of memory contention: the overhead in traffic to and from memory as a result of multiple threads concurrently attempting to access the same locations in memory. This issue is most acute with blocking implementations in which locks control access to memory. In order to acquire a lock, a thread must repeatedly attempt to modify that location. On a cache-coherent multiprocessor (one in which processors have local caches that are updated by hardware to keep them consistent with the latest values stored) this results in long waiting times for each attempt to modify the location, and is exacerbated by the additional memory traffic associated with unsuccessful attempts to acquire the lock.
.NET have ConcurrentDictionary,[5] ConcurrentQueue[6] and ConcurrentStack[7] in the System.Collections.Concurrent namespace.
Rust instead wraps data structures in Arc and Mutex.[8]
let counter = Arc::new(Mutex::new(0));
| General | |
|---|---|
| Process calculi | |
| Classic problems | |
Source: Wikipedia. Article content is retrieved live through the MediaWiki API.
In computer science, a concurrent data structure (also called shared data structure) is a data structure designed for access and modification by multiple computing threads (or processes or nodes) on a computer, for example concurrent queues, concurrent stacks etc. The concurrent data structure is typically considered to reside in an abstract storage environment known as shared memory, which may be physically implemented as either a tightly coupled or a distributed collection of storage modules.
A concurrent hash table or concurrent hash map is an implementation of hash tables allowing concurrent access by multiple threads using a hash function. Concurrent hash tables represent a key concurrent data structure for use in concurrent computing which allow multiple threads to more efficiently cooperate for a computation among shared data. Due to the natural problems associated with concurrent access - namely contention - the way and scope in which the table can be concurrently accessed differs depending on the implementation. Furthermore, the resulting speed up might not be linear with the amount of threads used as contention needs to be resolved, producing processing overhead. There exist multiple solutions to mitigate the effects of contention, that each preserve the correctness of operations on the table. As with their sequential counterpart, concurrent hash tables can be generalized and extended to fit broader applications, such as allowing more complex data types to be used for keys and values. These generalizations can however negatively impact performance and should thus be chosen in accordance to the requirements of the application.
A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots.
Disruptor is a library for the Java programming language that provides a concurrent ring buffer data structure of the same name, developed at LMAX Exchange. It is designed to provide a low-latency, high-throughput work queue in asynchronous event processing architectures. It ensures that any data is owned by only one thread for write access, therefore reducing write contention compared to other structures. The library is used for asynchronous logging in the popular Java software library Log4j.
Before the 1921 destruction of Tulsa’s Greenwood District, Black residents had created a remarkable center of business and community life. The district included stores, professional offices, entertainment venues and homes owned by Black citizens. Understanding Greenwood means learning what was built—not only what was burned.
MORE →Mae Jemison, aboard Space Shuttle Endeavour in 1992.
